llvm/unittests/Analysis/ValueLatticeTest.cpp

   1 //===- ValueLatticeTest.cpp - ScalarEvolution unit tests --------------===//
   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/ValueLattice.h"
  10 #include "llvm/ADT/SmallVector.h"
  11 #include "llvm/IR/ConstantRange.h"
  12 #include "llvm/IR/Constants.h"
  13 #include "llvm/IR/IRBuilder.h"
  14 #include "llvm/IR/LLVMContext.h"
  15 #include "llvm/IR/Module.h"
  16 #include "gtest/gtest.h"
  17
  18 namespace llvm {
  19 namespace {
  20
  21 // We use this fixture to ensure that we clean up ScalarEvolution before
  22 // deleting the PassManager.
  23 class ValueLatticeTest : public testing::Test {
  24 protected:
  25   LLVMContext Context;
  26   DataLayout DL = DataLayout("");
  27 };
  28
  29 TEST_F(ValueLatticeTest, ValueLatticeGetters) {
  30   auto I32Ty = IntegerType::get(Context, 32);
  31   auto *C1 = ConstantInt::get(I32Ty, 1);
  32
  33   EXPECT_TRUE(ValueLatticeElement::get(C1).isConstantRange());
  34   EXPECT_TRUE(
  35       ValueLatticeElement::getRange({C1->getValue()}).isConstantRange());
  36   EXPECT_TRUE(ValueLatticeElement::getOverdefined().isOverdefined());
  37
  38   auto FloatTy = Type::getFloatTy(Context);
  39   auto *C2 = ConstantFP::get(FloatTy, 1.1);
  40   EXPECT_TRUE(ValueLatticeElement::get(C2).isConstant());
  41   EXPECT_TRUE(ValueLatticeElement::getNot(C2).isNotConstant());
  42 }
  43
  44 TEST_F(ValueLatticeTest, MarkConstantRange) {
  45   auto LV1 =
  46       ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)});
  47
  48   // Test markConstantRange() with an equal range.
  49   EXPECT_FALSE(
  50       LV1.markConstantRange({APInt(32, 10, true), APInt(32, 20, true)}));
  51
  52   // Test markConstantRange() with supersets of existing range.
  53   EXPECT_TRUE(LV1.markConstantRange({APInt(32, 5, true), APInt(32, 20, true)}));
  54   EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 5U);
  55   EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 20U);
  56   EXPECT_TRUE(LV1.markConstantRange({APInt(32, 5, true), APInt(32, 23, true)}));
  57   EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 5U);
  58   EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 23U);
  59 }
  60
  61 TEST_F(ValueLatticeTest, MergeIn) {
  62   auto I32Ty = IntegerType::get(Context, 32);
  63   auto *C1 = ConstantInt::get(I32Ty, 1);
  64
  65   // Merge to lattice values with equal integer constant.
  66   auto LV1 = ValueLatticeElement::get(C1);
  67   EXPECT_FALSE(LV1.mergeIn(ValueLatticeElement::get(C1)));
  68   EXPECT_TRUE(LV1.isConstantRange());
  69   EXPECT_EQ(LV1.asConstantInteger()->getLimitedValue(), 1U);
  70
  71   // Merge LV1 with different integer constant.
  72   EXPECT_TRUE(
  73       LV1.mergeIn(ValueLatticeElement::get(ConstantInt::get(I32Ty, 99))));
  74   EXPECT_TRUE(LV1.isConstantRange());
  75   EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U);
  76   EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U);
  77
  78   // Merge constant range with same constant range.
  79   EXPECT_FALSE(LV1.mergeIn(LV1));
  80   EXPECT_TRUE(LV1.isConstantRange());
  81   EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U);
  82   EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U);
  83
  84   // Merge LV1 in undefined value.
  85   ValueLatticeElement LV2;
  86   EXPECT_TRUE(LV2.mergeIn(LV1));
  87   EXPECT_TRUE(LV1.isConstantRange());
  88   EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U);
  89   EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U);
  90   EXPECT_TRUE(LV2.isConstantRange());
  91   EXPECT_EQ(LV2.getConstantRange().getLower().getLimitedValue(), 1U);
  92   EXPECT_EQ(LV2.getConstantRange().getUpper().getLimitedValue(), 100U);
  93
  94   // Merge LV1 with overdefined.
  95   EXPECT_TRUE(LV1.mergeIn(ValueLatticeElement::getOverdefined()));
  96   EXPECT_TRUE(LV1.isOverdefined());
  97
  98   // Merge overdefined with overdefined.
  99   EXPECT_FALSE(LV1.mergeIn(ValueLatticeElement::getOverdefined()));
 100   EXPECT_TRUE(LV1.isOverdefined());
 101 }
 102
 103 TEST_F(ValueLatticeTest, getCompareIntegers) {
 104   auto *I32Ty = IntegerType::get(Context, 32);
 105   auto *I1Ty = IntegerType::get(Context, 1);
 106   auto *C1 = ConstantInt::get(I32Ty, 1);
 107   auto LV1 = ValueLatticeElement::get(C1);
 108
 109   // Check getCompare for equal integer constants.
 110   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV1, DL)->isOneValue());
 111   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV1, DL)->isOneValue());
 112   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV1, DL)->isOneValue());
 113   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV1, DL)->isZeroValue());
 114   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV1, DL)->isZeroValue());
 115   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV1, DL)->isZeroValue());
 116
 117   auto LV2 =
 118       ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)});
 119   // Check getCompare with distinct integer ranges.
 120   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV2, DL)->isOneValue());
 121   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV2, DL)->isOneValue());
 122   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV2, DL)->isOneValue());
 123   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV2, DL)->isZeroValue());
 124   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV2, DL)->isZeroValue());
 125   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV2, DL)->isZeroValue());
 126
 127   auto LV3 =
 128       ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 19, true)});
 129   // Check getCompare with a subset integer ranges.
 130   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SLT, I1Ty, LV3, DL), nullptr);
 131   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SLE, I1Ty, LV3, DL), nullptr);
 132   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_NE, I1Ty, LV3, DL), nullptr);
 133   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_EQ, I1Ty, LV3, DL), nullptr);
 134   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SGE, I1Ty, LV3, DL), nullptr);
 135   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SGT, I1Ty, LV3, DL), nullptr);
 136
 137   auto LV4 =
 138       ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 25, true)});
 139   // Check getCompare with overlapping integer ranges.
 140   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SLT, I1Ty, LV4, DL), nullptr);
 141   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SLE, I1Ty, LV4, DL), nullptr);
 142   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_NE, I1Ty, LV4, DL), nullptr);
 143   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_EQ, I1Ty, LV4, DL), nullptr);
 144   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SGE, I1Ty, LV4, DL), nullptr);
 145   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SGT, I1Ty, LV4, DL), nullptr);
 146 }
 147
 148 TEST_F(ValueLatticeTest, getCompareFloat) {
 149   auto *FloatTy = IntegerType::getFloatTy(Context);
 150   auto *I1Ty = IntegerType::get(Context, 1);
 151   auto *C1 = ConstantFP::get(FloatTy, 1.0);
 152   auto LV1 = ValueLatticeElement::get(C1);
 153   auto LV2 = ValueLatticeElement::get(C1);
 154
 155   // Check getCompare for equal floating point constants.
 156   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV2, DL)->isOneValue());
 157   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV2, DL)->isOneValue());
 158   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV2, DL)->isOneValue());
 159   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV2, DL)->isZeroValue());
 160   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV2, DL)->isZeroValue());
 161   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV2, DL)->isZeroValue());
 162
 163   EXPECT_TRUE(
 164       LV1.mergeIn(ValueLatticeElement::get(ConstantFP::get(FloatTy, 2.2))));
 165   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV2, DL), nullptr);
 166   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV2, DL), nullptr);
 167   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV2, DL), nullptr);
 168   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV2, DL), nullptr);
 169   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV2, DL), nullptr);
 170   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV2, DL), nullptr);
 171 }
 172
 173 TEST_F(ValueLatticeTest, getCompareUndef) {
 174   auto *I32Ty = IntegerType::get(Context, 32);
 175   auto *I1Ty = IntegerType::get(Context, 1);
 176
 177   // TODO: These results can be improved.
 178   auto LV1 = ValueLatticeElement::get(UndefValue::get(I32Ty));
 179   auto LV2 =
 180       ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)});
 181   EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV2, DL), nullptr);
 182   EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV2, DL), nullptr);
 183   EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV2, DL), nullptr);
 184   EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV2, DL), nullptr);
 185   EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV2, DL), nullptr);
 186   EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV2, DL), nullptr);
 187
 188   auto *FloatTy = IntegerType::getFloatTy(Context);
 189   auto LV3 = ValueLatticeElement::get(ConstantFP::get(FloatTy, 1.0));
 190   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV3, DL), nullptr);
 191   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV3, DL), nullptr);
 192   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV3, DL), nullptr);
 193   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV3, DL), nullptr);
 194   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV3, DL), nullptr);
 195   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV3, DL), nullptr);
 196 }
 197
 198 } // end anonymous namespace
 199 } // end namespace llvm