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
37/// printing the most "critical" sequence of dependent instructions according to
38/// the 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
66/// transitions and backend pressure increase events. Edges are internally
67/// ranked based on their "criticality". A dependency is considered to be
68/// critical if it takes a long time to execute, and if it contributes to
69/// backend pressure increases. Criticality is internally measured in terms of
70/// cycles; it is computed for every edge in the graph as a function of the edge
71/// latency and the number of backend pressure increase cycles contributed by
72/// that edge.
73///
74/// At the end of simulation, costs are propagated to nodes through the edges of
75/// the graph, and the most expensive path connecting the root-set (a
76/// set of nodes with no predecessors) to a leaf node is reported as critical
77/// sequence.
78//
79//===----------------------------------------------------------------------===//
80
81#ifndef LLVM_TOOLS_LLVM_MCA_BOTTLENECK_ANALYSIS_H
82#define LLVM_TOOLS_LLVM_MCA_BOTTLENECK_ANALYSIS_H
83
84#include "Views/InstructionView.h"
85#include "llvm/ADT/DenseMap.h"
86#include "llvm/ADT/SmallVector.h"
87#include "llvm/MC/MCInstPrinter.h"
88#include "llvm/MC/MCSchedule.h"
89#include "llvm/MC/MCSubtargetInfo.h"
90#include "llvm/Support/FormattedStream.h"
91#include "llvm/Support/raw_ostream.h"
92
93namespace llvm {
94namespace mca {
95
96class PressureTracker {
97 const MCSchedModel &SM;
98
99 // Resource pressure distribution. There is an element for every processor
100 // resource declared by the scheduling model. Quantities are number of cycles.
101 SmallVector<unsigned, 4> ResourcePressureDistribution;
102
103 // Each processor resource is associated with a so-called processor resource
104 // mask. This vector allows to correlate processor resource IDs with processor
105 // resource masks. There is exactly one element per each processor resource
106 // declared by the scheduling model.
107 SmallVector<uint64_t, 4> ProcResID2Mask;
108
109 // Maps processor resource state indices (returned by calls to
110 // `getResourceStateIndex(Mask)` to processor resource identifiers.
111 SmallVector<unsigned, 4> ResIdx2ProcResID;
112
113 // Maps Processor Resource identifiers to ResourceUsers indices.
114 SmallVector<unsigned, 4> ProcResID2ResourceUsersIndex;
115
116 // Identifies the last user of a processor resource unit.
117 // This vector is updated on every instruction issued event.
118 // There is one entry for every processor resource unit declared by the
119 // processor model. An all_ones value is treated like an invalid instruction
120 // identifier.
121 using User = std::pair<unsigned, unsigned>;
122 SmallVector<User, 4> ResourceUsers;
123
124 struct InstructionPressureInfo {
125 unsigned RegisterPressureCycles;
126 unsigned MemoryPressureCycles;
127 unsigned ResourcePressureCycles;
128 };
129 DenseMap<unsigned, InstructionPressureInfo> IPI;
130
131 void updateResourcePressureDistribution(uint64_t CumulativeMask);
132
133 User getResourceUser(unsigned ProcResID, unsigned UnitID) const {
134 unsigned Index = ProcResID2ResourceUsersIndex[ProcResID];
135 return ResourceUsers[Index + UnitID];
136 }
137
138public:
139 PressureTracker(const MCSchedModel &Model);
140
141 ArrayRef<unsigned> getResourcePressureDistribution() const {
142 return ResourcePressureDistribution;
143 }
144
145 void getResourceUsers(uint64_t ResourceMask,
146 SmallVectorImpl<User> &Users) const;
147
148 unsigned getRegisterPressureCycles(unsigned IID) const {
149 assert(IPI.contains(IID) && "Instruction is not tracked!");
150 const InstructionPressureInfo &Info = IPI.find(Val: IID)->second;
151 return Info.RegisterPressureCycles;
152 }
153
154 unsigned getMemoryPressureCycles(unsigned IID) const {
155 assert(IPI.contains(IID) && "Instruction is not tracked!");
156 const InstructionPressureInfo &Info = IPI.find(Val: IID)->second;
157 return Info.MemoryPressureCycles;
158 }
159
160 unsigned getResourcePressureCycles(unsigned IID) const {
161 assert(IPI.contains(IID) && "Instruction is not tracked!");
162 const InstructionPressureInfo &Info = IPI.find(Val: IID)->second;
163 return Info.ResourcePressureCycles;
164 }
165
166 const char *resolveResourceName(uint64_t ResourceMask) const {
167 unsigned Index = getResourceStateIndex(Mask: ResourceMask);
168 unsigned ProcResID = ResIdx2ProcResID[Index];
169 const MCProcResourceDesc &PRDesc = *SM.getProcResource(ProcResourceIdx: ProcResID);
170 return PRDesc.Name;
171 }
172
173 void onInstructionDispatched(unsigned IID);
174 void onInstructionExecuted(unsigned IID);
175
176 void handlePressureEvent(const HWPressureEvent &Event);
177 void handleInstructionIssuedEvent(const HWInstructionIssuedEvent &Event);
178};
179
180// A dependency edge.
181struct DependencyEdge {
182 enum DependencyType { DT_INVALID, DT_REGISTER, DT_MEMORY, DT_RESOURCE };
183
184 // Dependency edge descriptor.
185 //
186 // It specifies the dependency type, as well as the edge cost in cycles.
187 struct Dependency {
188 DependencyType Type;
189 uint64_t ResourceOrRegID;
190 uint64_t Cost;
191 };
192 Dependency Dep;
193
194 unsigned FromIID;
195 unsigned ToIID;
196
197 // Used by the bottleneck analysis to compute the interference
198 // probability for processor resources.
199 unsigned Frequency;
200};
201
202// A dependency graph used by the bottleneck analysis to describe data
203// dependencies and processor resource interferences between instructions.
204//
205// There is a node (an instance of struct DGNode) for every instruction in the
206// input assembly sequence. Edges of the graph represent dependencies between
207// instructions.
208//
209// Each edge of the graph is associated with a cost value which is used
210// internally to rank dependency based on their impact on the runtime
211// performance (see field DependencyEdge::Dependency::Cost). In general, the
212// higher the cost of an edge, the higher the impact on performance.
213//
214// The cost of a dependency is a function of both the latency and the number of
215// cycles where the dependency has been seen as critical (i.e. contributing to
216// back-pressure increases).
217//
218// Loop carried dependencies are carefully expanded by the bottleneck analysis
219// to guarantee that the graph stays acyclic. To this end, extra nodes are
220// pre-allocated at construction time to describe instructions from "past and
221// future" iterations. The graph is kept acyclic mainly because it simplifies
222// the complexity of the algorithm that computes the critical sequence.
223class DependencyGraph {
224 struct DGNode {
225 unsigned NumPredecessors;
226 unsigned NumVisitedPredecessors;
227 uint64_t Cost;
228 unsigned Depth;
229
230 DependencyEdge CriticalPredecessor;
231 // Measurements show that more than 90% of nodes have no outgoing edges. To
232 // minimize memory consumption we use SmallVector with zero inline elements
233 // that is preferred version of std::vector.
234 SmallVector<DependencyEdge, 0> OutgoingEdges;
235 };
236 SmallVector<DGNode, 16> Nodes;
237
238 DependencyGraph(const DependencyGraph &) = delete;
239 DependencyGraph &operator=(const DependencyGraph &) = delete;
240
241 void addDependency(unsigned From, unsigned To,
242 DependencyEdge::Dependency &&DE);
243
244 void pruneEdges(unsigned Iterations);
245 void initializeRootSet(SmallVectorImpl<unsigned> &RootSet) const;
246 void propagateThroughEdges(SmallVectorImpl<unsigned> &RootSet,
247 unsigned Iterations);
248
249#ifndef NDEBUG
250 void dumpDependencyEdge(raw_ostream &OS, const DependencyEdge &DE,
251 MCInstPrinter &MCIP) const;
252#endif
253
254public:
255 DependencyGraph(unsigned Size) : Nodes(Size) {}
256
257 void addRegisterDep(unsigned From, unsigned To, unsigned RegID,
258 unsigned Cost) {
259 addDependency(From, To, DE: {.Type: DependencyEdge::DT_REGISTER, .ResourceOrRegID: RegID, .Cost: Cost});
260 }
261
262 void addMemoryDep(unsigned From, unsigned To, unsigned Cost) {
263 addDependency(From, To, DE: {.Type: DependencyEdge::DT_MEMORY, /* unused */ .ResourceOrRegID: 0, .Cost: Cost});
264 }
265
266 void addResourceDep(unsigned From, unsigned To, uint64_t Mask,
267 unsigned Cost) {
268 addDependency(From, To, DE: {.Type: DependencyEdge::DT_RESOURCE, .ResourceOrRegID: Mask, .Cost: Cost});
269 }
270
271 // Called by the bottleneck analysis at the end of simulation to propagate
272 // costs through the edges of the graph, and compute a critical path.
273 void finalizeGraph(unsigned Iterations) {
274 SmallVector<unsigned, 16> RootSet;
275 pruneEdges(Iterations);
276 initializeRootSet(RootSet);
277 propagateThroughEdges(RootSet, Iterations);
278 }
279
280 // Returns a sequence of edges representing the critical sequence based on the
281 // simulated run. It assumes that the graph has already been finalized (i.e.
282 // method `finalizeGraph()` has already been called on this graph).
283 void getCriticalSequence(SmallVectorImpl<const DependencyEdge *> &Seq) const;
284
285#ifndef NDEBUG
286 void dump(raw_ostream &OS, MCInstPrinter &MCIP) const;
287#endif
288};
289
290/// A view that collects and prints a few performance numbers.
291class BottleneckAnalysis : public InstructionView {
292 PressureTracker Tracker;
293 DependencyGraph DG;
294
295 unsigned Iterations;
296 unsigned TotalCycles;
297
298 bool PressureIncreasedBecauseOfResources;
299 bool PressureIncreasedBecauseOfRegisterDependencies;
300 bool PressureIncreasedBecauseOfMemoryDependencies;
301 // True if throughput was affected by dispatch stalls.
302 bool SeenStallCycles;
303
304 struct BackPressureInfo {
305 // Cycles where backpressure increased.
306 unsigned PressureIncreaseCycles;
307 // Cycles where backpressure increased because of pipeline pressure.
308 unsigned ResourcePressureCycles;
309 // Cycles where backpressure increased because of data dependencies.
310 unsigned DataDependencyCycles;
311 // Cycles where backpressure increased because of register dependencies.
312 unsigned RegisterDependencyCycles;
313 // Cycles where backpressure increased because of memory dependencies.
314 unsigned MemoryDependencyCycles;
315 };
316 BackPressureInfo BPI;
317
318 // Used to populate the dependency graph DG.
319 void addRegisterDep(unsigned From, unsigned To, unsigned RegID, unsigned Cy);
320 void addMemoryDep(unsigned From, unsigned To, unsigned Cy);
321 void addResourceDep(unsigned From, unsigned To, uint64_t Mask, unsigned Cy);
322
323 void printInstruction(formatted_raw_ostream &FOS, const MCInst &MCI,
324 bool UseDifferentColor = false) const;
325
326 // Prints a bottleneck message to OS.
327 void printBottleneckHints(raw_ostream &OS) const;
328 void printCriticalSequence(raw_ostream &OS) const;
329
330public:
331 BottleneckAnalysis(const MCSubtargetInfo &STI, MCInstPrinter &MCIP,
332 ArrayRef<MCInst> Sequence, unsigned Iterations);
333
334 void onCycleEnd() override;
335 void onEvent(const HWStallEvent &Event) override { SeenStallCycles = true; }
336 void onEvent(const HWPressureEvent &Event) override;
337 void onEvent(const HWInstructionEvent &Event) override;
338
339 void printView(raw_ostream &OS) const override;
340 StringRef getNameAsString() const override { return "BottleneckAnalysis"; }
341 bool isSerializable() const override { return true; }
342 json::Value toJSON() const override;
343
344#ifndef NDEBUG
345 void dump(raw_ostream &OS, MCInstPrinter &MCIP) const { DG.dump(OS, MCIP); }
346#endif
347};
348
349} // namespace mca
350} // namespace llvm
351
352#endif
353