1765 lines · cpp
1//===- InlineSpiller.cpp - Insert spills and restores inline --------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// The inline spiller modifies the machine function directly instead of10// inserting spills and restores in VirtRegMap.11//12//===----------------------------------------------------------------------===//13 14#include "AllocationOrder.h"15#include "SplitKit.h"16#include "llvm/ADT/ArrayRef.h"17#include "llvm/ADT/DenseMap.h"18#include "llvm/ADT/MapVector.h"19#include "llvm/ADT/STLExtras.h"20#include "llvm/ADT/SetVector.h"21#include "llvm/ADT/SmallPtrSet.h"22#include "llvm/ADT/SmallVector.h"23#include "llvm/ADT/Statistic.h"24#include "llvm/CodeGen/LiveInterval.h"25#include "llvm/CodeGen/LiveIntervals.h"26#include "llvm/CodeGen/LiveRangeEdit.h"27#include "llvm/CodeGen/LiveRegMatrix.h"28#include "llvm/CodeGen/LiveStacks.h"29#include "llvm/CodeGen/MachineBasicBlock.h"30#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"31#include "llvm/CodeGen/MachineDominators.h"32#include "llvm/CodeGen/MachineFunction.h"33#include "llvm/CodeGen/MachineInstr.h"34#include "llvm/CodeGen/MachineInstrBuilder.h"35#include "llvm/CodeGen/MachineInstrBundle.h"36#include "llvm/CodeGen/MachineOperand.h"37#include "llvm/CodeGen/MachineRegisterInfo.h"38#include "llvm/CodeGen/SlotIndexes.h"39#include "llvm/CodeGen/Spiller.h"40#include "llvm/CodeGen/StackMaps.h"41#include "llvm/CodeGen/TargetInstrInfo.h"42#include "llvm/CodeGen/TargetOpcodes.h"43#include "llvm/CodeGen/TargetRegisterInfo.h"44#include "llvm/CodeGen/TargetSubtargetInfo.h"45#include "llvm/CodeGen/VirtRegMap.h"46#include "llvm/Config/llvm-config.h"47#include "llvm/Support/BlockFrequency.h"48#include "llvm/Support/BranchProbability.h"49#include "llvm/Support/CommandLine.h"50#include "llvm/Support/Compiler.h"51#include "llvm/Support/Debug.h"52#include "llvm/Support/ErrorHandling.h"53#include "llvm/Support/raw_ostream.h"54#include <cassert>55#include <iterator>56#include <tuple>57#include <utility>58 59using namespace llvm;60 61#define DEBUG_TYPE "regalloc"62 63STATISTIC(NumSpilledRanges, "Number of spilled live ranges");64STATISTIC(NumSnippets, "Number of spilled snippets");65STATISTIC(NumSpills, "Number of spills inserted");66STATISTIC(NumSpillsRemoved, "Number of spills removed");67STATISTIC(NumReloads, "Number of reloads inserted");68STATISTIC(NumReloadsRemoved, "Number of reloads removed");69STATISTIC(NumFolded, "Number of folded stack accesses");70STATISTIC(NumFoldedLoads, "Number of folded loads");71STATISTIC(NumRemats, "Number of rematerialized defs for spilling");72 73static cl::opt<bool>74RestrictStatepointRemat("restrict-statepoint-remat",75 cl::init(false), cl::Hidden,76 cl::desc("Restrict remat for statepoint operands"));77 78namespace {79class HoistSpillHelper : private LiveRangeEdit::Delegate {80 MachineFunction &MF;81 LiveIntervals &LIS;82 LiveStacks &LSS;83 MachineDominatorTree &MDT;84 VirtRegMap &VRM;85 MachineRegisterInfo &MRI;86 const TargetInstrInfo &TII;87 const TargetRegisterInfo &TRI;88 const MachineBlockFrequencyInfo &MBFI;89 90 InsertPointAnalysis IPA;91 92 // Map from StackSlot to the LiveInterval of the original register.93 // Note the LiveInterval of the original register may have been deleted94 // after it is spilled. We keep a copy here to track the range where95 // spills can be moved.96 DenseMap<int, std::unique_ptr<LiveInterval>> StackSlotToOrigLI;97 98 // Map from pair of (StackSlot and Original VNI) to a set of spills which99 // have the same stackslot and have equal values defined by Original VNI.100 // These spills are mergeable and are hoist candidates.101 using MergeableSpillsMap =102 MapVector<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>;103 MergeableSpillsMap MergeableSpills;104 105 /// This is the map from original register to a set containing all its106 /// siblings. To hoist a spill to another BB, we need to find out a live107 /// sibling there and use it as the source of the new spill.108 DenseMap<Register, SmallSetVector<Register, 16>> Virt2SiblingsMap;109 110 bool isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,111 MachineBasicBlock &BB, Register &LiveReg);112 113 void rmRedundantSpills(114 SmallPtrSet<MachineInstr *, 16> &Spills,115 SmallVectorImpl<MachineInstr *> &SpillsToRm,116 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);117 118 void getVisitOrders(119 MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,120 SmallVectorImpl<MachineDomTreeNode *> &Orders,121 SmallVectorImpl<MachineInstr *> &SpillsToRm,122 DenseMap<MachineDomTreeNode *, Register> &SpillsToKeep,123 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);124 125 void runHoistSpills(LiveInterval &OrigLI, VNInfo &OrigVNI,126 SmallPtrSet<MachineInstr *, 16> &Spills,127 SmallVectorImpl<MachineInstr *> &SpillsToRm,128 DenseMap<MachineBasicBlock *, Register> &SpillsToIns);129 130public:131 HoistSpillHelper(const Spiller::RequiredAnalyses &Analyses,132 MachineFunction &mf, VirtRegMap &vrm)133 : MF(mf), LIS(Analyses.LIS), LSS(Analyses.LSS), MDT(Analyses.MDT),134 VRM(vrm), MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()),135 TRI(*mf.getSubtarget().getRegisterInfo()), MBFI(Analyses.MBFI),136 IPA(LIS, mf.getNumBlockIDs()) {}137 138 void addToMergeableSpills(MachineInstr &Spill, int StackSlot,139 Register Original);140 bool rmFromMergeableSpills(MachineInstr &Spill, int StackSlot);141 void hoistAllSpills();142 void LRE_DidCloneVirtReg(Register, Register) override;143};144 145class InlineSpiller : public Spiller {146 MachineFunction &MF;147 LiveIntervals &LIS;148 LiveStacks &LSS;149 VirtRegMap &VRM;150 MachineRegisterInfo &MRI;151 const TargetInstrInfo &TII;152 const TargetRegisterInfo &TRI;153 LiveRegMatrix *Matrix = nullptr;154 155 // Variables that are valid during spill(), but used by multiple methods.156 LiveRangeEdit *Edit = nullptr;157 LiveInterval *StackInt = nullptr;158 int StackSlot;159 Register Original;160 AllocationOrder *Order = nullptr;161 162 // All registers to spill to StackSlot, including the main register.163 SmallVector<Register, 8> RegsToSpill;164 165 // All registers that were replaced by the spiller through some other method,166 // e.g. rematerialization.167 SmallVector<Register, 8> RegsReplaced;168 169 // All COPY instructions to/from snippets.170 // They are ignored since both operands refer to the same stack slot.171 // For bundled copies, this will only include the first header copy.172 SmallPtrSet<MachineInstr*, 8> SnippetCopies;173 174 // Values that failed to remat at some point.175 SmallPtrSet<VNInfo*, 8> UsedValues;176 177 // Dead defs generated during spilling.178 SmallVector<MachineInstr*, 8> DeadDefs;179 180 // Object records spills information and does the hoisting.181 HoistSpillHelper HSpiller;182 183 // Live range weight calculator.184 VirtRegAuxInfo &VRAI;185 186 ~InlineSpiller() override = default;187 188public:189 InlineSpiller(const Spiller::RequiredAnalyses &Analyses, MachineFunction &MF,190 VirtRegMap &VRM, VirtRegAuxInfo &VRAI, LiveRegMatrix *Matrix)191 : MF(MF), LIS(Analyses.LIS), LSS(Analyses.LSS), VRM(VRM),192 MRI(MF.getRegInfo()), TII(*MF.getSubtarget().getInstrInfo()),193 TRI(*MF.getSubtarget().getRegisterInfo()), Matrix(Matrix),194 HSpiller(Analyses, MF, VRM), VRAI(VRAI) {}195 196 void spill(LiveRangeEdit &, AllocationOrder *Order = nullptr) override;197 ArrayRef<Register> getSpilledRegs() override { return RegsToSpill; }198 ArrayRef<Register> getReplacedRegs() override { return RegsReplaced; }199 void postOptimization() override;200 201private:202 bool isSnippet(const LiveInterval &SnipLI);203 void collectRegsToSpill();204 205 bool isRegToSpill(Register Reg) { return is_contained(RegsToSpill, Reg); }206 207 bool isSibling(Register Reg);208 bool hoistSpillInsideBB(LiveInterval &SpillLI, MachineInstr &CopyMI);209 void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);210 211 void markValueUsed(LiveInterval*, VNInfo*);212 bool canGuaranteeAssignmentAfterRemat(Register VReg, MachineInstr &MI);213 bool hasPhysRegAvailable(const MachineInstr &MI);214 bool reMaterializeFor(LiveInterval &, MachineInstr &MI);215 void reMaterializeAll();216 217 bool coalesceStackAccess(MachineInstr *MI, Register Reg);218 bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>>,219 MachineInstr *LoadMI = nullptr);220 void insertReload(Register VReg, SlotIndex, MachineBasicBlock::iterator MI);221 void insertSpill(Register VReg, bool isKill, MachineBasicBlock::iterator MI);222 223 void spillAroundUses(Register Reg);224 void spillAll();225};226 227} // end anonymous namespace228 229Spiller::~Spiller() = default;230 231void Spiller::anchor() {}232 233Spiller *234llvm::createInlineSpiller(const InlineSpiller::RequiredAnalyses &Analyses,235 MachineFunction &MF, VirtRegMap &VRM,236 VirtRegAuxInfo &VRAI, LiveRegMatrix *Matrix) {237 return new InlineSpiller(Analyses, MF, VRM, VRAI, Matrix);238}239 240//===----------------------------------------------------------------------===//241// Snippets242//===----------------------------------------------------------------------===//243 244// When spilling a virtual register, we also spill any snippets it is connected245// to. The snippets are small live ranges that only have a single real use,246// leftovers from live range splitting. Spilling them enables memory operand247// folding or tightens the live range around the single use.248//249// This minimizes register pressure and maximizes the store-to-load distance for250// spill slots which can be important in tight loops.251 252/// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,253/// otherwise return 0.254static Register isCopyOf(const MachineInstr &MI, Register Reg,255 const TargetInstrInfo &TII) {256 if (!TII.isCopyInstr(MI))257 return Register();258 259 const MachineOperand &DstOp = MI.getOperand(0);260 const MachineOperand &SrcOp = MI.getOperand(1);261 262 // TODO: Probably only worth allowing subreg copies with undef dests.263 if (DstOp.getSubReg() != SrcOp.getSubReg())264 return Register();265 if (DstOp.getReg() == Reg)266 return SrcOp.getReg();267 if (SrcOp.getReg() == Reg)268 return DstOp.getReg();269 return Register();270}271 272/// Check for a copy bundle as formed by SplitKit.273static Register isCopyOfBundle(const MachineInstr &FirstMI, Register Reg,274 const TargetInstrInfo &TII) {275 if (!FirstMI.isBundled())276 return isCopyOf(FirstMI, Reg, TII);277 278 assert(!FirstMI.isBundledWithPred() && FirstMI.isBundledWithSucc() &&279 "expected to see first instruction in bundle");280 281 Register SnipReg;282 MachineBasicBlock::const_instr_iterator I = FirstMI.getIterator();283 while (I->isBundledWithSucc()) {284 const MachineInstr &MI = *I;285 auto CopyInst = TII.isCopyInstr(MI);286 if (!CopyInst)287 return Register();288 289 const MachineOperand &DstOp = *CopyInst->Destination;290 const MachineOperand &SrcOp = *CopyInst->Source;291 if (DstOp.getReg() == Reg) {292 if (!SnipReg)293 SnipReg = SrcOp.getReg();294 else if (SnipReg != SrcOp.getReg())295 return Register();296 } else if (SrcOp.getReg() == Reg) {297 if (!SnipReg)298 SnipReg = DstOp.getReg();299 else if (SnipReg != DstOp.getReg())300 return Register();301 }302 303 ++I;304 }305 306 return Register();307}308 309static void getVDefInterval(const MachineInstr &MI, LiveIntervals &LIS) {310 for (const MachineOperand &MO : MI.all_defs())311 if (MO.getReg().isVirtual())312 LIS.getInterval(MO.getReg());313}314 315/// isSnippet - Identify if a live interval is a snippet that should be spilled.316/// It is assumed that SnipLI is a virtual register with the same original as317/// Edit->getReg().318bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {319 Register Reg = Edit->getReg();320 321 // A snippet is a tiny live range with only a single instruction using it322 // besides copies to/from Reg or spills/fills.323 // Exception is done for statepoint instructions which will fold fills324 // into their operands.325 // We accept:326 //327 // %snip = COPY %Reg / FILL fi#328 // %snip = USE %snip329 // %snip = STATEPOINT %snip in var arg area330 // %Reg = COPY %snip / SPILL %snip, fi#331 //332 if (!LIS.intervalIsInOneMBB(SnipLI))333 return false;334 335 // Number of defs should not exceed 2 not accounting defs coming from336 // statepoint instructions.337 unsigned NumValNums = SnipLI.getNumValNums();338 for (auto *VNI : SnipLI.vnis()) {339 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);340 if (MI->getOpcode() == TargetOpcode::STATEPOINT)341 --NumValNums;342 }343 if (NumValNums > 2)344 return false;345 346 MachineInstr *UseMI = nullptr;347 348 // Check that all uses satisfy our criteria.349 for (MachineRegisterInfo::reg_bundle_nodbg_iterator350 RI = MRI.reg_bundle_nodbg_begin(SnipLI.reg()),351 E = MRI.reg_bundle_nodbg_end();352 RI != E;) {353 MachineInstr &MI = *RI++;354 355 // Allow copies to/from Reg.356 if (isCopyOfBundle(MI, Reg, TII))357 continue;358 359 // Allow stack slot loads.360 int FI;361 if (SnipLI.reg() == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)362 continue;363 364 // Allow stack slot stores.365 if (SnipLI.reg() == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)366 continue;367 368 if (StatepointOpers::isFoldableReg(&MI, SnipLI.reg()))369 continue;370 371 // Allow a single additional instruction.372 if (UseMI && &MI != UseMI)373 return false;374 UseMI = &MI;375 }376 return true;377}378 379/// collectRegsToSpill - Collect live range snippets that only have a single380/// real use.381void InlineSpiller::collectRegsToSpill() {382 Register Reg = Edit->getReg();383 384 // Main register always spills.385 RegsToSpill.assign(1, Reg);386 SnippetCopies.clear();387 RegsReplaced.clear();388 389 // Snippets all have the same original, so there can't be any for an original390 // register.391 if (Original == Reg)392 return;393 394 for (MachineInstr &MI : llvm::make_early_inc_range(MRI.reg_bundles(Reg))) {395 Register SnipReg = isCopyOfBundle(MI, Reg, TII);396 if (!isSibling(SnipReg))397 continue;398 LiveInterval &SnipLI = LIS.getInterval(SnipReg);399 if (!isSnippet(SnipLI))400 continue;401 SnippetCopies.insert(&MI);402 if (isRegToSpill(SnipReg))403 continue;404 RegsToSpill.push_back(SnipReg);405 LLVM_DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n');406 ++NumSnippets;407 }408}409 410bool InlineSpiller::isSibling(Register Reg) {411 return Reg.isVirtual() && VRM.getOriginal(Reg) == Original;412}413 414/// It is beneficial to spill to earlier place in the same BB in case415/// as follows:416/// There is an alternative def earlier in the same MBB.417/// Hoist the spill as far as possible in SpillMBB. This can ease418/// register pressure:419///420/// x = def421/// y = use x422/// s = copy x423///424/// Hoisting the spill of s to immediately after the def removes the425/// interference between x and y:426///427/// x = def428/// spill x429/// y = use killed x430///431/// This hoist only helps when the copy kills its source.432///433bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI,434 MachineInstr &CopyMI) {435 SlotIndex Idx = LIS.getInstructionIndex(CopyMI);436#ifndef NDEBUG437 VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot());438 assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy");439#endif440 441 Register SrcReg = CopyMI.getOperand(1).getReg();442 LiveInterval &SrcLI = LIS.getInterval(SrcReg);443 VNInfo *SrcVNI = SrcLI.getVNInfoAt(Idx);444 LiveQueryResult SrcQ = SrcLI.Query(Idx);445 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(SrcVNI->def);446 if (DefMBB != CopyMI.getParent() || !SrcQ.isKill())447 return false;448 449 // Conservatively extend the stack slot range to the range of the original450 // value. We may be able to do better with stack slot coloring by being more451 // careful here.452 assert(StackInt && "No stack slot assigned yet.");453 LiveInterval &OrigLI = LIS.getInterval(Original);454 VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);455 StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));456 LLVM_DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "457 << *StackInt << '\n');458 459 // We are going to spill SrcVNI immediately after its def, so clear out460 // any later spills of the same value.461 eliminateRedundantSpills(SrcLI, SrcVNI);462 463 MachineBasicBlock *MBB = LIS.getMBBFromIndex(SrcVNI->def);464 MachineBasicBlock::iterator MII;465 if (SrcVNI->isPHIDef())466 MII = MBB->SkipPHIsLabelsAndDebug(MBB->begin(), SrcReg);467 else {468 MachineInstr *DefMI = LIS.getInstructionFromIndex(SrcVNI->def);469 assert(DefMI && "Defining instruction disappeared");470 MII = DefMI;471 ++MII;472 }473 MachineInstrSpan MIS(MII, MBB);474 // Insert spill without kill flag immediately after def.475 TII.storeRegToStackSlot(*MBB, MII, SrcReg, false, StackSlot,476 MRI.getRegClass(SrcReg), Register());477 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MII);478 for (const MachineInstr &MI : make_range(MIS.begin(), MII))479 getVDefInterval(MI, LIS);480 --MII; // Point to store instruction.481 LLVM_DEBUG(dbgs() << "\thoisted: " << SrcVNI->def << '\t' << *MII);482 483 // If there is only 1 store instruction is required for spill, add it484 // to mergeable list. In X86 AMX, 2 intructions are required to store.485 // We disable the merge for this case.486 if (MIS.begin() == MII)487 HSpiller.addToMergeableSpills(*MII, StackSlot, Original);488 ++NumSpills;489 return true;490}491 492/// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any493/// redundant spills of this value in SLI.reg and sibling copies.494void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {495 assert(VNI && "Missing value");496 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;497 WorkList.push_back(std::make_pair(&SLI, VNI));498 assert(StackInt && "No stack slot assigned yet.");499 500 do {501 LiveInterval *LI;502 std::tie(LI, VNI) = WorkList.pop_back_val();503 Register Reg = LI->reg();504 LLVM_DEBUG(dbgs() << "Checking redundant spills for " << VNI->id << '@'505 << VNI->def << " in " << *LI << '\n');506 507 // Regs to spill are taken care of.508 if (isRegToSpill(Reg))509 continue;510 511 // Add all of VNI's live range to StackInt.512 StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));513 LLVM_DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n');514 515 // Find all spills and copies of VNI.516 for (MachineInstr &MI :517 llvm::make_early_inc_range(MRI.use_nodbg_bundles(Reg))) {518 if (!MI.mayStore() && !TII.isCopyInstr(MI))519 continue;520 SlotIndex Idx = LIS.getInstructionIndex(MI);521 if (LI->getVNInfoAt(Idx) != VNI)522 continue;523 524 // Follow sibling copies down the dominator tree.525 if (Register DstReg = isCopyOfBundle(MI, Reg, TII)) {526 if (isSibling(DstReg)) {527 LiveInterval &DstLI = LIS.getInterval(DstReg);528 VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot());529 assert(DstVNI && "Missing defined value");530 assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot");531 532 WorkList.push_back(std::make_pair(&DstLI, DstVNI));533 }534 continue;535 }536 537 // Erase spills.538 int FI;539 if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {540 LLVM_DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << MI);541 // eliminateDeadDefs won't normally remove stores, so switch opcode.542 MI.setDesc(TII.get(TargetOpcode::KILL));543 DeadDefs.push_back(&MI);544 ++NumSpillsRemoved;545 if (HSpiller.rmFromMergeableSpills(MI, StackSlot))546 --NumSpills;547 }548 }549 } while (!WorkList.empty());550}551 552//===----------------------------------------------------------------------===//553// Rematerialization554//===----------------------------------------------------------------------===//555 556/// markValueUsed - Remember that VNI failed to rematerialize, so its defining557/// instruction cannot be eliminated. See through snippet copies558void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) {559 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;560 WorkList.push_back(std::make_pair(LI, VNI));561 do {562 std::tie(LI, VNI) = WorkList.pop_back_val();563 if (!UsedValues.insert(VNI).second)564 continue;565 566 if (VNI->isPHIDef()) {567 MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);568 for (MachineBasicBlock *P : MBB->predecessors()) {569 VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(P));570 if (PVNI)571 WorkList.push_back(std::make_pair(LI, PVNI));572 }573 continue;574 }575 576 // Follow snippet copies.577 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);578 if (!SnippetCopies.count(MI))579 continue;580 LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg());581 assert(isRegToSpill(SnipLI.reg()) && "Unexpected register in copy");582 VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true));583 assert(SnipVNI && "Snippet undefined before copy");584 WorkList.push_back(std::make_pair(&SnipLI, SnipVNI));585 } while (!WorkList.empty());586}587 588bool InlineSpiller::canGuaranteeAssignmentAfterRemat(Register VReg,589 MachineInstr &MI) {590 if (!RestrictStatepointRemat)591 return true;592 // Here's a quick explanation of the problem we're trying to handle here:593 // * There are some pseudo instructions with more vreg uses than there are594 // physical registers on the machine.595 // * This is normally handled by spilling the vreg, and folding the reload596 // into the user instruction. (Thus decreasing the number of used vregs597 // until the remainder can be assigned to physregs.)598 // * However, since we may try to spill vregs in any order, we can end up599 // trying to spill each operand to the instruction, and then rematting it600 // instead. When that happens, the new live intervals (for the remats) are601 // expected to be trivially assignable (i.e. RS_Done). However, since we602 // may have more remats than physregs, we're guaranteed to fail to assign603 // one.604 // At the moment, we only handle this for STATEPOINTs since they're the only605 // pseudo op where we've seen this. If we start seeing other instructions606 // with the same problem, we need to revisit this.607 if (MI.getOpcode() != TargetOpcode::STATEPOINT)608 return true;609 // For STATEPOINTs we allow re-materialization for fixed arguments only hoping610 // that number of physical registers is enough to cover all fixed arguments.611 // If it is not true we need to revisit it.612 for (unsigned Idx = StatepointOpers(&MI).getVarIdx(),613 EndIdx = MI.getNumOperands();614 Idx < EndIdx; ++Idx) {615 MachineOperand &MO = MI.getOperand(Idx);616 if (MO.isReg() && MO.getReg() == VReg)617 return false;618 }619 return true;620}621 622/// hasPhysRegAvailable - Check if there is an available physical register for623/// rematerialization.624bool InlineSpiller::hasPhysRegAvailable(const MachineInstr &MI) {625 if (!Order || !Matrix)626 return false;627 628 SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);629 SlotIndex PrevIdx = UseIdx.getPrevSlot();630 631 for (MCPhysReg PhysReg : *Order) {632 if (!Matrix->checkInterference(PrevIdx, UseIdx, PhysReg))633 return true;634 }635 636 return false;637}638 639/// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.640bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) {641 // Analyze instruction642 SmallVector<std::pair<MachineInstr *, unsigned>, 8> Ops;643 VirtRegInfo RI = AnalyzeVirtRegInBundle(MI, VirtReg.reg(), &Ops);644 645 // Defs without reads will be deleted if unused after remat is646 // completed for other users of the virtual register.647 if (!RI.Reads) {648 LLVM_DEBUG(dbgs() << "\tskipping remat of def " << MI);649 return false;650 }651 652 SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);653 VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex());654 655 if (!ParentVNI) {656 LLVM_DEBUG(dbgs() << "\tadding <undef> flags: ");657 for (MachineOperand &MO : MI.all_uses())658 if (MO.getReg() == VirtReg.reg())659 MO.setIsUndef();660 LLVM_DEBUG(dbgs() << UseIdx << '\t' << MI);661 return true;662 }663 664 // Snippets copies are ignored for remat, and will be deleted if they665 // don't feed a live user after rematerialization completes.666 if (SnippetCopies.count(&MI)) {667 LLVM_DEBUG(dbgs() << "\tskipping remat snippet copy for " << UseIdx << '\t'668 << MI);669 return false;670 }671 672 LiveInterval &OrigLI = LIS.getInterval(Original);673 VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);674 assert(OrigVNI && "corrupted sub-interval");675 MachineInstr *DefMI = LIS.getInstructionFromIndex(OrigVNI->def);676 // This can happen if for two reasons: 1) This could be a phi valno,677 // or 2) the remat def has already been removed from the original678 // live interval; this happens if we rematted to all uses, and679 // then further split one of those live ranges.680 if (!DefMI) {681 markValueUsed(&VirtReg, ParentVNI);682 LLVM_DEBUG(dbgs() << "\tcannot remat missing def for " << UseIdx << '\t'683 << MI);684 return false;685 }686 687 LiveRangeEdit::Remat RM(ParentVNI);688 RM.OrigMI = DefMI;689 if (!Edit->canRematerializeAt(RM, UseIdx)) {690 markValueUsed(&VirtReg, ParentVNI);691 LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI);692 return false;693 }694 695 // If the instruction also writes VirtReg.reg, it had better not require the696 // same register for uses and defs.697 if (RI.Tied) {698 markValueUsed(&VirtReg, ParentVNI);699 LLVM_DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << MI);700 return false;701 }702 703 // Before rematerializing into a register for a single instruction, try to704 // fold a load into the instruction. That avoids allocating a new register.705 if (RM.OrigMI->canFoldAsLoad() &&706 (RM.OrigMI->mayLoad() || !hasPhysRegAvailable(MI)) &&707 foldMemoryOperand(Ops, RM.OrigMI)) {708 Edit->markRematerialized(RM.ParentVNI);709 ++NumFoldedLoads;710 return true;711 }712 713 // If we can't guarantee that we'll be able to actually assign the new vreg,714 // we can't remat.715 if (!canGuaranteeAssignmentAfterRemat(VirtReg.reg(), MI)) {716 markValueUsed(&VirtReg, ParentVNI);717 LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI);718 return false;719 }720 721 // Allocate a new register for the remat.722 Register NewVReg = Edit->createFrom(Original);723 724 // Constrain it to the register class of MI.725 MRI.constrainRegClass(NewVReg, MRI.getRegClass(VirtReg.reg()));726 727 // Finally we can rematerialize OrigMI before MI.728 SlotIndex DefIdx =729 Edit->rematerializeAt(*MI.getParent(), MI, NewVReg, RM, TRI);730 731 // We take the DebugLoc from MI, since OrigMI may be attributed to a732 // different source location.733 auto *NewMI = LIS.getInstructionFromIndex(DefIdx);734 NewMI->setDebugLoc(MI.getDebugLoc());735 736 (void)DefIdx;737 LLVM_DEBUG(dbgs() << "\tremat: " << DefIdx << '\t'738 << *LIS.getInstructionFromIndex(DefIdx));739 740 // Replace operands741 for (const auto &OpPair : Ops) {742 MachineOperand &MO = OpPair.first->getOperand(OpPair.second);743 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg()) {744 MO.setReg(NewVReg);745 MO.setIsKill();746 }747 }748 LLVM_DEBUG(dbgs() << "\t " << UseIdx << '\t' << MI << '\n');749 750 ++NumRemats;751 return true;752}753 754/// reMaterializeAll - Try to rematerialize as many uses as possible,755/// and trim the live ranges after.756void InlineSpiller::reMaterializeAll() {757 UsedValues.clear();758 759 // Try to remat before all uses of snippets.760 bool anyRemat = false;761 for (Register Reg : RegsToSpill) {762 LiveInterval &LI = LIS.getInterval(Reg);763 for (MachineInstr &MI : llvm::make_early_inc_range(MRI.reg_bundles(Reg))) {764 // Debug values are not allowed to affect codegen.765 if (MI.isDebugValue())766 continue;767 768 assert(!MI.isDebugInstr() && "Did not expect to find a use in debug "769 "instruction that isn't a DBG_VALUE");770 771 anyRemat |= reMaterializeFor(LI, MI);772 }773 }774 if (!anyRemat)775 return;776 777 // Remove any values that were completely rematted.778 for (Register Reg : RegsToSpill) {779 LiveInterval &LI = LIS.getInterval(Reg);780 for (VNInfo *VNI : LI.vnis()) {781 if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI))782 continue;783 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);784 MI->addRegisterDead(Reg, &TRI);785 if (!MI->allDefsAreDead())786 continue;787 LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);788 DeadDefs.push_back(MI);789 // If MI is a bundle header, also try removing copies inside the bundle,790 // otherwise the verifier would complain "live range continues after dead791 // def flag".792 if (MI->isBundledWithSucc() && !MI->isBundledWithPred()) {793 MachineBasicBlock::instr_iterator BeginIt = MI->getIterator(),794 EndIt = MI->getParent()->instr_end();795 ++BeginIt; // Skip MI that was already handled.796 797 bool OnlyDeadCopies = true;798 for (MachineBasicBlock::instr_iterator It = BeginIt;799 It != EndIt && It->isBundledWithPred(); ++It) {800 801 auto DestSrc = TII.isCopyInstr(*It);802 bool IsCopyToDeadReg =803 DestSrc && DestSrc->Destination->getReg() == Reg;804 if (!IsCopyToDeadReg) {805 OnlyDeadCopies = false;806 break;807 }808 }809 if (OnlyDeadCopies) {810 for (MachineBasicBlock::instr_iterator It = BeginIt;811 It != EndIt && It->isBundledWithPred(); ++It) {812 It->addRegisterDead(Reg, &TRI);813 LLVM_DEBUG(dbgs() << "All defs dead: " << *It);814 DeadDefs.push_back(&*It);815 }816 }817 }818 }819 }820 821 // Eliminate dead code after remat. Note that some snippet copies may be822 // deleted here.823 if (DeadDefs.empty())824 return;825 LLVM_DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n");826 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill);827 828 // LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions829 // after rematerialization. To remove a VNI for a vreg from its LiveInterval,830 // LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all831 // removed, PHI VNI are still left in the LiveInterval.832 // So to get rid of unused reg, we need to check whether it has non-dbg833 // reference instead of whether it has non-empty interval.834 unsigned ResultPos = 0;835 for (Register Reg : RegsToSpill) {836 if (MRI.reg_nodbg_empty(Reg)) {837 Edit->eraseVirtReg(Reg);838 RegsReplaced.push_back(Reg);839 continue;840 }841 842 assert(LIS.hasInterval(Reg) &&843 (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) &&844 "Empty and not used live-range?!");845 846 RegsToSpill[ResultPos++] = Reg;847 }848 RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end());849 LLVM_DEBUG(dbgs() << RegsToSpill.size()850 << " registers to spill after remat.\n");851}852 853//===----------------------------------------------------------------------===//854// Spilling855//===----------------------------------------------------------------------===//856 857/// If MI is a load or store of StackSlot, it can be removed.858bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, Register Reg) {859 int FI = 0;860 Register InstrReg = TII.isLoadFromStackSlot(*MI, FI);861 bool IsLoad = InstrReg.isValid();862 if (!IsLoad)863 InstrReg = TII.isStoreToStackSlot(*MI, FI);864 865 // We have a stack access. Is it the right register and slot?866 if (InstrReg != Reg || FI != StackSlot)867 return false;868 869 if (!IsLoad)870 HSpiller.rmFromMergeableSpills(*MI, StackSlot);871 872 LLVM_DEBUG(dbgs() << "Coalescing stack access: " << *MI);873 LIS.RemoveMachineInstrFromMaps(*MI);874 MI->eraseFromParent();875 876 if (IsLoad) {877 ++NumReloadsRemoved;878 --NumReloads;879 } else {880 ++NumSpillsRemoved;881 --NumSpills;882 }883 884 return true;885}886 887#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)888LLVM_DUMP_METHOD889// Dump the range of instructions from B to E with their slot indexes.890static void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B,891 MachineBasicBlock::iterator E,892 LiveIntervals const &LIS,893 const char *const header,894 Register VReg = Register()) {895 char NextLine = '\n';896 char SlotIndent = '\t';897 898 if (std::next(B) == E) {899 NextLine = ' ';900 SlotIndent = ' ';901 }902 903 dbgs() << '\t' << header << ": " << NextLine;904 905 for (MachineBasicBlock::iterator I = B; I != E; ++I) {906 SlotIndex Idx = LIS.getInstructionIndex(*I).getRegSlot();907 908 // If a register was passed in and this instruction has it as a909 // destination that is marked as an early clobber, print the910 // early-clobber slot index.911 if (VReg) {912 MachineOperand *MO = I->findRegisterDefOperand(VReg, /*TRI=*/nullptr);913 if (MO && MO->isEarlyClobber())914 Idx = Idx.getRegSlot(true);915 }916 917 dbgs() << SlotIndent << Idx << '\t' << *I;918 }919}920#endif921 922/// foldMemoryOperand - Try folding stack slot references in Ops into their923/// instructions.924///925/// @param Ops Operand indices from AnalyzeVirtRegInBundle().926/// @param LoadMI Load instruction to use instead of stack slot when non-null.927/// @return True on success.928bool InlineSpiller::929foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>> Ops,930 MachineInstr *LoadMI) {931 if (Ops.empty())932 return false;933 // Don't attempt folding in bundles.934 MachineInstr *MI = Ops.front().first;935 if (Ops.back().first != MI || MI->isBundled())936 return false;937 938 bool WasCopy = TII.isCopyInstr(*MI).has_value();939 Register ImpReg;940 941 // TII::foldMemoryOperand will do what we need here for statepoint942 // (fold load into use and remove corresponding def). We will replace943 // uses of removed def with loads (spillAroundUses).944 // For that to work we need to untie def and use to pass it through945 // foldMemoryOperand and signal foldPatchpoint that it is allowed to946 // fold them.947 bool UntieRegs = MI->getOpcode() == TargetOpcode::STATEPOINT;948 949 // Spill subregs if the target allows it.950 // We always want to spill subregs for stackmap/patchpoint pseudos.951 bool SpillSubRegs = TII.isSubregFoldable() ||952 MI->getOpcode() == TargetOpcode::STATEPOINT ||953 MI->getOpcode() == TargetOpcode::PATCHPOINT ||954 MI->getOpcode() == TargetOpcode::STACKMAP;955 956 // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied957 // operands.958 SmallVector<unsigned, 8> FoldOps;959 for (const auto &OpPair : Ops) {960 unsigned Idx = OpPair.second;961 assert(MI == OpPair.first && "Instruction conflict during operand folding");962 MachineOperand &MO = MI->getOperand(Idx);963 964 // No point restoring an undef read, and we'll produce an invalid live965 // interval.966 // TODO: Is this really the correct way to handle undef tied uses?967 if (MO.isUse() && !MO.readsReg() && !MO.isTied())968 continue;969 970 if (MO.isImplicit()) {971 ImpReg = MO.getReg();972 continue;973 }974 975 if (!SpillSubRegs && MO.getSubReg())976 return false;977 // We cannot fold a load instruction into a def.978 if (LoadMI && MO.isDef())979 return false;980 // Tied use operands should not be passed to foldMemoryOperand.981 if (UntieRegs || !MI->isRegTiedToDefOperand(Idx))982 FoldOps.push_back(Idx);983 }984 985 // If we only have implicit uses, we won't be able to fold that.986 // Moreover, TargetInstrInfo::foldMemoryOperand will assert if we try!987 if (FoldOps.empty())988 return false;989 990 MachineInstrSpan MIS(MI, MI->getParent());991 992 SmallVector<std::pair<unsigned, unsigned> > TiedOps;993 if (UntieRegs)994 for (unsigned Idx : FoldOps) {995 MachineOperand &MO = MI->getOperand(Idx);996 if (!MO.isTied())997 continue;998 unsigned Tied = MI->findTiedOperandIdx(Idx);999 if (MO.isUse())1000 TiedOps.emplace_back(Tied, Idx);1001 else {1002 assert(MO.isDef() && "Tied to not use and def?");1003 TiedOps.emplace_back(Idx, Tied);1004 }1005 MI->untieRegOperand(Idx);1006 }1007 1008 MachineInstr *FoldMI =1009 LoadMI ? TII.foldMemoryOperand(*MI, FoldOps, *LoadMI, &LIS)1010 : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS, &VRM);1011 if (!FoldMI) {1012 // Re-tie operands.1013 for (auto Tied : TiedOps)1014 MI->tieOperands(Tied.first, Tied.second);1015 return false;1016 }1017 1018 // Remove LIS for any dead defs in the original MI not in FoldMI.1019 for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) {1020 if (!MO->isReg())1021 continue;1022 Register Reg = MO->getReg();1023 if (!Reg || Reg.isVirtual() || MRI.isReserved(Reg)) {1024 continue;1025 }1026 // Skip non-Defs, including undef uses and internal reads.1027 if (MO->isUse())1028 continue;1029 PhysRegInfo RI = AnalyzePhysRegInBundle(*FoldMI, Reg, &TRI);1030 if (RI.FullyDefined)1031 continue;1032 // FoldMI does not define this physreg. Remove the LI segment.1033 assert(MO->isDead() && "Cannot fold physreg def");1034 SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();1035 LIS.removePhysRegDefAt(Reg.asMCReg(), Idx);1036 }1037 1038 int FI;1039 if (TII.isStoreToStackSlot(*MI, FI) &&1040 HSpiller.rmFromMergeableSpills(*MI, FI))1041 --NumSpills;1042 LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI);1043 // Update the call info.1044 if (MI->isCandidateForAdditionalCallInfo())1045 MI->getMF()->moveAdditionalCallInfo(MI, FoldMI);1046 1047 // If we've folded a store into an instruction labelled with debug-info,1048 // record a substitution from the old operand to the memory operand. Handle1049 // the simple common case where operand 0 is the one being folded, plus when1050 // the destination operand is also a tied def. More values could be1051 // substituted / preserved with more analysis.1052 if (MI->peekDebugInstrNum() && Ops[0].second == 0) {1053 // Helper lambda.1054 auto MakeSubstitution = [this,FoldMI,MI,&Ops]() {1055 // Substitute old operand zero to the new instructions memory operand.1056 unsigned OldOperandNum = Ops[0].second;1057 unsigned NewNum = FoldMI->getDebugInstrNum();1058 unsigned OldNum = MI->getDebugInstrNum();1059 MF.makeDebugValueSubstitution({OldNum, OldOperandNum},1060 {NewNum, MachineFunction::DebugOperandMemNumber});1061 };1062 1063 const MachineOperand &Op0 = MI->getOperand(Ops[0].second);1064 if (Ops.size() == 1 && Op0.isDef()) {1065 MakeSubstitution();1066 } else if (Ops.size() == 2 && Op0.isDef() && MI->getOperand(1).isTied() &&1067 Op0.getReg() == MI->getOperand(1).getReg()) {1068 MakeSubstitution();1069 }1070 } else if (MI->peekDebugInstrNum()) {1071 // This is a debug-labelled instruction, but the operand being folded isn't1072 // at operand zero. Most likely this means it's a load being folded in.1073 // Substitute any register defs from operand zero up to the one being1074 // folded -- past that point, we don't know what the new operand indexes1075 // will be.1076 MF.substituteDebugValuesForInst(*MI, *FoldMI, Ops[0].second);1077 }1078 1079 MI->eraseFromParent();1080 1081 // Insert any new instructions other than FoldMI into the LIS maps.1082 assert(!MIS.empty() && "Unexpected empty span of instructions!");1083 for (MachineInstr &MI : MIS)1084 if (&MI != FoldMI)1085 LIS.InsertMachineInstrInMaps(MI);1086 1087 // TII.foldMemoryOperand may have left some implicit operands on the1088 // instruction. Strip them.1089 if (ImpReg)1090 for (unsigned i = FoldMI->getNumOperands(); i; --i) {1091 MachineOperand &MO = FoldMI->getOperand(i - 1);1092 if (!MO.isReg() || !MO.isImplicit())1093 break;1094 if (MO.getReg() == ImpReg)1095 FoldMI->removeOperand(i - 1);1096 }1097 1098 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS,1099 "folded"));1100 1101 if (!WasCopy)1102 ++NumFolded;1103 else if (Ops.front().second == 0) {1104 ++NumSpills;1105 // If there is only 1 store instruction is required for spill, add it1106 // to mergeable list. In X86 AMX, 2 intructions are required to store.1107 // We disable the merge for this case.1108 if (std::distance(MIS.begin(), MIS.end()) <= 1)1109 HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original);1110 } else1111 ++NumReloads;1112 return true;1113}1114 1115void InlineSpiller::insertReload(Register NewVReg,1116 SlotIndex Idx,1117 MachineBasicBlock::iterator MI) {1118 MachineBasicBlock &MBB = *MI->getParent();1119 1120 MachineInstrSpan MIS(MI, &MBB);1121 TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot,1122 MRI.getRegClass(NewVReg), Register());1123 1124 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI);1125 1126 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload",1127 NewVReg));1128 ++NumReloads;1129}1130 1131/// Check if \p Def fully defines a VReg with an undefined value.1132/// If that's the case, that means the value of VReg is actually1133/// not relevant.1134static bool isRealSpill(const MachineInstr &Def) {1135 if (!Def.isImplicitDef())1136 return true;1137 1138 // We can say that the VReg defined by Def is undef, only if it is1139 // fully defined by Def. Otherwise, some of the lanes may not be1140 // undef and the value of the VReg matters.1141 return Def.getOperand(0).getSubReg();1142}1143 1144/// insertSpill - Insert a spill of NewVReg after MI.1145void InlineSpiller::insertSpill(Register NewVReg, bool isKill,1146 MachineBasicBlock::iterator MI) {1147 // Spill are not terminators, so inserting spills after terminators will1148 // violate invariants in MachineVerifier.1149 assert(!MI->isTerminator() && "Inserting a spill after a terminator");1150 MachineBasicBlock &MBB = *MI->getParent();1151 1152 MachineInstrSpan MIS(MI, &MBB);1153 MachineBasicBlock::iterator SpillBefore = std::next(MI);1154 bool IsRealSpill = isRealSpill(*MI);1155 1156 if (IsRealSpill)1157 TII.storeRegToStackSlot(MBB, SpillBefore, NewVReg, isKill, StackSlot,1158 MRI.getRegClass(NewVReg), Register());1159 else1160 // Don't spill undef value.1161 // Anything works for undef, in particular keeping the memory1162 // uninitialized is a viable option and it saves code size and1163 // run time.1164 BuildMI(MBB, SpillBefore, MI->getDebugLoc(), TII.get(TargetOpcode::KILL))1165 .addReg(NewVReg, getKillRegState(isKill));1166 1167 MachineBasicBlock::iterator Spill = std::next(MI);1168 LIS.InsertMachineInstrRangeInMaps(Spill, MIS.end());1169 for (const MachineInstr &MI : make_range(Spill, MIS.end()))1170 getVDefInterval(MI, LIS);1171 1172 LLVM_DEBUG(1173 dumpMachineInstrRangeWithSlotIndex(Spill, MIS.end(), LIS, "spill"));1174 ++NumSpills;1175 // If there is only 1 store instruction is required for spill, add it1176 // to mergeable list. In X86 AMX, 2 intructions are required to store.1177 // We disable the merge for this case.1178 if (IsRealSpill && std::distance(Spill, MIS.end()) <= 1)1179 HSpiller.addToMergeableSpills(*Spill, StackSlot, Original);1180}1181 1182/// spillAroundUses - insert spill code around each use of Reg.1183void InlineSpiller::spillAroundUses(Register Reg) {1184 LLVM_DEBUG(dbgs() << "spillAroundUses " << printReg(Reg) << '\n');1185 LiveInterval &OldLI = LIS.getInterval(Reg);1186 1187 // Iterate over instructions using Reg.1188 for (MachineInstr &MI : llvm::make_early_inc_range(MRI.reg_bundles(Reg))) {1189 // Debug values are not allowed to affect codegen.1190 if (MI.isDebugValue()) {1191 // Modify DBG_VALUE now that the value is in a spill slot.1192 MachineBasicBlock *MBB = MI.getParent();1193 LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:\t" << MI);1194 buildDbgValueForSpill(*MBB, &MI, MI, StackSlot, Reg);1195 MBB->erase(MI);1196 continue;1197 }1198 1199 assert(!MI.isDebugInstr() && "Did not expect to find a use in debug "1200 "instruction that isn't a DBG_VALUE");1201 1202 // Ignore copies to/from snippets. We'll delete them.1203 if (SnippetCopies.count(&MI))1204 continue;1205 1206 // Stack slot accesses may coalesce away.1207 if (coalesceStackAccess(&MI, Reg))1208 continue;1209 1210 // Analyze instruction.1211 SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops;1212 VirtRegInfo RI = AnalyzeVirtRegInBundle(MI, Reg, &Ops);1213 1214 // Find the slot index where this instruction reads and writes OldLI.1215 // This is usually the def slot, except for tied early clobbers.1216 SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot();1217 if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true)))1218 if (SlotIndex::isSameInstr(Idx, VNI->def))1219 Idx = VNI->def;1220 1221 // Check for a sibling copy.1222 Register SibReg = isCopyOfBundle(MI, Reg, TII);1223 if (SibReg && isSibling(SibReg)) {1224 // This may actually be a copy between snippets.1225 if (isRegToSpill(SibReg)) {1226 LLVM_DEBUG(dbgs() << "Found new snippet copy: " << MI);1227 SnippetCopies.insert(&MI);1228 continue;1229 }1230 if (RI.Writes) {1231 if (hoistSpillInsideBB(OldLI, MI)) {1232 // This COPY is now dead, the value is already in the stack slot.1233 MI.getOperand(0).setIsDead();1234 DeadDefs.push_back(&MI);1235 continue;1236 }1237 } else {1238 // This is a reload for a sib-reg copy. Drop spills downstream.1239 LiveInterval &SibLI = LIS.getInterval(SibReg);1240 eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx));1241 // The COPY will fold to a reload below.1242 }1243 }1244 1245 // Attempt to fold memory ops.1246 if (foldMemoryOperand(Ops))1247 continue;1248 1249 // Create a new virtual register for spill/fill.1250 // FIXME: Infer regclass from instruction alone.1251 Register NewVReg = Edit->createFrom(Reg);1252 1253 if (RI.Reads)1254 insertReload(NewVReg, Idx, &MI);1255 1256 // Rewrite instruction operands.1257 bool hasLiveDef = false;1258 for (const auto &OpPair : Ops) {1259 MachineOperand &MO = OpPair.first->getOperand(OpPair.second);1260 MO.setReg(NewVReg);1261 if (MO.isUse()) {1262 if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))1263 MO.setIsKill();1264 } else {1265 if (!MO.isDead())1266 hasLiveDef = true;1267 }1268 }1269 LLVM_DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << MI << '\n');1270 1271 // FIXME: Use a second vreg if instruction has no tied ops.1272 if (RI.Writes)1273 if (hasLiveDef)1274 insertSpill(NewVReg, true, &MI);1275 }1276}1277 1278/// spillAll - Spill all registers remaining after rematerialization.1279void InlineSpiller::spillAll() {1280 // Update LiveStacks now that we are committed to spilling.1281 if (StackSlot == VirtRegMap::NO_STACK_SLOT) {1282 StackSlot = VRM.assignVirt2StackSlot(Original);1283 StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original));1284 StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator());1285 } else1286 StackInt = &LSS.getInterval(StackSlot);1287 1288 if (Original != Edit->getReg())1289 VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);1290 1291 assert(StackInt->getNumValNums() == 1 && "Bad stack interval values");1292 for (Register Reg : RegsToSpill)1293 StackInt->MergeSegmentsInAsValue(LIS.getInterval(Reg),1294 StackInt->getValNumInfo(0));1295 LLVM_DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n');1296 1297 // Spill around uses of all RegsToSpill.1298 for (Register Reg : RegsToSpill) {1299 spillAroundUses(Reg);1300 // Assign all of the spilled registers to the slot so that1301 // LiveDebugVariables knows about these locations later on.1302 if (VRM.getStackSlot(Reg) == VirtRegMap::NO_STACK_SLOT)1303 VRM.assignVirt2StackSlot(Reg, StackSlot);1304 }1305 1306 // Hoisted spills may cause dead code.1307 if (!DeadDefs.empty()) {1308 LLVM_DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n");1309 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill);1310 }1311 1312 // Finally delete the SnippetCopies.1313 for (Register Reg : RegsToSpill) {1314 for (MachineInstr &MI :1315 llvm::make_early_inc_range(MRI.reg_instructions(Reg))) {1316 assert(SnippetCopies.count(&MI) && "Remaining use wasn't a snippet copy");1317 // FIXME: Do this with a LiveRangeEdit callback.1318 LIS.getSlotIndexes()->removeSingleMachineInstrFromMaps(MI);1319 MI.eraseFromBundle();1320 }1321 }1322 1323 // Delete all spilled registers.1324 for (Register Reg : RegsToSpill)1325 Edit->eraseVirtReg(Reg);1326}1327 1328void InlineSpiller::spill(LiveRangeEdit &edit, AllocationOrder *order) {1329 ++NumSpilledRanges;1330 Edit = &edit;1331 Order = order;1332 assert(!edit.getReg().isStack() && "Trying to spill a stack slot.");1333 // Share a stack slot among all descendants of Original.1334 Original = VRM.getOriginal(edit.getReg());1335 StackSlot = VRM.getStackSlot(Original);1336 StackInt = nullptr;1337 1338 LLVM_DEBUG(dbgs() << "Inline spilling "1339 << TRI.getRegClassName(MRI.getRegClass(edit.getReg()))1340 << ':' << edit.getParent() << "\nFrom original "1341 << printReg(Original) << '\n');1342 assert(edit.getParent().isSpillable() &&1343 "Attempting to spill already spilled value.");1344 assert(DeadDefs.empty() && "Previous spill didn't remove dead defs");1345 1346 collectRegsToSpill();1347 reMaterializeAll();1348 1349 // Remat may handle everything.1350 if (!RegsToSpill.empty())1351 spillAll();1352 1353 Edit->calculateRegClassAndHint(MF, VRAI);1354}1355 1356/// Optimizations after all the reg selections and spills are done.1357void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); }1358 1359/// When a spill is inserted, add the spill to MergeableSpills map.1360void HoistSpillHelper::addToMergeableSpills(MachineInstr &Spill, int StackSlot,1361 Register Original) {1362 BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();1363 LiveInterval &OrigLI = LIS.getInterval(Original);1364 // save a copy of LiveInterval in StackSlotToOrigLI because the original1365 // LiveInterval may be cleared after all its references are spilled.1366 1367 auto [Place, Inserted] = StackSlotToOrigLI.try_emplace(StackSlot);1368 if (Inserted) {1369 auto LI = std::make_unique<LiveInterval>(OrigLI.reg(), OrigLI.weight());1370 LI->assign(OrigLI, Allocator);1371 Place->second = std::move(LI);1372 }1373 1374 SlotIndex Idx = LIS.getInstructionIndex(Spill);1375 VNInfo *OrigVNI = Place->second->getVNInfoAt(Idx.getRegSlot());1376 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);1377 MergeableSpills[MIdx].insert(&Spill);1378}1379 1380/// When a spill is removed, remove the spill from MergeableSpills map.1381/// Return true if the spill is removed successfully.1382bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr &Spill,1383 int StackSlot) {1384 auto It = StackSlotToOrigLI.find(StackSlot);1385 if (It == StackSlotToOrigLI.end())1386 return false;1387 SlotIndex Idx = LIS.getInstructionIndex(Spill);1388 VNInfo *OrigVNI = It->second->getVNInfoAt(Idx.getRegSlot());1389 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);1390 return MergeableSpills[MIdx].erase(&Spill);1391}1392 1393/// Check BB to see if it is a possible target BB to place a hoisted spill,1394/// i.e., there should be a living sibling of OrigReg at the insert point.1395bool HoistSpillHelper::isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,1396 MachineBasicBlock &BB, Register &LiveReg) {1397 SlotIndex Idx = IPA.getLastInsertPoint(OrigLI, BB);1398 // The original def could be after the last insert point in the root block,1399 // we can't hoist to here.1400 if (Idx < OrigVNI.def) {1401 // TODO: We could be better here. If LI is not alive in landing pad1402 // we could hoist spill after LIP.1403 LLVM_DEBUG(dbgs() << "can't spill in root block - def after LIP\n");1404 return false;1405 }1406 Register OrigReg = OrigLI.reg();1407 SmallSetVector<Register, 16> &Siblings = Virt2SiblingsMap[OrigReg];1408 assert(OrigLI.getVNInfoAt(Idx) == &OrigVNI && "Unexpected VNI");1409 1410 for (const Register &SibReg : Siblings) {1411 LiveInterval &LI = LIS.getInterval(SibReg);1412 VNInfo *VNI = LI.getVNInfoAt(Idx);1413 if (VNI) {1414 LiveReg = SibReg;1415 return true;1416 }1417 }1418 return false;1419}1420 1421/// Remove redundant spills in the same BB. Save those redundant spills in1422/// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map.1423void HoistSpillHelper::rmRedundantSpills(1424 SmallPtrSet<MachineInstr *, 16> &Spills,1425 SmallVectorImpl<MachineInstr *> &SpillsToRm,1426 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {1427 // For each spill saw, check SpillBBToSpill[] and see if its BB already has1428 // another spill inside. If a BB contains more than one spill, only keep the1429 // earlier spill with smaller SlotIndex.1430 for (auto *const CurrentSpill : Spills) {1431 MachineBasicBlock *Block = CurrentSpill->getParent();1432 MachineDomTreeNode *Node = MDT.getNode(Block);1433 MachineInstr *PrevSpill = SpillBBToSpill[Node];1434 if (PrevSpill) {1435 SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill);1436 SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill);1437 MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;1438 MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;1439 SpillsToRm.push_back(SpillToRm);1440 SpillBBToSpill[MDT.getNode(Block)] = SpillToKeep;1441 } else {1442 SpillBBToSpill[MDT.getNode(Block)] = CurrentSpill;1443 }1444 }1445 for (auto *const SpillToRm : SpillsToRm)1446 Spills.erase(SpillToRm);1447}1448 1449/// Starting from \p Root find a top-down traversal order of the dominator1450/// tree to visit all basic blocks containing the elements of \p Spills.1451/// Redundant spills will be found and put into \p SpillsToRm at the same1452/// time. \p SpillBBToSpill will be populated as part of the process and1453/// maps a basic block to the first store occurring in the basic block.1454/// \post SpillsToRm.union(Spills\@post) == Spills\@pre1455void HoistSpillHelper::getVisitOrders(1456 MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,1457 SmallVectorImpl<MachineDomTreeNode *> &Orders,1458 SmallVectorImpl<MachineInstr *> &SpillsToRm,1459 DenseMap<MachineDomTreeNode *, Register> &SpillsToKeep,1460 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {1461 // The set contains all the possible BB nodes to which we may hoist1462 // original spills.1463 SmallPtrSet<MachineDomTreeNode *, 8> WorkSet;1464 // Save the BB nodes on the path from the first BB node containing1465 // non-redundant spill to the Root node.1466 SmallPtrSet<MachineDomTreeNode *, 8> NodesOnPath;1467 // All the spills to be hoisted must originate from a single def instruction1468 // to the OrigReg. It means the def instruction should dominate all the spills1469 // to be hoisted. We choose the BB where the def instruction is located as1470 // the Root.1471 MachineDomTreeNode *RootIDomNode = MDT[Root]->getIDom();1472 // For every node on the dominator tree with spill, walk up on the dominator1473 // tree towards the Root node until it is reached. If there is other node1474 // containing spill in the middle of the path, the previous spill saw will1475 // be redundant and the node containing it will be removed. All the nodes on1476 // the path starting from the first node with non-redundant spill to the Root1477 // node will be added to the WorkSet, which will contain all the possible1478 // locations where spills may be hoisted to after the loop below is done.1479 for (auto *const Spill : Spills) {1480 MachineBasicBlock *Block = Spill->getParent();1481 MachineDomTreeNode *Node = MDT[Block];1482 MachineInstr *SpillToRm = nullptr;1483 while (Node != RootIDomNode) {1484 // If Node dominates Block, and it already contains a spill, the spill in1485 // Block will be redundant.1486 if (Node != MDT[Block] && SpillBBToSpill[Node]) {1487 SpillToRm = SpillBBToSpill[MDT[Block]];1488 break;1489 /// If we see the Node already in WorkSet, the path from the Node to1490 /// the Root node must already be traversed by another spill.1491 /// Then no need to repeat.1492 } else if (WorkSet.count(Node)) {1493 break;1494 } else {1495 NodesOnPath.insert(Node);1496 }1497 Node = Node->getIDom();1498 }1499 if (SpillToRm) {1500 SpillsToRm.push_back(SpillToRm);1501 } else {1502 // Add a BB containing the original spills to SpillsToKeep -- i.e.,1503 // set the initial status before hoisting start. The value of BBs1504 // containing original spills is set to 0, in order to descriminate1505 // with BBs containing hoisted spills which will be inserted to1506 // SpillsToKeep later during hoisting.1507 SpillsToKeep[MDT[Block]] = Register();1508 WorkSet.insert_range(NodesOnPath);1509 }1510 NodesOnPath.clear();1511 }1512 1513 // Sort the nodes in WorkSet in top-down order and save the nodes1514 // in Orders. Orders will be used for hoisting in runHoistSpills.1515 unsigned idx = 0;1516 Orders.push_back(MDT.getNode(Root));1517 do {1518 MachineDomTreeNode *Node = Orders[idx++];1519 for (MachineDomTreeNode *Child : Node->children()) {1520 if (WorkSet.count(Child))1521 Orders.push_back(Child);1522 }1523 } while (idx != Orders.size());1524 assert(Orders.size() == WorkSet.size() &&1525 "Orders have different size with WorkSet");1526 1527#ifndef NDEBUG1528 LLVM_DEBUG(dbgs() << "Orders size is " << Orders.size() << "\n");1529 SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();1530 for (; RIt != Orders.rend(); RIt++)1531 LLVM_DEBUG(dbgs() << "BB" << (*RIt)->getBlock()->getNumber() << ",");1532 LLVM_DEBUG(dbgs() << "\n");1533#endif1534}1535 1536/// Try to hoist spills according to BB hotness. The spills to removed will1537/// be saved in \p SpillsToRm. The spills to be inserted will be saved in1538/// \p SpillsToIns.1539void HoistSpillHelper::runHoistSpills(1540 LiveInterval &OrigLI, VNInfo &OrigVNI,1541 SmallPtrSet<MachineInstr *, 16> &Spills,1542 SmallVectorImpl<MachineInstr *> &SpillsToRm,1543 DenseMap<MachineBasicBlock *, Register> &SpillsToIns) {1544 // Visit order of dominator tree nodes.1545 SmallVector<MachineDomTreeNode *, 32> Orders;1546 // SpillsToKeep contains all the nodes where spills are to be inserted1547 // during hoisting. If the spill to be inserted is an original spill1548 // (not a hoisted one), the value of the map entry is 0. If the spill1549 // is a hoisted spill, the value of the map entry is the VReg to be used1550 // as the source of the spill.1551 DenseMap<MachineDomTreeNode *, Register> SpillsToKeep;1552 // Map from BB to the first spill inside of it.1553 DenseMap<MachineDomTreeNode *, MachineInstr *> SpillBBToSpill;1554 1555 rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill);1556 1557 MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI.def);1558 getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep,1559 SpillBBToSpill);1560 1561 // SpillsInSubTreeMap keeps the map from a dom tree node to a pair of1562 // nodes set and the cost of all the spills inside those nodes.1563 // The nodes set are the locations where spills are to be inserted1564 // in the subtree of current node.1565 using NodesCostPair =1566 std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency>;1567 DenseMap<MachineDomTreeNode *, NodesCostPair> SpillsInSubTreeMap;1568 1569 // Iterate Orders set in reverse order, which will be a bottom-up order1570 // in the dominator tree. Once we visit a dom tree node, we know its1571 // children have already been visited and the spill locations in the1572 // subtrees of all the children have been determined.1573 SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();1574 for (; RIt != Orders.rend(); RIt++) {1575 MachineBasicBlock *Block = (*RIt)->getBlock();1576 1577 // If Block contains an original spill, simply continue.1578 if (auto It = SpillsToKeep.find(*RIt);1579 It != SpillsToKeep.end() && !It->second) {1580 auto &SIt = SpillsInSubTreeMap[*RIt];1581 SIt.first.insert(*RIt);1582 // Sit.second contains the cost of spill.1583 SIt.second = MBFI.getBlockFreq(Block);1584 continue;1585 }1586 1587 // Collect spills in subtree of current node (*RIt) to1588 // SpillsInSubTreeMap[*RIt].first.1589 for (MachineDomTreeNode *Child : (*RIt)->children()) {1590 if (!SpillsInSubTreeMap.contains(Child))1591 continue;1592 // The stmt:1593 // "auto &[SpillsInSubTree, SubTreeCost] = SpillsInSubTreeMap[*RIt]"1594 // below should be placed before getting the begin and end iterators of1595 // SpillsInSubTreeMap[Child].first, or else the iterators may be1596 // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time1597 // and the map grows and then the original buckets in the map are moved.1598 auto &[SpillsInSubTree, SubTreeCost] = SpillsInSubTreeMap[*RIt];1599 auto ChildIt = SpillsInSubTreeMap.find(Child);1600 SubTreeCost += ChildIt->second.second;1601 auto BI = ChildIt->second.first.begin();1602 auto EI = ChildIt->second.first.end();1603 SpillsInSubTree.insert(BI, EI);1604 SpillsInSubTreeMap.erase(ChildIt);1605 }1606 1607 auto &[SpillsInSubTree, SubTreeCost] = SpillsInSubTreeMap[*RIt];1608 // No spills in subtree, simply continue.1609 if (SpillsInSubTree.empty())1610 continue;1611 1612 // Check whether Block is a possible candidate to insert spill.1613 Register LiveReg;1614 if (!isSpillCandBB(OrigLI, OrigVNI, *Block, LiveReg))1615 continue;1616 1617 // If there are multiple spills that could be merged, bias a little1618 // to hoist the spill.1619 BranchProbability MarginProb = (SpillsInSubTree.size() > 1)1620 ? BranchProbability(9, 10)1621 : BranchProbability(1, 1);1622 if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) {1623 // Hoist: Move spills to current Block.1624 for (auto *const SpillBB : SpillsInSubTree) {1625 // When SpillBB is a BB contains original spill, insert the spill1626 // to SpillsToRm.1627 if (auto It = SpillsToKeep.find(SpillBB);1628 It != SpillsToKeep.end() && !It->second) {1629 MachineInstr *SpillToRm = SpillBBToSpill[SpillBB];1630 SpillsToRm.push_back(SpillToRm);1631 }1632 // SpillBB will not contain spill anymore, remove it from SpillsToKeep.1633 SpillsToKeep.erase(SpillBB);1634 }1635 // Current Block is the BB containing the new hoisted spill. Add it to1636 // SpillsToKeep. LiveReg is the source of the new spill.1637 SpillsToKeep[*RIt] = LiveReg;1638 LLVM_DEBUG({1639 dbgs() << "spills in BB: ";1640 for (const auto Rspill : SpillsInSubTree)1641 dbgs() << Rspill->getBlock()->getNumber() << " ";1642 dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber()1643 << "\n";1644 });1645 SpillsInSubTree.clear();1646 SpillsInSubTree.insert(*RIt);1647 SubTreeCost = MBFI.getBlockFreq(Block);1648 }1649 }1650 // For spills in SpillsToKeep with LiveReg set (i.e., not original spill),1651 // save them to SpillsToIns.1652 for (const auto &Ent : SpillsToKeep) {1653 if (Ent.second)1654 SpillsToIns[Ent.first->getBlock()] = Ent.second;1655 }1656}1657 1658/// For spills with equal values, remove redundant spills and hoist those left1659/// to less hot spots.1660///1661/// Spills with equal values will be collected into the same set in1662/// MergeableSpills when spill is inserted. These equal spills are originated1663/// from the same defining instruction and are dominated by the instruction.1664/// Before hoisting all the equal spills, redundant spills inside in the same1665/// BB are first marked to be deleted. Then starting from the spills left, walk1666/// up on the dominator tree towards the Root node where the define instruction1667/// is located, mark the dominated spills to be deleted along the way and1668/// collect the BB nodes on the path from non-dominated spills to the define1669/// instruction into a WorkSet. The nodes in WorkSet are the candidate places1670/// where we are considering to hoist the spills. We iterate the WorkSet in1671/// bottom-up order, and for each node, we will decide whether to hoist spills1672/// inside its subtree to that node. In this way, we can get benefit locally1673/// even if hoisting all the equal spills to one cold place is impossible.1674void HoistSpillHelper::hoistAllSpills() {1675 SmallVector<Register, 4> NewVRegs;1676 LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this);1677 1678 for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {1679 Register Reg = Register::index2VirtReg(i);1680 Register Original = VRM.getPreSplitReg(Reg);1681 if (!MRI.def_empty(Reg) && Original.isValid())1682 Virt2SiblingsMap[Original].insert(Reg);1683 }1684 1685 // Each entry in MergeableSpills contains a spill set with equal values.1686 for (auto &Ent : MergeableSpills) {1687 int Slot = Ent.first.first;1688 LiveInterval &OrigLI = *StackSlotToOrigLI[Slot];1689 VNInfo *OrigVNI = Ent.first.second;1690 SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;1691 if (Ent.second.empty())1692 continue;1693 1694 LLVM_DEBUG({1695 dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n"1696 << "Equal spills in BB: ";1697 for (const auto spill : EqValSpills)1698 dbgs() << spill->getParent()->getNumber() << " ";1699 dbgs() << "\n";1700 });1701 1702 // SpillsToRm is the spill set to be removed from EqValSpills.1703 SmallVector<MachineInstr *, 16> SpillsToRm;1704 // SpillsToIns is the spill set to be newly inserted after hoisting.1705 DenseMap<MachineBasicBlock *, Register> SpillsToIns;1706 1707 runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);1708 1709 LLVM_DEBUG({1710 dbgs() << "Finally inserted spills in BB: ";1711 for (const auto &Ispill : SpillsToIns)1712 dbgs() << Ispill.first->getNumber() << " ";1713 dbgs() << "\nFinally removed spills in BB: ";1714 for (const auto Rspill : SpillsToRm)1715 dbgs() << Rspill->getParent()->getNumber() << " ";1716 dbgs() << "\n";1717 });1718 1719 // Stack live range update.1720 LiveInterval &StackIntvl = LSS.getInterval(Slot);1721 if (!SpillsToIns.empty() || !SpillsToRm.empty())1722 StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI,1723 StackIntvl.getValNumInfo(0));1724 1725 // Insert hoisted spills.1726 for (auto const &Insert : SpillsToIns) {1727 MachineBasicBlock *BB = Insert.first;1728 Register LiveReg = Insert.second;1729 MachineBasicBlock::iterator MII = IPA.getLastInsertPointIter(OrigLI, *BB);1730 MachineInstrSpan MIS(MII, BB);1731 TII.storeRegToStackSlot(*BB, MII, LiveReg, false, Slot,1732 MRI.getRegClass(LiveReg), Register());1733 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MII);1734 for (const MachineInstr &MI : make_range(MIS.begin(), MII))1735 getVDefInterval(MI, LIS);1736 ++NumSpills;1737 }1738 1739 // Remove redundant spills or change them to dead instructions.1740 NumSpills -= SpillsToRm.size();1741 for (auto *const RMEnt : SpillsToRm) {1742 RMEnt->setDesc(TII.get(TargetOpcode::KILL));1743 for (unsigned i = RMEnt->getNumOperands(); i; --i) {1744 MachineOperand &MO = RMEnt->getOperand(i - 1);1745 if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead())1746 RMEnt->removeOperand(i - 1);1747 }1748 }1749 Edit.eliminateDeadDefs(SpillsToRm, {});1750 }1751}1752 1753/// For VirtReg clone, the \p New register should have the same physreg or1754/// stackslot as the \p old register.1755void HoistSpillHelper::LRE_DidCloneVirtReg(Register New, Register Old) {1756 if (VRM.hasPhys(Old))1757 VRM.assignVirt2Phys(New, VRM.getPhys(Old));1758 else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT)1759 VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));1760 else1761 llvm_unreachable("VReg should be assigned either physreg or stackslot");1762 if (VRM.hasShape(Old))1763 VRM.assignVirt2Shape(New, VRM.getShape(Old));1764}1765