1; RUN: opt -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 63; Undef handling. 64define 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 70T1: 71 ret i32 42 72 73F1: 74 ret i32 17 75} 76 77define i32 @test4(i1 %cond, i1 %cond2) { 78; CHECK-LABEL: @test4( 79 80 br i1 %cond, label %T1, label %F1 81 82T1: 83; CHECK: %v1 = call i32 @f1() 84; CHECK-NEXT: br label %T 85 86 %v1 = call i32 @f1() 87 br label %Merge 88 89F1: 90 %v2 = call i32 @f2() 91; CHECK: %v2 = call i32 @f2() 92; CHECK-NEXT: br i1 %cond2, 93 br label %Merge 94 95Merge: 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 100T2: 101 call void @f3() 102 ret i32 %B 103 104F2: 105 ret i32 %B 106} 107 108 109;; This tests that the branch in 'merge' can be cloned up into T1. 110define i32 @test5(i1 %cond, i1 %cond2) { 111; CHECK-LABEL: @test5( 112 113 br i1 %cond, label %T1, label %F1 114 115T1: 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 125F1: 126 %v2 = call i32 @f2() 127 br label %Merge 128 129Merge: 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 134T2: 135 call void @f3() 136 ret i32 %B 137 138F2: 139 ret i32 %B 140} 141 142 143;; Lexically duplicated conditionals should be threaded. 144 145 146define 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 160BB2: 161 call i32 @f1() 162 br label %BB1 163 164 165BB1: 166 %tmp459 = icmp eq i32 %A, 42 167 br i1 %tmp459, label %BB3, label %BB4 168 169BB3: 170 call i32 @f2() 171 ret i32 3 172 173BB4: 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 181define i32 @test7(i1 %cond, i1 %cond2) { 182Entry: 183; CHECK-LABEL: @test7( 184 %v1 = call i32 @f1() 185 br i1 %cond, label %Merge, label %F1 186 187F1: 188 %v2 = call i32 @f2() 189 br label %Merge 190 191Merge: 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 202T2: 203 call void @f3() 204 ret i32 %B 205 206F2: 207 ret i32 %B 208; CHECK: F2: 209; CHECK-NEXT: phi i32 210} 211 212 213declare i1 @test8a() 214 215define i32 @test8b(i1 %cond, i1 %cond2) { 216; CHECK-LABEL: @test8b( 217T0: 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 225T1: 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 232T2: 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 239T3: 240 ret i32 0 241 242F1: 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 247X: 248 call i1 @test8a() 249 ret i32 1 250Y: 251 ret i32 2 252} 253 254 255;;; Verify that we can handle constraint propagation through "xor x, 1". 256define i32 @test9(i1 %cond, i1 %cond2) { 257Entry: 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 266F1: 267 %v2 = call i32 @f2() 268 br label %Merge 269 270Merge: 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 282T2: 283 %Q = zext i1 %M to i32 284 ret i32 %Q 285 286F2: 287 ret i32 %B 288; CHECK: F2: 289; CHECK-NEXT: phi i32 290} 291 292 293 294; CHECK: @test10 295declare i32 @test10f1() 296declare i32 @test10f2() 297declare void @test10f3() 298 299;; Non-local condition threading. 300define 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 305T1: 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 313F1: 314 %v2 = call i32 @test10f2() 315 br label %Merge 316 317Merge: 318 %B = phi i32 [%v1, %T1], [%v2, %F1] 319 br i1 %cond, label %T2, label %F2 320 321T2: 322 call void @f3() 323 ret i32 %B 324 325F2: 326 ret i32 %B 327} 328 329 330; Impossible conditional constraints should get threaded. BB3 is dead here. 331define 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 338BB2: 339; CHECK: call i32 @f1() 340; CHECK-NEXT: ret i32 %C 341 %C = call i32 @f1() 342 ret i32 %C 343 344 345BB1: 346 %tmp459 = icmp eq i32 %A, 43 347 br i1 %tmp459, label %BB3, label %BB4 348 349BB3: 350 call i32 @f2() 351 ret i32 3 352 353BB4: 354 call void @f3() 355 ret i32 4 356} 357 358;; Correlated value through boolean expression. GCC PR18046. 359define void @test12(i32 %A) { 360; CHECK-LABEL: @test12( 361entry: 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 369bb: 370 %B = call i32 @test10f2() 371 br label %bb1 372 373bb1: 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 383bb2: 384 %D = call i32 @test10f2() 385 ret void 386 387return: 388 ret void 389} 390 391 392;; Duplicate condition to avoid xor of cond. 393;; rdar://7391699 394define i32 @test13(i1 %cond, i1 %cond2) { 395Entry: 396; CHECK-LABEL: @test13( 397 %v1 = call i32 @f1() 398 br i1 %cond, label %Merge, label %F1 399 400F1: 401 br label %Merge 402 403Merge: 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 410T2: 411 ret i32 123 412 413F2: 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( 425define i32 @test14(i32 %in) { 426entry: 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: 432left: 433 br label %merge 434 435; CHECK-NOT: right: 436right: 437 %B = call i32 @f1() 438 br label %merge 439 440merge: 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: 448left_ret: 449 ret i32 0 450 451right_ret: 452 ret i32 1 453} 454 455; PR5652 456; CHECK-LABEL: @test15( 457define i32 @test15(i32 %len) { 458entry: 459; CHECK: icmp ult i32 %len, 13 460 %tmp = icmp ult i32 %len, 13 461 br i1 %tmp, label %check, label %exit0 462 463exit0: 464 ret i32 0 465 466check: 467 %tmp9 = icmp ult i32 %len, 21 468 br i1 %tmp9, label %exit1, label %exit2 469 470exit2: 471; CHECK-NOT: ret i32 2 472 ret i32 2 473 474exit1: 475 ret i32 1 476; CHECK: } 477} 478 479;;; Verify that we can handle constraint propagation through cast. 480define i32 @test16(i1 %cond) { 481Entry: 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 488F1: 489 %v1 = call i32 @f1() 490 br label %Merge 491 492Merge: 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 503T2: 504 %Q = call i32 @f2() 505 ret i32 %Q 506 507F2: 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 516declare void @g() 517declare void @j() 518declare void @k() 519 520; CHECK-LABEL: define void @h(i32 %p) { 521define void @h(i32 %p) { 522 %x = icmp ult i32 %p, 5 523 br i1 %x, label %l1, label %l2 524 525l1: 526 call void @j() 527 br label %l3 528 529l2: 530 call void @k() 531 br label %l3 532 533l3: 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 540l4: 541 call void @j() 542 ret void 543 544l5: 545 call void @k() 546 ret void 547; CHECK: } 548} 549 550define i1 @trunc_switch(i1 %arg) { 551; CHECK-LABEL: @trunc_switch 552top: 553; CHECK: br i1 %arg, label %exitA, label %exitB 554 br i1 %arg, label %common, label %B 555 556B: 557 br label %common 558 559common: 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 568unreach: 569 unreachable 570 571exitA: 572 ret i1 true 573 574exitB: 575 ret i1 false 576} 577 578; CHECK-LABEL: define void @h_con(i32 %p) { 579define void @h_con(i32 %p) { 580 %x = icmp ult i32 %p, 5 581 br i1 %x, label %l1, label %l2 582 583l1: 584 call void @j() 585 br label %l3 586 587l2: 588 call void @k() 589 br label %l3 590 591l3: 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 598l4: 599 call void @j() 600 ret void 601 602l5: 603 call void @k() 604 ret void 605; CHECK: } 606} 607 608 609; CHECK: attributes [[$NOD]] = { noduplicate } 610; CHECK: attributes [[$CON]] = { convergent } 611