X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FVirtRegMap.cpp;h=7a7ea69e27fca567ad9ccbe04dbe2dacf1c43c5c;hb=bcb8c6d09ee426e0f774e3412912f6ae9e5f78dd;hp=c5bfcfd301234dd04e004bce19429c0c4b46b725;hpb=8fe00540fc6e1531d909d0688cc75a77b7dfa330;p=oota-llvm.git diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index c5bfcfd3012..7a7ea69e27f 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -9,7 +9,7 @@ // // 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. @@ -19,15 +19,19 @@ #define DEBUG_TYPE "virtregmap" #include "VirtRegMap.h" #include "llvm/Function.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/SlotIndexes.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" @@ -45,13 +49,14 @@ 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; @@ -70,43 +75,64 @@ bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) { EmergencySpillSlots.clear(); SpillSlotToUsesMap.resize(8); - ImplicitDefed.resize(MF->getRegInfo().getLastVirtReg()+1- - TargetRegisterInfo::FirstVirtualRegister); + ImplicitDefed.resize(MF->getRegInfo().getNumVirtRegs()); + + allocatableRCRegs.clear(); + for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(), + E = TRI->regclass_end(); I != E; ++I) + allocatableRCRegs.insert(std::make_pair(*I, + TRI->getAllocatableSet(mf, *I))); + 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); + Virt2ReMatIdMap.resize(NumRegs); + Virt2SplitMap.resize(NumRegs); + Virt2SplitKillMap.resize(NumRegs); + ReMatMap.resize(NumRegs); + ImplicitDefed.resize(NumRegs); } -int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { - assert(TargetRegisterInfo::isVirtualRegister(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()); +unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) { + int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), + RC->getAlignment()); if (LowSpillSlot == NO_STACK_SLOT) LowSpillSlot = SS; if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot) HighSpillSlot = SS; + assert(SS >= LowSpillSlot && "Unexpected low spill slot"); unsigned Idx = SS-LowSpillSlot; while (Idx >= SpillSlotToUsesMap.size()) SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2); - Virt2StackSlotMap[virtReg] = SS; - ++NumSpills; return SS; } +unsigned VirtRegMap::getRegAllocPref(unsigned virtReg) { + std::pair Hint = MRI->getRegAllocationHint(virtReg); + unsigned physReg = Hint.second; + if (TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg)) + physReg = getPhys(physReg); + if (Hint.first == 0) + return (TargetRegisterInfo::isPhysicalRegister(physReg)) + ? physReg : 0; + return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF); +} + +int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { + assert(TargetRegisterInfo::isVirtualRegister(virtReg)); + assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && + "attempt to assign stack slot to already spilled register"); + const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg); + ++NumSpills; + return Virt2StackSlotMap[virtReg] = createSpillSlot(RC); +} + void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { assert(TargetRegisterInfo::isVirtualRegister(virtReg)); assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && @@ -137,14 +163,7 @@ int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) { 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; + return EmergencySpillSlots[RC] = createSpillSlot(RC); } void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) { @@ -188,7 +207,7 @@ void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) { if (MF->getFrameInfo()->isFixedObjectIndex(FI)) continue; // This stack reference was produced by instruction selection and - // is not a spill. + // is not a spill if (FI < LowSpillSlot) continue; assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size() @@ -201,45 +220,141 @@ void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *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; +/// FindUnusedRegisters - Gather a list of allocatable registers that +/// have not been allocated to any virtual register. +bool VirtRegMap::FindUnusedRegisters(LiveIntervals* LIs) { + unsigned NumRegs = TRI->getNumRegs(); + UnusedRegs.reset(); + UnusedRegs.resize(NumRegs); + + BitVector Used(NumRegs); + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) + Used.set(Virt2PhysMap[Reg]); + } + + BitVector Allocatable = TRI->getAllocatableSet(*MF); + bool AnyUnused = false; + for (unsigned Reg = 1; Reg < NumRegs; ++Reg) { + if (Allocatable[Reg] && !Used[Reg] && !LIs->hasInterval(Reg)) { + bool ReallyUnused = true; + for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { + if (Used[*AS] || LIs->hasInterval(*AS)) { + ReallyUnused = false; + break; + } + } + if (ReallyUnused) { + AnyUnused = true; + UnusedRegs.set(Reg); + } + } + } + + return AnyUnused; +} + +void VirtRegMap::rewrite(SlotIndexes *Indexes) { + DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" + << "********** Function: " + << MF->getFunction()->getName() << '\n'); + DEBUG(dump()); + SmallVector SuperKills; + + for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); + MBBI != MBBE; ++MBBI) { + DEBUG(MBBI->print(dbgs(), Indexes)); + for (MachineBasicBlock::iterator MII = MBBI->begin(), MIE = MBBI->end(); + MII != MIE;) { + MachineInstr *MI = MII; + ++MII; + + for (MachineInstr::mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); MOI != MOE; ++MOI) { + MachineOperand &MO = *MOI; + if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) + continue; + unsigned VirtReg = MO.getReg(); + unsigned PhysReg = getPhys(VirtReg); + assert(PhysReg != NO_PHYS_REG && "Instruction uses unmapped VirtReg"); + + // 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. + if (MO.isUse() && MO.isKill() && !MO.isUndef()) + SuperKills.push_back(PhysReg); + + // We don't have to deal with sub-register defs because + // LiveIntervalAnalysis already added the necessary + // operands. + + // 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); + + DEBUG(dbgs() << "> " << *MI); + + // Finally, remove any identity copies. + if (MI->isIdentityCopy()) { + if (MI->getNumOperands() == 2) { + DEBUG(dbgs() << "Deleting identity copy.\n"); + RemoveMachineInstrFromMaps(MI); + 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); + } + } + } } - return true; + // Tell MRI about physical registers in use. + for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) + if (!MRI->reg_nodbg_empty(Reg)) + MRI->setPhysRegUsed(Reg); } -void VirtRegMap::print(std::ostream &OS, const Module* M) const { +void VirtRegMap::print(raw_ostream &OS, const Module* M) const { const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo(); + const MachineRegisterInfo &MRI = MF->getRegInfo(); 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 (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"; + } } - 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"; + 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'; } void VirtRegMap::dump() const { - print(cerr); + print(dbgs()); }