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 /// 88 /// By comparing column [2] with column [1], we get an idea about how many 89 /// cycles were spent in the scheduler's queue due to data dependencies. 90 /// 91 /// In this example, instruction 5 spent an average of ~6 cycles in the 92 /// scheduler's queue. As soon as operands became ready, the instruction 93 /// was immediately issued to the pipeline(s). 94 /// That is expected because instruction 5 cannot transition to the "ready" 95 /// state until %xmm4 is written by instruction 4. 96 /// 97 //===----------------------------------------------------------------------===// 98 99 #ifndef LLVM_TOOLS_LLVM_MCA_TIMELINEVIEW_H 100 #define LLVM_TOOLS_LLVM_MCA_TIMELINEVIEW_H 101 102 #include "Views/View.h" 103 #include "llvm/ADT/ArrayRef.h" 104 #include "llvm/MC/MCInst.h" 105 #include "llvm/MC/MCInstPrinter.h" 106 #include "llvm/MC/MCSubtargetInfo.h" 107 #include "llvm/Support/FormattedStream.h" 108 #include "llvm/Support/raw_ostream.h" 109 110 namespace llvm { 111 namespace mca { 112 113 /// This class listens to instruction state transition events 114 /// in order to construct a timeline information. 115 /// 116 /// For every instruction executed by the Pipeline, this class constructs 117 /// a TimelineViewEntry object. TimelineViewEntry objects are then used 118 /// to print the timeline information, as well as the "average wait times" 119 /// for every instruction in the input assembly sequence. 120 class TimelineView : public View { 121 const llvm::MCSubtargetInfo &STI; 122 llvm::MCInstPrinter &MCIP; 123 llvm::ArrayRef<llvm::MCInst> Source; 124 125 unsigned CurrentCycle; 126 unsigned MaxCycle; 127 unsigned LastCycle; 128 129 struct TimelineViewEntry { 130 int CycleDispatched; // A negative value is an "invalid cycle". 131 unsigned CycleReady; 132 unsigned CycleIssued; 133 unsigned CycleExecuted; 134 unsigned CycleRetired; 135 }; 136 std::vector<TimelineViewEntry> Timeline; 137 138 struct WaitTimeEntry { 139 unsigned CyclesSpentInSchedulerQueue; 140 unsigned CyclesSpentInSQWhileReady; 141 unsigned CyclesSpentAfterWBAndBeforeRetire; 142 }; 143 std::vector<WaitTimeEntry> WaitTime; 144 145 // This field is used to map instructions to buffered resources. 146 // Elements of this vector are <resourceID, BufferSizer> pairs. 147 std::vector<std::pair<unsigned, int>> UsedBuffer; 148 149 void printTimelineViewEntry(llvm::formatted_raw_ostream &OS, 150 const TimelineViewEntry &E, unsigned Iteration, 151 unsigned SourceIndex) const; 152 void printWaitTimeEntry(llvm::formatted_raw_ostream &OS, 153 const WaitTimeEntry &E, unsigned Index, 154 unsigned Executions) const; 155 156 // Display characters for the TimelineView report output. 157 struct DisplayChar { 158 static const char Dispatched = 'D'; 159 static const char Executed = 'E'; 160 static const char Retired = 'R'; 161 static const char Waiting = '='; // Instruction is waiting in the scheduler. 162 static const char Executing = 'e'; 163 static const char RetireLag = '-'; // The instruction is waiting to retire. 164 }; 165 166 public: 167 TimelineView(const llvm::MCSubtargetInfo &sti, llvm::MCInstPrinter &Printer, 168 llvm::ArrayRef<llvm::MCInst> S, unsigned Iterations, 169 unsigned Cycles); 170 171 // Event handlers. 172 void onCycleEnd() override { ++CurrentCycle; } 173 void onEvent(const HWInstructionEvent &Event) override; 174 void onReservedBuffers(const InstRef &IR, 175 llvm::ArrayRef<unsigned> Buffers) override; 176 177 // print functionalities. 178 void printTimeline(llvm::raw_ostream &OS) const; 179 void printAverageWaitTimes(llvm::raw_ostream &OS) const; 180 void printView(llvm::raw_ostream &OS) const override { 181 printTimeline(OS); 182 printAverageWaitTimes(OS); 183 } 184 }; 185 } // namespace mca 186 } // namespace llvm 187 188 #endif 189