PeepholeOptimizer.cpp [plain text]
#define DEBUG_TYPE "peephole-opt"
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetRegisterInfo.h"
using namespace llvm;
static cl::opt<bool>
Aggressive("aggressive-ext-opt", cl::Hidden,
cl::desc("Aggressive extension optimization"));
static cl::opt<bool>
DisablePeephole("disable-peephole", cl::Hidden, cl::init(false),
cl::desc("Disable the peephole optimizer"));
STATISTIC(NumReuse, "Number of extension results reused");
STATISTIC(NumBitcasts, "Number of bitcasts eliminated");
STATISTIC(NumCmps, "Number of compares eliminated");
STATISTIC(NumImmFold, "Number of move immediate folded");
STATISTIC(NumLoadFold, "Number of loads folded");
STATISTIC(NumSelects, "Number of selects optimized");
namespace {
class PeepholeOptimizer : public MachineFunctionPass {
const TargetMachine *TM;
const TargetInstrInfo *TII;
MachineRegisterInfo *MRI;
MachineDominatorTree *DT;
public:
static char ID; PeepholeOptimizer() : MachineFunctionPass(ID) {
initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry());
}
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
MachineFunctionPass::getAnalysisUsage(AU);
if (Aggressive) {
AU.addRequired<MachineDominatorTree>();
AU.addPreserved<MachineDominatorTree>();
}
}
private:
bool optimizeBitcastInstr(MachineInstr *MI, MachineBasicBlock *MBB);
bool optimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB);
bool optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB,
SmallPtrSet<MachineInstr*, 8> &LocalMIs);
bool optimizeSelect(MachineInstr *MI);
bool isMoveImmediate(MachineInstr *MI,
SmallSet<unsigned, 4> &ImmDefRegs,
DenseMap<unsigned, MachineInstr*> &ImmDefMIs);
bool foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB,
SmallSet<unsigned, 4> &ImmDefRegs,
DenseMap<unsigned, MachineInstr*> &ImmDefMIs);
bool isLoadFoldable(MachineInstr *MI, unsigned &FoldAsLoadDefReg);
};
}
char PeepholeOptimizer::ID = 0;
char &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID;
INITIALIZE_PASS_BEGIN(PeepholeOptimizer, "peephole-opts",
"Peephole Optimizations", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_END(PeepholeOptimizer, "peephole-opts",
"Peephole Optimizations", false, false)
bool PeepholeOptimizer::
optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB,
SmallPtrSet<MachineInstr*, 8> &LocalMIs) {
unsigned SrcReg, DstReg, SubIdx;
if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx))
return false;
if (TargetRegisterInfo::isPhysicalRegister(DstReg) ||
TargetRegisterInfo::isPhysicalRegister(SrcReg))
return false;
if (MRI->hasOneNonDBGUse(SrcReg))
return false;
const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
DstRC = TM->getRegisterInfo()->getSubClassWithSubReg(DstRC, SubIdx);
if (!DstRC)
return false;
bool UseSrcSubIdx = TM->getRegisterInfo()->
getSubClassWithSubReg(MRI->getRegClass(SrcReg), SubIdx) != 0;
SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs;
for (MachineRegisterInfo::use_nodbg_iterator
UI = MRI->use_nodbg_begin(DstReg), UE = MRI->use_nodbg_end();
UI != UE; ++UI)
ReachedBBs.insert(UI->getParent());
SmallVector<MachineOperand*, 8> Uses;
SmallVector<MachineOperand*, 8> ExtendedUses;
bool ExtendLife = true;
for (MachineRegisterInfo::use_nodbg_iterator
UI = MRI->use_nodbg_begin(SrcReg), UE = MRI->use_nodbg_end();
UI != UE; ++UI) {
MachineOperand &UseMO = UI.getOperand();
MachineInstr *UseMI = &*UI;
if (UseMI == MI)
continue;
if (UseMI->isPHI()) {
ExtendLife = false;
continue;
}
if (UseSrcSubIdx && UseMO.getSubReg() != SubIdx)
continue;
if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG)
continue;
MachineBasicBlock *UseMBB = UseMI->getParent();
if (UseMBB == MBB) {
if (!LocalMIs.count(UseMI))
Uses.push_back(&UseMO);
} else if (ReachedBBs.count(UseMBB)) {
Uses.push_back(&UseMO);
} else if (Aggressive && DT->dominates(MBB, UseMBB)) {
ExtendedUses.push_back(&UseMO);
} else {
ExtendLife = false;
break;
}
}
if (ExtendLife && !ExtendedUses.empty())
std::copy(ExtendedUses.begin(), ExtendedUses.end(),
std::back_inserter(Uses));
bool Changed = false;
if (!Uses.empty()) {
SmallPtrSet<MachineBasicBlock*, 4> PHIBBs;
for (MachineRegisterInfo::use_nodbg_iterator
UI = MRI->use_nodbg_begin(DstReg), UE = MRI->use_nodbg_end();
UI != UE; ++UI)
if (UI->isPHI())
PHIBBs.insert(UI->getParent());
const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
MachineOperand *UseMO = Uses[i];
MachineInstr *UseMI = UseMO->getParent();
MachineBasicBlock *UseMBB = UseMI->getParent();
if (PHIBBs.count(UseMBB))
continue;
if (!Changed) {
MRI->clearKillFlags(DstReg);
MRI->constrainRegClass(DstReg, DstRC);
}
unsigned NewVR = MRI->createVirtualRegister(RC);
MachineInstr *Copy = BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(),
TII->get(TargetOpcode::COPY), NewVR)
.addReg(DstReg, 0, SubIdx);
if (UseSrcSubIdx) {
Copy->getOperand(0).setSubReg(SubIdx);
Copy->getOperand(0).setIsUndef();
}
UseMO->setReg(NewVR);
++NumReuse;
Changed = true;
}
}
return Changed;
}
bool PeepholeOptimizer::optimizeBitcastInstr(MachineInstr *MI,
MachineBasicBlock *MBB) {
unsigned NumDefs = MI->getDesc().getNumDefs();
unsigned NumSrcs = MI->getDesc().getNumOperands() - NumDefs;
if (NumDefs != 1)
return false;
unsigned Def = 0;
unsigned Src = 0;
for (unsigned i = 0, e = NumDefs + NumSrcs; i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg())
continue;
unsigned Reg = MO.getReg();
if (!Reg)
continue;
if (MO.isDef())
Def = Reg;
else if (Src)
return false;
else
Src = Reg;
}
assert(Def && Src && "Malformed bitcast instruction!");
MachineInstr *DefMI = MRI->getVRegDef(Src);
if (!DefMI || !DefMI->isBitcast())
return false;
unsigned SrcSrc = 0;
NumDefs = DefMI->getDesc().getNumDefs();
NumSrcs = DefMI->getDesc().getNumOperands() - NumDefs;
if (NumDefs != 1)
return false;
for (unsigned i = 0, e = NumDefs + NumSrcs; i != e; ++i) {
const MachineOperand &MO = DefMI->getOperand(i);
if (!MO.isReg() || MO.isDef())
continue;
unsigned Reg = MO.getReg();
if (!Reg)
continue;
if (!MO.isDef()) {
if (SrcSrc)
return false;
else
SrcSrc = Reg;
}
}
if (MRI->getRegClass(SrcSrc) != MRI->getRegClass(Def))
return false;
MRI->replaceRegWith(Def, SrcSrc);
MRI->clearKillFlags(SrcSrc);
MI->eraseFromParent();
++NumBitcasts;
return true;
}
bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr *MI,
MachineBasicBlock *MBB) {
unsigned SrcReg, SrcReg2;
int CmpMask, CmpValue;
if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) ||
TargetRegisterInfo::isPhysicalRegister(SrcReg) ||
(SrcReg2 != 0 && TargetRegisterInfo::isPhysicalRegister(SrcReg2)))
return false;
if (TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) {
++NumCmps;
return true;
}
return false;
}
bool PeepholeOptimizer::optimizeSelect(MachineInstr *MI) {
unsigned TrueOp = 0;
unsigned FalseOp = 0;
bool Optimizable = false;
SmallVector<MachineOperand, 4> Cond;
if (TII->analyzeSelect(MI, Cond, TrueOp, FalseOp, Optimizable))
return false;
if (!Optimizable)
return false;
if (!TII->optimizeSelect(MI))
return false;
MI->eraseFromParent();
++NumSelects;
return true;
}
bool PeepholeOptimizer::isLoadFoldable(MachineInstr *MI,
unsigned &FoldAsLoadDefReg) {
if (!MI->canFoldAsLoad() || !MI->mayLoad())
return false;
const MCInstrDesc &MCID = MI->getDesc();
if (MCID.getNumDefs() != 1)
return false;
unsigned Reg = MI->getOperand(0).getReg();
if (!MI->getOperand(0).getSubReg() &&
TargetRegisterInfo::isVirtualRegister(Reg) &&
MRI->hasOneUse(Reg)) {
FoldAsLoadDefReg = Reg;
return true;
}
return false;
}
bool PeepholeOptimizer::isMoveImmediate(MachineInstr *MI,
SmallSet<unsigned, 4> &ImmDefRegs,
DenseMap<unsigned, MachineInstr*> &ImmDefMIs) {
const MCInstrDesc &MCID = MI->getDesc();
if (!MI->isMoveImmediate())
return false;
if (MCID.getNumDefs() != 1)
return false;
unsigned Reg = MI->getOperand(0).getReg();
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
ImmDefMIs.insert(std::make_pair(Reg, MI));
ImmDefRegs.insert(Reg);
return true;
}
return false;
}
bool PeepholeOptimizer::foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB,
SmallSet<unsigned, 4> &ImmDefRegs,
DenseMap<unsigned, MachineInstr*> &ImmDefMIs) {
for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || MO.isDef())
continue;
unsigned Reg = MO.getReg();
if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
if (ImmDefRegs.count(Reg) == 0)
continue;
DenseMap<unsigned, MachineInstr*>::iterator II = ImmDefMIs.find(Reg);
assert(II != ImmDefMIs.end());
if (TII->FoldImmediate(MI, II->second, Reg, MRI)) {
++NumImmFold;
return true;
}
}
return false;
}
bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) {
DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n");
DEBUG(dbgs() << "********** Function: " << MF.getName() << '\n');
if (DisablePeephole)
return false;
TM = &MF.getTarget();
TII = TM->getInstrInfo();
MRI = &MF.getRegInfo();
DT = Aggressive ? &getAnalysis<MachineDominatorTree>() : 0;
bool Changed = false;
SmallPtrSet<MachineInstr*, 8> LocalMIs;
SmallSet<unsigned, 4> ImmDefRegs;
DenseMap<unsigned, MachineInstr*> ImmDefMIs;
unsigned FoldAsLoadDefReg;
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
MachineBasicBlock *MBB = &*I;
bool SeenMoveImm = false;
LocalMIs.clear();
ImmDefRegs.clear();
ImmDefMIs.clear();
FoldAsLoadDefReg = 0;
for (MachineBasicBlock::iterator
MII = I->begin(), MIE = I->end(); MII != MIE; ) {
MachineInstr *MI = &*MII;
++MII;
LocalMIs.insert(MI);
if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() ||
MI->isKill() || MI->isInlineAsm() || MI->isDebugValue() ||
MI->hasUnmodeledSideEffects()) {
FoldAsLoadDefReg = 0;
continue;
}
if (MI->mayStore() || MI->isCall())
FoldAsLoadDefReg = 0;
if ((MI->isBitcast() && optimizeBitcastInstr(MI, MBB)) ||
(MI->isCompare() && optimizeCmpInstr(MI, MBB)) ||
(MI->isSelect() && optimizeSelect(MI))) {
LocalMIs.erase(MI);
Changed = true;
continue;
}
if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) {
SeenMoveImm = true;
} else {
Changed |= optimizeExtInstr(MI, MBB, LocalMIs);
MII = MI;
++MII;
if (SeenMoveImm)
Changed |= foldImmediate(MI, MBB, ImmDefRegs, ImmDefMIs);
}
if (!isLoadFoldable(MI, FoldAsLoadDefReg) && FoldAsLoadDefReg) {
MachineInstr *DefMI = 0;
MachineInstr *FoldMI = TII->optimizeLoadInstr(MI, MRI,
FoldAsLoadDefReg, DefMI);
if (FoldMI) {
DEBUG(dbgs() << "Replacing: " << *MI);
DEBUG(dbgs() << " With: " << *FoldMI);
LocalMIs.erase(MI);
LocalMIs.erase(DefMI);
LocalMIs.insert(FoldMI);
MI->eraseFromParent();
DefMI->eraseFromParent();
++NumLoadFold;
Changed = true;
continue;
}
}
}
}
return Changed;
}