SplitKit.cpp revision 789d5d85ba6e9259a8e0f0bcfbd06a59ad164512
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" 17f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "VirtRegMap.h" 184670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 21d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 22f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 23c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/Debug.h" 268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 276a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 286a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenusing namespace llvm; 318ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 324670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund OlesenSTATISTIC(NumFinished, "Number of splits finished"); 334670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund OlesenSTATISTIC(NumSimple, "Number of splits that were simple"); 34e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumCopies, "Number of copies inserted for splitting"); 35e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumRemats, "Number of rematerialized defs for splitting"); 36bdda37d7fbafe6876f248341837423a4100f95a5Jakob Stoklund OlesenSTATISTIC(NumRepairs, "Number of invalid live ranges repaired"); 374670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 388ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 398ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// Split Analysis 408ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 418ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 421b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund OlesenSplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, 43f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const LiveIntervals &lis, 44f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli) 451b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen : MF(vrm.getMachineFunction()), 461b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen VRM(vrm), 47078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LIS(lis), 48078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen Loops(mli), 491b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen TII(*MF.getTarget().getInstrInfo()), 501a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen CurLI(0), 511a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LastSplitPoint(MF.getNumBlockIDs()) {} 528ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 538ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::clear() { 54b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen UseSlots.clear(); 55db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.clear(); 56db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ThroughBlocks.clear(); 57078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = 0; 587d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen DidRepairRange = false; 598ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 608ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 611a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund OlesenSlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { 621a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen const MachineBasicBlock *MBB = MF.getBlockNumbered(Num); 631a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor(); 641a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num]; 652aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen SlotIndex MBBEnd = LIS.getMBBEndIdx(MBB); 661a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 671a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // Compute split points on the first call. The pair is independent of the 681a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // current live interval. 691a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (!LSP.first.isValid()) { 701a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator(); 711a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (FirstTerm == MBB->end()) 722aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen LSP.first = MBBEnd; 731a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen else 741a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.first = LIS.getInstructionIndex(FirstTerm); 751a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 761a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // If there is a landing pad successor, also find the call instruction. 771a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (!LPad) 781a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.first; 791a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // There may not be a call instruction (?) in which case we ignore LPad. 801a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.second = LSP.first; 811e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin(); 821e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen I != E;) { 831e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen --I; 845a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (I->isCall()) { 851a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen LSP.second = LIS.getInstructionIndex(I); 861a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen break; 871a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 881e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen } 891a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 901a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 911a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // If CurLI is live into a landing pad successor, move the last split point 921a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // back to the call that may throw. 932aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen if (!LPad || !LSP.second || !LIS.isLiveInToMBB(*CurLI, LPad)) 941a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LSP.first; 952aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen 962aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // Find the value leaving MBB. 972aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen const VNInfo *VNI = CurLI->getVNInfoBefore(MBBEnd); 982aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen if (!VNI) 992aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen return LSP.first; 1002aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen 1012aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // If the value leaving MBB was defined after the call in MBB, it can't 1022aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // really be live-in to the landing pad. This can happen if the landing pad 1032aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // has a PHI, and this register is undef on the exceptional edge. 1042aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // <rdar://problem/10664933> 1052aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen if (!SlotIndex::isEarlierInstr(VNI->def, LSP.second) && VNI->def < MBBEnd) 1062aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen return LSP.first; 1072aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen 1082aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // Value is properly live-in to the landing pad. 1092aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // Only allow splits before the call. 1102aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen return LSP.second; 1116a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen} 1126a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 11374c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund OlesenMachineBasicBlock::iterator 11474c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund OlesenSplitAnalysis::getLastSplitPointIter(MachineBasicBlock *MBB) { 11574c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen SlotIndex LSP = getLastSplitPoint(MBB->getNumber()); 11674c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen if (LSP == LIS.getMBBEndIdx(MBB)) 11774c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen return MBB->end(); 11874c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen return LIS.getInstructionFromIndex(LSP); 11974c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen} 12074c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen 121078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 122abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesenvoid SplitAnalysis::analyzeUses() { 123a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen assert(UseSlots.empty() && "Call clear first"); 124a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 125a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // First get all the defs from the interval values. This provides the correct 126a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // slots for early clobbers. 127a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(), 128a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen E = CurLI->vni_end(); I != E; ++I) 129a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen if (!(*I)->isPHIDef() && !(*I)->isUnused()) 130a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.push_back((*I)->def); 131a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 132a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // Get use slots form the use-def chain. 133078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineRegisterInfo &MRI = MF.getRegInfo(); 134a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen for (MachineRegisterInfo::use_nodbg_iterator 135a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E; 136a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen ++I) 137a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen if (!I.getOperand().isUndef()) 1382debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen UseSlots.push_back(LIS.getInstructionIndex(&*I).getRegSlot()); 139a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 140b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen array_pod_sort(UseSlots.begin(), UseSlots.end()); 1412b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 142a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // Remove duplicates, keeping the smaller slot for each instruction. 143a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // That is what we want for early clobbers. 144a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), 145a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen SlotIndex::isSameInstr), 146a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.end()); 147a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 1482b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // Compute per-live block info. 1492b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen if (!calcLiveBlockInfo()) { 1502b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // FIXME: calcLiveBlockInfo found inconsistencies in the live range. 1515b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola // I am looking at you, RegisterCoalescer! 1527d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen DidRepairRange = true; 153bdda37d7fbafe6876f248341837423a4100f95a5Jakob Stoklund Olesen ++NumRepairs; 1542b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); 1552b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen const_cast<LiveIntervals&>(LIS) 1562b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen .shrinkToUses(const_cast<LiveInterval*>(CurLI)); 157db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.clear(); 158db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ThroughBlocks.clear(); 1592b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen bool fixed = calcLiveBlockInfo(); 1602b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen (void)fixed; 1612b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen assert(fixed && "Couldn't fix broken live interval"); 1622b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen } 1632b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 164ef1f5ccca7efaa18209523b31019d356d302f635Jakob Stoklund Olesen DEBUG(dbgs() << "Analyze counted " 165db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen << UseSlots.size() << " instrs in " 166db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen << UseBlocks.size() << " blocks, through " 167f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen << NumThroughBlocks << " blocks.\n"); 1688ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 1698ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 170f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 171f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// where CurLI is live. 1722b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesenbool SplitAnalysis::calcLiveBlockInfo() { 173f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ThroughBlocks.resize(MF.getNumBlockIDs()); 174a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen NumThroughBlocks = NumGapBlocks = 0; 175f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (CurLI->empty()) 1762b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 177f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 178f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVI = CurLI->begin(); 179f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVE = CurLI->end(); 180f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 181f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 182f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseI = UseSlots.begin(); 183f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseE = UseSlots.end(); 184f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 185f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Loop over basic blocks where CurLI is live. 186f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); 187f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (;;) { 188f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BlockInfo BI; 189f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BI.MBB = MFI; 1906c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex Start, Stop; 1916c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 192f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 193a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // If the block contains no uses, the range must be live through. At one 1945b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola // point, RegisterCoalescer could create dangling ranges that ended 195a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // mid-block. 196a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (UseI == UseE || *UseI >= Stop) { 197a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen ++NumThroughBlocks; 198a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen ThroughBlocks.set(BI.MBB->getNumber()); 199a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // The range shouldn't end mid-block if there are no uses. This shouldn't 200a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // happen. 201a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (LVI->end < Stop) 202a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen return false; 203a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } else { 204a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // This block has uses. Find the first and last uses in the block. 205fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.FirstInstr = *UseI; 206fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen assert(BI.FirstInstr >= Start); 207f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen do ++UseI; 2086c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen while (UseI != UseE && *UseI < Stop); 209fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LastInstr = UseI[-1]; 210fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen assert(BI.LastInstr < Stop); 211f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 212a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // LVI is the first live segment overlapping MBB. 213a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveIn = LVI->start <= Start; 214a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen 21577ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen // When not live in, the first use should be a def. 21677ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen if (!BI.LiveIn) { 21777ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen assert(LVI->start == LVI->valno->def && "Dangling LiveRange start"); 218fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen assert(LVI->start == BI.FirstInstr && "First instr should be a def"); 219fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.FirstDef = BI.FirstInstr; 22077ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen } 22177ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen 222a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // Look for gaps in the live range. 223a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = true; 224a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen while (LVI->end < Stop) { 225a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SlotIndex LastStop = LVI->end; 226a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (++LVI == LVE || LVI->start >= Stop) { 227a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = false; 228fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LastInstr = LastStop; 229a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen break; 230a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } 23177ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen 232a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (LastStop < LVI->start) { 233a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // There is a gap in the live range. Create duplicate entries for the 234a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // live-in snippet and the live-out snippet. 235a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen ++NumGapBlocks; 236a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen 237a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // Push the Live-in part. 238a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = false; 239a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen UseBlocks.push_back(BI); 240fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen UseBlocks.back().LastInstr = LastStop; 241a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen 242a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // Set up BI for the live-out part. 243a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveIn = false; 244a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = true; 245fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.FirstInstr = BI.FirstDef = LVI->start; 246a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } 24777ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen 24877ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen // A LiveRange that starts in the middle of the block must be a def. 24977ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen assert(LVI->start == LVI->valno->def && "Dangling LiveRange start"); 25077ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen if (!BI.FirstDef) 25177ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen BI.FirstDef = LVI->start; 252f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 253f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 254db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.push_back(BI); 255626d6fb1903e74337b257c5e165944bcd1273e65Jakob Stoklund Olesen 256a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // LVI is now at LVE or LVI->end >= Stop. 257a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (LVI == LVE) 258a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen break; 259a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } 260f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 261f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Live segment ends exactly at Stop. Move to the next segment. 2626c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (LVI->end == Stop && ++LVI == LVE) 263f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 264f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 265f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Pick the next basic block. 2666c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (LVI->start < Stop) 267f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen ++MFI; 268f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 269f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MFI = LIS.getMBBFromIndex(LVI->start); 270f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 271b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen 272b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count"); 2732b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 274f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen} 275f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 2769f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesenunsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { 2779f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (cli->empty()) 2789f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen return 0; 2799f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval *li = const_cast<LiveInterval*>(cli); 2809f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval::iterator LVI = li->begin(); 2819f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval::iterator LVE = li->end(); 2829f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen unsigned Count = 0; 2839f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 2849f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Loop over basic blocks where li is live. 2859f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start); 2869f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen SlotIndex Stop = LIS.getMBBEndIdx(MFI); 2879f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen for (;;) { 2889f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen ++Count; 2899f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LVI = li->advanceTo(LVI, Stop); 2909f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (LVI == LVE) 2919f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen return Count; 2929f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen do { 2939f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen ++MFI; 2949f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen Stop = LIS.getMBBEndIdx(MFI); 2959f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } while (Stop <= LVI->start); 2969f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 2979f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen} 2989f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 29906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesenbool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 30006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen unsigned OrigReg = VRM.getOriginal(CurLI->reg); 30106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen const LiveInterval &Orig = LIS.getInterval(OrigReg); 30206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen assert(!Orig.empty() && "Splitting empty interval?"); 30306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen LiveInterval::const_iterator I = Orig.find(Idx); 30406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 30506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range containing Idx should begin at Idx. 30606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen if (I != Orig.end() && I->start <= Idx) 30706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I->start == Idx; 30806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 30906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range does not contain Idx, previous must end at Idx. 31006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I != Orig.begin() && (--I)->end == Idx; 31106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen} 31206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 3138ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::analyze(const LiveInterval *li) { 3148ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen clear(); 315078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = li; 316abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen analyzeUses(); 3178ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 3188ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 319697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen 320f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 3211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen// Split Editor 3221407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 3231407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3241c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 3251c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenSplitEditor::SplitEditor(SplitAnalysis &sa, 3261c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveIntervals &lis, 3271c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VirtRegMap &vrm, 328bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen MachineDominatorTree &mdt) 3291c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen : SA(sa), LIS(lis), VRM(vrm), 3301c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MRI(vrm.getMachineFunction().getRegInfo()), 3311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MDT(mdt), 3321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 3331c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 334bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Edit(0), 3351c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen OpenIdx(0), 336708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SpillMode(SM_Partition), 3371c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen RegAssign(Allocator) 338bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen{} 339bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 340708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesenvoid SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { 341708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen Edit = &LRE; 342708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SpillMode = SM; 343bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen OpenIdx = 0; 344bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen RegAssign.clear(); 345bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Values.clear(); 346c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen 347c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen // Reset the LiveRangeCalc instances needed for this spill mode. 348c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRCalc[0].reset(&VRM.getMachineFunction()); 349c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen if (SpillMode) 350c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRCalc[1].reset(&VRM.getMachineFunction()); 351bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 3521c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // We don't need an AliasAnalysis since we will only be performing 3531c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // cheap-as-a-copy remats anyway. 3548a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->anyRematerializable(0); 3551c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 3561c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3571c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::dump() const { 3581c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (RegAssign.empty()) { 3591c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " empty\n"; 3601c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 3611c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3621c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3631c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 3641c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 3651c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << '\n'; 366b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen} 367b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen 3681c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::defValue(unsigned RegIdx, 3691c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const VNInfo *ParentVNI, 3701c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx) { 3711c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 3721c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 373a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 374a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 3751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3761c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Create a new value. 3773b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator()); 3781c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3791c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Use insert for lookup, so we can add missing values with a second lookup. 3801c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen std::pair<ValueMap::iterator, bool> InsP = 381393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), 382393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen ValueForcePair(VNI, false))); 3831c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3841c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was the first time (RegIdx, ParentVNI) was mapped. 3851c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Keep it as a simple def without any liveness. 3861c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (InsP.second) 3871c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 3881c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3891c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // If the previous value was a simple mapping, add liveness for it now. 390393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (VNInfo *OldVNI = InsP.first->second.getPointer()) { 3911c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = OldVNI->def; 3921f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getDeadSlot(), OldVNI)); 393393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // No longer a simple mapping. Switch to a complex, non-forced mapping. 394393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen InsP.first->second = ValueForcePair(); 3951c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3961c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3971c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is a complex mapping, add liveness for VNI 3981c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 3991f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen LI->addRange(LiveRange(Def, Def.getDeadSlot(), VNI)); 4001c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 4029ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen} 4039ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 404393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesenvoid SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) { 4051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 406393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)]; 407393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen VNInfo *VNI = VFP.getPointer(); 4081c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 409393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // ParentVNI was either unmapped or already complex mapped. Either way, just 410393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // set the force bit. 411393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (!VNI) { 412393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen VFP.setInt(true); 4131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 414393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen } 4151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was previously a single mapping. Make sure the old def is represented 4171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by a trivial live range. 4181c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 4191f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getDeadSlot(), VNI)); 420393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // Mark as complex mapped, forced. 421393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen VFP = ValueForcePair(0, true); 422e5a2e366322ef5f0d597b1fb8dbf55f2cf36cf15Jakob Stoklund Olesen} 423e5a2e366322ef5f0d597b1fb8dbf55f2cf36cf15Jakob Stoklund Olesen 4240f43811903f10394f7088f4634c0b4f9668cbac0Eric ChristopherVNInfo *SplitEditor::defFromParent(unsigned RegIdx, 425cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 426cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 427cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 428cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I) { 429cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineInstr *CopyMI = 0; 430cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex Def; 431a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 432cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 433bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen // We may be trying to avoid interference that ends at a deleted instruction, 434bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen // so always begin RegIdx 0 early and all others late. 435bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen bool Late = RegIdx != 0; 436bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen 437cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Attempt cheap-as-a-copy rematerialization. 438cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 4398a06af96698537377275dd7848db69915638dd26Pete Cooper if (Edit->canRematerializeAt(RM, UseIdx, true)) { 4408a06af96698537377275dd7848db69915638dd26Pete Cooper Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late); 441e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumRemats; 442cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } else { 443cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Can't remat, just insert a copy from parent. 4440f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 445a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen .addReg(Edit->getReg()); 446bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) 4472debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen .getRegSlot(); 448e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumCopies; 449cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } 450cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 451cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Define the value in Reg. 4523b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen return defValue(RegIdx, ParentVNI, Def); 453cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen} 454cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 455f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen/// Create a new virtual register and live interval. 456e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesenunsigned SplitEditor::openIntv() { 4570f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the complement as index 0. 458a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->empty()) 4598a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->create(); 4600f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 4610f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the open interval. 462a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen OpenIdx = Edit->size(); 4638a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->create(); 464e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen return OpenIdx; 465e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen} 466e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 467e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesenvoid SplitEditor::selectIntv(unsigned Idx) { 468e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen assert(Idx != 0 && "Cannot select the complement interval"); 469e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen assert(Idx < Edit->size() && "Can only select previously opened interval"); 47087360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); 471e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen OpenIdx = Idx; 472f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 473f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 474207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 4750f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvBefore"); 4769b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " enterIntvBefore " << Idx); 477207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 478a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 479f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 4809b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 481207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx; 482f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 483207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 484078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 485f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen assert(MI && "enterIntvBefore called with invalid index"); 486cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 487207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 488207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 489f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 490f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 49187360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { 49287360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before enterIntvAfter"); 49387360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAfter " << Idx); 49487360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 49587360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 49687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen if (!ParentVNI) { 49787360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 49887360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen return Idx; 49987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen } 50087360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 50187360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 50287360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen assert(MI && "enterIntvAfter called with invalid index"); 50387360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen 50487360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), 50587360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 50687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen return VNI->def; 50787360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen} 50887360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen 509207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 5100f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 511207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(&MBB); 512207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex Last = End.getPrevSlot(); 513207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 514a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 515f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5169b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 517207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return End; 518f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 5199b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id); 520207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 52174c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen SA.getLastSplitPointIter(&MBB)); 522207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen RegAssign.insert(VNI->def, End, OpenIdx); 5230f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 524207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 525f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 526f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 527078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// useIntv - indicate that all instructions in MBB should use OpenLI. 5287536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 529078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 530f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 531f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 5327536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 5330f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before useIntv"); 5340f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 5350f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, End, OpenIdx); 5360f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 537f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 538f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 539207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 5400f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 5419b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAfter " << Idx); 542f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 543f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen // The interval must be live beyond the instruction at Idx. 544ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen SlotIndex Boundary = Idx.getBoundaryIndex(); 545ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary); 546f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5479b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 548ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen return Boundary.getNextSlot(); 549f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 550207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 551ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Boundary); 55201cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen assert(MI && "No instruction at index"); 553ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen 554ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // In spill mode, make live ranges as short as possible by inserting the copy 555ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // before MI. This is only possible if that instruction doesn't redefine the 556ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // value. The inserted COPY is not a kill, and we don't need to recompute 557ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // the source live range. The spiller also won't try to hoist this copy. 558ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) && 559ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen MI->readsVirtualRegister(Edit->getReg())) { 560ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen forceRecompute(0, ParentVNI); 561ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 562ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen return Idx; 563ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen } 564ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen 565ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(), 56601cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 567207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 568f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 569f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 5709b057771ba22441b8d312404204433477b4be657Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 5719b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 5729b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvBefore " << Idx); 5739b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 5749b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen // The interval must be live into the instruction at Idx. 575fc47933db5c8fea9bc89470d83cc5af7ca36f2a3Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 576a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 5779b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!ParentVNI) { 5789b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 5799b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return Idx.getNextSlot(); 5809b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 5819b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 5829b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 5839b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 5849b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(MI && "No instruction at index"); 5859b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 5869b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return VNI->def; 5879b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen} 5889b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 589207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 5900f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 591078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(&MBB); 5929b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 5937536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 594a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 595f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5969b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 597207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Start; 5987536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen } 5997536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6000f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 601cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MBB.SkipPHIsAndLabels(MBB.begin())); 6020f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, VNI->def, OpenIdx); 6030f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 604207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 605f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 606f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6075c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesenvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 6085c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before overlapIntv"); 609a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 610194eb71a11a77c7fb576780783a77e64924dfb10Jakob Stoklund Olesen assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) && 6115c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Parent changes value in extended range"); 6125c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 6135c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Range cannot span basic blocks"); 6145c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 615abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen // The complement interval will be extended as needed by LRCalc.extend(). 616b3dd82670aa60cacba81f090d292722c3ef44354Jakob Stoklund Olesen if (ParentVNI) 617393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(0, ParentVNI); 6185c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 6195c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen RegAssign.insert(Start, End, OpenIdx); 6205c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dump()); 6215c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen} 6225c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 623b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen//===----------------------------------------------------------------------===// 624b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen// Spill modes 625b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen//===----------------------------------------------------------------------===// 626b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 627b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesenvoid SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) { 628b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen LiveInterval *LI = Edit->get(0); 629b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n"); 630b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen RegAssignMap::iterator AssignI; 631b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen AssignI.setMap(RegAssign); 632b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 633b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 634b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *VNI = Copies[i]; 635b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SlotIndex Def = VNI->def; 636b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Def); 637b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen assert(MI && "No instruction for back-copy"); 638b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 639b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock *MBB = MI->getParent(); 640b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock::iterator MBBI(MI); 641b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen bool AtBegin; 642b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen do AtBegin = MBBI == MBB->begin(); 643b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen while (!AtBegin && (--MBBI)->isDebugValue()); 644b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 645b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Removing " << Def << '\t' << *MI); 646b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen LI->removeValNo(VNI); 647b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen LIS.RemoveMachineInstrFromMaps(MI); 648b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MI->eraseFromParent(); 649b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 650b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Adjust RegAssign if a register assignment is killed at VNI->def. We 651b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // want to avoid calculating the live range of the source register if 652b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // possible. 653b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen AssignI.find(VNI->def.getPrevSlot()); 654b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!AssignI.valid() || AssignI.start() >= Def) 655b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 656b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // If MI doesn't kill the assigned register, just leave it. 657b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (AssignI.stop() != Def) 658b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 659b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen unsigned RegIdx = AssignI.value(); 660b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) { 661b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx << '\n'); 662393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def)); 663b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } else { 6642debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex Kill = LIS.getInstructionIndex(MBBI).getRegSlot(); 665b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI); 666b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen AssignI.setStop(Kill); 667b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 668b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 669b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen} 670b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 671c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund OlesenMachineBasicBlock* 672c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund OlesenSplitEditor::findShallowDominator(MachineBasicBlock *MBB, 673c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *DefMBB) { 674c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (MBB == DefMBB) 675c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return MBB; 676c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def."); 677c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 678c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen const MachineLoopInfo &Loops = SA.Loops; 679c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB); 680c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineDomTreeNode *DefDomNode = MDT[DefMBB]; 681c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 682c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Best candidate so far. 683c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *BestMBB = MBB; 684c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen unsigned BestDepth = UINT_MAX; 685c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 686c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen for (;;) { 687c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen const MachineLoop *Loop = Loops.getLoopFor(MBB); 688c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 689c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // MBB isn't in a loop, it doesn't get any better. All dominators have a 690c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // higher frequency by definition. 691c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (!Loop) { 692c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 693c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen << MBB->getNumber() << " at depth 0\n"); 694c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return MBB; 695c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 696c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 697c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // We'll never be able to exit the DefLoop. 698c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (Loop == DefLoop) { 699c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 700c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen << MBB->getNumber() << " in the same loop\n"); 701c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return MBB; 702c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 703c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 704c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Least busy dominator seen so far. 705c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen unsigned Depth = Loop->getLoopDepth(); 706c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (Depth < BestDepth) { 707c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen BestMBB = MBB; 708c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen BestDepth = Depth; 709c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 710c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen << MBB->getNumber() << " at depth " << Depth << '\n'); 711c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 712c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 713c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Leave loop by going to the immediate dominator of the loop header. 714c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // This is a bigger stride than simply walking up the dominator tree. 715c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom(); 716c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 717c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Too far up the dominator tree? 718c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (!IDom || !MDT.dominates(DefDomNode, IDom)) 719c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return BestMBB; 720c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 721c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MBB = IDom->getBlock(); 722c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 723c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen} 724c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 725b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesenvoid SplitEditor::hoistCopiesForSize() { 726b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Get the complement interval, always RegIdx 0. 727b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen LiveInterval *LI = Edit->get(0); 728b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen LiveInterval *Parent = &Edit->getParent(); 729b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 730b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Track the nearest common dominator for all back-copies for each ParentVNI, 731b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // indexed by ParentVNI->id. 732b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair; 733b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums()); 734b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 735b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Find the nearest common dominator for parent values with multiple 736b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // back-copies. If a single back-copy dominates, put it in DomPair.second. 737b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end(); 738b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VI != VE; ++VI) { 739b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *VNI = *VI; 740b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); 741b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen assert(ParentVNI && "Parent not live at complement def"); 742b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 743b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Don't hoist remats. The complement is probably going to disappear 744b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // completely anyway. 745b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 746b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 747b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 748b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def); 749b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DomPair &Dom = NearestDom[ParentVNI->id]; 750b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 751b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Keep directly defined parent values. This is either a PHI or an 752b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // instruction in the complement range. All other copies of ParentVNI 753b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // should be eliminated. 754b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (VNI->def == ParentVNI->def) { 755b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n'); 756b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(ValMBB, VNI->def); 757b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 758b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 759b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Skip the singly mapped values. There is nothing to gain from hoisting a 760b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // single back-copy. 761393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) { 762b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n'); 763b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 764b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 765b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 766b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.first) { 767b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // First time we see ParentVNI. VNI dominates itself. 768b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(ValMBB, VNI->def); 769b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } else if (Dom.first == ValMBB) { 770b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Two defs in the same block. Pick the earlier def. 771b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.second.isValid() || VNI->def < Dom.second) 772b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom.second = VNI->def; 773b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } else { 774b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Different basic blocks. Check if one dominates. 775b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock *Near = 776b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MDT.findNearestCommonDominator(Dom.first, ValMBB); 777b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (Near == ValMBB) 778b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Def ValMBB dominates. 779b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(ValMBB, VNI->def); 780b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen else if (Near != Dom.first) 781b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // None dominate. Hoist to common dominator, need new def. 782b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(Near, SlotIndex()); 783b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 784b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 785b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def 786b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen << " for parent " << ParentVNI->id << '@' << ParentVNI->def 787b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen << " hoist to BB#" << Dom.first->getNumber() << ' ' 788b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen << Dom.second << '\n'); 789b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 790b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 791b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Insert the hoisted copies. 792b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { 793b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DomPair &Dom = NearestDom[i]; 794b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.first || Dom.second.isValid()) 795b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 796c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // This value needs a hoisted copy inserted at the end of Dom.first. 797c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen VNInfo *ParentVNI = Parent->getValNumInfo(i); 798c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def); 799c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Get a less loopy dominator than Dom.first. 800c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen Dom.first = findShallowDominator(Dom.first, DefMBB); 801b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot(); 802b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom.second = 803c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen defFromParent(0, ParentVNI, Last, *Dom.first, 80474c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen SA.getLastSplitPointIter(Dom.first))->def; 805b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 806b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 807b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Remove redundant back-copies that are now known to be dominated by another 808b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // def with the same value. 809b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SmallVector<VNInfo*, 8> BackCopies; 810b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end(); 811b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VI != VE; ++VI) { 812b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *VNI = *VI; 813b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); 814b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen const DomPair &Dom = NearestDom[ParentVNI->id]; 815b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.first || Dom.second == VNI->def) 816b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 817b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen BackCopies.push_back(VNI); 818393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(0, ParentVNI); 819b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 820b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen removeBackCopies(BackCopies); 821b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen} 822b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 823b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 82444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen/// transferValues - Transfer all possible values to the new live ranges. 825abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen/// Values that were rematerialized are left alone, they need LRCalc.extend(). 82644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesenbool SplitEditor::transferValues() { 8274670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Skipped = false; 8284670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegAssignMap::const_iterator AssignI = RegAssign.begin(); 829a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 830a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 8314670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " blit " << *ParentI << ':'); 8324670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen VNInfo *ParentVNI = ParentI->valno; 8334670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // RegAssign has holes where RegIdx 0 should be used. 8344670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex Start = ParentI->start; 8354670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen AssignI.advanceTo(Start); 8364670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen do { 8374670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen unsigned RegIdx; 8384670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex End = ParentI->end; 8394670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (!AssignI.valid()) { 8404670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 8414670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else if (AssignI.start() <= Start) { 8424670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = AssignI.value(); 8434670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (AssignI.stop() < End) { 8444670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = AssignI.stop(); 8454670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++AssignI; 8464670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 8474670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else { 8484670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 8494670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = std::min(End, AssignI.start()); 8504670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 85144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 85244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 8534670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 85444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 85544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 85644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Check for a simply defined value that can be blitted directly. 857393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id)); 858393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (VNInfo *VNI = VFP.getPointer()) { 8594670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id); 86044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LI->addRange(LiveRange(Start, End, VNI)); 86144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Start = End; 86244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 86344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 86444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 865393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // Skip values with forced recomputation. 866393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (VFP.getInt()) { 867393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen DEBUG(dbgs() << "(recalc)"); 8684670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Skipped = true; 86944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Start = End; 87044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 87144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 87244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 873c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LiveRangeCalc &LRC = getLRCalc(RegIdx); 874c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen 87544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This value has multiple defs in RegIdx, but it wasn't rematerialized, 87644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // so the live range is accurate. Add live-in blocks in [Start;End) to the 87744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // LiveInBlocks. 87844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 87944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SlotIndex BlockStart, BlockEnd; 88044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 88144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 88244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The first block may be live-in, or it may have its own def. 88344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Start != BlockStart) { 884ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End)); 88544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(VNI && "Missing def for complex mapped value"); 88644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 88744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // MBB has its own def. Is it also live-out? 888b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (BlockEnd <= End) 889c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.setLiveOutValue(MBB, VNI); 890b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 89144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Skip to the next block for live-in. 89244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen ++MBB; 89344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockStart = BlockEnd; 89444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 89544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 89644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Handle the live-in blocks covered by [Start;End). 89744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(Start <= BlockStart && "Expected live-in block"); 89844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen while (BlockStart < End) { 89944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 90044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockEnd = LIS.getMBBEndIdx(MBB); 90144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (BlockStart == ParentVNI->def) { 90244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This block has the def of a parent PHI, so it isn't live-in. 90344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 904ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End)); 90544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(VNI && "Missing def for complex mapped parent PHI"); 906b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (End >= BlockEnd) 907c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.setLiveOutValue(MBB, VNI); // Live-out as well. 90844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } else { 909b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This block needs a live-in value. The last block covered may not 910b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // be live-out. 91144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (End < BlockEnd) 912c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.addLiveInBlock(LI, MDT[MBB], End); 91344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen else { 914b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Live-through, and we don't know the value. 915c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.addLiveInBlock(LI, MDT[MBB]); 916c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.setLiveOutValue(MBB, 0); 91744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 91844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 91944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockStart = BlockEnd; 92044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen ++MBB; 92144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 9224670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Start = End; 9234670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } while (Start != ParentI->end); 9244670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 9254670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 92644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 927c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRCalc[0].calculateValues(LIS.getSlotIndexes(), &MDT, 928c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen &LIS.getVNInfoAllocator()); 929c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen if (SpillMode) 930c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRCalc[1].calculateValues(LIS.getSlotIndexes(), &MDT, 931c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen &LIS.getVNInfoAllocator()); 93244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 9334670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen return Skipped; 9344670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen} 9354670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 936e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesenvoid SplitEditor::extendPHIKillRanges() { 937e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // Extend live ranges to be live-out for successor PHI values. 938a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 939a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 940e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen const VNInfo *PHIVNI = *I; 941e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 942e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen continue; 943e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 944abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 945abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen LiveRangeCalc &LRC = getLRCalc(RegIdx); 946e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 947e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 948e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 949abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(*PI); 950abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen SlotIndex LastUse = End.getPrevSlot(); 951e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // The predecessor may not have a live-out value. That is OK, like an 952e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // undef PHI operand. 953abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen if (Edit->getParent().liveAt(LastUse)) { 954abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen assert(RegAssign.lookup(LastUse) == RegIdx && 955e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen "Different register assignment in phi predecessor"); 956abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen LRC.extend(LI, End, 957abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); 958e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 959e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 960e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 961e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen} 962e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 963a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 9644670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenvoid SplitEditor::rewriteAssigned(bool ExtendRanges) { 965a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 966078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 9677466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineOperand &MO = RI.getOperand(); 9687466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 9697466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen ++RI; 9700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // LiveDebugVariables should have handled all DBG_VALUE instructions. 9717466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen if (MI->isDebugValue()) { 9727466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen DEBUG(dbgs() << "Zapping " << *MI); 9737466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MO.setReg(0); 9747466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen continue; 9757466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 976a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 977b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // <undef> operands don't really read the register, so it doesn't matter 978b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // which register we choose. When the use operand is tied to a def, we must 979b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // use the same register as the def, so just do that always. 980078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI); 981b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen if (MO.isDef() || MO.isUndef()) 9822debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Idx = Idx.getRegSlot(MO.isEarlyClobber()); 9830f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 9840f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite to the mapped register at Idx. 9850f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned RegIdx = RegAssign.lookup(Idx); 986abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen LiveInterval *LI = Edit->get(RegIdx); 987abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen MO.setReg(LI->reg); 9880f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 9890f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':' << RegIdx << '\t' << *MI); 9900f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 9917cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Extend liveness to Idx if the instruction reads reg. 99281d686edbe6effe624add9394673bd571d89bfb7Jakob Stoklund Olesen if (!ExtendRanges || MO.isUndef()) 9937cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 9947cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 9957cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Skip instructions that don't read Reg. 9967cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (MO.isDef()) { 9977cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!MO.getSubReg() && !MO.isEarlyClobber()) 9987cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 9997cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // We may wan't to extend a live range for a partial redef, or for a use 10007cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // tied to an early clobber. 10017cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getPrevSlot(); 10027cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!Edit->getParent().liveAt(Idx)) 10037cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 10047cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen } else 10052debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Idx = Idx.getRegSlot(true); 10067cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 1007abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen getLRCalc(RegIdx).extend(LI, Idx.getNextSlot(), LIS.getSlotIndexes(), 1008abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen &MDT, &LIS.getVNInfoAllocator()); 10097466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 10107466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen} 10117466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 10125881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesenvoid SplitEditor::deleteRematVictims() { 10135881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen SmallVector<MachineInstr*, 8> Dead; 10142dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 10152dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen LiveInterval *LI = *I; 10162dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 10172dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen LII != LIE; ++LII) { 10181f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen // Dead defs end at the dead slot. 10191f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen if (LII->end != LII->valno->def.getDeadSlot()) 10202dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 10212dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 10222dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen assert(MI && "Missing instruction for dead def"); 10232dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MI->addRegisterDead(LI->reg, &TRI); 10245881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 10252dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen if (!MI->allDefsAreDead()) 10262dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 10275881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 10282dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << *MI); 10292dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen Dead.push_back(MI); 10302dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen } 10315881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen } 10325881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 10335881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (Dead.empty()) 10345881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen return; 10355881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 10368a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->eliminateDeadDefs(Dead); 10375881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen} 10385881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 10395928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesenvoid SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 10404670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumFinished; 10410f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 10420f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // At this point, the live intervals in Edit contain VNInfos corresponding to 10430f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // the inserted copies. 10440f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 10450f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Add the original defs from the parent interval. 1046a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 1047a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 10480f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *ParentVNI = *I; 10499ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (ParentVNI->isUnused()) 10509ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen continue; 1051670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 105229ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); 105329ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen VNI->setIsPHIDef(ParentVNI->isPHIDef()); 105429ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen 1055393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // Force rematted values to be recomputed everywhere. 10564670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // The new live ranges may be truncated. 1057a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 1058a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1059393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(i, ParentVNI); 10605fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 1061c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 1062b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Hoist back-copies to the complement interval when in spill mode. 1063b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen switch (SpillMode) { 1064b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen case SM_Partition: 1065b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Leave all back-copies as is. 1066b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen break; 1067b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen case SM_Size: 1068b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen hoistCopiesForSize(); 1069b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen break; 1070b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen case SM_Speed: 1071b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen llvm_unreachable("Spill mode 'speed' not implemented yet"); 1072b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 1073b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 107444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Transfer the simply mapped values, check if any are skipped. 107544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen bool Skipped = transferValues(); 107644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Skipped) 10774670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen extendPHIKillRanges(); 10784670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen else 10794670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumSimple; 10804670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 10814670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Rewrite virtual registers, possibly extending ranges. 108244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen rewriteAssigned(Skipped); 1083463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher 10845881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Delete defs that were rematted everywhere. 108544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Skipped) 10865881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen deleteRematVictims(); 10875fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 10880253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Get rid of unused values and set phi-kill flags. 1089a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) 1090078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen (*I)->RenumberValues(LIS); 10910253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 10925928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Provide a reverse mapping from original indices to Edit ranges. 10935928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRMap) { 10945928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->clear(); 10955928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 10965928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->push_back(i); 10975928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 10985928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 10993a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Now check if any registers were separated into multiple components. 1100078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 1101a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 11023a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Don't use iterators, they are invalidated by create() below. 1103a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveInterval *li = Edit->get(i); 11043a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen unsigned NumComp = ConEQ.Classify(li); 11053a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen if (NumComp <= 1) 11063a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen continue; 11073a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 11083a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> dups; 11093a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen dups.push_back(li); 1110ae5fbeec23cff833cad9e6b2a638efd1f48bef49Matt Beaumont-Gay for (unsigned j = 1; j != NumComp; ++j) 11118a06af96698537377275dd7848db69915638dd26Pete Cooper dups.push_back(&Edit->create()); 11122254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen ConEQ.Distribute(&dups[0], MRI); 11135928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // The new intervals all map back to i. 11145928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRMap) 11155928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->resize(Edit->size(), i); 11163a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen } 11173a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen 111808e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen // Calculate spill weight and allocation hints for new intervals. 11198a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops); 11205928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 11215928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen assert(!LRMap || LRMap->size() == Edit->size()); 1122f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 1123f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 1124f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 11258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1126f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen// Single Block Splitting 1127f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1128f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 11292d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesenbool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, 11302d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen bool SingleInstrs) const { 11312d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Always split for multiple instructions. 11322d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (!BI.isOneInstr()) 11332d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return true; 11342d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Don't split for single instructions unless explicitly requested. 11352d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (!SingleInstrs) 11362d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return false; 11372d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Splitting a live-through range always makes progress. 11382d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (BI.LiveIn && BI.LiveOut) 11392d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return true; 11402d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // No point in isolating a copy. It has no register class constraints. 11412d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike()) 11422d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return false; 11432d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Finally, don't isolate an end point that was created by earlier splits. 11442d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return isOriginalEndpoint(BI.FirstInstr); 11452d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen} 11462d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen 1147fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 1148fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen openIntv(); 1149fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 1150fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr, 1151fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen LastSplitPoint)); 1152fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { 1153fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(SegStart, leaveIntvAfter(BI.LastInstr)); 1154fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } else { 1155fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // The last use is after the last valid split point. 1156fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 1157fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen useIntv(SegStart, SegStop); 1158fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(SegStop, BI.LastInstr); 1159fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 1160fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen} 1161fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 1162b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1163b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1164b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// Global Live Range Splitting Support 1165b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1166b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1167b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// These methods support a method of global live range splitting that uses a 1168b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// global algorithm to decide intervals for CFG edges. They will insert split 1169b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// points and color intervals in basic blocks while avoiding interference. 1170b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// 1171b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// Note that splitSingleBlock is also useful for blocks where both CFG edges 1172b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// are on the stack. 1173b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1174b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitLiveThroughBlock(unsigned MBBNum, 1175b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvIn, SlotIndex LeaveBefore, 1176b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvOut, SlotIndex EnterAfter){ 1177b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 1178b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); 1179b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1180b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop 1181b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ") intf " << LeaveBefore << '-' << EnterAfter 1182b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", live-through " << IntvIn << " -> " << IntvOut); 1183b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1184b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks"); 1185b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1186fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block"); 1187fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf"); 1188fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!EnterAfter || EnterAfter >= Start) && "Interference before block"); 1189fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen 1190fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); 1191fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen 1192b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (!IntvOut) { 1193b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill on entry.\n"); 1194b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1195b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<<<< Possible LeaveBefore interference. 1196b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1197b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // -____________ Spill on entry. 1198b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1199b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1200b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = leaveIntvAtTop(*MBB); 1201b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1202b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen (void)Idx; 1203b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1204b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1205b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1206b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (!IntvIn) { 1207b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", reload on exit.\n"); 1208b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1209b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>>>>> Possible EnterAfter interference. 1210b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1211b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ___________-- Reload on exit. 1212b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1213b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1214b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAtEnd(*MBB); 1215b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1216b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen (void)Idx; 1217b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1218b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1219b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1220b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { 1221b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", straight through.\n"); 1222b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1223b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1224b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ------------- Straight through, same intv, no interference. 1225b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1226b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1227b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Stop); 1228b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1229b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1230b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1231b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // We cannot legally insert splits after LSP. 1232b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(MBBNum); 1233fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf"); 1234b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1235b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || 1236b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { 1237b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", switch avoiding interference.\n"); 1238b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1239b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. 1240b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1241b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ------======= Switch intervals between interference. 1242b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1243b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1244fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen SlotIndex Idx; 1245fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen if (LeaveBefore && LeaveBefore < LSP) { 1246fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen Idx = enterIntvBefore(LeaveBefore); 1247fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen useIntv(Idx, Stop); 1248fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen } else { 1249fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen Idx = enterIntvAtEnd(*MBB); 1250fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen } 1251b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1252b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1253b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1254b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1255b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1256b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1257b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1258b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", create local intv for interference.\n"); 1259b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1260b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. 1261b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1262b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ==---------== Switch intervals before/after interference. 1263b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1264b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(LeaveBefore <= EnterAfter && "Missed case"); 1265b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1266b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1267b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAfter(EnterAfter); 1268b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1269b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1270b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1271b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1272b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen Idx = leaveIntvBefore(LeaveBefore); 1273b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1274b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1275b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1276b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1277b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1278b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 1279b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvIn, SlotIndex LeaveBefore) { 1280b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 1281b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1282b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1283b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1284fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1285b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", reg-in " << IntvIn << ", leave before " << LeaveBefore 1286b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << (BI.LiveOut ? ", stack-out" : ", killed in block")); 1287b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1288b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(IntvIn && "Must have register in"); 1289b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(BI.LiveIn && "Must be live-in"); 1290b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference"); 1291b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1292fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { 1293b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << " before interference.\n"); 1294b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1295b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<< Interference after kill. 1296b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---x | Killed in block. 1297b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ========= Use IntvIn everywhere. 1298b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1299b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1300fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(Start, BI.LastInstr); 1301b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1302b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1303b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1304b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1305b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1306fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { 1307b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1308b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<< Possible interference after last use. 1309b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-out on stack. 1310b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =========____ Leave IntvIn after last use. 1311b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1312b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // < Interference after last use. 1313b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o--o| Live-out on stack, late last use. 1314b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ============ Copy to stack after LSP, overlap IntvIn. 1315b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // \_____ Stack interval is live-out. 1316b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1317fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (BI.LastInstr < LSP) { 1318b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill after last use before interference.\n"); 1319b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1320fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex Idx = leaveIntvAfter(BI.LastInstr); 1321b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1322b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1323b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } else { 1324b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill before last split point.\n"); 1325b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1326af4e40c2f41a7d60b86958e034b00542d551b5f2Jakob Stoklund Olesen SlotIndex Idx = leaveIntvBefore(LSP); 1327fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(Idx, BI.LastInstr); 1328b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1329b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1330b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1331b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1332b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1333b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1334b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // The interference is overlapping somewhere we wanted to use IntvIn. That 1335b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // means we need to create a local interval that can be allocated a 1336b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // different register. 1337b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned LocalIntv = openIntv(); 1338f9d7fb6b3c45abc64ad52cd8a9a8a7dd5aa9f4bbMatt Beaumont-Gay (void)LocalIntv; 1339b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n"); 1340b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1341fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastInstr < LSP) { 1342b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1343b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<< Interference overlapping uses. 1344b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-out on stack. 1345b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =====----____ Leave IntvIn before interference, then spill. 1346b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1347fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex To = leaveIntvAfter(BI.LastInstr); 1348b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(LeaveBefore); 1349b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, To); 1350b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1351b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, From); 1352b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1353b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1354b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1355b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1356b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<< Interference overlapping uses. 1357b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o--o| Live-out on stack, late last use. 1358b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =====------- Copy to stack before LSP, overlap LocalIntv. 1359b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // \_____ Stack interval is live-out. 1360b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1361b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex To = leaveIntvBefore(LSP); 1362fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(To, BI.LastInstr); 1363b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); 1364b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, To); 1365b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1366b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, From); 1367b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1368b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1369b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1370b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 1371b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvOut, SlotIndex EnterAfter) { 1372b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 1373b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1374b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1375b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1376fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1377b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", reg-out " << IntvOut << ", enter after " << EnterAfter 1378b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << (BI.LiveIn ? ", stack-in" : ", defined in block")); 1379b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1380b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1381b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1382b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(IntvOut && "Must have register out"); 1383b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(BI.LiveOut && "Must be live-out"); 1384b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || EnterAfter < LSP) && "Bad interference"); 1385b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1386fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { 1387b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << " after interference.\n"); 1388b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1389b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> Interference before def. 1390b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // | o---o---| Defined in block. 1391b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ========= Use IntvOut everywhere. 1392b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1393b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1394fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(BI.FirstInstr, Stop); 1395b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1396b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1397b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1398fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { 1399b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", reload after interference.\n"); 1400b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1401b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> Interference before def. 1402b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-through, stack-in. 1403b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ____========= Enter IntvOut before first use. 1404b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1405b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1406fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr)); 1407b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1408b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1409b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1410b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1411b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1412b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // The interference is overlapping somewhere we wanted to use IntvOut. That 1413b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // means we need to create a local interval that can be allocated a 1414b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // different register. 1415b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", interference overlaps uses.\n"); 1416b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1417b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>>>>> Interference overlapping uses. 1418b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-through, stack-in. 1419b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ____---====== Create local interval for interference range. 1420b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1421b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1422b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAfter(EnterAfter); 1423b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1424b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1425b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1426b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen openIntv(); 1427fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr)); 1428b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, Idx); 1429b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1430