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 #define DEBUG_TYPE "regalloc" 16 #include "Spiller.h" 17 #include "VirtRegMap.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/ADT/TinyPtrVector.h" 20 #include "llvm/Analysis/AliasAnalysis.h" 21 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 22 #include "llvm/CodeGen/LiveRangeEdit.h" 23 #include "llvm/CodeGen/LiveStackAnalysis.h" 24 #include "llvm/CodeGen/MachineDominators.h" 25 #include "llvm/CodeGen/MachineInstrBundle.h" 26 #include "llvm/CodeGen/MachineFrameInfo.h" 27 #include "llvm/CodeGen/MachineFunction.h" 28 #include "llvm/CodeGen/MachineLoopInfo.h" 29 #include "llvm/CodeGen/MachineRegisterInfo.h" 30 #include "llvm/Target/TargetMachine.h" 31 #include "llvm/Target/TargetInstrInfo.h" 32 #include "llvm/Support/CommandLine.h" 33 #include "llvm/Support/Debug.h" 34 #include "llvm/Support/raw_ostream.h" 35 36 using namespace llvm; 37 38 STATISTIC(NumSpilledRanges, "Number of spilled live ranges"); 39 STATISTIC(NumSnippets, "Number of spilled snippets"); 40 STATISTIC(NumSpills, "Number of spills inserted"); 41 STATISTIC(NumSpillsRemoved, "Number of spills removed"); 42 STATISTIC(NumReloads, "Number of reloads inserted"); 43 STATISTIC(NumReloadsRemoved, "Number of reloads removed"); 44 STATISTIC(NumFolded, "Number of folded stack accesses"); 45 STATISTIC(NumFoldedLoads, "Number of folded loads"); 46 STATISTIC(NumRemats, "Number of rematerialized defs for spilling"); 47 STATISTIC(NumOmitReloadSpill, "Number of omitted spills of reloads"); 48 STATISTIC(NumHoists, "Number of hoisted spills"); 49 50 static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden, 51 cl::desc("Disable inline spill hoisting")); 52 53 namespace { 54 class InlineSpiller : public Spiller { 55 MachineFunction &MF; 56 LiveIntervals &LIS; 57 LiveStacks &LSS; 58 AliasAnalysis *AA; 59 MachineDominatorTree &MDT; 60 MachineLoopInfo &Loops; 61 VirtRegMap &VRM; 62 MachineFrameInfo &MFI; 63 MachineRegisterInfo &MRI; 64 const TargetInstrInfo &TII; 65 const TargetRegisterInfo &TRI; 66 67 // Variables that are valid during spill(), but used by multiple methods. 68 LiveRangeEdit *Edit; 69 LiveInterval *StackInt; 70 int StackSlot; 71 unsigned Original; 72 73 // All registers to spill to StackSlot, including the main register. 74 SmallVector<unsigned, 8> RegsToSpill; 75 76 // All COPY instructions to/from snippets. 77 // They are ignored since both operands refer to the same stack slot. 78 SmallPtrSet<MachineInstr*, 8> SnippetCopies; 79 80 // Values that failed to remat at some point. 81 SmallPtrSet<VNInfo*, 8> UsedValues; 82 83 public: 84 // Information about a value that was defined by a copy from a sibling 85 // register. 86 struct SibValueInfo { 87 // True when all reaching defs were reloads: No spill is necessary. 88 bool AllDefsAreReloads; 89 90 // True when value is defined by an original PHI not from splitting. 91 bool DefByOrigPHI; 92 93 // True when the COPY defining this value killed its source. 94 bool KillsSource; 95 96 // The preferred register to spill. 97 unsigned SpillReg; 98 99 // The value of SpillReg that should be spilled. 100 VNInfo *SpillVNI; 101 102 // The block where SpillVNI should be spilled. Currently, this must be the 103 // block containing SpillVNI->def. 104 MachineBasicBlock *SpillMBB; 105 106 // A defining instruction that is not a sibling copy or a reload, or NULL. 107 // This can be used as a template for rematerialization. 108 MachineInstr *DefMI; 109 110 // List of values that depend on this one. These values are actually the 111 // same, but live range splitting has placed them in different registers, 112 // or SSA update needed to insert PHI-defs to preserve SSA form. This is 113 // copies of the current value and phi-kills. Usually only phi-kills cause 114 // more than one dependent value. 115 TinyPtrVector<VNInfo*> Deps; 116 117 SibValueInfo(unsigned Reg, VNInfo *VNI) 118 : AllDefsAreReloads(true), DefByOrigPHI(false), KillsSource(false), 119 SpillReg(Reg), SpillVNI(VNI), SpillMBB(0), DefMI(0) {} 120 121 // Returns true when a def has been found. 122 bool hasDef() const { return DefByOrigPHI || DefMI; } 123 }; 124 125 private: 126 // Values in RegsToSpill defined by sibling copies. 127 typedef DenseMap<VNInfo*, SibValueInfo> SibValueMap; 128 SibValueMap SibValues; 129 130 // Dead defs generated during spilling. 131 SmallVector<MachineInstr*, 8> DeadDefs; 132 133 ~InlineSpiller() {} 134 135 public: 136 InlineSpiller(MachineFunctionPass &pass, 137 MachineFunction &mf, 138 VirtRegMap &vrm) 139 : MF(mf), 140 LIS(pass.getAnalysis<LiveIntervals>()), 141 LSS(pass.getAnalysis<LiveStacks>()), 142 AA(&pass.getAnalysis<AliasAnalysis>()), 143 MDT(pass.getAnalysis<MachineDominatorTree>()), 144 Loops(pass.getAnalysis<MachineLoopInfo>()), 145 VRM(vrm), 146 MFI(*mf.getFrameInfo()), 147 MRI(mf.getRegInfo()), 148 TII(*mf.getTarget().getInstrInfo()), 149 TRI(*mf.getTarget().getRegisterInfo()) {} 150 151 void spill(LiveRangeEdit &); 152 153 private: 154 bool isSnippet(const LiveInterval &SnipLI); 155 void collectRegsToSpill(); 156 157 bool isRegToSpill(unsigned Reg) { 158 return std::find(RegsToSpill.begin(), 159 RegsToSpill.end(), Reg) != RegsToSpill.end(); 160 } 161 162 bool isSibling(unsigned Reg); 163 MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*); 164 void propagateSiblingValue(SibValueMap::iterator, VNInfo *VNI = 0); 165 void analyzeSiblingValues(); 166 167 bool hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI); 168 void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI); 169 170 void markValueUsed(LiveInterval*, VNInfo*); 171 bool reMaterializeFor(LiveInterval&, MachineBasicBlock::iterator MI); 172 void reMaterializeAll(); 173 174 bool coalesceStackAccess(MachineInstr *MI, unsigned Reg); 175 bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr*, unsigned> >, 176 MachineInstr *LoadMI = 0); 177 void insertReload(LiveInterval &NewLI, SlotIndex, 178 MachineBasicBlock::iterator MI); 179 void insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI, 180 SlotIndex, MachineBasicBlock::iterator MI); 181 182 void spillAroundUses(unsigned Reg); 183 void spillAll(); 184 }; 185 } 186 187 namespace llvm { 188 Spiller *createInlineSpiller(MachineFunctionPass &pass, 189 MachineFunction &mf, 190 VirtRegMap &vrm) { 191 return new InlineSpiller(pass, mf, vrm); 192 } 193 } 194 195 //===----------------------------------------------------------------------===// 196 // Snippets 197 //===----------------------------------------------------------------------===// 198 199 // When spilling a virtual register, we also spill any snippets it is connected 200 // to. The snippets are small live ranges that only have a single real use, 201 // leftovers from live range splitting. Spilling them enables memory operand 202 // folding or tightens the live range around the single use. 203 // 204 // This minimizes register pressure and maximizes the store-to-load distance for 205 // spill slots which can be important in tight loops. 206 207 /// isFullCopyOf - If MI is a COPY to or from Reg, return the other register, 208 /// otherwise return 0. 209 static unsigned isFullCopyOf(const MachineInstr *MI, unsigned Reg) { 210 if (!MI->isFullCopy()) 211 return 0; 212 if (MI->getOperand(0).getReg() == Reg) 213 return MI->getOperand(1).getReg(); 214 if (MI->getOperand(1).getReg() == Reg) 215 return MI->getOperand(0).getReg(); 216 return 0; 217 } 218 219 /// isSnippet - Identify if a live interval is a snippet that should be spilled. 220 /// It is assumed that SnipLI is a virtual register with the same original as 221 /// Edit->getReg(). 222 bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) { 223 unsigned Reg = Edit->getReg(); 224 225 // A snippet is a tiny live range with only a single instruction using it 226 // besides copies to/from Reg or spills/fills. We accept: 227 // 228 // %snip = COPY %Reg / FILL fi# 229 // %snip = USE %snip 230 // %Reg = COPY %snip / SPILL %snip, fi# 231 // 232 if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI)) 233 return false; 234 235 MachineInstr *UseMI = 0; 236 237 // Check that all uses satisfy our criteria. 238 for (MachineRegisterInfo::reg_nodbg_iterator 239 RI = MRI.reg_nodbg_begin(SnipLI.reg); 240 MachineInstr *MI = RI.skipInstruction();) { 241 242 // Allow copies to/from Reg. 243 if (isFullCopyOf(MI, Reg)) 244 continue; 245 246 // Allow stack slot loads. 247 int FI; 248 if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) 249 continue; 250 251 // Allow stack slot stores. 252 if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) 253 continue; 254 255 // Allow a single additional instruction. 256 if (UseMI && MI != UseMI) 257 return false; 258 UseMI = MI; 259 } 260 return true; 261 } 262 263 /// collectRegsToSpill - Collect live range snippets that only have a single 264 /// real use. 265 void InlineSpiller::collectRegsToSpill() { 266 unsigned Reg = Edit->getReg(); 267 268 // Main register always spills. 269 RegsToSpill.assign(1, Reg); 270 SnippetCopies.clear(); 271 272 // Snippets all have the same original, so there can't be any for an original 273 // register. 274 if (Original == Reg) 275 return; 276 277 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg); 278 MachineInstr *MI = RI.skipInstruction();) { 279 unsigned SnipReg = isFullCopyOf(MI, Reg); 280 if (!isSibling(SnipReg)) 281 continue; 282 LiveInterval &SnipLI = LIS.getInterval(SnipReg); 283 if (!isSnippet(SnipLI)) 284 continue; 285 SnippetCopies.insert(MI); 286 if (isRegToSpill(SnipReg)) 287 continue; 288 RegsToSpill.push_back(SnipReg); 289 DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n'); 290 ++NumSnippets; 291 } 292 } 293 294 295 //===----------------------------------------------------------------------===// 296 // Sibling Values 297 //===----------------------------------------------------------------------===// 298 299 // After live range splitting, some values to be spilled may be defined by 300 // copies from sibling registers. We trace the sibling copies back to the 301 // original value if it still exists. We need it for rematerialization. 302 // 303 // Even when the value can't be rematerialized, we still want to determine if 304 // the value has already been spilled, or we may want to hoist the spill from a 305 // loop. 306 307 bool InlineSpiller::isSibling(unsigned Reg) { 308 return TargetRegisterInfo::isVirtualRegister(Reg) && 309 VRM.getOriginal(Reg) == Original; 310 } 311 312 #ifndef NDEBUG 313 static raw_ostream &operator<<(raw_ostream &OS, 314 const InlineSpiller::SibValueInfo &SVI) { 315 OS << "spill " << PrintReg(SVI.SpillReg) << ':' 316 << SVI.SpillVNI->id << '@' << SVI.SpillVNI->def; 317 if (SVI.SpillMBB) 318 OS << " in BB#" << SVI.SpillMBB->getNumber(); 319 if (SVI.AllDefsAreReloads) 320 OS << " all-reloads"; 321 if (SVI.DefByOrigPHI) 322 OS << " orig-phi"; 323 if (SVI.KillsSource) 324 OS << " kill"; 325 OS << " deps["; 326 for (unsigned i = 0, e = SVI.Deps.size(); i != e; ++i) 327 OS << ' ' << SVI.Deps[i]->id << '@' << SVI.Deps[i]->def; 328 OS << " ]"; 329 if (SVI.DefMI) 330 OS << " def: " << *SVI.DefMI; 331 else 332 OS << '\n'; 333 return OS; 334 } 335 #endif 336 337 /// propagateSiblingValue - Propagate the value in SVI to dependents if it is 338 /// known. Otherwise remember the dependency for later. 339 /// 340 /// @param SVI SibValues entry to propagate. 341 /// @param VNI Dependent value, or NULL to propagate to all saved dependents. 342 void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVI, 343 VNInfo *VNI) { 344 // When VNI is non-NULL, add it to SVI's deps, and only propagate to that. 345 TinyPtrVector<VNInfo*> FirstDeps; 346 if (VNI) { 347 FirstDeps.push_back(VNI); 348 SVI->second.Deps.push_back(VNI); 349 } 350 351 // Has the value been completely determined yet? If not, defer propagation. 352 if (!SVI->second.hasDef()) 353 return; 354 355 // Work list of values to propagate. It would be nice to use a SetVector 356 // here, but then we would be forced to use a SmallSet. 357 SmallVector<SibValueMap::iterator, 8> WorkList(1, SVI); 358 SmallPtrSet<VNInfo*, 8> WorkSet; 359 360 do { 361 SVI = WorkList.pop_back_val(); 362 WorkSet.erase(SVI->first); 363 TinyPtrVector<VNInfo*> *Deps = VNI ? &FirstDeps : &SVI->second.Deps; 364 VNI = 0; 365 366 SibValueInfo &SV = SVI->second; 367 if (!SV.SpillMBB) 368 SV.SpillMBB = LIS.getMBBFromIndex(SV.SpillVNI->def); 369 370 DEBUG(dbgs() << " prop to " << Deps->size() << ": " 371 << SVI->first->id << '@' << SVI->first->def << ":\t" << SV); 372 373 assert(SV.hasDef() && "Propagating undefined value"); 374 375 // Should this value be propagated as a preferred spill candidate? We don't 376 // propagate values of registers that are about to spill. 377 bool PropSpill = !DisableHoisting && !isRegToSpill(SV.SpillReg); 378 unsigned SpillDepth = ~0u; 379 380 for (TinyPtrVector<VNInfo*>::iterator DepI = Deps->begin(), 381 DepE = Deps->end(); DepI != DepE; ++DepI) { 382 SibValueMap::iterator DepSVI = SibValues.find(*DepI); 383 assert(DepSVI != SibValues.end() && "Dependent value not in SibValues"); 384 SibValueInfo &DepSV = DepSVI->second; 385 if (!DepSV.SpillMBB) 386 DepSV.SpillMBB = LIS.getMBBFromIndex(DepSV.SpillVNI->def); 387 388 bool Changed = false; 389 390 // Propagate defining instruction. 391 if (!DepSV.hasDef()) { 392 Changed = true; 393 DepSV.DefMI = SV.DefMI; 394 DepSV.DefByOrigPHI = SV.DefByOrigPHI; 395 } 396 397 // Propagate AllDefsAreReloads. For PHI values, this computes an AND of 398 // all predecessors. 399 if (!SV.AllDefsAreReloads && DepSV.AllDefsAreReloads) { 400 Changed = true; 401 DepSV.AllDefsAreReloads = false; 402 } 403 404 // Propagate best spill value. 405 if (PropSpill && SV.SpillVNI != DepSV.SpillVNI) { 406 if (SV.SpillMBB == DepSV.SpillMBB) { 407 // DepSV is in the same block. Hoist when dominated. 408 if (DepSV.KillsSource && SV.SpillVNI->def < DepSV.SpillVNI->def) { 409 // This is an alternative def earlier in the same MBB. 410 // Hoist the spill as far as possible in SpillMBB. This can ease 411 // register pressure: 412 // 413 // x = def 414 // y = use x 415 // s = copy x 416 // 417 // Hoisting the spill of s to immediately after the def removes the 418 // interference between x and y: 419 // 420 // x = def 421 // spill x 422 // y = use x<kill> 423 // 424 // This hoist only helps when the DepSV copy kills its source. 425 Changed = true; 426 DepSV.SpillReg = SV.SpillReg; 427 DepSV.SpillVNI = SV.SpillVNI; 428 DepSV.SpillMBB = SV.SpillMBB; 429 } 430 } else { 431 // DepSV is in a different block. 432 if (SpillDepth == ~0u) 433 SpillDepth = Loops.getLoopDepth(SV.SpillMBB); 434 435 // Also hoist spills to blocks with smaller loop depth, but make sure 436 // that the new value dominates. Non-phi dependents are always 437 // dominated, phis need checking. 438 if ((Loops.getLoopDepth(DepSV.SpillMBB) > SpillDepth) && 439 (!DepSVI->first->isPHIDef() || 440 MDT.dominates(SV.SpillMBB, DepSV.SpillMBB))) { 441 Changed = true; 442 DepSV.SpillReg = SV.SpillReg; 443 DepSV.SpillVNI = SV.SpillVNI; 444 DepSV.SpillMBB = SV.SpillMBB; 445 } 446 } 447 } 448 449 if (!Changed) 450 continue; 451 452 // Something changed in DepSVI. Propagate to dependents. 453 if (WorkSet.insert(DepSVI->first)) 454 WorkList.push_back(DepSVI); 455 456 DEBUG(dbgs() << " update " << DepSVI->first->id << '@' 457 << DepSVI->first->def << " to:\t" << DepSV); 458 } 459 } while (!WorkList.empty()); 460 } 461 462 /// traceSiblingValue - Trace a value that is about to be spilled back to the 463 /// real defining instructions by looking through sibling copies. Always stay 464 /// within the range of OrigVNI so the registers are known to carry the same 465 /// value. 466 /// 467 /// Determine if the value is defined by all reloads, so spilling isn't 468 /// necessary - the value is already in the stack slot. 469 /// 470 /// Return a defining instruction that may be a candidate for rematerialization. 471 /// 472 MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, 473 VNInfo *OrigVNI) { 474 // Check if a cached value already exists. 475 SibValueMap::iterator SVI; 476 bool Inserted; 477 tie(SVI, Inserted) = 478 SibValues.insert(std::make_pair(UseVNI, SibValueInfo(UseReg, UseVNI))); 479 if (!Inserted) { 480 DEBUG(dbgs() << "Cached value " << PrintReg(UseReg) << ':' 481 << UseVNI->id << '@' << UseVNI->def << ' ' << SVI->second); 482 return SVI->second.DefMI; 483 } 484 485 DEBUG(dbgs() << "Tracing value " << PrintReg(UseReg) << ':' 486 << UseVNI->id << '@' << UseVNI->def << '\n'); 487 488 // List of (Reg, VNI) that have been inserted into SibValues, but need to be 489 // processed. 490 SmallVector<std::pair<unsigned, VNInfo*>, 8> WorkList; 491 WorkList.push_back(std::make_pair(UseReg, UseVNI)); 492 493 do { 494 unsigned Reg; 495 VNInfo *VNI; 496 tie(Reg, VNI) = WorkList.pop_back_val(); 497 DEBUG(dbgs() << " " << PrintReg(Reg) << ':' << VNI->id << '@' << VNI->def 498 << ":\t"); 499 500 // First check if this value has already been computed. 501 SVI = SibValues.find(VNI); 502 assert(SVI != SibValues.end() && "Missing SibValues entry"); 503 504 // Trace through PHI-defs created by live range splitting. 505 if (VNI->isPHIDef()) { 506 // Stop at original PHIs. We don't know the value at the predecessors. 507 if (VNI->def == OrigVNI->def) { 508 DEBUG(dbgs() << "orig phi value\n"); 509 SVI->second.DefByOrigPHI = true; 510 SVI->second.AllDefsAreReloads = false; 511 propagateSiblingValue(SVI); 512 continue; 513 } 514 515 // This is a PHI inserted by live range splitting. We could trace the 516 // live-out value from predecessor blocks, but that search can be very 517 // expensive if there are many predecessors and many more PHIs as 518 // generated by tail-dup when it sees an indirectbr. Instead, look at 519 // all the non-PHI defs that have the same value as OrigVNI. They must 520 // jointly dominate VNI->def. This is not optimal since VNI may actually 521 // be jointly dominated by a smaller subset of defs, so there is a change 522 // we will miss a AllDefsAreReloads optimization. 523 524 // Separate all values dominated by OrigVNI into PHIs and non-PHIs. 525 SmallVector<VNInfo*, 8> PHIs, NonPHIs; 526 LiveInterval &LI = LIS.getInterval(Reg); 527 LiveInterval &OrigLI = LIS.getInterval(Original); 528 529 for (LiveInterval::vni_iterator VI = LI.vni_begin(), VE = LI.vni_end(); 530 VI != VE; ++VI) { 531 VNInfo *VNI2 = *VI; 532 if (VNI2->isUnused()) 533 continue; 534 if (!OrigLI.containsOneValue() && 535 OrigLI.getVNInfoAt(VNI2->def) != OrigVNI) 536 continue; 537 if (VNI2->isPHIDef() && VNI2->def != OrigVNI->def) 538 PHIs.push_back(VNI2); 539 else 540 NonPHIs.push_back(VNI2); 541 } 542 DEBUG(dbgs() << "split phi value, checking " << PHIs.size() 543 << " phi-defs, and " << NonPHIs.size() 544 << " non-phi/orig defs\n"); 545 546 // Create entries for all the PHIs. Don't add them to the worklist, we 547 // are processing all of them in one go here. 548 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 549 SibValues.insert(std::make_pair(PHIs[i], SibValueInfo(Reg, PHIs[i]))); 550 551 // Add every PHI as a dependent of all the non-PHIs. 552 for (unsigned i = 0, e = NonPHIs.size(); i != e; ++i) { 553 VNInfo *NonPHI = NonPHIs[i]; 554 // Known value? Try an insertion. 555 tie(SVI, Inserted) = 556 SibValues.insert(std::make_pair(NonPHI, SibValueInfo(Reg, NonPHI))); 557 // Add all the PHIs as dependents of NonPHI. 558 for (unsigned pi = 0, pe = PHIs.size(); pi != pe; ++pi) 559 SVI->second.Deps.push_back(PHIs[pi]); 560 // This is the first time we see NonPHI, add it to the worklist. 561 if (Inserted) 562 WorkList.push_back(std::make_pair(Reg, NonPHI)); 563 else 564 // Propagate to all inserted PHIs, not just VNI. 565 propagateSiblingValue(SVI); 566 } 567 568 // Next work list item. 569 continue; 570 } 571 572 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 573 assert(MI && "Missing def"); 574 575 // Trace through sibling copies. 576 if (unsigned SrcReg = isFullCopyOf(MI, Reg)) { 577 if (isSibling(SrcReg)) { 578 LiveInterval &SrcLI = LIS.getInterval(SrcReg); 579 LiveRangeQuery SrcQ(SrcLI, VNI->def); 580 assert(SrcQ.valueIn() && "Copy from non-existing value"); 581 // Check if this COPY kills its source. 582 SVI->second.KillsSource = SrcQ.isKill(); 583 VNInfo *SrcVNI = SrcQ.valueIn(); 584 DEBUG(dbgs() << "copy of " << PrintReg(SrcReg) << ':' 585 << SrcVNI->id << '@' << SrcVNI->def 586 << " kill=" << unsigned(SVI->second.KillsSource) << '\n'); 587 // Known sibling source value? Try an insertion. 588 tie(SVI, Inserted) = SibValues.insert(std::make_pair(SrcVNI, 589 SibValueInfo(SrcReg, SrcVNI))); 590 // This is the first time we see Src, add it to the worklist. 591 if (Inserted) 592 WorkList.push_back(std::make_pair(SrcReg, SrcVNI)); 593 propagateSiblingValue(SVI, VNI); 594 // Next work list item. 595 continue; 596 } 597 } 598 599 // Track reachable reloads. 600 SVI->second.DefMI = MI; 601 SVI->second.SpillMBB = MI->getParent(); 602 int FI; 603 if (Reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) { 604 DEBUG(dbgs() << "reload\n"); 605 propagateSiblingValue(SVI); 606 // Next work list item. 607 continue; 608 } 609 610 // Potential remat candidate. 611 DEBUG(dbgs() << "def " << *MI); 612 SVI->second.AllDefsAreReloads = false; 613 propagateSiblingValue(SVI); 614 } while (!WorkList.empty()); 615 616 // Look up the value we were looking for. We already did this lookup at the 617 // top of the function, but SibValues may have been invalidated. 618 SVI = SibValues.find(UseVNI); 619 assert(SVI != SibValues.end() && "Didn't compute requested info"); 620 DEBUG(dbgs() << " traced to:\t" << SVI->second); 621 return SVI->second.DefMI; 622 } 623 624 /// analyzeSiblingValues - Trace values defined by sibling copies back to 625 /// something that isn't a sibling copy. 626 /// 627 /// Keep track of values that may be rematerializable. 628 void InlineSpiller::analyzeSiblingValues() { 629 SibValues.clear(); 630 631 // No siblings at all? 632 if (Edit->getReg() == Original) 633 return; 634 635 LiveInterval &OrigLI = LIS.getInterval(Original); 636 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 637 unsigned Reg = RegsToSpill[i]; 638 LiveInterval &LI = LIS.getInterval(Reg); 639 for (LiveInterval::const_vni_iterator VI = LI.vni_begin(), 640 VE = LI.vni_end(); VI != VE; ++VI) { 641 VNInfo *VNI = *VI; 642 if (VNI->isUnused()) 643 continue; 644 MachineInstr *DefMI = 0; 645 if (!VNI->isPHIDef()) { 646 DefMI = LIS.getInstructionFromIndex(VNI->def); 647 assert(DefMI && "No defining instruction"); 648 } 649 // Check possible sibling copies. 650 if (VNI->isPHIDef() || DefMI->isCopy()) { 651 VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def); 652 assert(OrigVNI && "Def outside original live range"); 653 if (OrigVNI->def != VNI->def) 654 DefMI = traceSiblingValue(Reg, VNI, OrigVNI); 655 } 656 if (DefMI && Edit->checkRematerializable(VNI, DefMI, AA)) { 657 DEBUG(dbgs() << "Value " << PrintReg(Reg) << ':' << VNI->id << '@' 658 << VNI->def << " may remat from " << *DefMI); 659 } 660 } 661 } 662 } 663 664 /// hoistSpill - Given a sibling copy that defines a value to be spilled, insert 665 /// a spill at a better location. 666 bool InlineSpiller::hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI) { 667 SlotIndex Idx = LIS.getInstructionIndex(CopyMI); 668 VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot()); 669 assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy"); 670 SibValueMap::iterator I = SibValues.find(VNI); 671 if (I == SibValues.end()) 672 return false; 673 674 const SibValueInfo &SVI = I->second; 675 676 // Let the normal folding code deal with the boring case. 677 if (!SVI.AllDefsAreReloads && SVI.SpillVNI == VNI) 678 return false; 679 680 // SpillReg may have been deleted by remat and DCE. 681 if (!LIS.hasInterval(SVI.SpillReg)) { 682 DEBUG(dbgs() << "Stale interval: " << PrintReg(SVI.SpillReg) << '\n'); 683 SibValues.erase(I); 684 return false; 685 } 686 687 LiveInterval &SibLI = LIS.getInterval(SVI.SpillReg); 688 if (!SibLI.containsValue(SVI.SpillVNI)) { 689 DEBUG(dbgs() << "Stale value: " << PrintReg(SVI.SpillReg) << '\n'); 690 SibValues.erase(I); 691 return false; 692 } 693 694 // Conservatively extend the stack slot range to the range of the original 695 // value. We may be able to do better with stack slot coloring by being more 696 // careful here. 697 assert(StackInt && "No stack slot assigned yet."); 698 LiveInterval &OrigLI = LIS.getInterval(Original); 699 VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx); 700 StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0)); 701 DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": " 702 << *StackInt << '\n'); 703 704 // Already spilled everywhere. 705 if (SVI.AllDefsAreReloads) { 706 DEBUG(dbgs() << "\tno spill needed: " << SVI); 707 ++NumOmitReloadSpill; 708 return true; 709 } 710 // We are going to spill SVI.SpillVNI immediately after its def, so clear out 711 // any later spills of the same value. 712 eliminateRedundantSpills(SibLI, SVI.SpillVNI); 713 714 MachineBasicBlock *MBB = LIS.getMBBFromIndex(SVI.SpillVNI->def); 715 MachineBasicBlock::iterator MII; 716 if (SVI.SpillVNI->isPHIDef()) 717 MII = MBB->SkipPHIsAndLabels(MBB->begin()); 718 else { 719 MachineInstr *DefMI = LIS.getInstructionFromIndex(SVI.SpillVNI->def); 720 assert(DefMI && "Defining instruction disappeared"); 721 MII = DefMI; 722 ++MII; 723 } 724 // Insert spill without kill flag immediately after def. 725 TII.storeRegToStackSlot(*MBB, MII, SVI.SpillReg, false, StackSlot, 726 MRI.getRegClass(SVI.SpillReg), &TRI); 727 --MII; // Point to store instruction. 728 LIS.InsertMachineInstrInMaps(MII); 729 DEBUG(dbgs() << "\thoisted: " << SVI.SpillVNI->def << '\t' << *MII); 730 731 ++NumSpills; 732 ++NumHoists; 733 return true; 734 } 735 736 /// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any 737 /// redundant spills of this value in SLI.reg and sibling copies. 738 void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) { 739 assert(VNI && "Missing value"); 740 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList; 741 WorkList.push_back(std::make_pair(&SLI, VNI)); 742 assert(StackInt && "No stack slot assigned yet."); 743 744 do { 745 LiveInterval *LI; 746 tie(LI, VNI) = WorkList.pop_back_val(); 747 unsigned Reg = LI->reg; 748 DEBUG(dbgs() << "Checking redundant spills for " 749 << VNI->id << '@' << VNI->def << " in " << *LI << '\n'); 750 751 // Regs to spill are taken care of. 752 if (isRegToSpill(Reg)) 753 continue; 754 755 // Add all of VNI's live range to StackInt. 756 StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0)); 757 DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n'); 758 759 // Find all spills and copies of VNI. 760 for (MachineRegisterInfo::use_nodbg_iterator UI = MRI.use_nodbg_begin(Reg); 761 MachineInstr *MI = UI.skipInstruction();) { 762 if (!MI->isCopy() && !MI->mayStore()) 763 continue; 764 SlotIndex Idx = LIS.getInstructionIndex(MI); 765 if (LI->getVNInfoAt(Idx) != VNI) 766 continue; 767 768 // Follow sibling copies down the dominator tree. 769 if (unsigned DstReg = isFullCopyOf(MI, Reg)) { 770 if (isSibling(DstReg)) { 771 LiveInterval &DstLI = LIS.getInterval(DstReg); 772 VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot()); 773 assert(DstVNI && "Missing defined value"); 774 assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot"); 775 WorkList.push_back(std::make_pair(&DstLI, DstVNI)); 776 } 777 continue; 778 } 779 780 // Erase spills. 781 int FI; 782 if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) { 783 DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << *MI); 784 // eliminateDeadDefs won't normally remove stores, so switch opcode. 785 MI->setDesc(TII.get(TargetOpcode::KILL)); 786 DeadDefs.push_back(MI); 787 ++NumSpillsRemoved; 788 --NumSpills; 789 } 790 } 791 } while (!WorkList.empty()); 792 } 793 794 795 //===----------------------------------------------------------------------===// 796 // Rematerialization 797 //===----------------------------------------------------------------------===// 798 799 /// markValueUsed - Remember that VNI failed to rematerialize, so its defining 800 /// instruction cannot be eliminated. See through snippet copies 801 void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) { 802 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList; 803 WorkList.push_back(std::make_pair(LI, VNI)); 804 do { 805 tie(LI, VNI) = WorkList.pop_back_val(); 806 if (!UsedValues.insert(VNI)) 807 continue; 808 809 if (VNI->isPHIDef()) { 810 MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 811 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 812 PE = MBB->pred_end(); PI != PE; ++PI) { 813 VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI)); 814 if (PVNI) 815 WorkList.push_back(std::make_pair(LI, PVNI)); 816 } 817 continue; 818 } 819 820 // Follow snippet copies. 821 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 822 if (!SnippetCopies.count(MI)) 823 continue; 824 LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg()); 825 assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy"); 826 VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true)); 827 assert(SnipVNI && "Snippet undefined before copy"); 828 WorkList.push_back(std::make_pair(&SnipLI, SnipVNI)); 829 } while (!WorkList.empty()); 830 } 831 832 /// reMaterializeFor - Attempt to rematerialize before MI instead of reloading. 833 bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, 834 MachineBasicBlock::iterator MI) { 835 SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true); 836 VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex()); 837 838 if (!ParentVNI) { 839 DEBUG(dbgs() << "\tadding <undef> flags: "); 840 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 841 MachineOperand &MO = MI->getOperand(i); 842 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) 843 MO.setIsUndef(); 844 } 845 DEBUG(dbgs() << UseIdx << '\t' << *MI); 846 return true; 847 } 848 849 if (SnippetCopies.count(MI)) 850 return false; 851 852 // Use an OrigVNI from traceSiblingValue when ParentVNI is a sibling copy. 853 LiveRangeEdit::Remat RM(ParentVNI); 854 SibValueMap::const_iterator SibI = SibValues.find(ParentVNI); 855 if (SibI != SibValues.end()) 856 RM.OrigMI = SibI->second.DefMI; 857 if (!Edit->canRematerializeAt(RM, UseIdx, false)) { 858 markValueUsed(&VirtReg, ParentVNI); 859 DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI); 860 return false; 861 } 862 863 // If the instruction also writes VirtReg.reg, it had better not require the 864 // same register for uses and defs. 865 SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops; 866 MIBundleOperands::RegInfo RI = 867 MIBundleOperands(MI).analyzeVirtReg(VirtReg.reg, &Ops); 868 if (RI.Tied) { 869 markValueUsed(&VirtReg, ParentVNI); 870 DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI); 871 return false; 872 } 873 874 // Before rematerializing into a register for a single instruction, try to 875 // fold a load into the instruction. That avoids allocating a new register. 876 if (RM.OrigMI->canFoldAsLoad() && 877 foldMemoryOperand(Ops, RM.OrigMI)) { 878 Edit->markRematerialized(RM.ParentVNI); 879 ++NumFoldedLoads; 880 return true; 881 } 882 883 // Alocate a new register for the remat. 884 LiveInterval &NewLI = Edit->createFrom(Original); 885 NewLI.markNotSpillable(); 886 887 // Finally we can rematerialize OrigMI before MI. 888 SlotIndex DefIdx = Edit->rematerializeAt(*MI->getParent(), MI, NewLI.reg, RM, 889 TRI); 890 DEBUG(dbgs() << "\tremat: " << DefIdx << '\t' 891 << *LIS.getInstructionFromIndex(DefIdx)); 892 893 // Replace operands 894 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 895 MachineOperand &MO = MI->getOperand(Ops[i].second); 896 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) { 897 MO.setReg(NewLI.reg); 898 MO.setIsKill(); 899 } 900 } 901 DEBUG(dbgs() << "\t " << UseIdx << '\t' << *MI); 902 903 VNInfo *DefVNI = NewLI.getNextValue(DefIdx, LIS.getVNInfoAllocator()); 904 NewLI.addRange(LiveRange(DefIdx, UseIdx.getRegSlot(), DefVNI)); 905 DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); 906 ++NumRemats; 907 return true; 908 } 909 910 /// reMaterializeAll - Try to rematerialize as many uses as possible, 911 /// and trim the live ranges after. 912 void InlineSpiller::reMaterializeAll() { 913 // analyzeSiblingValues has already tested all relevant defining instructions. 914 if (!Edit->anyRematerializable(AA)) 915 return; 916 917 UsedValues.clear(); 918 919 // Try to remat before all uses of snippets. 920 bool anyRemat = false; 921 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 922 unsigned Reg = RegsToSpill[i]; 923 LiveInterval &LI = LIS.getInterval(Reg); 924 for (MachineRegisterInfo::use_nodbg_iterator 925 RI = MRI.use_nodbg_begin(Reg); 926 MachineInstr *MI = RI.skipBundle();) 927 anyRemat |= reMaterializeFor(LI, MI); 928 } 929 if (!anyRemat) 930 return; 931 932 // Remove any values that were completely rematted. 933 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 934 unsigned Reg = RegsToSpill[i]; 935 LiveInterval &LI = LIS.getInterval(Reg); 936 for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end(); 937 I != E; ++I) { 938 VNInfo *VNI = *I; 939 if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI)) 940 continue; 941 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 942 MI->addRegisterDead(Reg, &TRI); 943 if (!MI->allDefsAreDead()) 944 continue; 945 DEBUG(dbgs() << "All defs dead: " << *MI); 946 DeadDefs.push_back(MI); 947 } 948 } 949 950 // Eliminate dead code after remat. Note that some snippet copies may be 951 // deleted here. 952 if (DeadDefs.empty()) 953 return; 954 DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n"); 955 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill); 956 957 // Get rid of deleted and empty intervals. 958 for (unsigned i = RegsToSpill.size(); i != 0; --i) { 959 unsigned Reg = RegsToSpill[i-1]; 960 if (!LIS.hasInterval(Reg)) { 961 RegsToSpill.erase(RegsToSpill.begin() + (i - 1)); 962 continue; 963 } 964 LiveInterval &LI = LIS.getInterval(Reg); 965 if (!LI.empty()) 966 continue; 967 Edit->eraseVirtReg(Reg); 968 RegsToSpill.erase(RegsToSpill.begin() + (i - 1)); 969 } 970 DEBUG(dbgs() << RegsToSpill.size() << " registers to spill after remat.\n"); 971 } 972 973 974 //===----------------------------------------------------------------------===// 975 // Spilling 976 //===----------------------------------------------------------------------===// 977 978 /// If MI is a load or store of StackSlot, it can be removed. 979 bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) { 980 int FI = 0; 981 unsigned InstrReg = TII.isLoadFromStackSlot(MI, FI); 982 bool IsLoad = InstrReg; 983 if (!IsLoad) 984 InstrReg = TII.isStoreToStackSlot(MI, FI); 985 986 // We have a stack access. Is it the right register and slot? 987 if (InstrReg != Reg || FI != StackSlot) 988 return false; 989 990 DEBUG(dbgs() << "Coalescing stack access: " << *MI); 991 LIS.RemoveMachineInstrFromMaps(MI); 992 MI->eraseFromParent(); 993 994 if (IsLoad) { 995 ++NumReloadsRemoved; 996 --NumReloads; 997 } else { 998 ++NumSpillsRemoved; 999 --NumSpills; 1000 } 1001 1002 return true; 1003 } 1004 1005 /// foldMemoryOperand - Try folding stack slot references in Ops into their 1006 /// instructions. 1007 /// 1008 /// @param Ops Operand indices from analyzeVirtReg(). 1009 /// @param LoadMI Load instruction to use instead of stack slot when non-null. 1010 /// @return True on success. 1011 bool InlineSpiller:: 1012 foldMemoryOperand(ArrayRef<std::pair<MachineInstr*, unsigned> > Ops, 1013 MachineInstr *LoadMI) { 1014 if (Ops.empty()) 1015 return false; 1016 // Don't attempt folding in bundles. 1017 MachineInstr *MI = Ops.front().first; 1018 if (Ops.back().first != MI || MI->isBundled()) 1019 return false; 1020 1021 bool WasCopy = MI->isCopy(); 1022 unsigned ImpReg = 0; 1023 1024 // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied 1025 // operands. 1026 SmallVector<unsigned, 8> FoldOps; 1027 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1028 unsigned Idx = Ops[i].second; 1029 MachineOperand &MO = MI->getOperand(Idx); 1030 if (MO.isImplicit()) { 1031 ImpReg = MO.getReg(); 1032 continue; 1033 } 1034 // FIXME: Teach targets to deal with subregs. 1035 if (MO.getSubReg()) 1036 return false; 1037 // We cannot fold a load instruction into a def. 1038 if (LoadMI && MO.isDef()) 1039 return false; 1040 // Tied use operands should not be passed to foldMemoryOperand. 1041 if (!MI->isRegTiedToDefOperand(Idx)) 1042 FoldOps.push_back(Idx); 1043 } 1044 1045 MachineInstr *FoldMI = 1046 LoadMI ? TII.foldMemoryOperand(MI, FoldOps, LoadMI) 1047 : TII.foldMemoryOperand(MI, FoldOps, StackSlot); 1048 if (!FoldMI) 1049 return false; 1050 LIS.ReplaceMachineInstrInMaps(MI, FoldMI); 1051 MI->eraseFromParent(); 1052 1053 // TII.foldMemoryOperand may have left some implicit operands on the 1054 // instruction. Strip them. 1055 if (ImpReg) 1056 for (unsigned i = FoldMI->getNumOperands(); i; --i) { 1057 MachineOperand &MO = FoldMI->getOperand(i - 1); 1058 if (!MO.isReg() || !MO.isImplicit()) 1059 break; 1060 if (MO.getReg() == ImpReg) 1061 FoldMI->RemoveOperand(i - 1); 1062 } 1063 1064 DEBUG(dbgs() << "\tfolded: " << LIS.getInstructionIndex(FoldMI) << '\t' 1065 << *FoldMI); 1066 if (!WasCopy) 1067 ++NumFolded; 1068 else if (Ops.front().second == 0) 1069 ++NumSpills; 1070 else 1071 ++NumReloads; 1072 return true; 1073 } 1074 1075 /// insertReload - Insert a reload of NewLI.reg before MI. 1076 void InlineSpiller::insertReload(LiveInterval &NewLI, 1077 SlotIndex Idx, 1078 MachineBasicBlock::iterator MI) { 1079 MachineBasicBlock &MBB = *MI->getParent(); 1080 TII.loadRegFromStackSlot(MBB, MI, NewLI.reg, StackSlot, 1081 MRI.getRegClass(NewLI.reg), &TRI); 1082 --MI; // Point to load instruction. 1083 SlotIndex LoadIdx = LIS.InsertMachineInstrInMaps(MI).getRegSlot(); 1084 // Some (out-of-tree) targets have EC reload instructions. 1085 if (MachineOperand *MO = MI->findRegisterDefOperand(NewLI.reg)) 1086 if (MO->isEarlyClobber()) 1087 LoadIdx = LoadIdx.getRegSlot(true); 1088 DEBUG(dbgs() << "\treload: " << LoadIdx << '\t' << *MI); 1089 VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, LIS.getVNInfoAllocator()); 1090 NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI)); 1091 ++NumReloads; 1092 } 1093 1094 /// insertSpill - Insert a spill of NewLI.reg after MI. 1095 void InlineSpiller::insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI, 1096 SlotIndex Idx, MachineBasicBlock::iterator MI) { 1097 MachineBasicBlock &MBB = *MI->getParent(); 1098 TII.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, StackSlot, 1099 MRI.getRegClass(NewLI.reg), &TRI); 1100 --MI; // Point to store instruction. 1101 SlotIndex StoreIdx = LIS.InsertMachineInstrInMaps(MI).getRegSlot(); 1102 DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI); 1103 VNInfo *StoreVNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator()); 1104 NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI)); 1105 ++NumSpills; 1106 } 1107 1108 /// spillAroundUses - insert spill code around each use of Reg. 1109 void InlineSpiller::spillAroundUses(unsigned Reg) { 1110 DEBUG(dbgs() << "spillAroundUses " << PrintReg(Reg) << '\n'); 1111 LiveInterval &OldLI = LIS.getInterval(Reg); 1112 1113 // Iterate over instructions using Reg. 1114 for (MachineRegisterInfo::reg_iterator RegI = MRI.reg_begin(Reg); 1115 MachineInstr *MI = RegI.skipBundle();) { 1116 1117 // Debug values are not allowed to affect codegen. 1118 if (MI->isDebugValue()) { 1119 // Modify DBG_VALUE now that the value is in a spill slot. 1120 uint64_t Offset = MI->getOperand(1).getImm(); 1121 const MDNode *MDPtr = MI->getOperand(2).getMetadata(); 1122 DebugLoc DL = MI->getDebugLoc(); 1123 if (MachineInstr *NewDV = TII.emitFrameIndexDebugValue(MF, StackSlot, 1124 Offset, MDPtr, DL)) { 1125 DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); 1126 MachineBasicBlock *MBB = MI->getParent(); 1127 MBB->insert(MBB->erase(MI), NewDV); 1128 } else { 1129 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 1130 MI->eraseFromParent(); 1131 } 1132 continue; 1133 } 1134 1135 // Ignore copies to/from snippets. We'll delete them. 1136 if (SnippetCopies.count(MI)) 1137 continue; 1138 1139 // Stack slot accesses may coalesce away. 1140 if (coalesceStackAccess(MI, Reg)) 1141 continue; 1142 1143 // Analyze instruction. 1144 SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops; 1145 MIBundleOperands::RegInfo RI = 1146 MIBundleOperands(MI).analyzeVirtReg(Reg, &Ops); 1147 1148 // Find the slot index where this instruction reads and writes OldLI. 1149 // This is usually the def slot, except for tied early clobbers. 1150 SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot(); 1151 if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true))) 1152 if (SlotIndex::isSameInstr(Idx, VNI->def)) 1153 Idx = VNI->def; 1154 1155 // Check for a sibling copy. 1156 unsigned SibReg = isFullCopyOf(MI, Reg); 1157 if (SibReg && isSibling(SibReg)) { 1158 // This may actually be a copy between snippets. 1159 if (isRegToSpill(SibReg)) { 1160 DEBUG(dbgs() << "Found new snippet copy: " << *MI); 1161 SnippetCopies.insert(MI); 1162 continue; 1163 } 1164 if (RI.Writes) { 1165 // Hoist the spill of a sib-reg copy. 1166 if (hoistSpill(OldLI, MI)) { 1167 // This COPY is now dead, the value is already in the stack slot. 1168 MI->getOperand(0).setIsDead(); 1169 DeadDefs.push_back(MI); 1170 continue; 1171 } 1172 } else { 1173 // This is a reload for a sib-reg copy. Drop spills downstream. 1174 LiveInterval &SibLI = LIS.getInterval(SibReg); 1175 eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx)); 1176 // The COPY will fold to a reload below. 1177 } 1178 } 1179 1180 // Attempt to fold memory ops. 1181 if (foldMemoryOperand(Ops)) 1182 continue; 1183 1184 // Allocate interval around instruction. 1185 // FIXME: Infer regclass from instruction alone. 1186 LiveInterval &NewLI = Edit->createFrom(Reg); 1187 NewLI.markNotSpillable(); 1188 1189 if (RI.Reads) 1190 insertReload(NewLI, Idx, MI); 1191 1192 // Rewrite instruction operands. 1193 bool hasLiveDef = false; 1194 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1195 MachineOperand &MO = Ops[i].first->getOperand(Ops[i].second); 1196 MO.setReg(NewLI.reg); 1197 if (MO.isUse()) { 1198 if (!Ops[i].first->isRegTiedToDefOperand(Ops[i].second)) 1199 MO.setIsKill(); 1200 } else { 1201 if (!MO.isDead()) 1202 hasLiveDef = true; 1203 } 1204 } 1205 DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI); 1206 1207 // FIXME: Use a second vreg if instruction has no tied ops. 1208 if (RI.Writes) { 1209 if (hasLiveDef) 1210 insertSpill(NewLI, OldLI, Idx, MI); 1211 else { 1212 // This instruction defines a dead value. We don't need to spill it, 1213 // but do create a live range for the dead value. 1214 VNInfo *VNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator()); 1215 NewLI.addRange(LiveRange(Idx, Idx.getDeadSlot(), VNI)); 1216 } 1217 } 1218 1219 DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); 1220 } 1221 } 1222 1223 /// spillAll - Spill all registers remaining after rematerialization. 1224 void InlineSpiller::spillAll() { 1225 // Update LiveStacks now that we are committed to spilling. 1226 if (StackSlot == VirtRegMap::NO_STACK_SLOT) { 1227 StackSlot = VRM.assignVirt2StackSlot(Original); 1228 StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original)); 1229 StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator()); 1230 } else 1231 StackInt = &LSS.getInterval(StackSlot); 1232 1233 if (Original != Edit->getReg()) 1234 VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot); 1235 1236 assert(StackInt->getNumValNums() == 1 && "Bad stack interval values"); 1237 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) 1238 StackInt->MergeRangesInAsValue(LIS.getInterval(RegsToSpill[i]), 1239 StackInt->getValNumInfo(0)); 1240 DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n'); 1241 1242 // Spill around uses of all RegsToSpill. 1243 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) 1244 spillAroundUses(RegsToSpill[i]); 1245 1246 // Hoisted spills may cause dead code. 1247 if (!DeadDefs.empty()) { 1248 DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n"); 1249 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill); 1250 } 1251 1252 // Finally delete the SnippetCopies. 1253 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 1254 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(RegsToSpill[i]); 1255 MachineInstr *MI = RI.skipInstruction();) { 1256 assert(SnippetCopies.count(MI) && "Remaining use wasn't a snippet copy"); 1257 // FIXME: Do this with a LiveRangeEdit callback. 1258 LIS.RemoveMachineInstrFromMaps(MI); 1259 MI->eraseFromParent(); 1260 } 1261 } 1262 1263 // Delete all spilled registers. 1264 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) 1265 Edit->eraseVirtReg(RegsToSpill[i]); 1266 } 1267 1268 void InlineSpiller::spill(LiveRangeEdit &edit) { 1269 ++NumSpilledRanges; 1270 Edit = &edit; 1271 assert(!TargetRegisterInfo::isStackSlot(edit.getReg()) 1272 && "Trying to spill a stack slot."); 1273 // Share a stack slot among all descendants of Original. 1274 Original = VRM.getOriginal(edit.getReg()); 1275 StackSlot = VRM.getStackSlot(Original); 1276 StackInt = 0; 1277 1278 DEBUG(dbgs() << "Inline spilling " 1279 << MRI.getRegClass(edit.getReg())->getName() 1280 << ':' << PrintReg(edit.getReg()) << ' ' << edit.getParent() 1281 << "\nFrom original " << LIS.getInterval(Original) << '\n'); 1282 assert(edit.getParent().isSpillable() && 1283 "Attempting to spill already spilled value."); 1284 assert(DeadDefs.empty() && "Previous spill didn't remove dead defs"); 1285 1286 collectRegsToSpill(); 1287 analyzeSiblingValues(); 1288 reMaterializeAll(); 1289 1290 // Remat may handle everything. 1291 if (!RegsToSpill.empty()) 1292 spillAll(); 1293 1294 Edit->calculateRegClassAndHint(MF, Loops); 1295 } 1296