diff options
Diffstat (limited to 'llvm/unittests/TableGen/AutomataTest.cpp')
| -rw-r--r-- | llvm/unittests/TableGen/AutomataTest.cpp | 153 |
1 files changed, 153 insertions, 0 deletions
diff --git a/llvm/unittests/TableGen/AutomataTest.cpp b/llvm/unittests/TableGen/AutomataTest.cpp new file mode 100644 index 00000000000..11c03426fd8 --- /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)}))); +} |
