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