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 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 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 LV1 in undefined value. 65 ValueLatticeElement LV2; 66 LV2.mergeIn(LV1, M.getDataLayout()); 67 EXPECT_TRUE(LV1.isConstantRange()); 68 EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U); 69 EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U); 70 EXPECT_TRUE(LV2.isConstantRange()); 71 EXPECT_EQ(LV2.getConstantRange().getLower().getLimitedValue(), 1U); 72 EXPECT_EQ(LV2.getConstantRange().getUpper().getLimitedValue(), 100U); 73 74 // Merge with overdefined. 75 LV1.mergeIn(ValueLatticeElement::getOverdefined(), M.getDataLayout()); 76 EXPECT_TRUE(LV1.isOverdefined()); 77 } 78 79 TEST_F(ValueLatticeTest, getCompareIntegers) { 80 auto *I32Ty = IntegerType::get(Context, 32); 81 auto *I1Ty = IntegerType::get(Context, 1); 82 auto *C1 = ConstantInt::get(I32Ty, 1); 83 auto LV1 = ValueLatticeElement::get(C1); 84 85 // Check getCompare for equal integer constants. 86 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV1)->isOneValue()); 87 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV1)->isOneValue()); 88 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV1)->isOneValue()); 89 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV1)->isZeroValue()); 90 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV1)->isZeroValue()); 91 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV1)->isZeroValue()); 92 93 auto LV2 = 94 ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)}); 95 // Check getCompare with distinct integer ranges. 96 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV2)->isOneValue()); 97 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV2)->isOneValue()); 98 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV2)->isOneValue()); 99 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV2)->isZeroValue()); 100 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV2)->isZeroValue()); 101 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV2)->isZeroValue()); 102 103 auto LV3 = 104 ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 19, true)}); 105 // Check getCompare with a subset integer ranges. 106 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SLT, I1Ty, LV3), nullptr); 107 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SLE, I1Ty, LV3), nullptr); 108 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_NE, I1Ty, LV3), nullptr); 109 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_EQ, I1Ty, LV3), nullptr); 110 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SGE, I1Ty, LV3), nullptr); 111 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SGT, I1Ty, LV3), nullptr); 112 113 auto LV4 = 114 ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 25, true)}); 115 // Check getCompare with overlapping integer ranges. 116 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SLT, I1Ty, LV4), nullptr); 117 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SLE, I1Ty, LV4), nullptr); 118 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_NE, I1Ty, LV4), nullptr); 119 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_EQ, I1Ty, LV4), nullptr); 120 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SGE, I1Ty, LV4), nullptr); 121 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SGT, I1Ty, LV4), nullptr); 122 } 123 124 TEST_F(ValueLatticeTest, getCompareFloat) { 125 auto *FloatTy = IntegerType::getFloatTy(Context); 126 auto *I1Ty = IntegerType::get(Context, 1); 127 auto *C1 = ConstantFP::get(FloatTy, 1.0); 128 auto LV1 = ValueLatticeElement::get(C1); 129 auto LV2 = ValueLatticeElement::get(C1); 130 131 // Check getCompare for equal floating point constants. 132 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV2)->isOneValue()); 133 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV2)->isOneValue()); 134 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV2)->isOneValue()); 135 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV2)->isZeroValue()); 136 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV2)->isZeroValue()); 137 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV2)->isZeroValue()); 138 139 LV1.mergeIn(ValueLatticeElement::get(ConstantFP::get(FloatTy, 2.2)), 140 M.getDataLayout()); 141 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV2), nullptr); 142 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV2), nullptr); 143 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV2), nullptr); 144 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV2), nullptr); 145 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV2), nullptr); 146 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV2), nullptr); 147 } 148 149 TEST_F(ValueLatticeTest, getCompareUndef) { 150 auto *I32Ty = IntegerType::get(Context, 32); 151 auto *I1Ty = IntegerType::get(Context, 1); 152 153 auto LV1 = ValueLatticeElement::get(UndefValue::get(I32Ty)); 154 auto LV2 = 155 ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)}); 156 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV2))); 157 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV2))); 158 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV2))); 159 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV2))); 160 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV2))); 161 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV2))); 162 163 auto *FloatTy = IntegerType::getFloatTy(Context); 164 auto LV3 = ValueLatticeElement::get(ConstantFP::get(FloatTy, 1.0)); 165 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV3))); 166 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV3))); 167 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV3))); 168 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV3))); 169 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV3))); 170 EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV3))); 171 } 172 173 } // end anonymous namespace 174 } // end namespace llvm 175