diff options
| -rw-r--r-- | lib/CodeGen/RegAllocLinearScan.cpp | 156 | ||||
| -rw-r--r-- | lib/CodeGen/VirtRegMap.cpp | 161 | ||||
| -rw-r--r-- | lib/CodeGen/VirtRegMap.h | 2 |
3 files changed, 176 insertions, 143 deletions
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 89952e6..42029dc 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -10,6 +10,7 @@ // This file implements a linear scan register allocator. // //===----------------------------------------------------------------------===// + #define DEBUG_TYPE "regalloc" #include "llvm/Function.h" #include "llvm/CodeGen/LiveVariables.h" @@ -18,28 +19,21 @@ #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/SSARegMap.h" #include "llvm/Target/MRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" -#include "llvm/Support/CFG.h" #include "Support/Debug.h" -#include "Support/DepthFirstIterator.h" -#include "Support/Statistic.h" -#include "Support/STLExtras.h" #include "LiveIntervals.h" #include "PhysRegTracker.h" #include "VirtRegMap.h" #include <algorithm> +#include <iostream> + using namespace llvm; namespace { - Statistic<> numStores("ra-linearscan", "Number of stores added"); - Statistic<> numLoads ("ra-linearscan", "Number of loads added"); - class RA : public MachineFunctionPass { private: MachineFunction* mf_; const TargetMachine* tm_; - const TargetInstrInfo* tii_; const MRegisterInfo* mri_; LiveIntervals* li_; typedef std::list<LiveIntervals::Interval*> IntervalPtrs; @@ -48,8 +42,6 @@ namespace { std::auto_ptr<PhysRegTracker> prt_; std::auto_ptr<VirtRegMap> vrm_; - int instrAdded_; - typedef std::vector<float> SpillWeights; SpillWeights spillWeights_; @@ -70,6 +62,9 @@ namespace { void releaseMemory(); private: + /// linearScan - the linear scan algorithm + void linearScan(); + /// initIntervalSets - initializa the four interval sets: /// unhandled, fixed, active and inactive void initIntervalSets(LiveIntervals::Intervals& li); @@ -90,10 +85,6 @@ namespace { /// is available, or spill. void assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur); - /// addSpillCode - adds spill code for interval. The interval - /// must be modified by LiveIntervals::updateIntervalForSpill. - void addSpillCode(IntervalPtrs::value_type li, int slot); - /// /// register handling helpers /// @@ -152,7 +143,6 @@ void RA::releaseMemory() bool RA::runOnMachineFunction(MachineFunction &fn) { mf_ = &fn; tm_ = &fn.getTarget(); - tii_ = &tm_->getInstrInfo(); mri_ = tm_->getRegisterInfo(); li_ = &getAnalysis<LiveIntervals>(); if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_)); @@ -160,6 +150,15 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { initIntervalSets(li_->getIntervals()); + linearScan(); + + eliminateVirtRegs(*mf_, *vrm_); + + return true; +} + +void RA::linearScan() +{ // linear scan algorithm DEBUG(std::cerr << "********** LINEAR SCAN **********\n"); DEBUG(std::cerr << "********** Function: " @@ -223,63 +222,6 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { } DEBUG(std::cerr << *vrm_); - - DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); - DEBUG(std::cerr << "********** Function: " - << mf_->getFunction()->getName() << '\n'); - - for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); - mbbi != mbbe; ++mbbi) { - instrAdded_ = 0; - - for (MachineBasicBlock::iterator mii = mbbi->begin(), mie = mbbi->end(); - mii != mie; ++mii) { - DEBUG( - std::cerr << '['; - unsigned index = li_->getInstructionIndex(mii); - if (index == std::numeric_limits<unsigned>::max()) - std::cerr << '*'; - else - std::cerr << index; - std::cerr << "]\t"; - mii->print(std::cerr, *tm_)); - - // use our current mapping and actually replace every - // virtual register with its allocated physical registers - DEBUG(std::cerr << "\t"); - for (unsigned i = 0, e = mii->getNumOperands(); - i != e; ++i) { - MachineOperand& op = mii->getOperand(i); - if (op.isRegister() && - MRegisterInfo::isVirtualRegister(op.getReg())) { - unsigned virtReg = op.getReg(); - unsigned physReg = vrm_->getPhys(virtReg); - DEBUG(std::cerr << "\t[reg" << virtReg - << " -> " << mri_->getName(physReg) << ']'); - mii->SetMachineOperandReg(i, physReg); - } - } - DEBUG(std::cerr << '\n'); - } - } - - DEBUG(std::cerr << "********** MACHINEINSTRS **********\n"); - DEBUG( - for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); - mbbi != mbbe; ++mbbi) { - std::cerr << mbbi->getBasicBlock()->getName() << ":\n"; - for (MachineBasicBlock::iterator mii = mbbi->begin(), - mie = mbbi->end(); mii != mie; ++mii) { - unsigned index = li_->getInstructionIndex(mii); - if (index == std::numeric_limits<unsigned>::max()) - std::cerr << "*\t"; - else - std::cerr << index << '\t'; - mii->print(std::cerr, *tm_); - } - }); - - return true; } void RA::initIntervalSets(LiveIntervals::Intervals& li) @@ -450,7 +392,6 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) // sorted on earliest start point and we may have changed our // start point. if (!cur->empty()) { - addSpillCode(cur, slot); IntervalPtrs::iterator it = unhandled_.begin(); while (it != unhandled_.end() && (*it)->start() < cur->start()) ++it; @@ -484,7 +425,6 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) earliestStart = std::min(earliestStart, (*i)->start()); int slot = vrm_->assignVirt2StackSlot((*i)->reg); li_->updateSpilledInterval(**i, slot); - addSpillCode(*i, slot); } } for (IntervalPtrs::iterator i = inactive_.begin(); @@ -497,7 +437,6 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) earliestStart = std::min(earliestStart, (*i)->start()); int slot = vrm_->assignVirt2StackSlot((*i)->reg); li_->updateSpilledInterval(**i, slot); - addSpillCode(*i, slot); } } @@ -580,71 +519,6 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) } } -void RA::addSpillCode(IntervalPtrs::value_type li, int slot) -{ - // We scan the instructions corresponding to each range. We load - // when we have a use and spill at end of basic blocks or end of - // ranges only if the register was modified. - const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li->reg); - - for (LiveIntervals::Interval::Ranges::iterator i = li->ranges.begin(), - e = li->ranges.end(); i != e; ++i) { - unsigned index = i->first; - unsigned end = i->second; - - bool loaded = false; - - // skip deleted instructions. getInstructionFromIndex returns - // null if the instruction was deleted (because of coalescing - // for example) - while (!li_->getInstructionFromIndex(index)) - index += LiveIntervals::InstrSlots::NUM; - MachineBasicBlock::iterator mi = li_->getInstructionFromIndex(index); - MachineBasicBlock* mbb = mi->getParent(); - assert(mbb && "machine instruction not bound to basic block"); - - for (; index < end; index += LiveIntervals::InstrSlots::NUM) { - // ignore deleted instructions - while (!li_->getInstructionFromIndex(index)) index += 2; - mi = li_->getInstructionFromIndex(index); - DEBUG(std::cerr << "\t\t\t\texamining: \t\t\t\t\t" - << LiveIntervals::getBaseIndex(index) << '\t'; - mi->print(std::cerr, *tm_)); - - // if it is used in this instruction load it - for (unsigned i = 0; i < mi->getNumOperands(); ++i) { - MachineOperand& mop = mi->getOperand(i); - if (mop.isRegister() && mop.getReg() == li->reg && - mop.isUse() && !loaded) { - loaded = true; - mri_->loadRegFromStackSlot(*mbb, mi, li->reg, slot, rc); - ++numLoads; - DEBUG(std::cerr << "\t\t\t\tadded load for reg" << li->reg - << " from ss#" << slot << " before: \t" - << LiveIntervals::getBaseIndex(index) << '\t'; - mi->print(std::cerr, *tm_)); - } - } - - // if it is defined in this instruction mark as dirty - for (unsigned i = 0; i < mi->getNumOperands(); ++i) { - MachineOperand& mop = mi->getOperand(i); - if (mop.isRegister() && mop.getReg() == li->reg && - mop.isDef()) { - loaded = true; - - mri_->storeRegToStackSlot(*mbb, next(mi), li->reg, slot,rc); - ++numStores; - DEBUG(std::cerr << "\t\t\t\tadded store for reg" << li->reg - << " to ss#" << slot << " after: \t\t" - << LiveIntervals::getBaseIndex(index) << " \t"; - mi->print(std::cerr, *tm_)); - } - } - } - } -} - unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur) { const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg); diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index bfbe0ef..bb29ffd 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -7,20 +7,32 @@ // //===----------------------------------------------------------------------===// // -// This file implements the virtual register map. +// This file implements the virtual register map. It also implements +// the eliminateVirtRegs() function that given a virtual register map +// and a machine function it eliminates all virtual references by +// replacing them with physical register references and adds spill +// code as necessary. // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "regalloc" #include "VirtRegMap.h" +#include "llvm/Function.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" #include "Support/Statistic.h" +#include "Support/Debug.h" +#include "Support/STLExtras.h" #include <iostream> using namespace llvm; namespace { - Statistic<> numSpills("ra-linearscan", "Number of register spills"); + Statistic<> numSpills("spiller", "Number of register spills"); + Statistic<> numStores("spiller", "Number of stores added"); + Statistic<> numLoads ("spiller", "Number of loads added"); + } int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) @@ -53,3 +65,148 @@ std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm) } return std::cerr << '\n'; } + +namespace { + + class Spiller { + typedef std::vector<unsigned> Phys2VirtMap; + typedef std::vector<bool> PhysFlag; + + MachineFunction& mf_; + const TargetMachine& tm_; + const TargetInstrInfo& tii_; + const MRegisterInfo& mri_; + const VirtRegMap& vrm_; + Phys2VirtMap p2vMap_; + PhysFlag dirty_; + + public: + Spiller(MachineFunction& mf, const VirtRegMap& vrm) + : mf_(mf), + tm_(mf_.getTarget()), + tii_(tm_.getInstrInfo()), + mri_(*tm_.getRegisterInfo()), + vrm_(vrm), + p2vMap_(mri_.getNumRegs()), + dirty_(mri_.getNumRegs()) { + DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); + DEBUG(std::cerr << "********** Function: " + << mf_.getFunction()->getName() << '\n'); + } + + void eliminateVirtRegs() { + for (MachineFunction::iterator mbbi = mf_.begin(), + mbbe = mf_.end(); mbbi != mbbe; ++mbbi) { + // clear map and dirty flag + p2vMap_.assign(p2vMap_.size(), 0); + dirty_.assign(dirty_.size(), false); + DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n"); + eliminateVirtRegsInMbb(*mbbi); + } + } + + private: + void vacateJustPhysReg(MachineBasicBlock& mbb, + MachineBasicBlock::iterator mii, + unsigned physReg) { + unsigned virtReg = p2vMap_[physReg]; + if (dirty_[physReg] && vrm_.hasStackSlot(virtReg)) { + mri_.storeRegToStackSlot(mbb, mii, physReg, + vrm_.getStackSlot(virtReg), + mri_.getRegClass(physReg)); + ++numStores; + DEBUG(std::cerr << "*\t"; prior(mii)->print(std::cerr, tm_)); + } + p2vMap_[physReg] = 0; + dirty_[physReg] = false; + } + + void vacatePhysReg(MachineBasicBlock& mbb, + MachineBasicBlock::iterator mii, + unsigned physReg) { + vacateJustPhysReg(mbb, mii, physReg); + for (const unsigned* as = mri_.getAliasSet(physReg); *as; ++as) + vacateJustPhysReg(mbb, mii, *as); + } + + void handleUse(MachineBasicBlock& mbb, + MachineBasicBlock::iterator mii, + unsigned virtReg, + unsigned physReg) { + // check if we are replacing a previous mapping + if (p2vMap_[physReg] != virtReg) { + vacatePhysReg(mbb, mii, physReg); + p2vMap_[physReg] = virtReg; + // load if necessary + if (vrm_.hasStackSlot(virtReg)) { + mri_.loadRegFromStackSlot(mbb, mii, physReg, + vrm_.getStackSlot(virtReg), + mri_.getRegClass(physReg)); + ++numLoads; + DEBUG(std::cerr << "*\t"; prior(mii)->print(std::cerr,tm_)); + } + } + } + + void handleDef(MachineBasicBlock& mbb, + MachineBasicBlock::iterator mii, + unsigned virtReg, + unsigned physReg) { + // check if we are replacing a previous mapping + if (p2vMap_[physReg] != virtReg) + vacatePhysReg(mbb, mii, physReg); + + p2vMap_[physReg] = virtReg; + dirty_[physReg] = true; + } + + void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) { + for (MachineBasicBlock::iterator mii = mbb.begin(), + mie = mbb.end(); mii != mie; ++mii) { + // rewrite all used operands + for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { + MachineOperand& op = mii->getOperand(i); + if (op.isRegister() && op.isUse() && + MRegisterInfo::isVirtualRegister(op.getReg())) { + unsigned physReg = vrm_.getPhys(op.getReg()); + handleUse(mbb, mii, op.getReg(), physReg); + mii->SetMachineOperandReg(i, physReg); + // mark as dirty if this is def&use + if (op.isDef()) dirty_[physReg] = true; + } + } + + // spill implicit defs + const TargetInstrDescriptor& tid =tii_.get(mii->getOpcode()); + for (const unsigned* id = tid.ImplicitDefs; *id; ++id) + vacatePhysReg(mbb, mii, *id); + + // rewrite def operands (def&use was handled with the + // uses so don't check for those here) + for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { + MachineOperand& op = mii->getOperand(i); + if (op.isRegister() && !op.isUse()) + if (MRegisterInfo::isPhysicalRegister(op.getReg())) + vacatePhysReg(mbb, mii, op.getReg()); + else { + unsigned physReg = vrm_.getPhys(op.getReg()); + handleDef(mbb, mii, op.getReg(), physReg); + mii->SetMachineOperandReg(i, physReg); + } + } + + DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_)); + } + + for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i) + vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i); + + } + }; +} + + +void llvm::eliminateVirtRegs(MachineFunction& mf, const VirtRegMap& vrm) +{ + Spiller(mf, vrm).eliminateVirtRegs(); +} diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h index f6a1cec..b5a819f 100644 --- a/lib/CodeGen/VirtRegMap.h +++ b/lib/CodeGen/VirtRegMap.h @@ -98,6 +98,8 @@ namespace llvm { std::ostream& operator<<(std::ostream& os, const VirtRegMap& li); + void eliminateVirtRegs(MachineFunction& mf, const VirtRegMap& vrm); + } // End llvm namespace #endif |