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 187