3 files changed, 107 insertions, 3 deletions

diff --git a/include/llvm/TableGen/Automaton.td b/include/llvm/TableGen/Automaton.td
new file mode 100644
index 000000000000..13ced2a0e784
--- /dev/null
+++ b/include/llvm/TableGen/Automaton.td
@@ -0,0 +1,95 @@
+//===- Automaton.td ----------------------------------------*- tablegen -*-===//
+//
+// 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 file defines the key top-level classes needed to produce a reasonably
+// generic finite-state automaton.
+//
+//===----------------------------------------------------------------------===//
+
+// Define a record inheriting from GenericAutomaton to generate a reasonably
+// generic finite-state automaton over a set of actions and states.
+//
+// This automaton is defined by:
+//   1) a state space (explicit, always bits<32>).
+//   2) a set of input symbols (actions, explicit) and
+//   3) a transition function from state + action -> state.
+//
+// A theoretical automaton is defined by <Q, S, d, q0, F>:
+//   Q: A set of possible states.
+//   S: (sigma) The input alphabet.
+//   d: (delta) The transition function f(q in Q, s in S) -> q' in Q.
+//   F: The set of final (accepting) states.
+//
+// Because generating all possible states is tedious, we instead define the
+// transition function only and crawl all reachable states starting from the
+// initial state with all inputs under all transitions until termination.
+//
+// We define F = S, that is, all valid states are accepting.
+//
+// To ensure the generation of the automaton terminates, the state transitions
+// are defined as a lattice (meaning every transitioned-to state is more
+// specific than the transitioned-from state, for some definition of specificity).
+// Concretely a transition may set one or more bits in the state that were
+// previously zero to one. If any bit was not zero, the transition is invalid.
+//
+// Instead of defining all possible states (which would be cumbersome), the user
+// provides a set of possible Transitions from state A, consuming an input
+// symbol A to state B. The Transition object transforms state A to state B and
+// acts as a predicate. This means the state space can be discovered by crawling
+// all the possible transitions until none are valid.
+//
+// This automaton is considered to be nondeterministic, meaning that multiple
+// transitions can occur from any (state, action) pair. The generated automaton
+// is determinized, meaning that is executes in O(k) time where k is the input
+// sequence length.
+//
+// In addition to a generated automaton that determines if a sequence of inputs
+// is accepted or not, a table is emitted that allows determining a plausible
+// sequence of states traversed to accept that input.
+class GenericAutomaton {
+  // Name of a class that inherits from Transition. All records inheriting from
+  // this class will be considered when constructing the automaton.
+  string TransitionClass;
+
+  // Names of fields within TransitionClass that define the action symbol. This
+  // defines the action as an N-tuple.
+  //
+  // Each symbol field can be of class, int, string or code type.
+  //   If the type of a field is a class, the Record's name is used verbatim
+  //     in C++ and the class name is used as the C++ type name.
+  //   If the type of a field is a string, code or int, that is also used
+  //     verbatim in C++.
+  //
+  // To override the C++ type name for field F, define a field called TypeOf_F.
+  // This should be a string that will be used verbatim in C++.
+  //
+  // As an example, to define a 2-tuple with an enum and a string, one might:
+  //   def MyTransition : Transition {
+  //     MyEnum S1;
+  //     int S2;
+  //   }
+  //   def MyAutomaton : GenericAutomaton }{
+  //     let TransitionClass = "Transition";
+  //     let SymbolFields = ["S1", "S2"];
+  //     let TypeOf_S1 = "MyEnumInCxxKind";
+  //   }
+  list<string> SymbolFields;
+}
+
+// All transitions inherit from Transition.
+class Transition {
+  // A transition S' = T(S) is valid if, for every set bit in NewState, the
+  // corresponding bit in S is clear. That is:
+  //   def T(S):
+  //     S' = S | NewState
+  //     return S' if S' != S else Failure
+  //
+  // The automaton generator uses this property to crawl the set of possible
+  // transitions from a starting state of 0b0.
+  bits<32> NewState;
+}
diff --git a/include/llvm/TableGen/Error.h b/include/llvm/TableGen/Error.h
index 7c83b6298620..cf990427f577 100644
--- a/include/llvm/TableGen/Error.h
+++ b/include/llvm/TableGen/Error.h
@@ -18,6 +18,7 @@
 
 namespace llvm {
 
+void PrintNote(const Twine &Msg);
 void PrintNote(ArrayRef<SMLoc> NoteLoc, const Twine &Msg);
 
 void PrintWarning(ArrayRef<SMLoc> WarningLoc, const Twine &Msg);
diff --git a/include/llvm/TableGen/Record.h b/include/llvm/TableGen/Record.h
index bf7f02208c28..73ed342a6101 100644
--- a/include/llvm/TableGen/Record.h
+++ b/include/llvm/TableGen/Record.h
@@ -1263,7 +1263,14 @@ class FieldInit : public TypedInit {
 
   FieldInit(Init *R, StringInit *FN)
       : TypedInit(IK_FieldInit, R->getFieldType(FN)), Rec(R), FieldName(FN) {
-    assert(getType() && "FieldInit with non-record type!");
+#ifndef NDEBUG
+    if (!getType()) {
+      llvm::errs() << "In Record = " << Rec->getAsString()
+                   << ", got FieldName = " << *FieldName
+                   << " with non-record type!\n";
+      llvm_unreachable("FieldInit with non-record type!");
+    }
+#endif
   }
 
 public:
@@ -1323,6 +1330,7 @@ public:
   void Profile(FoldingSetNodeID &ID) const;
 
   Init *getOperator() const { return Val; }
+  Record *getOperatorAsDef(ArrayRef<SMLoc> Loc) const;
 
   StringInit *getName() const { return ValName; }
 
@@ -1680,10 +1688,10 @@ raw_ostream &operator<<(raw_ostream &OS, const Record &R);
 
 class RecordKeeper {
   friend class RecordRecTy;
-  using RecordMap = std::map<std::string, std::unique_ptr<Record>>;
+  using RecordMap = std::map<std::string, std::unique_ptr<Record>, std::less<>>;
   RecordMap Classes, Defs;
   FoldingSet<RecordRecTy> RecordTypePool;
-  std::map<std::string, Init *> ExtraGlobals;
+  std::map<std::string, Init *, std::less<>> ExtraGlobals;
   unsigned AnonCounter = 0;
 
 public: