Mercurial > hg > CbC > CbC_llvm

comparison unittests/IR/ConstantRangeTest.cpp @ 148:63bd29f05246

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merged
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Wed, 14 Aug 2019 19:46:37 +0900
parents c2174574ed3a
children
comparison
equal deleted inserted replaced
146:3fc4d5c3e21e 148:63bd29f05246
1 //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===// 1 //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===//
2 // 2 //
3 // The LLVM Compiler Infrastructure 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // 4 // See https://llvm.org/LICENSE.txt for license information.
5 // This file is distributed under the University of Illinois Open Source 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 // License. See LICENSE.TXT for details.
7 // 6 //
8 //===----------------------------------------------------------------------===// 7 //===----------------------------------------------------------------------===//
9 8
9 #include "llvm/ADT/BitVector.h"
10 #include "llvm/IR/ConstantRange.h" 10 #include "llvm/IR/ConstantRange.h"
11 #include "llvm/IR/Instructions.h" 11 #include "llvm/IR/Instructions.h"
12 #include "llvm/IR/Operator.h" 12 #include "llvm/IR/Operator.h"
13 #include "llvm/Support/KnownBits.h"
13 #include "gtest/gtest.h" 14 #include "gtest/gtest.h"
14 15
15 using namespace llvm; 16 using namespace llvm;
16 17
17 namespace { 18 namespace {
23 static ConstantRange One; 24 static ConstantRange One;
24 static ConstantRange Some; 25 static ConstantRange Some;
25 static ConstantRange Wrap; 26 static ConstantRange Wrap;
26 }; 27 };
27 28
28 ConstantRange ConstantRangeTest::Full(16); 29 template<typename Fn>
30 static void EnumerateConstantRanges(unsigned Bits, Fn TestFn) {
31 unsigned Max = 1 << Bits;
32 for (unsigned Lo = 0; Lo < Max; Lo++) {
33 for (unsigned Hi = 0; Hi < Max; Hi++) {
34 // Enforce ConstantRange invariant.
35 if (Lo == Hi && Lo != 0 && Lo != Max - 1)
36 continue;
37
38 ConstantRange CR(APInt(Bits, Lo), APInt(Bits, Hi));
39 TestFn(CR);
40 }
41 }
42 }
43
44 template<typename Fn>
45 static void EnumerateTwoConstantRanges(unsigned Bits, Fn TestFn) {
46 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR1) {
47 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR2) {
48 TestFn(CR1, CR2);
49 });
50 });
51 }
52
53 template<typename Fn>
54 static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) {
55 if (!CR.isEmptySet()) {
56 APInt N = CR.getLower();
57 do TestFn(N);
58 while (++N != CR.getUpper());
59 }
60 }
61
62 template<typename Fn1, typename Fn2>
63 static void TestUnsignedBinOpExhaustive(
64 Fn1 RangeFn, Fn2 IntFn,
65 bool SkipZeroRHS = false, bool CorrectnessOnly = false) {
66 unsigned Bits = 4;
67 EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
68 const ConstantRange &CR2) {
69 APInt Min = APInt::getMaxValue(Bits);
70 APInt Max = APInt::getMinValue(Bits);
71 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
72 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
73 if (SkipZeroRHS && N2 == 0)
74 return;
75
76 APInt N = IntFn(N1, N2);
77 if (N.ult(Min))
78 Min = N;
79 if (N.ugt(Max))
80 Max = N;
81 });
82 });
83
84 ConstantRange CR = RangeFn(CR1, CR2);
85 if (Min.ugt(Max)) {
86 EXPECT_TRUE(CR.isEmptySet());
87 return;
88 }
89
90 ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
91 if (CorrectnessOnly) {
92 EXPECT_TRUE(CR.contains(Exact));
93 } else {
94 EXPECT_EQ(Exact, CR);
95 }
96 });
97 }
98
99 template<typename Fn1, typename Fn2>
100 static void TestSignedBinOpExhaustive(
101 Fn1 RangeFn, Fn2 IntFn,
102 bool SkipZeroRHS = false, bool CorrectnessOnly = false) {
103 unsigned Bits = 4;
104 EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
105 const ConstantRange &CR2) {
106 APInt Min = APInt::getSignedMaxValue(Bits);
107 APInt Max = APInt::getSignedMinValue(Bits);
108 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
109 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
110 if (SkipZeroRHS && N2 == 0)
111 return;
112
113 APInt N = IntFn(N1, N2);
114 if (N.slt(Min))
115 Min = N;
116 if (N.sgt(Max))
117 Max = N;
118 });
119 });
120
121 ConstantRange CR = RangeFn(CR1, CR2);
122 if (Min.sgt(Max)) {
123 EXPECT_TRUE(CR.isEmptySet());
124 return;
125 }
126
127 ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
128 if (CorrectnessOnly) {
129 EXPECT_TRUE(CR.contains(Exact));
130 } else {
131 EXPECT_EQ(Exact, CR);
132 }
133 });
134 }
135
136 ConstantRange ConstantRangeTest::Full(16, true);
29 ConstantRange ConstantRangeTest::Empty(16, false); 137 ConstantRange ConstantRangeTest::Empty(16, false);
30 ConstantRange ConstantRangeTest::One(APInt(16, 0xa)); 138 ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
31 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa)); 139 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
32 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa)); 140 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
33 141
120 EXPECT_TRUE(One.isSingleElement()); 228 EXPECT_TRUE(One.isSingleElement());
121 EXPECT_FALSE(Some.isSingleElement()); 229 EXPECT_FALSE(Some.isSingleElement());
122 EXPECT_FALSE(Wrap.isSingleElement()); 230 EXPECT_FALSE(Wrap.isSingleElement());
123 } 231 }
124 232
125 TEST_F(ConstantRangeTest, GetSetSize) {
126 EXPECT_EQ(Full.getSetSize(), APInt(17, 65536));
127 EXPECT_EQ(Empty.getSetSize(), APInt(17, 0));
128 EXPECT_EQ(One.getSetSize(), APInt(17, 1));
129 EXPECT_EQ(Some.getSetSize(), APInt(17, 0xaa0));
130
131 ConstantRange Wrap(APInt(4, 7), APInt(4, 3));
132 ConstantRange Wrap2(APInt(4, 8), APInt(4, 7));
133 EXPECT_EQ(Wrap.getSetSize(), APInt(5, 12));
134 EXPECT_EQ(Wrap2.getSetSize(), APInt(5, 15));
135 }
136
137 TEST_F(ConstantRangeTest, GetMinsAndMaxes) { 233 TEST_F(ConstantRangeTest, GetMinsAndMaxes) {
138 EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX)); 234 EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX));
139 EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa)); 235 EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa));
140 EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9)); 236 EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9));
141 EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX)); 237 EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX));
159 EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(), 255 EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),
160 APInt(4, 7)); 256 APInt(4, 7));
161 } 257 }
162 258
163 TEST_F(ConstantRangeTest, SignWrapped) { 259 TEST_F(ConstantRangeTest, SignWrapped) {
164 EXPECT_TRUE(Full.isSignWrappedSet()); 260 EXPECT_FALSE(Full.isSignWrappedSet());
165 EXPECT_FALSE(Empty.isSignWrappedSet()); 261 EXPECT_FALSE(Empty.isSignWrappedSet());
166 EXPECT_FALSE(One.isSignWrappedSet()); 262 EXPECT_FALSE(One.isSignWrappedSet());
167 EXPECT_FALSE(Some.isSignWrappedSet()); 263 EXPECT_FALSE(Some.isSignWrappedSet());
168 EXPECT_TRUE(Wrap.isSignWrappedSet()); 264 EXPECT_TRUE(Wrap.isSignWrappedSet());
169 265
172 EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet()); 268 EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet());
173 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet()); 269 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet());
174 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet()); 270 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet());
175 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet()); 271 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet());
176 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet()); 272 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet());
273 }
274
275 TEST_F(ConstantRangeTest, UpperWrapped) {
276 // The behavior here is the same as for isWrappedSet() / isSignWrappedSet().
277 EXPECT_FALSE(Full.isUpperWrapped());
278 EXPECT_FALSE(Empty.isUpperWrapped());
279 EXPECT_FALSE(One.isUpperWrapped());
280 EXPECT_FALSE(Some.isUpperWrapped());
281 EXPECT_TRUE(Wrap.isUpperWrapped());
282 EXPECT_FALSE(Full.isUpperSignWrapped());
283 EXPECT_FALSE(Empty.isUpperSignWrapped());
284 EXPECT_FALSE(One.isUpperSignWrapped());
285 EXPECT_FALSE(Some.isUpperSignWrapped());
286 EXPECT_TRUE(Wrap.isUpperSignWrapped());
287
288 // The behavior differs if Upper is the Min/SignedMin value.
289 ConstantRange CR1(APInt(8, 42), APInt::getMinValue(8));
290 EXPECT_FALSE(CR1.isWrappedSet());
291 EXPECT_TRUE(CR1.isUpperWrapped());
292
293 ConstantRange CR2(APInt(8, 42), APInt::getSignedMinValue(8));
294 EXPECT_FALSE(CR2.isSignWrappedSet());
295 EXPECT_TRUE(CR2.isUpperSignWrapped());
177 } 296 }
178 297
179 TEST_F(ConstantRangeTest, Trunc) { 298 TEST_F(ConstantRangeTest, Trunc) {
180 ConstantRange TFull = Full.truncate(10); 299 ConstantRange TFull = Full.truncate(10);
181 ConstantRange TEmpty = Empty.truncate(10); 300 ConstantRange TEmpty = Empty.truncate(10);
297 416
298 // [4, 2) /\ [1, 0) = [1, 0) 417 // [4, 2) /\ [1, 0) = [1, 0)
299 LHS = ConstantRange(APInt(32, 4), APInt(32, 2)); 418 LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
300 RHS = ConstantRange(APInt(32, 1), APInt(32, 0)); 419 RHS = ConstantRange(APInt(32, 1), APInt(32, 0));
301 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2))); 420 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2)));
302 421
303 // [15, 0) /\ [7, 6) = [15, 0) 422 // [15, 0) /\ [7, 6) = [15, 0)
304 LHS = ConstantRange(APInt(32, 15), APInt(32, 0)); 423 LHS = ConstantRange(APInt(32, 15), APInt(32, 0));
305 RHS = ConstantRange(APInt(32, 7), APInt(32, 6)); 424 RHS = ConstantRange(APInt(32, 7), APInt(32, 6));
306 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0))); 425 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0)));
426 }
427
428 template<typename Fn1, typename Fn2>
429 void testBinarySetOperationExhaustive(Fn1 OpFn, Fn2 InResultFn) {
430 unsigned Bits = 4;
431 EnumerateTwoConstantRanges(Bits,
432 [=](const ConstantRange &CR1, const ConstantRange &CR2) {
433 // Collect up to three contiguous unsigned ranges. The HaveInterrupt
434 // variables are used determine when we have to switch to the next
435 // range because the previous one ended.
436 APInt Lower1(Bits, 0), Upper1(Bits, 0);
437 APInt Lower2(Bits, 0), Upper2(Bits, 0);
438 APInt Lower3(Bits, 0), Upper3(Bits, 0);
439 bool HaveRange1 = false, HaveInterrupt1 = false;
440 bool HaveRange2 = false, HaveInterrupt2 = false;
441 bool HaveRange3 = false, HaveInterrupt3 = false;
442
443 APInt Num(Bits, 0);
444 for (unsigned I = 0, Limit = 1 << Bits; I < Limit; ++I, ++Num) {
445 if (!InResultFn(CR1, CR2, Num)) {
446 if (HaveRange3)
447 HaveInterrupt3 = true;
448 else if (HaveRange2)
449 HaveInterrupt2 = true;
450 else if (HaveRange1)
451 HaveInterrupt1 = true;
452 continue;
453 }
454
455 if (HaveRange3) {
456 Upper3 = Num;
457 } else if (HaveInterrupt2) {
458 HaveRange3 = true;
459 Lower3 = Upper3 = Num;
460 } else if (HaveRange2) {
461 Upper2 = Num;
462 } else if (HaveInterrupt1) {
463 HaveRange2 = true;
464 Lower2 = Upper2 = Num;
465 } else if (HaveRange1) {
466 Upper1 = Num;
467 } else {
468 HaveRange1 = true;
469 Lower1 = Upper1 = Num;
470 }
471 }
472
473 (void)HaveInterrupt3;
474 assert(!HaveInterrupt3 && "Should have at most three ranges");
475
476 ConstantRange SmallestCR = OpFn(CR1, CR2, ConstantRange::Smallest);
477 ConstantRange UnsignedCR = OpFn(CR1, CR2, ConstantRange::Unsigned);
478 ConstantRange SignedCR = OpFn(CR1, CR2, ConstantRange::Signed);
479
480 if (!HaveRange1) {
481 EXPECT_TRUE(SmallestCR.isEmptySet());
482 EXPECT_TRUE(UnsignedCR.isEmptySet());
483 EXPECT_TRUE(SignedCR.isEmptySet());
484 return;
485 }
486
487 if (!HaveRange2) {
488 if (Lower1 == Upper1 + 1) {
489 EXPECT_TRUE(SmallestCR.isFullSet());
490 EXPECT_TRUE(UnsignedCR.isFullSet());
491 EXPECT_TRUE(SignedCR.isFullSet());
492 } else {
493 ConstantRange Expected(Lower1, Upper1 + 1);
494 EXPECT_EQ(Expected, SmallestCR);
495 EXPECT_EQ(Expected, UnsignedCR);
496 EXPECT_EQ(Expected, SignedCR);
497 }
498 return;
499 }
500
501 ConstantRange Variant1(Bits, /*full*/ true);
502 ConstantRange Variant2(Bits, /*full*/ true);
503 if (!HaveRange3) {
504 // Compute the two possible ways to cover two disjoint ranges.
505 if (Lower1 != Upper2 + 1)
506 Variant1 = ConstantRange(Lower1, Upper2 + 1);
507 if (Lower2 != Upper1 + 1)
508 Variant2 = ConstantRange(Lower2, Upper1 + 1);
509 } else {
510 // If we have three ranges, the first and last one have to be adjacent
511 // to the unsigned domain. It's better to think of this as having two
512 // holes, and we can construct one range using each hole.
513 assert(Lower1.isNullValue() && Upper3.isMaxValue());
514 Variant1 = ConstantRange(Lower2, Upper1 + 1);
515 Variant2 = ConstantRange(Lower3, Upper2 + 1);
516 }
517
518 // Smallest: Smaller set, then any set.
519 if (Variant1.isSizeStrictlySmallerThan(Variant2))
520 EXPECT_EQ(Variant1, SmallestCR);
521 else if (Variant2.isSizeStrictlySmallerThan(Variant1))
522 EXPECT_EQ(Variant2, SmallestCR);
523 else
524 EXPECT_TRUE(Variant1 == SmallestCR || Variant2 == SmallestCR);
525
526 // Unsigned: Non-wrapped set, then smaller set, then any set.
527 bool Variant1Full = Variant1.isFullSet() || Variant1.isWrappedSet();
528 bool Variant2Full = Variant2.isFullSet() || Variant2.isWrappedSet();
529 if (!Variant1Full && Variant2Full)
530 EXPECT_EQ(Variant1, UnsignedCR);
531 else if (Variant1Full && !Variant2Full)
532 EXPECT_EQ(Variant2, UnsignedCR);
533 else if (Variant1.isSizeStrictlySmallerThan(Variant2))
534 EXPECT_EQ(Variant1, UnsignedCR);
535 else if (Variant2.isSizeStrictlySmallerThan(Variant1))
536 EXPECT_EQ(Variant2, UnsignedCR);
537 else
538 EXPECT_TRUE(Variant1 == UnsignedCR || Variant2 == UnsignedCR);
539
540 // Signed: Signed non-wrapped set, then smaller set, then any set.
541 Variant1Full = Variant1.isFullSet() || Variant1.isSignWrappedSet();
542 Variant2Full = Variant2.isFullSet() || Variant2.isSignWrappedSet();
543 if (!Variant1Full && Variant2Full)
544 EXPECT_EQ(Variant1, SignedCR);
545 else if (Variant1Full && !Variant2Full)
546 EXPECT_EQ(Variant2, SignedCR);
547 else if (Variant1.isSizeStrictlySmallerThan(Variant2))
548 EXPECT_EQ(Variant1, SignedCR);
549 else if (Variant2.isSizeStrictlySmallerThan(Variant1))
550 EXPECT_EQ(Variant2, SignedCR);
551 else
552 EXPECT_TRUE(Variant1 == SignedCR || Variant2 == SignedCR);
553 });
554 }
555
556 TEST_F(ConstantRangeTest, IntersectWithExhaustive) {
557 testBinarySetOperationExhaustive(
558 [](const ConstantRange &CR1, const ConstantRange &CR2,
559 ConstantRange::PreferredRangeType Type) {
560 return CR1.intersectWith(CR2, Type);
561 },
562 [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
563 return CR1.contains(N) && CR2.contains(N);
564 });
565 }
566
567 TEST_F(ConstantRangeTest, UnionWithExhaustive) {
568 testBinarySetOperationExhaustive(
569 [](const ConstantRange &CR1, const ConstantRange &CR2,
570 ConstantRange::PreferredRangeType Type) {
571 return CR1.unionWith(CR2, Type);
572 },
573 [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
574 return CR1.contains(N) || CR2.contains(N);
575 });
307 } 576 }
308 577
309 TEST_F(ConstantRangeTest, UnionWith) { 578 TEST_F(ConstantRangeTest, UnionWith) {
310 EXPECT_EQ(Wrap.unionWith(One), 579 EXPECT_EQ(Wrap.unionWith(One),
311 ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb))); 580 ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));
318 EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith( 587 EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(
319 ConstantRange(APInt(16, 0), APInt(16, 8))), 588 ConstantRange(APInt(16, 0), APInt(16, 8))),
320 ConstantRange(APInt(16, 14), APInt(16, 8))); 589 ConstantRange(APInt(16, 14), APInt(16, 8)));
321 EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith( 590 EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(
322 ConstantRange(APInt(16, 4), APInt(16, 0))), 591 ConstantRange(APInt(16, 4), APInt(16, 0))),
323 ConstantRange(16)); 592 ConstantRange::getFull(16));
324 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith( 593 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(
325 ConstantRange(APInt(16, 2), APInt(16, 1))), 594 ConstantRange(APInt(16, 2), APInt(16, 1))),
326 ConstantRange(16)); 595 ConstantRange::getFull(16));
327 } 596 }
328 597
329 TEST_F(ConstantRangeTest, SetDifference) { 598 TEST_F(ConstantRangeTest, SetDifference) {
330 EXPECT_EQ(Full.difference(Empty), Full); 599 EXPECT_EQ(Full.difference(Empty), Full);
331 EXPECT_EQ(Full.difference(Full), Empty); 600 EXPECT_EQ(Full.difference(Full), Empty);
562 EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2))); 831 EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
563 EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb))); 832 EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
564 EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111))); 833 EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
565 EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 834 EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
566 EXPECT_EQ(Wrap.udiv(Wrap), Full); 835 EXPECT_EQ(Wrap.udiv(Wrap), Full);
836
837
838 ConstantRange Zero(APInt(16, 0));
839 EXPECT_EQ(Zero.udiv(One), Zero);
840 EXPECT_EQ(Zero.udiv(Full), Zero);
841
842 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full),
843 ConstantRange(APInt(16, 0), APInt(16, 99)));
844 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full),
845 ConstantRange(APInt(16, 0), APInt(16, 99)));
846 }
847
848 TEST_F(ConstantRangeTest, SDiv) {
849 unsigned Bits = 4;
850 EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
851 const ConstantRange &CR2) {
852 // Collect possible results in a bit vector. We store the signed value plus
853 // a bias to make it unsigned.
854 int Bias = 1 << (Bits - 1);
855 BitVector Results(1 << Bits);
856 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
857 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
858 // Division by zero is UB.
859 if (N2 == 0)
860 return;
861
862 // SignedMin / -1 is UB.
863 if (N1.isMinSignedValue() && N2.isAllOnesValue())
864 return;
865
866 APInt N = N1.sdiv(N2);
867 Results.set(N.getSExtValue() + Bias);
868 });
869 });
870
871 ConstantRange CR = CR1.sdiv(CR2);
872 if (Results.none()) {
873 EXPECT_TRUE(CR.isEmptySet());
874 return;
875 }
876
877 // If there is a non-full signed envelope, that should be the result.
878 APInt SMin(Bits, Results.find_first() - Bias);
879 APInt SMax(Bits, Results.find_last() - Bias);
880 ConstantRange Envelope = ConstantRange::getNonEmpty(SMin, SMax + 1);
881 if (!Envelope.isFullSet()) {
882 EXPECT_EQ(Envelope, CR);
883 return;
884 }
885
886 // If the signed envelope is a full set, try to find a smaller sign wrapped
887 // set that is separated in negative and positive components (or one which
888 // can also additionally contain zero).
889 int LastNeg = Results.find_last_in(0, Bias) - Bias;
890 int LastPos = Results.find_next(Bias) - Bias;
891 if (Results[Bias]) {
892 if (LastNeg == -1)
893 ++LastNeg;
894 else if (LastPos == 1)
895 --LastPos;
896 }
897
898 APInt WMax(Bits, LastNeg);
899 APInt WMin(Bits, LastPos);
900 ConstantRange Wrapped = ConstantRange::getNonEmpty(WMin, WMax + 1);
901 EXPECT_EQ(Wrapped, CR);
902 });
903 }
904
905 TEST_F(ConstantRangeTest, URem) {
906 EXPECT_EQ(Full.urem(Empty), Empty);
907 EXPECT_EQ(Empty.urem(Full), Empty);
908 // urem by zero is poison.
909 EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty);
910 // urem by full range doesn't contain MaxValue.
911 EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff)));
912 // urem is upper bounded by maximum RHS minus one.
913 EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))),
914 ConstantRange(APInt(16, 0), APInt(16, 122)));
915 // urem is upper bounded by maximum LHS.
916 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full),
917 ConstantRange(APInt(16, 0), APInt(16, 123)));
918 // If the LHS is always lower than the RHS, the result is the LHS.
919 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
920 .urem(ConstantRange(APInt(16, 20), APInt(16, 30))),
921 ConstantRange(APInt(16, 10), APInt(16, 20)));
922 // It has to be strictly lower, otherwise the top value may wrap to zero.
923 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
924 .urem(ConstantRange(APInt(16, 19), APInt(16, 30))),
925 ConstantRange(APInt(16, 0), APInt(16, 20)));
926 // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].
927 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
928 .urem(ConstantRange(APInt(16, 10))),
929 ConstantRange(APInt(16, 0), APInt(16, 10)));
930
931 TestUnsignedBinOpExhaustive(
932 [](const ConstantRange &CR1, const ConstantRange &CR2) {
933 return CR1.urem(CR2);
934 },
935 [](const APInt &N1, const APInt &N2) {
936 return N1.urem(N2);
937 },
938 /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
939 }
940
941 TEST_F(ConstantRangeTest, SRem) {
942 EXPECT_EQ(Full.srem(Empty), Empty);
943 EXPECT_EQ(Empty.srem(Full), Empty);
944 // srem by zero is UB.
945 EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);
946 // srem by full range doesn't contain SignedMinValue.
947 EXPECT_EQ(Full.srem(Full), ConstantRange(APInt::getSignedMinValue(16) + 1,
948 APInt::getSignedMinValue(16)));
949
950 ConstantRange PosMod(APInt(16, 10), APInt(16, 21)); // [10, 20]
951 ConstantRange NegMod(APInt(16, -20), APInt(16, -9)); // [-20, -10]
952 ConstantRange IntMinMod(APInt::getSignedMinValue(16));
953
954 ConstantRange Expected(16, true);
955
956 // srem is bounded by abs(RHS) minus one.
957 ConstantRange PosLargeLHS(APInt(16, 0), APInt(16, 41));
958 Expected = ConstantRange(APInt(16, 0), APInt(16, 20));
959 EXPECT_EQ(PosLargeLHS.srem(PosMod), Expected);
960 EXPECT_EQ(PosLargeLHS.srem(NegMod), Expected);
961 ConstantRange NegLargeLHS(APInt(16, -40), APInt(16, 1));
962 Expected = ConstantRange(APInt(16, -19), APInt(16, 1));
963 EXPECT_EQ(NegLargeLHS.srem(PosMod), Expected);
964 EXPECT_EQ(NegLargeLHS.srem(NegMod), Expected);
965 ConstantRange PosNegLargeLHS(APInt(16, -32), APInt(16, 38));
966 Expected = ConstantRange(APInt(16, -19), APInt(16, 20));
967 EXPECT_EQ(PosNegLargeLHS.srem(PosMod), Expected);
968 EXPECT_EQ(PosNegLargeLHS.srem(NegMod), Expected);
969
970 // srem is bounded by LHS.
971 ConstantRange PosLHS(APInt(16, 0), APInt(16, 16));
972 EXPECT_EQ(PosLHS.srem(PosMod), PosLHS);
973 EXPECT_EQ(PosLHS.srem(NegMod), PosLHS);
974 EXPECT_EQ(PosLHS.srem(IntMinMod), PosLHS);
975 ConstantRange NegLHS(APInt(16, -15), APInt(16, 1));
976 EXPECT_EQ(NegLHS.srem(PosMod), NegLHS);
977 EXPECT_EQ(NegLHS.srem(NegMod), NegLHS);
978 EXPECT_EQ(NegLHS.srem(IntMinMod), NegLHS);
979 ConstantRange PosNegLHS(APInt(16, -12), APInt(16, 18));
980 EXPECT_EQ(PosNegLHS.srem(PosMod), PosNegLHS);
981 EXPECT_EQ(PosNegLHS.srem(NegMod), PosNegLHS);
982 EXPECT_EQ(PosNegLHS.srem(IntMinMod), PosNegLHS);
983
984 // srem is LHS if it is smaller than RHS.
985 ConstantRange PosSmallLHS(APInt(16, 3), APInt(16, 8));
986 EXPECT_EQ(PosSmallLHS.srem(PosMod), PosSmallLHS);
987 EXPECT_EQ(PosSmallLHS.srem(NegMod), PosSmallLHS);
988 EXPECT_EQ(PosSmallLHS.srem(IntMinMod), PosSmallLHS);
989 ConstantRange NegSmallLHS(APInt(16, -7), APInt(16, -2));
990 EXPECT_EQ(NegSmallLHS.srem(PosMod), NegSmallLHS);
991 EXPECT_EQ(NegSmallLHS.srem(NegMod), NegSmallLHS);
992 EXPECT_EQ(NegSmallLHS.srem(IntMinMod), NegSmallLHS);
993 ConstantRange PosNegSmallLHS(APInt(16, -3), APInt(16, 8));
994 EXPECT_EQ(PosNegSmallLHS.srem(PosMod), PosNegSmallLHS);
995 EXPECT_EQ(PosNegSmallLHS.srem(NegMod), PosNegSmallLHS);
996 EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);
997
998 // Example of a suboptimal result:
999 // [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
1000 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1001 .srem(ConstantRange(APInt(16, 10))),
1002 ConstantRange(APInt(16, 0), APInt(16, 10)));
1003
1004 TestSignedBinOpExhaustive(
1005 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1006 return CR1.srem(CR2);
1007 },
1008 [](const APInt &N1, const APInt &N2) {
1009 return N1.srem(N2);
1010 },
1011 /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
567 } 1012 }
568 1013
569 TEST_F(ConstantRangeTest, Shl) { 1014 TEST_F(ConstantRangeTest, Shl) {
1015 ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
1016 ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
570 EXPECT_EQ(Full.shl(Full), Full); 1017 EXPECT_EQ(Full.shl(Full), Full);
571 EXPECT_EQ(Full.shl(Empty), Empty); 1018 EXPECT_EQ(Full.shl(Empty), Empty);
572 EXPECT_EQ(Full.shl(One), Full); // TODO: [0, (-1 << 0xa) + 1) 1019 EXPECT_EQ(Full.shl(One), Full); // TODO: [0, (-1 << 0xa) + 1)
573 EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1) 1020 EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1)
574 EXPECT_EQ(Full.shl(Wrap), Full); 1021 EXPECT_EQ(Full.shl(Wrap), Full);
581 EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0) 1028 EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0)
582 EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1) 1029 EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1)
583 EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01) 1030 EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01)
584 EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1) 1031 EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1)
585 EXPECT_EQ(Wrap.shl(Wrap), Full); 1032 EXPECT_EQ(Wrap.shl(Wrap), Full);
1033 EXPECT_EQ(
1034 Some2.shl(ConstantRange(APInt(16, 0x1))),
1035 ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1));
1036 EXPECT_EQ(One.shl(WrapNullMax), Full);
586 } 1037 }
587 1038
588 TEST_F(ConstantRangeTest, Lshr) { 1039 TEST_F(ConstantRangeTest, Lshr) {
589 EXPECT_EQ(Full.lshr(Full), Full); 1040 EXPECT_EQ(Full.lshr(Full), Full);
590 EXPECT_EQ(Full.lshr(Empty), Empty); 1041 EXPECT_EQ(Full.lshr(Empty), Empty);
708 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 1159 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
709 Instruction::Add, C, OBO::NoSignedWrap); 1160 Instruction::Add, C, OBO::NoSignedWrap);
710 1161
711 EXPECT_FALSE(NSWRegion.isEmptySet()); 1162 EXPECT_FALSE(NSWRegion.isEmptySet());
712 1163
713 auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion(
714 Instruction::Add, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap);
715
716 EXPECT_FALSE(NoWrapRegion.isEmptySet());
717 EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion));
718
719 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E; 1164 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
720 ++I) { 1165 ++I) {
721 bool Overflow = false; 1166 bool Overflow = false;
722 (void)I.uadd_ov(C, Overflow); 1167 (void)I.uadd_ov(C, Overflow);
723 EXPECT_FALSE(Overflow); 1168 EXPECT_FALSE(Overflow);
727 ++I) { 1172 ++I) {
728 bool Overflow = false; 1173 bool Overflow = false;
729 (void)I.sadd_ov(C, Overflow); 1174 (void)I.sadd_ov(C, Overflow);
730 EXPECT_FALSE(Overflow); 1175 EXPECT_FALSE(Overflow);
731 } 1176 }
732
733 for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E;
734 ++I) {
735 bool Overflow = false;
736
737 (void)I.sadd_ov(C, Overflow);
738 EXPECT_FALSE(Overflow);
739
740 (void)I.uadd_ov(C, Overflow);
741 EXPECT_FALSE(Overflow);
742 }
743 } 1177 }
744 1178
745 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) { 1179 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
746 APInt C(4, Const, true /* = isSigned */); 1180 APInt C(4, Const, true /* = isSigned */);
747 1181
752 1186
753 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 1187 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
754 Instruction::Sub, C, OBO::NoSignedWrap); 1188 Instruction::Sub, C, OBO::NoSignedWrap);
755 1189
756 EXPECT_FALSE(NSWRegion.isEmptySet()); 1190 EXPECT_FALSE(NSWRegion.isEmptySet());
757
758 auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion(
759 Instruction::Sub, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap);
760
761 EXPECT_FALSE(NoWrapRegion.isEmptySet());
762 EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion));
763 1191
764 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E; 1192 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
765 ++I) { 1193 ++I) {
766 bool Overflow = false; 1194 bool Overflow = false;
767 (void)I.usub_ov(C, Overflow); 1195 (void)I.usub_ov(C, Overflow);
772 ++I) { 1200 ++I) {
773 bool Overflow = false; 1201 bool Overflow = false;
774 (void)I.ssub_ov(C, Overflow); 1202 (void)I.ssub_ov(C, Overflow);
775 EXPECT_FALSE(Overflow); 1203 EXPECT_FALSE(Overflow);
776 } 1204 }
777
778 for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E;
779 ++I) {
780 bool Overflow = false;
781
782 (void)I.ssub_ov(C, Overflow);
783 EXPECT_FALSE(Overflow);
784
785 (void)I.usub_ov(C, Overflow);
786 EXPECT_FALSE(Overflow);
787 }
788 } 1205 }
789 1206
790 auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 1207 auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
791 Instruction::Add, ConstantRange(32, /* isFullSet = */ true), 1208 Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
792 OBO::NoSignedWrap); 1209 OBO::NoSignedWrap);
809 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true), 1226 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
810 OBO::NoUnsignedWrap); 1227 OBO::NoUnsignedWrap);
811 EXPECT_TRUE(NUWForAllValues.isSingleElement() && 1228 EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
812 NUWForAllValues.getSingleElement()->isMaxValue()); 1229 NUWForAllValues.getSingleElement()->isMaxValue());
813 1230
814 auto NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
815 Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
816 OBO::NoUnsignedWrap | OBO::NoSignedWrap);
817 EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() &&
818 NUWAndNSWForAllValues.getSingleElement()->isMinValue());
819
820 NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
821 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
822 OBO::NoUnsignedWrap | OBO::NoSignedWrap);
823 EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() &&
824 NUWAndNSWForAllValues.getSingleElement()->isMaxValue());
825
826 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 1231 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
827 Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet()); 1232 Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
828 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 1233 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
829 Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet()); 1234 Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
830 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 1235 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
831 Instruction::Add, APInt(32, 0),
832 OBO::NoUnsignedWrap | OBO::NoSignedWrap).isFullSet());
833 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
834 Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet()); 1236 Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
835 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 1237 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
836 Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet()); 1238 Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
837 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
838 Instruction::Sub, APInt(32, 0),
839 OBO::NoUnsignedWrap | OBO::NoSignedWrap).isFullSet());
840 1239
841 ConstantRange OneToFive(APInt(32, 1), APInt(32, 6)); 1240 ConstantRange OneToFive(APInt(32, 1), APInt(32, 6));
842 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1241 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
843 Instruction::Add, OneToFive, OBO::NoSignedWrap), 1242 Instruction::Add, OneToFive, OBO::NoSignedWrap),
844 ConstantRange(APInt::getSignedMinValue(32), 1243 ConstantRange(APInt::getSignedMinValue(32),
845 APInt::getSignedMaxValue(32) - 4)); 1244 APInt::getSignedMaxValue(32) - 4));
846 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1245 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
847 Instruction::Add, OneToFive, OBO::NoUnsignedWrap), 1246 Instruction::Add, OneToFive, OBO::NoUnsignedWrap),
848 ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5)); 1247 ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));
849 EXPECT_EQ(
850 ConstantRange::makeGuaranteedNoWrapRegion(
851 Instruction::Add, OneToFive, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
852 ConstantRange(APInt::getMinValue(32), APInt::getSignedMaxValue(32) - 4));
853 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1248 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
854 Instruction::Sub, OneToFive, OBO::NoSignedWrap), 1249 Instruction::Sub, OneToFive, OBO::NoSignedWrap),
855 ConstantRange(APInt::getSignedMinValue(32) + 5, 1250 ConstantRange(APInt::getSignedMinValue(32) + 5,
856 APInt::getSignedMinValue(32))); 1251 APInt::getSignedMinValue(32)));
857 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1252 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
858 Instruction::Sub, OneToFive, OBO::NoUnsignedWrap), 1253 Instruction::Sub, OneToFive, OBO::NoUnsignedWrap),
859 ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32))); 1254 ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));
860 EXPECT_EQ(
861 ConstantRange::makeGuaranteedNoWrapRegion(
862 Instruction::Sub, OneToFive, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
863 ConstantRange(APInt::getMinValue(32) + 5, APInt::getSignedMinValue(32)));
864 1255
865 ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1)); 1256 ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1));
866 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1257 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
867 Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap), 1258 Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap),
868 ConstantRange(APInt::getSignedMinValue(32) + 5, 1259 ConstantRange(APInt::getSignedMinValue(32) + 5,
869 APInt::getSignedMinValue(32))); 1260 APInt::getSignedMinValue(32)));
870 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1261 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
871 Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap), 1262 Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
872 ConstantRange(APInt(32, 0), APInt(32, 2))); 1263 ConstantRange(APInt(32, 0), APInt(32, 2)));
873 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1264 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
874 Instruction::Add, MinusFiveToMinusTwo,
875 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
876 ConstantRange(APInt(32, 0), APInt(32, 2)));
877 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
878 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap), 1265 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap),
879 ConstantRange(APInt::getSignedMinValue(32), 1266 ConstantRange(APInt::getSignedMinValue(32),
880 APInt::getSignedMaxValue(32) - 4)); 1267 APInt::getSignedMaxValue(32) - 4));
881 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1268 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
882 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap), 1269 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
883 ConstantRange(APInt::getMaxValue(32) - 1,
884 APInt::getMinValue(32)));
885 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
886 Instruction::Sub, MinusFiveToMinusTwo,
887 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
888 ConstantRange(APInt::getMaxValue(32) - 1, 1270 ConstantRange(APInt::getMaxValue(32) - 1,
889 APInt::getMinValue(32))); 1271 APInt::getMinValue(32)));
890 1272
891 ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2)); 1273 ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2));
892 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1274 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
895 APInt::getSignedMinValue(32) - 1)); 1277 APInt::getSignedMinValue(32) - 1));
896 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1278 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
897 Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap), 1279 Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap),
898 ConstantRange(APInt(32, 0), APInt(32, 1))); 1280 ConstantRange(APInt(32, 0), APInt(32, 1)));
899 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1281 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
900 Instruction::Add, MinusOneToOne,
901 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
902 ConstantRange(APInt(32, 0), APInt(32, 1)));
903 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
904 Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap), 1282 Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap),
905 ConstantRange(APInt::getSignedMinValue(32) + 1, 1283 ConstantRange(APInt::getSignedMinValue(32) + 1,
906 APInt::getSignedMinValue(32) - 1)); 1284 APInt::getSignedMinValue(32) - 1));
907 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1285 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
908 Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap), 1286 Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap),
909 ConstantRange(APInt::getMaxValue(32),
910 APInt::getMinValue(32)));
911 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
912 Instruction::Sub, MinusOneToOne,
913 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
914 ConstantRange(APInt::getMaxValue(32), 1287 ConstantRange(APInt::getMaxValue(32),
915 APInt::getMinValue(32))); 1288 APInt::getMinValue(32)));
916 1289
917 ConstantRange One(APInt(32, 1), APInt(32, 2)); 1290 ConstantRange One(APInt(32, 1), APInt(32, 2));
918 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1291 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
920 ConstantRange(APInt::getSignedMinValue(32), 1293 ConstantRange(APInt::getSignedMinValue(32),
921 APInt::getSignedMaxValue(32))); 1294 APInt::getSignedMaxValue(32)));
922 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1295 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
923 Instruction::Add, One, OBO::NoUnsignedWrap), 1296 Instruction::Add, One, OBO::NoUnsignedWrap),
924 ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32))); 1297 ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
925 EXPECT_EQ(
926 ConstantRange::makeGuaranteedNoWrapRegion(
927 Instruction::Add, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
928 ConstantRange(APInt(32, 0), APInt::getSignedMaxValue(32)));
929 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1298 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
930 Instruction::Sub, One, OBO::NoSignedWrap), 1299 Instruction::Sub, One, OBO::NoSignedWrap),
931 ConstantRange(APInt::getSignedMinValue(32) + 1, 1300 ConstantRange(APInt::getSignedMinValue(32) + 1,
932 APInt::getSignedMinValue(32))); 1301 APInt::getSignedMinValue(32)));
933 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1302 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
934 Instruction::Sub, One, OBO::NoUnsignedWrap), 1303 Instruction::Sub, One, OBO::NoUnsignedWrap),
935 ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32))); 1304 ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
936 EXPECT_EQ( 1305 }
937 ConstantRange::makeGuaranteedNoWrapRegion( 1306
938 Instruction::Sub, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap), 1307 template<typename Fn>
939 ConstantRange(APInt::getMinValue(32) + 1, APInt::getSignedMinValue(32))); 1308 void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,
1309 unsigned NoWrapKind, Fn OverflowFn) {
1310 // When using 4 bits this test needs ~3s on a debug build.
1311 unsigned Bits = 3;
1312 EnumerateTwoConstantRanges(Bits,
1313 [&](const ConstantRange &CR1, const ConstantRange &CR2) {
1314 if (CR2.isEmptySet())
1315 return;
1316
1317 ConstantRange NoWrap =
1318 ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR2, NoWrapKind);
1319 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
1320 bool NoOverflow = true;
1321 bool Overflow = true;
1322 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
1323 if (OverflowFn(N1, N2))
1324 NoOverflow = false;
1325 else
1326 Overflow = false;
1327 });
1328 EXPECT_EQ(NoOverflow, NoWrap.contains(N1));
1329
1330 // The no-wrap range is exact for single-element ranges.
1331 if (CR2.isSingleElement()) {
1332 EXPECT_EQ(Overflow, !NoWrap.contains(N1));
1333 }
1334 });
1335 });
1336 }
1337
1338 // Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element
1339 // ranges also exact.
1340 TEST(ConstantRange, NoWrapRegionExhaustive) {
1341 TestNoWrapRegionExhaustive(
1342 Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap,
1343 [](const APInt &N1, const APInt &N2) {
1344 bool Overflow;
1345 (void) N1.uadd_ov(N2, Overflow);
1346 return Overflow;
1347 });
1348 TestNoWrapRegionExhaustive(
1349 Instruction::Add, OverflowingBinaryOperator::NoSignedWrap,
1350 [](const APInt &N1, const APInt &N2) {
1351 bool Overflow;
1352 (void) N1.sadd_ov(N2, Overflow);
1353 return Overflow;
1354 });
1355 TestNoWrapRegionExhaustive(
1356 Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap,
1357 [](const APInt &N1, const APInt &N2) {
1358 bool Overflow;
1359 (void) N1.usub_ov(N2, Overflow);
1360 return Overflow;
1361 });
1362 TestNoWrapRegionExhaustive(
1363 Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap,
1364 [](const APInt &N1, const APInt &N2) {
1365 bool Overflow;
1366 (void) N1.ssub_ov(N2, Overflow);
1367 return Overflow;
1368 });
1369 TestNoWrapRegionExhaustive(
1370 Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap,
1371 [](const APInt &N1, const APInt &N2) {
1372 bool Overflow;
1373 (void) N1.umul_ov(N2, Overflow);
1374 return Overflow;
1375 });
1376 TestNoWrapRegionExhaustive(
1377 Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap,
1378 [](const APInt &N1, const APInt &N2) {
1379 bool Overflow;
1380 (void) N1.smul_ov(N2, Overflow);
1381 return Overflow;
1382 });
940 } 1383 }
941 1384
942 TEST(ConstantRange, GetEquivalentICmp) { 1385 TEST(ConstantRange, GetEquivalentICmp) {
943 APInt RHS; 1386 APInt RHS;
944 CmpInst::Predicate Pred; 1387 CmpInst::Predicate Pred;
1019 ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS)); 1462 ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS));
1020 EXPECT_EQ(Pred, CmpInst::ICMP_NE); 1463 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1021 EXPECT_EQ(RHS, APInt(32, -1)); 1464 EXPECT_EQ(RHS, APInt(32, -1));
1022 } 1465 }
1023 1466
1467 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedSingleValue) {
1468 typedef OverflowingBinaryOperator OBO;
1469
1470 for (uint64_t I = std::numeric_limits<uint8_t>::min();
1471 I <= std::numeric_limits<uint8_t>::max(); I++) {
1472 auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
1473 Instruction::Mul, ConstantRange(APInt(8, I), APInt(8, I + 1)),
1474 OBO::NoUnsignedWrap);
1475
1476 for (uint64_t V = std::numeric_limits<uint8_t>::min();
1477 V <= std::numeric_limits<uint8_t>::max(); V++) {
1478 bool Overflow;
1479 (void)APInt(8, I).umul_ov(APInt(8, V), Overflow);
1480 EXPECT_EQ(!Overflow, Range.contains(APInt(8, V)));
1481 }
1482 }
1483 }
1484
1485 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedSingleValue) {
1486 typedef OverflowingBinaryOperator OBO;
1487
1488 for (int64_t I = std::numeric_limits<int8_t>::min();
1489 I <= std::numeric_limits<int8_t>::max(); I++) {
1490 auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
1491 Instruction::Mul,
1492 ConstantRange(APInt(8, I, /*isSigned=*/true),
1493 APInt(8, I + 1, /*isSigned=*/true)),
1494 OBO::NoSignedWrap);
1495
1496 for (int64_t V = std::numeric_limits<int8_t>::min();
1497 V <= std::numeric_limits<int8_t>::max(); V++) {
1498 bool Overflow;
1499 (void)APInt(8, I, /*isSigned=*/true)
1500 .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
1501 EXPECT_EQ(!Overflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
1502 }
1503 }
1504 }
1505
1506 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedRange) {
1507 typedef OverflowingBinaryOperator OBO;
1508
1509 for (uint64_t Lo = std::numeric_limits<uint8_t>::min();
1510 Lo <= std::numeric_limits<uint8_t>::max(); Lo++) {
1511 for (uint64_t Hi = Lo; Hi <= std::numeric_limits<uint8_t>::max(); Hi++) {
1512 EXPECT_EQ(
1513 ConstantRange::makeGuaranteedNoWrapRegion(
1514 Instruction::Mul, ConstantRange(APInt(8, Lo), APInt(8, Hi + 1)),
1515 OBO::NoUnsignedWrap),
1516 ConstantRange::makeGuaranteedNoWrapRegion(
1517 Instruction::Mul, ConstantRange(APInt(8, Hi), APInt(8, Hi + 1)),
1518 OBO::NoUnsignedWrap));
1519 }
1520 }
1521 }
1522
1523 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedRange) {
1524 typedef OverflowingBinaryOperator OBO;
1525
1526 int Lo = -12, Hi = 16;
1527 auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
1528 Instruction::Mul,
1529 ConstantRange(APInt(8, Lo, /*isSigned=*/true),
1530 APInt(8, Hi + 1, /*isSigned=*/true)),
1531 OBO::NoSignedWrap);
1532
1533 for (int64_t V = std::numeric_limits<int8_t>::min();
1534 V <= std::numeric_limits<int8_t>::max(); V++) {
1535 bool AnyOverflow = false;
1536 for (int64_t I = Lo; I <= Hi; I++) {
1537 bool Overflow;
1538 (void)APInt(8, I, /*isSigned=*/true)
1539 .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
1540 AnyOverflow |= Overflow;
1541 }
1542 EXPECT_EQ(!AnyOverflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
1543 }
1544 }
1545
1546 #define EXPECT_MAY_OVERFLOW(op) \
1547 EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))
1548 #define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \
1549 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))
1550 #define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \
1551 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (op))
1552 #define EXPECT_NEVER_OVERFLOWS(op) \
1553 EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))
1554
1555 TEST_F(ConstantRangeTest, UnsignedAddOverflow) {
1556 // Ill-defined - may overflow is a conservative result.
1557 EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty));
1558 EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some));
1559
1560 // Never overflow despite one full/wrap set.
1561 ConstantRange Zero(APInt::getNullValue(16));
1562 EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero));
1563 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero));
1564 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full));
1565 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap));
1566
1567 // But usually full/wrap always may overflow.
1568 EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One));
1569 EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One));
1570 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full));
1571 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap));
1572
1573 ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00));
1574 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
1575 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
1576 EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1));
1577 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2));
1578 EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A));
1579 EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A));
1580
1581 ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400));
1582 ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400));
1583 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1));
1584 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.unsignedAddMayOverflow(C2));
1585 EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A));
1586 EXPECT_ALWAYS_OVERFLOWS_HIGH(C2.unsignedAddMayOverflow(A));
1587 }
1588
1589 TEST_F(ConstantRangeTest, UnsignedSubOverflow) {
1590 // Ill-defined - may overflow is a conservative result.
1591 EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty));
1592 EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some));
1593
1594 // Never overflow despite one full/wrap set.
1595 ConstantRange Zero(APInt::getNullValue(16));
1596 ConstantRange Max(APInt::getAllOnesValue(16));
1597 EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero));
1598 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero));
1599 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full));
1600 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap));
1601
1602 // But usually full/wrap always may overflow.
1603 EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One));
1604 EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One));
1605 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full));
1606 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap));
1607
1608 ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100));
1609 ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200));
1610 EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A));
1611 EXPECT_ALWAYS_OVERFLOWS_LOW(A.unsignedSubMayOverflow(B));
1612
1613 ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101));
1614 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
1615 EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1));
1616 EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1));
1617
1618 ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102));
1619 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
1620 EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2));
1621 EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2));
1622 }
1623
1624 TEST_F(ConstantRangeTest, SignedAddOverflow) {
1625 // Ill-defined - may overflow is a conservative result.
1626 EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty));
1627 EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some));
1628
1629 // Never overflow despite one full/wrap set.
1630 ConstantRange Zero(APInt::getNullValue(16));
1631 EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero));
1632 EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero));
1633 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full));
1634 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap));
1635
1636 // But usually full/wrap always may overflow.
1637 EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One));
1638 EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One));
1639 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full));
1640 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap));
1641
1642 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
1643 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
1644 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
1645 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1));
1646 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2));
1647 ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201));
1648 ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202));
1649 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3));
1650 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4));
1651 ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400));
1652 ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400));
1653 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5));
1654 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedAddMayOverflow(B6));
1655
1656 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
1657 ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00));
1658 ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00));
1659 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1));
1660 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2));
1661 ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000));
1662 ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000));
1663 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3));
1664 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4));
1665 ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02));
1666 ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01));
1667 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5));
1668 EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedAddMayOverflow(D6));
1669
1670 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
1671 EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E));
1672 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000));
1673 EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F));
1674 }
1675
1676 TEST_F(ConstantRangeTest, SignedSubOverflow) {
1677 // Ill-defined - may overflow is a conservative result.
1678 EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty));
1679 EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some));
1680
1681 // Never overflow despite one full/wrap set.
1682 ConstantRange Zero(APInt::getNullValue(16));
1683 EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero));
1684 EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero));
1685
1686 // But usually full/wrap always may overflow.
1687 EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One));
1688 EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One));
1689 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full));
1690 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap));
1691
1692 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
1693 ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00));
1694 ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00));
1695 EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1));
1696 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2));
1697 ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02));
1698 ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01));
1699 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3));
1700 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedSubMayOverflow(B4));
1701
1702 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
1703 ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201));
1704 ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202));
1705 EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1));
1706 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2));
1707 ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400));
1708 ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400));
1709 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3));
1710 EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedSubMayOverflow(D4));
1711
1712 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
1713 EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E));
1714 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001));
1715 EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F));
1716 }
1717
1718 template<typename Fn1, typename Fn2>
1719 static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) {
1720 // Constant range overflow checks are tested exhaustively on 4-bit numbers.
1721 unsigned Bits = 4;
1722 EnumerateTwoConstantRanges(Bits, [=](const ConstantRange &CR1,
1723 const ConstantRange &CR2) {
1724 // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the
1725 // operations have overflow / have no overflow.
1726 bool RangeHasOverflowLow = false;
1727 bool RangeHasOverflowHigh = false;
1728 bool RangeHasNoOverflow = false;
1729 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
1730 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
1731 bool IsOverflowHigh;
1732 if (!OverflowFn(IsOverflowHigh, N1, N2)) {
1733 RangeHasNoOverflow = true;
1734 return;
1735 }
1736
1737 if (IsOverflowHigh)
1738 RangeHasOverflowHigh = true;
1739 else
1740 RangeHasOverflowLow = true;
1741 });
1742 });
1743
1744 ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2);
1745 switch (OR) {
1746 case ConstantRange::OverflowResult::AlwaysOverflowsLow:
1747 EXPECT_TRUE(RangeHasOverflowLow);
1748 EXPECT_FALSE(RangeHasOverflowHigh);
1749 EXPECT_FALSE(RangeHasNoOverflow);
1750 break;
1751 case ConstantRange::OverflowResult::AlwaysOverflowsHigh:
1752 EXPECT_TRUE(RangeHasOverflowHigh);
1753 EXPECT_FALSE(RangeHasOverflowLow);
1754 EXPECT_FALSE(RangeHasNoOverflow);
1755 break;
1756 case ConstantRange::OverflowResult::NeverOverflows:
1757 EXPECT_FALSE(RangeHasOverflowLow);
1758 EXPECT_FALSE(RangeHasOverflowHigh);
1759 EXPECT_TRUE(RangeHasNoOverflow);
1760 break;
1761 case ConstantRange::OverflowResult::MayOverflow:
1762 // We return MayOverflow for empty sets as a conservative result,
1763 // but of course neither the RangeHasOverflow nor the
1764 // RangeHasNoOverflow flags will be set.
1765 if (CR1.isEmptySet() || CR2.isEmptySet())
1766 break;
1767
1768 EXPECT_TRUE(RangeHasOverflowLow || RangeHasOverflowHigh);
1769 EXPECT_TRUE(RangeHasNoOverflow);
1770 break;
1771 }
1772 });
1773 }
1774
1775 TEST_F(ConstantRangeTest, UnsignedAddOverflowExhaustive) {
1776 TestOverflowExhaustive(
1777 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
1778 bool Overflow;
1779 (void) N1.uadd_ov(N2, Overflow);
1780 IsOverflowHigh = true;
1781 return Overflow;
1782 },
1783 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1784 return CR1.unsignedAddMayOverflow(CR2);
1785 });
1786 }
1787
1788 TEST_F(ConstantRangeTest, UnsignedSubOverflowExhaustive) {
1789 TestOverflowExhaustive(
1790 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
1791 bool Overflow;
1792 (void) N1.usub_ov(N2, Overflow);
1793 IsOverflowHigh = false;
1794 return Overflow;
1795 },
1796 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1797 return CR1.unsignedSubMayOverflow(CR2);
1798 });
1799 }
1800
1801 TEST_F(ConstantRangeTest, UnsignedMulOverflowExhaustive) {
1802 TestOverflowExhaustive(
1803 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
1804 bool Overflow;
1805 (void) N1.umul_ov(N2, Overflow);
1806 IsOverflowHigh = true;
1807 return Overflow;
1808 },
1809 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1810 return CR1.unsignedMulMayOverflow(CR2);
1811 });
1812 }
1813
1814 TEST_F(ConstantRangeTest, SignedAddOverflowExhaustive) {
1815 TestOverflowExhaustive(
1816 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
1817 bool Overflow;
1818 (void) N1.sadd_ov(N2, Overflow);
1819 IsOverflowHigh = N1.isNonNegative();
1820 return Overflow;
1821 },
1822 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1823 return CR1.signedAddMayOverflow(CR2);
1824 });
1825 }
1826
1827 TEST_F(ConstantRangeTest, SignedSubOverflowExhaustive) {
1828 TestOverflowExhaustive(
1829 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
1830 bool Overflow;
1831 (void) N1.ssub_ov(N2, Overflow);
1832 IsOverflowHigh = N1.isNonNegative();
1833 return Overflow;
1834 },
1835 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1836 return CR1.signedSubMayOverflow(CR2);
1837 });
1838 }
1839
1840 TEST_F(ConstantRangeTest, FromKnownBits) {
1841 KnownBits Unknown(16);
1842 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false));
1843 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true));
1844
1845 // .10..01. -> unsigned 01000010 (66) to 11011011 (219)
1846 // -> signed 11000010 (194) to 01011011 (91)
1847 KnownBits Known(8);
1848 Known.Zero = 36;
1849 Known.One = 66;
1850 ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1));
1851 ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1));
1852 EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false));
1853 EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true));
1854
1855 // 1.10.10. -> 10100100 (164) to 11101101 (237)
1856 Known.Zero = 18;
1857 Known.One = 164;
1858 ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1));
1859 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false));
1860 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true));
1861
1862 // 01.0.1.0 -> 01000100 (68) to 01101110 (110)
1863 Known.Zero = 145;
1864 Known.One = 68;
1865 ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1));
1866 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false));
1867 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true));
1868 }
1869
1870 TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {
1871 unsigned Bits = 4;
1872 unsigned Max = 1 << Bits;
1873 KnownBits Known(Bits);
1874 for (unsigned Zero = 0; Zero < Max; ++Zero) {
1875 for (unsigned One = 0; One < Max; ++One) {
1876 Known.Zero = Zero;
1877 Known.One = One;
1878 if (Known.hasConflict() || Known.isUnknown())
1879 continue;
1880
1881 APInt MinUnsigned = APInt::getMaxValue(Bits);
1882 APInt MaxUnsigned = APInt::getMinValue(Bits);
1883 APInt MinSigned = APInt::getSignedMaxValue(Bits);
1884 APInt MaxSigned = APInt::getSignedMinValue(Bits);
1885 for (unsigned N = 0; N < Max; ++N) {
1886 APInt Num(Bits, N);
1887 if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
1888 continue;
1889
1890 if (Num.ult(MinUnsigned)) MinUnsigned = Num;
1891 if (Num.ugt(MaxUnsigned)) MaxUnsigned = Num;
1892 if (Num.slt(MinSigned)) MinSigned = Num;
1893 if (Num.sgt(MaxSigned)) MaxSigned = Num;
1894 }
1895
1896 ConstantRange UnsignedCR(MinUnsigned, MaxUnsigned + 1);
1897 ConstantRange SignedCR(MinSigned, MaxSigned + 1);
1898 EXPECT_EQ(UnsignedCR, ConstantRange::fromKnownBits(Known, false));
1899 EXPECT_EQ(SignedCR, ConstantRange::fromKnownBits(Known, true));
1900 }
1901 }
1902 }
1903
1904 TEST_F(ConstantRangeTest, Negative) {
1905 // All elements in an empty set (of which there are none) are both negative
1906 // and non-negative. Empty & full sets checked explicitly for clarity, but
1907 // they are also covered by the exhaustive test below.
1908 EXPECT_TRUE(Empty.isAllNegative());
1909 EXPECT_TRUE(Empty.isAllNonNegative());
1910 EXPECT_FALSE(Full.isAllNegative());
1911 EXPECT_FALSE(Full.isAllNonNegative());
1912
1913 unsigned Bits = 4;
1914 EnumerateConstantRanges(Bits, [](const ConstantRange &CR) {
1915 bool AllNegative = true;
1916 bool AllNonNegative = true;
1917 ForeachNumInConstantRange(CR, [&](const APInt &N) {
1918 if (!N.isNegative())
1919 AllNegative = false;
1920 if (!N.isNonNegative())
1921 AllNonNegative = false;
1922 });
1923 assert((CR.isEmptySet() || !AllNegative || !AllNonNegative) &&
1924 "Only empty set can be both all negative and all non-negative");
1925
1926 EXPECT_EQ(AllNegative, CR.isAllNegative());
1927 EXPECT_EQ(AllNonNegative, CR.isAllNonNegative());
1928 });
1929 }
1930
1931 TEST_F(ConstantRangeTest, UAddSat) {
1932 TestUnsignedBinOpExhaustive(
1933 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1934 return CR1.uadd_sat(CR2);
1935 },
1936 [](const APInt &N1, const APInt &N2) {
1937 return N1.uadd_sat(N2);
1938 });
1939 }
1940
1941 TEST_F(ConstantRangeTest, USubSat) {
1942 TestUnsignedBinOpExhaustive(
1943 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1944 return CR1.usub_sat(CR2);
1945 },
1946 [](const APInt &N1, const APInt &N2) {
1947 return N1.usub_sat(N2);
1948 });
1949 }
1950
1951 TEST_F(ConstantRangeTest, SAddSat) {
1952 TestSignedBinOpExhaustive(
1953 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1954 return CR1.sadd_sat(CR2);
1955 },
1956 [](const APInt &N1, const APInt &N2) {
1957 return N1.sadd_sat(N2);
1958 });
1959 }
1960
1961 TEST_F(ConstantRangeTest, SSubSat) {
1962 TestSignedBinOpExhaustive(
1963 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1964 return CR1.ssub_sat(CR2);
1965 },
1966 [](const APInt &N1, const APInt &N2) {
1967 return N1.ssub_sat(N2);
1968 });
1969 }
1970
1971 TEST_F(ConstantRangeTest, Abs) {
1972 unsigned Bits = 4;
1973 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
1974 // We're working with unsigned integers here, because it makes the signed
1975 // min case non-wrapping.
1976 APInt Min = APInt::getMaxValue(Bits);
1977 APInt Max = APInt::getMinValue(Bits);
1978 ForeachNumInConstantRange(CR, [&](const APInt &N) {
1979 APInt AbsN = N.abs();
1980 if (AbsN.ult(Min))
1981 Min = AbsN;
1982 if (AbsN.ugt(Max))
1983 Max = AbsN;
1984 });
1985
1986 ConstantRange AbsCR = CR.abs();
1987 if (Min.ugt(Max)) {
1988 EXPECT_TRUE(AbsCR.isEmptySet());
1989 return;
1990 }
1991
1992 ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
1993 EXPECT_EQ(Exact, AbsCR);
1994 });
1995 }
1996
1024 } // anonymous namespace 1997 } // anonymous namespace