MIR-level target-independent rematerializer. More...

#include "llvm/CodeGen/Rematerializer.h"

Classes
struct	DependencyReuseInfo
	When rematerializating a register (called the "root" register in this context) to a given position, we must decide what to do with all its rematerializable dependencies (for unrematerializable dependencies, we have no choice but to re-use the same register). More...
struct	Reg
	A rematerializable register defined by a single machine instruction. More...

Public Types
using	RegisterIdx = unsigned
	Index type for rematerializable registers.
using	RegionBoundaries
	A region's boundaries i.e.

Public Member Functions
	Rematerializer (MachineFunction &MF, SmallVectorImpl< RegionBoundaries > &Regions, LiveIntervals &LIS)
	Simply initializes some internal state, does not identify rematerialization candidates.
bool	analyze (bool SupportRollback)
	Goes through the whole MF and identifies all rematerializable registers.
const Reg &	getReg (RegisterIdx RegIdx) const
ArrayRef< Reg >	getRegs () const
unsigned	getNumRegs () const
const RegionBoundaries &	getRegion (RegisterIdx RegionIdx)
unsigned	getNumRegions () const
bool	isRematerializedRegister (RegisterIdx RegIdx) const
	Whether register `RegIdx` is a rematerialization of some original register.
RegisterIdx	getOriginOf (RegisterIdx RematRegIdx) const
	Returns the origin index of rematerializable register `RegIdx`.
RegisterIdx	getOriginOrSelf (RegisterIdx RegIdx) const
	If `RegIdx` is a rematerialization, returns its origin's index.
ArrayRef< unsigned >	getUnrematableOprds (unsigned RegIdx) const
	Returns operand indices corresponding to unrematerializable operands for any register `RegIdx`.
RegisterIdx	rematerializeToRegion (RegisterIdx RootIdx, unsigned UseRegion, DependencyReuseInfo &DRI)
	Rematerializes register `RootIdx` just before its first user inside region `UseRegion`, transfers all its users in the region to the new register, and returns the latter's index.
RegisterIdx	rematerializeToPos (RegisterIdx RootIdx, MachineBasicBlock::iterator InsertPos, DependencyReuseInfo &DRI)
	Rematerializes register `RootIdx` before position `InsertPos` and returns the new register's index.
void	rollbackRematsOf (RegisterIdx RootIdx)
	Rolls back all rematerializations of original register `RootIdx`, transfering all their users back to it and permanently deleting them from the MIR.
void	rollback (RegisterIdx RematIdx)
	Rolls back register `RematIdx` (which must be a rematerialization) transfering all its users back to its origin.
void	reviveRegIfDead (RegisterIdx RootIdx)
	Revives original register `RootIdx` at its original position in the MIR if it was fully rematerialized with rollback support set.
void	transferRegionUsers (RegisterIdx FromRegIdx, RegisterIdx ToRegIdx, unsigned UseRegion)
	Transfers all users of register `FromRegIdx` in region `UseRegion` to `ToRegIdx`, the latter of which must be a rematerialization of the former or have the same origin register.
void	transferUser (RegisterIdx FromRegIdx, RegisterIdx ToRegIdx, MachineInstr &UserMI)
	Transfers user `UserMI` from register `FromRegIdx` to `ToRegIdx`, the latter of which must be a rematerialization of the former or have the same origin register.
void	updateLiveIntervals ()
	Recomputes all live intervals that have changed as a result of previous rematerializations/rollbacks.
void	commitRematerializations ()
	Deletes unused rematerialized registers that were left in the MIR to support rollback.
bool	isMOIdenticalAtUses (MachineOperand &MO, ArrayRef< SlotIndex > Uses) const
	Determines whether (sub-)register operand `MO` has the same value at all `Uses` as at `MO`.
RegisterIdx	findRematInRegion (RegisterIdx RegIdx, unsigned Region, SlotIndex Before) const
	Finds the closest rematerialization of register `RegIdx` in region `Region` that exists before slot `Before`.
Printable	printDependencyDAG (RegisterIdx RootIdx) const
Printable	printID (RegisterIdx RegIdx) const
Printable	printRematReg (RegisterIdx RegIdx, bool SkipRegions=false) const
Printable	printRegUsers (RegisterIdx RegIdx) const
Printable	printUser (const MachineInstr *MI) const

Static Public Attributes
static constexpr unsigned	NoReg = ~0
	Error value for register indices.

Detailed Description

MIR-level target-independent rematerializer.

Provides an API to identify and rematerialize registers within a machine function.

At the moment this supports rematerializing registers that meet all of the following constraints.

The register is virtual and has a single defining instruction.
The single defining instruction is deemed rematerializable by the TII and doesn't have any physical register use that is both non-constant and non-ignorable.
The register has at least one non-debug use that is inside or at a region boundary (see below for what we consider to be a region).

Rematerializable registers (represented by Rematerializer::Reg) form a DAG of their own, with every register having incoming edges from all rematerializable registers which are read by the instruction defining it. It is possible to rematerialize registers with unrematerializable dependencies; however the latter are not considered part of this DAG since their position/identity never change and therefore do not require the same level of tracking.

Each register has a "dependency DAG" which is defined as the subset of nodes in the overall DAG that have at least one path to the register, which is called the "root" register in this context. Semantically, these nodes are the registers which are involved into the computation of the root register i.e., all of its transitive dependencies. We use the term "root" because all paths within the dependency DAG of a register terminate at it; however, there may be multiple paths between a non-root node and the root node, so a dependency DAG is not always a tree.

The API uses dense unsigned integers starting at 0 to reference rematerializable registers. These indices are immutable i.e., even when registers are deleted their respective integer handle remain valid. Method which perform actual rematerializations should however be assumed to invalidate addresses to Rematerializer::Reg objects.

The rematerializer tracks def/use points of registers based on regions. These are alike the regions the machine scheduler works on. A region is simply a pair on MBB iterators encoding a range of machine instructions. The first iterator (beginning of the region) is inclusive whereas the second iterator (end of the region) is exclusive and can either point to a MBB's end sentinel or an actual MI (not necessarily a terminator). Regions must be non-empty, cannot overlap, and cannot contain terminators. However, they do not have to cover the whole function.

The API uses dense unsigned integers starting at 0 to reference regions. These map directly to the indices of the corresponding regions in the region vector passed during construction.

The rematerializer supports rematerializing arbitrary complex DAGs of registers to regions where these registers are used, with the option of re-using non-root registers or their previous rematerializations instead of rematerializing them again. It also optionally supports rolling back previous rematerializations (set during analysis phase, see Rematerializer::analyze) to restore the MIR state to what it was pre-rematerialization. When enabled, machine instructions defining rematerializable registers that no longer have any uses following previous rematerializations will not be deleted from the MIR; their opcode will instead be set to a DEBUG_VALUE and their read register operands set to the null register. This maintains their position in the MIR and keeps the original register alive for potential rollback while allowing other passes/analyzes (e.g., machine scheduler, live-interval analysis) to ignore them. Rematerializer::commitRematerializations actually deletes those instructions when rollback is deemed unnecessary.

Throughout its lifetime, the rematerializer tracks new registers it creates (which are rematerializable by construction) and their relations to other registers. It performs DAG updates immediately on rematerialization but defers/batches all necessary live interval updates to reduce the number of expensive LIS queries when successively rematerializing many registers. Rematerializer::updateLiveIntervals performs all currently batched live interval updates.

In its nomenclature, the rematerializer differentiates between "original registers" (registers that were present when it analyzed the function) and rematerializations of these original registers. Rematerializations have an "origin" which is the index of the original regiser they were rematerialized from (transitivity applies; a rematerialization and all of its own rematerializations have the same origin). Semantically, only original registers have rematerializations.

Definition at line 107 of file Rematerializer.h.

Member Typedef Documentation

◆ RegionBoundaries

using llvm::Rematerializer::RegionBoundaries

Initial value:

std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>

A region's boundaries i.e.

a pair of instruction bundle iterators. The lower boundary is inclusive, the upper boundary is exclusive.

Definition at line 194 of file Rematerializer.h.

◆ RegisterIdx

using llvm::Rematerializer::RegisterIdx = unsigned

Index type for rematerializable registers.

Definition at line 110 of file Rematerializer.h.

Constructor & Destructor Documentation

◆ Rematerializer()

Rematerializer::Rematerializer	(	MachineFunction &	MF,
		SmallVectorImpl< RegionBoundaries > &	Regions,
		LiveIntervals &	LIS )

Simply initializes some internal state, does not identify rematerialization candidates.

Definition at line 417 of file Rematerializer.cpp.

References assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), and MI.

Member Function Documentation

◆ analyze()

bool Rematerializer::analyze ( bool SupportRollback )

Goes through the whole MF and identifies all rematerializable registers.

When SupportRollback is set, rematerializations of original registers can be rolled back and original registers are maintained in the IR even when they longer have any users. Returns whether there is any rematerializable register in regions.

Definition at line 440 of file Rematerializer.cpp.

References assert(), llvm::dbgs(), getNumRegs(), llvm::RegionBase< Tr >::getParent(), I, LLVM_DEBUG, MI, and printDependencyDAG().

◆ commitRematerializations()

void Rematerializer::commitRematerializations ( )

Deletes unused rematerialized registers that were left in the MIR to support rollback.

Definition at line 297 of file Rematerializer.cpp.

References _.

◆ findRematInRegion()

RegisterIdx Rematerializer::findRematInRegion	(	RegisterIdx	RegIdx,
		unsigned	Region,
		SlotIndex	Before ) const

Finds the closest rematerialization of register RegIdx in region Region that exists before slot Before.

If no such rematerialization exists, returns Rematerializer::NoReg.

Definition at line 321 of file Rematerializer.cpp.

References llvm::Rematerializer::Reg::DefMI, llvm::Rematerializer::Reg::DefRegion, getOriginOrSelf(), getReg(), llvm::SlotIndex::getRegSlot(), NoReg, and llvm::Rematerializer::Reg::Uses.

◆ getNumRegions()

unsigned llvm::Rematerializer::getNumRegions ( ) const

inline

Definition at line 221 of file Rematerializer.h.

◆ getNumRegs()

unsigned llvm::Rematerializer::getNumRegs ( ) const

inline

Definition at line 215 of file Rematerializer.h.

Referenced by analyze().

◆ getOriginOf()

RegisterIdx llvm::Rematerializer::getOriginOf ( RegisterIdx RematRegIdx ) const

inline

Returns the origin index of rematerializable register RegIdx.

Definition at line 230 of file Rematerializer.h.

References assert(), and isRematerializedRegister().

Referenced by getOriginOrSelf(), and rollback().

◆ getOriginOrSelf()

RegisterIdx llvm::Rematerializer::getOriginOrSelf ( RegisterIdx RegIdx ) const

inline

If RegIdx is a rematerialization, returns its origin's index.

If it is an original register's index, returns the same index.

Definition at line 236 of file Rematerializer.h.

References getOriginOf(), and isRematerializedRegister().

Referenced by findRematInRegion(), and getUnrematableOprds().

◆ getReg()

const Reg & llvm::Rematerializer::getReg ( RegisterIdx RegIdx ) const

inline

Definition at line 210 of file Rematerializer.h.

References assert().

Referenced by findRematInRegion(), printDependencyDAG(), printID(), printRegUsers(), printRematReg(), rematerializeToPos(), rematerializeToRegion(), reviveRegIfDead(), rollback(), and updateLiveIntervals().

◆ getRegion()

const RegionBoundaries & llvm::Rematerializer::getRegion ( RegisterIdx RegionIdx )

inline

Definition at line 217 of file Rematerializer.h.

References assert().

◆ getRegs()

ArrayRef< Reg > llvm::Rematerializer::getRegs ( ) const

inline

Definition at line 214 of file Rematerializer.h.

◆ getUnrematableOprds()

ArrayRef< unsigned > llvm::Rematerializer::getUnrematableOprds ( unsigned RegIdx ) const

inline

Returns operand indices corresponding to unrematerializable operands for any register RegIdx.

Definition at line 243 of file Rematerializer.h.

References getOriginOrSelf().

Referenced by updateLiveIntervals().

◆ isMOIdenticalAtUses()

bool Rematerializer::isMOIdenticalAtUses	(	MachineOperand &	MO,
		ArrayRef< SlotIndex >	Uses ) const

Determines whether (sub-)register operand MO has the same value at all Uses as at MO.

This implies that it is also available at all Uses according to its current live interval.

Definition at line 303 of file Rematerializer.cpp.

References llvm::MachineOperand::getParent(), llvm::MachineOperand::getReg(), llvm::MachineOperand::getSubReg(), llvm::LiveRange::getVNInfoAt(), isIdenticalAtUse(), and Uses.

◆ isRematerializedRegister()

bool llvm::Rematerializer::isRematerializedRegister ( RegisterIdx RegIdx ) const

inline

Whether register RegIdx is a rematerialization of some original register.

Definition at line 225 of file Rematerializer.h.

References assert().

Referenced by getOriginOf(), and getOriginOrSelf().

◆ printDependencyDAG()

Printable Rematerializer::printDependencyDAG ( RegisterIdx RootIdx ) const

Definition at line 684 of file Rematerializer.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::begin(), llvm::Depth, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::emplace_or_assign(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), getReg(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup_or(), printID(), printRegUsers(), printRematReg(), and llvm::sort().

Referenced by analyze().

◆ printID()

Printable Rematerializer::printID ( RegisterIdx RegIdx ) const

Definition at line 712 of file Rematerializer.cpp.

References llvm::Rematerializer::Reg::DefMI, llvm::Rematerializer::Reg::DefRegion, llvm::Rematerializer::Reg::getDefReg(), llvm::MachineInstr::getOperand(), getReg(), llvm::MachineOperand::getSubReg(), and llvm::printReg().

Referenced by printDependencyDAG(), printRematReg(), printUser(), rematerializeToPos(), reviveRegIfDead(), rollbackRematsOf(), and updateLiveIntervals().

◆ printRegUsers()

Printable Rematerializer::printRegUsers ( RegisterIdx RegIdx ) const

Definition at line 767 of file Rematerializer.cpp.

References _, llvm::dbgs(), getReg(), MI, printUser(), Users, and Uses.

Referenced by printDependencyDAG(), and updateLiveIntervals().

◆ printRematReg()

Printable Rematerializer::printRematReg	(	RegisterIdx	RegIdx,
		bool	SkipRegions = false ) const

Definition at line 726 of file Rematerializer.cpp.

References assert(), llvm::Rematerializer::Reg::DefMI, llvm::Rematerializer::Reg::DefRegion, llvm::enumerate(), llvm::First, llvm::Rematerializer::Reg::getDefReg(), getReg(), I, llvm::LiveRange::liveAt(), llvm::MachineInstr::print(), printID(), and llvm::Rematerializer::Reg::Uses.

Referenced by printDependencyDAG().

◆ printUser()

Printable Rematerializer::printUser ( const MachineInstr * MI ) const

Definition at line 776 of file Rematerializer.cpp.

References llvm::dbgs(), MI, NoReg, and printID().

Referenced by printRegUsers(), and rematerializeToPos().

◆ rematerializeToPos()

RegisterIdx Rematerializer::rematerializeToPos	(	RegisterIdx	RootIdx,
		MachineBasicBlock::iterator	InsertPos,
		DependencyReuseInfo &	DRI )

Rematerializes register RootIdx before position InsertPos and returns the new register's index.

The root's dependency DAG is rematerialized or re-used according to DRI.

When the method returns, DRI contains additional entries for non-root registers of the root's dependency DAG that needed to be rematerialized along the root. References to Rematerializer::Reg should be considered invalidated by calls to this method.

Definition at line 83 of file Rematerializer.cpp.

References assert(), llvm::SetVector< T, Vector, Set, N >::contains(), llvm::dbgs(), llvm::Rematerializer::DependencyReuseInfo::DependencyMap, llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), getReg(), llvm::SetVector< T, Vector, Set, N >::insert(), LLVM_DEBUG, llvm::SmallVectorImpl< T >::pop_back_val(), printID(), printUser(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::reverse().

Referenced by rematerializeToRegion().

◆ rematerializeToRegion()

RegisterIdx Rematerializer::rematerializeToRegion	(	RegisterIdx	RootIdx,
		unsigned	UseRegion,
		DependencyReuseInfo &	DRI )

Rematerializes register RootIdx just before its first user inside region UseRegion, transfers all its users in the region to the new register, and returns the latter's index.

The root's dependency DAG is rematerialized or re-used according to DRI.

When the method returns, DRI contains additional entries for non-root registers of the root's dependency DAG that needed to be rematerialized along the root. References to Rematerializer::Reg should be considered invalidated by calls to this method.

Definition at line 72 of file Rematerializer.cpp.

References getReg(), llvm::Rematerializer::Reg::getRegionUseBounds(), rematerializeToPos(), and transferRegionUsers().

◆ reviveRegIfDead()

void Rematerializer::reviveRegIfDead ( RegisterIdx RootIdx )

Revives original register RootIdx at its original position in the MIR if it was fully rematerialized with rollback support set.

Transitive dependencies of the root register that were fully rematerialized are revived at their original positions; this requires that rollback support was set when they were themselves rematerialized.

Definition at line 154 of file Rematerializer.cpp.

References assert(), llvm::SetVector< T, Vector, Set, N >::contains(), llvm::dbgs(), DefMI, llvm::Rematerializer::Reg::DefMI, llvm::Rematerializer::Reg::DefRegion, llvm::Rematerializer::Reg::Dependencies, llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::MachineInstr::getOperand(), getReg(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::Rematerializer::Reg::isAlive(), LLVM_DEBUG, llvm::SmallVectorImpl< T >::pop_back_val(), printID(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Rematerializer::Reg::Dependency::RegIdx, llvm::reverse(), llvm::MachineInstr::setDesc(), and llvm::MachineOperand::setReg().

Referenced by rollback(), and rollbackRematsOf().

◆ rollback()

void Rematerializer::rollback ( RegisterIdx RematIdx )

Rolls back register RematIdx (which must be a rematerialization) transfering all its users back to its origin.

The latter is revived if it was fully rematerialized (this requires that rollback support was set at that time).

Definition at line 145 of file Rematerializer.cpp.

References assert(), DefMI, getOriginOf(), getReg(), reviveRegIfDead(), transferRegionUsers(), and Uses.

◆ rollbackRematsOf()

void Rematerializer::rollbackRematsOf ( RegisterIdx RootIdx )

Rolls back all rematerializations of original register RootIdx, transfering all their users back to it and permanently deleting them from the MIR.

The root register is revived if it was fully rematerialized (this requires that rollback support was set at that time). Transitive dependencies of the root register that were fully rematerialized are re-vived at their original positions; this requires that rollback support was set when they were rematerialized.

Definition at line 125 of file Rematerializer.cpp.

References llvm::dbgs(), LLVM_DEBUG, printID(), reviveRegIfDead(), transferRegionUsers(), and Uses.

◆ transferRegionUsers()

void Rematerializer::transferRegionUsers	(	RegisterIdx	FromRegIdx,
		RegisterIdx	ToRegIdx,
		unsigned	UseRegion )

Transfers all users of register FromRegIdx in region UseRegion to ToRegIdx, the latter of which must be a rematerialization of the former or have the same origin register.

Users in UseRegion must be reachable from ToRegIdx.

Definition at line 214 of file Rematerializer.cpp.

Referenced by rematerializeToRegion(), rollback(), and rollbackRematsOf().

◆ transferUser()

void Rematerializer::transferUser	(	RegisterIdx	FromRegIdx,
		RegisterIdx	ToRegIdx,
		MachineInstr &	UserMI )

Transfers user UserMI from register FromRegIdx to ToRegIdx, the latter of which must be a rematerialization of the former or have the same origin register.

UserMI must be a direct user of FromRegIdx. UserMI must be reachable from ToRegIdx.

Definition at line 205 of file Rematerializer.cpp.

◆ updateLiveIntervals()

void Rematerializer::updateLiveIntervals ( )

Recomputes all live intervals that have changed as a result of previous rematerializations/rollbacks.

Definition at line 262 of file Rematerializer.cpp.

References assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear(), llvm::dbgs(), llvm::Rematerializer::Reg::DefMI, llvm::Rematerializer::Reg::getDefReg(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getReg(), getReg(), llvm::MachineOperand::getSubReg(), getUnrematableOprds(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), LLVM_DEBUG, printID(), llvm::printReg(), and printRegUsers().

Member Data Documentation

◆ NoReg

unsigned llvm::Rematerializer::NoReg = ~0

staticconstexpr

Error value for register indices.

Definition at line 190 of file Rematerializer.h.

Referenced by findRematInRegion(), and printUser().

The documentation for this class was generated from the following files:

include/llvm/CodeGen/Rematerializer.h
lib/CodeGen/Rematerializer.cpp

Classes

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ RegionBoundaries

◆ RegisterIdx

Constructor & Destructor Documentation

◆ Rematerializer()

Member Function Documentation

◆ analyze()

◆ commitRematerializations()

◆ findRematInRegion()

◆ getNumRegions()

◆ getNumRegs()

◆ getOriginOf()

◆ getOriginOrSelf()

◆ getReg()

◆ getRegion()

◆ getRegs()

◆ getUnrematableOprds()

◆ isMOIdenticalAtUses()

◆ isRematerializedRegister()

◆ printDependencyDAG()

◆ printID()

◆ printRegUsers()

◆ printRematReg()

◆ printUser()

◆ rematerializeToPos()

◆ rematerializeToRegion()

◆ reviveRegIfDead()

◆ rollback()

◆ rollbackRematsOf()

◆ transferRegionUsers()

◆ transferUser()

◆ updateLiveIntervals()

Member Data Documentation

◆ NoReg