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. 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. 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 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 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 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 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 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. 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 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 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 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 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 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 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 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. 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 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 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 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 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