SplitKit.cpp revision c1c622ef0dd29d1bafd580790aec5231af50abf2
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 323 // Reset the LiveRangeCalc instances needed for this spill mode. 324 LRCalc[0].reset(&VRM.getMachineFunction()); 325 if (SpillMode) 326 LRCalc[1].reset(&VRM.getMachineFunction()); 327 328 // We don't need an AliasAnalysis since we will only be performing 329 // cheap-as-a-copy remats anyway. 330 Edit->anyRematerializable(LIS, TII, 0); 331} 332 333void SplitEditor::dump() const { 334 if (RegAssign.empty()) { 335 dbgs() << " empty\n"; 336 return; 337 } 338 339 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 340 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 341 dbgs() << '\n'; 342} 343 344VNInfo *SplitEditor::defValue(unsigned RegIdx, 345 const VNInfo *ParentVNI, 346 SlotIndex Idx) { 347 assert(ParentVNI && "Mapping NULL value"); 348 assert(Idx.isValid() && "Invalid SlotIndex"); 349 assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 350 LiveInterval *LI = Edit->get(RegIdx); 351 352 // Create a new value. 353 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 354 355 // Use insert for lookup, so we can add missing values with a second lookup. 356 std::pair<ValueMap::iterator, bool> InsP = 357 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 358 359 // This was the first time (RegIdx, ParentVNI) was mapped. 360 // Keep it as a simple def without any liveness. 361 if (InsP.second) 362 return VNI; 363 364 // If the previous value was a simple mapping, add liveness for it now. 365 if (VNInfo *OldVNI = InsP.first->second) { 366 SlotIndex Def = OldVNI->def; 367 LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 368 // No longer a simple mapping. 369 InsP.first->second = 0; 370 } 371 372 // This is a complex mapping, add liveness for VNI 373 SlotIndex Def = VNI->def; 374 LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 375 376 return VNI; 377} 378 379void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 380 assert(ParentVNI && "Mapping NULL value"); 381 VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 382 383 // ParentVNI was either unmapped or already complex mapped. Either way. 384 if (!VNI) 385 return; 386 387 // This was previously a single mapping. Make sure the old def is represented 388 // by a trivial live range. 389 SlotIndex Def = VNI->def; 390 Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 391 VNI = 0; 392} 393 394// extendRange - Extend the live range to reach Idx. 395// Potentially create phi-def values. 396void SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 397 getLRCalc(RegIdx).extend(Edit->get(RegIdx), Idx.getNextSlot(), 398 LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); 399} 400 401VNInfo *SplitEditor::defFromParent(unsigned RegIdx, 402 VNInfo *ParentVNI, 403 SlotIndex UseIdx, 404 MachineBasicBlock &MBB, 405 MachineBasicBlock::iterator I) { 406 MachineInstr *CopyMI = 0; 407 SlotIndex Def; 408 LiveInterval *LI = Edit->get(RegIdx); 409 410 // We may be trying to avoid interference that ends at a deleted instruction, 411 // so always begin RegIdx 0 early and all others late. 412 bool Late = RegIdx != 0; 413 414 // Attempt cheap-as-a-copy rematerialization. 415 LiveRangeEdit::Remat RM(ParentVNI); 416 if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 417 Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late); 418 ++NumRemats; 419 } else { 420 // Can't remat, just insert a copy from parent. 421 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 422 .addReg(Edit->getReg()); 423 Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) 424 .getDefIndex(); 425 ++NumCopies; 426 } 427 428 // Define the value in Reg. 429 VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 430 VNI->setCopy(CopyMI); 431 return VNI; 432} 433 434/// Create a new virtual register and live interval. 435unsigned SplitEditor::openIntv() { 436 // Create the complement as index 0. 437 if (Edit->empty()) 438 Edit->create(LIS, VRM); 439 440 // Create the open interval. 441 OpenIdx = Edit->size(); 442 Edit->create(LIS, VRM); 443 return OpenIdx; 444} 445 446void SplitEditor::selectIntv(unsigned Idx) { 447 assert(Idx != 0 && "Cannot select the complement interval"); 448 assert(Idx < Edit->size() && "Can only select previously opened interval"); 449 DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); 450 OpenIdx = Idx; 451} 452 453SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 454 assert(OpenIdx && "openIntv not called before enterIntvBefore"); 455 DEBUG(dbgs() << " enterIntvBefore " << Idx); 456 Idx = Idx.getBaseIndex(); 457 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 458 if (!ParentVNI) { 459 DEBUG(dbgs() << ": not live\n"); 460 return Idx; 461 } 462 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 463 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 464 assert(MI && "enterIntvBefore called with invalid index"); 465 466 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 467 return VNI->def; 468} 469 470SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { 471 assert(OpenIdx && "openIntv not called before enterIntvAfter"); 472 DEBUG(dbgs() << " enterIntvAfter " << Idx); 473 Idx = Idx.getBoundaryIndex(); 474 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 475 if (!ParentVNI) { 476 DEBUG(dbgs() << ": not live\n"); 477 return Idx; 478 } 479 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 480 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 481 assert(MI && "enterIntvAfter called with invalid index"); 482 483 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), 484 llvm::next(MachineBasicBlock::iterator(MI))); 485 return VNI->def; 486} 487 488SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 489 assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 490 SlotIndex End = LIS.getMBBEndIdx(&MBB); 491 SlotIndex Last = End.getPrevSlot(); 492 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 493 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 494 if (!ParentVNI) { 495 DEBUG(dbgs() << ": not live\n"); 496 return End; 497 } 498 DEBUG(dbgs() << ": valno " << ParentVNI->id); 499 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 500 LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 501 RegAssign.insert(VNI->def, End, OpenIdx); 502 DEBUG(dump()); 503 return VNI->def; 504} 505 506/// useIntv - indicate that all instructions in MBB should use OpenLI. 507void SplitEditor::useIntv(const MachineBasicBlock &MBB) { 508 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 509} 510 511void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 512 assert(OpenIdx && "openIntv not called before useIntv"); 513 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 514 RegAssign.insert(Start, End, OpenIdx); 515 DEBUG(dump()); 516} 517 518SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 519 assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 520 DEBUG(dbgs() << " leaveIntvAfter " << Idx); 521 522 // The interval must be live beyond the instruction at Idx. 523 Idx = Idx.getBoundaryIndex(); 524 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 525 if (!ParentVNI) { 526 DEBUG(dbgs() << ": not live\n"); 527 return Idx.getNextSlot(); 528 } 529 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 530 531 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 532 assert(MI && "No instruction at index"); 533 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 534 llvm::next(MachineBasicBlock::iterator(MI))); 535 return VNI->def; 536} 537 538SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 539 assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 540 DEBUG(dbgs() << " leaveIntvBefore " << Idx); 541 542 // The interval must be live into the instruction at Idx. 543 Idx = Idx.getBaseIndex(); 544 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 545 if (!ParentVNI) { 546 DEBUG(dbgs() << ": not live\n"); 547 return Idx.getNextSlot(); 548 } 549 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 550 551 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 552 assert(MI && "No instruction at index"); 553 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 554 return VNI->def; 555} 556 557SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 558 assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 559 SlotIndex Start = LIS.getMBBStartIdx(&MBB); 560 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 561 562 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 563 if (!ParentVNI) { 564 DEBUG(dbgs() << ": not live\n"); 565 return Start; 566 } 567 568 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 569 MBB.SkipPHIsAndLabels(MBB.begin())); 570 RegAssign.insert(Start, VNI->def, OpenIdx); 571 DEBUG(dump()); 572 return VNI->def; 573} 574 575void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 576 assert(OpenIdx && "openIntv not called before overlapIntv"); 577 const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 578 assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 579 "Parent changes value in extended range"); 580 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 581 "Range cannot span basic blocks"); 582 583 // The complement interval will be extended as needed by extendRange(). 584 if (ParentVNI) 585 markComplexMapped(0, ParentVNI); 586 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 587 RegAssign.insert(Start, End, OpenIdx); 588 DEBUG(dump()); 589} 590 591/// transferValues - Transfer all possible values to the new live ranges. 592/// Values that were rematerialized are left alone, they need extendRange(). 593bool SplitEditor::transferValues() { 594 bool Skipped = false; 595 RegAssignMap::const_iterator AssignI = RegAssign.begin(); 596 for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 597 ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 598 DEBUG(dbgs() << " blit " << *ParentI << ':'); 599 VNInfo *ParentVNI = ParentI->valno; 600 // RegAssign has holes where RegIdx 0 should be used. 601 SlotIndex Start = ParentI->start; 602 AssignI.advanceTo(Start); 603 do { 604 unsigned RegIdx; 605 SlotIndex End = ParentI->end; 606 if (!AssignI.valid()) { 607 RegIdx = 0; 608 } else if (AssignI.start() <= Start) { 609 RegIdx = AssignI.value(); 610 if (AssignI.stop() < End) { 611 End = AssignI.stop(); 612 ++AssignI; 613 } 614 } else { 615 RegIdx = 0; 616 End = std::min(End, AssignI.start()); 617 } 618 619 // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 620 DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 621 LiveInterval *LI = Edit->get(RegIdx); 622 623 // Check for a simply defined value that can be blitted directly. 624 if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 625 DEBUG(dbgs() << ':' << VNI->id); 626 LI->addRange(LiveRange(Start, End, VNI)); 627 Start = End; 628 continue; 629 } 630 631 // Skip rematerialized values, we need to use extendRange() and 632 // extendPHIKillRanges() to completely recompute the live ranges. 633 if (Edit->didRematerialize(ParentVNI)) { 634 DEBUG(dbgs() << "(remat)"); 635 Skipped = true; 636 Start = End; 637 continue; 638 } 639 640 LiveRangeCalc &LRC = getLRCalc(RegIdx); 641 642 // This value has multiple defs in RegIdx, but it wasn't rematerialized, 643 // so the live range is accurate. Add live-in blocks in [Start;End) to the 644 // LiveInBlocks. 645 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 646 SlotIndex BlockStart, BlockEnd; 647 tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 648 649 // The first block may be live-in, or it may have its own def. 650 if (Start != BlockStart) { 651 VNInfo *VNI = LI->extendInBlock(BlockStart, 652 std::min(BlockEnd, End).getPrevSlot()); 653 assert(VNI && "Missing def for complex mapped value"); 654 DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 655 // MBB has its own def. Is it also live-out? 656 if (BlockEnd <= End) 657 LRC.setLiveOutValue(MBB, VNI); 658 659 // Skip to the next block for live-in. 660 ++MBB; 661 BlockStart = BlockEnd; 662 } 663 664 // Handle the live-in blocks covered by [Start;End). 665 assert(Start <= BlockStart && "Expected live-in block"); 666 while (BlockStart < End) { 667 DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 668 BlockEnd = LIS.getMBBEndIdx(MBB); 669 if (BlockStart == ParentVNI->def) { 670 // This block has the def of a parent PHI, so it isn't live-in. 671 assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 672 VNInfo *VNI = LI->extendInBlock(BlockStart, 673 std::min(BlockEnd, End).getPrevSlot()); 674 assert(VNI && "Missing def for complex mapped parent PHI"); 675 if (End >= BlockEnd) 676 LRC.setLiveOutValue(MBB, VNI); // Live-out as well. 677 } else { 678 // This block needs a live-in value. The last block covered may not 679 // be live-out. 680 if (End < BlockEnd) 681 LRC.addLiveInBlock(LI, MDT[MBB], End); 682 else { 683 // Live-through, and we don't know the value. 684 LRC.addLiveInBlock(LI, MDT[MBB]); 685 LRC.setLiveOutValue(MBB, 0); 686 } 687 } 688 BlockStart = BlockEnd; 689 ++MBB; 690 } 691 Start = End; 692 } while (Start != ParentI->end); 693 DEBUG(dbgs() << '\n'); 694 } 695 696 LRCalc[0].calculateValues(LIS.getSlotIndexes(), &MDT, 697 &LIS.getVNInfoAllocator()); 698 if (SpillMode) 699 LRCalc[1].calculateValues(LIS.getSlotIndexes(), &MDT, 700 &LIS.getVNInfoAllocator()); 701 702 return Skipped; 703} 704 705void SplitEditor::extendPHIKillRanges() { 706 // Extend live ranges to be live-out for successor PHI values. 707 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 708 E = Edit->getParent().vni_end(); I != E; ++I) { 709 const VNInfo *PHIVNI = *I; 710 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 711 continue; 712 unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 713 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 714 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 715 PE = MBB->pred_end(); PI != PE; ++PI) { 716 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 717 // The predecessor may not have a live-out value. That is OK, like an 718 // undef PHI operand. 719 if (Edit->getParent().liveAt(End)) { 720 assert(RegAssign.lookup(End) == RegIdx && 721 "Different register assignment in phi predecessor"); 722 extendRange(RegIdx, End); 723 } 724 } 725 } 726} 727 728/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 729void SplitEditor::rewriteAssigned(bool ExtendRanges) { 730 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 731 RE = MRI.reg_end(); RI != RE;) { 732 MachineOperand &MO = RI.getOperand(); 733 MachineInstr *MI = MO.getParent(); 734 ++RI; 735 // LiveDebugVariables should have handled all DBG_VALUE instructions. 736 if (MI->isDebugValue()) { 737 DEBUG(dbgs() << "Zapping " << *MI); 738 MO.setReg(0); 739 continue; 740 } 741 742 // <undef> operands don't really read the register, so it doesn't matter 743 // which register we choose. When the use operand is tied to a def, we must 744 // use the same register as the def, so just do that always. 745 SlotIndex Idx = LIS.getInstructionIndex(MI); 746 if (MO.isDef() || MO.isUndef()) 747 Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex(); 748 749 // Rewrite to the mapped register at Idx. 750 unsigned RegIdx = RegAssign.lookup(Idx); 751 MO.setReg(Edit->get(RegIdx)->reg); 752 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 753 << Idx << ':' << RegIdx << '\t' << *MI); 754 755 // Extend liveness to Idx if the instruction reads reg. 756 if (!ExtendRanges || MO.isUndef()) 757 continue; 758 759 // Skip instructions that don't read Reg. 760 if (MO.isDef()) { 761 if (!MO.getSubReg() && !MO.isEarlyClobber()) 762 continue; 763 // We may wan't to extend a live range for a partial redef, or for a use 764 // tied to an early clobber. 765 Idx = Idx.getPrevSlot(); 766 if (!Edit->getParent().liveAt(Idx)) 767 continue; 768 } else 769 Idx = Idx.getUseIndex(); 770 771 extendRange(RegIdx, Idx); 772 } 773} 774 775void SplitEditor::deleteRematVictims() { 776 SmallVector<MachineInstr*, 8> Dead; 777 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 778 LiveInterval *LI = *I; 779 for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 780 LII != LIE; ++LII) { 781 // Dead defs end at the store slot. 782 if (LII->end != LII->valno->def.getNextSlot()) 783 continue; 784 MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 785 assert(MI && "Missing instruction for dead def"); 786 MI->addRegisterDead(LI->reg, &TRI); 787 788 if (!MI->allDefsAreDead()) 789 continue; 790 791 DEBUG(dbgs() << "All defs dead: " << *MI); 792 Dead.push_back(MI); 793 } 794 } 795 796 if (Dead.empty()) 797 return; 798 799 Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); 800} 801 802void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 803 ++NumFinished; 804 805 // At this point, the live intervals in Edit contain VNInfos corresponding to 806 // the inserted copies. 807 808 // Add the original defs from the parent interval. 809 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 810 E = Edit->getParent().vni_end(); I != E; ++I) { 811 const VNInfo *ParentVNI = *I; 812 if (ParentVNI->isUnused()) 813 continue; 814 unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 815 VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 816 VNI->setIsPHIDef(ParentVNI->isPHIDef()); 817 VNI->setCopy(ParentVNI->getCopy()); 818 819 // Mark rematted values as complex everywhere to force liveness computation. 820 // The new live ranges may be truncated. 821 if (Edit->didRematerialize(ParentVNI)) 822 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 823 markComplexMapped(i, ParentVNI); 824 } 825 826 // Transfer the simply mapped values, check if any are skipped. 827 bool Skipped = transferValues(); 828 if (Skipped) 829 extendPHIKillRanges(); 830 else 831 ++NumSimple; 832 833 // Rewrite virtual registers, possibly extending ranges. 834 rewriteAssigned(Skipped); 835 836 // Delete defs that were rematted everywhere. 837 if (Skipped) 838 deleteRematVictims(); 839 840 // Get rid of unused values and set phi-kill flags. 841 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 842 (*I)->RenumberValues(LIS); 843 844 // Provide a reverse mapping from original indices to Edit ranges. 845 if (LRMap) { 846 LRMap->clear(); 847 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 848 LRMap->push_back(i); 849 } 850 851 // Now check if any registers were separated into multiple components. 852 ConnectedVNInfoEqClasses ConEQ(LIS); 853 for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 854 // Don't use iterators, they are invalidated by create() below. 855 LiveInterval *li = Edit->get(i); 856 unsigned NumComp = ConEQ.Classify(li); 857 if (NumComp <= 1) 858 continue; 859 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 860 SmallVector<LiveInterval*, 8> dups; 861 dups.push_back(li); 862 for (unsigned j = 1; j != NumComp; ++j) 863 dups.push_back(&Edit->create(LIS, VRM)); 864 ConEQ.Distribute(&dups[0], MRI); 865 // The new intervals all map back to i. 866 if (LRMap) 867 LRMap->resize(Edit->size(), i); 868 } 869 870 // Calculate spill weight and allocation hints for new intervals. 871 Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops); 872 873 assert(!LRMap || LRMap->size() == Edit->size()); 874} 875 876 877//===----------------------------------------------------------------------===// 878// Single Block Splitting 879//===----------------------------------------------------------------------===// 880 881bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, 882 bool SingleInstrs) const { 883 // Always split for multiple instructions. 884 if (!BI.isOneInstr()) 885 return true; 886 // Don't split for single instructions unless explicitly requested. 887 if (!SingleInstrs) 888 return false; 889 // Splitting a live-through range always makes progress. 890 if (BI.LiveIn && BI.LiveOut) 891 return true; 892 // No point in isolating a copy. It has no register class constraints. 893 if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike()) 894 return false; 895 // Finally, don't isolate an end point that was created by earlier splits. 896 return isOriginalEndpoint(BI.FirstInstr); 897} 898 899void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 900 openIntv(); 901 SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 902 SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr, 903 LastSplitPoint)); 904 if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { 905 useIntv(SegStart, leaveIntvAfter(BI.LastInstr)); 906 } else { 907 // The last use is after the last valid split point. 908 SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 909 useIntv(SegStart, SegStop); 910 overlapIntv(SegStop, BI.LastInstr); 911 } 912} 913 914 915//===----------------------------------------------------------------------===// 916// Global Live Range Splitting Support 917//===----------------------------------------------------------------------===// 918 919// These methods support a method of global live range splitting that uses a 920// global algorithm to decide intervals for CFG edges. They will insert split 921// points and color intervals in basic blocks while avoiding interference. 922// 923// Note that splitSingleBlock is also useful for blocks where both CFG edges 924// are on the stack. 925 926void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, 927 unsigned IntvIn, SlotIndex LeaveBefore, 928 unsigned IntvOut, SlotIndex EnterAfter){ 929 SlotIndex Start, Stop; 930 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); 931 932 DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop 933 << ") intf " << LeaveBefore << '-' << EnterAfter 934 << ", live-through " << IntvIn << " -> " << IntvOut); 935 936 assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks"); 937 938 assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block"); 939 assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf"); 940 assert((!EnterAfter || EnterAfter >= Start) && "Interference before block"); 941 942 MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); 943 944 if (!IntvOut) { 945 DEBUG(dbgs() << ", spill on entry.\n"); 946 // 947 // <<<<<<<<< Possible LeaveBefore interference. 948 // |-----------| Live through. 949 // -____________ Spill on entry. 950 // 951 selectIntv(IntvIn); 952 SlotIndex Idx = leaveIntvAtTop(*MBB); 953 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 954 (void)Idx; 955 return; 956 } 957 958 if (!IntvIn) { 959 DEBUG(dbgs() << ", reload on exit.\n"); 960 // 961 // >>>>>>> Possible EnterAfter interference. 962 // |-----------| Live through. 963 // ___________-- Reload on exit. 964 // 965 selectIntv(IntvOut); 966 SlotIndex Idx = enterIntvAtEnd(*MBB); 967 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 968 (void)Idx; 969 return; 970 } 971 972 if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { 973 DEBUG(dbgs() << ", straight through.\n"); 974 // 975 // |-----------| Live through. 976 // ------------- Straight through, same intv, no interference. 977 // 978 selectIntv(IntvOut); 979 useIntv(Start, Stop); 980 return; 981 } 982 983 // We cannot legally insert splits after LSP. 984 SlotIndex LSP = SA.getLastSplitPoint(MBBNum); 985 assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf"); 986 987 if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || 988 LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { 989 DEBUG(dbgs() << ", switch avoiding interference.\n"); 990 // 991 // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. 992 // |-----------| Live through. 993 // ------======= Switch intervals between interference. 994 // 995 selectIntv(IntvOut); 996 SlotIndex Idx; 997 if (LeaveBefore && LeaveBefore < LSP) { 998 Idx = enterIntvBefore(LeaveBefore); 999 useIntv(Idx, Stop); 1000 } else { 1001 Idx = enterIntvAtEnd(*MBB); 1002 } 1003 selectIntv(IntvIn); 1004 useIntv(Start, Idx); 1005 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1006 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1007 return; 1008 } 1009 1010 DEBUG(dbgs() << ", create local intv for interference.\n"); 1011 // 1012 // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. 1013 // |-----------| Live through. 1014 // ==---------== Switch intervals before/after interference. 1015 // 1016 assert(LeaveBefore <= EnterAfter && "Missed case"); 1017 1018 selectIntv(IntvOut); 1019 SlotIndex Idx = enterIntvAfter(EnterAfter); 1020 useIntv(Idx, Stop); 1021 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1022 1023 selectIntv(IntvIn); 1024 Idx = leaveIntvBefore(LeaveBefore); 1025 useIntv(Start, Idx); 1026 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1027} 1028 1029 1030void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 1031 unsigned IntvIn, SlotIndex LeaveBefore) { 1032 SlotIndex Start, Stop; 1033 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1034 1035 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1036 << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1037 << ", reg-in " << IntvIn << ", leave before " << LeaveBefore 1038 << (BI.LiveOut ? ", stack-out" : ", killed in block")); 1039 1040 assert(IntvIn && "Must have register in"); 1041 assert(BI.LiveIn && "Must be live-in"); 1042 assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference"); 1043 1044 if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { 1045 DEBUG(dbgs() << " before interference.\n"); 1046 // 1047 // <<< Interference after kill. 1048 // |---o---x | Killed in block. 1049 // ========= Use IntvIn everywhere. 1050 // 1051 selectIntv(IntvIn); 1052 useIntv(Start, BI.LastInstr); 1053 return; 1054 } 1055 1056 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1057 1058 if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { 1059 // 1060 // <<< Possible interference after last use. 1061 // |---o---o---| Live-out on stack. 1062 // =========____ Leave IntvIn after last use. 1063 // 1064 // < Interference after last use. 1065 // |---o---o--o| Live-out on stack, late last use. 1066 // ============ Copy to stack after LSP, overlap IntvIn. 1067 // \_____ Stack interval is live-out. 1068 // 1069 if (BI.LastInstr < LSP) { 1070 DEBUG(dbgs() << ", spill after last use before interference.\n"); 1071 selectIntv(IntvIn); 1072 SlotIndex Idx = leaveIntvAfter(BI.LastInstr); 1073 useIntv(Start, Idx); 1074 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1075 } else { 1076 DEBUG(dbgs() << ", spill before last split point.\n"); 1077 selectIntv(IntvIn); 1078 SlotIndex Idx = leaveIntvBefore(LSP); 1079 overlapIntv(Idx, BI.LastInstr); 1080 useIntv(Start, Idx); 1081 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1082 } 1083 return; 1084 } 1085 1086 // The interference is overlapping somewhere we wanted to use IntvIn. That 1087 // means we need to create a local interval that can be allocated a 1088 // different register. 1089 unsigned LocalIntv = openIntv(); 1090 (void)LocalIntv; 1091 DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n"); 1092 1093 if (!BI.LiveOut || BI.LastInstr < LSP) { 1094 // 1095 // <<<<<<< Interference overlapping uses. 1096 // |---o---o---| Live-out on stack. 1097 // =====----____ Leave IntvIn before interference, then spill. 1098 // 1099 SlotIndex To = leaveIntvAfter(BI.LastInstr); 1100 SlotIndex From = enterIntvBefore(LeaveBefore); 1101 useIntv(From, To); 1102 selectIntv(IntvIn); 1103 useIntv(Start, From); 1104 assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1105 return; 1106 } 1107 1108 // <<<<<<< Interference overlapping uses. 1109 // |---o---o--o| Live-out on stack, late last use. 1110 // =====------- Copy to stack before LSP, overlap LocalIntv. 1111 // \_____ Stack interval is live-out. 1112 // 1113 SlotIndex To = leaveIntvBefore(LSP); 1114 overlapIntv(To, BI.LastInstr); 1115 SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); 1116 useIntv(From, To); 1117 selectIntv(IntvIn); 1118 useIntv(Start, From); 1119 assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1120} 1121 1122void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 1123 unsigned IntvOut, SlotIndex EnterAfter) { 1124 SlotIndex Start, Stop; 1125 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1126 1127 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1128 << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1129 << ", reg-out " << IntvOut << ", enter after " << EnterAfter 1130 << (BI.LiveIn ? ", stack-in" : ", defined in block")); 1131 1132 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1133 1134 assert(IntvOut && "Must have register out"); 1135 assert(BI.LiveOut && "Must be live-out"); 1136 assert((!EnterAfter || EnterAfter < LSP) && "Bad interference"); 1137 1138 if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { 1139 DEBUG(dbgs() << " after interference.\n"); 1140 // 1141 // >>>> Interference before def. 1142 // | o---o---| Defined in block. 1143 // ========= Use IntvOut everywhere. 1144 // 1145 selectIntv(IntvOut); 1146 useIntv(BI.FirstInstr, Stop); 1147 return; 1148 } 1149 1150 if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { 1151 DEBUG(dbgs() << ", reload after interference.\n"); 1152 // 1153 // >>>> Interference before def. 1154 // |---o---o---| Live-through, stack-in. 1155 // ____========= Enter IntvOut before first use. 1156 // 1157 selectIntv(IntvOut); 1158 SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr)); 1159 useIntv(Idx, Stop); 1160 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1161 return; 1162 } 1163 1164 // The interference is overlapping somewhere we wanted to use IntvOut. That 1165 // means we need to create a local interval that can be allocated a 1166 // different register. 1167 DEBUG(dbgs() << ", interference overlaps uses.\n"); 1168 // 1169 // >>>>>>> Interference overlapping uses. 1170 // |---o---o---| Live-through, stack-in. 1171 // ____---====== Create local interval for interference range. 1172 // 1173 selectIntv(IntvOut); 1174 SlotIndex Idx = enterIntvAfter(EnterAfter); 1175 useIntv(Idx, Stop); 1176 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1177 1178 openIntv(); 1179 SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr)); 1180 useIntv(From, Idx); 1181} 1182