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