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))
202 [&](
MCPhysReg SR) { return isRegUsed(SR); }) &&
204 [&](
MCPhysReg SR) { return isRegUsed(SR); })) {
214 assert((KillRegs.test(Reg) || isUnused(Reg) ||
215 isLiveInButUnusedBefore(Reg,
MI,
MBB, TRI, MRI)) &&
216 "Re-defining a live register!");
223 setUnused(KillRegUnits);
224 setUsed(DefRegUnits);
228 assert(Tracking &&
"Must be tracking to determine kills and defs");
234 for (ScavengedInfo &
I : Scavenged) {
235 if (
I.Restore == &
MI) {
250 return includeReserved;
278 auto FindFirstCandidate = [&]() ->
int {
280 if (Candidates.
test(Reg))
286 int Survivor = FindFirstCandidate();
287 assert(Survivor > 0 &&
"No candidates for scavenging");
290 assert(StartMI != ME &&
"MI already at terminator");
294 bool inVirtLiveRange =
false;
296 if (
MI->isDebugOrPseudoInstr()) {
300 bool isVirtKillInsn =
false;
301 bool isVirtDefInsn =
false;
306 if (!MO.isReg() || MO.isUndef() || !MO.getReg())
308 if (MO.getReg().isVirtual()) {
310 isVirtDefInsn =
true;
311 else if (MO.isKill())
312 isVirtKillInsn =
true;
316 Candidates.
reset(*AI);
320 if (!inVirtLiveRange) RestorePointMI =
MI;
323 if (isVirtKillInsn) inVirtLiveRange =
false;
324 if (isVirtDefInsn) inVirtLiveRange =
true;
327 if (Candidates.
test(Survivor))
331 if (Candidates.
none())
334 Survivor = FindFirstCandidate();
337 if (
MI == ME) RestorePointMI = ME;
338 assert(RestorePointMI != StartMI &&
339 "No available scavenger restore location!");
342 UseMI = RestorePointMI;
353static std::pair<MCPhysReg, MachineBasicBlock::iterator>
358 bool FoundTo =
false;
367 assert(
From->getParent() == To->getParent() &&
368 "Target instruction is in other than current basic block, use "
369 "enterBasicBlockEnd first");
379 if (!
MRI.isReserved(Reg) && Used.available(Reg) &&
381 return std::make_pair(Reg,
MBB.
end());
391 Used.accumulate(*std::next(
From));
401 if (Survivor == 0 || !Used.available(Survivor)) {
404 if (!
MRI.isReserved(Reg) && Used.available(Reg)) {
409 if (AvilableReg == 0)
411 Survivor = AvilableReg;
413 if (--InstrCountDown == 0)
418 bool FoundVReg =
false;
420 if (MO.isReg() && MO.getReg().isVirtual()) {
433 "iterating backwards");
436 return std::make_pair(Survivor, Pos);
441 while (!
MI.getOperand(i).isFI()) {
443 assert(i <
MI.getNumOperands() &&
"Instr doesn't have FrameIndex operand!");
448RegScavenger::ScavengedInfo &
459 unsigned SI = Scavenged.
size(), Diff = std::numeric_limits<unsigned>::max();
461 for (
unsigned I = 0;
I < Scavenged.
size(); ++
I) {
462 if (Scavenged[
I].Reg != 0)
465 int FI = Scavenged[
I].FrameIndex;
466 if (FI < FIB || FI >= FIE)
470 if (NeedSize > S || NeedAlign >
A)
478 unsigned D = (S - NeedSize) + (
A.value() - NeedAlign.
value());
485 if (SI == Scavenged.
size()) {
492 Scavenged[
SI].Reg =
Reg;
498 int FI = Scavenged[
SI].FrameIndex;
499 if (FI < FIB || FI >= FIE) {
501 TRI->
getName(Reg) +
" from class " +
503 ": Cannot scavenge register without an emergency "
514 II = std::prev(
UseMI);
519 return Scavenged[
SI];
524 int SPAdj,
bool AllowSpill) {
532 if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
533 !MO.getReg().isVirtual())
535 Candidates.
reset(*AI);
542 for (ScavengedInfo &
SI : Scavenged) {
547 " from scavenging candidates since it was already scavenged\n");
549 Candidates.
reset(*AI);
576 for (ScavengedInfo &
SI : Scavenged) {
577 assert(
SI.Reg != SReg &&
"scavenged a previously scavenged register");
581 ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj,
I,
UseMI);
582 Scavenged.Restore = &*std::prev(
UseMI);
592 bool RestoreAfter,
int SPAdj,
600 std::pair<MCPhysReg, MachineBasicBlock::iterator>
P =
606 if (Reg != 0 && SpillBefore ==
MBB.
end()) {
615 assert(Reg != 0 &&
"No register left to scavenge!");
618 RestoreAfter ? std::next(MBBI) : MBBI;
620 if (ReloadBefore !=
MBB.
end())
622 ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
623 Scavenged.Restore = &*std::prev(SpillBefore);
626 <<
" until " << *SpillBefore);
645 if (CommonMBB ==
nullptr)
647 assert(
MBB == CommonMBB &&
"All defs+uses must be in the same basic block");
650 if (!
MI.readsRegister(VReg, &
TRI)) {
651 assert((!RealDef || RealDef == &
MI) &&
652 "Can have at most one definition which is not a redefinition");
657 assert(RealDef !=
nullptr &&
"Must have at least 1 Def");
668 return !MO.getParent()->readsRegister(VReg, &TRI);
671 "Must have one definition that does not redefine vreg");
679 ReserveAfter, SPAdj);
680 MRI.replaceRegWith(VReg, SReg);
694 unsigned InitialNumVirtRegs =
MRI.getNumVirtRegs();
695 bool NextInstructionReadsVReg =
false;
702 if (NextInstructionReadsVReg) {
712 if (!Reg.isVirtual() ||
719 N->addRegisterKilled(SReg, &
TRI,
false);
725 NextInstructionReadsVReg =
false;
732 if (!Reg.isVirtual() ||
738 assert(!MO.isInternalRead() &&
"Cannot assign inside bundles");
739 assert((!MO.isUndef() || MO.isDef()) &&
"Cannot handle undef uses");
741 NextInstructionReadsVReg =
true;
745 I->addRegisterDead(SReg, &
TRI,
false);
751 if (!MO.isReg() || !MO.getReg().isVirtual())
753 assert(!MO.isInternalRead() &&
"Cannot assign inside bundles");
754 assert((!MO.isUndef() || MO.isDef()) &&
"Cannot handle undef uses");
755 assert(!MO.readsReg() &&
"Vreg use in first instruction not allowed");
759 return MRI.getNumVirtRegs() != InitialNumVirtRegs;
768 if (
MRI.getNumVirtRegs() == 0) {
780 LLVM_DEBUG(
dbgs() <<
"Warning: Required two scavenging passes for block "
824char ScavengerTest::ID;
827 "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
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_superreg_iterator > superregs(MCRegister Reg) const
Return an iterator range over all super-registers of Reg, excluding Reg.
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.
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.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
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.