80#define DEBUG_TYPE "regalloc"
82STATISTIC(NumGlobalSplits,
"Number of split global live ranges");
83STATISTIC(NumLocalSplits,
"Number of split local live ranges");
84STATISTIC(NumEvicted,
"Number of interferences evicted");
88 cl::desc(
"Spill mode for splitting live ranges"),
96 cl::desc(
"Last chance recoloring max depth"),
101 cl::desc(
"Last chance recoloring maximum number of considered"
102 " interference at a time"),
107 cl::desc(
"Exhaustive Search for registers bypassing the depth "
108 "and interference cutoffs of last chance recoloring"),
113 cl::desc(
"Instead of spilling a variable right away, defer the actual "
114 "code insertion to the end of the allocation. That way the "
115 "allocator might still find a suitable coloring for this "
116 "variable because of other evicted variables."),
122 cl::desc(
"Cost for first time use of callee-saved register."),
126 "grow-region-complexity-budget",
127 cl::desc(
"growRegion() does not scale with the number of BB edges, so "
128 "limit its budget and bail out once we reach the limit."),
132 "greedy-regclass-priority-trumps-globalness",
133 cl::desc(
"Change the greedy register allocator's live range priority "
134 "calculation to make the AllocationPriority of the register class "
135 "more important then whether the range is global"),
139 "greedy-reverse-local-assignment",
140 cl::desc(
"Reverse allocation order of local live ranges, such that "
141 "shorter local live ranges will tend to be allocated first"),
151 "Greedy Register Allocator",
false,
false)
171const 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)
382 if (CurQueue.empty())
399 for (
auto I = Order.
begin(),
E = Order.
end();
I !=
E && !PhysReg; ++
I) {
420 if (EvictAdvisor->canEvictHintInterference(VirtReg, PhysHint,
422 evictInterference(VirtReg, PhysHint, NewVRegs);
427 SetOfBrokenHints.insert(&VirtReg);
431 uint8_t
Cost = RegCosts[PhysReg];
438 << (
unsigned)Cost <<
'\n');
439 MCRegister CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost, FixedRegisters);
440 return CheapReg ? CheapReg : PhysReg;
452 for (
auto I = Order.
begin(),
E = Order.
end();
I !=
E && !PhysReg; ++
I) {
453 if ((*I).id() == PrevReg.
id())
457 for (; Units.
isValid(); ++Units) {
477void RAGreedy::evictInterference(
const LiveInterval &VirtReg,
483 unsigned Cascade = ExtraInfo->getOrAssignNewCascade(VirtReg.
reg());
486 <<
" interference: Cascade " << Cascade <<
'\n');
507 assert((ExtraInfo->getCascade(Intf->reg()) < Cascade ||
509 "Cannot decrease cascade number, illegal eviction");
510 ExtraInfo->setCascade(Intf->reg(), Cascade);
526std::optional<unsigned>
529 unsigned CostPerUseLimit)
const {
530 unsigned OrderLimit = Order.
getOrder().size();
532 if (CostPerUseLimit < uint8_t(~0u)) {
536 if (MinCost >= CostPerUseLimit) {
538 << MinCost <<
", no cheaper registers to be found.\n");
544 if (RegCosts[Order.
getOrder().back()] >= CostPerUseLimit) {
555 if (RegCosts[PhysReg] >= CostPerUseLimit)
559 if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {
576 uint8_t CostPerUseLimit,
581 MCRegister BestPhys = EvictAdvisor->tryFindEvictionCandidate(
582 VirtReg, Order, CostPerUseLimit, FixedRegisters);
584 evictInterference(VirtReg, BestPhys, NewVRegs);
602 SplitConstraints.resize(UseBlocks.
size());
604 for (
unsigned I = 0;
I != UseBlocks.
size(); ++
I) {
639 SA->getFirstSplitPoint(BC.
Number)))
645 if (Intf.
last() >= SA->getLastSplitPoint(BC.
Number)) {
672 const unsigned GroupSize = 8;
674 unsigned TBS[GroupSize];
675 unsigned B = 0,
T = 0;
677 for (
unsigned Number : Blocks) {
681 assert(
T < GroupSize &&
"Array overflow");
683 if (++
T == GroupSize) {
690 assert(
B < GroupSize &&
"Array overflow");
696 if (FirstNonDebugInstr !=
MBB->
end() &&
698 SA->getFirstSplitPoint(
Number)))
707 if (Intf.
last() >= SA->getLastSplitPoint(
Number))
712 if (++
B == GroupSize) {
723bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
727 unsigned AddedTo = 0;
729 unsigned Visited = 0;
736 for (
unsigned Bundle : NewBundles) {
740 if (Blocks.
size() >= Budget)
742 Budget -= Blocks.
size();
743 for (
unsigned Block : Blocks) {
755 if (ActiveBlocks.
size() == AddedTo)
762 if (!addThroughConstraints(Cand.Intf, NewBlocks))
768 AddedTo = ActiveBlocks.
size();
784bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
786 if (!SA->getNumThroughBlocks())
796 SpillPlacer->
prepare(Cand.LiveBundles);
800 if (!addSplitConstraints(Cand.Intf, Cost)) {
805 if (!growRegion(Cand)) {
812 if (!Cand.LiveBundles.any()) {
818 for (
int I : Cand.LiveBundles.set_bits())
819 dbgs() <<
" EB#" <<
I;
846BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
849 const BitVector &LiveBundles = Cand.LiveBundles;
851 for (
unsigned I = 0;
I != UseBlocks.
size(); ++
I) {
858 Cand.Intf.moveToBlock(BC.
Number);
868 for (
unsigned Number : Cand.ActiveBlocks) {
871 if (!RegIn && !RegOut)
873 if (RegIn && RegOut) {
875 Cand.Intf.moveToBlock(
Number);
876 if (Cand.Intf.hasInterference()) {
904 const unsigned NumGlobalIntvs = LREdit.
size();
907 assert(NumGlobalIntvs &&
"No global intervals configured");
919 unsigned IntvIn = 0, IntvOut = 0;
923 if (CandIn != NoCand) {
924 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
925 IntvIn = Cand.IntvIdx;
926 Cand.Intf.moveToBlock(
Number);
927 IntfIn = Cand.Intf.first();
932 if (CandOut != NoCand) {
933 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
934 IntvOut = Cand.IntvIdx;
935 Cand.Intf.moveToBlock(
Number);
936 IntfOut = Cand.Intf.last();
941 if (!IntvIn && !IntvOut) {
943 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
944 SE->splitSingleBlock(BI);
948 if (IntvIn && IntvOut)
949 SE->splitLiveThroughBlock(
Number, IntvIn, IntfIn, IntvOut, IntfOut);
951 SE->splitRegInBlock(BI, IntvIn, IntfIn);
953 SE->splitRegOutBlock(BI, IntvOut, IntfOut);
960 for (
unsigned UsedCand : UsedCands) {
962 for (
unsigned Number : Blocks) {
967 unsigned IntvIn = 0, IntvOut = 0;
971 if (CandIn != NoCand) {
972 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
973 IntvIn = Cand.IntvIdx;
974 Cand.Intf.moveToBlock(
Number);
975 IntfIn = Cand.Intf.first();
979 if (CandOut != NoCand) {
980 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
981 IntvOut = Cand.IntvIdx;
982 Cand.Intf.moveToBlock(
Number);
983 IntfOut = Cand.Intf.last();
985 if (!IntvIn && !IntvOut)
987 SE->splitLiveThroughBlock(
Number, IntvIn, IntfIn, IntvOut, IntfOut);
994 SE->finish(&IntvMap);
997 unsigned OrigBlocks = SA->getNumLiveBlocks();
1004 for (
unsigned I = 0,
E = LREdit.
size();
I !=
E; ++
I) {
1008 if (ExtraInfo->getOrInitStage(
Reg.reg()) !=
RS_New)
1013 if (IntvMap[
I] == 0) {
1014 ExtraInfo->setStage(Reg,
RS_Spill);
1020 if (IntvMap[
I] < NumGlobalIntvs) {
1021 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1022 LLVM_DEBUG(
dbgs() <<
"Main interval covers the same " << OrigBlocks
1023 <<
" blocks as original.\n");
1035 MF->
verify(
this,
"After splitting live range around region");
1043 unsigned NumCands = 0;
1048 bool HasCompact = calcCompactRegion(GlobalCand.
front());
1056 BestCost = SpillCost;
1061 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
1065 if (!HasCompact && BestCand == NoCand)
1068 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1071unsigned RAGreedy::calculateRegionSplitCost(
const LiveInterval &VirtReg,
1076 unsigned BestCand = NoCand;
1079 if (IgnoreCSR && EvictAdvisor->isUnusedCalleeSavedReg(PhysReg))
1085 unsigned WorstCount = ~0
u;
1087 for (
unsigned CandIndex = 0; CandIndex != NumCands; ++CandIndex) {
1088 if (CandIndex == BestCand || !GlobalCand[CandIndex].PhysReg)
1090 unsigned Count = GlobalCand[CandIndex].LiveBundles.count();
1091 if (Count < WorstCount) {
1097 GlobalCand[Worst] = GlobalCand[NumCands];
1098 if (BestCand == NumCands)
1102 if (GlobalCand.
size() <= NumCands)
1103 GlobalCand.
resize(NumCands+1);
1104 GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1105 Cand.reset(IntfCache, PhysReg);
1107 SpillPlacer->
prepare(Cand.LiveBundles);
1109 if (!addSplitConstraints(Cand.Intf, Cost)) {
1115 if (Cost >= BestCost) {
1117 if (BestCand == NoCand)
1118 dbgs() <<
" worse than no bundles\n";
1120 dbgs() <<
" worse than "
1121 <<
printReg(GlobalCand[BestCand].PhysReg,
TRI) <<
'\n';
1125 if (!growRegion(Cand)) {
1133 if (!Cand.LiveBundles.any()) {
1138 Cost += calcGlobalSplitCost(Cand, Order);
1140 dbgs() <<
", total = ";
1142 for (
int I : Cand.LiveBundles.set_bits())
1143 dbgs() <<
" EB#" <<
I;
1146 if (Cost < BestCost) {
1147 BestCand = NumCands;
1156unsigned RAGreedy::doRegionSplit(
const LiveInterval &VirtReg,
unsigned BestCand,
1168 if (BestCand != NoCand) {
1169 GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1170 if (
unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1172 Cand.IntvIdx = SE->openIntv();
1174 <<
B <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1181 GlobalSplitCandidate &Cand = GlobalCand.
front();
1182 assert(!Cand.PhysReg &&
"Compact region has no physreg");
1183 if (
unsigned B = Cand.getBundles(BundleCand, 0)) {
1185 Cand.IntvIdx = SE->openIntv();
1187 <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1192 splitAroundRegion(LREdit, UsedCands);
1203unsigned RAGreedy::tryBlockSplit(
const LiveInterval &VirtReg,
1206 assert(&SA->getParent() == &VirtReg &&
"Live range wasn't analyzed");
1213 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1214 SE->splitSingleBlock(BI);
1222 SE->finish(&IntvMap);
1229 for (
unsigned I = 0,
E = LREdit.
size();
I !=
E; ++
I) {
1231 if (ExtraInfo->getOrInitStage(LI.
reg()) ==
RS_New && IntvMap[
I] == 0)
1236 MF->
verify(
this,
"After splitting live range around basic blocks");
1250 assert(SuperRC &&
"Invalid register class");
1253 MI->getRegClassConstraintEffectForVReg(Reg, SuperRC,
TII,
TRI,
1265 if (!MO.isReg() || MO.getReg() != Reg)
1268 unsigned SubReg = MO.getSubReg();
1269 if (
SubReg == 0 && MO.isUse()) {
1277 Mask |= ~SubRegMask;
1292 MI->getOperand(0).getSubReg() ==
MI->getOperand(1).getSubReg())
1301 LiveAtMask |= S.LaneMask;
1316unsigned RAGreedy::tryInstructionSplit(
const LiveInterval &VirtReg,
1322 bool SplitSubClass =
true;
1326 SplitSubClass =
false;
1335 if (
Uses.size() <= 1)
1339 <<
" individual instrs.\n");
1343 unsigned SuperRCNumAllocatableRegs =
1351 if (
MI->isFullCopy() ||
1353 SuperRCNumAllocatableRegs ==
1366 SE->useIntv(SegStart, SegStop);
1369 if (LREdit.
empty()) {
1375 SE->finish(&IntvMap);
1391void RAGreedy::calcGapWeights(
MCRegister PhysReg,
1393 assert(SA->getUseBlocks().size() == 1 &&
"Not a local interval");
1396 const unsigned NumGaps =
Uses.size()-1;
1404 GapWeight.
assign(NumGaps, 0.0f);
1421 for (
unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1423 while (
Uses[Gap+1].getBoundaryIndex() < IntI.start())
1424 if (++Gap == NumGaps)
1430 const float weight = IntI.value()->weight();
1431 for (; Gap != NumGaps; ++Gap) {
1432 GapWeight[Gap] = std::max(GapWeight[Gap], weight);
1433 if (
Uses[Gap+1].getBaseIndex() >= IntI.stop())
1448 for (
unsigned Gap = 0;
I !=
E &&
I->start < StopIdx; ++
I) {
1449 while (
Uses[Gap+1].getBoundaryIndex() <
I->start)
1450 if (++Gap == NumGaps)
1455 for (; Gap != NumGaps; ++Gap) {
1457 if (
Uses[Gap+1].getBaseIndex() >=
I->end)
1469unsigned RAGreedy::tryLocalSplit(
const LiveInterval &VirtReg,
1474 if (SA->getUseBlocks().size() != 1)
1487 if (
Uses.size() <= 2)
1489 const unsigned NumGaps =
Uses.size()-1;
1492 dbgs() <<
"tryLocalSplit: ";
1508 unsigned RE = RMS.
size();
1509 for (
unsigned I = 0;
I != NumGaps && RI != RE; ++
I) {
1520 RegMaskGaps.push_back(
I);
1547 bool ProgressRequired = ExtraInfo->getStage(VirtReg) >=
RS_Split2;
1550 unsigned BestBefore = NumGaps;
1551 unsigned BestAfter = 0;
1554 const float blockFreq =
1563 calcGapWeights(PhysReg, GapWeight);
1567 for (
unsigned I = 0,
E = RegMaskGaps.size();
I !=
E; ++
I)
1574 unsigned SplitBefore = 0, SplitAfter = 1;
1578 float MaxGap = GapWeight[0];
1582 const bool LiveBefore = SplitBefore != 0 || BI.
LiveIn;
1583 const bool LiveAfter = SplitAfter != NumGaps || BI.
LiveOut;
1586 <<
'-' <<
Uses[SplitAfter] <<
" I=" << MaxGap);
1589 if (!LiveBefore && !LiveAfter) {
1597 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
1600 bool Legal = !ProgressRequired || NewGaps < NumGaps;
1609 blockFreq * (NewGaps + 1),
1610 Uses[SplitBefore].distance(
Uses[SplitAfter]) +
1618 float Diff = EstWeight - MaxGap;
1619 if (Diff > BestDiff) {
1622 BestBefore = SplitBefore;
1623 BestAfter = SplitAfter;
1630 if (++SplitBefore < SplitAfter) {
1633 if (GapWeight[SplitBefore - 1] >= MaxGap) {
1634 MaxGap = GapWeight[SplitBefore];
1635 for (
unsigned I = SplitBefore + 1;
I != SplitAfter; ++
I)
1636 MaxGap = std::max(MaxGap, GapWeight[
I]);
1644 if (SplitAfter >= NumGaps) {
1650 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
1655 if (BestBefore == NumGaps)
1659 <<
Uses[BestAfter] <<
", " << BestDiff <<
", "
1660 << (BestAfter - BestBefore + 1) <<
" instrs\n");
1668 SE->useIntv(SegStart, SegStop);
1670 SE->finish(&IntvMap);
1675 bool LiveBefore = BestBefore != 0 || BI.
LiveIn;
1676 bool LiveAfter = BestAfter != NumGaps || BI.
LiveOut;
1677 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1678 if (NewGaps >= NumGaps) {
1680 assert(!ProgressRequired &&
"Didn't make progress when it was required.");
1681 for (
unsigned I = 0,
E = IntvMap.
size();
I !=
E; ++
I)
1682 if (IntvMap[
I] == 1) {
1704 if (ExtraInfo->getStage(VirtReg) >=
RS_Spill)
1711 SA->analyze(&VirtReg);
1712 Register PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
1713 if (PhysReg || !NewVRegs.
empty())
1715 return tryInstructionSplit(VirtReg, Order, NewVRegs);
1721 SA->analyze(&VirtReg);
1726 if (ExtraInfo->getStage(VirtReg) <
RS_Split2) {
1727 MCRegister PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1728 if (PhysReg || !NewVRegs.
empty())
1733 return tryBlockSplit(VirtReg, Order, NewVRegs);
1756 if (PhysReg == AssignedReg)
1769bool RAGreedy::mayRecolorAllInterferences(
1771 SmallLISet &RecoloringCandidates,
const SmallVirtRegSet &FixedRegisters) {
1782 CutOffInfo |= CO_Interf;
1797 if (((ExtraInfo->getStage(*Intf) ==
RS_Done &&
1802 FixedRegisters.
count(Intf->reg())) {
1804 dbgs() <<
"Early abort: the interference is not recolorable.\n");
1807 RecoloringCandidates.insert(Intf);
1856unsigned RAGreedy::tryLastChanceRecoloring(
const LiveInterval &VirtReg,
1860 RecoloringStack &RecolorStack,
1865 LLVM_DEBUG(
dbgs() <<
"Try last chance recoloring for " << VirtReg <<
'\n');
1867 const ssize_t EntryStackSize = RecolorStack.size();
1871 "Last chance recoloring should really be last chance");
1877 LLVM_DEBUG(
dbgs() <<
"Abort because max depth has been reached.\n");
1878 CutOffInfo |= CO_Depth;
1883 SmallLISet RecoloringCandidates;
1895 RecoloringCandidates.clear();
1896 CurrentNewVRegs.
clear();
1902 dbgs() <<
"Some interferences are not with virtual registers.\n");
1909 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
1911 LLVM_DEBUG(
dbgs() <<
"Some interferences cannot be recolored.\n");
1918 PQueue RecoloringQueue;
1921 enqueue(RecoloringQueue, RC);
1923 "Interferences are supposed to be with allocated variables");
1926 RecolorStack.push_back(std::make_pair(RC,
VRM->
getPhys(ItVirtReg)));
1941 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
1942 FixedRegisters, RecolorStack,
Depth)) {
1944 for (
Register NewVReg : CurrentNewVRegs)
1956 FixedRegisters = SaveFixedRegisters;
1963 for (
Register R : CurrentNewVRegs) {
1975 for (ssize_t
I = RecolorStack.size() - 1;
I >= EntryStackSize; --
I) {
1978 std::tie(LI, PhysReg) = RecolorStack[
I];
1984 for (
size_t I = EntryStackSize;
I != RecolorStack.size(); ++
I) {
1987 std::tie(LI, PhysReg) = RecolorStack[
I];
1993 RecolorStack.resize(EntryStackSize);
2008bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2011 RecoloringStack &RecolorStack,
2013 while (!RecoloringQueue.empty()) {
2016 MCRegister PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters,
2017 RecolorStack,
Depth + 1);
2022 if (PhysReg == ~0u || (!PhysReg && !LI->
empty()))
2026 assert(LI->
empty() &&
"Only empty live-range do not require a register");
2028 <<
" succeeded. Empty LI.\n");
2032 <<
" succeeded with: " <<
printReg(PhysReg,
TRI) <<
'\n');
2046 CutOffInfo = CO_None;
2051 selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters, RecolorStack);
2052 if (Reg == ~0U && (CutOffInfo != CO_None)) {
2053 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2054 if (CutOffEncountered == CO_Depth)
2055 Ctx.
emitError(
"register allocation failed: maximum depth for recoloring "
2056 "reached. Use -fexhaustive-register-search to skip "
2058 else if (CutOffEncountered == CO_Interf)
2059 Ctx.
emitError(
"register allocation failed: maximum interference for "
2060 "recoloring reached. Use -fexhaustive-register-search "
2062 else if (CutOffEncountered == (CO_Depth | CO_Interf))
2063 Ctx.
emitError(
"register allocation failed: maximum interference and "
2064 "depth for recoloring reached. Use "
2065 "-fexhaustive-register-search to skip cutoffs");
2082 SA->analyze(&VirtReg);
2083 if (calcSpillCost() >= CSRCost)
2088 CostPerUseLimit = 1;
2091 if (ExtraInfo->getStage(VirtReg) <
RS_Split) {
2094 SA->analyze(&VirtReg);
2095 unsigned NumCands = 0;
2097 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2099 if (BestCand == NoCand)
2104 doRegionSplit(VirtReg, BestCand,
false, NewVRegs);
2112 SetOfBrokenHints.remove(&LI);
2115void RAGreedy::initializeCSRCost() {
2130 if (ActualEntry < FixedEntry)
2132 else if (ActualEntry <= UINT32_MAX)
2137 CSRCost = CSRCost.
getFrequency() * (ActualEntry / FixedEntry);
2143void RAGreedy::collectHintInfo(
Register Reg, HintsInfo &Out) {
2145 if (!Instr.isFullCopy())
2148 Register OtherReg = Instr.getOperand(0).getReg();
2149 if (OtherReg == Reg) {
2150 OtherReg = Instr.getOperand(1).getReg();
2151 if (OtherReg == Reg)
2158 Out.push_back(HintInfo(MBFI->
getBlockFreq(Instr.getParent()), OtherReg,
2169 for (
const HintInfo &Info :
List) {
2170 if (
Info.PhysReg != PhysReg)
2184void RAGreedy::tryHintRecoloring(
const LiveInterval &VirtReg) {
2205 if (
Reg.isPhysical())
2211 "We have an unallocated variable which should have been handled");
2226 <<
") is recolorable.\n");
2230 collectHintInfo(Reg, Info);
2233 if (CurrPhys != PhysReg) {
2235 BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);
2240 if (OldCopiesCost < NewCopiesCost) {
2254 for (
const HintInfo &HI : Info) {
2258 }
while (!RecoloringCandidates.
empty());
2297void RAGreedy::tryHintsRecoloring() {
2300 "Recoloring is possible only for virtual registers");
2305 tryHintRecoloring(*LI);
2312 RecoloringStack &RecolorStack,
2314 uint8_t CostPerUseLimit = uint8_t(~0u);
2319 tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {
2324 EvictAdvisor->isUnusedCalleeSavedReg(PhysReg) && NewVRegs.
empty()) {
2325 MCRegister CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
2326 CostPerUseLimit, NewVRegs);
2327 if (CSRReg || !NewVRegs.
empty())
2337 << ExtraInfo->getCascade(VirtReg.
reg()) <<
'\n');
2344 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,
2352 if (Hint && Hint != PhysReg)
2353 SetOfBrokenHints.insert(&VirtReg);
2357 assert((NewVRegs.
empty() ||
Depth) &&
"Cannot append to existing NewVRegs");
2363 ExtraInfo->setStage(VirtReg,
RS_Split);
2371 unsigned NewVRegSizeBefore = NewVRegs.
size();
2372 Register PhysReg = trySplit(VirtReg, Order, NewVRegs, FixedRegisters);
2373 if (PhysReg || (NewVRegs.
size() - NewVRegSizeBefore))
2380 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
2381 RecolorStack,
Depth);
2387 ExtraInfo->getStage(VirtReg) <
RS_Memory) {
2392 ExtraInfo->setStage(VirtReg,
RS_Memory);
2408 MF->
verify(
this,
"After spilling");
2417 using namespace ore;
2419 R <<
NV(
"NumSpills", Spills) <<
" spills ";
2420 R <<
NV(
"TotalSpillsCost", SpillsCost) <<
" total spills cost ";
2423 R <<
NV(
"NumFoldedSpills", FoldedSpills) <<
" folded spills ";
2424 R <<
NV(
"TotalFoldedSpillsCost", FoldedSpillsCost)
2425 <<
" total folded spills cost ";
2428 R <<
NV(
"NumReloads", Reloads) <<
" reloads ";
2429 R <<
NV(
"TotalReloadsCost", ReloadsCost) <<
" total reloads cost ";
2431 if (FoldedReloads) {
2432 R <<
NV(
"NumFoldedReloads", FoldedReloads) <<
" folded reloads ";
2433 R <<
NV(
"TotalFoldedReloadsCost", FoldedReloadsCost)
2434 <<
" total folded reloads cost ";
2436 if (ZeroCostFoldedReloads)
2437 R <<
NV(
"NumZeroCostFoldedReloads", ZeroCostFoldedReloads)
2438 <<
" zero cost folded reloads ";
2440 R <<
NV(
"NumVRCopies",
Copies) <<
" virtual registers copies ";
2441 R <<
NV(
"TotalCopiesCost", CopiesCost) <<
" total copies cost ";
2446 RAGreedyStats
Stats;
2452 A->getPseudoValue())->getFrameIndex());
2455 return MI.getOpcode() == TargetOpcode::PATCHPOINT ||
2456 MI.getOpcode() == TargetOpcode::STACKMAP ||
2457 MI.getOpcode() == TargetOpcode::STATEPOINT;
2469 if (Src.getSubReg())
2477 if (SrcReg != DestReg)
2494 if (!isPatchpointInstr(
MI)) {
2499 std::pair<unsigned, unsigned> NonZeroCostRange =
2503 for (
unsigned Idx = 0,
E =
MI.getNumOperands();
Idx <
E; ++
Idx) {
2507 if (
Idx >= NonZeroCostRange.first &&
Idx < NonZeroCostRange.second)
2513 for (
unsigned Slot : FoldedReloads)
2514 ZeroCostFoldedReloads.
erase(Slot);
2515 Stats.FoldedReloads += FoldedReloads.size();
2516 Stats.ZeroCostFoldedReloads += ZeroCostFoldedReloads.
size();
2529 Stats.FoldedReloadsCost = RelFreq *
Stats.FoldedReloads;
2531 Stats.FoldedSpillsCost = RelFreq *
Stats.FoldedSpills;
2536RAGreedy::RAGreedyStats RAGreedy::reportStats(
MachineLoop *L) {
2537 RAGreedyStats
Stats;
2541 Stats.add(reportStats(SubLoop));
2548 if (!
Stats.isEmpty()) {
2549 using namespace ore;
2553 L->getStartLoc(),
L->getHeader());
2555 R <<
"generated in loop";
2562void RAGreedy::reportStats() {
2565 RAGreedyStats
Stats;
2567 Stats.add(reportStats(L));
2572 if (!
Stats.isEmpty()) {
2573 using namespace ore;
2577 if (
auto *SP = MF->getFunction().getSubprogram())
2582 R <<
"generated in function";
2588bool RAGreedy::hasVirtRegAlloc() {
2604 LLVM_DEBUG(
dbgs() <<
"********** GREEDY REGISTER ALLOCATION **********\n"
2605 <<
"********** Function: " << mf.
getName() <<
'\n');
2608 TII = MF->getSubtarget().getInstrInfo();
2611 MF->verify(
this,
"Before greedy register allocator");
2614 getAnalysis<LiveIntervals>(),
2615 getAnalysis<LiveRegMatrix>());
2619 if (!hasVirtRegAlloc())
2622 Indexes = &getAnalysis<SlotIndexes>();
2623 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
2624 DomTree = &getAnalysis<MachineDominatorTree>();
2625 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
2626 Loops = &getAnalysis<MachineLoopInfo>();
2627 Bundles = &getAnalysis<EdgeBundles>();
2628 SpillPlacer = &getAnalysis<SpillPlacement>();
2629 DebugVars = &getAnalysis<LiveDebugVariables>();
2631 initializeCSRCost();
2634 RegClassPriorityTrumpsGlobalness =
2643 ExtraInfo.emplace();
2645 getAnalysis<RegAllocEvictionAdvisorAnalysis>().getAdvisor(*MF, *
this);
2647 getAnalysis<RegAllocPriorityAdvisorAnalysis>().getAdvisor(*MF, *
this);
2649 VRAI = std::make_unique<VirtRegAuxInfo>(*MF, *
LIS, *
VRM, *
Loops, *MBFI);
2652 VRAI->calculateSpillWeightsAndHints();
2661 SetOfBrokenHints.clear();
2664 tryHintsRecoloring();
2667 MF->verify(
this,
"Before post optimization");
SmallPtrSet< MachineInstr *, 2 > Uses
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")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
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 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 LaneBitmask getInstReadLaneMask(const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, const MachineInstr &MI, Register Reg)
static bool readsLaneSubset(const MachineRegisterInfo &MRI, const MachineInstr *MI, const LiveInterval &VirtReg, const TargetRegisterInfo *TRI, SlotIndex Use)
Return true if MI at \P Use reads a subset of the lanes live in VirtReg.
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)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
This file defines the SmallPtrSet class.
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
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
static uint64_t getMaxFrequency()
Returns the maximum possible frequency, the saturation value.
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.
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.
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.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Wrapper class representing physical registers. Should be passed by value.
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.
raw_ostream & printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const
uint64_t getEntryFreq() const
Divide a block's BlockFrequency::getFrequency() value by this value to obtain the entry block - relat...
float getBlockFreqRelativeToEntryBlock(const MachineBasicBlock *MBB) const
Compute the frequency of the block, relative to the entry block.
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
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 canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const
Register canReassign(const LiveInterval &VirtReg, Register PrevReg) 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.
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
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.
bool isVirtual() const
Return true if the specified register number is in the virtual 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.
@ InstrDist
The default distance between instructions as returned by distance().
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 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.
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 unsigned 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...
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...
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 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...
virtual unsigned 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...
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
This is an optimization pass for GlobalISel generic memory operations.
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.
@ 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.
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...
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.