Go to the documentation of this file.
80 #define DEBUG_TYPE "regalloc"
82 STATISTIC(NumGlobalSplits,
"Number of split global live ranges");
83 STATISTIC(NumLocalSplits,
"Number of split local live ranges");
84 STATISTIC(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"),
145 "Greedy Register Allocator",
false,
false)
164 const char *
const RAGreedy::StageName[] = {
234 bool RAGreedy::LRE_CanEraseVirtReg(
Register VirtReg) {
249 void RAGreedy::LRE_WillShrinkVirtReg(
Register VirtReg) {
260 ExtraInfo->LRE_DidCloneVirtReg(New, Old);
265 if (!Info.inBounds(Old))
274 Info[New] = Info[Old];
278 SpillerInstance.reset();
284 void RAGreedy::enqueue(PQueue &CurQueue,
const LiveInterval *LI) {
287 const unsigned Size = LI->
getSize();
289 assert(
Reg.isVirtual() &&
"Can only enqueue virtual registers");
292 auto Stage = ExtraInfo->getOrInitStage(
Reg);
295 ExtraInfo->setStage(
Reg, Stage);
306 static unsigned MemOp = 0;
313 bool ForceGlobal = !ReverseLocal &&
315 unsigned GlobalBit = 0;
337 if (RegClassPriorityTrumpsGlobalness)
351 CurQueue.push(std::make_pair(Prio, ~
Reg));
357 if (CurQueue.empty())
374 for (
auto I = Order.
begin(),
E = Order.
end();
I !=
E && !PhysReg; ++
I) {
395 if (EvictAdvisor->canEvictHintInterference(VirtReg, PhysHint,
397 evictInterference(VirtReg, PhysHint, NewVRegs);
402 SetOfBrokenHints.insert(&VirtReg);
406 uint8_t Cost = RegCosts[PhysReg];
413 << (
unsigned)Cost <<
'\n');
414 MCRegister CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost, FixedRegisters);
415 return CheapReg ? CheapReg : PhysReg;
427 for (
auto I = Order.
begin(),
E = Order.
end();
I !=
E && !PhysReg; ++
I) {
428 if ((*I).id() == PrevReg.
id())
432 for (; Units.
isValid(); ++Units) {
459 bool RAGreedy::canEvictInterferenceInRange(
const LiveInterval &VirtReg,
471 if (!Intf->overlaps(Start, End))
475 if (ExtraInfo->getStage(*Intf) ==
RS_Done)
484 if (!(Cost < MaxCost))
510 float *BestEvictweight)
const {
519 if (!canEvictInterferenceInRange(VirtReg, PhysReg, Start, End,
524 BestEvicteePhys = PhysReg;
526 *BestEvictweight = BestEvictCost.
MaxWeight;
527 return BestEvicteePhys;
533 void RAGreedy::evictInterference(
const LiveInterval &VirtReg,
539 unsigned Cascade = ExtraInfo->getOrAssignNewCascade(VirtReg.
reg());
542 <<
" interference: Cascade " << Cascade <<
'\n');
562 LastEvicted.addEviction(PhysReg, VirtReg.
reg(), Intf->reg());
565 assert((ExtraInfo->getCascade(Intf->reg()) < Cascade ||
567 "Cannot decrease cascade number, illegal eviction");
568 ExtraInfo->setCascade(Intf->reg(), Cascade);
570 NewVRegs.push_back(Intf->reg());
587 unsigned CostPerUseLimit)
const {
588 unsigned OrderLimit = Order.
getOrder().size();
590 if (CostPerUseLimit < uint8_t(~0u)) {
594 if (MinCost >= CostPerUseLimit) {
596 << MinCost <<
", no cheaper registers to be found.\n");
602 if (RegCosts[Order.
getOrder().back()] >= CostPerUseLimit) {
613 if (RegCosts[PhysReg] >= CostPerUseLimit)
617 if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {
619 dbgs() <<
printReg(PhysReg, TRI) <<
" would clobber CSR "
634 uint8_t CostPerUseLimit,
639 MCRegister BestPhys = EvictAdvisor->tryFindEvictionCandidate(
640 VirtReg, Order, CostPerUseLimit, FixedRegisters);
642 evictInterference(VirtReg, BestPhys, NewVRegs);
660 SplitConstraints.resize(UseBlocks.
size());
662 for (
unsigned I = 0;
I != UseBlocks.
size(); ++
I) {
697 SA->getFirstSplitPoint(BC.
Number)))
703 if (Intf.
last() >= SA->getLastSplitPoint(BC.
Number)) {
730 const unsigned GroupSize = 8;
732 unsigned TBS[GroupSize];
733 unsigned B = 0,
T = 0;
735 for (
unsigned Number : Blocks) {
739 assert(
T < GroupSize &&
"Array overflow");
741 if (++
T == GroupSize) {
748 assert(
B < GroupSize &&
"Array overflow");
754 if (FirstNonDebugInstr !=
MBB->
end() &&
756 SA->getFirstSplitPoint(Number)))
765 if (Intf.
last() >= SA->getLastSplitPoint(Number))
770 if (++
B == GroupSize) {
781 bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
785 unsigned AddedTo = 0;
787 unsigned Visited = 0;
794 for (
unsigned Bundle : NewBundles) {
798 if (Blocks.
size() >= Budget)
800 Budget -= Blocks.
size();
801 for (
unsigned Block : Blocks) {
802 if (!Todo.
test(Block))
806 ActiveBlocks.push_back(Block);
813 if (ActiveBlocks.size() == AddedTo)
818 auto NewBlocks =
makeArrayRef(ActiveBlocks).slice(AddedTo);
820 if (!addThroughConstraints(Cand.Intf, NewBlocks))
826 AddedTo = ActiveBlocks.size();
842 bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
844 if (!SA->getNumThroughBlocks())
854 SpillPlacer->
prepare(Cand.LiveBundles);
858 if (!addSplitConstraints(Cand.Intf, Cost)) {
863 if (!growRegion(Cand)) {
870 if (!Cand.LiveBundles.any()) {
876 for (
int I : Cand.LiveBundles.set_bits())
877 dbgs() <<
" EB#" <<
I;
953 bool RAGreedy::splitCanCauseEvictionChain(
Register Evictee,
954 GlobalSplitCandidate &Cand,
957 EvictionTrack::EvictorInfo VregEvictorInfo = LastEvicted.getEvictor(Evictee);
958 unsigned Evictor = VregEvictorInfo.first;
962 if (!Evictor || !PhysReg)
968 Cand.Intf.first(), Cand.Intf.last(), &MaxWeight);
972 if ((PhysReg != Cand.PhysReg) && (PhysReg != FutureEvictedPhysReg))
975 Cand.Intf.moveToBlock(BBNumber);
991 float splitArtifactWeight =
993 Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
994 if (splitArtifactWeight >= 0 && splitArtifactWeight < MaxWeight)
1004 BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
1007 const BitVector &LiveBundles = Cand.LiveBundles;
1009 for (
unsigned I = 0;
I != UseBlocks.
size(); ++
I) {
1016 Cand.Intf.moveToBlock(BC.
Number);
1026 for (
unsigned Number : Cand.ActiveBlocks) {
1027 bool RegIn = LiveBundles[Bundles->
getBundle(Number,
false)];
1028 bool RegOut = LiveBundles[Bundles->
getBundle(Number,
true)];
1029 if (!RegIn && !RegOut)
1031 if (RegIn && RegOut) {
1033 Cand.Intf.moveToBlock(Number);
1034 if (Cand.Intf.hasInterference()) {
1062 const unsigned NumGlobalIntvs = LREdit.
size();
1065 assert(NumGlobalIntvs &&
"No global intervals configured");
1077 unsigned IntvIn = 0, IntvOut = 0;
1080 unsigned CandIn = BundleCand[Bundles->
getBundle(Number,
false)];
1081 if (CandIn != NoCand) {
1082 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1083 IntvIn = Cand.IntvIdx;
1084 Cand.Intf.moveToBlock(Number);
1085 IntfIn = Cand.Intf.first();
1089 unsigned CandOut = BundleCand[Bundles->
getBundle(Number,
true)];
1090 if (CandOut != NoCand) {
1091 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1092 IntvOut = Cand.IntvIdx;
1093 Cand.Intf.moveToBlock(Number);
1094 IntfOut = Cand.Intf.last();
1099 if (!IntvIn && !IntvOut) {
1101 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1102 SE->splitSingleBlock(BI);
1106 if (IntvIn && IntvOut)
1107 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1109 SE->splitRegInBlock(BI, IntvIn, IntfIn);
1111 SE->splitRegOutBlock(BI, IntvOut, IntfOut);
1117 BitVector Todo = SA->getThroughBlocks();
1118 for (
unsigned UsedCand : UsedCands) {
1120 for (
unsigned Number : Blocks) {
1121 if (!Todo.
test(Number))
1125 unsigned IntvIn = 0, IntvOut = 0;
1128 unsigned CandIn = BundleCand[Bundles->
getBundle(Number,
false)];
1129 if (CandIn != NoCand) {
1130 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1131 IntvIn = Cand.IntvIdx;
1132 Cand.Intf.moveToBlock(Number);
1133 IntfIn = Cand.Intf.first();
1136 unsigned CandOut = BundleCand[Bundles->
getBundle(Number,
true)];
1137 if (CandOut != NoCand) {
1138 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1139 IntvOut = Cand.IntvIdx;
1140 Cand.Intf.moveToBlock(Number);
1141 IntfOut = Cand.Intf.last();
1143 if (!IntvIn && !IntvOut)
1145 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1152 SE->finish(&IntvMap);
1155 unsigned OrigBlocks = SA->getNumLiveBlocks();
1162 for (
unsigned I = 0,
E = LREdit.
size();
I !=
E; ++
I) {
1166 if (ExtraInfo->getOrInitStage(
Reg.reg()) !=
RS_New)
1171 if (IntvMap[
I] == 0) {
1178 if (IntvMap[
I] < NumGlobalIntvs) {
1179 if (SA->countLiveBlocks(&
Reg) >= OrigBlocks) {
1180 LLVM_DEBUG(
dbgs() <<
"Main interval covers the same " << OrigBlocks
1181 <<
" blocks as original.\n");
1193 MF->
verify(
this,
"After splitting live range around region");
1201 unsigned NumCands = 0;
1206 bool HasCompact = calcCompactRegion(GlobalCand.front());
1214 BestCost = SpillCost;
1219 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
1223 if (!HasCompact && BestCand == NoCand)
1226 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1229 unsigned RAGreedy::calculateRegionSplitCost(
const LiveInterval &VirtReg,
1234 unsigned BestCand = NoCand;
1237 if (IgnoreCSR && EvictAdvisor->isUnusedCalleeSavedReg(PhysReg))
1243 unsigned WorstCount = ~0u;
1245 for (
unsigned CandIndex = 0; CandIndex != NumCands; ++CandIndex) {
1246 if (CandIndex == BestCand || !GlobalCand[CandIndex].PhysReg)
1248 unsigned Count = GlobalCand[CandIndex].LiveBundles.count();
1249 if (Count < WorstCount) {
1255 GlobalCand[Worst] = GlobalCand[NumCands];
1256 if (BestCand == NumCands)
1260 if (GlobalCand.size() <= NumCands)
1261 GlobalCand.
resize(NumCands+1);
1262 GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1263 Cand.reset(IntfCache, PhysReg);
1265 SpillPlacer->
prepare(Cand.LiveBundles);
1267 if (!addSplitConstraints(Cand.Intf, Cost)) {
1273 if (Cost >= BestCost) {
1275 if (BestCand == NoCand)
1276 dbgs() <<
" worse than no bundles\n";
1278 dbgs() <<
" worse than "
1279 <<
printReg(GlobalCand[BestCand].PhysReg, TRI) <<
'\n';
1283 if (!growRegion(Cand)) {
1291 if (!Cand.LiveBundles.any()) {
1296 Cost += calcGlobalSplitCost(Cand, Order);
1298 dbgs() <<
", total = ";
1300 for (
int I : Cand.LiveBundles.set_bits())
1301 dbgs() <<
" EB#" <<
I;
1304 if (Cost < BestCost) {
1305 BestCand = NumCands;
1314 unsigned RAGreedy::doRegionSplit(
const LiveInterval &VirtReg,
unsigned BestCand,
1326 if (BestCand != NoCand) {
1327 GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1328 if (
unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1329 UsedCands.push_back(BestCand);
1330 Cand.IntvIdx = SE->openIntv();
1332 <<
B <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1339 GlobalSplitCandidate &Cand = GlobalCand.front();
1340 assert(!Cand.PhysReg &&
"Compact region has no physreg");
1341 if (
unsigned B = Cand.getBundles(BundleCand, 0)) {
1342 UsedCands.push_back(0);
1343 Cand.IntvIdx = SE->openIntv();
1345 <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1350 splitAroundRegion(LREdit, UsedCands);
1361 unsigned RAGreedy::tryBlockSplit(
const LiveInterval &VirtReg,
1364 assert(&SA->getParent() == &VirtReg &&
"Live range wasn't analyzed");
1371 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1372 SE->splitSingleBlock(BI);
1380 SE->finish(&IntvMap);
1387 for (
unsigned I = 0,
E = LREdit.
size();
I !=
E; ++
I) {
1389 if (ExtraInfo->getOrInitStage(LI.
reg()) ==
RS_New && IntvMap[
I] == 0)
1394 MF->
verify(
this,
"After splitting live range around basic blocks");
1408 assert(SuperRC &&
"Invalid register class");
1411 MI->getRegClassConstraintEffectForVReg(
Reg, SuperRC,
TII,
TRI,
1425 unsigned RAGreedy::tryInstructionSplit(
const LiveInterval &VirtReg,
1439 if (
Uses.size() <= 1)
1443 <<
" individual instrs.\n");
1454 if (
MI->isFullCopy() ||
1455 SuperRCNumAllocatableRegs ==
1464 SE->useIntv(SegStart, SegStop);
1467 if (LREdit.
empty()) {
1473 SE->finish(&IntvMap);
1489 void RAGreedy::calcGapWeights(
MCRegister PhysReg,
1491 assert(SA->getUseBlocks().size() == 1 &&
"Not a local interval");
1494 const unsigned NumGaps =
Uses.size()-1;
1502 GapWeight.
assign(NumGaps, 0.0
f);
1519 for (
unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1521 while (
Uses[Gap+1].getBoundaryIndex() < IntI.start())
1522 if (++Gap == NumGaps)
1528 const float weight = IntI.value()->weight();
1529 for (; Gap != NumGaps; ++Gap) {
1530 GapWeight[Gap] =
std::max(GapWeight[Gap], weight);
1531 if (
Uses[Gap+1].getBaseIndex() >= IntI.stop())
1546 for (
unsigned Gap = 0;
I !=
E &&
I->start < StopIdx; ++
I) {
1547 while (
Uses[Gap+1].getBoundaryIndex() <
I->start)
1548 if (++Gap == NumGaps)
1553 for (; Gap != NumGaps; ++Gap) {
1555 if (
Uses[Gap+1].getBaseIndex() >=
I->end)
1567 unsigned RAGreedy::tryLocalSplit(
const LiveInterval &VirtReg,
1572 if (SA->getUseBlocks().size() != 1)
1585 if (
Uses.size() <= 2)
1587 const unsigned NumGaps =
Uses.size()-1;
1590 dbgs() <<
"tryLocalSplit: ";
1606 unsigned RE = RMS.
size();
1607 for (
unsigned I = 0;
I != NumGaps && RI != RE; ++
I) {
1618 RegMaskGaps.push_back(
I);
1645 bool ProgressRequired = ExtraInfo->getStage(VirtReg) >=
RS_Split2;
1648 unsigned BestBefore = NumGaps;
1649 unsigned BestAfter = 0;
1652 const float blockFreq =
1661 calcGapWeights(PhysReg, GapWeight);
1665 for (
unsigned I = 0,
E = RegMaskGaps.size();
I !=
E; ++
I)
1672 unsigned SplitBefore = 0, SplitAfter = 1;
1676 float MaxGap = GapWeight[0];
1680 const bool LiveBefore = SplitBefore != 0 || BI.
LiveIn;
1681 const bool LiveAfter = SplitAfter != NumGaps || BI.
LiveOut;
1684 <<
'-' <<
Uses[SplitAfter] <<
" I=" << MaxGap);
1687 if (!LiveBefore && !LiveAfter) {
1695 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
1698 bool Legal = !ProgressRequired || NewGaps < NumGaps;
1707 blockFreq * (NewGaps + 1),
1708 Uses[SplitBefore].distance(
Uses[SplitAfter]) +
1716 float Diff = EstWeight - MaxGap;
1717 if (Diff > BestDiff) {
1720 BestBefore = SplitBefore;
1721 BestAfter = SplitAfter;
1728 if (++SplitBefore < SplitAfter) {
1731 if (GapWeight[SplitBefore - 1] >= MaxGap) {
1732 MaxGap = GapWeight[SplitBefore];
1733 for (
unsigned I = SplitBefore + 1;
I != SplitAfter; ++
I)
1734 MaxGap =
std::max(MaxGap, GapWeight[
I]);
1742 if (SplitAfter >= NumGaps) {
1748 MaxGap =
std::max(MaxGap, GapWeight[SplitAfter++]);
1753 if (BestBefore == NumGaps)
1757 <<
Uses[BestAfter] <<
", " << BestDiff <<
", "
1758 << (BestAfter - BestBefore + 1) <<
" instrs\n");
1766 SE->useIntv(SegStart, SegStop);
1768 SE->finish(&IntvMap);
1773 bool LiveBefore = BestBefore != 0 || BI.
LiveIn;
1774 bool LiveAfter = BestAfter != NumGaps || BI.
LiveOut;
1775 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1776 if (NewGaps >= NumGaps) {
1778 assert(!ProgressRequired &&
"Didn't make progress when it was required.");
1779 for (
unsigned I = 0,
E = IntvMap.size();
I !=
E; ++
I)
1780 if (IntvMap[
I] == 1) {
1802 if (ExtraInfo->getStage(VirtReg) >=
RS_Spill)
1809 SA->analyze(&VirtReg);
1810 Register PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
1811 if (PhysReg || !NewVRegs.empty())
1813 return tryInstructionSplit(VirtReg, Order, NewVRegs);
1819 SA->analyze(&VirtReg);
1824 if (ExtraInfo->getStage(VirtReg) <
RS_Split2) {
1825 MCRegister PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1826 if (PhysReg || !NewVRegs.empty())
1831 return tryBlockSplit(VirtReg, Order, NewVRegs);
1854 if (PhysReg == AssignedReg)
1867 bool RAGreedy::mayRecolorAllInterferences(
1869 SmallLISet &RecoloringCandidates,
const SmallVirtRegSet &FixedRegisters) {
1880 CutOffInfo |= CO_Interf;
1895 if (((ExtraInfo->getStage(*Intf) ==
RS_Done &&
1900 FixedRegisters.
count(Intf->reg())) {
1902 dbgs() <<
"Early abort: the interference is not recolorable.\n");
1905 RecoloringCandidates.insert(Intf);
1954 unsigned RAGreedy::tryLastChanceRecoloring(
const LiveInterval &VirtReg,
1958 RecoloringStack &RecolorStack,
1963 LLVM_DEBUG(
dbgs() <<
"Try last chance recoloring for " << VirtReg <<
'\n');
1965 const ssize_t EntryStackSize = RecolorStack.size();
1969 "Last chance recoloring should really be last chance");
1975 LLVM_DEBUG(
dbgs() <<
"Abort because max depth has been reached.\n");
1976 CutOffInfo |= CO_Depth;
1981 SmallLISet RecoloringCandidates;
1992 <<
printReg(PhysReg, TRI) <<
'\n');
1993 RecoloringCandidates.clear();
1994 CurrentNewVRegs.
clear();
2000 dbgs() <<
"Some interferences are not with virtual registers.\n");
2007 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
2009 LLVM_DEBUG(
dbgs() <<
"Some interferences cannot be recolored.\n");
2016 PQueue RecoloringQueue;
2019 enqueue(RecoloringQueue, RC);
2021 "Interferences are supposed to be with allocated variables");
2024 RecolorStack.push_back(std::make_pair(RC,
VRM->
getPhys(ItVirtReg)));
2039 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
2040 FixedRegisters, RecolorStack,
Depth)) {
2042 for (
Register NewVReg : CurrentNewVRegs)
2043 NewVRegs.push_back(NewVReg);
2051 <<
printReg(PhysReg, TRI) <<
'\n');
2054 FixedRegisters = SaveFixedRegisters;
2061 for (
Register &R : CurrentNewVRegs) {
2064 NewVRegs.push_back(R);
2073 for (ssize_t
I = RecolorStack.size() - 1;
I >= EntryStackSize; --
I) {
2076 std::tie(LI, PhysReg) = RecolorStack[
I];
2082 for (
size_t I = EntryStackSize;
I != RecolorStack.size(); ++
I) {
2085 std::tie(LI, PhysReg) = RecolorStack[
I];
2090 RecolorStack.resize(EntryStackSize);
2105 bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2108 RecoloringStack &RecolorStack,
2110 while (!RecoloringQueue.empty()) {
2113 MCRegister PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters,
2114 RecolorStack,
Depth + 1);
2119 if (PhysReg == ~0u || (!PhysReg && !LI->
empty()))
2123 assert(LI->
empty() &&
"Only empty live-range do not require a register");
2125 <<
" succeeded. Empty LI.\n");
2129 <<
" succeeded with: " <<
printReg(PhysReg, TRI) <<
'\n');
2143 CutOffInfo = CO_None;
2148 selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters, RecolorStack);
2149 if (
Reg == ~0U && (CutOffInfo != CO_None)) {
2150 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2151 if (CutOffEncountered == CO_Depth)
2152 Ctx.
emitError(
"register allocation failed: maximum depth for recoloring "
2153 "reached. Use -fexhaustive-register-search to skip "
2155 else if (CutOffEncountered == CO_Interf)
2156 Ctx.
emitError(
"register allocation failed: maximum interference for "
2157 "recoloring reached. Use -fexhaustive-register-search "
2159 else if (CutOffEncountered == (CO_Depth | CO_Interf))
2160 Ctx.
emitError(
"register allocation failed: maximum interference and "
2161 "depth for recoloring reached. Use "
2162 "-fexhaustive-register-search to skip cutoffs");
2179 SA->analyze(&VirtReg);
2180 if (calcSpillCost() >= CSRCost)
2185 CostPerUseLimit = 1;
2188 if (ExtraInfo->getStage(VirtReg) <
RS_Split) {
2191 SA->analyze(&VirtReg);
2192 unsigned NumCands = 0;
2194 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2196 if (BestCand == NoCand)
2201 doRegionSplit(VirtReg, BestCand,
false, NewVRegs);
2209 SetOfBrokenHints.remove(&LI);
2212 void RAGreedy::initializeCSRCost() {
2227 if (ActualEntry < FixedEntry)
2229 else if (ActualEntry <= UINT32_MAX)
2234 CSRCost = CSRCost.
getFrequency() * (ActualEntry / FixedEntry);
2240 void RAGreedy::collectHintInfo(
Register Reg, HintsInfo &Out) {
2242 if (!Instr.isFullCopy())
2245 Register OtherReg = Instr.getOperand(0).getReg();
2246 if (OtherReg ==
Reg) {
2247 OtherReg = Instr.getOperand(1).getReg();
2248 if (OtherReg ==
Reg)
2255 Out.push_back(HintInfo(MBFI->
getBlockFreq(Instr.getParent()), OtherReg,
2263 BlockFrequency RAGreedy::getBrokenHintFreq(
const HintsInfo &List,
2266 for (
const HintInfo &
Info : List) {
2267 if (
Info.PhysReg != PhysReg)
2281 void RAGreedy::tryHintRecoloring(
const LiveInterval &VirtReg) {
2293 RecoloringCandidates.push_back(
Reg);
2296 <<
'(' <<
printReg(PhysReg, TRI) <<
")\n");
2308 "We have an unallocated variable which should have been handled");
2323 <<
") is recolorable.\n");
2330 if (CurrPhys != PhysReg) {
2337 if (OldCopiesCost < NewCopiesCost) {
2351 for (
const HintInfo &
HI :
Info) {
2353 RecoloringCandidates.push_back(
HI.Reg);
2355 }
while (!RecoloringCandidates.empty());
2394 void RAGreedy::tryHintsRecoloring() {
2397 "Recoloring is possible only for virtual registers");
2402 tryHintRecoloring(*LI);
2409 RecoloringStack &RecolorStack,
2411 uint8_t CostPerUseLimit = uint8_t(~0u);
2416 tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {
2418 LastEvicted.clearEvicteeInfo(VirtReg.
reg());
2423 EvictAdvisor->isUnusedCalleeSavedReg(PhysReg) && NewVRegs.empty()) {
2424 MCRegister CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
2425 CostPerUseLimit, NewVRegs);
2426 if (CSRReg || !NewVRegs.empty())
2436 << ExtraInfo->getCascade(VirtReg.
reg()) <<
'\n');
2443 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,
2451 if (Hint && Hint != PhysReg)
2452 SetOfBrokenHints.insert(&VirtReg);
2455 LastEvicted.clearEvicteeInfo(VirtReg.
reg());
2459 assert((NewVRegs.empty() ||
Depth) &&
"Cannot append to existing NewVRegs");
2465 ExtraInfo->setStage(VirtReg,
RS_Split);
2467 NewVRegs.push_back(VirtReg.
reg());
2473 unsigned NewVRegSizeBefore = NewVRegs.size();
2474 Register PhysReg = trySplit(VirtReg, Order, NewVRegs, FixedRegisters);
2475 if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore)) {
2477 LastEvicted.clearEvicteeInfo(VirtReg.
reg());
2485 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
2486 RecolorStack,
Depth);
2492 ExtraInfo->getStage(VirtReg) <
RS_Memory) {
2497 ExtraInfo->setStage(VirtReg,
RS_Memory);
2499 NewVRegs.push_back(VirtReg.
reg());
2505 ExtraInfo->setStage(NewVRegs.begin(), NewVRegs.end(),
RS_Done);
2513 MF->
verify(
this,
"After spilling");
2522 using namespace ore;
2524 R <<
NV(
"NumSpills", Spills) <<
" spills ";
2525 R <<
NV(
"TotalSpillsCost", SpillsCost) <<
" total spills cost ";
2528 R <<
NV(
"NumFoldedSpills", FoldedSpills) <<
" folded spills ";
2529 R <<
NV(
"TotalFoldedSpillsCost", FoldedSpillsCost)
2530 <<
" total folded spills cost ";
2533 R <<
NV(
"NumReloads", Reloads) <<
" reloads ";
2534 R <<
NV(
"TotalReloadsCost", ReloadsCost) <<
" total reloads cost ";
2536 if (FoldedReloads) {
2537 R <<
NV(
"NumFoldedReloads", FoldedReloads) <<
" folded reloads ";
2538 R <<
NV(
"TotalFoldedReloadsCost", FoldedReloadsCost)
2539 <<
" total folded reloads cost ";
2541 if (ZeroCostFoldedReloads)
2542 R <<
NV(
"NumZeroCostFoldedReloads", ZeroCostFoldedReloads)
2543 <<
" zero cost folded reloads ";
2545 R <<
NV(
"NumVRCopies",
Copies) <<
" virtual registers copies ";
2546 R <<
NV(
"TotalCopiesCost", CopiesCost) <<
" total copies cost ";
2551 RAGreedyStats
Stats;
2557 A->getPseudoValue())->getFrameIndex());
2560 return MI.getOpcode() == TargetOpcode::PATCHPOINT ||
2561 MI.getOpcode() == TargetOpcode::STACKMAP ||
2562 MI.getOpcode() == TargetOpcode::STATEPOINT;
2569 Src.getReg().isVirtual())
2585 if (!isPatchpointInstr(
MI)) {
2586 Stats.FoldedReloads += Accesses.size();
2590 std::pair<unsigned, unsigned> NonZeroCostRange =
2594 for (
unsigned Idx = 0,
E =
MI.getNumOperands(); Idx <
E; ++Idx) {
2598 if (Idx >= NonZeroCostRange.first && Idx < NonZeroCostRange.second)
2604 for (
unsigned Slot : FoldedReloads)
2605 ZeroCostFoldedReloads.
erase(Slot);
2606 Stats.FoldedReloads += FoldedReloads.size();
2607 Stats.ZeroCostFoldedReloads += ZeroCostFoldedReloads.
size();
2613 Stats.FoldedSpills += Accesses.size();
2620 Stats.FoldedReloadsCost = RelFreq *
Stats.FoldedReloads;
2622 Stats.FoldedSpillsCost = RelFreq *
Stats.FoldedSpills;
2627 RAGreedy::RAGreedyStats RAGreedy::reportStats(
MachineLoop *L) {
2628 RAGreedyStats
Stats;
2632 Stats.add(reportStats(SubLoop));
2639 if (!
Stats.isEmpty()) {
2640 using namespace ore;
2644 L->getStartLoc(), L->getHeader());
2646 R <<
"generated in loop";
2653 void RAGreedy::reportStats() {
2656 RAGreedyStats
Stats;
2658 Stats.add(reportStats(L));
2663 if (!
Stats.isEmpty()) {
2664 using namespace ore;
2668 if (
auto *SP = MF->getFunction().getSubprogram())
2673 R <<
"generated in function";
2680 LLVM_DEBUG(
dbgs() <<
"********** GREEDY REGISTER ALLOCATION **********\n"
2681 <<
"********** Function: " << mf.
getName() <<
'\n');
2684 TRI = MF->getSubtarget().getRegisterInfo();
2685 TII = MF->getSubtarget().getInstrInfo();
2689 MF->verify(
this,
"Before greedy register allocator");
2692 getAnalysis<LiveIntervals>(),
2693 getAnalysis<LiveRegMatrix>());
2694 Indexes = &getAnalysis<SlotIndexes>();
2695 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
2696 DomTree = &getAnalysis<MachineDominatorTree>();
2697 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
2698 Loops = &getAnalysis<MachineLoopInfo>();
2699 Bundles = &getAnalysis<EdgeBundles>();
2700 SpillPlacer = &getAnalysis<SpillPlacement>();
2701 DebugVars = &getAnalysis<LiveDebugVariables>();
2702 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
2704 initializeCSRCost();
2707 RegClassPriorityTrumpsGlobalness =
2712 ExtraInfo.emplace();
2714 getAnalysis<RegAllocEvictionAdvisorAnalysis>().getAdvisor(*MF, *
this);
2716 VRAI = std::make_unique<VirtRegAuxInfo>(*MF, *
LIS, *
VRM, *
Loops, *MBFI);
2719 VRAI->calculateSpillWeightsAndHints();
2728 SetOfBrokenHints.clear();
2729 LastEvicted.clear();
2732 tryHintsRecoloring();
2735 MF->verify(
this,
"Before post optimization");
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
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...
static float normalizeSpillWeight(float UseDefFreq, unsigned Size, unsigned NumInstr)
Normalize the spill weight of a live interval.
virtual bool shouldRegionSplitForVirtReg(const MachineFunction &MF, const LiveInterval &VirtReg) const
Region split has a high compile time cost especially for large live range.
void enqueueImpl(const LiveInterval *LI) override
enqueue - Add VirtReg to the priority queue of unassigned registers.
bool LiveIn
Current reg is live in.
This is an optimization pass for GlobalISel generic memory operations.
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.
bool isImplicitDef() const
void emitError(uint64_t LocCookie, const Twine &ErrorStr)
emitError - Emit an error message to the currently installed error handler with optional location inf...
SlotIndex FirstInstr
First instr accessing current reg.
FunctionPass * createGreedyRegisterAllocator()
Greedy register allocation pass - This pass implements a global register allocator for optimized buil...
ImmutableAnalysis abstraction for fetching the Eviction Advisor.
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
unsigned getLastCostChange(const TargetRegisterClass *RC) const
Get the position of the last cost change in getOrder(RC).
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)
bool isValid() const
Returns true if this is a valid index.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
bool hasPreferredPhys(Register VirtReg) const
returns true if VirtReg is assigned to its preferred physreg.
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
@ RS_New
Newly created live range that has never been queued.
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
void enqueue(const LiveInterval *LI)
enqueue - Add VirtReg to the priority queue of unassigned registers.
bool isSpillable() const
isSpillable - Can this interval be spilled?
void unassign(const LiveInterval &VirtReg)
Unassign VirtReg from its PhysReg.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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...
bool hasKnownPreference(Register VirtReg) const
returns true if VirtReg has a known preferred register.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const
Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
LiveIntervalUnion * getLiveUnions()
Directly access the live interval unions per regunit.
Reg
All possible values of the reg field in the ModR/M byte.
float getBlockFreqRelativeToEntryBlock(const MachineBasicBlock *MBB) const
Compute the frequency of the block, relative to the entry block.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const
@ RS_Split
Attempt live range splitting if assignment is impossible.
Additional information about basic blocks where the current variable is live.
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)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
void iterate()
iterate - Update the network iteratively until convergence, or new bundles are found.
static uint64_t getMaxFrequency()
Returns the maximum possible frequency, the saturation value.
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
MCRegister selectOrSplit(const LiveInterval &, SmallVectorImpl< Register > &) override
bool TimePassesIsEnabled
If the user specifies the -time-passes argument on an LLVM tool command line then the value of this b...
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
A description of a memory reference used in the backend.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
static constexpr unsigned NoRegister
@ RS_Spill
Live range will be spilled. No more splitting will be attempted.
virtual unsigned getCSRFirstUseCost() const
Allow the target to override the cost of using a callee-saved register for the first time.
DiagnosticInfoOptimizationBase::Argument NV
void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)
addConstraints - Add constraints and biases.
LLVM_NODISCARD T pop_back_val()
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
SplitEditor - Edit machine code and LiveIntervals for live range splitting.
SlotIndex FirstDef
First non-phi valno->def, or SlotIndex().
unsigned const TargetRegisterInfo * TRI
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...
static const char TimerGroupDescription[]
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
INITIALIZE_PASS_BEGIN(RAGreedy, "greedy", "Greedy Register Allocator", false, false) INITIALIZE_PASS_END(RAGreedy
SmallPtrSet< MachineInstr *, 2 > Uses
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
@ SM_Size
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.
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.
ArrayRef< Register > regs() const
iterator_range< reg_instr_nodbg_iterator > reg_nodbg_instructions(Register Reg) const
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
bool runOnMachineFunction(MachineFunction &mf) override
Perform register allocation.
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 contains(Register Reg) const
Return true if the specified register is included in this register class.
void aboutToRemoveInterval(const LiveInterval &) override
Method called when the allocator is about to remove a LiveInterval.
TargetInstrInfo - Interface to description of machine instruction set.
Register get(unsigned idx) const
bool ChangesValue
True when this block changes the value of the live range.
void init(MachineFunction *mf, LiveIntervalUnion *liuarray, SlotIndexes *indexes, LiveIntervals *lis, const TargetRegisterInfo *tri)
init - Prepare cache for a new function.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
static cl::opt< unsigned > LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden, cl::desc("Last chance recoloring max depth"), cl::init(5))
Itanium Name Demangler i e convert the string _Z1fv into f()". You can also use the CRTP base ManglingParser to perform some simple analysis on the mangled name
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
virtual void spill(LiveRangeEdit &LRE)=0
spill - Spill the LRE.getParent() live interval.
@ RS_Done
There is nothing more we can do to this live range.
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
@ SM_Partition
SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange's.
Segments::const_iterator const_iterator
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Represent the analysis usage information of a pass.
float MaxWeight
Maximum spill weight evicted.
const uint8_t AllocationPriority
Classes with a higher priority value are assigned first by register allocators using a greedy heurist...
Cost of evicting interference - used by default advisor, and the eviction chain heuristic in RegAlloc...
const HexagonInstrInfo * TII
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 GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineOperand class - Representation of each machine instruction operand.
void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat)
bool finish()
finish - Compute the optimal spill code placement given the constraints.
STATISTIC(NumFunctions, "Total number of functions")
bool isPhysRegUsed(MCRegister PhysReg) const
Returns true if the given PhysReg has any live intervals assigned.
int getNumOccurrences() const
SlotIndex first()
first - Return the starting index of the first interfering range in the current block.
Analysis containing CSE Info
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.
LiveInterval - This class represents the liveness of a register, or stack slot.
BlockFrequency getBlockFrequency(unsigned Number) const
getBlockFrequency - Return the estimated block execution frequency per function invocation.
unsigned getNumBundles() const
getNumBundles - Return the total number of bundles in the CFG.
RegisterClassInfo RegClassInfo
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
SlotIndex - An opaque wrapper around machine indexes.
SegmentIter find(SlotIndex x)
uint8_t getMinCost(const TargetRegisterClass *RC) const
Get the minimum register cost in RC's allocation order.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
bool isProperSubClass(const TargetRegisterClass *RC) const
isProperSubClass - Returns true if RC has a legal super-class with more allocatable registers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
unsigned Number
Basic block number (from MBB::getNumber()).
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
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...
LiveIntervalUnion::Query & query(const LiveRange &LR, MCRegister RegUnit)
Query a line of the assigned virtual register matrix directly.
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
static const char TimerGroupName[]
BorderConstraint Entry
Constraint on block entry.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
ArrayRef< unsigned > getRecentPositive()
getRecentPositive - Return an array of bundles that became positive during the previous call to scanA...
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
@ PrefReg
Block entry/exit prefers a register.
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
bool regsOverlap(Register RegA, Register RegB) const
Returns true if the two registers are equal or alias each other.
SlotIndex LastInstr
Last instr accessing current reg.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
char & RAGreedyID
Greedy register allocator.
bool LiveOut
Current reg is live out.
void getAnalysisUsage(AnalysisUsage &AU) const override
RAGreedy analysis usage.
This class represents the liveness of a register, stack slot, etc.
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
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)
bool checkRegMaskInterference(const LiveInterval &VirtReg, MCRegister PhysReg=MCRegister::NoRegister)
Check for regmask interference only.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
This is an important class for using LLVM in a threaded context.
std::function< bool(const TargetRegisterInfo &TRI, const TargetRegisterClass &RC)> RegClassFilterFunc
RAGreedy(const RegClassFilterFunc F=allocateAllRegClasses)
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
MCRegister getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)
addPrefSpill - Add PrefSpill constraints to all blocks listed.
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
virtual bool reverseLocalAssignment() const
Allow the target to reverse allocation order of local live ranges.
initializer< Ty > init(const Ty &Val)
void moveToBlock(unsigned MBBNum)
moveTo - Move cursor to basic block MBBNum.
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...
MachineRegisterInfo * MRI
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
virtual bool regClassPriorityTrumpsGlobalness(const MachineFunction &MF) const
When prioritizing live ranges in register allocation, if this hook returns true then the AllocationPr...
Greedy Register Allocator
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const LiveInterval * dequeue() override
dequeue - Return the next unassigned register, or NULL.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
SlotIndex last()
last - Return the ending index of the last interfering range in the current block.
print Print MemDeps of function
ArrayRef< MCPhysReg > getOrder() const
Get the allocation order without reordered hints.
Register getReg() const
getReg - Returns the register number.
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)
@ PrefSpill
Block entry/exit prefers a stack slot.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
void addLinks(ArrayRef< unsigned > Links)
addLinks - Add transparent blocks with the given numbers.
LiveSegments::iterator SegmentIter
@ DontCare
Block doesn't care / variable not live.
LiveInterval & getInterval(Register Reg)
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...
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
@ IK_VirtReg
Virtual register interference.
@ InstrDist
The default distance between instructions as returned by distance().
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...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
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))
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
SlotIndex getLastIndex()
Returns the base index of the last slot in this analysis.
iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
void setPreservesCFG()
This function should be called by the pass, iff they do not:
virtual void postOptimization()
This would be a win on but not x86 or ppc64 Shrink
@ SM_Speed
SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
@ RS_Assign
Only attempt assignment and eviction. Then requeue as RS_Split.
InterferenceKind checkInterference(const LiveInterval &VirtReg, MCRegister PhysReg)
Check for interference before assigning VirtReg to PhysReg.
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
raw_ostream & printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const
unsigned BrokenHints
Total number of broken hints.
const SmallVectorImpl< const LiveInterval * > & interferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void prepare(BitVector &RegBundles)
prepare - Reset state and prepare for a new spill placement computation.
Cursor - The primary query interface for the block interference cache.
Wrapper class representing virtual and physical registers.
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
@ MustSpill
A register is impossible, variable must be spilled.
Optional< unsigned > getOrderLimit(const LiveInterval &VirtReg, const AllocationOrder &Order, unsigned CostPerUseLimit) const
iterator_range< def_iterator > def_operands(Register Reg) const
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
bool scanActiveBundles()
scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks,...
bool test(unsigned Idx) const
Register getSimpleHint(Register VReg) const
getSimpleHint - same as getRegAllocationHint except it will only return a target independent hint.
virtual bool shouldUseDeferredSpillingForVirtReg(const MachineFunction &MF, const LiveInterval &VirtReg) const
Deferred spilling delays the spill insertion of a virtual register after every other allocation.
Function & getFunction()
Return the LLVM function that this machine code represents.
block placement Basic Block Placement Stats
RegAllocBase provides the register allocation driver and interface that can be extended to add intere...
@ RS_Memory
Live range is in memory.
void assign(size_type NumElts, ValueParamT Elt)
This class is basically a combination of TimeRegion and Timer.
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 ...
bool isHint(Register Reg) const
Return true if Reg is a preferred physical register.
bool isSpillSlotObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a spill slot.
int getInstrDistance(SlotIndex other) const
Return the scaled distance from this index to the given one, where all slots on the same instruction ...
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
MCRegister getLastCalleeSavedAlias(MCRegister PhysReg) const
getLastCalleeSavedAlias - Returns the last callee saved register that overlaps PhysReg,...
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
unsigned getMaxCursors() const
getMaxCursors - Return the maximum number of concurrent cursors that can be supported.
Query interferences between a single live virtual register and a live interval union.
Register canReassign(const LiveInterval &VirtReg, Register PrevReg) const
bool hasInterference()
hasInterference - Return true if the current block has any interference.
@ RS_Split2
Attempt more aggressive live range splitting that is guaranteed to make progress.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
BorderConstraint Exit
Constraint on block exit.
size_t size() const
size - Get the array size.
Align max(MaybeAlign Lhs, Align Rhs)
ArrayRef< unsigned > getBlocks(unsigned Bundle) const
getBlocks - Return an array of blocks that are connected to Bundle.
static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
bool isUnusedCalleeSavedReg(MCRegister PhysReg) const
Returns true if the given PhysReg is a callee saved register and has not been used for allocation yet...
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 bool VerifyEnabled
VerifyEnabled - True when -verify-regalloc is given.
FunctionPass class - This class is used to implement most global optimizations.
void assign(const LiveInterval &VirtReg, MCRegister PhysReg)
Assign VirtReg to PhysReg.
static bool hasTiedDef(MachineRegisterInfo *MRI, unsigned reg)
Return true if reg has any tied def operand.
static AllocationOrder create(unsigned VirtReg, const VirtRegMap &VRM, const RegisterClassInfo &RegClassInfo, const LiveRegMatrix *Matrix)
Create a new AllocationOrder for VirtReg.
AnalysisUsage & addRequired()
bool hasInterval(Register Reg) const
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
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.
uint64_t getEntryFreq() const
Divide a block's BlockFrequency::getFrequency() value by this value to obtain the entry block - relat...
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
BlockConstraint - Entry and exit constraints for a basic block.
const RegClassFilterFunc ShouldAllocateClass
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...
A Use represents the edge between a Value definition and its users.
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
Wrapper class representing physical registers. Should be passed by value.
unsigned getBundle(unsigned N, bool Out) const
getBundle - Return the ingoing (Out = false) or outgoing (Out = true) bundle number for basic block N
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))
Spiller & spiller() override