LLVM  7.0.0svn
MachineTraceMetrics.h
Go to the documentation of this file.
1 //===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- C++ -*-===//
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 // This file defines the interface for the MachineTraceMetrics analysis pass
11 // that estimates CPU resource usage and critical data dependency paths through
12 // preferred traces. This is useful for super-scalar CPUs where execution speed
13 // can be limited both by data dependencies and by limited execution resources.
14 //
15 // Out-of-order CPUs will often be executing instructions from multiple basic
16 // blocks at the same time. This makes it difficult to estimate the resource
17 // usage accurately in a single basic block. Resources can be estimated better
18 // by looking at a trace through the current basic block.
19 //
20 // For every block, the MachineTraceMetrics pass will pick a preferred trace
21 // that passes through the block. The trace is chosen based on loop structure,
22 // branch probabilities, and resource usage. The intention is to pick likely
23 // traces that would be the most affected by code transformations.
24 //
25 // It is expensive to compute a full arbitrary trace for every block, so to
26 // save some computations, traces are chosen to be convergent. This means that
27 // if the traces through basic blocks A and B ever cross when moving away from
28 // A and B, they never diverge again. This applies in both directions - If the
29 // traces meet above A and B, they won't diverge when going further back.
30 //
31 // Traces tend to align with loops. The trace through a block in an inner loop
32 // will begin at the loop entry block and end at a back edge. If there are
33 // nested loops, the trace may begin and end at those instead.
34 //
35 // For each trace, we compute the critical path length, which is the number of
36 // cycles required to execute the trace when execution is limited by data
37 // dependencies only. We also compute the resource height, which is the number
38 // of cycles required to execute all instructions in the trace when ignoring
39 // data dependencies.
40 //
41 // Every instruction in the current block has a slack - the number of cycles
42 // execution of the instruction can be delayed without extending the critical
43 // path.
44 //
45 //===----------------------------------------------------------------------===//
46 
47 #ifndef LLVM_CODEGEN_MACHINETRACEMETRICS_H
48 #define LLVM_CODEGEN_MACHINETRACEMETRICS_H
49 
50 #include "llvm/ADT/SparseSet.h"
51 #include "llvm/ADT/ArrayRef.h"
52 #include "llvm/ADT/DenseMap.h"
53 #include "llvm/ADT/None.h"
54 #include "llvm/ADT/SmallVector.h"
58 
59 namespace llvm {
60 
61 class AnalysisUsage;
62 class MachineFunction;
63 class MachineInstr;
64 class MachineLoop;
65 class MachineLoopInfo;
66 class MachineRegisterInfo;
67 struct MCSchedClassDesc;
68 class raw_ostream;
69 class TargetInstrInfo;
70 class TargetRegisterInfo;
71 
72 // Keep track of physreg data dependencies by recording each live register unit.
73 // Associate each regunit with an instruction operand. Depending on the
74 // direction instructions are scanned, it could be the operand that defined the
75 // regunit, or the highest operand to read the regunit.
76 struct LiveRegUnit {
77  unsigned RegUnit;
78  unsigned Cycle = 0;
79  const MachineInstr *MI = nullptr;
80  unsigned Op = 0;
81 
82  unsigned getSparseSetIndex() const { return RegUnit; }
83 
84  LiveRegUnit(unsigned RU) : RegUnit(RU) {}
85 };
86 
87 
89  const MachineFunction *MF = nullptr;
90  const TargetInstrInfo *TII = nullptr;
91  const TargetRegisterInfo *TRI = nullptr;
92  const MachineRegisterInfo *MRI = nullptr;
93  const MachineLoopInfo *Loops = nullptr;
94  TargetSchedModel SchedModel;
95 
96 public:
97  friend class Ensemble;
98  friend class Trace;
99 
100  class Ensemble;
101 
102  static char ID;
103 
105 
106  void getAnalysisUsage(AnalysisUsage&) const override;
107  bool runOnMachineFunction(MachineFunction&) override;
108  void releaseMemory() override;
109  void verifyAnalysis() const override;
110 
111  /// Per-basic block information that doesn't depend on the trace through the
112  /// block.
113  struct FixedBlockInfo {
114  /// The number of non-trivial instructions in the block.
115  /// Doesn't count PHI and COPY instructions that are likely to be removed.
116  unsigned InstrCount = ~0u;
117 
118  /// True when the block contains calls.
119  bool HasCalls = false;
120 
121  FixedBlockInfo() = default;
122 
123  /// Returns true when resource information for this block has been computed.
124  bool hasResources() const { return InstrCount != ~0u; }
125 
126  /// Invalidate resource information.
127  void invalidate() { InstrCount = ~0u; }
128  };
129 
130  /// Get the fixed resource information about MBB. Compute it on demand.
131  const FixedBlockInfo *getResources(const MachineBasicBlock*);
132 
133  /// Get the scaled number of cycles used per processor resource in MBB.
134  /// This is an array with SchedModel.getNumProcResourceKinds() entries.
135  /// The getResources() function above must have been called first.
136  ///
137  /// These numbers have already been scaled by SchedModel.getResourceFactor().
138  ArrayRef<unsigned> getProcResourceCycles(unsigned MBBNum) const;
139 
140  /// A virtual register or regunit required by a basic block or its trace
141  /// successors.
142  struct LiveInReg {
143  /// The virtual register required, or a register unit.
144  unsigned Reg;
145 
146  /// For virtual registers: Minimum height of the defining instruction.
147  /// For regunits: Height of the highest user in the trace.
148  unsigned Height;
149 
150  LiveInReg(unsigned Reg, unsigned Height = 0) : Reg(Reg), Height(Height) {}
151  };
152 
153  /// Per-basic block information that relates to a specific trace through the
154  /// block. Convergent traces means that only one of these is required per
155  /// block in a trace ensemble.
156  struct TraceBlockInfo {
157  /// Trace predecessor, or NULL for the first block in the trace.
158  /// Valid when hasValidDepth().
159  const MachineBasicBlock *Pred = nullptr;
160 
161  /// Trace successor, or NULL for the last block in the trace.
162  /// Valid when hasValidHeight().
163  const MachineBasicBlock *Succ = nullptr;
164 
165  /// The block number of the head of the trace. (When hasValidDepth()).
166  unsigned Head;
167 
168  /// The block number of the tail of the trace. (When hasValidHeight()).
169  unsigned Tail;
170 
171  /// Accumulated number of instructions in the trace above this block.
172  /// Does not include instructions in this block.
173  unsigned InstrDepth = ~0u;
174 
175  /// Accumulated number of instructions in the trace below this block.
176  /// Includes instructions in this block.
177  unsigned InstrHeight = ~0u;
178 
179  TraceBlockInfo() = default;
180 
181  /// Returns true if the depth resources have been computed from the trace
182  /// above this block.
183  bool hasValidDepth() const { return InstrDepth != ~0u; }
184 
185  /// Returns true if the height resources have been computed from the trace
186  /// below this block.
187  bool hasValidHeight() const { return InstrHeight != ~0u; }
188 
189  /// Invalidate depth resources when some block above this one has changed.
190  void invalidateDepth() { InstrDepth = ~0u; HasValidInstrDepths = false; }
191 
192  /// Invalidate height resources when a block below this one has changed.
193  void invalidateHeight() { InstrHeight = ~0u; HasValidInstrHeights = false; }
194 
195  /// Assuming that this is a dominator of TBI, determine if it contains
196  /// useful instruction depths. A dominating block can be above the current
197  /// trace head, and any dependencies from such a far away dominator are not
198  /// expected to affect the critical path.
199  ///
200  /// Also returns true when TBI == this.
201  bool isUsefulDominator(const TraceBlockInfo &TBI) const {
202  // The trace for TBI may not even be calculated yet.
203  if (!hasValidDepth() || !TBI.hasValidDepth())
204  return false;
205  // Instruction depths are only comparable if the traces share a head.
206  if (Head != TBI.Head)
207  return false;
208  // It is almost always the case that TBI belongs to the same trace as
209  // this block, but rare convoluted cases involving irreducible control
210  // flow, a dominator may share a trace head without actually being on the
211  // same trace as TBI. This is not a big problem as long as it doesn't
212  // increase the instruction depth.
213  return HasValidInstrDepths && InstrDepth <= TBI.InstrDepth;
214  }
215 
216  // Data-dependency-related information. Per-instruction depth and height
217  // are computed from data dependencies in the current trace, using
218  // itinerary data.
219 
220  /// Instruction depths have been computed. This implies hasValidDepth().
221  bool HasValidInstrDepths = false;
222 
223  /// Instruction heights have been computed. This implies hasValidHeight().
224  bool HasValidInstrHeights = false;
225 
226  /// Critical path length. This is the number of cycles in the longest data
227  /// dependency chain through the trace. This is only valid when both
228  /// HasValidInstrDepths and HasValidInstrHeights are set.
229  unsigned CriticalPath;
230 
231  /// Live-in registers. These registers are defined above the current block
232  /// and used by this block or a block below it.
233  /// This does not include PHI uses in the current block, but it does
234  /// include PHI uses in deeper blocks.
236 
237  void print(raw_ostream&) const;
238  };
239 
240  /// InstrCycles represents the cycle height and depth of an instruction in a
241  /// trace.
242  struct InstrCycles {
243  /// Earliest issue cycle as determined by data dependencies and instruction
244  /// latencies from the beginning of the trace. Data dependencies from
245  /// before the trace are not included.
246  unsigned Depth;
247 
248  /// Minimum number of cycles from this instruction is issued to the of the
249  /// trace, as determined by data dependencies and instruction latencies.
250  unsigned Height;
251  };
252 
253  /// A trace represents a plausible sequence of executed basic blocks that
254  /// passes through the current basic block one. The Trace class serves as a
255  /// handle to internal cached data structures.
256  class Trace {
257  Ensemble &TE;
258  TraceBlockInfo &TBI;
259 
260  unsigned getBlockNum() const { return &TBI - &TE.BlockInfo[0]; }
261 
262  public:
263  explicit Trace(Ensemble &te, TraceBlockInfo &tbi) : TE(te), TBI(tbi) {}
264 
265  void print(raw_ostream&) const;
266 
267  /// Compute the total number of instructions in the trace.
268  unsigned getInstrCount() const {
269  return TBI.InstrDepth + TBI.InstrHeight;
270  }
271 
272  /// Return the resource depth of the top/bottom of the trace center block.
273  /// This is the number of cycles required to execute all instructions from
274  /// the trace head to the trace center block. The resource depth only
275  /// considers execution resources, it ignores data dependencies.
276  /// When Bottom is set, instructions in the trace center block are included.
277  unsigned getResourceDepth(bool Bottom) const;
278 
279  /// Return the resource length of the trace. This is the number of cycles
280  /// required to execute the instructions in the trace if they were all
281  /// independent, exposing the maximum instruction-level parallelism.
282  ///
283  /// Any blocks in Extrablocks are included as if they were part of the
284  /// trace. Likewise, extra resources required by the specified scheduling
285  /// classes are included. For the caller to account for extra machine
286  /// instructions, it must first resolve each instruction's scheduling class.
287  unsigned getResourceLength(
290  ArrayRef<const MCSchedClassDesc *> RemoveInstrs = None) const;
291 
292  /// Return the length of the (data dependency) critical path through the
293  /// trace.
294  unsigned getCriticalPath() const { return TBI.CriticalPath; }
295 
296  /// Return the depth and height of MI. The depth is only valid for
297  /// instructions in or above the trace center block. The height is only
298  /// valid for instructions in or below the trace center block.
300  return TE.Cycles.lookup(&MI);
301  }
302 
303  /// Return the slack of MI. This is the number of cycles MI can be delayed
304  /// before the critical path becomes longer.
305  /// MI must be an instruction in the trace center block.
306  unsigned getInstrSlack(const MachineInstr &MI) const;
307 
308  /// Return the Depth of a PHI instruction in a trace center block successor.
309  /// The PHI does not have to be part of the trace.
310  unsigned getPHIDepth(const MachineInstr &PHI) const;
311 
312  /// A dependence is useful if the basic block of the defining instruction
313  /// is part of the trace of the user instruction. It is assumed that DefMI
314  /// dominates UseMI (see also isUsefulDominator).
315  bool isDepInTrace(const MachineInstr &DefMI,
316  const MachineInstr &UseMI) const;
317  };
318 
319  /// A trace ensemble is a collection of traces selected using the same
320  /// strategy, for example 'minimum resource height'. There is one trace for
321  /// every block in the function.
322  class Ensemble {
323  friend class Trace;
324 
327  SmallVector<unsigned, 0> ProcResourceDepths;
328  SmallVector<unsigned, 0> ProcResourceHeights;
329 
330  void computeTrace(const MachineBasicBlock*);
331  void computeDepthResources(const MachineBasicBlock*);
332  void computeHeightResources(const MachineBasicBlock*);
333  unsigned computeCrossBlockCriticalPath(const TraceBlockInfo&);
334  void computeInstrDepths(const MachineBasicBlock*);
335  void computeInstrHeights(const MachineBasicBlock*);
336  void addLiveIns(const MachineInstr *DefMI, unsigned DefOp,
338 
339  protected:
341 
342  explicit Ensemble(MachineTraceMetrics*);
343 
344  virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0;
345  virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0;
346  const MachineLoop *getLoopFor(const MachineBasicBlock*) const;
347  const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const;
348  const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const;
349  ArrayRef<unsigned> getProcResourceDepths(unsigned MBBNum) const;
350  ArrayRef<unsigned> getProcResourceHeights(unsigned MBBNum) const;
351 
352  public:
353  virtual ~Ensemble();
354 
355  virtual const char *getName() const = 0;
356  void print(raw_ostream&) const;
357  void invalidate(const MachineBasicBlock *MBB);
358  void verify() const;
359 
360  /// Get the trace that passes through MBB.
361  /// The trace is computed on demand.
362  Trace getTrace(const MachineBasicBlock *MBB);
363 
364  /// Updates the depth of an machine instruction, given RegUnits.
365  void updateDepth(TraceBlockInfo &TBI, const MachineInstr&,
366  SparseSet<LiveRegUnit> &RegUnits);
367  void updateDepth(const MachineBasicBlock *, const MachineInstr&,
368  SparseSet<LiveRegUnit> &RegUnits);
369 
370  /// Updates the depth of the instructions from Start to End.
371  void updateDepths(MachineBasicBlock::iterator Start,
373  SparseSet<LiveRegUnit> &RegUnits);
374 
375  };
376 
377  /// Strategies for selecting traces.
378  enum Strategy {
379  /// Select the trace through a block that has the fewest instructions.
381 
382  TS_NumStrategies
383  };
384 
385  /// Get the trace ensemble representing the given trace selection strategy.
386  /// The returned Ensemble object is owned by the MachineTraceMetrics analysis,
387  /// and valid for the lifetime of the analysis pass.
388  Ensemble *getEnsemble(Strategy);
389 
390  /// Invalidate cached information about MBB. This must be called *before* MBB
391  /// is erased, or the CFG is otherwise changed.
392  ///
393  /// This invalidates per-block information about resource usage for MBB only,
394  /// and it invalidates per-trace information for any trace that passes
395  /// through MBB.
396  ///
397  /// Call Ensemble::getTrace() again to update any trace handles.
398  void invalidate(const MachineBasicBlock *MBB);
399 
400 private:
401  // One entry per basic block, indexed by block number.
403 
404  // Cycles consumed on each processor resource per block.
405  // The number of processor resource kinds is constant for a given subtarget,
406  // but it is not known at compile time. The number of cycles consumed by
407  // block B on processor resource R is at ProcResourceCycles[B*Kinds + R]
408  // where Kinds = SchedModel.getNumProcResourceKinds().
409  SmallVector<unsigned, 0> ProcResourceCycles;
410 
411  // One ensemble per strategy.
412  Ensemble* Ensembles[TS_NumStrategies];
413 
414  // Convert scaled resource usage to a cycle count that can be compared with
415  // latencies.
416  unsigned getCycles(unsigned Scaled) {
417  unsigned Factor = SchedModel.getLatencyFactor();
418  return (Scaled + Factor - 1) / Factor;
419  }
420 };
421 
423  const MachineTraceMetrics::Trace &Tr) {
424  Tr.print(OS);
425  return OS;
426 }
427 
429  const MachineTraceMetrics::Ensemble &En) {
430  En.print(OS);
431  return OS;
432 }
433 
434 } // end namespace llvm
435 
436 #endif // LLVM_CODEGEN_MACHINETRACEMETRICS_H
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...
void invalidateHeight()
Invalidate height resources when a block below this one has changed.
A trace ensemble is a collection of traces selected using the same strategy, for example &#39;minimum res...
static unsigned InstrCount
Trace(Ensemble &te, TraceBlockInfo &tbi)
Hexagon Hardware Loops
bool hasResources() const
Returns true when resource information for this block has been computed.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Provide an instruction scheduling machine model to CodeGen passes.
const HexagonInstrInfo * TII
Strategy
Strategies for selecting traces.
const MachineInstr * MI
static StringRef getName(Value *V)
LiveInReg(unsigned Reg, unsigned Height=0)
bool hasValidHeight() const
Returns true if the height resources have been computed from the trace below this block...
Select the trace through a block that has the fewest instructions.
bool hasValidDepth() const
Returns true if the depth resources have been computed from the trace above this block.
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
unsigned Height
For virtual registers: Minimum height of the defining instruction.
LiveRegUnit(unsigned RU)
TargetInstrInfo - Interface to description of machine instruction set.
void invalidateDepth()
Invalidate depth resources when some block above this one has changed.
unsigned CriticalPath
Critical path length.
unsigned const MachineRegisterInfo * MRI
void invalidate()
Invalidate resource information.
unsigned InstrHeight
Accumulated number of instructions in the trace below this block.
MachineInstrBuilder & UseMI
unsigned getCriticalPath() const
Return the length of the (data dependency) critical path through the trace.
InstrCycles getInstrCycles(const MachineInstr &MI) const
Return the depth and height of MI.
Per-basic block information that doesn&#39;t depend on the trace through the block.
unsigned getLatencyFactor() const
Multiply cycle count by this factor to normalize it relative to other resources.
Represent the analysis usage information of a pass.
static const unsigned End
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
unsigned Tail
The block number of the tail of the trace. (When hasValidHeight()).
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A trace represents a plausible sequence of executed basic blocks that passes through the current basi...
bool verify(const TargetRegisterInfo &TRI) const
Check that information hold by this instance make sense for the given TRI.
unsigned getInstrCount() const
Compute the total number of instructions in the trace.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
unsigned Height
Minimum number of cycles from this instruction is issued to the of the trace, as determined by data d...
MachineInstrBuilder MachineInstrBuilder & DefMI
Per-basic block information that relates to a specific trace through the block.
unsigned Head
The block number of the head of the trace. (When hasValidDepth()).
unsigned Reg
The virtual register required, or a register unit.
A virtual register or regunit required by a basic block or its trace successors.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:60
SparseSet - Fast set implmentation for objects that can be identified by small unsigned keys...
Definition: SparseSet.h:123
InstrCycles represents the cycle height and depth of an instruction in a trace.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
SmallVector< LiveInReg, 4 > LiveIns
Live-in registers.
unsigned InstrDepth
Accumulated number of instructions in the trace above this block.
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
bool isUsefulDominator(const TraceBlockInfo &TBI) const
Assuming that this is a dominator of TBI, determine if it contains useful instruction depths...
unsigned getSparseSetIndex() const