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/IR/ConstantRange.h"
11#include "llvm/IR/Constants.h"
12#include "llvm/IR/IRBuilder.h"
13#include "llvm/IR/LLVMContext.h"
14#include "llvm/IR/Module.h"
15#include "gtest/gtest.h"
16
17namespace llvm {
18namespace {
19
20// We use this fixture to ensure that we clean up ScalarEvolution before
21// deleting the PassManager.
22class ValueLatticeTest : public testing::Test {
23protected:
24 LLVMContext Context;
25 DataLayout DL = DataLayout("");
26};
27
28TEST_F(ValueLatticeTest, ValueLatticeGetters) {
29 auto I32Ty = IntegerType::get(C&: Context, NumBits: 32);
30 auto *C1 = ConstantInt::get(Ty: I32Ty, V: 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(C&: Context);
38 auto *C2 = ConstantFP::get(Ty: FloatTy, V: 1.1);
39 EXPECT_TRUE(ValueLatticeElement::get(C2).isConstant());
40 EXPECT_TRUE(ValueLatticeElement::getNot(C2).isNotConstant());
41}
42
43TEST_F(ValueLatticeTest, MarkConstantRange) {
44 auto LV1 =
45 ValueLatticeElement::getRange(CR: {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
60TEST_F(ValueLatticeTest, MergeIn) {
61 auto I32Ty = IntegerType::get(C&: Context, NumBits: 32);
62 auto *C1 = ConstantInt::get(Ty: I32Ty, V: 1);
63
64 // Merge to lattice values with equal integer constant.
65 auto LV1 = ValueLatticeElement::get(C: C1);
66 EXPECT_FALSE(LV1.mergeIn(ValueLatticeElement::get(C1)));
67 EXPECT_TRUE(LV1.isConstantRange());
68 EXPECT_EQ(LV1.asConstantInteger()->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
102TEST_F(ValueLatticeTest, getCompareIntegers) {
103 auto *I32Ty = IntegerType::get(C&: Context, NumBits: 32);
104 auto *I1Ty = IntegerType::get(C&: Context, NumBits: 1);
105 auto *C1 = ConstantInt::get(Ty: I32Ty, V: 1);
106 auto LV1 = ValueLatticeElement::get(C: C1);
107
108 // Check getCompare for equal integer constants.
109 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV1, DL)->isOneValue());
110 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV1, DL)->isOneValue());
111 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV1, DL)->isOneValue());
112 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV1, DL)->isZeroValue());
113 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV1, DL)->isZeroValue());
114 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV1, DL)->isZeroValue());
115
116 auto LV2 =
117 ValueLatticeElement::getRange(CR: {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, DL)->isOneValue());
120 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV2, DL)->isOneValue());
121 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV2, DL)->isOneValue());
122 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV2, DL)->isZeroValue());
123 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV2, DL)->isZeroValue());
124 EXPECT_TRUE(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV2, DL)->isZeroValue());
125
126 auto LV3 =
127 ValueLatticeElement::getRange(CR: {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, DL), nullptr);
130 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SLE, I1Ty, LV3, DL), nullptr);
131 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_NE, I1Ty, LV3, DL), nullptr);
132 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_EQ, I1Ty, LV3, DL), nullptr);
133 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SGE, I1Ty, LV3, DL), nullptr);
134 EXPECT_EQ(LV2.getCompare(CmpInst::ICMP_SGT, I1Ty, LV3, DL), nullptr);
135
136 auto LV4 =
137 ValueLatticeElement::getRange(CR: {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, DL), nullptr);
140 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SLE, I1Ty, LV4, DL), nullptr);
141 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_NE, I1Ty, LV4, DL), nullptr);
142 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_EQ, I1Ty, LV4, DL), nullptr);
143 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SGE, I1Ty, LV4, DL), nullptr);
144 EXPECT_EQ(LV3.getCompare(CmpInst::ICMP_SGT, I1Ty, LV4, DL), nullptr);
145}
146
147TEST_F(ValueLatticeTest, getCompareFloat) {
148 auto *FloatTy = IntegerType::getFloatTy(C&: Context);
149 auto *I1Ty = IntegerType::get(C&: Context, NumBits: 1);
150 auto *C1 = ConstantFP::get(Ty: FloatTy, V: 1.0);
151 auto LV1 = ValueLatticeElement::get(C: C1);
152 auto LV2 = ValueLatticeElement::get(C: C1);
153
154 // Check getCompare for equal floating point constants.
155 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV2, DL)->isOneValue());
156 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV2, DL)->isOneValue());
157 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV2, DL)->isOneValue());
158 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV2, DL)->isZeroValue());
159 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV2, DL)->isZeroValue());
160 EXPECT_TRUE(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV2, DL)->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, DL), nullptr);
165 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV2, DL), nullptr);
166 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV2, DL), nullptr);
167 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV2, DL), nullptr);
168 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV2, DL), nullptr);
169 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV2, DL), nullptr);
170}
171
172TEST_F(ValueLatticeTest, getCompareUndef) {
173 auto *I32Ty = IntegerType::get(C&: Context, NumBits: 32);
174 auto *I1Ty = IntegerType::get(C&: Context, NumBits: 1);
175
176 // TODO: These results can be improved.
177 auto LV1 = ValueLatticeElement::get(C: UndefValue::get(T: I32Ty));
178 auto LV2 =
179 ValueLatticeElement::getRange(CR: {APInt(32, 10, true), APInt(32, 20, true)});
180 EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_SLT, I1Ty, LV2, DL), nullptr);
181 EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_SLE, I1Ty, LV2, DL), nullptr);
182 EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_NE, I1Ty, LV2, DL), nullptr);
183 EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_EQ, I1Ty, LV2, DL), nullptr);
184 EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_SGE, I1Ty, LV2, DL), nullptr);
185 EXPECT_EQ(LV1.getCompare(CmpInst::ICMP_SGT, I1Ty, LV2, DL), nullptr);
186
187 auto *FloatTy = IntegerType::getFloatTy(C&: Context);
188 auto LV3 = ValueLatticeElement::get(C: ConstantFP::get(Ty: FloatTy, V: 1.0));
189 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OEQ, I1Ty, LV3, DL), nullptr);
190 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGE, I1Ty, LV3, DL), nullptr);
191 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLE, I1Ty, LV3, DL), nullptr);
192 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_ONE, I1Ty, LV3, DL), nullptr);
193 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OLT, I1Ty, LV3, DL), nullptr);
194 EXPECT_EQ(LV1.getCompare(CmpInst::FCMP_OGT, I1Ty, LV3, DL), nullptr);
195}
196
197} // end anonymous namespace
198} // end namespace llvm
199

source code of llvm/unittests/Analysis/ValueLatticeTest.cpp