SplitKit.cpp revision 224145
1212793Sdim//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 2212793Sdim// 3212793Sdim// The LLVM Compiler Infrastructure 4212793Sdim// 5212793Sdim// This file is distributed under the University of Illinois Open Source 6212793Sdim// License. See LICENSE.TXT for details. 7212793Sdim// 8212793Sdim//===----------------------------------------------------------------------===// 9212793Sdim// 10212793Sdim// This file contains the SplitAnalysis class as well as mutator functions for 11212793Sdim// live range splitting. 12212793Sdim// 13212793Sdim//===----------------------------------------------------------------------===// 14212793Sdim 15218893Sdim#define DEBUG_TYPE "regalloc" 16212793Sdim#include "SplitKit.h" 17218893Sdim#include "LiveRangeEdit.h" 18212793Sdim#include "VirtRegMap.h" 19221345Sdim#include "llvm/ADT/Statistic.h" 20212793Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 21218893Sdim#include "llvm/CodeGen/MachineDominators.h" 22212793Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 23212793Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 24212793Sdim#include "llvm/Support/Debug.h" 25212793Sdim#include "llvm/Support/raw_ostream.h" 26212793Sdim#include "llvm/Target/TargetInstrInfo.h" 27212793Sdim#include "llvm/Target/TargetMachine.h" 28212793Sdim 29212793Sdimusing namespace llvm; 30212793Sdim 31221345SdimSTATISTIC(NumFinished, "Number of splits finished"); 32221345SdimSTATISTIC(NumSimple, "Number of splits that were simple"); 33223017SdimSTATISTIC(NumCopies, "Number of copies inserted for splitting"); 34223017SdimSTATISTIC(NumRemats, "Number of rematerialized defs for splitting"); 35223017SdimSTATISTIC(NumRepairs, "Number of invalid live ranges repaired"); 36212793Sdim 37212793Sdim//===----------------------------------------------------------------------===// 38212793Sdim// Split Analysis 39212793Sdim//===----------------------------------------------------------------------===// 40212793Sdim 41218893SdimSplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 42212793Sdim const LiveIntervals &lis, 43212793Sdim const MachineLoopInfo &mli) 44218893Sdim : MF(vrm.getMachineFunction()), 45218893Sdim VRM(vrm), 46218893Sdim LIS(lis), 47218893Sdim Loops(mli), 48218893Sdim TII(*MF.getTarget().getInstrInfo()), 49221345Sdim CurLI(0), 50221345Sdim LastSplitPoint(MF.getNumBlockIDs()) {} 51212793Sdim 52212793Sdimvoid SplitAnalysis::clear() { 53218893Sdim UseSlots.clear(); 54221345Sdim UseBlocks.clear(); 55221345Sdim ThroughBlocks.clear(); 56218893Sdim CurLI = 0; 57223017Sdim DidRepairRange = false; 58212793Sdim} 59212793Sdim 60221345SdimSlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { 61221345Sdim const MachineBasicBlock *MBB = MF.getBlockNumbered(Num); 62221345Sdim const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor(); 63221345Sdim std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num]; 64221345Sdim 65221345Sdim // Compute split points on the first call. The pair is independent of the 66221345Sdim // current live interval. 67221345Sdim if (!LSP.first.isValid()) { 68221345Sdim MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator(); 69221345Sdim if (FirstTerm == MBB->end()) 70221345Sdim LSP.first = LIS.getMBBEndIdx(MBB); 71221345Sdim else 72221345Sdim LSP.first = LIS.getInstructionIndex(FirstTerm); 73221345Sdim 74221345Sdim // If there is a landing pad successor, also find the call instruction. 75221345Sdim if (!LPad) 76221345Sdim return LSP.first; 77221345Sdim // There may not be a call instruction (?) in which case we ignore LPad. 78221345Sdim LSP.second = LSP.first; 79224145Sdim for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin(); 80224145Sdim I != E;) { 81224145Sdim --I; 82221345Sdim if (I->getDesc().isCall()) { 83221345Sdim LSP.second = LIS.getInstructionIndex(I); 84221345Sdim break; 85221345Sdim } 86224145Sdim } 87221345Sdim } 88221345Sdim 89221345Sdim // If CurLI is live into a landing pad successor, move the last split point 90221345Sdim // back to the call that may throw. 91221345Sdim if (LPad && LSP.second.isValid() && LIS.isLiveInToMBB(*CurLI, LPad)) 92221345Sdim return LSP.second; 93221345Sdim else 94221345Sdim return LSP.first; 95212793Sdim} 96212793Sdim 97218893Sdim/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 98212793Sdimvoid SplitAnalysis::analyzeUses() { 99221345Sdim assert(UseSlots.empty() && "Call clear first"); 100221345Sdim 101221345Sdim // First get all the defs from the interval values. This provides the correct 102221345Sdim // slots for early clobbers. 103221345Sdim for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(), 104221345Sdim E = CurLI->vni_end(); I != E; ++I) 105221345Sdim if (!(*I)->isPHIDef() && !(*I)->isUnused()) 106221345Sdim UseSlots.push_back((*I)->def); 107221345Sdim 108221345Sdim // Get use slots form the use-def chain. 109218893Sdim const MachineRegisterInfo &MRI = MF.getRegInfo(); 110221345Sdim for (MachineRegisterInfo::use_nodbg_iterator 111221345Sdim I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E; 112221345Sdim ++I) 113221345Sdim if (!I.getOperand().isUndef()) 114221345Sdim UseSlots.push_back(LIS.getInstructionIndex(&*I).getDefIndex()); 115221345Sdim 116221345Sdim array_pod_sort(UseSlots.begin(), UseSlots.end()); 117221345Sdim 118221345Sdim // Remove duplicates, keeping the smaller slot for each instruction. 119221345Sdim // That is what we want for early clobbers. 120221345Sdim UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), 121221345Sdim SlotIndex::isSameInstr), 122221345Sdim UseSlots.end()); 123221345Sdim 124221345Sdim // Compute per-live block info. 125221345Sdim if (!calcLiveBlockInfo()) { 126221345Sdim // FIXME: calcLiveBlockInfo found inconsistencies in the live range. 127224145Sdim // I am looking at you, RegisterCoalescer! 128223017Sdim DidRepairRange = true; 129223017Sdim ++NumRepairs; 130221345Sdim DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); 131221345Sdim const_cast<LiveIntervals&>(LIS) 132221345Sdim .shrinkToUses(const_cast<LiveInterval*>(CurLI)); 133221345Sdim UseBlocks.clear(); 134221345Sdim ThroughBlocks.clear(); 135221345Sdim bool fixed = calcLiveBlockInfo(); 136221345Sdim (void)fixed; 137221345Sdim assert(fixed && "Couldn't fix broken live interval"); 138212793Sdim } 139221345Sdim 140221345Sdim DEBUG(dbgs() << "Analyze counted " 141221345Sdim << UseSlots.size() << " instrs in " 142221345Sdim << UseBlocks.size() << " blocks, through " 143221345Sdim << NumThroughBlocks << " blocks.\n"); 144212793Sdim} 145212793Sdim 146218893Sdim/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 147218893Sdim/// where CurLI is live. 148221345Sdimbool SplitAnalysis::calcLiveBlockInfo() { 149221345Sdim ThroughBlocks.resize(MF.getNumBlockIDs()); 150223017Sdim NumThroughBlocks = NumGapBlocks = 0; 151218893Sdim if (CurLI->empty()) 152221345Sdim return true; 153212793Sdim 154218893Sdim LiveInterval::const_iterator LVI = CurLI->begin(); 155218893Sdim LiveInterval::const_iterator LVE = CurLI->end(); 156212793Sdim 157218893Sdim SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 158218893Sdim UseI = UseSlots.begin(); 159218893Sdim UseE = UseSlots.end(); 160212793Sdim 161218893Sdim // Loop over basic blocks where CurLI is live. 162218893Sdim MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 163218893Sdim for (;;) { 164218893Sdim BlockInfo BI; 165218893Sdim BI.MBB = MFI; 166218893Sdim SlotIndex Start, Stop; 167218893Sdim tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 168212793Sdim 169223017Sdim // If the block contains no uses, the range must be live through. At one 170224145Sdim // point, RegisterCoalescer could create dangling ranges that ended 171223017Sdim // mid-block. 172223017Sdim if (UseI == UseE || *UseI >= Stop) { 173223017Sdim ++NumThroughBlocks; 174223017Sdim ThroughBlocks.set(BI.MBB->getNumber()); 175223017Sdim // The range shouldn't end mid-block if there are no uses. This shouldn't 176223017Sdim // happen. 177223017Sdim if (LVI->end < Stop) 178223017Sdim return false; 179223017Sdim } else { 180223017Sdim // This block has uses. Find the first and last uses in the block. 181218893Sdim BI.FirstUse = *UseI; 182218893Sdim assert(BI.FirstUse >= Start); 183218893Sdim do ++UseI; 184218893Sdim while (UseI != UseE && *UseI < Stop); 185218893Sdim BI.LastUse = UseI[-1]; 186218893Sdim assert(BI.LastUse < Stop); 187212793Sdim 188223017Sdim // LVI is the first live segment overlapping MBB. 189223017Sdim BI.LiveIn = LVI->start <= Start; 190223017Sdim 191223017Sdim // Look for gaps in the live range. 192223017Sdim BI.LiveOut = true; 193223017Sdim while (LVI->end < Stop) { 194223017Sdim SlotIndex LastStop = LVI->end; 195223017Sdim if (++LVI == LVE || LVI->start >= Stop) { 196223017Sdim BI.LiveOut = false; 197223017Sdim BI.LastUse = LastStop; 198223017Sdim break; 199223017Sdim } 200223017Sdim if (LastStop < LVI->start) { 201223017Sdim // There is a gap in the live range. Create duplicate entries for the 202223017Sdim // live-in snippet and the live-out snippet. 203223017Sdim ++NumGapBlocks; 204223017Sdim 205223017Sdim // Push the Live-in part. 206223017Sdim BI.LiveThrough = false; 207223017Sdim BI.LiveOut = false; 208223017Sdim UseBlocks.push_back(BI); 209223017Sdim UseBlocks.back().LastUse = LastStop; 210223017Sdim 211223017Sdim // Set up BI for the live-out part. 212223017Sdim BI.LiveIn = false; 213223017Sdim BI.LiveOut = true; 214223017Sdim BI.FirstUse = LVI->start; 215223017Sdim } 216218893Sdim } 217212793Sdim 218223017Sdim // Don't set LiveThrough when the block has a gap. 219223017Sdim BI.LiveThrough = BI.LiveIn && BI.LiveOut; 220221345Sdim UseBlocks.push_back(BI); 221223017Sdim 222223017Sdim // LVI is now at LVE or LVI->end >= Stop. 223223017Sdim if (LVI == LVE) 224223017Sdim break; 225221345Sdim } 226212793Sdim 227218893Sdim // Live segment ends exactly at Stop. Move to the next segment. 228218893Sdim if (LVI->end == Stop && ++LVI == LVE) 229218893Sdim break; 230218893Sdim 231218893Sdim // Pick the next basic block. 232218893Sdim if (LVI->start < Stop) 233218893Sdim ++MFI; 234218893Sdim else 235218893Sdim MFI = LIS.getMBBFromIndex(LVI->start); 236212793Sdim } 237223017Sdim 238223017Sdim assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count"); 239221345Sdim return true; 240212793Sdim} 241212793Sdim 242221345Sdimunsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { 243221345Sdim if (cli->empty()) 244221345Sdim return 0; 245221345Sdim LiveInterval *li = const_cast<LiveInterval*>(cli); 246221345Sdim LiveInterval::iterator LVI = li->begin(); 247221345Sdim LiveInterval::iterator LVE = li->end(); 248221345Sdim unsigned Count = 0; 249221345Sdim 250221345Sdim // Loop over basic blocks where li is live. 251221345Sdim MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start); 252221345Sdim SlotIndex Stop = LIS.getMBBEndIdx(MFI); 253221345Sdim for (;;) { 254221345Sdim ++Count; 255221345Sdim LVI = li->advanceTo(LVI, Stop); 256221345Sdim if (LVI == LVE) 257221345Sdim return Count; 258221345Sdim do { 259221345Sdim ++MFI; 260221345Sdim Stop = LIS.getMBBEndIdx(MFI); 261221345Sdim } while (Stop <= LVI->start); 262221345Sdim } 263221345Sdim} 264221345Sdim 265219077Sdimbool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 266219077Sdim unsigned OrigReg = VRM.getOriginal(CurLI->reg); 267219077Sdim const LiveInterval &Orig = LIS.getInterval(OrigReg); 268219077Sdim assert(!Orig.empty() && "Splitting empty interval?"); 269219077Sdim LiveInterval::const_iterator I = Orig.find(Idx); 270219077Sdim 271219077Sdim // Range containing Idx should begin at Idx. 272219077Sdim if (I != Orig.end() && I->start <= Idx) 273219077Sdim return I->start == Idx; 274219077Sdim 275219077Sdim // Range does not contain Idx, previous must end at Idx. 276219077Sdim return I != Orig.begin() && (--I)->end == Idx; 277219077Sdim} 278219077Sdim 279212793Sdimvoid SplitAnalysis::analyze(const LiveInterval *li) { 280212793Sdim clear(); 281218893Sdim CurLI = li; 282212793Sdim analyzeUses(); 283212793Sdim} 284212793Sdim 285212793Sdim 286218893Sdim//===----------------------------------------------------------------------===// 287221345Sdim// Split Editor 288218893Sdim//===----------------------------------------------------------------------===// 289212793Sdim 290221345Sdim/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 291221345SdimSplitEditor::SplitEditor(SplitAnalysis &sa, 292221345Sdim LiveIntervals &lis, 293221345Sdim VirtRegMap &vrm, 294221345Sdim MachineDominatorTree &mdt) 295221345Sdim : SA(sa), LIS(lis), VRM(vrm), 296221345Sdim MRI(vrm.getMachineFunction().getRegInfo()), 297221345Sdim MDT(mdt), 298221345Sdim TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 299221345Sdim TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 300221345Sdim Edit(0), 301221345Sdim OpenIdx(0), 302221345Sdim RegAssign(Allocator) 303221345Sdim{} 304212793Sdim 305221345Sdimvoid SplitEditor::reset(LiveRangeEdit &lre) { 306221345Sdim Edit = &lre; 307221345Sdim OpenIdx = 0; 308221345Sdim RegAssign.clear(); 309218893Sdim Values.clear(); 310221345Sdim 311221345Sdim // We don't need to clear LiveOutCache, only LiveOutSeen entries are read. 312221345Sdim LiveOutSeen.clear(); 313221345Sdim 314221345Sdim // We don't need an AliasAnalysis since we will only be performing 315221345Sdim // cheap-as-a-copy remats anyway. 316221345Sdim Edit->anyRematerializable(LIS, TII, 0); 317212793Sdim} 318212793Sdim 319221345Sdimvoid SplitEditor::dump() const { 320221345Sdim if (RegAssign.empty()) { 321221345Sdim dbgs() << " empty\n"; 322221345Sdim return; 323221345Sdim } 324221345Sdim 325221345Sdim for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 326221345Sdim dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 327221345Sdim dbgs() << '\n'; 328212793Sdim} 329212793Sdim 330221345SdimVNInfo *SplitEditor::defValue(unsigned RegIdx, 331221345Sdim const VNInfo *ParentVNI, 332221345Sdim SlotIndex Idx) { 333212793Sdim assert(ParentVNI && "Mapping NULL value"); 334212793Sdim assert(Idx.isValid() && "Invalid SlotIndex"); 335221345Sdim assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 336221345Sdim LiveInterval *LI = Edit->get(RegIdx); 337212793Sdim 338218893Sdim // Create a new value. 339218893Sdim VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 340212793Sdim 341218893Sdim // Use insert for lookup, so we can add missing values with a second lookup. 342221345Sdim std::pair<ValueMap::iterator, bool> InsP = 343221345Sdim Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 344218893Sdim 345221345Sdim // This was the first time (RegIdx, ParentVNI) was mapped. 346221345Sdim // Keep it as a simple def without any liveness. 347221345Sdim if (InsP.second) 348221345Sdim return VNI; 349221345Sdim 350221345Sdim // If the previous value was a simple mapping, add liveness for it now. 351221345Sdim if (VNInfo *OldVNI = InsP.first->second) { 352221345Sdim SlotIndex Def = OldVNI->def; 353221345Sdim LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 354221345Sdim // No longer a simple mapping. 355218893Sdim InsP.first->second = 0; 356221345Sdim } 357218893Sdim 358221345Sdim // This is a complex mapping, add liveness for VNI 359221345Sdim SlotIndex Def = VNI->def; 360221345Sdim LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 361221345Sdim 362212793Sdim return VNI; 363212793Sdim} 364212793Sdim 365221345Sdimvoid SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 366212793Sdim assert(ParentVNI && "Mapping NULL value"); 367221345Sdim VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 368212793Sdim 369221345Sdim // ParentVNI was either unmapped or already complex mapped. Either way. 370221345Sdim if (!VNI) 371221345Sdim return; 372212793Sdim 373221345Sdim // This was previously a single mapping. Make sure the old def is represented 374221345Sdim // by a trivial live range. 375221345Sdim SlotIndex Def = VNI->def; 376221345Sdim Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 377221345Sdim VNI = 0; 378221345Sdim} 379218893Sdim 380221345Sdim// extendRange - Extend the live range to reach Idx. 381221345Sdim// Potentially create phi-def values. 382221345Sdimvoid SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 383221345Sdim assert(Idx.isValid() && "Invalid SlotIndex"); 384218893Sdim MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 385212793Sdim assert(IdxMBB && "No MBB at Idx"); 386221345Sdim LiveInterval *LI = Edit->get(RegIdx); 387212793Sdim 388212793Sdim // Is there a def in the same MBB we can extend? 389221345Sdim if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx)) 390221345Sdim return; 391212793Sdim 392212793Sdim // Now for the fun part. We know that ParentVNI potentially has multiple defs, 393212793Sdim // and we may need to create even more phi-defs to preserve VNInfo SSA form. 394218893Sdim // Perform a search for all predecessor blocks where we know the dominating 395221345Sdim // VNInfo. 396221345Sdim VNInfo *VNI = findReachingDefs(LI, IdxMBB, Idx.getNextSlot()); 397212793Sdim 398221345Sdim // When there were multiple different values, we may need new PHIs. 399221345Sdim if (!VNI) 400221345Sdim return updateSSA(); 401221345Sdim 402221345Sdim // Poor man's SSA update for the single-value case. 403221345Sdim LiveOutPair LOP(VNI, MDT[LIS.getMBBFromIndex(VNI->def)]); 404221345Sdim for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 405221345Sdim E = LiveInBlocks.end(); I != E; ++I) { 406221345Sdim MachineBasicBlock *MBB = I->DomNode->getBlock(); 407221345Sdim SlotIndex Start = LIS.getMBBStartIdx(MBB); 408221345Sdim if (I->Kill.isValid()) 409221345Sdim LI->addRange(LiveRange(Start, I->Kill, VNI)); 410221345Sdim else { 411221345Sdim LiveOutCache[MBB] = LOP; 412221345Sdim LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 413221345Sdim } 414221345Sdim } 415221345Sdim} 416221345Sdim 417221345Sdim/// findReachingDefs - Search the CFG for known live-out values. 418221345Sdim/// Add required live-in blocks to LiveInBlocks. 419221345SdimVNInfo *SplitEditor::findReachingDefs(LiveInterval *LI, 420221345Sdim MachineBasicBlock *KillMBB, 421221345Sdim SlotIndex Kill) { 422221345Sdim // Initialize the live-out cache the first time it is needed. 423221345Sdim if (LiveOutSeen.empty()) { 424221345Sdim unsigned N = VRM.getMachineFunction().getNumBlockIDs(); 425221345Sdim LiveOutSeen.resize(N); 426221345Sdim LiveOutCache.resize(N); 427221345Sdim } 428221345Sdim 429218893Sdim // Blocks where LI should be live-in. 430221345Sdim SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB); 431212793Sdim 432221345Sdim // Remember if we have seen more than one value. 433221345Sdim bool UniqueVNI = true; 434221345Sdim VNInfo *TheVNI = 0; 435221345Sdim 436218893Sdim // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 437221345Sdim for (unsigned i = 0; i != WorkList.size(); ++i) { 438221345Sdim MachineBasicBlock *MBB = WorkList[i]; 439221345Sdim assert(!MBB->pred_empty() && "Value live-in to entry block?"); 440218893Sdim for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 441218893Sdim PE = MBB->pred_end(); PI != PE; ++PI) { 442218893Sdim MachineBasicBlock *Pred = *PI; 443221345Sdim LiveOutPair &LOP = LiveOutCache[Pred]; 444221345Sdim 445218893Sdim // Is this a known live-out block? 446221345Sdim if (LiveOutSeen.test(Pred->getNumber())) { 447221345Sdim if (VNInfo *VNI = LOP.first) { 448221345Sdim if (TheVNI && TheVNI != VNI) 449221345Sdim UniqueVNI = false; 450221345Sdim TheVNI = VNI; 451221345Sdim } 452218893Sdim continue; 453218893Sdim } 454212793Sdim 455221345Sdim // First time. LOP is garbage and must be cleared below. 456221345Sdim LiveOutSeen.set(Pred->getNumber()); 457221345Sdim 458218893Sdim // Does Pred provide a live-out value? 459221345Sdim SlotIndex Start, Last; 460221345Sdim tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred); 461221345Sdim Last = Last.getPrevSlot(); 462221345Sdim VNInfo *VNI = LI->extendInBlock(Start, Last); 463221345Sdim LOP.first = VNI; 464221345Sdim if (VNI) { 465221345Sdim LOP.second = MDT[LIS.getMBBFromIndex(VNI->def)]; 466221345Sdim if (TheVNI && TheVNI != VNI) 467221345Sdim UniqueVNI = false; 468221345Sdim TheVNI = VNI; 469218893Sdim continue; 470218893Sdim } 471221345Sdim LOP.second = 0; 472221345Sdim 473218893Sdim // No, we need a live-in value for Pred as well 474221345Sdim if (Pred != KillMBB) 475221345Sdim WorkList.push_back(Pred); 476221345Sdim else 477221345Sdim // Loopback to KillMBB, so value is really live through. 478221345Sdim Kill = SlotIndex(); 479212793Sdim } 480218893Sdim } 481212793Sdim 482221345Sdim // Transfer WorkList to LiveInBlocks in reverse order. 483221345Sdim // This ordering works best with updateSSA(). 484221345Sdim LiveInBlocks.clear(); 485221345Sdim LiveInBlocks.reserve(WorkList.size()); 486221345Sdim while(!WorkList.empty()) 487221345Sdim LiveInBlocks.push_back(MDT[WorkList.pop_back_val()]); 488221345Sdim 489221345Sdim // The kill block may not be live-through. 490221345Sdim assert(LiveInBlocks.back().DomNode->getBlock() == KillMBB); 491221345Sdim LiveInBlocks.back().Kill = Kill; 492221345Sdim 493221345Sdim return UniqueVNI ? TheVNI : 0; 494221345Sdim} 495221345Sdim 496221345Sdimvoid SplitEditor::updateSSA() { 497218893Sdim // This is essentially the same iterative algorithm that SSAUpdater uses, 498218893Sdim // except we already have a dominator tree, so we don't have to recompute it. 499218893Sdim unsigned Changes; 500218893Sdim do { 501218893Sdim Changes = 0; 502221345Sdim // Propagate live-out values down the dominator tree, inserting phi-defs 503221345Sdim // when necessary. 504221345Sdim for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 505221345Sdim E = LiveInBlocks.end(); I != E; ++I) { 506221345Sdim MachineDomTreeNode *Node = I->DomNode; 507221345Sdim // Skip block if the live-in value has already been determined. 508221345Sdim if (!Node) 509221345Sdim continue; 510218893Sdim MachineBasicBlock *MBB = Node->getBlock(); 511218893Sdim MachineDomTreeNode *IDom = Node->getIDom(); 512218893Sdim LiveOutPair IDomValue; 513221345Sdim 514218893Sdim // We need a live-in value to a block with no immediate dominator? 515218893Sdim // This is probably an unreachable block that has survived somehow. 516221345Sdim bool needPHI = !IDom || !LiveOutSeen.test(IDom->getBlock()->getNumber()); 517212793Sdim 518221345Sdim // IDom dominates all of our predecessors, but it may not be their 519221345Sdim // immediate dominator. Check if any of them have live-out values that are 520221345Sdim // properly dominated by IDom. If so, we need a phi-def here. 521218893Sdim if (!needPHI) { 522221345Sdim IDomValue = LiveOutCache[IDom->getBlock()]; 523218893Sdim for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 524218893Sdim PE = MBB->pred_end(); PI != PE; ++PI) { 525218893Sdim LiveOutPair Value = LiveOutCache[*PI]; 526218893Sdim if (!Value.first || Value.first == IDomValue.first) 527218893Sdim continue; 528218893Sdim // This predecessor is carrying something other than IDomValue. 529218893Sdim // It could be because IDomValue hasn't propagated yet, or it could be 530218893Sdim // because MBB is in the dominance frontier of that value. 531218893Sdim if (MDT.dominates(IDom, Value.second)) { 532218893Sdim needPHI = true; 533218893Sdim break; 534218893Sdim } 535218893Sdim } 536218893Sdim } 537212793Sdim 538221345Sdim // The value may be live-through even if Kill is set, as can happen when 539221345Sdim // we are called from extendRange. In that case LiveOutSeen is true, and 540221345Sdim // LiveOutCache indicates a foreign or missing value. 541221345Sdim LiveOutPair &LOP = LiveOutCache[MBB]; 542221345Sdim 543218893Sdim // Create a phi-def if required. 544218893Sdim if (needPHI) { 545218893Sdim ++Changes; 546218893Sdim SlotIndex Start = LIS.getMBBStartIdx(MBB); 547221345Sdim unsigned RegIdx = RegAssign.lookup(Start); 548221345Sdim LiveInterval *LI = Edit->get(RegIdx); 549218893Sdim VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 550218893Sdim VNI->setIsPHIDef(true); 551221345Sdim I->Value = VNI; 552221345Sdim // This block is done, we know the final value. 553221345Sdim I->DomNode = 0; 554221345Sdim if (I->Kill.isValid()) 555221345Sdim LI->addRange(LiveRange(Start, I->Kill, VNI)); 556221345Sdim else { 557218893Sdim LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 558221345Sdim LOP = LiveOutPair(VNI, Node); 559218893Sdim } 560218893Sdim } else if (IDomValue.first) { 561221345Sdim // No phi-def here. Remember incoming value. 562221345Sdim I->Value = IDomValue.first; 563221345Sdim if (I->Kill.isValid()) 564221345Sdim continue; 565218893Sdim // Propagate IDomValue if needed: 566218893Sdim // MBB is live-out and doesn't define its own value. 567221345Sdim if (LOP.second != Node && LOP.first != IDomValue.first) { 568218893Sdim ++Changes; 569221345Sdim LOP = IDomValue; 570218893Sdim } 571212793Sdim } 572212793Sdim } 573218893Sdim } while (Changes); 574212793Sdim 575221345Sdim // The values in LiveInBlocks are now accurate. No more phi-defs are needed 576221345Sdim // for these blocks, so we can color the live ranges. 577221345Sdim for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 578221345Sdim E = LiveInBlocks.end(); I != E; ++I) { 579221345Sdim if (!I->DomNode) 580218893Sdim continue; 581221345Sdim assert(I->Value && "No live-in value found"); 582221345Sdim MachineBasicBlock *MBB = I->DomNode->getBlock(); 583218893Sdim SlotIndex Start = LIS.getMBBStartIdx(MBB); 584221345Sdim unsigned RegIdx = RegAssign.lookup(Start); 585221345Sdim LiveInterval *LI = Edit->get(RegIdx); 586221345Sdim LI->addRange(LiveRange(Start, I->Kill.isValid() ? 587221345Sdim I->Kill : LIS.getMBBEndIdx(MBB), I->Value)); 588212793Sdim } 589212793Sdim} 590212793Sdim 591218893SdimVNInfo *SplitEditor::defFromParent(unsigned RegIdx, 592218893Sdim VNInfo *ParentVNI, 593218893Sdim SlotIndex UseIdx, 594218893Sdim MachineBasicBlock &MBB, 595218893Sdim MachineBasicBlock::iterator I) { 596218893Sdim MachineInstr *CopyMI = 0; 597218893Sdim SlotIndex Def; 598221345Sdim LiveInterval *LI = Edit->get(RegIdx); 599212793Sdim 600221345Sdim // We may be trying to avoid interference that ends at a deleted instruction, 601221345Sdim // so always begin RegIdx 0 early and all others late. 602221345Sdim bool Late = RegIdx != 0; 603221345Sdim 604218893Sdim // Attempt cheap-as-a-copy rematerialization. 605218893Sdim LiveRangeEdit::Remat RM(ParentVNI); 606221345Sdim if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 607221345Sdim Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late); 608223017Sdim ++NumRemats; 609218893Sdim } else { 610218893Sdim // Can't remat, just insert a copy from parent. 611218893Sdim CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 612221345Sdim .addReg(Edit->getReg()); 613221345Sdim Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) 614221345Sdim .getDefIndex(); 615223017Sdim ++NumCopies; 616212793Sdim } 617212793Sdim 618218893Sdim // Define the value in Reg. 619221345Sdim VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 620218893Sdim VNI->setCopy(CopyMI); 621212793Sdim return VNI; 622212793Sdim} 623212793Sdim 624212793Sdim/// Create a new virtual register and live interval. 625221345Sdimunsigned SplitEditor::openIntv() { 626218893Sdim // Create the complement as index 0. 627221345Sdim if (Edit->empty()) 628221345Sdim Edit->create(LIS, VRM); 629212793Sdim 630218893Sdim // Create the open interval. 631221345Sdim OpenIdx = Edit->size(); 632221345Sdim Edit->create(LIS, VRM); 633221345Sdim return OpenIdx; 634212793Sdim} 635212793Sdim 636221345Sdimvoid SplitEditor::selectIntv(unsigned Idx) { 637221345Sdim assert(Idx != 0 && "Cannot select the complement interval"); 638221345Sdim assert(Idx < Edit->size() && "Can only select previously opened interval"); 639224145Sdim DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); 640221345Sdim OpenIdx = Idx; 641221345Sdim} 642221345Sdim 643218893SdimSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 644218893Sdim assert(OpenIdx && "openIntv not called before enterIntvBefore"); 645218893Sdim DEBUG(dbgs() << " enterIntvBefore " << Idx); 646218893Sdim Idx = Idx.getBaseIndex(); 647221345Sdim VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 648218893Sdim if (!ParentVNI) { 649218893Sdim DEBUG(dbgs() << ": not live\n"); 650218893Sdim return Idx; 651212793Sdim } 652218893Sdim DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 653218893Sdim MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 654218893Sdim assert(MI && "enterIntvBefore called with invalid index"); 655212793Sdim 656218893Sdim VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 657218893Sdim return VNI->def; 658218893Sdim} 659212793Sdim 660224145SdimSlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { 661224145Sdim assert(OpenIdx && "openIntv not called before enterIntvAfter"); 662224145Sdim DEBUG(dbgs() << " enterIntvAfter " << Idx); 663224145Sdim Idx = Idx.getBoundaryIndex(); 664224145Sdim VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 665224145Sdim if (!ParentVNI) { 666224145Sdim DEBUG(dbgs() << ": not live\n"); 667224145Sdim return Idx; 668224145Sdim } 669224145Sdim DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 670224145Sdim MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 671224145Sdim assert(MI && "enterIntvAfter called with invalid index"); 672224145Sdim 673224145Sdim VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), 674224145Sdim llvm::next(MachineBasicBlock::iterator(MI))); 675224145Sdim return VNI->def; 676224145Sdim} 677224145Sdim 678218893SdimSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 679218893Sdim assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 680218893Sdim SlotIndex End = LIS.getMBBEndIdx(&MBB); 681218893Sdim SlotIndex Last = End.getPrevSlot(); 682218893Sdim DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 683221345Sdim VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 684218893Sdim if (!ParentVNI) { 685218893Sdim DEBUG(dbgs() << ": not live\n"); 686218893Sdim return End; 687212793Sdim } 688218893Sdim DEBUG(dbgs() << ": valno " << ParentVNI->id); 689218893Sdim VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 690221345Sdim LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 691218893Sdim RegAssign.insert(VNI->def, End, OpenIdx); 692218893Sdim DEBUG(dump()); 693218893Sdim return VNI->def; 694212793Sdim} 695212793Sdim 696218893Sdim/// useIntv - indicate that all instructions in MBB should use OpenLI. 697212793Sdimvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 698218893Sdim useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 699212793Sdim} 700212793Sdim 701212793Sdimvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 702218893Sdim assert(OpenIdx && "openIntv not called before useIntv"); 703218893Sdim DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 704218893Sdim RegAssign.insert(Start, End, OpenIdx); 705218893Sdim DEBUG(dump()); 706218893Sdim} 707212793Sdim 708218893SdimSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 709218893Sdim assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 710218893Sdim DEBUG(dbgs() << " leaveIntvAfter " << Idx); 711212793Sdim 712218893Sdim // The interval must be live beyond the instruction at Idx. 713218893Sdim Idx = Idx.getBoundaryIndex(); 714221345Sdim VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 715218893Sdim if (!ParentVNI) { 716218893Sdim DEBUG(dbgs() << ": not live\n"); 717218893Sdim return Idx.getNextSlot(); 718212793Sdim } 719218893Sdim DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 720212793Sdim 721218893Sdim MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 722218893Sdim assert(MI && "No instruction at index"); 723218893Sdim VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 724218893Sdim llvm::next(MachineBasicBlock::iterator(MI))); 725218893Sdim return VNI->def; 726212793Sdim} 727212793Sdim 728218893SdimSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 729218893Sdim assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 730218893Sdim DEBUG(dbgs() << " leaveIntvBefore " << Idx); 731212793Sdim 732218893Sdim // The interval must be live into the instruction at Idx. 733218893Sdim Idx = Idx.getBoundaryIndex(); 734221345Sdim VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 735218893Sdim if (!ParentVNI) { 736218893Sdim DEBUG(dbgs() << ": not live\n"); 737218893Sdim return Idx.getNextSlot(); 738212793Sdim } 739218893Sdim DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 740212793Sdim 741218893Sdim MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 742218893Sdim assert(MI && "No instruction at index"); 743218893Sdim VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 744218893Sdim return VNI->def; 745212793Sdim} 746212793Sdim 747218893SdimSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 748218893Sdim assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 749218893Sdim SlotIndex Start = LIS.getMBBStartIdx(&MBB); 750218893Sdim DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 751212793Sdim 752221345Sdim VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 753218893Sdim if (!ParentVNI) { 754218893Sdim DEBUG(dbgs() << ": not live\n"); 755218893Sdim return Start; 756212793Sdim } 757212793Sdim 758218893Sdim VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 759218893Sdim MBB.SkipPHIsAndLabels(MBB.begin())); 760218893Sdim RegAssign.insert(Start, VNI->def, OpenIdx); 761218893Sdim DEBUG(dump()); 762218893Sdim return VNI->def; 763218893Sdim} 764212793Sdim 765218893Sdimvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 766218893Sdim assert(OpenIdx && "openIntv not called before overlapIntv"); 767221345Sdim const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 768221345Sdim assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 769218893Sdim "Parent changes value in extended range"); 770218893Sdim assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 771218893Sdim "Range cannot span basic blocks"); 772212793Sdim 773221345Sdim // The complement interval will be extended as needed by extendRange(). 774221345Sdim if (ParentVNI) 775221345Sdim markComplexMapped(0, ParentVNI); 776218893Sdim DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 777218893Sdim RegAssign.insert(Start, End, OpenIdx); 778218893Sdim DEBUG(dump()); 779212793Sdim} 780212793Sdim 781221345Sdim/// transferValues - Transfer all possible values to the new live ranges. 782221345Sdim/// Values that were rematerialized are left alone, they need extendRange(). 783221345Sdimbool SplitEditor::transferValues() { 784221345Sdim bool Skipped = false; 785221345Sdim LiveInBlocks.clear(); 786221345Sdim RegAssignMap::const_iterator AssignI = RegAssign.begin(); 787221345Sdim for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 788221345Sdim ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 789221345Sdim DEBUG(dbgs() << " blit " << *ParentI << ':'); 790221345Sdim VNInfo *ParentVNI = ParentI->valno; 791221345Sdim // RegAssign has holes where RegIdx 0 should be used. 792221345Sdim SlotIndex Start = ParentI->start; 793221345Sdim AssignI.advanceTo(Start); 794221345Sdim do { 795221345Sdim unsigned RegIdx; 796221345Sdim SlotIndex End = ParentI->end; 797221345Sdim if (!AssignI.valid()) { 798221345Sdim RegIdx = 0; 799221345Sdim } else if (AssignI.start() <= Start) { 800221345Sdim RegIdx = AssignI.value(); 801221345Sdim if (AssignI.stop() < End) { 802221345Sdim End = AssignI.stop(); 803221345Sdim ++AssignI; 804221345Sdim } 805221345Sdim } else { 806221345Sdim RegIdx = 0; 807221345Sdim End = std::min(End, AssignI.start()); 808221345Sdim } 809221345Sdim 810221345Sdim // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 811221345Sdim DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 812221345Sdim LiveInterval *LI = Edit->get(RegIdx); 813221345Sdim 814221345Sdim // Check for a simply defined value that can be blitted directly. 815221345Sdim if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 816221345Sdim DEBUG(dbgs() << ':' << VNI->id); 817221345Sdim LI->addRange(LiveRange(Start, End, VNI)); 818221345Sdim Start = End; 819221345Sdim continue; 820221345Sdim } 821221345Sdim 822221345Sdim // Skip rematerialized values, we need to use extendRange() and 823221345Sdim // extendPHIKillRanges() to completely recompute the live ranges. 824221345Sdim if (Edit->didRematerialize(ParentVNI)) { 825221345Sdim DEBUG(dbgs() << "(remat)"); 826221345Sdim Skipped = true; 827221345Sdim Start = End; 828221345Sdim continue; 829221345Sdim } 830221345Sdim 831221345Sdim // Initialize the live-out cache the first time it is needed. 832221345Sdim if (LiveOutSeen.empty()) { 833221345Sdim unsigned N = VRM.getMachineFunction().getNumBlockIDs(); 834221345Sdim LiveOutSeen.resize(N); 835221345Sdim LiveOutCache.resize(N); 836221345Sdim } 837221345Sdim 838221345Sdim // This value has multiple defs in RegIdx, but it wasn't rematerialized, 839221345Sdim // so the live range is accurate. Add live-in blocks in [Start;End) to the 840221345Sdim // LiveInBlocks. 841221345Sdim MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 842221345Sdim SlotIndex BlockStart, BlockEnd; 843221345Sdim tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 844221345Sdim 845221345Sdim // The first block may be live-in, or it may have its own def. 846221345Sdim if (Start != BlockStart) { 847221345Sdim VNInfo *VNI = LI->extendInBlock(BlockStart, 848221345Sdim std::min(BlockEnd, End).getPrevSlot()); 849221345Sdim assert(VNI && "Missing def for complex mapped value"); 850221345Sdim DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 851221345Sdim // MBB has its own def. Is it also live-out? 852221345Sdim if (BlockEnd <= End) { 853221345Sdim LiveOutSeen.set(MBB->getNumber()); 854221345Sdim LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]); 855221345Sdim } 856221345Sdim // Skip to the next block for live-in. 857221345Sdim ++MBB; 858221345Sdim BlockStart = BlockEnd; 859221345Sdim } 860221345Sdim 861221345Sdim // Handle the live-in blocks covered by [Start;End). 862221345Sdim assert(Start <= BlockStart && "Expected live-in block"); 863221345Sdim while (BlockStart < End) { 864221345Sdim DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 865221345Sdim BlockEnd = LIS.getMBBEndIdx(MBB); 866221345Sdim if (BlockStart == ParentVNI->def) { 867221345Sdim // This block has the def of a parent PHI, so it isn't live-in. 868221345Sdim assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 869221345Sdim VNInfo *VNI = LI->extendInBlock(BlockStart, 870221345Sdim std::min(BlockEnd, End).getPrevSlot()); 871221345Sdim assert(VNI && "Missing def for complex mapped parent PHI"); 872221345Sdim if (End >= BlockEnd) { 873221345Sdim // Live-out as well. 874221345Sdim LiveOutSeen.set(MBB->getNumber()); 875221345Sdim LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]); 876221345Sdim } 877221345Sdim } else { 878221345Sdim // This block needs a live-in value. 879221345Sdim LiveInBlocks.push_back(MDT[MBB]); 880221345Sdim // The last block covered may not be live-out. 881221345Sdim if (End < BlockEnd) 882221345Sdim LiveInBlocks.back().Kill = End; 883221345Sdim else { 884221345Sdim // Live-out, but we need updateSSA to tell us the value. 885221345Sdim LiveOutSeen.set(MBB->getNumber()); 886221345Sdim LiveOutCache[MBB] = LiveOutPair((VNInfo*)0, 887221345Sdim (MachineDomTreeNode*)0); 888221345Sdim } 889221345Sdim } 890221345Sdim BlockStart = BlockEnd; 891221345Sdim ++MBB; 892221345Sdim } 893221345Sdim Start = End; 894221345Sdim } while (Start != ParentI->end); 895221345Sdim DEBUG(dbgs() << '\n'); 896221345Sdim } 897221345Sdim 898221345Sdim if (!LiveInBlocks.empty()) 899221345Sdim updateSSA(); 900221345Sdim 901221345Sdim return Skipped; 902212793Sdim} 903212793Sdim 904221345Sdimvoid SplitEditor::extendPHIKillRanges() { 905221345Sdim // Extend live ranges to be live-out for successor PHI values. 906221345Sdim for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 907221345Sdim E = Edit->getParent().vni_end(); I != E; ++I) { 908221345Sdim const VNInfo *PHIVNI = *I; 909221345Sdim if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 910221345Sdim continue; 911221345Sdim unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 912221345Sdim MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 913221345Sdim for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 914221345Sdim PE = MBB->pred_end(); PI != PE; ++PI) { 915221345Sdim SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 916221345Sdim // The predecessor may not have a live-out value. That is OK, like an 917221345Sdim // undef PHI operand. 918221345Sdim if (Edit->getParent().liveAt(End)) { 919221345Sdim assert(RegAssign.lookup(End) == RegIdx && 920221345Sdim "Different register assignment in phi predecessor"); 921221345Sdim extendRange(RegIdx, End); 922221345Sdim } 923221345Sdim } 924221345Sdim } 925221345Sdim} 926221345Sdim 927221345Sdim/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 928221345Sdimvoid SplitEditor::rewriteAssigned(bool ExtendRanges) { 929221345Sdim for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 930218893Sdim RE = MRI.reg_end(); RI != RE;) { 931212793Sdim MachineOperand &MO = RI.getOperand(); 932212793Sdim MachineInstr *MI = MO.getParent(); 933212793Sdim ++RI; 934218893Sdim // LiveDebugVariables should have handled all DBG_VALUE instructions. 935212793Sdim if (MI->isDebugValue()) { 936212793Sdim DEBUG(dbgs() << "Zapping " << *MI); 937212793Sdim MO.setReg(0); 938212793Sdim continue; 939212793Sdim } 940218893Sdim 941218893Sdim // <undef> operands don't really read the register, so just assign them to 942218893Sdim // the complement. 943218893Sdim if (MO.isUse() && MO.isUndef()) { 944221345Sdim MO.setReg(Edit->get(0)->reg); 945218893Sdim continue; 946212793Sdim } 947212793Sdim 948218893Sdim SlotIndex Idx = LIS.getInstructionIndex(MI); 949221345Sdim if (MO.isDef()) 950221345Sdim Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex(); 951218893Sdim 952218893Sdim // Rewrite to the mapped register at Idx. 953218893Sdim unsigned RegIdx = RegAssign.lookup(Idx); 954221345Sdim MO.setReg(Edit->get(RegIdx)->reg); 955218893Sdim DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 956218893Sdim << Idx << ':' << RegIdx << '\t' << *MI); 957218893Sdim 958221345Sdim // Extend liveness to Idx if the instruction reads reg. 959221345Sdim if (!ExtendRanges) 960221345Sdim continue; 961221345Sdim 962221345Sdim // Skip instructions that don't read Reg. 963221345Sdim if (MO.isDef()) { 964221345Sdim if (!MO.getSubReg() && !MO.isEarlyClobber()) 965221345Sdim continue; 966221345Sdim // We may wan't to extend a live range for a partial redef, or for a use 967221345Sdim // tied to an early clobber. 968221345Sdim Idx = Idx.getPrevSlot(); 969221345Sdim if (!Edit->getParent().liveAt(Idx)) 970221345Sdim continue; 971221345Sdim } else 972221345Sdim Idx = Idx.getUseIndex(); 973221345Sdim 974221345Sdim extendRange(RegIdx, Idx); 975212793Sdim } 976218893Sdim} 977212793Sdim 978221345Sdimvoid SplitEditor::deleteRematVictims() { 979221345Sdim SmallVector<MachineInstr*, 8> Dead; 980221345Sdim for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 981221345Sdim LiveInterval *LI = *I; 982221345Sdim for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 983221345Sdim LII != LIE; ++LII) { 984221345Sdim // Dead defs end at the store slot. 985221345Sdim if (LII->end != LII->valno->def.getNextSlot()) 986221345Sdim continue; 987221345Sdim MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 988221345Sdim assert(MI && "Missing instruction for dead def"); 989221345Sdim MI->addRegisterDead(LI->reg, &TRI); 990221345Sdim 991221345Sdim if (!MI->allDefsAreDead()) 992221345Sdim continue; 993221345Sdim 994221345Sdim DEBUG(dbgs() << "All defs dead: " << *MI); 995221345Sdim Dead.push_back(MI); 996221345Sdim } 997212793Sdim } 998221345Sdim 999221345Sdim if (Dead.empty()) 1000221345Sdim return; 1001221345Sdim 1002221345Sdim Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); 1003212793Sdim} 1004212793Sdim 1005221345Sdimvoid SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 1006221345Sdim ++NumFinished; 1007212793Sdim 1008218893Sdim // At this point, the live intervals in Edit contain VNInfos corresponding to 1009218893Sdim // the inserted copies. 1010212793Sdim 1011218893Sdim // Add the original defs from the parent interval. 1012221345Sdim for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 1013221345Sdim E = Edit->getParent().vni_end(); I != E; ++I) { 1014218893Sdim const VNInfo *ParentVNI = *I; 1015218893Sdim if (ParentVNI->isUnused()) 1016218893Sdim continue; 1017221345Sdim unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 1018221345Sdim VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 1019221345Sdim VNI->setIsPHIDef(ParentVNI->isPHIDef()); 1020221345Sdim VNI->setCopy(ParentVNI->getCopy()); 1021221345Sdim 1022221345Sdim // Mark rematted values as complex everywhere to force liveness computation. 1023221345Sdim // The new live ranges may be truncated. 1024221345Sdim if (Edit->didRematerialize(ParentVNI)) 1025221345Sdim for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1026221345Sdim markComplexMapped(i, ParentVNI); 1027218893Sdim } 1028212793Sdim 1029221345Sdim // Transfer the simply mapped values, check if any are skipped. 1030221345Sdim bool Skipped = transferValues(); 1031221345Sdim if (Skipped) 1032221345Sdim extendPHIKillRanges(); 1033221345Sdim else 1034221345Sdim ++NumSimple; 1035212793Sdim 1036221345Sdim // Rewrite virtual registers, possibly extending ranges. 1037221345Sdim rewriteAssigned(Skipped); 1038212793Sdim 1039221345Sdim // Delete defs that were rematted everywhere. 1040221345Sdim if (Skipped) 1041221345Sdim deleteRematVictims(); 1042212793Sdim 1043218893Sdim // Get rid of unused values and set phi-kill flags. 1044221345Sdim for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 1045218893Sdim (*I)->RenumberValues(LIS); 1046218893Sdim 1047221345Sdim // Provide a reverse mapping from original indices to Edit ranges. 1048221345Sdim if (LRMap) { 1049221345Sdim LRMap->clear(); 1050221345Sdim for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1051221345Sdim LRMap->push_back(i); 1052221345Sdim } 1053221345Sdim 1054218893Sdim // Now check if any registers were separated into multiple components. 1055218893Sdim ConnectedVNInfoEqClasses ConEQ(LIS); 1056221345Sdim for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 1057218893Sdim // Don't use iterators, they are invalidated by create() below. 1058221345Sdim LiveInterval *li = Edit->get(i); 1059218893Sdim unsigned NumComp = ConEQ.Classify(li); 1060218893Sdim if (NumComp <= 1) 1061218893Sdim continue; 1062218893Sdim DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 1063218893Sdim SmallVector<LiveInterval*, 8> dups; 1064218893Sdim dups.push_back(li); 1065221345Sdim for (unsigned j = 1; j != NumComp; ++j) 1066221345Sdim dups.push_back(&Edit->create(LIS, VRM)); 1067221345Sdim ConEQ.Distribute(&dups[0], MRI); 1068221345Sdim // The new intervals all map back to i. 1069221345Sdim if (LRMap) 1070221345Sdim LRMap->resize(Edit->size(), i); 1071212793Sdim } 1072212793Sdim 1073218893Sdim // Calculate spill weight and allocation hints for new intervals. 1074221345Sdim Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops); 1075221345Sdim 1076221345Sdim assert(!LRMap || LRMap->size() == Edit->size()); 1077212793Sdim} 1078212793Sdim 1079212793Sdim 1080212793Sdim//===----------------------------------------------------------------------===// 1081212793Sdim// Single Block Splitting 1082212793Sdim//===----------------------------------------------------------------------===// 1083212793Sdim 1084218893Sdim/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 1085218893Sdim/// may be an advantage to split CurLI for the duration of the block. 1086218893Sdimbool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 1087218893Sdim // If CurLI is local to one block, there is no point to splitting it. 1088221345Sdim if (UseBlocks.size() <= 1) 1089218893Sdim return false; 1090218893Sdim // Add blocks with multiple uses. 1091221345Sdim for (unsigned i = 0, e = UseBlocks.size(); i != e; ++i) { 1092221345Sdim const BlockInfo &BI = UseBlocks[i]; 1093221345Sdim if (BI.FirstUse == BI.LastUse) 1094212793Sdim continue; 1095218893Sdim Blocks.insert(BI.MBB); 1096212793Sdim } 1097218893Sdim return !Blocks.empty(); 1098218893Sdim} 1099212793Sdim 1100221345Sdimvoid SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 1101221345Sdim openIntv(); 1102221345Sdim SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 1103221345Sdim SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstUse, 1104221345Sdim LastSplitPoint)); 1105221345Sdim if (!BI.LiveOut || BI.LastUse < LastSplitPoint) { 1106221345Sdim useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 1107221345Sdim } else { 1108221345Sdim // The last use is after the last valid split point. 1109221345Sdim SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 1110221345Sdim useIntv(SegStart, SegStop); 1111221345Sdim overlapIntv(SegStop, BI.LastUse); 1112221345Sdim } 1113221345Sdim} 1114221345Sdim 1115218893Sdim/// splitSingleBlocks - Split CurLI into a separate live interval inside each 1116218893Sdim/// basic block in Blocks. 1117218893Sdimvoid SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 1118218893Sdim DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 1119221345Sdim ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA.getUseBlocks(); 1120221345Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1121221345Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1122221345Sdim if (Blocks.count(BI.MBB)) 1123221345Sdim splitSingleBlock(BI); 1124212793Sdim } 1125218893Sdim finish(); 1126212793Sdim} 1127224145Sdim 1128224145Sdim 1129224145Sdim//===----------------------------------------------------------------------===// 1130224145Sdim// Global Live Range Splitting Support 1131224145Sdim//===----------------------------------------------------------------------===// 1132224145Sdim 1133224145Sdim// These methods support a method of global live range splitting that uses a 1134224145Sdim// global algorithm to decide intervals for CFG edges. They will insert split 1135224145Sdim// points and color intervals in basic blocks while avoiding interference. 1136224145Sdim// 1137224145Sdim// Note that splitSingleBlock is also useful for blocks where both CFG edges 1138224145Sdim// are on the stack. 1139224145Sdim 1140224145Sdimvoid SplitEditor::splitLiveThroughBlock(unsigned MBBNum, 1141224145Sdim unsigned IntvIn, SlotIndex LeaveBefore, 1142224145Sdim unsigned IntvOut, SlotIndex EnterAfter){ 1143224145Sdim SlotIndex Start, Stop; 1144224145Sdim tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); 1145224145Sdim 1146224145Sdim DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop 1147224145Sdim << ") intf " << LeaveBefore << '-' << EnterAfter 1148224145Sdim << ", live-through " << IntvIn << " -> " << IntvOut); 1149224145Sdim 1150224145Sdim assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks"); 1151224145Sdim 1152224145Sdim if (!IntvOut) { 1153224145Sdim DEBUG(dbgs() << ", spill on entry.\n"); 1154224145Sdim // 1155224145Sdim // <<<<<<<<< Possible LeaveBefore interference. 1156224145Sdim // |-----------| Live through. 1157224145Sdim // -____________ Spill on entry. 1158224145Sdim // 1159224145Sdim selectIntv(IntvIn); 1160224145Sdim MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); 1161224145Sdim SlotIndex Idx = leaveIntvAtTop(*MBB); 1162224145Sdim assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1163224145Sdim (void)Idx; 1164224145Sdim return; 1165224145Sdim } 1166224145Sdim 1167224145Sdim if (!IntvIn) { 1168224145Sdim DEBUG(dbgs() << ", reload on exit.\n"); 1169224145Sdim // 1170224145Sdim // >>>>>>> Possible EnterAfter interference. 1171224145Sdim // |-----------| Live through. 1172224145Sdim // ___________-- Reload on exit. 1173224145Sdim // 1174224145Sdim selectIntv(IntvOut); 1175224145Sdim MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); 1176224145Sdim SlotIndex Idx = enterIntvAtEnd(*MBB); 1177224145Sdim assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1178224145Sdim (void)Idx; 1179224145Sdim return; 1180224145Sdim } 1181224145Sdim 1182224145Sdim if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { 1183224145Sdim DEBUG(dbgs() << ", straight through.\n"); 1184224145Sdim // 1185224145Sdim // |-----------| Live through. 1186224145Sdim // ------------- Straight through, same intv, no interference. 1187224145Sdim // 1188224145Sdim selectIntv(IntvOut); 1189224145Sdim useIntv(Start, Stop); 1190224145Sdim return; 1191224145Sdim } 1192224145Sdim 1193224145Sdim // We cannot legally insert splits after LSP. 1194224145Sdim SlotIndex LSP = SA.getLastSplitPoint(MBBNum); 1195224145Sdim 1196224145Sdim if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || 1197224145Sdim LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { 1198224145Sdim DEBUG(dbgs() << ", switch avoiding interference.\n"); 1199224145Sdim // 1200224145Sdim // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. 1201224145Sdim // |-----------| Live through. 1202224145Sdim // ------======= Switch intervals between interference. 1203224145Sdim // 1204224145Sdim SlotIndex Cut = (LeaveBefore && LeaveBefore < LSP) ? LeaveBefore : LSP; 1205224145Sdim selectIntv(IntvOut); 1206224145Sdim SlotIndex Idx = enterIntvBefore(Cut); 1207224145Sdim useIntv(Idx, Stop); 1208224145Sdim selectIntv(IntvIn); 1209224145Sdim useIntv(Start, Idx); 1210224145Sdim assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1211224145Sdim assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1212224145Sdim return; 1213224145Sdim } 1214224145Sdim 1215224145Sdim DEBUG(dbgs() << ", create local intv for interference.\n"); 1216224145Sdim // 1217224145Sdim // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. 1218224145Sdim // |-----------| Live through. 1219224145Sdim // ==---------== Switch intervals before/after interference. 1220224145Sdim // 1221224145Sdim assert(LeaveBefore <= EnterAfter && "Missed case"); 1222224145Sdim 1223224145Sdim selectIntv(IntvOut); 1224224145Sdim SlotIndex Idx = enterIntvAfter(EnterAfter); 1225224145Sdim useIntv(Idx, Stop); 1226224145Sdim assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1227224145Sdim 1228224145Sdim selectIntv(IntvIn); 1229224145Sdim Idx = leaveIntvBefore(LeaveBefore); 1230224145Sdim useIntv(Start, Idx); 1231224145Sdim assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1232224145Sdim} 1233224145Sdim 1234224145Sdim 1235224145Sdimvoid SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 1236224145Sdim unsigned IntvIn, SlotIndex LeaveBefore) { 1237224145Sdim SlotIndex Start, Stop; 1238224145Sdim tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1239224145Sdim 1240224145Sdim DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1241224145Sdim << "), uses " << BI.FirstUse << '-' << BI.LastUse 1242224145Sdim << ", reg-in " << IntvIn << ", leave before " << LeaveBefore 1243224145Sdim << (BI.LiveOut ? ", stack-out" : ", killed in block")); 1244224145Sdim 1245224145Sdim assert(IntvIn && "Must have register in"); 1246224145Sdim assert(BI.LiveIn && "Must be live-in"); 1247224145Sdim assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference"); 1248224145Sdim 1249224145Sdim if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastUse)) { 1250224145Sdim DEBUG(dbgs() << " before interference.\n"); 1251224145Sdim // 1252224145Sdim // <<< Interference after kill. 1253224145Sdim // |---o---x | Killed in block. 1254224145Sdim // ========= Use IntvIn everywhere. 1255224145Sdim // 1256224145Sdim selectIntv(IntvIn); 1257224145Sdim useIntv(Start, BI.LastUse); 1258224145Sdim return; 1259224145Sdim } 1260224145Sdim 1261224145Sdim SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1262224145Sdim 1263224145Sdim if (!LeaveBefore || LeaveBefore > BI.LastUse.getBoundaryIndex()) { 1264224145Sdim // 1265224145Sdim // <<< Possible interference after last use. 1266224145Sdim // |---o---o---| Live-out on stack. 1267224145Sdim // =========____ Leave IntvIn after last use. 1268224145Sdim // 1269224145Sdim // < Interference after last use. 1270224145Sdim // |---o---o--o| Live-out on stack, late last use. 1271224145Sdim // ============ Copy to stack after LSP, overlap IntvIn. 1272224145Sdim // \_____ Stack interval is live-out. 1273224145Sdim // 1274224145Sdim if (BI.LastUse < LSP) { 1275224145Sdim DEBUG(dbgs() << ", spill after last use before interference.\n"); 1276224145Sdim selectIntv(IntvIn); 1277224145Sdim SlotIndex Idx = leaveIntvAfter(BI.LastUse); 1278224145Sdim useIntv(Start, Idx); 1279224145Sdim assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1280224145Sdim } else { 1281224145Sdim DEBUG(dbgs() << ", spill before last split point.\n"); 1282224145Sdim selectIntv(IntvIn); 1283224145Sdim SlotIndex Idx = leaveIntvBefore(LSP); 1284224145Sdim overlapIntv(Idx, BI.LastUse); 1285224145Sdim useIntv(Start, Idx); 1286224145Sdim assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1287224145Sdim } 1288224145Sdim return; 1289224145Sdim } 1290224145Sdim 1291224145Sdim // The interference is overlapping somewhere we wanted to use IntvIn. That 1292224145Sdim // means we need to create a local interval that can be allocated a 1293224145Sdim // different register. 1294224145Sdim unsigned LocalIntv = openIntv(); 1295224145Sdim (void)LocalIntv; 1296224145Sdim DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n"); 1297224145Sdim 1298224145Sdim if (!BI.LiveOut || BI.LastUse < LSP) { 1299224145Sdim // 1300224145Sdim // <<<<<<< Interference overlapping uses. 1301224145Sdim // |---o---o---| Live-out on stack. 1302224145Sdim // =====----____ Leave IntvIn before interference, then spill. 1303224145Sdim // 1304224145Sdim SlotIndex To = leaveIntvAfter(BI.LastUse); 1305224145Sdim SlotIndex From = enterIntvBefore(LeaveBefore); 1306224145Sdim useIntv(From, To); 1307224145Sdim selectIntv(IntvIn); 1308224145Sdim useIntv(Start, From); 1309224145Sdim assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1310224145Sdim return; 1311224145Sdim } 1312224145Sdim 1313224145Sdim // <<<<<<< Interference overlapping uses. 1314224145Sdim // |---o---o--o| Live-out on stack, late last use. 1315224145Sdim // =====------- Copy to stack before LSP, overlap LocalIntv. 1316224145Sdim // \_____ Stack interval is live-out. 1317224145Sdim // 1318224145Sdim SlotIndex To = leaveIntvBefore(LSP); 1319224145Sdim overlapIntv(To, BI.LastUse); 1320224145Sdim SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); 1321224145Sdim useIntv(From, To); 1322224145Sdim selectIntv(IntvIn); 1323224145Sdim useIntv(Start, From); 1324224145Sdim assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1325224145Sdim} 1326224145Sdim 1327224145Sdimvoid SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 1328224145Sdim unsigned IntvOut, SlotIndex EnterAfter) { 1329224145Sdim SlotIndex Start, Stop; 1330224145Sdim tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1331224145Sdim 1332224145Sdim DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1333224145Sdim << "), uses " << BI.FirstUse << '-' << BI.LastUse 1334224145Sdim << ", reg-out " << IntvOut << ", enter after " << EnterAfter 1335224145Sdim << (BI.LiveIn ? ", stack-in" : ", defined in block")); 1336224145Sdim 1337224145Sdim SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1338224145Sdim 1339224145Sdim assert(IntvOut && "Must have register out"); 1340224145Sdim assert(BI.LiveOut && "Must be live-out"); 1341224145Sdim assert((!EnterAfter || EnterAfter < LSP) && "Bad interference"); 1342224145Sdim 1343224145Sdim if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstUse)) { 1344224145Sdim DEBUG(dbgs() << " after interference.\n"); 1345224145Sdim // 1346224145Sdim // >>>> Interference before def. 1347224145Sdim // | o---o---| Defined in block. 1348224145Sdim // ========= Use IntvOut everywhere. 1349224145Sdim // 1350224145Sdim selectIntv(IntvOut); 1351224145Sdim useIntv(BI.FirstUse, Stop); 1352224145Sdim return; 1353224145Sdim } 1354224145Sdim 1355224145Sdim if (!EnterAfter || EnterAfter < BI.FirstUse.getBaseIndex()) { 1356224145Sdim DEBUG(dbgs() << ", reload after interference.\n"); 1357224145Sdim // 1358224145Sdim // >>>> Interference before def. 1359224145Sdim // |---o---o---| Live-through, stack-in. 1360224145Sdim // ____========= Enter IntvOut before first use. 1361224145Sdim // 1362224145Sdim selectIntv(IntvOut); 1363224145Sdim SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstUse)); 1364224145Sdim useIntv(Idx, Stop); 1365224145Sdim assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1366224145Sdim return; 1367224145Sdim } 1368224145Sdim 1369224145Sdim // The interference is overlapping somewhere we wanted to use IntvOut. That 1370224145Sdim // means we need to create a local interval that can be allocated a 1371224145Sdim // different register. 1372224145Sdim DEBUG(dbgs() << ", interference overlaps uses.\n"); 1373224145Sdim // 1374224145Sdim // >>>>>>> Interference overlapping uses. 1375224145Sdim // |---o---o---| Live-through, stack-in. 1376224145Sdim // ____---====== Create local interval for interference range. 1377224145Sdim // 1378224145Sdim selectIntv(IntvOut); 1379224145Sdim SlotIndex Idx = enterIntvAfter(EnterAfter); 1380224145Sdim useIntv(Idx, Stop); 1381224145Sdim assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1382224145Sdim 1383224145Sdim openIntv(); 1384224145Sdim SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstUse)); 1385224145Sdim useIntv(From, Idx); 1386224145Sdim} 1387