aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/MachineTraceMetrics.h
blob: 460730b040591c7cebc0ecbc8945f5e228f7ffd5 (plain)
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
//===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// 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_MACHINE_TRACE_METRICS_H
#define LLVM_CODEGEN_MACHINE_TRACE_METRICS_H

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/TargetSchedule.h"

namespace llvm {

class InstrItineraryData;
class MachineBasicBlock;
class MachineInstr;
class MachineLoop;
class MachineLoopInfo;
class MachineRegisterInfo;
class TargetInstrInfo;
class TargetRegisterInfo;
class raw_ostream;

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

public:
  class Ensemble;
  class Trace;
  static char ID;
  MachineTraceMetrics();
  void getAnalysisUsage(AnalysisUsage&) const;
  bool runOnMachineFunction(MachineFunction&);
  void releaseMemory();
  void verifyAnalysis() const;

  friend class Ensemble;
  friend class Trace;

  /// 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;

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

    FixedBlockInfo() : InstrCount(~0u), HasCalls(false) {}

    /// 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*);

  /// 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;

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

    /// 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;

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

    TraceBlockInfo() :
      Pred(0), Succ(0),
      InstrDepth(~0u), InstrHeight(~0u),
      HasValidInstrDepths(false), HasValidInstrHeights(false) {}

    /// 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; }

    /// Determine if this block belongs to the same trace as TBI and comes
    /// before it in the trace.
    /// Also returns true when TBI == this.
    bool isEarlierInSameTrace(const TraceBlockInfo &TBI) const {
      return hasValidDepth() && TBI.hasValidDepth() &&
        Head == TBI.Head && 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;

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

    /// 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.
    unsigned getResourceLength(ArrayRef<const MachineBasicBlock*> Extrablocks =
                               ArrayRef<const MachineBasicBlock*>()) 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 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 {
    SmallVector<TraceBlockInfo, 4> BlockInfo;
    DenseMap<const MachineInstr*, InstrCycles> Cycles;
    friend class Trace;

    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;
    virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0;
    virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0;
    explicit Ensemble(MachineTraceMetrics*);
    const MachineLoop *getLoopFor(const MachineBasicBlock*) const;
    const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const;
    const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) 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);
  };

  /// 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;

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

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