507 lines · plain
1; Specifically exercise the cost modeling for non-trivial loop unswitching.2;3; RUN: opt -passes='loop(simple-loop-unswitch<nontrivial>),verify<loops>' -unswitch-threshold=5 -S < %s | FileCheck %s4; RUN: opt -passes='loop-mssa(simple-loop-unswitch<nontrivial>),verify<loops>' -unswitch-threshold=5 -S -verify-memoryssa < %s | FileCheck %s5 6declare void @a()7declare void @b()8declare void @x()9 10; First establish enough code size in the duplicated 'loop_begin' block to11; suppress unswitching.12define void @test_no_unswitch(ptr %ptr, i1 %cond) {13; CHECK-LABEL: @test_no_unswitch(14entry:15 br label %loop_begin16; CHECK-NEXT: entry:17; CHECK-NEXT: br label %loop_begin18;19; We shouldn't have unswitched into any other block either.20; CHECK-NOT: br i1 %cond21 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_b28; 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_b34 35loop_a:36 call void @a()37 br label %loop_latch38 39loop_b:40 call void @b()41 br label %loop_latch42 43loop_latch:44 %v = load i1, ptr %ptr45 br i1 %v, label %loop_begin, label %loop_exit46 47loop_exit:48 ret void49}50 51; Now check that the smaller formulation of 'loop_begin' does in fact unswitch52; with our low threshold.53define void @test_unswitch(ptr %ptr, i1 %cond) {54; CHECK-LABEL: @test_unswitch(55entry:56 br label %loop_begin57; CHECK-NEXT: entry:58; CHECK-NEXT: [[FROZEN:%.+]] = freeze i1 %cond59; CHECK-NEXT: br i1 [[FROZEN]], label %entry.split.us, label %entry.split60 61loop_begin:62 call void @x()63 br i1 %cond, label %loop_a, label %loop_b64 65loop_a:66 call void @a()67 br label %loop_latch68; The 'loop_a' unswitched loop.69;70; CHECK: entry.split.us:71; CHECK-NEXT: br label %loop_begin.us72;73; CHECK: loop_begin.us:74; CHECK-NEXT: call void @x()75; CHECK-NEXT: br label %loop_a.us76;77; CHECK: loop_a.us:78; CHECK-NEXT: call void @a()79; CHECK-NEXT: br label %loop_latch.us80;81; CHECK: loop_latch.us:82; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr83; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us84;85; CHECK: loop_exit.split.us:86; CHECK-NEXT: br label %loop_exit87 88loop_b:89 call void @b()90 br label %loop_latch91; The 'loop_b' unswitched loop.92;93; CHECK: entry.split:94; CHECK-NEXT: br label %loop_begin95;96; CHECK: loop_begin:97; CHECK-NEXT: call void @x()98; CHECK-NEXT: br label %loop_b99;100; CHECK: loop_b:101; CHECK-NEXT: call void @b()102; CHECK-NEXT: br label %loop_latch103;104; CHECK: loop_latch:105; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr106; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split107;108; CHECK: loop_exit.split:109; CHECK-NEXT: br label %loop_exit110 111loop_latch:112 %v = load i1, ptr %ptr113 br i1 %v, label %loop_begin, label %loop_exit114 115loop_exit:116 ret void117; CHECK: loop_exit:118; CHECK-NEXT: ret void119}120 121; Check that even with large amounts of code on either side of the unswitched122; branch, if that code would be kept in only one of the unswitched clones it123; doesn't contribute to the cost.124define void @test_unswitch_non_dup_code(ptr %ptr, i1 %cond) {125; CHECK-LABEL: @test_unswitch_non_dup_code(126entry:127 br label %loop_begin128; CHECK-NEXT: entry:129; CHECK-NEXT: [[FROZEN:%.+]] = freeze i1 %cond130; CHECK-NEXT: br i1 [[FROZEN]], label %entry.split.us, label %entry.split131 132loop_begin:133 call void @x()134 br i1 %cond, label %loop_a, label %loop_b135 136loop_a:137 call void @a()138 call void @a()139 call void @a()140 call void @a()141 br label %loop_latch142; The 'loop_a' unswitched loop.143;144; CHECK: entry.split.us:145; CHECK-NEXT: br label %loop_begin.us146;147; CHECK: loop_begin.us:148; CHECK-NEXT: call void @x()149; CHECK-NEXT: br label %loop_a.us150;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.us157;158; CHECK: loop_latch.us:159; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr160; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us161;162; CHECK: loop_exit.split.us:163; CHECK-NEXT: br label %loop_exit164 165loop_b:166 call void @b()167 call void @b()168 call void @b()169 call void @b()170 br label %loop_latch171; The 'loop_b' unswitched loop.172;173; CHECK: entry.split:174; CHECK-NEXT: br label %loop_begin175;176; CHECK: loop_begin:177; CHECK-NEXT: call void @x()178; CHECK-NEXT: br label %loop_b179;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_latch186;187; CHECK: loop_latch:188; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr189; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split190;191; CHECK: loop_exit.split:192; CHECK-NEXT: br label %loop_exit193 194loop_latch:195 %v = load i1, ptr %ptr196 br i1 %v, label %loop_begin, label %loop_exit197 198loop_exit:199 ret void200; CHECK: loop_exit:201; CHECK-NEXT: ret void202}203 204; Much like with non-duplicated code directly in the successor, we also won't205; duplicate even interesting CFGs.206define void @test_unswitch_non_dup_code_in_cfg(ptr %ptr, i1 %cond) {207; CHECK-LABEL: @test_unswitch_non_dup_code_in_cfg(208entry:209 br label %loop_begin210; CHECK-NEXT: entry:211; CHECK-NEXT: [[FROZEN:%.+]] = freeze i1 %cond212; CHECK-NEXT: br i1 [[FROZEN]], label %entry.split.us, label %entry.split213 214loop_begin:215 call void @x()216 br i1 %cond, label %loop_a, label %loop_b217 218loop_a:219 %v1 = load i1, ptr %ptr220 br i1 %v1, label %loop_a_a, label %loop_a_b221 222loop_a_a:223 call void @a()224 br label %loop_latch225 226loop_a_b:227 call void @a()228 br label %loop_latch229; The 'loop_a' unswitched loop.230;231; CHECK: entry.split.us:232; CHECK-NEXT: br label %loop_begin.us233;234; CHECK: loop_begin.us:235; CHECK-NEXT: call void @x()236; CHECK-NEXT: br label %loop_a.us237;238; CHECK: loop_a.us:239; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr240; CHECK-NEXT: br i1 %[[V]], label %loop_a_a.us, label %loop_a_b.us241;242; CHECK: loop_a_b.us:243; CHECK-NEXT: call void @a()244; CHECK-NEXT: br label %loop_latch.us245;246; CHECK: loop_a_a.us:247; CHECK-NEXT: call void @a()248; CHECK-NEXT: br label %loop_latch.us249;250; CHECK: loop_latch.us:251; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr252; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us253;254; CHECK: loop_exit.split.us:255; CHECK-NEXT: br label %loop_exit256 257loop_b:258 %v2 = load i1, ptr %ptr259 br i1 %v2, label %loop_b_a, label %loop_b_b260 261loop_b_a:262 call void @b()263 br label %loop_latch264 265loop_b_b:266 call void @b()267 br label %loop_latch268; The 'loop_b' unswitched loop.269;270; CHECK: entry.split:271; CHECK-NEXT: br label %loop_begin272;273; CHECK: loop_begin:274; CHECK-NEXT: call void @x()275; CHECK-NEXT: br label %loop_b276;277; CHECK: loop_b:278; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr279; CHECK-NEXT: br i1 %[[V]], label %loop_b_a, label %loop_b_b280;281; CHECK: loop_b_a:282; CHECK-NEXT: call void @b()283; CHECK-NEXT: br label %loop_latch284;285; CHECK: loop_b_b:286; CHECK-NEXT: call void @b()287; CHECK-NEXT: br label %loop_latch288;289; CHECK: loop_latch:290; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr291; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split292;293; CHECK: loop_exit.split:294; CHECK-NEXT: br label %loop_exit295 296loop_latch:297 %v3 = load i1, ptr %ptr298 br i1 %v3, label %loop_begin, label %loop_exit299 300loop_exit:301 ret void302; CHECK: loop_exit:303; CHECK-NEXT: ret void304}305 306; Check that even if there is *some* non-duplicated code on one side of an307; unswitch, we don't count any other code in the loop that will in fact have to308; be duplicated.309define void @test_no_unswitch_non_dup_code(ptr %ptr, i1 %cond) {310; CHECK-LABEL: @test_no_unswitch_non_dup_code(311entry:312 br label %loop_begin313; CHECK-NEXT: entry:314; CHECK-NEXT: br label %loop_begin315;316; We shouldn't have unswitched into any other block either.317; CHECK-NOT: br i1 %cond318 319loop_begin:320 call void @x()321 br i1 %cond, label %loop_a, label %loop_b322; CHECK: loop_begin:323; CHECK-NEXT: call void @x()324; CHECK-NEXT: br i1 %cond, label %loop_a, label %loop_b325 326loop_a:327 %v1 = load i1, ptr %ptr328 br i1 %v1, label %loop_a_a, label %loop_a_b329 330loop_a_a:331 call void @a()332 br label %loop_latch333 334loop_a_b:335 call void @a()336 br label %loop_latch337 338loop_b:339 %v2 = load i1, ptr %ptr340 br i1 %v2, label %loop_b_a, label %loop_b_b341 342loop_b_a:343 call void @b()344 br label %loop_latch345 346loop_b_b:347 call void @b()348 br label %loop_latch349 350loop_latch:351 call void @x()352 call void @x()353 %v = load i1, ptr %ptr354 br i1 %v, label %loop_begin, label %loop_exit355 356loop_exit:357 ret void358}359 360; Check that we still unswitch when the exit block contains lots of code, even361; though we do clone the exit block as part of unswitching. This should work362; because we should split the exit block before anything inside it.363define void @test_unswitch_large_exit(ptr %ptr, i1 %cond) {364; CHECK-LABEL: @test_unswitch_large_exit(365entry:366 br label %loop_begin367; CHECK-NEXT: entry:368; CHECK-NEXT: [[FROZEN:%.+]] = freeze i1 %cond369; CHECK-NEXT: br i1 [[FROZEN]], label %entry.split.us, label %entry.split370 371loop_begin:372 call void @x()373 br i1 %cond, label %loop_a, label %loop_b374 375loop_a:376 call void @a()377 br label %loop_latch378; The 'loop_a' unswitched loop.379;380; CHECK: entry.split.us:381; CHECK-NEXT: br label %loop_begin.us382;383; CHECK: loop_begin.us:384; CHECK-NEXT: call void @x()385; CHECK-NEXT: br label %loop_a.us386;387; CHECK: loop_a.us:388; CHECK-NEXT: call void @a()389; CHECK-NEXT: br label %loop_latch.us390;391; CHECK: loop_latch.us:392; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr393; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us394;395; CHECK: loop_exit.split.us:396; CHECK-NEXT: br label %loop_exit397 398loop_b:399 call void @b()400 br label %loop_latch401; The 'loop_b' unswitched loop.402;403; CHECK: entry.split:404; CHECK-NEXT: br label %loop_begin405;406; CHECK: loop_begin:407; CHECK-NEXT: call void @x()408; CHECK-NEXT: br label %loop_b409;410; CHECK: loop_b:411; CHECK-NEXT: call void @b()412; CHECK-NEXT: br label %loop_latch413;414; CHECK: loop_latch:415; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr416; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split417;418; CHECK: loop_exit.split:419; CHECK-NEXT: br label %loop_exit420 421loop_latch:422 %v = load i1, ptr %ptr423 br i1 %v, label %loop_begin, label %loop_exit424 425loop_exit:426 call void @x()427 call void @x()428 call void @x()429 call void @x()430 ret void431; CHECK: loop_exit:432; CHECK-NEXT: call void @x()433; CHECK-NEXT: call void @x()434; CHECK-NEXT: call void @x()435; CHECK-NEXT: call void @x()436; CHECK-NEXT: ret void437}438 439; Check that we handle a dedicated exit edge unswitch which is still440; non-trivial and has lots of code in the exit.441define void @test_unswitch_dedicated_exiting(ptr %ptr, i1 %cond) {442; CHECK-LABEL: @test_unswitch_dedicated_exiting(443entry:444 br label %loop_begin445; CHECK-NEXT: entry:446; CHECK-NEXT: [[FROZEN:%.+]] = freeze i1 %cond447; CHECK-NEXT: br i1 [[FROZEN]], label %entry.split.us, label %entry.split448 449loop_begin:450 call void @x()451 br i1 %cond, label %loop_a, label %loop_b_exit452 453loop_a:454 call void @a()455 br label %loop_latch456; The 'loop_a' unswitched loop.457;458; CHECK: entry.split.us:459; CHECK-NEXT: br label %loop_begin.us460;461; CHECK: loop_begin.us:462; CHECK-NEXT: call void @x()463; CHECK-NEXT: br label %loop_a.us464;465; CHECK: loop_a.us:466; CHECK-NEXT: call void @a()467; CHECK-NEXT: br label %loop_latch.us468;469; CHECK: loop_latch.us:470; CHECK-NEXT: %[[V:.*]] = load i1, ptr %ptr471; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us472;473; CHECK: loop_exit.split.us:474; CHECK-NEXT: br label %loop_exit475 476loop_b_exit:477 call void @b()478 call void @b()479 call void @b()480 call void @b()481 ret void482; The 'loop_b_exit' unswitched exit path.483;484; CHECK: entry.split:485; CHECK-NEXT: br label %loop_begin486;487; CHECK: loop_begin:488; CHECK-NEXT: call void @x()489; CHECK-NEXT: br label %loop_b_exit490;491; CHECK: loop_b_exit:492; CHECK-NEXT: call void @b()493; CHECK-NEXT: call void @b()494; CHECK-NEXT: call void @b()495; CHECK-NEXT: call void @b()496; CHECK-NEXT: ret void497 498loop_latch:499 %v = load i1, ptr %ptr500 br i1 %v, label %loop_begin, label %loop_exit501 502loop_exit:503 ret void504; CHECK: loop_exit:505; CHECK-NEXT: ret void506}507