1 //===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===// 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 // This class parses the Schedule.td file and produces an API that can be used 11 // to reason about whether an instruction can be added to a packet on a VLIW 12 // architecture. The class internally generates a deterministic finite 13 // automaton (DFA) that models all possible mappings of machine instructions 14 // to functional units as instructions are added to a packet. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #define DEBUG_TYPE "dfa-emitter" 19 20 #include "CodeGenTarget.h" 21 #include "llvm/ADT/DenseSet.h" 22 #include "llvm/ADT/STLExtras.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 <map> 28 #include <string> 29 #include <queue> 30 31 using namespace llvm; 32 33 // -------------------------------------------------------------------- 34 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp 35 36 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput. 37 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer. 38 // 39 // e.g. terms x resource bit combinations that fit in uint32_t: 40 // 4 terms x 8 bits = 32 bits 41 // 3 terms x 10 bits = 30 bits 42 // 2 terms x 16 bits = 32 bits 43 // 44 // e.g. terms x resource bit combinations that fit in uint64_t: 45 // 8 terms x 8 bits = 64 bits 46 // 7 terms x 9 bits = 63 bits 47 // 6 terms x 10 bits = 60 bits 48 // 5 terms x 12 bits = 60 bits 49 // 4 terms x 16 bits = 64 bits <--- current 50 // 3 terms x 21 bits = 63 bits 51 // 2 terms x 32 bits = 64 bits 52 // 53 #define DFA_MAX_RESTERMS 4 // The max # of AND'ed resource terms. 54 #define DFA_MAX_RESOURCES 16 // The max # of resource bits in one term. 55 56 typedef uint64_t DFAInput; 57 typedef int64_t DFAStateInput; 58 #define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable. 59 60 namespace { 61 DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) { 62 return (Inp << DFA_MAX_RESOURCES) | FuncUnits; 63 } 64 65 /// Return the DFAInput for an instruction class input vector. 66 /// This function is used in both DFAPacketizer.cpp and in 67 /// DFAPacketizerEmitter.cpp. 68 DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) { 69 DFAInput InsnInput = 0; 70 assert ((InsnClass.size() <= DFA_MAX_RESTERMS) && 71 "Exceeded maximum number of DFA terms"); 72 for (auto U : InsnClass) 73 InsnInput = addDFAFuncUnits(InsnInput, U); 74 return InsnInput; 75 } 76 } // end anonymous namespace 77 78 // -------------------------------------------------------------------- 79 80 #ifndef NDEBUG 81 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter". 82 // 83 // dbgsInsnClass - When debugging, print instruction class stages. 84 // 85 void dbgsInsnClass(const std::vector<unsigned> &InsnClass); 86 // 87 // dbgsStateInfo - When debugging, print the set of state info. 88 // 89 void dbgsStateInfo(const std::set<unsigned> &stateInfo); 90 // 91 // dbgsIndent - When debugging, indent by the specified amount. 92 // 93 void dbgsIndent(unsigned indent); 94 #endif 95 96 // 97 // class DFAPacketizerEmitter: class that generates and prints out the DFA 98 // for resource tracking. 99 // 100 namespace { 101 class DFAPacketizerEmitter { 102 private: 103 std::string TargetName; 104 // 105 // allInsnClasses is the set of all possible resources consumed by an 106 // InstrStage. 107 // 108 std::vector<std::vector<unsigned>> allInsnClasses; 109 RecordKeeper &Records; 110 111 public: 112 DFAPacketizerEmitter(RecordKeeper &R); 113 114 // 115 // collectAllFuncUnits - Construct a map of function unit names to bits. 116 // 117 int collectAllFuncUnits(std::vector<Record*> &ProcItinList, 118 std::map<std::string, unsigned> &FUNameToBitsMap, 119 int &maxResources, 120 raw_ostream &OS); 121 122 // 123 // collectAllComboFuncs - Construct a map from a combo function unit bit to 124 // the bits of all included functional units. 125 // 126 int collectAllComboFuncs(std::vector<Record*> &ComboFuncList, 127 std::map<std::string, unsigned> &FUNameToBitsMap, 128 std::map<unsigned, unsigned> &ComboBitToBitsMap, 129 raw_ostream &OS); 130 131 // 132 // collectOneInsnClass - Populate allInsnClasses with one instruction class. 133 // 134 int collectOneInsnClass(const std::string &ProcName, 135 std::vector<Record*> &ProcItinList, 136 std::map<std::string, unsigned> &FUNameToBitsMap, 137 Record *ItinData, 138 raw_ostream &OS); 139 140 // 141 // collectAllInsnClasses - Populate allInsnClasses which is a set of units 142 // used in each stage. 143 // 144 int collectAllInsnClasses(const std::string &ProcName, 145 std::vector<Record*> &ProcItinList, 146 std::map<std::string, unsigned> &FUNameToBitsMap, 147 std::vector<Record*> &ItinDataList, 148 int &maxStages, 149 raw_ostream &OS); 150 151 void run(raw_ostream &OS); 152 }; 153 } // end anonymous namespace 154 155 // 156 // 157 // State represents the usage of machine resources if the packet contains 158 // a set of instruction classes. 159 // 160 // Specifically, currentState is a set of bit-masks. 161 // The nth bit in a bit-mask indicates whether the nth resource is being used 162 // by this state. The set of bit-masks in a state represent the different 163 // possible outcomes of transitioning to this state. 164 // For example: consider a two resource architecture: resource L and resource M 165 // with three instruction classes: L, M, and L_or_M. 166 // From the initial state (currentState = 0x00), if we add instruction class 167 // L_or_M we will transition to a state with currentState = [0x01, 0x10]. This 168 // represents the possible resource states that can result from adding a L_or_M 169 // instruction 170 // 171 // Another way of thinking about this transition is we are mapping a NDFA with 172 // two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10]. 173 // 174 // A State instance also contains a collection of transitions from that state: 175 // a map from inputs to new states. 176 // 177 namespace { 178 class State { 179 public: 180 static int currentStateNum; 181 // stateNum is the only member used for equality/ordering, all other members 182 // can be mutated even in const State objects. 183 const int stateNum; 184 mutable bool isInitial; 185 mutable std::set<unsigned> stateInfo; 186 typedef std::map<std::vector<unsigned>, const State *> TransitionMap; 187 mutable TransitionMap Transitions; 188 189 State(); 190 191 bool operator<(const State &s) const { 192 return stateNum < s.stateNum; 193 } 194 195 // 196 // canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass 197 // may be a valid transition from this state i.e., can an instruction of type 198 // InsnClass be added to the packet represented by this state. 199 // 200 // Note that for multiple stages, this quick check does not take into account 201 // any possible resource competition between the stages themselves. That is 202 // enforced in AddInsnClassStages which checks the cross product of all 203 // stages for resource availability (which is a more involved check). 204 // 205 bool canMaybeAddInsnClass(std::vector<unsigned> &InsnClass, 206 std::map<unsigned, unsigned> &ComboBitToBitsMap) const; 207 // 208 // AddInsnClass - Return all combinations of resource reservation 209 // which are possible from this state (PossibleStates). 210 // 211 // PossibleStates is the set of valid resource states that ensue from valid 212 // transitions. 213 // 214 void AddInsnClass(std::vector<unsigned> &InsnClass, 215 std::map<unsigned, unsigned> &ComboBitToBitsMap, 216 std::set<unsigned> &PossibleStates) const; 217 // 218 // AddInsnClassStages - Return all combinations of resource reservation 219 // resulting from the cross product of all stages for this InsnClass 220 // which are possible from this state (PossibleStates). 221 // 222 void AddInsnClassStages(std::vector<unsigned> &InsnClass, 223 std::map<unsigned, unsigned> &ComboBitToBitsMap, 224 unsigned chkstage, unsigned numstages, 225 unsigned prevState, unsigned origState, 226 DenseSet<unsigned> &VisitedResourceStates, 227 std::set<unsigned> &PossibleStates) const; 228 // 229 // addTransition - Add a transition from this state given the input InsnClass 230 // 231 void addTransition(std::vector<unsigned> InsnClass, const State *To) const; 232 // 233 // hasTransition - Returns true if there is a transition from this state 234 // given the input InsnClass 235 // 236 bool hasTransition(std::vector<unsigned> InsnClass) const; 237 }; 238 } // end anonymous namespace 239 240 // 241 // class DFA: deterministic finite automaton for processor resource tracking. 242 // 243 namespace { 244 class DFA { 245 public: 246 DFA(); 247 248 // Set of states. Need to keep this sorted to emit the transition table. 249 typedef std::set<State> StateSet; 250 StateSet states; 251 252 State *currentState; 253 254 // 255 // Modify the DFA. 256 // 257 const State &newState(); 258 259 // 260 // writeTable: Print out a table representing the DFA. 261 // 262 void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName, 263 int numInsnClasses = 0, 264 int maxResources = 0, int numCombos = 0, int maxStages = 0); 265 }; 266 } // end anonymous namespace 267 268 #ifndef NDEBUG 269 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter". 270 // 271 // dbgsInsnClass - When debugging, print instruction class stages. 272 // 273 void dbgsInsnClass(const std::vector<unsigned> &InsnClass) { 274 DEBUG(dbgs() << "InsnClass: "); 275 for (unsigned i = 0; i < InsnClass.size(); ++i) { 276 if (i > 0) { 277 DEBUG(dbgs() << ", "); 278 } 279 DEBUG(dbgs() << "0x" << utohexstr(InsnClass[i])); 280 } 281 DFAInput InsnInput = getDFAInsnInput(InsnClass); 282 DEBUG(dbgs() << " (input: 0x" << utohexstr(InsnInput) << ")"); 283 } 284 285 // 286 // dbgsStateInfo - When debugging, print the set of state info. 287 // 288 void dbgsStateInfo(const std::set<unsigned> &stateInfo) { 289 DEBUG(dbgs() << "StateInfo: "); 290 unsigned i = 0; 291 for (std::set<unsigned>::iterator SI = stateInfo.begin(); 292 SI != stateInfo.end(); ++SI, ++i) { 293 unsigned thisState = *SI; 294 if (i > 0) { 295 DEBUG(dbgs() << ", "); 296 } 297 DEBUG(dbgs() << "0x" << utohexstr(thisState)); 298 } 299 } 300 301 // 302 // dbgsIndent - When debugging, indent by the specified amount. 303 // 304 void dbgsIndent(unsigned indent) { 305 for (unsigned i = 0; i < indent; ++i) { 306 DEBUG(dbgs() << " "); 307 } 308 } 309 #endif // NDEBUG 310 311 // 312 // Constructors and destructors for State and DFA 313 // 314 State::State() : 315 stateNum(currentStateNum++), isInitial(false) {} 316 317 DFA::DFA(): currentState(nullptr) {} 318 319 // 320 // addTransition - Add a transition from this state given the input InsnClass 321 // 322 void State::addTransition(std::vector<unsigned> InsnClass, const State *To) 323 const { 324 assert(!Transitions.count(InsnClass) && 325 "Cannot have multiple transitions for the same input"); 326 Transitions[InsnClass] = To; 327 } 328 329 // 330 // hasTransition - Returns true if there is a transition from this state 331 // given the input InsnClass 332 // 333 bool State::hasTransition(std::vector<unsigned> InsnClass) const { 334 return Transitions.count(InsnClass) > 0; 335 } 336 337 // 338 // AddInsnClass - Return all combinations of resource reservation 339 // which are possible from this state (PossibleStates). 340 // 341 // PossibleStates is the set of valid resource states that ensue from valid 342 // transitions. 343 // 344 void State::AddInsnClass(std::vector<unsigned> &InsnClass, 345 std::map<unsigned, unsigned> &ComboBitToBitsMap, 346 std::set<unsigned> &PossibleStates) const { 347 // 348 // Iterate over all resource states in currentState. 349 // 350 unsigned numstages = InsnClass.size(); 351 assert((numstages > 0) && "InsnClass has no stages"); 352 353 for (std::set<unsigned>::iterator SI = stateInfo.begin(); 354 SI != stateInfo.end(); ++SI) { 355 unsigned thisState = *SI; 356 357 DenseSet<unsigned> VisitedResourceStates; 358 359 DEBUG(dbgs() << " thisState: 0x" << utohexstr(thisState) << "\n"); 360 AddInsnClassStages(InsnClass, ComboBitToBitsMap, 361 numstages - 1, numstages, 362 thisState, thisState, 363 VisitedResourceStates, PossibleStates); 364 } 365 } 366 367 void State::AddInsnClassStages(std::vector<unsigned> &InsnClass, 368 std::map<unsigned, unsigned> &ComboBitToBitsMap, 369 unsigned chkstage, unsigned numstages, 370 unsigned prevState, unsigned origState, 371 DenseSet<unsigned> &VisitedResourceStates, 372 std::set<unsigned> &PossibleStates) const { 373 374 assert((chkstage < numstages) && "AddInsnClassStages: stage out of range"); 375 unsigned thisStage = InsnClass[chkstage]; 376 377 DEBUG({ 378 dbgsIndent((1 + numstages - chkstage) << 1); 379 dbgs() << "AddInsnClassStages " << chkstage << " (0x" 380 << utohexstr(thisStage) << ") from "; 381 dbgsInsnClass(InsnClass); 382 dbgs() << "\n"; 383 }); 384 385 // 386 // Iterate over all possible resources used in thisStage. 387 // For ex: for thisStage = 0x11, all resources = {0x01, 0x10}. 388 // 389 for (unsigned int j = 0; j < DFA_MAX_RESOURCES; ++j) { 390 unsigned resourceMask = (0x1 << j); 391 if (resourceMask & thisStage) { 392 unsigned combo = ComboBitToBitsMap[resourceMask]; 393 if (combo && ((~prevState & combo) != combo)) { 394 DEBUG(dbgs() << "\tSkipped Add 0x" << utohexstr(prevState) 395 << " - combo op 0x" << utohexstr(resourceMask) 396 << " (0x" << utohexstr(combo) <<") cannot be scheduled\n"); 397 continue; 398 } 399 // 400 // For each possible resource used in thisStage, generate the 401 // resource state if that resource was used. 402 // 403 unsigned ResultingResourceState = prevState | resourceMask | combo; 404 DEBUG({ 405 dbgsIndent((2 + numstages - chkstage) << 1); 406 dbgs() << "0x" << utohexstr(prevState) 407 << " | 0x" << utohexstr(resourceMask); 408 if (combo) 409 dbgs() << " | 0x" << utohexstr(combo); 410 dbgs() << " = 0x" << utohexstr(ResultingResourceState) << " "; 411 }); 412 413 // 414 // If this is the final stage for this class 415 // 416 if (chkstage == 0) { 417 // 418 // Check if the resulting resource state can be accommodated in this 419 // packet. 420 // We compute resource OR prevState (originally started as origState). 421 // If the result of the OR is different than origState, it implies 422 // that there is at least one resource that can be used to schedule 423 // thisStage in the current packet. 424 // Insert ResultingResourceState into PossibleStates only if we haven't 425 // processed ResultingResourceState before. 426 // 427 if (ResultingResourceState != prevState) { 428 if (VisitedResourceStates.count(ResultingResourceState) == 0) { 429 VisitedResourceStates.insert(ResultingResourceState); 430 PossibleStates.insert(ResultingResourceState); 431 DEBUG(dbgs() << "\tResultingResourceState: 0x" 432 << utohexstr(ResultingResourceState) << "\n"); 433 } else { 434 DEBUG(dbgs() << "\tSkipped Add - state already seen\n"); 435 } 436 } else { 437 DEBUG(dbgs() << "\tSkipped Add - no final resources available\n"); 438 } 439 } else { 440 // 441 // If the current resource can be accommodated, check the next 442 // stage in InsnClass for available resources. 443 // 444 if (ResultingResourceState != prevState) { 445 DEBUG(dbgs() << "\n"); 446 AddInsnClassStages(InsnClass, ComboBitToBitsMap, 447 chkstage - 1, numstages, 448 ResultingResourceState, origState, 449 VisitedResourceStates, PossibleStates); 450 } else { 451 DEBUG(dbgs() << "\tSkipped Add - no resources available\n"); 452 } 453 } 454 } 455 } 456 } 457 458 // 459 // canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass 460 // may be a valid transition from this state i.e., can an instruction of type 461 // InsnClass be added to the packet represented by this state. 462 // 463 // Note that this routine is performing conservative checks that can be 464 // quickly executed acting as a filter before calling AddInsnClassStages. 465 // Any cases allowed through here will be caught later in AddInsnClassStages 466 // which performs the more expensive exact check. 467 // 468 bool State::canMaybeAddInsnClass(std::vector<unsigned> &InsnClass, 469 std::map<unsigned, unsigned> &ComboBitToBitsMap) const { 470 for (std::set<unsigned>::const_iterator SI = stateInfo.begin(); 471 SI != stateInfo.end(); ++SI) { 472 473 // Check to see if all required resources are available. 474 bool available = true; 475 476 // Inspect each stage independently. 477 // note: This is a conservative check as we aren't checking for 478 // possible resource competition between the stages themselves 479 // The full cross product is examined later in AddInsnClass. 480 for (unsigned i = 0; i < InsnClass.size(); ++i) { 481 unsigned resources = *SI; 482 if ((~resources & InsnClass[i]) == 0) { 483 available = false; 484 break; 485 } 486 // Make sure _all_ resources for a combo function are available. 487 // note: This is a quick conservative check as it won't catch an 488 // unscheduleable combo if this stage is an OR expression 489 // containing a combo. 490 // These cases are caught later in AddInsnClass. 491 unsigned combo = ComboBitToBitsMap[InsnClass[i]]; 492 if (combo && ((~resources & combo) != combo)) { 493 DEBUG(dbgs() << "\tSkipped canMaybeAdd 0x" << utohexstr(resources) 494 << " - combo op 0x" << utohexstr(InsnClass[i]) 495 << " (0x" << utohexstr(combo) <<") cannot be scheduled\n"); 496 available = false; 497 break; 498 } 499 } 500 501 if (available) { 502 return true; 503 } 504 } 505 return false; 506 } 507 508 const State &DFA::newState() { 509 auto IterPair = states.insert(State()); 510 assert(IterPair.second && "State already exists"); 511 return *IterPair.first; 512 } 513 514 int State::currentStateNum = 0; 515 516 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): 517 TargetName(CodeGenTarget(R).getName()), 518 allInsnClasses(), Records(R) {} 519 520 // 521 // writeTableAndAPI - Print out a table representing the DFA and the 522 // associated API to create a DFA packetizer. 523 // 524 // Format: 525 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 526 // transitions. 527 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for 528 // the ith state. 529 // 530 // 531 void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName, 532 int numInsnClasses, 533 int maxResources, int numCombos, int maxStages) { 534 535 unsigned numStates = states.size(); 536 537 DEBUG(dbgs() << "-----------------------------------------------------------------------------\n"); 538 DEBUG(dbgs() << "writeTableAndAPI\n"); 539 DEBUG(dbgs() << "Total states: " << numStates << "\n"); 540 541 OS << "namespace llvm {\n"; 542 543 OS << "\n// Input format:\n"; 544 OS << "#define DFA_MAX_RESTERMS " << DFA_MAX_RESTERMS 545 << "\t// maximum AND'ed resource terms\n"; 546 OS << "#define DFA_MAX_RESOURCES " << DFA_MAX_RESOURCES 547 << "\t// maximum resource bits in one term\n"; 548 549 OS << "\n// " << TargetName << "DFAStateInputTable[][2] = " 550 << "pairs of <Input, NextState> for all valid\n"; 551 OS << "// transitions.\n"; 552 OS << "// " << numStates << "\tstates\n"; 553 OS << "// " << numInsnClasses << "\tinstruction classes\n"; 554 OS << "// " << maxResources << "\tresources max\n"; 555 OS << "// " << numCombos << "\tcombo resources\n"; 556 OS << "// " << maxStages << "\tstages max\n"; 557 OS << "const " << DFA_TBLTYPE << " " 558 << TargetName << "DFAStateInputTable[][2] = {\n"; 559 560 // This table provides a map to the beginning of the transitions for State s 561 // in DFAStateInputTable. 562 std::vector<int> StateEntry(numStates+1); 563 static const std::string SentinelEntry = "{-1, -1}"; 564 565 // Tracks the total valid transitions encountered so far. It is used 566 // to construct the StateEntry table. 567 int ValidTransitions = 0; 568 DFA::StateSet::iterator SI = states.begin(); 569 for (unsigned i = 0; i < numStates; ++i, ++SI) { 570 assert ((SI->stateNum == (int) i) && "Mismatch in state numbers"); 571 StateEntry[i] = ValidTransitions; 572 for (State::TransitionMap::iterator 573 II = SI->Transitions.begin(), IE = SI->Transitions.end(); 574 II != IE; ++II) { 575 OS << "{0x" << utohexstr(getDFAInsnInput(II->first)) << ", " 576 << II->second->stateNum 577 << "},\t"; 578 } 579 ValidTransitions += SI->Transitions.size(); 580 581 // If there are no valid transitions from this stage, we need a sentinel 582 // transition. 583 if (ValidTransitions == StateEntry[i]) { 584 OS << SentinelEntry << ",\t"; 585 ++ValidTransitions; 586 } 587 588 OS << " // state " << i << ": " << StateEntry[i]; 589 if (StateEntry[i] != (ValidTransitions-1)) { // More than one transition. 590 OS << "-" << (ValidTransitions-1); 591 } 592 OS << "\n"; 593 } 594 595 // Print out a sentinel entry at the end of the StateInputTable. This is 596 // needed to iterate over StateInputTable in DFAPacketizer::ReadTable() 597 OS << SentinelEntry << "\t"; 598 OS << " // state " << numStates << ": " << ValidTransitions; 599 OS << "\n"; 600 601 OS << "};\n\n"; 602 OS << "// " << TargetName << "DFAStateEntryTable[i] = " 603 << "Index of the first entry in DFAStateInputTable for\n"; 604 OS << "// " 605 << "the ith state.\n"; 606 OS << "// " << numStates << " states\n"; 607 OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; 608 609 // Multiply i by 2 since each entry in DFAStateInputTable is a set of 610 // two numbers. 611 unsigned lastState = 0; 612 for (unsigned i = 0; i < numStates; ++i) { 613 if (i && ((i % 10) == 0)) { 614 lastState = i-1; 615 OS << " // states " << (i-10) << ":" << lastState << "\n"; 616 } 617 OS << StateEntry[i] << ", "; 618 } 619 620 // Print out the index to the sentinel entry in StateInputTable 621 OS << ValidTransitions << ", "; 622 OS << " // states " << (lastState+1) << ":" << numStates << "\n"; 623 624 OS << "};\n"; 625 OS << "} // namespace\n"; 626 627 // 628 // Emit DFA Packetizer tables if the target is a VLIW machine. 629 // 630 std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 631 OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; 632 OS << "namespace llvm {\n"; 633 OS << "DFAPacketizer *" << SubTargetClassName << "::" 634 << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" 635 << " return new DFAPacketizer(IID, " << TargetName 636 << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; 637 OS << "} // End llvm namespace \n"; 638 } 639 640 // 641 // collectAllFuncUnits - Construct a map of function unit names to bits. 642 // 643 int DFAPacketizerEmitter::collectAllFuncUnits( 644 std::vector<Record*> &ProcItinList, 645 std::map<std::string, unsigned> &FUNameToBitsMap, 646 int &maxFUs, 647 raw_ostream &OS) { 648 DEBUG(dbgs() << "-----------------------------------------------------------------------------\n"); 649 DEBUG(dbgs() << "collectAllFuncUnits"); 650 DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n"); 651 652 int totalFUs = 0; 653 // Parse functional units for all the itineraries. 654 for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { 655 Record *Proc = ProcItinList[i]; 656 std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); 657 658 DEBUG(dbgs() << " FU:" << i 659 << " (" << FUs.size() << " FUs) " 660 << Proc->getName()); 661 662 663 // Convert macros to bits for each stage. 664 unsigned numFUs = FUs.size(); 665 for (unsigned j = 0; j < numFUs; ++j) { 666 assert ((j < DFA_MAX_RESOURCES) && 667 "Exceeded maximum number of representable resources"); 668 unsigned FuncResources = (unsigned) (1U << j); 669 FUNameToBitsMap[FUs[j]->getName()] = FuncResources; 670 DEBUG(dbgs() << " " << FUs[j]->getName() 671 << ":0x" << utohexstr(FuncResources)); 672 } 673 if (((int) numFUs) > maxFUs) { 674 maxFUs = numFUs; 675 } 676 totalFUs += numFUs; 677 DEBUG(dbgs() << "\n"); 678 } 679 return totalFUs; 680 } 681 682 // 683 // collectAllComboFuncs - Construct a map from a combo function unit bit to 684 // the bits of all included functional units. 685 // 686 int DFAPacketizerEmitter::collectAllComboFuncs( 687 std::vector<Record*> &ComboFuncList, 688 std::map<std::string, unsigned> &FUNameToBitsMap, 689 std::map<unsigned, unsigned> &ComboBitToBitsMap, 690 raw_ostream &OS) { 691 DEBUG(dbgs() << "-----------------------------------------------------------------------------\n"); 692 DEBUG(dbgs() << "collectAllComboFuncs"); 693 DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n"); 694 695 int numCombos = 0; 696 for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) { 697 Record *Func = ComboFuncList[i]; 698 std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD"); 699 700 DEBUG(dbgs() << " CFD:" << i 701 << " (" << FUs.size() << " combo FUs) " 702 << Func->getName() << "\n"); 703 704 // Convert macros to bits for each stage. 705 for (unsigned j = 0, N = FUs.size(); j < N; ++j) { 706 assert ((j < DFA_MAX_RESOURCES) && 707 "Exceeded maximum number of DFA resources"); 708 Record *FuncData = FUs[j]; 709 Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc"); 710 const std::vector<Record*> &FuncList = 711 FuncData->getValueAsListOfDefs("FuncList"); 712 const std::string &ComboFuncName = ComboFunc->getName(); 713 unsigned ComboBit = FUNameToBitsMap[ComboFuncName]; 714 unsigned ComboResources = ComboBit; 715 DEBUG(dbgs() << " combo: " << ComboFuncName 716 << ":0x" << utohexstr(ComboResources) << "\n"); 717 for (unsigned k = 0, M = FuncList.size(); k < M; ++k) { 718 std::string FuncName = FuncList[k]->getName(); 719 unsigned FuncResources = FUNameToBitsMap[FuncName]; 720 DEBUG(dbgs() << " " << FuncName 721 << ":0x" << utohexstr(FuncResources) << "\n"); 722 ComboResources |= FuncResources; 723 } 724 ComboBitToBitsMap[ComboBit] = ComboResources; 725 numCombos++; 726 DEBUG(dbgs() << " => combo bits: " << ComboFuncName << ":0x" 727 << utohexstr(ComboBit) << " = 0x" 728 << utohexstr(ComboResources) << "\n"); 729 } 730 } 731 return numCombos; 732 } 733 734 // 735 // collectOneInsnClass - Populate allInsnClasses with one instruction class 736 // 737 int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName, 738 std::vector<Record*> &ProcItinList, 739 std::map<std::string, unsigned> &FUNameToBitsMap, 740 Record *ItinData, 741 raw_ostream &OS) { 742 const std::vector<Record*> &StageList = 743 ItinData->getValueAsListOfDefs("Stages"); 744 745 // The number of stages. 746 unsigned NStages = StageList.size(); 747 748 DEBUG(dbgs() << " " << ItinData->getValueAsDef("TheClass")->getName() 749 << "\n"); 750 751 std::vector<unsigned> UnitBits; 752 753 // Compute the bitwise or of each unit used in this stage. 754 for (unsigned i = 0; i < NStages; ++i) { 755 const Record *Stage = StageList[i]; 756 757 // Get unit list. 758 const std::vector<Record*> &UnitList = 759 Stage->getValueAsListOfDefs("Units"); 760 761 DEBUG(dbgs() << " stage:" << i 762 << " [" << UnitList.size() << " units]:"); 763 unsigned dbglen = 26; // cursor after stage dbgs 764 765 // Compute the bitwise or of each unit used in this stage. 766 unsigned UnitBitValue = 0; 767 for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { 768 // Conduct bitwise or. 769 std::string UnitName = UnitList[j]->getName(); 770 DEBUG(dbgs() << " " << j << ":" << UnitName); 771 dbglen += 3 + UnitName.length(); 772 assert(FUNameToBitsMap.count(UnitName)); 773 UnitBitValue |= FUNameToBitsMap[UnitName]; 774 } 775 776 if (UnitBitValue != 0) 777 UnitBits.push_back(UnitBitValue); 778 779 while (dbglen <= 64) { // line up bits dbgs 780 dbglen += 8; 781 DEBUG(dbgs() << "\t"); 782 } 783 DEBUG(dbgs() << " (bits: 0x" << utohexstr(UnitBitValue) << ")\n"); 784 } 785 786 if (UnitBits.size() > 0) 787 allInsnClasses.push_back(UnitBits); 788 789 DEBUG({ 790 dbgs() << " "; 791 dbgsInsnClass(UnitBits); 792 dbgs() << "\n"; 793 }); 794 795 return NStages; 796 } 797 798 // 799 // collectAllInsnClasses - Populate allInsnClasses which is a set of units 800 // used in each stage. 801 // 802 int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName, 803 std::vector<Record*> &ProcItinList, 804 std::map<std::string, unsigned> &FUNameToBitsMap, 805 std::vector<Record*> &ItinDataList, 806 int &maxStages, 807 raw_ostream &OS) { 808 // Collect all instruction classes. 809 unsigned M = ItinDataList.size(); 810 811 int numInsnClasses = 0; 812 DEBUG(dbgs() << "-----------------------------------------------------------------------------\n" 813 << "collectAllInsnClasses " 814 << ProcName 815 << " (" << M << " classes)\n"); 816 817 // Collect stages for each instruction class for all itinerary data 818 for (unsigned j = 0; j < M; j++) { 819 Record *ItinData = ItinDataList[j]; 820 int NStages = collectOneInsnClass(ProcName, ProcItinList, 821 FUNameToBitsMap, ItinData, OS); 822 if (NStages > maxStages) { 823 maxStages = NStages; 824 } 825 numInsnClasses++; 826 } 827 return numInsnClasses; 828 } 829 830 // 831 // Run the worklist algorithm to generate the DFA. 832 // 833 void DFAPacketizerEmitter::run(raw_ostream &OS) { 834 835 // Collect processor iteraries. 836 std::vector<Record*> ProcItinList = 837 Records.getAllDerivedDefinitions("ProcessorItineraries"); 838 839 // 840 // Collect the Functional units. 841 // 842 std::map<std::string, unsigned> FUNameToBitsMap; 843 int maxResources = 0; 844 collectAllFuncUnits(ProcItinList, 845 FUNameToBitsMap, maxResources, OS); 846 847 // 848 // Collect the Combo Functional units. 849 // 850 std::map<unsigned, unsigned> ComboBitToBitsMap; 851 std::vector<Record*> ComboFuncList = 852 Records.getAllDerivedDefinitions("ComboFuncUnits"); 853 int numCombos = collectAllComboFuncs(ComboFuncList, 854 FUNameToBitsMap, ComboBitToBitsMap, OS); 855 856 // 857 // Collect the itineraries. 858 // 859 int maxStages = 0; 860 int numInsnClasses = 0; 861 for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { 862 Record *Proc = ProcItinList[i]; 863 864 // Get processor itinerary name. 865 const std::string &ProcName = Proc->getName(); 866 867 // Skip default. 868 if (ProcName == "NoItineraries") 869 continue; 870 871 // Sanity check for at least one instruction itinerary class. 872 unsigned NItinClasses = 873 Records.getAllDerivedDefinitions("InstrItinClass").size(); 874 if (NItinClasses == 0) 875 return; 876 877 // Get itinerary data list. 878 std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); 879 880 // Collect all instruction classes 881 numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList, 882 FUNameToBitsMap, ItinDataList, maxStages, OS); 883 } 884 885 // 886 // Run a worklist algorithm to generate the DFA. 887 // 888 DFA D; 889 const State *Initial = &D.newState(); 890 Initial->isInitial = true; 891 Initial->stateInfo.insert(0x0); 892 SmallVector<const State*, 32> WorkList; 893 // std::queue<State*> WorkList; 894 std::map<std::set<unsigned>, const State*> Visited; 895 896 WorkList.push_back(Initial); 897 898 // 899 // Worklist algorithm to create a DFA for processor resource tracking. 900 // C = {set of InsnClasses} 901 // Begin with initial node in worklist. Initial node does not have 902 // any consumed resources, 903 // ResourceState = 0x0 904 // Visited = {} 905 // While worklist != empty 906 // S = first element of worklist 907 // For every instruction class C 908 // if we can accommodate C in S: 909 // S' = state with resource states = {S Union C} 910 // Add a new transition: S x C -> S' 911 // If S' is not in Visited: 912 // Add S' to worklist 913 // Add S' to Visited 914 // 915 while (!WorkList.empty()) { 916 const State *current = WorkList.pop_back_val(); 917 DEBUG({ 918 dbgs() << "---------------------\n"; 919 dbgs() << "Processing state: " << current->stateNum << " - "; 920 dbgsStateInfo(current->stateInfo); 921 dbgs() << "\n"; 922 }); 923 for (unsigned i = 0; i < allInsnClasses.size(); i++) { 924 std::vector<unsigned> InsnClass = allInsnClasses[i]; 925 DEBUG({ 926 dbgs() << i << " "; 927 dbgsInsnClass(InsnClass); 928 dbgs() << "\n"; 929 }); 930 931 std::set<unsigned> NewStateResources; 932 // 933 // If we haven't already created a transition for this input 934 // and the state can accommodate this InsnClass, create a transition. 935 // 936 if (!current->hasTransition(InsnClass) && 937 current->canMaybeAddInsnClass(InsnClass, ComboBitToBitsMap)) { 938 const State *NewState = nullptr; 939 current->AddInsnClass(InsnClass, ComboBitToBitsMap, NewStateResources); 940 if (NewStateResources.size() == 0) { 941 DEBUG(dbgs() << " Skipped - no new states generated\n"); 942 continue; 943 } 944 945 DEBUG({ 946 dbgs() << "\t"; 947 dbgsStateInfo(NewStateResources); 948 dbgs() << "\n"; 949 }); 950 951 // 952 // If we have seen this state before, then do not create a new state. 953 // 954 auto VI = Visited.find(NewStateResources); 955 if (VI != Visited.end()) { 956 NewState = VI->second; 957 DEBUG({ 958 dbgs() << "\tFound existing state: " << NewState->stateNum 959 << " - "; 960 dbgsStateInfo(NewState->stateInfo); 961 dbgs() << "\n"; 962 }); 963 } else { 964 NewState = &D.newState(); 965 NewState->stateInfo = NewStateResources; 966 Visited[NewStateResources] = NewState; 967 WorkList.push_back(NewState); 968 DEBUG({ 969 dbgs() << "\tAccepted new state: " << NewState->stateNum << " - "; 970 dbgsStateInfo(NewState->stateInfo); 971 dbgs() << "\n"; 972 }); 973 } 974 975 current->addTransition(InsnClass, NewState); 976 } 977 } 978 } 979 980 // Print out the table. 981 D.writeTableAndAPI(OS, TargetName, 982 numInsnClasses, maxResources, numCombos, maxStages); 983 } 984 985 namespace llvm { 986 987 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { 988 emitSourceFileHeader("Target DFA Packetizer Tables", OS); 989 DFAPacketizerEmitter(RK).run(OS); 990 } 991 992 } // end namespaec llvm 993