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