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 #include "../../Dialect/Affine/Analysis/AffineStructuresParser.h" 11 12 #include <gmock/gmock.h> 13 #include <gtest/gtest.h> 14 15 namespace mlir { 16 17 /// Take a snapshot, add constraints making the set empty, and rollback. 18 /// The set should not be empty after rolling back. We add additional 19 /// constraints after the set is already empty and roll back the addition 20 /// of these. The set should be marked non-empty only once we rollback 21 /// past the addition of the first constraint that made it empty. 22 TEST(SimplexTest, emptyRollback) { 23 Simplex simplex(2); 24 // (u - v) >= 0 25 simplex.addInequality({1, -1, 0}); 26 ASSERT_FALSE(simplex.isEmpty()); 27 28 unsigned snapshot = simplex.getSnapshot(); 29 // (u - v) <= -1 30 simplex.addInequality({-1, 1, -1}); 31 ASSERT_TRUE(simplex.isEmpty()); 32 33 unsigned snapshot2 = simplex.getSnapshot(); 34 // (u - v) <= -3 35 simplex.addInequality({-1, 1, -3}); 36 ASSERT_TRUE(simplex.isEmpty()); 37 38 simplex.rollback(snapshot2); 39 ASSERT_TRUE(simplex.isEmpty()); 40 41 simplex.rollback(snapshot); 42 ASSERT_FALSE(simplex.isEmpty()); 43 } 44 45 /// Check that the set gets marked as empty when we add contradictory 46 /// constraints. 47 TEST(SimplexTest, addEquality_separate) { 48 Simplex simplex(1); 49 simplex.addInequality({1, -1}); // x >= 1. 50 ASSERT_FALSE(simplex.isEmpty()); 51 simplex.addEquality({1, 0}); // x == 0. 52 EXPECT_TRUE(simplex.isEmpty()); 53 } 54 55 void expectInequalityMakesSetEmpty(Simplex &simplex, ArrayRef<int64_t> coeffs, 56 bool expect) { 57 ASSERT_FALSE(simplex.isEmpty()); 58 unsigned snapshot = simplex.getSnapshot(); 59 simplex.addInequality(coeffs); 60 EXPECT_EQ(simplex.isEmpty(), expect); 61 simplex.rollback(snapshot); 62 } 63 64 TEST(SimplexTest, addInequality_rollback) { 65 Simplex simplex(3); 66 SmallVector<int64_t, 4> coeffs[]{{1, 0, 0, 0}, // u >= 0. 67 {-1, 0, 0, 0}, // u <= 0. 68 {1, -1, 1, 0}, // u - v + w >= 0. 69 {1, 1, -1, 0}}; // u + v - w >= 0. 70 // The above constraints force u = 0 and v = w. 71 // The constraints below violate v = w. 72 SmallVector<int64_t, 4> checkCoeffs[]{{0, 1, -1, -1}, // v - w >= 1. 73 {0, -1, 1, -1}}; // v - w <= -1. 74 75 for (int run = 0; run < 4; run++) { 76 unsigned snapshot = simplex.getSnapshot(); 77 78 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], false); 79 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], false); 80 81 for (int i = 0; i < 4; i++) 82 simplex.addInequality(coeffs[(run + i) % 4]); 83 84 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], true); 85 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], true); 86 87 simplex.rollback(snapshot); 88 EXPECT_EQ(simplex.getNumConstraints(), 0u); 89 90 expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], false); 91 expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], false); 92 } 93 } 94 95 Simplex simplexFromConstraints(unsigned nDim, 96 ArrayRef<SmallVector<int64_t, 8>> ineqs, 97 ArrayRef<SmallVector<int64_t, 8>> eqs) { 98 Simplex simplex(nDim); 99 for (const auto &ineq : ineqs) 100 simplex.addInequality(ineq); 101 for (const auto &eq : eqs) 102 simplex.addEquality(eq); 103 return simplex; 104 } 105 106 TEST(SimplexTest, isUnbounded) { 107 EXPECT_FALSE(simplexFromConstraints( 108 2, {{1, 1, 0}, {-1, -1, 0}, {1, -1, 5}, {-1, 1, -5}}, {}) 109 .isUnbounded()); 110 111 EXPECT_TRUE( 112 simplexFromConstraints(2, {{1, 1, 0}, {1, -1, 5}, {-1, 1, -5}}, {}) 113 .isUnbounded()); 114 115 EXPECT_TRUE( 116 simplexFromConstraints(2, {{-1, -1, 0}, {1, -1, 5}, {-1, 1, -5}}, {}) 117 .isUnbounded()); 118 119 EXPECT_TRUE(simplexFromConstraints(2, {}, {}).isUnbounded()); 120 121 EXPECT_FALSE(simplexFromConstraints(3, 122 { 123 {2, 0, 0, -1}, 124 {-2, 0, 0, 1}, 125 {0, 2, 0, -1}, 126 {0, -2, 0, 1}, 127 {0, 0, 2, -1}, 128 {0, 0, -2, 1}, 129 }, 130 {}) 131 .isUnbounded()); 132 133 EXPECT_TRUE(simplexFromConstraints(3, 134 { 135 {2, 0, 0, -1}, 136 {-2, 0, 0, 1}, 137 {0, 2, 0, -1}, 138 {0, -2, 0, 1}, 139 {0, 0, -2, 1}, 140 }, 141 {}) 142 .isUnbounded()); 143 144 EXPECT_TRUE(simplexFromConstraints(3, 145 { 146 {2, 0, 0, -1}, 147 {-2, 0, 0, 1}, 148 {0, 2, 0, -1}, 149 {0, -2, 0, 1}, 150 {0, 0, 2, -1}, 151 }, 152 {}) 153 .isUnbounded()); 154 155 // Bounded set with equalities. 156 EXPECT_FALSE(simplexFromConstraints(2, 157 {{1, 1, 1}, // x + y >= -1. 158 {-1, -1, 1}}, // x + y <= 1. 159 {{1, -1, 0}} // x = y. 160 ) 161 .isUnbounded()); 162 163 // Unbounded set with equalities. 164 EXPECT_TRUE(simplexFromConstraints(3, 165 {{1, 1, 1, 1}, // x + y + z >= -1. 166 {-1, -1, -1, 1}}, // x + y + z <= 1. 167 {{1, -1, -1, 0}} // x = y + z. 168 ) 169 .isUnbounded()); 170 171 // Rational empty set. 172 EXPECT_FALSE(simplexFromConstraints(3, 173 { 174 {2, 0, 0, -1}, 175 {-2, 0, 0, 1}, 176 {0, 2, 2, -1}, 177 {0, -2, -2, 1}, 178 {3, 3, 3, -4}, 179 }, 180 {}) 181 .isUnbounded()); 182 } 183 184 TEST(SimplexTest, getSamplePointIfIntegral) { 185 // Empty set. 186 EXPECT_FALSE(simplexFromConstraints(3, 187 { 188 {2, 0, 0, -1}, 189 {-2, 0, 0, 1}, 190 {0, 2, 2, -1}, 191 {0, -2, -2, 1}, 192 {3, 3, 3, -4}, 193 }, 194 {}) 195 .getSamplePointIfIntegral() 196 .hasValue()); 197 198 auto maybeSample = simplexFromConstraints(2, 199 {// x = y - 2. 200 {1, -1, 2}, 201 {-1, 1, -2}, 202 // x + y = 2. 203 {1, 1, -2}, 204 {-1, -1, 2}}, 205 {}) 206 .getSamplePointIfIntegral(); 207 208 EXPECT_TRUE(maybeSample.hasValue()); 209 EXPECT_THAT(*maybeSample, testing::ElementsAre(0, 2)); 210 211 auto maybeSample2 = simplexFromConstraints(2, 212 { 213 {1, 0, 0}, // x >= 0. 214 {-1, 0, 0}, // x <= 0. 215 }, 216 { 217 {0, 1, -2} // y = 2. 218 }) 219 .getSamplePointIfIntegral(); 220 EXPECT_TRUE(maybeSample2.hasValue()); 221 EXPECT_THAT(*maybeSample2, testing::ElementsAre(0, 2)); 222 223 EXPECT_FALSE(simplexFromConstraints(1, 224 {// 2x = 1. (no integer solutions) 225 {2, -1}, 226 {-2, +1}}, 227 {}) 228 .getSamplePointIfIntegral() 229 .hasValue()); 230 } 231 232 /// Some basic sanity checks involving zero or one variables. 233 TEST(SimplexTest, isMarkedRedundant_no_var_ge_zero) { 234 Simplex simplex(0); 235 simplex.addInequality({0}); // 0 >= 0. 236 237 simplex.detectRedundant(); 238 ASSERT_FALSE(simplex.isEmpty()); 239 EXPECT_TRUE(simplex.isMarkedRedundant(0)); 240 } 241 242 TEST(SimplexTest, isMarkedRedundant_no_var_eq) { 243 Simplex simplex(0); 244 simplex.addEquality({0}); // 0 == 0. 245 simplex.detectRedundant(); 246 ASSERT_FALSE(simplex.isEmpty()); 247 EXPECT_TRUE(simplex.isMarkedRedundant(0)); 248 } 249 250 TEST(SimplexTest, isMarkedRedundant_pos_var_eq) { 251 Simplex simplex(1); 252 simplex.addEquality({1, 0}); // x == 0. 253 254 simplex.detectRedundant(); 255 ASSERT_FALSE(simplex.isEmpty()); 256 EXPECT_FALSE(simplex.isMarkedRedundant(0)); 257 } 258 259 TEST(SimplexTest, isMarkedRedundant_zero_var_eq) { 260 Simplex simplex(1); 261 simplex.addEquality({0, 0}); // 0x == 0. 262 simplex.detectRedundant(); 263 ASSERT_FALSE(simplex.isEmpty()); 264 EXPECT_TRUE(simplex.isMarkedRedundant(0)); 265 } 266 267 TEST(SimplexTest, isMarkedRedundant_neg_var_eq) { 268 Simplex simplex(1); 269 simplex.addEquality({-1, 0}); // -x == 0. 270 simplex.detectRedundant(); 271 ASSERT_FALSE(simplex.isEmpty()); 272 EXPECT_FALSE(simplex.isMarkedRedundant(0)); 273 } 274 275 TEST(SimplexTest, isMarkedRedundant_pos_var_ge) { 276 Simplex simplex(1); 277 simplex.addInequality({1, 0}); // x >= 0. 278 simplex.detectRedundant(); 279 ASSERT_FALSE(simplex.isEmpty()); 280 EXPECT_FALSE(simplex.isMarkedRedundant(0)); 281 } 282 283 TEST(SimplexTest, isMarkedRedundant_zero_var_ge) { 284 Simplex simplex(1); 285 simplex.addInequality({0, 0}); // 0x >= 0. 286 simplex.detectRedundant(); 287 ASSERT_FALSE(simplex.isEmpty()); 288 EXPECT_TRUE(simplex.isMarkedRedundant(0)); 289 } 290 291 TEST(SimplexTest, isMarkedRedundant_neg_var_ge) { 292 Simplex simplex(1); 293 simplex.addInequality({-1, 0}); // x <= 0. 294 simplex.detectRedundant(); 295 ASSERT_FALSE(simplex.isEmpty()); 296 EXPECT_FALSE(simplex.isMarkedRedundant(0)); 297 } 298 299 /// None of the constraints are redundant. Slightly more complicated test 300 /// involving an equality. 301 TEST(SimplexTest, isMarkedRedundant_no_redundant) { 302 Simplex simplex(3); 303 304 simplex.addEquality({-1, 0, 1, 0}); // u = w. 305 simplex.addInequality({-1, 16, 0, 15}); // 15 - (u - 16v) >= 0. 306 simplex.addInequality({1, -16, 0, 0}); // (u - 16v) >= 0. 307 308 simplex.detectRedundant(); 309 ASSERT_FALSE(simplex.isEmpty()); 310 311 for (unsigned i = 0; i < simplex.getNumConstraints(); ++i) 312 EXPECT_FALSE(simplex.isMarkedRedundant(i)) << "i = " << i << "\n"; 313 } 314 315 TEST(SimplexTest, isMarkedRedundant_repeated_constraints) { 316 Simplex simplex(3); 317 318 // [4] to [7] are repeats of [0] to [3]. 319 simplex.addInequality({0, -1, 0, 1}); // [0]: y <= 1. 320 simplex.addInequality({-1, 0, 8, 7}); // [1]: 8z >= x - 7. 321 simplex.addInequality({1, 0, -8, 0}); // [2]: 8z <= x. 322 simplex.addInequality({0, 1, 0, 0}); // [3]: y >= 0. 323 simplex.addInequality({-1, 0, 8, 7}); // [4]: 8z >= 7 - x. 324 simplex.addInequality({1, 0, -8, 0}); // [5]: 8z <= x. 325 simplex.addInequality({0, 1, 0, 0}); // [6]: y >= 0. 326 simplex.addInequality({0, -1, 0, 1}); // [7]: y <= 1. 327 328 simplex.detectRedundant(); 329 ASSERT_FALSE(simplex.isEmpty()); 330 331 EXPECT_EQ(simplex.isMarkedRedundant(0), true); 332 EXPECT_EQ(simplex.isMarkedRedundant(1), true); 333 EXPECT_EQ(simplex.isMarkedRedundant(2), true); 334 EXPECT_EQ(simplex.isMarkedRedundant(3), true); 335 EXPECT_EQ(simplex.isMarkedRedundant(4), false); 336 EXPECT_EQ(simplex.isMarkedRedundant(5), false); 337 EXPECT_EQ(simplex.isMarkedRedundant(6), false); 338 EXPECT_EQ(simplex.isMarkedRedundant(7), false); 339 } 340 341 TEST(SimplexTest, isMarkedRedundant) { 342 Simplex simplex(3); 343 simplex.addInequality({0, -1, 0, 1}); // [0]: y <= 1. 344 simplex.addInequality({1, 0, 0, -1}); // [1]: x >= 1. 345 simplex.addInequality({-1, 0, 0, 2}); // [2]: x <= 2. 346 simplex.addInequality({-1, 0, 2, 7}); // [3]: 2z >= x - 7. 347 simplex.addInequality({1, 0, -2, 0}); // [4]: 2z <= x. 348 simplex.addInequality({0, 1, 0, 0}); // [5]: y >= 0. 349 simplex.addInequality({0, 1, -2, 1}); // [6]: y >= 2z - 1. 350 simplex.addInequality({-1, 1, 0, 1}); // [7]: y >= x - 1. 351 352 simplex.detectRedundant(); 353 ASSERT_FALSE(simplex.isEmpty()); 354 355 // [0], [1], [3], [4], [7] together imply [2], [5], [6] must hold. 356 // 357 // From [7], [0]: x <= y + 1 <= 2, so we have [2]. 358 // From [7], [1]: y >= x - 1 >= 0, so we have [5]. 359 // From [4], [7]: 2z - 1 <= x - 1 <= y, so we have [6]. 360 EXPECT_FALSE(simplex.isMarkedRedundant(0)); 361 EXPECT_FALSE(simplex.isMarkedRedundant(1)); 362 EXPECT_TRUE(simplex.isMarkedRedundant(2)); 363 EXPECT_FALSE(simplex.isMarkedRedundant(3)); 364 EXPECT_FALSE(simplex.isMarkedRedundant(4)); 365 EXPECT_TRUE(simplex.isMarkedRedundant(5)); 366 EXPECT_TRUE(simplex.isMarkedRedundant(6)); 367 EXPECT_FALSE(simplex.isMarkedRedundant(7)); 368 } 369 370 TEST(SimplexTest, isMarkedRedundantTiledLoopNestConstraints) { 371 Simplex simplex(3); // Variables are x, y, N. 372 simplex.addInequality({1, 0, 0, 0}); // [0]: x >= 0. 373 simplex.addInequality({-32, 0, 1, -1}); // [1]: 32x <= N - 1. 374 simplex.addInequality({0, 1, 0, 0}); // [2]: y >= 0. 375 simplex.addInequality({-32, 1, 0, 0}); // [3]: y >= 32x. 376 simplex.addInequality({32, -1, 0, 31}); // [4]: y <= 32x + 31. 377 simplex.addInequality({0, -1, 1, -1}); // [5]: y <= N - 1. 378 // [3] and [0] imply [2], as we have y >= 32x >= 0. 379 // [3] and [5] imply [1], as we have 32x <= y <= N - 1. 380 simplex.detectRedundant(); 381 EXPECT_FALSE(simplex.isMarkedRedundant(0)); 382 EXPECT_TRUE(simplex.isMarkedRedundant(1)); 383 EXPECT_TRUE(simplex.isMarkedRedundant(2)); 384 EXPECT_FALSE(simplex.isMarkedRedundant(3)); 385 EXPECT_FALSE(simplex.isMarkedRedundant(4)); 386 EXPECT_FALSE(simplex.isMarkedRedundant(5)); 387 } 388 389 TEST(Simplextest, pivotRedundantRegressionTest) { 390 Simplex simplex(2); 391 simplex.addInequality({-1, 0, -1}); // x <= -1. 392 unsigned snapshot = simplex.getSnapshot(); 393 394 simplex.addInequality({-1, 0, -2}); // x <= -2. 395 simplex.addInequality({-3, 0, -6}); 396 397 // This first marks x <= -1 as redundant. Then it performs some more pivots 398 // to check if the other constraints are redundant. Pivot must update the 399 // non-redundant rows as well, otherwise these pivots result in an incorrect 400 // tableau state. In particular, after the rollback below, some rows that are 401 // NOT marked redundant will have an incorrect state. 402 simplex.detectRedundant(); 403 404 // After the rollback, the only remaining constraint is x <= -1. 405 // The maximum value of x should be -1. 406 simplex.rollback(snapshot); 407 Optional<Fraction> maxX = 408 simplex.computeOptimum(Simplex::Direction::Up, {1, 0, 0}); 409 EXPECT_TRUE(maxX.hasValue() && *maxX == Fraction(-1, 1)); 410 } 411 412 TEST(SimplexTest, addInequality_already_redundant) { 413 Simplex simplex(1); 414 simplex.addInequality({1, -1}); // x >= 1. 415 simplex.addInequality({1, 0}); // x >= 0. 416 simplex.detectRedundant(); 417 ASSERT_FALSE(simplex.isEmpty()); 418 EXPECT_FALSE(simplex.isMarkedRedundant(0)); 419 EXPECT_TRUE(simplex.isMarkedRedundant(1)); 420 } 421 422 TEST(SimplexTest, appendVariable) { 423 Simplex simplex(1); 424 425 unsigned snapshot1 = simplex.getSnapshot(); 426 simplex.appendVariable(); 427 simplex.appendVariable(0); 428 EXPECT_EQ(simplex.getNumVariables(), 2u); 429 430 int64_t yMin = 2, yMax = 5; 431 simplex.addInequality({0, 1, -yMin}); // y >= 2. 432 simplex.addInequality({0, -1, yMax}); // y <= 5. 433 434 unsigned snapshot2 = simplex.getSnapshot(); 435 simplex.appendVariable(2); 436 EXPECT_EQ(simplex.getNumVariables(), 4u); 437 simplex.rollback(snapshot2); 438 439 EXPECT_EQ(simplex.getNumVariables(), 2u); 440 EXPECT_EQ(simplex.getNumConstraints(), 2u); 441 EXPECT_EQ(simplex.computeIntegerBounds({0, 1, 0}), 442 std::make_pair(yMin, yMax)); 443 444 simplex.rollback(snapshot1); 445 EXPECT_EQ(simplex.getNumVariables(), 1u); 446 EXPECT_EQ(simplex.getNumConstraints(), 0u); 447 } 448 449 TEST(SimplexTest, isRedundantInequality) { 450 Simplex simplex(2); 451 simplex.addInequality({0, -1, 2}); // y <= 2. 452 simplex.addInequality({1, 0, 0}); // x >= 0. 453 simplex.addEquality({-1, 1, 0}); // y = x. 454 455 EXPECT_TRUE(simplex.isRedundantInequality({-1, 0, 2})); // x <= 2. 456 EXPECT_TRUE(simplex.isRedundantInequality({0, 1, 0})); // y >= 0. 457 458 EXPECT_FALSE(simplex.isRedundantInequality({-1, 0, -1})); // x <= -1. 459 EXPECT_FALSE(simplex.isRedundantInequality({0, 1, -2})); // y >= 2. 460 EXPECT_FALSE(simplex.isRedundantInequality({0, 1, -1})); // y >= 1. 461 } 462 463 TEST(SimplexTest, isRedundantEquality) { 464 Simplex simplex(2); 465 simplex.addInequality({0, -1, 2}); // y <= 2. 466 simplex.addInequality({1, 0, 0}); // x >= 0. 467 simplex.addEquality({-1, 1, 0}); // y = x. 468 469 EXPECT_TRUE(simplex.isRedundantEquality({-1, 1, 0})); // y = x. 470 EXPECT_TRUE(simplex.isRedundantEquality({1, -1, 0})); // x = y. 471 472 EXPECT_FALSE(simplex.isRedundantEquality({0, 1, -1})); // y = 1. 473 474 simplex.addEquality({0, -1, 2}); // y = 2. 475 476 EXPECT_TRUE(simplex.isRedundantEquality({-1, 0, 2})); // x = 2. 477 } 478 479 static IntegerPolyhedron parsePoly(StringRef str, MLIRContext *context) { 480 FailureOr<IntegerPolyhedron> poly = parseIntegerSetToFAC(str, context); 481 482 EXPECT_TRUE(succeeded(poly)); 483 484 return *poly; 485 } 486 487 TEST(SimplexTest, IsRationalSubsetOf) { 488 489 MLIRContext context; 490 491 IntegerPolyhedron univ = parsePoly("(x) : ()", &context); 492 IntegerPolyhedron empty = 493 parsePoly("(x) : (x + 0 >= 0, -x - 1 >= 0)", &context); 494 IntegerPolyhedron s1 = parsePoly("(x) : ( x >= 0, -x + 4 >= 0)", &context); 495 IntegerPolyhedron s2 = parsePoly("(x) : (x - 1 >= 0, -x + 3 >= 0)", &context); 496 497 Simplex simUniv(univ); 498 Simplex simEmpty(empty); 499 Simplex sim1(s1); 500 Simplex sim2(s2); 501 502 EXPECT_TRUE(simUniv.isRationalSubsetOf(univ)); 503 EXPECT_TRUE(simEmpty.isRationalSubsetOf(empty)); 504 EXPECT_TRUE(sim1.isRationalSubsetOf(s1)); 505 EXPECT_TRUE(sim2.isRationalSubsetOf(s2)); 506 507 EXPECT_TRUE(simEmpty.isRationalSubsetOf(univ)); 508 EXPECT_TRUE(simEmpty.isRationalSubsetOf(s1)); 509 EXPECT_TRUE(simEmpty.isRationalSubsetOf(s2)); 510 EXPECT_TRUE(simEmpty.isRationalSubsetOf(empty)); 511 512 EXPECT_TRUE(simUniv.isRationalSubsetOf(univ)); 513 EXPECT_FALSE(simUniv.isRationalSubsetOf(s1)); 514 EXPECT_FALSE(simUniv.isRationalSubsetOf(s2)); 515 EXPECT_FALSE(simUniv.isRationalSubsetOf(empty)); 516 517 EXPECT_TRUE(sim1.isRationalSubsetOf(univ)); 518 EXPECT_TRUE(sim1.isRationalSubsetOf(s1)); 519 EXPECT_FALSE(sim1.isRationalSubsetOf(s2)); 520 EXPECT_FALSE(sim1.isRationalSubsetOf(empty)); 521 522 EXPECT_TRUE(sim2.isRationalSubsetOf(univ)); 523 EXPECT_TRUE(sim2.isRationalSubsetOf(s1)); 524 EXPECT_TRUE(sim2.isRationalSubsetOf(s2)); 525 EXPECT_FALSE(sim2.isRationalSubsetOf(empty)); 526 } 527 528 } // namespace mlir 529