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 8declare void @a() 9declare void @b() 10declare void @x() 11 12; First establish enough code size in the duplicated 'loop_begin' block to 13; suppress unswitching. 14define void @test_no_unswitch(i1* %ptr, i1 %cond) { 15; CHECK-LABEL: @test_no_unswitch( 16entry: 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 24loop_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 37loop_a: 38 call void @a() 39 br label %loop_latch 40 41loop_b: 42 call void @b() 43 br label %loop_latch 44 45loop_latch: 46 %v = load i1, i1* %ptr 47 br i1 %v, label %loop_begin, label %loop_exit 48 49loop_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. 55define void @test_unswitch(i1* %ptr, i1 %cond) { 56; CHECK-LABEL: @test_unswitch( 57entry: 58 br label %loop_begin 59; CHECK-NEXT: entry: 60; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 61 62loop_begin: 63 call void @x() 64 br i1 %cond, label %loop_a, label %loop_b 65 66loop_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 89loop_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 112loop_latch: 113 %v = load i1, i1* %ptr 114 br i1 %v, label %loop_begin, label %loop_exit 115 116loop_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. 125define void @test_unswitch_non_dup_code(i1* %ptr, i1 %cond) { 126; CHECK-LABEL: @test_unswitch_non_dup_code( 127entry: 128 br label %loop_begin 129; CHECK-NEXT: entry: 130; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 131 132loop_begin: 133 call void @x() 134 br i1 %cond, label %loop_a, label %loop_b 135 136loop_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 165loop_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 194loop_latch: 195 %v = load i1, i1* %ptr 196 br i1 %v, label %loop_begin, label %loop_exit 197 198loop_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. 206define void @test_unswitch_non_dup_code_in_cfg(i1* %ptr, i1 %cond) { 207; CHECK-LABEL: @test_unswitch_non_dup_code_in_cfg( 208entry: 209 br label %loop_begin 210; CHECK-NEXT: entry: 211; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 212 213loop_begin: 214 call void @x() 215 br i1 %cond, label %loop_a, label %loop_b 216 217loop_a: 218 %v1 = load i1, i1* %ptr 219 br i1 %v1, label %loop_a_a, label %loop_a_b 220 221loop_a_a: 222 call void @a() 223 br label %loop_latch 224 225loop_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 256loop_b: 257 %v2 = load i1, i1* %ptr 258 br i1 %v2, label %loop_b_a, label %loop_b_b 259 260loop_b_a: 261 call void @b() 262 br label %loop_latch 263 264loop_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 295loop_latch: 296 %v3 = load i1, i1* %ptr 297 br i1 %v3, label %loop_begin, label %loop_exit 298 299loop_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. 308define void @test_no_unswitch_non_dup_code(i1* %ptr, i1 %cond) { 309; CHECK-LABEL: @test_no_unswitch_non_dup_code( 310entry: 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 318loop_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 325loop_a: 326 %v1 = load i1, i1* %ptr 327 br i1 %v1, label %loop_a_a, label %loop_a_b 328 329loop_a_a: 330 call void @a() 331 br label %loop_latch 332 333loop_a_b: 334 call void @a() 335 br label %loop_latch 336 337loop_b: 338 %v2 = load i1, i1* %ptr 339 br i1 %v2, label %loop_b_a, label %loop_b_b 340 341loop_b_a: 342 call void @b() 343 br label %loop_latch 344 345loop_b_b: 346 call void @b() 347 br label %loop_latch 348 349loop_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 355loop_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. 362define void @test_unswitch_large_exit(i1* %ptr, i1 %cond) { 363; CHECK-LABEL: @test_unswitch_large_exit( 364entry: 365 br label %loop_begin 366; CHECK-NEXT: entry: 367; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 368 369loop_begin: 370 call void @x() 371 br i1 %cond, label %loop_a, label %loop_b 372 373loop_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 396loop_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 419loop_latch: 420 %v = load i1, i1* %ptr 421 br i1 %v, label %loop_begin, label %loop_exit 422 423loop_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. 439define void @test_unswitch_dedicated_exiting(i1* %ptr, i1 %cond) { 440; CHECK-LABEL: @test_unswitch_dedicated_exiting( 441entry: 442 br label %loop_begin 443; CHECK-NEXT: entry: 444; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 445 446loop_begin: 447 call void @x() 448 br i1 %cond, label %loop_a, label %loop_b_exit 449 450loop_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 473loop_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 495loop_latch: 496 %v = load i1, i1* %ptr 497 br i1 %v, label %loop_begin, label %loop_exit 498 499loop_exit: 500 ret void 501; CHECK: loop_exit: 502; CHECK-NEXT: ret void 503} 504