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