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/MC/MCTargetOptions.h"
14 #include "llvm/Support/FormatVariadic.h"
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 (!S
.contains(kCsvSep
)) {
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 BenchmarkClustering::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 (!DisasmHelper_
->decodeInst(MI
, MISize
, Bytes
)) {
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 DisasmHelper_
->printInst(&MI
, OSS
);
117 Bytes
= Bytes
.drop_front(MISize
);
118 Lines
.emplace_back(InstPrinterStr
.str().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 Benchmark
&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 State_
.getSubtargetInfo(), State_
.getInstrInfo(), MCI
);
139 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
140 const MCSchedClassDesc
*const SCDesc
=
141 State_
.getSubtargetInfo().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 LLVMState
&State
,
154 const BenchmarkClustering
&Clustering
,
155 double AnalysisInconsistencyEpsilon
,
156 bool AnalysisDisplayUnstableOpcodes
)
157 : Clustering_(Clustering
), State_(State
),
158 AnalysisInconsistencyEpsilonSquared_(AnalysisInconsistencyEpsilon
*
159 AnalysisInconsistencyEpsilon
),
160 AnalysisDisplayUnstableOpcodes_(AnalysisDisplayUnstableOpcodes
) {
161 if (Clustering
.getPoints().empty())
164 DisasmHelper_
= std::make_unique
<DisassemblerHelper
>(State
);
168 Error
Analysis::run
<Analysis::PrintClusters
>(raw_ostream
&OS
) const {
169 if (Clustering_
.getPoints().empty())
170 return Error::success();
173 OS
<< "cluster_id" << kCsvSep
<< "opcode_name" << kCsvSep
<< "config"
174 << kCsvSep
<< "sched_class";
175 for (const auto &Measurement
: Clustering_
.getPoints().front().Measurements
) {
177 writeEscaped
<kEscapeCsv
>(OS
, Measurement
.Key
);
182 for (const auto &ClusterIt
: Clustering_
.getValidClusters()) {
183 for (const size_t PointId
: ClusterIt
.PointIndices
) {
184 printInstructionRowCsv(PointId
, OS
);
188 return Error::success();
191 Analysis::ResolvedSchedClassAndPoints::ResolvedSchedClassAndPoints(
192 ResolvedSchedClass
&&RSC
)
193 : RSC(std::move(RSC
)) {}
195 std::vector
<Analysis::ResolvedSchedClassAndPoints
>
196 Analysis::makePointsPerSchedClass() const {
197 std::vector
<ResolvedSchedClassAndPoints
> Entries
;
198 // Maps SchedClassIds to index in result.
199 std::unordered_map
<unsigned, size_t> SchedClassIdToIndex
;
200 const auto &Points
= Clustering_
.getPoints();
201 for (size_t PointId
= 0, E
= Points
.size(); PointId
< E
; ++PointId
) {
202 const Benchmark
&Point
= Points
[PointId
];
203 if (!Point
.Error
.empty())
205 assert(!Point
.Key
.Instructions
.empty());
206 // FIXME: we should be using the tuple of classes for instructions in the
208 const MCInst
&MCI
= Point
.keyInstruction();
209 unsigned SchedClassId
;
211 std::tie(SchedClassId
, WasVariant
) =
212 ResolvedSchedClass::resolveSchedClassId(State_
.getSubtargetInfo(),
213 State_
.getInstrInfo(), MCI
);
214 const auto IndexIt
= SchedClassIdToIndex
.find(SchedClassId
);
215 if (IndexIt
== SchedClassIdToIndex
.end()) {
216 // Create a new entry.
217 SchedClassIdToIndex
.emplace(SchedClassId
, Entries
.size());
218 ResolvedSchedClassAndPoints
Entry(ResolvedSchedClass(
219 State_
.getSubtargetInfo(), SchedClassId
, WasVariant
));
220 Entry
.PointIds
.push_back(PointId
);
221 Entries
.push_back(std::move(Entry
));
223 // Append to the existing entry.
224 Entries
[IndexIt
->second
].PointIds
.push_back(PointId
);
230 // Parallel benchmarks repeat the same opcode multiple times. Just show this
231 // opcode and show the whole snippet only on hover.
232 static void writeParallelSnippetHtml(raw_ostream
&OS
,
233 const std::vector
<MCInst
> &Instructions
,
234 const MCInstrInfo
&InstrInfo
) {
235 if (Instructions
.empty())
237 writeEscaped
<kEscapeHtml
>(OS
, InstrInfo
.getName(Instructions
[0].getOpcode()));
238 if (Instructions
.size() > 1)
239 OS
<< " (x" << Instructions
.size() << ")";
242 // Latency tries to find a serial path. Just show the opcode path and show the
243 // whole snippet only on hover.
244 static void writeLatencySnippetHtml(raw_ostream
&OS
,
245 const std::vector
<MCInst
> &Instructions
,
246 const MCInstrInfo
&InstrInfo
) {
248 for (const MCInst
&Instr
: Instructions
) {
253 writeEscaped
<kEscapeHtml
>(OS
, InstrInfo
.getName(Instr
.getOpcode()));
257 void Analysis::printPointHtml(const Benchmark
&Point
, raw_ostream
&OS
) const {
258 OS
<< "<li><span class=\"mono\" title=\"";
259 writeSnippet
<EscapeTag
, kEscapeHtmlString
>(OS
, Point
.AssembledSnippet
, "\n");
261 switch (Point
.Mode
) {
262 case Benchmark::Latency
:
263 writeLatencySnippetHtml(OS
, Point
.Key
.Instructions
, State_
.getInstrInfo());
265 case Benchmark::Uops
:
266 case Benchmark::InverseThroughput
:
267 writeParallelSnippetHtml(OS
, Point
.Key
.Instructions
, State_
.getInstrInfo());
270 llvm_unreachable("invalid mode");
272 OS
<< "</span> <span class=\"mono\">";
273 writeEscaped
<kEscapeHtml
>(OS
, Point
.Key
.Config
);
274 OS
<< "</span></li>";
277 void Analysis::printSchedClassClustersHtml(
278 const std::vector
<SchedClassCluster
> &Clusters
,
279 const ResolvedSchedClass
&RSC
, raw_ostream
&OS
) const {
280 const auto &Points
= Clustering_
.getPoints();
281 OS
<< "<table class=\"sched-class-clusters\">";
282 OS
<< "<tr><th>ClusterId</th><th>Opcode/Config</th>";
283 assert(!Clusters
.empty());
284 for (const auto &Measurement
:
285 Points
[Clusters
[0].getPointIds()[0]].Measurements
) {
287 writeEscaped
<kEscapeHtml
>(OS
, Measurement
.Key
);
291 for (const SchedClassCluster
&Cluster
: Clusters
) {
293 << (Cluster
.measurementsMatch(State_
.getSubtargetInfo(), RSC
,
295 AnalysisInconsistencyEpsilonSquared_
)
299 writeClusterId
<kEscapeHtml
>(OS
, Cluster
.id());
300 OS
<< "</td><td><ul>";
301 for (const size_t PointId
: Cluster
.getPointIds()) {
302 printPointHtml(Points
[PointId
], OS
);
305 for (const auto &Stats
: Cluster
.getCentroid().getStats()) {
306 OS
<< "<td class=\"measurement\">";
307 writeMeasurementValue
<kEscapeHtml
>(OS
, Stats
.avg());
308 OS
<< "<br><span class=\"minmax\">[";
309 writeMeasurementValue
<kEscapeHtml
>(OS
, Stats
.min());
311 writeMeasurementValue
<kEscapeHtml
>(OS
, Stats
.max());
312 OS
<< "]</span></td>";
319 void Analysis::SchedClassCluster::addPoint(
320 size_t PointId
, const BenchmarkClustering
&Clustering
) {
321 PointIds
.push_back(PointId
);
322 const auto &Point
= Clustering
.getPoints()[PointId
];
323 if (ClusterId
.isUndef())
324 ClusterId
= Clustering
.getClusterIdForPoint(PointId
);
325 assert(ClusterId
== Clustering
.getClusterIdForPoint(PointId
));
327 Centroid
.addPoint(Point
.Measurements
);
330 bool Analysis::SchedClassCluster::measurementsMatch(
331 const MCSubtargetInfo
&STI
, const ResolvedSchedClass
&RSC
,
332 const BenchmarkClustering
&Clustering
,
333 const double AnalysisInconsistencyEpsilonSquared_
) const {
334 assert(!Clustering
.getPoints().empty());
335 const Benchmark::ModeE Mode
= Clustering
.getPoints()[0].Mode
;
337 if (!Centroid
.validate(Mode
))
340 const std::vector
<BenchmarkMeasure
> ClusterCenterPoint
=
341 Centroid
.getAsPoint();
343 const std::vector
<BenchmarkMeasure
> SchedClassPoint
=
344 RSC
.getAsPoint(Mode
, STI
, Centroid
.getStats());
345 if (SchedClassPoint
.empty())
346 return false; // In Uops mode validate() may not be enough.
348 assert(ClusterCenterPoint
.size() == SchedClassPoint
.size() &&
349 "Expected measured/sched data dimensions to match.");
351 return Clustering
.isNeighbour(ClusterCenterPoint
, SchedClassPoint
,
352 AnalysisInconsistencyEpsilonSquared_
);
355 void Analysis::printSchedClassDescHtml(const ResolvedSchedClass
&RSC
,
356 raw_ostream
&OS
) const {
357 OS
<< "<table class=\"sched-class-desc\">";
358 OS
<< "<tr><th>Valid</th><th>Variant</th><th>NumMicroOps</th><th>Latency</"
359 "th><th>RThroughput</th><th>WriteProcRes</th><th title=\"This is the "
360 "idealized unit resource (port) pressure assuming ideal "
361 "distribution\">Idealized Resource Pressure</th></tr>";
362 if (RSC
.SCDesc
->isValid()) {
363 const auto &SI
= State_
.getSubtargetInfo();
364 const auto &SM
= SI
.getSchedModel();
365 OS
<< "<tr><td>✔</td>";
366 OS
<< "<td>" << (RSC
.WasVariant
? "✔" : "✕") << "</td>";
367 OS
<< "<td>" << RSC
.SCDesc
->NumMicroOps
<< "</td>";
370 for (int I
= 0, E
= RSC
.SCDesc
->NumWriteLatencyEntries
; I
< E
; ++I
) {
371 const auto *const Entry
= SI
.getWriteLatencyEntry(RSC
.SCDesc
, I
);
372 OS
<< "<li>" << Entry
->Cycles
;
373 if (RSC
.SCDesc
->NumWriteLatencyEntries
> 1) {
374 // Dismabiguate if more than 1 latency.
375 OS
<< " (WriteResourceID " << Entry
->WriteResourceID
<< ")";
380 // inverse throughput.
382 writeMeasurementValue
<kEscapeHtml
>(
383 OS
, MCSchedModel::getReciprocalThroughput(SI
, *RSC
.SCDesc
));
387 for (const auto &WPR
: RSC
.NonRedundantWriteProcRes
) {
388 OS
<< "<li><span class=\"mono\">";
389 writeEscaped
<kEscapeHtml
>(OS
,
390 SM
.getProcResource(WPR
.ProcResourceIdx
)->Name
);
391 OS
<< "</span>: " << WPR
.ReleaseAtCycle
<< "</li>";
394 // Idealized port pressure.
396 for (const auto &Pressure
: RSC
.IdealizedProcResPressure
) {
397 OS
<< "<li><span class=\"mono\">";
398 writeEscaped
<kEscapeHtml
>(
399 OS
, SI
.getSchedModel().getProcResource(Pressure
.first
)->Name
);
401 writeMeasurementValue
<kEscapeHtml
>(OS
, Pressure
.second
);
407 OS
<< "<tr><td>✕</td><td></td><td></td></tr>";
412 void Analysis::printClusterRawHtml(const BenchmarkClustering::ClusterId
&Id
,
413 StringRef display_name
,
414 raw_ostream
&OS
) const {
415 const auto &Points
= Clustering_
.getPoints();
416 const auto &Cluster
= Clustering_
.getCluster(Id
);
417 if (Cluster
.PointIndices
.empty())
420 OS
<< "<div class=\"inconsistency\"><p>" << display_name
<< " Cluster ("
421 << Cluster
.PointIndices
.size() << " points)</p>";
422 OS
<< "<table class=\"sched-class-clusters\">";
424 OS
<< "<tr><th>ClusterId</th><th>Opcode/Config</th>";
425 for (const auto &Measurement
: Points
[Cluster
.PointIndices
[0]].Measurements
) {
427 writeEscaped
<kEscapeHtml
>(OS
, Measurement
.Key
);
433 for (const auto &PointId
: Cluster
.PointIndices
) {
434 OS
<< "<tr class=\"bad-cluster\"><td>" << display_name
<< "</td><td><ul>";
435 printPointHtml(Points
[PointId
], OS
);
437 for (const auto &Measurement
: Points
[PointId
].Measurements
) {
438 OS
<< "<td class=\"measurement\">";
439 writeMeasurementValue
<kEscapeHtml
>(OS
, Measurement
.PerInstructionValue
);
447 } // namespace exegesis
449 static constexpr const char kHtmlHead
[] = R
"(
451 <title>llvm-exegesis Analysis Results</title>
454 font-family: sans-serif
456 span.sched-class-name {
458 font-family: monospace;
461 font-family: monospace;
464 font-family: monospace;
471 border-collapse: collapse;
473 table, table tr,td,th {
474 border: 1px solid #444;
479 list-style-type: none;
481 table.sched-class-clusters td {
485 padding-bottom: 10px;
487 table.sched-class-desc td {
494 font-family: monospace;
499 tr.good-cluster td.measurement {
502 tr.bad-cluster td.measurement {
505 tr.good-cluster td.measurement span.minmax {
508 tr.bad-cluster td.measurement span.minmax {
516 Error
Analysis::run
<Analysis::PrintSchedClassInconsistencies
>(
517 raw_ostream
&OS
) const {
518 const auto &FirstPoint
= Clustering_
.getPoints()[0];
520 OS
<< "<!DOCTYPE html><html>" << kHtmlHead
<< "<body>";
521 OS
<< "<h1><span class=\"mono\">llvm-exegesis</span> Analysis Results</h1>";
522 OS
<< "<h3>Triple: <span class=\"mono\">";
523 writeEscaped
<kEscapeHtml
>(OS
, FirstPoint
.LLVMTriple
);
524 OS
<< "</span></h3><h3>Cpu: <span class=\"mono\">";
525 writeEscaped
<kEscapeHtml
>(OS
, FirstPoint
.CpuName
);
526 OS
<< "</span></h3>";
527 OS
<< "<h3>Epsilon: <span class=\"mono\">"
528 << format("%0.2f", std::sqrt(AnalysisInconsistencyEpsilonSquared_
))
531 const auto &SI
= State_
.getSubtargetInfo();
532 for (const auto &RSCAndPoints
: makePointsPerSchedClass()) {
533 if (!RSCAndPoints
.RSC
.SCDesc
)
535 // Bucket sched class points into sched class clusters.
536 std::vector
<SchedClassCluster
> SchedClassClusters
;
537 for (const size_t PointId
: RSCAndPoints
.PointIds
) {
538 const auto &ClusterId
= Clustering_
.getClusterIdForPoint(PointId
);
539 if (!ClusterId
.isValid())
540 continue; // Ignore noise and errors. FIXME: take noise into account ?
541 if (ClusterId
.isUnstable() ^ AnalysisDisplayUnstableOpcodes_
)
542 continue; // Either display stable or unstable clusters only.
543 auto SchedClassClusterIt
=
544 find_if(SchedClassClusters
, [ClusterId
](const SchedClassCluster
&C
) {
545 return C
.id() == ClusterId
;
547 if (SchedClassClusterIt
== SchedClassClusters
.end()) {
548 SchedClassClusters
.emplace_back();
549 SchedClassClusterIt
= std::prev(SchedClassClusters
.end());
551 SchedClassClusterIt
->addPoint(PointId
, Clustering_
);
554 // Print any scheduling class that has at least one cluster that does not
555 // match the checked-in data.
556 if (all_of(SchedClassClusters
, [this, &RSCAndPoints
,
557 &SI
](const SchedClassCluster
&C
) {
558 return C
.measurementsMatch(SI
, RSCAndPoints
.RSC
, Clustering_
,
559 AnalysisInconsistencyEpsilonSquared_
);
561 continue; // Nothing weird.
563 OS
<< "<div class=\"inconsistency\"><p>Sched Class <span "
564 "class=\"sched-class-name\">";
565 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
566 writeEscaped
<kEscapeHtml
>(OS
, RSCAndPoints
.RSC
.SCDesc
->Name
);
568 OS
<< RSCAndPoints
.RSC
.SchedClassId
;
570 OS
<< "</span> contains instructions whose performance characteristics do"
571 " not match that of LLVM:</p>";
572 printSchedClassClustersHtml(SchedClassClusters
, RSCAndPoints
.RSC
, OS
);
573 OS
<< "<p>llvm SchedModel data:</p>";
574 printSchedClassDescHtml(RSCAndPoints
.RSC
, OS
);
578 printClusterRawHtml(BenchmarkClustering::ClusterId::noise(),
581 OS
<< "</body></html>";
582 return Error::success();
585 } // namespace exegesis