50#define DEBUG_TYPE "regalloc"
54STATISTIC(NumCoalesced,
"Number of copies coalesced");
67class InstrPosIndexes {
69 void unsetInitialized() { IsInitialized =
false; }
73 Instr2PosIndex.
clear();
76 LastIndex += InstrDist;
77 Instr2PosIndex[&
MI] = LastIndex;
92 assert(
MI.getParent() == CurMBB &&
"MI is not in CurMBB");
93 auto It = Instr2PosIndex.find(&
MI);
94 if (It != Instr2PosIndex.end()) {
108 unsigned Distance = 1;
110 End = std::next(Start);
111 while (Start != CurMBB->begin() &&
112 !Instr2PosIndex.count(&*std::prev(Start))) {
116 while (
End != CurMBB->end() && !Instr2PosIndex.count(&*(
End))) {
124 Start == CurMBB->begin() ? 0 : Instr2PosIndex.at(&*std::prev(Start));
126 if (
End == CurMBB->end())
127 Step =
static_cast<uint64_t>(InstrDist);
131 assert(EndIndex > LastIndex &&
"Index must be ascending order");
132 unsigned NumAvailableIndexes = EndIndex - LastIndex - 1;
151 Step = (NumAvailableIndexes + 1) / (Distance + 1);
156 if (
LLVM_UNLIKELY(!Step || (!LastIndex && Step == InstrDist))) {
158 Index = Instr2PosIndex.at(&
MI);
162 for (
auto I = Start;
I !=
End; ++
I) {
164 Instr2PosIndex[&*
I] = LastIndex;
166 Index = Instr2PosIndex.at(&
MI);
171 bool IsInitialized =
false;
172 enum { InstrDist = 1024 };
182 bool ClearVirtRegs_ =
true)
184 StackSlotForVirtReg(-1), ClearVirtRegs(ClearVirtRegs_) {}
207 bool LiveOut =
false;
208 bool Reloaded =
false;
211 explicit LiveReg(
Register VirtReg) : VirtReg(VirtReg) {}
213 unsigned getSparseSetIndex()
const {
221 LiveRegMap LiveVirtRegs;
255 std::vector<unsigned> RegUnitStates;
262 RegUnitSet UsedInInstr;
263 RegUnitSet PhysRegUses;
269 InstrPosIndexes PosIndexes;
271 void setPhysRegState(
MCPhysReg PhysReg,
unsigned NewState);
272 bool isPhysRegFree(
MCPhysReg PhysReg)
const;
275 void markRegUsedInInstr(
MCPhysReg PhysReg) {
277 UsedInInstr.insert(Unit);
281 bool isClobberedByRegMasks(
MCPhysReg PhysReg)
const {
288 bool isRegUsedInInstr(
MCPhysReg PhysReg,
bool LookAtPhysRegUses)
const {
289 if (LookAtPhysRegUses && isClobberedByRegMasks(PhysReg))
292 if (UsedInInstr.count(Unit))
294 if (LookAtPhysRegUses && PhysRegUses.count(Unit))
302 void markPhysRegUsedInInstr(
MCPhysReg PhysReg) {
304 PhysRegUses.insert(Unit);
308 void unmarkRegUsedInInstr(
MCPhysReg PhysReg) {
310 UsedInInstr.erase(Unit);
317 spillImpossible = ~0
u
330 MachineFunctionProperties::Property::NoPHIs);
336 MachineFunctionProperties::Property::NoVRegs);
344 MachineFunctionProperties::Property::IsSSA);
352 void addRegClassDefCounts(std::vector<unsigned> &RegClassDefCounts,
366 unsigned calcSpillCost(
MCPhysReg PhysReg)
const;
378 bool LookAtPhysRegUses =
false);
385 bool LookAtPhysRegUses =
false);
398 bool shouldAllocateRegister(
const Register Reg)
const;
399 int getStackSpaceFor(
Register VirtReg);
401 MCPhysReg AssignedReg,
bool Kill,
bool LiveOut);
408 void dumpState()
const;
413char RegAllocFast::ID = 0;
421 return ShouldAllocateClass(*
TRI, RC);
424void RegAllocFast::setPhysRegState(
MCPhysReg PhysReg,
unsigned NewState) {
426 RegUnitStates[Unit] = NewState;
429bool RegAllocFast::isPhysRegFree(
MCPhysReg PhysReg)
const {
431 if (RegUnitStates[Unit] != regFree)
439int RegAllocFast::getStackSpaceFor(
Register VirtReg) {
441 int SS = StackSlotForVirtReg[VirtReg];
448 unsigned Size =
TRI->getSpillSize(RC);
449 Align Alignment =
TRI->getSpillAlign(RC);
453 StackSlotForVirtReg[VirtReg] = FrameIdx;
460 PosIndexes.getIndex(
A, IndexA);
462 PosIndexes.getIndex(
A, IndexA);
463 return IndexA < IndexB;
467bool RegAllocFast::mayLiveOut(
Register VirtReg) {
480 if (DefInst.getParent() !=
MBB) {
484 if (!SelfLoopDef ||
dominates(PosIndexes, DefInst, *SelfLoopDef))
485 SelfLoopDef = &DefInst;
496 static const unsigned Limit = 8;
498 for (
const MachineInstr &UseInst :
MRI->use_nodbg_instructions(VirtReg)) {
499 if (UseInst.getParent() !=
MBB || ++
C >= Limit) {
508 if (SelfLoopDef == &UseInst ||
509 !
dominates(PosIndexes, *SelfLoopDef, UseInst)) {
520bool RegAllocFast::mayLiveIn(
Register VirtReg) {
525 static const unsigned Limit = 8;
528 if (DefInst.getParent() !=
MBB || ++
C >= Limit) {
540 MCPhysReg AssignedReg,
bool Kill,
bool LiveOut) {
543 int FI = getStackSpaceFor(VirtReg);
560 SpilledOperandsMap[MO->getParent()].push_back(MO);
561 for (
auto MISpilledOperands : SpilledOperandsMap) {
567 *
MBB,
Before, *MISpilledOperands.first, FI, MISpilledOperands.second);
570 LLVM_DEBUG(
dbgs() <<
"Inserting debug info due to spill:\n" << *NewDV);
579 LLVM_DEBUG(
dbgs() <<
"Cloning debug info due to live out spill\n");
595 LRIDbgOperands.clear();
603 int FI = getStackSpaceFor(VirtReg);
623 if (!
TII->isBasicBlockPrologue(*
I))
641 if (LiveVirtRegs.empty())
648 setPhysRegState(Reg, regLiveIn);
656 getMBBBeginInsertionPoint(
MBB, PrologLiveIns);
657 for (
const LiveReg &LR : LiveVirtRegs) {
663 if (RegUnitStates[FirstUnit] == regLiveIn)
667 "no reload in start block. Missing vreg def?");
669 if (PrologLiveIns.
count(PhysReg)) {
673 reload(
MBB.
begin(), LR.VirtReg, PhysReg);
675 reload(InsertBefore, LR.VirtReg, PhysReg);
677 LiveVirtRegs.clear();
685 bool displacedAny = displacePhysReg(
MI, Reg);
686 setPhysRegState(Reg, regPreAssigned);
687 markRegUsedInInstr(Reg);
692 bool displacedAny = displacePhysReg(
MI, Reg);
693 setPhysRegState(Reg, regPreAssigned);
701 bool displacedAny =
false;
704 switch (
unsigned VirtReg = RegUnitStates[Unit]) {
706 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
707 assert(LRI != LiveVirtRegs.end() &&
"datastructures in sync");
710 reload(ReloadBefore, VirtReg, LRI->PhysReg);
712 setPhysRegState(LRI->PhysReg, regFree);
714 LRI->Reloaded =
true;
719 RegUnitStates[Unit] = regFree;
729void RegAllocFast::freePhysReg(
MCPhysReg PhysReg) {
733 switch (
unsigned VirtReg = RegUnitStates[FirstUnit]) {
739 setPhysRegState(PhysReg, regFree);
742 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
743 assert(LRI != LiveVirtRegs.end());
745 setPhysRegState(LRI->PhysReg, regFree);
756unsigned RegAllocFast::calcSpillCost(
MCPhysReg PhysReg)
const {
758 switch (
unsigned VirtReg = RegUnitStates[Unit]) {
764 return spillImpossible;
766 bool SureSpill = StackSlotForVirtReg[VirtReg] != -1 ||
767 findLiveVirtReg(VirtReg)->LiveOut;
768 return SureSpill ? spillClean : spillDirty;
775void RegAllocFast::assignDanglingDebugValues(
MachineInstr &Definition,
777 auto UDBGValIter = DanglingDbgValues.
find(VirtReg);
778 if (UDBGValIter == DanglingDbgValues.
end())
784 if (!
DbgValue->hasDebugOperandForReg(VirtReg))
793 if (
I->modifiesRegister(Reg,
TRI) || --Limit == 0) {
812void RegAllocFast::assignVirtToPhysReg(
MachineInstr &AtMI, LiveReg &LR,
817 assert(LR.PhysReg == 0 &&
"Already assigned a physreg");
818 assert(PhysReg != 0 &&
"Trying to assign no register");
819 LR.PhysReg = PhysReg;
820 setPhysRegState(PhysReg, VirtReg);
822 assignDanglingDebugValues(AtMI, VirtReg, PhysReg);
828 static const unsigned ChainLengthLimit = 3;
831 if (
Reg.isPhysical())
839 }
while (++
C <= ChainLengthLimit);
847 static const unsigned DefLimit = 3;
852 Reg = traceCopyChain(Reg);
865 bool LookAtPhysRegUses) {
866 const Register VirtReg = LR.VirtReg;
871 <<
" in class " <<
TRI->getRegClassName(&RC)
876 !isRegUsedInInstr(Hint0, LookAtPhysRegUses)) {
878 if (isPhysRegFree(Hint0)) {
881 assignVirtToPhysReg(
MI, LR, Hint0);
892 Register Hint1 = traceCopies(VirtReg);
894 !isRegUsedInInstr(Hint1, LookAtPhysRegUses)) {
896 if (isPhysRegFree(Hint1)) {
899 assignVirtToPhysReg(
MI, LR, Hint1);
910 unsigned BestCost = spillImpossible;
914 if (isRegUsedInInstr(PhysReg, LookAtPhysRegUses)) {
919 unsigned Cost = calcSpillCost(PhysReg);
923 assignVirtToPhysReg(
MI, LR, PhysReg);
927 if (PhysReg == Hint0 || PhysReg == Hint1)
928 Cost -= spillPrefBonus;
930 if (
Cost < BestCost) {
939 if (
MI.isInlineAsm())
940 MI.emitError(
"inline assembly requires more registers than available");
942 MI.emitError(
"ran out of registers during register allocation");
949 displacePhysReg(
MI, BestReg);
950 assignVirtToPhysReg(
MI, LR, BestReg);
957 if (!shouldAllocateRegister(VirtReg))
960 LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
962 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
963 PhysReg = LRI->PhysReg;
972 if (SubRegIdx != 0) {
973 PhysReg =
TRI->getSubReg(PhysReg, SubRegIdx);
983bool RegAllocFast::defineLiveThroughVirtReg(
MachineInstr &
MI,
unsigned OpNum,
985 if (!shouldAllocateRegister(VirtReg))
987 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
988 if (LRI != LiveVirtRegs.end()) {
990 if (PrevReg != 0 && isRegUsedInInstr(PrevReg,
true)) {
992 <<
" (tied/earlyclobber resolution)\n");
993 freePhysReg(PrevReg);
995 allocVirtReg(
MI, *LRI, 0,
true);
1001 TII->get(TargetOpcode::COPY), PrevReg)
1009 return defineVirtReg(
MI, OpNum, VirtReg,
true);
1019bool RegAllocFast::defineVirtReg(
MachineInstr &
MI,
unsigned OpNum,
1020 Register VirtReg,
bool LookAtPhysRegUses) {
1022 if (!shouldAllocateRegister(VirtReg))
1025 LiveRegMap::iterator LRI;
1027 std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
1030 if (mayLiveOut(VirtReg)) {
1031 LRI->LiveOut =
true;
1038 if (LRI->PhysReg == 0) {
1039 allocVirtReg(
MI, *LRI, 0, LookAtPhysRegUses);
1050 assert(!isRegUsedInInstr(LRI->PhysReg, LookAtPhysRegUses) &&
1051 "TODO: preassign mismatch");
1053 <<
" use existing assignment to "
1058 if (LRI->Reloaded || LRI->LiveOut) {
1059 if (!
MI.isImplicitDef()) {
1063 <<
" RL: " << LRI->Reloaded <<
'\n');
1064 bool Kill = LRI->LastUse ==
nullptr;
1065 spill(SpillBefore, VirtReg, PhysReg, Kill, LRI->LiveOut);
1069 if (
MI.getOpcode() == TargetOpcode::INLINEASM_BR) {
1070 int FI = StackSlotForVirtReg[VirtReg];
1083 LRI->LastUse =
nullptr;
1085 LRI->LiveOut =
false;
1086 LRI->Reloaded =
false;
1088 if (
MI.getOpcode() == TargetOpcode::BUNDLE) {
1089 BundleVirtRegsMap[VirtReg] = PhysReg;
1091 markRegUsedInInstr(PhysReg);
1092 return setPhysReg(
MI, MO, PhysReg);
1100 if (!shouldAllocateRegister(VirtReg))
1102 LiveRegMap::iterator LRI;
1104 std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
1107 if (mayLiveOut(VirtReg)) {
1108 LRI->LiveOut =
true;
1115 assert((!MO.
isKill() || LRI->LastUse == &
MI) &&
"Invalid kill flag");
1119 if (LRI->PhysReg == 0) {
1122 if (
MI.isCopy() &&
MI.getOperand(1).getSubReg() == 0) {
1123 Hint =
MI.getOperand(0).getReg();
1125 assert(!shouldAllocateRegister(Hint));
1129 "Copy destination should already be assigned");
1132 allocVirtReg(
MI, *LRI, Hint,
false);
1144 if (
MI.getOpcode() == TargetOpcode::BUNDLE) {
1145 BundleVirtRegsMap[VirtReg] = LRI->PhysReg;
1147 markRegUsedInInstr(LRI->PhysReg);
1148 return setPhysReg(
MI, MO, LRI->PhysReg);
1173 MI.addRegisterKilled(PhysReg,
TRI,
true);
1182 MI.addRegisterDead(PhysReg,
TRI,
true);
1184 MI.addRegisterDefined(PhysReg,
TRI);
1193void RegAllocFast::dumpState()
const {
1194 for (
unsigned Unit = 1, UnitE =
TRI->getNumRegUnits(); Unit != UnitE;
1196 switch (
unsigned VirtReg = RegUnitStates[Unit]) {
1199 case regPreAssigned:
1206 LiveRegMap::const_iterator
I = findLiveVirtReg(VirtReg);
1207 assert(
I != LiveVirtRegs.end() &&
"have LiveVirtRegs entry");
1208 if (
I->LiveOut ||
I->Reloaded) {
1216 assert(
TRI->hasRegUnit(
I->PhysReg, Unit) &&
"inverse mapping present");
1223 for (
const LiveReg &LR : LiveVirtRegs) {
1230 assert(RegUnitStates[Unit] == VirtReg &&
"inverse map valid");
1238void RegAllocFast::addRegClassDefCounts(
1239 std::vector<unsigned> &RegClassDefCounts,
Register Reg)
const {
1240 assert(RegClassDefCounts.size() ==
TRI->getNumRegClasses());
1242 if (
Reg.isVirtual()) {
1243 if (!shouldAllocateRegister(Reg))
1246 for (
unsigned RCIdx = 0, RCIdxEnd =
TRI->getNumRegClasses();
1247 RCIdx != RCIdxEnd; ++RCIdx) {
1251 ++RegClassDefCounts[RCIdx];
1257 for (
unsigned RCIdx = 0, RCIdxEnd =
TRI->getNumRegClasses();
1258 RCIdx != RCIdxEnd; ++RCIdx) {
1262 ++RegClassDefCounts[RCIdx];
1272void RegAllocFast::findAndSortDefOperandIndexes(
const MachineInstr &
MI) {
1273 DefOperandIndexes.
clear();
1276 std::vector<unsigned> RegClassDefCounts(
TRI->getNumRegClasses(), 0);
1277 assert(RegClassDefCounts[0] == 0);
1280 for (
unsigned I = 0, E =
MI.getNumOperands();
I < E; ++
I) {
1286 if (
Reg.isPhysical()) {
1288 markPhysRegUsedInInstr(Reg);
1293 if (
Reg.isVirtual() && shouldAllocateRegister(Reg))
1296 addRegClassDefCounts(RegClassDefCounts, Reg);
1310 unsigned ClassSize0 = RegClassInfo.
getOrder(&RC0).
size();
1311 unsigned ClassSize1 = RegClassInfo.
getOrder(&RC1).
size();
1313 bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.
getID()];
1314 bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.
getID()];
1315 if (SmallClass0 > SmallClass1)
1317 if (SmallClass0 < SmallClass1)
1325 if (Livethrough0 > Livethrough1)
1327 if (Livethrough0 < Livethrough1)
1341 unsigned TiedIdx =
MI.findTiedOperandIdx(
MI.getOperandNo(&MO));
1359 UsedInInstr.clear();
1361 BundleVirtRegsMap.
clear();
1364 bool HasPhysRegUse =
false;
1365 bool HasRegMask =
false;
1366 bool HasVRegDef =
false;
1367 bool HasDef =
false;
1368 bool HasEarlyClobber =
false;
1369 bool NeedToAssignLiveThroughs =
false;
1373 if (
Reg.isVirtual()) {
1374 if (!shouldAllocateRegister(Reg))
1380 HasEarlyClobber =
true;
1381 NeedToAssignLiveThroughs =
true;
1384 NeedToAssignLiveThroughs =
true;
1386 }
else if (
Reg.isPhysical()) {
1387 if (!
MRI->isReserved(Reg)) {
1390 bool displacedAny = definePhysReg(
MI, Reg);
1392 HasEarlyClobber =
true;
1397 HasPhysRegUse =
true;
1411 bool ReArrangedImplicitOps =
true;
1419 if (NeedToAssignLiveThroughs) {
1420 PhysRegUses.clear();
1422 while (ReArrangedImplicitOps) {
1423 ReArrangedImplicitOps =
false;
1424 findAndSortDefOperandIndexes(
MI);
1425 for (
uint16_t OpIdx : DefOperandIndexes) {
1431 ReArrangedImplicitOps = defineLiveThroughVirtReg(
MI, OpIdx, Reg);
1433 ReArrangedImplicitOps = defineVirtReg(
MI, OpIdx, Reg);
1437 if (ReArrangedImplicitOps)
1443 while (ReArrangedImplicitOps) {
1444 ReArrangedImplicitOps =
false;
1449 if (
Reg.isVirtual()) {
1450 ReArrangedImplicitOps =
1451 defineVirtReg(
MI,
MI.getOperandNo(&MO), Reg);
1452 if (ReArrangedImplicitOps)
1477 "tied def assigned to clobbered register");
1484 if (
Reg.isVirtual()) {
1485 assert(!shouldAllocateRegister(Reg));
1489 if (
MRI->isReserved(Reg))
1492 unmarkRegUsedInInstr(Reg);
1500 for (
const auto *RM : RegMasks)
1501 MRI->addPhysRegsUsedFromRegMask(RM);
1504 for (
const LiveReg &LR : LiveVirtRegs) {
1506 if (PhysReg != 0 && isClobberedByRegMasks(PhysReg))
1507 displacePhysReg(
MI, PhysReg);
1512 if (HasPhysRegUse) {
1517 if (!
Reg.isPhysical())
1519 if (
MRI->isReserved(Reg))
1521 if (!usePhysReg(
MI, Reg))
1529 bool HasUndefUse =
false;
1530 bool ReArrangedImplicitMOs =
true;
1531 while (ReArrangedImplicitMOs) {
1532 ReArrangedImplicitMOs =
false;
1537 if (!
Reg.isVirtual() || !shouldAllocateRegister(Reg))
1551 ReArrangedImplicitMOs = useVirtReg(
MI, MO, Reg);
1552 if (ReArrangedImplicitMOs)
1563 if (!
Reg.isVirtual() || !shouldAllocateRegister(Reg))
1566 assert(MO.
isUndef() &&
"Should only have undef virtreg uses left");
1567 allocVirtRegUndef(MO);
1572 if (HasEarlyClobber) {
1576 assert(!MO.
getSubReg() &&
"should be already handled in def processing");
1581 if (
Reg.isVirtual()) {
1582 assert(!shouldAllocateRegister(Reg));
1585 assert(
Reg.isPhysical() &&
"should have register assigned");
1593 if (
MI.readsRegister(Reg,
TRI))
1601 if (
MI.isCopy() &&
MI.getOperand(0).getReg() ==
MI.getOperand(1).getReg() &&
1602 MI.getNumOperands() == 2) {
1611 assert(
MI.isDebugValue() &&
"not a DBG_VALUE*");
1612 for (
const auto &MO :
MI.debug_operands()) {
1616 if (!
Reg.isVirtual())
1618 if (!shouldAllocateRegister(Reg))
1622 int SS = StackSlotForVirtReg[
Reg];
1632 LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
1637 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
1639 for (
auto &RegMO : DbgOps)
1640 setPhysReg(
MI, *RegMO, LRI->PhysReg);
1642 DanglingDbgValues[
Reg].push_back(&
MI);
1647 LiveDbgValueMap[
Reg].append(DbgOps.
begin(), DbgOps.
end());
1654 while (BundledMI->isBundledWithPred()) {
1660 if (!
Reg.isVirtual() || !shouldAllocateRegister(Reg))
1664 DI = BundleVirtRegsMap.
find(Reg);
1665 assert(DI != BundleVirtRegsMap.
end() &&
"Unassigned virtual register");
1667 setPhysReg(
MI, MO, DI->second);
1678 PosIndexes.unsetInitialized();
1679 RegUnitStates.assign(
TRI->getNumRegUnits(), regFree);
1680 assert(LiveVirtRegs.empty() &&
"Mapping not cleared from last block?");
1683 setPhysRegState(LiveReg.PhysReg, regPreAssigned);
1693 if (
MI.isDebugValue()) {
1694 handleDebugValue(
MI);
1698 allocateInstruction(
MI);
1702 if (
MI.getOpcode() == TargetOpcode::BUNDLE) {
1710 LLVM_DEBUG(
dbgs() <<
"Loading live registers at begin of block.\n");
1717 NumCoalesced += Coalesced.size();
1719 for (
auto &UDBGPair : DanglingDbgValues) {
1723 if (!
DbgValue->hasDebugOperandForReg(UDBGPair.first))
1730 DanglingDbgValues.clear();
1736 LLVM_DEBUG(
dbgs() <<
"********** FAST REGISTER ALLOCATION **********\n"
1737 <<
"********** Function: " << MF.
getName() <<
'\n');
1743 MRI->freezeReservedRegs();
1745 unsigned NumRegUnits =
TRI->getNumRegUnits();
1746 UsedInInstr.clear();
1747 UsedInInstr.setUniverse(NumRegUnits);
1748 PhysRegUses.clear();
1749 PhysRegUses.setUniverse(NumRegUnits);
1753 unsigned NumVirtRegs =
MRI->getNumVirtRegs();
1754 StackSlotForVirtReg.
resize(NumVirtRegs);
1755 LiveVirtRegs.setUniverse(NumVirtRegs);
1756 MayLiveAcrossBlocks.
clear();
1757 MayLiveAcrossBlocks.
resize(NumVirtRegs);
1761 allocateBasicBlock(
MBB);
1763 if (ClearVirtRegs) {
1766 MRI->clearVirtRegs();
1769 StackSlotForVirtReg.
clear();
1770 LiveDbgValueMap.
clear();
1777 bool ClearVirtRegs) {
1778 return new RegAllocFast(Ftor, ClearVirtRegs);
unsigned const MachineRegisterInfo * MRI
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_UNLIKELY(EXPR)
This file defines the DenseMap class.
const HexagonInstrInfo * TII
This file implements an indexed map.
unsigned const TargetRegisterInfo * TRI
This file implements a map that provides insertion order iteration.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
static bool isCoalescable(const MachineInstr &MI)
static cl::opt< bool > IgnoreMissingDefs("rafast-ignore-missing-defs", cl::Hidden)
static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)
static bool isTiedToNotUndef(const MachineOperand &MO)
static RegisterRegAlloc fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the SparseSet class derived from the version described in Briggs,...
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Class recording the (high level) value of a variable.
Represent the analysis usage information of a pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
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 clear()
clear - Removes all bits from the bitvector.
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
Lightweight error class with error context and mandatory checking.
FunctionPass class - This class is used to implement most global optimizations.
void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, Register SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg) const override
Store the specified register of the given register class to the specified stack frame index.
void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, Register DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg) const override
Load the specified register of the given register class from the specified stack frame index.
void resize(typename StorageT::size_type s)
MCRegAliasIterator enumerates all registers aliasing Reg.
Wrapper class representing physical registers. Should be passed by value.
static constexpr unsigned NoRegister
iterator_range< liveout_iterator > liveouts() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
iterator_range< livein_iterator > liveins() const
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Instructions::iterator instr_iterator
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
int CreateSpillStackObject(uint64_t Size, Align Alignment)
Create a new statically sized stack object that represents a spill slot, returning a nonnegative iden...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual MachineFunctionProperties getClearedProperties() const
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual MachineFunctionProperties getSetProperties() const
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
const MachineBasicBlock & front() const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
bool isDebugValueList() const
const MachineBasicBlock * getParent() const
bool isNonListDebugValue() const
MachineOperand & getDebugOperand(unsigned Index)
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
void setSubReg(unsigned subReg)
unsigned getSubReg() const
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
void setIsRenamable(bool Val=true)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
MachineBasicBlock * getMBB() const
void setIsDead(bool Val=true)
void setReg(Register Reg)
Change the register this operand corresponds to.
void setIsKill(bool Val=true)
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
bool isInternalRead() const
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
bool isMBB() const
isMBB - Tests if this is a MO_MachineBasicBlock operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
Wrapper class representing virtual and physical registers.
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
static constexpr bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
typename DenseT::iterator iterator
typename DenseT::const_iterator const_iterator
StringRef - Represent a constant reference to a string, i.e.
TargetInstrInfo - Interface to description of machine instruction set.
unsigned getID() const
Return the register class ID number.
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
bool hasSubClassEq(const TargetRegisterClass *RC) const
Returns true if RC is a sub-class of or equal to this class.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
self_iterator getIterator()
#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.
@ C
The default llvm calling convention, compatible with C.
@ Kill
The last use of a register.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
FunctionPass * createFastRegisterAllocator()
FastRegisterAllocation Pass - This pass register allocates as fast as possible.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
void updateDbgValueForSpill(MachineInstr &Orig, int FrameIndex, Register Reg)
Update a DBG_VALUE whose value has been spilled to FrameIndex.
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
static bool allocateAllRegClasses(const TargetRegisterInfo &, const TargetRegisterClass &)
Default register class filter function for register allocation.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
MachineInstr * buildDbgValueForSpill(MachineBasicBlock &BB, MachineBasicBlock::iterator I, const MachineInstr &Orig, int FrameIndex, Register SpillReg)
Clone a DBG_VALUE whose value has been spilled to FrameIndex.
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.
std::function< bool(const TargetRegisterInfo &TRI, const TargetRegisterClass &RC)> RegClassFilterFunc
This struct is a compact representation of a valid (non-zero power of two) alignment.
Pair of physical register and lane mask.
A MapVector that performs no allocations if smaller than a certain size.