X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLocal.cpp;h=765e7ff96ff7e83a277b9114343ed6c817cef079;hb=b5660dc8223bd5eb3d21d9855692617fcdec5663;hp=d3d5796e851c203fa01d0e3a6a121a4a78e7d1ce;hpb=6c087e5585b227f3c1d8278304c7cfbc7cd4f6e8;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp index d3d5796e851..765e7ff96ff 100644 --- a/lib/CodeGen/RegAllocLocal.cpp +++ b/lib/CodeGen/RegAllocLocal.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -14,12 +14,12 @@ #define DEBUG_TYPE "regalloc" #include "llvm/BasicBlock.h" -#include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/SSARegMap.h" #include "llvm/CodeGen/MachineFrameInfo.h" -#include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/RegAllocRegistry.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" @@ -29,12 +29,12 @@ #include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/STLExtras.h" #include using namespace llvm; STATISTIC(NumStores, "Number of stores added"); STATISTIC(NumLoads , "Number of loads added"); -STATISTIC(NumFolded, "Number of loads/stores folded into instructions"); namespace { static RegisterRegAlloc @@ -42,11 +42,15 @@ namespace { createLocalRegisterAllocator); - class VISIBILITY_HIDDEN RA : public MachineFunctionPass { + class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass { + public: + static char ID; + RALocal() : MachineFunctionPass((intptr_t)&ID) {} + private: const TargetMachine *TM; MachineFunction *MF; - const MRegisterInfo *RegInfo; - LiveVariables *LV; + const TargetRegisterInfo *TRI; + const TargetInstrInfo *TII; // StackSlotForVirtReg - Maps virtual regs to the frame index where these // values are spilled. @@ -81,25 +85,45 @@ namespace { // std::vector PhysRegsUseOrder; + // Virt2LastUseMap - This maps each virtual register to its last use + // (MachineInstr*, operand index pair). + IndexedMap, VirtReg2IndexFunctor> + Virt2LastUseMap; + + std::pair& getVirtRegLastUse(unsigned Reg) { + assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); + return Virt2LastUseMap[Reg]; + } + // VirtRegModified - This bitset contains information about which virtual // registers need to be spilled back to memory when their registers are // scavenged. If a virtual register has simply been rematerialized, there // is no reason to spill it to memory when we need the register back. // - std::vector VirtRegModified; + BitVector VirtRegModified; void markVirtRegModified(unsigned Reg, bool Val = true) { - assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - Reg -= MRegisterInfo::FirstVirtualRegister; - if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1); - VirtRegModified[Reg] = Val; + assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); + Reg -= TargetRegisterInfo::FirstVirtualRegister; + if (Val) + VirtRegModified.set(Reg); + else + VirtRegModified.reset(Reg); } bool isVirtRegModified(unsigned Reg) const { - assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size() + assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); + assert(Reg - TargetRegisterInfo::FirstVirtualRegister < VirtRegModified.size() && "Illegal virtual register!"); - return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister]; + return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister]; + } + + void AddToPhysRegsUseOrder(unsigned Reg) { + std::vector::iterator It = + std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), Reg); + if (It != PhysRegsUseOrder.end()) + PhysRegsUseOrder.erase(It); + PhysRegsUseOrder.push_back(Reg); } void MarkPhysRegRecentlyUsed(unsigned Reg) { @@ -143,7 +167,7 @@ namespace { /// bool areRegsEqual(unsigned R1, unsigned R2) const { if (R1 == R2) return true; - for (const unsigned *AliasSet = RegInfo->getAliasSet(R2); + for (const unsigned *AliasSet = TRI->getAliasSet(R2); *AliasSet; ++AliasSet) { if (*AliasSet == R1) return true; } @@ -180,13 +204,6 @@ namespace { /// void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg); - /// liberatePhysReg - Make sure the specified physical register is available - /// for use. If there is currently a value in it, it is either moved out of - /// the way or spilled to memory. - /// - void liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, - unsigned PhysReg); - /// isPhysRegAvailable - Return true if the specified physical register is /// free and available for use. This also includes checking to see if /// aliased registers are all free... @@ -224,11 +241,12 @@ namespace { void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, unsigned PhysReg); }; + char RALocal::ID = 0; } /// getStackSpaceFor - This allocates space for the specified virtual register /// to be held on the stack. -int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { +int RALocal::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { // Find the location Reg would belong... std::map::iterator I =StackSlotForVirtReg.lower_bound(VirtReg); @@ -248,7 +266,7 @@ int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { /// removePhysReg - This method marks the specified physical register as no /// longer being in use. /// -void RA::removePhysReg(unsigned PhysReg) { +void RALocal::removePhysReg(unsigned PhysReg) { PhysRegsUsed[PhysReg] = -1; // PhyReg no longer used std::vector::iterator It = @@ -262,24 +280,35 @@ void RA::removePhysReg(unsigned PhysReg) { /// virtual register slot specified by VirtReg. It then updates the RA data /// structures to indicate the fact that PhysReg is now available. /// -void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, - unsigned VirtReg, unsigned PhysReg) { +void RALocal::spillVirtReg(MachineBasicBlock &MBB, + MachineBasicBlock::iterator I, + unsigned VirtReg, unsigned PhysReg) { assert(VirtReg && "Spilling a physical register is illegal!" " Must not have appropriate kill for the register or use exists beyond" " the intended one."); - DOUT << " Spilling register " << RegInfo->getName(PhysReg) + DOUT << " Spilling register " << TRI->getName(PhysReg) << " containing %reg" << VirtReg; - if (!isVirtRegModified(VirtReg)) + + const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo(); + + if (!isVirtRegModified(VirtReg)) { DOUT << " which has not been modified, so no store necessary!"; - - // Otherwise, there is a virtual register corresponding to this physical - // register. We only need to spill it into its stack slot if it has been - // modified. - if (isVirtRegModified(VirtReg)) { - const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); + std::pair &LastUse = getVirtRegLastUse(VirtReg); + if (LastUse.first) + LastUse.first->getOperand(LastUse.second).setIsKill(); + } else { + // Otherwise, there is a virtual register corresponding to this physical + // register. We only need to spill it into its stack slot if it has been + // modified. + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); int FrameIndex = getStackSpaceFor(VirtReg, RC); DOUT << " to stack slot #" << FrameIndex; - RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC); + // If the instruction reads the register that's spilled, (e.g. this can + // happen if it is a move to a physical register), then the spill + // instruction is not a kill. + bool isKill = !(I != MBB.end() && + I->findRegisterUseOperandIdx(PhysReg) != -1); + TII->storeRegToStackSlot(MBB, I, PhysReg, isKill, FrameIndex, RC); ++NumStores; // Update statistics } @@ -295,8 +324,8 @@ void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, /// then the request is ignored if the physical register does not contain a /// virtual register. /// -void RA::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, - unsigned PhysReg, bool OnlyVirtRegs) { +void RALocal::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, + unsigned PhysReg, bool OnlyVirtRegs) { if (PhysRegsUsed[PhysReg] != -1) { // Only spill it if it's used! assert(PhysRegsUsed[PhysReg] != -2 && "Non allocable reg used!"); if (PhysRegsUsed[PhysReg] || !OnlyVirtRegs) @@ -304,23 +333,12 @@ void RA::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, } else { // If the selected register aliases any other registers, we must make // sure that one of the aliases isn't alive. - for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); + for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); *AliasSet; ++AliasSet) if (PhysRegsUsed[*AliasSet] != -1 && // Spill aliased register. PhysRegsUsed[*AliasSet] != -2) // If allocatable. - if (PhysRegsUsed[*AliasSet] == 0) { - // This must have been a dead def due to something like this: - // %EAX := - // := op %AL - // No more use of %EAX, %AH, etc. - // %EAX isn't dead upon definition, but %AH is. However %AH isn't - // an operand of definition MI so it's not marked as such. - DOUT << " Register " << RegInfo->getName(*AliasSet) - << " [%reg" << *AliasSet - << "] is never used, removing it frame live list\n"; - removePhysReg(*AliasSet); - } else - spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet); + if (PhysRegsUsed[*AliasSet]) + spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet); } } @@ -329,13 +347,13 @@ void RA::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, /// that PhysReg is the proper container for VirtReg now. The physical /// register must not be used for anything else when this is called. /// -void RA::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { +void RALocal::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { assert(PhysRegsUsed[PhysReg] == -1 && "Phys reg already assigned!"); // Update information to note the fact that this register was just used, and // it holds VirtReg. PhysRegsUsed[PhysReg] = VirtReg; getVirt2PhysRegMapSlot(VirtReg) = PhysReg; - PhysRegsUseOrder.push_back(PhysReg); // New use of PhysReg + AddToPhysRegsUseOrder(PhysReg); // New use of PhysReg } @@ -343,12 +361,12 @@ void RA::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { /// and available for use. This also includes checking to see if aliased /// registers are all free... /// -bool RA::isPhysRegAvailable(unsigned PhysReg) const { +bool RALocal::isPhysRegAvailable(unsigned PhysReg) const { if (PhysRegsUsed[PhysReg] != -1) return false; // If the selected register aliases any other allocated registers, it is // not free! - for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); + for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); *AliasSet; ++AliasSet) if (PhysRegsUsed[*AliasSet] != -1) // Aliased register in use? return false; // Can't use this reg then. @@ -359,7 +377,7 @@ bool RA::isPhysRegAvailable(unsigned PhysReg) const { /// getFreeReg - Look to see if there is a free register available in the /// specified register class. If not, return 0. /// -unsigned RA::getFreeReg(const TargetRegisterClass *RC) { +unsigned RALocal::getFreeReg(const TargetRegisterClass *RC) { // Get iterators defining the range of registers that are valid to allocate in // this class, which also specifies the preferred allocation order. TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF); @@ -374,23 +392,13 @@ unsigned RA::getFreeReg(const TargetRegisterClass *RC) { } -/// liberatePhysReg - Make sure the specified physical register is available for -/// use. If there is currently a value in it, it is either moved out of the way -/// or spilled to memory. -/// -void RA::liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, - unsigned PhysReg) { - spillPhysReg(MBB, I, PhysReg); -} - - /// getReg - Find a physical register to hold the specified virtual /// register. If all compatible physical registers are used, this method spills /// the last used virtual register to the stack, and uses that register. /// -unsigned RA::getReg(MachineBasicBlock &MBB, MachineInstr *I, - unsigned VirtReg) { - const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); +unsigned RALocal::getReg(MachineBasicBlock &MBB, MachineInstr *I, + unsigned VirtReg) { + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); // First check to see if we have a free register of the requested type... unsigned PhysReg = getFreeReg(RC); @@ -421,7 +429,7 @@ unsigned RA::getReg(MachineBasicBlock &MBB, MachineInstr *I, } else { // If one of the registers aliased to the current register is // compatible, use it. - for (const unsigned *AliasIt = RegInfo->getAliasSet(R); + for (const unsigned *AliasIt = TRI->getAliasSet(R); *AliasIt; ++AliasIt) { if (RC->contains(*AliasIt) && // If this is pinned down for some reason, don't use it. For @@ -465,8 +473,8 @@ unsigned RA::getReg(MachineBasicBlock &MBB, MachineInstr *I, /// subsequent instructions can use the reloaded value. This method returns the /// modified instruction. /// -MachineInstr *RA::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, - unsigned OpNum) { +MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned OpNum) { unsigned VirtReg = MI->getOperand(OpNum).getReg(); // If the virtual register is already available, just update the instruction @@ -479,24 +487,14 @@ MachineInstr *RA::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, // Otherwise, we need to fold it into the current instruction, or reload it. // If we have registers available to hold the value, use them. - const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); unsigned PhysReg = getFreeReg(RC); int FrameIndex = getStackSpaceFor(VirtReg, RC); if (PhysReg) { // Register is available, allocate it! assignVirtToPhysReg(VirtReg, PhysReg); } else { // No registers available. - // If we can fold this spill into this instruction, do so now. - if (MachineInstr* FMI = RegInfo->foldMemoryOperand(MI, OpNum, FrameIndex)){ - ++NumFolded; - // Since we changed the address of MI, make sure to update live variables - // to know that the new instruction has the properties of the old one. - LV->instructionChanged(MI, FMI); - return MBB.insert(MBB.erase(MI), FMI); - } - - // It looks like we can't fold this virtual register load into this - // instruction. Force some poor hapless value out of the register file to + // Force some poor hapless value out of the register file to // make room for the new register, and reload it. PhysReg = getReg(MBB, MI, VirtReg); } @@ -504,20 +502,44 @@ MachineInstr *RA::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, markVirtRegModified(VirtReg, false); // Note that this reg was just reloaded DOUT << " Reloading %reg" << VirtReg << " into " - << RegInfo->getName(PhysReg) << "\n"; + << TRI->getName(PhysReg) << "\n"; // Add move instruction(s) - RegInfo->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); + const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo(); + TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); ++NumLoads; // Update statistics - MF->setPhysRegUsed(PhysReg); + MF->getRegInfo().setPhysRegUsed(PhysReg); MI->getOperand(OpNum).setReg(PhysReg); // Assign the input register + getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum); return MI; } +/// isReadModWriteImplicitKill - True if this is an implicit kill for a +/// read/mod/write register, i.e. update partial register. +static bool isReadModWriteImplicitKill(MachineInstr *MI, unsigned Reg) { + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& MO = MI->getOperand(i); + if (MO.isRegister() && MO.getReg() == Reg && MO.isImplicit() && + MO.isDef() && !MO.isDead()) + return true; + } + return false; +} +/// isReadModWriteImplicitDef - True if this is an implicit def for a +/// read/mod/write register, i.e. update partial register. +static bool isReadModWriteImplicitDef(MachineInstr *MI, unsigned Reg) { + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& MO = MI->getOperand(i); + if (MO.isRegister() && MO.getReg() == Reg && MO.isImplicit() && + !MO.isDef() && MO.isKill()) + return true; + } + return false; +} -void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { +void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { // loop over each instruction MachineBasicBlock::iterator MII = MBB.begin(); const TargetInstrInfo &TII = *TM->getInstrInfo(); @@ -528,18 +550,18 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { // If this is the first basic block in the machine function, add live-in // registers as active. if (&MBB == &*MF->begin()) { - for (MachineFunction::livein_iterator I = MF->livein_begin(), - E = MF->livein_end(); I != E; ++I) { + for (MachineRegisterInfo::livein_iterator I=MF->getRegInfo().livein_begin(), + E = MF->getRegInfo().livein_end(); I != E; ++I) { unsigned Reg = I->first; - MF->setPhysRegUsed(Reg); + MF->getRegInfo().setPhysRegUsed(Reg); PhysRegsUsed[Reg] = 0; // It is free and reserved now - PhysRegsUseOrder.push_back(Reg); - for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + AddToPhysRegsUseOrder(Reg); + for (const unsigned *AliasSet = TRI->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { - PhysRegsUseOrder.push_back(*AliasSet); + AddToPhysRegsUseOrder(*AliasSet); PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - MF->setPhysRegUsed(*AliasSet); + MF->getRegInfo().setPhysRegUsed(*AliasSet); } } } @@ -548,12 +570,12 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { // Otherwise, sequentially allocate each instruction in the MBB. while (MII != MBB.end()) { MachineInstr *MI = MII++; - const TargetInstrDescriptor &TID = TII.get(MI->getOpcode()); + const TargetInstrDesc &TID = MI->getDesc(); DEBUG(DOUT << "\nStarting RegAlloc of: " << *MI; DOUT << " Regs have values: "; - for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i) + for (unsigned i = 0; i != TRI->getNumRegs(); ++i) if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) - DOUT << "[" << RegInfo->getName(i) + DOUT << "[" << TRI->getName(i) << ",%reg" << PhysRegsUsed[i] << "] "; DOUT << "\n"); @@ -568,8 +590,15 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { SmallVector Kills; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); - if (MO.isRegister() && MO.isKill()) - Kills.push_back(MO.getReg()); + if (MO.isRegister() && MO.isKill()) { + if (!MO.isImplicit()) + Kills.push_back(MO.getReg()); + else if (!isReadModWriteImplicitKill(MI, MO.getReg())) + // These are extra physical register kills when a sub-register + // is defined (def of a sub-register is a read/mod/write of the + // larger registers). Ignore. + Kills.push_back(MO.getReg()); + } } // Get the used operands into registers. This has the potential to spill @@ -582,7 +611,7 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { MachineOperand& MO = MI->getOperand(i); // here we are looking for only used operands (never def&use) if (MO.isRegister() && !MO.isDef() && MO.getReg() && !MO.isImplicit() && - MRegisterInfo::isVirtualRegister(MO.getReg())) + TargetRegisterInfo::isVirtualRegister(MO.getReg())) MI = reloadVirtReg(MBB, MI, i); } @@ -593,7 +622,7 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0, e = Kills.size(); i != e; ++i) { unsigned VirtReg = Kills[i]; unsigned PhysReg = VirtReg; - if (MRegisterInfo::isVirtualRegister(VirtReg)) { + if (TargetRegisterInfo::isVirtualRegister(VirtReg)) { // If the virtual register was never materialized into a register, it // might not be in the map, but it won't hurt to zero it out anyway. unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); @@ -602,17 +631,20 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { } else if (PhysRegsUsed[PhysReg] == -2) { // Unallocatable register dead, ignore. continue; + } else { + assert((!PhysRegsUsed[PhysReg] || PhysRegsUsed[PhysReg] == -1) && + "Silently clearing a virtual register?"); } if (PhysReg) { - DOUT << " Last use of " << RegInfo->getName(PhysReg) + DOUT << " Last use of " << TRI->getName(PhysReg) << "[%reg" << VirtReg <<"], removing it from live set\n"; removePhysReg(PhysReg); - for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); + for (const unsigned *AliasSet = TRI->getSubRegisters(PhysReg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { DOUT << " Last use of " - << RegInfo->getName(*AliasSet) + << TRI->getName(*AliasSet) << "[%reg" << VirtReg <<"], removing it from live set\n"; removePhysReg(*AliasSet); } @@ -625,20 +657,25 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); if (MO.isRegister() && MO.isDef() && !MO.isImplicit() && MO.getReg() && - MRegisterInfo::isPhysicalRegister(MO.getReg())) { + TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { unsigned Reg = MO.getReg(); if (PhysRegsUsed[Reg] == -2) continue; // Something like ESP. - - MF->setPhysRegUsed(Reg); + // These are extra physical register defs when a sub-register + // is defined (def of a sub-register is a read/mod/write of the + // larger registers). Ignore. + if (isReadModWriteImplicitDef(MI, MO.getReg())) continue; + + MF->getRegInfo().setPhysRegUsed(Reg); spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg PhysRegsUsed[Reg] = 0; // It is free and reserved now - PhysRegsUseOrder.push_back(Reg); - for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + AddToPhysRegsUseOrder(Reg); + + for (const unsigned *AliasSet = TRI->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { - PhysRegsUseOrder.push_back(*AliasSet); + MF->getRegInfo().setPhysRegUsed(*AliasSet); PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - MF->setPhysRegUsed(*AliasSet); + AddToPhysRegsUseOrder(*AliasSet); } } } @@ -649,22 +686,18 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { for (const unsigned *ImplicitDefs = TID.ImplicitDefs; *ImplicitDefs; ++ImplicitDefs) { unsigned Reg = *ImplicitDefs; - bool IsNonAllocatable = PhysRegsUsed[Reg] == -2; - if (!IsNonAllocatable) { + if (PhysRegsUsed[Reg] != -2) { spillPhysReg(MBB, MI, Reg, true); - PhysRegsUseOrder.push_back(Reg); + AddToPhysRegsUseOrder(Reg); PhysRegsUsed[Reg] = 0; // It is free and reserved now } - MF->setPhysRegUsed(Reg); - - for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + MF->getRegInfo().setPhysRegUsed(Reg); + for (const unsigned *AliasSet = TRI->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { - if (!IsNonAllocatable) { - PhysRegsUseOrder.push_back(*AliasSet); - PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - } - MF->setPhysRegUsed(*AliasSet); + AddToPhysRegsUseOrder(*AliasSet); + PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now + MF->getRegInfo().setPhysRegUsed(*AliasSet); } } } @@ -685,15 +718,16 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); if (MO.isRegister() && MO.isDef() && MO.getReg() && - MRegisterInfo::isVirtualRegister(MO.getReg())) { + TargetRegisterInfo::isVirtualRegister(MO.getReg())) { unsigned DestVirtReg = MO.getReg(); unsigned DestPhysReg; // If DestVirtReg already has a value, use it. if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) DestPhysReg = getReg(MBB, MI, DestVirtReg); - MF->setPhysRegUsed(DestPhysReg); + MF->getRegInfo().setPhysRegUsed(DestPhysReg); markVirtRegModified(DestVirtReg); + getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0); MI->getOperand(i).setReg(DestPhysReg); // Assign the output register } } @@ -704,7 +738,7 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0, e = DeadDefs.size(); i != e; ++i) { unsigned VirtReg = DeadDefs[i]; unsigned PhysReg = VirtReg; - if (MRegisterInfo::isVirtualRegister(VirtReg)) { + if (TargetRegisterInfo::isVirtualRegister(VirtReg)) { unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); PhysReg = PhysRegSlot; assert(PhysReg != 0); @@ -715,14 +749,14 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { } if (PhysReg) { - DOUT << " Register " << RegInfo->getName(PhysReg) + DOUT << " Register " << TRI->getName(PhysReg) << " [%reg" << VirtReg << "] is never used, removing it frame live list\n"; removePhysReg(PhysReg); - for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); + for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { - DOUT << " Register " << RegInfo->getName(*AliasSet) + DOUT << " Register " << TRI->getName(*AliasSet) << " [%reg" << *AliasSet << "] is never used, removing it frame live list\n"; removePhysReg(*AliasSet); @@ -733,28 +767,26 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { // Finally, if this is a noop copy instruction, zap it. unsigned SrcReg, DstReg; - if (TII.isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg) { - LV->removeVirtualRegistersKilled(MI); - LV->removeVirtualRegistersDead(MI); + if (TII.isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg) MBB.erase(MI); - } } MachineBasicBlock::iterator MI = MBB.getFirstTerminator(); // Spill all physical registers holding virtual registers now. - for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) - if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) + for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) + if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) { if (unsigned VirtReg = PhysRegsUsed[i]) spillVirtReg(MBB, MI, VirtReg, i); else removePhysReg(i); + } #if 0 // This checking code is very expensive. bool AllOk = true; - for (unsigned i = MRegisterInfo::FirstVirtualRegister, - e = MF->getSSARegMap()->getLastVirtReg(); i <= e; ++i) + for (unsigned i = TargetRegisterInfo::FirstVirtualRegister, + e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) if (unsigned PR = Virt2PhysRegMap[i]) { cerr << "Register still mapped: " << i << " -> " << PR << "\n"; AllOk = false; @@ -771,20 +803,20 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { /// runOnMachineFunction - Register allocate the whole function /// -bool RA::runOnMachineFunction(MachineFunction &Fn) { +bool RALocal::runOnMachineFunction(MachineFunction &Fn) { DOUT << "Machine Function " << "\n"; MF = &Fn; TM = &Fn.getTarget(); - RegInfo = TM->getRegisterInfo(); - LV = &getAnalysis(); + TRI = TM->getRegisterInfo(); + TII = TM->getInstrInfo(); - PhysRegsUsed.assign(RegInfo->getNumRegs(), -1); + PhysRegsUsed.assign(TRI->getNumRegs(), -1); // At various places we want to efficiently check to see whether a register // is allocatable. To handle this, we mark all unallocatable registers as // being pinned down, permanently. { - BitVector Allocable = RegInfo->getAllocatableSet(Fn); + BitVector Allocable = TRI->getAllocatableSet(Fn); for (unsigned i = 0, e = Allocable.size(); i != e; ++i) if (!Allocable[i]) PhysRegsUsed[i] = -2; // Mark the reg unallocable. @@ -792,7 +824,10 @@ bool RA::runOnMachineFunction(MachineFunction &Fn) { // initialize the virtual->physical register map to have a 'null' // mapping for all virtual registers - Virt2PhysRegMap.grow(MF->getSSARegMap()->getLastVirtReg()); + unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg(); + Virt2PhysRegMap.grow(LastVirtReg); + Virt2LastUseMap.grow(LastVirtReg); + VirtRegModified.resize(LastVirtReg+1-TargetRegisterInfo::FirstVirtualRegister); // Loop over all of the basic blocks, eliminating virtual register references for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); @@ -803,9 +838,10 @@ bool RA::runOnMachineFunction(MachineFunction &Fn) { PhysRegsUsed.clear(); VirtRegModified.clear(); Virt2PhysRegMap.clear(); + Virt2LastUseMap.clear(); return true; } FunctionPass *llvm::createLocalRegisterAllocator() { - return new RA(); + return new RALocal(); }