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#include "Spiller.h" 11e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/CodeGen/LiveIntervalAnalysis.h" 12789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 132d17293dd00d32208c7857ecdb20b79b0225c353Jakob Stoklund Olesen#include "llvm/CodeGen/LiveStackAnalysis.h" 14c75e7d2a06205f6c9870624eb5e8174a2b7b1bddBill Wendling#include "llvm/CodeGen/MachineFrameInfo.h" 15e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/CodeGen/MachineFunction.h" 161e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 17f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 18e2b201bac382464496758d789cddefa50690fbe3Lang Hames#include "llvm/CodeGen/MachineRegisterInfo.h" 191ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/VirtRegMap.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" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 25d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 26e2b201bac382464496758d789cddefa50690fbe3Lang Hames 27e2b201bac382464496758d789cddefa50690fbe3Lang Hamesusing namespace llvm; 28e2b201bac382464496758d789cddefa50690fbe3Lang Hames 29dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "spiller" 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 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 80eb3602472026dc029beb45ccbe09bc84162ba949Aaron Ballman assert(li->weight != llvm::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. 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineRegisterInfo::reg_instr_iterator 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines regItr = mri->reg_instr_begin(li->reg); 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines regItr != mri->reg_instr_end();) { 95e2b201bac382464496758d789cddefa50690fbe3Lang Hames 9638283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Grab the use/def instr. 97e2b201bac382464496758d789cddefa50690fbe3Lang Hames MachineInstr *mi = &*regItr; 986bbc73d3fd274e15297eb2c3e4172e43ce7bc8f8Lang Hames 9965de504ad226a0b2adc6c675115863a8e583ac1fDavid Greene DEBUG(dbgs() << " Processing " << *mi); 1006bbc73d3fd274e15297eb2c3e4172e43ce7bc8f8Lang Hames 10138283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Step regItr to the next use/def instr. 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++regItr; 103894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 10438283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Collect uses & defs for this instr. 105e2b201bac382464496758d789cddefa50690fbe3Lang Hames SmallVector<unsigned, 2> indices; 106e2b201bac382464496758d789cddefa50690fbe3Lang Hames bool hasUse = false; 107e2b201bac382464496758d789cddefa50690fbe3Lang Hames bool hasDef = false; 108e2b201bac382464496758d789cddefa50690fbe3Lang Hames for (unsigned i = 0; i != mi->getNumOperands(); ++i) { 109e2b201bac382464496758d789cddefa50690fbe3Lang Hames MachineOperand &op = mi->getOperand(i); 110e2b201bac382464496758d789cddefa50690fbe3Lang Hames if (!op.isReg() || op.getReg() != li->reg) 111e2b201bac382464496758d789cddefa50690fbe3Lang Hames continue; 112e2b201bac382464496758d789cddefa50690fbe3Lang Hames hasUse |= mi->getOperand(i).isUse(); 113e2b201bac382464496758d789cddefa50690fbe3Lang Hames hasDef |= mi->getOperand(i).isDef(); 114e2b201bac382464496758d789cddefa50690fbe3Lang Hames indices.push_back(i); 115e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 116e2b201bac382464496758d789cddefa50690fbe3Lang Hames 117e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey // Create a new virtual register for the load and/or store. 118e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey unsigned NewVReg = LRE.create(); 119894339e19fbb45a729008decd1d050ee518589a4Eric Christopher 12038283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Update the reg operands & kill flags. 121e2b201bac382464496758d789cddefa50690fbe3Lang Hames for (unsigned i = 0; i < indices.size(); ++i) { 12238283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames unsigned mopIdx = indices[i]; 12338283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames MachineOperand &mop = mi->getOperand(mopIdx); 124e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey mop.setReg(NewVReg); 12538283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames if (mop.isUse() && !mi->isRegTiedToDefOperand(mopIdx)) { 12638283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames mop.setIsKill(true); 127e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 128e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 129f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames assert(hasUse || hasDef); 130f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 13138283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Insert reload if necessary. 13238283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames MachineBasicBlock::iterator miItr(mi); 133e2b201bac382464496758d789cddefa50690fbe3Lang Hames if (hasUse) { 134e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey MachineInstrSpan MIS(miItr); 135e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey 136e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey tii->loadRegFromStackSlot(*mi->getParent(), miItr, NewVReg, ss, trc, 137746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng tri); 138e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey lis->InsertMachineInstrRangeInMaps(MIS.begin(), miItr); 139e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 140e2b201bac382464496758d789cddefa50690fbe3Lang Hames 14138283e23df5aa748ec3bb5f02f14f1741cf491ceLang Hames // Insert store if necessary. 142e2b201bac382464496758d789cddefa50690fbe3Lang Hames if (hasDef) { 143e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey MachineInstrSpan MIS(miItr); 144e742d687369f79702894b6cf302e1f222c5d7432Mark Lacey 14536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines tii->storeRegToStackSlot(*mi->getParent(), std::next(miItr), NewVReg, 146746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng true, ss, trc, tri); 14736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines lis->InsertMachineInstrRangeInMaps(std::next(miItr), MIS.end()); 148e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 149e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 150e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 151f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames}; 152e2b201bac382464496758d789cddefa50690fbe3Lang Hames 1531ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner} // end anonymous namespace 1541ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner 1551ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattnernamespace { 156e2b201bac382464496758d789cddefa50690fbe3Lang Hames 157f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames/// Spills any live range using the spill-everywhere method with no attempt at 158f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames/// folding. 159f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamesclass TrivialSpiller : public SpillerBase { 160f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamespublic: 16110382fb71d8306f320ecbeb7049d25354c0e5457Lang Hames 162f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen TrivialSpiller(MachineFunctionPass &pass, MachineFunction &mf, 163f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen VirtRegMap &vrm) 164f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen : SpillerBase(pass, mf, vrm) {} 165e2b201bac382464496758d789cddefa50690fbe3Lang Hames 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void spill(LiveRangeEdit &LRE) override { 167835ca07991c1b8ec47240b15417e1b2732480094Lang Hames // Ignore spillIs - we don't use it. 1681485455be0310c6b24f096823029e08867531016Lang Hames trivialSpillEverywhere(LRE); 169e2b201bac382464496758d789cddefa50690fbe3Lang Hames } 170e2b201bac382464496758d789cddefa50690fbe3Lang Hames}; 171e2b201bac382464496758d789cddefa50690fbe3Lang Hames 1721ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner} // end anonymous namespace 1731ca6531e2e8e1b3a4f6c48888568450ecf614004Chris Lattner 1742d24e2a396a1d211baaeedf32148a3b657240170David Blaikievoid Spiller::anchor() { } 1752d24e2a396a1d211baaeedf32148a3b657240170David Blaikie 176f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesenllvm::Spiller* llvm::createSpiller(MachineFunctionPass &pass, 177f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen MachineFunction &mf, 178f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen VirtRegMap &vrm) { 179835ca07991c1b8ec47240b15417e1b2732480094Lang Hames switch (spillerOpt) { 180f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen case trivial: return new TrivialSpiller(pass, mf, vrm); 181f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen case inline_: return createInlineSpiller(pass, mf, vrm); 182835ca07991c1b8ec47240b15417e1b2732480094Lang Hames } 183732f05c41f177a0bc4d47e93a5d02120f146cb4cChandler Carruth llvm_unreachable("Invalid spiller optimization"); 184e2b201bac382464496758d789cddefa50690fbe3Lang Hames} 185