SplitKit.cpp revision 77ee1140a3297e6fbd6cb7cf586872af6d00d07e
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.FirstUse = *UseI; 182 assert(BI.FirstUse >= Start); 183 do ++UseI; 184 while (UseI != UseE && *UseI < Stop); 185 BI.LastUse = UseI[-1]; 186 assert(BI.LastUse < 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.FirstUse && "First instr should be a def"); 195 BI.FirstDef = BI.FirstUse; 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.LastUse = 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().LastUse = LastStop; 217 218 // Set up BI for the live-out part. 219 BI.LiveIn = false; 220 BI.LiveOut = true; 221 BI.FirstUse = 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 RegAssign(Allocator) 313{} 314 315void SplitEditor::reset(LiveRangeEdit &lre) { 316 Edit = &lre; 317 OpenIdx = 0; 318 RegAssign.clear(); 319 Values.clear(); 320 321 // We don't need to clear LiveOutCache, only LiveOutSeen entries are read. 322 LiveOutSeen.clear(); 323 324 // We don't need an AliasAnalysis since we will only be performing 325 // cheap-as-a-copy remats anyway. 326 Edit->anyRematerializable(LIS, TII, 0); 327} 328 329void SplitEditor::dump() const { 330 if (RegAssign.empty()) { 331 dbgs() << " empty\n"; 332 return; 333 } 334 335 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 336 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 337 dbgs() << '\n'; 338} 339 340VNInfo *SplitEditor::defValue(unsigned RegIdx, 341 const VNInfo *ParentVNI, 342 SlotIndex Idx) { 343 assert(ParentVNI && "Mapping NULL value"); 344 assert(Idx.isValid() && "Invalid SlotIndex"); 345 assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 346 LiveInterval *LI = Edit->get(RegIdx); 347 348 // Create a new value. 349 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 350 351 // Use insert for lookup, so we can add missing values with a second lookup. 352 std::pair<ValueMap::iterator, bool> InsP = 353 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 354 355 // This was the first time (RegIdx, ParentVNI) was mapped. 356 // Keep it as a simple def without any liveness. 357 if (InsP.second) 358 return VNI; 359 360 // If the previous value was a simple mapping, add liveness for it now. 361 if (VNInfo *OldVNI = InsP.first->second) { 362 SlotIndex Def = OldVNI->def; 363 LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 364 // No longer a simple mapping. 365 InsP.first->second = 0; 366 } 367 368 // This is a complex mapping, add liveness for VNI 369 SlotIndex Def = VNI->def; 370 LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 371 372 return VNI; 373} 374 375void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 376 assert(ParentVNI && "Mapping NULL value"); 377 VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 378 379 // ParentVNI was either unmapped or already complex mapped. Either way. 380 if (!VNI) 381 return; 382 383 // This was previously a single mapping. Make sure the old def is represented 384 // by a trivial live range. 385 SlotIndex Def = VNI->def; 386 Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 387 VNI = 0; 388} 389 390// extendRange - Extend the live range to reach Idx. 391// Potentially create phi-def values. 392void SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 393 assert(Idx.isValid() && "Invalid SlotIndex"); 394 MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 395 assert(IdxMBB && "No MBB at Idx"); 396 LiveInterval *LI = Edit->get(RegIdx); 397 398 // Is there a def in the same MBB we can extend? 399 if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx)) 400 return; 401 402 // Now for the fun part. We know that ParentVNI potentially has multiple defs, 403 // and we may need to create even more phi-defs to preserve VNInfo SSA form. 404 // Perform a search for all predecessor blocks where we know the dominating 405 // VNInfo. 406 VNInfo *VNI = findReachingDefs(LI, IdxMBB, Idx.getNextSlot()); 407 408 // When there were multiple different values, we may need new PHIs. 409 if (!VNI) 410 return updateSSA(); 411 412 // Poor man's SSA update for the single-value case. 413 LiveOutPair LOP(VNI, MDT[LIS.getMBBFromIndex(VNI->def)]); 414 for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 415 E = LiveInBlocks.end(); I != E; ++I) { 416 MachineBasicBlock *MBB = I->DomNode->getBlock(); 417 SlotIndex Start = LIS.getMBBStartIdx(MBB); 418 if (I->Kill.isValid()) 419 LI->addRange(LiveRange(Start, I->Kill, VNI)); 420 else { 421 LiveOutCache[MBB] = LOP; 422 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 423 } 424 } 425} 426 427/// findReachingDefs - Search the CFG for known live-out values. 428/// Add required live-in blocks to LiveInBlocks. 429VNInfo *SplitEditor::findReachingDefs(LiveInterval *LI, 430 MachineBasicBlock *KillMBB, 431 SlotIndex Kill) { 432 // Initialize the live-out cache the first time it is needed. 433 if (LiveOutSeen.empty()) { 434 unsigned N = VRM.getMachineFunction().getNumBlockIDs(); 435 LiveOutSeen.resize(N); 436 LiveOutCache.resize(N); 437 } 438 439 // Blocks where LI should be live-in. 440 SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB); 441 442 // Remember if we have seen more than one value. 443 bool UniqueVNI = true; 444 VNInfo *TheVNI = 0; 445 446 // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 447 for (unsigned i = 0; i != WorkList.size(); ++i) { 448 MachineBasicBlock *MBB = WorkList[i]; 449 assert(!MBB->pred_empty() && "Value live-in to entry block?"); 450 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 451 PE = MBB->pred_end(); PI != PE; ++PI) { 452 MachineBasicBlock *Pred = *PI; 453 LiveOutPair &LOP = LiveOutCache[Pred]; 454 455 // Is this a known live-out block? 456 if (LiveOutSeen.test(Pred->getNumber())) { 457 if (VNInfo *VNI = LOP.first) { 458 if (TheVNI && TheVNI != VNI) 459 UniqueVNI = false; 460 TheVNI = VNI; 461 } 462 continue; 463 } 464 465 // First time. LOP is garbage and must be cleared below. 466 LiveOutSeen.set(Pred->getNumber()); 467 468 // Does Pred provide a live-out value? 469 SlotIndex Start, Last; 470 tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred); 471 Last = Last.getPrevSlot(); 472 VNInfo *VNI = LI->extendInBlock(Start, Last); 473 LOP.first = VNI; 474 if (VNI) { 475 LOP.second = MDT[LIS.getMBBFromIndex(VNI->def)]; 476 if (TheVNI && TheVNI != VNI) 477 UniqueVNI = false; 478 TheVNI = VNI; 479 continue; 480 } 481 LOP.second = 0; 482 483 // No, we need a live-in value for Pred as well 484 if (Pred != KillMBB) 485 WorkList.push_back(Pred); 486 else 487 // Loopback to KillMBB, so value is really live through. 488 Kill = SlotIndex(); 489 } 490 } 491 492 // Transfer WorkList to LiveInBlocks in reverse order. 493 // This ordering works best with updateSSA(). 494 LiveInBlocks.clear(); 495 LiveInBlocks.reserve(WorkList.size()); 496 while(!WorkList.empty()) 497 LiveInBlocks.push_back(MDT[WorkList.pop_back_val()]); 498 499 // The kill block may not be live-through. 500 assert(LiveInBlocks.back().DomNode->getBlock() == KillMBB); 501 LiveInBlocks.back().Kill = Kill; 502 503 return UniqueVNI ? TheVNI : 0; 504} 505 506void SplitEditor::updateSSA() { 507 // This is essentially the same iterative algorithm that SSAUpdater uses, 508 // except we already have a dominator tree, so we don't have to recompute it. 509 unsigned Changes; 510 do { 511 Changes = 0; 512 // Propagate live-out values down the dominator tree, inserting phi-defs 513 // when necessary. 514 for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 515 E = LiveInBlocks.end(); I != E; ++I) { 516 MachineDomTreeNode *Node = I->DomNode; 517 // Skip block if the live-in value has already been determined. 518 if (!Node) 519 continue; 520 MachineBasicBlock *MBB = Node->getBlock(); 521 MachineDomTreeNode *IDom = Node->getIDom(); 522 LiveOutPair IDomValue; 523 524 // We need a live-in value to a block with no immediate dominator? 525 // This is probably an unreachable block that has survived somehow. 526 bool needPHI = !IDom || !LiveOutSeen.test(IDom->getBlock()->getNumber()); 527 528 // IDom dominates all of our predecessors, but it may not be their 529 // immediate dominator. Check if any of them have live-out values that are 530 // properly dominated by IDom. If so, we need a phi-def here. 531 if (!needPHI) { 532 IDomValue = LiveOutCache[IDom->getBlock()]; 533 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 534 PE = MBB->pred_end(); PI != PE; ++PI) { 535 LiveOutPair Value = LiveOutCache[*PI]; 536 if (!Value.first || Value.first == IDomValue.first) 537 continue; 538 // This predecessor is carrying something other than IDomValue. 539 // It could be because IDomValue hasn't propagated yet, or it could be 540 // because MBB is in the dominance frontier of that value. 541 if (MDT.dominates(IDom, Value.second)) { 542 needPHI = true; 543 break; 544 } 545 } 546 } 547 548 // The value may be live-through even if Kill is set, as can happen when 549 // we are called from extendRange. In that case LiveOutSeen is true, and 550 // LiveOutCache indicates a foreign or missing value. 551 LiveOutPair &LOP = LiveOutCache[MBB]; 552 553 // Create a phi-def if required. 554 if (needPHI) { 555 ++Changes; 556 SlotIndex Start = LIS.getMBBStartIdx(MBB); 557 unsigned RegIdx = RegAssign.lookup(Start); 558 LiveInterval *LI = Edit->get(RegIdx); 559 VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 560 VNI->setIsPHIDef(true); 561 I->Value = VNI; 562 // This block is done, we know the final value. 563 I->DomNode = 0; 564 if (I->Kill.isValid()) 565 LI->addRange(LiveRange(Start, I->Kill, VNI)); 566 else { 567 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 568 LOP = LiveOutPair(VNI, Node); 569 } 570 } else if (IDomValue.first) { 571 // No phi-def here. Remember incoming value. 572 I->Value = IDomValue.first; 573 if (I->Kill.isValid()) 574 continue; 575 // Propagate IDomValue if needed: 576 // MBB is live-out and doesn't define its own value. 577 if (LOP.second != Node && LOP.first != IDomValue.first) { 578 ++Changes; 579 LOP = IDomValue; 580 } 581 } 582 } 583 } while (Changes); 584 585 // The values in LiveInBlocks are now accurate. No more phi-defs are needed 586 // for these blocks, so we can color the live ranges. 587 for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 588 E = LiveInBlocks.end(); I != E; ++I) { 589 if (!I->DomNode) 590 continue; 591 assert(I->Value && "No live-in value found"); 592 MachineBasicBlock *MBB = I->DomNode->getBlock(); 593 SlotIndex Start = LIS.getMBBStartIdx(MBB); 594 unsigned RegIdx = RegAssign.lookup(Start); 595 LiveInterval *LI = Edit->get(RegIdx); 596 LI->addRange(LiveRange(Start, I->Kill.isValid() ? 597 I->Kill : LIS.getMBBEndIdx(MBB), I->Value)); 598 } 599} 600 601VNInfo *SplitEditor::defFromParent(unsigned RegIdx, 602 VNInfo *ParentVNI, 603 SlotIndex UseIdx, 604 MachineBasicBlock &MBB, 605 MachineBasicBlock::iterator I) { 606 MachineInstr *CopyMI = 0; 607 SlotIndex Def; 608 LiveInterval *LI = Edit->get(RegIdx); 609 610 // We may be trying to avoid interference that ends at a deleted instruction, 611 // so always begin RegIdx 0 early and all others late. 612 bool Late = RegIdx != 0; 613 614 // Attempt cheap-as-a-copy rematerialization. 615 LiveRangeEdit::Remat RM(ParentVNI); 616 if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 617 Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late); 618 ++NumRemats; 619 } else { 620 // Can't remat, just insert a copy from parent. 621 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 622 .addReg(Edit->getReg()); 623 Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) 624 .getDefIndex(); 625 ++NumCopies; 626 } 627 628 // Define the value in Reg. 629 VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 630 VNI->setCopy(CopyMI); 631 return VNI; 632} 633 634/// Create a new virtual register and live interval. 635unsigned SplitEditor::openIntv() { 636 // Create the complement as index 0. 637 if (Edit->empty()) 638 Edit->create(LIS, VRM); 639 640 // Create the open interval. 641 OpenIdx = Edit->size(); 642 Edit->create(LIS, VRM); 643 return OpenIdx; 644} 645 646void SplitEditor::selectIntv(unsigned Idx) { 647 assert(Idx != 0 && "Cannot select the complement interval"); 648 assert(Idx < Edit->size() && "Can only select previously opened interval"); 649 DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); 650 OpenIdx = Idx; 651} 652 653SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 654 assert(OpenIdx && "openIntv not called before enterIntvBefore"); 655 DEBUG(dbgs() << " enterIntvBefore " << Idx); 656 Idx = Idx.getBaseIndex(); 657 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 658 if (!ParentVNI) { 659 DEBUG(dbgs() << ": not live\n"); 660 return Idx; 661 } 662 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 663 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 664 assert(MI && "enterIntvBefore called with invalid index"); 665 666 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 667 return VNI->def; 668} 669 670SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { 671 assert(OpenIdx && "openIntv not called before enterIntvAfter"); 672 DEBUG(dbgs() << " enterIntvAfter " << Idx); 673 Idx = Idx.getBoundaryIndex(); 674 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 675 if (!ParentVNI) { 676 DEBUG(dbgs() << ": not live\n"); 677 return Idx; 678 } 679 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 680 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 681 assert(MI && "enterIntvAfter called with invalid index"); 682 683 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), 684 llvm::next(MachineBasicBlock::iterator(MI))); 685 return VNI->def; 686} 687 688SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 689 assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 690 SlotIndex End = LIS.getMBBEndIdx(&MBB); 691 SlotIndex Last = End.getPrevSlot(); 692 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 693 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 694 if (!ParentVNI) { 695 DEBUG(dbgs() << ": not live\n"); 696 return End; 697 } 698 DEBUG(dbgs() << ": valno " << ParentVNI->id); 699 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 700 LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 701 RegAssign.insert(VNI->def, End, OpenIdx); 702 DEBUG(dump()); 703 return VNI->def; 704} 705 706/// useIntv - indicate that all instructions in MBB should use OpenLI. 707void SplitEditor::useIntv(const MachineBasicBlock &MBB) { 708 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 709} 710 711void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 712 assert(OpenIdx && "openIntv not called before useIntv"); 713 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 714 RegAssign.insert(Start, End, OpenIdx); 715 DEBUG(dump()); 716} 717 718SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 719 assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 720 DEBUG(dbgs() << " leaveIntvAfter " << Idx); 721 722 // The interval must be live beyond the instruction at Idx. 723 Idx = Idx.getBoundaryIndex(); 724 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 725 if (!ParentVNI) { 726 DEBUG(dbgs() << ": not live\n"); 727 return Idx.getNextSlot(); 728 } 729 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 730 731 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 732 assert(MI && "No instruction at index"); 733 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 734 llvm::next(MachineBasicBlock::iterator(MI))); 735 return VNI->def; 736} 737 738SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 739 assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 740 DEBUG(dbgs() << " leaveIntvBefore " << Idx); 741 742 // The interval must be live into the instruction at Idx. 743 Idx = Idx.getBaseIndex(); 744 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 745 if (!ParentVNI) { 746 DEBUG(dbgs() << ": not live\n"); 747 return Idx.getNextSlot(); 748 } 749 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 750 751 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 752 assert(MI && "No instruction at index"); 753 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 754 return VNI->def; 755} 756 757SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 758 assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 759 SlotIndex Start = LIS.getMBBStartIdx(&MBB); 760 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 761 762 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 763 if (!ParentVNI) { 764 DEBUG(dbgs() << ": not live\n"); 765 return Start; 766 } 767 768 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 769 MBB.SkipPHIsAndLabels(MBB.begin())); 770 RegAssign.insert(Start, VNI->def, OpenIdx); 771 DEBUG(dump()); 772 return VNI->def; 773} 774 775void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 776 assert(OpenIdx && "openIntv not called before overlapIntv"); 777 const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 778 assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 779 "Parent changes value in extended range"); 780 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 781 "Range cannot span basic blocks"); 782 783 // The complement interval will be extended as needed by extendRange(). 784 if (ParentVNI) 785 markComplexMapped(0, ParentVNI); 786 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 787 RegAssign.insert(Start, End, OpenIdx); 788 DEBUG(dump()); 789} 790 791/// transferValues - Transfer all possible values to the new live ranges. 792/// Values that were rematerialized are left alone, they need extendRange(). 793bool SplitEditor::transferValues() { 794 bool Skipped = false; 795 LiveInBlocks.clear(); 796 RegAssignMap::const_iterator AssignI = RegAssign.begin(); 797 for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 798 ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 799 DEBUG(dbgs() << " blit " << *ParentI << ':'); 800 VNInfo *ParentVNI = ParentI->valno; 801 // RegAssign has holes where RegIdx 0 should be used. 802 SlotIndex Start = ParentI->start; 803 AssignI.advanceTo(Start); 804 do { 805 unsigned RegIdx; 806 SlotIndex End = ParentI->end; 807 if (!AssignI.valid()) { 808 RegIdx = 0; 809 } else if (AssignI.start() <= Start) { 810 RegIdx = AssignI.value(); 811 if (AssignI.stop() < End) { 812 End = AssignI.stop(); 813 ++AssignI; 814 } 815 } else { 816 RegIdx = 0; 817 End = std::min(End, AssignI.start()); 818 } 819 820 // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 821 DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 822 LiveInterval *LI = Edit->get(RegIdx); 823 824 // Check for a simply defined value that can be blitted directly. 825 if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 826 DEBUG(dbgs() << ':' << VNI->id); 827 LI->addRange(LiveRange(Start, End, VNI)); 828 Start = End; 829 continue; 830 } 831 832 // Skip rematerialized values, we need to use extendRange() and 833 // extendPHIKillRanges() to completely recompute the live ranges. 834 if (Edit->didRematerialize(ParentVNI)) { 835 DEBUG(dbgs() << "(remat)"); 836 Skipped = true; 837 Start = End; 838 continue; 839 } 840 841 // Initialize the live-out cache the first time it is needed. 842 if (LiveOutSeen.empty()) { 843 unsigned N = VRM.getMachineFunction().getNumBlockIDs(); 844 LiveOutSeen.resize(N); 845 LiveOutCache.resize(N); 846 } 847 848 // This value has multiple defs in RegIdx, but it wasn't rematerialized, 849 // so the live range is accurate. Add live-in blocks in [Start;End) to the 850 // LiveInBlocks. 851 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 852 SlotIndex BlockStart, BlockEnd; 853 tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 854 855 // The first block may be live-in, or it may have its own def. 856 if (Start != BlockStart) { 857 VNInfo *VNI = LI->extendInBlock(BlockStart, 858 std::min(BlockEnd, End).getPrevSlot()); 859 assert(VNI && "Missing def for complex mapped value"); 860 DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 861 // MBB has its own def. Is it also live-out? 862 if (BlockEnd <= End) { 863 LiveOutSeen.set(MBB->getNumber()); 864 LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]); 865 } 866 // Skip to the next block for live-in. 867 ++MBB; 868 BlockStart = BlockEnd; 869 } 870 871 // Handle the live-in blocks covered by [Start;End). 872 assert(Start <= BlockStart && "Expected live-in block"); 873 while (BlockStart < End) { 874 DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 875 BlockEnd = LIS.getMBBEndIdx(MBB); 876 if (BlockStart == ParentVNI->def) { 877 // This block has the def of a parent PHI, so it isn't live-in. 878 assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 879 VNInfo *VNI = LI->extendInBlock(BlockStart, 880 std::min(BlockEnd, End).getPrevSlot()); 881 assert(VNI && "Missing def for complex mapped parent PHI"); 882 if (End >= BlockEnd) { 883 // Live-out as well. 884 LiveOutSeen.set(MBB->getNumber()); 885 LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]); 886 } 887 } else { 888 // This block needs a live-in value. 889 LiveInBlocks.push_back(MDT[MBB]); 890 // The last block covered may not be live-out. 891 if (End < BlockEnd) 892 LiveInBlocks.back().Kill = End; 893 else { 894 // Live-out, but we need updateSSA to tell us the value. 895 LiveOutSeen.set(MBB->getNumber()); 896 LiveOutCache[MBB] = LiveOutPair((VNInfo*)0, 897 (MachineDomTreeNode*)0); 898 } 899 } 900 BlockStart = BlockEnd; 901 ++MBB; 902 } 903 Start = End; 904 } while (Start != ParentI->end); 905 DEBUG(dbgs() << '\n'); 906 } 907 908 if (!LiveInBlocks.empty()) 909 updateSSA(); 910 911 return Skipped; 912} 913 914void SplitEditor::extendPHIKillRanges() { 915 // Extend live ranges to be live-out for successor PHI values. 916 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 917 E = Edit->getParent().vni_end(); I != E; ++I) { 918 const VNInfo *PHIVNI = *I; 919 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 920 continue; 921 unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 922 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 923 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 924 PE = MBB->pred_end(); PI != PE; ++PI) { 925 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 926 // The predecessor may not have a live-out value. That is OK, like an 927 // undef PHI operand. 928 if (Edit->getParent().liveAt(End)) { 929 assert(RegAssign.lookup(End) == RegIdx && 930 "Different register assignment in phi predecessor"); 931 extendRange(RegIdx, End); 932 } 933 } 934 } 935} 936 937/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 938void SplitEditor::rewriteAssigned(bool ExtendRanges) { 939 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 940 RE = MRI.reg_end(); RI != RE;) { 941 MachineOperand &MO = RI.getOperand(); 942 MachineInstr *MI = MO.getParent(); 943 ++RI; 944 // LiveDebugVariables should have handled all DBG_VALUE instructions. 945 if (MI->isDebugValue()) { 946 DEBUG(dbgs() << "Zapping " << *MI); 947 MO.setReg(0); 948 continue; 949 } 950 951 // <undef> operands don't really read the register, so it doesn't matter 952 // which register we choose. When the use operand is tied to a def, we must 953 // use the same register as the def, so just do that always. 954 SlotIndex Idx = LIS.getInstructionIndex(MI); 955 if (MO.isDef() || MO.isUndef()) 956 Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex(); 957 958 // Rewrite to the mapped register at Idx. 959 unsigned RegIdx = RegAssign.lookup(Idx); 960 MO.setReg(Edit->get(RegIdx)->reg); 961 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 962 << Idx << ':' << RegIdx << '\t' << *MI); 963 964 // Extend liveness to Idx if the instruction reads reg. 965 if (!ExtendRanges || MO.isUndef()) 966 continue; 967 968 // Skip instructions that don't read Reg. 969 if (MO.isDef()) { 970 if (!MO.getSubReg() && !MO.isEarlyClobber()) 971 continue; 972 // We may wan't to extend a live range for a partial redef, or for a use 973 // tied to an early clobber. 974 Idx = Idx.getPrevSlot(); 975 if (!Edit->getParent().liveAt(Idx)) 976 continue; 977 } else 978 Idx = Idx.getUseIndex(); 979 980 extendRange(RegIdx, Idx); 981 } 982} 983 984void SplitEditor::deleteRematVictims() { 985 SmallVector<MachineInstr*, 8> Dead; 986 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 987 LiveInterval *LI = *I; 988 for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 989 LII != LIE; ++LII) { 990 // Dead defs end at the store slot. 991 if (LII->end != LII->valno->def.getNextSlot()) 992 continue; 993 MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 994 assert(MI && "Missing instruction for dead def"); 995 MI->addRegisterDead(LI->reg, &TRI); 996 997 if (!MI->allDefsAreDead()) 998 continue; 999 1000 DEBUG(dbgs() << "All defs dead: " << *MI); 1001 Dead.push_back(MI); 1002 } 1003 } 1004 1005 if (Dead.empty()) 1006 return; 1007 1008 Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); 1009} 1010 1011void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 1012 ++NumFinished; 1013 1014 // At this point, the live intervals in Edit contain VNInfos corresponding to 1015 // the inserted copies. 1016 1017 // Add the original defs from the parent interval. 1018 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 1019 E = Edit->getParent().vni_end(); I != E; ++I) { 1020 const VNInfo *ParentVNI = *I; 1021 if (ParentVNI->isUnused()) 1022 continue; 1023 unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 1024 VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 1025 VNI->setIsPHIDef(ParentVNI->isPHIDef()); 1026 VNI->setCopy(ParentVNI->getCopy()); 1027 1028 // Mark rematted values as complex everywhere to force liveness computation. 1029 // The new live ranges may be truncated. 1030 if (Edit->didRematerialize(ParentVNI)) 1031 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1032 markComplexMapped(i, ParentVNI); 1033 } 1034 1035 // Transfer the simply mapped values, check if any are skipped. 1036 bool Skipped = transferValues(); 1037 if (Skipped) 1038 extendPHIKillRanges(); 1039 else 1040 ++NumSimple; 1041 1042 // Rewrite virtual registers, possibly extending ranges. 1043 rewriteAssigned(Skipped); 1044 1045 // Delete defs that were rematted everywhere. 1046 if (Skipped) 1047 deleteRematVictims(); 1048 1049 // Get rid of unused values and set phi-kill flags. 1050 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 1051 (*I)->RenumberValues(LIS); 1052 1053 // Provide a reverse mapping from original indices to Edit ranges. 1054 if (LRMap) { 1055 LRMap->clear(); 1056 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1057 LRMap->push_back(i); 1058 } 1059 1060 // Now check if any registers were separated into multiple components. 1061 ConnectedVNInfoEqClasses ConEQ(LIS); 1062 for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 1063 // Don't use iterators, they are invalidated by create() below. 1064 LiveInterval *li = Edit->get(i); 1065 unsigned NumComp = ConEQ.Classify(li); 1066 if (NumComp <= 1) 1067 continue; 1068 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 1069 SmallVector<LiveInterval*, 8> dups; 1070 dups.push_back(li); 1071 for (unsigned j = 1; j != NumComp; ++j) 1072 dups.push_back(&Edit->create(LIS, VRM)); 1073 ConEQ.Distribute(&dups[0], MRI); 1074 // The new intervals all map back to i. 1075 if (LRMap) 1076 LRMap->resize(Edit->size(), i); 1077 } 1078 1079 // Calculate spill weight and allocation hints for new intervals. 1080 Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops); 1081 1082 assert(!LRMap || LRMap->size() == Edit->size()); 1083} 1084 1085 1086//===----------------------------------------------------------------------===// 1087// Single Block Splitting 1088//===----------------------------------------------------------------------===// 1089 1090/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 1091/// may be an advantage to split CurLI for the duration of the block. 1092bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 1093 // If CurLI is local to one block, there is no point to splitting it. 1094 if (UseBlocks.size() <= 1) 1095 return false; 1096 // Add blocks with multiple uses. 1097 for (unsigned i = 0, e = UseBlocks.size(); i != e; ++i) { 1098 const BlockInfo &BI = UseBlocks[i]; 1099 if (BI.FirstUse == BI.LastUse) 1100 continue; 1101 Blocks.insert(BI.MBB); 1102 } 1103 return !Blocks.empty(); 1104} 1105 1106void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 1107 openIntv(); 1108 SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 1109 SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstUse, 1110 LastSplitPoint)); 1111 if (!BI.LiveOut || BI.LastUse < LastSplitPoint) { 1112 useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 1113 } else { 1114 // The last use is after the last valid split point. 1115 SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 1116 useIntv(SegStart, SegStop); 1117 overlapIntv(SegStop, BI.LastUse); 1118 } 1119} 1120 1121/// splitSingleBlocks - Split CurLI into a separate live interval inside each 1122/// basic block in Blocks. 1123void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 1124 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 1125 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA.getUseBlocks(); 1126 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1127 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1128 if (Blocks.count(BI.MBB)) 1129 splitSingleBlock(BI); 1130 } 1131 finish(); 1132} 1133 1134 1135//===----------------------------------------------------------------------===// 1136// Global Live Range Splitting Support 1137//===----------------------------------------------------------------------===// 1138 1139// These methods support a method of global live range splitting that uses a 1140// global algorithm to decide intervals for CFG edges. They will insert split 1141// points and color intervals in basic blocks while avoiding interference. 1142// 1143// Note that splitSingleBlock is also useful for blocks where both CFG edges 1144// are on the stack. 1145 1146void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, 1147 unsigned IntvIn, SlotIndex LeaveBefore, 1148 unsigned IntvOut, SlotIndex EnterAfter){ 1149 SlotIndex Start, Stop; 1150 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); 1151 1152 DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop 1153 << ") intf " << LeaveBefore << '-' << EnterAfter 1154 << ", live-through " << IntvIn << " -> " << IntvOut); 1155 1156 assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks"); 1157 1158 assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block"); 1159 assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf"); 1160 assert((!EnterAfter || EnterAfter >= Start) && "Interference before block"); 1161 1162 MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); 1163 1164 if (!IntvOut) { 1165 DEBUG(dbgs() << ", spill on entry.\n"); 1166 // 1167 // <<<<<<<<< Possible LeaveBefore interference. 1168 // |-----------| Live through. 1169 // -____________ Spill on entry. 1170 // 1171 selectIntv(IntvIn); 1172 SlotIndex Idx = leaveIntvAtTop(*MBB); 1173 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1174 (void)Idx; 1175 return; 1176 } 1177 1178 if (!IntvIn) { 1179 DEBUG(dbgs() << ", reload on exit.\n"); 1180 // 1181 // >>>>>>> Possible EnterAfter interference. 1182 // |-----------| Live through. 1183 // ___________-- Reload on exit. 1184 // 1185 selectIntv(IntvOut); 1186 SlotIndex Idx = enterIntvAtEnd(*MBB); 1187 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1188 (void)Idx; 1189 return; 1190 } 1191 1192 if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { 1193 DEBUG(dbgs() << ", straight through.\n"); 1194 // 1195 // |-----------| Live through. 1196 // ------------- Straight through, same intv, no interference. 1197 // 1198 selectIntv(IntvOut); 1199 useIntv(Start, Stop); 1200 return; 1201 } 1202 1203 // We cannot legally insert splits after LSP. 1204 SlotIndex LSP = SA.getLastSplitPoint(MBBNum); 1205 assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf"); 1206 1207 if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || 1208 LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { 1209 DEBUG(dbgs() << ", switch avoiding interference.\n"); 1210 // 1211 // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. 1212 // |-----------| Live through. 1213 // ------======= Switch intervals between interference. 1214 // 1215 selectIntv(IntvOut); 1216 SlotIndex Idx; 1217 if (LeaveBefore && LeaveBefore < LSP) { 1218 Idx = enterIntvBefore(LeaveBefore); 1219 useIntv(Idx, Stop); 1220 } else { 1221 Idx = enterIntvAtEnd(*MBB); 1222 } 1223 selectIntv(IntvIn); 1224 useIntv(Start, Idx); 1225 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1226 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1227 return; 1228 } 1229 1230 DEBUG(dbgs() << ", create local intv for interference.\n"); 1231 // 1232 // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. 1233 // |-----------| Live through. 1234 // ==---------== Switch intervals before/after interference. 1235 // 1236 assert(LeaveBefore <= EnterAfter && "Missed case"); 1237 1238 selectIntv(IntvOut); 1239 SlotIndex Idx = enterIntvAfter(EnterAfter); 1240 useIntv(Idx, Stop); 1241 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1242 1243 selectIntv(IntvIn); 1244 Idx = leaveIntvBefore(LeaveBefore); 1245 useIntv(Start, Idx); 1246 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1247} 1248 1249 1250void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 1251 unsigned IntvIn, SlotIndex LeaveBefore) { 1252 SlotIndex Start, Stop; 1253 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1254 1255 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1256 << "), uses " << BI.FirstUse << '-' << BI.LastUse 1257 << ", reg-in " << IntvIn << ", leave before " << LeaveBefore 1258 << (BI.LiveOut ? ", stack-out" : ", killed in block")); 1259 1260 assert(IntvIn && "Must have register in"); 1261 assert(BI.LiveIn && "Must be live-in"); 1262 assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference"); 1263 1264 if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastUse)) { 1265 DEBUG(dbgs() << " before interference.\n"); 1266 // 1267 // <<< Interference after kill. 1268 // |---o---x | Killed in block. 1269 // ========= Use IntvIn everywhere. 1270 // 1271 selectIntv(IntvIn); 1272 useIntv(Start, BI.LastUse); 1273 return; 1274 } 1275 1276 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1277 1278 if (!LeaveBefore || LeaveBefore > BI.LastUse.getBoundaryIndex()) { 1279 // 1280 // <<< Possible interference after last use. 1281 // |---o---o---| Live-out on stack. 1282 // =========____ Leave IntvIn after last use. 1283 // 1284 // < Interference after last use. 1285 // |---o---o--o| Live-out on stack, late last use. 1286 // ============ Copy to stack after LSP, overlap IntvIn. 1287 // \_____ Stack interval is live-out. 1288 // 1289 if (BI.LastUse < LSP) { 1290 DEBUG(dbgs() << ", spill after last use before interference.\n"); 1291 selectIntv(IntvIn); 1292 SlotIndex Idx = leaveIntvAfter(BI.LastUse); 1293 useIntv(Start, Idx); 1294 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1295 } else { 1296 DEBUG(dbgs() << ", spill before last split point.\n"); 1297 selectIntv(IntvIn); 1298 SlotIndex Idx = leaveIntvBefore(LSP); 1299 overlapIntv(Idx, BI.LastUse); 1300 useIntv(Start, Idx); 1301 assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1302 } 1303 return; 1304 } 1305 1306 // The interference is overlapping somewhere we wanted to use IntvIn. That 1307 // means we need to create a local interval that can be allocated a 1308 // different register. 1309 unsigned LocalIntv = openIntv(); 1310 (void)LocalIntv; 1311 DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n"); 1312 1313 if (!BI.LiveOut || BI.LastUse < LSP) { 1314 // 1315 // <<<<<<< Interference overlapping uses. 1316 // |---o---o---| Live-out on stack. 1317 // =====----____ Leave IntvIn before interference, then spill. 1318 // 1319 SlotIndex To = leaveIntvAfter(BI.LastUse); 1320 SlotIndex From = enterIntvBefore(LeaveBefore); 1321 useIntv(From, To); 1322 selectIntv(IntvIn); 1323 useIntv(Start, From); 1324 assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1325 return; 1326 } 1327 1328 // <<<<<<< Interference overlapping uses. 1329 // |---o---o--o| Live-out on stack, late last use. 1330 // =====------- Copy to stack before LSP, overlap LocalIntv. 1331 // \_____ Stack interval is live-out. 1332 // 1333 SlotIndex To = leaveIntvBefore(LSP); 1334 overlapIntv(To, BI.LastUse); 1335 SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); 1336 useIntv(From, To); 1337 selectIntv(IntvIn); 1338 useIntv(Start, From); 1339 assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1340} 1341 1342void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 1343 unsigned IntvOut, SlotIndex EnterAfter) { 1344 SlotIndex Start, Stop; 1345 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1346 1347 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1348 << "), uses " << BI.FirstUse << '-' << BI.LastUse 1349 << ", reg-out " << IntvOut << ", enter after " << EnterAfter 1350 << (BI.LiveIn ? ", stack-in" : ", defined in block")); 1351 1352 SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1353 1354 assert(IntvOut && "Must have register out"); 1355 assert(BI.LiveOut && "Must be live-out"); 1356 assert((!EnterAfter || EnterAfter < LSP) && "Bad interference"); 1357 1358 if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstUse)) { 1359 DEBUG(dbgs() << " after interference.\n"); 1360 // 1361 // >>>> Interference before def. 1362 // | o---o---| Defined in block. 1363 // ========= Use IntvOut everywhere. 1364 // 1365 selectIntv(IntvOut); 1366 useIntv(BI.FirstUse, Stop); 1367 return; 1368 } 1369 1370 if (!EnterAfter || EnterAfter < BI.FirstUse.getBaseIndex()) { 1371 DEBUG(dbgs() << ", reload after interference.\n"); 1372 // 1373 // >>>> Interference before def. 1374 // |---o---o---| Live-through, stack-in. 1375 // ____========= Enter IntvOut before first use. 1376 // 1377 selectIntv(IntvOut); 1378 SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstUse)); 1379 useIntv(Idx, Stop); 1380 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1381 return; 1382 } 1383 1384 // The interference is overlapping somewhere we wanted to use IntvOut. That 1385 // means we need to create a local interval that can be allocated a 1386 // different register. 1387 DEBUG(dbgs() << ", interference overlaps uses.\n"); 1388 // 1389 // >>>>>>> Interference overlapping uses. 1390 // |---o---o---| Live-through, stack-in. 1391 // ____---====== Create local interval for interference range. 1392 // 1393 selectIntv(IntvOut); 1394 SlotIndex Idx = enterIntvAfter(EnterAfter); 1395 useIntv(Idx, Stop); 1396 assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1397 1398 openIntv(); 1399 SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstUse)); 1400 useIntv(From, Idx); 1401} 1402