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