1 //===-- Analysis.cpp --------------------------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "Analysis.h" 11 #include "BenchmarkResult.h" 12 #include "llvm/ADT/STLExtras.h" 13 #include "llvm/MC/MCAsmInfo.h" 14 #include "llvm/Support/FormatVariadic.h" 15 #include <unordered_set> 16 #include <vector> 17 18 namespace exegesis { 19 20 static const char kCsvSep = ','; 21 22 namespace { 23 24 enum EscapeTag { kEscapeCsv, kEscapeHtml, kEscapeHtmlString }; 25 26 template <EscapeTag Tag> 27 void writeEscaped(llvm::raw_ostream &OS, const llvm::StringRef S); 28 29 template <> 30 void writeEscaped<kEscapeCsv>(llvm::raw_ostream &OS, const llvm::StringRef S) { 31 if (std::find(S.begin(), S.end(), kCsvSep) == S.end()) { 32 OS << S; 33 } else { 34 // Needs escaping. 35 OS << '"'; 36 for (const char C : S) { 37 if (C == '"') 38 OS << "\"\""; 39 else 40 OS << C; 41 } 42 OS << '"'; 43 } 44 } 45 46 template <> 47 void writeEscaped<kEscapeHtml>(llvm::raw_ostream &OS, const llvm::StringRef S) { 48 for (const char C : S) { 49 if (C == '<') 50 OS << "<"; 51 else if (C == '>') 52 OS << ">"; 53 else if (C == '&') 54 OS << "&"; 55 else 56 OS << C; 57 } 58 } 59 60 template <> 61 void writeEscaped<kEscapeHtmlString>(llvm::raw_ostream &OS, 62 const llvm::StringRef S) { 63 for (const char C : S) { 64 if (C == '"') 65 OS << "\\\""; 66 else 67 OS << C; 68 } 69 } 70 71 } // namespace 72 73 template <EscapeTag Tag> 74 static void 75 writeClusterId(llvm::raw_ostream &OS, 76 const InstructionBenchmarkClustering::ClusterId &CID) { 77 if (CID.isNoise()) 78 writeEscaped<Tag>(OS, "[noise]"); 79 else if (CID.isError()) 80 writeEscaped<Tag>(OS, "[error]"); 81 else 82 OS << CID.getId(); 83 } 84 85 template <EscapeTag Tag> 86 static void writeMeasurementValue(llvm::raw_ostream &OS, const double Value) { 87 writeEscaped<Tag>(OS, llvm::formatv("{0:F}", Value).str()); 88 } 89 90 template <typename EscapeTag, EscapeTag Tag> 91 void Analysis::writeSnippet(llvm::raw_ostream &OS, 92 llvm::ArrayRef<uint8_t> Bytes, 93 const char *Separator) const { 94 llvm::SmallVector<std::string, 3> Lines; 95 // Parse the asm snippet and print it. 96 while (!Bytes.empty()) { 97 llvm::MCInst MI; 98 uint64_t MISize = 0; 99 if (!Disasm_->getInstruction(MI, MISize, Bytes, 0, llvm::nulls(), 100 llvm::nulls())) { 101 writeEscaped<Tag>(OS, llvm::join(Lines, Separator)); 102 writeEscaped<Tag>(OS, Separator); 103 writeEscaped<Tag>(OS, "[error decoding asm snippet]"); 104 return; 105 } 106 Lines.emplace_back(); 107 std::string &Line = Lines.back(); 108 llvm::raw_string_ostream OSS(Line); 109 InstPrinter_->printInst(&MI, OSS, "", *SubtargetInfo_); 110 Bytes = Bytes.drop_front(MISize); 111 OSS.flush(); 112 Line = llvm::StringRef(Line).trim().str(); 113 } 114 writeEscaped<Tag>(OS, llvm::join(Lines, Separator)); 115 } 116 117 // Prints a row representing an instruction, along with scheduling info and 118 // point coordinates (measurements). 119 void Analysis::printInstructionRowCsv(const size_t PointId, 120 llvm::raw_ostream &OS) const { 121 const InstructionBenchmark &Point = Clustering_.getPoints()[PointId]; 122 writeClusterId<kEscapeCsv>(OS, Clustering_.getClusterIdForPoint(PointId)); 123 OS << kCsvSep; 124 writeSnippet<EscapeTag, kEscapeCsv>(OS, Point.AssembledSnippet, "; "); 125 OS << kCsvSep; 126 writeEscaped<kEscapeCsv>(OS, Point.Key.Config); 127 OS << kCsvSep; 128 assert(!Point.Key.Instructions.empty()); 129 // FIXME: Resolve variant classes. 130 const unsigned SchedClassId = 131 InstrInfo_->get(Point.Key.Instructions[0].getOpcode()).getSchedClass(); 132 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 133 const auto &SchedModel = SubtargetInfo_->getSchedModel(); 134 const llvm::MCSchedClassDesc *const SCDesc = 135 SchedModel.getSchedClassDesc(SchedClassId); 136 writeEscaped<kEscapeCsv>(OS, SCDesc->Name); 137 #else 138 OS << SchedClassId; 139 #endif 140 for (const auto &Measurement : Point.Measurements) { 141 OS << kCsvSep; 142 writeMeasurementValue<kEscapeCsv>(OS, Measurement.PerInstructionValue); 143 } 144 OS << "\n"; 145 } 146 147 Analysis::Analysis(const llvm::Target &Target, 148 const InstructionBenchmarkClustering &Clustering) 149 : Clustering_(Clustering) { 150 if (Clustering.getPoints().empty()) 151 return; 152 153 const InstructionBenchmark &FirstPoint = Clustering.getPoints().front(); 154 InstrInfo_.reset(Target.createMCInstrInfo()); 155 RegInfo_.reset(Target.createMCRegInfo(FirstPoint.LLVMTriple)); 156 AsmInfo_.reset(Target.createMCAsmInfo(*RegInfo_, FirstPoint.LLVMTriple)); 157 SubtargetInfo_.reset(Target.createMCSubtargetInfo(FirstPoint.LLVMTriple, 158 FirstPoint.CpuName, "")); 159 InstPrinter_.reset(Target.createMCInstPrinter( 160 llvm::Triple(FirstPoint.LLVMTriple), 0 /*default variant*/, *AsmInfo_, 161 *InstrInfo_, *RegInfo_)); 162 163 Context_ = llvm::make_unique<llvm::MCContext>(AsmInfo_.get(), RegInfo_.get(), 164 &ObjectFileInfo_); 165 Disasm_.reset(Target.createMCDisassembler(*SubtargetInfo_, *Context_)); 166 assert(Disasm_ && "cannot create MCDisassembler. missing call to " 167 "InitializeXXXTargetDisassembler ?"); 168 } 169 170 template <> 171 llvm::Error 172 Analysis::run<Analysis::PrintClusters>(llvm::raw_ostream &OS) const { 173 if (Clustering_.getPoints().empty()) 174 return llvm::Error::success(); 175 176 // Write the header. 177 OS << "cluster_id" << kCsvSep << "opcode_name" << kCsvSep << "config" 178 << kCsvSep << "sched_class"; 179 for (const auto &Measurement : Clustering_.getPoints().front().Measurements) { 180 OS << kCsvSep; 181 writeEscaped<kEscapeCsv>(OS, Measurement.Key); 182 } 183 OS << "\n"; 184 185 // Write the points. 186 const auto &Clusters = Clustering_.getValidClusters(); 187 for (size_t I = 0, E = Clusters.size(); I < E; ++I) { 188 for (const size_t PointId : Clusters[I].PointIndices) { 189 printInstructionRowCsv(PointId, OS); 190 } 191 OS << "\n\n"; 192 } 193 return llvm::Error::success(); 194 } 195 196 std::unordered_map<unsigned, std::vector<size_t>> 197 Analysis::makePointsPerSchedClass() const { 198 std::unordered_map<unsigned, std::vector<size_t>> PointsPerSchedClass; 199 const auto &Points = Clustering_.getPoints(); 200 for (size_t PointId = 0, E = Points.size(); PointId < E; ++PointId) { 201 const InstructionBenchmark &Point = Points[PointId]; 202 if (!Point.Error.empty()) 203 continue; 204 assert(!Point.Key.Instructions.empty()); 205 const auto Opcode = Point.Key.Instructions[0].getOpcode(); 206 // FIXME: Resolve variant classes. 207 PointsPerSchedClass[InstrInfo_->get(Opcode).getSchedClass()].push_back( 208 PointId); 209 } 210 return PointsPerSchedClass; 211 } 212 213 // Uops repeat the same opcode over again. Just show this opcode and show the 214 // whole snippet only on hover. 215 static void writeUopsSnippetHtml(llvm::raw_ostream &OS, 216 const std::vector<llvm::MCInst> &Instructions, 217 const llvm::MCInstrInfo &InstrInfo) { 218 if (Instructions.empty()) 219 return; 220 writeEscaped<kEscapeHtml>(OS, InstrInfo.getName(Instructions[0].getOpcode())); 221 if (Instructions.size() > 1) 222 OS << " (x" << Instructions.size() << ")"; 223 } 224 225 // Latency tries to find a serial path. Just show the opcode path and show the 226 // whole snippet only on hover. 227 static void 228 writeLatencySnippetHtml(llvm::raw_ostream &OS, 229 const std::vector<llvm::MCInst> &Instructions, 230 const llvm::MCInstrInfo &InstrInfo) { 231 bool First = true; 232 for (const llvm::MCInst &Instr : Instructions) { 233 if (First) 234 First = false; 235 else 236 OS << " → "; 237 writeEscaped<kEscapeHtml>(OS, InstrInfo.getName(Instr.getOpcode())); 238 } 239 } 240 241 void Analysis::printSchedClassClustersHtml( 242 const std::vector<SchedClassCluster> &Clusters, const SchedClass &SC, 243 llvm::raw_ostream &OS) const { 244 const auto &Points = Clustering_.getPoints(); 245 OS << "<table class=\"sched-class-clusters\">"; 246 OS << "<tr><th>ClusterId</th><th>Opcode/Config</th>"; 247 assert(!Clusters.empty()); 248 for (const auto &Measurement : 249 Points[Clusters[0].getPointIds()[0]].Measurements) { 250 OS << "<th>"; 251 writeEscaped<kEscapeHtml>(OS, Measurement.Key); 252 OS << "</th>"; 253 } 254 OS << "</tr>"; 255 for (const SchedClassCluster &Cluster : Clusters) { 256 OS << "<tr class=\"" 257 << (Cluster.measurementsMatch(*SubtargetInfo_, SC, Clustering_) 258 ? "good-cluster" 259 : "bad-cluster") 260 << "\"><td>"; 261 writeClusterId<kEscapeHtml>(OS, Cluster.id()); 262 OS << "</td><td><ul>"; 263 for (const size_t PointId : Cluster.getPointIds()) { 264 const auto &Point = Points[PointId]; 265 OS << "<li><span class=\"mono\" title=\""; 266 writeSnippet<EscapeTag, kEscapeHtmlString>(OS, Point.AssembledSnippet, 267 "\n"); 268 OS << "\">"; 269 switch (Point.Mode) { 270 case InstructionBenchmark::Latency: 271 writeLatencySnippetHtml(OS, Point.Key.Instructions, *InstrInfo_); 272 break; 273 case InstructionBenchmark::Uops: 274 writeUopsSnippetHtml(OS, Point.Key.Instructions, *InstrInfo_); 275 break; 276 default: 277 llvm_unreachable("invalid mode"); 278 } 279 OS << "</span> <span class=\"mono\">"; 280 writeEscaped<kEscapeHtml>(OS, Point.Key.Config); 281 OS << "</span></li>"; 282 } 283 OS << "</ul></td>"; 284 for (const auto &Stats : Cluster.getRepresentative()) { 285 OS << "<td class=\"measurement\">"; 286 writeMeasurementValue<kEscapeHtml>(OS, Stats.avg()); 287 OS << "<br><span class=\"minmax\">["; 288 writeMeasurementValue<kEscapeHtml>(OS, Stats.min()); 289 OS << ";"; 290 writeMeasurementValue<kEscapeHtml>(OS, Stats.max()); 291 OS << "]</span></td>"; 292 } 293 OS << "</tr>"; 294 } 295 OS << "</table>"; 296 } 297 298 // Return the non-redundant list of WriteProcRes used by the given sched class. 299 // The scheduling model for LLVM is such that each instruction has a certain 300 // number of uops which consume resources which are described by WriteProcRes 301 // entries. Each entry describe how many cycles are spent on a specific ProcRes 302 // kind. 303 // For example, an instruction might have 3 uOps, one dispatching on P0 304 // (ProcResIdx=1) and two on P06 (ProcResIdx = 7). 305 // Note that LLVM additionally denormalizes resource consumption to include 306 // usage of super resources by subresources. So in practice if there exists a 307 // P016 (ProcResIdx=10), then the cycles consumed by P0 are also consumed by 308 // P06 (ProcResIdx = 7) and P016 (ProcResIdx = 10), and the resources consumed 309 // by P06 are also consumed by P016. In the figure below, parenthesized cycles 310 // denote implied usage of superresources by subresources: 311 // P0 P06 P016 312 // uOp1 1 (1) (1) 313 // uOp2 1 (1) 314 // uOp3 1 (1) 315 // ============================= 316 // 1 3 3 317 // Eventually we end up with three entries for the WriteProcRes of the 318 // instruction: 319 // {ProcResIdx=1, Cycles=1} // P0 320 // {ProcResIdx=7, Cycles=3} // P06 321 // {ProcResIdx=10, Cycles=3} // P016 322 // 323 // Note that in this case, P016 does not contribute any cycles, so it would 324 // be removed by this function. 325 // FIXME: Move this to MCSubtargetInfo and use it in llvm-mca. 326 static llvm::SmallVector<llvm::MCWriteProcResEntry, 8> 327 getNonRedundantWriteProcRes(const llvm::MCSchedClassDesc &SCDesc, 328 const llvm::MCSubtargetInfo &STI) { 329 llvm::SmallVector<llvm::MCWriteProcResEntry, 8> Result; 330 const auto &SM = STI.getSchedModel(); 331 const unsigned NumProcRes = SM.getNumProcResourceKinds(); 332 333 // This assumes that the ProcResDescs are sorted in topological order, which 334 // is guaranteed by the tablegen backend. 335 llvm::SmallVector<float, 32> ProcResUnitUsage(NumProcRes); 336 for (const auto *WPR = STI.getWriteProcResBegin(&SCDesc), 337 *const WPREnd = STI.getWriteProcResEnd(&SCDesc); 338 WPR != WPREnd; ++WPR) { 339 const llvm::MCProcResourceDesc *const ProcResDesc = 340 SM.getProcResource(WPR->ProcResourceIdx); 341 if (ProcResDesc->SubUnitsIdxBegin == nullptr) { 342 // This is a ProcResUnit. 343 Result.push_back({WPR->ProcResourceIdx, WPR->Cycles}); 344 ProcResUnitUsage[WPR->ProcResourceIdx] += WPR->Cycles; 345 } else { 346 // This is a ProcResGroup. First see if it contributes any cycles or if 347 // it has cycles just from subunits. 348 float RemainingCycles = WPR->Cycles; 349 for (const auto *SubResIdx = ProcResDesc->SubUnitsIdxBegin; 350 SubResIdx != ProcResDesc->SubUnitsIdxBegin + ProcResDesc->NumUnits; 351 ++SubResIdx) { 352 RemainingCycles -= ProcResUnitUsage[*SubResIdx]; 353 } 354 if (RemainingCycles < 0.01f) { 355 // The ProcResGroup contributes no cycles of its own. 356 continue; 357 } 358 // The ProcResGroup contributes `RemainingCycles` cycles of its own. 359 Result.push_back({WPR->ProcResourceIdx, 360 static_cast<uint16_t>(std::round(RemainingCycles))}); 361 // Spread the remaining cycles over all subunits. 362 for (const auto *SubResIdx = ProcResDesc->SubUnitsIdxBegin; 363 SubResIdx != ProcResDesc->SubUnitsIdxBegin + ProcResDesc->NumUnits; 364 ++SubResIdx) { 365 ProcResUnitUsage[*SubResIdx] += RemainingCycles / ProcResDesc->NumUnits; 366 } 367 } 368 } 369 return Result; 370 } 371 372 Analysis::SchedClass::SchedClass(const llvm::MCSchedClassDesc &SD, 373 const llvm::MCSubtargetInfo &STI) 374 : SCDesc(&SD), 375 NonRedundantWriteProcRes(getNonRedundantWriteProcRes(SD, STI)), 376 IdealizedProcResPressure(computeIdealizedProcResPressure( 377 STI.getSchedModel(), NonRedundantWriteProcRes)) {} 378 379 void Analysis::SchedClassCluster::addPoint( 380 size_t PointId, const InstructionBenchmarkClustering &Clustering) { 381 PointIds.push_back(PointId); 382 const auto &Point = Clustering.getPoints()[PointId]; 383 if (ClusterId.isUndef()) { 384 ClusterId = Clustering.getClusterIdForPoint(PointId); 385 Representative.resize(Point.Measurements.size()); 386 } 387 for (size_t I = 0, E = Point.Measurements.size(); I < E; ++I) { 388 Representative[I].push(Point.Measurements[I]); 389 } 390 assert(ClusterId == Clustering.getClusterIdForPoint(PointId)); 391 } 392 393 bool Analysis::SchedClassCluster::measurementsMatch( 394 const llvm::MCSubtargetInfo &STI, const SchedClass &SC, 395 const InstructionBenchmarkClustering &Clustering) const { 396 const size_t NumMeasurements = Representative.size(); 397 std::vector<BenchmarkMeasure> ClusterCenterPoint(NumMeasurements); 398 std::vector<BenchmarkMeasure> SchedClassPoint(NumMeasurements); 399 // Latency case. 400 assert(!Clustering.getPoints().empty()); 401 const InstructionBenchmark::ModeE Mode = Clustering.getPoints()[0].Mode; 402 if (Mode == InstructionBenchmark::Latency) { 403 if (NumMeasurements != 1) { 404 llvm::errs() 405 << "invalid number of measurements in latency mode: expected 1, got " 406 << NumMeasurements << "\n"; 407 return false; 408 } 409 // Find the latency. 410 SchedClassPoint[0].PerInstructionValue = 0.0; 411 for (unsigned I = 0; I < SC.SCDesc->NumWriteLatencyEntries; ++I) { 412 const llvm::MCWriteLatencyEntry *const WLE = 413 STI.getWriteLatencyEntry(SC.SCDesc, I); 414 SchedClassPoint[0].PerInstructionValue = 415 std::max<double>(SchedClassPoint[0].PerInstructionValue, WLE->Cycles); 416 } 417 ClusterCenterPoint[0].PerInstructionValue = Representative[0].avg(); 418 } else if (Mode == InstructionBenchmark::Uops) { 419 for (int I = 0, E = Representative.size(); I < E; ++I) { 420 // Find the pressure on ProcResIdx `Key`. 421 uint16_t ProcResIdx = 0; 422 if (!llvm::to_integer(Representative[I].key(), ProcResIdx, 10)) { 423 llvm::errs() << "expected ProcResIdx key, got " 424 << Representative[I].key() << "\n"; 425 return false; 426 } 427 const auto ProcResPressureIt = 428 std::find_if(SC.IdealizedProcResPressure.begin(), 429 SC.IdealizedProcResPressure.end(), 430 [ProcResIdx](const std::pair<uint16_t, float> &WPR) { 431 return WPR.first == ProcResIdx; 432 }); 433 SchedClassPoint[I].PerInstructionValue = 434 ProcResPressureIt == SC.IdealizedProcResPressure.end() 435 ? 0.0 436 : ProcResPressureIt->second; 437 ClusterCenterPoint[I].PerInstructionValue = Representative[I].avg(); 438 } 439 } else { 440 llvm::errs() << "unimplemented measurement matching for mode " << Mode 441 << "\n"; 442 return false; 443 } 444 return Clustering.isNeighbour(ClusterCenterPoint, SchedClassPoint); 445 } 446 447 void Analysis::printSchedClassDescHtml(const SchedClass &SC, 448 llvm::raw_ostream &OS) const { 449 OS << "<table class=\"sched-class-desc\">"; 450 OS << "<tr><th>Valid</th><th>Variant</th><th>uOps</th><th>Latency</" 451 "th><th>WriteProcRes</th><th title=\"This is the idealized unit " 452 "resource (port) pressure assuming ideal distribution\">Idealized " 453 "Resource Pressure</th></tr>"; 454 if (SC.SCDesc->isValid()) { 455 const auto &SM = SubtargetInfo_->getSchedModel(); 456 OS << "<tr><td>✔</td>"; 457 OS << "<td>" << (SC.SCDesc->isVariant() ? "✔" : "✕") 458 << "</td>"; 459 OS << "<td>" << SC.SCDesc->NumMicroOps << "</td>"; 460 // Latencies. 461 OS << "<td><ul>"; 462 for (int I = 0, E = SC.SCDesc->NumWriteLatencyEntries; I < E; ++I) { 463 const auto *const Entry = 464 SubtargetInfo_->getWriteLatencyEntry(SC.SCDesc, I); 465 OS << "<li>" << Entry->Cycles; 466 if (SC.SCDesc->NumWriteLatencyEntries > 1) { 467 // Dismabiguate if more than 1 latency. 468 OS << " (WriteResourceID " << Entry->WriteResourceID << ")"; 469 } 470 OS << "</li>"; 471 } 472 OS << "</ul></td>"; 473 // WriteProcRes. 474 OS << "<td><ul>"; 475 for (const auto &WPR : SC.NonRedundantWriteProcRes) { 476 OS << "<li><span class=\"mono\">"; 477 writeEscaped<kEscapeHtml>(OS, 478 SM.getProcResource(WPR.ProcResourceIdx)->Name); 479 OS << "</span>: " << WPR.Cycles << "</li>"; 480 } 481 OS << "</ul></td>"; 482 // Idealized port pressure. 483 OS << "<td><ul>"; 484 for (const auto &Pressure : SC.IdealizedProcResPressure) { 485 OS << "<li><span class=\"mono\">"; 486 writeEscaped<kEscapeHtml>(OS, SubtargetInfo_->getSchedModel() 487 .getProcResource(Pressure.first) 488 ->Name); 489 OS << "</span>: "; 490 writeMeasurementValue<kEscapeHtml>(OS, Pressure.second); 491 OS << "</li>"; 492 } 493 OS << "</ul></td>"; 494 OS << "</tr>"; 495 } else { 496 OS << "<tr><td>✕</td><td></td><td></td></tr>"; 497 } 498 OS << "</table>"; 499 } 500 501 static constexpr const char kHtmlHead[] = R"( 502 <head> 503 <title>llvm-exegesis Analysis Results</title> 504 <style> 505 body { 506 font-family: sans-serif 507 } 508 span.sched-class-name { 509 font-weight: bold; 510 font-family: monospace; 511 } 512 span.opcode { 513 font-family: monospace; 514 } 515 span.config { 516 font-family: monospace; 517 } 518 div.inconsistency { 519 margin-top: 50px; 520 } 521 table { 522 margin-left: 50px; 523 border-collapse: collapse; 524 } 525 table, table tr,td,th { 526 border: 1px solid #444; 527 } 528 table ul { 529 padding-left: 0px; 530 margin: 0px; 531 list-style-type: none; 532 } 533 table.sched-class-clusters td { 534 padding-left: 10px; 535 padding-right: 10px; 536 padding-top: 10px; 537 padding-bottom: 10px; 538 } 539 table.sched-class-desc td { 540 padding-left: 10px; 541 padding-right: 10px; 542 padding-top: 2px; 543 padding-bottom: 2px; 544 } 545 span.mono { 546 font-family: monospace; 547 } 548 td.measurement { 549 text-align: center; 550 } 551 tr.good-cluster td.measurement { 552 color: #292 553 } 554 tr.bad-cluster td.measurement { 555 color: #922 556 } 557 tr.good-cluster td.measurement span.minmax { 558 color: #888; 559 } 560 tr.bad-cluster td.measurement span.minmax { 561 color: #888; 562 } 563 </style> 564 </head> 565 )"; 566 567 template <> 568 llvm::Error Analysis::run<Analysis::PrintSchedClassInconsistencies>( 569 llvm::raw_ostream &OS) const { 570 const auto &FirstPoint = Clustering_.getPoints()[0]; 571 // Print the header. 572 OS << "<!DOCTYPE html><html>" << kHtmlHead << "<body>"; 573 OS << "<h1><span class=\"mono\">llvm-exegesis</span> Analysis Results</h1>"; 574 OS << "<h3>Triple: <span class=\"mono\">"; 575 writeEscaped<kEscapeHtml>(OS, FirstPoint.LLVMTriple); 576 OS << "</span></h3><h3>Cpu: <span class=\"mono\">"; 577 writeEscaped<kEscapeHtml>(OS, FirstPoint.CpuName); 578 OS << "</span></h3>"; 579 580 for (const auto &SchedClassAndPoints : makePointsPerSchedClass()) { 581 const auto SchedClassId = SchedClassAndPoints.first; 582 const std::vector<size_t> &SchedClassPoints = SchedClassAndPoints.second; 583 const auto &SchedModel = SubtargetInfo_->getSchedModel(); 584 const llvm::MCSchedClassDesc *const SCDesc = 585 SchedModel.getSchedClassDesc(SchedClassId); 586 if (!SCDesc) 587 continue; 588 const SchedClass SC(*SCDesc, *SubtargetInfo_); 589 590 // Bucket sched class points into sched class clusters. 591 std::vector<SchedClassCluster> SchedClassClusters; 592 for (const size_t PointId : SchedClassPoints) { 593 const auto &ClusterId = Clustering_.getClusterIdForPoint(PointId); 594 if (!ClusterId.isValid()) 595 continue; // Ignore noise and errors. FIXME: take noise into account ? 596 auto SchedClassClusterIt = 597 std::find_if(SchedClassClusters.begin(), SchedClassClusters.end(), 598 [ClusterId](const SchedClassCluster &C) { 599 return C.id() == ClusterId; 600 }); 601 if (SchedClassClusterIt == SchedClassClusters.end()) { 602 SchedClassClusters.emplace_back(); 603 SchedClassClusterIt = std::prev(SchedClassClusters.end()); 604 } 605 SchedClassClusterIt->addPoint(PointId, Clustering_); 606 } 607 608 // Print any scheduling class that has at least one cluster that does not 609 // match the checked-in data. 610 if (std::all_of(SchedClassClusters.begin(), SchedClassClusters.end(), 611 [this, &SC](const SchedClassCluster &C) { 612 return C.measurementsMatch(*SubtargetInfo_, SC, 613 Clustering_); 614 })) 615 continue; // Nothing weird. 616 617 OS << "<div class=\"inconsistency\"><p>Sched Class <span " 618 "class=\"sched-class-name\">"; 619 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 620 writeEscaped<kEscapeHtml>(OS, SCDesc->Name); 621 #else 622 OS << SchedClassId; 623 #endif 624 OS << "</span> contains instructions whose performance characteristics do" 625 " not match that of LLVM:</p>"; 626 printSchedClassClustersHtml(SchedClassClusters, SC, OS); 627 OS << "<p>llvm SchedModel data:</p>"; 628 printSchedClassDescHtml(SC, OS); 629 OS << "</div>"; 630 } 631 632 OS << "</body></html>"; 633 return llvm::Error::success(); 634 } 635 636 // Distributes a pressure budget as evenly as possible on the provided subunits 637 // given the already existing port pressure distribution. 638 // 639 // The algorithm is as follows: while there is remaining pressure to 640 // distribute, find the subunits with minimal pressure, and distribute 641 // remaining pressure equally up to the pressure of the unit with 642 // second-to-minimal pressure. 643 // For example, let's assume we want to distribute 2*P1256 644 // (Subunits = [P1,P2,P5,P6]), and the starting DensePressure is: 645 // DensePressure = P0 P1 P2 P3 P4 P5 P6 P7 646 // 0.1 0.3 0.2 0.0 0.0 0.5 0.5 0.5 647 // RemainingPressure = 2.0 648 // We sort the subunits by pressure: 649 // Subunits = [(P2,p=0.2), (P1,p=0.3), (P5,p=0.5), (P6, p=0.5)] 650 // We'll first start by the subunits with minimal pressure, which are at 651 // the beginning of the sorted array. In this example there is one (P2). 652 // The subunit with second-to-minimal pressure is the next one in the 653 // array (P1). So we distribute 0.1 pressure to P2, and remove 0.1 cycles 654 // from the budget. 655 // Subunits = [(P2,p=0.3), (P1,p=0.3), (P5,p=0.5), (P5,p=0.5)] 656 // RemainingPressure = 1.9 657 // We repeat this process: distribute 0.2 pressure on each of the minimal 658 // P2 and P1, decrease budget by 2*0.2: 659 // Subunits = [(P2,p=0.5), (P1,p=0.5), (P5,p=0.5), (P5,p=0.5)] 660 // RemainingPressure = 1.5 661 // There are no second-to-minimal subunits so we just share the remaining 662 // budget (1.5 cycles) equally: 663 // Subunits = [(P2,p=0.875), (P1,p=0.875), (P5,p=0.875), (P5,p=0.875)] 664 // RemainingPressure = 0.0 665 // We stop as there is no remaining budget to distribute. 666 void distributePressure(float RemainingPressure, 667 llvm::SmallVector<uint16_t, 32> Subunits, 668 llvm::SmallVector<float, 32> &DensePressure) { 669 // Find the number of subunits with minimal pressure (they are at the 670 // front). 671 llvm::sort(Subunits, [&DensePressure](const uint16_t A, const uint16_t B) { 672 return DensePressure[A] < DensePressure[B]; 673 }); 674 const auto getPressureForSubunit = [&DensePressure, 675 &Subunits](size_t I) -> float & { 676 return DensePressure[Subunits[I]]; 677 }; 678 size_t NumMinimalSU = 1; 679 while (NumMinimalSU < Subunits.size() && 680 getPressureForSubunit(NumMinimalSU) == getPressureForSubunit(0)) { 681 ++NumMinimalSU; 682 } 683 while (RemainingPressure > 0.0f) { 684 if (NumMinimalSU == Subunits.size()) { 685 // All units are minimal, just distribute evenly and be done. 686 for (size_t I = 0; I < NumMinimalSU; ++I) { 687 getPressureForSubunit(I) += RemainingPressure / NumMinimalSU; 688 } 689 return; 690 } 691 // Distribute the remaining pressure equally. 692 const float MinimalPressure = getPressureForSubunit(NumMinimalSU - 1); 693 const float SecondToMinimalPressure = getPressureForSubunit(NumMinimalSU); 694 assert(MinimalPressure < SecondToMinimalPressure); 695 const float Increment = SecondToMinimalPressure - MinimalPressure; 696 if (RemainingPressure <= NumMinimalSU * Increment) { 697 // There is not enough remaining pressure. 698 for (size_t I = 0; I < NumMinimalSU; ++I) { 699 getPressureForSubunit(I) += RemainingPressure / NumMinimalSU; 700 } 701 return; 702 } 703 // Bump all minimal pressure subunits to `SecondToMinimalPressure`. 704 for (size_t I = 0; I < NumMinimalSU; ++I) { 705 getPressureForSubunit(I) = SecondToMinimalPressure; 706 RemainingPressure -= SecondToMinimalPressure; 707 } 708 while (NumMinimalSU < Subunits.size() && 709 getPressureForSubunit(NumMinimalSU) == SecondToMinimalPressure) { 710 ++NumMinimalSU; 711 } 712 } 713 } 714 715 std::vector<std::pair<uint16_t, float>> computeIdealizedProcResPressure( 716 const llvm::MCSchedModel &SM, 717 llvm::SmallVector<llvm::MCWriteProcResEntry, 8> WPRS) { 718 // DensePressure[I] is the port pressure for Proc Resource I. 719 llvm::SmallVector<float, 32> DensePressure(SM.getNumProcResourceKinds()); 720 llvm::sort(WPRS, [](const llvm::MCWriteProcResEntry &A, 721 const llvm::MCWriteProcResEntry &B) { 722 return A.ProcResourceIdx < B.ProcResourceIdx; 723 }); 724 for (const llvm::MCWriteProcResEntry &WPR : WPRS) { 725 // Get units for the entry. 726 const llvm::MCProcResourceDesc *const ProcResDesc = 727 SM.getProcResource(WPR.ProcResourceIdx); 728 if (ProcResDesc->SubUnitsIdxBegin == nullptr) { 729 // This is a ProcResUnit. 730 DensePressure[WPR.ProcResourceIdx] += WPR.Cycles; 731 } else { 732 // This is a ProcResGroup. 733 llvm::SmallVector<uint16_t, 32> Subunits(ProcResDesc->SubUnitsIdxBegin, 734 ProcResDesc->SubUnitsIdxBegin + 735 ProcResDesc->NumUnits); 736 distributePressure(WPR.Cycles, Subunits, DensePressure); 737 } 738 } 739 // Turn dense pressure into sparse pressure by removing zero entries. 740 std::vector<std::pair<uint16_t, float>> Pressure; 741 for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) { 742 if (DensePressure[I] > 0.0f) 743 Pressure.emplace_back(I, DensePressure[I]); 744 } 745 return Pressure; 746 } 747 748 } // namespace exegesis 749