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   Module M;
  27
  28   ValueLatticeTest() : M("", Context) {}
  29 };
  30
  31 TEST_F(ValueLatticeTest, ValueLatticeGetters) {
  32   auto I32Ty = IntegerType::get(Context, 32);
  33   auto *C1 = ConstantInt::get(I32Ty, 1);
  34
  35   EXPECT_TRUE(ValueLatticeElement::get(C1).isConstantRange());
  36   EXPECT_TRUE(
  37       ValueLatticeElement::getRange({C1->getValue()}).isConstantRange());
  38   EXPECT_TRUE(ValueLatticeElement::getOverdefined().isOverdefined());
  39
  40   auto FloatTy = Type::getFloatTy(Context);
  41   auto *C2 = ConstantFP::get(FloatTy, 1.1);
  42   EXPECT_TRUE(ValueLatticeElement::get(C2).isConstant());
  43   EXPECT_TRUE(ValueLatticeElement::getNot(C2).isNotConstant());
  44 }
  45
  46 TEST_F(ValueLatticeTest, MergeIn) {
  47   auto I32Ty = IntegerType::get(Context, 32);
  48   auto *C1 = ConstantInt::get(I32Ty, 1);
  49
  50   // Merge to lattice values with equal integer constant.
  51   auto LV1 = ValueLatticeElement::get(C1);
  52   EXPECT_FALSE(LV1.mergeIn(ValueLatticeElement::get(C1), M.getDataLayout()));
  53   EXPECT_TRUE(LV1.isConstantRange());
  54   EXPECT_EQ(LV1.asConstantInteger().getValue().getLimitedValue(), 1U);
  55
  56   // Merge LV1 with different integer constant.
  57   EXPECT_TRUE(LV1.mergeIn(ValueLatticeElement::get(ConstantInt::get(I32Ty, 99)),
  58                           M.getDataLayout()));
  59   EXPECT_TRUE(LV1.isConstantRange());
  60   EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U);
  61   EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U);
  62
  63   // Merge constant range with same constant range.
  64   EXPECT_FALSE(LV1.mergeIn(LV1, M.getDataLayout()));
  65   EXPECT_TRUE(LV1.isConstantRange());
  66   EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U);
  67   EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U);
  68
  69   // Merge LV1 in undefined value.
  70   ValueLatticeElement LV2;
  71   EXPECT_TRUE(LV2.mergeIn(LV1, M.getDataLayout()));
  72   EXPECT_TRUE(LV1.isConstantRange());
  73   EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U);
  74   EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U);
  75   EXPECT_TRUE(LV2.isConstantRange());
  76   EXPECT_EQ(LV2.getConstantRange().getLower().getLimitedValue(), 1U);
  77   EXPECT_EQ(LV2.getConstantRange().getUpper().getLimitedValue(), 100U);
  78
  79   // Merge LV1 with overdefined.
  80   EXPECT_TRUE(
  81       LV1.mergeIn(ValueLatticeElement::getOverdefined(), M.getDataLayout()));
  82   EXPECT_TRUE(LV1.isOverdefined());
  83
  84   // Merge overdefined with overdefined.
  85   EXPECT_FALSE(
  86       LV1.mergeIn(ValueLatticeElement::getOverdefined(), M.getDataLayout()));
  87   EXPECT_TRUE(LV1.isOverdefined());
  88 }
  89
  90 TEST_F(ValueLatticeTest, getCompareIntegers) {
  91   auto *I32Ty = IntegerType::get(Context, 32);
  92   auto *I1Ty = IntegerType::get(Context, 1);
  93   auto *C1 = ConstantInt::get(I32Ty, 1);
  94   auto LV1 = ValueLatticeElement::get(C1);
  95
  96   // Check getCompare for equal integer constants.
  97   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV1)->isOneValue());
  98   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV1)->isOneValue());
  99   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV1)->isOneValue());
 100   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV1)->isZeroValue());
 101   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV1)->isZeroValue());
 102   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV1)->isZeroValue());
 103
 104   auto LV2 =
 105       ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)});
 106   // Check getCompare with distinct integer ranges.
 107   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV2)->isOneValue());
 108   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV2)->isOneValue());
 109   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV2)->isOneValue());
 110   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV2)->isZeroValue());
 111   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV2)->isZeroValue());
 112   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV2)->isZeroValue());
 113
 114   auto LV3 =
 115       ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 19, true)});
 116   // Check getCompare with a subset integer ranges.
 117   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SLT, I1Ty, LV3), nullptr);
 118   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SLE, I1Ty, LV3), nullptr);
 119   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_NE, I1Ty, LV3), nullptr);
 120   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_EQ, I1Ty, LV3), nullptr);
 121   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SGE, I1Ty, LV3), nullptr);
 122   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SGT, I1Ty, LV3), nullptr);
 123
 124   auto LV4 =
 125       ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 25, true)});
 126   // Check getCompare with overlapping integer ranges.
 127   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SLT, I1Ty, LV4), nullptr);
 128   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SLE, I1Ty, LV4), nullptr);
 129   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_NE, I1Ty, LV4), nullptr);
 130   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_EQ, I1Ty, LV4), nullptr);
 131   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SGE, I1Ty, LV4), nullptr);
 132   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SGT, I1Ty, LV4), nullptr);
 133 }
 134
 135 TEST_F(ValueLatticeTest, getCompareFloat) {
 136   auto *FloatTy = IntegerType::getFloatTy(Context);
 137   auto *I1Ty = IntegerType::get(Context, 1);
 138   auto *C1 = ConstantFP::get(FloatTy, 1.0);
 139   auto LV1 = ValueLatticeElement::get(C1);
 140   auto LV2 = ValueLatticeElement::get(C1);
 141
 142   // Check getCompare for equal floating point constants.
 143   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV2)->isOneValue());
 144   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV2)->isOneValue());
 145   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV2)->isOneValue());
 146   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV2)->isZeroValue());
 147   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV2)->isZeroValue());
 148   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV2)->isZeroValue());
 149
 150   EXPECT_TRUE(
 151       LV1.mergeIn(ValueLatticeElement::get(ConstantFP::get(FloatTy, 2.2)),
 152                   M.getDataLayout()));
 153   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV2), nullptr);
 154   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV2), nullptr);
 155   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV2), nullptr);
 156   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV2), nullptr);
 157   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV2), nullptr);
 158   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV2), nullptr);
 159 }
 160
 161 TEST_F(ValueLatticeTest, getCompareUndef) {
 162   auto *I32Ty = IntegerType::get(Context, 32);
 163   auto *I1Ty = IntegerType::get(Context, 1);
 164
 165   auto LV1 = ValueLatticeElement::get(UndefValue::get(I32Ty));
 166   auto LV2 =
 167       ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)});
 168   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV2)));
 169   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV2)));
 170   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV2)));
 171   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV2)));
 172   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV2)));
 173   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV2)));
 174
 175   auto *FloatTy = IntegerType::getFloatTy(Context);
 176   auto LV3 = ValueLatticeElement::get(ConstantFP::get(FloatTy, 1.0));
 177   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV3)));
 178   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV3)));
 179   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV3)));
 180   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV3)));
 181   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV3)));
 182   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV3)));
 183 }
 184
 185 } // end anonymous namespace
 186 } // end namespace llvm