#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IndexedMap.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");
class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass {
public:
static char ID;
- RALocal() : MachineFunctionPass((intptr_t)&ID) {}
+ RALocal() : MachineFunctionPass((intptr_t)&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.
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);
-
- if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
- 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;
}
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);
<< 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;
}
-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());
+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;
+ }
+ };
+}
- // 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(),
- 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);
- }
- }
- }
- }
-
-
+/// 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;
+ DenseMap<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) {
// 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() &&
- !I->isRegReDefinedByTwoAddr(MO.getReg())) {
- std::map<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
+ if (MO.isReg() && MO.getReg() && MO.isDef()) {
+ DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
last = LastUseDef.find(MO.getReg());
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 &&
+ I->isRegReDefinedByTwoAddr(MO.getReg(), 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);
}
// 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
+ for (DenseMap<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;
if (isPhysReg || !usedOutsideBlock) {
if (MO.isUse())
MO.setIsKill(true);
- else if (MI->getOperand(idx).isDef())
+ else
MO.setIsDead(true);
}
}
+}
+
+void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) {
+ // loop over each instruction
+ MachineBasicBlock::iterator MII = MBB.begin();
+
+ 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(),
+ 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);
+ }
+ }
+ }
+ }
+
+ ComputeLocalLiveness(MBB);
// Otherwise, sequentially allocate each instruction in the MBB.
while (MII != MBB.end()) {
getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0);
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
}
}
// 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);
}
// 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