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 -simple-loop-unswitch -enable-nontrivial-unswitch -unswitch-threshold=5 -S < %s | FileCheck %s
   5 ; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -unswitch-threshold=5 -enable-mssa-loop-dependency=true -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(i1* %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, i1* %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(i1* %ptr, i1 %cond) {
  55 ; CHECK-LABEL: @test_unswitch(
  56 entry:
  57   br label %loop_begin
  58 ; CHECK-NEXT:  entry:
  59 ; CHECK-NEXT:    br i1 %cond, 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, i1* %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, i1* %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, i1* %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(i1* %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:    br i1 %cond, label %entry.split.us, label %entry.split
 130
 131 loop_begin:
 132   call void @x()
 133   br i1 %cond, label %loop_a, label %loop_b
 134
 135 loop_a:
 136   call void @a()
 137   call void @a()
 138   call void @a()
 139   call void @a()
 140   br label %loop_latch
 141 ; The 'loop_a' unswitched loop.
 142 ;
 143 ; CHECK:       entry.split.us:
 144 ; CHECK-NEXT:    br label %loop_begin.us
 145 ;
 146 ; CHECK:       loop_begin.us:
 147 ; CHECK-NEXT:    call void @x()
 148 ; CHECK-NEXT:    br label %loop_a.us
 149 ;
 150 ; CHECK:       loop_a.us:
 151 ; CHECK-NEXT:    call void @a()
 152 ; CHECK-NEXT:    call void @a()
 153 ; CHECK-NEXT:    call void @a()
 154 ; CHECK-NEXT:    call void @a()
 155 ; CHECK-NEXT:    br label %loop_latch.us
 156 ;
 157 ; CHECK:       loop_latch.us:
 158 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 159 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 160 ;
 161 ; CHECK:       loop_exit.split.us:
 162 ; CHECK-NEXT:    br label %loop_exit
 163
 164 loop_b:
 165   call void @b()
 166   call void @b()
 167   call void @b()
 168   call void @b()
 169   br label %loop_latch
 170 ; The 'loop_b' unswitched loop.
 171 ;
 172 ; CHECK:       entry.split:
 173 ; CHECK-NEXT:    br label %loop_begin
 174 ;
 175 ; CHECK:       loop_begin:
 176 ; CHECK-NEXT:    call void @x()
 177 ; CHECK-NEXT:    br label %loop_b
 178 ;
 179 ; CHECK:       loop_b:
 180 ; CHECK-NEXT:    call void @b()
 181 ; CHECK-NEXT:    call void @b()
 182 ; CHECK-NEXT:    call void @b()
 183 ; CHECK-NEXT:    call void @b()
 184 ; CHECK-NEXT:    br label %loop_latch
 185 ;
 186 ; CHECK:       loop_latch:
 187 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 188 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 189 ;
 190 ; CHECK:       loop_exit.split:
 191 ; CHECK-NEXT:    br label %loop_exit
 192
 193 loop_latch:
 194   %v = load i1, i1* %ptr
 195   br i1 %v, label %loop_begin, label %loop_exit
 196
 197 loop_exit:
 198   ret void
 199 ; CHECK:       loop_exit:
 200 ; CHECK-NEXT:    ret void
 201 }
 202
 203 ; Much like with non-duplicated code directly in the successor, we also won't
 204 ; duplicate even interesting CFGs.
 205 define void @test_unswitch_non_dup_code_in_cfg(i1* %ptr, i1 %cond) {
 206 ; CHECK-LABEL: @test_unswitch_non_dup_code_in_cfg(
 207 entry:
 208   br label %loop_begin
 209 ; CHECK-NEXT:  entry:
 210 ; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
 211
 212 loop_begin:
 213   call void @x()
 214   br i1 %cond, label %loop_a, label %loop_b
 215
 216 loop_a:
 217   %v1 = load i1, i1* %ptr
 218   br i1 %v1, label %loop_a_a, label %loop_a_b
 219
 220 loop_a_a:
 221   call void @a()
 222   br label %loop_latch
 223
 224 loop_a_b:
 225   call void @a()
 226   br label %loop_latch
 227 ; The 'loop_a' unswitched loop.
 228 ;
 229 ; CHECK:       entry.split.us:
 230 ; CHECK-NEXT:    br label %loop_begin.us
 231 ;
 232 ; CHECK:       loop_begin.us:
 233 ; CHECK-NEXT:    call void @x()
 234 ; CHECK-NEXT:    br label %loop_a.us
 235 ;
 236 ; CHECK:       loop_a.us:
 237 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 238 ; CHECK-NEXT:    br i1 %[[V]], label %loop_a_a.us, label %loop_a_b.us
 239 ;
 240 ; CHECK:       loop_a_b.us:
 241 ; CHECK-NEXT:    call void @a()
 242 ; CHECK-NEXT:    br label %loop_latch.us
 243 ;
 244 ; CHECK:       loop_a_a.us:
 245 ; CHECK-NEXT:    call void @a()
 246 ; CHECK-NEXT:    br label %loop_latch.us
 247 ;
 248 ; CHECK:       loop_latch.us:
 249 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 250 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 251 ;
 252 ; CHECK:       loop_exit.split.us:
 253 ; CHECK-NEXT:    br label %loop_exit
 254
 255 loop_b:
 256   %v2 = load i1, i1* %ptr
 257   br i1 %v2, label %loop_b_a, label %loop_b_b
 258
 259 loop_b_a:
 260   call void @b()
 261   br label %loop_latch
 262
 263 loop_b_b:
 264   call void @b()
 265   br label %loop_latch
 266 ; The 'loop_b' unswitched loop.
 267 ;
 268 ; CHECK:       entry.split:
 269 ; CHECK-NEXT:    br label %loop_begin
 270 ;
 271 ; CHECK:       loop_begin:
 272 ; CHECK-NEXT:    call void @x()
 273 ; CHECK-NEXT:    br label %loop_b
 274 ;
 275 ; CHECK:       loop_b:
 276 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 277 ; CHECK-NEXT:    br i1 %[[V]], label %loop_b_a, label %loop_b_b
 278 ;
 279 ; CHECK:       loop_b_a:
 280 ; CHECK-NEXT:    call void @b()
 281 ; CHECK-NEXT:    br label %loop_latch
 282 ;
 283 ; CHECK:       loop_b_b:
 284 ; CHECK-NEXT:    call void @b()
 285 ; CHECK-NEXT:    br label %loop_latch
 286 ;
 287 ; CHECK:       loop_latch:
 288 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 289 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 290 ;
 291 ; CHECK:       loop_exit.split:
 292 ; CHECK-NEXT:    br label %loop_exit
 293
 294 loop_latch:
 295   %v3 = load i1, i1* %ptr
 296   br i1 %v3, label %loop_begin, label %loop_exit
 297
 298 loop_exit:
 299   ret void
 300 ; CHECK:       loop_exit:
 301 ; CHECK-NEXT:    ret void
 302 }
 303
 304 ; Check that even if there is *some* non-duplicated code on one side of an
 305 ; unswitch, we don't count any other code in the loop that will in fact have to
 306 ; be duplicated.
 307 define void @test_no_unswitch_non_dup_code(i1* %ptr, i1 %cond) {
 308 ; CHECK-LABEL: @test_no_unswitch_non_dup_code(
 309 entry:
 310   br label %loop_begin
 311 ; CHECK-NEXT:  entry:
 312 ; CHECK-NEXT:    br label %loop_begin
 313 ;
 314 ; We shouldn't have unswitched into any other block either.
 315 ; CHECK-NOT:     br i1 %cond
 316
 317 loop_begin:
 318   call void @x()
 319   br i1 %cond, label %loop_a, label %loop_b
 320 ; CHECK:       loop_begin:
 321 ; CHECK-NEXT:    call void @x()
 322 ; CHECK-NEXT:    br i1 %cond, label %loop_a, label %loop_b
 323
 324 loop_a:
 325   %v1 = load i1, i1* %ptr
 326   br i1 %v1, label %loop_a_a, label %loop_a_b
 327
 328 loop_a_a:
 329   call void @a()
 330   br label %loop_latch
 331
 332 loop_a_b:
 333   call void @a()
 334   br label %loop_latch
 335
 336 loop_b:
 337   %v2 = load i1, i1* %ptr
 338   br i1 %v2, label %loop_b_a, label %loop_b_b
 339
 340 loop_b_a:
 341   call void @b()
 342   br label %loop_latch
 343
 344 loop_b_b:
 345   call void @b()
 346   br label %loop_latch
 347
 348 loop_latch:
 349   call void @x()
 350   call void @x()
 351   %v = load i1, i1* %ptr
 352   br i1 %v, label %loop_begin, label %loop_exit
 353
 354 loop_exit:
 355   ret void
 356 }
 357
 358 ; Check that we still unswitch when the exit block contains lots of code, even
 359 ; though we do clone the exit block as part of unswitching. This should work
 360 ; because we should split the exit block before anything inside it.
 361 define void @test_unswitch_large_exit(i1* %ptr, i1 %cond) {
 362 ; CHECK-LABEL: @test_unswitch_large_exit(
 363 entry:
 364   br label %loop_begin
 365 ; CHECK-NEXT:  entry:
 366 ; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
 367
 368 loop_begin:
 369   call void @x()
 370   br i1 %cond, label %loop_a, label %loop_b
 371
 372 loop_a:
 373   call void @a()
 374   br label %loop_latch
 375 ; The 'loop_a' unswitched loop.
 376 ;
 377 ; CHECK:       entry.split.us:
 378 ; CHECK-NEXT:    br label %loop_begin.us
 379 ;
 380 ; CHECK:       loop_begin.us:
 381 ; CHECK-NEXT:    call void @x()
 382 ; CHECK-NEXT:    br label %loop_a.us
 383 ;
 384 ; CHECK:       loop_a.us:
 385 ; CHECK-NEXT:    call void @a()
 386 ; CHECK-NEXT:    br label %loop_latch.us
 387 ;
 388 ; CHECK:       loop_latch.us:
 389 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 390 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 391 ;
 392 ; CHECK:       loop_exit.split.us:
 393 ; CHECK-NEXT:    br label %loop_exit
 394
 395 loop_b:
 396   call void @b()
 397   br label %loop_latch
 398 ; The 'loop_b' unswitched loop.
 399 ;
 400 ; CHECK:       entry.split:
 401 ; CHECK-NEXT:    br label %loop_begin
 402 ;
 403 ; CHECK:       loop_begin:
 404 ; CHECK-NEXT:    call void @x()
 405 ; CHECK-NEXT:    br label %loop_b
 406 ;
 407 ; CHECK:       loop_b:
 408 ; CHECK-NEXT:    call void @b()
 409 ; CHECK-NEXT:    br label %loop_latch
 410 ;
 411 ; CHECK:       loop_latch:
 412 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 413 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
 414 ;
 415 ; CHECK:       loop_exit.split:
 416 ; CHECK-NEXT:    br label %loop_exit
 417
 418 loop_latch:
 419   %v = load i1, i1* %ptr
 420   br i1 %v, label %loop_begin, label %loop_exit
 421
 422 loop_exit:
 423   call void @x()
 424   call void @x()
 425   call void @x()
 426   call void @x()
 427   ret void
 428 ; CHECK:       loop_exit:
 429 ; CHECK-NEXT:    call void @x()
 430 ; CHECK-NEXT:    call void @x()
 431 ; CHECK-NEXT:    call void @x()
 432 ; CHECK-NEXT:    call void @x()
 433 ; CHECK-NEXT:    ret void
 434 }
 435
 436 ; Check that we handle a dedicated exit edge unswitch which is still
 437 ; non-trivial and has lots of code in the exit.
 438 define void @test_unswitch_dedicated_exiting(i1* %ptr, i1 %cond) {
 439 ; CHECK-LABEL: @test_unswitch_dedicated_exiting(
 440 entry:
 441   br label %loop_begin
 442 ; CHECK-NEXT:  entry:
 443 ; CHECK-NEXT:    br i1 %cond, label %entry.split.us, label %entry.split
 444
 445 loop_begin:
 446   call void @x()
 447   br i1 %cond, label %loop_a, label %loop_b_exit
 448
 449 loop_a:
 450   call void @a()
 451   br label %loop_latch
 452 ; The 'loop_a' unswitched loop.
 453 ;
 454 ; CHECK:       entry.split.us:
 455 ; CHECK-NEXT:    br label %loop_begin.us
 456 ;
 457 ; CHECK:       loop_begin.us:
 458 ; CHECK-NEXT:    call void @x()
 459 ; CHECK-NEXT:    br label %loop_a.us
 460 ;
 461 ; CHECK:       loop_a.us:
 462 ; CHECK-NEXT:    call void @a()
 463 ; CHECK-NEXT:    br label %loop_latch.us
 464 ;
 465 ; CHECK:       loop_latch.us:
 466 ; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
 467 ; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us
 468 ;
 469 ; CHECK:       loop_exit.split.us:
 470 ; CHECK-NEXT:    br label %loop_exit
 471
 472 loop_b_exit:
 473   call void @b()
 474   call void @b()
 475   call void @b()
 476   call void @b()
 477   ret void
 478 ; The 'loop_b_exit' unswitched exit path.
 479 ;
 480 ; CHECK:       entry.split:
 481 ; CHECK-NEXT:    br label %loop_begin
 482 ;
 483 ; CHECK:       loop_begin:
 484 ; CHECK-NEXT:    call void @x()
 485 ; CHECK-NEXT:    br label %loop_b_exit
 486 ;
 487 ; CHECK:       loop_b_exit:
 488 ; CHECK-NEXT:    call void @b()
 489 ; CHECK-NEXT:    call void @b()
 490 ; CHECK-NEXT:    call void @b()
 491 ; CHECK-NEXT:    call void @b()
 492 ; CHECK-NEXT:    ret void
 493
 494 loop_latch:
 495   %v = load i1, i1* %ptr
 496   br i1 %v, label %loop_begin, label %loop_exit
 497
 498 loop_exit:
 499   ret void
 500 ; CHECK:       loop_exit:
 501 ; CHECK-NEXT:    ret void
 502 }