610 lines · plain
1; RUN: opt -passes=jump-threading -S < %s | FileCheck %s2 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 %F111 12T1:13 %v1 = call i32 @f1()14 br label %Merge15 16F1:17 %v2 = call i32 @f2()18 br label %Merge19 20Merge:21 %A = phi i1 [true, %T1], [false, %F1]22 %B = phi i32 [%v1, %T1], [%v2, %F1]23 br i1 %A, label %T2, label %F224 25T2:26; CHECK: T2:27; CHECK: ret i32 %v128 call void @f3()29 ret i32 %B30 31F2:32; CHECK: F2:33; CHECK: ret i32 %v234 ret i32 %B35}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 %F143 44T1:45; CHECK: %v1 = call i32 @f1()46; CHECK: ret i32 4747 %v1 = call i32 @f1()48 br label %Merge49 50F1:51 br i1 %cond, label %Merge, label %F252 53Merge:54 %B = phi i32 [47, %T1], [192, %F1]55 ret i32 %B56 57F2:58 call void @f3()59 ret i32 1260}61 62 63define i32 @test3(i1 %cond) {64; CHECK-LABEL: @test3(65; CHECK-NEXT: T1:66; CHECK-NEXT: ret i32 4267 br i1 true, label %T1, label %F168 69T1:70 ret i32 4271 72F1:73 ret i32 1774}75 76define i32 @test4(i1 %cond, i1 %cond2) {77; CHECK-LABEL: @test4(78 79 br i1 %cond, label %T1, label %F180 81T1:82; CHECK: %v1 = call i32 @f1()83; CHECK-NEXT: br label %T84 85 %v1 = call i32 @f1()86 br label %Merge87 88F1:89 %v2 = call i32 @f2()90; CHECK: %v2 = call i32 @f2()91; CHECK-NEXT: br i1 %cond2,92 br label %Merge93 94Merge:95 %A = phi i1 [undef, %T1], [%cond2, %F1]96 %B = phi i32 [%v1, %T1], [%v2, %F1]97 br i1 %A, label %T2, label %F298 99T2:100 call void @f3()101 ret i32 %B102 103F2:104 ret i32 %B105}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 %F1113 114T1:115; CHECK: T1:116; CHECK-NEXT: %v1 = call i32 @f1()117; CHECK-NEXT: %cond3 = icmp eq i32 %v1, 412118; CHECK-NEXT: br i1 %cond3, label %T2, label %F2119 120 %v1 = call i32 @f1()121 %cond3 = icmp eq i32 %v1, 412122 br label %Merge123 124F1:125 %v2 = call i32 @f2()126 br label %Merge127 128Merge:129 %A = phi i1 [%cond3, %T1], [%cond2, %F1]130 %B = phi i32 [%v1, %T1], [%v2, %F1]131 br i1 %A, label %T2, label %F2132 133T2:134 call void @f3()135 ret i32 %B136 137F2:138 ret i32 %B139}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, 42148 br i1 %tmp455, label %BB1, label %BB2149 150; CHECK: call i32 @f2()151; CHECK-NEXT: ret i32 3152 153; CHECK: call i32 @f1()154; CHECK-NOT: br155; CHECK: call void @f3()156; CHECK-NOT: br157; CHECK: ret i32 4158 159BB2:160 call i32 @f1()161 br label %BB1162 163 164BB1:165 %tmp459 = icmp eq i32 %A, 42166 br i1 %tmp459, label %BB3, label %BB4167 168BB3:169 call i32 @f2()170 ret i32 3171 172BB4:173 call void @f3()174 ret i32 4175}176 177 178;; This tests that the branch in 'merge' can be cloned up into T1.179;; rdar://7367025180define i32 @test7(i1 %cond, i1 %cond2) {181Entry:182; CHECK-LABEL: @test7(183 %v1 = call i32 @f1()184 br i1 %cond, label %Merge, label %F1185 186F1:187 %v2 = call i32 @f2()188 br label %Merge189 190Merge:191 %B = phi i32 [%v1, %Entry], [%v2, %F1]192 %M = icmp ne i32 %B, %v1193 %N = icmp eq i32 %B, 47194 %O = and i1 %M, %N195 br i1 %O, label %T2, label %F2196 197; CHECK: Merge:198; CHECK-NOT: phi199; CHECK-NEXT: %v2 = call i32 @f2()200 201T2:202 call void @f3()203 ret i32 %B204 205F2:206 ret i32 %B207; CHECK: F2:208; CHECK-NEXT: phi i32209}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 %F1219 220; CHECK: T0:221; CHECK-NEXT: call222; CHECK-NEXT: br i1 %A, label %T1, label %Y223 224T1:225 %B = call i1 @test8a()226 br i1 %B, label %T2, label %F1227 228; CHECK: T1:229; CHECK-NEXT: call230; CHECK-NEXT: br i1 %B, label %T2, label %Y231T2:232 %C = call i1 @test8a()233 br i1 %cond, label %T3, label %F1234 235; CHECK: T2:236; CHECK-NEXT: call237; CHECK-NEXT: br i1 %cond, label %T3, label %Y238T3:239 ret i32 0240 241F1:242 %D = phi i32 [0, %T0], [0, %T1], [1, %T2]243 %E = icmp eq i32 %D, 1244 %F = and i1 %E, %cond245 br i1 %F, label %X, label %Y246X:247 call i1 @test8a()248 ret i32 1249Y:250 ret i32 2251}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 %F1260 261; CHECK: Entry:262; CHECK-NEXT: %v1 = call i32 @f1()263; CHECK-NEXT: br i1 %cond, label %F2, label %Merge264 265F1:266 %v2 = call i32 @f2()267 br label %Merge268 269Merge:270 %B = phi i32 [%v1, %Entry], [%v2, %F1]271 %M = icmp eq i32 %B, %v1272 %M1 = xor i1 %M, 1273 %N = icmp eq i32 %B, 47274 %O = and i1 %M1, %N275 br i1 %O, label %T2, label %F2276 277; CHECK: Merge:278; CHECK-NOT: phi279; CHECK-NEXT: %v2 = call i32 @f2()280 281T2:282 %Q = zext i1 %M to i32283 ret i32 %Q284 285F2:286 ret i32 %B287; CHECK: F2:288; CHECK-NEXT: phi i32289}290 291 292 293; CHECK: @test10294declare 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 %F2302 br i1 %cond, label %T1, label %F1303 304T1:305 %v1 = call i32 @test10f1()306 br label %Merge307 308; CHECK: %v1 = call i32 @test10f1()309; CHECK-NEXT: call void @f3()310; CHECK-NEXT: ret i32 %v1311 312F1:313 %v2 = call i32 @test10f2()314 br label %Merge315 316Merge:317 %B = phi i32 [%v1, %T1], [%v2, %F1]318 br i1 %cond, label %T2, label %F2319 320T2:321 call void @f3()322 ret i32 %B323 324F2:325 ret i32 %B326}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: icmp333; CHECK-NEXT: br i1 %tmp455, label %BB4, label %BB2334 %tmp455 = icmp eq i32 %A, 42335 br i1 %tmp455, label %BB1, label %BB2336 337BB2:338; CHECK: call i32 @f1()339; CHECK-NEXT: ret i32 %C340 %C = call i32 @f1()341 ret i32 %C342 343 344BB1:345 %tmp459 = icmp eq i32 %A, 43346 br i1 %tmp459, label %BB3, label %BB4347 348BB3:349 call i32 @f2()350 ret i32 3351 352BB4:353 call void @f3()354 ret i32 4355}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, 0362 br i1 %cond, label %bb, label %bb1363; Should branch to the return block instead of through BB1.364; CHECK: entry:365; CHECK-NEXT: %cond = icmp eq i32 %A, 0366; CHECK-NEXT: br i1 %cond, label %bb1, label %return367 368bb:369 %B = call i32 @test10f2()370 br label %bb1371 372bb1:373 %C = phi i32 [ %A, %entry ], [ %B, %bb ]374 %cond4 = icmp eq i32 %C, 0375 br i1 %cond4, label %bb2, label %return376 377; CHECK: bb1:378; CHECK-NEXT: %B = call i32 @test10f2()379; CHECK-NEXT: %cond4 = icmp eq i32 %B, 0380; CHECK-NEXT: br i1 %cond4, label %bb2, label %return381 382bb2:383 %D = call i32 @test10f2()384 ret void385 386return:387 ret void388}389 390 391;; Duplicate condition to avoid xor of cond.392;; rdar://7391699393define i32 @test13(i1 %cond, i1 %cond2) {394Entry:395; CHECK-LABEL: @test13(396 %v1 = call i32 @f1()397 br i1 %cond, label %Merge, label %F1398 399F1:400 br label %Merge401 402Merge:403 %B = phi i1 [true, %Entry], [%cond2, %F1]404 %C = phi i32 [192, %Entry], [%v1, %F1]405 %M = icmp eq i32 %C, 192406 %N = xor i1 %B, %M407 br i1 %N, label %T2, label %F2408 409T2:410 ret i32 123411 412F2:413 ret i32 %v1414 415; CHECK: br i1 %cond, label %F2, label %Merge416 417; CHECK: Merge:418; CHECK-NEXT: %M = icmp eq i32 %v1, 192419; CHECK-NEXT: %N = xor i1 %cond2, %M420; CHECK-NEXT: br i1 %N, label %T2, label %F2421}422 423; CHECK-LABEL: @test14(424define i32 @test14(i32 %in) {425entry:426 %A = icmp eq i32 %in, 0427; CHECK: br i1 %A, label %right_ret, label %merge428 br i1 %A, label %left, label %right429 430; CHECK-NOT: left:431left:432 br label %merge433 434; CHECK-NOT: right:435right:436 %B = call i32 @f1()437 br label %merge438 439merge:440; CHECK-NOT: %C = phi i32 [%in, %left], [%B, %right]441 %C = phi i32 [%in, %left], [%B, %right]442 %D = add i32 %C, 1443 %E = icmp eq i32 %D, 2444 br i1 %E, label %left_ret, label %right_ret445 446; CHECK: left_ret:447left_ret:448 ret i32 0449 450right_ret:451 ret i32 1452}453 454; PR5652455; CHECK-LABEL: @test15(456define i32 @test15(i32 %len) {457entry:458; CHECK: icmp ult i32 %len, 13459 %tmp = icmp ult i32 %len, 13460 br i1 %tmp, label %check, label %exit0461 462exit0:463 ret i32 0464 465check:466 %tmp9 = icmp ult i32 %len, 21467 br i1 %tmp9, label %exit1, label %exit2468 469exit2:470; CHECK-NOT: ret i32 2471 ret i32 2472 473exit1:474 ret i32 1475; 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 %F1483 484; CHECK: Entry:485; CHECK-NEXT: br i1 %cond, label %F2, label %Merge486 487F1:488 %v1 = call i32 @f1()489 br label %Merge490 491Merge:492 %B = phi i32 [0, %Entry], [%v1, %F1]493 %M = icmp eq i32 %B, 0494 %M1 = zext i1 %M to i32495 %N = icmp eq i32 %M1, 0496 br i1 %N, label %T2, label %F2497 498; CHECK: Merge:499; CHECK-NOT: phi500; CHECK-NEXT: %v1 = call i32 @f1()501 502T2:503 %Q = call i32 @f2()504 ret i32 %Q505 506F2:507 ret i32 %B508; CHECK: F2:509; CHECK-NEXT: phi i32510}511 512; In this test we check that block duplication is inhibited by the presence513; 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, 5522 br i1 %x, label %l1, label %l2523 524l1:525 call void @j()526 br label %l3527 528l2:529 call void @k()530 br label %l3531 532l3:533; CHECK: call void @g() [[$NOD:#[0-9]+]]534; CHECK-NOT: call void @g() [[$NOD]]535 call void @g() noduplicate536 %y = icmp ult i32 %p, 5537 br i1 %y, label %l4, label %l5538 539l4:540 call void @j()541 ret void542 543l5:544 call void @k()545 ret void546; CHECK: }547}548 549define i1 @trunc_switch(i1 %arg) {550; CHECK-LABEL: @trunc_switch551top:552; CHECK: br i1 %arg, label %exitA, label %exitB553 br i1 %arg, label %common, label %B554 555B:556 br label %common557 558common:559 %phi = phi i8 [ 2, %B ], [ 1, %top ]560 %trunc = trunc i8 %phi to i2561; CHECK-NOT: switch562 switch i2 %trunc, label %unreach [563 i2 1, label %exitA564 i2 -2, label %exitB565 ]566 567unreach:568 unreachable569 570exitA:571 ret i1 true572 573exitB:574 ret i1 false575}576 577; CHECK-LABEL: define void @h_con(i32 %p) {578define void @h_con(i32 %p) {579 %x = icmp ult i32 %p, 5580 br i1 %x, label %l1, label %l2581 582l1:583 call void @j()584 br label %l3585 586l2:587 call void @k()588 br label %l3589 590l3:591; CHECK: call void @g() [[$CON:#[0-9]+]]592; CHECK-NOT: call void @g() [[$CON]]593 call void @g() convergent594 %y = icmp ult i32 %p, 5595 br i1 %y, label %l4, label %l5596 597l4:598 call void @j()599 ret void600 601l5:602 call void @k()603 ret void604; CHECK: }605}606 607 608; CHECK: attributes [[$NOD]] = { noduplicate }609; CHECK: attributes [[$CON]] = { convergent }610