1 //===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // The machine combiner pass uses machine trace metrics to ensure the combined
11 // instructions does not lengthen the critical path or the resource depth.
12 //===----------------------------------------------------------------------===//
13 #define DEBUG_TYPE "machine-combiner"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/CodeGen/MachineDominators.h"
18 #include "llvm/CodeGen/MachineFunction.h"
19 #include "llvm/CodeGen/MachineFunctionPass.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/CodeGen/MachineLoopInfo.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/CodeGen/MachineTraceMetrics.h"
24 #include "llvm/CodeGen/Passes.h"
25 #include "llvm/CodeGen/TargetSchedule.h"
26 #include "llvm/Support/CommandLine.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include "llvm/Target/TargetInstrInfo.h"
30 #include "llvm/Target/TargetRegisterInfo.h"
31 #include "llvm/Target/TargetSubtargetInfo.h"
35 STATISTIC(NumInstCombined, "Number of machineinst combined");
38 class MachineCombiner : public MachineFunctionPass {
39 const TargetInstrInfo *TII;
40 const TargetRegisterInfo *TRI;
41 MCSchedModel SchedModel;
42 MachineRegisterInfo *MRI;
43 MachineTraceMetrics *Traces;
44 MachineTraceMetrics::Ensemble *MinInstr;
46 TargetSchedModel TSchedModel;
48 /// True if optimizing for code size.
53 MachineCombiner() : MachineFunctionPass(ID) {
54 initializeMachineCombinerPass(*PassRegistry::getPassRegistry());
56 void getAnalysisUsage(AnalysisUsage &AU) const override;
57 bool runOnMachineFunction(MachineFunction &MF) override;
58 const char *getPassName() const override { return "Machine InstCombiner"; }
61 bool doSubstitute(unsigned NewSize, unsigned OldSize);
62 bool combineInstructions(MachineBasicBlock *);
63 MachineInstr *getOperandDef(const MachineOperand &MO);
64 unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
65 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
66 MachineTraceMetrics::Trace BlockTrace);
67 unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
68 MachineTraceMetrics::Trace BlockTrace);
70 improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
71 MachineTraceMetrics::Trace BlockTrace,
72 SmallVectorImpl<MachineInstr *> &InsInstrs,
73 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
74 bool NewCodeHasLessInsts);
75 bool preservesResourceLen(MachineBasicBlock *MBB,
76 MachineTraceMetrics::Trace BlockTrace,
77 SmallVectorImpl<MachineInstr *> &InsInstrs,
78 SmallVectorImpl<MachineInstr *> &DelInstrs);
79 void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
80 SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
84 char MachineCombiner::ID = 0;
85 char &llvm::MachineCombinerID = MachineCombiner::ID;
87 INITIALIZE_PASS_BEGIN(MachineCombiner, "machine-combiner",
88 "Machine InstCombiner", false, false)
89 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
90 INITIALIZE_PASS_END(MachineCombiner, "machine-combiner", "Machine InstCombiner",
93 void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
95 AU.addPreserved<MachineDominatorTree>();
96 AU.addPreserved<MachineLoopInfo>();
97 AU.addRequired<MachineTraceMetrics>();
98 AU.addPreserved<MachineTraceMetrics>();
99 MachineFunctionPass::getAnalysisUsage(AU);
102 MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
103 MachineInstr *DefInstr = nullptr;
104 // We need a virtual register definition.
105 if (MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
106 DefInstr = MRI->getUniqueVRegDef(MO.getReg());
107 // PHI's have no depth etc.
108 if (DefInstr && DefInstr->isPHI())
113 /// Computes depth of instructions in vector \InsInstr.
115 /// \param InsInstrs is a vector of machine instructions
116 /// \param InstrIdxForVirtReg is a dense map of virtual register to index
117 /// of defining machine instruction in \p InsInstrs
118 /// \param BlockTrace is a trace of machine instructions
120 /// \returns Depth of last instruction in \InsInstrs ("NewRoot")
122 MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
123 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
124 MachineTraceMetrics::Trace BlockTrace) {
126 SmallVector<unsigned, 16> InstrDepth;
127 assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
128 "Missing machine model\n");
130 // For each instruction in the new sequence compute the depth based on the
131 // operands. Use the trace information when possible. For new operands which
132 // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
133 for (auto *InstrPtr : InsInstrs) { // for each Use
135 DEBUG(dbgs() << "NEW INSTR "; InstrPtr->dump(); dbgs() << "\n";);
136 for (const MachineOperand &MO : InstrPtr->operands()) {
137 // Check for virtual register operand.
138 if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
142 unsigned DepthOp = 0;
143 unsigned LatencyOp = 0;
144 DenseMap<unsigned, unsigned>::iterator II =
145 InstrIdxForVirtReg.find(MO.getReg());
146 if (II != InstrIdxForVirtReg.end()) {
147 // Operand is new virtual register not in trace
148 assert(II->second < InstrDepth.size() && "Bad Index");
149 MachineInstr *DefInstr = InsInstrs[II->second];
151 "There must be a definition for a new virtual register");
152 DepthOp = InstrDepth[II->second];
153 LatencyOp = TSchedModel.computeOperandLatency(
154 DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
155 InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
157 MachineInstr *DefInstr = getOperandDef(MO);
159 DepthOp = BlockTrace.getInstrCycles(DefInstr).Depth;
160 LatencyOp = TSchedModel.computeOperandLatency(
161 DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
162 InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
165 IDepth = std::max(IDepth, DepthOp + LatencyOp);
167 InstrDepth.push_back(IDepth);
169 unsigned NewRootIdx = InsInstrs.size() - 1;
170 return InstrDepth[NewRootIdx];
173 /// Computes instruction latency as max of latency of defined operands.
175 /// \param Root is a machine instruction that could be replaced by NewRoot.
176 /// It is used to compute a more accurate latency information for NewRoot in
177 /// case there is a dependent instruction in the same trace (\p BlockTrace)
178 /// \param NewRoot is the instruction for which the latency is computed
179 /// \param BlockTrace is a trace of machine instructions
181 /// \returns Latency of \p NewRoot
182 unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
183 MachineTraceMetrics::Trace BlockTrace) {
185 assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
186 "Missing machine model\n");
188 // Check each definition in NewRoot and compute the latency
189 unsigned NewRootLatency = 0;
191 for (const MachineOperand &MO : NewRoot->operands()) {
192 // Check for virtual register operand.
193 if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
197 // Get the first instruction that uses MO
198 MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
200 MachineInstr *UseMO = RI->getParent();
201 unsigned LatencyOp = 0;
202 if (UseMO && BlockTrace.isDepInTrace(Root, UseMO)) {
203 LatencyOp = TSchedModel.computeOperandLatency(
204 NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
205 UseMO->findRegisterUseOperandIdx(MO.getReg()));
207 LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
209 NewRootLatency = std::max(NewRootLatency, LatencyOp);
211 return NewRootLatency;
214 /// True when the new instruction sequence does not lengthen the critical path
215 /// and the new sequence has less instructions or the new sequence improves the
217 /// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
218 /// The new code sequence ends in MI NewRoot. A necessary condition for the new
219 /// sequence to replace the old sequence is that it cannot lengthen the critical
220 /// path. This is decided by the formula:
221 /// (NewRootDepth + NewRootLatency) <= (RootDepth + RootLatency + RootSlack)).
222 /// If the new sequence has an equal length critical path but does not reduce
223 /// the number of instructions (NewCodeHasLessInsts is false), then it is not
224 /// considered an improvement. The slack is the number of cycles Root can be
225 /// delayed before the critical patch becomes longer.
226 bool MachineCombiner::improvesCriticalPathLen(
227 MachineBasicBlock *MBB, MachineInstr *Root,
228 MachineTraceMetrics::Trace BlockTrace,
229 SmallVectorImpl<MachineInstr *> &InsInstrs,
230 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
231 bool NewCodeHasLessInsts) {
233 assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
234 "Missing machine model\n");
235 // NewRoot is the last instruction in the \p InsInstrs vector.
236 // Get depth and latency of NewRoot.
237 unsigned NewRootIdx = InsInstrs.size() - 1;
238 MachineInstr *NewRoot = InsInstrs[NewRootIdx];
239 unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
240 unsigned NewRootLatency = getLatency(Root, NewRoot, BlockTrace);
242 // Get depth, latency and slack of Root.
243 unsigned RootDepth = BlockTrace.getInstrCycles(Root).Depth;
244 unsigned RootLatency = TSchedModel.computeInstrLatency(Root);
245 unsigned RootSlack = BlockTrace.getInstrSlack(Root);
247 DEBUG(dbgs() << "DEPENDENCE DATA FOR " << Root << "\n";
248 dbgs() << " NewRootDepth: " << NewRootDepth
249 << " NewRootLatency: " << NewRootLatency << "\n";
250 dbgs() << " RootDepth: " << RootDepth << " RootLatency: " << RootLatency
251 << " RootSlack: " << RootSlack << "\n";
252 dbgs() << " NewRootDepth + NewRootLatency "
253 << NewRootDepth + NewRootLatency << "\n";
254 dbgs() << " RootDepth + RootLatency + RootSlack "
255 << RootDepth + RootLatency + RootSlack << "\n";);
257 unsigned NewCycleCount = NewRootDepth + NewRootLatency;
258 unsigned OldCycleCount = RootDepth + RootLatency + RootSlack;
260 if (NewCodeHasLessInsts)
261 return NewCycleCount <= OldCycleCount;
263 return NewCycleCount < OldCycleCount;
266 /// helper routine to convert instructions into SC
267 void MachineCombiner::instr2instrSC(
268 SmallVectorImpl<MachineInstr *> &Instrs,
269 SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
270 for (auto *InstrPtr : Instrs) {
271 unsigned Opc = InstrPtr->getOpcode();
272 unsigned Idx = TII->get(Opc).getSchedClass();
273 const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
274 InstrsSC.push_back(SC);
277 /// True when the new instructions do not increase resource length
278 bool MachineCombiner::preservesResourceLen(
279 MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
280 SmallVectorImpl<MachineInstr *> &InsInstrs,
281 SmallVectorImpl<MachineInstr *> &DelInstrs) {
282 if (!TSchedModel.hasInstrSchedModel())
285 // Compute current resource length
287 //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
288 SmallVector <const MachineBasicBlock *, 1> MBBarr;
289 MBBarr.push_back(MBB);
290 unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
292 // Deal with SC rather than Instructions.
293 SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
294 SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
296 instr2instrSC(InsInstrs, InsInstrsSC);
297 instr2instrSC(DelInstrs, DelInstrsSC);
299 ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
300 ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
302 // Compute new resource length.
303 unsigned ResLenAfterCombine =
304 BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
306 DEBUG(dbgs() << "RESOURCE DATA: \n";
307 dbgs() << " resource len before: " << ResLenBeforeCombine
308 << " after: " << ResLenAfterCombine << "\n";);
310 return ResLenAfterCombine <= ResLenBeforeCombine;
313 /// \returns true when new instruction sequence should be generated
314 /// independent if it lengthens critical path or not
315 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
316 if (OptSize && (NewSize < OldSize))
318 if (!TSchedModel.hasInstrSchedModelOrItineraries())
323 /// Substitute a slow code sequence with a faster one by
324 /// evaluating instruction combining pattern.
325 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
326 /// combining based on machine trace metrics. Only combine a sequence of
327 /// instructions when this neither lengthens the critical path nor increases
328 /// resource pressure. When optimizing for codesize always combine when the new
329 /// sequence is shorter.
330 bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
331 bool Changed = false;
332 DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
334 auto BlockIter = MBB->begin();
336 while (BlockIter != MBB->end()) {
337 auto &MI = *BlockIter++;
339 DEBUG(dbgs() << "INSTR "; MI.dump(); dbgs() << "\n";);
340 SmallVector<MachineCombinerPattern::MC_PATTERN, 16> Patterns;
341 // The motivating example is:
343 // MUL Other MUL_op1 MUL_op2 Other
345 // ADD/SUB => MADD/MSUB
346 // (=Root) (=NewRoot)
348 // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
349 // usually beneficial for code size it unfortunately can hurt performance
350 // when the ADD is on the critical path, but the MUL is not. With the
351 // substitution the MUL becomes part of the critical path (in form of the
352 // MADD) and can lengthen it on architectures where the MADD latency is
353 // longer than the ADD latency.
355 // For each instruction we check if it can be the root of a combiner
356 // pattern. Then for each pattern the new code sequence in form of MI is
357 // generated and evaluated. When the efficiency criteria (don't lengthen
358 // critical path, don't use more resources) is met the new sequence gets
359 // hooked up into the basic block before the old sequence is removed.
361 // The algorithm does not try to evaluate all patterns and pick the best.
362 // This is only an artificial restriction though. In practice there is
363 // mostly one pattern, and getMachineCombinerPatterns() can order patterns
364 // based on an internal cost heuristic.
366 if (TII->getMachineCombinerPatterns(MI, Patterns)) {
367 for (auto P : Patterns) {
368 SmallVector<MachineInstr *, 16> InsInstrs;
369 SmallVector<MachineInstr *, 16> DelInstrs;
370 DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
372 MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
373 MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
374 Traces->verifyAnalysis();
375 TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
377 unsigned NewInstCount = InsInstrs.size();
378 unsigned OldInstCount = DelInstrs.size();
379 // Found pattern, but did not generate alternative sequence.
380 // This can happen e.g. when an immediate could not be materialized
381 // in a single instruction.
384 // Substitute when we optimize for codesize and the new sequence has
385 // fewer instructions OR
386 // the new sequence neither lengthens the critical path nor increases
387 // resource pressure.
388 if (doSubstitute(NewInstCount, OldInstCount) ||
389 (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs,
391 NewInstCount < OldInstCount) &&
392 preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs))) {
393 for (auto *InstrPtr : InsInstrs)
394 MBB->insert((MachineBasicBlock::iterator) &MI, InstrPtr);
395 for (auto *InstrPtr : DelInstrs)
396 InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
401 Traces->invalidate(MBB);
402 Traces->verifyAnalysis();
403 // Eagerly stop after the first pattern fires.
406 // Cleanup instructions of the alternative code sequence. There is no
408 MachineFunction *MF = MBB->getParent();
409 for (auto *InstrPtr : InsInstrs)
410 MF->DeleteMachineInstr(InstrPtr);
412 InstrIdxForVirtReg.clear();
420 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
421 const TargetSubtargetInfo &STI = MF.getSubtarget();
422 TII = STI.getInstrInfo();
423 TRI = STI.getRegisterInfo();
424 SchedModel = STI.getSchedModel();
425 TSchedModel.init(SchedModel, &STI, TII);
426 MRI = &MF.getRegInfo();
427 Traces = &getAnalysis<MachineTraceMetrics>();
429 OptSize = MF.getFunction()->optForSize();
431 DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
432 if (!TII->useMachineCombiner()) {
433 DEBUG(dbgs() << " Skipping pass: Target does not support machine combiner\n");
437 bool Changed = false;
439 // Try to combine instructions.
441 Changed |= combineInstructions(&MBB);