52 #define DEBUG_TYPE "regalloc" 54 STATISTIC(NumStores,
"Number of stores added");
55 STATISTIC(NumLoads ,
"Number of loads added");
56 STATISTIC(NumCoalesced,
"Number of copies coalesced");
87 unsigned short LastOpNum = 0;
90 explicit LiveReg(
unsigned VirtReg) : VirtReg(VirtReg) {}
92 unsigned getSparseSetIndex()
const {
100 LiveRegMap LiveVirtRegs;
125 std::vector<unsigned> PhysRegState;
133 RegUnitSet UsedInInstr;
135 void setPhysRegState(
MCPhysReg PhysReg,
unsigned NewState);
138 void markRegUsedInInstr(
MCPhysReg PhysReg) {
140 UsedInInstr.insert(*Units);
144 bool isRegUsedInInstr(
MCPhysReg PhysReg)
const {
146 if (UsedInInstr.count(*Units))
154 spillImpossible = ~0u
158 StringRef getPassName()
const override {
return "Fast Register Allocator"; }
185 void addKillFlag(
const LiveReg &LRI);
186 void killVirtReg(LiveReg &LR);
187 void killVirtReg(
unsigned VirtReg);
194 unsigned calcSpillCost(
MCPhysReg PhysReg)
const;
195 void assignVirtToPhysReg(LiveReg &,
MCPhysReg PhysReg);
197 LiveRegMap::iterator findLiveVirtReg(
unsigned VirtReg) {
201 LiveRegMap::const_iterator findLiveVirtReg(
unsigned VirtReg)
const {
208 LiveReg &reloadVirtReg(
MachineInstr &
MI,
unsigned OpNum,
unsigned VirtReg,
213 int getStackSpaceFor(
unsigned VirtReg);
229 void RegAllocFast::setPhysRegState(
MCPhysReg PhysReg,
unsigned NewState) {
230 PhysRegState[PhysReg] = NewState;
235 int RegAllocFast::getStackSpaceFor(
unsigned VirtReg) {
237 int SS = StackSlotForVirtReg[VirtReg];
249 StackSlotForVirtReg[VirtReg] = FrameIdx;
258 <<
" in " <<
printReg(AssignedReg, TRI));
259 int FI = getStackSpaceFor(VirtReg);
274 LLVM_DEBUG(
dbgs() <<
"Inserting debug info due to spill:\n" << *NewDV);
279 LRIDbgValues.clear();
287 int FI = getStackSpaceFor(VirtReg);
295 bool RegAllocFast::isLastUseOfLocalReg(
const MachineOperand &MO)
const {
298 if (StackSlotForVirtReg[MO.
getReg()] != -1)
309 void RegAllocFast::addKillFlag(
const LiveReg &LR) {
310 if (!LR.LastUse)
return;
312 if (MO.
isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) {
313 if (MO.
getReg() == LR.PhysReg)
328 void RegAllocFast::killVirtReg(LiveReg &LR) {
330 assert(PhysRegState[LR.PhysReg] == LR.VirtReg &&
331 "Broken RegState mapping");
332 setPhysRegState(LR.PhysReg, regFree);
337 void RegAllocFast::killVirtReg(
unsigned VirtReg) {
339 "killVirtReg needs a virtual register");
340 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
341 if (LRI != LiveVirtRegs.end() && LRI->PhysReg)
350 "Spilling a physical register is illegal!");
351 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
352 assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
353 "Spilling unmapped virtual register");
354 spillVirtReg(MI, *LRI);
359 assert(PhysRegState[LR.PhysReg] == LR.VirtReg &&
"Broken RegState mapping");
367 spill(MI, LR.VirtReg, LR.PhysReg, SpillKill);
370 LR.LastUse =
nullptr;
377 if (LiveVirtRegs.empty())
381 for (LiveReg &LR : LiveVirtRegs) {
384 spillVirtReg(MI, LR);
386 LiveVirtRegs.clear();
397 unsigned PhysReg = MO.
getReg();
399 "Bad usePhysReg operand");
401 markRegUsedInInstr(PhysReg);
402 switch (PhysRegState[PhysReg]) {
406 PhysRegState[PhysReg] = regFree;
420 switch (PhysRegState[Alias]) {
435 "Instruction is not using a subregister of a reserved register");
440 setPhysRegState(Alias, regFree);
445 setPhysRegState(Alias, regDisabled);
453 setPhysRegState(PhysReg, regFree);
462 markRegUsedInInstr(PhysReg);
463 switch (
unsigned VirtReg = PhysRegState[PhysReg]) {
467 spillVirtReg(MI, VirtReg);
471 setPhysRegState(PhysReg, NewState);
476 setPhysRegState(PhysReg, NewState);
479 switch (
unsigned VirtReg = PhysRegState[Alias]) {
483 spillVirtReg(MI, VirtReg);
487 setPhysRegState(Alias, regDisabled);
499 unsigned RegAllocFast::calcSpillCost(
MCPhysReg PhysReg)
const {
500 if (isRegUsedInInstr(PhysReg)) {
502 <<
" is already used in instr.\n");
503 return spillImpossible;
505 switch (
unsigned VirtReg = PhysRegState[PhysReg]) {
512 <<
printReg(PhysReg, TRI) <<
" is reserved already.\n");
513 return spillImpossible;
515 LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
516 assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
517 "Missing VirtReg entry");
518 return LRI->Dirty ? spillDirty : spillClean;
527 switch (
unsigned VirtReg = PhysRegState[Alias]) {
534 return spillImpossible;
536 LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
537 assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
538 "Missing VirtReg entry");
539 Cost += LRI->Dirty ? spillDirty : spillClean;
550 void RegAllocFast::assignVirtToPhysReg(LiveReg &LR,
MCPhysReg PhysReg) {
551 unsigned VirtReg = LR.VirtReg;
554 assert(LR.PhysReg == 0 &&
"Already assigned a physreg");
555 assert(PhysReg != 0 &&
"Trying to assign no register");
556 LR.PhysReg = PhysReg;
557 setPhysRegState(PhysReg, VirtReg);
561 void RegAllocFast::allocVirtReg(
MachineInstr &MI, LiveReg &LR,
unsigned Hint) {
562 const unsigned VirtReg = LR.VirtReg;
565 "Can only allocate virtual registers");
575 unsigned Cost = calcSpillCost(Hint);
576 if (Cost < spillDirty) {
578 definePhysReg(MI, Hint, regFree);
579 assignVirtToPhysReg(LR, Hint);
586 for (
MCPhysReg PhysReg : AllocationOrder) {
587 if (PhysRegState[PhysReg] == regFree && !isRegUsedInInstr(PhysReg)) {
588 assignVirtToPhysReg(LR, PhysReg);
594 unsigned BestCost = spillImpossible;
595 for (
MCPhysReg PhysReg : AllocationOrder) {
597 unsigned Cost = calcSpillCost(PhysReg);
598 LLVM_DEBUG(
dbgs() <<
"Cost: " << Cost <<
" BestCost: " << BestCost <<
'\n');
601 assignVirtToPhysReg(LR, PhysReg);
604 if (Cost < BestCost) {
614 MI.
emitError(
"inline assembly requires more registers than available");
616 MI.
emitError(
"ran out of registers during register allocation");
617 definePhysReg(MI, *AllocationOrder.begin(), regFree);
618 assignVirtToPhysReg(LR, *AllocationOrder.begin());
622 definePhysReg(MI, BestReg, regFree);
623 assignVirtToPhysReg(LR, BestReg);
628 unsigned VirtReg,
unsigned Hint) {
630 "Not a virtual register");
631 LiveRegMap::iterator LRI;
633 std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
643 allocVirtReg(MI, *LRI, Hint);
644 }
else if (LRI->LastUse) {
647 if (LRI->LastUse != &MI || LRI->LastUse->
getOperand(LRI->LastOpNum).
isUse())
650 assert(LRI->PhysReg &&
"Register not assigned");
652 LRI->LastOpNum = OpNum;
654 markRegUsedInInstr(LRI->PhysReg);
659 RegAllocFast::LiveReg &RegAllocFast::reloadVirtReg(
MachineInstr &MI,
664 "Not a virtual register");
665 LiveRegMap::iterator LRI;
667 std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
670 allocVirtReg(MI, *LRI, Hint);
671 reload(MI, VirtReg, LRI->PhysReg);
672 }
else if (LRI->Dirty) {
673 if (isLastUseOfLocalReg(MO)) {
697 assert(LRI->PhysReg &&
"Register not assigned");
699 LRI->LastOpNum = OpNum;
700 markRegUsedInInstr(LRI->PhysReg);
738 void RegAllocFast::handleThroughOperands(
MachineInstr &MI,
743 if (!MO.
isReg())
continue;
749 if (ThroughRegs.
insert(Reg).second)
761 markRegUsedInInstr(Reg);
763 if (ThroughRegs.
count(PhysRegState[*AI]))
764 definePhysReg(MI, *AI, regFree);
772 if (!MO.
isReg())
continue;
776 if (!MO.
isTied())
continue;
780 LiveReg &LR = reloadVirtReg(MI,
I, Reg, 0);
782 setPhysReg(MI, MO, PhysReg);
789 LiveReg &LR = reloadVirtReg(MI,
I, Reg, 0);
797 if (!MO.
isReg())
continue;
803 MCPhysReg PhysReg = defineVirtReg(MI,
I, Reg, 0);
815 <<
" as used in instr\n");
816 markRegUsedInInstr(Reg);
820 for (
unsigned PartialDef : PartialDefs)
821 markRegUsedInInstr(PartialDef);
825 void RegAllocFast::dumpState() {
827 if (PhysRegState[
Reg] == regDisabled)
continue;
829 switch(PhysRegState[
Reg]) {
837 LiveRegMap::iterator LRI = findLiveVirtReg(PhysRegState[Reg]);
838 assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
839 "Missing VirtReg entry");
842 assert(LRI->PhysReg == Reg &&
"Bad inverse map");
849 for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
850 e = LiveVirtRegs.end(); i != e; ++i) {
857 assert(PhysRegState[i->PhysReg] == i->VirtReg &&
"Bad inverse map");
862 void RegAllocFast::allocateInstruction(
MachineInstr &MI) {
866 unsigned CopySrcReg = 0;
867 unsigned CopyDstReg = 0;
868 unsigned CopySrcSub = 0;
869 unsigned CopyDstSub = 0;
883 unsigned VirtOpEnd = 0;
884 bool hasTiedOps =
false;
885 bool hasEarlyClobbers =
false;
886 bool hasPartialRedefs =
false;
887 bool hasPhysDefs =
false;
895 if (!MO.
isReg())
continue;
901 hasTiedOps = hasTiedOps ||
905 hasEarlyClobbers =
true;
907 hasPartialRedefs =
true;
915 definePhysReg(MI, Reg,
917 hasEarlyClobbers =
true;
931 if (MI.
isInlineAsm() || hasEarlyClobbers || hasPartialRedefs ||
932 (hasTiedOps && (hasPhysDefs || MCID.
getNumDefs() > 1))) {
933 handleThroughOperands(MI, VirtDead);
938 hasEarlyClobbers =
true;
943 for (
unsigned I = 0;
I != VirtOpEnd; ++
I) {
945 if (!MO.
isReg())
continue;
949 LiveReg &LR = reloadVirtReg(MI,
I, Reg, CopyDstReg);
951 CopySrcReg = (CopySrcReg == Reg || CopySrcReg == PhysReg) ? PhysReg : 0;
952 if (setPhysReg(MI, MO, PhysReg))
960 if (hasEarlyClobbers) {
962 if (!MO.
isReg())
continue;
967 markRegUsedInInstr(Reg);
980 LLVM_DEBUG(
dbgs() <<
" Spilling remaining registers before call.\n");
986 for (
unsigned I = 0;
I != DefOpEnd; ++
I) {
994 definePhysReg(MI, Reg, MO.
isDead() ? regFree : regReserved);
997 MCPhysReg PhysReg = defineVirtReg(MI,
I, Reg, CopySrcReg);
1002 CopyDstReg = (CopyDstReg == Reg || CopyDstReg == PhysReg) ? PhysReg : 0;
1009 for (
unsigned VirtReg : VirtDead)
1010 killVirtReg(VirtReg);
1014 if (CopyDstReg && CopyDstReg == CopySrcReg && CopyDstSub == CopySrcSub) {
1020 void RegAllocFast::handleDebugValue(
MachineInstr &MI) {
1033 LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
1034 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
1035 setPhysReg(MI, MO, LRI->PhysReg);
1037 int SS = StackSlotForVirtReg[
Reg];
1041 LLVM_DEBUG(
dbgs() <<
"Modifying debug info due to spill:" <<
"\t" << MI);
1046 LLVM_DEBUG(
dbgs() <<
"Unable to allocate vreg used by DBG_VALUE");
1052 LiveDbgValueMap[
Reg].push_back(&MI);
1059 PhysRegState.assign(TRI->
getNumRegs(), regDisabled);
1060 assert(LiveVirtRegs.empty() &&
"Mapping not cleared from last block?");
1067 definePhysReg(MII, LI.PhysReg, regReserved);
1075 dbgs() <<
"\n>> " << MI <<
"Regs:";
1082 handleDebugValue(MI);
1086 allocateInstruction(MI);
1090 LLVM_DEBUG(
dbgs() <<
"Spilling live registers at end of block.\n");
1091 spillAll(MBB.getFirstTerminator());
1097 NumCoalesced += Coalesced.size();
1103 LLVM_DEBUG(
dbgs() <<
"********** FAST REGISTER ALLOCATION **********\n" 1104 <<
"********** Function: " << MF.
getName() <<
'\n');
1110 MRI->freezeReservedRegs(MF);
1112 UsedInInstr.clear();
1117 unsigned NumVirtRegs = MRI->getNumVirtRegs();
1118 StackSlotForVirtReg.
resize(NumVirtRegs);
1119 LiveVirtRegs.setUniverse(NumVirtRegs);
1123 allocateBasicBlock(MBB);
1127 MRI->clearVirtRegs();
1129 StackSlotForVirtReg.
clear();
1130 LiveDbgValueMap.
clear();
1135 return new RegAllocFast();
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool contains(unsigned Reg) const
Return true if the specified register is included in this register class.
bool isCall(QueryType Type=AnyInBundle) const
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
void emitError(StringRef Msg) const
Emit an error referring to the source location of this instruction.
bool isAllocatable(unsigned PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
This class represents lattice values for constants.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
void push_back(const T &Elt)
Describe properties that are true of each instruction in the target description file.
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned getSubReg() const
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
void setIsDead(bool Val=true)
reg_nodbg_iterator reg_nodbg_begin(unsigned RegNo) const
iterator_range< mop_iterator > operands()
bool isCopyLike() const
Return true if the instruction behaves like a copy.
void setIsRenamable(bool Val=true)
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
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 isEarlyClobber() const
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
unsigned getSpillAlignment(const TargetRegisterClass &RC) const
Return the minimum required alignment in bytes for a spill slot for a register of this class...
MachineInstr * buildDbgValueForSpill(MachineBasicBlock &BB, MachineBasicBlock::iterator I, const MachineInstr &Orig, int FrameIndex)
Clone a DBG_VALUE whose value has been spilled to FrameIndex.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Retuns the total number of operands.
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
RegisterRegAlloc class - Track the registration of register allocators.
virtual const TargetInstrInfo * getInstrInfo() const
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
TargetInstrInfo - Interface to description of machine instruction set.
bool isSuperRegister(unsigned RegA, unsigned RegB) const
Returns true if RegB is a super-register of RegA.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
MachineInstrBundleIterator< MachineInstr > iterator
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
bool readsVirtualRegister(unsigned Reg) const
Return true if the MachineInstr reads the specified virtual register.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
unsigned getSubReg(unsigned Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo...
MCRegAliasIterator enumerates all registers aliasing Reg.
Represent the analysis usage information of a pass.
void resize(typename StorageT::size_type s)
FunctionPass class - This class is used to implement most global optimizations.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
int CreateSpillStackObject(uint64_t Size, unsigned Alignment)
Create a new statically sized stack object that represents a spill slot, returning a nonnegative iden...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setIsKill(bool Val=true)
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specific constraint if it is set.
unsigned findTiedOperandIdx(unsigned OpIdx) const
Given the index of a tied register operand, find the operand it is tied to.
bool isDebugValue() const
MachineOperand class - Representation of each machine instruction operand.
static RegisterRegAlloc fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator)
void updateDbgValueForSpill(MachineInstr &Orig, int FrameIndex)
Update a DBG_VALUE whose value has been spilled to FrameIndex.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void addRegisterDefined(unsigned Reg, const TargetRegisterInfo *RegInfo=nullptr)
We have determined MI defines a register.
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
virtual void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const
Store the specified register of the given register class to the specified stack frame index...
const MachineBasicBlock * getParent() const
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
TargetSubtargetInfo - Generic base class for all target subtargets.
Representation of each machine instruction.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
SparseSet - Fast set implmentation for objects that can be identified by small unsigned keys...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
void setReg(unsigned Reg)
Change the register this operand corresponds to.
INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false, false) void RegAllocFast
Pair of physical register and lane mask.
void setSubReg(unsigned subReg)
void addPhysRegsUsedFromRegMask(const uint32_t *RegMask)
addPhysRegsUsedFromRegMask - Mark any registers not in RegMask as used.
bool hasOneNonDBGUse(unsigned RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug instruction using the specified regis...
iterator_range< livein_iterator > liveins() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
static reg_nodbg_iterator reg_nodbg_end()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
FunctionPass * createFastRegisterAllocator()
FastRegisterAllocation Pass - This pass register allocates as fast as possible.
use_instr_nodbg_iterator use_instr_nodbg_begin(unsigned RegNo) const
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
bool addRegisterKilled(unsigned IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI kills a register.
StringRef - Represent a constant reference to a string, i.e.
const MachineOperand & getOperand(unsigned i) const
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
virtual void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const
Load the specified register of the given register class from the specified stack frame index...
Properties which a MachineFunction may have at a given point in time.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.