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");
849 if (LoadMI && MO.
isDef())
852 if (UntieRegs || !
MI->isRegTiedToDefOperand(Idx))
853 FoldOps.push_back(Idx);
865 for (
unsigned Idx : FoldOps) {
869 unsigned Tied =
MI->findTiedOperandIdx(Idx);
876 MI->untieRegOperand(Idx);
880 LoadMI ?
TII.foldMemoryOperand(*
MI, FoldOps, *LoadMI, &LIS)
881 :
TII.foldMemoryOperand(*
MI, FoldOps, StackSlot, &LIS, &VRM);
884 for (
auto Tied : TiedOps)
885 MI->tieOperands(Tied.first, Tied.second);
911 HSpiller.rmFromMergeableSpills(*
MI, FI))
915 if (
MI->isCandidateForCallSiteEntry())
916 MI->getMF()->moveCallSiteInfo(
MI, FoldMI);
923 if (
MI->peekDebugInstrNum() && Ops[0].second == 0) {
925 auto MakeSubstitution = [
this,FoldMI,
MI,&Ops]() {
927 unsigned OldOperandNum = Ops[0].second;
929 unsigned OldNum =
MI->getDebugInstrNum();
930 MF.makeDebugValueSubstitution({OldNum, OldOperandNum},
935 if (Ops.size() == 1 && Op0.
isDef()) {
937 }
else if (Ops.size() == 2 && Op0.
isDef() &&
MI->getOperand(1).isTied() &&
938 Op0.
getReg() ==
MI->getOperand(1).getReg()) {
941 }
else if (
MI->peekDebugInstrNum()) {
947 MF.substituteDebugValuesForInst(*
MI, *FoldMI, Ops[0].second);
950 MI->eraseFromParent();
953 assert(!MIS.empty() &&
"Unexpected empty span of instructions!");
965 if (MO.
getReg() == ImpReg)
974 else if (Ops.front().second == 0) {
979 if (std::distance(MIS.begin(), MIS.end()) <= 1)
980 HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original);
986 void InlineSpiller::insertReload(
Register NewVReg,
1006 if (!
Def.isImplicitDef())
1009 "Implicit def with more than one definition");
1013 return Def.getOperand(0).getSubReg();
1017 void InlineSpiller::insertSpill(
Register NewVReg,
bool isKill,
1021 assert(!
MI->isTerminator() &&
"Inserting a spill after a terminator");
1036 BuildMI(
MBB, SpillBefore,
MI->getDebugLoc(),
TII.get(TargetOpcode::KILL))
1050 if (IsRealSpill && std::distance(Spill, MIS.end()) <= 1)
1051 HSpiller.addToMergeableSpills(*Spill, StackSlot, Original);
1055 void InlineSpiller::spillAroundUses(
Register Reg) {
1062 if (
MI.isDebugValue()) {
1071 assert(!
MI.isDebugInstr() &&
"Did not expect to find a use in debug "
1072 "instruction that isn't a DBG_VALUE");
1075 if (SnippetCopies.count(&
MI))
1079 if (coalesceStackAccess(&
MI,
Reg))
1095 if (SibReg && isSibling(SibReg)) {
1097 if (isRegToSpill(SibReg)) {
1099 SnippetCopies.insert(&
MI);
1103 if (hoistSpillInsideBB(OldLI,
MI)) {
1105 MI.getOperand(0).setIsDead();
1106 DeadDefs.push_back(&
MI);
1112 eliminateRedundantSpills(SibLI, SibLI.
getVNInfoAt(Idx));
1118 if (foldMemoryOperand(Ops))
1126 insertReload(NewVReg, Idx, &
MI);
1129 bool hasLiveDef =
false;
1130 for (
const auto &OpPair : Ops) {
1134 if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
1146 insertSpill(NewVReg,
true, &
MI);
1151 void InlineSpiller::spillAll() {
1154 StackSlot = VRM.assignVirt2StackSlot(Original);
1155 StackInt = &LSS.getOrCreateInterval(StackSlot,
MRI.
getRegClass(Original));
1156 StackInt->getNextValue(
SlotIndex(), LSS.getVNInfoAllocator());
1158 StackInt = &LSS.getInterval(StackSlot);
1160 if (Original != Edit->getReg())
1161 VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);
1163 assert(StackInt->getNumValNums() == 1 &&
"Bad stack interval values");
1167 LLVM_DEBUG(
dbgs() <<
"Merged spilled regs: " << *StackInt <<
'\n');
1171 spillAroundUses(
Reg);
1174 if (!DeadDefs.empty()) {
1175 LLVM_DEBUG(
dbgs() <<
"Eliminating " << DeadDefs.size() <<
" dead defs\n");
1176 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill,
AA);
1183 assert(SnippetCopies.count(&
MI) &&
"Remaining use wasn't a snippet copy");
1186 MI.eraseFromParent();
1192 Edit->eraseVirtReg(
Reg);
1199 "Trying to spill a stack slot.");
1201 Original = VRM.getOriginal(edit.
getReg());
1202 StackSlot = VRM.getStackSlot(Original);
1207 <<
':' << edit.
getParent() <<
"\nFrom original "
1210 "Attempting to spill already spilled value.");
1211 assert(DeadDefs.empty() &&
"Previous spill didn't remove dead defs");
1213 collectRegsToSpill();
1217 if (!RegsToSpill.empty())
1220 Edit->calculateRegClassAndHint(MF, VRAI);
1224 void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); }
1227 void HoistSpillHelper::addToMergeableSpills(
MachineInstr &Spill,
int StackSlot,
1228 unsigned Original) {
1233 if (StackSlotToOrigLI.find(StackSlot) == StackSlotToOrigLI.end()) {
1234 auto LI = std::make_unique<LiveInterval>(OrigLI.
reg(), OrigLI.
weight());
1236 StackSlotToOrigLI[StackSlot] =
std::move(LI);
1239 VNInfo *OrigVNI = StackSlotToOrigLI[StackSlot]->getVNInfoAt(Idx.
getRegSlot());
1240 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1241 MergeableSpills[MIdx].insert(&Spill);
1246 bool HoistSpillHelper::rmFromMergeableSpills(
MachineInstr &Spill,
1248 auto It = StackSlotToOrigLI.find(StackSlot);
1249 if (It == StackSlotToOrigLI.end())
1253 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1254 return MergeableSpills[MIdx].erase(&Spill);
1261 SlotIndex Idx = IPA.getLastInsertPoint(OrigLI,
BB);
1264 if (Idx < OrigVNI.
def) {
1267 LLVM_DEBUG(
dbgs() <<
"can't spill in root block - def after LIP\n");
1274 for (
const Register &SibReg : Siblings) {
1287 void HoistSpillHelper::rmRedundantSpills(
1294 for (
const auto CurrentSpill : Spills) {
1301 MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;
1302 MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;
1303 SpillsToRm.push_back(SpillToRm);
1304 SpillBBToSpill[MDT.getBase().getNode(Block)] = SpillToKeep;
1306 SpillBBToSpill[MDT.getBase().getNode(Block)] = CurrentSpill;
1309 for (
const auto SpillToRm : SpillsToRm)
1310 Spills.
erase(SpillToRm);
1319 void HoistSpillHelper::getVisitOrders(
1343 for (
const auto Spill : Spills) {
1347 while (Node != RootIDomNode) {
1350 if (Node != MDT[Block] && SpillBBToSpill[Node]) {
1351 SpillToRm = SpillBBToSpill[MDT[
Block]];
1356 }
else if (WorkSet.
count(Node)) {
1359 NodesOnPath.
insert(Node);
1361 Node = Node->getIDom();
1364 SpillsToRm.push_back(SpillToRm);
1371 SpillsToKeep[MDT[
Block]] = 0;
1374 NodesOnPath.
clear();
1380 Orders.push_back(MDT.getBase().getNode(Root));
1384 if (WorkSet.
count(Child))
1385 Orders.push_back(Child);
1387 }
while (idx != Orders.size());
1389 "Orders have different size with WorkSet");
1392 LLVM_DEBUG(
dbgs() <<
"Orders size is " << Orders.size() <<
"\n");
1394 for (; RIt != Orders.rend(); RIt++)
1395 LLVM_DEBUG(
dbgs() <<
"BB" << (*RIt)->getBlock()->getNumber() <<
",");
1403 void HoistSpillHelper::runHoistSpills(
1419 rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill);
1422 getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep,
1429 using NodesCostPair =
1430 std::pair<SmallPtrSet<MachineDomTreeNode *, 16>,
BlockFrequency>;
1438 for (; RIt != Orders.rend(); RIt++) {
1442 if (SpillsToKeep.
find(*RIt) != SpillsToKeep.
end() && !SpillsToKeep[*RIt]) {
1443 SpillsInSubTreeMap[*RIt].first.
insert(*RIt);
1445 SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block);
1452 if (SpillsInSubTreeMap.
find(Child) == SpillsInSubTreeMap.
end())
1460 SpillsInSubTreeMap[*RIt].first;
1462 SubTreeCost += SpillsInSubTreeMap[Child].second;
1463 auto BI = SpillsInSubTreeMap[Child].first.
begin();
1464 auto EI = SpillsInSubTreeMap[Child].first.
end();
1465 SpillsInSubTree.
insert(BI, EI);
1466 SpillsInSubTreeMap.
erase(Child);
1470 SpillsInSubTreeMap[*RIt].first;
1473 if (SpillsInSubTree.
empty())
1478 if (!isSpillCandBB(OrigLI, OrigVNI, *Block, LiveReg))
1486 if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) {
1488 for (
const auto SpillBB : SpillsInSubTree) {
1491 if (SpillsToKeep.
find(SpillBB) != SpillsToKeep.
end() &&
1492 !SpillsToKeep[SpillBB]) {
1494 SpillsToRm.push_back(SpillToRm);
1497 SpillsToKeep.
erase(SpillBB);
1501 SpillsToKeep[*RIt] = LiveReg;
1503 dbgs() <<
"spills in BB: ";
1504 for (
const auto Rspill : SpillsInSubTree)
1505 dbgs() << Rspill->getBlock()->getNumber() <<
" ";
1506 dbgs() <<
"were promoted to BB" << (*RIt)->getBlock()->getNumber()
1509 SpillsInSubTree.clear();
1510 SpillsInSubTree.insert(*RIt);
1511 SubTreeCost = MBFI.getBlockFreq(Block);
1516 for (
const auto &Ent : SpillsToKeep) {
1518 SpillsToIns[Ent.first->getBlock()] = Ent.second;
1538 void HoistSpillHelper::hoistAllSpills() {
1546 Virt2SiblingsMap[Original].insert(
Reg);
1550 for (
auto &Ent : MergeableSpills) {
1551 int Slot = Ent.first.first;
1553 VNInfo *OrigVNI = Ent.first.second;
1555 if (Ent.second.empty())
1559 dbgs() <<
"\nFor Slot" <<
Slot <<
" and VN" << OrigVNI->
id <<
":\n"
1560 <<
"Equal spills in BB: ";
1561 for (
const auto spill : EqValSpills)
1562 dbgs() <<
spill->getParent()->getNumber() <<
" ";
1571 runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
1574 dbgs() <<
"Finally inserted spills in BB: ";
1575 for (
const auto &Ispill : SpillsToIns)
1576 dbgs() << Ispill.first->getNumber() <<
" ";
1577 dbgs() <<
"\nFinally removed spills in BB: ";
1578 for (
const auto Rspill : SpillsToRm)
1579 dbgs() << Rspill->getParent()->getNumber() <<
" ";
1585 if (!SpillsToIns.empty() || !SpillsToRm.empty())
1587 StackIntvl.getValNumInfo(0));
1590 for (
auto const &Insert : SpillsToIns) {
1604 NumSpills -= SpillsToRm.size();
1605 for (
auto const RMEnt : SpillsToRm) {
1606 RMEnt->setDesc(
TII.get(TargetOpcode::KILL));
1607 for (
unsigned i = RMEnt->getNumOperands();
i; --
i) {
1610 RMEnt->removeOperand(
i - 1);
1613 Edit.eliminateDeadDefs(SpillsToRm,
None,
AA);
1620 if (VRM.hasPhys(Old))
1621 VRM.assignVirt2Phys(New, VRM.getPhys(Old));
1623 VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
1626 if (VRM.hasShape(Old))
1627 VRM.assignVirt2Shape(New, VRM.getShape(Old));