1 //===- MPIntTest.cpp - Tests for MPInt ------------------------------------===//
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/MPInt.h"
10 #include "mlir/Analysis/Presburger/SlowMPInt.h"
11 #include <gmock/gmock.h>
12 #include <gtest/gtest.h>
13 
14 using namespace mlir;
15 using namespace presburger;
16 
17 // googletest boilerplate to run the same tests with both MPInt and SlowMPInt.
18 template <typename>
19 class IntTest : public testing::Test {};
20 using TypeList = testing::Types<MPInt, detail::SlowMPInt>;
21 // This is for pretty-printing the test name with the name of the class in use.
22 class TypeNames {
23 public:
24   template <typename T>
GetName(int)25   static std::string GetName(int) { // NOLINT; gtest mandates this name.
26     if (std::is_same<T, MPInt>())
27       return "MPInt";
28     if (std::is_same<T, detail::SlowMPInt>())
29       return "SlowMPInt";
30     llvm_unreachable("Unknown class!");
31   }
32 };
33 TYPED_TEST_SUITE(IntTest, TypeList, TypeNames);
34 
TYPED_TEST(IntTest,ops)35 TYPED_TEST(IntTest, ops) {
36   TypeParam two(2), five(5), seven(7), ten(10);
37   EXPECT_EQ(five + five, ten);
38   EXPECT_EQ(five * five, 2 * ten + five);
39   EXPECT_EQ(five * five, 3 * ten - five);
40   EXPECT_EQ(five * two, ten);
41   EXPECT_EQ(five / two, two);
42   EXPECT_EQ(five % two, two / two);
43 
44   EXPECT_EQ(-ten % seven, -10 % 7);
45   EXPECT_EQ(ten % -seven, 10 % -7);
46   EXPECT_EQ(-ten % -seven, -10 % -7);
47   EXPECT_EQ(ten % seven, 10 % 7);
48 
49   EXPECT_EQ(-ten / seven, -10 / 7);
50   EXPECT_EQ(ten / -seven, 10 / -7);
51   EXPECT_EQ(-ten / -seven, -10 / -7);
52   EXPECT_EQ(ten / seven, 10 / 7);
53 
54   TypeParam x = ten;
55   x += five;
56   EXPECT_EQ(x, 15);
57   x *= two;
58   EXPECT_EQ(x, 30);
59   x /= seven;
60   EXPECT_EQ(x, 4);
61   x -= two * 10;
62   EXPECT_EQ(x, -16);
63   x *= 2 * two;
64   EXPECT_EQ(x, -64);
65   x /= two / -2;
66   EXPECT_EQ(x, 64);
67 
68   EXPECT_LE(ten, ten);
69   EXPECT_GE(ten, ten);
70   EXPECT_EQ(ten, ten);
71   EXPECT_FALSE(ten != ten);
72   EXPECT_FALSE(ten < ten);
73   EXPECT_FALSE(ten > ten);
74   EXPECT_LT(five, ten);
75   EXPECT_GT(ten, five);
76 }
77 
TYPED_TEST(IntTest,ops64Overloads)78 TYPED_TEST(IntTest, ops64Overloads) {
79   TypeParam two(2), five(5), seven(7), ten(10);
80   EXPECT_EQ(five + 5, ten);
81   EXPECT_EQ(five + 5, 5 + five);
82   EXPECT_EQ(five * 5, 2 * ten + 5);
83   EXPECT_EQ(five * 5, 3 * ten - 5);
84   EXPECT_EQ(five * two, ten);
85   EXPECT_EQ(5 / two, 2);
86   EXPECT_EQ(five / 2, 2);
87   EXPECT_EQ(2 % two, 0);
88   EXPECT_EQ(2 - two, 0);
89   EXPECT_EQ(2 % two, two % 2);
90 
91   TypeParam x = ten;
92   x += 5;
93   EXPECT_EQ(x, 15);
94   x *= 2;
95   EXPECT_EQ(x, 30);
96   x /= 7;
97   EXPECT_EQ(x, 4);
98   x -= 20;
99   EXPECT_EQ(x, -16);
100   x *= 4;
101   EXPECT_EQ(x, -64);
102   x /= -1;
103   EXPECT_EQ(x, 64);
104 
105   EXPECT_LE(ten, 10);
106   EXPECT_GE(ten, 10);
107   EXPECT_EQ(ten, 10);
108   EXPECT_FALSE(ten != 10);
109   EXPECT_FALSE(ten < 10);
110   EXPECT_FALSE(ten > 10);
111   EXPECT_LT(five, 10);
112   EXPECT_GT(ten, 5);
113 
114   EXPECT_LE(10, ten);
115   EXPECT_GE(10, ten);
116   EXPECT_EQ(10, ten);
117   EXPECT_FALSE(10 != ten);
118   EXPECT_FALSE(10 < ten);
119   EXPECT_FALSE(10 > ten);
120   EXPECT_LT(5, ten);
121   EXPECT_GT(10, five);
122 }
123 
TYPED_TEST(IntTest,overflows)124 TYPED_TEST(IntTest, overflows) {
125   TypeParam x(1ll << 60);
126   EXPECT_EQ((x * x - x * x * x * x) / (x * x * x), 1 - (1ll << 60));
127   TypeParam y(1ll << 62);
128   EXPECT_EQ((y + y + y + y + y + y) / y, 6);
129   EXPECT_EQ(-(2 * (-y)), 2 * y); // -(-2^63) overflow.
130   x *= x;
131   EXPECT_EQ(x, (y * y) / 16);
132   y += y;
133   y += y;
134   y += y;
135   y /= 8;
136   EXPECT_EQ(y, 1ll << 62);
137 
138   TypeParam min(std::numeric_limits<int64_t>::min());
139   TypeParam one(1);
140   EXPECT_EQ(floorDiv(min, -one), -min);
141   EXPECT_EQ(ceilDiv(min, -one), -min);
142   EXPECT_EQ(abs(min), -min);
143 
144   TypeParam z = min;
145   z /= -1;
146   EXPECT_EQ(z, -min);
147   TypeParam w(min);
148   --w;
149   EXPECT_EQ(w, TypeParam(min) - 1);
150   TypeParam u(min);
151   u -= 1;
152   EXPECT_EQ(u, w);
153 
154   TypeParam max(std::numeric_limits<int64_t>::max());
155   TypeParam v = max;
156   ++v;
157   EXPECT_EQ(v, max + 1);
158   TypeParam t = max;
159   t += 1;
160   EXPECT_EQ(t, v);
161 }
162 
TYPED_TEST(IntTest,floorCeilModAbsLcmGcd)163 TYPED_TEST(IntTest, floorCeilModAbsLcmGcd) {
164   TypeParam x(1ll << 50), one(1), two(2), three(3);
165 
166   // Run on small values and large values.
167   for (const TypeParam &y : {x, x * x}) {
168     EXPECT_EQ(floorDiv(3 * y, three), y);
169     EXPECT_EQ(ceilDiv(3 * y, three), y);
170     EXPECT_EQ(floorDiv(3 * y - 1, three), y - 1);
171     EXPECT_EQ(ceilDiv(3 * y - 1, three), y);
172     EXPECT_EQ(floorDiv(3 * y - 2, three), y - 1);
173     EXPECT_EQ(ceilDiv(3 * y - 2, three), y);
174 
175     EXPECT_EQ(mod(3 * y, three), 0);
176     EXPECT_EQ(mod(3 * y + 1, three), one);
177     EXPECT_EQ(mod(3 * y + 2, three), two);
178 
179     EXPECT_EQ(floorDiv(3 * y, y), 3);
180     EXPECT_EQ(ceilDiv(3 * y, y), 3);
181     EXPECT_EQ(floorDiv(3 * y - 1, y), 2);
182     EXPECT_EQ(ceilDiv(3 * y - 1, y), 3);
183     EXPECT_EQ(floorDiv(3 * y - 2, y), 2);
184     EXPECT_EQ(ceilDiv(3 * y - 2, y), 3);
185 
186     EXPECT_EQ(mod(3 * y, y), 0);
187     EXPECT_EQ(mod(3 * y + 1, y), 1);
188     EXPECT_EQ(mod(3 * y + 2, y), 2);
189 
190     EXPECT_EQ(abs(y), y);
191     EXPECT_EQ(abs(-y), y);
192 
193     EXPECT_EQ(gcd(2 * y, 3 * y), y);
194     EXPECT_EQ(lcm(2 * y, 3 * y), 6 * y);
195     EXPECT_EQ(gcd(15 * y, 6 * y), 3 * y);
196     EXPECT_EQ(lcm(15 * y, 6 * y), 30 * y);
197   }
198 }
199