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 writeEscaped<kEscapeHtml>(OS, Measurement.Key); 186 OS << "</th>"; 187 } 188 OS << "</tr>"; 189 for (size_t I = 0, E = PointIds.size(); I < E;) { 190 const auto &CurrentClusterId = 191 Clustering_.getClusterIdForPoint(PointIds[I]); 192 OS << "<tr><td>"; 193 writeClusterId<kEscapeHtml>(OS, CurrentClusterId); 194 OS << "</td><td><ul>"; 195 const auto &ClusterRepresentative = 196 Points[PointIds[I]]; // FIXME: average measurements. 197 for (; I < E && 198 Clustering_.getClusterIdForPoint(PointIds[I]) == CurrentClusterId; 199 ++I) { 200 OS << "<li><span class=\"mono\">"; 201 writeEscaped<kEscapeHtml>(OS, Points[PointIds[I]].Key.OpcodeName); 202 OS << "</span> <span class=\"mono\">"; 203 writeEscaped<kEscapeHtml>(OS, Points[PointIds[I]].Key.Config); 204 OS << "</span></li>"; 205 } 206 OS << "</ul></td>"; 207 for (const auto &Measurement : ClusterRepresentative.Measurements) { 208 OS << "<td>"; 209 writeMeasurementValue<kEscapeHtml>(OS, Measurement.Value); 210 OS << "</td>"; 211 } 212 OS << "</tr>"; 213 } 214 OS << "</table>"; 215 } 216 217 // Return the non-redundant list of WriteProcRes used by the given sched class. 218 // The scheduling model for LLVM is such that each instruction has a certain 219 // number of uops which consume resources which are described by WriteProcRes 220 // entries. Each entry describe how many cycles are spent on a specific ProcRes 221 // kind. 222 // For example, an instruction might have 3 uOps, one dispatching on P0 223 // (ProcResIdx=1) and two on P06 (ProcResIdx = 7). 224 // Note that LLVM additionally denormalizes resource consumption to include 225 // usage of super resources by subresources. So in practice if there exists a 226 // P016 (ProcResIdx=10), then the cycles consumed by P0 are also consumed by 227 // P06 (ProcResIdx = 7) and P016 (ProcResIdx = 10), and the resources consumed 228 // by P06 are also consumed by P016. In the figure below, parenthesized cycles 229 // denote implied usage of superresources by subresources: 230 // P0 P06 P016 231 // uOp1 1 (1) (1) 232 // uOp2 1 (1) 233 // uOp3 1 (1) 234 // ============================= 235 // 1 3 3 236 // Eventually we end up with three entries for the WriteProcRes of the 237 // instruction: 238 // {ProcResIdx=1, Cycles=1} // P0 239 // {ProcResIdx=7, Cycles=3} // P06 240 // {ProcResIdx=10, Cycles=3} // P016 241 // 242 // Note that in this case, P016 does not contribute any cycles, so it would 243 // be removed by this function. 244 // FIXME: Move this to MCSubtargetInfo and use it in llvm-mca. 245 static llvm::SmallVector<llvm::MCWriteProcResEntry, 8> 246 getNonRedundantWriteProcRes(const llvm::MCSchedClassDesc &SCDesc, 247 const llvm::MCSubtargetInfo &STI) { 248 llvm::SmallVector<llvm::MCWriteProcResEntry, 8> Result; 249 const auto &SM = STI.getSchedModel(); 250 const unsigned NumProcRes = SM.getNumProcResourceKinds(); 251 252 // This assumes that the ProcResDescs are sorted in topological order, which 253 // is guaranteed by the tablegen backend. 254 llvm::SmallVector<float, 32> ProcResUnitUsage(NumProcRes); 255 for (const auto *WPR = STI.getWriteProcResBegin(&SCDesc), 256 *const WPREnd = STI.getWriteProcResEnd(&SCDesc); 257 WPR != WPREnd; ++WPR) { 258 const llvm::MCProcResourceDesc *const ProcResDesc = 259 SM.getProcResource(WPR->ProcResourceIdx); 260 if (ProcResDesc->SubUnitsIdxBegin == nullptr) { 261 // This is a ProcResUnit. 262 Result.push_back({WPR->ProcResourceIdx, WPR->Cycles}); 263 ProcResUnitUsage[WPR->ProcResourceIdx] += WPR->Cycles; 264 } else { 265 // This is a ProcResGroup. First see if it contributes any cycles or if 266 // it has cycles just from subunits. 267 float RemainingCycles = WPR->Cycles; 268 for (const auto *SubResIdx = ProcResDesc->SubUnitsIdxBegin; 269 SubResIdx != ProcResDesc->SubUnitsIdxBegin + ProcResDesc->NumUnits; 270 ++SubResIdx) { 271 RemainingCycles -= ProcResUnitUsage[*SubResIdx]; 272 } 273 if (RemainingCycles < 0.01f) { 274 // The ProcResGroup contributes no cycles of its own. 275 continue; 276 } 277 // The ProcResGroup contributes `RemainingCycles` cycles of its own. 278 Result.push_back({WPR->ProcResourceIdx, 279 static_cast<uint16_t>(std::round(RemainingCycles))}); 280 // Spread the remaining cycles over all subunits. 281 for (const auto *SubResIdx = ProcResDesc->SubUnitsIdxBegin; 282 SubResIdx != ProcResDesc->SubUnitsIdxBegin + ProcResDesc->NumUnits; 283 ++SubResIdx) { 284 ProcResUnitUsage[*SubResIdx] += RemainingCycles / ProcResDesc->NumUnits; 285 } 286 } 287 } 288 return Result; 289 } 290 291 void Analysis::printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc, 292 llvm::raw_ostream &OS) const { 293 OS << "<table class=\"sched-class-desc\">"; 294 OS << "<tr><th>Valid</th><th>Variant</th><th>uOps</th><th>Latency</" 295 "th><th>WriteProcRes</th></tr>"; 296 if (SCDesc.isValid()) { 297 OS << "<tr><td>✔</td>"; 298 OS << "<td>" << (SCDesc.isVariant() ? "✔" : "✕") << "</td>"; 299 OS << "<td>" << SCDesc.NumMicroOps << "</td>"; 300 // Latencies. 301 OS << "<td><ul>"; 302 for (int I = 0, E = SCDesc.NumWriteLatencyEntries; I < E; ++I) { 303 const auto *const Entry = 304 SubtargetInfo_->getWriteLatencyEntry(&SCDesc, I); 305 OS << "<li>" << Entry->Cycles; 306 if (SCDesc.NumWriteLatencyEntries > 1) { 307 // Dismabiguate if more than 1 latency. 308 OS << " (WriteResourceID " << Entry->WriteResourceID << ")"; 309 } 310 OS << "</li>"; 311 } 312 OS << "</ul></td>"; 313 // WriteProcRes. 314 OS << "<td><ul>"; 315 for (const auto &WPR : 316 getNonRedundantWriteProcRes(SCDesc, *SubtargetInfo_)) { 317 OS << "<li><span class=\"mono\">"; 318 writeEscaped<kEscapeHtml>(OS, SubtargetInfo_->getSchedModel() 319 .getProcResource(WPR.ProcResourceIdx) 320 ->Name); 321 OS << "</spam>: " << WPR.Cycles << "</li>"; 322 } 323 OS << "</ul></td>"; 324 OS << "</tr>"; 325 } else { 326 OS << "<tr><td>✕</td><td></td><td></td></tr>"; 327 } 328 OS << "</table>"; 329 } 330 331 static constexpr const char kHtmlHead[] = R"( 332 <head> 333 <title>llvm-exegesis Analysis Results</title> 334 <style> 335 body { 336 font-family: sans-serif 337 } 338 span.sched-class-name { 339 font-weight: bold; 340 font-family: monospace; 341 } 342 span.opcode { 343 font-family: monospace; 344 } 345 span.config { 346 font-family: monospace; 347 } 348 div.inconsistency { 349 margin-top: 50px; 350 } 351 table { 352 margin-left: 50px; 353 border-collapse: collapse; 354 } 355 table, table tr,td,th { 356 border: 1px solid #444; 357 } 358 table ul { 359 padding-left: 0px; 360 margin: 0px; 361 list-style-type: none; 362 } 363 table.sched-class-clusters td { 364 padding-left: 10px; 365 padding-right: 10px; 366 padding-top: 10px; 367 padding-bottom: 10px; 368 } 369 table.sched-class-desc td { 370 padding-left: 10px; 371 padding-right: 10px; 372 padding-top: 2px; 373 padding-bottom: 2px; 374 } 375 span.mono { 376 font-family: monospace; 377 } 378 </style> 379 </head> 380 )"; 381 382 template <> 383 llvm::Error Analysis::run<Analysis::PrintSchedClassInconsistencies>( 384 llvm::raw_ostream &OS) const { 385 // Print the header. 386 OS << "<!DOCTYPE html><html>" << kHtmlHead << "<body>"; 387 OS << "<h1><span class=\"mono\">llvm-exegesis</span> Analysis Results</h1>"; 388 OS << "<h3>Triple: <span class=\"mono\">"; 389 writeEscaped<kEscapeHtml>(OS, Clustering_.getPoints()[0].LLVMTriple); 390 OS << "</span></h3><h3>Cpu: <span class=\"mono\">"; 391 writeEscaped<kEscapeHtml>(OS, Clustering_.getPoints()[0].CpuName); 392 OS << "</span></h3>"; 393 394 // All the points in a scheduling class should be in the same cluster. 395 // Print any scheduling class for which this is not the case. 396 for (const auto &SchedClassAndPoints : makePointsPerSchedClass()) { 397 std::unordered_set<size_t> ClustersForSchedClass; 398 for (const size_t PointId : SchedClassAndPoints.second) { 399 const auto &ClusterId = Clustering_.getClusterIdForPoint(PointId); 400 if (!ClusterId.isValid()) 401 continue; // Ignore noise and errors. 402 ClustersForSchedClass.insert(ClusterId.getId()); 403 } 404 if (ClustersForSchedClass.size() <= 1) 405 continue; // Nothing weird. 406 407 const auto &SchedModel = SubtargetInfo_->getSchedModel(); 408 const llvm::MCSchedClassDesc *const SCDesc = 409 SchedModel.getSchedClassDesc(SchedClassAndPoints.first); 410 if (!SCDesc) 411 continue; 412 OS << "<div class=\"inconsistency\"><p>Sched Class <span " 413 "class=\"sched-class-name\">"; 414 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 415 writeEscaped<kEscapeHtml>(OS, SCDesc->Name); 416 #else 417 OS << SchedClassAndPoints.first; 418 #endif 419 OS << "</span> contains instructions with distinct performance " 420 "characteristics, falling into " 421 << ClustersForSchedClass.size() << " clusters:</p>"; 422 printSchedClassClustersHtml(SchedClassAndPoints.second, OS); 423 OS << "<p>llvm data:</p>"; 424 printSchedClassDescHtml(*SCDesc, OS); 425 OS << "</div>"; 426 } 427 428 OS << "</body></html>"; 429 return llvm::Error::success(); 430 } 431 432 } // namespace exegesis 433