#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/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
using namespace llvm;
STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
+STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted");
STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk");
STATISTIC(NumReMats, "Number of instructions re-materialized");
-
-static cl::opt<bool>
-EnableReMat("two-addr-remat", cl::init(false), cl::Hidden,
- cl::desc("Two-addr conversion should remat when possible."));
+STATISTIC(NumDeletes, "Number of dead instructions deleted");
namespace {
class VISIBILITY_HIDDEN TwoAddressInstructionPass
unsigned Reg,
MachineBasicBlock::iterator OldPos);
- bool isSafeToReMat(unsigned DstReg, MachineInstr *MI);
bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
- MachineInstr *MI, unsigned Loc,
- MachineInstr *DefMI, MachineBasicBlock *MBB,
+ MachineInstr *MI, MachineInstr *DefMI,
+ MachineBasicBlock *MBB, unsigned Loc,
DenseMap<MachineInstr*, unsigned> &DistanceMap);
+
+ bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist,
+ DenseMap<MachineInstr*, unsigned> &DistanceMap,
+ unsigned &LastDef);
+
+ bool isProfitableToCommute(unsigned regB, unsigned regC,
+ MachineInstr *MI, MachineBasicBlock *MBB,
+ unsigned Dist,
+ DenseMap<MachineInstr*, unsigned> &DistanceMap);
+
+ bool CommuteInstruction(MachineBasicBlock::iterator &mi,
+ MachineFunction::iterator &mbbi,
+ unsigned RegC, unsigned Dist,
+ 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);
}
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)
++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)
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;
}
-/// isSafeToReMat - Return true if it's safe to rematerialize the specified
-/// instruction which defined the specified register instead of copying it.
-bool
-TwoAddressInstructionPass::isSafeToReMat(unsigned DstReg, MachineInstr *MI) {
- const TargetInstrDesc &TID = MI->getDesc();
- if (!TID.isAsCheapAsAMove())
- return false;
- bool SawStore = false;
- if (!MI->isSafeToMove(TII, SawStore))
- return false;
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (!MO.isRegister())
- continue;
- // FIXME: For now, do not remat any instruction with register operands.
- // Later on, we can loosen the restriction is the register operands have
- // not been modified between the def and use. Note, this is different from
- // MachineSink because the code in no longer in two-address form (at least
- // partially).
- if (MO.isUse())
- return false;
- else if (!MO.isDead() && MO.getReg() != DstReg)
- return false;
- }
- 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.getReg() == Reg &&
+ if (MO.isReg() && MO.getReg() == Reg &&
(MO.isDef() || TID.getOperandConstraint(i, TOI::TIED_TO) != -1))
// Earlier use is a two-address one.
return true;
bool
TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
const TargetRegisterClass *RC,
- MachineInstr *MI, unsigned Loc,
- MachineInstr *DefMI, MachineBasicBlock *MBB,
- DenseMap<MachineInstr*, unsigned> &DistanceMap) {
- if (DefMI->getParent() != MBB)
- return true;
- // If earlier uses in MBB are not two-address uses, then don't remat.
+ 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();
- if (UseMI->getParent() != MBB)
+ 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();
+}
+
+/// NoUseAfterLastDef - Return true if there are no intervening uses between the
+/// last instruction in the MBB that defines the specified register and the
+/// two-address instruction which is being processed. It also returns the last
+/// def location by reference
+bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg,
+ MachineBasicBlock *MBB, unsigned Dist,
+ DenseMap<MachineInstr*, unsigned> &DistanceMap,
+ unsigned &LastDef) {
+ LastDef = 0;
+ unsigned LastUse = Dist;
+ for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
+ E = MRI->reg_end(); I != E; ++I) {
+ MachineOperand &MO = I.getOperand();
+ MachineInstr *MI = MO.getParent();
+ if (MI->getParent() != MBB)
continue;
- 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;
+ DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
+ if (DI == DistanceMap.end())
+ continue;
+ if (MO.isUse() && DI->second < LastUse)
+ LastUse = DI->second;
+ if (MO.isDef() && DI->second > LastDef)
+ LastDef = DI->second;
+ }
+
+ return !(LastUse > LastDef && LastUse < Dist);
+}
+
+/// isProfitableToReMat - Return true if it's potentially profitable to commute
+/// the two-address instruction that's being processed.
+bool
+TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC,
+ MachineInstr *MI, MachineBasicBlock *MBB,
+ unsigned Dist, DenseMap<MachineInstr*, unsigned> &DistanceMap) {
+ // Determine if it's profitable to commute this two address instruction. In
+ // general, we want no uses between this instruction and the definition of
+ // the two-address register.
+ // e.g.
+ // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
+ // %reg1029<def> = MOV8rr %reg1028
+ // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
+ // insert => %reg1030<def> = MOV8rr %reg1028
+ // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
+ // In this case, it might not be possible to coalesce the second MOV8rr
+ // instruction if the first one is coalesced. So it would be profitable to
+ // commute it:
+ // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
+ // %reg1029<def> = MOV8rr %reg1028
+ // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
+ // insert => %reg1030<def> = MOV8rr %reg1029
+ // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead>
+
+ if (!MI->killsRegister(regC))
+ return false;
+
+ // Ok, we have something like:
+ // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
+ // let's see if it's worth commuting it.
+
+ // If there is a use of regC between its last def (could be livein) and this
+ // instruction, then bail.
+ unsigned LastDefC = 0;
+ if (!NoUseAfterLastDef(regC, MBB, Dist, DistanceMap, LastDefC))
+ return false;
+
+ // If there is a use of regB between its last def (could be livein) and this
+ // instruction, then go ahead and make this transformation.
+ unsigned LastDefB = 0;
+ if (!NoUseAfterLastDef(regB, MBB, Dist, DistanceMap, LastDefB))
+ return true;
+
+ // Since there are no intervening uses for both registers, then commute
+ // if the def of regC is closer. Its live interval is shorter.
+ return LastDefB && LastDefC && LastDefC > LastDefB;
+}
+
+/// CommuteInstruction - Commute a two-address instruction and update the basic
+/// block, distance map, and live variables if needed. Return true if it is
+/// successful.
+bool
+TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi,
+ MachineFunction::iterator &mbbi,
+ unsigned RegC, unsigned Dist,
+ DenseMap<MachineInstr*, unsigned> &DistanceMap) {
+ MachineInstr *MI = mi;
+ DOUT << "2addr: COMMUTING : " << *MI;
+ MachineInstr *NewMI = TII->commuteInstruction(MI);
+
+ if (NewMI == 0) {
+ DOUT << "2addr: COMMUTING FAILED!\n";
+ return false;
}
- return !OtherUse;
+
+ DOUT << "2addr: COMMUTED TO: " << *NewMI;
+ // If the instruction changed to commute it, update livevar.
+ if (NewMI != MI) {
+ 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));
+ }
+ return true;
+}
+
+/// isSafeToDelete - If the specified instruction does not produce any side
+/// effects and all of its defs are dead, then it's safe to delete.
+static bool isSafeToDelete(MachineInstr *MI, const TargetInstrInfo *TII) {
+ const TargetInstrDesc &TID = MI->getDesc();
+ if (TID.mayStore() || TID.isCall())
+ return false;
+ if (TID.isTerminator() || TID.hasUnmodeledSideEffects())
+ return false;
+
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = MI->getOperand(i);
+ if (!MO.isReg() || !MO.isDef())
+ continue;
+ if (!MO.isDead())
+ return false;
+ }
+
+ return true;
}
/// runOnMachineFunction - Reduce two-address instructions to two operands.
MRI = &MF.getRegInfo();
TII = TM.getInstrInfo();
TRI = TM.getRegisterInfo();
- LV = &getAnalysis<LiveVariables>();
+ LV = getAnalysisIfAvailable<LiveVariables>();
bool MadeChange = false;
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
// allow us to coalesce A and B together, eliminating the copy we are
// about to insert.
if (!mi->killsRegister(regB)) {
+ // If regA is dead and the instruction can be deleted, just delete
+ // it so it doesn't clobber regB.
+ if (mi->getOperand(ti).isDead() && isSafeToDelete(mi, TII)) {
+ mbbi->erase(mi); // Nuke the old inst.
+ mi = nmi;
+ ++NumDeletes;
+ break; // Done with this instruction.
+ }
+
// If this instruction is commutative, check to see if C dies. If
// so, swap the B and C operands. This makes the live ranges of A
// 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();
-
if (mi->killsRegister(regC)) {
- DOUT << "2addr: COMMUTING : " << *mi;
- MachineInstr *NewMI = TII->commuteInstruction(mi);
-
- if (NewMI == 0) {
- DOUT << "2addr: COMMUTING FAILED!\n";
- } else {
- DOUT << "2addr: COMMUTED TO: " << *NewMI;
- // If the instruction changed to commute it, update livevar.
- if (NewMI != mi) {
- LV->instructionChanged(mi, NewMI); // Update live variables
- mbbi->insert(mi, NewMI); // Insert the new inst
- mbbi->erase(mi); // Nuke the old inst.
- mi = NewMI;
- DistanceMap.insert(std::make_pair(NewMI, Dist));
- }
-
+ if (CommuteInstruction(mi, mbbi, regC, Dist, DistanceMap)) {
++NumCommuted;
regB = regC;
goto InstructionRearranged;
assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
#endif
- MachineInstr *NewMI = 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: " << *NewMI;
}
}
+ // If it's profitable to commute the instruction, do so.
+ if (TID.isCommutable() && mi->getNumOperands() >= 3) {
+ unsigned regC = mi->getOperand(3-si).getReg();
+ if (isProfitableToCommute(regB, regC, mi, mbbi, Dist, DistanceMap))
+ if (CommuteInstruction(mi, mbbi, regC, Dist, DistanceMap)) {
+ ++NumAggrCommuted;
+ ++NumCommuted;
+ regB = regC;
+ }
+ }
+
InstructionRearranged:
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 (EnableReMat && DefMI &&
- isSafeToReMat(regB, DefMI) &&
- isProfitableToReMat(regB, rc, mi, Dist, DefMI, mbbi,DistanceMap)){
+ 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);
TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
}
- MachineBasicBlock::iterator prevMi = prior(mi);
- DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
+ MachineBasicBlock::iterator prevMI = prior(mi);
+ // Update DistanceMap.
+ DistanceMap.insert(std::make_pair(prevMI, Dist));
+ DistanceMap[mi] = ++Dist;
// 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) {
- // 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);
+ // 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