1 //===-- llvm/CodeGen/Spiller.cpp - Spiller -------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #define DEBUG_TYPE "spiller" 11 12 #include "Spiller.h" 13 #include "VirtRegMap.h" 14 #include "LiveRangeEdit.h" 15 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 16 #include "llvm/CodeGen/LiveStackAnalysis.h" 17 #include "llvm/CodeGen/MachineFrameInfo.h" 18 #include "llvm/CodeGen/MachineFunction.h" 19 #include "llvm/CodeGen/MachineInstrBuilder.h" 20 #include "llvm/CodeGen/MachineLoopInfo.h" 21 #include "llvm/CodeGen/MachineRegisterInfo.h" 22 #include "llvm/Target/TargetMachine.h" 23 #include "llvm/Target/TargetInstrInfo.h" 24 #include "llvm/Support/CommandLine.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/ErrorHandling.h" 27 #include "llvm/Support/raw_ostream.h" 28 29 using namespace llvm; 30 31 namespace { 32 enum SpillerName { trivial, standard, inline_ }; 33 } 34 35 static cl::opt<SpillerName> 36 spillerOpt("spiller", 37 cl::desc("Spiller to use: (default: standard)"), 38 cl::Prefix, 39 cl::values(clEnumVal(trivial, "trivial spiller"), 40 clEnumVal(standard, "default spiller"), 41 clEnumValN(inline_, "inline", "inline spiller"), 42 clEnumValEnd), 43 cl::init(standard)); 44 45 // Spiller virtual destructor implementation. 46 Spiller::~Spiller() {} 47 48 namespace { 49 50 /// Utility class for spillers. 51 class SpillerBase : public Spiller { 52 protected: 53 MachineFunctionPass *pass; 54 MachineFunction *mf; 55 VirtRegMap *vrm; 56 LiveIntervals *lis; 57 MachineFrameInfo *mfi; 58 MachineRegisterInfo *mri; 59 const TargetInstrInfo *tii; 60 const TargetRegisterInfo *tri; 61 62 /// Construct a spiller base. 63 SpillerBase(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm) 64 : pass(&pass), mf(&mf), vrm(&vrm) 65 { 66 lis = &pass.getAnalysis<LiveIntervals>(); 67 mfi = mf.getFrameInfo(); 68 mri = &mf.getRegInfo(); 69 tii = mf.getTarget().getInstrInfo(); 70 tri = mf.getTarget().getRegisterInfo(); 71 } 72 73 /// Add spill ranges for every use/def of the live interval, inserting loads 74 /// immediately before each use, and stores after each def. No folding or 75 /// remat is attempted. 76 void trivialSpillEverywhere(LiveInterval *li, 77 SmallVectorImpl<LiveInterval*> &newIntervals) { 78 DEBUG(dbgs() << "Spilling everywhere " << *li << "\n"); 79 80 assert(li->weight != HUGE_VALF && 81 "Attempting to spill already spilled value."); 82 83 assert(!TargetRegisterInfo::isStackSlot(li->reg) && 84 "Trying to spill a stack slot."); 85 86 DEBUG(dbgs() << "Trivial spill everywhere of reg" << li->reg << "\n"); 87 88 const TargetRegisterClass *trc = mri->getRegClass(li->reg); 89 unsigned ss = vrm->assignVirt2StackSlot(li->reg); 90 91 // Iterate over reg uses/defs. 92 for (MachineRegisterInfo::reg_iterator 93 regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) { 94 95 // Grab the use/def instr. 96 MachineInstr *mi = &*regItr; 97 98 DEBUG(dbgs() << " Processing " << *mi); 99 100 // Step regItr to the next use/def instr. 101 do { 102 ++regItr; 103 } while (regItr != mri->reg_end() && (&*regItr == mi)); 104 105 // Collect uses & defs for this instr. 106 SmallVector<unsigned, 2> indices; 107 bool hasUse = false; 108 bool hasDef = false; 109 for (unsigned i = 0; i != mi->getNumOperands(); ++i) { 110 MachineOperand &op = mi->getOperand(i); 111 if (!op.isReg() || op.getReg() != li->reg) 112 continue; 113 hasUse |= mi->getOperand(i).isUse(); 114 hasDef |= mi->getOperand(i).isDef(); 115 indices.push_back(i); 116 } 117 118 // Create a new vreg & interval for this instr. 119 unsigned newVReg = mri->createVirtualRegister(trc); 120 vrm->grow(); 121 vrm->assignVirt2StackSlot(newVReg, ss); 122 LiveInterval *newLI = &lis->getOrCreateInterval(newVReg); 123 newLI->weight = HUGE_VALF; 124 125 // Update the reg operands & kill flags. 126 for (unsigned i = 0; i < indices.size(); ++i) { 127 unsigned mopIdx = indices[i]; 128 MachineOperand &mop = mi->getOperand(mopIdx); 129 mop.setReg(newVReg); 130 if (mop.isUse() && !mi->isRegTiedToDefOperand(mopIdx)) { 131 mop.setIsKill(true); 132 } 133 } 134 assert(hasUse || hasDef); 135 136 // Insert reload if necessary. 137 MachineBasicBlock::iterator miItr(mi); 138 if (hasUse) { 139 tii->loadRegFromStackSlot(*mi->getParent(), miItr, newVReg, ss, trc, 140 tri); 141 MachineInstr *loadInstr(prior(miItr)); 142 SlotIndex loadIndex = 143 lis->InsertMachineInstrInMaps(loadInstr).getDefIndex(); 144 vrm->addSpillSlotUse(ss, loadInstr); 145 SlotIndex endIndex = loadIndex.getNextIndex(); 146 VNInfo *loadVNI = 147 newLI->getNextValue(loadIndex, 0, lis->getVNInfoAllocator()); 148 newLI->addRange(LiveRange(loadIndex, endIndex, loadVNI)); 149 } 150 151 // Insert store if necessary. 152 if (hasDef) { 153 tii->storeRegToStackSlot(*mi->getParent(), llvm::next(miItr), newVReg, 154 true, ss, trc, tri); 155 MachineInstr *storeInstr(llvm::next(miItr)); 156 SlotIndex storeIndex = 157 lis->InsertMachineInstrInMaps(storeInstr).getDefIndex(); 158 vrm->addSpillSlotUse(ss, storeInstr); 159 SlotIndex beginIndex = storeIndex.getPrevIndex(); 160 VNInfo *storeVNI = 161 newLI->getNextValue(beginIndex, 0, lis->getVNInfoAllocator()); 162 newLI->addRange(LiveRange(beginIndex, storeIndex, storeVNI)); 163 } 164 165 newIntervals.push_back(newLI); 166 } 167 } 168 }; 169 170 } // end anonymous namespace 171 172 namespace { 173 174 /// Spills any live range using the spill-everywhere method with no attempt at 175 /// folding. 176 class TrivialSpiller : public SpillerBase { 177 public: 178 179 TrivialSpiller(MachineFunctionPass &pass, MachineFunction &mf, 180 VirtRegMap &vrm) 181 : SpillerBase(pass, mf, vrm) {} 182 183 void spill(LiveRangeEdit &LRE) { 184 // Ignore spillIs - we don't use it. 185 trivialSpillEverywhere(&LRE.getParent(), *LRE.getNewVRegs()); 186 } 187 }; 188 189 } // end anonymous namespace 190 191 namespace { 192 193 /// Falls back on LiveIntervals::addIntervalsForSpills. 194 class StandardSpiller : public Spiller { 195 protected: 196 MachineFunction *mf; 197 LiveIntervals *lis; 198 LiveStacks *lss; 199 MachineLoopInfo *loopInfo; 200 VirtRegMap *vrm; 201 public: 202 StandardSpiller(MachineFunctionPass &pass, MachineFunction &mf, 203 VirtRegMap &vrm) 204 : mf(&mf), 205 lis(&pass.getAnalysis<LiveIntervals>()), 206 lss(&pass.getAnalysis<LiveStacks>()), 207 loopInfo(pass.getAnalysisIfAvailable<MachineLoopInfo>()), 208 vrm(&vrm) {} 209 210 /// Falls back on LiveIntervals::addIntervalsForSpills. 211 void spill(LiveRangeEdit &LRE) { 212 std::vector<LiveInterval*> added = 213 lis->addIntervalsForSpills(LRE.getParent(), LRE.getUselessVRegs(), 214 loopInfo, *vrm); 215 LRE.getNewVRegs()->insert(LRE.getNewVRegs()->end(), 216 added.begin(), added.end()); 217 218 // Update LiveStacks. 219 int SS = vrm->getStackSlot(LRE.getReg()); 220 if (SS == VirtRegMap::NO_STACK_SLOT) 221 return; 222 const TargetRegisterClass *RC = mf->getRegInfo().getRegClass(LRE.getReg()); 223 LiveInterval &SI = lss->getOrCreateInterval(SS, RC); 224 if (!SI.hasAtLeastOneValue()) 225 SI.getNextValue(SlotIndex(), 0, lss->getVNInfoAllocator()); 226 SI.MergeRangesInAsValue(LRE.getParent(), SI.getValNumInfo(0)); 227 } 228 }; 229 230 } // end anonymous namespace 231 232 llvm::Spiller* llvm::createSpiller(MachineFunctionPass &pass, 233 MachineFunction &mf, 234 VirtRegMap &vrm) { 235 switch (spillerOpt) { 236 default: assert(0 && "unknown spiller"); 237 case trivial: return new TrivialSpiller(pass, mf, vrm); 238 case standard: return new StandardSpiller(pass, mf, vrm); 239 case inline_: return createInlineSpiller(pass, mf, vrm); 240 } 241 } 242
