1 //===- AffineStructuresTest.cpp - Tests for AffineStructures ----*- C++ -*-===//
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/AffineStructures.h"
10
11 #include <gmock/gmock.h>
12 #include <gtest/gtest.h>
13
14 #include <numeric>
15
16 namespace mlir {
17
18 enum class TestFunction { Sample, Empty };
19
20 /// If fn is TestFunction::Sample (default):
21 /// If hasSample is true, check that findIntegerSample returns a valid sample
22 /// for the FlatAffineConstraints fac.
23 /// If hasSample is false, check that findIntegerSample returns None.
24 ///
25 /// If fn is TestFunction::Empty, check that isIntegerEmpty returns the
26 /// opposite of hasSample.
checkSample(bool hasSample,const FlatAffineConstraints & fac,TestFunction fn=TestFunction::Sample)27 static void checkSample(bool hasSample, const FlatAffineConstraints &fac,
28 TestFunction fn = TestFunction::Sample) {
29 Optional<SmallVector<int64_t, 8>> maybeSample;
30 switch (fn) {
31 case TestFunction::Sample:
32 maybeSample = fac.findIntegerSample();
33 if (!hasSample) {
34 EXPECT_FALSE(maybeSample.hasValue());
35 if (maybeSample.hasValue()) {
36 for (auto x : *maybeSample)
37 llvm::errs() << x << ' ';
38 llvm::errs() << '\n';
39 }
40 } else {
41 ASSERT_TRUE(maybeSample.hasValue());
42 EXPECT_TRUE(fac.containsPoint(*maybeSample));
43 }
44 break;
45 case TestFunction::Empty:
46 EXPECT_EQ(!hasSample, fac.isIntegerEmpty());
47 break;
48 }
49 }
50
51 /// Construct a FlatAffineConstraints from a set of inequality and
52 /// equality constraints.
53 static FlatAffineConstraints
makeFACFromConstraints(unsigned ids,ArrayRef<SmallVector<int64_t,4>> ineqs,ArrayRef<SmallVector<int64_t,4>> eqs,unsigned syms=0)54 makeFACFromConstraints(unsigned ids, ArrayRef<SmallVector<int64_t, 4>> ineqs,
55 ArrayRef<SmallVector<int64_t, 4>> eqs,
56 unsigned syms = 0) {
57 FlatAffineConstraints fac(ineqs.size(), eqs.size(), ids + 1, ids - syms,
58 syms);
59 for (const auto &eq : eqs)
60 fac.addEquality(eq);
61 for (const auto &ineq : ineqs)
62 fac.addInequality(ineq);
63 return fac;
64 }
65
66 /// Check sampling for all the permutations of the dimensions for the given
67 /// constraint set. Since the GBR algorithm progresses dimension-wise, different
68 /// orderings may cause the algorithm to proceed differently. At least some of
69 ///.these permutations should make it past the heuristics and test the
70 /// implementation of the GBR algorithm itself.
71 /// Use TestFunction fn to test.
checkPermutationsSample(bool hasSample,unsigned nDim,ArrayRef<SmallVector<int64_t,4>> ineqs,ArrayRef<SmallVector<int64_t,4>> eqs,TestFunction fn=TestFunction::Sample)72 static void checkPermutationsSample(bool hasSample, unsigned nDim,
73 ArrayRef<SmallVector<int64_t, 4>> ineqs,
74 ArrayRef<SmallVector<int64_t, 4>> eqs,
75 TestFunction fn = TestFunction::Sample) {
76 SmallVector<unsigned, 4> perm(nDim);
77 std::iota(perm.begin(), perm.end(), 0);
78 auto permute = [&perm](ArrayRef<int64_t> coeffs) {
79 SmallVector<int64_t, 4> permuted;
80 for (unsigned id : perm)
81 permuted.push_back(coeffs[id]);
82 permuted.push_back(coeffs.back());
83 return permuted;
84 };
85 do {
86 SmallVector<SmallVector<int64_t, 4>, 4> permutedIneqs, permutedEqs;
87 for (const auto &ineq : ineqs)
88 permutedIneqs.push_back(permute(ineq));
89 for (const auto &eq : eqs)
90 permutedEqs.push_back(permute(eq));
91
92 checkSample(hasSample,
93 makeFACFromConstraints(nDim, permutedIneqs, permutedEqs), fn);
94 } while (std::next_permutation(perm.begin(), perm.end()));
95 }
96
TEST(FlatAffineConstraintsTest,FindSampleTest)97 TEST(FlatAffineConstraintsTest, FindSampleTest) {
98 // Bounded sets with only inequalities.
99
100 // 0 <= 7x <= 5
101 checkSample(true, makeFACFromConstraints(1, {{7, 0}, {-7, 5}}, {}));
102
103 // 1 <= 5x and 5x <= 4 (no solution).
104 checkSample(false, makeFACFromConstraints(1, {{5, -1}, {-5, 4}}, {}));
105
106 // 1 <= 5x and 5x <= 9 (solution: x = 1).
107 checkSample(true, makeFACFromConstraints(1, {{5, -1}, {-5, 9}}, {}));
108
109 // Bounded sets with equalities.
110 // x >= 8 and 40 >= y and x = y.
111 checkSample(
112 true, makeFACFromConstraints(2, {{1, 0, -8}, {0, -1, 40}}, {{1, -1, 0}}));
113
114 // x <= 10 and y <= 10 and 10 <= z and x + 2y = 3z.
115 // solution: x = y = z = 10.
116 checkSample(true, makeFACFromConstraints(
117 3, {{-1, 0, 0, 10}, {0, -1, 0, 10}, {0, 0, 1, -10}},
118 {{1, 2, -3, 0}}));
119
120 // x <= 10 and y <= 10 and 11 <= z and x + 2y = 3z.
121 // This implies x + 2y >= 33 and x + 2y <= 30, which has no solution.
122 checkSample(false, makeFACFromConstraints(
123 3, {{-1, 0, 0, 10}, {0, -1, 0, 10}, {0, 0, 1, -11}},
124 {{1, 2, -3, 0}}));
125
126 // 0 <= r and r <= 3 and 4q + r = 7.
127 // Solution: q = 1, r = 3.
128 checkSample(true,
129 makeFACFromConstraints(2, {{0, 1, 0}, {0, -1, 3}}, {{4, 1, -7}}));
130
131 // 4q + r = 7 and r = 0.
132 // Solution: q = 1, r = 3.
133 checkSample(false, makeFACFromConstraints(2, {}, {{4, 1, -7}, {0, 1, 0}}));
134
135 // The next two sets are large sets that should take a long time to sample
136 // with a naive branch and bound algorithm but can be sampled efficiently with
137 // the GBR algorithm.
138 //
139 // This is a triangle with vertices at (1/3, 0), (2/3, 0) and (10000, 10000).
140 checkSample(
141 true,
142 makeFACFromConstraints(
143 2, {{0, 1, 0}, {300000, -299999, -100000}, {-300000, 299998, 200000}},
144 {}));
145
146 // This is a tetrahedron with vertices at
147 // (1/3, 0, 0), (2/3, 0, 0), (2/3, 0, 10000), and (10000, 10000, 10000).
148 // The first three points form a triangular base on the xz plane with the
149 // apex at the fourth point, which is the only integer point.
150 checkPermutationsSample(
151 true, 3,
152 {
153 {0, 1, 0, 0}, // y >= 0
154 {0, -1, 1, 0}, // z >= y
155 {300000, -299998, -1,
156 -100000}, // -300000x + 299998y + 100000 + z <= 0.
157 {-150000, 149999, 0, 100000}, // -150000x + 149999y + 100000 >= 0.
158 },
159 {});
160
161 // Same thing with some spurious extra dimensions equated to constants.
162 checkSample(true,
163 makeFACFromConstraints(
164 5,
165 {
166 {0, 1, 0, 1, -1, 0},
167 {0, -1, 1, -1, 1, 0},
168 {300000, -299998, -1, -9, 21, -112000},
169 {-150000, 149999, 0, -15, 47, 68000},
170 },
171 {{0, 0, 0, 1, -1, 0}, // p = q.
172 {0, 0, 0, 1, 1, -2000}})); // p + q = 20000 => p = q = 10000.
173
174 // This is a tetrahedron with vertices at
175 // (1/3, 0, 0), (2/3, 0, 0), (2/3, 0, 100), (100, 100 - 1/3, 100).
176 checkPermutationsSample(false, 3,
177 {
178 {0, 1, 0, 0},
179 {0, -300, 299, 0},
180 {300 * 299, -89400, -299, -100 * 299},
181 {-897, 894, 0, 598},
182 },
183 {});
184
185 // Two tests involving equalities that are integer empty but not rational
186 // empty.
187
188 // This is a line segment from (0, 1/3) to (100, 100 + 1/3).
189 checkSample(false, makeFACFromConstraints(
190 2,
191 {
192 {1, 0, 0}, // x >= 0.
193 {-1, 0, 100} // -x + 100 >= 0, i.e., x <= 100.
194 },
195 {
196 {3, -3, 1} // 3x - 3y + 1 = 0, i.e., y = x + 1/3.
197 }));
198
199 // A thin parallelogram. 0 <= x <= 100 and x + 1/3 <= y <= x + 2/3.
200 checkSample(false, makeFACFromConstraints(2,
201 {
202 {1, 0, 0}, // x >= 0.
203 {-1, 0, 100}, // x <= 100.
204 {3, -3, 2}, // 3x - 3y >= -2.
205 {-3, 3, -1}, // 3x - 3y <= -1.
206 },
207 {}));
208
209 checkSample(true, makeFACFromConstraints(2,
210 {
211 {2, 0, 0}, // 2x >= 1.
212 {-2, 0, 99}, // 2x <= 99.
213 {0, 2, 0}, // 2y >= 0.
214 {0, -2, 99}, // 2y <= 99.
215 },
216 {}));
217 // 2D cone with apex at (10000, 10000) and
218 // edges passing through (1/3, 0) and (2/3, 0).
219 checkSample(
220 true,
221 makeFACFromConstraints(
222 2, {{300000, -299999, -100000}, {-300000, 299998, 200000}}, {}));
223
224 // Cartesian product of a tetrahedron and a 2D cone.
225 // The tetrahedron has vertices at
226 // (1/3, 0, 0), (2/3, 0, 0), (2/3, 0, 10000), and (10000, 10000, 10000).
227 // The first three points form a triangular base on the xz plane with the
228 // apex at the fourth point, which is the only integer point.
229 // The cone has apex at (10000, 10000) and
230 // edges passing through (1/3, 0) and (2/3, 0).
231 checkPermutationsSample(
232 true /* not empty */, 5,
233 {
234 // Tetrahedron contraints:
235 {0, 1, 0, 0, 0, 0}, // y >= 0
236 {0, -1, 1, 0, 0, 0}, // z >= y
237 // -300000x + 299998y + 100000 + z <= 0.
238 {300000, -299998, -1, 0, 0, -100000},
239 // -150000x + 149999y + 100000 >= 0.
240 {-150000, 149999, 0, 0, 0, 100000},
241
242 // Triangle constraints:
243 // 300000p - 299999q >= 100000
244 {0, 0, 0, 300000, -299999, -100000},
245 // -300000p + 299998q + 200000 >= 0
246 {0, 0, 0, -300000, 299998, 200000},
247 },
248 {});
249
250 // Cartesian product of same tetrahedron as above and {(p, q) : 1/3 <= p <=
251 // 2/3}. Since the second set is empty, the whole set is too.
252 checkPermutationsSample(
253 false /* empty */, 5,
254 {
255 // Tetrahedron contraints:
256 {0, 1, 0, 0, 0, 0}, // y >= 0
257 {0, -1, 1, 0, 0, 0}, // z >= y
258 // -300000x + 299998y + 100000 + z <= 0.
259 {300000, -299998, -1, 0, 0, -100000},
260 // -150000x + 149999y + 100000 >= 0.
261 {-150000, 149999, 0, 0, 0, 100000},
262
263 // Second set constraints:
264 // 3p >= 1
265 {0, 0, 0, 3, 0, -1},
266 // 3p <= 2
267 {0, 0, 0, -3, 0, 2},
268 },
269 {});
270
271 // Cartesian product of same tetrahedron as above and
272 // {(p, q, r) : 1 <= p <= 2 and p = 3q + 3r}.
273 // Since the second set is empty, the whole set is too.
274 checkPermutationsSample(
275 false /* empty */, 5,
276 {
277 // Tetrahedron contraints:
278 {0, 1, 0, 0, 0, 0, 0}, // y >= 0
279 {0, -1, 1, 0, 0, 0, 0}, // z >= y
280 // -300000x + 299998y + 100000 + z <= 0.
281 {300000, -299998, -1, 0, 0, 0, -100000},
282 // -150000x + 149999y + 100000 >= 0.
283 {-150000, 149999, 0, 0, 0, 0, 100000},
284
285 // Second set constraints:
286 // p >= 1
287 {0, 0, 0, 1, 0, 0, -1},
288 // p <= 2
289 {0, 0, 0, -1, 0, 0, 2},
290 },
291 {
292 {0, 0, 0, 1, -3, -3, 0}, // p = 3q + 3r
293 });
294
295 // Cartesian product of a tetrahedron and a 2D cone.
296 // The tetrahedron is empty and has vertices at
297 // (1/3, 0, 0), (2/3, 0, 0), (2/3, 0, 100), and (100, 100 - 1/3, 100).
298 // The cone has apex at (10000, 10000) and
299 // edges passing through (1/3, 0) and (2/3, 0).
300 // Since the tetrahedron is empty, the Cartesian product is too.
301 checkPermutationsSample(false /* empty */, 5,
302 {
303 // Tetrahedron contraints:
304 {0, 1, 0, 0, 0, 0},
305 {0, -300, 299, 0, 0, 0},
306 {300 * 299, -89400, -299, 0, 0, -100 * 299},
307 {-897, 894, 0, 0, 0, 598},
308
309 // Triangle constraints:
310 // 300000p - 299999q >= 100000
311 {0, 0, 0, 300000, -299999, -100000},
312 // -300000p + 299998q + 200000 >= 0
313 {0, 0, 0, -300000, 299998, 200000},
314 },
315 {});
316
317 // Cartesian product of same tetrahedron as above and
318 // {(p, q) : 1/3 <= p <= 2/3}.
319 checkPermutationsSample(false /* empty */, 5,
320 {
321 // Tetrahedron contraints:
322 {0, 1, 0, 0, 0, 0},
323 {0, -300, 299, 0, 0, 0},
324 {300 * 299, -89400, -299, 0, 0, -100 * 299},
325 {-897, 894, 0, 0, 0, 598},
326
327 // Second set constraints:
328 // 3p >= 1
329 {0, 0, 0, 3, 0, -1},
330 // 3p <= 2
331 {0, 0, 0, -3, 0, 2},
332 },
333 {});
334
335 checkSample(true, makeFACFromConstraints(3,
336 {
337 {2, 0, 0, -1}, // 2x >= 1
338 },
339 {{
340 {1, -1, 0, -1}, // y = x - 1
341 {0, 1, -1, 0}, // z = y
342 }}));
343 }
344
TEST(FlatAffineConstraintsTest,IsIntegerEmptyTest)345 TEST(FlatAffineConstraintsTest, IsIntegerEmptyTest) {
346 // 1 <= 5x and 5x <= 4 (no solution).
347 EXPECT_TRUE(
348 makeFACFromConstraints(1, {{5, -1}, {-5, 4}}, {}).isIntegerEmpty());
349 // 1 <= 5x and 5x <= 9 (solution: x = 1).
350 EXPECT_FALSE(
351 makeFACFromConstraints(1, {{5, -1}, {-5, 9}}, {}).isIntegerEmpty());
352
353 // Unbounded sets.
354 EXPECT_TRUE(makeFACFromConstraints(3,
355 {
356 {0, 2, 0, -1}, // 2y >= 1
357 {0, -2, 0, 1}, // 2y <= 1
358 {0, 0, 2, -1}, // 2z >= 1
359 },
360 {{2, 0, 0, -1}} // 2x = 1
361 )
362 .isIntegerEmpty());
363
364 EXPECT_FALSE(makeFACFromConstraints(3,
365 {
366 {2, 0, 0, -1}, // 2x >= 1
367 {-3, 0, 0, 3}, // 3x <= 3
368 {0, 0, 5, -6}, // 5z >= 6
369 {0, 0, -7, 17}, // 7z <= 17
370 {0, 3, 0, -2}, // 3y >= 2
371 },
372 {})
373 .isIntegerEmpty());
374
375 EXPECT_FALSE(makeFACFromConstraints(3,
376 {
377 {2, 0, 0, -1}, // 2x >= 1
378 },
379 {{
380 {1, -1, 0, -1}, // y = x - 1
381 {0, 1, -1, 0}, // z = y
382 }})
383 .isIntegerEmpty());
384
385 // FlatAffineConstraints::isEmpty() does not detect the following sets to be
386 // empty.
387
388 // 3x + 7y = 1 and 0 <= x, y <= 10.
389 // Since x and y are non-negative, 3x + 7y can never be 1.
390 EXPECT_TRUE(
391 makeFACFromConstraints(
392 2, {{1, 0, 0}, {-1, 0, 10}, {0, 1, 0}, {0, -1, 10}}, {{3, 7, -1}})
393 .isIntegerEmpty());
394
395 // 2x = 3y and y = x - 1 and x + y = 6z + 2 and 0 <= x, y <= 100.
396 // Substituting y = x - 1 in 3y = 2x, we obtain x = 3 and hence y = 2.
397 // Since x + y = 5 cannot be equal to 6z + 2 for any z, the set is empty.
398 EXPECT_TRUE(
399 makeFACFromConstraints(3,
400 {
401 {1, 0, 0, 0},
402 {-1, 0, 0, 100},
403 {0, 1, 0, 0},
404 {0, -1, 0, 100},
405 },
406 {{2, -3, 0, 0}, {1, -1, 0, -1}, {1, 1, -6, -2}})
407 .isIntegerEmpty());
408
409 // 2x = 3y and y = x - 1 + 6z and x + y = 6q + 2 and 0 <= x, y <= 100.
410 // 2x = 3y implies x is a multiple of 3 and y is even.
411 // Now y = x - 1 + 6z implies y = 2 mod 3. In fact, since y is even, we have
412 // y = 2 mod 6. Then since x = y + 1 + 6z, we have x = 3 mod 6, implying
413 // x + y = 5 mod 6, which contradicts x + y = 6q + 2, so the set is empty.
414 EXPECT_TRUE(makeFACFromConstraints(
415 4,
416 {
417 {1, 0, 0, 0, 0},
418 {-1, 0, 0, 0, 100},
419 {0, 1, 0, 0, 0},
420 {0, -1, 0, 0, 100},
421 },
422 {{2, -3, 0, 0, 0}, {1, -1, 6, 0, -1}, {1, 1, 0, -6, -2}})
423 .isIntegerEmpty());
424
425 // Set with symbols.
426 FlatAffineConstraints fac6 = makeFACFromConstraints(2,
427 {
428 {1, 1, 0},
429 },
430 {
431 {1, -1, 0},
432 },
433 1);
434 EXPECT_FALSE(fac6.isIntegerEmpty());
435 }
436
TEST(FlatAffineConstraintsTest,removeRedundantConstraintsTest)437 TEST(FlatAffineConstraintsTest, removeRedundantConstraintsTest) {
438 FlatAffineConstraints fac = makeFACFromConstraints(1,
439 {
440 {1, -2}, // x >= 2.
441 {-1, 2} // x <= 2.
442 },
443 {{1, -2}}); // x == 2.
444 fac.removeRedundantConstraints();
445
446 // Both inequalities are redundant given the equality. Both have been removed.
447 EXPECT_EQ(fac.getNumInequalities(), 0u);
448 EXPECT_EQ(fac.getNumEqualities(), 1u);
449
450 FlatAffineConstraints fac2 =
451 makeFACFromConstraints(2,
452 {
453 {1, 0, -3}, // x >= 3.
454 {0, 1, -2} // y >= 2 (redundant).
455 },
456 {{1, -1, 0}}); // x == y.
457 fac2.removeRedundantConstraints();
458
459 // The second inequality is redundant and should have been removed. The
460 // remaining inequality should be the first one.
461 EXPECT_EQ(fac2.getNumInequalities(), 1u);
462 EXPECT_THAT(fac2.getInequality(0), testing::ElementsAre(1, 0, -3));
463 EXPECT_EQ(fac2.getNumEqualities(), 1u);
464
465 FlatAffineConstraints fac3 =
466 makeFACFromConstraints(3, {},
467 {{1, -1, 0, 0}, // x == y.
468 {1, 0, -1, 0}, // x == z.
469 {0, 1, -1, 0}}); // y == z.
470 fac3.removeRedundantConstraints();
471
472 // One of the three equalities can be removed.
473 EXPECT_EQ(fac3.getNumInequalities(), 0u);
474 EXPECT_EQ(fac3.getNumEqualities(), 2u);
475
476 FlatAffineConstraints fac4 = makeFACFromConstraints(
477 17,
478 {{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1},
479 {0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 500},
480 {0, 0, 0, -16, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
481 {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1},
482 {0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 998},
483 {0, 0, 0, 16, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15},
484 {0, 0, 0, 0, -16, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
485 {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1},
486 {0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 998},
487 {0, 0, 0, 0, 16, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15},
488 {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
489 {0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
490 {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -1},
491 {0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 500},
492 {0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 15},
493 {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -16, 0, 0, 0, 0, 0, 0},
494 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -16, 0, 1, 0, 0, 0},
495 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -1},
496 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 998},
497 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, -1, 0, 0, 15},
498 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
499 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1},
500 {0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8},
501 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 8, 8},
502 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, -8, -1},
503 {0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -8, -1},
504 {0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
505 {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0},
506 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -10},
507 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 10},
508 {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -13},
509 {0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 13},
510 {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10},
511 {0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
512 {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13},
513 {-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13}},
514 {});
515
516 // The above is a large set of constraints without any redundant constraints,
517 // as verified by the Fourier-Motzkin based removeRedundantInequalities.
518 unsigned nIneq = fac4.getNumInequalities();
519 unsigned nEq = fac4.getNumEqualities();
520 fac4.removeRedundantInequalities();
521 ASSERT_EQ(fac4.getNumInequalities(), nIneq);
522 ASSERT_EQ(fac4.getNumEqualities(), nEq);
523 // Now we test that removeRedundantConstraints does not find any constraints
524 // to be redundant either.
525 fac4.removeRedundantConstraints();
526 EXPECT_EQ(fac4.getNumInequalities(), nIneq);
527 EXPECT_EQ(fac4.getNumEqualities(), nEq);
528
529 FlatAffineConstraints fac5 =
530 makeFACFromConstraints(2,
531 {
532 {128, 0, 127}, // [0]: 128x >= -127.
533 {-1, 0, 7}, // [1]: x <= 7.
534 {-128, 1, 0}, // [2]: y >= 128x.
535 {0, 1, 0} // [3]: y >= 0.
536 },
537 {});
538 // [0] implies that 128x >= 0, since x has to be an integer. (This should be
539 // caught by GCDTightenInqualities().)
540 // So [2] and [0] imply [3] since we have y >= 128x >= 0.
541 fac5.removeRedundantConstraints();
542 EXPECT_EQ(fac5.getNumInequalities(), 3u);
543 SmallVector<int64_t, 8> redundantConstraint = {0, 1, 0};
544 for (unsigned i = 0; i < 3; ++i) {
545 // Ensure that the removed constraint was the redundant constraint [3].
546 EXPECT_NE(fac5.getInequality(i), ArrayRef<int64_t>(redundantConstraint));
547 }
548 }
549
TEST(FlatAffineConstraintsTest,addConstantUpperBound)550 TEST(FlatAffineConstraintsTest, addConstantUpperBound) {
551 FlatAffineConstraints fac = makeFACFromConstraints(2, {}, {});
552 fac.addConstantUpperBound(0, 1);
553 EXPECT_EQ(fac.atIneq(0, 0), -1);
554 EXPECT_EQ(fac.atIneq(0, 1), 0);
555 EXPECT_EQ(fac.atIneq(0, 2), 1);
556
557 fac.addConstantUpperBound({1, 2, 3}, 1);
558 EXPECT_EQ(fac.atIneq(1, 0), -1);
559 EXPECT_EQ(fac.atIneq(1, 1), -2);
560 EXPECT_EQ(fac.atIneq(1, 2), -2);
561 }
562
TEST(FlatAffineConstraintsTest,addConstantLowerBound)563 TEST(FlatAffineConstraintsTest, addConstantLowerBound) {
564 FlatAffineConstraints fac = makeFACFromConstraints(2, {}, {});
565 fac.addConstantLowerBound(0, 1);
566 EXPECT_EQ(fac.atIneq(0, 0), 1);
567 EXPECT_EQ(fac.atIneq(0, 1), 0);
568 EXPECT_EQ(fac.atIneq(0, 2), -1);
569
570 fac.addConstantLowerBound({1, 2, 3}, 1);
571 EXPECT_EQ(fac.atIneq(1, 0), 1);
572 EXPECT_EQ(fac.atIneq(1, 1), 2);
573 EXPECT_EQ(fac.atIneq(1, 2), 2);
574 }
575
TEST(FlatAffineConstraintsTest,clearConstraints)576 TEST(FlatAffineConstraintsTest, clearConstraints) {
577 FlatAffineConstraints fac = makeFACFromConstraints(1, {}, {});
578
579 fac.addInequality({1, 0});
580 EXPECT_EQ(fac.atIneq(0, 0), 1);
581 EXPECT_EQ(fac.atIneq(0, 1), 0);
582
583 fac.clearConstraints();
584
585 fac.addInequality({1, 0});
586 EXPECT_EQ(fac.atIneq(0, 0), 1);
587 EXPECT_EQ(fac.atIneq(0, 1), 0);
588 }
589
590 } // namespace mlir
591