X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FVirtRegMap.cpp;h=e0aa4053987c225a3545dbdea6f45daf1542e80b;hb=5be77762a3aa434ee877b0a03b98b5c3a7571918;hp=c5bfcfd301234dd04e004bce19429c0c4b46b725;hpb=8fe00540fc6e1531d909d0688cc75a77b7dfa330;p=oota-llvm.git diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index c5bfcfd3012..e0aa4053987 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -9,35 +9,38 @@ // // This file implements the VirtRegMap class. // -// It also contains implementations of the the Spiller interface, which, given a +// It also contains implementations of 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 "virtregmap" -#include "VirtRegMap.h" -#include "llvm/Function.h" +#define DEBUG_TYPE "regalloc" +#include "llvm/CodeGen/VirtRegMap.h" +#include "LiveDebugVariables.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/IR/Function.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" -#include "llvm/ADT/BitVector.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallSet.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" #include using namespace llvm; -STATISTIC(NumSpills , "Number of register spills"); +STATISTIC(NumSpillSlots, "Number of spill slots allocated"); +STATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting"); //===----------------------------------------------------------------------===// // VirtRegMap implementation @@ -45,47 +48,52 @@ STATISTIC(NumSpills , "Number of register spills"); char VirtRegMap::ID = 0; -static RegisterPass -X("virtregmap", "Virtual Register Map"); +INITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false) bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) { + MRI = &mf.getRegInfo(); TII = mf.getTarget().getInstrInfo(); + TRI = mf.getTarget().getRegisterInfo(); MF = &mf; - - ReMatId = MAX_STACK_SLOT+1; - LowSpillSlot = HighSpillSlot = NO_STACK_SLOT; - + Virt2PhysMap.clear(); Virt2StackSlotMap.clear(); - Virt2ReMatIdMap.clear(); Virt2SplitMap.clear(); - Virt2SplitKillMap.clear(); - ReMatMap.clear(); - ImplicitDefed.clear(); - SpillSlotToUsesMap.clear(); - MI2VirtMap.clear(); - SpillPt2VirtMap.clear(); - RestorePt2VirtMap.clear(); - EmergencySpillMap.clear(); - EmergencySpillSlots.clear(); - - SpillSlotToUsesMap.resize(8); - ImplicitDefed.resize(MF->getRegInfo().getLastVirtReg()+1- - TargetRegisterInfo::FirstVirtualRegister); + grow(); - return false; } void VirtRegMap::grow() { - unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg(); - Virt2PhysMap.grow(LastVirtReg); - Virt2StackSlotMap.grow(LastVirtReg); - Virt2ReMatIdMap.grow(LastVirtReg); - Virt2SplitMap.grow(LastVirtReg); - Virt2SplitKillMap.grow(LastVirtReg); - ReMatMap.grow(LastVirtReg); - ImplicitDefed.resize(LastVirtReg-TargetRegisterInfo::FirstVirtualRegister+1); + unsigned NumRegs = MF->getRegInfo().getNumVirtRegs(); + Virt2PhysMap.resize(NumRegs); + Virt2StackSlotMap.resize(NumRegs); + Virt2SplitMap.resize(NumRegs); +} + +unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) { + int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), + RC->getAlignment()); + ++NumSpillSlots; + return SS; +} + +bool VirtRegMap::hasPreferredPhys(unsigned VirtReg) { + unsigned Hint = MRI->getSimpleHint(VirtReg); + if (!Hint) + return 0; + if (TargetRegisterInfo::isVirtualRegister(Hint)) + Hint = getPhys(Hint); + return getPhys(VirtReg) == Hint; +} + +bool VirtRegMap::hasKnownPreference(unsigned VirtReg) { + std::pair Hint = MRI->getRegAllocationHint(VirtReg); + if (TargetRegisterInfo::isPhysicalRegister(Hint.second)) + return true; + if (TargetRegisterInfo::isVirtualRegister(Hint.second)) + return hasPhys(Hint.second); + return false; } int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { @@ -93,18 +101,7 @@ int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && "attempt to assign stack slot to already spilled register"); const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg); - int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(), - RC->getAlignment()); - if (LowSpillSlot == NO_STACK_SLOT) - LowSpillSlot = SS; - if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot) - HighSpillSlot = SS; - unsigned Idx = SS-LowSpillSlot; - while (Idx >= SpillSlotToUsesMap.size()) - SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2); - Virt2StackSlotMap[virtReg] = SS; - ++NumSpills; - return SS; + return Virt2StackSlotMap[virtReg] = createSpillSlot(RC); } void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { @@ -117,129 +114,286 @@ void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { Virt2StackSlotMap[virtReg] = SS; } -int VirtRegMap::assignVirtReMatId(unsigned virtReg) { - assert(TargetRegisterInfo::isVirtualRegister(virtReg)); - assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT && - "attempt to assign re-mat id to already spilled register"); - Virt2ReMatIdMap[virtReg] = ReMatId; - return ReMatId++; -} +void VirtRegMap::print(raw_ostream &OS, const Module*) const { + OS << "********** REGISTER MAP **********\n"; + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) { + OS << '[' << PrintReg(Reg, TRI) << " -> " + << PrintReg(Virt2PhysMap[Reg], TRI) << "] " + << MRI->getRegClass(Reg)->getName() << "\n"; + } + } -void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) { - assert(TargetRegisterInfo::isVirtualRegister(virtReg)); - assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT && - "attempt to assign re-mat id to already spilled register"); - Virt2ReMatIdMap[virtReg] = id; + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) { + OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg] + << "] " << MRI->getRegClass(Reg)->getName() << "\n"; + } + } + OS << '\n'; } -int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) { - std::map::iterator I = - EmergencySpillSlots.find(RC); - if (I != EmergencySpillSlots.end()) - return I->second; - int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(), - RC->getAlignment()); - if (LowSpillSlot == NO_STACK_SLOT) - LowSpillSlot = SS; - if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot) - HighSpillSlot = SS; - EmergencySpillSlots[RC] = SS; - return SS; +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +void VirtRegMap::dump() const { + print(dbgs()); } +#endif -void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) { - if (!MF->getFrameInfo()->isFixedObjectIndex(FI)) { - // If FI < LowSpillSlot, this stack reference was produced by - // instruction selection and is not a spill - if (FI >= LowSpillSlot) { - assert(FI >= 0 && "Spill slot index should not be negative!"); - assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size() - && "Invalid spill slot"); - SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI); - } - } -} +//===----------------------------------------------------------------------===// +// VirtRegRewriter +//===----------------------------------------------------------------------===// +// +// The VirtRegRewriter is the last of the register allocator passes. +// It rewrites virtual registers to physical registers as specified in the +// VirtRegMap analysis. It also updates live-in information on basic blocks +// according to LiveIntervals. +// +namespace { +class VirtRegRewriter : public MachineFunctionPass { + MachineFunction *MF; + const TargetMachine *TM; + const TargetRegisterInfo *TRI; + const TargetInstrInfo *TII; + MachineRegisterInfo *MRI; + SlotIndexes *Indexes; + LiveIntervals *LIS; + VirtRegMap *VRM; -void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI, - MachineInstr *NewMI, ModRef MRInfo) { - // Move previous memory references folded to new instruction. - MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI); - for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI), - E = MI2VirtMap.end(); I != E && I->first == OldMI; ) { - MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second)); - MI2VirtMap.erase(I++); - } + void rewrite(); + void addMBBLiveIns(); +public: + static char ID; + VirtRegRewriter() : MachineFunctionPass(ID) {} - // add new memory reference - MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo))); + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + + virtual bool runOnMachineFunction(MachineFunction&); +}; +} // end anonymous namespace + +char &llvm::VirtRegRewriterID = VirtRegRewriter::ID; + +INITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter", + "Virtual Register Rewriter", false, false) +INITIALIZE_PASS_DEPENDENCY(SlotIndexes) +INITIALIZE_PASS_DEPENDENCY(LiveIntervals) +INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) +INITIALIZE_PASS_DEPENDENCY(LiveStacks) +INITIALIZE_PASS_DEPENDENCY(VirtRegMap) +INITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter", + "Virtual Register Rewriter", false, false) + +char VirtRegRewriter::ID = 0; + +void VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + MachineFunctionPass::getAnalysisUsage(AU); } -void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) { - MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI); - MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo))); +bool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { + MF = &fn; + TM = &MF->getTarget(); + TRI = TM->getRegisterInfo(); + TII = TM->getInstrInfo(); + MRI = &MF->getRegInfo(); + Indexes = &getAnalysis(); + LIS = &getAnalysis(); + VRM = &getAnalysis(); + DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" + << "********** Function: " + << MF->getName() << '\n'); + DEBUG(VRM->dump()); + + // Add kill flags while we still have virtual registers. + LIS->addKillFlags(VRM); + + // Live-in lists on basic blocks are required for physregs. + addMBBLiveIns(); + + // Rewrite virtual registers. + rewrite(); + + // Write out new DBG_VALUE instructions. + getAnalysis().emitDebugValues(VRM); + + // All machine operands and other references to virtual registers have been + // replaced. Remove the virtual registers and release all the transient data. + VRM->clearAllVirt(); + MRI->clearVirtRegs(); + return true; } -void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (!MO.isFI()) - continue; - int FI = MO.getIndex(); - if (MF->getFrameInfo()->isFixedObjectIndex(FI)) +// Compute MBB live-in lists from virtual register live ranges and their +// assignments. +void VirtRegRewriter::addMBBLiveIns() { + SmallVector LiveIn; + for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { + unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); + if (MRI->reg_nodbg_empty(VirtReg)) continue; - // This stack reference was produced by instruction selection and - // is not a spill. - if (FI < LowSpillSlot) + LiveInterval &LI = LIS->getInterval(VirtReg); + if (LI.empty() || LIS->intervalIsInOneMBB(LI)) continue; - assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size() - && "Invalid spill slot"); - SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI); + // This is a virtual register that is live across basic blocks. Its + // assigned PhysReg must be marked as live-in to those blocks. + unsigned PhysReg = VRM->getPhys(VirtReg); + assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); + + // Scan the segments of LI. + for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I != E; + ++I) { + if (!Indexes->findLiveInMBBs(I->start, I->end, LiveIn)) + continue; + for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) + if (!LiveIn[i]->isLiveIn(PhysReg)) + LiveIn[i]->addLiveIn(PhysReg); + LiveIn.clear(); + } } - MI2VirtMap.erase(MI); - SpillPt2VirtMap.erase(MI); - RestorePt2VirtMap.erase(MI); - EmergencySpillMap.erase(MI); } -bool VirtRegMap::OnlyUseOfStackSlot(const MachineInstr *MI) const { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (!MO.isFI()) - continue; - int FI = MO.getIndex(); - if (MF->getFrameInfo()->isFixedObjectIndex(FI)) - continue; - // This stack reference was produced by instruction selection and - // is not a spill. - if (FI < LowSpillSlot) - continue; - assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size() - && "Invalid spill slot"); - if (SpillSlotToUsesMap[FI - LowSpillSlot].size() != 1) - return false; - } +void VirtRegRewriter::rewrite() { + SmallVector SuperDeads; + SmallVector SuperDefs; + SmallVector SuperKills; + SmallPtrSet NoReturnInsts; - return true; -} + for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); + MBBI != MBBE; ++MBBI) { + DEBUG(MBBI->print(dbgs(), Indexes)); + bool IsExitBB = MBBI->succ_empty(); + for (MachineBasicBlock::instr_iterator + MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { + MachineInstr *MI = MII; + ++MII; -void VirtRegMap::print(std::ostream &OS, const Module* M) const { - const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo(); + // Check if this instruction is a call to a noreturn function. + // If so, all the definitions set by this instruction can be ignored. + if (IsExitBB && MI->isCall()) + for (MachineInstr::mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); MOI != MOE; ++MOI) { + MachineOperand &MO = *MOI; + if (!MO.isGlobal()) + continue; + const Function *Func = dyn_cast(MO.getGlobal()); + if (!Func || !Func->hasFnAttribute(Attribute::NoReturn) || + // We need to keep correct unwind information + // even if the function will not return, since the + // runtime may need it. + !Func->hasFnAttribute(Attribute::NoUnwind)) + continue; + NoReturnInsts.insert(MI); + break; + } - OS << "********** REGISTER MAP **********\n"; - for (unsigned i = TargetRegisterInfo::FirstVirtualRegister, - e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) { - if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG) - OS << "[reg" << i << " -> " << TRI->getName(Virt2PhysMap[i]) - << "]\n"; - } + for (MachineInstr::mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); MOI != MOE; ++MOI) { + MachineOperand &MO = *MOI; - for (unsigned i = TargetRegisterInfo::FirstVirtualRegister, - e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) - if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT) - OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n"; - OS << '\n'; -} + // Make sure MRI knows about registers clobbered by regmasks. + if (MO.isRegMask()) + MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); -void VirtRegMap::dump() const { - print(cerr); + if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) + continue; + unsigned VirtReg = MO.getReg(); + unsigned PhysReg = VRM->getPhys(VirtReg); + assert(PhysReg != VirtRegMap::NO_PHYS_REG && + "Instruction uses unmapped VirtReg"); + assert(!MRI->isReserved(PhysReg) && "Reserved register assignment"); + + // Preserve semantics of sub-register operands. + if (MO.getSubReg()) { + // A virtual register kill refers to the whole register, so we may + // have to add operands for the super-register. A + // partial redef always kills and redefines the super-register. + if (MO.readsReg() && (MO.isDef() || MO.isKill())) + SuperKills.push_back(PhysReg); + + if (MO.isDef()) { + // The flag only makes sense for sub-register defs, and + // we are substituting a full physreg. An operand + // from the SuperKills list will represent the partial read of the + // super-register. + MO.setIsUndef(false); + + // Also add implicit defs for the super-register. + if (MO.isDead()) + SuperDeads.push_back(PhysReg); + else + SuperDefs.push_back(PhysReg); + } + + // PhysReg operands cannot have subregister indexes. + PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); + assert(PhysReg && "Invalid SubReg for physical register"); + MO.setSubReg(0); + } + // Rewrite. Note we could have used MachineOperand::substPhysReg(), but + // we need the inlining here. + MO.setReg(PhysReg); + } + + // Add any missing super-register kills after rewriting the whole + // instruction. + while (!SuperKills.empty()) + MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true); + + while (!SuperDeads.empty()) + MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true); + + while (!SuperDefs.empty()) + MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI); + + DEBUG(dbgs() << "> " << *MI); + + // Finally, remove any identity copies. + if (MI->isIdentityCopy()) { + ++NumIdCopies; + if (MI->getNumOperands() == 2) { + DEBUG(dbgs() << "Deleting identity copy.\n"); + if (Indexes) + Indexes->removeMachineInstrFromMaps(MI); + // It's safe to erase MI because MII has already been incremented. + MI->eraseFromParent(); + } else { + // Transform identity copy to a KILL to deal with subregisters. + MI->setDesc(TII->get(TargetOpcode::KILL)); + DEBUG(dbgs() << "Identity copy: " << *MI); + } + } + } + } + + // Tell MRI about physical registers in use. + if (NoReturnInsts.empty()) { + for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) + if (!MRI->reg_nodbg_empty(Reg)) + MRI->setPhysRegUsed(Reg); + } else { + for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) { + if (MRI->reg_nodbg_empty(Reg)) + continue; + // Check if this register has a use that will impact the rest of the + // code. Uses in debug and noreturn instructions do not impact the + // generated code. + for (MachineRegisterInfo::reg_nodbg_iterator It = + MRI->reg_nodbg_begin(Reg), + EndIt = MRI->reg_nodbg_end(); It != EndIt; ++It) { + if (!NoReturnInsts.count(&(*It))) { + MRI->setPhysRegUsed(Reg); + break; + } + } + } + } }