1 //===- MatrixTest.cpp - Tests for QuasiPolynomial -------------------------===//
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 #include "mlir/Analysis/Presburger/QuasiPolynomial.h"
10 #include "./Utils.h"
11 #include "mlir/Analysis/Presburger/Fraction.h"
12 #include <gmock/gmock.h>
13 #include <gtest/gtest.h>
14
15 using namespace mlir;
16 using namespace presburger;
17
18 // Test the arithmetic operations on QuasiPolynomials;
19 // addition, subtraction, multiplication, and division
20 // by a constant.
21 // Two QPs of 3 parameters each were generated randomly
22 // and their sum, difference, and product computed by hand.
TEST(QuasiPolynomialTest,arithmetic)23 TEST(QuasiPolynomialTest, arithmetic) {
24 QuasiPolynomial qp1(
25 3, {Fraction(1, 3), Fraction(1, 1), Fraction(1, 2)},
26 {{{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
27 {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)}},
28 {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)}},
29 {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
30 {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
31 {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4), Fraction(0, 1)}}});
32 QuasiPolynomial qp2(
33 3, {Fraction(1, 1), Fraction(2, 1)},
34 {{{Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
35 {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
36 {{Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1), Fraction(0, 1)}}});
37
38 QuasiPolynomial sum = qp1 + qp2;
39 EXPECT_EQ_REPR_QUASIPOLYNOMIAL(
40 sum,
41 QuasiPolynomial(
42 3,
43 {Fraction(1, 3), Fraction(1, 1), Fraction(1, 2), Fraction(1, 1),
44 Fraction(2, 1)},
45 {{{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
46 {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)}},
47 {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)}},
48 {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
49 {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
50 {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4), Fraction(0, 1)}},
51 {{Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
52 {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
53 {{Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1),
54 Fraction(0, 1)}}}));
55
56 QuasiPolynomial diff = qp1 - qp2;
57 EXPECT_EQ_REPR_QUASIPOLYNOMIAL(
58 diff,
59 QuasiPolynomial(
60 3,
61 {Fraction(1, 3), Fraction(1, 1), Fraction(1, 2), Fraction(-1, 1),
62 Fraction(-2, 1)},
63 {{{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
64 {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)}},
65 {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)}},
66 {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
67 {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
68 {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4), Fraction(0, 1)}},
69 {{Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
70 {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
71 {{Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1),
72 Fraction(0, 1)}}}));
73
74 QuasiPolynomial prod = qp1 * qp2;
75 EXPECT_EQ_REPR_QUASIPOLYNOMIAL(
76 prod,
77 QuasiPolynomial(
78 3,
79 {Fraction(1, 3), Fraction(2, 3), Fraction(1, 1), Fraction(2, 1),
80 Fraction(1, 2), Fraction(1, 1)},
81 {{{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
82 {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)},
83 {Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
84 {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
85 {{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
86 {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)},
87 {Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1), Fraction(0, 1)}},
88 {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)},
89 {Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
90 {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
91 {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)},
92 {Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1), Fraction(0, 1)}},
93 {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
94 {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
95 {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4), Fraction(0, 1)},
96 {Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
97 {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
98 {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
99 {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
100 {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4), Fraction(0, 1)},
101 {Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1),
102 Fraction(0, 1)}}}));
103
104 QuasiPolynomial quot = qp1 / 2;
105 EXPECT_EQ_REPR_QUASIPOLYNOMIAL(
106 quot,
107 QuasiPolynomial(
108 3, {Fraction(1, 6), Fraction(1, 2), Fraction(1, 4)},
109 {{{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
110 {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)}},
111 {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)}},
112 {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
113 {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
114 {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4),
115 Fraction(0, 1)}}}));
116 }
117
118 // Test the simplify() operation on QPs, which removes terms that
119 // are identically zero. A random QP was generated and terms were
120 // changed to account for each condition in simplify() –
121 // the term coefficient being zero, or all the coefficients in some
122 // affine term in the product being zero.
TEST(QuasiPolynomialTest,simplify)123 TEST(QuasiPolynomialTest, simplify) {
124 QuasiPolynomial qp(2,
125 {Fraction(2, 3), Fraction(0, 1), Fraction(1, 1),
126 Fraction(1, 2), Fraction(0, 1)},
127 {{{Fraction(1, 1), Fraction(3, 4), Fraction(5, 3)},
128 {Fraction(2, 1), Fraction(0, 1), Fraction(0, 1)}},
129 {{Fraction(1, 3), Fraction(8, 5), Fraction(2, 5)}},
130 {{Fraction(2, 7), Fraction(9, 5), Fraction(0, 1)},
131 {Fraction(0, 1), Fraction(0, 1), Fraction(0, 1)}},
132 {{Fraction(1, 1), Fraction(4, 5), Fraction(6, 5)}},
133 {{Fraction(1, 3), Fraction(4, 3), Fraction(7, 8)}}});
134 EXPECT_EQ_REPR_QUASIPOLYNOMIAL(
135 qp.simplify(),
136 QuasiPolynomial(2, {Fraction(2, 3), Fraction(1, 2)},
137 {{{Fraction(1, 1), Fraction(3, 4), Fraction(5, 3)},
138 {Fraction(2, 1), Fraction(0, 1), Fraction(0, 1)}},
139 {{Fraction(1, 1), Fraction(4, 5), Fraction(6, 5)}}}));
140 }