48 #include "llvm/Config/llvm-config.h"
64 #define DEBUG_TYPE "regalloc"
66 STATISTIC(NumSpilledRanges,
"Number of spilled live ranges");
67 STATISTIC(NumSnippets,
"Number of spilled snippets");
68 STATISTIC(NumSpills,
"Number of spills inserted");
69 STATISTIC(NumSpillsRemoved,
"Number of spills removed");
70 STATISTIC(NumReloads,
"Number of reloads inserted");
71 STATISTIC(NumReloadsRemoved,
"Number of reloads removed");
72 STATISTIC(NumFolded,
"Number of folded stack accesses");
73 STATISTIC(NumFoldedLoads,
"Number of folded loads");
74 STATISTIC(NumRemats,
"Number of rematerialized defs for spilling");
77 cl::desc(
"Disable inline spill hoisting"));
81 cl::desc(
"Restrict remat for statepoint operands"));
109 using MergeableSpillsMap =
111 MergeableSpillsMap MergeableSpills;
121 void rmRedundantSpills(
146 MRI(mf.getRegInfo()),
TII(*mf.getSubtarget().getInstrInfo()),
147 TRI(*mf.getSubtarget().getRegisterInfo()),
149 IPA(LIS, mf.getNumBlockIDs()) {}
151 void addToMergeableSpills(
MachineInstr &Spill,
int StackSlot,
153 bool rmFromMergeableSpills(
MachineInstr &Spill,
int StackSlot);
154 void hoistAllSpills();
158 class InlineSpiller :
public Spiller {
191 HoistSpillHelper HSpiller;
196 ~InlineSpiller()
override =
default;
206 MRI(MF.getRegInfo()),
TII(*MF.getSubtarget().getInstrInfo()),
207 TRI(*MF.getSubtarget().getRegisterInfo()),
209 HSpiller(
Pass, MF, VRM), VRAI(VRAI) {}
212 void postOptimization()
override;
216 void collectRegsToSpill();
227 void reMaterializeAll();
230 bool foldMemoryOperand(
ArrayRef<std::pair<MachineInstr *, unsigned>>,
243 void Spiller::anchor() {}
248 return new InlineSpiller(
Pass, MF, VRM, VRAI);
266 if (!
MI.isFullCopy())
268 if (
MI.getOperand(0).getReg() ==
Reg)
269 return MI.getOperand(1).getReg();
270 if (
MI.getOperand(1).getReg() ==
Reg)
271 return MI.getOperand(0).getReg();
284 bool InlineSpiller::isSnippet(
const LiveInterval &SnipLI) {
294 if (SnipLI.
getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI))
329 void InlineSpiller::collectRegsToSpill() {
333 RegsToSpill.assign(1,
Reg);
334 SnippetCopies.clear();
344 if (!isSibling(SnipReg))
347 if (!isSnippet(SnipLI))
349 SnippetCopies.insert(&
MI);
350 if (isRegToSpill(SnipReg))
352 RegsToSpill.push_back(SnipReg);
359 return Reg.isVirtual() && VRM.getOriginal(
Reg) == Original;
381 bool InlineSpiller::hoistSpillInsideBB(
LiveInterval &SpillLI,
383 SlotIndex Idx = LIS.getInstructionIndex(CopyMI);
400 assert(StackInt &&
"No stack slot assigned yet.");
403 StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));
405 << *StackInt <<
'\n');
409 eliminateRedundantSpills(SrcLI, SrcVNI);
417 assert(
DefMI &&
"Defining instruction disappeared");
425 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MII);
434 if (MIS.begin() == MII)
435 HSpiller.addToMergeableSpills(*MII, StackSlot, Original);
443 assert(VNI &&
"Missing value");
445 WorkList.push_back(std::make_pair(&SLI, VNI));
446 assert(StackInt &&
"No stack slot assigned yet.");
453 << VNI->
def <<
" in " << *LI <<
'\n');
456 if (isRegToSpill(
Reg))
460 StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));
461 LLVM_DEBUG(
dbgs() <<
"Merged to stack int: " << *StackInt <<
'\n');
466 if (!
MI.isCopy() && !
MI.mayStore())
474 if (isSibling(DstReg)) {
477 assert(DstVNI &&
"Missing defined value");
479 WorkList.push_back(std::make_pair(&DstLI, DstVNI));
489 MI.setDesc(
TII.get(TargetOpcode::KILL));
490 DeadDefs.push_back(&
MI);
492 if (HSpiller.rmFromMergeableSpills(
MI, StackSlot))
496 }
while (!WorkList.empty());
507 WorkList.push_back(std::make_pair(LI, VNI));
510 if (!UsedValues.insert(VNI).second)
518 WorkList.push_back(std::make_pair(LI, PVNI));
525 if (!SnippetCopies.count(
MI))
527 LiveInterval &SnipLI = LIS.getInterval(
MI->getOperand(1).getReg());
528 assert(isRegToSpill(SnipLI.
reg()) &&
"Unexpected register in copy");
530 assert(SnipVNI &&
"Snippet undefined before copy");
531 WorkList.push_back(std::make_pair(&SnipLI, SnipVNI));
532 }
while (!WorkList.empty());
535 bool InlineSpiller::canGuaranteeAssignmentAfterRemat(
Register VReg,
554 if (
MI.getOpcode() != TargetOpcode::STATEPOINT)
560 EndIdx =
MI.getNumOperands();
561 Idx < EndIdx; ++Idx) {
590 if (SnippetCopies.count(&
MI))
596 RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->
def);
598 if (!Edit->canRematerializeAt(
RM, OrigVNI, UseIdx,
false)) {
599 markValueUsed(&VirtReg, ParentVNI);
607 markValueUsed(&VirtReg, ParentVNI);
614 if (
RM.OrigMI->canFoldAsLoad() &&
615 foldMemoryOperand(Ops,
RM.OrigMI)) {
616 Edit->markRematerialized(
RM.ParentVNI);
623 if (!canGuaranteeAssignmentAfterRemat(VirtReg.
reg(),
MI)) {
624 markValueUsed(&VirtReg, ParentVNI);
630 Register NewVReg = Edit->createFrom(Original);
634 Edit->rematerializeAt(*
MI.getParent(),
MI, NewVReg,
RM,
TRI);
638 auto *NewMI = LIS.getInstructionFromIndex(DefIdx);
639 NewMI->setDebugLoc(
MI.getDebugLoc());
643 << *LIS.getInstructionFromIndex(DefIdx));
646 for (
const auto &OpPair : Ops) {
661 void InlineSpiller::reMaterializeAll() {
662 if (!Edit->anyRematerializable(
AA))
668 bool anyRemat =
false;
673 if (
MI.isDebugValue())
676 assert(!
MI.isDebugInstr() &&
"Did not expect to find a use in debug "
677 "instruction that isn't a DBG_VALUE");
679 anyRemat |= reMaterializeFor(LI,
MI);
693 if (!
MI->allDefsAreDead())
696 DeadDefs.push_back(
MI);
702 if (DeadDefs.empty())
704 LLVM_DEBUG(
dbgs() <<
"Remat created " << DeadDefs.size() <<
" dead defs.\n");
705 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill,
AA);
713 unsigned ResultPos = 0;
716 Edit->eraseVirtReg(
Reg);
722 "Empty and not used live-range?!");
724 RegsToSpill[ResultPos++] =
Reg;
726 RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end());
728 <<
" registers to spill after remat.\n");
739 bool IsLoad = InstrReg;
744 if (InstrReg !=
Reg || FI != StackSlot)
748 HSpiller.rmFromMergeableSpills(*
MI, StackSlot);
751 LIS.RemoveMachineInstrFromMaps(*
MI);
752 MI->eraseFromParent();
765 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
771 const char *
const header,
773 char NextLine =
'\n';
774 char SlotIndent =
'\t';
776 if (std::next(
B) ==
E) {
781 dbgs() <<
'\t' << header <<
": " << NextLine;
795 dbgs() << SlotIndent << Idx <<
'\t' << *
I;
807 foldMemoryOperand(
ArrayRef<std::pair<MachineInstr *, unsigned>> Ops,
813 if (Ops.back().first !=
MI ||
MI->isBundled())
816 bool WasCopy =
MI->isCopy();
825 bool UntieRegs =
MI->getOpcode() == TargetOpcode::STATEPOINT;
829 bool SpillSubRegs =
TII.isSubregFoldable() ||
830 MI->getOpcode() == TargetOpcode::STATEPOINT ||
831 MI->getOpcode() == TargetOpcode::PATCHPOINT ||
832 MI->getOpcode() == TargetOpcode::STACKMAP;
837 for (
const auto &OpPair : Ops) {
838 unsigned Idx = OpPair.second;
839 assert(
MI == OpPair.first &&
"Instruction conflict during operand folding");
856 if (LoadMI && MO.
isDef())
859 if (UntieRegs || !
MI->isRegTiedToDefOperand(Idx))
860 FoldOps.push_back(Idx);
872 for (
unsigned Idx : FoldOps) {
876 unsigned Tied =
MI->findTiedOperandIdx(Idx);
883 MI->untieRegOperand(Idx);
887 LoadMI ?
TII.foldMemoryOperand(*
MI, FoldOps, *LoadMI, &LIS)
888 :
TII.foldMemoryOperand(*
MI, FoldOps, StackSlot, &LIS, &VRM);
891 for (
auto Tied : TiedOps)
892 MI->tieOperands(Tied.first, Tied.second);
918 HSpiller.rmFromMergeableSpills(*
MI, FI))
922 if (
MI->isCandidateForCallSiteEntry())
923 MI->getMF()->moveCallSiteInfo(
MI, FoldMI);
930 if (
MI->peekDebugInstrNum() && Ops[0].second == 0) {
932 auto MakeSubstitution = [
this,FoldMI,
MI,&Ops]() {
934 unsigned OldOperandNum = Ops[0].second;
936 unsigned OldNum =
MI->getDebugInstrNum();
937 MF.makeDebugValueSubstitution({OldNum, OldOperandNum},
942 if (Ops.size() == 1 && Op0.
isDef()) {
944 }
else if (Ops.size() == 2 && Op0.
isDef() &&
MI->getOperand(1).isTied() &&
945 Op0.
getReg() ==
MI->getOperand(1).getReg()) {
948 }
else if (
MI->peekDebugInstrNum()) {
954 MF.substituteDebugValuesForInst(*
MI, *FoldMI, Ops[0].second);
957 MI->eraseFromParent();
960 assert(!MIS.empty() &&
"Unexpected empty span of instructions!");
972 if (MO.
getReg() == ImpReg)
981 else if (Ops.front().second == 0) {
986 if (std::distance(MIS.begin(), MIS.end()) <= 1)
987 HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original);
993 void InlineSpiller::insertReload(
Register NewVReg,
1013 if (!
Def.isImplicitDef())
1016 "Implicit def with more than one definition");
1020 return Def.getOperand(0).getSubReg();
1024 void InlineSpiller::insertSpill(
Register NewVReg,
bool isKill,
1028 assert(!
MI->isTerminator() &&
"Inserting a spill after a terminator");
1043 BuildMI(
MBB, SpillBefore,
MI->getDebugLoc(),
TII.get(TargetOpcode::KILL))
1057 if (IsRealSpill && std::distance(Spill, MIS.end()) <= 1)
1058 HSpiller.addToMergeableSpills(*Spill, StackSlot, Original);
1062 void InlineSpiller::spillAroundUses(
Register Reg) {
1069 if (
MI.isDebugValue()) {
1078 assert(!
MI.isDebugInstr() &&
"Did not expect to find a use in debug "
1079 "instruction that isn't a DBG_VALUE");
1082 if (SnippetCopies.count(&
MI))
1086 if (coalesceStackAccess(&
MI,
Reg))
1102 if (SibReg && isSibling(SibReg)) {
1104 if (isRegToSpill(SibReg)) {
1106 SnippetCopies.insert(&
MI);
1110 if (hoistSpillInsideBB(OldLI,
MI)) {
1112 MI.getOperand(0).setIsDead();
1113 DeadDefs.push_back(&
MI);
1119 eliminateRedundantSpills(SibLI, SibLI.
getVNInfoAt(Idx));
1125 if (foldMemoryOperand(Ops))
1133 insertReload(NewVReg, Idx, &
MI);
1136 bool hasLiveDef =
false;
1137 for (
const auto &OpPair : Ops) {
1141 if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
1153 insertSpill(NewVReg,
true, &
MI);
1158 void InlineSpiller::spillAll() {
1161 StackSlot = VRM.assignVirt2StackSlot(Original);
1162 StackInt = &LSS.getOrCreateInterval(StackSlot,
MRI.
getRegClass(Original));
1163 StackInt->getNextValue(
SlotIndex(), LSS.getVNInfoAllocator());
1165 StackInt = &LSS.getInterval(StackSlot);
1167 if (Original != Edit->getReg())
1168 VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);
1170 assert(StackInt->getNumValNums() == 1 &&
"Bad stack interval values");
1174 LLVM_DEBUG(
dbgs() <<
"Merged spilled regs: " << *StackInt <<
'\n');
1178 spillAroundUses(
Reg);
1181 if (!DeadDefs.empty()) {
1182 LLVM_DEBUG(
dbgs() <<
"Eliminating " << DeadDefs.size() <<
" dead defs\n");
1183 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill,
AA);
1190 assert(SnippetCopies.count(&
MI) &&
"Remaining use wasn't a snippet copy");
1193 MI.eraseFromParent();
1199 Edit->eraseVirtReg(
Reg);
1206 "Trying to spill a stack slot.");
1208 Original = VRM.getOriginal(edit.
getReg());
1209 StackSlot = VRM.getStackSlot(Original);
1214 <<
':' << edit.
getParent() <<
"\nFrom original "
1217 "Attempting to spill already spilled value.");
1218 assert(DeadDefs.empty() &&
"Previous spill didn't remove dead defs");
1220 collectRegsToSpill();
1224 if (!RegsToSpill.empty())
1227 Edit->calculateRegClassAndHint(MF, VRAI);
1231 void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); }
1234 void HoistSpillHelper::addToMergeableSpills(
MachineInstr &Spill,
int StackSlot,
1235 unsigned Original) {
1240 if (StackSlotToOrigLI.find(StackSlot) == StackSlotToOrigLI.end()) {
1241 auto LI = std::make_unique<LiveInterval>(OrigLI.
reg(), OrigLI.
weight());
1243 StackSlotToOrigLI[StackSlot] =
std::move(LI);
1246 VNInfo *OrigVNI = StackSlotToOrigLI[StackSlot]->getVNInfoAt(Idx.
getRegSlot());
1247 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1248 MergeableSpills[MIdx].insert(&Spill);
1253 bool HoistSpillHelper::rmFromMergeableSpills(
MachineInstr &Spill,
1255 auto It = StackSlotToOrigLI.find(StackSlot);
1256 if (It == StackSlotToOrigLI.end())
1260 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1261 return MergeableSpills[MIdx].erase(&Spill);
1268 SlotIndex Idx = IPA.getLastInsertPoint(OrigLI,
BB);
1271 if (Idx < OrigVNI.
def) {
1274 LLVM_DEBUG(
dbgs() <<
"can't spill in root block - def after LIP\n");
1281 for (
const Register &SibReg : Siblings) {
1294 void HoistSpillHelper::rmRedundantSpills(
1301 for (
const auto CurrentSpill : Spills) {
1308 MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;
1309 MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;
1310 SpillsToRm.push_back(SpillToRm);
1311 SpillBBToSpill[MDT.getBase().getNode(Block)] = SpillToKeep;
1313 SpillBBToSpill[MDT.getBase().getNode(Block)] = CurrentSpill;
1316 for (
const auto SpillToRm : SpillsToRm)
1317 Spills.
erase(SpillToRm);
1326 void HoistSpillHelper::getVisitOrders(
1350 for (
const auto Spill : Spills) {
1354 while (Node != RootIDomNode) {
1357 if (Node != MDT[Block] && SpillBBToSpill[Node]) {
1358 SpillToRm = SpillBBToSpill[MDT[
Block]];
1363 }
else if (WorkSet.
count(Node)) {
1366 NodesOnPath.
insert(Node);
1368 Node = Node->getIDom();
1371 SpillsToRm.push_back(SpillToRm);
1378 SpillsToKeep[MDT[
Block]] = 0;
1381 NodesOnPath.
clear();
1387 Orders.push_back(MDT.getBase().getNode(Root));
1391 if (WorkSet.
count(Child))
1392 Orders.push_back(Child);
1394 }
while (idx != Orders.size());
1396 "Orders have different size with WorkSet");
1399 LLVM_DEBUG(
dbgs() <<
"Orders size is " << Orders.size() <<
"\n");
1401 for (; RIt != Orders.rend(); RIt++)
1402 LLVM_DEBUG(
dbgs() <<
"BB" << (*RIt)->getBlock()->getNumber() <<
",");
1410 void HoistSpillHelper::runHoistSpills(
1426 rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill);
1429 getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep,
1436 using NodesCostPair =
1437 std::pair<SmallPtrSet<MachineDomTreeNode *, 16>,
BlockFrequency>;
1445 for (; RIt != Orders.rend(); RIt++) {
1449 if (SpillsToKeep.
find(*RIt) != SpillsToKeep.
end() && !SpillsToKeep[*RIt]) {
1450 SpillsInSubTreeMap[*RIt].first.
insert(*RIt);
1452 SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block);
1459 if (SpillsInSubTreeMap.
find(Child) == SpillsInSubTreeMap.
end())
1467 SpillsInSubTreeMap[*RIt].first;
1469 SubTreeCost += SpillsInSubTreeMap[Child].second;
1470 auto BI = SpillsInSubTreeMap[Child].first.
begin();
1471 auto EI = SpillsInSubTreeMap[Child].first.
end();
1472 SpillsInSubTree.
insert(BI, EI);
1473 SpillsInSubTreeMap.
erase(Child);
1477 SpillsInSubTreeMap[*RIt].first;
1480 if (SpillsInSubTree.
empty())
1485 if (!isSpillCandBB(OrigLI, OrigVNI, *Block, LiveReg))
1493 if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) {
1495 for (
const auto SpillBB : SpillsInSubTree) {
1498 if (SpillsToKeep.
find(SpillBB) != SpillsToKeep.
end() &&
1499 !SpillsToKeep[SpillBB]) {
1501 SpillsToRm.push_back(SpillToRm);
1504 SpillsToKeep.
erase(SpillBB);
1508 SpillsToKeep[*RIt] = LiveReg;
1510 dbgs() <<
"spills in BB: ";
1511 for (
const auto Rspill : SpillsInSubTree)
1512 dbgs() << Rspill->getBlock()->getNumber() <<
" ";
1513 dbgs() <<
"were promoted to BB" << (*RIt)->getBlock()->getNumber()
1516 SpillsInSubTree.clear();
1517 SpillsInSubTree.insert(*RIt);
1518 SubTreeCost = MBFI.getBlockFreq(Block);
1523 for (
const auto &Ent : SpillsToKeep) {
1525 SpillsToIns[Ent.first->getBlock()] = Ent.second;
1545 void HoistSpillHelper::hoistAllSpills() {
1553 Virt2SiblingsMap[Original].insert(
Reg);
1557 for (
auto &Ent : MergeableSpills) {
1558 int Slot = Ent.first.first;
1560 VNInfo *OrigVNI = Ent.first.second;
1562 if (Ent.second.empty())
1566 dbgs() <<
"\nFor Slot" <<
Slot <<
" and VN" << OrigVNI->
id <<
":\n"
1567 <<
"Equal spills in BB: ";
1568 for (
const auto spill : EqValSpills)
1569 dbgs() <<
spill->getParent()->getNumber() <<
" ";
1578 runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
1581 dbgs() <<
"Finally inserted spills in BB: ";
1582 for (
const auto &Ispill : SpillsToIns)
1583 dbgs() << Ispill.first->getNumber() <<
" ";
1584 dbgs() <<
"\nFinally removed spills in BB: ";
1585 for (
const auto Rspill : SpillsToRm)
1586 dbgs() << Rspill->getParent()->getNumber() <<
" ";
1592 if (!SpillsToIns.empty() || !SpillsToRm.empty())
1594 StackIntvl.getValNumInfo(0));
1597 for (
auto const &Insert : SpillsToIns) {
1611 NumSpills -= SpillsToRm.size();
1612 for (
auto const RMEnt : SpillsToRm) {
1613 RMEnt->setDesc(
TII.get(TargetOpcode::KILL));
1614 for (
unsigned i = RMEnt->getNumOperands();
i; --
i) {
1617 RMEnt->removeOperand(
i - 1);
1620 Edit.eliminateDeadDefs(SpillsToRm,
None,
AA);
1627 if (VRM.hasPhys(Old))
1628 VRM.assignVirt2Phys(New, VRM.getPhys(Old));
1630 VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
1633 if (VRM.hasShape(Old))
1634 VRM.assignVirt2Shape(New, VRM.getShape(Old));