SplitKit.cpp revision 71d9e65ee71712b965c79739e63de94fbb8078ad
18ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 28ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 38ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// The LLVM Compiler Infrastructure 48ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 58ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// License. See LICENSE.TXT for details. 78ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 88ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 98ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 108ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// This file contains the SplitAnalysis class as well as mutator functions for 118ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// live range splitting. 128ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 138ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 148ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 15376dcbd6c2c7adb8281f89d045b307eee7bd682aJakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "SplitKit.h" 17a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen#include "LiveRangeEdit.h" 18f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "VirtRegMap.h" 194670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 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" 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/Debug.h" 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 266a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 276a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 288ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenusing namespace llvm; 308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 314670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund OlesenSTATISTIC(NumFinished, "Number of splits finished"); 324670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund OlesenSTATISTIC(NumSimple, "Number of splits that were simple"); 334670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 348ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 358ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// Split Analysis 368ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 381b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund OlesenSplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 39f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const LiveIntervals &lis, 40f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli) 411b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen : MF(vrm.getMachineFunction()), 421b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen VRM(vrm), 43078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LIS(lis), 44078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Loops(mli), 451b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen TII(*MF.getTarget().getInstrInfo()), 461a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen CurLI(0), 471a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LastSplitPoint(MF.getNumBlockIDs()) {} 488ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 498ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::clear() { 50b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen UseSlots.clear(); 51f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveBlocks.clear(); 52078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = 0; 538ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 548ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 551a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund OlesenSlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { 561a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen const MachineBasicBlock *MBB = MF.getBlockNumbered(Num); 571a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor(); 581a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num]; 591a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 601a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // Compute split points on the first call. The pair is independent of the 611a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // current live interval. 621a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (!LSP.first.isValid()) { 631a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator(); 641a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (FirstTerm == MBB->end()) 651a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.first = LIS.getMBBEndIdx(MBB); 661a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen else 671a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.first = LIS.getInstructionIndex(FirstTerm); 681a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 691a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // If there is a landing pad successor, also find the call instruction. 701a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (!LPad) 711a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.first; 721a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // There may not be a call instruction (?) in which case we ignore LPad. 731a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.second = LSP.first; 741a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen for (MachineBasicBlock::const_iterator I = FirstTerm, E = MBB->begin(); 751a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen I != E; --I) 761a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (I->getDesc().isCall()) { 771a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.second = LIS.getInstructionIndex(I); 781a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen break; 791a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 801a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 811a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 821a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // If CurLI is live into a landing pad successor, move the last split point 831a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // back to the call that may throw. 8471d9e65ee71712b965c79739e63de94fbb8078adJakob Stoklund Olesen if (LPad && LSP.second.isValid() && LIS.isLiveInToMBB(*CurLI, LPad)) 851a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.second; 861a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen else 871a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.first; 886a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen} 896a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 90078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 91abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesenvoid SplitAnalysis::analyzeUses() { 92a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen assert(UseSlots.empty() && "Call clear first"); 93a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 94a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // First get all the defs from the interval values. This provides the correct 95a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // slots for early clobbers. 96a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(), 97a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen E = CurLI->vni_end(); I != E; ++I) 98a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen if (!(*I)->isPHIDef() && !(*I)->isUnused()) 99a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.push_back((*I)->def); 100a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 101a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // Get use slots form the use-def chain. 102078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineRegisterInfo &MRI = MF.getRegInfo(); 103a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen for (MachineRegisterInfo::use_nodbg_iterator 104a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E; 105a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen ++I) 106a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen if (!I.getOperand().isUndef()) 107a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.push_back(LIS.getInstructionIndex(&*I).getDefIndex()); 108a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 109b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen array_pod_sort(UseSlots.begin(), UseSlots.end()); 1102b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 111a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // Remove duplicates, keeping the smaller slot for each instruction. 112a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // That is what we want for early clobbers. 113a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), 114a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen SlotIndex::isSameInstr), 115a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.end()); 116a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 1172b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // Compute per-live block info. 1182b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen if (!calcLiveBlockInfo()) { 1192b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // FIXME: calcLiveBlockInfo found inconsistencies in the live range. 1202b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // I am looking at you, SimpleRegisterCoalescing! 1212b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); 1222b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen const_cast<LiveIntervals&>(LIS) 1232b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen .shrinkToUses(const_cast<LiveInterval*>(CurLI)); 1242b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen LiveBlocks.clear(); 1252b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen bool fixed = calcLiveBlockInfo(); 1262b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen (void)fixed; 1272b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen assert(fixed && "Couldn't fix broken live interval"); 1282b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen } 1292b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 130ef1f5ccca7efaa18209523b31019d356d302f635Jakob Stoklund Olesen DEBUG(dbgs() << "Analyze counted " 131a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen << UseSlots.size() << " instrs, " 132ef1f5ccca7efaa18209523b31019d356d302f635Jakob Stoklund Olesen << LiveBlocks.size() << " spanned.\n"); 1338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 1348ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 135f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 136f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// where CurLI is live. 1372b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesenbool SplitAnalysis::calcLiveBlockInfo() { 138f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (CurLI->empty()) 1392b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 140f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 141f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVI = CurLI->begin(); 142f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVE = CurLI->end(); 143f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 144f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 145f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseI = UseSlots.begin(); 146f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseE = UseSlots.end(); 147f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 148f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Loop over basic blocks where CurLI is live. 149f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 150f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (;;) { 151f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BlockInfo BI; 152f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.MBB = MFI; 1536c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex Start, Stop; 1546c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 155f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 156f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // LVI is the first live segment overlapping MBB. 1576c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen BI.LiveIn = LVI->start <= Start; 158f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (!BI.LiveIn) 159f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Def = LVI->start; 160f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 161f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Find the first and last uses in the block. 162a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen BI.Uses = UseI != UseE && *UseI < Stop; 163a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen if (BI.Uses) { 164f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.FirstUse = *UseI; 1656c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen assert(BI.FirstUse >= Start); 166f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen do ++UseI; 1676c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen while (UseI != UseE && *UseI < Stop); 168f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LastUse = UseI[-1]; 1696c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen assert(BI.LastUse < Stop); 170f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 171f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 172f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Look for gaps in the live range. 173f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool hasGap = false; 174f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveOut = true; 1756c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen while (LVI->end < Stop) { 176f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastStop = LVI->end; 1776c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (++LVI == LVE || LVI->start >= Stop) { 178f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Kill = LastStop; 179f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveOut = false; 180f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 181f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 182f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LastStop < LVI->start) { 183f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen hasGap = true; 184f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Kill = LastStop; 185f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Def = LVI->start; 186f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 187f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 188f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 189f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Don't set LiveThrough when the block has a gap. 190f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut; 191f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveBlocks.push_back(BI); 192f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 1932b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // FIXME: This should never happen. The live range stops or starts without a 1942b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // corresponding use. An earlier pass did something wrong. 1952b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen if (!BI.LiveThrough && !BI.Uses) 1962b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return false; 1972b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 198f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // LVI is now at LVE or LVI->end >= Stop. 199f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LVI == LVE) 200f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 201f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 202f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Live segment ends exactly at Stop. Move to the next segment. 2036c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (LVI->end == Stop && ++LVI == LVE) 204f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 205f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 206f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Pick the next basic block. 2076c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (LVI->start < Stop) 208f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen ++MFI; 209f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 210f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MFI = LIS.getMBBFromIndex(LVI->start); 211f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 2122b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 213f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen} 214f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 21506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesenbool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 21606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen unsigned OrigReg = VRM.getOriginal(CurLI->reg); 21706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen const LiveInterval &Orig = LIS.getInterval(OrigReg); 21806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen assert(!Orig.empty() && "Splitting empty interval?"); 21906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen LiveInterval::const_iterator I = Orig.find(Idx); 22006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 22106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range containing Idx should begin at Idx. 22206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen if (I != Orig.end() && I->start <= Idx) 22306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I->start == Idx; 22406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 22506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range does not contain Idx, previous must end at Idx. 22606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I != Orig.begin() && (--I)->end == Idx; 22706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen} 22806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 2298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::analyze(const LiveInterval *li) { 2308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen clear(); 231078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = li; 232abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen analyzeUses(); 2338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 2348ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 235697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen 236f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2371c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen// Split Editor 2381407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 2391407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2401c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 2411c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenSplitEditor::SplitEditor(SplitAnalysis &sa, 2421c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveIntervals &lis, 2431c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VirtRegMap &vrm, 244bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen MachineDominatorTree &mdt) 2451c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen : SA(sa), LIS(lis), VRM(vrm), 2461c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MRI(vrm.getMachineFunction().getRegInfo()), 2471c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MDT(mdt), 2481c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 2491c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 250bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Edit(0), 2511c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen OpenIdx(0), 2521c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen RegAssign(Allocator) 253bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen{} 254bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 255bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesenvoid SplitEditor::reset(LiveRangeEdit &lre) { 256bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Edit = &lre; 257bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen OpenIdx = 0; 258bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen RegAssign.clear(); 259bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Values.clear(); 26013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 26113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // We don't need to clear LiveOutCache, only LiveOutSeen entries are read. 26213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutSeen.clear(); 263bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 2641c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // We don't need an AliasAnalysis since we will only be performing 2651c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // cheap-as-a-copy remats anyway. 266a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->anyRematerializable(LIS, TII, 0); 2671c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 2681c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2691c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::dump() const { 2701c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (RegAssign.empty()) { 2711c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " empty\n"; 2721c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 2731c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 2741c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 2761c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 2771c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << '\n'; 278b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen} 279b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen 2801c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::defValue(unsigned RegIdx, 2811c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const VNInfo *ParentVNI, 2821c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx) { 2831c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 2841c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 285a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 286a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 2871c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2881c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Create a new value. 2891c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 2901c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2911c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Use insert for lookup, so we can add missing values with a second lookup. 2921c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen std::pair<ValueMap::iterator, bool> InsP = 2931c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 2941c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2951c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was the first time (RegIdx, ParentVNI) was mapped. 2961c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Keep it as a simple def without any liveness. 2971c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (InsP.second) 2981c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 2991c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3001c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // If the previous value was a simple mapping, add liveness for it now. 3011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (VNInfo *OldVNI = InsP.first->second) { 3021c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = OldVNI->def; 3031c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 3041c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // No longer a simple mapping. 3051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen InsP.first->second = 0; 3061c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3081c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is a complex mapping, add liveness for VNI 3091c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 3101c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 3111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3121c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 3139ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen} 3149ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 3151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 3161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 3171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 3181c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3191c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // ParentVNI was either unmapped or already complex mapped. Either way. 3201c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (!VNI) 3211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 3221c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3231c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was previously a single mapping. Make sure the old def is represented 3241c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by a trivial live range. 3251c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 326a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 3271c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNI = 0; 3281c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 3295fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 330d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen// extendRange - Extend the live range to reach Idx. 3311407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen// Potentially create phi-def values. 3321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 3331407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 334078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 3351407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(IdxMBB && "No MBB at Idx"); 336a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 3371407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3381407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Is there a def in the same MBB we can extend? 339d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx)) 340d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen return; 3411407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3421407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Now for the fun part. We know that ParentVNI potentially has multiple defs, 3431407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // and we may need to create even more phi-defs to preserve VNInfo SSA form. 344e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Perform a search for all predecessor blocks where we know the dominating 345e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB. 346e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 34713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // Initialize the live-out cache the first time it is needed. 34813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LiveOutSeen.empty()) { 34913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen unsigned N = VRM.getMachineFunction().getNumBlockIDs(); 35013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutSeen.resize(N); 35113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutCache.resize(N); 35213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen } 35313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 354078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Blocks where LI should be live-in. 355e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen SmallVector<MachineDomTreeNode*, 16> LiveIn; 356078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIn.push_back(MDT[IdxMBB]); 357e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 3588701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen // Remember if we have seen more than one value. 3598701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen bool UniqueVNI = true; 3608701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen VNInfo *IdxVNI = 0; 3618701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen 362078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 363e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = 0; i != LiveIn.size(); ++i) { 364e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 3657cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen assert(!MBB->pred_empty() && "Value live-in to entry block?"); 366e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 367e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 368e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *Pred = *PI; 36913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutPair &LOP = LiveOutCache[Pred]; 37013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 371e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Is this a known live-out block? 37213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LiveOutSeen.test(Pred->getNumber())) { 37313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (VNInfo *VNI = LOP.first) { 3748701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (IdxVNI && IdxVNI != VNI) 3758701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; 3768701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen IdxVNI = VNI; 3778701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } 378e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 3798701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } 38013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 38113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // First time. LOP is garbage and must be cleared below. 38213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutSeen.set(Pred->getNumber()); 38313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 384e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Does Pred provide a live-out value? 3859763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen SlotIndex Start, Last; 3869763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred); 3879763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen Last = Last.getPrevSlot(); 38813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(Start, Last); 38913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP.first = VNI; 39013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (VNI) { 39113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP.second = MDT[LIS.getMBBFromIndex(VNI->def)]; 3928701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (IdxVNI && IdxVNI != VNI) 3938701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; 3948701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen IdxVNI = VNI; 395e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 396e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 39713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP.second = 0; 39813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 399e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // No, we need a live-in value for Pred as well 400e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (Pred != IdxMBB) 401078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIn.push_back(MDT[Pred]); 4028701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen else 4038701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; // Loopback to IdxMBB, ask updateSSA() for help. 4041407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 405e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 4061407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 407e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We may need to add phi-def values to preserve the SSA form. 4088701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen if (UniqueVNI) { 4098701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen LiveOutPair LOP(IdxVNI, MDT[LIS.getMBBFromIndex(IdxVNI->def)]); 4108701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen // Update LiveOutCache, but skip IdxMBB at LiveIn[0]. 4118701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen for (unsigned i = 1, e = LiveIn.size(); i != e; ++i) 4128701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen LiveOutCache[LiveIn[i]->getBlock()] = LOP; 4138701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } else 4148701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen IdxVNI = updateSSA(RegIdx, LiveIn, Idx, IdxMBB); 4151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Since we went through the trouble of a full BFS visiting all reaching defs, 4171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // the values in LiveIn are now accurate. No more phi-defs are needed 4181c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // for these blocks, so we can color the live ranges. 4191c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) { 4201c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MachineBasicBlock *MBB = LiveIn[i]->getBlock(); 4211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 42213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen VNInfo *VNI = LiveOutCache[MBB].first; 4231c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4241c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Anything in LiveIn other than IdxMBB is live-through. 4251c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // In IdxMBB, we should stop at Idx unless the same value is live-out. 4261c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (MBB == IdxMBB && IdxVNI != VNI) 4271c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI)); 4281c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen else 4291c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 4301c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 4311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 4321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4331c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::updateSSA(unsigned RegIdx, 4341c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SmallVectorImpl<MachineDomTreeNode*> &LiveIn, 4351c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx, 4361c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const MachineBasicBlock *IdxMBB) { 437e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is essentially the same iterative algorithm that SSAUpdater uses, 438e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // except we already have a dominator tree, so we don't have to recompute it. 439a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 440e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNInfo *IdxVNI = 0; 441e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen unsigned Changes; 442e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen do { 443e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen Changes = 0; 4441c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Propagate live-out values down the dominator tree, inserting phi-defs 4451c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // when necessary. Since LiveIn was created by a BFS, going backwards makes 4461c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // it more likely for us to visit immediate dominators before their 4471c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // children. 448e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (unsigned i = LiveIn.size(); i; --i) { 449e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *Node = LiveIn[i-1]; 450e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = Node->getBlock(); 451e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *IDom = Node->getIDom(); 452e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveOutPair IDomValue; 45313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 454e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We need a live-in value to a block with no immediate dominator? 455e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is probably an unreachable block that has survived somehow. 45613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen bool needPHI = !IDom || !LiveOutSeen.test(IDom->getBlock()->getNumber()); 457ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 458e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // IDom dominates all of our predecessors, but it may not be the immediate 459e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // dominator. Check if any of them have live-out values that are properly 460e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // dominated by IDom. If so, we need a phi-def here. 461e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!needPHI) { 46213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen IDomValue = LiveOutCache[IDom->getBlock()]; 463e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 464e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 465078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutPair Value = LiveOutCache[*PI]; 466e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!Value.first || Value.first == IDomValue.first) 467e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 468e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This predecessor is carrying something other than IDomValue. 469e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // It could be because IDomValue hasn't propagated yet, or it could be 470e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // because MBB is in the dominance frontier of that value. 471078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (MDT.dominates(IDom, Value.second)) { 472e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen needPHI = true; 473e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen break; 474e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 475e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 476e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 477ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 478e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Create a phi-def if required. 479e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (needPHI) { 480e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 481078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 482078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 483e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNI->setIsPHIDef(true); 484078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // We no longer need LI to be live-in. 485e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveIn.erase(LiveIn.begin()+(i-1)); 486e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Blocks in LiveIn are either IdxMBB, or have a value live-through. 487e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (MBB == IdxMBB) 488e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IdxVNI = VNI; 489e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Check if we need to update live-out info. 49013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutPair &LOP = LiveOutCache[MBB]; 49113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LOP.second == Node || !LiveOutSeen.test(MBB->getNumber())) { 492e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We already have a live-out defined in MBB, so this must be IdxMBB. 493e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(MBB == IdxMBB && "Adding phi-def to known live-out"); 494078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI)); 495e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else { 496e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This phi-def is also live-out, so color the whole block. 497078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 49813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP = LiveOutPair(VNI, Node); 499e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 500e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else if (IDomValue.first) { 501c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // No phi-def here. Remember incoming value for IdxMBB. 50213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (MBB == IdxMBB) { 503e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen IdxVNI = IDomValue.first; 50413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // IdxMBB need not be live-out. 50513ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (!LiveOutSeen.test(MBB->getNumber())) 50613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen continue; 50713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen } 50813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen assert(LiveOutSeen.test(MBB->getNumber()) && "Expected live-out block"); 509c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // Propagate IDomValue if needed: 510c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // MBB is live-out and doesn't define its own value. 51113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutPair &LOP = LiveOutCache[MBB]; 51213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LOP.second != Node && LOP.first != IDomValue.first) { 513e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 51413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP = IDomValue; 515e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 516ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen } 5171407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 518e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } while (Changes); 5191407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 520e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen assert(IdxVNI && "Didn't find value for Idx"); 5211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return IdxVNI; 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; 531a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 532cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 533cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Attempt cheap-as-a-copy rematerialization. 534cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 535a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 536a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen 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) 540a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen .addReg(Edit->getReg()); 541078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex(); 542cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } 543cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 544cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Define the value in Reg. 545670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 546cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNI->setCopy(CopyMI); 547cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen return VNI; 548cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen} 549cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 550f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen/// Create a new virtual register and live interval. 551f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesenvoid SplitEditor::openIntv() { 5520f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(!OpenIdx && "Previous LI not closed before openIntv"); 5537536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 5540f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the complement as index 0. 555a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->empty()) 5566a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->create(LIS, VRM); 5570f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 5580f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the open interval. 559a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen OpenIdx = Edit->size(); 5606a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->create(LIS, VRM); 561f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 562f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 563207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 5640f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvBefore"); 5659b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " enterIntvBefore " << Idx); 566207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 567a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 568f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5699b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 570207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx; 571f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 572207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 573078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 574f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen assert(MI && "enterIntvBefore called with invalid index"); 575cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 576207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 577207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 578f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 579f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 580207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 5810f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 582207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(&MBB); 583207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex Last = End.getPrevSlot(); 584207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 585a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 586f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5879b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 588207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return End; 589f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 5909b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id); 591207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 592a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 593207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen RegAssign.insert(VNI->def, End, OpenIdx); 5940f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 595207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 596f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 597f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 598078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// useIntv - indicate that all instructions in MBB should use OpenLI. 5997536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 600078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 601f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 602f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6037536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 6040f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before useIntv"); 6050f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 6060f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, End, OpenIdx); 6070f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 608f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 609f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 610207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 6110f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 6129b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAfter " << Idx); 613f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 614f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen // The interval must be live beyond the instruction at Idx. 615cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 616a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 617f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6189b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 619207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx.getNextSlot(); 620f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 621207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 622f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 62301cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 62401cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen assert(MI && "No instruction at index"); 62501cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 62601cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 627207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 628f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 629f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 6309b057771ba22441b8d312404204433477b4be657Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 6319b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 6329b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvBefore " << Idx); 6339b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6349b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen // The interval must be live into the instruction at Idx. 6359b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 636a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 6379b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!ParentVNI) { 6389b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 6399b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return Idx.getNextSlot(); 6409b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 6419b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 6429b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6439b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 6449b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(MI && "No instruction at index"); 6459b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 6469b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return VNI->def; 6479b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen} 6489b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 649207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 6500f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 651078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(&MBB); 6529b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 6537536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 654a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 655f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6569b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 657207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Start; 6587536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen } 6597536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6600f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 661cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MBB.SkipPHIsAndLabels(MBB.begin())); 6620f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, VNI->def, OpenIdx); 6630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 664207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 665f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 666f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6675c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesenvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 6685c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before overlapIntv"); 669a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 670a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 6715c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Parent changes value in extended range"); 6725c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 6735c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Range cannot span basic blocks"); 6745c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 675d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen // The complement interval will be extended as needed by extendRange(). 676b3dd82670aa60cacba81f090d292722c3ef44354Jakob Stoklund Olesen if (ParentVNI) 677b3dd82670aa60cacba81f090d292722c3ef44354Jakob Stoklund Olesen markComplexMapped(0, ParentVNI); 6785c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 6795c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen RegAssign.insert(Start, End, OpenIdx); 6805c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dump()); 6815c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen} 6825c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 6837536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// closeIntv - Indicate that we are done editing the currently open 684f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// LiveInterval, and ranges can be trimmed. 6857536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::closeIntv() { 6860f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before closeIntv"); 6870f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher OpenIdx = 0; 6885fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen} 6897536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6904670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen/// transferSimpleValues - Transfer all simply defined values to the new live 6914670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen/// ranges. 6924670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen/// Values that were rematerialized or that have multiple defs are left alone. 6934670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenbool SplitEditor::transferSimpleValues() { 6944670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Skipped = false; 6954670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegAssignMap::const_iterator AssignI = RegAssign.begin(); 696a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 697a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 6984670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " blit " << *ParentI << ':'); 6994670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen VNInfo *ParentVNI = ParentI->valno; 7004670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // RegAssign has holes where RegIdx 0 should be used. 7014670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex Start = ParentI->start; 7024670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen AssignI.advanceTo(Start); 7034670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen do { 7044670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen unsigned RegIdx; 7054670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex End = ParentI->end; 7064670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (!AssignI.valid()) { 7074670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 7084670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else if (AssignI.start() <= Start) { 7094670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = AssignI.value(); 7104670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (AssignI.stop() < End) { 7114670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = AssignI.stop(); 7124670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++AssignI; 7134670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 7144670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else { 7154670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 7164670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = std::min(End, AssignI.start()); 7174670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 7184670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 7194670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 7204670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id); 721a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->get(RegIdx)->addRange(LiveRange(Start, End, VNI)); 7224670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else 7234670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Skipped = true; 7244670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Start = End; 7254670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } while (Start != ParentI->end); 7264670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 7274670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 7284670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen return Skipped; 7294670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen} 7304670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 731e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesenvoid SplitEditor::extendPHIKillRanges() { 732e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // Extend live ranges to be live-out for successor PHI values. 733a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 734a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 735e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen const VNInfo *PHIVNI = *I; 736e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 737e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen continue; 738e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 739e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 740e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 741e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 742e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 743e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // The predecessor may not have a live-out value. That is OK, like an 744e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // undef PHI operand. 745a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->getParent().liveAt(End)) { 746e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen assert(RegAssign.lookup(End) == RegIdx && 747e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen "Different register assignment in phi predecessor"); 748e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen extendRange(RegIdx, End); 749e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 750e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 751e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 752e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen} 753e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 754a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 7554670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenvoid SplitEditor::rewriteAssigned(bool ExtendRanges) { 756a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 757078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 7587466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineOperand &MO = RI.getOperand(); 7597466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 7607466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen ++RI; 7610f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // LiveDebugVariables should have handled all DBG_VALUE instructions. 7627466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen if (MI->isDebugValue()) { 7637466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen DEBUG(dbgs() << "Zapping " << *MI); 7647466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MO.setReg(0); 7657466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen continue; 7667466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 767a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 768a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // <undef> operands don't really read the register, so just assign them to 769a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // the complement. 770a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen if (MO.isUse() && MO.isUndef()) { 771a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen MO.setReg(Edit->get(0)->reg); 772a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen continue; 773a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen } 774a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 775078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI); 7767cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (MO.isDef()) 7777cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex(); 7780f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7790f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite to the mapped register at Idx. 7800f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned RegIdx = RegAssign.lookup(Idx); 781a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen MO.setReg(Edit->get(RegIdx)->reg); 7820f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 7830f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':' << RegIdx << '\t' << *MI); 7840f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7857cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Extend liveness to Idx if the instruction reads reg. 7867cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!ExtendRanges) 7877cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 7887cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 7897cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Skip instructions that don't read Reg. 7907cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (MO.isDef()) { 7917cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!MO.getSubReg() && !MO.isEarlyClobber()) 7927cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 7937cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // We may wan't to extend a live range for a partial redef, or for a use 7947cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // tied to an early clobber. 7957cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getPrevSlot(); 7967cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!Edit->getParent().liveAt(Idx)) 7977cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 7987cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen } else 7997cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getUseIndex(); 8007cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 8017cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen extendRange(RegIdx, Idx); 8027466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 8037466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen} 8047466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 8055881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesenvoid SplitEditor::deleteRematVictims() { 8065881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen SmallVector<MachineInstr*, 8> Dead; 8072dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 8082dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen LiveInterval *LI = *I; 8092dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 8102dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen LII != LIE; ++LII) { 8112dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen // Dead defs end at the store slot. 8122dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen if (LII->end != LII->valno->def.getNextSlot()) 8132dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 8142dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 8152dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen assert(MI && "Missing instruction for dead def"); 8162dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MI->addRegisterDead(LI->reg, &TRI); 8175881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8182dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen if (!MI->allDefsAreDead()) 8192dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 8205881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8212dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << *MI); 8222dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen Dead.push_back(MI); 8232dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen } 8245881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen } 8255881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8265881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (Dead.empty()) 8275881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen return; 8285881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8296a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); 8305881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen} 8315881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8320f43811903f10394f7088f4634c0b4f9668cbac0Eric Christophervoid SplitEditor::finish() { 8330f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx == 0 && "Previous LI not closed before rewrite"); 8344670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumFinished; 8350f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 8360f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // At this point, the live intervals in Edit contain VNInfos corresponding to 8370f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // the inserted copies. 8380f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 8390f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Add the original defs from the parent interval. 840a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 841a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 8420f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *ParentVNI = *I; 8439ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (ParentVNI->isUnused()) 8449ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen continue; 845670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 84629ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 84729ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNI->setIsPHIDef(ParentVNI->isPHIDef()); 84829ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNI->setCopy(ParentVNI->getCopy()); 84929ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen 8504670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Mark rematted values as complex everywhere to force liveness computation. 8514670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // The new live ranges may be truncated. 852a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 853a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 8544670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen markComplexMapped(i, ParentVNI); 8555fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 856c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 8570f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#ifndef NDEBUG 8580f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Every new interval must have a def by now, otherwise the split is bogus. 859a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 8600f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); 8610f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#endif 8620f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 8634670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Transfer the simply mapped values, check if any are complex. 8644670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Complex = transferSimpleValues(); 8654670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (Complex) 8664670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen extendPHIKillRanges(); 8674670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen else 8684670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumSimple; 8694670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 8704670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Rewrite virtual registers, possibly extending ranges. 8714670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen rewriteAssigned(Complex); 872463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher 8735881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Delete defs that were rematted everywhere. 8745881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (Complex) 8755881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen deleteRematVictims(); 8765fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 8770253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Get rid of unused values and set phi-kill flags. 878a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 879078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen (*I)->RenumberValues(LIS); 8800253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8813a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Now check if any registers were separated into multiple components. 882078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 883a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 8843a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Don't use iterators, they are invalidated by create() below. 885a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *li = Edit->get(i); 8863a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen unsigned NumComp = ConEQ.Classify(li); 8873a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen if (NumComp <= 1) 8883a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen continue; 8893a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 8903a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> dups; 8913a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen dups.push_back(li); 8923a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen for (unsigned i = 1; i != NumComp; ++i) 8936a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen dups.push_back(&Edit->create(LIS, VRM)); 8942254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen ConEQ.Distribute(&dups[0], MRI); 8953a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen } 8963a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen 89708e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen // Calculate spill weight and allocation hints for new intervals. 8986094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops); 899f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 900f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 901f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 9028ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 903f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen// Single Block Splitting 904f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 905f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 906078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 907078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// may be an advantage to split CurLI for the duration of the block. 9082bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesenbool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 909078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // If CurLI is local to one block, there is no point to splitting it. 9109b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (LiveBlocks.size() <= 1) 9112bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return false; 9122bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen // Add blocks with multiple uses. 9139b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 9149b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen const BlockInfo &BI = LiveBlocks[i]; 915a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen if (!BI.Uses || BI.FirstUse == BI.LastUse) 9169b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 9179b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Blocks.insert(BI.MBB); 9189b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 9192bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return !Blocks.empty(); 9202bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen} 9212bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen 922078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// splitSingleBlocks - Split CurLI into a separate live interval inside each 92357d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen/// basic block in Blocks. 92457d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 925e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 926f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 9270eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) { 9280eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i]; 9299b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!BI.Uses || !Blocks.count(BI.MBB)) 9309b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 931f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 932f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen openIntv(); 933612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 934c8ec765551119d5bdcfeebdaeb869242c098bdc5Jakob Stoklund Olesen SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstUse, 935612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen LastSplitPoint)); 936612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastUse < LastSplitPoint) { 9379b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 9389b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } else { 939c70f687dce99ea48ca779e6767006f6663781132Jakob Stoklund Olesen // The last use is after the last valid split point. 940612f7807c581eafb7c8105e1a55c8d839033bfb3Jakob Stoklund Olesen SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 9419b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen useIntv(SegStart, SegStop); 9429b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen overlapIntv(SegStop, BI.LastUse); 9439b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 944f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen closeIntv(); 945f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 9467466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen finish(); 947f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 948