[InstCombine] Signed saturation patterns
[llvm-core.git] / tools / llvm-exegesis / lib / Analysis.cpp
blob0fa0767b71d80790f2cf3794a26bc7af0e214939
1 //===-- Analysis.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 //===----------------------------------------------------------------------===//
9 #include "Analysis.h"
10 #include "BenchmarkResult.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/MC/MCAsmInfo.h"
13 #include "llvm/Support/FormatVariadic.h"
14 #include <limits>
15 #include <unordered_set>
16 #include <vector>
18 namespace llvm {
19 namespace exegesis {
21 static const char kCsvSep = ',';
23 namespace {
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()) {
31 OS << S;
32 } else {
33 // Needs escaping.
34 OS << '"';
35 for (const char C : S) {
36 if (C == '"')
37 OS << "\"\"";
38 else
39 OS << C;
41 OS << '"';
45 template <> void writeEscaped<kEscapeHtml>(raw_ostream &OS, const StringRef S) {
46 for (const char C : S) {
47 if (C == '<')
48 OS << "&lt;";
49 else if (C == '>')
50 OS << "&gt;";
51 else if (C == '&')
52 OS << "&amp;";
53 else
54 OS << C;
58 template <>
59 void writeEscaped<kEscapeHtmlString>(raw_ostream &OS, const StringRef S) {
60 for (const char C : S) {
61 if (C == '"')
62 OS << "\\\"";
63 else
64 OS << C;
68 } // namespace
70 template <EscapeTag Tag>
71 static void
72 writeClusterId(raw_ostream &OS,
73 const InstructionBenchmarkClustering::ClusterId &CID) {
74 if (CID.isNoise())
75 writeEscaped<Tag>(OS, "[noise]");
76 else if (CID.isError())
77 writeEscaped<Tag>(OS, "[error]");
78 else
79 OS << CID.getId();
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}");
96 writeEscaped<Tag>(
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()) {
106 MCInst MI;
107 uint64_t MISize = 0;
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]");
112 return;
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));
129 OS << kCsvSep;
130 writeSnippet<EscapeTag, kEscapeCsv>(OS, Point.AssembledSnippet, "; ");
131 OS << kCsvSep;
132 writeEscaped<kEscapeCsv>(OS, Point.Key.Config);
133 OS << kCsvSep;
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);
143 #else
144 OS << SchedClassId;
145 #endif
146 for (const auto &Measurement : Point.Measurements) {
147 OS << kCsvSep;
148 writeMeasurementValue<kEscapeCsv>(OS, Measurement.PerInstructionValue);
150 OS << "\n";
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())
162 return;
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(),
174 &ObjectFileInfo_);
175 Disasm_.reset(Target.createMCDisassembler(*SubtargetInfo_, *Context_));
176 assert(Disasm_ && "cannot create MCDisassembler. missing call to "
177 "InitializeXXXTargetDisassembler ?");
180 template <>
181 Error Analysis::run<Analysis::PrintClusters>(raw_ostream &OS) const {
182 if (Clustering_.getPoints().empty())
183 return Error::success();
185 // Write the header.
186 OS << "cluster_id" << kCsvSep << "opcode_name" << kCsvSep << "config"
187 << kCsvSep << "sched_class";
188 for (const auto &Measurement : Clustering_.getPoints().front().Measurements) {
189 OS << kCsvSep;
190 writeEscaped<kEscapeCsv>(OS, Measurement.Key);
192 OS << "\n";
194 // Write the points.
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);
200 OS << "\n\n";
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())
218 continue;
219 assert(!Point.Key.Instructions.empty());
220 // FIXME: we should be using the tuple of classes for instructions in the
221 // snippet as key.
222 const MCInst &MCI = Point.keyInstruction();
223 unsigned SchedClassId;
224 bool WasVariant;
225 std::tie(SchedClassId, WasVariant) =
226 ResolvedSchedClass::resolveSchedClassId(*SubtargetInfo_, *InstrInfo_,
227 MCI);
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));
236 } else {
237 // Append to the existing entry.
238 Entries[IndexIt->second].PointIds.push_back(PointId);
241 return Entries;
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())
250 return;
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) {
261 bool First = true;
262 for (const MCInst &Instr : Instructions) {
263 if (First)
264 First = false;
265 else
266 OS << " &rarr; ";
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");
275 OS << "\">";
276 switch (Point.Mode) {
277 case InstructionBenchmark::Latency:
278 writeLatencySnippetHtml(OS, Point.Key.Instructions, *InstrInfo_);
279 break;
280 case InstructionBenchmark::Uops:
281 case InstructionBenchmark::InverseThroughput:
282 writeUopsSnippetHtml(OS, Point.Key.Instructions, *InstrInfo_);
283 break;
284 default:
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) {
301 OS << "<th>";
302 writeEscaped<kEscapeHtml>(OS, Measurement.Key);
303 OS << "</th>";
305 OS << "</tr>";
306 for (const SchedClassCluster &Cluster : Clusters) {
307 OS << "<tr class=\""
308 << (Cluster.measurementsMatch(*SubtargetInfo_, RSC, Clustering_,
309 AnalysisInconsistencyEpsilonSquared_)
310 ? "good-cluster"
311 : "bad-cluster")
312 << "\"><td>";
313 writeClusterId<kEscapeHtml>(OS, Cluster.id());
314 OS << "</td><td><ul>";
315 for (const size_t PointId : Cluster.getPointIds()) {
316 printPointHtml(Points[PointId], OS);
318 OS << "</ul></td>";
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());
324 OS << ";";
325 writeMeasurementValue<kEscapeHtml>(OS, Stats.max());
326 OS << "]</span></td>";
328 OS << "</tr>";
330 OS << "</table>";
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))
352 return false;
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>&#10004;</td>";
379 OS << "<td>" << (RSC.WasVariant ? "&#10004;" : "&#10005;") << "</td>";
380 OS << "<td>" << RSC.SCDesc->NumMicroOps << "</td>";
381 // Latencies.
382 OS << "<td><ul>";
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 << ")";
391 OS << "</li>";
393 OS << "</ul></td>";
394 // inverse throughput.
395 OS << "<td>";
396 writeMeasurementValue<kEscapeHtml>(
398 MCSchedModel::getReciprocalThroughput(*SubtargetInfo_, *RSC.SCDesc));
399 OS << "</td>";
400 // WriteProcRes.
401 OS << "<td><ul>";
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>";
408 OS << "</ul></td>";
409 // Idealized port pressure.
410 OS << "<td><ul>";
411 for (const auto &Pressure : RSC.IdealizedProcResPressure) {
412 OS << "<li><span class=\"mono\">";
413 writeEscaped<kEscapeHtml>(OS, SubtargetInfo_->getSchedModel()
414 .getProcResource(Pressure.first)
415 ->Name);
416 OS << "</span>: ";
417 writeMeasurementValue<kEscapeHtml>(OS, Pressure.second);
418 OS << "</li>";
420 OS << "</ul></td>";
421 OS << "</tr>";
422 } else {
423 OS << "<tr><td>&#10005;</td><td></td><td></td></tr>";
425 OS << "</table>";
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())
434 return;
436 OS << "<div class=\"inconsistency\"><p>" << display_name << " Cluster ("
437 << Cluster.PointIndices.size() << " points)</p>";
438 OS << "<table class=\"sched-class-clusters\">";
439 // Table Header.
440 OS << "<tr><th>ClusterId</th><th>Opcode/Config</th>";
441 for (const auto &Measurement : Points[Cluster.PointIndices[0]].Measurements) {
442 OS << "<th>";
443 writeEscaped<kEscapeHtml>(OS, Measurement.Key);
444 OS << "</th>";
446 OS << "</tr>";
448 // Point data.
449 for (const auto &PointId : Cluster.PointIndices) {
450 OS << "<tr class=\"bad-cluster\"><td>" << display_name << "</td><td><ul>";
451 printPointHtml(Points[PointId], OS);
452 OS << "</ul></td>";
453 for (const auto &Measurement : Points[PointId].Measurements) {
454 OS << "<td class=\"measurement\">";
455 writeMeasurementValue<kEscapeHtml>(OS, Measurement.PerInstructionValue);
457 OS << "</tr>";
459 OS << "</table>";
461 OS << "</div>";
463 } // namespace exegesis
465 static constexpr const char kHtmlHead[] = R"(
466 <head>
467 <title>llvm-exegesis Analysis Results</title>
468 <style>
469 body {
470 font-family: sans-serif
472 span.sched-class-name {
473 font-weight: bold;
474 font-family: monospace;
476 span.opcode {
477 font-family: monospace;
479 span.config {
480 font-family: monospace;
482 div.inconsistency {
483 margin-top: 50px;
485 table {
486 margin-left: 50px;
487 border-collapse: collapse;
489 table, table tr,td,th {
490 border: 1px solid #444;
492 table ul {
493 padding-left: 0px;
494 margin: 0px;
495 list-style-type: none;
497 table.sched-class-clusters td {
498 padding-left: 10px;
499 padding-right: 10px;
500 padding-top: 10px;
501 padding-bottom: 10px;
503 table.sched-class-desc td {
504 padding-left: 10px;
505 padding-right: 10px;
506 padding-top: 2px;
507 padding-bottom: 2px;
509 span.mono {
510 font-family: monospace;
512 td.measurement {
513 text-align: center;
515 tr.good-cluster td.measurement {
516 color: #292
518 tr.bad-cluster td.measurement {
519 color: #922
521 tr.good-cluster td.measurement span.minmax {
522 color: #888;
524 tr.bad-cluster td.measurement span.minmax {
525 color: #888;
527 </style>
528 </head>
531 template <>
532 Error Analysis::run<Analysis::PrintSchedClassInconsistencies>(
533 raw_ostream &OS) const {
534 const auto &FirstPoint = Clustering_.getPoints()[0];
535 // Print the header.
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)
546 continue;
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,
572 Clustering_,
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);
581 #else
582 OS << RSCAndPoints.RSC.SchedClassId;
583 #endif
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);
589 OS << "</div>";
592 printClusterRawHtml(InstructionBenchmarkClustering::ClusterId::noise(),
593 "[noise]", OS);
595 OS << "</body></html>";
596 return Error::success();
599 } // namespace exegesis
600 } // namespace llvm