1 //===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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"
14 
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"
32 
33 using namespace llvm;
34 
35 STATISTIC(NumInstCombined, "Number of machineinst combined");
36 
37 namespace {
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;
45 
46   TargetSchedModel TSchedModel;
47 
48   /// True if optimizing for code size.
49   bool OptSize;
50 
51 public:
52   static char ID;
MachineCombiner()53   MachineCombiner() : MachineFunctionPass(ID) {
54     initializeMachineCombinerPass(*PassRegistry::getPassRegistry());
55   }
56   void getAnalysisUsage(AnalysisUsage &AU) const override;
57   bool runOnMachineFunction(MachineFunction &MF) override;
getPassName() const58   const char *getPassName() const override { return "Machine InstCombiner"; }
59 
60 private:
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);
69   bool
70   preservesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
71                            MachineTraceMetrics::Trace BlockTrace,
72                            SmallVectorImpl<MachineInstr *> &InsInstrs,
73                            DenseMap<unsigned, unsigned> &InstrIdxForVirtReg);
74   bool preservesResourceLen(MachineBasicBlock *MBB,
75                             MachineTraceMetrics::Trace BlockTrace,
76                             SmallVectorImpl<MachineInstr *> &InsInstrs,
77                             SmallVectorImpl<MachineInstr *> &DelInstrs);
78   void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
79                      SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
80 };
81 }
82 
83 char MachineCombiner::ID = 0;
84 char &llvm::MachineCombinerID = MachineCombiner::ID;
85 
86 INITIALIZE_PASS_BEGIN(MachineCombiner, "machine-combiner",
87                       "Machine InstCombiner", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)88 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
89 INITIALIZE_PASS_END(MachineCombiner, "machine-combiner", "Machine InstCombiner",
90                     false, false)
91 
92 void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
93   AU.setPreservesCFG();
94   AU.addPreserved<MachineDominatorTree>();
95   AU.addPreserved<MachineLoopInfo>();
96   AU.addRequired<MachineTraceMetrics>();
97   AU.addPreserved<MachineTraceMetrics>();
98   MachineFunctionPass::getAnalysisUsage(AU);
99 }
100 
getOperandDef(const MachineOperand & MO)101 MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
102   MachineInstr *DefInstr = nullptr;
103   // We need a virtual register definition.
104   if (MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
105     DefInstr = MRI->getUniqueVRegDef(MO.getReg());
106   // PHI's have no depth etc.
107   if (DefInstr && DefInstr->isPHI())
108     DefInstr = nullptr;
109   return DefInstr;
110 }
111 
112 /// Computes depth of instructions in vector \InsInstr.
113 ///
114 /// \param InsInstrs is a vector of machine instructions
115 /// \param InstrIdxForVirtReg is a dense map of virtual register to index
116 /// of defining machine instruction in \p InsInstrs
117 /// \param BlockTrace is a trace of machine instructions
118 ///
119 /// \returns Depth of last instruction in \InsInstrs ("NewRoot")
120 unsigned
getDepth(SmallVectorImpl<MachineInstr * > & InsInstrs,DenseMap<unsigned,unsigned> & InstrIdxForVirtReg,MachineTraceMetrics::Trace BlockTrace)121 MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
122                           DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
123                           MachineTraceMetrics::Trace BlockTrace) {
124 
125   SmallVector<unsigned, 16> InstrDepth;
126   assert(TSchedModel.hasInstrSchedModel() && "Missing machine model\n");
127 
128   // For each instruction in the new sequence compute the depth based on the
129   // operands. Use the trace information when possible. For new operands which
130   // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
131   for (auto *InstrPtr : InsInstrs) { // for each Use
132     unsigned IDepth = 0;
133     DEBUG(dbgs() << "NEW INSTR "; InstrPtr->dump(); dbgs() << "\n";);
134     for (unsigned i = 0, e = InstrPtr->getNumOperands(); i != e; ++i) {
135       const MachineOperand &MO = InstrPtr->getOperand(i);
136       // Check for virtual register operand.
137       if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
138         continue;
139       if (!MO.isUse())
140         continue;
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];
149         assert(DefInstr &&
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()));
155       } else {
156         MachineInstr *DefInstr = getOperandDef(MO);
157         if (DefInstr) {
158           DepthOp = BlockTrace.getInstrCycles(DefInstr).Depth;
159           LatencyOp = TSchedModel.computeOperandLatency(
160               DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
161               InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
162         }
163       }
164       IDepth = std::max(IDepth, DepthOp + LatencyOp);
165     }
166     InstrDepth.push_back(IDepth);
167   }
168   unsigned NewRootIdx = InsInstrs.size() - 1;
169   return InstrDepth[NewRootIdx];
170 }
171 
172 /// Computes instruction latency as max of latency of defined operands.
173 ///
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
179 ///
180 /// \returns Latency of \p NewRoot
getLatency(MachineInstr * Root,MachineInstr * NewRoot,MachineTraceMetrics::Trace BlockTrace)181 unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
182                                      MachineTraceMetrics::Trace BlockTrace) {
183 
184   assert(TSchedModel.hasInstrSchedModel() && "Missing machine model\n");
185 
186   // Check each definition in NewRoot and compute the latency
187   unsigned NewRootLatency = 0;
188 
189   for (unsigned i = 0, e = NewRoot->getNumOperands(); i != e; ++i) {
190     const MachineOperand &MO = NewRoot->getOperand(i);
191     // Check for virtual register operand.
192     if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
193       continue;
194     if (!MO.isDef())
195       continue;
196     // Get the first instruction that uses MO
197     MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
198     RI++;
199     MachineInstr *UseMO = RI->getParent();
200     unsigned LatencyOp = 0;
201     if (UseMO && BlockTrace.isDepInTrace(Root, UseMO)) {
202       LatencyOp = TSchedModel.computeOperandLatency(
203           NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
204           UseMO->findRegisterUseOperandIdx(MO.getReg()));
205     } else {
206       LatencyOp = TSchedModel.computeInstrLatency(NewRoot->getOpcode());
207     }
208     NewRootLatency = std::max(NewRootLatency, LatencyOp);
209   }
210   return NewRootLatency;
211 }
212 
213 /// True when the new instruction sequence does not
214 /// lengthen the critical path. The DAGCombine code sequence ends in MI
215 /// (Machine Instruction) Root. The new code sequence ends in MI NewRoot. A
216 /// necessary condition for the new sequence to replace the old sequence is that
217 /// it cannot lengthen the critical path. This is decided by the formula
218 /// (NewRootDepth + NewRootLatency) <= (RootDepth + RootLatency + RootSlack)).
219 /// The slack is the number of cycles Root can be delayed before the critical
220 /// patch becomes longer.
preservesCriticalPathLen(MachineBasicBlock * MBB,MachineInstr * Root,MachineTraceMetrics::Trace BlockTrace,SmallVectorImpl<MachineInstr * > & InsInstrs,DenseMap<unsigned,unsigned> & InstrIdxForVirtReg)221 bool MachineCombiner::preservesCriticalPathLen(
222     MachineBasicBlock *MBB, MachineInstr *Root,
223     MachineTraceMetrics::Trace BlockTrace,
224     SmallVectorImpl<MachineInstr *> &InsInstrs,
225     DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) {
226 
227   assert(TSchedModel.hasInstrSchedModel() && "Missing machine model\n");
228   // NewRoot is the last instruction in the \p InsInstrs vector
229   // Get depth and latency of NewRoot
230   unsigned NewRootIdx = InsInstrs.size() - 1;
231   MachineInstr *NewRoot = InsInstrs[NewRootIdx];
232   unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
233   unsigned NewRootLatency = getLatency(Root, NewRoot, BlockTrace);
234 
235   // Get depth, latency and slack of Root
236   unsigned RootDepth = BlockTrace.getInstrCycles(Root).Depth;
237   unsigned RootLatency = TSchedModel.computeInstrLatency(Root);
238   unsigned RootSlack = BlockTrace.getInstrSlack(Root);
239 
240   DEBUG(dbgs() << "DEPENDENCE DATA FOR " << Root << "\n";
241         dbgs() << " NewRootDepth: " << NewRootDepth
242                << " NewRootLatency: " << NewRootLatency << "\n";
243         dbgs() << " RootDepth: " << RootDepth << " RootLatency: " << RootLatency
244                << " RootSlack: " << RootSlack << "\n";
245         dbgs() << " NewRootDepth + NewRootLatency "
246                << NewRootDepth + NewRootLatency << "\n";
247         dbgs() << " RootDepth + RootLatency + RootSlack "
248                << RootDepth + RootLatency + RootSlack << "\n";);
249 
250   /// True when the new sequence does not lenghten the critical path.
251   return ((NewRootDepth + NewRootLatency) <=
252           (RootDepth + RootLatency + RootSlack));
253 }
254 
255 /// helper routine to convert instructions into SC
instr2instrSC(SmallVectorImpl<MachineInstr * > & Instrs,SmallVectorImpl<const MCSchedClassDesc * > & InstrsSC)256 void MachineCombiner::instr2instrSC(
257     SmallVectorImpl<MachineInstr *> &Instrs,
258     SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
259   for (auto *InstrPtr : Instrs) {
260     unsigned Opc = InstrPtr->getOpcode();
261     unsigned Idx = TII->get(Opc).getSchedClass();
262     const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
263     InstrsSC.push_back(SC);
264   }
265 }
266 /// True when the new instructions do not increase resource length
preservesResourceLen(MachineBasicBlock * MBB,MachineTraceMetrics::Trace BlockTrace,SmallVectorImpl<MachineInstr * > & InsInstrs,SmallVectorImpl<MachineInstr * > & DelInstrs)267 bool MachineCombiner::preservesResourceLen(
268     MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
269     SmallVectorImpl<MachineInstr *> &InsInstrs,
270     SmallVectorImpl<MachineInstr *> &DelInstrs) {
271 
272   // Compute current resource length
273 
274   //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
275   SmallVector <const MachineBasicBlock *, 1> MBBarr;
276   MBBarr.push_back(MBB);
277   unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
278 
279   // Deal with SC rather than Instructions.
280   SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
281   SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
282 
283   instr2instrSC(InsInstrs, InsInstrsSC);
284   instr2instrSC(DelInstrs, DelInstrsSC);
285 
286   ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
287   ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
288 
289   // Compute new resource length
290   unsigned ResLenAfterCombine =
291       BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
292 
293   DEBUG(dbgs() << "RESOURCE DATA: \n";
294         dbgs() << " resource len before: " << ResLenBeforeCombine
295                << " after: " << ResLenAfterCombine << "\n";);
296 
297   return ResLenAfterCombine <= ResLenBeforeCombine;
298 }
299 
300 /// \returns true when new instruction sequence should be generated
301 /// independent if it lengthens critical path or not
doSubstitute(unsigned NewSize,unsigned OldSize)302 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
303   if (OptSize && (NewSize < OldSize))
304     return true;
305   if (!TSchedModel.hasInstrSchedModel())
306     return true;
307   return false;
308 }
309 
310 /// Substitute a slow code sequence with a faster one by
311 /// evaluating instruction combining pattern.
312 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
313 /// combining based on machine trace metrics. Only combine a sequence of
314 /// instructions  when this neither lengthens the critical path nor increases
315 /// resource pressure. When optimizing for codesize always combine when the new
316 /// sequence is shorter.
combineInstructions(MachineBasicBlock * MBB)317 bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
318   bool Changed = false;
319   DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
320 
321   auto BlockIter = MBB->begin();
322 
323   while (BlockIter != MBB->end()) {
324     auto &MI = *BlockIter++;
325 
326     DEBUG(dbgs() << "INSTR "; MI.dump(); dbgs() << "\n";);
327     SmallVector<MachineCombinerPattern::MC_PATTERN, 16> Pattern;
328     // The motivating example is:
329     //
330     //     MUL  Other        MUL_op1 MUL_op2  Other
331     //      \    /               \      |    /
332     //      ADD/SUB      =>        MADD/MSUB
333     //      (=Root)                (=NewRoot)
334 
335     // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
336     // usually beneficial for code size it unfortunately can hurt performance
337     // when the ADD is on the critical path, but the MUL is not. With the
338     // substitution the MUL becomes part of the critical path (in form of the
339     // MADD) and can lengthen it on architectures where the MADD latency is
340     // longer than the ADD latency.
341     //
342     // For each instruction we check if it can be the root of a combiner
343     // pattern. Then for each pattern the new code sequence in form of MI is
344     // generated and evaluated. When the efficiency criteria (don't lengthen
345     // critical path, don't use more resources) is met the new sequence gets
346     // hooked up into the basic block before the old sequence is removed.
347     //
348     // The algorithm does not try to evaluate all patterns and pick the best.
349     // This is only an artificial restriction though. In practice there is
350     // mostly one pattern and hasPattern() can order patterns based on an
351     // internal cost heuristic.
352 
353     if (TII->hasPattern(MI, Pattern)) {
354       for (auto P : Pattern) {
355         SmallVector<MachineInstr *, 16> InsInstrs;
356         SmallVector<MachineInstr *, 16> DelInstrs;
357         DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
358         if (!MinInstr)
359           MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
360         MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
361         Traces->verifyAnalysis();
362         TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
363                                         InstrIdxForVirtReg);
364         // Found pattern, but did not generate alternative sequence.
365         // This can happen e.g. when an immediate could not be materialized
366         // in a single instruction.
367         if (!InsInstrs.size())
368           continue;
369         // Substitute when we optimize for codesize and the new sequence has
370         // fewer instructions OR
371         // the new sequence neither lenghten the critical path nor increases
372         // resource pressure.
373         if (doSubstitute(InsInstrs.size(), DelInstrs.size()) ||
374             (preservesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs,
375                                       InstrIdxForVirtReg) &&
376              preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs))) {
377           for (auto *InstrPtr : InsInstrs)
378             MBB->insert((MachineBasicBlock::iterator) & MI,
379                         (MachineInstr *)InstrPtr);
380           for (auto *InstrPtr : DelInstrs)
381             InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
382 
383           Changed = true;
384           ++NumInstCombined;
385 
386           Traces->invalidate(MBB);
387           Traces->verifyAnalysis();
388           // Eagerly stop after the first pattern fired
389           break;
390         } else {
391           // Cleanup instructions of the alternative code sequence. There is no
392           // use for them.
393           for (auto *InstrPtr : InsInstrs) {
394             MachineFunction *MF = MBB->getParent();
395             MF->DeleteMachineInstr((MachineInstr *)InstrPtr);
396           }
397         }
398         InstrIdxForVirtReg.clear();
399       }
400     }
401   }
402 
403   return Changed;
404 }
405 
runOnMachineFunction(MachineFunction & MF)406 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
407   const TargetSubtargetInfo &STI = MF.getSubtarget();
408   TII = STI.getInstrInfo();
409   TRI = STI.getRegisterInfo();
410   SchedModel = STI.getSchedModel();
411   TSchedModel.init(SchedModel, &STI, TII);
412   MRI = &MF.getRegInfo();
413   Traces = &getAnalysis<MachineTraceMetrics>();
414   MinInstr = 0;
415 
416   OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
417 
418   DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
419   if (!TII->useMachineCombiner()) {
420     DEBUG(dbgs() << "  Skipping pass: Target does not support machine combiner\n");
421     return false;
422   }
423 
424   bool Changed = false;
425 
426   // Try to combine instructions.
427   for (auto &MBB : MF)
428     Changed |= combineInstructions(&MBB);
429 
430   return Changed;
431 }
432