DFAPacketizerEmitter.cpp revision 239462
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#include "CodeGenTarget.h" 19#include "llvm/ADT/DenseSet.h" 20#include "llvm/TableGen/Record.h" 21#include "llvm/TableGen/TableGenBackend.h" 22#include <list> 23#include <map> 24#include <string> 25using namespace llvm; 26 27// 28// class DFAPacketizerEmitter: class that generates and prints out the DFA 29// for resource tracking. 30// 31namespace { 32class DFAPacketizerEmitter { 33private: 34 std::string TargetName; 35 // 36 // allInsnClasses is the set of all possible resources consumed by an 37 // InstrStage. 38 // 39 DenseSet<unsigned> allInsnClasses; 40 RecordKeeper &Records; 41 42public: 43 DFAPacketizerEmitter(RecordKeeper &R); 44 45 // 46 // collectAllInsnClasses: Populate allInsnClasses which is a set of units 47 // used in each stage. 48 // 49 void collectAllInsnClasses(const std::string &Name, 50 Record *ItinData, 51 unsigned &NStages, 52 raw_ostream &OS); 53 54 void run(raw_ostream &OS); 55}; 56} // End anonymous namespace. 57 58// 59// 60// State represents the usage of machine resources if the packet contains 61// a set of instruction classes. 62// 63// Specifically, currentState is a set of bit-masks. 64// The nth bit in a bit-mask indicates whether the nth resource is being used 65// by this state. The set of bit-masks in a state represent the different 66// possible outcomes of transitioning to this state. 67// For example: consider a two resource architecture: resource L and resource M 68// with three instruction classes: L, M, and L_or_M. 69// From the initial state (currentState = 0x00), if we add instruction class 70// L_or_M we will transition to a state with currentState = [0x01, 0x10]. This 71// represents the possible resource states that can result from adding a L_or_M 72// instruction 73// 74// Another way of thinking about this transition is we are mapping a NDFA with 75// two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10]. 76// 77// 78namespace { 79class State { 80 public: 81 static int currentStateNum; 82 int stateNum; 83 bool isInitial; 84 std::set<unsigned> stateInfo; 85 86 State(); 87 State(const State &S); 88 89 // 90 // canAddInsnClass - Returns true if an instruction of type InsnClass is a 91 // valid transition from this state, i.e., can an instruction of type InsnClass 92 // be added to the packet represented by this state. 93 // 94 // PossibleStates is the set of valid resource states that ensue from valid 95 // transitions. 96 // 97 bool canAddInsnClass(unsigned InsnClass) const; 98 // 99 // AddInsnClass - Return all combinations of resource reservation 100 // which are possible from this state (PossibleStates). 101 // 102 void AddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates); 103}; 104} // End anonymous namespace. 105 106 107namespace { 108struct Transition { 109 public: 110 static int currentTransitionNum; 111 int transitionNum; 112 State *from; 113 unsigned input; 114 State *to; 115 116 Transition(State *from_, unsigned input_, State *to_); 117}; 118} // End anonymous namespace. 119 120 121// 122// Comparators to keep set of states sorted. 123// 124namespace { 125struct ltState { 126 bool operator()(const State *s1, const State *s2) const; 127}; 128 129struct ltTransition { 130 bool operator()(const Transition *s1, const Transition *s2) const; 131}; 132} // End anonymous namespace. 133 134 135// 136// class DFA: deterministic finite automaton for processor resource tracking. 137// 138namespace { 139class DFA { 140public: 141 DFA(); 142 143 // Set of states. Need to keep this sorted to emit the transition table. 144 std::set<State*, ltState> states; 145 146 // Map from a state to the list of transitions with that state as source. 147 std::map<State*, std::set<Transition*, ltTransition>, ltState> 148 stateTransitions; 149 State *currentState; 150 151 // Highest valued Input seen. 152 unsigned LargestInput; 153 154 // 155 // Modify the DFA. 156 // 157 void initialize(); 158 void addState(State *); 159 void addTransition(Transition *); 160 161 // 162 // getTransition - Return the state when a transition is made from 163 // State From with Input I. If a transition is not found, return NULL. 164 // 165 State *getTransition(State *, unsigned); 166 167 // 168 // isValidTransition: Predicate that checks if there is a valid transition 169 // from state From on input InsnClass. 170 // 171 bool isValidTransition(State *From, unsigned InsnClass); 172 173 // 174 // writeTable: Print out a table representing the DFA. 175 // 176 void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName); 177}; 178} // End anonymous namespace. 179 180 181// 182// Constructors for State, Transition, and DFA 183// 184State::State() : 185 stateNum(currentStateNum++), isInitial(false) {} 186 187 188State::State(const State &S) : 189 stateNum(currentStateNum++), isInitial(S.isInitial), 190 stateInfo(S.stateInfo) {} 191 192 193Transition::Transition(State *from_, unsigned input_, State *to_) : 194 transitionNum(currentTransitionNum++), from(from_), input(input_), 195 to(to_) {} 196 197 198DFA::DFA() : 199 LargestInput(0) {} 200 201 202bool ltState::operator()(const State *s1, const State *s2) const { 203 return (s1->stateNum < s2->stateNum); 204} 205 206bool ltTransition::operator()(const Transition *s1, const Transition *s2) const { 207 return (s1->input < s2->input); 208} 209 210// 211// AddInsnClass - Return all combinations of resource reservation 212// which are possible from this state (PossibleStates). 213// 214void State::AddInsnClass(unsigned InsnClass, 215 std::set<unsigned> &PossibleStates) { 216 // 217 // Iterate over all resource states in currentState. 218 // 219 220 for (std::set<unsigned>::iterator SI = stateInfo.begin(); 221 SI != stateInfo.end(); ++SI) { 222 unsigned thisState = *SI; 223 224 // 225 // Iterate over all possible resources used in InsnClass. 226 // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}. 227 // 228 229 DenseSet<unsigned> VisitedResourceStates; 230 for (unsigned int j = 0; j < sizeof(InsnClass) * 8; ++j) { 231 if ((0x1 << j) & InsnClass) { 232 // 233 // For each possible resource used in InsnClass, generate the 234 // resource state if that resource was used. 235 // 236 unsigned ResultingResourceState = thisState | (0x1 << j); 237 // 238 // Check if the resulting resource state can be accommodated in this 239 // packet. 240 // We compute ResultingResourceState OR thisState. 241 // If the result of the OR is different than thisState, it implies 242 // that there is at least one resource that can be used to schedule 243 // InsnClass in the current packet. 244 // Insert ResultingResourceState into PossibleStates only if we haven't 245 // processed ResultingResourceState before. 246 // 247 if ((ResultingResourceState != thisState) && 248 (VisitedResourceStates.count(ResultingResourceState) == 0)) { 249 VisitedResourceStates.insert(ResultingResourceState); 250 PossibleStates.insert(ResultingResourceState); 251 } 252 } 253 } 254 } 255 256} 257 258 259// 260// canAddInsnClass - Quickly verifies if an instruction of type InsnClass is a 261// valid transition from this state i.e., can an instruction of type InsnClass 262// be added to the packet represented by this state. 263// 264bool State::canAddInsnClass(unsigned InsnClass) const { 265 for (std::set<unsigned>::const_iterator SI = stateInfo.begin(); 266 SI != stateInfo.end(); ++SI) { 267 if (~*SI & InsnClass) 268 return true; 269 } 270 return false; 271} 272 273 274void DFA::initialize() { 275 currentState->isInitial = true; 276} 277 278 279void DFA::addState(State *S) { 280 assert(!states.count(S) && "State already exists"); 281 states.insert(S); 282} 283 284 285void DFA::addTransition(Transition *T) { 286 // Update LargestInput. 287 if (T->input > LargestInput) 288 LargestInput = T->input; 289 290 // Add the new transition. 291 bool Added = stateTransitions[T->from].insert(T).second; 292 assert(Added && "Cannot have multiple states for the same input"); 293 (void)Added; 294} 295 296 297// 298// getTransition - Return the state when a transition is made from 299// State From with Input I. If a transition is not found, return NULL. 300// 301State *DFA::getTransition(State *From, unsigned I) { 302 // Do we have a transition from state From? 303 if (!stateTransitions.count(From)) 304 return NULL; 305 306 // Do we have a transition from state From with Input I? 307 Transition TVal(NULL, I, NULL); 308 // Do not count this temporal instance 309 Transition::currentTransitionNum--; 310 std::set<Transition*, ltTransition>::iterator T = 311 stateTransitions[From].find(&TVal); 312 if (T != stateTransitions[From].end()) 313 return (*T)->to; 314 315 return NULL; 316} 317 318 319bool DFA::isValidTransition(State *From, unsigned InsnClass) { 320 return (getTransition(From, InsnClass) != NULL); 321} 322 323 324int State::currentStateNum = 0; 325int Transition::currentTransitionNum = 0; 326 327DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): 328 TargetName(CodeGenTarget(R).getName()), 329 allInsnClasses(), Records(R) {} 330 331 332// 333// writeTableAndAPI - Print out a table representing the DFA and the 334// associated API to create a DFA packetizer. 335// 336// Format: 337// DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 338// transitions. 339// DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for 340// the ith state. 341// 342// 343void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { 344 std::set<State*, ltState>::iterator SI = states.begin(); 345 // This table provides a map to the beginning of the transitions for State s 346 // in DFAStateInputTable. 347 std::vector<int> StateEntry(states.size()); 348 349 OS << "namespace llvm {\n\n"; 350 OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n"; 351 352 // Tracks the total valid transitions encountered so far. It is used 353 // to construct the StateEntry table. 354 int ValidTransitions = 0; 355 for (unsigned i = 0; i < states.size(); ++i, ++SI) { 356 StateEntry[i] = ValidTransitions; 357 for (unsigned j = 0; j <= LargestInput; ++j) { 358 assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers"); 359 State *To = getTransition(*SI, j); 360 if (To == NULL) 361 continue; 362 363 OS << "{" << j << ", " 364 << To->stateNum 365 << "}, "; 366 ++ValidTransitions; 367 } 368 369 // If there are no valid transitions from this stage, we need a sentinel 370 // transition. 371 if (ValidTransitions == StateEntry[i]) { 372 OS << "{-1, -1},"; 373 ++ValidTransitions; 374 } 375 376 OS << "\n"; 377 } 378 OS << "};\n\n"; 379 OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; 380 381 // Multiply i by 2 since each entry in DFAStateInputTable is a set of 382 // two numbers. 383 for (unsigned i = 0; i < states.size(); ++i) 384 OS << StateEntry[i] << ", "; 385 386 OS << "\n};\n"; 387 OS << "} // namespace\n"; 388 389 390 // 391 // Emit DFA Packetizer tables if the target is a VLIW machine. 392 // 393 std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 394 OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; 395 OS << "namespace llvm {\n"; 396 OS << "DFAPacketizer *" << SubTargetClassName << "::" 397 << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" 398 << " return new DFAPacketizer(IID, " << TargetName 399 << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; 400 OS << "} // End llvm namespace \n"; 401} 402 403 404// 405// collectAllInsnClasses - Populate allInsnClasses which is a set of units 406// used in each stage. 407// 408void DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name, 409 Record *ItinData, 410 unsigned &NStages, 411 raw_ostream &OS) { 412 // Collect processor itineraries. 413 std::vector<Record*> ProcItinList = 414 Records.getAllDerivedDefinitions("ProcessorItineraries"); 415 416 // If just no itinerary then don't bother. 417 if (ProcItinList.size() < 2) 418 return; 419 std::map<std::string, unsigned> NameToBitsMap; 420 421 // Parse functional units for all the itineraries. 422 for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { 423 Record *Proc = ProcItinList[i]; 424 std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); 425 426 // Convert macros to bits for each stage. 427 for (unsigned i = 0, N = FUs.size(); i < N; ++i) 428 NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); 429 } 430 431 const std::vector<Record*> &StageList = 432 ItinData->getValueAsListOfDefs("Stages"); 433 434 // The number of stages. 435 NStages = StageList.size(); 436 437 // For each unit. 438 unsigned UnitBitValue = 0; 439 440 // Compute the bitwise or of each unit used in this stage. 441 for (unsigned i = 0; i < NStages; ++i) { 442 const Record *Stage = StageList[i]; 443 444 // Get unit list. 445 const std::vector<Record*> &UnitList = 446 Stage->getValueAsListOfDefs("Units"); 447 448 for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { 449 // Conduct bitwise or. 450 std::string UnitName = UnitList[j]->getName(); 451 assert(NameToBitsMap.count(UnitName)); 452 UnitBitValue |= NameToBitsMap[UnitName]; 453 } 454 455 if (UnitBitValue != 0) 456 allInsnClasses.insert(UnitBitValue); 457 } 458} 459 460 461// 462// Run the worklist algorithm to generate the DFA. 463// 464void DFAPacketizerEmitter::run(raw_ostream &OS) { 465 466 // Collect processor iteraries. 467 std::vector<Record*> ProcItinList = 468 Records.getAllDerivedDefinitions("ProcessorItineraries"); 469 470 // 471 // Collect the instruction classes. 472 // 473 for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { 474 Record *Proc = ProcItinList[i]; 475 476 // Get processor itinerary name. 477 const std::string &Name = Proc->getName(); 478 479 // Skip default. 480 if (Name == "NoItineraries") 481 continue; 482 483 // Sanity check for at least one instruction itinerary class. 484 unsigned NItinClasses = 485 Records.getAllDerivedDefinitions("InstrItinClass").size(); 486 if (NItinClasses == 0) 487 return; 488 489 // Get itinerary data list. 490 std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); 491 492 // Collect instruction classes for all itinerary data. 493 for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { 494 Record *ItinData = ItinDataList[j]; 495 unsigned NStages; 496 collectAllInsnClasses(Name, ItinData, NStages, OS); 497 } 498 } 499 500 501 // 502 // Run a worklist algorithm to generate the DFA. 503 // 504 DFA D; 505 State *Initial = new State; 506 Initial->isInitial = true; 507 Initial->stateInfo.insert(0x0); 508 D.addState(Initial); 509 SmallVector<State*, 32> WorkList; 510 std::map<std::set<unsigned>, State*> Visited; 511 512 WorkList.push_back(Initial); 513 514 // 515 // Worklist algorithm to create a DFA for processor resource tracking. 516 // C = {set of InsnClasses} 517 // Begin with initial node in worklist. Initial node does not have 518 // any consumed resources, 519 // ResourceState = 0x0 520 // Visited = {} 521 // While worklist != empty 522 // S = first element of worklist 523 // For every instruction class C 524 // if we can accommodate C in S: 525 // S' = state with resource states = {S Union C} 526 // Add a new transition: S x C -> S' 527 // If S' is not in Visited: 528 // Add S' to worklist 529 // Add S' to Visited 530 // 531 while (!WorkList.empty()) { 532 State *current = WorkList.pop_back_val(); 533 for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(), 534 CE = allInsnClasses.end(); CI != CE; ++CI) { 535 unsigned InsnClass = *CI; 536 537 std::set<unsigned> NewStateResources; 538 // 539 // If we haven't already created a transition for this input 540 // and the state can accommodate this InsnClass, create a transition. 541 // 542 if (!D.getTransition(current, InsnClass) && 543 current->canAddInsnClass(InsnClass)) { 544 State *NewState = NULL; 545 current->AddInsnClass(InsnClass, NewStateResources); 546 assert(NewStateResources.size() && "New states must be generated"); 547 548 // 549 // If we have seen this state before, then do not create a new state. 550 // 551 // 552 std::map<std::set<unsigned>, State*>::iterator VI; 553 if ((VI = Visited.find(NewStateResources)) != Visited.end()) 554 NewState = VI->second; 555 else { 556 NewState = new State; 557 NewState->stateInfo = NewStateResources; 558 D.addState(NewState); 559 Visited[NewStateResources] = NewState; 560 WorkList.push_back(NewState); 561 } 562 563 Transition *NewTransition = new Transition(current, InsnClass, 564 NewState); 565 D.addTransition(NewTransition); 566 } 567 } 568 } 569 570 // Print out the table. 571 D.writeTableAndAPI(OS, TargetName); 572} 573 574namespace llvm { 575 576void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { 577 emitSourceFileHeader("Target DFA Packetizer Tables", OS); 578 DFAPacketizerEmitter(RK).run(OS); 579} 580 581} // End llvm namespace 582