[TableGen] Introduce a generic automaton (DFA) backend
Summary:
This patch introduces -gen-automata, a backend for generating deterministic finite-state automata.
DFAs are already generated by the -gen-dfa-packetizer backend. This backend is more generic and will
hopefully be used to implement the DFA generation (and determinization) for the packetizer in the
future.
This backend allows not only generation of a DFA from an NFA (nondeterministic finite-state
automaton), it also emits sidetables that allow a path through the DFA under a sequence of inputs to
be analyzed, and the equivalent set of all possible NFA transitions extracted.
This allows a user to not just answer "can my problem be solved?" but also "what is the
solution?". Clearly this analysis is more expensive than just playing a DFA forwards so is
opt-in. The DFAPacketizer has this behaviour already but this is a more compact and generic
representation.
Examples are bundled in unittests/TableGen/Automata.td. Some are trivial, but the BinPacking example
is a stripped-down version of the original target problem I set out to solve, where we pack values
(actually immediates) into bins (an immediate pool in a VLIW bundle) subject to a set of esoteric
constraints.
Reviewers: t.p.northover
Subscribers: mgorny, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D67968
llvm-svn: 373718
diff --git a/llvm/unittests/TableGen/AutomataTest.cpp b/llvm/unittests/TableGen/AutomataTest.cpp
new file mode 100644
index 0000000..11c0342
--- /dev/null
+++ b/llvm/unittests/TableGen/AutomataTest.cpp
@@ -0,0 +1,153 @@
+//===- unittest/TableGen/AutomataTest.cpp - DFA tests ---------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Automaton.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using testing::ContainerEq;
+using testing::UnorderedElementsAre;
+
+// Bring in the enums created by SearchableTables.td.
+#define GET_SymKind_DECL
+#define GET_BinRequirementKindEnum_DECL
+#include "AutomataTables.inc"
+
+// And bring in the automata from Automata.td.
+#define GET_SimpleAutomaton_DECL
+#define GET_TupleAutomaton_DECL
+#define GET_NfaAutomaton_DECL
+#define GET_BinPackerAutomaton_DECL
+#include "AutomataAutomata.inc"
+
+TEST(Automata, SimpleAutomatonAcceptsFromInitialState) {
+ Automaton<SymKind> A(makeArrayRef(SimpleAutomatonTransitions));
+ EXPECT_TRUE(A.add(SK_a));
+ A.reset();
+ EXPECT_TRUE(A.add(SK_b));
+ A.reset();
+ EXPECT_TRUE(A.add(SK_c));
+ A.reset();
+ EXPECT_FALSE(A.add(SK_d));
+}
+
+TEST(Automata, SimpleAutomatonAcceptsSequences) {
+ Automaton<SymKind> A(makeArrayRef(SimpleAutomatonTransitions));
+ // Test sequence <a b>
+ A.reset();
+ EXPECT_TRUE(A.add(SK_a));
+ EXPECT_TRUE(A.add(SK_b));
+
+ // Test sequence <a c> is rejected (c cannot get bit 0b10);
+ A.reset();
+ EXPECT_TRUE(A.add(SK_a));
+ EXPECT_FALSE(A.add(SK_c));
+
+ // Symmetric test: sequence <c a> is rejected.
+ A.reset();
+ EXPECT_TRUE(A.add(SK_c));
+ EXPECT_FALSE(A.add(SK_a));
+}
+
+TEST(Automata, TupleAutomatonAccepts) {
+ Automaton<TupleAutomatonAction> A(makeArrayRef(TupleAutomatonTransitions));
+ A.reset();
+ EXPECT_TRUE(
+ A.add({SK_a, SK_b, "yeet"}));
+ A.reset();
+ EXPECT_FALSE(
+ A.add({SK_a, SK_a, "yeet"}));
+ A.reset();
+ EXPECT_FALSE(
+ A.add({SK_a, SK_b, "feet"}));
+ A.reset();
+ EXPECT_TRUE(
+ A.add({SK_b, SK_b, "foo"}));
+}
+
+TEST(Automata, NfaAutomatonAccepts) {
+ Automaton<SymKind> A(makeArrayRef(NfaAutomatonTransitions));
+
+ // Test sequences <a a>, <a b>, <b a>, <b b>. All should be accepted.
+ A.reset();
+ EXPECT_TRUE(A.add(SK_a));
+ EXPECT_TRUE(A.add(SK_a));
+ A.reset();
+ EXPECT_TRUE(A.add(SK_a));
+ EXPECT_TRUE(A.add(SK_b));
+ A.reset();
+ EXPECT_TRUE(A.add(SK_b));
+ EXPECT_TRUE(A.add(SK_a));
+ A.reset();
+ EXPECT_TRUE(A.add(SK_b));
+ EXPECT_TRUE(A.add(SK_b));
+
+ // Expect that <b b b> is not accepted.
+ A.reset();
+ EXPECT_TRUE(A.add(SK_b));
+ EXPECT_TRUE(A.add(SK_b));
+ EXPECT_FALSE(A.add(SK_b));
+}
+
+TEST(Automata, BinPackerAutomatonAccepts) {
+ Automaton<BinPackerAutomatonAction> A(makeArrayRef(BinPackerAutomatonTransitions));
+
+ // Expect that we can pack two double-bins in 0-4, then no more in 0-4.
+ A.reset();
+ EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
+ EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
+ EXPECT_FALSE(A.add(BRK_0_to_4));
+
+ // Expect that we can pack two double-bins in 0-4, two more in 0-6 then no
+ // more.
+ A.reset();
+ EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
+ EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
+ EXPECT_TRUE(A.add(BRK_0_to_6));
+ EXPECT_TRUE(A.add(BRK_0_to_6));
+ EXPECT_FALSE(A.add(BRK_0_to_6));
+
+ // Expect that we can pack BRK_0_to_6 five times to occupy five bins, then
+ // cannot allocate any double-bins.
+ A.reset();
+ for (unsigned I = 0; I < 5; ++I)
+ EXPECT_TRUE(A.add(BRK_0_to_6));
+ EXPECT_FALSE(A.add(BRK_0_to_6_dbl));
+}
+
+// The state we defined in TableGen uses the least significant 6 bits to represent a bin state.
+#define BINS(a, b, c, d, e, f) \
+ ((a << 5) | (b << 4) | (c << 3) | (d << 2) | (e << 1) | (f << 0))
+
+TEST(Automata, BinPackerAutomatonExplains) {
+ Automaton<BinPackerAutomatonAction> A(makeArrayRef(BinPackerAutomatonTransitions),
+ makeArrayRef(BinPackerAutomatonTransitionInfo));
+ // Pack two double-bins in 0-4, then a single bin in 0-6.
+ EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
+ EXPECT_TRUE(A.add(BRK_0_to_4_dbl));
+ EXPECT_TRUE(A.add(BRK_0_to_6));
+ EXPECT_THAT(
+ A.getNfaPaths(),
+ UnorderedElementsAre(
+ // Allocate {0,1} first, then 6.
+ ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1),
+ BINS(1, 0, 1, 1, 1, 1)}),
+ // Allocate {0,1} first, then 5.
+ ContainerEq(NfaPath{BINS(0, 0, 0, 0, 1, 1), BINS(0, 0, 1, 1, 1, 1),
+ BINS(0, 1, 1, 1, 1, 1)}),
+ // Allocate {2,3} first, then 6.
+ ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1),
+ BINS(1, 0, 1, 1, 1, 1)}),
+ // Allocate {2,3} first, then 5.
+ ContainerEq(NfaPath{BINS(0, 0, 1, 1, 0, 0), BINS(0, 0, 1, 1, 1, 1),
+ BINS(0, 1, 1, 1, 1, 1)})));
+}