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