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