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 ; CHECK-LABEL: define void @h_con(i32 %p) { 551 define void @h_con(i32 %p) { 552 %x = icmp ult i32 %p, 5 553 br i1 %x, label %l1, label %l2 554 555 l1: 556 call void @j() 557 br label %l3 558 559 l2: 560 call void @k() 561 br label %l3 562 563 l3: 564 ; CHECK: call void @g() [[CON:#[0-9]+]] 565 ; CHECK-NOT: call void @g() [[CON]] 566 call void @g() convergent 567 %y = icmp ult i32 %p, 5 568 br i1 %y, label %l4, label %l5 569 570 l4: 571 call void @j() 572 ret void 573 574 l5: 575 call void @k() 576 ret void 577 ; CHECK: } 578 } 579 580 581 ; CHECK: attributes [[NOD]] = { noduplicate } 582 ; CHECK: attributes [[CON]] = { convergent } 583
