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