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