From 5f37502bfbadfa65de087627bd67fd58bb03725c Mon Sep 17 00:00:00 2001 From: Alkis Evlogimenos Date: Mon, 1 Mar 2004 20:05:10 +0000 Subject: [PATCH] Add the long awaited memory operand folding support for linear scan git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12058 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveIntervalAnalysis.h | 3 +- lib/CodeGen/LiveIntervalAnalysis.cpp | 54 +++++++++++++-------- lib/CodeGen/LiveIntervalAnalysis.h | 3 +- lib/CodeGen/RegAllocLinearScan.cpp | 6 +-- lib/CodeGen/VirtRegMap.cpp | 39 ++++++++++++--- lib/CodeGen/VirtRegMap.h | 14 ++++++ 6 files changed, 89 insertions(+), 30 deletions(-) diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 24bc8956b3f..5b78342e281 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -28,6 +28,7 @@ namespace llvm { class LiveVariables; class MRegisterInfo; + class VirtRegMap; class LiveIntervals : public MachineFunctionPass { @@ -164,7 +165,7 @@ namespace llvm { Intervals& getIntervals() { return intervals_; } - void updateSpilledInterval(Interval& i, int slot); + void updateSpilledInterval(Interval& i, VirtRegMap& vrm, int slot); private: /// computeIntervals - compute live intervals diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index fc46de2be92..d6cc357fd54 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -31,6 +31,7 @@ #include "Support/Debug.h" #include "Support/Statistic.h" #include "Support/STLExtras.h" +#include "VirtRegMap.h" #include #include #include @@ -184,7 +185,9 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { return true; } -void LiveIntervals::updateSpilledInterval(Interval& li, int slot) +void LiveIntervals::updateSpilledInterval(Interval& li, + VirtRegMap& vrm, + int slot) { assert(li.weight != std::numeric_limits::infinity() && "attempt to spill already spilled interval!"); @@ -202,27 +205,40 @@ void LiveIntervals::updateSpilledInterval(Interval& li, int slot) while (!getInstructionFromIndex(index)) index += InstrSlots::NUM; MachineBasicBlock::iterator mi = getInstructionFromIndex(index); + for_operand: for (unsigned i = 0; i < mi->getNumOperands(); ++i) { MachineOperand& mop = mi->getOperand(i); if (mop.isRegister() && mop.getReg() == li.reg) { - // This is tricky. We need to add information in - // the interval about the spill code so we have to - // use our extra load/store slots. - // - // If we have a use we are going to have a load so - // we start the interval from the load slot - // onwards. Otherwise we start from the def slot. - unsigned start = (mop.isUse() ? - getLoadIndex(index) : - getDefIndex(index)); - // If we have a def we are going to have a store - // right after it so we end the interval after the - // use of the next instruction. Otherwise we end - // after the use of this instruction. - unsigned end = 1 + (mop.isDef() ? - getUseIndex(index+InstrSlots::NUM) : - getUseIndex(index)); - li.addRange(start, end); + MachineInstr* old = mi; + if (mri_->foldMemoryOperand(mi, i, slot)) { + lv_->instructionChanged(old, mi); + vrm.virtFolded(li.reg, old, mi); + mi2iMap_.erase(old); + i2miMap_[index/InstrSlots::NUM] = mi; + mi2iMap_[mi] = index; + ++numFolded; + goto for_operand; + } + else { + // This is tricky. We need to add information in + // the interval about the spill code so we have to + // use our extra load/store slots. + // + // If we have a use we are going to have a load so + // we start the interval from the load slot + // onwards. Otherwise we start from the def slot. + unsigned start = (mop.isUse() ? + getLoadIndex(index) : + getDefIndex(index)); + // If we have a def we are going to have a store + // right after it so we end the interval after the + // use of the next instruction. Otherwise we end + // after the use of this instruction. + unsigned end = 1 + (mop.isDef() ? + getUseIndex(index+InstrSlots::NUM) : + getUseIndex(index)); + li.addRange(start, end); + } } } } diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h index 24bc8956b3f..5b78342e281 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.h +++ b/lib/CodeGen/LiveIntervalAnalysis.h @@ -28,6 +28,7 @@ namespace llvm { class LiveVariables; class MRegisterInfo; + class VirtRegMap; class LiveIntervals : public MachineFunctionPass { @@ -164,7 +165,7 @@ namespace llvm { Intervals& getIntervals() { return intervals_; } - void updateSpilledInterval(Interval& i, int slot); + void updateSpilledInterval(Interval& i, VirtRegMap& vrm, int slot); private: /// computeIntervals - compute live intervals diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 9e396186827..d6c53cd0a72 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -385,7 +385,7 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) if (cur->weight <= minWeight) { DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';); int slot = vrm_->assignVirt2StackSlot(cur->reg); - li_->updateSpilledInterval(*cur, slot); + li_->updateSpilledInterval(*cur, *vrm_, slot); // if we didn't eliminate the interval find where to add it // back to unhandled. We need to scan since unhandled are @@ -424,7 +424,7 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n'); earliestStart = std::min(earliestStart, (*i)->start()); int slot = vrm_->assignVirt2StackSlot((*i)->reg); - li_->updateSpilledInterval(**i, slot); + li_->updateSpilledInterval(**i, *vrm_, slot); } } for (IntervalPtrs::iterator i = inactive_.begin(); @@ -436,7 +436,7 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n'); earliestStart = std::min(earliestStart, (*i)->start()); int slot = vrm_->assignVirt2StackSlot((*i)->reg); - li_->updateSpilledInterval(**i, slot); + li_->updateSpilledInterval(**i, *vrm_, slot); } } diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index e517cb371e6..1238a2cefbb 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -19,6 +19,7 @@ #include "VirtRegMap.h" #include "llvm/Function.h" #include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineInstr.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" #include "Support/Statistic.h" @@ -49,6 +50,24 @@ int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) return frameIndex; } +void VirtRegMap::virtFolded(unsigned virtReg, + MachineInstr* oldMI, + MachineInstr* newMI) +{ + // move previous memory references folded to new instruction + MI2VirtMap::iterator i, e; + std::vector regs; + for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) { + regs.push_back(i->second); + mi2vMap_.erase(i++); + } + for (unsigned i = 0, e = regs.size(); i != e; ++i) + mi2vMap_.insert(std::make_pair(newMI, i)); + + // add new memory reference + mi2vMap_.insert(std::make_pair(newMI, virtReg)); +} + std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm) { const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo(); @@ -129,9 +148,9 @@ namespace { vrm_.getStackSlot(virtReg), mri_.getRegClass(physReg)); ++numStores; - DEBUG(std::cerr << "\t\tadded: "; + DEBUG(std::cerr << "added: "; prior(nextLastRef)->print(std::cerr, tm_); - std::cerr << "\t\tafter: "; + std::cerr << "after: "; lastDef->print(std::cerr, tm_)); lastDef_[virtReg] = 0; } @@ -161,10 +180,8 @@ namespace { vrm_.getStackSlot(virtReg), mri_.getRegClass(physReg)); ++numLoads; - DEBUG(std::cerr << "\t\tadded: "; - prior(mii)->print(std::cerr,tm_); - std::cerr << "\t\tbefore: "; - mii->print(std::cerr, tm_)); + DEBUG(std::cerr << "added: "; + prior(mii)->print(std::cerr,tm_)); lastDef_[virtReg] = mii; } } @@ -186,6 +203,16 @@ namespace { void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) { for (MachineBasicBlock::iterator mii = mbb.begin(), mie = mbb.end(); mii != mie; ++mii) { + + // if we have references to memory operands make sure + // we clear all physical registers that may contain + // the value of the spilled virtual register + VirtRegMap::MI2VirtMap::const_iterator i, e; + for (tie(i, e) = vrm_.getFoldedVirts(mii); i != e; ++i) { + unsigned physReg = vrm_.getPhys(i->second); + if (physReg) vacateJustPhysReg(mbb, mii, physReg); + } + // rewrite all used operands for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { MachineOperand& op = mii->getOperand(i); diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h index b0af8c5c739..90cc44d31c4 100644 --- a/lib/CodeGen/VirtRegMap.h +++ b/lib/CodeGen/VirtRegMap.h @@ -22,18 +22,23 @@ #include "llvm/CodeGen/SSARegMap.h" #include "Support/DenseMap.h" #include +#include namespace llvm { + class MachineInstr; + class VirtRegMap { public: typedef DenseMap Virt2PhysMap; typedef DenseMap Virt2StackSlotMap; + typedef std::multimap MI2VirtMap; private: MachineFunction* mf_; Virt2PhysMap v2pMap_; Virt2StackSlotMap v2ssMap_; + MI2VirtMap mi2vMap_; // do not implement VirtRegMap(const VirtRegMap& rhs); @@ -89,6 +94,15 @@ namespace llvm { int assignVirt2StackSlot(unsigned virtReg); + void virtFolded(unsigned virtReg, + MachineInstr* oldMI, + MachineInstr* newMI); + + std::pair + getFoldedVirts(MachineInstr* MI) const { + return mi2vMap_.equal_range(MI); + } + friend std::ostream& operator<<(std::ostream& os, const VirtRegMap& li); }; -- 2.34.1