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