test/CodeGen/X86/block-placement.ll

   1 ; RUN: llc -march=x86 -enable-block-placement < %s | FileCheck %s
   2
   3 declare void @error(i32 %i, i32 %a, i32 %b)
   4
   5 define i32 @test_ifchains(i32 %i, i32* %a, i32 %b) {
   6 ; Test a chain of ifs, where the block guarded by the if is error handling code
   7 ; that is not expected to run.
   8 ; CHECK: test_ifchains:
   9 ; CHECK: %entry
  10 ; CHECK: %else1
  11 ; CHECK: %else2
  12 ; CHECK: %else3
  13 ; CHECK: %else4
  14 ; CHECK: %exit
  15 ; CHECK: %then1
  16 ; CHECK: %then2
  17 ; CHECK: %then3
  18 ; CHECK: %then4
  19 ; CHECK: %then5
  20
  21 entry:
  22   %gep1 = getelementptr i32* %a, i32 1
  23   %val1 = load i32* %gep1
  24   %cond1 = icmp ugt i32 %val1, 1
  25   br i1 %cond1, label %then1, label %else1, !prof !0
  26
  27 then1:
  28   call void @error(i32 %i, i32 1, i32 %b)
  29   br label %else1
  30
  31 else1:
  32   %gep2 = getelementptr i32* %a, i32 2
  33   %val2 = load i32* %gep2
  34   %cond2 = icmp ugt i32 %val2, 2
  35   br i1 %cond2, label %then2, label %else2, !prof !0
  36
  37 then2:
  38   call void @error(i32 %i, i32 1, i32 %b)
  39   br label %else2
  40
  41 else2:
  42   %gep3 = getelementptr i32* %a, i32 3
  43   %val3 = load i32* %gep3
  44   %cond3 = icmp ugt i32 %val3, 3
  45   br i1 %cond3, label %then3, label %else3, !prof !0
  46
  47 then3:
  48   call void @error(i32 %i, i32 1, i32 %b)
  49   br label %else3
  50
  51 else3:
  52   %gep4 = getelementptr i32* %a, i32 4
  53   %val4 = load i32* %gep4
  54   %cond4 = icmp ugt i32 %val4, 4
  55   br i1 %cond4, label %then4, label %else4, !prof !0
  56
  57 then4:
  58   call void @error(i32 %i, i32 1, i32 %b)
  59   br label %else4
  60
  61 else4:
  62   %gep5 = getelementptr i32* %a, i32 3
  63   %val5 = load i32* %gep5
  64   %cond5 = icmp ugt i32 %val5, 3
  65   br i1 %cond5, label %then5, label %exit, !prof !0
  66
  67 then5:
  68   call void @error(i32 %i, i32 1, i32 %b)
  69   br label %exit
  70
  71 exit:
  72   ret i32 %b
  73 }
  74
  75 define i32 @test_loop_cold_blocks(i32 %i, i32* %a) {
  76 ; Check that we sink cold loop blocks after the hot loop body.
  77 ; CHECK: test_loop_cold_blocks:
  78 ; CHECK: %entry
  79 ; CHECK: %body1
  80 ; CHECK: %body2
  81 ; CHECK: %body3
  82 ; CHECK: %unlikely1
  83 ; CHECK: %unlikely2
  84 ; CHECK: %exit
  85
  86 entry:
  87   br label %body1
  88
  89 body1:
  90   %iv = phi i32 [ 0, %entry ], [ %next, %body3 ]
  91   %base = phi i32 [ 0, %entry ], [ %sum, %body3 ]
  92   %unlikelycond1 = icmp slt i32 %base, 42
  93   br i1 %unlikelycond1, label %unlikely1, label %body2, !prof !0
  94
  95 unlikely1:
  96   call void @error(i32 %i, i32 1, i32 %base)
  97   br label %body2
  98
  99 body2:
 100   %unlikelycond2 = icmp sgt i32 %base, 21
 101   br i1 %unlikelycond2, label %unlikely2, label %body3, !prof !0
 102
 103 unlikely2:
 104   call void @error(i32 %i, i32 2, i32 %base)
 105   br label %body3
 106
 107 body3:
 108   %arrayidx = getelementptr inbounds i32* %a, i32 %iv
 109   %0 = load i32* %arrayidx
 110   %sum = add nsw i32 %0, %base
 111   %next = add i32 %iv, 1
 112   %exitcond = icmp eq i32 %next, %i
 113   br i1 %exitcond, label %exit, label %body1
 114
 115 exit:
 116   ret i32 %sum
 117 }
 118
 119 !0 = metadata !{metadata !"branch_weights", i32 4, i32 64}
 120
 121 define i32 @test_loop_early_exits(i32 %i, i32* %a) {
 122 ; Check that we sink early exit blocks out of loop bodies.
 123 ; CHECK: test_loop_early_exits:
 124 ; CHECK: %entry
 125 ; CHECK: %body1
 126 ; CHECK: %body2
 127 ; CHECK: %body3
 128 ; CHECK: %body4
 129 ; CHECK: %exit
 130 ; CHECK: %bail1
 131 ; CHECK: %bail2
 132 ; CHECK: %bail3
 133
 134 entry:
 135   br label %body1
 136
 137 body1:
 138   %iv = phi i32 [ 0, %entry ], [ %next, %body4 ]
 139   %base = phi i32 [ 0, %entry ], [ %sum, %body4 ]
 140   %bailcond1 = icmp eq i32 %base, 42
 141   br i1 %bailcond1, label %bail1, label %body2
 142
 143 bail1:
 144   ret i32 -1
 145
 146 body2:
 147   %bailcond2 = icmp eq i32 %base, 43
 148   br i1 %bailcond2, label %bail2, label %body3
 149
 150 bail2:
 151   ret i32 -2
 152
 153 body3:
 154   %bailcond3 = icmp eq i32 %base, 44
 155   br i1 %bailcond3, label %bail3, label %body4
 156
 157 bail3:
 158   ret i32 -3
 159
 160 body4:
 161   %arrayidx = getelementptr inbounds i32* %a, i32 %iv
 162   %0 = load i32* %arrayidx
 163   %sum = add nsw i32 %0, %base
 164   %next = add i32 %iv, 1
 165   %exitcond = icmp eq i32 %next, %i
 166   br i1 %exitcond, label %exit, label %body1
 167
 168 exit:
 169   ret i32 %sum
 170 }
 171
 172 define i32 @test_loop_align(i32 %i, i32* %a) {
 173 ; Check that we provide basic loop body alignment with the block placement
 174 ; pass.
 175 ; CHECK: test_loop_align:
 176 ; CHECK: %entry
 177 ; CHECK: .align [[ALIGN:[0-9]+]],
 178 ; CHECK-NEXT: %body
 179 ; CHECK: %exit
 180
 181 entry:
 182   br label %body
 183
 184 body:
 185   %iv = phi i32 [ 0, %entry ], [ %next, %body ]
 186   %base = phi i32 [ 0, %entry ], [ %sum, %body ]
 187   %arrayidx = getelementptr inbounds i32* %a, i32 %iv
 188   %0 = load i32* %arrayidx
 189   %sum = add nsw i32 %0, %base
 190   %next = add i32 %iv, 1
 191   %exitcond = icmp eq i32 %next, %i
 192   br i1 %exitcond, label %exit, label %body
 193
 194 exit:
 195   ret i32 %sum
 196 }
 197
 198 define i32 @test_nested_loop_align(i32 %i, i32* %a, i32* %b) {
 199 ; Check that we provide nested loop body alignment.
 200 ; CHECK: test_nested_loop_align:
 201 ; CHECK: %entry
 202 ; CHECK: .align [[ALIGN]],
 203 ; CHECK-NEXT: %loop.body.1
 204 ; CHECK: .align [[ALIGN]],
 205 ; CHECK-NEXT: %inner.loop.body
 206 ; CHECK-NOT: .align
 207 ; CHECK: %exit
 208
 209 entry:
 210   br label %loop.body.1
 211
 212 loop.body.1:
 213   %iv = phi i32 [ 0, %entry ], [ %next, %loop.body.2 ]
 214   %arrayidx = getelementptr inbounds i32* %a, i32 %iv
 215   %bidx = load i32* %arrayidx
 216   br label %inner.loop.body
 217
 218 inner.loop.body:
 219   %inner.iv = phi i32 [ 0, %loop.body.1 ], [ %inner.next, %inner.loop.body ]
 220   %base = phi i32 [ 0, %loop.body.1 ], [ %sum, %inner.loop.body ]
 221   %scaled_idx = mul i32 %bidx, %iv
 222   %inner.arrayidx = getelementptr inbounds i32* %b, i32 %scaled_idx
 223   %0 = load i32* %inner.arrayidx
 224   %sum = add nsw i32 %0, %base
 225   %inner.next = add i32 %iv, 1
 226   %inner.exitcond = icmp eq i32 %inner.next, %i
 227   br i1 %inner.exitcond, label %loop.body.2, label %inner.loop.body
 228
 229 loop.body.2:
 230   %next = add i32 %iv, 1
 231   %exitcond = icmp eq i32 %next, %i
 232   br i1 %exitcond, label %exit, label %loop.body.1
 233
 234 exit:
 235   ret i32 %sum
 236 }
 237
 238 define void @unnatural_cfg1() {
 239 ; Test that we can handle a loop with an inner unnatural loop at the end of
 240 ; a function. This is a gross CFG reduced out of the single source GCC.
 241 ; CHECK: unnatural_cfg1
 242 ; CHECK: %entry
 243 ; CHECK: %loop.body1
 244 ; CHECK: %loop.body2
 245 ; CHECK: %loop.body3
 246
 247 entry:
 248   br label %loop.header
 249
 250 loop.header:
 251   br label %loop.body1
 252
 253 loop.body1:
 254   br i1 undef, label %loop.body3, label %loop.body2
 255
 256 loop.body2:
 257   %ptr = load i32** undef, align 4
 258   br label %loop.body3
 259
 260 loop.body3:
 261   %myptr = phi i32* [ %ptr2, %loop.body5 ], [ %ptr, %loop.body2 ], [ undef, %loop.body1 ]
 262   %bcmyptr = bitcast i32* %myptr to i32*
 263   %val = load i32* %bcmyptr, align 4
 264   %comp = icmp eq i32 %val, 48
 265   br i1 %comp, label %loop.body4, label %loop.body5
 266
 267 loop.body4:
 268   br i1 undef, label %loop.header, label %loop.body5
 269
 270 loop.body5:
 271   %ptr2 = load i32** undef, align 4
 272   br label %loop.body3
 273 }
 274
 275 define void @unnatural_cfg2() {
 276 ; Test that we can handle a loop with a nested natural loop *and* an unnatural
 277 ; loop. This was reduced from a crash on block placement when run over
 278 ; single-source GCC.
 279 ; CHECK: unnatural_cfg2
 280 ; CHECK: %entry
 281 ; CHECK: %loop.header
 282 ; CHECK: %loop.body1
 283 ; CHECK: %loop.body2
 284 ; CHECK: %loop.body3
 285 ; CHECK: %loop.inner1.begin
 286 ; The end block is folded with %loop.body3...
 287 ; CHECK-NOT: %loop.inner1.end
 288 ; CHECK: %loop.body4
 289 ; CHECK: %loop.inner2.begin
 290 ; The loop.inner2.end block is folded
 291 ; CHECK: %bail
 292
 293 entry:
 294   br label %loop.header
 295
 296 loop.header:
 297   %comp0 = icmp eq i32* undef, null
 298   br i1 %comp0, label %bail, label %loop.body1
 299
 300 loop.body1:
 301   %val0 = load i32** undef, align 4
 302   br i1 undef, label %loop.body2, label %loop.inner1.begin
 303
 304 loop.body2:
 305   br i1 undef, label %loop.body4, label %loop.body3
 306
 307 loop.body3:
 308   %ptr1 = getelementptr inbounds i32* %val0, i32 0
 309   %castptr1 = bitcast i32* %ptr1 to i32**
 310   %val1 = load i32** %castptr1, align 4
 311   br label %loop.inner1.begin
 312
 313 loop.inner1.begin:
 314   %valphi = phi i32* [ %val2, %loop.inner1.end ], [ %val1, %loop.body3 ], [ %val0, %loop.body1 ]
 315   %castval = bitcast i32* %valphi to i32*
 316   %comp1 = icmp eq i32 undef, 48
 317   br i1 %comp1, label %loop.inner1.end, label %loop.body4
 318
 319 loop.inner1.end:
 320   %ptr2 = getelementptr inbounds i32* %valphi, i32 0
 321   %castptr2 = bitcast i32* %ptr2 to i32**
 322   %val2 = load i32** %castptr2, align 4
 323   br label %loop.inner1.begin
 324
 325 loop.body4.dead:
 326   br label %loop.body4
 327
 328 loop.body4:
 329   %comp2 = icmp ult i32 undef, 3
 330   br i1 %comp2, label %loop.inner2.begin, label %loop.end
 331
 332 loop.inner2.begin:
 333   br i1 false, label %loop.end, label %loop.inner2.end
 334
 335 loop.inner2.end:
 336   %comp3 = icmp eq i32 undef, 1769472
 337   br i1 %comp3, label %loop.end, label %loop.inner2.begin
 338
 339 loop.end:
 340   br label %loop.header
 341
 342 bail:
 343   unreachable
 344 }
 345
 346 define i32 @problematic_switch() {
 347 ; This function's CFG caused overlow in the machine branch probability
 348 ; calculation, triggering asserts. Make sure we don't crash on it.
 349 ; CHECK: problematic_switch
 350
 351 entry:
 352   switch i32 undef, label %exit [
 353     i32 879, label %bogus
 354     i32 877, label %step
 355     i32 876, label %step
 356     i32 875, label %step
 357     i32 874, label %step
 358     i32 873, label %step
 359     i32 872, label %step
 360     i32 868, label %step
 361     i32 867, label %step
 362     i32 866, label %step
 363     i32 861, label %step
 364     i32 860, label %step
 365     i32 856, label %step
 366     i32 855, label %step
 367     i32 854, label %step
 368     i32 831, label %step
 369     i32 830, label %step
 370     i32 829, label %step
 371     i32 828, label %step
 372     i32 815, label %step
 373     i32 814, label %step
 374     i32 811, label %step
 375     i32 806, label %step
 376     i32 805, label %step
 377     i32 804, label %step
 378     i32 803, label %step
 379     i32 802, label %step
 380     i32 801, label %step
 381     i32 800, label %step
 382     i32 799, label %step
 383     i32 798, label %step
 384     i32 797, label %step
 385     i32 796, label %step
 386     i32 795, label %step
 387   ]
 388 bogus:
 389   unreachable
 390 step:
 391   br label %exit
 392 exit:
 393   %merge = phi i32 [ 3, %step ], [ 6, %entry ]
 394   ret i32 %merge
 395 }
 396
 397 define void @fpcmp_unanalyzable_branch(i1 %cond) {
 398 ; This function's CFG contains an unanalyzable branch that is likely to be
 399 ; split due to having a different high-probability predecessor.
 400 ; CHECK: fpcmp_unanalyzable_branch
 401 ; CHECK: %entry
 402 ; CHECK: %exit
 403 ; CHECK-NOT: %if.then
 404 ; CHECK-NOT: %if.end
 405 ; CHECK-NOT: jne
 406 ; CHECK-NOT: jnp
 407 ; CHECK: jne
 408 ; CHECK-NEXT: jnp
 409 ; CHECK-NEXT: %if.then
 410
 411 entry:
 412 ; Note that this branch must be strongly biased toward
 413 ; 'entry.if.then_crit_edge' to ensure that we would try to form a chain for
 414 ; 'entry' -> 'entry.if.then_crit_edge' -> 'if.then'. It is the last edge in that
 415 ; chain which would violate the unanalyzable branch in 'exit', but we won't even
 416 ; try this trick unless 'if.then' is believed to almost always be reached from
 417 ; 'entry.if.then_crit_edge'.
 418   br i1 %cond, label %entry.if.then_crit_edge, label %lor.lhs.false, !prof !1
 419
 420 entry.if.then_crit_edge:
 421   %.pre14 = load i8* undef, align 1, !tbaa !0
 422   br label %if.then
 423
 424 lor.lhs.false:
 425   br i1 undef, label %if.end, label %exit
 426
 427 exit:
 428   %cmp.i = fcmp une double 0.000000e+00, undef
 429   br i1 %cmp.i, label %if.then, label %if.end
 430
 431 if.then:
 432   %0 = phi i8 [ %.pre14, %entry.if.then_crit_edge ], [ undef, %exit ]
 433   %1 = and i8 %0, 1
 434   store i8 %1, i8* undef, align 4, !tbaa !0
 435   br label %if.end
 436
 437 if.end:
 438   ret void
 439 }
 440
 441 !1 = metadata !{metadata !"branch_weights", i32 1000, i32 1}
 442
 443 declare i32 @f()
 444 declare i32 @g()
 445 declare i32 @h(i32 %x)
 446
 447 define i32 @test_global_cfg_break_profitability() {
 448 ; Check that our metrics for the profitability of a CFG break are global rather
 449 ; than local. A successor may be very hot, but if the current block isn't, it
 450 ; doesn't matter. Within this test the 'then' block is slightly warmer than the
 451 ; 'else' block, but not nearly enough to merit merging it with the exit block
 452 ; even though the probability of 'then' branching to the 'exit' block is very
 453 ; high.
 454 ; CHECK: test_global_cfg_break_profitability
 455 ; CHECK: calll f
 456 ; CHECK: calll g
 457 ; CHECK: calll h
 458 ; CHECK: ret
 459
 460 entry:
 461   br i1 undef, label %then, label %else, !prof !2
 462
 463 then:
 464   %then.result = call i32 @f()
 465   br label %exit
 466
 467 else:
 468   %else.result = call i32 @g()
 469   br label %exit
 470
 471 exit:
 472   %result = phi i32 [ %then.result, %then ], [ %else.result, %else ]
 473   %result2 = call i32 @h(i32 %result)
 474   ret i32 %result
 475 }
 476
 477 !2 = metadata !{metadata !"branch_weights", i32 3, i32 1}