diff options
Diffstat (limited to 'lib/CodeGen/RegAllocFast.cpp')
| -rw-r--r-- | lib/CodeGen/RegAllocFast.cpp | 1169 |
1 files changed, 469 insertions, 700 deletions
diff --git a/lib/CodeGen/RegAllocFast.cpp b/lib/CodeGen/RegAllocFast.cpp index ab5e1032e1..488f630aa6 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; |