LLVM  10.0.0svn
Automaton.h
Go to the documentation of this file.
1 //===-- Automaton.h - Support for driving TableGen-produced DFAs ----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements class that drive and introspect deterministic finite-
10 // state automata (DFAs) as generated by TableGen's -gen-automata backend.
11 //
12 // For a description of how to define an automaton, see
13 // include/llvm/TableGen/Automaton.td.
14 //
15 // One important detail is that these deterministic automata are created from
16 // (potentially) nondeterministic definitions. Therefore a unique sequence of
17 // input symbols will produce one path through the DFA but multiple paths
18 // through the original NFA. An automaton by default only returns "accepted" or
19 // "not accepted", but frequently we want to analyze what NFA path was taken.
20 // Finding a path through the NFA states that results in a DFA state can help
21 // answer *what* the solution to a problem was, not just that there exists a
22 // solution.
23 //
24 //===----------------------------------------------------------------------===//
25 
26 #ifndef LLVM_SUPPORT_AUTOMATON_H
27 #define LLVM_SUPPORT_AUTOMATON_H
28 
29 #include "llvm/ADT/ArrayRef.h"
30 #include "llvm/ADT/DenseMap.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/Support/Allocator.h"
33 #include <deque>
34 #include <map>
35 #include <memory>
36 #include <unordered_map>
37 #include <vector>
38 
39 namespace llvm {
40 
42 
43 /// Forward define the pair type used by the automata transition info tables.
44 ///
45 /// Experimental results with large tables have shown a significant (multiple
46 /// orders of magnitude) parsing speedup by using a custom struct here with a
47 /// trivial constructor rather than std::pair<uint64_t, uint64_t>.
48 struct NfaStatePair {
50 
51  bool operator<(const NfaStatePair &Other) const {
52  return std::make_tuple(FromDfaState, ToDfaState) <
53  std::make_tuple(Other.FromDfaState, Other.ToDfaState);
54  }
55 };
56 
57 namespace internal {
58 /// The internal class that maintains all possible paths through an NFA based
59 /// on a path through the DFA.
61 private:
62  /// Cached transition table. This is a table of NfaStatePairs that contains
63  /// zero-terminated sequences pointed to by DFA transitions.
64  ArrayRef<NfaStatePair> TransitionInfo;
65 
66  /// A simple linked-list of traversed states that can have a shared tail. The
67  /// traversed path is stored in reverse order with the latest state as the
68  /// head.
69  struct PathSegment {
70  uint64_t State;
71  PathSegment *Tail;
72  };
73 
74  /// We allocate segment objects frequently. Allocate them upfront and dispose
75  /// at the end of a traversal rather than hammering the system allocator.
77 
78  /// Heads of each tracked path. These are not ordered.
79  std::deque<PathSegment *> Heads;
80 
81  /// The returned paths. This is populated during getPaths.
83 
84  /// Create a new segment and return it.
85  PathSegment *makePathSegment(uint64_t State, PathSegment *Tail) {
86  PathSegment *P = Allocator.Allocate();
87  *P = {State, Tail};
88  return P;
89  }
90 
91  /// Pairs defines a sequence of possible NFA transitions for a single DFA
92  /// transition.
93  void transition(ArrayRef<NfaStatePair> Pairs) {
94  // Iterate over all existing heads. We will mutate the Heads deque during
95  // iteration.
96  unsigned NumHeads = Heads.size();
97  for (unsigned I = 0; I < NumHeads; ++I) {
98  PathSegment *Head = Heads[I];
99  // The sequence of pairs is sorted. Select the set of pairs that
100  // transition from the current head state.
101  auto PI = lower_bound(Pairs, NfaStatePair{Head->State, 0ULL});
102  auto PE = upper_bound(Pairs, NfaStatePair{Head->State, INT64_MAX});
103  // For every transition from the current head state, add a new path
104  // segment.
105  for (; PI != PE; ++PI)
106  if (PI->FromDfaState == Head->State)
107  Heads.push_back(makePathSegment(PI->ToDfaState, Head));
108  }
109  // Now we've iterated over all the initial heads and added new ones,
110  // dispose of the original heads.
111  Heads.erase(Heads.begin(), std::next(Heads.begin(), NumHeads));
112  }
113 
114 public:
116  : TransitionInfo(TransitionInfo) {
117  reset();
118  }
119 
120  void reset() {
121  Paths.clear();
122  Heads.clear();
123  Allocator.DestroyAll();
124  // The initial NFA state is 0.
125  Heads.push_back(makePathSegment(0ULL, nullptr));
126  }
127 
128  void transition(unsigned TransitionInfoIdx) {
129  unsigned EndIdx = TransitionInfoIdx;
130  while (TransitionInfo[EndIdx].ToDfaState != 0)
131  ++EndIdx;
132  ArrayRef<NfaStatePair> Pairs(&TransitionInfo[TransitionInfoIdx],
133  EndIdx - TransitionInfoIdx);
134  transition(Pairs);
135  }
136 
138  Paths.clear();
139  for (auto *Head : Heads) {
140  NfaPath P;
141  while (Head->State != 0) {
142  P.push_back(Head->State);
143  Head = Head->Tail;
144  }
145  std::reverse(P.begin(), P.end());
146  Paths.push_back(std::move(P));
147  }
148  return Paths;
149  }
150 };
151 } // namespace internal
152 
153 /// A deterministic finite-state automaton. The automaton is defined in
154 /// TableGen; this object drives an automaton defined by tblgen-emitted tables.
155 ///
156 /// An automaton accepts a sequence of input tokens ("actions"). This class is
157 /// templated on the type of these actions.
158 template <typename ActionT> class Automaton {
159  /// Map from {State, Action} to {NewState, TransitionInfoIdx}.
160  /// TransitionInfoIdx is used by the DfaTranscriber to analyze the transition.
161  /// FIXME: This uses a std::map because ActionT can be a pair type including
162  /// an enum. In particular DenseMapInfo<ActionT> must be defined to use
163  /// DenseMap here.
164  /// This is a shared_ptr to allow very quick copy-construction of Automata; this
165  /// state is immutable after construction so this is safe.
166  using MapTy = std::map<std::pair<uint64_t, ActionT>, std::pair<uint64_t, unsigned>>;
167  std::shared_ptr<MapTy> M;
168  /// An optional transcription object. This uses much more state than simply
169  /// traversing the DFA for acceptance, so is heap allocated.
170  std::shared_ptr<internal::NfaTranscriber> Transcriber;
171  /// The initial DFA state is 1.
172  uint64_t State = 1;
173  /// True if we should transcribe and false if not (even if Transcriber is defined).
174  bool Transcribe;
175 
176 public:
177  /// Create an automaton.
178  /// \param Transitions The Transitions table as created by TableGen. Note that
179  /// because the action type differs per automaton, the
180  /// table type is templated as ArrayRef<InfoT>.
181  /// \param TranscriptionTable The TransitionInfo table as created by TableGen.
182  ///
183  /// Providing the TranscriptionTable argument as non-empty will enable the
184  /// use of transcription, which analyzes the possible paths in the original
185  /// NFA taken by the DFA. NOTE: This is substantially more work than simply
186  /// driving the DFA, so unless you require the getPaths() method leave this
187  /// empty.
188  template <typename InfoT>
190  ArrayRef<NfaStatePair> TranscriptionTable = {}) {
191  if (!TranscriptionTable.empty())
192  Transcriber =
193  std::make_shared<internal::NfaTranscriber>(TranscriptionTable);
194  Transcribe = Transcriber != nullptr;
195  M = std::make_shared<MapTy>();
196  for (const auto &I : Transitions)
197  // Greedily read and cache the transition table.
198  M->emplace(std::make_pair(I.FromDfaState, I.Action),
199  std::make_pair(I.ToDfaState, I.InfoIdx));
200  }
201  Automaton(const Automaton &) = default;
202 
203  /// Reset the automaton to its initial state.
204  void reset() {
205  State = 1;
206  if (Transcriber)
207  Transcriber->reset();
208  }
209 
210  /// Enable or disable transcription. Transcription is only available if
211  /// TranscriptionTable was provided to the constructor.
212  void enableTranscription(bool Enable = true) {
213  assert(Transcriber &&
214  "Transcription is only available if TranscriptionTable was provided "
215  "to the Automaton constructor");
216  Transcribe = Enable;
217  }
218 
219  /// Transition the automaton based on input symbol A. Return true if the
220  /// automaton transitioned to a valid state, false if the automaton
221  /// transitioned to an invalid state.
222  ///
223  /// If this function returns false, all methods are undefined until reset() is
224  /// called.
225  bool add(const ActionT &A) {
226  auto I = M->find({State, A});
227  if (I == M->end())
228  return false;
229  if (Transcriber && Transcribe)
230  Transcriber->transition(I->second.second);
231  State = I->second.first;
232  return true;
233  }
234 
235  /// Return true if the automaton can be transitioned based on input symbol A.
236  bool canAdd(const ActionT &A) {
237  auto I = M->find({State, A});
238  return I != M->end();
239  }
240 
241  /// Obtain a set of possible paths through the input nondeterministic
242  /// automaton that could be obtained from the sequence of input actions
243  /// presented to this deterministic automaton.
245  assert(Transcriber && Transcribe &&
246  "Can only obtain NFA paths if transcribing!");
247  return Transcriber->getPaths();
248  }
249 };
250 
251 } // namespace llvm
252 
253 #endif // LLVM_SUPPORT_AUTOMATON_H
auto lower_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1261
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Automaton(ArrayRef< InfoT > Transitions, ArrayRef< NfaStatePair > TranscriptionTable={})
Create an automaton.
Definition: Automaton.h:189
void enableTranscription(bool Enable=true)
Enable or disable transcription.
Definition: Automaton.h:212
void push_back(const T &Elt)
Definition: SmallVector.h:211
bool operator<(const NfaStatePair &Other) const
Definition: Automaton.h:51
The internal class that maintains all possible paths through an NFA based on a path through the DFA...
Definition: Automaton.h:60
ArrayRef< NfaPath > getPaths()
Definition: Automaton.h:137
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
#define INT64_MAX
Definition: DataTypes.h:77
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:261
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
void DestroyAll()
Call the destructor of each allocated object and deallocate all but the current slab and reset the cu...
Definition: Allocator.h:467
bool add(const ActionT &A)
Transition the automaton based on input symbol A.
Definition: Automaton.h:225
#define P(N)
void reset()
Reset the automaton to its initial state.
Definition: Automaton.h:204
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
Definition: Allocator.h:496
Forward define the pair type used by the automata transition info tables.
Definition: Automaton.h:48
Basic Register Allocator
uint64_t ToDfaState
Definition: Automaton.h:49
ArrayRef< NfaPath > getNfaPaths()
Obtain a set of possible paths through the input nondeterministic automaton that could be obtained fr...
Definition: Automaton.h:244
bool canAdd(const ActionT &A)
Return true if the automaton can be transitioned based on input symbol A.
Definition: Automaton.h:236
#define I(x, y, z)
Definition: MD5.cpp:58
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void transition(unsigned TransitionInfoIdx)
Definition: Automaton.h:128
uint64_t FromDfaState
Definition: Automaton.h:49
A deterministic finite-state automaton.
Definition: Automaton.h:158
NfaTranscriber(ArrayRef< NfaStatePair > TransitionInfo)
Definition: Automaton.h:115
auto upper_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range))
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1276