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"),
145 "split-threshold-for-reg-with-hint",
146 cl::desc(
"The threshold for splitting a virtual register with a hint, in "
157 "Greedy Register Allocator",
false,
false)
177const char *
const RAGreedy::StageName[] = {
237bool RAGreedy::LRE_CanEraseVirtReg(
Register VirtReg) {
252void RAGreedy::LRE_WillShrinkVirtReg(
Register VirtReg) {
263 ExtraInfo->LRE_DidCloneVirtReg(New, Old);
268 if (!Info.inBounds(Old))
277 Info[New] = Info[Old];
281 SpillerInstance.reset();
287void RAGreedy::enqueue(PQueue &CurQueue,
const LiveInterval *LI) {
291 assert(Reg.isVirtual() &&
"Can only enqueue virtual registers");
293 auto Stage = ExtraInfo->getOrInitStage(Reg);
296 ExtraInfo->setStage(Reg, Stage);
299 unsigned Ret = PriorityAdvisor->getPriority(*LI);
303 CurQueue.push(std::make_pair(Ret, ~Reg));
306unsigned DefaultPriorityAdvisor::getPriority(
const LiveInterval &LI)
const {
321 static unsigned MemOp = 0;
328 (!ReverseLocalAssignment &&
331 unsigned GlobalBit = 0;
338 if (!ReverseLocalAssignment)
366 Prio = std::min(Prio, (
unsigned)
maxUIntN(24));
369 if (RegClassPriorityTrumpsGlobalness)
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);
442 uint8_t
Cost = RegCosts[PhysReg];
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)) {
583 uint8_t CostPerUseLimit,
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))
775 AddedTo = ActiveBlocks.
size();
791bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
793 if (!SA->getNumThroughBlocks())
803 SpillPlacer->
prepare(Cand.LiveBundles);
807 if (!addSplitConstraints(Cand.Intf,
Cost)) {
812 if (!growRegion(Cand)) {
819 if (!Cand.LiveBundles.any()) {
825 for (
int I : Cand.LiveBundles.set_bits())
826 dbgs() <<
" EB#" <<
I;
853BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
856 const BitVector &LiveBundles = Cand.LiveBundles;
858 for (
unsigned I = 0;
I != UseBlocks.
size(); ++
I) {
865 Cand.Intf.moveToBlock(BC.
Number);
875 for (
unsigned Number : Cand.ActiveBlocks) {
878 if (!RegIn && !RegOut)
880 if (RegIn && RegOut) {
882 Cand.Intf.moveToBlock(
Number);
883 if (Cand.Intf.hasInterference()) {
911 const unsigned NumGlobalIntvs = LREdit.
size();
914 assert(NumGlobalIntvs &&
"No global intervals configured");
926 unsigned IntvIn = 0, IntvOut = 0;
930 if (CandIn != NoCand) {
931 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
932 IntvIn = Cand.IntvIdx;
933 Cand.Intf.moveToBlock(
Number);
934 IntfIn = Cand.Intf.first();
939 if (CandOut != NoCand) {
940 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
941 IntvOut = Cand.IntvIdx;
942 Cand.Intf.moveToBlock(
Number);
943 IntfOut = Cand.Intf.last();
948 if (!IntvIn && !IntvOut) {
950 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
951 SE->splitSingleBlock(BI);
955 if (IntvIn && IntvOut)
956 SE->splitLiveThroughBlock(
Number, IntvIn, IntfIn, IntvOut, IntfOut);
958 SE->splitRegInBlock(BI, IntvIn, IntfIn);
960 SE->splitRegOutBlock(BI, IntvOut, IntfOut);
967 for (
unsigned UsedCand : UsedCands) {
974 unsigned IntvIn = 0, IntvOut = 0;
978 if (CandIn != NoCand) {
979 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
980 IntvIn = Cand.IntvIdx;
981 Cand.Intf.moveToBlock(
Number);
982 IntfIn = Cand.Intf.first();
986 if (CandOut != NoCand) {
987 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
988 IntvOut = Cand.IntvIdx;
989 Cand.Intf.moveToBlock(
Number);
990 IntfOut = Cand.Intf.last();
992 if (!IntvIn && !IntvOut)
994 SE->splitLiveThroughBlock(
Number, IntvIn, IntfIn, IntvOut, IntfOut);
1001 SE->finish(&IntvMap);
1004 unsigned OrigBlocks = SA->getNumLiveBlocks();
1011 for (
unsigned I = 0,
E = LREdit.
size();
I !=
E; ++
I) {
1015 if (ExtraInfo->getOrInitStage(
Reg.reg()) !=
RS_New)
1020 if (IntvMap[
I] == 0) {
1021 ExtraInfo->setStage(Reg,
RS_Spill);
1027 if (IntvMap[
I] < NumGlobalIntvs) {
1028 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1029 LLVM_DEBUG(
dbgs() <<
"Main interval covers the same " << OrigBlocks
1030 <<
" blocks as original.\n");
1042 MF->
verify(
this,
"After splitting live range around region");
1050 unsigned NumCands = 0;
1055 bool HasCompact = calcCompactRegion(GlobalCand.
front());
1063 BestCost = SpillCost;
1068 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
1072 if (!HasCompact && BestCand == NoCand)
1075 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1079RAGreedy::calculateRegionSplitCostAroundReg(
MCPhysReg PhysReg,
1083 unsigned &BestCand) {
1087 unsigned WorstCount = ~0
u;
1089 for (
unsigned CandIndex = 0; CandIndex != NumCands; ++CandIndex) {
1090 if (CandIndex == BestCand || !GlobalCand[CandIndex].PhysReg)
1092 unsigned Count = GlobalCand[CandIndex].LiveBundles.count();
1093 if (Count < WorstCount) {
1099 GlobalCand[Worst] = GlobalCand[NumCands];
1100 if (BestCand == NumCands)
1104 if (GlobalCand.
size() <= NumCands)
1105 GlobalCand.
resize(NumCands+1);
1106 GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1107 Cand.reset(IntfCache, PhysReg);
1109 SpillPlacer->
prepare(Cand.LiveBundles);
1111 if (!addSplitConstraints(Cand.Intf,
Cost)) {
1117 if (
Cost >= BestCost) {
1119 if (BestCand == NoCand)
1120 dbgs() <<
" worse than no bundles\n";
1122 dbgs() <<
" worse than "
1123 <<
printReg(GlobalCand[BestCand].PhysReg,
TRI) <<
'\n';
1127 if (!growRegion(Cand)) {
1135 if (!Cand.LiveBundles.any()) {
1140 Cost += calcGlobalSplitCost(Cand, Order);
1142 dbgs() <<
", total = ";
1144 for (
int I : Cand.LiveBundles.set_bits())
1145 dbgs() <<
" EB#" <<
I;
1148 if (
Cost < BestCost) {
1149 BestCand = NumCands;
1157unsigned RAGreedy::calculateRegionSplitCost(
const LiveInterval &VirtReg,
1162 unsigned BestCand = NoCand;
1165 if (IgnoreCSR && EvictAdvisor->isUnusedCalleeSavedReg(PhysReg))
1168 calculateRegionSplitCostAroundReg(PhysReg, Order, BestCost, NumCands,
1175unsigned RAGreedy::doRegionSplit(
const LiveInterval &VirtReg,
unsigned BestCand,
1187 if (BestCand != NoCand) {
1188 GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1189 if (
unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1191 Cand.IntvIdx = SE->openIntv();
1193 <<
B <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1200 GlobalSplitCandidate &Cand = GlobalCand.
front();
1201 assert(!Cand.PhysReg &&
"Compact region has no physreg");
1202 if (
unsigned B = Cand.getBundles(BundleCand, 0)) {
1204 Cand.IntvIdx = SE->openIntv();
1206 <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1211 splitAroundRegion(LREdit, UsedCands);
1217bool RAGreedy::trySplitAroundHintReg(
MCPhysReg Hint,
1231 if (OtherReg == Reg) {
1232 OtherReg =
Instr.getOperand(0).getReg();
1233 if (OtherReg == Reg)
1241 if (OtherPhysReg == Hint)
1251 unsigned NumCands = 0;
1252 unsigned BestCand = NoCand;
1253 SA->analyze(&VirtReg);
1254 calculateRegionSplitCostAroundReg(Hint, Order,
Cost, NumCands, BestCand);
1255 if (BestCand == NoCand)
1258 doRegionSplit(VirtReg, BestCand,
false, NewVRegs);
1269unsigned RAGreedy::tryBlockSplit(
const LiveInterval &VirtReg,
1272 assert(&SA->getParent() == &VirtReg &&
"Live range wasn't analyzed");
1279 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1280 SE->splitSingleBlock(BI);
1288 SE->finish(&IntvMap);
1295 for (
unsigned I = 0,
E = LREdit.
size();
I !=
E; ++
I) {
1297 if (ExtraInfo->getOrInitStage(LI.
reg()) ==
RS_New && IntvMap[
I] == 0)
1302 MF->
verify(
this,
"After splitting live range around basic blocks");
1316 assert(SuperRC &&
"Invalid register class");
1319 MI->getRegClassConstraintEffectForVReg(Reg, SuperRC,
TII,
TRI,
1331 if (!MO.isReg() || MO.getReg() != Reg)
1334 unsigned SubReg = MO.getSubReg();
1335 if (
SubReg == 0 && MO.isUse()) {
1343 Mask |= ~SubRegMask;
1358 auto DestSrc =
TII->isCopyInstr(*
MI);
1360 DestSrc->Destination->getSubReg() == DestSrc->Source->getSubReg())
1369 LiveAtMask |= S.LaneMask;
1384unsigned RAGreedy::tryInstructionSplit(
const LiveInterval &VirtReg,
1390 bool SplitSubClass =
true;
1394 SplitSubClass =
false;
1403 if (
Uses.size() <= 1)
1407 <<
" individual instrs.\n");
1411 unsigned SuperRCNumAllocatableRegs =
1421 SuperRCNumAllocatableRegs ==
1434 SE->useIntv(SegStart, SegStop);
1437 if (LREdit.
empty()) {
1443 SE->finish(&IntvMap);
1459void RAGreedy::calcGapWeights(
MCRegister PhysReg,
1461 assert(SA->getUseBlocks().size() == 1 &&
"Not a local interval");
1464 const unsigned NumGaps =
Uses.size()-1;
1472 GapWeight.
assign(NumGaps, 0.0f);
1489 for (
unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1491 while (
Uses[Gap+1].getBoundaryIndex() < IntI.start())
1492 if (++Gap == NumGaps)
1498 const float weight = IntI.value()->weight();
1499 for (; Gap != NumGaps; ++Gap) {
1500 GapWeight[Gap] = std::max(GapWeight[Gap], weight);
1501 if (
Uses[Gap+1].getBaseIndex() >= IntI.stop())
1516 for (
unsigned Gap = 0;
I !=
E &&
I->start < StopIdx; ++
I) {
1517 while (
Uses[Gap+1].getBoundaryIndex() <
I->start)
1518 if (++Gap == NumGaps)
1523 for (; Gap != NumGaps; ++Gap) {
1525 if (
Uses[Gap+1].getBaseIndex() >=
I->end)
1537unsigned RAGreedy::tryLocalSplit(
const LiveInterval &VirtReg,
1542 if (SA->getUseBlocks().size() != 1)
1555 if (
Uses.size() <= 2)
1557 const unsigned NumGaps =
Uses.size()-1;
1560 dbgs() <<
"tryLocalSplit: ";
1576 unsigned RE = RMS.
size();
1577 for (
unsigned I = 0;
I != NumGaps && RI != RE; ++
I) {
1588 RegMaskGaps.push_back(
I);
1615 bool ProgressRequired = ExtraInfo->getStage(VirtReg) >=
RS_Split2;
1618 unsigned BestBefore = NumGaps;
1619 unsigned BestAfter = 0;
1622 const float blockFreq =
1631 calcGapWeights(PhysReg, GapWeight);
1635 for (
unsigned I = 0,
E = RegMaskGaps.size();
I !=
E; ++
I)
1642 unsigned SplitBefore = 0, SplitAfter = 1;
1646 float MaxGap = GapWeight[0];
1650 const bool LiveBefore = SplitBefore != 0 || BI.
LiveIn;
1651 const bool LiveAfter = SplitAfter != NumGaps || BI.
LiveOut;
1654 <<
'-' <<
Uses[SplitAfter] <<
" I=" << MaxGap);
1657 if (!LiveBefore && !LiveAfter) {
1665 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
1668 bool Legal = !ProgressRequired || NewGaps < NumGaps;
1677 blockFreq * (NewGaps + 1),
1678 Uses[SplitBefore].distance(
Uses[SplitAfter]) +
1686 float Diff = EstWeight - MaxGap;
1687 if (Diff > BestDiff) {
1690 BestBefore = SplitBefore;
1691 BestAfter = SplitAfter;
1698 if (++SplitBefore < SplitAfter) {
1701 if (GapWeight[SplitBefore - 1] >= MaxGap) {
1702 MaxGap = GapWeight[SplitBefore];
1703 for (
unsigned I = SplitBefore + 1;
I != SplitAfter; ++
I)
1704 MaxGap = std::max(MaxGap, GapWeight[
I]);
1712 if (SplitAfter >= NumGaps) {
1718 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
1723 if (BestBefore == NumGaps)
1727 <<
Uses[BestAfter] <<
", " << BestDiff <<
", "
1728 << (BestAfter - BestBefore + 1) <<
" instrs\n");
1736 SE->useIntv(SegStart, SegStop);
1738 SE->finish(&IntvMap);
1743 bool LiveBefore = BestBefore != 0 || BI.
LiveIn;
1744 bool LiveAfter = BestAfter != NumGaps || BI.
LiveOut;
1745 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1746 if (NewGaps >= NumGaps) {
1748 assert(!ProgressRequired &&
"Didn't make progress when it was required.");
1749 for (
unsigned I = 0,
E = IntvMap.
size();
I !=
E; ++
I)
1750 if (IntvMap[
I] == 1) {
1772 if (ExtraInfo->getStage(VirtReg) >=
RS_Spill)
1779 SA->analyze(&VirtReg);
1780 Register PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
1781 if (PhysReg || !NewVRegs.
empty())
1783 return tryInstructionSplit(VirtReg, Order, NewVRegs);
1789 SA->analyze(&VirtReg);
1794 if (ExtraInfo->getStage(VirtReg) <
RS_Split2) {
1795 MCRegister PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1796 if (PhysReg || !NewVRegs.
empty())
1801 return tryBlockSplit(VirtReg, Order, NewVRegs);
1824 if (PhysReg == AssignedReg)
1837bool RAGreedy::mayRecolorAllInterferences(
1839 SmallLISet &RecoloringCandidates,
const SmallVirtRegSet &FixedRegisters) {
1850 CutOffInfo |= CO_Interf;
1865 if (((ExtraInfo->getStage(*Intf) ==
RS_Done &&
1870 FixedRegisters.
count(Intf->reg())) {
1872 dbgs() <<
"Early abort: the interference is not recolorable.\n");
1875 RecoloringCandidates.insert(Intf);
1924unsigned RAGreedy::tryLastChanceRecoloring(
const LiveInterval &VirtReg,
1928 RecoloringStack &RecolorStack,
1933 LLVM_DEBUG(
dbgs() <<
"Try last chance recoloring for " << VirtReg <<
'\n');
1935 const ssize_t EntryStackSize = RecolorStack.size();
1939 "Last chance recoloring should really be last chance");
1945 LLVM_DEBUG(
dbgs() <<
"Abort because max depth has been reached.\n");
1946 CutOffInfo |= CO_Depth;
1951 SmallLISet RecoloringCandidates;
1963 RecoloringCandidates.clear();
1964 CurrentNewVRegs.
clear();
1970 dbgs() <<
"Some interferences are not with virtual registers.\n");
1977 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
1979 LLVM_DEBUG(
dbgs() <<
"Some interferences cannot be recolored.\n");
1986 PQueue RecoloringQueue;
1989 enqueue(RecoloringQueue, RC);
1991 "Interferences are supposed to be with allocated variables");
1994 RecolorStack.push_back(std::make_pair(RC,
VRM->
getPhys(ItVirtReg)));
2009 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
2010 FixedRegisters, RecolorStack,
Depth)) {
2012 for (
Register NewVReg : CurrentNewVRegs)
2024 FixedRegisters = SaveFixedRegisters;
2031 for (
Register R : CurrentNewVRegs) {
2043 for (ssize_t
I = RecolorStack.size() - 1;
I >= EntryStackSize; --
I) {
2046 std::tie(LI, PhysReg) = RecolorStack[
I];
2052 for (
size_t I = EntryStackSize;
I != RecolorStack.size(); ++
I) {
2055 std::tie(LI, PhysReg) = RecolorStack[
I];
2061 RecolorStack.resize(EntryStackSize);
2076bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2079 RecoloringStack &RecolorStack,
2081 while (!RecoloringQueue.empty()) {
2084 MCRegister PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters,
2085 RecolorStack,
Depth + 1);
2090 if (PhysReg == ~0u || (!PhysReg && !LI->
empty()))
2094 assert(LI->
empty() &&
"Only empty live-range do not require a register");
2096 <<
" succeeded. Empty LI.\n");
2100 <<
" succeeded with: " <<
printReg(PhysReg,
TRI) <<
'\n');
2114 CutOffInfo = CO_None;
2119 selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters, RecolorStack);
2120 if (Reg == ~0U && (CutOffInfo != CO_None)) {
2121 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2122 if (CutOffEncountered == CO_Depth)
2123 Ctx.
emitError(
"register allocation failed: maximum depth for recoloring "
2124 "reached. Use -fexhaustive-register-search to skip "
2126 else if (CutOffEncountered == CO_Interf)
2127 Ctx.
emitError(
"register allocation failed: maximum interference for "
2128 "recoloring reached. Use -fexhaustive-register-search "
2130 else if (CutOffEncountered == (CO_Depth | CO_Interf))
2131 Ctx.
emitError(
"register allocation failed: maximum interference and "
2132 "depth for recoloring reached. Use "
2133 "-fexhaustive-register-search to skip cutoffs");
2150 SA->analyze(&VirtReg);
2151 if (calcSpillCost() >= CSRCost)
2156 CostPerUseLimit = 1;
2159 if (ExtraInfo->getStage(VirtReg) <
RS_Split) {
2162 SA->analyze(&VirtReg);
2163 unsigned NumCands = 0;
2165 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2167 if (BestCand == NoCand)
2172 doRegionSplit(VirtReg, BestCand,
false, NewVRegs);
2180 SetOfBrokenHints.remove(&LI);
2183void RAGreedy::initializeCSRCost() {
2198 if (ActualEntry < FixedEntry)
2200 else if (ActualEntry <= UINT32_MAX)
2205 CSRCost = CSRCost.
getFrequency() * (ActualEntry / FixedEntry);
2211void RAGreedy::collectHintInfo(
Register Reg, HintsInfo &Out) {
2217 if (OtherReg == Reg) {
2218 OtherReg =
Instr.getOperand(1).getReg();
2219 if (OtherReg == Reg)
2237 for (
const HintInfo &Info :
List) {
2238 if (
Info.PhysReg != PhysReg)
2252void RAGreedy::tryHintRecoloring(
const LiveInterval &VirtReg) {
2273 if (
Reg.isPhysical())
2279 "We have an unallocated variable which should have been handled");
2294 <<
") is recolorable.\n");
2298 collectHintInfo(Reg, Info);
2301 if (CurrPhys != PhysReg) {
2303 BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);
2308 if (OldCopiesCost < NewCopiesCost) {
2322 for (
const HintInfo &HI : Info) {
2326 }
while (!RecoloringCandidates.
empty());
2365void RAGreedy::tryHintsRecoloring() {
2368 "Recoloring is possible only for virtual registers");
2373 tryHintRecoloring(*LI);
2380 RecoloringStack &RecolorStack,
2382 uint8_t CostPerUseLimit = uint8_t(~0u);
2387 tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {
2392 EvictAdvisor->isUnusedCalleeSavedReg(PhysReg) && NewVRegs.
empty()) {
2393 MCRegister CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
2394 CostPerUseLimit, NewVRegs);
2395 if (CSRReg || !NewVRegs.
empty())
2403 if (!NewVRegs.
empty())
2408 << ExtraInfo->getCascade(VirtReg.
reg()) <<
'\n');
2415 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,
2423 if (Hint && Hint != PhysReg)
2424 SetOfBrokenHints.insert(&VirtReg);
2428 assert((NewVRegs.
empty() ||
Depth) &&
"Cannot append to existing NewVRegs");
2434 ExtraInfo->setStage(VirtReg,
RS_Split);
2442 unsigned NewVRegSizeBefore = NewVRegs.
size();
2443 Register PhysReg = trySplit(VirtReg, Order, NewVRegs, FixedRegisters);
2444 if (PhysReg || (NewVRegs.
size() - NewVRegSizeBefore))
2451 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
2452 RecolorStack,
Depth);
2458 ExtraInfo->getStage(VirtReg) <
RS_Memory) {
2463 ExtraInfo->setStage(VirtReg,
RS_Memory);
2479 MF->
verify(
this,
"After spilling");
2488 using namespace ore;
2490 R <<
NV(
"NumSpills", Spills) <<
" spills ";
2491 R <<
NV(
"TotalSpillsCost", SpillsCost) <<
" total spills cost ";
2494 R <<
NV(
"NumFoldedSpills", FoldedSpills) <<
" folded spills ";
2495 R <<
NV(
"TotalFoldedSpillsCost", FoldedSpillsCost)
2496 <<
" total folded spills cost ";
2499 R <<
NV(
"NumReloads", Reloads) <<
" reloads ";
2500 R <<
NV(
"TotalReloadsCost", ReloadsCost) <<
" total reloads cost ";
2502 if (FoldedReloads) {
2503 R <<
NV(
"NumFoldedReloads", FoldedReloads) <<
" folded reloads ";
2504 R <<
NV(
"TotalFoldedReloadsCost", FoldedReloadsCost)
2505 <<
" total folded reloads cost ";
2507 if (ZeroCostFoldedReloads)
2508 R <<
NV(
"NumZeroCostFoldedReloads", ZeroCostFoldedReloads)
2509 <<
" zero cost folded reloads ";
2511 R <<
NV(
"NumVRCopies",
Copies) <<
" virtual registers copies ";
2512 R <<
NV(
"TotalCopiesCost", CopiesCost) <<
" total copies cost ";
2517 RAGreedyStats
Stats;
2523 A->getPseudoValue())->getFrameIndex());
2526 return MI.getOpcode() == TargetOpcode::PATCHPOINT ||
2527 MI.getOpcode() == TargetOpcode::STACKMAP ||
2528 MI.getOpcode() == TargetOpcode::STATEPOINT;
2541 if (SrcReg && Src.getSubReg())
2549 if (SrcReg != DestReg)
2566 if (!isPatchpointInstr(
MI)) {
2571 std::pair<unsigned, unsigned> NonZeroCostRange =
2575 for (
unsigned Idx = 0,
E =
MI.getNumOperands();
Idx <
E; ++
Idx) {
2579 if (
Idx >= NonZeroCostRange.first &&
Idx < NonZeroCostRange.second)
2585 for (
unsigned Slot : FoldedReloads)
2586 ZeroCostFoldedReloads.
erase(Slot);
2587 Stats.FoldedReloads += FoldedReloads.size();
2588 Stats.ZeroCostFoldedReloads += ZeroCostFoldedReloads.
size();
2601 Stats.FoldedReloadsCost = RelFreq *
Stats.FoldedReloads;
2603 Stats.FoldedSpillsCost = RelFreq *
Stats.FoldedSpills;
2608RAGreedy::RAGreedyStats RAGreedy::reportStats(
MachineLoop *L) {
2609 RAGreedyStats
Stats;
2613 Stats.add(reportStats(SubLoop));
2620 if (!
Stats.isEmpty()) {
2621 using namespace ore;
2625 L->getStartLoc(),
L->getHeader());
2627 R <<
"generated in loop";
2634void RAGreedy::reportStats() {
2637 RAGreedyStats
Stats;
2639 Stats.add(reportStats(L));
2644 if (!
Stats.isEmpty()) {
2645 using namespace ore;
2649 if (
auto *SP = MF->getFunction().getSubprogram())
2654 R <<
"generated in function";
2660bool RAGreedy::hasVirtRegAlloc() {
2676 LLVM_DEBUG(
dbgs() <<
"********** GREEDY REGISTER ALLOCATION **********\n"
2677 <<
"********** Function: " << mf.
getName() <<
'\n');
2680 TII = MF->getSubtarget().getInstrInfo();
2683 MF->verify(
this,
"Before greedy register allocator");
2686 getAnalysis<LiveIntervals>(),
2687 getAnalysis<LiveRegMatrix>());
2691 if (!hasVirtRegAlloc())
2694 Indexes = &getAnalysis<SlotIndexes>();
2698 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
2699 DomTree = &getAnalysis<MachineDominatorTree>();
2700 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
2701 Loops = &getAnalysis<MachineLoopInfo>();
2702 Bundles = &getAnalysis<EdgeBundles>();
2703 SpillPlacer = &getAnalysis<SpillPlacement>();
2704 DebugVars = &getAnalysis<LiveDebugVariables>();
2706 initializeCSRCost();
2709 RegClassPriorityTrumpsGlobalness =
2718 ExtraInfo.emplace();
2720 getAnalysis<RegAllocEvictionAdvisorAnalysis>().getAdvisor(*MF, *
this);
2722 getAnalysis<RegAllocPriorityAdvisorAnalysis>().getAdvisor(*MF, *
this);
2724 VRAI = std::make_unique<VirtRegAuxInfo>(*MF, *
LIS, *
VRM, *
Loops, *MBFI);
2727 VRAI->calculateSpillWeightsAndHints();
2736 SetOfBrokenHints.clear();
2739 tryHintsRecoloring();
2742 MF->verify(
this,
"Before post optimization");
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
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
DenseMap< Block *, BlockRelaxAux > Blocks
Rewrite Partial Register Uses
const HexagonInstrInfo * TII
This file implements an indexed map.
block placement Basic Block Placement Stats
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static cl::opt< bool > GreedyRegClassPriorityTrumpsGlobalness("greedy-regclass-priority-trumps-globalness", cl::desc("Change the greedy register allocator's live range priority " "calculation to make the AllocationPriority of the register class " "more important then whether the range is global"), cl::Hidden)
static cl::opt< bool > ExhaustiveSearch("exhaustive-register-search", cl::NotHidden, cl::desc("Exhaustive Search for registers bypassing the depth " "and interference cutoffs of last chance recoloring"), cl::Hidden)
static cl::opt< unsigned > LastChanceRecoloringMaxInterference("lcr-max-interf", cl::Hidden, cl::desc("Last chance recoloring maximum number of considered" " interference at a time"), cl::init(8))
static bool hasTiedDef(MachineRegisterInfo *MRI, unsigned reg)
Return true if reg has any tied def operand.
static bool readsLaneSubset(const MachineRegisterInfo &MRI, const MachineInstr *MI, const LiveInterval &VirtReg, const TargetRegisterInfo *TRI, SlotIndex Use, const TargetInstrInfo *TII)
Return true if MI at \P Use reads a subset of the lanes live in VirtReg.
static bool assignedRegPartiallyOverlaps(const TargetRegisterInfo &TRI, const VirtRegMap &VRM, MCRegister PhysReg, const LiveInterval &Intf)
Return true if the existing assignment of Intf overlaps, but is not the same, as PhysReg.
static cl::opt< unsigned > CSRFirstTimeCost("regalloc-csr-first-time-cost", cl::desc("Cost for first time use of callee-saved register."), cl::init(0), cl::Hidden)
static cl::opt< unsigned > LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden, cl::desc("Last chance recoloring max depth"), cl::init(5))
static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator)
static cl::opt< unsigned long > GrowRegionComplexityBudget("grow-region-complexity-budget", cl::desc("growRegion() does not scale with the number of BB edges, so " "limit its budget and bail out once we reach the limit."), cl::init(10000), cl::Hidden)
Greedy Register Allocator
static cl::opt< SplitEditor::ComplementSpillMode > SplitSpillMode("split-spill-mode", cl::Hidden, cl::desc("Spill mode for splitting live ranges"), cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")), cl::init(SplitEditor::SM_Speed))
static LaneBitmask getInstReadLaneMask(const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, const MachineInstr &MI, Register Reg)
static unsigned getNumAllocatableRegsForConstraints(const MachineInstr *MI, Register Reg, const TargetRegisterClass *SuperRC, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, const RegisterClassInfo &RCI)
Get the number of allocatable registers that match the constraints of Reg on MI and that are also in ...
static cl::opt< bool > EnableDeferredSpilling("enable-deferred-spilling", cl::Hidden, cl::desc("Instead of spilling a variable right away, defer the actual " "code insertion to the end of the allocation. That way the " "allocator might still find a suitable coloring for this " "variable because of other evicted variables."), cl::init(false))
static cl::opt< unsigned > SplitThresholdForRegWithHint("split-threshold-for-reg-with-hint", cl::desc("The threshold for splitting a virtual register with a hint, in " "percentate"), cl::init(75), cl::Hidden)
static cl::opt< bool > GreedyReverseLocalAssignment("greedy-reverse-local-assignment", cl::desc("Reverse allocation order of local live ranges, such that " "shorter local live ranges will tend to be allocated first"), cl::Hidden)
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.
bool liveAt(SlotIndex index) const
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
bool checkRegMaskInterference(const LiveInterval &VirtReg, MCRegister PhysReg=MCRegister::NoRegister)
Check for regmask interference only.
void unassign(const LiveInterval &VirtReg)
Unassign VirtReg from its PhysReg.
LiveIntervalUnion::Query & query(const LiveRange &LR, MCRegister RegUnit)
Query a line of the assigned virtual register matrix directly.
bool isPhysRegUsed(MCRegister PhysReg) const
Returns true if the given PhysReg has any live intervals assigned.
@ IK_VirtReg
Virtual register interference.
void assign(const LiveInterval &VirtReg, MCRegister PhysReg)
Assign VirtReg to PhysReg.
InterferenceKind checkInterference(const LiveInterval &VirtReg, MCRegister PhysReg)
Check for interference before assigning VirtReg to PhysReg.
LiveIntervalUnion * getLiveUnions()
Directly access the live interval unions per regunit.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
Wrapper class representing physical registers. Should be passed by value.
constexpr bool isValid() const
static constexpr unsigned NoRegister
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
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 canReassign(const LiveInterval &VirtReg, MCRegister FromReg) const
bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const
unsigned getLastCostChange(const TargetRegisterClass *RC) const
Get the position of the last cost change in getOrder(RC).
bool isProperSubClass(const TargetRegisterClass *RC) const
isProperSubClass - Returns true if RC has a legal super-class with more allocatable registers.
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
uint8_t getMinCost(const TargetRegisterClass *RC) const
Get the minimum register cost in RC's allocation order.
MCRegister getLastCalleeSavedAlias(MCRegister PhysReg) const
getLastCalleeSavedAlias - Returns the last callee saved register that overlaps PhysReg,...
Wrapper class representing virtual and physical registers.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
SlotIndex - An opaque wrapper around machine indexes.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
@ InstrDist
The default distance between instructions as returned by distance().
bool isValid() const
Returns true if this is a valid index.
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
int getApproxInstrDistance(SlotIndex other) const
Return the scaled distance from this index to the given one, where all slots on the same instruction ...
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
SlotIndex getLastIndex()
Returns the base index of the last slot in this analysis.
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
void packIndexes()
Renumber all indexes using the default instruction distance.
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)
addConstraints - Add constraints and biases.
bool finish()
finish - Compute the optimal spill code placement given the constraints.
void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)
addPrefSpill - Add PrefSpill constraints to all blocks listed.
void prepare(BitVector &RegBundles)
prepare - Reset state and prepare for a new spill placement computation.
bool scanActiveBundles()
scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks,...
void addLinks(ArrayRef< unsigned > Links)
addLinks - Add transparent blocks with the given numbers.
void iterate()
iterate - Update the network iteratively until convergence, or new bundles are found.
@ MustSpill
A register is impossible, variable must be spilled.
@ DontCare
Block doesn't care / variable not live.
@ PrefReg
Block entry/exit prefers a register.
@ PrefSpill
Block entry/exit prefers a stack slot.
ArrayRef< unsigned > getRecentPositive()
getRecentPositive - Return an array of bundles that became positive during the previous call to scanA...
BlockFrequency getBlockFrequency(unsigned Number) const
getBlockFrequency - Return the estimated block execution frequency per function invocation.
virtual void spill(LiveRangeEdit &LRE)=0
spill - Spill the LRE.getParent() live interval.
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
SplitEditor - Edit machine code and LiveIntervals for live range splitting.
@ SM_Partition
SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...
@ SM_Speed
SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies.
@ SM_Size
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.
TargetInstrInfo - Interface to description of machine instruction set.
virtual 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...
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...
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...
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
NodeAddr< InstrNode * > Instr
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.
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.
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.