SplitKit.cpp revision c1c622ef0dd29d1bafd580790aec5231af50abf2
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"); 33e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumCopies, "Number of copies inserted for splitting"); 34e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumRemats, "Number of rematerialized defs for splitting"); 35bdda37d7fbafe6876f248341837423a4100f95a5Jakob Stoklund OlesenSTATISTIC(NumRepairs, "Number of invalid live ranges repaired"); 364670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 388ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// Split Analysis 398ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 408ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 411b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund OlesenSplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 42f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const LiveIntervals &lis, 43f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli) 441b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen : MF(vrm.getMachineFunction()), 451b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen VRM(vrm), 46078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LIS(lis), 47078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Loops(mli), 481b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen TII(*MF.getTarget().getInstrInfo()), 491a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen CurLI(0), 501a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LastSplitPoint(MF.getNumBlockIDs()) {} 518ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 528ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::clear() { 53b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen UseSlots.clear(); 54db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.clear(); 55db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ThroughBlocks.clear(); 56078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = 0; 577d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen DidRepairRange = false; 588ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 598ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 601a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund OlesenSlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { 611a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen const MachineBasicBlock *MBB = MF.getBlockNumbered(Num); 621a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor(); 631a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num]; 641a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 651a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // Compute split points on the first call. The pair is independent of the 661a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // current live interval. 671a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (!LSP.first.isValid()) { 681a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator(); 691a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (FirstTerm == MBB->end()) 701a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.first = LIS.getMBBEndIdx(MBB); 711a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen else 721a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.first = LIS.getInstructionIndex(FirstTerm); 731a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 741a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // If there is a landing pad successor, also find the call instruction. 751a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (!LPad) 761a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.first; 771a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // There may not be a call instruction (?) in which case we ignore LPad. 781a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.second = LSP.first; 791e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin(); 801e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen I != E;) { 811e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen --I; 821a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (I->getDesc().isCall()) { 831a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.second = LIS.getInstructionIndex(I); 841a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen break; 851a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 861e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen } 871a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 881a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 891a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // If CurLI is live into a landing pad successor, move the last split point 901a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // back to the call that may throw. 9171d9e65ee71712b965c79739e63de94fbb8078adJakob Stoklund Olesen if (LPad && LSP.second.isValid() && LIS.isLiveInToMBB(*CurLI, LPad)) 921a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.second; 931a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen else 941a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.first; 956a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen} 966a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 97078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 98abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesenvoid SplitAnalysis::analyzeUses() { 99a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen assert(UseSlots.empty() && "Call clear first"); 100a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 101a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // First get all the defs from the interval values. This provides the correct 102a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // slots for early clobbers. 103a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(), 104a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen E = CurLI->vni_end(); I != E; ++I) 105a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen if (!(*I)->isPHIDef() && !(*I)->isUnused()) 106a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.push_back((*I)->def); 107a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 108a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // Get use slots form the use-def chain. 109078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineRegisterInfo &MRI = MF.getRegInfo(); 110a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen for (MachineRegisterInfo::use_nodbg_iterator 111a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E; 112a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen ++I) 113a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen if (!I.getOperand().isUndef()) 114a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.push_back(LIS.getInstructionIndex(&*I).getDefIndex()); 115a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 116b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen array_pod_sort(UseSlots.begin(), UseSlots.end()); 1172b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 118a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // Remove duplicates, keeping the smaller slot for each instruction. 119a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // That is what we want for early clobbers. 120a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), 121a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen SlotIndex::isSameInstr), 122a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.end()); 123a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 1242b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // Compute per-live block info. 1252b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen if (!calcLiveBlockInfo()) { 1262b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // FIXME: calcLiveBlockInfo found inconsistencies in the live range. 1275b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola // I am looking at you, RegisterCoalescer! 1287d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen DidRepairRange = true; 129bdda37d7fbafe6876f248341837423a4100f95a5Jakob Stoklund Olesen ++NumRepairs; 1302b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); 1312b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen const_cast<LiveIntervals&>(LIS) 1322b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen .shrinkToUses(const_cast<LiveInterval*>(CurLI)); 133db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.clear(); 134db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ThroughBlocks.clear(); 1352b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen bool fixed = calcLiveBlockInfo(); 1362b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen (void)fixed; 1372b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen assert(fixed && "Couldn't fix broken live interval"); 1382b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen } 1392b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 140ef1f5ccca7efaa18209523b31019d356d302f635Jakob Stoklund Olesen DEBUG(dbgs() << "Analyze counted " 141db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen << UseSlots.size() << " instrs in " 142db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen << UseBlocks.size() << " blocks, through " 143f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen << NumThroughBlocks << " blocks.\n"); 1448ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 1458ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 146f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 147f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// where CurLI is live. 1482b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesenbool SplitAnalysis::calcLiveBlockInfo() { 149f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ThroughBlocks.resize(MF.getNumBlockIDs()); 150a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen NumThroughBlocks = NumGapBlocks = 0; 151f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (CurLI->empty()) 1522b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 153f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 154f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVI = CurLI->begin(); 155f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVE = CurLI->end(); 156f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 157f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 158f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseI = UseSlots.begin(); 159f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseE = UseSlots.end(); 160f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 161f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Loop over basic blocks where CurLI is live. 162f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 163f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (;;) { 164f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BlockInfo BI; 165f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.MBB = MFI; 1666c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex Start, Stop; 1676c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 168f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 169a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // If the block contains no uses, the range must be live through. At one 1705b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola // point, RegisterCoalescer could create dangling ranges that ended 171a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // mid-block. 172a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (UseI == UseE || *UseI >= Stop) { 173a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen ++NumThroughBlocks; 174a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen ThroughBlocks.set(BI.MBB->getNumber()); 175a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // The range shouldn't end mid-block if there are no uses. This shouldn't 176a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // happen. 177a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (LVI->end < Stop) 178a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen return false; 179a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } else { 180a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // This block has uses. Find the first and last uses in the block. 181fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.FirstInstr = *UseI; 182fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen assert(BI.FirstInstr >= Start); 183f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen do ++UseI; 1846c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen while (UseI != UseE && *UseI < Stop); 185fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LastInstr = UseI[-1]; 186fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen assert(BI.LastInstr < Stop); 187f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 188a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // LVI is the first live segment overlapping MBB. 189a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveIn = LVI->start <= Start; 190a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen 19177ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen // When not live in, the first use should be a def. 19277ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen if (!BI.LiveIn) { 19377ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen assert(LVI->start == LVI->valno->def && "Dangling LiveRange start"); 194fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen assert(LVI->start == BI.FirstInstr && "First instr should be a def"); 195fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.FirstDef = BI.FirstInstr; 19677ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen } 19777ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen 198a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // Look for gaps in the live range. 199a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = true; 200a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen while (LVI->end < Stop) { 201a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SlotIndex LastStop = LVI->end; 202a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (++LVI == LVE || LVI->start >= Stop) { 203a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = false; 204fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LastInstr = LastStop; 205a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen break; 206a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } 20777ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen 208a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (LastStop < LVI->start) { 209a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // There is a gap in the live range. Create duplicate entries for the 210a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // live-in snippet and the live-out snippet. 211a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen ++NumGapBlocks; 212a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen 213a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // Push the Live-in part. 214a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = false; 215a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen UseBlocks.push_back(BI); 216fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen UseBlocks.back().LastInstr = LastStop; 217a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen 218a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // Set up BI for the live-out part. 219a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveIn = false; 220a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = true; 221fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.FirstInstr = BI.FirstDef = LVI->start; 222a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } 22377ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen 22477ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen // A LiveRange that starts in the middle of the block must be a def. 22577ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen assert(LVI->start == LVI->valno->def && "Dangling LiveRange start"); 22677ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen if (!BI.FirstDef) 22777ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen BI.FirstDef = LVI->start; 228f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 229f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 230db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.push_back(BI); 231626d6fb1903e74337b257c5e165944bcd1273e65Jakob Stoklund Olesen 232a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // LVI is now at LVE or LVI->end >= Stop. 233a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (LVI == LVE) 234a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen break; 235a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } 236f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 237f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Live segment ends exactly at Stop. Move to the next segment. 2386c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (LVI->end == Stop && ++LVI == LVE) 239f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 240f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 241f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Pick the next basic block. 2426c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (LVI->start < Stop) 243f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen ++MFI; 244f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 245f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MFI = LIS.getMBBFromIndex(LVI->start); 246f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 247b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen 248b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count"); 2492b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 250f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen} 251f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 2529f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesenunsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { 2539f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (cli->empty()) 2549f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen return 0; 2559f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval *li = const_cast<LiveInterval*>(cli); 2569f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval::iterator LVI = li->begin(); 2579f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval::iterator LVE = li->end(); 2589f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen unsigned Count = 0; 2599f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 2609f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Loop over basic blocks where li is live. 2619f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start); 2629f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen SlotIndex Stop = LIS.getMBBEndIdx(MFI); 2639f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen for (;;) { 2649f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen ++Count; 2659f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LVI = li->advanceTo(LVI, Stop); 2669f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (LVI == LVE) 2679f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen return Count; 2689f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen do { 2699f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen ++MFI; 2709f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen Stop = LIS.getMBBEndIdx(MFI); 2719f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } while (Stop <= LVI->start); 2729f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 2739f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen} 2749f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 27506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesenbool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 27606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen unsigned OrigReg = VRM.getOriginal(CurLI->reg); 27706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen const LiveInterval &Orig = LIS.getInterval(OrigReg); 27806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen assert(!Orig.empty() && "Splitting empty interval?"); 27906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen LiveInterval::const_iterator I = Orig.find(Idx); 28006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 28106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range containing Idx should begin at Idx. 28206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen if (I != Orig.end() && I->start <= Idx) 28306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I->start == Idx; 28406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 28506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range does not contain Idx, previous must end at Idx. 28606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I != Orig.begin() && (--I)->end == Idx; 28706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen} 28806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 2898ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::analyze(const LiveInterval *li) { 2908ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen clear(); 291078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = li; 292abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen analyzeUses(); 2938ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 2948ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 295697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen 296f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2971c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen// Split Editor 2981407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 2991407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3001c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 3011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenSplitEditor::SplitEditor(SplitAnalysis &sa, 3021c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveIntervals &lis, 3031c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VirtRegMap &vrm, 304bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen MachineDominatorTree &mdt) 3051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen : SA(sa), LIS(lis), VRM(vrm), 3061c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MRI(vrm.getMachineFunction().getRegInfo()), 3071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MDT(mdt), 3081c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 3091c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 310bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Edit(0), 3111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen OpenIdx(0), 312708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SpillMode(SM_Partition), 3131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen RegAssign(Allocator) 314bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen{} 315bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 316708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesenvoid SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { 317708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen Edit = &LRE; 318708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SpillMode = SM; 319bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen OpenIdx = 0; 320bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen RegAssign.clear(); 321bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Values.clear(); 322c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen 323c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen // Reset the LiveRangeCalc instances needed for this spill mode. 324c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRCalc[0].reset(&VRM.getMachineFunction()); 325c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen if (SpillMode) 326c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRCalc[1].reset(&VRM.getMachineFunction()); 327bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 3281c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // We don't need an AliasAnalysis since we will only be performing 3291c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // cheap-as-a-copy remats anyway. 330a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->anyRematerializable(LIS, TII, 0); 3311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 3321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3331c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::dump() const { 3341c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (RegAssign.empty()) { 3351c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " empty\n"; 3361c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 3371c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3381c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3391c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 3401c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 3411c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << '\n'; 342b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen} 343b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen 3441c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::defValue(unsigned RegIdx, 3451c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const VNInfo *ParentVNI, 3461c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx) { 3471c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 3481c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 349a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 350a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 3511c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3521c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Create a new value. 3531c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 3541c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3551c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Use insert for lookup, so we can add missing values with a second lookup. 3561c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen std::pair<ValueMap::iterator, bool> InsP = 3571c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 3581c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3591c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was the first time (RegIdx, ParentVNI) was mapped. 3601c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Keep it as a simple def without any liveness. 3611c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (InsP.second) 3621c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 3631c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3641c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // If the previous value was a simple mapping, add liveness for it now. 3651c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (VNInfo *OldVNI = InsP.first->second) { 3661c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = OldVNI->def; 3671c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 3681c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // No longer a simple mapping. 3691c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen InsP.first->second = 0; 3701c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3711c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3721c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is a complex mapping, add liveness for VNI 3731c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 3741c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 3751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3761c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 3779ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen} 3789ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 3791c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 3801c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 3811c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 3821c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3831c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // ParentVNI was either unmapped or already complex mapped. Either way. 3841c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (!VNI) 3851c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 3861c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3871c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was previously a single mapping. Make sure the old def is represented 3881c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by a trivial live range. 3891c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 390a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 3911c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNI = 0; 3921c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 3935fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 394d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen// extendRange - Extend the live range to reach Idx. 3951407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen// Potentially create phi-def values. 3961c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 397c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen getLRCalc(RegIdx).extend(Edit->get(RegIdx), Idx.getNextSlot(), 398c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); 399670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen} 400670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 4010f43811903f10394f7088f4634c0b4f9668cbac0Eric ChristopherVNInfo *SplitEditor::defFromParent(unsigned RegIdx, 402cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 403cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 404cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 405cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I) { 406cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineInstr *CopyMI = 0; 407cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex Def; 408a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 409cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 410bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen // We may be trying to avoid interference that ends at a deleted instruction, 411bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen // so always begin RegIdx 0 early and all others late. 412bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen bool Late = RegIdx != 0; 413bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen 414cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Attempt cheap-as-a-copy rematerialization. 415cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 416a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 417bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late); 418e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumRemats; 419cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } else { 420cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Can't remat, just insert a copy from parent. 4210f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 422a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen .addReg(Edit->getReg()); 423bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) 424bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen .getDefIndex(); 425e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumCopies; 426cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } 427cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 428cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Define the value in Reg. 429670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 430cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNI->setCopy(CopyMI); 431cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen return VNI; 432cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen} 433cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 434f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen/// Create a new virtual register and live interval. 435e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesenunsigned SplitEditor::openIntv() { 4360f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the complement as index 0. 437a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->empty()) 4386a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->create(LIS, VRM); 4390f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 4400f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the open interval. 441a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen OpenIdx = Edit->size(); 4426a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->create(LIS, VRM); 443e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen return OpenIdx; 444e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen} 445e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 446e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesenvoid SplitEditor::selectIntv(unsigned Idx) { 447e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen assert(Idx != 0 && "Cannot select the complement interval"); 448e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen assert(Idx < Edit->size() && "Can only select previously opened interval"); 44987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); 450e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen OpenIdx = Idx; 451f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 452f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 453207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 4540f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvBefore"); 4559b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " enterIntvBefore " << Idx); 456207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 457a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 458f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 4599b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 460207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx; 461f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 462207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 463078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 464f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen assert(MI && "enterIntvBefore called with invalid index"); 465cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 466207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 467207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 468f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 469f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 47087360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { 47187360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before enterIntvAfter"); 47287360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAfter " << Idx); 47387360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 47487360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 47587360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen if (!ParentVNI) { 47687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 47787360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen return Idx; 47887360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen } 47987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 48087360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 48187360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen assert(MI && "enterIntvAfter called with invalid index"); 48287360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen 48387360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), 48487360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 48587360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen return VNI->def; 48687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen} 48787360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen 488207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 4890f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 490207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(&MBB); 491207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex Last = End.getPrevSlot(); 492207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 493a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 494f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 4959b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 496207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return End; 497f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 4989b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id); 499207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 500a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 501207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen RegAssign.insert(VNI->def, End, OpenIdx); 5020f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 503207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 504f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 505f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 506078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// useIntv - indicate that all instructions in MBB should use OpenLI. 5077536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 508078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 509f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 510f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 5117536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 5120f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before useIntv"); 5130f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 5140f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, End, OpenIdx); 5150f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 516f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 517f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 518207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 5190f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 5209b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAfter " << Idx); 521f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 522f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen // The interval must be live beyond the instruction at Idx. 523cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 524a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 525f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5269b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 527207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx.getNextSlot(); 528f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 529207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 530f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 53101cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 53201cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen assert(MI && "No instruction at index"); 53301cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 53401cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 535207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 536f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 537f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 5389b057771ba22441b8d312404204433477b4be657Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 5399b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 5409b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvBefore " << Idx); 5419b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 5429b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen // The interval must be live into the instruction at Idx. 543fc47933db5c8fea9bc89470d83cc5af7ca36f2a3Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 544a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 5459b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!ParentVNI) { 5469b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 5479b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return Idx.getNextSlot(); 5489b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 5499b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 5509b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 5519b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 5529b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(MI && "No instruction at index"); 5539b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 5549b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return VNI->def; 5559b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen} 5569b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 557207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 5580f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 559078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(&MBB); 5609b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 5617536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 562a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 563f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5649b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 565207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Start; 5667536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen } 5677536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 5680f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 569cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MBB.SkipPHIsAndLabels(MBB.begin())); 5700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, VNI->def, OpenIdx); 5710f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 572207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 573f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 574f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 5755c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesenvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 5765c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before overlapIntv"); 577a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 578a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 5795c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Parent changes value in extended range"); 5805c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 5815c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Range cannot span basic blocks"); 5825c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 583d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen // The complement interval will be extended as needed by extendRange(). 584b3dd82670aa60cacba81f090d292722c3ef44354Jakob Stoklund Olesen if (ParentVNI) 585b3dd82670aa60cacba81f090d292722c3ef44354Jakob Stoklund Olesen markComplexMapped(0, ParentVNI); 5865c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 5875c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen RegAssign.insert(Start, End, OpenIdx); 5885c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dump()); 5895c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen} 5905c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 59144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen/// transferValues - Transfer all possible values to the new live ranges. 59244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen/// Values that were rematerialized are left alone, they need extendRange(). 59344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesenbool SplitEditor::transferValues() { 5944670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Skipped = false; 5954670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegAssignMap::const_iterator AssignI = RegAssign.begin(); 596a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 597a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 5984670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " blit " << *ParentI << ':'); 5994670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen VNInfo *ParentVNI = ParentI->valno; 6004670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // RegAssign has holes where RegIdx 0 should be used. 6014670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex Start = ParentI->start; 6024670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen AssignI.advanceTo(Start); 6034670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen do { 6044670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen unsigned RegIdx; 6054670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex End = ParentI->end; 6064670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (!AssignI.valid()) { 6074670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 6084670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else if (AssignI.start() <= Start) { 6094670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = AssignI.value(); 6104670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (AssignI.stop() < End) { 6114670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = AssignI.stop(); 6124670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++AssignI; 6134670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 6144670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else { 6154670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 6164670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = std::min(End, AssignI.start()); 6174670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 61844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 61944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 6204670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 62144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 62244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 62344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Check for a simply defined value that can be blitted directly. 6244670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 6254670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id); 62644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LI->addRange(LiveRange(Start, End, VNI)); 62744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Start = End; 62844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 62944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 63044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 63144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Skip rematerialized values, we need to use extendRange() and 63244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // extendPHIKillRanges() to completely recompute the live ranges. 63344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) { 63444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << "(remat)"); 6354670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Skipped = true; 63644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Start = End; 63744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 63844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 63944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 640c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LiveRangeCalc &LRC = getLRCalc(RegIdx); 641c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen 64244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This value has multiple defs in RegIdx, but it wasn't rematerialized, 64344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // so the live range is accurate. Add live-in blocks in [Start;End) to the 64444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // LiveInBlocks. 64544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 64644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SlotIndex BlockStart, BlockEnd; 64744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 64844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 64944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The first block may be live-in, or it may have its own def. 65044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Start != BlockStart) { 65144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(BlockStart, 65244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen std::min(BlockEnd, End).getPrevSlot()); 65344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(VNI && "Missing def for complex mapped value"); 65444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 65544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // MBB has its own def. Is it also live-out? 656b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (BlockEnd <= End) 657c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.setLiveOutValue(MBB, VNI); 658b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 65944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Skip to the next block for live-in. 66044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen ++MBB; 66144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockStart = BlockEnd; 66244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 66344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 66444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Handle the live-in blocks covered by [Start;End). 66544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(Start <= BlockStart && "Expected live-in block"); 66644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen while (BlockStart < End) { 66744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 66844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockEnd = LIS.getMBBEndIdx(MBB); 66944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (BlockStart == ParentVNI->def) { 67044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This block has the def of a parent PHI, so it isn't live-in. 67144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 67244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(BlockStart, 67344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen std::min(BlockEnd, End).getPrevSlot()); 67444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(VNI && "Missing def for complex mapped parent PHI"); 675b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (End >= BlockEnd) 676c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.setLiveOutValue(MBB, VNI); // Live-out as well. 67744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } else { 678b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This block needs a live-in value. The last block covered may not 679b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // be live-out. 68044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (End < BlockEnd) 681c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.addLiveInBlock(LI, MDT[MBB], End); 68244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen else { 683b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Live-through, and we don't know the value. 684c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.addLiveInBlock(LI, MDT[MBB]); 685c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.setLiveOutValue(MBB, 0); 68644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 68744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 68844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockStart = BlockEnd; 68944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen ++MBB; 69044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 6914670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Start = End; 6924670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } while (Start != ParentI->end); 6934670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 6944670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 69544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 696c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRCalc[0].calculateValues(LIS.getSlotIndexes(), &MDT, 697c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen &LIS.getVNInfoAllocator()); 698c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen if (SpillMode) 699c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRCalc[1].calculateValues(LIS.getSlotIndexes(), &MDT, 700c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen &LIS.getVNInfoAllocator()); 70144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 7024670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen return Skipped; 7034670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen} 7044670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 705e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesenvoid SplitEditor::extendPHIKillRanges() { 706e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // Extend live ranges to be live-out for successor PHI values. 707a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 708a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 709e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen const VNInfo *PHIVNI = *I; 710e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 711e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen continue; 712e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 713e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 714e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 715e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 716e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 717e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // The predecessor may not have a live-out value. That is OK, like an 718e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // undef PHI operand. 719a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->getParent().liveAt(End)) { 720e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen assert(RegAssign.lookup(End) == RegIdx && 721e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen "Different register assignment in phi predecessor"); 722e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen extendRange(RegIdx, End); 723e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 724e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 725e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 726e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen} 727e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 728a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 7294670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenvoid SplitEditor::rewriteAssigned(bool ExtendRanges) { 730a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 731078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 7327466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineOperand &MO = RI.getOperand(); 7337466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 7347466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen ++RI; 7350f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // LiveDebugVariables should have handled all DBG_VALUE instructions. 7367466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen if (MI->isDebugValue()) { 7377466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen DEBUG(dbgs() << "Zapping " << *MI); 7387466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MO.setReg(0); 7397466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen continue; 7407466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 741a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 742b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // <undef> operands don't really read the register, so it doesn't matter 743b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // which register we choose. When the use operand is tied to a def, we must 744b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // use the same register as the def, so just do that always. 745078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI); 746b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen if (MO.isDef() || MO.isUndef()) 7477cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex(); 7480f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7490f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite to the mapped register at Idx. 7500f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned RegIdx = RegAssign.lookup(Idx); 751a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen MO.setReg(Edit->get(RegIdx)->reg); 7520f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 7530f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':' << RegIdx << '\t' << *MI); 7540f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 7557cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Extend liveness to Idx if the instruction reads reg. 75681d686edbe6effe624add9394673bd571d89bfb7Jakob Stoklund Olesen if (!ExtendRanges || MO.isUndef()) 7577cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 7587cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 7597cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Skip instructions that don't read Reg. 7607cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (MO.isDef()) { 7617cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!MO.getSubReg() && !MO.isEarlyClobber()) 7627cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 7637cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // We may wan't to extend a live range for a partial redef, or for a use 7647cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // tied to an early clobber. 7657cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getPrevSlot(); 7667cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!Edit->getParent().liveAt(Idx)) 7677cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 7687cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen } else 7697cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getUseIndex(); 7707cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 7717cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen extendRange(RegIdx, Idx); 7727466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 7737466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen} 7747466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 7755881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesenvoid SplitEditor::deleteRematVictims() { 7765881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen SmallVector<MachineInstr*, 8> Dead; 7772dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 7782dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen LiveInterval *LI = *I; 7792dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 7802dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen LII != LIE; ++LII) { 7812dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen // Dead defs end at the store slot. 7822dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen if (LII->end != LII->valno->def.getNextSlot()) 7832dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 7842dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 7852dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen assert(MI && "Missing instruction for dead def"); 7862dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MI->addRegisterDead(LI->reg, &TRI); 7875881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 7882dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen if (!MI->allDefsAreDead()) 7892dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 7905881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 7912dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << *MI); 7922dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen Dead.push_back(MI); 7932dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen } 7945881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen } 7955881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 7965881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (Dead.empty()) 7975881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen return; 7985881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 7996a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); 8005881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen} 8015881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 8025928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesenvoid SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 8034670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumFinished; 8040f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 8050f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // At this point, the live intervals in Edit contain VNInfos corresponding to 8060f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // the inserted copies. 8070f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 8080f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Add the original defs from the parent interval. 809a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 810a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 8110f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *ParentVNI = *I; 8129ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (ParentVNI->isUnused()) 8139ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen continue; 814670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 81529ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 81629ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNI->setIsPHIDef(ParentVNI->isPHIDef()); 81729ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNI->setCopy(ParentVNI->getCopy()); 81829ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen 8194670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Mark rematted values as complex everywhere to force liveness computation. 8204670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // The new live ranges may be truncated. 821a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 822a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 8234670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen markComplexMapped(i, ParentVNI); 8245fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 825c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 82644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Transfer the simply mapped values, check if any are skipped. 82744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen bool Skipped = transferValues(); 82844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Skipped) 8294670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen extendPHIKillRanges(); 8304670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen else 8314670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumSimple; 8324670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 8334670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Rewrite virtual registers, possibly extending ranges. 83444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen rewriteAssigned(Skipped); 835463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher 8365881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Delete defs that were rematted everywhere. 83744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Skipped) 8385881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen deleteRematVictims(); 8395fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 8400253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Get rid of unused values and set phi-kill flags. 841a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 842078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen (*I)->RenumberValues(LIS); 8430253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8445928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Provide a reverse mapping from original indices to Edit ranges. 8455928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRMap) { 8465928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->clear(); 8475928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 8485928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->push_back(i); 8495928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 8505928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 8513a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Now check if any registers were separated into multiple components. 852078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 853a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 8543a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Don't use iterators, they are invalidated by create() below. 855a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *li = Edit->get(i); 8563a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen unsigned NumComp = ConEQ.Classify(li); 8573a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen if (NumComp <= 1) 8583a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen continue; 8593a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 8603a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> dups; 8613a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen dups.push_back(li); 862ae5fbeec23cff833cad9e6b2a638efd1f48bef49Matt Beaumont-Gay for (unsigned j = 1; j != NumComp; ++j) 8636a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen dups.push_back(&Edit->create(LIS, VRM)); 8642254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen ConEQ.Distribute(&dups[0], MRI); 8655928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // The new intervals all map back to i. 8665928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRMap) 8675928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->resize(Edit->size(), i); 8683a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen } 8693a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen 87008e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen // Calculate spill weight and allocation hints for new intervals. 8716094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops); 8725928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 8735928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen assert(!LRMap || LRMap->size() == Edit->size()); 874f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 875f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 876f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 8778ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 878f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen// Single Block Splitting 879f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 880f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 8812d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesenbool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, 8822d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen bool SingleInstrs) const { 8832d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Always split for multiple instructions. 8842d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (!BI.isOneInstr()) 8852d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return true; 8862d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Don't split for single instructions unless explicitly requested. 8872d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (!SingleInstrs) 8882d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return false; 8892d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Splitting a live-through range always makes progress. 8902d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (BI.LiveIn && BI.LiveOut) 8912d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return true; 8922d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // No point in isolating a copy. It has no register class constraints. 8932d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike()) 8942d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return false; 8952d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Finally, don't isolate an end point that was created by earlier splits. 8962d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return isOriginalEndpoint(BI.FirstInstr); 8972d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen} 8982d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen 899fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 900fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen openIntv(); 901fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 902fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr, 903fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen LastSplitPoint)); 904fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { 905fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(SegStart, leaveIntvAfter(BI.LastInstr)); 906fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } else { 907fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // The last use is after the last valid split point. 908fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 909fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen useIntv(SegStart, SegStop); 910fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(SegStop, BI.LastInstr); 911fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 912fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen} 913fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 914b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 915b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 916b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// Global Live Range Splitting Support 917b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 918b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 919b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// These methods support a method of global live range splitting that uses a 920b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// global algorithm to decide intervals for CFG edges. They will insert split 921b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// points and color intervals in basic blocks while avoiding interference. 922b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// 923b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// Note that splitSingleBlock is also useful for blocks where both CFG edges 924b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// are on the stack. 925b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 926b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitLiveThroughBlock(unsigned MBBNum, 927b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvIn, SlotIndex LeaveBefore, 928b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvOut, SlotIndex EnterAfter){ 929b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 930b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); 931b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 932b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop 933b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ") intf " << LeaveBefore << '-' << EnterAfter 934b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", live-through " << IntvIn << " -> " << IntvOut); 935b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 936b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks"); 937b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 938fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block"); 939fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf"); 940fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!EnterAfter || EnterAfter >= Start) && "Interference before block"); 941fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen 942fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); 943fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen 944b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (!IntvOut) { 945b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill on entry.\n"); 946b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 947b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<<<< Possible LeaveBefore interference. 948b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 949b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // -____________ Spill on entry. 950b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 951b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 952b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = leaveIntvAtTop(*MBB); 953b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 954b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen (void)Idx; 955b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 956b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 957b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 958b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (!IntvIn) { 959b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", reload on exit.\n"); 960b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 961b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>>>>> Possible EnterAfter interference. 962b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 963b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ___________-- Reload on exit. 964b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 965b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 966b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAtEnd(*MBB); 967b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 968b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen (void)Idx; 969b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 970b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 971b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 972b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { 973b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", straight through.\n"); 974b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 975b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 976b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ------------- Straight through, same intv, no interference. 977b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 978b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 979b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Stop); 980b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 981b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 982b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 983b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // We cannot legally insert splits after LSP. 984b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(MBBNum); 985fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf"); 986b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 987b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || 988b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { 989b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", switch avoiding interference.\n"); 990b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 991b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. 992b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 993b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ------======= Switch intervals between interference. 994b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 995b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 996fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen SlotIndex Idx; 997fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen if (LeaveBefore && LeaveBefore < LSP) { 998fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen Idx = enterIntvBefore(LeaveBefore); 999fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen useIntv(Idx, Stop); 1000fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen } else { 1001fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen Idx = enterIntvAtEnd(*MBB); 1002fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen } 1003b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1004b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1005b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1006b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1007b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1008b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1009b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1010b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", create local intv for interference.\n"); 1011b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1012b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. 1013b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1014b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ==---------== Switch intervals before/after interference. 1015b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1016b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(LeaveBefore <= EnterAfter && "Missed case"); 1017b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1018b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1019b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAfter(EnterAfter); 1020b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1021b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1022b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1023b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1024b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen Idx = leaveIntvBefore(LeaveBefore); 1025b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1026b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1027b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1028b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1029b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1030b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 1031b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvIn, SlotIndex LeaveBefore) { 1032b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 1033b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1034b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1035b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1036fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1037b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", reg-in " << IntvIn << ", leave before " << LeaveBefore 1038b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << (BI.LiveOut ? ", stack-out" : ", killed in block")); 1039b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1040b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(IntvIn && "Must have register in"); 1041b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(BI.LiveIn && "Must be live-in"); 1042b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference"); 1043b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1044fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { 1045b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << " before interference.\n"); 1046b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1047b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<< Interference after kill. 1048b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---x | Killed in block. 1049b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ========= Use IntvIn everywhere. 1050b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1051b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1052fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(Start, BI.LastInstr); 1053b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1054b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1055b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1056b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1057b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1058fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { 1059b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1060b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<< Possible interference after last use. 1061b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-out on stack. 1062b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =========____ Leave IntvIn after last use. 1063b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1064b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // < Interference after last use. 1065b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o--o| Live-out on stack, late last use. 1066b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ============ Copy to stack after LSP, overlap IntvIn. 1067b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // \_____ Stack interval is live-out. 1068b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1069fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (BI.LastInstr < LSP) { 1070b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill after last use before interference.\n"); 1071b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1072fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex Idx = leaveIntvAfter(BI.LastInstr); 1073b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1074b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1075b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } else { 1076b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill before last split point.\n"); 1077b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1078af4e40c2f41a7d60b86958e034b00542d551b5f2Jakob Stoklund Olesen SlotIndex Idx = leaveIntvBefore(LSP); 1079fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(Idx, BI.LastInstr); 1080b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1081b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1082b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1083b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1084b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1085b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1086b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // The interference is overlapping somewhere we wanted to use IntvIn. That 1087b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // means we need to create a local interval that can be allocated a 1088b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // different register. 1089b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned LocalIntv = openIntv(); 1090f9d7fb6b3c45abc64ad52cd8a9a8a7dd5aa9f4bbMatt Beaumont-Gay (void)LocalIntv; 1091b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n"); 1092b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1093fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastInstr < LSP) { 1094b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1095b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<< Interference overlapping uses. 1096b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-out on stack. 1097b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =====----____ Leave IntvIn before interference, then spill. 1098b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1099fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex To = leaveIntvAfter(BI.LastInstr); 1100b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(LeaveBefore); 1101b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, To); 1102b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1103b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, From); 1104b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1105b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1106b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1107b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1108b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<< Interference overlapping uses. 1109b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o--o| Live-out on stack, late last use. 1110b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =====------- Copy to stack before LSP, overlap LocalIntv. 1111b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // \_____ Stack interval is live-out. 1112b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1113b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex To = leaveIntvBefore(LSP); 1114fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(To, BI.LastInstr); 1115b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); 1116b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, To); 1117b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1118b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, From); 1119b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1120b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1121b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1122b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 1123b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvOut, SlotIndex EnterAfter) { 1124b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 1125b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1126b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1127b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1128fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1129b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", reg-out " << IntvOut << ", enter after " << EnterAfter 1130b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << (BI.LiveIn ? ", stack-in" : ", defined in block")); 1131b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1132b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1133b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1134b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(IntvOut && "Must have register out"); 1135b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(BI.LiveOut && "Must be live-out"); 1136b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || EnterAfter < LSP) && "Bad interference"); 1137b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1138fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { 1139b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << " after interference.\n"); 1140b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1141b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> Interference before def. 1142b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // | o---o---| Defined in block. 1143b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ========= Use IntvOut everywhere. 1144b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1145b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1146fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(BI.FirstInstr, Stop); 1147b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1148b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1149b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1150fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { 1151b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", reload after interference.\n"); 1152b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1153b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> Interference before def. 1154b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-through, stack-in. 1155b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ____========= Enter IntvOut before first use. 1156b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1157b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1158fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr)); 1159b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1160b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1161b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1162b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1163b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1164b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // The interference is overlapping somewhere we wanted to use IntvOut. That 1165b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // means we need to create a local interval that can be allocated a 1166b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // different register. 1167b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", interference overlaps uses.\n"); 1168b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1169b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>>>>> Interference overlapping uses. 1170b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-through, stack-in. 1171b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ____---====== Create local interval for interference range. 1172b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1173b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1174b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAfter(EnterAfter); 1175b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1176b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1177b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1178b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen openIntv(); 1179fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr)); 1180b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, Idx); 1181b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1182