Reapply Avoid creating an immutable map in the Automaton class.

[kariddi]

Summary

In the DFAPacketizer we copy the Transitions array
into a map in order to later access the transitions
based on a "Current State/Action" pair as a key.
This map lives in the Automaton object used by the DFAPacketizer.
It is never changed during the life of the object after
having been created during the creation of the Automaton
itself.

This map creation can make the creation of a DFAPacketizer
quite expensive if the target contains a considerable
amount of transition states.
This patch avoids creating the new map by using the TableGen
generated array as the map based on the assumption that this
array is already sorted in the DFAPacketizer by State/Action
pairs (the key of the map) and we can perform cheap log(N)
searches using std::lower_bound() directly on this array.

The previous patch in 051d330314cb1f175025ca37da8e5e1d851e1790
used this approach for every possible user of the Automaton.
In this patch this approach is used only in the DFAPacketizer.
The problem was that, because the Action object can be customized,
there could be cases where the relative order of the actions
is different between the time TableGen generates the transitions
array and the time the Automaton is instantiated if a customized
action type is used.

An example is the "BinPackerAutomatonAccepts" that asserted on
an assert() added on the previous commit.
In this test the "BinRequirementKindEnum" is generated through
the "Searchable Tables" infrastructure.
When the transitions array is generated every element of the enum
is assigned a temporary value and the transitions array is ordered
based on that value. In the transition array the enum is left with
its textual name and not the underlying value (like BRK_0_to_4,
BRK_0_to_6, ... etc in this case).
The C++ code that is included by users of the enum is generated
subsequently by the "Searchable Tables" infrastructure and is at this
point that each element of the enum have their actual numerical value
assigned. With this new assignment the relative order between enum elements
could be different from the one temporarily determined during the transitions
array generation, causing the array to be effectively unordered now and
to fix that is necessary to actually create the map and we can't
perform the optimization.

[kariddi]

Fixing typo that made everything useless :P

[jmolloy]

llvm/include/llvm/Support/Automaton.h

238

Does this compile? I'm confused by the syntax here.

[kariddi]

llvm/include/llvm/Support/Automaton.h

238

Yeah, it compiles, we are passing the the map type as a template parameter (so if they user knows is not doing anything fancy with custom actions can use the one that just uses the ordered array in the background), but the map type is a templated type on the action type.

I chose to pass a template here instead of a class because if we passed a class the instantiation would have looked something like:

Automaton<uint64_t, OrderedArrayMap<uint64_t> A;

Duplicating the information about the action type in the instantiation (passed both to the automaton and the map), with this syntax we can do:

Automaton<uint64_t, OrderedArrayMap> A;

Another way I was thinking I could have done is pass the action type through the map and then just do:

Automaton<OrderedArrayMap<uint64_t>> A;

but the action type seems something that pertains the Automaton more than the map, so I liked more the first version.

[kariddi]

ping

[kariddi]

ping2 :)

llvm/include/llvm/CodeGen/DFAPacketizer.h

 class InstrItineraryData;
 class MachineFunction;
 class MachineInstr;
 class MachineLoopInfo;
 class MCInstrDesc;
 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.
     A.enableTranscription(false);
   }
 
   // Reset the current state to make all resources available.
   void clearResources() {

llvm/include/llvm/Support/Automaton.h

for (auto *Head : Heads) {
       std::reverse(P.begin(), P.end());
       Paths.push_back(std::move(P));
     }
     return Paths;
   }
 };
 } // 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
   /// use of transcription, which analyzes the possible paths in the original
   /// 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>(
           Other.Transcriber->getTransitionInfo());
   }
 
   /// Reset the automaton to its initial state.
   void reset() {
public:
 
   /// Transition the automaton based on input symbol A. Return true if the
   /// automaton transitioned to a valid state, false if the automaton
   /// transitioned to an invalid state.
   ///
   /// 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
   /// automaton that could be obtained from the sequence of input actions
   /// presented to this deterministic automaton.
   ArrayRef<NfaPath> getNfaPaths() {
     assert(Transcriber && Transcribe &&
            "Can only obtain NFA paths if transcribing!");
     return Transcriber->getPaths();
   }
 };
 
 } // namespace llvm
 
 #endif // LLVM_SUPPORT_AUTOMATON_H

llvm/utils/TableGen/DFAEmitter.cpp

Table.emit(
       [](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 << "  ";
+  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";
   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;

llvm/utils/TableGen/DFAPacketizerEmitter.cpp

void DFAPacketizerEmitter::emitForItineraries(
   Emitter.emit(TargetAndDFAName, OS);
   OS << "} // end anonymous namespace\n\n";
 
   std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
   OS << "namespace llvm {\n";
   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
      << "ProcResourceIndexStart[IID->SchedModel.ProcID + 1] - "
         "ProcResIdxStart;\n"
      << "  return new DFAPacketizer(IID, A, {&" << TargetAndDFAName
      << "ResourceIndices[ProcResIdxStart], ProcResIdxNum});\n"
      << "\n}\n\n";