1 //===- AffineStructuresParserTest.cpp - FAC parsing unit tests --*- C++ -*-===//
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 contains tests for parsing IntegerSets to IntegerPolyhedron.
10 // The tests with invalid input check that the parser only accepts well-formed
11 // IntegerSets. The tests with well-formed input compare the returned FACs to
12 // manually constructed FACs with a PresburgerSet equality check.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "./AffineStructuresParser.h"
17 #include "mlir/Analysis/Presburger/PresburgerRelation.h"
18
19 #include <gtest/gtest.h>
20
21 using namespace mlir;
22 using namespace presburger;
23
24 /// Construct a IntegerPolyhedron from a set of inequality, equality, and
25 /// division onstraints.
makeFACFromConstraints(unsigned dims,unsigned syms,ArrayRef<SmallVector<int64_t,4>> ineqs,ArrayRef<SmallVector<int64_t,4>> eqs={},ArrayRef<std::pair<SmallVector<int64_t,4>,int64_t>> divs={})26 static IntegerPolyhedron makeFACFromConstraints(
27 unsigned dims, unsigned syms, ArrayRef<SmallVector<int64_t, 4>> ineqs,
28 ArrayRef<SmallVector<int64_t, 4>> eqs = {},
29 ArrayRef<std::pair<SmallVector<int64_t, 4>, int64_t>> divs = {}) {
30 IntegerPolyhedron fac(ineqs.size(), eqs.size(), dims + syms + 1,
31 PresburgerSpace::getSetSpace(dims, syms, 0));
32 for (const auto &div : divs)
33 fac.addLocalFloorDiv(div.first, div.second);
34 for (const auto &eq : eqs)
35 fac.addEquality(eq);
36 for (const auto &ineq : ineqs)
37 fac.addInequality(ineq);
38 return fac;
39 }
40
TEST(ParseFACTest,InvalidInputTest)41 TEST(ParseFACTest, InvalidInputTest) {
42 MLIRContext context;
43 FailureOr<IntegerPolyhedron> fac;
44
45 fac = parseIntegerSetToFAC("(x)", &context, false);
46 EXPECT_TRUE(failed(fac))
47 << "should not accept strings with no constraint list";
48
49 fac = parseIntegerSetToFAC("(x)[] : ())", &context, false);
50 EXPECT_TRUE(failed(fac))
51 << "should not accept strings that contain remaining characters";
52
53 fac = parseIntegerSetToFAC("(x)[] : (x - >= 0)", &context, false);
54 EXPECT_TRUE(failed(fac))
55 << "should not accept strings that contain incomplete constraints";
56
57 fac = parseIntegerSetToFAC("(x)[] : (y == 0)", &context, false);
58 EXPECT_TRUE(failed(fac))
59 << "should not accept strings that contain unkown identifiers";
60
61 fac = parseIntegerSetToFAC("(x, x) : (2 * x >= 0)", &context, false);
62 EXPECT_TRUE(failed(fac))
63 << "should not accept strings that contain repeated identifier names";
64
65 fac = parseIntegerSetToFAC("(x)[x] : (2 * x >= 0)", &context, false);
66 EXPECT_TRUE(failed(fac))
67 << "should not accept strings that contain repeated identifier names";
68
69 fac = parseIntegerSetToFAC("(x) : (2 * x + 9223372036854775808 >= 0)",
70 &context, false);
71 EXPECT_TRUE(failed(fac)) << "should not accept strings with integer literals "
72 "that do not fit into int64_t";
73 }
74
75 /// Parses and compares the `str` to the `ex`. The equality check is performed
76 /// by using PresburgerSet::isEqual
parseAndCompare(StringRef str,const IntegerPolyhedron & ex,MLIRContext * context)77 static bool parseAndCompare(StringRef str, const IntegerPolyhedron &ex,
78 MLIRContext *context) {
79 FailureOr<IntegerPolyhedron> fac = parseIntegerSetToFAC(str, context);
80
81 EXPECT_TRUE(succeeded(fac));
82
83 return PresburgerSet(*fac).isEqual(PresburgerSet(ex));
84 }
85
TEST(ParseFACTest,ParseAndCompareTest)86 TEST(ParseFACTest, ParseAndCompareTest) {
87 MLIRContext context;
88 // simple ineq
89 EXPECT_TRUE(parseAndCompare(
90 "(x)[] : (x >= 0)", makeFACFromConstraints(1, 0, {{1, 0}}), &context));
91
92 // simple eq
93 EXPECT_TRUE(parseAndCompare("(x)[] : (x == 0)",
94 makeFACFromConstraints(1, 0, {}, {{1, 0}}),
95 &context));
96
97 // multiple constraints
98 EXPECT_TRUE(parseAndCompare("(x)[] : (7 * x >= 0, -7 * x + 5 >= 0)",
99 makeFACFromConstraints(1, 0, {{7, 0}, {-7, 5}}),
100 &context));
101
102 // multiple dimensions
103 EXPECT_TRUE(parseAndCompare("(x,y,z)[] : (x + y - z >= 0)",
104 makeFACFromConstraints(3, 0, {{1, 1, -1, 0}}),
105 &context));
106
107 // dimensions and symbols
108 EXPECT_TRUE(parseAndCompare(
109 "(x,y,z)[a,b] : (x + y - z + 2 * a - 15 * b >= 0)",
110 makeFACFromConstraints(3, 2, {{1, 1, -1, 2, -15, 0}}), &context));
111
112 // only symbols
113 EXPECT_TRUE(parseAndCompare("()[a] : (2 * a - 4 == 0)",
114 makeFACFromConstraints(0, 1, {}, {{2, -4}}),
115 &context));
116
117 // simple floordiv
118 EXPECT_TRUE(parseAndCompare(
119 "(x, y) : (y - 3 * ((x + y - 13) floordiv 3) - 42 == 0)",
120 makeFACFromConstraints(2, 0, {}, {{0, 1, -3, -42}}, {{{1, 1, -13}, 3}}),
121 &context));
122
123 // multiple floordiv
124 EXPECT_TRUE(parseAndCompare(
125 "(x, y) : (y - x floordiv 3 - y floordiv 2 == 0)",
126 makeFACFromConstraints(2, 0, {}, {{0, 1, -1, -1, 0}},
127 {{{1, 0, 0}, 3}, {{0, 1, 0, 0}, 2}}),
128 &context));
129
130 // nested floordiv
131 EXPECT_TRUE(parseAndCompare(
132 "(x, y) : (y - (x + y floordiv 2) floordiv 3 == 0)",
133 makeFACFromConstraints(2, 0, {}, {{0, 1, 0, -1, 0}},
134 {{{0, 1, 0}, 2}, {{1, 0, 1, 0}, 3}}),
135 &context));
136 }
137