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 };
27 
TEST_F(ValueLatticeTest,ValueLatticeGetters)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 
TEST_F(ValueLatticeTest,MarkConstantRange)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 
TEST_F(ValueLatticeTest,MergeIn)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().getValue().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 
TEST_F(ValueLatticeTest,getCompareIntegers)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)->isOneValue());
110   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV1)->isOneValue());
111   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV1)->isOneValue());
112   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV1)->isZeroValue());
113   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV1)->isZeroValue());
114   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV1)->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)->isOneValue());
120   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV2)->isOneValue());
121   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV2)->isOneValue());
122   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV2)->isZeroValue());
123   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV2)->isZeroValue());
124   EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV2)->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), nullptr);
130   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SLE, I1Ty, LV3), nullptr);
131   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_NE, I1Ty, LV3), nullptr);
132   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_EQ, I1Ty, LV3), nullptr);
133   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SGE, I1Ty, LV3), nullptr);
134   EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SGT, I1Ty, LV3), 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), nullptr);
140   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SLE, I1Ty, LV4), nullptr);
141   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_NE, I1Ty, LV4), nullptr);
142   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_EQ, I1Ty, LV4), nullptr);
143   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SGE, I1Ty, LV4), nullptr);
144   EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SGT, I1Ty, LV4), nullptr);
145 }
146 
TEST_F(ValueLatticeTest,getCompareFloat)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)->isOneValue());
156   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV2)->isOneValue());
157   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV2)->isOneValue());
158   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV2)->isZeroValue());
159   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV2)->isZeroValue());
160   EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV2)->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), nullptr);
165   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV2), nullptr);
166   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV2), nullptr);
167   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV2), nullptr);
168   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV2), nullptr);
169   EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV2), nullptr);
170 }
171 
TEST_F(ValueLatticeTest,getCompareUndef)172 TEST_F(ValueLatticeTest, getCompareUndef) {
173   auto *I32Ty = IntegerType::get(Context, 32);
174   auto *I1Ty = IntegerType::get(Context, 1);
175 
176   auto LV1 = ValueLatticeElement::get(UndefValue::get(I32Ty));
177   auto LV2 =
178       ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)});
179   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV2)));
180   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV2)));
181   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV2)));
182   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV2)));
183   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV2)));
184   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV2)));
185 
186   auto *FloatTy = IntegerType::getFloatTy(Context);
187   auto LV3 = ValueLatticeElement::get(ConstantFP::get(FloatTy, 1.0));
188   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV3)));
189   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV3)));
190   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV3)));
191   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV3)));
192   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV3)));
193   EXPECT_TRUE(isa<UndefValue>(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV3)));
194 }
195 
196 } // end anonymous namespace
197 } // end namespace llvm
198