76#define DEBUG_TYPE "regalloc"
78STATISTIC(NumGlobalSplits,
"Number of split global live ranges");
79STATISTIC(NumLocalSplits,
"Number of split local live ranges");
80STATISTIC(NumEvicted,
"Number of interferences evicted");
84 cl::desc(
"Spill mode for splitting live ranges"),
92 cl::desc(
"Last chance recoloring max depth"),
97 cl::desc(
"Last chance recoloring maximum number of considered"
98 " interference at a time"),
103 cl::desc(
"Exhaustive Search for registers bypassing the depth "
104 "and interference cutoffs of last chance recoloring"),
109 cl::desc(
"Instead of spilling a variable right away, defer the actual "
110 "code insertion to the end of the allocation. That way the "
111 "allocator might still find a suitable coloring for this "
112 "variable because of other evicted variables."),
118 cl::desc(
"Cost for first time use of callee-saved register."),
122 "grow-region-complexity-budget",
123 cl::desc(
"growRegion() does not scale with the number of BB edges, so "
124 "limit its budget and bail out once we reach the limit."),
128 "greedy-regclass-priority-trumps-globalness",
129 cl::desc(
"Change the greedy register allocator's live range priority "
130 "calculation to make the AllocationPriority of the register class "
131 "more important then whether the range is global"),
135 "greedy-reverse-local-assignment",
136 cl::desc(
"Reverse allocation order of local live ranges, such that "
137 "shorter local live ranges will tend to be allocated first"),
141 "split-threshold-for-reg-with-hint",
142 cl::desc(
"The threshold for splitting a virtual register with a hint, in "
153 "Greedy Register Allocator",
false,
false)
173const char *
const RAGreedy::StageName[] = {
231bool RAGreedy::LRE_CanEraseVirtReg(
Register VirtReg) {
246void RAGreedy::LRE_WillShrinkVirtReg(
Register VirtReg) {
257 ExtraInfo->LRE_DidCloneVirtReg(New, Old);
262 if (!Info.inBounds(Old))
271 Info[New] = Info[Old];
275 SpillerInstance.reset();
281void RAGreedy::enqueue(PQueue &CurQueue,
const LiveInterval *LI) {
285 assert(Reg.isVirtual() &&
"Can only enqueue virtual registers");
287 auto Stage = ExtraInfo->getOrInitStage(Reg);
290 ExtraInfo->setStage(Reg, Stage);
293 unsigned Ret = PriorityAdvisor->getPriority(*LI);
297 CurQueue.push(std::make_pair(Ret, ~Reg));
300unsigned DefaultPriorityAdvisor::getPriority(
const LiveInterval &LI)
const {
315 static unsigned MemOp = 0;
322 (!ReverseLocalAssignment &&
325 unsigned GlobalBit = 0;
332 if (!ReverseLocalAssignment)
360 Prio = std::min(Prio, (
unsigned)
maxUIntN(24));
363 if (RegClassPriorityTrumpsGlobalness)
379unsigned DummyPriorityAdvisor::getPriority(
const LiveInterval &LI)
const {
388 if (CurQueue.empty())
405 for (
auto I = Order.
begin(), E = Order.
end();
I != E && !PhysReg; ++
I) {
426 if (EvictAdvisor->canEvictHintInterference(VirtReg, PhysHint,
428 evictInterference(VirtReg, PhysHint, NewVRegs);
433 if (trySplitAroundHintReg(PhysHint, VirtReg, NewVRegs, Order))
438 SetOfBrokenHints.insert(&VirtReg);
449 << (
unsigned)
Cost <<
'\n');
450 MCRegister CheapReg = tryEvict(VirtReg, Order, NewVRegs,
Cost, FixedRegisters);
451 return CheapReg ? CheapReg : PhysReg;
460 auto HasRegUnitInterference = [&](
MCRegUnit Unit) {
484void RAGreedy::evictInterference(
const LiveInterval &VirtReg,
490 unsigned Cascade = ExtraInfo->getOrAssignNewCascade(VirtReg.
reg());
493 <<
" interference: Cascade " << Cascade <<
'\n');
514 assert((ExtraInfo->getCascade(Intf->reg()) < Cascade ||
516 "Cannot decrease cascade number, illegal eviction");
517 ExtraInfo->setCascade(Intf->reg(), Cascade);
533std::optional<unsigned>
536 unsigned CostPerUseLimit)
const {
537 unsigned OrderLimit = Order.
getOrder().size();
539 if (CostPerUseLimit <
uint8_t(~0u)) {
543 if (MinCost >= CostPerUseLimit) {
545 << MinCost <<
", no cheaper registers to be found.\n");
551 if (RegCosts[Order.
getOrder().back()] >= CostPerUseLimit) {
562 if (RegCosts[PhysReg] >= CostPerUseLimit)
566 if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {
588 MCRegister BestPhys = EvictAdvisor->tryFindEvictionCandidate(
589 VirtReg, Order, CostPerUseLimit, FixedRegisters);
591 evictInterference(VirtReg, BestPhys, NewVRegs);
609 SplitConstraints.resize(UseBlocks.
size());
611 for (
unsigned I = 0;
I != UseBlocks.
size(); ++
I) {
646 SA->getFirstSplitPoint(BC.
Number)))
652 if (Intf.
last() >= SA->getLastSplitPoint(BC.
Number)) {
679 const unsigned GroupSize = 8;
681 unsigned TBS[GroupSize];
682 unsigned B = 0,
T = 0;
688 assert(
T < GroupSize &&
"Array overflow");
690 if (++
T == GroupSize) {
697 assert(
B < GroupSize &&
"Array overflow");
703 if (FirstNonDebugInstr !=
MBB->
end() &&
705 SA->getFirstSplitPoint(
Number)))
714 if (Intf.
last() >= SA->getLastSplitPoint(
Number))
719 if (++
B == GroupSize) {
730bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
734 unsigned AddedTo = 0;
736 unsigned Visited = 0;
743 for (
unsigned Bundle : NewBundles) {
747 if (
Blocks.size() >= Budget)
762 if (ActiveBlocks.
size() == AddedTo)
769 if (!addThroughConstraints(Cand.Intf, NewBlocks))
777 bool PrefSpill =
true;
778 if (SA->looksLikeLoopIV() && NewBlocks.size() >= 2) {
784 if (L &&
L->getHeader()->getNumber() == (
int)NewBlocks[0] &&
785 all_of(NewBlocks.drop_front(), [&](
unsigned Block) {
786 return L == Loops->getLoopFor(MF->getBlockNumbered(Block));
793 AddedTo = ActiveBlocks.
size();
809bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
811 if (!SA->getNumThroughBlocks())
821 SpillPlacer->
prepare(Cand.LiveBundles);
825 if (!addSplitConstraints(Cand.Intf,
Cost)) {
830 if (!growRegion(Cand)) {
837 if (!Cand.LiveBundles.any()) {
843 for (
int I : Cand.LiveBundles.set_bits())
844 dbgs() <<
" EB#" <<
I;
871BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
874 const BitVector &LiveBundles = Cand.LiveBundles;
876 for (
unsigned I = 0;
I != UseBlocks.
size(); ++
I) {
883 Cand.Intf.moveToBlock(BC.
Number);
893 for (
unsigned Number : Cand.ActiveBlocks) {
896 if (!RegIn && !RegOut)
898 if (RegIn && RegOut) {
900 Cand.Intf.moveToBlock(
Number);
901 if (Cand.Intf.hasInterference()) {
929 const unsigned NumGlobalIntvs = LREdit.
size();
932 assert(NumGlobalIntvs &&
"No global intervals configured");
944 unsigned IntvIn = 0, IntvOut = 0;
948 if (CandIn != NoCand) {
949 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
950 IntvIn = Cand.IntvIdx;
951 Cand.Intf.moveToBlock(
Number);
952 IntfIn = Cand.Intf.first();
957 if (CandOut != NoCand) {
958 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
959 IntvOut = Cand.IntvIdx;
960 Cand.Intf.moveToBlock(
Number);
961 IntfOut = Cand.Intf.last();
966 if (!IntvIn && !IntvOut) {
968 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
969 SE->splitSingleBlock(BI);
973 if (IntvIn && IntvOut)
974 SE->splitLiveThroughBlock(
Number, IntvIn, IntfIn, IntvOut, IntfOut);
976 SE->splitRegInBlock(BI, IntvIn, IntfIn);
978 SE->splitRegOutBlock(BI, IntvOut, IntfOut);
985 for (
unsigned UsedCand : UsedCands) {
992 unsigned IntvIn = 0, IntvOut = 0;
996 if (CandIn != NoCand) {
997 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
998 IntvIn = Cand.IntvIdx;
999 Cand.Intf.moveToBlock(
Number);
1000 IntfIn = Cand.Intf.first();
1004 if (CandOut != NoCand) {
1005 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1006 IntvOut = Cand.IntvIdx;
1007 Cand.Intf.moveToBlock(
Number);
1008 IntfOut = Cand.Intf.last();
1010 if (!IntvIn && !IntvOut)
1012 SE->splitLiveThroughBlock(
Number, IntvIn, IntfIn, IntvOut, IntfOut);
1019 SE->finish(&IntvMap);
1022 unsigned OrigBlocks = SA->getNumLiveBlocks();
1029 for (
unsigned I = 0, E = LREdit.
size();
I != E; ++
I) {
1033 if (ExtraInfo->getOrInitStage(
Reg.reg()) !=
RS_New)
1038 if (IntvMap[
I] == 0) {
1039 ExtraInfo->setStage(Reg,
RS_Spill);
1045 if (IntvMap[
I] < NumGlobalIntvs) {
1046 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1047 LLVM_DEBUG(
dbgs() <<
"Main interval covers the same " << OrigBlocks
1048 <<
" blocks as original.\n");
1060 MF->
verify(
this,
"After splitting live range around region", &
errs());
1068 unsigned NumCands = 0;
1073 bool HasCompact = calcCompactRegion(GlobalCand.
front());
1081 BestCost = SpillCost;
1086 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
1090 if (!HasCompact && BestCand == NoCand)
1093 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1097RAGreedy::calculateRegionSplitCostAroundReg(
MCPhysReg PhysReg,
1101 unsigned &BestCand) {
1105 unsigned WorstCount = ~0
u;
1107 for (
unsigned CandIndex = 0; CandIndex != NumCands; ++CandIndex) {
1108 if (CandIndex == BestCand || !GlobalCand[CandIndex].PhysReg)
1110 unsigned Count = GlobalCand[CandIndex].LiveBundles.count();
1111 if (Count < WorstCount) {
1117 GlobalCand[Worst] = GlobalCand[NumCands];
1118 if (BestCand == NumCands)
1122 if (GlobalCand.
size() <= NumCands)
1123 GlobalCand.
resize(NumCands+1);
1124 GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1125 Cand.reset(IntfCache, PhysReg);
1127 SpillPlacer->
prepare(Cand.LiveBundles);
1129 if (!addSplitConstraints(Cand.Intf,
Cost)) {
1135 if (
Cost >= BestCost) {
1137 if (BestCand == NoCand)
1138 dbgs() <<
" worse than no bundles\n";
1140 dbgs() <<
" worse than "
1141 <<
printReg(GlobalCand[BestCand].PhysReg,
TRI) <<
'\n';
1145 if (!growRegion(Cand)) {
1153 if (!Cand.LiveBundles.any()) {
1158 Cost += calcGlobalSplitCost(Cand, Order);
1161 for (
int I : Cand.LiveBundles.set_bits())
1162 dbgs() <<
" EB#" <<
I;
1165 if (
Cost < BestCost) {
1166 BestCand = NumCands;
1174unsigned RAGreedy::calculateRegionSplitCost(
const LiveInterval &VirtReg,
1179 unsigned BestCand = NoCand;
1182 if (IgnoreCSR && EvictAdvisor->isUnusedCalleeSavedReg(PhysReg))
1185 calculateRegionSplitCostAroundReg(PhysReg, Order, BestCost, NumCands,
1192unsigned RAGreedy::doRegionSplit(
const LiveInterval &VirtReg,
unsigned BestCand,
1204 if (BestCand != NoCand) {
1205 GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1206 if (
unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1208 Cand.IntvIdx = SE->openIntv();
1210 <<
B <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1217 GlobalSplitCandidate &Cand = GlobalCand.
front();
1218 assert(!Cand.PhysReg &&
"Compact region has no physreg");
1219 if (
unsigned B = Cand.getBundles(BundleCand, 0)) {
1221 Cand.IntvIdx = SE->openIntv();
1223 <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1228 splitAroundRegion(LREdit, UsedCands);
1234bool RAGreedy::trySplitAroundHintReg(
MCPhysReg Hint,
1245 if (ExtraInfo->getStage(VirtReg) >=
RS_Split2)
1258 if (OtherReg == Reg) {
1259 OtherReg =
Instr.getOperand(0).getReg();
1260 if (OtherReg == Reg)
1268 if (OtherPhysReg == Hint)
1278 unsigned NumCands = 0;
1279 unsigned BestCand = NoCand;
1280 SA->analyze(&VirtReg);
1281 calculateRegionSplitCostAroundReg(Hint, Order,
Cost, NumCands, BestCand);
1282 if (BestCand == NoCand)
1285 doRegionSplit(VirtReg, BestCand,
false, NewVRegs);
1296unsigned RAGreedy::tryBlockSplit(
const LiveInterval &VirtReg,
1299 assert(&SA->getParent() == &VirtReg &&
"Live range wasn't analyzed");
1306 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1307 SE->splitSingleBlock(BI);
1315 SE->finish(&IntvMap);
1322 for (
unsigned I = 0, E = LREdit.
size();
I != E; ++
I) {
1324 if (ExtraInfo->getOrInitStage(LI.
reg()) ==
RS_New && IntvMap[
I] == 0)
1329 MF->
verify(
this,
"After splitting live range around basic blocks", &
errs());
1343 assert(SuperRC &&
"Invalid register class");
1346 MI->getRegClassConstraintEffectForVReg(Reg, SuperRC,
TII,
TRI,
1361 for (
auto [
MI, OpIdx] : Ops) {
1374 Mask |= ~SubRegMask;
1391 auto DestSrc =
TII->isCopyInstr(*
MI);
1392 if (DestSrc && !
MI->isBundled() &&
1393 DestSrc->Destination->getSubReg() == DestSrc->Source->getSubReg())
1402 LiveAtMask |= S.LaneMask;
1417unsigned RAGreedy::tryInstructionSplit(
const LiveInterval &VirtReg,
1423 bool SplitSubClass =
true;
1427 SplitSubClass =
false;
1436 if (
Uses.size() <= 1)
1440 <<
" individual instrs.\n");
1444 unsigned SuperRCNumAllocatableRegs =
1454 SuperRCNumAllocatableRegs ==
1467 SE->useIntv(SegStart, SegStop);
1470 if (LREdit.
empty()) {
1476 SE->finish(&IntvMap);
1492void RAGreedy::calcGapWeights(
MCRegister PhysReg,
1494 assert(SA->getUseBlocks().size() == 1 &&
"Not a local interval");
1497 const unsigned NumGaps =
Uses.size()-1;
1505 GapWeight.
assign(NumGaps, 0.0f);
1522 for (
unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1524 while (
Uses[Gap+1].getBoundaryIndex() < IntI.start())
1525 if (++Gap == NumGaps)
1531 const float weight = IntI.value()->weight();
1532 for (; Gap != NumGaps; ++Gap) {
1533 GapWeight[Gap] = std::max(GapWeight[Gap], weight);
1534 if (
Uses[Gap+1].getBaseIndex() >= IntI.stop())
1549 for (
unsigned Gap = 0;
I != E &&
I->start < StopIdx; ++
I) {
1550 while (
Uses[Gap+1].getBoundaryIndex() <
I->start)
1551 if (++Gap == NumGaps)
1556 for (; Gap != NumGaps; ++Gap) {
1558 if (
Uses[Gap+1].getBaseIndex() >=
I->end)
1570unsigned RAGreedy::tryLocalSplit(
const LiveInterval &VirtReg,
1575 if (SA->getUseBlocks().size() != 1)
1588 if (
Uses.size() <= 2)
1590 const unsigned NumGaps =
Uses.size()-1;
1593 dbgs() <<
"tryLocalSplit: ";
1609 unsigned RE = RMS.
size();
1610 for (
unsigned I = 0;
I != NumGaps && RI != RE; ++
I) {
1621 RegMaskGaps.push_back(
I);
1648 bool ProgressRequired = ExtraInfo->getStage(VirtReg) >=
RS_Split2;
1651 unsigned BestBefore = NumGaps;
1652 unsigned BestAfter = 0;
1655 const float blockFreq =
1664 calcGapWeights(PhysReg, GapWeight);
1668 for (
unsigned Gap : RegMaskGaps)
1675 unsigned SplitBefore = 0, SplitAfter = 1;
1679 float MaxGap = GapWeight[0];
1683 const bool LiveBefore = SplitBefore != 0 || BI.
LiveIn;
1684 const bool LiveAfter = SplitAfter != NumGaps || BI.
LiveOut;
1687 <<
'-' <<
Uses[SplitAfter] <<
" I=" << MaxGap);
1690 if (!LiveBefore && !LiveAfter) {
1698 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
1701 bool Legal = !ProgressRequired || NewGaps < NumGaps;
1710 blockFreq * (NewGaps + 1),
1711 Uses[SplitBefore].distance(
Uses[SplitAfter]) +
1719 float Diff = EstWeight - MaxGap;
1720 if (Diff > BestDiff) {
1723 BestBefore = SplitBefore;
1724 BestAfter = SplitAfter;
1731 if (++SplitBefore < SplitAfter) {
1734 if (GapWeight[SplitBefore - 1] >= MaxGap) {
1735 MaxGap = GapWeight[SplitBefore];
1736 for (
unsigned I = SplitBefore + 1;
I != SplitAfter; ++
I)
1737 MaxGap = std::max(MaxGap, GapWeight[
I]);
1745 if (SplitAfter >= NumGaps) {
1751 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
1756 if (BestBefore == NumGaps)
1760 <<
Uses[BestAfter] <<
", " << BestDiff <<
", "
1761 << (BestAfter - BestBefore + 1) <<
" instrs\n");
1769 SE->useIntv(SegStart, SegStop);
1771 SE->finish(&IntvMap);
1776 bool LiveBefore = BestBefore != 0 || BI.
LiveIn;
1777 bool LiveAfter = BestAfter != NumGaps || BI.
LiveOut;
1778 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1779 if (NewGaps >= NumGaps) {
1781 assert(!ProgressRequired &&
"Didn't make progress when it was required.");
1782 for (
unsigned I = 0, E = IntvMap.
size();
I != E; ++
I)
1783 if (IntvMap[
I] == 1) {
1805 if (ExtraInfo->getStage(VirtReg) >=
RS_Spill)
1812 SA->analyze(&VirtReg);
1813 Register PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
1814 if (PhysReg || !NewVRegs.
empty())
1816 return tryInstructionSplit(VirtReg, Order, NewVRegs);
1822 SA->analyze(&VirtReg);
1827 if (ExtraInfo->getStage(VirtReg) <
RS_Split2) {
1828 MCRegister PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1829 if (PhysReg || !NewVRegs.
empty())
1834 return tryBlockSplit(VirtReg, Order, NewVRegs);
1857 if (PhysReg == AssignedReg)
1870bool RAGreedy::mayRecolorAllInterferences(
1872 SmallLISet &RecoloringCandidates,
const SmallVirtRegSet &FixedRegisters) {
1883 CutOffInfo |= CO_Interf;
1898 if (((ExtraInfo->getStage(*Intf) ==
RS_Done &&
1903 FixedRegisters.
count(Intf->reg())) {
1905 dbgs() <<
"Early abort: the interference is not recolorable.\n");
1908 RecoloringCandidates.insert(Intf);
1957unsigned RAGreedy::tryLastChanceRecoloring(
const LiveInterval &VirtReg,
1961 RecoloringStack &RecolorStack,
1966 LLVM_DEBUG(
dbgs() <<
"Try last chance recoloring for " << VirtReg <<
'\n');
1968 const ssize_t EntryStackSize = RecolorStack.size();
1972 "Last chance recoloring should really be last chance");
1978 LLVM_DEBUG(
dbgs() <<
"Abort because max depth has been reached.\n");
1979 CutOffInfo |= CO_Depth;
1984 SmallLISet RecoloringCandidates;
1996 RecoloringCandidates.clear();
1997 CurrentNewVRegs.
clear();
2003 dbgs() <<
"Some interferences are not with virtual registers.\n");
2010 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
2012 LLVM_DEBUG(
dbgs() <<
"Some interferences cannot be recolored.\n");
2019 PQueue RecoloringQueue;
2022 enqueue(RecoloringQueue, RC);
2024 "Interferences are supposed to be with allocated variables");
2027 RecolorStack.push_back(std::make_pair(RC,
VRM->
getPhys(ItVirtReg)));
2045 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
2046 FixedRegisters, RecolorStack,
Depth)) {
2048 for (
Register NewVReg : CurrentNewVRegs)
2058 LLVM_DEBUG(
dbgs() <<
"tryRecoloringCandidates deleted a fixed register "
2060 FixedRegisters.
erase(ThisVirtReg);
2068 FixedRegisters = SaveFixedRegisters;
2075 for (
Register R : CurrentNewVRegs) {
2087 for (ssize_t
I = RecolorStack.size() - 1;
I >= EntryStackSize; --
I) {
2090 std::tie(LI, PhysReg) = RecolorStack[
I];
2096 for (
size_t I = EntryStackSize;
I != RecolorStack.size(); ++
I) {
2099 std::tie(LI, PhysReg) = RecolorStack[
I];
2105 RecolorStack.resize(EntryStackSize);
2120bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2123 RecoloringStack &RecolorStack,
2125 while (!RecoloringQueue.empty()) {
2128 MCRegister PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters,
2129 RecolorStack,
Depth + 1);
2134 if (PhysReg == ~0u || (!PhysReg && !LI->
empty()))
2138 assert(LI->
empty() &&
"Only empty live-range do not require a register");
2140 <<
" succeeded. Empty LI.\n");
2144 <<
" succeeded with: " <<
printReg(PhysReg,
TRI) <<
'\n');
2158 CutOffInfo = CO_None;
2163 selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters, RecolorStack);
2164 if (Reg == ~0U && (CutOffInfo != CO_None)) {
2165 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2166 if (CutOffEncountered == CO_Depth)
2167 Ctx.
emitError(
"register allocation failed: maximum depth for recoloring "
2168 "reached. Use -fexhaustive-register-search to skip "
2170 else if (CutOffEncountered == CO_Interf)
2171 Ctx.
emitError(
"register allocation failed: maximum interference for "
2172 "recoloring reached. Use -fexhaustive-register-search "
2174 else if (CutOffEncountered == (CO_Depth | CO_Interf))
2175 Ctx.
emitError(
"register allocation failed: maximum interference and "
2176 "depth for recoloring reached. Use "
2177 "-fexhaustive-register-search to skip cutoffs");
2194 SA->analyze(&VirtReg);
2195 if (calcSpillCost() >= CSRCost)
2200 CostPerUseLimit = 1;
2203 if (ExtraInfo->getStage(VirtReg) <
RS_Split) {
2206 SA->analyze(&VirtReg);
2207 unsigned NumCands = 0;
2209 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2211 if (BestCand == NoCand)
2216 doRegionSplit(VirtReg, BestCand,
false, NewVRegs);
2224 SetOfBrokenHints.remove(&LI);
2227void RAGreedy::initializeCSRCost() {
2242 if (ActualEntry < FixedEntry)
2244 else if (ActualEntry <= UINT32_MAX)
2256void RAGreedy::collectHintInfo(
Register Reg, HintsInfo &Out) {
2262 if (OtherReg == Reg) {
2263 OtherReg =
Instr.getOperand(1).getReg();
2264 if (OtherReg == Reg)
2282 for (
const HintInfo &Info :
List) {
2283 if (
Info.PhysReg != PhysReg)
2297void RAGreedy::tryHintRecoloring(
const LiveInterval &VirtReg) {
2318 if (
Reg.isPhysical())
2324 "We have an unallocated variable which should have been handled");
2339 <<
") is recolorable.\n");
2343 collectHintInfo(Reg, Info);
2346 if (CurrPhys != PhysReg) {
2348 BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);
2353 if (OldCopiesCost < NewCopiesCost) {
2367 for (
const HintInfo &HI : Info) {
2371 }
while (!RecoloringCandidates.
empty());
2410void RAGreedy::tryHintsRecoloring() {
2413 "Recoloring is possible only for virtual registers");
2418 tryHintRecoloring(*LI);
2425 RecoloringStack &RecolorStack,
2432 tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {
2437 EvictAdvisor->isUnusedCalleeSavedReg(PhysReg) && NewVRegs.
empty()) {
2438 MCRegister CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
2439 CostPerUseLimit, NewVRegs);
2440 if (CSRReg || !NewVRegs.
empty())
2448 if (!NewVRegs.
empty())
2453 << ExtraInfo->getCascade(VirtReg.
reg()) <<
'\n');
2460 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,
2468 if (Hint && Hint != PhysReg)
2469 SetOfBrokenHints.insert(&VirtReg);
2473 assert((NewVRegs.
empty() ||
Depth) &&
"Cannot append to existing NewVRegs");
2479 ExtraInfo->setStage(VirtReg,
RS_Split);
2487 unsigned NewVRegSizeBefore = NewVRegs.
size();
2488 Register PhysReg = trySplit(VirtReg, Order, NewVRegs, FixedRegisters);
2489 if (PhysReg || (NewVRegs.
size() - NewVRegSizeBefore))
2496 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
2497 RecolorStack,
Depth);
2503 ExtraInfo->getStage(VirtReg) <
RS_Memory) {
2508 ExtraInfo->setStage(VirtReg,
RS_Memory);
2536 using namespace ore;
2538 R <<
NV(
"NumSpills", Spills) <<
" spills ";
2539 R <<
NV(
"TotalSpillsCost", SpillsCost) <<
" total spills cost ";
2542 R <<
NV(
"NumFoldedSpills", FoldedSpills) <<
" folded spills ";
2543 R <<
NV(
"TotalFoldedSpillsCost", FoldedSpillsCost)
2544 <<
" total folded spills cost ";
2547 R <<
NV(
"NumReloads", Reloads) <<
" reloads ";
2548 R <<
NV(
"TotalReloadsCost", ReloadsCost) <<
" total reloads cost ";
2550 if (FoldedReloads) {
2551 R <<
NV(
"NumFoldedReloads", FoldedReloads) <<
" folded reloads ";
2552 R <<
NV(
"TotalFoldedReloadsCost", FoldedReloadsCost)
2553 <<
" total folded reloads cost ";
2555 if (ZeroCostFoldedReloads)
2556 R <<
NV(
"NumZeroCostFoldedReloads", ZeroCostFoldedReloads)
2557 <<
" zero cost folded reloads ";
2559 R <<
NV(
"NumVRCopies",
Copies) <<
" virtual registers copies ";
2560 R <<
NV(
"TotalCopiesCost", CopiesCost) <<
" total copies cost ";
2565 RAGreedyStats
Stats;
2571 A->getPseudoValue())->getFrameIndex());
2574 return MI.getOpcode() == TargetOpcode::PATCHPOINT ||
2575 MI.getOpcode() == TargetOpcode::STACKMAP ||
2576 MI.getOpcode() == TargetOpcode::STATEPOINT;
2589 if (SrcReg && Src.getSubReg())
2597 if (SrcReg != DestReg)
2614 if (!isPatchpointInstr(
MI)) {
2619 std::pair<unsigned, unsigned> NonZeroCostRange =
2623 for (
unsigned Idx = 0, E =
MI.getNumOperands();
Idx < E; ++
Idx) {
2627 if (
Idx >= NonZeroCostRange.first &&
Idx < NonZeroCostRange.second)
2633 for (
unsigned Slot : FoldedReloads)
2634 ZeroCostFoldedReloads.
erase(Slot);
2635 Stats.FoldedReloads += FoldedReloads.size();
2636 Stats.ZeroCostFoldedReloads += ZeroCostFoldedReloads.
size();
2649 Stats.FoldedReloadsCost = RelFreq *
Stats.FoldedReloads;
2651 Stats.FoldedSpillsCost = RelFreq *
Stats.FoldedSpills;
2656RAGreedy::RAGreedyStats RAGreedy::reportStats(
MachineLoop *L) {
2657 RAGreedyStats
Stats;
2661 Stats.add(reportStats(SubLoop));
2668 if (!
Stats.isEmpty()) {
2669 using namespace ore;
2673 L->getStartLoc(),
L->getHeader());
2675 R <<
"generated in loop";
2682void RAGreedy::reportStats() {
2685 RAGreedyStats
Stats;
2687 Stats.add(reportStats(L));
2692 if (!
Stats.isEmpty()) {
2693 using namespace ore;
2697 if (
auto *SP = MF->getFunction().getSubprogram())
2702 R <<
"generated in function";
2708bool RAGreedy::hasVirtRegAlloc() {
2724 LLVM_DEBUG(
dbgs() <<
"********** GREEDY REGISTER ALLOCATION **********\n"
2725 <<
"********** Function: " << mf.
getName() <<
'\n');
2728 TII = MF->getSubtarget().getInstrInfo();
2731 MF->verify(
this,
"Before greedy register allocator", &
errs());
2734 getAnalysis<LiveIntervalsWrapperPass>().getLIS(),
2735 getAnalysis<LiveRegMatrixWrapperLegacy>().getLRM());
2739 if (!hasVirtRegAlloc())
2742 Indexes = &getAnalysis<SlotIndexesWrapperPass>().getSI();
2746 MBFI = &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
2747 DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
2748 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
2749 Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
2750 Bundles = &getAnalysis<EdgeBundlesWrapperLegacy>().getEdgeBundles();
2751 SpillPlacer = &getAnalysis<SpillPlacementWrapperLegacy>().getResult();
2752 DebugVars = &getAnalysis<LiveDebugVariablesWrapperLegacy>().getLDV();
2754 initializeCSRCost();
2757 RegClassPriorityTrumpsGlobalness =
2766 ExtraInfo.emplace();
2768 getAnalysis<RegAllocEvictionAdvisorAnalysis>().getAdvisor(*MF, *
this);
2770 getAnalysis<RegAllocPriorityAdvisorAnalysis>().getAdvisor(*MF, *
this);
2772 VRAI = std::make_unique<VirtRegAuxInfo>(*MF, *
LIS, *
VRM, *
Loops, *MBFI);
2775 VRAI->calculateSpillWeightsAndHints();
2784 SetOfBrokenHints.clear();
2787 tryHintsRecoloring();
2790 MF->verify(
this,
"Before post optimization", &
errs());
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
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)
static cl::opt< unsigned > SplitThresholdForRegWithHint("split-threshold-for-reg-with-hint", cl::desc("The threshold for splitting a virtual register with a hint, in " "percentage"), cl::init(75), 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< 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)
Remove Loads Into Fake Uses
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(const Instruction *I, 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.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
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().
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...
Analysis pass which computes a MachineDominatorTree.
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...
bool verify(Pass *p=nullptr, const char *Banner=nullptr, raw_ostream *OS=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
bool isImplicitDef() const
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.
RAGreedy(const RegAllocFilterFunc F=nullptr)
void enqueueImpl(const LiveInterval *LI) override
enqueue - Add VirtReg to the priority queue of unassigned registers.
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
bool shouldAllocateRegister(Register Reg)
Get whether a given register should be allocated.
static bool VerifyEnabled
VerifyEnabled - True when -verify-regalloc is given.
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.
unsigned virtRegIndex() const
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.
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.
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.
@ InstrDist
The default distance between instructions as returned by distance().
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
int getNumOccurrences() const
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.
std::function< bool(const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, const Register Reg)> RegAllocFilterFunc
Filter function for register classes during regalloc.
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.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
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.
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.