1*8bcb0991SDimitry Andric //===- DFAEmitter.cpp - Finite state automaton emitter --------------------===// 2*8bcb0991SDimitry Andric // 3*8bcb0991SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*8bcb0991SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5*8bcb0991SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*8bcb0991SDimitry Andric // 7*8bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 8*8bcb0991SDimitry Andric // 9*8bcb0991SDimitry Andric // This class can produce a generic deterministic finite state automaton (DFA), 10*8bcb0991SDimitry Andric // given a set of possible states and transitions. 11*8bcb0991SDimitry Andric // 12*8bcb0991SDimitry Andric // The input transitions can be nondeterministic - this class will produce the 13*8bcb0991SDimitry Andric // deterministic equivalent state machine. 14*8bcb0991SDimitry Andric // 15*8bcb0991SDimitry Andric // The generated code can run the DFA and produce an accepted / not accepted 16*8bcb0991SDimitry Andric // state and also produce, given a sequence of transitions that results in an 17*8bcb0991SDimitry Andric // accepted state, the sequence of intermediate states. This is useful if the 18*8bcb0991SDimitry Andric // initial automaton was nondeterministic - it allows mapping back from the DFA 19*8bcb0991SDimitry Andric // to the NFA. 20*8bcb0991SDimitry Andric // 21*8bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 22*8bcb0991SDimitry Andric #define DEBUG_TYPE "dfa-emitter" 23*8bcb0991SDimitry Andric 24*8bcb0991SDimitry Andric #include "DFAEmitter.h" 25*8bcb0991SDimitry Andric #include "CodeGenTarget.h" 26*8bcb0991SDimitry Andric #include "SequenceToOffsetTable.h" 27*8bcb0991SDimitry Andric #include "TableGenBackends.h" 28*8bcb0991SDimitry Andric #include "llvm/ADT/SmallVector.h" 29*8bcb0991SDimitry Andric #include "llvm/ADT/StringExtras.h" 30*8bcb0991SDimitry Andric #include "llvm/ADT/UniqueVector.h" 31*8bcb0991SDimitry Andric #include "llvm/Support/Debug.h" 32*8bcb0991SDimitry Andric #include "llvm/Support/raw_ostream.h" 33*8bcb0991SDimitry Andric #include "llvm/TableGen/Record.h" 34*8bcb0991SDimitry Andric #include "llvm/TableGen/TableGenBackend.h" 35*8bcb0991SDimitry Andric #include <cassert> 36*8bcb0991SDimitry Andric #include <cstdint> 37*8bcb0991SDimitry Andric #include <map> 38*8bcb0991SDimitry Andric #include <set> 39*8bcb0991SDimitry Andric #include <string> 40*8bcb0991SDimitry Andric #include <vector> 41*8bcb0991SDimitry Andric 42*8bcb0991SDimitry Andric using namespace llvm; 43*8bcb0991SDimitry Andric 44*8bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 45*8bcb0991SDimitry Andric // DfaEmitter implementation. This is independent of the GenAutomaton backend. 46*8bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 47*8bcb0991SDimitry Andric 48*8bcb0991SDimitry Andric void DfaEmitter::addTransition(state_type From, state_type To, action_type A) { 49*8bcb0991SDimitry Andric Actions.insert(A); 50*8bcb0991SDimitry Andric NfaStates.insert(From); 51*8bcb0991SDimitry Andric NfaStates.insert(To); 52*8bcb0991SDimitry Andric NfaTransitions[{From, A}].push_back(To); 53*8bcb0991SDimitry Andric ++NumNfaTransitions; 54*8bcb0991SDimitry Andric } 55*8bcb0991SDimitry Andric 56*8bcb0991SDimitry Andric void DfaEmitter::visitDfaState(DfaState DS) { 57*8bcb0991SDimitry Andric // For every possible action... 58*8bcb0991SDimitry Andric auto FromId = DfaStates.idFor(DS); 59*8bcb0991SDimitry Andric for (action_type A : Actions) { 60*8bcb0991SDimitry Andric DfaState NewStates; 61*8bcb0991SDimitry Andric DfaTransitionInfo TI; 62*8bcb0991SDimitry Andric // For every represented state, word pair in the original NFA... 63*8bcb0991SDimitry Andric for (state_type &FromState : DS) { 64*8bcb0991SDimitry Andric // If this action is possible from this state add the transitioned-to 65*8bcb0991SDimitry Andric // states to NewStates. 66*8bcb0991SDimitry Andric auto I = NfaTransitions.find({FromState, A}); 67*8bcb0991SDimitry Andric if (I == NfaTransitions.end()) 68*8bcb0991SDimitry Andric continue; 69*8bcb0991SDimitry Andric for (state_type &ToState : I->second) { 70*8bcb0991SDimitry Andric NewStates.push_back(ToState); 71*8bcb0991SDimitry Andric TI.emplace_back(FromState, ToState); 72*8bcb0991SDimitry Andric } 73*8bcb0991SDimitry Andric } 74*8bcb0991SDimitry Andric if (NewStates.empty()) 75*8bcb0991SDimitry Andric continue; 76*8bcb0991SDimitry Andric // Sort and unique. 77*8bcb0991SDimitry Andric sort(NewStates); 78*8bcb0991SDimitry Andric NewStates.erase(std::unique(NewStates.begin(), NewStates.end()), 79*8bcb0991SDimitry Andric NewStates.end()); 80*8bcb0991SDimitry Andric sort(TI); 81*8bcb0991SDimitry Andric TI.erase(std::unique(TI.begin(), TI.end()), TI.end()); 82*8bcb0991SDimitry Andric unsigned ToId = DfaStates.insert(NewStates); 83*8bcb0991SDimitry Andric DfaTransitions.emplace(std::make_pair(FromId, A), std::make_pair(ToId, TI)); 84*8bcb0991SDimitry Andric } 85*8bcb0991SDimitry Andric } 86*8bcb0991SDimitry Andric 87*8bcb0991SDimitry Andric void DfaEmitter::constructDfa() { 88*8bcb0991SDimitry Andric DfaState Initial(1, /*NFA initial state=*/0); 89*8bcb0991SDimitry Andric DfaStates.insert(Initial); 90*8bcb0991SDimitry Andric 91*8bcb0991SDimitry Andric // Note that UniqueVector starts indices at 1, not zero. 92*8bcb0991SDimitry Andric unsigned DfaStateId = 1; 93*8bcb0991SDimitry Andric while (DfaStateId <= DfaStates.size()) 94*8bcb0991SDimitry Andric visitDfaState(DfaStates[DfaStateId++]); 95*8bcb0991SDimitry Andric } 96*8bcb0991SDimitry Andric 97*8bcb0991SDimitry Andric void DfaEmitter::emit(StringRef Name, raw_ostream &OS) { 98*8bcb0991SDimitry Andric constructDfa(); 99*8bcb0991SDimitry Andric 100*8bcb0991SDimitry Andric OS << "// Input NFA has " << NfaStates.size() << " states with " 101*8bcb0991SDimitry Andric << NumNfaTransitions << " transitions.\n"; 102*8bcb0991SDimitry Andric OS << "// Generated DFA has " << DfaStates.size() << " states with " 103*8bcb0991SDimitry Andric << DfaTransitions.size() << " transitions.\n\n"; 104*8bcb0991SDimitry Andric 105*8bcb0991SDimitry Andric // Implementation note: We don't bake a simple std::pair<> here as it requires 106*8bcb0991SDimitry Andric // significantly more effort to parse. A simple test with a large array of 107*8bcb0991SDimitry Andric // struct-pairs (N=100000) took clang-10 6s to parse. The same array of 108*8bcb0991SDimitry Andric // std::pair<uint64_t, uint64_t> took 242s. Instead we allow the user to 109*8bcb0991SDimitry Andric // define the pair type. 110*8bcb0991SDimitry Andric // 111*8bcb0991SDimitry Andric // FIXME: It may make sense to emit these as ULEB sequences instead of 112*8bcb0991SDimitry Andric // pairs of uint64_t. 113*8bcb0991SDimitry Andric OS << "// A zero-terminated sequence of NFA state transitions. Every DFA\n"; 114*8bcb0991SDimitry Andric OS << "// transition implies a set of NFA transitions. These are referred\n"; 115*8bcb0991SDimitry Andric OS << "// to by index in " << Name << "Transitions[].\n"; 116*8bcb0991SDimitry Andric 117*8bcb0991SDimitry Andric SequenceToOffsetTable<DfaTransitionInfo> Table; 118*8bcb0991SDimitry Andric std::map<DfaTransitionInfo, unsigned> EmittedIndices; 119*8bcb0991SDimitry Andric for (auto &T : DfaTransitions) 120*8bcb0991SDimitry Andric Table.add(T.second.second); 121*8bcb0991SDimitry Andric Table.layout(); 122*8bcb0991SDimitry Andric OS << "std::array<NfaStatePair, " << Table.size() << "> " << Name 123*8bcb0991SDimitry Andric << "TransitionInfo = {{\n"; 124*8bcb0991SDimitry Andric Table.emit( 125*8bcb0991SDimitry Andric OS, 126*8bcb0991SDimitry Andric [](raw_ostream &OS, std::pair<uint64_t, uint64_t> P) { 127*8bcb0991SDimitry Andric OS << "{" << P.first << ", " << P.second << "}"; 128*8bcb0991SDimitry Andric }, 129*8bcb0991SDimitry Andric "{0ULL, 0ULL}"); 130*8bcb0991SDimitry Andric 131*8bcb0991SDimitry Andric OS << "}};\n\n"; 132*8bcb0991SDimitry Andric 133*8bcb0991SDimitry Andric OS << "// A transition in the generated " << Name << " DFA.\n"; 134*8bcb0991SDimitry Andric OS << "struct " << Name << "Transition {\n"; 135*8bcb0991SDimitry Andric OS << " unsigned FromDfaState; // The transitioned-from DFA state.\n"; 136*8bcb0991SDimitry Andric OS << " "; 137*8bcb0991SDimitry Andric printActionType(OS); 138*8bcb0991SDimitry Andric OS << " Action; // The input symbol that causes this transition.\n"; 139*8bcb0991SDimitry Andric OS << " unsigned ToDfaState; // The transitioned-to DFA state.\n"; 140*8bcb0991SDimitry Andric OS << " unsigned InfoIdx; // Start index into " << Name 141*8bcb0991SDimitry Andric << "TransitionInfo.\n"; 142*8bcb0991SDimitry Andric OS << "};\n\n"; 143*8bcb0991SDimitry Andric 144*8bcb0991SDimitry Andric OS << "// A table of DFA transitions, ordered by {FromDfaState, Action}.\n"; 145*8bcb0991SDimitry Andric OS << "// The initial state is 1, not zero.\n"; 146*8bcb0991SDimitry Andric OS << "std::array<" << Name << "Transition, " << DfaTransitions.size() << "> " 147*8bcb0991SDimitry Andric << Name << "Transitions = {{\n"; 148*8bcb0991SDimitry Andric for (auto &KV : DfaTransitions) { 149*8bcb0991SDimitry Andric dfa_state_type From = KV.first.first; 150*8bcb0991SDimitry Andric dfa_state_type To = KV.second.first; 151*8bcb0991SDimitry Andric action_type A = KV.first.second; 152*8bcb0991SDimitry Andric unsigned InfoIdx = Table.get(KV.second.second); 153*8bcb0991SDimitry Andric OS << " {" << From << ", "; 154*8bcb0991SDimitry Andric printActionValue(A, OS); 155*8bcb0991SDimitry Andric OS << ", " << To << ", " << InfoIdx << "},\n"; 156*8bcb0991SDimitry Andric } 157*8bcb0991SDimitry Andric OS << "\n}};\n\n"; 158*8bcb0991SDimitry Andric } 159*8bcb0991SDimitry Andric 160*8bcb0991SDimitry Andric void DfaEmitter::printActionType(raw_ostream &OS) { OS << "uint64_t"; } 161*8bcb0991SDimitry Andric 162*8bcb0991SDimitry Andric void DfaEmitter::printActionValue(action_type A, raw_ostream &OS) { OS << A; } 163*8bcb0991SDimitry Andric 164*8bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 165*8bcb0991SDimitry Andric // AutomatonEmitter implementation 166*8bcb0991SDimitry Andric //===----------------------------------------------------------------------===// 167*8bcb0991SDimitry Andric 168*8bcb0991SDimitry Andric namespace { 169*8bcb0991SDimitry Andric // FIXME: This entire discriminated union could be removed with c++17: 170*8bcb0991SDimitry Andric // using Action = std::variant<Record *, unsigned, std::string>; 171*8bcb0991SDimitry Andric struct Action { 172*8bcb0991SDimitry Andric Record *R = nullptr; 173*8bcb0991SDimitry Andric unsigned I = 0; 174*8bcb0991SDimitry Andric std::string S = nullptr; 175*8bcb0991SDimitry Andric 176*8bcb0991SDimitry Andric Action() = default; 177*8bcb0991SDimitry Andric Action(Record *R, unsigned I, std::string S) : R(R), I(I), S(S) {} 178*8bcb0991SDimitry Andric 179*8bcb0991SDimitry Andric void print(raw_ostream &OS) const { 180*8bcb0991SDimitry Andric if (R) 181*8bcb0991SDimitry Andric OS << R->getName(); 182*8bcb0991SDimitry Andric else if (!S.empty()) 183*8bcb0991SDimitry Andric OS << '"' << S << '"'; 184*8bcb0991SDimitry Andric else 185*8bcb0991SDimitry Andric OS << I; 186*8bcb0991SDimitry Andric } 187*8bcb0991SDimitry Andric bool operator<(const Action &Other) const { 188*8bcb0991SDimitry Andric return std::make_tuple(R, I, S) < 189*8bcb0991SDimitry Andric std::make_tuple(Other.R, Other.I, Other.S); 190*8bcb0991SDimitry Andric } 191*8bcb0991SDimitry Andric }; 192*8bcb0991SDimitry Andric 193*8bcb0991SDimitry Andric using ActionTuple = std::vector<Action>; 194*8bcb0991SDimitry Andric class Automaton; 195*8bcb0991SDimitry Andric 196*8bcb0991SDimitry Andric class Transition { 197*8bcb0991SDimitry Andric uint64_t NewState; 198*8bcb0991SDimitry Andric // The tuple of actions that causes this transition. 199*8bcb0991SDimitry Andric ActionTuple Actions; 200*8bcb0991SDimitry Andric // The types of the actions; this is the same across all transitions. 201*8bcb0991SDimitry Andric SmallVector<std::string, 4> Types; 202*8bcb0991SDimitry Andric 203*8bcb0991SDimitry Andric public: 204*8bcb0991SDimitry Andric Transition(Record *R, Automaton *Parent); 205*8bcb0991SDimitry Andric const ActionTuple &getActions() { return Actions; } 206*8bcb0991SDimitry Andric SmallVector<std::string, 4> getTypes() { return Types; } 207*8bcb0991SDimitry Andric 208*8bcb0991SDimitry Andric bool canTransitionFrom(uint64_t State); 209*8bcb0991SDimitry Andric uint64_t transitionFrom(uint64_t State); 210*8bcb0991SDimitry Andric }; 211*8bcb0991SDimitry Andric 212*8bcb0991SDimitry Andric class Automaton { 213*8bcb0991SDimitry Andric RecordKeeper &Records; 214*8bcb0991SDimitry Andric Record *R; 215*8bcb0991SDimitry Andric std::vector<Transition> Transitions; 216*8bcb0991SDimitry Andric /// All possible action tuples, uniqued. 217*8bcb0991SDimitry Andric UniqueVector<ActionTuple> Actions; 218*8bcb0991SDimitry Andric /// The fields within each Transition object to find the action symbols. 219*8bcb0991SDimitry Andric std::vector<StringRef> ActionSymbolFields; 220*8bcb0991SDimitry Andric 221*8bcb0991SDimitry Andric public: 222*8bcb0991SDimitry Andric Automaton(RecordKeeper &Records, Record *R); 223*8bcb0991SDimitry Andric void emit(raw_ostream &OS); 224*8bcb0991SDimitry Andric 225*8bcb0991SDimitry Andric ArrayRef<StringRef> getActionSymbolFields() { return ActionSymbolFields; } 226*8bcb0991SDimitry Andric /// If the type of action A has been overridden (there exists a field 227*8bcb0991SDimitry Andric /// "TypeOf_A") return that, otherwise return the empty string. 228*8bcb0991SDimitry Andric StringRef getActionSymbolType(StringRef A); 229*8bcb0991SDimitry Andric }; 230*8bcb0991SDimitry Andric 231*8bcb0991SDimitry Andric class AutomatonEmitter { 232*8bcb0991SDimitry Andric RecordKeeper &Records; 233*8bcb0991SDimitry Andric 234*8bcb0991SDimitry Andric public: 235*8bcb0991SDimitry Andric AutomatonEmitter(RecordKeeper &R) : Records(R) {} 236*8bcb0991SDimitry Andric void run(raw_ostream &OS); 237*8bcb0991SDimitry Andric }; 238*8bcb0991SDimitry Andric 239*8bcb0991SDimitry Andric /// A DfaEmitter implementation that can print our variant action type. 240*8bcb0991SDimitry Andric class CustomDfaEmitter : public DfaEmitter { 241*8bcb0991SDimitry Andric const UniqueVector<ActionTuple> &Actions; 242*8bcb0991SDimitry Andric std::string TypeName; 243*8bcb0991SDimitry Andric 244*8bcb0991SDimitry Andric public: 245*8bcb0991SDimitry Andric CustomDfaEmitter(const UniqueVector<ActionTuple> &Actions, StringRef TypeName) 246*8bcb0991SDimitry Andric : Actions(Actions), TypeName(TypeName) {} 247*8bcb0991SDimitry Andric 248*8bcb0991SDimitry Andric void printActionType(raw_ostream &OS) override; 249*8bcb0991SDimitry Andric void printActionValue(action_type A, raw_ostream &OS) override; 250*8bcb0991SDimitry Andric }; 251*8bcb0991SDimitry Andric } // namespace 252*8bcb0991SDimitry Andric 253*8bcb0991SDimitry Andric void AutomatonEmitter::run(raw_ostream &OS) { 254*8bcb0991SDimitry Andric for (Record *R : Records.getAllDerivedDefinitions("GenericAutomaton")) { 255*8bcb0991SDimitry Andric Automaton A(Records, R); 256*8bcb0991SDimitry Andric OS << "#ifdef GET_" << R->getName() << "_DECL\n"; 257*8bcb0991SDimitry Andric A.emit(OS); 258*8bcb0991SDimitry Andric OS << "#endif // GET_" << R->getName() << "_DECL\n"; 259*8bcb0991SDimitry Andric } 260*8bcb0991SDimitry Andric } 261*8bcb0991SDimitry Andric 262*8bcb0991SDimitry Andric Automaton::Automaton(RecordKeeper &Records, Record *R) 263*8bcb0991SDimitry Andric : Records(Records), R(R) { 264*8bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << "Emitting automaton for " << R->getName() << "\n"); 265*8bcb0991SDimitry Andric ActionSymbolFields = R->getValueAsListOfStrings("SymbolFields"); 266*8bcb0991SDimitry Andric } 267*8bcb0991SDimitry Andric 268*8bcb0991SDimitry Andric void Automaton::emit(raw_ostream &OS) { 269*8bcb0991SDimitry Andric StringRef TransitionClass = R->getValueAsString("TransitionClass"); 270*8bcb0991SDimitry Andric for (Record *T : Records.getAllDerivedDefinitions(TransitionClass)) { 271*8bcb0991SDimitry Andric assert(T->isSubClassOf("Transition")); 272*8bcb0991SDimitry Andric Transitions.emplace_back(T, this); 273*8bcb0991SDimitry Andric Actions.insert(Transitions.back().getActions()); 274*8bcb0991SDimitry Andric } 275*8bcb0991SDimitry Andric 276*8bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << " Action alphabet cardinality: " << Actions.size() 277*8bcb0991SDimitry Andric << "\n"); 278*8bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << " Each state has " << Transitions.size() 279*8bcb0991SDimitry Andric << " potential transitions.\n"); 280*8bcb0991SDimitry Andric 281*8bcb0991SDimitry Andric StringRef Name = R->getName(); 282*8bcb0991SDimitry Andric 283*8bcb0991SDimitry Andric CustomDfaEmitter Emitter(Actions, std::string(Name) + "Action"); 284*8bcb0991SDimitry Andric // Starting from the initial state, build up a list of possible states and 285*8bcb0991SDimitry Andric // transitions. 286*8bcb0991SDimitry Andric std::deque<uint64_t> Worklist(1, 0); 287*8bcb0991SDimitry Andric std::set<uint64_t> SeenStates; 288*8bcb0991SDimitry Andric unsigned NumTransitions = 0; 289*8bcb0991SDimitry Andric SeenStates.insert(Worklist.front()); 290*8bcb0991SDimitry Andric while (!Worklist.empty()) { 291*8bcb0991SDimitry Andric uint64_t State = Worklist.front(); 292*8bcb0991SDimitry Andric Worklist.pop_front(); 293*8bcb0991SDimitry Andric for (Transition &T : Transitions) { 294*8bcb0991SDimitry Andric if (!T.canTransitionFrom(State)) 295*8bcb0991SDimitry Andric continue; 296*8bcb0991SDimitry Andric uint64_t NewState = T.transitionFrom(State); 297*8bcb0991SDimitry Andric if (SeenStates.emplace(NewState).second) 298*8bcb0991SDimitry Andric Worklist.emplace_back(NewState); 299*8bcb0991SDimitry Andric ++NumTransitions; 300*8bcb0991SDimitry Andric Emitter.addTransition(State, NewState, Actions.idFor(T.getActions())); 301*8bcb0991SDimitry Andric } 302*8bcb0991SDimitry Andric } 303*8bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << " NFA automaton has " << SeenStates.size() 304*8bcb0991SDimitry Andric << " states with " << NumTransitions << " transitions.\n"); 305*8bcb0991SDimitry Andric 306*8bcb0991SDimitry Andric const auto &ActionTypes = Transitions.back().getTypes(); 307*8bcb0991SDimitry Andric OS << "// The type of an action in the " << Name << " automaton.\n"; 308*8bcb0991SDimitry Andric if (ActionTypes.size() == 1) { 309*8bcb0991SDimitry Andric OS << "using " << Name << "Action = " << ActionTypes[0] << ";\n"; 310*8bcb0991SDimitry Andric } else { 311*8bcb0991SDimitry Andric OS << "using " << Name << "Action = std::tuple<" << join(ActionTypes, ", ") 312*8bcb0991SDimitry Andric << ">;\n"; 313*8bcb0991SDimitry Andric } 314*8bcb0991SDimitry Andric OS << "\n"; 315*8bcb0991SDimitry Andric 316*8bcb0991SDimitry Andric Emitter.emit(Name, OS); 317*8bcb0991SDimitry Andric } 318*8bcb0991SDimitry Andric 319*8bcb0991SDimitry Andric StringRef Automaton::getActionSymbolType(StringRef A) { 320*8bcb0991SDimitry Andric Twine Ty = "TypeOf_" + A; 321*8bcb0991SDimitry Andric if (!R->getValue(Ty.str())) 322*8bcb0991SDimitry Andric return ""; 323*8bcb0991SDimitry Andric return R->getValueAsString(Ty.str()); 324*8bcb0991SDimitry Andric } 325*8bcb0991SDimitry Andric 326*8bcb0991SDimitry Andric Transition::Transition(Record *R, Automaton *Parent) { 327*8bcb0991SDimitry Andric BitsInit *NewStateInit = R->getValueAsBitsInit("NewState"); 328*8bcb0991SDimitry Andric NewState = 0; 329*8bcb0991SDimitry Andric assert(NewStateInit->getNumBits() <= sizeof(uint64_t) * 8 && 330*8bcb0991SDimitry Andric "State cannot be represented in 64 bits!"); 331*8bcb0991SDimitry Andric for (unsigned I = 0; I < NewStateInit->getNumBits(); ++I) { 332*8bcb0991SDimitry Andric if (auto *Bit = dyn_cast<BitInit>(NewStateInit->getBit(I))) { 333*8bcb0991SDimitry Andric if (Bit->getValue()) 334*8bcb0991SDimitry Andric NewState |= 1ULL << I; 335*8bcb0991SDimitry Andric } 336*8bcb0991SDimitry Andric } 337*8bcb0991SDimitry Andric 338*8bcb0991SDimitry Andric for (StringRef A : Parent->getActionSymbolFields()) { 339*8bcb0991SDimitry Andric RecordVal *SymbolV = R->getValue(A); 340*8bcb0991SDimitry Andric if (auto *Ty = dyn_cast<RecordRecTy>(SymbolV->getType())) { 341*8bcb0991SDimitry Andric Actions.emplace_back(R->getValueAsDef(A), 0, ""); 342*8bcb0991SDimitry Andric Types.emplace_back(Ty->getAsString()); 343*8bcb0991SDimitry Andric } else if (isa<IntRecTy>(SymbolV->getType())) { 344*8bcb0991SDimitry Andric Actions.emplace_back(nullptr, R->getValueAsInt(A), ""); 345*8bcb0991SDimitry Andric Types.emplace_back("unsigned"); 346*8bcb0991SDimitry Andric } else if (isa<StringRecTy>(SymbolV->getType()) || 347*8bcb0991SDimitry Andric isa<CodeRecTy>(SymbolV->getType())) { 348*8bcb0991SDimitry Andric Actions.emplace_back(nullptr, 0, R->getValueAsString(A)); 349*8bcb0991SDimitry Andric Types.emplace_back("std::string"); 350*8bcb0991SDimitry Andric } else { 351*8bcb0991SDimitry Andric report_fatal_error("Unhandled symbol type!"); 352*8bcb0991SDimitry Andric } 353*8bcb0991SDimitry Andric 354*8bcb0991SDimitry Andric StringRef TypeOverride = Parent->getActionSymbolType(A); 355*8bcb0991SDimitry Andric if (!TypeOverride.empty()) 356*8bcb0991SDimitry Andric Types.back() = TypeOverride; 357*8bcb0991SDimitry Andric } 358*8bcb0991SDimitry Andric } 359*8bcb0991SDimitry Andric 360*8bcb0991SDimitry Andric bool Transition::canTransitionFrom(uint64_t State) { 361*8bcb0991SDimitry Andric if ((State & NewState) == 0) 362*8bcb0991SDimitry Andric // The bits we want to set are not set; 363*8bcb0991SDimitry Andric return true; 364*8bcb0991SDimitry Andric return false; 365*8bcb0991SDimitry Andric } 366*8bcb0991SDimitry Andric 367*8bcb0991SDimitry Andric uint64_t Transition::transitionFrom(uint64_t State) { 368*8bcb0991SDimitry Andric return State | NewState; 369*8bcb0991SDimitry Andric } 370*8bcb0991SDimitry Andric 371*8bcb0991SDimitry Andric void CustomDfaEmitter::printActionType(raw_ostream &OS) { OS << TypeName; } 372*8bcb0991SDimitry Andric 373*8bcb0991SDimitry Andric void CustomDfaEmitter::printActionValue(action_type A, raw_ostream &OS) { 374*8bcb0991SDimitry Andric const ActionTuple &AT = Actions[A]; 375*8bcb0991SDimitry Andric if (AT.size() > 1) 376*8bcb0991SDimitry Andric OS << "std::make_tuple("; 377*8bcb0991SDimitry Andric bool First = true; 378*8bcb0991SDimitry Andric for (const auto &SingleAction : AT) { 379*8bcb0991SDimitry Andric if (!First) 380*8bcb0991SDimitry Andric OS << ", "; 381*8bcb0991SDimitry Andric First = false; 382*8bcb0991SDimitry Andric SingleAction.print(OS); 383*8bcb0991SDimitry Andric } 384*8bcb0991SDimitry Andric if (AT.size() > 1) 385*8bcb0991SDimitry Andric OS << ")"; 386*8bcb0991SDimitry Andric } 387*8bcb0991SDimitry Andric 388*8bcb0991SDimitry Andric namespace llvm { 389*8bcb0991SDimitry Andric 390*8bcb0991SDimitry Andric void EmitAutomata(RecordKeeper &RK, raw_ostream &OS) { 391*8bcb0991SDimitry Andric AutomatonEmitter(RK).run(OS); 392*8bcb0991SDimitry Andric } 393*8bcb0991SDimitry Andric 394*8bcb0991SDimitry Andric } // namespace llvm 395