X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLocal.cpp;h=456c457a316e033262c469dc6bcba5d74ef56aad;hp=57f3c836e5513a182c4d5f92c97d3233c0f8edbe;hb=44a95e06cc0bb3a2d617fe94235aee92b1951910;hpb=b8822ad224d4eb5dc1b8b770bee11a2160e79141 diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp index 57f3c836e55..456c457a316 100644 --- a/lib/CodeGen/RegAllocLocal.cpp +++ b/lib/CodeGen/RegAllocLocal.cpp @@ -1,31 +1,52 @@ //===-- RegAllocLocal.cpp - A BasicBlock generic register allocator -------===// // +// 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 register allocator allocates registers to a basic block at a time, // attempting to keep values in registers and reusing registers as appropriate. // //===----------------------------------------------------------------------===// #define DEBUG_TYPE "regalloc" +#include "llvm/BasicBlock.h" #include "llvm/CodeGen/Passes.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/RegAllocRegistry.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" -#include "Support/CommandLine.h" -#include "Support/Debug.h" -#include "Support/Statistic.h" -#include +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Compiler.h" +#include "llvm/ADT/IndexedMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.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 { - Statistic<> NumSpilled ("ra-local", "Number of registers spilled"); - Statistic<> NumReloaded("ra-local", "Number of registers reloaded"); - cl::opt DisableKill("no-kill", cl::Hidden, - cl::desc("Disable register kill in local-ra")); + static RegisterRegAlloc + localRegAlloc("local", " local register allocator", + createLocalRegisterAllocator); + - class 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; @@ -37,16 +58,22 @@ namespace { // Virt2PhysRegMap - This map contains entries for each virtual register // that is currently available in a physical register. + IndexedMap Virt2PhysRegMap; + + unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) { + return Virt2PhysRegMap[VirtReg]; + } + + // PhysRegsUsed - This array is effectively a map, containing entries for + // each physical register that currently has a value (ie, it is in + // Virt2PhysRegMap). The value mapped to is the virtual register + // corresponding to the physical register (the inverse of the + // Virt2PhysRegMap), or 0. The value is set to 0 if this register is pinned + // because it is used by a future instruction, and to -2 if it is not + // allocatable. If the entry for a physical register is -1, then the + // physical register is "not in the map". // - std::map Virt2PhysRegMap; - - // PhysRegsUsed - This map contains entries for each physical register that - // currently has a value (ie, it is in Virt2PhysRegMap). The value mapped - // to is the virtual register corresponding to the physical register (the - // inverse of the Virt2PhysRegMap), or 0. The value is set to 0 if this - // register is pinned because it is used by a future instruction. - // - std::map PhysRegsUsed; + std::vector PhysRegsUsed; // PhysRegsUseOrder - This contains a list of the physical registers that // currently have a virtual register value in them. This list provides an @@ -66,32 +93,40 @@ namespace { std::vector VirtRegModified; void markVirtRegModified(unsigned Reg, bool Val = true) { - assert(Reg >= MRegisterInfo::FirstVirtualRegister && "Illegal VirtReg!"); + assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); Reg -= MRegisterInfo::FirstVirtualRegister; if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1); VirtRegModified[Reg] = Val; } bool isVirtRegModified(unsigned Reg) const { - assert(Reg >= MRegisterInfo::FirstVirtualRegister && "Illegal VirtReg!"); + assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size() - && "Illegal virtual register!"); + && "Illegal virtual register!"); return VirtRegModified[Reg - MRegisterInfo::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) { - assert(!PhysRegsUseOrder.empty() && "No registers used!"); - if (PhysRegsUseOrder.back() == Reg) return; // Already most recently used + if (PhysRegsUseOrder.empty() || + PhysRegsUseOrder.back() == Reg) return; // Already most recently used for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i) - if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) { - unsigned RegMatch = PhysRegsUseOrder[i-1]; // remove from middle - PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1); - // Add it to the end of the list - PhysRegsUseOrder.push_back(RegMatch); - if (RegMatch == Reg) - return; // Found an exact match, exit early - } + if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) { + unsigned RegMatch = PhysRegsUseOrder[i-1]; // remove from middle + PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1); + // Add it to the end of the list + PhysRegsUseOrder.push_back(RegMatch); + if (RegMatch == Reg) + return; // Found an exact match, exit early + } } public: @@ -100,9 +135,9 @@ namespace { } virtual void getAnalysisUsage(AnalysisUsage &AU) const { - if (!DisableKill) - AU.addRequired(); + AU.addRequired(); AU.addRequiredID(PHIEliminationID); + AU.addRequiredID(TwoAddressInstructionPassID); MachineFunctionPass::getAnalysisUsage(AU); } @@ -120,9 +155,10 @@ namespace { /// bool areRegsEqual(unsigned R1, unsigned R2) const { if (R1 == R2) return true; - if (const unsigned *AliasSet = RegInfo->getAliasSet(R2)) - for (unsigned i = 0; AliasSet[i]; ++i) - if (AliasSet[i] == R1) return true; + for (const unsigned *AliasSet = RegInfo->getAliasSet(R2); + *AliasSet; ++AliasSet) { + if (*AliasSet == R1) return true; + } return false; } @@ -139,14 +175,16 @@ namespace { /// the virtual register slot specified by VirtReg. It then updates the RA /// data structures to indicate the fact that PhysReg is now available. /// - void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, + void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned VirtReg, unsigned PhysReg); /// spillPhysReg - This method spills the specified physical register into - /// the virtual register slot associated with it. + /// the virtual register slot associated with it. If OnlyVirtRegs is set to + /// true, then the request is ignored if the physical register does not + /// contain a virtual register. /// - void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, - unsigned PhysReg); + void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, + unsigned PhysReg, bool OnlyVirtRegs = false); /// assignVirtToPhysReg - This method updates local state so that we know /// that PhysReg is the proper container for VirtReg now. The physical @@ -154,13 +192,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... @@ -171,32 +202,39 @@ namespace { /// specified register class. If not, return 0. /// unsigned getFreeReg(const TargetRegisterClass *RC); - + /// 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 getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, - unsigned VirtReg); - - /// reloadVirtReg - This method loads the specified virtual register into a - /// physical register, returning the physical register chosen. This updates - /// the regalloc data structures to reflect the fact that the virtual reg is - /// now alive in a physical register, and the previous one isn't. + unsigned getReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned VirtReg); + + /// reloadVirtReg - This method transforms the specified specified virtual + /// register use to refer to a physical register. This method may do this + /// in one of several ways: if the register is available in a physical + /// register already, it uses that physical register. If the value is not + /// in a physical register, and if there are physical registers available, + /// it loads it into a register. If register pressure is high, and it is + /// possible, it tries to fold the load of the virtual register into the + /// instruction itself. It avoids doing this if register pressure is low to + /// improve the chance that subsequent instructions can use the reloaded + /// value. This method returns the modified instruction. /// - unsigned reloadVirtReg(MachineBasicBlock &MBB, - MachineBasicBlock::iterator &I, unsigned VirtReg); + MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned OpNum); + 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); @@ -204,7 +242,8 @@ int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { return I->second; // Already has space allocated? // Allocate a new stack object for this spill location... - int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC); + int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(), + RC->getAlignment()); // Assign the slot... StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx)); @@ -212,17 +251,16 @@ int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { } -/// removePhysReg - This method marks the specified physical register as no +/// removePhysReg - This method marks the specified physical register as no /// longer being in use. /// -void RA::removePhysReg(unsigned PhysReg) { - PhysRegsUsed.erase(PhysReg); // PhyReg no longer used +void RALocal::removePhysReg(unsigned PhysReg) { + PhysRegsUsed[PhysReg] = -1; // PhyReg no longer used std::vector::iterator It = std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg); - assert(It != PhysRegsUseOrder.end() && - "Spilled a physical register, but it was not in use list!"); - PhysRegsUseOrder.erase(It); + if (It != PhysRegsUseOrder.end()) + PhysRegsUseOrder.erase(It); } @@ -230,54 +268,55 @@ 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) { - - DEBUG(std::cerr << " Spilling register " << RegInfo->getName(PhysReg)); - if (VirtReg == 0) { - DEBUG(std::cerr << " which corresponds to no vreg, " - << "must be spurious physreg: ignoring (WARNING)\n"); - } else { - // FIXME: move this into the conditional?? +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) + << " containing %reg" << VirtReg; + 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); int FrameIndex = getStackSpaceFor(VirtReg, RC); - - DEBUG(std::cerr << " containing %reg" << VirtReg; - if (!isVirtRegModified(VirtReg)) - std::cerr << " 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)) { - DEBUG(std::cerr << " to stack slot #" << FrameIndex); - RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC); - ++NumSpilled; // Update statistics - } - Virt2PhysRegMap.erase(VirtReg); // VirtReg no longer available + DOUT << " to stack slot #" << FrameIndex; + RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC); + ++NumStores; // Update statistics } - DEBUG(std::cerr << "\n"); + getVirt2PhysRegMapSlot(VirtReg) = 0; // VirtReg no longer available + + DOUT << "\n"; removePhysReg(PhysReg); } /// spillPhysReg - This method spills the specified physical register into the -/// virtual register slot associated with it. +/// virtual register slot associated with it. If OnlyVirtRegs is set to true, +/// then the request is ignored if the physical register does not contain a +/// virtual register. /// -void RA::spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, - unsigned PhysReg) { - std::map::iterator PI = PhysRegsUsed.find(PhysReg); - if (PI != PhysRegsUsed.end()) { // Only spill it if it's used! - spillVirtReg(MBB, I, PI->second, PhysReg); - } else if (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg)) { +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) + spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg); + } else { // If the selected register aliases any other registers, we must make - // sure that one of the aliases isn't alive... - for (unsigned i = 0; AliasSet[i]; ++i) { - PI = PhysRegsUsed.find(AliasSet[i]); - if (PI != PhysRegsUsed.end()) // Spill aliased register... - spillVirtReg(MBB, I, PI->second, AliasSet[i]); - } + // sure that one of the aliases isn't alive. + for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); + *AliasSet; ++AliasSet) + if (PhysRegsUsed[*AliasSet] != -1 && // Spill aliased register. + PhysRegsUsed[*AliasSet] != -2) // If allocatable. + if (PhysRegsUsed[*AliasSet]) + spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet); } } @@ -286,14 +325,13 @@ void RA::spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &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) { - assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() && - "Phys reg already assigned!"); +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; - Virt2PhysRegMap[VirtReg] = PhysReg; - PhysRegsUseOrder.push_back(PhysReg); // New use of PhysReg + getVirt2PhysRegMapSlot(VirtReg) = PhysReg; + AddToPhysRegsUseOrder(PhysReg); // New use of PhysReg } @@ -301,15 +339,15 @@ 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 { - if (PhysRegsUsed.count(PhysReg)) return false; +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! - if (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg)) - for (unsigned i = 0; AliasSet[i]; ++i) - if (PhysRegsUsed.count(AliasSet[i])) // Aliased register in use? - return false; // Can't use this reg then. + for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); + *AliasSet; ++AliasSet) + if (PhysRegsUsed[*AliasSet] != -1) // Aliased register in use? + return false; // Can't use this reg then. return true; } @@ -317,7 +355,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); @@ -332,55 +370,12 @@ 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) { - // FIXME: This code checks to see if a register is available, but it really - // wants to know if a reg is available BEFORE the instruction executes. If - // called after killed operands are freed, it runs the risk of reallocating a - // used operand... -#if 0 - if (isPhysRegAvailable(PhysReg)) return; // Already available... - - // Check to see if the register is directly used, not indirectly used through - // aliases. If aliased registers are the ones actually used, we cannot be - // sure that we will be able to save the whole thing if we do a reg-reg copy. - std::map::iterator PRUI = PhysRegsUsed.find(PhysReg); - if (PRUI != PhysRegsUsed.end()) { - unsigned VirtReg = PRUI->second; // The virtual register held... - - // Check to see if there is a compatible register available. If so, we can - // move the value into the new register... - // - const TargetRegisterClass *RC = RegInfo->getRegClass(PhysReg); - if (unsigned NewReg = getFreeReg(RC)) { - // Emit the code to copy the value... - RegInfo->copyRegToReg(MBB, I, NewReg, PhysReg, RC); - - // Update our internal state to indicate that PhysReg is available and Reg - // isn't. - Virt2PhysRegMap.erase(VirtReg); - removePhysReg(PhysReg); // Free the physreg - - // Move reference over to new register... - assignVirtToPhysReg(VirtReg, NewReg); - return; - } - } -#endif - 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, MachineBasicBlock::iterator &I, - unsigned VirtReg) { +unsigned RALocal::getReg(MachineBasicBlock &MBB, MachineInstr *I, + unsigned VirtReg) { const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); // First check to see if we have a free register of the requested type... @@ -396,21 +391,39 @@ unsigned RA::getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, for (unsigned i = 0; PhysReg == 0; ++i) { assert(i != PhysRegsUseOrder.size() && "Couldn't find a register of the appropriate class!"); - + unsigned R = PhysRegsUseOrder[i]; - // If the current register is compatible, use it. - if (RegInfo->getRegClass(R) == RC) { - PhysReg = R; - break; - } else { - // If one of the registers aliased to the current register is - // compatible, use it. - if (const unsigned *AliasSet = RegInfo->getAliasSet(R)) - for (unsigned a = 0; AliasSet[a]; ++a) - if (RegInfo->getRegClass(AliasSet[a]) == RC) { - PhysReg = AliasSet[a]; // Take an aliased register - break; - } + + // We can only use this register if it holds a virtual register (ie, it + // can be spilled). Do not use it if it is an explicitly allocated + // physical register! + assert(PhysRegsUsed[R] != -1 && + "PhysReg in PhysRegsUseOrder, but is not allocated?"); + if (PhysRegsUsed[R] && PhysRegsUsed[R] != -2) { + // If the current register is compatible, use it. + if (RC->contains(R)) { + PhysReg = R; + break; + } else { + // If one of the registers aliased to the current register is + // compatible, use it. + for (const unsigned *AliasIt = RegInfo->getAliasSet(R); + *AliasIt; ++AliasIt) { + if (RC->contains(*AliasIt) && + // If this is pinned down for some reason, don't use it. For + // example, if CL is pinned, and we run across CH, don't use + // CH as justification for using scavenging ECX (which will + // fail). + PhysRegsUsed[*AliasIt] != 0 && + + // Make sure the register is allocatable. Don't allocate SIL on + // x86-32. + PhysRegsUsed[*AliasIt] != -2) { + PhysReg = *AliasIt; // Take an aliased register + break; + } + } + } } } @@ -427,218 +440,378 @@ unsigned RA::getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, } -/// reloadVirtReg - This method loads the specified virtual register into a -/// physical register, returning the physical register chosen. This updates the -/// regalloc data structures to reflect the fact that the virtual reg is now -/// alive in a physical register, and the previous one isn't. +/// reloadVirtReg - This method transforms the specified specified virtual +/// register use to refer to a physical register. This method may do this in +/// one of several ways: if the register is available in a physical register +/// already, it uses that physical register. If the value is not in a physical +/// register, and if there are physical registers available, it loads it into a +/// register. If register pressure is high, and it is possible, it tries to +/// fold the load of the virtual register into the instruction itself. It +/// avoids doing this if register pressure is low to improve the chance that +/// subsequent instructions can use the reloaded value. This method returns the +/// modified instruction. /// -unsigned RA::reloadVirtReg(MachineBasicBlock &MBB, - MachineBasicBlock::iterator &I, - unsigned VirtReg) { - std::map::iterator It = Virt2PhysRegMap.find(VirtReg); - if (It != Virt2PhysRegMap.end()) { - MarkPhysRegRecentlyUsed(It->second); - return It->second; // Already have this value available! +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 + // and return. + if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) { + MarkPhysRegRecentlyUsed(PR); // Already have this value available! + MI->getOperand(OpNum).setReg(PR); // Assign the input register + return MI; } - unsigned PhysReg = getReg(MBB, I, VirtReg); - + // 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); + 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 + // make room for the new register, and reload it. + PhysReg = getReg(MBB, MI, VirtReg); + } + markVirtRegModified(VirtReg, false); // Note that this reg was just reloaded - DEBUG(std::cerr << " Reloading %reg" << VirtReg << " into " - << RegInfo->getName(PhysReg) << "\n"); + DOUT << " Reloading %reg" << VirtReg << " into " + << RegInfo->getName(PhysReg) << "\n"; // Add move instruction(s) - RegInfo->loadRegFromStackSlot(MBB, I, PhysReg, FrameIndex, RC); - ++NumReloaded; // Update statistics - return PhysReg; + RegInfo->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); + ++NumLoads; // Update statistics + + MF->setPhysRegUsed(PhysReg); + MI->getOperand(OpNum).setReg(PhysReg); // Assign the input register + 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 I = MBB.begin(); - for (; I != MBB.end(); ++I) { - MachineInstr *MI = *I; - const TargetInstrDescriptor &TID = TM->getInstrInfo().get(MI->getOpcode()); - DEBUG(std::cerr << "\nStarting RegAlloc of: " << *MI; - std::cerr << " Regs have values: "; - for (std::map::const_iterator - I = PhysRegsUsed.begin(), E = PhysRegsUsed.end(); I != E; ++I) - std::cerr << "[" << RegInfo->getName(I->first) - << ",%reg" << I->second << "] "; - std::cerr << "\n"); + MachineBasicBlock::iterator MII = MBB.begin(); + const TargetInstrInfo &TII = *TM->getInstrInfo(); + + DEBUG(const BasicBlock *LBB = MBB.getBasicBlock(); + if (LBB) DOUT << "\nStarting RegAlloc of BB: " << LBB->getName()); + + // 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) { + unsigned Reg = I->first; + MF->setPhysRegUsed(Reg); + PhysRegsUsed[Reg] = 0; // It is free and reserved now + AddToPhysRegsUseOrder(Reg); + for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); + *AliasSet; ++AliasSet) { + if (PhysRegsUsed[*AliasSet] != -2) { + AddToPhysRegsUseOrder(*AliasSet); + PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now + MF->setPhysRegUsed(*AliasSet); + } + } + } + } + + // Otherwise, sequentially allocate each instruction in the MBB. + while (MII != MBB.end()) { + MachineInstr *MI = MII++; + const TargetInstrDescriptor &TID = TII.get(MI->getOpcode()); + DEBUG(DOUT << "\nStarting RegAlloc of: " << *MI; + DOUT << " Regs have values: "; + for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i) + if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) + DOUT << "[" << RegInfo->getName(i) + << ",%reg" << PhysRegsUsed[i] << "] "; + DOUT << "\n"); // Loop over the implicit uses, making sure that they are at the head of the // use order list, so they don't get reallocated. - if (const unsigned *ImplicitUses = TID.ImplicitUses) - for (unsigned i = 0; ImplicitUses[i]; ++i) - MarkPhysRegRecentlyUsed(ImplicitUses[i]); + if (TID.ImplicitUses) { + for (const unsigned *ImplicitUses = TID.ImplicitUses; + *ImplicitUses; ++ImplicitUses) + MarkPhysRegRecentlyUsed(*ImplicitUses); + } + + SmallVector Kills; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& MO = MI->getOperand(i); + 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 potiential to spill + // Get the used operands into registers. This has the potential to spill // incoming values if we are out of registers. Note that we completely // ignore physical register uses here. We assume that if an explicit // physical register is referenced by the instruction, that it is guaranteed // to be live-in, or the input is badly hosed. // - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) - if (MI->getOperand(i).opIsUse() && MI->getOperand(i).isVirtualRegister()){ - unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum(); - unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg); - MI->SetMachineOperandReg(i, PhysSrcReg); // Assign the input register + for (unsigned i = 0; i != MI->getNumOperands(); ++i) { + 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())) + MI = reloadVirtReg(MBB, MI, i); + } + + // If this instruction is the last user of this register, kill the + // value, freeing the register being used, so it doesn't need to be + // spilled to memory. + // + for (unsigned i = 0, e = Kills.size(); i != e; ++i) { + unsigned VirtReg = Kills[i]; + unsigned PhysReg = VirtReg; + if (MRegisterInfo::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); + PhysReg = PhysRegSlot; + PhysRegSlot = 0; + } else if (PhysRegsUsed[PhysReg] == -2) { + // Unallocatable register dead, ignore. + continue; + } else { + assert((!PhysRegsUsed[PhysReg] || PhysRegsUsed[PhysReg] == -1) && + "Silently clearing a virtual register?"); } - - if (!DisableKill) { - // If this instruction is the last user of anything in registers, kill the - // value, freeing the register being used, so it doesn't need to be - // spilled to memory. - // - for (LiveVariables::killed_iterator KI = LV->killed_begin(MI), - KE = LV->killed_end(MI); KI != KE; ++KI) { - unsigned VirtReg = KI->second; - unsigned PhysReg = VirtReg; - if (VirtReg >= MRegisterInfo::FirstVirtualRegister) { - std::map::iterator I = - Virt2PhysRegMap.find(VirtReg); - assert(I != Virt2PhysRegMap.end()); - PhysReg = I->second; - Virt2PhysRegMap.erase(I); - } - if (PhysReg) { - DEBUG(std::cerr << " Last use of " << RegInfo->getName(PhysReg) - << "[%reg" << VirtReg <<"], removing it from live set\n"); - // If the physical register was used, but there was no definition of - // the physical register (we are reading garbage), Live Variables will - // tell us that this is the last use of the register even though we - // don't know of anything in the register. No need to remove it. - if (VirtReg != PhysReg || PhysRegsUsed.count(PhysReg)) - removePhysReg(PhysReg); + if (PhysReg) { + DOUT << " Last use of " << RegInfo->getName(PhysReg) + << "[%reg" << VirtReg <<"], removing it from live set\n"; + removePhysReg(PhysReg); + for (const unsigned *AliasSet = RegInfo->getSubRegisters(PhysReg); + *AliasSet; ++AliasSet) { + if (PhysRegsUsed[*AliasSet] != -2) { + DOUT << " Last use of " + << RegInfo->getName(*AliasSet) + << "[%reg" << VirtReg <<"], removing it from live set\n"; + removePhysReg(*AliasSet); + } } } } // Loop over all of the operands of the instruction, spilling registers that // are defined, and marking explicit destinations in the PhysRegsUsed map. - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) - if ((MI->getOperand(i).opIsDefOnly() || - MI->getOperand(i).opIsDefAndUse()) && - MI->getOperand(i).isPhysicalRegister()) { - unsigned Reg = MI->getOperand(i).getAllocatedRegNum(); - spillPhysReg(MBB, I, Reg); // Spill any existing value in the reg + 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())) { + unsigned Reg = MO.getReg(); + if (PhysRegsUsed[Reg] == -2) continue; // Something like ESP. + // 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->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); + AddToPhysRegsUseOrder(Reg); + + for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); + *AliasSet; ++AliasSet) { + if (PhysRegsUsed[*AliasSet] != -2) { + MF->setPhysRegUsed(*AliasSet); + PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now + AddToPhysRegsUseOrder(*AliasSet); + } + } } + } // Loop over the implicit defs, spilling them as well. - if (const unsigned *ImplicitDefs = TID.ImplicitDefs) - for (unsigned i = 0; ImplicitDefs[i]; ++i) { - unsigned Reg = ImplicitDefs[i]; - spillPhysReg(MBB, I, Reg); - PhysRegsUseOrder.push_back(Reg); - PhysRegsUsed[Reg] = 0; // It is free and reserved now + if (TID.ImplicitDefs) { + for (const unsigned *ImplicitDefs = TID.ImplicitDefs; + *ImplicitDefs; ++ImplicitDefs) { + unsigned Reg = *ImplicitDefs; + if (PhysRegsUsed[Reg] != -2) { + spillPhysReg(MBB, MI, Reg, true); + AddToPhysRegsUseOrder(Reg); + PhysRegsUsed[Reg] = 0; // It is free and reserved now + } + MF->setPhysRegUsed(Reg); + for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); + *AliasSet; ++AliasSet) { + if (PhysRegsUsed[*AliasSet] != -2) { + AddToPhysRegsUseOrder(*AliasSet); + PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now + MF->setPhysRegUsed(*AliasSet); + } + } } + } + + SmallVector DeadDefs; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& MO = MI->getOperand(i); + if (MO.isRegister() && MO.isDead()) + DeadDefs.push_back(MO.getReg()); + } // Okay, we have allocated all of the source operands and spilled any values // that would be destroyed by defs of this instruction. Loop over the - // implicit defs and assign them to a register, spilling incoming values if + // explicit defs and assign them to a register, spilling incoming values if // we need to scavenge a register. // - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) - if ((MI->getOperand(i).opIsDefOnly() || MI->getOperand(i).opIsDefAndUse()) - && MI->getOperand(i).isVirtualRegister()) { - unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum(); + 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())) { + unsigned DestVirtReg = MO.getReg(); unsigned DestPhysReg; - // If DestVirtReg already has a value, forget about it. Why doesn't - // getReg do this right? - std::map::iterator DestI = - Virt2PhysRegMap.find(DestVirtReg); - if (DestI != Virt2PhysRegMap.end()) { - unsigned PhysReg = DestI->second; - Virt2PhysRegMap.erase(DestI); - removePhysReg(PhysReg); - } - - if (TM->getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) { - // must be same register number as the first operand - // This maps a = b + c into b += c, and saves b into a's spot - assert(MI->getOperand(1).isRegister() && - MI->getOperand(1).getAllocatedRegNum() && - MI->getOperand(1).opIsUse() && - "Two address instruction invalid!"); - DestPhysReg = MI->getOperand(1).getAllocatedRegNum(); - - liberatePhysReg(MBB, I, DestPhysReg); - assignVirtToPhysReg(DestVirtReg, DestPhysReg); - } else { - DestPhysReg = getReg(MBB, I, DestVirtReg); - } + // If DestVirtReg already has a value, use it. + if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) + DestPhysReg = getReg(MBB, MI, DestVirtReg); + MF->setPhysRegUsed(DestPhysReg); markVirtRegModified(DestVirtReg); - MI->SetMachineOperandReg(i, DestPhysReg); // Assign the output register + MI->getOperand(i).setReg(DestPhysReg); // Assign the output register } + } - if (!DisableKill) { - // If this instruction defines any registers that are immediately dead, - // kill them now. - // - for (LiveVariables::killed_iterator KI = LV->dead_begin(MI), - KE = LV->dead_end(MI); KI != KE; ++KI) { - unsigned VirtReg = KI->second; - unsigned PhysReg = VirtReg; - if (VirtReg >= MRegisterInfo::FirstVirtualRegister) { - std::map::iterator I = - Virt2PhysRegMap.find(VirtReg); - assert(I != Virt2PhysRegMap.end()); - PhysReg = I->second; - Virt2PhysRegMap.erase(I); - } + // If this instruction defines any registers that are immediately dead, + // kill them now. + // + for (unsigned i = 0, e = DeadDefs.size(); i != e; ++i) { + unsigned VirtReg = DeadDefs[i]; + unsigned PhysReg = VirtReg; + if (MRegisterInfo::isVirtualRegister(VirtReg)) { + unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); + PhysReg = PhysRegSlot; + assert(PhysReg != 0); + PhysRegSlot = 0; + } else if (PhysRegsUsed[PhysReg] == -2) { + // Unallocatable register dead, ignore. + continue; + } - if (PhysReg) { - DEBUG(std::cerr << " Register " << RegInfo->getName(PhysReg) - << " [%reg" << VirtReg - << "] is never used, removing it frame live list\n"); - removePhysReg(PhysReg); + if (PhysReg) { + DOUT << " Register " << RegInfo->getName(PhysReg) + << " [%reg" << VirtReg + << "] is never used, removing it frame live list\n"; + removePhysReg(PhysReg); + for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); + *AliasSet; ++AliasSet) { + if (PhysRegsUsed[*AliasSet] != -2) { + DOUT << " Register " << RegInfo->getName(*AliasSet) + << " [%reg" << *AliasSet + << "] is never used, removing it frame live list\n"; + removePhysReg(*AliasSet); + } } } } + + // 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); + MBB.erase(MI); + } } - // Rewind the iterator to point to the first flow control instruction... - const TargetInstrInfo &TII = TM->getInstrInfo(); - I = MBB.end(); - while (I != MBB.begin() && TII.isTerminatorInstr((*(I-1))->getOpcode())) - --I; + MachineBasicBlock::iterator MI = MBB.getFirstTerminator(); // Spill all physical registers holding virtual registers now. - while (!PhysRegsUsed.empty()) - spillVirtReg(MBB, I, PhysRegsUsed.begin()->second, - PhysRegsUsed.begin()->first); + for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) + if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) + if (unsigned VirtReg = PhysRegsUsed[i]) + spillVirtReg(MBB, MI, VirtReg, i); + else + removePhysReg(i); - for (std::map::iterator I = Virt2PhysRegMap.begin(), - E = Virt2PhysRegMap.end(); I != E; ++I) - std::cerr << "Register still mapped: " << I->first << " -> " - << I->second << "\n"; +#if 0 + // This checking code is very expensive. + bool AllOk = true; + for (unsigned i = MRegisterInfo::FirstVirtualRegister, + e = MF->getSSARegMap()->getLastVirtReg(); i <= e; ++i) + if (unsigned PR = Virt2PhysRegMap[i]) { + cerr << "Register still mapped: " << i << " -> " << PR << "\n"; + AllOk = false; + } + assert(AllOk && "Virtual registers still in phys regs?"); +#endif - assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?"); - assert(PhysRegsUseOrder.empty() && "Physical regs still allocated?"); + // Clear any physical register which appear live at the end of the basic + // block, but which do not hold any virtual registers. e.g., the stack + // pointer. + PhysRegsUseOrder.clear(); } /// runOnMachineFunction - Register allocate the whole function /// -bool RA::runOnMachineFunction(MachineFunction &Fn) { - DEBUG(std::cerr << "Machine Function " << "\n"); +bool RALocal::runOnMachineFunction(MachineFunction &Fn) { + DOUT << "Machine Function " << "\n"; MF = &Fn; TM = &Fn.getTarget(); RegInfo = TM->getRegisterInfo(); + LV = &getAnalysis(); + + PhysRegsUsed.assign(RegInfo->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); + for (unsigned i = 0, e = Allocable.size(); i != e; ++i) + if (!Allocable[i]) + PhysRegsUsed[i] = -2; // Mark the reg unallocable. + } - if (!DisableKill) - LV = &getAnalysis(); + // initialize the virtual->physical register map to have a 'null' + // mapping for all virtual registers + Virt2PhysRegMap.grow(MF->getSSARegMap()->getLastVirtReg()); // Loop over all of the basic blocks, eliminating virtual register references for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); @@ -646,10 +819,12 @@ bool RA::runOnMachineFunction(MachineFunction &Fn) { AllocateBasicBlock(*MBB); StackSlotForVirtReg.clear(); + PhysRegsUsed.clear(); VirtRegModified.clear(); + Virt2PhysRegMap.clear(); return true; } -Pass *createLocalRegisterAllocator() { - return new RA(); +FunctionPass *llvm::createLocalRegisterAllocator() { + return new RALocal(); }