1; RUN: opt -passes='print<scalar-evolution>,loop(unswitch,loop-instsimplify),print<scalar-evolution>' -enable-nontrivial-unswitch -S < %s 2>%t.scev | FileCheck %s 2; RUN: FileCheck %s --check-prefix=SCEV < %t.scev 3 4target triple = "x86_64-unknown-linux-gnu" 5 6declare void @f() 7 8; Check that trivially unswitching an inner loop resets both the inner and outer 9; loop trip count. 10define void @test1(i32 %n, i32 %m, i1 %cond) { 11; Check that SCEV has no trip count before unswitching. 12; SCEV-LABEL: Determining loop execution counts for: @test1 13; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count. 14; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count. 15; 16; Now check that after unswitching and simplifying instructions we get clean 17; backedge-taken counts. 18; SCEV-LABEL: Determining loop execution counts for: @test1 19; SCEV: Loop %inner_loop_begin: backedge-taken count is (-1 + (1 smax %m))<nsw> 20; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw> 21; 22; And verify the code matches what we expect. 23; CHECK-LABEL: define void @test1( 24entry: 25 br label %outer_loop_begin 26; Ensure the outer loop didn't get unswitched. 27; CHECK: entry: 28; CHECK-NEXT: br label %outer_loop_begin 29 30outer_loop_begin: 31 %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ] 32 ; Block unswitching of the outer loop with a noduplicate call. 33 call void @f() noduplicate 34 br label %inner_loop_begin 35; Ensure the inner loop got unswitched into the outer loop. 36; CHECK: outer_loop_begin: 37; CHECK-NEXT: %{{.*}} = phi i32 38; CHECK-NEXT: call void @f() 39; CHECK-NEXT: br i1 %cond, 40 41inner_loop_begin: 42 %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ] 43 br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit 44 45inner_loop_latch: 46 %j.next = add nsw i32 %j, 1 47 %j.cmp = icmp slt i32 %j.next, %m 48 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit 49 50inner_loop_early_exit: 51 %j.lcssa = phi i32 [ %i, %inner_loop_begin ] 52 br label %outer_loop_latch 53 54inner_loop_late_exit: 55 br label %outer_loop_latch 56 57outer_loop_latch: 58 %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ] 59 %i.next = add nsw i32 %i.phi, 1 60 %i.cmp = icmp slt i32 %i.next, %n 61 br i1 %i.cmp, label %outer_loop_begin, label %exit 62 63exit: 64 ret void 65} 66 67; Check that trivially unswitching an inner loop resets both the inner and outer 68; loop trip count. 69define void @test2(i32 %n, i32 %m, i32 %cond) { 70; Check that SCEV has no trip count before unswitching. 71; SCEV-LABEL: Determining loop execution counts for: @test2 72; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count. 73; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count. 74; 75; Now check that after unswitching and simplifying instructions we get clean 76; backedge-taken counts. 77; SCEV-LABEL: Determining loop execution counts for: @test2 78; SCEV: Loop %inner_loop_begin: backedge-taken count is (-1 + (1 smax %m))<nsw> 79; FIXME: The following backedge taken count should be known but isn't apparently 80; just because of a switch in the outer loop. 81; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count. 82; 83; CHECK-LABEL: define void @test2( 84entry: 85 br label %outer_loop_begin 86; Ensure the outer loop didn't get unswitched. 87; CHECK: entry: 88; CHECK-NEXT: br label %outer_loop_begin 89 90outer_loop_begin: 91 %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ] 92 ; Block unswitching of the outer loop with a noduplicate call. 93 call void @f() noduplicate 94 br label %inner_loop_begin 95; Ensure the inner loop got unswitched into the outer loop. 96; CHECK: outer_loop_begin: 97; CHECK-NEXT: %{{.*}} = phi i32 98; CHECK-NEXT: call void @f() 99; CHECK-NEXT: switch i32 %cond, 100 101inner_loop_begin: 102 %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ] 103 switch i32 %cond, label %inner_loop_early_exit [ 104 i32 1, label %inner_loop_latch 105 i32 2, label %inner_loop_latch 106 ] 107 108inner_loop_latch: 109 %j.next = add nsw i32 %j, 1 110 %j.cmp = icmp slt i32 %j.next, %m 111 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit 112 113inner_loop_early_exit: 114 %j.lcssa = phi i32 [ %i, %inner_loop_begin ] 115 br label %outer_loop_latch 116 117inner_loop_late_exit: 118 br label %outer_loop_latch 119 120outer_loop_latch: 121 %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ] 122 %i.next = add nsw i32 %i.phi, 1 123 %i.cmp = icmp slt i32 %i.next, %n 124 br i1 %i.cmp, label %outer_loop_begin, label %exit 125 126exit: 127 ret void 128} 129 130; Check that non-trivial unswitching of a branch in an inner loop into the outer 131; loop invalidates both inner and outer. 132define void @test3(i32 %n, i32 %m, i1 %cond) { 133; Check that SCEV has no trip count before unswitching. 134; SCEV-LABEL: Determining loop execution counts for: @test3 135; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count. 136; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count. 137; 138; Now check that after unswitching and simplifying instructions we get clean 139; backedge-taken counts. 140; SCEV-LABEL: Determining loop execution counts for: @test3 141; SCEV: Loop %inner_loop_begin{{.*}}: backedge-taken count is (-1 + (1 smax %m))<nsw> 142; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw> 143; 144; And verify the code matches what we expect. 145; CHECK-LABEL: define void @test3( 146entry: 147 br label %outer_loop_begin 148; Ensure the outer loop didn't get unswitched. 149; CHECK: entry: 150; CHECK-NEXT: br label %outer_loop_begin 151 152outer_loop_begin: 153 %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ] 154 ; Block unswitching of the outer loop with a noduplicate call. 155 call void @f() noduplicate 156 br label %inner_loop_begin 157; Ensure the inner loop got unswitched into the outer loop. 158; CHECK: outer_loop_begin: 159; CHECK-NEXT: %{{.*}} = phi i32 160; CHECK-NEXT: call void @f() 161; CHECK-NEXT: br i1 %cond, 162 163inner_loop_begin: 164 %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ] 165 %j.tmp = add nsw i32 %j, 1 166 br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit 167 168inner_loop_latch: 169 %j.next = add nsw i32 %j, 1 170 %j.cmp = icmp slt i32 %j.next, %m 171 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit 172 173inner_loop_early_exit: 174 %j.lcssa = phi i32 [ %j.tmp, %inner_loop_begin ] 175 br label %outer_loop_latch 176 177inner_loop_late_exit: 178 br label %outer_loop_latch 179 180outer_loop_latch: 181 %inc.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ 1, %inner_loop_late_exit ] 182 %i.next = add nsw i32 %i, %inc.phi 183 %i.cmp = icmp slt i32 %i.next, %n 184 br i1 %i.cmp, label %outer_loop_begin, label %exit 185 186exit: 187 ret void 188} 189