llvm/unittests/Analysis/ConstraintSystemTest.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Analysis/ConstraintSystem.h"
  10 #include "gtest/gtest.h"
  11
  12 using namespace llvm;
  13
  14 namespace {
  15
  16 TEST(ConstraintSolverTest, TestSolutionChecks) {
  17   {
  18     ConstraintSystem CS;
  19     // x + y <= 10, x >= 5, y >= 6, x <= 10, y <= 10
  20     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 <= 10
  32     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 >= 1
  65     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 >= 10
  76     CS.addVariableRow({10, 2, 1, 3});
  77     CS.addVariableRow({-10, -2, -1, 0});
  78
  79     EXPECT_TRUE(CS.mayHaveSolution());
  80   }
  81 }
  82
  83 TEST(ConstraintSolverTest, IsConditionImplied) {
  84   {
  85     // For the test below, we assume we know
  86     // x <= 5 && y <= 3
  87     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 know
 116     // x + 1 <= y + 1 == x - y <= 0
 117     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 know
 133     // x <= y == x - y <= 0
 134     // y <= z == y - x <= 0
 135     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
 146 TEST(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 } // namespace