#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/Support/CommandLine.h"
+#include "llvm/Target/TargetOptions.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk");
-
-static cl::opt<bool>
-EnableReMat("2-addr-remat", cl::init(false), cl::Hidden,
- cl::desc("Two-addr conversion should remat when possible."));
+STATISTIC(NumReMats, "Number of instructions re-materialized");
namespace {
class VISIBILITY_HIDDEN TwoAddressInstructionPass
bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
unsigned Reg,
MachineBasicBlock::iterator OldPos);
+
+ bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
+ MachineInstr *MI, MachineInstr *DefMI,
+ MachineBasicBlock *MBB, unsigned Loc,
+ DenseMap<MachineInstr*, unsigned> &DistanceMap);
public:
static char ID; // Pass identification, replacement for typeid
- TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {}
+ TwoAddressInstructionPass() : MachineFunctionPass(&ID) {}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<LiveVariables>();
AU.addPreserved<LiveVariables>();
AU.addPreservedID(MachineLoopInfoID);
AU.addPreservedID(MachineDominatorsID);
- AU.addPreservedID(PHIEliminationID);
+ if (StrongPHIElim)
+ AU.addPreservedID(StrongPHIEliminationID);
+ else
+ AU.addPreservedID(PHIEliminationID);
MachineFunctionPass::getAnalysisUsage(AU);
}
/// three-address instruction to avoid clobbering a register. Try to sink it
/// past the instruction that would kill the above mentioned register to reduce
/// register pressure.
-///
bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
MachineInstr *MI, unsigned SavedReg,
MachineBasicBlock::iterator OldPos) {
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
- if (!MO.isRegister())
+ if (!MO.isReg())
continue;
unsigned MOReg = MO.getReg();
if (!MOReg)
// Find the instruction that kills SavedReg.
MachineInstr *KillMI = NULL;
-
for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
UE = MRI->use_end(); UI != UE; ++UI) {
MachineOperand &UseMO = UI.getOperand();
// position and the kill use, then it's not safe to sink it.
//
// FIXME: This can be sped up if there is an easy way to query whether an
- // instruction if before or after another instruction. Then we can use
+ // instruction is before or after another instruction. Then we can use
// MachineRegisterInfo def / use instead.
MachineOperand *KillMO = NULL;
MachineBasicBlock::iterator KillPos = KillMI;
++KillPos;
+ unsigned NumVisited = 0;
for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
MachineInstr *OtherMI = I;
-
+ if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost.
+ return false;
+ ++NumVisited;
for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = OtherMI->getOperand(i);
- if (!MO.isRegister())
+ if (!MO.isReg())
continue;
unsigned MOReg = MO.getReg();
if (!MOReg)
if (MO.isKill()) {
if (OtherMI == KillMI && MOReg == SavedReg)
- // Save the operand that kills the register. We want unset the kill
- // marker is we can sink MI past it.
+ // Save the operand that kills the register. We want to unset the kill
+ // marker if we can sink MI past it.
KillMO = &MO;
else if (UseRegs.count(MOReg))
// One of the uses is killed before the destination.
KillMO->setIsKill(false);
KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
KillMO->setIsKill(true);
- LiveVariables::VarInfo& VarInfo = LV->getVarInfo(SavedReg);
- VarInfo.removeKill(KillMI);
- VarInfo.Kills.push_back(MI);
+
+ if (LV)
+ LV->replaceKillInstruction(SavedReg, KillMI, MI);
// Move instruction to its destination.
MBB->remove(MI);
return true;
}
+/// isTwoAddrUse - Return true if the specified MI is using the specified
+/// register as a two-address operand.
+static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) {
+ const TargetInstrDesc &TID = UseMI->getDesc();
+ for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = UseMI->getOperand(i);
+ if (MO.isReg() && MO.getReg() == Reg &&
+ (MO.isDef() || TID.getOperandConstraint(i, TOI::TIED_TO) != -1))
+ // Earlier use is a two-address one.
+ return true;
+ }
+ return false;
+}
+
+/// isProfitableToReMat - Return true if the heuristics determines it is likely
+/// to be profitable to re-materialize the definition of Reg rather than copy
+/// the register.
+bool
+TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
+ const TargetRegisterClass *RC,
+ MachineInstr *MI, MachineInstr *DefMI,
+ MachineBasicBlock *MBB, unsigned Loc,
+ DenseMap<MachineInstr*, unsigned> &DistanceMap){
+ bool OtherUse = false;
+ for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
+ UE = MRI->use_end(); UI != UE; ++UI) {
+ MachineOperand &UseMO = UI.getOperand();
+ if (!UseMO.isUse())
+ continue;
+ MachineInstr *UseMI = UseMO.getParent();
+ MachineBasicBlock *UseMBB = UseMI->getParent();
+ if (UseMBB == MBB) {
+ DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
+ if (DI != DistanceMap.end() && DI->second == Loc)
+ continue; // Current use.
+ OtherUse = true;
+ // There is at least one other use in the MBB that will clobber the
+ // register.
+ if (isTwoAddrUse(UseMI, Reg))
+ return true;
+ }
+ }
+
+ // If other uses in MBB are not two-address uses, then don't remat.
+ if (OtherUse)
+ return false;
+
+ // No other uses in the same block, remat if it's defined in the same
+ // block so it does not unnecessarily extend the live range.
+ return MBB == DefMI->getParent();
+}
+
/// runOnMachineFunction - Reduce two-address instructions to two operands.
///
bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
MRI = &MF.getRegInfo();
TII = TM.getInstrInfo();
TRI = TM.getRegisterInfo();
- LV = &getAnalysis<LiveVariables>();
+ LV = getAnalysisToUpdate<LiveVariables>();
bool MadeChange = false;
DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
- SmallPtrSet<MachineInstr*, 8> ReMattedInstrs;
+ // ReMatRegs - Keep track of the registers whose def's are remat'ed.
+ BitVector ReMatRegs;
+ ReMatRegs.resize(MRI->getLastVirtReg()+1);
+
+ // DistanceMap - Keep track the distance of a MI from the start of the
+ // current basic block.
+ DenseMap<MachineInstr*, unsigned> DistanceMap;
for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
mbbi != mbbe; ++mbbi) {
+ unsigned Dist = 0;
+ DistanceMap.clear();
for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
mi != me; ) {
MachineBasicBlock::iterator nmi = next(mi);
const TargetInstrDesc &TID = mi->getDesc();
bool FirstTied = true;
+ DistanceMap.insert(std::make_pair(mi, ++Dist));
for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
if (ti == -1)
FirstTied = false;
- assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() &&
+ assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() &&
mi->getOperand(si).isUse() && "two address instruction invalid");
// If the two operands are the same we just remove the use
// should never occur because we are in SSA form.
for (unsigned i = 0; i != mi->getNumOperands(); ++i)
assert((int)i == ti ||
- !mi->getOperand(i).isRegister() ||
+ !mi->getOperand(i).isReg() ||
mi->getOperand(i).getReg() != regA);
#endif
// and C joinable.
// FIXME: This code also works for A := B op C instructions.
if (TID.isCommutable() && mi->getNumOperands() >= 3) {
- assert(mi->getOperand(3-si).isRegister() &&
+ assert(mi->getOperand(3-si).isReg() &&
"Not a proper commutative instruction!");
unsigned regC = mi->getOperand(3-si).getReg();
DOUT << "2addr: COMMUTED TO: " << *NewMI;
// If the instruction changed to commute it, update livevar.
if (NewMI != mi) {
- LV->instructionChanged(mi, NewMI); // Update live variables
+ if (LV)
+ // Update live variables
+ LV->replaceKillInstruction(regC, mi, NewMI);
+
mbbi->insert(mi, NewMI); // Insert the new inst
mbbi->erase(mi); // Nuke the old inst.
mi = NewMI;
+ DistanceMap.insert(std::make_pair(NewMI, Dist));
}
++NumCommuted;
assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
#endif
- if (MachineInstr *New=TII->convertToThreeAddress(mbbi, mi, *LV)) {
+ MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV);
+ if (NewMI) {
DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
- DOUT << "2addr: TO 3-ADDR: " << *New;
+ DOUT << "2addr: TO 3-ADDR: " << *NewMI;
bool Sunk = false;
- if (New->findRegisterUseOperand(regB, false, TRI))
+ if (NewMI->findRegisterUseOperand(regB, false, TRI))
// FIXME: Temporary workaround. If the new instruction doesn't
// uses regB, convertToThreeAddress must have created more
// then one instruction.
- Sunk = Sink3AddrInstruction(mbbi, New, regB, mi);
+ Sunk = Sink3AddrInstruction(mbbi, NewMI, regB, mi);
mbbi->erase(mi); // Nuke the old inst.
if (!Sunk) {
- mi = New;
+ DistanceMap.insert(std::make_pair(NewMI, Dist));
+ mi = NewMI;
nmi = next(mi);
}
}
InstructionRearranged:
- const TargetRegisterClass* rc = MF.getRegInfo().getRegClass(regA);
- MachineInstr *Orig = MRI->getVRegDef(regB);
-
- if (EnableReMat && Orig && TII->isTriviallyReMaterializable(Orig)) {
- TII->reMaterialize(*mbbi, mi, regA, Orig);
- ReMattedInstrs.insert(Orig);
+ const TargetRegisterClass* rc = MRI->getRegClass(regA);
+ MachineInstr *DefMI = MRI->getVRegDef(regB);
+ // If it's safe and profitable, remat the definition instead of
+ // copying it.
+ if (DefMI &&
+ DefMI->getDesc().isAsCheapAsAMove() &&
+ DefMI->isSafeToReMat(TII, regB) &&
+ isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist,DistanceMap)){
+ DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n");
+ TII->reMaterialize(*mbbi, mi, regA, DefMI);
+ ReMatRegs.set(regB);
+ ++NumReMats;
} else {
TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
}
MachineBasicBlock::iterator prevMi = prior(mi);
- DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
// Update live variables for regB.
- LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
+ if (LV) {
+ LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
- // regB is used in this BB.
- varInfoB.UsedBlocks[mbbi->getNumber()] = true;
+ // regB is used in this BB.
+ varInfoB.UsedBlocks[mbbi->getNumber()] = true;
- if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
- LV->addVirtualRegisterKilled(regB, prevMi);
+ if (LV->removeVirtualRegisterKilled(regB, mi))
+ LV->addVirtualRegisterKilled(regB, prevMi);
- if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
- LV->addVirtualRegisterDead(regB, prevMi);
+ if (LV->removeVirtualRegisterDead(regB, mi))
+ LV->addVirtualRegisterDead(regB, prevMi);
+ }
+ DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
+
// Replace all occurences of regB with regA.
for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
- if (mi->getOperand(i).isRegister() &&
+ if (mi->getOperand(i).isReg() &&
mi->getOperand(i).getReg() == regB)
mi->getOperand(i).setReg(regA);
}
}
}
- if (EnableReMat) {
- SmallPtrSet<MachineInstr*, 8>::iterator I = ReMattedInstrs.begin();
- SmallPtrSet<MachineInstr*, 8>::iterator E = ReMattedInstrs.end();
-
- for (; I != E; ++I) {
- MachineInstr *MI = *I;
- bool InstrDead = true;
-
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- const MachineOperand &MO = MI->getOperand(i);
- if (!MO.isRegister())
- continue;
- unsigned MOReg = MO.getReg();
- if (!MOReg)
- continue;
- if (MO.isDef()) {
- if (MO.isImplicit())
- continue;
-
- if (MRI->use_begin(MOReg) != MRI->use_end()) {
- InstrDead = false;
- break;
- }
- }
- }
-
- if (InstrDead && MI->getNumOperands() > 0)
- MI->eraseFromParent();
+ // Some remat'ed instructions are dead.
+ int VReg = ReMatRegs.find_first();
+ while (VReg != -1) {
+ if (MRI->use_empty(VReg)) {
+ MachineInstr *DefMI = MRI->getVRegDef(VReg);
+ DefMI->eraseFromParent();
}
+ VReg = ReMatRegs.find_next(VReg);
}
return MadeChange;
projects / oota-llvm.git / blobdiff