llvm/tools/llvm-mca/Views/TimelineView.h

   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.
 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;
 178   void printView(llvm::raw_ostream &OS) const override {
 179     printTimeline(OS);
 180     printAverageWaitTimes(OS);
 181   }
 182   StringRef getNameAsString() const override { return "TimelineView"; }
 183   json::Value toJSON() const override;
 184 };
 185 } // namespace mca
 186 } // namespace llvm
 187
 188 #endif