1 //===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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.
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.
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.
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.
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
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
45 //===----------------------------------------------------------------------===//
47 #ifndef LLVM_CODEGEN_MACHINE_TRACE_METRICS_H
48 #define LLVM_CODEGEN_MACHINE_TRACE_METRICS_H
50 #include "llvm/ADT/SmallVector.h"
51 #include "llvm/CodeGen/MachineFunctionPass.h"
55 class TargetInstrInfo;
56 class TargetRegisterInfo;
57 class MachineBasicBlock;
58 class MachineRegisterInfo;
59 class MachineLoopInfo;
63 class MachineTraceMetrics : public MachineFunctionPass {
64 const MachineFunction *MF;
65 const TargetInstrInfo *TII;
66 const TargetRegisterInfo *TRI;
67 const MachineRegisterInfo *MRI;
68 const MachineLoopInfo *Loops;
74 MachineTraceMetrics();
75 void getAnalysisUsage(AnalysisUsage&) const;
76 bool runOnMachineFunction(MachineFunction&);
78 void verifyAnalysis() const;
80 friend class Ensemble;
83 /// Per-basic block information that doesn't depend on the trace through the
85 struct FixedBlockInfo {
86 /// The number of non-trivial instructions in the block.
87 /// Doesn't count PHI and COPY instructions that are likely to be removed.
90 /// True when the block contains calls.
93 FixedBlockInfo() : InstrCount(~0u), HasCalls(false) {}
95 /// Returns true when resource information for this block has been computed.
96 bool hasResources() const { return InstrCount != ~0u; }
98 /// Invalidate resource information.
99 void invalidate() { InstrCount = ~0u; }
102 /// Get the fixed resource information about MBB. Compute it on demand.
103 const FixedBlockInfo *getResources(const MachineBasicBlock*);
105 /// Per-basic block information that relates to a specific trace through the
106 /// block. Convergent traces means that only one of these is required per
107 /// block in a trace ensemble.
108 struct TraceBlockInfo {
109 /// Trace predecessor, or NULL for the first block in the trace.
110 /// Valid when hasValidDepth().
111 const MachineBasicBlock *Pred;
113 /// Trace successor, or NULL for the last block in the trace.
114 /// Valid when hasValidHeight().
115 const MachineBasicBlock *Succ;
117 /// The block number of the head of the trace. (When hasValidDepth()).
120 /// The block number of the tail of the trace. (When hasValidHeight()).
123 /// Accumulated number of instructions in the trace above this block.
124 /// Does not include instructions in this block.
127 /// Accumulated number of instructions in the trace below this block.
128 /// Includes instructions in this block.
129 unsigned InstrHeight;
131 TraceBlockInfo() : Pred(0), Succ(0), InstrDepth(~0u), InstrHeight(~0u) {}
133 /// Returns true if the depth resources have been computed from the trace
134 /// above this block.
135 bool hasValidDepth() const { return InstrDepth != ~0u; }
137 /// Returns true if the height resources have been computed from the trace
138 /// below this block.
139 bool hasValidHeight() const { return InstrHeight != ~0u; }
141 /// Invalidate depth resources when some block above this one has changed.
142 void invalidateDepth() { InstrDepth = ~0u; }
144 /// Invalidate height resources when a block below this one has changed.
145 void invalidateHeight() { InstrHeight = ~0u; }
147 void print(raw_ostream&) const;
150 /// A trace represents a plausible sequence of executed basic blocks that
151 /// passes through the current basic block one. The Trace class serves as a
152 /// handle to internal cached data structures.
158 explicit Trace(Ensemble &te, TraceBlockInfo &tbi) : TE(te), TBI(tbi) {}
159 void print(raw_ostream&) const;
161 /// Compute the total number of instructions in the trace.
162 unsigned getInstrCount() const {
163 return TBI.InstrDepth + TBI.InstrHeight;
167 /// A trace ensemble is a collection of traces selected using the same
168 /// strategy, for example 'minimum resource height'. There is one trace for
169 /// every block in the function.
171 SmallVector<TraceBlockInfo, 4> BlockInfo;
174 void computeTrace(const MachineBasicBlock*);
175 void computeDepthResources(const MachineBasicBlock*);
176 void computeHeightResources(const MachineBasicBlock*);
179 MachineTraceMetrics &CT;
180 virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0;
181 virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0;
182 explicit Ensemble(MachineTraceMetrics*);
183 const MachineLoop *getLoopFor(const MachineBasicBlock*) const;
184 const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const;
185 const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const;
189 virtual const char *getName() const =0;
190 void print(raw_ostream&) const;
191 void invalidate(const MachineBasicBlock *MBB);
194 /// Get the trace that passes through MBB.
195 /// The trace is computed on demand.
196 Trace getTrace(const MachineBasicBlock *MBB);
199 /// Strategies for selecting traces.
201 /// Select the trace through a block that has the fewest instructions.
207 /// Get the trace ensemble representing the given trace selection strategy.
208 /// The returned Ensemble object is owned by the MachineTraceMetrics analysis,
209 /// and valid for the lifetime of the analysis pass.
210 Ensemble *getEnsemble(Strategy);
212 /// Invalidate cached information about MBB. This must be called *before* MBB
213 /// is erased, or the CFG is otherwise changed.
215 /// This invalidates per-block information about resource usage for MBB only,
216 /// and it invalidates per-trace information for any trace that passes
219 /// Call Ensemble::getTrace() again to update any trace handles.
220 void invalidate(const MachineBasicBlock *MBB);
223 // One entry per basic block, indexed by block number.
224 SmallVector<FixedBlockInfo, 4> BlockInfo;
226 // One ensemble per strategy.
227 Ensemble* Ensembles[TS_NumStrategies];
230 inline raw_ostream &operator<<(raw_ostream &OS,
231 const MachineTraceMetrics::Trace &Tr) {
236 inline raw_ostream &operator<<(raw_ostream &OS,
237 const MachineTraceMetrics::Ensemble &En) {
241 } // end namespace llvm