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