1 //===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===// 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 // This class parses the Schedule.td file and produces an API that can be used 10 // to reason about whether an instruction can be added to a packet on a VLIW 11 // architecture. The class internally generates a deterministic finite 12 // automaton (DFA) that models all possible mappings of machine instructions 13 // to functional units as instructions are added to a packet. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #define DEBUG_TYPE "dfa-emitter" 18 19 #include "CodeGenTarget.h" 20 #include "DFAEmitter.h" 21 #include "llvm/ADT/DenseSet.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/ADT/StringExtras.h" 24 #include "llvm/TableGen/Record.h" 25 #include "llvm/TableGen/TableGenBackend.h" 26 #include "llvm/Support/Debug.h" 27 #include "llvm/Support/raw_ostream.h" 28 #include <cassert> 29 #include <cstdint> 30 #include <map> 31 #include <set> 32 #include <string> 33 #include <unordered_map> 34 #include <vector> 35 36 using namespace llvm; 37 38 // -------------------------------------------------------------------- 39 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp 40 41 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput. 42 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer. 43 // 44 // e.g. terms x resource bit combinations that fit in uint32_t: 45 // 4 terms x 8 bits = 32 bits 46 // 3 terms x 10 bits = 30 bits 47 // 2 terms x 16 bits = 32 bits 48 // 49 // e.g. terms x resource bit combinations that fit in uint64_t: 50 // 8 terms x 8 bits = 64 bits 51 // 7 terms x 9 bits = 63 bits 52 // 6 terms x 10 bits = 60 bits 53 // 5 terms x 12 bits = 60 bits 54 // 4 terms x 16 bits = 64 bits <--- current 55 // 3 terms x 21 bits = 63 bits 56 // 2 terms x 32 bits = 64 bits 57 // 58 #define DFA_MAX_RESTERMS 4 // The max # of AND'ed resource terms. 59 #define DFA_MAX_RESOURCES 16 // The max # of resource bits in one term. 60 61 typedef uint64_t DFAInput; 62 typedef int64_t DFAStateInput; 63 #define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable. 64 65 namespace { 66 67 DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) { 68 return (Inp << DFA_MAX_RESOURCES) | FuncUnits; 69 } 70 71 /// Return the DFAInput for an instruction class input vector. 72 /// This function is used in both DFAPacketizer.cpp and in 73 /// DFAPacketizerEmitter.cpp. 74 DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) { 75 DFAInput InsnInput = 0; 76 assert((InsnClass.size() <= DFA_MAX_RESTERMS) && 77 "Exceeded maximum number of DFA terms"); 78 for (auto U : InsnClass) 79 InsnInput = addDFAFuncUnits(InsnInput, U); 80 return InsnInput; 81 } 82 83 } // end anonymous namespace 84 85 // -------------------------------------------------------------------- 86 87 #ifndef NDEBUG 88 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter". 89 // 90 // dbgsInsnClass - When debugging, print instruction class stages. 91 // 92 void dbgsInsnClass(const std::vector<unsigned> &InsnClass); 93 // 94 // dbgsStateInfo - When debugging, print the set of state info. 95 // 96 void dbgsStateInfo(const std::set<unsigned> &stateInfo); 97 // 98 // dbgsIndent - When debugging, indent by the specified amount. 99 // 100 void dbgsIndent(unsigned indent); 101 #endif 102 103 // 104 // class DFAPacketizerEmitter: class that generates and prints out the DFA 105 // for resource tracking. 106 // 107 namespace { 108 109 class DFAPacketizerEmitter { 110 private: 111 std::string TargetName; 112 // 113 // allInsnClasses is the set of all possible resources consumed by an 114 // InstrStage. 115 // 116 std::vector<std::vector<unsigned>> allInsnClasses; 117 RecordKeeper &Records; 118 119 public: 120 DFAPacketizerEmitter(RecordKeeper &R); 121 122 // 123 // collectAllFuncUnits - Construct a map of function unit names to bits. 124 // 125 int collectAllFuncUnits(std::vector<Record*> &ProcItinList, 126 std::map<std::string, unsigned> &FUNameToBitsMap, 127 int &maxResources, 128 raw_ostream &OS); 129 130 // 131 // collectAllComboFuncs - Construct a map from a combo function unit bit to 132 // the bits of all included functional units. 133 // 134 int collectAllComboFuncs(std::vector<Record*> &ComboFuncList, 135 std::map<std::string, unsigned> &FUNameToBitsMap, 136 std::map<unsigned, unsigned> &ComboBitToBitsMap, 137 raw_ostream &OS); 138 139 // 140 // collectOneInsnClass - Populate allInsnClasses with one instruction class. 141 // 142 int collectOneInsnClass(const std::string &ProcName, 143 std::vector<Record*> &ProcItinList, 144 std::map<std::string, unsigned> &FUNameToBitsMap, 145 Record *ItinData, 146 raw_ostream &OS); 147 148 // 149 // collectAllInsnClasses - Populate allInsnClasses which is a set of units 150 // used in each stage. 151 // 152 int collectAllInsnClasses(const std::string &ProcName, 153 std::vector<Record*> &ProcItinList, 154 std::map<std::string, unsigned> &FUNameToBitsMap, 155 std::vector<Record*> &ItinDataList, 156 int &maxStages, 157 raw_ostream &OS); 158 159 // Emit code for a subset of itineraries. 160 void emitForItineraries(raw_ostream &OS, 161 std::vector<Record *> &ProcItinList, 162 std::string DFAName); 163 164 void run(raw_ostream &OS); 165 }; 166 } // end anonymous namespace 167 168 #ifndef NDEBUG 169 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter". 170 // 171 // dbgsInsnClass - When debugging, print instruction class stages. 172 // 173 void dbgsInsnClass(const std::vector<unsigned> &InsnClass) { 174 LLVM_DEBUG(dbgs() << "InsnClass: "); 175 for (unsigned i = 0; i < InsnClass.size(); ++i) { 176 if (i > 0) { 177 LLVM_DEBUG(dbgs() << ", "); 178 } 179 LLVM_DEBUG(dbgs() << "0x" << Twine::utohexstr(InsnClass[i])); 180 } 181 DFAInput InsnInput = getDFAInsnInput(InsnClass); 182 LLVM_DEBUG(dbgs() << " (input: 0x" << Twine::utohexstr(InsnInput) << ")"); 183 } 184 185 // 186 // dbgsIndent - When debugging, indent by the specified amount. 187 // 188 void dbgsIndent(unsigned indent) { 189 for (unsigned i = 0; i < indent; ++i) { 190 LLVM_DEBUG(dbgs() << " "); 191 } 192 } 193 #endif // NDEBUG 194 195 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): 196 TargetName(CodeGenTarget(R).getName()), Records(R) {} 197 198 // 199 // collectAllFuncUnits - Construct a map of function unit names to bits. 200 // 201 int DFAPacketizerEmitter::collectAllFuncUnits( 202 std::vector<Record*> &ProcItinList, 203 std::map<std::string, unsigned> &FUNameToBitsMap, 204 int &maxFUs, 205 raw_ostream &OS) { 206 LLVM_DEBUG(dbgs() << "-------------------------------------------------------" 207 "----------------------\n"); 208 LLVM_DEBUG(dbgs() << "collectAllFuncUnits"); 209 LLVM_DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n"); 210 211 int totalFUs = 0; 212 // Parse functional units for all the itineraries. 213 for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { 214 Record *Proc = ProcItinList[i]; 215 std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); 216 217 LLVM_DEBUG(dbgs() << " FU:" << i << " (" << FUs.size() << " FUs) " 218 << Proc->getName()); 219 220 // Convert macros to bits for each stage. 221 unsigned numFUs = FUs.size(); 222 for (unsigned j = 0; j < numFUs; ++j) { 223 assert ((j < DFA_MAX_RESOURCES) && 224 "Exceeded maximum number of representable resources"); 225 unsigned FuncResources = (unsigned) (1U << j); 226 FUNameToBitsMap[FUs[j]->getName()] = FuncResources; 227 LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x" 228 << Twine::utohexstr(FuncResources)); 229 } 230 if (((int) numFUs) > maxFUs) { 231 maxFUs = numFUs; 232 } 233 totalFUs += numFUs; 234 LLVM_DEBUG(dbgs() << "\n"); 235 } 236 return totalFUs; 237 } 238 239 // 240 // collectAllComboFuncs - Construct a map from a combo function unit bit to 241 // the bits of all included functional units. 242 // 243 int DFAPacketizerEmitter::collectAllComboFuncs( 244 std::vector<Record*> &ComboFuncList, 245 std::map<std::string, unsigned> &FUNameToBitsMap, 246 std::map<unsigned, unsigned> &ComboBitToBitsMap, 247 raw_ostream &OS) { 248 LLVM_DEBUG(dbgs() << "-------------------------------------------------------" 249 "----------------------\n"); 250 LLVM_DEBUG(dbgs() << "collectAllComboFuncs"); 251 LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n"); 252 253 int numCombos = 0; 254 for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) { 255 Record *Func = ComboFuncList[i]; 256 std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD"); 257 258 LLVM_DEBUG(dbgs() << " CFD:" << i << " (" << FUs.size() << " combo FUs) " 259 << Func->getName() << "\n"); 260 261 // Convert macros to bits for each stage. 262 for (unsigned j = 0, N = FUs.size(); j < N; ++j) { 263 assert ((j < DFA_MAX_RESOURCES) && 264 "Exceeded maximum number of DFA resources"); 265 Record *FuncData = FUs[j]; 266 Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc"); 267 const std::vector<Record*> &FuncList = 268 FuncData->getValueAsListOfDefs("FuncList"); 269 const std::string &ComboFuncName = ComboFunc->getName(); 270 unsigned ComboBit = FUNameToBitsMap[ComboFuncName]; 271 unsigned ComboResources = ComboBit; 272 LLVM_DEBUG(dbgs() << " combo: " << ComboFuncName << ":0x" 273 << Twine::utohexstr(ComboResources) << "\n"); 274 for (unsigned k = 0, M = FuncList.size(); k < M; ++k) { 275 std::string FuncName = FuncList[k]->getName(); 276 unsigned FuncResources = FUNameToBitsMap[FuncName]; 277 LLVM_DEBUG(dbgs() << " " << FuncName << ":0x" 278 << Twine::utohexstr(FuncResources) << "\n"); 279 ComboResources |= FuncResources; 280 } 281 ComboBitToBitsMap[ComboBit] = ComboResources; 282 numCombos++; 283 LLVM_DEBUG(dbgs() << " => combo bits: " << ComboFuncName << ":0x" 284 << Twine::utohexstr(ComboBit) << " = 0x" 285 << Twine::utohexstr(ComboResources) << "\n"); 286 } 287 } 288 return numCombos; 289 } 290 291 // 292 // collectOneInsnClass - Populate allInsnClasses with one instruction class 293 // 294 int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName, 295 std::vector<Record*> &ProcItinList, 296 std::map<std::string, unsigned> &FUNameToBitsMap, 297 Record *ItinData, 298 raw_ostream &OS) { 299 const std::vector<Record*> &StageList = 300 ItinData->getValueAsListOfDefs("Stages"); 301 302 // The number of stages. 303 unsigned NStages = StageList.size(); 304 305 LLVM_DEBUG(dbgs() << " " << ItinData->getValueAsDef("TheClass")->getName() 306 << "\n"); 307 308 std::vector<unsigned> UnitBits; 309 310 // Compute the bitwise or of each unit used in this stage. 311 for (unsigned i = 0; i < NStages; ++i) { 312 const Record *Stage = StageList[i]; 313 314 // Get unit list. 315 const std::vector<Record*> &UnitList = 316 Stage->getValueAsListOfDefs("Units"); 317 318 LLVM_DEBUG(dbgs() << " stage:" << i << " [" << UnitList.size() 319 << " units]:"); 320 unsigned dbglen = 26; // cursor after stage dbgs 321 322 // Compute the bitwise or of each unit used in this stage. 323 unsigned UnitBitValue = 0; 324 for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { 325 // Conduct bitwise or. 326 std::string UnitName = UnitList[j]->getName(); 327 LLVM_DEBUG(dbgs() << " " << j << ":" << UnitName); 328 dbglen += 3 + UnitName.length(); 329 assert(FUNameToBitsMap.count(UnitName)); 330 UnitBitValue |= FUNameToBitsMap[UnitName]; 331 } 332 333 if (UnitBitValue != 0) 334 UnitBits.push_back(UnitBitValue); 335 336 while (dbglen <= 64) { // line up bits dbgs 337 dbglen += 8; 338 LLVM_DEBUG(dbgs() << "\t"); 339 } 340 LLVM_DEBUG(dbgs() << " (bits: 0x" << Twine::utohexstr(UnitBitValue) 341 << ")\n"); 342 } 343 344 if (!UnitBits.empty()) 345 allInsnClasses.push_back(UnitBits); 346 347 LLVM_DEBUG({ 348 dbgs() << " "; 349 dbgsInsnClass(UnitBits); 350 dbgs() << "\n"; 351 }); 352 353 return NStages; 354 } 355 356 // 357 // collectAllInsnClasses - Populate allInsnClasses which is a set of units 358 // used in each stage. 359 // 360 int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName, 361 std::vector<Record*> &ProcItinList, 362 std::map<std::string, unsigned> &FUNameToBitsMap, 363 std::vector<Record*> &ItinDataList, 364 int &maxStages, 365 raw_ostream &OS) { 366 // Collect all instruction classes. 367 unsigned M = ItinDataList.size(); 368 369 int numInsnClasses = 0; 370 LLVM_DEBUG(dbgs() << "-------------------------------------------------------" 371 "----------------------\n" 372 << "collectAllInsnClasses " << ProcName << " (" << M 373 << " classes)\n"); 374 375 // Collect stages for each instruction class for all itinerary data 376 for (unsigned j = 0; j < M; j++) { 377 Record *ItinData = ItinDataList[j]; 378 int NStages = collectOneInsnClass(ProcName, ProcItinList, 379 FUNameToBitsMap, ItinData, OS); 380 if (NStages > maxStages) { 381 maxStages = NStages; 382 } 383 numInsnClasses++; 384 } 385 return numInsnClasses; 386 } 387 388 // 389 // Run the worklist algorithm to generate the DFA. 390 // 391 void DFAPacketizerEmitter::run(raw_ostream &OS) { 392 OS << "\n" 393 << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; 394 OS << "namespace llvm {\n"; 395 396 OS << "\n// Input format:\n"; 397 OS << "#define DFA_MAX_RESTERMS " << DFA_MAX_RESTERMS 398 << "\t// maximum AND'ed resource terms\n"; 399 OS << "#define DFA_MAX_RESOURCES " << DFA_MAX_RESOURCES 400 << "\t// maximum resource bits in one term\n"; 401 402 // Collect processor iteraries. 403 std::vector<Record*> ProcItinList = 404 Records.getAllDerivedDefinitions("ProcessorItineraries"); 405 406 std::unordered_map<std::string, std::vector<Record*>> ItinsByNamespace; 407 for (Record *R : ProcItinList) 408 ItinsByNamespace[R->getValueAsString("PacketizerNamespace")].push_back(R); 409 410 for (auto &KV : ItinsByNamespace) 411 emitForItineraries(OS, KV.second, KV.first); 412 OS << "} // end namespace llvm\n"; 413 } 414 415 void DFAPacketizerEmitter::emitForItineraries( 416 raw_ostream &OS, std::vector<Record *> &ProcItinList, 417 std::string DFAName) { 418 // 419 // Collect the Functional units. 420 // 421 std::map<std::string, unsigned> FUNameToBitsMap; 422 int maxResources = 0; 423 collectAllFuncUnits(ProcItinList, 424 FUNameToBitsMap, maxResources, OS); 425 426 // 427 // Collect the Combo Functional units. 428 // 429 std::map<unsigned, unsigned> ComboBitToBitsMap; 430 std::vector<Record*> ComboFuncList = 431 Records.getAllDerivedDefinitions("ComboFuncUnits"); 432 collectAllComboFuncs(ComboFuncList, FUNameToBitsMap, ComboBitToBitsMap, OS); 433 434 // 435 // Collect the itineraries. 436 // 437 int maxStages = 0; 438 int numInsnClasses = 0; 439 for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { 440 Record *Proc = ProcItinList[i]; 441 442 // Get processor itinerary name. 443 const std::string &ProcName = Proc->getName(); 444 445 // Skip default. 446 if (ProcName == "NoItineraries") 447 continue; 448 449 // Sanity check for at least one instruction itinerary class. 450 unsigned NItinClasses = 451 Records.getAllDerivedDefinitions("InstrItinClass").size(); 452 if (NItinClasses == 0) 453 return; 454 455 // Get itinerary data list. 456 std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); 457 458 // Collect all instruction classes 459 numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList, 460 FUNameToBitsMap, ItinDataList, maxStages, OS); 461 } 462 463 // The type of a state in the nondeterministic automaton we're defining. 464 using NfaStateTy = unsigned; 465 466 // Given a resource state, return all resource states by applying 467 // InsnClass. 468 auto applyInsnClass = [&](ArrayRef<unsigned> InsnClass, 469 NfaStateTy State) -> std::deque<unsigned> { 470 std::deque<unsigned> V(1, State); 471 // Apply every stage in the class individually. 472 for (unsigned Stage : InsnClass) { 473 // Apply this stage to every existing member of V in turn. 474 size_t Sz = V.size(); 475 for (unsigned I = 0; I < Sz; ++I) { 476 unsigned S = V.front(); 477 V.pop_front(); 478 479 // For this stage, state combination, try all possible resources. 480 for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) { 481 unsigned ResourceMask = 1U << J; 482 if ((ResourceMask & Stage) == 0) 483 // This resource isn't required by this stage. 484 continue; 485 unsigned Combo = ComboBitToBitsMap[ResourceMask]; 486 if (Combo && ((~S & Combo) != Combo)) 487 // This combo units bits are not available. 488 continue; 489 unsigned ResultingResourceState = S | ResourceMask | Combo; 490 if (ResultingResourceState == S) 491 continue; 492 V.push_back(ResultingResourceState); 493 } 494 } 495 } 496 return V; 497 }; 498 499 // Given a resource state, return a quick (conservative) guess as to whether 500 // InsnClass can be applied. This is a filter for the more heavyweight 501 // applyInsnClass. 502 auto canApplyInsnClass = [](ArrayRef<unsigned> InsnClass, 503 NfaStateTy State) -> bool { 504 for (unsigned Resources : InsnClass) { 505 if ((State | Resources) == State) 506 return false; 507 } 508 return true; 509 }; 510 511 DfaEmitter Emitter; 512 std::deque<NfaStateTy> Worklist(1, 0); 513 std::set<NfaStateTy> SeenStates; 514 SeenStates.insert(Worklist.front()); 515 while (!Worklist.empty()) { 516 NfaStateTy State = Worklist.front(); 517 Worklist.pop_front(); 518 for (unsigned i = 0; i < allInsnClasses.size(); i++) { 519 const std::vector<unsigned> &InsnClass = allInsnClasses[i]; 520 if (!canApplyInsnClass(InsnClass, State)) 521 continue; 522 for (unsigned NewState : applyInsnClass(InsnClass, State)) { 523 if (SeenStates.emplace(NewState).second) 524 Worklist.emplace_back(NewState); 525 Emitter.addTransition(State, NewState, getDFAInsnInput(InsnClass)); 526 } 527 } 528 } 529 530 OS << "} // end namespace llvm\n\n"; 531 OS << "namespace {\n"; 532 std::string TargetAndDFAName = TargetName + DFAName; 533 Emitter.emit(TargetAndDFAName, OS); 534 OS << "} // end anonymous namespace\n\n"; 535 536 std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 537 OS << "namespace llvm {\n"; 538 OS << "DFAPacketizer *" << SubTargetClassName << "::" 539 << "create" << DFAName 540 << "DFAPacketizer(const InstrItineraryData *IID) const {\n" 541 << " static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName 542 << "Transition>(" << TargetAndDFAName << "Transitions), " 543 << TargetAndDFAName << "TransitionInfo);\n" 544 << " return new DFAPacketizer(IID, A);\n" 545 << "\n}\n\n"; 546 } 547 548 namespace llvm { 549 550 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { 551 emitSourceFileHeader("Target DFA Packetizer Tables", OS); 552 DFAPacketizerEmitter(RK).run(OS); 553 } 554 555 } // end namespace llvm 556