diff --git a/llvm/include/llvm/Support/Automaton.h b/llvm/include/llvm/Support/Automaton.h
--- a/llvm/include/llvm/Support/Automaton.h
+++ b/llvm/include/llvm/Support/Automaton.h
@@ -154,12 +154,26 @@
 };
 } // namespace internal
 
+// Type representing a transition in the DFA state.
+// The action type can be a custom type.
+template <typename ActionT> struct TransitionType {
+  using StateT = unsigned;
+  StateT FromDfaState; // The transitioned-from DFA state.
+  ActionT Action;      // The input symbol that causes this transition.
+  StateT ToDfaState;   // The transitioned-to DFA state.
+  unsigned InfoIdx;    // Start index into TransitionInfo.
+};
+
 /// A deterministic finite-state automaton. The automaton is defined in
 /// TableGen; this object drives an automaton defined by tblgen-emitted tables.
 ///
 /// An automaton accepts a sequence of input tokens ("actions"). This class is
 /// templated on the type of these actions.
 template <typename ActionT> class Automaton {
+  using TransitionT = TransitionType<ActionT>;
+  using TransitionKeyT = std::pair<decltype(TransitionT::FromDfaState),
+                                   decltype(TransitionT::Action)>;
+  using StateT = typename TransitionT::StateT;
   /// Map from {State, Action} to {NewState, TransitionInfoIdx}.
   /// TransitionInfoIdx is used by the DfaTranscriber to analyze the transition.
   /// FIXME: This uses a std::map because ActionT can be a pair type including
@@ -167,16 +181,20 @@
   /// DenseMap here.
   /// This is a shared_ptr to allow very quick copy-construction of Automata; this
   /// state is immutable after construction so this is safe.
-  using MapTy = std::map<std::pair<uint64_t, ActionT>, std::pair<uint64_t, unsigned>>;
-  std::shared_ptr<MapTy> M;
+  ArrayRef<TransitionT> TransitionMap;
   /// An optional transcription object. This uses much more state than simply
   /// traversing the DFA for acceptance, so is heap allocated.
   std::shared_ptr<internal::NfaTranscriber> Transcriber;
   /// The initial DFA state is 1.
-  uint64_t State = 1;
+  StateT State = 1;
   /// True if we should transcribe and false if not (even if Transcriber is defined).
   bool Transcribe;
 
+  static bool transitionLessThan(const TransitionT &A,
+                                 const TransitionKeyT &B) {
+    return std::make_pair(A.FromDfaState, A.Action) < B;
+  }
+
 public:
   /// Create an automaton.
   /// \param Transitions The Transitions table as created by TableGen. Note that
@@ -189,21 +207,24 @@
   /// NFA taken by the DFA. NOTE: This is substantially more work than simply
   /// driving the DFA, so unless you require the getPaths() method leave this
   /// empty.
-  template <typename InfoT>
-  Automaton(ArrayRef<InfoT> Transitions,
+  Automaton(ArrayRef<TransitionT> Transitions,
             ArrayRef<NfaStatePair> TranscriptionTable = {}) {
     if (!TranscriptionTable.empty())
       Transcriber =
           std::make_shared<internal::NfaTranscriber>(TranscriptionTable);
     Transcribe = Transcriber != nullptr;
-    M = std::make_shared<MapTy>();
-    for (const auto &I : Transitions)
-      // Greedily read and cache the transition table.
-      M->emplace(std::make_pair(I.FromDfaState, I.Action),
-                 std::make_pair(I.ToDfaState, I.InfoIdx));
+    TransitionMap = Transitions;
+    assert(std::is_sorted(TransitionMap.begin(), TransitionMap.end(),
+                          [](const TransitionT &A, const TransitionT &B) {
+                            return std::make_pair(A.FromDfaState, A.Action) <
+                                   std::make_pair(B.FromDfaState, B.Action);
+                          }) &&
+           "The transitions array is expected to be sorted by FromDfaState and "
+           "Action");
   }
   Automaton(const Automaton &Other)
-      : M(Other.M), State(Other.State), Transcribe(Other.Transcribe) {
+      : TransitionMap(Other.TransitionMap), State(Other.State),
+        Transcribe(Other.Transcribe) {
     // Transcriber is not thread-safe, so create a new instance on copy.
     if (Other.Transcriber)
       Transcriber = std::make_shared<internal::NfaTranscriber>(
@@ -233,19 +254,22 @@
   /// If this function returns false, all methods are undefined until reset() is
   /// called.
   bool add(const ActionT &A) {
-    auto I = M->find({State, A});
-    if (I == M->end())
+    auto I = lower_bound(TransitionMap.begin(), TransitionMap.end(),
+                         std::make_pair(State, A), transitionLessThan);
+    if (I == TransitionMap.end() || State != I->FromDfaState || A != I->Action)
       return false;
     if (Transcriber && Transcribe)
-      Transcriber->transition(I->second.second);
-    State = I->second.first;
+      Transcriber->transition(I->InfoIdx);
+    State = I->ToDfaState;
     return true;
   }
 
   /// Return true if the automaton can be transitioned based on input symbol A.
   bool canAdd(const ActionT &A) {
-    auto I = M->find({State, A});
-    return I != M->end();
+    auto I = lower_bound(TransitionMap.begin(), TransitionMap.end(),
+                         std::make_pair(State, A), transitionLessThan);
+    return I != TransitionMap.end() && State == I->FromDfaState &&
+           A == I->Action;
   }
 
   /// Obtain a set of possible paths through the input nondeterministic
diff --git a/llvm/utils/TableGen/DFAEmitter.cpp b/llvm/utils/TableGen/DFAEmitter.cpp
--- a/llvm/utils/TableGen/DFAEmitter.cpp
+++ b/llvm/utils/TableGen/DFAEmitter.cpp
@@ -131,15 +131,9 @@
   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 << "  ";
+  OS << "using " << Name << "Transition = TransitionType<";
   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 << ">;\n\n";
 
   OS << "// A table of DFA transitions, ordered by {FromDfaState, Action}.\n";
   OS << "// The initial state is 1, not zero.\n";