83 #define DEBUG_TYPE "regalloc" 85 STATISTIC(NumGlobalSplits,
"Number of split global live ranges");
86 STATISTIC(NumLocalSplits,
"Number of split local live ranges");
87 STATISTIC(NumEvicted,
"Number of interferences evicted");
91 cl::desc(
"Spill mode for splitting live ranges"),
99 cl::desc(
"Last chance recoloring max depth"),
104 cl::desc(
"Last chance recoloring maximum number of considered" 105 " interference at a time"),
110 cl::desc(
"Exhaustive Search for registers bypassing the depth " 111 "and interference cutoffs of last chance recoloring"),
116 cl::desc(
"Local reassignment can yield better allocation decisions, but " 117 "may be compile time intensive"),
122 cl::desc(
"Instead of spilling a variable right away, defer the actual " 123 "code insertion to the end of the allocation. That way the " 124 "allocator might still find a suitable coloring for this " 125 "variable because of other evicted variables."),
130 cl::desc(
"A threshold of live range size which may cause " 131 "high compile time cost in global splitting."),
137 cl::desc(
"Cost for first time use of callee-saved register."),
142 cl::desc(
"Consider the cost of local intervals created by a split " 143 "candidate when choosing the best split candidate."),
155 using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>;
179 std::unique_ptr<Spiller> SpillerInstance;
181 unsigned NextCascade;
196 enum LiveRangeStage {
241 static const char *
const StageName[];
246 LiveRangeStage Stage = RS_New;
249 unsigned Cascade = 0;
256 LiveRangeStage getStage(
const LiveInterval &VirtReg)
const {
257 return ExtraRegInfo[VirtReg.
reg].Stage;
260 void setStage(
const LiveInterval &VirtReg, LiveRangeStage Stage) {
261 ExtraRegInfo.
resize(
MRI->getNumVirtRegs());
262 ExtraRegInfo[VirtReg.
reg].Stage = Stage;
265 template<
typename Iterator>
266 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
267 ExtraRegInfo.
resize(
MRI->getNumVirtRegs());
268 for (;Begin != End; ++Begin) {
269 unsigned Reg = *Begin;
270 if (ExtraRegInfo[Reg].Stage == RS_New)
271 ExtraRegInfo[
Reg].Stage = NewStage;
276 struct EvictionCost {
277 unsigned BrokenHints = 0;
280 EvictionCost() =
default;
282 bool isMax()
const {
return BrokenHints == ~0u; }
284 void setMax() { BrokenHints = ~0u; }
286 void setBrokenHints(
unsigned NHints) { BrokenHints = NHints; }
289 return std::tie(BrokenHints, MaxWeight) <
290 std::tie(O.BrokenHints, O.MaxWeight);
296 class EvictionTrack {
300 std::pair<
unsigned ,
unsigned >;
306 EvicteeInfo Evictees;
310 void clear() { Evictees.clear(); }
317 void clearEvicteeInfo(
unsigned Evictee) { Evictees.erase(Evictee); }
324 void addEviction(
unsigned PhysReg,
unsigned Evictor,
unsigned Evictee) {
325 Evictees[Evictee].first = Evictor;
326 Evictees[Evictee].second = PhysReg;
333 EvictorInfo getEvictor(
unsigned Evictee) {
334 if (Evictees.count(Evictee)) {
335 return Evictees[Evictee];
338 return EvictorInfo(0, 0);
343 EvictionTrack LastEvicted;
346 std::unique_ptr<SplitAnalysis> SA;
347 std::unique_ptr<SplitEditor> SE;
356 struct GlobalSplitCandidate {
375 ActiveBlocks.
clear();
381 for (
unsigned i : LiveBundles.
set_bits())
395 enum :
unsigned {
NoCand = ~0u };
406 bool EnableLocalReassign;
410 bool EnableAdvancedRASplitCost;
419 StringRef getPassName()
const override {
return "Greedy Register Allocator"; }
423 void releaseMemory()
override;
424 Spiller &spiller()
override {
return *SpillerInstance; }
442 SmallVirtRegSet &,
unsigned = 0);
444 bool LRE_CanEraseVirtReg(
unsigned)
override;
445 void LRE_WillShrinkVirtReg(
unsigned)
override;
446 void LRE_DidCloneVirtReg(
unsigned,
unsigned)
override;
453 bool growRegion(GlobalSplitCandidate &Cand);
454 bool splitCanCauseEvictionChain(
unsigned Evictee, GlobalSplitCandidate &Cand,
457 bool splitCanCauseLocalSpill(
unsigned VirtRegToSplit,
458 GlobalSplitCandidate &Cand,
unsigned BBNumber,
462 bool *CanCauseEvictionChain);
463 bool calcCompactRegion(GlobalSplitCandidate&);
466 unsigned canReassign(
LiveInterval &VirtReg,
unsigned PrevReg);
468 bool canEvictInterference(
LiveInterval&,
unsigned,
bool, EvictionCost&);
469 bool canEvictInterferenceInRange(
LiveInterval &VirtReg,
unsigned PhysReg,
471 EvictionCost &MaxCost);
477 bool mayRecolorAllInterferences(
unsigned PhysReg,
LiveInterval &VirtReg,
478 SmallLISet &RecoloringCandidates,
479 const SmallVirtRegSet &FixedRegisters);
487 unsigned isSplitBenefitWorthCost(
LiveInterval &VirtReg);
489 unsigned calculateRegionSplitCost(
LiveInterval &VirtReg,
492 unsigned &NumCands,
bool IgnoreCSR,
493 bool *CanCauseEvictionChain =
nullptr);
495 unsigned doRegionSplit(
LiveInterval &VirtReg,
unsigned BestCand,
501 unsigned PhysReg,
unsigned &CostPerUseLimit,
503 void initializeCSRCost();
514 SmallVirtRegSet &,
unsigned);
516 SmallVirtRegSet &,
unsigned);
518 void tryHintsRecoloring();
531 : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
536 void collectHintInfo(
unsigned, HintsInfo &);
538 bool isUnusedCalleeSavedReg(
unsigned PhysReg)
const;
541 void reportNumberOfSplillsReloads(
MachineLoop *L,
unsigned &Reloads,
542 unsigned &FoldedReloads,
unsigned &Spills,
543 unsigned &FoldedSpills);
546 void reportNumberOfSplillsReloads() {
548 unsigned Reloads, FoldedReloads, Spills, FoldedSpills;
549 reportNumberOfSplillsReloads(L, Reloads, FoldedReloads, Spills,
561 "Greedy Register Allocator",
false,
false)
579 const char *
const RAGreedy::StageName[] = {
595 return new RAGreedy();
633 bool RAGreedy::LRE_CanEraseVirtReg(
unsigned VirtReg) {
635 if (VRM->hasPhys(VirtReg)) {
637 aboutToRemoveInterval(LI);
648 void RAGreedy::LRE_WillShrinkVirtReg(
unsigned VirtReg) {
649 if (!VRM->hasPhys(VirtReg))
658 void RAGreedy::LRE_DidCloneVirtReg(
unsigned New,
unsigned Old) {
667 ExtraRegInfo[Old].Stage = RS_Assign;
668 ExtraRegInfo.
grow(New);
669 ExtraRegInfo[New] = ExtraRegInfo[Old];
672 void RAGreedy::releaseMemory() {
673 SpillerInstance.reset();
674 ExtraRegInfo.
clear();
678 void RAGreedy::enqueue(
LiveInterval *LI) { enqueue(Queue, LI); }
680 void RAGreedy::enqueue(PQueue &CurQueue,
LiveInterval *LI) {
684 const unsigned Reg = LI->
reg;
686 "Can only enqueue virtual registers");
689 ExtraRegInfo.
grow(Reg);
690 if (ExtraRegInfo[Reg].Stage == RS_New)
691 ExtraRegInfo[
Reg].Stage = RS_Assign;
693 if (ExtraRegInfo[Reg].Stage == RS_Split) {
697 }
else if (ExtraRegInfo[Reg].Stage == RS_Memory) {
702 static unsigned MemOp = 0;
709 bool ForceGlobal = !ReverseLocal &&
712 if (ExtraRegInfo[Reg].Stage == RS_Assign && !ForceGlobal && !LI->
empty() &&
713 LIS->intervalIsInOneMBB(*LI)) {
730 Prio = (1u << 29) + Size;
736 if (VRM->hasKnownPreference(Reg))
741 CurQueue.push(std::make_pair(Prio, ~Reg));
744 LiveInterval *RAGreedy::dequeue() {
return dequeue(Queue); }
747 if (CurQueue.empty())
749 LiveInterval *LI = &LIS->getInterval(~CurQueue.top().second);
764 while ((PhysReg = Order.
next()))
765 if (!
Matrix->checkInterference(VirtReg, PhysReg))
767 if (!PhysReg || Order.
isHint())
774 if (
unsigned Hint =
MRI->getSimpleHint(VirtReg.
reg))
777 EvictionCost MaxCost;
778 MaxCost.setBrokenHints(1);
779 if (canEvictInterference(VirtReg, Hint,
true, MaxCost)) {
780 evictInterference(VirtReg, Hint, NewVRegs);
785 SetOfBrokenHints.
insert(&VirtReg);
797 unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost);
798 return CheapReg ? CheapReg : PhysReg;
805 unsigned RAGreedy::canReassign(
LiveInterval &VirtReg,
unsigned PrevReg) {
808 while ((PhysReg = Order.
next())) {
809 if (PhysReg == PrevReg)
813 for (; Units.
isValid(); ++Units) {
816 if (subQ.checkInterference())
843 bool RAGreedy::shouldEvict(
LiveInterval &A,
bool IsHint,
845 bool CanSplit = getStage(B) < RS_Spill;
849 if (CanSplit && IsHint && !BreaksHint)
868 bool RAGreedy::canEvictInterference(
LiveInterval &VirtReg,
unsigned PhysReg,
869 bool IsHint, EvictionCost &MaxCost) {
874 bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
883 unsigned Cascade = ExtraRegInfo[VirtReg.
reg].Cascade;
885 Cascade = NextCascade;
898 "Only expecting virtual register interference from query");
900 if (getStage(*Intf) == RS_Done)
910 RegClassInfo.getNumAllocatableRegs(
MRI->getRegClass(VirtReg.
reg)) <
911 RegClassInfo.getNumAllocatableRegs(
MRI->getRegClass(Intf->
reg)));
913 unsigned IntfCascade = ExtraRegInfo[Intf->
reg].Cascade;
914 if (Cascade <= IntfCascade) {
919 Cost.BrokenHints += 10;
922 bool BreaksHint = VRM->hasPreferredPhys(Intf->
reg);
924 Cost.BrokenHints += BreaksHint;
927 if (!(Cost < MaxCost))
932 if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
937 if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
938 (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) {
957 bool RAGreedy::canEvictInterferenceInRange(
LiveInterval &VirtReg,
960 EvictionCost &MaxCost) {
978 if (getStage(*Intf) == RS_Done)
982 bool BreaksHint = VRM->hasPreferredPhys(Intf->
reg);
984 Cost.BrokenHints += BreaksHint;
987 if (!(Cost < MaxCost))
992 if (Cost.MaxWeight == 0)
1010 unsigned RAGreedy::getCheapestEvicteeWeight(
const AllocationOrder &Order,
1013 float *BestEvictweight) {
1014 EvictionCost BestEvictCost;
1015 BestEvictCost.setMax();
1016 BestEvictCost.MaxWeight = VirtReg.
weight;
1017 unsigned BestEvicteePhys = 0;
1020 for (
auto PhysReg : Order.
getOrder()) {
1022 if (!canEvictInterferenceInRange(VirtReg, PhysReg, Start, End,
1027 BestEvicteePhys = PhysReg;
1029 *BestEvictweight = BestEvictCost.MaxWeight;
1030 return BestEvicteePhys;
1036 void RAGreedy::evictInterference(
LiveInterval &VirtReg,
unsigned PhysReg,
1041 unsigned Cascade = ExtraRegInfo[VirtReg.
reg].Cascade;
1043 Cascade = ExtraRegInfo[VirtReg.
reg].Cascade = NextCascade++;
1046 <<
" interference: Cascade " << Cascade <<
'\n');
1062 for (
unsigned i = 0, e = Intfs.
size(); i != e; ++i) {
1065 if (!VRM->hasPhys(Intf->
reg))
1068 LastEvicted.addEviction(PhysReg, VirtReg.
reg, Intf->
reg);
1071 assert((ExtraRegInfo[Intf->
reg].Cascade < Cascade ||
1073 "Cannot decrease cascade number, illegal eviction");
1074 ExtraRegInfo[Intf->
reg].Cascade = Cascade;
1082 bool RAGreedy::isUnusedCalleeSavedReg(
unsigned PhysReg)
const {
1083 unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg);
1087 return !
Matrix->isPhysRegUsed(PhysReg);
1097 unsigned CostPerUseLimit) {
1102 EvictionCost BestCost;
1104 unsigned BestPhys = 0;
1109 if (CostPerUseLimit < ~0u) {
1110 BestCost.BrokenHints = 0;
1111 BestCost.MaxWeight = VirtReg.
weight;
1115 unsigned MinCost = RegClassInfo.getMinCost(RC);
1116 if (MinCost >= CostPerUseLimit) {
1118 << MinCost <<
", no cheaper registers to be found.\n");
1125 OrderLimit = RegClassInfo.getLastCostChange(RC);
1132 while (
unsigned PhysReg = Order.
next(OrderLimit)) {
1137 if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {
1139 dbgs() <<
printReg(PhysReg, TRI) <<
" would clobber CSR " 1140 <<
printReg(RegClassInfo.getLastCalleeSavedAlias(PhysReg),
TRI)
1145 if (!canEvictInterference(VirtReg, PhysReg,
false, BestCost))
1159 evictInterference(VirtReg, BestPhys, NewVRegs);
1179 for (
unsigned i = 0; i != UseBlocks.
size(); ++i) {
1187 !LIS->getInstructionFromIndex(BI.
LastInstr)->isImplicitDef())
1214 SA->getFirstSplitPoint(BC.
Number)))
1220 if (Intf.
last() >= SA->getLastSplitPoint(BC.
Number)) {
1247 const unsigned GroupSize = 8;
1249 unsigned TBS[GroupSize];
1250 unsigned B = 0,
T = 0;
1252 for (
unsigned i = 0; i != Blocks.
size(); ++i) {
1253 unsigned Number = Blocks[i];
1257 assert(
T < GroupSize &&
"Array overflow");
1259 if (++
T == GroupSize) {
1266 assert(B < GroupSize &&
"Array overflow");
1271 if (!MBB->
empty() &&
1273 SA->getFirstSplitPoint(Number)))
1282 if (Intf.
last() >= SA->getLastSplitPoint(Number))
1287 if (++B == GroupSize) {
1298 bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
1300 BitVector Todo = SA->getThroughBlocks();
1302 unsigned AddedTo = 0;
1304 unsigned Visited = 0;
1310 for (
int i = 0, e = NewBundles.
size(); i != e; ++i) {
1311 unsigned Bundle = NewBundles[i];
1316 unsigned Block = *
I;
1317 if (!Todo.
test(Block))
1328 if (ActiveBlocks.
size() == AddedTo)
1333 auto NewBlocks =
makeArrayRef(ActiveBlocks).slice(AddedTo);
1335 if (!addThroughConstraints(Cand.Intf, NewBlocks))
1341 AddedTo = ActiveBlocks.
size();
1357 bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
1359 if (!SA->getNumThroughBlocks())
1363 Cand.reset(IntfCache, 0);
1369 SpillPlacer->
prepare(Cand.LiveBundles);
1373 if (!addSplitConstraints(Cand.Intf, Cost)) {
1378 if (!growRegion(Cand)) {
1385 if (!Cand.LiveBundles.any()) {
1391 for (
int i : Cand.LiveBundles.set_bits())
1392 dbgs() <<
" EB#" << i;
1403 for (
unsigned i = 0; i != UseBlocks.
size(); ++i) {
1469 bool RAGreedy::splitCanCauseEvictionChain(
unsigned Evictee,
1470 GlobalSplitCandidate &Cand,
1473 EvictionTrack::EvictorInfo VregEvictorInfo = LastEvicted.getEvictor(Evictee);
1474 unsigned Evictor = VregEvictorInfo.first;
1475 unsigned PhysReg = VregEvictorInfo.second;
1478 if (!Evictor || !PhysReg)
1481 float MaxWeight = 0;
1482 unsigned FutureEvictedPhysReg =
1483 getCheapestEvicteeWeight(Order, LIS->getInterval(Evictee),
1484 Cand.Intf.first(), Cand.Intf.last(), &MaxWeight);
1488 if ((PhysReg != Cand.PhysReg) && (PhysReg != FutureEvictedPhysReg))
1491 Cand.Intf.moveToBlock(BBNumber);
1498 if (!LIS->hasInterval(Evictor))
1507 VirtRegAuxInfo VRAI(*MF, *LIS, VRM, getAnalysis<MachineLoopInfo>(), *MBFI);
1508 float splitArtifactWeight =
1510 Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
1511 if (splitArtifactWeight >= 0 && splitArtifactWeight < MaxWeight)
1529 bool RAGreedy::splitCanCauseLocalSpill(
unsigned VirtRegToSplit,
1530 GlobalSplitCandidate &Cand,
1533 Cand.Intf.moveToBlock(BBNumber);
1536 for (
auto PhysReg : Order.
getOrder()) {
1537 if (!
Matrix->checkInterference(Cand.Intf.first().getPrevIndex(),
1538 Cand.Intf.last(), PhysReg))
1543 float CheapestEvictWeight = 0;
1544 unsigned FutureEvictedPhysReg = getCheapestEvicteeWeight(
1545 Order, LIS->getInterval(VirtRegToSplit), Cand.Intf.first(),
1546 Cand.Intf.last(), &CheapestEvictWeight);
1549 if (FutureEvictedPhysReg) {
1550 VirtRegAuxInfo VRAI(*MF, *LIS, VRM, getAnalysis<MachineLoopInfo>(), *MBFI);
1551 float splitArtifactWeight =
1553 Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
1556 if (splitArtifactWeight >= 0 && splitArtifactWeight > CheapestEvictWeight)
1569 BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
1571 bool *CanCauseEvictionChain) {
1573 const BitVector &LiveBundles = Cand.LiveBundles;
1574 unsigned VirtRegToSplit = SA->getParent().reg;
1576 for (
unsigned i = 0; i != UseBlocks.
size(); ++i) {
1583 Cand.Intf.moveToBlock(BC.
Number);
1587 if (EnableAdvancedRASplitCost && Cand.Intf.hasInterference() && BI.
LiveIn &&
1588 BI.
LiveOut && RegIn && RegOut) {
1590 if (CanCauseEvictionChain &&
1591 splitCanCauseEvictionChain(VirtRegToSplit, Cand, BC.
Number, Order)) {
1598 *CanCauseEvictionChain =
true;
1600 }
else if (splitCanCauseLocalSpill(VirtRegToSplit, Cand, BC.
Number,
1616 for (
unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
1617 unsigned Number = Cand.ActiveBlocks[i];
1618 bool RegIn = LiveBundles[Bundles->
getBundle(Number,
false)];
1619 bool RegOut = LiveBundles[Bundles->
getBundle(Number,
true)];
1620 if (!RegIn && !RegOut)
1622 if (RegIn && RegOut) {
1624 Cand.Intf.moveToBlock(Number);
1625 if (Cand.Intf.hasInterference()) {
1631 if (EnableAdvancedRASplitCost && CanCauseEvictionChain &&
1632 splitCanCauseEvictionChain(VirtRegToSplit, Cand, Number, Order)) {
1640 *CanCauseEvictionChain =
true;
1667 const unsigned NumGlobalIntvs = LREdit.
size();
1670 assert(NumGlobalIntvs &&
"No global intervals configured");
1675 unsigned Reg = SA->getParent().reg;
1676 bool SingleInstrs = RegClassInfo.isProperSubClass(
MRI->getRegClass(Reg));
1680 for (
unsigned i = 0; i != UseBlocks.
size(); ++i) {
1683 unsigned IntvIn = 0, IntvOut = 0;
1686 unsigned CandIn = BundleCand[Bundles->
getBundle(Number,
false)];
1688 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1689 IntvIn = Cand.IntvIdx;
1690 Cand.Intf.moveToBlock(Number);
1691 IntfIn = Cand.Intf.first();
1695 unsigned CandOut = BundleCand[Bundles->
getBundle(Number,
true)];
1697 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1698 IntvOut = Cand.IntvIdx;
1699 Cand.Intf.moveToBlock(Number);
1700 IntfOut = Cand.Intf.last();
1705 if (!IntvIn && !IntvOut) {
1707 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1708 SE->splitSingleBlock(BI);
1712 if (IntvIn && IntvOut)
1713 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1715 SE->splitRegInBlock(BI, IntvIn, IntfIn);
1717 SE->splitRegOutBlock(BI, IntvOut, IntfOut);
1723 BitVector Todo = SA->getThroughBlocks();
1724 for (
unsigned c = 0; c != UsedCands.
size(); ++c) {
1726 for (
unsigned i = 0, e = Blocks.
size(); i != e; ++i) {
1727 unsigned Number = Blocks[i];
1728 if (!Todo.
test(Number))
1732 unsigned IntvIn = 0, IntvOut = 0;
1735 unsigned CandIn = BundleCand[Bundles->
getBundle(Number,
false)];
1737 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1738 IntvIn = Cand.IntvIdx;
1739 Cand.Intf.moveToBlock(Number);
1740 IntfIn = Cand.Intf.first();
1743 unsigned CandOut = BundleCand[Bundles->
getBundle(Number,
true)];
1745 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1746 IntvOut = Cand.IntvIdx;
1747 Cand.Intf.moveToBlock(Number);
1748 IntfOut = Cand.Intf.last();
1750 if (!IntvIn && !IntvOut)
1752 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1759 SE->finish(&IntvMap);
1762 ExtraRegInfo.
resize(
MRI->getNumVirtRegs());
1763 unsigned OrigBlocks = SA->getNumLiveBlocks();
1770 for (
unsigned i = 0, e = LREdit.
size(); i != e; ++i) {
1774 if (getStage(Reg) != RS_New)
1779 if (IntvMap[i] == 0) {
1780 setStage(Reg, RS_Spill);
1786 if (IntvMap[i] < NumGlobalIntvs) {
1787 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1788 LLVM_DEBUG(
dbgs() <<
"Main interval covers the same " << OrigBlocks
1789 <<
" blocks as original.\n");
1791 setStage(Reg, RS_Split2);
1801 MF->
verify(
this,
"After splitting live range around region");
1807 unsigned RAGreedy::isSplitBenefitWorthCost(
LiveInterval &VirtReg) {
1817 if (!isSplitBenefitWorthCost(VirtReg))
1819 unsigned NumCands = 0;
1824 bool HasCompact = calcCompactRegion(GlobalCand.
front());
1832 BestCost = SpillCost;
1837 bool CanCauseEvictionChain =
false;
1839 calculateRegionSplitCost(VirtReg, Order, BestCost, NumCands,
1840 false , &CanCauseEvictionChain);
1846 if (HasCompact && (BestCost > SpillCost) && (BestCand !=
NoCand) &&
1847 CanCauseEvictionChain) {
1852 if (!HasCompact && BestCand ==
NoCand)
1855 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1858 unsigned RAGreedy::calculateRegionSplitCost(
LiveInterval &VirtReg,
1861 unsigned &NumCands,
bool IgnoreCSR,
1862 bool *CanCauseEvictionChain) {
1863 unsigned BestCand =
NoCand;
1865 while (
unsigned PhysReg = Order.
next()) {
1866 if (IgnoreCSR && isUnusedCalleeSavedReg(PhysReg))
1872 unsigned WorstCount = ~0u;
1874 for (
unsigned i = 0; i != NumCands; ++i) {
1875 if (i == BestCand || !GlobalCand[i].PhysReg)
1877 unsigned Count = GlobalCand[i].LiveBundles.count();
1878 if (Count < WorstCount) {
1884 GlobalCand[Worst] = GlobalCand[NumCands];
1885 if (BestCand == NumCands)
1889 if (GlobalCand.
size() <= NumCands)
1890 GlobalCand.
resize(NumCands+1);
1891 GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1892 Cand.reset(IntfCache, PhysReg);
1894 SpillPlacer->
prepare(Cand.LiveBundles);
1896 if (!addSplitConstraints(Cand.Intf, Cost)) {
1902 if (Cost >= BestCost) {
1905 dbgs() <<
" worse than no bundles\n";
1907 dbgs() <<
" worse than " 1908 <<
printReg(GlobalCand[BestCand].PhysReg, TRI) <<
'\n';
1912 if (!growRegion(Cand)) {
1920 if (!Cand.LiveBundles.any()) {
1925 bool HasEvictionChain =
false;
1926 Cost += calcGlobalSplitCost(Cand, Order, &HasEvictionChain);
1928 dbgs() <<
", total = ";
1930 for (
int i : Cand.LiveBundles.set_bits())
1931 dbgs() <<
" EB#" << i;
1934 if (Cost < BestCost) {
1935 BestCand = NumCands;
1939 if (CanCauseEvictionChain)
1940 *CanCauseEvictionChain = HasEvictionChain;
1945 if (CanCauseEvictionChain && BestCand !=
NoCand) {
1950 if (!(*CanCauseEvictionChain))
1958 unsigned RAGreedy::doRegionSplit(
LiveInterval &VirtReg,
unsigned BestCand,
1963 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM,
this, &DeadRemats);
1970 if (BestCand !=
NoCand) {
1971 GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1972 if (
unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1974 Cand.IntvIdx = SE->openIntv();
1976 << B <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1983 GlobalSplitCandidate &Cand = GlobalCand.
front();
1984 assert(!Cand.PhysReg &&
"Compact region has no physreg");
1985 if (
unsigned B = Cand.getBundles(BundleCand, 0)) {
1987 Cand.IntvIdx = SE->openIntv();
1989 <<
" bundles, intv " << Cand.IntvIdx <<
".\n");
1994 splitAroundRegion(LREdit, UsedCands);
2007 assert(&SA->getParent() == &VirtReg &&
"Live range wasn't analyzed");
2008 unsigned Reg = VirtReg.
reg;
2009 bool SingleInstrs = RegClassInfo.isProperSubClass(
MRI->getRegClass(Reg));
2010 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM,
this, &DeadRemats);
2013 for (
unsigned i = 0; i != UseBlocks.
size(); ++i) {
2015 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
2016 SE->splitSingleBlock(BI);
2024 SE->finish(&IntvMap);
2029 ExtraRegInfo.
resize(
MRI->getNumVirtRegs());
2033 for (
unsigned i = 0, e = LREdit.
size(); i != e; ++i) {
2035 if (getStage(LI) == RS_New && IntvMap[i] == 0)
2036 setStage(LI, RS_Spill);
2040 MF->
verify(
this,
"After splitting live range around basic blocks");
2054 assert(SuperRC &&
"Invalid register class");
2076 if (!RegClassInfo.isProperSubClass(CurRC))
2081 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM,
this, &DeadRemats);
2085 if (Uses.
size() <= 1)
2089 <<
" individual instrs.\n");
2098 for (
unsigned i = 0; i != Uses.
size(); ++i) {
2100 if (
MI->isFullCopy() ||
2101 SuperRCNumAllocatableRegs ==
2108 SlotIndex SegStart = SE->enterIntvBefore(Uses[i]);
2109 SlotIndex SegStop = SE->leaveIntvAfter(Uses[i]);
2110 SE->useIntv(SegStart, SegStop);
2113 if (LREdit.
empty()) {
2119 SE->finish(&IntvMap);
2121 ExtraRegInfo.
resize(
MRI->getNumVirtRegs());
2124 setStage(LREdit.
begin(), LREdit.
end(), RS_Spill);
2137 void RAGreedy::calcGapWeights(
unsigned PhysReg,
2139 assert(SA->getUseBlocks().size() == 1 &&
"Not a local interval");
2142 const unsigned NumGaps = Uses.
size()-1;
2146 BI.LiveIn ? BI.FirstInstr.
getBaseIndex() : BI.FirstInstr;
2150 GapWeight.
assign(NumGaps, 0.0f);
2154 if (!
Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units)
2155 .checkInterference())
2166 Matrix->getLiveUnions()[*Units] .find(StartIdx);
2167 for (
unsigned Gap = 0; IntI.
valid() && IntI.
start() < StopIdx; ++IntI) {
2169 while (Uses[Gap+1].getBoundaryIndex() < IntI.
start())
2170 if (++Gap == NumGaps)
2176 const float weight = IntI.
value()->weight;
2177 for (; Gap != NumGaps; ++Gap) {
2178 GapWeight[Gap] =
std::max(GapWeight[Gap], weight);
2179 if (Uses[Gap+1].getBaseIndex() >= IntI.
stop())
2189 const LiveRange &LR = LIS->getRegUnit(*Units);
2194 for (
unsigned Gap = 0; I != E && I->start < StopIdx; ++
I) {
2195 while (Uses[Gap+1].getBoundaryIndex() < I->start)
2196 if (++Gap == NumGaps)
2201 for (; Gap != NumGaps; ++Gap) {
2203 if (Uses[Gap+1].getBaseIndex() >= I->
end)
2219 if (SA->getUseBlocks().size() != 1)
2232 if (Uses.
size() <= 2)
2234 const unsigned NumGaps = Uses.
size()-1;
2237 dbgs() <<
"tryLocalSplit: ";
2238 for (
unsigned i = 0, e = Uses.
size(); i != e; ++i)
2239 dbgs() <<
' ' << Uses[i];
2246 if (
Matrix->checkRegMaskInterference(VirtReg)) {
2253 unsigned re = RMS.
size();
2254 for (
unsigned i = 0; i != NumGaps && ri != re; ++i) {
2265 RegMaskGaps.push_back(i);
2292 bool ProgressRequired = getStage(VirtReg) >= RS_Split2;
2295 unsigned BestBefore = NumGaps;
2296 unsigned BestAfter = 0;
2299 const float blockFreq =
2305 while (
unsigned PhysReg = Order.
next()) {
2308 calcGapWeights(PhysReg, GapWeight);
2311 if (
Matrix->checkRegMaskInterference(VirtReg, PhysReg))
2312 for (
unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i)
2319 unsigned SplitBefore = 0, SplitAfter = 1;
2323 float MaxGap = GapWeight[0];
2327 const bool LiveBefore = SplitBefore != 0 || BI.
LiveIn;
2328 const bool LiveAfter = SplitAfter != NumGaps || BI.
LiveOut;
2331 <<
'-' << Uses[SplitAfter] <<
" i=" << MaxGap);
2334 if (!LiveBefore && !LiveAfter) {
2342 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
2345 bool Legal = !ProgressRequired || NewGaps < NumGaps;
2354 blockFreq * (NewGaps + 1),
2355 Uses[SplitBefore].distance(Uses[SplitAfter]) +
2361 if (EstWeight * Hysteresis >= MaxGap) {
2363 float Diff = EstWeight - MaxGap;
2364 if (Diff > BestDiff) {
2366 BestDiff = Hysteresis * Diff;
2367 BestBefore = SplitBefore;
2368 BestAfter = SplitAfter;
2375 if (++SplitBefore < SplitAfter) {
2378 if (GapWeight[SplitBefore - 1] >= MaxGap) {
2379 MaxGap = GapWeight[SplitBefore];
2380 for (
unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
2381 MaxGap =
std::max(MaxGap, GapWeight[i]);
2389 if (SplitAfter >= NumGaps) {
2395 MaxGap =
std::max(MaxGap, GapWeight[SplitAfter++]);
2400 if (BestBefore == NumGaps)
2403 LLVM_DEBUG(
dbgs() <<
"Best local split range: " << Uses[BestBefore] <<
'-' 2404 << Uses[BestAfter] <<
", " << BestDiff <<
", " 2405 << (BestAfter - BestBefore + 1) <<
" instrs\n");
2407 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM,
this, &DeadRemats);
2411 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
2412 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]);
2413 SE->useIntv(SegStart, SegStop);
2415 SE->finish(&IntvMap);
2421 bool LiveBefore = BestBefore != 0 || BI.
LiveIn;
2422 bool LiveAfter = BestAfter != NumGaps || BI.
LiveOut;
2423 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
2424 if (NewGaps >= NumGaps) {
2426 assert(!ProgressRequired &&
"Didn't make progress when it was required.");
2427 for (
unsigned i = 0, e = IntvMap.
size(); i != e; ++i)
2428 if (IntvMap[i] == 1) {
2429 setStage(LIS->getInterval(LREdit.
get(i)), RS_Split2);
2449 if (getStage(VirtReg) >= RS_Spill)
2453 if (LIS->intervalIsInOneMBB(VirtReg)) {
2456 SA->analyze(&VirtReg);
2457 unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
2458 if (PhysReg || !NewVRegs.
empty())
2460 return tryInstructionSplit(VirtReg, Order, NewVRegs);
2466 SA->analyze(&VirtReg);
2472 if (SA->didRepairRange()) {
2474 Matrix->invalidateVirtRegs();
2475 if (
unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
2482 if (getStage(VirtReg) < RS_Split2) {
2483 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
2484 if (PhysReg || !NewVRegs.
empty())
2489 return tryBlockSplit(VirtReg, Order, NewVRegs);
2514 RAGreedy::mayRecolorAllInterferences(
unsigned PhysReg,
LiveInterval &VirtReg,
2515 SmallLISet &RecoloringCandidates,
2516 const SmallVirtRegSet &FixedRegisters) {
2526 CutOffInfo |= CO_Interf;
2535 if (((getStage(*Intf) == RS_Done &&
2536 MRI->getRegClass(Intf->
reg) == CurRC) &&
2538 FixedRegisters.count(Intf->
reg)) {
2540 dbgs() <<
"Early abort: the interference is not recolorable.\n");
2543 RecoloringCandidates.insert(Intf);
2588 unsigned RAGreedy::tryLastChanceRecoloring(
LiveInterval &VirtReg,
2591 SmallVirtRegSet &FixedRegisters,
2593 LLVM_DEBUG(
dbgs() <<
"Try last chance recoloring for " << VirtReg <<
'\n');
2596 "Last chance recoloring should really be last chance");
2602 LLVM_DEBUG(
dbgs() <<
"Abort because max depth has been reached.\n");
2603 CutOffInfo |= CO_Depth;
2608 SmallLISet RecoloringCandidates;
2618 while (
unsigned PhysReg = Order.
next()) {
2620 <<
printReg(PhysReg, TRI) <<
'\n');
2621 RecoloringCandidates.clear();
2622 VirtRegToPhysReg.
clear();
2623 CurrentNewVRegs.
clear();
2626 if (
Matrix->checkInterference(VirtReg, PhysReg) >
2629 dbgs() <<
"Some interferences are not with virtual registers.\n");
2636 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
2638 LLVM_DEBUG(
dbgs() <<
"Some interferences cannot be recolored.\n");
2645 PQueue RecoloringQueue;
2646 for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2647 EndIt = RecoloringCandidates.end();
2648 It != EndIt; ++It) {
2649 unsigned ItVirtReg = (*It)->reg;
2650 enqueue(RecoloringQueue, *It);
2651 assert(VRM->hasPhys(ItVirtReg) &&
2652 "Interferences are supposed to be with allocated variables");
2655 VirtRegToPhysReg[ItVirtReg] = VRM->getPhys(ItVirtReg);
2663 Matrix->assign(VirtReg, PhysReg);
2668 SmallVirtRegSet SaveFixedRegisters(FixedRegisters);
2669 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
2670 FixedRegisters, Depth)) {
2672 for (
unsigned NewVReg : CurrentNewVRegs)
2676 Matrix->unassign(VirtReg);
2681 <<
printReg(PhysReg, TRI) <<
'\n');
2684 FixedRegisters = SaveFixedRegisters;
2685 Matrix->unassign(VirtReg);
2692 End = CurrentNewVRegs.
end();
2693 Next != End; ++Next) {
2694 if (RecoloringCandidates.count(&LIS->getInterval(*Next)))
2699 for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2700 EndIt = RecoloringCandidates.end();
2701 It != EndIt; ++It) {
2702 unsigned ItVirtReg = (*It)->reg;
2703 if (VRM->hasPhys(ItVirtReg))
2705 unsigned ItPhysReg = VirtRegToPhysReg[ItVirtReg];
2706 Matrix->assign(**It, ItPhysReg);
2722 bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2724 SmallVirtRegSet &FixedRegisters,
2726 while (!RecoloringQueue.empty()) {
2730 PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters, Depth + 1);
2735 if (PhysReg == ~0u || (!PhysReg && !LI->
empty()))
2739 assert(LI->
empty() &&
"Only empty live-range do not require a register");
2741 <<
" succeeded. Empty LI.\n");
2745 <<
" succeeded with: " <<
printReg(PhysReg, TRI) <<
'\n');
2747 Matrix->assign(*LI, PhysReg);
2748 FixedRegisters.insert(LI->
reg);
2757 unsigned RAGreedy::selectOrSplit(
LiveInterval &VirtReg,
2759 CutOffInfo = CO_None;
2761 SmallVirtRegSet FixedRegisters;
2762 unsigned Reg = selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters);
2763 if (Reg == ~0U && (CutOffInfo != CO_None)) {
2764 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2765 if (CutOffEncountered == CO_Depth)
2766 Ctx.
emitError(
"register allocation failed: maximum depth for recoloring " 2767 "reached. Use -fexhaustive-register-search to skip " 2769 else if (CutOffEncountered == CO_Interf)
2770 Ctx.
emitError(
"register allocation failed: maximum interference for " 2771 "recoloring reached. Use -fexhaustive-register-search " 2773 else if (CutOffEncountered == (CO_Depth | CO_Interf))
2774 Ctx.
emitError(
"register allocation failed: maximum interference and " 2775 "depth for recoloring reached. Use " 2776 "-fexhaustive-register-search to skip cutoffs");
2787 unsigned RAGreedy::tryAssignCSRFirstTime(
LiveInterval &VirtReg,
2790 unsigned &CostPerUseLimit,
2792 if (getStage(VirtReg) == RS_Spill && VirtReg.
isSpillable()) {
2795 SA->analyze(&VirtReg);
2796 if (calcSpillCost() >= CSRCost)
2801 CostPerUseLimit = 1;
2804 if (getStage(VirtReg) < RS_Split) {
2807 SA->analyze(&VirtReg);
2808 unsigned NumCands = 0;
2810 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2817 doRegionSplit(VirtReg, BestCand,
false, NewVRegs);
2823 void RAGreedy::aboutToRemoveInterval(
LiveInterval &LI) {
2825 SetOfBrokenHints.
remove(&LI);
2828 void RAGreedy::initializeCSRCost() {
2842 uint64_t FixedEntry = 1 << 14;
2843 if (ActualEntry < FixedEntry)
2845 else if (ActualEntry <= UINT32_MAX)
2850 CSRCost = CSRCost.
getFrequency() * (ActualEntry / FixedEntry);
2856 void RAGreedy::collectHintInfo(
unsigned Reg, HintsInfo &Out) {
2858 if (!Instr.isFullCopy())
2861 unsigned OtherReg = Instr.getOperand(0).getReg();
2862 if (OtherReg == Reg) {
2863 OtherReg = Instr.getOperand(1).getReg();
2864 if (OtherReg == Reg)
2870 : VRM->getPhys(OtherReg);
2872 Out.push_back(HintInfo(MBFI->
getBlockFreq(Instr.getParent()), OtherReg,
2883 for (
const HintInfo &
Info : List) {
2884 if (
Info.PhysReg != PhysReg)
2898 void RAGreedy::tryHintRecoloring(
LiveInterval &VirtReg) {
2905 unsigned Reg = VirtReg.
reg;
2906 unsigned PhysReg = VRM->getPhys(Reg);
2913 <<
'(' <<
printReg(PhysReg, TRI) <<
")\n");
2922 assert(VRM->hasPhys(Reg) &&
"We have unallocated variable!!");
2927 unsigned CurrPhys = VRM->getPhys(Reg);
2930 if (CurrPhys != PhysReg && (!
MRI->getRegClass(Reg)->contains(PhysReg) ||
2931 Matrix->checkInterference(LI, PhysReg)))
2935 <<
") is recolorable.\n");
2939 collectHintInfo(Reg, Info);
2942 if (CurrPhys != PhysReg) {
2944 BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);
2949 if (OldCopiesCost < NewCopiesCost) {
2959 Matrix->assign(LI, PhysReg);
2963 for (
const HintInfo &
HI : Info) {
2967 }
while (!RecoloringCandidates.
empty());
3006 void RAGreedy::tryHintsRecoloring() {
3009 "Recoloring is possible only for virtual registers");
3012 if (!VRM->hasPhys(LI->
reg))
3014 tryHintRecoloring(*LI);
3018 unsigned RAGreedy::selectOrSplitImpl(
LiveInterval &VirtReg,
3020 SmallVirtRegSet &FixedRegisters,
3022 unsigned CostPerUseLimit = ~0u;
3025 if (
unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) {
3027 LastEvicted.clearEvicteeInfo(VirtReg.
reg);
3031 if (CSRCost.
getFrequency() && isUnusedCalleeSavedReg(PhysReg) &&
3033 unsigned CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
3034 CostPerUseLimit, NewVRegs);
3035 if (CSRReg || !NewVRegs.
empty())
3043 LiveRangeStage Stage = getStage(VirtReg);
3045 << ExtraRegInfo[VirtReg.
reg].Cascade <<
'\n');
3050 if (Stage != RS_Split)
3051 if (
unsigned PhysReg =
3052 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit)) {
3053 unsigned Hint =
MRI->getSimpleHint(VirtReg.
reg);
3059 if (Hint && Hint != PhysReg)
3060 SetOfBrokenHints.
insert(&VirtReg);
3063 LastEvicted.clearEvicteeInfo(VirtReg.
reg);
3067 assert((NewVRegs.
empty() ||
Depth) &&
"Cannot append to existing NewVRegs");
3072 if (Stage < RS_Split) {
3073 setStage(VirtReg, RS_Split);
3079 if (Stage < RS_Spill) {
3081 unsigned NewVRegSizeBefore = NewVRegs.
size();
3082 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
3083 if (PhysReg || (NewVRegs.
size() - NewVRegSizeBefore)) {
3085 LastEvicted.clearEvicteeInfo(VirtReg.
reg);
3093 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
3102 setStage(VirtReg, RS_Memory);
3108 LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM,
this, &DeadRemats);
3109 spiller().spill(LRE);
3110 setStage(NewVRegs.
begin(), NewVRegs.
end(), RS_Done);
3113 MF->
verify(
this,
"After spilling");
3121 void RAGreedy::reportNumberOfSplillsReloads(
MachineLoop *L,
unsigned &Reloads,
3122 unsigned &FoldedReloads,
3124 unsigned &FoldedSpills) {
3132 unsigned SubReloads;
3133 unsigned SubFoldedReloads;
3135 unsigned SubFoldedSpills;
3137 reportNumberOfSplillsReloads(SubLoop, SubReloads, SubFoldedReloads,
3138 SubSpills, SubFoldedSpills);
3139 Reloads += SubReloads;
3140 FoldedReloads += SubFoldedReloads;
3141 Spills += SubSpills;
3142 FoldedSpills += SubFoldedSpills;
3156 cast<FixedStackPseudoSourceValue>(A->getPseudoValue())
3173 if (Reloads || FoldedReloads || Spills || FoldedSpills) {
3174 using namespace ore;
3178 L->getStartLoc(), L->getHeader());
3180 R <<
NV(
"NumSpills", Spills) <<
" spills ";
3182 R <<
NV(
"NumFoldedSpills", FoldedSpills) <<
" folded spills ";
3184 R <<
NV(
"NumReloads", Reloads) <<
" reloads ";
3186 R <<
NV(
"NumFoldedReloads", FoldedReloads) <<
" folded reloads ";
3187 R <<
"generated in loop";
3194 LLVM_DEBUG(
dbgs() <<
"********** GREEDY REGISTER ALLOCATION **********\n" 3195 <<
"********** Function: " << mf.
getName() <<
'\n');
3198 TRI = MF->getSubtarget().getRegisterInfo();
3199 TII = MF->getSubtarget().getInstrInfo();
3203 MF->getSubtarget().enableRALocalReassignment(
3204 MF->getTarget().getOptLevel());
3207 MF->getSubtarget().enableAdvancedRASplitCost();
3210 MF->verify(
this,
"Before greedy register allocator");
3213 getAnalysis<LiveIntervals>(),
3214 getAnalysis<LiveRegMatrix>());
3215 Indexes = &getAnalysis<SlotIndexes>();
3216 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
3217 DomTree = &getAnalysis<MachineDominatorTree>();
3218 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
3220 Loops = &getAnalysis<MachineLoopInfo>();
3221 Bundles = &getAnalysis<EdgeBundles>();
3222 SpillPlacer = &getAnalysis<SpillPlacement>();
3223 DebugVars = &getAnalysis<LiveDebugVariables>();
3224 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3226 initializeCSRCost();
3233 SE.reset(
new SplitEditor(*SA, *AA, *LIS, *VRM, *DomTree, *MBFI));
3234 ExtraRegInfo.
clear();
3235 ExtraRegInfo.
resize(
MRI->getNumVirtRegs());
3237 IntfCache.
init(MF,
Matrix->getLiveUnions(), Indexes, LIS,
TRI);
3239 SetOfBrokenHints.
clear();
3240 LastEvicted.clear();
3243 tryHintsRecoloring();
3245 reportNumberOfSplillsReloads();
bool isHint() const
Return true if the last register returned from next() was a preferred register.
const T & front() const
front - Get the first element.
void setPhysReg(InterferenceCache &Cache, unsigned PhysReg)
setPhysReg - Point this cursor to PhysReg's interference.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
const T & back() const
back - Get the last element.
DiagnosticInfoOptimizationBase::Argument NV
unsigned getBundle(unsigned N, bool Out) const
getBundle - Return the ingoing (Out = false) or outgoing (Out = true) bundle number for basic block N...
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
void rewind()
Start over from the beginning.
This class represents lattice values for constants.
unsigned getNumRegs() const
Return the number of registers in this class.
MachineInstr & instr_front()
A register is impossible, variable must be spilled.
void push_back(const T &Elt)
LiveInterval - This class represents the liveness of a register, or stack slot.
SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies...
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned getCostPerUse(unsigned RegNo) const
Return the additional cost of using this register instead of other registers in its class...
bool test(unsigned Idx) const
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
SlotIndex FirstDef
First non-phi valno->def, or SlotIndex().
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
virtual bool reverseLocalAssignment() const
Allow the target to reverse allocation order of local live ranges.
unsigned next(unsigned Limit=0)
Return the next physical register in the allocation order, or 0.
bool isValid() const
Returns true if this is a valid index.
STATISTIC(NumFunctions, "Total number of functions")
ArrayRef< unsigned > regs() const
unsigned const TargetRegisterInfo * TRI
bool valid() const
valid - Return true if the current position is valid, false for end().
char & RAGreedyID
Greedy register allocator.
Callback methods for LiveRangeEdit owners.
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))
This class represents the liveness of a register, stack slot, etc.
ArrayRef< unsigned > getBlocks(unsigned Bundle) const
getBlocks - Return an array of blocks that are connected to Bundle.
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
SlotIndex getLastIndex()
Returns the base index of the last slot in this analysis.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
A description of a memory reference used in the backend.
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Query interferences between a single live virtual register and a live interval union.
void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)
addPrefSpill - Add PrefSpill constraints to all blocks listed.
static cl::opt< unsigned > HugeSizeForSplit("huge-size-for-split", cl::Hidden, cl::desc("A threshold of live range size which may cause " "high compile time cost in global splitting."), cl::init(5000))
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
static cl::opt< unsigned > LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden, cl::desc("Last chance recoloring max depth"), cl::init(5))
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
bool scanActiveBundles()
scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks...
void init(MachineFunction *mf, LiveIntervalUnion *liuarray, SlotIndexes *indexes, LiveIntervals *lis, const TargetRegisterInfo *tri)
init - Prepare cache for a new function.
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
This class is basically a combination of TimeRegion and Timer.
ArrayRef< unsigned > getRecentPositive()
getRecentPositive - Return an array of bundles that became positive during the previous call to scanA...
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
static cl::opt< bool > EnableLocalReassignment("enable-local-reassign", cl::Hidden, cl::desc("Local reassignment can yield better allocation decisions, but " "may be compile time intensive"), cl::init(false))
void iterate()
iterate - Update the network iteratively until convergence, or new bundles are found.
bool remove(const value_type &X)
Remove an item from the set vector.
RegAllocBase provides the register allocation driver and interface that can be extended to add intere...
BorderConstraint Exit
Constraint on block exit.
void assign(size_type NumElts, const T &Elt)
void emitError(unsigned LocCookie, const Twine &ErrorStr)
emitError - Emit an error message to the currently installed error handler with optional location inf...
bool insert(const value_type &X)
Insert a new element into the SetVector.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def...
const SmallVectorImpl< LiveInterval * > & interferingVRegs() const
SplitEditor - Edit machine code and LiveIntervals for live range splitting.
iterator_range< def_iterator > def_operands(unsigned Reg) const
INITIALIZE_PASS_BEGIN(RAGreedy, "greedy", "Greedy Register Allocator", false, false) INITIALIZE_PASS_END(RAGreedy
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...
auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
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...
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
RegisterRegAlloc class - Track the registration of register allocators.
virtual const TargetInstrInfo * getInstrInfo() const
BlockConstraint - Entry and exit constraints for a basic block.
bool inBounds(IndexT n) const
Analysis containing CSE Info
SlotIndex LastInstr
Last instr accessing current reg.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
float futureWeight(LiveInterval &li, SlotIndex start, SlotIndex end)
Compute future expected spill weight of a split artifact of li that will span between start and end s...
TargetInstrInfo - Interface to description of machine instruction set.
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)
void addLinks(ArrayRef< unsigned > Links)
addLinks - Add transparent blocks with the given numbers.
unsigned collectInterferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
SlotIndex last()
last - Return the ending index of the last interfering range in the current block.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
initializer< Ty > init(const Ty &Val)
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
const uint8_t AllocationPriority
Classes with a higher priority value are assigned first by register allocators using a greedy heurist...
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
Block doesn't care / variable not live.
BlockFrequency getBlockFrequency(unsigned Number) const
getBlockFrequency - Return the estimated block execution frequency per function invocation.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
This is an important class for using LLVM in a threaded context.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Cursor - The primary query interface for the block interference cache.
size_t size() const
size - Get the array size.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
ArrayRef< MCPhysReg > getOrder() const
Get the allocation order without reordered hints.
const KeyT & start() const
start - Return the beginning of the current interval.
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions. ...
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
raw_ostream & printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Represent the analysis usage information of a pass.
Greedy Register Allocator
static unsigned getNumAllocatableRegsForConstraints(const MachineInstr *MI, unsigned 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 ...
int getInstrDistance(SlotIndex other) const
Return the scaled distance from this index to the given one, where all slots on the same instruction ...
unsigned Number
Basic block number (from MBB::getNumber()).
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 getZeroIndex()
Returns the zero index for this analysis.
void resize(typename StorageT::size_type s)
FunctionPass class - This class is used to implement most global optimizations.
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
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))
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat)
virtual unsigned getCSRFirstUseCost() const
Allow the target to override the cost of using a callee-saved register for the first time...
static cl::opt< bool > ConsiderLocalIntervalCost("condsider-local-interval-cost", cl::Hidden, cl::desc("Consider the cost of local intervals created by a split " "candidate when choosing the best split candidate."), cl::init(false))
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
BorderConstraint Entry
Constraint on block entry.
bool finish()
finish - Compute the optimal spill code placement given the constraints.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Block entry/exit prefers a register.
void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)
addConstraints - Add constraints and biases.
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
static bool hasTiedDef(MachineRegisterInfo *MRI, unsigned reg)
Return true if reg has any tied def operand.
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...
A SetVector that performs no allocations if smaller than a certain size.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, VirtRegMap *VRM, const MachineLoopInfo &MLI, const MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo::NormalizingFn norm=normalizeSpillWeight)
Compute spill weights and allocation hints for all virtual register live intervals.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
void splitRegister(unsigned OldReg, ArrayRef< unsigned > NewRegs, LiveIntervals &LIS)
splitRegister - Move any user variables in OldReg to the live ranges in NewRegs where they are live...
Segments::const_iterator const_iterator
Block entry/exit prefers a stack slot.
SlotIndex FirstInstr
First instr accessing current reg.
MachineOperand class - Representation of each machine instruction operand.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Additional information about basic blocks where the current variable is live.
Promote Memory to Register
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
LLVM_NODISCARD T pop_back_val()
void prepare(BitVector &RegBundles)
prepare - Reset state and prepare for a new spill placement computation.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
bool hasInterference()
hasInterference - Return true if the current block has any interference.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange's.
void clear()
Completely clear the SetVector.
const ValT & value() const
value - Return the mapped value at the current interval.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
bool LiveOut
Current reg is live out.
static void clear(coro::Shape &Shape)
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
unsigned getNumBundles() const
getNumBundles - Return the total number of bundles in the CFG.
void moveToBlock(unsigned MBBNum)
moveTo - Move cursor to basic block MBBNum.
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
const KeyT & stop() const
stop - Return the end of the current interval.
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))
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
Spiller * createInlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm)
Create and return a spiller that will insert spill code directly instead of deferring though VirtRegM...
Representation of each machine instruction.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
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...
static uint64_t getMaxFrequency()
Returns the maximum possible frequency, the saturation value.
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
LLVM_NODISCARD bool empty() const
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...
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...
FunctionPass * createGreedyRegisterAllocator()
Greedy register allocation pass - This pass implements a global register allocator for optimized buil...
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)
const TargetRegisterClass * getRegClassConstraintEffectForVReg(unsigned Reg, const TargetRegisterClass *CurRC, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, bool ExploreBundle=false) const
Applies the constraints (def/use) implied by this MI on Reg to the given CurRC.
static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator)
uint64_t getEntryFreq() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static float normalizeSpillWeight(float UseDefFreq, unsigned Size, unsigned NumInstr)
Normalize the spill weight of a live interval.
bool operator<(int64_t V1, const APSInt &V2)
bool isSpillable() const
isSpillable - Can this interval be spilled?
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
iterator_range< const_set_bits_iterator > set_bits() const
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
The default distance between instructions as returned by distance().
StringRef - Represent a constant reference to a string, i.e.
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none...
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
bool TimePassesIsEnabled
If the user specifies the -time-passes argument on an LLVM tool command line then the value of this b...
bool LiveIn
Current reg is live in.
unsigned getMaxCursors() const
getMaxCursors - Return the maximum number of concurrent cursors that can be supported.
SlotIndex - An opaque wrapper around machine indexes.
bool isTriviallyReMaterializable(const MachineInstr &MI, AliasAnalysis *AA=nullptr) const
Return true if the instruction is trivially rematerializable, meaning it has no side effects and requ...
Virtual register interference.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
The operation is expected to be selectable directly by the target, and no transformation is necessary...
SlotIndex first()
first - Return the starting index of the first interfering range in the current block.
unsigned get(unsigned idx) const
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
bool isSpillSlotObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a spill slot.
Properties which a MachineFunction may have at a given point in time.
bool ChangesValue
True when this block changes the value of the live range.