From 6194569d22003fddaf1a33acdbb84d5efe76e7d7 Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Wed, 9 Dec 2009 05:39:12 +0000 Subject: [PATCH] Added a new "splitting" spiller. When a call is placed to spill an interval this spiller will first try to break the interval up into its component values. Single value intervals and intervals which have already been split (or are the result of previous splits) are spilled by the default spiller. Splitting intervals as described above may improve the performance of generated code in some circumstances. This work is experimental however, and it still miscompiles many benchmarks. It's not recommended for general use yet. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@90951 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveIntervalAnalysis.h | 4 + lib/CodeGen/LiveInterval.cpp | 2 +- lib/CodeGen/LiveIntervalAnalysis.cpp | 4 +- lib/CodeGen/RegAllocLinearScan.cpp | 15 +- lib/CodeGen/Spiller.cpp | 336 +++++++++++++++++++- lib/CodeGen/Spiller.h | 4 +- 6 files changed, 343 insertions(+), 22 deletions(-) diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 7a02d0fe991..a06e310c294 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -186,6 +186,10 @@ namespace llvm { return indexes_->getMBBFromIndex(index); } + SlotIndex getMBBTerminatorGap(const MachineBasicBlock *mbb) { + return indexes_->getTerminatorGap(mbb); + } + SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { return indexes_->insertMachineInstrInMaps(MI); } diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 8d632cb5ca1..cc286aa13d6 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -847,7 +847,7 @@ void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { if (vni->isUnused()) { OS << "x"; } else { - if (!vni->isDefAccurate()) + if (!vni->isDefAccurate() && !vni->isPHIDef()) OS << "?"; else OS << vni->def; diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 35337efd504..c16ddc57caf 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -401,7 +401,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, interval.removeRange(Start, End); assert(interval.ranges.size() == 1 && "Newly discovered PHI interval has >1 ranges."); - MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex()); + MachineBasicBlock *killMBB = getMBBFromIndex(VNI->def); VNI->addKill(indexes_->getTerminatorGap(killMBB)); VNI->setHasPHIKill(true); DEBUG({ @@ -412,7 +412,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // Replace the interval with one of a NEW value number. Note that this // value number isn't actually defined by an instruction, weird huh? :) LiveRange LR(Start, End, - interval.getNextValue(SlotIndex(getMBBStartIdx(mbb), true), + interval.getNextValue(SlotIndex(getMBBStartIdx(Killer->getParent()), true), 0, false, VNInfoAllocator)); LR.valno->setIsPHIDef(true); DEBUG(errs() << " replace range with " << LR); diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 4ff512932f8..c1f587567e8 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -1261,9 +1261,9 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) { // The earliest start of a Spilled interval indicates up to where // in handled we need to roll back + assert(!spillIs.empty() && "No spill intervals?"); + SlotIndex earliestStart = spillIs[0]->beginIndex(); - LiveInterval *earliestStartInterval = cur; - // Spill live intervals of virtual regs mapped to the physical register we // want to clear (and its aliases). We only spill those that overlap with the // current interval as the rest do not affect its allocation. we also keep @@ -1274,19 +1274,16 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) { LiveInterval *sli = spillIs.back(); spillIs.pop_back(); DEBUG(errs() << "\t\t\tspilling(a): " << *sli << '\n'); - earliestStartInterval = - (earliestStartInterval->beginIndex() < sli->beginIndex()) ? - earliestStartInterval : sli; + if (sli->beginIndex() < earliestStart) + earliestStart = sli->beginIndex(); std::vector newIs; - newIs = spiller_->spill(sli, spillIs); + newIs = spiller_->spill(sli, spillIs, &earliestStart); addStackInterval(sli, ls_, li_, mri_, *vrm_); std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); spilled.insert(sli->reg); } - SlotIndex earliestStart = earliestStartInterval->beginIndex(); - DEBUG(errs() << "\t\trolling back to: " << earliestStart << '\n'); // Scan handled in reverse order up to the earliest start of a @@ -1295,7 +1292,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) { while (!handled_.empty()) { LiveInterval* i = handled_.back(); // If this interval starts before t we are done. - if (i->beginIndex() < earliestStart) + if (!i->empty() && i->beginIndex() < earliestStart) break; DEBUG(errs() << "\t\t\tundo changes for: " << *i << '\n'); handled_.pop_back(); diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp index 74662155654..bc246c14b77 100644 --- a/lib/CodeGen/Spiller.cpp +++ b/lib/CodeGen/Spiller.cpp @@ -20,22 +20,25 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include using namespace llvm; namespace { - enum SpillerName { trivial, standard }; + enum SpillerName { trivial, standard, splitting }; } static cl::opt spillerOpt("spiller", cl::desc("Spiller to use: (default: standard)"), cl::Prefix, - cl::values(clEnumVal(trivial, "trivial spiller"), - clEnumVal(standard, "default spiller"), + cl::values(clEnumVal(trivial, "trivial spiller"), + clEnumVal(standard, "default spiller"), + clEnumVal(splitting, "splitting spiller"), clEnumValEnd), cl::init(standard)); +// Spiller virtual destructor implementation. Spiller::~Spiller() {} namespace { @@ -170,7 +173,8 @@ public: : SpillerBase(mf, lis, vrm) {} std::vector spill(LiveInterval *li, - SmallVectorImpl &spillIs) { + SmallVectorImpl &spillIs, + SlotIndex*) { // Ignore spillIs - we don't use it. return trivialSpillEverywhere(li); } @@ -179,23 +183,336 @@ public: /// Falls back on LiveIntervals::addIntervalsForSpills. class StandardSpiller : public Spiller { -private: +protected: LiveIntervals *lis; const MachineLoopInfo *loopInfo; VirtRegMap *vrm; public: - StandardSpiller(MachineFunction *mf, LiveIntervals *lis, - const MachineLoopInfo *loopInfo, VirtRegMap *vrm) + StandardSpiller(LiveIntervals *lis, const MachineLoopInfo *loopInfo, + VirtRegMap *vrm) : lis(lis), loopInfo(loopInfo), vrm(vrm) {} /// Falls back on LiveIntervals::addIntervalsForSpills. std::vector spill(LiveInterval *li, - SmallVectorImpl &spillIs) { + SmallVectorImpl &spillIs, + SlotIndex*) { return lis->addIntervalsForSpills(*li, spillIs, loopInfo, *vrm); } }; +/// When a call to spill is placed this spiller will first try to break the +/// interval up into its component values (one new interval per value). +/// If this fails, or if a call is placed to spill a previously split interval +/// then the spiller falls back on the standard spilling mechanism. +class SplittingSpiller : public StandardSpiller { +public: + SplittingSpiller(MachineFunction *mf, LiveIntervals *lis, + const MachineLoopInfo *loopInfo, VirtRegMap *vrm) + : StandardSpiller(lis, loopInfo, vrm) { + + mri = &mf->getRegInfo(); + tii = mf->getTarget().getInstrInfo(); + tri = mf->getTarget().getRegisterInfo(); + } + + std::vector spill(LiveInterval *li, + SmallVectorImpl &spillIs, + SlotIndex *earliestStart) { + + if (worthTryingToSplit(li)) { + return tryVNISplit(li, earliestStart); + } + // else + return StandardSpiller::spill(li, spillIs, earliestStart); + } + +private: + + MachineRegisterInfo *mri; + const TargetInstrInfo *tii; + const TargetRegisterInfo *tri; + DenseSet alreadySplit; + + bool worthTryingToSplit(LiveInterval *li) const { + return (!alreadySplit.count(li) && li->getNumValNums() > 1); + } + + /// Try to break a LiveInterval into its component values. + std::vector tryVNISplit(LiveInterval *li, + SlotIndex *earliestStart) { + + DEBUG(errs() << "Trying VNI split of %reg" << *li << "\n"); + + std::vector added; + SmallVector vnis; + + std::copy(li->vni_begin(), li->vni_end(), std::back_inserter(vnis)); + + for (SmallVectorImpl::iterator vniItr = vnis.begin(), + vniEnd = vnis.end(); vniItr != vniEnd; ++vniItr) { + VNInfo *vni = *vniItr; + + // Skip unused VNIs, or VNIs with no kills. + if (vni->isUnused() || vni->kills.empty()) + continue; + + DEBUG(errs() << " Extracted Val #" << vni->id << " as "); + LiveInterval *splitInterval = extractVNI(li, vni); + + if (splitInterval != 0) { + DEBUG(errs() << *splitInterval << "\n"); + added.push_back(splitInterval); + alreadySplit.insert(splitInterval); + if (earliestStart != 0) { + if (splitInterval->beginIndex() < *earliestStart) + *earliestStart = splitInterval->beginIndex(); + } + } else { + DEBUG(errs() << "0\n"); + } + } + + DEBUG(errs() << "Original LI: " << *li << "\n"); + + // If there original interval still contains some live ranges + // add it to added and alreadySplit. + if (!li->empty()) { + added.push_back(li); + alreadySplit.insert(li); + if (earliestStart != 0) { + if (li->beginIndex() < *earliestStart) + *earliestStart = li->beginIndex(); + } + } + + return added; + } + + /// Extract the given value number from the interval. + LiveInterval* extractVNI(LiveInterval *li, VNInfo *vni) const { + assert(vni->isDefAccurate() || vni->isPHIDef()); + assert(!vni->kills.empty()); + + // Create a new vreg and live interval, copy VNI kills & ranges over. + const TargetRegisterClass *trc = mri->getRegClass(li->reg); + unsigned newVReg = mri->createVirtualRegister(trc); + vrm->grow(); + LiveInterval *newLI = &lis->getOrCreateInterval(newVReg); + VNInfo *newVNI = newLI->createValueCopy(vni, lis->getVNInfoAllocator()); + + // Start by copying all live ranges in the VN to the new interval. + for (LiveInterval::iterator rItr = li->begin(), rEnd = li->end(); + rItr != rEnd; ++rItr) { + if (rItr->valno == vni) { + newLI->addRange(LiveRange(rItr->start, rItr->end, newVNI)); + } + } + + // Erase the old VNI & ranges. + li->removeValNo(vni); + + // Collect all current uses of the register belonging to the given VNI. + // We'll use this to rename the register after we've dealt with the def. + std::set uses; + for (MachineRegisterInfo::use_iterator + useItr = mri->use_begin(li->reg), useEnd = mri->use_end(); + useItr != useEnd; ++useItr) { + uses.insert(&*useItr); + } + + // Process the def instruction for this VNI. + if (newVNI->isPHIDef()) { + // Insert a copy at the start of the MBB. The range proceeding the + // copy will be attached to the original LiveInterval. + MachineBasicBlock *defMBB = lis->getMBBFromIndex(newVNI->def); + tii->copyRegToReg(*defMBB, defMBB->begin(), newVReg, li->reg, trc, trc); + MachineInstr *copyMI = defMBB->begin(); + copyMI->addRegisterKilled(li->reg, tri); + SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI); + VNInfo *phiDefVNI = li->getNextValue(lis->getMBBStartIdx(defMBB), + 0, false, lis->getVNInfoAllocator()); + phiDefVNI->setIsPHIDef(true); + phiDefVNI->addKill(copyIdx.getDefIndex()); + li->addRange(LiveRange(phiDefVNI->def, copyIdx.getDefIndex(), phiDefVNI)); + LiveRange *oldPHIDefRange = + newLI->getLiveRangeContaining(lis->getMBBStartIdx(defMBB)); + + // If the old phi def starts in the middle of the range chop it up. + if (oldPHIDefRange->start < lis->getMBBStartIdx(defMBB)) { + LiveRange oldPHIDefRange2(copyIdx.getDefIndex(), oldPHIDefRange->end, + oldPHIDefRange->valno); + oldPHIDefRange->end = lis->getMBBStartIdx(defMBB); + newLI->addRange(oldPHIDefRange2); + } else if (oldPHIDefRange->start == lis->getMBBStartIdx(defMBB)) { + // Otherwise if it's at the start of the range just trim it. + oldPHIDefRange->start = copyIdx.getDefIndex(); + } else { + assert(false && "PHI def range doesn't cover PHI def?"); + } + + newVNI->def = copyIdx.getDefIndex(); + newVNI->setCopy(copyMI); + newVNI->setIsPHIDef(false); // not a PHI def anymore. + newVNI->setIsDefAccurate(true); + } else { + // non-PHI def. Rename the def. If it's two-addr that means renaming the use + // and inserting a new copy too. + MachineInstr *defInst = lis->getInstructionFromIndex(newVNI->def); + // We'll rename this now, so we can remove it from uses. + uses.erase(defInst); + unsigned defOpIdx = defInst->findRegisterDefOperandIdx(li->reg); + bool isTwoAddr = defInst->isRegTiedToUseOperand(defOpIdx), + twoAddrUseIsUndef = false; + + for (unsigned i = 0; i < defInst->getNumOperands(); ++i) { + MachineOperand &mo = defInst->getOperand(i); + if (mo.isReg() && (mo.isDef() || isTwoAddr) && (mo.getReg()==li->reg)) { + mo.setReg(newVReg); + if (isTwoAddr && mo.isUse() && mo.isUndef()) + twoAddrUseIsUndef = true; + } + } + + SlotIndex defIdx = lis->getInstructionIndex(defInst); + newVNI->def = defIdx.getDefIndex(); + + if (isTwoAddr && !twoAddrUseIsUndef) { + MachineBasicBlock *defMBB = defInst->getParent(); + tii->copyRegToReg(*defMBB, defInst, newVReg, li->reg, trc, trc); + MachineInstr *copyMI = prior(MachineBasicBlock::iterator(defInst)); + SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI); + copyMI->addRegisterKilled(li->reg, tri); + LiveRange *origUseRange = + li->getLiveRangeContaining(newVNI->def.getUseIndex()); + VNInfo *origUseVNI = origUseRange->valno; + origUseRange->end = copyIdx.getDefIndex(); + bool updatedKills = false; + for (unsigned k = 0; k < origUseVNI->kills.size(); ++k) { + if (origUseVNI->kills[k] == defIdx.getDefIndex()) { + origUseVNI->kills[k] = copyIdx.getDefIndex(); + updatedKills = true; + break; + } + } + assert(updatedKills && "Failed to update VNI kill list."); + VNInfo *copyVNI = newLI->getNextValue(copyIdx.getDefIndex(), copyMI, + true, lis->getVNInfoAllocator()); + copyVNI->addKill(defIdx.getDefIndex()); + LiveRange copyRange(copyIdx.getDefIndex(),defIdx.getDefIndex(),copyVNI); + newLI->addRange(copyRange); + } + } + + for (std::set::iterator + usesItr = uses.begin(), usesEnd = uses.end(); + usesItr != usesEnd; ++usesItr) { + MachineInstr *useInst = *usesItr; + SlotIndex useIdx = lis->getInstructionIndex(useInst); + LiveRange *useRange = + newLI->getLiveRangeContaining(useIdx.getUseIndex()); + + // If this use doesn't belong to the new interval skip it. + if (useRange == 0) + continue; + + // This use doesn't belong to the VNI, skip it. + if (useRange->valno != newVNI) + continue; + + // Check if this instr is two address. + unsigned useOpIdx = useInst->findRegisterUseOperandIdx(li->reg); + bool isTwoAddress = useInst->isRegTiedToDefOperand(useOpIdx); + + // Rename uses (and defs for two-address instrs). + for (unsigned i = 0; i < useInst->getNumOperands(); ++i) { + MachineOperand &mo = useInst->getOperand(i); + if (mo.isReg() && (mo.isUse() || isTwoAddress) && + (mo.getReg() == li->reg)) { + mo.setReg(newVReg); + } + } + + // If this is a two address instruction we've got some extra work to do. + if (isTwoAddress) { + // We modified the def operand, so we need to copy back to the original + // reg. + MachineBasicBlock *useMBB = useInst->getParent(); + MachineBasicBlock::iterator useItr(useInst); + tii->copyRegToReg(*useMBB, next(useItr), li->reg, newVReg, trc, trc); + MachineInstr *copyMI = next(useItr); + copyMI->addRegisterKilled(newVReg, tri); + SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI); + + // Change the old two-address defined range & vni to start at + // (and be defined by) the copy. + LiveRange *origDefRange = + li->getLiveRangeContaining(useIdx.getDefIndex()); + origDefRange->start = copyIdx.getDefIndex(); + origDefRange->valno->def = copyIdx.getDefIndex(); + origDefRange->valno->setCopy(copyMI); + + // Insert a new range & vni for the two-address-to-copy value. This + // will be attached to the new live interval. + VNInfo *copyVNI = + newLI->getNextValue(useIdx.getDefIndex(), 0, true, + lis->getVNInfoAllocator()); + copyVNI->addKill(copyIdx.getDefIndex()); + LiveRange copyRange(useIdx.getDefIndex(),copyIdx.getDefIndex(),copyVNI); + newLI->addRange(copyRange); + } + } + + // Iterate over any PHI kills - we'll need to insert new copies for them. + for (VNInfo::KillSet::iterator + killItr = newVNI->kills.begin(), killEnd = newVNI->kills.end(); + killItr != killEnd; ++killItr) { + SlotIndex killIdx(*killItr); + if (killItr->isPHI()) { + MachineBasicBlock *killMBB = lis->getMBBFromIndex(killIdx); + LiveRange *oldKillRange = + newLI->getLiveRangeContaining(killIdx); + + assert(oldKillRange != 0 && "No kill range?"); + + tii->copyRegToReg(*killMBB, killMBB->getFirstTerminator(), + li->reg, newVReg, trc, trc); + MachineInstr *copyMI = prior(killMBB->getFirstTerminator()); + copyMI->addRegisterKilled(newVReg, tri); + SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI); + + // Save the current end. We may need it to add a new range if the + // current range runs of the end of the MBB. + SlotIndex newKillRangeEnd = oldKillRange->end; + oldKillRange->end = copyIdx.getDefIndex(); + + if (newKillRangeEnd != lis->getMBBEndIdx(killMBB).getNextSlot()) { + assert(newKillRangeEnd > lis->getMBBEndIdx(killMBB).getNextSlot() && + "PHI kill range doesn't reach kill-block end. Not sane."); + newLI->addRange(LiveRange(lis->getMBBEndIdx(killMBB).getNextSlot(), + newKillRangeEnd, newVNI)); + } + + *killItr = oldKillRange->end; + VNInfo *newKillVNI = li->getNextValue(copyIdx.getDefIndex(), + copyMI, true, + lis->getVNInfoAllocator()); + newKillVNI->addKill(lis->getMBBTerminatorGap(killMBB)); + newKillVNI->setHasPHIKill(true); + li->addRange(LiveRange(copyIdx.getDefIndex(), + lis->getMBBEndIdx(killMBB).getNextSlot(), + newKillVNI)); + } + + } + + newVNI->setHasPHIKill(false); + + return newLI; + } + +}; + } llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis, @@ -203,7 +520,8 @@ llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm) { switch (spillerOpt) { case trivial: return new TrivialSpiller(mf, lis, vrm); break; - case standard: return new StandardSpiller(mf, lis, loopInfo, vrm); break; + case standard: return new StandardSpiller(lis, loopInfo, vrm); break; + case splitting: return new SplittingSpiller(mf, lis, loopInfo, vrm); break; default: llvm_unreachable("Unreachable!"); break; } } diff --git a/lib/CodeGen/Spiller.h b/lib/CodeGen/Spiller.h index c6bd9857dba..dda52e871fe 100644 --- a/lib/CodeGen/Spiller.h +++ b/lib/CodeGen/Spiller.h @@ -21,6 +21,7 @@ namespace llvm { class MachineFunction; class MachineInstr; class MachineLoopInfo; + class SlotIndex; class VirtRegMap; class VNInfo; @@ -35,7 +36,8 @@ namespace llvm { /// Spill the given live range. The method used will depend on the Spiller /// implementation selected. virtual std::vector spill(LiveInterval *li, - SmallVectorImpl &spillIs) = 0; + SmallVectorImpl &spillIs, + SlotIndex *earliestIndex = 0) = 0; }; -- 2.34.1