diff options
| -rw-r--r-- | lib/CodeGen/RegAllocFast.cpp | 1169 | ||||
| -rw-r--r-- | test/CodeGen/X86/2010-05-05-LocalAllocEarlyClobber.ll | 4 | ||||
| -rw-r--r-- | test/CodeGen/X86/2010-05-06-LocalInlineAsmClobber.ll | 3 |
3 files changed, 473 insertions, 703 deletions
diff --git a/lib/CodeGen/RegAllocFast.cpp b/lib/CodeGen/RegAllocFast.cpp index ab5e103..488f630 100644 --- a/lib/CodeGen/RegAllocFast.cpp +++ b/lib/CodeGen/RegAllocFast.cpp @@ -18,7 +18,6 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/RegAllocRegistry.h" #include "llvm/Target/TargetInstrInfo.h" @@ -57,65 +56,44 @@ namespace { // values are spilled. IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg; - // Virt2PhysRegMap - This map contains entries for each virtual register + // Virt2PhysMap - This map contains entries for each virtual register // that is currently available in a physical register. - IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap; + DenseMap<unsigned, unsigned> Virt2PhysMap; - unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) { - return Virt2PhysRegMap[VirtReg]; - } + // RegState - Track the state of a physical register. + enum RegState { + // A disabled register is not available for allocation, but an alias may + // be in use. A register can only be moved out of the disabled state if + // all aliases are disabled. + regDisabled, + + // A free register is not currently in use and can be allocated + // immediately without checking aliases. + regFree, + + // A reserved register has been assigned expolicitly (e.g., setting up a + // call parameter), and it remains reserved until it is used. + regReserved - // 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::vector<int> PhysRegsUsed; + // A register state may also be a virtual register number, indication that + // the physical register is currently allocated to a virtual register. In + // that case, Virt2PhysMap contains the inverse mapping. + }; + + // PhysRegState - One of the RegState enums, or a virtreg. + std::vector<unsigned> PhysRegState; // UsedInInstr - BitVector of physregs that are used in the current // instruction, and so cannot be allocated. BitVector UsedInInstr; - // Virt2LastUseMap - This maps each virtual register to its last use - // (MachineInstr*, operand index pair). - IndexedMap<std::pair<MachineInstr*, unsigned>, VirtReg2IndexFunctor> - Virt2LastUseMap; + // PhysRegDirty - A bit is set for each physreg that holds a dirty virtual + // register. Bits for physregs that are not mapped to a virtual register are + // invalid. + BitVector PhysRegDirty; - std::pair<MachineInstr*,unsigned>& 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. - // - BitVector VirtRegModified; - - // UsedInMultipleBlocks - Tracks whether a particular register is used in - // more than one block. - BitVector UsedInMultipleBlocks; - - void markVirtRegModified(unsigned Reg, bool Val = true) { - assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - Reg -= TargetRegisterInfo::FirstVirtualRegister; - if (Val) - VirtRegModified.set(Reg); - else - VirtRegModified.reset(Reg); - } - - bool isVirtRegModified(unsigned Reg) const { - assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - assert(Reg - TargetRegisterInfo::FirstVirtualRegister < - VirtRegModified.size() && "Illegal virtual register!"); - return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister]; - } + // ReservedRegs - vector of reserved physical registers. + BitVector ReservedRegs; public: virtual const char *getPassName() const { @@ -124,104 +102,32 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); - AU.addRequired<LiveVariables>(); AU.addRequiredID(PHIEliminationID); AU.addRequiredID(TwoAddressInstructionPassID); MachineFunctionPass::getAnalysisUsage(AU); } private: - /// runOnMachineFunction - Register allocate the whole function bool runOnMachineFunction(MachineFunction &Fn); - - /// AllocateBasicBlock - Register allocate the specified basic block. void AllocateBasicBlock(MachineBasicBlock &MBB); - - - /// areRegsEqual - This method returns true if the specified registers are - /// related to each other. To do this, it checks to see if they are equal - /// or if the first register is in the alias set of the second register. - /// - bool areRegsEqual(unsigned R1, unsigned R2) const { - if (R1 == R2) return true; - for (const unsigned *AliasSet = TRI->getAliasSet(R2); - *AliasSet; ++AliasSet) { - if (*AliasSet == R1) return true; - } - return false; - } - - /// getStackSpaceFor - This returns the frame index of the specified virtual - /// register on the stack, allocating space if necessary. int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); - - /// removePhysReg - This method marks the specified physical register as no - /// longer being in use. - /// - void removePhysReg(unsigned PhysReg); - - /// spillVirtReg - This method spills the value specified by PhysReg into - /// the virtual register slot specified by VirtReg. It then updates the RA - /// data structures to indicate the fact that PhysReg is now available. - /// + void killVirtReg(unsigned VirtReg); 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. If OnlyVirtRegs is set to - /// true, then the request is ignored if the physical register does not - /// contain a virtual register. - /// + unsigned VirtReg, bool isKill); + void killPhysReg(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 - /// register must not be used for anything else when this is called. - /// + unsigned PhysReg, bool isKill); void assignVirtToPhysReg(unsigned VirtReg, 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... - /// - bool isPhysRegAvailable(unsigned PhysReg) const; - - /// isPhysRegSpillable - Can PhysReg be freed by spilling? - bool isPhysRegSpillable(unsigned PhysReg) const; - - /// getFreeReg - Look to see if there is a free register available in the - /// 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. If NoFree is true, that means the caller knows there isn't - /// a free register, do not call getFreeReg(). - unsigned getReg(MachineBasicBlock &MBB, MachineInstr *MI, - unsigned VirtReg, bool NoFree = false); - - /// reloadVirtReg - This method transforms the 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: PhysReg if that is an available physical - /// register, otherwise any physical register of the right class. - /// 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. - /// - MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, - unsigned OpNum, SmallSet<unsigned, 4> &RRegs, - unsigned PhysReg); - - void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, - unsigned PhysReg); + unsigned allocVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned VirtReg); + unsigned defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned VirtReg); + unsigned reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned VirtReg); + void reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned PhysReg); + void spillAll(MachineBasicBlock &MBB, MachineInstr *MI); + void setPhysReg(MachineOperand &MO, unsigned PhysReg); }; char RAFast::ID = 0; } @@ -243,676 +149,544 @@ int RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { return FrameIdx; } - -/// removePhysReg - This method marks the specified physical register as no -/// longer being in use. -/// -void RAFast::removePhysReg(unsigned PhysReg) { - PhysRegsUsed[PhysReg] = -1; // PhyReg no longer used +/// killVirtReg - Mark virtreg as no longer available. +void RAFast::killVirtReg(unsigned VirtReg) { + assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && + "killVirtReg needs a virtual register"); + DEBUG(dbgs() << " Killing %reg" << VirtReg << "\n"); + DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.find(VirtReg); + if (i == Virt2PhysMap.end()) return; + unsigned PhysReg = i->second; + assert(PhysRegState[PhysReg] == VirtReg && "Broken RegState mapping"); + PhysRegState[PhysReg] = regFree; + Virt2PhysMap.erase(i); } - -/// spillVirtReg - This method spills the value specified by PhysReg into the -/// virtual register slot specified by VirtReg. It then updates the RA data -/// structures to indicate the fact that PhysReg is now available. -/// +/// spillVirtReg - This method spills the value specified by VirtReg into the +/// corresponding stack slot if needed. If isKill is set, the register is also +/// killed. void RAFast::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."); - DEBUG(dbgs() << " Spilling register " << TRI->getName(PhysReg) - << " containing %reg" << VirtReg); - - if (!isVirtRegModified(VirtReg)) { - DEBUG(dbgs() << " which has not been modified, so no store necessary!"); - std::pair<MachineInstr*, unsigned> &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. + MachineBasicBlock::iterator I, + unsigned VirtReg, bool isKill) { + assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && + "Spilling a physical register is illegal!"); + DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.find(VirtReg); + assert(i != Virt2PhysMap.end() && "Spilling unmapped virtual register"); + unsigned PhysReg = i->second; + assert(PhysRegState[PhysReg] == VirtReg && "Broken RegState mapping"); + + if (PhysRegDirty.test(PhysReg)) { + PhysRegDirty.reset(PhysReg); + DEBUG(dbgs() << " Spilling register " << TRI->getName(PhysReg) + << " containing %reg" << VirtReg); const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); int FrameIndex = getStackSpaceFor(VirtReg, RC); - DEBUG(dbgs() << " to stack slot #" << FrameIndex); - // 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->readsRegister(PhysReg)); + DEBUG(dbgs() << " to stack slot #" << FrameIndex << "\n"); TII->storeRegToStackSlot(MBB, I, PhysReg, isKill, FrameIndex, RC, TRI); ++NumStores; // Update statistics } - getVirt2PhysRegMapSlot(VirtReg) = 0; // VirtReg no longer available - - DEBUG(dbgs() << '\n'); - removePhysReg(PhysReg); + if (isKill) { + PhysRegState[PhysReg] = regFree; + Virt2PhysMap.erase(i); + } } +/// spillAll - Spill all dirty virtregs without killing them. +void RAFast::spillAll(MachineBasicBlock &MBB, MachineInstr *MI) { + SmallVector<unsigned, 16> Dirty; + for (DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.begin(), + e = Virt2PhysMap.end(); i != e; ++i) + if (PhysRegDirty.test(i->second)) + Dirty.push_back(i->first); + for (unsigned i = 0, e = Dirty.size(); i != e; ++i) + spillVirtReg(MBB, MI, Dirty[i], false); +} -/// spillPhysReg - This method spills the specified physical register into 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 RAFast::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); +/// killPhysReg - Kill any virtual register aliased by PhysReg. +void RAFast::killPhysReg(unsigned PhysReg) { + // Fast path for the normal case. + switch (unsigned VirtReg = PhysRegState[PhysReg]) { + case regDisabled: + break; + case regFree: + return; + case regReserved: + PhysRegState[PhysReg] = regFree; + return; + default: + killVirtReg(VirtReg); return; } - // If the selected register aliases any other registers, we must make - // sure that one of the aliases isn't alive. - for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); - *AliasSet; ++AliasSet) { - if (PhysRegsUsed[*AliasSet] == -1 || // Spill aliased register. - PhysRegsUsed[*AliasSet] == -2) // If allocatable. - continue; - - if (PhysRegsUsed[*AliasSet]) - spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet); + // This is a disabled register, we have to check aliases. + for (const unsigned *AS = TRI->getAliasSet(PhysReg); + unsigned Alias = *AS; ++AS) { + switch (unsigned VirtReg = PhysRegState[Alias]) { + case regDisabled: + case regFree: + break; + case regReserved: + PhysRegState[Alias] = regFree; + break; + default: + killVirtReg(VirtReg); + break; + } } } +/// spillPhysReg - Spill any dirty virtual registers that aliases PhysReg. If +/// isKill is set, they are also killed. +void RAFast::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned PhysReg, bool isKill) { + switch (unsigned VirtReg = PhysRegState[PhysReg]) { + case regDisabled: + break; + case regFree: + return; + case regReserved: + if (isKill) + PhysRegState[PhysReg] = regFree; + return; + default: + spillVirtReg(MBB, MI, VirtReg, isKill); + return; + } + + // This is a disabled register, we have to check aliases. + for (const unsigned *AS = TRI->getAliasSet(PhysReg); + unsigned Alias = *AS; ++AS) { + switch (unsigned VirtReg = PhysRegState[Alias]) { + case regDisabled: + case regFree: + break; + case regReserved: + if (isKill) + PhysRegState[Alias] = regFree; + break; + default: + spillVirtReg(MBB, MI, VirtReg, isKill); + break; + } + } +} /// assignVirtToPhysReg - This method updates local state so that we know /// that PhysReg is the proper container for VirtReg now. The physical /// register must not be used for anything else when this is called. /// void RAFast::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; - UsedInInstr.set(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... -/// -bool RAFast::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 = TRI->getAliasSet(PhysReg); - *AliasSet; ++AliasSet) - if (PhysRegsUsed[*AliasSet] >= 0) // Aliased register in use? - return false; // Can't use this reg then. - return true; -} - -/// isPhysRegSpillable - Return true if the specified physical register can be -/// spilled for use in the current instruction. -/// -bool RAFast::isPhysRegSpillable(unsigned PhysReg) const { - // Test that PhysReg and all aliases are either free or assigned to a VirtReg - // that is not used in the instruction. - if (PhysRegsUsed[PhysReg] != -1 && - (PhysRegsUsed[PhysReg] <= 0 || UsedInInstr.test(PhysReg))) - return false; - - for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); - *AliasSet; ++AliasSet) - if (PhysRegsUsed[*AliasSet] != -1 && - (PhysRegsUsed[*AliasSet] <= 0 || UsedInInstr.test(*AliasSet))) - return false; - return true; + DEBUG(dbgs() << " Assigning %reg" << VirtReg << " to " + << TRI->getName(PhysReg) << "\n"); + Virt2PhysMap.insert(std::make_pair(VirtReg, PhysReg)); + PhysRegState[PhysReg] = VirtReg; } +/// allocVirtReg - Allocate a physical register for VirtReg. +unsigned RAFast::allocVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned VirtReg) { + const unsigned spillCost = 100; + assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && + "Can only allocate virtual registers"); -/// getFreeReg - Look to see if there is a free register available in the -/// specified register class. If not, return 0. -/// -unsigned RAFast::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); - TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF); - - for (; RI != RE; ++RI) - if (isPhysRegAvailable(*RI)) { // Is reg unused? - assert(*RI != 0 && "Cannot use register!"); - return *RI; // Found an unused register! + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); + TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF); + TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF); + + // First try to find a completely free register. + unsigned BestCost = 0, BestReg = 0; + bool hasDisabled = false; + for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { + unsigned PhysReg = *I; + switch(PhysRegState[PhysReg]) { + case regDisabled: + hasDisabled = true; + case regReserved: + continue; + case regFree: + if (!UsedInInstr.test(PhysReg)) { + assignVirtToPhysReg(VirtReg, PhysReg); + return PhysReg; + } + continue; + default: + // Grab the first spillable register we meet. + if (!BestReg && !UsedInInstr.test(PhysReg)) { + BestReg = PhysReg; + BestCost = PhysRegDirty.test(PhysReg) ? spillCost : 1; + } + continue; } - return 0; -} - + } -/// 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 RAFast::getReg(MachineBasicBlock &MBB, MachineInstr *I, - unsigned VirtReg, bool NoFree) { - const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); + DEBUG(dbgs() << " Allocating %reg" << VirtReg << " from " << RC->getName() + << " candidate=" << TRI->getName(BestReg) << "\n"); - // First check to see if we have a free register of the requested type... - unsigned PhysReg = NoFree ? 0 : getFreeReg(RC); + // Try to extend the working set for RC if there were any disabled registers. + if (hasDisabled && (!BestReg || BestCost >= spillCost)) { + for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { + unsigned PhysReg = *I; + if (PhysRegState[PhysReg] != regDisabled || UsedInInstr.test(PhysReg)) + continue; - if (PhysReg != 0) { - // Assign the register. - assignVirtToPhysReg(VirtReg, PhysReg); - return PhysReg; + // Calculate the cost of bringing PhysReg into the working set. + unsigned Cost=0; + bool Impossible = false; + for (const unsigned *AS = TRI->getAliasSet(PhysReg); + unsigned Alias = *AS; ++AS) { + if (UsedInInstr.test(Alias)) { + Impossible = true; + break; + } + switch (PhysRegState[Alias]) { + case regDisabled: + break; + case regReserved: + Impossible = true; + break; + case regFree: + Cost++; + break; + default: + Cost += PhysRegDirty.test(Alias) ? spillCost : 1; + break; + } + } + if (Impossible) continue; + DEBUG(dbgs() << " - candidate " << TRI->getName(PhysReg) + << " cost=" << Cost << "\n"); + if (!BestReg || Cost < BestCost) { + BestReg = PhysReg; + BestCost = Cost; + if (Cost < spillCost) break; + } + } } - // If we didn't find an unused register, scavenge one now! Don't be fancy, - // just grab the first possible register. - TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF); - TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF); - - for (; RI != RE; ++RI) - if (isPhysRegSpillable(*RI)) { - PhysReg = *RI; - break; + if (BestReg) { + // BestCost is 0 when all aliases are already disabled. + if (BestCost) { + if (PhysRegState[BestReg] != regDisabled) + spillVirtReg(MBB, MI, PhysRegState[BestReg], true); + else { + MF->getRegInfo().setPhysRegUsed(BestReg); + // Make sure all aliases are disabled. + for (const unsigned *AS = TRI->getAliasSet(BestReg); + unsigned Alias = *AS; ++AS) { + MF->getRegInfo().setPhysRegUsed(Alias); + switch (PhysRegState[Alias]) { + case regDisabled: + continue; + case regFree: + PhysRegState[Alias] = regDisabled; + break; + default: + spillVirtReg(MBB, MI, PhysRegState[Alias], true); + PhysRegState[Alias] = regDisabled; + break; + } + } + } } + assignVirtToPhysReg(VirtReg, BestReg); + return BestReg; + } - assert(PhysReg && "Physical register not assigned!?!?"); - spillPhysReg(MBB, I, PhysReg); - assignVirtToPhysReg(VirtReg, PhysReg); - return PhysReg; + // Nothing we can do. + std::string msg; + raw_string_ostream Msg(msg); + Msg << "Ran out of registers during register allocation!"; + if (MI->isInlineAsm()) { + Msg << "\nPlease check your inline asm statement for " + << "invalid constraints:\n"; + MI->print(Msg, TM); + } + report_fatal_error(Msg.str()); + return 0; } +/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. +unsigned RAFast::defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned VirtReg) { + assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && + "Not a virtual register"); + unsigned PhysReg = Virt2PhysMap.lookup(VirtReg); + if (!PhysReg) + PhysReg = allocVirtReg(MBB, MI, VirtReg); + UsedInInstr.set(PhysReg); + PhysRegDirty.set(PhysReg); + return PhysReg; +} -/// reloadVirtReg - This method transforms the 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: PhysReg if that is an available physical register, otherwise any -/// 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. -/// -MachineInstr *RAFast::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, - unsigned OpNum, - SmallSet<unsigned, 4> &ReloadedRegs, - unsigned PhysReg) { - unsigned VirtReg = MI->getOperand(OpNum).getReg(); - - // If the virtual register is already available, just update the instruction - // and return. - if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) { - MI->getOperand(OpNum).setReg(PR); // Assign the input register - if (!MI->isDebugValue()) { - // Do not do these for DBG_VALUE as they can affect codegen. - UsedInInstr.set(PR); - getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum); - } - return MI; +/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. +unsigned RAFast::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned VirtReg) { + assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && + "Not a virtual register"); + unsigned PhysReg = Virt2PhysMap.lookup(VirtReg); + if (!PhysReg) { + PhysReg = allocVirtReg(MBB, MI, VirtReg); + PhysRegDirty.reset(PhysReg); + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); + int FrameIndex = getStackSpaceFor(VirtReg, RC); + DEBUG(dbgs() << " Reloading %reg" << VirtReg << " into " + << TRI->getName(PhysReg) << "\n"); + TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC, TRI); + ++NumLoads; } + UsedInInstr.set(PhysReg); + return PhysReg; +} - // 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->getRegInfo().getRegClass(VirtReg); - // If we already have a PhysReg (this happens when the instruction is a - // reg-to-reg copy with a PhysReg destination) use that. - if (!PhysReg || !TargetRegisterInfo::isPhysicalRegister(PhysReg) || - !isPhysRegAvailable(PhysReg)) - PhysReg = getFreeReg(RC); - int FrameIndex = getStackSpaceFor(VirtReg, RC); - - if (PhysReg) { // Register is available, allocate it! - assignVirtToPhysReg(VirtReg, PhysReg); - } else { // No registers available. - // 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, true); +/// reservePhysReg - Mark PhysReg as reserved. This is very similar to +/// defineVirtReg except the physreg is reverved instead of allocated. +void RAFast::reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI, + unsigned PhysReg) { + switch (unsigned VirtReg = PhysRegState[PhysReg]) { + case regDisabled: + break; + case regFree: + PhysRegState[PhysReg] = regReserved; + return; + case regReserved: + return; + default: + spillVirtReg(MBB, MI, VirtReg, true); + PhysRegState[PhysReg] = regReserved; + return; } - markVirtRegModified(VirtReg, false); // Note that this reg was just reloaded - - DEBUG(dbgs() << " Reloading %reg" << VirtReg << " into " - << TRI->getName(PhysReg) << "\n"); - - // Add move instruction(s) - TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC, TRI); - ++NumLoads; // Update statistics - - MF->getRegInfo().setPhysRegUsed(PhysReg); - MI->getOperand(OpNum).setReg(PhysReg); // Assign the input register - getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum); - - if (!ReloadedRegs.insert(PhysReg)) { - std::string msg; - raw_string_ostream Msg(msg); - Msg << "Ran out of registers during register allocation!"; - if (MI->isInlineAsm()) { - Msg << "\nPlease check your inline asm statement for invalid " - << "constraints:\n"; - MI->print(Msg, TM); - } - report_fatal_error(Msg.str()); - } - for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg); - *SubRegs; ++SubRegs) { - if (ReloadedRegs.insert(*SubRegs)) continue; - - std::string msg; - raw_string_ostream Msg(msg); - Msg << "Ran out of registers during register allocation!"; - if (MI->isInlineAsm()) { - Msg << "\nPlease check your inline asm statement for invalid " - << "constraints:\n"; - MI->print(Msg, TM); + // This is a disabled register, disable all aliases. + for (const unsigned *AS = TRI->getAliasSet(PhysReg); + unsigned Alias = *AS; ++AS) { + switch (unsigned VirtReg = PhysRegState[Alias]) { + case regDisabled: + case regFree: + break; + case regReserved: + // is a super register already reserved? + if (TRI->isSuperRegister(PhysReg, Alias)) + return; + break; + default: + spillVirtReg(MBB, MI, VirtReg, true); + break; } - report_fatal_error(Msg.str()); + PhysRegState[Alias] = regDisabled; + MF->getRegInfo().setPhysRegUsed(Alias); } - - return MI; + PhysRegState[PhysReg] = regReserved; + MF->getRegInfo().setPhysRegUsed(PhysReg); } -/// 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.isReg() && 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.isReg() && MO.getReg() == Reg && MO.isImplicit() && - !MO.isDef() && MO.isKill()) - return true; - } - return false; +// setPhysReg - Change MO the refer the PhysReg, considering subregs. +void RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) { + if (unsigned Idx = MO.getSubReg()) { + MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, Idx) : 0); + MO.setSubReg(0); + } else + MO.setReg(PhysReg); } void RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) { - // loop over each instruction - MachineBasicBlock::iterator MII = MBB.begin(); + DEBUG(dbgs() << "\nBB#" << MBB.getNumber() << ", "<< MBB.getName() << "\n"); - DEBUG({ - const BasicBlock *LBB = MBB.getBasicBlock(); - if (LBB) - dbgs() << "\nStarting RegAlloc of BB: " << LBB->getName(); - }); + PhysRegState.assign(TRI->getNumRegs(), regDisabled); + assert(Virt2PhysMap.empty() && "Mapping not cleared form last block?"); + PhysRegDirty.reset(); - // Add live-in registers as active. + MachineBasicBlock::iterator MII = MBB.begin(); + + // Add live-in registers as live. for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(), - E = MBB.livein_end(); I != E; ++I) { - unsigned Reg = *I; - MF->getRegInfo().setPhysRegUsed(Reg); - PhysRegsUsed[Reg] = 0; // It is free and reserved now - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); - *SubRegs; ++SubRegs) { - if (PhysRegsUsed[*SubRegs] == -2) continue; - PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now - MF->getRegInfo().setPhysRegUsed(*SubRegs); - } - } + E = MBB.livein_end(); I != E; ++I) + reservePhysReg(MBB, MII, *I); + + SmallVector<unsigned, 8> VirtKills, PhysKills, PhysDefs; // Otherwise, sequentially allocate each instruction in the MBB. while (MII != MBB.end()) { MachineInstr *MI = MII++; const TargetInstrDesc &TID = MI->getDesc(); DEBUG({ - dbgs() << "\nStarting RegAlloc of: " << *MI; - dbgs() << " Regs have values: "; - for (unsigned i = 0; i != TRI->getNumRegs(); ++i) - if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) - dbgs() << "[" << TRI->getName(i) - << ",%reg" << PhysRegsUsed[i] << "] "; + dbgs() << "\nStarting RegAlloc of: " << *MI << "Working set:"; + for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { + if (PhysRegState[Reg] == regDisabled) continue; + dbgs() << " " << TRI->getName(Reg); + switch(PhysRegState[Reg]) { + case regFree: + break; + case regReserved: + dbgs() << "(resv)"; + break; + default: + dbgs() << "=%reg" << PhysRegState[Reg]; + if (PhysRegDirty.test(Reg)) + dbgs() << "*"; + assert(Virt2PhysMap.lookup(PhysRegState[Reg]) == Reg && + "Bad inverse map"); + break; + } + } dbgs() << '\n'; + // Check that Virt2PhysMap is the inverse. + for (DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.begin(), + e = Virt2PhysMap.end(); i != e; ++i) { + assert(TargetRegisterInfo::isVirtualRegister(i->first) && + "Bad map key"); + assert(TargetRegisterInfo::isPhysicalRegister(i->second) && + "Bad map value"); + assert(PhysRegState[i->second] == i->first && "Bad inverse map"); + } }); - // Track registers used by instruction. - UsedInInstr.reset(); - - // Determine whether this is a copy instruction. The cases where the - // source or destination are phys regs are handled specially. - unsigned SrcCopyReg, DstCopyReg, SrcCopySubReg, DstCopySubReg; - unsigned SrcCopyPhysReg = 0U; - bool isCopy = TII->isMoveInstr(*MI, SrcCopyReg, DstCopyReg, - SrcCopySubReg, DstCopySubReg); - if (isCopy && SrcCopySubReg == 0 && DstCopySubReg == 0 && - TargetRegisterInfo::isVirtualRegister(SrcCopyReg)) - SrcCopyPhysReg = getVirt2PhysRegMapSlot(SrcCopyReg); - - // Loop over the implicit uses, making sure they don't get reallocated. - if (TID.ImplicitUses) { - for (const unsigned *ImplicitUses = TID.ImplicitUses; - *ImplicitUses; ++ImplicitUses) - UsedInInstr.set(*ImplicitUses); - } - - SmallVector<unsigned, 8> Kills; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isKill()) continue; - - 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()); - } - - // If any physical regs are earlyclobber, spill any value they might - // have in them, then mark them unallocatable. - // If any virtual regs are earlyclobber, allocate them now (before - // freeing inputs that are killed). - if (MI->isInlineAsm()) { + // Debug values are not allowed to change codegen in any way. + if (MI->isDebugValue()) { for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isDef() || !MO.isEarlyClobber() || - !MO.getReg()) - continue; - - if (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->getRegInfo().setPhysRegUsed(DestPhysReg); - markVirtRegModified(DestVirtReg); - getVirtRegLastUse(DestVirtReg) = - std::make_pair((MachineInstr*)0, 0); - DEBUG(dbgs() << " Assigning " << TRI->getName(DestPhysReg) - << " to %reg" << DestVirtReg << "\n"); - MO.setReg(DestPhysReg); // Assign the earlyclobber register - } else { - 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->getRegInfo().setPhysRegUsed(Reg); - spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg - PhysRegsUsed[Reg] = 0; // It is free and reserved now - - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); - *SubRegs; ++SubRegs) { - if (PhysRegsUsed[*SubRegs] == -2) continue; - MF->getRegInfo().setPhysRegUsed(*SubRegs); - PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now - } - } + if (!MO.isReg()) continue; + unsigned Reg = MO.getReg(); + if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; + // This may be 0 if the register is currently spilled. Tough. + setPhysReg(MO, Virt2PhysMap.lookup(Reg)); } + // Next instruction. + continue; } - // If a DBG_VALUE says something is located in a spilled register, - // change the DBG_VALUE to be undef, which prevents the register - // from being reloaded here. Doing that would change the generated - // code, unless another use immediately follows this instruction. - if (MI->isDebugValue() && - MI->getNumOperands()==3 && MI->getOperand(0).isReg()) { - unsigned VirtReg = MI->getOperand(0).getReg(); - if (VirtReg && TargetRegisterInfo::isVirtualRegister(VirtReg) && - !getVirt2PhysRegMapSlot(VirtReg)) - MI->getOperand(0).setReg(0U); - } + // Track registers used by instruction. + UsedInInstr.reset(); + PhysDefs.clear(); - // 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. - // - SmallSet<unsigned, 4> ReloadedRegs; - for (unsigned i = 0; i != MI->getNumOperands(); ++i) { + // First scan. + // Mark physreg uses and early clobbers as used. + // Collect PhysKills. + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - // here we are looking for only used operands (never def&use) - if (MO.isReg() && !MO.isDef() && MO.getReg() && !MO.isImplicit() && - TargetRegisterInfo::isVirtualRegister(MO.getReg())) - MI = reloadVirtReg(MBB, MI, i, ReloadedRegs, - isCopy ? DstCopyReg : 0); - } + if (!MO.isReg()) continue; - // 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 (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); - 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?"); - } + // FIXME: For now, don't trust kill flags + if (MO.isUse()) MO.setIsKill(false); - if (!PhysReg) continue; - - DEBUG(dbgs() << " Last use of " << TRI->getName(PhysReg) - << "[%reg" << VirtReg <<"], removing it from live set\n"); - removePhysReg(PhysReg); - for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg); - *SubRegs; ++SubRegs) { - if (PhysRegsUsed[*SubRegs] != -2) { - DEBUG(dbgs() << " Last use of " - << TRI->getName(*SubRegs) << "[%reg" << VirtReg - <<"], removing it from live set\n"); - removePhysReg(*SubRegs); - } + unsigned Reg = MO.getReg(); + if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg) || + ReservedRegs.test(Reg)) continue; + if (MO.isUse()) { + PhysKills.push_back(Reg); // Any clean physreg use is a kill. + UsedInInstr.set(Reg); + } else if (MO.isEarlyClobber()) { + spillPhysReg(MBB, MI, Reg, true); + UsedInInstr.set(Reg); + PhysDefs.push_back(Reg); } } - // Track registers defined by instruction. - UsedInInstr.reset(); - - // Loop over all of the operands of the instruction, spilling registers that - // are defined, and marking explicit destinations in the PhysRegsUsed map. + // Second scan. + // Allocate virtreg uses and early clobbers. + // Collect VirtKills for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isDef() || MO.isImplicit() || !MO.getReg() || - MO.isEarlyClobber() || - !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) - continue; - + if (!MO.isReg()) continue; 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->getRegInfo().setPhysRegUsed(Reg); - spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg - PhysRegsUsed[Reg] = 0; // It is free and reserved now - - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); - *SubRegs; ++SubRegs) { - if (PhysRegsUsed[*SubRegs] == -2) continue; - - MF->getRegInfo().setPhysRegUsed(*SubRegs); - PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now + if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; + if (MO.isUse()) { + setPhysReg(MO, reloadVirtReg(MBB, MI, Reg)); + if (MO.isKill()) + VirtKills.push_back(Reg); + } else if (MO.isEarlyClobber()) { + unsigned PhysReg = defineVirtReg(MBB, MI, Reg); + setPhysReg(MO, PhysReg); + PhysDefs.push_back(PhysReg); } } - // Loop over the implicit defs, spilling them as well. - if (TID.ImplicitDefs) { - for (const unsigned *ImplicitDefs = TID.ImplicitDefs; - *ImplicitDefs; ++ImplicitDefs) { - unsigned Reg = *ImplicitDefs; - if (PhysRegsUsed[Reg] != -2) { - spillPhysReg(MBB, MI, Reg, true); - PhysRegsUsed[Reg] = 0; // It is free and reserved now - } - MF->getRegInfo().setPhysRegUsed(Reg); - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); - *SubRegs; ++SubRegs) { - if (PhysRegsUsed[*SubRegs] == -2) continue; + // Process virtreg kills + for (unsigned i = 0, e = VirtKills.size(); i != e; ++i) + killVirtReg(VirtKills[i]); + VirtKills.clear(); - PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now - MF->getRegInfo().setPhysRegUsed(*SubRegs); - } - } - } + // Process physreg kills + for (unsigned i = 0, e = PhysKills.size(); i != e; ++i) + killPhysReg(PhysKills[i]); + PhysKills.clear(); - SmallVector<unsigned, 8> DeadDefs; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isDead()) - DeadDefs.push_back(MO.getReg()); + // Track registers defined by instruction - early clobbers at this point. + UsedInInstr.reset(); + for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { + unsigned PhysReg = PhysDefs[i]; + UsedInInstr.set(PhysReg); + for (const unsigned *AS = TRI->getAliasSet(PhysReg); + unsigned Alias = *AS; ++AS) + UsedInInstr.set(Alias); } - // 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 - // explicit defs and assign them to a register, spilling incoming values if - // we need to scavenge a register. - // + // Third scan. + // Allocate defs and collect dead defs. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isDef() || !MO.getReg() || - MO.isEarlyClobber() || - !TargetRegisterInfo::isVirtualRegister(MO.getReg())) - continue; + if (!MO.isReg() || !MO.isDef() || !MO.getReg()) continue; + unsigned Reg = MO.getReg(); - unsigned DestVirtReg = MO.getReg(); - unsigned DestPhysReg; - - // If DestVirtReg already has a value, use it. - if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) { - // If this is a copy try to reuse the input as the output; - // that will make the copy go away. - // If this is a copy, the source reg is a phys reg, and - // that reg is available, use that phys reg for DestPhysReg. - // If this is a copy, the source reg is a virtual reg, and - // the phys reg that was assigned to that virtual reg is now - // available, use that phys reg for DestPhysReg. (If it's now - // available that means this was the last use of the source.) - if (isCopy && - TargetRegisterInfo::isPhysicalRegister(SrcCopyReg) && - isPhysRegAvailable(SrcCopyReg)) { - DestPhysReg = SrcCopyReg; - assignVirtToPhysReg(DestVirtReg, DestPhysReg); - } else if (isCopy && - TargetRegisterInfo::isVirtualRegister(SrcCopyReg) && - SrcCopyPhysReg && isPhysRegAvailable(SrcCopyPhysReg) && - MF->getRegInfo().getRegClass(DestVirtReg)-> - contains(SrcCopyPhysReg)) { - DestPhysReg = SrcCopyPhysReg; - assignVirtToPhysReg(DestVirtReg, DestPhysReg); - } else - DestPhysReg = getReg(MBB, MI, DestVirtReg); + if (TargetRegisterInfo::isPhysicalRegister(Reg)) { + if (ReservedRegs.test(Reg)) continue; + if (MO.isImplicit()) + spillPhysReg(MBB, MI, Reg, true); + else + reservePhysReg(MBB, MI, Reg); + if (MO.isDead()) + PhysKills.push_back(Reg); + continue; } - MF->getRegInfo().setPhysRegUsed(DestPhysReg); - markVirtRegModified(DestVirtReg); - getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0); - DEBUG(dbgs() << " Assigning " << TRI->getName(DestPhysReg) - << " to %reg" << DestVirtReg << "\n"); - MO.setReg(DestPhysReg); // Assign the output register - UsedInInstr.set(DestPhysReg); + if (MO.isDead()) + VirtKills.push_back(Reg); + setPhysReg(MO, defineVirtReg(MBB, MI, Reg)); } - // 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 (TargetRegisterInfo::isVirtualRegister(VirtReg)) { - unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); - PhysReg = PhysRegSlot; - assert(PhysReg != 0); - PhysRegSlot = 0; - } else if (PhysRegsUsed[PhysReg] == -2) { - // Unallocatable register dead, ignore. - continue; - } else if (!PhysReg) - continue; - - DEBUG(dbgs() << " Register " << TRI->getName(PhysReg) - << " [%reg" << VirtReg - << "] is never used, removing it from live set\n"); - removePhysReg(PhysReg); - for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); - *AliasSet; ++AliasSet) { - if (PhysRegsUsed[*AliasSet] != -2) { - DEBUG(dbgs() << " Register " << TRI->getName(*AliasSet) - << " [%reg" << *AliasSet - << "] is never used, removing it from live set\n"); - removePhysReg(*AliasSet); - } - } + // Spill all dirty virtregs before a call, in case of an exception. + if (TID.isCall()) { + DEBUG(dbgs() << " Spilling remaining registers before call.\n"); + spillAll(MBB, MI); } - // Finally, if this is a noop copy instruction, zap it. (Except that if - // the copy is dead, it must be kept to avoid messing up liveness info for - // the register scavenger. See pr4100.) - if (TII->isMoveInstr(*MI, SrcCopyReg, DstCopyReg, - SrcCopySubReg, DstCopySubReg) && - SrcCopyReg == DstCopyReg && DeadDefs.empty()) - MBB.erase(MI); + // Process virtreg deads. + for (unsigned i = 0, e = VirtKills.size(); i != e; ++i) + killVirtReg(VirtKills[i]); + VirtKills.clear(); + + // Process physreg deads. + for (unsigned i = 0, e = PhysKills.size(); i != e; ++i) + killPhysReg(PhysKills[i]); + PhysKills.clear(); } + // Spill all physical registers holding virtual registers now. + DEBUG(dbgs() << "Killing live registers at end of block.\n"); MachineBasicBlock::iterator MI = MBB.getFirstTerminator(); + while (!Virt2PhysMap.empty()) + spillVirtReg(MBB, MI, Virt2PhysMap.begin()->first, true); - // Spill all physical registers holding virtual registers now. - 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); - } + DEBUG(MBB.dump()); } /// runOnMachineFunction - Register allocate the whole function /// bool RAFast::runOnMachineFunction(MachineFunction &Fn) { DEBUG(dbgs() << "Machine Function\n"); + DEBUG(Fn.dump()); MF = &Fn; TM = &Fn.getTarget(); TRI = TM->getRegisterInfo(); TII = TM->getInstrInfo(); - PhysRegsUsed.assign(TRI->getNumRegs(), -1); + PhysRegDirty.resize(TRI->getNumRegs()); UsedInInstr.resize(TRI->getNumRegs()); - - // 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 = TRI->getAllocatableSet(Fn); - for (unsigned i = 0, e = Allocable.size(); i != e; ++i) - if (!Allocable[i]) - PhysRegsUsed[i] = -2; // Mark the reg unallocable. - } + ReservedRegs = TRI->getReservedRegs(*MF); // initialize the virtual->physical register map to have a 'null' // mapping for all virtual registers unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg(); StackSlotForVirtReg.grow(LastVirtReg); - Virt2PhysRegMap.grow(LastVirtReg); - Virt2LastUseMap.grow(LastVirtReg); - VirtRegModified.resize(LastVirtReg+1 - - TargetRegisterInfo::FirstVirtualRegister); - UsedInMultipleBlocks.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(); @@ -920,11 +694,6 @@ bool RAFast::runOnMachineFunction(MachineFunction &Fn) { AllocateBasicBlock(*MBB); StackSlotForVirtReg.clear(); - PhysRegsUsed.clear(); - VirtRegModified.clear(); - UsedInMultipleBlocks.clear(); - Virt2PhysRegMap.clear(); - Virt2LastUseMap.clear(); return true; } diff --git a/test/CodeGen/X86/2010-05-05-LocalAllocEarlyClobber.ll b/test/CodeGen/X86/2010-05-05-LocalAllocEarlyClobber.ll index 5ad363a..375f424 100644 --- a/test/CodeGen/X86/2010-05-05-LocalAllocEarlyClobber.ll +++ b/test/CodeGen/X86/2010-05-05-LocalAllocEarlyClobber.ll @@ -1,6 +1,6 @@ -; RUN: llc < %s -O0 -regalloc=local | FileCheck %s +; RUN-XFAIL: llc < %s -O0 -regalloc=local | FileCheck %s +; RUN: llc < %s -O0 -regalloc=fast | FileCheck %s ; PR6520 -; XFAIL: * target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32" target triple = "i386-apple-darwin10.0.0" diff --git a/test/CodeGen/X86/2010-05-06-LocalInlineAsmClobber.ll b/test/CodeGen/X86/2010-05-06-LocalInlineAsmClobber.ll index 167acdf..e554f9f 100644 --- a/test/CodeGen/X86/2010-05-06-LocalInlineAsmClobber.ll +++ b/test/CodeGen/X86/2010-05-06-LocalInlineAsmClobber.ll @@ -1,4 +1,5 @@ -; RUN: llc -regalloc=local %s -o /dev/null +; RUN: llc -regalloc=local %s -o %t +; RUN: llc -regalloc=fast %s -o %t ; PR7066 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" |