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.hasInstrSchedModel() && "Missing machine model\n");
129 // For each instruction in the new sequence compute the depth based on the
130 // operands. Use the trace information when possible. For new operands which
131 // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
132 for (auto *InstrPtr : InsInstrs) { // for each Use
134 DEBUG(dbgs() << "NEW INSTR "; InstrPtr->dump(); dbgs() << "\n";);
135 for (const MachineOperand &MO : InstrPtr->operands()) {
136 // Check for virtual register operand.
137 if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
141 unsigned DepthOp = 0;
142 unsigned LatencyOp = 0;
143 DenseMap<unsigned, unsigned>::iterator II =
144 InstrIdxForVirtReg.find(MO.getReg());
145 if (II != InstrIdxForVirtReg.end()) {
146 // Operand is new virtual register not in trace
147 assert(II->second < InstrDepth.size() && "Bad Index");
148 MachineInstr *DefInstr = InsInstrs[II->second];
150 "There must be a definition for a new virtual register");
151 DepthOp = InstrDepth[II->second];
152 LatencyOp = TSchedModel.computeOperandLatency(
153 DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
154 InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
156 MachineInstr *DefInstr = getOperandDef(MO);
158 DepthOp = BlockTrace.getInstrCycles(DefInstr).Depth;
159 LatencyOp = TSchedModel.computeOperandLatency(
160 DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
161 InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
164 IDepth = std::max(IDepth, DepthOp + LatencyOp);
166 InstrDepth.push_back(IDepth);
168 unsigned NewRootIdx = InsInstrs.size() - 1;
169 return InstrDepth[NewRootIdx];
172 /// Computes instruction latency as max of latency of defined operands.
174 /// \param Root is a machine instruction that could be replaced by NewRoot.
175 /// It is used to compute a more accurate latency information for NewRoot in
176 /// case there is a dependent instruction in the same trace (\p BlockTrace)
177 /// \param NewRoot is the instruction for which the latency is computed
178 /// \param BlockTrace is a trace of machine instructions
180 /// \returns Latency of \p NewRoot
181 unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
182 MachineTraceMetrics::Trace BlockTrace) {
184 assert(TSchedModel.hasInstrSchedModel() && "Missing machine model\n");
186 // Check each definition in NewRoot and compute the latency
187 unsigned NewRootLatency = 0;
189 for (const MachineOperand &MO : NewRoot->operands()) {
190 // Check for virtual register operand.
191 if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
195 // Get the first instruction that uses MO
196 MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
198 MachineInstr *UseMO = RI->getParent();
199 unsigned LatencyOp = 0;
200 if (UseMO && BlockTrace.isDepInTrace(Root, UseMO)) {
201 LatencyOp = TSchedModel.computeOperandLatency(
202 NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
203 UseMO->findRegisterUseOperandIdx(MO.getReg()));
205 LatencyOp = TSchedModel.computeInstrLatency(NewRoot->getOpcode());
207 NewRootLatency = std::max(NewRootLatency, LatencyOp);
209 return NewRootLatency;
212 /// True when the new instruction sequence does not lengthen the critical path
213 /// and the new sequence has less instructions or the new sequence improves the
215 /// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
216 /// The new code sequence ends in MI NewRoot. A necessary condition for the new
217 /// sequence to replace the old sequence is that it cannot lengthen the critical
218 /// path. This is decided by the formula:
219 /// (NewRootDepth + NewRootLatency) <= (RootDepth + RootLatency + RootSlack)).
220 /// If the new sequence has an equal length critical path but does not reduce
221 /// the number of instructions (NewCodeHasLessInsts is false), then it is not
222 /// considered an improvement. The slack is the number of cycles Root can be
223 /// delayed before the critical patch becomes longer.
224 bool MachineCombiner::improvesCriticalPathLen(
225 MachineBasicBlock *MBB, MachineInstr *Root,
226 MachineTraceMetrics::Trace BlockTrace,
227 SmallVectorImpl<MachineInstr *> &InsInstrs,
228 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
229 bool NewCodeHasLessInsts) {
231 assert(TSchedModel.hasInstrSchedModel() && "Missing machine model\n");
232 // NewRoot is the last instruction in the \p InsInstrs vector.
233 // Get depth and latency of NewRoot.
234 unsigned NewRootIdx = InsInstrs.size() - 1;
235 MachineInstr *NewRoot = InsInstrs[NewRootIdx];
236 unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
237 unsigned NewRootLatency = getLatency(Root, NewRoot, BlockTrace);
239 // Get depth, latency and slack of Root.
240 unsigned RootDepth = BlockTrace.getInstrCycles(Root).Depth;
241 unsigned RootLatency = TSchedModel.computeInstrLatency(Root);
242 unsigned RootSlack = BlockTrace.getInstrSlack(Root);
244 DEBUG(dbgs() << "DEPENDENCE DATA FOR " << Root << "\n";
245 dbgs() << " NewRootDepth: " << NewRootDepth
246 << " NewRootLatency: " << NewRootLatency << "\n";
247 dbgs() << " RootDepth: " << RootDepth << " RootLatency: " << RootLatency
248 << " RootSlack: " << RootSlack << "\n";
249 dbgs() << " NewRootDepth + NewRootLatency "
250 << NewRootDepth + NewRootLatency << "\n";
251 dbgs() << " RootDepth + RootLatency + RootSlack "
252 << RootDepth + RootLatency + RootSlack << "\n";);
254 unsigned NewCycleCount = NewRootDepth + NewRootLatency;
255 unsigned OldCycleCount = RootDepth + RootLatency + RootSlack;
257 if (NewCodeHasLessInsts)
258 return NewCycleCount <= OldCycleCount;
260 return NewCycleCount < OldCycleCount;
263 /// helper routine to convert instructions into SC
264 void MachineCombiner::instr2instrSC(
265 SmallVectorImpl<MachineInstr *> &Instrs,
266 SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
267 for (auto *InstrPtr : Instrs) {
268 unsigned Opc = InstrPtr->getOpcode();
269 unsigned Idx = TII->get(Opc).getSchedClass();
270 const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
271 InstrsSC.push_back(SC);
274 /// True when the new instructions do not increase resource length
275 bool MachineCombiner::preservesResourceLen(
276 MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
277 SmallVectorImpl<MachineInstr *> &InsInstrs,
278 SmallVectorImpl<MachineInstr *> &DelInstrs) {
280 // Compute current resource length
282 //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
283 SmallVector <const MachineBasicBlock *, 1> MBBarr;
284 MBBarr.push_back(MBB);
285 unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
287 // Deal with SC rather than Instructions.
288 SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
289 SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
291 instr2instrSC(InsInstrs, InsInstrsSC);
292 instr2instrSC(DelInstrs, DelInstrsSC);
294 ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
295 ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
297 // Compute new resource length.
298 unsigned ResLenAfterCombine =
299 BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
301 DEBUG(dbgs() << "RESOURCE DATA: \n";
302 dbgs() << " resource len before: " << ResLenBeforeCombine
303 << " after: " << ResLenAfterCombine << "\n";);
305 return ResLenAfterCombine <= ResLenBeforeCombine;
308 /// \returns true when new instruction sequence should be generated
309 /// independent if it lengthens critical path or not
310 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
311 if (OptSize && (NewSize < OldSize))
313 if (!TSchedModel.hasInstrSchedModel())
318 /// Substitute a slow code sequence with a faster one by
319 /// evaluating instruction combining pattern.
320 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
321 /// combining based on machine trace metrics. Only combine a sequence of
322 /// instructions when this neither lengthens the critical path nor increases
323 /// resource pressure. When optimizing for codesize always combine when the new
324 /// sequence is shorter.
325 bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
326 bool Changed = false;
327 DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
329 auto BlockIter = MBB->begin();
331 while (BlockIter != MBB->end()) {
332 auto &MI = *BlockIter++;
334 DEBUG(dbgs() << "INSTR "; MI.dump(); dbgs() << "\n";);
335 SmallVector<MachineCombinerPattern::MC_PATTERN, 16> Patterns;
336 // The motivating example is:
338 // MUL Other MUL_op1 MUL_op2 Other
340 // ADD/SUB => MADD/MSUB
341 // (=Root) (=NewRoot)
343 // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
344 // usually beneficial for code size it unfortunately can hurt performance
345 // when the ADD is on the critical path, but the MUL is not. With the
346 // substitution the MUL becomes part of the critical path (in form of the
347 // MADD) and can lengthen it on architectures where the MADD latency is
348 // longer than the ADD latency.
350 // For each instruction we check if it can be the root of a combiner
351 // pattern. Then for each pattern the new code sequence in form of MI is
352 // generated and evaluated. When the efficiency criteria (don't lengthen
353 // critical path, don't use more resources) is met the new sequence gets
354 // hooked up into the basic block before the old sequence is removed.
356 // The algorithm does not try to evaluate all patterns and pick the best.
357 // This is only an artificial restriction though. In practice there is
358 // mostly one pattern, and getMachineCombinerPatterns() can order patterns
359 // based on an internal cost heuristic.
361 if (TII->getMachineCombinerPatterns(MI, Patterns)) {
362 for (auto P : Patterns) {
363 SmallVector<MachineInstr *, 16> InsInstrs;
364 SmallVector<MachineInstr *, 16> DelInstrs;
365 DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
367 MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
368 MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
369 Traces->verifyAnalysis();
370 TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
372 unsigned NewInstCount = InsInstrs.size();
373 unsigned OldInstCount = DelInstrs.size();
374 // Found pattern, but did not generate alternative sequence.
375 // This can happen e.g. when an immediate could not be materialized
376 // in a single instruction.
379 // Substitute when we optimize for codesize and the new sequence has
380 // fewer instructions OR
381 // the new sequence neither lengthens the critical path nor increases
382 // resource pressure.
383 if (doSubstitute(NewInstCount, OldInstCount) ||
384 (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs,
386 NewInstCount < OldInstCount) &&
387 preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs))) {
388 for (auto *InstrPtr : InsInstrs)
389 MBB->insert((MachineBasicBlock::iterator) &MI, InstrPtr);
390 for (auto *InstrPtr : DelInstrs)
391 InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
396 Traces->invalidate(MBB);
397 Traces->verifyAnalysis();
398 // Eagerly stop after the first pattern fires.
401 // Cleanup instructions of the alternative code sequence. There is no
403 MachineFunction *MF = MBB->getParent();
404 for (auto *InstrPtr : InsInstrs)
405 MF->DeleteMachineInstr(InstrPtr);
407 InstrIdxForVirtReg.clear();
415 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
416 const TargetSubtargetInfo &STI = MF.getSubtarget();
417 TII = STI.getInstrInfo();
418 TRI = STI.getRegisterInfo();
419 SchedModel = STI.getSchedModel();
420 TSchedModel.init(SchedModel, &STI, TII);
421 MRI = &MF.getRegInfo();
422 Traces = &getAnalysis<MachineTraceMetrics>();
425 OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
427 DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
428 if (!TII->useMachineCombiner()) {
429 DEBUG(dbgs() << " Skipping pass: Target does not support machine combiner\n");
433 bool Changed = false;
435 // Try to combine instructions.
437 Changed |= combineInstructions(&MBB);