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
>
28 void writeEscaped(llvm::raw_ostream
&OS
, const llvm::StringRef S
);
31 void writeEscaped
<kEscapeCsv
>(llvm::raw_ostream
&OS
, const llvm::StringRef S
) {
32 if (std::find(S
.begin(), S
.end(), kCsvSep
) == S
.end()) {
37 for (const char C
: S
) {
48 void writeEscaped
<kEscapeHtml
>(llvm::raw_ostream
&OS
, const llvm::StringRef S
) {
49 for (const char C
: S
) {
62 void writeEscaped
<kEscapeHtmlString
>(llvm::raw_ostream
&OS
,
63 const llvm::StringRef S
) {
64 for (const char C
: S
) {
74 template <EscapeTag Tag
>
76 writeClusterId(llvm::raw_ostream
&OS
,
77 const InstructionBenchmarkClustering::ClusterId
&CID
) {
79 writeEscaped
<Tag
>(OS
, "[noise]");
80 else if (CID
.isError())
81 writeEscaped
<Tag
>(OS
, "[error]");
86 template <EscapeTag Tag
>
87 static void writeMeasurementValue(llvm::raw_ostream
&OS
, const double Value
) {
88 // Given Value, if we wanted to serialize it to a string,
89 // how many base-10 digits will we need to store, max?
90 static constexpr auto MaxDigitCount
=
91 std::numeric_limits
<decltype(Value
)>::max_digits10
;
92 // Also, we will need a decimal separator.
93 static constexpr auto DecimalSeparatorLen
= 1; // '.' e.g.
94 // So how long of a string will the serialization produce, max?
95 static constexpr auto SerializationLen
= MaxDigitCount
+ DecimalSeparatorLen
;
97 // WARNING: when changing the format, also adjust the small-size estimate ^.
98 static constexpr StringLiteral SimpleFloatFormat
= StringLiteral("{0:F}");
102 llvm::formatv(SimpleFloatFormat
.data(), Value
).sstr
<SerializationLen
>());
105 template <typename EscapeTag
, EscapeTag Tag
>
106 void Analysis::writeSnippet(llvm::raw_ostream
&OS
,
107 llvm::ArrayRef
<uint8_t> Bytes
,
108 const char *Separator
) const {
109 llvm::SmallVector
<std::string
, 3> Lines
;
110 // Parse the asm snippet and print it.
111 while (!Bytes
.empty()) {
114 if (!Disasm_
->getInstruction(MI
, MISize
, Bytes
, 0, llvm::nulls(),
116 writeEscaped
<Tag
>(OS
, llvm::join(Lines
, Separator
));
117 writeEscaped
<Tag
>(OS
, Separator
);
118 writeEscaped
<Tag
>(OS
, "[error decoding asm snippet]");
121 llvm::SmallString
<128> InstPrinterStr
; // FIXME: magic number.
122 llvm::raw_svector_ostream
OSS(InstPrinterStr
);
123 InstPrinter_
->printInst(&MI
, OSS
, "", *SubtargetInfo_
);
124 Bytes
= Bytes
.drop_front(MISize
);
125 Lines
.emplace_back(llvm::StringRef(InstPrinterStr
).trim());
127 writeEscaped
<Tag
>(OS
, llvm::join(Lines
, Separator
));
130 // Prints a row representing an instruction, along with scheduling info and
131 // point coordinates (measurements).
132 void Analysis::printInstructionRowCsv(const size_t PointId
,
133 llvm::raw_ostream
&OS
) const {
134 const InstructionBenchmark
&Point
= Clustering_
.getPoints()[PointId
];
135 writeClusterId
<kEscapeCsv
>(OS
, Clustering_
.getClusterIdForPoint(PointId
));
137 writeSnippet
<EscapeTag
, kEscapeCsv
>(OS
, Point
.AssembledSnippet
, "; ");
139 writeEscaped
<kEscapeCsv
>(OS
, Point
.Key
.Config
);
141 assert(!Point
.Key
.Instructions
.empty());
142 const llvm::MCInst
&MCI
= Point
.keyInstruction();
143 unsigned SchedClassId
;
144 std::tie(SchedClassId
, std::ignore
) = ResolvedSchedClass::resolveSchedClassId(
145 *SubtargetInfo_
, *InstrInfo_
, MCI
);
146 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
147 const llvm::MCSchedClassDesc
*const SCDesc
=
148 SubtargetInfo_
->getSchedModel().getSchedClassDesc(SchedClassId
);
149 writeEscaped
<kEscapeCsv
>(OS
, SCDesc
->Name
);
153 for (const auto &Measurement
: Point
.Measurements
) {
155 writeMeasurementValue
<kEscapeCsv
>(OS
, Measurement
.PerInstructionValue
);
160 Analysis::Analysis(const llvm::Target
&Target
,
161 std::unique_ptr
<llvm::MCInstrInfo
> InstrInfo
,
162 const InstructionBenchmarkClustering
&Clustering
,
163 double AnalysisInconsistencyEpsilon
,
164 bool AnalysisDisplayUnstableOpcodes
)
165 : Clustering_(Clustering
), InstrInfo_(std::move(InstrInfo
)),
166 AnalysisInconsistencyEpsilonSquared_(AnalysisInconsistencyEpsilon
*
167 AnalysisInconsistencyEpsilon
),
168 AnalysisDisplayUnstableOpcodes_(AnalysisDisplayUnstableOpcodes
) {
169 if (Clustering
.getPoints().empty())
172 const InstructionBenchmark
&FirstPoint
= Clustering
.getPoints().front();
173 RegInfo_
.reset(Target
.createMCRegInfo(FirstPoint
.LLVMTriple
));
174 AsmInfo_
.reset(Target
.createMCAsmInfo(*RegInfo_
, FirstPoint
.LLVMTriple
));
175 SubtargetInfo_
.reset(Target
.createMCSubtargetInfo(FirstPoint
.LLVMTriple
,
176 FirstPoint
.CpuName
, ""));
177 InstPrinter_
.reset(Target
.createMCInstPrinter(
178 llvm::Triple(FirstPoint
.LLVMTriple
), 0 /*default variant*/, *AsmInfo_
,
179 *InstrInfo_
, *RegInfo_
));
181 Context_
= std::make_unique
<llvm::MCContext
>(AsmInfo_
.get(), RegInfo_
.get(),
183 Disasm_
.reset(Target
.createMCDisassembler(*SubtargetInfo_
, *Context_
));
184 assert(Disasm_
&& "cannot create MCDisassembler. missing call to "
185 "InitializeXXXTargetDisassembler ?");
190 Analysis::run
<Analysis::PrintClusters
>(llvm::raw_ostream
&OS
) const {
191 if (Clustering_
.getPoints().empty())
192 return llvm::Error::success();
195 OS
<< "cluster_id" << kCsvSep
<< "opcode_name" << kCsvSep
<< "config"
196 << kCsvSep
<< "sched_class";
197 for (const auto &Measurement
: Clustering_
.getPoints().front().Measurements
) {
199 writeEscaped
<kEscapeCsv
>(OS
, Measurement
.Key
);
204 const auto &Clusters
= Clustering_
.getValidClusters();
205 for (size_t I
= 0, E
= Clusters
.size(); I
< E
; ++I
) {
206 for (const size_t PointId
: Clusters
[I
].PointIndices
) {
207 printInstructionRowCsv(PointId
, OS
);
211 return llvm::Error::success();
214 Analysis::ResolvedSchedClassAndPoints::ResolvedSchedClassAndPoints(
215 ResolvedSchedClass
&&RSC
)
216 : RSC(std::move(RSC
)) {}
218 std::vector
<Analysis::ResolvedSchedClassAndPoints
>
219 Analysis::makePointsPerSchedClass() const {
220 std::vector
<ResolvedSchedClassAndPoints
> Entries
;
221 // Maps SchedClassIds to index in result.
222 std::unordered_map
<unsigned, size_t> SchedClassIdToIndex
;
223 const auto &Points
= Clustering_
.getPoints();
224 for (size_t PointId
= 0, E
= Points
.size(); PointId
< E
; ++PointId
) {
225 const InstructionBenchmark
&Point
= Points
[PointId
];
226 if (!Point
.Error
.empty())
228 assert(!Point
.Key
.Instructions
.empty());
229 // FIXME: we should be using the tuple of classes for instructions in the
231 const llvm::MCInst
&MCI
= Point
.keyInstruction();
232 unsigned SchedClassId
;
234 std::tie(SchedClassId
, WasVariant
) =
235 ResolvedSchedClass::resolveSchedClassId(*SubtargetInfo_
, *InstrInfo_
,
237 const auto IndexIt
= SchedClassIdToIndex
.find(SchedClassId
);
238 if (IndexIt
== SchedClassIdToIndex
.end()) {
239 // Create a new entry.
240 SchedClassIdToIndex
.emplace(SchedClassId
, Entries
.size());
241 ResolvedSchedClassAndPoints
Entry(
242 ResolvedSchedClass(*SubtargetInfo_
, SchedClassId
, WasVariant
));
243 Entry
.PointIds
.push_back(PointId
);
244 Entries
.push_back(std::move(Entry
));
246 // Append to the existing entry.
247 Entries
[IndexIt
->second
].PointIds
.push_back(PointId
);
253 // Uops repeat the same opcode over again. Just show this opcode and show the
254 // whole snippet only on hover.
255 static void writeUopsSnippetHtml(llvm::raw_ostream
&OS
,
256 const std::vector
<llvm::MCInst
> &Instructions
,
257 const llvm::MCInstrInfo
&InstrInfo
) {
258 if (Instructions
.empty())
260 writeEscaped
<kEscapeHtml
>(OS
, InstrInfo
.getName(Instructions
[0].getOpcode()));
261 if (Instructions
.size() > 1)
262 OS
<< " (x" << Instructions
.size() << ")";
265 // Latency tries to find a serial path. Just show the opcode path and show the
266 // whole snippet only on hover.
268 writeLatencySnippetHtml(llvm::raw_ostream
&OS
,
269 const std::vector
<llvm::MCInst
> &Instructions
,
270 const llvm::MCInstrInfo
&InstrInfo
) {
272 for (const llvm::MCInst
&Instr
: Instructions
) {
277 writeEscaped
<kEscapeHtml
>(OS
, InstrInfo
.getName(Instr
.getOpcode()));
281 void Analysis::printSchedClassClustersHtml(
282 const std::vector
<SchedClassCluster
> &Clusters
,
283 const ResolvedSchedClass
&RSC
, llvm::raw_ostream
&OS
) const {
284 const auto &Points
= Clustering_
.getPoints();
285 OS
<< "<table class=\"sched-class-clusters\">";
286 OS
<< "<tr><th>ClusterId</th><th>Opcode/Config</th>";
287 assert(!Clusters
.empty());
288 for (const auto &Measurement
:
289 Points
[Clusters
[0].getPointIds()[0]].Measurements
) {
291 writeEscaped
<kEscapeHtml
>(OS
, Measurement
.Key
);
295 for (const SchedClassCluster
&Cluster
: Clusters
) {
297 << (Cluster
.measurementsMatch(*SubtargetInfo_
, RSC
, Clustering_
,
298 AnalysisInconsistencyEpsilonSquared_
)
302 writeClusterId
<kEscapeHtml
>(OS
, Cluster
.id());
303 OS
<< "</td><td><ul>";
304 for (const size_t PointId
: Cluster
.getPointIds()) {
305 const auto &Point
= Points
[PointId
];
306 OS
<< "<li><span class=\"mono\" title=\"";
307 writeSnippet
<EscapeTag
, kEscapeHtmlString
>(OS
, Point
.AssembledSnippet
,
310 switch (Point
.Mode
) {
311 case InstructionBenchmark::Latency
:
312 writeLatencySnippetHtml(OS
, Point
.Key
.Instructions
, *InstrInfo_
);
314 case InstructionBenchmark::Uops
:
315 case InstructionBenchmark::InverseThroughput
:
316 writeUopsSnippetHtml(OS
, Point
.Key
.Instructions
, *InstrInfo_
);
319 llvm_unreachable("invalid mode");
321 OS
<< "</span> <span class=\"mono\">";
322 writeEscaped
<kEscapeHtml
>(OS
, Point
.Key
.Config
);
323 OS
<< "</span></li>";
326 for (const auto &Stats
: Cluster
.getCentroid().getStats()) {
327 OS
<< "<td class=\"measurement\">";
328 writeMeasurementValue
<kEscapeHtml
>(OS
, Stats
.avg());
329 OS
<< "<br><span class=\"minmax\">[";
330 writeMeasurementValue
<kEscapeHtml
>(OS
, Stats
.min());
332 writeMeasurementValue
<kEscapeHtml
>(OS
, Stats
.max());
333 OS
<< "]</span></td>";
340 void Analysis::SchedClassCluster::addPoint(
341 size_t PointId
, const InstructionBenchmarkClustering
&Clustering
) {
342 PointIds
.push_back(PointId
);
343 const auto &Point
= Clustering
.getPoints()[PointId
];
344 if (ClusterId
.isUndef())
345 ClusterId
= Clustering
.getClusterIdForPoint(PointId
);
346 assert(ClusterId
== Clustering
.getClusterIdForPoint(PointId
));
348 Centroid
.addPoint(Point
.Measurements
);
351 bool Analysis::SchedClassCluster::measurementsMatch(
352 const llvm::MCSubtargetInfo
&STI
, const ResolvedSchedClass
&RSC
,
353 const InstructionBenchmarkClustering
&Clustering
,
354 const double AnalysisInconsistencyEpsilonSquared_
) const {
355 assert(!Clustering
.getPoints().empty());
356 const InstructionBenchmark::ModeE Mode
= Clustering
.getPoints()[0].Mode
;
358 if (!Centroid
.validate(Mode
))
361 const std::vector
<BenchmarkMeasure
> ClusterCenterPoint
=
362 Centroid
.getAsPoint();
364 const std::vector
<BenchmarkMeasure
> SchedClassPoint
=
365 RSC
.getAsPoint(Mode
, STI
, Centroid
.getStats());
366 if (SchedClassPoint
.empty())
367 return false; // In Uops mode validate() may not be enough.
369 assert(ClusterCenterPoint
.size() == SchedClassPoint
.size() &&
370 "Expected measured/sched data dimensions to match.");
372 return Clustering
.isNeighbour(ClusterCenterPoint
, SchedClassPoint
,
373 AnalysisInconsistencyEpsilonSquared_
);
376 void Analysis::printSchedClassDescHtml(const ResolvedSchedClass
&RSC
,
377 llvm::raw_ostream
&OS
) const {
378 OS
<< "<table class=\"sched-class-desc\">";
379 OS
<< "<tr><th>Valid</th><th>Variant</th><th>NumMicroOps</th><th>Latency</"
380 "th><th>RThroughput</th><th>WriteProcRes</th><th title=\"This is the "
381 "idealized unit resource (port) pressure assuming ideal "
382 "distribution\">Idealized Resource Pressure</th></tr>";
383 if (RSC
.SCDesc
->isValid()) {
384 const auto &SM
= SubtargetInfo_
->getSchedModel();
385 OS
<< "<tr><td>✔</td>";
386 OS
<< "<td>" << (RSC
.WasVariant
? "✔" : "✕") << "</td>";
387 OS
<< "<td>" << RSC
.SCDesc
->NumMicroOps
<< "</td>";
390 for (int I
= 0, E
= RSC
.SCDesc
->NumWriteLatencyEntries
; I
< E
; ++I
) {
391 const auto *const Entry
=
392 SubtargetInfo_
->getWriteLatencyEntry(RSC
.SCDesc
, I
);
393 OS
<< "<li>" << Entry
->Cycles
;
394 if (RSC
.SCDesc
->NumWriteLatencyEntries
> 1) {
395 // Dismabiguate if more than 1 latency.
396 OS
<< " (WriteResourceID " << Entry
->WriteResourceID
<< ")";
401 // inverse throughput.
403 writeMeasurementValue
<kEscapeHtml
>(
405 MCSchedModel::getReciprocalThroughput(*SubtargetInfo_
, *RSC
.SCDesc
));
409 for (const auto &WPR
: RSC
.NonRedundantWriteProcRes
) {
410 OS
<< "<li><span class=\"mono\">";
411 writeEscaped
<kEscapeHtml
>(OS
,
412 SM
.getProcResource(WPR
.ProcResourceIdx
)->Name
);
413 OS
<< "</span>: " << WPR
.Cycles
<< "</li>";
416 // Idealized port pressure.
418 for (const auto &Pressure
: RSC
.IdealizedProcResPressure
) {
419 OS
<< "<li><span class=\"mono\">";
420 writeEscaped
<kEscapeHtml
>(OS
, SubtargetInfo_
->getSchedModel()
421 .getProcResource(Pressure
.first
)
424 writeMeasurementValue
<kEscapeHtml
>(OS
, Pressure
.second
);
430 OS
<< "<tr><td>✕</td><td></td><td></td></tr>";
435 static constexpr const char kHtmlHead
[] = R
"(
437 <title>llvm-exegesis Analysis Results</title>
440 font-family: sans-serif
442 span.sched-class-name {
444 font-family: monospace;
447 font-family: monospace;
450 font-family: monospace;
457 border-collapse: collapse;
459 table, table tr,td,th {
460 border: 1px solid #444;
465 list-style-type: none;
467 table.sched-class-clusters td {
471 padding-bottom: 10px;
473 table.sched-class-desc td {
480 font-family: monospace;
485 tr.good-cluster td.measurement {
488 tr.bad-cluster td.measurement {
491 tr.good-cluster td.measurement span.minmax {
494 tr.bad-cluster td.measurement span.minmax {
502 llvm::Error
Analysis::run
<Analysis::PrintSchedClassInconsistencies
>(
503 llvm::raw_ostream
&OS
) const {
504 const auto &FirstPoint
= Clustering_
.getPoints()[0];
506 OS
<< "<!DOCTYPE html><html>" << kHtmlHead
<< "<body>";
507 OS
<< "<h1><span class=\"mono\">llvm-exegesis</span> Analysis Results</h1>";
508 OS
<< "<h3>Triple: <span class=\"mono\">";
509 writeEscaped
<kEscapeHtml
>(OS
, FirstPoint
.LLVMTriple
);
510 OS
<< "</span></h3><h3>Cpu: <span class=\"mono\">";
511 writeEscaped
<kEscapeHtml
>(OS
, FirstPoint
.CpuName
);
512 OS
<< "</span></h3>";
514 for (const auto &RSCAndPoints
: makePointsPerSchedClass()) {
515 if (!RSCAndPoints
.RSC
.SCDesc
)
517 // Bucket sched class points into sched class clusters.
518 std::vector
<SchedClassCluster
> SchedClassClusters
;
519 for (const size_t PointId
: RSCAndPoints
.PointIds
) {
520 const auto &ClusterId
= Clustering_
.getClusterIdForPoint(PointId
);
521 if (!ClusterId
.isValid())
522 continue; // Ignore noise and errors. FIXME: take noise into account ?
523 if (ClusterId
.isUnstable() ^ AnalysisDisplayUnstableOpcodes_
)
524 continue; // Either display stable or unstable clusters only.
525 auto SchedClassClusterIt
=
526 std::find_if(SchedClassClusters
.begin(), SchedClassClusters
.end(),
527 [ClusterId
](const SchedClassCluster
&C
) {
528 return C
.id() == ClusterId
;
530 if (SchedClassClusterIt
== SchedClassClusters
.end()) {
531 SchedClassClusters
.emplace_back();
532 SchedClassClusterIt
= std::prev(SchedClassClusters
.end());
534 SchedClassClusterIt
->addPoint(PointId
, Clustering_
);
537 // Print any scheduling class that has at least one cluster that does not
538 // match the checked-in data.
539 if (llvm::all_of(SchedClassClusters
,
540 [this, &RSCAndPoints
](const SchedClassCluster
&C
) {
541 return C
.measurementsMatch(
542 *SubtargetInfo_
, RSCAndPoints
.RSC
, Clustering_
,
543 AnalysisInconsistencyEpsilonSquared_
);
545 continue; // Nothing weird.
547 OS
<< "<div class=\"inconsistency\"><p>Sched Class <span "
548 "class=\"sched-class-name\">";
549 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
550 writeEscaped
<kEscapeHtml
>(OS
, RSCAndPoints
.RSC
.SCDesc
->Name
);
552 OS
<< RSCAndPoints
.RSC
.SchedClassId
;
554 OS
<< "</span> contains instructions whose performance characteristics do"
555 " not match that of LLVM:</p>";
556 printSchedClassClustersHtml(SchedClassClusters
, RSCAndPoints
.RSC
, OS
);
557 OS
<< "<p>llvm SchedModel data:</p>";
558 printSchedClassDescHtml(RSCAndPoints
.RSC
, OS
);
562 OS
<< "</body></html>";
563 return llvm::Error::success();
566 } // namespace exegesis