1; RUN: opt -passes='print<scalar-evolution>,loop(unswitch<nontrivial>,loop-instsimplify),print<scalar-evolution>' -S < %s 2>%t.scev | FileCheck %s 2; RUN: opt -verify-memoryssa -passes='print<scalar-evolution>,loop-mssa(unswitch<nontrivial>,loop-instsimplify),print<scalar-evolution>' -S < %s 2>%t.scev | FileCheck %s 3; RUN: FileCheck %s --check-prefix=SCEV < %t.scev 4 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 outer 10; 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: @test1 14; 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 clean 18; backedge-taken counts. 19; SCEV-LABEL: Determining loop execution counts for: @test1 20; 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_begin 27; Ensure the outer loop didn't get unswitched. 28; CHECK: entry: 29; CHECK-NEXT: br label %outer_loop_begin 30 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() noduplicate 35 br label %inner_loop_begin 36; Ensure the inner loop got unswitched into the outer loop. 37; CHECK: outer_loop_begin: 38; CHECK-NEXT: %{{.*}} = phi i32 39; 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_exit 45 46inner_loop_latch: 47 %j.next = add nsw i32 %j, 1 48 %j.cmp = icmp slt i32 %j.next, %m 49 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit 50 51inner_loop_early_exit: 52 %j.lcssa = phi i32 [ %i, %inner_loop_begin ] 53 br label %outer_loop_latch 54 55inner_loop_late_exit: 56 br label %outer_loop_latch 57 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, 1 61 %i.cmp = icmp slt i32 %i.next, %n 62 br i1 %i.cmp, label %outer_loop_begin, label %exit 63 64exit: 65 ret void 66} 67 68; Check that trivially unswitching an inner loop resets both the inner and outer 69; 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: @test2 73; 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 clean 77; backedge-taken counts. 78; SCEV-LABEL: Determining loop execution counts for: @test2 79; 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_begin 85; Ensure the outer loop didn't get unswitched. 86; CHECK: entry: 87; CHECK-NEXT: br label %outer_loop_begin 88 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() noduplicate 93 br label %inner_loop_begin 94; Ensure the inner loop got unswitched into the outer loop. 95; CHECK: outer_loop_begin: 96; CHECK-NEXT: %{{.*}} = phi i32 97; 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_latch 104 i32 2, label %inner_loop_latch 105 ] 106 107inner_loop_latch: 108 %j.next = add nsw i32 %j, 1 109 %j.cmp = icmp slt i32 %j.next, %m 110 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit 111 112inner_loop_early_exit: 113 %j.lcssa = phi i32 [ %i, %inner_loop_begin ] 114 br label %outer_loop_latch 115 116inner_loop_late_exit: 117 br label %outer_loop_latch 118 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, 1 122 %i.cmp = icmp slt i32 %i.next, %n 123 br i1 %i.cmp, label %outer_loop_begin, label %exit 124 125exit: 126 ret void 127} 128 129; Check that non-trivial unswitching of a branch in an inner loop into the outer 130; 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: @test3 134; 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 clean 138; backedge-taken counts. 139; SCEV-LABEL: Determining loop execution counts for: @test3 140; 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_begin 147; Ensure the outer loop didn't get unswitched. 148; CHECK: entry: 149; CHECK-NEXT: br label %outer_loop_begin 150 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() noduplicate 155 br label %inner_loop_begin 156; Ensure the inner loop got unswitched into the outer loop. 157; CHECK: outer_loop_begin: 158; CHECK-NEXT: %{{.*}} = phi i32 159; 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, 1 165 br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit 166 167inner_loop_latch: 168 %j.next = add nsw i32 %j, 1 169 %j.cmp = icmp slt i32 %j.next, %m 170 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit 171 172inner_loop_early_exit: 173 %j.lcssa = phi i32 [ %j.tmp, %inner_loop_begin ] 174 br label %outer_loop_latch 175 176inner_loop_late_exit: 177 br label %outer_loop_latch 178 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.phi 182 %i.cmp = icmp slt i32 %i.next, %n 183 br i1 %i.cmp, label %outer_loop_begin, label %exit 184 185exit: 186 ret void 187} 188