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/IR/Instructions.h" 11 #include "llvm/IR/Operator.h" 12 #include "llvm/Support/KnownBits.h" 13 #include "gtest/gtest.h" 14 15 using namespace llvm; 16 17 namespace { 18 19 class ConstantRangeTest : public ::testing::Test { 20 protected: 21 static ConstantRange Full; 22 static ConstantRange Empty; 23 static ConstantRange One; 24 static ConstantRange Some; 25 static ConstantRange Wrap; 26 }; 27 28 ConstantRange ConstantRangeTest::Full(16, true); 29 ConstantRange ConstantRangeTest::Empty(16, false); 30 ConstantRange ConstantRangeTest::One(APInt(16, 0xa)); 31 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa)); 32 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa)); 33 34 TEST_F(ConstantRangeTest, Basics) { 35 EXPECT_TRUE(Full.isFullSet()); 36 EXPECT_FALSE(Full.isEmptySet()); 37 EXPECT_TRUE(Full.inverse().isEmptySet()); 38 EXPECT_FALSE(Full.isWrappedSet()); 39 EXPECT_TRUE(Full.contains(APInt(16, 0x0))); 40 EXPECT_TRUE(Full.contains(APInt(16, 0x9))); 41 EXPECT_TRUE(Full.contains(APInt(16, 0xa))); 42 EXPECT_TRUE(Full.contains(APInt(16, 0xaa9))); 43 EXPECT_TRUE(Full.contains(APInt(16, 0xaaa))); 44 45 EXPECT_FALSE(Empty.isFullSet()); 46 EXPECT_TRUE(Empty.isEmptySet()); 47 EXPECT_TRUE(Empty.inverse().isFullSet()); 48 EXPECT_FALSE(Empty.isWrappedSet()); 49 EXPECT_FALSE(Empty.contains(APInt(16, 0x0))); 50 EXPECT_FALSE(Empty.contains(APInt(16, 0x9))); 51 EXPECT_FALSE(Empty.contains(APInt(16, 0xa))); 52 EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9))); 53 EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa))); 54 55 EXPECT_FALSE(One.isFullSet()); 56 EXPECT_FALSE(One.isEmptySet()); 57 EXPECT_FALSE(One.isWrappedSet()); 58 EXPECT_FALSE(One.contains(APInt(16, 0x0))); 59 EXPECT_FALSE(One.contains(APInt(16, 0x9))); 60 EXPECT_TRUE(One.contains(APInt(16, 0xa))); 61 EXPECT_FALSE(One.contains(APInt(16, 0xaa9))); 62 EXPECT_FALSE(One.contains(APInt(16, 0xaaa))); 63 EXPECT_FALSE(One.inverse().contains(APInt(16, 0xa))); 64 65 EXPECT_FALSE(Some.isFullSet()); 66 EXPECT_FALSE(Some.isEmptySet()); 67 EXPECT_FALSE(Some.isWrappedSet()); 68 EXPECT_FALSE(Some.contains(APInt(16, 0x0))); 69 EXPECT_FALSE(Some.contains(APInt(16, 0x9))); 70 EXPECT_TRUE(Some.contains(APInt(16, 0xa))); 71 EXPECT_TRUE(Some.contains(APInt(16, 0xaa9))); 72 EXPECT_FALSE(Some.contains(APInt(16, 0xaaa))); 73 74 EXPECT_FALSE(Wrap.isFullSet()); 75 EXPECT_FALSE(Wrap.isEmptySet()); 76 EXPECT_TRUE(Wrap.isWrappedSet()); 77 EXPECT_TRUE(Wrap.contains(APInt(16, 0x0))); 78 EXPECT_TRUE(Wrap.contains(APInt(16, 0x9))); 79 EXPECT_FALSE(Wrap.contains(APInt(16, 0xa))); 80 EXPECT_FALSE(Wrap.contains(APInt(16, 0xaa9))); 81 EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa))); 82 } 83 84 TEST_F(ConstantRangeTest, Equality) { 85 EXPECT_EQ(Full, Full); 86 EXPECT_EQ(Empty, Empty); 87 EXPECT_EQ(One, One); 88 EXPECT_EQ(Some, Some); 89 EXPECT_EQ(Wrap, Wrap); 90 EXPECT_NE(Full, Empty); 91 EXPECT_NE(Full, One); 92 EXPECT_NE(Full, Some); 93 EXPECT_NE(Full, Wrap); 94 EXPECT_NE(Empty, One); 95 EXPECT_NE(Empty, Some); 96 EXPECT_NE(Empty, Wrap); 97 EXPECT_NE(One, Some); 98 EXPECT_NE(One, Wrap); 99 EXPECT_NE(Some, Wrap); 100 } 101 102 TEST_F(ConstantRangeTest, SingleElement) { 103 EXPECT_EQ(Full.getSingleElement(), static_cast<APInt *>(nullptr)); 104 EXPECT_EQ(Empty.getSingleElement(), static_cast<APInt *>(nullptr)); 105 EXPECT_EQ(Full.getSingleMissingElement(), static_cast<APInt *>(nullptr)); 106 EXPECT_EQ(Empty.getSingleMissingElement(), static_cast<APInt *>(nullptr)); 107 108 EXPECT_EQ(*One.getSingleElement(), APInt(16, 0xa)); 109 EXPECT_EQ(Some.getSingleElement(), static_cast<APInt *>(nullptr)); 110 EXPECT_EQ(Wrap.getSingleElement(), static_cast<APInt *>(nullptr)); 111 112 EXPECT_EQ(One.getSingleMissingElement(), static_cast<APInt *>(nullptr)); 113 EXPECT_EQ(Some.getSingleMissingElement(), static_cast<APInt *>(nullptr)); 114 115 ConstantRange OneInverse = One.inverse(); 116 EXPECT_EQ(*OneInverse.getSingleMissingElement(), *One.getSingleElement()); 117 118 EXPECT_FALSE(Full.isSingleElement()); 119 EXPECT_FALSE(Empty.isSingleElement()); 120 EXPECT_TRUE(One.isSingleElement()); 121 EXPECT_FALSE(Some.isSingleElement()); 122 EXPECT_FALSE(Wrap.isSingleElement()); 123 } 124 125 TEST_F(ConstantRangeTest, GetSetSize) { 126 EXPECT_EQ(Full.getSetSize(), APInt(17, 65536)); 127 EXPECT_EQ(Empty.getSetSize(), APInt(17, 0)); 128 EXPECT_EQ(One.getSetSize(), APInt(17, 1)); 129 EXPECT_EQ(Some.getSetSize(), APInt(17, 0xaa0)); 130 131 ConstantRange Wrap(APInt(4, 7), APInt(4, 3)); 132 ConstantRange Wrap2(APInt(4, 8), APInt(4, 7)); 133 EXPECT_EQ(Wrap.getSetSize(), APInt(5, 12)); 134 EXPECT_EQ(Wrap2.getSetSize(), APInt(5, 15)); 135 } 136 137 TEST_F(ConstantRangeTest, GetMinsAndMaxes) { 138 EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX)); 139 EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa)); 140 EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9)); 141 EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX)); 142 143 EXPECT_EQ(Full.getUnsignedMin(), APInt(16, 0)); 144 EXPECT_EQ(One.getUnsignedMin(), APInt(16, 0xa)); 145 EXPECT_EQ(Some.getUnsignedMin(), APInt(16, 0xa)); 146 EXPECT_EQ(Wrap.getUnsignedMin(), APInt(16, 0)); 147 148 EXPECT_EQ(Full.getSignedMax(), APInt(16, INT16_MAX)); 149 EXPECT_EQ(One.getSignedMax(), APInt(16, 0xa)); 150 EXPECT_EQ(Some.getSignedMax(), APInt(16, 0xaa9)); 151 EXPECT_EQ(Wrap.getSignedMax(), APInt(16, INT16_MAX)); 152 153 EXPECT_EQ(Full.getSignedMin(), APInt(16, (uint64_t)INT16_MIN)); 154 EXPECT_EQ(One.getSignedMin(), APInt(16, 0xa)); 155 EXPECT_EQ(Some.getSignedMin(), APInt(16, 0xa)); 156 EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint64_t)INT16_MIN)); 157 158 // Found by Klee 159 EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(), 160 APInt(4, 7)); 161 } 162 163 TEST_F(ConstantRangeTest, SignWrapped) { 164 EXPECT_TRUE(Full.isSignWrappedSet()); 165 EXPECT_FALSE(Empty.isSignWrappedSet()); 166 EXPECT_FALSE(One.isSignWrappedSet()); 167 EXPECT_FALSE(Some.isSignWrappedSet()); 168 EXPECT_TRUE(Wrap.isSignWrappedSet()); 169 170 EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet()); 171 EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet()); 172 EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet()); 173 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet()); 174 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet()); 175 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet()); 176 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet()); 177 } 178 179 TEST_F(ConstantRangeTest, Trunc) { 180 ConstantRange TFull = Full.truncate(10); 181 ConstantRange TEmpty = Empty.truncate(10); 182 ConstantRange TOne = One.truncate(10); 183 ConstantRange TSome = Some.truncate(10); 184 ConstantRange TWrap = Wrap.truncate(10); 185 EXPECT_TRUE(TFull.isFullSet()); 186 EXPECT_TRUE(TEmpty.isEmptySet()); 187 EXPECT_EQ(TOne, ConstantRange(One.getLower().trunc(10), 188 One.getUpper().trunc(10))); 189 EXPECT_TRUE(TSome.isFullSet()); 190 EXPECT_TRUE(TWrap.isFullSet()); 191 192 // trunc([2, 5), 3->2) = [2, 1) 193 ConstantRange TwoFive(APInt(3, 2), APInt(3, 5)); 194 EXPECT_EQ(TwoFive.truncate(2), ConstantRange(APInt(2, 2), APInt(2, 1))); 195 196 // trunc([2, 6), 3->2) = full 197 ConstantRange TwoSix(APInt(3, 2), APInt(3, 6)); 198 EXPECT_TRUE(TwoSix.truncate(2).isFullSet()); 199 200 // trunc([5, 7), 3->2) = [1, 3) 201 ConstantRange FiveSeven(APInt(3, 5), APInt(3, 7)); 202 EXPECT_EQ(FiveSeven.truncate(2), ConstantRange(APInt(2, 1), APInt(2, 3))); 203 204 // trunc([7, 1), 3->2) = [3, 1) 205 ConstantRange SevenOne(APInt(3, 7), APInt(3, 1)); 206 EXPECT_EQ(SevenOne.truncate(2), ConstantRange(APInt(2, 3), APInt(2, 1))); 207 } 208 209 TEST_F(ConstantRangeTest, ZExt) { 210 ConstantRange ZFull = Full.zeroExtend(20); 211 ConstantRange ZEmpty = Empty.zeroExtend(20); 212 ConstantRange ZOne = One.zeroExtend(20); 213 ConstantRange ZSome = Some.zeroExtend(20); 214 ConstantRange ZWrap = Wrap.zeroExtend(20); 215 EXPECT_EQ(ZFull, ConstantRange(APInt(20, 0), APInt(20, 0x10000))); 216 EXPECT_TRUE(ZEmpty.isEmptySet()); 217 EXPECT_EQ(ZOne, ConstantRange(One.getLower().zext(20), 218 One.getUpper().zext(20))); 219 EXPECT_EQ(ZSome, ConstantRange(Some.getLower().zext(20), 220 Some.getUpper().zext(20))); 221 EXPECT_EQ(ZWrap, ConstantRange(APInt(20, 0), APInt(20, 0x10000))); 222 223 // zext([5, 0), 3->7) = [5, 8) 224 ConstantRange FiveZero(APInt(3, 5), APInt(3, 0)); 225 EXPECT_EQ(FiveZero.zeroExtend(7), ConstantRange(APInt(7, 5), APInt(7, 8))); 226 } 227 228 TEST_F(ConstantRangeTest, SExt) { 229 ConstantRange SFull = Full.signExtend(20); 230 ConstantRange SEmpty = Empty.signExtend(20); 231 ConstantRange SOne = One.signExtend(20); 232 ConstantRange SSome = Some.signExtend(20); 233 ConstantRange SWrap = Wrap.signExtend(20); 234 EXPECT_EQ(SFull, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true), 235 APInt(20, INT16_MAX + 1, true))); 236 EXPECT_TRUE(SEmpty.isEmptySet()); 237 EXPECT_EQ(SOne, ConstantRange(One.getLower().sext(20), 238 One.getUpper().sext(20))); 239 EXPECT_EQ(SSome, ConstantRange(Some.getLower().sext(20), 240 Some.getUpper().sext(20))); 241 EXPECT_EQ(SWrap, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true), 242 APInt(20, INT16_MAX + 1, true))); 243 244 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16), 245 ConstantRange(APInt(16, -128), APInt(16, 128))); 246 247 EXPECT_EQ(ConstantRange(APInt(16, 0x0200), APInt(16, 0x8000)).signExtend(19), 248 ConstantRange(APInt(19, 0x0200), APInt(19, 0x8000))); 249 } 250 251 TEST_F(ConstantRangeTest, IntersectWith) { 252 EXPECT_EQ(Empty.intersectWith(Full), Empty); 253 EXPECT_EQ(Empty.intersectWith(Empty), Empty); 254 EXPECT_EQ(Empty.intersectWith(One), Empty); 255 EXPECT_EQ(Empty.intersectWith(Some), Empty); 256 EXPECT_EQ(Empty.intersectWith(Wrap), Empty); 257 EXPECT_EQ(Full.intersectWith(Full), Full); 258 EXPECT_EQ(Some.intersectWith(Some), Some); 259 EXPECT_EQ(Some.intersectWith(One), One); 260 EXPECT_EQ(Full.intersectWith(One), One); 261 EXPECT_EQ(Full.intersectWith(Some), Some); 262 EXPECT_EQ(Some.intersectWith(Wrap), Empty); 263 EXPECT_EQ(One.intersectWith(Wrap), Empty); 264 EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One)); 265 266 // Klee generated testcase from PR4545. 267 // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like 268 // 01..4.6789ABCDEF where the dots represent values not in the intersection. 269 ConstantRange LHS(APInt(16, 4), APInt(16, 2)); 270 ConstantRange RHS(APInt(16, 6), APInt(16, 5)); 271 EXPECT_TRUE(LHS.intersectWith(RHS) == LHS); 272 273 // previous bug: intersection of [min, 3) and [2, max) should be 2 274 LHS = ConstantRange(APInt(32, -2147483646), APInt(32, 3)); 275 RHS = ConstantRange(APInt(32, 2), APInt(32, 2147483646)); 276 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2))); 277 278 // [2, 0) /\ [4, 3) = [2, 0) 279 LHS = ConstantRange(APInt(32, 2), APInt(32, 0)); 280 RHS = ConstantRange(APInt(32, 4), APInt(32, 3)); 281 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2), APInt(32, 0))); 282 283 // [2, 0) /\ [4, 2) = [4, 0) 284 LHS = ConstantRange(APInt(32, 2), APInt(32, 0)); 285 RHS = ConstantRange(APInt(32, 4), APInt(32, 2)); 286 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0))); 287 288 // [4, 2) /\ [5, 1) = [5, 1) 289 LHS = ConstantRange(APInt(32, 4), APInt(32, 2)); 290 RHS = ConstantRange(APInt(32, 5), APInt(32, 1)); 291 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 5), APInt(32, 1))); 292 293 // [2, 0) /\ [7, 4) = [7, 4) 294 LHS = ConstantRange(APInt(32, 2), APInt(32, 0)); 295 RHS = ConstantRange(APInt(32, 7), APInt(32, 4)); 296 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 4))); 297 298 // [4, 2) /\ [1, 0) = [1, 0) 299 LHS = ConstantRange(APInt(32, 4), APInt(32, 2)); 300 RHS = ConstantRange(APInt(32, 1), APInt(32, 0)); 301 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2))); 302 303 // [15, 0) /\ [7, 6) = [15, 0) 304 LHS = ConstantRange(APInt(32, 15), APInt(32, 0)); 305 RHS = ConstantRange(APInt(32, 7), APInt(32, 6)); 306 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0))); 307 } 308 309 TEST_F(ConstantRangeTest, UnionWith) { 310 EXPECT_EQ(Wrap.unionWith(One), 311 ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb))); 312 EXPECT_EQ(One.unionWith(Wrap), Wrap.unionWith(One)); 313 EXPECT_EQ(Empty.unionWith(Empty), Empty); 314 EXPECT_EQ(Full.unionWith(Full), Full); 315 EXPECT_EQ(Some.unionWith(Wrap), Full); 316 317 // PR4545 318 EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith( 319 ConstantRange(APInt(16, 0), APInt(16, 8))), 320 ConstantRange(APInt(16, 14), APInt(16, 8))); 321 EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith( 322 ConstantRange(APInt(16, 4), APInt(16, 0))), 323 ConstantRange::getFull(16)); 324 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith( 325 ConstantRange(APInt(16, 2), APInt(16, 1))), 326 ConstantRange::getFull(16)); 327 } 328 329 TEST_F(ConstantRangeTest, SetDifference) { 330 EXPECT_EQ(Full.difference(Empty), Full); 331 EXPECT_EQ(Full.difference(Full), Empty); 332 EXPECT_EQ(Empty.difference(Empty), Empty); 333 EXPECT_EQ(Empty.difference(Full), Empty); 334 335 ConstantRange A(APInt(16, 3), APInt(16, 7)); 336 ConstantRange B(APInt(16, 5), APInt(16, 9)); 337 ConstantRange C(APInt(16, 3), APInt(16, 5)); 338 ConstantRange D(APInt(16, 7), APInt(16, 9)); 339 ConstantRange E(APInt(16, 5), APInt(16, 4)); 340 ConstantRange F(APInt(16, 7), APInt(16, 3)); 341 EXPECT_EQ(A.difference(B), C); 342 EXPECT_EQ(B.difference(A), D); 343 EXPECT_EQ(E.difference(A), F); 344 } 345 346 TEST_F(ConstantRangeTest, SubtractAPInt) { 347 EXPECT_EQ(Full.subtract(APInt(16, 4)), Full); 348 EXPECT_EQ(Empty.subtract(APInt(16, 4)), Empty); 349 EXPECT_EQ(Some.subtract(APInt(16, 4)), 350 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6))); 351 EXPECT_EQ(Wrap.subtract(APInt(16, 4)), 352 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6))); 353 EXPECT_EQ(One.subtract(APInt(16, 4)), 354 ConstantRange(APInt(16, 0x6))); 355 } 356 357 TEST_F(ConstantRangeTest, Add) { 358 EXPECT_EQ(Full.add(APInt(16, 4)), Full); 359 EXPECT_EQ(Full.add(Full), Full); 360 EXPECT_EQ(Full.add(Empty), Empty); 361 EXPECT_EQ(Full.add(One), Full); 362 EXPECT_EQ(Full.add(Some), Full); 363 EXPECT_EQ(Full.add(Wrap), Full); 364 EXPECT_EQ(Empty.add(Empty), Empty); 365 EXPECT_EQ(Empty.add(One), Empty); 366 EXPECT_EQ(Empty.add(Some), Empty); 367 EXPECT_EQ(Empty.add(Wrap), Empty); 368 EXPECT_EQ(Empty.add(APInt(16, 4)), Empty); 369 EXPECT_EQ(Some.add(APInt(16, 4)), 370 ConstantRange(APInt(16, 0xe), APInt(16, 0xaae))); 371 EXPECT_EQ(Wrap.add(APInt(16, 4)), 372 ConstantRange(APInt(16, 0xaae), APInt(16, 0xe))); 373 EXPECT_EQ(One.add(APInt(16, 4)), 374 ConstantRange(APInt(16, 0xe))); 375 } 376 377 TEST_F(ConstantRangeTest, AddWithNoSignedWrap) { 378 EXPECT_EQ(Empty.addWithNoSignedWrap(APInt(16, 1)), Empty); 379 EXPECT_EQ(Full.addWithNoSignedWrap(APInt(16, 1)), 380 ConstantRange(APInt(16, INT16_MIN+1), APInt(16, INT16_MIN))); 381 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)).addWithNoSignedWrap(APInt(8, 10)), 382 ConstantRange(APInt(8, -40), APInt(8, 60))); 383 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 120)).addWithNoSignedWrap(APInt(8, 10)), 384 ConstantRange(APInt(8, -40), APInt(8, INT8_MIN))); 385 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10)).addWithNoSignedWrap(APInt(8, 5)), 386 ConstantRange(APInt(8, 125), APInt(8, -5))); 387 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, 10)), 388 ConstantRange(APInt(8, INT8_MIN+10), APInt(8, -110))); 389 390 EXPECT_EQ(Empty.addWithNoSignedWrap(APInt(16, -1)), Empty); 391 EXPECT_EQ(Full.addWithNoSignedWrap(APInt(16, -1)), 392 ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX))); 393 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)), 394 ConstantRange(APInt(8, -60), APInt(8, 40))); 395 EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)), 396 ConstantRange(APInt(8, INT8_MIN), APInt(8, 40))); 397 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -5)), 398 ConstantRange(APInt(8, 115), APInt(8, -125))); 399 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -10)), 400 ConstantRange(APInt(8, 110), APInt(8, INT8_MIN-10))); 401 } 402 403 TEST_F(ConstantRangeTest, Sub) { 404 EXPECT_EQ(Full.sub(APInt(16, 4)), Full); 405 EXPECT_EQ(Full.sub(Full), Full); 406 EXPECT_EQ(Full.sub(Empty), Empty); 407 EXPECT_EQ(Full.sub(One), Full); 408 EXPECT_EQ(Full.sub(Some), Full); 409 EXPECT_EQ(Full.sub(Wrap), Full); 410 EXPECT_EQ(Empty.sub(Empty), Empty); 411 EXPECT_EQ(Empty.sub(One), Empty); 412 EXPECT_EQ(Empty.sub(Some), Empty); 413 EXPECT_EQ(Empty.sub(Wrap), Empty); 414 EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty); 415 EXPECT_EQ(Some.sub(APInt(16, 4)), 416 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6))); 417 EXPECT_EQ(Some.sub(Some), 418 ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0))); 419 EXPECT_EQ(Wrap.sub(APInt(16, 4)), 420 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6))); 421 EXPECT_EQ(One.sub(APInt(16, 4)), 422 ConstantRange(APInt(16, 0x6))); 423 } 424 425 TEST_F(ConstantRangeTest, Multiply) { 426 EXPECT_EQ(Full.multiply(Full), Full); 427 EXPECT_EQ(Full.multiply(Empty), Empty); 428 EXPECT_EQ(Full.multiply(One), Full); 429 EXPECT_EQ(Full.multiply(Some), Full); 430 EXPECT_EQ(Full.multiply(Wrap), Full); 431 EXPECT_EQ(Empty.multiply(Empty), Empty); 432 EXPECT_EQ(Empty.multiply(One), Empty); 433 EXPECT_EQ(Empty.multiply(Some), Empty); 434 EXPECT_EQ(Empty.multiply(Wrap), Empty); 435 EXPECT_EQ(One.multiply(One), ConstantRange(APInt(16, 0xa*0xa), 436 APInt(16, 0xa*0xa + 1))); 437 EXPECT_EQ(One.multiply(Some), ConstantRange(APInt(16, 0xa*0xa), 438 APInt(16, 0xa*0xaa9 + 1))); 439 EXPECT_EQ(One.multiply(Wrap), Full); 440 EXPECT_EQ(Some.multiply(Some), Full); 441 EXPECT_EQ(Some.multiply(Wrap), Full); 442 EXPECT_EQ(Wrap.multiply(Wrap), Full); 443 444 ConstantRange Zero(APInt(16, 0)); 445 EXPECT_EQ(Zero.multiply(Full), Zero); 446 EXPECT_EQ(Zero.multiply(Some), Zero); 447 EXPECT_EQ(Zero.multiply(Wrap), Zero); 448 EXPECT_EQ(Full.multiply(Zero), Zero); 449 EXPECT_EQ(Some.multiply(Zero), Zero); 450 EXPECT_EQ(Wrap.multiply(Zero), Zero); 451 452 // http://llvm.org/PR4545 453 EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply( 454 ConstantRange(APInt(4, 6), APInt(4, 2))), 455 ConstantRange(4, /*isFullSet=*/true)); 456 457 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply( 458 ConstantRange(APInt(8, 252), APInt(8, 4))), 459 ConstantRange(APInt(8, 250), APInt(8, 9))); 460 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply( 461 ConstantRange(APInt(8, 2), APInt(8, 4))), 462 ConstantRange(APInt(8, 250), APInt(8, 253))); 463 464 // TODO: This should be return [-2, 0] 465 EXPECT_EQ(ConstantRange(APInt(8, -2)).multiply( 466 ConstantRange(APInt(8, 0), APInt(8, 2))), 467 ConstantRange(APInt(8, -2), APInt(8, 1))); 468 } 469 470 TEST_F(ConstantRangeTest, UMax) { 471 EXPECT_EQ(Full.umax(Full), Full); 472 EXPECT_EQ(Full.umax(Empty), Empty); 473 EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0))); 474 EXPECT_EQ(Full.umax(Wrap), Full); 475 EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0))); 476 EXPECT_EQ(Empty.umax(Empty), Empty); 477 EXPECT_EQ(Empty.umax(Some), Empty); 478 EXPECT_EQ(Empty.umax(Wrap), Empty); 479 EXPECT_EQ(Empty.umax(One), Empty); 480 EXPECT_EQ(Some.umax(Some), Some); 481 EXPECT_EQ(Some.umax(Wrap), ConstantRange(APInt(16, 0xa), APInt(16, 0))); 482 EXPECT_EQ(Some.umax(One), Some); 483 // TODO: ConstantRange is currently over-conservative here. 484 EXPECT_EQ(Wrap.umax(Wrap), Full); 485 EXPECT_EQ(Wrap.umax(One), ConstantRange(APInt(16, 0xa), APInt(16, 0))); 486 EXPECT_EQ(One.umax(One), One); 487 } 488 489 TEST_F(ConstantRangeTest, SMax) { 490 EXPECT_EQ(Full.smax(Full), Full); 491 EXPECT_EQ(Full.smax(Empty), Empty); 492 EXPECT_EQ(Full.smax(Some), ConstantRange(APInt(16, 0xa), 493 APInt::getSignedMinValue(16))); 494 EXPECT_EQ(Full.smax(Wrap), Full); 495 EXPECT_EQ(Full.smax(One), ConstantRange(APInt(16, 0xa), 496 APInt::getSignedMinValue(16))); 497 EXPECT_EQ(Empty.smax(Empty), Empty); 498 EXPECT_EQ(Empty.smax(Some), Empty); 499 EXPECT_EQ(Empty.smax(Wrap), Empty); 500 EXPECT_EQ(Empty.smax(One), Empty); 501 EXPECT_EQ(Some.smax(Some), Some); 502 EXPECT_EQ(Some.smax(Wrap), ConstantRange(APInt(16, 0xa), 503 APInt(16, (uint64_t)INT16_MIN))); 504 EXPECT_EQ(Some.smax(One), Some); 505 EXPECT_EQ(Wrap.smax(One), ConstantRange(APInt(16, 0xa), 506 APInt(16, (uint64_t)INT16_MIN))); 507 EXPECT_EQ(One.smax(One), One); 508 } 509 510 TEST_F(ConstantRangeTest, UMin) { 511 EXPECT_EQ(Full.umin(Full), Full); 512 EXPECT_EQ(Full.umin(Empty), Empty); 513 EXPECT_EQ(Full.umin(Some), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 514 EXPECT_EQ(Full.umin(Wrap), Full); 515 EXPECT_EQ(Empty.umin(Empty), Empty); 516 EXPECT_EQ(Empty.umin(Some), Empty); 517 EXPECT_EQ(Empty.umin(Wrap), Empty); 518 EXPECT_EQ(Empty.umin(One), Empty); 519 EXPECT_EQ(Some.umin(Some), Some); 520 EXPECT_EQ(Some.umin(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 521 EXPECT_EQ(Some.umin(One), One); 522 // TODO: ConstantRange is currently over-conservative here. 523 EXPECT_EQ(Wrap.umin(Wrap), Full); 524 EXPECT_EQ(Wrap.umin(One), ConstantRange(APInt(16, 0), APInt(16, 0xb))); 525 EXPECT_EQ(One.umin(One), One); 526 } 527 528 TEST_F(ConstantRangeTest, SMin) { 529 EXPECT_EQ(Full.smin(Full), Full); 530 EXPECT_EQ(Full.smin(Empty), Empty); 531 EXPECT_EQ(Full.smin(Some), ConstantRange(APInt(16, (uint64_t)INT16_MIN), 532 APInt(16, 0xaaa))); 533 EXPECT_EQ(Full.smin(Wrap), Full); 534 EXPECT_EQ(Empty.smin(Empty), Empty); 535 EXPECT_EQ(Empty.smin(Some), Empty); 536 EXPECT_EQ(Empty.smin(Wrap), Empty); 537 EXPECT_EQ(Empty.smin(One), Empty); 538 EXPECT_EQ(Some.smin(Some), Some); 539 EXPECT_EQ(Some.smin(Wrap), ConstantRange(APInt(16, (uint64_t)INT16_MIN), 540 APInt(16, 0xaaa))); 541 EXPECT_EQ(Some.smin(One), One); 542 // TODO: ConstantRange is currently over-conservative here. 543 EXPECT_EQ(Wrap.smin(Wrap), Full); 544 EXPECT_EQ(Wrap.smin(One), ConstantRange(APInt(16, (uint64_t)INT16_MIN), 545 APInt(16, 0xb))); 546 EXPECT_EQ(One.smin(One), One); 547 } 548 549 TEST_F(ConstantRangeTest, UDiv) { 550 EXPECT_EQ(Full.udiv(Full), Full); 551 EXPECT_EQ(Full.udiv(Empty), Empty); 552 EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0), 553 APInt(16, 0xffff / 0xa + 1))); 554 EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0), 555 APInt(16, 0xffff / 0xa + 1))); 556 EXPECT_EQ(Full.udiv(Wrap), Full); 557 EXPECT_EQ(Empty.udiv(Empty), Empty); 558 EXPECT_EQ(Empty.udiv(One), Empty); 559 EXPECT_EQ(Empty.udiv(Some), Empty); 560 EXPECT_EQ(Empty.udiv(Wrap), Empty); 561 EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1))); 562 EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2))); 563 EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb))); 564 EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111))); 565 EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 566 EXPECT_EQ(Wrap.udiv(Wrap), Full); 567 } 568 569 TEST_F(ConstantRangeTest, Shl) { 570 EXPECT_EQ(Full.shl(Full), Full); 571 EXPECT_EQ(Full.shl(Empty), Empty); 572 EXPECT_EQ(Full.shl(One), Full); // TODO: [0, (-1 << 0xa) + 1) 573 EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1) 574 EXPECT_EQ(Full.shl(Wrap), Full); 575 EXPECT_EQ(Empty.shl(Empty), Empty); 576 EXPECT_EQ(Empty.shl(One), Empty); 577 EXPECT_EQ(Empty.shl(Some), Empty); 578 EXPECT_EQ(Empty.shl(Wrap), Empty); 579 EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa), 580 APInt(16, (0xa << 0xa) + 1))); 581 EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0) 582 EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1) 583 EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01) 584 EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1) 585 EXPECT_EQ(Wrap.shl(Wrap), Full); 586 } 587 588 TEST_F(ConstantRangeTest, Lshr) { 589 EXPECT_EQ(Full.lshr(Full), Full); 590 EXPECT_EQ(Full.lshr(Empty), Empty); 591 EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0), 592 APInt(16, (0xffff >> 0xa) + 1))); 593 EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0), 594 APInt(16, (0xffff >> 0xa) + 1))); 595 EXPECT_EQ(Full.lshr(Wrap), Full); 596 EXPECT_EQ(Empty.lshr(Empty), Empty); 597 EXPECT_EQ(Empty.lshr(One), Empty); 598 EXPECT_EQ(Empty.lshr(Some), Empty); 599 EXPECT_EQ(Empty.lshr(Wrap), Empty); 600 EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0))); 601 EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0))); 602 EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb))); 603 EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0), 604 APInt(16, (0xaaa >> 0xa) + 1))); 605 EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 606 EXPECT_EQ(Wrap.lshr(Wrap), Full); 607 } 608 609 TEST_F(ConstantRangeTest, Ashr) { 610 EXPECT_EQ(Full.ashr(Full), Full); 611 EXPECT_EQ(Full.ashr(Empty), Empty); 612 EXPECT_EQ(Full.ashr(One), ConstantRange(APInt(16, 0xffe0), 613 APInt(16, (0x7fff >> 0xa) + 1 ))); 614 ConstantRange Small(APInt(16, 0xa), APInt(16, 0xb)); 615 EXPECT_EQ(Full.ashr(Small), ConstantRange(APInt(16, 0xffe0), 616 APInt(16, (0x7fff >> 0xa) + 1 ))); 617 EXPECT_EQ(Full.ashr(Some), ConstantRange(APInt(16, 0xffe0), 618 APInt(16, (0x7fff >> 0xa) + 1 ))); 619 EXPECT_EQ(Full.ashr(Wrap), Full); 620 EXPECT_EQ(Empty.ashr(Empty), Empty); 621 EXPECT_EQ(Empty.ashr(One), Empty); 622 EXPECT_EQ(Empty.ashr(Some), Empty); 623 EXPECT_EQ(Empty.ashr(Wrap), Empty); 624 EXPECT_EQ(One.ashr(One), ConstantRange(APInt(16, 0))); 625 EXPECT_EQ(One.ashr(Some), ConstantRange(APInt(16, 0))); 626 EXPECT_EQ(One.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb))); 627 EXPECT_EQ(Some.ashr(Some), ConstantRange(APInt(16, 0), 628 APInt(16, (0xaaa >> 0xa) + 1))); 629 EXPECT_EQ(Some.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 630 EXPECT_EQ(Wrap.ashr(Wrap), Full); 631 ConstantRange Neg(APInt(16, 0xf3f0, true), APInt(16, 0xf7f8, true)); 632 EXPECT_EQ(Neg.ashr(Small), ConstantRange(APInt(16, 0xfffc, true), 633 APInt(16, 0xfffe, true))); 634 } 635 636 TEST(ConstantRange, MakeAllowedICmpRegion) { 637 // PR8250 638 ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32)); 639 EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax) 640 .isEmptySet()); 641 } 642 643 TEST(ConstantRange, MakeSatisfyingICmpRegion) { 644 ConstantRange LowHalf(APInt(8, 0), APInt(8, 128)); 645 ConstantRange HighHalf(APInt(8, 128), APInt(8, 0)); 646 ConstantRange EmptySet(8, /* isFullSet = */ false); 647 648 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf), 649 HighHalf); 650 651 EXPECT_EQ( 652 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf), 653 LowHalf); 654 655 EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ, 656 HighHalf).isEmptySet()); 657 658 ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200)); 659 660 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT, 661 UnsignedSample), 662 ConstantRange(APInt(8, 0), APInt(8, 5))); 663 664 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE, 665 UnsignedSample), 666 ConstantRange(APInt(8, 0), APInt(8, 6))); 667 668 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT, 669 UnsignedSample), 670 ConstantRange(APInt(8, 200), APInt(8, 0))); 671 672 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE, 673 UnsignedSample), 674 ConstantRange(APInt(8, 199), APInt(8, 0))); 675 676 ConstantRange SignedSample(APInt(8, -5), APInt(8, 5)); 677 678 EXPECT_EQ( 679 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample), 680 ConstantRange(APInt(8, -128), APInt(8, -5))); 681 682 EXPECT_EQ( 683 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample), 684 ConstantRange(APInt(8, -128), APInt(8, -4))); 685 686 EXPECT_EQ( 687 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample), 688 ConstantRange(APInt(8, 5), APInt(8, -128))); 689 690 EXPECT_EQ( 691 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample), 692 ConstantRange(APInt(8, 4), APInt(8, -128))); 693 } 694 695 TEST(ConstantRange, MakeGuaranteedNoWrapRegion) { 696 const int IntMin4Bits = 8; 697 const int IntMax4Bits = 7; 698 typedef OverflowingBinaryOperator OBO; 699 700 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) { 701 APInt C(4, Const, true /* = isSigned */); 702 703 auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 704 Instruction::Add, C, OBO::NoUnsignedWrap); 705 706 EXPECT_FALSE(NUWRegion.isEmptySet()); 707 708 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 709 Instruction::Add, C, OBO::NoSignedWrap); 710 711 EXPECT_FALSE(NSWRegion.isEmptySet()); 712 713 auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion( 714 Instruction::Add, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap); 715 716 EXPECT_FALSE(NoWrapRegion.isEmptySet()); 717 EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion)); 718 719 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E; 720 ++I) { 721 bool Overflow = false; 722 (void)I.uadd_ov(C, Overflow); 723 EXPECT_FALSE(Overflow); 724 } 725 726 for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E; 727 ++I) { 728 bool Overflow = false; 729 (void)I.sadd_ov(C, Overflow); 730 EXPECT_FALSE(Overflow); 731 } 732 733 for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E; 734 ++I) { 735 bool Overflow = false; 736 737 (void)I.sadd_ov(C, Overflow); 738 EXPECT_FALSE(Overflow); 739 740 (void)I.uadd_ov(C, Overflow); 741 EXPECT_FALSE(Overflow); 742 } 743 } 744 745 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) { 746 APInt C(4, Const, true /* = isSigned */); 747 748 auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 749 Instruction::Sub, C, OBO::NoUnsignedWrap); 750 751 EXPECT_FALSE(NUWRegion.isEmptySet()); 752 753 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 754 Instruction::Sub, C, OBO::NoSignedWrap); 755 756 EXPECT_FALSE(NSWRegion.isEmptySet()); 757 758 auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion( 759 Instruction::Sub, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap); 760 761 EXPECT_FALSE(NoWrapRegion.isEmptySet()); 762 EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion)); 763 764 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E; 765 ++I) { 766 bool Overflow = false; 767 (void)I.usub_ov(C, Overflow); 768 EXPECT_FALSE(Overflow); 769 } 770 771 for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E; 772 ++I) { 773 bool Overflow = false; 774 (void)I.ssub_ov(C, Overflow); 775 EXPECT_FALSE(Overflow); 776 } 777 778 for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E; 779 ++I) { 780 bool Overflow = false; 781 782 (void)I.ssub_ov(C, Overflow); 783 EXPECT_FALSE(Overflow); 784 785 (void)I.usub_ov(C, Overflow); 786 EXPECT_FALSE(Overflow); 787 } 788 } 789 790 auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 791 Instruction::Add, ConstantRange(32, /* isFullSet = */ true), 792 OBO::NoSignedWrap); 793 EXPECT_TRUE(NSWForAllValues.isSingleElement() && 794 NSWForAllValues.getSingleElement()->isMinValue()); 795 796 NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 797 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true), 798 OBO::NoSignedWrap); 799 EXPECT_TRUE(NSWForAllValues.isSingleElement() && 800 NSWForAllValues.getSingleElement()->isMaxValue()); 801 802 auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 803 Instruction::Add, ConstantRange(32, /* isFullSet = */ true), 804 OBO::NoUnsignedWrap); 805 EXPECT_TRUE(NUWForAllValues.isSingleElement() && 806 NUWForAllValues.getSingleElement()->isMinValue()); 807 808 NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 809 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true), 810 OBO::NoUnsignedWrap); 811 EXPECT_TRUE(NUWForAllValues.isSingleElement() && 812 NUWForAllValues.getSingleElement()->isMaxValue()); 813 814 auto NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 815 Instruction::Add, ConstantRange(32, /* isFullSet = */ true), 816 OBO::NoUnsignedWrap | OBO::NoSignedWrap); 817 EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() && 818 NUWAndNSWForAllValues.getSingleElement()->isMinValue()); 819 820 NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 821 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true), 822 OBO::NoUnsignedWrap | OBO::NoSignedWrap); 823 EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() && 824 NUWAndNSWForAllValues.getSingleElement()->isMaxValue()); 825 826 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 827 Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet()); 828 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 829 Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet()); 830 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 831 Instruction::Add, APInt(32, 0), 832 OBO::NoUnsignedWrap | OBO::NoSignedWrap).isFullSet()); 833 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 834 Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet()); 835 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 836 Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet()); 837 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 838 Instruction::Sub, APInt(32, 0), 839 OBO::NoUnsignedWrap | OBO::NoSignedWrap).isFullSet()); 840 841 ConstantRange OneToFive(APInt(32, 1), APInt(32, 6)); 842 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 843 Instruction::Add, OneToFive, OBO::NoSignedWrap), 844 ConstantRange(APInt::getSignedMinValue(32), 845 APInt::getSignedMaxValue(32) - 4)); 846 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 847 Instruction::Add, OneToFive, OBO::NoUnsignedWrap), 848 ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5)); 849 EXPECT_EQ( 850 ConstantRange::makeGuaranteedNoWrapRegion( 851 Instruction::Add, OneToFive, OBO::NoUnsignedWrap | OBO::NoSignedWrap), 852 ConstantRange(APInt::getMinValue(32), APInt::getSignedMaxValue(32) - 4)); 853 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 854 Instruction::Sub, OneToFive, OBO::NoSignedWrap), 855 ConstantRange(APInt::getSignedMinValue(32) + 5, 856 APInt::getSignedMinValue(32))); 857 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 858 Instruction::Sub, OneToFive, OBO::NoUnsignedWrap), 859 ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32))); 860 EXPECT_EQ( 861 ConstantRange::makeGuaranteedNoWrapRegion( 862 Instruction::Sub, OneToFive, OBO::NoUnsignedWrap | OBO::NoSignedWrap), 863 ConstantRange(APInt::getMinValue(32) + 5, APInt::getSignedMinValue(32))); 864 865 ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1)); 866 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 867 Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap), 868 ConstantRange(APInt::getSignedMinValue(32) + 5, 869 APInt::getSignedMinValue(32))); 870 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 871 Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap), 872 ConstantRange(APInt(32, 0), APInt(32, 2))); 873 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 874 Instruction::Add, MinusFiveToMinusTwo, 875 OBO::NoUnsignedWrap | OBO::NoSignedWrap), 876 ConstantRange(APInt(32, 0), APInt(32, 2))); 877 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 878 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap), 879 ConstantRange(APInt::getSignedMinValue(32), 880 APInt::getSignedMaxValue(32) - 4)); 881 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 882 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap), 883 ConstantRange(APInt::getMaxValue(32) - 1, 884 APInt::getMinValue(32))); 885 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 886 Instruction::Sub, MinusFiveToMinusTwo, 887 OBO::NoUnsignedWrap | OBO::NoSignedWrap), 888 ConstantRange(APInt::getMaxValue(32) - 1, 889 APInt::getMinValue(32))); 890 891 ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2)); 892 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 893 Instruction::Add, MinusOneToOne, OBO::NoSignedWrap), 894 ConstantRange(APInt::getSignedMinValue(32) + 1, 895 APInt::getSignedMinValue(32) - 1)); 896 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 897 Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap), 898 ConstantRange(APInt(32, 0), APInt(32, 1))); 899 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 900 Instruction::Add, MinusOneToOne, 901 OBO::NoUnsignedWrap | OBO::NoSignedWrap), 902 ConstantRange(APInt(32, 0), APInt(32, 1))); 903 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 904 Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap), 905 ConstantRange(APInt::getSignedMinValue(32) + 1, 906 APInt::getSignedMinValue(32) - 1)); 907 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 908 Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap), 909 ConstantRange(APInt::getMaxValue(32), 910 APInt::getMinValue(32))); 911 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 912 Instruction::Sub, MinusOneToOne, 913 OBO::NoUnsignedWrap | OBO::NoSignedWrap), 914 ConstantRange(APInt::getMaxValue(32), 915 APInt::getMinValue(32))); 916 917 ConstantRange One(APInt(32, 1), APInt(32, 2)); 918 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 919 Instruction::Add, One, OBO::NoSignedWrap), 920 ConstantRange(APInt::getSignedMinValue(32), 921 APInt::getSignedMaxValue(32))); 922 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 923 Instruction::Add, One, OBO::NoUnsignedWrap), 924 ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32))); 925 EXPECT_EQ( 926 ConstantRange::makeGuaranteedNoWrapRegion( 927 Instruction::Add, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap), 928 ConstantRange(APInt(32, 0), APInt::getSignedMaxValue(32))); 929 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 930 Instruction::Sub, One, OBO::NoSignedWrap), 931 ConstantRange(APInt::getSignedMinValue(32) + 1, 932 APInt::getSignedMinValue(32))); 933 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 934 Instruction::Sub, One, OBO::NoUnsignedWrap), 935 ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32))); 936 EXPECT_EQ( 937 ConstantRange::makeGuaranteedNoWrapRegion( 938 Instruction::Sub, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap), 939 ConstantRange(APInt::getMinValue(32) + 1, APInt::getSignedMinValue(32))); 940 } 941 942 TEST(ConstantRange, GetEquivalentICmp) { 943 APInt RHS; 944 CmpInst::Predicate Pred; 945 946 EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100)) 947 .getEquivalentICmp(Pred, RHS)); 948 EXPECT_EQ(Pred, CmpInst::ICMP_ULT); 949 EXPECT_EQ(RHS, APInt(32, 100)); 950 951 EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100)) 952 .getEquivalentICmp(Pred, RHS)); 953 EXPECT_EQ(Pred, CmpInst::ICMP_SLT); 954 EXPECT_EQ(RHS, APInt(32, 100)); 955 956 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32)) 957 .getEquivalentICmp(Pred, RHS)); 958 EXPECT_EQ(Pred, CmpInst::ICMP_UGE); 959 EXPECT_EQ(RHS, APInt(32, 100)); 960 961 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32)) 962 .getEquivalentICmp(Pred, RHS)); 963 EXPECT_EQ(Pred, CmpInst::ICMP_SGE); 964 EXPECT_EQ(RHS, APInt(32, 100)); 965 966 EXPECT_TRUE( 967 ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred, RHS)); 968 EXPECT_EQ(Pred, CmpInst::ICMP_UGE); 969 EXPECT_EQ(RHS, APInt(32, 0)); 970 971 EXPECT_TRUE( 972 ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred, RHS)); 973 EXPECT_EQ(Pred, CmpInst::ICMP_ULT); 974 EXPECT_EQ(RHS, APInt(32, 0)); 975 976 EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200)) 977 .getEquivalentICmp(Pred, RHS)); 978 979 EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100), 980 APInt::getSignedMinValue(32) + APInt(32, 100)) 981 .getEquivalentICmp(Pred, RHS)); 982 983 EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100), 984 APInt::getMinValue(32) + APInt(32, 100)) 985 .getEquivalentICmp(Pred, RHS)); 986 987 EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred, RHS)); 988 EXPECT_EQ(Pred, CmpInst::ICMP_EQ); 989 EXPECT_EQ(RHS, APInt(32, 100)); 990 991 EXPECT_TRUE( 992 ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred, RHS)); 993 EXPECT_EQ(Pred, CmpInst::ICMP_NE); 994 EXPECT_EQ(RHS, APInt(32, 100)); 995 996 EXPECT_TRUE( 997 ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred, RHS)); 998 EXPECT_EQ(Pred, CmpInst::ICMP_NE); 999 EXPECT_EQ(RHS, APInt(512, 100)); 1000 1001 // NB! It would be correct for the following four calls to getEquivalentICmp 1002 // to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT. 1003 // However, that's not the case today. 1004 1005 EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred, RHS)); 1006 EXPECT_EQ(Pred, CmpInst::ICMP_EQ); 1007 EXPECT_EQ(RHS, APInt(32, 0)); 1008 1009 EXPECT_TRUE( 1010 ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred, RHS)); 1011 EXPECT_EQ(Pred, CmpInst::ICMP_NE); 1012 EXPECT_EQ(RHS, APInt(32, 0)); 1013 1014 EXPECT_TRUE(ConstantRange(APInt(32, -1)).getEquivalentICmp(Pred, RHS)); 1015 EXPECT_EQ(Pred, CmpInst::ICMP_EQ); 1016 EXPECT_EQ(RHS, APInt(32, -1)); 1017 1018 EXPECT_TRUE( 1019 ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS)); 1020 EXPECT_EQ(Pred, CmpInst::ICMP_NE); 1021 EXPECT_EQ(RHS, APInt(32, -1)); 1022 } 1023 1024 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedSingleValue) { 1025 typedef OverflowingBinaryOperator OBO; 1026 1027 for (uint64_t I = std::numeric_limits<uint8_t>::min(); 1028 I <= std::numeric_limits<uint8_t>::max(); I++) { 1029 auto Range = ConstantRange::makeGuaranteedNoWrapRegion( 1030 Instruction::Mul, ConstantRange(APInt(8, I), APInt(8, I + 1)), 1031 OBO::NoUnsignedWrap); 1032 1033 for (uint64_t V = std::numeric_limits<uint8_t>::min(); 1034 V <= std::numeric_limits<uint8_t>::max(); V++) { 1035 bool Overflow; 1036 (void)APInt(8, I).umul_ov(APInt(8, V), Overflow); 1037 EXPECT_EQ(!Overflow, Range.contains(APInt(8, V))); 1038 } 1039 } 1040 } 1041 1042 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedSingleValue) { 1043 typedef OverflowingBinaryOperator OBO; 1044 1045 for (int64_t I = std::numeric_limits<int8_t>::min(); 1046 I <= std::numeric_limits<int8_t>::max(); I++) { 1047 auto Range = ConstantRange::makeGuaranteedNoWrapRegion( 1048 Instruction::Mul, 1049 ConstantRange(APInt(8, I, /*isSigned=*/true), 1050 APInt(8, I + 1, /*isSigned=*/true)), 1051 OBO::NoSignedWrap); 1052 1053 for (int64_t V = std::numeric_limits<int8_t>::min(); 1054 V <= std::numeric_limits<int8_t>::max(); V++) { 1055 bool Overflow; 1056 (void)APInt(8, I, /*isSigned=*/true) 1057 .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow); 1058 EXPECT_EQ(!Overflow, Range.contains(APInt(8, V, /*isSigned=*/true))); 1059 } 1060 } 1061 } 1062 1063 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedAndSignedSingleValue) { 1064 typedef OverflowingBinaryOperator OBO; 1065 1066 for (uint64_t I = std::numeric_limits<uint8_t>::min(); 1067 I <= std::numeric_limits<uint8_t>::max(); I++) { 1068 auto Range = ConstantRange::makeGuaranteedNoWrapRegion( 1069 Instruction::Mul, ConstantRange(APInt(8, I), APInt(8, I + 1)), 1070 OBO::NoUnsignedWrap | OBO::NoSignedWrap); 1071 1072 for (uint64_t V = std::numeric_limits<uint8_t>::min(); 1073 V <= std::numeric_limits<uint8_t>::max(); V++) { 1074 bool UOverflow; 1075 (void)APInt(8, I).umul_ov(APInt(8, V), UOverflow); 1076 bool SOverflow; 1077 (void)APInt(8, I).smul_ov(APInt(8, V), SOverflow); 1078 EXPECT_EQ(!(UOverflow || SOverflow), Range.contains(APInt(8, V))); 1079 } 1080 } 1081 } 1082 1083 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedRange) { 1084 typedef OverflowingBinaryOperator OBO; 1085 1086 for (uint64_t Lo = std::numeric_limits<uint8_t>::min(); 1087 Lo <= std::numeric_limits<uint8_t>::max(); Lo++) { 1088 for (uint64_t Hi = Lo; Hi <= std::numeric_limits<uint8_t>::max(); Hi++) { 1089 EXPECT_EQ( 1090 ConstantRange::makeGuaranteedNoWrapRegion( 1091 Instruction::Mul, ConstantRange(APInt(8, Lo), APInt(8, Hi + 1)), 1092 OBO::NoUnsignedWrap), 1093 ConstantRange::makeGuaranteedNoWrapRegion( 1094 Instruction::Mul, ConstantRange(APInt(8, Hi), APInt(8, Hi + 1)), 1095 OBO::NoUnsignedWrap)); 1096 } 1097 } 1098 } 1099 1100 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedRange) { 1101 typedef OverflowingBinaryOperator OBO; 1102 1103 int Lo = -12, Hi = 16; 1104 auto Range = ConstantRange::makeGuaranteedNoWrapRegion( 1105 Instruction::Mul, 1106 ConstantRange(APInt(8, Lo, /*isSigned=*/true), 1107 APInt(8, Hi + 1, /*isSigned=*/true)), 1108 OBO::NoSignedWrap); 1109 1110 for (int64_t V = std::numeric_limits<int8_t>::min(); 1111 V <= std::numeric_limits<int8_t>::max(); V++) { 1112 bool AnyOverflow = false; 1113 for (int64_t I = Lo; I <= Hi; I++) { 1114 bool Overflow; 1115 (void)APInt(8, I, /*isSigned=*/true) 1116 .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow); 1117 AnyOverflow |= Overflow; 1118 } 1119 EXPECT_EQ(!AnyOverflow, Range.contains(APInt(8, V, /*isSigned=*/true))); 1120 } 1121 } 1122 1123 #define EXPECT_MAY_OVERFLOW(op) \ 1124 EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op)) 1125 #define EXPECT_ALWAYS_OVERFLOWS(op) \ 1126 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflows, (op)) 1127 #define EXPECT_NEVER_OVERFLOWS(op) \ 1128 EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op)) 1129 1130 TEST_F(ConstantRangeTest, UnsignedAddOverflow) { 1131 // Ill-defined - may overflow is a conservative result. 1132 EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty)); 1133 EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some)); 1134 1135 // Never overflow despite one full/wrap set. 1136 ConstantRange Zero(APInt::getNullValue(16)); 1137 EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero)); 1138 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero)); 1139 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full)); 1140 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap)); 1141 1142 // But usually full/wrap always may overflow. 1143 EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One)); 1144 EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One)); 1145 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full)); 1146 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap)); 1147 1148 ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00)); 1149 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201)); 1150 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202)); 1151 EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1)); 1152 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2)); 1153 EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A)); 1154 EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A)); 1155 1156 ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400)); 1157 ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400)); 1158 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1)); 1159 EXPECT_ALWAYS_OVERFLOWS(A.unsignedAddMayOverflow(C2)); 1160 EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A)); 1161 EXPECT_ALWAYS_OVERFLOWS(C2.unsignedAddMayOverflow(A)); 1162 } 1163 1164 TEST_F(ConstantRangeTest, UnsignedSubOverflow) { 1165 // Ill-defined - may overflow is a conservative result. 1166 EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty)); 1167 EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some)); 1168 1169 // Never overflow despite one full/wrap set. 1170 ConstantRange Zero(APInt::getNullValue(16)); 1171 ConstantRange Max(APInt::getAllOnesValue(16)); 1172 EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero)); 1173 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero)); 1174 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full)); 1175 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap)); 1176 1177 // But usually full/wrap always may overflow. 1178 EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One)); 1179 EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One)); 1180 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full)); 1181 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap)); 1182 1183 ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100)); 1184 ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200)); 1185 EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A)); 1186 EXPECT_ALWAYS_OVERFLOWS(A.unsignedSubMayOverflow(B)); 1187 1188 ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101)); 1189 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201)); 1190 EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1)); 1191 EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1)); 1192 1193 ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102)); 1194 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202)); 1195 EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2)); 1196 EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2)); 1197 } 1198 1199 TEST_F(ConstantRangeTest, SignedAddOverflow) { 1200 // Ill-defined - may overflow is a conservative result. 1201 EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty)); 1202 EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some)); 1203 1204 // Never overflow despite one full/wrap set. 1205 ConstantRange Zero(APInt::getNullValue(16)); 1206 EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero)); 1207 EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero)); 1208 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full)); 1209 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap)); 1210 1211 // But usually full/wrap always may overflow. 1212 EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One)); 1213 EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One)); 1214 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full)); 1215 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap)); 1216 1217 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00)); 1218 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201)); 1219 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202)); 1220 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1)); 1221 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2)); 1222 ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201)); 1223 ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202)); 1224 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3)); 1225 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4)); 1226 ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400)); 1227 ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400)); 1228 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5)); 1229 EXPECT_ALWAYS_OVERFLOWS(A.signedAddMayOverflow(B6)); 1230 1231 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300)); 1232 ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00)); 1233 ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00)); 1234 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1)); 1235 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2)); 1236 ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000)); 1237 ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000)); 1238 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3)); 1239 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4)); 1240 ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02)); 1241 ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01)); 1242 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5)); 1243 EXPECT_ALWAYS_OVERFLOWS(C.signedAddMayOverflow(D6)); 1244 1245 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100)); 1246 EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E)); 1247 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000)); 1248 EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F)); 1249 } 1250 1251 TEST_F(ConstantRangeTest, SignedSubOverflow) { 1252 // Ill-defined - may overflow is a conservative result. 1253 EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty)); 1254 EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some)); 1255 1256 // Never overflow despite one full/wrap set. 1257 ConstantRange Zero(APInt::getNullValue(16)); 1258 EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero)); 1259 EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero)); 1260 1261 // But usually full/wrap always may overflow. 1262 EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One)); 1263 EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One)); 1264 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full)); 1265 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap)); 1266 1267 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00)); 1268 ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00)); 1269 ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00)); 1270 EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1)); 1271 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2)); 1272 ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02)); 1273 ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01)); 1274 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3)); 1275 EXPECT_ALWAYS_OVERFLOWS(A.signedSubMayOverflow(B4)); 1276 1277 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300)); 1278 ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201)); 1279 ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202)); 1280 EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1)); 1281 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2)); 1282 ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400)); 1283 ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400)); 1284 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3)); 1285 EXPECT_ALWAYS_OVERFLOWS(C.signedSubMayOverflow(D4)); 1286 1287 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100)); 1288 EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E)); 1289 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001)); 1290 EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F)); 1291 } 1292 1293 template<typename Fn1, typename Fn2> 1294 static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) { 1295 // Constant range overflow checks are tested exhaustively on 4-bit numbers. 1296 unsigned Bits = 4; 1297 unsigned Max = 1 << Bits; 1298 for (unsigned Lo1 = 0; Lo1 < Max; Lo1++) { 1299 for (unsigned Hi1 = 0; Hi1 < Max; Hi1++) { 1300 // Enforce ConstantRange invariant. 1301 if (Lo1 == Hi1 && Lo1 != 0 && Lo1 != Max - 1) 1302 continue; 1303 1304 ConstantRange CR1(APInt(Bits, Lo1), APInt(Bits, Hi1)); 1305 unsigned Size1 = CR1.getSetSize().getLimitedValue(); 1306 1307 for (unsigned Lo2 = 0; Lo2 < Max; Lo2++) { 1308 for (unsigned Hi2 = 0; Hi2 < Max; Hi2++) { 1309 // Enforce ConstantRange invariant. 1310 if (Lo2 == Hi2 && Lo2 != 0 && Lo2 != Max - 1) 1311 continue; 1312 1313 ConstantRange CR2(APInt(Bits, Lo2), APInt(Bits, Hi2)); 1314 unsigned Size2 = CR2.getSetSize().getLimitedValue(); 1315 1316 // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the 1317 // operations have overflow / have no overflow. These loops are based 1318 // on Size1/Size2 to properly handle empty/full ranges. 1319 bool RangeHasOverflow = false; 1320 bool RangeHasNoOverflow = false; 1321 APInt N1(Bits, Lo1); 1322 for (unsigned I1 = 0; I1 < Size1; ++I1, ++N1) { 1323 APInt N2(Bits, Lo2); 1324 for (unsigned I2 = 0; I2 < Size2; ++I2, ++N2) { 1325 assert(CR1.contains(N1)); 1326 assert(CR2.contains(N2)); 1327 1328 if (OverflowFn(N1, N2)) 1329 RangeHasOverflow = true; 1330 else 1331 RangeHasNoOverflow = true; 1332 } 1333 } 1334 1335 ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2); 1336 switch (OR) { 1337 case ConstantRange::OverflowResult::AlwaysOverflows: 1338 EXPECT_TRUE(RangeHasOverflow); 1339 EXPECT_FALSE(RangeHasNoOverflow); 1340 break; 1341 case ConstantRange::OverflowResult::NeverOverflows: 1342 EXPECT_FALSE(RangeHasOverflow); 1343 EXPECT_TRUE(RangeHasNoOverflow); 1344 break; 1345 case ConstantRange::OverflowResult::MayOverflow: 1346 // We return MayOverflow for empty sets as a conservative result, 1347 // but of course neither the RangeHasOverflow nor the 1348 // RangeHasNoOverflow flags will be set. 1349 if (CR1.isEmptySet() || CR2.isEmptySet()) 1350 break; 1351 1352 EXPECT_TRUE(RangeHasOverflow); 1353 EXPECT_TRUE(RangeHasNoOverflow); 1354 break; 1355 } 1356 } 1357 } 1358 } 1359 } 1360 } 1361 1362 TEST_F(ConstantRangeTest, UnsignedAddOverflowExhautive) { 1363 TestOverflowExhaustive( 1364 [](const APInt &N1, const APInt &N2) { 1365 bool Overflow; 1366 (void) N1.uadd_ov(N2, Overflow); 1367 return Overflow; 1368 }, 1369 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1370 return CR1.unsignedAddMayOverflow(CR2); 1371 }); 1372 } 1373 1374 TEST_F(ConstantRangeTest, UnsignedSubOverflowExhautive) { 1375 TestOverflowExhaustive( 1376 [](const APInt &N1, const APInt &N2) { 1377 bool Overflow; 1378 (void) N1.usub_ov(N2, Overflow); 1379 return Overflow; 1380 }, 1381 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1382 return CR1.unsignedSubMayOverflow(CR2); 1383 }); 1384 } 1385 1386 TEST_F(ConstantRangeTest, SignedAddOverflowExhautive) { 1387 TestOverflowExhaustive( 1388 [](const APInt &N1, const APInt &N2) { 1389 bool Overflow; 1390 (void) N1.sadd_ov(N2, Overflow); 1391 return Overflow; 1392 }, 1393 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1394 return CR1.signedAddMayOverflow(CR2); 1395 }); 1396 } 1397 1398 TEST_F(ConstantRangeTest, SignedSubOverflowExhautive) { 1399 TestOverflowExhaustive( 1400 [](const APInt &N1, const APInt &N2) { 1401 bool Overflow; 1402 (void) N1.ssub_ov(N2, Overflow); 1403 return Overflow; 1404 }, 1405 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1406 return CR1.signedSubMayOverflow(CR2); 1407 }); 1408 } 1409 1410 TEST_F(ConstantRangeTest, FromKnownBits) { 1411 KnownBits Unknown(16); 1412 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false)); 1413 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true)); 1414 1415 // .10..01. -> unsigned 01000010 (66) to 11011011 (219) 1416 // -> signed 11000010 (194) to 01011011 (91) 1417 KnownBits Known(8); 1418 Known.Zero = 36; 1419 Known.One = 66; 1420 ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1)); 1421 ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1)); 1422 EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false)); 1423 EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true)); 1424 1425 // 1.10.10. -> 10100100 (164) to 11101101 (237) 1426 Known.Zero = 18; 1427 Known.One = 164; 1428 ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1)); 1429 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false)); 1430 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true)); 1431 1432 // 01.0.1.0 -> 01000100 (68) to 01101110 (110) 1433 Known.Zero = 145; 1434 Known.One = 68; 1435 ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1)); 1436 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false)); 1437 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true)); 1438 } 1439 1440 TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) { 1441 unsigned Bits = 4; 1442 unsigned Max = 1 << Bits; 1443 KnownBits Known(Bits); 1444 for (unsigned Zero = 0; Zero < Max; ++Zero) { 1445 for (unsigned One = 0; One < Max; ++One) { 1446 Known.Zero = Zero; 1447 Known.One = One; 1448 if (Known.hasConflict() || Known.isUnknown()) 1449 continue; 1450 1451 APInt MinUnsigned = APInt::getMaxValue(Bits); 1452 APInt MaxUnsigned = APInt::getMinValue(Bits); 1453 APInt MinSigned = APInt::getSignedMaxValue(Bits); 1454 APInt MaxSigned = APInt::getSignedMinValue(Bits); 1455 for (unsigned N = 0; N < Max; ++N) { 1456 APInt Num(Bits, N); 1457 if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0) 1458 continue; 1459 1460 if (Num.ult(MinUnsigned)) MinUnsigned = Num; 1461 if (Num.ugt(MaxUnsigned)) MaxUnsigned = Num; 1462 if (Num.slt(MinSigned)) MinSigned = Num; 1463 if (Num.sgt(MaxSigned)) MaxSigned = Num; 1464 } 1465 1466 ConstantRange UnsignedCR(MinUnsigned, MaxUnsigned + 1); 1467 ConstantRange SignedCR(MinSigned, MaxSigned + 1); 1468 EXPECT_EQ(UnsignedCR, ConstantRange::fromKnownBits(Known, false)); 1469 EXPECT_EQ(SignedCR, ConstantRange::fromKnownBits(Known, true)); 1470 } 1471 } 1472 } 1473 1474 } // anonymous namespace 1475