SplitKit.cpp revision e2dc0c978e2435dbbb55cb7fca7750034c3e292a
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" 1908e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen#include "llvm/CodeGen/CalcSpillWeights.h" 208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 21d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 22f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 246a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/Debug.h" 268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 276a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 286a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenusing namespace llvm; 318ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 326a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenstatic cl::opt<bool> 336a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund OlesenAllowSplit("spiller-splits-edges", 346a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen cl::desc("Allow critical edge splitting during spilling")); 358ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 368ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// Split Analysis 388ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 398ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 401b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund OlesenSplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 41f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const LiveIntervals &lis, 42f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli) 431b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen : MF(vrm.getMachineFunction()), 441b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen VRM(vrm), 45078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LIS(lis), 46078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Loops(mli), 471b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen TII(*MF.getTarget().getInstrInfo()), 48078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI(0) {} 498ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 508ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::clear() { 51b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen UseSlots.clear(); 52078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen UsingInstrs.clear(); 53078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen UsingBlocks.clear(); 54f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveBlocks.clear(); 55078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = 0; 568ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 578ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 586a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenbool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) { 596a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen MachineBasicBlock *T, *F; 606a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen SmallVector<MachineOperand, 4> Cond; 61078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen return !TII.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond); 626a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen} 636a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 64078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 65abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesenvoid SplitAnalysis::analyzeUses() { 66078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineRegisterInfo &MRI = MF.getRegInfo(); 67a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(CurLI->reg), 68a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen E = MRI.reg_end(); I != E; ++I) { 69a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen MachineOperand &MO = I.getOperand(); 70a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen if (MO.isUse() && MO.isUndef()) 71a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen continue; 72a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 73078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (MI->isDebugValue() || !UsingInstrs.insert(MI)) 748ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen continue; 75078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen UseSlots.push_back(LIS.getInstructionIndex(MI).getDefIndex()); 768ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen MachineBasicBlock *MBB = MI->getParent(); 774f5c9d206139f946ae4bb5ee7e3ddb1714057cdbJakob Stoklund Olesen UsingBlocks[MBB]++; 788ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen } 79b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen array_pod_sort(UseSlots.begin(), UseSlots.end()); 80f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen calcLiveBlockInfo(); 81e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen DEBUG(dbgs() << " counted " 82078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen << UsingInstrs.size() << " instrs, " 834f5c9d206139f946ae4bb5ee7e3ddb1714057cdbJakob Stoklund Olesen << UsingBlocks.size() << " blocks.\n"); 848ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 858ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 86f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 87f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// where CurLI is live. 88f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesenvoid SplitAnalysis::calcLiveBlockInfo() { 89f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (CurLI->empty()) 90f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen return; 91f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 92f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVI = CurLI->begin(); 93f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVE = CurLI->end(); 94f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 95f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 96f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseI = UseSlots.begin(); 97f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseE = UseSlots.end(); 98f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 99f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Loop over basic blocks where CurLI is live. 100f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 101f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (;;) { 102f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BlockInfo BI; 103f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.MBB = MFI; 104f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex Start, Stop; 105f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 106f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 107f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // The last split point is the latest possible insertion point that dominates 108f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // all successor blocks. If interference reaches LastSplitPoint, it is not 109f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // possible to insert a split or reload that makes CurLI live in the 110f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // outgoing bundle. 111f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineBasicBlock::iterator LSP = LIS.getLastSplitPoint(*CurLI, BI.MBB); 112f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LSP == BI.MBB->end()) 113f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LastSplitPoint = Stop; 114f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 115f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LastSplitPoint = LIS.getInstructionIndex(LSP); 116f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 117f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // LVI is the first live segment overlapping MBB. 118f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveIn = LVI->start <= Start; 119f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (!BI.LiveIn) 120f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Def = LVI->start; 121f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 122f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Find the first and last uses in the block. 123f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Uses = hasUses(MFI); 124f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (BI.Uses && UseI != UseE) { 125f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.FirstUse = *UseI; 126f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen assert(BI.FirstUse >= Start); 127f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen do ++UseI; 128f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen while (UseI != UseE && *UseI < Stop); 129f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LastUse = UseI[-1]; 130f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen assert(BI.LastUse < Stop); 131f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 132f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 133f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Look for gaps in the live range. 134f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool hasGap = false; 135f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveOut = true; 136f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen while (LVI->end < Stop) { 137f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastStop = LVI->end; 138f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (++LVI == LVE || LVI->start >= Stop) { 139f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Kill = LastStop; 140f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveOut = false; 141f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 142f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 143f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LastStop < LVI->start) { 144f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen hasGap = true; 145f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Kill = LastStop; 146f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Def = LVI->start; 147f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 148f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 149f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 150f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Don't set LiveThrough when the block has a gap. 151f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut; 152f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveBlocks.push_back(BI); 153f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 154f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // LVI is now at LVE or LVI->end >= Stop. 155f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LVI == LVE) 156f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 157f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 158f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Live segment ends exactly at Stop. Move to the next segment. 159f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LVI->end == Stop && ++LVI == LVE) 160f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 161f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 162f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Pick the next basic block. 163f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LVI->start < Stop) 164f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen ++MFI; 165f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 166f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MFI = LIS.getMBBFromIndex(LVI->start); 167f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 168f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen} 169f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 17006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesenbool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 17106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen unsigned OrigReg = VRM.getOriginal(CurLI->reg); 17206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen const LiveInterval &Orig = LIS.getInterval(OrigReg); 17306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen assert(!Orig.empty() && "Splitting empty interval?"); 17406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen LiveInterval::const_iterator I = Orig.find(Idx); 17506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 17606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range containing Idx should begin at Idx. 17706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen if (I != Orig.end() && I->start <= Idx) 17806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I->start == Idx; 17906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 18006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range does not contain Idx, previous must end at Idx. 18106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I != Orig.begin() && (--I)->end == Idx; 18206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen} 18306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 184532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesenvoid SplitAnalysis::print(const BlockPtrSet &B, raw_ostream &OS) const { 185532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen for (BlockPtrSet::const_iterator I = B.begin(), E = B.end(); I != E; ++I) { 186078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen unsigned count = UsingBlocks.lookup(*I); 187532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen OS << " BB#" << (*I)->getNumber(); 188532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen if (count) 189532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen OS << '(' << count << ')'; 190532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen } 191532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen} 192532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen 1938ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::analyze(const LiveInterval *li) { 1948ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen clear(); 195078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = li; 196abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen analyzeUses(); 1978ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 1988ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 199697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen 200f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen// Split Editor 2021407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 2031407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2041c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 2051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenSplitEditor::SplitEditor(SplitAnalysis &sa, 2061c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveIntervals &lis, 2071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VirtRegMap &vrm, 2081c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MachineDominatorTree &mdt, 2091c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveRangeEdit &edit) 2101c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen : SA(sa), LIS(lis), VRM(vrm), 2111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MRI(vrm.getMachineFunction().getRegInfo()), 2121c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MDT(mdt), 2131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 2141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 2151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen Edit(edit), 2161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen OpenIdx(0), 2171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen RegAssign(Allocator) 2181c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen{ 2191c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // We don't need an AliasAnalysis since we will only be performing 2201c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // cheap-as-a-copy remats anyway. 2211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen Edit.anyRematerializable(LIS, TII, 0); 2221c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 2231c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2241c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::dump() const { 2251c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (RegAssign.empty()) { 2261c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " empty\n"; 2271c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 2281c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 2291c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2301c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 2311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 2321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << '\n'; 233b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen} 234b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen 2351c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::defValue(unsigned RegIdx, 2361c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const VNInfo *ParentVNI, 2371c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx) { 2381c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 2391c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 2401c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 2411c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveInterval *LI = Edit.get(RegIdx); 2421c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2431c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Create a new value. 2441c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 2451c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2461c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Preserve the PHIDef bit. 2471c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (ParentVNI->isPHIDef() && Idx == ParentVNI->def) 2481c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNI->setIsPHIDef(true); 2491c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2501c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Use insert for lookup, so we can add missing values with a second lookup. 2511c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen std::pair<ValueMap::iterator, bool> InsP = 2521c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 2531c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2541c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was the first time (RegIdx, ParentVNI) was mapped. 2551c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Keep it as a simple def without any liveness. 2561c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (InsP.second) 2571c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 2581c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2591c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // If the previous value was a simple mapping, add liveness for it now. 2601c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (VNInfo *OldVNI = InsP.first->second) { 2611c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = OldVNI->def; 2621c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 2631c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // No longer a simple mapping. 2641c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen InsP.first->second = 0; 2651c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 2661c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2671c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is a complex mapping, add liveness for VNI 2681c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 2691c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 2701c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2711c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 2729ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen} 2739ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 2741c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 2751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 2761c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 2771c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2781c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // ParentVNI was either unmapped or already complex mapped. Either way. 2791c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (!VNI) 2801c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 2811c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2821c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was previously a single mapping. Make sure the old def is represented 2831c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by a trivial live range. 2841c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 2851c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 2861c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNI = 0; 2871c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 2885fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 289d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen// extendRange - Extend the live range to reach Idx. 2901407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen// Potentially create phi-def values. 2911c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 2921407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 293078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 2941407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(IdxMBB && "No MBB at Idx"); 2951c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveInterval *LI = Edit.get(RegIdx); 2961407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2971407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Is there a def in the same MBB we can extend? 298d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx)) 299d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen return; 3001407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3011407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Now for the fun part. We know that ParentVNI potentially has multiple defs, 3021407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // and we may need to create even more phi-defs to preserve VNInfo SSA form. 303e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Perform a search for all predecessor blocks where we know the dominating 304e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB. 305e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber() 306078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen << " at " << Idx << " in " << *LI << '\n'); 307e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 308078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Blocks where LI should be live-in. 309e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen SmallVector<MachineDomTreeNode*, 16> LiveIn; 310078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIn.push_back(MDT[IdxMBB]); 311e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 312078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 313e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = 0; i != LiveIn.size(); ++i) { 314e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 315e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 316e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 317e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *Pred = *PI; 318e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Is this a known live-out block? 319e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen std::pair<LiveOutMap::iterator,bool> LOIP = 320078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutCache.insert(std::make_pair(Pred, LiveOutPair())); 321e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Yes, we have been here before. 3221c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (!LOIP.second) 323e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 324e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 325e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Does Pred provide a live-out value? 3269763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen SlotIndex Start, Last; 3279763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred); 3289763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen Last = Last.getPrevSlot(); 3299763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen if (VNInfo *VNI = LI->extendInBlock(Start, Last)) { 330078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def); 331e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveOutPair &LOP = LOIP.first->second; 332e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LOP.first = VNI; 333078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LOP.second = MDT[DefMBB]; 334e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 335e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 336e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // No, we need a live-in value for Pred as well 337e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (Pred != IdxMBB) 338078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIn.push_back(MDT[Pred]); 3391407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 340e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 3411407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 342e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We may need to add phi-def values to preserve the SSA form. 3431c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *IdxVNI = updateSSA(RegIdx, LiveIn, Idx, IdxMBB); 3441c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3451c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen#ifndef NDEBUG 3461c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Check the LiveOutCache invariants. 3471c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end(); 3481c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen I != E; ++I) { 3491c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(I->first && "Null MBB entry in cache"); 3501c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(I->second.first && "Null VNInfo in cache"); 3511c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(I->second.second && "Null DomTreeNode in cache"); 3521c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (I->second.second->getBlock() == I->first) 3531c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen continue; 3541c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(), 3551c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen PE = I->first->pred_end(); PI != PE; ++PI) 3561c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant"); 3571c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3581c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen#endif 3591c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3601c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Since we went through the trouble of a full BFS visiting all reaching defs, 3611c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // the values in LiveIn are now accurate. No more phi-defs are needed 3621c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // for these blocks, so we can color the live ranges. 3631c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) { 3641c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 3651c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 3661c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *VNI = LiveOutCache.lookup(MBB).first; 3671c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3681c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Anything in LiveIn other than IdxMBB is live-through. 3691c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // In IdxMBB, we should stop at Idx unless the same value is live-out. 3701c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (MBB == IdxMBB && IdxVNI != VNI) 3711c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI)); 3721c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen else 3731c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 3741c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 3761c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3771c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::updateSSA(unsigned RegIdx, 3781c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SmallVectorImpl<MachineDomTreeNode*> &LiveIn, 3791c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx, 3801c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const MachineBasicBlock *IdxMBB) { 381e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is essentially the same iterative algorithm that SSAUpdater uses, 382e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // except we already have a dominator tree, so we don't have to recompute it. 3831c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveInterval *LI = Edit.get(RegIdx); 384e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNInfo *IdxVNI = 0; 385e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen unsigned Changes; 386e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen do { 387e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen Changes = 0; 388e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n"); 3891c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Propagate live-out values down the dominator tree, inserting phi-defs 3901c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // when necessary. Since LiveIn was created by a BFS, going backwards makes 3911c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // it more likely for us to visit immediate dominators before their 3921c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // children. 393e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = LiveIn.size(); i; --i) { 394e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *Node = LiveIn[i-1]; 395e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = Node->getBlock(); 396e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *IDom = Node->getIDom(); 397e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveOutPair IDomValue; 398e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We need a live-in value to a block with no immediate dominator? 399e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is probably an unreachable block that has survived somehow. 400e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen bool needPHI = !IDom; 401e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 402e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Get the IDom live-out value. 403e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!needPHI) { 404078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock()); 405078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (I != LiveOutCache.end()) 406e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IDomValue = I->second; 407e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen else 408e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // If IDom is outside our set of live-out blocks, there must be new 409e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // defs, and we need a phi-def here. 410e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen needPHI = true; 411e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 412ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 413e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // IDom dominates all of our predecessors, but it may not be the immediate 414e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // dominator. Check if any of them have live-out values that are properly 415e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // dominated by IDom. If so, we need a phi-def here. 416e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!needPHI) { 417e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 418e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 419078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutPair Value = LiveOutCache[*PI]; 420e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!Value.first || Value.first == IDomValue.first) 421e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 422e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This predecessor is carrying something other than IDomValue. 423e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // It could be because IDomValue hasn't propagated yet, or it could be 424e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // because MBB is in the dominance frontier of that value. 425078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (MDT.dominates(IDom, Value.second)) { 426e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen needPHI = true; 427e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen break; 428e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 429e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 430e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 431ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 432e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Create a phi-def if required. 433e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (needPHI) { 434e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 435078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 436078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 437e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNI->setIsPHIDef(true); 438e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " - BB#" << MBB->getNumber() 439e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen << " phi-def #" << VNI->id << " at " << Start << '\n'); 440078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // We no longer need LI to be live-in. 441e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveIn.erase(LiveIn.begin()+(i-1)); 442e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Blocks in LiveIn are either IdxMBB, or have a value live-through. 443e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (MBB == IdxMBB) 444e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IdxVNI = VNI; 445e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Check if we need to update live-out info. 446078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutMap::iterator I = LiveOutCache.find(MBB); 447078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (I == LiveOutCache.end() || I->second.second == Node) { 448e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We already have a live-out defined in MBB, so this must be IdxMBB. 449e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(MBB == IdxMBB && "Adding phi-def to known live-out"); 450078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI)); 451e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else { 452e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This phi-def is also live-out, so color the whole block. 453078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 454e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen I->second = LiveOutPair(VNI, Node); 455e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 456e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else if (IDomValue.first) { 457c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // No phi-def here. Remember incoming value for IdxMBB. 458e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (MBB == IdxMBB) 459e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IdxVNI = IDomValue.first; 460c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // Propagate IDomValue if needed: 461c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // MBB is live-out and doesn't define its own value. 462078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutMap::iterator I = LiveOutCache.find(MBB); 463078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (I != LiveOutCache.end() && I->second.second != Node && 464c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen I->second.first != IDomValue.first) { 465e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 466e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen I->second = IDomValue; 467e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " - BB#" << MBB->getNumber() 468e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen << " idom valno #" << IDomValue.first->id 469e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen << " from BB#" << IDom->getBlock()->getNumber() << '\n'); 470e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 471ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen } 4721407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 473e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " - made " << Changes << " changes.\n"); 474e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } while (Changes); 4751407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 476e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(IdxVNI && "Didn't find value for Idx"); 4771c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return IdxVNI; 478670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen} 479670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 4800f43811903f10394f7088f4634c0b4f9668cbac0Eric ChristopherVNInfo *SplitEditor::defFromParent(unsigned RegIdx, 481cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 482cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 483cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 484cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I) { 485cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineInstr *CopyMI = 0; 486cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex Def; 4870f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher LiveInterval *LI = Edit.get(RegIdx); 488cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 489cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Attempt cheap-as-a-copy rematerialization. 490cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 491078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (Edit.canRematerializeAt(RM, UseIdx, true, LIS)) { 4920f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher Def = Edit.rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI); 493cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } else { 494cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Can't remat, just insert a copy from parent. 4950f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 4960f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher .addReg(Edit.getReg()); 497078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex(); 498cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } 499cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 500670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // Temporarily mark all values as complex mapped. 501670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen markComplexMapped(RegIdx, ParentVNI); 502670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 503cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Define the value in Reg. 504670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 505cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNI->setCopy(CopyMI); 506cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen return VNI; 507cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen} 508cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 509f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen/// Create a new virtual register and live interval. 510f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesenvoid SplitEditor::openIntv() { 5110f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(!OpenIdx && "Previous LI not closed before openIntv"); 5127536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 5130f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the complement as index 0. 5141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (Edit.empty()) 5150f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher Edit.create(MRI, LIS, VRM); 5160f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 5170f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the open interval. 5180f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher OpenIdx = Edit.size(); 5190f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher Edit.create(MRI, LIS, VRM); 520f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 521f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 522207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 5230f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvBefore"); 5249b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " enterIntvBefore " << Idx); 525207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 526078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 527f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5289b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 529207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx; 530f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 531207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 532078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 533f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen assert(MI && "enterIntvBefore called with invalid index"); 534cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 535207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 536207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 537f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 538f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 539207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 5400f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 541207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(&MBB); 542207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex Last = End.getPrevSlot(); 543207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 544207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Last); 545f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5469b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 547207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return End; 548f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 5499b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id); 550207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 551cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen LIS.getLastSplitPoint(Edit.getParent(), &MBB)); 552207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen RegAssign.insert(VNI->def, End, OpenIdx); 5530f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 554207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 555f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 556f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 557078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// useIntv - indicate that all instructions in MBB should use OpenLI. 5587536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 559078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 560f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 561f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 5627536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 5630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before useIntv"); 5640f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 5650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, End, OpenIdx); 5660f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 567f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 568f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 569207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 5700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 5719b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAfter " << Idx); 572f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 573f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen // The interval must be live beyond the instruction at Idx. 574cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 575078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 576f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5779b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 578207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx.getNextSlot(); 579f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 580207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 581f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 58201cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 58301cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen assert(MI && "No instruction at index"); 58401cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 58501cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 586207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 587f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 588f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 5899b057771ba22441b8d312404204433477b4be657Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 5909b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 5919b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvBefore " << Idx); 5929b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 5939b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen // The interval must be live into the instruction at Idx. 5949b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 5959b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 5969b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!ParentVNI) { 5979b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 5989b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return Idx.getNextSlot(); 5999b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 6009b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 6019b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6029b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 6039b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(MI && "No instruction at index"); 6049b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 6059b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return VNI->def; 6069b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen} 6079b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 608207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 6090f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 610078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(&MBB); 6119b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 6127536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 613078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Start); 614f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6159b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 616207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Start; 6177536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen } 6187536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6190f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 620cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MBB.SkipPHIsAndLabels(MBB.begin())); 6210f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, VNI->def, OpenIdx); 6220f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 623207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 624f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 625f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6265c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesenvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 6275c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before overlapIntv"); 6285c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(Edit.getParent().getVNInfoAt(Start) == 6295c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen Edit.getParent().getVNInfoAt(End.getPrevSlot()) && 6305c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Parent changes value in extended range"); 6315c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*"); 6325c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 6335c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Range cannot span basic blocks"); 6345c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 635d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen // Treat this as useIntv() for now. 636d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen // The complement interval will be extended as needed by extendRange(). 6375c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 6385c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen RegAssign.insert(Start, End, OpenIdx); 6395c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dump()); 6405c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen} 6415c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 6427536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// closeIntv - Indicate that we are done editing the currently open 643f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// LiveInterval, and ranges can be trimmed. 6447536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::closeIntv() { 6450f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before closeIntv"); 6460f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher OpenIdx = 0; 6475fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen} 6487536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 649e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesenvoid SplitEditor::extendPHIKillRanges() { 650e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // Extend live ranges to be live-out for successor PHI values. 651e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(), 652e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen E = Edit.getParent().vni_end(); I != E; ++I) { 653e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen const VNInfo *PHIVNI = *I; 654e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 655e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen continue; 656e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 657e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 658e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 659e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 660e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 661e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // The predecessor may not have a live-out value. That is OK, like an 662e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // undef PHI operand. 663e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen if (Edit.getParent().liveAt(End)) { 664e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen assert(RegAssign.lookup(End) == RegIdx && 665e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen "Different register assignment in phi predecessor"); 666e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen extendRange(RegIdx, End); 667e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 668e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 669e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 670e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen} 671e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 6720f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher/// rewriteAssigned - Rewrite all uses of Edit.getReg(). 6730f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::rewriteAssigned() { 6740f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit.getReg()), 675078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 6767466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineOperand &MO = RI.getOperand(); 6777466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 6787466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen ++RI; 6790f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // LiveDebugVariables should have handled all DBG_VALUE instructions. 6807466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen if (MI->isDebugValue()) { 6817466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen DEBUG(dbgs() << "Zapping " << *MI); 6827466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MO.setReg(0); 6837466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen continue; 6847466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 685a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 686a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // <undef> operands don't really read the register, so just assign them to 687a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // the complement. 688a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen if (MO.isUse() && MO.isUndef()) { 689a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen MO.setReg(Edit.get(0)->reg); 690a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen continue; 691a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen } 692a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 693078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI); 6947466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 6950f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 6960f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite to the mapped register at Idx. 6970f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned RegIdx = RegAssign.lookup(Idx); 6980f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MO.setReg(Edit.get(RegIdx)->reg); 6990f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 7000f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':' << RegIdx << '\t' << *MI); 7010f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7020f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Extend liveness to Idx. 7031c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen extendRange(RegIdx, Idx); 7047466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 7057466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen} 7067466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 7070f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher/// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping. 7080f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs, 7090f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const ConnectedVNInfoEqClasses &ConEq) { 7100f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg), 7110f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RE = MRI.reg_end(); RI != RE;) { 7120f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineOperand &MO = RI.getOperand(); 7130f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineInstr *MI = MO.getParent(); 7140f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher ++RI; 7150f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher if (MO.isUse() && MO.isUndef()) 7169d999772df3a7fd96857bb9155e1e9ab5fee7a13Jakob Stoklund Olesen continue; 7170f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // DBG_VALUE instructions should have been eliminated earlier. 7180f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher SlotIndex Idx = LIS.getInstructionIndex(MI); 7190f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 7200f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 7210f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':'); 7220f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx); 7230f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(VNI && "Interval not live at use."); 7240f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg); 7250f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << VNI->id << '\t' << *MI); 7265fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 727463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher} 7285fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 7290f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::finish() { 7300f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx == 0 && "Previous LI not closed before rewrite"); 7310f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7320f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // At this point, the live intervals in Edit contain VNInfos corresponding to 7330f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // the inserted copies. 7340f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7350f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Add the original defs from the parent interval. 7360f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(), 7370f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher E = Edit.getParent().vni_end(); I != E; ++I) { 7380f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *ParentVNI = *I; 7399ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (ParentVNI->isUnused()) 7409ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen continue; 741670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 7420f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Mark all values as complex to force liveness computation. 7430f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // This should really only be necessary for remat victims, but we are lazy. 744670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen markComplexMapped(RegIdx, ParentVNI); 745670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen defValue(RegIdx, ParentVNI, ParentVNI->def); 7465fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 747c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 7480f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#ifndef NDEBUG 7490f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Every new interval must have a def by now, otherwise the split is bogus. 7500f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I) 7510f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); 7520f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#endif 7530f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7540f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // FIXME: Don't recompute the liveness of all values, infer it from the 7550f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // overlaps between the parent live interval and RegAssign. 756d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen // The extendRange algorithm is only necessary when: 7570f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // - The parent value maps to multiple defs, and new phis are needed, or 7580f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // - The value has been rematerialized before some uses, and we want to 7590f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // minimize the live range so it only reaches the remaining uses. 7600f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // All other values have simple liveness that can be computed from RegAssign 7610f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // and the parent live interval. 7620f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite instructions. 764e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen extendPHIKillRanges(); 7650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher rewriteAssigned(); 766463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher 7670f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // FIXME: Delete defs that were rematted everywhere. 7685fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 7690253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Get rid of unused values and set phi-kill flags. 770078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I) 771078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen (*I)->RenumberValues(LIS); 7720253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 7733a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Now check if any registers were separated into multiple components. 774078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 775078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen for (unsigned i = 0, e = Edit.size(); i != e; ++i) { 7763a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Don't use iterators, they are invalidated by create() below. 777078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveInterval *li = Edit.get(i); 7783a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen unsigned NumComp = ConEQ.Classify(li); 7793a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen if (NumComp <= 1) 7803a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen continue; 7813a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 7823a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> dups; 7833a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen dups.push_back(li); 7843a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen for (unsigned i = 1; i != NumComp; ++i) 785078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen dups.push_back(&Edit.create(MRI, LIS, VRM)); 7860f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher rewriteComponents(dups, ConEQ); 7873a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen ConEQ.Distribute(&dups[0]); 7883a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen } 7893a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen 79008e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen // Calculate spill weight and allocation hints for new intervals. 7910eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops); 792078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I){ 793a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen LiveInterval &li = **I; 7949db3ea46cb7bd6bdf108d314daffd0dfd50a73feJakob Stoklund Olesen vrai.CalculateRegClass(li.reg); 79508e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen vrai.CalculateWeightAndHint(li); 796078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName() 797e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen << ":" << li << '\n'); 79808e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen } 799f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 800f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 801f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 8028ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 803f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen// Single Block Splitting 804f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 805f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 806078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 807078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// may be an advantage to split CurLI for the duration of the block. 8082bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesenbool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 809078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // If CurLI is local to one block, there is no point to splitting it. 8109b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (LiveBlocks.size() <= 1) 8112bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return false; 8122bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen // Add blocks with multiple uses. 8139b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 8149b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen const BlockInfo &BI = LiveBlocks[i]; 8159b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!BI.Uses) 8162bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen continue; 8179b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen unsigned Instrs = UsingBlocks.lookup(BI.MBB); 8189b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (Instrs <= 1) 8199b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 8209b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough) 8219b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 8229b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Blocks.insert(BI.MBB); 8239b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 8242bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return !Blocks.empty(); 8252bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen} 8262bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen 827078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// splitSingleBlocks - Split CurLI into a separate live interval inside each 82857d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen/// basic block in Blocks. 82957d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 830e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 831f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 8320eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) { 8330eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i]; 8349b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!BI.Uses || !Blocks.count(BI.MBB)) 8359b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 836f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 837f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen openIntv(); 8389b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex SegStart = enterIntvBefore(BI.FirstUse); 839c70f687dce99ea48ca779e6767006f6663781132Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) { 8409b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 8419b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } else { 842c70f687dce99ea48ca779e6767006f6663781132Jakob Stoklund Olesen // The last use is after the last valid split point. 8439b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint); 8449b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen useIntv(SegStart, SegStop); 8459b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen overlapIntv(SegStop, BI.LastUse); 8469b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 847f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen closeIntv(); 848f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 8497466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen finish(); 850f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 851