diff --git a/llvm/include/llvm/CodeGen/DFAPacketizer.h b/llvm/include/llvm/CodeGen/DFAPacketizer.h
--- a/llvm/include/llvm/CodeGen/DFAPacketizer.h
+++ b/llvm/include/llvm/CodeGen/DFAPacketizer.h
@@ -46,16 +46,18 @@
 class SUnit;
 class TargetInstrInfo;
 
+using DFAPacketizerAutomaton = Automaton<uint64_t, OrderedArrayMap>;
+
 class DFAPacketizer {
 private:
   const InstrItineraryData *InstrItins;
-  Automaton<uint64_t> A;
+  DFAPacketizerAutomaton A;
   /// For every itinerary, an "action" to apply to the automaton. This removes
   /// the redundancy in actions between itinerary classes.
   ArrayRef<unsigned> ItinActions;
 
 public:
-  DFAPacketizer(const InstrItineraryData *InstrItins, Automaton<uint64_t> a,
+  DFAPacketizer(const InstrItineraryData *InstrItins, DFAPacketizerAutomaton a,
                 ArrayRef<unsigned> ItinActions)
       : InstrItins(InstrItins), A(std::move(a)), ItinActions(ItinActions) {
     // Start off with resource tracking disabled.
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,34 +154,109 @@
 };
 } // 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.
+};
+
+template <typename ActionT> class OrderedArrayMap {
+public:
+  using TransitionT = TransitionType<ActionT>;
+  using TransitionKeyT = std::pair<decltype(TransitionT::FromDfaState),
+                                   decltype(TransitionT::Action)>;
+  using TransitionValueT = std::pair<decltype(TransitionT::ToDfaState),
+                                     decltype(TransitionT::InfoIdx)>;
+
+private:
+  ArrayRef<TransitionT> TransitionsArray;
+  static bool transitionLessThan(const TransitionT &A,
+                                 const TransitionKeyT &B) {
+    return std::make_pair(A.FromDfaState, A.Action) < B;
+  }
+
+public:
+  OrderedArrayMap(ArrayRef<TransitionT> OrderedTransitions)
+      : TransitionsArray(OrderedTransitions) {
+    assert(std::is_sorted(OrderedTransitions.begin(), OrderedTransitions.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");
+  }
+
+  Optional<TransitionValueT> find(const TransitionKeyT &K) {
+    auto It = std::lower_bound(TransitionsArray.begin(), TransitionsArray.end(),
+                               K, transitionLessThan);
+    Optional<TransitionValueT> Result = None;
+    if (It != TransitionsArray.end() &&
+        std::make_pair(It->FromDfaState, It->Action) == K)
+      Result = std::make_pair(It->ToDfaState, It->InfoIdx);
+    return Result;
+  }
+};
+
+template <typename ActionT> class TransitionMap {
+  using MapTy =
+      std::map<std::pair<uint64_t, ActionT>, std::pair<uint64_t, unsigned>>;
+  std::shared_ptr<MapTy> M;
+
+public:
+  using TransitionT = TransitionType<ActionT>;
+  using TransitionKeyT = std::pair<decltype(TransitionT::FromDfaState),
+                                   decltype(TransitionT::Action)>;
+  using TransitionValueT = std::pair<decltype(TransitionT::ToDfaState),
+                                     decltype(TransitionT::InfoIdx)>;
+  TransitionMap(ArrayRef<TransitionT> Transitions) {
+    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));
+  }
+
+  Optional<TransitionValueT> find(const TransitionKeyT &K) {
+    auto It = M->find(K);
+    Optional<TransitionValueT> Result = None;
+    if (It != M->end())
+      Result = It->second;
+    return Result;
+  }
+};
+
 /// 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 {
+template <typename ActionT, template <typename ATy> class MapTy = TransitionMap>
+class Automaton {
+  using TransitionMapTy = MapTy<ActionT>;
+  using TransitionT = typename TransitionMapTy::TransitionT;
+  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
-  /// an enum. In particular DenseMapInfo<ActionT> must be defined to use
-  /// 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;
+  TransitionMapTy TransitionsMap;
   /// 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;
 
 public:
   /// Create an automaton.
-  /// \param Transitions The Transitions table as created by TableGen. Note that
-  ///                    because the action type differs per automaton, the
-  ///                    table type is templated as ArrayRef<InfoT>.
+  /// \param TransitionsArray The Transitions table as created by TableGen.
+  ///                     Note that because the action type differs per
+  ///                     automaton, the table type is templated as
+  ///                     ArrayRef<InfoT>.
   /// \param TranscriptionTable The TransitionInfo table as created by TableGen.
   ///
   /// Providing the TranscriptionTable argument as non-empty will enable the
@@ -189,21 +264,17 @@
   /// 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,
-            ArrayRef<NfaStatePair> TranscriptionTable = {}) {
+  Automaton(ArrayRef<TransitionT> TransitionsArray,
+            ArrayRef<NfaStatePair> TranscriptionTable = {})
+      : TransitionsMap(TransitionsArray) {
     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));
   }
   Automaton(const Automaton &Other)
-      : M(Other.M), State(Other.State), Transcribe(Other.Transcribe) {
+      : TransitionsMap(Other.TransitionsMap), 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 +304,19 @@
   /// 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 NextState = TransitionsMap.find({State, A});
+    if (!NextState.hasValue())
       return false;
     if (Transcriber && Transcribe)
-      Transcriber->transition(I->second.second);
-    State = I->second.first;
+      Transcriber->transition(NextState->second);
+    State = NextState->first;
     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 NextState = TransitionsMap.find({State, A});
+    return NextState.hasValue();
   }
 
   /// 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";
diff --git a/llvm/utils/TableGen/DFAPacketizerEmitter.cpp b/llvm/utils/TableGen/DFAPacketizerEmitter.cpp
--- a/llvm/utils/TableGen/DFAPacketizerEmitter.cpp
+++ b/llvm/utils/TableGen/DFAPacketizerEmitter.cpp
@@ -340,9 +340,9 @@
   OS << "DFAPacketizer *" << SubTargetClassName << "::"
      << "create" << DFAName
      << "DFAPacketizer(const InstrItineraryData *IID) const {\n"
-     << "  static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName
-     << "Transition>(" << TargetAndDFAName << "Transitions), "
-     << TargetAndDFAName << "TransitionInfo);\n"
+     << "  static Automaton<uint64_t, OrderedArrayMap> A(ArrayRef<"
+     << TargetAndDFAName << "Transition>(" << TargetAndDFAName
+     << "Transitions), " << TargetAndDFAName << "TransitionInfo);\n"
      << "  unsigned ProcResIdxStart = " << TargetAndDFAName
      << "ProcResourceIndexStart[IID->SchedModel.ProcID];\n"
      << "  unsigned ProcResIdxNum = " << TargetAndDFAName