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