llvm.org GIT mirror llvm / b29d4ba include / llvm / CodeGen / MachineTraceMetrics.h
b29d4ba

Tree @b29d4ba (Download .tar.gz)

MachineTraceMetrics.h @b29d4baraw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
//===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the interface for the MachineTraceMetrics analysis pass
// that estimates CPU resource usage and critical data dependency paths through
// preferred traces. This is useful for super-scalar CPUs where execution speed
// can be limited both by data dependencies and by limited execution resources.
//
// Out-of-order CPUs will often be executing instructions from multiple basic
// blocks at the same time. This makes it difficult to estimate the resource
// usage accurately in a single basic block. Resources can be estimated better
// by looking at a trace through the current basic block.
//
// For every block, the MachineTraceMetrics pass will pick a preferred trace
// that passes through the block. The trace is chosen based on loop structure,
// branch probabilities, and resource usage. The intention is to pick likely
// traces that would be the most affected by code transformations.
//
// It is expensive to compute a full arbitrary trace for every block, so to
// save some computations, traces are chosen to be convergent. This means that
// if the traces through basic blocks A and B ever cross when moving away from
// A and B, they never diverge again. This applies in both directions - If the
// traces meet above A and B, they won't diverge when going further back.
//
// Traces tend to align with loops. The trace through a block in an inner loop
// will begin at the loop entry block and end at a back edge. If there are
// nested loops, the trace may begin and end at those instead.
//
// For each trace, we compute the critical path length, which is the number of
// cycles required to execute the trace when execution is limited by data
// dependencies only. We also compute the resource height, which is the number
// of cycles required to execute all instructions in the trace when ignoring
// data dependencies.
//
// Every instruction in the current block has a slack - the number of cycles
// execution of the instruction can be delayed without extending the critical
// path.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_MACHINETRACEMETRICS_H
#define LLVM_CODEGEN_MACHINETRACEMETRICS_H

#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/TargetSchedule.h"

namespace llvm {

class AnalysisUsage;
class MachineFunction;
class MachineInstr;
class MachineLoop;
class MachineLoopInfo;
class MachineRegisterInfo;
struct MCSchedClassDesc;
class raw_ostream;
class TargetInstrInfo;
class TargetRegisterInfo;

// Keep track of physreg data dependencies by recording each live register unit.
// Associate each regunit with an instruction operand. Depending on the
// direction instructions are scanned, it could be the operand that defined the
// regunit, or the highest operand to read the regunit.
struct LiveRegUnit {
  unsigned RegUnit;
  unsigned Cycle = 0;
  const MachineInstr *MI = nullptr;
  unsigned Op = 0;

  unsigned getSparseSetIndex() const { return RegUnit; }

  LiveRegUnit(unsigned RU) : RegUnit(RU) {}
};


class MachineTraceMetrics : public MachineFunctionPass {
  const MachineFunction *MF = nullptr;
  const TargetInstrInfo *TII = nullptr;
  const TargetRegisterInfo *TRI = nullptr;
  const MachineRegisterInfo *MRI = nullptr;
  const MachineLoopInfo *Loops = nullptr;
  TargetSchedModel SchedModel;

public:
  friend class Ensemble;
  friend class Trace;

  class Ensemble;

  static char ID;

  MachineTraceMetrics();

  void getAnalysisUsage(AnalysisUsage&) const override;
  bool runOnMachineFunction(MachineFunction&) override;
  void releaseMemory() override;
  void verifyAnalysis() const override;

  /// Per-basic block information that doesn't depend on the trace through the
  /// block.
  struct FixedBlockInfo {
    /// The number of non-trivial instructions in the block.
    /// Doesn't count PHI and COPY instructions that are likely to be removed.
    unsigned InstrCount = ~0u;

    /// True when the block contains calls.
    bool HasCalls = false;

    FixedBlockInfo() = default;

    /// Returns true when resource information for this block has been computed.
    bool hasResources() const { return InstrCount != ~0u; }

    /// Invalidate resource information.
    void invalidate() { InstrCount = ~0u; }
  };

  /// Get the fixed resource information about MBB. Compute it on demand.
  const FixedBlockInfo *getResources(const MachineBasicBlock*);

  /// Get the scaled number of cycles used per processor resource in MBB.
  /// This is an array with SchedModel.getNumProcResourceKinds() entries.
  /// The getResources() function above must have been called first.
  ///
  /// These numbers have already been scaled by SchedModel.getResourceFactor().
  ArrayRef<unsigned> getProcResourceCycles(unsigned MBBNum) const;

  /// A virtual register or regunit required by a basic block or its trace
  /// successors.
  struct LiveInReg {
    /// The virtual register required, or a register unit.
    unsigned Reg;

    /// For virtual registers: Minimum height of the defining instruction.
    /// For regunits: Height of the highest user in the trace.
    unsigned Height;

    LiveInReg(unsigned Reg, unsigned Height = 0) : Reg(Reg), Height(Height) {}
  };

  /// Per-basic block information that relates to a specific trace through the
  /// block. Convergent traces means that only one of these is required per
  /// block in a trace ensemble.
  struct TraceBlockInfo {
    /// Trace predecessor, or NULL for the first block in the trace.
    /// Valid when hasValidDepth().
    const MachineBasicBlock *Pred = nullptr;

    /// Trace successor, or NULL for the last block in the trace.
    /// Valid when hasValidHeight().
    const MachineBasicBlock *Succ = nullptr;

    /// The block number of the head of the trace. (When hasValidDepth()).
    unsigned Head;

    /// The block number of the tail of the trace. (When hasValidHeight()).
    unsigned Tail;

    /// Accumulated number of instructions in the trace above this block.
    /// Does not include instructions in this block.
    unsigned InstrDepth = ~0u;

    /// Accumulated number of instructions in the trace below this block.
    /// Includes instructions in this block.
    unsigned InstrHeight = ~0u;

    TraceBlockInfo() = default;

    /// Returns true if the depth resources have been computed from the trace
    /// above this block.
    bool hasValidDepth() const { return InstrDepth != ~0u; }

    /// Returns true if the height resources have been computed from the trace
    /// below this block.
    bool hasValidHeight() const { return InstrHeight != ~0u; }

    /// Invalidate depth resources when some block above this one has changed.
    void invalidateDepth() { InstrDepth = ~0u; HasValidInstrDepths = false; }

    /// Invalidate height resources when a block below this one has changed.
    void invalidateHeight() { InstrHeight = ~0u; HasValidInstrHeights = false; }

    /// Assuming that this is a dominator of TBI, determine if it contains
    /// useful instruction depths. A dominating block can be above the current
    /// trace head, and any dependencies from such a far away dominator are not
    /// expected to affect the critical path.
    ///
    /// Also returns true when TBI == this.
    bool isUsefulDominator(const TraceBlockInfo &TBI) const {
      // The trace for TBI may not even be calculated yet.
      if (!hasValidDepth() || !TBI.hasValidDepth())
        return false;
      // Instruction depths are only comparable if the traces share a head.
      if (Head != TBI.Head)
        return false;
      // It is almost always the case that TBI belongs to the same trace as
      // this block, but rare convoluted cases involving irreducible control
      // flow, a dominator may share a trace head without actually being on the
      // same trace as TBI. This is not a big problem as long as it doesn't
      // increase the instruction depth.
      return HasValidInstrDepths && InstrDepth <= TBI.InstrDepth;
    }

    // Data-dependency-related information. Per-instruction depth and height
    // are computed from data dependencies in the current trace, using
    // itinerary data.

    /// Instruction depths have been computed. This implies hasValidDepth().
    bool HasValidInstrDepths = false;

    /// Instruction heights have been computed. This implies hasValidHeight().
    bool HasValidInstrHeights = false;

    /// Critical path length. This is the number of cycles in the longest data
    /// dependency chain through the trace. This is only valid when both
    /// HasValidInstrDepths and HasValidInstrHeights are set.
    unsigned CriticalPath;

    /// Live-in registers. These registers are defined above the current block
    /// and used by this block or a block below it.
    /// This does not include PHI uses in the current block, but it does
    /// include PHI uses in deeper blocks.
    SmallVector<LiveInReg, 4> LiveIns;

    void print(raw_ostream&) const;
  };

  /// InstrCycles represents the cycle height and depth of an instruction in a
  /// trace.
  struct InstrCycles {
    /// Earliest issue cycle as determined by data dependencies and instruction
    /// latencies from the beginning of the trace. Data dependencies from
    /// before the trace are not included.
    unsigned Depth;

    /// Minimum number of cycles from this instruction is issued to the of the
    /// trace, as determined by data dependencies and instruction latencies.
    unsigned Height;
  };

  /// A trace represents a plausible sequence of executed basic blocks that
  /// passes through the current basic block one. The Trace class serves as a
  /// handle to internal cached data structures.
  class Trace {
    Ensemble &TE;
    TraceBlockInfo &TBI;

    unsigned getBlockNum() const { return &TBI - &TE.BlockInfo[0]; }

  public:
    explicit Trace(Ensemble &te, TraceBlockInfo &tbi) : TE(te), TBI(tbi) {}

    void print(raw_ostream&) const;

    /// Compute the total number of instructions in the trace.
    unsigned getInstrCount() const {
      return TBI.InstrDepth + TBI.InstrHeight;
    }

    /// Return the resource depth of the top/bottom of the trace center block.
    /// This is the number of cycles required to execute all instructions from
    /// the trace head to the trace center block. The resource depth only
    /// considers execution resources, it ignores data dependencies.
    /// When Bottom is set, instructions in the trace center block are included.
    unsigned getResourceDepth(bool Bottom) const;

    /// Return the resource length of the trace. This is the number of cycles
    /// required to execute the instructions in the trace if they were all
    /// independent, exposing the maximum instruction-level parallelism.
    ///
    /// Any blocks in Extrablocks are included as if they were part of the
    /// trace. Likewise, extra resources required by the specified scheduling
    /// classes are included. For the caller to account for extra machine
    /// instructions, it must first resolve each instruction's scheduling class.
    unsigned getResourceLength(
        ArrayRef<const MachineBasicBlock *> Extrablocks = None,
        ArrayRef<const MCSchedClassDesc *> ExtraInstrs = None,
        ArrayRef<const MCSchedClassDesc *> RemoveInstrs = None) const;

    /// Return the length of the (data dependency) critical path through the
    /// trace.
    unsigned getCriticalPath() const { return TBI.CriticalPath; }

    /// Return the depth and height of MI. The depth is only valid for
    /// instructions in or above the trace center block. The height is only
    /// valid for instructions in or below the trace center block.
    InstrCycles getInstrCycles(const MachineInstr &MI) const {
      return TE.Cycles.lookup(&MI);
    }

    /// Return the slack of MI. This is the number of cycles MI can be delayed
    /// before the critical path becomes longer.
    /// MI must be an instruction in the trace center block.
    unsigned getInstrSlack(const MachineInstr &MI) const;

    /// Return the Depth of a PHI instruction in a trace center block successor.
    /// The PHI does not have to be part of the trace.
    unsigned getPHIDepth(const MachineInstr &PHI) const;

    /// A dependence is useful if the basic block of the defining instruction
    /// is part of the trace of the user instruction. It is assumed that DefMI
    /// dominates UseMI (see also isUsefulDominator).
    bool isDepInTrace(const MachineInstr &DefMI,
                      const MachineInstr &UseMI) const;
  };

  /// A trace ensemble is a collection of traces selected using the same
  /// strategy, for example 'minimum resource height'. There is one trace for
  /// every block in the function.
  class Ensemble {
    friend class Trace;

    SmallVector<TraceBlockInfo, 4> BlockInfo;
    DenseMap<const MachineInstr*, InstrCycles> Cycles;
    SmallVector<unsigned, 0> ProcResourceDepths;
    SmallVector<unsigned, 0> ProcResourceHeights;

    void computeTrace(const MachineBasicBlock*);
    void computeDepthResources(const MachineBasicBlock*);
    void computeHeightResources(const MachineBasicBlock*);
    unsigned computeCrossBlockCriticalPath(const TraceBlockInfo&);
    void computeInstrDepths(const MachineBasicBlock*);
    void computeInstrHeights(const MachineBasicBlock*);
    void addLiveIns(const MachineInstr *DefMI, unsigned DefOp,
                    ArrayRef<const MachineBasicBlock*> Trace);

  protected:
    MachineTraceMetrics &MTM;

    explicit Ensemble(MachineTraceMetrics*);

    virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0;
    virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0;
    const MachineLoop *getLoopFor(const MachineBasicBlock*) const;
    const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const;
    const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const;
    ArrayRef<unsigned> getProcResourceDepths(unsigned MBBNum) const;
    ArrayRef<unsigned> getProcResourceHeights(unsigned MBBNum) const;

  public:
    virtual ~Ensemble();

    virtual const char *getName() const = 0;
    void print(raw_ostream&) const;
    void invalidate(const MachineBasicBlock *MBB);
    void verify() const;

    /// Get the trace that passes through MBB.
    /// The trace is computed on demand.
    Trace getTrace(const MachineBasicBlock *MBB);

    /// Updates the depth of an machine instruction, given RegUnits.
    void updateDepth(TraceBlockInfo &TBI, const MachineInstr&,
                     SparseSet<LiveRegUnit> &RegUnits);
    void updateDepth(const MachineBasicBlock *, const MachineInstr&,
                     SparseSet<LiveRegUnit> &RegUnits);

    /// Updates the depth of the instructions from Start to End.
    void updateDepths(MachineBasicBlock::iterator Start,
                      MachineBasicBlock::iterator End,
                      SparseSet<LiveRegUnit> &RegUnits);

  };

  /// Strategies for selecting traces.
  enum Strategy {
    /// Select the trace through a block that has the fewest instructions.
    TS_MinInstrCount,

    TS_NumStrategies
  };

  /// Get the trace ensemble representing the given trace selection strategy.
  /// The returned Ensemble object is owned by the MachineTraceMetrics analysis,
  /// and valid for the lifetime of the analysis pass.
  Ensemble *getEnsemble(Strategy);

  /// Invalidate cached information about MBB. This must be called *before* MBB
  /// is erased, or the CFG is otherwise changed.
  ///
  /// This invalidates per-block information about resource usage for MBB only,
  /// and it invalidates per-trace information for any trace that passes
  /// through MBB.
  ///
  /// Call Ensemble::getTrace() again to update any trace handles.
  void invalidate(const MachineBasicBlock *MBB);

private:
  // One entry per basic block, indexed by block number.
  SmallVector<FixedBlockInfo, 4> BlockInfo;

  // Cycles consumed on each processor resource per block.
  // The number of processor resource kinds is constant for a given subtarget,
  // but it is not known at compile time. The number of cycles consumed by
  // block B on processor resource R is at ProcResourceCycles[B*Kinds + R]
  // where Kinds = SchedModel.getNumProcResourceKinds().
  SmallVector<unsigned, 0> ProcResourceCycles;

  // One ensemble per strategy.
  Ensemble* Ensembles[TS_NumStrategies];

  // Convert scaled resource usage to a cycle count that can be compared with
  // latencies.
  unsigned getCycles(unsigned Scaled) {
    unsigned Factor = SchedModel.getLatencyFactor();
    return (Scaled + Factor - 1) / Factor;
  }
};

inline raw_ostream &operator<<(raw_ostream &OS,
                               const MachineTraceMetrics::Trace &Tr) {
  Tr.print(OS);
  return OS;
}

inline raw_ostream &operator<<(raw_ostream &OS,
                               const MachineTraceMetrics::Ensemble &En) {
  En.print(OS);
  return OS;
}

} // end namespace llvm

#endif // LLVM_CODEGEN_MACHINETRACEMETRICS_H