X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSpiller.cpp;h=4326a8983d373b07253fcd9d2f46729e10afa0a7;hb=8f909345bcabd0cbcb99d01d23f1d77b8b1518ec;hp=ce63121251e3248bb62fcbb440acbe1f4fc6110e;hpb=f41538d1b54f55e8900394929b50f7ce3e61125f;p=oota-llvm.git diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp index ce63121251e..4326a8983d3 100644 --- a/lib/CodeGen/Spiller.cpp +++ b/lib/CodeGen/Spiller.cpp @@ -13,12 +13,13 @@ #include "VirtRegMap.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; @@ -39,7 +40,8 @@ protected: VirtRegMap *vrm; /// Construct a spiller base. - SpillerBase(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, VirtRegMap *vrm) : + SpillerBase(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, + VirtRegMap *vrm) : mf(mf), lis(lis), ls(ls), vrm(vrm) { mfi = mf->getFrameInfo(); @@ -47,31 +49,53 @@ protected: tii = mf->getTarget().getInstrInfo(); } - /// 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. - unsigned insertStoreFor(MachineInstr *mi, unsigned ss, - unsigned newVReg, - const TargetRegisterClass *trc) { - MachineBasicBlock::iterator nextInstItr(mi); - ++nextInstItr; + /// Ensures there is space before the given machine instruction, returns the + /// instruction's new number. + MachineInstrIndex makeSpaceBefore(MachineInstr *mi) { + if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) { + lis->scaleNumbering(2); + ls->scaleNumbering(2); + } + + MachineInstrIndex 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. + MachineInstrIndex makeSpaceAfter(MachineInstr *mi) { if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) { lis->scaleNumbering(2); ls->scaleNumbering(2); } - unsigned miIdx = lis->getInstructionIndex(mi); + MachineInstrIndex miIdx = lis->getInstructionIndex(mi); assert(lis->hasGapAfterInstr(miIdx)); - tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, newVReg, + 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. + MachineInstrIndex insertStoreAfter(MachineInstr *mi, unsigned ss, + unsigned vreg, + const TargetRegisterClass *trc) { + + MachineBasicBlock::iterator nextInstItr(next(mi)); + + MachineInstrIndex miIdx = makeSpaceAfter(mi); + + tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, vreg, true, ss, trc); - MachineBasicBlock::iterator storeInstItr(mi); - ++storeInstItr; + MachineBasicBlock::iterator storeInstItr(next(mi)); MachineInstr *storeInst = &*storeInstItr; - unsigned storeInstIdx = miIdx + LiveInterval::InstrSlots::NUM; + MachineInstrIndex storeInstIdx = lis->getNextIndex(miIdx); assert(lis->getInstructionFromIndex(storeInstIdx) == 0 && "Store inst index already in use."); @@ -81,29 +105,84 @@ protected: return storeInstIdx; } - /// Insert a load of the given veg 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. - unsigned insertLoadFor(MachineInstr *mi, unsigned ss, - unsigned newVReg, - const TargetRegisterClass *trc) { - MachineBasicBlock::iterator useInstItr(mi); + /// 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. + MachineInstrIndex insertStoreBefore(MachineInstr *mi, unsigned ss, + unsigned vreg, + const TargetRegisterClass *trc) { + MachineInstrIndex miIdx = makeSpaceBefore(mi); + + tii->storeRegToStackSlot(*mi->getParent(), mi, vreg, true, ss, trc); + MachineBasicBlock::iterator storeInstItr(prior(mi)); + MachineInstr *storeInst = &*storeInstItr; + MachineInstrIndex storeInstIdx = lis->getPrevIndex(miIdx); - if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) { - lis->scaleNumbering(2); - ls->scaleNumbering(2); - } + assert(lis->getInstructionFromIndex(storeInstIdx) == 0 && + "Store inst index already in use."); - unsigned miIdx = lis->getInstructionIndex(mi); + lis->InsertMachineInstrInMaps(storeInst, storeInstIdx); - assert(lis->hasGapBeforeInstr(miIdx)); + return storeInstIdx; + } + + void insertStoreAfterInstOnInterval(LiveInterval *li, + MachineInstr *mi, unsigned ss, + unsigned vreg, + const TargetRegisterClass *trc) { + + MachineInstrIndex storeInstIdx = insertStoreAfter(mi, ss, vreg, trc); + MachineInstrIndex 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. + MachineInstrIndex insertLoadAfter(MachineInstr *mi, unsigned ss, + unsigned vreg, + const TargetRegisterClass *trc) { + + MachineBasicBlock::iterator nextInstItr(next(mi)); + + MachineInstrIndex miIdx = makeSpaceAfter(mi); + + tii->loadRegFromStackSlot(*mi->getParent(), nextInstItr, vreg, ss, trc); + MachineBasicBlock::iterator loadInstItr(next(mi)); + MachineInstr *loadInst = &*loadInstItr; + MachineInstrIndex loadInstIdx = lis->getNextIndex(miIdx); + + assert(lis->getInstructionFromIndex(loadInstIdx) == 0 && + "Store inst index already in use."); - tii->loadRegFromStackSlot(*mi->getParent(), useInstItr, newVReg, ss, trc); - MachineBasicBlock::iterator loadInstItr(mi); - --loadInstItr; + 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. + MachineInstrIndex insertLoadBefore(MachineInstr *mi, unsigned ss, + unsigned vreg, + const TargetRegisterClass *trc) { + MachineInstrIndex miIdx = makeSpaceBefore(mi); + + tii->loadRegFromStackSlot(*mi->getParent(), mi, vreg, ss, trc); + MachineBasicBlock::iterator loadInstItr(prior(mi)); MachineInstr *loadInst = &*loadInstItr; - unsigned loadInstIdx = miIdx - LiveInterval::InstrSlots::NUM; + MachineInstrIndex loadInstIdx = lis->getPrevIndex(miIdx); assert(lis->getInstructionFromIndex(loadInstIdx) == 0 && "Load inst index already in use."); @@ -113,12 +192,32 @@ protected: return loadInstIdx; } + void insertLoadBeforeInstOnInterval(LiveInterval *li, + MachineInstr *mi, unsigned ss, + unsigned vreg, + const TargetRegisterClass *trc) { + + MachineInstrIndex loadInstIdx = insertLoadBefore(mi, ss, vreg, trc); + MachineInstrIndex start = lis->getDefIndex(loadInstIdx), + end = lis->getUseIndex(lis->getInstructionIndex(mi)); + + 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); + } + + /// 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) { - DOUT << "Spilling everywhere " << *li << "\n"; + DEBUG(errs() << "Spilling everywhere " << *li << "\n"); assert(li->weight != HUGE_VALF && "Attempting to spill already spilled value."); @@ -126,6 +225,8 @@ protected: assert(!li->isStackSlot() && "Trying to spill a stack slot."); + DEBUG(errs() << "Trivial spill everywhere of reg" << li->reg << "\n"); + std::vector added; const TargetRegisterClass *trc = mri->getRegClass(li->reg); @@ -135,6 +236,9 @@ protected: regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) { MachineInstr *mi = &*regItr; + + DEBUG(errs() << " Processing " << *mi); + do { ++regItr; } while (regItr != mri->reg_end() && (&*regItr == mi)); @@ -173,35 +277,16 @@ protected: assert(hasUse || hasDef); if (hasUse) { - unsigned loadInstIdx = insertLoadFor(mi, ss, newVReg, trc); - unsigned start = lis->getDefIndex(loadInstIdx), - end = lis->getUseIndex(lis->getInstructionIndex(mi)); - - VNInfo *vni = - newLI->getNextValue(loadInstIdx, 0, lis->getVNInfoAllocator()); - vni->kills.push_back(lis->getInstructionIndex(mi)); - LiveRange lr(start, end, vni); - - newLI->addRange(lr); + insertLoadBeforeInstOnInterval(newLI, mi, ss, newVReg, trc); } if (hasDef) { - unsigned storeInstIdx = insertStoreFor(mi, ss, newVReg, trc); - unsigned start = lis->getDefIndex(lis->getInstructionIndex(mi)), - end = lis->getUseIndex(storeInstIdx); - - VNInfo *vni = - newLI->getNextValue(storeInstIdx, 0, lis->getVNInfoAllocator()); - vni->kills.push_back(storeInstIdx); - LiveRange lr(start, end, vni); - - newLI->addRange(lr); + insertStoreAfterInstOnInterval(newLI, mi, ss, newVReg, trc); } added.push_back(newLI); } - return added; } @@ -212,13 +297,64 @@ protected: /// folding. class TrivialSpiller : public SpillerBase { public: - TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, VirtRegMap *vrm) : + + TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, + VirtRegMap *vrm) : SpillerBase(mf, lis, ls, vrm) {} std::vector spill(LiveInterval *li) { return trivialSpillEverywhere(li); } + 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; + MachineInstrIndex 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(); + MachineInstrIndex 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)); + } + + li->removeRange(storeIdx, loadIdx, true); + + return spillIntervals; + } + }; }