DFAPacketizerEmitter.cpp revision 243830
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) { 282243830Sdim DFA::StateSet::iterator SI = states.begin(); 283234285Sdim // This table provides a map to the beginning of the transitions for State s 284234285Sdim // in DFAStateInputTable. 285234285Sdim std::vector<int> StateEntry(states.size()); 286234285Sdim 287234285Sdim OS << "namespace llvm {\n\n"; 288234285Sdim OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n"; 289234285Sdim 290234285Sdim // Tracks the total valid transitions encountered so far. It is used 291234285Sdim // to construct the StateEntry table. 292234285Sdim int ValidTransitions = 0; 293234285Sdim for (unsigned i = 0; i < states.size(); ++i, ++SI) { 294243830Sdim assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers"); 295234285Sdim StateEntry[i] = ValidTransitions; 296243830Sdim for (State::TransitionMap::iterator 297243830Sdim II = (*SI)->Transitions.begin(), IE = (*SI)->Transitions.end(); 298243830Sdim II != IE; ++II) { 299243830Sdim OS << "{" << II->first << ", " 300243830Sdim << II->second->stateNum 301234285Sdim << "}, "; 302234285Sdim } 303243830Sdim ValidTransitions += (*SI)->Transitions.size(); 304234285Sdim 305234285Sdim // If there are no valid transitions from this stage, we need a sentinel 306234285Sdim // transition. 307234285Sdim if (ValidTransitions == StateEntry[i]) { 308234285Sdim OS << "{-1, -1},"; 309234285Sdim ++ValidTransitions; 310234285Sdim } 311234285Sdim 312234285Sdim OS << "\n"; 313234285Sdim } 314234285Sdim OS << "};\n\n"; 315234285Sdim OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; 316234285Sdim 317234285Sdim // Multiply i by 2 since each entry in DFAStateInputTable is a set of 318234285Sdim // two numbers. 319234285Sdim for (unsigned i = 0; i < states.size(); ++i) 320234285Sdim OS << StateEntry[i] << ", "; 321234285Sdim 322234285Sdim OS << "\n};\n"; 323234285Sdim OS << "} // namespace\n"; 324234285Sdim 325234285Sdim 326234285Sdim // 327234285Sdim // Emit DFA Packetizer tables if the target is a VLIW machine. 328234285Sdim // 329234285Sdim std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 330234285Sdim OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; 331234285Sdim OS << "namespace llvm {\n"; 332234285Sdim OS << "DFAPacketizer *" << SubTargetClassName << "::" 333234285Sdim << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" 334234285Sdim << " return new DFAPacketizer(IID, " << TargetName 335234285Sdim << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; 336234285Sdim OS << "} // End llvm namespace \n"; 337234285Sdim} 338234285Sdim 339234285Sdim 340234285Sdim// 341234285Sdim// collectAllInsnClasses - Populate allInsnClasses which is a set of units 342234285Sdim// used in each stage. 343234285Sdim// 344239462Sdimvoid DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name, 345234285Sdim Record *ItinData, 346234285Sdim unsigned &NStages, 347234285Sdim raw_ostream &OS) { 348234285Sdim // Collect processor itineraries. 349234285Sdim std::vector<Record*> ProcItinList = 350234285Sdim Records.getAllDerivedDefinitions("ProcessorItineraries"); 351234285Sdim 352234285Sdim // If just no itinerary then don't bother. 353234285Sdim if (ProcItinList.size() < 2) 354234285Sdim return; 355234285Sdim std::map<std::string, unsigned> NameToBitsMap; 356234285Sdim 357234285Sdim // Parse functional units for all the itineraries. 358234285Sdim for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { 359234285Sdim Record *Proc = ProcItinList[i]; 360234285Sdim std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); 361234285Sdim 362234285Sdim // Convert macros to bits for each stage. 363234285Sdim for (unsigned i = 0, N = FUs.size(); i < N; ++i) 364234285Sdim NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); 365234285Sdim } 366234285Sdim 367234285Sdim const std::vector<Record*> &StageList = 368234285Sdim ItinData->getValueAsListOfDefs("Stages"); 369234285Sdim 370234285Sdim // The number of stages. 371234285Sdim NStages = StageList.size(); 372234285Sdim 373234285Sdim // For each unit. 374234285Sdim unsigned UnitBitValue = 0; 375234285Sdim 376234285Sdim // Compute the bitwise or of each unit used in this stage. 377234285Sdim for (unsigned i = 0; i < NStages; ++i) { 378234285Sdim const Record *Stage = StageList[i]; 379234285Sdim 380234285Sdim // Get unit list. 381234285Sdim const std::vector<Record*> &UnitList = 382234285Sdim Stage->getValueAsListOfDefs("Units"); 383234285Sdim 384234285Sdim for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { 385234285Sdim // Conduct bitwise or. 386234285Sdim std::string UnitName = UnitList[j]->getName(); 387234285Sdim assert(NameToBitsMap.count(UnitName)); 388234285Sdim UnitBitValue |= NameToBitsMap[UnitName]; 389234285Sdim } 390234285Sdim 391234285Sdim if (UnitBitValue != 0) 392234285Sdim allInsnClasses.insert(UnitBitValue); 393234285Sdim } 394234285Sdim} 395234285Sdim 396234285Sdim 397234285Sdim// 398234285Sdim// Run the worklist algorithm to generate the DFA. 399234285Sdim// 400239462Sdimvoid DFAPacketizerEmitter::run(raw_ostream &OS) { 401234285Sdim 402234285Sdim // Collect processor iteraries. 403234285Sdim std::vector<Record*> ProcItinList = 404234285Sdim Records.getAllDerivedDefinitions("ProcessorItineraries"); 405234285Sdim 406234285Sdim // 407234285Sdim // Collect the instruction classes. 408234285Sdim // 409234285Sdim for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { 410234285Sdim Record *Proc = ProcItinList[i]; 411234285Sdim 412234285Sdim // Get processor itinerary name. 413234285Sdim const std::string &Name = Proc->getName(); 414234285Sdim 415234285Sdim // Skip default. 416234285Sdim if (Name == "NoItineraries") 417234285Sdim continue; 418234285Sdim 419234285Sdim // Sanity check for at least one instruction itinerary class. 420234285Sdim unsigned NItinClasses = 421234285Sdim Records.getAllDerivedDefinitions("InstrItinClass").size(); 422234285Sdim if (NItinClasses == 0) 423234285Sdim return; 424234285Sdim 425234285Sdim // Get itinerary data list. 426234285Sdim std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); 427234285Sdim 428234285Sdim // Collect instruction classes for all itinerary data. 429234285Sdim for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { 430234285Sdim Record *ItinData = ItinDataList[j]; 431234285Sdim unsigned NStages; 432234285Sdim collectAllInsnClasses(Name, ItinData, NStages, OS); 433234285Sdim } 434234285Sdim } 435234285Sdim 436234285Sdim 437234285Sdim // 438234285Sdim // Run a worklist algorithm to generate the DFA. 439234285Sdim // 440234285Sdim DFA D; 441234285Sdim State *Initial = new State; 442234285Sdim Initial->isInitial = true; 443234285Sdim Initial->stateInfo.insert(0x0); 444234285Sdim D.addState(Initial); 445234285Sdim SmallVector<State*, 32> WorkList; 446234285Sdim std::map<std::set<unsigned>, State*> Visited; 447234285Sdim 448234285Sdim WorkList.push_back(Initial); 449234285Sdim 450234285Sdim // 451234285Sdim // Worklist algorithm to create a DFA for processor resource tracking. 452234285Sdim // C = {set of InsnClasses} 453234285Sdim // Begin with initial node in worklist. Initial node does not have 454234285Sdim // any consumed resources, 455234285Sdim // ResourceState = 0x0 456234285Sdim // Visited = {} 457234285Sdim // While worklist != empty 458234285Sdim // S = first element of worklist 459234285Sdim // For every instruction class C 460234285Sdim // if we can accommodate C in S: 461234285Sdim // S' = state with resource states = {S Union C} 462234285Sdim // Add a new transition: S x C -> S' 463234285Sdim // If S' is not in Visited: 464234285Sdim // Add S' to worklist 465234285Sdim // Add S' to Visited 466234285Sdim // 467234285Sdim while (!WorkList.empty()) { 468234285Sdim State *current = WorkList.pop_back_val(); 469234285Sdim for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(), 470234285Sdim CE = allInsnClasses.end(); CI != CE; ++CI) { 471234285Sdim unsigned InsnClass = *CI; 472234285Sdim 473234285Sdim std::set<unsigned> NewStateResources; 474234285Sdim // 475234285Sdim // If we haven't already created a transition for this input 476234285Sdim // and the state can accommodate this InsnClass, create a transition. 477234285Sdim // 478243830Sdim if (!current->hasTransition(InsnClass) && 479239462Sdim current->canAddInsnClass(InsnClass)) { 480234285Sdim State *NewState = NULL; 481239462Sdim current->AddInsnClass(InsnClass, NewStateResources); 482239462Sdim assert(NewStateResources.size() && "New states must be generated"); 483234285Sdim 484234285Sdim // 485234285Sdim // If we have seen this state before, then do not create a new state. 486234285Sdim // 487234285Sdim // 488234285Sdim std::map<std::set<unsigned>, State*>::iterator VI; 489234285Sdim if ((VI = Visited.find(NewStateResources)) != Visited.end()) 490234285Sdim NewState = VI->second; 491234285Sdim else { 492234285Sdim NewState = new State; 493234285Sdim NewState->stateInfo = NewStateResources; 494234285Sdim D.addState(NewState); 495234285Sdim Visited[NewStateResources] = NewState; 496234285Sdim WorkList.push_back(NewState); 497234285Sdim } 498243830Sdim 499243830Sdim current->addTransition(InsnClass, NewState); 500234285Sdim } 501234285Sdim } 502234285Sdim } 503234285Sdim 504234285Sdim // Print out the table. 505234285Sdim D.writeTableAndAPI(OS, TargetName); 506234285Sdim} 507239462Sdim 508239462Sdimnamespace llvm { 509239462Sdim 510239462Sdimvoid EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { 511239462Sdim emitSourceFileHeader("Target DFA Packetizer Tables", OS); 512239462Sdim DFAPacketizerEmitter(RK).run(OS); 513239462Sdim} 514239462Sdim 515239462Sdim} // End llvm namespace 516