brintos / llvm-project-archived public Read only

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-exception6//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 18using namespace llvm;19 20namespace {21 22class ConstantRangeTest : public ::testing::Test {23protected:24  static ConstantRange Full;25  static ConstantRange Empty;26  static ConstantRange One;27  static ConstantRange Some;28  static ConstantRange Wrap;29};30 31template<typename Fn>32static void EnumerateAPInts(unsigned Bits, Fn TestFn) {33  APInt N(Bits, 0);34  do {35    TestFn(N);36  } while (++N != 0);37}38 39template<typename Fn>40static 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 54template <typename Fn>55static 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 62template <typename Fn>63static 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 72template <typename Fn>73static 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 81using PreferFn = llvm::function_ref<bool(const ConstantRange &,82                                         const ConstantRange &)>;83 84bool PreferSmallest(const ConstantRange &CR1, const ConstantRange &CR2) {85  return CR1.isSizeStrictlySmallerThan(CR2);86}87 88bool 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 95bool 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 101bool 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 108bool 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 115testing::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 set128// Elems under the given PreferenceFn. The preference function should return129// true if the first range argument is strictly preferred to the second one.130static 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 ranges162  // [Elem, PrevElem] they imply. Check that none of the ranges are strictly163  // 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. Avoid175    // 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 186using UnaryRangeFn = llvm::function_ref<ConstantRange(const ConstantRange &)>;187using UnaryIntFn = llvm::function_ref<std::optional<APInt>(const APInt &)>;188 189static 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 201using BinaryRangeFn = llvm::function_ref<ConstantRange(const ConstantRange &,202                                                       const ConstantRange &)>;203using BinaryIntFn =204    llvm::function_ref<std::optional<APInt>(const APInt &, const APInt &)>;205using BinaryCheckFn = llvm::function_ref<bool(const ConstantRange &,206                                              const ConstantRange &)>;207 208static bool CheckAll(const ConstantRange &, const ConstantRange &) {209  return true;210}211 212static bool CheckCorrectnessOnly(const ConstantRange &, const ConstantRange &) {213  return false;214}215 216static bool CheckSingleElementsOnly(const ConstantRange &CR1,217                                    const ConstantRange &CR2) {218  return CR1.isSingleElement() && CR2.isSingleElement();219}220 221static bool CheckNonWrappedOnly(const ConstantRange &CR1,222                                const ConstantRange &CR2) {223  return !CR1.isWrappedSet() && !CR2.isWrappedSet();224}225 226static bool CheckNonSignWrappedOnly(const ConstantRange &CR1,227                                    const ConstantRange &CR2) {228  return !CR1.isSignWrappedSet() && !CR2.isSignWrappedSet();229}230 231static bool232CheckNoSignedWrappedLHSAndNoWrappedRHSOnly(const ConstantRange &CR1,233                                           const ConstantRange &CR2) {234  return !CR1.isSignWrappedSet() && !CR2.isWrappedSet();235}236 237static bool CheckNonWrappedOrSignWrappedOnly(const ConstantRange &CR1,238                                             const ConstantRange &CR2) {239  return !CR1.isWrappedSet() && !CR1.isSignWrappedSet() &&240         !CR2.isWrappedSet() && !CR2.isSignWrappedSet();241}242 243// CheckFn determines whether optimality is checked for a given range pair.244// Correctness is always checked.245static void TestBinaryOpExhaustive(BinaryRangeFn RangeFn, BinaryIntFn IntFn,246                                   PreferFn PreferenceFn = PreferSmallest,247                                   BinaryCheckFn CheckFn = CheckAll) {248  EnumerateTwoInterestingConstantRanges(249      [&](const ConstantRange &CR1, const ConstantRange &CR2) {250        SmallBitVector Elems(1 << CR1.getBitWidth());251        ForeachNumInConstantRange(CR1, [&](const APInt &N1) {252          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {253            if (std::optional<APInt> ResultN = IntFn(N1, N2))254              Elems.set(ResultN->getZExtValue());255          });256        });257        TestRange(RangeFn(CR1, CR2), Elems, PreferenceFn, {CR1, CR2},258                  CheckFn(CR1, CR2));259      });260}261 262ConstantRange ConstantRangeTest::Full(16, true);263ConstantRange ConstantRangeTest::Empty(16, false);264ConstantRange ConstantRangeTest::One(APInt(16, 0xa));265ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));266ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));267 268TEST_F(ConstantRangeTest, Basics) {269  EXPECT_TRUE(Full.isFullSet());270  EXPECT_FALSE(Full.isEmptySet());271  EXPECT_TRUE(Full.inverse().isEmptySet());272  EXPECT_FALSE(Full.isWrappedSet());273  EXPECT_TRUE(Full.contains(APInt(16, 0x0)));274  EXPECT_TRUE(Full.contains(APInt(16, 0x9)));275  EXPECT_TRUE(Full.contains(APInt(16, 0xa)));276  EXPECT_TRUE(Full.contains(APInt(16, 0xaa9)));277  EXPECT_TRUE(Full.contains(APInt(16, 0xaaa)));278 279  EXPECT_FALSE(Empty.isFullSet());280  EXPECT_TRUE(Empty.isEmptySet());281  EXPECT_TRUE(Empty.inverse().isFullSet());282  EXPECT_FALSE(Empty.isWrappedSet());283  EXPECT_FALSE(Empty.contains(APInt(16, 0x0)));284  EXPECT_FALSE(Empty.contains(APInt(16, 0x9)));285  EXPECT_FALSE(Empty.contains(APInt(16, 0xa)));286  EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9)));287  EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa)));288 289  EXPECT_FALSE(One.isFullSet());290  EXPECT_FALSE(One.isEmptySet());291  EXPECT_FALSE(One.isWrappedSet());292  EXPECT_FALSE(One.contains(APInt(16, 0x0)));293  EXPECT_FALSE(One.contains(APInt(16, 0x9)));294  EXPECT_TRUE(One.contains(APInt(16, 0xa)));295  EXPECT_FALSE(One.contains(APInt(16, 0xaa9)));296  EXPECT_FALSE(One.contains(APInt(16, 0xaaa)));297  EXPECT_FALSE(One.inverse().contains(APInt(16, 0xa)));298 299  EXPECT_FALSE(Some.isFullSet());300  EXPECT_FALSE(Some.isEmptySet());301  EXPECT_FALSE(Some.isWrappedSet());302  EXPECT_FALSE(Some.contains(APInt(16, 0x0)));303  EXPECT_FALSE(Some.contains(APInt(16, 0x9)));304  EXPECT_TRUE(Some.contains(APInt(16, 0xa)));305  EXPECT_TRUE(Some.contains(APInt(16, 0xaa9)));306  EXPECT_FALSE(Some.contains(APInt(16, 0xaaa)));307 308  EXPECT_FALSE(Wrap.isFullSet());309  EXPECT_FALSE(Wrap.isEmptySet());310  EXPECT_TRUE(Wrap.isWrappedSet());311  EXPECT_TRUE(Wrap.contains(APInt(16, 0x0)));312  EXPECT_TRUE(Wrap.contains(APInt(16, 0x9)));313  EXPECT_FALSE(Wrap.contains(APInt(16, 0xa)));314  EXPECT_FALSE(Wrap.contains(APInt(16, 0xaa9)));315  EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa)));316}317 318TEST_F(ConstantRangeTest, Equality) {319  EXPECT_EQ(Full, Full);320  EXPECT_EQ(Empty, Empty);321  EXPECT_EQ(One, One);322  EXPECT_EQ(Some, Some);323  EXPECT_EQ(Wrap, Wrap);324  EXPECT_NE(Full, Empty);325  EXPECT_NE(Full, One);326  EXPECT_NE(Full, Some);327  EXPECT_NE(Full, Wrap);328  EXPECT_NE(Empty, One);329  EXPECT_NE(Empty, Some);330  EXPECT_NE(Empty, Wrap);331  EXPECT_NE(One, Some);332  EXPECT_NE(One, Wrap);333  EXPECT_NE(Some, Wrap);334}335 336TEST_F(ConstantRangeTest, SingleElement) {337  EXPECT_EQ(Full.getSingleElement(), static_cast<APInt *>(nullptr));338  EXPECT_EQ(Empty.getSingleElement(), static_cast<APInt *>(nullptr));339  EXPECT_EQ(Full.getSingleMissingElement(), static_cast<APInt *>(nullptr));340  EXPECT_EQ(Empty.getSingleMissingElement(), static_cast<APInt *>(nullptr));341 342  EXPECT_EQ(*One.getSingleElement(), APInt(16, 0xa));343  EXPECT_EQ(Some.getSingleElement(), static_cast<APInt *>(nullptr));344  EXPECT_EQ(Wrap.getSingleElement(), static_cast<APInt *>(nullptr));345 346  EXPECT_EQ(One.getSingleMissingElement(), static_cast<APInt *>(nullptr));347  EXPECT_EQ(Some.getSingleMissingElement(), static_cast<APInt *>(nullptr));348 349  ConstantRange OneInverse = One.inverse();350  EXPECT_EQ(*OneInverse.getSingleMissingElement(), *One.getSingleElement());351 352  EXPECT_FALSE(Full.isSingleElement());353  EXPECT_FALSE(Empty.isSingleElement());354  EXPECT_TRUE(One.isSingleElement());355  EXPECT_FALSE(Some.isSingleElement());356  EXPECT_FALSE(Wrap.isSingleElement());357}358 359TEST_F(ConstantRangeTest, GetMinsAndMaxes) {360  EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX));361  EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa));362  EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9));363  EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX));364 365  EXPECT_EQ(Full.getUnsignedMin(), APInt(16, 0));366  EXPECT_EQ(One.getUnsignedMin(), APInt(16, 0xa));367  EXPECT_EQ(Some.getUnsignedMin(), APInt(16, 0xa));368  EXPECT_EQ(Wrap.getUnsignedMin(), APInt(16, 0));369 370  EXPECT_EQ(Full.getSignedMax(), APInt(16, INT16_MAX));371  EXPECT_EQ(One.getSignedMax(), APInt(16, 0xa));372  EXPECT_EQ(Some.getSignedMax(), APInt(16, 0xaa9));373  EXPECT_EQ(Wrap.getSignedMax(), APInt(16, INT16_MAX));374 375  EXPECT_EQ(Full.getSignedMin(), APInt(16, (uint16_t)INT16_MIN));376  EXPECT_EQ(One.getSignedMin(), APInt(16, 0xa));377  EXPECT_EQ(Some.getSignedMin(), APInt(16, 0xa));378  EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint16_t)INT16_MIN));379 380  // Found by Klee381  EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),382            APInt(4, 7));383}384 385TEST_F(ConstantRangeTest, SignWrapped) {386  EXPECT_FALSE(Full.isSignWrappedSet());387  EXPECT_FALSE(Empty.isSignWrappedSet());388  EXPECT_FALSE(One.isSignWrappedSet());389  EXPECT_FALSE(Some.isSignWrappedSet());390  EXPECT_TRUE(Wrap.isSignWrappedSet());391 392  EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet());393  EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet());394  EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet());395  EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet());396  EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet());397  EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet());398  EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet());399}400 401TEST_F(ConstantRangeTest, UpperWrapped) {402  // The behavior here is the same as for isWrappedSet() / isSignWrappedSet().403  EXPECT_FALSE(Full.isUpperWrapped());404  EXPECT_FALSE(Empty.isUpperWrapped());405  EXPECT_FALSE(One.isUpperWrapped());406  EXPECT_FALSE(Some.isUpperWrapped());407  EXPECT_TRUE(Wrap.isUpperWrapped());408  EXPECT_FALSE(Full.isUpperSignWrapped());409  EXPECT_FALSE(Empty.isUpperSignWrapped());410  EXPECT_FALSE(One.isUpperSignWrapped());411  EXPECT_FALSE(Some.isUpperSignWrapped());412  EXPECT_TRUE(Wrap.isUpperSignWrapped());413 414  // The behavior differs if Upper is the Min/SignedMin value.415  ConstantRange CR1(APInt(8, 42), APInt::getMinValue(8));416  EXPECT_FALSE(CR1.isWrappedSet());417  EXPECT_TRUE(CR1.isUpperWrapped());418 419  ConstantRange CR2(APInt(8, 42), APInt::getSignedMinValue(8));420  EXPECT_FALSE(CR2.isSignWrappedSet());421  EXPECT_TRUE(CR2.isUpperSignWrapped());422}423 424TEST_F(ConstantRangeTest, Trunc) {425  ConstantRange TFull = Full.truncate(10);426  ConstantRange TEmpty = Empty.truncate(10);427  ConstantRange TOne = One.truncate(10);428  ConstantRange TSome = Some.truncate(10);429  ConstantRange TWrap = Wrap.truncate(10);430  EXPECT_TRUE(TFull.isFullSet());431  EXPECT_TRUE(TEmpty.isEmptySet());432  EXPECT_EQ(TOne, ConstantRange(One.getLower().trunc(10),433                                One.getUpper().trunc(10)));434  EXPECT_TRUE(TSome.isFullSet());435  EXPECT_TRUE(TWrap.isFullSet());436 437  // trunc([2, 5), 3->2) = [2, 1)438  ConstantRange TwoFive(APInt(3, 2), APInt(3, 5));439  EXPECT_EQ(TwoFive.truncate(2), ConstantRange(APInt(2, 2), APInt(2, 1)));440 441  // trunc([2, 6), 3->2) = full442  ConstantRange TwoSix(APInt(3, 2), APInt(3, 6));443  EXPECT_TRUE(TwoSix.truncate(2).isFullSet());444 445  // trunc([5, 7), 3->2) = [1, 3)446  ConstantRange FiveSeven(APInt(3, 5), APInt(3, 7));447  EXPECT_EQ(FiveSeven.truncate(2), ConstantRange(APInt(2, 1), APInt(2, 3)));448 449  // trunc([7, 1), 3->2) = [3, 1)450  ConstantRange SevenOne(APInt(3, 7), APInt(3, 1));451  EXPECT_EQ(SevenOne.truncate(2), ConstantRange(APInt(2, 3), APInt(2, 1)));452 453  ConstantRange Nop = Full.truncate(Full.getBitWidth());454  EXPECT_EQ(Full, Nop);455}456 457TEST_F(ConstantRangeTest, TruncNuw) {458  auto Range = [](unsigned NumBits, unsigned Lower, unsigned Upper) {459    return ConstantRange(APInt(NumBits, Lower), APInt(NumBits, Upper));460  };461  // trunc([0, 4), 3->2) = full462  EXPECT_TRUE(463      Range(3, 0, 4).truncate(2, TruncInst::NoUnsignedWrap).isFullSet());464  // trunc([0, 3), 3->2) = [0, 3)465  EXPECT_EQ(Range(3, 0, 3).truncate(2, TruncInst::NoUnsignedWrap),466            Range(2, 0, 3));467  // trunc([1, 3), 3->2) = [1, 3)468  EXPECT_EQ(Range(3, 1, 3).truncate(2, TruncInst::NoUnsignedWrap),469            Range(2, 1, 3));470  // trunc([1, 5), 3->2) = [1, 0)471  EXPECT_EQ(Range(3, 1, 5).truncate(2, TruncInst::NoUnsignedWrap),472            Range(2, 1, 0));473  // trunc([4, 7), 3->2) = empty474  EXPECT_TRUE(475      Range(3, 4, 7).truncate(2, TruncInst::NoUnsignedWrap).isEmptySet());476  // trunc([4, 0), 3->2) = empty477  EXPECT_TRUE(478      Range(3, 4, 0).truncate(2, TruncInst::NoUnsignedWrap).isEmptySet());479  // trunc([4, 1), 3->2) = [0, 1)480  EXPECT_EQ(Range(3, 4, 1).truncate(2, TruncInst::NoUnsignedWrap),481            Range(2, 0, 1));482  // trunc([3, 1), 3->2) = [3, 1)483  EXPECT_EQ(Range(3, 3, 1).truncate(2, TruncInst::NoUnsignedWrap),484            Range(2, 3, 1));485  // trunc([3, 0), 3->2) = [3, 0)486  EXPECT_EQ(Range(3, 3, 0).truncate(2, TruncInst::NoUnsignedWrap),487            Range(2, 3, 0));488  // trunc([1, 0), 2->1) = [1, 0)489  EXPECT_EQ(Range(2, 1, 0).truncate(1, TruncInst::NoUnsignedWrap),490            Range(1, 1, 0));491  // trunc([2, 1), 2->1) = [0, 1)492  EXPECT_EQ(Range(2, 2, 1).truncate(1, TruncInst::NoUnsignedWrap),493            Range(1, 0, 1));494}495 496TEST_F(ConstantRangeTest, TruncNuwExhaustive) {497  EnumerateConstantRanges(4, [&](const ConstantRange &CR) {498    unsigned NumBits = 3;499    ConstantRange Trunc = CR.truncate(NumBits, TruncInst::NoUnsignedWrap);500    SmallBitVector Elems(1 << NumBits);501    ForeachNumInConstantRange(CR, [&](const APInt &N) {502      if (N.isIntN(NumBits))503        Elems.set(N.getZExtValue());504    });505    TestRange(Trunc, Elems, PreferSmallest, {CR});506  });507  EnumerateConstantRanges(3, [&](const ConstantRange &CR) {508    ConstantRange Trunc = CR.truncate(1, TruncInst::NoUnsignedWrap);509    EXPECT_EQ(CR.contains(APInt::getZero(3)),510              Trunc.contains(APInt::getZero(1)));511    EXPECT_EQ(CR.contains(APInt::getOneBitSet(3, 0)),512              Trunc.contains(APInt::getAllOnes(1)));513  });514}515 516TEST_F(ConstantRangeTest, ZExt) {517  ConstantRange ZFull = Full.zeroExtend(20);518  ConstantRange ZEmpty = Empty.zeroExtend(20);519  ConstantRange ZOne = One.zeroExtend(20);520  ConstantRange ZSome = Some.zeroExtend(20);521  ConstantRange ZWrap = Wrap.zeroExtend(20);522  EXPECT_EQ(ZFull, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));523  EXPECT_TRUE(ZEmpty.isEmptySet());524  EXPECT_EQ(ZOne, ConstantRange(One.getLower().zext(20),525                                One.getUpper().zext(20)));526  EXPECT_EQ(ZSome, ConstantRange(Some.getLower().zext(20),527                                 Some.getUpper().zext(20)));528  EXPECT_EQ(ZWrap, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));529 530  // zext([5, 0), 3->7) = [5, 8)531  ConstantRange FiveZero(APInt(3, 5), APInt(3, 0));532  EXPECT_EQ(FiveZero.zeroExtend(7), ConstantRange(APInt(7, 5), APInt(7, 8)));533 534  ConstantRange Nop = Full.zeroExtend(Full.getBitWidth());535  EXPECT_EQ(Full, Nop);536}537 538TEST_F(ConstantRangeTest, SExt) {539  ConstantRange SFull = Full.signExtend(20);540  ConstantRange SEmpty = Empty.signExtend(20);541  ConstantRange SOne = One.signExtend(20);542  ConstantRange SSome = Some.signExtend(20);543  ConstantRange SWrap = Wrap.signExtend(20);544  EXPECT_EQ(SFull, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),545                                 APInt(20, INT16_MAX + 1, true)));546  EXPECT_TRUE(SEmpty.isEmptySet());547  EXPECT_EQ(SOne, ConstantRange(One.getLower().sext(20),548                                One.getUpper().sext(20)));549  EXPECT_EQ(SSome, ConstantRange(Some.getLower().sext(20),550                                 Some.getUpper().sext(20)));551  EXPECT_EQ(SWrap, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),552                                 APInt(20, INT16_MAX + 1, true)));553 554  EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16),555            ConstantRange(APInt(16, -128, true), APInt(16, 128)));556 557  EXPECT_EQ(ConstantRange(APInt(16, 0x0200), APInt(16, 0x8000)).signExtend(19),558            ConstantRange(APInt(19, 0x0200), APInt(19, 0x8000)));559 560  ConstantRange Nop = Full.signExtend(Full.getBitWidth());561  EXPECT_EQ(Full, Nop);562}563 564TEST_F(ConstantRangeTest, IntersectWith) {565  EXPECT_EQ(Empty.intersectWith(Full), Empty);566  EXPECT_EQ(Empty.intersectWith(Empty), Empty);567  EXPECT_EQ(Empty.intersectWith(One), Empty);568  EXPECT_EQ(Empty.intersectWith(Some), Empty);569  EXPECT_EQ(Empty.intersectWith(Wrap), Empty);570  EXPECT_EQ(Full.intersectWith(Full), Full);571  EXPECT_EQ(Some.intersectWith(Some), Some);572  EXPECT_EQ(Some.intersectWith(One), One);573  EXPECT_EQ(Full.intersectWith(One), One);574  EXPECT_EQ(Full.intersectWith(Some), Some);575  EXPECT_EQ(Some.intersectWith(Wrap), Empty);576  EXPECT_EQ(One.intersectWith(Wrap), Empty);577  EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One));578 579  // Klee generated testcase from PR4545.580  // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like581  // 01..4.6789ABCDEF where the dots represent values not in the intersection.582  ConstantRange LHS(APInt(16, 4), APInt(16, 2));583  ConstantRange RHS(APInt(16, 6), APInt(16, 5));584  EXPECT_TRUE(LHS.intersectWith(RHS) == LHS);585 586  // previous bug: intersection of [min, 3) and [2, max) should be 2587  LHS = ConstantRange(APInt(32, (uint32_t)-2147483646), APInt(32, 3));588  RHS = ConstantRange(APInt(32, 2), APInt(32, 2147483646));589  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2)));590 591  // [2, 0) /\ [4, 3) = [2, 0)592  LHS = ConstantRange(APInt(32, 2), APInt(32, 0));593  RHS = ConstantRange(APInt(32, 4), APInt(32, 3));594  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2), APInt(32, 0)));595 596  // [2, 0) /\ [4, 2) = [4, 0)597  LHS = ConstantRange(APInt(32, 2), APInt(32, 0));598  RHS = ConstantRange(APInt(32, 4), APInt(32, 2));599  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0)));600 601  // [4, 2) /\ [5, 1) = [5, 1)602  LHS = ConstantRange(APInt(32, 4), APInt(32, 2));603  RHS = ConstantRange(APInt(32, 5), APInt(32, 1));604  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 5), APInt(32, 1)));605 606  // [2, 0) /\ [7, 4) = [7, 4)607  LHS = ConstantRange(APInt(32, 2), APInt(32, 0));608  RHS = ConstantRange(APInt(32, 7), APInt(32, 4));609  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 4)));610 611  // [4, 2) /\ [1, 0) = [1, 0)612  LHS = ConstantRange(APInt(32, 4), APInt(32, 2));613  RHS = ConstantRange(APInt(32, 1), APInt(32, 0));614  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2)));615 616  // [15, 0) /\ [7, 6) = [15, 0)617  LHS = ConstantRange(APInt(32, 15), APInt(32, 0));618  RHS = ConstantRange(APInt(32, 7), APInt(32, 6));619  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0)));620}621 622template <typename Fn1, typename Fn2, typename Fn3>623void testBinarySetOperationExhaustive(Fn1 OpFn, Fn2 ExactOpFn, Fn3 InResultFn) {624  EnumerateTwoInterestingConstantRanges(625      [=](const ConstantRange &CR1, const ConstantRange &CR2) {626        unsigned Bits = CR1.getBitWidth();627        SmallBitVector Elems(1 << Bits);628        APInt Num(Bits, 0);629        for (unsigned I = 0, Limit = 1 << Bits; I < Limit; ++I, ++Num)630          if (InResultFn(CR1, CR2, Num))631            Elems.set(Num.getZExtValue());632 633        ConstantRange SmallestCR = OpFn(CR1, CR2, ConstantRange::Smallest);634        TestRange(SmallestCR, Elems, PreferSmallest, {CR1, CR2});635 636        ConstantRange UnsignedCR = OpFn(CR1, CR2, ConstantRange::Unsigned);637        TestRange(UnsignedCR, Elems, PreferSmallestNonFullUnsigned, {CR1, CR2});638 639        ConstantRange SignedCR = OpFn(CR1, CR2, ConstantRange::Signed);640        TestRange(SignedCR, Elems, PreferSmallestNonFullSigned, {CR1, CR2});641 642        std::optional<ConstantRange> ExactCR = ExactOpFn(CR1, CR2);643        if (SmallestCR.isSizeLargerThan(Elems.count())) {644          EXPECT_TRUE(!ExactCR);645        } else {646          EXPECT_EQ(SmallestCR, *ExactCR);647        }648      });649}650 651TEST_F(ConstantRangeTest, IntersectWithExhaustive) {652  testBinarySetOperationExhaustive(653      [](const ConstantRange &CR1, const ConstantRange &CR2,654         ConstantRange::PreferredRangeType Type) {655        return CR1.intersectWith(CR2, Type);656      },657      [](const ConstantRange &CR1, const ConstantRange &CR2) {658        return CR1.exactIntersectWith(CR2);659      },660      [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {661        return CR1.contains(N) && CR2.contains(N);662      });663}664 665TEST_F(ConstantRangeTest, UnionWithExhaustive) {666  testBinarySetOperationExhaustive(667      [](const ConstantRange &CR1, const ConstantRange &CR2,668         ConstantRange::PreferredRangeType Type) {669        return CR1.unionWith(CR2, Type);670      },671      [](const ConstantRange &CR1, const ConstantRange &CR2) {672        return CR1.exactUnionWith(CR2);673      },674      [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {675        return CR1.contains(N) || CR2.contains(N);676      });677}678 679TEST_F(ConstantRangeTest, UnionWith) {680  EXPECT_EQ(Wrap.unionWith(One),681            ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));682  EXPECT_EQ(One.unionWith(Wrap), Wrap.unionWith(One));683  EXPECT_EQ(Empty.unionWith(Empty), Empty);684  EXPECT_EQ(Full.unionWith(Full), Full);685  EXPECT_EQ(Some.unionWith(Wrap), Full);686 687  // PR4545688  EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(689                                    ConstantRange(APInt(16, 0), APInt(16, 8))),690            ConstantRange(APInt(16, 14), APInt(16, 8)));691  EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(692                                    ConstantRange(APInt(16, 4), APInt(16, 0))),693            ConstantRange::getFull(16));694  EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(695                                    ConstantRange(APInt(16, 2), APInt(16, 1))),696            ConstantRange::getFull(16));697}698 699TEST_F(ConstantRangeTest, SetDifference) {700  EXPECT_EQ(Full.difference(Empty), Full);701  EXPECT_EQ(Full.difference(Full), Empty);702  EXPECT_EQ(Empty.difference(Empty), Empty);703  EXPECT_EQ(Empty.difference(Full), Empty);704 705  ConstantRange A(APInt(16, 3), APInt(16, 7));706  ConstantRange B(APInt(16, 5), APInt(16, 9));707  ConstantRange C(APInt(16, 3), APInt(16, 5));708  ConstantRange D(APInt(16, 7), APInt(16, 9));709  ConstantRange E(APInt(16, 5), APInt(16, 4));710  ConstantRange F(APInt(16, 7), APInt(16, 3));711  EXPECT_EQ(A.difference(B), C);712  EXPECT_EQ(B.difference(A), D);713  EXPECT_EQ(E.difference(A), F);714}715 716TEST_F(ConstantRangeTest, getActiveBits) {717  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {718    unsigned Exact = 0;719    ForeachNumInConstantRange(CR, [&](const APInt &N) {720      Exact = std::max(Exact, N.getActiveBits());721    });722 723    unsigned ResultCR = CR.getActiveBits();724    EXPECT_EQ(Exact, ResultCR);725  });726}727TEST_F(ConstantRangeTest, losslessUnsignedTruncationZeroext) {728  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {729    unsigned Bits = CR.getBitWidth();730    unsigned MinBitWidth = CR.getActiveBits();731    if (MinBitWidth == 0) {732      EXPECT_TRUE(CR.isEmptySet() ||733                  (CR.isSingleElement() && CR.getSingleElement()->isZero()));734      return;735    }736    if (MinBitWidth == Bits)737      return;738    EXPECT_EQ(CR, CR.truncate(MinBitWidth).zeroExtend(Bits));739  });740}741 742TEST_F(ConstantRangeTest, getMinSignedBits) {743  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {744    unsigned Exact = 0;745    ForeachNumInConstantRange(CR, [&](const APInt &N) {746      Exact = std::max(Exact, N.getSignificantBits());747    });748 749    unsigned ResultCR = CR.getMinSignedBits();750    EXPECT_EQ(Exact, ResultCR);751  });752}753TEST_F(ConstantRangeTest, losslessSignedTruncationSignext) {754  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {755    unsigned Bits = CR.getBitWidth();756    unsigned MinBitWidth = CR.getMinSignedBits();757    if (MinBitWidth == 0) {758      EXPECT_TRUE(CR.isEmptySet());759      return;760    }761    if (MinBitWidth == Bits)762      return;763    EXPECT_EQ(CR, CR.truncate(MinBitWidth).signExtend(Bits));764  });765}766 767TEST_F(ConstantRangeTest, SubtractAPInt) {768  EXPECT_EQ(Full.subtract(APInt(16, 4)), Full);769  EXPECT_EQ(Empty.subtract(APInt(16, 4)), Empty);770  EXPECT_EQ(Some.subtract(APInt(16, 4)),771            ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));772  EXPECT_EQ(Wrap.subtract(APInt(16, 4)),773            ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));774  EXPECT_EQ(One.subtract(APInt(16, 4)),775            ConstantRange(APInt(16, 0x6)));776}777 778TEST_F(ConstantRangeTest, Add) {779  EXPECT_EQ(Full.add(APInt(16, 4)), Full);780  EXPECT_EQ(Full.add(Full), Full);781  EXPECT_EQ(Full.add(Empty), Empty);782  EXPECT_EQ(Full.add(One), Full);783  EXPECT_EQ(Full.add(Some), Full);784  EXPECT_EQ(Full.add(Wrap), Full);785  EXPECT_EQ(Empty.add(Empty), Empty);786  EXPECT_EQ(Empty.add(One), Empty);787  EXPECT_EQ(Empty.add(Some), Empty);788  EXPECT_EQ(Empty.add(Wrap), Empty);789  EXPECT_EQ(Empty.add(APInt(16, 4)), Empty);790  EXPECT_EQ(Some.add(APInt(16, 4)),791            ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));792  EXPECT_EQ(Wrap.add(APInt(16, 4)),793            ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));794  EXPECT_EQ(One.add(APInt(16, 4)),795            ConstantRange(APInt(16, 0xe)));796 797  TestBinaryOpExhaustive(798      [](const ConstantRange &CR1, const ConstantRange &CR2) {799        return CR1.add(CR2);800      },801      [](const APInt &N1, const APInt &N2) {802        return N1 + N2;803      });804}805 806TEST_F(ConstantRangeTest, AddWithNoWrap) {807  typedef OverflowingBinaryOperator OBO;808  EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoSignedWrap), Empty);809  EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoSignedWrap), Empty);810  EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoSignedWrap), Full);811  EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoSignedWrap), Full);812  EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoSignedWrap), Full);813  EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),814                               OBO::NoSignedWrap),815            ConstantRange(APInt(16, INT16_MIN + 1, true),816                          APInt(16, INT16_MIN, true)));817  EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))818                .addWithNoWrap(Full, OBO::NoSignedWrap),819            ConstantRange(APInt(16, INT16_MIN + 1, true),820                          APInt(16, INT16_MIN, true)));821  EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, -1, true), APInt(16, 0)),822                               OBO::NoSignedWrap),823            ConstantRange(APInt(16, INT16_MIN, true), APInt(16, INT16_MAX)));824  EXPECT_EQ(ConstantRange(APInt(8, 100), APInt(8, 120))825                .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, 123)),826                               OBO::NoSignedWrap),827            ConstantRange(8, false));828  EXPECT_EQ(ConstantRange(APInt(8, -120, true), APInt(8, -100, true))829                .addWithNoWrap(830                    ConstantRange(APInt(8, -110, true), APInt(8, -100, true)),831                    OBO::NoSignedWrap),832            ConstantRange(8, false));833  EXPECT_EQ(834      ConstantRange(APInt(8, 0), APInt(8, 101))835          .addWithNoWrap(ConstantRange(APInt(8, -128, true), APInt(8, 28)),836                         OBO::NoSignedWrap),837      ConstantRange(8, true));838  EXPECT_EQ(839      ConstantRange(APInt(8, 0), APInt(8, 101))840          .addWithNoWrap(ConstantRange(APInt(8, -120, true), APInt(8, 29)),841                         OBO::NoSignedWrap),842      ConstantRange(APInt(8, -120, true), APInt(8, -128, true)));843  EXPECT_EQ(ConstantRange(APInt(8, -50, true), APInt(8, 50))844                .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 20)),845                               OBO::NoSignedWrap),846            ConstantRange(APInt(8, -40, true), APInt(8, 69)));847  EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))848                .addWithNoWrap(ConstantRange(APInt(8, -50, true), APInt(8, 50)),849                               OBO::NoSignedWrap),850            ConstantRange(APInt(8, -40, true), APInt(8, 69)));851  EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10, true))852                .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),853                               OBO::NoSignedWrap),854            ConstantRange(APInt(8, 125), APInt(8, 9)));855  EXPECT_EQ(856      ConstantRange(APInt(8, 5), APInt(8, 20))857          .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, -10, true)),858                         OBO::NoSignedWrap),859      ConstantRange(APInt(8, 125), APInt(8, 9)));860 861  TestBinaryOpExhaustive(862      [](const ConstantRange &CR1, const ConstantRange &CR2) {863        return CR1.addWithNoWrap(CR2, OBO::NoSignedWrap);864      },865      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {866        bool IsOverflow;867        APInt Res = N1.sadd_ov(N2, IsOverflow);868        if (IsOverflow)869          return std::nullopt;870        return Res;871      },872      PreferSmallest, CheckNonSignWrappedOnly);873 874  EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoUnsignedWrap), Empty);875  EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoUnsignedWrap), Empty);876  EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);877  EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoUnsignedWrap), Full);878  EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);879  EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),880                               OBO::NoUnsignedWrap),881            ConstantRange(APInt(16, 1), APInt(16, 0)));882  EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))883                .addWithNoWrap(Full, OBO::NoUnsignedWrap),884            ConstantRange(APInt(16, 1), APInt(16, 0)));885  EXPECT_EQ(ConstantRange(APInt(8, 200), APInt(8, 220))886                .addWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 123)),887                               OBO::NoUnsignedWrap),888            ConstantRange(8, false));889  EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))890                .addWithNoWrap(ConstantRange(APInt(8, 0), APInt(8, 156)),891                               OBO::NoUnsignedWrap),892            ConstantRange(8, true));893  EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))894                .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 29)),895                               OBO::NoUnsignedWrap),896            ConstantRange(APInt(8, 10), APInt(8, 129)));897  EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, 10))898                .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),899                               OBO::NoUnsignedWrap),900            ConstantRange(APInt(8, 50), APInt(8, 0)));901  EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))902                .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),903                               OBO::NoUnsignedWrap),904            ConstantRange(APInt(8, 60), APInt(8, -37, true)));905  EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, -30, true))906                .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),907                               OBO::NoUnsignedWrap),908            ConstantRange(APInt(8, 25), APInt(8, -11, true)));909  EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))910                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, -30, true)),911                               OBO::NoUnsignedWrap),912            ConstantRange(APInt(8, 25), APInt(8, -11, true)));913 914  TestBinaryOpExhaustive(915      [](const ConstantRange &CR1, const ConstantRange &CR2) {916        return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap);917      },918      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {919        bool IsOverflow;920        APInt Res = N1.uadd_ov(N2, IsOverflow);921        if (IsOverflow)922          return std::nullopt;923        return Res;924      },925      PreferSmallest, CheckNonWrappedOnly);926 927  EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))928                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),929                               OBO::NoSignedWrap),930            ConstantRange(APInt(8, 70), APInt(8, -128, true)));931  EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))932                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),933                               OBO::NoUnsignedWrap),934            ConstantRange(APInt(8, 70), APInt(8, 169)));935  EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))936                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),937                               OBO::NoUnsignedWrap | OBO::NoSignedWrap),938            ConstantRange(APInt(8, 70), APInt(8, -128, true)));939 940  EXPECT_EQ(ConstantRange(APInt(8, -100, true), APInt(8, -50, true))941                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),942                               OBO::NoSignedWrap),943            ConstantRange(APInt(8, -80, true), APInt(8, -21, true)));944  EXPECT_EQ(ConstantRange(APInt(8, -100, true), APInt(8, -50, true))945                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),946                               OBO::NoUnsignedWrap),947            ConstantRange(APInt(8, 176), APInt(8, 235)));948  EXPECT_EQ(ConstantRange(APInt(8, -100, true), APInt(8, -50, true))949                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),950                               OBO::NoUnsignedWrap | OBO::NoSignedWrap),951            ConstantRange(APInt(8, 176), APInt(8, 235)));952 953  TestBinaryOpExhaustive(954      [](const ConstantRange &CR1, const ConstantRange &CR2) {955        return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);956      },957      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {958        bool IsOverflow1, IsOverflow2;959        APInt Res1 = N1.uadd_ov(N2, IsOverflow1);960        APInt Res2 = N1.sadd_ov(N2, IsOverflow2);961        if (IsOverflow1 || IsOverflow2)962          return std::nullopt;963        assert(Res1 == Res2 && "Addition results differ?");964        return Res1;965      },966      PreferSmallest, CheckNonWrappedOrSignWrappedOnly);967}968 969TEST_F(ConstantRangeTest, Sub) {970  EXPECT_EQ(Full.sub(APInt(16, 4)), Full);971  EXPECT_EQ(Full.sub(Full), Full);972  EXPECT_EQ(Full.sub(Empty), Empty);973  EXPECT_EQ(Full.sub(One), Full);974  EXPECT_EQ(Full.sub(Some), Full);975  EXPECT_EQ(Full.sub(Wrap), Full);976  EXPECT_EQ(Empty.sub(Empty), Empty);977  EXPECT_EQ(Empty.sub(One), Empty);978  EXPECT_EQ(Empty.sub(Some), Empty);979  EXPECT_EQ(Empty.sub(Wrap), Empty);980  EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty);981  EXPECT_EQ(Some.sub(APInt(16, 4)),982            ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));983  EXPECT_EQ(Some.sub(Some),984            ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0)));985  EXPECT_EQ(Wrap.sub(APInt(16, 4)),986            ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));987  EXPECT_EQ(One.sub(APInt(16, 4)),988            ConstantRange(APInt(16, 0x6)));989 990  TestBinaryOpExhaustive(991      [](const ConstantRange &CR1, const ConstantRange &CR2) {992        return CR1.sub(CR2);993      },994      [](const APInt &N1, const APInt &N2) {995        return N1 - N2;996      });997}998 999TEST_F(ConstantRangeTest, SubWithNoWrap) {1000  typedef OverflowingBinaryOperator OBO;1001  TestBinaryOpExhaustive(1002      [](const ConstantRange &CR1, const ConstantRange &CR2) {1003        return CR1.subWithNoWrap(CR2, OBO::NoSignedWrap);1004      },1005      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1006        bool IsOverflow;1007        APInt Res = N1.ssub_ov(N2, IsOverflow);1008        if (IsOverflow)1009          return std::nullopt;1010        return Res;1011      },1012      PreferSmallest, CheckNonSignWrappedOnly);1013  TestBinaryOpExhaustive(1014      [](const ConstantRange &CR1, const ConstantRange &CR2) {1015        return CR1.subWithNoWrap(CR2, OBO::NoUnsignedWrap);1016      },1017      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1018        bool IsOverflow;1019        APInt Res = N1.usub_ov(N2, IsOverflow);1020        if (IsOverflow)1021          return std::nullopt;1022        return Res;1023      },1024      PreferSmallest, CheckNonWrappedOnly);1025  TestBinaryOpExhaustive(1026      [](const ConstantRange &CR1, const ConstantRange &CR2) {1027        return CR1.subWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);1028      },1029      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1030        bool IsOverflow1, IsOverflow2;1031        APInt Res1 = N1.usub_ov(N2, IsOverflow1);1032        APInt Res2 = N1.ssub_ov(N2, IsOverflow2);1033        if (IsOverflow1 || IsOverflow2)1034          return std::nullopt;1035        assert(Res1 == Res2 && "Subtraction results differ?");1036        return Res1;1037      },1038      PreferSmallest, CheckNonWrappedOrSignWrappedOnly);1039}1040 1041TEST_F(ConstantRangeTest, Multiply) {1042  EXPECT_EQ(Full.multiply(Full), Full);1043  EXPECT_EQ(Full.multiply(Empty), Empty);1044  EXPECT_EQ(Full.multiply(One), Full);1045  EXPECT_EQ(Full.multiply(Some), Full);1046  EXPECT_EQ(Full.multiply(Wrap), Full);1047  EXPECT_EQ(Empty.multiply(Empty), Empty);1048  EXPECT_EQ(Empty.multiply(One), Empty);1049  EXPECT_EQ(Empty.multiply(Some), Empty);1050  EXPECT_EQ(Empty.multiply(Wrap), Empty);1051  EXPECT_EQ(One.multiply(One), ConstantRange(APInt(16, 0xa*0xa),1052                                             APInt(16, 0xa*0xa + 1)));1053  EXPECT_EQ(One.multiply(Some), ConstantRange(APInt(16, 0xa*0xa),1054                                              APInt(16, 0xa*0xaa9 + 1)));1055  EXPECT_EQ(One.multiply(Wrap), Full);1056  EXPECT_EQ(Some.multiply(Some), Full);1057  EXPECT_EQ(Some.multiply(Wrap), Full);1058  EXPECT_EQ(Wrap.multiply(Wrap), Full);1059 1060  ConstantRange Zero(APInt(16, 0));1061  EXPECT_EQ(Zero.multiply(Full), Zero);1062  EXPECT_EQ(Zero.multiply(Some), Zero);1063  EXPECT_EQ(Zero.multiply(Wrap), Zero);1064  EXPECT_EQ(Full.multiply(Zero), Zero);1065  EXPECT_EQ(Some.multiply(Zero), Zero);1066  EXPECT_EQ(Wrap.multiply(Zero), Zero);1067 1068  // http://llvm.org/PR45451069  EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply(1070                ConstantRange(APInt(4, 6), APInt(4, 2))),1071            ConstantRange(4, /*isFullSet=*/true));1072 1073  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply(1074              ConstantRange(APInt(8, 252), APInt(8, 4))),1075            ConstantRange(APInt(8, 250), APInt(8, 9)));1076  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply(1077              ConstantRange(APInt(8, 2), APInt(8, 4))),1078            ConstantRange(APInt(8, 250), APInt(8, 253)));1079 1080  // TODO: This should be return [-2, 0]1081  EXPECT_EQ(ConstantRange(APInt(8, -2, true))1082                .multiply(ConstantRange(APInt(8, 0), APInt(8, 2))),1083            ConstantRange(APInt(8, -2, true), APInt(8, 1)));1084 1085  // Multiplication by -1 should give precise results.1086  EXPECT_EQ(ConstantRange(APInt(8, 3), APInt(8, -11, true))1087                .multiply(ConstantRange(APInt(8, -1, true))),1088            ConstantRange(APInt(8, 12), APInt(8, -2, true)));1089  EXPECT_EQ(ConstantRange(APInt(8, -1, true))1090                .multiply(ConstantRange(APInt(8, 3), APInt(8, -11, true))),1091            ConstantRange(APInt(8, 12), APInt(8, -2, true)));1092 1093  TestBinaryOpExhaustive(1094      [](const ConstantRange &CR1, const ConstantRange &CR2) {1095        return CR1.multiply(CR2);1096      },1097      [](const APInt &N1, const APInt &N2) {1098        return N1 * N2;1099      },1100      PreferSmallest,1101      [](const ConstantRange &, const ConstantRange &) {1102        return false; // Check correctness only.1103      });1104}1105 1106TEST_F(ConstantRangeTest, MultiplyWithNoWrap) {1107  using OBO = OverflowingBinaryOperator;1108 1109  EXPECT_EQ(Empty.multiplyWithNoWrap(Some, OBO::NoUnsignedWrap), Empty);1110  EXPECT_EQ(Some.multiplyWithNoWrap(Empty, OBO::NoUnsignedWrap), Empty);1111  EXPECT_EQ(Full.multiplyWithNoWrap(Full, OBO::NoUnsignedWrap), Full);1112  EXPECT_EQ(Full.multiplyWithNoWrap(Some, OBO::NoUnsignedWrap), Full);1113  EXPECT_EQ(Some.multiplyWithNoWrap(Full, OBO::NoUnsignedWrap), Full);1114  EXPECT_EQ(ConstantRange(APInt(4, 0), APInt(4, 2))1115                .multiplyWithNoWrap(ConstantRange(APInt(4, 2), APInt(4, 0)),1116                                    OBO::NoUnsignedWrap),1117            ConstantRange::getFull(4));1118  EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 5))1119                .multiplyWithNoWrap(ConstantRange(APInt(4, 1), APInt(4, 5)),1120                                    OBO::NoUnsignedWrap),1121            ConstantRange(APInt(4, 1), APInt(4, 0)));1122  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0))1123                .multiplyWithNoWrap(ConstantRange(APInt(8, 252), APInt(8, 4)),1124                                    OBO::NoUnsignedWrap),1125            ConstantRange(APInt(8, 250), APInt(8, 9)));1126  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255))1127                .multiplyWithNoWrap(ConstantRange(APInt(8, 2), APInt(8, 4)),1128                                    OBO::NoUnsignedWrap),1129            ConstantRange::getEmpty(8));1130 1131  EXPECT_EQ(Empty.multiplyWithNoWrap(Some, OBO::NoSignedWrap), Empty);1132  EXPECT_EQ(Some.multiplyWithNoWrap(Empty, OBO::NoSignedWrap), Empty);1133  EXPECT_EQ(Full.multiplyWithNoWrap(Full, OBO::NoSignedWrap), Full);1134  EXPECT_EQ(Full.multiplyWithNoWrap(Some, OBO::NoSignedWrap), Full);1135  EXPECT_EQ(Some.multiplyWithNoWrap(Full, OBO::NoSignedWrap), Full);1136  EXPECT_EQ(1137      ConstantRange(APInt(4, 0), APInt(4, 4))1138          .multiplyWithNoWrap(ConstantRange(APInt(4, -5, true), APInt(4, 4)),1139                              OBO::NoSignedWrap),1140      ConstantRange::getFull(4));1141  EXPECT_EQ(ConstantRange(APInt(4, 0), APInt(4, 3))1142                .multiplyWithNoWrap(ConstantRange(APInt(4, 0), APInt(4, 5)),1143                                    OBO::NoSignedWrap),1144            ConstantRange(APInt(4, 0), APInt(4, -8, true)));1145  EXPECT_EQ(ConstantRange(APInt(8, 3), APInt(8, -11, true))1146                .multiplyWithNoWrap(ConstantRange(APInt(8, -1, true)),1147                                    OBO::NoSignedWrap),1148            ConstantRange(APInt(8, 12), APInt(8, -2, true)));1149  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255))1150                .multiplyWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 121)),1151                                    OBO::NoSignedWrap),1152            ConstantRange::getEmpty(8));1153  EXPECT_TRUE(ConstantRange::getFull(8)1154                  .multiplyWithNoWrap(ConstantRange(APInt(8, 2), APInt(8, 128)),1155                                      OBO::NoUnsignedWrap | OBO::NoSignedWrap)1156                  .isAllNonNegative());1157  EXPECT_TRUE(ConstantRange(APInt(8, 2), APInt(8, 128))1158                  .multiplyWithNoWrap(ConstantRange::getFull(8),1159                                      OBO::NoUnsignedWrap | OBO::NoSignedWrap)1160                  .isAllNonNegative());1161  EXPECT_FALSE(1162      ConstantRange::getFull(8)1163          .multiplyWithNoWrap(ConstantRange(APInt(8, 1), APInt(8, 128)),1164                              OBO::NoUnsignedWrap | OBO::NoSignedWrap)1165          .isAllNonNegative());1166  EXPECT_FALSE(1167      ConstantRange::getFull(8)1168          .multiplyWithNoWrap(ConstantRange(APInt(8, 2), APInt(8, 128)),1169                              OBO::NoSignedWrap)1170          .isAllNonNegative());1171 1172  TestBinaryOpExhaustive(1173      [](const ConstantRange &CR1, const ConstantRange &CR2) {1174        return CR1.multiplyWithNoWrap(CR2, OBO::NoUnsignedWrap);1175      },1176      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1177        bool IsOverflow;1178        APInt Res = N1.umul_ov(N2, IsOverflow);1179        if (IsOverflow)1180          return std::nullopt;1181        return Res;1182      },1183      PreferSmallest, CheckCorrectnessOnly);1184  TestBinaryOpExhaustive(1185      [](const ConstantRange &CR1, const ConstantRange &CR2) {1186        return CR1.multiplyWithNoWrap(CR2, OBO::NoSignedWrap);1187      },1188      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1189        bool IsOverflow;1190        APInt Res = N1.smul_ov(N2, IsOverflow);1191        if (IsOverflow)1192          return std::nullopt;1193        return Res;1194      },1195      PreferSmallest, CheckCorrectnessOnly);1196  TestBinaryOpExhaustive(1197      [](const ConstantRange &CR1, const ConstantRange &CR2) {1198        return CR1.multiplyWithNoWrap(CR2,1199                                      OBO::NoUnsignedWrap | OBO::NoSignedWrap);1200      },1201      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1202        bool IsOverflow1, IsOverflow2;1203        APInt Res1 = N1.umul_ov(N2, IsOverflow1);1204        APInt Res2 = N1.smul_ov(N2, IsOverflow2);1205        if (IsOverflow1 || IsOverflow2)1206          return std::nullopt;1207        assert(Res1 == Res2 && "Multiplication results differ?");1208        return Res1;1209      },1210      PreferSmallest, CheckCorrectnessOnly);1211}1212 1213TEST_F(ConstantRangeTest, smul_fast) {1214  TestBinaryOpExhaustive(1215      [](const ConstantRange &CR1, const ConstantRange &CR2) {1216        return CR1.smul_fast(CR2);1217      },1218      [](const APInt &N1, const APInt &N2) { return N1 * N2; }, PreferSmallest,1219      CheckCorrectnessOnly);1220}1221 1222TEST_F(ConstantRangeTest, UMax) {1223  EXPECT_EQ(Full.umax(Full), Full);1224  EXPECT_EQ(Full.umax(Empty), Empty);1225  EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));1226  EXPECT_EQ(Full.umax(Wrap), Full);1227  EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));1228  EXPECT_EQ(Empty.umax(Empty), Empty);1229  EXPECT_EQ(Empty.umax(Some), Empty);1230  EXPECT_EQ(Empty.umax(Wrap), Empty);1231  EXPECT_EQ(Empty.umax(One), Empty);1232  EXPECT_EQ(Some.umax(Some), Some);1233  EXPECT_EQ(Some.umax(Wrap), ConstantRange(APInt(16, 0xa), APInt(16, 0)));1234  EXPECT_EQ(Some.umax(One), Some);1235  EXPECT_EQ(Wrap.umax(Wrap), Wrap);1236  EXPECT_EQ(Wrap.umax(One), ConstantRange(APInt(16, 0xa), APInt(16, 0)));1237  EXPECT_EQ(One.umax(One), One);1238 1239  TestBinaryOpExhaustive(1240      [](const ConstantRange &CR1, const ConstantRange &CR2) {1241        return CR1.umax(CR2);1242      },1243      [](const APInt &N1, const APInt &N2) {1244        return APIntOps::umax(N1, N2);1245      },1246      PreferSmallestNonFullUnsigned);1247}1248 1249TEST_F(ConstantRangeTest, SMax) {1250  EXPECT_EQ(Full.smax(Full), Full);1251  EXPECT_EQ(Full.smax(Empty), Empty);1252  EXPECT_EQ(Full.smax(Some), ConstantRange(APInt(16, 0xa),1253                                           APInt::getSignedMinValue(16)));1254  EXPECT_EQ(Full.smax(Wrap), Full);1255  EXPECT_EQ(Full.smax(One), ConstantRange(APInt(16, 0xa),1256                                          APInt::getSignedMinValue(16)));1257  EXPECT_EQ(Empty.smax(Empty), Empty);1258  EXPECT_EQ(Empty.smax(Some), Empty);1259  EXPECT_EQ(Empty.smax(Wrap), Empty);1260  EXPECT_EQ(Empty.smax(One), Empty);1261  EXPECT_EQ(Some.smax(Some), Some);1262  EXPECT_EQ(Some.smax(Wrap),1263            ConstantRange(APInt(16, 0xa), APInt(16, (uint16_t)INT16_MIN)));1264  EXPECT_EQ(Some.smax(One), Some);1265  EXPECT_EQ(Wrap.smax(One),1266            ConstantRange(APInt(16, 0xa), APInt(16, (uint16_t)INT16_MIN)));1267  EXPECT_EQ(One.smax(One), One);1268 1269  TestBinaryOpExhaustive(1270      [](const ConstantRange &CR1, const ConstantRange &CR2) {1271        return CR1.smax(CR2);1272      },1273      [](const APInt &N1, const APInt &N2) {1274        return APIntOps::smax(N1, N2);1275      },1276      PreferSmallestNonFullSigned);1277}1278 1279TEST_F(ConstantRangeTest, UMin) {1280  EXPECT_EQ(Full.umin(Full), Full);1281  EXPECT_EQ(Full.umin(Empty), Empty);1282  EXPECT_EQ(Full.umin(Some), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));1283  EXPECT_EQ(Full.umin(Wrap), Full);1284  EXPECT_EQ(Empty.umin(Empty), Empty);1285  EXPECT_EQ(Empty.umin(Some), Empty);1286  EXPECT_EQ(Empty.umin(Wrap), Empty);1287  EXPECT_EQ(Empty.umin(One), Empty);1288  EXPECT_EQ(Some.umin(Some), Some);1289  EXPECT_EQ(Some.umin(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));1290  EXPECT_EQ(Some.umin(One), One);1291  EXPECT_EQ(Wrap.umin(Wrap), Wrap);1292  EXPECT_EQ(Wrap.umin(One), ConstantRange(APInt(16, 0), APInt(16, 0xb)));1293  EXPECT_EQ(One.umin(One), One);1294 1295  TestBinaryOpExhaustive(1296      [](const ConstantRange &CR1, const ConstantRange &CR2) {1297        return CR1.umin(CR2);1298      },1299      [](const APInt &N1, const APInt &N2) {1300        return APIntOps::umin(N1, N2);1301      },1302      PreferSmallestNonFullUnsigned);1303}1304 1305TEST_F(ConstantRangeTest, SMin) {1306  EXPECT_EQ(Full.smin(Full), Full);1307  EXPECT_EQ(Full.smin(Empty), Empty);1308  EXPECT_EQ(Full.smin(Some),1309            ConstantRange(APInt(16, (uint16_t)INT16_MIN), APInt(16, 0xaaa)));1310  EXPECT_EQ(Full.smin(Wrap), Full);1311  EXPECT_EQ(Empty.smin(Empty), Empty);1312  EXPECT_EQ(Empty.smin(Some), Empty);1313  EXPECT_EQ(Empty.smin(Wrap), Empty);1314  EXPECT_EQ(Empty.smin(One), Empty);1315  EXPECT_EQ(Some.smin(Some), Some);1316  EXPECT_EQ(Some.smin(Wrap),1317            ConstantRange(APInt(16, (uint16_t)INT16_MIN), APInt(16, 0xaaa)));1318  EXPECT_EQ(Some.smin(One), One);1319  EXPECT_EQ(Wrap.smin(Wrap), Wrap);1320  EXPECT_EQ(Wrap.smin(One),1321            ConstantRange(APInt(16, (uint16_t)INT16_MIN), APInt(16, 0xb)));1322  EXPECT_EQ(One.smin(One), One);1323 1324  TestBinaryOpExhaustive(1325      [](const ConstantRange &CR1, const ConstantRange &CR2) {1326        return CR1.smin(CR2);1327      },1328      [](const APInt &N1, const APInt &N2) {1329        return APIntOps::smin(N1, N2);1330      },1331      PreferSmallestNonFullSigned);1332}1333 1334TEST_F(ConstantRangeTest, UDiv) {1335  EXPECT_EQ(Full.udiv(Full), Full);1336  EXPECT_EQ(Full.udiv(Empty), Empty);1337  EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0),1338                                          APInt(16, 0xffff / 0xa + 1)));1339  EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0),1340                                           APInt(16, 0xffff / 0xa + 1)));1341  EXPECT_EQ(Full.udiv(Wrap), Full);1342  EXPECT_EQ(Empty.udiv(Empty), Empty);1343  EXPECT_EQ(Empty.udiv(One), Empty);1344  EXPECT_EQ(Empty.udiv(Some), Empty);1345  EXPECT_EQ(Empty.udiv(Wrap), Empty);1346  EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));1347  EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));1348  EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));1349  EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));1350  EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));1351  EXPECT_EQ(Wrap.udiv(Wrap), Full);1352 1353 1354  ConstantRange Zero(APInt(16, 0));1355  EXPECT_EQ(Zero.udiv(One), Zero);1356  EXPECT_EQ(Zero.udiv(Full), Zero);1357 1358  EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full),1359            ConstantRange(APInt(16, 0), APInt(16, 99)));1360  EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full),1361            ConstantRange(APInt(16, 0), APInt(16, 99)));1362}1363 1364TEST_F(ConstantRangeTest, SDiv) {1365  ConstantRange OneBit = ConstantRange::getFull(1);1366  EXPECT_EQ(OneBit.sdiv(OneBit), ConstantRange(APInt(1, 0)));1367 1368  EnumerateTwoInterestingConstantRanges([&](const ConstantRange &CR1,1369                                            const ConstantRange &CR2) {1370    // Collect possible results in a bit vector. We store the signed value plus1371    // a bias to make it unsigned.1372    unsigned Bits = CR1.getBitWidth();1373    int Bias = 1 << (Bits - 1);1374    BitVector Results(1 << Bits);1375    ForeachNumInConstantRange(CR1, [&](const APInt &N1) {1376      ForeachNumInConstantRange(CR2, [&](const APInt &N2) {1377        // Division by zero is UB.1378        if (N2 == 0)1379          return;1380 1381        // SignedMin / -1 is UB.1382        if (N1.isMinSignedValue() && N2.isAllOnes())1383          return;1384 1385        APInt N = N1.sdiv(N2);1386        Results.set(N.getSExtValue() + Bias);1387      });1388    });1389 1390    ConstantRange CR = CR1.sdiv(CR2);1391    if (Results.none()) {1392      EXPECT_TRUE(CR.isEmptySet());1393      return;1394    }1395 1396    // If there is a non-full signed envelope, that should be the result.1397    APInt SMin(Bits, Results.find_first() - Bias, true);1398    APInt SMax(Bits, Results.find_last() - Bias, true);1399    ConstantRange Envelope = ConstantRange::getNonEmpty(SMin, SMax + 1);1400    if (!Envelope.isFullSet()) {1401      EXPECT_EQ(Envelope, CR);1402      return;1403    }1404 1405    // If the signed envelope is a full set, try to find a smaller sign wrapped1406    // set that is separated in negative and positive components (or one which1407    // can also additionally contain zero).1408    int LastNeg = Results.find_last_in(0, Bias) - Bias;1409    int LastPos = Results.find_next(Bias) - Bias;1410    if (Results[Bias]) {1411      if (LastNeg == -1)1412        ++LastNeg;1413      else if (LastPos == 1)1414        --LastPos;1415    }1416 1417    APInt WMax(Bits, LastNeg, true);1418    APInt WMin(Bits, LastPos, true);1419    ConstantRange Wrapped = ConstantRange::getNonEmpty(WMin, WMax + 1);1420    EXPECT_EQ(Wrapped, CR);1421  });1422}1423 1424TEST_F(ConstantRangeTest, URem) {1425  EXPECT_EQ(Full.urem(Empty), Empty);1426  EXPECT_EQ(Empty.urem(Full), Empty);1427  // urem by zero is poison.1428  EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty);1429  // urem by full range doesn't contain MaxValue.1430  EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff)));1431  // urem is upper bounded by maximum RHS minus one.1432  EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))),1433            ConstantRange(APInt(16, 0), APInt(16, 122)));1434  // urem is upper bounded by maximum LHS.1435  EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full),1436            ConstantRange(APInt(16, 0), APInt(16, 123)));1437  // If the LHS is always lower than the RHS, the result is the LHS.1438  EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))1439                .urem(ConstantRange(APInt(16, 20), APInt(16, 30))),1440            ConstantRange(APInt(16, 10), APInt(16, 20)));1441  // It has to be strictly lower, otherwise the top value may wrap to zero.1442  EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))1443                .urem(ConstantRange(APInt(16, 19), APInt(16, 30))),1444            ConstantRange(APInt(16, 0), APInt(16, 20)));1445  // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].1446  EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))1447                .urem(ConstantRange(APInt(16, 10))),1448            ConstantRange(APInt(16, 0), APInt(16, 10)));1449 1450  TestBinaryOpExhaustive(1451      [](const ConstantRange &CR1, const ConstantRange &CR2) {1452        return CR1.urem(CR2);1453      },1454      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1455        if (N2.isZero())1456          return std::nullopt;1457        return N1.urem(N2);1458      },1459      PreferSmallest, CheckSingleElementsOnly);1460}1461 1462TEST_F(ConstantRangeTest, SRem) {1463  EXPECT_EQ(Full.srem(Empty), Empty);1464  EXPECT_EQ(Empty.srem(Full), Empty);1465  // srem by zero is UB.1466  EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);1467  // srem by full range doesn't contain SignedMinValue.1468  EXPECT_EQ(Full.srem(Full), ConstantRange(APInt::getSignedMinValue(16) + 1,1469                                           APInt::getSignedMinValue(16)));1470 1471  ConstantRange PosMod(APInt(16, 10), APInt(16, 21));              // [10, 20]1472  ConstantRange NegMod(APInt(16, -20, true), APInt(16, -9, true)); // [-20, -10]1473  ConstantRange IntMinMod(APInt::getSignedMinValue(16));1474 1475  ConstantRange Expected(16, true);1476 1477  // srem is bounded by abs(RHS) minus one.1478  ConstantRange PosLargeLHS(APInt(16, 0), APInt(16, 41));1479  Expected = ConstantRange(APInt(16, 0), APInt(16, 20));1480  EXPECT_EQ(PosLargeLHS.srem(PosMod), Expected);1481  EXPECT_EQ(PosLargeLHS.srem(NegMod), Expected);1482  ConstantRange NegLargeLHS(APInt(16, -40, true), APInt(16, 1));1483  Expected = ConstantRange(APInt(16, -19, true), APInt(16, 1));1484  EXPECT_EQ(NegLargeLHS.srem(PosMod), Expected);1485  EXPECT_EQ(NegLargeLHS.srem(NegMod), Expected);1486  ConstantRange PosNegLargeLHS(APInt(16, -32, true), APInt(16, 38));1487  Expected = ConstantRange(APInt(16, -19, true), APInt(16, 20));1488  EXPECT_EQ(PosNegLargeLHS.srem(PosMod), Expected);1489  EXPECT_EQ(PosNegLargeLHS.srem(NegMod), Expected);1490 1491  // srem is bounded by LHS.1492  ConstantRange PosLHS(APInt(16, 0), APInt(16, 16));1493  EXPECT_EQ(PosLHS.srem(PosMod), PosLHS);1494  EXPECT_EQ(PosLHS.srem(NegMod), PosLHS);1495  EXPECT_EQ(PosLHS.srem(IntMinMod), PosLHS);1496  ConstantRange NegLHS(APInt(16, -15, true), APInt(16, 1));1497  EXPECT_EQ(NegLHS.srem(PosMod), NegLHS);1498  EXPECT_EQ(NegLHS.srem(NegMod), NegLHS);1499  EXPECT_EQ(NegLHS.srem(IntMinMod), NegLHS);1500  ConstantRange PosNegLHS(APInt(16, -12, true), APInt(16, 18));1501  EXPECT_EQ(PosNegLHS.srem(PosMod), PosNegLHS);1502  EXPECT_EQ(PosNegLHS.srem(NegMod), PosNegLHS);1503  EXPECT_EQ(PosNegLHS.srem(IntMinMod), PosNegLHS);1504 1505  // srem is LHS if it is smaller than RHS.1506  ConstantRange PosSmallLHS(APInt(16, 3), APInt(16, 8));1507  EXPECT_EQ(PosSmallLHS.srem(PosMod), PosSmallLHS);1508  EXPECT_EQ(PosSmallLHS.srem(NegMod), PosSmallLHS);1509  EXPECT_EQ(PosSmallLHS.srem(IntMinMod), PosSmallLHS);1510  ConstantRange NegSmallLHS(APInt(16, -7, true), APInt(16, -2, true));1511  EXPECT_EQ(NegSmallLHS.srem(PosMod), NegSmallLHS);1512  EXPECT_EQ(NegSmallLHS.srem(NegMod), NegSmallLHS);1513  EXPECT_EQ(NegSmallLHS.srem(IntMinMod), NegSmallLHS);1514  ConstantRange PosNegSmallLHS(APInt(16, -3, true), APInt(16, 8));1515  EXPECT_EQ(PosNegSmallLHS.srem(PosMod), PosNegSmallLHS);1516  EXPECT_EQ(PosNegSmallLHS.srem(NegMod), PosNegSmallLHS);1517  EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);1518 1519  // Example of a suboptimal result:1520  // [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].1521  EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))1522                .srem(ConstantRange(APInt(16, 10))),1523            ConstantRange(APInt(16, 0), APInt(16, 10)));1524 1525  TestBinaryOpExhaustive(1526      [](const ConstantRange &CR1, const ConstantRange &CR2) {1527        return CR1.srem(CR2);1528      },1529      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1530        if (N2.isZero())1531          return std::nullopt;1532        return N1.srem(N2);1533      },1534      PreferSmallest, CheckSingleElementsOnly);1535}1536 1537TEST_F(ConstantRangeTest, Shl) {1538  ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));1539  ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));1540  EXPECT_EQ(Full.shl(Full), Full);1541  EXPECT_EQ(Full.shl(Empty), Empty);1542  EXPECT_EQ(Full.shl(One), ConstantRange(APInt(16, 0),1543                                         APInt(16, 0xfc00) + 1));1544  EXPECT_EQ(Full.shl(Some), Full);   // TODO: [0, (-1 << 0xa) + 1)1545  EXPECT_EQ(Full.shl(Wrap), Full);1546  EXPECT_EQ(Empty.shl(Empty), Empty);1547  EXPECT_EQ(Empty.shl(One), Empty);1548  EXPECT_EQ(Empty.shl(Some), Empty);1549  EXPECT_EQ(Empty.shl(Wrap), Empty);1550  EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),1551                                        APInt(16, (0xa << 0xa) + 1)));1552  EXPECT_EQ(One.shl(Some), Full);    // TODO: [0xa << 0xa, 0)1553  EXPECT_EQ(One.shl(Wrap), Full);    // TODO: [0xa, 0xa << 14 + 1)1554  EXPECT_EQ(Some.shl(Some), Full);   // TODO: [0xa << 0xa, 0xfc01)1555  EXPECT_EQ(Some.shl(Wrap), Full);   // TODO: [0xa, 0x7ff << 0x5 + 1)1556  EXPECT_EQ(Wrap.shl(Wrap), Full);1557  EXPECT_EQ(1558      Some2.shl(ConstantRange(APInt(16, 0x1))),1559      ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1));1560  EXPECT_EQ(One.shl(WrapNullMax), Full);1561 1562  ConstantRange NegOne(APInt(16, 0xffff));1563  EXPECT_EQ(NegOne.shl(ConstantRange(APInt(16, 0), APInt(16, 5))),1564            ConstantRange(APInt(16, 0xfff0), APInt(16, 0)));1565  EXPECT_EQ(ConstantRange(APInt(16, 0xfffe), APInt(16, 0))1566                .shl(ConstantRange(APInt(16, 0), APInt(16, 5))),1567            ConstantRange(APInt(16, 0xffe0), APInt(16, 0)));1568 1569  TestBinaryOpExhaustive(1570      [](const ConstantRange &CR1, const ConstantRange &CR2) {1571        return CR1.shl(CR2);1572      },1573      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1574        if (N2.uge(N2.getBitWidth()))1575          return std::nullopt;1576        return N1.shl(N2);1577      },1578      PreferSmallestUnsigned,1579      [](const ConstantRange &, const ConstantRange &CR2) {1580        // We currently only produce precise results for single element RHS.1581        return CR2.isSingleElement();1582      });1583}1584 1585TEST_F(ConstantRangeTest, ShlWithNoWrap) {1586  using OBO = OverflowingBinaryOperator;1587  TestBinaryOpExhaustive(1588      [](const ConstantRange &CR1, const ConstantRange &CR2) {1589        ConstantRange Res = CR1.shlWithNoWrap(CR2, OBO::NoUnsignedWrap);1590        EXPECT_TRUE(CR1.shl(CR2).contains(Res));1591        return Res;1592      },1593      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1594        bool IsOverflow;1595        APInt Res = N1.ushl_ov(N2, IsOverflow);1596        if (IsOverflow)1597          return std::nullopt;1598        return Res;1599      },1600      PreferSmallest, CheckNonWrappedOnly);1601  TestBinaryOpExhaustive(1602      [](const ConstantRange &CR1, const ConstantRange &CR2) {1603        return CR1.shlWithNoWrap(CR2, OBO::NoSignedWrap);1604      },1605      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1606        bool IsOverflow;1607        APInt Res = N1.sshl_ov(N2, IsOverflow);1608        if (IsOverflow)1609          return std::nullopt;1610        return Res;1611      },1612      PreferSmallestSigned, CheckNoSignedWrappedLHSAndNoWrappedRHSOnly);1613  TestBinaryOpExhaustive(1614      [](const ConstantRange &CR1, const ConstantRange &CR2) {1615        return CR1.shlWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);1616      },1617      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {1618        bool IsOverflow1, IsOverflow2;1619        APInt Res1 = N1.ushl_ov(N2, IsOverflow1);1620        APInt Res2 = N1.sshl_ov(N2, IsOverflow2);1621        if (IsOverflow1 || IsOverflow2)1622          return std::nullopt;1623        assert(Res1 == Res2 && "Left shift results differ?");1624        return Res1;1625      },1626      PreferSmallest, CheckCorrectnessOnly);1627 1628  EXPECT_EQ(One.shlWithNoWrap(Full, OBO::NoSignedWrap),1629            ConstantRange(APInt(16, 10), APInt(16, 20481)));1630  EXPECT_EQ(One.shlWithNoWrap(Full, OBO::NoUnsignedWrap),1631            ConstantRange(APInt(16, 10), APInt(16, -24575, true)));1632  EXPECT_EQ(One.shlWithNoWrap(Full, OBO::NoSignedWrap | OBO::NoUnsignedWrap),1633            ConstantRange(APInt(16, 10), APInt(16, 20481)));1634  ConstantRange NegOne(APInt(16, 0xffff));1635  EXPECT_EQ(NegOne.shlWithNoWrap(Full, OBO::NoSignedWrap),1636            ConstantRange(APInt(16, -32768, true), APInt(16, 0)));1637  EXPECT_EQ(NegOne.shlWithNoWrap(Full, OBO::NoUnsignedWrap), NegOne);1638  EXPECT_EQ(ConstantRange(APInt(16, 768))1639                .shlWithNoWrap(Full, OBO::NoSignedWrap | OBO::NoUnsignedWrap),1640            ConstantRange(APInt(16, 768), APInt(16, 24577)));1641  EXPECT_EQ(Full.shlWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 16)),1642                               OBO::NoUnsignedWrap),1643            ConstantRange(APInt(16, 0), APInt(16, -1, true)));1644  EXPECT_EQ(ConstantRange(APInt(4, 3), APInt(4, -8, true))1645                .shlWithNoWrap(ConstantRange(APInt(4, 0), APInt(4, 4)),1646                               OBO::NoSignedWrap),1647            ConstantRange(APInt(4, 3), APInt(4, -8, true)));1648  EXPECT_EQ(ConstantRange(APInt(4, -1, true), APInt(4, 0))1649                .shlWithNoWrap(ConstantRange(APInt(4, 1), APInt(4, 4)),1650                               OBO::NoSignedWrap),1651            ConstantRange(APInt(4, -8, true), APInt(4, -1, true)));1652}1653 1654TEST_F(ConstantRangeTest, Lshr) {1655  EXPECT_EQ(Full.lshr(Full), Full);1656  EXPECT_EQ(Full.lshr(Empty), Empty);1657  EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),1658                                          APInt(16, (0xffff >> 0xa) + 1)));1659  EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),1660                                           APInt(16, (0xffff >> 0xa) + 1)));1661  EXPECT_EQ(Full.lshr(Wrap), Full);1662  EXPECT_EQ(Empty.lshr(Empty), Empty);1663  EXPECT_EQ(Empty.lshr(One), Empty);1664  EXPECT_EQ(Empty.lshr(Some), Empty);1665  EXPECT_EQ(Empty.lshr(Wrap), Empty);1666  EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0)));1667  EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));1668  EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));1669  EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),1670                                           APInt(16, (0xaaa >> 0xa) + 1)));1671  EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));1672  EXPECT_EQ(Wrap.lshr(Wrap), Full);1673}1674 1675TEST_F(ConstantRangeTest, Ashr) {1676  EXPECT_EQ(Full.ashr(Full), Full);1677  EXPECT_EQ(Full.ashr(Empty), Empty);1678  EXPECT_EQ(Full.ashr(One), ConstantRange(APInt(16, 0xffe0),1679                                          APInt(16, (0x7fff >> 0xa) + 1 )));1680  ConstantRange Small(APInt(16, 0xa), APInt(16, 0xb));1681  EXPECT_EQ(Full.ashr(Small), ConstantRange(APInt(16, 0xffe0),1682                                           APInt(16, (0x7fff >> 0xa) + 1 )));1683  EXPECT_EQ(Full.ashr(Some), ConstantRange(APInt(16, 0xffe0),1684                                           APInt(16, (0x7fff >> 0xa) + 1 )));1685  EXPECT_EQ(Full.ashr(Wrap), Full);1686  EXPECT_EQ(Empty.ashr(Empty), Empty);1687  EXPECT_EQ(Empty.ashr(One), Empty);1688  EXPECT_EQ(Empty.ashr(Some), Empty);1689  EXPECT_EQ(Empty.ashr(Wrap), Empty);1690  EXPECT_EQ(One.ashr(One), ConstantRange(APInt(16, 0)));1691  EXPECT_EQ(One.ashr(Some), ConstantRange(APInt(16, 0)));1692  EXPECT_EQ(One.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));1693  EXPECT_EQ(Some.ashr(Some), ConstantRange(APInt(16, 0),1694                                           APInt(16, (0xaaa >> 0xa) + 1)));1695  EXPECT_EQ(Some.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));1696  EXPECT_EQ(Wrap.ashr(Wrap), Full);1697  ConstantRange Neg(APInt(16, 0xf3f0), APInt(16, 0xf7f8));1698  EXPECT_EQ(Neg.ashr(Small),1699            ConstantRange(APInt(16, 0xfffc), APInt(16, 0xfffe)));1700}1701 1702TEST(ConstantRange, MakeAllowedICmpRegionEdgeCases) {1703  ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(8));1704  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax)1705                  .isEmptySet());1706  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGE, SMax)1707                  .isSingleElement());1708  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SLE, SMax)1709                  .isFullSet());1710  ConstantRange SMin = ConstantRange(APInt::getSignedMinValue(8));1711  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SLT, SMin)1712                  .isEmptySet());1713  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SLE, SMin)1714                  .isSingleElement());1715  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGE, SMin)1716                  .isFullSet());1717  ConstantRange UMax = ConstantRange(APInt::getMaxValue(8));1718  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_UGT, UMax)1719                  .isEmptySet());1720  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_UGE, UMax)1721                  .isSingleElement());1722  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_ULE, UMax)1723                  .isFullSet());1724  ConstantRange UMin = ConstantRange(APInt::getMinValue(8));1725  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_ULT, UMin)1726                  .isEmptySet());1727  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_ULE, UMin)1728                  .isSingleElement());1729  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_UGE, UMin)1730                  .isFullSet());1731}1732 1733TEST(ConstantRange, MakeExactICmpRegion) {1734  for (unsigned Bits : {1, 4}) {1735    EnumerateAPInts(Bits, [](const APInt &N) {1736      for (auto Pred : ICmpInst::predicates()) {1737        EXPECT_EQ(ConstantRange::makeAllowedICmpRegion(Pred, N),1738                  ConstantRange::makeSatisfyingICmpRegion(Pred, N));1739      };1740    });1741  }1742}1743 1744TEST(ConstantRange, MakeSatisfyingICmpRegion) {1745  ConstantRange LowHalf(APInt(8, 0), APInt(8, 128));1746  ConstantRange HighHalf(APInt(8, 128), APInt(8, 0));1747  ConstantRange EmptySet(8, /* isFullSet = */ false);1748 1749  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf),1750            HighHalf);1751 1752  EXPECT_EQ(1753      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf),1754      LowHalf);1755 1756  EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ,1757                                                      HighHalf).isEmptySet());1758 1759  ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200));1760 1761  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT,1762                                                    UnsignedSample),1763            ConstantRange(APInt(8, 0), APInt(8, 5)));1764 1765  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE,1766                                                    UnsignedSample),1767            ConstantRange(APInt(8, 0), APInt(8, 6)));1768 1769  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT,1770                                                    UnsignedSample),1771            ConstantRange(APInt(8, 200), APInt(8, 0)));1772 1773  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE,1774                                                    UnsignedSample),1775            ConstantRange(APInt(8, 199), APInt(8, 0)));1776 1777  ConstantRange SignedSample(APInt(8, -5, true), APInt(8, 5));1778 1779  EXPECT_EQ(1780      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample),1781      ConstantRange(APInt(8, -128, true), APInt(8, -5, true)));1782 1783  EXPECT_EQ(1784      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample),1785      ConstantRange(APInt(8, -128, true), APInt(8, -4, true)));1786 1787  EXPECT_EQ(1788      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample),1789      ConstantRange(APInt(8, 5), APInt(8, -128, true)));1790 1791  EXPECT_EQ(1792      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample),1793      ConstantRange(APInt(8, 4), APInt(8, -128, true)));1794}1795 1796void ICmpTestImpl(CmpInst::Predicate Pred) {1797  EnumerateTwoInterestingConstantRanges(1798      [&](const ConstantRange &CR1, const ConstantRange &CR2) {1799        bool Exhaustive = true;1800        ForeachNumInConstantRange(CR1, [&](const APInt &N1) {1801          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {1802            Exhaustive &= ICmpInst::compare(N1, N2, Pred);1803          });1804        });1805        EXPECT_EQ(CR1.icmp(Pred, CR2), Exhaustive);1806      });1807}1808 1809TEST(ConstantRange, ICmp) {1810  for (auto Pred : ICmpInst::predicates())1811    ICmpTestImpl(Pred);1812}1813 1814TEST(ConstantRange, MakeGuaranteedNoWrapRegion) {1815  const int IntMin4Bits = -8;1816  const int IntMax4Bits = 7;1817  typedef OverflowingBinaryOperator OBO;1818 1819  for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {1820    APInt C(4, Const, true /* = isSigned */);1821 1822    auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(1823        Instruction::Add, C, OBO::NoUnsignedWrap);1824 1825    EXPECT_FALSE(NUWRegion.isEmptySet());1826 1827    auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(1828        Instruction::Add, C, OBO::NoSignedWrap);1829 1830    EXPECT_FALSE(NSWRegion.isEmptySet());1831 1832    for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;1833         ++I) {1834      bool Overflow = false;1835      (void)I.uadd_ov(C, Overflow);1836      EXPECT_FALSE(Overflow);1837    }1838 1839    for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;1840         ++I) {1841      bool Overflow = false;1842      (void)I.sadd_ov(C, Overflow);1843      EXPECT_FALSE(Overflow);1844    }1845  }1846 1847  for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {1848    APInt C(4, Const, true /* = isSigned */);1849 1850    auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(1851        Instruction::Sub, C, OBO::NoUnsignedWrap);1852 1853    EXPECT_FALSE(NUWRegion.isEmptySet());1854 1855    auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(1856        Instruction::Sub, C, OBO::NoSignedWrap);1857 1858    EXPECT_FALSE(NSWRegion.isEmptySet());1859 1860    for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;1861         ++I) {1862      bool Overflow = false;1863      (void)I.usub_ov(C, Overflow);1864      EXPECT_FALSE(Overflow);1865    }1866 1867    for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;1868         ++I) {1869      bool Overflow = false;1870      (void)I.ssub_ov(C, Overflow);1871      EXPECT_FALSE(Overflow);1872    }1873  }1874 1875  auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(1876      Instruction::Add, ConstantRange(32, /* isFullSet = */ true),1877      OBO::NoSignedWrap);1878  EXPECT_TRUE(NSWForAllValues.isSingleElement() &&1879              NSWForAllValues.getSingleElement()->isMinValue());1880 1881  NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(1882      Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),1883      OBO::NoSignedWrap);1884  EXPECT_TRUE(NSWForAllValues.isSingleElement() &&1885              NSWForAllValues.getSingleElement()->isMaxValue());1886 1887  auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(1888      Instruction::Add, ConstantRange(32, /* isFullSet = */ true),1889      OBO::NoUnsignedWrap);1890  EXPECT_TRUE(NUWForAllValues.isSingleElement() &&1891              NUWForAllValues.getSingleElement()->isMinValue());1892 1893  NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(1894      Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),1895      OBO::NoUnsignedWrap);1896  EXPECT_TRUE(NUWForAllValues.isSingleElement() &&1897              NUWForAllValues.getSingleElement()->isMaxValue());1898 1899  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(1900      Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());1901  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(1902      Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet());1903  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(1904      Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());1905  EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(1906      Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet());1907 1908  ConstantRange OneToFive(APInt(32, 1), APInt(32, 6));1909  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1910                Instruction::Add, OneToFive, OBO::NoSignedWrap),1911            ConstantRange(APInt::getSignedMinValue(32),1912                          APInt::getSignedMaxValue(32) - 4));1913  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1914                Instruction::Add, OneToFive, OBO::NoUnsignedWrap),1915            ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));1916  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1917                Instruction::Sub, OneToFive, OBO::NoSignedWrap),1918            ConstantRange(APInt::getSignedMinValue(32) + 5,1919                          APInt::getSignedMinValue(32)));1920  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1921                Instruction::Sub, OneToFive, OBO::NoUnsignedWrap),1922            ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));1923 1924  ConstantRange MinusFiveToMinusTwo(APInt(32, -5, true), APInt(32, -1, true));1925  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1926                Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap),1927            ConstantRange(APInt::getSignedMinValue(32) + 5,1928                          APInt::getSignedMinValue(32)));1929  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1930                Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),1931            ConstantRange(APInt(32, 0), APInt(32, 2)));1932  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1933                Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap),1934            ConstantRange(APInt::getSignedMinValue(32),1935                          APInt::getSignedMaxValue(32) - 4));1936  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1937                Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),1938            ConstantRange(APInt::getMaxValue(32) - 1, APInt::getMinValue(32)));1939 1940  ConstantRange MinusOneToOne(APInt(32, -1, true), APInt(32, 2));1941  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1942                Instruction::Add, MinusOneToOne, OBO::NoSignedWrap),1943            ConstantRange(APInt::getSignedMinValue(32) + 1,1944                          APInt::getSignedMinValue(32) - 1));1945  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1946                Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap),1947            ConstantRange(APInt(32, 0), APInt(32, 1)));1948  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1949                Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap),1950            ConstantRange(APInt::getSignedMinValue(32) + 1,1951                          APInt::getSignedMinValue(32) - 1));1952  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1953                Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap),1954            ConstantRange(APInt::getMaxValue(32),1955                          APInt::getMinValue(32)));1956 1957  ConstantRange One(APInt(32, 1), APInt(32, 2));1958  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1959                Instruction::Add, One, OBO::NoSignedWrap),1960            ConstantRange(APInt::getSignedMinValue(32),1961                          APInt::getSignedMaxValue(32)));1962  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1963                Instruction::Add, One, OBO::NoUnsignedWrap),1964            ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));1965  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1966                Instruction::Sub, One, OBO::NoSignedWrap),1967            ConstantRange(APInt::getSignedMinValue(32) + 1,1968                          APInt::getSignedMinValue(32)));1969  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1970                Instruction::Sub, One, OBO::NoUnsignedWrap),1971            ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));1972 1973  ConstantRange OneLessThanBitWidth(APInt(32, 0), APInt(32, 31) + 1);1974  ConstantRange UpToBitWidth(APInt(32, 0), APInt(32, 32) + 1);1975  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1976                Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),1977            ConstantRange::makeGuaranteedNoWrapRegion(1978                Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));1979  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1980                Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),1981            ConstantRange::makeGuaranteedNoWrapRegion(1982                Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));1983  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1984                Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),1985            ConstantRange(APInt(32, 0), APInt(32, 1) + 1));1986  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(1987                Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),1988            ConstantRange(APInt(32, -1, true), APInt(32, 0) + 1));1989 1990  EXPECT_EQ(1991      ConstantRange::makeGuaranteedNoWrapRegion(1992          Instruction::Shl, ConstantRange::getFull(32), OBO::NoUnsignedWrap),1993      ConstantRange::makeGuaranteedNoWrapRegion(1994          Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));1995  EXPECT_EQ(1996      ConstantRange::makeGuaranteedNoWrapRegion(1997          Instruction::Shl, ConstantRange::getFull(32), OBO::NoSignedWrap),1998      ConstantRange::makeGuaranteedNoWrapRegion(1999          Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));2000 2001  ConstantRange IllegalShAmt(APInt(32, 32), APInt(32, 0) + 1);2002  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(2003                Instruction::Shl, IllegalShAmt, OBO::NoUnsignedWrap),2004            ConstantRange::getFull(32));2005  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(2006                Instruction::Shl, IllegalShAmt, OBO::NoSignedWrap),2007            ConstantRange::getFull(32));2008 2009  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(2010                Instruction::Shl,2011                ConstantRange(APInt(32, -32, true), APInt(32, 16) + 1),2012                OBO::NoUnsignedWrap),2013            ConstantRange::makeGuaranteedNoWrapRegion(2014                Instruction::Shl,2015                ConstantRange(APInt(32, 0), APInt(32, 16) + 1),2016                OBO::NoUnsignedWrap));2017  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(2018                Instruction::Shl,2019                ConstantRange(APInt(32, -32, true), APInt(32, 16) + 1),2020                OBO::NoSignedWrap),2021            ConstantRange::makeGuaranteedNoWrapRegion(2022                Instruction::Shl,2023                ConstantRange(APInt(32, 0), APInt(32, 16) + 1),2024                OBO::NoSignedWrap));2025 2026  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(2027                Instruction::Shl,2028                ConstantRange(APInt(32, -32, true), APInt(32, 16) + 1),2029                OBO::NoUnsignedWrap),2030            ConstantRange(APInt(32, 0), APInt(32, 65535) + 1));2031  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(2032                Instruction::Shl,2033                ConstantRange(APInt(32, -32, true), APInt(32, 16) + 1),2034                OBO::NoSignedWrap),2035            ConstantRange(APInt(32, -32768, true), APInt(32, 32767) + 1));2036}2037 2038template <typename Fn>2039void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,2040                                unsigned NoWrapKind, Fn OverflowFn) {2041  for (unsigned Bits : {1, 5}) {2042    EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {2043      if (CR.isEmptySet())2044        return;2045      if (Instruction::isShift(BinOp) && CR.getUnsignedMax().uge(Bits))2046        return;2047 2048      ConstantRange NoWrap =2049          ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR, NoWrapKind);2050      EnumerateAPInts(Bits, [&](const APInt &N1) {2051        bool NoOverflow = true;2052        bool Overflow = true;2053        ForeachNumInConstantRange(CR, [&](const APInt &N2) {2054          if (OverflowFn(N1, N2))2055            NoOverflow = false;2056          else2057            Overflow = false;2058        });2059        EXPECT_EQ(NoOverflow, NoWrap.contains(N1));2060 2061        // The no-wrap range is exact for single-element ranges.2062        if (CR.isSingleElement()) {2063          EXPECT_EQ(Overflow, !NoWrap.contains(N1));2064        }2065      });2066    });2067  }2068}2069 2070// Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element2071// ranges also exact.2072TEST(ConstantRange, NoWrapRegionExhaustive) {2073  TestNoWrapRegionExhaustive(2074      Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap,2075      [](const APInt &N1, const APInt &N2) {2076        bool Overflow;2077        (void) N1.uadd_ov(N2, Overflow);2078        return Overflow;2079      });2080  TestNoWrapRegionExhaustive(2081      Instruction::Add, OverflowingBinaryOperator::NoSignedWrap,2082      [](const APInt &N1, const APInt &N2) {2083        bool Overflow;2084        (void) N1.sadd_ov(N2, Overflow);2085        return Overflow;2086      });2087  TestNoWrapRegionExhaustive(2088      Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap,2089      [](const APInt &N1, const APInt &N2) {2090        bool Overflow;2091        (void) N1.usub_ov(N2, Overflow);2092        return Overflow;2093      });2094  TestNoWrapRegionExhaustive(2095      Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap,2096      [](const APInt &N1, const APInt &N2) {2097        bool Overflow;2098        (void) N1.ssub_ov(N2, Overflow);2099        return Overflow;2100      });2101  TestNoWrapRegionExhaustive(2102      Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap,2103      [](const APInt &N1, const APInt &N2) {2104        bool Overflow;2105        (void) N1.umul_ov(N2, Overflow);2106        return Overflow;2107      });2108  TestNoWrapRegionExhaustive(2109      Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap,2110      [](const APInt &N1, const APInt &N2) {2111        bool Overflow;2112        (void) N1.smul_ov(N2, Overflow);2113        return Overflow;2114      });2115  TestNoWrapRegionExhaustive(Instruction::Shl,2116                             OverflowingBinaryOperator::NoUnsignedWrap,2117                             [](const APInt &N1, const APInt &N2) {2118                               bool Overflow;2119                               (void)N1.ushl_ov(N2, Overflow);2120                               return Overflow;2121                             });2122  TestNoWrapRegionExhaustive(Instruction::Shl,2123                             OverflowingBinaryOperator::NoSignedWrap,2124                             [](const APInt &N1, const APInt &N2) {2125                               bool Overflow;2126                               (void)N1.sshl_ov(N2, Overflow);2127                               return Overflow;2128                             });2129}2130 2131TEST(ConstantRange, GetEquivalentICmp) {2132  APInt RHS;2133  CmpInst::Predicate Pred;2134 2135  EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))2136                  .getEquivalentICmp(Pred, RHS));2137  EXPECT_EQ(Pred, CmpInst::ICMP_ULT);2138  EXPECT_EQ(RHS, APInt(32, 100));2139 2140  EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100))2141                  .getEquivalentICmp(Pred, RHS));2142  EXPECT_EQ(Pred, CmpInst::ICMP_SLT);2143  EXPECT_EQ(RHS, APInt(32, 100));2144 2145  EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32))2146                  .getEquivalentICmp(Pred, RHS));2147  EXPECT_EQ(Pred, CmpInst::ICMP_UGE);2148  EXPECT_EQ(RHS, APInt(32, 100));2149 2150  EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32))2151                  .getEquivalentICmp(Pred, RHS));2152  EXPECT_EQ(Pred, CmpInst::ICMP_SGE);2153  EXPECT_EQ(RHS, APInt(32, 100));2154 2155  EXPECT_TRUE(2156      ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred, RHS));2157  EXPECT_EQ(Pred, CmpInst::ICMP_UGE);2158  EXPECT_EQ(RHS, APInt(32, 0));2159 2160  EXPECT_TRUE(2161      ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred, RHS));2162  EXPECT_EQ(Pred, CmpInst::ICMP_ULT);2163  EXPECT_EQ(RHS, APInt(32, 0));2164 2165  EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200))2166                   .getEquivalentICmp(Pred, RHS));2167 2168  EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100),2169                             APInt::getSignedMinValue(32) + APInt(32, 100))2170                   .getEquivalentICmp(Pred, RHS));2171 2172  EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100),2173                             APInt::getMinValue(32) + APInt(32, 100))2174                   .getEquivalentICmp(Pred, RHS));2175 2176  EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred, RHS));2177  EXPECT_EQ(Pred, CmpInst::ICMP_EQ);2178  EXPECT_EQ(RHS, APInt(32, 100));2179 2180  EXPECT_TRUE(2181      ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred, RHS));2182  EXPECT_EQ(Pred, CmpInst::ICMP_NE);2183  EXPECT_EQ(RHS, APInt(32, 100));2184 2185  EXPECT_TRUE(2186      ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred, RHS));2187  EXPECT_EQ(Pred, CmpInst::ICMP_NE);2188  EXPECT_EQ(RHS, APInt(512, 100));2189 2190  // NB!  It would be correct for the following four calls to getEquivalentICmp2191  // to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT.2192  // However, that's not the case today.2193 2194  EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred, RHS));2195  EXPECT_EQ(Pred, CmpInst::ICMP_EQ);2196  EXPECT_EQ(RHS, APInt(32, 0));2197 2198  EXPECT_TRUE(2199      ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred, RHS));2200  EXPECT_EQ(Pred, CmpInst::ICMP_NE);2201  EXPECT_EQ(RHS, APInt(32, 0));2202 2203  EXPECT_TRUE(ConstantRange(APInt(32, -1, true)).getEquivalentICmp(Pred, RHS));2204  EXPECT_EQ(Pred, CmpInst::ICMP_EQ);2205  EXPECT_EQ(RHS, APInt(32, -1, true));2206 2207  EXPECT_TRUE(ConstantRange(APInt(32, -1, true))2208                  .inverse()2209                  .getEquivalentICmp(Pred, RHS));2210  EXPECT_EQ(Pred, CmpInst::ICMP_NE);2211  EXPECT_EQ(RHS, APInt(32, -1, true));2212 2213  EnumerateInterestingConstantRanges([](const ConstantRange &CR) {2214    unsigned Bits = CR.getBitWidth();2215    CmpInst::Predicate Pred;2216    APInt RHS, Offset;2217    CR.getEquivalentICmp(Pred, RHS, Offset);2218    EnumerateAPInts(Bits, [&](const APInt &N) {2219      bool Result = ICmpInst::compare(N + Offset, RHS, Pred);2220      EXPECT_EQ(CR.contains(N), Result);2221    });2222 2223    if (CR.getEquivalentICmp(Pred, RHS)) {2224      EnumerateAPInts(Bits, [&](const APInt &N) {2225        bool Result = ICmpInst::compare(N, RHS, Pred);2226        EXPECT_EQ(CR.contains(N), Result);2227      });2228    }2229  });2230}2231 2232TEST(ConstantRange, SplitPosNeg) {2233  EnumerateInterestingConstantRanges([](const ConstantRange &CR) {2234    auto [Pos, Neg] = CR.splitPosNeg();2235    EXPECT_TRUE(Pos.isAllPositive());2236    EXPECT_TRUE(Neg.isAllNegative());2237    if (CR.getBitWidth() == 1)2238      EXPECT_TRUE(Pos.isEmptySet());2239  });2240}2241 2242#define EXPECT_MAY_OVERFLOW(op) \2243  EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))2244#define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \2245  EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))2246#define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \2247  EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (op))2248#define EXPECT_NEVER_OVERFLOWS(op) \2249  EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))2250 2251TEST_F(ConstantRangeTest, UnsignedAddOverflow) {2252  // Ill-defined - may overflow is a conservative result.2253  EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty));2254  EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some));2255 2256  // Never overflow despite one full/wrap set.2257  ConstantRange Zero(APInt::getZero(16));2258  EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero));2259  EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero));2260  EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full));2261  EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap));2262 2263  // But usually full/wrap always may overflow.2264  EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One));2265  EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One));2266  EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full));2267  EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap));2268 2269  ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00));2270  ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));2271  ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));2272  EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1));2273  EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2));2274  EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A));2275  EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A));2276 2277  ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400));2278  ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400));2279  EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1));2280  EXPECT_ALWAYS_OVERFLOWS_HIGH(A.unsignedAddMayOverflow(C2));2281  EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A));2282  EXPECT_ALWAYS_OVERFLOWS_HIGH(C2.unsignedAddMayOverflow(A));2283}2284 2285TEST_F(ConstantRangeTest, UnsignedSubOverflow) {2286  // Ill-defined - may overflow is a conservative result.2287  EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty));2288  EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some));2289 2290  // Never overflow despite one full/wrap set.2291  ConstantRange Zero(APInt::getZero(16));2292  ConstantRange Max(APInt::getAllOnes(16));2293  EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero));2294  EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero));2295  EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full));2296  EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap));2297 2298  // But usually full/wrap always may overflow.2299  EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One));2300  EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One));2301  EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full));2302  EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap));2303 2304  ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100));2305  ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200));2306  EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A));2307  EXPECT_ALWAYS_OVERFLOWS_LOW(A.unsignedSubMayOverflow(B));2308 2309  ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101));2310  ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));2311  EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1));2312  EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1));2313 2314  ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102));2315  ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));2316  EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2));2317  EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2));2318}2319 2320TEST_F(ConstantRangeTest, SignedAddOverflow) {2321  // Ill-defined - may overflow is a conservative result.2322  EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty));2323  EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some));2324 2325  // Never overflow despite one full/wrap set.2326  ConstantRange Zero(APInt::getZero(16));2327  EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero));2328  EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero));2329  EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full));2330  EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap));2331 2332  // But usually full/wrap always may overflow.2333  EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One));2334  EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One));2335  EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full));2336  EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap));2337 2338  ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));2339  ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));2340  ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));2341  EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1));2342  EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2));2343  ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201));2344  ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202));2345  EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3));2346  EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4));2347  ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400));2348  ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400));2349  EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5));2350  EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedAddMayOverflow(B6));2351 2352  ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));2353  ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00));2354  ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00));2355  EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1));2356  EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2));2357  ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000));2358  ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000));2359  EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3));2360  EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4));2361  ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02));2362  ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01));2363  EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5));2364  EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedAddMayOverflow(D6));2365 2366  ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));2367  EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E));2368  ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000));2369  EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F));2370}2371 2372TEST_F(ConstantRangeTest, SignedSubOverflow) {2373  // Ill-defined - may overflow is a conservative result.2374  EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty));2375  EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some));2376 2377  // Never overflow despite one full/wrap set.2378  ConstantRange Zero(APInt::getZero(16));2379  EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero));2380  EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero));2381 2382  // But usually full/wrap always may overflow.2383  EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One));2384  EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One));2385  EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full));2386  EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap));2387 2388  ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));2389  ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00));2390  ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00));2391  EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1));2392  EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2));2393  ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02));2394  ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01));2395  EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3));2396  EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedSubMayOverflow(B4));2397 2398  ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));2399  ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201));2400  ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202));2401  EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1));2402  EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2));2403  ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400));2404  ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400));2405  EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3));2406  EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedSubMayOverflow(D4));2407 2408  ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));2409  EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E));2410  ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001));2411  EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F));2412}2413 2414template <typename Fn1, typename Fn2>2415static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) {2416  // Constant range overflow checks are tested exhaustively on 4-bit numbers.2417  EnumerateTwoInterestingConstantRanges([=](const ConstantRange &CR1,2418                                            const ConstantRange &CR2) {2419    // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the2420    // operations have overflow / have no overflow.2421    bool RangeHasOverflowLow = false;2422    bool RangeHasOverflowHigh = false;2423    bool RangeHasNoOverflow = false;2424    ForeachNumInConstantRange(CR1, [&](const APInt &N1) {2425      ForeachNumInConstantRange(CR2, [&](const APInt &N2) {2426        bool IsOverflowHigh;2427        if (!OverflowFn(IsOverflowHigh, N1, N2)) {2428          RangeHasNoOverflow = true;2429          return;2430        }2431 2432        if (IsOverflowHigh)2433          RangeHasOverflowHigh = true;2434        else2435          RangeHasOverflowLow = true;2436      });2437    });2438 2439    ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2);2440    switch (OR) {2441    case ConstantRange::OverflowResult::AlwaysOverflowsLow:2442      EXPECT_TRUE(RangeHasOverflowLow);2443      EXPECT_FALSE(RangeHasOverflowHigh);2444      EXPECT_FALSE(RangeHasNoOverflow);2445      break;2446    case ConstantRange::OverflowResult::AlwaysOverflowsHigh:2447      EXPECT_TRUE(RangeHasOverflowHigh);2448      EXPECT_FALSE(RangeHasOverflowLow);2449      EXPECT_FALSE(RangeHasNoOverflow);2450      break;2451    case ConstantRange::OverflowResult::NeverOverflows:2452      EXPECT_FALSE(RangeHasOverflowLow);2453      EXPECT_FALSE(RangeHasOverflowHigh);2454      EXPECT_TRUE(RangeHasNoOverflow);2455      break;2456    case ConstantRange::OverflowResult::MayOverflow:2457      // We return MayOverflow for empty sets as a conservative result,2458      // but of course neither the RangeHasOverflow nor the2459      // RangeHasNoOverflow flags will be set.2460      if (CR1.isEmptySet() || CR2.isEmptySet())2461        break;2462 2463      EXPECT_TRUE(RangeHasOverflowLow || RangeHasOverflowHigh);2464      EXPECT_TRUE(RangeHasNoOverflow);2465      break;2466    }2467  });2468}2469 2470TEST_F(ConstantRangeTest, UnsignedAddOverflowExhaustive) {2471  TestOverflowExhaustive(2472      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {2473        bool Overflow;2474        (void) N1.uadd_ov(N2, Overflow);2475        IsOverflowHigh = true;2476        return Overflow;2477      },2478      [](const ConstantRange &CR1, const ConstantRange &CR2) {2479        return CR1.unsignedAddMayOverflow(CR2);2480      });2481}2482 2483TEST_F(ConstantRangeTest, UnsignedSubOverflowExhaustive) {2484  TestOverflowExhaustive(2485      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {2486        bool Overflow;2487        (void) N1.usub_ov(N2, Overflow);2488        IsOverflowHigh = false;2489        return Overflow;2490      },2491      [](const ConstantRange &CR1, const ConstantRange &CR2) {2492        return CR1.unsignedSubMayOverflow(CR2);2493      });2494}2495 2496TEST_F(ConstantRangeTest, UnsignedMulOverflowExhaustive) {2497  TestOverflowExhaustive(2498      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {2499        bool Overflow;2500        (void) N1.umul_ov(N2, Overflow);2501        IsOverflowHigh = true;2502        return Overflow;2503      },2504      [](const ConstantRange &CR1, const ConstantRange &CR2) {2505        return CR1.unsignedMulMayOverflow(CR2);2506      });2507}2508 2509TEST_F(ConstantRangeTest, SignedAddOverflowExhaustive) {2510  TestOverflowExhaustive(2511      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {2512        bool Overflow;2513        (void) N1.sadd_ov(N2, Overflow);2514        IsOverflowHigh = N1.isNonNegative();2515        return Overflow;2516      },2517      [](const ConstantRange &CR1, const ConstantRange &CR2) {2518        return CR1.signedAddMayOverflow(CR2);2519      });2520}2521 2522TEST_F(ConstantRangeTest, SignedSubOverflowExhaustive) {2523  TestOverflowExhaustive(2524      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {2525        bool Overflow;2526        (void) N1.ssub_ov(N2, Overflow);2527        IsOverflowHigh = N1.isNonNegative();2528        return Overflow;2529      },2530      [](const ConstantRange &CR1, const ConstantRange &CR2) {2531        return CR1.signedSubMayOverflow(CR2);2532      });2533}2534 2535TEST_F(ConstantRangeTest, FromKnownBits) {2536  KnownBits Unknown(16);2537  EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false));2538  EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true));2539 2540  // .10..01. -> unsigned 01000010 (66)  to 11011011 (219)2541  //          -> signed   11000010 (194) to 01011011 (91)2542  KnownBits Known(8);2543  Known.Zero = 36;2544  Known.One = 66;2545  ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1));2546  ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1));2547  EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false));2548  EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true));2549 2550  // 1.10.10. -> 10100100 (164) to 11101101 (237)2551  Known.Zero = 18;2552  Known.One = 164;2553  ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1));2554  EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false));2555  EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true));2556 2557  // 01.0.1.0 -> 01000100 (68) to 01101110 (110)2558  Known.Zero = 145;2559  Known.One = 68;2560  ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1));2561  EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false));2562  EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true));2563}2564 2565TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {2566  unsigned Bits = 4;2567  unsigned Max = 1 << Bits;2568  KnownBits Known(Bits);2569  for (unsigned Zero = 0; Zero < Max; ++Zero) {2570    for (unsigned One = 0; One < Max; ++One) {2571      Known.Zero = Zero;2572      Known.One = One;2573      if (Known.hasConflict() || Known.isUnknown())2574        continue;2575 2576      SmallBitVector Elems(1 << Bits);2577      for (unsigned N = 0; N < Max; ++N) {2578        APInt Num(Bits, N);2579        if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)2580          continue;2581        Elems.set(Num.getZExtValue());2582      }2583 2584      TestRange(ConstantRange::fromKnownBits(Known, false),2585                Elems, PreferSmallestUnsigned, {});2586      TestRange(ConstantRange::fromKnownBits(Known, true),2587                Elems, PreferSmallestSigned, {});2588    }2589  }2590}2591 2592TEST_F(ConstantRangeTest, ToKnownBits) {2593  EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {2594    KnownBits Known = CR.toKnownBits();2595    KnownBits ExpectedKnown(CR.getBitWidth());2596    ExpectedKnown.Zero.setAllBits();2597    ExpectedKnown.One.setAllBits();2598    ForeachNumInConstantRange(CR, [&](const APInt &N) {2599      ExpectedKnown.One &= N;2600      ExpectedKnown.Zero &= ~N;2601    });2602    // For an empty CR any result would be legal.2603    if (!CR.isEmptySet()) {2604      EXPECT_EQ(ExpectedKnown, Known);2605    }2606  });2607}2608 2609TEST_F(ConstantRangeTest, Negative) {2610  // All elements in an empty set (of which there are none) are both negative2611  // and non-negative. Empty & full sets checked explicitly for clarity, but2612  // they are also covered by the exhaustive test below.2613  EXPECT_TRUE(Empty.isAllNegative());2614  EXPECT_TRUE(Empty.isAllNonNegative());2615  EXPECT_TRUE(Empty.isAllPositive());2616  EXPECT_FALSE(Full.isAllNegative());2617  EXPECT_FALSE(Full.isAllNonNegative());2618  EXPECT_FALSE(Full.isAllPositive());2619 2620  EnumerateInterestingConstantRanges([](const ConstantRange &CR) {2621    bool AllNegative = true;2622    bool AllNonNegative = true;2623    bool AllPositive = true;2624    ForeachNumInConstantRange(CR, [&](const APInt &N) {2625      if (!N.isNegative())2626        AllNegative = false;2627      if (!N.isNonNegative())2628        AllNonNegative = false;2629      if (!N.isStrictlyPositive())2630        AllPositive = false;2631    });2632    assert(2633        (CR.isEmptySet() || !AllNegative || !AllNonNegative || !AllPositive) &&2634        "Only empty set can be all negative, all non-negative, and all "2635        "positive");2636 2637    EXPECT_EQ(AllNegative, CR.isAllNegative());2638    EXPECT_EQ(AllNonNegative, CR.isAllNonNegative());2639    EXPECT_EQ(AllPositive, CR.isAllPositive());2640  });2641}2642 2643TEST_F(ConstantRangeTest, UAddSat) {2644  TestBinaryOpExhaustive(2645      [](const ConstantRange &CR1, const ConstantRange &CR2) {2646        return CR1.uadd_sat(CR2);2647      },2648      [](const APInt &N1, const APInt &N2) {2649        return N1.uadd_sat(N2);2650      },2651      PreferSmallestUnsigned);2652}2653 2654TEST_F(ConstantRangeTest, USubSat) {2655  TestBinaryOpExhaustive(2656      [](const ConstantRange &CR1, const ConstantRange &CR2) {2657        return CR1.usub_sat(CR2);2658      },2659      [](const APInt &N1, const APInt &N2) {2660        return N1.usub_sat(N2);2661      },2662      PreferSmallestUnsigned);2663}2664 2665TEST_F(ConstantRangeTest, UMulSat) {2666  TestBinaryOpExhaustive(2667      [](const ConstantRange &CR1, const ConstantRange &CR2) {2668        return CR1.umul_sat(CR2);2669      },2670      [](const APInt &N1, const APInt &N2) { return N1.umul_sat(N2); },2671      PreferSmallestUnsigned);2672}2673 2674TEST_F(ConstantRangeTest, UShlSat) {2675  TestBinaryOpExhaustive(2676      [](const ConstantRange &CR1, const ConstantRange &CR2) {2677        return CR1.ushl_sat(CR2);2678      },2679      [](const APInt &N1, const APInt &N2) { return N1.ushl_sat(N2); },2680      PreferSmallestUnsigned);2681}2682 2683TEST_F(ConstantRangeTest, SAddSat) {2684  TestBinaryOpExhaustive(2685      [](const ConstantRange &CR1, const ConstantRange &CR2) {2686        return CR1.sadd_sat(CR2);2687      },2688      [](const APInt &N1, const APInt &N2) {2689        return N1.sadd_sat(N2);2690      },2691      PreferSmallestSigned);2692}2693 2694TEST_F(ConstantRangeTest, SSubSat) {2695  TestBinaryOpExhaustive(2696      [](const ConstantRange &CR1, const ConstantRange &CR2) {2697        return CR1.ssub_sat(CR2);2698      },2699      [](const APInt &N1, const APInt &N2) {2700        return N1.ssub_sat(N2);2701      },2702      PreferSmallestSigned);2703}2704 2705TEST_F(ConstantRangeTest, SMulSat) {2706  TestBinaryOpExhaustive(2707      [](const ConstantRange &CR1, const ConstantRange &CR2) {2708        return CR1.smul_sat(CR2);2709      },2710      [](const APInt &N1, const APInt &N2) { return N1.smul_sat(N2); },2711      PreferSmallestSigned);2712}2713 2714TEST_F(ConstantRangeTest, SShlSat) {2715  TestBinaryOpExhaustive(2716      [](const ConstantRange &CR1, const ConstantRange &CR2) {2717        return CR1.sshl_sat(CR2);2718      },2719      [](const APInt &N1, const APInt &N2) { return N1.sshl_sat(N2); },2720      PreferSmallestSigned);2721}2722 2723TEST_F(ConstantRangeTest, Abs) {2724  TestUnaryOpExhaustive(2725      [](const ConstantRange &CR) { return CR.abs(); },2726      [](const APInt &N) { return N.abs(); });2727 2728  TestUnaryOpExhaustive(2729      [](const ConstantRange &CR) { return CR.abs(/*IntMinIsPoison=*/true); },2730      [](const APInt &N) -> std::optional<APInt> {2731        if (N.isMinSignedValue())2732          return std::nullopt;2733        return N.abs();2734      });2735}2736 2737TEST_F(ConstantRangeTest, Ctlz) {2738  TestUnaryOpExhaustive(2739      [](const ConstantRange &CR) { return CR.ctlz(); },2740      [](const APInt &N) { return APInt(N.getBitWidth(), N.countl_zero()); });2741 2742  TestUnaryOpExhaustive(2743      [](const ConstantRange &CR) { return CR.ctlz(/*ZeroIsPoison=*/true); },2744      [](const APInt &N) -> std::optional<APInt> {2745        if (N.isZero())2746          return std::nullopt;2747        return APInt(N.getBitWidth(), N.countl_zero());2748      });2749}2750 2751TEST_F(ConstantRangeTest, Cttz) {2752  TestUnaryOpExhaustive(2753      [](const ConstantRange &CR) { return CR.cttz(); },2754      [](const APInt &N) { return APInt(N.getBitWidth(), N.countr_zero()); });2755 2756  TestUnaryOpExhaustive(2757      [](const ConstantRange &CR) { return CR.cttz(/*ZeroIsPoison=*/true); },2758      [](const APInt &N) -> std::optional<APInt> {2759        if (N.isZero())2760          return std::nullopt;2761        return APInt(N.getBitWidth(), N.countr_zero());2762      });2763}2764 2765TEST_F(ConstantRangeTest, Ctpop) {2766  TestUnaryOpExhaustive(2767      [](const ConstantRange &CR) { return CR.ctpop(); },2768      [](const APInt &N) { return APInt(N.getBitWidth(), N.popcount()); });2769}2770 2771TEST_F(ConstantRangeTest, castOps) {2772  ConstantRange A(APInt(16, 66), APInt(16, 128));2773  ConstantRange FpToI8 = A.castOp(Instruction::FPToSI, 8);2774  EXPECT_EQ(8u, FpToI8.getBitWidth());2775  EXPECT_TRUE(FpToI8.isFullSet());2776 2777  ConstantRange FpToI16 = A.castOp(Instruction::FPToSI, 16);2778  EXPECT_EQ(16u, FpToI16.getBitWidth());2779  EXPECT_EQ(A, FpToI16);2780 2781  ConstantRange FPExtToDouble = A.castOp(Instruction::FPExt, 64);2782  EXPECT_EQ(64u, FPExtToDouble.getBitWidth());2783  EXPECT_TRUE(FPExtToDouble.isFullSet());2784 2785  ConstantRange PtrToInt = A.castOp(Instruction::PtrToInt, 64);2786  EXPECT_EQ(64u, PtrToInt.getBitWidth());2787  EXPECT_TRUE(PtrToInt.isFullSet());2788 2789  ConstantRange IntToPtr = A.castOp(Instruction::IntToPtr, 64);2790  EXPECT_EQ(64u, IntToPtr.getBitWidth());2791  EXPECT_TRUE(IntToPtr.isFullSet());2792 2793  ConstantRange UIToFP = A.castOp(Instruction::UIToFP, 16);2794  EXPECT_EQ(16u, UIToFP.getBitWidth());2795  EXPECT_TRUE(UIToFP.isFullSet());2796 2797  ConstantRange UIToFP2 = A.castOp(Instruction::UIToFP, 64);2798  ConstantRange B(APInt(64, 0), APInt(64, 65536));2799  EXPECT_EQ(64u, UIToFP2.getBitWidth());2800  EXPECT_EQ(B, UIToFP2);2801 2802  ConstantRange SIToFP = A.castOp(Instruction::SIToFP, 16);2803  EXPECT_EQ(16u, SIToFP.getBitWidth());2804  EXPECT_TRUE(SIToFP.isFullSet());2805 2806  ConstantRange SIToFP2 = A.castOp(Instruction::SIToFP, 64);2807  ConstantRange C(APInt(64, -32768), APInt(64, 32768));2808  EXPECT_EQ(64u, SIToFP2.getBitWidth());2809  EXPECT_EQ(C, SIToFP2);2810}2811 2812TEST_F(ConstantRangeTest, binaryAnd) {2813  // Single element ranges.2814  ConstantRange R16(APInt(8, 16));2815  ConstantRange R20(APInt(8, 20));2816  EXPECT_EQ(*R16.binaryAnd(R16).getSingleElement(), APInt(8, 16));2817  EXPECT_EQ(*R16.binaryAnd(R20).getSingleElement(), APInt(8, 16 & 20));2818 2819  ConstantRange R16_32(APInt(8, 16), APInt(8, 32));2820  // 'And' with a high bits mask.2821  ConstantRange R32(APInt(8, 32));2822  EXPECT_TRUE(R16_32.binaryAnd(R32).getSingleElement()->isZero());2823  EXPECT_TRUE(R32.binaryAnd(R16_32).getSingleElement()->isZero());2824  // 'And' with a low bits mask. Handled conservatively for now.2825  ConstantRange R4(APInt(8, 4));2826  ConstantRange R0_5(APInt(8, 0), APInt(8, 5));2827  EXPECT_EQ(R16_32.binaryAnd(R4), R0_5);2828  EXPECT_EQ(R4.binaryAnd(R16_32), R0_5);2829 2830  // Ranges with more than one element. Handled conservatively for now.2831  ConstantRange R0_99(APInt(8, 0), APInt(8, 99));2832  ConstantRange R0_32(APInt(8, 0), APInt(8, 32));2833  EXPECT_EQ(R16_32.binaryAnd(R0_99), R0_32);2834  EXPECT_EQ(R0_99.binaryAnd(R16_32), R0_32);2835 2836  // 'And' with leading bits are masked (with common leading bits stripped)2837  ConstantRange RMaskedL(APInt(8, 0b10'00101'1), APInt(8, 0b10'10000'0 + 1));2838  ConstantRange RMaskedR(APInt(8, 0b10'11111'0), APInt(8, 0b10'11111'1 + 1));2839  EXPECT_EQ(RMaskedL.binaryAnd(RMaskedR).getLower(), APInt(8, 0b10'00101'0));2840  EXPECT_EQ(RMaskedR.binaryAnd(RMaskedL).getLower(), APInt(8, 0b10'00101'0));2841 2842  ConstantRange RMaskedL1(APInt(8, 0b00'011'010), APInt(8, 0b00'100'100 + 1));2843  ConstantRange RMaskedR1(APInt(8, 0b00'111'010), APInt(8, 0b00'111'110 + 1));2844  EXPECT_EQ(RMaskedL1.binaryAnd(RMaskedR1).getLower(), APInt(8, 0b00'011'000));2845  EXPECT_EQ(RMaskedR1.binaryAnd(RMaskedL1).getLower(), APInt(8, 0b00'011'000));2846 2847  ConstantRange RMaskedL2(APInt(8, 0b0000'0111u), APInt(8, 0b0000'1101u + 1u));2848  ConstantRange RMaskedR2(APInt(8, 0xff), APInt(8, 0));2849  EXPECT_EQ(RMaskedL2.binaryAnd(RMaskedR2), RMaskedL2);2850  EXPECT_EQ(RMaskedR2.binaryAnd(RMaskedL2), RMaskedL2);2851 2852  ConstantRange RMaskedL3(APInt(4, 0b0011u), APInt(4, 0));2853  ConstantRange RMaskedR3(APInt(4, 0b1011u), APInt(4, 0));2854  APInt Zero_4(4, 0);2855  EXPECT_EQ(RMaskedL3.binaryAnd(RMaskedR3).getLower().uge(Zero_4), true);2856  EXPECT_EQ(RMaskedR3.binaryAnd(RMaskedL3).getLower().uge(Zero_4), true);2857 2858  // wrapped set2859  APInt NegSeven(4, 9); // Also -72860  ConstantRange RMaskedL4(NegSeven, APInt(4, 1));2861  ConstantRange RMaskedR4(NegSeven, APInt(4, 0));2862  EXPECT_EQ(RMaskedL4.binaryAnd(RMaskedR4).contains(Zero_4), true);2863  EXPECT_EQ(RMaskedR4.binaryAnd(RMaskedL4).contains(Zero_4), true);2864  EXPECT_EQ(RMaskedL4.binaryAnd(RMaskedR4).contains(NegSeven), true);2865  EXPECT_EQ(RMaskedR4.binaryAnd(RMaskedL4).contains(NegSeven), true);2866 2867  TestBinaryOpExhaustive(2868      [](const ConstantRange &CR1, const ConstantRange &CR2) {2869        return CR1.binaryAnd(CR2);2870      },2871      [](const APInt &N1, const APInt &N2) { return N1 & N2; }, PreferSmallest,2872      CheckSingleElementsOnly);2873}2874 2875TEST_F(ConstantRangeTest, binaryOr) {2876  // Single element ranges.2877  ConstantRange R16(APInt(8, 16));2878  ConstantRange R20(APInt(8, 20));2879  EXPECT_EQ(*R16.binaryOr(R16).getSingleElement(), APInt(8, 16));2880  EXPECT_EQ(*R16.binaryOr(R20).getSingleElement(), APInt(8, 16 | 20));2881 2882  ConstantRange R16_32(APInt(8, 16), APInt(8, 32));2883  // 'Or' with a high bits mask.2884  // KnownBits estimate is important, otherwise the maximum included element2885  // would be 2^8 - 1.2886  ConstantRange R32(APInt(8, 32));2887  ConstantRange R48_64(APInt(8, 48), APInt(8, 64));2888  EXPECT_EQ(R16_32.binaryOr(R32), R48_64);2889  EXPECT_EQ(R32.binaryOr(R16_32), R48_64);2890  // 'Or' with a low bits mask.2891  ConstantRange R4(APInt(8, 4));2892  ConstantRange R0_16(APInt(8, 0), APInt(8, 16));2893  ConstantRange R4_16(APInt(8, 4), APInt(8, 16));2894  EXPECT_EQ(R0_16.binaryOr(R4), R4_16);2895  EXPECT_EQ(R4.binaryOr(R0_16), R4_16);2896 2897  // Ranges with more than one element. Handled conservatively for now.2898  // UMaxUMin estimate is important, otherwise the lower bound would be zero.2899  ConstantRange R0_64(APInt(8, 0), APInt(8, 64));2900  ConstantRange R5_32(APInt(8, 5), APInt(8, 32));2901  ConstantRange R5_64(APInt(8, 5), APInt(8, 64));2902  EXPECT_EQ(R0_64.binaryOr(R5_32), R5_64);2903  EXPECT_EQ(R5_32.binaryOr(R0_64), R5_64);2904 2905  TestBinaryOpExhaustive(2906      [](const ConstantRange &CR1, const ConstantRange &CR2) {2907        return CR1.binaryOr(CR2);2908      },2909      [](const APInt &N1, const APInt &N2) { return N1 | N2; }, PreferSmallest,2910      CheckSingleElementsOnly);2911}2912 2913TEST_F(ConstantRangeTest, binaryXor) {2914  // Single element ranges.2915  ConstantRange R16(APInt(8, 16));2916  ConstantRange R20(APInt(8, 20));2917  EXPECT_EQ(*R16.binaryXor(R16).getSingleElement(), APInt(8, 0));2918  EXPECT_EQ(*R16.binaryXor(R20).getSingleElement(), APInt(8, 16 ^ 20));2919 2920  // Ranges with more than a single element.2921  ConstantRange R16_35(APInt(8, 16), APInt(8, 35));2922  ConstantRange R0_99(APInt(8, 0), APInt(8, 99));2923  EXPECT_EQ(R16_35.binaryXor(R16_35), ConstantRange(APInt(8, 0), APInt(8, 64)));2924  EXPECT_EQ(R16_35.binaryXor(R0_99), ConstantRange(APInt(8, 0), APInt(8, 128)));2925  EXPECT_EQ(R0_99.binaryXor(R16_35), ConstantRange(APInt(8, 0), APInt(8, 128)));2926 2927  // Treat xor A, B as sub nsw nuw A, B2928  ConstantRange R0_51(APInt(8, 0), APInt(8, 51));2929  ConstantRange R63(APInt(8, 63));2930  EXPECT_EQ(R0_51.binaryXor(R63), ConstantRange(APInt(8, 13), APInt(8, 64)));2931  EXPECT_EQ(R63.binaryXor(R0_51), ConstantRange(APInt(8, 13), APInt(8, 64)));2932 2933  TestBinaryOpExhaustive(2934      [](const ConstantRange &CR1, const ConstantRange &CR2) {2935        return CR1.binaryXor(CR2);2936      },2937      [](const APInt &N1, const APInt &N2) {2938        return N1 ^ N2;2939      },2940      PreferSmallest,2941      CheckSingleElementsOnly);2942}2943 2944TEST_F(ConstantRangeTest, binaryNot) {2945  TestUnaryOpExhaustive(2946      [](const ConstantRange &CR) { return CR.binaryNot(); },2947      [](const APInt &N) { return ~N; },2948      PreferSmallest);2949  TestUnaryOpExhaustive(2950      [](const ConstantRange &CR) {2951        return CR.binaryXor(ConstantRange(APInt::getAllOnes(CR.getBitWidth())));2952      },2953      [](const APInt &N) { return ~N; }, PreferSmallest);2954  TestUnaryOpExhaustive(2955      [](const ConstantRange &CR) {2956        return ConstantRange(APInt::getAllOnes(CR.getBitWidth())).binaryXor(CR);2957      },2958      [](const APInt &N) { return ~N; }, PreferSmallest);2959}2960 2961template <typename T>2962void testConstantRangeICmpPredEquivalence(ICmpInst::Predicate SrcPred, T Func) {2963  EnumerateTwoInterestingConstantRanges(2964      [&](const ConstantRange &CR1, const ConstantRange &CR2) {2965        ICmpInst::Predicate TgtPred;2966        bool ExpectedEquivalent;2967        std::tie(TgtPred, ExpectedEquivalent) = Func(CR1, CR2);2968        if (TgtPred == CmpInst::Predicate::BAD_ICMP_PREDICATE)2969          return;2970        bool TrulyEquivalent = true;2971        ForeachNumInConstantRange(CR1, [&](const APInt &N1) {2972          if (!TrulyEquivalent)2973            return;2974          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {2975            if (!TrulyEquivalent)2976              return;2977            TrulyEquivalent &= ICmpInst::compare(N1, N2, SrcPred) ==2978                               ICmpInst::compare(N1, N2, TgtPred);2979          });2980        });2981        ASSERT_EQ(TrulyEquivalent, ExpectedEquivalent);2982      });2983}2984 2985TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfICmpPredicate) {2986  for (auto Pred : ICmpInst::predicates()) {2987    if (ICmpInst::isEquality(Pred))2988      continue;2989    ICmpInst::Predicate FlippedSignednessPred =2990        ICmpInst::getFlippedSignednessPredicate(Pred);2991    testConstantRangeICmpPredEquivalence(Pred, [FlippedSignednessPred](2992                                                   const ConstantRange &CR1,2993                                                   const ConstantRange &CR2) {2994      return std::make_pair(2995          FlippedSignednessPred,2996          ConstantRange::areInsensitiveToSignednessOfICmpPredicate(CR1, CR2));2997    });2998  }2999}3000 3001TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfInvertedICmpPredicate) {3002  for (auto Pred : ICmpInst::predicates()) {3003    if (ICmpInst::isEquality(Pred))3004      continue;3005    ICmpInst::Predicate InvertedFlippedSignednessPred =3006        ICmpInst::getInversePredicate(3007            ICmpInst::getFlippedSignednessPredicate(Pred));3008    testConstantRangeICmpPredEquivalence(3009        Pred, [InvertedFlippedSignednessPred](const ConstantRange &CR1,3010                                              const ConstantRange &CR2) {3011          return std::make_pair(3012              InvertedFlippedSignednessPred,3013              ConstantRange::areInsensitiveToSignednessOfInvertedICmpPredicate(3014                  CR1, CR2));3015        });3016  }3017}3018 3019TEST_F(ConstantRangeTest, getEquivalentPredWithFlippedSignedness) {3020  for (auto Pred : ICmpInst::predicates()) {3021    if (ICmpInst::isEquality(Pred))3022      continue;3023    testConstantRangeICmpPredEquivalence(3024        Pred, [Pred](const ConstantRange &CR1, const ConstantRange &CR2) {3025          return std::make_pair(3026              ConstantRange::getEquivalentPredWithFlippedSignedness(Pred, CR1,3027                                                                    CR2),3028              /*ExpectedEquivalent=*/true);3029        });3030  }3031}3032 3033TEST_F(ConstantRangeTest, isSizeLargerThan) {3034  EXPECT_FALSE(Empty.isSizeLargerThan(0));3035 3036  EXPECT_TRUE(Full.isSizeLargerThan(0));3037  EXPECT_TRUE(Full.isSizeLargerThan(65535));3038  EXPECT_FALSE(Full.isSizeLargerThan(65536));3039 3040  EXPECT_TRUE(One.isSizeLargerThan(0));3041  EXPECT_FALSE(One.isSizeLargerThan(1));3042}3043 3044TEST_F(ConstantRangeTest, MakeMaskNotEqualRange) {3045  // Mask: 0b0001, C: 0b0001. MMNE() = [2, 1)3046  ConstantRange CR(APInt(4, 2), APInt(4, 1));3047  EXPECT_EQ(CR, ConstantRange::makeMaskNotEqualRange(APInt(4, 1), APInt(4, 1)));3048  EXPECT_NE(CR, ConstantRange::makeMaskNotEqualRange(APInt(4, 0),3049                                                     APInt(4, -1, true)));3050  EXPECT_TRUE(CR.contains(APInt(4, 7)));3051  EXPECT_TRUE(CR.contains(APInt(4, 15)));3052 3053  // Mask: 0b0100, C: 0b0100. MMNE() = [-8, 4)3054  ConstantRange CR2(APInt(4, -8, true), APInt(4, 4));3055  auto MMNE = ConstantRange::makeMaskNotEqualRange(APInt(4, 4), APInt(4, 4));3056  EXPECT_EQ(CR2, MMNE);3057  EXPECT_NE(ConstantRange::getNonEmpty(APInt(4, 0), APInt(4, -4, true)), MMNE);3058 3059  // CR: [-16, -8). MMNE() = [-8, -16)3060  ConstantRange CR3(APInt(8, 240), APInt(8, 248));3061  EXPECT_EQ(CR3.inverse(),3062            ConstantRange::makeMaskNotEqualRange(APInt(8, 248), APInt(8, 240)));3063 3064  // Mask: 0, C: 0b1111: unsatisfiable.3065  EXPECT_EQ(ConstantRange::getFull(4),3066            ConstantRange::makeMaskNotEqualRange(APInt(4, 0), APInt(4, 15)));3067}3068 3069TEST_F(ConstantRangeTest, MakeMaskNotEqualRangeExhaustive) {3070  unsigned Bits = 4;3071  unsigned Max = 1 << Bits;3072 3073  EnumerateAPInts(Bits, [&](const APInt &Mask) {3074    EnumerateAPInts(Bits, [&](const APInt &C) {3075      SmallBitVector Elems(Max);3076      for (unsigned N = 0; N < Max; ++N) {3077        APInt Num(Bits, N);3078        if ((Num & Mask) == C)3079          continue;3080        Elems.set(Num.getZExtValue());3081      }3082 3083      // Only test optimality with PreferSmallest. E.g., given Mask = 0b0001, C3084      // = 0b0001, a possible better range would be [0, 15) when preferring the3085      // smallest unsigned, however we conservatively return [2, 1).3086      TestRange(ConstantRange::makeMaskNotEqualRange(Mask, C), Elems,3087                PreferSmallest, {});3088    });3089  });3090}3091 3092} // anonymous namespace3093