353 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8/// \file9///10/// This file implements the bottleneck analysis view.11///12/// This view internally observes backend pressure increase events in order to13/// 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% of27/// the simulated cycles. In particular, the major cause of backend pressure28/// increases was the contention on floating point adder JFPA accessible from29/// pipeline resource JFPU0.30///31/// At the end of each cycle, if pressure on the simulated out-of-order buffers32/// has increased, a backend pressure event is reported.33/// In particular, this occurs when there is a delta between the number of uOps34/// dispatched and the number of uOps issued to the underlying pipelines.35///36/// The bottleneck analysis view is also responsible for identifying and37/// printing the most "critical" sequence of dependent instructions according to38/// the simulated run.39///40/// Below is the critical sequence computed for the dot-product example on41/// btver2:42///43/// Instruction Dependency Information44/// +----< 2. vhaddps %xmm3, %xmm3, %xmm445/// |46/// | < loop carried > 47/// |48/// | 0. vmulps %xmm0, %xmm0, %xmm249/// +----> 1. vhaddps %xmm2, %xmm2, %xmm3 ## RESOURCE interference: JFPA [ probability: 73% ]50/// +----> 2. vhaddps %xmm3, %xmm3, %xmm4 ## REGISTER dependency: %xmm351/// |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 a58/// 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 resource63/// interferences.64///65/// Edges are dynamically 'discovered' by observing instruction state66/// transitions and backend pressure increase events. Edges are internally67/// ranked based on their "criticality". A dependency is considered to be68/// critical if it takes a long time to execute, and if it contributes to69/// backend pressure increases. Criticality is internally measured in terms of70/// cycles; it is computed for every edge in the graph as a function of the edge71/// latency and the number of backend pressure increase cycles contributed by72/// that edge.73///74/// At the end of simulation, costs are propagated to nodes through the edges of75/// the graph, and the most expensive path connecting the root-set (a76/// set of nodes with no predecessors) to a leaf node is reported as critical77/// sequence.78//79//===----------------------------------------------------------------------===//80 81#ifndef LLVM_TOOLS_LLVM_MCA_BOTTLENECK_ANALYSIS_H82#define LLVM_TOOLS_LLVM_MCA_BOTTLENECK_ANALYSIS_H83 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 processor100 // 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 resource104 // mask. This vector allows to correlate processor resource IDs with processor105 // resource masks. There is exactly one element per each processor resource106 // declared by the scheduling model.107 SmallVector<uint64_t, 4> ProcResID2Mask;108 109 // Maps processor resource state indices (returned by calls to110 // `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 the119 // processor model. An all_ones value is treated like an invalid instruction120 // 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(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(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(IID)->second;163 return Info.ResourcePressureCycles;164 }165 166 const char *resolveResourceName(uint64_t ResourceMask) const {167 unsigned Index = getResourceStateIndex(ResourceMask);168 unsigned ProcResID = ResIdx2ProcResID[Index];169 const MCProcResourceDesc &PRDesc = *SM.getProcResource(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 interference198 // probability for processor resources.199 unsigned Frequency;200};201 202// A dependency graph used by the bottleneck analysis to describe data203// dependencies and processor resource interferences between instructions.204//205// There is a node (an instance of struct DGNode) for every instruction in the206// input assembly sequence. Edges of the graph represent dependencies between207// instructions.208//209// Each edge of the graph is associated with a cost value which is used210// internally to rank dependency based on their impact on the runtime211// performance (see field DependencyEdge::Dependency::Cost). In general, the212// 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 of215// cycles where the dependency has been seen as critical (i.e. contributing to216// back-pressure increases).217//218// Loop carried dependencies are carefully expanded by the bottleneck analysis219// to guarantee that the graph stays acyclic. To this end, extra nodes are220// pre-allocated at construction time to describe instructions from "past and221// future" iterations. The graph is kept acyclic mainly because it simplifies222// 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. To232 // minimize memory consumption we use SmallVector with zero inline elements233 // 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 NDEBUG250 void dumpDependencyEdge(raw_ostream &OS, const DependencyEdge &DE,251 MCInstPrinter &MCIP) const;252#endif253 254public:255 DependencyGraph(unsigned Size) : Nodes(Size) {}256 257 void addRegisterDep(unsigned From, unsigned To, unsigned RegID,258 unsigned Cost) {259 addDependency(From, To, {DependencyEdge::DT_REGISTER, RegID, Cost});260 }261 262 void addMemoryDep(unsigned From, unsigned To, unsigned Cost) {263 addDependency(From, To, {DependencyEdge::DT_MEMORY, /* unused */ 0, Cost});264 }265 266 void addResourceDep(unsigned From, unsigned To, uint64_t Mask,267 unsigned Cost) {268 addDependency(From, To, {DependencyEdge::DT_RESOURCE, Mask, Cost});269 }270 271 // Called by the bottleneck analysis at the end of simulation to propagate272 // 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 the281 // 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 NDEBUG286 void dump(raw_ostream &OS, MCInstPrinter &MCIP) const;287#endif288};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 NDEBUG345 void dump(raw_ostream &OS, MCInstPrinter &MCIP) const { DG.dump(OS, MCIP); }346#endif347};348 349} // namespace mca350} // namespace llvm351 352#endif353