SplitKit.cpp revision 8701768ae2e93e8741106acfa4a29959e1439487
18ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 28ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 38ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// The LLVM Compiler Infrastructure 48ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 58ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// License. See LICENSE.TXT for details. 78ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 88ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 98ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 108ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// This file contains the SplitAnalysis class as well as mutator functions for 118ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// live range splitting. 128ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 138ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 148ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 15376dcbd6c2c7adb8281f89d045b307eee7bd682aJakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "SplitKit.h" 17a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen#include "LiveRangeEdit.h" 18f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "VirtRegMap.h" 194670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 2008e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen#include "llvm/CodeGen/CalcSpillWeights.h" 218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 22d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 23f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 256a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/Debug.h" 278ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 286a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 296a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 318ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenusing namespace llvm; 328ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 336a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenstatic cl::opt<bool> 346a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund OlesenAllowSplit("spiller-splits-edges", 356a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen cl::desc("Allow critical edge splitting during spilling")); 368ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 374670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund OlesenSTATISTIC(NumFinished, "Number of splits finished"); 384670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund OlesenSTATISTIC(NumSimple, "Number of splits that were simple"); 394670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 408ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 418ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// Split Analysis 428ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 438ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 441b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund OlesenSplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 45f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const LiveIntervals &lis, 46f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli) 471b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen : MF(vrm.getMachineFunction()), 481b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen VRM(vrm), 49078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LIS(lis), 50078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Loops(mli), 511b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen TII(*MF.getTarget().getInstrInfo()), 52078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI(0) {} 538ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 548ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::clear() { 55b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen UseSlots.clear(); 56078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen UsingInstrs.clear(); 57078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen UsingBlocks.clear(); 58f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveBlocks.clear(); 59078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = 0; 608ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 618ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 626a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenbool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) { 636a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen MachineBasicBlock *T, *F; 646a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen SmallVector<MachineOperand, 4> Cond; 65078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen return !TII.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond); 666a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen} 676a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 68078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 69abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesenvoid SplitAnalysis::analyzeUses() { 70078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineRegisterInfo &MRI = MF.getRegInfo(); 71a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(CurLI->reg), 72a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen E = MRI.reg_end(); I != E; ++I) { 73a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen MachineOperand &MO = I.getOperand(); 74a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen if (MO.isUse() && MO.isUndef()) 75a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen continue; 76a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 77078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (MI->isDebugValue() || !UsingInstrs.insert(MI)) 788ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen continue; 79078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen UseSlots.push_back(LIS.getInstructionIndex(MI).getDefIndex()); 808ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen MachineBasicBlock *MBB = MI->getParent(); 814f5c9d206139f946ae4bb5ee7e3ddb1714057cdbJakob Stoklund Olesen UsingBlocks[MBB]++; 828ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen } 83b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen array_pod_sort(UseSlots.begin(), UseSlots.end()); 84f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen calcLiveBlockInfo(); 85e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen DEBUG(dbgs() << " counted " 86078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen << UsingInstrs.size() << " instrs, " 874f5c9d206139f946ae4bb5ee7e3ddb1714057cdbJakob Stoklund Olesen << UsingBlocks.size() << " blocks.\n"); 888ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 898ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 90f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 91f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// where CurLI is live. 92f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesenvoid SplitAnalysis::calcLiveBlockInfo() { 93f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (CurLI->empty()) 94f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen return; 95f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 96f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVI = CurLI->begin(); 97f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVE = CurLI->end(); 98f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 99f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 100f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseI = UseSlots.begin(); 101f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseE = UseSlots.end(); 102f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 103f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Loop over basic blocks where CurLI is live. 104f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 105f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (;;) { 106f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BlockInfo BI; 107f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.MBB = MFI; 108f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex Start, Stop; 109f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 110f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 111f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // The last split point is the latest possible insertion point that dominates 112f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // all successor blocks. If interference reaches LastSplitPoint, it is not 113f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // possible to insert a split or reload that makes CurLI live in the 114f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // outgoing bundle. 115f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineBasicBlock::iterator LSP = LIS.getLastSplitPoint(*CurLI, BI.MBB); 116f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LSP == BI.MBB->end()) 117f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LastSplitPoint = Stop; 118f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 119f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LastSplitPoint = LIS.getInstructionIndex(LSP); 120f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 121f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // LVI is the first live segment overlapping MBB. 122f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveIn = LVI->start <= Start; 123f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (!BI.LiveIn) 124f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Def = LVI->start; 125f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 126f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Find the first and last uses in the block. 127f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Uses = hasUses(MFI); 128f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (BI.Uses && UseI != UseE) { 129f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.FirstUse = *UseI; 130f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen assert(BI.FirstUse >= Start); 131f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen do ++UseI; 132f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen while (UseI != UseE && *UseI < Stop); 133f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LastUse = UseI[-1]; 134f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen assert(BI.LastUse < Stop); 135f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 136f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 137f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Look for gaps in the live range. 138f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool hasGap = false; 139f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveOut = true; 140f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen while (LVI->end < Stop) { 141f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastStop = LVI->end; 142f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (++LVI == LVE || LVI->start >= Stop) { 143f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Kill = LastStop; 144f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveOut = false; 145f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 146f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 147f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LastStop < LVI->start) { 148f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen hasGap = true; 149f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Kill = LastStop; 150f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Def = LVI->start; 151f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 152f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 153f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 154f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Don't set LiveThrough when the block has a gap. 155f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut; 156f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveBlocks.push_back(BI); 157f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 158f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // LVI is now at LVE or LVI->end >= Stop. 159f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LVI == LVE) 160f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 161f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 162f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Live segment ends exactly at Stop. Move to the next segment. 163f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LVI->end == Stop && ++LVI == LVE) 164f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 165f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 166f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Pick the next basic block. 167f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LVI->start < Stop) 168f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen ++MFI; 169f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 170f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MFI = LIS.getMBBFromIndex(LVI->start); 171f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 172f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen} 173f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 17406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesenbool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 17506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen unsigned OrigReg = VRM.getOriginal(CurLI->reg); 17606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen const LiveInterval &Orig = LIS.getInterval(OrigReg); 17706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen assert(!Orig.empty() && "Splitting empty interval?"); 17806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen LiveInterval::const_iterator I = Orig.find(Idx); 17906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 18006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range containing Idx should begin at Idx. 18106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen if (I != Orig.end() && I->start <= Idx) 18206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I->start == Idx; 18306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 18406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range does not contain Idx, previous must end at Idx. 18506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I != Orig.begin() && (--I)->end == Idx; 18606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen} 18706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 188532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesenvoid SplitAnalysis::print(const BlockPtrSet &B, raw_ostream &OS) const { 189532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen for (BlockPtrSet::const_iterator I = B.begin(), E = B.end(); I != E; ++I) { 190078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen unsigned count = UsingBlocks.lookup(*I); 191532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen OS << " BB#" << (*I)->getNumber(); 192532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen if (count) 193532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen OS << '(' << count << ')'; 194532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen } 195532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen} 196532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen 1978ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::analyze(const LiveInterval *li) { 1988ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen clear(); 199078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = li; 200abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen analyzeUses(); 2018ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 2028ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 203697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen 204f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen// Split Editor 2061407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 2071407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2081c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 2091c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenSplitEditor::SplitEditor(SplitAnalysis &sa, 2101c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveIntervals &lis, 2111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VirtRegMap &vrm, 2121c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MachineDominatorTree &mdt, 2131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveRangeEdit &edit) 2141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen : SA(sa), LIS(lis), VRM(vrm), 2151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MRI(vrm.getMachineFunction().getRegInfo()), 2161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MDT(mdt), 2171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 2181c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 219a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit(&edit), 2201c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen OpenIdx(0), 2211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen RegAssign(Allocator) 2221c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen{ 2231c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // We don't need an AliasAnalysis since we will only be performing 2241c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // cheap-as-a-copy remats anyway. 225a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->anyRematerializable(LIS, TII, 0); 2261c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 2271c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2281c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::dump() const { 2291c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (RegAssign.empty()) { 2301c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " empty\n"; 2311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 2321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 2331c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2341c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 2351c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 2361c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << '\n'; 237b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen} 238b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen 2391c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::defValue(unsigned RegIdx, 2401c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const VNInfo *ParentVNI, 2411c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx) { 2421c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 2431c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 244a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 245a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 2461c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2471c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Create a new value. 2481c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 2491c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2501c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Preserve the PHIDef bit. 2511c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (ParentVNI->isPHIDef() && Idx == ParentVNI->def) 2521c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNI->setIsPHIDef(true); 2531c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2541c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Use insert for lookup, so we can add missing values with a second lookup. 2551c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen std::pair<ValueMap::iterator, bool> InsP = 2561c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 2571c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2581c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was the first time (RegIdx, ParentVNI) was mapped. 2591c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Keep it as a simple def without any liveness. 2601c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (InsP.second) 2611c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 2621c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2631c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // If the previous value was a simple mapping, add liveness for it now. 2641c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (VNInfo *OldVNI = InsP.first->second) { 2651c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = OldVNI->def; 2661c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 2671c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // No longer a simple mapping. 2681c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen InsP.first->second = 0; 2691c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 2701c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2711c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is a complex mapping, add liveness for VNI 2721c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 2731c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 2741c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 2769ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen} 2779ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 2781c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 2791c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 2801c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 2811c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2821c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // ParentVNI was either unmapped or already complex mapped. Either way. 2831c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (!VNI) 2841c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 2851c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2861c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was previously a single mapping. Make sure the old def is represented 2871c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by a trivial live range. 2881c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 289a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 2901c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNI = 0; 2911c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 2925fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 293d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen// extendRange - Extend the live range to reach Idx. 2941407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen// Potentially create phi-def values. 2951c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 2961407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 297078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 2981407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(IdxMBB && "No MBB at Idx"); 299a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 3001407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3011407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Is there a def in the same MBB we can extend? 302d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx)) 303d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen return; 3041407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3051407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Now for the fun part. We know that ParentVNI potentially has multiple defs, 3061407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // and we may need to create even more phi-defs to preserve VNInfo SSA form. 307e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Perform a search for all predecessor blocks where we know the dominating 308e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB. 309e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber() 310078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen << " at " << Idx << " in " << *LI << '\n'); 311e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 312078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Blocks where LI should be live-in. 313e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen SmallVector<MachineDomTreeNode*, 16> LiveIn; 314078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIn.push_back(MDT[IdxMBB]); 315e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 3168701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen // Remember if we have seen more than one value. 3178701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen bool UniqueVNI = true; 3188701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen VNInfo *IdxVNI = 0; 3198701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen 320078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 321e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = 0; i != LiveIn.size(); ++i) { 322e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 323e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 324e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 325e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *Pred = *PI; 326e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Is this a known live-out block? 327e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen std::pair<LiveOutMap::iterator,bool> LOIP = 328078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutCache.insert(std::make_pair(Pred, LiveOutPair())); 329e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Yes, we have been here before. 3308701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (!LOIP.second) { 3318701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (VNInfo *VNI = LOIP.first->second.first) { 3328701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (IdxVNI && IdxVNI != VNI) 3338701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; 3348701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen IdxVNI = VNI; 3358701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } 336e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 3378701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } 338e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Does Pred provide a live-out value? 3399763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen SlotIndex Start, Last; 3409763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred); 3419763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen Last = Last.getPrevSlot(); 3429763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen if (VNInfo *VNI = LI->extendInBlock(Start, Last)) { 343078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def); 344e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveOutPair &LOP = LOIP.first->second; 345e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LOP.first = VNI; 346078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LOP.second = MDT[DefMBB]; 3478701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (IdxVNI && IdxVNI != VNI) 3488701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; 3498701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen IdxVNI = VNI; 350e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 351e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 352e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // No, we need a live-in value for Pred as well 353e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (Pred != IdxMBB) 354078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIn.push_back(MDT[Pred]); 3558701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen else 3568701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; // Loopback to IdxMBB, ask updateSSA() for help. 3571407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 358e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 3591407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 360e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We may need to add phi-def values to preserve the SSA form. 3618701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (UniqueVNI) { 3628701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen LiveOutPair LOP(IdxVNI, MDT[LIS.getMBBFromIndex(IdxVNI->def)]); 3638701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen // Update LiveOutCache, but skip IdxMBB at LiveIn[0]. 3648701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen for (unsigned i = 1, e = LiveIn.size(); i != e; ++i) 3658701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen LiveOutCache[LiveIn[i]->getBlock()] = LOP; 3668701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } else 3678701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen IdxVNI = updateSSA(RegIdx, LiveIn, Idx, IdxMBB); 3681c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3691c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen#ifndef NDEBUG 3701c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Check the LiveOutCache invariants. 3711c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end(); 3721c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen I != E; ++I) { 3731c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(I->first && "Null MBB entry in cache"); 3741c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(I->second.first && "Null VNInfo in cache"); 3751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(I->second.second && "Null DomTreeNode in cache"); 3761c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (I->second.second->getBlock() == I->first) 3771c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen continue; 3781c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(), 3791c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen PE = I->first->pred_end(); PI != PE; ++PI) 3801c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant"); 3811c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3821c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen#endif 3831c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3841c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Since we went through the trouble of a full BFS visiting all reaching defs, 3851c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // the values in LiveIn are now accurate. No more phi-defs are needed 3861c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // for these blocks, so we can color the live ranges. 3871c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) { 3881c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 3891c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 3901c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *VNI = LiveOutCache.lookup(MBB).first; 3911c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3921c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Anything in LiveIn other than IdxMBB is live-through. 3931c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // In IdxMBB, we should stop at Idx unless the same value is live-out. 3941c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (MBB == IdxMBB && IdxVNI != VNI) 3951c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI)); 3961c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen else 3971c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 3981c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3991c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 4001c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::updateSSA(unsigned RegIdx, 4021c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SmallVectorImpl<MachineDomTreeNode*> &LiveIn, 4031c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx, 4041c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const MachineBasicBlock *IdxMBB) { 405e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is essentially the same iterative algorithm that SSAUpdater uses, 406e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // except we already have a dominator tree, so we don't have to recompute it. 407a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 408e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNInfo *IdxVNI = 0; 409e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen unsigned Changes; 410e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen do { 411e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen Changes = 0; 412e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n"); 4131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Propagate live-out values down the dominator tree, inserting phi-defs 4141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // when necessary. Since LiveIn was created by a BFS, going backwards makes 4151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // it more likely for us to visit immediate dominators before their 4161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // children. 417e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = LiveIn.size(); i; --i) { 418e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *Node = LiveIn[i-1]; 419e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = Node->getBlock(); 420e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *IDom = Node->getIDom(); 421e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveOutPair IDomValue; 422e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We need a live-in value to a block with no immediate dominator? 423e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is probably an unreachable block that has survived somehow. 424e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen bool needPHI = !IDom; 425e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 426e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Get the IDom live-out value. 427e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!needPHI) { 428078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock()); 429078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (I != LiveOutCache.end()) 430e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IDomValue = I->second; 431e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen else 432e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // If IDom is outside our set of live-out blocks, there must be new 433e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // defs, and we need a phi-def here. 434e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen needPHI = true; 435e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 436ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 437e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // IDom dominates all of our predecessors, but it may not be the immediate 438e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // dominator. Check if any of them have live-out values that are properly 439e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // dominated by IDom. If so, we need a phi-def here. 440e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!needPHI) { 441e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 442e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 443078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutPair Value = LiveOutCache[*PI]; 444e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!Value.first || Value.first == IDomValue.first) 445e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 446e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This predecessor is carrying something other than IDomValue. 447e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // It could be because IDomValue hasn't propagated yet, or it could be 448e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // because MBB is in the dominance frontier of that value. 449078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (MDT.dominates(IDom, Value.second)) { 450e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen needPHI = true; 451e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen break; 452e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 453e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 454e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 455ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 456e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Create a phi-def if required. 457e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (needPHI) { 458e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 459078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 460078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 461e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNI->setIsPHIDef(true); 462e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " - BB#" << MBB->getNumber() 463e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen << " phi-def #" << VNI->id << " at " << Start << '\n'); 464078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // We no longer need LI to be live-in. 465e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveIn.erase(LiveIn.begin()+(i-1)); 466e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Blocks in LiveIn are either IdxMBB, or have a value live-through. 467e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (MBB == IdxMBB) 468e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IdxVNI = VNI; 469e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Check if we need to update live-out info. 470078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutMap::iterator I = LiveOutCache.find(MBB); 471078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (I == LiveOutCache.end() || I->second.second == Node) { 472e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We already have a live-out defined in MBB, so this must be IdxMBB. 473e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(MBB == IdxMBB && "Adding phi-def to known live-out"); 474078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI)); 475e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else { 476e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This phi-def is also live-out, so color the whole block. 477078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 478e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen I->second = LiveOutPair(VNI, Node); 479e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 480e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else if (IDomValue.first) { 481c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // No phi-def here. Remember incoming value for IdxMBB. 482e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (MBB == IdxMBB) 483e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IdxVNI = IDomValue.first; 484c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // Propagate IDomValue if needed: 485c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // MBB is live-out and doesn't define its own value. 486078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutMap::iterator I = LiveOutCache.find(MBB); 487078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (I != LiveOutCache.end() && I->second.second != Node && 488c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen I->second.first != IDomValue.first) { 489e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 490e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen I->second = IDomValue; 491e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " - BB#" << MBB->getNumber() 492e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen << " idom valno #" << IDomValue.first->id 493e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen << " from BB#" << IDom->getBlock()->getNumber() << '\n'); 494e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 495ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen } 4961407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 497e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " - made " << Changes << " changes.\n"); 498e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } while (Changes); 4991407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 500e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(IdxVNI && "Didn't find value for Idx"); 5011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return IdxVNI; 502670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen} 503670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 5040f43811903f10394f7088f4634c0b4f9668cbac0Eric ChristopherVNInfo *SplitEditor::defFromParent(unsigned RegIdx, 505cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 506cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 507cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 508cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I) { 509cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineInstr *CopyMI = 0; 510cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex Def; 511a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 512cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 513cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Attempt cheap-as-a-copy rematerialization. 514cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 515a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 516a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI); 517cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } else { 518cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Can't remat, just insert a copy from parent. 5190f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 520a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen .addReg(Edit->getReg()); 521078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex(); 522cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } 523cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 524cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Define the value in Reg. 525670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 526cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNI->setCopy(CopyMI); 527cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen return VNI; 528cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen} 529cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 530f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen/// Create a new virtual register and live interval. 531f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesenvoid SplitEditor::openIntv() { 5320f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(!OpenIdx && "Previous LI not closed before openIntv"); 5337536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 5340f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the complement as index 0. 535a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->empty()) 536a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->create(MRI, LIS, VRM); 5370f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 5380f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the open interval. 539a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen OpenIdx = Edit->size(); 540a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->create(MRI, LIS, VRM); 541f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 542f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 543207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 5440f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvBefore"); 5459b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " enterIntvBefore " << Idx); 546207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 547a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 548f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5499b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 550207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx; 551f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 552207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 553078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 554f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen assert(MI && "enterIntvBefore called with invalid index"); 555cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 556207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 557207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 558f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 559f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 560207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 5610f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 562207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(&MBB); 563207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex Last = End.getPrevSlot(); 564207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 565a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 566f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5679b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 568207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return End; 569f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 5709b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id); 571207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 572a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 573207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen RegAssign.insert(VNI->def, End, OpenIdx); 5740f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 575207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 576f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 577f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 578078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// useIntv - indicate that all instructions in MBB should use OpenLI. 5797536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 580078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 581f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 582f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 5837536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 5840f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before useIntv"); 5850f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 5860f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, End, OpenIdx); 5870f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 588f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 589f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 590207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 5910f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 5929b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAfter " << Idx); 593f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 594f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen // The interval must be live beyond the instruction at Idx. 595cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 596a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 597f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5989b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 599207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx.getNextSlot(); 600f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 601207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 602f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 60301cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 60401cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen assert(MI && "No instruction at index"); 60501cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 60601cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 607207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 608f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 609f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 6109b057771ba22441b8d312404204433477b4be657Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 6119b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 6129b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvBefore " << Idx); 6139b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6149b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen // The interval must be live into the instruction at Idx. 6159b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 616a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 6179b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!ParentVNI) { 6189b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 6199b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return Idx.getNextSlot(); 6209b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 6219b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 6229b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6239b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 6249b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(MI && "No instruction at index"); 6259b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 6269b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return VNI->def; 6279b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen} 6289b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 629207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 6300f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 631078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(&MBB); 6329b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 6337536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 634a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 635f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6369b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 637207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Start; 6387536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen } 6397536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6400f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 641cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MBB.SkipPHIsAndLabels(MBB.begin())); 6420f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, VNI->def, OpenIdx); 6430f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 644207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 645f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 646f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6475c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesenvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 6485c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before overlapIntv"); 649a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 650a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 6515c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Parent changes value in extended range"); 6525c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 6535c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Range cannot span basic blocks"); 6545c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 655d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen // The complement interval will be extended as needed by extendRange(). 6564670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen markComplexMapped(0, ParentVNI); 6575c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 6585c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen RegAssign.insert(Start, End, OpenIdx); 6595c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dump()); 6605c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen} 6615c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 6627536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// closeIntv - Indicate that we are done editing the currently open 663f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// LiveInterval, and ranges can be trimmed. 6647536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::closeIntv() { 6650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before closeIntv"); 6660f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher OpenIdx = 0; 6675fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen} 6687536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6694670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen/// transferSimpleValues - Transfer all simply defined values to the new live 6704670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen/// ranges. 6714670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen/// Values that were rematerialized or that have multiple defs are left alone. 6724670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenbool SplitEditor::transferSimpleValues() { 6734670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Skipped = false; 6744670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegAssignMap::const_iterator AssignI = RegAssign.begin(); 675a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 676a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 6774670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " blit " << *ParentI << ':'); 6784670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen VNInfo *ParentVNI = ParentI->valno; 6794670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // RegAssign has holes where RegIdx 0 should be used. 6804670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex Start = ParentI->start; 6814670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen AssignI.advanceTo(Start); 6824670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen do { 6834670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen unsigned RegIdx; 6844670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex End = ParentI->end; 6854670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (!AssignI.valid()) { 6864670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 6874670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else if (AssignI.start() <= Start) { 6884670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = AssignI.value(); 6894670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (AssignI.stop() < End) { 6904670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = AssignI.stop(); 6914670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++AssignI; 6924670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 6934670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else { 6944670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 6954670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = std::min(End, AssignI.start()); 6964670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 6974670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 6984670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 6994670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id); 700a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->get(RegIdx)->addRange(LiveRange(Start, End, VNI)); 7014670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else 7024670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Skipped = true; 7034670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Start = End; 7044670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } while (Start != ParentI->end); 7054670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 7064670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 7074670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen return Skipped; 7084670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen} 7094670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 710e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesenvoid SplitEditor::extendPHIKillRanges() { 711e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // Extend live ranges to be live-out for successor PHI values. 712a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 713a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 714e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen const VNInfo *PHIVNI = *I; 715e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 716e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen continue; 717e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 718e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 719e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 720e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 721e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 722e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // The predecessor may not have a live-out value. That is OK, like an 723e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // undef PHI operand. 724a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->getParent().liveAt(End)) { 725e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen assert(RegAssign.lookup(End) == RegIdx && 726e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen "Different register assignment in phi predecessor"); 727e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen extendRange(RegIdx, End); 728e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 729e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 730e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 731e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen} 732e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 733a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 7344670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenvoid SplitEditor::rewriteAssigned(bool ExtendRanges) { 735a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 736078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 7377466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineOperand &MO = RI.getOperand(); 7387466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 7397466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen ++RI; 7400f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // LiveDebugVariables should have handled all DBG_VALUE instructions. 7417466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen if (MI->isDebugValue()) { 7427466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen DEBUG(dbgs() << "Zapping " << *MI); 7437466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MO.setReg(0); 7447466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen continue; 7457466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 746a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 747a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // <undef> operands don't really read the register, so just assign them to 748a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // the complement. 749a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen if (MO.isUse() && MO.isUndef()) { 750a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen MO.setReg(Edit->get(0)->reg); 751a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen continue; 752a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen } 753a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 754078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI); 7557466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 7560f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7570f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite to the mapped register at Idx. 7580f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned RegIdx = RegAssign.lookup(Idx); 759a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen MO.setReg(Edit->get(RegIdx)->reg); 7600f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 7610f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':' << RegIdx << '\t' << *MI); 7620f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Extend liveness to Idx. 7644670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (ExtendRanges) 7654670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen extendRange(RegIdx, Idx); 7667466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 7677466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen} 7687466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 7690f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher/// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping. 7700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs, 7710f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const ConnectedVNInfoEqClasses &ConEq) { 7720f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg), 7730f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RE = MRI.reg_end(); RI != RE;) { 7740f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineOperand &MO = RI.getOperand(); 7750f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineInstr *MI = MO.getParent(); 7760f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher ++RI; 7770f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher if (MO.isUse() && MO.isUndef()) 7789d999772df3a7fd96857bb9155e1e9ab5fee7a13Jakob Stoklund Olesen continue; 7790f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // DBG_VALUE instructions should have been eliminated earlier. 7800f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher SlotIndex Idx = LIS.getInstructionIndex(MI); 7810f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 7820f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 7830f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':'); 7840f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx); 7850f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(VNI && "Interval not live at use."); 7860f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg); 7870f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << VNI->id << '\t' << *MI); 7885fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 789463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher} 7905fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 7910f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::finish() { 7920f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx == 0 && "Previous LI not closed before rewrite"); 7934670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumFinished; 7940f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7950f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // At this point, the live intervals in Edit contain VNInfos corresponding to 7960f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // the inserted copies. 7970f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7980f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Add the original defs from the parent interval. 799a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 800a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 8010f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *ParentVNI = *I; 8029ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (ParentVNI->isUnused()) 8039ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen continue; 804670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 805670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen defValue(RegIdx, ParentVNI, ParentVNI->def); 8064670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Mark rematted values as complex everywhere to force liveness computation. 8074670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // The new live ranges may be truncated. 808a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 809a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 8104670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen markComplexMapped(i, ParentVNI); 8115fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 812c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 8130f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#ifndef NDEBUG 8140f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Every new interval must have a def by now, otherwise the split is bogus. 815a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 8160f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); 8170f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#endif 8180f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 8194670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Transfer the simply mapped values, check if any are complex. 8204670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Complex = transferSimpleValues(); 8214670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (Complex) 8224670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen extendPHIKillRanges(); 8234670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen else 8244670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumSimple; 8254670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 8264670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Rewrite virtual registers, possibly extending ranges. 8274670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen rewriteAssigned(Complex); 828463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher 8290f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // FIXME: Delete defs that were rematted everywhere. 8305fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 8310253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Get rid of unused values and set phi-kill flags. 832a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 833078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen (*I)->RenumberValues(LIS); 8340253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8353a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Now check if any registers were separated into multiple components. 836078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 837a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 8383a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Don't use iterators, they are invalidated by create() below. 839a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *li = Edit->get(i); 8403a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen unsigned NumComp = ConEQ.Classify(li); 8413a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen if (NumComp <= 1) 8423a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen continue; 8433a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 8443a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> dups; 8453a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen dups.push_back(li); 8463a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen for (unsigned i = 1; i != NumComp; ++i) 847a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen dups.push_back(&Edit->create(MRI, LIS, VRM)); 8480f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher rewriteComponents(dups, ConEQ); 8493a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen ConEQ.Distribute(&dups[0]); 8503a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen } 8513a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen 85208e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen // Calculate spill weight and allocation hints for new intervals. 8530eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops); 854a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 855a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen LiveInterval &li = **I; 8569db3ea46cb7bd6bdf108d314daffd0dfd50a73feJakob Stoklund Olesen vrai.CalculateRegClass(li.reg); 85708e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen vrai.CalculateWeightAndHint(li); 858078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName() 859e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen << ":" << li << '\n'); 86008e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen } 861f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 862f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 863f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 8648ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 865f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen// Single Block Splitting 866f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 867f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 868078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 869078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// may be an advantage to split CurLI for the duration of the block. 8702bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesenbool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 871078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // If CurLI is local to one block, there is no point to splitting it. 8729b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (LiveBlocks.size() <= 1) 8732bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return false; 8742bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen // Add blocks with multiple uses. 8759b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 8769b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen const BlockInfo &BI = LiveBlocks[i]; 8779b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!BI.Uses) 8782bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen continue; 8799b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen unsigned Instrs = UsingBlocks.lookup(BI.MBB); 8809b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (Instrs <= 1) 8819b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 8829b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough) 8839b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 8849b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Blocks.insert(BI.MBB); 8859b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 8862bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return !Blocks.empty(); 8872bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen} 8882bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen 889078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// splitSingleBlocks - Split CurLI into a separate live interval inside each 89057d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen/// basic block in Blocks. 89157d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 892e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 893f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 8940eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) { 8950eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i]; 8969b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!BI.Uses || !Blocks.count(BI.MBB)) 8979b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 898f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 899f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen openIntv(); 9009b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex SegStart = enterIntvBefore(BI.FirstUse); 901c70f687dce99ea48ca779e6767006f6663781132Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) { 9029b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 9039b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } else { 904c70f687dce99ea48ca779e6767006f6663781132Jakob Stoklund Olesen // The last use is after the last valid split point. 9059b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint); 9069b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen useIntv(SegStart, SegStop); 9079b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen overlapIntv(SegStop, BI.LastUse); 9089b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 909f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen closeIntv(); 910f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 9117466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen finish(); 912f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 913