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" 15789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 162d17293dd00d32208c7857ecdb20b79b0225c353Jakob Stoklund Olesen#include "llvm/CodeGen/LiveStackAnalysis.h" 17c75e7d2a06205f6c9870624eb5e8174a2b7b1bddBill Wendling#include "llvm/CodeGen/MachineFrameInfo.h" 18e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/CodeGen/MachineFunction.h" 191e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 20f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 21e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/CodeGen/MachineRegisterInfo.h" 22e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/Target/TargetMachine.h" 23e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/Target/TargetInstrInfo.h" 24835ca07991c1b8ec47240b15417e1b2732480094Lang Hames#include "llvm/Support/CommandLine.h" 25e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/Support/Debug.h" 2615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 27c75e7d2a06205f6c9870624eb5e8174a2b7b1bddBill Wendling#include "llvm/Support/raw_ostream.h" 28e2b201bac382464496758d789cddefa50690fbe3Lang Hames 29e2b201bac382464496758d789cddefa50690fbe3Lang Hamesusing namespace llvm; 30e2b201bac382464496758d789cddefa50690fbe3Lang Hames 31835ca07991c1b8ec47240b15417e1b2732480094Lang Hamesnamespace { 325d9b1091811106ebad0517a7e0c7936a95cb38adJakob Stoklund Olesen enum SpillerName { trivial, inline_ }; 33835ca07991c1b8ec47240b15417e1b2732480094Lang Hames} 34835ca07991c1b8ec47240b15417e1b2732480094Lang Hames 35835ca07991c1b8ec47240b15417e1b2732480094Lang Hamesstatic cl::opt<SpillerName> 36835ca07991c1b8ec47240b15417e1b2732480094Lang HamesspillerOpt("spiller", 37835ca07991c1b8ec47240b15417e1b2732480094Lang Hames cl::desc("Spiller to use: (default: standard)"), 38835ca07991c1b8ec47240b15417e1b2732480094Lang Hames cl::Prefix, 396194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames cl::values(clEnumVal(trivial, "trivial spiller"), 40d5bd68ed08a414b00721c3c556459d0f295ea4d5Jakob Stoklund Olesen clEnumValN(inline_, "inline", "inline spiller"), 41835ca07991c1b8ec47240b15417e1b2732480094Lang Hames clEnumValEnd), 425d9b1091811106ebad0517a7e0c7936a95cb38adJakob Stoklund Olesen cl::init(trivial)); 43835ca07991c1b8ec47240b15417e1b2732480094Lang Hames 446194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames// Spiller virtual destructor implementation. 45e2b201bac382464496758d789cddefa50690fbe3Lang HamesSpiller::~Spiller() {} 46e2b201bac382464496758d789cddefa50690fbe3Lang Hames 47e2b201bac382464496758d789cddefa50690fbe3Lang Hamesnamespace { 48e2b201bac382464496758d789cddefa50690fbe3Lang Hames 49f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames/// Utility class for spillers. 50f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamesclass SpillerBase : public Spiller { 51f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamesprotected: 52f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen MachineFunctionPass *pass; 53f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames MachineFunction *mf; 54f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen VirtRegMap *vrm; 55f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames LiveIntervals *lis; 56f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames MachineFrameInfo *mfi; 57f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames MachineRegisterInfo *mri; 58f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames const TargetInstrInfo *tii; 59746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng const TargetRegisterInfo *tri; 60894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 61894339e19fbb45a729008decd1d050ee518589a4Eric Christopher /// Construct a spiller base. 62f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen SpillerBase(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm) 63f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen : pass(&pass), mf(&mf), vrm(&vrm) 64e2b201bac382464496758d789cddefa50690fbe3Lang Hames { 65f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen lis = &pass.getAnalysis<LiveIntervals>(); 66f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen mfi = mf.getFrameInfo(); 67f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen mri = &mf.getRegInfo(); 68f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen tii = mf.getTarget().getInstrInfo(); 69f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen tri = mf.getTarget().getRegisterInfo(); 70e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 71e2b201bac382464496758d789cddefa50690fbe3Lang Hames 72f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames /// Add spill ranges for every use/def of the live interval, inserting loads 7338283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames /// immediately before each use, and stores after each def. No folding or 7438283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames /// remat is attempted. 751485455be0310c6b24f096823029e08867531016Lang Hames void trivialSpillEverywhere(LiveRangeEdit& LRE) { 761485455be0310c6b24f096823029e08867531016Lang Hames LiveInterval* li = &LRE.getParent(); 771485455be0310c6b24f096823029e08867531016Lang Hames 7865de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << "Spilling everywhere " << *li << "\n"); 79e2b201bac382464496758d789cddefa50690fbe3Lang Hames 80e2b201bac382464496758d789cddefa50690fbe3Lang Hames assert(li->weight != HUGE_VALF && 81e2b201bac382464496758d789cddefa50690fbe3Lang Hames "Attempting to spill already spilled value."); 82e2b201bac382464496758d789cddefa50690fbe3Lang Hames 83be97e906e03dd9b22e14f6749157c9d5f9701dd5Jakob Stoklund Olesen assert(!TargetRegisterInfo::isStackSlot(li->reg) && 84e2b201bac382464496758d789cddefa50690fbe3Lang Hames "Trying to spill a stack slot."); 85e2b201bac382464496758d789cddefa50690fbe3Lang Hames 8665de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << "Trivial spill everywhere of reg" << li->reg << "\n"); 876bbc73d3fd274e15297eb2c3e4172e43ce7bc8f8Lang Hames 88e2b201bac382464496758d789cddefa50690fbe3Lang Hames const TargetRegisterClass *trc = mri->getRegClass(li->reg); 89e2b201bac382464496758d789cddefa50690fbe3Lang Hames unsigned ss = vrm->assignVirt2StackSlot(li->reg); 90e2b201bac382464496758d789cddefa50690fbe3Lang Hames 9138283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Iterate over reg uses/defs. 92f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames for (MachineRegisterInfo::reg_iterator 93f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) { 94e2b201bac382464496758d789cddefa50690fbe3Lang Hames 9538283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Grab the use/def instr. 96e2b201bac382464496758d789cddefa50690fbe3Lang Hames MachineInstr *mi = &*regItr; 976bbc73d3fd274e15297eb2c3e4172e43ce7bc8f8Lang Hames 9865de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << " Processing " << *mi); 996bbc73d3fd274e15297eb2c3e4172e43ce7bc8f8Lang Hames 10038283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Step regItr to the next use/def instr. 101f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames do { 102f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames ++regItr; 103f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames } while (regItr != mri->reg_end() && (&*regItr == mi)); 104894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 10538283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Collect uses & defs for this instr. 106e2b201bac382464496758d789cddefa50690fbe3Lang Hames SmallVector<unsigned, 2> indices; 107e2b201bac382464496758d789cddefa50690fbe3Lang Hames bool hasUse = false; 108e2b201bac382464496758d789cddefa50690fbe3Lang Hames bool hasDef = false; 109e2b201bac382464496758d789cddefa50690fbe3Lang Hames for (unsigned i = 0; i != mi->getNumOperands(); ++i) { 110e2b201bac382464496758d789cddefa50690fbe3Lang Hames MachineOperand &op = mi->getOperand(i); 111e2b201bac382464496758d789cddefa50690fbe3Lang Hames if (!op.isReg() || op.getReg() != li->reg) 112e2b201bac382464496758d789cddefa50690fbe3Lang Hames continue; 113e2b201bac382464496758d789cddefa50690fbe3Lang Hames hasUse |= mi->getOperand(i).isUse(); 114e2b201bac382464496758d789cddefa50690fbe3Lang Hames hasDef |= mi->getOperand(i).isDef(); 115e2b201bac382464496758d789cddefa50690fbe3Lang Hames indices.push_back(i); 116e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 117e2b201bac382464496758d789cddefa50690fbe3Lang Hames 11838283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Create a new vreg & interval for this instr. 1198a06af96698537377275dd7848db69915638dd26Pete Cooper LiveInterval *newLI = &LRE.create(); 120f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames newLI->weight = HUGE_VALF; 121894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 12238283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Update the reg operands & kill flags. 123e2b201bac382464496758d789cddefa50690fbe3Lang Hames for (unsigned i = 0; i < indices.size(); ++i) { 12438283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames unsigned mopIdx = indices[i]; 12538283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames MachineOperand &mop = mi->getOperand(mopIdx); 1261485455be0310c6b24f096823029e08867531016Lang Hames mop.setReg(newLI->reg); 12738283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames if (mop.isUse() && !mi->isRegTiedToDefOperand(mopIdx)) { 12838283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames mop.setIsKill(true); 129e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 130e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 131f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames assert(hasUse || hasDef); 132f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 13338283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Insert reload if necessary. 13438283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames MachineBasicBlock::iterator miItr(mi); 135e2b201bac382464496758d789cddefa50690fbe3Lang Hames if (hasUse) { 1361485455be0310c6b24f096823029e08867531016Lang Hames tii->loadRegFromStackSlot(*mi->getParent(), miItr, newLI->reg, ss, trc, 137746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng tri); 13838283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames MachineInstr *loadInstr(prior(miItr)); 13938283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames SlotIndex loadIndex = 1402debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen lis->InsertMachineInstrInMaps(loadInstr).getRegSlot(); 14138283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames SlotIndex endIndex = loadIndex.getNextIndex(); 14238283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames VNInfo *loadVNI = 1433b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen newLI->getNextValue(loadIndex, lis->getVNInfoAllocator()); 14438283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames newLI->addRange(LiveRange(loadIndex, endIndex, loadVNI)); 145e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 146e2b201bac382464496758d789cddefa50690fbe3Lang Hames 14738283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Insert store if necessary. 148e2b201bac382464496758d789cddefa50690fbe3Lang Hames if (hasDef) { 1491485455be0310c6b24f096823029e08867531016Lang Hames tii->storeRegToStackSlot(*mi->getParent(), llvm::next(miItr),newLI->reg, 150746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng true, ss, trc, tri); 1517896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineInstr *storeInstr(llvm::next(miItr)); 15238283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames SlotIndex storeIndex = 1532debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen lis->InsertMachineInstrInMaps(storeInstr).getRegSlot(); 15438283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames SlotIndex beginIndex = storeIndex.getPrevIndex(); 15538283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames VNInfo *storeVNI = 1563b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen newLI->getNextValue(beginIndex, lis->getVNInfoAllocator()); 15738283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames newLI->addRange(LiveRange(beginIndex, storeIndex, storeVNI)); 158e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 159e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 160e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 161f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames}; 162e2b201bac382464496758d789cddefa50690fbe3Lang Hames 1631ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner} // end anonymous namespace 1641ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner 1651ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattnernamespace { 166e2b201bac382464496758d789cddefa50690fbe3Lang Hames 167f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames/// Spills any live range using the spill-everywhere method with no attempt at 168f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames/// folding. 169f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamesclass TrivialSpiller : public SpillerBase { 170f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamespublic: 17110382fb71d8306f320ecbeb7049d25354c0e5457Lang Hames 172f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen TrivialSpiller(MachineFunctionPass &pass, MachineFunction &mf, 173f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen VirtRegMap &vrm) 174f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen : SpillerBase(pass, mf, vrm) {} 175e2b201bac382464496758d789cddefa50690fbe3Lang Hames 17647dbf6cef761c25cfeb0aa7d624a6f98288bb96aJakob Stoklund Olesen void spill(LiveRangeEdit &LRE) { 177835ca07991c1b8ec47240b15417e1b2732480094Lang Hames // Ignore spillIs - we don't use it. 1781485455be0310c6b24f096823029e08867531016Lang Hames trivialSpillEverywhere(LRE); 179e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 180e2b201bac382464496758d789cddefa50690fbe3Lang Hames}; 181e2b201bac382464496758d789cddefa50690fbe3Lang Hames 1821ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner} // end anonymous namespace 1831ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner 1842d24e2a396a1d211baaeedf32148a3b657240170David Blaikievoid Spiller::anchor() { } 1852d24e2a396a1d211baaeedf32148a3b657240170David Blaikie 186f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesenllvm::Spiller* llvm::createSpiller(MachineFunctionPass &pass, 187f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen MachineFunction &mf, 188f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen VirtRegMap &vrm) { 189835ca07991c1b8ec47240b15417e1b2732480094Lang Hames switch (spillerOpt) { 190f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen case trivial: return new TrivialSpiller(pass, mf, vrm); 191f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen case inline_: return createInlineSpiller(pass, mf, vrm); 192835ca07991c1b8ec47240b15417e1b2732480094Lang Hames } 193732f05c41f177a0bc4d47e93a5d02120f146cb4cChandler Carruth llvm_unreachable("Invalid spiller optimization"); 194e2b201bac382464496758d789cddefa50690fbe3Lang Hames} 195