test/Transforms/GuardWidening/widen-frequent-branches.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -guard-widening-widen-frequent-branches=true -guard-widening-frequent-branch-threshold=1000 -S -guard-widening < %s        | FileCheck %s
   3 ; RUN: opt -guard-widening-widen-frequent-branches=true -guard-widening-frequent-branch-threshold=1000 -S -passes='require<branch-prob>,guard-widening' < %s | FileCheck %s
   4
   5 declare void @llvm.experimental.guard(i1,...)
   6 declare void @foo()
   7 declare void @bar()
   8
   9 ; Check that we don't widen without branch probability.
  10 define void @test_01(i1 %cond_0, i1 %cond_1) {
  11 ; CHECK-LABEL: @test_01(
  12 ; CHECK-NEXT:  entry:
  13 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[COND_0:%.*]]) [ "deopt"() ]
  14 ; CHECK-NEXT:    br i1 [[COND_1:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
  15 ; CHECK:       if.true:
  16 ; CHECK-NEXT:    call void @foo()
  17 ; CHECK-NEXT:    br label [[MERGE:%.*]]
  18 ; CHECK:       if.false:
  19 ; CHECK-NEXT:    call void @bar()
  20 ; CHECK-NEXT:    br label [[MERGE]]
  21 ; CHECK:       merge:
  22 ; CHECK-NEXT:    ret void
  23 ;
  24 entry:
  25   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
  26   br i1 %cond_1, label %if.true, label %if.false
  27
  28 if.true:
  29   call void @foo()
  30   br label %merge
  31
  32 if.false:
  33   call void @bar()
  34   br label %merge
  35
  36 merge:
  37   ret void
  38 }
  39
  40 ; Check that we don't widen with branch probability below threshold.
  41 define void @test_02(i1 %cond_0, i1 %cond_1) {
  42 ; CHECK-LABEL: @test_02(
  43 ; CHECK-NEXT:  entry:
  44 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[COND_0:%.*]]) [ "deopt"() ]
  45 ; CHECK-NEXT:    br i1 [[COND_1:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !0
  46 ; CHECK:       if.true:
  47 ; CHECK-NEXT:    call void @foo()
  48 ; CHECK-NEXT:    br label [[MERGE:%.*]]
  49 ; CHECK:       if.false:
  50 ; CHECK-NEXT:    call void @bar()
  51 ; CHECK-NEXT:    br label [[MERGE]]
  52 ; CHECK:       merge:
  53 ; CHECK-NEXT:    ret void
  54 ;
  55 entry:
  56   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
  57   br i1 %cond_1, label %if.true, label %if.false, !prof !0
  58
  59 if.true:
  60   call void @foo()
  61   br label %merge
  62
  63 if.false:
  64   call void @bar()
  65   br label %merge
  66
  67 merge:
  68   ret void
  69 }
  70
  71 ; Check that we widen conditions of explicit branches into dominating guards
  72 ; when the probability is high enough.
  73 define void @test_03(i1 %cond_0, i1 %cond_1) {
  74 ; CHECK-LABEL: @test_03(
  75 ; CHECK-NEXT:  entry:
  76 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_1:%.*]]
  77 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
  78 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !1
  79 ; CHECK:       if.true:
  80 ; CHECK-NEXT:    call void @foo()
  81 ; CHECK-NEXT:    br label [[MERGE:%.*]]
  82 ; CHECK:       if.false:
  83 ; CHECK-NEXT:    call void @bar()
  84 ; CHECK-NEXT:    br label [[MERGE]]
  85 ; CHECK:       merge:
  86 ; CHECK-NEXT:    ret void
  87 ;
  88 entry:
  89   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
  90   br i1 %cond_1, label %if.true, label %if.false, !prof !1
  91
  92 if.true:
  93   call void @foo()
  94   br label %merge
  95
  96 if.false:
  97   call void @bar()
  98   br label %merge
  99
 100 merge:
 101   ret void
 102 }
 103
 104 ; Similar to test_03, but the likely taken branch is the false branch.
 105 define void @test_03_not_taken(i1 %cond_0, i1 %cond_1) {
 106 ; CHECK-LABEL: @test_03_not_taken(
 107 ; CHECK-NEXT:  entry:
 108 ; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_1:%.*]], true
 109 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
 110 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 111 ; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
 112 ; CHECK:       if.true:
 113 ; CHECK-NEXT:    call void @foo()
 114 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 115 ; CHECK:       if.false:
 116 ; CHECK-NEXT:    call void @bar()
 117 ; CHECK-NEXT:    br label [[MERGE]]
 118 ; CHECK:       merge:
 119 ; CHECK-NEXT:    ret void
 120 ;
 121 entry:
 122   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 123   br i1 %cond_1, label %if.true, label %if.false, !prof !3
 124
 125 if.true:
 126   call void @foo()
 127   br label %merge
 128
 129 if.false:
 130   call void @bar()
 131   br label %merge
 132
 133 merge:
 134   ret void
 135 }
 136
 137 ; Widen loop-invariant condition into the guard in preheader.
 138 define void @test_04(i1 %cond_0, i1 %cond_1, i32 %n) {
 139 ; CHECK-LABEL: @test_04(
 140 ; CHECK-NEXT:  entry:
 141 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_1:%.*]]
 142 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 143 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 144 ; CHECK:       loop:
 145 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[MERGE:%.*]] ]
 146 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !1
 147 ; CHECK:       if.true:
 148 ; CHECK-NEXT:    call void @foo()
 149 ; CHECK-NEXT:    br label [[MERGE]]
 150 ; CHECK:       if.false:
 151 ; CHECK-NEXT:    call void @bar()
 152 ; CHECK-NEXT:    br label [[MERGE]]
 153 ; CHECK:       merge:
 154 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 155 ; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[N:%.*]]
 156 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
 157 ; CHECK:       exit:
 158 ; CHECK-NEXT:    ret void
 159 ;
 160 entry:
 161   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 162   br label %loop
 163
 164 loop:
 165   %iv = phi i32 [ 0, %entry ], [ %iv.next, %merge ]
 166   br i1 %cond_1, label %if.true, label %if.false, !prof !1
 167
 168 if.true:
 169   call void @foo()
 170   br label %merge
 171
 172 if.false:
 173   call void @bar()
 174   br label %merge
 175
 176 merge:
 177   %iv.next = add i32 %iv, 1
 178   %cond = icmp slt i32 %iv.next, %n
 179   br i1 %cond, label %loop, label %exit
 180
 181 exit:
 182   ret void
 183 }
 184
 185 ; Similar to test_04, but the likely taken branch is the false branch.
 186 define void @test_04_not_taken(i1 %cond_0, i1 %cond_1, i32 %n) {
 187 ; CHECK-LABEL: @test_04_not_taken(
 188 ; CHECK-NEXT:  entry:
 189 ; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_1:%.*]], true
 190 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
 191 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 192 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 193 ; CHECK:       loop:
 194 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[MERGE:%.*]] ]
 195 ; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
 196 ; CHECK:       if.true:
 197 ; CHECK-NEXT:    call void @foo()
 198 ; CHECK-NEXT:    br label [[MERGE]]
 199 ; CHECK:       if.false:
 200 ; CHECK-NEXT:    call void @bar()
 201 ; CHECK-NEXT:    br label [[MERGE]]
 202 ; CHECK:       merge:
 203 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 204 ; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[N:%.*]]
 205 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
 206 ; CHECK:       exit:
 207 ; CHECK-NEXT:    ret void
 208 ;
 209 entry:
 210   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 211   br label %loop
 212
 213 loop:
 214   %iv = phi i32 [ 0, %entry ], [ %iv.next, %merge ]
 215   br i1 %cond_1, label %if.true, label %if.false, !prof !3
 216
 217 if.true:
 218   call void @foo()
 219   br label %merge
 220
 221 if.false:
 222   call void @bar()
 223   br label %merge
 224
 225 merge:
 226   %iv.next = add i32 %iv, 1
 227   %cond = icmp slt i32 %iv.next, %n
 228   br i1 %cond, label %loop, label %exit
 229
 230 exit:
 231   ret void
 232 }
 233
 234 ; Widen loop-invariant condition into the guard in the same loop.
 235 define void @test_05(i1 %cond_0, i1 %cond_1, i32 %n) {
 236 ; CHECK-LABEL: @test_05(
 237 ; CHECK-NEXT:  entry:
 238 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 239 ; CHECK:       loop:
 240 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[MERGE:%.*]] ]
 241 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_1:%.*]]
 242 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 243 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !1
 244 ; CHECK:       if.true:
 245 ; CHECK-NEXT:    call void @foo()
 246 ; CHECK-NEXT:    br label [[MERGE]]
 247 ; CHECK:       if.false:
 248 ; CHECK-NEXT:    call void @bar()
 249 ; CHECK-NEXT:    br label [[MERGE]]
 250 ; CHECK:       merge:
 251 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 252 ; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[N:%.*]]
 253 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
 254 ; CHECK:       exit:
 255 ; CHECK-NEXT:    ret void
 256 ;
 257 entry:
 258   br label %loop
 259
 260 loop:
 261   %iv = phi i32 [ 0, %entry ], [ %iv.next, %merge ]
 262   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 263   br i1 %cond_1, label %if.true, label %if.false, !prof !1
 264
 265 if.true:
 266   call void @foo()
 267   br label %merge
 268
 269 if.false:
 270   call void @bar()
 271   br label %merge
 272
 273 merge:
 274   %iv.next = add i32 %iv, 1
 275   %cond = icmp slt i32 %iv.next, %n
 276   br i1 %cond, label %loop, label %exit
 277
 278 exit:
 279   ret void
 280 }
 281
 282 ; Similar to test_05, but the likely taken branch is the false branch.
 283 define void @test_05_not_taken(i1 %cond_0, i1 %cond_1, i32 %n) {
 284 ; CHECK-LABEL: @test_05_not_taken(
 285 ; CHECK-NEXT:  entry:
 286 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 287 ; CHECK:       loop:
 288 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[MERGE:%.*]] ]
 289 ; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_1:%.*]], true
 290 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
 291 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 292 ; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
 293 ; CHECK:       if.true:
 294 ; CHECK-NEXT:    call void @foo()
 295 ; CHECK-NEXT:    br label [[MERGE]]
 296 ; CHECK:       if.false:
 297 ; CHECK-NEXT:    call void @bar()
 298 ; CHECK-NEXT:    br label [[MERGE]]
 299 ; CHECK:       merge:
 300 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 301 ; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[N:%.*]]
 302 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
 303 ; CHECK:       exit:
 304 ; CHECK-NEXT:    ret void
 305 ;
 306 entry:
 307   br label %loop
 308
 309 loop:
 310   %iv = phi i32 [ 0, %entry ], [ %iv.next, %merge ]
 311   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 312   br i1 %cond_1, label %if.true, label %if.false, !prof !3
 313
 314 if.true:
 315   call void @foo()
 316   br label %merge
 317
 318 if.false:
 319   call void @bar()
 320   br label %merge
 321
 322 merge:
 323   %iv.next = add i32 %iv, 1
 324   %cond = icmp slt i32 %iv.next, %n
 325   br i1 %cond, label %loop, label %exit
 326
 327 exit:
 328   ret void
 329 }
 330
 331 ; Some of checks are frequently taken and some are not, make sure that we only
 332 ; widen frequent ones.
 333 define void @test_06(i1 %cond_0, i1 %cond_1, i1 %cond_2, i1 %cond_3, i1 %cond_4, i32 %n) {
 334 ; CHECK-LABEL: @test_06(
 335 ; CHECK-NEXT:  entry:
 336 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_2:%.*]]
 337 ; CHECK-NEXT:    [[WIDE_CHK1:%.*]] = and i1 [[WIDE_CHK]], [[COND_4:%.*]]
 338 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK1]]) [ "deopt"() ]
 339 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 340 ; CHECK:       loop:
 341 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 342 ; CHECK-NEXT:    br i1 [[COND_1:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_FALSE_1:%.*]], !prof !3
 343 ; CHECK:       if.true_1:
 344 ; CHECK-NEXT:    call void @foo()
 345 ; CHECK-NEXT:    br label [[MERGE_1:%.*]]
 346 ; CHECK:       if.false_1:
 347 ; CHECK-NEXT:    call void @bar()
 348 ; CHECK-NEXT:    br label [[MERGE_1]]
 349 ; CHECK:       merge_1:
 350 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE_2:%.*]], label [[IF_FALSE_2:%.*]], !prof !1
 351 ; CHECK:       if.true_2:
 352 ; CHECK-NEXT:    call void @foo()
 353 ; CHECK-NEXT:    br label [[MERGE_2:%.*]]
 354 ; CHECK:       if.false_2:
 355 ; CHECK-NEXT:    call void @bar()
 356 ; CHECK-NEXT:    br label [[MERGE_2]]
 357 ; CHECK:       merge_2:
 358 ; CHECK-NEXT:    br i1 [[COND_3:%.*]], label [[IF_TRUE_3:%.*]], label [[IF_FALSE_3:%.*]], !prof !3
 359 ; CHECK:       if.true_3:
 360 ; CHECK-NEXT:    call void @foo()
 361 ; CHECK-NEXT:    br label [[MERGE_3:%.*]]
 362 ; CHECK:       if.false_3:
 363 ; CHECK-NEXT:    call void @bar()
 364 ; CHECK-NEXT:    br label [[MERGE_3]]
 365 ; CHECK:       merge_3:
 366 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE_4:%.*]], label [[IF_FALSE_4:%.*]], !prof !1
 367 ; CHECK:       if.true_4:
 368 ; CHECK-NEXT:    call void @foo()
 369 ; CHECK-NEXT:    br label [[BACKEDGE]]
 370 ; CHECK:       if.false_4:
 371 ; CHECK-NEXT:    call void @bar()
 372 ; CHECK-NEXT:    br label [[BACKEDGE]]
 373 ; CHECK:       backedge:
 374 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 375 ; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[N:%.*]]
 376 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
 377 ; CHECK:       exit:
 378 ; CHECK-NEXT:    ret void
 379 ;
 380 entry:
 381   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 382   br label %loop
 383
 384 loop:
 385   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 386   br i1 %cond_1, label %if.true_1, label %if.false_1, !prof !2
 387
 388 if.true_1:
 389   call void @foo()
 390   br label %merge_1
 391
 392 if.false_1:
 393   call void @bar()
 394   br label %merge_1
 395
 396 merge_1:
 397   br i1 %cond_2, label %if.true_2, label %if.false_2, !prof !1
 398
 399 if.true_2:
 400   call void @foo()
 401   br label %merge_2
 402
 403 if.false_2:
 404   call void @bar()
 405   br label %merge_2
 406
 407 merge_2:
 408   br i1 %cond_3, label %if.true_3, label %if.false_3, !prof !2
 409
 410 if.true_3:
 411   call void @foo()
 412   br label %merge_3
 413
 414 if.false_3:
 415   call void @bar()
 416   br label %merge_3
 417
 418 merge_3:
 419   br i1 %cond_4, label %if.true_4, label %if.false_4, !prof !1
 420
 421 if.true_4:
 422   call void @foo()
 423   br label %backedge
 424
 425 if.false_4:
 426   call void @bar()
 427   br label %backedge
 428
 429 backedge:
 430   %iv.next = add i32 %iv, 1
 431   %cond = icmp slt i32 %iv.next, %n
 432   br i1 %cond, label %loop, label %exit
 433
 434 exit:
 435   ret void
 436 }
 437
 438 ; Similar to test_06, but the likely taken branch is the false branch.
 439 define void @test_06_not_taken(i1 %cond_0, i1 %cond_1, i1 %cond_2, i1 %cond_3, i1 %cond_4, i32 %n) {
 440 ; CHECK-LABEL: @test_06_not_taken(
 441 ; CHECK-NEXT:  entry:
 442 ; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_2:%.*]], true
 443 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
 444 ; CHECK-NEXT:    [[INVERTED1:%.*]] = xor i1 [[COND_4:%.*]], true
 445 ; CHECK-NEXT:    [[WIDE_CHK2:%.*]] = and i1 [[WIDE_CHK]], [[INVERTED1]]
 446 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK2]]) [ "deopt"() ]
 447 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 448 ; CHECK:       loop:
 449 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 450 ; CHECK-NEXT:    br i1 [[COND_1:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_FALSE_1:%.*]], !prof !3
 451 ; CHECK:       if.true_1:
 452 ; CHECK-NEXT:    call void @foo()
 453 ; CHECK-NEXT:    br label [[MERGE_1:%.*]]
 454 ; CHECK:       if.false_1:
 455 ; CHECK-NEXT:    call void @bar()
 456 ; CHECK-NEXT:    br label [[MERGE_1]]
 457 ; CHECK:       merge_1:
 458 ; CHECK-NEXT:    br i1 false, label [[IF_TRUE_2:%.*]], label [[IF_FALSE_2:%.*]], !prof !2
 459 ; CHECK:       if.true_2:
 460 ; CHECK-NEXT:    call void @foo()
 461 ; CHECK-NEXT:    br label [[MERGE_2:%.*]]
 462 ; CHECK:       if.false_2:
 463 ; CHECK-NEXT:    call void @bar()
 464 ; CHECK-NEXT:    br label [[MERGE_2]]
 465 ; CHECK:       merge_2:
 466 ; CHECK-NEXT:    br i1 [[COND_3:%.*]], label [[IF_TRUE_3:%.*]], label [[IF_FALSE_3:%.*]], !prof !3
 467 ; CHECK:       if.true_3:
 468 ; CHECK-NEXT:    call void @foo()
 469 ; CHECK-NEXT:    br label [[MERGE_3:%.*]]
 470 ; CHECK:       if.false_3:
 471 ; CHECK-NEXT:    call void @bar()
 472 ; CHECK-NEXT:    br label [[MERGE_3]]
 473 ; CHECK:       merge_3:
 474 ; CHECK-NEXT:    br i1 false, label [[IF_TRUE_4:%.*]], label [[IF_FALSE_4:%.*]], !prof !2
 475 ; CHECK:       if.true_4:
 476 ; CHECK-NEXT:    call void @foo()
 477 ; CHECK-NEXT:    br label [[BACKEDGE]]
 478 ; CHECK:       if.false_4:
 479 ; CHECK-NEXT:    call void @bar()
 480 ; CHECK-NEXT:    br label [[BACKEDGE]]
 481 ; CHECK:       backedge:
 482 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 483 ; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[N:%.*]]
 484 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
 485 ; CHECK:       exit:
 486 ; CHECK-NEXT:    ret void
 487 ;
 488 entry:
 489   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 490   br label %loop
 491
 492 loop:
 493   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 494   br i1 %cond_1, label %if.true_1, label %if.false_1, !prof !2
 495
 496 if.true_1:
 497   call void @foo()
 498   br label %merge_1
 499
 500 if.false_1:
 501   call void @bar()
 502   br label %merge_1
 503
 504 merge_1:
 505   br i1 %cond_2, label %if.true_2, label %if.false_2, !prof !3
 506
 507 if.true_2:
 508   call void @foo()
 509   br label %merge_2
 510
 511 if.false_2:
 512   call void @bar()
 513   br label %merge_2
 514
 515 merge_2:
 516   br i1 %cond_3, label %if.true_3, label %if.false_3, !prof !2
 517
 518 if.true_3:
 519   call void @foo()
 520   br label %merge_3
 521
 522 if.false_3:
 523   call void @bar()
 524   br label %merge_3
 525
 526 merge_3:
 527   br i1 %cond_4, label %if.true_4, label %if.false_4, !prof !3
 528
 529 if.true_4:
 530   call void @foo()
 531   br label %backedge
 532
 533 if.false_4:
 534   call void @bar()
 535   br label %backedge
 536
 537 backedge:
 538   %iv.next = add i32 %iv, 1
 539   %cond = icmp slt i32 %iv.next, %n
 540   br i1 %cond, label %loop, label %exit
 541
 542 exit:
 543   ret void
 544 }
 545
 546 ; Check triangle CFG pattern.
 547 define void @test_07(i1 %cond_0, i1 %cond_1) {
 548 ; CHECK-LABEL: @test_07(
 549 ; CHECK-NEXT:  entry:
 550 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_1:%.*]]
 551 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 552 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[MERGE:%.*]], !prof !1
 553 ; CHECK:       if.true:
 554 ; CHECK-NEXT:    call void @foo()
 555 ; CHECK-NEXT:    br label [[MERGE]]
 556 ; CHECK:       merge:
 557 ; CHECK-NEXT:    ret void
 558 ;
 559 entry:
 560   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 561   br i1 %cond_1, label %if.true, label %merge, !prof !1
 562
 563 if.true:
 564   call void @foo()
 565   br label %merge
 566
 567 merge:
 568   ret void
 569 }
 570
 571 ; Similar to test_07, but the likely taken branch is the false branch.
 572 define void @test_07_not_taken(i1 %cond_0, i1 %cond_1) {
 573 ; CHECK-LABEL: @test_07_not_taken(
 574 ; CHECK-NEXT:  entry:
 575 ; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_1:%.*]], true
 576 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
 577 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 578 ; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[MERGE:%.*]], !prof !2
 579 ; CHECK:       if.true:
 580 ; CHECK-NEXT:    call void @foo()
 581 ; CHECK-NEXT:    br label [[MERGE]]
 582 ; CHECK:       merge:
 583 ; CHECK-NEXT:    ret void
 584 ;
 585 entry:
 586   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 587   br i1 %cond_1, label %if.true, label %merge, !prof !3
 588
 589 if.true:
 590   call void @foo()
 591   br label %merge
 592
 593 merge:
 594   ret void
 595 }
 596
 597 define void @test_08(i1 %cond_0, i1 %cond_1) {
 598 ; CHECK-LABEL: @test_08(
 599 ; CHECK-NEXT:  entry:
 600 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_1:%.*]]
 601 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 602 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !1
 603 ; CHECK:       if.true:
 604 ; CHECK-NEXT:    call void @foo()
 605 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 606 ; CHECK:       if.false:
 607 ; CHECK-NEXT:    ret void
 608 ; CHECK:       merge:
 609 ; CHECK-NEXT:    ret void
 610 ;
 611 entry:
 612   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 613   br i1 %cond_1, label %if.true, label %if.false, !prof !1
 614
 615 if.true:
 616   call void @foo()
 617   br label %merge
 618
 619 if.false:
 620   ret void
 621
 622 merge:
 623   ret void
 624 }
 625
 626 define void @test_08_not_taken(i1 %cond_0, i1 %cond_1) {
 627 ; CHECK-LABEL: @test_08_not_taken(
 628 ; CHECK-NEXT:  entry:
 629 ; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_1:%.*]], true
 630 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
 631 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 632 ; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
 633 ; CHECK:       if.true:
 634 ; CHECK-NEXT:    call void @foo()
 635 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 636 ; CHECK:       if.false:
 637 ; CHECK-NEXT:    ret void
 638 ; CHECK:       merge:
 639 ; CHECK-NEXT:    ret void
 640 ;
 641 entry:
 642   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 643   br i1 %cond_1, label %if.true, label %if.false, !prof !3
 644
 645 if.true:
 646   call void @foo()
 647   br label %merge
 648
 649 if.false:
 650   ret void
 651
 652 merge:
 653   ret void
 654 }
 655
 656 ; Check that L >u C0 && L >u C1  ->  L >u max(C0, C1).
 657 define void @test_09(i32 %L) {
 658 ; CHECK-LABEL: @test_09(
 659 ; CHECK-NEXT:  entry:
 660 ; CHECK-NEXT:    [[COND_0:%.*]] = icmp ugt i32 [[L:%.*]], 123
 661 ; CHECK-NEXT:    [[COND_1:%.*]] = icmp ugt i32 [[L]], 456
 662 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = icmp uge i32 [[L]], 457
 663 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 664 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !1
 665 ; CHECK:       if.true:
 666 ; CHECK-NEXT:    call void @foo()
 667 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 668 ; CHECK:       if.false:
 669 ; CHECK-NEXT:    ret void
 670 ; CHECK:       merge:
 671 ; CHECK-NEXT:    ret void
 672 ;
 673 entry:
 674   %cond_0 = icmp ugt i32 %L, 123
 675   %cond_1 = icmp ugt i32 %L, 456
 676   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 677   br i1 %cond_1, label %if.true, label %if.false, !prof !1
 678
 679 if.true:
 680   call void @foo()
 681   br label %merge
 682
 683 if.false:
 684   ret void
 685
 686 merge:
 687   ret void
 688 }
 689
 690 ; Check that L >u C0 && !(L <=u C1)  ->  L >u max(C0, C1).
 691 define void @test_09_not_taken(i32 %L) {
 692 ; CHECK-LABEL: @test_09_not_taken(
 693 ; CHECK-NEXT:  entry:
 694 ; CHECK-NEXT:    [[COND_0:%.*]] = icmp ugt i32 [[L:%.*]], 123
 695 ; CHECK-NEXT:    [[COND_1:%.*]] = icmp ule i32 [[L]], 456
 696 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = icmp uge i32 [[L]], 457
 697 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 698 ; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
 699 ; CHECK:       if.true:
 700 ; CHECK-NEXT:    call void @foo()
 701 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 702 ; CHECK:       if.false:
 703 ; CHECK-NEXT:    ret void
 704 ; CHECK:       merge:
 705 ; CHECK-NEXT:    ret void
 706 ;
 707 entry:
 708   %cond_0 = icmp ugt i32 %L, 123
 709   %cond_1 = icmp ule i32 %L, 456
 710   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 711   br i1 %cond_1, label %if.true, label %if.false, !prof !3
 712
 713 if.true:
 714   call void @foo()
 715   br label %merge
 716
 717 if.false:
 718   ret void
 719
 720 merge:
 721   ret void
 722 }
 723
 724 ; Check that a profitable transform is preferred over non-profitable.
 725 define void @test_10(i32 %L, i1 %irrelevant_cond, i1 %infinite_loop_cond) {
 726 ; CHECK-LABEL: @test_10(
 727 ; CHECK-NEXT:  entry:
 728 ; CHECK-NEXT:    [[COND_0:%.*]] = icmp ugt i32 [[L:%.*]], 123
 729 ; CHECK-NEXT:    [[COND_1:%.*]] = icmp ugt i32 [[L]], 456
 730 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 731 ; CHECK:       loop:
 732 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[IRRELEVANT_COND:%.*]]) [ "deopt"() ]
 733 ; CHECK-NEXT:    br i1 [[INFINITE_LOOP_COND:%.*]], label [[LOOP]], label [[AFTER_LOOP:%.*]]
 734 ; CHECK:       after_loop:
 735 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = icmp uge i32 [[L]], 457
 736 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 737 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !1
 738 ; CHECK:       if.true:
 739 ; CHECK-NEXT:    call void @foo()
 740 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 741 ; CHECK:       if.false:
 742 ; CHECK-NEXT:    br label [[MERGE]]
 743 ; CHECK:       merge:
 744 ; CHECK-NEXT:    ret void
 745 ;
 746 entry:
 747   %cond_0 = icmp ugt i32 %L, 123
 748   %cond_1 = icmp ugt i32 %L, 456
 749   br label %loop
 750
 751 loop:
 752   call void(i1, ...) @llvm.experimental.guard(i1 %irrelevant_cond) [ "deopt"() ]
 753   br i1 %infinite_loop_cond, label %loop, label %after_loop
 754
 755 after_loop:
 756   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 757   br i1 %cond_1, label %if.true, label %if.false, !prof !1
 758
 759 if.true:
 760   call void @foo()
 761   br label %merge
 762
 763 if.false:
 764   br label %merge
 765
 766 merge:
 767   ret void
 768 }
 769
 770 ; Check that a profitable transform is preferred over non-profitable.
 771
 772 define void @test_10_not_taken(i32 %L, i1 %irrelevant_cond, i1 %infinite_loop_cond) {
 773 ; CHECK-LABEL: @test_10_not_taken(
 774 ; CHECK-NEXT:  entry:
 775 ; CHECK-NEXT:    [[COND_0:%.*]] = icmp ugt i32 [[L:%.*]], 123
 776 ; CHECK-NEXT:    [[COND_1:%.*]] = icmp ule i32 [[L]], 456
 777 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 778 ; CHECK:       loop:
 779 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[IRRELEVANT_COND:%.*]]) [ "deopt"() ]
 780 ; CHECK-NEXT:    br i1 [[INFINITE_LOOP_COND:%.*]], label [[LOOP]], label [[AFTER_LOOP:%.*]]
 781 ; CHECK:       after_loop:
 782 ; CHECK-NEXT:    [[WIDE_CHK:%.*]] = icmp uge i32 [[L]], 457
 783 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
 784 ; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
 785 ; CHECK:       if.true:
 786 ; CHECK-NEXT:    call void @foo()
 787 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 788 ; CHECK:       if.false:
 789 ; CHECK-NEXT:    br label [[MERGE]]
 790 ; CHECK:       merge:
 791 ; CHECK-NEXT:    ret void
 792 ;
 793 entry:
 794   %cond_0 = icmp ugt i32 %L, 123
 795   %cond_1 = icmp ule i32 %L, 456
 796   br label %loop
 797
 798 loop:
 799   call void(i1, ...) @llvm.experimental.guard(i1 %irrelevant_cond) [ "deopt"() ]
 800   br i1 %infinite_loop_cond, label %loop, label %after_loop
 801
 802 after_loop:
 803   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
 804   br i1 %cond_1, label %if.true, label %if.false, !prof !3
 805
 806 if.true:
 807   call void @foo()
 808   br label %merge
 809
 810 if.false:
 811   br label %merge
 812
 813 merge:
 814   ret void
 815 }
 816
 817 !0 = !{!"branch_weights", i32 998, i32 1}
 818 !1 = !{!"branch_weights", i32 999, i32 1}
 819 !2 = !{!"branch_weights", i32 500, i32 500}
 820 !3 = !{!"branch_weights", i32 1, i32 999}