[InstCombine] Signed saturation tests. NFC
[llvm-complete.git] / utils / TableGen / DFAEmitter.h
blob76de8f72cd88e67a0e9c6ec2b29d6ca252f864e0
1 //===--------------------- DfaEmitter.h -----------------------------------===//
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 // Defines a generic automaton builder. This takes a set of transitions and
9 // states that represent a nondeterministic finite state automaton (NFA) and
10 // emits a determinized DFA in a form that include/llvm/Support/Automaton.h can
11 // drive.
13 // See file llvm/TableGen/Automaton.td for the TableGen API definition.
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_UTILS_TABLEGEN_DFAEMITTER_H
18 #define LLVM_UTILS_TABLEGEN_DFAEMITTER_H
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/ADT/UniqueVector.h"
22 #include "llvm/Support/raw_ostream.h"
23 #include "llvm/TableGen/Record.h"
24 #include <set>
25 #include <unordered_map>
27 namespace llvm {
29 class raw_ostream;
30 /// Construct a deterministic finite state automaton from possible
31 /// nondeterministic state and transition data.
32 ///
33 /// The state type is a 64-bit unsigned integer. The generated automaton is
34 /// invariant to the sparsity of the state representation - its size is only
35 /// a function of the cardinality of the set of states.
36 ///
37 /// The inputs to this emitter are considered to define a nondeterministic
38 /// finite state automaton (NFA). This is then converted to a DFA during
39 /// emission. The emitted tables can be used to by
40 /// include/llvm/Support/Automaton.h.
41 class DfaEmitter {
42 public:
43 // The type of an NFA state. The initial state is always zero.
44 using state_type = uint64_t;
45 // The type of an action.
46 using action_type = uint64_t;
48 DfaEmitter() = default;
49 virtual ~DfaEmitter() = default;
51 void addTransition(state_type From, state_type To, action_type A);
52 void emit(StringRef Name, raw_ostream &OS);
54 protected:
55 /// Emit the C++ type of an action to OS.
56 virtual void printActionType(raw_ostream &OS);
57 /// Emit the C++ value of an action A to OS.
58 virtual void printActionValue(action_type A, raw_ostream &OS);
60 private:
61 /// The state type of deterministic states. These are only used internally to
62 /// this class. This is an ID into the DfaStates UniqueVector.
63 using dfa_state_type = unsigned;
65 /// The actual representation of a DFA state, which is a union of one or more
66 /// NFA states.
67 using DfaState = SmallVector<state_type, 4>;
69 /// A DFA transition consists of a set of NFA states transitioning to a
70 /// new set of NFA states. The DfaTransitionInfo tracks, for every
71 /// transitioned-from NFA state, a set of valid transitioned-to states.
72 ///
73 /// Emission of this transition relation allows algorithmic determination of
74 /// the possible candidate NFA paths taken under a given input sequence to
75 /// reach a given DFA state.
76 using DfaTransitionInfo = SmallVector<std::pair<state_type, state_type>, 4>;
78 /// The set of all possible actions.
79 std::set<action_type> Actions;
81 /// The set of nondeterministic transitions. A state-action pair can
82 /// transition to multiple target states.
83 std::map<std::pair<state_type, action_type>, std::vector<state_type>>
84 NfaTransitions;
85 std::set<state_type> NfaStates;
86 unsigned NumNfaTransitions = 0;
88 /// The set of deterministic states. DfaStates.getId(DfaState) returns an ID,
89 /// which is dfa_state_type. Note that because UniqueVector reserves state
90 /// zero, the initial DFA state is always 1.
91 UniqueVector<DfaState> DfaStates;
92 /// The set of deterministic transitions. A state-action pair has only a
93 /// single target state.
94 std::map<std::pair<dfa_state_type, action_type>,
95 std::pair<dfa_state_type, DfaTransitionInfo>>
96 DfaTransitions;
98 /// Visit all NFA states and construct the DFA.
99 void constructDfa();
100 /// Visit a single DFA state and construct all possible transitions to new DFA
101 /// states.
102 void visitDfaState(DfaState DS);
105 } // namespace llvm
107 #endif