79#define DEBUG_TYPE "regalloc"
81STATISTIC(NumGlobalSplits,
"Number of split global live ranges");
82STATISTIC(NumLocalSplits,
"Number of split local live ranges");
83STATISTIC(NumEvicted,
"Number of interferences evicted");
87 cl::desc(
"Spill mode for splitting live ranges"),
95 cl::desc(
"Last chance recoloring max depth"),
100 cl::desc(
"Last chance recoloring maximum number of considered"
101 " interference at a time"),
106 cl::desc(
"Exhaustive Search for registers bypassing the depth "
107 "and interference cutoffs of last chance recoloring"),
112 cl::desc(
"Instead of spilling a variable right away, defer the actual "
113 "code insertion to the end of the allocation. That way the "
114 "allocator might still find a suitable coloring for this "
115 "variable because of other evicted variables."),
121 cl::desc(
"Cost for first time use of callee-saved register."),
125 "grow-region-complexity-budget",
126 cl::desc(
"growRegion() does not scale with the number of BB edges, so "
127 "limit its budget and bail out once we reach the limit."),
131 "greedy-regclass-priority-trumps-globalness",
132 cl::desc(
"Change the greedy register allocator's live range priority "
133 "calculation to make the AllocationPriority of the register class "
134 "more important then whether the range is global"),
138 "greedy-reverse-local-assignment",
139 cl::desc(
"Reverse allocation order of local live ranges, such that "
140 "shorter local live ranges will tend to be allocated first"),
144 "split-threshold-for-reg-with-hint",
145 cl::desc(
"The threshold for splitting a virtual register with a hint, in "
156 "Greedy Register Allocator",
false,
false)
176const char *
const RAGreedy::StageName[] = {
236bool RAGreedy::LRE_CanEraseVirtReg(
Register VirtReg) {
251void RAGreedy::LRE_WillShrinkVirtReg(
Register VirtReg) {
262 ExtraInfo->LRE_DidCloneVirtReg(New, Old);
267 if (!Info.inBounds(Old))
276 Info[New] = Info[Old];
280 SpillerInstance.reset();
286void RAGreedy::enqueue(PQueue &CurQueue,
const LiveInterval *LI) {
290 assert(Reg.isVirtual() &&
"Can only enqueue virtual registers");
292 auto Stage = ExtraInfo->getOrInitStage(Reg);
295 ExtraInfo->setStage(Reg, Stage);
298 unsigned Ret = PriorityAdvisor->getPriority(*LI);
302 CurQueue.push(std::make_pair(Ret, ~Reg));
305unsigned DefaultPriorityAdvisor::getPriority(
const LiveInterval &LI)
const {
320 static unsigned MemOp = 0;
327 (!ReverseLocalAssignment &&
330 unsigned GlobalBit = 0;
337 if (!ReverseLocalAssignment)
365 Prio = std::min(Prio, (
unsigned)
maxUIntN(24));
368 if (RegClassPriorityTrumpsGlobalness)
387 if (CurQueue.empty())
404 for (
auto I = Order.
begin(), E = Order.
end();
I != E && !PhysReg; ++
I) {
425 if (EvictAdvisor->canEvictHintInterference(VirtReg, PhysHint,
427 evictInterference(VirtReg, PhysHint, NewVRegs);
432 if (trySplitAroundHintReg(PhysHint, VirtReg, NewVRegs, Order))
437 SetOfBrokenHints.insert(&VirtReg);
441 uint8_t
Cost = RegCosts[PhysReg];
448 << (
unsigned)
Cost <<
'\n');
449 MCRegister CheapReg = tryEvict(VirtReg, Order, NewVRegs,
Cost, FixedRegisters);
450 return CheapReg ? CheapReg : PhysReg;
459 auto HasRegUnitInterference = [&](
MCRegUnit Unit) {
483void RAGreedy::evictInterference(
const LiveInterval &VirtReg,
489 unsigned Cascade = ExtraInfo->getOrAssignNewCascade(VirtReg.
reg());
492 <<
" interference: Cascade " << Cascade <<
'\n');
513 assert((ExtraInfo->getCascade(Intf->reg()) < Cascade ||
515 "Cannot decrease cascade number, illegal eviction");
516 ExtraInfo->setCascade(Intf->reg(), Cascade);
532std::optional<unsigned>
535 unsigned CostPerUseLimit)
const {
536 unsigned OrderLimit = Order.
getOrder().size();
538 if (CostPerUseLimit < uint8_t(~0u)) {
542 if (MinCost >= CostPerUseLimit) {
544 << MinCost <<
", no cheaper registers to be found.\n");
550 if (RegCosts[Order.
getOrder().back()] >= CostPerUseLimit) {
561 if (RegCosts[PhysReg] >= CostPerUseLimit)
565 if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {
582 uint8_t CostPerUseLimit,
587 MCRegister BestPhys = EvictAdvisor->tryFindEvictionCandidate(
588 VirtReg, Order, CostPerUseLimit, FixedRegisters);
590 evictInterference(VirtReg, BestPhys, NewVRegs);
608 SplitConstraints.resize(UseBlocks.
size());
610 for (
unsigned I = 0;
I != UseBlocks.
size(); ++
I) {
645 SA->getFirstSplitPoint(BC.
Number)))
651 if (Intf.
last() >= SA->getLastSplitPoint(BC.
Number)) {
678 const unsigned GroupSize = 8;
680 unsigned TBS[GroupSize];
681 unsigned B = 0,
T = 0;
687 assert(
T < GroupSize &&
"Array overflow");
689 if (++
T == GroupSize) {
696 assert(
B < GroupSize &&
"Array overflow");
702 if (FirstNonDebugInstr !=
MBB->
end() &&
704 SA->getFirstSplitPoint(
Number)))
713 if (Intf.
last() >= SA->getLastSplitPoint(
Number))
718 if (++
B == GroupSize) {
729bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
733 unsigned AddedTo = 0;
735 unsigned Visited = 0;
742 for (
unsigned Bundle : NewBundles) {
746 if (
Blocks.size() >= Budget)
761 if (ActiveBlocks.
size() == AddedTo)
768 if (!addThroughConstraints(Cand.Intf, NewBlocks))
776 bool PrefSpill =
true;
777 if (SA->looksLikeLoopIV() && NewBlocks.size() >= 2) {
783 if (L &&
L->getHeader()->getNumber() == (
int)NewBlocks[0] &&
784 all_of(NewBlocks.drop_front(), [&](
unsigned Block) {
785 return L == Loops->getLoopFor(MF->getBlockNumbered(Block));
792 AddedTo = ActiveBlocks.
size();
808bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
810 if (!SA->getNumThroughBlocks())
820 SpillPlacer->
prepare(Cand.LiveBundles);
824 if (!addSplitConstraints(Cand.Intf,
Cost)) {
829 if (!growRegion(Cand)) {
836 if (!Cand.LiveBundles.any()) {
842 for (
int I : Cand.LiveBundles.set_bits())
843 dbgs() <<
" EB#" <<
I;
870BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
873 const BitVector &LiveBundles = Cand.LiveBundles;
875 for (
unsigned I = 0;
I != UseBlocks.
size(); ++
I) {
882 Cand.Intf.moveToBlock(BC.
Number);
892 for (
unsigned Number : Cand.ActiveBlocks) {
895 if (!RegIn && !RegOut)
897 if (RegIn && RegOut) {
899 Cand.Intf.moveToBlock(
Number);
900 if (Cand.Intf.hasInterference()) {
928 const unsigned NumGlobalIntvs = LREdit.
size();
931 assert(NumGlobalIntvs &&
"No global intervals configured");
943 unsigned IntvIn = 0, IntvOut = 0;
947 if (CandIn != NoCand) {
948 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
949 IntvIn = Cand.IntvIdx;
950 Cand.Intf.moveToBlock(
Number);
951 IntfIn = Cand.Intf.first();
956 if (CandOut != NoCand) {
957 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
958 IntvOut = Cand.IntvIdx;
959 Cand.Intf.moveToBlock(
Number);
960 IntfOut = Cand.Intf.last();
965 if (!IntvIn && !IntvOut) {
967 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
968 SE->splitSingleBlock(BI);
972 if (IntvIn && IntvOut)
973 SE->splitLiveThroughBlock(
Number, IntvIn, IntfIn, IntvOut, IntfOut);
975 SE->splitRegInBlock(BI, IntvIn, IntfIn);
977 SE->splitRegOutBlock(BI, IntvOut, IntfOut);
984 for (
unsigned UsedCand : UsedCands) {
991 unsigned IntvIn = 0, IntvOut = 0;
995 if (CandIn != NoCand) {
996 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
997 IntvIn = Cand.IntvIdx;
998 Cand.Intf.moveToBlock(
Number);
999 IntfIn = Cand.Intf.first();
1003 if (CandOut != NoCand) {
1004 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1005 IntvOut = Cand.IntvIdx;
1006 Cand.Intf.moveToBlock(
Number);
1007 IntfOut = Cand.Intf.last();
1009 if (!IntvIn && !IntvOut)
1011 SE->splitLiveThroughBlock(
Number, IntvIn, IntfIn, IntvOut, IntfOut);
1018 SE->finish(&IntvMap);
1021 unsigned OrigBlocks = SA->getNumLiveBlocks();
1028 for (
unsigned I = 0, E = LREdit.
size();
I != E; ++
I) {
1032 if (ExtraInfo->getOrInitStage(
Reg.reg()) !=
RS_New)
1037 if (IntvMap[
I] == 0) {
1038 ExtraInfo->setStage(Reg,
RS_Spill);
1044 if (IntvMap[
I] < NumGlobalIntvs) {
1045 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1046 LLVM_DEBUG(
dbgs() <<
"Main interval covers the same " << OrigBlocks
1047 <<
" blocks as original.\n");
1059 MF->
verify(
this,
"After splitting live range around region");
1067 unsigned NumCands = 0;
1072 bool HasCompact = calcCompactRegion(GlobalCand.
front());
1080 BestCost = SpillCost;
1085 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
1089 if (!HasCompact && BestCand == NoCand)
1092 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1096RAGreedy::calculateRegionSplitCostAroundReg(
MCPhysReg PhysReg,
1100 unsigned &BestCand) {
1104 unsigned WorstCount = ~0
u;
1106 for (
unsigned CandIndex = 0; CandIndex != NumCands; ++CandIndex) {
1107 if (CandIndex == BestCand || !GlobalCand[CandIndex].PhysReg)
1109 unsigned Count = GlobalCand[CandIndex].LiveBundles.count();
1110 if (Count < WorstCount) {
1116 GlobalCand[Worst] = GlobalCand[NumCands];
1117 if (BestCand == NumCands)
1121 if (GlobalCand.
size() <= NumCands)
1122 GlobalCand.
resize(NumCands+1);
1123 GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1124 Cand.reset(IntfCache, PhysReg);
1126 SpillPlacer->
prepare(Cand.LiveBundles);
1128 if (!addSplitConstraints(Cand.Intf,
Cost)) {
1134 if (
Cost >= BestCost) {
1136 if (BestCand == NoCand)
1137 dbgs() <<
" worse than no bundles\n";
1139 dbgs() <<
" worse than "
1140 <<
printReg(GlobalCand[BestCand].PhysReg,
TRI) <<
'\n';
1144 if (!growRegion(Cand)) {
1152 if (!Cand.LiveBundles.any()) {
1157 Cost += calcGlobalSplitCost(Cand, Order);
1160 for (
int I : Cand.LiveBundles.set_bits())
1161 dbgs() <<
" EB#" <<
I;
1164 if (
Cost < BestCost) {
1165 BestCand = NumCands;
1173unsigned RAGreedy::calculateRegionSplitCost(
const LiveInterval &VirtReg,
1178 unsigned BestCand = NoCand;
1181 if (IgnoreCSR && EvictAdvisor->isUnusedCalleeSavedReg(PhysReg))
1184 calculateRegionSplitCostAroundReg(PhysReg, Order, BestCost, NumCands,
1191unsigned RAGreedy::doRegionSplit(
const LiveInterval &VirtReg,
unsigned BestCand,
1203 if (BestCand != NoCand) {
1204 GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1205 if (
unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1207 Cand.IntvIdx = SE->openIntv();
1209 <<
B <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1216 GlobalSplitCandidate &Cand = GlobalCand.
front();
1217 assert(!Cand.PhysReg &&
"Compact region has no physreg");
1218 if (
unsigned B = Cand.getBundles(BundleCand, 0)) {
1220 Cand.IntvIdx = SE->openIntv();
1222 <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1227 splitAroundRegion(LREdit, UsedCands);
1233bool RAGreedy::trySplitAroundHintReg(
MCPhysReg Hint,
1244 if (ExtraInfo->getStage(VirtReg) >=
RS_Split2)
1257 if (OtherReg == Reg) {
1258 OtherReg =
Instr.getOperand(0).getReg();
1259 if (OtherReg == Reg)
1267 if (OtherPhysReg == Hint)
1277 unsigned NumCands = 0;
1278 unsigned BestCand = NoCand;
1279 SA->analyze(&VirtReg);
1280 calculateRegionSplitCostAroundReg(Hint, Order,
Cost, NumCands, BestCand);
1281 if (BestCand == NoCand)
1284 doRegionSplit(VirtReg, BestCand,
false, NewVRegs);
1295unsigned RAGreedy::tryBlockSplit(
const LiveInterval &VirtReg,
1298 assert(&SA->getParent() == &VirtReg &&
"Live range wasn't analyzed");
1305 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1306 SE->splitSingleBlock(BI);
1314 SE->finish(&IntvMap);
1321 for (
unsigned I = 0, E = LREdit.
size();
I != E; ++
I) {
1323 if (ExtraInfo->getOrInitStage(LI.
reg()) ==
RS_New && IntvMap[
I] == 0)
1328 MF->
verify(
this,
"After splitting live range around basic blocks");
1342 assert(SuperRC &&
"Invalid register class");
1345 MI->getRegClassConstraintEffectForVReg(Reg, SuperRC,
TII,
TRI,
1360 for (
auto [
MI, OpIdx] : Ops) {
1373 Mask |= ~SubRegMask;
1390 auto DestSrc =
TII->isCopyInstr(*
MI);
1391 if (DestSrc && !
MI->isBundled() &&
1392 DestSrc->Destination->getSubReg() == DestSrc->Source->getSubReg())
1401 LiveAtMask |= S.LaneMask;
1416unsigned RAGreedy::tryInstructionSplit(
const LiveInterval &VirtReg,
1422 bool SplitSubClass =
true;
1426 SplitSubClass =
false;
1435 if (
Uses.size() <= 1)
1439 <<
" individual instrs.\n");
1443 unsigned SuperRCNumAllocatableRegs =
1453 SuperRCNumAllocatableRegs ==
1466 SE->useIntv(SegStart, SegStop);
1469 if (LREdit.
empty()) {
1475 SE->finish(&IntvMap);
1491void RAGreedy::calcGapWeights(
MCRegister PhysReg,
1493 assert(SA->getUseBlocks().size() == 1 &&
"Not a local interval");
1496 const unsigned NumGaps =
Uses.size()-1;
1504 GapWeight.
assign(NumGaps, 0.0f);
1521 for (
unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1523 while (
Uses[Gap+1].getBoundaryIndex() < IntI.start())
1524 if (++Gap == NumGaps)
1530 const float weight = IntI.value()->weight();
1531 for (; Gap != NumGaps; ++Gap) {
1532 GapWeight[Gap] = std::max(GapWeight[Gap], weight);
1533 if (
Uses[Gap+1].getBaseIndex() >= IntI.stop())
1548 for (
unsigned Gap = 0;
I != E &&
I->start < StopIdx; ++
I) {
1549 while (
Uses[Gap+1].getBoundaryIndex() <
I->start)
1550 if (++Gap == NumGaps)
1555 for (; Gap != NumGaps; ++Gap) {
1557 if (
Uses[Gap+1].getBaseIndex() >=
I->end)
1569unsigned RAGreedy::tryLocalSplit(
const LiveInterval &VirtReg,
1574 if (SA->getUseBlocks().size() != 1)
1587 if (
Uses.size() <= 2)
1589 const unsigned NumGaps =
Uses.size()-1;
1592 dbgs() <<
"tryLocalSplit: ";
1608 unsigned RE = RMS.
size();
1609 for (
unsigned I = 0;
I != NumGaps && RI != RE; ++
I) {
1620 RegMaskGaps.push_back(
I);
1647 bool ProgressRequired = ExtraInfo->getStage(VirtReg) >=
RS_Split2;
1650 unsigned BestBefore = NumGaps;
1651 unsigned BestAfter = 0;
1654 const float blockFreq =
1663 calcGapWeights(PhysReg, GapWeight);
1667 for (
unsigned I = 0, E = RegMaskGaps.size();
I != E; ++
I)
1674 unsigned SplitBefore = 0, SplitAfter = 1;
1678 float MaxGap = GapWeight[0];
1682 const bool LiveBefore = SplitBefore != 0 || BI.
LiveIn;
1683 const bool LiveAfter = SplitAfter != NumGaps || BI.
LiveOut;
1686 <<
'-' <<
Uses[SplitAfter] <<
" I=" << MaxGap);
1689 if (!LiveBefore && !LiveAfter) {
1697 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
1700 bool Legal = !ProgressRequired || NewGaps < NumGaps;
1709 blockFreq * (NewGaps + 1),
1710 Uses[SplitBefore].distance(
Uses[SplitAfter]) +
1718 float Diff = EstWeight - MaxGap;
1719 if (Diff > BestDiff) {
1722 BestBefore = SplitBefore;
1723 BestAfter = SplitAfter;
1730 if (++SplitBefore < SplitAfter) {
1733 if (GapWeight[SplitBefore - 1] >= MaxGap) {
1734 MaxGap = GapWeight[SplitBefore];
1735 for (
unsigned I = SplitBefore + 1;
I != SplitAfter; ++
I)
1736 MaxGap = std::max(MaxGap, GapWeight[
I]);
1744 if (SplitAfter >= NumGaps) {
1750 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
1755 if (BestBefore == NumGaps)
1759 <<
Uses[BestAfter] <<
", " << BestDiff <<
", "
1760 << (BestAfter - BestBefore + 1) <<
" instrs\n");
1768 SE->useIntv(SegStart, SegStop);
1770 SE->finish(&IntvMap);
1775 bool LiveBefore = BestBefore != 0 || BI.
LiveIn;
1776 bool LiveAfter = BestAfter != NumGaps || BI.
LiveOut;
1777 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1778 if (NewGaps >= NumGaps) {
1780 assert(!ProgressRequired &&
"Didn't make progress when it was required.");
1781 for (
unsigned I = 0, E = IntvMap.
size();
I != E; ++
I)
1782 if (IntvMap[
I] == 1) {
1804 if (ExtraInfo->getStage(VirtReg) >=
RS_Spill)
1811 SA->analyze(&VirtReg);
1812 Register PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
1813 if (PhysReg || !NewVRegs.
empty())
1815 return tryInstructionSplit(VirtReg, Order, NewVRegs);
1821 SA->analyze(&VirtReg);
1826 if (ExtraInfo->getStage(VirtReg) <
RS_Split2) {
1827 MCRegister PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1828 if (PhysReg || !NewVRegs.
empty())
1833 return tryBlockSplit(VirtReg, Order, NewVRegs);
1856 if (PhysReg == AssignedReg)
1869bool RAGreedy::mayRecolorAllInterferences(
1871 SmallLISet &RecoloringCandidates,
const SmallVirtRegSet &FixedRegisters) {
1882 CutOffInfo |= CO_Interf;
1897 if (((ExtraInfo->getStage(*Intf) ==
RS_Done &&
1902 FixedRegisters.
count(Intf->reg())) {
1904 dbgs() <<
"Early abort: the interference is not recolorable.\n");
1907 RecoloringCandidates.insert(Intf);
1956unsigned RAGreedy::tryLastChanceRecoloring(
const LiveInterval &VirtReg,
1960 RecoloringStack &RecolorStack,
1965 LLVM_DEBUG(
dbgs() <<
"Try last chance recoloring for " << VirtReg <<
'\n');
1967 const ssize_t EntryStackSize = RecolorStack.size();
1971 "Last chance recoloring should really be last chance");
1977 LLVM_DEBUG(
dbgs() <<
"Abort because max depth has been reached.\n");
1978 CutOffInfo |= CO_Depth;
1983 SmallLISet RecoloringCandidates;
1995 RecoloringCandidates.clear();
1996 CurrentNewVRegs.
clear();
2002 dbgs() <<
"Some interferences are not with virtual registers.\n");
2009 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
2011 LLVM_DEBUG(
dbgs() <<
"Some interferences cannot be recolored.\n");
2018 PQueue RecoloringQueue;
2021 enqueue(RecoloringQueue, RC);
2023 "Interferences are supposed to be with allocated variables");
2026 RecolorStack.push_back(std::make_pair(RC,
VRM->
getPhys(ItVirtReg)));
2041 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
2042 FixedRegisters, RecolorStack,
Depth)) {
2044 for (
Register NewVReg : CurrentNewVRegs)
2056 FixedRegisters = SaveFixedRegisters;
2063 for (
Register R : CurrentNewVRegs) {
2075 for (ssize_t
I = RecolorStack.size() - 1;
I >= EntryStackSize; --
I) {
2078 std::tie(LI, PhysReg) = RecolorStack[
I];
2084 for (
size_t I = EntryStackSize;
I != RecolorStack.size(); ++
I) {
2087 std::tie(LI, PhysReg) = RecolorStack[
I];
2093 RecolorStack.resize(EntryStackSize);
2108bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2111 RecoloringStack &RecolorStack,
2113 while (!RecoloringQueue.empty()) {
2116 MCRegister PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters,
2117 RecolorStack,
Depth + 1);
2122 if (PhysReg == ~0u || (!PhysReg && !LI->
empty()))
2126 assert(LI->
empty() &&
"Only empty live-range do not require a register");
2128 <<
" succeeded. Empty LI.\n");
2132 <<
" succeeded with: " <<
printReg(PhysReg,
TRI) <<
'\n');
2146 CutOffInfo = CO_None;
2151 selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters, RecolorStack);
2152 if (Reg == ~0U && (CutOffInfo != CO_None)) {
2153 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2154 if (CutOffEncountered == CO_Depth)
2155 Ctx.
emitError(
"register allocation failed: maximum depth for recoloring "
2156 "reached. Use -fexhaustive-register-search to skip "
2158 else if (CutOffEncountered == CO_Interf)
2159 Ctx.
emitError(
"register allocation failed: maximum interference for "
2160 "recoloring reached. Use -fexhaustive-register-search "
2162 else if (CutOffEncountered == (CO_Depth | CO_Interf))
2163 Ctx.
emitError(
"register allocation failed: maximum interference and "
2164 "depth for recoloring reached. Use "
2165 "-fexhaustive-register-search to skip cutoffs");
2182 SA->analyze(&VirtReg);
2183 if (calcSpillCost() >= CSRCost)
2188 CostPerUseLimit = 1;
2191 if (ExtraInfo->getStage(VirtReg) <
RS_Split) {
2194 SA->analyze(&VirtReg);
2195 unsigned NumCands = 0;
2197 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2199 if (BestCand == NoCand)
2204 doRegionSplit(VirtReg, BestCand,
false, NewVRegs);
2212 SetOfBrokenHints.remove(&LI);
2215void RAGreedy::initializeCSRCost() {
2230 if (ActualEntry < FixedEntry)
2232 else if (ActualEntry <= UINT32_MAX)
2244void RAGreedy::collectHintInfo(
Register Reg, HintsInfo &Out) {
2250 if (OtherReg == Reg) {
2251 OtherReg =
Instr.getOperand(1).getReg();
2252 if (OtherReg == Reg)
2270 for (
const HintInfo &Info :
List) {
2271 if (
Info.PhysReg != PhysReg)
2285void RAGreedy::tryHintRecoloring(
const LiveInterval &VirtReg) {
2306 if (
Reg.isPhysical())
2312 "We have an unallocated variable which should have been handled");
2327 <<
") is recolorable.\n");
2331 collectHintInfo(Reg, Info);
2334 if (CurrPhys != PhysReg) {
2336 BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);
2341 if (OldCopiesCost < NewCopiesCost) {
2355 for (
const HintInfo &HI : Info) {
2359 }
while (!RecoloringCandidates.
empty());
2398void RAGreedy::tryHintsRecoloring() {
2401 "Recoloring is possible only for virtual registers");
2406 tryHintRecoloring(*LI);
2413 RecoloringStack &RecolorStack,
2415 uint8_t CostPerUseLimit = uint8_t(~0u);
2420 tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {
2425 EvictAdvisor->isUnusedCalleeSavedReg(PhysReg) && NewVRegs.
empty()) {
2426 MCRegister CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
2427 CostPerUseLimit, NewVRegs);
2428 if (CSRReg || !NewVRegs.
empty())
2436 if (!NewVRegs.
empty())
2441 << ExtraInfo->getCascade(VirtReg.
reg()) <<
'\n');
2448 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,
2456 if (Hint && Hint != PhysReg)
2457 SetOfBrokenHints.insert(&VirtReg);
2461 assert((NewVRegs.
empty() ||
Depth) &&
"Cannot append to existing NewVRegs");
2467 ExtraInfo->setStage(VirtReg,
RS_Split);
2475 unsigned NewVRegSizeBefore = NewVRegs.
size();
2476 Register PhysReg = trySplit(VirtReg, Order, NewVRegs, FixedRegisters);
2477 if (PhysReg || (NewVRegs.
size() - NewVRegSizeBefore))
2484 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
2485 RecolorStack,
Depth);
2491 ExtraInfo->getStage(VirtReg) <
RS_Memory) {
2496 ExtraInfo->setStage(VirtReg,
RS_Memory);
2512 MF->
verify(
this,
"After spilling");
2521 using namespace ore;
2523 R <<
NV(
"NumSpills", Spills) <<
" spills ";
2524 R <<
NV(
"TotalSpillsCost", SpillsCost) <<
" total spills cost ";
2527 R <<
NV(
"NumFoldedSpills", FoldedSpills) <<
" folded spills ";
2528 R <<
NV(
"TotalFoldedSpillsCost", FoldedSpillsCost)
2529 <<
" total folded spills cost ";
2532 R <<
NV(
"NumReloads", Reloads) <<
" reloads ";
2533 R <<
NV(
"TotalReloadsCost", ReloadsCost) <<
" total reloads cost ";
2535 if (FoldedReloads) {
2536 R <<
NV(
"NumFoldedReloads", FoldedReloads) <<
" folded reloads ";
2537 R <<
NV(
"TotalFoldedReloadsCost", FoldedReloadsCost)
2538 <<
" total folded reloads cost ";
2540 if (ZeroCostFoldedReloads)
2541 R <<
NV(
"NumZeroCostFoldedReloads", ZeroCostFoldedReloads)
2542 <<
" zero cost folded reloads ";
2544 R <<
NV(
"NumVRCopies",
Copies) <<
" virtual registers copies ";
2545 R <<
NV(
"TotalCopiesCost", CopiesCost) <<
" total copies cost ";
2550 RAGreedyStats
Stats;
2556 A->getPseudoValue())->getFrameIndex());
2559 return MI.getOpcode() == TargetOpcode::PATCHPOINT ||
2560 MI.getOpcode() == TargetOpcode::STACKMAP ||
2561 MI.getOpcode() == TargetOpcode::STATEPOINT;
2574 if (SrcReg && Src.getSubReg())
2582 if (SrcReg != DestReg)
2599 if (!isPatchpointInstr(
MI)) {
2604 std::pair<unsigned, unsigned> NonZeroCostRange =
2608 for (
unsigned Idx = 0, E =
MI.getNumOperands();
Idx < E; ++
Idx) {
2612 if (
Idx >= NonZeroCostRange.first &&
Idx < NonZeroCostRange.second)
2618 for (
unsigned Slot : FoldedReloads)
2619 ZeroCostFoldedReloads.
erase(Slot);
2620 Stats.FoldedReloads += FoldedReloads.size();
2621 Stats.ZeroCostFoldedReloads += ZeroCostFoldedReloads.
size();
2634 Stats.FoldedReloadsCost = RelFreq *
Stats.FoldedReloads;
2636 Stats.FoldedSpillsCost = RelFreq *
Stats.FoldedSpills;
2641RAGreedy::RAGreedyStats RAGreedy::reportStats(
MachineLoop *L) {
2642 RAGreedyStats
Stats;
2646 Stats.add(reportStats(SubLoop));
2653 if (!
Stats.isEmpty()) {
2654 using namespace ore;
2658 L->getStartLoc(),
L->getHeader());
2660 R <<
"generated in loop";
2667void RAGreedy::reportStats() {
2670 RAGreedyStats
Stats;
2672 Stats.add(reportStats(L));
2677 if (!
Stats.isEmpty()) {
2678 using namespace ore;
2682 if (
auto *SP = MF->getFunction().getSubprogram())
2687 R <<
"generated in function";
2693bool RAGreedy::hasVirtRegAlloc() {
2709 LLVM_DEBUG(
dbgs() <<
"********** GREEDY REGISTER ALLOCATION **********\n"
2710 <<
"********** Function: " << mf.
getName() <<
'\n');
2713 TII = MF->getSubtarget().getInstrInfo();
2716 MF->verify(
this,
"Before greedy register allocator");
2719 getAnalysis<LiveIntervals>(),
2720 getAnalysis<LiveRegMatrix>());
2724 if (!hasVirtRegAlloc())
2727 Indexes = &getAnalysis<SlotIndexes>();
2731 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
2732 DomTree = &getAnalysis<MachineDominatorTree>();
2733 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
2734 Loops = &getAnalysis<MachineLoopInfo>();
2735 Bundles = &getAnalysis<EdgeBundles>();
2736 SpillPlacer = &getAnalysis<SpillPlacement>();
2737 DebugVars = &getAnalysis<LiveDebugVariables>();
2739 initializeCSRCost();
2742 RegClassPriorityTrumpsGlobalness =
2751 ExtraInfo.emplace();
2753 getAnalysis<RegAllocEvictionAdvisorAnalysis>().getAdvisor(*MF, *
this);
2755 getAnalysis<RegAllocPriorityAdvisorAnalysis>().getAdvisor(*MF, *
this);
2757 VRAI = std::make_unique<VirtRegAuxInfo>(*MF, *
LIS, *
VRM, *
Loops, *MBFI);
2760 VRAI->calculateSpillWeightsAndHints();
2769 SetOfBrokenHints.clear();
2772 tryHintsRecoloring();
2775 MF->verify(
this,
"Before post optimization");
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Analysis containing CSE Info
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
DenseMap< Block *, BlockRelaxAux > Blocks
Rewrite Partial Register Uses
const HexagonInstrInfo * TII
This file implements an indexed map.
block placement Basic Block Placement Stats
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static cl::opt< bool > GreedyRegClassPriorityTrumpsGlobalness("greedy-regclass-priority-trumps-globalness", cl::desc("Change the greedy register allocator's live range priority " "calculation to make the AllocationPriority of the register class " "more important then whether the range is global"), cl::Hidden)
static cl::opt< bool > ExhaustiveSearch("exhaustive-register-search", cl::NotHidden, cl::desc("Exhaustive Search for registers bypassing the depth " "and interference cutoffs of last chance recoloring"), cl::Hidden)
static cl::opt< unsigned > LastChanceRecoloringMaxInterference("lcr-max-interf", cl::Hidden, cl::desc("Last chance recoloring maximum number of considered" " interference at a time"), cl::init(8))
static bool hasTiedDef(MachineRegisterInfo *MRI, unsigned reg)
Return true if reg has any tied def operand.
static bool readsLaneSubset(const MachineRegisterInfo &MRI, const MachineInstr *MI, const LiveInterval &VirtReg, const TargetRegisterInfo *TRI, SlotIndex Use, const TargetInstrInfo *TII)
Return true if MI at \P Use reads a subset of the lanes live in VirtReg.
static bool assignedRegPartiallyOverlaps(const TargetRegisterInfo &TRI, const VirtRegMap &VRM, MCRegister PhysReg, const LiveInterval &Intf)
Return true if the existing assignment of Intf overlaps, but is not the same, as PhysReg.
static cl::opt< unsigned > CSRFirstTimeCost("regalloc-csr-first-time-cost", cl::desc("Cost for first time use of callee-saved register."), cl::init(0), cl::Hidden)
static cl::opt< unsigned > LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden, cl::desc("Last chance recoloring max depth"), cl::init(5))
static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator)
static cl::opt< unsigned long > GrowRegionComplexityBudget("grow-region-complexity-budget", cl::desc("growRegion() does not scale with the number of BB edges, so " "limit its budget and bail out once we reach the limit."), cl::init(10000), cl::Hidden)
Greedy Register Allocator
static cl::opt< SplitEditor::ComplementSpillMode > SplitSpillMode("split-spill-mode", cl::Hidden, cl::desc("Spill mode for splitting live ranges"), cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")), cl::init(SplitEditor::SM_Speed))
static unsigned getNumAllocatableRegsForConstraints(const MachineInstr *MI, Register Reg, const TargetRegisterClass *SuperRC, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, const RegisterClassInfo &RCI)
Get the number of allocatable registers that match the constraints of Reg on MI and that are also in ...
static cl::opt< bool > EnableDeferredSpilling("enable-deferred-spilling", cl::Hidden, cl::desc("Instead of spilling a variable right away, defer the actual " "code insertion to the end of the allocation. That way the " "allocator might still find a suitable coloring for this " "variable because of other evicted variables."), cl::init(false))
static cl::opt< unsigned > SplitThresholdForRegWithHint("split-threshold-for-reg-with-hint", cl::desc("The threshold for splitting a virtual register with a hint, in " "percentate"), cl::init(75), cl::Hidden)
static cl::opt< bool > GreedyReverseLocalAssignment("greedy-reverse-local-assignment", cl::desc("Reverse allocation order of local live ranges, such that " "shorter local live ranges will tend to be allocated first"), cl::Hidden)
static LaneBitmask getInstReadLaneMask(const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, const MachineInstr &FirstMI, Register Reg)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
This file defines the SmallSet class.
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)
bool isHint(Register Reg) const
Return true if Reg is a preferred physical register.
ArrayRef< MCPhysReg > getOrder() const
Get the allocation order without reordered hints.
static AllocationOrder create(unsigned VirtReg, const VirtRegMap &VRM, const RegisterClassInfo &RegClassInfo, const LiveRegMatrix *Matrix)
Create a new AllocationOrder for VirtReg.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this 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),...
size_t size() const
size - Get the array size.
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.
bool test(unsigned Idx) const
static BlockFrequency max()
Returns the maximum possible frequency, the saturation value.
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
ArrayRef< unsigned > getBlocks(unsigned Bundle) const
getBlocks - Return an array of blocks that are connected to Bundle.
unsigned getBundle(unsigned N, bool Out) const
getBundle - Return the ingoing (Out = false) or outgoing (Out = true) bundle number for basic block N
unsigned getNumBundles() const
getNumBundles - Return the total number of bundles in the CFG.
FunctionPass class - This class is used to implement most global optimizations.
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Cursor - The primary query interface for the block interference cache.
SlotIndex first()
first - Return the starting index of the first interfering range in the current block.
SlotIndex last()
last - Return the ending index of the last interfering range in the current block.
bool hasInterference()
hasInterference - Return true if the current block has any interference.
void moveToBlock(unsigned MBBNum)
moveTo - Move cursor to basic block MBBNum.
void init(MachineFunction *mf, LiveIntervalUnion *liuarray, SlotIndexes *indexes, LiveIntervals *lis, const TargetRegisterInfo *tri)
init - Prepare cache for a new function.
unsigned getMaxCursors() const
getMaxCursors - Return the maximum number of concurrent cursors that can be supported.
This is an important class for using LLVM in a threaded context.
void emitError(uint64_t LocCookie, const Twine &ErrorStr)
emitError - Emit an error message to the currently installed error handler with optional location inf...
void splitRegister(Register OldReg, ArrayRef< Register > NewRegs, LiveIntervals &LIS)
splitRegister - Move any user variables in OldReg to the live ranges in NewRegs where they are live.
Query interferences between a single live virtual register and a live interval union.
const SmallVectorImpl< const LiveInterval * > & interferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
SegmentIter find(SlotIndex x)
LiveSegments::iterator SegmentIter
A live range for subregisters.
LiveInterval - This class represents the liveness of a register, or stack slot.
bool isSpillable() const
isSpillable - Can this interval be spilled?
bool hasSubRanges() const
Returns true if subregister liveness information is available.
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange's.
iterator_range< subrange_iterator > subranges()
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const
Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...
LiveInterval & getInterval(Register Reg)
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
Register get(unsigned idx) const
ArrayRef< Register > regs() const
This class represents the liveness of a register, stack slot, etc.
bool liveAt(SlotIndex index) const
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
bool checkRegMaskInterference(const LiveInterval &VirtReg, MCRegister PhysReg=MCRegister::NoRegister)
Check for regmask interference only.
void unassign(const LiveInterval &VirtReg)
Unassign VirtReg from its PhysReg.
LiveIntervalUnion::Query & query(const LiveRange &LR, MCRegister RegUnit)
Query a line of the assigned virtual register matrix directly.
bool isPhysRegUsed(MCRegister PhysReg) const
Returns true if the given PhysReg has any live intervals assigned.
@ IK_VirtReg
Virtual register interference.
void assign(const LiveInterval &VirtReg, MCRegister PhysReg)
Assign VirtReg to PhysReg.
InterferenceKind checkInterference(const LiveInterval &VirtReg, MCRegister PhysReg)
Check for interference before assigning VirtReg to PhysReg.
LiveIntervalUnion * getLiveUnions()
Directly access the live interval unions per regunit.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
Wrapper class representing physical registers. Should be passed by value.
constexpr bool isValid() const
static constexpr unsigned NoRegister
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
double getBlockFreqRelativeToEntryBlock(const MachineBasicBlock *MBB) const
Compute the frequency of the block, relative to the entry block.
BlockFrequency getEntryFreq() const
Divide a block's BlockFrequency::getFrequency() value by this value to obtain the entry block - relat...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
bool isSpillSlotObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a spill slot.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Function & getFunction()
Return the LLVM function that this machine code represents.
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.
bool isImplicitDef() const
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Register getReg() const
getReg - Returns the register number.
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Register getSimpleHint(Register VReg) const
getSimpleHint - same as getRegAllocationHint except it will only return a target independent hint.
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.
iterator_range< def_iterator > def_operands(Register Reg) const
LaneBitmask getMaxLaneMaskForVReg(Register Reg) const
Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
iterator_range< reg_instr_nodbg_iterator > reg_nodbg_instructions(Register Reg) const
Spiller & spiller() override
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
MCRegister selectOrSplit(const LiveInterval &, SmallVectorImpl< Register > &) override
bool runOnMachineFunction(MachineFunction &mf) override
Perform register allocation.
const LiveInterval * dequeue() override
dequeue - Return the next unassigned register, or NULL.
void enqueueImpl(const LiveInterval *LI) override
enqueue - Add VirtReg to the priority queue of unassigned registers.
RAGreedy(const RegClassFilterFunc F=allocateAllRegClasses)
void getAnalysisUsage(AnalysisUsage &AU) const override
RAGreedy analysis usage.
void aboutToRemoveInterval(const LiveInterval &) override
Method called when the allocator is about to remove a LiveInterval.
RegAllocBase provides the register allocation driver and interface that can be extended to add intere...
void enqueue(const LiveInterval *LI)
enqueue - Add VirtReg to the priority queue of unassigned registers.
void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat)
SmallPtrSet< MachineInstr *, 32 > DeadRemats
Inst which is a def of an original reg and whose defs are already all dead after remat is saved in De...
const TargetRegisterInfo * TRI
static const char TimerGroupName[]
static const char TimerGroupDescription[]
virtual void postOptimization()
RegisterClassInfo RegClassInfo
MachineRegisterInfo * MRI
static bool VerifyEnabled
VerifyEnabled - True when -verify-regalloc is given.
const RegClassFilterFunc ShouldAllocateClass
ImmutableAnalysis abstraction for fetching the Eviction Advisor.
std::optional< unsigned > getOrderLimit(const LiveInterval &VirtReg, const AllocationOrder &Order, unsigned CostPerUseLimit) const
bool isUnusedCalleeSavedReg(MCRegister PhysReg) const
Returns true if the given PhysReg is a callee saved register and has not been used for allocation yet...
bool canReassign(const LiveInterval &VirtReg, MCRegister FromReg) const
bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const
unsigned getLastCostChange(const TargetRegisterClass *RC) const
Get the position of the last cost change in getOrder(RC).
bool isProperSubClass(const TargetRegisterClass *RC) const
isProperSubClass - Returns true if RC has a legal super-class with more allocatable registers.
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
uint8_t getMinCost(const TargetRegisterClass *RC) const
Get the minimum register cost in RC's allocation order.
MCRegister getLastCalleeSavedAlias(MCRegister PhysReg) const
getLastCalleeSavedAlias - Returns the last callee saved register that overlaps PhysReg,...
Wrapper class representing virtual and physical registers.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
SlotIndex - An opaque wrapper around machine indexes.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
@ InstrDist
The default distance between instructions as returned by distance().
bool isValid() const
Returns true if this is a valid index.
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
int getApproxInstrDistance(SlotIndex other) const
Return the scaled distance from this index to the given one, where all slots on the same instruction ...
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
SlotIndex getLastIndex()
Returns the base index of the last slot in this analysis.
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
void packIndexes()
Renumber all indexes using the default instruction distance.
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
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 assign(size_type NumElts, ValueParamT Elt)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)
addConstraints - Add constraints and biases.
bool finish()
finish - Compute the optimal spill code placement given the constraints.
void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)
addPrefSpill - Add PrefSpill constraints to all blocks listed.
void prepare(BitVector &RegBundles)
prepare - Reset state and prepare for a new spill placement computation.
bool scanActiveBundles()
scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks,...
void addLinks(ArrayRef< unsigned > Links)
addLinks - Add transparent blocks with the given numbers.
void iterate()
iterate - Update the network iteratively until convergence, or new bundles are found.
@ MustSpill
A register is impossible, variable must be spilled.
@ DontCare
Block doesn't care / variable not live.
@ PrefReg
Block entry/exit prefers a register.
@ PrefSpill
Block entry/exit prefers a stack slot.
ArrayRef< unsigned > getRecentPositive()
getRecentPositive - Return an array of bundles that became positive during the previous call to scanA...
BlockFrequency getBlockFrequency(unsigned Number) const
getBlockFrequency - Return the estimated block execution frequency per function invocation.
virtual void spill(LiveRangeEdit &LRE)=0
spill - Spill the LRE.getParent() live interval.
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
SplitEditor - Edit machine code and LiveIntervals for live range splitting.
@ SM_Partition
SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...
@ SM_Speed
SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies.
@ SM_Size
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.
TargetInstrInfo - Interface to description of machine instruction set.
virtual std::pair< unsigned, unsigned > getPatchpointUnfoldableRange(const MachineInstr &MI) const
For a patchpoint, stackmap, or statepoint intrinsic, return the range of operands which can't be fold...
bool isFullCopyInstr(const MachineInstr &MI) const
virtual bool hasStoreToStackSlot(const MachineInstr &MI, SmallVectorImpl< const MachineMemOperand * > &Accesses) const
If the specified machine instruction has a store to a stack slot, return true along with the FrameInd...
virtual Register isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const
If the specified machine instruction is a direct load from a stack slot, return the virtual or physic...
virtual Register isStoreToStackSlot(const MachineInstr &MI, int &FrameIndex) const
If the specified machine instruction is a direct store to a stack slot, return the virtual or physica...
std::optional< DestSourcePair > isCopyInstr(const MachineInstr &MI) const
If the specific machine instruction is a instruction that moves/copies value from one register to ano...
virtual bool hasLoadFromStackSlot(const MachineInstr &MI, SmallVectorImpl< const MachineMemOperand * > &Accesses) const
If the specified machine instruction has a load from a stack slot, return true along with the FrameIn...
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
const bool GlobalPriority
const uint8_t AllocationPriority
Classes with a higher priority value are assigned first by register allocators using a greedy heurist...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual bool shouldUseDeferredSpillingForVirtReg(const MachineFunction &MF, const LiveInterval &VirtReg) const
Deferred spilling delays the spill insertion of a virtual register after every other allocation.
virtual bool shouldRegionSplitForVirtReg(const MachineFunction &MF, const LiveInterval &VirtReg) const
Region split has a high compile time cost especially for large live range.
virtual bool shouldUseLastChanceRecoloringForVirtReg(const MachineFunction &MF, const LiveInterval &VirtReg) const
Last chance recoloring has a high compile time cost especially for targets with a lot of registers.
virtual unsigned getCSRFirstUseCost() const
Allow the target to override the cost of using a callee-saved register for the first time.
LaneBitmask getCoveringLanes() const
The lane masks returned by getSubRegIndexLaneMask() above can only be used to determine if sub-regist...
ArrayRef< uint8_t > getRegisterCosts(const MachineFunction &MF) const
Get a list of cost values for all registers that correspond to the index returned by RegisterCostTabl...
virtual bool reverseLocalAssignment() const
Allow the target to reverse allocation order of local live ranges.
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
virtual const TargetRegisterClass * getLargestLegalSuperClass(const TargetRegisterClass *RC, const MachineFunction &) const
Returns the largest super class of RC that is legal to use in the current sub-target and has the same...
MCRegister getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo.
bool regsOverlap(Register RegA, Register RegB) const
Returns true if the two registers are equal or alias each other.
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
virtual bool regClassPriorityTrumpsGlobalness(const MachineFunction &MF) const
When prioritizing live ranges in register allocation, if this hook returns true then the AllocationPr...
A Use represents the edge between a Value definition and its users.
bool hasKnownPreference(Register VirtReg) const
returns true if VirtReg has a known preferred register.
MCRegister getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
Reg
All possible values of the reg field in the ModR/M byte.
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< InstrNode * > Instr
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
FunctionPass * createGreedyRegisterAllocator()
Greedy register allocation pass - This pass implements a global register allocator for optimized buil...
bool TimePassesIsEnabled
If the user specifies the -time-passes argument on an LLVM tool command line then the value of this b...
char & RAGreedyID
Greedy register allocator.
Spiller * createInlineSpiller(MachineFunctionPass &Pass, MachineFunction &MF, VirtRegMap &VRM, VirtRegAuxInfo &VRAI)
Create and return a spiller that will insert spill code directly instead of deferring though VirtRegM...
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)
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.
@ RS_Split2
Attempt more aggressive live range splitting that is guaranteed to make progress.
@ RS_Spill
Live range will be spilled. No more splitting will be attempted.
@ RS_Split
Attempt live range splitting if assignment is impossible.
@ RS_New
Newly created live range that has never been queued.
@ RS_Done
There is nothing more we can do to this live range.
@ RS_Assign
Only attempt assignment and eviction. Then requeue as RS_Split.
@ RS_Memory
Live range is in memory.
VirtRegInfo AnalyzeVirtRegInBundle(MachineInstr &MI, Register Reg, SmallVectorImpl< std::pair< MachineInstr *, unsigned > > *Ops=nullptr)
AnalyzeVirtRegInBundle - Analyze how the current instruction or bundle uses a virtual register.
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Printable printBlockFreq(const BlockFrequencyInfo &BFI, BlockFrequency Freq)
Print the block frequency Freq relative to the current functions entry frequency.
static float normalizeSpillWeight(float UseDefFreq, unsigned Size, unsigned NumInstr)
Normalize the spill weight of a live interval.
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
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
uint64_t maxUIntN(uint64_t N)
Gets the maximum value for a N-bit unsigned integer.
constexpr bool any() const
This class is basically a combination of TimeRegion and Timer.
BlockConstraint - Entry and exit constraints for a basic block.
BorderConstraint Exit
Constraint on block exit.
bool ChangesValue
True when this block changes the value of the live range.
BorderConstraint Entry
Constraint on block entry.
unsigned Number
Basic block number (from MBB::getNumber()).
Additional information about basic blocks where the current variable is live.
SlotIndex FirstDef
First non-phi valno->def, or SlotIndex().
bool LiveOut
Current reg is live out.
bool LiveIn
Current reg is live in.
SlotIndex LastInstr
Last instr accessing current reg.
SlotIndex FirstInstr
First instr accessing current reg.