#include "llvm/Support/Compiler.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IndexedMap.h"
+#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
-#include <map>
using namespace llvm;
STATISTIC(NumStores, "Number of stores added");
STATISTIC(NumLoads , "Number of loads added");
static RegisterRegAlloc
- localRegAlloc("local", " local register allocator",
+ localRegAlloc("local", "local register allocator",
createLocalRegisterAllocator);
namespace {
class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass {
public:
static char ID;
- RALocal() : MachineFunctionPass((intptr_t)&ID) {}
+ RALocal() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1) {}
private:
const TargetMachine *TM;
MachineFunction *MF;
// StackSlotForVirtReg - Maps virtual regs to the frame index where these
// values are spilled.
- std::map<unsigned, int> StackSlotForVirtReg;
+ IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
// Virt2PhysRegMap - This map contains entries for each virtual register
// that is currently available in a physical register.
/// 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.
- ///
+ /// 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);
+ unsigned VirtReg, bool NoFree = false);
/// reloadVirtReg - This method transforms the specified specified virtual
/// register use to refer to a physical register. This method may do this
/// value. This method returns the modified instruction.
///
MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
- unsigned OpNum);
+ unsigned OpNum, SmallSet<unsigned, 4> &RRegs);
/// ComputeLocalLiveness - Computes liveness of registers within a basic
/// block, setting the killed/dead flags as appropriate.
/// to be held on the stack.
int RALocal::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
// Find the location Reg would belong...
- std::map<unsigned, int>::iterator I = StackSlotForVirtReg.find(VirtReg);
-
- if (I != StackSlotForVirtReg.end())
- return I->second; // Already has space allocated?
+ int SS = StackSlotForVirtReg[VirtReg];
+ if (SS != -1)
+ return SS; // Already has space allocated?
// Allocate a new stack object for this spill location...
int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
RC->getAlignment());
// Assign the slot...
- StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
+ StackSlotForVirtReg[VirtReg] = FrameIdx;
return FrameIdx;
}
/// the last used virtual register to the stack, and uses that register.
///
unsigned RALocal::getReg(MachineBasicBlock &MBB, MachineInstr *I,
- unsigned VirtReg) {
+ unsigned VirtReg, bool NoFree) {
const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
// First check to see if we have a free register of the requested type...
- unsigned PhysReg = getFreeReg(RC);
+ unsigned PhysReg = NoFree ? 0 : getFreeReg(RC);
// If we didn't find an unused register, scavenge one now!
if (PhysReg == 0) {
/// modified instruction.
///
MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
- unsigned OpNum) {
+ unsigned OpNum,
+ SmallSet<unsigned, 4> &ReloadedRegs) {
unsigned VirtReg = MI->getOperand(OpNum).getReg();
// If the virtual register is already available, just update the instruction
} 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);
+ PhysReg = getReg(MBB, MI, VirtReg, true);
}
markVirtRegModified(VirtReg, false); // Note that this reg was just reloaded
MF->getRegInfo().setPhysRegUsed(PhysReg);
MI->getOperand(OpNum).setReg(PhysReg); // Assign the input register
getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum);
+
+ if (!ReloadedRegs.insert(PhysReg)) {
+ cerr << "Ran out of registers during register allocation!\n";
+ if (MI->getOpcode() == TargetInstrInfo::INLINEASM) {
+ cerr << "Please check your inline asm statement for invalid "
+ << "constraints:\n";
+ MI->print(cerr.stream(), TM);
+ }
+ exit(1);
+ }
+ for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg);
+ *SubRegs; ++SubRegs) {
+ if (!ReloadedRegs.insert(*SubRegs)) {
+ cerr << "Ran out of registers during register allocation!\n";
+ if (MI->getOpcode() == TargetInstrInfo::INLINEASM) {
+ cerr << "Please check your inline asm statement for invalid "
+ << "constraints:\n";
+ MI->print(cerr.stream(), TM);
+ }
+ exit(1);
+ }
+ }
+
return MI;
}
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() &&
+ if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() &&
MO.isDef() && !MO.isDead())
return true;
}
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() &&
+ if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() &&
!MO.isDef() && MO.isKill())
return true;
}
return false;
}
-namespace llvm {
- template<> struct DenseMapInfo<uint32_t> {
- static inline uint32_t getEmptyKey() { return ~0; }
- static inline uint32_t getTombstoneKey() { return ~0 - 1; }
- static unsigned getHashValue(const uint32_t& Val) { return Val * 37; }
- static bool isPod() { return true; }
- static bool isEqual(const uint32_t& LHS, const uint32_t& RHS) {
- return LHS == RHS;
- }
- };
-}
-
/// ComputeLocalLiveness - Computes liveness of registers within a basic
/// block, setting the killed/dead flags as appropriate.
void RALocal::ComputeLocalLiveness(MachineBasicBlock& MBB) {
// them for later. Also, we have to process these
// _before_ processing the defs, since an instr
// uses regs before it defs them.
- if (MO.isReg() && MO.getReg() && MO.isUse())
+ if (MO.isReg() && MO.getReg() && MO.isUse()) {
LastUseDef[MO.getReg()] = std::make_pair(I, i);
+
+
+ if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) continue;
+
+ const unsigned* Aliases = TRI->getAliasSet(MO.getReg());
+ if (Aliases) {
+ while (*Aliases) {
+ DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
+ alias = LastUseDef.find(*Aliases);
+
+ if (alias != LastUseDef.end() && alias->second.first != I)
+ LastUseDef[*Aliases] = std::make_pair(I, i);
+
+ ++Aliases;
+ }
+ }
+ }
}
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
if (last != LastUseDef.end()) {
// Check if this is a two address instruction. If so, then
// the def does not kill the use.
- if (last->second.first == I) {
- bool isTwoAddr = false;
- for (unsigned j = i+1, je = I->getDesc().getNumOperands();
- j < je; ++j) {
- const MachineOperand &MO2 = I->getOperand(j);
- if (MO2.isRegister() && MO2.isUse() &&
- MO2.getReg() == MO.getReg() &&
- I->getDesc().getOperandConstraint(j, TOI::TIED_TO) == (int)i)
- isTwoAddr = true;
- }
-
- if (isTwoAddr) continue;
- }
+ if (last->second.first == I &&
+ I->isRegReDefinedByTwoAddr(i))
+ continue;
MachineOperand& lastUD =
last->second.first->getOperand(last->second.second);
if (lastUD.isDef())
lastUD.setIsDead(true);
- else if (lastUD.isUse())
+ else
lastUD.setIsKill(true);
}
// Physical registers and those that are not live-out of the block
// are killed/dead at their last use/def within this block.
if (isPhysReg || !usedOutsideBlock) {
- if (MO.isUse())
- MO.setIsKill(true);
- else if (MI->getOperand(idx).isDef())
+ if (MO.isUse()) {
+ // Don't mark uses that are tied to defs as kills.
+ if (!MI->isRegTiedToDefOperand(idx))
+ MO.setIsKill(true);
+ } else
MO.setIsDead(true);
}
}
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() || MBB.isLandingPad()) {
- for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(),
+ // Add live-in registers as active.
+ 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
- AddToPhysRegsUseOrder(Reg);
- for (const unsigned *AliasSet = TRI->getSubRegisters(Reg);
- *AliasSet; ++AliasSet) {
- if (PhysRegsUsed[*AliasSet] != -2) {
- AddToPhysRegsUseOrder(*AliasSet);
- PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now
- MF->getRegInfo().setPhysRegUsed(*AliasSet);
- }
+ unsigned Reg = *I;
+ MF->getRegInfo().setPhysRegUsed(Reg);
+ PhysRegsUsed[Reg] = 0; // It is free and reserved now
+ AddToPhysRegsUseOrder(Reg);
+ for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
+ *SubRegs; ++SubRegs) {
+ if (PhysRegsUsed[*SubRegs] != -2) {
+ AddToPhysRegsUseOrder(*SubRegs);
+ PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now
+ MF->getRegInfo().setPhysRegUsed(*SubRegs);
}
- }
+ }
}
ComputeLocalLiveness(MBB);
SmallVector<unsigned, 8> Kills;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand& MO = MI->getOperand(i);
- if (MO.isRegister() && MO.isKill()) {
+ if (MO.isReg() && MO.isKill()) {
if (!MO.isImplicit())
Kills.push_back(MO.getReg());
else if (!isReadModWriteImplicitKill(MI, 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->getOpcode()==TargetInstrInfo::INLINEASM) {
+ for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
+ MachineOperand& MO = MI->getOperand(i);
+ if (MO.isReg() && MO.isDef() && MO.isEarlyClobber() &&
+ MO.getReg()) {
+ 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);
+ DOUT << " 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
+ AddToPhysRegsUseOrder(Reg);
+
+ for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
+ *SubRegs; ++SubRegs) {
+ if (PhysRegsUsed[*SubRegs] != -2) {
+ MF->getRegInfo().setPhysRegUsed(*SubRegs);
+ PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now
+ AddToPhysRegsUseOrder(*SubRegs);
+ }
+ }
+ }
+ }
+ }
+ }
+
// 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) {
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() &&
+ if (MO.isReg() && !MO.isDef() && MO.getReg() && !MO.isImplicit() &&
TargetRegisterInfo::isVirtualRegister(MO.getReg()))
- MI = reloadVirtReg(MBB, MI, i);
+ MI = reloadVirtReg(MBB, MI, i, ReloadedRegs);
}
// If this instruction is the last user of this register, kill the
DOUT << " Last use of " << TRI->getName(PhysReg)
<< "[%reg" << VirtReg <<"], removing it from live set\n";
removePhysReg(PhysReg);
- for (const unsigned *AliasSet = TRI->getSubRegisters(PhysReg);
- *AliasSet; ++AliasSet) {
- if (PhysRegsUsed[*AliasSet] != -2) {
+ for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg);
+ *SubRegs; ++SubRegs) {
+ if (PhysRegsUsed[*SubRegs] != -2) {
DOUT << " Last use of "
- << TRI->getName(*AliasSet)
+ << TRI->getName(*SubRegs)
<< "[%reg" << VirtReg <<"], removing it from live set\n";
- removePhysReg(*AliasSet);
+ removePhysReg(*SubRegs);
}
}
}
// are defined, and marking explicit destinations in the PhysRegsUsed map.
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand& MO = MI->getOperand(i);
- if (MO.isRegister() && MO.isDef() && !MO.isImplicit() && MO.getReg() &&
+ if (MO.isReg() && MO.isDef() && !MO.isImplicit() && MO.getReg() &&
+ !MO.isEarlyClobber() &&
TargetRegisterInfo::isPhysicalRegister(MO.getReg())) {
unsigned Reg = MO.getReg();
if (PhysRegsUsed[Reg] == -2) continue; // Something like ESP.
PhysRegsUsed[Reg] = 0; // It is free and reserved now
AddToPhysRegsUseOrder(Reg);
- for (const unsigned *AliasSet = TRI->getSubRegisters(Reg);
- *AliasSet; ++AliasSet) {
- if (PhysRegsUsed[*AliasSet] != -2) {
- MF->getRegInfo().setPhysRegUsed(*AliasSet);
- PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now
- AddToPhysRegsUseOrder(*AliasSet);
+ for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
+ *SubRegs; ++SubRegs) {
+ if (PhysRegsUsed[*SubRegs] != -2) {
+ MF->getRegInfo().setPhysRegUsed(*SubRegs);
+ PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now
+ AddToPhysRegsUseOrder(*SubRegs);
}
}
}
PhysRegsUsed[Reg] = 0; // It is free and reserved now
}
MF->getRegInfo().setPhysRegUsed(Reg);
- for (const unsigned *AliasSet = TRI->getSubRegisters(Reg);
- *AliasSet; ++AliasSet) {
- if (PhysRegsUsed[*AliasSet] != -2) {
- AddToPhysRegsUseOrder(*AliasSet);
- PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now
- MF->getRegInfo().setPhysRegUsed(*AliasSet);
+ for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
+ *SubRegs; ++SubRegs) {
+ if (PhysRegsUsed[*SubRegs] != -2) {
+ AddToPhysRegsUseOrder(*SubRegs);
+ PhysRegsUsed[*SubRegs] = 0; // It is free and reserved now
+ MF->getRegInfo().setPhysRegUsed(*SubRegs);
}
}
}
SmallVector<unsigned, 8> DeadDefs;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand& MO = MI->getOperand(i);
- if (MO.isRegister() && MO.isDead())
+ if (MO.isReg() && MO.isDead())
DeadDefs.push_back(MO.getReg());
}
//
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand& MO = MI->getOperand(i);
- if (MO.isRegister() && MO.isDef() && MO.getReg() &&
+ if (MO.isReg() && MO.isDef() && MO.getReg() &&
+ !MO.isEarlyClobber() &&
TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
unsigned DestVirtReg = MO.getReg();
unsigned DestPhysReg;
if (PhysReg) {
DOUT << " Register " << TRI->getName(PhysReg)
<< " [%reg" << VirtReg
- << "] is never used, removing it frame live list\n";
+ << "] is never used, removing it from live set\n";
removePhysReg(PhysReg);
for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
*AliasSet; ++AliasSet) {
if (PhysRegsUsed[*AliasSet] != -2) {
DOUT << " Register " << TRI->getName(*AliasSet)
<< " [%reg" << *AliasSet
- << "] is never used, removing it frame live list\n";
+ << "] is never used, removing it from live set\n";
removePhysReg(*AliasSet);
}
}
}
// Finally, if this is a noop copy instruction, zap it.
- unsigned SrcReg, DstReg;
- if (TII->isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg)
+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+ if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
+ SrcReg == DstReg)
MBB.erase(MI);
}
// 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);
projects / oota-llvm.git / blobdiff