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 
ValueLatticeTest()29   ValueLatticeTest() : M("", Context) {}
30 };
31 
TEST_F(ValueLatticeTest,ValueLatticeGetters)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 
TEST_F(ValueLatticeTest,MergeIn)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 
TEST_F(ValueLatticeTest,getCompareIntegers)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 
TEST_F(ValueLatticeTest,getCompareFloat)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 
TEST_F(ValueLatticeTest,getCompareUndef)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