SplitKit.cpp revision b5a457c4cbc71db6ae313ef1bf8eadac65767ab0
1//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 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// This file contains the SplitAnalysis class as well as mutator functions for 11// live range splitting. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "regalloc" 16#include "SplitKit.h" 17#include "LiveRangeEdit.h" 18#include "VirtRegMap.h" 19#include "llvm/ADT/Statistic.h" 20#include "llvm/CodeGen/LiveIntervalAnalysis.h" 21#include "llvm/CodeGen/MachineDominators.h" 22#include "llvm/CodeGen/MachineInstrBuilder.h" 23#include "llvm/CodeGen/MachineRegisterInfo.h" 24#include "llvm/Support/Debug.h" 25#include "llvm/Support/raw_ostream.h" 26#include "llvm/Target/TargetInstrInfo.h" 27#include "llvm/Target/TargetMachine.h" 28 29using namespace llvm; 30 31STATISTIC(NumFinished, "Number of splits finished"); 32STATISTIC(NumSimple, "Number of splits that were simple"); 33STATISTIC(NumCopies, "Number of copies inserted for splitting"); 34STATISTIC(NumRemats, "Number of rematerialized defs for splitting"); 35STATISTIC(NumRepairs, "Number of invalid live ranges repaired"); 36 37//===----------------------------------------------------------------------===// 38// Split Analysis 39//===----------------------------------------------------------------------===// 40 41SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 42 const LiveIntervals &lis, 43 const MachineLoopInfo &mli) 44 : MF(vrm.getMachineFunction()), 45 VRM(vrm), 46 LIS(lis), 47 Loops(mli), 48 TII(*MF.getTarget().getInstrInfo()), 49 CurLI(0), 50 LastSplitPoint(MF.getNumBlockIDs()) {} 51 52void SplitAnalysis::clear() { 53 UseSlots.clear(); 54 UseBlocks.clear(); 55 ThroughBlocks.clear(); 56 CurLI = 0; 57 DidRepairRange = false; 58} 59 60SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { 61 const MachineBasicBlock *MBB = MF.getBlockNumbered(Num); 62 const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor(); 63 std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num]; 64 65 // Compute split points on the first call. The pair is independent of the 66 // current live interval. 67 if (!LSP.first.isValid()) { 68 MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator(); 69 if (FirstTerm == MBB->end()) 70 LSP.first = LIS.getMBBEndIdx(MBB); 71 else 72 LSP.first = LIS.getInstructionIndex(FirstTerm); 73 74 // If there is a landing pad successor, also find the call instruction. 75 if (!LPad) 76 return LSP.first; 77 // There may not be a call instruction (?) in which case we ignore LPad. 78 LSP.second = LSP.first; 79 for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin(); 80 I != E;) { 81 --I; 82 if (I->getDesc().isCall()) { 83 LSP.second = LIS.getInstructionIndex(I); 84 break; 85 } 86 } 87 } 88 89 // If CurLI is live into a landing pad successor, move the last split point 90 // back to the call that may throw. 91 if (LPad && LSP.second.isValid() && LIS.isLiveInToMBB(*CurLI, LPad)) 92 return LSP.second; 93 else 94 return LSP.first; 95} 96 97/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 98void SplitAnalysis::analyzeUses() { 99 assert(UseSlots.empty() && "Call clear first"); 100 101 // First get all the defs from the interval values. This provides the correct 102 // slots for early clobbers. 103 for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(), 104 E = CurLI->vni_end(); I != E; ++I) 105 if (!(*I)->isPHIDef() && !(*I)->isUnused()) 106 UseSlots.push_back((*I)->def); 107 108 // Get use slots form the use-def chain. 109 const MachineRegisterInfo &MRI = MF.getRegInfo(); 110 for (MachineRegisterInfo::use_nodbg_iterator 111 I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E; 112 ++I) 113 if (!I.getOperand().isUndef()) 114 UseSlots.push_back(LIS.getInstructionIndex(&*I).getDefIndex()); 115 116 array_pod_sort(UseSlots.begin(), UseSlots.end()); 117 118 // Remove duplicates, keeping the smaller slot for each instruction. 119 // That is what we want for early clobbers. 120 UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), 121 SlotIndex::isSameInstr), 122 UseSlots.end()); 123 124 // Compute per-live block info. 125 if (!calcLiveBlockInfo()) { 126 // FIXME: calcLiveBlockInfo found inconsistencies in the live range. 127 // I am looking at you, RegisterCoalescer! 128 DidRepairRange = true; 129 ++NumRepairs; 130 DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); 131 const_cast<LiveIntervals&>(LIS) 132 .shrinkToUses(const_cast<LiveInterval*>(CurLI)); 133 UseBlocks.clear(); 134 ThroughBlocks.clear(); 135 bool fixed = calcLiveBlockInfo(); 136 (void)fixed; 137 assert(fixed && "Couldn't fix broken live interval"); 138 } 139 140 DEBUG(dbgs() << "Analyze counted " 141 << UseSlots.size() << " instrs in " 142 << UseBlocks.size() << " blocks, through " 143 << NumThroughBlocks << " blocks.\n"); 144} 145 146/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 147/// where CurLI is live. 148bool SplitAnalysis::calcLiveBlockInfo() { 149 ThroughBlocks.resize(MF.getNumBlockIDs()); 150 NumThroughBlocks = NumGapBlocks = 0; 151 if (CurLI->empty()) 152 return true; 153 154 LiveInterval::const_iterator LVI = CurLI->begin(); 155 LiveInterval::const_iterator LVE = CurLI->end(); 156 157 SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 158 UseI = UseSlots.begin(); 159 UseE = UseSlots.end(); 160 161 // Loop over basic blocks where CurLI is live. 162 MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 163 for (;;) { 164 BlockInfo BI; 165 BI.MBB = MFI; 166 SlotIndex Start, Stop; 167 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 168 169 // If the block contains no uses, the range must be live through. At one 170 // point, RegisterCoalescer could create dangling ranges that ended 171 // mid-block. 172 if (UseI == UseE || *UseI >= Stop) { 173 ++NumThroughBlocks; 174 ThroughBlocks.set(BI.MBB->getNumber()); 175 // The range shouldn't end mid-block if there are no uses. This shouldn't 176 // happen. 177 if (LVI->end < Stop) 178 return false; 179 } else { 180 // This block has uses. Find the first and last uses in the block. 181 BI.FirstInstr = *UseI; 182 assert(BI.FirstInstr >= Start); 183 do ++UseI; 184 while (UseI != UseE && *UseI < Stop); 185 BI.LastInstr = UseI[-1]; 186 assert(BI.LastInstr < Stop); 187 188 // LVI is the first live segment overlapping MBB. 189 BI.LiveIn = LVI->start <= Start; 190 191 // When not live in, the first use should be a def. 192 if (!BI.LiveIn) { 193 assert(LVI->start == LVI->valno->def && "Dangling LiveRange start"); 194 assert(LVI->start == BI.FirstInstr && "First instr should be a def"); 195 BI.FirstDef = BI.FirstInstr; 196 } 197 198 // Look for gaps in the live range. 199 BI.LiveOut = true; 200 while (LVI->end < Stop) { 201 SlotIndex LastStop = LVI->end; 202 if (++LVI == LVE || LVI->start >= Stop) { 203 BI.LiveOut = false; 204 BI.LastInstr = LastStop; 205 break; 206 } 207 208 if (LastStop < LVI->start) { 209 // There is a gap in the live range. Create duplicate entries for the 210 // live-in snippet and the live-out snippet. 211 ++NumGapBlocks; 212 213 // Push the Live-in part. 214 BI.LiveOut = false; 215 UseBlocks.push_back(BI); 216 UseBlocks.back().LastInstr = LastStop; 217 218 // Set up BI for the live-out part. 219 BI.LiveIn = false; 220 BI.LiveOut = true; 221 BI.FirstInstr = BI.FirstDef = LVI->start; 222 } 223 224 // A LiveRange that starts in the middle of the block must be a def. 225 assert(LVI->start == LVI->valno->def && "Dangling LiveRange start"); 226 if (!BI.FirstDef) 227 BI.FirstDef = LVI->start; 228 } 229 230 UseBlocks.push_back(BI); 231 232 // LVI is now at LVE or LVI->end >= Stop. 233 if (LVI == LVE) 234 break; 235 } 236 237 // Live segment ends exactly at Stop. Move to the next segment. 238 if (LVI->end == Stop && ++LVI == LVE) 239 break; 240 241 // Pick the next basic block. 242 if (LVI->start < Stop) 243 ++MFI; 244 else 245 MFI = LIS.getMBBFromIndex(LVI->start); 246 } 247 248 assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count"); 249 return true; 250} 251 252unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { 253 if (cli->empty()) 254 return 0; 255 LiveInterval *li = const_cast<LiveInterval*>(cli); 256 LiveInterval::iterator LVI = li->begin(); 257 LiveInterval::iterator LVE = li->end(); 258 unsigned Count = 0; 259 260 // Loop over basic blocks where li is live. 261 MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start); 262 SlotIndex Stop = LIS.getMBBEndIdx(MFI); 263 for (;;) { 264 ++Count; 265 LVI = li->advanceTo(LVI, Stop); 266 if (LVI == LVE) 267 return Count; 268 do { 269 ++MFI; 270 Stop = LIS.getMBBEndIdx(MFI); 271 } while (Stop <= LVI->start); 272 } 273} 274 275bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 276 unsigned OrigReg = VRM.getOriginal(CurLI->reg); 277 const LiveInterval &Orig = LIS.getInterval(OrigReg); 278 assert(!Orig.empty() && "Splitting empty interval?"); 279 LiveInterval::const_iterator I = Orig.find(Idx); 280 281 // Range containing Idx should begin at Idx. 282 if (I != Orig.end() && I->start <= Idx) 283 return I->start == Idx; 284 285 // Range does not contain Idx, previous must end at Idx. 286 return I != Orig.begin() && (--I)->end == Idx; 287} 288 289void SplitAnalysis::analyze(const LiveInterval *li) { 290 clear(); 291 CurLI = li; 292 analyzeUses(); 293} 294 295 296//===----------------------------------------------------------------------===// 297// Split Editor 298//===----------------------------------------------------------------------===// 299 300/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 301SplitEditor::SplitEditor(SplitAnalysis &sa, 302 LiveIntervals &lis, 303 VirtRegMap &vrm, 304 MachineDominatorTree &mdt) 305 : SA(sa), LIS(lis), VRM(vrm), 306 MRI(vrm.getMachineFunction().getRegInfo()), 307 MDT(mdt), 308 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 309 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 310 Edit(0), 311 OpenIdx(0), 312 SpillMode(SM_Partition), 313 RegAssign(Allocator) 314{} 315 316void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { 317 Edit = &LRE; 318 SpillMode = SM; 319 OpenIdx = 0; 320 RegAssign.clear(); 321 Values.clear(); 322 LRCalc.reset(&VRM.getMachineFunction()); 323 324 // We don't need an AliasAnalysis since we will only be performing 325 // cheap-as-a-copy remats anyway. 326 Edit->anyRematerializable(LIS, TII, 0); 327} 328 329void SplitEditor::dump() const { 330 if (RegAssign.empty()) { 331 dbgs() << " empty\n"; 332 return; 333 } 334 335 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 336 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 337 dbgs() << '\n'; 338} 339 340VNInfo *SplitEditor::defValue(unsigned RegIdx, 341 const VNInfo *ParentVNI, 342 SlotIndex Idx) { 343 assert(ParentVNI && "Mapping NULL value"); 344 assert(Idx.isValid() && "Invalid SlotIndex"); 345 assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 346 LiveInterval *LI = Edit->get(RegIdx); 347 348 // Create a new value. 349 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 350 351 // Use insert for lookup, so we can add missing values with a second lookup. 352 std::pair<ValueMap::iterator, bool> InsP = 353 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 354 355 // This was the first time (RegIdx, ParentVNI) was mapped. 356 // Keep it as a simple def without any liveness. 357 if (InsP.second) 358 return VNI; 359 360 // If the previous value was a simple mapping, add liveness for it now. 361 if (VNInfo *OldVNI = InsP.first->second) { 362 SlotIndex Def = OldVNI->def; 363 LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 364 // No longer a simple mapping. 365 InsP.first->second = 0; 366 } 367 368 // This is a complex mapping, add liveness for VNI 369 SlotIndex Def = VNI->def; 370 LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 371 372 return VNI; 373} 374 375void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 376 assert(ParentVNI && "Mapping NULL value"); 377 VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 378 379 // ParentVNI was either unmapped or already complex mapped. Either way. 380 if (!VNI) 381 return; 382 383 // This was previously a single mapping. Make sure the old def is represented 384 // by a trivial live range. 385 SlotIndex Def = VNI->def; 386 Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 387 VNI = 0; 388} 389 390// extendRange - Extend the live range to reach Idx. 391// Potentially create phi-def values. 392void SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 393 LRCalc.extend(Edit->get(RegIdx), Idx.getNextSlot(), 394 LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); 395} 396 397VNInfo *SplitEditor::defFromParent(unsigned RegIdx, 398 VNInfo *ParentVNI, 399 SlotIndex UseIdx, 400 MachineBasicBlock &MBB, 401 MachineBasicBlock::iterator I) { 402 MachineInstr *CopyMI = 0; 403 SlotIndex Def; 404 LiveInterval *LI = Edit->get(RegIdx); 405 406 // We may be trying to avoid interference that ends at a deleted instruction, 407 // so always begin RegIdx 0 early and all others late. 408 bool Late = RegIdx != 0; 409 410 // Attempt cheap-as-a-copy rematerialization. 411 LiveRangeEdit::Remat RM(ParentVNI); 412 if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 413 Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late); 414 ++NumRemats; 415 } else { 416 // Can't remat, just insert a copy from parent. 417 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 418 .addReg(Edit->getReg()); 419 Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) 420 .getDefIndex(); 421 ++NumCopies; 422 } 423 424 // Define the value in Reg. 425 VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 426 VNI->setCopy(CopyMI); 427 return VNI; 428} 429 430/// Create a new virtual register and live interval. 431unsigned SplitEditor::openIntv() { 432 // Create the complement as index 0. 433 if (Edit->empty()) 434 Edit->create(LIS, VRM); 435 436 // Create the open interval. 437 OpenIdx = Edit->size(); 438 Edit->create(LIS, VRM); 439 return OpenIdx; 440} 441 442void SplitEditor::selectIntv(unsigned Idx) { 443 assert(Idx != 0 && "Cannot select the complement interval"); 444 assert(Idx < Edit->size() && "Can only select previously opened interval"); 445 DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); 446 OpenIdx = Idx; 447} 448 449SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 450 assert(OpenIdx && "openIntv not called before enterIntvBefore"); 451 DEBUG(dbgs() << " enterIntvBefore " << Idx); 452 Idx = Idx.getBaseIndex(); 453 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 454 if (!ParentVNI) { 455 DEBUG(dbgs() << ": not live\n"); 456 return Idx; 457 } 458 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 459 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 460 assert(MI && "enterIntvBefore called with invalid index"); 461 462 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 463 return VNI->def; 464} 465 466SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { 467 assert(OpenIdx && "openIntv not called before enterIntvAfter"); 468 DEBUG(dbgs() << " enterIntvAfter " << Idx); 469 Idx = Idx.getBoundaryIndex(); 470 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 471 if (!ParentVNI) { 472 DEBUG(dbgs() << ": not live\n"); 473 return Idx; 474 } 475 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 476 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 477 assert(MI && "enterIntvAfter called with invalid index"); 478 479 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), 480 llvm::next(MachineBasicBlock::iterator(MI))); 481 return VNI->def; 482} 483 484SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 485 assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 486 SlotIndex End = LIS.getMBBEndIdx(&MBB); 487 SlotIndex Last = End.getPrevSlot(); 488 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 489 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 490 if (!ParentVNI) { 491 DEBUG(dbgs() << ": not live\n"); 492 return End; 493 } 494 DEBUG(dbgs() << ": valno " << ParentVNI->id); 495 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 496 LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 497 RegAssign.insert(VNI->def, End, OpenIdx); 498 DEBUG(dump()); 499 return VNI->def; 500} 501 502/// useIntv - indicate that all instructions in MBB should use OpenLI. 503void SplitEditor::useIntv(const MachineBasicBlock &MBB) { 504 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 505} 506 507void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 508 assert(OpenIdx && "openIntv not called before useIntv"); 509 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 510 RegAssign.insert(Start, End, OpenIdx); 511 DEBUG(dump()); 512} 513 514SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 515 assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 516 DEBUG(dbgs() << " leaveIntvAfter " << Idx); 517 518 // The interval must be live beyond the instruction at Idx. 519 Idx = Idx.getBoundaryIndex(); 520 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 521 if (!ParentVNI) { 522 DEBUG(dbgs() << ": not live\n"); 523 return Idx.getNextSlot(); 524 } 525 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 526 527 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 528 assert(MI && "No instruction at index"); 529 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 530 llvm::next(MachineBasicBlock::iterator(MI))); 531 return VNI->def; 532} 533 534SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 535 assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 536 DEBUG(dbgs() << " leaveIntvBefore " << Idx); 537 538 // The interval must be live into the instruction at Idx. 539 Idx = Idx.getBaseIndex(); 540 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 541 if (!ParentVNI) { 542 DEBUG(dbgs() << ": not live\n"); 543 return Idx.getNextSlot(); 544 } 545 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 546 547 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 548 assert(MI && "No instruction at index"); 549 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 550 return VNI->def; 551} 552 553SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 554 assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 555 SlotIndex Start = LIS.getMBBStartIdx(&MBB); 556 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 557 558 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 559 if (!ParentVNI) { 560 DEBUG(dbgs() << ": not live\n"); 561 return Start; 562 } 563 564 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 565 MBB.SkipPHIsAndLabels(MBB.begin())); 566 RegAssign.insert(Start, VNI->def, OpenIdx); 567 DEBUG(dump()); 568 return VNI->def; 569} 570 571void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 572 assert(OpenIdx && "openIntv not called before overlapIntv"); 573 const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 574 assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 575 "Parent changes value in extended range"); 576 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 577 "Range cannot span basic blocks"); 578 579 // The complement interval will be extended as needed by extendRange(). 580 if (ParentVNI) 581 markComplexMapped(0, ParentVNI); 582 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 583 RegAssign.insert(Start, End, OpenIdx); 584 DEBUG(dump()); 585} 586 587/// transferValues - Transfer all possible values to the new live ranges. 588/// Values that were rematerialized are left alone, they need extendRange(). 589bool SplitEditor::transferValues() { 590 bool Skipped = false; 591 RegAssignMap::const_iterator AssignI = RegAssign.begin(); 592 for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 593 ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 594 DEBUG(dbgs() << " blit " << *ParentI << ':'); 595 VNInfo *ParentVNI = ParentI->valno; 596 // RegAssign has holes where RegIdx 0 should be used. 597 SlotIndex Start = ParentI->start; 598 AssignI.advanceTo(Start); 599 do { 600 unsigned RegIdx; 601 SlotIndex End = ParentI->end; 602 if (!AssignI.valid()) { 603 RegIdx = 0; 604 } else if (AssignI.start() <= Start) { 605 RegIdx = AssignI.value(); 606 if (AssignI.stop() < End) { 607 End = AssignI.stop(); 608 ++AssignI; 609 } 610 } else { 611 RegIdx = 0; 612 End = std::min(End, AssignI.start()); 613 } 614 615 // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 616 DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 617 LiveInterval *LI = Edit->get(RegIdx); 618 619 // Check for a simply defined value that can be blitted directly. 620 if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 621 DEBUG(dbgs() << ':' << VNI->id); 622 LI->addRange(LiveRange(Start, End, VNI)); 623 Start = End; 624 continue; 625 } 626 627 // Skip rematerialized values, we need to use extendRange() and 628 // extendPHIKillRanges() to completely recompute the live ranges. 629 if (Edit->didRematerialize(ParentVNI)) { 630 DEBUG(dbgs() << "(remat)"); 631 Skipped = true; 632 Start = End; 633 continue; 634 } 635 636 // This value has multiple defs in RegIdx, but it wasn't rematerialized, 637 // so the live range is accurate. Add live-in blocks in [Start;End) to the 638 // LiveInBlocks. 639 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 640 SlotIndex BlockStart, BlockEnd; 641 tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 642 643 // The first block may be live-in, or it may have its own def. 644 if (Start != BlockStart) { 645 VNInfo *VNI = LI->extendInBlock(BlockStart, 646 std::min(BlockEnd, End).getPrevSlot()); 647 assert(VNI && "Missing def for complex mapped value"); 648 DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 649 // MBB has its own def. Is it also live-out? 650 if (BlockEnd <= End) 651 LRCalc.setLiveOutValue(MBB, VNI); 652 653 // Skip to the next block for live-in. 654 ++MBB; 655 BlockStart = BlockEnd; 656 } 657 658 // Handle the live-in blocks covered by [Start;End). 659 assert(Start <= BlockStart && "Expected live-in block"); 660 while (BlockStart < End) { 661 DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 662 BlockEnd = LIS.getMBBEndIdx(MBB); 663 if (BlockStart == ParentVNI->def) { 664 // This block has the def of a parent PHI, so it isn't live-in. 665 assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 666 VNInfo *VNI = LI->extendInBlock(BlockStart, 667 std::min(BlockEnd, End).getPrevSlot()); 668 assert(VNI && "Missing def for complex mapped parent PHI"); 669 if (End >= BlockEnd) 670 LRCalc.setLiveOutValue(MBB, VNI); // Live-out as well. 671 } else { 672 // This block needs a live-in value. The last block covered may not 673 // be live-out. 674 if (End < BlockEnd) 675 LRCalc.addLiveInBlock(LI, MDT[MBB], End); 676 else { 677 // Live-through, and we don't know the value. 678 LRCalc.addLiveInBlock(LI, MDT[MBB]); 679 LRCalc.setLiveOutValue(MBB, 0); 680 } 681 } 682 BlockStart = BlockEnd; 683 ++MBB; 684 } 685 Start = End; 686 } while (Start != ParentI->end); 687 DEBUG(dbgs() << '\n'); 688 } 689 690 LRCalc.calculateValues(LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); 691 692 return Skipped; 693} 694 695void SplitEditor::extendPHIKillRanges() { 696 // Extend live ranges to be live-out for successor PHI values. 697 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 698 E = Edit->getParent().vni_end(); I != E; ++I) { 699 const VNInfo *PHIVNI = *I; 700 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 701 continue; 702 unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 703 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 704 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 705 PE = MBB->pred_end(); PI != PE; ++PI) { 706 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 707 // The predecessor may not have a live-out value. That is OK, like an 708 // undef PHI operand. 709 if (Edit->getParent().liveAt(End)) { 710 assert(RegAssign.lookup(End) == RegIdx && 711 "Different register assignment in phi predecessor"); 712 extendRange(RegIdx, End); 713 } 714 } 715 } 716} 717 718/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 719void SplitEditor::rewriteAssigned(bool ExtendRanges) { 720 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 721 RE = MRI.reg_end(); RI != RE;) { 722 MachineOperand &MO = RI.getOperand(); 723 MachineInstr *MI = MO.getParent(); 724 ++RI; 725 // LiveDebugVariables should have handled all DBG_VALUE instructions. 726 if (MI->isDebugValue()) { 727 DEBUG(dbgs() << "Zapping " << *MI); 728 MO.setReg(0); 729 continue; 730 } 731 732 // <undef> operands don't really read the register, so it doesn't matter 733 // which register we choose. When the use operand is tied to a def, we must 734 // use the same register as the def, so just do that always. 735 SlotIndex Idx = LIS.getInstructionIndex(MI); 736 if (MO.isDef() || MO.isUndef()) 737 Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex(); 738 739 // Rewrite to the mapped register at Idx. 740 unsigned RegIdx = RegAssign.lookup(Idx); 741 MO.setReg(Edit->get(RegIdx)->reg); 742 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 743 << Idx << ':' << RegIdx << '\t' << *MI); 744 745 // Extend liveness to Idx if the instruction reads reg. 746 if (!ExtendRanges || MO.isUndef()) 747 continue; 748 749 // Skip instructions that don't read Reg. 750 if (MO.isDef()) { 751 if (!MO.getSubReg() && !MO.isEarlyClobber()) 752 continue; 753 // We may wan't to extend a live range for a partial redef, or for a use 754 // tied to an early clobber. 755 Idx = Idx.getPrevSlot(); 756 if (!Edit->getParent().liveAt(Idx)) 757 continue; 758 } else 759 Idx = Idx.getUseIndex(); 760 761 extendRange(RegIdx, Idx); 762 } 763} 764 765void SplitEditor::deleteRematVictims() { 766 SmallVector<MachineInstr*, 8> Dead; 767 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 768 LiveInterval *LI = *I; 769 for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 770 LII != LIE; ++LII) { 771 // Dead defs end at the store slot. 772 if (LII->end != LII->valno->def.getNextSlot()) 773 continue; 774 MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 775 assert(MI && "Missing instruction for dead def"); 776 MI->addRegisterDead(LI->reg, &TRI); 777 778 if (!MI->allDefsAreDead()) 779 continue; 780 781 DEBUG(dbgs() << "All defs dead: " << *MI); 782 Dead.push_back(MI); 783 } 784 } 785 786 if (Dead.empty()) 787 return; 788 789 Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); 790} 791 792void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 793 ++NumFinished; 794 795 // At this point, the live intervals in Edit contain VNInfos corresponding to 796 // the inserted copies. 797 798 // Add the original defs from the parent interval. 799 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 800 E = Edit->getParent().vni_end(); I != E; ++I) { 801 const VNInfo *ParentVNI = *I; 802 if (ParentVNI->isUnused()) 803 continue; 804 unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 805 VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 806 VNI->setIsPHIDef(ParentVNI->isPHIDef()); 807 VNI->setCopy(ParentVNI->getCopy()); 808 809 // Mark rematted values as complex everywhere to force liveness computation. 810 // The new live ranges may be truncated. 811 if (Edit->didRematerialize(ParentVNI)) 812 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 813 markComplexMapped(i, ParentVNI); 814 } 815 816 // Transfer the simply mapped values, check if any are skipped. 817 bool Skipped = transferValues(); 818 if (Skipped) 819 extendPHIKillRanges(); 820 else 821 ++NumSimple; 822 823 // Rewrite virtual registers, possibly extending ranges. 824 rewriteAssigned(Skipped); 825 826 // Delete defs that were rematted everywhere. 827 if (Skipped) 828 deleteRematVictims(); 829 830 // Get rid of unused values and set phi-kill flags. 831 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 832 (*I)->RenumberValues(LIS); 833 834 // Provide a reverse mapping from original indices to Edit ranges. 835 if (LRMap) { 836 LRMap->clear(); 837 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 838 LRMap->push_back(i); 839 } 840 841 // Now check if any registers were separated into multiple components. 842 ConnectedVNInfoEqClasses ConEQ(LIS); 843 for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 844 // Don't use iterators, they are invalidated by create() below. 845 LiveInterval *li = Edit->get(i); 846 unsigned NumComp = ConEQ.Classify(li); 847 if (NumComp <= 1) 848 continue; 849 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 850 SmallVector<LiveInterval*, 8> dups; 851 dups.push_back(li); 852 for (unsigned j = 1; j != NumComp; ++j) 853 dups.push_back(&Edit->create(LIS, VRM)); 854 ConEQ.Distribute(&dups[0], MRI); 855 // The new intervals all map back to i. 856 if (LRMap) 857 LRMap->resize(Edit->size(), i); 858 } 859 860 // Calculate spill weight and allocation hints for new intervals. 861 Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops); 862 863 assert(!LRMap || LRMap->size() == Edit->size()); 864} 865 866 867//===----------------------------------------------------------------------===// 868// Single Block Splitting 869//===----------------------------------------------------------------------===// 870 871bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, 872 bool SingleInstrs) const { 873 // Always split for multiple instructions. 874 if (!BI.isOneInstr()) 875 return true; 876 // Don't split for single instructions unless explicitly requested. 877 if (!SingleInstrs) 878 return false; 879 // Splitting a live-through range always makes progress. 880 if (BI.LiveIn && BI.LiveOut) 881 return true; 882 // No point in isolating a copy. It has no register class constraints. 883 if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike()) 884 return false; 885 // Finally, don't isolate an end point that was created by earlier splits. 886 return isOriginalEndpoint(BI.FirstInstr); 887} 888 889void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 890 openIntv(); 891 SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 892 SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr, 893 LastSplitPoint)); 894 if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { 895 useIntv(SegStart, leaveIntvAfter(BI.LastInstr)); 896 } else { 897 // The last use is after the last valid split point. 898 SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 899 useIntv(SegStart, SegStop); 900 overlapIntv(SegStop, BI.LastInstr); 901 } 902} 903 904 905//===----------------------------------------------------------------------===// 906// Global Live Range Splitting Support 907//===----------------------------------------------------------------------===// 908 909// These methods support a method of global live range splitting that uses a 910// global algorithm to decide intervals for CFG edges. They will insert split 911// points and color intervals in basic blocks while avoiding interference. 912// 913// Note that splitSingleBlock is also useful for blocks where both CFG edges 914// are on the stack. 915 916void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, 917 unsigned IntvIn, SlotIndex LeaveBefore, 918 unsigned IntvOut, SlotIndex EnterAfter){ 919 SlotIndex Start, Stop; 920 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); 921 922 DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop 923 << ") intf " << LeaveBefore << '-' << EnterAfter 924 << ", live-through " << IntvIn << " -> " << IntvOut); 925 926 assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks"); 927 928 assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block"); 929 assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf"); 930 assert((!EnterAfter || EnterAfter >= Start) && "Interference before block"); 931 932 MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); 933 934 if (!IntvOut) { 935 DEBUG(dbgs() << ", spill on entry.\n"); 936 // 937 // <<<<<<<<< Possible LeaveBefore interference. 938 // |-----------| Live through. 939 // -____________ Spill on entry. 940 // 941 selectIntv(IntvIn); 942 SlotIndex Idx = leaveIntvAtTop(*MBB); 943 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 944 (void)Idx; 945 return; 946 } 947 948 if (!IntvIn) { 949 DEBUG(dbgs() << ", reload on exit.\n"); 950 // 951 // >>>>>>> Possible EnterAfter interference. 952 // |-----------| Live through. 953 // ___________-- Reload on exit. 954 // 955 selectIntv(IntvOut); 956 SlotIndex Idx = enterIntvAtEnd(*MBB); 957 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 958 (void)Idx; 959 return; 960 } 961 962 if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { 963 DEBUG(dbgs() << ", straight through.\n"); 964 // 965 // |-----------| Live through. 966 // ------------- Straight through, same intv, no interference. 967 // 968 selectIntv(IntvOut); 969 useIntv(Start, Stop); 970 return; 971 } 972 973 // We cannot legally insert splits after LSP. 974 SlotIndex LSP = SA.getLastSplitPoint(MBBNum); 975 assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf"); 976 977 if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || 978 LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { 979 DEBUG(dbgs() << ", switch avoiding interference.\n"); 980 // 981 // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. 982 // |-----------| Live through. 983 // ------======= Switch intervals between interference. 984 // 985 selectIntv(IntvOut); 986 SlotIndex Idx; 987 if (LeaveBefore && LeaveBefore < LSP) { 988 Idx = enterIntvBefore(LeaveBefore); 989 useIntv(Idx, Stop); 990 } else { 991 Idx = enterIntvAtEnd(*MBB); 992 } 993 selectIntv(IntvIn); 994 useIntv(Start, Idx); 995 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 996 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 997 return; 998 } 999 1000 DEBUG(dbgs() << ", create local intv for interference.\n"); 1001 // 1002 // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. 1003 // |-----------| Live through. 1004 // ==---------== Switch intervals before/after interference. 1005 // 1006 assert(LeaveBefore <= EnterAfter && "Missed case"); 1007 1008 selectIntv(IntvOut); 1009 SlotIndex Idx = enterIntvAfter(EnterAfter); 1010 useIntv(Idx, Stop); 1011 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1012 1013 selectIntv(IntvIn); 1014 Idx = leaveIntvBefore(LeaveBefore); 1015 useIntv(Start, Idx); 1016 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1017} 1018 1019 1020void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 1021 unsigned IntvIn, SlotIndex LeaveBefore) { 1022 SlotIndex Start, Stop; 1023 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1024 1025 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1026 << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1027 << ", reg-in " << IntvIn << ", leave before " << LeaveBefore 1028 << (BI.LiveOut ? ", stack-out" : ", killed in block")); 1029 1030 assert(IntvIn && "Must have register in"); 1031 assert(BI.LiveIn && "Must be live-in"); 1032 assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference"); 1033 1034 if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { 1035 DEBUG(dbgs() << " before interference.\n"); 1036 // 1037 // <<< Interference after kill. 1038 // |---o---x | Killed in block. 1039 // ========= Use IntvIn everywhere. 1040 // 1041 selectIntv(IntvIn); 1042 useIntv(Start, BI.LastInstr); 1043 return; 1044 } 1045 1046 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1047 1048 if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { 1049 // 1050 // <<< Possible interference after last use. 1051 // |---o---o---| Live-out on stack. 1052 // =========____ Leave IntvIn after last use. 1053 // 1054 // < Interference after last use. 1055 // |---o---o--o| Live-out on stack, late last use. 1056 // ============ Copy to stack after LSP, overlap IntvIn. 1057 // \_____ Stack interval is live-out. 1058 // 1059 if (BI.LastInstr < LSP) { 1060 DEBUG(dbgs() << ", spill after last use before interference.\n"); 1061 selectIntv(IntvIn); 1062 SlotIndex Idx = leaveIntvAfter(BI.LastInstr); 1063 useIntv(Start, Idx); 1064 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1065 } else { 1066 DEBUG(dbgs() << ", spill before last split point.\n"); 1067 selectIntv(IntvIn); 1068 SlotIndex Idx = leaveIntvBefore(LSP); 1069 overlapIntv(Idx, BI.LastInstr); 1070 useIntv(Start, Idx); 1071 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1072 } 1073 return; 1074 } 1075 1076 // The interference is overlapping somewhere we wanted to use IntvIn. That 1077 // means we need to create a local interval that can be allocated a 1078 // different register. 1079 unsigned LocalIntv = openIntv(); 1080 (void)LocalIntv; 1081 DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n"); 1082 1083 if (!BI.LiveOut || BI.LastInstr < LSP) { 1084 // 1085 // <<<<<<< Interference overlapping uses. 1086 // |---o---o---| Live-out on stack. 1087 // =====----____ Leave IntvIn before interference, then spill. 1088 // 1089 SlotIndex To = leaveIntvAfter(BI.LastInstr); 1090 SlotIndex From = enterIntvBefore(LeaveBefore); 1091 useIntv(From, To); 1092 selectIntv(IntvIn); 1093 useIntv(Start, From); 1094 assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1095 return; 1096 } 1097 1098 // <<<<<<< Interference overlapping uses. 1099 // |---o---o--o| Live-out on stack, late last use. 1100 // =====------- Copy to stack before LSP, overlap LocalIntv. 1101 // \_____ Stack interval is live-out. 1102 // 1103 SlotIndex To = leaveIntvBefore(LSP); 1104 overlapIntv(To, BI.LastInstr); 1105 SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); 1106 useIntv(From, To); 1107 selectIntv(IntvIn); 1108 useIntv(Start, From); 1109 assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1110} 1111 1112void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 1113 unsigned IntvOut, SlotIndex EnterAfter) { 1114 SlotIndex Start, Stop; 1115 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1116 1117 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1118 << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1119 << ", reg-out " << IntvOut << ", enter after " << EnterAfter 1120 << (BI.LiveIn ? ", stack-in" : ", defined in block")); 1121 1122 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1123 1124 assert(IntvOut && "Must have register out"); 1125 assert(BI.LiveOut && "Must be live-out"); 1126 assert((!EnterAfter || EnterAfter < LSP) && "Bad interference"); 1127 1128 if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { 1129 DEBUG(dbgs() << " after interference.\n"); 1130 // 1131 // >>>> Interference before def. 1132 // | o---o---| Defined in block. 1133 // ========= Use IntvOut everywhere. 1134 // 1135 selectIntv(IntvOut); 1136 useIntv(BI.FirstInstr, Stop); 1137 return; 1138 } 1139 1140 if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { 1141 DEBUG(dbgs() << ", reload after interference.\n"); 1142 // 1143 // >>>> Interference before def. 1144 // |---o---o---| Live-through, stack-in. 1145 // ____========= Enter IntvOut before first use. 1146 // 1147 selectIntv(IntvOut); 1148 SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr)); 1149 useIntv(Idx, Stop); 1150 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1151 return; 1152 } 1153 1154 // The interference is overlapping somewhere we wanted to use IntvOut. That 1155 // means we need to create a local interval that can be allocated a 1156 // different register. 1157 DEBUG(dbgs() << ", interference overlaps uses.\n"); 1158 // 1159 // >>>>>>> Interference overlapping uses. 1160 // |---o---o---| Live-through, stack-in. 1161 // ____---====== Create local interval for interference range. 1162 // 1163 selectIntv(IntvOut); 1164 SlotIndex Idx = enterIntvAfter(EnterAfter); 1165 useIntv(Idx, Stop); 1166 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1167 1168 openIntv(); 1169 SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr)); 1170 useIntv(From, Idx); 1171} 1172