|
LLVM 23.0.0git
|
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... | |
| class | Listener |
| Rematerializer listener. 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. | |
| using | RematsOf = SmallDenseSet<RegisterIdx, 4> |
Public Member Functions | |
| Rematerializer (MachineFunction &MF, SmallVectorImpl< RegionBoundaries > &Regions, LiveIntervals &LIS) | |
| Simply initializes some internal state, does not identify rematerialization candidates. | |
| bool | analyze () |
| Goes through the whole MF and identifies all rematerializable registers. | |
| void | addListener (Listener *Listen) |
| Adds a new listener to the rematerializer. | |
| void | removeListener (Listener *Listen) |
| Removes a listener from the rematerializer. | |
| void | clearListeners () |
| Removes all listeners from the rematerializer. | |
| const Reg & | getReg (RegisterIdx RegIdx) const |
| ArrayRef< Reg > | getRegs () const |
| unsigned | getNumRegs () const |
| const RegionBoundaries & | getRegion (RegisterIdx RegionIdx) const |
| unsigned | getNumRegions () const |
| bool | isOriginalRegister (RegisterIdx RegIdx) const |
Whether register RegIdx is an original register. | |
| 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 (RegisterIdx RegIdx) const |
Returns operand indices corresponding to unrematerializable operands for any register RegIdx. | |
| RegisterIdx | getDefRegIdx (const MachineInstr &MI) const |
If MI's first operand defines a register and that register is a rematerializable register tracked by the rematerializer, returns its index in the Regs vector. | |
| RegisterIdx | rematerializeToRegion (RegisterIdx RootIdx, unsigned UseRegion, DependencyReuseInfo &DRI) |
Rematerializes register RootIdx just before its first user inside region UseRegion (or at the end of the region if it has no user), transfers all its users in the region to the new register, and returns the latter's index. | |
| RegisterIdx | rematerializeToPos (RegisterIdx RootIdx, unsigned UseRegion, MachineBasicBlock::iterator InsertPos, DependencyReuseInfo &DRI) |
Rematerializes register RootIdx before position InsertPos in UseRegion and returns the new register's index. | |
| RegisterIdx | rematerializeReg (RegisterIdx RegIdx, unsigned UseRegion, MachineBasicBlock::iterator InsertPos, SmallVectorImpl< Reg::Dependency > &&Dependencies) |
Rematerializes register RegIdx before InsertPos in UseRegion, adding the new rematerializable register to the backing vector Regs and returning its index inside the vector. | |
| void | recreateReg (RegisterIdx RegIdx, unsigned DefRegion, MachineBasicBlock::iterator InsertPos, Register DefReg, SmallVectorImpl< Reg::Dependency > &&Dependencies) |
Re-creates a previously deleted register RegIdx before InsertPos in DefRegion. | |
| 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, unsigned UserRegion, MachineInstr &UserMI) |
Transfers user UserMI in region UserRegion from register FromRegIdx to ToRegIdx, the latter of which must be a rematerialization of the former or have the same origin register. | |
| void | transferAllUsers (RegisterIdx FromRegIdx, RegisterIdx ToRegIdx) |
Transfers all users of register FromRegIdx to register 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. | |
| 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, std::optional< unsigned > UseRegion=std::nullopt) const |
Static Public Attributes | |
| static constexpr unsigned | NoReg = ~0 |
| Error value for register indices. | |
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.
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.
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 97 of file Rematerializer.h.
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 204 of file Rematerializer.h.
Index type for rematerializable registers.
Definition at line 100 of file Rematerializer.h.
| using llvm::Rematerializer::RematsOf = SmallDenseSet<RegisterIdx, 4> |
Definition at line 207 of file Rematerializer.h.
| Rematerializer::Rematerializer | ( | MachineFunction & | MF, |
| SmallVectorImpl< RegionBoundaries > & | Regions, | ||
| LiveIntervals & | LIS ) |
Simply initializes some internal state, does not identify rematerialization candidates.
Definition at line 338 of file Rematerializer.cpp.
References assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), and MI.
Referenced by llvm::Rematerializer::Listener::rematerializerNoteRegCreated(), and llvm::Rematerializer::Listener::rematerializerNoteRegDeleted().
|
inline |
Adds a new listener to the rematerializer.
Definition at line 220 of file Rematerializer.h.
References assert(), and llvm_unreachable.
| bool Rematerializer::analyze | ( | ) |
Goes through the whole MF and identifies all rematerializable registers.
Returns whether there is any rematerializable register in regions.
Maps all MIs to their parent region. Region terminators are considered part of the region they terminate.
Definition at line 361 of file Rematerializer.cpp.
References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::dbgs(), getNumRegs(), llvm::RegionBase< Tr >::getParent(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), LLVM_DEBUG, MBB, MI, printDependencyDAG(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::reserve().
|
inline |
Removes all listeners from the rematerializer.
Definition at line 233 of file Rematerializer.h.
| 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 252 of file Rematerializer.cpp.
References llvm::Rematerializer::Reg::DefMI, llvm::Rematerializer::Reg::DefRegion, getOriginOrSelf(), getReg(), llvm::SlotIndex::getRegSlot(), NoReg, and llvm::Rematerializer::Reg::Uses.
| RegisterIdx Rematerializer::getDefRegIdx | ( | const MachineInstr & | MI | ) | const |
If MI's first operand defines a register and that register is a rematerializable register tracked by the rematerializer, returns its index in the Regs vector.
Otherwise returns Rematerializer::NoReg.
Definition at line 490 of file Rematerializer.cpp.
Referenced by printUser().
|
inline |
Definition at line 246 of file Rematerializer.h.
|
inline |
Definition at line 240 of file Rematerializer.h.
Referenced by analyze().
|
inline |
Returns the origin index of rematerializable register RegIdx.
Definition at line 259 of file Rematerializer.h.
References assert(), and isRematerializedRegister().
Referenced by getOriginOrSelf(), recreateReg(), and llvm::Rollbacker::rematerializerNoteRegCreated().
|
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 265 of file Rematerializer.h.
References getOriginOf(), and isRematerializedRegister().
Referenced by findRematInRegion(), getUnrematableOprds(), and rematerializeReg().
|
inline |
Definition at line 235 of file Rematerializer.h.
References assert().
Referenced by findRematInRegion(), printDependencyDAG(), printID(), printRegUsers(), printRematReg(), recreateReg(), rematerializeToPos(), rematerializeToRegion(), llvm::Rollbacker::rollback(), and updateLiveIntervals().
|
inline |
Definition at line 242 of file Rematerializer.h.
References assert().
Definition at line 239 of file Rematerializer.h.
|
inline |
Returns operand indices corresponding to unrematerializable operands for any register RegIdx.
Definition at line 272 of file Rematerializer.h.
References getOriginOrSelf().
Referenced by updateLiveIntervals().
| 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 234 of file Rematerializer.cpp.
References llvm::MachineOperand::getParent(), llvm::MachineOperand::getReg(), llvm::MachineOperand::getSubReg(), llvm::LiveRange::getVNInfoAt(), isIdenticalAtUse(), and Uses.
|
inline |
Whether register RegIdx is an original register.
Definition at line 249 of file Rematerializer.h.
References isRematerializedRegister().
Referenced by recreateReg().
|
inline |
Whether register RegIdx is a rematerialization of some original register.
Definition at line 254 of file Rematerializer.h.
References assert().
Referenced by getOriginOf(), getOriginOrSelf(), isOriginalRegister(), and llvm::Rollbacker::rematerializerNoteRegDeleted().
| Printable Rematerializer::printDependencyDAG | ( | RegisterIdx | RootIdx | ) | const |
Definition at line 650 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().
| Printable Rematerializer::printID | ( | RegisterIdx | RegIdx | ) | const |
Definition at line 678 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(), recreateReg(), rematerializeReg(), rematerializeToPos(), and updateLiveIntervals().
| Printable Rematerializer::printRegUsers | ( | RegisterIdx | RegIdx | ) | const |
Definition at line 733 of file Rematerializer.cpp.
References getReg(), MI, printUser(), Users, and Uses.
Referenced by printDependencyDAG(), and updateLiveIntervals().
| Printable Rematerializer::printRematReg | ( | RegisterIdx | RegIdx, |
| bool | SkipRegions = false ) const |
Definition at line 692 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(), recreateReg(), and rematerializeReg().
| Printable Rematerializer::printUser | ( | const MachineInstr * | MI, |
| std::optional< unsigned > | UseRegion = std::nullopt ) const |
Definition at line 742 of file Rematerializer.cpp.
References getDefRegIdx(), MI, NoReg, and printID().
Referenced by printRegUsers().
| void Rematerializer::recreateReg | ( | RegisterIdx | RegIdx, |
| unsigned | DefRegion, | ||
| MachineBasicBlock::iterator | InsertPos, | ||
| Register | DefReg, | ||
| SmallVectorImpl< Reg::Dependency > && | Dependencies ) |
Re-creates a previously deleted register RegIdx before InsertPos in DefRegion.
DefReg must be the original virtual register that RegIdx used to define. Sets the new register's rematerializable dependencies to Dependencies (these are assumed to already exist in the MIR).
Definition at line 535 of file Rematerializer.cpp.
References assert(), llvm::dbgs(), DefMI, llvm::Rematerializer::Reg::DefMI, llvm::Rematerializer::Reg::DefRegion, llvm::Rematerializer::Reg::Dependencies, getOriginOf(), getReg(), isOriginalRegister(), LLVM_DEBUG, printID(), and printRematReg().
Referenced by llvm::Rollbacker::rollback().
| RegisterIdx Rematerializer::rematerializeReg | ( | RegisterIdx | RegIdx, |
| unsigned | UseRegion, | ||
| MachineBasicBlock::iterator | InsertPos, | ||
| SmallVectorImpl< Reg::Dependency > && | Dependencies ) |
Rematerializes register RegIdx before InsertPos in UseRegion, adding the new rematerializable register to the backing vector Regs and returning its index inside the vector.
Sets the new register's rematerializable dependencies to Dependencies (these are assumed to already exist in the MIR) and its unrematerializable dependencies to the same as RegIdx. The new register initially has no user. Since the method appends to Regs, references to elements within it should be considered invalidated across calls to this method unless the vector can be guaranteed to have enough space for an extra element.
Definition at line 501 of file Rematerializer.cpp.
References llvm::dbgs(), llvm::Rematerializer::Reg::DefMI, llvm::Rematerializer::Reg::DefRegion, llvm::Rematerializer::Reg::Dependencies, llvm::Rematerializer::Reg::getDefReg(), getOriginOrSelf(), LLVM_DEBUG, llvm::Rematerializer::Reg::Mask, printID(), and printRematReg().
Referenced by rematerializeToPos().
| RegisterIdx Rematerializer::rematerializeToPos | ( | RegisterIdx | RootIdx, |
| unsigned | UseRegion, | ||
| MachineBasicBlock::iterator | InsertPos, | ||
| DependencyReuseInfo & | DRI ) |
Rematerializes register RootIdx before position InsertPos in UseRegion 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 91 of file Rematerializer.cpp.
References assert(), llvm::dbgs(), llvm::Rematerializer::DependencyReuseInfo::DependencyMap, llvm::SmallVectorImpl< T >::emplace_back(), getReg(), LLVM_DEBUG, printID(), rematerializeReg(), and rematerializeToPos().
Referenced by rematerializeToPos(), and rematerializeToRegion().
| RegisterIdx Rematerializer::rematerializeToRegion | ( | RegisterIdx | RootIdx, |
| unsigned | UseRegion, | ||
| DependencyReuseInfo & | DRI ) |
Rematerializes register RootIdx just before its first user inside region UseRegion (or at the end of the region if it has no user), 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 75 of file Rematerializer.cpp.
References getReg(), llvm::Rematerializer::Reg::getRegionUseBounds(), rematerializeToPos(), and transferRegionUsers().
|
inline |
Removes a listener from the rematerializer.
Definition at line 227 of file Rematerializer.h.
References llvm_unreachable.
| void Rematerializer::transferAllUsers | ( | RegisterIdx | FromRegIdx, |
| RegisterIdx | ToRegIdx ) |
Transfers all users of register FromRegIdx to register ToRegIdx, the latter of which must be a rematerialization of the former or have the same origin register.
Users of FromRegIdx must be reachable from ToRegIdx.
Definition at line 143 of file Rematerializer.cpp.
References llvm::Rematerializer::Reg::Uses.
Referenced by llvm::Rollbacker::rollback().
| 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 127 of file Rematerializer.cpp.
Referenced by rematerializeToRegion().
| void Rematerializer::transferUser | ( | RegisterIdx | FromRegIdx, |
| RegisterIdx | ToRegIdx, | ||
| unsigned | UserRegion, | ||
| MachineInstr & | UserMI ) |
Transfers user UserMI in region UserRegion 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 119 of file Rematerializer.cpp.
| void Rematerializer::updateLiveIntervals | ( | ) |
Recomputes all live intervals that have changed as a result of previous rematerializations.
Definition at line 184 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::Rematerializer::Reg::isAlive(), LLVM_DEBUG, printID(), llvm::printReg(), and printRegUsers().
Referenced by llvm::Rollbacker::rollback().
|
staticconstexpr |
Error value for register indices.
Definition at line 200 of file Rematerializer.h.
Referenced by findRematInRegion(), getDefRegIdx(), printUser(), and llvm::Rollbacker::rollback().