[TableGen] Introduce a generic automaton (DFA) backend
Summary:
This patch introduces -gen-automata, a backend for generating deterministic finite-state automata.
DFAs are already generated by the -gen-dfa-packetizer backend. This backend is more generic and will
hopefully be used to implement the DFA generation (and determinization) for the packetizer in the
future.
This backend allows not only generation of a DFA from an NFA (nondeterministic finite-state
automaton), it also emits sidetables that allow a path through the DFA under a sequence of inputs to
be analyzed, and the equivalent set of all possible NFA transitions extracted.
This allows a user to not just answer "can my problem be solved?" but also "what is the
solution?". Clearly this analysis is more expensive than just playing a DFA forwards so is
opt-in. The DFAPacketizer has this behaviour already but this is a more compact and generic
representation.
Examples are bundled in unittests/TableGen/Automata.td. Some are trivial, but the BinPacking example
is a stripped-down version of the original target problem I set out to solve, where we pack values
(actually immediates) into bins (an immediate pool in a VLIW bundle) subject to a set of esoteric
constraints.
Reviewers: t.p.northover
Subscribers: mgorny, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D67968
llvm-svn: 373718
diff --git a/llvm/utils/TableGen/CMakeLists.txt b/llvm/utils/TableGen/CMakeLists.txt
index 77ef764..407e10d 100644
--- a/llvm/utils/TableGen/CMakeLists.txt
+++ b/llvm/utils/TableGen/CMakeLists.txt
@@ -21,6 +21,7 @@
DAGISelMatcherGen.cpp
DAGISelMatcherOpt.cpp
DAGISelMatcher.cpp
+ DFAEmitter.cpp
DFAPacketizerEmitter.cpp
DisassemblerEmitter.cpp
ExegesisEmitter.cpp
diff --git a/llvm/utils/TableGen/DFAEmitter.cpp b/llvm/utils/TableGen/DFAEmitter.cpp
new file mode 100644
index 0000000..cf339dc
--- /dev/null
+++ b/llvm/utils/TableGen/DFAEmitter.cpp
@@ -0,0 +1,394 @@
+//===- DFAEmitter.cpp - Finite state automaton emitter --------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This class can produce a generic deterministic finite state automaton (DFA),
+// given a set of possible states and transitions.
+//
+// The input transitions can be nondeterministic - this class will produce the
+// deterministic equivalent state machine.
+//
+// The generated code can run the DFA and produce an accepted / not accepted
+// state and also produce, given a sequence of transitions that results in an
+// accepted state, the sequence of intermediate states. This is useful if the
+// initial automaton was nondeterministic - it allows mapping back from the DFA
+// to the NFA.
+//
+//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "dfa-emitter"
+
+#include "DFAEmitter.h"
+#include "CodeGenTarget.h"
+#include "SequenceToOffsetTable.h"
+#include "TableGenBackends.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/UniqueVector.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/TableGen/Record.h"
+#include "llvm/TableGen/TableGenBackend.h"
+#include <cassert>
+#include <cstdint>
+#include <map>
+#include <set>
+#include <string>
+#include <vector>
+
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+// DfaEmitter implementation. This is independent of the GenAutomaton backend.
+//===----------------------------------------------------------------------===//
+
+void DfaEmitter::addTransition(state_type From, state_type To, action_type A) {
+ Actions.insert(A);
+ NfaStates.insert(From);
+ NfaStates.insert(To);
+ NfaTransitions[{From, A}].push_back(To);
+ ++NumNfaTransitions;
+}
+
+void DfaEmitter::visitDfaState(DfaState DS) {
+ // For every possible action...
+ auto FromId = DfaStates.idFor(DS);
+ for (action_type A : Actions) {
+ DfaState NewStates;
+ DfaTransitionInfo TI;
+ // For every represented state, word pair in the original NFA...
+ for (state_type &FromState : DS) {
+ // If this action is possible from this state add the transitioned-to
+ // states to NewStates.
+ auto I = NfaTransitions.find({FromState, A});
+ if (I == NfaTransitions.end())
+ continue;
+ for (state_type &ToState : I->second) {
+ NewStates.push_back(ToState);
+ TI.emplace_back(FromState, ToState);
+ }
+ }
+ if (NewStates.empty())
+ continue;
+ // Sort and unique.
+ sort(NewStates);
+ NewStates.erase(std::unique(NewStates.begin(), NewStates.end()),
+ NewStates.end());
+ sort(TI);
+ TI.erase(std::unique(TI.begin(), TI.end()), TI.end());
+ unsigned ToId = DfaStates.insert(NewStates);
+ DfaTransitions.emplace(std::make_pair(FromId, A), std::make_pair(ToId, TI));
+ }
+}
+
+void DfaEmitter::constructDfa() {
+ DfaState Initial(1, /*NFA initial state=*/0);
+ DfaStates.insert(Initial);
+
+ // Note that UniqueVector starts indices at 1, not zero.
+ unsigned DfaStateId = 1;
+ while (DfaStateId <= DfaStates.size())
+ visitDfaState(DfaStates[DfaStateId++]);
+}
+
+void DfaEmitter::emit(StringRef Name, raw_ostream &OS) {
+ constructDfa();
+
+ OS << "// Input NFA has " << NfaStates.size() << " states with "
+ << NumNfaTransitions << " transitions.\n";
+ OS << "// Generated DFA has " << DfaStates.size() << " states with "
+ << DfaTransitions.size() << " transitions.\n\n";
+
+ // Implementation note: We don't bake a simple std::pair<> here as it requires
+ // significantly more effort to parse. A simple test with a large array of
+ // struct-pairs (N=100000) took clang-10 6s to parse. The same array of
+ // std::pair<uint64_t, uint64_t> took 242s. Instead we allow the user to
+ // define the pair type.
+ //
+ // FIXME: It may make sense to emit these as ULEB sequences instead of
+ // pairs of uint64_t.
+ OS << "// A zero-terminated sequence of NFA state transitions. Every DFA\n";
+ OS << "// transition implies a set of NFA transitions. These are referred\n";
+ OS << "// to by index in " << Name << "Transitions[].\n";
+
+ SequenceToOffsetTable<DfaTransitionInfo> Table;
+ std::map<DfaTransitionInfo, unsigned> EmittedIndices;
+ for (auto &T : DfaTransitions)
+ Table.add(T.second.second);
+ Table.layout();
+ OS << "std::array<NfaStatePair, " << Table.size() << "> " << Name
+ << "TransitionInfo = {{\n";
+ Table.emit(
+ OS,
+ [](raw_ostream &OS, std::pair<uint64_t, uint64_t> P) {
+ OS << "{" << P.first << ", " << P.second << "}";
+ },
+ "{0ULL, 0ULL}");
+
+ OS << "}};\n\n";
+
+ OS << "// A transition in the generated " << Name << " DFA.\n";
+ OS << "struct " << Name << "Transition {\n";
+ OS << " unsigned FromDfaState; // The transitioned-from DFA state.\n";
+ OS << " ";
+ printActionType(OS);
+ OS << " Action; // The input symbol that causes this transition.\n";
+ OS << " unsigned ToDfaState; // The transitioned-to DFA state.\n";
+ OS << " unsigned InfoIdx; // Start index into " << Name
+ << "TransitionInfo.\n";
+ OS << "};\n\n";
+
+ OS << "// A table of DFA transitions, ordered by {FromDfaState, Action}.\n";
+ OS << "// The initial state is 1, not zero.\n";
+ OS << "std::array<" << Name << "Transition, " << DfaTransitions.size() << "> "
+ << Name << "Transitions = {{\n";
+ for (auto &KV : DfaTransitions) {
+ dfa_state_type From = KV.first.first;
+ dfa_state_type To = KV.second.first;
+ action_type A = KV.first.second;
+ unsigned InfoIdx = Table.get(KV.second.second);
+ OS << " {" << From << ", ";
+ printActionValue(A, OS);
+ OS << ", " << To << ", " << InfoIdx << "},\n";
+ }
+ OS << "\n}};\n\n";
+}
+
+void DfaEmitter::printActionType(raw_ostream &OS) { OS << "uint64_t"; }
+
+void DfaEmitter::printActionValue(action_type A, raw_ostream &OS) { OS << A; }
+
+//===----------------------------------------------------------------------===//
+// AutomatonEmitter implementation
+//===----------------------------------------------------------------------===//
+
+namespace {
+// FIXME: This entire discriminated union could be removed with c++17:
+// using Action = std::variant<Record *, unsigned, std::string>;
+struct Action {
+ Record *R = nullptr;
+ unsigned I = 0;
+ std::string S = nullptr;
+
+ Action() = default;
+ Action(Record *R, unsigned I, std::string S) : R(R), I(I), S(S) {}
+
+ void print(raw_ostream &OS) const {
+ if (R)
+ OS << R->getName();
+ else if (!S.empty())
+ OS << '"' << S << '"';
+ else
+ OS << I;
+ }
+ bool operator<(const Action &Other) const {
+ return std::make_tuple(R, I, S) <
+ std::make_tuple(Other.R, Other.I, Other.S);
+ }
+};
+
+using ActionTuple = std::vector<Action>;
+class Automaton;
+
+class Transition {
+ uint64_t NewState;
+ // The tuple of actions that causes this transition.
+ ActionTuple Actions;
+ // The types of the actions; this is the same across all transitions.
+ SmallVector<std::string, 4> Types;
+
+public:
+ Transition(Record *R, Automaton *Parent);
+ const ActionTuple &getActions() { return Actions; }
+ SmallVector<std::string, 4> getTypes() { return Types; }
+
+ bool canTransitionFrom(uint64_t State);
+ uint64_t transitionFrom(uint64_t State);
+};
+
+class Automaton {
+ RecordKeeper &Records;
+ Record *R;
+ std::vector<Transition> Transitions;
+ /// All possible action tuples, uniqued.
+ UniqueVector<ActionTuple> Actions;
+ /// The fields within each Transition object to find the action symbols.
+ std::vector<StringRef> ActionSymbolFields;
+
+public:
+ Automaton(RecordKeeper &Records, Record *R);
+ void emit(raw_ostream &OS);
+
+ ArrayRef<StringRef> getActionSymbolFields() { return ActionSymbolFields; }
+ /// If the type of action A has been overridden (there exists a field
+ /// "TypeOf_A") return that, otherwise return the empty string.
+ StringRef getActionSymbolType(StringRef A);
+};
+
+class AutomatonEmitter {
+ RecordKeeper &Records;
+
+public:
+ AutomatonEmitter(RecordKeeper &R) : Records(R) {}
+ void run(raw_ostream &OS);
+};
+
+/// A DfaEmitter implementation that can print our variant action type.
+class CustomDfaEmitter : public DfaEmitter {
+ const UniqueVector<ActionTuple> &Actions;
+ std::string TypeName;
+
+public:
+ CustomDfaEmitter(const UniqueVector<ActionTuple> &Actions, StringRef TypeName)
+ : Actions(Actions), TypeName(TypeName) {}
+
+ void printActionType(raw_ostream &OS) override;
+ void printActionValue(action_type A, raw_ostream &OS) override;
+};
+} // namespace
+
+void AutomatonEmitter::run(raw_ostream &OS) {
+ for (Record *R : Records.getAllDerivedDefinitions("GenericAutomaton")) {
+ Automaton A(Records, R);
+ OS << "#ifdef GET_" << R->getName() << "_DECL\n";
+ A.emit(OS);
+ OS << "#endif // GET_" << R->getName() << "_DECL\n";
+ }
+}
+
+Automaton::Automaton(RecordKeeper &Records, Record *R)
+ : Records(Records), R(R) {
+ LLVM_DEBUG(dbgs() << "Emitting automaton for " << R->getName() << "\n");
+ ActionSymbolFields = R->getValueAsListOfStrings("SymbolFields");
+}
+
+void Automaton::emit(raw_ostream &OS) {
+ StringRef TransitionClass = R->getValueAsString("TransitionClass");
+ for (Record *T : Records.getAllDerivedDefinitions(TransitionClass)) {
+ assert(T->isSubClassOf("Transition"));
+ Transitions.emplace_back(T, this);
+ Actions.insert(Transitions.back().getActions());
+ }
+
+ LLVM_DEBUG(dbgs() << " Action alphabet cardinality: " << Actions.size()
+ << "\n");
+ LLVM_DEBUG(dbgs() << " Each state has " << Transitions.size()
+ << " potential transitions.\n");
+
+ StringRef Name = R->getName();
+
+ CustomDfaEmitter Emitter(Actions, std::string(Name) + "Action");
+ // Starting from the initial state, build up a list of possible states and
+ // transitions.
+ std::deque<uint64_t> Worklist(1, 0);
+ std::set<uint64_t> SeenStates;
+ unsigned NumTransitions = 0;
+ SeenStates.insert(Worklist.front());
+ while (!Worklist.empty()) {
+ uint64_t State = Worklist.front();
+ Worklist.pop_front();
+ for (Transition &T : Transitions) {
+ if (!T.canTransitionFrom(State))
+ continue;
+ uint64_t NewState = T.transitionFrom(State);
+ if (SeenStates.emplace(NewState).second)
+ Worklist.emplace_back(NewState);
+ ++NumTransitions;
+ Emitter.addTransition(State, NewState, Actions.idFor(T.getActions()));
+ }
+ }
+ LLVM_DEBUG(dbgs() << " NFA automaton has " << SeenStates.size()
+ << " states with " << NumTransitions << " transitions.\n");
+
+ const auto &ActionTypes = Transitions.back().getTypes();
+ OS << "// The type of an action in the " << Name << " automaton.\n";
+ if (ActionTypes.size() == 1) {
+ OS << "using " << Name << "Action = " << ActionTypes[0] << ";\n";
+ } else {
+ OS << "using " << Name << "Action = std::tuple<" << join(ActionTypes, ", ")
+ << ">;\n";
+ }
+ OS << "\n";
+
+ Emitter.emit(Name, OS);
+}
+
+StringRef Automaton::getActionSymbolType(StringRef A) {
+ Twine Ty = "TypeOf_" + A;
+ if (!R->getValue(Ty.str()))
+ return "";
+ return R->getValueAsString(Ty.str());
+}
+
+Transition::Transition(Record *R, Automaton *Parent) {
+ BitsInit *NewStateInit = R->getValueAsBitsInit("NewState");
+ NewState = 0;
+ assert(NewStateInit->getNumBits() <= sizeof(uint64_t) * 8 &&
+ "State cannot be represented in 64 bits!");
+ for (unsigned I = 0; I < NewStateInit->getNumBits(); ++I) {
+ if (auto *Bit = dyn_cast<BitInit>(NewStateInit->getBit(I))) {
+ if (Bit->getValue())
+ NewState |= 1ULL << I;
+ }
+ }
+
+ for (StringRef A : Parent->getActionSymbolFields()) {
+ RecordVal *SymbolV = R->getValue(A);
+ if (auto *Ty = dyn_cast<RecordRecTy>(SymbolV->getType())) {
+ Actions.emplace_back(R->getValueAsDef(A), 0, "");
+ Types.emplace_back(Ty->getAsString());
+ } else if (isa<IntRecTy>(SymbolV->getType())) {
+ Actions.emplace_back(nullptr, R->getValueAsInt(A), "");
+ Types.emplace_back("unsigned");
+ } else if (isa<StringRecTy>(SymbolV->getType()) ||
+ isa<CodeRecTy>(SymbolV->getType())) {
+ Actions.emplace_back(nullptr, 0, R->getValueAsString(A));
+ Types.emplace_back("std::string");
+ } else {
+ report_fatal_error("Unhandled symbol type!");
+ }
+
+ StringRef TypeOverride = Parent->getActionSymbolType(A);
+ if (!TypeOverride.empty())
+ Types.back() = TypeOverride;
+ }
+}
+
+bool Transition::canTransitionFrom(uint64_t State) {
+ if ((State & NewState) == 0)
+ // The bits we want to set are not set;
+ return true;
+ return false;
+}
+
+uint64_t Transition::transitionFrom(uint64_t State) {
+ return State | NewState;
+}
+
+void CustomDfaEmitter::printActionType(raw_ostream &OS) { OS << TypeName; }
+
+void CustomDfaEmitter::printActionValue(action_type A, raw_ostream &OS) {
+ const ActionTuple &AT = Actions[A];
+ if (AT.size() > 1)
+ OS << "{";
+ bool First = true;
+ for (const auto &SingleAction : AT) {
+ if (!First)
+ OS << ", ";
+ First = false;
+ SingleAction.print(OS);
+ }
+ if (AT.size() > 1)
+ OS << "}";
+}
+
+namespace llvm {
+
+void EmitAutomata(RecordKeeper &RK, raw_ostream &OS) {
+ AutomatonEmitter(RK).run(OS);
+}
+
+} // namespace llvm
diff --git a/llvm/utils/TableGen/DFAEmitter.h b/llvm/utils/TableGen/DFAEmitter.h
new file mode 100644
index 0000000..76de8f7
--- /dev/null
+++ b/llvm/utils/TableGen/DFAEmitter.h
@@ -0,0 +1,107 @@
+//===--------------------- DfaEmitter.h -----------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Defines a generic automaton builder. This takes a set of transitions and
+// states that represent a nondeterministic finite state automaton (NFA) and
+// emits a determinized DFA in a form that include/llvm/Support/Automaton.h can
+// drive.
+//
+// See file llvm/TableGen/Automaton.td for the TableGen API definition.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_DFAEMITTER_H
+#define LLVM_UTILS_TABLEGEN_DFAEMITTER_H
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/UniqueVector.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/TableGen/Record.h"
+#include <set>
+#include <unordered_map>
+
+namespace llvm {
+
+class raw_ostream;
+/// Construct a deterministic finite state automaton from possible
+/// nondeterministic state and transition data.
+///
+/// The state type is a 64-bit unsigned integer. The generated automaton is
+/// invariant to the sparsity of the state representation - its size is only
+/// a function of the cardinality of the set of states.
+///
+/// The inputs to this emitter are considered to define a nondeterministic
+/// finite state automaton (NFA). This is then converted to a DFA during
+/// emission. The emitted tables can be used to by
+/// include/llvm/Support/Automaton.h.
+class DfaEmitter {
+public:
+ // The type of an NFA state. The initial state is always zero.
+ using state_type = uint64_t;
+ // The type of an action.
+ using action_type = uint64_t;
+
+ DfaEmitter() = default;
+ virtual ~DfaEmitter() = default;
+
+ void addTransition(state_type From, state_type To, action_type A);
+ void emit(StringRef Name, raw_ostream &OS);
+
+protected:
+ /// Emit the C++ type of an action to OS.
+ virtual void printActionType(raw_ostream &OS);
+ /// Emit the C++ value of an action A to OS.
+ virtual void printActionValue(action_type A, raw_ostream &OS);
+
+private:
+ /// The state type of deterministic states. These are only used internally to
+ /// this class. This is an ID into the DfaStates UniqueVector.
+ using dfa_state_type = unsigned;
+
+ /// The actual representation of a DFA state, which is a union of one or more
+ /// NFA states.
+ using DfaState = SmallVector<state_type, 4>;
+
+ /// A DFA transition consists of a set of NFA states transitioning to a
+ /// new set of NFA states. The DfaTransitionInfo tracks, for every
+ /// transitioned-from NFA state, a set of valid transitioned-to states.
+ ///
+ /// Emission of this transition relation allows algorithmic determination of
+ /// the possible candidate NFA paths taken under a given input sequence to
+ /// reach a given DFA state.
+ using DfaTransitionInfo = SmallVector<std::pair<state_type, state_type>, 4>;
+
+ /// The set of all possible actions.
+ std::set<action_type> Actions;
+
+ /// The set of nondeterministic transitions. A state-action pair can
+ /// transition to multiple target states.
+ std::map<std::pair<state_type, action_type>, std::vector<state_type>>
+ NfaTransitions;
+ std::set<state_type> NfaStates;
+ unsigned NumNfaTransitions = 0;
+
+ /// The set of deterministic states. DfaStates.getId(DfaState) returns an ID,
+ /// which is dfa_state_type. Note that because UniqueVector reserves state
+ /// zero, the initial DFA state is always 1.
+ UniqueVector<DfaState> DfaStates;
+ /// The set of deterministic transitions. A state-action pair has only a
+ /// single target state.
+ std::map<std::pair<dfa_state_type, action_type>,
+ std::pair<dfa_state_type, DfaTransitionInfo>>
+ DfaTransitions;
+
+ /// Visit all NFA states and construct the DFA.
+ void constructDfa();
+ /// Visit a single DFA state and construct all possible transitions to new DFA
+ /// states.
+ void visitDfaState(DfaState DS);
+};
+
+} // namespace llvm
+
+#endif
diff --git a/llvm/utils/TableGen/TableGen.cpp b/llvm/utils/TableGen/TableGen.cpp
index 817663b..f730d91 100644
--- a/llvm/utils/TableGen/TableGen.cpp
+++ b/llvm/utils/TableGen/TableGen.cpp
@@ -54,6 +54,7 @@
GenX86FoldTables,
GenRegisterBank,
GenExegesis,
+ GenAutomata,
};
namespace llvm {
@@ -124,7 +125,9 @@
clEnumValN(GenRegisterBank, "gen-register-bank",
"Generate registers bank descriptions"),
clEnumValN(GenExegesis, "gen-exegesis",
- "Generate llvm-exegesis tables")));
+ "Generate llvm-exegesis tables"),
+ clEnumValN(GenAutomata, "gen-automata",
+ "Generate generic automata")));
cl::OptionCategory PrintEnumsCat("Options for -print-enums");
cl::opt<std::string> Class("class", cl::desc("Print Enum list for this class"),
@@ -249,6 +252,9 @@
case GenExegesis:
EmitExegesis(Records, OS);
break;
+ case GenAutomata:
+ EmitAutomata(Records, OS);
+ break;
}
return false;
diff --git a/llvm/utils/TableGen/TableGenBackends.h b/llvm/utils/TableGen/TableGenBackends.h
index 9c21ef3..8c067dd 100644
--- a/llvm/utils/TableGen/TableGenBackends.h
+++ b/llvm/utils/TableGen/TableGenBackends.h
@@ -90,6 +90,7 @@
void EmitX86FoldTables(RecordKeeper &RK, raw_ostream &OS);
void EmitRegisterBank(RecordKeeper &RK, raw_ostream &OS);
void EmitExegesis(RecordKeeper &RK, raw_ostream &OS);
+void EmitAutomata(RecordKeeper &RK, raw_ostream &OS);
} // End llvm namespace