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
15using namespace mlir;
16using 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.
23TEST(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 a: sum,
41 b: 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 a: diff,
59 b: 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 a: prod,
77 b: 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 a: quot,
107 b: 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.
123TEST(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 a: qp.simplify(),
136 b: 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}

source code of mlir/unittests/Analysis/Presburger/QuasiPolynomialTest.cpp