llvm-project

Форк
0
/
ConstantRangeTest.cpp 
2847 строк · 110.6 Кб
1
//===- ConstantRangeTest.cpp - ConstantRange 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/IR/ConstantRange.h"
10
#include "llvm/ADT/BitVector.h"
11
#include "llvm/ADT/Sequence.h"
12
#include "llvm/ADT/SmallBitVector.h"
13
#include "llvm/IR/Instructions.h"
14
#include "llvm/IR/Operator.h"
15
#include "llvm/Support/KnownBits.h"
16
#include "gtest/gtest.h"
17

18
using namespace llvm;
19

20
namespace {
21

22
class ConstantRangeTest : public ::testing::Test {
23
protected:
24
  static ConstantRange Full;
25
  static ConstantRange Empty;
26
  static ConstantRange One;
27
  static ConstantRange Some;
28
  static ConstantRange Wrap;
29
};
30

31
template<typename Fn>
32
static void EnumerateAPInts(unsigned Bits, Fn TestFn) {
33
  APInt N(Bits, 0);
34
  do {
35
    TestFn(N);
36
  } while (++N != 0);
37
}
38

39
template<typename Fn>
40
static void EnumerateConstantRanges(unsigned Bits, Fn TestFn) {
41
  unsigned Max = 1 << Bits;
42
  for (unsigned Lo = 0; Lo < Max; Lo++) {
43
    for (unsigned Hi = 0; Hi < Max; Hi++) {
44
      // Enforce ConstantRange invariant.
45
      if (Lo == Hi && Lo != 0 && Lo != Max - 1)
46
        continue;
47

48
      ConstantRange CR(APInt(Bits, Lo), APInt(Bits, Hi));
49
      TestFn(CR);
50
    }
51
  }
52
}
53

54
template <typename Fn>
55
static void EnumerateInterestingConstantRanges(Fn TestFn) {
56
  // Check 1 bit ranges, because they may have special cases.
57
  EnumerateConstantRanges(/* Bits */ 1, TestFn);
58
  // Check 4 bit ranges to have decent coverage without being too slow.
59
  EnumerateConstantRanges(/* Bits */ 4, TestFn);
60
}
61

62
template <typename Fn>
63
static void EnumerateTwoInterestingConstantRanges(Fn TestFn) {
64
  for (unsigned Bits : {1, 4}) {
65
    EnumerateConstantRanges(Bits, [&](const ConstantRange &CR1) {
66
      EnumerateConstantRanges(
67
          Bits, [&](const ConstantRange &CR2) { TestFn(CR1, CR2); });
68
    });
69
  }
70
}
71

72
template <typename Fn>
73
static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) {
74
  if (!CR.isEmptySet()) {
75
    APInt N = CR.getLower();
76
    do TestFn(N);
77
    while (++N != CR.getUpper());
78
  }
79
}
80

81
using PreferFn = llvm::function_ref<bool(const ConstantRange &,
82
                                         const ConstantRange &)>;
83

84
bool PreferSmallest(const ConstantRange &CR1, const ConstantRange &CR2) {
85
  return CR1.isSizeStrictlySmallerThan(CR2);
86
}
87

88
bool PreferSmallestUnsigned(const ConstantRange &CR1,
89
                            const ConstantRange &CR2) {
90
  if (CR1.isWrappedSet() != CR2.isWrappedSet())
91
    return CR1.isWrappedSet() < CR2.isWrappedSet();
92
  return PreferSmallest(CR1, CR2);
93
}
94

95
bool PreferSmallestSigned(const ConstantRange &CR1, const ConstantRange &CR2) {
96
  if (CR1.isSignWrappedSet() != CR2.isSignWrappedSet())
97
    return CR1.isSignWrappedSet() < CR2.isSignWrappedSet();
98
  return PreferSmallest(CR1, CR2);
99
}
100

101
bool PreferSmallestNonFullUnsigned(const ConstantRange &CR1,
102
                                   const ConstantRange &CR2) {
103
  if (CR1.isFullSet() != CR2.isFullSet())
104
    return CR1.isFullSet() < CR2.isFullSet();
105
  return PreferSmallestUnsigned(CR1, CR2);
106
}
107

108
bool PreferSmallestNonFullSigned(const ConstantRange &CR1,
109
                                 const ConstantRange &CR2) {
110
  if (CR1.isFullSet() != CR2.isFullSet())
111
    return CR1.isFullSet() < CR2.isFullSet();
112
  return PreferSmallestSigned(CR1, CR2);
113
}
114

115
testing::AssertionResult rangeContains(const ConstantRange &CR, const APInt &N,
116
                                       ArrayRef<ConstantRange> Inputs) {
117
  if (CR.contains(N))
118
    return testing::AssertionSuccess();
119

120
  testing::AssertionResult Result = testing::AssertionFailure();
121
  Result << CR << " does not contain " << N << " for inputs: ";
122
  for (const ConstantRange &Input : Inputs)
123
    Result << Input << ", ";
124
  return Result;
125
}
126

127
// Check whether constant range CR is an optimal approximation of the set
128
// Elems under the given PreferenceFn. The preference function should return
129
// true if the first range argument is strictly preferred to the second one.
130
static void TestRange(const ConstantRange &CR, const SmallBitVector &Elems,
131
                      PreferFn PreferenceFn, ArrayRef<ConstantRange> Inputs,
132
                      bool CheckOptimality = true) {
133
  unsigned BitWidth = CR.getBitWidth();
134

135
  // Check conservative correctness.
136
  for (unsigned Elem : Elems.set_bits()) {
137
    EXPECT_TRUE(rangeContains(CR, APInt(BitWidth, Elem), Inputs));
138
  }
139

140
  if (!CheckOptimality)
141
    return;
142

143
  // Make sure we have at least one element for the code below.
144
  if (Elems.none()) {
145
    EXPECT_TRUE(CR.isEmptySet());
146
    return;
147
  }
148

149
  auto NotPreferred = [&](const ConstantRange &PossibleCR) {
150
    if (!PreferenceFn(PossibleCR, CR))
151
      return testing::AssertionSuccess();
152

153
    testing::AssertionResult Result = testing::AssertionFailure();
154
    Result << "Inputs = ";
155
    for (const ConstantRange &Input : Inputs)
156
      Result << Input << ", ";
157
    Result << "CR = " << CR << ", BetterCR = " << PossibleCR;
158
    return Result;
159
  };
160

161
  // Look at all pairs of adjacent elements and the slack-free ranges
162
  // [Elem, PrevElem] they imply. Check that none of the ranges are strictly
163
  // preferred over the computed range (they may have equal preference).
164
  int FirstElem = Elems.find_first();
165
  int PrevElem = FirstElem, Elem;
166
  do {
167
    Elem = Elems.find_next(PrevElem);
168
    if (Elem < 0)
169
      Elem = FirstElem; // Wrap around to first element.
170

171
    ConstantRange PossibleCR =
172
        ConstantRange::getNonEmpty(APInt(BitWidth, Elem),
173
                                   APInt(BitWidth, PrevElem) + 1);
174
    // We get a full range any time PrevElem and Elem are adjacent. Avoid
175
    // repeated checks by skipping here, and explicitly checking below instead.
176
    if (!PossibleCR.isFullSet()) {
177
      EXPECT_TRUE(NotPreferred(PossibleCR));
178
    }
179

180
    PrevElem = Elem;
181
  } while (Elem != FirstElem);
182

183
  EXPECT_TRUE(NotPreferred(ConstantRange::getFull(BitWidth)));
184
}
185

186
using UnaryRangeFn = llvm::function_ref<ConstantRange(const ConstantRange &)>;
187
using UnaryIntFn = llvm::function_ref<std::optional<APInt>(const APInt &)>;
188

189
static void TestUnaryOpExhaustive(UnaryRangeFn RangeFn, UnaryIntFn IntFn,
190
                                  PreferFn PreferenceFn = PreferSmallest) {
191
  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
192
    SmallBitVector Elems(1 << CR.getBitWidth());
193
    ForeachNumInConstantRange(CR, [&](const APInt &N) {
194
      if (std::optional<APInt> ResultN = IntFn(N))
195
        Elems.set(ResultN->getZExtValue());
196
    });
197
    TestRange(RangeFn(CR), Elems, PreferenceFn, {CR});
198
  });
199
}
200

201
using BinaryRangeFn = llvm::function_ref<ConstantRange(const ConstantRange &,
202
                                                       const ConstantRange &)>;
203
using BinaryIntFn =
204
    llvm::function_ref<std::optional<APInt>(const APInt &, const APInt &)>;
205
using BinaryCheckFn = llvm::function_ref<bool(const ConstantRange &,
206
                                              const ConstantRange &)>;
207

208
static bool CheckAll(const ConstantRange &, const ConstantRange &) {
209
  return true;
210
}
211

212
static bool CheckCorrectnessOnly(const ConstantRange &, const ConstantRange &) {
213
  return false;
214
}
215

216
static bool CheckSingleElementsOnly(const ConstantRange &CR1,
217
                                    const ConstantRange &CR2) {
218
  return CR1.isSingleElement() && CR2.isSingleElement();
219
}
220

221
static bool CheckNonWrappedOnly(const ConstantRange &CR1,
222
                                const ConstantRange &CR2) {
223
  return !CR1.isWrappedSet() && !CR2.isWrappedSet();
224
}
225

226
static bool CheckNonSignWrappedOnly(const ConstantRange &CR1,
227
                                    const ConstantRange &CR2) {
228
  return !CR1.isSignWrappedSet() && !CR2.isSignWrappedSet();
229
}
230

231
static bool CheckNonWrappedOrSignWrappedOnly(const ConstantRange &CR1,
232
                                             const ConstantRange &CR2) {
233
  return !CR1.isWrappedSet() && !CR1.isSignWrappedSet() &&
234
         !CR2.isWrappedSet() && !CR2.isSignWrappedSet();
235
}
236

237
// CheckFn determines whether optimality is checked for a given range pair.
238
// Correctness is always checked.
239
static void TestBinaryOpExhaustive(BinaryRangeFn RangeFn, BinaryIntFn IntFn,
240
                                   PreferFn PreferenceFn = PreferSmallest,
241
                                   BinaryCheckFn CheckFn = CheckAll) {
242
  EnumerateTwoInterestingConstantRanges(
243
      [&](const ConstantRange &CR1, const ConstantRange &CR2) {
244
        SmallBitVector Elems(1 << CR1.getBitWidth());
245
        ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
246
          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
247
            if (std::optional<APInt> ResultN = IntFn(N1, N2))
248
              Elems.set(ResultN->getZExtValue());
249
          });
250
        });
251
        TestRange(RangeFn(CR1, CR2), Elems, PreferenceFn, {CR1, CR2},
252
                  CheckFn(CR1, CR2));
253
      });
254
}
255

256
ConstantRange ConstantRangeTest::Full(16, true);
257
ConstantRange ConstantRangeTest::Empty(16, false);
258
ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
259
ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
260
ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
261

262
TEST_F(ConstantRangeTest, Basics) {
263
  EXPECT_TRUE(Full.isFullSet());
264
  EXPECT_FALSE(Full.isEmptySet());
265
  EXPECT_TRUE(Full.inverse().isEmptySet());
266
  EXPECT_FALSE(Full.isWrappedSet());
267
  EXPECT_TRUE(Full.contains(APInt(16, 0x0)));
268
  EXPECT_TRUE(Full.contains(APInt(16, 0x9)));
269
  EXPECT_TRUE(Full.contains(APInt(16, 0xa)));
270
  EXPECT_TRUE(Full.contains(APInt(16, 0xaa9)));
271
  EXPECT_TRUE(Full.contains(APInt(16, 0xaaa)));
272

273
  EXPECT_FALSE(Empty.isFullSet());
274
  EXPECT_TRUE(Empty.isEmptySet());
275
  EXPECT_TRUE(Empty.inverse().isFullSet());
276
  EXPECT_FALSE(Empty.isWrappedSet());
277
  EXPECT_FALSE(Empty.contains(APInt(16, 0x0)));
278
  EXPECT_FALSE(Empty.contains(APInt(16, 0x9)));
279
  EXPECT_FALSE(Empty.contains(APInt(16, 0xa)));
280
  EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9)));
281
  EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa)));
282

283
  EXPECT_FALSE(One.isFullSet());
284
  EXPECT_FALSE(One.isEmptySet());
285
  EXPECT_FALSE(One.isWrappedSet());
286
  EXPECT_FALSE(One.contains(APInt(16, 0x0)));
287
  EXPECT_FALSE(One.contains(APInt(16, 0x9)));
288
  EXPECT_TRUE(One.contains(APInt(16, 0xa)));
289
  EXPECT_FALSE(One.contains(APInt(16, 0xaa9)));
290
  EXPECT_FALSE(One.contains(APInt(16, 0xaaa)));
291
  EXPECT_FALSE(One.inverse().contains(APInt(16, 0xa)));
292

293
  EXPECT_FALSE(Some.isFullSet());
294
  EXPECT_FALSE(Some.isEmptySet());
295
  EXPECT_FALSE(Some.isWrappedSet());
296
  EXPECT_FALSE(Some.contains(APInt(16, 0x0)));
297
  EXPECT_FALSE(Some.contains(APInt(16, 0x9)));
298
  EXPECT_TRUE(Some.contains(APInt(16, 0xa)));
299
  EXPECT_TRUE(Some.contains(APInt(16, 0xaa9)));
300
  EXPECT_FALSE(Some.contains(APInt(16, 0xaaa)));
301

302
  EXPECT_FALSE(Wrap.isFullSet());
303
  EXPECT_FALSE(Wrap.isEmptySet());
304
  EXPECT_TRUE(Wrap.isWrappedSet());
305
  EXPECT_TRUE(Wrap.contains(APInt(16, 0x0)));
306
  EXPECT_TRUE(Wrap.contains(APInt(16, 0x9)));
307
  EXPECT_FALSE(Wrap.contains(APInt(16, 0xa)));
308
  EXPECT_FALSE(Wrap.contains(APInt(16, 0xaa9)));
309
  EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa)));
310
}
311

312
TEST_F(ConstantRangeTest, Equality) {
313
  EXPECT_EQ(Full, Full);
314
  EXPECT_EQ(Empty, Empty);
315
  EXPECT_EQ(One, One);
316
  EXPECT_EQ(Some, Some);
317
  EXPECT_EQ(Wrap, Wrap);
318
  EXPECT_NE(Full, Empty);
319
  EXPECT_NE(Full, One);
320
  EXPECT_NE(Full, Some);
321
  EXPECT_NE(Full, Wrap);
322
  EXPECT_NE(Empty, One);
323
  EXPECT_NE(Empty, Some);
324
  EXPECT_NE(Empty, Wrap);
325
  EXPECT_NE(One, Some);
326
  EXPECT_NE(One, Wrap);
327
  EXPECT_NE(Some, Wrap);
328
}
329

330
TEST_F(ConstantRangeTest, SingleElement) {
331
  EXPECT_EQ(Full.getSingleElement(), static_cast<APInt *>(nullptr));
332
  EXPECT_EQ(Empty.getSingleElement(), static_cast<APInt *>(nullptr));
333
  EXPECT_EQ(Full.getSingleMissingElement(), static_cast<APInt *>(nullptr));
334
  EXPECT_EQ(Empty.getSingleMissingElement(), static_cast<APInt *>(nullptr));
335

336
  EXPECT_EQ(*One.getSingleElement(), APInt(16, 0xa));
337
  EXPECT_EQ(Some.getSingleElement(), static_cast<APInt *>(nullptr));
338
  EXPECT_EQ(Wrap.getSingleElement(), static_cast<APInt *>(nullptr));
339

340
  EXPECT_EQ(One.getSingleMissingElement(), static_cast<APInt *>(nullptr));
341
  EXPECT_EQ(Some.getSingleMissingElement(), static_cast<APInt *>(nullptr));
342

343
  ConstantRange OneInverse = One.inverse();
344
  EXPECT_EQ(*OneInverse.getSingleMissingElement(), *One.getSingleElement());
345

346
  EXPECT_FALSE(Full.isSingleElement());
347
  EXPECT_FALSE(Empty.isSingleElement());
348
  EXPECT_TRUE(One.isSingleElement());
349
  EXPECT_FALSE(Some.isSingleElement());
350
  EXPECT_FALSE(Wrap.isSingleElement());
351
}
352

353
TEST_F(ConstantRangeTest, GetMinsAndMaxes) {
354
  EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX));
355
  EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa));
356
  EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9));
357
  EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX));
358

359
  EXPECT_EQ(Full.getUnsignedMin(), APInt(16, 0));
360
  EXPECT_EQ(One.getUnsignedMin(), APInt(16, 0xa));
361
  EXPECT_EQ(Some.getUnsignedMin(), APInt(16, 0xa));
362
  EXPECT_EQ(Wrap.getUnsignedMin(), APInt(16, 0));
363

364
  EXPECT_EQ(Full.getSignedMax(), APInt(16, INT16_MAX));
365
  EXPECT_EQ(One.getSignedMax(), APInt(16, 0xa));
366
  EXPECT_EQ(Some.getSignedMax(), APInt(16, 0xaa9));
367
  EXPECT_EQ(Wrap.getSignedMax(), APInt(16, INT16_MAX));
368

369
  EXPECT_EQ(Full.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
370
  EXPECT_EQ(One.getSignedMin(), APInt(16, 0xa));
371
  EXPECT_EQ(Some.getSignedMin(), APInt(16, 0xa));
372
  EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
373

374
  // Found by Klee
375
  EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),
376
            APInt(4, 7));
377
}
378

379
TEST_F(ConstantRangeTest, SignWrapped) {
380
  EXPECT_FALSE(Full.isSignWrappedSet());
381
  EXPECT_FALSE(Empty.isSignWrappedSet());
382
  EXPECT_FALSE(One.isSignWrappedSet());
383
  EXPECT_FALSE(Some.isSignWrappedSet());
384
  EXPECT_TRUE(Wrap.isSignWrappedSet());
385

386
  EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet());
387
  EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet());
388
  EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet());
389
  EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet());
390
  EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet());
391
  EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet());
392
  EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet());
393
}
394

395
TEST_F(ConstantRangeTest, UpperWrapped) {
396
  // The behavior here is the same as for isWrappedSet() / isSignWrappedSet().
397
  EXPECT_FALSE(Full.isUpperWrapped());
398
  EXPECT_FALSE(Empty.isUpperWrapped());
399
  EXPECT_FALSE(One.isUpperWrapped());
400
  EXPECT_FALSE(Some.isUpperWrapped());
401
  EXPECT_TRUE(Wrap.isUpperWrapped());
402
  EXPECT_FALSE(Full.isUpperSignWrapped());
403
  EXPECT_FALSE(Empty.isUpperSignWrapped());
404
  EXPECT_FALSE(One.isUpperSignWrapped());
405
  EXPECT_FALSE(Some.isUpperSignWrapped());
406
  EXPECT_TRUE(Wrap.isUpperSignWrapped());
407

408
  // The behavior differs if Upper is the Min/SignedMin value.
409
  ConstantRange CR1(APInt(8, 42), APInt::getMinValue(8));
410
  EXPECT_FALSE(CR1.isWrappedSet());
411
  EXPECT_TRUE(CR1.isUpperWrapped());
412

413
  ConstantRange CR2(APInt(8, 42), APInt::getSignedMinValue(8));
414
  EXPECT_FALSE(CR2.isSignWrappedSet());
415
  EXPECT_TRUE(CR2.isUpperSignWrapped());
416
}
417

418
TEST_F(ConstantRangeTest, Trunc) {
419
  ConstantRange TFull = Full.truncate(10);
420
  ConstantRange TEmpty = Empty.truncate(10);
421
  ConstantRange TOne = One.truncate(10);
422
  ConstantRange TSome = Some.truncate(10);
423
  ConstantRange TWrap = Wrap.truncate(10);
424
  EXPECT_TRUE(TFull.isFullSet());
425
  EXPECT_TRUE(TEmpty.isEmptySet());
426
  EXPECT_EQ(TOne, ConstantRange(One.getLower().trunc(10),
427
                                One.getUpper().trunc(10)));
428
  EXPECT_TRUE(TSome.isFullSet());
429
  EXPECT_TRUE(TWrap.isFullSet());
430

431
  // trunc([2, 5), 3->2) = [2, 1)
432
  ConstantRange TwoFive(APInt(3, 2), APInt(3, 5));
433
  EXPECT_EQ(TwoFive.truncate(2), ConstantRange(APInt(2, 2), APInt(2, 1)));
434

435
  // trunc([2, 6), 3->2) = full
436
  ConstantRange TwoSix(APInt(3, 2), APInt(3, 6));
437
  EXPECT_TRUE(TwoSix.truncate(2).isFullSet());
438

439
  // trunc([5, 7), 3->2) = [1, 3)
440
  ConstantRange FiveSeven(APInt(3, 5), APInt(3, 7));
441
  EXPECT_EQ(FiveSeven.truncate(2), ConstantRange(APInt(2, 1), APInt(2, 3)));
442

443
  // trunc([7, 1), 3->2) = [3, 1)
444
  ConstantRange SevenOne(APInt(3, 7), APInt(3, 1));
445
  EXPECT_EQ(SevenOne.truncate(2), ConstantRange(APInt(2, 3), APInt(2, 1)));
446
}
447

448
TEST_F(ConstantRangeTest, ZExt) {
449
  ConstantRange ZFull = Full.zeroExtend(20);
450
  ConstantRange ZEmpty = Empty.zeroExtend(20);
451
  ConstantRange ZOne = One.zeroExtend(20);
452
  ConstantRange ZSome = Some.zeroExtend(20);
453
  ConstantRange ZWrap = Wrap.zeroExtend(20);
454
  EXPECT_EQ(ZFull, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
455
  EXPECT_TRUE(ZEmpty.isEmptySet());
456
  EXPECT_EQ(ZOne, ConstantRange(One.getLower().zext(20),
457
                                One.getUpper().zext(20)));
458
  EXPECT_EQ(ZSome, ConstantRange(Some.getLower().zext(20),
459
                                 Some.getUpper().zext(20)));
460
  EXPECT_EQ(ZWrap, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
461

462
  // zext([5, 0), 3->7) = [5, 8)
463
  ConstantRange FiveZero(APInt(3, 5), APInt(3, 0));
464
  EXPECT_EQ(FiveZero.zeroExtend(7), ConstantRange(APInt(7, 5), APInt(7, 8)));
465
}
466

467
TEST_F(ConstantRangeTest, SExt) {
468
  ConstantRange SFull = Full.signExtend(20);
469
  ConstantRange SEmpty = Empty.signExtend(20);
470
  ConstantRange SOne = One.signExtend(20);
471
  ConstantRange SSome = Some.signExtend(20);
472
  ConstantRange SWrap = Wrap.signExtend(20);
473
  EXPECT_EQ(SFull, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
474
                                 APInt(20, INT16_MAX + 1, true)));
475
  EXPECT_TRUE(SEmpty.isEmptySet());
476
  EXPECT_EQ(SOne, ConstantRange(One.getLower().sext(20),
477
                                One.getUpper().sext(20)));
478
  EXPECT_EQ(SSome, ConstantRange(Some.getLower().sext(20),
479
                                 Some.getUpper().sext(20)));
480
  EXPECT_EQ(SWrap, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
481
                                 APInt(20, INT16_MAX + 1, true)));
482

483
  EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16),
484
            ConstantRange(APInt(16, -128), APInt(16, 128)));
485

486
  EXPECT_EQ(ConstantRange(APInt(16, 0x0200), APInt(16, 0x8000)).signExtend(19),
487
            ConstantRange(APInt(19, 0x0200), APInt(19, 0x8000)));
488
}
489

490
TEST_F(ConstantRangeTest, IntersectWith) {
491
  EXPECT_EQ(Empty.intersectWith(Full), Empty);
492
  EXPECT_EQ(Empty.intersectWith(Empty), Empty);
493
  EXPECT_EQ(Empty.intersectWith(One), Empty);
494
  EXPECT_EQ(Empty.intersectWith(Some), Empty);
495
  EXPECT_EQ(Empty.intersectWith(Wrap), Empty);
496
  EXPECT_EQ(Full.intersectWith(Full), Full);
497
  EXPECT_EQ(Some.intersectWith(Some), Some);
498
  EXPECT_EQ(Some.intersectWith(One), One);
499
  EXPECT_EQ(Full.intersectWith(One), One);
500
  EXPECT_EQ(Full.intersectWith(Some), Some);
501
  EXPECT_EQ(Some.intersectWith(Wrap), Empty);
502
  EXPECT_EQ(One.intersectWith(Wrap), Empty);
503
  EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One));
504

505
  // Klee generated testcase from PR4545.
506
  // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
507
  // 01..4.6789ABCDEF where the dots represent values not in the intersection.
508
  ConstantRange LHS(APInt(16, 4), APInt(16, 2));
509
  ConstantRange RHS(APInt(16, 6), APInt(16, 5));
510
  EXPECT_TRUE(LHS.intersectWith(RHS) == LHS);
511

512
  // previous bug: intersection of [min, 3) and [2, max) should be 2
513
  LHS = ConstantRange(APInt(32, -2147483646), APInt(32, 3));
514
  RHS = ConstantRange(APInt(32, 2), APInt(32, 2147483646));
515
  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2)));
516

517
  // [2, 0) /\ [4, 3) = [2, 0)
518
  LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
519
  RHS = ConstantRange(APInt(32, 4), APInt(32, 3));
520
  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2), APInt(32, 0)));
521

522
  // [2, 0) /\ [4, 2) = [4, 0)
523
  LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
524
  RHS = ConstantRange(APInt(32, 4), APInt(32, 2));
525
  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0)));
526

527
  // [4, 2) /\ [5, 1) = [5, 1)
528
  LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
529
  RHS = ConstantRange(APInt(32, 5), APInt(32, 1));
530
  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 5), APInt(32, 1)));
531

532
  // [2, 0) /\ [7, 4) = [7, 4)
533
  LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
534
  RHS = ConstantRange(APInt(32, 7), APInt(32, 4));
535
  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 4)));
536

537
  // [4, 2) /\ [1, 0) = [1, 0)
538
  LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
539
  RHS = ConstantRange(APInt(32, 1), APInt(32, 0));
540
  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2)));
541

542
  // [15, 0) /\ [7, 6) = [15, 0)
543
  LHS = ConstantRange(APInt(32, 15), APInt(32, 0));
544
  RHS = ConstantRange(APInt(32, 7), APInt(32, 6));
545
  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0)));
546
}
547

548
template <typename Fn1, typename Fn2, typename Fn3>
549
void testBinarySetOperationExhaustive(Fn1 OpFn, Fn2 ExactOpFn, Fn3 InResultFn) {
550
  EnumerateTwoInterestingConstantRanges(
551
      [=](const ConstantRange &CR1, const ConstantRange &CR2) {
552
        unsigned Bits = CR1.getBitWidth();
553
        SmallBitVector Elems(1 << Bits);
554
        APInt Num(Bits, 0);
555
        for (unsigned I = 0, Limit = 1 << Bits; I < Limit; ++I, ++Num)
556
          if (InResultFn(CR1, CR2, Num))
557
            Elems.set(Num.getZExtValue());
558

559
        ConstantRange SmallestCR = OpFn(CR1, CR2, ConstantRange::Smallest);
560
        TestRange(SmallestCR, Elems, PreferSmallest, {CR1, CR2});
561

562
        ConstantRange UnsignedCR = OpFn(CR1, CR2, ConstantRange::Unsigned);
563
        TestRange(UnsignedCR, Elems, PreferSmallestNonFullUnsigned, {CR1, CR2});
564

565
        ConstantRange SignedCR = OpFn(CR1, CR2, ConstantRange::Signed);
566
        TestRange(SignedCR, Elems, PreferSmallestNonFullSigned, {CR1, CR2});
567

568
        std::optional<ConstantRange> ExactCR = ExactOpFn(CR1, CR2);
569
        if (SmallestCR.isSizeLargerThan(Elems.count())) {
570
          EXPECT_TRUE(!ExactCR);
571
        } else {
572
          EXPECT_EQ(SmallestCR, *ExactCR);
573
        }
574
      });
575
}
576

577
TEST_F(ConstantRangeTest, IntersectWithExhaustive) {
578
  testBinarySetOperationExhaustive(
579
      [](const ConstantRange &CR1, const ConstantRange &CR2,
580
         ConstantRange::PreferredRangeType Type) {
581
        return CR1.intersectWith(CR2, Type);
582
      },
583
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
584
        return CR1.exactIntersectWith(CR2);
585
      },
586
      [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
587
        return CR1.contains(N) && CR2.contains(N);
588
      });
589
}
590

591
TEST_F(ConstantRangeTest, UnionWithExhaustive) {
592
  testBinarySetOperationExhaustive(
593
      [](const ConstantRange &CR1, const ConstantRange &CR2,
594
         ConstantRange::PreferredRangeType Type) {
595
        return CR1.unionWith(CR2, Type);
596
      },
597
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
598
        return CR1.exactUnionWith(CR2);
599
      },
600
      [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
601
        return CR1.contains(N) || CR2.contains(N);
602
      });
603
}
604

605
TEST_F(ConstantRangeTest, UnionWith) {
606
  EXPECT_EQ(Wrap.unionWith(One),
607
            ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));
608
  EXPECT_EQ(One.unionWith(Wrap), Wrap.unionWith(One));
609
  EXPECT_EQ(Empty.unionWith(Empty), Empty);
610
  EXPECT_EQ(Full.unionWith(Full), Full);
611
  EXPECT_EQ(Some.unionWith(Wrap), Full);
612

613
  // PR4545
614
  EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(
615
                                    ConstantRange(APInt(16, 0), APInt(16, 8))),
616
            ConstantRange(APInt(16, 14), APInt(16, 8)));
617
  EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(
618
                                    ConstantRange(APInt(16, 4), APInt(16, 0))),
619
            ConstantRange::getFull(16));
620
  EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(
621
                                    ConstantRange(APInt(16, 2), APInt(16, 1))),
622
            ConstantRange::getFull(16));
623
}
624

625
TEST_F(ConstantRangeTest, SetDifference) {
626
  EXPECT_EQ(Full.difference(Empty), Full);
627
  EXPECT_EQ(Full.difference(Full), Empty);
628
  EXPECT_EQ(Empty.difference(Empty), Empty);
629
  EXPECT_EQ(Empty.difference(Full), Empty);
630

631
  ConstantRange A(APInt(16, 3), APInt(16, 7));
632
  ConstantRange B(APInt(16, 5), APInt(16, 9));
633
  ConstantRange C(APInt(16, 3), APInt(16, 5));
634
  ConstantRange D(APInt(16, 7), APInt(16, 9));
635
  ConstantRange E(APInt(16, 5), APInt(16, 4));
636
  ConstantRange F(APInt(16, 7), APInt(16, 3));
637
  EXPECT_EQ(A.difference(B), C);
638
  EXPECT_EQ(B.difference(A), D);
639
  EXPECT_EQ(E.difference(A), F);
640
}
641

642
TEST_F(ConstantRangeTest, getActiveBits) {
643
  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
644
    unsigned Exact = 0;
645
    ForeachNumInConstantRange(CR, [&](const APInt &N) {
646
      Exact = std::max(Exact, N.getActiveBits());
647
    });
648

649
    unsigned ResultCR = CR.getActiveBits();
650
    EXPECT_EQ(Exact, ResultCR);
651
  });
652
}
653
TEST_F(ConstantRangeTest, losslessUnsignedTruncationZeroext) {
654
  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
655
    unsigned Bits = CR.getBitWidth();
656
    unsigned MinBitWidth = CR.getActiveBits();
657
    if (MinBitWidth == 0) {
658
      EXPECT_TRUE(CR.isEmptySet() ||
659
                  (CR.isSingleElement() && CR.getSingleElement()->isZero()));
660
      return;
661
    }
662
    if (MinBitWidth == Bits)
663
      return;
664
    EXPECT_EQ(CR, CR.truncate(MinBitWidth).zeroExtend(Bits));
665
  });
666
}
667

668
TEST_F(ConstantRangeTest, getMinSignedBits) {
669
  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
670
    unsigned Exact = 0;
671
    ForeachNumInConstantRange(CR, [&](const APInt &N) {
672
      Exact = std::max(Exact, N.getSignificantBits());
673
    });
674

675
    unsigned ResultCR = CR.getMinSignedBits();
676
    EXPECT_EQ(Exact, ResultCR);
677
  });
678
}
679
TEST_F(ConstantRangeTest, losslessSignedTruncationSignext) {
680
  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
681
    unsigned Bits = CR.getBitWidth();
682
    unsigned MinBitWidth = CR.getMinSignedBits();
683
    if (MinBitWidth == 0) {
684
      EXPECT_TRUE(CR.isEmptySet());
685
      return;
686
    }
687
    if (MinBitWidth == Bits)
688
      return;
689
    EXPECT_EQ(CR, CR.truncate(MinBitWidth).signExtend(Bits));
690
  });
691
}
692

693
TEST_F(ConstantRangeTest, SubtractAPInt) {
694
  EXPECT_EQ(Full.subtract(APInt(16, 4)), Full);
695
  EXPECT_EQ(Empty.subtract(APInt(16, 4)), Empty);
696
  EXPECT_EQ(Some.subtract(APInt(16, 4)),
697
            ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
698
  EXPECT_EQ(Wrap.subtract(APInt(16, 4)),
699
            ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
700
  EXPECT_EQ(One.subtract(APInt(16, 4)),
701
            ConstantRange(APInt(16, 0x6)));
702
}
703

704
TEST_F(ConstantRangeTest, Add) {
705
  EXPECT_EQ(Full.add(APInt(16, 4)), Full);
706
  EXPECT_EQ(Full.add(Full), Full);
707
  EXPECT_EQ(Full.add(Empty), Empty);
708
  EXPECT_EQ(Full.add(One), Full);
709
  EXPECT_EQ(Full.add(Some), Full);
710
  EXPECT_EQ(Full.add(Wrap), Full);
711
  EXPECT_EQ(Empty.add(Empty), Empty);
712
  EXPECT_EQ(Empty.add(One), Empty);
713
  EXPECT_EQ(Empty.add(Some), Empty);
714
  EXPECT_EQ(Empty.add(Wrap), Empty);
715
  EXPECT_EQ(Empty.add(APInt(16, 4)), Empty);
716
  EXPECT_EQ(Some.add(APInt(16, 4)),
717
            ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
718
  EXPECT_EQ(Wrap.add(APInt(16, 4)),
719
            ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
720
  EXPECT_EQ(One.add(APInt(16, 4)),
721
            ConstantRange(APInt(16, 0xe)));
722

723
  TestBinaryOpExhaustive(
724
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
725
        return CR1.add(CR2);
726
      },
727
      [](const APInt &N1, const APInt &N2) {
728
        return N1 + N2;
729
      });
730
}
731

732
TEST_F(ConstantRangeTest, AddWithNoWrap) {
733
  typedef OverflowingBinaryOperator OBO;
734
  EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoSignedWrap), Empty);
735
  EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoSignedWrap), Empty);
736
  EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoSignedWrap), Full);
737
  EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoSignedWrap), Full);
738
  EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoSignedWrap), Full);
739
  EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
740
                               OBO::NoSignedWrap),
741
            ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN)));
742
  EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
743
                .addWithNoWrap(Full, OBO::NoSignedWrap),
744
            ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN)));
745
  EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, -1), APInt(16, 0)),
746
                               OBO::NoSignedWrap),
747
            ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX)));
748
  EXPECT_EQ(ConstantRange(APInt(8, 100), APInt(8, 120))
749
                .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, 123)),
750
                               OBO::NoSignedWrap),
751
            ConstantRange(8, false));
752
  EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, -100))
753
                .addWithNoWrap(ConstantRange(APInt(8, -110), APInt(8, -100)),
754
                               OBO::NoSignedWrap),
755
            ConstantRange(8, false));
756
  EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
757
                .addWithNoWrap(ConstantRange(APInt(8, -128), APInt(8, 28)),
758
                               OBO::NoSignedWrap),
759
            ConstantRange(8, true));
760
  EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
761
                .addWithNoWrap(ConstantRange(APInt(8, -120), APInt(8, 29)),
762
                               OBO::NoSignedWrap),
763
            ConstantRange(APInt(8, -120), APInt(8, -128)));
764
  EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50))
765
                .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 20)),
766
                               OBO::NoSignedWrap),
767
            ConstantRange(APInt(8, -40), APInt(8, 69)));
768
  EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
769
                .addWithNoWrap(ConstantRange(APInt(8, -50), APInt(8, 50)),
770
                               OBO::NoSignedWrap),
771
            ConstantRange(APInt(8, -40), APInt(8, 69)));
772
  EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10))
773
                .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
774
                               OBO::NoSignedWrap),
775
            ConstantRange(APInt(8, 125), APInt(8, 9)));
776
  EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
777
                .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, -10)),
778
                               OBO::NoSignedWrap),
779
            ConstantRange(APInt(8, 125), APInt(8, 9)));
780

781
  TestBinaryOpExhaustive(
782
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
783
        return CR1.addWithNoWrap(CR2, OBO::NoSignedWrap);
784
      },
785
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
786
        bool IsOverflow;
787
        APInt Res = N1.sadd_ov(N2, IsOverflow);
788
        if (IsOverflow)
789
          return std::nullopt;
790
        return Res;
791
      },
792
      PreferSmallest, CheckNonSignWrappedOnly);
793

794
  EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoUnsignedWrap), Empty);
795
  EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoUnsignedWrap), Empty);
796
  EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
797
  EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoUnsignedWrap), Full);
798
  EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
799
  EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
800
                               OBO::NoUnsignedWrap),
801
            ConstantRange(APInt(16, 1), APInt(16, 0)));
802
  EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
803
                .addWithNoWrap(Full, OBO::NoUnsignedWrap),
804
            ConstantRange(APInt(16, 1), APInt(16, 0)));
805
  EXPECT_EQ(ConstantRange(APInt(8, 200), APInt(8, 220))
806
                .addWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 123)),
807
                               OBO::NoUnsignedWrap),
808
            ConstantRange(8, false));
809
  EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
810
                .addWithNoWrap(ConstantRange(APInt(8, 0), APInt(8, 156)),
811
                               OBO::NoUnsignedWrap),
812
            ConstantRange(8, true));
813
  EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
814
                .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 29)),
815
                               OBO::NoUnsignedWrap),
816
            ConstantRange(APInt(8, 10), APInt(8, 129)));
817
  EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, 10))
818
                .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
819
                               OBO::NoUnsignedWrap),
820
            ConstantRange(APInt(8, 50), APInt(8, 0)));
821
  EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
822
                .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
823
                               OBO::NoUnsignedWrap),
824
            ConstantRange(APInt(8, 60), APInt(8, -37)));
825
  EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, -30))
826
                .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
827
                               OBO::NoUnsignedWrap),
828
            ConstantRange(APInt(8, 25), APInt(8, -11)));
829
  EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
830
                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, -30)),
831
                               OBO::NoUnsignedWrap),
832
            ConstantRange(APInt(8, 25), APInt(8, -11)));
833

834
  TestBinaryOpExhaustive(
835
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
836
        return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap);
837
      },
838
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
839
        bool IsOverflow;
840
        APInt Res = N1.uadd_ov(N2, IsOverflow);
841
        if (IsOverflow)
842
          return std::nullopt;
843
        return Res;
844
      },
845
      PreferSmallest, CheckNonWrappedOnly);
846

847
  EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
848
                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
849
                               OBO::NoSignedWrap),
850
            ConstantRange(APInt(8, 70), APInt(8, -128)));
851
  EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
852
                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
853
                               OBO::NoUnsignedWrap),
854
            ConstantRange(APInt(8, 70), APInt(8, 169)));
855
  EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
856
                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
857
                               OBO::NoUnsignedWrap | OBO::NoSignedWrap),
858
            ConstantRange(APInt(8, 70), APInt(8, -128)));
859

860
  EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
861
                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
862
                               OBO::NoSignedWrap),
863
            ConstantRange(APInt(8, -80), APInt(8, -21)));
864
  EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
865
                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
866
                               OBO::NoUnsignedWrap),
867
            ConstantRange(APInt(8, 176), APInt(8, 235)));
868
  EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
869
                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
870
                               OBO::NoUnsignedWrap | OBO::NoSignedWrap),
871
            ConstantRange(APInt(8, 176), APInt(8, 235)));
872

873
  TestBinaryOpExhaustive(
874
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
875
        return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);
876
      },
877
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
878
        bool IsOverflow1, IsOverflow2;
879
        APInt Res1 = N1.uadd_ov(N2, IsOverflow1);
880
        APInt Res2 = N1.sadd_ov(N2, IsOverflow2);
881
        if (IsOverflow1 || IsOverflow2)
882
          return std::nullopt;
883
        assert(Res1 == Res2 && "Addition results differ?");
884
        return Res1;
885
      },
886
      PreferSmallest, CheckNonWrappedOrSignWrappedOnly);
887
}
888

889
TEST_F(ConstantRangeTest, Sub) {
890
  EXPECT_EQ(Full.sub(APInt(16, 4)), Full);
891
  EXPECT_EQ(Full.sub(Full), Full);
892
  EXPECT_EQ(Full.sub(Empty), Empty);
893
  EXPECT_EQ(Full.sub(One), Full);
894
  EXPECT_EQ(Full.sub(Some), Full);
895
  EXPECT_EQ(Full.sub(Wrap), Full);
896
  EXPECT_EQ(Empty.sub(Empty), Empty);
897
  EXPECT_EQ(Empty.sub(One), Empty);
898
  EXPECT_EQ(Empty.sub(Some), Empty);
899
  EXPECT_EQ(Empty.sub(Wrap), Empty);
900
  EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty);
901
  EXPECT_EQ(Some.sub(APInt(16, 4)),
902
            ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
903
  EXPECT_EQ(Some.sub(Some),
904
            ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0)));
905
  EXPECT_EQ(Wrap.sub(APInt(16, 4)),
906
            ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
907
  EXPECT_EQ(One.sub(APInt(16, 4)),
908
            ConstantRange(APInt(16, 0x6)));
909

910
  TestBinaryOpExhaustive(
911
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
912
        return CR1.sub(CR2);
913
      },
914
      [](const APInt &N1, const APInt &N2) {
915
        return N1 - N2;
916
      });
917
}
918

919
TEST_F(ConstantRangeTest, SubWithNoWrap) {
920
  typedef OverflowingBinaryOperator OBO;
921
  TestBinaryOpExhaustive(
922
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
923
        return CR1.subWithNoWrap(CR2, OBO::NoSignedWrap);
924
      },
925
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
926
        bool IsOverflow;
927
        APInt Res = N1.ssub_ov(N2, IsOverflow);
928
        if (IsOverflow)
929
          return std::nullopt;
930
        return Res;
931
      },
932
      PreferSmallest, CheckNonSignWrappedOnly);
933
  TestBinaryOpExhaustive(
934
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
935
        return CR1.subWithNoWrap(CR2, OBO::NoUnsignedWrap);
936
      },
937
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
938
        bool IsOverflow;
939
        APInt Res = N1.usub_ov(N2, IsOverflow);
940
        if (IsOverflow)
941
          return std::nullopt;
942
        return Res;
943
      },
944
      PreferSmallest, CheckNonWrappedOnly);
945
  TestBinaryOpExhaustive(
946
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
947
        return CR1.subWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);
948
      },
949
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
950
        bool IsOverflow1, IsOverflow2;
951
        APInt Res1 = N1.usub_ov(N2, IsOverflow1);
952
        APInt Res2 = N1.ssub_ov(N2, IsOverflow2);
953
        if (IsOverflow1 || IsOverflow2)
954
          return std::nullopt;
955
        assert(Res1 == Res2 && "Subtraction results differ?");
956
        return Res1;
957
      },
958
      PreferSmallest, CheckNonWrappedOrSignWrappedOnly);
959
}
960

961
TEST_F(ConstantRangeTest, Multiply) {
962
  EXPECT_EQ(Full.multiply(Full), Full);
963
  EXPECT_EQ(Full.multiply(Empty), Empty);
964
  EXPECT_EQ(Full.multiply(One), Full);
965
  EXPECT_EQ(Full.multiply(Some), Full);
966
  EXPECT_EQ(Full.multiply(Wrap), Full);
967
  EXPECT_EQ(Empty.multiply(Empty), Empty);
968
  EXPECT_EQ(Empty.multiply(One), Empty);
969
  EXPECT_EQ(Empty.multiply(Some), Empty);
970
  EXPECT_EQ(Empty.multiply(Wrap), Empty);
971
  EXPECT_EQ(One.multiply(One), ConstantRange(APInt(16, 0xa*0xa),
972
                                             APInt(16, 0xa*0xa + 1)));
973
  EXPECT_EQ(One.multiply(Some), ConstantRange(APInt(16, 0xa*0xa),
974
                                              APInt(16, 0xa*0xaa9 + 1)));
975
  EXPECT_EQ(One.multiply(Wrap), Full);
976
  EXPECT_EQ(Some.multiply(Some), Full);
977
  EXPECT_EQ(Some.multiply(Wrap), Full);
978
  EXPECT_EQ(Wrap.multiply(Wrap), Full);
979

980
  ConstantRange Zero(APInt(16, 0));
981
  EXPECT_EQ(Zero.multiply(Full), Zero);
982
  EXPECT_EQ(Zero.multiply(Some), Zero);
983
  EXPECT_EQ(Zero.multiply(Wrap), Zero);
984
  EXPECT_EQ(Full.multiply(Zero), Zero);
985
  EXPECT_EQ(Some.multiply(Zero), Zero);
986
  EXPECT_EQ(Wrap.multiply(Zero), Zero);
987

988
  // http://llvm.org/PR4545
989
  EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply(
990
                ConstantRange(APInt(4, 6), APInt(4, 2))),
991
            ConstantRange(4, /*isFullSet=*/true));
992

993
  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply(
994
              ConstantRange(APInt(8, 252), APInt(8, 4))),
995
            ConstantRange(APInt(8, 250), APInt(8, 9)));
996
  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply(
997
              ConstantRange(APInt(8, 2), APInt(8, 4))),
998
            ConstantRange(APInt(8, 250), APInt(8, 253)));
999

1000
  // TODO: This should be return [-2, 0]
1001
  EXPECT_EQ(ConstantRange(APInt(8, -2)).multiply(
1002
              ConstantRange(APInt(8, 0), APInt(8, 2))),
1003
            ConstantRange(APInt(8, -2), APInt(8, 1)));
1004

1005
  // Multiplication by -1 should give precise results.
1006
  EXPECT_EQ(ConstantRange(APInt(8, 3), APInt(8, -11))
1007
                .multiply(ConstantRange(APInt(8, -1))),
1008
            ConstantRange(APInt(8, 12), APInt(8, -2)));
1009
  EXPECT_EQ(ConstantRange(APInt(8, -1))
1010
                .multiply(ConstantRange(APInt(8, 3), APInt(8, -11))),
1011
            ConstantRange(APInt(8, 12), APInt(8, -2)));
1012

1013
  TestBinaryOpExhaustive(
1014
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1015
        return CR1.multiply(CR2);
1016
      },
1017
      [](const APInt &N1, const APInt &N2) {
1018
        return N1 * N2;
1019
      },
1020
      PreferSmallest,
1021
      [](const ConstantRange &, const ConstantRange &) {
1022
        return false; // Check correctness only.
1023
      });
1024
}
1025

1026
TEST_F(ConstantRangeTest, MultiplyWithNoWrap) {
1027
  using OBO = OverflowingBinaryOperator;
1028

1029
  EXPECT_EQ(Empty.multiplyWithNoWrap(Some, OBO::NoUnsignedWrap), Empty);
1030
  EXPECT_EQ(Some.multiplyWithNoWrap(Empty, OBO::NoUnsignedWrap), Empty);
1031
  EXPECT_EQ(Full.multiplyWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
1032
  EXPECT_EQ(Full.multiplyWithNoWrap(Some, OBO::NoUnsignedWrap), Full);
1033
  EXPECT_EQ(Some.multiplyWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
1034
  EXPECT_EQ(ConstantRange(APInt(4, 0), APInt(4, 2))
1035
                .multiplyWithNoWrap(ConstantRange(APInt(4, 2), APInt(4, 0)),
1036
                                    OBO::NoUnsignedWrap),
1037
            ConstantRange::getFull(4));
1038
  EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 5))
1039
                .multiplyWithNoWrap(ConstantRange(APInt(4, 1), APInt(4, 5)),
1040
                                    OBO::NoUnsignedWrap),
1041
            ConstantRange(APInt(4, 1), APInt(4, 0)));
1042
  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0))
1043
                .multiplyWithNoWrap(ConstantRange(APInt(8, 252), APInt(8, 4)),
1044
                                    OBO::NoUnsignedWrap),
1045
            ConstantRange(APInt(8, 250), APInt(8, 9)));
1046
  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255))
1047
                .multiplyWithNoWrap(ConstantRange(APInt(8, 2), APInt(8, 4)),
1048
                                    OBO::NoUnsignedWrap),
1049
            ConstantRange::getEmpty(8));
1050

1051
  EXPECT_EQ(Empty.multiplyWithNoWrap(Some, OBO::NoSignedWrap), Empty);
1052
  EXPECT_EQ(Some.multiplyWithNoWrap(Empty, OBO::NoSignedWrap), Empty);
1053
  EXPECT_EQ(Full.multiplyWithNoWrap(Full, OBO::NoSignedWrap), Full);
1054
  EXPECT_EQ(Full.multiplyWithNoWrap(Some, OBO::NoSignedWrap), Full);
1055
  EXPECT_EQ(Some.multiplyWithNoWrap(Full, OBO::NoSignedWrap), Full);
1056
  EXPECT_EQ(
1057
      ConstantRange(APInt(4, 0), APInt(4, 4))
1058
          .multiplyWithNoWrap(ConstantRange(APInt(4, -5, true), APInt(4, 4)),
1059
                              OBO::NoSignedWrap),
1060
      ConstantRange::getFull(4));
1061
  EXPECT_EQ(ConstantRange(APInt(4, 0), APInt(4, 3))
1062
                .multiplyWithNoWrap(ConstantRange(APInt(4, 0), APInt(4, 5)),
1063
                                    OBO::NoSignedWrap),
1064
            ConstantRange(APInt(4, 0), APInt(4, -8, true)));
1065
  EXPECT_EQ(ConstantRange(APInt(8, 3), APInt(8, -11, true))
1066
                .multiplyWithNoWrap(ConstantRange(APInt(8, -1, true)),
1067
                                    OBO::NoSignedWrap),
1068
            ConstantRange(APInt(8, 12), APInt(8, -2, true)));
1069
  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255))
1070
                .multiplyWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 121)),
1071
                                    OBO::NoSignedWrap),
1072
            ConstantRange::getEmpty(8));
1073

1074
  TestBinaryOpExhaustive(
1075
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1076
        return CR1.multiplyWithNoWrap(CR2, OBO::NoUnsignedWrap);
1077
      },
1078
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1079
        bool IsOverflow;
1080
        APInt Res = N1.umul_ov(N2, IsOverflow);
1081
        if (IsOverflow)
1082
          return std::nullopt;
1083
        return Res;
1084
      },
1085
      PreferSmallest, CheckCorrectnessOnly);
1086
  TestBinaryOpExhaustive(
1087
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1088
        return CR1.multiplyWithNoWrap(CR2, OBO::NoSignedWrap);
1089
      },
1090
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1091
        bool IsOverflow;
1092
        APInt Res = N1.smul_ov(N2, IsOverflow);
1093
        if (IsOverflow)
1094
          return std::nullopt;
1095
        return Res;
1096
      },
1097
      PreferSmallest, CheckCorrectnessOnly);
1098
  TestBinaryOpExhaustive(
1099
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1100
        return CR1.multiplyWithNoWrap(CR2,
1101
                                      OBO::NoUnsignedWrap | OBO::NoSignedWrap);
1102
      },
1103
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1104
        bool IsOverflow1, IsOverflow2;
1105
        APInt Res1 = N1.umul_ov(N2, IsOverflow1);
1106
        APInt Res2 = N1.smul_ov(N2, IsOverflow2);
1107
        if (IsOverflow1 || IsOverflow2)
1108
          return std::nullopt;
1109
        assert(Res1 == Res2 && "Multiplication results differ?");
1110
        return Res1;
1111
      },
1112
      PreferSmallest, CheckCorrectnessOnly);
1113
}
1114

1115
TEST_F(ConstantRangeTest, smul_fast) {
1116
  TestBinaryOpExhaustive(
1117
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1118
        return CR1.smul_fast(CR2);
1119
      },
1120
      [](const APInt &N1, const APInt &N2) { return N1 * N2; }, PreferSmallest,
1121
      CheckCorrectnessOnly);
1122
}
1123

1124
TEST_F(ConstantRangeTest, UMax) {
1125
  EXPECT_EQ(Full.umax(Full), Full);
1126
  EXPECT_EQ(Full.umax(Empty), Empty);
1127
  EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1128
  EXPECT_EQ(Full.umax(Wrap), Full);
1129
  EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1130
  EXPECT_EQ(Empty.umax(Empty), Empty);
1131
  EXPECT_EQ(Empty.umax(Some), Empty);
1132
  EXPECT_EQ(Empty.umax(Wrap), Empty);
1133
  EXPECT_EQ(Empty.umax(One), Empty);
1134
  EXPECT_EQ(Some.umax(Some), Some);
1135
  EXPECT_EQ(Some.umax(Wrap), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1136
  EXPECT_EQ(Some.umax(One), Some);
1137
  EXPECT_EQ(Wrap.umax(Wrap), Wrap);
1138
  EXPECT_EQ(Wrap.umax(One), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1139
  EXPECT_EQ(One.umax(One), One);
1140

1141
  TestBinaryOpExhaustive(
1142
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1143
        return CR1.umax(CR2);
1144
      },
1145
      [](const APInt &N1, const APInt &N2) {
1146
        return APIntOps::umax(N1, N2);
1147
      },
1148
      PreferSmallestNonFullUnsigned);
1149
}
1150

1151
TEST_F(ConstantRangeTest, SMax) {
1152
  EXPECT_EQ(Full.smax(Full), Full);
1153
  EXPECT_EQ(Full.smax(Empty), Empty);
1154
  EXPECT_EQ(Full.smax(Some), ConstantRange(APInt(16, 0xa),
1155
                                           APInt::getSignedMinValue(16)));
1156
  EXPECT_EQ(Full.smax(Wrap), Full);
1157
  EXPECT_EQ(Full.smax(One), ConstantRange(APInt(16, 0xa),
1158
                                          APInt::getSignedMinValue(16)));
1159
  EXPECT_EQ(Empty.smax(Empty), Empty);
1160
  EXPECT_EQ(Empty.smax(Some), Empty);
1161
  EXPECT_EQ(Empty.smax(Wrap), Empty);
1162
  EXPECT_EQ(Empty.smax(One), Empty);
1163
  EXPECT_EQ(Some.smax(Some), Some);
1164
  EXPECT_EQ(Some.smax(Wrap), ConstantRange(APInt(16, 0xa),
1165
                                           APInt(16, (uint64_t)INT16_MIN)));
1166
  EXPECT_EQ(Some.smax(One), Some);
1167
  EXPECT_EQ(Wrap.smax(One), ConstantRange(APInt(16, 0xa),
1168
                                          APInt(16, (uint64_t)INT16_MIN)));
1169
  EXPECT_EQ(One.smax(One), One);
1170

1171
  TestBinaryOpExhaustive(
1172
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1173
        return CR1.smax(CR2);
1174
      },
1175
      [](const APInt &N1, const APInt &N2) {
1176
        return APIntOps::smax(N1, N2);
1177
      },
1178
      PreferSmallestNonFullSigned);
1179
}
1180

1181
TEST_F(ConstantRangeTest, UMin) {
1182
  EXPECT_EQ(Full.umin(Full), Full);
1183
  EXPECT_EQ(Full.umin(Empty), Empty);
1184
  EXPECT_EQ(Full.umin(Some), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1185
  EXPECT_EQ(Full.umin(Wrap), Full);
1186
  EXPECT_EQ(Empty.umin(Empty), Empty);
1187
  EXPECT_EQ(Empty.umin(Some), Empty);
1188
  EXPECT_EQ(Empty.umin(Wrap), Empty);
1189
  EXPECT_EQ(Empty.umin(One), Empty);
1190
  EXPECT_EQ(Some.umin(Some), Some);
1191
  EXPECT_EQ(Some.umin(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1192
  EXPECT_EQ(Some.umin(One), One);
1193
  EXPECT_EQ(Wrap.umin(Wrap), Wrap);
1194
  EXPECT_EQ(Wrap.umin(One), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1195
  EXPECT_EQ(One.umin(One), One);
1196

1197
  TestBinaryOpExhaustive(
1198
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1199
        return CR1.umin(CR2);
1200
      },
1201
      [](const APInt &N1, const APInt &N2) {
1202
        return APIntOps::umin(N1, N2);
1203
      },
1204
      PreferSmallestNonFullUnsigned);
1205
}
1206

1207
TEST_F(ConstantRangeTest, SMin) {
1208
  EXPECT_EQ(Full.smin(Full), Full);
1209
  EXPECT_EQ(Full.smin(Empty), Empty);
1210
  EXPECT_EQ(Full.smin(Some), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1211
                                           APInt(16, 0xaaa)));
1212
  EXPECT_EQ(Full.smin(Wrap), Full);
1213
  EXPECT_EQ(Empty.smin(Empty), Empty);
1214
  EXPECT_EQ(Empty.smin(Some), Empty);
1215
  EXPECT_EQ(Empty.smin(Wrap), Empty);
1216
  EXPECT_EQ(Empty.smin(One), Empty);
1217
  EXPECT_EQ(Some.smin(Some), Some);
1218
  EXPECT_EQ(Some.smin(Wrap), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1219
                                           APInt(16, 0xaaa)));
1220
  EXPECT_EQ(Some.smin(One), One);
1221
  EXPECT_EQ(Wrap.smin(Wrap), Wrap);
1222
  EXPECT_EQ(Wrap.smin(One), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1223
                                          APInt(16, 0xb)));
1224
  EXPECT_EQ(One.smin(One), One);
1225

1226
  TestBinaryOpExhaustive(
1227
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1228
        return CR1.smin(CR2);
1229
      },
1230
      [](const APInt &N1, const APInt &N2) {
1231
        return APIntOps::smin(N1, N2);
1232
      },
1233
      PreferSmallestNonFullSigned);
1234
}
1235

1236
TEST_F(ConstantRangeTest, UDiv) {
1237
  EXPECT_EQ(Full.udiv(Full), Full);
1238
  EXPECT_EQ(Full.udiv(Empty), Empty);
1239
  EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0),
1240
                                          APInt(16, 0xffff / 0xa + 1)));
1241
  EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0),
1242
                                           APInt(16, 0xffff / 0xa + 1)));
1243
  EXPECT_EQ(Full.udiv(Wrap), Full);
1244
  EXPECT_EQ(Empty.udiv(Empty), Empty);
1245
  EXPECT_EQ(Empty.udiv(One), Empty);
1246
  EXPECT_EQ(Empty.udiv(Some), Empty);
1247
  EXPECT_EQ(Empty.udiv(Wrap), Empty);
1248
  EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));
1249
  EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
1250
  EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1251
  EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
1252
  EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1253
  EXPECT_EQ(Wrap.udiv(Wrap), Full);
1254

1255

1256
  ConstantRange Zero(APInt(16, 0));
1257
  EXPECT_EQ(Zero.udiv(One), Zero);
1258
  EXPECT_EQ(Zero.udiv(Full), Zero);
1259

1260
  EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full),
1261
            ConstantRange(APInt(16, 0), APInt(16, 99)));
1262
  EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full),
1263
            ConstantRange(APInt(16, 0), APInt(16, 99)));
1264
}
1265

1266
TEST_F(ConstantRangeTest, SDiv) {
1267
  ConstantRange OneBit = ConstantRange::getFull(1);
1268
  EXPECT_EQ(OneBit.sdiv(OneBit), ConstantRange(APInt(1, 0)));
1269

1270
  EnumerateTwoInterestingConstantRanges([&](const ConstantRange &CR1,
1271
                                            const ConstantRange &CR2) {
1272
    // Collect possible results in a bit vector. We store the signed value plus
1273
    // a bias to make it unsigned.
1274
    unsigned Bits = CR1.getBitWidth();
1275
    int Bias = 1 << (Bits - 1);
1276
    BitVector Results(1 << Bits);
1277
    ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
1278
      ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
1279
        // Division by zero is UB.
1280
        if (N2 == 0)
1281
          return;
1282

1283
        // SignedMin / -1 is UB.
1284
        if (N1.isMinSignedValue() && N2.isAllOnes())
1285
          return;
1286

1287
        APInt N = N1.sdiv(N2);
1288
        Results.set(N.getSExtValue() + Bias);
1289
      });
1290
    });
1291

1292
    ConstantRange CR = CR1.sdiv(CR2);
1293
    if (Results.none()) {
1294
      EXPECT_TRUE(CR.isEmptySet());
1295
      return;
1296
    }
1297

1298
    // If there is a non-full signed envelope, that should be the result.
1299
    APInt SMin(Bits, Results.find_first() - Bias);
1300
    APInt SMax(Bits, Results.find_last() - Bias);
1301
    ConstantRange Envelope = ConstantRange::getNonEmpty(SMin, SMax + 1);
1302
    if (!Envelope.isFullSet()) {
1303
      EXPECT_EQ(Envelope, CR);
1304
      return;
1305
    }
1306

1307
    // If the signed envelope is a full set, try to find a smaller sign wrapped
1308
    // set that is separated in negative and positive components (or one which
1309
    // can also additionally contain zero).
1310
    int LastNeg = Results.find_last_in(0, Bias) - Bias;
1311
    int LastPos = Results.find_next(Bias) - Bias;
1312
    if (Results[Bias]) {
1313
      if (LastNeg == -1)
1314
        ++LastNeg;
1315
      else if (LastPos == 1)
1316
        --LastPos;
1317
    }
1318

1319
    APInt WMax(Bits, LastNeg);
1320
    APInt WMin(Bits, LastPos);
1321
    ConstantRange Wrapped = ConstantRange::getNonEmpty(WMin, WMax + 1);
1322
    EXPECT_EQ(Wrapped, CR);
1323
  });
1324
}
1325

1326
TEST_F(ConstantRangeTest, URem) {
1327
  EXPECT_EQ(Full.urem(Empty), Empty);
1328
  EXPECT_EQ(Empty.urem(Full), Empty);
1329
  // urem by zero is poison.
1330
  EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty);
1331
  // urem by full range doesn't contain MaxValue.
1332
  EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff)));
1333
  // urem is upper bounded by maximum RHS minus one.
1334
  EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))),
1335
            ConstantRange(APInt(16, 0), APInt(16, 122)));
1336
  // urem is upper bounded by maximum LHS.
1337
  EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full),
1338
            ConstantRange(APInt(16, 0), APInt(16, 123)));
1339
  // If the LHS is always lower than the RHS, the result is the LHS.
1340
  EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
1341
                .urem(ConstantRange(APInt(16, 20), APInt(16, 30))),
1342
            ConstantRange(APInt(16, 10), APInt(16, 20)));
1343
  // It has to be strictly lower, otherwise the top value may wrap to zero.
1344
  EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
1345
                .urem(ConstantRange(APInt(16, 19), APInt(16, 30))),
1346
            ConstantRange(APInt(16, 0), APInt(16, 20)));
1347
  // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].
1348
  EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1349
                .urem(ConstantRange(APInt(16, 10))),
1350
            ConstantRange(APInt(16, 0), APInt(16, 10)));
1351

1352
  TestBinaryOpExhaustive(
1353
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1354
        return CR1.urem(CR2);
1355
      },
1356
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1357
        if (N2.isZero())
1358
          return std::nullopt;
1359
        return N1.urem(N2);
1360
      },
1361
      PreferSmallest, CheckSingleElementsOnly);
1362
}
1363

1364
TEST_F(ConstantRangeTest, SRem) {
1365
  EXPECT_EQ(Full.srem(Empty), Empty);
1366
  EXPECT_EQ(Empty.srem(Full), Empty);
1367
  // srem by zero is UB.
1368
  EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);
1369
  // srem by full range doesn't contain SignedMinValue.
1370
  EXPECT_EQ(Full.srem(Full), ConstantRange(APInt::getSignedMinValue(16) + 1,
1371
                                           APInt::getSignedMinValue(16)));
1372

1373
  ConstantRange PosMod(APInt(16, 10), APInt(16, 21));  // [10, 20]
1374
  ConstantRange NegMod(APInt(16, -20), APInt(16, -9)); // [-20, -10]
1375
  ConstantRange IntMinMod(APInt::getSignedMinValue(16));
1376

1377
  ConstantRange Expected(16, true);
1378

1379
  // srem is bounded by abs(RHS) minus one.
1380
  ConstantRange PosLargeLHS(APInt(16, 0), APInt(16, 41));
1381
  Expected = ConstantRange(APInt(16, 0), APInt(16, 20));
1382
  EXPECT_EQ(PosLargeLHS.srem(PosMod), Expected);
1383
  EXPECT_EQ(PosLargeLHS.srem(NegMod), Expected);
1384
  ConstantRange NegLargeLHS(APInt(16, -40), APInt(16, 1));
1385
  Expected = ConstantRange(APInt(16, -19), APInt(16, 1));
1386
  EXPECT_EQ(NegLargeLHS.srem(PosMod), Expected);
1387
  EXPECT_EQ(NegLargeLHS.srem(NegMod), Expected);
1388
  ConstantRange PosNegLargeLHS(APInt(16, -32), APInt(16, 38));
1389
  Expected = ConstantRange(APInt(16, -19), APInt(16, 20));
1390
  EXPECT_EQ(PosNegLargeLHS.srem(PosMod), Expected);
1391
  EXPECT_EQ(PosNegLargeLHS.srem(NegMod), Expected);
1392

1393
  // srem is bounded by LHS.
1394
  ConstantRange PosLHS(APInt(16, 0), APInt(16, 16));
1395
  EXPECT_EQ(PosLHS.srem(PosMod), PosLHS);
1396
  EXPECT_EQ(PosLHS.srem(NegMod), PosLHS);
1397
  EXPECT_EQ(PosLHS.srem(IntMinMod), PosLHS);
1398
  ConstantRange NegLHS(APInt(16, -15), APInt(16, 1));
1399
  EXPECT_EQ(NegLHS.srem(PosMod), NegLHS);
1400
  EXPECT_EQ(NegLHS.srem(NegMod), NegLHS);
1401
  EXPECT_EQ(NegLHS.srem(IntMinMod), NegLHS);
1402
  ConstantRange PosNegLHS(APInt(16, -12), APInt(16, 18));
1403
  EXPECT_EQ(PosNegLHS.srem(PosMod), PosNegLHS);
1404
  EXPECT_EQ(PosNegLHS.srem(NegMod), PosNegLHS);
1405
  EXPECT_EQ(PosNegLHS.srem(IntMinMod), PosNegLHS);
1406

1407
  // srem is LHS if it is smaller than RHS.
1408
  ConstantRange PosSmallLHS(APInt(16, 3), APInt(16, 8));
1409
  EXPECT_EQ(PosSmallLHS.srem(PosMod), PosSmallLHS);
1410
  EXPECT_EQ(PosSmallLHS.srem(NegMod), PosSmallLHS);
1411
  EXPECT_EQ(PosSmallLHS.srem(IntMinMod), PosSmallLHS);
1412
  ConstantRange NegSmallLHS(APInt(16, -7), APInt(16, -2));
1413
  EXPECT_EQ(NegSmallLHS.srem(PosMod), NegSmallLHS);
1414
  EXPECT_EQ(NegSmallLHS.srem(NegMod), NegSmallLHS);
1415
  EXPECT_EQ(NegSmallLHS.srem(IntMinMod), NegSmallLHS);
1416
  ConstantRange PosNegSmallLHS(APInt(16, -3), APInt(16, 8));
1417
  EXPECT_EQ(PosNegSmallLHS.srem(PosMod), PosNegSmallLHS);
1418
  EXPECT_EQ(PosNegSmallLHS.srem(NegMod), PosNegSmallLHS);
1419
  EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);
1420

1421
  // Example of a suboptimal result:
1422
  // [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
1423
  EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1424
                .srem(ConstantRange(APInt(16, 10))),
1425
            ConstantRange(APInt(16, 0), APInt(16, 10)));
1426

1427
  TestBinaryOpExhaustive(
1428
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1429
        return CR1.srem(CR2);
1430
      },
1431
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1432
        if (N2.isZero())
1433
          return std::nullopt;
1434
        return N1.srem(N2);
1435
      },
1436
      PreferSmallest, CheckSingleElementsOnly);
1437
}
1438

1439
TEST_F(ConstantRangeTest, Shl) {
1440
  ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
1441
  ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
1442
  EXPECT_EQ(Full.shl(Full), Full);
1443
  EXPECT_EQ(Full.shl(Empty), Empty);
1444
  EXPECT_EQ(Full.shl(One), ConstantRange(APInt(16, 0),
1445
                                         APInt(16, 0xfc00) + 1));
1446
  EXPECT_EQ(Full.shl(Some), Full);   // TODO: [0, (-1 << 0xa) + 1)
1447
  EXPECT_EQ(Full.shl(Wrap), Full);
1448
  EXPECT_EQ(Empty.shl(Empty), Empty);
1449
  EXPECT_EQ(Empty.shl(One), Empty);
1450
  EXPECT_EQ(Empty.shl(Some), Empty);
1451
  EXPECT_EQ(Empty.shl(Wrap), Empty);
1452
  EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),
1453
                                        APInt(16, (0xa << 0xa) + 1)));
1454
  EXPECT_EQ(One.shl(Some), Full);    // TODO: [0xa << 0xa, 0)
1455
  EXPECT_EQ(One.shl(Wrap), Full);    // TODO: [0xa, 0xa << 14 + 1)
1456
  EXPECT_EQ(Some.shl(Some), Full);   // TODO: [0xa << 0xa, 0xfc01)
1457
  EXPECT_EQ(Some.shl(Wrap), Full);   // TODO: [0xa, 0x7ff << 0x5 + 1)
1458
  EXPECT_EQ(Wrap.shl(Wrap), Full);
1459
  EXPECT_EQ(
1460
      Some2.shl(ConstantRange(APInt(16, 0x1))),
1461
      ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1));
1462
  EXPECT_EQ(One.shl(WrapNullMax), Full);
1463

1464
  ConstantRange NegOne(APInt(16, 0xffff));
1465
  EXPECT_EQ(NegOne.shl(ConstantRange(APInt(16, 0), APInt(16, 5))),
1466
            ConstantRange(APInt(16, 0xfff0), APInt(16, 0)));
1467
  EXPECT_EQ(ConstantRange(APInt(16, 0xfffe), APInt(16, 0))
1468
                .shl(ConstantRange(APInt(16, 0), APInt(16, 5))),
1469
            ConstantRange(APInt(16, 0xffe0), APInt(16, 0)));
1470

1471
  TestBinaryOpExhaustive(
1472
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
1473
        return CR1.shl(CR2);
1474
      },
1475
      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1476
        if (N2.uge(N2.getBitWidth()))
1477
          return std::nullopt;
1478
        return N1.shl(N2);
1479
      },
1480
      PreferSmallestUnsigned,
1481
      [](const ConstantRange &, const ConstantRange &CR2) {
1482
        // We currently only produce precise results for single element RHS.
1483
        return CR2.isSingleElement();
1484
      });
1485
}
1486

1487
TEST_F(ConstantRangeTest, Lshr) {
1488
  EXPECT_EQ(Full.lshr(Full), Full);
1489
  EXPECT_EQ(Full.lshr(Empty), Empty);
1490
  EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),
1491
                                          APInt(16, (0xffff >> 0xa) + 1)));
1492
  EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),
1493
                                           APInt(16, (0xffff >> 0xa) + 1)));
1494
  EXPECT_EQ(Full.lshr(Wrap), Full);
1495
  EXPECT_EQ(Empty.lshr(Empty), Empty);
1496
  EXPECT_EQ(Empty.lshr(One), Empty);
1497
  EXPECT_EQ(Empty.lshr(Some), Empty);
1498
  EXPECT_EQ(Empty.lshr(Wrap), Empty);
1499
  EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0)));
1500
  EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));
1501
  EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1502
  EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),
1503
                                           APInt(16, (0xaaa >> 0xa) + 1)));
1504
  EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1505
  EXPECT_EQ(Wrap.lshr(Wrap), Full);
1506
}
1507

1508
TEST_F(ConstantRangeTest, Ashr) {
1509
  EXPECT_EQ(Full.ashr(Full), Full);
1510
  EXPECT_EQ(Full.ashr(Empty), Empty);
1511
  EXPECT_EQ(Full.ashr(One), ConstantRange(APInt(16, 0xffe0),
1512
                                          APInt(16, (0x7fff >> 0xa) + 1 )));
1513
  ConstantRange Small(APInt(16, 0xa), APInt(16, 0xb));
1514
  EXPECT_EQ(Full.ashr(Small), ConstantRange(APInt(16, 0xffe0),
1515
                                           APInt(16, (0x7fff >> 0xa) + 1 )));
1516
  EXPECT_EQ(Full.ashr(Some), ConstantRange(APInt(16, 0xffe0),
1517
                                           APInt(16, (0x7fff >> 0xa) + 1 )));
1518
  EXPECT_EQ(Full.ashr(Wrap), Full);
1519
  EXPECT_EQ(Empty.ashr(Empty), Empty);
1520
  EXPECT_EQ(Empty.ashr(One), Empty);
1521
  EXPECT_EQ(Empty.ashr(Some), Empty);
1522
  EXPECT_EQ(Empty.ashr(Wrap), Empty);
1523
  EXPECT_EQ(One.ashr(One), ConstantRange(APInt(16, 0)));
1524
  EXPECT_EQ(One.ashr(Some), ConstantRange(APInt(16, 0)));
1525
  EXPECT_EQ(One.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1526
  EXPECT_EQ(Some.ashr(Some), ConstantRange(APInt(16, 0),
1527
                                           APInt(16, (0xaaa >> 0xa) + 1)));
1528
  EXPECT_EQ(Some.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1529
  EXPECT_EQ(Wrap.ashr(Wrap), Full);
1530
  ConstantRange Neg(APInt(16, 0xf3f0, true), APInt(16, 0xf7f8, true));
1531
  EXPECT_EQ(Neg.ashr(Small), ConstantRange(APInt(16, 0xfffc, true),
1532
                                           APInt(16, 0xfffe, true)));
1533
}
1534

1535
TEST(ConstantRange, MakeAllowedICmpRegion) {
1536
  // PR8250
1537
  ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32));
1538
  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax)
1539
                  .isEmptySet());
1540
}
1541

1542
TEST(ConstantRange, MakeSatisfyingICmpRegion) {
1543
  ConstantRange LowHalf(APInt(8, 0), APInt(8, 128));
1544
  ConstantRange HighHalf(APInt(8, 128), APInt(8, 0));
1545
  ConstantRange EmptySet(8, /* isFullSet = */ false);
1546

1547
  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf),
1548
            HighHalf);
1549

1550
  EXPECT_EQ(
1551
      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf),
1552
      LowHalf);
1553

1554
  EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ,
1555
                                                      HighHalf).isEmptySet());
1556

1557
  ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200));
1558

1559
  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT,
1560
                                                    UnsignedSample),
1561
            ConstantRange(APInt(8, 0), APInt(8, 5)));
1562

1563
  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE,
1564
                                                    UnsignedSample),
1565
            ConstantRange(APInt(8, 0), APInt(8, 6)));
1566

1567
  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT,
1568
                                                    UnsignedSample),
1569
            ConstantRange(APInt(8, 200), APInt(8, 0)));
1570

1571
  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE,
1572
                                                    UnsignedSample),
1573
            ConstantRange(APInt(8, 199), APInt(8, 0)));
1574

1575
  ConstantRange SignedSample(APInt(8, -5), APInt(8, 5));
1576

1577
  EXPECT_EQ(
1578
      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample),
1579
      ConstantRange(APInt(8, -128), APInt(8, -5)));
1580

1581
  EXPECT_EQ(
1582
      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample),
1583
      ConstantRange(APInt(8, -128), APInt(8, -4)));
1584

1585
  EXPECT_EQ(
1586
      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample),
1587
      ConstantRange(APInt(8, 5), APInt(8, -128)));
1588

1589
  EXPECT_EQ(
1590
      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample),
1591
      ConstantRange(APInt(8, 4), APInt(8, -128)));
1592
}
1593

1594
void ICmpTestImpl(CmpInst::Predicate Pred) {
1595
  EnumerateTwoInterestingConstantRanges(
1596
      [&](const ConstantRange &CR1, const ConstantRange &CR2) {
1597
        bool Exhaustive = true;
1598
        ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
1599
          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
1600
            Exhaustive &= ICmpInst::compare(N1, N2, Pred);
1601
          });
1602
        });
1603
        EXPECT_EQ(CR1.icmp(Pred, CR2), Exhaustive);
1604
      });
1605
}
1606

1607
TEST(ConstantRange, ICmp) {
1608
  for (auto Pred : ICmpInst::predicates())
1609
    ICmpTestImpl(Pred);
1610
}
1611

1612
TEST(ConstantRange, MakeGuaranteedNoWrapRegion) {
1613
  const int IntMin4Bits = 8;
1614
  const int IntMax4Bits = 7;
1615
  typedef OverflowingBinaryOperator OBO;
1616

1617
  for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
1618
    APInt C(4, Const, true /* = isSigned */);
1619

1620
    auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1621
        Instruction::Add, C, OBO::NoUnsignedWrap);
1622

1623
    EXPECT_FALSE(NUWRegion.isEmptySet());
1624

1625
    auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1626
        Instruction::Add, C, OBO::NoSignedWrap);
1627

1628
    EXPECT_FALSE(NSWRegion.isEmptySet());
1629

1630
    for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
1631
         ++I) {
1632
      bool Overflow = false;
1633
      (void)I.uadd_ov(C, Overflow);
1634
      EXPECT_FALSE(Overflow);
1635
    }
1636

1637
    for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
1638
         ++I) {
1639
      bool Overflow = false;
1640
      (void)I.sadd_ov(C, Overflow);
1641
      EXPECT_FALSE(Overflow);
1642
    }
1643
  }
1644

1645
  for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
1646
    APInt C(4, Const, true /* = isSigned */);
1647

1648
    auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1649
        Instruction::Sub, C, OBO::NoUnsignedWrap);
1650

1651
    EXPECT_FALSE(NUWRegion.isEmptySet());
1652

1653
    auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1654
        Instruction::Sub, C, OBO::NoSignedWrap);
1655

1656
    EXPECT_FALSE(NSWRegion.isEmptySet());
1657

1658
    for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
1659
         ++I) {
1660
      bool Overflow = false;
1661
      (void)I.usub_ov(C, Overflow);
1662
      EXPECT_FALSE(Overflow);
1663
    }
1664

1665
    for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
1666
         ++I) {
1667
      bool Overflow = false;
1668
      (void)I.ssub_ov(C, Overflow);
1669
      EXPECT_FALSE(Overflow);
1670
    }
1671
  }
1672

1673
  auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1674
      Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
1675
      OBO::NoSignedWrap);
1676
  EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
1677
              NSWForAllValues.getSingleElement()->isMinValue());
1678

1679
  NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1680
      Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
1681
      OBO::NoSignedWrap);
1682
  EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
1683
              NSWForAllValues.getSingleElement()->isMaxValue());
1684

1685
  auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1686
      Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
1687
      OBO::NoUnsignedWrap);
1688
  EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
1689
              NUWForAllValues.getSingleElement()->isMinValue());
1690

1691
  NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1692
      Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
1693
      OBO::NoUnsignedWrap);
1694
  EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
1695
              NUWForAllValues.getSingleElement()->isMaxValue());
1696

1697
  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1698
      Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
1699
  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1700
      Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
1701
  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1702
      Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
1703
  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1704
      Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
1705

1706
  ConstantRange OneToFive(APInt(32, 1), APInt(32, 6));
1707
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1708
                Instruction::Add, OneToFive, OBO::NoSignedWrap),
1709
            ConstantRange(APInt::getSignedMinValue(32),
1710
                          APInt::getSignedMaxValue(32) - 4));
1711
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1712
                Instruction::Add, OneToFive, OBO::NoUnsignedWrap),
1713
            ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));
1714
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1715
                Instruction::Sub, OneToFive, OBO::NoSignedWrap),
1716
            ConstantRange(APInt::getSignedMinValue(32) + 5,
1717
                          APInt::getSignedMinValue(32)));
1718
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1719
                Instruction::Sub, OneToFive, OBO::NoUnsignedWrap),
1720
            ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));
1721

1722
  ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1));
1723
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1724
                Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap),
1725
            ConstantRange(APInt::getSignedMinValue(32) + 5,
1726
                          APInt::getSignedMinValue(32)));
1727
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1728
                Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
1729
            ConstantRange(APInt(32, 0), APInt(32, 2)));
1730
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1731
                Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap),
1732
            ConstantRange(APInt::getSignedMinValue(32),
1733
                          APInt::getSignedMaxValue(32) - 4));
1734
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1735
                Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
1736
            ConstantRange(APInt::getMaxValue(32) - 1,
1737
                          APInt::getMinValue(32)));
1738

1739
  ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2));
1740
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1741
                Instruction::Add, MinusOneToOne, OBO::NoSignedWrap),
1742
            ConstantRange(APInt::getSignedMinValue(32) + 1,
1743
                          APInt::getSignedMinValue(32) - 1));
1744
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1745
                Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap),
1746
            ConstantRange(APInt(32, 0), APInt(32, 1)));
1747
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1748
                Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap),
1749
            ConstantRange(APInt::getSignedMinValue(32) + 1,
1750
                          APInt::getSignedMinValue(32) - 1));
1751
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1752
                Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap),
1753
            ConstantRange(APInt::getMaxValue(32),
1754
                          APInt::getMinValue(32)));
1755

1756
  ConstantRange One(APInt(32, 1), APInt(32, 2));
1757
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1758
                Instruction::Add, One, OBO::NoSignedWrap),
1759
            ConstantRange(APInt::getSignedMinValue(32),
1760
                          APInt::getSignedMaxValue(32)));
1761
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1762
                Instruction::Add, One, OBO::NoUnsignedWrap),
1763
            ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
1764
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1765
                Instruction::Sub, One, OBO::NoSignedWrap),
1766
            ConstantRange(APInt::getSignedMinValue(32) + 1,
1767
                          APInt::getSignedMinValue(32)));
1768
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1769
                Instruction::Sub, One, OBO::NoUnsignedWrap),
1770
            ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
1771

1772
  ConstantRange OneLessThanBitWidth(APInt(32, 0), APInt(32, 31) + 1);
1773
  ConstantRange UpToBitWidth(APInt(32, 0), APInt(32, 32) + 1);
1774
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1775
                Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
1776
            ConstantRange::makeGuaranteedNoWrapRegion(
1777
                Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
1778
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1779
                Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
1780
            ConstantRange::makeGuaranteedNoWrapRegion(
1781
                Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
1782
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1783
                Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
1784
            ConstantRange(APInt(32, 0), APInt(32, 1) + 1));
1785
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1786
                Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
1787
            ConstantRange(APInt(32, -1), APInt(32, 0) + 1));
1788

1789
  EXPECT_EQ(
1790
      ConstantRange::makeGuaranteedNoWrapRegion(
1791
          Instruction::Shl, ConstantRange::getFull(32), OBO::NoUnsignedWrap),
1792
      ConstantRange::makeGuaranteedNoWrapRegion(
1793
          Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
1794
  EXPECT_EQ(
1795
      ConstantRange::makeGuaranteedNoWrapRegion(
1796
          Instruction::Shl, ConstantRange::getFull(32), OBO::NoSignedWrap),
1797
      ConstantRange::makeGuaranteedNoWrapRegion(
1798
          Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
1799

1800
  ConstantRange IllegalShAmt(APInt(32, 32), APInt(32, 0) + 1);
1801
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1802
                Instruction::Shl, IllegalShAmt, OBO::NoUnsignedWrap),
1803
            ConstantRange::getFull(32));
1804
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1805
                Instruction::Shl, IllegalShAmt, OBO::NoSignedWrap),
1806
            ConstantRange::getFull(32));
1807

1808
  EXPECT_EQ(
1809
      ConstantRange::makeGuaranteedNoWrapRegion(
1810
          Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1811
          OBO::NoUnsignedWrap),
1812
      ConstantRange::makeGuaranteedNoWrapRegion(
1813
          Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
1814
          OBO::NoUnsignedWrap));
1815
  EXPECT_EQ(
1816
      ConstantRange::makeGuaranteedNoWrapRegion(
1817
          Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1818
          OBO::NoSignedWrap),
1819
      ConstantRange::makeGuaranteedNoWrapRegion(
1820
          Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
1821
          OBO::NoSignedWrap));
1822

1823
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1824
                Instruction::Shl,
1825
                ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1826
                OBO::NoUnsignedWrap),
1827
            ConstantRange(APInt(32, 0), APInt(32, 65535) + 1));
1828
  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1829
                Instruction::Shl,
1830
                ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1831
                OBO::NoSignedWrap),
1832
            ConstantRange(APInt(32, -32768), APInt(32, 32767) + 1));
1833
}
1834

1835
template<typename Fn>
1836
void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,
1837
                                unsigned NoWrapKind, Fn OverflowFn) {
1838
  for (unsigned Bits : {1, 5}) {
1839
    EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
1840
      if (CR.isEmptySet())
1841
        return;
1842
      if (Instruction::isShift(BinOp) && CR.getUnsignedMax().uge(Bits))
1843
        return;
1844

1845
      ConstantRange NoWrap =
1846
          ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR, NoWrapKind);
1847
      EnumerateAPInts(Bits, [&](const APInt &N1) {
1848
        bool NoOverflow = true;
1849
        bool Overflow = true;
1850
        ForeachNumInConstantRange(CR, [&](const APInt &N2) {
1851
          if (OverflowFn(N1, N2))
1852
            NoOverflow = false;
1853
          else
1854
            Overflow = false;
1855
        });
1856
        EXPECT_EQ(NoOverflow, NoWrap.contains(N1));
1857

1858
        // The no-wrap range is exact for single-element ranges.
1859
        if (CR.isSingleElement()) {
1860
          EXPECT_EQ(Overflow, !NoWrap.contains(N1));
1861
        }
1862
      });
1863
    });
1864
  }
1865
}
1866

1867
// Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element
1868
// ranges also exact.
1869
TEST(ConstantRange, NoWrapRegionExhaustive) {
1870
  TestNoWrapRegionExhaustive(
1871
      Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap,
1872
      [](const APInt &N1, const APInt &N2) {
1873
        bool Overflow;
1874
        (void) N1.uadd_ov(N2, Overflow);
1875
        return Overflow;
1876
      });
1877
  TestNoWrapRegionExhaustive(
1878
      Instruction::Add, OverflowingBinaryOperator::NoSignedWrap,
1879
      [](const APInt &N1, const APInt &N2) {
1880
        bool Overflow;
1881
        (void) N1.sadd_ov(N2, Overflow);
1882
        return Overflow;
1883
      });
1884
  TestNoWrapRegionExhaustive(
1885
      Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap,
1886
      [](const APInt &N1, const APInt &N2) {
1887
        bool Overflow;
1888
        (void) N1.usub_ov(N2, Overflow);
1889
        return Overflow;
1890
      });
1891
  TestNoWrapRegionExhaustive(
1892
      Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap,
1893
      [](const APInt &N1, const APInt &N2) {
1894
        bool Overflow;
1895
        (void) N1.ssub_ov(N2, Overflow);
1896
        return Overflow;
1897
      });
1898
  TestNoWrapRegionExhaustive(
1899
      Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap,
1900
      [](const APInt &N1, const APInt &N2) {
1901
        bool Overflow;
1902
        (void) N1.umul_ov(N2, Overflow);
1903
        return Overflow;
1904
      });
1905
  TestNoWrapRegionExhaustive(
1906
      Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap,
1907
      [](const APInt &N1, const APInt &N2) {
1908
        bool Overflow;
1909
        (void) N1.smul_ov(N2, Overflow);
1910
        return Overflow;
1911
      });
1912
  TestNoWrapRegionExhaustive(Instruction::Shl,
1913
                             OverflowingBinaryOperator::NoUnsignedWrap,
1914
                             [](const APInt &N1, const APInt &N2) {
1915
                               bool Overflow;
1916
                               (void)N1.ushl_ov(N2, Overflow);
1917
                               return Overflow;
1918
                             });
1919
  TestNoWrapRegionExhaustive(Instruction::Shl,
1920
                             OverflowingBinaryOperator::NoSignedWrap,
1921
                             [](const APInt &N1, const APInt &N2) {
1922
                               bool Overflow;
1923
                               (void)N1.sshl_ov(N2, Overflow);
1924
                               return Overflow;
1925
                             });
1926
}
1927

1928
TEST(ConstantRange, GetEquivalentICmp) {
1929
  APInt RHS;
1930
  CmpInst::Predicate Pred;
1931

1932
  EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
1933
                  .getEquivalentICmp(Pred, RHS));
1934
  EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
1935
  EXPECT_EQ(RHS, APInt(32, 100));
1936

1937
  EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100))
1938
                  .getEquivalentICmp(Pred, RHS));
1939
  EXPECT_EQ(Pred, CmpInst::ICMP_SLT);
1940
  EXPECT_EQ(RHS, APInt(32, 100));
1941

1942
  EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32))
1943
                  .getEquivalentICmp(Pred, RHS));
1944
  EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
1945
  EXPECT_EQ(RHS, APInt(32, 100));
1946

1947
  EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32))
1948
                  .getEquivalentICmp(Pred, RHS));
1949
  EXPECT_EQ(Pred, CmpInst::ICMP_SGE);
1950
  EXPECT_EQ(RHS, APInt(32, 100));
1951

1952
  EXPECT_TRUE(
1953
      ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred, RHS));
1954
  EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
1955
  EXPECT_EQ(RHS, APInt(32, 0));
1956

1957
  EXPECT_TRUE(
1958
      ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred, RHS));
1959
  EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
1960
  EXPECT_EQ(RHS, APInt(32, 0));
1961

1962
  EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200))
1963
                   .getEquivalentICmp(Pred, RHS));
1964

1965
  EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100),
1966
                             APInt::getSignedMinValue(32) + APInt(32, 100))
1967
                   .getEquivalentICmp(Pred, RHS));
1968

1969
  EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100),
1970
                             APInt::getMinValue(32) + APInt(32, 100))
1971
                   .getEquivalentICmp(Pred, RHS));
1972

1973
  EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred, RHS));
1974
  EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1975
  EXPECT_EQ(RHS, APInt(32, 100));
1976

1977
  EXPECT_TRUE(
1978
      ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred, RHS));
1979
  EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1980
  EXPECT_EQ(RHS, APInt(32, 100));
1981

1982
  EXPECT_TRUE(
1983
      ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred, RHS));
1984
  EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1985
  EXPECT_EQ(RHS, APInt(512, 100));
1986

1987
  // NB!  It would be correct for the following four calls to getEquivalentICmp
1988
  // to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT.
1989
  // However, that's not the case today.
1990

1991
  EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred, RHS));
1992
  EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1993
  EXPECT_EQ(RHS, APInt(32, 0));
1994

1995
  EXPECT_TRUE(
1996
      ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred, RHS));
1997
  EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1998
  EXPECT_EQ(RHS, APInt(32, 0));
1999

2000
  EXPECT_TRUE(ConstantRange(APInt(32, -1)).getEquivalentICmp(Pred, RHS));
2001
  EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
2002
  EXPECT_EQ(RHS, APInt(32, -1));
2003

2004
  EXPECT_TRUE(
2005
      ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS));
2006
  EXPECT_EQ(Pred, CmpInst::ICMP_NE);
2007
  EXPECT_EQ(RHS, APInt(32, -1));
2008

2009
  EnumerateInterestingConstantRanges([](const ConstantRange &CR) {
2010
    unsigned Bits = CR.getBitWidth();
2011
    CmpInst::Predicate Pred;
2012
    APInt RHS, Offset;
2013
    CR.getEquivalentICmp(Pred, RHS, Offset);
2014
    EnumerateAPInts(Bits, [&](const APInt &N) {
2015
      bool Result = ICmpInst::compare(N + Offset, RHS, Pred);
2016
      EXPECT_EQ(CR.contains(N), Result);
2017
    });
2018

2019
    if (CR.getEquivalentICmp(Pred, RHS)) {
2020
      EnumerateAPInts(Bits, [&](const APInt &N) {
2021
        bool Result = ICmpInst::compare(N, RHS, Pred);
2022
        EXPECT_EQ(CR.contains(N), Result);
2023
      });
2024
    }
2025
  });
2026
}
2027

2028
#define EXPECT_MAY_OVERFLOW(op) \
2029
  EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))
2030
#define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \
2031
  EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))
2032
#define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \
2033
  EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (op))
2034
#define EXPECT_NEVER_OVERFLOWS(op) \
2035
  EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))
2036

2037
TEST_F(ConstantRangeTest, UnsignedAddOverflow) {
2038
  // Ill-defined - may overflow is a conservative result.
2039
  EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty));
2040
  EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some));
2041

2042
  // Never overflow despite one full/wrap set.
2043
  ConstantRange Zero(APInt::getZero(16));
2044
  EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero));
2045
  EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero));
2046
  EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full));
2047
  EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap));
2048

2049
  // But usually full/wrap always may overflow.
2050
  EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One));
2051
  EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One));
2052
  EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full));
2053
  EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap));
2054

2055
  ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00));
2056
  ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
2057
  ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
2058
  EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1));
2059
  EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2));
2060
  EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A));
2061
  EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A));
2062

2063
  ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400));
2064
  ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400));
2065
  EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1));
2066
  EXPECT_ALWAYS_OVERFLOWS_HIGH(A.unsignedAddMayOverflow(C2));
2067
  EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A));
2068
  EXPECT_ALWAYS_OVERFLOWS_HIGH(C2.unsignedAddMayOverflow(A));
2069
}
2070

2071
TEST_F(ConstantRangeTest, UnsignedSubOverflow) {
2072
  // Ill-defined - may overflow is a conservative result.
2073
  EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty));
2074
  EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some));
2075

2076
  // Never overflow despite one full/wrap set.
2077
  ConstantRange Zero(APInt::getZero(16));
2078
  ConstantRange Max(APInt::getAllOnes(16));
2079
  EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero));
2080
  EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero));
2081
  EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full));
2082
  EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap));
2083

2084
  // But usually full/wrap always may overflow.
2085
  EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One));
2086
  EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One));
2087
  EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full));
2088
  EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap));
2089

2090
  ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100));
2091
  ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200));
2092
  EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A));
2093
  EXPECT_ALWAYS_OVERFLOWS_LOW(A.unsignedSubMayOverflow(B));
2094

2095
  ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101));
2096
  ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
2097
  EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1));
2098
  EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1));
2099

2100
  ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102));
2101
  ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
2102
  EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2));
2103
  EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2));
2104
}
2105

2106
TEST_F(ConstantRangeTest, SignedAddOverflow) {
2107
  // Ill-defined - may overflow is a conservative result.
2108
  EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty));
2109
  EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some));
2110

2111
  // Never overflow despite one full/wrap set.
2112
  ConstantRange Zero(APInt::getZero(16));
2113
  EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero));
2114
  EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero));
2115
  EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full));
2116
  EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap));
2117

2118
  // But usually full/wrap always may overflow.
2119
  EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One));
2120
  EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One));
2121
  EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full));
2122
  EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap));
2123

2124
  ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
2125
  ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
2126
  ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
2127
  EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1));
2128
  EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2));
2129
  ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201));
2130
  ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202));
2131
  EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3));
2132
  EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4));
2133
  ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400));
2134
  ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400));
2135
  EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5));
2136
  EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedAddMayOverflow(B6));
2137

2138
  ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
2139
  ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00));
2140
  ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00));
2141
  EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1));
2142
  EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2));
2143
  ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000));
2144
  ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000));
2145
  EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3));
2146
  EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4));
2147
  ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02));
2148
  ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01));
2149
  EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5));
2150
  EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedAddMayOverflow(D6));
2151

2152
  ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
2153
  EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E));
2154
  ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000));
2155
  EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F));
2156
}
2157

2158
TEST_F(ConstantRangeTest, SignedSubOverflow) {
2159
  // Ill-defined - may overflow is a conservative result.
2160
  EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty));
2161
  EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some));
2162

2163
  // Never overflow despite one full/wrap set.
2164
  ConstantRange Zero(APInt::getZero(16));
2165
  EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero));
2166
  EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero));
2167

2168
  // But usually full/wrap always may overflow.
2169
  EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One));
2170
  EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One));
2171
  EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full));
2172
  EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap));
2173

2174
  ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
2175
  ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00));
2176
  ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00));
2177
  EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1));
2178
  EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2));
2179
  ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02));
2180
  ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01));
2181
  EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3));
2182
  EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedSubMayOverflow(B4));
2183

2184
  ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
2185
  ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201));
2186
  ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202));
2187
  EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1));
2188
  EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2));
2189
  ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400));
2190
  ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400));
2191
  EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3));
2192
  EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedSubMayOverflow(D4));
2193

2194
  ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
2195
  EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E));
2196
  ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001));
2197
  EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F));
2198
}
2199

2200
template <typename Fn1, typename Fn2>
2201
static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) {
2202
  // Constant range overflow checks are tested exhaustively on 4-bit numbers.
2203
  EnumerateTwoInterestingConstantRanges([=](const ConstantRange &CR1,
2204
                                            const ConstantRange &CR2) {
2205
    // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the
2206
    // operations have overflow / have no overflow.
2207
    bool RangeHasOverflowLow = false;
2208
    bool RangeHasOverflowHigh = false;
2209
    bool RangeHasNoOverflow = false;
2210
    ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
2211
      ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
2212
        bool IsOverflowHigh;
2213
        if (!OverflowFn(IsOverflowHigh, N1, N2)) {
2214
          RangeHasNoOverflow = true;
2215
          return;
2216
        }
2217

2218
        if (IsOverflowHigh)
2219
          RangeHasOverflowHigh = true;
2220
        else
2221
          RangeHasOverflowLow = true;
2222
      });
2223
    });
2224

2225
    ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2);
2226
    switch (OR) {
2227
    case ConstantRange::OverflowResult::AlwaysOverflowsLow:
2228
      EXPECT_TRUE(RangeHasOverflowLow);
2229
      EXPECT_FALSE(RangeHasOverflowHigh);
2230
      EXPECT_FALSE(RangeHasNoOverflow);
2231
      break;
2232
    case ConstantRange::OverflowResult::AlwaysOverflowsHigh:
2233
      EXPECT_TRUE(RangeHasOverflowHigh);
2234
      EXPECT_FALSE(RangeHasOverflowLow);
2235
      EXPECT_FALSE(RangeHasNoOverflow);
2236
      break;
2237
    case ConstantRange::OverflowResult::NeverOverflows:
2238
      EXPECT_FALSE(RangeHasOverflowLow);
2239
      EXPECT_FALSE(RangeHasOverflowHigh);
2240
      EXPECT_TRUE(RangeHasNoOverflow);
2241
      break;
2242
    case ConstantRange::OverflowResult::MayOverflow:
2243
      // We return MayOverflow for empty sets as a conservative result,
2244
      // but of course neither the RangeHasOverflow nor the
2245
      // RangeHasNoOverflow flags will be set.
2246
      if (CR1.isEmptySet() || CR2.isEmptySet())
2247
        break;
2248

2249
      EXPECT_TRUE(RangeHasOverflowLow || RangeHasOverflowHigh);
2250
      EXPECT_TRUE(RangeHasNoOverflow);
2251
      break;
2252
    }
2253
  });
2254
}
2255

2256
TEST_F(ConstantRangeTest, UnsignedAddOverflowExhaustive) {
2257
  TestOverflowExhaustive(
2258
      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2259
        bool Overflow;
2260
        (void) N1.uadd_ov(N2, Overflow);
2261
        IsOverflowHigh = true;
2262
        return Overflow;
2263
      },
2264
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2265
        return CR1.unsignedAddMayOverflow(CR2);
2266
      });
2267
}
2268

2269
TEST_F(ConstantRangeTest, UnsignedSubOverflowExhaustive) {
2270
  TestOverflowExhaustive(
2271
      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2272
        bool Overflow;
2273
        (void) N1.usub_ov(N2, Overflow);
2274
        IsOverflowHigh = false;
2275
        return Overflow;
2276
      },
2277
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2278
        return CR1.unsignedSubMayOverflow(CR2);
2279
      });
2280
}
2281

2282
TEST_F(ConstantRangeTest, UnsignedMulOverflowExhaustive) {
2283
  TestOverflowExhaustive(
2284
      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2285
        bool Overflow;
2286
        (void) N1.umul_ov(N2, Overflow);
2287
        IsOverflowHigh = true;
2288
        return Overflow;
2289
      },
2290
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2291
        return CR1.unsignedMulMayOverflow(CR2);
2292
      });
2293
}
2294

2295
TEST_F(ConstantRangeTest, SignedAddOverflowExhaustive) {
2296
  TestOverflowExhaustive(
2297
      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2298
        bool Overflow;
2299
        (void) N1.sadd_ov(N2, Overflow);
2300
        IsOverflowHigh = N1.isNonNegative();
2301
        return Overflow;
2302
      },
2303
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2304
        return CR1.signedAddMayOverflow(CR2);
2305
      });
2306
}
2307

2308
TEST_F(ConstantRangeTest, SignedSubOverflowExhaustive) {
2309
  TestOverflowExhaustive(
2310
      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2311
        bool Overflow;
2312
        (void) N1.ssub_ov(N2, Overflow);
2313
        IsOverflowHigh = N1.isNonNegative();
2314
        return Overflow;
2315
      },
2316
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2317
        return CR1.signedSubMayOverflow(CR2);
2318
      });
2319
}
2320

2321
TEST_F(ConstantRangeTest, FromKnownBits) {
2322
  KnownBits Unknown(16);
2323
  EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false));
2324
  EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true));
2325

2326
  // .10..01. -> unsigned 01000010 (66)  to 11011011 (219)
2327
  //          -> signed   11000010 (194) to 01011011 (91)
2328
  KnownBits Known(8);
2329
  Known.Zero = 36;
2330
  Known.One = 66;
2331
  ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1));
2332
  ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1));
2333
  EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false));
2334
  EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true));
2335

2336
  // 1.10.10. -> 10100100 (164) to 11101101 (237)
2337
  Known.Zero = 18;
2338
  Known.One = 164;
2339
  ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1));
2340
  EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false));
2341
  EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true));
2342

2343
  // 01.0.1.0 -> 01000100 (68) to 01101110 (110)
2344
  Known.Zero = 145;
2345
  Known.One = 68;
2346
  ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1));
2347
  EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false));
2348
  EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true));
2349
}
2350

2351
TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {
2352
  unsigned Bits = 4;
2353
  unsigned Max = 1 << Bits;
2354
  KnownBits Known(Bits);
2355
  for (unsigned Zero = 0; Zero < Max; ++Zero) {
2356
    for (unsigned One = 0; One < Max; ++One) {
2357
      Known.Zero = Zero;
2358
      Known.One = One;
2359
      if (Known.hasConflict() || Known.isUnknown())
2360
        continue;
2361

2362
      SmallBitVector Elems(1 << Bits);
2363
      for (unsigned N = 0; N < Max; ++N) {
2364
        APInt Num(Bits, N);
2365
        if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
2366
          continue;
2367
        Elems.set(Num.getZExtValue());
2368
      }
2369

2370
      TestRange(ConstantRange::fromKnownBits(Known, false),
2371
                Elems, PreferSmallestUnsigned, {});
2372
      TestRange(ConstantRange::fromKnownBits(Known, true),
2373
                Elems, PreferSmallestSigned, {});
2374
    }
2375
  }
2376
}
2377

2378
TEST_F(ConstantRangeTest, ToKnownBits) {
2379
  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
2380
    KnownBits Known = CR.toKnownBits();
2381
    KnownBits ExpectedKnown(CR.getBitWidth());
2382
    ExpectedKnown.Zero.setAllBits();
2383
    ExpectedKnown.One.setAllBits();
2384
    ForeachNumInConstantRange(CR, [&](const APInt &N) {
2385
      ExpectedKnown.One &= N;
2386
      ExpectedKnown.Zero &= ~N;
2387
    });
2388
    // For an empty CR any result would be legal.
2389
    if (!CR.isEmptySet()) {
2390
      EXPECT_EQ(ExpectedKnown, Known);
2391
    }
2392
  });
2393
}
2394

2395
TEST_F(ConstantRangeTest, Negative) {
2396
  // All elements in an empty set (of which there are none) are both negative
2397
  // and non-negative. Empty & full sets checked explicitly for clarity, but
2398
  // they are also covered by the exhaustive test below.
2399
  EXPECT_TRUE(Empty.isAllNegative());
2400
  EXPECT_TRUE(Empty.isAllNonNegative());
2401
  EXPECT_TRUE(Empty.isAllPositive());
2402
  EXPECT_FALSE(Full.isAllNegative());
2403
  EXPECT_FALSE(Full.isAllNonNegative());
2404
  EXPECT_FALSE(Full.isAllPositive());
2405

2406
  EnumerateInterestingConstantRanges([](const ConstantRange &CR) {
2407
    bool AllNegative = true;
2408
    bool AllNonNegative = true;
2409
    bool AllPositive = true;
2410
    ForeachNumInConstantRange(CR, [&](const APInt &N) {
2411
      if (!N.isNegative())
2412
        AllNegative = false;
2413
      if (!N.isNonNegative())
2414
        AllNonNegative = false;
2415
      if (!N.isStrictlyPositive())
2416
        AllPositive = false;
2417
    });
2418
    assert(
2419
        (CR.isEmptySet() || !AllNegative || !AllNonNegative || !AllPositive) &&
2420
        "Only empty set can be all negative, all non-negative, and all "
2421
        "positive");
2422

2423
    EXPECT_EQ(AllNegative, CR.isAllNegative());
2424
    EXPECT_EQ(AllNonNegative, CR.isAllNonNegative());
2425
    EXPECT_EQ(AllPositive, CR.isAllPositive());
2426
  });
2427
}
2428

2429
TEST_F(ConstantRangeTest, UAddSat) {
2430
  TestBinaryOpExhaustive(
2431
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2432
        return CR1.uadd_sat(CR2);
2433
      },
2434
      [](const APInt &N1, const APInt &N2) {
2435
        return N1.uadd_sat(N2);
2436
      },
2437
      PreferSmallestUnsigned);
2438
}
2439

2440
TEST_F(ConstantRangeTest, USubSat) {
2441
  TestBinaryOpExhaustive(
2442
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2443
        return CR1.usub_sat(CR2);
2444
      },
2445
      [](const APInt &N1, const APInt &N2) {
2446
        return N1.usub_sat(N2);
2447
      },
2448
      PreferSmallestUnsigned);
2449
}
2450

2451
TEST_F(ConstantRangeTest, UMulSat) {
2452
  TestBinaryOpExhaustive(
2453
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2454
        return CR1.umul_sat(CR2);
2455
      },
2456
      [](const APInt &N1, const APInt &N2) { return N1.umul_sat(N2); },
2457
      PreferSmallestUnsigned);
2458
}
2459

2460
TEST_F(ConstantRangeTest, UShlSat) {
2461
  TestBinaryOpExhaustive(
2462
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2463
        return CR1.ushl_sat(CR2);
2464
      },
2465
      [](const APInt &N1, const APInt &N2) { return N1.ushl_sat(N2); },
2466
      PreferSmallestUnsigned);
2467
}
2468

2469
TEST_F(ConstantRangeTest, SAddSat) {
2470
  TestBinaryOpExhaustive(
2471
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2472
        return CR1.sadd_sat(CR2);
2473
      },
2474
      [](const APInt &N1, const APInt &N2) {
2475
        return N1.sadd_sat(N2);
2476
      },
2477
      PreferSmallestSigned);
2478
}
2479

2480
TEST_F(ConstantRangeTest, SSubSat) {
2481
  TestBinaryOpExhaustive(
2482
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2483
        return CR1.ssub_sat(CR2);
2484
      },
2485
      [](const APInt &N1, const APInt &N2) {
2486
        return N1.ssub_sat(N2);
2487
      },
2488
      PreferSmallestSigned);
2489
}
2490

2491
TEST_F(ConstantRangeTest, SMulSat) {
2492
  TestBinaryOpExhaustive(
2493
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2494
        return CR1.smul_sat(CR2);
2495
      },
2496
      [](const APInt &N1, const APInt &N2) { return N1.smul_sat(N2); },
2497
      PreferSmallestSigned);
2498
}
2499

2500
TEST_F(ConstantRangeTest, SShlSat) {
2501
  TestBinaryOpExhaustive(
2502
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2503
        return CR1.sshl_sat(CR2);
2504
      },
2505
      [](const APInt &N1, const APInt &N2) { return N1.sshl_sat(N2); },
2506
      PreferSmallestSigned);
2507
}
2508

2509
TEST_F(ConstantRangeTest, Abs) {
2510
  TestUnaryOpExhaustive(
2511
      [](const ConstantRange &CR) { return CR.abs(); },
2512
      [](const APInt &N) { return N.abs(); });
2513

2514
  TestUnaryOpExhaustive(
2515
      [](const ConstantRange &CR) { return CR.abs(/*IntMinIsPoison=*/true); },
2516
      [](const APInt &N) -> std::optional<APInt> {
2517
        if (N.isMinSignedValue())
2518
          return std::nullopt;
2519
        return N.abs();
2520
      });
2521
}
2522

2523
TEST_F(ConstantRangeTest, Ctlz) {
2524
  TestUnaryOpExhaustive(
2525
      [](const ConstantRange &CR) { return CR.ctlz(); },
2526
      [](const APInt &N) { return APInt(N.getBitWidth(), N.countl_zero()); });
2527

2528
  TestUnaryOpExhaustive(
2529
      [](const ConstantRange &CR) { return CR.ctlz(/*ZeroIsPoison=*/true); },
2530
      [](const APInt &N) -> std::optional<APInt> {
2531
        if (N.isZero())
2532
          return std::nullopt;
2533
        return APInt(N.getBitWidth(), N.countl_zero());
2534
      });
2535
}
2536

2537
TEST_F(ConstantRangeTest, Cttz) {
2538
  TestUnaryOpExhaustive(
2539
      [](const ConstantRange &CR) { return CR.cttz(); },
2540
      [](const APInt &N) { return APInt(N.getBitWidth(), N.countr_zero()); });
2541

2542
  TestUnaryOpExhaustive(
2543
      [](const ConstantRange &CR) { return CR.cttz(/*ZeroIsPoison=*/true); },
2544
      [](const APInt &N) -> std::optional<APInt> {
2545
        if (N.isZero())
2546
          return std::nullopt;
2547
        return APInt(N.getBitWidth(), N.countr_zero());
2548
      });
2549
}
2550

2551
TEST_F(ConstantRangeTest, Ctpop) {
2552
  TestUnaryOpExhaustive(
2553
      [](const ConstantRange &CR) { return CR.ctpop(); },
2554
      [](const APInt &N) { return APInt(N.getBitWidth(), N.popcount()); });
2555
}
2556

2557
TEST_F(ConstantRangeTest, castOps) {
2558
  ConstantRange A(APInt(16, 66), APInt(16, 128));
2559
  ConstantRange FpToI8 = A.castOp(Instruction::FPToSI, 8);
2560
  EXPECT_EQ(8u, FpToI8.getBitWidth());
2561
  EXPECT_TRUE(FpToI8.isFullSet());
2562

2563
  ConstantRange FpToI16 = A.castOp(Instruction::FPToSI, 16);
2564
  EXPECT_EQ(16u, FpToI16.getBitWidth());
2565
  EXPECT_EQ(A, FpToI16);
2566

2567
  ConstantRange FPExtToDouble = A.castOp(Instruction::FPExt, 64);
2568
  EXPECT_EQ(64u, FPExtToDouble.getBitWidth());
2569
  EXPECT_TRUE(FPExtToDouble.isFullSet());
2570

2571
  ConstantRange PtrToInt = A.castOp(Instruction::PtrToInt, 64);
2572
  EXPECT_EQ(64u, PtrToInt.getBitWidth());
2573
  EXPECT_TRUE(PtrToInt.isFullSet());
2574

2575
  ConstantRange IntToPtr = A.castOp(Instruction::IntToPtr, 64);
2576
  EXPECT_EQ(64u, IntToPtr.getBitWidth());
2577
  EXPECT_TRUE(IntToPtr.isFullSet());
2578

2579
  ConstantRange UIToFP = A.castOp(Instruction::UIToFP, 16);
2580
  EXPECT_EQ(16u, UIToFP.getBitWidth());
2581
  EXPECT_TRUE(UIToFP.isFullSet());
2582

2583
  ConstantRange UIToFP2 = A.castOp(Instruction::UIToFP, 64);
2584
  ConstantRange B(APInt(64, 0), APInt(64, 65536));
2585
  EXPECT_EQ(64u, UIToFP2.getBitWidth());
2586
  EXPECT_EQ(B, UIToFP2);
2587

2588
  ConstantRange SIToFP = A.castOp(Instruction::SIToFP, 16);
2589
  EXPECT_EQ(16u, SIToFP.getBitWidth());
2590
  EXPECT_TRUE(SIToFP.isFullSet());
2591

2592
  ConstantRange SIToFP2 = A.castOp(Instruction::SIToFP, 64);
2593
  ConstantRange C(APInt(64, -32768), APInt(64, 32768));
2594
  EXPECT_EQ(64u, SIToFP2.getBitWidth());
2595
  EXPECT_EQ(C, SIToFP2);
2596
}
2597

2598
TEST_F(ConstantRangeTest, binaryAnd) {
2599
  // Single element ranges.
2600
  ConstantRange R16(APInt(8, 16));
2601
  ConstantRange R20(APInt(8, 20));
2602
  EXPECT_EQ(*R16.binaryAnd(R16).getSingleElement(), APInt(8, 16));
2603
  EXPECT_EQ(*R16.binaryAnd(R20).getSingleElement(), APInt(8, 16 & 20));
2604

2605
  ConstantRange R16_32(APInt(8, 16), APInt(8, 32));
2606
  // 'And' with a high bits mask.
2607
  ConstantRange R32(APInt(8, 32));
2608
  EXPECT_TRUE(R16_32.binaryAnd(R32).getSingleElement()->isZero());
2609
  EXPECT_TRUE(R32.binaryAnd(R16_32).getSingleElement()->isZero());
2610
  // 'And' with a low bits mask. Handled conservatively for now.
2611
  ConstantRange R4(APInt(8, 4));
2612
  ConstantRange R0_5(APInt(8, 0), APInt(8, 5));
2613
  EXPECT_EQ(R16_32.binaryAnd(R4), R0_5);
2614
  EXPECT_EQ(R4.binaryAnd(R16_32), R0_5);
2615

2616
  // Ranges with more than one element. Handled conservatively for now.
2617
  ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
2618
  ConstantRange R0_32(APInt(8, 0), APInt(8, 32));
2619
  EXPECT_EQ(R16_32.binaryAnd(R0_99), R0_32);
2620
  EXPECT_EQ(R0_99.binaryAnd(R16_32), R0_32);
2621

2622
  TestBinaryOpExhaustive(
2623
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2624
        return CR1.binaryAnd(CR2);
2625
      },
2626
      [](const APInt &N1, const APInt &N2) { return N1 & N2; }, PreferSmallest,
2627
      CheckSingleElementsOnly);
2628
}
2629

2630
TEST_F(ConstantRangeTest, binaryOr) {
2631
  // Single element ranges.
2632
  ConstantRange R16(APInt(8, 16));
2633
  ConstantRange R20(APInt(8, 20));
2634
  EXPECT_EQ(*R16.binaryOr(R16).getSingleElement(), APInt(8, 16));
2635
  EXPECT_EQ(*R16.binaryOr(R20).getSingleElement(), APInt(8, 16 | 20));
2636

2637
  ConstantRange R16_32(APInt(8, 16), APInt(8, 32));
2638
  // 'Or' with a high bits mask.
2639
  // KnownBits estimate is important, otherwise the maximum included element
2640
  // would be 2^8 - 1.
2641
  ConstantRange R32(APInt(8, 32));
2642
  ConstantRange R48_64(APInt(8, 48), APInt(8, 64));
2643
  EXPECT_EQ(R16_32.binaryOr(R32), R48_64);
2644
  EXPECT_EQ(R32.binaryOr(R16_32), R48_64);
2645
  // 'Or' with a low bits mask.
2646
  ConstantRange R4(APInt(8, 4));
2647
  ConstantRange R0_16(APInt(8, 0), APInt(8, 16));
2648
  ConstantRange R4_16(APInt(8, 4), APInt(8, 16));
2649
  EXPECT_EQ(R0_16.binaryOr(R4), R4_16);
2650
  EXPECT_EQ(R4.binaryOr(R0_16), R4_16);
2651

2652
  // Ranges with more than one element. Handled conservatively for now.
2653
  // UMaxUMin estimate is important, otherwise the lower bound would be zero.
2654
  ConstantRange R0_64(APInt(8, 0), APInt(8, 64));
2655
  ConstantRange R5_32(APInt(8, 5), APInt(8, 32));
2656
  ConstantRange R5_64(APInt(8, 5), APInt(8, 64));
2657
  EXPECT_EQ(R0_64.binaryOr(R5_32), R5_64);
2658
  EXPECT_EQ(R5_32.binaryOr(R0_64), R5_64);
2659

2660
  TestBinaryOpExhaustive(
2661
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2662
        return CR1.binaryOr(CR2);
2663
      },
2664
      [](const APInt &N1, const APInt &N2) { return N1 | N2; }, PreferSmallest,
2665
      CheckSingleElementsOnly);
2666
}
2667

2668
TEST_F(ConstantRangeTest, binaryXor) {
2669
  // Single element ranges.
2670
  ConstantRange R16(APInt(8, 16));
2671
  ConstantRange R20(APInt(8, 20));
2672
  EXPECT_EQ(*R16.binaryXor(R16).getSingleElement(), APInt(8, 0));
2673
  EXPECT_EQ(*R16.binaryXor(R20).getSingleElement(), APInt(8, 16 ^ 20));
2674

2675
  // Ranges with more than a single element.
2676
  ConstantRange R16_35(APInt(8, 16), APInt(8, 35));
2677
  ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
2678
  EXPECT_EQ(R16_35.binaryXor(R16_35), ConstantRange(APInt(8, 0), APInt(8, 64)));
2679
  EXPECT_EQ(R16_35.binaryXor(R0_99), ConstantRange(APInt(8, 0), APInt(8, 128)));
2680
  EXPECT_EQ(R0_99.binaryXor(R16_35), ConstantRange(APInt(8, 0), APInt(8, 128)));
2681

2682
  // Treat xor A, B as sub nsw nuw A, B
2683
  ConstantRange R0_51(APInt(8, 0), APInt(8, 51));
2684
  ConstantRange R63(APInt(8, 63));
2685
  EXPECT_EQ(R0_51.binaryXor(R63), ConstantRange(APInt(8, 13), APInt(8, 64)));
2686
  EXPECT_EQ(R63.binaryXor(R0_51), ConstantRange(APInt(8, 13), APInt(8, 64)));
2687

2688
  TestBinaryOpExhaustive(
2689
      [](const ConstantRange &CR1, const ConstantRange &CR2) {
2690
        return CR1.binaryXor(CR2);
2691
      },
2692
      [](const APInt &N1, const APInt &N2) {
2693
        return N1 ^ N2;
2694
      },
2695
      PreferSmallest,
2696
      CheckSingleElementsOnly);
2697
}
2698

2699
TEST_F(ConstantRangeTest, binaryNot) {
2700
  TestUnaryOpExhaustive(
2701
      [](const ConstantRange &CR) { return CR.binaryNot(); },
2702
      [](const APInt &N) { return ~N; },
2703
      PreferSmallest);
2704
  TestUnaryOpExhaustive(
2705
      [](const ConstantRange &CR) {
2706
        return CR.binaryXor(ConstantRange(APInt::getAllOnes(CR.getBitWidth())));
2707
      },
2708
      [](const APInt &N) { return ~N; }, PreferSmallest);
2709
  TestUnaryOpExhaustive(
2710
      [](const ConstantRange &CR) {
2711
        return ConstantRange(APInt::getAllOnes(CR.getBitWidth())).binaryXor(CR);
2712
      },
2713
      [](const APInt &N) { return ~N; }, PreferSmallest);
2714
}
2715

2716
template <typename T>
2717
void testConstantRangeICmpPredEquivalence(ICmpInst::Predicate SrcPred, T Func) {
2718
  EnumerateTwoInterestingConstantRanges(
2719
      [&](const ConstantRange &CR1, const ConstantRange &CR2) {
2720
        ICmpInst::Predicate TgtPred;
2721
        bool ExpectedEquivalent;
2722
        std::tie(TgtPred, ExpectedEquivalent) = Func(CR1, CR2);
2723
        if (TgtPred == CmpInst::Predicate::BAD_ICMP_PREDICATE)
2724
          return;
2725
        bool TrulyEquivalent = true;
2726
        ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
2727
          if (!TrulyEquivalent)
2728
            return;
2729
          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
2730
            if (!TrulyEquivalent)
2731
              return;
2732
            TrulyEquivalent &= ICmpInst::compare(N1, N2, SrcPred) ==
2733
                               ICmpInst::compare(N1, N2, TgtPred);
2734
          });
2735
        });
2736
        ASSERT_EQ(TrulyEquivalent, ExpectedEquivalent);
2737
      });
2738
}
2739

2740
TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfICmpPredicate) {
2741
  for (auto Pred : ICmpInst::predicates()) {
2742
    if (ICmpInst::isEquality(Pred))
2743
      continue;
2744
    ICmpInst::Predicate FlippedSignednessPred =
2745
        ICmpInst::getFlippedSignednessPredicate(Pred);
2746
    testConstantRangeICmpPredEquivalence(Pred, [FlippedSignednessPred](
2747
                                                   const ConstantRange &CR1,
2748
                                                   const ConstantRange &CR2) {
2749
      return std::make_pair(
2750
          FlippedSignednessPred,
2751
          ConstantRange::areInsensitiveToSignednessOfICmpPredicate(CR1, CR2));
2752
    });
2753
  }
2754
}
2755

2756
TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfInvertedICmpPredicate) {
2757
  for (auto Pred : ICmpInst::predicates()) {
2758
    if (ICmpInst::isEquality(Pred))
2759
      continue;
2760
    ICmpInst::Predicate InvertedFlippedSignednessPred =
2761
        ICmpInst::getInversePredicate(
2762
            ICmpInst::getFlippedSignednessPredicate(Pred));
2763
    testConstantRangeICmpPredEquivalence(
2764
        Pred, [InvertedFlippedSignednessPred](const ConstantRange &CR1,
2765
                                              const ConstantRange &CR2) {
2766
          return std::make_pair(
2767
              InvertedFlippedSignednessPred,
2768
              ConstantRange::areInsensitiveToSignednessOfInvertedICmpPredicate(
2769
                  CR1, CR2));
2770
        });
2771
  }
2772
}
2773

2774
TEST_F(ConstantRangeTest, getEquivalentPredWithFlippedSignedness) {
2775
  for (auto Pred : ICmpInst::predicates()) {
2776
    if (ICmpInst::isEquality(Pred))
2777
      continue;
2778
    testConstantRangeICmpPredEquivalence(
2779
        Pred, [Pred](const ConstantRange &CR1, const ConstantRange &CR2) {
2780
          return std::make_pair(
2781
              ConstantRange::getEquivalentPredWithFlippedSignedness(Pred, CR1,
2782
                                                                    CR2),
2783
              /*ExpectedEquivalent=*/true);
2784
        });
2785
  }
2786
}
2787

2788
TEST_F(ConstantRangeTest, isSizeLargerThan) {
2789
  EXPECT_FALSE(Empty.isSizeLargerThan(0));
2790

2791
  EXPECT_TRUE(Full.isSizeLargerThan(0));
2792
  EXPECT_TRUE(Full.isSizeLargerThan(65535));
2793
  EXPECT_FALSE(Full.isSizeLargerThan(65536));
2794

2795
  EXPECT_TRUE(One.isSizeLargerThan(0));
2796
  EXPECT_FALSE(One.isSizeLargerThan(1));
2797
}
2798

2799
TEST_F(ConstantRangeTest, MakeMaskNotEqualRange) {
2800
  // Mask: 0b0001, C: 0b0001. MMNE() = [2, 1)
2801
  ConstantRange CR(APInt(4, 2), APInt(4, 1));
2802
  EXPECT_EQ(CR, ConstantRange::makeMaskNotEqualRange(APInt(4, 1), APInt(4, 1)));
2803
  EXPECT_NE(CR, ConstantRange::makeMaskNotEqualRange(APInt(4, 0),
2804
                                                     APInt(4, -1, true)));
2805
  EXPECT_TRUE(CR.contains(APInt(4, 7)));
2806
  EXPECT_TRUE(CR.contains(APInt(4, 15)));
2807

2808
  // Mask: 0b0100, C: 0b0100. MMNE() = [-8, 4)
2809
  ConstantRange CR2(APInt(4, -8, true), APInt(4, 4));
2810
  auto MMNE = ConstantRange::makeMaskNotEqualRange(APInt(4, 4), APInt(4, 4));
2811
  EXPECT_EQ(CR2, MMNE);
2812
  EXPECT_NE(ConstantRange::getNonEmpty(APInt(4, 0), APInt(4, -4, true)), MMNE);
2813

2814
  // CR: [-16, -8). MMNE() = [-8, -16)
2815
  ConstantRange CR3(APInt(8, 240), APInt(8, 248));
2816
  EXPECT_EQ(CR3.inverse(),
2817
            ConstantRange::makeMaskNotEqualRange(APInt(8, 248), APInt(8, 240)));
2818

2819
  // Mask: 0, C: 0b1111: unsatisfiable.
2820
  EXPECT_EQ(ConstantRange::getFull(4),
2821
            ConstantRange::makeMaskNotEqualRange(APInt(4, 0), APInt(4, 15)));
2822
}
2823

2824
TEST_F(ConstantRangeTest, MakeMaskNotEqualRangeExhaustive) {
2825
  unsigned Bits = 4;
2826
  unsigned Max = 1 << Bits;
2827

2828
  EnumerateAPInts(Bits, [&](const APInt &Mask) {
2829
    EnumerateAPInts(Bits, [&](const APInt &C) {
2830
      SmallBitVector Elems(Max);
2831
      for (unsigned N = 0; N < Max; ++N) {
2832
        APInt Num(Bits, N);
2833
        if ((Num & Mask) == C)
2834
          continue;
2835
        Elems.set(Num.getZExtValue());
2836
      }
2837

2838
      // Only test optimality with PreferSmallest. E.g., given Mask = 0b0001, C
2839
      // = 0b0001, a possible better range would be [0, 15) when preferring the
2840
      // smallest unsigned, however we conservatively return [2, 1).
2841
      TestRange(ConstantRange::makeMaskNotEqualRange(Mask, C), Elems,
2842
                PreferSmallest, {});
2843
    });
2844
  });
2845
}
2846

2847
} // anonymous namespace
2848

Использование cookies

Мы используем файлы cookie в соответствии с Политикой конфиденциальности и Политикой использования cookies.

Нажимая кнопку «Принимаю», Вы даете АО «СберТех» согласие на обработку Ваших персональных данных в целях совершенствования нашего веб-сайта и Сервиса GitVerse, а также повышения удобства их использования.

Запретить использование cookies Вы можете самостоятельно в настройках Вашего браузера.