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 DFA::StateSet::iterator SI = states.begin(); 283 // This table provides a map to the beginning of the transitions for State s 284 // in DFAStateInputTable. 285 std::vector<int> StateEntry(states.size()); 286 287 OS << "namespace llvm {\n\n"; 288 OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n"; 289 290 // Tracks the total valid transitions encountered so far. It is used 291 // to construct the StateEntry table. 292 int ValidTransitions = 0; 293 for (unsigned i = 0; i < states.size(); ++i, ++SI) { 294 assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers"); 295 StateEntry[i] = ValidTransitions; 296 for (State::TransitionMap::iterator 297 II = (*SI)->Transitions.begin(), IE = (*SI)->Transitions.end(); 298 II != IE; ++II) { 299 OS << "{" << II->first << ", " 300 << II->second->stateNum 301 << "}, "; 302 } 303 ValidTransitions += (*SI)->Transitions.size(); 304 305 // If there are no valid transitions from this stage, we need a sentinel 306 // transition. 307 if (ValidTransitions == StateEntry[i]) { 308 OS << "{-1, -1},"; 309 ++ValidTransitions; 310 } 311 312 OS << "\n"; 313 } 314 OS << "};\n\n"; 315 OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; 316 317 // Multiply i by 2 since each entry in DFAStateInputTable is a set of 318 // two numbers. 319 for (unsigned i = 0; i < states.size(); ++i) 320 OS << StateEntry[i] << ", "; 321 322 OS << "\n};\n"; 323 OS << "} // namespace\n"; 324 325 326 // 327 // Emit DFA Packetizer tables if the target is a VLIW machine. 328 // 329 std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 330 OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; 331 OS << "namespace llvm {\n"; 332 OS << "DFAPacketizer *" << SubTargetClassName << "::" 333 << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" 334 << " return new DFAPacketizer(IID, " << TargetName 335 << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; 336 OS << "} // End llvm namespace \n"; 337} 338 339 340// 341// collectAllInsnClasses - Populate allInsnClasses which is a set of units 342// used in each stage. 343// 344void DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name, 345 Record *ItinData, 346 unsigned &NStages, 347 raw_ostream &OS) { 348 // Collect processor itineraries. 349 std::vector<Record*> ProcItinList = 350 Records.getAllDerivedDefinitions("ProcessorItineraries"); 351 352 // If just no itinerary then don't bother. 353 if (ProcItinList.size() < 2) 354 return; 355 std::map<std::string, unsigned> NameToBitsMap; 356 357 // Parse functional units for all the itineraries. 358 for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { 359 Record *Proc = ProcItinList[i]; 360 std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); 361 362 // Convert macros to bits for each stage. 363 for (unsigned i = 0, N = FUs.size(); i < N; ++i) 364 NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); 365 } 366 367 const std::vector<Record*> &StageList = 368 ItinData->getValueAsListOfDefs("Stages"); 369 370 // The number of stages. 371 NStages = StageList.size(); 372 373 // For each unit. 374 unsigned UnitBitValue = 0; 375 376 // Compute the bitwise or of each unit used in this stage. 377 for (unsigned i = 0; i < NStages; ++i) { 378 const Record *Stage = StageList[i]; 379 380 // Get unit list. 381 const std::vector<Record*> &UnitList = 382 Stage->getValueAsListOfDefs("Units"); 383 384 for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { 385 // Conduct bitwise or. 386 std::string UnitName = UnitList[j]->getName(); 387 assert(NameToBitsMap.count(UnitName)); 388 UnitBitValue |= NameToBitsMap[UnitName]; 389 } 390 391 if (UnitBitValue != 0) 392 allInsnClasses.insert(UnitBitValue); 393 } 394} 395 396 397// 398// Run the worklist algorithm to generate the DFA. 399// 400void DFAPacketizerEmitter::run(raw_ostream &OS) { 401 402 // Collect processor iteraries. 403 std::vector<Record*> ProcItinList = 404 Records.getAllDerivedDefinitions("ProcessorItineraries"); 405 406 // 407 // Collect the instruction classes. 408 // 409 for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { 410 Record *Proc = ProcItinList[i]; 411 412 // Get processor itinerary name. 413 const std::string &Name = Proc->getName(); 414 415 // Skip default. 416 if (Name == "NoItineraries") 417 continue; 418 419 // Sanity check for at least one instruction itinerary class. 420 unsigned NItinClasses = 421 Records.getAllDerivedDefinitions("InstrItinClass").size(); 422 if (NItinClasses == 0) 423 return; 424 425 // Get itinerary data list. 426 std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); 427 428 // Collect instruction classes for all itinerary data. 429 for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { 430 Record *ItinData = ItinDataList[j]; 431 unsigned NStages; 432 collectAllInsnClasses(Name, ItinData, NStages, OS); 433 } 434 } 435 436 437 // 438 // Run a worklist algorithm to generate the DFA. 439 // 440 DFA D; 441 State *Initial = new State; 442 Initial->isInitial = true; 443 Initial->stateInfo.insert(0x0); 444 D.addState(Initial); 445 SmallVector<State*, 32> WorkList; 446 std::map<std::set<unsigned>, State*> Visited; 447 448 WorkList.push_back(Initial); 449 450 // 451 // Worklist algorithm to create a DFA for processor resource tracking. 452 // C = {set of InsnClasses} 453 // Begin with initial node in worklist. Initial node does not have 454 // any consumed resources, 455 // ResourceState = 0x0 456 // Visited = {} 457 // While worklist != empty 458 // S = first element of worklist 459 // For every instruction class C 460 // if we can accommodate C in S: 461 // S' = state with resource states = {S Union C} 462 // Add a new transition: S x C -> S' 463 // If S' is not in Visited: 464 // Add S' to worklist 465 // Add S' to Visited 466 // 467 while (!WorkList.empty()) { 468 State *current = WorkList.pop_back_val(); 469 for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(), 470 CE = allInsnClasses.end(); CI != CE; ++CI) { 471 unsigned InsnClass = *CI; 472 473 std::set<unsigned> NewStateResources; 474 // 475 // If we haven't already created a transition for this input 476 // and the state can accommodate this InsnClass, create a transition. 477 // 478 if (!current->hasTransition(InsnClass) && 479 current->canAddInsnClass(InsnClass)) { 480 State *NewState = NULL; 481 current->AddInsnClass(InsnClass, NewStateResources); 482 assert(NewStateResources.size() && "New states must be generated"); 483 484 // 485 // If we have seen this state before, then do not create a new state. 486 // 487 // 488 std::map<std::set<unsigned>, State*>::iterator VI; 489 if ((VI = Visited.find(NewStateResources)) != Visited.end()) 490 NewState = VI->second; 491 else { 492 NewState = new State; 493 NewState->stateInfo = NewStateResources; 494 D.addState(NewState); 495 Visited[NewStateResources] = NewState; 496 WorkList.push_back(NewState); 497 } 498 499 current->addTransition(InsnClass, NewState); 500 } 501 } 502 } 503 504 // Print out the table. 505 D.writeTableAndAPI(OS, TargetName); 506} 507 508namespace llvm { 509 510void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { 511 emitSourceFileHeader("Target DFA Packetizer Tables", OS); 512 DFAPacketizerEmitter(RK).run(OS); 513} 514 515} // End llvm namespace 516