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 199