SplitKit.cpp revision 6a3dbd3b25bbc99bd1a233d6a74ddea3493ba6ac
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 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 352 PE = MBB->pred_end(); PI != PE; ++PI) { 353 MachineBasicBlock *Pred = *PI; 354 LiveOutPair &LOP = LiveOutCache[Pred]; 355 356 // Is this a known live-out block? 357 if (LiveOutSeen.test(Pred->getNumber())) { 358 if (VNInfo *VNI = LOP.first) { 359 if (IdxVNI && IdxVNI != VNI) 360 UniqueVNI = false; 361 IdxVNI = VNI; 362 } 363 continue; 364 } 365 366 // First time. LOP is garbage and must be cleared below. 367 LiveOutSeen.set(Pred->getNumber()); 368 369 // Does Pred provide a live-out value? 370 SlotIndex Start, Last; 371 tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred); 372 Last = Last.getPrevSlot(); 373 VNInfo *VNI = LI->extendInBlock(Start, Last); 374 LOP.first = VNI; 375 if (VNI) { 376 LOP.second = MDT[LIS.getMBBFromIndex(VNI->def)]; 377 if (IdxVNI && IdxVNI != VNI) 378 UniqueVNI = false; 379 IdxVNI = VNI; 380 continue; 381 } 382 LOP.second = 0; 383 384 // No, we need a live-in value for Pred as well 385 if (Pred != IdxMBB) 386 LiveIn.push_back(MDT[Pred]); 387 else 388 UniqueVNI = false; // Loopback to IdxMBB, ask updateSSA() for help. 389 } 390 } 391 392 // We may need to add phi-def values to preserve the SSA form. 393 if (UniqueVNI) { 394 LiveOutPair LOP(IdxVNI, MDT[LIS.getMBBFromIndex(IdxVNI->def)]); 395 // Update LiveOutCache, but skip IdxMBB at LiveIn[0]. 396 for (unsigned i = 1, e = LiveIn.size(); i != e; ++i) 397 LiveOutCache[LiveIn[i]->getBlock()] = LOP; 398 } else 399 IdxVNI = updateSSA(RegIdx, LiveIn, Idx, IdxMBB); 400 401 // Since we went through the trouble of a full BFS visiting all reaching defs, 402 // the values in LiveIn are now accurate. No more phi-defs are needed 403 // for these blocks, so we can color the live ranges. 404 for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) { 405 MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 406 SlotIndex Start = LIS.getMBBStartIdx(MBB); 407 VNInfo *VNI = LiveOutCache[MBB].first; 408 409 // Anything in LiveIn other than IdxMBB is live-through. 410 // In IdxMBB, we should stop at Idx unless the same value is live-out. 411 if (MBB == IdxMBB && IdxVNI != VNI) 412 LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI)); 413 else 414 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 415 } 416} 417 418VNInfo *SplitEditor::updateSSA(unsigned RegIdx, 419 SmallVectorImpl<MachineDomTreeNode*> &LiveIn, 420 SlotIndex Idx, 421 const MachineBasicBlock *IdxMBB) { 422 // This is essentially the same iterative algorithm that SSAUpdater uses, 423 // except we already have a dominator tree, so we don't have to recompute it. 424 LiveInterval *LI = Edit->get(RegIdx); 425 VNInfo *IdxVNI = 0; 426 unsigned Changes; 427 do { 428 Changes = 0; 429 // Propagate live-out values down the dominator tree, inserting phi-defs 430 // when necessary. Since LiveIn was created by a BFS, going backwards makes 431 // it more likely for us to visit immediate dominators before their 432 // children. 433 for (unsigned i = LiveIn.size(); i; --i) { 434 MachineDomTreeNode *Node = LiveIn[i-1]; 435 MachineBasicBlock *MBB = Node->getBlock(); 436 MachineDomTreeNode *IDom = Node->getIDom(); 437 LiveOutPair IDomValue; 438 439 // We need a live-in value to a block with no immediate dominator? 440 // This is probably an unreachable block that has survived somehow. 441 bool needPHI = !IDom || !LiveOutSeen.test(IDom->getBlock()->getNumber()); 442 443 // IDom dominates all of our predecessors, but it may not be the immediate 444 // dominator. Check if any of them have live-out values that are properly 445 // dominated by IDom. If so, we need a phi-def here. 446 if (!needPHI) { 447 IDomValue = LiveOutCache[IDom->getBlock()]; 448 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 449 PE = MBB->pred_end(); PI != PE; ++PI) { 450 LiveOutPair Value = LiveOutCache[*PI]; 451 if (!Value.first || Value.first == IDomValue.first) 452 continue; 453 // This predecessor is carrying something other than IDomValue. 454 // It could be because IDomValue hasn't propagated yet, or it could be 455 // because MBB is in the dominance frontier of that value. 456 if (MDT.dominates(IDom, Value.second)) { 457 needPHI = true; 458 break; 459 } 460 } 461 } 462 463 // Create a phi-def if required. 464 if (needPHI) { 465 ++Changes; 466 SlotIndex Start = LIS.getMBBStartIdx(MBB); 467 VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 468 VNI->setIsPHIDef(true); 469 // We no longer need LI to be live-in. 470 LiveIn.erase(LiveIn.begin()+(i-1)); 471 // Blocks in LiveIn are either IdxMBB, or have a value live-through. 472 if (MBB == IdxMBB) 473 IdxVNI = VNI; 474 // Check if we need to update live-out info. 475 LiveOutPair &LOP = LiveOutCache[MBB]; 476 if (LOP.second == Node || !LiveOutSeen.test(MBB->getNumber())) { 477 // We already have a live-out defined in MBB, so this must be IdxMBB. 478 assert(MBB == IdxMBB && "Adding phi-def to known live-out"); 479 LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI)); 480 } else { 481 // This phi-def is also live-out, so color the whole block. 482 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 483 LOP = LiveOutPair(VNI, Node); 484 } 485 } else if (IDomValue.first) { 486 // No phi-def here. Remember incoming value for IdxMBB. 487 if (MBB == IdxMBB) { 488 IdxVNI = IDomValue.first; 489 // IdxMBB need not be live-out. 490 if (!LiveOutSeen.test(MBB->getNumber())) 491 continue; 492 } 493 assert(LiveOutSeen.test(MBB->getNumber()) && "Expected live-out block"); 494 // Propagate IDomValue if needed: 495 // MBB is live-out and doesn't define its own value. 496 LiveOutPair &LOP = LiveOutCache[MBB]; 497 if (LOP.second != Node && LOP.first != IDomValue.first) { 498 ++Changes; 499 LOP = IDomValue; 500 } 501 } 502 } 503 } while (Changes); 504 505 assert(IdxVNI && "Didn't find value for Idx"); 506 return IdxVNI; 507} 508 509VNInfo *SplitEditor::defFromParent(unsigned RegIdx, 510 VNInfo *ParentVNI, 511 SlotIndex UseIdx, 512 MachineBasicBlock &MBB, 513 MachineBasicBlock::iterator I) { 514 MachineInstr *CopyMI = 0; 515 SlotIndex Def; 516 LiveInterval *LI = Edit->get(RegIdx); 517 518 // Attempt cheap-as-a-copy rematerialization. 519 LiveRangeEdit::Remat RM(ParentVNI); 520 if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 521 Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI); 522 } else { 523 // Can't remat, just insert a copy from parent. 524 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 525 .addReg(Edit->getReg()); 526 Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex(); 527 } 528 529 // Define the value in Reg. 530 VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 531 VNI->setCopy(CopyMI); 532 return VNI; 533} 534 535/// Create a new virtual register and live interval. 536void SplitEditor::openIntv() { 537 assert(!OpenIdx && "Previous LI not closed before openIntv"); 538 539 // Create the complement as index 0. 540 if (Edit->empty()) 541 Edit->create(LIS, VRM); 542 543 // Create the open interval. 544 OpenIdx = Edit->size(); 545 Edit->create(LIS, VRM); 546} 547 548SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 549 assert(OpenIdx && "openIntv not called before enterIntvBefore"); 550 DEBUG(dbgs() << " enterIntvBefore " << Idx); 551 Idx = Idx.getBaseIndex(); 552 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 553 if (!ParentVNI) { 554 DEBUG(dbgs() << ": not live\n"); 555 return Idx; 556 } 557 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 558 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 559 assert(MI && "enterIntvBefore called with invalid index"); 560 561 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 562 return VNI->def; 563} 564 565SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 566 assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 567 SlotIndex End = LIS.getMBBEndIdx(&MBB); 568 SlotIndex Last = End.getPrevSlot(); 569 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 570 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 571 if (!ParentVNI) { 572 DEBUG(dbgs() << ": not live\n"); 573 return End; 574 } 575 DEBUG(dbgs() << ": valno " << ParentVNI->id); 576 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 577 LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 578 RegAssign.insert(VNI->def, End, OpenIdx); 579 DEBUG(dump()); 580 return VNI->def; 581} 582 583/// useIntv - indicate that all instructions in MBB should use OpenLI. 584void SplitEditor::useIntv(const MachineBasicBlock &MBB) { 585 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 586} 587 588void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 589 assert(OpenIdx && "openIntv not called before useIntv"); 590 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 591 RegAssign.insert(Start, End, OpenIdx); 592 DEBUG(dump()); 593} 594 595SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 596 assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 597 DEBUG(dbgs() << " leaveIntvAfter " << Idx); 598 599 // The interval must be live beyond the instruction at Idx. 600 Idx = Idx.getBoundaryIndex(); 601 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 602 if (!ParentVNI) { 603 DEBUG(dbgs() << ": not live\n"); 604 return Idx.getNextSlot(); 605 } 606 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 607 608 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 609 assert(MI && "No instruction at index"); 610 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 611 llvm::next(MachineBasicBlock::iterator(MI))); 612 return VNI->def; 613} 614 615SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 616 assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 617 DEBUG(dbgs() << " leaveIntvBefore " << Idx); 618 619 // The interval must be live into the instruction at Idx. 620 Idx = Idx.getBoundaryIndex(); 621 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 622 if (!ParentVNI) { 623 DEBUG(dbgs() << ": not live\n"); 624 return Idx.getNextSlot(); 625 } 626 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 627 628 MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 629 assert(MI && "No instruction at index"); 630 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 631 return VNI->def; 632} 633 634SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 635 assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 636 SlotIndex Start = LIS.getMBBStartIdx(&MBB); 637 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 638 639 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 640 if (!ParentVNI) { 641 DEBUG(dbgs() << ": not live\n"); 642 return Start; 643 } 644 645 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 646 MBB.SkipPHIsAndLabels(MBB.begin())); 647 RegAssign.insert(Start, VNI->def, OpenIdx); 648 DEBUG(dump()); 649 return VNI->def; 650} 651 652void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 653 assert(OpenIdx && "openIntv not called before overlapIntv"); 654 const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 655 assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 656 "Parent changes value in extended range"); 657 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 658 "Range cannot span basic blocks"); 659 660 // The complement interval will be extended as needed by extendRange(). 661 markComplexMapped(0, ParentVNI); 662 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 663 RegAssign.insert(Start, End, OpenIdx); 664 DEBUG(dump()); 665} 666 667/// closeIntv - Indicate that we are done editing the currently open 668/// LiveInterval, and ranges can be trimmed. 669void SplitEditor::closeIntv() { 670 assert(OpenIdx && "openIntv not called before closeIntv"); 671 OpenIdx = 0; 672} 673 674/// transferSimpleValues - Transfer all simply defined values to the new live 675/// ranges. 676/// Values that were rematerialized or that have multiple defs are left alone. 677bool SplitEditor::transferSimpleValues() { 678 bool Skipped = false; 679 RegAssignMap::const_iterator AssignI = RegAssign.begin(); 680 for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 681 ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 682 DEBUG(dbgs() << " blit " << *ParentI << ':'); 683 VNInfo *ParentVNI = ParentI->valno; 684 // RegAssign has holes where RegIdx 0 should be used. 685 SlotIndex Start = ParentI->start; 686 AssignI.advanceTo(Start); 687 do { 688 unsigned RegIdx; 689 SlotIndex End = ParentI->end; 690 if (!AssignI.valid()) { 691 RegIdx = 0; 692 } else if (AssignI.start() <= Start) { 693 RegIdx = AssignI.value(); 694 if (AssignI.stop() < End) { 695 End = AssignI.stop(); 696 ++AssignI; 697 } 698 } else { 699 RegIdx = 0; 700 End = std::min(End, AssignI.start()); 701 } 702 DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 703 if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 704 DEBUG(dbgs() << ':' << VNI->id); 705 Edit->get(RegIdx)->addRange(LiveRange(Start, End, VNI)); 706 } else 707 Skipped = true; 708 Start = End; 709 } while (Start != ParentI->end); 710 DEBUG(dbgs() << '\n'); 711 } 712 return Skipped; 713} 714 715void SplitEditor::extendPHIKillRanges() { 716 // Extend live ranges to be live-out for successor PHI values. 717 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 718 E = Edit->getParent().vni_end(); I != E; ++I) { 719 const VNInfo *PHIVNI = *I; 720 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 721 continue; 722 unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 723 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 724 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 725 PE = MBB->pred_end(); PI != PE; ++PI) { 726 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 727 // The predecessor may not have a live-out value. That is OK, like an 728 // undef PHI operand. 729 if (Edit->getParent().liveAt(End)) { 730 assert(RegAssign.lookup(End) == RegIdx && 731 "Different register assignment in phi predecessor"); 732 extendRange(RegIdx, End); 733 } 734 } 735 } 736} 737 738/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 739void SplitEditor::rewriteAssigned(bool ExtendRanges) { 740 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 741 RE = MRI.reg_end(); RI != RE;) { 742 MachineOperand &MO = RI.getOperand(); 743 MachineInstr *MI = MO.getParent(); 744 ++RI; 745 // LiveDebugVariables should have handled all DBG_VALUE instructions. 746 if (MI->isDebugValue()) { 747 DEBUG(dbgs() << "Zapping " << *MI); 748 MO.setReg(0); 749 continue; 750 } 751 752 // <undef> operands don't really read the register, so just assign them to 753 // the complement. 754 if (MO.isUse() && MO.isUndef()) { 755 MO.setReg(Edit->get(0)->reg); 756 continue; 757 } 758 759 SlotIndex Idx = LIS.getInstructionIndex(MI); 760 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 761 762 // Rewrite to the mapped register at Idx. 763 unsigned RegIdx = RegAssign.lookup(Idx); 764 MO.setReg(Edit->get(RegIdx)->reg); 765 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 766 << Idx << ':' << RegIdx << '\t' << *MI); 767 768 // Extend liveness to Idx. 769 if (ExtendRanges) 770 extendRange(RegIdx, Idx); 771 } 772} 773 774void SplitEditor::deleteRematVictims() { 775 SmallVector<MachineInstr*, 8> Dead; 776 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 777 E = Edit->getParent().vni_end(); I != E; ++I) { 778 const VNInfo *VNI = *I; 779 // Was VNI rematted anywhere? 780 if (VNI->isUnused() || VNI->isPHIDef() || !Edit->didRematerialize(VNI)) 781 continue; 782 unsigned RegIdx = RegAssign.lookup(VNI->def); 783 LiveInterval *LI = Edit->get(RegIdx); 784 LiveInterval::const_iterator LII = LI->FindLiveRangeContaining(VNI->def); 785 assert(LII != LI->end() && "Missing live range for rematted def"); 786 787 // Is this a dead def? 788 if (LII->end != VNI->def.getNextSlot()) 789 continue; 790 791 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 792 assert(MI && "Missing instruction for dead def"); 793 MI->addRegisterDead(LI->reg, &TRI); 794 795 if (!MI->allDefsAreDead()) 796 continue; 797 798 DEBUG(dbgs() << "All defs dead: " << *MI); 799 Dead.push_back(MI); 800 } 801 802 if (Dead.empty()) 803 return; 804 805 Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); 806} 807 808void SplitEditor::finish() { 809 assert(OpenIdx == 0 && "Previous LI not closed before rewrite"); 810 ++NumFinished; 811 812 // At this point, the live intervals in Edit contain VNInfos corresponding to 813 // the inserted copies. 814 815 // Add the original defs from the parent interval. 816 for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 817 E = Edit->getParent().vni_end(); I != E; ++I) { 818 const VNInfo *ParentVNI = *I; 819 if (ParentVNI->isUnused()) 820 continue; 821 unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 822 VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 823 VNI->setIsPHIDef(ParentVNI->isPHIDef()); 824 VNI->setCopy(ParentVNI->getCopy()); 825 826 // Mark rematted values as complex everywhere to force liveness computation. 827 // The new live ranges may be truncated. 828 if (Edit->didRematerialize(ParentVNI)) 829 for (unsigned i = 0, e = Edit->size(); i != e; ++i) 830 markComplexMapped(i, ParentVNI); 831 } 832 833#ifndef NDEBUG 834 // Every new interval must have a def by now, otherwise the split is bogus. 835 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 836 assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); 837#endif 838 839 // Transfer the simply mapped values, check if any are complex. 840 bool Complex = transferSimpleValues(); 841 if (Complex) 842 extendPHIKillRanges(); 843 else 844 ++NumSimple; 845 846 // Rewrite virtual registers, possibly extending ranges. 847 rewriteAssigned(Complex); 848 849 // Delete defs that were rematted everywhere. 850 if (Complex) 851 deleteRematVictims(); 852 853 // Get rid of unused values and set phi-kill flags. 854 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 855 (*I)->RenumberValues(LIS); 856 857 // Now check if any registers were separated into multiple components. 858 ConnectedVNInfoEqClasses ConEQ(LIS); 859 for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 860 // Don't use iterators, they are invalidated by create() below. 861 LiveInterval *li = Edit->get(i); 862 unsigned NumComp = ConEQ.Classify(li); 863 if (NumComp <= 1) 864 continue; 865 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 866 SmallVector<LiveInterval*, 8> dups; 867 dups.push_back(li); 868 for (unsigned i = 1; i != NumComp; ++i) 869 dups.push_back(&Edit->create(LIS, VRM)); 870 ConEQ.Distribute(&dups[0], MRI); 871 } 872 873 // Calculate spill weight and allocation hints for new intervals. 874 VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops); 875 for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 876 LiveInterval &li = **I; 877 vrai.CalculateRegClass(li.reg); 878 vrai.CalculateWeightAndHint(li); 879 DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName() 880 << ":" << li << '\n'); 881 } 882} 883 884 885//===----------------------------------------------------------------------===// 886// Single Block Splitting 887//===----------------------------------------------------------------------===// 888 889/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 890/// may be an advantage to split CurLI for the duration of the block. 891bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 892 // If CurLI is local to one block, there is no point to splitting it. 893 if (LiveBlocks.size() <= 1) 894 return false; 895 // Add blocks with multiple uses. 896 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 897 const BlockInfo &BI = LiveBlocks[i]; 898 if (!BI.Uses) 899 continue; 900 unsigned Instrs = UsingBlocks.lookup(BI.MBB); 901 if (Instrs <= 1) 902 continue; 903 if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough) 904 continue; 905 Blocks.insert(BI.MBB); 906 } 907 return !Blocks.empty(); 908} 909 910/// splitSingleBlocks - Split CurLI into a separate live interval inside each 911/// basic block in Blocks. 912void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 913 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 914 915 for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) { 916 const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i]; 917 if (!BI.Uses || !Blocks.count(BI.MBB)) 918 continue; 919 920 openIntv(); 921 SlotIndex SegStart = enterIntvBefore(BI.FirstUse); 922 if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) { 923 useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 924 } else { 925 // The last use is after the last valid split point. 926 SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint); 927 useIntv(SegStart, SegStop); 928 overlapIntv(SegStop, BI.LastUse); 929 } 930 closeIntv(); 931 } 932 finish(); 933} 934