154 lines · cpp
1//===--- ConstraintSystemTests.cpp ----------------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Analysis/ConstraintSystem.h"10#include "gtest/gtest.h"11 12using namespace llvm;13 14namespace {15 16TEST(ConstraintSolverTest, TestSolutionChecks) {17 {18 ConstraintSystem CS;19 // x + y <= 10, x >= 5, y >= 6, x <= 10, y <= 1020 CS.addVariableRow({10, 1, 1});21 CS.addVariableRow({-5, -1, 0});22 CS.addVariableRow({-6, 0, -1});23 CS.addVariableRow({10, 1, 0});24 CS.addVariableRow({10, 0, 1});25 26 EXPECT_FALSE(CS.mayHaveSolution());27 }28 29 {30 ConstraintSystem CS;31 // x + y <= 10, x >= 2, y >= 3, x <= 10, y <= 1032 CS.addVariableRow({10, 1, 1});33 CS.addVariableRow({-2, -1, 0});34 CS.addVariableRow({-3, 0, -1});35 CS.addVariableRow({10, 1, 0});36 CS.addVariableRow({10, 0, 1});37 38 EXPECT_TRUE(CS.mayHaveSolution());39 }40 41 {42 ConstraintSystem CS;43 // x + y <= 10, x >= 10, y >= 10; does not have a solution.44 CS.addVariableRow({10, 1, 1});45 CS.addVariableRow({-10, -1, 0});46 CS.addVariableRow({-10, 0, -1});47 48 EXPECT_FALSE(CS.mayHaveSolution());49 }50 51 {52 ConstraintSystem CS;53 // x + y >= 20, 10 >= x, 10 >= y; does HAVE a solution.54 CS.addVariableRow({-20, -1, -1});55 CS.addVariableRow({-10, -1, 0});56 CS.addVariableRow({-10, 0, -1});57 58 EXPECT_TRUE(CS.mayHaveSolution());59 }60 61 {62 ConstraintSystem CS;63 64 // 2x + y + 3z <= 10, 2x + y >= 10, y >= 165 CS.addVariableRow({10, 2, 1, 3});66 CS.addVariableRow({-10, -2, -1, 0});67 CS.addVariableRow({-1, 0, 0, -1});68 69 EXPECT_FALSE(CS.mayHaveSolution());70 }71 72 {73 ConstraintSystem CS;74 75 // 2x + y + 3z <= 10, 2x + y >= 1076 CS.addVariableRow({10, 2, 1, 3});77 CS.addVariableRow({-10, -2, -1, 0});78 79 EXPECT_TRUE(CS.mayHaveSolution());80 }81}82 83TEST(ConstraintSolverTest, IsConditionImplied) {84 {85 // For the test below, we assume we know86 // x <= 5 && y <= 387 ConstraintSystem CS;88 CS.addVariableRow({5, 1, 0});89 CS.addVariableRow({3, 0, 1});90 91 // x + y <= 6 does not hold.92 EXPECT_FALSE(CS.isConditionImplied({6, 1, 1}));93 // x + y <= 7 does not hold.94 EXPECT_FALSE(CS.isConditionImplied({7, 1, 1}));95 // x + y <= 8 does hold.96 EXPECT_TRUE(CS.isConditionImplied({8, 1, 1}));97 98 // 2 * x + y <= 12 does hold.99 EXPECT_FALSE(CS.isConditionImplied({12, 2, 1}));100 // 2 * x + y <= 13 does hold.101 EXPECT_TRUE(CS.isConditionImplied({13, 2, 1}));102 103 // x + y <= 12 does hold.104 EXPECT_FALSE(CS.isConditionImplied({12, 2, 1}));105 // 2 * x + y <= 13 does hold.106 EXPECT_TRUE(CS.isConditionImplied({13, 2, 1}));107 108 // x <= y == x - y <= 0 does not hold.109 EXPECT_FALSE(CS.isConditionImplied({0, 1, -1}));110 // y <= x == -x + y <= 0 does not hold.111 EXPECT_FALSE(CS.isConditionImplied({0, -1, 1}));112 }113 114 {115 // For the test below, we assume we know116 // x + 1 <= y + 1 == x - y <= 0117 ConstraintSystem CS;118 CS.addVariableRow({0, 1, -1});119 120 // x <= y == x - y <= 0 does hold.121 EXPECT_TRUE(CS.isConditionImplied({0, 1, -1}));122 // y <= x == -x + y <= 0 does not hold.123 EXPECT_FALSE(CS.isConditionImplied({0, -1, 1}));124 125 // x <= y + 10 == x - y <= 10 does hold.126 EXPECT_TRUE(CS.isConditionImplied({10, 1, -1}));127 // x + 10 <= y == x - y <= -10 does NOT hold.128 EXPECT_FALSE(CS.isConditionImplied({-10, 1, -1}));129 }130 131 {132 // For the test below, we assume we know133 // x <= y == x - y <= 0134 // y <= z == y - x <= 0135 ConstraintSystem CS;136 CS.addVariableRow({0, 1, -1, 0});137 CS.addVariableRow({0, 0, 1, -1});138 139 // z <= y == -y + z <= 0 does not hold.140 EXPECT_FALSE(CS.isConditionImplied({0, 0, -1, 1}));141 // x <= z == x - z <= 0 does hold.142 EXPECT_TRUE(CS.isConditionImplied({0, 1, 0, -1}));143 }144}145 146TEST(ConstraintSolverTest, IsConditionImpliedOverflow) {147 ConstraintSystem CS;148 // Make sure isConditionImplied returns false when there is an overflow.149 int64_t Limit = std::numeric_limits<int64_t>::max();150 CS.addVariableRow({Limit - 1, Limit - 2, Limit - 3});151 EXPECT_FALSE(CS.isConditionImplied({Limit - 1, Limit - 2, Limit - 3}));152}153} // namespace154