#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"
STATISTIC(NumLoads , "Number of loads added");
static RegisterRegAlloc
- localRegAlloc("local", " local register allocator",
+ localRegAlloc("local", "local register allocator",
createLocalRegisterAllocator);
namespace {
/// 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.
/// 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;
}
// 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) {
// Check if this is a two address instruction. If so, then
// the def does not kill the use.
if (last->second.first == I &&
- I->isRegReDefinedByTwoAddr(MO.getReg(), i))
+ I->isRegReDefinedByTwoAddr(i))
continue;
MachineOperand& lastUD =
// 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 (MO.isUse()) {
+ // Don't mark uses that are tied to defs as kills.
+ if (MI->getDesc().getOperandConstraint(idx, TOI::TIED_TO) == -1)
+ 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);
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);
}
}
}
// 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.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);
}
}
}
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);
}
}
}
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);
}
projects / oota-llvm.git / blobdiff