llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-cost.ll

   1 ; Specifically exercise the cost modeling for non-trivial loop unswitching.
   2 ;
   3 ; RUN: opt -passes='loop(simple-loop-unswitch<nontrivial>),verify<loops>' -unswitch-threshold=5 -S < %s | FileCheck %s
   4 ; RUN: opt -passes='loop-mssa(simple-loop-unswitch<nontrivial>),verify<loops>' -unswitch-threshold=5 -S -verify-memoryssa < %s | FileCheck %s
   5
   6 declare void @a()
   7 declare void @b()
   8 declare void @x()
   9
  10 ; First establish enough code size in the duplicated 'loop_begin' block to
  11 ; suppress unswitching.
  12 define void @test_no_unswitch(ptr %ptr, i1 %cond) {
  13 ; CHECK-LABEL: @test_no_unswitch(
  14 entry:
  15   br label %loop_begin
  16 ; CHECK-NEXT:  entry:
  17 ; CHECK-NEXT:    br label %loop_begin
  18 ;
  19 ; We shouldn't have unswitched into any other block either.
  20 ; CHECK-NOT:     br i1 %cond
  21
  22 loop_begin:
  23   call void @x()
  24   call void @x()
  25   call void @x()
  26   call void @x()
  27   br i1 %cond, label %loop_a, label %loop_b
  28 ; CHECK:       loop_begin:
  29 ; CHECK-NEXT:    call void @x()
  30 ; CHECK-NEXT:    call void @x()
  31 ; CHECK-NEXT:    call void @x()
  32 ; CHECK-NEXT:    call void @x()
  33 ; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
  34
  35 loop_a:
  36   call void @a()
  37   br label %loop_latch
  38
  39 loop_b:
  40   call void @b()
  41   br label %loop_latch
  42
  43 loop_latch:
  44   %v = load i1, ptr %ptr
  45   br i1 %v, label %loop_begin, label %loop_exit
  46
  47 loop_exit:
  48   ret void
  49 }
  50
  51 ; Now check that the smaller formulation of 'loop_begin' does in fact unswitch
  52 ; with our low threshold.
  53 define void @test_unswitch(ptr %ptr, i1 %cond) {
  54 ; CHECK-LABEL: @test_unswitch(
  55 entry:
  56   br label %loop_begin
  57 ; CHECK-NEXT:  entry:
  58 ; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond
  59 ; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split.us, label %entry.split
  60
  61 loop_begin:
  62   call void @x()
  63   br i1 %cond, label %loop_a, label %loop_b
  64
  65 loop_a:
  66   call void @a()
  67   br label %loop_latch
  68 ; The 'loop_a' unswitched loop.
  69 ;
  70 ; CHECK:       entry.split.us:
  71 ; CHECK-NEXT:    br label %loop_begin.us
  72 ;
  73 ; CHECK:       loop_begin.us:
  74 ; CHECK-NEXT:    call void @x()
  75 ; CHECK-NEXT:    br label %loop_a.us
  76 ;
  77 ; CHECK:       loop_a.us:
  78 ; CHECK-NEXT:    call void @a()
  79 ; CHECK-NEXT:    br label %loop_latch.us
  80 ;
  81 ; CHECK:       loop_latch.us:
  82 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
  83 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
  84 ;
  85 ; CHECK:       loop_exit.split.us:
  86 ; CHECK-NEXT:    br label %loop_exit
  87
  88 loop_b:
  89   call void @b()
  90   br label %loop_latch
  91 ; The 'loop_b' unswitched loop.
  92 ;
  93 ; CHECK:       entry.split:
  94 ; CHECK-NEXT:    br label %loop_begin
  95 ;
  96 ; CHECK:       loop_begin:
  97 ; CHECK-NEXT:    call void @x()
  98 ; CHECK-NEXT:    br label %loop_b
  99 ;
 100 ; CHECK:       loop_b:
 101 ; CHECK-NEXT:    call void @b()
 102 ; CHECK-NEXT:    br label %loop_latch
 103 ;
 104 ; CHECK:       loop_latch:
 105 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
 106 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 107 ;
 108 ; CHECK:       loop_exit.split:
 109 ; CHECK-NEXT:    br label %loop_exit
 110
 111 loop_latch:
 112   %v = load i1, ptr %ptr
 113   br i1 %v, label %loop_begin, label %loop_exit
 114
 115 loop_exit:
 116   ret void
 117 ; CHECK:       loop_exit:
 118 ; CHECK-NEXT:    ret void
 119 }
 120
 121 ; Check that even with large amounts of code on either side of the unswitched
 122 ; branch, if that code would be kept in only one of the unswitched clones it
 123 ; doesn't contribute to the cost.
 124 define void @test_unswitch_non_dup_code(ptr %ptr, i1 %cond) {
 125 ; CHECK-LABEL: @test_unswitch_non_dup_code(
 126 entry:
 127   br label %loop_begin
 128 ; CHECK-NEXT:  entry:
 129 ; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond
 130 ; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split.us, label %entry.split
 131
 132 loop_begin:
 133   call void @x()
 134   br i1 %cond, label %loop_a, label %loop_b
 135
 136 loop_a:
 137   call void @a()
 138   call void @a()
 139   call void @a()
 140   call void @a()
 141   br label %loop_latch
 142 ; The 'loop_a' unswitched loop.
 143 ;
 144 ; CHECK:       entry.split.us:
 145 ; CHECK-NEXT:    br label %loop_begin.us
 146 ;
 147 ; CHECK:       loop_begin.us:
 148 ; CHECK-NEXT:    call void @x()
 149 ; CHECK-NEXT:    br label %loop_a.us
 150 ;
 151 ; CHECK:       loop_a.us:
 152 ; CHECK-NEXT:    call void @a()
 153 ; CHECK-NEXT:    call void @a()
 154 ; CHECK-NEXT:    call void @a()
 155 ; CHECK-NEXT:    call void @a()
 156 ; CHECK-NEXT:    br label %loop_latch.us
 157 ;
 158 ; CHECK:       loop_latch.us:
 159 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
 160 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 161 ;
 162 ; CHECK:       loop_exit.split.us:
 163 ; CHECK-NEXT:    br label %loop_exit
 164
 165 loop_b:
 166   call void @b()
 167   call void @b()
 168   call void @b()
 169   call void @b()
 170   br label %loop_latch
 171 ; The 'loop_b' unswitched loop.
 172 ;
 173 ; CHECK:       entry.split:
 174 ; CHECK-NEXT:    br label %loop_begin
 175 ;
 176 ; CHECK:       loop_begin:
 177 ; CHECK-NEXT:    call void @x()
 178 ; CHECK-NEXT:    br label %loop_b
 179 ;
 180 ; CHECK:       loop_b:
 181 ; CHECK-NEXT:    call void @b()
 182 ; CHECK-NEXT:    call void @b()
 183 ; CHECK-NEXT:    call void @b()
 184 ; CHECK-NEXT:    call void @b()
 185 ; CHECK-NEXT:    br label %loop_latch
 186 ;
 187 ; CHECK:       loop_latch:
 188 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
 189 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 190 ;
 191 ; CHECK:       loop_exit.split:
 192 ; CHECK-NEXT:    br label %loop_exit
 193
 194 loop_latch:
 195   %v = load i1, ptr %ptr
 196   br i1 %v, label %loop_begin, label %loop_exit
 197
 198 loop_exit:
 199   ret void
 200 ; CHECK:       loop_exit:
 201 ; CHECK-NEXT:    ret void
 202 }
 203
 204 ; Much like with non-duplicated code directly in the successor, we also won't
 205 ; duplicate even interesting CFGs.
 206 define void @test_unswitch_non_dup_code_in_cfg(ptr %ptr, i1 %cond) {
 207 ; CHECK-LABEL: @test_unswitch_non_dup_code_in_cfg(
 208 entry:
 209   br label %loop_begin
 210 ; CHECK-NEXT:  entry:
 211 ; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond
 212 ; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split.us, label %entry.split
 213
 214 loop_begin:
 215   call void @x()
 216   br i1 %cond, label %loop_a, label %loop_b
 217
 218 loop_a:
 219   %v1 = load i1, ptr %ptr
 220   br i1 %v1, label %loop_a_a, label %loop_a_b
 221
 222 loop_a_a:
 223   call void @a()
 224   br label %loop_latch
 225
 226 loop_a_b:
 227   call void @a()
 228   br label %loop_latch
 229 ; The 'loop_a' unswitched loop.
 230 ;
 231 ; CHECK:       entry.split.us:
 232 ; CHECK-NEXT:    br label %loop_begin.us
 233 ;
 234 ; CHECK:       loop_begin.us:
 235 ; CHECK-NEXT:    call void @x()
 236 ; CHECK-NEXT:    br label %loop_a.us
 237 ;
 238 ; CHECK:       loop_a.us:
 239 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
 240 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a_a.us, label %loop_a_b.us
 241 ;
 242 ; CHECK:       loop_a_b.us:
 243 ; CHECK-NEXT:    call void @a()
 244 ; CHECK-NEXT:    br label %loop_latch.us
 245 ;
 246 ; CHECK:       loop_a_a.us:
 247 ; CHECK-NEXT:    call void @a()
 248 ; CHECK-NEXT:    br label %loop_latch.us
 249 ;
 250 ; CHECK:       loop_latch.us:
 251 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
 252 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 253 ;
 254 ; CHECK:       loop_exit.split.us:
 255 ; CHECK-NEXT:    br label %loop_exit
 256
 257 loop_b:
 258   %v2 = load i1, ptr %ptr
 259   br i1 %v2, label %loop_b_a, label %loop_b_b
 260
 261 loop_b_a:
 262   call void @b()
 263   br label %loop_latch
 264
 265 loop_b_b:
 266   call void @b()
 267   br label %loop_latch
 268 ; The 'loop_b' unswitched loop.
 269 ;
 270 ; CHECK:       entry.split:
 271 ; CHECK-NEXT:    br label %loop_begin
 272 ;
 273 ; CHECK:       loop_begin:
 274 ; CHECK-NEXT:    call void @x()
 275 ; CHECK-NEXT:    br label %loop_b
 276 ;
 277 ; CHECK:       loop_b:
 278 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
 279 ; CHECK-NEXT:    br i1 %[[V]], label %loop_b_a, label %loop_b_b
 280 ;
 281 ; CHECK:       loop_b_a:
 282 ; CHECK-NEXT:    call void @b()
 283 ; CHECK-NEXT:    br label %loop_latch
 284 ;
 285 ; CHECK:       loop_b_b:
 286 ; CHECK-NEXT:    call void @b()
 287 ; CHECK-NEXT:    br label %loop_latch
 288 ;
 289 ; CHECK:       loop_latch:
 290 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
 291 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 292 ;
 293 ; CHECK:       loop_exit.split:
 294 ; CHECK-NEXT:    br label %loop_exit
 295
 296 loop_latch:
 297   %v3 = load i1, ptr %ptr
 298   br i1 %v3, label %loop_begin, label %loop_exit
 299
 300 loop_exit:
 301   ret void
 302 ; CHECK:       loop_exit:
 303 ; CHECK-NEXT:    ret void
 304 }
 305
 306 ; Check that even if there is *some* non-duplicated code on one side of an
 307 ; unswitch, we don't count any other code in the loop that will in fact have to
 308 ; be duplicated.
 309 define void @test_no_unswitch_non_dup_code(ptr %ptr, i1 %cond) {
 310 ; CHECK-LABEL: @test_no_unswitch_non_dup_code(
 311 entry:
 312   br label %loop_begin
 313 ; CHECK-NEXT:  entry:
 314 ; CHECK-NEXT:    br label %loop_begin
 315 ;
 316 ; We shouldn't have unswitched into any other block either.
 317 ; CHECK-NOT:     br i1 %cond
 318
 319 loop_begin:
 320   call void @x()
 321   br i1 %cond, label %loop_a, label %loop_b
 322 ; CHECK:       loop_begin:
 323 ; CHECK-NEXT:    call void @x()
 324 ; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
 325
 326 loop_a:
 327   %v1 = load i1, ptr %ptr
 328   br i1 %v1, label %loop_a_a, label %loop_a_b
 329
 330 loop_a_a:
 331   call void @a()
 332   br label %loop_latch
 333
 334 loop_a_b:
 335   call void @a()
 336   br label %loop_latch
 337
 338 loop_b:
 339   %v2 = load i1, ptr %ptr
 340   br i1 %v2, label %loop_b_a, label %loop_b_b
 341
 342 loop_b_a:
 343   call void @b()
 344   br label %loop_latch
 345
 346 loop_b_b:
 347   call void @b()
 348   br label %loop_latch
 349
 350 loop_latch:
 351   call void @x()
 352   call void @x()
 353   %v = load i1, ptr %ptr
 354   br i1 %v, label %loop_begin, label %loop_exit
 355
 356 loop_exit:
 357   ret void
 358 }
 359
 360 ; Check that we still unswitch when the exit block contains lots of code, even
 361 ; though we do clone the exit block as part of unswitching. This should work
 362 ; because we should split the exit block before anything inside it.
 363 define void @test_unswitch_large_exit(ptr %ptr, i1 %cond) {
 364 ; CHECK-LABEL: @test_unswitch_large_exit(
 365 entry:
 366   br label %loop_begin
 367 ; CHECK-NEXT:  entry:
 368 ; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond
 369 ; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split.us, label %entry.split
 370
 371 loop_begin:
 372   call void @x()
 373   br i1 %cond, label %loop_a, label %loop_b
 374
 375 loop_a:
 376   call void @a()
 377   br label %loop_latch
 378 ; The 'loop_a' unswitched loop.
 379 ;
 380 ; CHECK:       entry.split.us:
 381 ; CHECK-NEXT:    br label %loop_begin.us
 382 ;
 383 ; CHECK:       loop_begin.us:
 384 ; CHECK-NEXT:    call void @x()
 385 ; CHECK-NEXT:    br label %loop_a.us
 386 ;
 387 ; CHECK:       loop_a.us:
 388 ; CHECK-NEXT:    call void @a()
 389 ; CHECK-NEXT:    br label %loop_latch.us
 390 ;
 391 ; CHECK:       loop_latch.us:
 392 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
 393 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 394 ;
 395 ; CHECK:       loop_exit.split.us:
 396 ; CHECK-NEXT:    br label %loop_exit
 397
 398 loop_b:
 399   call void @b()
 400   br label %loop_latch
 401 ; The 'loop_b' unswitched loop.
 402 ;
 403 ; CHECK:       entry.split:
 404 ; CHECK-NEXT:    br label %loop_begin
 405 ;
 406 ; CHECK:       loop_begin:
 407 ; CHECK-NEXT:    call void @x()
 408 ; CHECK-NEXT:    br label %loop_b
 409 ;
 410 ; CHECK:       loop_b:
 411 ; CHECK-NEXT:    call void @b()
 412 ; CHECK-NEXT:    br label %loop_latch
 413 ;
 414 ; CHECK:       loop_latch:
 415 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
 416 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 417 ;
 418 ; CHECK:       loop_exit.split:
 419 ; CHECK-NEXT:    br label %loop_exit
 420
 421 loop_latch:
 422   %v = load i1, ptr %ptr
 423   br i1 %v, label %loop_begin, label %loop_exit
 424
 425 loop_exit:
 426   call void @x()
 427   call void @x()
 428   call void @x()
 429   call void @x()
 430   ret void
 431 ; CHECK:       loop_exit:
 432 ; CHECK-NEXT:    call void @x()
 433 ; CHECK-NEXT:    call void @x()
 434 ; CHECK-NEXT:    call void @x()
 435 ; CHECK-NEXT:    call void @x()
 436 ; CHECK-NEXT:    ret void
 437 }
 438
 439 ; Check that we handle a dedicated exit edge unswitch which is still
 440 ; non-trivial and has lots of code in the exit.
 441 define void @test_unswitch_dedicated_exiting(ptr %ptr, i1 %cond) {
 442 ; CHECK-LABEL: @test_unswitch_dedicated_exiting(
 443 entry:
 444   br label %loop_begin
 445 ; CHECK-NEXT:  entry:
 446 ; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond
 447 ; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split.us, label %entry.split
 448
 449 loop_begin:
 450   call void @x()
 451   br i1 %cond, label %loop_a, label %loop_b_exit
 452
 453 loop_a:
 454   call void @a()
 455   br label %loop_latch
 456 ; The 'loop_a' unswitched loop.
 457 ;
 458 ; CHECK:       entry.split.us:
 459 ; CHECK-NEXT:    br label %loop_begin.us
 460 ;
 461 ; CHECK:       loop_begin.us:
 462 ; CHECK-NEXT:    call void @x()
 463 ; CHECK-NEXT:    br label %loop_a.us
 464 ;
 465 ; CHECK:       loop_a.us:
 466 ; CHECK-NEXT:    call void @a()
 467 ; CHECK-NEXT:    br label %loop_latch.us
 468 ;
 469 ; CHECK:       loop_latch.us:
 470 ; CHECK-NEXT:    %[[V:.*]] = load i1, ptr %ptr
 471 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 472 ;
 473 ; CHECK:       loop_exit.split.us:
 474 ; CHECK-NEXT:    br label %loop_exit
 475
 476 loop_b_exit:
 477   call void @b()
 478   call void @b()
 479   call void @b()
 480   call void @b()
 481   ret void
 482 ; The 'loop_b_exit' unswitched exit path.
 483 ;
 484 ; CHECK:       entry.split:
 485 ; CHECK-NEXT:    br label %loop_begin
 486 ;
 487 ; CHECK:       loop_begin:
 488 ; CHECK-NEXT:    call void @x()
 489 ; CHECK-NEXT:    br label %loop_b_exit
 490 ;
 491 ; CHECK:       loop_b_exit:
 492 ; CHECK-NEXT:    call void @b()
 493 ; CHECK-NEXT:    call void @b()
 494 ; CHECK-NEXT:    call void @b()
 495 ; CHECK-NEXT:    call void @b()
 496 ; CHECK-NEXT:    ret void
 497
 498 loop_latch:
 499   %v = load i1, ptr %ptr
 500   br i1 %v, label %loop_begin, label %loop_exit
 501
 502 loop_exit:
 503   ret void
 504 ; CHECK:       loop_exit:
 505 ; CHECK-NEXT:    ret void
 506 }