Go to the documentation of this file.
38 #include "llvm/Config/llvm-config.h"
50 #define DEBUG_TYPE "regalloc"
52 STATISTIC(NumSpillSlots,
"Number of spill slots allocated");
53 STATISTIC(NumIdCopies,
"Number of identity moves eliminated after rewriting");
64 MRI = &mf.getRegInfo();
65 TII = mf.getSubtarget().getInstrInfo();
66 TRI = mf.getSubtarget().getRegisterInfo();
70 Virt2StackSlotMap.clear();
71 Virt2SplitMap.clear();
72 Virt2ShapeMap.clear();
80 Virt2PhysMap.resize(NumRegs);
81 Virt2StackSlotMap.resize(NumRegs);
82 Virt2SplitMap.resize(NumRegs);
88 "attempt to assign physical register to already mapped "
91 "Attempt to map virtReg to a reserved physReg");
92 Virt2PhysMap[virtReg.
id()] = physReg;
100 Align CurrentAlign =
ST.getFrameLowering()->getStackAlign();
101 if (Alignment > CurrentAlign && !
ST.getRegisterInfo()->canRealignStack(*MF)) {
102 Alignment = CurrentAlign;
130 "attempt to assign stack slot to already spilled register");
132 return Virt2StackSlotMap[virtReg.
id()] = createSpillSlot(RC);
138 "attempt to assign stack slot to already spilled register");
141 "illegal fixed frame index");
142 Virt2StackSlotMap[virtReg.
id()] =
SS;
146 OS <<
"********** REGISTER MAP **********\n";
159 OS <<
'[' <<
printReg(
Reg, TRI) <<
" -> fi#" << Virt2StackSlotMap[
Reg]
166 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
196 void addMBBLiveIns();
205 VirtRegRewriter(
bool ClearVirtRegs_ =
true) :
207 ClearVirtRegs(ClearVirtRegs_) {}
230 "Virtual Register Rewriter",
false,
false)
239 void VirtRegRewriter::getAnalysisUsage(
AnalysisUsage &AU)
const {
240 AU.setPreservesCFG();
261 Indexes = &getAnalysis<SlotIndexes>();
262 LIS = &getAnalysis<LiveIntervals>();
263 VRM = &getAnalysis<VirtRegMap>();
264 DebugVars = getAnalysisIfAvailable<LiveDebugVariables>();
265 LLVM_DEBUG(
dbgs() <<
"********** REWRITE VIRTUAL REGISTERS **********\n"
266 <<
"********** Function: " << MF->
getName() <<
'\n');
278 if (DebugVars && ClearVirtRegs) {
294 void VirtRegRewriter::addLiveInsForSubRanges(
const LiveInterval &LI,
299 using SubRangeIteratorPair =
300 std::pair<const LiveInterval::SubRange *, LiveInterval::const_iterator>;
306 SubRanges.push_back(std::make_pair(&SR, SR.begin()));
307 if (!
First.isValid() || SR.segments.front().start < First)
308 First = SR.segments.front().start;
309 if (!
Last.isValid() || SR.segments.back().end > Last)
310 Last = SR.segments.back().end;
321 for (
auto &RangeIterPair : SubRanges) {
324 while (SRI != SR->
end() && SRI->end <= MBBBegin)
326 if (SRI == SR->
end())
328 if (SRI->start <= MBBBegin)
340 void VirtRegRewriter::addMBBLiveIns() {
354 assert(!ClearVirtRegs &&
"Unmapped virtual register");
359 addLiveInsForSubRanges(LI, PhysReg);
365 for (
const auto &Seg : LI) {
383 bool VirtRegRewriter::readsUndefSubreg(
const MachineOperand &MO)
const {
395 "Reads of completely dead register should be marked undef already");
408 if (!
MI.isIdentityCopy())
420 RewriteRegs.
insert(DstReg);
428 if (
MI.getOperand(1).isUndef() ||
MI.getNumOperands() > 2) {
429 MI.setDesc(
TII->get(TargetOpcode::KILL));
436 MI.eraseFromBundle();
445 if (!
MI.isCopy() && !
MI.isKill())
448 if (
MI.isBundledWithPred() && !
MI.isBundledWithSucc()) {
455 I !=
E &&
I->isBundledWithSucc(); ++
I) {
456 if (!
I->isCopy() && !
I->isKill())
468 Src->getOperand(1).getReg()))
476 for (
int E = MIs.size(), PrevE =
E;
E > 1; PrevE =
E) {
477 for (
int I =
E;
I--; )
484 MF->getFunction().getContext().emitError(
485 "register rewriting failed: cycle in copy bundle");
495 if (BundledMI != BundleStart) {
498 }
else if (BundledMI->isBundledWithSucc()) {
499 BundledMI->unbundleFromSucc();
500 BundleStart = &*std::next(BundledMI->getIterator());
503 if (Indexes && BundledMI != FirstMI)
529 if (UnitRange.
liveAt(AfterMIDefs) && UnitRange.
liveAt(BeforeMIUses))
559 RewriteRegs.
insert(PhysReg);
570 (MO.
isDef() && subRegLiveThrough(
MI, PhysReg)))
571 SuperKills.push_back(PhysReg);
576 SuperDeads.push_back(PhysReg);
578 SuperDefs.push_back(PhysReg);
582 if (readsUndefSubreg(MO))
587 }
else if (!MO.
isDead()) {
603 assert(PhysReg.
isValid() &&
"Invalid SubReg for physical register");
614 while (!SuperKills.empty())
617 while (!SuperDeads.empty())
620 while (!SuperDefs.empty())
625 expandCopyBundle(
MI);
628 handleIdentityCopy(
MI);
635 for (
Register PhysReg : RewriteRegs) {
647 return new VirtRegRewriter(ClearVirtRegs);
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This is an optimization pass for GlobalISel generic memory operations.
bool subRegLivenessEnabled() const
void setIsInternalRead(bool Val=true)
bool shouldTrackSubRegLiveness(const TargetRegisterClass &RC) const
Returns true if liveness for register class RC should be tracked at the subregister level.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
bool hasPreferredPhys(Register VirtReg) const
returns true if VirtReg is assigned to its preferred physreg.
virtual const TargetInstrInfo * getInstrInfo() const
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
MachineInstr * removeFromBundle()
Unlink this instruction from its basic block and return it without deleting it.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
bool hasKnownPreference(Register VirtReg) const
returns true if VirtReg has a known preferred register.
FunctionPass * createVirtRegRewriter(bool ClearVirtRegs=true)
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Reg
All possible values of the reg field in the ModR/M byte.
void assignVirt2Phys(Register virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void addKillFlags(const VirtRegMap *)
Add kill flags to any instruction that kills a virtual register.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Properties which a MachineFunction may have at a given point in time.
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
LLVM_NODISCARD T pop_back_val()
std::pair< iterator, bool > insert(const ValueT &V)
unsigned const TargetRegisterInfo * TRI
void removeRegUnit(unsigned Unit)
Remove computed live range for register unit Unit.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
TargetInstrInfo - Interface to description of machine instruction set.
bool liveAt(SlotIndex index) const
Virtual Register Rewriter
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
Segments::const_iterator const_iterator
void setSubReg(unsigned subReg)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Represent the analysis usage information of a pass.
const HexagonInstrInfo * TII
into llvm powi allowing the code generator to produce balanced multiplication trees First
MachineOperand class - Representation of each machine instruction operand.
MachineFunctionProperties & set(Property P)
STATISTIC(NumFunctions, "Total number of functions")
This class implements an extremely fast bulk output stream that can only output to a stream.
LiveInterval - This class represents the liveness of a register, or stack slot.
This struct is a compact representation of a valid (non-zero power of two) alignment.
void removeSingleMachineInstrFromMaps(MachineInstr &MI)
Removes a single machine instruction MI from the mapping.
int getObjectIndexBegin() const
Return the minimum frame object index.
SlotIndex - An opaque wrapper around machine indexes.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
INITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter", "Virtual Register Rewriter", false, false) INITIALIZE_PASS_END(VirtRegRewriter
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
MBBIndexIterator findMBBIndex(SlotIndex Idx) const
Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex that is greater or equal to Idx...
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
int CreateSpillStackObject(uint64_t Size, Align Alignment)
Create a new statically sized stack object that represents a spill slot, returning a nonnegative iden...
MBBIndexIterator MBBIndexEnd() const
Return an iterator for the end of the idx2MBBMap.
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
char & VirtRegRewriterID
VirtRegRewriter pass.
MachineRegisterInfo & getRegInfo() const
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Align getSpillAlign(const TargetRegisterClass &RC) const
Return the minimum required alignment in bytes for a spill slot for a register of this class.
Implements a dense probed hash-table based set.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
unsigned getSpillSize(const TargetRegisterClass &RC) const
Return the size in bytes of the stack slot allocated to hold a spilled copy of a register from class ...
bool regsOverlap(Register RegA, Register RegB) const
Returns true if the two registers are equal or alias each other.
reverse_instr_iterator instr_rend()
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
This class represents the liveness of a register, stack slot, etc.
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
MBBIndexIterator MBBIndexBegin() const
Returns an iterator for the begin of the idx2MBBMap.
MCRegister getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Register getReg() const
getReg - Returns the register number.
A Module instance is used to store all the information related to an LLVM module.
LiveInterval & getInterval(Register Reg)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
MBBIndexIterator advanceMBBIndex(MBBIndexIterator I, SlotIndex To) const
Move iterator to the next IdxMBBPair where the SlotIndex is greater or equal to To.
constexpr bool none() const
MachineBasicBlock MachineBasicBlock::iterator MBBI
void setIsUndef(bool Val=true)
void clearAllVirt()
clears all virtual to physical register mappings
void setIsRenamable(bool Val=true)
A live range for subregisters.
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
unsigned getSubReg() const
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
static bool rewrite(Function &F)
Register getSimpleHint(Register VReg) const
getSimpleHint - same as getRegAllocationHint except it will only return a target independent hint.
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Iterator for intrusive lists based on ilist_node.
SmallVectorImpl< IdxMBBPair >::const_iterator MBBIndexIterator
Iterator over the idx2MBBMap (sorted pairs of slot index of basic block begin and basic block)
int assignVirt2StackSlot(Register virtReg)
create a mapping for the specifed virtual register to the next available stack slot
void addPhysRegsUsedFromRegMask(const uint32_t *RegMask)
addPhysRegsUsedFromRegMask - Mark any registers not in RegMask as used.
void clearVirtRegs()
clearVirtRegs - Remove all virtual registers (after physreg assignment).
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
void setReg(Register Reg)
Change the register this operand corresponds to.
bool hasSubRanges() const
Returns true if subregister liveness information is available.
MCRegister getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo.
FunctionPass class - This class is used to implement most global optimizations.
void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
void emitDebugValues(VirtRegMap *VRM)
emitDebugValues - Emit new DBG_VALUE instructions reflecting the changes that happened during registe...
std::pair< Register, Register > getRegAllocationHint(Register VReg) const
getRegAllocationHint - Return the register allocation hint for the specified virtual register.
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
Wrapper class representing physical registers. Should be passed by value.
iterator_range< subrange_iterator > subranges()