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 158ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "SplitKit.h" 164670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 178ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 18789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 19de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/CodeGen/MachineBlockFrequencyInfo.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 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "regalloc" 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 344670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund OlesenSTATISTIC(NumFinished, "Number of splits finished"); 354670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund OlesenSTATISTIC(NumSimple, "Number of splits that were simple"); 36e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumCopies, "Number of copies inserted for splitting"); 37e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumRemats, "Number of rematerialized defs for splitting"); 38bdda37d7fbafe6876f248341837423a4100f95a5Jakob Stoklund OlesenSTATISTIC(NumRepairs, "Number of invalid live ranges repaired"); 394670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 408ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 41de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// Last Insert Point Analysis 428ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 438ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 44de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarInsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis, 45de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned BBNum) 46de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : LIS(lis), LastInsertPoint(BBNum) {} 478ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 48de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarSlotIndex 49de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarInsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI, 50de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const MachineBasicBlock &MBB) { 51de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Num = MBB.getNumber(); 52de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num]; 53de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB); 548ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 55de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<const MachineBasicBlock *, 1> EHPadSucessors; 56de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const MachineBasicBlock *SMBB : MBB.successors()) 57de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (SMBB->isEHPad()) 58de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar EHPadSucessors.push_back(SMBB); 591a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 60de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Compute insert points on the first call. The pair is independent of the 611a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // current live interval. 62de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!LIP.first.isValid()) { 63de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator(); 64de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (FirstTerm == MBB.end()) 65de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LIP.first = MBBEnd; 661a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen else 67de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LIP.first = LIS.getInstructionIndex(*FirstTerm); 681a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 691a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // If there is a landing pad successor, also find the call instruction. 70de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (EHPadSucessors.empty()) 71de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return LIP.first; 721a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // There may not be a call instruction (?) in which case we ignore LPad. 73de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LIP.second = LIP.first; 74de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (MachineBasicBlock::const_iterator I = MBB.end(), E = MBB.begin(); 751e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen I != E;) { 761e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen --I; 775a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (I->isCall()) { 78de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LIP.second = LIS.getInstructionIndex(*I); 791a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen break; 801a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 811e0bd63477da6e9b1dc5111bafba2b1cf143bfbaJakob Stoklund Olesen } 821a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 831a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 84de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If CurLI is live into a landing pad successor, move the last insert point 851a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // back to the call that may throw. 86de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!LIP.second) 87de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return LIP.first; 88de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 89de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (none_of(EHPadSucessors, [&](const MachineBasicBlock *EHPad) { 90de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return LIS.isLiveInToMBB(CurLI, EHPad); 91de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar })) 92de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return LIP.first; 932aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen 942aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // Find the value leaving MBB. 95de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd); 962aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen if (!VNI) 97de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return LIP.first; 982aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen 992aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // If the value leaving MBB was defined after the call in MBB, it can't 1002aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // really be live-in to the landing pad. This can happen if the landing pad 1012aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // has a PHI, and this register is undef on the exceptional edge. 1022aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // <rdar://problem/10664933> 103de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd) 104de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return LIP.first; 1052aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen 1062aad2f6e601328d15033944ea51ad6f66a7f3c0aJakob Stoklund Olesen // Value is properly live-in to the landing pad. 107de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Only allow inserts before the call. 108de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return LIP.second; 1096a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen} 1106a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 11174c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund OlesenMachineBasicBlock::iterator 112de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarInsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI, 113de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineBasicBlock &MBB) { 114de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SlotIndex LIP = getLastInsertPoint(CurLI, MBB); 115de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (LIP == LIS.getMBBEndIdx(&MBB)) 116de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return MBB.end(); 117de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return LIS.getInstructionFromIndex(LIP); 118de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 119de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 120de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===----------------------------------------------------------------------===// 121de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// Split Analysis 122de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===----------------------------------------------------------------------===// 123de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 124de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarSplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, 125de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const MachineLoopInfo &mli) 126de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli), 127de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TII(*MF.getSubtarget().getInstrInfo()), CurLI(nullptr), 128de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IPA(lis, MF.getNumBlockIDs()) {} 129de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 130de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid SplitAnalysis::clear() { 131de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UseSlots.clear(); 132de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UseBlocks.clear(); 133de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ThroughBlocks.clear(); 134de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar CurLI = nullptr; 135de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DidRepairRange = false; 13674c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen} 13774c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen 138078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// analyzeUses - Count instructions, basic blocks, and loops using CurLI. 139abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesenvoid SplitAnalysis::analyzeUses() { 140a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen assert(UseSlots.empty() && "Call clear first"); 141a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 142a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // First get all the defs from the interval values. This provides the correct 143a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // slots for early clobbers. 144ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (const VNInfo *VNI : CurLI->valnos) 145ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!VNI->isPHIDef() && !VNI->isUnused()) 146ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines UseSlots.push_back(VNI->def); 147a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 148a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // Get use slots form the use-def chain. 149078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineRegisterInfo &MRI = MF.getRegInfo(); 15036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg)) 15136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!MO.isUndef()) 152de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot()); 153a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 154b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen array_pod_sort(UseSlots.begin(), UseSlots.end()); 1552b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 156a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // Remove duplicates, keeping the smaller slot for each instruction. 157a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen // That is what we want for early clobbers. 158a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), 159a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen SlotIndex::isSameInstr), 160a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen UseSlots.end()); 161a2948ef5accab638371615f539ea9f9ec5ff5d03Jakob Stoklund Olesen 1622b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // Compute per-live block info. 1632b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen if (!calcLiveBlockInfo()) { 1642b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen // FIXME: calcLiveBlockInfo found inconsistencies in the live range. 1655b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola // I am looking at you, RegisterCoalescer! 1667d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen DidRepairRange = true; 167bdda37d7fbafe6876f248341837423a4100f95a5Jakob Stoklund Olesen ++NumRepairs; 1682b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); 1692b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen const_cast<LiveIntervals&>(LIS) 1702b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen .shrinkToUses(const_cast<LiveInterval*>(CurLI)); 171db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.clear(); 172db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ThroughBlocks.clear(); 1732b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen bool fixed = calcLiveBlockInfo(); 1742b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen (void)fixed; 1752b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen assert(fixed && "Couldn't fix broken live interval"); 1762b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen } 1772b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen 178ef1f5ccca7efaa18209523b31019d356d302f635Jakob Stoklund Olesen DEBUG(dbgs() << "Analyze counted " 179db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen << UseSlots.size() << " instrs in " 180db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen << UseBlocks.size() << " blocks, through " 181f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen << NumThroughBlocks << " blocks.\n"); 1828ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 1838ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 184f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 185f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen/// where CurLI is live. 1862b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesenbool SplitAnalysis::calcLiveBlockInfo() { 187f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen ThroughBlocks.resize(MF.getNumBlockIDs()); 188a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen NumThroughBlocks = NumGapBlocks = 0; 189f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen if (CurLI->empty()) 1902b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 191f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 192f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVI = CurLI->begin(); 193f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen LiveInterval::const_iterator LVE = CurLI->end(); 194f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 195f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 196f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseI = UseSlots.begin(); 197f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen UseE = UseSlots.end(); 198f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 199f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Loop over basic blocks where CurLI is live. 200f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineFunction::iterator MFI = 201f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LIS.getMBBFromIndex(LVI->start)->getIterator(); 202f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen for (;;) { 203f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen BlockInfo BI; 204f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BI.MBB = &*MFI; 2056c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen SlotIndex Start, Stop; 20636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 207f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 208a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // If the block contains no uses, the range must be live through. At one 2095b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola // point, RegisterCoalescer could create dangling ranges that ended 210a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // mid-block. 211a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (UseI == UseE || *UseI >= Stop) { 212a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen ++NumThroughBlocks; 213a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen ThroughBlocks.set(BI.MBB->getNumber()); 214a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // The range shouldn't end mid-block if there are no uses. This shouldn't 215a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // happen. 216a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (LVI->end < Stop) 217a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen return false; 218a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } else { 219a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // This block has uses. Find the first and last uses in the block. 220fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.FirstInstr = *UseI; 221fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen assert(BI.FirstInstr >= Start); 222f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen do ++UseI; 2236c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen while (UseI != UseE && *UseI < Stop); 224fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LastInstr = UseI[-1]; 225fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen assert(BI.LastInstr < Stop); 226f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 227a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // LVI is the first live segment overlapping MBB. 228a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveIn = LVI->start <= Start; 229a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen 23077ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen // When not live in, the first use should be a def. 23177ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen if (!BI.LiveIn) { 232331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert(LVI->start == LVI->valno->def && "Dangling Segment start"); 233fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen assert(LVI->start == BI.FirstInstr && "First instr should be a def"); 234fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.FirstDef = BI.FirstInstr; 23577ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen } 23677ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen 237a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // Look for gaps in the live range. 238a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = true; 239a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen while (LVI->end < Stop) { 240a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen SlotIndex LastStop = LVI->end; 241a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (++LVI == LVE || LVI->start >= Stop) { 242a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = false; 243fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.LastInstr = LastStop; 244a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen break; 245a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } 24677ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen 247a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (LastStop < LVI->start) { 248a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // There is a gap in the live range. Create duplicate entries for the 249a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // live-in snippet and the live-out snippet. 250a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen ++NumGapBlocks; 251a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen 252a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // Push the Live-in part. 253a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = false; 254a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen UseBlocks.push_back(BI); 255fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen UseBlocks.back().LastInstr = LastStop; 256a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen 257a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // Set up BI for the live-out part. 258a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveIn = false; 259a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen BI.LiveOut = true; 260fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen BI.FirstInstr = BI.FirstDef = LVI->start; 261a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } 26277ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen 263331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // A Segment that starts in the middle of the block must be a def. 264331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert(LVI->start == LVI->valno->def && "Dangling Segment start"); 26577ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen if (!BI.FirstDef) 26677ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen BI.FirstDef = LVI->start; 267f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 268f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 269db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen UseBlocks.push_back(BI); 270626d6fb1903e74337b257c5e165944bcd1273e65Jakob Stoklund Olesen 271a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen // LVI is now at LVE or LVI->end >= Stop. 272a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen if (LVI == LVE) 273a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen break; 274a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen } 275f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 276f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Live segment ends exactly at Stop. Move to the next segment. 2776c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (LVI->end == Stop && ++LVI == LVE) 278f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen break; 279f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 280f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Pick the next basic block. 2816c8afd728eb02742ce320ecd39bcf3774d8423b7Jakob Stoklund Olesen if (LVI->start < Stop) 282f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen ++MFI; 283f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen else 284f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MFI = LIS.getMBBFromIndex(LVI->start)->getIterator(); 285f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen } 286b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen 287b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count"); 2882b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen return true; 289f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen} 290f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 2919f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesenunsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { 2929f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (cli->empty()) 2939f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen return 0; 2949f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval *li = const_cast<LiveInterval*>(cli); 2959f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval::iterator LVI = li->begin(); 2969f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LiveInterval::iterator LVE = li->end(); 2979f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen unsigned Count = 0; 2989f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 2999f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen // Loop over basic blocks where li is live. 300f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineFunction::const_iterator MFI = 301f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LIS.getMBBFromIndex(LVI->start)->getIterator(); 302f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar SlotIndex Stop = LIS.getMBBEndIdx(&*MFI); 3039f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen for (;;) { 3049f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen ++Count; 3059f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen LVI = li->advanceTo(LVI, Stop); 3069f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen if (LVI == LVE) 3079f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen return Count; 3089f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen do { 3099f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen ++MFI; 310f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Stop = LIS.getMBBEndIdx(&*MFI); 3119f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } while (Stop <= LVI->start); 3129f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen } 3139f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen} 3149f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 31506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesenbool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { 31606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen unsigned OrigReg = VRM.getOriginal(CurLI->reg); 31706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen const LiveInterval &Orig = LIS.getInterval(OrigReg); 31806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen assert(!Orig.empty() && "Splitting empty interval?"); 31906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen LiveInterval::const_iterator I = Orig.find(Idx); 32006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 32106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range containing Idx should begin at Idx. 32206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen if (I != Orig.end() && I->start <= Idx) 32306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I->start == Idx; 32406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 32506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen // Range does not contain Idx, previous must end at Idx. 32606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen return I != Orig.begin() && (--I)->end == Idx; 32706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen} 32806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 3298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::analyze(const LiveInterval *li) { 3308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen clear(); 331078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen CurLI = li; 332abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen analyzeUses(); 3338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 3348ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 335697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen 336f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 3371c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen// Split Editor 3381407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 3391407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 3401c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 341de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarSplitEditor::SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa, 342de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveIntervals &lis, VirtRegMap &vrm, 3434eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer MachineDominatorTree &mdt, 3444eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer MachineBlockFrequencyInfo &mbfi) 345de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : SA(sa), AA(aa), LIS(lis), VRM(vrm), 346de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MRI(vrm.getMachineFunction().getRegInfo()), MDT(mdt), 347de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()), 34837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()), 34937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition), 35037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegAssign(Allocator) {} 351bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 352708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesenvoid SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { 353708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen Edit = &LRE; 354708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SpillMode = SM; 355bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen OpenIdx = 0; 356bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen RegAssign.clear(); 357bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen Values.clear(); 358c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen 359c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen // Reset the LiveRangeCalc instances needed for this spill mode. 360631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, 361631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen &LIS.getVNInfoAllocator()); 362c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen if (SpillMode) 363631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, 364631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen &LIS.getVNInfoAllocator()); 365bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen 3661c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // We don't need an AliasAnalysis since we will only be performing 3671c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // cheap-as-a-copy remats anyway. 368dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Edit->anyRematerializable(nullptr); 3691c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen} 3701c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 371b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 372de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarLLVM_DUMP_METHOD void SplitEditor::dump() const { 3731c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (RegAssign.empty()) { 3741c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " empty\n"; 3751c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 3761c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 3771c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3781c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) 3791c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); 3801c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen dbgs() << '\n'; 381b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen} 38277e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 383b3e9681cc0ea2d52a1f8cd09880656780dce4073Jakob Stoklund Olesen 3841c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund OlesenVNInfo *SplitEditor::defValue(unsigned RegIdx, 3851c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const VNInfo *ParentVNI, 3861c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx) { 3871c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 3881c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(Idx.isValid() && "Invalid SlotIndex"); 389a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); 3901feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 3911c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3921c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Create a new value. 3933b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator()); 3941c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 3951c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Use insert for lookup, so we can add missing values with a second lookup. 3961c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen std::pair<ValueMap::iterator, bool> InsP = 397393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), 398393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen ValueForcePair(VNI, false))); 3991c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4001c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was the first time (RegIdx, ParentVNI) was mapped. 4011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Keep it as a simple def without any liveness. 4021c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen if (InsP.second) 4031c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 4041c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // If the previous value was a simple mapping, add liveness for it now. 406393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (VNInfo *OldVNI = InsP.first->second.getPointer()) { 4071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = OldVNI->def; 408331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), OldVNI)); 409393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // No longer a simple mapping. Switch to a complex, non-forced mapping. 410393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen InsP.first->second = ValueForcePair(); 4111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen } 4121c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is a complex mapping, add liveness for VNI 4141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 415331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI)); 4161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return VNI; 4189ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen} 4199ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 420393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesenvoid SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) { 4211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen assert(ParentVNI && "Mapping NULL value"); 422393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)]; 423393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen VNInfo *VNI = VFP.getPointer(); 4241c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 425393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // ParentVNI was either unmapped or already complex mapped. Either way, just 426393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // set the force bit. 427393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (!VNI) { 428393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen VFP.setInt(true); 4291c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen return; 430393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen } 4311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 4321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This was previously a single mapping. Make sure the old def is represented 4331c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by a trivial live range. 4341c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Def = VNI->def; 4351feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 436331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI)); 437393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // Mark as complex mapped, forced. 438dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines VFP = ValueForcePair(nullptr, true); 439e5a2e366322ef5f0d597b1fb8dbf55f2cf36cf15Jakob Stoklund Olesen} 440e5a2e366322ef5f0d597b1fb8dbf55f2cf36cf15Jakob Stoklund Olesen 4410f43811903f10394f7088f4634c0b4f9668cbac0Eric ChristopherVNInfo *SplitEditor::defFromParent(unsigned RegIdx, 442cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 443cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 444cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 445cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I) { 446dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineInstr *CopyMI = nullptr; 447cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex Def; 4481feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 449cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 450bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen // We may be trying to avoid interference that ends at a deleted instruction, 451bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen // so always begin RegIdx 0 early and all others late. 452bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen bool Late = RegIdx != 0; 453bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen 454cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Attempt cheap-as-a-copy rematerialization. 455de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Original = VRM.getOriginal(Edit->get(RegIdx)); 456de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveInterval &OrigLI = LIS.getInterval(Original); 457de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx); 458cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 459de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def); 460de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 461de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) { 4628a06af96698537377275dd7848db69915638dd26Pete Cooper Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late); 463e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumRemats; 464cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } else { 465cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Can't remat, just insert a copy from parent. 4660f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) 467a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen .addReg(Edit->getReg()); 468de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Def = LIS.getSlotIndexes() 469de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ->insertMachineInstrInMaps(*CopyMI, Late) 470de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar .getRegSlot(); 471e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumCopies; 472cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen } 473cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 474cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen // Define the value in Reg. 4753b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen return defValue(RegIdx, ParentVNI, Def); 476cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen} 477cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 478f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen/// Create a new virtual register and live interval. 479e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesenunsigned SplitEditor::openIntv() { 4800f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the complement as index 0. 481a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->empty()) 482e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey Edit->createEmptyInterval(); 4830f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 4840f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Create the open interval. 485a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen OpenIdx = Edit->size(); 486e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey Edit->createEmptyInterval(); 487e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen return OpenIdx; 488e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen} 489e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 490e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesenvoid SplitEditor::selectIntv(unsigned Idx) { 491e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen assert(Idx != 0 && "Cannot select the complement interval"); 492e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen assert(Idx < Edit->size() && "Can only select previously opened interval"); 49387360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); 494e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen OpenIdx = Idx; 495f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 496f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 497207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { 4980f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvBefore"); 4999b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " enterIntvBefore " << Idx); 500207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 501a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 502f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5039b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 504207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Idx; 505f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 506207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 507078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 508f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen assert(MI && "enterIntvBefore called with invalid index"); 509cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 510207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); 511207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 512f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 513f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 51487360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { 51587360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before enterIntvAfter"); 51687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAfter " << Idx); 51787360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen Idx = Idx.getBoundaryIndex(); 51887360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 51987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen if (!ParentVNI) { 52087360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 52187360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen return Idx; 52287360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen } 52387360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 52487360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 52587360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen assert(MI && "enterIntvAfter called with invalid index"); 52687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen 52787360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), 52836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::next(MachineBasicBlock::iterator(MI))); 52987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen return VNI->def; 53087360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen} 53187360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen 532207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { 5330f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); 534207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(&MBB); 535207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex Last = End.getPrevSlot(); 536207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); 537a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); 538f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5399b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 540207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return End; 541f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 5429b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id); 543207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, 54474c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen SA.getLastSplitPointIter(&MBB)); 545207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen RegAssign.insert(VNI->def, End, OpenIdx); 5460f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 547207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 548f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 549f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 550078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen/// useIntv - indicate that all instructions in MBB should use OpenLI. 5517536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(const MachineBasicBlock &MBB) { 552078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); 553f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 554f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 5557536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesenvoid SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 5560f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before useIntv"); 5570f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); 5580f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, End, OpenIdx); 5590f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 560f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 561f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 562207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { 5630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAfter"); 5649b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAfter " << Idx); 565f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 566f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen // The interval must be live beyond the instruction at Idx. 567ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen SlotIndex Boundary = Idx.getBoundaryIndex(); 568ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary); 569f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 5709b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 571ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen return Boundary.getNextSlot(); 572f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen } 573207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 574ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Boundary); 57501cb34b0111a1e8792f327b56c51bc3bbaf83acaJakob Stoklund Olesen assert(MI && "No instruction at index"); 576ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen 577ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // In spill mode, make live ranges as short as possible by inserting the copy 578ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // before MI. This is only possible if that instruction doesn't redefine the 579ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // value. The inserted COPY is not a kill, and we don't need to recompute 580ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen // the source live range. The spiller also won't try to hoist this copy. 581ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) && 582ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen MI->readsVirtualRegister(Edit->getReg())) { 583ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen forceRecompute(0, ParentVNI); 584ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 585ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen return Idx; 586ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen } 587ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen 588ebac0c1747d20e48f359d76dd454444107080d83Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(), 58936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::next(MachineBasicBlock::iterator(MI))); 590207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 591f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen} 592f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 5939b057771ba22441b8d312404204433477b4be657Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { 5949b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before leaveIntvBefore"); 5959b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvBefore " << Idx); 5969b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 5979b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen // The interval must be live into the instruction at Idx. 598fc47933db5c8fea9bc89470d83cc5af7ca36f2a3Jakob Stoklund Olesen Idx = Idx.getBaseIndex(); 599a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); 6009b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen if (!ParentVNI) { 6019b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 6029b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return Idx.getNextSlot(); 6039b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen } 6049b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); 6059b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 6069b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Idx); 6079b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen assert(MI && "No instruction at index"); 6089b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); 6099b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen return VNI->def; 6109b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen} 6119b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 612207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund OlesenSlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 6130f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); 614078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen SlotIndex Start = LIS.getMBBStartIdx(&MBB); 6159b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); 6167536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 617a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 618f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen if (!ParentVNI) { 6199b24afe41e06572f901edf2e78ef71fb228db29eJakob Stoklund Olesen DEBUG(dbgs() << ": not live\n"); 620207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return Start; 6217536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen } 6227536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 6230f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, 624cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MBB.SkipPHIsAndLabels(MBB.begin())); 6250f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssign.insert(Start, VNI->def, OpenIdx); 6260f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dump()); 627207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen return VNI->def; 628f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 629f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 6305c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesenvoid SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { 6315c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(OpenIdx && "openIntv not called before overlapIntv"); 632a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); 633194eb71a11a77c7fb576780783a77e64924dfb10Jakob Stoklund Olesen assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) && 6345c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Parent changes value in extended range"); 6355c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && 6365c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen "Range cannot span basic blocks"); 6375c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 638abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen // The complement interval will be extended as needed by LRCalc.extend(). 639b3dd82670aa60cacba81f090d292722c3ef44354Jakob Stoklund Olesen if (ParentVNI) 640393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(0, ParentVNI); 6415c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); 6425c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen RegAssign.insert(Start, End, OpenIdx); 6435c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen DEBUG(dump()); 6445c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen} 6455c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 646b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen//===----------------------------------------------------------------------===// 647b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen// Spill modes 648b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen//===----------------------------------------------------------------------===// 649b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 650b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesenvoid SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) { 6511feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(0)); 652b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n"); 653b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen RegAssignMap::iterator AssignI; 654b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen AssignI.setMap(RegAssign); 655b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 656b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 657ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SlotIndex Def = Copies[i]->def; 658b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(Def); 659b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen assert(MI && "No instruction for back-copy"); 660b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 661b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock *MBB = MI->getParent(); 662b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock::iterator MBBI(MI); 663b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen bool AtBegin; 664b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen do AtBegin = MBBI == MBB->begin(); 665b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen while (!AtBegin && (--MBBI)->isDebugValue()); 666b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 667b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Removing " << Def << '\t' << *MI); 668ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LIS.removeVRegDefAt(*LI, Def); 669de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LIS.RemoveMachineInstrFromMaps(*MI); 670b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MI->eraseFromParent(); 671b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 672ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Adjust RegAssign if a register assignment is killed at Def. We want to 673ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // avoid calculating the live range of the source register if possible. 6741599a64277f3a01619b5614974be9bec662c7ec0Jakob Stoklund Olesen AssignI.find(Def.getPrevSlot()); 675b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!AssignI.valid() || AssignI.start() >= Def) 676b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 677b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // If MI doesn't kill the assigned register, just leave it. 678b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (AssignI.stop() != Def) 679b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 680b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen unsigned RegIdx = AssignI.value(); 681b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) { 682b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx << '\n'); 683393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def)); 684b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } else { 685de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SlotIndex Kill = LIS.getInstructionIndex(*MBBI).getRegSlot(); 686b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI); 687b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen AssignI.setStop(Kill); 688b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 689b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 690b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen} 691b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 692c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund OlesenMachineBasicBlock* 693c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund OlesenSplitEditor::findShallowDominator(MachineBasicBlock *MBB, 694c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *DefMBB) { 695c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (MBB == DefMBB) 696c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return MBB; 697c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def."); 698c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 699c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen const MachineLoopInfo &Loops = SA.Loops; 700c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB); 701c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineDomTreeNode *DefDomNode = MDT[DefMBB]; 702c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 703c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Best candidate so far. 704c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *BestMBB = MBB; 705c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen unsigned BestDepth = UINT_MAX; 706c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 707c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen for (;;) { 708c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen const MachineLoop *Loop = Loops.getLoopFor(MBB); 709c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 710c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // MBB isn't in a loop, it doesn't get any better. All dominators have a 711c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // higher frequency by definition. 712c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (!Loop) { 713c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 714c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen << MBB->getNumber() << " at depth 0\n"); 715c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return MBB; 716c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 717c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 718c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // We'll never be able to exit the DefLoop. 719c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (Loop == DefLoop) { 720c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 721c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen << MBB->getNumber() << " in the same loop\n"); 722c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return MBB; 723c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 724c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 725c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Least busy dominator seen so far. 726c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen unsigned Depth = Loop->getLoopDepth(); 727c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (Depth < BestDepth) { 728c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen BestMBB = MBB; 729c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen BestDepth = Depth; 730c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" 731c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen << MBB->getNumber() << " at depth " << Depth << '\n'); 732c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 733c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 734c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Leave loop by going to the immediate dominator of the loop header. 735c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // This is a bigger stride than simply walking up the dominator tree. 736c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom(); 737c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 738c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Too far up the dominator tree? 739c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen if (!IDom || !MDT.dominates(DefDomNode, IDom)) 740c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen return BestMBB; 741c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 742c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MBB = IDom->getBlock(); 743c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen } 744c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen} 745c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 746de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid SplitEditor::computeRedundantBackCopies( 747de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) { 748de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveInterval *LI = &LIS.getInterval(Edit->get(0)); 749de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveInterval *Parent = &Edit->getParent(); 750de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums()); 751de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallPtrSet<VNInfo *, 8> DominatedVNIs; 752de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 753de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Aggregate VNIs having the same value as ParentVNI. 754de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (VNInfo *VNI : LI->valnos) { 755de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (VNI->isUnused()) 756de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 757de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); 758de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar EqualVNs[ParentVNI->id].insert(VNI); 759de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 760de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 761de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // For VNI aggregation of each ParentVNI, collect dominated, i.e., 762de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // redundant VNIs to BackCopies. 763de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { 764de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VNInfo *ParentVNI = Parent->getValNumInfo(i); 765de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!NotToHoistSet.count(ParentVNI->id)) 766de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 767de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin(); 768de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallPtrSetIterator<VNInfo *> It2 = It1; 769de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) { 770de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar It2 = It1; 771de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) { 772de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2)) 773de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 774de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 775de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def); 776de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def); 777de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (MBB1 == MBB2) { 778de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1)); 779de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else if (MDT.dominates(MBB1, MBB2)) { 780de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DominatedVNIs.insert(*It2); 781de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else if (MDT.dominates(MBB2, MBB1)) { 782de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DominatedVNIs.insert(*It1); 783de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 784de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 785de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 786de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!DominatedVNIs.empty()) { 787de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar forceRecompute(0, ParentVNI); 788de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto VNI : DominatedVNIs) { 789de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BackCopies.push_back(VNI); 790de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 791de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DominatedVNIs.clear(); 792de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 793de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 794de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 795de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 796de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// For SM_Size mode, find a common dominator for all the back-copies for 797de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// the same ParentVNI and hoist the backcopies to the dominator BB. 798de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// For SM_Speed mode, if the common dominator is hot and it is not beneficial 799de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// to do the hoisting, simply remove the dominated backcopies for the same 800de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// ParentVNI. 801de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid SplitEditor::hoistCopies() { 802b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Get the complement interval, always RegIdx 0. 8031feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(0)); 804b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen LiveInterval *Parent = &Edit->getParent(); 805b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 806b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Track the nearest common dominator for all back-copies for each ParentVNI, 807b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // indexed by ParentVNI->id. 808b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair; 809b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums()); 810de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The total cost of all the back-copies for each ParentVNI. 811de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums()); 812de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The ParentVNI->id set for which hoisting back-copies are not beneficial 813de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // for Speed. 814de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DenseSet<unsigned> NotToHoistSet; 815b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 816b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Find the nearest common dominator for parent values with multiple 817b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // back-copies. If a single back-copy dominates, put it in DomPair.second. 818ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (VNInfo *VNI : LI->valnos) { 8191599a64277f3a01619b5614974be9bec662c7ec0Jakob Stoklund Olesen if (VNI->isUnused()) 8201599a64277f3a01619b5614974be9bec662c7ec0Jakob Stoklund Olesen continue; 821b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); 822b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen assert(ParentVNI && "Parent not live at complement def"); 823b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 824b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Don't hoist remats. The complement is probably going to disappear 825b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // completely anyway. 826b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 827b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 828b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 829b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def); 830de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 831b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DomPair &Dom = NearestDom[ParentVNI->id]; 832b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 833b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Keep directly defined parent values. This is either a PHI or an 834b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // instruction in the complement range. All other copies of ParentVNI 835b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // should be eliminated. 836b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (VNI->def == ParentVNI->def) { 837b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n'); 838b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(ValMBB, VNI->def); 839b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 840b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 841b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Skip the singly mapped values. There is nothing to gain from hoisting a 842b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // single back-copy. 843393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) { 844b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n'); 845b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 846b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 847b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 848b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.first) { 849b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // First time we see ParentVNI. VNI dominates itself. 850b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(ValMBB, VNI->def); 851b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } else if (Dom.first == ValMBB) { 852b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Two defs in the same block. Pick the earlier def. 853b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.second.isValid() || VNI->def < Dom.second) 854b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom.second = VNI->def; 855b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } else { 856b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Different basic blocks. Check if one dominates. 857b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MachineBasicBlock *Near = 858b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen MDT.findNearestCommonDominator(Dom.first, ValMBB); 859b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (Near == ValMBB) 860b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Def ValMBB dominates. 861b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(ValMBB, VNI->def); 862b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen else if (Near != Dom.first) 863b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // None dominate. Hoist to common dominator, need new def. 864b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom = DomPair(Near, SlotIndex()); 865de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB); 866b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 867b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 868b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def 869b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen << " for parent " << ParentVNI->id << '@' << ParentVNI->def 870b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen << " hoist to BB#" << Dom.first->getNumber() << ' ' 871b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen << Dom.second << '\n'); 872b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 873b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 874b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Insert the hoisted copies. 875b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { 876b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen DomPair &Dom = NearestDom[i]; 877b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen if (!Dom.first || Dom.second.isValid()) 878b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 879c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // This value needs a hoisted copy inserted at the end of Dom.first. 880c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen VNInfo *ParentVNI = Parent->getValNumInfo(i); 881c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def); 882c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen // Get a less loopy dominator than Dom.first. 883c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen Dom.first = findShallowDominator(Dom.first, DefMBB); 884de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (SpillMode == SM_Speed && 885de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) { 886de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NotToHoistSet.insert(ParentVNI->id); 887de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 888de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 889b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot(); 890b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen Dom.second = 891c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen defFromParent(0, ParentVNI, Last, *Dom.first, 89274c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen SA.getLastSplitPointIter(Dom.first))->def; 893b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 894b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 895b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Remove redundant back-copies that are now known to be dominated by another 896b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // def with the same value. 897b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen SmallVector<VNInfo*, 8> BackCopies; 898ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (VNInfo *VNI : LI->valnos) { 8991599a64277f3a01619b5614974be9bec662c7ec0Jakob Stoklund Olesen if (VNI->isUnused()) 9001599a64277f3a01619b5614974be9bec662c7ec0Jakob Stoklund Olesen continue; 901b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); 902b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen const DomPair &Dom = NearestDom[ParentVNI->id]; 903de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Dom.first || Dom.second == VNI->def || 904de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NotToHoistSet.count(ParentVNI->id)) 905b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen continue; 906b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen BackCopies.push_back(VNI); 907393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(0, ParentVNI); 908b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 909de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 910de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If it is not beneficial to hoist all the BackCopies, simply remove 911de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // redundant BackCopies in speed mode. 912de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (SpillMode == SM_Speed && !NotToHoistSet.empty()) 913de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar computeRedundantBackCopies(NotToHoistSet, BackCopies); 914de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 915b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen removeBackCopies(BackCopies); 916b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen} 917b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 918b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 91944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen/// transferValues - Transfer all possible values to the new live ranges. 920abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen/// Values that were rematerialized are left alone, they need LRCalc.extend(). 92144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesenbool SplitEditor::transferValues() { 9224670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool Skipped = false; 9234670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegAssignMap::const_iterator AssignI = RegAssign.begin(); 924ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (const LiveRange::Segment &S : Edit->getParent()) { 925ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DEBUG(dbgs() << " blit " << S << ':'); 926ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines VNInfo *ParentVNI = S.valno; 9274670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // RegAssign has holes where RegIdx 0 should be used. 928ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SlotIndex Start = S.start; 9294670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen AssignI.advanceTo(Start); 9304670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen do { 9314670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen unsigned RegIdx; 932ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SlotIndex End = S.end; 9334670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (!AssignI.valid()) { 9344670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 9354670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else if (AssignI.start() <= Start) { 9364670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = AssignI.value(); 9374670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen if (AssignI.stop() < End) { 9384670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = AssignI.stop(); 9394670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++AssignI; 9404670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 9414670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } else { 9424670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen RegIdx = 0; 9434670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen End = std::min(End, AssignI.start()); 9444670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 94544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 94644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. 9474670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); 948e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun LiveRange &LR = LIS.getInterval(Edit->get(RegIdx)); 94944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 95044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Check for a simply defined value that can be blitted directly. 951393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id)); 952393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (VNInfo *VNI = VFP.getPointer()) { 9534670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id); 954e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun LR.addSegment(LiveInterval::Segment(Start, End, VNI)); 95544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Start = End; 95644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 95744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 95844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 959393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // Skip values with forced recomputation. 960393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen if (VFP.getInt()) { 961393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen DEBUG(dbgs() << "(recalc)"); 9624670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Skipped = true; 96344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen Start = End; 96444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen continue; 96544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 96644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 967c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LiveRangeCalc &LRC = getLRCalc(RegIdx); 968c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen 96944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This value has multiple defs in RegIdx, but it wasn't rematerialized, 97044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // so the live range is accurate. Add live-in blocks in [Start;End) to the 97144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // LiveInBlocks. 972f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator(); 97344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SlotIndex BlockStart, BlockEnd; 974f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB); 97544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 97644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // The first block may be live-in, or it may have its own def. 97744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Start != BlockStart) { 978e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End)); 97944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(VNI && "Missing def for complex mapped value"); 98044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); 98144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // MBB has its own def. Is it also live-out? 982b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (BlockEnd <= End) 983f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LRC.setLiveOutValue(&*MBB, VNI); 984b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen 98544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Skip to the next block for live-in. 98644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen ++MBB; 98744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockStart = BlockEnd; 98844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 98944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 99044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Handle the live-in blocks covered by [Start;End). 99144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(Start <= BlockStart && "Expected live-in block"); 99244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen while (BlockStart < End) { 99344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen DEBUG(dbgs() << ">BB#" << MBB->getNumber()); 994f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BlockEnd = LIS.getMBBEndIdx(&*MBB); 99544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (BlockStart == ParentVNI->def) { 99644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // This block has the def of a parent PHI, so it isn't live-in. 99744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); 998e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End)); 99944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen assert(VNI && "Missing def for complex mapped parent PHI"); 1000b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen if (End >= BlockEnd) 1001f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well. 100244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } else { 1003b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // This block needs a live-in value. The last block covered may not 1004b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // be live-out. 100544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (End < BlockEnd) 1006f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LRC.addLiveInBlock(LR, MDT[&*MBB], End); 100744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen else { 1008b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen // Live-through, and we don't know the value. 1009f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LRC.addLiveInBlock(LR, MDT[&*MBB]); 1010f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LRC.setLiveOutValue(&*MBB, nullptr); 101144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 101244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 101344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen BlockStart = BlockEnd; 101444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen ++MBB; 101544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen } 10164670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen Start = End; 1017ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } while (Start != S.end); 10184670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 10194670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen } 102044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 1021631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen LRCalc[0].calculateValues(); 1022c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen if (SpillMode) 1023631390e3c26fe5581ee9468b04593cedf48cc908Jakob Stoklund Olesen LRCalc[1].calculateValues(); 102444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 10254670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen return Skipped; 10264670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen} 10274670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 1028e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesenvoid SplitEditor::extendPHIKillRanges() { 1029de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Extend live ranges to be live-out for successor PHI values. 1030ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (const VNInfo *PHIVNI : Edit->getParent().valnos) { 1031e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) 1032e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen continue; 1033e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(PHIVNI->def); 1034e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun LiveRange &LR = LIS.getInterval(Edit->get(RegIdx)); 1035de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 1036de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Check whether PHI is dead. 1037de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const LiveRange::Segment *Segment = LR.getSegmentContaining(PHIVNI->def); 1038de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(Segment != nullptr && "Missing segment for VNI"); 1039de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Segment->end == PHIVNI->def.getDeadSlot()) { 1040de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // This is a dead PHI. Remove it. 1041de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LR.removeSegment(*Segment, true); 1042de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 1043de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 1044de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 1045abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen LiveRangeCalc &LRC = getLRCalc(RegIdx); 1046e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); 1047e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 1048e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 1049abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen SlotIndex End = LIS.getMBBEndIdx(*PI); 1050abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen SlotIndex LastUse = End.getPrevSlot(); 1051e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // The predecessor may not have a live-out value. That is OK, like an 1052e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen // undef PHI operand. 1053abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen if (Edit->getParent().liveAt(LastUse)) { 1054abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen assert(RegAssign.lookup(LastUse) == RegIdx && 1055e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen "Different register assignment in phi predecessor"); 1056e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun LRC.extend(LR, End); 1057e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 1058e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 1059e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen } 1060e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen} 1061e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 1062a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen/// rewriteAssigned - Rewrite all uses of Edit->getReg(). 10634670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesenvoid SplitEditor::rewriteAssigned(bool ExtendRanges) { 1064a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), 1065078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 106636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineOperand &MO = *RI; 10677466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 10687466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen ++RI; 10690f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // LiveDebugVariables should have handled all DBG_VALUE instructions. 10707466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen if (MI->isDebugValue()) { 10717466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen DEBUG(dbgs() << "Zapping " << *MI); 10727466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen MO.setReg(0); 10737466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen continue; 10747466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 1075a372d16f92392bb4cd4184783466f0300a51a9aeJakob Stoklund Olesen 1076b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // <undef> operands don't really read the register, so it doesn't matter 1077b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // which register we choose. When the use operand is tied to a def, we must 1078b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen // use the same register as the def, so just do that always. 1079de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SlotIndex Idx = LIS.getInstructionIndex(*MI); 1080b09701db9e74298912164d988ddf40bb1b5ec19bJakob Stoklund Olesen if (MO.isDef() || MO.isUndef()) 10812debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Idx = Idx.getRegSlot(MO.isEarlyClobber()); 10820f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 10830f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Rewrite to the mapped register at Idx. 10840f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned RegIdx = RegAssign.lookup(Idx); 10851feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); 1086abcc73e8ba3131c7c4f198840ece31453a0101acJakob Stoklund Olesen MO.setReg(LI->reg); 10870f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' 10880f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher << Idx << ':' << RegIdx << '\t' << *MI); 10890f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 10907cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Extend liveness to Idx if the instruction reads reg. 109181d686edbe6effe624add9394673bd571d89bfb7Jakob Stoklund Olesen if (!ExtendRanges || MO.isUndef()) 10927cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 10937cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 10947cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // Skip instructions that don't read Reg. 10957cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (MO.isDef()) { 10967cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!MO.getSubReg() && !MO.isEarlyClobber()) 10977cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 10987cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // We may wan't to extend a live range for a partial redef, or for a use 10997cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen // tied to an early clobber. 11007cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen Idx = Idx.getPrevSlot(); 11017cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen if (!Edit->getParent().liveAt(Idx)) 11027cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen continue; 11037cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen } else 11042debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen Idx = Idx.getRegSlot(true); 11057cec179a647bff132d7af36d91df877056880c5eJakob Stoklund Olesen 1106e25dde550baec1f79caf2fc06edd74e7ae6ffa33Matthias Braun getLRCalc(RegIdx).extend(*LI, Idx.getNextSlot()); 11077466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen } 11087466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen} 11097466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 11105881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesenvoid SplitEditor::deleteRematVictims() { 11115881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen SmallVector<MachineInstr*, 8> Dead; 11122dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ 11131feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *LI = &LIS.getInterval(*I); 1114ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (const LiveRange::Segment &S : LI->segments) { 11151f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen // Dead defs end at the dead slot. 1116ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (S.end != S.valno->def.getDeadSlot()) 11172dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 1118de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (S.valno->isPHIDef()) 1119de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 1120ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def); 11212dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen assert(MI && "Missing instruction for dead def"); 11222dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen MI->addRegisterDead(LI->reg, &TRI); 11235881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 11242dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen if (!MI->allDefsAreDead()) 11252dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen continue; 11265881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 11272dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << *MI); 11282dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen Dead.push_back(MI); 11292dc455a366e26d8c1085ef617651232304ee097eJakob Stoklund Olesen } 11305881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen } 11315881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 11325881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (Dead.empty()) 11335881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen return; 11345881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 1135de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Edit->eliminateDeadDefs(Dead, None, &AA); 11365881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen} 11375881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 11385928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesenvoid SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { 11394670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumFinished; 11400f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 11410f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // At this point, the live intervals in Edit contain VNInfos corresponding to 11420f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // the inserted copies. 11430f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 11440f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher // Add the original defs from the parent interval. 1145ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (const VNInfo *ParentVNI : Edit->getParent().valnos) { 11469ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen if (ParentVNI->isUnused()) 11479ecd1e71973f555cab00ee862b6f509d0126025aJakob Stoklund Olesen continue; 1148670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen unsigned RegIdx = RegAssign.lookup(ParentVNI->def); 1149b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen defValue(RegIdx, ParentVNI, ParentVNI->def); 115029ef87599c86b28db94d57705ab2901768253cadJakob Stoklund Olesen 1151393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen // Force rematted values to be recomputed everywhere. 11524670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen // The new live ranges may be truncated. 1153a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen if (Edit->didRematerialize(ParentVNI)) 1154a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 1155393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen forceRecompute(i, ParentVNI); 11565fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 1157c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 1158b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Hoist back-copies to the complement interval when in spill mode. 1159b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen switch (SpillMode) { 1160b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen case SM_Partition: 1161b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen // Leave all back-copies as is. 1162b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen break; 1163b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen case SM_Size: 1164b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen case SM_Speed: 1165de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // hoistCopies will behave differently between size and speed. 1166de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar hoistCopies(); 1167b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen } 1168b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 116944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Transfer the simply mapped values, check if any are skipped. 117044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen bool Skipped = transferValues(); 1171de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 1172de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Rewrite virtual registers, possibly extending ranges. 1173de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar rewriteAssigned(Skipped); 1174de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 117544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Skipped) 11764670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen extendPHIKillRanges(); 11774670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen else 11784670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen ++NumSimple; 11794670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 11805881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Delete defs that were rematted everywhere. 118144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen if (Skipped) 11825881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen deleteRematVictims(); 11835fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 11840253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Get rid of unused values and set phi-kill flags. 11851feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) { 11861feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval &LI = LIS.getInterval(*I); 11871feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LI.RenumberValues(); 11881feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey } 11890253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 11905928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // Provide a reverse mapping from original indices to Edit ranges. 11915928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRMap) { 11925928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->clear(); 11935928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) 11945928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->push_back(i); 11955928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen } 11965928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 11973a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Now check if any registers were separated into multiple components. 1198078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 1199a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen for (unsigned i = 0, e = Edit->size(); i != e; ++i) { 12003a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen // Don't use iterators, they are invalidated by create() below. 1201f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned VReg = Edit->get(i); 1202f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LiveInterval &LI = LIS.getInterval(VReg); 1203f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar SmallVector<LiveInterval*, 8> SplitLIs; 1204f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LIS.splitSeparateComponents(LI, SplitLIs); 1205f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Original = VRM.getOriginal(VReg); 1206f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (LiveInterval *SplitLI : SplitLIs) 1207f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar VRM.setIsSplitFromReg(SplitLI->reg, Original); 1208f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 12095928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen // The new intervals all map back to i. 12105928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen if (LRMap) 12115928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen LRMap->resize(Edit->size(), i); 12123a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen } 12133a0e0715a5691e26ca70bc853d6d3d116e5949b8Jakob Stoklund Olesen 121408e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesen // Calculate spill weight and allocation hints for new intervals. 12154eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI); 12165928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen 12175928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen assert(!LRMap || LRMap->size() == Edit->size()); 1218f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen} 1219f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 1220f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 12218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1222f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen// Single Block Splitting 1223f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1224f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 12252d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesenbool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, 12262d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen bool SingleInstrs) const { 12272d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Always split for multiple instructions. 12282d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (!BI.isOneInstr()) 12292d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return true; 12302d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Don't split for single instructions unless explicitly requested. 12312d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (!SingleInstrs) 12322d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return false; 12332d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Splitting a live-through range always makes progress. 12342d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (BI.LiveIn && BI.LiveOut) 12352d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return true; 12362d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // No point in isolating a copy. It has no register class constraints. 12372d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike()) 12382d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return false; 12392d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen // Finally, don't isolate an end point that was created by earlier splits. 12402d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen return isOriginalEndpoint(BI.FirstInstr); 12412d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen} 12422d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen 1243fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesenvoid SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { 1244fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen openIntv(); 1245fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); 1246fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr, 1247fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen LastSplitPoint)); 1248fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { 1249fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(SegStart, leaveIntvAfter(BI.LastInstr)); 1250fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } else { 1251fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen // The last use is after the last valid split point. 1252fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); 1253fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen useIntv(SegStart, SegStop); 1254fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(SegStop, BI.LastInstr); 1255fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen } 1256fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen} 1257fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 1258b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1259b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1260b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// Global Live Range Splitting Support 1261b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1262b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1263b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// These methods support a method of global live range splitting that uses a 1264b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// global algorithm to decide intervals for CFG edges. They will insert split 1265b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// points and color intervals in basic blocks while avoiding interference. 1266b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// 1267b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// Note that splitSingleBlock is also useful for blocks where both CFG edges 1268b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen// are on the stack. 1269b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1270b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitLiveThroughBlock(unsigned MBBNum, 1271b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvIn, SlotIndex LeaveBefore, 1272b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvOut, SlotIndex EnterAfter){ 1273b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 127436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); 1275b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1276b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop 1277b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ") intf " << LeaveBefore << '-' << EnterAfter 1278b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", live-through " << IntvIn << " -> " << IntvOut); 1279b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1280b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks"); 1281b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1282fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block"); 1283fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf"); 1284fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!EnterAfter || EnterAfter >= Start) && "Interference before block"); 1285fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen 1286fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); 1287fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen 1288b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (!IntvOut) { 1289b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill on entry.\n"); 1290b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1291b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<<<< Possible LeaveBefore interference. 1292b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1293b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // -____________ Spill on entry. 1294b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1295b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1296b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = leaveIntvAtTop(*MBB); 1297b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1298b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen (void)Idx; 1299b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1300b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1301b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1302b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (!IntvIn) { 1303b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", reload on exit.\n"); 1304b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1305b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>>>>> Possible EnterAfter interference. 1306b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1307b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ___________-- Reload on exit. 1308b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1309b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1310b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAtEnd(*MBB); 1311b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1312b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen (void)Idx; 1313b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1314b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1315b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1316b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { 1317b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", straight through.\n"); 1318b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1319b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1320b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ------------- Straight through, same intv, no interference. 1321b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1322b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1323b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Stop); 1324b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1325b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1326b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1327b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // We cannot legally insert splits after LSP. 1328b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(MBBNum); 1329fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf"); 1330b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1331b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || 1332b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { 1333b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", switch avoiding interference.\n"); 1334b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1335b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. 1336b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1337b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ------======= Switch intervals between interference. 1338b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1339b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1340fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen SlotIndex Idx; 1341fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen if (LeaveBefore && LeaveBefore < LSP) { 1342fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen Idx = enterIntvBefore(LeaveBefore); 1343fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen useIntv(Idx, Stop); 1344fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen } else { 1345fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen Idx = enterIntvAtEnd(*MBB); 1346fe9b2d142a0feb87b06579509479957f25d7d0a4Jakob Stoklund Olesen } 1347b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1348b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1349b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1350b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1351b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1352b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1353b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1354b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", create local intv for interference.\n"); 1355b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1356b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. 1357b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |-----------| Live through. 1358b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ==---------== Switch intervals before/after interference. 1359b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1360b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(LeaveBefore <= EnterAfter && "Missed case"); 1361b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1362b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1363b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAfter(EnterAfter); 1364b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1365b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1366b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1367b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1368b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen Idx = leaveIntvBefore(LeaveBefore); 1369b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1370b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1371b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1372b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1373b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1374b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 1375b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvIn, SlotIndex LeaveBefore) { 1376b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 137736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1378b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1379b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1380fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1381b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", reg-in " << IntvIn << ", leave before " << LeaveBefore 1382b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << (BI.LiveOut ? ", stack-out" : ", killed in block")); 1383b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1384b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(IntvIn && "Must have register in"); 1385b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(BI.LiveIn && "Must be live-in"); 1386b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference"); 1387b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1388fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { 1389b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << " before interference.\n"); 1390b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1391b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<< Interference after kill. 1392b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---x | Killed in block. 1393b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ========= Use IntvIn everywhere. 1394b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1395b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1396fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(Start, BI.LastInstr); 1397b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1398b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1399b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1400b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1401b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1402fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { 1403b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1404b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<< Possible interference after last use. 1405b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-out on stack. 1406b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =========____ Leave IntvIn after last use. 1407b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1408b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // < Interference after last use. 1409b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o--o| Live-out on stack, late last use. 1410b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ============ Copy to stack after LSP, overlap IntvIn. 1411b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // \_____ Stack interval is live-out. 1412b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1413fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (BI.LastInstr < LSP) { 1414b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill after last use before interference.\n"); 1415b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1416fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex Idx = leaveIntvAfter(BI.LastInstr); 1417b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1418b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1419b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } else { 1420b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", spill before last split point.\n"); 1421b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1422af4e40c2f41a7d60b86958e034b00542d551b5f2Jakob Stoklund Olesen SlotIndex Idx = leaveIntvBefore(LSP); 1423fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(Idx, BI.LastInstr); 1424b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, Idx); 1425b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); 1426b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1427b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1428b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1429b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1430b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // The interference is overlapping somewhere we wanted to use IntvIn. That 1431b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // means we need to create a local interval that can be allocated a 1432b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // different register. 1433b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned LocalIntv = openIntv(); 1434f9d7fb6b3c45abc64ad52cd8a9a8a7dd5aa9f4bbMatt Beaumont-Gay (void)LocalIntv; 1435b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n"); 1436b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1437fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveOut || BI.LastInstr < LSP) { 1438b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1439b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<< Interference overlapping uses. 1440b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-out on stack. 1441b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =====----____ Leave IntvIn before interference, then spill. 1442b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1443fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex To = leaveIntvAfter(BI.LastInstr); 1444b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(LeaveBefore); 1445b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, To); 1446b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1447b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, From); 1448b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1449b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1450b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1451b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1452b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // <<<<<<< Interference overlapping uses. 1453b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o--o| Live-out on stack, late last use. 1454b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // =====------- Copy to stack before LSP, overlap LocalIntv. 1455b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // \_____ Stack interval is live-out. 1456b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1457b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex To = leaveIntvBefore(LSP); 1458fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen overlapIntv(To, BI.LastInstr); 1459b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); 1460b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, To); 1461b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvIn); 1462b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Start, From); 1463b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); 1464b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1465b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1466b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesenvoid SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 1467b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvOut, SlotIndex EnterAfter) { 1468b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Start, Stop; 146936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); 1470b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1471b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop 1472fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen << "), uses " << BI.FirstInstr << '-' << BI.LastInstr 1473b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << ", reg-out " << IntvOut << ", enter after " << EnterAfter 1474b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen << (BI.LiveIn ? ", stack-in" : ", defined in block")); 1475b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1476b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); 1477b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1478b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(IntvOut && "Must have register out"); 1479b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert(BI.LiveOut && "Must be live-out"); 1480b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || EnterAfter < LSP) && "Bad interference"); 1481b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1482fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { 1483b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << " after interference.\n"); 1484b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1485b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> Interference before def. 1486b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // | o---o---| Defined in block. 1487b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ========= Use IntvOut everywhere. 1488b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1489b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1490fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen useIntv(BI.FirstInstr, Stop); 1491b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1492b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1493b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1494fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { 1495b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", reload after interference.\n"); 1496b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1497b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>> Interference before def. 1498b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-through, stack-in. 1499b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ____========= Enter IntvOut before first use. 1500b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1501b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1502fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr)); 1503b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1504b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1505b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen return; 1506b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen } 1507b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1508b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // The interference is overlapping somewhere we wanted to use IntvOut. That 1509b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // means we need to create a local interval that can be allocated a 1510b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // different register. 1511b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen DEBUG(dbgs() << ", interference overlaps uses.\n"); 1512b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1513b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // >>>>>>> Interference overlapping uses. 1514b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // |---o---o---| Live-through, stack-in. 1515b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // ____---====== Create local interval for interference range. 1516b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen // 1517b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen selectIntv(IntvOut); 1518b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen SlotIndex Idx = enterIntvAfter(EnterAfter); 1519b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(Idx, Stop); 1520b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); 1521b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 1522b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen openIntv(); 1523fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr)); 1524b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen useIntv(From, Idx); 1525b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen} 1526