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(NumCmps, "Number of compares eliminated");
STATISTIC(NumImmFold, "Number of move immediate folded");
STATISTIC(NumLoadFold, "Number of loads folded");
STATISTIC(NumSelects, "Number of selects optimized");
STATISTIC(NumCopiesBitcasts, "Number of copies/bitcasts 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 optimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB);
bool optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB,
SmallPtrSet<MachineInstr*, 8> &LocalMIs);
bool optimizeSelect(MachineInstr *MI);
bool optimizeCopyOrBitcast(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::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;
}
static bool shareSameRegisterFile(const TargetRegisterInfo &TRI,
const TargetRegisterClass *DefRC,
unsigned DefSubReg,
const TargetRegisterClass *SrcRC,
unsigned SrcSubReg) {
if (DefRC == SrcRC)
return true;
unsigned SrcIdx, DefIdx;
if (SrcSubReg && DefSubReg)
return TRI.getCommonSuperRegClass(SrcRC, SrcSubReg, DefRC, DefSubReg,
SrcIdx, DefIdx) != NULL;
if (!SrcSubReg) {
std::swap(DefSubReg, SrcSubReg);
std::swap(DefRC, SrcRC);
}
if (SrcSubReg)
return TRI.getMatchingSuperRegClass(SrcRC, DefRC, SrcSubReg) != NULL;
return TRI.getCommonSubClass(DefRC, SrcRC) != NULL;
}
static bool getCopyOrBitcastDefUseIdx(const MachineInstr &Copy,
unsigned &DefIdx, unsigned &SrcIdx) {
assert((Copy.isCopy() || Copy.isBitcast()) && "Wrong operation type.");
if (Copy.isCopy()) {
if (Copy.getDesc().getNumOperands() != 2)
return false;
DefIdx = 0;
SrcIdx = 1;
assert(Copy.getOperand(DefIdx).isDef() && "Use comes before def!");
return true;
}
if (Copy.getDesc().getNumDefs() != 1)
return false;
SrcIdx = Copy.getDesc().getNumOperands();
for (unsigned OpIdx = 0, EndOpIdx = SrcIdx; OpIdx != EndOpIdx; ++OpIdx) {
const MachineOperand &MO = Copy.getOperand(OpIdx);
if (!MO.isReg() || !MO.getReg())
continue;
if (MO.isDef())
DefIdx = OpIdx;
else if (SrcIdx != EndOpIdx)
return false;
SrcIdx = OpIdx;
}
return true;
}
bool PeepholeOptimizer::optimizeCopyOrBitcast(MachineInstr *MI) {
unsigned DefIdx, SrcIdx;
if (!MI || !getCopyOrBitcastDefUseIdx(*MI, DefIdx, SrcIdx))
return false;
const MachineOperand &MODef = MI->getOperand(DefIdx);
assert(MODef.isReg() && "Copies must be between registers.");
unsigned Def = MODef.getReg();
if (TargetRegisterInfo::isPhysicalRegister(Def))
return false;
const TargetRegisterClass *DefRC = MRI->getRegClass(Def);
unsigned DefSubReg = MODef.getSubReg();
unsigned Src;
unsigned SrcSubReg;
bool ShouldRewrite = false;
MachineInstr *Copy = MI;
const TargetRegisterInfo &TRI = *TM->getRegisterInfo();
do {
unsigned CopyDefIdx, CopySrcIdx;
if (!getCopyOrBitcastDefUseIdx(*Copy, CopyDefIdx, CopySrcIdx))
break;
const MachineOperand &MO = Copy->getOperand(CopySrcIdx);
assert(MO.isReg() && "Copies must be between registers.");
Src = MO.getReg();
if (TargetRegisterInfo::isPhysicalRegister(Src))
break;
const TargetRegisterClass *SrcRC = MRI->getRegClass(Src);
SrcSubReg = MO.getSubReg();
ShouldRewrite = shareSameRegisterFile(TRI, DefRC, DefSubReg, SrcRC,
SrcSubReg);
Copy = MRI->getVRegDef(Src);
} while (!ShouldRewrite && Copy && (Copy->isCopy() || Copy->isBitcast()));
if (!ShouldRewrite || Src == MI->getOperand(SrcIdx).getReg())
return false;
unsigned NewVR = TargetRegisterInfo::isPhysicalRegister(Def) ? Def :
MRI->createVirtualRegister(DefRC);
MachineInstr *NewCopy = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
TII->get(TargetOpcode::COPY), NewVR)
.addReg(Src, 0, SrcSubReg);
NewCopy->getOperand(0).setSubReg(DefSubReg);
MRI->replaceRegWith(Def, NewVR);
MRI->clearKillFlags(NewVR);
MI->eraseFromParent();
++NumCopiesBitcasts;
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() || MI->isCopy()) && optimizeCopyOrBitcast(MI)) ||
(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;
}