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

   1 ; Specifically exercise the cost modeling for non-trivial loop unswitching.
   2 ;
   3 ; RUN: opt -passes='loop(unswitch<nontrivial>),verify<loops>' -unswitch-threshold=5 -S < %s | FileCheck %s
   4 ; RUN: opt -passes='loop-mssa(unswitch<nontrivial>),verify<loops>' -unswitch-threshold=5 -S < %s | FileCheck %s
   5 ; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -unswitch-threshold=5 -S < %s | FileCheck %s
   6 ; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -unswitch-threshold=5 -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s | FileCheck %s
   7
   8 declare void @a()
   9 declare void @b()
  10 declare void @x()
  11
  12 ; First establish enough code size in the duplicated 'loop_begin' block to
  13 ; suppress unswitching.
  14 define void @test_no_unswitch(i1* %ptr, i1 %cond) {
  15 ; CHECK-LABEL: @test_no_unswitch(
  16 entry:
  17   br label %loop_begin
  18 ; CHECK-NEXT:  entry:
  19 ; CHECK-NEXT:    br label %loop_begin
  20 ;
  21 ; We shouldn't have unswitched into any other block either.
  22 ; CHECK-NOT:     br i1 %cond
  23
  24 loop_begin:
  25   call void @x()
  26   call void @x()
  27   call void @x()
  28   call void @x()
  29   br i1 %cond, label %loop_a, label %loop_b
  30 ; CHECK:       loop_begin:
  31 ; CHECK-NEXT:    call void @x()
  32 ; CHECK-NEXT:    call void @x()
  33 ; CHECK-NEXT:    call void @x()
  34 ; CHECK-NEXT:    call void @x()
  35 ; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
  36
  37 loop_a:
  38   call void @a()
  39   br label %loop_latch
  40
  41 loop_b:
  42   call void @b()
  43   br label %loop_latch
  44
  45 loop_latch:
  46   %v = load i1, i1* %ptr
  47   br i1 %v, label %loop_begin, label %loop_exit
  48
  49 loop_exit:
  50   ret void
  51 }
  52
  53 ; Now check that the smaller formulation of 'loop_begin' does in fact unswitch
  54 ; with our low threshold.
  55 define void @test_unswitch(i1* %ptr, i1 %cond) {
  56 ; CHECK-LABEL: @test_unswitch(
  57 entry:
  58   br label %loop_begin
  59 ; CHECK-NEXT:  entry:
  60 ; CHECK-NEXT:    br i1 %cond, 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, i1* %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, i1* %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, i1* %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(i1* %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:    br i1 %cond, 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, i1* %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, i1* %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, i1* %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(i1* %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:    br i1 %cond, label %entry.split.us, label %entry.split
 212
 213 loop_begin:
 214   call void @x()
 215   br i1 %cond, label %loop_a, label %loop_b
 216
 217 loop_a:
 218   %v1 = load i1, i1* %ptr
 219   br i1 %v1, label %loop_a_a, label %loop_a_b
 220
 221 loop_a_a:
 222   call void @a()
 223   br label %loop_latch
 224
 225 loop_a_b:
 226   call void @a()
 227   br label %loop_latch
 228 ; The 'loop_a' unswitched loop.
 229 ;
 230 ; CHECK:       entry.split.us:
 231 ; CHECK-NEXT:    br label %loop_begin.us
 232 ;
 233 ; CHECK:       loop_begin.us:
 234 ; CHECK-NEXT:    call void @x()
 235 ; CHECK-NEXT:    br label %loop_a.us
 236 ;
 237 ; CHECK:       loop_a.us:
 238 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 239 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a_a.us, label %loop_a_b.us
 240 ;
 241 ; CHECK:       loop_a_b.us:
 242 ; CHECK-NEXT:    call void @a()
 243 ; CHECK-NEXT:    br label %loop_latch.us
 244 ;
 245 ; CHECK:       loop_a_a.us:
 246 ; CHECK-NEXT:    call void @a()
 247 ; CHECK-NEXT:    br label %loop_latch.us
 248 ;
 249 ; CHECK:       loop_latch.us:
 250 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 251 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 252 ;
 253 ; CHECK:       loop_exit.split.us:
 254 ; CHECK-NEXT:    br label %loop_exit
 255
 256 loop_b:
 257   %v2 = load i1, i1* %ptr
 258   br i1 %v2, label %loop_b_a, label %loop_b_b
 259
 260 loop_b_a:
 261   call void @b()
 262   br label %loop_latch
 263
 264 loop_b_b:
 265   call void @b()
 266   br label %loop_latch
 267 ; The 'loop_b' unswitched loop.
 268 ;
 269 ; CHECK:       entry.split:
 270 ; CHECK-NEXT:    br label %loop_begin
 271 ;
 272 ; CHECK:       loop_begin:
 273 ; CHECK-NEXT:    call void @x()
 274 ; CHECK-NEXT:    br label %loop_b
 275 ;
 276 ; CHECK:       loop_b:
 277 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 278 ; CHECK-NEXT:    br i1 %[[V]], label %loop_b_a, label %loop_b_b
 279 ;
 280 ; CHECK:       loop_b_a:
 281 ; CHECK-NEXT:    call void @b()
 282 ; CHECK-NEXT:    br label %loop_latch
 283 ;
 284 ; CHECK:       loop_b_b:
 285 ; CHECK-NEXT:    call void @b()
 286 ; CHECK-NEXT:    br label %loop_latch
 287 ;
 288 ; CHECK:       loop_latch:
 289 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 290 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 291 ;
 292 ; CHECK:       loop_exit.split:
 293 ; CHECK-NEXT:    br label %loop_exit
 294
 295 loop_latch:
 296   %v3 = load i1, i1* %ptr
 297   br i1 %v3, label %loop_begin, label %loop_exit
 298
 299 loop_exit:
 300   ret void
 301 ; CHECK:       loop_exit:
 302 ; CHECK-NEXT:    ret void
 303 }
 304
 305 ; Check that even if there is *some* non-duplicated code on one side of an
 306 ; unswitch, we don't count any other code in the loop that will in fact have to
 307 ; be duplicated.
 308 define void @test_no_unswitch_non_dup_code(i1* %ptr, i1 %cond) {
 309 ; CHECK-LABEL: @test_no_unswitch_non_dup_code(
 310 entry:
 311   br label %loop_begin
 312 ; CHECK-NEXT:  entry:
 313 ; CHECK-NEXT:    br label %loop_begin
 314 ;
 315 ; We shouldn't have unswitched into any other block either.
 316 ; CHECK-NOT:     br i1 %cond
 317
 318 loop_begin:
 319   call void @x()
 320   br i1 %cond, label %loop_a, label %loop_b
 321 ; CHECK:       loop_begin:
 322 ; CHECK-NEXT:    call void @x()
 323 ; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
 324
 325 loop_a:
 326   %v1 = load i1, i1* %ptr
 327   br i1 %v1, label %loop_a_a, label %loop_a_b
 328
 329 loop_a_a:
 330   call void @a()
 331   br label %loop_latch
 332
 333 loop_a_b:
 334   call void @a()
 335   br label %loop_latch
 336
 337 loop_b:
 338   %v2 = load i1, i1* %ptr
 339   br i1 %v2, label %loop_b_a, label %loop_b_b
 340
 341 loop_b_a:
 342   call void @b()
 343   br label %loop_latch
 344
 345 loop_b_b:
 346   call void @b()
 347   br label %loop_latch
 348
 349 loop_latch:
 350   call void @x()
 351   call void @x()
 352   %v = load i1, i1* %ptr
 353   br i1 %v, label %loop_begin, label %loop_exit
 354
 355 loop_exit:
 356   ret void
 357 }
 358
 359 ; Check that we still unswitch when the exit block contains lots of code, even
 360 ; though we do clone the exit block as part of unswitching. This should work
 361 ; because we should split the exit block before anything inside it.
 362 define void @test_unswitch_large_exit(i1* %ptr, i1 %cond) {
 363 ; CHECK-LABEL: @test_unswitch_large_exit(
 364 entry:
 365   br label %loop_begin
 366 ; CHECK-NEXT:  entry:
 367 ; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
 368
 369 loop_begin:
 370   call void @x()
 371   br i1 %cond, label %loop_a, label %loop_b
 372
 373 loop_a:
 374   call void @a()
 375   br label %loop_latch
 376 ; The 'loop_a' unswitched loop.
 377 ;
 378 ; CHECK:       entry.split.us:
 379 ; CHECK-NEXT:    br label %loop_begin.us
 380 ;
 381 ; CHECK:       loop_begin.us:
 382 ; CHECK-NEXT:    call void @x()
 383 ; CHECK-NEXT:    br label %loop_a.us
 384 ;
 385 ; CHECK:       loop_a.us:
 386 ; CHECK-NEXT:    call void @a()
 387 ; CHECK-NEXT:    br label %loop_latch.us
 388 ;
 389 ; CHECK:       loop_latch.us:
 390 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 391 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 392 ;
 393 ; CHECK:       loop_exit.split.us:
 394 ; CHECK-NEXT:    br label %loop_exit
 395
 396 loop_b:
 397   call void @b()
 398   br label %loop_latch
 399 ; The 'loop_b' unswitched loop.
 400 ;
 401 ; CHECK:       entry.split:
 402 ; CHECK-NEXT:    br label %loop_begin
 403 ;
 404 ; CHECK:       loop_begin:
 405 ; CHECK-NEXT:    call void @x()
 406 ; CHECK-NEXT:    br label %loop_b
 407 ;
 408 ; CHECK:       loop_b:
 409 ; CHECK-NEXT:    call void @b()
 410 ; CHECK-NEXT:    br label %loop_latch
 411 ;
 412 ; CHECK:       loop_latch:
 413 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 414 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 415 ;
 416 ; CHECK:       loop_exit.split:
 417 ; CHECK-NEXT:    br label %loop_exit
 418
 419 loop_latch:
 420   %v = load i1, i1* %ptr
 421   br i1 %v, label %loop_begin, label %loop_exit
 422
 423 loop_exit:
 424   call void @x()
 425   call void @x()
 426   call void @x()
 427   call void @x()
 428   ret void
 429 ; CHECK:       loop_exit:
 430 ; CHECK-NEXT:    call void @x()
 431 ; CHECK-NEXT:    call void @x()
 432 ; CHECK-NEXT:    call void @x()
 433 ; CHECK-NEXT:    call void @x()
 434 ; CHECK-NEXT:    ret void
 435 }
 436
 437 ; Check that we handle a dedicated exit edge unswitch which is still
 438 ; non-trivial and has lots of code in the exit.
 439 define void @test_unswitch_dedicated_exiting(i1* %ptr, i1 %cond) {
 440 ; CHECK-LABEL: @test_unswitch_dedicated_exiting(
 441 entry:
 442   br label %loop_begin
 443 ; CHECK-NEXT:  entry:
 444 ; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
 445
 446 loop_begin:
 447   call void @x()
 448   br i1 %cond, label %loop_a, label %loop_b_exit
 449
 450 loop_a:
 451   call void @a()
 452   br label %loop_latch
 453 ; The 'loop_a' unswitched loop.
 454 ;
 455 ; CHECK:       entry.split.us:
 456 ; CHECK-NEXT:    br label %loop_begin.us
 457 ;
 458 ; CHECK:       loop_begin.us:
 459 ; CHECK-NEXT:    call void @x()
 460 ; CHECK-NEXT:    br label %loop_a.us
 461 ;
 462 ; CHECK:       loop_a.us:
 463 ; CHECK-NEXT:    call void @a()
 464 ; CHECK-NEXT:    br label %loop_latch.us
 465 ;
 466 ; CHECK:       loop_latch.us:
 467 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 468 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 469 ;
 470 ; CHECK:       loop_exit.split.us:
 471 ; CHECK-NEXT:    br label %loop_exit
 472
 473 loop_b_exit:
 474   call void @b()
 475   call void @b()
 476   call void @b()
 477   call void @b()
 478   ret void
 479 ; The 'loop_b_exit' unswitched exit path.
 480 ;
 481 ; CHECK:       entry.split:
 482 ; CHECK-NEXT:    br label %loop_begin
 483 ;
 484 ; CHECK:       loop_begin:
 485 ; CHECK-NEXT:    call void @x()
 486 ; CHECK-NEXT:    br label %loop_b_exit
 487 ;
 488 ; CHECK:       loop_b_exit:
 489 ; CHECK-NEXT:    call void @b()
 490 ; CHECK-NEXT:    call void @b()
 491 ; CHECK-NEXT:    call void @b()
 492 ; CHECK-NEXT:    call void @b()
 493 ; CHECK-NEXT:    ret void
 494
 495 loop_latch:
 496   %v = load i1, i1* %ptr
 497   br i1 %v, label %loop_begin, label %loop_exit
 498
 499 loop_exit:
 500   ret void
 501 ; CHECK:       loop_exit:
 502 ; CHECK-NEXT:    ret void
 503 }