TimelineView.h revision 360784 
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/View.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/raw_ostream.h"
110
111namespace llvm {
112namespace mca {
113
114/// This class listens to instruction state transition events
115/// in order to construct a timeline information.
116///
117/// For every instruction executed by the Pipeline, this class constructs
118/// a TimelineViewEntry object. TimelineViewEntry objects are then used
119/// to print the timeline information, as well as the "average wait times"
120/// for every instruction in the input assembly sequence.
121class TimelineView : public View {
122  const llvm::MCSubtargetInfo &STI;
123  llvm::MCInstPrinter &MCIP;
124  llvm::ArrayRef<llvm::MCInst> Source;
125
126  unsigned CurrentCycle;
127  unsigned MaxCycle;
128  unsigned LastCycle;
129
130  struct TimelineViewEntry {
131    int CycleDispatched;  // A negative value is an "invalid cycle".
132    unsigned CycleReady;
133    unsigned CycleIssued;
134    unsigned CycleExecuted;
135    unsigned CycleRetired;
136  };
137  std::vector<TimelineViewEntry> Timeline;
138
139  struct WaitTimeEntry {
140    unsigned CyclesSpentInSchedulerQueue;
141    unsigned CyclesSpentInSQWhileReady;
142    unsigned CyclesSpentAfterWBAndBeforeRetire;
143  };
144  std::vector<WaitTimeEntry> WaitTime;
145
146  // This field is used to map instructions to buffered resources.
147  // Elements of this vector are <resourceID, BufferSizer> pairs.
148  std::vector<std::pair<unsigned, int>> UsedBuffer;
149
150  void printTimelineViewEntry(llvm::formatted_raw_ostream &OS,
151                              const TimelineViewEntry &E, unsigned Iteration,
152                              unsigned SourceIndex) const;
153  void printWaitTimeEntry(llvm::formatted_raw_ostream &OS,
154                          const WaitTimeEntry &E, unsigned Index,
155                          unsigned Executions) const;
156
157  // Display characters for the TimelineView report output.
158  struct DisplayChar {
159    static const char Dispatched = 'D';
160    static const char Executed = 'E';
161    static const char Retired = 'R';
162    static const char Waiting = '='; // Instruction is waiting in the scheduler.
163    static const char Executing = 'e';
164    static const char RetireLag = '-'; // The instruction is waiting to retire.
165  };
166
167public:
168  TimelineView(const llvm::MCSubtargetInfo &sti, llvm::MCInstPrinter &Printer,
169               llvm::ArrayRef<llvm::MCInst> S, unsigned Iterations,
170               unsigned Cycles);
171
172  // Event handlers.
173  void onCycleEnd() override { ++CurrentCycle; }
174  void onEvent(const HWInstructionEvent &Event) override;
175  void onReservedBuffers(const InstRef &IR,
176                         llvm::ArrayRef<unsigned> Buffers) override;
177
178  // print functionalities.
179  void printTimeline(llvm::raw_ostream &OS) const;
180  void printAverageWaitTimes(llvm::raw_ostream &OS) const;
181  void printView(llvm::raw_ostream &OS) const override {
182    printTimeline(OS);
183    printAverageWaitTimes(OS);
184  }
185};
186} // namespace mca
187} // namespace llvm
188
189#endif
190