1 //===- llvm/unittest/Support/ConstantRangeTest.cpp - ConstantRange tests --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Support/ConstantRange.h"
11 #include "llvm/Support/raw_os_ostream.h"
13 #include "gtest/gtest.h"
19 class ConstantRangeTest : public ::testing::Test {
21 static ConstantRange Full;
22 static ConstantRange Empty;
23 static ConstantRange One;
24 static ConstantRange Some;
25 static ConstantRange Wrap;
28 ConstantRange ConstantRangeTest::Full(16);
29 ConstantRange ConstantRangeTest::Empty(16, false);
30 ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
31 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
32 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
34 TEST_F(ConstantRangeTest, Basics) {
35 EXPECT_TRUE(Full.isFullSet());
36 EXPECT_FALSE(Full.isEmptySet());
37 EXPECT_FALSE(Full.isWrappedSet());
38 EXPECT_TRUE(Full.contains(APInt(16, 0x0)));
39 EXPECT_TRUE(Full.contains(APInt(16, 0x9)));
40 EXPECT_TRUE(Full.contains(APInt(16, 0xa)));
41 EXPECT_TRUE(Full.contains(APInt(16, 0xaa9)));
42 EXPECT_TRUE(Full.contains(APInt(16, 0xaaa)));
44 EXPECT_FALSE(Empty.isFullSet());
45 EXPECT_TRUE(Empty.isEmptySet());
46 EXPECT_FALSE(Empty.isWrappedSet());
47 EXPECT_FALSE(Empty.contains(APInt(16, 0x0)));
48 EXPECT_FALSE(Empty.contains(APInt(16, 0x9)));
49 EXPECT_FALSE(Empty.contains(APInt(16, 0xa)));
50 EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9)));
51 EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa)));
53 EXPECT_FALSE(One.isFullSet());
54 EXPECT_FALSE(One.isEmptySet());
55 EXPECT_FALSE(One.isWrappedSet());
56 EXPECT_FALSE(One.contains(APInt(16, 0x0)));
57 EXPECT_FALSE(One.contains(APInt(16, 0x9)));
58 EXPECT_TRUE(One.contains(APInt(16, 0xa)));
59 EXPECT_FALSE(One.contains(APInt(16, 0xaa9)));
60 EXPECT_FALSE(One.contains(APInt(16, 0xaaa)));
62 EXPECT_FALSE(Some.isFullSet());
63 EXPECT_FALSE(Some.isEmptySet());
64 EXPECT_FALSE(Some.isWrappedSet());
65 EXPECT_FALSE(Some.contains(APInt(16, 0x0)));
66 EXPECT_FALSE(Some.contains(APInt(16, 0x9)));
67 EXPECT_TRUE(Some.contains(APInt(16, 0xa)));
68 EXPECT_TRUE(Some.contains(APInt(16, 0xaa9)));
69 EXPECT_FALSE(Some.contains(APInt(16, 0xaaa)));
71 EXPECT_FALSE(Wrap.isFullSet());
72 EXPECT_FALSE(Wrap.isEmptySet());
73 EXPECT_TRUE(Wrap.isWrappedSet());
74 EXPECT_TRUE(Wrap.contains(APInt(16, 0x0)));
75 EXPECT_TRUE(Wrap.contains(APInt(16, 0x9)));
76 EXPECT_FALSE(Wrap.contains(APInt(16, 0xa)));
77 EXPECT_FALSE(Wrap.contains(APInt(16, 0xaa9)));
78 EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa)));
81 TEST_F(ConstantRangeTest, Equality) {
82 EXPECT_TRUE(Full == Full);
83 EXPECT_TRUE(Empty == Empty);
84 EXPECT_TRUE(One == One);
85 EXPECT_TRUE(Some == Some);
86 EXPECT_TRUE(Wrap == Wrap);
87 EXPECT_TRUE(Full != Empty);
88 EXPECT_TRUE(Full != One);
89 EXPECT_TRUE(Full != Some);
90 EXPECT_TRUE(Full != Wrap);
91 EXPECT_TRUE(Empty != One);
92 EXPECT_TRUE(Empty != Some);
93 EXPECT_TRUE(Empty != Wrap);
94 EXPECT_TRUE(One != Some);
95 EXPECT_TRUE(One != Wrap);
96 EXPECT_TRUE(Some != Wrap);
99 TEST_F(ConstantRangeTest, SingleElement) {
100 EXPECT_EQ(Full.getSingleElement(), static_cast<APInt *>(NULL));
101 EXPECT_EQ(Empty.getSingleElement(), static_cast<APInt *>(NULL));
102 EXPECT_EQ(*One.getSingleElement(), APInt(16, 0xa));
103 EXPECT_EQ(Some.getSingleElement(), static_cast<APInt *>(NULL));
104 EXPECT_EQ(Wrap.getSingleElement(), static_cast<APInt *>(NULL));
106 EXPECT_FALSE(Full.isSingleElement());
107 EXPECT_FALSE(Empty.isSingleElement());
108 EXPECT_TRUE(One.isSingleElement());
109 EXPECT_FALSE(Some.isSingleElement());
110 EXPECT_FALSE(Wrap.isSingleElement());
113 TEST_F(ConstantRangeTest, GetSetSize) {
114 EXPECT_EQ(Full.getSetSize(), APInt(16, 0));
115 EXPECT_EQ(Empty.getSetSize(), APInt(16, 0));
116 EXPECT_EQ(One.getSetSize(), APInt(16, 1));
117 EXPECT_EQ(Some.getSetSize(), APInt(16, 0xaa0));
118 EXPECT_EQ(Wrap.getSetSize(), APInt(16, 0x10000 - 0xaa0));
121 TEST_F(ConstantRangeTest, GetMinsAndMaxes) {
122 EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX));
123 EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa));
124 EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9));
125 EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX));
127 EXPECT_EQ(Full.getUnsignedMin(), APInt(16, 0));
128 EXPECT_EQ(One.getUnsignedMin(), APInt(16, 0xa));
129 EXPECT_EQ(Some.getUnsignedMin(), APInt(16, 0xa));
130 EXPECT_EQ(Wrap.getUnsignedMin(), APInt(16, 0));
132 EXPECT_EQ(Full.getSignedMax(), APInt(16, INT16_MAX));
133 EXPECT_EQ(One.getSignedMax(), APInt(16, 0xa));
134 EXPECT_EQ(Some.getSignedMax(), APInt(16, 0xaa9));
135 EXPECT_EQ(Wrap.getSignedMax(), APInt(16, INT16_MAX));
137 EXPECT_EQ(Full.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
138 EXPECT_EQ(One.getSignedMin(), APInt(16, 0xa));
139 EXPECT_EQ(Some.getSignedMin(), APInt(16, 0xa));
140 EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
143 EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),
147 TEST_F(ConstantRangeTest, Trunc) {
148 ConstantRange TFull = Full.truncate(10);
149 ConstantRange TEmpty = Empty.truncate(10);
150 ConstantRange TOne = One.truncate(10);
151 ConstantRange TSome = Some.truncate(10);
152 ConstantRange TWrap = Wrap.truncate(10);
153 EXPECT_TRUE(TFull.isFullSet());
154 EXPECT_TRUE(TEmpty.isEmptySet());
155 EXPECT_TRUE(TOne == ConstantRange(APInt(One.getLower()).trunc(10),
156 APInt(One.getUpper()).trunc(10)));
157 EXPECT_TRUE(TSome.isFullSet());
160 TEST_F(ConstantRangeTest, ZExt) {
161 ConstantRange ZFull = Full.zeroExtend(20);
162 ConstantRange ZEmpty = Empty.zeroExtend(20);
163 ConstantRange ZOne = One.zeroExtend(20);
164 ConstantRange ZSome = Some.zeroExtend(20);
165 ConstantRange ZWrap = Wrap.zeroExtend(20);
166 EXPECT_TRUE(ZFull == ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
167 EXPECT_TRUE(ZEmpty.isEmptySet());
168 EXPECT_TRUE(ZOne == ConstantRange(APInt(One.getLower()).zext(20),
169 APInt(One.getUpper()).zext(20)));
170 EXPECT_TRUE(ZSome == ConstantRange(APInt(Some.getLower()).zext(20),
171 APInt(Some.getUpper()).zext(20)));
172 EXPECT_TRUE(ZWrap == ConstantRange(APInt(Wrap.getLower()).zext(20),
173 APInt(Wrap.getUpper()).zext(20)));
176 TEST_F(ConstantRangeTest, SExt) {
177 ConstantRange SFull = Full.signExtend(20);
178 ConstantRange SEmpty = Empty.signExtend(20);
179 ConstantRange SOne = One.signExtend(20);
180 ConstantRange SSome = Some.signExtend(20);
181 ConstantRange SWrap = Wrap.signExtend(20);
182 EXPECT_TRUE(SFull == ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
183 APInt(20, INT16_MAX + 1, true)));
184 EXPECT_TRUE(SEmpty.isEmptySet());
185 EXPECT_TRUE(SOne == ConstantRange(APInt(One.getLower()).sext(20),
186 APInt(One.getUpper()).sext(20)));
187 EXPECT_TRUE(SSome == ConstantRange(APInt(Some.getLower()).sext(20),
188 APInt(Some.getUpper()).sext(20)));
189 EXPECT_TRUE(SWrap == ConstantRange(APInt(Wrap.getLower()).sext(20),
190 APInt(Wrap.getUpper()).sext(20)));
193 TEST_F(ConstantRangeTest, IntersectWith) {
194 EXPECT_TRUE(Empty.intersectWith(Full).isEmptySet());
195 EXPECT_TRUE(Empty.intersectWith(Empty).isEmptySet());
196 EXPECT_TRUE(Empty.intersectWith(One).isEmptySet());
197 EXPECT_TRUE(Empty.intersectWith(Some).isEmptySet());
198 EXPECT_TRUE(Empty.intersectWith(Wrap).isEmptySet());
199 EXPECT_TRUE(Full.intersectWith(Full).isFullSet());
200 EXPECT_TRUE(Some.intersectWith(Some) == Some);
201 EXPECT_TRUE(Some.intersectWith(One) == One);
202 EXPECT_TRUE(Full.intersectWith(One) == One);
203 EXPECT_TRUE(Full.intersectWith(Some) == Some);
204 EXPECT_TRUE(Some.intersectWith(Wrap).isEmptySet());
205 EXPECT_TRUE(One.intersectWith(Wrap).isEmptySet());
206 EXPECT_TRUE(One.intersectWith(Wrap) == Wrap.intersectWith(One));
208 // Klee generated testcase from PR4545.
209 // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
210 // 01..4.6789ABCDEF where the dots represent values not in the intersection.
211 ConstantRange LHS(APInt(16, 4), APInt(16, 2));
212 ConstantRange RHS(APInt(16, 6), APInt(16, 5));
213 EXPECT_TRUE(LHS.intersectWith(RHS) == LHS);
216 TEST_F(ConstantRangeTest, UnionWith) {
217 EXPECT_TRUE(Wrap.unionWith(One) ==
218 ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));
219 EXPECT_TRUE(One.unionWith(Wrap) == Wrap.unionWith(One));
220 EXPECT_TRUE(Empty.unionWith(Empty).isEmptySet());
221 EXPECT_TRUE(Full.unionWith(Full).isFullSet());
222 EXPECT_TRUE(Some.unionWith(Wrap).isFullSet());
225 EXPECT_TRUE(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(
226 ConstantRange(APInt(16, 0), APInt(16, 8))) ==
227 ConstantRange(APInt(16, 14), APInt(16, 8)));
228 EXPECT_TRUE(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(
229 ConstantRange(APInt(16, 4), APInt(16, 0))) ==
231 EXPECT_TRUE(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(
232 ConstantRange(APInt(16, 2), APInt(16, 1))) ==
236 TEST_F(ConstantRangeTest, SubtractAPInt) {
237 EXPECT_TRUE(Full.subtract(APInt(16, 4)).isFullSet());
238 EXPECT_TRUE(Empty.subtract(APInt(16, 4)).isEmptySet());
239 EXPECT_TRUE(Some.subtract(APInt(16, 4)) ==
240 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
241 EXPECT_TRUE(Wrap.subtract(APInt(16, 4)) ==
242 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
243 EXPECT_TRUE(One.subtract(APInt(16, 4)) ==
244 ConstantRange(APInt(16, 0x6)));
247 TEST_F(ConstantRangeTest, Add) {
248 EXPECT_TRUE(Full.add(APInt(16, 4)).isFullSet());
249 EXPECT_TRUE(Full.add(Full) == Full);
250 EXPECT_TRUE(Full.add(Empty) == Empty);
251 EXPECT_TRUE(Full.add(One) == Full);
252 EXPECT_TRUE(Full.add(Some) == Full);
253 EXPECT_TRUE(Full.add(Wrap) == Full);
254 EXPECT_TRUE(Empty.add(Empty) == Empty);
255 EXPECT_TRUE(Empty.add(One) == Empty);
256 EXPECT_TRUE(Empty.add(Some) == Empty);
257 EXPECT_TRUE(Empty.add(Wrap) == Empty);
258 EXPECT_TRUE(Empty.add(APInt(16, 4)).isEmptySet());
259 EXPECT_TRUE(Some.add(APInt(16, 4)) ==
260 ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
261 EXPECT_TRUE(Wrap.add(APInt(16, 4)) ==
262 ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
263 EXPECT_TRUE(One.add(APInt(16, 4)) ==
264 ConstantRange(APInt(16, 0xe)));
267 TEST_F(ConstantRangeTest, Multiply) {
268 EXPECT_TRUE(Full.multiply(Full) == Full);
269 EXPECT_TRUE(Full.multiply(Empty) == Empty);
270 EXPECT_TRUE(Full.multiply(One) == Full);
271 EXPECT_TRUE(Full.multiply(Some) == Full);
272 EXPECT_TRUE(Full.multiply(Wrap) == Full);
273 EXPECT_TRUE(Empty.multiply(Empty) == Empty);
274 EXPECT_TRUE(Empty.multiply(One) == Empty);
275 EXPECT_TRUE(Empty.multiply(Some) == Empty);
276 EXPECT_TRUE(Empty.multiply(Wrap) == Empty);
277 EXPECT_TRUE(One.multiply(One) == ConstantRange(APInt(16, 0xa*0xa),
278 APInt(16, 0xa*0xa + 1)));
279 EXPECT_TRUE(One.multiply(Some) == ConstantRange(APInt(16, 0xa*0xa),
280 APInt(16, 0xa*0xaa9 + 1)));
281 EXPECT_TRUE(One.multiply(Wrap).isFullSet());
282 EXPECT_TRUE(Some.multiply(Some).isFullSet());
283 EXPECT_TRUE(Some.multiply(Wrap) == Full);
284 EXPECT_TRUE(Wrap.multiply(Wrap) == Full);
286 // http://llvm.org/PR4545
287 EXPECT_TRUE(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply(
288 ConstantRange(APInt(4, 6), APInt(4, 2))) ==
289 ConstantRange(4, /*isFullSet=*/true));
292 TEST_F(ConstantRangeTest, UMax) {
293 EXPECT_TRUE(Full.umax(Full).isFullSet());
294 EXPECT_TRUE(Full.umax(Empty).isEmptySet());
295 EXPECT_TRUE(Full.umax(Some) == ConstantRange(APInt(16, 0xa), APInt(16, 0)));
296 EXPECT_TRUE(Full.umax(Wrap).isFullSet());
297 EXPECT_TRUE(Full.umax(Some) == ConstantRange(APInt(16, 0xa), APInt(16, 0)));
298 EXPECT_TRUE(Empty.umax(Empty) == Empty);
299 EXPECT_TRUE(Empty.umax(Some) == Empty);
300 EXPECT_TRUE(Empty.umax(Wrap) == Empty);
301 EXPECT_TRUE(Empty.umax(One) == Empty);
302 EXPECT_TRUE(Some.umax(Some) == Some);
303 EXPECT_TRUE(Some.umax(Wrap) == ConstantRange(APInt(16, 0xa), APInt(16, 0)));
304 EXPECT_TRUE(Some.umax(One) == Some);
305 // TODO: ConstantRange is currently over-conservative here.
306 EXPECT_TRUE(Wrap.umax(Wrap) == Full);
307 EXPECT_TRUE(Wrap.umax(One) == ConstantRange(APInt(16, 0xa), APInt(16, 0)));
308 EXPECT_TRUE(One.umax(One) == One);
311 TEST_F(ConstantRangeTest, SMax) {
312 EXPECT_TRUE(Full.smax(Full).isFullSet());
313 EXPECT_TRUE(Full.smax(Empty).isEmptySet());
314 EXPECT_TRUE(Full.smax(Some) == ConstantRange(APInt(16, 0xa),
315 APInt::getSignedMinValue(16)));
316 EXPECT_TRUE(Full.smax(Wrap).isFullSet());
317 EXPECT_TRUE(Full.smax(One) == ConstantRange(APInt(16, 0xa),
318 APInt::getSignedMinValue(16)));
319 EXPECT_TRUE(Empty.smax(Empty) == Empty);
320 EXPECT_TRUE(Empty.smax(Some) == Empty);
321 EXPECT_TRUE(Empty.smax(Wrap) == Empty);
322 EXPECT_TRUE(Empty.smax(One) == Empty);
323 EXPECT_TRUE(Some.smax(Some) == Some);
324 EXPECT_TRUE(Some.smax(Wrap) == ConstantRange(APInt(16, 0xa),
325 APInt(16, (uint64_t)INT16_MIN)));
326 EXPECT_TRUE(Some.smax(One) == Some);
327 EXPECT_TRUE(Wrap.smax(One) == ConstantRange(APInt(16, 0xa),
328 APInt(16, (uint64_t)INT16_MIN)));
329 EXPECT_TRUE(One.smax(One) == One);
332 TEST_F(ConstantRangeTest, UDiv) {
333 EXPECT_TRUE(Full.udiv(Full) == Full);
334 EXPECT_TRUE(Full.udiv(Empty) == Empty);
335 EXPECT_TRUE(Full.udiv(One) == ConstantRange(APInt(16, 0),
336 APInt(16, 0xffff / 0xa + 1)));
337 EXPECT_TRUE(Full.udiv(Some) == ConstantRange(APInt(16, 0),
338 APInt(16, 0xffff / 0xa + 1)));
339 EXPECT_TRUE(Full.udiv(Wrap) == Full);
340 EXPECT_TRUE(Empty.udiv(Empty) == Empty);
341 EXPECT_TRUE(Empty.udiv(One) == Empty);
342 EXPECT_TRUE(Empty.udiv(Some) == Empty);
343 EXPECT_TRUE(Empty.udiv(Wrap) == Empty);
344 EXPECT_TRUE(One.udiv(One) == ConstantRange(APInt(16, 1)));
345 EXPECT_TRUE(One.udiv(Some) == ConstantRange(APInt(16, 0), APInt(16, 2)));
346 EXPECT_TRUE(One.udiv(Wrap) == ConstantRange(APInt(16, 0), APInt(16, 0xb)));
347 EXPECT_TRUE(Some.udiv(Some) == ConstantRange(APInt(16, 0), APInt(16, 0x111)));
348 EXPECT_TRUE(Some.udiv(Wrap) == ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
349 EXPECT_TRUE(Wrap.udiv(Wrap) == Full);
352 } // anonymous namespace