1 //===-------- InlineSpiller.cpp - Insert spills and restores inline -------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // The inline spiller modifies the machine function directly instead of 11 // inserting spills and restores in VirtRegMap. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "Spiller.h" 16 #include "SplitKit.h" 17 #include "llvm/ADT/MapVector.h" 18 #include "llvm/ADT/SetVector.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/ADT/TinyPtrVector.h" 21 #include "llvm/Analysis/AliasAnalysis.h" 22 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 23 #include "llvm/CodeGen/LiveRangeEdit.h" 24 #include "llvm/CodeGen/LiveStackAnalysis.h" 25 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 26 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 27 #include "llvm/CodeGen/MachineDominators.h" 28 #include "llvm/CodeGen/MachineFrameInfo.h" 29 #include "llvm/CodeGen/MachineFunction.h" 30 #include "llvm/CodeGen/MachineInstrBuilder.h" 31 #include "llvm/CodeGen/MachineInstrBundle.h" 32 #include "llvm/CodeGen/MachineLoopInfo.h" 33 #include "llvm/CodeGen/MachineRegisterInfo.h" 34 #include "llvm/CodeGen/VirtRegMap.h" 35 #include "llvm/IR/DebugInfo.h" 36 #include "llvm/Support/CommandLine.h" 37 #include "llvm/Support/Debug.h" 38 #include "llvm/Support/raw_ostream.h" 39 #include "llvm/Target/TargetInstrInfo.h" 40 41 using namespace llvm; 42 43 #define DEBUG_TYPE "regalloc" 44 45 STATISTIC(NumSpilledRanges, "Number of spilled live ranges"); 46 STATISTIC(NumSnippets, "Number of spilled snippets"); 47 STATISTIC(NumSpills, "Number of spills inserted"); 48 STATISTIC(NumSpillsRemoved, "Number of spills removed"); 49 STATISTIC(NumReloads, "Number of reloads inserted"); 50 STATISTIC(NumReloadsRemoved, "Number of reloads removed"); 51 STATISTIC(NumFolded, "Number of folded stack accesses"); 52 STATISTIC(NumFoldedLoads, "Number of folded loads"); 53 STATISTIC(NumRemats, "Number of rematerialized defs for spilling"); 54 55 static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden, 56 cl::desc("Disable inline spill hoisting")); 57 58 namespace { 59 class HoistSpillHelper : private LiveRangeEdit::Delegate { 60 MachineFunction &MF; 61 LiveIntervals &LIS; 62 LiveStacks &LSS; 63 AliasAnalysis *AA; 64 MachineDominatorTree &MDT; 65 MachineLoopInfo &Loops; 66 VirtRegMap &VRM; 67 MachineFrameInfo &MFI; 68 MachineRegisterInfo &MRI; 69 const TargetInstrInfo &TII; 70 const TargetRegisterInfo &TRI; 71 const MachineBlockFrequencyInfo &MBFI; 72 73 InsertPointAnalysis IPA; 74 75 // Map from StackSlot to its original register. 76 DenseMap<int, unsigned> StackSlotToReg; 77 // Map from pair of (StackSlot and Original VNI) to a set of spills which 78 // have the same stackslot and have equal values defined by Original VNI. 79 // These spills are mergeable and are hoist candiates. 80 typedef MapVector<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>> 81 MergeableSpillsMap; 82 MergeableSpillsMap MergeableSpills; 83 84 /// This is the map from original register to a set containing all its 85 /// siblings. To hoist a spill to another BB, we need to find out a live 86 /// sibling there and use it as the source of the new spill. 87 DenseMap<unsigned, SmallSetVector<unsigned, 16>> Virt2SiblingsMap; 88 89 bool isSpillCandBB(unsigned OrigReg, VNInfo &OrigVNI, MachineBasicBlock &BB, 90 unsigned &LiveReg); 91 92 void rmRedundantSpills( 93 SmallPtrSet<MachineInstr *, 16> &Spills, 94 SmallVectorImpl<MachineInstr *> &SpillsToRm, 95 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill); 96 97 void getVisitOrders( 98 MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills, 99 SmallVectorImpl<MachineDomTreeNode *> &Orders, 100 SmallVectorImpl<MachineInstr *> &SpillsToRm, 101 DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep, 102 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill); 103 104 void runHoistSpills(unsigned OrigReg, VNInfo &OrigVNI, 105 SmallPtrSet<MachineInstr *, 16> &Spills, 106 SmallVectorImpl<MachineInstr *> &SpillsToRm, 107 DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns); 108 109 public: 110 HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf, 111 VirtRegMap &vrm) 112 : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()), 113 LSS(pass.getAnalysis<LiveStacks>()), 114 AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()), 115 MDT(pass.getAnalysis<MachineDominatorTree>()), 116 Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm), 117 MFI(*mf.getFrameInfo()), MRI(mf.getRegInfo()), 118 TII(*mf.getSubtarget().getInstrInfo()), 119 TRI(*mf.getSubtarget().getRegisterInfo()), 120 MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()), 121 IPA(LIS, mf.getNumBlockIDs()) {} 122 123 void addToMergeableSpills(MachineInstr &Spill, int StackSlot, 124 unsigned Original); 125 bool rmFromMergeableSpills(MachineInstr &Spill, int StackSlot); 126 void hoistAllSpills(); 127 void LRE_DidCloneVirtReg(unsigned, unsigned) override; 128 }; 129 130 class InlineSpiller : public Spiller { 131 MachineFunction &MF; 132 LiveIntervals &LIS; 133 LiveStacks &LSS; 134 AliasAnalysis *AA; 135 MachineDominatorTree &MDT; 136 MachineLoopInfo &Loops; 137 VirtRegMap &VRM; 138 MachineFrameInfo &MFI; 139 MachineRegisterInfo &MRI; 140 const TargetInstrInfo &TII; 141 const TargetRegisterInfo &TRI; 142 const MachineBlockFrequencyInfo &MBFI; 143 144 // Variables that are valid during spill(), but used by multiple methods. 145 LiveRangeEdit *Edit; 146 LiveInterval *StackInt; 147 int StackSlot; 148 unsigned Original; 149 150 // All registers to spill to StackSlot, including the main register. 151 SmallVector<unsigned, 8> RegsToSpill; 152 153 // All COPY instructions to/from snippets. 154 // They are ignored since both operands refer to the same stack slot. 155 SmallPtrSet<MachineInstr*, 8> SnippetCopies; 156 157 // Values that failed to remat at some point. 158 SmallPtrSet<VNInfo*, 8> UsedValues; 159 160 // Dead defs generated during spilling. 161 SmallVector<MachineInstr*, 8> DeadDefs; 162 163 // Object records spills information and does the hoisting. 164 HoistSpillHelper HSpiller; 165 166 ~InlineSpiller() override {} 167 168 public: 169 InlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm) 170 : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()), 171 LSS(pass.getAnalysis<LiveStacks>()), 172 AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()), 173 MDT(pass.getAnalysis<MachineDominatorTree>()), 174 Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm), 175 MFI(*mf.getFrameInfo()), MRI(mf.getRegInfo()), 176 TII(*mf.getSubtarget().getInstrInfo()), 177 TRI(*mf.getSubtarget().getRegisterInfo()), 178 MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()), 179 HSpiller(pass, mf, vrm) {} 180 181 void spill(LiveRangeEdit &) override; 182 void postOptimization() override; 183 184 private: 185 bool isSnippet(const LiveInterval &SnipLI); 186 void collectRegsToSpill(); 187 188 bool isRegToSpill(unsigned Reg) { 189 return std::find(RegsToSpill.begin(), 190 RegsToSpill.end(), Reg) != RegsToSpill.end(); 191 } 192 193 bool isSibling(unsigned Reg); 194 bool hoistSpillInsideBB(LiveInterval &SpillLI, MachineInstr &CopyMI); 195 void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI); 196 197 void markValueUsed(LiveInterval*, VNInfo*); 198 bool reMaterializeFor(LiveInterval &, MachineInstr &MI); 199 void reMaterializeAll(); 200 201 bool coalesceStackAccess(MachineInstr *MI, unsigned Reg); 202 bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr*, unsigned> >, 203 MachineInstr *LoadMI = nullptr); 204 void insertReload(unsigned VReg, SlotIndex, MachineBasicBlock::iterator MI); 205 void insertSpill(unsigned VReg, bool isKill, MachineBasicBlock::iterator MI); 206 207 void spillAroundUses(unsigned Reg); 208 void spillAll(); 209 }; 210 } 211 212 namespace llvm { 213 214 Spiller::~Spiller() { } 215 void Spiller::anchor() { } 216 217 Spiller *createInlineSpiller(MachineFunctionPass &pass, 218 MachineFunction &mf, 219 VirtRegMap &vrm) { 220 return new InlineSpiller(pass, mf, vrm); 221 } 222 223 } 224 225 //===----------------------------------------------------------------------===// 226 // Snippets 227 //===----------------------------------------------------------------------===// 228 229 // When spilling a virtual register, we also spill any snippets it is connected 230 // to. The snippets are small live ranges that only have a single real use, 231 // leftovers from live range splitting. Spilling them enables memory operand 232 // folding or tightens the live range around the single use. 233 // 234 // This minimizes register pressure and maximizes the store-to-load distance for 235 // spill slots which can be important in tight loops. 236 237 /// isFullCopyOf - If MI is a COPY to or from Reg, return the other register, 238 /// otherwise return 0. 239 static unsigned isFullCopyOf(const MachineInstr &MI, unsigned Reg) { 240 if (!MI.isFullCopy()) 241 return 0; 242 if (MI.getOperand(0).getReg() == Reg) 243 return MI.getOperand(1).getReg(); 244 if (MI.getOperand(1).getReg() == Reg) 245 return MI.getOperand(0).getReg(); 246 return 0; 247 } 248 249 /// isSnippet - Identify if a live interval is a snippet that should be spilled. 250 /// It is assumed that SnipLI is a virtual register with the same original as 251 /// Edit->getReg(). 252 bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) { 253 unsigned Reg = Edit->getReg(); 254 255 // A snippet is a tiny live range with only a single instruction using it 256 // besides copies to/from Reg or spills/fills. We accept: 257 // 258 // %snip = COPY %Reg / FILL fi# 259 // %snip = USE %snip 260 // %Reg = COPY %snip / SPILL %snip, fi# 261 // 262 if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI)) 263 return false; 264 265 MachineInstr *UseMI = nullptr; 266 267 // Check that all uses satisfy our criteria. 268 for (MachineRegisterInfo::reg_instr_nodbg_iterator 269 RI = MRI.reg_instr_nodbg_begin(SnipLI.reg), 270 E = MRI.reg_instr_nodbg_end(); RI != E; ) { 271 MachineInstr &MI = *RI++; 272 273 // Allow copies to/from Reg. 274 if (isFullCopyOf(MI, Reg)) 275 continue; 276 277 // Allow stack slot loads. 278 int FI; 279 if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) 280 continue; 281 282 // Allow stack slot stores. 283 if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) 284 continue; 285 286 // Allow a single additional instruction. 287 if (UseMI && &MI != UseMI) 288 return false; 289 UseMI = &MI; 290 } 291 return true; 292 } 293 294 /// collectRegsToSpill - Collect live range snippets that only have a single 295 /// real use. 296 void InlineSpiller::collectRegsToSpill() { 297 unsigned Reg = Edit->getReg(); 298 299 // Main register always spills. 300 RegsToSpill.assign(1, Reg); 301 SnippetCopies.clear(); 302 303 // Snippets all have the same original, so there can't be any for an original 304 // register. 305 if (Original == Reg) 306 return; 307 308 for (MachineRegisterInfo::reg_instr_iterator 309 RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); RI != E; ) { 310 MachineInstr &MI = *RI++; 311 unsigned SnipReg = isFullCopyOf(MI, Reg); 312 if (!isSibling(SnipReg)) 313 continue; 314 LiveInterval &SnipLI = LIS.getInterval(SnipReg); 315 if (!isSnippet(SnipLI)) 316 continue; 317 SnippetCopies.insert(&MI); 318 if (isRegToSpill(SnipReg)) 319 continue; 320 RegsToSpill.push_back(SnipReg); 321 DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n'); 322 ++NumSnippets; 323 } 324 } 325 326 bool InlineSpiller::isSibling(unsigned Reg) { 327 return TargetRegisterInfo::isVirtualRegister(Reg) && 328 VRM.getOriginal(Reg) == Original; 329 } 330 331 /// It is beneficial to spill to earlier place in the same BB in case 332 /// as follows: 333 /// There is an alternative def earlier in the same MBB. 334 /// Hoist the spill as far as possible in SpillMBB. This can ease 335 /// register pressure: 336 /// 337 /// x = def 338 /// y = use x 339 /// s = copy x 340 /// 341 /// Hoisting the spill of s to immediately after the def removes the 342 /// interference between x and y: 343 /// 344 /// x = def 345 /// spill x 346 /// y = use x<kill> 347 /// 348 /// This hoist only helps when the copy kills its source. 349 /// 350 bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI, 351 MachineInstr &CopyMI) { 352 SlotIndex Idx = LIS.getInstructionIndex(CopyMI); 353 #ifndef NDEBUG 354 VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot()); 355 assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy"); 356 #endif 357 358 unsigned SrcReg = CopyMI.getOperand(1).getReg(); 359 LiveInterval &SrcLI = LIS.getInterval(SrcReg); 360 VNInfo *SrcVNI = SrcLI.getVNInfoAt(Idx); 361 LiveQueryResult SrcQ = SrcLI.Query(Idx); 362 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(SrcVNI->def); 363 if (DefMBB != CopyMI.getParent() || !SrcQ.isKill()) 364 return false; 365 366 // Conservatively extend the stack slot range to the range of the original 367 // value. We may be able to do better with stack slot coloring by being more 368 // careful here. 369 assert(StackInt && "No stack slot assigned yet."); 370 LiveInterval &OrigLI = LIS.getInterval(Original); 371 VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx); 372 StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0)); 373 DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": " 374 << *StackInt << '\n'); 375 376 // We are going to spill SrcVNI immediately after its def, so clear out 377 // any later spills of the same value. 378 eliminateRedundantSpills(SrcLI, SrcVNI); 379 380 MachineBasicBlock *MBB = LIS.getMBBFromIndex(SrcVNI->def); 381 MachineBasicBlock::iterator MII; 382 if (SrcVNI->isPHIDef()) 383 MII = MBB->SkipPHIsAndLabels(MBB->begin()); 384 else { 385 MachineInstr *DefMI = LIS.getInstructionFromIndex(SrcVNI->def); 386 assert(DefMI && "Defining instruction disappeared"); 387 MII = DefMI; 388 ++MII; 389 } 390 // Insert spill without kill flag immediately after def. 391 TII.storeRegToStackSlot(*MBB, MII, SrcReg, false, StackSlot, 392 MRI.getRegClass(SrcReg), &TRI); 393 --MII; // Point to store instruction. 394 LIS.InsertMachineInstrInMaps(*MII); 395 DEBUG(dbgs() << "\thoisted: " << SrcVNI->def << '\t' << *MII); 396 397 HSpiller.addToMergeableSpills(*MII, StackSlot, Original); 398 ++NumSpills; 399 return true; 400 } 401 402 /// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any 403 /// redundant spills of this value in SLI.reg and sibling copies. 404 void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) { 405 assert(VNI && "Missing value"); 406 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList; 407 WorkList.push_back(std::make_pair(&SLI, VNI)); 408 assert(StackInt && "No stack slot assigned yet."); 409 410 do { 411 LiveInterval *LI; 412 std::tie(LI, VNI) = WorkList.pop_back_val(); 413 unsigned Reg = LI->reg; 414 DEBUG(dbgs() << "Checking redundant spills for " 415 << VNI->id << '@' << VNI->def << " in " << *LI << '\n'); 416 417 // Regs to spill are taken care of. 418 if (isRegToSpill(Reg)) 419 continue; 420 421 // Add all of VNI's live range to StackInt. 422 StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0)); 423 DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n'); 424 425 // Find all spills and copies of VNI. 426 for (MachineRegisterInfo::use_instr_nodbg_iterator 427 UI = MRI.use_instr_nodbg_begin(Reg), E = MRI.use_instr_nodbg_end(); 428 UI != E; ) { 429 MachineInstr &MI = *UI++; 430 if (!MI.isCopy() && !MI.mayStore()) 431 continue; 432 SlotIndex Idx = LIS.getInstructionIndex(MI); 433 if (LI->getVNInfoAt(Idx) != VNI) 434 continue; 435 436 // Follow sibling copies down the dominator tree. 437 if (unsigned DstReg = isFullCopyOf(MI, Reg)) { 438 if (isSibling(DstReg)) { 439 LiveInterval &DstLI = LIS.getInterval(DstReg); 440 VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot()); 441 assert(DstVNI && "Missing defined value"); 442 assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot"); 443 WorkList.push_back(std::make_pair(&DstLI, DstVNI)); 444 } 445 continue; 446 } 447 448 // Erase spills. 449 int FI; 450 if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) { 451 DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << MI); 452 // eliminateDeadDefs won't normally remove stores, so switch opcode. 453 MI.setDesc(TII.get(TargetOpcode::KILL)); 454 DeadDefs.push_back(&MI); 455 ++NumSpillsRemoved; 456 if (HSpiller.rmFromMergeableSpills(MI, StackSlot)) 457 --NumSpills; 458 } 459 } 460 } while (!WorkList.empty()); 461 } 462 463 464 //===----------------------------------------------------------------------===// 465 // Rematerialization 466 //===----------------------------------------------------------------------===// 467 468 /// markValueUsed - Remember that VNI failed to rematerialize, so its defining 469 /// instruction cannot be eliminated. See through snippet copies 470 void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) { 471 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList; 472 WorkList.push_back(std::make_pair(LI, VNI)); 473 do { 474 std::tie(LI, VNI) = WorkList.pop_back_val(); 475 if (!UsedValues.insert(VNI).second) 476 continue; 477 478 if (VNI->isPHIDef()) { 479 MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 480 for (MachineBasicBlock *P : MBB->predecessors()) { 481 VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(P)); 482 if (PVNI) 483 WorkList.push_back(std::make_pair(LI, PVNI)); 484 } 485 continue; 486 } 487 488 // Follow snippet copies. 489 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 490 if (!SnippetCopies.count(MI)) 491 continue; 492 LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg()); 493 assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy"); 494 VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true)); 495 assert(SnipVNI && "Snippet undefined before copy"); 496 WorkList.push_back(std::make_pair(&SnipLI, SnipVNI)); 497 } while (!WorkList.empty()); 498 } 499 500 /// reMaterializeFor - Attempt to rematerialize before MI instead of reloading. 501 bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) { 502 503 // Analyze instruction 504 SmallVector<std::pair<MachineInstr *, unsigned>, 8> Ops; 505 MIBundleOperands::VirtRegInfo RI = 506 MIBundleOperands(MI).analyzeVirtReg(VirtReg.reg, &Ops); 507 508 if (!RI.Reads) 509 return false; 510 511 SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true); 512 VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex()); 513 514 if (!ParentVNI) { 515 DEBUG(dbgs() << "\tadding <undef> flags: "); 516 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 517 MachineOperand &MO = MI.getOperand(i); 518 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) 519 MO.setIsUndef(); 520 } 521 DEBUG(dbgs() << UseIdx << '\t' << MI); 522 return true; 523 } 524 525 if (SnippetCopies.count(&MI)) 526 return false; 527 528 LiveInterval &OrigLI = LIS.getInterval(Original); 529 VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx); 530 LiveRangeEdit::Remat RM(ParentVNI); 531 RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def); 532 533 if (!Edit->canRematerializeAt(RM, OrigVNI, UseIdx, false)) { 534 markValueUsed(&VirtReg, ParentVNI); 535 DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI); 536 return false; 537 } 538 539 // If the instruction also writes VirtReg.reg, it had better not require the 540 // same register for uses and defs. 541 if (RI.Tied) { 542 markValueUsed(&VirtReg, ParentVNI); 543 DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << MI); 544 return false; 545 } 546 547 // Before rematerializing into a register for a single instruction, try to 548 // fold a load into the instruction. That avoids allocating a new register. 549 if (RM.OrigMI->canFoldAsLoad() && 550 foldMemoryOperand(Ops, RM.OrigMI)) { 551 Edit->markRematerialized(RM.ParentVNI); 552 ++NumFoldedLoads; 553 return true; 554 } 555 556 // Alocate a new register for the remat. 557 unsigned NewVReg = Edit->createFrom(Original); 558 559 // Finally we can rematerialize OrigMI before MI. 560 SlotIndex DefIdx = 561 Edit->rematerializeAt(*MI.getParent(), MI, NewVReg, RM, TRI); 562 (void)DefIdx; 563 DEBUG(dbgs() << "\tremat: " << DefIdx << '\t' 564 << *LIS.getInstructionFromIndex(DefIdx)); 565 566 // Replace operands 567 for (const auto &OpPair : Ops) { 568 MachineOperand &MO = OpPair.first->getOperand(OpPair.second); 569 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) { 570 MO.setReg(NewVReg); 571 MO.setIsKill(); 572 } 573 } 574 DEBUG(dbgs() << "\t " << UseIdx << '\t' << MI << '\n'); 575 576 ++NumRemats; 577 return true; 578 } 579 580 /// reMaterializeAll - Try to rematerialize as many uses as possible, 581 /// and trim the live ranges after. 582 void InlineSpiller::reMaterializeAll() { 583 if (!Edit->anyRematerializable(AA)) 584 return; 585 586 UsedValues.clear(); 587 588 // Try to remat before all uses of snippets. 589 bool anyRemat = false; 590 for (unsigned Reg : RegsToSpill) { 591 LiveInterval &LI = LIS.getInterval(Reg); 592 for (MachineRegisterInfo::reg_bundle_iterator 593 RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end(); 594 RegI != E; ) { 595 MachineInstr &MI = *RegI++; 596 597 // Debug values are not allowed to affect codegen. 598 if (MI.isDebugValue()) 599 continue; 600 601 anyRemat |= reMaterializeFor(LI, MI); 602 } 603 } 604 if (!anyRemat) 605 return; 606 607 // Remove any values that were completely rematted. 608 for (unsigned Reg : RegsToSpill) { 609 LiveInterval &LI = LIS.getInterval(Reg); 610 for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end(); 611 I != E; ++I) { 612 VNInfo *VNI = *I; 613 if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI)) 614 continue; 615 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 616 MI->addRegisterDead(Reg, &TRI); 617 if (!MI->allDefsAreDead()) 618 continue; 619 DEBUG(dbgs() << "All defs dead: " << *MI); 620 DeadDefs.push_back(MI); 621 } 622 } 623 624 // Eliminate dead code after remat. Note that some snippet copies may be 625 // deleted here. 626 if (DeadDefs.empty()) 627 return; 628 DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n"); 629 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA); 630 631 // LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions 632 // after rematerialization. To remove a VNI for a vreg from its LiveInterval, 633 // LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all 634 // removed, PHI VNI are still left in the LiveInterval. 635 // So to get rid of unused reg, we need to check whether it has non-dbg 636 // reference instead of whether it has non-empty interval. 637 unsigned ResultPos = 0; 638 for (unsigned Reg : RegsToSpill) { 639 if (MRI.reg_nodbg_empty(Reg)) { 640 Edit->eraseVirtReg(Reg); 641 continue; 642 } 643 assert((LIS.hasInterval(Reg) && !LIS.getInterval(Reg).empty()) && 644 "Reg with empty interval has reference"); 645 RegsToSpill[ResultPos++] = Reg; 646 } 647 RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end()); 648 DEBUG(dbgs() << RegsToSpill.size() << " registers to spill after remat.\n"); 649 } 650 651 652 //===----------------------------------------------------------------------===// 653 // Spilling 654 //===----------------------------------------------------------------------===// 655 656 /// If MI is a load or store of StackSlot, it can be removed. 657 bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) { 658 int FI = 0; 659 unsigned InstrReg = TII.isLoadFromStackSlot(*MI, FI); 660 bool IsLoad = InstrReg; 661 if (!IsLoad) 662 InstrReg = TII.isStoreToStackSlot(*MI, FI); 663 664 // We have a stack access. Is it the right register and slot? 665 if (InstrReg != Reg || FI != StackSlot) 666 return false; 667 668 if (!IsLoad) 669 HSpiller.rmFromMergeableSpills(*MI, StackSlot); 670 671 DEBUG(dbgs() << "Coalescing stack access: " << *MI); 672 LIS.RemoveMachineInstrFromMaps(*MI); 673 MI->eraseFromParent(); 674 675 if (IsLoad) { 676 ++NumReloadsRemoved; 677 --NumReloads; 678 } else { 679 ++NumSpillsRemoved; 680 --NumSpills; 681 } 682 683 return true; 684 } 685 686 #if !defined(NDEBUG) 687 // Dump the range of instructions from B to E with their slot indexes. 688 static void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B, 689 MachineBasicBlock::iterator E, 690 LiveIntervals const &LIS, 691 const char *const header, 692 unsigned VReg =0) { 693 char NextLine = '\n'; 694 char SlotIndent = '\t'; 695 696 if (std::next(B) == E) { 697 NextLine = ' '; 698 SlotIndent = ' '; 699 } 700 701 dbgs() << '\t' << header << ": " << NextLine; 702 703 for (MachineBasicBlock::iterator I = B; I != E; ++I) { 704 SlotIndex Idx = LIS.getInstructionIndex(*I).getRegSlot(); 705 706 // If a register was passed in and this instruction has it as a 707 // destination that is marked as an early clobber, print the 708 // early-clobber slot index. 709 if (VReg) { 710 MachineOperand *MO = I->findRegisterDefOperand(VReg); 711 if (MO && MO->isEarlyClobber()) 712 Idx = Idx.getRegSlot(true); 713 } 714 715 dbgs() << SlotIndent << Idx << '\t' << *I; 716 } 717 } 718 #endif 719 720 /// foldMemoryOperand - Try folding stack slot references in Ops into their 721 /// instructions. 722 /// 723 /// @param Ops Operand indices from analyzeVirtReg(). 724 /// @param LoadMI Load instruction to use instead of stack slot when non-null. 725 /// @return True on success. 726 bool InlineSpiller:: 727 foldMemoryOperand(ArrayRef<std::pair<MachineInstr*, unsigned> > Ops, 728 MachineInstr *LoadMI) { 729 if (Ops.empty()) 730 return false; 731 // Don't attempt folding in bundles. 732 MachineInstr *MI = Ops.front().first; 733 if (Ops.back().first != MI || MI->isBundled()) 734 return false; 735 736 bool WasCopy = MI->isCopy(); 737 unsigned ImpReg = 0; 738 739 bool SpillSubRegs = (MI->getOpcode() == TargetOpcode::STATEPOINT || 740 MI->getOpcode() == TargetOpcode::PATCHPOINT || 741 MI->getOpcode() == TargetOpcode::STACKMAP); 742 743 // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied 744 // operands. 745 SmallVector<unsigned, 8> FoldOps; 746 for (const auto &OpPair : Ops) { 747 unsigned Idx = OpPair.second; 748 assert(MI == OpPair.first && "Instruction conflict during operand folding"); 749 MachineOperand &MO = MI->getOperand(Idx); 750 if (MO.isImplicit()) { 751 ImpReg = MO.getReg(); 752 continue; 753 } 754 // FIXME: Teach targets to deal with subregs. 755 if (!SpillSubRegs && MO.getSubReg()) 756 return false; 757 // We cannot fold a load instruction into a def. 758 if (LoadMI && MO.isDef()) 759 return false; 760 // Tied use operands should not be passed to foldMemoryOperand. 761 if (!MI->isRegTiedToDefOperand(Idx)) 762 FoldOps.push_back(Idx); 763 } 764 765 MachineInstrSpan MIS(MI); 766 767 MachineInstr *FoldMI = 768 LoadMI ? TII.foldMemoryOperand(*MI, FoldOps, *LoadMI, &LIS) 769 : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS); 770 if (!FoldMI) 771 return false; 772 773 // Remove LIS for any dead defs in the original MI not in FoldMI. 774 for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) { 775 if (!MO->isReg()) 776 continue; 777 unsigned Reg = MO->getReg(); 778 if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || 779 MRI.isReserved(Reg)) { 780 continue; 781 } 782 // Skip non-Defs, including undef uses and internal reads. 783 if (MO->isUse()) 784 continue; 785 MIBundleOperands::PhysRegInfo RI = 786 MIBundleOperands(*FoldMI).analyzePhysReg(Reg, &TRI); 787 if (RI.FullyDefined) 788 continue; 789 // FoldMI does not define this physreg. Remove the LI segment. 790 assert(MO->isDead() && "Cannot fold physreg def"); 791 SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot(); 792 LIS.removePhysRegDefAt(Reg, Idx); 793 } 794 795 int FI; 796 if (TII.isStoreToStackSlot(*MI, FI) && 797 HSpiller.rmFromMergeableSpills(*MI, FI)) 798 --NumSpills; 799 LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI); 800 MI->eraseFromParent(); 801 802 // Insert any new instructions other than FoldMI into the LIS maps. 803 assert(!MIS.empty() && "Unexpected empty span of instructions!"); 804 for (MachineInstr &MI : MIS) 805 if (&MI != FoldMI) 806 LIS.InsertMachineInstrInMaps(MI); 807 808 // TII.foldMemoryOperand may have left some implicit operands on the 809 // instruction. Strip them. 810 if (ImpReg) 811 for (unsigned i = FoldMI->getNumOperands(); i; --i) { 812 MachineOperand &MO = FoldMI->getOperand(i - 1); 813 if (!MO.isReg() || !MO.isImplicit()) 814 break; 815 if (MO.getReg() == ImpReg) 816 FoldMI->RemoveOperand(i - 1); 817 } 818 819 DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS, 820 "folded")); 821 822 if (!WasCopy) 823 ++NumFolded; 824 else if (Ops.front().second == 0) { 825 ++NumSpills; 826 HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original); 827 } else 828 ++NumReloads; 829 return true; 830 } 831 832 void InlineSpiller::insertReload(unsigned NewVReg, 833 SlotIndex Idx, 834 MachineBasicBlock::iterator MI) { 835 MachineBasicBlock &MBB = *MI->getParent(); 836 837 MachineInstrSpan MIS(MI); 838 TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot, 839 MRI.getRegClass(NewVReg), &TRI); 840 841 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI); 842 843 DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload", 844 NewVReg)); 845 ++NumReloads; 846 } 847 848 /// insertSpill - Insert a spill of NewVReg after MI. 849 void InlineSpiller::insertSpill(unsigned NewVReg, bool isKill, 850 MachineBasicBlock::iterator MI) { 851 MachineBasicBlock &MBB = *MI->getParent(); 852 853 MachineInstrSpan MIS(MI); 854 TII.storeRegToStackSlot(MBB, std::next(MI), NewVReg, isKill, StackSlot, 855 MRI.getRegClass(NewVReg), &TRI); 856 857 LIS.InsertMachineInstrRangeInMaps(std::next(MI), MIS.end()); 858 859 DEBUG(dumpMachineInstrRangeWithSlotIndex(std::next(MI), MIS.end(), LIS, 860 "spill")); 861 ++NumSpills; 862 HSpiller.addToMergeableSpills(*std::next(MI), StackSlot, Original); 863 } 864 865 /// spillAroundUses - insert spill code around each use of Reg. 866 void InlineSpiller::spillAroundUses(unsigned Reg) { 867 DEBUG(dbgs() << "spillAroundUses " << PrintReg(Reg) << '\n'); 868 LiveInterval &OldLI = LIS.getInterval(Reg); 869 870 // Iterate over instructions using Reg. 871 for (MachineRegisterInfo::reg_bundle_iterator 872 RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end(); 873 RegI != E; ) { 874 MachineInstr *MI = &*(RegI++); 875 876 // Debug values are not allowed to affect codegen. 877 if (MI->isDebugValue()) { 878 // Modify DBG_VALUE now that the value is in a spill slot. 879 bool IsIndirect = MI->isIndirectDebugValue(); 880 uint64_t Offset = IsIndirect ? MI->getOperand(1).getImm() : 0; 881 const MDNode *Var = MI->getDebugVariable(); 882 const MDNode *Expr = MI->getDebugExpression(); 883 DebugLoc DL = MI->getDebugLoc(); 884 DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); 885 MachineBasicBlock *MBB = MI->getParent(); 886 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) && 887 "Expected inlined-at fields to agree"); 888 BuildMI(*MBB, MBB->erase(MI), DL, TII.get(TargetOpcode::DBG_VALUE)) 889 .addFrameIndex(StackSlot) 890 .addImm(Offset) 891 .addMetadata(Var) 892 .addMetadata(Expr); 893 continue; 894 } 895 896 // Ignore copies to/from snippets. We'll delete them. 897 if (SnippetCopies.count(MI)) 898 continue; 899 900 // Stack slot accesses may coalesce away. 901 if (coalesceStackAccess(MI, Reg)) 902 continue; 903 904 // Analyze instruction. 905 SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops; 906 MIBundleOperands::VirtRegInfo RI = 907 MIBundleOperands(*MI).analyzeVirtReg(Reg, &Ops); 908 909 // Find the slot index where this instruction reads and writes OldLI. 910 // This is usually the def slot, except for tied early clobbers. 911 SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot(); 912 if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true))) 913 if (SlotIndex::isSameInstr(Idx, VNI->def)) 914 Idx = VNI->def; 915 916 // Check for a sibling copy. 917 unsigned SibReg = isFullCopyOf(*MI, Reg); 918 if (SibReg && isSibling(SibReg)) { 919 // This may actually be a copy between snippets. 920 if (isRegToSpill(SibReg)) { 921 DEBUG(dbgs() << "Found new snippet copy: " << *MI); 922 SnippetCopies.insert(MI); 923 continue; 924 } 925 if (RI.Writes) { 926 if (hoistSpillInsideBB(OldLI, *MI)) { 927 // This COPY is now dead, the value is already in the stack slot. 928 MI->getOperand(0).setIsDead(); 929 DeadDefs.push_back(MI); 930 continue; 931 } 932 } else { 933 // This is a reload for a sib-reg copy. Drop spills downstream. 934 LiveInterval &SibLI = LIS.getInterval(SibReg); 935 eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx)); 936 // The COPY will fold to a reload below. 937 } 938 } 939 940 // Attempt to fold memory ops. 941 if (foldMemoryOperand(Ops)) 942 continue; 943 944 // Create a new virtual register for spill/fill. 945 // FIXME: Infer regclass from instruction alone. 946 unsigned NewVReg = Edit->createFrom(Reg); 947 948 if (RI.Reads) 949 insertReload(NewVReg, Idx, MI); 950 951 // Rewrite instruction operands. 952 bool hasLiveDef = false; 953 for (const auto &OpPair : Ops) { 954 MachineOperand &MO = OpPair.first->getOperand(OpPair.second); 955 MO.setReg(NewVReg); 956 if (MO.isUse()) { 957 if (!OpPair.first->isRegTiedToDefOperand(OpPair.second)) 958 MO.setIsKill(); 959 } else { 960 if (!MO.isDead()) 961 hasLiveDef = true; 962 } 963 } 964 DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI << '\n'); 965 966 // FIXME: Use a second vreg if instruction has no tied ops. 967 if (RI.Writes) 968 if (hasLiveDef) 969 insertSpill(NewVReg, true, MI); 970 } 971 } 972 973 /// spillAll - Spill all registers remaining after rematerialization. 974 void InlineSpiller::spillAll() { 975 // Update LiveStacks now that we are committed to spilling. 976 if (StackSlot == VirtRegMap::NO_STACK_SLOT) { 977 StackSlot = VRM.assignVirt2StackSlot(Original); 978 StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original)); 979 StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator()); 980 } else 981 StackInt = &LSS.getInterval(StackSlot); 982 983 if (Original != Edit->getReg()) 984 VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot); 985 986 assert(StackInt->getNumValNums() == 1 && "Bad stack interval values"); 987 for (unsigned Reg : RegsToSpill) 988 StackInt->MergeSegmentsInAsValue(LIS.getInterval(Reg), 989 StackInt->getValNumInfo(0)); 990 DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n'); 991 992 // Spill around uses of all RegsToSpill. 993 for (unsigned Reg : RegsToSpill) 994 spillAroundUses(Reg); 995 996 // Hoisted spills may cause dead code. 997 if (!DeadDefs.empty()) { 998 DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n"); 999 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA); 1000 } 1001 1002 // Finally delete the SnippetCopies. 1003 for (unsigned Reg : RegsToSpill) { 1004 for (MachineRegisterInfo::reg_instr_iterator 1005 RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); 1006 RI != E; ) { 1007 MachineInstr &MI = *(RI++); 1008 assert(SnippetCopies.count(&MI) && "Remaining use wasn't a snippet copy"); 1009 // FIXME: Do this with a LiveRangeEdit callback. 1010 LIS.RemoveMachineInstrFromMaps(MI); 1011 MI.eraseFromParent(); 1012 } 1013 } 1014 1015 // Delete all spilled registers. 1016 for (unsigned Reg : RegsToSpill) 1017 Edit->eraseVirtReg(Reg); 1018 } 1019 1020 void InlineSpiller::spill(LiveRangeEdit &edit) { 1021 ++NumSpilledRanges; 1022 Edit = &edit; 1023 assert(!TargetRegisterInfo::isStackSlot(edit.getReg()) 1024 && "Trying to spill a stack slot."); 1025 // Share a stack slot among all descendants of Original. 1026 Original = VRM.getOriginal(edit.getReg()); 1027 StackSlot = VRM.getStackSlot(Original); 1028 StackInt = nullptr; 1029 1030 DEBUG(dbgs() << "Inline spilling " 1031 << TRI.getRegClassName(MRI.getRegClass(edit.getReg())) 1032 << ':' << edit.getParent() 1033 << "\nFrom original " << PrintReg(Original) << '\n'); 1034 assert(edit.getParent().isSpillable() && 1035 "Attempting to spill already spilled value."); 1036 assert(DeadDefs.empty() && "Previous spill didn't remove dead defs"); 1037 1038 collectRegsToSpill(); 1039 reMaterializeAll(); 1040 1041 // Remat may handle everything. 1042 if (!RegsToSpill.empty()) 1043 spillAll(); 1044 1045 Edit->calculateRegClassAndHint(MF, Loops, MBFI); 1046 } 1047 1048 /// Optimizations after all the reg selections and spills are done. 1049 /// 1050 void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); } 1051 1052 /// When a spill is inserted, add the spill to MergeableSpills map. 1053 /// 1054 void HoistSpillHelper::addToMergeableSpills(MachineInstr &Spill, int StackSlot, 1055 unsigned Original) { 1056 StackSlotToReg[StackSlot] = Original; 1057 SlotIndex Idx = LIS.getInstructionIndex(Spill); 1058 VNInfo *OrigVNI = LIS.getInterval(Original).getVNInfoAt(Idx.getRegSlot()); 1059 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI); 1060 MergeableSpills[MIdx].insert(&Spill); 1061 } 1062 1063 /// When a spill is removed, remove the spill from MergeableSpills map. 1064 /// Return true if the spill is removed successfully. 1065 /// 1066 bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr &Spill, 1067 int StackSlot) { 1068 int Original = StackSlotToReg[StackSlot]; 1069 if (!Original) 1070 return false; 1071 SlotIndex Idx = LIS.getInstructionIndex(Spill); 1072 VNInfo *OrigVNI = LIS.getInterval(Original).getVNInfoAt(Idx.getRegSlot()); 1073 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI); 1074 return MergeableSpills[MIdx].erase(&Spill); 1075 } 1076 1077 /// Check BB to see if it is a possible target BB to place a hoisted spill, 1078 /// i.e., there should be a living sibling of OrigReg at the insert point. 1079 /// 1080 bool HoistSpillHelper::isSpillCandBB(unsigned OrigReg, VNInfo &OrigVNI, 1081 MachineBasicBlock &BB, unsigned &LiveReg) { 1082 SlotIndex Idx; 1083 LiveInterval &OrigLI = LIS.getInterval(OrigReg); 1084 MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(OrigLI, BB); 1085 if (MI != BB.end()) 1086 Idx = LIS.getInstructionIndex(*MI); 1087 else 1088 Idx = LIS.getMBBEndIdx(&BB).getPrevSlot(); 1089 SmallSetVector<unsigned, 16> &Siblings = Virt2SiblingsMap[OrigReg]; 1090 assert((LIS.getInterval(OrigReg)).getVNInfoAt(Idx) == &OrigVNI && 1091 "Unexpected VNI"); 1092 1093 for (auto const SibReg : Siblings) { 1094 LiveInterval &LI = LIS.getInterval(SibReg); 1095 VNInfo *VNI = LI.getVNInfoAt(Idx); 1096 if (VNI) { 1097 LiveReg = SibReg; 1098 return true; 1099 } 1100 } 1101 return false; 1102 } 1103 1104 /// Remove redundant spills in the same BB. Save those redundant spills in 1105 /// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map. 1106 /// 1107 void HoistSpillHelper::rmRedundantSpills( 1108 SmallPtrSet<MachineInstr *, 16> &Spills, 1109 SmallVectorImpl<MachineInstr *> &SpillsToRm, 1110 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) { 1111 // For each spill saw, check SpillBBToSpill[] and see if its BB already has 1112 // another spill inside. If a BB contains more than one spill, only keep the 1113 // earlier spill with smaller SlotIndex. 1114 for (const auto CurrentSpill : Spills) { 1115 MachineBasicBlock *Block = CurrentSpill->getParent(); 1116 MachineDomTreeNode *Node = MDT.DT->getNode(Block); 1117 MachineInstr *PrevSpill = SpillBBToSpill[Node]; 1118 if (PrevSpill) { 1119 SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill); 1120 SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill); 1121 MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill; 1122 MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill; 1123 SpillsToRm.push_back(SpillToRm); 1124 SpillBBToSpill[MDT.DT->getNode(Block)] = SpillToKeep; 1125 } else { 1126 SpillBBToSpill[MDT.DT->getNode(Block)] = CurrentSpill; 1127 } 1128 } 1129 for (const auto SpillToRm : SpillsToRm) 1130 Spills.erase(SpillToRm); 1131 } 1132 1133 /// Starting from \p Root find a top-down traversal order of the dominator 1134 /// tree to visit all basic blocks containing the elements of \p Spills. 1135 /// Redundant spills will be found and put into \p SpillsToRm at the same 1136 /// time. \p SpillBBToSpill will be populated as part of the process and 1137 /// maps a basic block to the first store occurring in the basic block. 1138 /// \post SpillsToRm.union(Spills\@post) == Spills\@pre 1139 /// 1140 void HoistSpillHelper::getVisitOrders( 1141 MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills, 1142 SmallVectorImpl<MachineDomTreeNode *> &Orders, 1143 SmallVectorImpl<MachineInstr *> &SpillsToRm, 1144 DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep, 1145 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) { 1146 // The set contains all the possible BB nodes to which we may hoist 1147 // original spills. 1148 SmallPtrSet<MachineDomTreeNode *, 8> WorkSet; 1149 // Save the BB nodes on the path from the first BB node containing 1150 // non-redundant spill to the Root node. 1151 SmallPtrSet<MachineDomTreeNode *, 8> NodesOnPath; 1152 // All the spills to be hoisted must originate from a single def instruction 1153 // to the OrigReg. It means the def instruction should dominate all the spills 1154 // to be hoisted. We choose the BB where the def instruction is located as 1155 // the Root. 1156 MachineDomTreeNode *RootIDomNode = MDT[Root]->getIDom(); 1157 // For every node on the dominator tree with spill, walk up on the dominator 1158 // tree towards the Root node until it is reached. If there is other node 1159 // containing spill in the middle of the path, the previous spill saw will 1160 // be redundant and the node containing it will be removed. All the nodes on 1161 // the path starting from the first node with non-redundant spill to the Root 1162 // node will be added to the WorkSet, which will contain all the possible 1163 // locations where spills may be hoisted to after the loop below is done. 1164 for (const auto Spill : Spills) { 1165 MachineBasicBlock *Block = Spill->getParent(); 1166 MachineDomTreeNode *Node = MDT[Block]; 1167 MachineInstr *SpillToRm = nullptr; 1168 while (Node != RootIDomNode) { 1169 // If Node dominates Block, and it already contains a spill, the spill in 1170 // Block will be redundant. 1171 if (Node != MDT[Block] && SpillBBToSpill[Node]) { 1172 SpillToRm = SpillBBToSpill[MDT[Block]]; 1173 break; 1174 /// If we see the Node already in WorkSet, the path from the Node to 1175 /// the Root node must already be traversed by another spill. 1176 /// Then no need to repeat. 1177 } else if (WorkSet.count(Node)) { 1178 break; 1179 } else { 1180 NodesOnPath.insert(Node); 1181 } 1182 Node = Node->getIDom(); 1183 } 1184 if (SpillToRm) { 1185 SpillsToRm.push_back(SpillToRm); 1186 } else { 1187 // Add a BB containing the original spills to SpillsToKeep -- i.e., 1188 // set the initial status before hoisting start. The value of BBs 1189 // containing original spills is set to 0, in order to descriminate 1190 // with BBs containing hoisted spills which will be inserted to 1191 // SpillsToKeep later during hoisting. 1192 SpillsToKeep[MDT[Block]] = 0; 1193 WorkSet.insert(NodesOnPath.begin(), NodesOnPath.end()); 1194 } 1195 NodesOnPath.clear(); 1196 } 1197 1198 // Sort the nodes in WorkSet in top-down order and save the nodes 1199 // in Orders. Orders will be used for hoisting in runHoistSpills. 1200 unsigned idx = 0; 1201 Orders.push_back(MDT.DT->getNode(Root)); 1202 do { 1203 MachineDomTreeNode *Node = Orders[idx++]; 1204 const std::vector<MachineDomTreeNode *> &Children = Node->getChildren(); 1205 unsigned NumChildren = Children.size(); 1206 for (unsigned i = 0; i != NumChildren; ++i) { 1207 MachineDomTreeNode *Child = Children[i]; 1208 if (WorkSet.count(Child)) 1209 Orders.push_back(Child); 1210 } 1211 } while (idx != Orders.size()); 1212 assert(Orders.size() == WorkSet.size() && 1213 "Orders have different size with WorkSet"); 1214 1215 #ifndef NDEBUG 1216 DEBUG(dbgs() << "Orders size is " << Orders.size() << "\n"); 1217 SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin(); 1218 for (; RIt != Orders.rend(); RIt++) 1219 DEBUG(dbgs() << "BB" << (*RIt)->getBlock()->getNumber() << ","); 1220 DEBUG(dbgs() << "\n"); 1221 #endif 1222 } 1223 1224 /// Try to hoist spills according to BB hotness. The spills to removed will 1225 /// be saved in \p SpillsToRm. The spills to be inserted will be saved in 1226 /// \p SpillsToIns. 1227 /// 1228 void HoistSpillHelper::runHoistSpills( 1229 unsigned OrigReg, VNInfo &OrigVNI, SmallPtrSet<MachineInstr *, 16> &Spills, 1230 SmallVectorImpl<MachineInstr *> &SpillsToRm, 1231 DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns) { 1232 // Visit order of dominator tree nodes. 1233 SmallVector<MachineDomTreeNode *, 32> Orders; 1234 // SpillsToKeep contains all the nodes where spills are to be inserted 1235 // during hoisting. If the spill to be inserted is an original spill 1236 // (not a hoisted one), the value of the map entry is 0. If the spill 1237 // is a hoisted spill, the value of the map entry is the VReg to be used 1238 // as the source of the spill. 1239 DenseMap<MachineDomTreeNode *, unsigned> SpillsToKeep; 1240 // Map from BB to the first spill inside of it. 1241 DenseMap<MachineDomTreeNode *, MachineInstr *> SpillBBToSpill; 1242 1243 rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill); 1244 1245 MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI.def); 1246 getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep, 1247 SpillBBToSpill); 1248 1249 // SpillsInSubTreeMap keeps the map from a dom tree node to a pair of 1250 // nodes set and the cost of all the spills inside those nodes. 1251 // The nodes set are the locations where spills are to be inserted 1252 // in the subtree of current node. 1253 typedef std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency> 1254 NodesCostPair; 1255 DenseMap<MachineDomTreeNode *, NodesCostPair> SpillsInSubTreeMap; 1256 // Iterate Orders set in reverse order, which will be a bottom-up order 1257 // in the dominator tree. Once we visit a dom tree node, we know its 1258 // children have already been visited and the spill locations in the 1259 // subtrees of all the children have been determined. 1260 SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin(); 1261 for (; RIt != Orders.rend(); RIt++) { 1262 MachineBasicBlock *Block = (*RIt)->getBlock(); 1263 1264 // If Block contains an original spill, simply continue. 1265 if (SpillsToKeep.find(*RIt) != SpillsToKeep.end() && !SpillsToKeep[*RIt]) { 1266 SpillsInSubTreeMap[*RIt].first.insert(*RIt); 1267 // SpillsInSubTreeMap[*RIt].second contains the cost of spill. 1268 SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block); 1269 continue; 1270 } 1271 1272 // Collect spills in subtree of current node (*RIt) to 1273 // SpillsInSubTreeMap[*RIt].first. 1274 const std::vector<MachineDomTreeNode *> &Children = (*RIt)->getChildren(); 1275 unsigned NumChildren = Children.size(); 1276 for (unsigned i = 0; i != NumChildren; ++i) { 1277 MachineDomTreeNode *Child = Children[i]; 1278 if (SpillsInSubTreeMap.find(Child) == SpillsInSubTreeMap.end()) 1279 continue; 1280 // The stmt "SpillsInSubTree = SpillsInSubTreeMap[*RIt].first" below 1281 // should be placed before getting the begin and end iterators of 1282 // SpillsInSubTreeMap[Child].first, or else the iterators may be 1283 // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time 1284 // and the map grows and then the original buckets in the map are moved. 1285 SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree = 1286 SpillsInSubTreeMap[*RIt].first; 1287 BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second; 1288 SubTreeCost += SpillsInSubTreeMap[Child].second; 1289 auto BI = SpillsInSubTreeMap[Child].first.begin(); 1290 auto EI = SpillsInSubTreeMap[Child].first.end(); 1291 SpillsInSubTree.insert(BI, EI); 1292 SpillsInSubTreeMap.erase(Child); 1293 } 1294 1295 SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree = 1296 SpillsInSubTreeMap[*RIt].first; 1297 BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second; 1298 // No spills in subtree, simply continue. 1299 if (SpillsInSubTree.empty()) 1300 continue; 1301 1302 // Check whether Block is a possible candidate to insert spill. 1303 unsigned LiveReg = 0; 1304 if (!isSpillCandBB(OrigReg, OrigVNI, *Block, LiveReg)) 1305 continue; 1306 1307 // If there are multiple spills that could be merged, bias a little 1308 // to hoist the spill. 1309 BranchProbability MarginProb = (SpillsInSubTree.size() > 1) 1310 ? BranchProbability(9, 10) 1311 : BranchProbability(1, 1); 1312 if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) { 1313 // Hoist: Move spills to current Block. 1314 for (const auto SpillBB : SpillsInSubTree) { 1315 // When SpillBB is a BB contains original spill, insert the spill 1316 // to SpillsToRm. 1317 if (SpillsToKeep.find(SpillBB) != SpillsToKeep.end() && 1318 !SpillsToKeep[SpillBB]) { 1319 MachineInstr *SpillToRm = SpillBBToSpill[SpillBB]; 1320 SpillsToRm.push_back(SpillToRm); 1321 } 1322 // SpillBB will not contain spill anymore, remove it from SpillsToKeep. 1323 SpillsToKeep.erase(SpillBB); 1324 } 1325 // Current Block is the BB containing the new hoisted spill. Add it to 1326 // SpillsToKeep. LiveReg is the source of the new spill. 1327 SpillsToKeep[*RIt] = LiveReg; 1328 DEBUG({ 1329 dbgs() << "spills in BB: "; 1330 for (const auto Rspill : SpillsInSubTree) 1331 dbgs() << Rspill->getBlock()->getNumber() << " "; 1332 dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber() 1333 << "\n"; 1334 }); 1335 SpillsInSubTree.clear(); 1336 SpillsInSubTree.insert(*RIt); 1337 SubTreeCost = MBFI.getBlockFreq(Block); 1338 } 1339 } 1340 // For spills in SpillsToKeep with LiveReg set (i.e., not original spill), 1341 // save them to SpillsToIns. 1342 for (const auto Ent : SpillsToKeep) { 1343 if (Ent.second) 1344 SpillsToIns[Ent.first->getBlock()] = Ent.second; 1345 } 1346 } 1347 1348 /// For spills with equal values, remove redundant spills and hoist those left 1349 /// to less hot spots. 1350 /// 1351 /// Spills with equal values will be collected into the same set in 1352 /// MergeableSpills when spill is inserted. These equal spills are originated 1353 /// from the same defining instruction and are dominated by the instruction. 1354 /// Before hoisting all the equal spills, redundant spills inside in the same 1355 /// BB are first marked to be deleted. Then starting from the spills left, walk 1356 /// up on the dominator tree towards the Root node where the define instruction 1357 /// is located, mark the dominated spills to be deleted along the way and 1358 /// collect the BB nodes on the path from non-dominated spills to the define 1359 /// instruction into a WorkSet. The nodes in WorkSet are the candidate places 1360 /// where we are considering to hoist the spills. We iterate the WorkSet in 1361 /// bottom-up order, and for each node, we will decide whether to hoist spills 1362 /// inside its subtree to that node. In this way, we can get benefit locally 1363 /// even if hoisting all the equal spills to one cold place is impossible. 1364 /// 1365 void HoistSpillHelper::hoistAllSpills() { 1366 SmallVector<unsigned, 4> NewVRegs; 1367 LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this); 1368 1369 // Save the mapping between stackslot and its original reg. 1370 DenseMap<int, unsigned> SlotToOrigReg; 1371 for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) { 1372 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 1373 int Slot = VRM.getStackSlot(Reg); 1374 if (Slot != VirtRegMap::NO_STACK_SLOT) 1375 SlotToOrigReg[Slot] = VRM.getOriginal(Reg); 1376 unsigned Original = VRM.getPreSplitReg(Reg); 1377 if (!MRI.def_empty(Reg)) 1378 Virt2SiblingsMap[Original].insert(Reg); 1379 } 1380 1381 // Each entry in MergeableSpills contains a spill set with equal values. 1382 for (auto &Ent : MergeableSpills) { 1383 int Slot = Ent.first.first; 1384 unsigned OrigReg = SlotToOrigReg[Slot]; 1385 LiveInterval &OrigLI = LIS.getInterval(OrigReg); 1386 VNInfo *OrigVNI = Ent.first.second; 1387 SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second; 1388 if (Ent.second.empty()) 1389 continue; 1390 1391 DEBUG({ 1392 dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n" 1393 << "Equal spills in BB: "; 1394 for (const auto spill : EqValSpills) 1395 dbgs() << spill->getParent()->getNumber() << " "; 1396 dbgs() << "\n"; 1397 }); 1398 1399 // SpillsToRm is the spill set to be removed from EqValSpills. 1400 SmallVector<MachineInstr *, 16> SpillsToRm; 1401 // SpillsToIns is the spill set to be newly inserted after hoisting. 1402 DenseMap<MachineBasicBlock *, unsigned> SpillsToIns; 1403 1404 runHoistSpills(OrigReg, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns); 1405 1406 DEBUG({ 1407 dbgs() << "Finally inserted spills in BB: "; 1408 for (const auto Ispill : SpillsToIns) 1409 dbgs() << Ispill.first->getNumber() << " "; 1410 dbgs() << "\nFinally removed spills in BB: "; 1411 for (const auto Rspill : SpillsToRm) 1412 dbgs() << Rspill->getParent()->getNumber() << " "; 1413 dbgs() << "\n"; 1414 }); 1415 1416 // Stack live range update. 1417 LiveInterval &StackIntvl = LSS.getInterval(Slot); 1418 if (!SpillsToIns.empty() || !SpillsToRm.empty()) 1419 StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI, 1420 StackIntvl.getValNumInfo(0)); 1421 1422 // Insert hoisted spills. 1423 for (auto const Insert : SpillsToIns) { 1424 MachineBasicBlock *BB = Insert.first; 1425 unsigned LiveReg = Insert.second; 1426 MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(OrigLI, *BB); 1427 TII.storeRegToStackSlot(*BB, MI, LiveReg, false, Slot, 1428 MRI.getRegClass(LiveReg), &TRI); 1429 LIS.InsertMachineInstrRangeInMaps(std::prev(MI), MI); 1430 ++NumSpills; 1431 } 1432 1433 // Remove redundant spills or change them to dead instructions. 1434 NumSpills -= SpillsToRm.size(); 1435 for (auto const RMEnt : SpillsToRm) { 1436 RMEnt->setDesc(TII.get(TargetOpcode::KILL)); 1437 for (unsigned i = RMEnt->getNumOperands(); i; --i) { 1438 MachineOperand &MO = RMEnt->getOperand(i - 1); 1439 if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead()) 1440 RMEnt->RemoveOperand(i - 1); 1441 } 1442 } 1443 Edit.eliminateDeadDefs(SpillsToRm, None, AA); 1444 } 1445 } 1446 1447 /// For VirtReg clone, the \p New register should have the same physreg or 1448 /// stackslot as the \p old register. 1449 void HoistSpillHelper::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 1450 if (VRM.hasPhys(Old)) 1451 VRM.assignVirt2Phys(New, VRM.getPhys(Old)); 1452 else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT) 1453 VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old)); 1454 else 1455 llvm_unreachable("VReg should be assigned either physreg or stackslot"); 1456 } 1457