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