test/Transforms/JumpThreading/basic.ll

   1 ; RUN: opt -jump-threading -S < %s | FileCheck %s
   2
   3 declare i32 @f1()
   4 declare i32 @f2()
   5 declare void @f3()
   6
   7 define i32 @test1(i1 %cond) {
   8 ; CHECK-LABEL: @test1(
   9
  10         br i1 %cond, label %T1, label %F1
  11
  12 T1:
  13         %v1 = call i32 @f1()
  14         br label %Merge
  15
  16 F1:
  17         %v2 = call i32 @f2()
  18         br label %Merge
  19
  20 Merge:
  21         %A = phi i1 [true, %T1], [false, %F1]
  22         %B = phi i32 [%v1, %T1], [%v2, %F1]
  23         br i1 %A, label %T2, label %F2
  24
  25 T2:
  26 ; CHECK: T2:
  27 ; CHECK: ret i32 %v1
  28         call void @f3()
  29         ret i32 %B
  30
  31 F2:
  32 ; CHECK: F2:
  33 ; CHECK: ret i32 %v2
  34         ret i32 %B
  35 }
  36
  37
  38 ;; cond is known false on Entry -> F1 edge!
  39 define i32 @test2(i1 %cond) {
  40 ; CHECK-LABEL: @test2(
  41 Entry:
  42         br i1 %cond, label %T1, label %F1
  43
  44 T1:
  45 ; CHECK: %v1 = call i32 @f1()
  46 ; CHECK: ret i32 47
  47         %v1 = call i32 @f1()
  48         br label %Merge
  49
  50 F1:
  51         br i1 %cond, label %Merge, label %F2
  52
  53 Merge:
  54         %B = phi i32 [47, %T1], [192, %F1]
  55         ret i32 %B
  56
  57 F2:
  58         call void @f3()
  59         ret i32 12
  60 }
  61
  62
  63 ; Undef handling.
  64 define i32 @test3(i1 %cond) {
  65 ; CHECK-LABEL: @test3(
  66 ; CHECK-NEXT: T1:
  67 ; CHECK-NEXT: ret i32 42
  68         br i1 undef, label %T1, label %F1
  69
  70 T1:
  71         ret i32 42
  72
  73 F1:
  74         ret i32 17
  75 }
  76
  77 define i32 @test4(i1 %cond, i1 %cond2) {
  78 ; CHECK-LABEL: @test4(
  79
  80         br i1 %cond, label %T1, label %F1
  81
  82 T1:
  83 ; CHECK:   %v1 = call i32 @f1()
  84 ; CHECK-NEXT:   br label %T
  85
  86         %v1 = call i32 @f1()
  87         br label %Merge
  88
  89 F1:
  90         %v2 = call i32 @f2()
  91 ; CHECK:   %v2 = call i32 @f2()
  92 ; CHECK-NEXT:   br i1 %cond2,
  93         br label %Merge
  94
  95 Merge:
  96         %A = phi i1 [undef, %T1], [%cond2, %F1]
  97         %B = phi i32 [%v1, %T1], [%v2, %F1]
  98         br i1 %A, label %T2, label %F2
  99
 100 T2:
 101         call void @f3()
 102         ret i32 %B
 103
 104 F2:
 105         ret i32 %B
 106 }
 107
 108
 109 ;; This tests that the branch in 'merge' can be cloned up into T1.
 110 define i32 @test5(i1 %cond, i1 %cond2) {
 111 ; CHECK-LABEL: @test5(
 112
 113         br i1 %cond, label %T1, label %F1
 114
 115 T1:
 116 ; CHECK: T1:
 117 ; CHECK-NEXT:   %v1 = call i32 @f1()
 118 ; CHECK-NEXT:   %cond3 = icmp eq i32 %v1, 412
 119 ; CHECK-NEXT:   br i1 %cond3, label %T2, label %F2
 120
 121         %v1 = call i32 @f1()
 122         %cond3 = icmp eq i32 %v1, 412
 123         br label %Merge
 124
 125 F1:
 126         %v2 = call i32 @f2()
 127         br label %Merge
 128
 129 Merge:
 130         %A = phi i1 [%cond3, %T1], [%cond2, %F1]
 131         %B = phi i32 [%v1, %T1], [%v2, %F1]
 132         br i1 %A, label %T2, label %F2
 133
 134 T2:
 135         call void @f3()
 136         ret i32 %B
 137
 138 F2:
 139         ret i32 %B
 140 }
 141
 142
 143 ;; Lexically duplicated conditionals should be threaded.
 144
 145
 146 define i32 @test6(i32 %A) {
 147 ; CHECK-LABEL: @test6(
 148         %tmp455 = icmp eq i32 %A, 42
 149         br i1 %tmp455, label %BB1, label %BB2
 150
 151 ; CHECK: call i32 @f2()
 152 ; CHECK-NEXT: ret i32 3
 153
 154 ; CHECK: call i32 @f1()
 155 ; CHECK-NOT: br
 156 ; CHECK: call void @f3()
 157 ; CHECK-NOT: br
 158 ; CHECK: ret i32 4
 159
 160 BB2:
 161         call i32 @f1()
 162         br label %BB1
 163
 164
 165 BB1:
 166         %tmp459 = icmp eq i32 %A, 42
 167         br i1 %tmp459, label %BB3, label %BB4
 168
 169 BB3:
 170         call i32 @f2()
 171         ret i32 3
 172
 173 BB4:
 174         call void @f3()
 175         ret i32 4
 176 }
 177
 178
 179 ;; This tests that the branch in 'merge' can be cloned up into T1.
 180 ;; rdar://7367025
 181 define i32 @test7(i1 %cond, i1 %cond2) {
 182 Entry:
 183 ; CHECK-LABEL: @test7(
 184         %v1 = call i32 @f1()
 185         br i1 %cond, label %Merge, label %F1
 186
 187 F1:
 188         %v2 = call i32 @f2()
 189         br label %Merge
 190
 191 Merge:
 192         %B = phi i32 [%v1, %Entry], [%v2, %F1]
 193         %M = icmp ne i32 %B, %v1
 194         %N = icmp eq i32 %B, 47
 195         %O = and i1 %M, %N
 196         br i1 %O, label %T2, label %F2
 197
 198 ; CHECK: Merge:
 199 ; CHECK-NOT: phi
 200 ; CHECK-NEXT:   %v2 = call i32 @f2()
 201
 202 T2:
 203         call void @f3()
 204         ret i32 %B
 205
 206 F2:
 207         ret i32 %B
 208 ; CHECK: F2:
 209 ; CHECK-NEXT: phi i32
 210 }
 211
 212
 213 declare i1 @test8a()
 214
 215 define i32 @test8b(i1 %cond, i1 %cond2) {
 216 ; CHECK-LABEL: @test8b(
 217 T0:
 218         %A = call i1 @test8a()
 219         br i1 %A, label %T1, label %F1
 220
 221 ; CHECK: T0:
 222 ; CHECK-NEXT: call
 223 ; CHECK-NEXT: br i1 %A, label %T1, label %Y
 224
 225 T1:
 226         %B = call i1 @test8a()
 227         br i1 %B, label %T2, label %F1
 228
 229 ; CHECK: T1:
 230 ; CHECK-NEXT: call
 231 ; CHECK-NEXT: br i1 %B, label %T2, label %Y
 232 T2:
 233         %C = call i1 @test8a()
 234         br i1 %cond, label %T3, label %F1
 235
 236 ; CHECK: T2:
 237 ; CHECK-NEXT: call
 238 ; CHECK-NEXT: br i1 %cond, label %T3, label %Y
 239 T3:
 240         ret i32 0
 241
 242 F1:
 243         %D = phi i32 [0, %T0], [0, %T1], [1, %T2]
 244         %E = icmp eq i32 %D, 1
 245         %F = and i1 %E, %cond
 246         br i1 %F, label %X, label %Y
 247 X:
 248         call i1 @test8a()
 249         ret i32 1
 250 Y:
 251         ret i32 2
 252 }
 253
 254
 255 ;;; Verify that we can handle constraint propagation through "xor x, 1".
 256 define i32 @test9(i1 %cond, i1 %cond2) {
 257 Entry:
 258 ; CHECK-LABEL: @test9(
 259         %v1 = call i32 @f1()
 260         br i1 %cond, label %Merge, label %F1
 261
 262 ; CHECK: Entry:
 263 ; CHECK-NEXT:  %v1 = call i32 @f1()
 264 ; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
 265
 266 F1:
 267         %v2 = call i32 @f2()
 268         br label %Merge
 269
 270 Merge:
 271         %B = phi i32 [%v1, %Entry], [%v2, %F1]
 272         %M = icmp eq i32 %B, %v1
 273         %M1 = xor i1 %M, 1
 274         %N = icmp eq i32 %B, 47
 275         %O = and i1 %M1, %N
 276         br i1 %O, label %T2, label %F2
 277
 278 ; CHECK: Merge:
 279 ; CHECK-NOT: phi
 280 ; CHECK-NEXT:   %v2 = call i32 @f2()
 281
 282 T2:
 283         %Q = zext i1 %M to i32
 284         ret i32 %Q
 285
 286 F2:
 287         ret i32 %B
 288 ; CHECK: F2:
 289 ; CHECK-NEXT: phi i32
 290 }
 291
 292
 293
 294 ; CHECK: @test10
 295 declare i32 @test10f1()
 296 declare i32 @test10f2()
 297 declare void @test10f3()
 298
 299 ;; Non-local condition threading.
 300 define i32 @test10g(i1 %cond) {
 301 ; CHECK-LABEL: @test10g(
 302 ; CHECK-NEXT:   br i1 %cond, label %T2, label %F2
 303         br i1 %cond, label %T1, label %F1
 304
 305 T1:
 306         %v1 = call i32 @test10f1()
 307         br label %Merge
 308
 309 ; CHECK: %v1 = call i32 @test10f1()
 310 ; CHECK-NEXT: call void @f3()
 311 ; CHECK-NEXT: ret i32 %v1
 312
 313 F1:
 314         %v2 = call i32 @test10f2()
 315         br label %Merge
 316
 317 Merge:
 318         %B = phi i32 [%v1, %T1], [%v2, %F1]
 319         br i1 %cond, label %T2, label %F2
 320
 321 T2:
 322         call void @f3()
 323         ret i32 %B
 324
 325 F2:
 326         ret i32 %B
 327 }
 328
 329
 330 ; Impossible conditional constraints should get threaded.  BB3 is dead here.
 331 define i32 @test11(i32 %A) {
 332 ; CHECK-LABEL: @test11(
 333 ; CHECK-NEXT: icmp
 334 ; CHECK-NEXT: br i1 %tmp455, label %BB4, label %BB2
 335         %tmp455 = icmp eq i32 %A, 42
 336         br i1 %tmp455, label %BB1, label %BB2
 337
 338 BB2:
 339 ; CHECK: call i32 @f1()
 340 ; CHECK-NEXT: ret i32 %C
 341         %C = call i32 @f1()
 342         ret i32 %C
 343
 344
 345 BB1:
 346         %tmp459 = icmp eq i32 %A, 43
 347         br i1 %tmp459, label %BB3, label %BB4
 348
 349 BB3:
 350         call i32 @f2()
 351         ret i32 3
 352
 353 BB4:
 354         call void @f3()
 355         ret i32 4
 356 }
 357
 358 ;; Correlated value through boolean expression.  GCC PR18046.
 359 define void @test12(i32 %A) {
 360 ; CHECK-LABEL: @test12(
 361 entry:
 362   %cond = icmp eq i32 %A, 0
 363   br i1 %cond, label %bb, label %bb1
 364 ; Should branch to the return block instead of through BB1.
 365 ; CHECK: entry:
 366 ; CHECK-NEXT: %cond = icmp eq i32 %A, 0
 367 ; CHECK-NEXT: br i1 %cond, label %bb1, label %return
 368
 369 bb:
 370   %B = call i32 @test10f2()
 371   br label %bb1
 372
 373 bb1:
 374   %C = phi i32 [ %A, %entry ], [ %B, %bb ]
 375   %cond4 = icmp eq i32 %C, 0
 376   br i1 %cond4, label %bb2, label %return
 377
 378 ; CHECK: bb1:
 379 ; CHECK-NEXT: %B = call i32 @test10f2()
 380 ; CHECK-NEXT: %cond4 = icmp eq i32 %B, 0
 381 ; CHECK-NEXT: br i1 %cond4, label %bb2, label %return
 382
 383 bb2:
 384   %D = call i32 @test10f2()
 385   ret void
 386
 387 return:
 388   ret void
 389 }
 390
 391
 392 ;; Duplicate condition to avoid xor of cond.
 393 ;; rdar://7391699
 394 define i32 @test13(i1 %cond, i1 %cond2) {
 395 Entry:
 396 ; CHECK-LABEL: @test13(
 397         %v1 = call i32 @f1()
 398         br i1 %cond, label %Merge, label %F1
 399
 400 F1:
 401         br label %Merge
 402
 403 Merge:
 404         %B = phi i1 [true, %Entry], [%cond2, %F1]
 405         %C = phi i32 [192, %Entry], [%v1, %F1]
 406         %M = icmp eq i32 %C, 192
 407         %N = xor i1 %B, %M
 408         br i1 %N, label %T2, label %F2
 409
 410 T2:
 411         ret i32 123
 412
 413 F2:
 414         ret i32 %v1
 415
 416 ; CHECK:   br i1 %cond, label %F2, label %Merge
 417
 418 ; CHECK:      Merge:
 419 ; CHECK-NEXT:   %M = icmp eq i32 %v1, 192
 420 ; CHECK-NEXT:   %N = xor i1 %cond2, %M
 421 ; CHECK-NEXT:   br i1 %N, label %T2, label %F2
 422 }
 423
 424 ; CHECK-LABEL: @test14(
 425 define i32 @test14(i32 %in) {
 426 entry:
 427         %A = icmp eq i32 %in, 0
 428 ; CHECK: br i1 %A, label %right_ret, label %merge
 429   br i1 %A, label %left, label %right
 430
 431 ; CHECK-NOT: left:
 432 left:
 433         br label %merge
 434
 435 ; CHECK-NOT: right:
 436 right:
 437   %B = call i32 @f1()
 438         br label %merge
 439
 440 merge:
 441 ; CHECK-NOT: %C = phi i32 [%in, %left], [%B, %right]
 442         %C = phi i32 [%in, %left], [%B, %right]
 443         %D = add i32 %C, 1
 444         %E = icmp eq i32 %D, 2
 445         br i1 %E, label %left_ret, label %right_ret
 446
 447 ; CHECK: left_ret:
 448 left_ret:
 449         ret i32 0
 450
 451 right_ret:
 452         ret i32 1
 453 }
 454
 455 ; PR5652
 456 ; CHECK-LABEL: @test15(
 457 define i32 @test15(i32 %len) {
 458 entry:
 459 ; CHECK: icmp ult i32 %len, 13
 460   %tmp = icmp ult i32 %len, 13
 461   br i1 %tmp, label %check, label %exit0
 462
 463 exit0:
 464   ret i32 0
 465
 466 check:
 467   %tmp9 = icmp ult i32 %len, 21
 468   br i1 %tmp9, label %exit1, label %exit2
 469
 470 exit2:
 471 ; CHECK-NOT: ret i32 2
 472   ret i32 2
 473
 474 exit1:
 475   ret i32 1
 476 ; CHECK: }
 477 }
 478
 479 ;;; Verify that we can handle constraint propagation through cast.
 480 define i32 @test16(i1 %cond) {
 481 Entry:
 482 ; CHECK-LABEL: @test16(
 483         br i1 %cond, label %Merge, label %F1
 484
 485 ; CHECK: Entry:
 486 ; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
 487
 488 F1:
 489         %v1 = call i32 @f1()
 490         br label %Merge
 491
 492 Merge:
 493         %B = phi i32 [0, %Entry], [%v1, %F1]
 494         %M = icmp eq i32 %B, 0
 495         %M1 = zext i1 %M to i32
 496         %N = icmp eq i32 %M1, 0
 497         br i1 %N, label %T2, label %F2
 498
 499 ; CHECK: Merge:
 500 ; CHECK-NOT: phi
 501 ; CHECK-NEXT:   %v1 = call i32 @f1()
 502
 503 T2:
 504         %Q = call i32 @f2()
 505         ret i32 %Q
 506
 507 F2:
 508         ret i32 %B
 509 ; CHECK: F2:
 510 ; CHECK-NEXT: phi i32
 511 }
 512
 513 ; In this test we check that block duplication is inhibited by the presence
 514 ; of a function with the 'noduplicate' attribute.
 515
 516 declare void @g()
 517 declare void @j()
 518 declare void @k()
 519
 520 ; CHECK-LABEL: define void @h(i32 %p) {
 521 define void @h(i32 %p) {
 522   %x = icmp ult i32 %p, 5
 523   br i1 %x, label %l1, label %l2
 524
 525 l1:
 526   call void @j()
 527   br label %l3
 528
 529 l2:
 530   call void @k()
 531   br label %l3
 532
 533 l3:
 534 ; CHECK: call void @g() [[$NOD:#[0-9]+]]
 535 ; CHECK-NOT: call void @g() [[$NOD]]
 536   call void @g() noduplicate
 537   %y = icmp ult i32 %p, 5
 538   br i1 %y, label %l4, label %l5
 539
 540 l4:
 541   call void @j()
 542   ret void
 543
 544 l5:
 545   call void @k()
 546   ret void
 547 ; CHECK: }
 548 }
 549
 550 define i1 @trunc_switch(i1 %arg) {
 551 ; CHECK-LABEL: @trunc_switch
 552 top:
 553 ; CHECK: br i1 %arg, label %exitA, label %exitB
 554   br i1 %arg, label %common, label %B
 555
 556 B:
 557   br label %common
 558
 559 common:
 560   %phi = phi i8 [ 2, %B ], [ 1, %top ]
 561   %trunc = trunc i8 %phi to i2
 562 ; CHECK-NOT: switch
 563   switch i2 %trunc, label %unreach [
 564     i2 1, label %exitA
 565     i2 -2, label %exitB
 566   ]
 567
 568 unreach:
 569   unreachable
 570
 571 exitA:
 572   ret i1 true
 573
 574 exitB:
 575   ret i1 false
 576 }
 577
 578 ; CHECK-LABEL: define void @h_con(i32 %p) {
 579 define void @h_con(i32 %p) {
 580   %x = icmp ult i32 %p, 5
 581   br i1 %x, label %l1, label %l2
 582
 583 l1:
 584   call void @j()
 585   br label %l3
 586
 587 l2:
 588   call void @k()
 589   br label %l3
 590
 591 l3:
 592 ; CHECK: call void @g() [[$CON:#[0-9]+]]
 593 ; CHECK-NOT: call void @g() [[$CON]]
 594   call void @g() convergent
 595   %y = icmp ult i32 %p, 5
 596   br i1 %y, label %l4, label %l5
 597
 598 l4:
 599   call void @j()
 600   ret void
 601
 602 l5:
 603   call void @k()
 604   ret void
 605 ; CHECK: }
 606 }
 607
 608
 609 ; CHECK: attributes [[$NOD]] = { noduplicate }
 610 ; CHECK: attributes [[$CON]] = { convergent }