InlineSpiller.cpp revision e9bd4ea5fda4957c373a3bbc14803d9670041dcc
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 "LiveRangeEdit.h" 18#include "VirtRegMap.h" 19#include "llvm/ADT/Statistic.h" 20#include "llvm/Analysis/AliasAnalysis.h" 21#include "llvm/CodeGen/LiveIntervalAnalysis.h" 22#include "llvm/CodeGen/LiveStackAnalysis.h" 23#include "llvm/CodeGen/MachineDominators.h" 24#include "llvm/CodeGen/MachineFrameInfo.h" 25#include "llvm/CodeGen/MachineFunction.h" 26#include "llvm/CodeGen/MachineLoopInfo.h" 27#include "llvm/CodeGen/MachineRegisterInfo.h" 28#include "llvm/Target/TargetMachine.h" 29#include "llvm/Target/TargetInstrInfo.h" 30#include "llvm/Support/Debug.h" 31#include "llvm/Support/raw_ostream.h" 32 33using namespace llvm; 34 35STATISTIC(NumSpilledRanges, "Number of spilled live ranges"); 36STATISTIC(NumSnippets, "Number of snippets included in spills"); 37STATISTIC(NumSpills, "Number of spills inserted"); 38STATISTIC(NumReloads, "Number of reloads inserted"); 39STATISTIC(NumFolded, "Number of folded stack accesses"); 40STATISTIC(NumFoldedLoads, "Number of folded loads"); 41STATISTIC(NumRemats, "Number of rematerialized defs for spilling"); 42STATISTIC(NumOmitReloadSpill, "Number of omitted spills after reloads"); 43STATISTIC(NumHoistLocal, "Number of locally hoisted spills"); 44STATISTIC(NumHoistGlobal, "Number of globally hoisted spills"); 45STATISTIC(NumRedundantSpills, "Number of redundant spills identified"); 46 47namespace { 48class InlineSpiller : public Spiller { 49 MachineFunctionPass &Pass; 50 MachineFunction &MF; 51 LiveIntervals &LIS; 52 LiveStacks &LSS; 53 AliasAnalysis *AA; 54 MachineDominatorTree &MDT; 55 MachineLoopInfo &Loops; 56 VirtRegMap &VRM; 57 MachineFrameInfo &MFI; 58 MachineRegisterInfo &MRI; 59 const TargetInstrInfo &TII; 60 const TargetRegisterInfo &TRI; 61 62 // Variables that are valid during spill(), but used by multiple methods. 63 LiveRangeEdit *Edit; 64 LiveInterval *StackInt; 65 int StackSlot; 66 unsigned Original; 67 68 // All registers to spill to StackSlot, including the main register. 69 SmallVector<unsigned, 8> RegsToSpill; 70 71 // All COPY instructions to/from snippets. 72 // They are ignored since both operands refer to the same stack slot. 73 SmallPtrSet<MachineInstr*, 8> SnippetCopies; 74 75 // Values that failed to remat at some point. 76 SmallPtrSet<VNInfo*, 8> UsedValues; 77 78 // Information about a value that was defined by a copy from a sibling 79 // register. 80 struct SibValueInfo { 81 // True when all reaching defs were reloads: No spill is necessary. 82 bool AllDefsAreReloads; 83 84 // The preferred register to spill. 85 unsigned SpillReg; 86 87 // The value of SpillReg that should be spilled. 88 VNInfo *SpillVNI; 89 90 // A defining instruction that is not a sibling copy or a reload, or NULL. 91 // This can be used as a template for rematerialization. 92 MachineInstr *DefMI; 93 94 SibValueInfo(unsigned Reg, VNInfo *VNI) 95 : AllDefsAreReloads(false), SpillReg(Reg), SpillVNI(VNI), DefMI(0) {} 96 }; 97 98 // Values in RegsToSpill defined by sibling copies. 99 typedef DenseMap<VNInfo*, SibValueInfo> SibValueMap; 100 SibValueMap SibValues; 101 102 // Dead defs generated during spilling. 103 SmallVector<MachineInstr*, 8> DeadDefs; 104 105 ~InlineSpiller() {} 106 107public: 108 InlineSpiller(MachineFunctionPass &pass, 109 MachineFunction &mf, 110 VirtRegMap &vrm) 111 : Pass(pass), 112 MF(mf), 113 LIS(pass.getAnalysis<LiveIntervals>()), 114 LSS(pass.getAnalysis<LiveStacks>()), 115 AA(&pass.getAnalysis<AliasAnalysis>()), 116 MDT(pass.getAnalysis<MachineDominatorTree>()), 117 Loops(pass.getAnalysis<MachineLoopInfo>()), 118 VRM(vrm), 119 MFI(*mf.getFrameInfo()), 120 MRI(mf.getRegInfo()), 121 TII(*mf.getTarget().getInstrInfo()), 122 TRI(*mf.getTarget().getRegisterInfo()) {} 123 124 void spill(LiveRangeEdit &); 125 126private: 127 bool isSnippet(const LiveInterval &SnipLI); 128 void collectRegsToSpill(); 129 130 bool isRegToSpill(unsigned Reg) { 131 return std::find(RegsToSpill.begin(), 132 RegsToSpill.end(), Reg) != RegsToSpill.end(); 133 } 134 135 bool isSibling(unsigned Reg); 136 MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*); 137 void analyzeSiblingValues(); 138 139 bool hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI); 140 void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI); 141 142 void markValueUsed(LiveInterval*, VNInfo*); 143 bool reMaterializeFor(LiveInterval&, MachineBasicBlock::iterator MI); 144 void reMaterializeAll(); 145 146 bool coalesceStackAccess(MachineInstr *MI, unsigned Reg); 147 bool foldMemoryOperand(MachineBasicBlock::iterator MI, 148 const SmallVectorImpl<unsigned> &Ops, 149 MachineInstr *LoadMI = 0); 150 void insertReload(LiveInterval &NewLI, SlotIndex, 151 MachineBasicBlock::iterator MI); 152 void insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI, 153 SlotIndex, MachineBasicBlock::iterator MI); 154 155 void spillAroundUses(unsigned Reg); 156 void spillAll(); 157}; 158} 159 160namespace llvm { 161Spiller *createInlineSpiller(MachineFunctionPass &pass, 162 MachineFunction &mf, 163 VirtRegMap &vrm) { 164 return new InlineSpiller(pass, mf, vrm); 165} 166} 167 168//===----------------------------------------------------------------------===// 169// Snippets 170//===----------------------------------------------------------------------===// 171 172// When spilling a virtual register, we also spill any snippets it is connected 173// to. The snippets are small live ranges that only have a single real use, 174// leftovers from live range splitting. Spilling them enables memory operand 175// folding or tightens the live range around the single use. 176// 177// This minimizes register pressure and maximizes the store-to-load distance for 178// spill slots which can be important in tight loops. 179 180/// isFullCopyOf - If MI is a COPY to or from Reg, return the other register, 181/// otherwise return 0. 182static unsigned isFullCopyOf(const MachineInstr *MI, unsigned Reg) { 183 if (!MI->isCopy()) 184 return 0; 185 if (MI->getOperand(0).getSubReg() != 0) 186 return 0; 187 if (MI->getOperand(1).getSubReg() != 0) 188 return 0; 189 if (MI->getOperand(0).getReg() == Reg) 190 return MI->getOperand(1).getReg(); 191 if (MI->getOperand(1).getReg() == Reg) 192 return MI->getOperand(0).getReg(); 193 return 0; 194} 195 196/// isSnippet - Identify if a live interval is a snippet that should be spilled. 197/// It is assumed that SnipLI is a virtual register with the same original as 198/// Edit->getReg(). 199bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) { 200 unsigned Reg = Edit->getReg(); 201 202 // A snippet is a tiny live range with only a single instruction using it 203 // besides copies to/from Reg or spills/fills. We accept: 204 // 205 // %snip = COPY %Reg / FILL fi# 206 // %snip = USE %snip 207 // %Reg = COPY %snip / SPILL %snip, fi# 208 // 209 if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI)) 210 return false; 211 212 MachineInstr *UseMI = 0; 213 214 // Check that all uses satisfy our criteria. 215 for (MachineRegisterInfo::reg_nodbg_iterator 216 RI = MRI.reg_nodbg_begin(SnipLI.reg); 217 MachineInstr *MI = RI.skipInstruction();) { 218 219 // Allow copies to/from Reg. 220 if (isFullCopyOf(MI, Reg)) 221 continue; 222 223 // Allow stack slot loads. 224 int FI; 225 if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) 226 continue; 227 228 // Allow stack slot stores. 229 if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) 230 continue; 231 232 // Allow a single additional instruction. 233 if (UseMI && MI != UseMI) 234 return false; 235 UseMI = MI; 236 } 237 return true; 238} 239 240/// collectRegsToSpill - Collect live range snippets that only have a single 241/// real use. 242void InlineSpiller::collectRegsToSpill() { 243 unsigned Reg = Edit->getReg(); 244 245 // Main register always spills. 246 RegsToSpill.assign(1, Reg); 247 SnippetCopies.clear(); 248 249 // Snippets all have the same original, so there can't be any for an original 250 // register. 251 if (Original == Reg) 252 return; 253 254 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg); 255 MachineInstr *MI = RI.skipInstruction();) { 256 unsigned SnipReg = isFullCopyOf(MI, Reg); 257 if (!isSibling(SnipReg)) 258 continue; 259 LiveInterval &SnipLI = LIS.getInterval(SnipReg); 260 if (!isSnippet(SnipLI)) 261 continue; 262 SnippetCopies.insert(MI); 263 if (isRegToSpill(SnipReg)) 264 continue; 265 RegsToSpill.push_back(SnipReg); 266 DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n'); 267 ++NumSnippets; 268 } 269} 270 271 272//===----------------------------------------------------------------------===// 273// Sibling Values 274//===----------------------------------------------------------------------===// 275 276// After live range splitting, some values to be spilled may be defined by 277// copies from sibling registers. We trace the sibling copies back to the 278// original value if it still exists. We need it for rematerialization. 279// 280// Even when the value can't be rematerialized, we still want to determine if 281// the value has already been spilled, or we may want to hoist the spill from a 282// loop. 283 284bool InlineSpiller::isSibling(unsigned Reg) { 285 return TargetRegisterInfo::isVirtualRegister(Reg) && 286 VRM.getOriginal(Reg) == Original; 287} 288 289/// traceSiblingValue - Trace a value that is about to be spilled back to the 290/// real defining instructions by looking through sibling copies. Always stay 291/// within the range of OrigVNI so the registers are known to carry the same 292/// value. 293/// 294/// Determine if the value is defined by all reloads, so spilling isn't 295/// necessary - the value is already in the stack slot. 296/// 297/// Return a defining instruction that may be a candidate for rematerialization. 298/// 299MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, 300 VNInfo *OrigVNI) { 301 DEBUG(dbgs() << "Tracing value " << PrintReg(UseReg) << ':' 302 << UseVNI->id << '@' << UseVNI->def << '\n'); 303 SmallPtrSet<VNInfo*, 8> Visited; 304 SmallVector<std::pair<unsigned, VNInfo*>, 8> WorkList; 305 WorkList.push_back(std::make_pair(UseReg, UseVNI)); 306 307 // Best spill candidate seen so far. This must dominate UseVNI. 308 SibValueInfo SVI(UseReg, UseVNI); 309 MachineBasicBlock *UseMBB = LIS.getMBBFromIndex(UseVNI->def); 310 unsigned SpillDepth = Loops.getLoopDepth(UseMBB); 311 bool SeenOrigPHI = false; // Original PHI met. 312 313 do { 314 unsigned Reg; 315 VNInfo *VNI; 316 tie(Reg, VNI) = WorkList.pop_back_val(); 317 if (!Visited.insert(VNI)) 318 continue; 319 320 // Is this value a better spill candidate? 321 if (!isRegToSpill(Reg)) { 322 MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 323 if (MBB != UseMBB && MDT.dominates(MBB, UseMBB)) { 324 // This is a valid spill location dominating UseVNI. 325 // Prefer to spill at a smaller loop depth. 326 unsigned Depth = Loops.getLoopDepth(MBB); 327 if (Depth < SpillDepth) { 328 DEBUG(dbgs() << " spill depth " << Depth << ": " << PrintReg(Reg) 329 << ':' << VNI->id << '@' << VNI->def << '\n'); 330 SVI.SpillReg = Reg; 331 SVI.SpillVNI = VNI; 332 SpillDepth = Depth; 333 } 334 } 335 } 336 337 // Trace through PHI-defs created by live range splitting. 338 if (VNI->isPHIDef()) { 339 if (VNI->def == OrigVNI->def) { 340 DEBUG(dbgs() << " orig phi value " << PrintReg(Reg) << ':' 341 << VNI->id << '@' << VNI->def << '\n'); 342 SeenOrigPHI = true; 343 continue; 344 } 345 // Get values live-out of predecessors. 346 LiveInterval &LI = LIS.getInterval(Reg); 347 MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 348 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 349 PE = MBB->pred_end(); PI != PE; ++PI) { 350 VNInfo *PVNI = LI.getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot()); 351 if (PVNI) 352 WorkList.push_back(std::make_pair(Reg, PVNI)); 353 } 354 continue; 355 } 356 357 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 358 assert(MI && "Missing def"); 359 360 // Trace through sibling copies. 361 if (unsigned SrcReg = isFullCopyOf(MI, Reg)) { 362 if (isSibling(SrcReg)) { 363 LiveInterval &SrcLI = LIS.getInterval(SrcReg); 364 VNInfo *SrcVNI = SrcLI.getVNInfoAt(VNI->def.getUseIndex()); 365 assert(SrcVNI && "Copy from non-existing value"); 366 DEBUG(dbgs() << " copy of " << PrintReg(SrcReg) << ':' 367 << SrcVNI->id << '@' << SrcVNI->def << '\n'); 368 WorkList.push_back(std::make_pair(SrcReg, SrcVNI)); 369 continue; 370 } 371 } 372 373 // Track reachable reloads. 374 int FI; 375 if (Reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) { 376 DEBUG(dbgs() << " reload " << PrintReg(Reg) << ':' 377 << VNI->id << "@" << VNI->def << '\n'); 378 SVI.AllDefsAreReloads = true; 379 continue; 380 } 381 382 // We have an 'original' def. Don't record trivial cases. 383 if (VNI == UseVNI) { 384 DEBUG(dbgs() << "Not a sibling copy.\n"); 385 return MI; 386 } 387 388 // Potential remat candidate. 389 DEBUG(dbgs() << " def " << PrintReg(Reg) << ':' 390 << VNI->id << '@' << VNI->def << '\t' << *MI); 391 SVI.DefMI = MI; 392 } while (!WorkList.empty()); 393 394 if (SeenOrigPHI || SVI.DefMI) 395 SVI.AllDefsAreReloads = false; 396 397 DEBUG({ 398 if (SVI.AllDefsAreReloads) 399 dbgs() << "All defs are reloads.\n"; 400 else 401 dbgs() << "Prefer to spill " << PrintReg(SVI.SpillReg) << ':' 402 << SVI.SpillVNI->id << '@' << SVI.SpillVNI->def << '\n'; 403 }); 404 SibValues.insert(std::make_pair(UseVNI, SVI)); 405 return SVI.DefMI; 406} 407 408/// analyzeSiblingValues - Trace values defined by sibling copies back to 409/// something that isn't a sibling copy. 410/// 411/// Keep track of values that may be rematerializable. 412void InlineSpiller::analyzeSiblingValues() { 413 SibValues.clear(); 414 415 // No siblings at all? 416 if (Edit->getReg() == Original) 417 return; 418 419 LiveInterval &OrigLI = LIS.getInterval(Original); 420 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 421 unsigned Reg = RegsToSpill[i]; 422 LiveInterval &LI = LIS.getInterval(Reg); 423 for (LiveInterval::const_vni_iterator VI = LI.vni_begin(), 424 VE = LI.vni_end(); VI != VE; ++VI) { 425 VNInfo *VNI = *VI; 426 if (VNI->isUnused()) 427 continue; 428 MachineInstr *DefMI = 0; 429 // Check possible sibling copies. 430 if (VNI->isPHIDef() || VNI->getCopy()) { 431 VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def); 432 if (OrigVNI->def != VNI->def) 433 DefMI = traceSiblingValue(Reg, VNI, OrigVNI); 434 } 435 if (!DefMI && !VNI->isPHIDef()) 436 DefMI = LIS.getInstructionFromIndex(VNI->def); 437 if (DefMI && Edit->checkRematerializable(VNI, DefMI, TII, AA)) { 438 DEBUG(dbgs() << "Value " << PrintReg(Reg) << ':' << VNI->id << '@' 439 << VNI->def << " may remat from " << *DefMI); 440 } 441 } 442 } 443} 444 445/// hoistSpill - Given a sibling copy that defines a value to be spilled, insert 446/// a spill at a better location. 447bool InlineSpiller::hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI) { 448 SlotIndex Idx = LIS.getInstructionIndex(CopyMI); 449 VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getDefIndex()); 450 assert(VNI && VNI->def == Idx.getDefIndex() && "Not defined by copy"); 451 SibValueMap::iterator I = SibValues.find(VNI); 452 if (I == SibValues.end()) 453 return false; 454 455 const SibValueInfo &SVI = I->second; 456 457 // Let the normal folding code deal with the boring case. 458 if (!SVI.AllDefsAreReloads && SVI.SpillVNI == VNI) 459 return false; 460 461 // SpillReg may have been deleted by remat and DCE. 462 if (!LIS.hasInterval(SVI.SpillReg)) { 463 DEBUG(dbgs() << "Stale interval: " << PrintReg(SVI.SpillReg) << '\n'); 464 SibValues.erase(I); 465 return false; 466 } 467 468 LiveInterval &SibLI = LIS.getInterval(SVI.SpillReg); 469 if (!SibLI.containsValue(SVI.SpillVNI)) { 470 DEBUG(dbgs() << "Stale value: " << PrintReg(SVI.SpillReg) << '\n'); 471 SibValues.erase(I); 472 return false; 473 } 474 475 // Conservatively extend the stack slot range to the range of the original 476 // value. We may be able to do better with stack slot coloring by being more 477 // careful here. 478 assert(StackInt && "No stack slot assigned yet."); 479 LiveInterval &OrigLI = LIS.getInterval(Original); 480 VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx); 481 StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0)); 482 DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": " 483 << *StackInt << '\n'); 484 485 // Already spilled everywhere. 486 if (SVI.AllDefsAreReloads) { 487 ++NumOmitReloadSpill; 488 return true; 489 } 490 // We are going to spill SVI.SpillVNI immediately after its def, so clear out 491 // any later spills of the same value. 492 eliminateRedundantSpills(SibLI, SVI.SpillVNI); 493 494 MachineBasicBlock *MBB = LIS.getMBBFromIndex(SVI.SpillVNI->def); 495 MachineBasicBlock::iterator MII; 496 if (SVI.SpillVNI->isPHIDef()) 497 MII = MBB->SkipPHIsAndLabels(MBB->begin()); 498 else { 499 MachineInstr *DefMI = LIS.getInstructionFromIndex(SVI.SpillVNI->def); 500 assert(DefMI && "Defining instruction disappeared"); 501 MII = DefMI; 502 ++MII; 503 } 504 // Insert spill without kill flag immediately after def. 505 TII.storeRegToStackSlot(*MBB, MII, SVI.SpillReg, false, StackSlot, 506 MRI.getRegClass(SVI.SpillReg), &TRI); 507 --MII; // Point to store instruction. 508 LIS.InsertMachineInstrInMaps(MII); 509 VRM.addSpillSlotUse(StackSlot, MII); 510 DEBUG(dbgs() << "\thoisted: " << SVI.SpillVNI->def << '\t' << *MII); 511 512 if (MBB == CopyMI->getParent()) 513 ++NumHoistLocal; 514 else 515 ++NumHoistGlobal; 516 return true; 517} 518 519/// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any 520/// redundant spills of this value in SLI.reg and sibling copies. 521void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) { 522 assert(VNI && "Missing value"); 523 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList; 524 WorkList.push_back(std::make_pair(&SLI, VNI)); 525 assert(StackInt && "No stack slot assigned yet."); 526 527 do { 528 LiveInterval *LI; 529 tie(LI, VNI) = WorkList.pop_back_val(); 530 unsigned Reg = LI->reg; 531 DEBUG(dbgs() << "Checking redundant spills for " 532 << VNI->id << '@' << VNI->def << " in " << *LI << '\n'); 533 534 // Regs to spill are taken care of. 535 if (isRegToSpill(Reg)) 536 continue; 537 538 // Add all of VNI's live range to StackInt. 539 StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0)); 540 DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n'); 541 542 // Find all spills and copies of VNI. 543 for (MachineRegisterInfo::use_nodbg_iterator UI = MRI.use_nodbg_begin(Reg); 544 MachineInstr *MI = UI.skipInstruction();) { 545 if (!MI->isCopy() && !MI->getDesc().mayStore()) 546 continue; 547 SlotIndex Idx = LIS.getInstructionIndex(MI); 548 if (LI->getVNInfoAt(Idx) != VNI) 549 continue; 550 551 // Follow sibling copies down the dominator tree. 552 if (unsigned DstReg = isFullCopyOf(MI, Reg)) { 553 if (isSibling(DstReg)) { 554 LiveInterval &DstLI = LIS.getInterval(DstReg); 555 VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getDefIndex()); 556 assert(DstVNI && "Missing defined value"); 557 assert(DstVNI->def == Idx.getDefIndex() && "Wrong copy def slot"); 558 WorkList.push_back(std::make_pair(&DstLI, DstVNI)); 559 } 560 continue; 561 } 562 563 // Erase spills. 564 int FI; 565 if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) { 566 DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << *MI); 567 // eliminateDeadDefs won't normally remove stores, so switch opcode. 568 MI->setDesc(TII.get(TargetOpcode::KILL)); 569 DeadDefs.push_back(MI); 570 ++NumRedundantSpills; 571 } 572 } 573 } while (!WorkList.empty()); 574} 575 576 577//===----------------------------------------------------------------------===// 578// Rematerialization 579//===----------------------------------------------------------------------===// 580 581/// markValueUsed - Remember that VNI failed to rematerialize, so its defining 582/// instruction cannot be eliminated. See through snippet copies 583void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) { 584 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList; 585 WorkList.push_back(std::make_pair(LI, VNI)); 586 do { 587 tie(LI, VNI) = WorkList.pop_back_val(); 588 if (!UsedValues.insert(VNI)) 589 continue; 590 591 if (VNI->isPHIDef()) { 592 MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 593 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 594 PE = MBB->pred_end(); PI != PE; ++PI) { 595 VNInfo *PVNI = LI->getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot()); 596 if (PVNI) 597 WorkList.push_back(std::make_pair(LI, PVNI)); 598 } 599 continue; 600 } 601 602 // Follow snippet copies. 603 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 604 if (!SnippetCopies.count(MI)) 605 continue; 606 LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg()); 607 assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy"); 608 VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getUseIndex()); 609 assert(SnipVNI && "Snippet undefined before copy"); 610 WorkList.push_back(std::make_pair(&SnipLI, SnipVNI)); 611 } while (!WorkList.empty()); 612} 613 614/// reMaterializeFor - Attempt to rematerialize before MI instead of reloading. 615bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, 616 MachineBasicBlock::iterator MI) { 617 SlotIndex UseIdx = LIS.getInstructionIndex(MI).getUseIndex(); 618 VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx); 619 620 if (!ParentVNI) { 621 DEBUG(dbgs() << "\tadding <undef> flags: "); 622 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 623 MachineOperand &MO = MI->getOperand(i); 624 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) 625 MO.setIsUndef(); 626 } 627 DEBUG(dbgs() << UseIdx << '\t' << *MI); 628 return true; 629 } 630 631 if (SnippetCopies.count(MI)) 632 return false; 633 634 // Use an OrigVNI from traceSiblingValue when ParentVNI is a sibling copy. 635 LiveRangeEdit::Remat RM(ParentVNI); 636 SibValueMap::const_iterator SibI = SibValues.find(ParentVNI); 637 if (SibI != SibValues.end()) 638 RM.OrigMI = SibI->second.DefMI; 639 if (!Edit->canRematerializeAt(RM, UseIdx, false, LIS)) { 640 markValueUsed(&VirtReg, ParentVNI); 641 DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI); 642 return false; 643 } 644 645 // If the instruction also writes VirtReg.reg, it had better not require the 646 // same register for uses and defs. 647 bool Reads, Writes; 648 SmallVector<unsigned, 8> Ops; 649 tie(Reads, Writes) = MI->readsWritesVirtualRegister(VirtReg.reg, &Ops); 650 if (Writes) { 651 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 652 MachineOperand &MO = MI->getOperand(Ops[i]); 653 if (MO.isUse() ? MI->isRegTiedToDefOperand(Ops[i]) : MO.getSubReg()) { 654 markValueUsed(&VirtReg, ParentVNI); 655 DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI); 656 return false; 657 } 658 } 659 } 660 661 // Before rematerializing into a register for a single instruction, try to 662 // fold a load into the instruction. That avoids allocating a new register. 663 if (RM.OrigMI->getDesc().canFoldAsLoad() && 664 foldMemoryOperand(MI, Ops, RM.OrigMI)) { 665 Edit->markRematerialized(RM.ParentVNI); 666 ++NumFoldedLoads; 667 return true; 668 } 669 670 // Alocate a new register for the remat. 671 LiveInterval &NewLI = Edit->createFrom(Original, LIS, VRM); 672 NewLI.markNotSpillable(); 673 674 // Finally we can rematerialize OrigMI before MI. 675 SlotIndex DefIdx = Edit->rematerializeAt(*MI->getParent(), MI, NewLI.reg, RM, 676 LIS, TII, TRI); 677 DEBUG(dbgs() << "\tremat: " << DefIdx << '\t' 678 << *LIS.getInstructionFromIndex(DefIdx)); 679 680 // Replace operands 681 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 682 MachineOperand &MO = MI->getOperand(Ops[i]); 683 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) { 684 MO.setReg(NewLI.reg); 685 MO.setIsKill(); 686 } 687 } 688 DEBUG(dbgs() << "\t " << UseIdx << '\t' << *MI); 689 690 VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, LIS.getVNInfoAllocator()); 691 NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI)); 692 DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); 693 ++NumRemats; 694 return true; 695} 696 697/// reMaterializeAll - Try to rematerialize as many uses as possible, 698/// and trim the live ranges after. 699void InlineSpiller::reMaterializeAll() { 700 // analyzeSiblingValues has already tested all relevant defining instructions. 701 if (!Edit->anyRematerializable(LIS, TII, AA)) 702 return; 703 704 UsedValues.clear(); 705 706 // Try to remat before all uses of snippets. 707 bool anyRemat = false; 708 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 709 unsigned Reg = RegsToSpill[i]; 710 LiveInterval &LI = LIS.getInterval(Reg); 711 for (MachineRegisterInfo::use_nodbg_iterator 712 RI = MRI.use_nodbg_begin(Reg); 713 MachineInstr *MI = RI.skipInstruction();) 714 anyRemat |= reMaterializeFor(LI, MI); 715 } 716 if (!anyRemat) 717 return; 718 719 // Remove any values that were completely rematted. 720 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 721 unsigned Reg = RegsToSpill[i]; 722 LiveInterval &LI = LIS.getInterval(Reg); 723 for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end(); 724 I != E; ++I) { 725 VNInfo *VNI = *I; 726 if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI)) 727 continue; 728 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 729 MI->addRegisterDead(Reg, &TRI); 730 if (!MI->allDefsAreDead()) 731 continue; 732 DEBUG(dbgs() << "All defs dead: " << *MI); 733 DeadDefs.push_back(MI); 734 } 735 } 736 737 // Eliminate dead code after remat. Note that some snippet copies may be 738 // deleted here. 739 if (DeadDefs.empty()) 740 return; 741 DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n"); 742 Edit->eliminateDeadDefs(DeadDefs, LIS, VRM, TII); 743 744 // Get rid of deleted and empty intervals. 745 for (unsigned i = RegsToSpill.size(); i != 0; --i) { 746 unsigned Reg = RegsToSpill[i-1]; 747 if (!LIS.hasInterval(Reg)) { 748 RegsToSpill.erase(RegsToSpill.begin() + (i - 1)); 749 continue; 750 } 751 LiveInterval &LI = LIS.getInterval(Reg); 752 if (!LI.empty()) 753 continue; 754 Edit->eraseVirtReg(Reg, LIS); 755 RegsToSpill.erase(RegsToSpill.begin() + (i - 1)); 756 } 757 DEBUG(dbgs() << RegsToSpill.size() << " registers to spill after remat.\n"); 758} 759 760 761//===----------------------------------------------------------------------===// 762// Spilling 763//===----------------------------------------------------------------------===// 764 765/// If MI is a load or store of StackSlot, it can be removed. 766bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) { 767 int FI = 0; 768 unsigned InstrReg; 769 if (!(InstrReg = TII.isLoadFromStackSlot(MI, FI)) && 770 !(InstrReg = TII.isStoreToStackSlot(MI, FI))) 771 return false; 772 773 // We have a stack access. Is it the right register and slot? 774 if (InstrReg != Reg || FI != StackSlot) 775 return false; 776 777 DEBUG(dbgs() << "Coalescing stack access: " << *MI); 778 LIS.RemoveMachineInstrFromMaps(MI); 779 MI->eraseFromParent(); 780 return true; 781} 782 783/// foldMemoryOperand - Try folding stack slot references in Ops into MI. 784/// @param MI Instruction using or defining the current register. 785/// @param Ops Operand indices from readsWritesVirtualRegister(). 786/// @param LoadMI Load instruction to use instead of stack slot when non-null. 787/// @return True on success, and MI will be erased. 788bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI, 789 const SmallVectorImpl<unsigned> &Ops, 790 MachineInstr *LoadMI) { 791 // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied 792 // operands. 793 SmallVector<unsigned, 8> FoldOps; 794 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 795 unsigned Idx = Ops[i]; 796 MachineOperand &MO = MI->getOperand(Idx); 797 if (MO.isImplicit()) 798 continue; 799 // FIXME: Teach targets to deal with subregs. 800 if (MO.getSubReg()) 801 return false; 802 // We cannot fold a load instruction into a def. 803 if (LoadMI && MO.isDef()) 804 return false; 805 // Tied use operands should not be passed to foldMemoryOperand. 806 if (!MI->isRegTiedToDefOperand(Idx)) 807 FoldOps.push_back(Idx); 808 } 809 810 MachineInstr *FoldMI = 811 LoadMI ? TII.foldMemoryOperand(MI, FoldOps, LoadMI) 812 : TII.foldMemoryOperand(MI, FoldOps, StackSlot); 813 if (!FoldMI) 814 return false; 815 LIS.ReplaceMachineInstrInMaps(MI, FoldMI); 816 if (!LoadMI) 817 VRM.addSpillSlotUse(StackSlot, FoldMI); 818 MI->eraseFromParent(); 819 DEBUG(dbgs() << "\tfolded: " << *FoldMI); 820 ++NumFolded; 821 return true; 822} 823 824/// insertReload - Insert a reload of NewLI.reg before MI. 825void InlineSpiller::insertReload(LiveInterval &NewLI, 826 SlotIndex Idx, 827 MachineBasicBlock::iterator MI) { 828 MachineBasicBlock &MBB = *MI->getParent(); 829 TII.loadRegFromStackSlot(MBB, MI, NewLI.reg, StackSlot, 830 MRI.getRegClass(NewLI.reg), &TRI); 831 --MI; // Point to load instruction. 832 SlotIndex LoadIdx = LIS.InsertMachineInstrInMaps(MI).getDefIndex(); 833 VRM.addSpillSlotUse(StackSlot, MI); 834 DEBUG(dbgs() << "\treload: " << LoadIdx << '\t' << *MI); 835 VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, 0, 836 LIS.getVNInfoAllocator()); 837 NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI)); 838 ++NumReloads; 839} 840 841/// insertSpill - Insert a spill of NewLI.reg after MI. 842void InlineSpiller::insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI, 843 SlotIndex Idx, MachineBasicBlock::iterator MI) { 844 MachineBasicBlock &MBB = *MI->getParent(); 845 TII.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, StackSlot, 846 MRI.getRegClass(NewLI.reg), &TRI); 847 --MI; // Point to store instruction. 848 SlotIndex StoreIdx = LIS.InsertMachineInstrInMaps(MI).getDefIndex(); 849 VRM.addSpillSlotUse(StackSlot, MI); 850 DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI); 851 VNInfo *StoreVNI = NewLI.getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 852 NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI)); 853 ++NumSpills; 854} 855 856/// spillAroundUses - insert spill code around each use of Reg. 857void InlineSpiller::spillAroundUses(unsigned Reg) { 858 LiveInterval &OldLI = LIS.getInterval(Reg); 859 860 // Iterate over instructions using Reg. 861 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg); 862 MachineInstr *MI = RI.skipInstruction();) { 863 864 // Debug values are not allowed to affect codegen. 865 if (MI->isDebugValue()) { 866 // Modify DBG_VALUE now that the value is in a spill slot. 867 uint64_t Offset = MI->getOperand(1).getImm(); 868 const MDNode *MDPtr = MI->getOperand(2).getMetadata(); 869 DebugLoc DL = MI->getDebugLoc(); 870 if (MachineInstr *NewDV = TII.emitFrameIndexDebugValue(MF, StackSlot, 871 Offset, MDPtr, DL)) { 872 DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); 873 MachineBasicBlock *MBB = MI->getParent(); 874 MBB->insert(MBB->erase(MI), NewDV); 875 } else { 876 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 877 MI->eraseFromParent(); 878 } 879 continue; 880 } 881 882 // Ignore copies to/from snippets. We'll delete them. 883 if (SnippetCopies.count(MI)) 884 continue; 885 886 // Stack slot accesses may coalesce away. 887 if (coalesceStackAccess(MI, Reg)) 888 continue; 889 890 // Analyze instruction. 891 bool Reads, Writes; 892 SmallVector<unsigned, 8> Ops; 893 tie(Reads, Writes) = MI->readsWritesVirtualRegister(Reg, &Ops); 894 895 // Find the slot index where this instruction reads and writes OldLI. 896 // This is usually the def slot, except for tied early clobbers. 897 SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex(); 898 if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getUseIndex())) 899 if (SlotIndex::isSameInstr(Idx, VNI->def)) 900 Idx = VNI->def; 901 902 // Check for a sibling copy. 903 unsigned SibReg = isFullCopyOf(MI, Reg); 904 if (SibReg && isSibling(SibReg)) { 905 if (Writes) { 906 // Hoist the spill of a sib-reg copy. 907 if (hoistSpill(OldLI, MI)) { 908 // This COPY is now dead, the value is already in the stack slot. 909 MI->getOperand(0).setIsDead(); 910 DeadDefs.push_back(MI); 911 continue; 912 } 913 } else { 914 // This is a reload for a sib-reg copy. Drop spills downstream. 915 LiveInterval &SibLI = LIS.getInterval(SibReg); 916 eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx)); 917 // The COPY will fold to a reload below. 918 } 919 } 920 921 // Attempt to fold memory ops. 922 if (foldMemoryOperand(MI, Ops)) 923 continue; 924 925 // Allocate interval around instruction. 926 // FIXME: Infer regclass from instruction alone. 927 LiveInterval &NewLI = Edit->createFrom(Reg, LIS, VRM); 928 NewLI.markNotSpillable(); 929 930 if (Reads) 931 insertReload(NewLI, Idx, MI); 932 933 // Rewrite instruction operands. 934 bool hasLiveDef = false; 935 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 936 MachineOperand &MO = MI->getOperand(Ops[i]); 937 MO.setReg(NewLI.reg); 938 if (MO.isUse()) { 939 if (!MI->isRegTiedToDefOperand(Ops[i])) 940 MO.setIsKill(); 941 } else { 942 if (!MO.isDead()) 943 hasLiveDef = true; 944 } 945 } 946 DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI); 947 948 // FIXME: Use a second vreg if instruction has no tied ops. 949 if (Writes && hasLiveDef) 950 insertSpill(NewLI, OldLI, Idx, MI); 951 952 DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); 953 } 954} 955 956/// spillAll - Spill all registers remaining after rematerialization. 957void InlineSpiller::spillAll() { 958 // Update LiveStacks now that we are committed to spilling. 959 if (StackSlot == VirtRegMap::NO_STACK_SLOT) { 960 StackSlot = VRM.assignVirt2StackSlot(Original); 961 StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original)); 962 StackInt->getNextValue(SlotIndex(), 0, LSS.getVNInfoAllocator()); 963 } else 964 StackInt = &LSS.getInterval(StackSlot); 965 966 if (Original != Edit->getReg()) 967 VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot); 968 969 assert(StackInt->getNumValNums() == 1 && "Bad stack interval values"); 970 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) 971 StackInt->MergeRangesInAsValue(LIS.getInterval(RegsToSpill[i]), 972 StackInt->getValNumInfo(0)); 973 DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n'); 974 975 // Spill around uses of all RegsToSpill. 976 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) 977 spillAroundUses(RegsToSpill[i]); 978 979 // Hoisted spills may cause dead code. 980 if (!DeadDefs.empty()) { 981 DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n"); 982 Edit->eliminateDeadDefs(DeadDefs, LIS, VRM, TII); 983 } 984 985 // Finally delete the SnippetCopies. 986 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()); 987 MachineInstr *MI = RI.skipInstruction();) { 988 assert(SnippetCopies.count(MI) && "Remaining use wasn't a snippet copy"); 989 // FIXME: Do this with a LiveRangeEdit callback. 990 VRM.RemoveMachineInstrFromMaps(MI); 991 LIS.RemoveMachineInstrFromMaps(MI); 992 MI->eraseFromParent(); 993 } 994 995 // Delete all spilled registers. 996 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) 997 Edit->eraseVirtReg(RegsToSpill[i], LIS); 998} 999 1000void InlineSpiller::spill(LiveRangeEdit &edit) { 1001 ++NumSpilledRanges; 1002 Edit = &edit; 1003 assert(!TargetRegisterInfo::isStackSlot(edit.getReg()) 1004 && "Trying to spill a stack slot."); 1005 // Share a stack slot among all descendants of Original. 1006 Original = VRM.getOriginal(edit.getReg()); 1007 StackSlot = VRM.getStackSlot(Original); 1008 StackInt = 0; 1009 1010 DEBUG(dbgs() << "Inline spilling " 1011 << MRI.getRegClass(edit.getReg())->getName() 1012 << ':' << edit.getParent() << "\nFrom original " 1013 << LIS.getInterval(Original) << '\n'); 1014 assert(edit.getParent().isSpillable() && 1015 "Attempting to spill already spilled value."); 1016 assert(DeadDefs.empty() && "Previous spill didn't remove dead defs"); 1017 1018 collectRegsToSpill(); 1019 analyzeSiblingValues(); 1020 reMaterializeAll(); 1021 1022 // Remat may handle everything. 1023 if (!RegsToSpill.empty()) 1024 spillAll(); 1025 1026 Edit->calculateRegClassAndHint(MF, LIS, Loops); 1027} 1028