MachineCombiner.cpp [plain text]
#define DEBUG_TYPE "machine-combiner"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MachineTraceMetrics.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
using namespace llvm;
STATISTIC(NumInstCombined, "Number of machineinst combined");
namespace {
class MachineCombiner : public MachineFunctionPass {
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
MCSchedModel SchedModel;
MachineRegisterInfo *MRI;
MachineTraceMetrics *Traces;
MachineTraceMetrics::Ensemble *MinInstr;
TargetSchedModel TSchedModel;
bool OptSize;
public:
static char ID;
MachineCombiner() : MachineFunctionPass(ID) {
initializeMachineCombinerPass(*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override;
bool runOnMachineFunction(MachineFunction &MF) override;
const char *getPassName() const override { return "Machine InstCombiner"; }
private:
bool doSubstitute(unsigned NewSize, unsigned OldSize);
bool combineInstructions(MachineBasicBlock *);
MachineInstr *getOperandDef(const MachineOperand &MO);
unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
MachineTraceMetrics::Trace BlockTrace);
unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
MachineTraceMetrics::Trace BlockTrace);
bool
improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
MachineTraceMetrics::Trace BlockTrace,
SmallVectorImpl<MachineInstr *> &InsInstrs,
DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
bool NewCodeHasLessInsts);
bool preservesResourceLen(MachineBasicBlock *MBB,
MachineTraceMetrics::Trace BlockTrace,
SmallVectorImpl<MachineInstr *> &InsInstrs,
SmallVectorImpl<MachineInstr *> &DelInstrs);
void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
};
}
char MachineCombiner::ID = 0;
char &llvm::MachineCombinerID = MachineCombiner::ID;
INITIALIZE_PASS_BEGIN(MachineCombiner, "machine-combiner",
"Machine InstCombiner", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
INITIALIZE_PASS_END(MachineCombiner, "machine-combiner", "Machine InstCombiner",
false, false)
void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addPreserved<MachineDominatorTree>();
AU.addPreserved<MachineLoopInfo>();
AU.addRequired<MachineTraceMetrics>();
AU.addPreserved<MachineTraceMetrics>();
MachineFunctionPass::getAnalysisUsage(AU);
}
MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
MachineInstr *DefInstr = nullptr;
if (MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
DefInstr = MRI->getUniqueVRegDef(MO.getReg());
if (DefInstr && DefInstr->isPHI())
DefInstr = nullptr;
return DefInstr;
}
unsigned
MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
MachineTraceMetrics::Trace BlockTrace) {
SmallVector<unsigned, 16> InstrDepth;
assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
"Missing machine model\n");
for (auto *InstrPtr : InsInstrs) { unsigned IDepth = 0;
DEBUG(dbgs() << "NEW INSTR "; InstrPtr->dump(); dbgs() << "\n";);
for (const MachineOperand &MO : InstrPtr->operands()) {
if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
continue;
if (!MO.isUse())
continue;
unsigned DepthOp = 0;
unsigned LatencyOp = 0;
DenseMap<unsigned, unsigned>::iterator II =
InstrIdxForVirtReg.find(MO.getReg());
if (II != InstrIdxForVirtReg.end()) {
assert(II->second < InstrDepth.size() && "Bad Index");
MachineInstr *DefInstr = InsInstrs[II->second];
assert(DefInstr &&
"There must be a definition for a new virtual register");
DepthOp = InstrDepth[II->second];
LatencyOp = TSchedModel.computeOperandLatency(
DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
} else {
MachineInstr *DefInstr = getOperandDef(MO);
if (DefInstr) {
DepthOp = BlockTrace.getInstrCycles(DefInstr).Depth;
LatencyOp = TSchedModel.computeOperandLatency(
DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
}
}
IDepth = std::max(IDepth, DepthOp + LatencyOp);
}
InstrDepth.push_back(IDepth);
}
unsigned NewRootIdx = InsInstrs.size() - 1;
return InstrDepth[NewRootIdx];
}
unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
MachineTraceMetrics::Trace BlockTrace) {
assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
"Missing machine model\n");
unsigned NewRootLatency = 0;
for (const MachineOperand &MO : NewRoot->operands()) {
if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
continue;
if (!MO.isDef())
continue;
MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
RI++;
MachineInstr *UseMO = RI->getParent();
unsigned LatencyOp = 0;
if (UseMO && BlockTrace.isDepInTrace(Root, UseMO)) {
LatencyOp = TSchedModel.computeOperandLatency(
NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
UseMO->findRegisterUseOperandIdx(MO.getReg()));
} else {
LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
}
NewRootLatency = std::max(NewRootLatency, LatencyOp);
}
return NewRootLatency;
}
bool MachineCombiner::improvesCriticalPathLen(
MachineBasicBlock *MBB, MachineInstr *Root,
MachineTraceMetrics::Trace BlockTrace,
SmallVectorImpl<MachineInstr *> &InsInstrs,
DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
bool NewCodeHasLessInsts) {
assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
"Missing machine model\n");
unsigned NewRootIdx = InsInstrs.size() - 1;
MachineInstr *NewRoot = InsInstrs[NewRootIdx];
unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
unsigned NewRootLatency = getLatency(Root, NewRoot, BlockTrace);
unsigned RootDepth = BlockTrace.getInstrCycles(Root).Depth;
unsigned RootLatency = TSchedModel.computeInstrLatency(Root);
unsigned RootSlack = BlockTrace.getInstrSlack(Root);
DEBUG(dbgs() << "DEPENDENCE DATA FOR " << Root << "\n";
dbgs() << " NewRootDepth: " << NewRootDepth
<< " NewRootLatency: " << NewRootLatency << "\n";
dbgs() << " RootDepth: " << RootDepth << " RootLatency: " << RootLatency
<< " RootSlack: " << RootSlack << "\n";
dbgs() << " NewRootDepth + NewRootLatency = "
<< NewRootDepth + NewRootLatency << "\n";
dbgs() << " RootDepth + RootLatency + RootSlack = "
<< RootDepth + RootLatency + RootSlack << "\n";);
unsigned NewCycleCount = NewRootDepth + NewRootLatency;
unsigned OldCycleCount = RootDepth + RootLatency + RootSlack;
if (NewCodeHasLessInsts)
return NewCycleCount <= OldCycleCount;
else
return NewCycleCount < OldCycleCount;
}
void MachineCombiner::instr2instrSC(
SmallVectorImpl<MachineInstr *> &Instrs,
SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
for (auto *InstrPtr : Instrs) {
unsigned Opc = InstrPtr->getOpcode();
unsigned Idx = TII->get(Opc).getSchedClass();
const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
InstrsSC.push_back(SC);
}
}
bool MachineCombiner::preservesResourceLen(
MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
SmallVectorImpl<MachineInstr *> &InsInstrs,
SmallVectorImpl<MachineInstr *> &DelInstrs) {
if (!TSchedModel.hasInstrSchedModel())
return true;
SmallVector <const MachineBasicBlock *, 1> MBBarr;
MBBarr.push_back(MBB);
unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
instr2instrSC(InsInstrs, InsInstrsSC);
instr2instrSC(DelInstrs, DelInstrsSC);
ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
unsigned ResLenAfterCombine =
BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
DEBUG(dbgs() << "RESOURCE DATA: \n";
dbgs() << " resource len before: " << ResLenBeforeCombine
<< " after: " << ResLenAfterCombine << "\n";);
return ResLenAfterCombine <= ResLenBeforeCombine;
}
bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
if (OptSize && (NewSize < OldSize))
return true;
if (!TSchedModel.hasInstrSchedModelOrItineraries())
return true;
return false;
}
bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
bool Changed = false;
DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
auto BlockIter = MBB->begin();
while (BlockIter != MBB->end()) {
auto &MI = *BlockIter++;
DEBUG(dbgs() << "INSTR "; MI.dump(); dbgs() << "\n";);
SmallVector<MachineCombinerPattern, 16> Patterns;
if (TII->getMachineCombinerPatterns(MI, Patterns)) {
for (auto P : Patterns) {
SmallVector<MachineInstr *, 16> InsInstrs;
SmallVector<MachineInstr *, 16> DelInstrs;
DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
if (!MinInstr)
MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
Traces->verifyAnalysis();
TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
InstrIdxForVirtReg);
unsigned NewInstCount = InsInstrs.size();
unsigned OldInstCount = DelInstrs.size();
if (!NewInstCount)
continue;
if (doSubstitute(NewInstCount, OldInstCount) ||
(improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs,
InstrIdxForVirtReg,
NewInstCount < OldInstCount) &&
preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs))) {
for (auto *InstrPtr : InsInstrs)
MBB->insert((MachineBasicBlock::iterator) &MI, InstrPtr);
for (auto *InstrPtr : DelInstrs)
InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
Changed = true;
++NumInstCombined;
Traces->invalidate(MBB);
Traces->verifyAnalysis();
break;
} else {
MachineFunction *MF = MBB->getParent();
for (auto *InstrPtr : InsInstrs)
MF->DeleteMachineInstr(InstrPtr);
}
InstrIdxForVirtReg.clear();
}
}
}
return Changed;
}
bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
const TargetSubtargetInfo &STI = MF.getSubtarget();
TII = STI.getInstrInfo();
TRI = STI.getRegisterInfo();
SchedModel = STI.getSchedModel();
TSchedModel.init(SchedModel, &STI, TII);
MRI = &MF.getRegInfo();
Traces = &getAnalysis<MachineTraceMetrics>();
MinInstr = nullptr;
OptSize = MF.getFunction()->optForSize();
DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
if (!TII->useMachineCombiner()) {
DEBUG(dbgs() << " Skipping pass: Target does not support machine combiner\n");
return false;
}
bool Changed = false;
for (auto &MBB : MF)
Changed |= combineInstructions(&MBB);
return Changed;
}