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