Spiller.cpp revision 8783e401a3ad187dcd0f306153f9339f7270621d
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 "llvm/CodeGen/LiveIntervalAnalysis.h" 15#include "llvm/CodeGen/MachineFrameInfo.h" 16#include "llvm/CodeGen/MachineFunction.h" 17#include "llvm/CodeGen/MachineRegisterInfo.h" 18#include "llvm/Target/TargetMachine.h" 19#include "llvm/Target/TargetInstrInfo.h" 20#include "llvm/Support/CommandLine.h" 21#include "llvm/Support/Debug.h" 22#include "llvm/Support/raw_ostream.h" 23 24using namespace llvm; 25 26namespace { 27 enum SpillerName { trivial, standard }; 28} 29 30static cl::opt<SpillerName> 31spillerOpt("spiller", 32 cl::desc("Spiller to use: (default: standard)"), 33 cl::Prefix, 34 cl::values(clEnumVal(trivial, "trivial spiller"), 35 clEnumVal(standard, "default spiller"), 36 clEnumValEnd), 37 cl::init(standard)); 38 39Spiller::~Spiller() {} 40 41namespace { 42 43/// Utility class for spillers. 44class SpillerBase : public Spiller { 45protected: 46 47 MachineFunction *mf; 48 LiveIntervals *lis; 49 MachineFrameInfo *mfi; 50 MachineRegisterInfo *mri; 51 const TargetInstrInfo *tii; 52 VirtRegMap *vrm; 53 54 /// Construct a spiller base. 55 SpillerBase(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm) 56 : mf(mf), lis(lis), vrm(vrm) 57 { 58 mfi = mf->getFrameInfo(); 59 mri = &mf->getRegInfo(); 60 tii = mf->getTarget().getInstrInfo(); 61 } 62 63 /// Add spill ranges for every use/def of the live interval, inserting loads 64 /// immediately before each use, and stores after each def. No folding or 65 /// remat is attempted. 66 std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) { 67 DEBUG(errs() << "Spilling everywhere " << *li << "\n"); 68 69 assert(li->weight != HUGE_VALF && 70 "Attempting to spill already spilled value."); 71 72 assert(!li->isStackSlot() && 73 "Trying to spill a stack slot."); 74 75 DEBUG(errs() << "Trivial spill everywhere of reg" << li->reg << "\n"); 76 77 std::vector<LiveInterval*> added; 78 79 const TargetRegisterClass *trc = mri->getRegClass(li->reg); 80 unsigned ss = vrm->assignVirt2StackSlot(li->reg); 81 82 // Iterate over reg uses/defs. 83 for (MachineRegisterInfo::reg_iterator 84 regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) { 85 86 // Grab the use/def instr. 87 MachineInstr *mi = &*regItr; 88 89 DEBUG(errs() << " Processing " << *mi); 90 91 // Step regItr to the next use/def instr. 92 do { 93 ++regItr; 94 } while (regItr != mri->reg_end() && (&*regItr == mi)); 95 96 // Collect uses & defs for this instr. 97 SmallVector<unsigned, 2> indices; 98 bool hasUse = false; 99 bool hasDef = false; 100 for (unsigned i = 0; i != mi->getNumOperands(); ++i) { 101 MachineOperand &op = mi->getOperand(i); 102 if (!op.isReg() || op.getReg() != li->reg) 103 continue; 104 hasUse |= mi->getOperand(i).isUse(); 105 hasDef |= mi->getOperand(i).isDef(); 106 indices.push_back(i); 107 } 108 109 // Create a new vreg & interval for this instr. 110 unsigned newVReg = mri->createVirtualRegister(trc); 111 vrm->grow(); 112 vrm->assignVirt2StackSlot(newVReg, ss); 113 LiveInterval *newLI = &lis->getOrCreateInterval(newVReg); 114 newLI->weight = HUGE_VALF; 115 116 // Update the reg operands & kill flags. 117 for (unsigned i = 0; i < indices.size(); ++i) { 118 unsigned mopIdx = indices[i]; 119 MachineOperand &mop = mi->getOperand(mopIdx); 120 mop.setReg(newVReg); 121 if (mop.isUse() && !mi->isRegTiedToDefOperand(mopIdx)) { 122 mop.setIsKill(true); 123 } 124 } 125 assert(hasUse || hasDef); 126 127 // Insert reload if necessary. 128 MachineBasicBlock::iterator miItr(mi); 129 if (hasUse) { 130 tii->loadRegFromStackSlot(*mi->getParent(), miItr, newVReg, ss, trc); 131 MachineInstr *loadInstr(prior(miItr)); 132 SlotIndex loadIndex = 133 lis->InsertMachineInstrInMaps(loadInstr).getDefIndex(); 134 SlotIndex endIndex = loadIndex.getNextIndex(); 135 VNInfo *loadVNI = 136 newLI->getNextValue(loadIndex, 0, true, lis->getVNInfoAllocator()); 137 loadVNI->addKill(endIndex); 138 newLI->addRange(LiveRange(loadIndex, endIndex, loadVNI)); 139 } 140 141 // Insert store if necessary. 142 if (hasDef) { 143 tii->storeRegToStackSlot(*mi->getParent(), next(miItr), newVReg, true, 144 ss, trc); 145 MachineInstr *storeInstr(next(miItr)); 146 SlotIndex storeIndex = 147 lis->InsertMachineInstrInMaps(storeInstr).getDefIndex(); 148 SlotIndex beginIndex = storeIndex.getPrevIndex(); 149 VNInfo *storeVNI = 150 newLI->getNextValue(beginIndex, 0, true, lis->getVNInfoAllocator()); 151 storeVNI->addKill(storeIndex); 152 newLI->addRange(LiveRange(beginIndex, storeIndex, storeVNI)); 153 } 154 155 added.push_back(newLI); 156 } 157 158 return added; 159 } 160 161}; 162 163 164/// Spills any live range using the spill-everywhere method with no attempt at 165/// folding. 166class TrivialSpiller : public SpillerBase { 167public: 168 169 TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm) 170 : SpillerBase(mf, lis, vrm) {} 171 172 std::vector<LiveInterval*> spill(LiveInterval *li, 173 SmallVectorImpl<LiveInterval*> &spillIs) { 174 // Ignore spillIs - we don't use it. 175 return trivialSpillEverywhere(li); 176 } 177 178}; 179 180/// Falls back on LiveIntervals::addIntervalsForSpills. 181class StandardSpiller : public Spiller { 182private: 183 LiveIntervals *lis; 184 const MachineLoopInfo *loopInfo; 185 VirtRegMap *vrm; 186public: 187 StandardSpiller(MachineFunction *mf, LiveIntervals *lis, 188 const MachineLoopInfo *loopInfo, VirtRegMap *vrm) 189 : lis(lis), loopInfo(loopInfo), vrm(vrm) {} 190 191 /// Falls back on LiveIntervals::addIntervalsForSpills. 192 std::vector<LiveInterval*> spill(LiveInterval *li, 193 SmallVectorImpl<LiveInterval*> &spillIs) { 194 return lis->addIntervalsForSpills(*li, spillIs, loopInfo, *vrm); 195 } 196 197}; 198 199} 200 201llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis, 202 const MachineLoopInfo *loopInfo, 203 VirtRegMap *vrm) { 204 switch (spillerOpt) { 205 case trivial: return new TrivialSpiller(mf, lis, vrm); break; 206 case standard: return new StandardSpiller(mf, lis, loopInfo, vrm); break; 207 default: llvm_unreachable("Unreachable!"); break; 208 } 209} 210