1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2 ; RUN: opt -simplifycfg -S -o - < %s | FileCheck %s 3 4 declare void @helper(i32) 5 6 define void @test1(i1 %a, i1 %b) { 7 ; CHECK-LABEL: @test1( 8 entry: 9 br i1 %a, label %Y, label %X, !prof !0 10 ; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !0 11 12 X: 13 %c = or i1 %b, false 14 br i1 %c, label %Z, label %Y, !prof !1 15 16 Y: 17 call void @helper(i32 0) 18 ret void 19 20 Z: 21 call void @helper(i32 1) 22 ret void 23 } 24 25 ; Make sure the metadata name string is "branch_weights" before propagating it. 26 27 define void @fake_weights(i1 %a, i1 %b) { 28 ; CHECK-LABEL: @fake_weights( 29 entry: 30 br i1 %a, label %Y, label %X, !prof !12 31 ; CHECK: %or.cond = and i1 %a.not, %c 32 ; CHECK-NEXT: br i1 %or.cond, label %Z, label %Y, !prof !1 33 ; CHECK: Y: 34 X: 35 %c = or i1 %b, false 36 br i1 %c, label %Z, label %Y, !prof !1 37 38 Y: 39 call void @helper(i32 0) 40 ret void 41 42 Z: 43 call void @helper(i32 1) 44 ret void 45 } 46 47 define void @test2(i1 %a, i1 %b) { 48 ; CHECK-LABEL: @test2( 49 entry: 50 br i1 %a, label %X, label %Y, !prof !1 51 ; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !2 52 ; CHECK-NOT: !prof 53 54 X: 55 %c = or i1 %b, false 56 br i1 %c, label %Z, label %Y, !prof !2 57 58 Y: 59 call void @helper(i32 0) 60 ret void 61 62 Z: 63 call void @helper(i32 1) 64 ret void 65 } 66 67 define void @test3(i1 %a, i1 %b) { 68 ; CHECK-LABEL: @test3( 69 ; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !1 70 entry: 71 br i1 %a, label %X, label %Y, !prof !1 72 73 X: 74 %c = or i1 %b, false 75 br i1 %c, label %Z, label %Y 76 77 Y: 78 call void @helper(i32 0) 79 ret void 80 81 Z: 82 call void @helper(i32 1) 83 ret void 84 } 85 86 define void @test4(i1 %a, i1 %b) { 87 ; CHECK-LABEL: @test4( 88 ; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !1 89 entry: 90 br i1 %a, label %X, label %Y 91 92 X: 93 %c = or i1 %b, false 94 br i1 %c, label %Z, label %Y, !prof !1 95 96 Y: 97 call void @helper(i32 0) 98 ret void 99 100 Z: 101 call void @helper(i32 1) 102 ret void 103 } 104 105 ;; test5 - The case where it jumps to the default target will be removed. 106 define void @test5(i32 %M, i32 %N) nounwind uwtable { 107 entry: 108 switch i32 %N, label %sw2 [ 109 i32 1, label %sw2 110 i32 2, label %sw.bb 111 i32 3, label %sw.bb1 112 ], !prof !3 113 ; CHECK-LABEL: @test5( 114 ; CHECK: switch i32 %N, label %sw2 [ 115 ; CHECK: i32 3, label %sw.bb1 116 ; CHECK: i32 2, label %sw.bb 117 ; CHECK: ], !prof !3 118 119 sw.bb: 120 call void @helper(i32 0) 121 br label %sw.epilog 122 123 sw.bb1: 124 call void @helper(i32 1) 125 br label %sw.epilog 126 127 sw2: 128 call void @helper(i32 2) 129 br label %sw.epilog 130 131 sw.epilog: 132 ret void 133 } 134 135 ;; test6 - Some cases of the second switch are pruned during optimization. 136 ;; Then the second switch will be converted to a branch, finally, the first 137 ;; switch and the branch will be merged into a single switch. 138 define void @test6(i32 %M, i32 %N) nounwind uwtable { 139 entry: 140 switch i32 %N, label %sw2 [ 141 i32 1, label %sw2 142 i32 2, label %sw.bb 143 i32 3, label %sw.bb1 144 ], !prof !4 145 ; CHECK-LABEL: @test6( 146 ; CHECK: switch i32 %N, label %sw.epilog 147 ; CHECK: i32 3, label %sw.bb1 148 ; CHECK: i32 2, label %sw.bb 149 ; CHECK: i32 4, label %sw.bb5 150 ; CHECK: ], !prof !4 151 152 sw.bb: 153 call void @helper(i32 0) 154 br label %sw.epilog 155 156 sw.bb1: 157 call void @helper(i32 1) 158 br label %sw.epilog 159 160 sw2: 161 ;; Here "case 2" is invalidated since the default case of the first switch 162 ;; does not include "case 2". 163 switch i32 %N, label %sw.epilog [ 164 i32 2, label %sw.bb4 165 i32 4, label %sw.bb5 166 ], !prof !5 167 168 sw.bb4: 169 call void @helper(i32 2) 170 br label %sw.epilog 171 172 sw.bb5: 173 call void @helper(i32 3) 174 br label %sw.epilog 175 176 sw.epilog: 177 ret void 178 } 179 180 ;; This test is based on test1 but swapped the targets of the second branch. 181 define void @test1_swap(i1 %a, i1 %b) { 182 ; CHECK-LABEL: @test1_swap( 183 entry: 184 br i1 %a, label %Y, label %X, !prof !0 185 ; CHECK: br i1 %or.cond, label %Y, label %Z, !prof !5 186 187 X: 188 %c = or i1 %b, false 189 br i1 %c, label %Y, label %Z, !prof !1 190 191 Y: 192 call void @helper(i32 0) 193 ret void 194 195 Z: 196 call void @helper(i32 1) 197 ret void 198 } 199 200 define void @test7(i1 %a, i1 %b) { 201 ; CHECK-LABEL: @test7( 202 entry: 203 %c = or i1 %b, false 204 br i1 %a, label %Y, label %X, !prof !0 205 ; CHECK: br i1 %brmerge, label %Y, label %Z, !prof !6 206 207 X: 208 br i1 %c, label %Y, label %Z, !prof !6 209 210 Y: 211 call void @helper(i32 0) 212 ret void 213 214 Z: 215 call void @helper(i32 1) 216 ret void 217 } 218 219 ; Test basic folding to a conditional branch. 220 define void @test8(i64 %x, i64 %y) nounwind { 221 ; CHECK-LABEL: @test8( 222 entry: 223 %lt = icmp slt i64 %x, %y 224 ; CHECK: br i1 %lt, label %a, label %b, !prof !7 225 %qux = select i1 %lt, i32 0, i32 2 226 switch i32 %qux, label %bees [ 227 i32 0, label %a 228 i32 1, label %b 229 i32 2, label %b 230 ], !prof !7 231 a: 232 call void @helper(i32 0) nounwind 233 ret void 234 b: 235 call void @helper(i32 1) nounwind 236 ret void 237 bees: 238 call void @helper(i32 2) nounwind 239 ret void 240 } 241 242 ; Test edge splitting when the default target has icmp and unconditinal 243 ; branch 244 define i1 @test9(i32 %x, i32 %y) nounwind { 245 ; CHECK-LABEL: @test9( 246 entry: 247 switch i32 %x, label %bees [ 248 i32 0, label %a 249 i32 1, label %end 250 i32 2, label %end 251 ], !prof !7 252 ; CHECK: switch i32 %x, label %bees [ 253 ; CHECK: i32 0, label %a 254 ; CHECK: i32 1, label %end 255 ; CHECK: i32 2, label %end 256 ; CHECK: i32 92, label %end 257 ; CHECK: ], !prof !8 258 259 a: 260 call void @helper(i32 0) nounwind 261 %reta = icmp slt i32 %x, %y 262 ret i1 %reta 263 264 bees: 265 %tmp = icmp eq i32 %x, 92 266 br label %end 267 268 end: 269 ; CHECK: end: 270 ; CHECK: %ret = phi i1 [ true, %entry ], [ false, %bees ], [ true, %entry ], [ true, %entry ] 271 %ret = phi i1 [ true, %entry ], [%tmp, %bees], [true, %entry] 272 call void @helper(i32 2) nounwind 273 ret i1 %ret 274 } 275 276 define void @test10(i32 %x) nounwind readnone ssp noredzone { 277 entry: 278 switch i32 %x, label %lor.rhs [ 279 i32 2, label %lor.end 280 i32 1, label %lor.end 281 i32 3, label %lor.end 282 ], !prof !7 283 284 lor.rhs: 285 call void @helper(i32 1) nounwind 286 ret void 287 288 lor.end: 289 call void @helper(i32 0) nounwind 290 ret void 291 292 ; CHECK-LABEL: @test10( 293 ; CHECK: %x.off = add i32 %x, -1 294 ; CHECK: %switch = icmp ult i32 %x.off, 3 295 ; CHECK: br i1 %switch, label %lor.end, label %lor.rhs, !prof !9 296 } 297 298 ; Remove dead cases from the switch. 299 define void @test11(i32 %x) nounwind { 300 %i = shl i32 %x, 1 301 switch i32 %i, label %a [ 302 i32 21, label %b 303 i32 24, label %c 304 ], !prof !8 305 ; CHECK-LABEL: @test11( 306 ; CHECK: %cond = icmp eq i32 %i, 24 307 ; CHECK: br i1 %cond, label %c, label %a, !prof !10 308 309 a: 310 call void @helper(i32 0) nounwind 311 ret void 312 b: 313 call void @helper(i32 1) nounwind 314 ret void 315 c: 316 call void @helper(i32 2) nounwind 317 ret void 318 } 319 320 ;; test12 - Don't crash if the whole switch is removed 321 define void @test12(i32 %M, i32 %N) nounwind uwtable { 322 entry: 323 switch i32 %N, label %sw.bb [ 324 i32 1, label %sw.bb 325 ], !prof !9 326 ; CHECK-LABEL: @test12( 327 ; CHECK-NEXT: entry: 328 ; CHECK-NEXT: call void @helper 329 ; CHECK-NEXT: ret void 330 331 sw.bb: 332 call void @helper(i32 0) 333 br label %sw.epilog 334 335 sw.epilog: 336 ret void 337 } 338 339 ;; If every case is dead, make sure they are all removed. This used to 340 ;; crash trying to merge the metadata. 341 define void @test13(i32 %x) nounwind { 342 entry: 343 %i = shl i32 %x, 1 344 switch i32 %i, label %a [ 345 i32 21, label %b 346 i32 25, label %c 347 ], !prof !8 348 ; CHECK-LABEL: @test13( 349 ; CHECK-NEXT: entry: 350 ; CHECK-NEXT: call void @helper 351 ; CHECK-NEXT: ret void 352 353 a: 354 call void @helper(i32 0) nounwind 355 ret void 356 b: 357 call void @helper(i32 1) nounwind 358 ret void 359 c: 360 call void @helper(i32 2) nounwind 361 ret void 362 } 363 364 ;; When folding branches to common destination, the updated branch weights 365 ;; can exceed uint32 by more than factor of 2. We should keep halving the 366 ;; weights until they can fit into uint32. 367 @max_regno = common global i32 0, align 4 368 define void @test14(i32* %old, i32 %final) { 369 ; CHECK-LABEL: @test14 370 ; CHECK: br i1 %or.cond, label %for.exit, label %for.inc, !prof !11 371 for.cond: 372 br label %for.cond2 373 for.cond2: 374 %i.1 = phi i32 [ %inc19, %for.inc ], [ 0, %for.cond ] 375 %bit.0 = phi i32 [ %shl, %for.inc ], [ 1, %for.cond ] 376 %tobool = icmp eq i32 %bit.0, 0 377 br i1 %tobool, label %for.exit, label %for.body3, !prof !10 378 for.body3: 379 %v3 = load i32, i32* @max_regno, align 4 380 %cmp4 = icmp eq i32 %i.1, %v3 381 br i1 %cmp4, label %for.exit, label %for.inc, !prof !11 382 for.inc: 383 %shl = shl i32 %bit.0, 1 384 %inc19 = add nsw i32 %i.1, 1 385 br label %for.cond2 386 for.exit: 387 ret void 388 } 389 390 ; Don't drop the metadata. 391 392 define i32 @HoistThenElseCodeToIf(i32 %n) { 393 ; CHECK-LABEL: @HoistThenElseCodeToIf( 394 ; CHECK-NEXT: entry: 395 ; CHECK-NEXT: [[TOBOOL:%.*]] = icmp eq i32 %n, 0 396 ; CHECK-NEXT: [[DOT:%.*]] = select i1 [[TOBOOL]], i32 1, i32 234, !prof !12 397 ; CHECK-NEXT: ret i32 [[DOT]] 398 ; 399 entry: 400 %tobool = icmp eq i32 %n, 0 401 br i1 %tobool, label %if, label %else, !prof !0 402 403 if: 404 br label %return 405 406 else: 407 br label %return 408 409 return: 410 %retval.0 = phi i32 [ 1, %if ], [ 234, %else ] 411 ret i32 %retval.0 412 } 413 414 ; The selects should have freshly calculated branch weights. 415 416 define i32 @SimplifyCondBranchToCondBranch(i1 %cmpa, i1 %cmpb) { 417 ; CHECK-LABEL: @SimplifyCondBranchToCondBranch( 418 ; CHECK-NEXT: block1: 419 ; CHECK-NEXT: [[BRMERGE:%.*]] = or i1 %cmpa, %cmpb 420 ; CHECK-NEXT: [[DOTMUX:%.*]] = select i1 %cmpa, i32 0, i32 2, !prof !13 421 ; CHECK-NEXT: [[OUTVAL:%.*]] = select i1 [[BRMERGE]], i32 [[DOTMUX]], i32 1, !prof !14 422 ; CHECK-NEXT: ret i32 [[OUTVAL]] 423 ; 424 block1: 425 br i1 %cmpa, label %block3, label %block2, !prof !13 426 427 block2: 428 br i1 %cmpb, label %block3, label %exit, !prof !14 429 430 block3: 431 %cowval = phi i32 [ 2, %block2 ], [ 0, %block1 ] 432 br label %exit 433 434 exit: 435 %outval = phi i32 [ %cowval, %block3 ], [ 1, %block2 ] 436 ret i32 %outval 437 } 438 439 ; Swap the operands of the compares to verify that the weights update correctly. 440 441 define i32 @SimplifyCondBranchToCondBranchSwap(i1 %cmpa, i1 %cmpb) { 442 ; CHECK-LABEL: @SimplifyCondBranchToCondBranchSwap( 443 ; CHECK-NEXT: block1: 444 ; CHECK-NEXT: [[CMPA_NOT:%.*]] = xor i1 %cmpa, true 445 ; CHECK-NEXT: [[CMPB_NOT:%.*]] = xor i1 %cmpb, true 446 ; CHECK-NEXT: [[BRMERGE:%.*]] = or i1 [[CMPA_NOT]], [[CMPB_NOT]] 447 ; CHECK-NEXT: [[DOTMUX:%.*]] = select i1 [[CMPA_NOT]], i32 0, i32 2, !prof !15 448 ; CHECK-NEXT: [[OUTVAL:%.*]] = select i1 [[BRMERGE]], i32 [[DOTMUX]], i32 1, !prof !16 449 ; CHECK-NEXT: ret i32 [[OUTVAL]] 450 ; 451 block1: 452 br i1 %cmpa, label %block2, label %block3, !prof !13 453 454 block2: 455 br i1 %cmpb, label %exit, label %block3, !prof !14 456 457 block3: 458 %cowval = phi i32 [ 2, %block2 ], [ 0, %block1 ] 459 br label %exit 460 461 exit: 462 %outval = phi i32 [ %cowval, %block3 ], [ 1, %block2 ] 463 ret i32 %outval 464 } 465 466 define i32 @SimplifyCondBranchToCondBranchSwapMissingWeight(i1 %cmpa, i1 %cmpb) { 467 ; CHECK-LABEL: @SimplifyCondBranchToCondBranchSwapMissingWeight( 468 ; CHECK-NEXT: block1: 469 ; CHECK-NEXT: [[CMPA_NOT:%.*]] = xor i1 %cmpa, true 470 ; CHECK-NEXT: [[CMPB_NOT:%.*]] = xor i1 %cmpb, true 471 ; CHECK-NEXT: [[BRMERGE:%.*]] = or i1 [[CMPA_NOT]], [[CMPB_NOT]] 472 ; CHECK-NEXT: [[DOTMUX:%.*]] = select i1 [[CMPA_NOT]], i32 0, i32 2, !prof !17 473 ; CHECK-NEXT: [[OUTVAL:%.*]] = select i1 [[BRMERGE]], i32 [[DOTMUX]], i32 1, !prof !18 474 ; CHECK-NEXT: ret i32 [[OUTVAL]] 475 ; 476 block1: 477 br i1 %cmpa, label %block2, label %block3, !prof !13 478 479 block2: 480 br i1 %cmpb, label %exit, label %block3 481 482 block3: 483 %cowval = phi i32 [ 2, %block2 ], [ 0, %block1 ] 484 br label %exit 485 486 exit: 487 %outval = phi i32 [ %cowval, %block3 ], [ 1, %block2 ] 488 ret i32 %outval 489 } 490 491 !0 = !{!"branch_weights", i32 3, i32 5} 492 !1 = !{!"branch_weights", i32 1, i32 1} 493 !2 = !{!"branch_weights", i32 1, i32 2} 494 !3 = !{!"branch_weights", i32 4, i32 3, i32 2, i32 1} 495 !4 = !{!"branch_weights", i32 4, i32 3, i32 2, i32 1} 496 !5 = !{!"branch_weights", i32 7, i32 6, i32 5} 497 !6 = !{!"branch_weights", i32 1, i32 3} 498 !7 = !{!"branch_weights", i32 33, i32 9, i32 8, i32 7} 499 !8 = !{!"branch_weights", i32 33, i32 9, i32 8} 500 !9 = !{!"branch_weights", i32 7, i32 6} 501 !10 = !{!"branch_weights", i32 672646, i32 21604207} 502 !11 = !{!"branch_weights", i32 6960, i32 21597248} 503 !12 = !{!"these_are_not_the_branch_weights_you_are_looking_for", i32 3, i32 5} 504 !13 = !{!"branch_weights", i32 2, i32 3} 505 !14 = !{!"branch_weights", i32 4, i32 7} 506 507 ; CHECK: !0 = !{!"branch_weights", i32 5, i32 11} 508 ; CHECK: !1 = !{!"branch_weights", i32 1, i32 3} 509 ; CHECK: !2 = !{!"branch_weights", i32 1, i32 5} 510 ; CHECK: !3 = !{!"branch_weights", i32 7, i32 1, i32 2} 511 ; CHECK: !4 = !{!"branch_weights", i32 49, i32 12, i32 24, i32 35} 512 ; CHECK: !5 = !{!"branch_weights", i32 11, i32 5} 513 ; CHECK: !6 = !{!"branch_weights", i32 17, i32 15} 514 ; CHECK: !7 = !{!"branch_weights", i32 9, i32 7} 515 ; CHECK: !8 = !{!"branch_weights", i32 17, i32 9, i32 8, i32 7, i32 17} 516 ; CHECK: !9 = !{!"branch_weights", i32 24, i32 33} 517 ; CHECK: !10 = !{!"branch_weights", i32 8, i32 33} 518 ;; The false weight prints out as a negative integer here, but inside llvm, we 519 ;; treat the weight as an unsigned integer. 520 ; CHECK: !11 = !{!"branch_weights", i32 112017436, i32 -735157296} 521 ; CHECK: !12 = !{!"branch_weights", i32 3, i32 5} 522 ; CHECK: !13 = !{!"branch_weights", i32 22, i32 12} 523 ; CHECK: !14 = !{!"branch_weights", i32 34, i32 21} 524 ; CHECK: !15 = !{!"branch_weights", i32 33, i32 14} 525 ; CHECK: !16 = !{!"branch_weights", i32 47, i32 8} 526 ; CHECK: !17 = !{!"branch_weights", i32 6, i32 2} 527 ; CHECK: !18 = !{!"branch_weights", i32 8, i32 2} 528
