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