#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
+#include <algorithm>
using namespace llvm;
namespace {
Statistic<> NumStores("spiller", "Number of stores added");
Statistic<> NumLoads ("spiller", "Number of loads added");
Statistic<> NumReused("spiller", "Number of values reused");
+ Statistic<> NumDSE ("spiller", "Number of dead stores elided");
enum SpillerName { simple, local };
Virt2StackSlotMap[virtReg] = frameIndex;
}
-void VirtRegMap::virtFolded(unsigned virtReg,
- MachineInstr* oldMI,
- MachineInstr* newMI) {
- // move previous memory references folded to new instruction
- std::vector<MI2VirtMapTy::mapped_type> regs;
- for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(oldMI),
- E = MI2VirtMap.end(); I != E && I->first == oldMI; ) {
- regs.push_back(I->second);
+void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
+ unsigned OpNo, MachineInstr *NewMI) {
+ // Move previous memory references folded to new instruction.
+ MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
+ for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
+ E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
+ MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
MI2VirtMap.erase(I++);
}
- MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(newMI);
- for (unsigned i = 0, e = regs.size(); i != e; ++i)
- MI2VirtMap.insert(IP, std::make_pair(newMI, regs[i]));
+ ModRef MRInfo;
+ if (!OldMI->getOperand(OpNo).isDef()) {
+ assert(OldMI->getOperand(OpNo).isUse() && "Operand is not use or def?");
+ MRInfo = isRef;
+ } else {
+ MRInfo = OldMI->getOperand(OpNo).isUse() ? isModRef : isMod;
+ }
// add new memory reference
- MI2VirtMap.insert(IP, std::make_pair(newMI, virtReg));
+ MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
}
void VirtRegMap::print(std::ostream &OS) const {
};
}
-bool SimpleSpiller::runOnMachineFunction(MachineFunction& MF,
- const VirtRegMap& VRM) {
+bool SimpleSpiller::runOnMachineFunction(MachineFunction &MF,
+ const VirtRegMap &VRM) {
DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
DEBUG(std::cerr << "********** Function: "
<< MF.getFunction()->getName() << '\n');
- const TargetMachine& TM = MF.getTarget();
- const MRegisterInfo& MRI = *TM.getRegisterInfo();
+ const TargetMachine &TM = MF.getTarget();
+ const MRegisterInfo &MRI = *TM.getRegisterInfo();
+ bool *PhysRegsUsed = MF.getUsedPhysregs();
// LoadedRegs - Keep track of which vregs are loaded, so that we only load
// each vreg once (in the case where a spilled vreg is used by multiple
++NumStores;
}
}
+ PhysRegsUsed[PhysReg] = true;
MI.SetMachineOperandReg(i, PhysReg);
}
}
// and ".second" is the virtual register that is spilled.
std::vector<std::pair<unsigned, unsigned> > DefAndUseVReg;
+ // MaybeDeadStores - When we need to write a value back into a stack slot,
+ // keep track of the inserted store. If the stack slot value is never read
+ // (because the value was used from some available register, for example), and
+ // subsequently stored to, the original store is dead. This map keeps track
+ // of inserted stores that are not used. If we see a subsequent store to the
+ // same stack slot, the original store is deleted.
+ std::map<int, MachineInstr*> MaybeDeadStores;
+
+ bool *PhysRegsUsed = MBB.getParent()->getUsedPhysregs();
+
for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
MII != E; ) {
MachineInstr &MI = *MII;
if (!VRM.hasStackSlot(VirtReg)) {
// This virtual register was assigned a physreg!
- MI.SetMachineOperandReg(i, VRM.getPhys(VirtReg));
+ unsigned Phys = VRM.getPhys(VirtReg);
+ PhysRegsUsed[Phys] = true;
+ MI.SetMachineOperandReg(i, Phys);
} else {
// Is this virtual register a spilled value?
if (MO.isUse()) {
std::map<int, unsigned>::iterator SSI =
SpillSlotsAvailable.find(StackSlot);
if (SSI != SpillSlotsAvailable.end()) {
+ DEBUG(std::cerr << "Reusing SS#" << StackSlot << " from physreg "
+ << MRI->getName(SSI->second) << " for vreg"
+ << VirtReg <<" instead of reloading into physreg "
+ << MRI->getName(VRM.getPhys(VirtReg)) << "\n");
// If this stack slot value is already available, reuse it!
PhysReg = SSI->second;
MI.SetMachineOperandReg(i, PhysReg);
- DEBUG(std::cerr << "Reusing SS#" << StackSlot << " from physreg "
- << MRI->getName(SSI->second) << "\n");
// The only technical detail we have is that we don't know that
// PhysReg won't be clobbered by a reloaded stack slot that occurs
// Otherwise, reload it and remember that we have it.
PhysReg = VRM.getPhys(VirtReg);
+ RecheckRegister:
// Note that, if we reused a register for a previous operand, the
// register we want to reload into might not actually be
// available. If this occurs, use the register indicated by the
if (ReusedOperands[ro].PhysRegReused == PhysReg) {
// Yup, use the reload register that we didn't use before.
PhysReg = ReusedOperands[ro].AssignedPhysReg;
- break;
+ goto RecheckRegister;
} else {
ReusedOp &Op = ReusedOperands[ro];
unsigned PRRU = Op.PhysRegReused;
ClobberPhysReg(Op.AssignedPhysReg, SpillSlotsAvailable,
PhysRegsAvailable);
+ // Any stores to this stack slot are not dead anymore.
+ MaybeDeadStores.erase(Op.StackSlot);
+
MI.SetMachineOperandReg(Op.Operand, Op.AssignedPhysReg);
PhysRegsAvailable[Op.AssignedPhysReg] = Op.StackSlot;
SpillSlotsAvailable[Op.StackSlot] = Op.AssignedPhysReg;
}
}
ContinueReload:
-
+ PhysRegsUsed[PhysReg] = true;
MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot);
// This invalidates PhysReg.
ClobberPhysReg(PhysReg, SpillSlotsAvailable, PhysRegsAvailable);
+ // Any stores to this stack slot are not dead anymore.
+ MaybeDeadStores.erase(StackSlot);
+
MI.SetMachineOperandReg(i, PhysReg);
PhysRegsAvailable[PhysReg] = StackSlot;
SpillSlotsAvailable[StackSlot] = PhysReg;
// Loop over all of the implicit defs, clearing them from our available
// sets.
- const TargetInstrDescriptor &InstrDesc = TII->get(MI.getOpcode());
- for (const unsigned* ImpDef = InstrDesc.ImplicitDefs; *ImpDef; ++ImpDef)
+ for (const unsigned *ImpDef = TII->getImplicitDefs(MI.getOpcode());
+ *ImpDef; ++ImpDef) {
+ PhysRegsUsed[*ImpDef] = true;
ClobberPhysReg(*ImpDef, SpillSlotsAvailable, PhysRegsAvailable);
+ }
DEBUG(std::cerr << '\t' << MI);
// If we have folded references to memory operands, make sure we clear all
// physical registers that may contain the value of the spilled virtual
// register
- VirtRegMap::MI2VirtMapTy::const_iterator I, E;
- for (tie(I, E) = VRM.getFoldedVirts(&MI); I != E; ++I) {
- DEBUG(std::cerr << "Folded vreg: " << I->second);
- if (VRM.hasStackSlot(I->second)) {
- int SS = VRM.getStackSlot(I->second);
+ VirtRegMap::MI2VirtMapTy::const_iterator I, End;
+ for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) {
+ DEBUG(std::cerr << "Folded vreg: " << I->second.first << " MR: "
+ << I->second.second);
+ unsigned VirtReg = I->second.first;
+ VirtRegMap::ModRef MR = I->second.second;
+ if (VRM.hasStackSlot(VirtReg)) {
+ int SS = VRM.getStackSlot(VirtReg);
DEBUG(std::cerr << " - StackSlot: " << SS << "\n");
- std::map<int, unsigned>::iterator I = SpillSlotsAvailable.find(SS);
- if (I != SpillSlotsAvailable.end()) {
- PhysRegsAvailable.erase(I->second);
- SpillSlotsAvailable.erase(I);
+ // If this reference is not a use, any previous store is now dead.
+ // Otherwise, the store to this stack slot is not dead anymore.
+ std::map<int, MachineInstr*>::iterator MDSI = MaybeDeadStores.find(SS);
+ if (MDSI != MaybeDeadStores.end()) {
+ if (MR & VirtRegMap::isRef) // Previous store is not dead.
+ MaybeDeadStores.erase(MDSI);
+ else {
+ // If we get here, the store is dead, nuke it now.
+ assert(MR == VirtRegMap::isMod && "Can't be modref!");
+ MBB.erase(MDSI->second);
+ MaybeDeadStores.erase(MDSI);
+ ++NumDSE;
+ }
+ }
+
+ // If the spill slot value is available, and this is a new definition of
+ // the value, the value is not available anymore.
+ if (MR & VirtRegMap::isMod) {
+ std::map<int, unsigned>::iterator It = SpillSlotsAvailable.find(SS);
+ if (It != SpillSlotsAvailable.end()) {
+ PhysRegsAvailable.erase(It->second);
+ SpillSlotsAvailable.erase(It);
+ }
}
} else {
DEBUG(std::cerr << ": No stack slot!\n");
else
PhysReg = MO.getReg();
+ PhysRegsUsed[PhysReg] = true;
MRI->storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot);
DEBUG(std::cerr << "Store:\t" << *next(MII));
MI.SetMachineOperandReg(i, PhysReg);
+ // If there is a dead store to this stack slot, nuke it now.
+ MachineInstr *&LastStore = MaybeDeadStores[StackSlot];
+ if (LastStore) {
+ DEBUG(std::cerr << " Killed store:\t" << *LastStore);
+ ++NumDSE;
+ MBB.erase(LastStore);
+ }
+ LastStore = next(MII);
+
// If the stack slot value was previously available in some other
// register, change it now. Otherwise, make the register available,
// in PhysReg.
PhysRegsAvailable[PhysReg] = StackSlot;
SpillSlotsAvailable[StackSlot] = PhysReg;
DEBUG(std::cerr << "Updating SS#" << StackSlot <<" in physreg "
- << MRI->getName(PhysReg) << "\n");
+ << MRI->getName(PhysReg) << " for virtreg #"
+ << VirtReg << "\n");
++NumStores;
VirtReg = PhysReg;
projects / oota-llvm.git / blobdiff