Spiller.cpp revision 894339e19fbb45a729008decd1d050ee518589a4
1e2b201bac382464496758d789cddefa50690fbe3Lang Hames//===-- llvm/CodeGen/Spiller.cpp - Spiller -------------------------------===// 2e2b201bac382464496758d789cddefa50690fbe3Lang Hames// 3e2b201bac382464496758d789cddefa50690fbe3Lang Hames// The LLVM Compiler Infrastructure 4e2b201bac382464496758d789cddefa50690fbe3Lang Hames// 5e2b201bac382464496758d789cddefa50690fbe3Lang Hames// This file is distributed under the University of Illinois Open Source 6e2b201bac382464496758d789cddefa50690fbe3Lang Hames// License. See LICENSE.TXT for details. 7e2b201bac382464496758d789cddefa50690fbe3Lang Hames// 8e2b201bac382464496758d789cddefa50690fbe3Lang Hames//===----------------------------------------------------------------------===// 9e2b201bac382464496758d789cddefa50690fbe3Lang Hames 10e2b201bac382464496758d789cddefa50690fbe3Lang Hames#define DEBUG_TYPE "spiller" 11e2b201bac382464496758d789cddefa50690fbe3Lang Hames 12e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "Spiller.h" 13e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "VirtRegMap.h" 14e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/CodeGen/LiveIntervalAnalysis.h" 15c75e7d2a06205f6c9870624eb5e8174a2b7b1bddBill Wendling#include "llvm/CodeGen/MachineFrameInfo.h" 16e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/CodeGen/MachineFunction.h" 17e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/CodeGen/MachineRegisterInfo.h" 18e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/Target/TargetMachine.h" 19e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/Target/TargetInstrInfo.h" 20835ca07991c1b8ec47240b15417e1b2732480094Lang Hames#include "llvm/Support/CommandLine.h" 21e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/Support/Debug.h" 2215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 23c75e7d2a06205f6c9870624eb5e8174a2b7b1bddBill Wendling#include "llvm/Support/raw_ostream.h" 246194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames#include <set> 25e2b201bac382464496758d789cddefa50690fbe3Lang Hames 26e2b201bac382464496758d789cddefa50690fbe3Lang Hamesusing namespace llvm; 27e2b201bac382464496758d789cddefa50690fbe3Lang Hames 28835ca07991c1b8ec47240b15417e1b2732480094Lang Hamesnamespace { 29914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen enum SpillerName { trivial, standard, splitting, inline_ }; 30835ca07991c1b8ec47240b15417e1b2732480094Lang Hames} 31835ca07991c1b8ec47240b15417e1b2732480094Lang Hames 32835ca07991c1b8ec47240b15417e1b2732480094Lang Hamesstatic cl::opt<SpillerName> 33835ca07991c1b8ec47240b15417e1b2732480094Lang HamesspillerOpt("spiller", 34835ca07991c1b8ec47240b15417e1b2732480094Lang Hames cl::desc("Spiller to use: (default: standard)"), 35835ca07991c1b8ec47240b15417e1b2732480094Lang Hames cl::Prefix, 366194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames cl::values(clEnumVal(trivial, "trivial spiller"), 376194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames clEnumVal(standard, "default spiller"), 386194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames clEnumVal(splitting, "splitting spiller"), 39d5bd68ed08a414b00721c3c556459d0f295ea4d5Jakob Stoklund Olesen clEnumValN(inline_, "inline", "inline spiller"), 40835ca07991c1b8ec47240b15417e1b2732480094Lang Hames clEnumValEnd), 41835ca07991c1b8ec47240b15417e1b2732480094Lang Hames cl::init(standard)); 42835ca07991c1b8ec47240b15417e1b2732480094Lang Hames 436194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames// Spiller virtual destructor implementation. 44e2b201bac382464496758d789cddefa50690fbe3Lang HamesSpiller::~Spiller() {} 45e2b201bac382464496758d789cddefa50690fbe3Lang Hames 46e2b201bac382464496758d789cddefa50690fbe3Lang Hamesnamespace { 47e2b201bac382464496758d789cddefa50690fbe3Lang Hames 48f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames/// Utility class for spillers. 49f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamesclass SpillerBase : public Spiller { 50f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamesprotected: 51f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames MachineFunction *mf; 52f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames LiveIntervals *lis; 53f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames MachineFrameInfo *mfi; 54f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames MachineRegisterInfo *mri; 55f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames const TargetInstrInfo *tii; 56746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng const TargetRegisterInfo *tri; 57f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames VirtRegMap *vrm; 58894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 59894339e19fbb45a729008decd1d050ee518589a4Eric Christopher /// Construct a spiller base. 608783e401a3ad187dcd0f306153f9339f7270621dLang Hames SpillerBase(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm) 618783e401a3ad187dcd0f306153f9339f7270621dLang Hames : mf(mf), lis(lis), vrm(vrm) 62e2b201bac382464496758d789cddefa50690fbe3Lang Hames { 63e2b201bac382464496758d789cddefa50690fbe3Lang Hames mfi = mf->getFrameInfo(); 64e2b201bac382464496758d789cddefa50690fbe3Lang Hames mri = &mf->getRegInfo(); 65e2b201bac382464496758d789cddefa50690fbe3Lang Hames tii = mf->getTarget().getInstrInfo(); 66746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng tri = mf->getTarget().getRegisterInfo(); 67e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 68e2b201bac382464496758d789cddefa50690fbe3Lang Hames 69f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames /// Add spill ranges for every use/def of the live interval, inserting loads 7038283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames /// immediately before each use, and stores after each def. No folding or 7138283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames /// remat is attempted. 7267674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen void trivialSpillEverywhere(LiveInterval *li, 7367674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen std::vector<LiveInterval*> &newIntervals) { 7465de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << "Spilling everywhere " << *li << "\n"); 75e2b201bac382464496758d789cddefa50690fbe3Lang Hames 76e2b201bac382464496758d789cddefa50690fbe3Lang Hames assert(li->weight != HUGE_VALF && 77e2b201bac382464496758d789cddefa50690fbe3Lang Hames "Attempting to spill already spilled value."); 78e2b201bac382464496758d789cddefa50690fbe3Lang Hames 79e2b201bac382464496758d789cddefa50690fbe3Lang Hames assert(!li->isStackSlot() && 80e2b201bac382464496758d789cddefa50690fbe3Lang Hames "Trying to spill a stack slot."); 81e2b201bac382464496758d789cddefa50690fbe3Lang Hames 8265de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << "Trivial spill everywhere of reg" << li->reg << "\n"); 836bbc73d3fd274e15297eb2c3e4172e43ce7bc8f8Lang Hames 84e2b201bac382464496758d789cddefa50690fbe3Lang Hames const TargetRegisterClass *trc = mri->getRegClass(li->reg); 85e2b201bac382464496758d789cddefa50690fbe3Lang Hames unsigned ss = vrm->assignVirt2StackSlot(li->reg); 86e2b201bac382464496758d789cddefa50690fbe3Lang Hames 8738283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Iterate over reg uses/defs. 88f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames for (MachineRegisterInfo::reg_iterator 89f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) { 90e2b201bac382464496758d789cddefa50690fbe3Lang Hames 9138283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Grab the use/def instr. 92e2b201bac382464496758d789cddefa50690fbe3Lang Hames MachineInstr *mi = &*regItr; 936bbc73d3fd274e15297eb2c3e4172e43ce7bc8f8Lang Hames 9465de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << " Processing " << *mi); 956bbc73d3fd274e15297eb2c3e4172e43ce7bc8f8Lang Hames 9638283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Step regItr to the next use/def instr. 97f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames do { 98f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames ++regItr; 99f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames } while (regItr != mri->reg_end() && (&*regItr == mi)); 100894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 10138283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Collect uses & defs for this instr. 102e2b201bac382464496758d789cddefa50690fbe3Lang Hames SmallVector<unsigned, 2> indices; 103e2b201bac382464496758d789cddefa50690fbe3Lang Hames bool hasUse = false; 104e2b201bac382464496758d789cddefa50690fbe3Lang Hames bool hasDef = false; 105e2b201bac382464496758d789cddefa50690fbe3Lang Hames for (unsigned i = 0; i != mi->getNumOperands(); ++i) { 106e2b201bac382464496758d789cddefa50690fbe3Lang Hames MachineOperand &op = mi->getOperand(i); 107e2b201bac382464496758d789cddefa50690fbe3Lang Hames if (!op.isReg() || op.getReg() != li->reg) 108e2b201bac382464496758d789cddefa50690fbe3Lang Hames continue; 109e2b201bac382464496758d789cddefa50690fbe3Lang Hames hasUse |= mi->getOperand(i).isUse(); 110e2b201bac382464496758d789cddefa50690fbe3Lang Hames hasDef |= mi->getOperand(i).isDef(); 111e2b201bac382464496758d789cddefa50690fbe3Lang Hames indices.push_back(i); 112e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 113e2b201bac382464496758d789cddefa50690fbe3Lang Hames 11438283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Create a new vreg & interval for this instr. 115e2b201bac382464496758d789cddefa50690fbe3Lang Hames unsigned newVReg = mri->createVirtualRegister(trc); 116e2b201bac382464496758d789cddefa50690fbe3Lang Hames vrm->grow(); 117e2b201bac382464496758d789cddefa50690fbe3Lang Hames vrm->assignVirt2StackSlot(newVReg, ss); 118f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames LiveInterval *newLI = &lis->getOrCreateInterval(newVReg); 119f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames newLI->weight = HUGE_VALF; 120894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 12138283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Update the reg operands & kill flags. 122e2b201bac382464496758d789cddefa50690fbe3Lang Hames for (unsigned i = 0; i < indices.size(); ++i) { 12338283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames unsigned mopIdx = indices[i]; 12438283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames MachineOperand &mop = mi->getOperand(mopIdx); 12538283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames mop.setReg(newVReg); 12638283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames if (mop.isUse() && !mi->isRegTiedToDefOperand(mopIdx)) { 12738283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames mop.setIsKill(true); 128e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 129e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 130f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames assert(hasUse || hasDef); 131f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 13238283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Insert reload if necessary. 13338283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames MachineBasicBlock::iterator miItr(mi); 134e2b201bac382464496758d789cddefa50690fbe3Lang Hames if (hasUse) { 135746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng tii->loadRegFromStackSlot(*mi->getParent(), miItr, newVReg, ss, trc, 136746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng tri); 13738283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames MachineInstr *loadInstr(prior(miItr)); 13838283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames SlotIndex loadIndex = 13938283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames lis->InsertMachineInstrInMaps(loadInstr).getDefIndex(); 140d540801e13d1aef4f074f8c32115f55104130e28Jakob Stoklund Olesen vrm->addSpillSlotUse(ss, loadInstr); 14138283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames SlotIndex endIndex = loadIndex.getNextIndex(); 14238283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames VNInfo *loadVNI = 14338283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames newLI->getNextValue(loadIndex, 0, true, lis->getVNInfoAllocator()); 14438283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames newLI->addRange(LiveRange(loadIndex, endIndex, loadVNI)); 145e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 146e2b201bac382464496758d789cddefa50690fbe3Lang Hames 14738283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Insert store if necessary. 148e2b201bac382464496758d789cddefa50690fbe3Lang Hames if (hasDef) { 149e9b3ac27dda22a6939246323935111070cf24280Evan Cheng tii->storeRegToStackSlot(*mi->getParent(), llvm::next(miItr), newVReg, 150746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng true, ss, trc, tri); 1517896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineInstr *storeInstr(llvm::next(miItr)); 15238283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames SlotIndex storeIndex = 15338283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames lis->InsertMachineInstrInMaps(storeInstr).getDefIndex(); 154d540801e13d1aef4f074f8c32115f55104130e28Jakob Stoklund Olesen vrm->addSpillSlotUse(ss, storeInstr); 15538283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames SlotIndex beginIndex = storeIndex.getPrevIndex(); 15638283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames VNInfo *storeVNI = 15738283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames newLI->getNextValue(beginIndex, 0, true, lis->getVNInfoAllocator()); 15838283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames newLI->addRange(LiveRange(beginIndex, storeIndex, storeVNI)); 159e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 160e2b201bac382464496758d789cddefa50690fbe3Lang Hames 16167674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen newIntervals.push_back(newLI); 162e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 163e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 164f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames}; 165e2b201bac382464496758d789cddefa50690fbe3Lang Hames 1661ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner} // end anonymous namespace 1671ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner 1681ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattnernamespace { 169e2b201bac382464496758d789cddefa50690fbe3Lang Hames 170f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames/// Spills any live range using the spill-everywhere method with no attempt at 171f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames/// folding. 172f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamesclass TrivialSpiller : public SpillerBase { 173f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamespublic: 17410382fb71d8306f320ecbeb7049d25354c0e5457Lang Hames 1758783e401a3ad187dcd0f306153f9339f7270621dLang Hames TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm) 1768783e401a3ad187dcd0f306153f9339f7270621dLang Hames : SpillerBase(mf, lis, vrm) {} 177e2b201bac382464496758d789cddefa50690fbe3Lang Hames 17867674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen void spill(LiveInterval *li, 17967674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen std::vector<LiveInterval*> &newIntervals, 18067674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &, 18167674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen SlotIndex*) { 182835ca07991c1b8ec47240b15417e1b2732480094Lang Hames // Ignore spillIs - we don't use it. 18367674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen trivialSpillEverywhere(li, newIntervals); 184e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 185e2b201bac382464496758d789cddefa50690fbe3Lang Hames}; 186e2b201bac382464496758d789cddefa50690fbe3Lang Hames 1871ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner} // end anonymous namespace 1881ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner 1891ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattnernamespace { 1901ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner 191835ca07991c1b8ec47240b15417e1b2732480094Lang Hames/// Falls back on LiveIntervals::addIntervalsForSpills. 192835ca07991c1b8ec47240b15417e1b2732480094Lang Hamesclass StandardSpiller : public Spiller { 1936194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hamesprotected: 194835ca07991c1b8ec47240b15417e1b2732480094Lang Hames LiveIntervals *lis; 195835ca07991c1b8ec47240b15417e1b2732480094Lang Hames const MachineLoopInfo *loopInfo; 196835ca07991c1b8ec47240b15417e1b2732480094Lang Hames VirtRegMap *vrm; 197835ca07991c1b8ec47240b15417e1b2732480094Lang Hamespublic: 1986194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames StandardSpiller(LiveIntervals *lis, const MachineLoopInfo *loopInfo, 1996194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames VirtRegMap *vrm) 200835ca07991c1b8ec47240b15417e1b2732480094Lang Hames : lis(lis), loopInfo(loopInfo), vrm(vrm) {} 201835ca07991c1b8ec47240b15417e1b2732480094Lang Hames 202835ca07991c1b8ec47240b15417e1b2732480094Lang Hames /// Falls back on LiveIntervals::addIntervalsForSpills. 20367674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen void spill(LiveInterval *li, 20467674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen std::vector<LiveInterval*> &newIntervals, 20567674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &spillIs, 20667674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen SlotIndex*) { 20767674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen std::vector<LiveInterval*> added = 20867674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen lis->addIntervalsForSpills(*li, spillIs, loopInfo, *vrm); 20967674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen newIntervals.insert(newIntervals.end(), added.begin(), added.end()); 210835ca07991c1b8ec47240b15417e1b2732480094Lang Hames } 211835ca07991c1b8ec47240b15417e1b2732480094Lang Hames}; 212835ca07991c1b8ec47240b15417e1b2732480094Lang Hames 2131ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner} // end anonymous namespace 2141ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner 2151ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattnernamespace { 2161ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner 2176194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames/// When a call to spill is placed this spiller will first try to break the 2186194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames/// interval up into its component values (one new interval per value). 2196194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames/// If this fails, or if a call is placed to spill a previously split interval 220894339e19fbb45a729008decd1d050ee518589a4Eric Christopher/// then the spiller falls back on the standard spilling mechanism. 2216194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hamesclass SplittingSpiller : public StandardSpiller { 2226194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hamespublic: 2236194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames SplittingSpiller(MachineFunction *mf, LiveIntervals *lis, 2246194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames const MachineLoopInfo *loopInfo, VirtRegMap *vrm) 2256194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames : StandardSpiller(lis, loopInfo, vrm) { 2266194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 2276194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames mri = &mf->getRegInfo(); 2286194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames tii = mf->getTarget().getInstrInfo(); 2296194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames tri = mf->getTarget().getRegisterInfo(); 2306194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 2316194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 23267674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen void spill(LiveInterval *li, 23367674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen std::vector<LiveInterval*> &newIntervals, 23467674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &spillIs, 23567674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen SlotIndex *earliestStart) { 23667674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen if (worthTryingToSplit(li)) 23767674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen tryVNISplit(li, earliestStart); 23867674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen else 23967674e2685af8ab16292550becac15f7b17ea831Jakob Stoklund Olesen StandardSpiller::spill(li, newIntervals, spillIs, earliestStart); 2406194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 2416194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 2426194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hamesprivate: 2436194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 2446194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineRegisterInfo *mri; 2456194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames const TargetInstrInfo *tii; 246894339e19fbb45a729008decd1d050ee518589a4Eric Christopher const TargetRegisterInfo *tri; 2476194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames DenseSet<LiveInterval*> alreadySplit; 2486194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 2496194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames bool worthTryingToSplit(LiveInterval *li) const { 2506194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames return (!alreadySplit.count(li) && li->getNumValNums() > 1); 2516194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 2526194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 2536194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames /// Try to break a LiveInterval into its component values. 2546194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames std::vector<LiveInterval*> tryVNISplit(LiveInterval *li, 2556194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames SlotIndex *earliestStart) { 2566194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 25765de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << "Trying VNI split of %reg" << *li << "\n"); 2586194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 2596194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames std::vector<LiveInterval*> added; 2606194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames SmallVector<VNInfo*, 4> vnis; 2616194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 2626194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames std::copy(li->vni_begin(), li->vni_end(), std::back_inserter(vnis)); 263894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 2646194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames for (SmallVectorImpl<VNInfo*>::iterator vniItr = vnis.begin(), 2656194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames vniEnd = vnis.end(); vniItr != vniEnd; ++vniItr) { 2666194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames VNInfo *vni = *vniItr; 267894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 26815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // Skip unused VNIs. 26915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen if (vni->isUnused()) 2706194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames continue; 2716194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 27265de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << " Extracted Val #" << vni->id << " as "); 2736194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames LiveInterval *splitInterval = extractVNI(li, vni); 274894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 2756194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (splitInterval != 0) { 27665de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << *splitInterval << "\n"); 2776194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames added.push_back(splitInterval); 2786194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames alreadySplit.insert(splitInterval); 2796194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (earliestStart != 0) { 2806194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (splitInterval->beginIndex() < *earliestStart) 2816194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames *earliestStart = splitInterval->beginIndex(); 2826194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 2836194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } else { 28465de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << "0\n"); 2856194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 286894339e19fbb45a729008decd1d050ee518589a4Eric Christopher } 2876194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 28865de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << "Original LI: " << *li << "\n"); 2896194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 2906194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // If there original interval still contains some live ranges 291894339e19fbb45a729008decd1d050ee518589a4Eric Christopher // add it to added and alreadySplit. 2926194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (!li->empty()) { 2936194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames added.push_back(li); 2946194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames alreadySplit.insert(li); 2956194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (earliestStart != 0) { 2966194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (li->beginIndex() < *earliestStart) 2976194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames *earliestStart = li->beginIndex(); 2986194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 2996194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 3006194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 3016194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames return added; 3026194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 3036194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 3046194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames /// Extract the given value number from the interval. 3056194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames LiveInterval* extractVNI(LiveInterval *li, VNInfo *vni) const { 3066194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames assert(vni->isDefAccurate() || vni->isPHIDef()); 3076194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 30815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // Create a new vreg and live interval, copy VNI ranges over. 3096194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames const TargetRegisterClass *trc = mri->getRegClass(li->reg); 3106194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames unsigned newVReg = mri->createVirtualRegister(trc); 3116194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames vrm->grow(); 3126194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames LiveInterval *newLI = &lis->getOrCreateInterval(newVReg); 3136194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames VNInfo *newVNI = newLI->createValueCopy(vni, lis->getVNInfoAllocator()); 3146194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 315894339e19fbb45a729008decd1d050ee518589a4Eric Christopher // Start by copying all live ranges in the VN to the new interval. 3166194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames for (LiveInterval::iterator rItr = li->begin(), rEnd = li->end(); 3176194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames rItr != rEnd; ++rItr) { 3186194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (rItr->valno == vni) { 3196194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newLI->addRange(LiveRange(rItr->start, rItr->end, newVNI)); 3206194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 3216194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 3226194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 323894339e19fbb45a729008decd1d050ee518589a4Eric Christopher // Erase the old VNI & ranges. 3246194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames li->removeValNo(vni); 3256194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 3266194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // Collect all current uses of the register belonging to the given VNI. 3276194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // We'll use this to rename the register after we've dealt with the def. 3286194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames std::set<MachineInstr*> uses; 3296194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames for (MachineRegisterInfo::use_iterator 3306194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames useItr = mri->use_begin(li->reg), useEnd = mri->use_end(); 3316194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames useItr != useEnd; ++useItr) { 3326194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames uses.insert(&*useItr); 3336194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 3346194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 3356194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // Process the def instruction for this VNI. 3366194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (newVNI->isPHIDef()) { 3376194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // Insert a copy at the start of the MBB. The range proceeding the 3386194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // copy will be attached to the original LiveInterval. 3396194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineBasicBlock *defMBB = lis->getMBBFromIndex(newVNI->def); 34034dcc6fadca0a1117cdbd0e9b35c991a55b6e556Dan Gohman tii->copyRegToReg(*defMBB, defMBB->begin(), newVReg, li->reg, trc, trc, 34134dcc6fadca0a1117cdbd0e9b35c991a55b6e556Dan Gohman DebugLoc()); 3426194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineInstr *copyMI = defMBB->begin(); 3436194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames copyMI->addRegisterKilled(li->reg, tri); 3446194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI); 3456194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames VNInfo *phiDefVNI = li->getNextValue(lis->getMBBStartIdx(defMBB), 3466194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 0, false, lis->getVNInfoAllocator()); 3476194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames phiDefVNI->setIsPHIDef(true); 3486194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames li->addRange(LiveRange(phiDefVNI->def, copyIdx.getDefIndex(), phiDefVNI)); 3496194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames LiveRange *oldPHIDefRange = 3506194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newLI->getLiveRangeContaining(lis->getMBBStartIdx(defMBB)); 3516194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 3526194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // If the old phi def starts in the middle of the range chop it up. 3536194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (oldPHIDefRange->start < lis->getMBBStartIdx(defMBB)) { 3546194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames LiveRange oldPHIDefRange2(copyIdx.getDefIndex(), oldPHIDefRange->end, 3556194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames oldPHIDefRange->valno); 3566194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames oldPHIDefRange->end = lis->getMBBStartIdx(defMBB); 3576194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newLI->addRange(oldPHIDefRange2); 3586194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } else if (oldPHIDefRange->start == lis->getMBBStartIdx(defMBB)) { 3596194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // Otherwise if it's at the start of the range just trim it. 3606194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames oldPHIDefRange->start = copyIdx.getDefIndex(); 3616194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } else { 3626194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames assert(false && "PHI def range doesn't cover PHI def?"); 3636194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 3646194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 3656194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newVNI->def = copyIdx.getDefIndex(); 3666194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newVNI->setCopy(copyMI); 3676194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newVNI->setIsPHIDef(false); // not a PHI def anymore. 3686194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newVNI->setIsDefAccurate(true); 3696194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } else { 370894339e19fbb45a729008decd1d050ee518589a4Eric Christopher // non-PHI def. Rename the def. If it's two-addr that means renaming the 371894339e19fbb45a729008decd1d050ee518589a4Eric Christopher // use and inserting a new copy too. 3726194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineInstr *defInst = lis->getInstructionFromIndex(newVNI->def); 3736194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // We'll rename this now, so we can remove it from uses. 3746194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames uses.erase(defInst); 3756194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames unsigned defOpIdx = defInst->findRegisterDefOperandIdx(li->reg); 3766194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames bool isTwoAddr = defInst->isRegTiedToUseOperand(defOpIdx), 3776194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames twoAddrUseIsUndef = false; 3786194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 3796194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames for (unsigned i = 0; i < defInst->getNumOperands(); ++i) { 3806194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineOperand &mo = defInst->getOperand(i); 3816194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (mo.isReg() && (mo.isDef() || isTwoAddr) && (mo.getReg()==li->reg)) { 3826194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames mo.setReg(newVReg); 3836194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (isTwoAddr && mo.isUse() && mo.isUndef()) 3846194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames twoAddrUseIsUndef = true; 3856194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 3866194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 387894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 3886194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames SlotIndex defIdx = lis->getInstructionIndex(defInst); 3896194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newVNI->def = defIdx.getDefIndex(); 3906194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 3916194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (isTwoAddr && !twoAddrUseIsUndef) { 3926194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineBasicBlock *defMBB = defInst->getParent(); 39334dcc6fadca0a1117cdbd0e9b35c991a55b6e556Dan Gohman tii->copyRegToReg(*defMBB, defInst, newVReg, li->reg, trc, trc, 39434dcc6fadca0a1117cdbd0e9b35c991a55b6e556Dan Gohman DebugLoc()); 3956194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineInstr *copyMI = prior(MachineBasicBlock::iterator(defInst)); 3966194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI); 3976194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames copyMI->addRegisterKilled(li->reg, tri); 3986194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames LiveRange *origUseRange = 3996194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames li->getLiveRangeContaining(newVNI->def.getUseIndex()); 4006194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames origUseRange->end = copyIdx.getDefIndex(); 4016194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames VNInfo *copyVNI = newLI->getNextValue(copyIdx.getDefIndex(), copyMI, 4026194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames true, lis->getVNInfoAllocator()); 4036194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames LiveRange copyRange(copyIdx.getDefIndex(),defIdx.getDefIndex(),copyVNI); 4046194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newLI->addRange(copyRange); 405894339e19fbb45a729008decd1d050ee518589a4Eric Christopher } 4066194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 407894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 4086194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames for (std::set<MachineInstr*>::iterator 4096194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames usesItr = uses.begin(), usesEnd = uses.end(); 4106194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames usesItr != usesEnd; ++usesItr) { 4116194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineInstr *useInst = *usesItr; 4126194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames SlotIndex useIdx = lis->getInstructionIndex(useInst); 4136194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames LiveRange *useRange = 4146194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newLI->getLiveRangeContaining(useIdx.getUseIndex()); 4156194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 4166194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // If this use doesn't belong to the new interval skip it. 4176194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (useRange == 0) 4186194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames continue; 4196194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 4206194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // This use doesn't belong to the VNI, skip it. 4216194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (useRange->valno != newVNI) 4226194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames continue; 4236194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 4246194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // Check if this instr is two address. 4256194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames unsigned useOpIdx = useInst->findRegisterUseOperandIdx(li->reg); 4266194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames bool isTwoAddress = useInst->isRegTiedToDefOperand(useOpIdx); 427894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 4286194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // Rename uses (and defs for two-address instrs). 4296194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames for (unsigned i = 0; i < useInst->getNumOperands(); ++i) { 4306194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineOperand &mo = useInst->getOperand(i); 4316194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (mo.isReg() && (mo.isUse() || isTwoAddress) && 4326194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames (mo.getReg() == li->reg)) { 4336194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames mo.setReg(newVReg); 4346194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 4356194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 4366194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 4376194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // If this is a two address instruction we've got some extra work to do. 4386194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (isTwoAddress) { 4396194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // We modified the def operand, so we need to copy back to the original 4406194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // reg. 4416194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineBasicBlock *useMBB = useInst->getParent(); 4426194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames MachineBasicBlock::iterator useItr(useInst); 443894339e19fbb45a729008decd1d050ee518589a4Eric Christopher tii->copyRegToReg(*useMBB, llvm::next(useItr), li->reg, newVReg, trc, 444894339e19fbb45a729008decd1d050ee518589a4Eric Christopher trc, DebugLoc()); 4457d9663c70b3300070298d716dba6e6f6ce2d1e3eDouglas Gregor MachineInstr *copyMI = llvm::next(useItr); 4466194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames copyMI->addRegisterKilled(newVReg, tri); 4476194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI); 4486194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 4496194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // Change the old two-address defined range & vni to start at 4506194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // (and be defined by) the copy. 4516194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames LiveRange *origDefRange = 4526194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames li->getLiveRangeContaining(useIdx.getDefIndex()); 4536194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames origDefRange->start = copyIdx.getDefIndex(); 4546194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames origDefRange->valno->def = copyIdx.getDefIndex(); 4556194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames origDefRange->valno->setCopy(copyMI); 4566194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 4576194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // Insert a new range & vni for the two-address-to-copy value. This 4586194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // will be attached to the new live interval. 4596194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames VNInfo *copyVNI = 4606194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newLI->getNextValue(useIdx.getDefIndex(), 0, true, 4616194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames lis->getVNInfoAllocator()); 4626194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames LiveRange copyRange(useIdx.getDefIndex(),copyIdx.getDefIndex(),copyVNI); 4636194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newLI->addRange(copyRange); 4646194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 4656194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 46615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 4676194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames // Iterate over any PHI kills - we'll need to insert new copies for them. 46815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen for (LiveInterval::iterator LRI = newLI->begin(), LRE = newLI->end(); 46915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen LRI != LRE; ++LRI) { 47015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen if (LRI->valno != newVNI || LRI->end.isPHI()) 47115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen continue; 47215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen SlotIndex killIdx = LRI->end; 47315a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen MachineBasicBlock *killMBB = lis->getMBBFromIndex(killIdx); 4746194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 47515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen tii->copyRegToReg(*killMBB, killMBB->getFirstTerminator(), 47615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen li->reg, newVReg, trc, trc, 47715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen DebugLoc()); 47815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen MachineInstr *copyMI = prior(killMBB->getFirstTerminator()); 47915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen copyMI->addRegisterKilled(newVReg, tri); 48015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI); 4816194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 48215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // Save the current end. We may need it to add a new range if the 48315a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // current range runs of the end of the MBB. 48415a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen SlotIndex newKillRangeEnd = LRI->end; 48515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen LRI->end = copyIdx.getDefIndex(); 4866194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 48715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen if (newKillRangeEnd != lis->getMBBEndIdx(killMBB)) { 48815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen assert(newKillRangeEnd > lis->getMBBEndIdx(killMBB) && 48915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen "PHI kill range doesn't reach kill-block end. Not sane."); 49015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen newLI->addRange(LiveRange(lis->getMBBEndIdx(killMBB), 49115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen newKillRangeEnd, newVNI)); 4926194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 4936194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 49415a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen VNInfo *newKillVNI = li->getNextValue(copyIdx.getDefIndex(), 49515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen copyMI, true, 49615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen lis->getVNInfoAllocator()); 49715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen newKillVNI->setHasPHIKill(true); 49815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen li->addRange(LiveRange(copyIdx.getDefIndex(), 49915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen lis->getMBBEndIdx(killMBB), 50015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen newKillVNI)); 5016194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 5026194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames newVNI->setHasPHIKill(false); 5036194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 5046194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames return newLI; 5056194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames } 5066194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 5076194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames}; 5086194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames 5091ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner} // end anonymous namespace 5101ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner 511e2b201bac382464496758d789cddefa50690fbe3Lang Hames 512914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesennamespace llvm { 513914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund OlesenSpiller *createInlineSpiller(MachineFunction*, 514914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen LiveIntervals*, 515914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen const MachineLoopInfo*, 516914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen VirtRegMap*); 517914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen} 518914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 519e2b201bac382464496758d789cddefa50690fbe3Lang Hamesllvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis, 520835ca07991c1b8ec47240b15417e1b2732480094Lang Hames const MachineLoopInfo *loopInfo, 521835ca07991c1b8ec47240b15417e1b2732480094Lang Hames VirtRegMap *vrm) { 522835ca07991c1b8ec47240b15417e1b2732480094Lang Hames switch (spillerOpt) { 5231ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner default: assert(0 && "unknown spiller"); 5241ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner case trivial: return new TrivialSpiller(mf, lis, vrm); 5251ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner case standard: return new StandardSpiller(lis, loopInfo, vrm); 5261ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner case splitting: return new SplittingSpiller(mf, lis, loopInfo, vrm); 527914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen case inline_: return createInlineSpiller(mf, lis, loopInfo, vrm); 528835ca07991c1b8ec47240b15417e1b2732480094Lang Hames } 529e2b201bac382464496758d789cddefa50690fbe3Lang Hames} 530