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