// The machine combiner pass uses machine trace metrics to ensure the combined
// instructions does not lengthen the critical path or the resource depth.
//===----------------------------------------------------------------------===//
+
#define DEBUG_TYPE "machine-combiner"
#include "llvm/ADT/Statistic.h"
unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
MachineTraceMetrics::Trace BlockTrace);
bool
- preservesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
+ improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
MachineTraceMetrics::Trace BlockTrace,
SmallVectorImpl<MachineInstr *> &InsInstrs,
- DenseMap<unsigned, unsigned> &InstrIdxForVirtReg);
+ DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
+ bool NewCodeHasLessInsts);
bool preservesResourceLen(MachineBasicBlock *MBB,
MachineTraceMetrics::Trace BlockTrace,
SmallVectorImpl<MachineInstr *> &InsInstrs,
MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
MachineTraceMetrics::Trace BlockTrace) {
-
SmallVector<unsigned, 16> InstrDepth;
- assert(TSchedModel.hasInstrSchedModel() && "Missing machine model\n");
+ assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
+ "Missing machine model\n");
// For each instruction in the new sequence compute the depth based on the
// operands. Use the trace information when possible. For new operands which
/// \returns Latency of \p NewRoot
unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
MachineTraceMetrics::Trace BlockTrace) {
-
- assert(TSchedModel.hasInstrSchedModel() && "Missing machine model\n");
+ assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
+ "Missing machine model\n");
// Check each definition in NewRoot and compute the latency
unsigned NewRootLatency = 0;
NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
UseMO->findRegisterUseOperandIdx(MO.getReg()));
} else {
- LatencyOp = TSchedModel.computeInstrLatency(NewRoot->getOpcode());
+ LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
}
NewRootLatency = std::max(NewRootLatency, LatencyOp);
}
return NewRootLatency;
}
-/// True when the new instruction sequence does not
-/// lengthen the critical path. The DAGCombine code sequence ends in MI
-/// (Machine Instruction) Root. The new code sequence ends in MI NewRoot. A
-/// necessary condition for the new sequence to replace the old sequence is that
-/// it cannot lengthen the critical path. This is decided by the formula
+/// True when the new instruction sequence does not lengthen the critical path
+/// and the new sequence has less instructions or the new sequence improves the
+/// critical path.
+/// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
+/// The new code sequence ends in MI NewRoot. A necessary condition for the new
+/// sequence to replace the old sequence is that it cannot lengthen the critical
+/// path. This is decided by the formula:
/// (NewRootDepth + NewRootLatency) <= (RootDepth + RootLatency + RootSlack)).
-/// The slack is the number of cycles Root can be delayed before the critical
-/// patch becomes longer.
-bool MachineCombiner::preservesCriticalPathLen(
+/// If the new sequence has an equal length critical path but does not reduce
+/// the number of instructions (NewCodeHasLessInsts is false), then it is not
+/// considered an improvement. The slack is the number of cycles Root can be
+/// delayed before the critical patch becomes longer.
+bool MachineCombiner::improvesCriticalPathLen(
MachineBasicBlock *MBB, MachineInstr *Root,
MachineTraceMetrics::Trace BlockTrace,
SmallVectorImpl<MachineInstr *> &InsInstrs,
- DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) {
-
- assert(TSchedModel.hasInstrSchedModel() && "Missing machine model\n");
- // NewRoot is the last instruction in the \p InsInstrs vector
- // Get depth and latency of NewRoot
+ DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
+ bool NewCodeHasLessInsts) {
+ assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
+ "Missing machine model\n");
+ // NewRoot is the last instruction in the \p InsInstrs vector.
+ // Get depth and latency of NewRoot.
unsigned NewRootIdx = InsInstrs.size() - 1;
MachineInstr *NewRoot = InsInstrs[NewRootIdx];
unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
unsigned NewRootLatency = getLatency(Root, NewRoot, BlockTrace);
- // Get depth, latency and slack of Root
+ // Get depth, latency and slack of Root.
unsigned RootDepth = BlockTrace.getInstrCycles(Root).Depth;
unsigned RootLatency = TSchedModel.computeInstrLatency(Root);
unsigned RootSlack = BlockTrace.getInstrSlack(Root);
<< " NewRootLatency: " << NewRootLatency << "\n";
dbgs() << " RootDepth: " << RootDepth << " RootLatency: " << RootLatency
<< " RootSlack: " << RootSlack << "\n";
- dbgs() << " NewRootDepth + NewRootLatency "
+ dbgs() << " NewRootDepth + NewRootLatency = "
<< NewRootDepth + NewRootLatency << "\n";
- dbgs() << " RootDepth + RootLatency + RootSlack "
+ dbgs() << " RootDepth + RootLatency + RootSlack = "
<< RootDepth + RootLatency + RootSlack << "\n";);
- /// True when the new sequence does not lengthen the critical path.
- return ((NewRootDepth + NewRootLatency) <=
- (RootDepth + RootLatency + RootSlack));
+ unsigned NewCycleCount = NewRootDepth + NewRootLatency;
+ unsigned OldCycleCount = RootDepth + RootLatency + RootSlack;
+
+ if (NewCodeHasLessInsts)
+ return NewCycleCount <= OldCycleCount;
+ else
+ return NewCycleCount < OldCycleCount;
}
/// helper routine to convert instructions into SC
InstrsSC.push_back(SC);
}
}
+
/// True when the new instructions do not increase resource length
bool MachineCombiner::preservesResourceLen(
MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
SmallVectorImpl<MachineInstr *> &InsInstrs,
SmallVectorImpl<MachineInstr *> &DelInstrs) {
+ if (!TSchedModel.hasInstrSchedModel())
+ return true;
// Compute current resource length
ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
- // Compute new resource length
+ // Compute new resource length.
unsigned ResLenAfterCombine =
BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
if (OptSize && (NewSize < OldSize))
return true;
- if (!TSchedModel.hasInstrSchedModel())
+ if (!TSchedModel.hasInstrSchedModelOrItineraries())
return true;
return false;
}
auto &MI = *BlockIter++;
DEBUG(dbgs() << "INSTR "; MI.dump(); dbgs() << "\n";);
- SmallVector<MachineCombinerPattern::MC_PATTERN, 16> Pattern;
+ SmallVector<MachineCombinerPattern::MC_PATTERN, 16> Patterns;
// The motivating example is:
//
// MUL Other MUL_op1 MUL_op2 Other
//
// The algorithm does not try to evaluate all patterns and pick the best.
// This is only an artificial restriction though. In practice there is
- // mostly one pattern and hasPattern() can order patterns based on an
- // internal cost heuristic.
+ // mostly one pattern, and getMachineCombinerPatterns() can order patterns
+ // based on an internal cost heuristic.
- if (TII->hasPattern(MI, Pattern)) {
- for (auto P : Pattern) {
+ if (TII->getMachineCombinerPatterns(MI, Patterns)) {
+ for (auto P : Patterns) {
SmallVector<MachineInstr *, 16> InsInstrs;
SmallVector<MachineInstr *, 16> DelInstrs;
DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
Traces->verifyAnalysis();
TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
InstrIdxForVirtReg);
+ unsigned NewInstCount = InsInstrs.size();
+ unsigned OldInstCount = DelInstrs.size();
// Found pattern, but did not generate alternative sequence.
// This can happen e.g. when an immediate could not be materialized
// in a single instruction.
- if (!InsInstrs.size())
+ if (!NewInstCount)
continue;
// Substitute when we optimize for codesize and the new sequence has
// fewer instructions OR
// the new sequence neither lengthens the critical path nor increases
// resource pressure.
- if (doSubstitute(InsInstrs.size(), DelInstrs.size()) ||
- (preservesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs,
- InstrIdxForVirtReg) &&
+ 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,
- (MachineInstr *)InstrPtr);
+ MBB->insert((MachineBasicBlock::iterator) &MI, InstrPtr);
for (auto *InstrPtr : DelInstrs)
InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
Traces->invalidate(MBB);
Traces->verifyAnalysis();
- // Eagerly stop after the first pattern fired
+ // Eagerly stop after the first pattern fires.
break;
} else {
// Cleanup instructions of the alternative code sequence. There is no
// use for them.
- for (auto *InstrPtr : InsInstrs) {
- MachineFunction *MF = MBB->getParent();
- MF->DeleteMachineInstr((MachineInstr *)InstrPtr);
- }
+ MachineFunction *MF = MBB->getParent();
+ for (auto *InstrPtr : InsInstrs)
+ MF->DeleteMachineInstr(InstrPtr);
}
InstrIdxForVirtReg.clear();
}
TSchedModel.init(SchedModel, &STI, TII);
MRI = &MF.getRegInfo();
Traces = &getAnalysis<MachineTraceMetrics>();
- MinInstr = 0;
-
- OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
+ MinInstr = nullptr;
+ OptSize = MF.getFunction()->optForSize();
DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
if (!TII->useMachineCombiner()) {
projects / oota-llvm.git / blobdiff