1234285Sdim//===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine-----===// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This class parses the Schedule.td file and produces an API that can be used 11234285Sdim// to reason about whether an instruction can be added to a packet on a VLIW 12234285Sdim// architecture. The class internally generates a deterministic finite 13234285Sdim// automaton (DFA) that models all possible mappings of machine instructions 14234285Sdim// to functional units as instructions are added to a packet. 15234285Sdim// 16234285Sdim//===----------------------------------------------------------------------===// 17234285Sdim 18239462Sdim#include "CodeGenTarget.h" 19239462Sdim#include "llvm/ADT/DenseSet.h" 20243830Sdim#include "llvm/ADT/STLExtras.h" 21234285Sdim#include "llvm/TableGen/Record.h" 22239462Sdim#include "llvm/TableGen/TableGenBackend.h" 23234285Sdim#include <list> 24239462Sdim#include <map> 25239462Sdim#include <string> 26234285Sdimusing namespace llvm; 27234285Sdim 28234285Sdim// 29239462Sdim// class DFAPacketizerEmitter: class that generates and prints out the DFA 30239462Sdim// for resource tracking. 31234285Sdim// 32239462Sdimnamespace { 33239462Sdimclass DFAPacketizerEmitter { 34239462Sdimprivate: 35239462Sdim std::string TargetName; 36239462Sdim // 37239462Sdim // allInsnClasses is the set of all possible resources consumed by an 38239462Sdim // InstrStage. 39239462Sdim // 40239462Sdim DenseSet<unsigned> allInsnClasses; 41239462Sdim RecordKeeper &Records; 42239462Sdim 43239462Sdimpublic: 44239462Sdim DFAPacketizerEmitter(RecordKeeper &R); 45239462Sdim 46239462Sdim // 47239462Sdim // collectAllInsnClasses: Populate allInsnClasses which is a set of units 48239462Sdim // used in each stage. 49239462Sdim // 50239462Sdim void collectAllInsnClasses(const std::string &Name, 51239462Sdim Record *ItinData, 52239462Sdim unsigned &NStages, 53239462Sdim raw_ostream &OS); 54239462Sdim 55239462Sdim void run(raw_ostream &OS); 56239462Sdim}; 57239462Sdim} // End anonymous namespace. 58239462Sdim 59239462Sdim// 60239462Sdim// 61234285Sdim// State represents the usage of machine resources if the packet contains 62234285Sdim// a set of instruction classes. 63234285Sdim// 64234285Sdim// Specifically, currentState is a set of bit-masks. 65234285Sdim// The nth bit in a bit-mask indicates whether the nth resource is being used 66234285Sdim// by this state. The set of bit-masks in a state represent the different 67234285Sdim// possible outcomes of transitioning to this state. 68234285Sdim// For example: consider a two resource architecture: resource L and resource M 69234285Sdim// with three instruction classes: L, M, and L_or_M. 70234285Sdim// From the initial state (currentState = 0x00), if we add instruction class 71234285Sdim// L_or_M we will transition to a state with currentState = [0x01, 0x10]. This 72234285Sdim// represents the possible resource states that can result from adding a L_or_M 73234285Sdim// instruction 74234285Sdim// 75234285Sdim// Another way of thinking about this transition is we are mapping a NDFA with 76234285Sdim// two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10]. 77234285Sdim// 78243830Sdim// A State instance also contains a collection of transitions from that state: 79243830Sdim// a map from inputs to new states. 80234285Sdim// 81234285Sdimnamespace { 82234285Sdimclass State { 83234285Sdim public: 84234285Sdim static int currentStateNum; 85234285Sdim int stateNum; 86234285Sdim bool isInitial; 87234285Sdim std::set<unsigned> stateInfo; 88243830Sdim typedef std::map<unsigned, State *> TransitionMap; 89243830Sdim TransitionMap Transitions; 90234285Sdim 91234285Sdim State(); 92234285Sdim State(const State &S); 93234285Sdim 94243830Sdim bool operator<(const State &s) const { 95243830Sdim return stateNum < s.stateNum; 96243830Sdim } 97243830Sdim 98234285Sdim // 99234285Sdim // canAddInsnClass - Returns true if an instruction of type InsnClass is a 100234285Sdim // valid transition from this state, i.e., can an instruction of type InsnClass 101234285Sdim // be added to the packet represented by this state. 102234285Sdim // 103234285Sdim // PossibleStates is the set of valid resource states that ensue from valid 104234285Sdim // transitions. 105234285Sdim // 106239462Sdim bool canAddInsnClass(unsigned InsnClass) const; 107239462Sdim // 108239462Sdim // AddInsnClass - Return all combinations of resource reservation 109239462Sdim // which are possible from this state (PossibleStates). 110239462Sdim // 111239462Sdim void AddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates); 112243830Sdim // 113243830Sdim // addTransition - Add a transition from this state given the input InsnClass 114243830Sdim // 115243830Sdim void addTransition(unsigned InsnClass, State *To); 116243830Sdim // 117243830Sdim // hasTransition - Returns true if there is a transition from this state 118243830Sdim // given the input InsnClass 119243830Sdim // 120243830Sdim bool hasTransition(unsigned InsnClass); 121234285Sdim}; 122234285Sdim} // End anonymous namespace. 123234285Sdim 124234285Sdim// 125234285Sdim// class DFA: deterministic finite automaton for processor resource tracking. 126234285Sdim// 127234285Sdimnamespace { 128234285Sdimclass DFA { 129234285Sdimpublic: 130234285Sdim DFA(); 131243830Sdim ~DFA(); 132234285Sdim 133234285Sdim // Set of states. Need to keep this sorted to emit the transition table. 134243830Sdim typedef std::set<State *, less_ptr<State> > StateSet; 135243830Sdim StateSet states; 136234285Sdim 137234285Sdim State *currentState; 138234285Sdim 139234285Sdim // 140234285Sdim // Modify the DFA. 141234285Sdim // 142234285Sdim void initialize(); 143234285Sdim void addState(State *); 144234285Sdim 145234285Sdim // 146234285Sdim // writeTable: Print out a table representing the DFA. 147234285Sdim // 148234285Sdim void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName); 149234285Sdim}; 150234285Sdim} // End anonymous namespace. 151234285Sdim 152234285Sdim 153234285Sdim// 154243830Sdim// Constructors and destructors for State and DFA 155234285Sdim// 156234285SdimState::State() : 157234285Sdim stateNum(currentStateNum++), isInitial(false) {} 158234285Sdim 159234285Sdim 160234285SdimState::State(const State &S) : 161234285Sdim stateNum(currentStateNum++), isInitial(S.isInitial), 162234285Sdim stateInfo(S.stateInfo) {} 163234285Sdim 164243830SdimDFA::DFA(): currentState(NULL) {} 165234285Sdim 166243830SdimDFA::~DFA() { 167243830Sdim DeleteContainerPointers(states); 168243830Sdim} 169234285Sdim 170243830Sdim// 171243830Sdim// addTransition - Add a transition from this state given the input InsnClass 172243830Sdim// 173243830Sdimvoid State::addTransition(unsigned InsnClass, State *To) { 174243830Sdim assert(!Transitions.count(InsnClass) && 175243830Sdim "Cannot have multiple transitions for the same input"); 176243830Sdim Transitions[InsnClass] = To; 177234285Sdim} 178234285Sdim 179243830Sdim// 180243830Sdim// hasTransition - Returns true if there is a transition from this state 181243830Sdim// given the input InsnClass 182243830Sdim// 183243830Sdimbool State::hasTransition(unsigned InsnClass) { 184243830Sdim return Transitions.count(InsnClass) > 0; 185239462Sdim} 186234285Sdim 187234285Sdim// 188239462Sdim// AddInsnClass - Return all combinations of resource reservation 189239462Sdim// which are possible from this state (PossibleStates). 190234285Sdim// 191239462Sdimvoid State::AddInsnClass(unsigned InsnClass, 192234285Sdim std::set<unsigned> &PossibleStates) { 193234285Sdim // 194234285Sdim // Iterate over all resource states in currentState. 195234285Sdim // 196234285Sdim 197234285Sdim for (std::set<unsigned>::iterator SI = stateInfo.begin(); 198234285Sdim SI != stateInfo.end(); ++SI) { 199234285Sdim unsigned thisState = *SI; 200234285Sdim 201234285Sdim // 202234285Sdim // Iterate over all possible resources used in InsnClass. 203234285Sdim // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}. 204234285Sdim // 205234285Sdim 206234285Sdim DenseSet<unsigned> VisitedResourceStates; 207234285Sdim for (unsigned int j = 0; j < sizeof(InsnClass) * 8; ++j) { 208234285Sdim if ((0x1 << j) & InsnClass) { 209234285Sdim // 210234285Sdim // For each possible resource used in InsnClass, generate the 211234285Sdim // resource state if that resource was used. 212234285Sdim // 213234285Sdim unsigned ResultingResourceState = thisState | (0x1 << j); 214234285Sdim // 215234285Sdim // Check if the resulting resource state can be accommodated in this 216234285Sdim // packet. 217234285Sdim // We compute ResultingResourceState OR thisState. 218234285Sdim // If the result of the OR is different than thisState, it implies 219234285Sdim // that there is at least one resource that can be used to schedule 220234285Sdim // InsnClass in the current packet. 221234285Sdim // Insert ResultingResourceState into PossibleStates only if we haven't 222234285Sdim // processed ResultingResourceState before. 223234285Sdim // 224234285Sdim if ((ResultingResourceState != thisState) && 225234285Sdim (VisitedResourceStates.count(ResultingResourceState) == 0)) { 226234285Sdim VisitedResourceStates.insert(ResultingResourceState); 227234285Sdim PossibleStates.insert(ResultingResourceState); 228234285Sdim } 229234285Sdim } 230234285Sdim } 231234285Sdim } 232234285Sdim 233234285Sdim} 234234285Sdim 235234285Sdim 236239462Sdim// 237239462Sdim// canAddInsnClass - Quickly verifies if an instruction of type InsnClass is a 238239462Sdim// valid transition from this state i.e., can an instruction of type InsnClass 239239462Sdim// be added to the packet represented by this state. 240239462Sdim// 241239462Sdimbool State::canAddInsnClass(unsigned InsnClass) const { 242239462Sdim for (std::set<unsigned>::const_iterator SI = stateInfo.begin(); 243239462Sdim SI != stateInfo.end(); ++SI) { 244239462Sdim if (~*SI & InsnClass) 245239462Sdim return true; 246239462Sdim } 247239462Sdim return false; 248239462Sdim} 249239462Sdim 250239462Sdim 251234285Sdimvoid DFA::initialize() { 252243830Sdim assert(currentState && "Missing current state"); 253234285Sdim currentState->isInitial = true; 254234285Sdim} 255234285Sdim 256234285Sdim 257234285Sdimvoid DFA::addState(State *S) { 258234285Sdim assert(!states.count(S) && "State already exists"); 259234285Sdim states.insert(S); 260234285Sdim} 261234285Sdim 262234285Sdim 263234285Sdimint State::currentStateNum = 0; 264234285Sdim 265239462SdimDFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): 266234285Sdim TargetName(CodeGenTarget(R).getName()), 267234285Sdim allInsnClasses(), Records(R) {} 268234285Sdim 269234285Sdim 270234285Sdim// 271234285Sdim// writeTableAndAPI - Print out a table representing the DFA and the 272234285Sdim// associated API to create a DFA packetizer. 273234285Sdim// 274234285Sdim// Format: 275234285Sdim// DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 276234285Sdim// transitions. 277234285Sdim// DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for 278234285Sdim// the ith state. 279234285Sdim// 280234285Sdim// 281234285Sdimvoid DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { 282249423Sdim static const std::string SentinelEntry = "{-1, -1}"; 283243830Sdim DFA::StateSet::iterator SI = states.begin(); 284234285Sdim // This table provides a map to the beginning of the transitions for State s 285234285Sdim // in DFAStateInputTable. 286234285Sdim std::vector<int> StateEntry(states.size()); 287234285Sdim 288234285Sdim OS << "namespace llvm {\n\n"; 289234285Sdim OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n"; 290234285Sdim 291234285Sdim // Tracks the total valid transitions encountered so far. It is used 292234285Sdim // to construct the StateEntry table. 293234285Sdim int ValidTransitions = 0; 294234285Sdim for (unsigned i = 0; i < states.size(); ++i, ++SI) { 295243830Sdim assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers"); 296234285Sdim StateEntry[i] = ValidTransitions; 297243830Sdim for (State::TransitionMap::iterator 298243830Sdim II = (*SI)->Transitions.begin(), IE = (*SI)->Transitions.end(); 299243830Sdim II != IE; ++II) { 300243830Sdim OS << "{" << II->first << ", " 301243830Sdim << II->second->stateNum 302234285Sdim << "}, "; 303234285Sdim } 304243830Sdim ValidTransitions += (*SI)->Transitions.size(); 305234285Sdim 306234285Sdim // If there are no valid transitions from this stage, we need a sentinel 307234285Sdim // transition. 308234285Sdim if (ValidTransitions == StateEntry[i]) { 309249423Sdim OS << SentinelEntry << ","; 310234285Sdim ++ValidTransitions; 311234285Sdim } 312234285Sdim 313234285Sdim OS << "\n"; 314234285Sdim } 315249423Sdim 316249423Sdim // Print out a sentinel entry at the end of the StateInputTable. This is 317249423Sdim // needed to iterate over StateInputTable in DFAPacketizer::ReadTable() 318249423Sdim OS << SentinelEntry << "\n"; 319249423Sdim 320234285Sdim OS << "};\n\n"; 321234285Sdim OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; 322234285Sdim 323234285Sdim // Multiply i by 2 since each entry in DFAStateInputTable is a set of 324234285Sdim // two numbers. 325234285Sdim for (unsigned i = 0; i < states.size(); ++i) 326234285Sdim OS << StateEntry[i] << ", "; 327234285Sdim 328249423Sdim // Print out the index to the sentinel entry in StateInputTable 329249423Sdim OS << ValidTransitions << ", "; 330249423Sdim 331234285Sdim OS << "\n};\n"; 332234285Sdim OS << "} // namespace\n"; 333234285Sdim 334234285Sdim 335234285Sdim // 336234285Sdim // Emit DFA Packetizer tables if the target is a VLIW machine. 337234285Sdim // 338234285Sdim std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 339234285Sdim OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; 340234285Sdim OS << "namespace llvm {\n"; 341234285Sdim OS << "DFAPacketizer *" << SubTargetClassName << "::" 342234285Sdim << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" 343234285Sdim << " return new DFAPacketizer(IID, " << TargetName 344234285Sdim << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; 345234285Sdim OS << "} // End llvm namespace \n"; 346234285Sdim} 347234285Sdim 348234285Sdim 349234285Sdim// 350234285Sdim// collectAllInsnClasses - Populate allInsnClasses which is a set of units 351234285Sdim// used in each stage. 352234285Sdim// 353239462Sdimvoid DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name, 354234285Sdim Record *ItinData, 355234285Sdim unsigned &NStages, 356234285Sdim raw_ostream &OS) { 357234285Sdim // Collect processor itineraries. 358234285Sdim std::vector<Record*> ProcItinList = 359234285Sdim Records.getAllDerivedDefinitions("ProcessorItineraries"); 360234285Sdim 361234285Sdim // If just no itinerary then don't bother. 362234285Sdim if (ProcItinList.size() < 2) 363234285Sdim return; 364234285Sdim std::map<std::string, unsigned> NameToBitsMap; 365234285Sdim 366234285Sdim // Parse functional units for all the itineraries. 367234285Sdim for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { 368234285Sdim Record *Proc = ProcItinList[i]; 369234285Sdim std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); 370234285Sdim 371234285Sdim // Convert macros to bits for each stage. 372234285Sdim for (unsigned i = 0, N = FUs.size(); i < N; ++i) 373234285Sdim NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); 374234285Sdim } 375234285Sdim 376234285Sdim const std::vector<Record*> &StageList = 377234285Sdim ItinData->getValueAsListOfDefs("Stages"); 378234285Sdim 379234285Sdim // The number of stages. 380234285Sdim NStages = StageList.size(); 381234285Sdim 382234285Sdim // For each unit. 383234285Sdim unsigned UnitBitValue = 0; 384234285Sdim 385234285Sdim // Compute the bitwise or of each unit used in this stage. 386234285Sdim for (unsigned i = 0; i < NStages; ++i) { 387234285Sdim const Record *Stage = StageList[i]; 388234285Sdim 389234285Sdim // Get unit list. 390234285Sdim const std::vector<Record*> &UnitList = 391234285Sdim Stage->getValueAsListOfDefs("Units"); 392234285Sdim 393234285Sdim for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { 394234285Sdim // Conduct bitwise or. 395234285Sdim std::string UnitName = UnitList[j]->getName(); 396234285Sdim assert(NameToBitsMap.count(UnitName)); 397234285Sdim UnitBitValue |= NameToBitsMap[UnitName]; 398234285Sdim } 399234285Sdim 400234285Sdim if (UnitBitValue != 0) 401234285Sdim allInsnClasses.insert(UnitBitValue); 402234285Sdim } 403234285Sdim} 404234285Sdim 405234285Sdim 406234285Sdim// 407234285Sdim// Run the worklist algorithm to generate the DFA. 408234285Sdim// 409239462Sdimvoid DFAPacketizerEmitter::run(raw_ostream &OS) { 410234285Sdim 411234285Sdim // Collect processor iteraries. 412234285Sdim std::vector<Record*> ProcItinList = 413234285Sdim Records.getAllDerivedDefinitions("ProcessorItineraries"); 414234285Sdim 415234285Sdim // 416234285Sdim // Collect the instruction classes. 417234285Sdim // 418234285Sdim for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { 419234285Sdim Record *Proc = ProcItinList[i]; 420234285Sdim 421234285Sdim // Get processor itinerary name. 422234285Sdim const std::string &Name = Proc->getName(); 423234285Sdim 424234285Sdim // Skip default. 425234285Sdim if (Name == "NoItineraries") 426234285Sdim continue; 427234285Sdim 428234285Sdim // Sanity check for at least one instruction itinerary class. 429234285Sdim unsigned NItinClasses = 430234285Sdim Records.getAllDerivedDefinitions("InstrItinClass").size(); 431234285Sdim if (NItinClasses == 0) 432234285Sdim return; 433234285Sdim 434234285Sdim // Get itinerary data list. 435234285Sdim std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); 436234285Sdim 437234285Sdim // Collect instruction classes for all itinerary data. 438234285Sdim for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { 439234285Sdim Record *ItinData = ItinDataList[j]; 440234285Sdim unsigned NStages; 441234285Sdim collectAllInsnClasses(Name, ItinData, NStages, OS); 442234285Sdim } 443234285Sdim } 444234285Sdim 445234285Sdim 446234285Sdim // 447234285Sdim // Run a worklist algorithm to generate the DFA. 448234285Sdim // 449234285Sdim DFA D; 450234285Sdim State *Initial = new State; 451234285Sdim Initial->isInitial = true; 452234285Sdim Initial->stateInfo.insert(0x0); 453234285Sdim D.addState(Initial); 454234285Sdim SmallVector<State*, 32> WorkList; 455234285Sdim std::map<std::set<unsigned>, State*> Visited; 456234285Sdim 457234285Sdim WorkList.push_back(Initial); 458234285Sdim 459234285Sdim // 460234285Sdim // Worklist algorithm to create a DFA for processor resource tracking. 461234285Sdim // C = {set of InsnClasses} 462234285Sdim // Begin with initial node in worklist. Initial node does not have 463234285Sdim // any consumed resources, 464234285Sdim // ResourceState = 0x0 465234285Sdim // Visited = {} 466234285Sdim // While worklist != empty 467234285Sdim // S = first element of worklist 468234285Sdim // For every instruction class C 469234285Sdim // if we can accommodate C in S: 470234285Sdim // S' = state with resource states = {S Union C} 471234285Sdim // Add a new transition: S x C -> S' 472234285Sdim // If S' is not in Visited: 473234285Sdim // Add S' to worklist 474234285Sdim // Add S' to Visited 475234285Sdim // 476234285Sdim while (!WorkList.empty()) { 477234285Sdim State *current = WorkList.pop_back_val(); 478234285Sdim for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(), 479234285Sdim CE = allInsnClasses.end(); CI != CE; ++CI) { 480234285Sdim unsigned InsnClass = *CI; 481234285Sdim 482234285Sdim std::set<unsigned> NewStateResources; 483234285Sdim // 484234285Sdim // If we haven't already created a transition for this input 485234285Sdim // and the state can accommodate this InsnClass, create a transition. 486234285Sdim // 487243830Sdim if (!current->hasTransition(InsnClass) && 488239462Sdim current->canAddInsnClass(InsnClass)) { 489234285Sdim State *NewState = NULL; 490239462Sdim current->AddInsnClass(InsnClass, NewStateResources); 491239462Sdim assert(NewStateResources.size() && "New states must be generated"); 492234285Sdim 493234285Sdim // 494234285Sdim // If we have seen this state before, then do not create a new state. 495234285Sdim // 496234285Sdim // 497234285Sdim std::map<std::set<unsigned>, State*>::iterator VI; 498234285Sdim if ((VI = Visited.find(NewStateResources)) != Visited.end()) 499234285Sdim NewState = VI->second; 500234285Sdim else { 501234285Sdim NewState = new State; 502234285Sdim NewState->stateInfo = NewStateResources; 503234285Sdim D.addState(NewState); 504234285Sdim Visited[NewStateResources] = NewState; 505234285Sdim WorkList.push_back(NewState); 506234285Sdim } 507243830Sdim 508243830Sdim current->addTransition(InsnClass, NewState); 509234285Sdim } 510234285Sdim } 511234285Sdim } 512234285Sdim 513234285Sdim // Print out the table. 514234285Sdim D.writeTableAndAPI(OS, TargetName); 515234285Sdim} 516239462Sdim 517239462Sdimnamespace llvm { 518239462Sdim 519239462Sdimvoid EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { 520239462Sdim emitSourceFileHeader("Target DFA Packetizer Tables", OS); 521239462Sdim DFAPacketizerEmitter(RK).run(OS); 522239462Sdim} 523239462Sdim 524239462Sdim} // End llvm namespace 525