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