1 //===-- Analysis.cpp --------------------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
10 #include "BenchmarkResult.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/MC/MCAsmInfo.h"
13 #include "llvm/Support/FormatVariadic.h"
15 #include <unordered_set>
21 static const char kCsvSep
= ',';
25 enum EscapeTag
{ kEscapeCsv
, kEscapeHtml
, kEscapeHtmlString
};
27 template <EscapeTag Tag
> void writeEscaped(raw_ostream
&OS
, const StringRef S
);
29 template <> void writeEscaped
<kEscapeCsv
>(raw_ostream
&OS
, const StringRef S
) {
30 if (std::find(S
.begin(), S
.end(), kCsvSep
) == S
.end()) {
35 for (const char C
: S
) {
45 template <> void writeEscaped
<kEscapeHtml
>(raw_ostream
&OS
, const StringRef S
) {
46 for (const char C
: S
) {
59 void writeEscaped
<kEscapeHtmlString
>(raw_ostream
&OS
, const StringRef S
) {
60 for (const char C
: S
) {
70 template <EscapeTag Tag
>
72 writeClusterId(raw_ostream
&OS
,
73 const InstructionBenchmarkClustering::ClusterId
&CID
) {
75 writeEscaped
<Tag
>(OS
, "[noise]");
76 else if (CID
.isError())
77 writeEscaped
<Tag
>(OS
, "[error]");
82 template <EscapeTag Tag
>
83 static void writeMeasurementValue(raw_ostream
&OS
, const double Value
) {
84 // Given Value, if we wanted to serialize it to a string,
85 // how many base-10 digits will we need to store, max?
86 static constexpr auto MaxDigitCount
=
87 std::numeric_limits
<decltype(Value
)>::max_digits10
;
88 // Also, we will need a decimal separator.
89 static constexpr auto DecimalSeparatorLen
= 1; // '.' e.g.
90 // So how long of a string will the serialization produce, max?
91 static constexpr auto SerializationLen
= MaxDigitCount
+ DecimalSeparatorLen
;
93 // WARNING: when changing the format, also adjust the small-size estimate ^.
94 static constexpr StringLiteral SimpleFloatFormat
= StringLiteral("{0:F}");
97 OS
, formatv(SimpleFloatFormat
.data(), Value
).sstr
<SerializationLen
>());
100 template <typename EscapeTag
, EscapeTag Tag
>
101 void Analysis::writeSnippet(raw_ostream
&OS
, ArrayRef
<uint8_t> Bytes
,
102 const char *Separator
) const {
103 SmallVector
<std::string
, 3> Lines
;
104 // Parse the asm snippet and print it.
105 while (!Bytes
.empty()) {
108 if (!Disasm_
->getInstruction(MI
, MISize
, Bytes
, 0, nulls(), nulls())) {
109 writeEscaped
<Tag
>(OS
, join(Lines
, Separator
));
110 writeEscaped
<Tag
>(OS
, Separator
);
111 writeEscaped
<Tag
>(OS
, "[error decoding asm snippet]");
114 SmallString
<128> InstPrinterStr
; // FIXME: magic number.
115 raw_svector_ostream
OSS(InstPrinterStr
);
116 InstPrinter_
->printInst(&MI
, OSS
, "", *SubtargetInfo_
);
117 Bytes
= Bytes
.drop_front(MISize
);
118 Lines
.emplace_back(StringRef(InstPrinterStr
).trim());
120 writeEscaped
<Tag
>(OS
, join(Lines
, Separator
));
123 // Prints a row representing an instruction, along with scheduling info and
124 // point coordinates (measurements).
125 void Analysis::printInstructionRowCsv(const size_t PointId
,
126 raw_ostream
&OS
) const {
127 const InstructionBenchmark
&Point
= Clustering_
.getPoints()[PointId
];
128 writeClusterId
<kEscapeCsv
>(OS
, Clustering_
.getClusterIdForPoint(PointId
));
130 writeSnippet
<EscapeTag
, kEscapeCsv
>(OS
, Point
.AssembledSnippet
, "; ");
132 writeEscaped
<kEscapeCsv
>(OS
, Point
.Key
.Config
);
134 assert(!Point
.Key
.Instructions
.empty());
135 const MCInst
&MCI
= Point
.keyInstruction();
136 unsigned SchedClassId
;
137 std::tie(SchedClassId
, std::ignore
) = ResolvedSchedClass::resolveSchedClassId(
138 *SubtargetInfo_
, *InstrInfo_
, MCI
);
139 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
140 const MCSchedClassDesc
*const SCDesc
=
141 SubtargetInfo_
->getSchedModel().getSchedClassDesc(SchedClassId
);
142 writeEscaped
<kEscapeCsv
>(OS
, SCDesc
->Name
);
146 for (const auto &Measurement
: Point
.Measurements
) {
148 writeMeasurementValue
<kEscapeCsv
>(OS
, Measurement
.PerInstructionValue
);
153 Analysis::Analysis(const Target
&Target
, std::unique_ptr
<MCInstrInfo
> InstrInfo
,
154 const InstructionBenchmarkClustering
&Clustering
,
155 double AnalysisInconsistencyEpsilon
,
156 bool AnalysisDisplayUnstableOpcodes
)
157 : Clustering_(Clustering
), InstrInfo_(std::move(InstrInfo
)),
158 AnalysisInconsistencyEpsilonSquared_(AnalysisInconsistencyEpsilon
*
159 AnalysisInconsistencyEpsilon
),
160 AnalysisDisplayUnstableOpcodes_(AnalysisDisplayUnstableOpcodes
) {
161 if (Clustering
.getPoints().empty())
164 const InstructionBenchmark
&FirstPoint
= Clustering
.getPoints().front();
165 RegInfo_
.reset(Target
.createMCRegInfo(FirstPoint
.LLVMTriple
));
166 AsmInfo_
.reset(Target
.createMCAsmInfo(*RegInfo_
, FirstPoint
.LLVMTriple
));
167 SubtargetInfo_
.reset(Target
.createMCSubtargetInfo(FirstPoint
.LLVMTriple
,
168 FirstPoint
.CpuName
, ""));
169 InstPrinter_
.reset(Target
.createMCInstPrinter(
170 Triple(FirstPoint
.LLVMTriple
), 0 /*default variant*/, *AsmInfo_
,
171 *InstrInfo_
, *RegInfo_
));
173 Context_
= std::make_unique
<MCContext
>(AsmInfo_
.get(), RegInfo_
.get(),
175 Disasm_
.reset(Target
.createMCDisassembler(*SubtargetInfo_
, *Context_
));
176 assert(Disasm_
&& "cannot create MCDisassembler. missing call to "
177 "InitializeXXXTargetDisassembler ?");
181 Error
Analysis::run
<Analysis::PrintClusters
>(raw_ostream
&OS
) const {
182 if (Clustering_
.getPoints().empty())
183 return Error::success();
186 OS
<< "cluster_id" << kCsvSep
<< "opcode_name" << kCsvSep
<< "config"
187 << kCsvSep
<< "sched_class";
188 for (const auto &Measurement
: Clustering_
.getPoints().front().Measurements
) {
190 writeEscaped
<kEscapeCsv
>(OS
, Measurement
.Key
);
195 const auto &Clusters
= Clustering_
.getValidClusters();
196 for (size_t I
= 0, E
= Clusters
.size(); I
< E
; ++I
) {
197 for (const size_t PointId
: Clusters
[I
].PointIndices
) {
198 printInstructionRowCsv(PointId
, OS
);
202 return Error::success();
205 Analysis::ResolvedSchedClassAndPoints::ResolvedSchedClassAndPoints(
206 ResolvedSchedClass
&&RSC
)
207 : RSC(std::move(RSC
)) {}
209 std::vector
<Analysis::ResolvedSchedClassAndPoints
>
210 Analysis::makePointsPerSchedClass() const {
211 std::vector
<ResolvedSchedClassAndPoints
> Entries
;
212 // Maps SchedClassIds to index in result.
213 std::unordered_map
<unsigned, size_t> SchedClassIdToIndex
;
214 const auto &Points
= Clustering_
.getPoints();
215 for (size_t PointId
= 0, E
= Points
.size(); PointId
< E
; ++PointId
) {
216 const InstructionBenchmark
&Point
= Points
[PointId
];
217 if (!Point
.Error
.empty())
219 assert(!Point
.Key
.Instructions
.empty());
220 // FIXME: we should be using the tuple of classes for instructions in the
222 const MCInst
&MCI
= Point
.keyInstruction();
223 unsigned SchedClassId
;
225 std::tie(SchedClassId
, WasVariant
) =
226 ResolvedSchedClass::resolveSchedClassId(*SubtargetInfo_
, *InstrInfo_
,
228 const auto IndexIt
= SchedClassIdToIndex
.find(SchedClassId
);
229 if (IndexIt
== SchedClassIdToIndex
.end()) {
230 // Create a new entry.
231 SchedClassIdToIndex
.emplace(SchedClassId
, Entries
.size());
232 ResolvedSchedClassAndPoints
Entry(
233 ResolvedSchedClass(*SubtargetInfo_
, SchedClassId
, WasVariant
));
234 Entry
.PointIds
.push_back(PointId
);
235 Entries
.push_back(std::move(Entry
));
237 // Append to the existing entry.
238 Entries
[IndexIt
->second
].PointIds
.push_back(PointId
);
244 // Uops repeat the same opcode over again. Just show this opcode and show the
245 // whole snippet only on hover.
246 static void writeUopsSnippetHtml(raw_ostream
&OS
,
247 const std::vector
<MCInst
> &Instructions
,
248 const MCInstrInfo
&InstrInfo
) {
249 if (Instructions
.empty())
251 writeEscaped
<kEscapeHtml
>(OS
, InstrInfo
.getName(Instructions
[0].getOpcode()));
252 if (Instructions
.size() > 1)
253 OS
<< " (x" << Instructions
.size() << ")";
256 // Latency tries to find a serial path. Just show the opcode path and show the
257 // whole snippet only on hover.
258 static void writeLatencySnippetHtml(raw_ostream
&OS
,
259 const std::vector
<MCInst
> &Instructions
,
260 const MCInstrInfo
&InstrInfo
) {
262 for (const MCInst
&Instr
: Instructions
) {
267 writeEscaped
<kEscapeHtml
>(OS
, InstrInfo
.getName(Instr
.getOpcode()));
271 void Analysis::printPointHtml(const InstructionBenchmark
&Point
,
272 llvm::raw_ostream
&OS
) const {
273 OS
<< "<li><span class=\"mono\" title=\"";
274 writeSnippet
<EscapeTag
, kEscapeHtmlString
>(OS
, Point
.AssembledSnippet
, "\n");
276 switch (Point
.Mode
) {
277 case InstructionBenchmark::Latency
:
278 writeLatencySnippetHtml(OS
, Point
.Key
.Instructions
, *InstrInfo_
);
280 case InstructionBenchmark::Uops
:
281 case InstructionBenchmark::InverseThroughput
:
282 writeUopsSnippetHtml(OS
, Point
.Key
.Instructions
, *InstrInfo_
);
285 llvm_unreachable("invalid mode");
287 OS
<< "</span> <span class=\"mono\">";
288 writeEscaped
<kEscapeHtml
>(OS
, Point
.Key
.Config
);
289 OS
<< "</span></li>";
292 void Analysis::printSchedClassClustersHtml(
293 const std::vector
<SchedClassCluster
> &Clusters
,
294 const ResolvedSchedClass
&RSC
, raw_ostream
&OS
) const {
295 const auto &Points
= Clustering_
.getPoints();
296 OS
<< "<table class=\"sched-class-clusters\">";
297 OS
<< "<tr><th>ClusterId</th><th>Opcode/Config</th>";
298 assert(!Clusters
.empty());
299 for (const auto &Measurement
:
300 Points
[Clusters
[0].getPointIds()[0]].Measurements
) {
302 writeEscaped
<kEscapeHtml
>(OS
, Measurement
.Key
);
306 for (const SchedClassCluster
&Cluster
: Clusters
) {
308 << (Cluster
.measurementsMatch(*SubtargetInfo_
, RSC
, Clustering_
,
309 AnalysisInconsistencyEpsilonSquared_
)
313 writeClusterId
<kEscapeHtml
>(OS
, Cluster
.id());
314 OS
<< "</td><td><ul>";
315 for (const size_t PointId
: Cluster
.getPointIds()) {
316 printPointHtml(Points
[PointId
], OS
);
319 for (const auto &Stats
: Cluster
.getCentroid().getStats()) {
320 OS
<< "<td class=\"measurement\">";
321 writeMeasurementValue
<kEscapeHtml
>(OS
, Stats
.avg());
322 OS
<< "<br><span class=\"minmax\">[";
323 writeMeasurementValue
<kEscapeHtml
>(OS
, Stats
.min());
325 writeMeasurementValue
<kEscapeHtml
>(OS
, Stats
.max());
326 OS
<< "]</span></td>";
333 void Analysis::SchedClassCluster::addPoint(
334 size_t PointId
, const InstructionBenchmarkClustering
&Clustering
) {
335 PointIds
.push_back(PointId
);
336 const auto &Point
= Clustering
.getPoints()[PointId
];
337 if (ClusterId
.isUndef())
338 ClusterId
= Clustering
.getClusterIdForPoint(PointId
);
339 assert(ClusterId
== Clustering
.getClusterIdForPoint(PointId
));
341 Centroid
.addPoint(Point
.Measurements
);
344 bool Analysis::SchedClassCluster::measurementsMatch(
345 const MCSubtargetInfo
&STI
, const ResolvedSchedClass
&RSC
,
346 const InstructionBenchmarkClustering
&Clustering
,
347 const double AnalysisInconsistencyEpsilonSquared_
) const {
348 assert(!Clustering
.getPoints().empty());
349 const InstructionBenchmark::ModeE Mode
= Clustering
.getPoints()[0].Mode
;
351 if (!Centroid
.validate(Mode
))
354 const std::vector
<BenchmarkMeasure
> ClusterCenterPoint
=
355 Centroid
.getAsPoint();
357 const std::vector
<BenchmarkMeasure
> SchedClassPoint
=
358 RSC
.getAsPoint(Mode
, STI
, Centroid
.getStats());
359 if (SchedClassPoint
.empty())
360 return false; // In Uops mode validate() may not be enough.
362 assert(ClusterCenterPoint
.size() == SchedClassPoint
.size() &&
363 "Expected measured/sched data dimensions to match.");
365 return Clustering
.isNeighbour(ClusterCenterPoint
, SchedClassPoint
,
366 AnalysisInconsistencyEpsilonSquared_
);
369 void Analysis::printSchedClassDescHtml(const ResolvedSchedClass
&RSC
,
370 raw_ostream
&OS
) const {
371 OS
<< "<table class=\"sched-class-desc\">";
372 OS
<< "<tr><th>Valid</th><th>Variant</th><th>NumMicroOps</th><th>Latency</"
373 "th><th>RThroughput</th><th>WriteProcRes</th><th title=\"This is the "
374 "idealized unit resource (port) pressure assuming ideal "
375 "distribution\">Idealized Resource Pressure</th></tr>";
376 if (RSC
.SCDesc
->isValid()) {
377 const auto &SM
= SubtargetInfo_
->getSchedModel();
378 OS
<< "<tr><td>✔</td>";
379 OS
<< "<td>" << (RSC
.WasVariant
? "✔" : "✕") << "</td>";
380 OS
<< "<td>" << RSC
.SCDesc
->NumMicroOps
<< "</td>";
383 for (int I
= 0, E
= RSC
.SCDesc
->NumWriteLatencyEntries
; I
< E
; ++I
) {
384 const auto *const Entry
=
385 SubtargetInfo_
->getWriteLatencyEntry(RSC
.SCDesc
, I
);
386 OS
<< "<li>" << Entry
->Cycles
;
387 if (RSC
.SCDesc
->NumWriteLatencyEntries
> 1) {
388 // Dismabiguate if more than 1 latency.
389 OS
<< " (WriteResourceID " << Entry
->WriteResourceID
<< ")";
394 // inverse throughput.
396 writeMeasurementValue
<kEscapeHtml
>(
398 MCSchedModel::getReciprocalThroughput(*SubtargetInfo_
, *RSC
.SCDesc
));
402 for (const auto &WPR
: RSC
.NonRedundantWriteProcRes
) {
403 OS
<< "<li><span class=\"mono\">";
404 writeEscaped
<kEscapeHtml
>(OS
,
405 SM
.getProcResource(WPR
.ProcResourceIdx
)->Name
);
406 OS
<< "</span>: " << WPR
.Cycles
<< "</li>";
409 // Idealized port pressure.
411 for (const auto &Pressure
: RSC
.IdealizedProcResPressure
) {
412 OS
<< "<li><span class=\"mono\">";
413 writeEscaped
<kEscapeHtml
>(OS
, SubtargetInfo_
->getSchedModel()
414 .getProcResource(Pressure
.first
)
417 writeMeasurementValue
<kEscapeHtml
>(OS
, Pressure
.second
);
423 OS
<< "<tr><td>✕</td><td></td><td></td></tr>";
428 void Analysis::printClusterRawHtml(
429 const InstructionBenchmarkClustering::ClusterId
&Id
, StringRef display_name
,
430 llvm::raw_ostream
&OS
) const {
431 const auto &Points
= Clustering_
.getPoints();
432 const auto &Cluster
= Clustering_
.getCluster(Id
);
433 if (Cluster
.PointIndices
.empty())
436 OS
<< "<div class=\"inconsistency\"><p>" << display_name
<< " Cluster ("
437 << Cluster
.PointIndices
.size() << " points)</p>";
438 OS
<< "<table class=\"sched-class-clusters\">";
440 OS
<< "<tr><th>ClusterId</th><th>Opcode/Config</th>";
441 for (const auto &Measurement
: Points
[Cluster
.PointIndices
[0]].Measurements
) {
443 writeEscaped
<kEscapeHtml
>(OS
, Measurement
.Key
);
449 for (const auto &PointId
: Cluster
.PointIndices
) {
450 OS
<< "<tr class=\"bad-cluster\"><td>" << display_name
<< "</td><td><ul>";
451 printPointHtml(Points
[PointId
], OS
);
453 for (const auto &Measurement
: Points
[PointId
].Measurements
) {
454 OS
<< "<td class=\"measurement\">";
455 writeMeasurementValue
<kEscapeHtml
>(OS
, Measurement
.PerInstructionValue
);
463 } // namespace exegesis
465 static constexpr const char kHtmlHead
[] = R
"(
467 <title>llvm-exegesis Analysis Results</title>
470 font-family: sans-serif
472 span.sched-class-name {
474 font-family: monospace;
477 font-family: monospace;
480 font-family: monospace;
487 border-collapse: collapse;
489 table, table tr,td,th {
490 border: 1px solid #444;
495 list-style-type: none;
497 table.sched-class-clusters td {
501 padding-bottom: 10px;
503 table.sched-class-desc td {
510 font-family: monospace;
515 tr.good-cluster td.measurement {
518 tr.bad-cluster td.measurement {
521 tr.good-cluster td.measurement span.minmax {
524 tr.bad-cluster td.measurement span.minmax {
532 Error
Analysis::run
<Analysis::PrintSchedClassInconsistencies
>(
533 raw_ostream
&OS
) const {
534 const auto &FirstPoint
= Clustering_
.getPoints()[0];
536 OS
<< "<!DOCTYPE html><html>" << kHtmlHead
<< "<body>";
537 OS
<< "<h1><span class=\"mono\">llvm-exegesis</span> Analysis Results</h1>";
538 OS
<< "<h3>Triple: <span class=\"mono\">";
539 writeEscaped
<kEscapeHtml
>(OS
, FirstPoint
.LLVMTriple
);
540 OS
<< "</span></h3><h3>Cpu: <span class=\"mono\">";
541 writeEscaped
<kEscapeHtml
>(OS
, FirstPoint
.CpuName
);
542 OS
<< "</span></h3>";
544 for (const auto &RSCAndPoints
: makePointsPerSchedClass()) {
545 if (!RSCAndPoints
.RSC
.SCDesc
)
547 // Bucket sched class points into sched class clusters.
548 std::vector
<SchedClassCluster
> SchedClassClusters
;
549 for (const size_t PointId
: RSCAndPoints
.PointIds
) {
550 const auto &ClusterId
= Clustering_
.getClusterIdForPoint(PointId
);
551 if (!ClusterId
.isValid())
552 continue; // Ignore noise and errors. FIXME: take noise into account ?
553 if (ClusterId
.isUnstable() ^ AnalysisDisplayUnstableOpcodes_
)
554 continue; // Either display stable or unstable clusters only.
555 auto SchedClassClusterIt
=
556 std::find_if(SchedClassClusters
.begin(), SchedClassClusters
.end(),
557 [ClusterId
](const SchedClassCluster
&C
) {
558 return C
.id() == ClusterId
;
560 if (SchedClassClusterIt
== SchedClassClusters
.end()) {
561 SchedClassClusters
.emplace_back();
562 SchedClassClusterIt
= std::prev(SchedClassClusters
.end());
564 SchedClassClusterIt
->addPoint(PointId
, Clustering_
);
567 // Print any scheduling class that has at least one cluster that does not
568 // match the checked-in data.
569 if (all_of(SchedClassClusters
, [this,
570 &RSCAndPoints
](const SchedClassCluster
&C
) {
571 return C
.measurementsMatch(*SubtargetInfo_
, RSCAndPoints
.RSC
,
573 AnalysisInconsistencyEpsilonSquared_
);
575 continue; // Nothing weird.
577 OS
<< "<div class=\"inconsistency\"><p>Sched Class <span "
578 "class=\"sched-class-name\">";
579 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
580 writeEscaped
<kEscapeHtml
>(OS
, RSCAndPoints
.RSC
.SCDesc
->Name
);
582 OS
<< RSCAndPoints
.RSC
.SchedClassId
;
584 OS
<< "</span> contains instructions whose performance characteristics do"
585 " not match that of LLVM:</p>";
586 printSchedClassClustersHtml(SchedClassClusters
, RSCAndPoints
.RSC
, OS
);
587 OS
<< "<p>llvm SchedModel data:</p>";
588 printSchedClassDescHtml(RSCAndPoints
.RSC
, OS
);
592 printClusterRawHtml(InstructionBenchmarkClustering::ClusterId::noise(),
595 OS
<< "</body></html>";
596 return Error::success();
599 } // namespace exegesis