1 //===- SimplexTest.cpp - Tests for Simplex --------------------------------===//
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/Simplex.h"
10
11 #include <gmock/gmock.h>
12 #include <gtest/gtest.h>
13
14 namespace mlir {
15
16 /// Take a snapshot, add constraints making the set empty, and rollback.
17 /// The set should not be empty after rolling back.
TEST(SimplexTest,emptyRollback)18 TEST(SimplexTest, emptyRollback) {
19 Simplex simplex(2);
20 // (u - v) >= 0
21 simplex.addInequality({1, -1, 0});
22 EXPECT_FALSE(simplex.isEmpty());
23
24 unsigned snapshot = simplex.getSnapshot();
25 // (u - v) <= -1
26 simplex.addInequality({-1, 1, -1});
27 EXPECT_TRUE(simplex.isEmpty());
28 simplex.rollback(snapshot);
29 EXPECT_FALSE(simplex.isEmpty());
30 }
31
32 /// Check that the set gets marked as empty when we add contradictory
33 /// constraints.
TEST(SimplexTest,addEquality_separate)34 TEST(SimplexTest, addEquality_separate) {
35 Simplex simplex(1);
36 simplex.addInequality({1, -1}); // x >= 1.
37 ASSERT_FALSE(simplex.isEmpty());
38 simplex.addEquality({1, 0}); // x == 0.
39 EXPECT_TRUE(simplex.isEmpty());
40 }
41
expectInequalityMakesSetEmpty(Simplex & simplex,ArrayRef<int64_t> coeffs,bool expect)42 void expectInequalityMakesSetEmpty(Simplex &simplex, ArrayRef<int64_t> coeffs,
43 bool expect) {
44 ASSERT_FALSE(simplex.isEmpty());
45 unsigned snapshot = simplex.getSnapshot();
46 simplex.addInequality(coeffs);
47 EXPECT_EQ(simplex.isEmpty(), expect);
48 simplex.rollback(snapshot);
49 }
50
TEST(SimplexTest,addInequality_rollback)51 TEST(SimplexTest, addInequality_rollback) {
52 Simplex simplex(3);
53 SmallVector<int64_t, 4> coeffs[]{{1, 0, 0, 0}, // u >= 0.
54 {-1, 0, 0, 0}, // u <= 0.
55 {1, -1, 1, 0}, // u - v + w >= 0.
56 {1, 1, -1, 0}}; // u + v - w >= 0.
57 // The above constraints force u = 0 and v = w.
58 // The constraints below violate v = w.
59 SmallVector<int64_t, 4> checkCoeffs[]{{0, 1, -1, -1}, // v - w >= 1.
60 {0, -1, 1, -1}}; // v - w <= -1.
61
62 for (int run = 0; run < 4; run++) {
63 unsigned snapshot = simplex.getSnapshot();
64
65 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], false);
66 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], false);
67
68 for (int i = 0; i < 4; i++)
69 simplex.addInequality(coeffs[(run + i) % 4]);
70
71 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], true);
72 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], true);
73
74 simplex.rollback(snapshot);
75 EXPECT_EQ(simplex.numConstraints(), 0u);
76
77 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], false);
78 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], false);
79 }
80 }
81
simplexFromConstraints(unsigned nDim,SmallVector<SmallVector<int64_t,8>,8> ineqs,SmallVector<SmallVector<int64_t,8>,8> eqs)82 Simplex simplexFromConstraints(unsigned nDim,
83 SmallVector<SmallVector<int64_t, 8>, 8> ineqs,
84 SmallVector<SmallVector<int64_t, 8>, 8> eqs) {
85 Simplex simplex(nDim);
86 for (const auto &ineq : ineqs)
87 simplex.addInequality(ineq);
88 for (const auto &eq : eqs)
89 simplex.addEquality(eq);
90 return simplex;
91 }
92
TEST(SimplexTest,isUnbounded)93 TEST(SimplexTest, isUnbounded) {
94 EXPECT_FALSE(simplexFromConstraints(
95 2, {{1, 1, 0}, {-1, -1, 0}, {1, -1, 5}, {-1, 1, -5}}, {})
96 .isUnbounded());
97
98 EXPECT_TRUE(
99 simplexFromConstraints(2, {{1, 1, 0}, {1, -1, 5}, {-1, 1, -5}}, {})
100 .isUnbounded());
101
102 EXPECT_TRUE(
103 simplexFromConstraints(2, {{-1, -1, 0}, {1, -1, 5}, {-1, 1, -5}}, {})
104 .isUnbounded());
105
106 EXPECT_TRUE(simplexFromConstraints(2, {}, {}).isUnbounded());
107
108 EXPECT_FALSE(simplexFromConstraints(3,
109 {
110 {2, 0, 0, -1},
111 {-2, 0, 0, 1},
112 {0, 2, 0, -1},
113 {0, -2, 0, 1},
114 {0, 0, 2, -1},
115 {0, 0, -2, 1},
116 },
117 {})
118 .isUnbounded());
119
120 EXPECT_TRUE(simplexFromConstraints(3,
121 {
122 {2, 0, 0, -1},
123 {-2, 0, 0, 1},
124 {0, 2, 0, -1},
125 {0, -2, 0, 1},
126 {0, 0, -2, 1},
127 },
128 {})
129 .isUnbounded());
130
131 EXPECT_TRUE(simplexFromConstraints(3,
132 {
133 {2, 0, 0, -1},
134 {-2, 0, 0, 1},
135 {0, 2, 0, -1},
136 {0, -2, 0, 1},
137 {0, 0, 2, -1},
138 },
139 {})
140 .isUnbounded());
141
142 // Bounded set with equalities.
143 EXPECT_FALSE(simplexFromConstraints(2,
144 {{1, 1, 1}, // x + y >= -1.
145 {-1, -1, 1}}, // x + y <= 1.
146 {{1, -1, 0}} // x = y.
147 )
148 .isUnbounded());
149
150 // Unbounded set with equalities.
151 EXPECT_TRUE(simplexFromConstraints(3,
152 {{1, 1, 1, 1}, // x + y + z >= -1.
153 {-1, -1, -1, 1}}, // x + y + z <= 1.
154 {{1, -1, -1, 0}} // x = y + z.
155 )
156 .isUnbounded());
157
158 // Rational empty set.
159 EXPECT_FALSE(simplexFromConstraints(3,
160 {
161 {2, 0, 0, -1},
162 {-2, 0, 0, 1},
163 {0, 2, 2, -1},
164 {0, -2, -2, 1},
165 {3, 3, 3, -4},
166 },
167 {})
168 .isUnbounded());
169 }
170
TEST(SimplexTest,getSamplePointIfIntegral)171 TEST(SimplexTest, getSamplePointIfIntegral) {
172 // Empty set.
173 EXPECT_FALSE(simplexFromConstraints(3,
174 {
175 {2, 0, 0, -1},
176 {-2, 0, 0, 1},
177 {0, 2, 2, -1},
178 {0, -2, -2, 1},
179 {3, 3, 3, -4},
180 },
181 {})
182 .getSamplePointIfIntegral()
183 .hasValue());
184
185 auto maybeSample = simplexFromConstraints(2,
186 {// x = y - 2.
187 {1, -1, 2},
188 {-1, 1, -2},
189 // x + y = 2.
190 {1, 1, -2},
191 {-1, -1, 2}},
192 {})
193 .getSamplePointIfIntegral();
194
195 EXPECT_TRUE(maybeSample.hasValue());
196 EXPECT_THAT(*maybeSample, testing::ElementsAre(0, 2));
197
198 auto maybeSample2 = simplexFromConstraints(2,
199 {
200 {1, 0, 0}, // x >= 0.
201 {-1, 0, 0}, // x <= 0.
202 },
203 {
204 {0, 1, -2} // y = 2.
205 })
206 .getSamplePointIfIntegral();
207 EXPECT_TRUE(maybeSample2.hasValue());
208 EXPECT_THAT(*maybeSample2, testing::ElementsAre(0, 2));
209
210 EXPECT_FALSE(simplexFromConstraints(1,
211 {// 2x = 1. (no integer solutions)
212 {2, -1},
213 {-2, +1}},
214 {})
215 .getSamplePointIfIntegral()
216 .hasValue());
217 }
218
219 /// Some basic sanity checks involving zero or one variables.
TEST(SimplexTest,isMarkedRedundant_no_var_ge_zero)220 TEST(SimplexTest, isMarkedRedundant_no_var_ge_zero) {
221 Simplex simplex(0);
222 simplex.addInequality({0}); // 0 >= 0.
223
224 simplex.detectRedundant();
225 ASSERT_FALSE(simplex.isEmpty());
226 EXPECT_TRUE(simplex.isMarkedRedundant(0));
227 }
228
TEST(SimplexTest,isMarkedRedundant_no_var_eq)229 TEST(SimplexTest, isMarkedRedundant_no_var_eq) {
230 Simplex simplex(0);
231 simplex.addEquality({0}); // 0 == 0.
232 simplex.detectRedundant();
233 ASSERT_FALSE(simplex.isEmpty());
234 EXPECT_TRUE(simplex.isMarkedRedundant(0));
235 }
236
TEST(SimplexTest,isMarkedRedundant_pos_var_eq)237 TEST(SimplexTest, isMarkedRedundant_pos_var_eq) {
238 Simplex simplex(1);
239 simplex.addEquality({1, 0}); // x == 0.
240
241 simplex.detectRedundant();
242 ASSERT_FALSE(simplex.isEmpty());
243 EXPECT_FALSE(simplex.isMarkedRedundant(0));
244 }
245
TEST(SimplexTest,isMarkedRedundant_zero_var_eq)246 TEST(SimplexTest, isMarkedRedundant_zero_var_eq) {
247 Simplex simplex(1);
248 simplex.addEquality({0, 0}); // 0x == 0.
249 simplex.detectRedundant();
250 ASSERT_FALSE(simplex.isEmpty());
251 EXPECT_TRUE(simplex.isMarkedRedundant(0));
252 }
253
TEST(SimplexTest,isMarkedRedundant_neg_var_eq)254 TEST(SimplexTest, isMarkedRedundant_neg_var_eq) {
255 Simplex simplex(1);
256 simplex.addEquality({-1, 0}); // -x == 0.
257 simplex.detectRedundant();
258 ASSERT_FALSE(simplex.isEmpty());
259 EXPECT_FALSE(simplex.isMarkedRedundant(0));
260 }
261
TEST(SimplexTest,isMarkedRedundant_pos_var_ge)262 TEST(SimplexTest, isMarkedRedundant_pos_var_ge) {
263 Simplex simplex(1);
264 simplex.addInequality({1, 0}); // x >= 0.
265 simplex.detectRedundant();
266 ASSERT_FALSE(simplex.isEmpty());
267 EXPECT_FALSE(simplex.isMarkedRedundant(0));
268 }
269
TEST(SimplexTest,isMarkedRedundant_zero_var_ge)270 TEST(SimplexTest, isMarkedRedundant_zero_var_ge) {
271 Simplex simplex(1);
272 simplex.addInequality({0, 0}); // 0x >= 0.
273 simplex.detectRedundant();
274 ASSERT_FALSE(simplex.isEmpty());
275 EXPECT_TRUE(simplex.isMarkedRedundant(0));
276 }
277
TEST(SimplexTest,isMarkedRedundant_neg_var_ge)278 TEST(SimplexTest, isMarkedRedundant_neg_var_ge) {
279 Simplex simplex(1);
280 simplex.addInequality({-1, 0}); // x <= 0.
281 simplex.detectRedundant();
282 ASSERT_FALSE(simplex.isEmpty());
283 EXPECT_FALSE(simplex.isMarkedRedundant(0));
284 }
285
286 /// None of the constraints are redundant. Slightly more complicated test
287 /// involving an equality.
TEST(SimplexTest,isMarkedRedundant_no_redundant)288 TEST(SimplexTest, isMarkedRedundant_no_redundant) {
289 Simplex simplex(3);
290
291 simplex.addEquality({-1, 0, 1, 0}); // u = w.
292 simplex.addInequality({-1, 16, 0, 15}); // 15 - (u - 16v) >= 0.
293 simplex.addInequality({1, -16, 0, 0}); // (u - 16v) >= 0.
294
295 simplex.detectRedundant();
296 ASSERT_FALSE(simplex.isEmpty());
297
298 for (unsigned i = 0; i < simplex.numConstraints(); ++i)
299 EXPECT_FALSE(simplex.isMarkedRedundant(i)) << "i = " << i << "\n";
300 }
301
TEST(SimplexTest,isMarkedRedundant_repeated_constraints)302 TEST(SimplexTest, isMarkedRedundant_repeated_constraints) {
303 Simplex simplex(3);
304
305 // [4] to [7] are repeats of [0] to [3].
306 simplex.addInequality({0, -1, 0, 1}); // [0]: y <= 1.
307 simplex.addInequality({-1, 0, 8, 7}); // [1]: 8z >= x - 7.
308 simplex.addInequality({1, 0, -8, 0}); // [2]: 8z <= x.
309 simplex.addInequality({0, 1, 0, 0}); // [3]: y >= 0.
310 simplex.addInequality({-1, 0, 8, 7}); // [4]: 8z >= 7 - x.
311 simplex.addInequality({1, 0, -8, 0}); // [5]: 8z <= x.
312 simplex.addInequality({0, 1, 0, 0}); // [6]: y >= 0.
313 simplex.addInequality({0, -1, 0, 1}); // [7]: y <= 1.
314
315 simplex.detectRedundant();
316 ASSERT_FALSE(simplex.isEmpty());
317
318 EXPECT_EQ(simplex.isMarkedRedundant(0), true);
319 EXPECT_EQ(simplex.isMarkedRedundant(1), true);
320 EXPECT_EQ(simplex.isMarkedRedundant(2), true);
321 EXPECT_EQ(simplex.isMarkedRedundant(3), true);
322 EXPECT_EQ(simplex.isMarkedRedundant(4), false);
323 EXPECT_EQ(simplex.isMarkedRedundant(5), false);
324 EXPECT_EQ(simplex.isMarkedRedundant(6), false);
325 EXPECT_EQ(simplex.isMarkedRedundant(7), false);
326 }
327
TEST(SimplexTest,isMarkedRedundant)328 TEST(SimplexTest, isMarkedRedundant) {
329 Simplex simplex(3);
330 simplex.addInequality({0, -1, 0, 1}); // [0]: y <= 1.
331 simplex.addInequality({1, 0, 0, -1}); // [1]: x >= 1.
332 simplex.addInequality({-1, 0, 0, 2}); // [2]: x <= 2.
333 simplex.addInequality({-1, 0, 2, 7}); // [3]: 2z >= x - 7.
334 simplex.addInequality({1, 0, -2, 0}); // [4]: 2z <= x.
335 simplex.addInequality({0, 1, 0, 0}); // [5]: y >= 0.
336 simplex.addInequality({0, 1, -2, 1}); // [6]: y >= 2z - 1.
337 simplex.addInequality({-1, 1, 0, 1}); // [7]: y >= x - 1.
338
339 simplex.detectRedundant();
340 ASSERT_FALSE(simplex.isEmpty());
341
342 // [0], [1], [3], [4], [7] together imply [2], [5], [6] must hold.
343 //
344 // From [7], [0]: x <= y + 1 <= 2, so we have [2].
345 // From [7], [1]: y >= x - 1 >= 0, so we have [5].
346 // From [4], [7]: 2z - 1 <= x - 1 <= y, so we have [6].
347 EXPECT_FALSE(simplex.isMarkedRedundant(0));
348 EXPECT_FALSE(simplex.isMarkedRedundant(1));
349 EXPECT_TRUE(simplex.isMarkedRedundant(2));
350 EXPECT_FALSE(simplex.isMarkedRedundant(3));
351 EXPECT_FALSE(simplex.isMarkedRedundant(4));
352 EXPECT_TRUE(simplex.isMarkedRedundant(5));
353 EXPECT_TRUE(simplex.isMarkedRedundant(6));
354 EXPECT_FALSE(simplex.isMarkedRedundant(7));
355 }
356
TEST(SimplexTest,isMarkedRedundantTiledLoopNestConstraints)357 TEST(SimplexTest, isMarkedRedundantTiledLoopNestConstraints) {
358 Simplex simplex(3); // Variables are x, y, N.
359 simplex.addInequality({1, 0, 0, 0}); // [0]: x >= 0.
360 simplex.addInequality({-32, 0, 1, -1}); // [1]: 32x <= N - 1.
361 simplex.addInequality({0, 1, 0, 0}); // [2]: y >= 0.
362 simplex.addInequality({-32, 1, 0, 0}); // [3]: y >= 32x.
363 simplex.addInequality({32, -1, 0, 31}); // [4]: y <= 32x + 31.
364 simplex.addInequality({0, -1, 1, -1}); // [5]: y <= N - 1.
365 // [3] and [0] imply [2], as we have y >= 32x >= 0.
366 // [3] and [5] imply [1], as we have 32x <= y <= N - 1.
367 simplex.detectRedundant();
368 EXPECT_FALSE(simplex.isMarkedRedundant(0));
369 EXPECT_TRUE(simplex.isMarkedRedundant(1));
370 EXPECT_TRUE(simplex.isMarkedRedundant(2));
371 EXPECT_FALSE(simplex.isMarkedRedundant(3));
372 EXPECT_FALSE(simplex.isMarkedRedundant(4));
373 EXPECT_FALSE(simplex.isMarkedRedundant(5));
374 }
375
TEST(SimplexTest,addInequality_already_redundant)376 TEST(SimplexTest, addInequality_already_redundant) {
377 Simplex simplex(1);
378 simplex.addInequality({1, -1}); // x >= 1.
379 simplex.addInequality({1, 0}); // x >= 0.
380 simplex.detectRedundant();
381 ASSERT_FALSE(simplex.isEmpty());
382 EXPECT_FALSE(simplex.isMarkedRedundant(0));
383 EXPECT_TRUE(simplex.isMarkedRedundant(1));
384 }
385
386 } // namespace mlir
387