SplitKit.cpp revision 7d6b6a05b549da70b4473f015c97954c2a422724
18ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 28ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 38ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// The LLVM Compiler Infrastructure 48ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 58ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// License. See LICENSE.TXT for details. 78ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 88ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 98ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 108ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// This file contains the SplitAnalysis class as well as mutator functions for 118ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// live range splitting. 128ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 138ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 148ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 15376dcbd6c2c7adb8281f89d045b307eee7bd682aJakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "SplitKit.h" 17a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen#include "LiveRangeEdit.h" 18f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "VirtRegMap.h" 194670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 21d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 22f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/Debug.h" 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 266a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 276a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 288ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenusing namespace llvm; 308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 314670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund OlesenSTATISTIC(NumFinished, "Number of splits finished"); 324670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund OlesenSTATISTIC(NumSimple, "Number of splits that were simple"); 334670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 348ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 358ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// Split Analysis 368ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 381b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund OlesenSplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 39f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const LiveIntervals &lis, 40f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli) 411b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen : MF(vrm.getMachineFunction()), 421b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen VRM(vrm), 43078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LIS(lis), 44078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Loops(mli), 451b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen TII(*MF.getTarget().getInstrInfo()), 461a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen CurLI(0), 471a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LastSplitPoint(MF.getNumBlockIDs()) {} 488ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 498ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::clear() { 50b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen UseSlots.clear(); 51db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.clear(); 52db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ThroughBlocks.clear(); 53078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = 0; 547d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen DidRepairRange = false; 558ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 568ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 571a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund OlesenSlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { 581a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen const MachineBasicBlock *MBB = MF.getBlockNumbered(Num); 591a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor(); 601a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num]; 611a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 621a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // Compute split points on the first call. The pair is independent of the 631a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // current live interval. 641a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (!LSP.first.isValid()) { 651a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator(); 661a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (FirstTerm == MBB->end()) 671a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.first = LIS.getMBBEndIdx(MBB); 681a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen else 691a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.first = LIS.getInstructionIndex(FirstTerm); 701a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 711a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // If there is a landing pad successor, also find the call instruction. 721a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (!LPad) 731a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.first; 741a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // There may not be a call instruction (?) in which case we ignore LPad. 751a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.second = LSP.first; 761a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen for (MachineBasicBlock::const_iterator I = FirstTerm, E = MBB->begin(); 771a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen I != E; --I) 781a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (I->getDesc().isCall()) { 791a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.second = LIS.getInstructionIndex(I); 801a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen break; 811a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 821a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 831a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 841a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // If CurLI is live into a landing pad successor, move the last split point 851a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // back to the call that may throw. 8671d9e65ee71712b965c79739e63de94fbb8078adJakob Stoklund Olesen if (LPad && LSP.second.isValid() && LIS.isLiveInToMBB(*CurLI, LPad)) 871a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.second; 881a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen else 891a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.first; 906a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen} 916a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 92078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 93abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesenvoid SplitAnalysis::analyzeUses() { 94a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen assert(UseSlots.empty() && "Call clear first"); 95a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 96a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // First get all the defs from the interval values. This provides the correct 97a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // slots for early clobbers. 98a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(), 99a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen E = CurLI->vni_end(); I != E; ++I) 100a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen if (!(*I)->isPHIDef() && !(*I)->isUnused()) 101a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.push_back((*I)->def); 102a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 103a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // Get use slots form the use-def chain. 104078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineRegisterInfo &MRI = MF.getRegInfo(); 105a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen for (MachineRegisterInfo::use_nodbg_iterator 106a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E; 107a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen ++I) 108a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen if (!I.getOperand().isUndef()) 109a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.push_back(LIS.getInstructionIndex(&*I).getDefIndex()); 110a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 111b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen array_pod_sort(UseSlots.begin(), UseSlots.end()); 1122b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 113a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // Remove duplicates, keeping the smaller slot for each instruction. 114a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // That is what we want for early clobbers. 115a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), 116a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen SlotIndex::isSameInstr), 117a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.end()); 118a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 1192b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // Compute per-live block info. 1202b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen if (!calcLiveBlockInfo()) { 1212b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // FIXME: calcLiveBlockInfo found inconsistencies in the live range. 1222b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // I am looking at you, SimpleRegisterCoalescing! 1237d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen DidRepairRange = true; 1242b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); 1252b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen const_cast<LiveIntervals&>(LIS) 1262b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen .shrinkToUses(const_cast<LiveInterval*>(CurLI)); 127db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.clear(); 128db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ThroughBlocks.clear(); 1292b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen bool fixed = calcLiveBlockInfo(); 1302b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen (void)fixed; 1312b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen assert(fixed && "Couldn't fix broken live interval"); 1322b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen } 1332b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 134ef1f5ccca7efaa18209523b31019d356d302f635Jakob Stoklund Olesen DEBUG(dbgs() << "Analyze counted " 135db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen << UseSlots.size() << " instrs in " 136db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen << UseBlocks.size() << " blocks, through " 137f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen << NumThroughBlocks << " blocks.\n"); 1388ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 1398ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 140f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 141f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// where CurLI is live. 1422b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesenbool SplitAnalysis::calcLiveBlockInfo() { 143f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ThroughBlocks.resize(MF.getNumBlockIDs()); 144f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen NumThroughBlocks = 0; 145f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (CurLI->empty()) 1462b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 147f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 148f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVI = CurLI->begin(); 149f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVE = CurLI->end(); 150f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 151f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 152f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseI = UseSlots.begin(); 153f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseE = UseSlots.end(); 154f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 155f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Loop over basic blocks where CurLI is live. 156f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 157f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (;;) { 158f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BlockInfo BI; 159f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.MBB = MFI; 1606c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex Start, Stop; 1616c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 162f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 163f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // LVI is the first live segment overlapping MBB. 1646c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen BI.LiveIn = LVI->start <= Start; 165f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (!BI.LiveIn) 166f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Def = LVI->start; 167f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 168f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Find the first and last uses in the block. 169db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen bool Uses = UseI != UseE && *UseI < Stop; 170db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (Uses) { 171f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.FirstUse = *UseI; 1726c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen assert(BI.FirstUse >= Start); 173f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen do ++UseI; 1746c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen while (UseI != UseE && *UseI < Stop); 175f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LastUse = UseI[-1]; 1766c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen assert(BI.LastUse < Stop); 177f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 178f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 179f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Look for gaps in the live range. 180f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool hasGap = false; 181f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveOut = true; 1826c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen while (LVI->end < Stop) { 183f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastStop = LVI->end; 1846c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (++LVI == LVE || LVI->start >= Stop) { 185f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Kill = LastStop; 186f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveOut = false; 187f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 188f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 189f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LastStop < LVI->start) { 190f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen hasGap = true; 191f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Kill = LastStop; 192f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.Def = LVI->start; 193f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 194f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 195f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 196f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Don't set LiveThrough when the block has a gap. 197f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut; 198db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (Uses) 199db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.push_back(BI); 200f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen else { 201f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ++NumThroughBlocks; 202f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ThroughBlocks.set(BI.MBB->getNumber()); 203f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 2042b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // FIXME: This should never happen. The live range stops or starts without a 2052b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // corresponding use. An earlier pass did something wrong. 206db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (!BI.LiveThrough && !Uses) 2072b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return false; 2082b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 209f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // LVI is now at LVE or LVI->end >= Stop. 210f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (LVI == LVE) 211f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 212f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 213f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Live segment ends exactly at Stop. Move to the next segment. 2146c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (LVI->end == Stop && ++LVI == LVE) 215f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 216f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 217f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Pick the next basic block. 2186c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (LVI->start < Stop) 219f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen ++MFI; 220f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 221f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MFI = LIS.getMBBFromIndex(LVI->start); 222f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 2232b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 224f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen} 225f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 2269f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesenunsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { 2279f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (cli->empty()) 2289f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen return 0; 2299f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval *li = const_cast<LiveInterval*>(cli); 2309f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval::iterator LVI = li->begin(); 2319f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval::iterator LVE = li->end(); 2329f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen unsigned Count = 0; 2339f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 2349f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Loop over basic blocks where li is live. 2359f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start); 2369f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen SlotIndex Stop = LIS.getMBBEndIdx(MFI); 2379f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen for (;;) { 2389f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen ++Count; 2399f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LVI = li->advanceTo(LVI, Stop); 2409f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (LVI == LVE) 2419f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen return Count; 2429f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen do { 2439f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen ++MFI; 2449f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen Stop = LIS.getMBBEndIdx(MFI); 2459f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } while (Stop <= LVI->start); 2469f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 2479f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen} 2489f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 24906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesenbool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 25006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen unsigned OrigReg = VRM.getOriginal(CurLI->reg); 25106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen const LiveInterval &Orig = LIS.getInterval(OrigReg); 25206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen assert(!Orig.empty() && "Splitting empty interval?"); 25306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen LiveInterval::const_iterator I = Orig.find(Idx); 25406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 25506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range containing Idx should begin at Idx. 25606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen if (I != Orig.end() && I->start <= Idx) 25706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I->start == Idx; 25806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 25906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range does not contain Idx, previous must end at Idx. 26006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I != Orig.begin() && (--I)->end == Idx; 26106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen} 26206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 2638ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::analyze(const LiveInterval *li) { 2648ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen clear(); 265078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = li; 266abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen analyzeUses(); 2678ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 2688ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 269697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen 270f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2711c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen// Split Editor 2721407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 2731407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2741c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 2751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenSplitEditor::SplitEditor(SplitAnalysis &sa, 2761c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveIntervals &lis, 2771c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VirtRegMap &vrm, 278bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen MachineDominatorTree &mdt) 2791c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen : SA(sa), LIS(lis), VRM(vrm), 2801c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MRI(vrm.getMachineFunction().getRegInfo()), 2811c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MDT(mdt), 2821c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 2831c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 284bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Edit(0), 2851c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen OpenIdx(0), 2861c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen RegAssign(Allocator) 287bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen{} 288bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 289bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesenvoid SplitEditor::reset(LiveRangeEdit &lre) { 290bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Edit = &lre; 291bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen OpenIdx = 0; 292bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen RegAssign.clear(); 293bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Values.clear(); 29413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 29513ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // We don't need to clear LiveOutCache, only LiveOutSeen entries are read. 29613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutSeen.clear(); 297bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 2981c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // We don't need an AliasAnalysis since we will only be performing 2991c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // cheap-as-a-copy remats anyway. 300a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->anyRematerializable(LIS, TII, 0); 3011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 3021c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3031c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::dump() const { 3041c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (RegAssign.empty()) { 3051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " empty\n"; 3061c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 3071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3081c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3091c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 3101c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 3111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << '\n'; 312b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen} 313b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen 3141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::defValue(unsigned RegIdx, 3151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const VNInfo *ParentVNI, 3161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx) { 3171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 3181c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 319a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 320a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 3211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3221c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Create a new value. 3231c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); 3241c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3251c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Use insert for lookup, so we can add missing values with a second lookup. 3261c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen std::pair<ValueMap::iterator, bool> InsP = 3271c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); 3281c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3291c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was the first time (RegIdx, ParentVNI) was mapped. 3301c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Keep it as a simple def without any liveness. 3311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (InsP.second) 3321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 3331c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3341c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // If the previous value was a simple mapping, add liveness for it now. 3351c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (VNInfo *OldVNI = InsP.first->second) { 3361c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = OldVNI->def; 3371c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); 3381c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // No longer a simple mapping. 3391c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen InsP.first->second = 0; 3401c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3411c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3421c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is a complex mapping, add liveness for VNI 3431c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 3441c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 3451c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3461c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 3479ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen} 3489ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 3491c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { 3501c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 3511c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; 3521c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3531c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // ParentVNI was either unmapped or already complex mapped. Either way. 3541c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (!VNI) 3551c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 3561c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3571c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was previously a single mapping. Make sure the old def is represented 3581c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by a trivial live range. 3591c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 360a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); 3611c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNI = 0; 3621c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 3635fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 364d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen// extendRange - Extend the live range to reach Idx. 3651407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen// Potentially create phi-def values. 3661c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { 3671407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 368078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); 3691407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen assert(IdxMBB && "No MBB at Idx"); 370a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 3711407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3721407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Is there a def in the same MBB we can extend? 373d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx)) 374d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen return; 3751407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3761407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Now for the fun part. We know that ParentVNI potentially has multiple defs, 3771407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // and we may need to create even more phi-defs to preserve VNInfo SSA form. 378e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Perform a search for all predecessor blocks where we know the dominating 37944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // VNInfo. 38044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen VNInfo *VNI = findReachingDefs(LI, IdxMBB, Idx.getNextSlot()); 381e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 38244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // When there were multiple different values, we may need new PHIs. 38344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (!VNI) 38444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen return updateSSA(); 38544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 38644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Poor man's SSA update for the single-value case. 38744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveOutPair LOP(VNI, MDT[LIS.getMBBFromIndex(VNI->def)]); 38844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 38944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen E = LiveInBlocks.end(); I != E; ++I) { 39044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen MachineBasicBlock *MBB = I->DomNode->getBlock(); 39144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 39244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (I->Kill.isValid()) 39344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LI->addRange(LiveRange(Start, I->Kill, VNI)); 39444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen else { 39544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveOutCache[MBB] = LOP; 39644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 39744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 39844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 39944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen} 40044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 40144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen/// findReachingDefs - Search the CFG for known live-out values. 40244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen/// Add required live-in blocks to LiveInBlocks. 40344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund OlesenVNInfo *SplitEditor::findReachingDefs(LiveInterval *LI, 40444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen MachineBasicBlock *KillMBB, 40544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SlotIndex Kill) { 40613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // Initialize the live-out cache the first time it is needed. 40713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LiveOutSeen.empty()) { 40813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen unsigned N = VRM.getMachineFunction().getNumBlockIDs(); 40913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutSeen.resize(N); 41013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutCache.resize(N); 41113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen } 41213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 413078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Blocks where LI should be live-in. 41444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB); 415e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 4168701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen // Remember if we have seen more than one value. 4178701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen bool UniqueVNI = true; 41844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen VNInfo *TheVNI = 0; 4198701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen 420078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. 42144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen for (unsigned i = 0; i != WorkList.size(); ++i) { 42244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen MachineBasicBlock *MBB = WorkList[i]; 4237cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen assert(!MBB->pred_empty() && "Value live-in to entry block?"); 424e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 425e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 426e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *Pred = *PI; 42713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutPair &LOP = LiveOutCache[Pred]; 42813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 429e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Is this a known live-out block? 43013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LiveOutSeen.test(Pred->getNumber())) { 43113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (VNInfo *VNI = LOP.first) { 43244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (TheVNI && TheVNI != VNI) 4338701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; 43444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen TheVNI = VNI; 4358701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } 436e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 4378701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen } 43813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 43913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // First time. LOP is garbage and must be cleared below. 44013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LiveOutSeen.set(Pred->getNumber()); 44113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 442e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Does Pred provide a live-out value? 4439763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen SlotIndex Start, Last; 4449763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred); 4459763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen Last = Last.getPrevSlot(); 44613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(Start, Last); 44713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP.first = VNI; 44813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (VNI) { 44913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP.second = MDT[LIS.getMBBFromIndex(VNI->def)]; 45044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (TheVNI && TheVNI != VNI) 4518701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen UniqueVNI = false; 45244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen TheVNI = VNI; 453e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 454e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 45513ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP.second = 0; 45613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 457e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // No, we need a live-in value for Pred as well 45844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Pred != KillMBB) 45944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen WorkList.push_back(Pred); 4608701768ae2e93e8741106acfa4a29959e1439487Jakob Stoklund Olesen else 46144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Loopback to KillMBB, so value is really live through. 46244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Kill = SlotIndex(); 4631407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 464e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 4651407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 46644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Transfer WorkList to LiveInBlocks in reverse order. 46744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This ordering works best with updateSSA(). 46844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInBlocks.clear(); 46944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInBlocks.reserve(WorkList.size()); 47044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen while(!WorkList.empty()) 47144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInBlocks.push_back(MDT[WorkList.pop_back_val()]); 4721c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 47344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The kill block may not be live-through. 47444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(LiveInBlocks.back().DomNode->getBlock() == KillMBB); 47544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInBlocks.back().Kill = Kill; 47644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 47744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen return UniqueVNI ? TheVNI : 0; 4781c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 4791c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 48044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesenvoid SplitEditor::updateSSA() { 481e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is essentially the same iterative algorithm that SSAUpdater uses, 482e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // except we already have a dominator tree, so we don't have to recompute it. 483e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen unsigned Changes; 484e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen do { 485e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen Changes = 0; 4861c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Propagate live-out values down the dominator tree, inserting phi-defs 48744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // when necessary. 48844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 48944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen E = LiveInBlocks.end(); I != E; ++I) { 49044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen MachineDomTreeNode *Node = I->DomNode; 49144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Skip block if the live-in value has already been determined. 49244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (!Node) 49344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 494e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineBasicBlock *MBB = Node->getBlock(); 495e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen MachineDomTreeNode *IDom = Node->getIDom(); 496e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveOutPair IDomValue; 49713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 498e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // We need a live-in value to a block with no immediate dominator? 499e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is probably an unreachable block that has survived somehow. 50013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen bool needPHI = !IDom || !LiveOutSeen.test(IDom->getBlock()->getNumber()); 501ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 50244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // IDom dominates all of our predecessors, but it may not be their 50344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // immediate dominator. Check if any of them have live-out values that are 50444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // properly dominated by IDom. If so, we need a phi-def here. 505e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!needPHI) { 50613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen IDomValue = LiveOutCache[IDom->getBlock()]; 507e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 508e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 509078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveOutPair Value = LiveOutCache[*PI]; 510e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (!Value.first || Value.first == IDomValue.first) 511e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen continue; 512e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This predecessor is carrying something other than IDomValue. 513e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // It could be because IDomValue hasn't propagated yet, or it could be 514e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // because MBB is in the dominance frontier of that value. 515078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen if (MDT.dominates(IDom, Value.second)) { 516e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen needPHI = true; 517e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen break; 518e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 519e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 520e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 521ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen 52244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The value may be live-through even if Kill is set, as can happen when 52344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // we are called from extendRange. In that case LiveOutSeen is true, and 52444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // LiveOutCache indicates a foreign or missing value. 52544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveOutPair &LOP = LiveOutCache[MBB]; 52644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 527e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Create a phi-def if required. 528e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen if (needPHI) { 529e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 530078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 53144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(Start); 53244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 533078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); 534e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen VNI->setIsPHIDef(true); 53544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen I->Value = VNI; 53644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This block is done, we know the final value. 53744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen I->DomNode = 0; 53844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (I->Kill.isValid()) 53944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LI->addRange(LiveRange(Start, I->Kill, VNI)); 54044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen else { 541078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); 54213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP = LiveOutPair(VNI, Node); 543e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 544e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } else if (IDomValue.first) { 54544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // No phi-def here. Remember incoming value. 54644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen I->Value = IDomValue.first; 54744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (I->Kill.isValid()) 54844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 549c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // Propagate IDomValue if needed: 550c94fcb1507db5c043558f3f58d389e774bc2f71dJakob Stoklund Olesen // MBB is live-out and doesn't define its own value. 55113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen if (LOP.second != Node && LOP.first != IDomValue.first) { 552e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen ++Changes; 55313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen LOP = IDomValue; 554e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } 555ff3ae8691c18c4c40d09fb21ecac880aea9a536bJakob Stoklund Olesen } 5561407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen } 557e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen } while (Changes); 5581407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 55944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The values in LiveInBlocks are now accurate. No more phi-defs are needed 56044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // for these blocks, so we can color the live ranges. 56144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen for (SmallVectorImpl<LiveInBlock>::iterator I = LiveInBlocks.begin(), 56244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen E = LiveInBlocks.end(); I != E; ++I) { 56344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (!I->DomNode) 56444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 56544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(I->Value && "No live-in value found"); 56644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen MachineBasicBlock *MBB = I->DomNode->getBlock(); 56744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(MBB); 56844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(Start); 56944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 57044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LI->addRange(LiveRange(Start, I->Kill.isValid() ? 57144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen I->Kill : LIS.getMBBEndIdx(MBB), I->Value)); 57244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 573670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen} 574670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 5750f43811903f10394f7088f4634c0b4f9668cbac0Eric ChristopherVNInfo *SplitEditor::defFromParent(unsigned RegIdx, 576cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 577cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 578cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 579cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I) { 580cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineInstr *CopyMI = 0; 581cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex Def; 582a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 583cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 584bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen // We may be trying to avoid interference that ends at a deleted instruction, 585bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen // so always begin RegIdx 0 early and all others late. 586bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen bool Late = RegIdx != 0; 587bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen 588cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Attempt cheap-as-a-copy rematerialization. 589cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 590a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { 591bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late); 592cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } else { 593cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Can't remat, just insert a copy from parent. 5940f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 595a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen .addReg(Edit->getReg()); 596bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) 597bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen .getDefIndex(); 598cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } 599cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 600cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Define the value in Reg. 601670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); 602cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNI->setCopy(CopyMI); 603cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen return VNI; 604cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen} 605cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 606f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen/// Create a new virtual register and live interval. 607e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesenunsigned SplitEditor::openIntv() { 6080f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the complement as index 0. 609a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->empty()) 6106a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->create(LIS, VRM); 6110f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 6120f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the open interval. 613a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen OpenIdx = Edit->size(); 6146a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->create(LIS, VRM); 615e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen return OpenIdx; 616e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen} 617e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 618e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesenvoid SplitEditor::selectIntv(unsigned Idx) { 619e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen assert(Idx != 0 && "Cannot select the complement interval"); 620e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen assert(Idx < Edit->size() && "Can only select previously opened interval"); 621e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen OpenIdx = Idx; 622f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 623f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 624207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 6250f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvBefore"); 6269b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " enterIntvBefore " << Idx); 627207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 628a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 629f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6309b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 631207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx; 632f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 633207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 634078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 635f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen assert(MI && "enterIntvBefore called with invalid index"); 636cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 637207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 638207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 639f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 640f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 641207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 6420f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 643207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(&MBB); 644207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex Last = End.getPrevSlot(); 645207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 646a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 647f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6489b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 649207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return End; 650f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 6519b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id); 652207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 653a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LIS.getLastSplitPoint(Edit->getParent(), &MBB)); 654207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen RegAssign.insert(VNI->def, End, OpenIdx); 6550f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 656207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 657f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 658f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 659078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// useIntv - indicate that all instructions in MBB should use OpenLI. 6607536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 661078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 662f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 663f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6647536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 6650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before useIntv"); 6660f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 6670f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, End, OpenIdx); 6680f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 669f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 670f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 671207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 6720f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 6739b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAfter " << Idx); 674f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 675f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen // The interval must be live beyond the instruction at Idx. 676cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 677a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 678f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6799b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 680207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx.getNextSlot(); 681f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 682207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 683f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 68401cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 68501cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen assert(MI && "No instruction at index"); 68601cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), 68701cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 688207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 689f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 690f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 6919b057771ba22441b8d312404204433477b4be657Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 6929b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 6939b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvBefore " << Idx); 6949b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6959b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen // The interval must be live into the instruction at Idx. 6969b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 697a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 6989b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!ParentVNI) { 6999b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 7009b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return Idx.getNextSlot(); 7019b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 7029b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 7039b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 7049b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 7059b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(MI && "No instruction at index"); 7069b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 7079b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return VNI->def; 7089b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen} 7099b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 710207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 7110f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 712078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(&MBB); 7139b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 7147536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 715a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 716f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 7179b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 718207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Start; 7197536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen } 7207536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 7210f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 722cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MBB.SkipPHIsAndLabels(MBB.begin())); 7230f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, VNI->def, OpenIdx); 7240f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 725207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 726f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 727f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 7285c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesenvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 7295c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before overlapIntv"); 730a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 731a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && 7325c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Parent changes value in extended range"); 7335c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 7345c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Range cannot span basic blocks"); 7355c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 736d3fdaeb69a25bcd21914b80f75606e2c2f1b35c8Jakob Stoklund Olesen // The complement interval will be extended as needed by extendRange(). 737b3dd82670aa60cacba81f090d292722c3ef44354Jakob Stoklund Olesen if (ParentVNI) 738b3dd82670aa60cacba81f090d292722c3ef44354Jakob Stoklund Olesen markComplexMapped(0, ParentVNI); 7395c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 7405c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen RegAssign.insert(Start, End, OpenIdx); 7415c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dump()); 7425c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen} 7435c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 74444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen/// transferValues - Transfer all possible values to the new live ranges. 74544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen/// Values that were rematerialized are left alone, they need extendRange(). 74644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesenbool SplitEditor::transferValues() { 7474670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Skipped = false; 74844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInBlocks.clear(); 7494670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegAssignMap::const_iterator AssignI = RegAssign.begin(); 750a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 751a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 7524670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " blit " << *ParentI << ':'); 7534670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen VNInfo *ParentVNI = ParentI->valno; 7544670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // RegAssign has holes where RegIdx 0 should be used. 7554670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex Start = ParentI->start; 7564670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen AssignI.advanceTo(Start); 7574670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen do { 7584670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen unsigned RegIdx; 7594670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex End = ParentI->end; 7604670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (!AssignI.valid()) { 7614670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 7624670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else if (AssignI.start() <= Start) { 7634670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = AssignI.value(); 7644670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (AssignI.stop() < End) { 7654670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = AssignI.stop(); 7664670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++AssignI; 7674670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 7684670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else { 7694670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 7704670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = std::min(End, AssignI.start()); 7714670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 77244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 77344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 7744670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 77544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 77644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 77744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Check for a simply defined value that can be blitted directly. 7784670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { 7794670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id); 78044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LI->addRange(LiveRange(Start, End, VNI)); 78144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Start = End; 78244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 78344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 78444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 78544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Skip rematerialized values, we need to use extendRange() and 78644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // extendPHIKillRanges() to completely recompute the live ranges. 78744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) { 78844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << "(remat)"); 7894670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Skipped = true; 79044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Start = End; 79144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 79244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 79344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 79444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Initialize the live-out cache the first time it is needed. 79544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (LiveOutSeen.empty()) { 79644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen unsigned N = VRM.getMachineFunction().getNumBlockIDs(); 79744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveOutSeen.resize(N); 79844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveOutCache.resize(N); 79944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 80044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 80144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This value has multiple defs in RegIdx, but it wasn't rematerialized, 80244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // so the live range is accurate. Add live-in blocks in [Start;End) to the 80344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // LiveInBlocks. 80444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 80544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SlotIndex BlockStart, BlockEnd; 80644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 80744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 80844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The first block may be live-in, or it may have its own def. 80944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Start != BlockStart) { 81044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(BlockStart, 81144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen std::min(BlockEnd, End).getPrevSlot()); 81244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(VNI && "Missing def for complex mapped value"); 81344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 81444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // MBB has its own def. Is it also live-out? 81544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (BlockEnd <= End) { 81644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveOutSeen.set(MBB->getNumber()); 81744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]); 81844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 81944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Skip to the next block for live-in. 82044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen ++MBB; 82144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockStart = BlockEnd; 82244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 82344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 82444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Handle the live-in blocks covered by [Start;End). 82544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(Start <= BlockStart && "Expected live-in block"); 82644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen while (BlockStart < End) { 82744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 82844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockEnd = LIS.getMBBEndIdx(MBB); 82944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (BlockStart == ParentVNI->def) { 83044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This block has the def of a parent PHI, so it isn't live-in. 83144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 83244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(BlockStart, 83344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen std::min(BlockEnd, End).getPrevSlot()); 83444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(VNI && "Missing def for complex mapped parent PHI"); 83544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (End >= BlockEnd) { 83644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Live-out as well. 83744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveOutSeen.set(MBB->getNumber()); 83844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveOutCache[MBB] = LiveOutPair(VNI, MDT[MBB]); 83944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 84044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } else { 84144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This block needs a live-in value. 84244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInBlocks.push_back(MDT[MBB]); 84344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The last block covered may not be live-out. 84444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (End < BlockEnd) 84544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInBlocks.back().Kill = End; 84644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen else { 84744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Live-out, but we need updateSSA to tell us the value. 84844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveOutSeen.set(MBB->getNumber()); 849cbc5f407eff618225a2fd4363f67d660607e6c2dFrancois Pichet LiveOutCache[MBB] = LiveOutPair((VNInfo*)0, 850cbc5f407eff618225a2fd4363f67d660607e6c2dFrancois Pichet (MachineDomTreeNode*)0); 85144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 85244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 85344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockStart = BlockEnd; 85444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen ++MBB; 85544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 8564670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Start = End; 8574670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } while (Start != ParentI->end); 8584670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 8594670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 86044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 86144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (!LiveInBlocks.empty()) 86244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen updateSSA(); 86344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 8644670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen return Skipped; 8654670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen} 8664670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 867e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesenvoid SplitEditor::extendPHIKillRanges() { 868e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // Extend live ranges to be live-out for successor PHI values. 869a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 870a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 871e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen const VNInfo *PHIVNI = *I; 872e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 873e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen continue; 874e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 875e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 876e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 877e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 878e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); 879e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // The predecessor may not have a live-out value. That is OK, like an 880e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // undef PHI operand. 881a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->getParent().liveAt(End)) { 882e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen assert(RegAssign.lookup(End) == RegIdx && 883e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen "Different register assignment in phi predecessor"); 884e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen extendRange(RegIdx, End); 885e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 886e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 887e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 888e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen} 889e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 890a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 8914670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenvoid SplitEditor::rewriteAssigned(bool ExtendRanges) { 892a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 893078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 8947466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineOperand &MO = RI.getOperand(); 8957466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 8967466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen ++RI; 8970f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // LiveDebugVariables should have handled all DBG_VALUE instructions. 8987466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen if (MI->isDebugValue()) { 8997466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen DEBUG(dbgs() << "Zapping " << *MI); 9007466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MO.setReg(0); 9017466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen continue; 9027466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 903a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 904a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // <undef> operands don't really read the register, so just assign them to 905a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen // the complement. 906a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen if (MO.isUse() && MO.isUndef()) { 907a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen MO.setReg(Edit->get(0)->reg); 908a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen continue; 909a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen } 910a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 911078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI); 9127cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (MO.isDef()) 9137cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex(); 9140f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 9150f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite to the mapped register at Idx. 9160f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned RegIdx = RegAssign.lookup(Idx); 917a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen MO.setReg(Edit->get(RegIdx)->reg); 9180f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 9190f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':' << RegIdx << '\t' << *MI); 9200f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 9217cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Extend liveness to Idx if the instruction reads reg. 9227cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!ExtendRanges) 9237cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 9247cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 9257cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Skip instructions that don't read Reg. 9267cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (MO.isDef()) { 9277cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!MO.getSubReg() && !MO.isEarlyClobber()) 9287cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 9297cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // We may wan't to extend a live range for a partial redef, or for a use 9307cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // tied to an early clobber. 9317cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getPrevSlot(); 9327cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!Edit->getParent().liveAt(Idx)) 9337cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 9347cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen } else 9357cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getUseIndex(); 9367cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 9377cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen extendRange(RegIdx, Idx); 9387466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 9397466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen} 9407466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 9415881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesenvoid SplitEditor::deleteRematVictims() { 9425881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen SmallVector<MachineInstr*, 8> Dead; 9432dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 9442dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen LiveInterval *LI = *I; 9452dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 9462dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen LII != LIE; ++LII) { 9472dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen // Dead defs end at the store slot. 9482dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen if (LII->end != LII->valno->def.getNextSlot()) 9492dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 9502dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 9512dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen assert(MI && "Missing instruction for dead def"); 9522dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MI->addRegisterDead(LI->reg, &TRI); 9535881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 9542dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen if (!MI->allDefsAreDead()) 9552dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 9565881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 9572dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << *MI); 9582dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen Dead.push_back(MI); 9592dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen } 9605881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen } 9615881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 9625881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (Dead.empty()) 9635881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen return; 9645881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 9656a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); 9665881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen} 9675881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 9685928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesenvoid SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 9694670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumFinished; 9700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 9710f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // At this point, the live intervals in Edit contain VNInfos corresponding to 9720f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // the inserted copies. 9730f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 9740f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Add the original defs from the parent interval. 975a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 976a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 9770f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *ParentVNI = *I; 9789ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (ParentVNI->isUnused()) 9799ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen continue; 980670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 98129ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 98229ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNI->setIsPHIDef(ParentVNI->isPHIDef()); 98329ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNI->setCopy(ParentVNI->getCopy()); 98429ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen 9854670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Mark rematted values as complex everywhere to force liveness computation. 9864670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // The new live ranges may be truncated. 987a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 988a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 9894670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen markComplexMapped(i, ParentVNI); 9905fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 991c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 9920f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#ifndef NDEBUG 9930f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Every new interval must have a def by now, otherwise the split is bogus. 994a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 9950f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); 9960f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#endif 9970f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 99844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Transfer the simply mapped values, check if any are skipped. 99944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen bool Skipped = transferValues(); 100044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Skipped) 10014670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen extendPHIKillRanges(); 10024670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen else 10034670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumSimple; 10044670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 10054670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Rewrite virtual registers, possibly extending ranges. 100644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen rewriteAssigned(Skipped); 1007463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher 10085881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Delete defs that were rematted everywhere. 100944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Skipped) 10105881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen deleteRematVictims(); 10115fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 10120253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Get rid of unused values and set phi-kill flags. 1013a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 1014078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen (*I)->RenumberValues(LIS); 10150253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 10165928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Provide a reverse mapping from original indices to Edit ranges. 10175928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRMap) { 10185928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->clear(); 10195928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 10205928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->push_back(i); 10215928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 10225928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10233a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Now check if any registers were separated into multiple components. 1024078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 1025a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 10263a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Don't use iterators, they are invalidated by create() below. 1027a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *li = Edit->get(i); 10283a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen unsigned NumComp = ConEQ.Classify(li); 10293a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen if (NumComp <= 1) 10303a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen continue; 10313a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 10323a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> dups; 10333a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen dups.push_back(li); 1034ae5fbeec23cff833cad9e6b2a638efd1f48bef49Matt Beaumont-Gay for (unsigned j = 1; j != NumComp; ++j) 10356a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen dups.push_back(&Edit->create(LIS, VRM)); 10362254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen ConEQ.Distribute(&dups[0], MRI); 10375928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // The new intervals all map back to i. 10385928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRMap) 10395928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->resize(Edit->size(), i); 10403a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen } 10413a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen 104208e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen // Calculate spill weight and allocation hints for new intervals. 10436094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops); 10445928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10455928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen assert(!LRMap || LRMap->size() == Edit->size()); 1046f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 1047f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 1048f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 10498ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1050f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen// Single Block Splitting 1051f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1052f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 1053078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it 1054078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// may be an advantage to split CurLI for the duration of the block. 10552bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesenbool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 1056078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // If CurLI is local to one block, there is no point to splitting it. 1057db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (UseBlocks.size() <= 1) 10582bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return false; 10592bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen // Add blocks with multiple uses. 1060db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0, e = UseBlocks.size(); i != e; ++i) { 1061db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const BlockInfo &BI = UseBlocks[i]; 1062db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen if (BI.FirstUse == BI.LastUse) 10639b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen continue; 10649b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen Blocks.insert(BI.MBB); 10659b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 10662bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen return !Blocks.empty(); 10672bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen} 10682bfb32468404eb68dcc1b69a34336794b20e3f33Jakob Stoklund Olesen 1069fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 1070fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen openIntv(); 1071fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 1072fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstUse, 1073fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen LastSplitPoint)); 1074fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastUse < LastSplitPoint) { 1075fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen useIntv(SegStart, leaveIntvAfter(BI.LastUse)); 1076fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } else { 1077fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // The last use is after the last valid split point. 1078fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 1079fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen useIntv(SegStart, SegStop); 1080fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen overlapIntv(SegStop, BI.LastUse); 1081fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 1082fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen} 1083fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 1084078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// splitSingleBlocks - Split CurLI into a separate live interval inside each 108557d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen/// basic block in Blocks. 108657d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 1087e1f543fbb338ea80cdac021fcb09230ad86896c6Jakob Stoklund Olesen DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 1088db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA.getUseBlocks(); 1089db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1090db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1091fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen if (Blocks.count(BI.MBB)) 1092fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen splitSingleBlock(BI); 1093f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 10947466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen finish(); 1095f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 1096