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/Support/FormatVariadic.h" 13 #include <unordered_set> 14 #include <vector> 15 16 namespace exegesis { 17 18 static const char kCsvSep = ','; 19 20 namespace { 21 22 enum EscapeTag { kEscapeCsv, kEscapeHtml }; 23 24 template <EscapeTag Tag> 25 void writeEscaped(llvm::raw_ostream &OS, const llvm::StringRef S); 26 27 template <> 28 void writeEscaped<kEscapeCsv>(llvm::raw_ostream &OS, const llvm::StringRef S) { 29 if (std::find(S.begin(), S.end(), kCsvSep) == S.end()) { 30 OS << S; 31 } else { 32 // Needs escaping. 33 OS << '"'; 34 for (const char C : S) { 35 if (C == '"') 36 OS << "\"\""; 37 else 38 OS << C; 39 } 40 OS << '"'; 41 } 42 } 43 44 template <> 45 void writeEscaped<kEscapeHtml>(llvm::raw_ostream &OS, const llvm::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 } // namespace 59 60 template <EscapeTag Tag> 61 static void 62 writeClusterId(llvm::raw_ostream &OS, 63 const InstructionBenchmarkClustering::ClusterId &CID) { 64 if (CID.isNoise()) 65 writeEscaped<Tag>(OS, "[noise]"); 66 else if (CID.isError()) 67 writeEscaped<Tag>(OS, "[error]"); 68 else 69 OS << CID.getId(); 70 } 71 72 template <EscapeTag Tag> 73 static void writeMeasurementValue(llvm::raw_ostream &OS, const double Value) { 74 writeEscaped<Tag>(OS, llvm::formatv("{0:F}", Value).str()); 75 } 76 77 // Prints a row representing an instruction, along with scheduling info and 78 // point coordinates (measurements). 79 void Analysis::printInstructionRowCsv(const size_t PointId, 80 llvm::raw_ostream &OS) const { 81 const InstructionBenchmark &Point = Clustering_.getPoints()[PointId]; 82 writeClusterId<kEscapeCsv>(OS, Clustering_.getClusterIdForPoint(PointId)); 83 OS << kCsvSep; 84 writeEscaped<kEscapeCsv>(OS, Point.Key.OpcodeName); 85 OS << kCsvSep; 86 writeEscaped<kEscapeCsv>(OS, Point.Key.Config); 87 OS << kCsvSep; 88 const auto OpcodeIt = MnemonicToOpcode_.find(Point.Key.OpcodeName); 89 if (OpcodeIt != MnemonicToOpcode_.end()) { 90 const unsigned SchedClassId = 91 InstrInfo_->get(OpcodeIt->second).getSchedClass(); 92 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 93 const auto &SchedModel = SubtargetInfo_->getSchedModel(); 94 const llvm::MCSchedClassDesc *const SCDesc = 95 SchedModel.getSchedClassDesc(SchedClassId); 96 writeEscaped<kEscapeCsv>(OS, SCDesc->Name); 97 #else 98 OS << SchedClassId; 99 #endif 100 } 101 // FIXME: Print the sched class once InstructionBenchmark separates key into 102 // (mnemonic, mode, opaque). 103 for (const auto &Measurement : Point.Measurements) { 104 OS << kCsvSep; 105 writeMeasurementValue<kEscapeCsv>(OS, Measurement.Value); 106 } 107 OS << "\n"; 108 } 109 110 Analysis::Analysis(const llvm::Target &Target, 111 const InstructionBenchmarkClustering &Clustering) 112 : Clustering_(Clustering) { 113 if (Clustering.getPoints().empty()) 114 return; 115 116 InstrInfo_.reset(Target.createMCInstrInfo()); 117 const InstructionBenchmark &FirstPoint = Clustering.getPoints().front(); 118 SubtargetInfo_.reset(Target.createMCSubtargetInfo(FirstPoint.LLVMTriple, 119 FirstPoint.CpuName, "")); 120 121 // Build an index of mnemonic->opcode. 122 for (int I = 0, E = InstrInfo_->getNumOpcodes(); I < E; ++I) 123 MnemonicToOpcode_.emplace(InstrInfo_->getName(I), I); 124 } 125 126 template <> 127 llvm::Error 128 Analysis::run<Analysis::PrintClusters>(llvm::raw_ostream &OS) const { 129 if (Clustering_.getPoints().empty()) 130 return llvm::Error::success(); 131 132 // Write the header. 133 OS << "cluster_id" << kCsvSep << "opcode_name" << kCsvSep << "config" 134 << kCsvSep << "sched_class"; 135 for (const auto &Measurement : Clustering_.getPoints().front().Measurements) { 136 OS << kCsvSep; 137 writeEscaped<kEscapeCsv>(OS, Measurement.Key); 138 } 139 OS << "\n"; 140 141 // Write the points. 142 const auto &Clusters = Clustering_.getValidClusters(); 143 for (size_t I = 0, E = Clusters.size(); I < E; ++I) { 144 for (const size_t PointId : Clusters[I].PointIndices) { 145 printInstructionRowCsv(PointId, OS); 146 } 147 OS << "\n\n"; 148 } 149 return llvm::Error::success(); 150 } 151 152 std::unordered_map<unsigned, std::vector<size_t>> 153 Analysis::makePointsPerSchedClass() const { 154 std::unordered_map<unsigned, std::vector<size_t>> PointsPerSchedClass; 155 const auto &Points = Clustering_.getPoints(); 156 for (size_t PointId = 0, E = Points.size(); PointId < E; ++PointId) { 157 const InstructionBenchmark &Point = Points[PointId]; 158 if (!Point.Error.empty()) 159 continue; 160 const auto OpcodeIt = MnemonicToOpcode_.find(Point.Key.OpcodeName); 161 if (OpcodeIt == MnemonicToOpcode_.end()) 162 continue; 163 const unsigned SchedClassId = 164 InstrInfo_->get(OpcodeIt->second).getSchedClass(); 165 PointsPerSchedClass[SchedClassId].push_back(PointId); 166 } 167 return PointsPerSchedClass; 168 } 169 170 void Analysis::printSchedClassClustersHtml(std::vector<size_t> PointIds, 171 llvm::raw_ostream &OS) const { 172 assert(!PointIds.empty()); 173 // Sort the points by cluster id so that we can display them grouped by 174 // cluster. 175 std::sort(PointIds.begin(), PointIds.end(), 176 [this](const size_t A, const size_t B) { 177 return Clustering_.getClusterIdForPoint(A) < 178 Clustering_.getClusterIdForPoint(B); 179 }); 180 const auto &Points = Clustering_.getPoints(); 181 OS << "<table class=\"sched-class-clusters\">"; 182 OS << "<tr><th>ClusterId</th><th>Opcode/Config</th>"; 183 for (const auto &Measurement : Points[PointIds[0]].Measurements) { 184 OS << "<th>"; 185 if (Measurement.DebugString.empty()) 186 writeEscaped<kEscapeHtml>(OS, Measurement.Key); 187 else 188 writeEscaped<kEscapeHtml>(OS, Measurement.DebugString); 189 OS << "</th>"; 190 } 191 OS << "</tr>"; 192 for (size_t I = 0, E = PointIds.size(); I < E;) { 193 const auto &CurrentClusterId = 194 Clustering_.getClusterIdForPoint(PointIds[I]); 195 OS << "<tr><td>"; 196 writeClusterId<kEscapeHtml>(OS, CurrentClusterId); 197 OS << "</td><td><ul>"; 198 std::vector<BenchmarkMeasureStats> MeasurementStats( 199 Points[PointIds[I]].Measurements.size()); 200 for (; I < E && 201 Clustering_.getClusterIdForPoint(PointIds[I]) == CurrentClusterId; 202 ++I) { 203 const auto &Point = Points[PointIds[I]]; 204 OS << "<li><span class=\"mono\">"; 205 writeEscaped<kEscapeHtml>(OS, Point.Key.OpcodeName); 206 OS << "</span> <span class=\"mono\">"; 207 writeEscaped<kEscapeHtml>(OS, Point.Key.Config); 208 OS << "</span></li>"; 209 for (size_t J = 0, F = Point.Measurements.size(); J < F; ++J) { 210 MeasurementStats[J].push(Point.Measurements[J]); 211 } 212 } 213 OS << "</ul></td>"; 214 for (const auto &Stats : MeasurementStats) { 215 OS << "<td class=\"measurement\">"; 216 writeMeasurementValue<kEscapeHtml>(OS, Stats.avg()); 217 OS << "<br><span class=\"minmax\">["; 218 writeMeasurementValue<kEscapeHtml>(OS, Stats.min()); 219 OS << ";"; 220 writeMeasurementValue<kEscapeHtml>(OS, Stats.max()); 221 OS << "]</span></td>"; 222 } 223 OS << "</tr>"; 224 } 225 OS << "</table>"; 226 } 227 228 // Return the non-redundant list of WriteProcRes used by the given sched class. 229 // The scheduling model for LLVM is such that each instruction has a certain 230 // number of uops which consume resources which are described by WriteProcRes 231 // entries. Each entry describe how many cycles are spent on a specific ProcRes 232 // kind. 233 // For example, an instruction might have 3 uOps, one dispatching on P0 234 // (ProcResIdx=1) and two on P06 (ProcResIdx = 7). 235 // Note that LLVM additionally denormalizes resource consumption to include 236 // usage of super resources by subresources. So in practice if there exists a 237 // P016 (ProcResIdx=10), then the cycles consumed by P0 are also consumed by 238 // P06 (ProcResIdx = 7) and P016 (ProcResIdx = 10), and the resources consumed 239 // by P06 are also consumed by P016. In the figure below, parenthesized cycles 240 // denote implied usage of superresources by subresources: 241 // P0 P06 P016 242 // uOp1 1 (1) (1) 243 // uOp2 1 (1) 244 // uOp3 1 (1) 245 // ============================= 246 // 1 3 3 247 // Eventually we end up with three entries for the WriteProcRes of the 248 // instruction: 249 // {ProcResIdx=1, Cycles=1} // P0 250 // {ProcResIdx=7, Cycles=3} // P06 251 // {ProcResIdx=10, Cycles=3} // P016 252 // 253 // Note that in this case, P016 does not contribute any cycles, so it would 254 // be removed by this function. 255 // FIXME: Move this to MCSubtargetInfo and use it in llvm-mca. 256 static llvm::SmallVector<llvm::MCWriteProcResEntry, 8> 257 getNonRedundantWriteProcRes(const llvm::MCSchedClassDesc &SCDesc, 258 const llvm::MCSubtargetInfo &STI) { 259 llvm::SmallVector<llvm::MCWriteProcResEntry, 8> Result; 260 const auto &SM = STI.getSchedModel(); 261 const unsigned NumProcRes = SM.getNumProcResourceKinds(); 262 263 // This assumes that the ProcResDescs are sorted in topological order, which 264 // is guaranteed by the tablegen backend. 265 llvm::SmallVector<float, 32> ProcResUnitUsage(NumProcRes); 266 for (const auto *WPR = STI.getWriteProcResBegin(&SCDesc), 267 *const WPREnd = STI.getWriteProcResEnd(&SCDesc); 268 WPR != WPREnd; ++WPR) { 269 const llvm::MCProcResourceDesc *const ProcResDesc = 270 SM.getProcResource(WPR->ProcResourceIdx); 271 if (ProcResDesc->SubUnitsIdxBegin == nullptr) { 272 // This is a ProcResUnit. 273 Result.push_back({WPR->ProcResourceIdx, WPR->Cycles}); 274 ProcResUnitUsage[WPR->ProcResourceIdx] += WPR->Cycles; 275 } else { 276 // This is a ProcResGroup. First see if it contributes any cycles or if 277 // it has cycles just from subunits. 278 float RemainingCycles = WPR->Cycles; 279 for (const auto *SubResIdx = ProcResDesc->SubUnitsIdxBegin; 280 SubResIdx != ProcResDesc->SubUnitsIdxBegin + ProcResDesc->NumUnits; 281 ++SubResIdx) { 282 RemainingCycles -= ProcResUnitUsage[*SubResIdx]; 283 } 284 if (RemainingCycles < 0.01f) { 285 // The ProcResGroup contributes no cycles of its own. 286 continue; 287 } 288 // The ProcResGroup contributes `RemainingCycles` cycles of its own. 289 Result.push_back({WPR->ProcResourceIdx, 290 static_cast<uint16_t>(std::round(RemainingCycles))}); 291 // Spread the remaining cycles over all subunits. 292 for (const auto *SubResIdx = ProcResDesc->SubUnitsIdxBegin; 293 SubResIdx != ProcResDesc->SubUnitsIdxBegin + ProcResDesc->NumUnits; 294 ++SubResIdx) { 295 ProcResUnitUsage[*SubResIdx] += RemainingCycles / ProcResDesc->NumUnits; 296 } 297 } 298 } 299 return Result; 300 } 301 302 void Analysis::printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc, 303 llvm::raw_ostream &OS) const { 304 OS << "<table class=\"sched-class-desc\">"; 305 OS << "<tr><th>Valid</th><th>Variant</th><th>uOps</th><th>Latency</" 306 "th><th>WriteProcRes</th></tr>"; 307 if (SCDesc.isValid()) { 308 OS << "<tr><td>✔</td>"; 309 OS << "<td>" << (SCDesc.isVariant() ? "✔" : "✕") << "</td>"; 310 OS << "<td>" << SCDesc.NumMicroOps << "</td>"; 311 // Latencies. 312 OS << "<td><ul>"; 313 for (int I = 0, E = SCDesc.NumWriteLatencyEntries; I < E; ++I) { 314 const auto *const Entry = 315 SubtargetInfo_->getWriteLatencyEntry(&SCDesc, I); 316 OS << "<li>" << Entry->Cycles; 317 if (SCDesc.NumWriteLatencyEntries > 1) { 318 // Dismabiguate if more than 1 latency. 319 OS << " (WriteResourceID " << Entry->WriteResourceID << ")"; 320 } 321 OS << "</li>"; 322 } 323 OS << "</ul></td>"; 324 // WriteProcRes. 325 OS << "<td><ul>"; 326 for (const auto &WPR : 327 getNonRedundantWriteProcRes(SCDesc, *SubtargetInfo_)) { 328 OS << "<li><span class=\"mono\">"; 329 writeEscaped<kEscapeHtml>(OS, SubtargetInfo_->getSchedModel() 330 .getProcResource(WPR.ProcResourceIdx) 331 ->Name); 332 OS << "</span>: " << WPR.Cycles << "</li>"; 333 } 334 OS << "</ul></td>"; 335 OS << "</tr>"; 336 } else { 337 OS << "<tr><td>✕</td><td></td><td></td></tr>"; 338 } 339 OS << "</table>"; 340 } 341 342 static constexpr const char kHtmlHead[] = R"( 343 <head> 344 <title>llvm-exegesis Analysis Results</title> 345 <style> 346 body { 347 font-family: sans-serif 348 } 349 span.sched-class-name { 350 font-weight: bold; 351 font-family: monospace; 352 } 353 span.opcode { 354 font-family: monospace; 355 } 356 span.config { 357 font-family: monospace; 358 } 359 div.inconsistency { 360 margin-top: 50px; 361 } 362 table { 363 margin-left: 50px; 364 border-collapse: collapse; 365 } 366 table, table tr,td,th { 367 border: 1px solid #444; 368 } 369 table ul { 370 padding-left: 0px; 371 margin: 0px; 372 list-style-type: none; 373 } 374 table.sched-class-clusters td { 375 padding-left: 10px; 376 padding-right: 10px; 377 padding-top: 10px; 378 padding-bottom: 10px; 379 } 380 table.sched-class-desc td { 381 padding-left: 10px; 382 padding-right: 10px; 383 padding-top: 2px; 384 padding-bottom: 2px; 385 } 386 span.mono { 387 font-family: monospace; 388 } 389 span.minmax { 390 color: #888; 391 } 392 td.measurement { 393 text-align: center; 394 } 395 </style> 396 </head> 397 )"; 398 399 template <> 400 llvm::Error Analysis::run<Analysis::PrintSchedClassInconsistencies>( 401 llvm::raw_ostream &OS) const { 402 // Print the header. 403 OS << "<!DOCTYPE html><html>" << kHtmlHead << "<body>"; 404 OS << "<h1><span class=\"mono\">llvm-exegesis</span> Analysis Results</h1>"; 405 OS << "<h3>Triple: <span class=\"mono\">"; 406 writeEscaped<kEscapeHtml>(OS, Clustering_.getPoints()[0].LLVMTriple); 407 OS << "</span></h3><h3>Cpu: <span class=\"mono\">"; 408 writeEscaped<kEscapeHtml>(OS, Clustering_.getPoints()[0].CpuName); 409 OS << "</span></h3>"; 410 411 // All the points in a scheduling class should be in the same cluster. 412 // Print any scheduling class for which this is not the case. 413 for (const auto &SchedClassAndPoints : makePointsPerSchedClass()) { 414 std::unordered_set<size_t> ClustersForSchedClass; 415 for (const size_t PointId : SchedClassAndPoints.second) { 416 const auto &ClusterId = Clustering_.getClusterIdForPoint(PointId); 417 if (!ClusterId.isValid()) 418 continue; // Ignore noise and errors. 419 ClustersForSchedClass.insert(ClusterId.getId()); 420 } 421 if (ClustersForSchedClass.size() <= 1) 422 continue; // Nothing weird. 423 424 const auto &SchedModel = SubtargetInfo_->getSchedModel(); 425 const llvm::MCSchedClassDesc *const SCDesc = 426 SchedModel.getSchedClassDesc(SchedClassAndPoints.first); 427 if (!SCDesc) 428 continue; 429 OS << "<div class=\"inconsistency\"><p>Sched Class <span " 430 "class=\"sched-class-name\">"; 431 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 432 writeEscaped<kEscapeHtml>(OS, SCDesc->Name); 433 #else 434 OS << SchedClassAndPoints.first; 435 #endif 436 OS << "</span> contains instructions with distinct performance " 437 "characteristics, falling into " 438 << ClustersForSchedClass.size() << " clusters:</p>"; 439 printSchedClassClustersHtml(SchedClassAndPoints.second, OS); 440 OS << "<p>llvm data:</p>"; 441 printSchedClassDescHtml(*SCDesc, OS); 442 OS << "</div>"; 443 } 444 445 OS << "</body></html>"; 446 return llvm::Error::success(); 447 } 448 449 } // namespace exegesis 450