test/Transforms/InstSimplify/compare.ll

   1 ; RUN: opt < %s -instsimplify -S | FileCheck %s
   2 target datalayout = "p:32:32"
   3
   4 define i1 @ptrtoint() {
   5 ; CHECK-LABEL: @ptrtoint(
   6   %a = alloca i8
   7   %tmp = ptrtoint i8* %a to i32
   8   %r = icmp eq i32 %tmp, 0
   9   ret i1 %r
  10 ; CHECK: ret i1 false
  11 }
  12
  13 define i1 @bitcast() {
  14 ; CHECK-LABEL: @bitcast(
  15   %a = alloca i32
  16   %b = alloca i64
  17   %x = bitcast i32* %a to i8*
  18   %y = bitcast i64* %b to i8*
  19   %cmp = icmp eq i8* %x, %y
  20   ret i1 %cmp
  21 ; CHECK-NEXT: ret i1 false
  22 }
  23
  24 define i1 @gep() {
  25 ; CHECK-LABEL: @gep(
  26   %a = alloca [3 x i8], align 8
  27   %x = getelementptr inbounds [3 x i8]* %a, i32 0, i32 0
  28   %cmp = icmp eq i8* %x, null
  29   ret i1 %cmp
  30 ; CHECK-NEXT: ret i1 false
  31 }
  32
  33 define i1 @gep2() {
  34 ; CHECK-LABEL: @gep2(
  35   %a = alloca [3 x i8], align 8
  36   %x = getelementptr inbounds [3 x i8]* %a, i32 0, i32 0
  37   %y = getelementptr inbounds [3 x i8]* %a, i32 0, i32 0
  38   %cmp = icmp eq i8* %x, %y
  39   ret i1 %cmp
  40 ; CHECK-NEXT: ret i1 true
  41 }
  42
  43 ; PR11238
  44 %gept = type { i32, i32 }
  45 @gepy = global %gept zeroinitializer, align 8
  46 @gepz = extern_weak global %gept
  47
  48 define i1 @gep3() {
  49 ; CHECK-LABEL: @gep3(
  50   %x = alloca %gept, align 8
  51   %a = getelementptr %gept* %x, i64 0, i32 0
  52   %b = getelementptr %gept* %x, i64 0, i32 1
  53   %equal = icmp eq i32* %a, %b
  54   ret i1 %equal
  55 ; CHECK-NEXT: ret i1 false
  56 }
  57
  58 define i1 @gep4() {
  59 ; CHECK-LABEL: @gep4(
  60   %x = alloca %gept, align 8
  61   %a = getelementptr %gept* @gepy, i64 0, i32 0
  62   %b = getelementptr %gept* @gepy, i64 0, i32 1
  63   %equal = icmp eq i32* %a, %b
  64   ret i1 %equal
  65 ; CHECK-NEXT: ret i1 false
  66 }
  67
  68 define i1 @gep5() {
  69 ; CHECK-LABEL: @gep5(
  70   %x = alloca %gept, align 8
  71   %a = getelementptr inbounds %gept* %x, i64 0, i32 1
  72   %b = getelementptr %gept* @gepy, i64 0, i32 0
  73   %equal = icmp eq i32* %a, %b
  74   ret i1 %equal
  75 ; CHECK-NEXT: ret i1 false
  76 }
  77
  78 define i1 @gep6(%gept* %x) {
  79 ; Same as @gep3 but potentially null.
  80 ; CHECK-LABEL: @gep6(
  81   %a = getelementptr %gept* %x, i64 0, i32 0
  82   %b = getelementptr %gept* %x, i64 0, i32 1
  83   %equal = icmp eq i32* %a, %b
  84   ret i1 %equal
  85 ; CHECK-NEXT: ret i1 false
  86 }
  87
  88 define i1 @gep7(%gept* %x) {
  89 ; CHECK-LABEL: @gep7(
  90   %a = getelementptr %gept* %x, i64 0, i32 0
  91   %b = getelementptr %gept* @gepz, i64 0, i32 0
  92   %equal = icmp eq i32* %a, %b
  93   ret i1 %equal
  94 ; CHECK: ret i1 %equal
  95 }
  96
  97 define i1 @gep8(%gept* %x) {
  98 ; CHECK-LABEL: @gep8(
  99   %a = getelementptr %gept* %x, i32 1
 100   %b = getelementptr %gept* %x, i32 -1
 101   %equal = icmp ugt %gept* %a, %b
 102   ret i1 %equal
 103 ; CHECK: ret i1 %equal
 104 }
 105
 106 define i1 @gep9(i8* %ptr) {
 107 ; CHECK-LABEL: @gep9(
 108 ; CHECK-NOT: ret
 109 ; CHECK: ret i1 true
 110
 111 entry:
 112   %first1 = getelementptr inbounds i8* %ptr, i32 0
 113   %first2 = getelementptr inbounds i8* %first1, i32 1
 114   %first3 = getelementptr inbounds i8* %first2, i32 2
 115   %first4 = getelementptr inbounds i8* %first3, i32 4
 116   %last1 = getelementptr inbounds i8* %first2, i32 48
 117   %last2 = getelementptr inbounds i8* %last1, i32 8
 118   %last3 = getelementptr inbounds i8* %last2, i32 -4
 119   %last4 = getelementptr inbounds i8* %last3, i32 -4
 120   %first.int = ptrtoint i8* %first4 to i32
 121   %last.int = ptrtoint i8* %last4 to i32
 122   %cmp = icmp ne i32 %last.int, %first.int
 123   ret i1 %cmp
 124 }
 125
 126 define i1 @gep10(i8* %ptr) {
 127 ; CHECK-LABEL: @gep10(
 128 ; CHECK-NOT: ret
 129 ; CHECK: ret i1 true
 130
 131 entry:
 132   %first1 = getelementptr inbounds i8* %ptr, i32 -2
 133   %first2 = getelementptr inbounds i8* %first1, i32 44
 134   %last1 = getelementptr inbounds i8* %ptr, i32 48
 135   %last2 = getelementptr inbounds i8* %last1, i32 -6
 136   %first.int = ptrtoint i8* %first2 to i32
 137   %last.int = ptrtoint i8* %last2 to i32
 138   %cmp = icmp eq i32 %last.int, %first.int
 139   ret i1 %cmp
 140 }
 141
 142 define i1 @gep11(i8* %ptr) {
 143 ; CHECK-LABEL: @gep11(
 144 ; CHECK-NOT: ret
 145 ; CHECK: ret i1 true
 146
 147 entry:
 148   %first1 = getelementptr inbounds i8* %ptr, i32 -2
 149   %last1 = getelementptr inbounds i8* %ptr, i32 48
 150   %last2 = getelementptr inbounds i8* %last1, i32 -6
 151   %cmp = icmp ult i8* %first1, %last2
 152   ret i1 %cmp
 153 }
 154
 155 define i1 @gep12(i8* %ptr) {
 156 ; CHECK-LABEL: @gep12(
 157 ; CHECK-NOT: ret
 158 ; CHECK: ret i1 %cmp
 159
 160 entry:
 161   %first1 = getelementptr inbounds i8* %ptr, i32 -2
 162   %last1 = getelementptr inbounds i8* %ptr, i32 48
 163   %last2 = getelementptr inbounds i8* %last1, i32 -6
 164   %cmp = icmp slt i8* %first1, %last2
 165   ret i1 %cmp
 166 }
 167
 168 define i1 @gep13(i8* %ptr) {
 169 ; CHECK-LABEL: @gep13(
 170 ; We can prove this GEP is non-null because it is inbounds.
 171   %x = getelementptr inbounds i8* %ptr, i32 1
 172   %cmp = icmp eq i8* %x, null
 173   ret i1 %cmp
 174 ; CHECK-NEXT: ret i1 false
 175 }
 176
 177 define i1 @gep14({ {}, i8 }* %ptr) {
 178 ; CHECK-LABEL: @gep14(
 179 ; We can't simplify this because the offset of one in the GEP actually doesn't
 180 ; move the pointer.
 181   %x = getelementptr inbounds { {}, i8 }* %ptr, i32 0, i32 1
 182   %cmp = icmp eq i8* %x, null
 183   ret i1 %cmp
 184 ; CHECK-NOT: ret i1 false
 185 }
 186
 187 define i1 @gep15({ {}, [4 x {i8, i8}]}* %ptr, i32 %y) {
 188 ; CHECK-LABEL: @gep15(
 189 ; We can prove this GEP is non-null even though there is a user value, as we
 190 ; would necessarily violate inbounds on one side or the other.
 191   %x = getelementptr inbounds { {}, [4 x {i8, i8}]}* %ptr, i32 0, i32 1, i32 %y, i32 1
 192   %cmp = icmp eq i8* %x, null
 193   ret i1 %cmp
 194 ; CHECK-NEXT: ret i1 false
 195 }
 196
 197 define i1 @gep16(i8* %ptr, i32 %a) {
 198 ; CHECK-LABEL: @gep16(
 199 ; We can prove this GEP is non-null because it is inbounds and because we know
 200 ; %b is non-zero even though we don't know its value.
 201   %b = or i32 %a, 1
 202   %x = getelementptr inbounds i8* %ptr, i32 %b
 203   %cmp = icmp eq i8* %x, null
 204   ret i1 %cmp
 205 ; CHECK-NEXT: ret i1 false
 206 }
 207
 208 define i1 @zext(i32 %x) {
 209 ; CHECK-LABEL: @zext(
 210   %e1 = zext i32 %x to i64
 211   %e2 = zext i32 %x to i64
 212   %r = icmp eq i64 %e1, %e2
 213   ret i1 %r
 214 ; CHECK: ret i1 true
 215 }
 216
 217 define i1 @zext2(i1 %x) {
 218 ; CHECK-LABEL: @zext2(
 219   %e = zext i1 %x to i32
 220   %c = icmp ne i32 %e, 0
 221   ret i1 %c
 222 ; CHECK: ret i1 %x
 223 }
 224
 225 define i1 @zext3() {
 226 ; CHECK-LABEL: @zext3(
 227   %e = zext i1 1 to i32
 228   %c = icmp ne i32 %e, 0
 229   ret i1 %c
 230 ; CHECK: ret i1 true
 231 }
 232
 233 define i1 @sext(i32 %x) {
 234 ; CHECK-LABEL: @sext(
 235   %e1 = sext i32 %x to i64
 236   %e2 = sext i32 %x to i64
 237   %r = icmp eq i64 %e1, %e2
 238   ret i1 %r
 239 ; CHECK: ret i1 true
 240 }
 241
 242 define i1 @sext2(i1 %x) {
 243 ; CHECK-LABEL: @sext2(
 244   %e = sext i1 %x to i32
 245   %c = icmp ne i32 %e, 0
 246   ret i1 %c
 247 ; CHECK: ret i1 %x
 248 }
 249
 250 define i1 @sext3() {
 251 ; CHECK-LABEL: @sext3(
 252   %e = sext i1 1 to i32
 253   %c = icmp ne i32 %e, 0
 254   ret i1 %c
 255 ; CHECK: ret i1 true
 256 }
 257
 258 define i1 @add(i32 %x, i32 %y) {
 259 ; CHECK-LABEL: @add(
 260   %l = lshr i32 %x, 1
 261   %q = lshr i32 %y, 1
 262   %r = or i32 %q, 1
 263   %s = add i32 %l, %r
 264   %c = icmp eq i32 %s, 0
 265   ret i1 %c
 266 ; CHECK: ret i1 false
 267 }
 268
 269 define i1 @add2(i8 %x, i8 %y) {
 270 ; CHECK-LABEL: @add2(
 271   %l = or i8 %x, 128
 272   %r = or i8 %y, 129
 273   %s = add i8 %l, %r
 274   %c = icmp eq i8 %s, 0
 275   ret i1 %c
 276 ; CHECK: ret i1 false
 277 }
 278
 279 define i1 @add3(i8 %x, i8 %y) {
 280 ; CHECK-LABEL: @add3(
 281   %l = zext i8 %x to i32
 282   %r = zext i8 %y to i32
 283   %s = add i32 %l, %r
 284   %c = icmp eq i32 %s, 0
 285   ret i1 %c
 286 ; CHECK: ret i1 %c
 287 }
 288
 289 define i1 @add4(i32 %x, i32 %y) {
 290 ; CHECK-LABEL: @add4(
 291   %z = add nsw i32 %y, 1
 292   %s1 = add nsw i32 %x, %y
 293   %s2 = add nsw i32 %x, %z
 294   %c = icmp slt i32 %s1, %s2
 295   ret i1 %c
 296 ; CHECK: ret i1 true
 297 }
 298
 299 define i1 @add5(i32 %x, i32 %y) {
 300 ; CHECK-LABEL: @add5(
 301   %z = add nuw i32 %y, 1
 302   %s1 = add nuw i32 %x, %z
 303   %s2 = add nuw i32 %x, %y
 304   %c = icmp ugt i32 %s1, %s2
 305   ret i1 %c
 306 ; CHECK: ret i1 true
 307 }
 308
 309 define i1 @add6(i64 %A, i64 %B) {
 310 ; CHECK-LABEL: @add6(
 311   %s1 = add i64 %A, %B
 312   %s2 = add i64 %B, %A
 313   %cmp = icmp eq i64 %s1, %s2
 314   ret i1 %cmp
 315 ; CHECK: ret i1 true
 316 }
 317
 318 define i1 @addpowtwo(i32 %x, i32 %y) {
 319 ; CHECK-LABEL: @addpowtwo(
 320   %l = lshr i32 %x, 1
 321   %r = shl i32 1, %y
 322   %s = add i32 %l, %r
 323   %c = icmp eq i32 %s, 0
 324   ret i1 %c
 325 ; CHECK: ret i1 false
 326 }
 327
 328 define i1 @or(i32 %x) {
 329 ; CHECK-LABEL: @or(
 330   %o = or i32 %x, 1
 331   %c = icmp eq i32 %o, 0
 332   ret i1 %c
 333 ; CHECK: ret i1 false
 334 }
 335
 336 define i1 @shl1(i32 %x) {
 337 ; CHECK-LABEL: @shl1(
 338   %s = shl i32 1, %x
 339   %c = icmp eq i32 %s, 0
 340   ret i1 %c
 341 ; CHECK: ret i1 false
 342 }
 343
 344 define i1 @shl2(i32 %X) {
 345 ; CHECK: @shl2
 346   %sub = shl nsw i32 -1, %X
 347   %cmp = icmp eq i32 %sub, 31
 348   ret i1 %cmp
 349 ; CHECK-NEXT: ret i1 false
 350 }
 351
 352 define i1 @shl3(i32 %X) {
 353 ; CHECK: @shl3
 354   %sub = shl nuw i32 4, %X
 355   %cmp = icmp eq i32 %sub, 31
 356   ret i1 %cmp
 357 ; CHECK-NEXT: ret i1 false
 358 }
 359
 360 define i1 @shl4(i32 %X) {
 361 ; CHECK: @shl4
 362   %sub = shl nsw i32 -1, %X
 363   %cmp = icmp sle i32 %sub, -1
 364   ret i1 %cmp
 365 ; CHECK-NEXT: ret i1 true
 366 }
 367
 368 define i1 @shl5(i32 %X) {
 369 ; CHECK: @shl5
 370   %sub = shl nuw i32 4, %X
 371   %cmp = icmp ugt i32 %sub, 3
 372   ret i1 %cmp
 373 ; CHECK-NEXT: ret i1 true
 374 }
 375
 376 define i1 @lshr1(i32 %x) {
 377 ; CHECK-LABEL: @lshr1(
 378   %s = lshr i32 -1, %x
 379   %c = icmp eq i32 %s, 0
 380   ret i1 %c
 381 ; CHECK: ret i1 false
 382 }
 383
 384 define i1 @lshr2(i32 %x) {
 385 ; CHECK-LABEL: @lshr2(
 386   %s = lshr i32 %x, 30
 387   %c = icmp ugt i32 %s, 8
 388   ret i1 %c
 389 ; CHECK: ret i1 false
 390 }
 391
 392 define i1 @lshr3(i32 %x) {
 393 ; CHECK-LABEL: @lshr3(
 394   %s = lshr i32 %x, %x
 395   %c = icmp eq i32 %s, 0
 396   ret i1 %c
 397 ; CHECK: ret i1 true
 398 }
 399
 400 define i1 @ashr1(i32 %x) {
 401 ; CHECK-LABEL: @ashr1(
 402   %s = ashr i32 -1, %x
 403   %c = icmp eq i32 %s, 0
 404   ret i1 %c
 405 ; CHECK: ret i1 false
 406 }
 407
 408 define i1 @ashr2(i32 %x) {
 409 ; CHECK-LABEL: @ashr2(
 410   %s = ashr i32 %x, 30
 411   %c = icmp slt i32 %s, -5
 412   ret i1 %c
 413 ; CHECK: ret i1 false
 414 }
 415
 416 define i1 @ashr3(i32 %x) {
 417 ; CHECK-LABEL: @ashr3(
 418   %s = ashr i32 %x, %x
 419   %c = icmp eq i32 %s, 0
 420   ret i1 %c
 421 ; CHECK: ret i1 true
 422 }
 423
 424 define i1 @select1(i1 %cond) {
 425 ; CHECK-LABEL: @select1(
 426   %s = select i1 %cond, i32 1, i32 0
 427   %c = icmp eq i32 %s, 1
 428   ret i1 %c
 429 ; CHECK: ret i1 %cond
 430 }
 431
 432 define i1 @select2(i1 %cond) {
 433 ; CHECK-LABEL: @select2(
 434   %x = zext i1 %cond to i32
 435   %s = select i1 %cond, i32 %x, i32 0
 436   %c = icmp ne i32 %s, 0
 437   ret i1 %c
 438 ; CHECK: ret i1 %cond
 439 }
 440
 441 define i1 @select3(i1 %cond) {
 442 ; CHECK-LABEL: @select3(
 443   %x = zext i1 %cond to i32
 444   %s = select i1 %cond, i32 1, i32 %x
 445   %c = icmp ne i32 %s, 0
 446   ret i1 %c
 447 ; CHECK: ret i1 %cond
 448 }
 449
 450 define i1 @select4(i1 %cond) {
 451 ; CHECK-LABEL: @select4(
 452   %invert = xor i1 %cond, 1
 453   %s = select i1 %invert, i32 0, i32 1
 454   %c = icmp ne i32 %s, 0
 455   ret i1 %c
 456 ; CHECK: ret i1 %cond
 457 }
 458
 459 define i1 @select5(i32 %x) {
 460 ; CHECK-LABEL: @select5(
 461   %c = icmp eq i32 %x, 0
 462   %s = select i1 %c, i32 1, i32 %x
 463   %c2 = icmp eq i32 %s, 0
 464   ret i1 %c2
 465 ; CHECK: ret i1 false
 466 }
 467
 468 define i1 @select6(i32 %x) {
 469 ; CHECK-LABEL: @select6(
 470   %c = icmp sgt i32 %x, 0
 471   %s = select i1 %c, i32 %x, i32 4
 472   %c2 = icmp eq i32 %s, 0
 473   ret i1 %c2
 474 ; CHECK: ret i1 %c2
 475 }
 476
 477 define i1 @urem1(i32 %X, i32 %Y) {
 478 ; CHECK-LABEL: @urem1(
 479   %A = urem i32 %X, %Y
 480   %B = icmp ult i32 %A, %Y
 481   ret i1 %B
 482 ; CHECK: ret i1 true
 483 }
 484
 485 define i1 @urem2(i32 %X, i32 %Y) {
 486 ; CHECK-LABEL: @urem2(
 487   %A = urem i32 %X, %Y
 488   %B = icmp eq i32 %A, %Y
 489   ret i1 %B
 490 ; CHECK: ret i1 false
 491 }
 492
 493 define i1 @urem3(i32 %X) {
 494 ; CHECK-LABEL: @urem3(
 495   %A = urem i32 %X, 10
 496   %B = icmp ult i32 %A, 15
 497   ret i1 %B
 498 ; CHECK: ret i1 true
 499 }
 500
 501 define i1 @urem4(i32 %X) {
 502 ; CHECK-LABEL: @urem4(
 503   %A = urem i32 %X, 15
 504   %B = icmp ult i32 %A, 10
 505   ret i1 %B
 506 ; CHECK: ret i1 %B
 507 }
 508
 509 define i1 @urem5(i16 %X, i32 %Y) {
 510 ; CHECK-LABEL: @urem5(
 511   %A = zext i16 %X to i32
 512   %B = urem i32 %A, %Y
 513   %C = icmp slt i32 %B, %Y
 514   ret i1 %C
 515 ; CHECK-NOT: ret i1 true
 516 }
 517
 518 define i1 @urem6(i32 %X, i32 %Y) {
 519 ; CHECK-LABEL: @urem6(
 520   %A = urem i32 %X, %Y
 521   %B = icmp ugt i32 %Y, %A
 522   ret i1 %B
 523 ; CHECK: ret i1 true
 524 }
 525
 526 define i1 @urem7(i32 %X) {
 527 ; CHECK-LABEL: @urem7(
 528   %A = urem i32 1, %X
 529   %B = icmp sgt i32 %A, %X
 530   ret i1 %B
 531 ; CHECK-NOT: ret i1 false
 532 }
 533
 534 define i1 @srem1(i32 %X) {
 535 ; CHECK-LABEL: @srem1(
 536   %A = srem i32 %X, -5
 537   %B = icmp sgt i32 %A, 5
 538   ret i1 %B
 539 ; CHECK: ret i1 false
 540 }
 541
 542 ; PR9343 #15
 543 ; CHECK-LABEL: @srem2(
 544 ; CHECK: ret i1 false
 545 define i1 @srem2(i16 %X, i32 %Y) {
 546   %A = zext i16 %X to i32
 547   %B = add nsw i32 %A, 1
 548   %C = srem i32 %B, %Y
 549   %D = icmp slt i32 %C, 0
 550   ret i1 %D
 551 }
 552
 553 ; CHECK-LABEL: @srem3(
 554 ; CHECK-NEXT: ret i1 false
 555 define i1 @srem3(i16 %X, i32 %Y) {
 556   %A = zext i16 %X to i32
 557   %B = or i32 2147483648, %A
 558   %C = sub nsw i32 1, %B
 559   %D = srem i32 %C, %Y
 560   %E = icmp slt i32 %D, 0
 561   ret i1 %E
 562 }
 563
 564 define i1 @udiv1(i32 %X) {
 565 ; CHECK-LABEL: @udiv1(
 566   %A = udiv i32 %X, 1000000
 567   %B = icmp ult i32 %A, 5000
 568   ret i1 %B
 569 ; CHECK: ret i1 true
 570 }
 571
 572 define i1 @udiv2(i32 %X, i32 %Y, i32 %Z) {
 573 ; CHECK-LABEL: @udiv2(
 574   %A = udiv exact i32 10, %Z
 575   %B = udiv exact i32 20, %Z
 576   %C = icmp ult i32 %A, %B
 577   ret i1 %C
 578 ; CHECK: ret i1 true
 579 }
 580
 581 define i1 @udiv3(i32 %X, i32 %Y) {
 582 ; CHECK-LABEL: @udiv3(
 583   %A = udiv i32 %X, %Y
 584   %C = icmp ugt i32 %A, %X
 585   ret i1 %C
 586 ; CHECK: ret i1 false
 587 }
 588
 589 define i1 @udiv4(i32 %X, i32 %Y) {
 590 ; CHECK-LABEL: @udiv4(
 591   %A = udiv i32 %X, %Y
 592   %C = icmp ule i32 %A, %X
 593   ret i1 %C
 594 ; CHECK: ret i1 true
 595 }
 596
 597 define i1 @udiv5(i32 %X) {
 598 ; CHECK-LABEL: @udiv5(
 599   %A = udiv i32 123, %X
 600   %C = icmp ugt i32 %A, 124
 601   ret i1 %C
 602 ; CHECK: ret i1 false
 603 }
 604
 605 ; PR11340
 606 define i1 @udiv6(i32 %X) nounwind {
 607 ; CHECK-LABEL: @udiv6(
 608   %A = udiv i32 1, %X
 609   %C = icmp eq i32 %A, 0
 610   ret i1 %C
 611 ; CHECK: ret i1 %C
 612 }
 613
 614
 615 define i1 @sdiv1(i32 %X) {
 616 ; CHECK-LABEL: @sdiv1(
 617   %A = sdiv i32 %X, 1000000
 618   %B = icmp slt i32 %A, 3000
 619   ret i1 %B
 620 ; CHECK: ret i1 true
 621 }
 622
 623 define i1 @or1(i32 %X) {
 624 ; CHECK-LABEL: @or1(
 625   %A = or i32 %X, 62
 626   %B = icmp ult i32 %A, 50
 627   ret i1 %B
 628 ; CHECK: ret i1 false
 629 }
 630
 631 define i1 @and1(i32 %X) {
 632 ; CHECK-LABEL: @and1(
 633   %A = and i32 %X, 62
 634   %B = icmp ugt i32 %A, 70
 635   ret i1 %B
 636 ; CHECK: ret i1 false
 637 }
 638
 639 define i1 @mul1(i32 %X) {
 640 ; CHECK-LABEL: @mul1(
 641 ; Square of a non-zero number is non-zero if there is no overflow.
 642   %Y = or i32 %X, 1
 643   %M = mul nuw i32 %Y, %Y
 644   %C = icmp eq i32 %M, 0
 645   ret i1 %C
 646 ; CHECK: ret i1 false
 647 }
 648
 649 define i1 @mul2(i32 %X) {
 650 ; CHECK-LABEL: @mul2(
 651 ; Square of a non-zero number is positive if there is no signed overflow.
 652   %Y = or i32 %X, 1
 653   %M = mul nsw i32 %Y, %Y
 654   %C = icmp sgt i32 %M, 0
 655   ret i1 %C
 656 ; CHECK: ret i1 true
 657 }
 658
 659 define i1 @mul3(i32 %X, i32 %Y) {
 660 ; CHECK-LABEL: @mul3(
 661 ; Product of non-negative numbers is non-negative if there is no signed overflow.
 662   %XX = mul nsw i32 %X, %X
 663   %YY = mul nsw i32 %Y, %Y
 664   %M = mul nsw i32 %XX, %YY
 665   %C = icmp sge i32 %M, 0
 666   ret i1 %C
 667 ; CHECK: ret i1 true
 668 }
 669
 670 define <2 x i1> @vectorselect1(<2 x i1> %cond) {
 671 ; CHECK-LABEL: @vectorselect1(
 672   %invert = xor <2 x i1> %cond, <i1 1, i1 1>
 673   %s = select <2 x i1> %invert, <2 x i32> <i32 0, i32 0>, <2 x i32> <i32 1, i32 1>
 674   %c = icmp ne <2 x i32> %s, <i32 0, i32 0>
 675   ret <2 x i1> %c
 676 ; CHECK: ret <2 x i1> %cond
 677 }
 678
 679 ; PR11948
 680 define <2 x i1> @vectorselectcrash(i32 %arg1) {
 681   %tobool40 = icmp ne i32 %arg1, 0
 682   %cond43 = select i1 %tobool40, <2 x i16> <i16 -5, i16 66>, <2 x i16> <i16 46, i16 1>
 683   %cmp45 = icmp ugt <2 x i16> %cond43, <i16 73, i16 21>
 684   ret <2 x i1> %cmp45
 685 }
 686
 687 ; PR12013
 688 define i1 @alloca_compare(i64 %idx) {
 689   %sv = alloca { i32, i32, [124 x i32] }
 690   %1 = getelementptr inbounds { i32, i32, [124 x i32] }* %sv, i32 0, i32 2, i64 %idx
 691   %2 = icmp eq i32* %1, null
 692   ret i1 %2
 693   ; CHECK: alloca_compare
 694   ; CHECK: ret i1 false
 695 }
 696
 697 ; PR12075
 698 define i1 @infinite_gep() {
 699   ret i1 1
 700
 701 unreachableblock:
 702   %X = getelementptr i32 *%X, i32 1
 703   %Y = icmp eq i32* %X, null
 704   ret i1 %Y
 705 }
 706
 707 ; It's not valid to fold a comparison of an argument with an alloca, even though
 708 ; that's tempting. An argument can't *alias* an alloca, however the aliasing rule
 709 ; relies on restrictions against guessing an object's address and dereferencing.
 710 ; There are no restrictions against guessing an object's address and comparing.
 711
 712 define i1 @alloca_argument_compare(i64* %arg) {
 713   %alloc = alloca i64
 714   %cmp = icmp eq i64* %arg, %alloc
 715   ret i1 %cmp
 716   ; CHECK: alloca_argument_compare
 717   ; CHECK: ret i1 %cmp
 718 }
 719
 720 ; As above, but with the operands reversed.
 721
 722 define i1 @alloca_argument_compare_swapped(i64* %arg) {
 723   %alloc = alloca i64
 724   %cmp = icmp eq i64* %alloc, %arg
 725   ret i1 %cmp
 726   ; CHECK: alloca_argument_compare_swapped
 727   ; CHECK: ret i1 %cmp
 728 }
 729
 730 ; Don't assume that a noalias argument isn't equal to a global variable's
 731 ; address. This is an example where AliasAnalysis' NoAlias concept is
 732 ; different from actual pointer inequality.
 733
 734 @y = external global i32
 735 define zeroext i1 @external_compare(i32* noalias %x) {
 736   %cmp = icmp eq i32* %x, @y
 737   ret i1 %cmp
 738   ; CHECK: external_compare
 739   ; CHECK: ret i1 %cmp
 740 }
 741
 742 define i1 @alloca_gep(i64 %a, i64 %b) {
 743 ; CHECK-LABEL: @alloca_gep(
 744 ; We can prove this GEP is non-null because it is inbounds and the pointer
 745 ; is non-null.
 746   %strs = alloca [1000 x [1001 x i8]], align 16
 747   %x = getelementptr inbounds [1000 x [1001 x i8]]* %strs, i64 0, i64 %a, i64 %b
 748   %cmp = icmp eq i8* %x, null
 749   ret i1 %cmp
 750 ; CHECK-NEXT: ret i1 false
 751 }
 752
 753 define i1 @non_inbounds_gep_compare(i64* %a) {
 754 ; CHECK-LABEL: @non_inbounds_gep_compare(
 755 ; Equality compares with non-inbounds GEPs can be folded.
 756   %x = getelementptr i64* %a, i64 42
 757   %y = getelementptr inbounds i64* %x, i64 -42
 758   %z = getelementptr i64* %a, i64 -42
 759   %w = getelementptr inbounds i64* %z, i64 42
 760   %cmp = icmp eq i64* %y, %w
 761   ret i1 %cmp
 762 ; CHECK-NEXT: ret i1 true
 763 }
 764
 765 define i1 @non_inbounds_gep_compare2(i64* %a) {
 766 ; CHECK-LABEL: @non_inbounds_gep_compare2(
 767 ; Equality compares with non-inbounds GEPs can be folded.
 768   %x = getelementptr i64* %a, i64 4294967297
 769   %y = getelementptr i64* %a, i64 1
 770   %cmp = icmp eq i64* %y, %y
 771   ret i1 %cmp
 772 ; CHECK-NEXT: ret i1 true
 773 }
 774
 775 define <4 x i8> @vectorselectfold(<4 x i8> %a, <4 x i8> %b) {
 776   %false = icmp ne <4 x i8> zeroinitializer, zeroinitializer
 777   %sel = select <4 x i1> %false, <4 x i8> %a, <4 x i8> %b
 778   ret <4 x i8> %sel
 779
 780 ; CHECK-LABEL: @vectorselectfold
 781 ; CHECK-NEXT: ret <4 x i8> %b
 782 }
 783
 784 define <4 x i8> @vectorselectfold2(<4 x i8> %a, <4 x i8> %b) {
 785   %true = icmp eq <4 x i8> zeroinitializer, zeroinitializer
 786   %sel = select <4 x i1> %true, <4 x i8> %a, <4 x i8> %b
 787   ret <4 x i8> %sel
 788
 789 ; CHECK-LABEL: @vectorselectfold
 790 ; CHECK-NEXT: ret <4 x i8> %a
 791 }
 792
 793 define i1 @compare_always_true_slt(i16 %a) {
 794   %1 = zext i16 %a to i32
 795   %2 = sub nsw i32 0, %1
 796   %3 = icmp slt i32 %2, 1
 797   ret i1 %3
 798
 799 ; CHECK-LABEL: @compare_always_true_slt
 800 ; CHECK-NEXT: ret i1 true
 801 }
 802
 803 define i1 @compare_always_true_sle(i16 %a) {
 804   %1 = zext i16 %a to i32
 805   %2 = sub nsw i32 0, %1
 806   %3 = icmp sle i32 %2, 0
 807   ret i1 %3
 808
 809 ; CHECK-LABEL: @compare_always_true_sle
 810 ; CHECK-NEXT: ret i1 true
 811 }
 812
 813 define i1 @compare_always_false_sgt(i16 %a) {
 814   %1 = zext i16 %a to i32
 815   %2 = sub nsw i32 0, %1
 816   %3 = icmp sgt i32 %2, 0
 817   ret i1 %3
 818
 819 ; CHECK-LABEL: @compare_always_false_sgt
 820 ; CHECK-NEXT: ret i1 false
 821 }
 822
 823 define i1 @compare_always_false_sge(i16 %a) {
 824   %1 = zext i16 %a to i32
 825   %2 = sub nsw i32 0, %1
 826   %3 = icmp sge i32 %2, 1
 827   ret i1 %3
 828
 829 ; CHECK-LABEL: @compare_always_false_sge
 830 ; CHECK-NEXT: ret i1 false
 831 }
 832
 833 define i1 @compare_always_false_eq(i16 %a) {
 834   %1 = zext i16 %a to i32
 835   %2 = sub nsw i32 0, %1
 836   %3 = icmp eq i32 %2, 1
 837   ret i1 %3
 838
 839 ; CHECK-LABEL: @compare_always_false_eq
 840 ; CHECK-NEXT: ret i1 false
 841 }
 842
 843 define i1 @compare_always_false_ne(i16 %a) {
 844   %1 = zext i16 %a to i32
 845   %2 = sub nsw i32 0, %1
 846   %3 = icmp ne i32 %2, 1
 847   ret i1 %3
 848
 849 ; CHECK-LABEL: @compare_always_false_ne
 850 ; CHECK-NEXT: ret i1 true
 851 }
 852
 853 define i1 @compare_dividend(i32 %a) {
 854   %div = sdiv i32 2, %a
 855   %cmp = icmp eq i32 %div, 3
 856   ret i1 %cmp
 857
 858 ; CHECK-LABEL: @compare_dividend
 859 ; CHECK-NEXT: ret i1 false
 860 }
 861
 862 define i1 @lshr_ugt_false(i32 %a) {
 863   %shr = lshr i32 1, %a
 864   %cmp = icmp ugt i32 %shr, 1
 865   ret i1 %cmp
 866 ; CHECK-LABEL: @lshr_ugt_false
 867 ; CHECK-NEXT: ret i1 false
 868 }
 869
 870 define i1 @exact_lshr_ugt_false(i32 %a) {
 871   %shr = lshr exact i32 30, %a
 872   %cmp = icmp ult i32 %shr, 15
 873   ret i1 %cmp
 874 ; CHECK-LABEL: @exact_lshr_ugt_false
 875 ; CHECK-NEXT: ret i1 false
 876 }
 877
 878 define i1 @lshr_sgt_false(i32 %a) {
 879   %shr = lshr i32 1, %a
 880   %cmp = icmp sgt i32 %shr, 1
 881   ret i1 %cmp
 882 ; CHECK-LABEL: @lshr_sgt_false
 883 ; CHECK-NEXT: ret i1 false
 884 }
 885
 886 define i1 @ashr_sgt_false(i32 %a) {
 887   %shr = ashr i32 -30, %a
 888   %cmp = icmp sgt i32 %shr, -1
 889   ret i1 %cmp
 890 ; CHECK-LABEL: @ashr_sgt_false
 891 ; CHECK-NEXT: ret i1 false
 892 }
 893
 894 define i1 @exact_ashr_sgt_false(i32 %a) {
 895   %shr = ashr exact i32 -30, %a
 896   %cmp = icmp sgt i32 %shr, -15
 897   ret i1 %cmp
 898 ; CHECK-LABEL: @exact_ashr_sgt_false
 899 ; CHECK-NEXT: ret i1 false
 900 }
 901
 902 define i1 @nonnull_arg(i32* nonnull %i) {
 903   %cmp = icmp eq i32* %i, null
 904   ret i1 %cmp
 905 ; CHECK-LABEL: @nonnull_arg
 906 ; CHECK: ret i1 false
 907 }
 908
 909 define i1 @nonnull_deref_arg(i32* dereferenceable(4) %i) {
 910   %cmp = icmp eq i32* %i, null
 911   ret i1 %cmp
 912 ; CHECK-LABEL: @nonnull_deref_arg
 913 ; CHECK: ret i1 false
 914 }
 915
 916 define i1 @nonnull_deref_as_arg(i32 addrspace(1)* dereferenceable(4) %i) {
 917   %cmp = icmp eq i32 addrspace(1)* %i, null
 918   ret i1 %cmp
 919 ; CHECK-LABEL: @nonnull_deref_as_arg
 920 ; CHECK: icmp
 921 ; CHECK ret
 922 }
 923
 924 declare nonnull i32* @returns_nonnull_helper()
 925 define i1 @returns_nonnull() {
 926   %call = call nonnull i32* @returns_nonnull_helper()
 927   %cmp = icmp eq i32* %call, null
 928   ret i1 %cmp
 929 ; CHECK-LABEL: @returns_nonnull
 930 ; CHECK: ret i1 false
 931 }
 932
 933 declare dereferenceable(4) i32* @returns_nonnull_deref_helper()
 934 define i1 @returns_nonnull_deref() {
 935   %call = call dereferenceable(4) i32* @returns_nonnull_deref_helper()
 936   %cmp = icmp eq i32* %call, null
 937   ret i1 %cmp
 938 ; CHECK-LABEL: @returns_nonnull_deref
 939 ; CHECK: ret i1 false
 940 }
 941
 942 declare dereferenceable(4) i32 addrspace(1)* @returns_nonnull_deref_as_helper()
 943 define i1 @returns_nonnull_as_deref() {
 944   %call = call dereferenceable(4) i32 addrspace(1)* @returns_nonnull_deref_as_helper()
 945   %cmp = icmp eq i32 addrspace(1)* %call, null
 946   ret i1 %cmp
 947 ; CHECK-LABEL: @returns_nonnull_as_deref
 948 ; CHECK: icmp
 949 ; CHECK: ret
 950 }
 951
 952 define i1 @nonnull_load(i32** %addr) {
 953   %ptr = load i32** %addr, !nonnull !{}
 954   %cmp = icmp eq i32* %ptr, null
 955   ret i1 %cmp
 956 ; CHECK-LABEL: @nonnull_load
 957 ; CHECK: ret i1 false
 958 }
 959
 960 define i1 @nonnull_load_as_outer(i32* addrspace(1)* %addr) {
 961   %ptr = load i32* addrspace(1)* %addr, !nonnull !{}
 962   %cmp = icmp eq i32* %ptr, null
 963   ret i1 %cmp
 964 ; CHECK-LABEL: @nonnull_load_as_outer
 965 ; CHECK: ret i1 false
 966 }
 967 define i1 @nonnull_load_as_inner(i32 addrspace(1)** %addr) {
 968   %ptr = load i32 addrspace(1)** %addr, !nonnull !{}
 969   %cmp = icmp eq i32 addrspace(1)* %ptr, null
 970   ret i1 %cmp
 971 ; CHECK-LABEL: @nonnull_load_as_inner
 972 ; CHECK: ret i1 false
 973 }
 974
 975 ; If a bit is known to be zero for A and known to be one for B,
 976 ; then A and B cannot be equal.
 977 define i1 @icmp_eq_const(i32 %a) nounwind {
 978   %b = mul nsw i32 %a, -2
 979   %c = icmp eq i32 %b, 1
 980   ret i1 %c
 981
 982 ; CHECK-LABEL: @icmp_eq_const
 983 ; CHECK-NEXT: ret i1 false
 984 }
 985
 986 define i1 @icmp_ne_const(i32 %a) nounwind {
 987   %b = mul nsw i32 %a, -2
 988   %c = icmp ne i32 %b, 1
 989   ret i1 %c
 990
 991 ; CHECK-LABEL: @icmp_ne_const
 992 ; CHECK-NEXT: ret i1 true
 993 }
 994
 995 define i1 @icmp_sdiv_int_min(i32 %a) {
 996   %div = sdiv i32 -2147483648, %a
 997   %cmp = icmp ne i32 %div, -1073741824
 998   ret i1 %cmp
 999
1000 ; CHECK-LABEL: @icmp_sdiv_int_min
1001 ; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 -2147483648, %a
1002 ; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32 [[DIV]], -1073741824
1003 ; CHECK-NEXT: ret i1 [[CMP]]
1004 }
1005
1006 define i1 @icmp_sdiv_pr20288(i64 %a) {
1007    %div = sdiv i64 %a, -8589934592
1008    %cmp = icmp ne i64 %div, 1073741824
1009    ret i1 %cmp
1010
1011 ; CHECK-LABEL: @icmp_sdiv_pr20288
1012 ; CHECK-NEXT: [[DIV:%.*]] = sdiv i64 %a, -8589934592
1013 ; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[DIV]], 1073741824
1014 ; CHECK-NEXT: ret i1 [[CMP]]
1015 }
1016
1017 define i1 @icmp_sdiv_neg1(i64 %a) {
1018  %div = sdiv i64 %a, -1
1019  %cmp = icmp ne i64 %div, 1073741824
1020  ret i1 %cmp
1021
1022 ; CHECK-LABEL: @icmp_sdiv_neg1
1023 ; CHECK-NEXT: [[DIV:%.*]] = sdiv i64 %a, -1
1024 ; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[DIV]], 1073741824
1025 ; CHECK-NEXT: ret i1 [[CMP]]
1026 }
1027
1028 define i1 @icmp_known_bits(i4 %x, i4 %y) {
1029   %and1 = and i4 %y, -7
1030   %and2 = and i4 %x, -7
1031   %or1 = or i4 %and1, 2
1032   %or2 = or i4 %and2, 2
1033   %add = add i4 %or1, %or2
1034   %cmp = icmp eq i4 %add, 0
1035   ret i1 %cmp
1036
1037 ; CHECK-LABEL: @icmp_known_bits
1038 ; CHECK-NEXT: ret i1 false
1039 }
1040
1041 define i1 @icmp_shl_nuw_1(i64 %a) {
1042  %shl = shl nuw i64 1, %a
1043  %cmp = icmp ne i64 %shl, 0
1044  ret i1 %cmp
1045
1046 ; CHECK-LABEL: @icmp_shl_nuw_1
1047 ; CHECK-NEXT: ret i1 true
1048 }
1049
1050 define i1 @icmp_shl_nsw_neg1(i64 %a) {
1051  %shl = shl nsw i64 -1, %a
1052  %cmp = icmp sge i64 %shl, 3
1053  ret i1 %cmp
1054
1055 ; CHECK-LABEL: @icmp_shl_nsw_neg1
1056 ; CHECK-NEXT: ret i1 false
1057 }
1058
1059 define i1 @icmp_shl_nsw_1(i64 %a) {
1060  %shl = shl nsw i64 1, %a
1061  %cmp = icmp sge i64 %shl, 0
1062  ret i1 %cmp
1063
1064 ; CHECK-LABEL: @icmp_shl_nsw_1
1065 ; CHECK-NEXT: ret i1 true
1066 }
1067
1068 define i1 @icmp_shl_1_V_ugt_2147483648(i32 %V) {
1069   %shl = shl i32 1, %V
1070   %cmp = icmp ugt i32 %shl, 2147483648
1071   ret i1 %cmp
1072
1073 ; CHECK-LABEL: @icmp_shl_1_V_ugt_2147483648(
1074 ; CHECK-NEXT: ret i1 false
1075 }
1076
1077 define i1 @icmp_shl_1_V_ule_2147483648(i32 %V) {
1078   %shl = shl i32 1, %V
1079   %cmp = icmp ule i32 %shl, 2147483648
1080   ret i1 %cmp
1081
1082 ; CHECK-LABEL: @icmp_shl_1_V_ule_2147483648(
1083 ; CHECK-NEXT: ret i1 true
1084 }
1085
1086 define i1 @icmp_shl_1_V_eq_31(i32 %V) {
1087   %shl = shl i32 1, %V
1088   %cmp = icmp eq i32 %shl, 31
1089   ret i1 %cmp
1090
1091 ; CHECK-LABEL: @icmp_shl_1_V_eq_31(
1092 ; CHECK-NEXT: ret i1 false
1093 }
1094
1095 define i1 @icmp_shl_1_V_ne_31(i32 %V) {
1096   %shl = shl i32 1, %V
1097   %cmp = icmp ne i32 %shl, 31
1098   ret i1 %cmp
1099
1100 ; CHECK-LABEL: @icmp_shl_1_V_ne_31(
1101 ; CHECK-NEXT: ret i1 true
1102 }
1103
1104 define i1 @tautological1(i32 %A, i32 %B) {
1105   %C = and i32 %A, %B
1106   %D = icmp ugt i32 %C, %A
1107   ret i1 %D
1108 ; CHECK-LABEL: @tautological1(
1109 ; CHECK: ret i1 false
1110 }
1111
1112 define i1 @tautological2(i32 %A, i32 %B) {
1113   %C = and i32 %A, %B
1114   %D = icmp ule i32 %C, %A
1115   ret i1 %D
1116 ; CHECK-LABEL: @tautological2(
1117 ; CHECK: ret i1 true
1118 }
1119
1120 define i1 @tautological3(i32 %A, i32 %B) {
1121   %C = or i32 %A, %B
1122   %D = icmp ule i32 %A, %C
1123   ret i1 %D
1124 ; CHECK-LABEL: @tautological3(
1125 ; CHECK: ret i1 true
1126 }
1127
1128 define i1 @tautological4(i32 %A, i32 %B) {
1129   %C = or i32 %A, %B
1130   %D = icmp ugt i32 %A, %C
1131   ret i1 %D
1132 ; CHECK-LABEL: @tautological4(
1133 ; CHECK: ret i1 false
1134 }
1135
1136 define i1 @tautological5(i32 %A, i32 %B) {
1137   %C = or i32 %A, %B
1138   %D = icmp ult i32 %C, %A
1139   ret i1 %D
1140 ; CHECK-LABEL: @tautological5(
1141 ; CHECK: ret i1 false
1142 }
1143
1144 define i1 @tautological6(i32 %A, i32 %B) {
1145   %C = or i32 %A, %B
1146   %D = icmp uge i32 %C, %A
1147   ret i1 %D
1148 ; CHECK-LABEL: @tautological6(
1149 ; CHECK: ret i1 true
1150 }
1151
1152 define i1 @tautological7(i32 %A, i32 %B) {
1153   %C = and i32 %A, %B
1154   %D = icmp uge i32 %A, %C
1155   ret i1 %D
1156 ; CHECK-LABEL: @tautological7(
1157 ; CHECK: ret i1 true
1158 }
1159
1160 define i1 @tautological8(i32 %A, i32 %B) {
1161   %C = and i32 %A, %B
1162   %D = icmp ult i32 %A, %C
1163   ret i1 %D
1164 ; CHECK-LABEL: @tautological8(
1165 ; CHECK: ret i1 false
1166 }