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