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