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 6declare void @a() 7declare void @b() 8declare void @x() 9 10; First establish enough code size in the duplicated 'loop_begin' block to 11; suppress unswitching. 12define void @test_no_unswitch(i1* %ptr, i1 %cond) { 13; CHECK-LABEL: @test_no_unswitch( 14entry: 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 22loop_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 35loop_a: 36 call void @a() 37 br label %loop_latch 38 39loop_b: 40 call void @b() 41 br label %loop_latch 42 43loop_latch: 44 %v = load i1, i1* %ptr 45 br i1 %v, label %loop_begin, label %loop_exit 46 47loop_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. 53define void @test_unswitch(i1* %ptr, i1 %cond) { 54; CHECK-LABEL: @test_unswitch( 55entry: 56 br label %loop_begin 57; CHECK-NEXT: entry: 58; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 59 60loop_begin: 61 call void @x() 62 br i1 %cond, label %loop_a, label %loop_b 63 64loop_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 87loop_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 110loop_latch: 111 %v = load i1, i1* %ptr 112 br i1 %v, label %loop_begin, label %loop_exit 113 114loop_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. 123define void @test_unswitch_non_dup_code(i1* %ptr, i1 %cond) { 124; CHECK-LABEL: @test_unswitch_non_dup_code( 125entry: 126 br label %loop_begin 127; CHECK-NEXT: entry: 128; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 129 130loop_begin: 131 call void @x() 132 br i1 %cond, label %loop_a, label %loop_b 133 134loop_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 163loop_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 192loop_latch: 193 %v = load i1, i1* %ptr 194 br i1 %v, label %loop_begin, label %loop_exit 195 196loop_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. 204define void @test_unswitch_non_dup_code_in_cfg(i1* %ptr, i1 %cond) { 205; CHECK-LABEL: @test_unswitch_non_dup_code_in_cfg( 206entry: 207 br label %loop_begin 208; CHECK-NEXT: entry: 209; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 210 211loop_begin: 212 call void @x() 213 br i1 %cond, label %loop_a, label %loop_b 214 215loop_a: 216 %v1 = load i1, i1* %ptr 217 br i1 %v1, label %loop_a_a, label %loop_a_b 218 219loop_a_a: 220 call void @a() 221 br label %loop_latch 222 223loop_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 254loop_b: 255 %v2 = load i1, i1* %ptr 256 br i1 %v2, label %loop_b_a, label %loop_b_b 257 258loop_b_a: 259 call void @b() 260 br label %loop_latch 261 262loop_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 293loop_latch: 294 %v3 = load i1, i1* %ptr 295 br i1 %v3, label %loop_begin, label %loop_exit 296 297loop_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. 306define void @test_no_unswitch_non_dup_code(i1* %ptr, i1 %cond) { 307; CHECK-LABEL: @test_no_unswitch_non_dup_code( 308entry: 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 316loop_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 323loop_a: 324 %v1 = load i1, i1* %ptr 325 br i1 %v1, label %loop_a_a, label %loop_a_b 326 327loop_a_a: 328 call void @a() 329 br label %loop_latch 330 331loop_a_b: 332 call void @a() 333 br label %loop_latch 334 335loop_b: 336 %v2 = load i1, i1* %ptr 337 br i1 %v2, label %loop_b_a, label %loop_b_b 338 339loop_b_a: 340 call void @b() 341 br label %loop_latch 342 343loop_b_b: 344 call void @b() 345 br label %loop_latch 346 347loop_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 353loop_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. 360define void @test_unswitch_large_exit(i1* %ptr, i1 %cond) { 361; CHECK-LABEL: @test_unswitch_large_exit( 362entry: 363 br label %loop_begin 364; CHECK-NEXT: entry: 365; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 366 367loop_begin: 368 call void @x() 369 br i1 %cond, label %loop_a, label %loop_b 370 371loop_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 394loop_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 417loop_latch: 418 %v = load i1, i1* %ptr 419 br i1 %v, label %loop_begin, label %loop_exit 420 421loop_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. 437define void @test_unswitch_dedicated_exiting(i1* %ptr, i1 %cond) { 438; CHECK-LABEL: @test_unswitch_dedicated_exiting( 439entry: 440 br label %loop_begin 441; CHECK-NEXT: entry: 442; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 443 444loop_begin: 445 call void @x() 446 br i1 %cond, label %loop_a, label %loop_b_exit 447 448loop_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 471loop_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 493loop_latch: 494 %v = load i1, i1* %ptr 495 br i1 %v, label %loop_begin, label %loop_exit 496 497loop_exit: 498 ret void 499; CHECK: loop_exit: 500; CHECK-NEXT: ret void 501} 502