1//===--------------------- TimelineView.cpp ---------------------*- 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 the TimelineView interface.
11///
12//===----------------------------------------------------------------------===//
13
14#include "Views/TimelineView.h"
15#include <numeric>
16
17namespace llvm {
18namespace mca {
19
20TimelineView::TimelineView(const MCSubtargetInfo &sti, MCInstPrinter &Printer,
21                           llvm::ArrayRef<llvm::MCInst> S, unsigned Iterations,
22                           unsigned Cycles)
23    : STI(sti), MCIP(Printer), Source(S), CurrentCycle(0),
24      MaxCycle(Cycles == 0 ? 80 : Cycles), LastCycle(0), WaitTime(S.size()),
25      UsedBuffer(S.size()) {
26  unsigned NumInstructions = Source.size();
27  assert(Iterations && "Invalid number of iterations specified!");
28  NumInstructions *= Iterations;
29  Timeline.resize(NumInstructions);
30  TimelineViewEntry InvalidTVEntry = {-1, 0, 0, 0, 0};
31  std::fill(Timeline.begin(), Timeline.end(), InvalidTVEntry);
32
33  WaitTimeEntry NullWTEntry = {0, 0, 0};
34  std::fill(WaitTime.begin(), WaitTime.end(), NullWTEntry);
35
36  std::pair<unsigned, int> NullUsedBufferEntry = {/* Invalid resource ID*/ 0,
37                                                  /* unknown buffer size */ -1};
38  std::fill(UsedBuffer.begin(), UsedBuffer.end(), NullUsedBufferEntry);
39}
40
41void TimelineView::onReservedBuffers(const InstRef &IR,
42                                     ArrayRef<unsigned> Buffers) {
43  if (IR.getSourceIndex() >= Source.size())
44    return;
45
46  const MCSchedModel &SM = STI.getSchedModel();
47  std::pair<unsigned, int> BufferInfo = {0, -1};
48  for (const unsigned Buffer : Buffers) {
49    const MCProcResourceDesc &MCDesc = *SM.getProcResource(Buffer);
50    if (!BufferInfo.first || BufferInfo.second > MCDesc.BufferSize) {
51      BufferInfo.first = Buffer;
52      BufferInfo.second = MCDesc.BufferSize;
53    }
54  }
55
56  UsedBuffer[IR.getSourceIndex()] = BufferInfo;
57}
58
59void TimelineView::onEvent(const HWInstructionEvent &Event) {
60  const unsigned Index = Event.IR.getSourceIndex();
61  if (Index >= Timeline.size())
62    return;
63
64  switch (Event.Type) {
65  case HWInstructionEvent::Retired: {
66    TimelineViewEntry &TVEntry = Timeline[Index];
67    if (CurrentCycle < MaxCycle)
68      TVEntry.CycleRetired = CurrentCycle;
69
70    // Update the WaitTime entry which corresponds to this Index.
71    assert(TVEntry.CycleDispatched >= 0 && "Invalid TVEntry found!");
72    unsigned CycleDispatched = static_cast<unsigned>(TVEntry.CycleDispatched);
73    WaitTimeEntry &WTEntry = WaitTime[Index % Source.size()];
74    WTEntry.CyclesSpentInSchedulerQueue +=
75        TVEntry.CycleIssued - CycleDispatched;
76    assert(CycleDispatched <= TVEntry.CycleReady &&
77           "Instruction cannot be ready if it hasn't been dispatched yet!");
78    WTEntry.CyclesSpentInSQWhileReady +=
79        TVEntry.CycleIssued - TVEntry.CycleReady;
80    WTEntry.CyclesSpentAfterWBAndBeforeRetire +=
81        (CurrentCycle - 1) - TVEntry.CycleExecuted;
82    break;
83  }
84  case HWInstructionEvent::Ready:
85    Timeline[Index].CycleReady = CurrentCycle;
86    break;
87  case HWInstructionEvent::Issued:
88    Timeline[Index].CycleIssued = CurrentCycle;
89    break;
90  case HWInstructionEvent::Executed:
91    Timeline[Index].CycleExecuted = CurrentCycle;
92    break;
93  case HWInstructionEvent::Dispatched:
94    // There may be multiple dispatch events. Microcoded instructions that are
95    // expanded into multiple uOps may require multiple dispatch cycles. Here,
96    // we want to capture the first dispatch cycle.
97    if (Timeline[Index].CycleDispatched == -1)
98      Timeline[Index].CycleDispatched = static_cast<int>(CurrentCycle);
99    break;
100  default:
101    return;
102  }
103  if (CurrentCycle < MaxCycle)
104    LastCycle = std::max(LastCycle, CurrentCycle);
105}
106
107static raw_ostream::Colors chooseColor(unsigned CumulativeCycles,
108                                       unsigned Executions, int BufferSize) {
109  if (CumulativeCycles && BufferSize < 0)
110    return raw_ostream::MAGENTA;
111  unsigned Size = static_cast<unsigned>(BufferSize);
112  if (CumulativeCycles >= Size * Executions)
113    return raw_ostream::RED;
114  if ((CumulativeCycles * 2) >= Size * Executions)
115    return raw_ostream::YELLOW;
116  return raw_ostream::SAVEDCOLOR;
117}
118
119static void tryChangeColor(raw_ostream &OS, unsigned Cycles,
120                           unsigned Executions, int BufferSize) {
121  if (!OS.has_colors())
122    return;
123
124  raw_ostream::Colors Color = chooseColor(Cycles, Executions, BufferSize);
125  if (Color == raw_ostream::SAVEDCOLOR) {
126    OS.resetColor();
127    return;
128  }
129  OS.changeColor(Color, /* bold */ true, /* BG */ false);
130}
131
132void TimelineView::printWaitTimeEntry(formatted_raw_ostream &OS,
133                                      const WaitTimeEntry &Entry,
134                                      unsigned SourceIndex,
135                                      unsigned Executions) const {
136  bool PrintingTotals = SourceIndex == Source.size();
137  unsigned CumulativeExecutions = PrintingTotals ? Timeline.size() : Executions;
138
139  if (!PrintingTotals)
140    OS << SourceIndex << '.';
141
142  OS.PadToColumn(7);
143
144  double AverageTime1, AverageTime2, AverageTime3;
145  AverageTime1 =
146      (double)Entry.CyclesSpentInSchedulerQueue / CumulativeExecutions;
147  AverageTime2 = (double)Entry.CyclesSpentInSQWhileReady / CumulativeExecutions;
148  AverageTime3 =
149      (double)Entry.CyclesSpentAfterWBAndBeforeRetire / CumulativeExecutions;
150
151  OS << Executions;
152  OS.PadToColumn(13);
153
154  int BufferSize = PrintingTotals ? 0 : UsedBuffer[SourceIndex].second;
155  if (!PrintingTotals)
156    tryChangeColor(OS, Entry.CyclesSpentInSchedulerQueue, CumulativeExecutions,
157                   BufferSize);
158  OS << format("%.1f", floor((AverageTime1 * 10) + 0.5) / 10);
159  OS.PadToColumn(20);
160  if (!PrintingTotals)
161    tryChangeColor(OS, Entry.CyclesSpentInSQWhileReady, CumulativeExecutions,
162                   BufferSize);
163  OS << format("%.1f", floor((AverageTime2 * 10) + 0.5) / 10);
164  OS.PadToColumn(27);
165  if (!PrintingTotals)
166    tryChangeColor(OS, Entry.CyclesSpentAfterWBAndBeforeRetire,
167                   CumulativeExecutions, STI.getSchedModel().MicroOpBufferSize);
168  OS << format("%.1f", floor((AverageTime3 * 10) + 0.5) / 10);
169
170  if (OS.has_colors())
171    OS.resetColor();
172  OS.PadToColumn(34);
173}
174
175void TimelineView::printAverageWaitTimes(raw_ostream &OS) const {
176  std::string Header =
177      "\n\nAverage Wait times (based on the timeline view):\n"
178      "[0]: Executions\n"
179      "[1]: Average time spent waiting in a scheduler's queue\n"
180      "[2]: Average time spent waiting in a scheduler's queue while ready\n"
181      "[3]: Average time elapsed from WB until retire stage\n\n"
182      "      [0]    [1]    [2]    [3]\n";
183  OS << Header;
184
185  // Use a different string stream for printing instructions.
186  std::string Instruction;
187  raw_string_ostream InstrStream(Instruction);
188
189  formatted_raw_ostream FOS(OS);
190  unsigned Executions = Timeline.size() / Source.size();
191  unsigned IID = 0;
192  for (const MCInst &Inst : Source) {
193    printWaitTimeEntry(FOS, WaitTime[IID], IID, Executions);
194    // Append the instruction info at the end of the line.
195    MCIP.printInst(&Inst, 0, "", STI, InstrStream);
196    InstrStream.flush();
197
198    // Consume any tabs or spaces at the beginning of the string.
199    StringRef Str(Instruction);
200    Str = Str.ltrim();
201    FOS << "   " << Str << '\n';
202    FOS.flush();
203    Instruction = "";
204
205    ++IID;
206  }
207
208  // If the timeline contains more than one instruction,
209  // let's also print global averages.
210  if (Source.size() != 1) {
211    WaitTimeEntry TotalWaitTime = std::accumulate(
212        WaitTime.begin(), WaitTime.end(), WaitTimeEntry{0, 0, 0},
213        [](const WaitTimeEntry &A, const WaitTimeEntry &B) {
214          return WaitTimeEntry{
215              A.CyclesSpentInSchedulerQueue + B.CyclesSpentInSchedulerQueue,
216              A.CyclesSpentInSQWhileReady + B.CyclesSpentInSQWhileReady,
217              A.CyclesSpentAfterWBAndBeforeRetire +
218                  B.CyclesSpentAfterWBAndBeforeRetire};
219        });
220    printWaitTimeEntry(FOS, TotalWaitTime, IID, Executions);
221    FOS << "   "
222        << "<total>" << '\n';
223    InstrStream.flush();
224  }
225}
226
227void TimelineView::printTimelineViewEntry(formatted_raw_ostream &OS,
228                                          const TimelineViewEntry &Entry,
229                                          unsigned Iteration,
230                                          unsigned SourceIndex) const {
231  if (Iteration == 0 && SourceIndex == 0)
232    OS << '\n';
233  OS << '[' << Iteration << ',' << SourceIndex << ']';
234  OS.PadToColumn(10);
235  assert(Entry.CycleDispatched >= 0 && "Invalid TimelineViewEntry!");
236  unsigned CycleDispatched = static_cast<unsigned>(Entry.CycleDispatched);
237  for (unsigned I = 0, E = CycleDispatched; I < E; ++I)
238    OS << ((I % 5 == 0) ? '.' : ' ');
239  OS << TimelineView::DisplayChar::Dispatched;
240  if (CycleDispatched != Entry.CycleExecuted) {
241    // Zero latency instructions have the same value for CycleDispatched,
242    // CycleIssued and CycleExecuted.
243    for (unsigned I = CycleDispatched + 1, E = Entry.CycleIssued; I < E; ++I)
244      OS << TimelineView::DisplayChar::Waiting;
245    if (Entry.CycleIssued == Entry.CycleExecuted)
246      OS << TimelineView::DisplayChar::DisplayChar::Executed;
247    else {
248      if (CycleDispatched != Entry.CycleIssued)
249        OS << TimelineView::DisplayChar::Executing;
250      for (unsigned I = Entry.CycleIssued + 1, E = Entry.CycleExecuted; I < E;
251           ++I)
252        OS << TimelineView::DisplayChar::Executing;
253      OS << TimelineView::DisplayChar::Executed;
254    }
255  }
256
257  for (unsigned I = Entry.CycleExecuted + 1, E = Entry.CycleRetired; I < E; ++I)
258    OS << TimelineView::DisplayChar::RetireLag;
259  OS << TimelineView::DisplayChar::Retired;
260
261  // Skip other columns.
262  for (unsigned I = Entry.CycleRetired + 1, E = LastCycle; I <= E; ++I)
263    OS << ((I % 5 == 0 || I == LastCycle) ? '.' : ' ');
264}
265
266static void printTimelineHeader(formatted_raw_ostream &OS, unsigned Cycles) {
267  OS << "\n\nTimeline view:\n";
268  if (Cycles >= 10) {
269    OS.PadToColumn(10);
270    for (unsigned I = 0; I <= Cycles; ++I) {
271      if (((I / 10) & 1) == 0)
272        OS << ' ';
273      else
274        OS << I % 10;
275    }
276    OS << '\n';
277  }
278
279  OS << "Index";
280  OS.PadToColumn(10);
281  for (unsigned I = 0; I <= Cycles; ++I) {
282    if (((I / 10) & 1) == 0)
283      OS << I % 10;
284    else
285      OS << ' ';
286  }
287  OS << '\n';
288}
289
290void TimelineView::printTimeline(raw_ostream &OS) const {
291  formatted_raw_ostream FOS(OS);
292  printTimelineHeader(FOS, LastCycle);
293  FOS.flush();
294
295  // Use a different string stream for the instruction.
296  std::string Instruction;
297  raw_string_ostream InstrStream(Instruction);
298
299  unsigned IID = 0;
300  const unsigned Iterations = Timeline.size() / Source.size();
301  for (unsigned Iteration = 0; Iteration < Iterations; ++Iteration) {
302    for (const MCInst &Inst : Source) {
303      const TimelineViewEntry &Entry = Timeline[IID];
304      if (Entry.CycleRetired == 0)
305        return;
306
307      unsigned SourceIndex = IID % Source.size();
308      printTimelineViewEntry(FOS, Entry, Iteration, SourceIndex);
309      // Append the instruction info at the end of the line.
310      MCIP.printInst(&Inst, 0, "", STI, InstrStream);
311      InstrStream.flush();
312
313      // Consume any tabs or spaces at the beginning of the string.
314      StringRef Str(Instruction);
315      Str = Str.ltrim();
316      FOS << "   " << Str << '\n';
317      FOS.flush();
318      Instruction = "";
319
320      ++IID;
321    }
322  }
323}
324} // namespace mca
325} // namespace llvm
326