1 //===--------------------- TimelineView.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 /// \brief
9 ///
10 /// This file implements a timeline view for the llvm-mca tool.
11 ///
12 /// Class TimelineView observes events generated by the pipeline. For every
13 /// instruction executed by the pipeline, it stores information related to
14 /// state transition. It then plots that information in the form of a table
15 /// as reported by the example below:
16 ///
17 /// Timeline view:
18 ///     	          0123456
19 /// Index	0123456789
20 ///
21 /// [0,0]	DeER .    .    ..	vmovshdup  %xmm0, %xmm1
22 /// [0,1]	DeER .    .    ..	vpermilpd  $1, %xmm0, %xmm2
23 /// [0,2]	.DeER.    .    ..	vpermilps  $231, %xmm0, %xmm5
24 /// [0,3]	.DeeeER   .    ..	vaddss  %xmm1, %xmm0, %xmm3
25 /// [0,4]	. D==eeeER.    ..	vaddss  %xmm3, %xmm2, %xmm4
26 /// [0,5]	. D=====eeeER  ..	vaddss  %xmm4, %xmm5, %xmm6
27 ///
28 /// [1,0]	.  DeE------R  ..	vmovshdup  %xmm0, %xmm1
29 /// [1,1]	.  DeE------R  ..	vpermilpd  $1, %xmm0, %xmm2
30 /// [1,2]	.   DeE-----R  ..	vpermilps  $231, %xmm0, %xmm5
31 /// [1,3]	.   D=eeeE--R  ..	vaddss  %xmm1, %xmm0, %xmm3
32 /// [1,4]	.    D===eeeER ..	vaddss  %xmm3, %xmm2, %xmm4
33 /// [1,5]	.    D======eeeER	vaddss  %xmm4, %xmm5, %xmm6
34 ///
35 /// There is an entry for every instruction in the input assembly sequence.
36 /// The first field is a pair of numbers obtained from the instruction index.
37 /// The first element of the pair is the iteration index, while the second
38 /// element of the pair is a sequence number (i.e. a position in the assembly
39 /// sequence).
40 /// The second field of the table is the actual timeline information; each
41 /// column is the information related to a specific cycle of execution.
42 /// The timeline of an instruction is described by a sequence of character
43 /// where each character represents the instruction state at a specific cycle.
44 ///
45 /// Possible instruction states are:
46 ///  D: Instruction Dispatched
47 ///  e: Instruction Executing
48 ///  E: Instruction Executed (write-back stage)
49 ///  R: Instruction retired
50 ///  =: Instruction waiting in the Scheduler's queue
51 ///  -: Instruction executed, waiting to retire in order.
52 ///
53 /// dots ('.') and empty spaces are cycles where the instruction is not
54 /// in-flight.
55 ///
56 /// The last column is the assembly instruction associated to the entry.
57 ///
58 /// Based on the timeline view information from the example, instruction 0
59 /// at iteration 0 was dispatched at cycle 0, and was retired at cycle 3.
60 /// Instruction [0,1] was also dispatched at cycle 0, and it retired at
61 /// the same cycle than instruction [0,0].
62 /// Instruction [0,4] has been dispatched at cycle 2. However, it had to
63 /// wait for two cycles before being issued. That is because operands
64 /// became ready only at cycle 5.
65 ///
66 /// This view helps further understanding bottlenecks and the impact of
67 /// resource pressure on the code.
68 ///
69 /// To better understand why instructions had to wait for multiple cycles in
70 /// the scheduler's queue, class TimelineView also reports extra timing info
71 /// in another table named "Average Wait times" (see example below).
72 ///
73 ///
74 /// Average Wait times (based on the timeline view):
75 /// [0]: Executions
76 /// [1]: Average time spent waiting in a scheduler's queue
77 /// [2]: Average time spent waiting in a scheduler's queue while ready
78 /// [3]: Average time elapsed from WB until retire stage
79 ///
80 ///	[0]	[1]	[2]	[3]
81 /// 0.	 2	1.0	1.0	3.0	vmovshdup  %xmm0, %xmm1
82 /// 1.	 2	1.0	1.0	3.0	vpermilpd  $1, %xmm0, %xmm2
83 /// 2.	 2	1.0	1.0	2.5	vpermilps  $231, %xmm0, %xmm5
84 /// 3.	 2	1.5	0.5	1.0	vaddss  %xmm1, %xmm0, %xmm3
85 /// 4.	 2	3.5	0.0	0.0	vaddss  %xmm3, %xmm2, %xmm4
86 /// 5.	 2	6.5	0.0	0.0	vaddss  %xmm4, %xmm5, %xmm6
87 ///      2	2.4	0.6	1.6     <total>
88 ///
89 /// By comparing column [2] with column [1], we get an idea about how many
90 /// cycles were spent in the scheduler's queue due to data dependencies.
91 ///
92 /// In this example, instruction 5 spent an average of ~6 cycles in the
93 /// scheduler's queue. As soon as operands became ready, the instruction
94 /// was immediately issued to the pipeline(s).
95 /// That is expected because instruction 5 cannot transition to the "ready"
96 /// state until %xmm4 is written by instruction 4.
97 ///
98 //===----------------------------------------------------------------------===//
99 
100 #ifndef LLVM_TOOLS_LLVM_MCA_TIMELINEVIEW_H
101 #define LLVM_TOOLS_LLVM_MCA_TIMELINEVIEW_H
102 
103 #include "Views/InstructionView.h"
104 #include "llvm/ADT/ArrayRef.h"
105 #include "llvm/MC/MCInst.h"
106 #include "llvm/MC/MCInstPrinter.h"
107 #include "llvm/MC/MCSubtargetInfo.h"
108 #include "llvm/Support/FormattedStream.h"
109 #include "llvm/Support/JSON.h"
110 #include "llvm/Support/raw_ostream.h"
111 
112 namespace llvm {
113 namespace mca {
114 
115 /// This class listens to instruction state transition events
116 /// in order to construct a timeline information.
117 ///
118 /// For every instruction executed by the Pipeline, this class constructs
119 /// a TimelineViewEntry object. TimelineViewEntry objects are then used
120 /// to print the timeline information, as well as the "average wait times"
121 /// for every instruction in the input assembly sequence.
122 class TimelineView : public InstructionView {
123   unsigned CurrentCycle;
124   unsigned MaxCycle;
125   unsigned LastCycle;
126 
127   struct TimelineViewEntry {
128     int CycleDispatched;  // A negative value is an "invalid cycle".
129     unsigned CycleReady;
130     unsigned CycleIssued;
131     unsigned CycleExecuted;
132     unsigned CycleRetired;
133   };
134   std::vector<TimelineViewEntry> Timeline;
135 
136   struct WaitTimeEntry {
137     unsigned CyclesSpentInSchedulerQueue;
138     unsigned CyclesSpentInSQWhileReady;
139     unsigned CyclesSpentAfterWBAndBeforeRetire;
140   };
141   std::vector<WaitTimeEntry> WaitTime;
142 
143   // This field is used to map instructions to buffered resources.
144   // Elements of this vector are <resourceID, BufferSizer> pairs.
145   std::vector<std::pair<unsigned, int>> UsedBuffer;
146 
147   void printTimelineViewEntry(llvm::formatted_raw_ostream &OS,
148                               const TimelineViewEntry &E, unsigned Iteration,
149                               unsigned SourceIndex) const;
150   void printWaitTimeEntry(llvm::formatted_raw_ostream &OS,
151                           const WaitTimeEntry &E, unsigned Index,
152                           unsigned Executions) const;
153 
154   // Display characters for the TimelineView report output.
155   struct DisplayChar {
156     static const char Dispatched = 'D';
157     static const char Executed = 'E';
158     static const char Retired = 'R';
159     static const char Waiting = '='; // Instruction is waiting in the scheduler.
160     static const char Executing = 'e';
161     static const char RetireLag = '-'; // The instruction is waiting to retire.
162   };
163 
164 public:
165   TimelineView(const llvm::MCSubtargetInfo &sti, llvm::MCInstPrinter &Printer,
166                llvm::ArrayRef<llvm::MCInst> S, unsigned Iterations,
167                unsigned Cycles);
168 
169   // Event handlers.
onCycleEnd()170   void onCycleEnd() override { ++CurrentCycle; }
171   void onEvent(const HWInstructionEvent &Event) override;
172   void onReservedBuffers(const InstRef &IR,
173                          llvm::ArrayRef<unsigned> Buffers) override;
174 
175   // print functionalities.
176   void printTimeline(llvm::raw_ostream &OS) const;
177   void printAverageWaitTimes(llvm::raw_ostream &OS) const;
printView(llvm::raw_ostream & OS)178   void printView(llvm::raw_ostream &OS) const override {
179     printTimeline(OS);
180     printAverageWaitTimes(OS);
181   }
getNameAsString()182   StringRef getNameAsString() const override { return "TimelineView"; }
183   json::Value toJSON() const override;
184 };
185 } // namespace mca
186 } // namespace llvm
187 
188 #endif
189