SplitKit.cpp revision 9763e2bf39b84f18bd464b0cda61fe1cd98dcaae
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//===----------------------------------------------------------------------===// 2011407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen// LiveIntervalMap 2021407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 2031407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 204b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen// Work around the fact that the std::pair constructors are broken for pointer 205b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen// pairs in some implementations. makeVV(x, 0) works. 206b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesenstatic inline std::pair<const VNInfo*, VNInfo*> 207b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund OlesenmakeVV(const VNInfo *a, VNInfo *b) { 208b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen return std::make_pair(a, b); 209b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen} 210b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen 2119ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesenvoid LiveIntervalMap::reset(LiveInterval *li) { 212078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI = li; 213078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutCache.clear(); 2149ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen} 2159ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 2165fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 2171407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen// mapValue - Find the mapped value for ParentVNI at Idx. 2181407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen// Potentially create phi-def values. 2195fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund OlesenVNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx, 2205fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen bool *simple) { 221078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen assert(LI && "call reset first"); 2221407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 2231407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 224078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen assert(ParentLI.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI"); 2251407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2261407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // This is a complex mapped value. There may be multiple defs, and we may need 2271407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // to create phi-defs. 2285fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen if (simple) *simple = false; 229078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 2301407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(IdxMBB && "No MBB at Idx"); 2311407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2321407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Is there a def in the same MBB we can extend? 2339763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen if (VNInfo *VNI = LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx)) 2341407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen return VNI; 2351407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2361407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Now for the fun part. We know that ParentVNI potentially has multiple defs, 2371407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // and we may need to create even more phi-defs to preserve VNInfo SSA form. 238e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Perform a search for all predecessor blocks where we know the dominating 239e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB. 240e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber() 241078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen << " at " << Idx << " in " << *LI << '\n'); 242e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 243078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Blocks where LI should be live-in. 244e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen SmallVector<MachineDomTreeNode*, 16> LiveIn; 245078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIn.push_back(MDT[IdxMBB]); 246e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 247078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 248e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = 0; i != LiveIn.size(); ++i) { 249e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 250e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 251e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 252e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *Pred = *PI; 253e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Is this a known live-out block? 254e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen std::pair<LiveOutMap::iterator,bool> LOIP = 255078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutCache.insert(std::make_pair(Pred, LiveOutPair())); 256e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Yes, we have been here before. 257e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!LOIP.second) { 2588a8e26fb1867b45ab7c5832dc3f509127d6624b8Benjamin Kramer DEBUG(if (VNInfo *VNI = LOIP.first->second.first) 2598a8e26fb1867b45ab7c5832dc3f509127d6624b8Benjamin Kramer dbgs() << " known valno #" << VNI->id 260e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen << " at BB#" << Pred->getNumber() << '\n'); 261e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 262e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 263e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 264e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Does Pred provide a live-out value? 2659763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen SlotIndex Start, Last; 2669763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred); 2679763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen Last = Last.getPrevSlot(); 2689763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen if (VNInfo *VNI = LI->extendInBlock(Start, Last)) { 269078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def); 270e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " found valno #" << VNI->id 271c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen << " from BB#" << DefMBB->getNumber() 272c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen << " at BB#" << Pred->getNumber() << '\n'); 273e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveOutPair &LOP = LOIP.first->second; 274e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LOP.first = VNI; 275078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LOP.second = MDT[DefMBB]; 276e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 277e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 278e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // No, we need a live-in value for Pred as well 279e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (Pred != IdxMBB) 280078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIn.push_back(MDT[Pred]); 2811407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 282e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 2831407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 284e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We may need to add phi-def values to preserve the SSA form. 285e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is essentially the same iterative algorithm that SSAUpdater uses, 286e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // except we already have a dominator tree, so we don't have to recompute it. 287e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNInfo *IdxVNI = 0; 288e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen unsigned Changes; 289e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen do { 290e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen Changes = 0; 291e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n"); 292e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Propagate live-out values down the dominator tree, inserting phi-defs when 293e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // necessary. Since LiveIn was created by a BFS, going backwards makes it more 294e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // likely for us to visit immediate dominators before their children. 295e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = LiveIn.size(); i; --i) { 296e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *Node = LiveIn[i-1]; 297e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = Node->getBlock(); 298e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *IDom = Node->getIDom(); 299e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveOutPair IDomValue; 300e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We need a live-in value to a block with no immediate dominator? 301e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is probably an unreachable block that has survived somehow. 302e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen bool needPHI = !IDom; 303e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 304e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Get the IDom live-out value. 305e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!needPHI) { 306078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock()); 307078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (I != LiveOutCache.end()) 308e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IDomValue = I->second; 309e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen else 310e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // If IDom is outside our set of live-out blocks, there must be new 311e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // defs, and we need a phi-def here. 312e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen needPHI = true; 313e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 314ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 315e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // IDom dominates all of our predecessors, but it may not be the immediate 316e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // dominator. Check if any of them have live-out values that are properly 317e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // dominated by IDom. If so, we need a phi-def here. 318e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!needPHI) { 319e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 320e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 321078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutPair Value = LiveOutCache[*PI]; 322e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!Value.first || Value.first == IDomValue.first) 323e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 324e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This predecessor is carrying something other than IDomValue. 325e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // It could be because IDomValue hasn't propagated yet, or it could be 326e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // because MBB is in the dominance frontier of that value. 327078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (MDT.dominates(IDom, Value.second)) { 328e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen needPHI = true; 329e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen break; 330e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 331e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 332e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 333ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 334e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Create a phi-def if required. 335e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (needPHI) { 336e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 337078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 338078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 339e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNI->setIsPHIDef(true); 340e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " - BB#" << MBB->getNumber() 341e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen << " phi-def #" << VNI->id << " at " << Start << '\n'); 342078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // We no longer need LI to be live-in. 343e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveIn.erase(LiveIn.begin()+(i-1)); 344e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Blocks in LiveIn are either IdxMBB, or have a value live-through. 345e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (MBB == IdxMBB) 346e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IdxVNI = VNI; 347e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Check if we need to update live-out info. 348078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutMap::iterator I = LiveOutCache.find(MBB); 349078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (I == LiveOutCache.end() || I->second.second == Node) { 350e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We already have a live-out defined in MBB, so this must be IdxMBB. 351e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(MBB == IdxMBB && "Adding phi-def to known live-out"); 352078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI)); 353e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else { 354e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This phi-def is also live-out, so color the whole block. 355078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 356e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen I->second = LiveOutPair(VNI, Node); 357e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 358e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else if (IDomValue.first) { 359c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // No phi-def here. Remember incoming value for IdxMBB. 360e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (MBB == IdxMBB) 361e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IdxVNI = IDomValue.first; 362c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // Propagate IDomValue if needed: 363c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // MBB is live-out and doesn't define its own value. 364078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutMap::iterator I = LiveOutCache.find(MBB); 365078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (I != LiveOutCache.end() && I->second.second != Node && 366c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen I->second.first != IDomValue.first) { 367e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 368e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen I->second = IDomValue; 369e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " - BB#" << MBB->getNumber() 370e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen << " idom valno #" << IDomValue.first->id 371e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen << " from BB#" << IDom->getBlock()->getNumber() << '\n'); 372e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 373ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen } 3741407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 375e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen DEBUG(dbgs() << " - made " << Changes << " changes.\n"); 376e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } while (Changes); 3771407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 378e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(IdxVNI && "Didn't find value for Idx"); 3791407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 380e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen#ifndef NDEBUG 381078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Check the LiveOutCache invariants. 382078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end(); 383e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen I != E; ++I) { 384e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(I->first && "Null MBB entry in cache"); 385e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(I->second.first && "Null VNInfo in cache"); 386e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(I->second.second && "Null DomTreeNode in cache"); 387e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (I->second.second->getBlock() == I->first) 388e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 389e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(), 390e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = I->first->pred_end(); PI != PE; ++PI) 391078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant"); 392e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 393e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen#endif 3941407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 395e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Since we went through the trouble of a full BFS visiting all reaching defs, 396e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // the values in LiveIn are now accurate. No more phi-defs are needed 397e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // for these blocks, so we can color the live ranges. 3981407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // This makes the next mapValue call much faster. 399e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) { 400e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 401078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 402078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *VNI = LiveOutCache.lookup(MBB).first; 40308eb8dd616bb4d4213f2ebda1de56b45bb88b6d9Jakob Stoklund Olesen 40408eb8dd616bb4d4213f2ebda1de56b45bb88b6d9Jakob Stoklund Olesen // Anything in LiveIn other than IdxMBB is live-through. 40508eb8dd616bb4d4213f2ebda1de56b45bb88b6d9Jakob Stoklund Olesen // In IdxMBB, we should stop at Idx unless the same value is live-out. 40608eb8dd616bb4d4213f2ebda1de56b45bb88b6d9Jakob Stoklund Olesen if (MBB == IdxMBB && IdxVNI != VNI) 40708eb8dd616bb4d4213f2ebda1de56b45bb88b6d9Jakob Stoklund Olesen LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI)); 40808eb8dd616bb4d4213f2ebda1de56b45bb88b6d9Jakob Stoklund Olesen else 40908eb8dd616bb4d4213f2ebda1de56b45bb88b6d9Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 4101407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 4111407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 4121407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen return IdxVNI; 4131407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen} 4141407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 415d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen#ifndef NDEBUG 416d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesenvoid LiveIntervalMap::dumpCache() { 417078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end(); 418d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen I != E; ++I) { 419d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen assert(I->first && "Null MBB entry in cache"); 420d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen assert(I->second.first && "Null VNInfo in cache"); 421d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen assert(I->second.second && "Null DomTreeNode in cache"); 422d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen dbgs() << " cache: BB#" << I->first->getNumber() 423d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen << " has valno #" << I->second.first->id << " from BB#" 424d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen << I->second.second->getBlock()->getNumber() << ", preds"; 425d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(), 426d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen PE = I->first->pred_end(); PI != PE; ++PI) 427d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen dbgs() << " BB#" << (*PI)->getNumber(); 428d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen dbgs() << '\n'; 429d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen } 430078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen dbgs() << " cache: " << LiveOutCache.size() << " entries.\n"; 431d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen} 432d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen#endif 433d7ca57705e7ccc19245b8b3d6fc271562366bf92Jakob Stoklund Olesen 434f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen 4351407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 436f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen// Split Editor 437f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 438f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 439f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 440d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund OlesenSplitEditor::SplitEditor(SplitAnalysis &sa, 441d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen LiveIntervals &lis, 442d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen VirtRegMap &vrm, 443d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen MachineDominatorTree &mdt, 444a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen LiveRangeEdit &edit) 4450eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen : SA(sa), LIS(lis), VRM(vrm), 446078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MRI(vrm.getMachineFunction().getRegInfo()), 4470f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MDT(mdt), 448078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 449078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 450078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Edit(edit), 4510f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher OpenIdx(0), 4520f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign(Allocator) 453f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen{ 454cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // We don't need an AliasAnalysis since we will only be performing 455cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // cheap-as-a-copy remats anyway. 456078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Edit.anyRematerializable(LIS, TII, 0); 457f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 458f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 4590f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::dump() const { 4600f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher if (RegAssign.empty()) { 4610f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher dbgs() << " empty\n"; 4620f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher return; 4630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher } 4640f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 4650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 4660f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 4670f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher dbgs() << '\n'; 4685fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen} 4695fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 470670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund OlesenVNInfo *SplitEditor::defValue(unsigned RegIdx, 471670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen const VNInfo *ParentVNI, 472670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen SlotIndex Idx) { 473670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 474670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 475670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 476670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen LiveInterval *LI = Edit.get(RegIdx); 477670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 478670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // Create a new value. 479670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 480670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 481670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // Preserve the PHIDef bit. 482670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen if (ParentVNI->isPHIDef() && Idx == ParentVNI->def) 483670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNI->setIsPHIDef(true); 484670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 485670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // Use insert for lookup, so we can add missing values with a second lookup. 486670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen std::pair<ValueMap::iterator, bool> InsP = 487670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 488670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 489670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // This was the first time (RegIdx, ParentVNI) was mapped. 490670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // Keep it as a simple def without any liveness. 491670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen if (InsP.second) 492670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen return VNI; 493670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 494670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // If the previous value was a simple mapping, add liveness for it now. 495670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen if (VNInfo *OldVNI = InsP.first->second) { 496670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen SlotIndex Def = OldVNI->def; 497670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 498670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // No longer a simple mapping. 499670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen InsP.first->second = 0; 500670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen } 501670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 502670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // This is a complex mapping, add liveness for VNI 503670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen SlotIndex Def = VNI->def; 504670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 505670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 506670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen return VNI; 507670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen} 508670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 509670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesenvoid SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 510670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 511670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 512670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 513670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // ParentVNI was either unmapped or already complex mapped. Either way. 514670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen if (!VNI) 515670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen return; 516670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 517670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // This was previously a single mapping. Make sure the old def is represented 518670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // by a trivial live range. 519670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen SlotIndex Def = VNI->def; 520670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 521670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNI = 0; 522670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen} 523670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 5240f43811903f10394f7088f4634c0b4f9668cbac0Eric ChristopherVNInfo *SplitEditor::defFromParent(unsigned RegIdx, 525cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 526cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 527cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 528cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I) { 529cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineInstr *CopyMI = 0; 530cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex Def; 5310f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher LiveInterval *LI = Edit.get(RegIdx); 532cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 533cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Attempt cheap-as-a-copy rematerialization. 534cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 535078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (Edit.canRematerializeAt(RM, UseIdx, true, LIS)) { 5360f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher Def = Edit.rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI); 537cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } else { 538cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Can't remat, just insert a copy from parent. 5390f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 5400f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher .addReg(Edit.getReg()); 541078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex(); 542cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } 543cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 544670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen // Temporarily mark all values as complex mapped. 545670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen markComplexMapped(RegIdx, ParentVNI); 546670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 547cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Define the value in Reg. 548670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 549cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNI->setCopy(CopyMI); 550cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen return VNI; 551cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen} 552cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 553f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen/// Create a new virtual register and live interval. 554f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesenvoid SplitEditor::openIntv() { 5550f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(!OpenIdx && "Previous LI not closed before openIntv"); 5567536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 5570f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the complement as index 0. 5580f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher if (Edit.empty()) { 5590f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher Edit.create(MRI, LIS, VRM); 5600f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent())); 5610f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher LIMappers.back().reset(Edit.get(0)); 5620f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher } 5630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 5640f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the open interval. 5650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher OpenIdx = Edit.size(); 5660f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher Edit.create(MRI, LIS, VRM); 5670f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent())); 5680f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher LIMappers[OpenIdx].reset(Edit.get(OpenIdx)); 569f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 570f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 571207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 5720f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvBefore"); 5739b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " enterIntvBefore " << Idx); 574207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 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; 579f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 580207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 581078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 582f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen assert(MI && "enterIntvBefore called with invalid index"); 583cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 584207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 585207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 586f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 587f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 588207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 5890f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 590207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(&MBB); 591207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex Last = End.getPrevSlot(); 592207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 593207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Last); 594f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5959b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 596207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return End; 597f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 5989b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id); 599207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 600cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen LIS.getLastSplitPoint(Edit.getParent(), &MBB)); 601207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen RegAssign.insert(VNI->def, End, OpenIdx); 6020f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 603207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 604f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 605f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 606078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// useIntv - indicate that all instructions in MBB should use OpenLI. 6077536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 608078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 609f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 610f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6117536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 6120f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before useIntv"); 6130f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 6140f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, End, OpenIdx); 6150f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 616f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 617f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 618207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 6190f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 6209b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAfter " << Idx); 621f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 622f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen // The interval must be live beyond the instruction at Idx. 623cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 624078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 625f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6269b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 627207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx.getNextSlot(); 628f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 629207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 630f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 63101cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 63201cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen assert(MI && "No instruction at index"); 63301cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 63401cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 635207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 636f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 637f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 6389b057771ba22441b8d312404204433477b4be657Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 6399b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 6409b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvBefore " << Idx); 6419b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6429b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen // The interval must be live into the instruction at Idx. 6439b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 6449b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 6459b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!ParentVNI) { 6469b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 6479b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return Idx.getNextSlot(); 6489b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 6499b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 6509b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6519b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 6529b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(MI && "No instruction at index"); 6539b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 6549b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return VNI->def; 6559b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen} 6569b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 657207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 6580f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 659078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(&MBB); 6609b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 6617536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 662078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Start); 663f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6649b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 665207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Start; 6667536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen } 6677536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6680f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 669cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MBB.SkipPHIsAndLabels(MBB.begin())); 6700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, VNI->def, OpenIdx); 6710f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 672207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 673f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 674f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6755c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesenvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 6765c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before overlapIntv"); 6775c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(Edit.getParent().getVNInfoAt(Start) == 6785c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen Edit.getParent().getVNInfoAt(End.getPrevSlot()) && 6795c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Parent changes value in extended range"); 6805c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*"); 6815c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 6825c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Range cannot span basic blocks"); 6835c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 6845c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // Treat this as useIntv() for now. The complement interval will be extended 6855c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen // as needed by mapValue(). 6865c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 6875c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen RegAssign.insert(Start, End, OpenIdx); 6885c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dump()); 6895c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen} 6905c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 6917536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// closeIntv - Indicate that we are done editing the currently open 692f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// LiveInterval, and ranges can be trimmed. 6937536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::closeIntv() { 6940f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before closeIntv"); 6950f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher OpenIdx = 0; 6965fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen} 6977536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6980f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher/// rewriteAssigned - Rewrite all uses of Edit.getReg(). 6990f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::rewriteAssigned() { 7000f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit.getReg()), 701078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 7027466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineOperand &MO = RI.getOperand(); 7037466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 7047466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen ++RI; 7050f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // LiveDebugVariables should have handled all DBG_VALUE instructions. 7067466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen if (MI->isDebugValue()) { 7077466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen DEBUG(dbgs() << "Zapping " << *MI); 7087466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MO.setReg(0); 7097466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen continue; 7107466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 711a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 712a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // <undef> operands don't really read the register, so just assign them to 713a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // the complement. 714a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen if (MO.isUse() && MO.isUndef()) { 715a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen MO.setReg(Edit.get(0)->reg); 716a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen continue; 717a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen } 718a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 719078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI); 7207466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 7210f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7220f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite to the mapped register at Idx. 7230f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned RegIdx = RegAssign.lookup(Idx); 7240f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MO.setReg(Edit.get(RegIdx)->reg); 7250f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 7260f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':' << RegIdx << '\t' << *MI); 7270f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7280f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Extend liveness to Idx. 7290f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); 7300f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher LIMappers[RegIdx].mapValue(ParentVNI, Idx); 7317466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 7327466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen} 7337466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 7340f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher/// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping. 7350f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs, 7360f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const ConnectedVNInfoEqClasses &ConEq) { 7370f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg), 7380f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RE = MRI.reg_end(); RI != RE;) { 7390f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineOperand &MO = RI.getOperand(); 7400f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineInstr *MI = MO.getParent(); 7410f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher ++RI; 7420f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher if (MO.isUse() && MO.isUndef()) 7439d999772df3a7fd96857bb9155e1e9ab5fee7a13Jakob Stoklund Olesen continue; 7440f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // DBG_VALUE instructions should have been eliminated earlier. 7450f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher SlotIndex Idx = LIS.getInstructionIndex(MI); 7460f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 7470f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 7480f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':'); 7490f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx); 7500f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(VNI && "Interval not live at use."); 7510f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg); 7520f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << VNI->id << '\t' << *MI); 7535fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 754463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher} 7555fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 7560f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::finish() { 7570f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx == 0 && "Previous LI not closed before rewrite"); 7580f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7590f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // At this point, the live intervals in Edit contain VNInfos corresponding to 7600f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // the inserted copies. 7610f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7620f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Add the original defs from the parent interval. 7630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(), 7640f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher E = Edit.getParent().vni_end(); I != E; ++I) { 7650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *ParentVNI = *I; 7669ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (ParentVNI->isUnused()) 7679ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen continue; 768670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 7690f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Mark all values as complex to force liveness computation. 7700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // This should really only be necessary for remat victims, but we are lazy. 771670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen markComplexMapped(RegIdx, ParentVNI); 772670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen defValue(RegIdx, ParentVNI, ParentVNI->def); 7735fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 774c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 7750f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#ifndef NDEBUG 7760f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Every new interval must have a def by now, otherwise the split is bogus. 7770f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I) 7780f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); 7790f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#endif 7800f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7810f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // FIXME: Don't recompute the liveness of all values, infer it from the 7820f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // overlaps between the parent live interval and RegAssign. 7830f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // The mapValue algorithm is only necessary when: 7840f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // - The parent value maps to multiple defs, and new phis are needed, or 7850f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // - The value has been rematerialized before some uses, and we want to 7860f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // minimize the live range so it only reaches the remaining uses. 7870f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // All other values have simple liveness that can be computed from RegAssign 7880f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // and the parent live interval. 7890f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7900f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Extend live ranges to be live-out for successor PHI values. 7910f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(), 7920f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher E = Edit.getParent().vni_end(); I != E; ++I) { 7930f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *PHIVNI = *I; 7949ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 7950f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher continue; 796c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 797c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen LiveIntervalMap &LIM = LIMappers[RegIdx]; 7980f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 799c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen DEBUG(dbgs() << " map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def 800c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen << " -> " << RegIdx << '\n'); 8010f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 8020f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher PE = MBB->pred_end(); PI != PE; ++PI) { 8030f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 804c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen DEBUG(dbgs() << " pred BB#" << (*PI)->getNumber() << '@' << End); 8050f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // The predecessor may not have a live-out value. That is OK, like an 8060f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // undef PHI operand. 807c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen if (VNInfo *VNI = Edit.getParent().getVNInfoAt(End)) { 808c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen DEBUG(dbgs() << " has parent valno #" << VNI->id << " live out\n"); 809c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen assert(RegAssign.lookup(End) == RegIdx && 810c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen "Different register assignment in phi predecessor"); 8110f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher LIM.mapValue(VNI, End); 812c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen } 813c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen else 814c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen DEBUG(dbgs() << " is not live-out\n"); 815463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher } 816c50f077b065a328a7ce21d97cfc0a21e5059f735Jakob Stoklund Olesen DEBUG(dbgs() << " " << *LIM.getLI() << '\n'); 817463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher } 8187466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 8190f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite instructions. 8200f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher rewriteAssigned(); 821463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher 8220f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // FIXME: Delete defs that were rematted everywhere. 8235fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 8240253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Get rid of unused values and set phi-kill flags. 825078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I) 826078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen (*I)->RenumberValues(LIS); 8270253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8283a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Now check if any registers were separated into multiple components. 829078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 830078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen for (unsigned i = 0, e = Edit.size(); i != e; ++i) { 8313a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Don't use iterators, they are invalidated by create() below. 832078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveInterval *li = Edit.get(i); 8333a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen unsigned NumComp = ConEQ.Classify(li); 8343a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen if (NumComp <= 1) 8353a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen continue; 8363a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 8373a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> dups; 8383a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen dups.push_back(li); 8393a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen for (unsigned i = 1; i != NumComp; ++i) 840078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen dups.push_back(&Edit.create(MRI, LIS, VRM)); 8410f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher rewriteComponents(dups, ConEQ); 8423a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen ConEQ.Distribute(&dups[0]); 8433a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen } 8443a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen 84508e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen // Calculate spill weight and allocation hints for new intervals. 8460eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops); 847078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I){ 848a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen LiveInterval &li = **I; 8499db3ea46cb7bd6bdf108d314daffd0dfd50a73feJakob Stoklund Olesen vrai.CalculateRegClass(li.reg); 85008e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen vrai.CalculateWeightAndHint(li); 851078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName() 852e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen << ":" << li << '\n'); 85308e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen } 854f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 855f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 856f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 8578ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 858f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen// Single Block Splitting 859f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 860f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 861078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 862078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// may be an advantage to split CurLI for the duration of the block. 8632bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesenbool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 864078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // If CurLI is local to one block, there is no point to splitting it. 8659b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (LiveBlocks.size() <= 1) 8662bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return false; 8672bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen // Add blocks with multiple uses. 8689b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 8699b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen const BlockInfo &BI = LiveBlocks[i]; 8709b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!BI.Uses) 8712bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen continue; 8729b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen unsigned Instrs = UsingBlocks.lookup(BI.MBB); 8739b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (Instrs <= 1) 8749b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 8759b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough) 8769b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 8779b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Blocks.insert(BI.MBB); 8789b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 8792bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return !Blocks.empty(); 8802bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen} 8812bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen 882078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// splitSingleBlocks - Split CurLI into a separate live interval inside each 88357d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen/// basic block in Blocks. 88457d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 885e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 886f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 8870eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) { 8880eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i]; 8899b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!BI.Uses || !Blocks.count(BI.MBB)) 8909b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 891f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 892f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen openIntv(); 8939b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex SegStart = enterIntvBefore(BI.FirstUse); 894c70f687dce99ea48ca779e6767006f6663781132Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) { 8959b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 8969b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } else { 897c70f687dce99ea48ca779e6767006f6663781132Jakob Stoklund Olesen // The last use is after the last valid split point. 8989b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint); 8999b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen useIntv(SegStart, SegStop); 9009b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen overlapIntv(SegStop, BI.LastUse); 9019b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 902f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen closeIntv(); 903f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 9047466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen finish(); 905f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 906