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 //===----------------------------------------------------------------------===// 8 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> 17 18 namespace llvm { 19 namespace exegesis { 20 21 static const char kCsvSep = ','; 22 23 namespace { 24 25 enum EscapeTag { kEscapeCsv, kEscapeHtml, kEscapeHtmlString }; 26 27 template <EscapeTag Tag> void writeEscaped(raw_ostream &OS, const StringRef S); 28 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; 40 } 41 OS << '"'; 42 } 43 } 44 45 template <> void writeEscaped<kEscapeHtml>(raw_ostream &OS, const StringRef S) { 46 for (const char C : S) { 47 if (C == '<') 48 OS << "<"; 49 else if (C == '>') 50 OS << ">"; 51 else if (C == '&') 52 OS << "&"; 53 else 54 OS << C; 55 } 56 } 57 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; 65 } 66 } 67 68 } // namespace 69 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(); 80 } 81 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; 92 93 // WARNING: when changing the format, also adjust the small-size estimate ^. 94 static constexpr StringLiteral SimpleFloatFormat = StringLiteral("{0:F}"); 95 96 writeEscaped<Tag>( 97 OS, formatv(SimpleFloatFormat.data(), Value).sstr<SerializationLen>()); 98 } 99 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; 113 } 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()); 119 } 120 writeEscaped<Tag>(OS, join(Lines, Separator)); 121 } 122 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); 149 } 150 OS << "\n"; 151 } 152 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; 163 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_)); 172 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 ?"); 178 } 179 180 template <> 181 Error Analysis::run<Analysis::PrintClusters>(raw_ostream &OS) const { 182 if (Clustering_.getPoints().empty()) 183 return Error::success(); 184 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); 191 } 192 OS << "\n"; 193 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); 199 } 200 OS << "\n\n"; 201 } 202 return Error::success(); 203 } 204 205 Analysis::ResolvedSchedClassAndPoints::ResolvedSchedClassAndPoints( 206 ResolvedSchedClass &&RSC) 207 : RSC(std::move(RSC)) {} 208 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); 239 } 240 } 241 return Entries; 242 } 243 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() << ")"; 254 } 255 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 << " → "; 267 writeEscaped<kEscapeHtml>(OS, InstrInfo.getName(Instr.getOpcode())); 268 } 269 } 270 271 void Analysis::printSchedClassClustersHtml( 272 const std::vector<SchedClassCluster> &Clusters, 273 const ResolvedSchedClass &RSC, raw_ostream &OS) const { 274 const auto &Points = Clustering_.getPoints(); 275 OS << "<table class=\"sched-class-clusters\">"; 276 OS << "<tr><th>ClusterId</th><th>Opcode/Config</th>"; 277 assert(!Clusters.empty()); 278 for (const auto &Measurement : 279 Points[Clusters[0].getPointIds()[0]].Measurements) { 280 OS << "<th>"; 281 writeEscaped<kEscapeHtml>(OS, Measurement.Key); 282 OS << "</th>"; 283 } 284 OS << "</tr>"; 285 for (const SchedClassCluster &Cluster : Clusters) { 286 OS << "<tr class=\"" 287 << (Cluster.measurementsMatch(*SubtargetInfo_, RSC, Clustering_, 288 AnalysisInconsistencyEpsilonSquared_) 289 ? "good-cluster" 290 : "bad-cluster") 291 << "\"><td>"; 292 writeClusterId<kEscapeHtml>(OS, Cluster.id()); 293 OS << "</td><td><ul>"; 294 for (const size_t PointId : Cluster.getPointIds()) { 295 const auto &Point = Points[PointId]; 296 OS << "<li><span class=\"mono\" title=\""; 297 writeSnippet<EscapeTag, kEscapeHtmlString>(OS, Point.AssembledSnippet, 298 "\n"); 299 OS << "\">"; 300 switch (Point.Mode) { 301 case InstructionBenchmark::Latency: 302 writeLatencySnippetHtml(OS, Point.Key.Instructions, *InstrInfo_); 303 break; 304 case InstructionBenchmark::Uops: 305 case InstructionBenchmark::InverseThroughput: 306 writeUopsSnippetHtml(OS, Point.Key.Instructions, *InstrInfo_); 307 break; 308 default: 309 llvm_unreachable("invalid mode"); 310 } 311 OS << "</span> <span class=\"mono\">"; 312 writeEscaped<kEscapeHtml>(OS, Point.Key.Config); 313 OS << "</span></li>"; 314 } 315 OS << "</ul></td>"; 316 for (const auto &Stats : Cluster.getCentroid().getStats()) { 317 OS << "<td class=\"measurement\">"; 318 writeMeasurementValue<kEscapeHtml>(OS, Stats.avg()); 319 OS << "<br><span class=\"minmax\">["; 320 writeMeasurementValue<kEscapeHtml>(OS, Stats.min()); 321 OS << ";"; 322 writeMeasurementValue<kEscapeHtml>(OS, Stats.max()); 323 OS << "]</span></td>"; 324 } 325 OS << "</tr>"; 326 } 327 OS << "</table>"; 328 } 329 330 void Analysis::SchedClassCluster::addPoint( 331 size_t PointId, const InstructionBenchmarkClustering &Clustering) { 332 PointIds.push_back(PointId); 333 const auto &Point = Clustering.getPoints()[PointId]; 334 if (ClusterId.isUndef()) 335 ClusterId = Clustering.getClusterIdForPoint(PointId); 336 assert(ClusterId == Clustering.getClusterIdForPoint(PointId)); 337 338 Centroid.addPoint(Point.Measurements); 339 } 340 341 bool Analysis::SchedClassCluster::measurementsMatch( 342 const MCSubtargetInfo &STI, const ResolvedSchedClass &RSC, 343 const InstructionBenchmarkClustering &Clustering, 344 const double AnalysisInconsistencyEpsilonSquared_) const { 345 assert(!Clustering.getPoints().empty()); 346 const InstructionBenchmark::ModeE Mode = Clustering.getPoints()[0].Mode; 347 348 if (!Centroid.validate(Mode)) 349 return false; 350 351 const std::vector<BenchmarkMeasure> ClusterCenterPoint = 352 Centroid.getAsPoint(); 353 354 const std::vector<BenchmarkMeasure> SchedClassPoint = 355 RSC.getAsPoint(Mode, STI, Centroid.getStats()); 356 if (SchedClassPoint.empty()) 357 return false; // In Uops mode validate() may not be enough. 358 359 assert(ClusterCenterPoint.size() == SchedClassPoint.size() && 360 "Expected measured/sched data dimensions to match."); 361 362 return Clustering.isNeighbour(ClusterCenterPoint, SchedClassPoint, 363 AnalysisInconsistencyEpsilonSquared_); 364 } 365 366 void Analysis::printSchedClassDescHtml(const ResolvedSchedClass &RSC, 367 raw_ostream &OS) const { 368 OS << "<table class=\"sched-class-desc\">"; 369 OS << "<tr><th>Valid</th><th>Variant</th><th>NumMicroOps</th><th>Latency</" 370 "th><th>RThroughput</th><th>WriteProcRes</th><th title=\"This is the " 371 "idealized unit resource (port) pressure assuming ideal " 372 "distribution\">Idealized Resource Pressure</th></tr>"; 373 if (RSC.SCDesc->isValid()) { 374 const auto &SM = SubtargetInfo_->getSchedModel(); 375 OS << "<tr><td>✔</td>"; 376 OS << "<td>" << (RSC.WasVariant ? "✔" : "✕") << "</td>"; 377 OS << "<td>" << RSC.SCDesc->NumMicroOps << "</td>"; 378 // Latencies. 379 OS << "<td><ul>"; 380 for (int I = 0, E = RSC.SCDesc->NumWriteLatencyEntries; I < E; ++I) { 381 const auto *const Entry = 382 SubtargetInfo_->getWriteLatencyEntry(RSC.SCDesc, I); 383 OS << "<li>" << Entry->Cycles; 384 if (RSC.SCDesc->NumWriteLatencyEntries > 1) { 385 // Dismabiguate if more than 1 latency. 386 OS << " (WriteResourceID " << Entry->WriteResourceID << ")"; 387 } 388 OS << "</li>"; 389 } 390 OS << "</ul></td>"; 391 // inverse throughput. 392 OS << "<td>"; 393 writeMeasurementValue<kEscapeHtml>( 394 OS, 395 MCSchedModel::getReciprocalThroughput(*SubtargetInfo_, *RSC.SCDesc)); 396 OS << "</td>"; 397 // WriteProcRes. 398 OS << "<td><ul>"; 399 for (const auto &WPR : RSC.NonRedundantWriteProcRes) { 400 OS << "<li><span class=\"mono\">"; 401 writeEscaped<kEscapeHtml>(OS, 402 SM.getProcResource(WPR.ProcResourceIdx)->Name); 403 OS << "</span>: " << WPR.Cycles << "</li>"; 404 } 405 OS << "</ul></td>"; 406 // Idealized port pressure. 407 OS << "<td><ul>"; 408 for (const auto &Pressure : RSC.IdealizedProcResPressure) { 409 OS << "<li><span class=\"mono\">"; 410 writeEscaped<kEscapeHtml>(OS, SubtargetInfo_->getSchedModel() 411 .getProcResource(Pressure.first) 412 ->Name); 413 OS << "</span>: "; 414 writeMeasurementValue<kEscapeHtml>(OS, Pressure.second); 415 OS << "</li>"; 416 } 417 OS << "</ul></td>"; 418 OS << "</tr>"; 419 } else { 420 OS << "<tr><td>✕</td><td></td><td></td></tr>"; 421 } 422 OS << "</table>"; 423 } 424 425 static constexpr const char kHtmlHead[] = R"( 426 <head> 427 <title>llvm-exegesis Analysis Results</title> 428 <style> 429 body { 430 font-family: sans-serif 431 } 432 span.sched-class-name { 433 font-weight: bold; 434 font-family: monospace; 435 } 436 span.opcode { 437 font-family: monospace; 438 } 439 span.config { 440 font-family: monospace; 441 } 442 div.inconsistency { 443 margin-top: 50px; 444 } 445 table { 446 margin-left: 50px; 447 border-collapse: collapse; 448 } 449 table, table tr,td,th { 450 border: 1px solid #444; 451 } 452 table ul { 453 padding-left: 0px; 454 margin: 0px; 455 list-style-type: none; 456 } 457 table.sched-class-clusters td { 458 padding-left: 10px; 459 padding-right: 10px; 460 padding-top: 10px; 461 padding-bottom: 10px; 462 } 463 table.sched-class-desc td { 464 padding-left: 10px; 465 padding-right: 10px; 466 padding-top: 2px; 467 padding-bottom: 2px; 468 } 469 span.mono { 470 font-family: monospace; 471 } 472 td.measurement { 473 text-align: center; 474 } 475 tr.good-cluster td.measurement { 476 color: #292 477 } 478 tr.bad-cluster td.measurement { 479 color: #922 480 } 481 tr.good-cluster td.measurement span.minmax { 482 color: #888; 483 } 484 tr.bad-cluster td.measurement span.minmax { 485 color: #888; 486 } 487 </style> 488 </head> 489 )"; 490 491 template <> 492 Error Analysis::run<Analysis::PrintSchedClassInconsistencies>( 493 raw_ostream &OS) const { 494 const auto &FirstPoint = Clustering_.getPoints()[0]; 495 // Print the header. 496 OS << "<!DOCTYPE html><html>" << kHtmlHead << "<body>"; 497 OS << "<h1><span class=\"mono\">llvm-exegesis</span> Analysis Results</h1>"; 498 OS << "<h3>Triple: <span class=\"mono\">"; 499 writeEscaped<kEscapeHtml>(OS, FirstPoint.LLVMTriple); 500 OS << "</span></h3><h3>Cpu: <span class=\"mono\">"; 501 writeEscaped<kEscapeHtml>(OS, FirstPoint.CpuName); 502 OS << "</span></h3>"; 503 504 for (const auto &RSCAndPoints : makePointsPerSchedClass()) { 505 if (!RSCAndPoints.RSC.SCDesc) 506 continue; 507 // Bucket sched class points into sched class clusters. 508 std::vector<SchedClassCluster> SchedClassClusters; 509 for (const size_t PointId : RSCAndPoints.PointIds) { 510 const auto &ClusterId = Clustering_.getClusterIdForPoint(PointId); 511 if (!ClusterId.isValid()) 512 continue; // Ignore noise and errors. FIXME: take noise into account ? 513 if (ClusterId.isUnstable() ^ AnalysisDisplayUnstableOpcodes_) 514 continue; // Either display stable or unstable clusters only. 515 auto SchedClassClusterIt = 516 std::find_if(SchedClassClusters.begin(), SchedClassClusters.end(), 517 [ClusterId](const SchedClassCluster &C) { 518 return C.id() == ClusterId; 519 }); 520 if (SchedClassClusterIt == SchedClassClusters.end()) { 521 SchedClassClusters.emplace_back(); 522 SchedClassClusterIt = std::prev(SchedClassClusters.end()); 523 } 524 SchedClassClusterIt->addPoint(PointId, Clustering_); 525 } 526 527 // Print any scheduling class that has at least one cluster that does not 528 // match the checked-in data. 529 if (all_of(SchedClassClusters, [this, 530 &RSCAndPoints](const SchedClassCluster &C) { 531 return C.measurementsMatch(*SubtargetInfo_, RSCAndPoints.RSC, 532 Clustering_, 533 AnalysisInconsistencyEpsilonSquared_); 534 })) 535 continue; // Nothing weird. 536 537 OS << "<div class=\"inconsistency\"><p>Sched Class <span " 538 "class=\"sched-class-name\">"; 539 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 540 writeEscaped<kEscapeHtml>(OS, RSCAndPoints.RSC.SCDesc->Name); 541 #else 542 OS << RSCAndPoints.RSC.SchedClassId; 543 #endif 544 OS << "</span> contains instructions whose performance characteristics do" 545 " not match that of LLVM:</p>"; 546 printSchedClassClustersHtml(SchedClassClusters, RSCAndPoints.RSC, OS); 547 OS << "<p>llvm SchedModel data:</p>"; 548 printSchedClassDescHtml(RSCAndPoints.RSC, OS); 549 OS << "</div>"; 550 } 551 552 OS << "</body></html>"; 553 return Error::success(); 554 } 555 556 } // namespace exegesis 557 } // namespace llvm 558