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