47#define DEBUG_TYPE "reg-scavenging"
49STATISTIC(NumScavengedRegs,
"Number of frame index regs scavenged");
68 KillRegUnits.
resize(NumRegUnits);
69 DefRegUnits.
resize(NumRegUnits);
70 TmpRegUnits.
resize(NumRegUnits);
74 for (ScavengedInfo &SI : Scavenged) {
93 MBBI = std::prev(
MBB.
end());
108void RegScavenger::determineKillsAndDefs() {
109 assert(Tracking &&
"Must be tracking to determine kills and defs");
112 assert(!
MI.isDebugInstr() &&
"Debug values have no kills or defs");
116 KillRegUnits.
reset();
119 if (MO.isRegMask()) {
121 for (
unsigned RU = 0, RUEnd = TRI->
getNumRegUnits(); RU != RUEnd; ++RU) {
123 if (MO.clobbersPhysReg(*RURI)) {
131 KillRegUnits |= TmpRegUnits;
135 if (!MO.getReg().isPhysical() || isReserved(MO.getReg()))
144 addRegUnits(KillRegUnits, Reg);
148 addRegUnits(KillRegUnits, Reg);
150 addRegUnits(DefRegUnits, Reg);
161 assert(MBBI !=
MBB->
end() &&
"Already past the end of the basic block!");
162 MBBI = std::next(MBBI);
164 assert(MBBI !=
MBB->
end() &&
"Already at the end of the basic block!");
168 for (ScavengedInfo &
I : Scavenged) {
169 if (
I.Restore != &
MI)
176 if (
MI.isDebugOrPseudoInstr())
179 determineKillsAndDefs();
187 if (!Reg.isPhysical() || isReserved(Reg))
201 bool SubUsed =
false;
207 bool SuperUsed =
false;
214 if (!SubUsed && !SuperUsed) {
226 assert((KillRegs.test(Reg) || isUnused(Reg) ||
227 isLiveInButUnusedBefore(Reg,
MI,
MBB, TRI, MRI)) &&
228 "Re-defining a live register!");
235 setUnused(KillRegUnits);
236 setUsed(DefRegUnits);
240 assert(Tracking &&
"Must be tracking to determine kills and defs");
246 for (ScavengedInfo &
I : Scavenged) {
247 if (
I.Restore == &
MI) {
262 return includeReserved;
290 assert(Survivor > 0 &&
"No candidates for scavenging");
293 assert(StartMI != ME &&
"MI already at terminator");
297 bool inVirtLiveRange =
false;
299 if (
MI->isDebugOrPseudoInstr()) {
303 bool isVirtKillInsn =
false;
304 bool isVirtDefInsn =
false;
309 if (!MO.isReg() || MO.isUndef() || !MO.getReg())
311 if (MO.getReg().isVirtual()) {
313 isVirtDefInsn =
true;
314 else if (MO.isKill())
315 isVirtKillInsn =
true;
319 Candidates.
reset(*AI);
323 if (!inVirtLiveRange) RestorePointMI =
MI;
326 if (isVirtKillInsn) inVirtLiveRange =
false;
327 if (isVirtDefInsn) inVirtLiveRange =
true;
330 if (Candidates.
test(Survivor))
334 if (Candidates.
none())
340 if (
MI == ME) RestorePointMI = ME;
341 assert(RestorePointMI != StartMI &&
342 "No available scavenger restore location!");
345 UseMI = RestorePointMI;
356static std::pair<MCPhysReg, MachineBasicBlock::iterator>
361 bool FoundTo =
false;
370 assert(
From->getParent() == To->getParent() &&
371 "Target instruction is in other than current basic block, use "
372 "enterBasicBlockEnd first");
382 if (!
MRI.isReserved(Reg) && Used.available(Reg) &&
384 return std::make_pair(Reg,
MBB.
end());
394 Used.accumulate(*std::next(
From));
404 if (Survivor == 0 || !Used.available(Survivor)) {
407 if (!
MRI.isReserved(Reg) && Used.available(Reg)) {
412 if (AvilableReg == 0)
414 Survivor = AvilableReg;
416 if (--InstrCountDown == 0)
421 bool FoundVReg =
false;
423 if (MO.isReg() && MO.getReg().isVirtual()) {
436 "iterating backwards");
439 return std::make_pair(Survivor, Pos);
444 while (!
MI.getOperand(i).isFI()) {
446 assert(i <
MI.getNumOperands() &&
"Instr doesn't have FrameIndex operand!");
451RegScavenger::ScavengedInfo &
462 unsigned SI = Scavenged.
size(), Diff = std::numeric_limits<unsigned>::max();
464 for (
unsigned I = 0;
I < Scavenged.
size(); ++
I) {
465 if (Scavenged[
I].Reg != 0)
468 int FI = Scavenged[
I].FrameIndex;
469 if (FI < FIB || FI >= FIE)
473 if (NeedSize > S || NeedAlign >
A)
481 unsigned D = (S - NeedSize) + (
A.value() - NeedAlign.
value());
488 if (SI == Scavenged.
size()) {
495 Scavenged[
SI].Reg =
Reg;
501 int FI = Scavenged[
SI].FrameIndex;
502 if (FI < FIB || FI >= FIE) {
504 TRI->
getName(Reg) +
" from class " +
506 ": Cannot scavenge register without an emergency "
517 II = std::prev(
UseMI);
522 return Scavenged[
SI];
527 int SPAdj,
bool AllowSpill) {
535 if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
536 !MO.getReg().isVirtual())
538 Candidates.
reset(*AI);
545 for (ScavengedInfo &
SI : Scavenged) {
550 " from scavenging candidates since it was already scavenged\n");
552 Candidates.
reset(*AI);
578 for (ScavengedInfo &
SI : Scavenged) {
579 assert(
SI.Reg != SReg &&
"scavenged a previously scavenged register");
583 ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj,
I,
UseMI);
584 Scavenged.Restore = &*std::prev(
UseMI);
594 bool RestoreAfter,
int SPAdj,
602 std::pair<MCPhysReg, MachineBasicBlock::iterator>
P =
608 if (Reg != 0 && SpillBefore ==
MBB.
end()) {
617 assert(Reg != 0 &&
"No register left to scavenge!");
620 RestoreAfter ? std::next(MBBI) : MBBI;
622 if (ReloadBefore !=
MBB.
end())
624 ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
625 Scavenged.Restore = &*std::prev(SpillBefore);
628 <<
" until " << *SpillBefore);
647 if (CommonMBB ==
nullptr)
649 assert(
MBB == CommonMBB &&
"All defs+uses must be in the same basic block");
652 if (!
MI.readsRegister(VReg, &
TRI)) {
653 assert((!RealDef || RealDef == &
MI) &&
654 "Can have at most one definition which is not a redefinition");
659 assert(RealDef !=
nullptr &&
"Must have at least 1 Def");
670 return !MO.getParent()->readsRegister(VReg, &TRI);
673 "Must have one definition that does not redefine vreg");
681 ReserveAfter, SPAdj);
682 MRI.replaceRegWith(VReg, SReg);
696 unsigned InitialNumVirtRegs =
MRI.getNumVirtRegs();
697 bool NextInstructionReadsVReg =
false;
704 if (NextInstructionReadsVReg) {
714 if (!Reg.isVirtual() ||
721 N->addRegisterKilled(SReg, &
TRI,
false);
727 NextInstructionReadsVReg =
false;
734 if (!Reg.isVirtual() ||
740 assert(!MO.isInternalRead() &&
"Cannot assign inside bundles");
741 assert((!MO.isUndef() || MO.isDef()) &&
"Cannot handle undef uses");
743 NextInstructionReadsVReg =
true;
747 I->addRegisterDead(SReg, &
TRI,
false);
753 if (!MO.isReg() || !MO.getReg().isVirtual())
755 assert(!MO.isInternalRead() &&
"Cannot assign inside bundles");
756 assert((!MO.isUndef() || MO.isDef()) &&
"Cannot handle undef uses");
757 assert(!MO.readsReg() &&
"Vreg use in first instruction not allowed");
761 return MRI.getNumVirtRegs() != InitialNumVirtRegs;
770 if (
MRI.getNumVirtRegs() == 0) {
782 LLVM_DEBUG(
dbgs() <<
"Warning: Required two scavenging passes for block "
826char ScavengerTest::ID;
829 "Scavenge virtual registers inside basic blocks",
false,
false)
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
This file implements the BitVector class.
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static cl::opt< unsigned > InstrLimit("dfa-instr-limit", cl::Hidden, cl::init(0), cl::desc("If present, stops packetizing after N instructions"))
@ Available
We know the block is fully available. This is a fixpoint.
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
static Register scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS, Register VReg, bool ReserveAfter)
Allocate a register for the virtual register VReg.
static unsigned getFrameIndexOperandNum(MachineInstr &MI)
static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI, RegScavenger &RS, MachineBasicBlock &MBB)
Allocate (scavenge) vregs inside a single basic block.
static std::pair< MCPhysReg, MachineBasicBlock::iterator > findSurvivorBackwards(const MachineRegisterInfo &MRI, MachineBasicBlock::iterator From, MachineBasicBlock::iterator To, const LiveRegUnits &LiveOut, ArrayRef< MCPhysReg > AllocationOrder, bool RestoreAfter)
Given the bitvector Available of free register units at position From.
This file declares the machine register scavenger class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool test(unsigned Idx) const
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
bool none() const
none - Returns true if none of the bits are set.
A set of register units used to track register liveness.
void addRegMasked(MCPhysReg Reg, LaneBitmask Mask)
Adds register units covered by physical register Reg that are part of the lanemask Mask.
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
void init(const TargetRegisterInfo &TRI)
Initialize and clear the set.
void stepBackward(const MachineInstr &MI)
Updates liveness when stepping backwards over the instruction MI.
void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of block MBB.
void addLiveIns(const MachineBasicBlock &MBB)
Adds registers living into block MBB.
void removeReg(MCPhysReg Reg)
Removes all register units covered by physical register Reg.
MCRegAliasIterator enumerates all registers aliasing Reg.
MCRegUnitRootIterator enumerates the root registers of a register unit.
bool isValid() const
Check if the iterator is at the end of the list.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
const char * getName(MCRegister RegNo) const
Return the human-readable symbolic target-specific name for the specified physical register.
iterator_range< mc_subreg_iterator > subregs(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, excluding Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Wrapper class representing physical registers. Should be passed by value.
MCSuperRegIterator enumerates all super-registers of Reg.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineInstrBundleIterator< MachineInstr > iterator
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
int64_t getObjectSize(int ObjectIdx) const
Return the size of the specified object.
int getObjectIndexEnd() const
Return one past the maximum frame object index.
int getObjectIndexBegin() const
Return the minimum frame object index.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const MachineFunctionProperties & getProperties() const
Get the function properties.
bool verify(Pass *p=nullptr, const char *Banner=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use.
Representation of each machine instruction.
iterator_range< mop_iterator > operands()
MachineOperand class - Representation of each machine instruction operand.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
void enterBasicBlockEnd(MachineBasicBlock &MBB)
Start tracking liveness from the end of basic block MBB.
bool isRegUsed(Register Reg, bool includeReserved=true) const
Return if a specific register is currently used.
Register FindUnusedReg(const TargetRegisterClass *RC) const
Find an unused register of the specified register class.
Register scavengeRegister(const TargetRegisterClass *RC, MachineBasicBlock::iterator I, int SPAdj, bool AllowSpill=true)
Make a register of the specific register class available and do the appropriate bookkeeping.
void setRegUsed(Register Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Tell the scavenger a register is used.
void backward()
Update internal register state and move MBB iterator backwards.
void enterBasicBlock(MachineBasicBlock &MBB)
Start tracking liveness from the begin of basic block MBB.
Register scavengeRegisterBackwards(const TargetRegisterClass &RC, MachineBasicBlock::iterator To, bool RestoreAfter, int SPAdj, bool AllowSpill=true)
Make a register of the specific register class available from the current position backwards to the p...
BitVector getRegsAvailable(const TargetRegisterClass *RC)
Return all available registers in the register class in Mask.
void forward()
Move the internal MBB iterator and update register states.
Wrapper class representing virtual and physical registers.
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
void push_back(const T &Elt)
Information about stack frame layout on the target.
virtual void determineCalleeSaves(MachineFunction &MF, BitVector &SavedRegs, RegScavenger *RS=nullptr) const
This method determines which of the registers reported by TargetRegisterInfo::getCalleeSavedRegs() sh...
virtual void processFunctionBeforeFrameFinalized(MachineFunction &MF, RegScavenger *RS=nullptr) const
processFunctionBeforeFrameFinalized - This method is called immediately before the specified function...
virtual void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg) const
Load the specified register of the given register class from the specified stack frame index.
virtual void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg) const
Store the specified register of the given register class to the specified stack frame index.
ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF) const
Returns the preferred order for allocating registers from this register class in MF.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Align getSpillAlign(const TargetRegisterClass &RC) const
Return the minimum required alignment in bytes for a spill slot for a register of this class.
virtual bool eliminateFrameIndex(MachineBasicBlock::iterator MI, int SPAdj, unsigned FIOperandNum, RegScavenger *RS=nullptr) const =0
This method must be overriden to eliminate abstract frame indices from instructions which may use the...
virtual bool saveScavengerRegister(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, MachineBasicBlock::iterator &UseMI, const TargetRegisterClass *RC, Register Reg) const
Spill the register so it can be used by the register scavenger.
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 ...
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
BitVector getAllocatableSet(const MachineFunction &MF, const TargetRegisterClass *RC=nullptr) const
Returns a bitset indexed by register number indicating if a register is allocatable or not.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetFrameLowering * getFrameLowering() const
virtual const TargetInstrInfo * getInstrInfo() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
void scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS)
Replaces all frame index virtual registers with physical registers.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
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.
This struct is a compact representation of a valid (non-zero power of two) alignment.
uint64_t value() const
This is a hole in the type system and should not be abused.