DFAPacketizerEmitter.cpp revision 234285
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 18234285Sdim#include "llvm/TableGen/Record.h" 19234285Sdim#include "CodeGenTarget.h" 20234285Sdim#include "DFAPacketizerEmitter.h" 21234285Sdim#include <list> 22234285Sdim 23234285Sdimusing namespace llvm; 24234285Sdim 25234285Sdim// 26234285Sdim// 27234285Sdim// State represents the usage of machine resources if the packet contains 28234285Sdim// a set of instruction classes. 29234285Sdim// 30234285Sdim// Specifically, currentState is a set of bit-masks. 31234285Sdim// The nth bit in a bit-mask indicates whether the nth resource is being used 32234285Sdim// by this state. The set of bit-masks in a state represent the different 33234285Sdim// possible outcomes of transitioning to this state. 34234285Sdim// For example: consider a two resource architecture: resource L and resource M 35234285Sdim// with three instruction classes: L, M, and L_or_M. 36234285Sdim// From the initial state (currentState = 0x00), if we add instruction class 37234285Sdim// L_or_M we will transition to a state with currentState = [0x01, 0x10]. This 38234285Sdim// represents the possible resource states that can result from adding a L_or_M 39234285Sdim// instruction 40234285Sdim// 41234285Sdim// Another way of thinking about this transition is we are mapping a NDFA with 42234285Sdim// two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10]. 43234285Sdim// 44234285Sdim// 45234285Sdimnamespace { 46234285Sdimclass State { 47234285Sdim public: 48234285Sdim static int currentStateNum; 49234285Sdim int stateNum; 50234285Sdim bool isInitial; 51234285Sdim std::set<unsigned> stateInfo; 52234285Sdim 53234285Sdim State(); 54234285Sdim State(const State &S); 55234285Sdim 56234285Sdim // 57234285Sdim // canAddInsnClass - Returns true if an instruction of type InsnClass is a 58234285Sdim // valid transition from this state, i.e., can an instruction of type InsnClass 59234285Sdim // be added to the packet represented by this state. 60234285Sdim // 61234285Sdim // PossibleStates is the set of valid resource states that ensue from valid 62234285Sdim // transitions. 63234285Sdim // 64234285Sdim bool canAddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates); 65234285Sdim}; 66234285Sdim} // End anonymous namespace. 67234285Sdim 68234285Sdim 69234285Sdimnamespace { 70234285Sdimstruct Transition { 71234285Sdim public: 72234285Sdim static int currentTransitionNum; 73234285Sdim int transitionNum; 74234285Sdim State *from; 75234285Sdim unsigned input; 76234285Sdim State *to; 77234285Sdim 78234285Sdim Transition(State *from_, unsigned input_, State *to_); 79234285Sdim}; 80234285Sdim} // End anonymous namespace. 81234285Sdim 82234285Sdim 83234285Sdim// 84234285Sdim// Comparators to keep set of states sorted. 85234285Sdim// 86234285Sdimnamespace { 87234285Sdimstruct ltState { 88234285Sdim bool operator()(const State *s1, const State *s2) const; 89234285Sdim}; 90234285Sdim} // End anonymous namespace. 91234285Sdim 92234285Sdim 93234285Sdim// 94234285Sdim// class DFA: deterministic finite automaton for processor resource tracking. 95234285Sdim// 96234285Sdimnamespace { 97234285Sdimclass DFA { 98234285Sdimpublic: 99234285Sdim DFA(); 100234285Sdim 101234285Sdim // Set of states. Need to keep this sorted to emit the transition table. 102234285Sdim std::set<State*, ltState> states; 103234285Sdim 104234285Sdim // Map from a state to the list of transitions with that state as source. 105234285Sdim std::map<State*, SmallVector<Transition*, 16>, ltState> stateTransitions; 106234285Sdim State *currentState; 107234285Sdim 108234285Sdim // Highest valued Input seen. 109234285Sdim unsigned LargestInput; 110234285Sdim 111234285Sdim // 112234285Sdim // Modify the DFA. 113234285Sdim // 114234285Sdim void initialize(); 115234285Sdim void addState(State *); 116234285Sdim void addTransition(Transition *); 117234285Sdim 118234285Sdim // 119234285Sdim // getTransition - Return the state when a transition is made from 120234285Sdim // State From with Input I. If a transition is not found, return NULL. 121234285Sdim // 122234285Sdim State *getTransition(State *, unsigned); 123234285Sdim 124234285Sdim // 125234285Sdim // isValidTransition: Predicate that checks if there is a valid transition 126234285Sdim // from state From on input InsnClass. 127234285Sdim // 128234285Sdim bool isValidTransition(State *From, unsigned InsnClass); 129234285Sdim 130234285Sdim // 131234285Sdim // writeTable: Print out a table representing the DFA. 132234285Sdim // 133234285Sdim void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName); 134234285Sdim}; 135234285Sdim} // End anonymous namespace. 136234285Sdim 137234285Sdim 138234285Sdim// 139234285Sdim// Constructors for State, Transition, and DFA 140234285Sdim// 141234285SdimState::State() : 142234285Sdim stateNum(currentStateNum++), isInitial(false) {} 143234285Sdim 144234285Sdim 145234285SdimState::State(const State &S) : 146234285Sdim stateNum(currentStateNum++), isInitial(S.isInitial), 147234285Sdim stateInfo(S.stateInfo) {} 148234285Sdim 149234285Sdim 150234285SdimTransition::Transition(State *from_, unsigned input_, State *to_) : 151234285Sdim transitionNum(currentTransitionNum++), from(from_), input(input_), 152234285Sdim to(to_) {} 153234285Sdim 154234285Sdim 155234285SdimDFA::DFA() : 156234285Sdim LargestInput(0) {} 157234285Sdim 158234285Sdim 159234285Sdimbool ltState::operator()(const State *s1, const State *s2) const { 160234285Sdim return (s1->stateNum < s2->stateNum); 161234285Sdim} 162234285Sdim 163234285Sdim 164234285Sdim// 165234285Sdim// canAddInsnClass - Returns true if an instruction of type InsnClass is a 166234285Sdim// valid transition from this state i.e., can an instruction of type InsnClass 167234285Sdim// be added to the packet represented by this state. 168234285Sdim// 169234285Sdim// PossibleStates is the set of valid resource states that ensue from valid 170234285Sdim// transitions. 171234285Sdim// 172234285Sdimbool State::canAddInsnClass(unsigned InsnClass, 173234285Sdim std::set<unsigned> &PossibleStates) { 174234285Sdim // 175234285Sdim // Iterate over all resource states in currentState. 176234285Sdim // 177234285Sdim bool AddedState = false; 178234285Sdim 179234285Sdim for (std::set<unsigned>::iterator SI = stateInfo.begin(); 180234285Sdim SI != stateInfo.end(); ++SI) { 181234285Sdim unsigned thisState = *SI; 182234285Sdim 183234285Sdim // 184234285Sdim // Iterate over all possible resources used in InsnClass. 185234285Sdim // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}. 186234285Sdim // 187234285Sdim 188234285Sdim DenseSet<unsigned> VisitedResourceStates; 189234285Sdim for (unsigned int j = 0; j < sizeof(InsnClass) * 8; ++j) { 190234285Sdim if ((0x1 << j) & InsnClass) { 191234285Sdim // 192234285Sdim // For each possible resource used in InsnClass, generate the 193234285Sdim // resource state if that resource was used. 194234285Sdim // 195234285Sdim unsigned ResultingResourceState = thisState | (0x1 << j); 196234285Sdim // 197234285Sdim // Check if the resulting resource state can be accommodated in this 198234285Sdim // packet. 199234285Sdim // We compute ResultingResourceState OR thisState. 200234285Sdim // If the result of the OR is different than thisState, it implies 201234285Sdim // that there is at least one resource that can be used to schedule 202234285Sdim // InsnClass in the current packet. 203234285Sdim // Insert ResultingResourceState into PossibleStates only if we haven't 204234285Sdim // processed ResultingResourceState before. 205234285Sdim // 206234285Sdim if ((ResultingResourceState != thisState) && 207234285Sdim (VisitedResourceStates.count(ResultingResourceState) == 0)) { 208234285Sdim VisitedResourceStates.insert(ResultingResourceState); 209234285Sdim PossibleStates.insert(ResultingResourceState); 210234285Sdim AddedState = true; 211234285Sdim } 212234285Sdim } 213234285Sdim } 214234285Sdim } 215234285Sdim 216234285Sdim return AddedState; 217234285Sdim} 218234285Sdim 219234285Sdim 220234285Sdimvoid DFA::initialize() { 221234285Sdim currentState->isInitial = true; 222234285Sdim} 223234285Sdim 224234285Sdim 225234285Sdimvoid DFA::addState(State *S) { 226234285Sdim assert(!states.count(S) && "State already exists"); 227234285Sdim states.insert(S); 228234285Sdim} 229234285Sdim 230234285Sdim 231234285Sdimvoid DFA::addTransition(Transition *T) { 232234285Sdim // Update LargestInput. 233234285Sdim if (T->input > LargestInput) 234234285Sdim LargestInput = T->input; 235234285Sdim 236234285Sdim // Add the new transition. 237234285Sdim stateTransitions[T->from].push_back(T); 238234285Sdim} 239234285Sdim 240234285Sdim 241234285Sdim// 242234285Sdim// getTransition - Return the state when a transition is made from 243234285Sdim// State From with Input I. If a transition is not found, return NULL. 244234285Sdim// 245234285SdimState *DFA::getTransition(State *From, unsigned I) { 246234285Sdim // Do we have a transition from state From? 247234285Sdim if (!stateTransitions.count(From)) 248234285Sdim return NULL; 249234285Sdim 250234285Sdim // Do we have a transition from state From with Input I? 251234285Sdim for (SmallVector<Transition*, 16>::iterator VI = 252234285Sdim stateTransitions[From].begin(); 253234285Sdim VI != stateTransitions[From].end(); ++VI) 254234285Sdim if ((*VI)->input == I) 255234285Sdim return (*VI)->to; 256234285Sdim 257234285Sdim return NULL; 258234285Sdim} 259234285Sdim 260234285Sdim 261234285Sdimbool DFA::isValidTransition(State *From, unsigned InsnClass) { 262234285Sdim return (getTransition(From, InsnClass) != NULL); 263234285Sdim} 264234285Sdim 265234285Sdim 266234285Sdimint State::currentStateNum = 0; 267234285Sdimint Transition::currentTransitionNum = 0; 268234285Sdim 269234285SdimDFAGen::DFAGen(RecordKeeper &R): 270234285Sdim TargetName(CodeGenTarget(R).getName()), 271234285Sdim allInsnClasses(), Records(R) {} 272234285Sdim 273234285Sdim 274234285Sdim// 275234285Sdim// writeTableAndAPI - Print out a table representing the DFA and the 276234285Sdim// associated API to create a DFA packetizer. 277234285Sdim// 278234285Sdim// Format: 279234285Sdim// DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 280234285Sdim// transitions. 281234285Sdim// DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for 282234285Sdim// the ith state. 283234285Sdim// 284234285Sdim// 285234285Sdimvoid DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { 286234285Sdim std::set<State*, ltState>::iterator SI = states.begin(); 287234285Sdim // This table provides a map to the beginning of the transitions for State s 288234285Sdim // in DFAStateInputTable. 289234285Sdim std::vector<int> StateEntry(states.size()); 290234285Sdim 291234285Sdim OS << "namespace llvm {\n\n"; 292234285Sdim OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n"; 293234285Sdim 294234285Sdim // Tracks the total valid transitions encountered so far. It is used 295234285Sdim // to construct the StateEntry table. 296234285Sdim int ValidTransitions = 0; 297234285Sdim for (unsigned i = 0; i < states.size(); ++i, ++SI) { 298234285Sdim StateEntry[i] = ValidTransitions; 299234285Sdim for (unsigned j = 0; j <= LargestInput; ++j) { 300234285Sdim assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers"); 301234285Sdim if (!isValidTransition(*SI, j)) 302234285Sdim continue; 303234285Sdim 304234285Sdim OS << "{" << j << ", " 305234285Sdim << getTransition(*SI, j)->stateNum 306234285Sdim << "}, "; 307234285Sdim ++ValidTransitions; 308234285Sdim } 309234285Sdim 310234285Sdim // If there are no valid transitions from this stage, we need a sentinel 311234285Sdim // transition. 312234285Sdim if (ValidTransitions == StateEntry[i]) { 313234285Sdim OS << "{-1, -1},"; 314234285Sdim ++ValidTransitions; 315234285Sdim } 316234285Sdim 317234285Sdim OS << "\n"; 318234285Sdim } 319234285Sdim OS << "};\n\n"; 320234285Sdim OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; 321234285Sdim 322234285Sdim // Multiply i by 2 since each entry in DFAStateInputTable is a set of 323234285Sdim // two numbers. 324234285Sdim for (unsigned i = 0; i < states.size(); ++i) 325234285Sdim OS << StateEntry[i] << ", "; 326234285Sdim 327234285Sdim OS << "\n};\n"; 328234285Sdim OS << "} // namespace\n"; 329234285Sdim 330234285Sdim 331234285Sdim // 332234285Sdim // Emit DFA Packetizer tables if the target is a VLIW machine. 333234285Sdim // 334234285Sdim std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 335234285Sdim OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; 336234285Sdim OS << "namespace llvm {\n"; 337234285Sdim OS << "DFAPacketizer *" << SubTargetClassName << "::" 338234285Sdim << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" 339234285Sdim << " return new DFAPacketizer(IID, " << TargetName 340234285Sdim << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; 341234285Sdim OS << "} // End llvm namespace \n"; 342234285Sdim} 343234285Sdim 344234285Sdim 345234285Sdim// 346234285Sdim// collectAllInsnClasses - Populate allInsnClasses which is a set of units 347234285Sdim// used in each stage. 348234285Sdim// 349234285Sdimvoid DFAGen::collectAllInsnClasses(const std::string &Name, 350234285Sdim Record *ItinData, 351234285Sdim unsigned &NStages, 352234285Sdim raw_ostream &OS) { 353234285Sdim // Collect processor itineraries. 354234285Sdim std::vector<Record*> ProcItinList = 355234285Sdim Records.getAllDerivedDefinitions("ProcessorItineraries"); 356234285Sdim 357234285Sdim // If just no itinerary then don't bother. 358234285Sdim if (ProcItinList.size() < 2) 359234285Sdim return; 360234285Sdim std::map<std::string, unsigned> NameToBitsMap; 361234285Sdim 362234285Sdim // Parse functional units for all the itineraries. 363234285Sdim for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { 364234285Sdim Record *Proc = ProcItinList[i]; 365234285Sdim std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); 366234285Sdim 367234285Sdim // Convert macros to bits for each stage. 368234285Sdim for (unsigned i = 0, N = FUs.size(); i < N; ++i) 369234285Sdim NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); 370234285Sdim } 371234285Sdim 372234285Sdim const std::vector<Record*> &StageList = 373234285Sdim ItinData->getValueAsListOfDefs("Stages"); 374234285Sdim 375234285Sdim // The number of stages. 376234285Sdim NStages = StageList.size(); 377234285Sdim 378234285Sdim // For each unit. 379234285Sdim unsigned UnitBitValue = 0; 380234285Sdim 381234285Sdim // Compute the bitwise or of each unit used in this stage. 382234285Sdim for (unsigned i = 0; i < NStages; ++i) { 383234285Sdim const Record *Stage = StageList[i]; 384234285Sdim 385234285Sdim // Get unit list. 386234285Sdim const std::vector<Record*> &UnitList = 387234285Sdim Stage->getValueAsListOfDefs("Units"); 388234285Sdim 389234285Sdim for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { 390234285Sdim // Conduct bitwise or. 391234285Sdim std::string UnitName = UnitList[j]->getName(); 392234285Sdim assert(NameToBitsMap.count(UnitName)); 393234285Sdim UnitBitValue |= NameToBitsMap[UnitName]; 394234285Sdim } 395234285Sdim 396234285Sdim if (UnitBitValue != 0) 397234285Sdim allInsnClasses.insert(UnitBitValue); 398234285Sdim } 399234285Sdim} 400234285Sdim 401234285Sdim 402234285Sdim// 403234285Sdim// Run the worklist algorithm to generate the DFA. 404234285Sdim// 405234285Sdimvoid DFAGen::run(raw_ostream &OS) { 406234285Sdim EmitSourceFileHeader("Target DFA Packetizer Tables", OS); 407234285Sdim 408234285Sdim // Collect processor iteraries. 409234285Sdim std::vector<Record*> ProcItinList = 410234285Sdim Records.getAllDerivedDefinitions("ProcessorItineraries"); 411234285Sdim 412234285Sdim // 413234285Sdim // Collect the instruction classes. 414234285Sdim // 415234285Sdim for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { 416234285Sdim Record *Proc = ProcItinList[i]; 417234285Sdim 418234285Sdim // Get processor itinerary name. 419234285Sdim const std::string &Name = Proc->getName(); 420234285Sdim 421234285Sdim // Skip default. 422234285Sdim if (Name == "NoItineraries") 423234285Sdim continue; 424234285Sdim 425234285Sdim // Sanity check for at least one instruction itinerary class. 426234285Sdim unsigned NItinClasses = 427234285Sdim Records.getAllDerivedDefinitions("InstrItinClass").size(); 428234285Sdim if (NItinClasses == 0) 429234285Sdim return; 430234285Sdim 431234285Sdim // Get itinerary data list. 432234285Sdim std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); 433234285Sdim 434234285Sdim // Collect instruction classes for all itinerary data. 435234285Sdim for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { 436234285Sdim Record *ItinData = ItinDataList[j]; 437234285Sdim unsigned NStages; 438234285Sdim collectAllInsnClasses(Name, ItinData, NStages, OS); 439234285Sdim } 440234285Sdim } 441234285Sdim 442234285Sdim 443234285Sdim // 444234285Sdim // Run a worklist algorithm to generate the DFA. 445234285Sdim // 446234285Sdim DFA D; 447234285Sdim State *Initial = new State; 448234285Sdim Initial->isInitial = true; 449234285Sdim Initial->stateInfo.insert(0x0); 450234285Sdim D.addState(Initial); 451234285Sdim SmallVector<State*, 32> WorkList; 452234285Sdim std::map<std::set<unsigned>, State*> Visited; 453234285Sdim 454234285Sdim WorkList.push_back(Initial); 455234285Sdim 456234285Sdim // 457234285Sdim // Worklist algorithm to create a DFA for processor resource tracking. 458234285Sdim // C = {set of InsnClasses} 459234285Sdim // Begin with initial node in worklist. Initial node does not have 460234285Sdim // any consumed resources, 461234285Sdim // ResourceState = 0x0 462234285Sdim // Visited = {} 463234285Sdim // While worklist != empty 464234285Sdim // S = first element of worklist 465234285Sdim // For every instruction class C 466234285Sdim // if we can accommodate C in S: 467234285Sdim // S' = state with resource states = {S Union C} 468234285Sdim // Add a new transition: S x C -> S' 469234285Sdim // If S' is not in Visited: 470234285Sdim // Add S' to worklist 471234285Sdim // Add S' to Visited 472234285Sdim // 473234285Sdim while (!WorkList.empty()) { 474234285Sdim State *current = WorkList.pop_back_val(); 475234285Sdim for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(), 476234285Sdim CE = allInsnClasses.end(); CI != CE; ++CI) { 477234285Sdim unsigned InsnClass = *CI; 478234285Sdim 479234285Sdim std::set<unsigned> NewStateResources; 480234285Sdim // 481234285Sdim // If we haven't already created a transition for this input 482234285Sdim // and the state can accommodate this InsnClass, create a transition. 483234285Sdim // 484234285Sdim if (!D.getTransition(current, InsnClass) && 485234285Sdim current->canAddInsnClass(InsnClass, NewStateResources)) { 486234285Sdim State *NewState = NULL; 487234285Sdim 488234285Sdim // 489234285Sdim // If we have seen this state before, then do not create a new state. 490234285Sdim // 491234285Sdim // 492234285Sdim std::map<std::set<unsigned>, State*>::iterator VI; 493234285Sdim if ((VI = Visited.find(NewStateResources)) != Visited.end()) 494234285Sdim NewState = VI->second; 495234285Sdim else { 496234285Sdim NewState = new State; 497234285Sdim NewState->stateInfo = NewStateResources; 498234285Sdim D.addState(NewState); 499234285Sdim Visited[NewStateResources] = NewState; 500234285Sdim WorkList.push_back(NewState); 501234285Sdim } 502234285Sdim 503234285Sdim Transition *NewTransition = new Transition(current, InsnClass, 504234285Sdim NewState); 505234285Sdim D.addTransition(NewTransition); 506234285Sdim } 507234285Sdim } 508234285Sdim } 509234285Sdim 510234285Sdim // Print out the table. 511234285Sdim D.writeTableAndAPI(OS, TargetName); 512234285Sdim} 513