LLVM API Documentation
00001 //===-- llvm/CodeGen/Spiller.cpp - Spiller -------------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 00010 #define DEBUG_TYPE "spiller" 00011 00012 #include "Spiller.h" 00013 #include "VirtRegMap.h" 00014 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 00015 #include "llvm/CodeGen/LiveStackAnalysis.h" 00016 #include "llvm/CodeGen/MachineFunction.h" 00017 #include "llvm/CodeGen/MachineRegisterInfo.h" 00018 #include "llvm/CodeGen/MachineFrameInfo.h" 00019 #include "llvm/Target/TargetMachine.h" 00020 #include "llvm/Target/TargetInstrInfo.h" 00021 #include "llvm/Support/Debug.h" 00022 00023 using namespace llvm; 00024 00025 Spiller::~Spiller() {} 00026 00027 namespace { 00028 00029 /// Utility class for spillers. 00030 class SpillerBase : public Spiller { 00031 protected: 00032 00033 MachineFunction *mf; 00034 LiveIntervals *lis; 00035 LiveStacks *ls; 00036 MachineFrameInfo *mfi; 00037 MachineRegisterInfo *mri; 00038 const TargetInstrInfo *tii; 00039 VirtRegMap *vrm; 00040 00041 /// Construct a spiller base. 00042 SpillerBase(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, 00043 VirtRegMap *vrm) : 00044 mf(mf), lis(lis), ls(ls), vrm(vrm) 00045 { 00046 mfi = mf->getFrameInfo(); 00047 mri = &mf->getRegInfo(); 00048 tii = mf->getTarget().getInstrInfo(); 00049 } 00050 00051 /// Ensures there is space before the given machine instruction, returns the 00052 /// instruction's new number. 00053 unsigned makeSpaceBefore(MachineInstr *mi) { 00054 if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) { 00055 lis->scaleNumbering(2); 00056 ls->scaleNumbering(2); 00057 } 00058 00059 unsigned miIdx = lis->getInstructionIndex(mi); 00060 00061 assert(lis->hasGapBeforeInstr(miIdx)); 00062 00063 return miIdx; 00064 } 00065 00066 /// Ensure there is space after the given machine instruction, returns the 00067 /// instruction's new number. 00068 unsigned makeSpaceAfter(MachineInstr *mi) { 00069 if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) { 00070 lis->scaleNumbering(2); 00071 ls->scaleNumbering(2); 00072 } 00073 00074 unsigned miIdx = lis->getInstructionIndex(mi); 00075 00076 assert(lis->hasGapAfterInstr(miIdx)); 00077 00078 return miIdx; 00079 } 00080 00081 /// Insert a store of the given vreg to the given stack slot immediately 00082 /// after the given instruction. Returns the base index of the inserted 00083 /// instruction. The caller is responsible for adding an appropriate 00084 /// LiveInterval to the LiveIntervals analysis. 00085 unsigned insertStoreAfter(MachineInstr *mi, unsigned ss, 00086 unsigned vreg, 00087 const TargetRegisterClass *trc) { 00088 00089 MachineBasicBlock::iterator nextInstItr(next(mi)); 00090 00091 unsigned miIdx = makeSpaceAfter(mi); 00092 00093 tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, vreg, 00094 true, ss, trc); 00095 MachineBasicBlock::iterator storeInstItr(next(mi)); 00096 MachineInstr *storeInst = &*storeInstItr; 00097 unsigned storeInstIdx = miIdx + LiveInterval::InstrSlots::NUM; 00098 00099 assert(lis->getInstructionFromIndex(storeInstIdx) == 0 && 00100 "Store inst index already in use."); 00101 00102 lis->InsertMachineInstrInMaps(storeInst, storeInstIdx); 00103 00104 return storeInstIdx; 00105 } 00106 00107 /// Insert a store of the given vreg to the given stack slot immediately 00108 /// before the given instructnion. Returns the base index of the inserted 00109 /// Instruction. 00110 unsigned insertStoreBefore(MachineInstr *mi, unsigned ss, 00111 unsigned vreg, 00112 const TargetRegisterClass *trc) { 00113 unsigned miIdx = makeSpaceBefore(mi); 00114 00115 tii->storeRegToStackSlot(*mi->getParent(), mi, vreg, true, ss, trc); 00116 MachineBasicBlock::iterator storeInstItr(prior(mi)); 00117 MachineInstr *storeInst = &*storeInstItr; 00118 unsigned storeInstIdx = miIdx - LiveInterval::InstrSlots::NUM; 00119 00120 assert(lis->getInstructionFromIndex(storeInstIdx) == 0 && 00121 "Store inst index already in use."); 00122 00123 lis->InsertMachineInstrInMaps(storeInst, storeInstIdx); 00124 00125 return storeInstIdx; 00126 } 00127 00128 void insertStoreAfterInstOnInterval(LiveInterval *li, 00129 MachineInstr *mi, unsigned ss, 00130 unsigned vreg, 00131 const TargetRegisterClass *trc) { 00132 00133 unsigned storeInstIdx = insertStoreAfter(mi, ss, vreg, trc); 00134 unsigned start = lis->getDefIndex(lis->getInstructionIndex(mi)), 00135 end = lis->getUseIndex(storeInstIdx); 00136 00137 VNInfo *vni = 00138 li->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator()); 00139 li->addKill(vni, storeInstIdx, false); 00140 DOUT << " Inserting store range: [" << start << ", " << end << ")\n"; 00141 LiveRange lr(start, end, vni); 00142 00143 li->addRange(lr); 00144 } 00145 00146 /// Insert a load of the given vreg from the given stack slot immediately 00147 /// after the given instruction. Returns the base index of the inserted 00148 /// instruction. The caller is responsibel for adding/removing an appropriate 00149 /// range vreg's LiveInterval. 00150 unsigned insertLoadAfter(MachineInstr *mi, unsigned ss, 00151 unsigned vreg, 00152 const TargetRegisterClass *trc) { 00153 00154 MachineBasicBlock::iterator nextInstItr(next(mi)); 00155 00156 unsigned miIdx = makeSpaceAfter(mi); 00157 00158 tii->loadRegFromStackSlot(*mi->getParent(), nextInstItr, vreg, ss, trc); 00159 MachineBasicBlock::iterator loadInstItr(next(mi)); 00160 MachineInstr *loadInst = &*loadInstItr; 00161 unsigned loadInstIdx = miIdx + LiveInterval::InstrSlots::NUM; 00162 00163 assert(lis->getInstructionFromIndex(loadInstIdx) == 0 && 00164 "Store inst index already in use."); 00165 00166 lis->InsertMachineInstrInMaps(loadInst, loadInstIdx); 00167 00168 return loadInstIdx; 00169 } 00170 00171 /// Insert a load of the given vreg from the given stack slot immediately 00172 /// before the given instruction. Returns the base index of the inserted 00173 /// instruction. The caller is responsible for adding an appropriate 00174 /// LiveInterval to the LiveIntervals analysis. 00175 unsigned insertLoadBefore(MachineInstr *mi, unsigned ss, 00176 unsigned vreg, 00177 const TargetRegisterClass *trc) { 00178 unsigned miIdx = makeSpaceBefore(mi); 00179 00180 tii->loadRegFromStackSlot(*mi->getParent(), mi, vreg, ss, trc); 00181 MachineBasicBlock::iterator loadInstItr(prior(mi)); 00182 MachineInstr *loadInst = &*loadInstItr; 00183 unsigned loadInstIdx = miIdx - LiveInterval::InstrSlots::NUM; 00184 00185 assert(lis->getInstructionFromIndex(loadInstIdx) == 0 && 00186 "Load inst index already in use."); 00187 00188 lis->InsertMachineInstrInMaps(loadInst, loadInstIdx); 00189 00190 return loadInstIdx; 00191 } 00192 00193 void insertLoadBeforeInstOnInterval(LiveInterval *li, 00194 MachineInstr *mi, unsigned ss, 00195 unsigned vreg, 00196 const TargetRegisterClass *trc) { 00197 00198 unsigned loadInstIdx = insertLoadBefore(mi, ss, vreg, trc); 00199 unsigned start = lis->getDefIndex(loadInstIdx), 00200 end = lis->getUseIndex(lis->getInstructionIndex(mi)); 00201 00202 VNInfo *vni = 00203 li->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator()); 00204 li->addKill(vni, lis->getInstructionIndex(mi), false); 00205 DOUT << " Intserting load range: [" << start << ", " << end << ")\n"; 00206 LiveRange lr(start, end, vni); 00207 00208 li->addRange(lr); 00209 } 00210 00211 00212 00213 /// Add spill ranges for every use/def of the live interval, inserting loads 00214 /// immediately before each use, and stores after each def. No folding is 00215 /// attempted. 00216 std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) { 00217 DOUT << "Spilling everywhere " << *li << "\n"; 00218 00219 assert(li->weight != HUGE_VALF && 00220 "Attempting to spill already spilled value."); 00221 00222 assert(!li->isStackSlot() && 00223 "Trying to spill a stack slot."); 00224 00225 DOUT << "Trivial spill everywhere of reg" << li->reg << "\n"; 00226 00227 std::vector<LiveInterval*> added; 00228 00229 const TargetRegisterClass *trc = mri->getRegClass(li->reg); 00230 unsigned ss = vrm->assignVirt2StackSlot(li->reg); 00231 00232 for (MachineRegisterInfo::reg_iterator 00233 regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) { 00234 00235 MachineInstr *mi = &*regItr; 00236 00237 DOUT << " Processing " << *mi; 00238 00239 do { 00240 ++regItr; 00241 } while (regItr != mri->reg_end() && (&*regItr == mi)); 00242 00243 SmallVector<unsigned, 2> indices; 00244 bool hasUse = false; 00245 bool hasDef = false; 00246 00247 for (unsigned i = 0; i != mi->getNumOperands(); ++i) { 00248 MachineOperand &op = mi->getOperand(i); 00249 00250 if (!op.isReg() || op.getReg() != li->reg) 00251 continue; 00252 00253 hasUse |= mi->getOperand(i).isUse(); 00254 hasDef |= mi->getOperand(i).isDef(); 00255 00256 indices.push_back(i); 00257 } 00258 00259 unsigned newVReg = mri->createVirtualRegister(trc); 00260 vrm->grow(); 00261 vrm->assignVirt2StackSlot(newVReg, ss); 00262 00263 LiveInterval *newLI = &lis->getOrCreateInterval(newVReg); 00264 newLI->weight = HUGE_VALF; 00265 00266 for (unsigned i = 0; i < indices.size(); ++i) { 00267 mi->getOperand(indices[i]).setReg(newVReg); 00268 00269 if (mi->getOperand(indices[i]).isUse()) { 00270 mi->getOperand(indices[i]).setIsKill(true); 00271 } 00272 } 00273 00274 assert(hasUse || hasDef); 00275 00276 if (hasUse) { 00277 insertLoadBeforeInstOnInterval(newLI, mi, ss, newVReg, trc); 00278 } 00279 00280 if (hasDef) { 00281 insertStoreAfterInstOnInterval(newLI, mi, ss, newVReg, trc); 00282 } 00283 00284 added.push_back(newLI); 00285 } 00286 00287 return added; 00288 } 00289 00290 }; 00291 00292 00293 /// Spills any live range using the spill-everywhere method with no attempt at 00294 /// folding. 00295 class TrivialSpiller : public SpillerBase { 00296 public: 00297 00298 TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, 00299 VirtRegMap *vrm) : 00300 SpillerBase(mf, lis, ls, vrm) {} 00301 00302 std::vector<LiveInterval*> spill(LiveInterval *li) { 00303 return trivialSpillEverywhere(li); 00304 } 00305 00306 std::vector<LiveInterval*> intraBlockSplit(LiveInterval *li, VNInfo *valno) { 00307 std::vector<LiveInterval*> spillIntervals; 00308 00309 if (!valno->isDefAccurate() && !valno->isPHIDef()) { 00310 // Early out for values which have no well defined def point. 00311 return spillIntervals; 00312 } 00313 00314 // Ok.. we should be able to proceed... 00315 const TargetRegisterClass *trc = mri->getRegClass(li->reg); 00316 unsigned ss = vrm->assignVirt2StackSlot(li->reg); 00317 vrm->grow(); 00318 vrm->assignVirt2StackSlot(li->reg, ss); 00319 00320 MachineInstr *mi = 0; 00321 unsigned storeIdx = 0; 00322 00323 if (valno->isDefAccurate()) { 00324 // If we have an accurate def we can just grab an iterator to the instr 00325 // after the def. 00326 mi = lis->getInstructionFromIndex(valno->def); 00327 storeIdx = insertStoreAfter(mi, ss, li->reg, trc) + 00328 LiveInterval::InstrSlots::DEF; 00329 } else { 00330 // if we get here we have a PHI def. 00331 mi = &lis->getMBBFromIndex(valno->def)->front(); 00332 storeIdx = insertStoreBefore(mi, ss, li->reg, trc) + 00333 LiveInterval::InstrSlots::DEF; 00334 } 00335 00336 MachineBasicBlock *defBlock = mi->getParent(); 00337 unsigned loadIdx = 0; 00338 00339 // Now we need to find the load... 00340 MachineBasicBlock::iterator useItr(mi); 00341 for (; !useItr->readsRegister(li->reg); ++useItr) {} 00342 00343 if (useItr != defBlock->end()) { 00344 MachineInstr *loadInst = useItr; 00345 loadIdx = insertLoadBefore(loadInst, ss, li->reg, trc) + 00346 LiveInterval::InstrSlots::USE; 00347 } 00348 else { 00349 MachineInstr *loadInst = &defBlock->back(); 00350 loadIdx = insertLoadAfter(loadInst, ss, li->reg, trc) + 00351 LiveInterval::InstrSlots::USE; 00352 } 00353 00354 li->removeRange(storeIdx, loadIdx, true); 00355 00356 return spillIntervals; 00357 } 00358 00359 }; 00360 00361 } 00362 00363 llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis, 00364 LiveStacks *ls, VirtRegMap *vrm) { 00365 return new TrivialSpiller(mf, lis, ls, vrm); 00366 }