SplitKit.cpp revision 7cec179a647bff132d7af36d91df877056880c5e
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()); 842b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 852b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // Compute per-live block info. 862b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen if (!calcLiveBlockInfo()) { 872b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // FIXME: calcLiveBlockInfo found inconsistencies in the live range. 882b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // I am looking at you, SimpleRegisterCoalescing! 892b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); 902b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen const_cast<LiveIntervals&>(LIS) 912b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen .shrinkToUses(const_cast<LiveInterval*>(CurLI)); 922b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen LiveBlocks.clear(); 932b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen bool fixed = calcLiveBlockInfo(); 942b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen (void)fixed; 952b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen assert(fixed && "Couldn't fix broken live interval"); 962b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen } 972b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 98e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen DEBUG(dbgs() << " counted " 99078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen << UsingInstrs.size() << " instrs, " 1004f5c9d206139f946ae4bb5ee7e3ddb1714057cdbJakob Stoklund Olesen << UsingBlocks.size() << " blocks.\n"); 1018ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 1028ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 103f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 104f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// where CurLI is live. 1052b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesenbool SplitAnalysis::calcLiveBlockInfo() { 106f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (CurLI->empty()) 1072b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 108f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 109f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVI = CurLI->begin(); 110f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVE = CurLI->end(); 111f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 112f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 113f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseI = UseSlots.begin(); 114f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseE = UseSlots.end(); 115f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 116f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Loop over basic blocks where CurLI is live. 117f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 118f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (;;) { 119f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BlockInfo BI; 120f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.MBB = MFI; 12136d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen tie(BI.Start, BI.Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 122f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 123f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // The last split point is the latest possible insertion point that dominates 124f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // all successor blocks. If interference reaches LastSplitPoint, it is not 125f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // possible to insert a split or reload that makes CurLI live in the 126f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // outgoing bundle. 127f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineBasicBlock::iterator LSP = LIS.getLastSplitPoint(*CurLI, BI.MBB); 128f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LSP == BI.MBB->end()) 12936d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen BI.LastSplitPoint = BI.Stop; 130f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 131f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LastSplitPoint = LIS.getInstructionIndex(LSP); 132f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 133f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // LVI is the first live segment overlapping MBB. 13436d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen BI.LiveIn = LVI->start <= BI.Start; 135f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (!BI.LiveIn) 136f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Def = LVI->start; 137f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 138f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Find the first and last uses in the block. 139f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Uses = hasUses(MFI); 140f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (BI.Uses && UseI != UseE) { 141f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.FirstUse = *UseI; 14236d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen assert(BI.FirstUse >= BI.Start); 143f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen do ++UseI; 14436d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen while (UseI != UseE && *UseI < BI.Stop); 145f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LastUse = UseI[-1]; 14636d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen assert(BI.LastUse < BI.Stop); 147f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 148f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 149f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Look for gaps in the live range. 150f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool hasGap = false; 151f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveOut = true; 15236d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen while (LVI->end < BI.Stop) { 153f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastStop = LVI->end; 15436d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen if (++LVI == LVE || LVI->start >= BI.Stop) { 155f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Kill = LastStop; 156f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveOut = false; 157f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 158f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 159f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LastStop < LVI->start) { 160f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen hasGap = true; 161f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Kill = LastStop; 162f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Def = LVI->start; 163f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 164f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 165f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 166f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Don't set LiveThrough when the block has a gap. 167f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut; 168f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveBlocks.push_back(BI); 169f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 1702b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // FIXME: This should never happen. The live range stops or starts without a 1712b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // corresponding use. An earlier pass did something wrong. 1722b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen if (!BI.LiveThrough && !BI.Uses) 1732b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return false; 1742b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 175f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // LVI is now at LVE or LVI->end >= Stop. 176f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LVI == LVE) 177f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 178f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 179f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Live segment ends exactly at Stop. Move to the next segment. 18036d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen if (LVI->end == BI.Stop && ++LVI == LVE) 181f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 182f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 183f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Pick the next basic block. 18436d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen if (LVI->start < BI.Stop) 185f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen ++MFI; 186f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 187f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MFI = LIS.getMBBFromIndex(LVI->start); 188f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 1892b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 190f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen} 191f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 19206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesenbool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 19306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen unsigned OrigReg = VRM.getOriginal(CurLI->reg); 19406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen const LiveInterval &Orig = LIS.getInterval(OrigReg); 19506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen assert(!Orig.empty() && "Splitting empty interval?"); 19606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen LiveInterval::const_iterator I = Orig.find(Idx); 19706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 19806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range containing Idx should begin at Idx. 19906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen if (I != Orig.end() && I->start <= Idx) 20006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I->start == Idx; 20106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 20206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range does not contain Idx, previous must end at Idx. 20306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I != Orig.begin() && (--I)->end == Idx; 20406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen} 20506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 206532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesenvoid SplitAnalysis::print(const BlockPtrSet &B, raw_ostream &OS) const { 207532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen for (BlockPtrSet::const_iterator I = B.begin(), E = B.end(); I != E; ++I) { 208078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen unsigned count = UsingBlocks.lookup(*I); 209532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen OS << " BB#" << (*I)->getNumber(); 210532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen if (count) 211532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen OS << '(' << count << ')'; 212532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen } 213532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen} 214532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen 2158ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::analyze(const LiveInterval *li) { 2168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen clear(); 217078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = li; 218abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen analyzeUses(); 2198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 2208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 221697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen 222f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2231c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen// Split Editor 2241407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 2251407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2261c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 2271c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenSplitEditor::SplitEditor(SplitAnalysis &sa, 2281c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveIntervals &lis, 2291c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VirtRegMap &vrm, 230bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen MachineDominatorTree &mdt) 2311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen : SA(sa), LIS(lis), VRM(vrm), 2321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MRI(vrm.getMachineFunction().getRegInfo()), 2331c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MDT(mdt), 2341c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 2351c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 236bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Edit(0), 2371c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen OpenIdx(0), 2381c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen RegAssign(Allocator) 239bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen{} 240bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 241bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesenvoid SplitEditor::reset(LiveRangeEdit &lre) { 242bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Edit = &lre; 243bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen OpenIdx = 0; 244bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen RegAssign.clear(); 245bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Values.clear(); 24613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 24713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // We don't need to clear LiveOutCache, only LiveOutSeen entries are read. 24813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutSeen.clear(); 249bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 2501c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // We don't need an AliasAnalysis since we will only be performing 2511c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // cheap-as-a-copy remats anyway. 252a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->anyRematerializable(LIS, TII, 0); 2531c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 2541c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2551c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::dump() const { 2561c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (RegAssign.empty()) { 2571c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " empty\n"; 2581c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 2591c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 2601c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2611c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 2621c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 2631c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << '\n'; 264b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen} 265b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen 2661c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::defValue(unsigned RegIdx, 2671c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const VNInfo *ParentVNI, 2681c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx) { 2691c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 2701c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 271a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 272a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 2731c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2741c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Create a new value. 2751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 2761c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2771c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Use insert for lookup, so we can add missing values with a second lookup. 2781c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen std::pair<ValueMap::iterator, bool> InsP = 2791c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 2801c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2811c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was the first time (RegIdx, ParentVNI) was mapped. 2821c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Keep it as a simple def without any liveness. 2831c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (InsP.second) 2841c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 2851c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2861c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // If the previous value was a simple mapping, add liveness for it now. 2871c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (VNInfo *OldVNI = InsP.first->second) { 2881c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = OldVNI->def; 2891c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 2901c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // No longer a simple mapping. 2911c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen InsP.first->second = 0; 2921c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 2931c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2941c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is a complex mapping, add liveness for VNI 2951c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 2961c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 2971c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2981c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 2999ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen} 3009ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 3011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 3021c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 3031c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 3041c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // ParentVNI was either unmapped or already complex mapped. Either way. 3061c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (!VNI) 3071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 3081c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3091c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was previously a single mapping. Make sure the old def is represented 3101c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by a trivial live range. 3111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 312a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 3131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNI = 0; 3141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 3155fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 316d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen// extendRange - Extend the live range to reach Idx. 3171407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen// Potentially create phi-def values. 3181c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 3191407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 320078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 3211407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(IdxMBB && "No MBB at Idx"); 322a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 3231407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3241407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Is there a def in the same MBB we can extend? 325d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx)) 326d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen return; 3271407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3281407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Now for the fun part. We know that ParentVNI potentially has multiple defs, 3291407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // and we may need to create even more phi-defs to preserve VNInfo SSA form. 330e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Perform a search for all predecessor blocks where we know the dominating 331e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB. 332e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 33313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // Initialize the live-out cache the first time it is needed. 33413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LiveOutSeen.empty()) { 33513ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen unsigned N = VRM.getMachineFunction().getNumBlockIDs(); 33613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutSeen.resize(N); 33713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutCache.resize(N); 33813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen } 33913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 340078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Blocks where LI should be live-in. 341e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen SmallVector<MachineDomTreeNode*, 16> LiveIn; 342078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIn.push_back(MDT[IdxMBB]); 343e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 3448701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen // Remember if we have seen more than one value. 3458701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen bool UniqueVNI = true; 3468701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen VNInfo *IdxVNI = 0; 3478701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen 348078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 349e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = 0; i != LiveIn.size(); ++i) { 350e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 3517cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen assert(!MBB->pred_empty() && "Value live-in to entry block?"); 352e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 353e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 354e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *Pred = *PI; 35513ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutPair &LOP = LiveOutCache[Pred]; 35613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 357e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Is this a known live-out block? 35813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LiveOutSeen.test(Pred->getNumber())) { 35913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (VNInfo *VNI = LOP.first) { 3608701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (IdxVNI && IdxVNI != VNI) 3618701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; 3628701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen IdxVNI = VNI; 3638701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } 364e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 3658701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } 36613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 36713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // First time. LOP is garbage and must be cleared below. 36813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutSeen.set(Pred->getNumber()); 36913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 370e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Does Pred provide a live-out value? 3719763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen SlotIndex Start, Last; 3729763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred); 3739763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen Last = Last.getPrevSlot(); 37413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(Start, Last); 37513ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP.first = VNI; 37613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (VNI) { 37713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP.second = MDT[LIS.getMBBFromIndex(VNI->def)]; 3788701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (IdxVNI && IdxVNI != VNI) 3798701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; 3808701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen IdxVNI = VNI; 381e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 382e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 38313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP.second = 0; 38413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 385e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // No, we need a live-in value for Pred as well 386e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (Pred != IdxMBB) 387078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIn.push_back(MDT[Pred]); 3888701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen else 3898701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; // Loopback to IdxMBB, ask updateSSA() for help. 3901407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 391e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 3921407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 393e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We may need to add phi-def values to preserve the SSA form. 3948701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (UniqueVNI) { 3958701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen LiveOutPair LOP(IdxVNI, MDT[LIS.getMBBFromIndex(IdxVNI->def)]); 3968701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen // Update LiveOutCache, but skip IdxMBB at LiveIn[0]. 3978701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen for (unsigned i = 1, e = LiveIn.size(); i != e; ++i) 3988701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen LiveOutCache[LiveIn[i]->getBlock()] = LOP; 3998701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } else 4008701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen IdxVNI = updateSSA(RegIdx, LiveIn, Idx, IdxMBB); 4011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4021c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Since we went through the trouble of a full BFS visiting all reaching defs, 4031c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // the values in LiveIn are now accurate. No more phi-defs are needed 4041c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // for these blocks, so we can color the live ranges. 4051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) { 4061c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 4071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 40813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen VNInfo *VNI = LiveOutCache[MBB].first; 4091c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4101c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Anything in LiveIn other than IdxMBB is live-through. 4111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // In IdxMBB, we should stop at Idx unless the same value is live-out. 4121c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (MBB == IdxMBB && IdxVNI != VNI) 4131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI)); 4141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen else 4151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 4161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 4171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 4181c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4191c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::updateSSA(unsigned RegIdx, 4201c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SmallVectorImpl<MachineDomTreeNode*> &LiveIn, 4211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx, 4221c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const MachineBasicBlock *IdxMBB) { 423e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is essentially the same iterative algorithm that SSAUpdater uses, 424e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // except we already have a dominator tree, so we don't have to recompute it. 425a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 426e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNInfo *IdxVNI = 0; 427e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen unsigned Changes; 428e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen do { 429e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen Changes = 0; 4301c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Propagate live-out values down the dominator tree, inserting phi-defs 4311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // when necessary. Since LiveIn was created by a BFS, going backwards makes 4321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // it more likely for us to visit immediate dominators before their 4331c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // children. 434e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = LiveIn.size(); i; --i) { 435e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *Node = LiveIn[i-1]; 436e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = Node->getBlock(); 437e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *IDom = Node->getIDom(); 438e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveOutPair IDomValue; 43913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 440e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We need a live-in value to a block with no immediate dominator? 441e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is probably an unreachable block that has survived somehow. 44213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen bool needPHI = !IDom || !LiveOutSeen.test(IDom->getBlock()->getNumber()); 443ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 444e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // IDom dominates all of our predecessors, but it may not be the immediate 445e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // dominator. Check if any of them have live-out values that are properly 446e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // dominated by IDom. If so, we need a phi-def here. 447e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!needPHI) { 44813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen IDomValue = LiveOutCache[IDom->getBlock()]; 449e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 450e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 451078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutPair Value = LiveOutCache[*PI]; 452e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!Value.first || Value.first == IDomValue.first) 453e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 454e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This predecessor is carrying something other than IDomValue. 455e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // It could be because IDomValue hasn't propagated yet, or it could be 456e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // because MBB is in the dominance frontier of that value. 457078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (MDT.dominates(IDom, Value.second)) { 458e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen needPHI = true; 459e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen break; 460e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 461e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 462e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 463ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 464e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Create a phi-def if required. 465e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (needPHI) { 466e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 467078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 468078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 469e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNI->setIsPHIDef(true); 470078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // We no longer need LI to be live-in. 471e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveIn.erase(LiveIn.begin()+(i-1)); 472e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Blocks in LiveIn are either IdxMBB, or have a value live-through. 473e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (MBB == IdxMBB) 474e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IdxVNI = VNI; 475e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Check if we need to update live-out info. 47613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutPair &LOP = LiveOutCache[MBB]; 47713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LOP.second == Node || !LiveOutSeen.test(MBB->getNumber())) { 478e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We already have a live-out defined in MBB, so this must be IdxMBB. 479e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(MBB == IdxMBB && "Adding phi-def to known live-out"); 480078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI)); 481e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else { 482e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This phi-def is also live-out, so color the whole block. 483078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 48413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP = LiveOutPair(VNI, Node); 485e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 486e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else if (IDomValue.first) { 487c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // No phi-def here. Remember incoming value for IdxMBB. 48813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (MBB == IdxMBB) { 489e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IdxVNI = IDomValue.first; 49013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // IdxMBB need not be live-out. 49113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (!LiveOutSeen.test(MBB->getNumber())) 49213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen continue; 49313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen } 49413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen assert(LiveOutSeen.test(MBB->getNumber()) && "Expected live-out block"); 495c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // Propagate IDomValue if needed: 496c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // MBB is live-out and doesn't define its own value. 49713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutPair &LOP = LiveOutCache[MBB]; 49813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LOP.second != Node && LOP.first != IDomValue.first) { 499e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 50013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP = IDomValue; 501e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 502ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen } 5031407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 504e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } while (Changes); 5051407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 506e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(IdxVNI && "Didn't find value for Idx"); 5071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return IdxVNI; 508670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen} 509670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 5100f43811903f10394f7088f4634c0b4f9668cbac0Eric ChristopherVNInfo *SplitEditor::defFromParent(unsigned RegIdx, 511cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 512cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 513cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 514cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I) { 515cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineInstr *CopyMI = 0; 516cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex Def; 517a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 518cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 519cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Attempt cheap-as-a-copy rematerialization. 520cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 521a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 522a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI); 523cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } else { 524cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Can't remat, just insert a copy from parent. 5250f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 526a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen .addReg(Edit->getReg()); 527078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex(); 528cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } 529cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 530cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Define the value in Reg. 531670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 532cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNI->setCopy(CopyMI); 533cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen return VNI; 534cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen} 535cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 536f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen/// Create a new virtual register and live interval. 537f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesenvoid SplitEditor::openIntv() { 5380f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(!OpenIdx && "Previous LI not closed before openIntv"); 5397536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 5400f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the complement as index 0. 541a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->empty()) 5426a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->create(LIS, VRM); 5430f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 5440f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the open interval. 545a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen OpenIdx = Edit->size(); 5466a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->create(LIS, VRM); 547f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 548f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 549207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 5500f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvBefore"); 5519b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " enterIntvBefore " << Idx); 552207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 553a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 554f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5559b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 556207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx; 557f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 558207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 559078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 560f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen assert(MI && "enterIntvBefore called with invalid index"); 561cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 562207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 563207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 564f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 565f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 566207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 5670f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 568207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(&MBB); 569207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex Last = End.getPrevSlot(); 570207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 571a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 572f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5739b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 574207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return End; 575f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 5769b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id); 577207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 578a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 579207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen RegAssign.insert(VNI->def, End, OpenIdx); 5800f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 581207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 582f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 583f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 584078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// useIntv - indicate that all instructions in MBB should use OpenLI. 5857536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 586078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 587f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 588f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 5897536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 5900f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before useIntv"); 5910f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 5920f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, End, OpenIdx); 5930f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 594f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 595f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 596207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 5970f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 5989b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAfter " << Idx); 599f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 600f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen // The interval must be live beyond the instruction at Idx. 601cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 602a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 603f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6049b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 605207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx.getNextSlot(); 606f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 607207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 608f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 60901cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 61001cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen assert(MI && "No instruction at index"); 61101cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 61201cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 613207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 614f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 615f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 6169b057771ba22441b8d312404204433477b4be657Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 6179b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 6189b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvBefore " << Idx); 6199b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6209b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen // The interval must be live into the instruction at Idx. 6219b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 622a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 6239b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!ParentVNI) { 6249b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 6259b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return Idx.getNextSlot(); 6269b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 6279b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 6289b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6299b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 6309b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(MI && "No instruction at index"); 6319b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 6329b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return VNI->def; 6339b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen} 6349b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 635207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 6360f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 637078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(&MBB); 6389b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 6397536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 640a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 641f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6429b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 643207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Start; 6447536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen } 6457536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6460f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 647cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MBB.SkipPHIsAndLabels(MBB.begin())); 6480f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, VNI->def, OpenIdx); 6490f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 650207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 651f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 652f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6535c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesenvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 6545c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before overlapIntv"); 655a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 656a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 6575c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Parent changes value in extended range"); 6585c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 6595c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Range cannot span basic blocks"); 6605c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 661d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen // The complement interval will be extended as needed by extendRange(). 6624670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen markComplexMapped(0, ParentVNI); 6635c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 6645c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen RegAssign.insert(Start, End, OpenIdx); 6655c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dump()); 6665c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen} 6675c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 6687536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// closeIntv - Indicate that we are done editing the currently open 669f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// LiveInterval, and ranges can be trimmed. 6707536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::closeIntv() { 6710f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before closeIntv"); 6720f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher OpenIdx = 0; 6735fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen} 6747536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6754670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen/// transferSimpleValues - Transfer all simply defined values to the new live 6764670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen/// ranges. 6774670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen/// Values that were rematerialized or that have multiple defs are left alone. 6784670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenbool SplitEditor::transferSimpleValues() { 6794670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Skipped = false; 6804670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegAssignMap::const_iterator AssignI = RegAssign.begin(); 681a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 682a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 6834670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " blit " << *ParentI << ':'); 6844670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen VNInfo *ParentVNI = ParentI->valno; 6854670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // RegAssign has holes where RegIdx 0 should be used. 6864670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex Start = ParentI->start; 6874670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen AssignI.advanceTo(Start); 6884670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen do { 6894670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen unsigned RegIdx; 6904670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex End = ParentI->end; 6914670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (!AssignI.valid()) { 6924670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 6934670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else if (AssignI.start() <= Start) { 6944670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = AssignI.value(); 6954670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (AssignI.stop() < End) { 6964670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = AssignI.stop(); 6974670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++AssignI; 6984670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 6994670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else { 7004670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 7014670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = std::min(End, AssignI.start()); 7024670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 7034670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 7044670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 7054670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id); 706a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->get(RegIdx)->addRange(LiveRange(Start, End, VNI)); 7074670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else 7084670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Skipped = true; 7094670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Start = End; 7104670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } while (Start != ParentI->end); 7114670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 7124670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 7134670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen return Skipped; 7144670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen} 7154670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 716e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesenvoid SplitEditor::extendPHIKillRanges() { 717e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // Extend live ranges to be live-out for successor PHI values. 718a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 719a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 720e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen const VNInfo *PHIVNI = *I; 721e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 722e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen continue; 723e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 724e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 725e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 726e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 727e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 728e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // The predecessor may not have a live-out value. That is OK, like an 729e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // undef PHI operand. 730a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->getParent().liveAt(End)) { 731e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen assert(RegAssign.lookup(End) == RegIdx && 732e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen "Different register assignment in phi predecessor"); 733e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen extendRange(RegIdx, End); 734e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 735e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 736e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 737e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen} 738e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 739a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 7404670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenvoid SplitEditor::rewriteAssigned(bool ExtendRanges) { 741a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 742078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 7437466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineOperand &MO = RI.getOperand(); 7447466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 7457466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen ++RI; 7460f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // LiveDebugVariables should have handled all DBG_VALUE instructions. 7477466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen if (MI->isDebugValue()) { 7487466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen DEBUG(dbgs() << "Zapping " << *MI); 7497466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MO.setReg(0); 7507466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen continue; 7517466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 752a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 753a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // <undef> operands don't really read the register, so just assign them to 754a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // the complement. 755a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen if (MO.isUse() && MO.isUndef()) { 756a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen MO.setReg(Edit->get(0)->reg); 757a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen continue; 758a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen } 759a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 760078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI); 7617cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (MO.isDef()) 7627cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex(); 7630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7640f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite to the mapped register at Idx. 7650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned RegIdx = RegAssign.lookup(Idx); 766a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen MO.setReg(Edit->get(RegIdx)->reg); 7670f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 7680f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':' << RegIdx << '\t' << *MI); 7690f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7707cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Extend liveness to Idx if the instruction reads reg. 7717cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!ExtendRanges) 7727cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 7737cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 7747cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Skip instructions that don't read Reg. 7757cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (MO.isDef()) { 7767cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!MO.getSubReg() && !MO.isEarlyClobber()) 7777cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 7787cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // We may wan't to extend a live range for a partial redef, or for a use 7797cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // tied to an early clobber. 7807cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getPrevSlot(); 7817cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!Edit->getParent().liveAt(Idx)) 7827cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 7837cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen } else 7847cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getUseIndex(); 7857cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 7867cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen extendRange(RegIdx, Idx); 7877466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 7887466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen} 7897466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 7905881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesenvoid SplitEditor::deleteRematVictims() { 7915881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen SmallVector<MachineInstr*, 8> Dead; 7925881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 7935881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 7945881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen const VNInfo *VNI = *I; 7955881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Was VNI rematted anywhere? 7965881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (VNI->isUnused() || VNI->isPHIDef() || !Edit->didRematerialize(VNI)) 7975881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen continue; 7985881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(VNI->def); 7995881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 8005881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen LiveInterval::const_iterator LII = LI->FindLiveRangeContaining(VNI->def); 8015881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen assert(LII != LI->end() && "Missing live range for rematted def"); 8025881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8035881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Is this a dead def? 8045881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (LII->end != VNI->def.getNextSlot()) 8055881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen continue; 8065881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8075881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 8085881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen assert(MI && "Missing instruction for dead def"); 8095881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen MI->addRegisterDead(LI->reg, &TRI); 8105881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8115881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (!MI->allDefsAreDead()) 8125881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen continue; 8135881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8145881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << *MI); 8155881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen Dead.push_back(MI); 8165881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen } 8175881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8185881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (Dead.empty()) 8195881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen return; 8205881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8216a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); 8225881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen} 8235881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8240f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::finish() { 8250f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx == 0 && "Previous LI not closed before rewrite"); 8264670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumFinished; 8270f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 8280f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // At this point, the live intervals in Edit contain VNInfos corresponding to 8290f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // the inserted copies. 8300f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 8310f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Add the original defs from the parent interval. 832a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 833a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 8340f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *ParentVNI = *I; 8359ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (ParentVNI->isUnused()) 8369ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen continue; 837670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 83829ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 83929ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNI->setIsPHIDef(ParentVNI->isPHIDef()); 84029ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNI->setCopy(ParentVNI->getCopy()); 84129ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen 8424670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Mark rematted values as complex everywhere to force liveness computation. 8434670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // The new live ranges may be truncated. 844a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 845a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 8464670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen markComplexMapped(i, ParentVNI); 8475fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 848c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 8490f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#ifndef NDEBUG 8500f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Every new interval must have a def by now, otherwise the split is bogus. 851a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 8520f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); 8530f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#endif 8540f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 8554670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Transfer the simply mapped values, check if any are complex. 8564670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Complex = transferSimpleValues(); 8574670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (Complex) 8584670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen extendPHIKillRanges(); 8594670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen else 8604670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumSimple; 8614670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 8624670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Rewrite virtual registers, possibly extending ranges. 8634670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen rewriteAssigned(Complex); 864463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher 8655881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Delete defs that were rematted everywhere. 8665881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (Complex) 8675881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen deleteRematVictims(); 8685fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 8690253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Get rid of unused values and set phi-kill flags. 870a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 871078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen (*I)->RenumberValues(LIS); 8720253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8733a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Now check if any registers were separated into multiple components. 874078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 875a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 8763a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Don't use iterators, they are invalidated by create() below. 877a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *li = Edit->get(i); 8783a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen unsigned NumComp = ConEQ.Classify(li); 8793a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen if (NumComp <= 1) 8803a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen continue; 8813a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 8823a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> dups; 8833a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen dups.push_back(li); 8843a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen for (unsigned i = 1; i != NumComp; ++i) 8856a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen dups.push_back(&Edit->create(LIS, VRM)); 8862254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen ConEQ.Distribute(&dups[0], MRI); 8873a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen } 8883a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen 88908e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen // Calculate spill weight and allocation hints for new intervals. 8900eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops); 891a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 892a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen LiveInterval &li = **I; 8939db3ea46cb7bd6bdf108d314daffd0dfd50a73feJakob Stoklund Olesen vrai.CalculateRegClass(li.reg); 89408e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen vrai.CalculateWeightAndHint(li); 895078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName() 896e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen << ":" << li << '\n'); 89708e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen } 898f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 899f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 900f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 9018ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 902f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen// Single Block Splitting 903f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 904f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 905078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 906078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// may be an advantage to split CurLI for the duration of the block. 9072bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesenbool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 908078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // If CurLI is local to one block, there is no point to splitting it. 9099b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (LiveBlocks.size() <= 1) 9102bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return false; 9112bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen // Add blocks with multiple uses. 9129b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 9139b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen const BlockInfo &BI = LiveBlocks[i]; 9149b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!BI.Uses) 9152bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen continue; 9169b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen unsigned Instrs = UsingBlocks.lookup(BI.MBB); 9179b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (Instrs <= 1) 9189b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 9199b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough) 9209b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 9219b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Blocks.insert(BI.MBB); 9229b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 9232bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return !Blocks.empty(); 9242bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen} 9252bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen 926078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// splitSingleBlocks - Split CurLI into a separate live interval inside each 92757d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen/// basic block in Blocks. 92857d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 929e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 930f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 9310eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) { 9320eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i]; 9339b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!BI.Uses || !Blocks.count(BI.MBB)) 9349b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 935f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 936f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen openIntv(); 9379b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex SegStart = enterIntvBefore(BI.FirstUse); 938c70f687dce99ea48ca779e6767006f6663781132Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) { 9399b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 9409b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } else { 941c70f687dce99ea48ca779e6767006f6663781132Jakob Stoklund Olesen // The last use is after the last valid split point. 9429b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint); 9439b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen useIntv(SegStart, SegStop); 9449b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen overlapIntv(SegStop, BI.LastUse); 9459b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 946f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen closeIntv(); 947f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 9487466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen finish(); 949f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 950