Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/MachineCombiner.cpp
Line
Count
Source (jump to first uncovered line)
1
//===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// The machine combiner pass uses machine trace metrics to ensure the combined
10
// instructions do not lengthen the critical path or the resource depth.
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/ADT/DenseMap.h"
14
#include "llvm/ADT/Statistic.h"
15
#include "llvm/CodeGen/MachineDominators.h"
16
#include "llvm/CodeGen/MachineFunction.h"
17
#include "llvm/CodeGen/MachineFunctionPass.h"
18
#include "llvm/CodeGen/MachineLoopInfo.h"
19
#include "llvm/CodeGen/MachineRegisterInfo.h"
20
#include "llvm/CodeGen/MachineTraceMetrics.h"
21
#include "llvm/CodeGen/Passes.h"
22
#include "llvm/CodeGen/TargetInstrInfo.h"
23
#include "llvm/CodeGen/TargetRegisterInfo.h"
24
#include "llvm/CodeGen/TargetSchedule.h"
25
#include "llvm/CodeGen/TargetSubtargetInfo.h"
26
#include "llvm/Support/CommandLine.h"
27
#include "llvm/Support/Debug.h"
28
#include "llvm/Support/raw_ostream.h"
29
30
using namespace llvm;
31
32
#define DEBUG_TYPE "machine-combiner"
33
34
STATISTIC(NumInstCombined, "Number of machineinst combined");
35
36
static cl::opt<unsigned>
37
inc_threshold("machine-combiner-inc-threshold", cl::Hidden,
38
              cl::desc("Incremental depth computation will be used for basic "
39
                       "blocks with more instructions."), cl::init(500));
40
41
static cl::opt<bool> dump_intrs("machine-combiner-dump-subst-intrs", cl::Hidden,
42
                                cl::desc("Dump all substituted intrs"),
43
                                cl::init(false));
44
45
#ifdef EXPENSIVE_CHECKS
46
static cl::opt<bool> VerifyPatternOrder(
47
    "machine-combiner-verify-pattern-order", cl::Hidden,
48
    cl::desc(
49
        "Verify that the generated patterns are ordered by increasing latency"),
50
    cl::init(true));
51
#else
52
static cl::opt<bool> VerifyPatternOrder(
53
    "machine-combiner-verify-pattern-order", cl::Hidden,
54
    cl::desc(
55
        "Verify that the generated patterns are ordered by increasing latency"),
56
    cl::init(false));
57
#endif
58
59
namespace {
60
class MachineCombiner : public MachineFunctionPass {
61
  const TargetSubtargetInfo *STI;
62
  const TargetInstrInfo *TII;
63
  const TargetRegisterInfo *TRI;
64
  MCSchedModel SchedModel;
65
  MachineRegisterInfo *MRI;
66
  MachineLoopInfo *MLI; // Current MachineLoopInfo
67
  MachineTraceMetrics *Traces;
68
  MachineTraceMetrics::Ensemble *MinInstr;
69
70
  TargetSchedModel TSchedModel;
71
72
  /// True if optimizing for code size.
73
  bool OptSize;
74
75
public:
76
  static char ID;
77
21.6k
  MachineCombiner() : MachineFunctionPass(ID) {
78
21.6k
    initializeMachineCombinerPass(*PassRegistry::getPassRegistry());
79
21.6k
  }
80
  void getAnalysisUsage(AnalysisUsage &AU) const override;
81
  bool runOnMachineFunction(MachineFunction &MF) override;
82
424k
  StringRef getPassName() const override { return "Machine InstCombiner"; }
83
84
private:
85
  bool doSubstitute(unsigned NewSize, unsigned OldSize);
86
  bool combineInstructions(MachineBasicBlock *);
87
  MachineInstr *getOperandDef(const MachineOperand &MO);
88
  unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
89
                    DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
90
                    MachineTraceMetrics::Trace BlockTrace);
91
  unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
92
                      MachineTraceMetrics::Trace BlockTrace);
93
  bool
94
  improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
95
                          MachineTraceMetrics::Trace BlockTrace,
96
                          SmallVectorImpl<MachineInstr *> &InsInstrs,
97
                          SmallVectorImpl<MachineInstr *> &DelInstrs,
98
                          DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
99
                          MachineCombinerPattern Pattern, bool SlackIsAccurate);
100
  bool preservesResourceLen(MachineBasicBlock *MBB,
101
                            MachineTraceMetrics::Trace BlockTrace,
102
                            SmallVectorImpl<MachineInstr *> &InsInstrs,
103
                            SmallVectorImpl<MachineInstr *> &DelInstrs);
104
  void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
105
                     SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
106
  std::pair<unsigned, unsigned>
107
  getLatenciesForInstrSequences(MachineInstr &MI,
108
                                SmallVectorImpl<MachineInstr *> &InsInstrs,
109
                                SmallVectorImpl<MachineInstr *> &DelInstrs,
110
                                MachineTraceMetrics::Trace BlockTrace);
111
112
  void verifyPatternOrder(MachineBasicBlock *MBB, MachineInstr &Root,
113
                          SmallVector<MachineCombinerPattern, 16> &Patterns);
114
};
115
}
116
117
char MachineCombiner::ID = 0;
118
char &llvm::MachineCombinerID = MachineCombiner::ID;
119
120
42.3k
INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,
121
42.3k
                      "Machine InstCombiner", false, false)
122
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
123
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
124
42.3k
INITIALIZE_PASS_END(MachineCombiner, DEBUG_TYPE, "Machine InstCombiner",
125
                    false, false)
126
127
21.5k
void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
128
21.5k
  AU.setPreservesCFG();
129
21.5k
  AU.addPreserved<MachineDominatorTree>();
130
21.5k
  AU.addRequired<MachineLoopInfo>();
131
21.5k
  AU.addPreserved<MachineLoopInfo>();
132
21.5k
  AU.addRequired<MachineTraceMetrics>();
133
21.5k
  AU.addPreserved<MachineTraceMetrics>();
134
21.5k
  MachineFunctionPass::getAnalysisUsage(AU);
135
21.5k
}
136
137
258k
MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
138
258k
  MachineInstr *DefInstr = nullptr;
139
258k
  // We need a virtual register definition.
140
258k
  if (MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
141
258k
    DefInstr = MRI->getUniqueVRegDef(MO.getReg());
142
258k
  // PHI's have no depth etc.
143
258k
  if (DefInstr && DefInstr->isPHI())
144
25.7k
    DefInstr = nullptr;
145
258k
  return DefInstr;
146
258k
}
147
148
/// Computes depth of instructions in vector \InsInstr.
149
///
150
/// \param InsInstrs is a vector of machine instructions
151
/// \param InstrIdxForVirtReg is a dense map of virtual register to index
152
/// of defining machine instruction in \p InsInstrs
153
/// \param BlockTrace is a trace of machine instructions
154
///
155
/// \returns Depth of last instruction in \InsInstrs ("NewRoot")
156
unsigned
157
MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
158
                          DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
159
86.4k
                          MachineTraceMetrics::Trace BlockTrace) {
160
86.4k
  SmallVector<unsigned, 16> InstrDepth;
161
86.4k
  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
162
86.4k
         "Missing machine model\n");
163
86.4k
164
86.4k
  // For each instruction in the new sequence compute the depth based on the
165
86.4k
  // operands. Use the trace information when possible. For new operands which
166
86.4k
  // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
167
89.9k
  for (auto *InstrPtr : InsInstrs) { // for each Use
168
89.9k
    unsigned IDepth = 0;
169
355k
    for (const MachineOperand &MO : InstrPtr->operands()) {
170
355k
      // Check for virtual register operand.
171
355k
      if (!(MO.isReg() && 
TargetRegisterInfo::isVirtualRegister(MO.getReg())355k
))
172
3.14k
        continue;
173
352k
      if (!MO.isUse())
174
89.9k
        continue;
175
262k
      unsigned DepthOp = 0;
176
262k
      unsigned LatencyOp = 0;
177
262k
      DenseMap<unsigned, unsigned>::iterator II =
178
262k
          InstrIdxForVirtReg.find(MO.getReg());
179
262k
      if (II != InstrIdxForVirtReg.end()) {
180
3.48k
        // Operand is new virtual register not in trace
181
3.48k
        assert(II->second < InstrDepth.size() && "Bad Index");
182
3.48k
        MachineInstr *DefInstr = InsInstrs[II->second];
183
3.48k
        assert(DefInstr &&
184
3.48k
               "There must be a definition for a new virtual register");
185
3.48k
        DepthOp = InstrDepth[II->second];
186
3.48k
        int DefIdx = DefInstr->findRegisterDefOperandIdx(MO.getReg());
187
3.48k
        int UseIdx = InstrPtr->findRegisterUseOperandIdx(MO.getReg());
188
3.48k
        LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
189
3.48k
                                                      InstrPtr, UseIdx);
190
258k
      } else {
191
258k
        MachineInstr *DefInstr = getOperandDef(MO);
192
258k
        if (DefInstr) {
193
233k
          DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
194
233k
          LatencyOp = TSchedModel.computeOperandLatency(
195
233k
              DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
196
233k
              InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
197
233k
        }
198
258k
      }
199
262k
      IDepth = std::max(IDepth, DepthOp + LatencyOp);
200
262k
    }
201
89.9k
    InstrDepth.push_back(IDepth);
202
89.9k
  }
203
86.4k
  unsigned NewRootIdx = InsInstrs.size() - 1;
204
86.4k
  return InstrDepth[NewRootIdx];
205
86.4k
}
206
207
/// Computes instruction latency as max of latency of defined operands.
208
///
209
/// \param Root is a machine instruction that could be replaced by NewRoot.
210
/// It is used to compute a more accurate latency information for NewRoot in
211
/// case there is a dependent instruction in the same trace (\p BlockTrace)
212
/// \param NewRoot is the instruction for which the latency is computed
213
/// \param BlockTrace is a trace of machine instructions
214
///
215
/// \returns Latency of \p NewRoot
216
unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
217
84.1k
                                     MachineTraceMetrics::Trace BlockTrace) {
218
84.1k
  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
219
84.1k
         "Missing machine model\n");
220
84.1k
221
84.1k
  // Check each definition in NewRoot and compute the latency
222
84.1k
  unsigned NewRootLatency = 0;
223
84.1k
224
335k
  for (const MachineOperand &MO : NewRoot->operands()) {
225
335k
    // Check for virtual register operand.
226
335k
    if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
227
48
      continue;
228
335k
    if (!MO.isDef())
229
251k
      continue;
230
84.1k
    // Get the first instruction that uses MO
231
84.1k
    MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
232
84.1k
    RI++;
233
84.1k
    if (RI == MRI->reg_end())
234
0
      continue;
235
84.1k
    MachineInstr *UseMO = RI->getParent();
236
84.1k
    unsigned LatencyOp = 0;
237
84.1k
    if (UseMO && BlockTrace.isDepInTrace(*Root, *UseMO)) {
238
70.8k
      LatencyOp = TSchedModel.computeOperandLatency(
239
70.8k
          NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
240
70.8k
          UseMO->findRegisterUseOperandIdx(MO.getReg()));
241
70.8k
    } else {
242
13.2k
      LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
243
13.2k
    }
244
84.1k
    NewRootLatency = std::max(NewRootLatency, LatencyOp);
245
84.1k
  }
246
84.1k
  return NewRootLatency;
247
84.1k
}
248
249
/// The combiner's goal may differ based on which pattern it is attempting
250
/// to optimize.
251
enum class CombinerObjective {
252
  MustReduceDepth, // The data dependency chain must be improved.
253
  Default          // The critical path must not be lengthened.
254
};
255
256
86.4k
static CombinerObjective getCombinerObjective(MachineCombinerPattern P) {
257
86.4k
  // TODO: If C++ ever gets a real enum class, make this part of the
258
86.4k
  // MachineCombinerPattern class.
259
86.4k
  switch (P) {
260
86.4k
  case MachineCombinerPattern::REASSOC_AX_BY:
261
3.05k
  case MachineCombinerPattern::REASSOC_AX_YB:
262
3.05k
  case MachineCombinerPattern::REASSOC_XA_BY:
263
3.05k
  case MachineCombinerPattern::REASSOC_XA_YB:
264
3.05k
    return CombinerObjective::MustReduceDepth;
265
83.3k
  default:
266
83.3k
    return CombinerObjective::Default;
267
86.4k
  }
268
86.4k
}
269
270
/// Estimate the latency of the new and original instruction sequence by summing
271
/// up the latencies of the inserted and deleted instructions. This assumes
272
/// that the inserted and deleted instructions are dependent instruction chains,
273
/// which might not hold in all cases.
274
std::pair<unsigned, unsigned> MachineCombiner::getLatenciesForInstrSequences(
275
    MachineInstr &MI, SmallVectorImpl<MachineInstr *> &InsInstrs,
276
    SmallVectorImpl<MachineInstr *> &DelInstrs,
277
84.1k
    MachineTraceMetrics::Trace BlockTrace) {
278
84.1k
  assert(!InsInstrs.empty() && "Only support sequences that insert instrs.");
279
84.1k
  unsigned NewRootLatency = 0;
280
84.1k
  // NewRoot is the last instruction in the \p InsInstrs vector.
281
84.1k
  MachineInstr *NewRoot = InsInstrs.back();
282
85.3k
  for (unsigned i = 0; i < InsInstrs.size() - 1; 
i++1.16k
)
283
1.16k
    NewRootLatency += TSchedModel.computeInstrLatency(InsInstrs[i]);
284
84.1k
  NewRootLatency += getLatency(&MI, NewRoot, BlockTrace);
285
84.1k
286
84.1k
  unsigned RootLatency = 0;
287
84.1k
  for (auto I : DelInstrs)
288
168k
    RootLatency += TSchedModel.computeInstrLatency(I);
289
84.1k
290
84.1k
  return {NewRootLatency, RootLatency};
291
84.1k
}
292
293
/// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
294
/// The new code sequence ends in MI NewRoot. A necessary condition for the new
295
/// sequence to replace the old sequence is that it cannot lengthen the critical
296
/// path. The definition of "improve" may be restricted by specifying that the
297
/// new path improves the data dependency chain (MustReduceDepth).
298
bool MachineCombiner::improvesCriticalPathLen(
299
    MachineBasicBlock *MBB, MachineInstr *Root,
300
    MachineTraceMetrics::Trace BlockTrace,
301
    SmallVectorImpl<MachineInstr *> &InsInstrs,
302
    SmallVectorImpl<MachineInstr *> &DelInstrs,
303
    DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
304
    MachineCombinerPattern Pattern,
305
86.4k
    bool SlackIsAccurate) {
306
86.4k
  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
307
86.4k
         "Missing machine model\n");
308
86.4k
  // Get depth and latency of NewRoot and Root.
309
86.4k
  unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
310
86.4k
  unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
311
86.4k
312
86.4k
  LLVM_DEBUG(dbgs() << "  Dependence data for " << *Root << "\tNewRootDepth: "
313
86.4k
                    << NewRootDepth << "\tRootDepth: " << RootDepth);
314
86.4k
315
86.4k
  // For a transform such as reassociation, the cost equation is
316
86.4k
  // conservatively calculated so that we must improve the depth (data
317
86.4k
  // dependency cycles) in the critical path to proceed with the transform.
318
86.4k
  // Being conservative also protects against inaccuracies in the underlying
319
86.4k
  // machine trace metrics and CPU models.
320
86.4k
  if (getCombinerObjective(Pattern) == CombinerObjective::MustReduceDepth) {
321
3.05k
    LLVM_DEBUG(dbgs() << "\tIt MustReduceDepth ");
322
3.05k
    LLVM_DEBUG(NewRootDepth < RootDepth
323
3.05k
                   ? dbgs() << "\t  and it does it\n"
324
3.05k
                   : dbgs() << "\t  but it does NOT do it\n");
325
3.05k
    return NewRootDepth < RootDepth;
326
3.05k
  }
327
83.3k
328
83.3k
  // A more flexible cost calculation for the critical path includes the slack
329
83.3k
  // of the original code sequence. This may allow the transform to proceed
330
83.3k
  // even if the instruction depths (data dependency cycles) become worse.
331
83.3k
332
83.3k
  // Account for the latency of the inserted and deleted instructions by
333
83.3k
  unsigned NewRootLatency, RootLatency;
334
83.3k
  std::tie(NewRootLatency, RootLatency) =
335
83.3k
      getLatenciesForInstrSequences(*Root, InsInstrs, DelInstrs, BlockTrace);
336
83.3k
337
83.3k
  unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
338
83.3k
  unsigned NewCycleCount = NewRootDepth + NewRootLatency;
339
83.3k
  unsigned OldCycleCount =
340
83.3k
      RootDepth + RootLatency + (SlackIsAccurate ? 
RootSlack82.8k
:
0499
);
341
83.3k
  LLVM_DEBUG(dbgs() << "\n\tNewRootLatency: " << NewRootLatency
342
83.3k
                    << "\tRootLatency: " << RootLatency << "\n\tRootSlack: "
343
83.3k
                    << RootSlack << " SlackIsAccurate=" << SlackIsAccurate
344
83.3k
                    << "\n\tNewRootDepth + NewRootLatency = " << NewCycleCount
345
83.3k
                    << "\n\tRootDepth + RootLatency + RootSlack = "
346
83.3k
                    << OldCycleCount;);
347
83.3k
  LLVM_DEBUG(NewCycleCount <= OldCycleCount
348
83.3k
                 ? dbgs() << "\n\t  It IMPROVES PathLen because"
349
83.3k
                 : dbgs() << "\n\t  It DOES NOT improve PathLen because");
350
83.3k
  LLVM_DEBUG(dbgs() << "\n\t\tNewCycleCount = " << NewCycleCount
351
83.3k
                    << ", OldCycleCount = " << OldCycleCount << "\n");
352
83.3k
353
83.3k
  return NewCycleCount <= OldCycleCount;
354
83.3k
}
355
356
/// helper routine to convert instructions into SC
357
void MachineCombiner::instr2instrSC(
358
    SmallVectorImpl<MachineInstr *> &Instrs,
359
168k
    SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
360
253k
  for (auto *InstrPtr : Instrs) {
361
253k
    unsigned Opc = InstrPtr->getOpcode();
362
253k
    unsigned Idx = TII->get(Opc).getSchedClass();
363
253k
    const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
364
253k
    InstrsSC.push_back(SC);
365
253k
  }
366
168k
}
367
368
/// True when the new instructions do not increase resource length
369
bool MachineCombiner::preservesResourceLen(
370
    MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
371
    SmallVectorImpl<MachineInstr *> &InsInstrs,
372
84.0k
    SmallVectorImpl<MachineInstr *> &DelInstrs) {
373
84.0k
  if (!TSchedModel.hasInstrSchedModel())
374
30
    return true;
375
84.0k
376
84.0k
  // Compute current resource length
377
84.0k
378
84.0k
  //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
379
84.0k
  SmallVector <const MachineBasicBlock *, 1> MBBarr;
380
84.0k
  MBBarr.push_back(MBB);
381
84.0k
  unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
382
84.0k
383
84.0k
  // Deal with SC rather than Instructions.
384
84.0k
  SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
385
84.0k
  SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
386
84.0k
387
84.0k
  instr2instrSC(InsInstrs, InsInstrsSC);
388
84.0k
  instr2instrSC(DelInstrs, DelInstrsSC);
389
84.0k
390
84.0k
  ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
391
84.0k
  ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
392
84.0k
393
84.0k
  // Compute new resource length.
394
84.0k
  unsigned ResLenAfterCombine =
395
84.0k
      BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
396
84.0k
397
84.0k
  LLVM_DEBUG(dbgs() << "\t\tResource length before replacement: "
398
84.0k
                    << ResLenBeforeCombine
399
84.0k
                    << " and after: " << ResLenAfterCombine << "\n";);
400
84.0k
  LLVM_DEBUG(
401
84.0k
      ResLenAfterCombine <= ResLenBeforeCombine
402
84.0k
          ? dbgs() << "\t\t  As result it IMPROVES/PRESERVES Resource Length\n"
403
84.0k
          : dbgs() << "\t\t  As result it DOES NOT improve/preserve Resource "
404
84.0k
                      "Length\n");
405
84.0k
406
84.0k
  return ResLenAfterCombine <= ResLenBeforeCombine;
407
84.0k
}
408
409
/// \returns true when new instruction sequence should be generated
410
/// independent if it lengthens critical path or not
411
89.0k
bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
412
89.0k
  if (OptSize && 
(NewSize < OldSize)72
)
413
40
    return true;
414
89.0k
  if (!TSchedModel.hasInstrSchedModelOrItineraries())
415
2.57k
    return true;
416
86.4k
  return false;
417
86.4k
}
418
419
/// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
420
/// depths if requested.
421
///
422
/// \param MBB basic block to insert instructions in
423
/// \param MI current machine instruction
424
/// \param InsInstrs new instructions to insert in \p MBB
425
/// \param DelInstrs instruction to delete from \p MBB
426
/// \param MinInstr is a pointer to the machine trace information
427
/// \param RegUnits set of live registers, needed to compute instruction depths
428
/// \param IncrementalUpdate if true, compute instruction depths incrementally,
429
///                          otherwise invalidate the trace
430
static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
431
                                     SmallVector<MachineInstr *, 16> InsInstrs,
432
                                     SmallVector<MachineInstr *, 16> DelInstrs,
433
                                     MachineTraceMetrics::Ensemble *MinInstr,
434
                                     SparseSet<LiveRegUnit> &RegUnits,
435
86.7k
                                     bool IncrementalUpdate) {
436
86.7k
  for (auto *InstrPtr : InsInstrs)
437
90.6k
    MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
438
86.7k
439
173k
  for (auto *InstrPtr : DelInstrs) {
440
173k
    InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
441
173k
    // Erase all LiveRegs defined by the removed instruction
442
173k
    for (auto I = RegUnits.begin(); I != RegUnits.end(); ) {
443
378
      if (I->MI == InstrPtr)
444
0
        I = RegUnits.erase(I);
445
378
      else
446
378
        I++;
447
378
    }
448
173k
  }
449
86.7k
450
86.7k
  if (IncrementalUpdate)
451
668
    for (auto *InstrPtr : InsInstrs)
452
830
      MinInstr->updateDepth(MBB, *InstrPtr, RegUnits);
453
86.0k
  else
454
86.0k
    MinInstr->invalidate(MBB);
455
86.7k
456
86.7k
  NumInstCombined++;
457
86.7k
}
458
459
// Check that the difference between original and new latency is decreasing for
460
// later patterns. This helps to discover sub-optimal pattern orderings.
461
void MachineCombiner::verifyPatternOrder(
462
    MachineBasicBlock *MBB, MachineInstr &Root,
463
382
    SmallVector<MachineCombinerPattern, 16> &Patterns) {
464
382
  long PrevLatencyDiff = std::numeric_limits<long>::max();
465
382
  (void)PrevLatencyDiff; // Variable is used in assert only.
466
750
  for (auto P : Patterns) {
467
750
    SmallVector<MachineInstr *, 16> InsInstrs;
468
750
    SmallVector<MachineInstr *, 16> DelInstrs;
469
750
    DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
470
750
    TII->genAlternativeCodeSequence(Root, P, InsInstrs, DelInstrs,
471
750
                                    InstrIdxForVirtReg);
472
750
    // Found pattern, but did not generate alternative sequence.
473
750
    // This can happen e.g. when an immediate could not be materialized
474
750
    // in a single instruction.
475
750
    if (InsInstrs.empty() || !TSchedModel.hasInstrSchedModelOrItineraries())
476
0
      continue;
477
750
478
750
    unsigned NewRootLatency, RootLatency;
479
750
    std::tie(NewRootLatency, RootLatency) = getLatenciesForInstrSequences(
480
750
        Root, InsInstrs, DelInstrs, MinInstr->getTrace(MBB));
481
750
    long CurrentLatencyDiff = ((long)RootLatency) - ((long)NewRootLatency);
482
750
    assert(CurrentLatencyDiff <= PrevLatencyDiff &&
483
750
           "Current pattern is better than previous pattern.");
484
750
    PrevLatencyDiff = CurrentLatencyDiff;
485
750
  }
486
382
}
487
488
/// Substitute a slow code sequence with a faster one by
489
/// evaluating instruction combining pattern.
490
/// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
491
/// combining based on machine trace metrics. Only combine a sequence of
492
/// instructions  when this neither lengthens the critical path nor increases
493
/// resource pressure. When optimizing for codesize always combine when the new
494
/// sequence is shorter.
495
2.40M
bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
496
2.40M
  bool Changed = false;
497
2.40M
  LLVM_DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
498
2.40M
499
2.40M
  bool IncrementalUpdate = false;
500
2.40M
  auto BlockIter = MBB->begin();
501
2.40M
  decltype(BlockIter) LastUpdate;
502
2.40M
  // Check if the block is in a loop.
503
2.40M
  const MachineLoop *ML = MLI->getLoopFor(MBB);
504
2.40M
  if (!MinInstr)
505
402k
    MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
506
2.40M
507
2.40M
  SparseSet<LiveRegUnit> RegUnits;
508
2.40M
  RegUnits.setUniverse(TRI->getNumRegUnits());
509
2.40M
510
25.1M
  while (BlockIter != MBB->end()) {
511
22.7M
    auto &MI = *BlockIter++;
512
22.7M
    SmallVector<MachineCombinerPattern, 16> Patterns;
513
22.7M
    // The motivating example is:
514
22.7M
    //
515
22.7M
    //     MUL  Other        MUL_op1 MUL_op2  Other
516
22.7M
    //      \    /               \      |    /
517
22.7M
    //      ADD/SUB      =>        MADD/MSUB
518
22.7M
    //      (=Root)                (=NewRoot)
519
22.7M
520
22.7M
    // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
521
22.7M
    // usually beneficial for code size it unfortunately can hurt performance
522
22.7M
    // when the ADD is on the critical path, but the MUL is not. With the
523
22.7M
    // substitution the MUL becomes part of the critical path (in form of the
524
22.7M
    // MADD) and can lengthen it on architectures where the MADD latency is
525
22.7M
    // longer than the ADD latency.
526
22.7M
    //
527
22.7M
    // For each instruction we check if it can be the root of a combiner
528
22.7M
    // pattern. Then for each pattern the new code sequence in form of MI is
529
22.7M
    // generated and evaluated. When the efficiency criteria (don't lengthen
530
22.7M
    // critical path, don't use more resources) is met the new sequence gets
531
22.7M
    // hooked up into the basic block before the old sequence is removed.
532
22.7M
    //
533
22.7M
    // The algorithm does not try to evaluate all patterns and pick the best.
534
22.7M
    // This is only an artificial restriction though. In practice there is
535
22.7M
    // mostly one pattern, and getMachineCombinerPatterns() can order patterns
536
22.7M
    // based on an internal cost heuristic. If
537
22.7M
    // machine-combiner-verify-pattern-order is enabled, all patterns are
538
22.7M
    // checked to ensure later patterns do not provide better latency savings.
539
22.7M
540
22.7M
    if (!TII->getMachineCombinerPatterns(MI, Patterns))
541
22.6M
      continue;
542
87.7k
543
87.7k
    if (VerifyPatternOrder)
544
382
      verifyPatternOrder(MBB, MI, Patterns);
545
87.7k
546
89.1k
    for (auto P : Patterns) {
547
89.1k
      SmallVector<MachineInstr *, 16> InsInstrs;
548
89.1k
      SmallVector<MachineInstr *, 16> DelInstrs;
549
89.1k
      DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
550
89.1k
      TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
551
89.1k
                                      InstrIdxForVirtReg);
552
89.1k
      unsigned NewInstCount = InsInstrs.size();
553
89.1k
      unsigned OldInstCount = DelInstrs.size();
554
89.1k
      // Found pattern, but did not generate alternative sequence.
555
89.1k
      // This can happen e.g. when an immediate could not be materialized
556
89.1k
      // in a single instruction.
557
89.1k
      if (!NewInstCount)
558
72
        continue;
559
89.1k
560
89.1k
      LLVM_DEBUG(if (dump_intrs) {
561
89.1k
        dbgs() << "\tFor the Pattern (" << (int)P
562
89.1k
               << ") these instructions could be removed\n";
563
89.1k
        for (auto const *InstrPtr : DelInstrs)
564
89.1k
          InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,
565
89.1k
                          /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);
566
89.1k
        dbgs() << "\tThese instructions could replace the removed ones\n";
567
89.1k
        for (auto const *InstrPtr : InsInstrs)
568
89.1k
          InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,
569
89.1k
                          /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);
570
89.1k
      });
571
89.1k
572
89.1k
      bool SubstituteAlways = false;
573
89.1k
      if (ML && 
TII->isThroughputPattern(P)45.7k
)
574
66
        SubstituteAlways = true;
575
89.1k
576
89.1k
      if (IncrementalUpdate) {
577
588
        // Update depths since the last incremental update.
578
588
        MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
579
588
        LastUpdate = BlockIter;
580
588
      }
581
89.1k
582
89.1k
      // Substitute when we optimize for codesize and the new sequence has
583
89.1k
      // fewer instructions OR
584
89.1k
      // the new sequence neither lengthens the critical path nor increases
585
89.1k
      // resource pressure.
586
89.1k
      if (SubstituteAlways || 
doSubstitute(NewInstCount, OldInstCount)89.0k
) {
587
2.68k
        insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
588
2.68k
                                 RegUnits, IncrementalUpdate);
589
2.68k
        // Eagerly stop after the first pattern fires.
590
2.68k
        Changed = true;
591
2.68k
        break;
592
86.4k
      } else {
593
86.4k
        // For big basic blocks, we only compute the full trace the first time
594
86.4k
        // we hit this. We do not invalidate the trace, but instead update the
595
86.4k
        // instruction depths incrementally.
596
86.4k
        // NOTE: Only the instruction depths up to MI are accurate. All other
597
86.4k
        // trace information is not updated.
598
86.4k
        MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
599
86.4k
        Traces->verifyAnalysis();
600
86.4k
        if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
601
86.4k
                                    InstrIdxForVirtReg, P,
602
86.4k
                                    !IncrementalUpdate) &&
603
86.4k
            
preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)84.0k
) {
604
84.0k
          if (MBB->size() > inc_threshold) {
605
668
            // Use incremental depth updates for basic blocks above treshold
606
668
            IncrementalUpdate = true;
607
668
            LastUpdate = BlockIter;
608
668
          }
609
84.0k
610
84.0k
          insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
611
84.0k
                                   RegUnits, IncrementalUpdate);
612
84.0k
613
84.0k
          // Eagerly stop after the first pattern fires.
614
84.0k
          Changed = true;
615
84.0k
          break;
616
84.0k
        }
617
2.36k
        // Cleanup instructions of the alternative code sequence. There is no
618
2.36k
        // use for them.
619
2.36k
        MachineFunction *MF = MBB->getParent();
620
2.36k
        for (auto *InstrPtr : InsInstrs)
621
4.33k
          MF->DeleteMachineInstr(InstrPtr);
622
2.36k
      }
623
89.1k
      InstrIdxForVirtReg.clear();
624
2.36k
    }
625
87.7k
  }
626
2.40M
627
2.40M
  if (Changed && 
IncrementalUpdate69.2k
)
628
124
    Traces->invalidate(MBB);
629
2.40M
  return Changed;
630
2.40M
}
631
632
402k
bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
633
402k
  STI = &MF.getSubtarget();
634
402k
  TII = STI->getInstrInfo();
635
402k
  TRI = STI->getRegisterInfo();
636
402k
  SchedModel = STI->getSchedModel();
637
402k
  TSchedModel.init(STI);
638
402k
  MRI = &MF.getRegInfo();
639
402k
  MLI = &getAnalysis<MachineLoopInfo>();
640
402k
  Traces = &getAnalysis<MachineTraceMetrics>();
641
402k
  MinInstr = nullptr;
642
402k
  OptSize = MF.getFunction().hasOptSize();
643
402k
644
402k
  LLVM_DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
645
402k
  if (!TII->useMachineCombiner()) {
646
0
    LLVM_DEBUG(
647
0
        dbgs()
648
0
        << "  Skipping pass: Target does not support machine combiner\n");
649
0
    return false;
650
0
  }
651
402k
652
402k
  bool Changed = false;
653
402k
654
402k
  // Try to combine instructions.
655
402k
  for (auto &MBB : MF)
656
2.40M
    Changed |= combineInstructions(&MBB);
657
402k
658
402k
  return Changed;
659
402k
}