SplitKit.cpp revision 331de11a0acc6a095b98914b5f05ff242c9d7819
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" 174670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 188ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 19789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 20d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 21f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 22c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 241ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/VirtRegMap.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) { 217331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert(LVI->start == LVI->valno->def && "Dangling Segment 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 248331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // A Segment that starts in the middle of the block must be a def. 249331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert(LVI->start == LVI->valno->def && "Dangling Segment 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, 3284eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer MachineDominatorTree &mdt, 3294eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer MachineBlockFrequencyInfo &mbfi) 3301c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen : SA(sa), LIS(lis), VRM(vrm), 3311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MRI(vrm.getMachineFunction().getRegInfo()), 3321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen MDT(mdt), 3331c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), 3341c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), 3354eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer MBFI(mbfi), 336bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Edit(0), 3371c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen OpenIdx(0), 338708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SpillMode(SM_Partition), 3391c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen RegAssign(Allocator) 340bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen{} 341bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 342708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesenvoid SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { 343708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen Edit = &LRE; 344708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SpillMode = SM; 345bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen OpenIdx = 0; 346bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen RegAssign.clear(); 347bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Values.clear(); 348c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen 349c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen // Reset the LiveRangeCalc instances needed for this spill mode. 350631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, 351631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen &LIS.getVNInfoAllocator()); 352c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen if (SpillMode) 353631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, 354631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen &LIS.getVNInfoAllocator()); 355bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 3561c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // We don't need an AliasAnalysis since we will only be performing 3571c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // cheap-as-a-copy remats anyway. 3588a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->anyRematerializable(0); 3591c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 3601c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 361b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 3621c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesenvoid SplitEditor::dump() const { 3631c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (RegAssign.empty()) { 3641c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " empty\n"; 3651c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 3661c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3671c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3681c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 3691c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 3701c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << '\n'; 371b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen} 37277e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 373b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen 3741c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::defValue(unsigned RegIdx, 3751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const VNInfo *ParentVNI, 3761c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx) { 3771c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 3781c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 379a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 3801feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 3811c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3821c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Create a new value. 3833b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator()); 3841c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3851c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Use insert for lookup, so we can add missing values with a second lookup. 3861c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen std::pair<ValueMap::iterator, bool> InsP = 387393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), 388393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen ValueForcePair(VNI, false))); 3891c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3901c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was the first time (RegIdx, ParentVNI) was mapped. 3911c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Keep it as a simple def without any liveness. 3921c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (InsP.second) 3931c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 3941c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3951c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // If the previous value was a simple mapping, add liveness for it now. 396393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (VNInfo *OldVNI = InsP.first->second.getPointer()) { 3971c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = OldVNI->def; 398331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), OldVNI)); 399393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // No longer a simple mapping. Switch to a complex, non-forced mapping. 400393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen InsP.first->second = ValueForcePair(); 4011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 4021c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4031c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is a complex mapping, add liveness for VNI 4041c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 405331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI)); 4061c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 4089ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen} 4099ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 410393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesenvoid SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) { 4111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 412393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)]; 413393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen VNInfo *VNI = VFP.getPointer(); 4141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 415393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // ParentVNI was either unmapped or already complex mapped. Either way, just 416393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // set the force bit. 417393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (!VNI) { 418393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen VFP.setInt(true); 4191c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 420393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen } 4211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4221c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was previously a single mapping. Make sure the old def is represented 4231c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by a trivial live range. 4241c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 4251feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 426331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI)); 427393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // Mark as complex mapped, forced. 428393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen VFP = ValueForcePair(0, true); 429e5a2e366322ef5f0d597b1fb8dbf55f2cf36cf15Jakob Stoklund Olesen} 430e5a2e366322ef5f0d597b1fb8dbf55f2cf36cf15Jakob Stoklund Olesen 4310f43811903f10394f7088f4634c0b4f9668cbac0Eric ChristopherVNInfo *SplitEditor::defFromParent(unsigned RegIdx, 432cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 433cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 434cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 435cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I) { 436cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineInstr *CopyMI = 0; 437cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex Def; 4381feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 439cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 440bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen // We may be trying to avoid interference that ends at a deleted instruction, 441bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen // so always begin RegIdx 0 early and all others late. 442bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen bool Late = RegIdx != 0; 443bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen 444cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Attempt cheap-as-a-copy rematerialization. 445cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 4468a06af96698537377275dd7848db69915638dd26Pete Cooper if (Edit->canRematerializeAt(RM, UseIdx, true)) { 4478a06af96698537377275dd7848db69915638dd26Pete Cooper Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late); 448e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumRemats; 449cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } else { 450cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Can't remat, just insert a copy from parent. 4510f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 452a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen .addReg(Edit->getReg()); 453bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) 4542debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen .getRegSlot(); 455e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumCopies; 456cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } 457cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 458cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Define the value in Reg. 4593b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen return defValue(RegIdx, ParentVNI, Def); 460cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen} 461cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 462f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen/// Create a new virtual register and live interval. 463e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesenunsigned SplitEditor::openIntv() { 4640f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the complement as index 0. 465a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->empty()) 466e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey Edit->createEmptyInterval(); 4670f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 4680f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the open interval. 469a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen OpenIdx = Edit->size(); 470e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey Edit->createEmptyInterval(); 471e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen return OpenIdx; 472e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen} 473e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 474e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesenvoid SplitEditor::selectIntv(unsigned Idx) { 475e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen assert(Idx != 0 && "Cannot select the complement interval"); 476e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen assert(Idx < Edit->size() && "Can only select previously opened interval"); 47787360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); 478e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen OpenIdx = Idx; 479f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 480f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 481207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 4820f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvBefore"); 4839b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " enterIntvBefore " << Idx); 484207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 485a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 486f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 4879b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 488207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx; 489f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 490207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 491078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 492f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen assert(MI && "enterIntvBefore called with invalid index"); 493cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 494207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 495207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 496f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 497f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 49887360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { 49987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before enterIntvAfter"); 50087360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAfter " << Idx); 50187360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 50287360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 50387360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen if (!ParentVNI) { 50487360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 50587360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen return Idx; 50687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen } 50787360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 50887360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 50987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen assert(MI && "enterIntvAfter called with invalid index"); 51087360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen 51187360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), 51287360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 51387360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen return VNI->def; 51487360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen} 51587360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen 516207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 5170f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 518207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(&MBB); 519207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex Last = End.getPrevSlot(); 520207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 521a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 522f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5239b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 524207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return End; 525f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 5269b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id); 527207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 52874c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen SA.getLastSplitPointIter(&MBB)); 529207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen RegAssign.insert(VNI->def, End, OpenIdx); 5300f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 531207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 532f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 533f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 534078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// useIntv - indicate that all instructions in MBB should use OpenLI. 5357536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 536078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 537f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 538f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 5397536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 5400f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before useIntv"); 5410f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 5420f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, End, OpenIdx); 5430f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 544f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 545f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 546207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 5470f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 5489b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAfter " << Idx); 549f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 550f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen // The interval must be live beyond the instruction at Idx. 551ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen SlotIndex Boundary = Idx.getBoundaryIndex(); 552ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary); 553f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5549b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 555ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen return Boundary.getNextSlot(); 556f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 557207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 558ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Boundary); 55901cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen assert(MI && "No instruction at index"); 560ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen 561ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // In spill mode, make live ranges as short as possible by inserting the copy 562ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // before MI. This is only possible if that instruction doesn't redefine the 563ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // value. The inserted COPY is not a kill, and we don't need to recompute 564ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // the source live range. The spiller also won't try to hoist this copy. 565ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) && 566ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen MI->readsVirtualRegister(Edit->getReg())) { 567ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen forceRecompute(0, ParentVNI); 568ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 569ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen return Idx; 570ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen } 571ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen 572ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(), 57301cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen llvm::next(MachineBasicBlock::iterator(MI))); 574207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 575f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 576f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 5779b057771ba22441b8d312404204433477b4be657Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 5789b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 5799b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvBefore " << Idx); 5809b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 5819b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen // The interval must be live into the instruction at Idx. 582fc47933db5c8fea9bc89470d83cc5af7ca36f2a3Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 583a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 5849b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!ParentVNI) { 5859b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 5869b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return Idx.getNextSlot(); 5879b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 5889b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 5899b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 5909b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 5919b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(MI && "No instruction at index"); 5929b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 5939b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return VNI->def; 5949b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen} 5959b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 596207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 5970f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 598078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(&MBB); 5999b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 6007536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 601a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 602f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6039b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 604207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Start; 6057536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen } 6067536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6070f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 608cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MBB.SkipPHIsAndLabels(MBB.begin())); 6090f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, VNI->def, OpenIdx); 6100f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 611207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 612f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 613f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6145c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesenvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 6155c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before overlapIntv"); 616a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 617194eb71a11a77c7fb576780783a77e64924dfb10Jakob Stoklund Olesen assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) && 6185c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Parent changes value in extended range"); 6195c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 6205c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Range cannot span basic blocks"); 6215c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 622abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen // The complement interval will be extended as needed by LRCalc.extend(). 623b3dd82670aa60cacba81f090d292722c3ef44354Jakob Stoklund Olesen if (ParentVNI) 624393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(0, ParentVNI); 6255c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 6265c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen RegAssign.insert(Start, End, OpenIdx); 6275c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dump()); 6285c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen} 6295c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 630b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen//===----------------------------------------------------------------------===// 631b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen// Spill modes 632b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen//===----------------------------------------------------------------------===// 633b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 634b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesenvoid SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) { 6351feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(0)); 636b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n"); 637b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen RegAssignMap::iterator AssignI; 638b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen AssignI.setMap(RegAssign); 639b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 640b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 641b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *VNI = Copies[i]; 642b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SlotIndex Def = VNI->def; 643b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Def); 644b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen assert(MI && "No instruction for back-copy"); 645b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 646b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock *MBB = MI->getParent(); 647b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock::iterator MBBI(MI); 648b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen bool AtBegin; 649b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen do AtBegin = MBBI == MBB->begin(); 650b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen while (!AtBegin && (--MBBI)->isDebugValue()); 651b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 652b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Removing " << Def << '\t' << *MI); 653b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen LI->removeValNo(VNI); 654b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen LIS.RemoveMachineInstrFromMaps(MI); 655b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MI->eraseFromParent(); 656b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 657b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Adjust RegAssign if a register assignment is killed at VNI->def. We 658b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // want to avoid calculating the live range of the source register if 659b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // possible. 6601599a64277f3a01619b5614974be9bec662c7ec0Jakob Stoklund Olesen AssignI.find(Def.getPrevSlot()); 661b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!AssignI.valid() || AssignI.start() >= Def) 662b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 663b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // If MI doesn't kill the assigned register, just leave it. 664b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (AssignI.stop() != Def) 665b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 666b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen unsigned RegIdx = AssignI.value(); 667b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) { 668b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx << '\n'); 669393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def)); 670b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } else { 6712debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex Kill = LIS.getInstructionIndex(MBBI).getRegSlot(); 672b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI); 673b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen AssignI.setStop(Kill); 674b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 675b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 676b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen} 677b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 678c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund OlesenMachineBasicBlock* 679c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund OlesenSplitEditor::findShallowDominator(MachineBasicBlock *MBB, 680c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *DefMBB) { 681c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (MBB == DefMBB) 682c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return MBB; 683c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def."); 684c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 685c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen const MachineLoopInfo &Loops = SA.Loops; 686c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB); 687c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineDomTreeNode *DefDomNode = MDT[DefMBB]; 688c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 689c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Best candidate so far. 690c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *BestMBB = MBB; 691c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen unsigned BestDepth = UINT_MAX; 692c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 693c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen for (;;) { 694c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen const MachineLoop *Loop = Loops.getLoopFor(MBB); 695c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 696c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // MBB isn't in a loop, it doesn't get any better. All dominators have a 697c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // higher frequency by definition. 698c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (!Loop) { 699c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 700c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen << MBB->getNumber() << " at depth 0\n"); 701c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return MBB; 702c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 703c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 704c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // We'll never be able to exit the DefLoop. 705c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (Loop == DefLoop) { 706c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 707c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen << MBB->getNumber() << " in the same loop\n"); 708c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return MBB; 709c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 710c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 711c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Least busy dominator seen so far. 712c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen unsigned Depth = Loop->getLoopDepth(); 713c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (Depth < BestDepth) { 714c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen BestMBB = MBB; 715c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen BestDepth = Depth; 716c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 717c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen << MBB->getNumber() << " at depth " << Depth << '\n'); 718c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 719c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 720c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Leave loop by going to the immediate dominator of the loop header. 721c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // This is a bigger stride than simply walking up the dominator tree. 722c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom(); 723c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 724c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Too far up the dominator tree? 725c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (!IDom || !MDT.dominates(DefDomNode, IDom)) 726c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return BestMBB; 727c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 728c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MBB = IDom->getBlock(); 729c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 730c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen} 731c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 732b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesenvoid SplitEditor::hoistCopiesForSize() { 733b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Get the complement interval, always RegIdx 0. 7341feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(0)); 735b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen LiveInterval *Parent = &Edit->getParent(); 736b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 737b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Track the nearest common dominator for all back-copies for each ParentVNI, 738b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // indexed by ParentVNI->id. 739b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair; 740b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums()); 741b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 742b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Find the nearest common dominator for parent values with multiple 743b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // back-copies. If a single back-copy dominates, put it in DomPair.second. 744b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end(); 745b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VI != VE; ++VI) { 746b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *VNI = *VI; 7471599a64277f3a01619b5614974be9bec662c7ec0Jakob Stoklund Olesen if (VNI->isUnused()) 7481599a64277f3a01619b5614974be9bec662c7ec0Jakob Stoklund Olesen continue; 749b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); 750b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen assert(ParentVNI && "Parent not live at complement def"); 751b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 752b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Don't hoist remats. The complement is probably going to disappear 753b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // completely anyway. 754b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 755b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 756b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 757b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def); 758b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DomPair &Dom = NearestDom[ParentVNI->id]; 759b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 760b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Keep directly defined parent values. This is either a PHI or an 761b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // instruction in the complement range. All other copies of ParentVNI 762b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // should be eliminated. 763b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (VNI->def == ParentVNI->def) { 764b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n'); 765b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(ValMBB, VNI->def); 766b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 767b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 768b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Skip the singly mapped values. There is nothing to gain from hoisting a 769b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // single back-copy. 770393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) { 771b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n'); 772b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 773b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 774b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 775b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.first) { 776b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // First time we see ParentVNI. VNI dominates itself. 777b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(ValMBB, VNI->def); 778b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } else if (Dom.first == ValMBB) { 779b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Two defs in the same block. Pick the earlier def. 780b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.second.isValid() || VNI->def < Dom.second) 781b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom.second = VNI->def; 782b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } else { 783b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Different basic blocks. Check if one dominates. 784b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock *Near = 785b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MDT.findNearestCommonDominator(Dom.first, ValMBB); 786b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (Near == ValMBB) 787b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Def ValMBB dominates. 788b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(ValMBB, VNI->def); 789b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen else if (Near != Dom.first) 790b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // None dominate. Hoist to common dominator, need new def. 791b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(Near, SlotIndex()); 792b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 793b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 794b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def 795b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen << " for parent " << ParentVNI->id << '@' << ParentVNI->def 796b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen << " hoist to BB#" << Dom.first->getNumber() << ' ' 797b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen << Dom.second << '\n'); 798b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 799b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 800b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Insert the hoisted copies. 801b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { 802b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DomPair &Dom = NearestDom[i]; 803b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.first || Dom.second.isValid()) 804b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 805c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // This value needs a hoisted copy inserted at the end of Dom.first. 806c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen VNInfo *ParentVNI = Parent->getValNumInfo(i); 807c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def); 808c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Get a less loopy dominator than Dom.first. 809c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen Dom.first = findShallowDominator(Dom.first, DefMBB); 810b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot(); 811b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom.second = 812c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen defFromParent(0, ParentVNI, Last, *Dom.first, 81374c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen SA.getLastSplitPointIter(Dom.first))->def; 814b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 815b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 816b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Remove redundant back-copies that are now known to be dominated by another 817b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // def with the same value. 818b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SmallVector<VNInfo*, 8> BackCopies; 819b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end(); 820b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VI != VE; ++VI) { 821b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *VNI = *VI; 8221599a64277f3a01619b5614974be9bec662c7ec0Jakob Stoklund Olesen if (VNI->isUnused()) 8231599a64277f3a01619b5614974be9bec662c7ec0Jakob Stoklund Olesen continue; 824b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); 825b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen const DomPair &Dom = NearestDom[ParentVNI->id]; 826b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.first || Dom.second == VNI->def) 827b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 828b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen BackCopies.push_back(VNI); 829393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(0, ParentVNI); 830b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 831b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen removeBackCopies(BackCopies); 832b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen} 833b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 834b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 83544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen/// transferValues - Transfer all possible values to the new live ranges. 836abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen/// Values that were rematerialized are left alone, they need LRCalc.extend(). 83744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesenbool SplitEditor::transferValues() { 8384670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Skipped = false; 8394670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegAssignMap::const_iterator AssignI = RegAssign.begin(); 840a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), 841a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { 8424670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " blit " << *ParentI << ':'); 8434670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen VNInfo *ParentVNI = ParentI->valno; 8444670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // RegAssign has holes where RegIdx 0 should be used. 8454670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex Start = ParentI->start; 8464670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen AssignI.advanceTo(Start); 8474670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen do { 8484670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen unsigned RegIdx; 8494670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen SlotIndex End = ParentI->end; 8504670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (!AssignI.valid()) { 8514670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 8524670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else if (AssignI.start() <= Start) { 8534670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = AssignI.value(); 8544670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (AssignI.stop() < End) { 8554670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = AssignI.stop(); 8564670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++AssignI; 8574670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 8584670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else { 8594670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 8604670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = std::min(End, AssignI.start()); 8614670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 86244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 86344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 8644670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 8651feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 86644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 86744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Check for a simply defined value that can be blitted directly. 868393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id)); 869393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (VNInfo *VNI = VFP.getPointer()) { 8704670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id); 871331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun LI->addSegment(LiveInterval::Segment(Start, End, VNI)); 87244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Start = End; 87344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 87444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 87544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 876393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // Skip values with forced recomputation. 877393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (VFP.getInt()) { 878393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen DEBUG(dbgs() << "(recalc)"); 8794670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Skipped = true; 88044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Start = End; 88144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 88244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 88344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 884c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LiveRangeCalc &LRC = getLRCalc(RegIdx); 885c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen 88644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This value has multiple defs in RegIdx, but it wasn't rematerialized, 88744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // so the live range is accurate. Add live-in blocks in [Start;End) to the 88844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // LiveInBlocks. 88944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 89044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SlotIndex BlockStart, BlockEnd; 89144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); 89244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 89344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The first block may be live-in, or it may have its own def. 89444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Start != BlockStart) { 895ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End)); 89644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(VNI && "Missing def for complex mapped value"); 89744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 89844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // MBB has its own def. Is it also live-out? 899b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (BlockEnd <= End) 900c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.setLiveOutValue(MBB, VNI); 901b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 90244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Skip to the next block for live-in. 90344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen ++MBB; 90444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockStart = BlockEnd; 90544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 90644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 90744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Handle the live-in blocks covered by [Start;End). 90844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(Start <= BlockStart && "Expected live-in block"); 90944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen while (BlockStart < End) { 91044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 91144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockEnd = LIS.getMBBEndIdx(MBB); 91244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (BlockStart == ParentVNI->def) { 91344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This block has the def of a parent PHI, so it isn't live-in. 91444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 915ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End)); 91644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(VNI && "Missing def for complex mapped parent PHI"); 917b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (End >= BlockEnd) 918c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.setLiveOutValue(MBB, VNI); // Live-out as well. 91944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } else { 920b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This block needs a live-in value. The last block covered may not 921b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // be live-out. 92244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (End < BlockEnd) 923c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.addLiveInBlock(LI, MDT[MBB], End); 92444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen else { 925b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Live-through, and we don't know the value. 926c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.addLiveInBlock(LI, MDT[MBB]); 927c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LRC.setLiveOutValue(MBB, 0); 92844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 92944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 93044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockStart = BlockEnd; 93144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen ++MBB; 93244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 9334670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Start = End; 9344670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } while (Start != ParentI->end); 9354670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 9364670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 93744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 938631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen LRCalc[0].calculateValues(); 939c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen if (SpillMode) 940631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen LRCalc[1].calculateValues(); 94144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 9424670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen return Skipped; 9434670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen} 9444670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 945e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesenvoid SplitEditor::extendPHIKillRanges() { 946e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // Extend live ranges to be live-out for successor PHI values. 947a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 948a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 949e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen const VNInfo *PHIVNI = *I; 950e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 951e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen continue; 952e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 9531feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 954abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen LiveRangeCalc &LRC = getLRCalc(RegIdx); 955e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 956e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 957e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 958abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(*PI); 959abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen SlotIndex LastUse = End.getPrevSlot(); 960e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // The predecessor may not have a live-out value. That is OK, like an 961e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // undef PHI operand. 962abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen if (Edit->getParent().liveAt(LastUse)) { 963abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen assert(RegAssign.lookup(LastUse) == RegIdx && 964e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen "Different register assignment in phi predecessor"); 965631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen LRC.extend(LI, End); 966e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 967e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 968e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 969e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen} 970e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 971a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 9724670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenvoid SplitEditor::rewriteAssigned(bool ExtendRanges) { 973a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 974078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 9757466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineOperand &MO = RI.getOperand(); 9767466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 9777466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen ++RI; 9780f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // LiveDebugVariables should have handled all DBG_VALUE instructions. 9797466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen if (MI->isDebugValue()) { 9807466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen DEBUG(dbgs() << "Zapping " << *MI); 9817466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MO.setReg(0); 9827466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen continue; 9837466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 984a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 985b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // <undef> operands don't really read the register, so it doesn't matter 986b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // which register we choose. When the use operand is tied to a def, we must 987b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // use the same register as the def, so just do that always. 988078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI); 989b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen if (MO.isDef() || MO.isUndef()) 9902debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Idx = Idx.getRegSlot(MO.isEarlyClobber()); 9910f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 9920f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite to the mapped register at Idx. 9930f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned RegIdx = RegAssign.lookup(Idx); 9941feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 995abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen MO.setReg(LI->reg); 9960f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 9970f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':' << RegIdx << '\t' << *MI); 9980f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 9997cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Extend liveness to Idx if the instruction reads reg. 100081d686edbe6effe624add9394673bd571d89bfb7Jakob Stoklund Olesen if (!ExtendRanges || MO.isUndef()) 10017cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 10027cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 10037cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Skip instructions that don't read Reg. 10047cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (MO.isDef()) { 10057cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!MO.getSubReg() && !MO.isEarlyClobber()) 10067cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 10077cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // We may wan't to extend a live range for a partial redef, or for a use 10087cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // tied to an early clobber. 10097cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getPrevSlot(); 10107cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!Edit->getParent().liveAt(Idx)) 10117cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 10127cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen } else 10132debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Idx = Idx.getRegSlot(true); 10147cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 1015631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen getLRCalc(RegIdx).extend(LI, Idx.getNextSlot()); 10167466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 10177466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen} 10187466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 10195881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesenvoid SplitEditor::deleteRematVictims() { 10205881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen SmallVector<MachineInstr*, 8> Dead; 10212dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 10221feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(*I); 10232dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); 10242dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen LII != LIE; ++LII) { 10251f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen // Dead defs end at the dead slot. 10261f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen if (LII->end != LII->valno->def.getDeadSlot()) 10272dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 10282dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); 10292dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen assert(MI && "Missing instruction for dead def"); 10302dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MI->addRegisterDead(LI->reg, &TRI); 10315881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 10322dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen if (!MI->allDefsAreDead()) 10332dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 10345881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 10352dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << *MI); 10362dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen Dead.push_back(MI); 10372dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen } 10385881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen } 10395881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 10405881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (Dead.empty()) 10415881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen return; 10425881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 10438a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->eliminateDeadDefs(Dead); 10445881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen} 10455881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 10465928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesenvoid SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 10474670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumFinished; 10480f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 10490f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // At this point, the live intervals in Edit contain VNInfos corresponding to 10500f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // the inserted copies. 10510f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 10520f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Add the original defs from the parent interval. 1053a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), 1054a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen E = Edit->getParent().vni_end(); I != E; ++I) { 10550f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const VNInfo *ParentVNI = *I; 10569ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (ParentVNI->isUnused()) 10579ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen continue; 1058670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 1059b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen defValue(RegIdx, ParentVNI, ParentVNI->def); 106029ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen 1061393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // Force rematted values to be recomputed everywhere. 10624670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // The new live ranges may be truncated. 1063a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 1064a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1065393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(i, ParentVNI); 10665fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 1067c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 1068b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Hoist back-copies to the complement interval when in spill mode. 1069b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen switch (SpillMode) { 1070b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen case SM_Partition: 1071b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Leave all back-copies as is. 1072b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen break; 1073b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen case SM_Size: 1074b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen hoistCopiesForSize(); 1075b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen break; 1076b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen case SM_Speed: 1077b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen llvm_unreachable("Spill mode 'speed' not implemented yet"); 1078b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 1079b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 108044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Transfer the simply mapped values, check if any are skipped. 108144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen bool Skipped = transferValues(); 108244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Skipped) 10834670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen extendPHIKillRanges(); 10844670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen else 10854670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumSimple; 10864670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 10874670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // Rewrite virtual registers, possibly extending ranges. 108844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen rewriteAssigned(Skipped); 1089463a2977b1d9e6679f859db9f32e9e783b075c10Eric Christopher 10905881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Delete defs that were rematted everywhere. 109144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Skipped) 10925881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen deleteRematVictims(); 10935fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 10940253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Get rid of unused values and set phi-kill flags. 10951feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) { 10961feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval &LI = LIS.getInterval(*I); 10971feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LI.RenumberValues(); 10981feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey } 10990253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 11005928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Provide a reverse mapping from original indices to Edit ranges. 11015928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRMap) { 11025928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->clear(); 11035928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 11045928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->push_back(i); 11055928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 11065928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 11073a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Now check if any registers were separated into multiple components. 1108078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 1109a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 11103a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Don't use iterators, they are invalidated by create() below. 11111feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *li = &LIS.getInterval(Edit->get(i)); 11123a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen unsigned NumComp = ConEQ.Classify(li); 11133a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen if (NumComp <= 1) 11143a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen continue; 11153a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); 11163a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> dups; 11173a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen dups.push_back(li); 1118ae5fbeec23cff833cad9e6b2a638efd1f48bef49Matt Beaumont-Gay for (unsigned j = 1; j != NumComp; ++j) 1119e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey dups.push_back(&Edit->createEmptyInterval()); 11202254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen ConEQ.Distribute(&dups[0], MRI); 11215928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // The new intervals all map back to i. 11225928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRMap) 11235928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->resize(Edit->size(), i); 11243a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen } 11253a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen 112608e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen // Calculate spill weight and allocation hints for new intervals. 11274eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI); 11285928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 11295928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen assert(!LRMap || LRMap->size() == Edit->size()); 1130f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 1131f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 1132f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 11338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1134f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen// Single Block Splitting 1135f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1136f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 11372d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesenbool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, 11382d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen bool SingleInstrs) const { 11392d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Always split for multiple instructions. 11402d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (!BI.isOneInstr()) 11412d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return true; 11422d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Don't split for single instructions unless explicitly requested. 11432d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (!SingleInstrs) 11442d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return false; 11452d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Splitting a live-through range always makes progress. 11462d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (BI.LiveIn && BI.LiveOut) 11472d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return true; 11482d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // No point in isolating a copy. It has no register class constraints. 11492d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike()) 11502d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return false; 11512d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Finally, don't isolate an end point that was created by earlier splits. 11522d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return isOriginalEndpoint(BI.FirstInstr); 11532d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen} 11542d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen 1155fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 1156fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen openIntv(); 1157fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 1158fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr, 1159fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen LastSplitPoint)); 1160fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { 1161fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(SegStart, leaveIntvAfter(BI.LastInstr)); 1162fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } else { 1163fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // The last use is after the last valid split point. 1164fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 1165fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen useIntv(SegStart, SegStop); 1166fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(SegStop, BI.LastInstr); 1167fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 1168fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen} 1169fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 1170b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1171b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1172b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// Global Live Range Splitting Support 1173b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1174b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1175b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// These methods support a method of global live range splitting that uses a 1176b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// global algorithm to decide intervals for CFG edges. They will insert split 1177b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// points and color intervals in basic blocks while avoiding interference. 1178b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// 1179b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// Note that splitSingleBlock is also useful for blocks where both CFG edges 1180b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// are on the stack. 1181b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1182b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitLiveThroughBlock(unsigned MBBNum, 1183b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvIn, SlotIndex LeaveBefore, 1184b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvOut, SlotIndex EnterAfter){ 1185b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 1186b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); 1187b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1188b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop 1189b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ") intf " << LeaveBefore << '-' << EnterAfter 1190b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", live-through " << IntvIn << " -> " << IntvOut); 1191b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1192b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks"); 1193b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1194fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block"); 1195fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf"); 1196fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!EnterAfter || EnterAfter >= Start) && "Interference before block"); 1197fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen 1198fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); 1199fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen 1200b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (!IntvOut) { 1201b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill on entry.\n"); 1202b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1203b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<<<< Possible LeaveBefore interference. 1204b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1205b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // -____________ Spill on entry. 1206b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1207b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1208b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = leaveIntvAtTop(*MBB); 1209b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1210b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen (void)Idx; 1211b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1212b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1213b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1214b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (!IntvIn) { 1215b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", reload on exit.\n"); 1216b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1217b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>>>>> Possible EnterAfter interference. 1218b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1219b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ___________-- Reload on exit. 1220b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1221b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1222b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAtEnd(*MBB); 1223b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1224b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen (void)Idx; 1225b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1226b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1227b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1228b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { 1229b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", straight through.\n"); 1230b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1231b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1232b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ------------- Straight through, same intv, no interference. 1233b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1234b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1235b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Stop); 1236b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1237b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1238b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1239b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // We cannot legally insert splits after LSP. 1240b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(MBBNum); 1241fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf"); 1242b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1243b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || 1244b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { 1245b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", switch avoiding interference.\n"); 1246b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1247b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. 1248b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1249b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ------======= Switch intervals between interference. 1250b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1251b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1252fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen SlotIndex Idx; 1253fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen if (LeaveBefore && LeaveBefore < LSP) { 1254fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen Idx = enterIntvBefore(LeaveBefore); 1255fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen useIntv(Idx, Stop); 1256fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen } else { 1257fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen Idx = enterIntvAtEnd(*MBB); 1258fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen } 1259b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1260b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1261b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1262b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1263b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1264b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1265b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1266b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", create local intv for interference.\n"); 1267b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1268b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. 1269b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1270b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ==---------== Switch intervals before/after interference. 1271b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1272b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(LeaveBefore <= EnterAfter && "Missed case"); 1273b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1274b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1275b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAfter(EnterAfter); 1276b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1277b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1278b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1279b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1280b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen Idx = leaveIntvBefore(LeaveBefore); 1281b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1282b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1283b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1284b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1285b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1286b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 1287b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvIn, SlotIndex LeaveBefore) { 1288b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 1289b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1290b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1291b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1292fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1293b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", reg-in " << IntvIn << ", leave before " << LeaveBefore 1294b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << (BI.LiveOut ? ", stack-out" : ", killed in block")); 1295b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1296b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(IntvIn && "Must have register in"); 1297b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(BI.LiveIn && "Must be live-in"); 1298b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference"); 1299b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1300fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { 1301b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << " before interference.\n"); 1302b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1303b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<< Interference after kill. 1304b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---x | Killed in block. 1305b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ========= Use IntvIn everywhere. 1306b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1307b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1308fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(Start, BI.LastInstr); 1309b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1310b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1311b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1312b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1313b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1314fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { 1315b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1316b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<< Possible interference after last use. 1317b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-out on stack. 1318b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =========____ Leave IntvIn after last use. 1319b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1320b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // < Interference after last use. 1321b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o--o| Live-out on stack, late last use. 1322b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ============ Copy to stack after LSP, overlap IntvIn. 1323b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // \_____ Stack interval is live-out. 1324b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1325fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (BI.LastInstr < LSP) { 1326b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill after last use before interference.\n"); 1327b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1328fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex Idx = leaveIntvAfter(BI.LastInstr); 1329b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1330b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1331b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } else { 1332b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill before last split point.\n"); 1333b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1334af4e40c2f41a7d60b86958e034b00542d551b5f2Jakob Stoklund Olesen SlotIndex Idx = leaveIntvBefore(LSP); 1335fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(Idx, BI.LastInstr); 1336b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1337b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1338b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1339b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1340b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1341b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1342b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // The interference is overlapping somewhere we wanted to use IntvIn. That 1343b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // means we need to create a local interval that can be allocated a 1344b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // different register. 1345b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned LocalIntv = openIntv(); 1346f9d7fb6b3c45abc64ad52cd8a9a8a7dd5aa9f4bbMatt Beaumont-Gay (void)LocalIntv; 1347b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n"); 1348b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1349fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastInstr < LSP) { 1350b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1351b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<< Interference overlapping uses. 1352b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-out on stack. 1353b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =====----____ Leave IntvIn before interference, then spill. 1354b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1355fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex To = leaveIntvAfter(BI.LastInstr); 1356b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(LeaveBefore); 1357b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, To); 1358b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1359b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, From); 1360b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1361b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1362b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1363b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1364b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<< Interference overlapping uses. 1365b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o--o| Live-out on stack, late last use. 1366b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =====------- Copy to stack before LSP, overlap LocalIntv. 1367b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // \_____ Stack interval is live-out. 1368b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1369b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex To = leaveIntvBefore(LSP); 1370fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(To, BI.LastInstr); 1371b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); 1372b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, To); 1373b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1374b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, From); 1375b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1376b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1377b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1378b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 1379b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvOut, SlotIndex EnterAfter) { 1380b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 1381b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1382b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1383b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1384fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1385b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", reg-out " << IntvOut << ", enter after " << EnterAfter 1386b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << (BI.LiveIn ? ", stack-in" : ", defined in block")); 1387b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1388b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1389b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1390b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(IntvOut && "Must have register out"); 1391b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(BI.LiveOut && "Must be live-out"); 1392b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || EnterAfter < LSP) && "Bad interference"); 1393b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1394fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { 1395b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << " after interference.\n"); 1396b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1397b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> Interference before def. 1398b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // | o---o---| Defined in block. 1399b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ========= Use IntvOut everywhere. 1400b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1401b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1402fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(BI.FirstInstr, Stop); 1403b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1404b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1405b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1406fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { 1407b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", reload after interference.\n"); 1408b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1409b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> Interference before def. 1410b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-through, stack-in. 1411b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ____========= Enter IntvOut before first use. 1412b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1413b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1414fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr)); 1415b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1416b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1417b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1418b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1419b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1420b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // The interference is overlapping somewhere we wanted to use IntvOut. That 1421b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // means we need to create a local interval that can be allocated a 1422b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // different register. 1423b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", interference overlaps uses.\n"); 1424b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1425b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>>>>> Interference overlapping uses. 1426b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-through, stack-in. 1427b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ____---====== Create local interval for interference range. 1428b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1429b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1430b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAfter(EnterAfter); 1431b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1432b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1433b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1434b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen openIntv(); 1435fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr)); 1436b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, Idx); 1437b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1438