SplitKit.cpp revision 1e0bd63477da6e9b1dc5111bafba2b1cf143bfba
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 // Look for gaps in the live range. 192 BI.LiveOut = true; 193 while (LVI->end < Stop) { 194 SlotIndex LastStop = LVI->end; 195 if (++LVI == LVE || LVI->start >= Stop) { 196 BI.LiveOut = false; 197 BI.LastUse = LastStop; 198 break; 199 } 200 if (LastStop < LVI->start) { 201 // There is a gap in the live range. Create duplicate entries for the 202 // live-in snippet and the live-out snippet. 203 ++NumGapBlocks; 204 205 // Push the Live-in part. 206 BI.LiveThrough = false; 207 BI.LiveOut = false; 208 UseBlocks.push_back(BI); 209 UseBlocks.back().LastUse = LastStop; 210 211 // Set up BI for the live-out part. 212 BI.LiveIn = false; 213 BI.LiveOut = true; 214 BI.FirstUse = LVI->start; 215 } 216 } 217 218 // Don't set LiveThrough when the block has a gap. 219 BI.LiveThrough = BI.LiveIn && BI.LiveOut; 220 UseBlocks.push_back(BI); 221 222 // LVI is now at LVE or LVI->end >= Stop. 223 if (LVI == LVE) 224 break; 225 } 226 227 // Live segment ends exactly at Stop. Move to the next segment. 228 if (LVI->end == Stop && ++LVI == LVE) 229 break; 230 231 // Pick the next basic block. 232 if (LVI->start < Stop) 233 ++MFI; 234 else 235 MFI = LIS.getMBBFromIndex(LVI->start); 236 } 237 238 assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count"); 239 return true; 240} 241 242unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { 243 if (cli->empty()) 244 return 0; 245 LiveInterval *li = const_cast<LiveInterval*>(cli); 246 LiveInterval::iterator LVI = li->begin(); 247 LiveInterval::iterator LVE = li->end(); 248 unsigned Count = 0; 249 250 // Loop over basic blocks where li is live. 251 MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start); 252 SlotIndex Stop = LIS.getMBBEndIdx(MFI); 253 for (;;) { 254 ++Count; 255 LVI = li->advanceTo(LVI, Stop); 256 if (LVI == LVE) 257 return Count; 258 do { 259 ++MFI; 260 Stop = LIS.getMBBEndIdx(MFI); 261 } while (Stop <= LVI->start); 262 } 263} 264 265bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 266 unsigned OrigReg = VRM.getOriginal(CurLI->reg); 267 const LiveInterval &Orig = LIS.getInterval(OrigReg); 268 assert(!Orig.empty() && "Splitting empty interval?"); 269 LiveInterval::const_iterator I = Orig.find(Idx); 270 271 // Range containing Idx should begin at Idx. 272 if (I != Orig.end() && I->start <= Idx) 273 return I->start == Idx; 274 275 // Range does not contain Idx, previous must end at Idx. 276 return I != Orig.begin() && (--I)->end == Idx; 277} 278 279void SplitAnalysis::analyze(const LiveInterval *li) { 280 clear(); 281 CurLI = li; 282 analyzeUses(); 283} 284 285 286//===----------------------------------------------------------------------===// 287// Split Editor 288//===----------------------------------------------------------------------===// 289 290/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 291SplitEditor::SplitEditor(SplitAnalysis &sa, 292 LiveIntervals &lis, 293 VirtRegMap &vrm, 294 MachineDominatorTree &mdt) 295 : SA(sa), LIS(lis), VRM(vrm), 296 MRI(vrm.getMachineFunction().getRegInfo()), 297 MDT(mdt), 298 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 299 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 300 Edit(0), 301 OpenIdx(0), 302 RegAssign(Allocator) 303{} 304 305void SplitEditor::reset(LiveRangeEdit &lre) { 306 Edit = &lre; 307 OpenIdx = 0; 308 RegAssign.clear(); 309 Values.clear(); 310 311 // We don't need to clear LiveOutCache, only LiveOutSeen entries are read. 312 LiveOutSeen.clear(); 313 314 // We don't need an AliasAnalysis since we will only be performing 315 // cheap-as-a-copy remats anyway. 316 Edit->anyRematerializable(LIS, TII, 0); 317} 318 319void SplitEditor::dump() const { 320 if (RegAssign.empty()) { 321 dbgs() << " empty\n"; 322 return; 323 } 324 325 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 326 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 327 dbgs() << '\n'; 328} 329 330VNInfo *SplitEditor::defValue(unsigned RegIdx, 331 const VNInfo *ParentVNI, 332 SlotIndex Idx) { 333 assert(ParentVNI && "Mapping NULL value"); 334 assert(Idx.isValid() && "Invalid SlotIndex"); 335 assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 336 LiveInterval *LI = Edit->get(RegIdx); 337 338 // Create a new value. 339 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 340 341 // Use insert for lookup, so we can add missing values with a second lookup. 342 std::pair<ValueMap::iterator, bool> InsP = 343 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 344 345 // This was the first time (RegIdx, ParentVNI) was mapped. 346 // Keep it as a simple def without any liveness. 347 if (InsP.second) 348 return VNI; 349 350 // If the previous value was a simple mapping, add liveness for it now. 351 if (VNInfo *OldVNI = InsP.first->second) { 352 SlotIndex Def = OldVNI->def; 353 LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 354 // No longer a simple mapping. 355 InsP.first->second = 0; 356 } 357 358 // This is a complex mapping, add liveness for VNI 359 SlotIndex Def = VNI->def; 360 LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 361 362 return VNI; 363} 364 365void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 366 assert(ParentVNI && "Mapping NULL value"); 367 VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 368 369 // ParentVNI was either unmapped or already complex mapped. Either way. 370 if (!VNI) 371 return; 372 373 // This was previously a single mapping. Make sure the old def is represented 374 // by a trivial live range. 375 SlotIndex Def = VNI->def; 376 Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 377 VNI = 0; 378} 379 380// extendRange - Extend the live range to reach Idx. 381// Potentially create phi-def values. 382void SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 383 assert(Idx.isValid() && "Invalid SlotIndex"); 384 MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 385 assert(IdxMBB && "No MBB at Idx"); 386 LiveInterval *LI = Edit->get(RegIdx); 387 388 // Is there a def in the same MBB we can extend? 389 if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx)) 390 return; 391 392 // Now for the fun part. We know that ParentVNI potentially has multiple defs, 393 // and we may need to create even more phi-defs to preserve VNInfo SSA form. 394 // Perform a search for all predecessor blocks where we know the dominating 395 // VNInfo. 396 VNInfo *VNI = findReachingDefs(LI, IdxMBB, Idx.getNextSlot()); 397 398 // When there were multiple different values, we may need new PHIs. 399 if (!VNI) 400 return updateSSA(); 401 402 // Poor man's SSA update for the single-value case. 403 LiveOutPair LOP(VNI, MDT[LIS.getMBBFromIndex(VNI->def)]); 404 for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 405 E = LiveInBlocks.end(); I != E; ++I) { 406 MachineBasicBlock *MBB = I->DomNode->getBlock(); 407 SlotIndex Start = LIS.getMBBStartIdx(MBB); 408 if (I->Kill.isValid()) 409 LI->addRange(LiveRange(Start, I->Kill, VNI)); 410 else { 411 LiveOutCache[MBB] = LOP; 412 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 413 } 414 } 415} 416 417/// findReachingDefs - Search the CFG for known live-out values. 418/// Add required live-in blocks to LiveInBlocks. 419VNInfo *SplitEditor::findReachingDefs(LiveInterval *LI, 420 MachineBasicBlock *KillMBB, 421 SlotIndex Kill) { 422 // Initialize the live-out cache the first time it is needed. 423 if (LiveOutSeen.empty()) { 424 unsigned N = VRM.getMachineFunction().getNumBlockIDs(); 425 LiveOutSeen.resize(N); 426 LiveOutCache.resize(N); 427 } 428 429 // Blocks where LI should be live-in. 430 SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB); 431 432 // Remember if we have seen more than one value. 433 bool UniqueVNI = true; 434 VNInfo *TheVNI = 0; 435 436 // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 437 for (unsigned i = 0; i != WorkList.size(); ++i) { 438 MachineBasicBlock *MBB = WorkList[i]; 439 assert(!MBB->pred_empty() && "Value live-in to entry block?"); 440 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 441 PE = MBB->pred_end(); PI != PE; ++PI) { 442 MachineBasicBlock *Pred = *PI; 443 LiveOutPair &LOP = LiveOutCache[Pred]; 444 445 // Is this a known live-out block? 446 if (LiveOutSeen.test(Pred->getNumber())) { 447 if (VNInfo *VNI = LOP.first) { 448 if (TheVNI && TheVNI != VNI) 449 UniqueVNI = false; 450 TheVNI = VNI; 451 } 452 continue; 453 } 454 455 // First time. LOP is garbage and must be cleared below. 456 LiveOutSeen.set(Pred->getNumber()); 457 458 // Does Pred provide a live-out value? 459 SlotIndex Start, Last; 460 tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred); 461 Last = Last.getPrevSlot(); 462 VNInfo *VNI = LI->extendInBlock(Start, Last); 463 LOP.first = VNI; 464 if (VNI) { 465 LOP.second = MDT[LIS.getMBBFromIndex(VNI->def)]; 466 if (TheVNI && TheVNI != VNI) 467 UniqueVNI = false; 468 TheVNI = VNI; 469 continue; 470 } 471 LOP.second = 0; 472 473 // No, we need a live-in value for Pred as well 474 if (Pred != KillMBB) 475 WorkList.push_back(Pred); 476 else 477 // Loopback to KillMBB, so value is really live through. 478 Kill = SlotIndex(); 479 } 480 } 481 482 // Transfer WorkList to LiveInBlocks in reverse order. 483 // This ordering works best with updateSSA(). 484 LiveInBlocks.clear(); 485 LiveInBlocks.reserve(WorkList.size()); 486 while(!WorkList.empty()) 487 LiveInBlocks.push_back(MDT[WorkList.pop_back_val()]); 488 489 // The kill block may not be live-through. 490 assert(LiveInBlocks.back().DomNode->getBlock() == KillMBB); 491 LiveInBlocks.back().Kill = Kill; 492 493 return UniqueVNI ? TheVNI : 0; 494} 495 496void SplitEditor::updateSSA() { 497 // This is essentially the same iterative algorithm that SSAUpdater uses, 498 // except we already have a dominator tree, so we don't have to recompute it. 499 unsigned Changes; 500 do { 501 Changes = 0; 502 // Propagate live-out values down the dominator tree, inserting phi-defs 503 // when necessary. 504 for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 505 E = LiveInBlocks.end(); I != E; ++I) { 506 MachineDomTreeNode *Node = I->DomNode; 507 // Skip block if the live-in value has already been determined. 508 if (!Node) 509 continue; 510 MachineBasicBlock *MBB = Node->getBlock(); 511 MachineDomTreeNode *IDom = Node->getIDom(); 512 LiveOutPair IDomValue; 513 514 // We need a live-in value to a block with no immediate dominator? 515 // This is probably an unreachable block that has survived somehow. 516 bool needPHI = !IDom || !LiveOutSeen.test(IDom->getBlock()->getNumber()); 517 518 // IDom dominates all of our predecessors, but it may not be their 519 // immediate dominator. Check if any of them have live-out values that are 520 // properly dominated by IDom. If so, we need a phi-def here. 521 if (!needPHI) { 522 IDomValue = LiveOutCache[IDom->getBlock()]; 523 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 524 PE = MBB->pred_end(); PI != PE; ++PI) { 525 LiveOutPair Value = LiveOutCache[*PI]; 526 if (!Value.first || Value.first == IDomValue.first) 527 continue; 528 // This predecessor is carrying something other than IDomValue. 529 // It could be because IDomValue hasn't propagated yet, or it could be 530 // because MBB is in the dominance frontier of that value. 531 if (MDT.dominates(IDom, Value.second)) { 532 needPHI = true; 533 break; 534 } 535 } 536 } 537 538 // The value may be live-through even if Kill is set, as can happen when 539 // we are called from extendRange. In that case LiveOutSeen is true, and 540 // LiveOutCache indicates a foreign or missing value. 541 LiveOutPair &LOP = LiveOutCache[MBB]; 542 543 // Create a phi-def if required. 544 if (needPHI) { 545 ++Changes; 546 SlotIndex Start = LIS.getMBBStartIdx(MBB); 547 unsigned RegIdx = RegAssign.lookup(Start); 548 LiveInterval *LI = Edit->get(RegIdx); 549 VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 550 VNI->setIsPHIDef(true); 551 I->Value = VNI; 552 // This block is done, we know the final value. 553 I->DomNode = 0; 554 if (I->Kill.isValid()) 555 LI->addRange(LiveRange(Start, I->Kill, VNI)); 556 else { 557 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 558 LOP = LiveOutPair(VNI, Node); 559 } 560 } else if (IDomValue.first) { 561 // No phi-def here. Remember incoming value. 562 I->Value = IDomValue.first; 563 if (I->Kill.isValid()) 564 continue; 565 // Propagate IDomValue if needed: 566 // MBB is live-out and doesn't define its own value. 567 if (LOP.second != Node && LOP.first != IDomValue.first) { 568 ++Changes; 569 LOP = IDomValue; 570 } 571 } 572 } 573 } while (Changes); 574 575 // The values in LiveInBlocks are now accurate. No more phi-defs are needed 576 // for these blocks, so we can color the live ranges. 577 for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 578 E = LiveInBlocks.end(); I != E; ++I) { 579 if (!I->DomNode) 580 continue; 581 assert(I->Value && "No live-in value found"); 582 MachineBasicBlock *MBB = I->DomNode->getBlock(); 583 SlotIndex Start = LIS.getMBBStartIdx(MBB); 584 unsigned RegIdx = RegAssign.lookup(Start); 585 LiveInterval *LI = Edit->get(RegIdx); 586 LI->addRange(LiveRange(Start, I->Kill.isValid() ? 587 I->Kill : LIS.getMBBEndIdx(MBB), I->Value)); 588 } 589} 590 591VNInfo *SplitEditor::defFromParent(unsigned RegIdx, 592 VNInfo *ParentVNI, 593 SlotIndex UseIdx, 594 MachineBasicBlock &MBB, 595 MachineBasicBlock::iterator I) { 596 MachineInstr *CopyMI = 0; 597 SlotIndex Def; 598 LiveInterval *LI = Edit->get(RegIdx); 599 600 // We may be trying to avoid interference that ends at a deleted instruction, 601 // so always begin RegIdx 0 early and all others late. 602 bool Late = RegIdx != 0; 603 604 // Attempt cheap-as-a-copy rematerialization. 605 LiveRangeEdit::Remat RM(ParentVNI); 606 if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 607 Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late); 608 ++NumRemats; 609 } else { 610 // Can't remat, just insert a copy from parent. 611 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 612 .addReg(Edit->getReg()); 613 Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) 614 .getDefIndex(); 615 ++NumCopies; 616 } 617 618 // Define the value in Reg. 619 VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 620 VNI->setCopy(CopyMI); 621 return VNI; 622} 623 624/// Create a new virtual register and live interval. 625unsigned SplitEditor::openIntv() { 626 // Create the complement as index 0. 627 if (Edit->empty()) 628 Edit->create(LIS, VRM); 629 630 // Create the open interval. 631 OpenIdx = Edit->size(); 632 Edit->create(LIS, VRM); 633 return OpenIdx; 634} 635 636void SplitEditor::selectIntv(unsigned Idx) { 637 assert(Idx != 0 && "Cannot select the complement interval"); 638 assert(Idx < Edit->size() && "Can only select previously opened interval"); 639 OpenIdx = Idx; 640} 641 642SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 643 assert(OpenIdx && "openIntv not called before enterIntvBefore"); 644 DEBUG(dbgs() << " enterIntvBefore " << Idx); 645 Idx = Idx.getBaseIndex(); 646 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 647 if (!ParentVNI) { 648 DEBUG(dbgs() << ": not live\n"); 649 return Idx; 650 } 651 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 652 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 653 assert(MI && "enterIntvBefore called with invalid index"); 654 655 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 656 return VNI->def; 657} 658 659SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 660 assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 661 SlotIndex End = LIS.getMBBEndIdx(&MBB); 662 SlotIndex Last = End.getPrevSlot(); 663 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 664 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 665 if (!ParentVNI) { 666 DEBUG(dbgs() << ": not live\n"); 667 return End; 668 } 669 DEBUG(dbgs() << ": valno " << ParentVNI->id); 670 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 671 LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 672 RegAssign.insert(VNI->def, End, OpenIdx); 673 DEBUG(dump()); 674 return VNI->def; 675} 676 677/// useIntv - indicate that all instructions in MBB should use OpenLI. 678void SplitEditor::useIntv(const MachineBasicBlock &MBB) { 679 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 680} 681 682void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 683 assert(OpenIdx && "openIntv not called before useIntv"); 684 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 685 RegAssign.insert(Start, End, OpenIdx); 686 DEBUG(dump()); 687} 688 689SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 690 assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 691 DEBUG(dbgs() << " leaveIntvAfter " << Idx); 692 693 // The interval must be live beyond the instruction at Idx. 694 Idx = Idx.getBoundaryIndex(); 695 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 696 if (!ParentVNI) { 697 DEBUG(dbgs() << ": not live\n"); 698 return Idx.getNextSlot(); 699 } 700 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 701 702 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 703 assert(MI && "No instruction at index"); 704 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 705 llvm::next(MachineBasicBlock::iterator(MI))); 706 return VNI->def; 707} 708 709SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 710 assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 711 DEBUG(dbgs() << " leaveIntvBefore " << Idx); 712 713 // The interval must be live into the instruction at Idx. 714 Idx = Idx.getBoundaryIndex(); 715 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 716 if (!ParentVNI) { 717 DEBUG(dbgs() << ": not live\n"); 718 return Idx.getNextSlot(); 719 } 720 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 721 722 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 723 assert(MI && "No instruction at index"); 724 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 725 return VNI->def; 726} 727 728SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 729 assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 730 SlotIndex Start = LIS.getMBBStartIdx(&MBB); 731 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 732 733 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 734 if (!ParentVNI) { 735 DEBUG(dbgs() << ": not live\n"); 736 return Start; 737 } 738 739 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 740 MBB.SkipPHIsAndLabels(MBB.begin())); 741 RegAssign.insert(Start, VNI->def, OpenIdx); 742 DEBUG(dump()); 743 return VNI->def; 744} 745 746void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 747 assert(OpenIdx && "openIntv not called before overlapIntv"); 748 const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 749 assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 750 "Parent changes value in extended range"); 751 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 752 "Range cannot span basic blocks"); 753 754 // The complement interval will be extended as needed by extendRange(). 755 if (ParentVNI) 756 markComplexMapped(0, ParentVNI); 757 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 758 RegAssign.insert(Start, End, OpenIdx); 759 DEBUG(dump()); 760} 761 762/// transferValues - Transfer all possible values to the new live ranges. 763/// Values that were rematerialized are left alone, they need extendRange(). 764bool SplitEditor::transferValues() { 765 bool Skipped = false; 766 LiveInBlocks.clear(); 767 RegAssignMap::const_iterator AssignI = RegAssign.begin(); 768 for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 769 ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 770 DEBUG(dbgs() << " blit " << *ParentI << ':'); 771 VNInfo *ParentVNI = ParentI->valno; 772 // RegAssign has holes where RegIdx 0 should be used. 773 SlotIndex Start = ParentI->start; 774 AssignI.advanceTo(Start); 775 do { 776 unsigned RegIdx; 777 SlotIndex End = ParentI->end; 778 if (!AssignI.valid()) { 779 RegIdx = 0; 780 } else if (AssignI.start() <= Start) { 781 RegIdx = AssignI.value(); 782 if (AssignI.stop() < End) { 783 End = AssignI.stop(); 784 ++AssignI; 785 } 786 } else { 787 RegIdx = 0; 788 End = std::min(End, AssignI.start()); 789 } 790 791 // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 792 DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 793 LiveInterval *LI = Edit->get(RegIdx); 794 795 // Check for a simply defined value that can be blitted directly. 796 if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 797 DEBUG(dbgs() << ':' << VNI->id); 798 LI->addRange(LiveRange(Start, End, VNI)); 799 Start = End; 800 continue; 801 } 802 803 // Skip rematerialized values, we need to use extendRange() and 804 // extendPHIKillRanges() to completely recompute the live ranges. 805 if (Edit->didRematerialize(ParentVNI)) { 806 DEBUG(dbgs() << "(remat)"); 807 Skipped = true; 808 Start = End; 809 continue; 810 } 811 812 // Initialize the live-out cache the first time it is needed. 813 if (LiveOutSeen.empty()) { 814 unsigned N = VRM.getMachineFunction().getNumBlockIDs(); 815 LiveOutSeen.resize(N); 816 LiveOutCache.resize(N); 817 } 818 819 // This value has multiple defs in RegIdx, but it wasn't rematerialized, 820 // so the live range is accurate. Add live-in blocks in [Start;End) to the 821 // LiveInBlocks. 822 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 823 SlotIndex BlockStart, BlockEnd; 824 tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 825 826 // The first block may be live-in, or it may have its own def. 827 if (Start != BlockStart) { 828 VNInfo *VNI = LI->extendInBlock(BlockStart, 829 std::min(BlockEnd, End).getPrevSlot()); 830 assert(VNI && "Missing def for complex mapped value"); 831 DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 832 // MBB has its own def. Is it also live-out? 833 if (BlockEnd <= End) { 834 LiveOutSeen.set(MBB->getNumber()); 835 LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]); 836 } 837 // Skip to the next block for live-in. 838 ++MBB; 839 BlockStart = BlockEnd; 840 } 841 842 // Handle the live-in blocks covered by [Start;End). 843 assert(Start <= BlockStart && "Expected live-in block"); 844 while (BlockStart < End) { 845 DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 846 BlockEnd = LIS.getMBBEndIdx(MBB); 847 if (BlockStart == ParentVNI->def) { 848 // This block has the def of a parent PHI, so it isn't live-in. 849 assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 850 VNInfo *VNI = LI->extendInBlock(BlockStart, 851 std::min(BlockEnd, End).getPrevSlot()); 852 assert(VNI && "Missing def for complex mapped parent PHI"); 853 if (End >= BlockEnd) { 854 // Live-out as well. 855 LiveOutSeen.set(MBB->getNumber()); 856 LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]); 857 } 858 } else { 859 // This block needs a live-in value. 860 LiveInBlocks.push_back(MDT[MBB]); 861 // The last block covered may not be live-out. 862 if (End < BlockEnd) 863 LiveInBlocks.back().Kill = End; 864 else { 865 // Live-out, but we need updateSSA to tell us the value. 866 LiveOutSeen.set(MBB->getNumber()); 867 LiveOutCache[MBB] = LiveOutPair((VNInfo*)0, 868 (MachineDomTreeNode*)0); 869 } 870 } 871 BlockStart = BlockEnd; 872 ++MBB; 873 } 874 Start = End; 875 } while (Start != ParentI->end); 876 DEBUG(dbgs() << '\n'); 877 } 878 879 if (!LiveInBlocks.empty()) 880 updateSSA(); 881 882 return Skipped; 883} 884 885void SplitEditor::extendPHIKillRanges() { 886 // Extend live ranges to be live-out for successor PHI values. 887 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 888 E = Edit->getParent().vni_end(); I != E; ++I) { 889 const VNInfo *PHIVNI = *I; 890 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 891 continue; 892 unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 893 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 894 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 895 PE = MBB->pred_end(); PI != PE; ++PI) { 896 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 897 // The predecessor may not have a live-out value. That is OK, like an 898 // undef PHI operand. 899 if (Edit->getParent().liveAt(End)) { 900 assert(RegAssign.lookup(End) == RegIdx && 901 "Different register assignment in phi predecessor"); 902 extendRange(RegIdx, End); 903 } 904 } 905 } 906} 907 908/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 909void SplitEditor::rewriteAssigned(bool ExtendRanges) { 910 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 911 RE = MRI.reg_end(); RI != RE;) { 912 MachineOperand &MO = RI.getOperand(); 913 MachineInstr *MI = MO.getParent(); 914 ++RI; 915 // LiveDebugVariables should have handled all DBG_VALUE instructions. 916 if (MI->isDebugValue()) { 917 DEBUG(dbgs() << "Zapping " << *MI); 918 MO.setReg(0); 919 continue; 920 } 921 922 // <undef> operands don't really read the register, so just assign them to 923 // the complement. 924 if (MO.isUse() && MO.isUndef()) { 925 MO.setReg(Edit->get(0)->reg); 926 continue; 927 } 928 929 SlotIndex Idx = LIS.getInstructionIndex(MI); 930 if (MO.isDef()) 931 Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex(); 932 933 // Rewrite to the mapped register at Idx. 934 unsigned RegIdx = RegAssign.lookup(Idx); 935 MO.setReg(Edit->get(RegIdx)->reg); 936 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 937 << Idx << ':' << RegIdx << '\t' << *MI); 938 939 // Extend liveness to Idx if the instruction reads reg. 940 if (!ExtendRanges) 941 continue; 942 943 // Skip instructions that don't read Reg. 944 if (MO.isDef()) { 945 if (!MO.getSubReg() && !MO.isEarlyClobber()) 946 continue; 947 // We may wan't to extend a live range for a partial redef, or for a use 948 // tied to an early clobber. 949 Idx = Idx.getPrevSlot(); 950 if (!Edit->getParent().liveAt(Idx)) 951 continue; 952 } else 953 Idx = Idx.getUseIndex(); 954 955 extendRange(RegIdx, Idx); 956 } 957} 958 959void SplitEditor::deleteRematVictims() { 960 SmallVector<MachineInstr*, 8> Dead; 961 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 962 LiveInterval *LI = *I; 963 for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 964 LII != LIE; ++LII) { 965 // Dead defs end at the store slot. 966 if (LII->end != LII->valno->def.getNextSlot()) 967 continue; 968 MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 969 assert(MI && "Missing instruction for dead def"); 970 MI->addRegisterDead(LI->reg, &TRI); 971 972 if (!MI->allDefsAreDead()) 973 continue; 974 975 DEBUG(dbgs() << "All defs dead: " << *MI); 976 Dead.push_back(MI); 977 } 978 } 979 980 if (Dead.empty()) 981 return; 982 983 Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); 984} 985 986void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 987 ++NumFinished; 988 989 // At this point, the live intervals in Edit contain VNInfos corresponding to 990 // the inserted copies. 991 992 // Add the original defs from the parent interval. 993 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 994 E = Edit->getParent().vni_end(); I != E; ++I) { 995 const VNInfo *ParentVNI = *I; 996 if (ParentVNI->isUnused()) 997 continue; 998 unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 999 VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 1000 VNI->setIsPHIDef(ParentVNI->isPHIDef()); 1001 VNI->setCopy(ParentVNI->getCopy()); 1002 1003 // Mark rematted values as complex everywhere to force liveness computation. 1004 // The new live ranges may be truncated. 1005 if (Edit->didRematerialize(ParentVNI)) 1006 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1007 markComplexMapped(i, ParentVNI); 1008 } 1009 1010#ifndef NDEBUG 1011 // Every new interval must have a def by now, otherwise the split is bogus. 1012 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 1013 assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); 1014#endif 1015 1016 // Transfer the simply mapped values, check if any are skipped. 1017 bool Skipped = transferValues(); 1018 if (Skipped) 1019 extendPHIKillRanges(); 1020 else 1021 ++NumSimple; 1022 1023 // Rewrite virtual registers, possibly extending ranges. 1024 rewriteAssigned(Skipped); 1025 1026 // Delete defs that were rematted everywhere. 1027 if (Skipped) 1028 deleteRematVictims(); 1029 1030 // Get rid of unused values and set phi-kill flags. 1031 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 1032 (*I)->RenumberValues(LIS); 1033 1034 // Provide a reverse mapping from original indices to Edit ranges. 1035 if (LRMap) { 1036 LRMap->clear(); 1037 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1038 LRMap->push_back(i); 1039 } 1040 1041 // Now check if any registers were separated into multiple components. 1042 ConnectedVNInfoEqClasses ConEQ(LIS); 1043 for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 1044 // Don't use iterators, they are invalidated by create() below. 1045 LiveInterval *li = Edit->get(i); 1046 unsigned NumComp = ConEQ.Classify(li); 1047 if (NumComp <= 1) 1048 continue; 1049 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 1050 SmallVector<LiveInterval*, 8> dups; 1051 dups.push_back(li); 1052 for (unsigned j = 1; j != NumComp; ++j) 1053 dups.push_back(&Edit->create(LIS, VRM)); 1054 ConEQ.Distribute(&dups[0], MRI); 1055 // The new intervals all map back to i. 1056 if (LRMap) 1057 LRMap->resize(Edit->size(), i); 1058 } 1059 1060 // Calculate spill weight and allocation hints for new intervals. 1061 Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops); 1062 1063 assert(!LRMap || LRMap->size() == Edit->size()); 1064} 1065 1066 1067//===----------------------------------------------------------------------===// 1068// Single Block Splitting 1069//===----------------------------------------------------------------------===// 1070 1071/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 1072/// may be an advantage to split CurLI for the duration of the block. 1073bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 1074 // If CurLI is local to one block, there is no point to splitting it. 1075 if (UseBlocks.size() <= 1) 1076 return false; 1077 // Add blocks with multiple uses. 1078 for (unsigned i = 0, e = UseBlocks.size(); i != e; ++i) { 1079 const BlockInfo &BI = UseBlocks[i]; 1080 if (BI.FirstUse == BI.LastUse) 1081 continue; 1082 Blocks.insert(BI.MBB); 1083 } 1084 return !Blocks.empty(); 1085} 1086 1087void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 1088 openIntv(); 1089 SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 1090 SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstUse, 1091 LastSplitPoint)); 1092 if (!BI.LiveOut || BI.LastUse < LastSplitPoint) { 1093 useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 1094 } else { 1095 // The last use is after the last valid split point. 1096 SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 1097 useIntv(SegStart, SegStop); 1098 overlapIntv(SegStop, BI.LastUse); 1099 } 1100} 1101 1102/// splitSingleBlocks - Split CurLI into a separate live interval inside each 1103/// basic block in Blocks. 1104void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 1105 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 1106 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA.getUseBlocks(); 1107 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1108 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1109 if (Blocks.count(BI.MBB)) 1110 splitSingleBlock(BI); 1111 } 1112 finish(); 1113} 1114