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