X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSpiller.cpp;h=b6bbcd7176dda1220378a82eefe72b613cc2e102;hb=df8412c4c1a3a798c5a849ebc3f56904568d40c4;hp=7e6f18789796666b707a23c4dd6b9e10e7ae65f4;hpb=cc3b0650f1feec45d1a2890b20c05c4b325f1788;p=oota-llvm.git diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp index 7e6f1878979..b6bbcd7176d 100644 --- a/lib/CodeGen/Spiller.cpp +++ b/lib/CodeGen/Spiller.cpp @@ -11,18 +11,38 @@ #include "Spiller.h" #include "VirtRegMap.h" +#include "LiveRangeEdit.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; +namespace { + enum SpillerName { trivial, standard, inline_ }; +} + +static cl::opt +spillerOpt("spiller", + cl::desc("Spiller to use: (default: standard)"), + cl::Prefix, + cl::values(clEnumVal(trivial, "trivial spiller"), + clEnumVal(standard, "default spiller"), + clEnumValN(inline_, "inline", "inline spiller"), + clEnumValEnd), + cl::init(standard)); + +// Spiller virtual destructor implementation. Spiller::~Spiller() {} namespace { @@ -30,336 +50,192 @@ namespace { /// Utility class for spillers. class SpillerBase : public Spiller { protected: - + MachineFunctionPass *pass; MachineFunction *mf; + VirtRegMap *vrm; LiveIntervals *lis; - LiveStacks *ls; MachineFrameInfo *mfi; MachineRegisterInfo *mri; const TargetInstrInfo *tii; - VirtRegMap *vrm; - - /// Construct a spiller base. - SpillerBase(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, - VirtRegMap *vrm) : - mf(mf), lis(lis), ls(ls), vrm(vrm) - { - mfi = mf->getFrameInfo(); - mri = &mf->getRegInfo(); - tii = mf->getTarget().getInstrInfo(); - } - - /// Ensures there is space before the given machine instruction, returns the - /// instruction's new number. - LiveIndex makeSpaceBefore(MachineInstr *mi) { - if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) { - lis->scaleNumbering(2); - ls->scaleNumbering(2); - } - - LiveIndex miIdx = lis->getInstructionIndex(mi); - - assert(lis->hasGapBeforeInstr(miIdx)); - - return miIdx; - } - - /// Ensure there is space after the given machine instruction, returns the - /// instruction's new number. - LiveIndex makeSpaceAfter(MachineInstr *mi) { - if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) { - lis->scaleNumbering(2); - ls->scaleNumbering(2); - } - - LiveIndex miIdx = lis->getInstructionIndex(mi); - - assert(lis->hasGapAfterInstr(miIdx)); - - return miIdx; - } - - /// Insert a store of the given vreg to the given stack slot immediately - /// after the given instruction. Returns the base index of the inserted - /// instruction. The caller is responsible for adding an appropriate - /// LiveInterval to the LiveIntervals analysis. - LiveIndex insertStoreAfter(MachineInstr *mi, unsigned ss, - unsigned vreg, - const TargetRegisterClass *trc) { - - MachineBasicBlock::iterator nextInstItr(next(mi)); - - LiveIndex miIdx = makeSpaceAfter(mi); - - tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, vreg, - true, ss, trc); - MachineBasicBlock::iterator storeInstItr(next(mi)); - MachineInstr *storeInst = &*storeInstItr; - LiveIndex storeInstIdx = lis->getNextIndex(miIdx); - - assert(lis->getInstructionFromIndex(storeInstIdx) == 0 && - "Store inst index already in use."); - - lis->InsertMachineInstrInMaps(storeInst, storeInstIdx); - - return storeInstIdx; - } - - /// Insert a store of the given vreg to the given stack slot immediately - /// before the given instructnion. Returns the base index of the inserted - /// Instruction. - LiveIndex insertStoreBefore(MachineInstr *mi, unsigned ss, - unsigned vreg, - const TargetRegisterClass *trc) { - LiveIndex miIdx = makeSpaceBefore(mi); - - tii->storeRegToStackSlot(*mi->getParent(), mi, vreg, true, ss, trc); - MachineBasicBlock::iterator storeInstItr(prior(mi)); - MachineInstr *storeInst = &*storeInstItr; - LiveIndex storeInstIdx = lis->getPrevIndex(miIdx); - - assert(lis->getInstructionFromIndex(storeInstIdx) == 0 && - "Store inst index already in use."); - - lis->InsertMachineInstrInMaps(storeInst, storeInstIdx); - - return storeInstIdx; - } - - void insertStoreAfterInstOnInterval(LiveInterval *li, - MachineInstr *mi, unsigned ss, - unsigned vreg, - const TargetRegisterClass *trc) { - - LiveIndex storeInstIdx = insertStoreAfter(mi, ss, vreg, trc); - LiveIndex start = lis->getDefIndex(lis->getInstructionIndex(mi)), - end = lis->getUseIndex(storeInstIdx); - - VNInfo *vni = - li->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator()); - vni->addKill(storeInstIdx); - DEBUG(errs() << " Inserting store range: [" << start - << ", " << end << ")\n"); - LiveRange lr(start, end, vni); - - li->addRange(lr); - } - - /// Insert a load of the given vreg from the given stack slot immediately - /// after the given instruction. Returns the base index of the inserted - /// instruction. The caller is responsibel for adding/removing an appropriate - /// range vreg's LiveInterval. - LiveIndex insertLoadAfter(MachineInstr *mi, unsigned ss, - unsigned vreg, - const TargetRegisterClass *trc) { - - MachineBasicBlock::iterator nextInstItr(next(mi)); - - LiveIndex miIdx = makeSpaceAfter(mi); - - tii->loadRegFromStackSlot(*mi->getParent(), nextInstItr, vreg, ss, trc); - MachineBasicBlock::iterator loadInstItr(next(mi)); - MachineInstr *loadInst = &*loadInstItr; - LiveIndex loadInstIdx = lis->getNextIndex(miIdx); - - assert(lis->getInstructionFromIndex(loadInstIdx) == 0 && - "Store inst index already in use."); - - lis->InsertMachineInstrInMaps(loadInst, loadInstIdx); - - return loadInstIdx; - } - - /// Insert a load of the given vreg from the given stack slot immediately - /// before the given instruction. Returns the base index of the inserted - /// instruction. The caller is responsible for adding an appropriate - /// LiveInterval to the LiveIntervals analysis. - LiveIndex insertLoadBefore(MachineInstr *mi, unsigned ss, - unsigned vreg, - const TargetRegisterClass *trc) { - LiveIndex miIdx = makeSpaceBefore(mi); - - tii->loadRegFromStackSlot(*mi->getParent(), mi, vreg, ss, trc); - MachineBasicBlock::iterator loadInstItr(prior(mi)); - MachineInstr *loadInst = &*loadInstItr; - LiveIndex loadInstIdx = lis->getPrevIndex(miIdx); - - assert(lis->getInstructionFromIndex(loadInstIdx) == 0 && - "Load inst index already in use."); - - lis->InsertMachineInstrInMaps(loadInst, loadInstIdx); - - return loadInstIdx; - } - - void insertLoadBeforeInstOnInterval(LiveInterval *li, - MachineInstr *mi, unsigned ss, - unsigned vreg, - const TargetRegisterClass *trc) { - - LiveIndex loadInstIdx = insertLoadBefore(mi, ss, vreg, trc); - LiveIndex start = lis->getDefIndex(loadInstIdx), - end = lis->getUseIndex(lis->getInstructionIndex(mi)); + const TargetRegisterInfo *tri; - VNInfo *vni = - li->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator()); - vni->addKill(lis->getInstructionIndex(mi)); - DEBUG(errs() << " Intserting load range: [" << start - << ", " << end << ")\n"); - LiveRange lr(start, end, vni); - - li->addRange(lr); + /// Construct a spiller base. + SpillerBase(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm) + : pass(&pass), mf(&mf), vrm(&vrm) + { + lis = &pass.getAnalysis(); + mfi = mf.getFrameInfo(); + mri = &mf.getRegInfo(); + tii = mf.getTarget().getInstrInfo(); + tri = mf.getTarget().getRegisterInfo(); } - - /// Add spill ranges for every use/def of the live interval, inserting loads - /// immediately before each use, and stores after each def. No folding is - /// attempted. - std::vector trivialSpillEverywhere(LiveInterval *li) { - DEBUG(errs() << "Spilling everywhere " << *li << "\n"); + /// immediately before each use, and stores after each def. No folding or + /// remat is attempted. + void trivialSpillEverywhere(LiveInterval *li, + SmallVectorImpl &newIntervals) { + DEBUG(dbgs() << "Spilling everywhere " << *li << "\n"); assert(li->weight != HUGE_VALF && "Attempting to spill already spilled value."); - assert(!li->isStackSlot() && + assert(!TargetRegisterInfo::isStackSlot(li->reg) && "Trying to spill a stack slot."); - DEBUG(errs() << "Trivial spill everywhere of reg" << li->reg << "\n"); + DEBUG(dbgs() << "Trivial spill everywhere of reg" << li->reg << "\n"); - std::vector added; - const TargetRegisterClass *trc = mri->getRegClass(li->reg); unsigned ss = vrm->assignVirt2StackSlot(li->reg); + // Iterate over reg uses/defs. for (MachineRegisterInfo::reg_iterator regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) { + // Grab the use/def instr. MachineInstr *mi = &*regItr; - DEBUG(errs() << " Processing " << *mi); + DEBUG(dbgs() << " Processing " << *mi); + // Step regItr to the next use/def instr. do { ++regItr; } while (regItr != mri->reg_end() && (&*regItr == mi)); - + + // Collect uses & defs for this instr. SmallVector indices; bool hasUse = false; bool hasDef = false; - for (unsigned i = 0; i != mi->getNumOperands(); ++i) { MachineOperand &op = mi->getOperand(i); - if (!op.isReg() || op.getReg() != li->reg) continue; - hasUse |= mi->getOperand(i).isUse(); hasDef |= mi->getOperand(i).isDef(); - indices.push_back(i); } + // Create a new vreg & interval for this instr. unsigned newVReg = mri->createVirtualRegister(trc); vrm->grow(); vrm->assignVirt2StackSlot(newVReg, ss); - LiveInterval *newLI = &lis->getOrCreateInterval(newVReg); newLI->weight = HUGE_VALF; - - for (unsigned i = 0; i < indices.size(); ++i) { - mi->getOperand(indices[i]).setReg(newVReg); - if (mi->getOperand(indices[i]).isUse()) { - mi->getOperand(indices[i]).setIsKill(true); + // Update the reg operands & kill flags. + for (unsigned i = 0; i < indices.size(); ++i) { + unsigned mopIdx = indices[i]; + MachineOperand &mop = mi->getOperand(mopIdx); + mop.setReg(newVReg); + if (mop.isUse() && !mi->isRegTiedToDefOperand(mopIdx)) { + mop.setIsKill(true); } } - assert(hasUse || hasDef); + // Insert reload if necessary. + MachineBasicBlock::iterator miItr(mi); if (hasUse) { - insertLoadBeforeInstOnInterval(newLI, mi, ss, newVReg, trc); + tii->loadRegFromStackSlot(*mi->getParent(), miItr, newVReg, ss, trc, + tri); + MachineInstr *loadInstr(prior(miItr)); + SlotIndex loadIndex = + lis->InsertMachineInstrInMaps(loadInstr).getDefIndex(); + vrm->addSpillSlotUse(ss, loadInstr); + SlotIndex endIndex = loadIndex.getNextIndex(); + VNInfo *loadVNI = + newLI->getNextValue(loadIndex, 0, lis->getVNInfoAllocator()); + newLI->addRange(LiveRange(loadIndex, endIndex, loadVNI)); } + // Insert store if necessary. if (hasDef) { - insertStoreAfterInstOnInterval(newLI, mi, ss, newVReg, trc); + tii->storeRegToStackSlot(*mi->getParent(), llvm::next(miItr), newVReg, + true, ss, trc, tri); + MachineInstr *storeInstr(llvm::next(miItr)); + SlotIndex storeIndex = + lis->InsertMachineInstrInMaps(storeInstr).getDefIndex(); + vrm->addSpillSlotUse(ss, storeInstr); + SlotIndex beginIndex = storeIndex.getPrevIndex(); + VNInfo *storeVNI = + newLI->getNextValue(beginIndex, 0, lis->getVNInfoAllocator()); + newLI->addRange(LiveRange(beginIndex, storeIndex, storeVNI)); } - added.push_back(newLI); + newIntervals.push_back(newLI); } - - return added; } - }; +} // end anonymous namespace + +namespace { /// Spills any live range using the spill-everywhere method with no attempt at /// folding. class TrivialSpiller : public SpillerBase { public: - TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, - VirtRegMap *vrm) : - SpillerBase(mf, lis, ls, vrm) {} + TrivialSpiller(MachineFunctionPass &pass, MachineFunction &mf, + VirtRegMap &vrm) + : SpillerBase(pass, mf, vrm) {} - std::vector spill(LiveInterval *li) { - return trivialSpillEverywhere(li); + void spill(LiveRangeEdit &LRE) { + // Ignore spillIs - we don't use it. + trivialSpillEverywhere(&LRE.getParent(), *LRE.getNewVRegs()); } +}; - std::vector intraBlockSplit(LiveInterval *li, VNInfo *valno) { - std::vector spillIntervals; - - if (!valno->isDefAccurate() && !valno->isPHIDef()) { - // Early out for values which have no well defined def point. - return spillIntervals; - } - - // Ok.. we should be able to proceed... - const TargetRegisterClass *trc = mri->getRegClass(li->reg); - unsigned ss = vrm->assignVirt2StackSlot(li->reg); - vrm->grow(); - vrm->assignVirt2StackSlot(li->reg, ss); - - MachineInstr *mi = 0; - LiveIndex storeIdx = MachineInstrIndex(); - - if (valno->isDefAccurate()) { - // If we have an accurate def we can just grab an iterator to the instr - // after the def. - mi = lis->getInstructionFromIndex(valno->def); - storeIdx = lis->getDefIndex(insertStoreAfter(mi, ss, li->reg, trc)); - } else { - // if we get here we have a PHI def. - mi = &lis->getMBBFromIndex(valno->def)->front(); - storeIdx = lis->getDefIndex(insertStoreBefore(mi, ss, li->reg, trc)); - } - - MachineBasicBlock *defBlock = mi->getParent(); - LiveIndex loadIdx = MachineInstrIndex(); - - // Now we need to find the load... - MachineBasicBlock::iterator useItr(mi); - for (; !useItr->readsRegister(li->reg); ++useItr) {} - - if (useItr != defBlock->end()) { - MachineInstr *loadInst = useItr; - loadIdx = lis->getUseIndex(insertLoadBefore(loadInst, ss, li->reg, trc)); - } - else { - MachineInstr *loadInst = &defBlock->back(); - loadIdx = lis->getUseIndex(insertLoadAfter(loadInst, ss, li->reg, trc)); - } +} // end anonymous namespace - li->removeRange(storeIdx, loadIdx, true); +namespace { - return spillIntervals; +/// Falls back on LiveIntervals::addIntervalsForSpills. +class StandardSpiller : public Spiller { +protected: + MachineFunction *mf; + LiveIntervals *lis; + LiveStacks *lss; + MachineLoopInfo *loopInfo; + VirtRegMap *vrm; +public: + StandardSpiller(MachineFunctionPass &pass, MachineFunction &mf, + VirtRegMap &vrm) + : mf(&mf), + lis(&pass.getAnalysis()), + lss(&pass.getAnalysis()), + loopInfo(pass.getAnalysisIfAvailable()), + vrm(&vrm) {} + + /// Falls back on LiveIntervals::addIntervalsForSpills. + void spill(LiveRangeEdit &LRE) { + std::vector added = + lis->addIntervalsForSpills(LRE.getParent(), LRE.getUselessVRegs(), + loopInfo, *vrm); + LRE.getNewVRegs()->insert(LRE.getNewVRegs()->end(), + added.begin(), added.end()); + + // Update LiveStacks. + int SS = vrm->getStackSlot(LRE.getReg()); + if (SS == VirtRegMap::NO_STACK_SLOT) + return; + const TargetRegisterClass *RC = mf->getRegInfo().getRegClass(LRE.getReg()); + LiveInterval &SI = lss->getOrCreateInterval(SS, RC); + if (!SI.hasAtLeastOneValue()) + SI.getNextValue(SlotIndex(), 0, lss->getVNInfoAllocator()); + SI.MergeRangesInAsValue(LRE.getParent(), SI.getValNumInfo(0)); } - }; -} +} // end anonymous namespace -llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis, - LiveStacks *ls, VirtRegMap *vrm) { - return new TrivialSpiller(mf, lis, ls, vrm); +llvm::Spiller* llvm::createSpiller(MachineFunctionPass &pass, + MachineFunction &mf, + VirtRegMap &vrm) { + switch (spillerOpt) { + default: assert(0 && "unknown spiller"); + case trivial: return new TrivialSpiller(pass, mf, vrm); + case standard: return new StandardSpiller(pass, mf, vrm); + case inline_: return createInlineSpiller(pass, mf, vrm); + } }