xref: /freebsd/contrib/llvm-project/llvm/tools/llvm-mca/Views/BottleneckAnalysis.h (revision ae7e8a02e6e93455e026036132c4d053b2c12ad9)
1 //===--------------------- BottleneckAnalysis.h -----------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 ///
10 /// This file implements the bottleneck analysis view.
11 ///
12 /// This view internally observes backend pressure increase events in order to
13 /// identify problematic data dependencies and processor resource interferences.
14 ///
15 /// Example of bottleneck analysis report for a dot-product on X86 btver2:
16 ///
17 /// Cycles with backend pressure increase [ 40.76% ]
18 /// Throughput Bottlenecks:
19 ///   Resource Pressure       [ 39.34% ]
20 ///   - JFPA  [ 39.34% ]
21 ///   - JFPU0  [ 39.34% ]
22 ///   Data Dependencies:      [ 1.42% ]
23 ///   - Register Dependencies [ 1.42% ]
24 ///   - Memory Dependencies   [ 0.00% ]
25 ///
26 /// According to the example, backend pressure increased during the 40.76% of
27 /// the simulated cycles.  In particular, the major cause of backend pressure
28 /// increases was the contention on floating point adder JFPA accessible from
29 /// pipeline resource JFPU0.
30 ///
31 /// At the end of each cycle, if pressure on the simulated out-of-order buffers
32 /// has increased, a backend pressure event is reported.
33 /// In particular, this occurs when there is a delta between the number of uOps
34 /// dispatched and the number of uOps issued to the underlying pipelines.
35 ///
36 /// The bottleneck analysis view is also responsible for identifying and printing
37 /// the most "critical" sequence of dependent instructions according to the
38 /// simulated run.
39 ///
40 /// Below is the critical sequence computed for the dot-product example on
41 /// btver2:
42 ///
43 ///              Instruction                     Dependency Information
44 /// +----< 2.    vhaddps %xmm3, %xmm3, %xmm4
45 /// |
46 /// |    < loop carried >
47 /// |
48 /// |      0.    vmulps	 %xmm0, %xmm0, %xmm2
49 /// +----> 1.    vhaddps %xmm2, %xmm2, %xmm3     ## RESOURCE interference:  JFPA [ probability: 73% ]
50 /// +----> 2.    vhaddps %xmm3, %xmm3, %xmm4     ## REGISTER dependency:  %xmm3
51 /// |
52 /// |    < loop carried >
53 /// |
54 /// +----> 1.    vhaddps %xmm2, %xmm2, %xmm3     ## RESOURCE interference:  JFPA [ probability: 73% ]
55 ///
56 ///
57 /// The algorithm that computes the critical sequence is very similar to a
58 /// critical path analysis.
59 ///
60 /// A dependency graph is used internally to track dependencies between nodes.
61 /// Nodes of the graph represent instructions from the input assembly sequence,
62 /// and edges of the graph represent data dependencies or processor resource
63 /// interferences.
64 ///
65 /// Edges are dynamically 'discovered' by observing instruction state transitions
66 /// and backend pressure increase events. Edges are internally ranked based on
67 /// their "criticality". A dependency is considered to be critical if it takes a
68 /// long time to execute, and if it contributes to backend pressure increases.
69 /// Criticality is internally measured in terms of cycles; it is computed for
70 /// every edge in the graph as a function of the edge latency and the number of
71 /// backend pressure increase cycles contributed by that edge.
72 ///
73 /// At the end of simulation, costs are propagated to nodes through the edges of
74 /// the graph, and the most expensive path connecting the root-set (a
75 /// set of nodes with no predecessors) to a leaf node is reported as critical
76 /// sequence.
77 //
78 //===----------------------------------------------------------------------===//
79 
80 #ifndef LLVM_TOOLS_LLVM_MCA_BOTTLENECK_ANALYSIS_H
81 #define LLVM_TOOLS_LLVM_MCA_BOTTLENECK_ANALYSIS_H
82 
83 #include "Views/InstructionView.h"
84 #include "llvm/ADT/DenseMap.h"
85 #include "llvm/ADT/SmallVector.h"
86 #include "llvm/MC/MCInstPrinter.h"
87 #include "llvm/MC/MCSchedule.h"
88 #include "llvm/MC/MCSubtargetInfo.h"
89 #include "llvm/Support/FormattedStream.h"
90 #include "llvm/Support/raw_ostream.h"
91 
92 namespace llvm {
93 namespace mca {
94 
95 class PressureTracker {
96   const MCSchedModel &SM;
97 
98   // Resource pressure distribution. There is an element for every processor
99   // resource declared by the scheduling model. Quantities are number of cycles.
100   SmallVector<unsigned, 4> ResourcePressureDistribution;
101 
102   // Each processor resource is associated with a so-called processor resource
103   // mask. This vector allows to correlate processor resource IDs with processor
104   // resource masks. There is exactly one element per each processor resource
105   // declared by the scheduling model.
106   SmallVector<uint64_t, 4> ProcResID2Mask;
107 
108   // Maps processor resource state indices (returned by calls to
109   // `getResourceStateIndex(Mask)` to processor resource identifiers.
110   SmallVector<unsigned, 4> ResIdx2ProcResID;
111 
112   // Maps Processor Resource identifiers to ResourceUsers indices.
113   SmallVector<unsigned, 4> ProcResID2ResourceUsersIndex;
114 
115   // Identifies the last user of a processor resource unit.
116   // This vector is updated on every instruction issued event.
117   // There is one entry for every processor resource unit declared by the
118   // processor model. An all_ones value is treated like an invalid instruction
119   // identifier.
120   using User = std::pair<unsigned, unsigned>;
121   SmallVector<User, 4> ResourceUsers;
122 
123   struct InstructionPressureInfo {
124     unsigned RegisterPressureCycles;
125     unsigned MemoryPressureCycles;
126     unsigned ResourcePressureCycles;
127   };
128   DenseMap<unsigned, InstructionPressureInfo> IPI;
129 
130   void updateResourcePressureDistribution(uint64_t CumulativeMask);
131 
132   User getResourceUser(unsigned ProcResID, unsigned UnitID) const {
133     unsigned Index = ProcResID2ResourceUsersIndex[ProcResID];
134     return ResourceUsers[Index + UnitID];
135   }
136 
137 public:
138   PressureTracker(const MCSchedModel &Model);
139 
140   ArrayRef<unsigned> getResourcePressureDistribution() const {
141     return ResourcePressureDistribution;
142   }
143 
144   void getResourceUsers(uint64_t ResourceMask,
145                         SmallVectorImpl<User> &Users) const;
146 
147   unsigned getRegisterPressureCycles(unsigned IID) const {
148     assert(IPI.find(IID) != IPI.end() && "Instruction is not tracked!");
149     const InstructionPressureInfo &Info = IPI.find(IID)->second;
150     return Info.RegisterPressureCycles;
151   }
152 
153   unsigned getMemoryPressureCycles(unsigned IID) const {
154     assert(IPI.find(IID) != IPI.end() && "Instruction is not tracked!");
155     const InstructionPressureInfo &Info = IPI.find(IID)->second;
156     return Info.MemoryPressureCycles;
157   }
158 
159   unsigned getResourcePressureCycles(unsigned IID) const {
160     assert(IPI.find(IID) != IPI.end() && "Instruction is not tracked!");
161     const InstructionPressureInfo &Info = IPI.find(IID)->second;
162     return Info.ResourcePressureCycles;
163   }
164 
165   const char *resolveResourceName(uint64_t ResourceMask) const {
166     unsigned Index = getResourceStateIndex(ResourceMask);
167     unsigned ProcResID = ResIdx2ProcResID[Index];
168     const MCProcResourceDesc &PRDesc = *SM.getProcResource(ProcResID);
169     return PRDesc.Name;
170   }
171 
172   void onInstructionDispatched(unsigned IID);
173   void onInstructionExecuted(unsigned IID);
174 
175   void handlePressureEvent(const HWPressureEvent &Event);
176   void handleInstructionIssuedEvent(const HWInstructionIssuedEvent &Event);
177 };
178 
179 // A dependency edge.
180 struct DependencyEdge {
181   enum DependencyType { DT_INVALID, DT_REGISTER, DT_MEMORY, DT_RESOURCE };
182 
183   // Dependency edge descriptor.
184   //
185   // It specifies the dependency type, as well as the edge cost in cycles.
186   struct Dependency {
187     DependencyType Type;
188     uint64_t ResourceOrRegID;
189     uint64_t Cost;
190   };
191   Dependency Dep;
192 
193   unsigned FromIID;
194   unsigned ToIID;
195 
196   // Used by the bottleneck analysis to compute the interference
197   // probability for processor resources.
198   unsigned Frequency;
199 };
200 
201 // A dependency graph used by the bottleneck analysis to describe data
202 // dependencies and processor resource interferences between instructions.
203 //
204 // There is a node (an instance of struct DGNode) for every instruction in the
205 // input assembly sequence. Edges of the graph represent dependencies between
206 // instructions.
207 //
208 // Each edge of the graph is associated with a cost value which is used
209 // internally to rank dependency based on their impact on the runtime
210 // performance (see field DependencyEdge::Dependency::Cost). In general, the
211 // higher the cost of an edge, the higher the impact on performance.
212 //
213 // The cost of a dependency is a function of both the latency and the number of
214 // cycles where the dependency has been seen as critical (i.e. contributing to
215 // back-pressure increases).
216 //
217 // Loop carried dependencies are carefully expanded by the bottleneck analysis
218 // to guarantee that the graph stays acyclic. To this end, extra nodes are
219 // pre-allocated at construction time to describe instructions from "past and
220 // future" iterations. The graph is kept acyclic mainly because it simplifies the
221 // complexity of the algorithm that computes the critical sequence.
222 class DependencyGraph {
223   struct DGNode {
224     unsigned NumPredecessors;
225     unsigned NumVisitedPredecessors;
226     uint64_t Cost;
227     unsigned Depth;
228 
229     DependencyEdge CriticalPredecessor;
230     SmallVector<DependencyEdge, 8> OutgoingEdges;
231   };
232   SmallVector<DGNode, 16> Nodes;
233 
234   DependencyGraph(const DependencyGraph &) = delete;
235   DependencyGraph &operator=(const DependencyGraph &) = delete;
236 
237   void addDependency(unsigned From, unsigned To,
238                      DependencyEdge::Dependency &&DE);
239 
240   void pruneEdges(unsigned Iterations);
241   void initializeRootSet(SmallVectorImpl<unsigned> &RootSet) const;
242   void propagateThroughEdges(SmallVectorImpl<unsigned> &RootSet, unsigned Iterations);
243 
244 #ifndef NDEBUG
245   void dumpDependencyEdge(raw_ostream &OS, const DependencyEdge &DE,
246                           MCInstPrinter &MCIP) const;
247 #endif
248 
249 public:
250   DependencyGraph(unsigned Size) : Nodes(Size) {}
251 
252   void addRegisterDep(unsigned From, unsigned To, unsigned RegID,
253                       unsigned Cost) {
254     addDependency(From, To, {DependencyEdge::DT_REGISTER, RegID, Cost});
255   }
256 
257   void addMemoryDep(unsigned From, unsigned To, unsigned Cost) {
258     addDependency(From, To, {DependencyEdge::DT_MEMORY, /* unused */ 0, Cost});
259   }
260 
261   void addResourceDep(unsigned From, unsigned To, uint64_t Mask,
262                       unsigned Cost) {
263     addDependency(From, To, {DependencyEdge::DT_RESOURCE, Mask, Cost});
264   }
265 
266   // Called by the bottleneck analysis at the end of simulation to propagate
267   // costs through the edges of the graph, and compute a critical path.
268   void finalizeGraph(unsigned Iterations) {
269     SmallVector<unsigned, 16> RootSet;
270     pruneEdges(Iterations);
271     initializeRootSet(RootSet);
272     propagateThroughEdges(RootSet, Iterations);
273   }
274 
275   // Returns a sequence of edges representing the critical sequence based on the
276   // simulated run. It assumes that the graph has already been finalized (i.e.
277   // method `finalizeGraph()` has already been called on this graph).
278   void getCriticalSequence(SmallVectorImpl<const DependencyEdge *> &Seq) const;
279 
280 #ifndef NDEBUG
281   void dump(raw_ostream &OS, MCInstPrinter &MCIP) const;
282 #endif
283 };
284 
285 /// A view that collects and prints a few performance numbers.
286 class BottleneckAnalysis : public InstructionView {
287   PressureTracker Tracker;
288   DependencyGraph DG;
289 
290   unsigned Iterations;
291   unsigned TotalCycles;
292 
293   bool PressureIncreasedBecauseOfResources;
294   bool PressureIncreasedBecauseOfRegisterDependencies;
295   bool PressureIncreasedBecauseOfMemoryDependencies;
296   // True if throughput was affected by dispatch stalls.
297   bool SeenStallCycles;
298 
299   struct BackPressureInfo {
300     // Cycles where backpressure increased.
301     unsigned PressureIncreaseCycles;
302     // Cycles where backpressure increased because of pipeline pressure.
303     unsigned ResourcePressureCycles;
304     // Cycles where backpressure increased because of data dependencies.
305     unsigned DataDependencyCycles;
306     // Cycles where backpressure increased because of register dependencies.
307     unsigned RegisterDependencyCycles;
308     // Cycles where backpressure increased because of memory dependencies.
309     unsigned MemoryDependencyCycles;
310   };
311   BackPressureInfo BPI;
312 
313   // Used to populate the dependency graph DG.
314   void addRegisterDep(unsigned From, unsigned To, unsigned RegID, unsigned Cy);
315   void addMemoryDep(unsigned From, unsigned To, unsigned Cy);
316   void addResourceDep(unsigned From, unsigned To, uint64_t Mask, unsigned Cy);
317 
318   void printInstruction(formatted_raw_ostream &FOS, const MCInst &MCI,
319                         bool UseDifferentColor = false) const;
320 
321   // Prints a bottleneck message to OS.
322   void printBottleneckHints(raw_ostream &OS) const;
323   void printCriticalSequence(raw_ostream &OS) const;
324 
325 public:
326   BottleneckAnalysis(const MCSubtargetInfo &STI, MCInstPrinter &MCIP,
327                      ArrayRef<MCInst> Sequence, unsigned Iterations);
328 
329   void onCycleEnd() override;
330   void onEvent(const HWStallEvent &Event) override { SeenStallCycles = true; }
331   void onEvent(const HWPressureEvent &Event) override;
332   void onEvent(const HWInstructionEvent &Event) override;
333 
334   void printView(raw_ostream &OS) const override;
335   StringRef getNameAsString() const override { return "BottleneckAnalysis"; }
336   json::Value toJSON() const override { return "not implemented"; }
337 
338 #ifndef NDEBUG
339   void dump(raw_ostream &OS, MCInstPrinter &MCIP) const { DG.dump(OS, MCIP); }
340 #endif
341 };
342 
343 } // namespace mca
344 } // namespace llvm
345 
346 #endif
347