/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/CodeGen/MachineTraceMetrics.h
Line | Count | Source (jump to first uncovered line) |
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" |
55 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
56 | | #include "llvm/CodeGen/MachineFunctionPass.h" |
57 | | #include "llvm/CodeGen/TargetSchedule.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 | 8.09M | unsigned getSparseSetIndex() const { return RegUnit; } |
83 | | |
84 | 2.91M | LiveRegUnit(unsigned RU) : RegUnit(RU) {} |
85 | | }; |
86 | | |
87 | | |
88 | | class MachineTraceMetrics : public MachineFunctionPass { |
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 | | |
104 | | MachineTraceMetrics(); |
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 | 10.5M | FixedBlockInfo() = default; |
122 | | |
123 | | /// Returns true when resource information for this block has been computed. |
124 | 3.73M | bool hasResources() const { return InstrCount != ~0u; } |
125 | | |
126 | | /// Invalidate resource information. |
127 | 91.9k | 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 | 1.90M | 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 | 7.06M | TraceBlockInfo() = default; |
180 | | |
181 | | /// Returns true if the depth resources have been computed from the trace |
182 | | /// above this block. |
183 | 24.6M | 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 | 4.32M | bool hasValidHeight() const { return InstrHeight != ~0u; } |
188 | | |
189 | | /// Invalidate depth resources when some block above this one has changed. |
190 | 197k | void invalidateDepth() { InstrDepth = ~0u; HasValidInstrDepths = false; } |
191 | | |
192 | | /// Invalidate height resources when a block below this one has changed. |
193 | 222k | 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 | 10.4M | bool isUsefulDominator(const TraceBlockInfo &TBI) const { |
202 | 10.4M | // The trace for TBI may not even be calculated yet. |
203 | 10.4M | if (!hasValidDepth() || 10.4M !TBI.hasValidDepth()9.87M ) |
204 | 602k | return false; |
205 | 10.4M | // Instruction depths are only comparable if the traces share a head. |
206 | 9.87M | if (9.87M Head != TBI.Head9.87M ) |
207 | 297k | return false; |
208 | 9.87M | // It is almost always the case that TBI belongs to the same trace as |
209 | 9.87M | // this block, but rare convoluted cases involving irreducible control |
210 | 9.87M | // flow, a dominator may share a trace head without actually being on the |
211 | 9.87M | // same trace as TBI. This is not a big problem as long as it doesn't |
212 | 9.87M | // increase the instruction depth. |
213 | 9.57M | return HasValidInstrDepths && 9.57M InstrDepth <= TBI.InstrDepth9.55M ; |
214 | 10.4M | } |
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. |
235 | | SmallVector<LiveInReg, 4> LiveIns; |
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 | 842k | unsigned getBlockNum() const { return &TBI - &TE.BlockInfo[0]; } |
261 | | |
262 | | public: |
263 | 272k | 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 | 0 | unsigned getInstrCount() const { |
269 | 0 | return TBI.InstrDepth + TBI.InstrHeight; |
270 | 0 | } |
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( |
288 | | ArrayRef<const MachineBasicBlock *> Extrablocks = None, |
289 | | ArrayRef<const MCSchedClassDesc *> ExtraInstrs = None, |
290 | | ArrayRef<const MCSchedClassDesc *> RemoveInstrs = None) const; |
291 | | |
292 | | /// Return the length of the (data dependency) critical path through the |
293 | | /// trace. |
294 | 154k | 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. |
299 | 722k | InstrCycles getInstrCycles(const MachineInstr &MI) const { |
300 | 722k | return TE.Cycles.lookup(&MI); |
301 | 722k | } |
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 | | |
325 | | SmallVector<TraceBlockInfo, 4> BlockInfo; |
326 | | DenseMap<const MachineInstr*, InstrCycles> Cycles; |
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, |
337 | | ArrayRef<const MachineBasicBlock*> Trace); |
338 | | |
339 | | protected: |
340 | | MachineTraceMetrics &MTM; |
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, |
372 | | MachineBasicBlock::iterator End, |
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. |
380 | | TS_MinInstrCount, |
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. |
402 | | SmallVector<FixedBlockInfo, 4> BlockInfo; |
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 | 359k | unsigned getCycles(unsigned Scaled) { |
417 | 359k | unsigned Factor = SchedModel.getLatencyFactor(); |
418 | 359k | return (Scaled + Factor - 1) / Factor; |
419 | 359k | } |
420 | | }; |
421 | | |
422 | | inline raw_ostream &operator<<(raw_ostream &OS, |
423 | 0 | const MachineTraceMetrics::Trace &Tr) { |
424 | 0 | Tr.print(OS); |
425 | 0 | return OS; |
426 | 0 | } |
427 | | |
428 | | inline raw_ostream &operator<<(raw_ostream &OS, |
429 | 0 | const MachineTraceMetrics::Ensemble &En) { |
430 | 0 | En.print(OS); |
431 | 0 | return OS; |
432 | 0 | } |
433 | | |
434 | | } // end namespace llvm |
435 | | |
436 | | #endif // LLVM_CODEGEN_MACHINETRACEMETRICS_H |