#define DEBUG_TYPE "regalloc"
#include "llvm/BasicBlock.h"
-#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineFrameInfo.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");
-namespace {
- static RegisterRegAlloc
- localRegAlloc("local", " local register allocator",
- createLocalRegisterAllocator);
-
+static RegisterRegAlloc
+ localRegAlloc("local", " local register allocator",
+ createLocalRegisterAllocator);
+namespace {
class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass {
public:
static char ID;
// 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!");
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<LiveVariables>();
AU.addRequiredID(PHIEliminationID);
AU.addRequiredID(TwoAddressInstructionPassID);
MachineFunctionPass::getAnalysisUsage(AU);
MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
unsigned OpNum);
+ /// ComputeLocalLiveness - Computes liveness of registers within a basic
+ /// block, setting the killed/dead flags as appropriate.
+ void ComputeLocalLiveness(MachineBasicBlock& MBB);
void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
unsigned PhysReg);
/// 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.lower_bound(VirtReg);
+ std::map<unsigned, int>::iterator I = StackSlotForVirtReg.find(VirtReg);
- if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
+ if (I != StackSlotForVirtReg.end())
return I->second; // Already has space allocated?
// Allocate a new stack object for this spill location...
assert(VirtReg && "Spilling a physical register is illegal!"
" Must not have appropriate kill for the register or use exists beyond"
" the intended one.");
- DOUT << " Spilling register " << TRI->getPrintableName(PhysReg)
+ DOUT << " Spilling register " << TRI->getName(PhysReg)
<< " containing %reg" << VirtReg;
- const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo();
-
if (!isVirtRegModified(VirtReg)) {
DOUT << " which has not been modified, so no store necessary!";
std::pair<MachineInstr*, unsigned> &LastUse = getVirtRegLastUse(VirtReg);
// 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->findRegisterUseOperandIdx(PhysReg) != -1);
+ bool isKill = !(I != MBB.end() && I->readsRegister(PhysReg));
TII->storeRegToStackSlot(MBB, I, PhysReg, isKill, FrameIndex, RC);
++NumStores; // Update statistics
}
// If the virtual register is already available, just update the instruction
// and return.
if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) {
- MarkPhysRegRecentlyUsed(PR); // Already have this value available!
+ MarkPhysRegRecentlyUsed(PR); // Already have this value available!
MI->getOperand(OpNum).setReg(PR); // Assign the input register
+ getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum);
return MI;
}
markVirtRegModified(VirtReg, false); // Note that this reg was just reloaded
DOUT << " Reloading %reg" << VirtReg << " into "
- << TRI->getPrintableName(PhysReg) << "\n";
+ << TRI->getName(PhysReg) << "\n";
// Add move instruction(s)
- const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo();
TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC);
++NumLoads; // Update statistics
return false;
}
+// precedes - Helper function to determine with MachineInstr A
+// precedes MachineInstr B within the same MBB.
+static bool precedes(MachineBasicBlock::iterator A,
+ MachineBasicBlock::iterator B) {
+ if (A == B)
+ return false;
+
+ MachineBasicBlock::iterator I = A->getParent()->begin();
+ while (I != A->getParent()->end()) {
+ if (I == A)
+ return true;
+ else if (I == B)
+ return false;
+
+ ++I;
+ }
+
+ return false;
+}
+
+/// ComputeLocalLiveness - Computes liveness of registers within a basic
+/// block, setting the killed/dead flags as appropriate.
+void RALocal::ComputeLocalLiveness(MachineBasicBlock& MBB) {
+ MachineRegisterInfo& MRI = MBB.getParent()->getRegInfo();
+ // Keep track of the most recently seen previous use or def of each reg,
+ // so that we can update them with dead/kill markers.
+ std::map<unsigned, std::pair<MachineInstr*, unsigned> > LastUseDef;
+ for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
+ I != E; ++I) {
+ for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
+ MachineOperand& MO = I->getOperand(i);
+ // Uses don't trigger any flags, but we need to save
+ // 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())
+ LastUseDef[MO.getReg()] = std::make_pair(I, i);
+ }
+
+ for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
+ MachineOperand& MO = I->getOperand(i);
+ // Defs others than 2-addr redefs _do_ trigger flag changes:
+ // - A def followed by a def is dead
+ // - A use followed by a def is a kill
+ if (MO.isReg() && MO.getReg() && MO.isDef()) {
+ std::map<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
+ last = LastUseDef.find(MO.getReg());
+ if (last != LastUseDef.end()) {
+
+ // If this is a two address instr, then we don't mark the def
+ // as killing the use.
+ if (last->second.first == I) {
+ LastUseDef[MO.getReg()] = std::make_pair(I, i);
+ continue;
+ }
+
+
+ MachineOperand& lastUD =
+ last->second.first->getOperand(last->second.second);
+
+ if (lastUD.isDef())
+ lastUD.setIsDead(true);
+ else if (lastUD.isUse())
+ lastUD.setIsKill(true);
+ }
+
+ LastUseDef[MO.getReg()] = std::make_pair(I, i);
+ }
+ }
+ }
+
+ // Live-out (of the function) registers contain return values of the function,
+ // so we need to make sure they are alive at return time.
+ if (!MBB.empty() && MBB.back().getDesc().isReturn()) {
+ MachineInstr* Ret = &MBB.back();
+ for (MachineRegisterInfo::liveout_iterator
+ I = MF->getRegInfo().liveout_begin(),
+ E = MF->getRegInfo().liveout_end(); I != E; ++I)
+ if (!Ret->readsRegister(*I)) {
+ Ret->addOperand(MachineOperand::CreateReg(*I, false, true));
+ LastUseDef[*I] = std::make_pair(Ret, Ret->getNumOperands()-1);
+ }
+ }
+
+ // Finally, loop over the final use/def of each reg
+ // in the block and determine if it is dead.
+ for (std::map<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
+ I = LastUseDef.begin(), E = LastUseDef.end(); I != E; ++I) {
+ MachineInstr* MI = I->second.first;
+ unsigned idx = I->second.second;
+ MachineOperand& MO = MI->getOperand(idx);
+
+ bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(MO.getReg());
+
+ // A crude approximation of "live-out" calculation
+ bool usedOutsideBlock = isPhysReg ? false :
+ UsedInMultipleBlocks.test(MO.getReg() -
+ TargetRegisterInfo::FirstVirtualRegister);
+ if (!isPhysReg && !usedOutsideBlock)
+ for (MachineRegisterInfo::reg_iterator UI = MRI.reg_begin(MO.getReg()),
+ UE = MRI.reg_end(); UI != UE; ++UI)
+ // Two cases:
+ // - used in another block
+ // - used in the same block before it is defined (loop)
+ if (UI->getParent() != &MBB ||
+ (MO.isDef() && UI.getOperand().isUse() && precedes(&*UI, MI))) {
+ UsedInMultipleBlocks.set(MO.getReg() -
+ TargetRegisterInfo::FirstVirtualRegister);
+ usedOutsideBlock = true;
+ break;
+ }
+
+ // 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())
+ MO.setIsDead(true);
+ }
+ }
+}
+
void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) {
// loop over each instruction
MachineBasicBlock::iterator MII = MBB.begin();
- const TargetInstrInfo &TII = *TM->getInstrInfo();
DEBUG(const BasicBlock *LBB = MBB.getBasicBlock();
if (LBB) DOUT << "\nStarting RegAlloc of BB: " << LBB->getName());
// If this is the first basic block in the machine function, add live-in
// registers as active.
- if (&MBB == &*MF->begin()) {
- for (MachineRegisterInfo::livein_iterator I=MF->getRegInfo().livein_begin(),
- E = MF->getRegInfo().livein_end(); I != E; ++I) {
- unsigned Reg = I->first;
+ if (&MBB == &*MF->begin() || MBB.isLandingPad()) {
+ 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);
}
}
+ ComputeLocalLiveness(MBB);
+
// Otherwise, sequentially allocate each instruction in the MBB.
while (MII != MBB.end()) {
MachineInstr *MI = MII++;
DOUT << " Regs have values: ";
for (unsigned i = 0; i != TRI->getNumRegs(); ++i)
if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2)
- DOUT << "[" << TRI->getPrintableName(i)
+ DOUT << "[" << TRI->getName(i)
<< ",%reg" << PhysRegsUsed[i] << "] ";
DOUT << "\n");
}
if (PhysReg) {
- DOUT << " Last use of " << TRI->getPrintableName(PhysReg)
+ 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) {
DOUT << " Last use of "
- << TRI->getPrintableName(*AliasSet)
+ << TRI->getName(*AliasSet)
<< "[%reg" << VirtReg <<"], removing it from live set\n";
removePhysReg(*AliasSet);
}
MF->getRegInfo().setPhysRegUsed(DestPhysReg);
markVirtRegModified(DestVirtReg);
getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0);
- DOUT << " Assigning " << TRI->getPrintableName(DestPhysReg)
+ DOUT << " Assigning " << TRI->getName(DestPhysReg)
<< " to %reg" << DestVirtReg << "\n";
- MI->getOperand(i).setReg(DestPhysReg); // Assign the output register
+ MO.setReg(DestPhysReg); // Assign the output register
}
}
}
if (PhysReg) {
- DOUT << " Register " << TRI->getPrintableName(PhysReg)
+ DOUT << " Register " << TRI->getName(PhysReg)
<< " [%reg" << VirtReg
<< "] is never used, removing it frame live list\n";
removePhysReg(PhysReg);
for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
*AliasSet; ++AliasSet) {
if (PhysRegsUsed[*AliasSet] != -2) {
- DOUT << " Register " << TRI->getPrintableName(*AliasSet)
+ DOUT << " Register " << TRI->getName(*AliasSet)
<< " [%reg" << *AliasSet
<< "] is never used, removing it frame live list\n";
removePhysReg(*AliasSet);
// Finally, if this is a noop copy instruction, zap it.
unsigned SrcReg, DstReg;
- if (TII.isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg)
+ if (TII->isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg)
MBB.erase(MI);
}
PhysRegsUseOrder.clear();
}
-
/// runOnMachineFunction - Register allocate the whole function
///
bool RALocal::runOnMachineFunction(MachineFunction &Fn) {
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();
MBB != MBBe; ++MBB)
StackSlotForVirtReg.clear();
PhysRegsUsed.clear();
VirtRegModified.clear();
+ UsedInMultipleBlocks.clear();
Virt2PhysRegMap.clear();
Virt2LastUseMap.clear();
return true;
projects / oota-llvm.git / blobdiff