188 lines · plain
1; RUN: opt -passes='print<scalar-evolution>,loop(simple-loop-unswitch<nontrivial>,loop-instsimplify),print<scalar-evolution>' -S < %s 2>%t.scev | FileCheck %s2; RUN: opt -verify-memoryssa -passes='print<scalar-evolution>,loop-mssa(simple-loop-unswitch<nontrivial>,loop-instsimplify),print<scalar-evolution>' -S < %s 2>%t.scev | FileCheck %s3; RUN: FileCheck %s --check-prefix=SCEV < %t.scev4 5target triple = "x86_64-unknown-linux-gnu"6 7declare void @f()8 9; Check that trivially unswitching an inner loop resets both the inner and outer10; loop trip count.11define void @test1(i32 %n, i32 %m, i1 %cond) {12; Check that SCEV has no trip count before unswitching.13; SCEV-LABEL: Determining loop execution counts for: @test114; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.15; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.16;17; Now check that after unswitching and simplifying instructions we get clean18; backedge-taken counts.19; SCEV-LABEL: Determining loop execution counts for: @test120; SCEV: Loop %inner_loop_begin: backedge-taken count is (-1 + (1 smax %m))<nsw>21; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw>22;23; And verify the code matches what we expect.24; CHECK-LABEL: define void @test1(25entry:26 br label %outer_loop_begin27; Ensure the outer loop didn't get unswitched.28; CHECK: entry:29; CHECK-NEXT: br label %outer_loop_begin30 31outer_loop_begin:32 %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]33 ; Block unswitching of the outer loop with a noduplicate call.34 call void @f() noduplicate35 br label %inner_loop_begin36; Ensure the inner loop got unswitched into the outer loop.37; CHECK: outer_loop_begin:38; CHECK-NEXT: %{{.*}} = phi i3239; CHECK-NEXT: call void @f()40; CHECK-NEXT: br i1 %cond,41 42inner_loop_begin:43 %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]44 br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit45 46inner_loop_latch:47 %j.next = add nsw i32 %j, 148 %j.cmp = icmp slt i32 %j.next, %m49 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit50 51inner_loop_early_exit:52 %j.lcssa = phi i32 [ %i, %inner_loop_begin ]53 br label %outer_loop_latch54 55inner_loop_late_exit:56 br label %outer_loop_latch57 58outer_loop_latch:59 %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ]60 %i.next = add nsw i32 %i.phi, 161 %i.cmp = icmp slt i32 %i.next, %n62 br i1 %i.cmp, label %outer_loop_begin, label %exit63 64exit:65 ret void66}67 68; Check that trivially unswitching an inner loop resets both the inner and outer69; loop trip count.70define void @test2(i32 %n, i32 %m, i32 %cond) {71; Check that SCEV has no trip count before unswitching.72; SCEV-LABEL: Determining loop execution counts for: @test273; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.74; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.75;76; Now check that after unswitching and simplifying instructions we get clean77; backedge-taken counts.78; SCEV-LABEL: Determining loop execution counts for: @test279; SCEV: Loop %inner_loop_begin: backedge-taken count is (-1 + (1 smax %m))<nsw>80; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw>81;82; CHECK-LABEL: define void @test2(83entry:84 br label %outer_loop_begin85; Ensure the outer loop didn't get unswitched.86; CHECK: entry:87; CHECK-NEXT: br label %outer_loop_begin88 89outer_loop_begin:90 %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]91 ; Block unswitching of the outer loop with a noduplicate call.92 call void @f() noduplicate93 br label %inner_loop_begin94; Ensure the inner loop got unswitched into the outer loop.95; CHECK: outer_loop_begin:96; CHECK-NEXT: %{{.*}} = phi i3297; CHECK-NEXT: call void @f()98; CHECK-NEXT: switch i32 %cond,99 100inner_loop_begin:101 %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]102 switch i32 %cond, label %inner_loop_early_exit [103 i32 1, label %inner_loop_latch104 i32 2, label %inner_loop_latch105 ]106 107inner_loop_latch:108 %j.next = add nsw i32 %j, 1109 %j.cmp = icmp slt i32 %j.next, %m110 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit111 112inner_loop_early_exit:113 %j.lcssa = phi i32 [ %i, %inner_loop_begin ]114 br label %outer_loop_latch115 116inner_loop_late_exit:117 br label %outer_loop_latch118 119outer_loop_latch:120 %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ]121 %i.next = add nsw i32 %i.phi, 1122 %i.cmp = icmp slt i32 %i.next, %n123 br i1 %i.cmp, label %outer_loop_begin, label %exit124 125exit:126 ret void127}128 129; Check that non-trivial unswitching of a branch in an inner loop into the outer130; loop invalidates both inner and outer.131define void @test3(i32 %n, i32 %m, i1 %cond) {132; Check that SCEV has no trip count before unswitching.133; SCEV-LABEL: Determining loop execution counts for: @test3134; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.135; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.136;137; Now check that after unswitching and simplifying instructions we get clean138; backedge-taken counts.139; SCEV-LABEL: Determining loop execution counts for: @test3140; SCEV: Loop %inner_loop_begin{{.*}}: backedge-taken count is (-1 + (1 smax %m))<nsw>141; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw>142;143; And verify the code matches what we expect.144; CHECK-LABEL: define void @test3(145entry:146 br label %outer_loop_begin147; Ensure the outer loop didn't get unswitched.148; CHECK: entry:149; CHECK-NEXT: br label %outer_loop_begin150 151outer_loop_begin:152 %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]153 ; Block unswitching of the outer loop with a noduplicate call.154 call void @f() noduplicate155 br label %inner_loop_begin156; Ensure the inner loop got unswitched into the outer loop.157; CHECK: outer_loop_begin:158; CHECK-NEXT: %{{.*}} = phi i32159; CHECK-NEXT: call void @f()160; CHECK-NEXT: br i1 %cond,161 162inner_loop_begin:163 %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]164 %j.tmp = add nsw i32 %j, 1165 br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit166 167inner_loop_latch:168 %j.next = add nsw i32 %j, 1169 %j.cmp = icmp slt i32 %j.next, %m170 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit171 172inner_loop_early_exit:173 %j.lcssa = phi i32 [ %j.tmp, %inner_loop_begin ]174 br label %outer_loop_latch175 176inner_loop_late_exit:177 br label %outer_loop_latch178 179outer_loop_latch:180 %inc.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ 1, %inner_loop_late_exit ]181 %i.next = add nsw i32 %i, %inc.phi182 %i.cmp = icmp slt i32 %i.next, %n183 br i1 %i.cmp, label %outer_loop_begin, label %exit184 185exit:186 ret void187}188