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