diff options
-rw-r--r-- | lib/CodeGen/VirtRegMap.cpp | 614 | ||||
-rw-r--r-- | lib/CodeGen/VirtRegMap.h | 210 |
2 files changed, 417 insertions, 407 deletions
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index cffe77c..5296086 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -7,353 +7,367 @@ // //===----------------------------------------------------------------------===// // -// 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 +// This file implements the VirtRegMap class. +// +// It also contains implementations of the the Spiller interface, which, given a +// virtual register map and a machine function, eliminates all virtual +// references by replacing them with physical register references - adding spill // code as necessary. // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" +#define DEBUG_TYPE "spiller" #include "VirtRegMap.h" #include "llvm/Function.h" #include "llvm/CodeGen/MachineFrameInfo.h" -#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/SSARegMap.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" -#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" - using namespace llvm; namespace { - Statistic<> numSpills("spiller", "Number of register spills"); - Statistic<> numStores("spiller", "Number of stores added"); - Statistic<> numLoads ("spiller", "Number of loads added"); - - enum SpillerName { simple, local }; - - cl::opt<SpillerName> - SpillerOpt("spiller", - cl::desc("Spiller to use: (default: local)"), - cl::Prefix, - cl::values(clEnumVal(simple, " simple spiller"), - clEnumVal(local, " local spiller"), - clEnumValEnd), - cl::init(local)); + Statistic<> NumSpills("spiller", "Number of register spills"); + Statistic<> NumStores("spiller", "Number of stores added"); + Statistic<> NumLoads ("spiller", "Number of loads added"); + + enum SpillerName { simple, local }; + + cl::opt<SpillerName> + SpillerOpt("spiller", + cl::desc("Spiller to use: (default: local)"), + cl::Prefix, + cl::values(clEnumVal(simple, " simple spiller"), + clEnumVal(local, " local spiller"), + clEnumValEnd), + cl::init(local)); +} + +//===----------------------------------------------------------------------===// +// VirtRegMap implementation +//===----------------------------------------------------------------------===// + +void VirtRegMap::grow() { + v2pMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); + v2ssMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); } -int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) -{ - assert(MRegisterInfo::isVirtualRegister(virtReg)); - assert(v2ssMap_[virtReg] == NO_STACK_SLOT && - "attempt to assign stack slot to already spilled register"); - const TargetRegisterClass* RC = - mf_->getSSARegMap()->getRegClass(virtReg); - int frameIndex = mf_->getFrameInfo()->CreateStackObject(RC->getSize(), - RC->getAlignment()); - v2ssMap_[virtReg] = frameIndex; - ++numSpills; - return frameIndex; +int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { + assert(MRegisterInfo::isVirtualRegister(virtReg)); + assert(v2ssMap_[virtReg] == NO_STACK_SLOT && + "attempt to assign stack slot to already spilled register"); + const TargetRegisterClass* RC = mf_->getSSARegMap()->getRegClass(virtReg); + int frameIndex = mf_->getFrameInfo()->CreateStackObject(RC->getSize(), + RC->getAlignment()); + v2ssMap_[virtReg] = frameIndex; + ++NumSpills; + return frameIndex; } -void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) -{ - assert(MRegisterInfo::isVirtualRegister(virtReg)); - assert(v2ssMap_[virtReg] == NO_STACK_SLOT && - "attempt to assign stack slot to already spilled register"); - v2ssMap_[virtReg] = frameIndex; +void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) { + assert(MRegisterInfo::isVirtualRegister(virtReg)); + assert(v2ssMap_[virtReg] == NO_STACK_SLOT && + "attempt to assign stack slot to already spilled register"); + v2ssMap_[virtReg] = frameIndex; } void VirtRegMap::virtFolded(unsigned virtReg, MachineInstr* oldMI, - MachineInstr* newMI) -{ - // move previous memory references folded to new instruction - MI2VirtMap::iterator i, e; - std::vector<MI2VirtMap::mapped_type> 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)); + MachineInstr* newMI) { + // move previous memory references folded to new instruction + MI2VirtMap::iterator i, e; + std::vector<MI2VirtMap::mapped_type> 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)); +} - // add new memory reference - mi2vMap_.insert(std::make_pair(newMI, virtReg)); +void VirtRegMap::print(std::ostream& os) const { + const MRegisterInfo* mri = mf_->getTarget().getRegisterInfo(); + + std::cerr << "********** REGISTER MAP **********\n"; + for (unsigned i = MRegisterInfo::FirstVirtualRegister, + e = mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) { + if (v2pMap_[i] != (unsigned)VirtRegMap::NO_PHYS_REG) + std::cerr << "[reg" << i << " -> " + << mri->getName(v2pMap_[i]) << "]\n"; + } + + for (unsigned i = MRegisterInfo::FirstVirtualRegister, + e = mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) { + if (v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT) + std::cerr << "[reg" << i << " -> fi#" + << v2ssMap_[i] << "]\n"; + } + std::cerr << '\n'; } -std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm) -{ - const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo(); +void VirtRegMap::dump() const { print(std::cerr); } - std::cerr << "********** REGISTER MAP **********\n"; - for (unsigned i = MRegisterInfo::FirstVirtualRegister, - e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) { - if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG) - std::cerr << "[reg" << i << " -> " - << mri->getName(vrm.v2pMap_[i]) << "]\n"; - } - for (unsigned i = MRegisterInfo::FirstVirtualRegister, - e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) { - if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT) - std::cerr << "[reg" << i << " -> fi#" - << vrm.v2ssMap_[i] << "]\n"; - } - return std::cerr << '\n'; -} -Spiller::~Spiller() -{ +//===----------------------------------------------------------------------===// +// Simple Spiller Implementation +//===----------------------------------------------------------------------===// -} +Spiller::~Spiller() {} namespace { + struct SimpleSpiller : public Spiller { + bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap &VRM); + }; +} - class SimpleSpiller : public Spiller { - public: - bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) { - DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); - DEBUG(std::cerr << "********** Function: " - << mf.getFunction()->getName() << '\n'); - const TargetMachine& tm = mf.getTarget(); - const MRegisterInfo& mri = *tm.getRegisterInfo(); - - typedef DenseMap<bool, VirtReg2IndexFunctor> Loaded; - Loaded loaded; - - for (MachineFunction::iterator mbbi = mf.begin(), - mbbe = mf.end(); mbbi != mbbe; ++mbbi) { - DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n"); - for (MachineBasicBlock::iterator mii = mbbi->begin(), - mie = mbbi->end(); mii != mie; ++mii) { - loaded.grow(mf.getSSARegMap()->getLastVirtReg()); - for (unsigned i = 0,e = mii->getNumOperands(); i != e; ++i){ - MachineOperand& mop = mii->getOperand(i); - if (mop.isRegister() && mop.getReg() && - MRegisterInfo::isVirtualRegister(mop.getReg())) { - unsigned virtReg = mop.getReg(); - unsigned physReg = vrm.getPhys(virtReg); - if (mop.isUse() && - vrm.hasStackSlot(mop.getReg()) && - !loaded[virtReg]) { - mri.loadRegFromStackSlot( - *mbbi, - mii, - physReg, - vrm.getStackSlot(virtReg)); - loaded[virtReg] = true; - DEBUG(std::cerr << '\t'; - prior(mii)->print(std::cerr, &tm)); - ++numLoads; - } - if (mop.isDef() && - vrm.hasStackSlot(mop.getReg())) { - mri.storeRegToStackSlot( - *mbbi, - next(mii), - physReg, - vrm.getStackSlot(virtReg)); - ++numStores; - } - mii->SetMachineOperandReg(i, physReg); - } - } - DEBUG(std::cerr << '\t'; mii->print(std::cerr, &tm)); - loaded.clear(); - } - } - return true; - } - }; - - class LocalSpiller : public Spiller { - typedef std::vector<unsigned> Phys2VirtMap; - typedef std::vector<bool> PhysFlag; - typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI; - - MachineFunction* mf_; - const TargetMachine* tm_; - const TargetInstrInfo* tii_; - const MRegisterInfo* mri_; - const VirtRegMap* vrm_; - Phys2VirtMap p2vMap_; - PhysFlag dirty_; - Virt2MI lastDef_; - - public: - bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) { - mf_ = &mf; - tm_ = &mf_->getTarget(); - tii_ = tm_->getInstrInfo(); - mri_ = tm_->getRegisterInfo(); - vrm_ = &vrm; - p2vMap_.assign(mri_->getNumRegs(), 0); - dirty_.assign(mri_->getNumRegs(), false); - - 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) { - lastDef_.grow(mf_->getSSARegMap()->getLastVirtReg()); - DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n"); - eliminateVirtRegsInMbb(*mbbi); - // clear map, dirty flag and last ref - p2vMap_.assign(p2vMap_.size(), 0); - dirty_.assign(dirty_.size(), false); - lastDef_.clear(); - } - return true; +bool SimpleSpiller::runOnMachineFunction(MachineFunction& MF, + const VirtRegMap& VRM) { + DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); + DEBUG(std::cerr << "********** Function: " + << MF.getFunction()->getName() << '\n'); + const TargetMachine& TM = MF.getTarget(); + const MRegisterInfo& mri = *TM.getRegisterInfo(); + + DenseMap<bool, VirtReg2IndexFunctor> Loaded; + + for (MachineFunction::iterator mbbi = MF.begin(), E = MF.end(); + mbbi != E; ++mbbi) { + DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n"); + for (MachineBasicBlock::iterator mii = mbbi->begin(), + mie = mbbi->end(); mii != mie; ++mii) { + Loaded.grow(MF.getSSARegMap()->getLastVirtReg()); + for (unsigned i = 0,e = mii->getNumOperands(); i != e; ++i){ + MachineOperand& mop = mii->getOperand(i); + if (mop.isRegister() && mop.getReg() && + MRegisterInfo::isVirtualRegister(mop.getReg())) { + unsigned virtReg = mop.getReg(); + unsigned physReg = VRM.getPhys(virtReg); + if (mop.isUse() && VRM.hasStackSlot(mop.getReg()) && + !Loaded[virtReg]) { + mri.loadRegFromStackSlot(*mbbi, mii, physReg, + VRM.getStackSlot(virtReg)); + Loaded[virtReg] = true; + DEBUG(std::cerr << '\t'; + prior(mii)->print(std::cerr, &TM)); + ++NumLoads; + } + + if (mop.isDef() && VRM.hasStackSlot(mop.getReg())) { + mri.storeRegToStackSlot(*mbbi, next(mii), physReg, + VRM.getStackSlot(virtReg)); + ++NumStores; + } + mii->SetMachineOperandReg(i, physReg); } + } + DEBUG(std::cerr << '\t'; mii->print(std::cerr, &TM)); + Loaded.clear(); + } + } + return true; +} - private: - void vacateJustPhysReg(MachineBasicBlock& mbb, - MachineBasicBlock::iterator mii, - unsigned physReg) { - unsigned virtReg = p2vMap_[physReg]; - if (dirty_[physReg] && vrm_->hasStackSlot(virtReg)) { - assert(lastDef_[virtReg] && "virtual register is mapped " - "to a register and but was not defined!"); - MachineBasicBlock::iterator lastDef = lastDef_[virtReg]; - MachineBasicBlock::iterator nextLastRef = next(lastDef); - mri_->storeRegToStackSlot(*lastDef->getParent(), - nextLastRef, - physReg, - vrm_->getStackSlot(virtReg)); - ++numStores; - DEBUG(std::cerr << "added: "; - prior(nextLastRef)->print(std::cerr, tm_); - std::cerr << "after: "; - lastDef->print(std::cerr, tm_)); - lastDef_[virtReg] = 0; - } - p2vMap_[physReg] = 0; - dirty_[physReg] = false; - } +//===----------------------------------------------------------------------===// +// Local Spiller Implementation +//===----------------------------------------------------------------------===// - void vacatePhysReg(MachineBasicBlock& mbb, +namespace { + class LocalSpiller : public Spiller { + typedef std::vector<unsigned> Phys2VirtMap; + typedef std::vector<bool> PhysFlag; + typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI; + + MachineFunction *MF; + const TargetMachine *TM; + const TargetInstrInfo *TII; + const MRegisterInfo *MRI; + const VirtRegMap *VRM; + Phys2VirtMap p2vMap_; + PhysFlag dirty_; + Virt2MI lastDef_; + + public: + bool runOnMachineFunction(MachineFunction &MF, const VirtRegMap &VRM); + + private: + void vacateJustPhysReg(MachineBasicBlock& mbb, MachineBasicBlock::iterator mii, - unsigned physReg) { - vacateJustPhysReg(mbb, mii, physReg); - for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) - vacateJustPhysReg(mbb, mii, *as); - } + unsigned physReg); - void handleUse(MachineBasicBlock& mbb, + void vacatePhysReg(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)); - ++numLoads; - DEBUG(std::cerr << "added: "; - prior(mii)->print(std::cerr, tm_)); - lastDef_[virtReg] = mii; - } - } + 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)); + ++NumLoads; + DEBUG(std::cerr << "added: "; + prior(mii)->print(std::cerr, TM)); + lastDef_[virtReg] = mii; } + } + } - 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); + 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; + lastDef_[virtReg] = mii; + } + + void eliminateVirtRegsInMbb(MachineBasicBlock& mbb); + }; +} + +bool LocalSpiller::runOnMachineFunction(MachineFunction &mf, + const VirtRegMap &vrm) { + MF = &mf; + TM = &MF->getTarget(); + TII = TM->getInstrInfo(); + MRI = TM->getRegisterInfo(); + VRM = &vrm; + p2vMap_.assign(MRI->getNumRegs(), 0); + dirty_.assign(MRI->getNumRegs(), false); + + 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) { + lastDef_.grow(MF->getSSARegMap()->getLastVirtReg()); + DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n"); + eliminateVirtRegsInMbb(*mbbi); + // clear map, dirty flag and last ref + p2vMap_.assign(p2vMap_.size(), 0); + dirty_.assign(dirty_.size(), false); + lastDef_.clear(); + } + return true; +} - p2vMap_[physReg] = virtReg; - dirty_[physReg] = true; - lastDef_[virtReg] = mii; +void LocalSpiller::vacateJustPhysReg(MachineBasicBlock& mbb, + MachineBasicBlock::iterator mii, + unsigned physReg) { + unsigned virtReg = p2vMap_[physReg]; + if (dirty_[physReg] && VRM->hasStackSlot(virtReg)) { + assert(lastDef_[virtReg] && "virtual register is mapped " + "to a register and but was not defined!"); + MachineBasicBlock::iterator lastDef = lastDef_[virtReg]; + MachineBasicBlock::iterator nextLastRef = next(lastDef); + MRI->storeRegToStackSlot(*lastDef->getParent(), + nextLastRef, + physReg, + VRM->getStackSlot(virtReg)); + ++NumStores; + DEBUG(std::cerr << "added: "; + prior(nextLastRef)->print(std::cerr, TM); + std::cerr << "after: "; + lastDef->print(std::cerr, TM)); + lastDef_[virtReg] = 0; + } + p2vMap_[physReg] = 0; + dirty_[physReg] = false; +} + +void LocalSpiller::eliminateVirtRegsInMbb(MachineBasicBlock &MBB) { + for (MachineBasicBlock::iterator MI = MBB.begin(), E = MBB.end(); + MI != E; ++MI) { + + // 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(MI); i != e; ++i) { + if (VRM->hasPhys(i->second)) + vacateJustPhysReg(MBB, MI, VRM->getPhys(i->second)); + } + + // rewrite all used operands + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& op = MI->getOperand(i); + if (op.isRegister() && op.getReg() && op.isUse() && + MRegisterInfo::isVirtualRegister(op.getReg())) { + unsigned virtReg = op.getReg(); + unsigned physReg = VRM->getPhys(virtReg); + handleUse(MBB, MI, virtReg, physReg); + MI->SetMachineOperandReg(i, physReg); + // mark as dirty if this is def&use + if (op.isDef()) { + dirty_[physReg] = true; + lastDef_[virtReg] = MI; } + } + } - 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) { - if (vrm_->hasPhys(i->second)) - vacateJustPhysReg(mbb, mii, vrm_->getPhys(i->second)); - } - - // rewrite all used operands - for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { - MachineOperand& op = mii->getOperand(i); - if (op.isRegister() && op.getReg() && op.isUse() && - MRegisterInfo::isVirtualRegister(op.getReg())) { - unsigned virtReg = op.getReg(); - unsigned physReg = vrm_->getPhys(virtReg); - handleUse(mbb, mii, virtReg, physReg); - mii->SetMachineOperandReg(i, physReg); - // mark as dirty if this is def&use - if (op.isDef()) { - dirty_[physReg] = true; - lastDef_[virtReg] = mii; - } - } - } - - // spill implicit physical register defs - const TargetInstrDescriptor& tid = tii_->get(mii->getOpcode()); - for (const unsigned* id = tid.ImplicitDefs; *id; ++id) - vacatePhysReg(mbb, mii, *id); - - // spill explicit physical register defs - for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { - MachineOperand& op = mii->getOperand(i); - if (op.isRegister() && op.getReg() && !op.isUse() && - MRegisterInfo::isPhysicalRegister(op.getReg())) - vacatePhysReg(mbb, mii, op.getReg()); - } - - // 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.getReg() && !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); + // spill implicit physical register defs + const TargetInstrDescriptor& tid = TII->get(MI->getOpcode()); + for (const unsigned* id = tid.ImplicitDefs; *id; ++id) + vacatePhysReg(MBB, MI, *id); + + // spill explicit physical register defs + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& op = MI->getOperand(i); + if (op.isRegister() && op.getReg() && !op.isUse() && + MRegisterInfo::isPhysicalRegister(op.getReg())) + vacatePhysReg(MBB, MI, op.getReg()); + } + // rewrite def operands (def&use was handled with the + // uses so don't check for those here) + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& op = MI->getOperand(i); + if (op.isRegister() && op.getReg() && !op.isUse()) + if (MRegisterInfo::isPhysicalRegister(op.getReg())) + vacatePhysReg(MBB, MI, op.getReg()); + else { + unsigned physReg = VRM->getPhys(op.getReg()); + handleDef(MBB, MI, op.getReg(), physReg); + MI->SetMachineOperandReg(i, physReg); } - }; + } + + DEBUG(std::cerr << '\t'; MI->print(std::cerr, TM)); + } + + for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i) + vacateJustPhysReg(MBB, MBB.getFirstTerminator(), i); } -llvm::Spiller* llvm::createSpiller() -{ - switch (SpillerOpt) { - default: - std::cerr << "no spiller selected"; - abort(); - case local: - return new LocalSpiller(); - case simple: - return new SimpleSpiller(); - } + +llvm::Spiller* llvm::createSpiller() { + switch (SpillerOpt) { + default: assert(0 && "Unreachable!"); + case local: + return new LocalSpiller(); + case simple: + return new SimpleSpiller(); + } } diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h index fb694d5..664ca62 100644 --- a/lib/CodeGen/VirtRegMap.h +++ b/lib/CodeGen/VirtRegMap.h @@ -7,125 +7,121 @@ // //===----------------------------------------------------------------------===// // -// This file implements a virtual register map. This maps virtual -// registers to physical registers and virtual registers to stack -// slots. It is created and updated by a register allocator and then -// used by a machine code rewriter that adds spill code and rewrites -// virtual into physical register references. +// This file implements a virtual register map. This maps virtual registers to +// physical registers and virtual registers to stack slots. It is created and +// updated by a register allocator and then used by a machine code rewriter that +// adds spill code and rewrites virtual into physical register references. // //===----------------------------------------------------------------------===// #ifndef LLVM_CODEGEN_VIRTREGMAP_H #define LLVM_CODEGEN_VIRTREGMAP_H -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/SSARegMap.h" +#include "llvm/Target/MRegisterInfo.h" #include "llvm/ADT/DenseMap.h" -#include <climits> #include <map> namespace llvm { - - class MachineInstr; - - class VirtRegMap { - public: - typedef DenseMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap; - typedef DenseMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap; - typedef std::multimap<MachineInstr*, unsigned> MI2VirtMap; - - private: - MachineFunction* mf_; - Virt2PhysMap v2pMap_; - Virt2StackSlotMap v2ssMap_; - MI2VirtMap mi2vMap_; - - // do not implement - VirtRegMap(const VirtRegMap& rhs); - const VirtRegMap& operator=(const VirtRegMap& rhs); - - enum { - NO_PHYS_REG = 0, - NO_STACK_SLOT = INT_MAX - }; - - public: - VirtRegMap(MachineFunction& mf) - : mf_(&mf), - v2pMap_(NO_PHYS_REG), - v2ssMap_(NO_STACK_SLOT) { - grow(); - } - - void grow() { - v2pMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); - v2ssMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); - } - - bool hasPhys(unsigned virtReg) const { - return getPhys(virtReg) != NO_PHYS_REG; - } - - unsigned getPhys(unsigned virtReg) const { - assert(MRegisterInfo::isVirtualRegister(virtReg)); - return v2pMap_[virtReg]; - } - - void assignVirt2Phys(unsigned virtReg, unsigned physReg) { - assert(MRegisterInfo::isVirtualRegister(virtReg) && - MRegisterInfo::isPhysicalRegister(physReg)); - assert(v2pMap_[virtReg] == NO_PHYS_REG && - "attempt to assign physical register to already mapped " - "virtual register"); - v2pMap_[virtReg] = physReg; - } - - void clearVirt(unsigned virtReg) { - assert(MRegisterInfo::isVirtualRegister(virtReg)); - assert(v2pMap_[virtReg] != NO_PHYS_REG && - "attempt to clear a not assigned virtual register"); - v2pMap_[virtReg] = NO_PHYS_REG; - } - - void clearAllVirt() { - v2pMap_.clear(); - grow(); - } - - bool hasStackSlot(unsigned virtReg) const { - return getStackSlot(virtReg) != NO_STACK_SLOT; - } - - int getStackSlot(unsigned virtReg) const { - assert(MRegisterInfo::isVirtualRegister(virtReg)); - return v2ssMap_[virtReg]; - } - - int assignVirt2StackSlot(unsigned virtReg); - void assignVirt2StackSlot(unsigned virtReg, int frameIndex); - - void virtFolded(unsigned virtReg, - MachineInstr* oldMI, - MachineInstr* newMI); - - std::pair<MI2VirtMap::const_iterator, MI2VirtMap::const_iterator> - getFoldedVirts(MachineInstr* MI) const { - return mi2vMap_.equal_range(MI); - } - - friend std::ostream& operator<<(std::ostream& os, const VirtRegMap& li); - }; - - std::ostream& operator<<(std::ostream& os, const VirtRegMap& li); - - struct Spiller { - virtual ~Spiller(); - - virtual bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) = 0; - + class MachineInstr; + + class VirtRegMap { + public: + typedef DenseMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap; + typedef DenseMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap; + typedef std::multimap<MachineInstr*, unsigned> MI2VirtMap; + + private: + MachineFunction* mf_; + Virt2PhysMap v2pMap_; + Virt2StackSlotMap v2ssMap_; + MI2VirtMap mi2vMap_; + + VirtRegMap(const VirtRegMap&); // DO NOT IMPLEMENT + void operator=(const VirtRegMap&); // DO NOT IMPLEMENT + + enum { + NO_PHYS_REG = 0, + NO_STACK_SLOT = ~0 >> 1 }; - Spiller* createSpiller(); + public: + VirtRegMap(MachineFunction& mf) + : mf_(&mf), v2pMap_(NO_PHYS_REG), v2ssMap_(NO_STACK_SLOT) { + grow(); + } + + void grow(); + + bool hasPhys(unsigned virtReg) const { + return getPhys(virtReg) != NO_PHYS_REG; + } + + unsigned getPhys(unsigned virtReg) const { + assert(MRegisterInfo::isVirtualRegister(virtReg)); + return v2pMap_[virtReg]; + } + + void assignVirt2Phys(unsigned virtReg, unsigned physReg) { + assert(MRegisterInfo::isVirtualRegister(virtReg) && + MRegisterInfo::isPhysicalRegister(physReg)); + assert(v2pMap_[virtReg] == NO_PHYS_REG && + "attempt to assign physical register to already mapped " + "virtual register"); + v2pMap_[virtReg] = physReg; + } + + void clearVirt(unsigned virtReg) { + assert(MRegisterInfo::isVirtualRegister(virtReg)); + assert(v2pMap_[virtReg] != NO_PHYS_REG && + "attempt to clear a not assigned virtual register"); + v2pMap_[virtReg] = NO_PHYS_REG; + } + + void clearAllVirt() { + v2pMap_.clear(); + grow(); + } + + bool hasStackSlot(unsigned virtReg) const { + return getStackSlot(virtReg) != NO_STACK_SLOT; + } + + int getStackSlot(unsigned virtReg) const { + assert(MRegisterInfo::isVirtualRegister(virtReg)); + return v2ssMap_[virtReg]; + } + + int assignVirt2StackSlot(unsigned virtReg); + void assignVirt2StackSlot(unsigned virtReg, int frameIndex); + + void virtFolded(unsigned virtReg, MachineInstr* oldMI, + MachineInstr* newMI); + + std::pair<MI2VirtMap::const_iterator, MI2VirtMap::const_iterator> + getFoldedVirts(MachineInstr* MI) const { + return mi2vMap_.equal_range(MI); + } + + void print(std::ostream &OS) const; + void dump() const; + }; + + inline std::ostream &operator<<(std::ostream &OS, const VirtRegMap &VRM) { + VRM.print(OS); + return OS; + } + + /// Spiller interface: Implementations of this interface assign spilled + /// virtual registers to stack slots, rewriting the code. + struct Spiller { + virtual ~Spiller(); + virtual bool runOnMachineFunction(MachineFunction &MF, + const VirtRegMap &VRM) = 0; + }; + + /// createSpiller - Create an return a spiller object, as specified on the + /// command line. + Spiller* createSpiller(); } // End llvm namespace |