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