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; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw> 80; 81; CHECK-LABEL: define void @test2( 82entry: 83 br label %outer_loop_begin 84; Ensure the outer loop didn't get unswitched. 85; CHECK: entry: 86; CHECK-NEXT: br label %outer_loop_begin 87 88outer_loop_begin: 89 %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ] 90 ; Block unswitching of the outer loop with a noduplicate call. 91 call void @f() noduplicate 92 br label %inner_loop_begin 93; Ensure the inner loop got unswitched into the outer loop. 94; CHECK: outer_loop_begin: 95; CHECK-NEXT: %{{.*}} = phi i32 96; CHECK-NEXT: call void @f() 97; CHECK-NEXT: switch i32 %cond, 98 99inner_loop_begin: 100 %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ] 101 switch i32 %cond, label %inner_loop_early_exit [ 102 i32 1, label %inner_loop_latch 103 i32 2, label %inner_loop_latch 104 ] 105 106inner_loop_latch: 107 %j.next = add nsw i32 %j, 1 108 %j.cmp = icmp slt i32 %j.next, %m 109 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit 110 111inner_loop_early_exit: 112 %j.lcssa = phi i32 [ %i, %inner_loop_begin ] 113 br label %outer_loop_latch 114 115inner_loop_late_exit: 116 br label %outer_loop_latch 117 118outer_loop_latch: 119 %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ] 120 %i.next = add nsw i32 %i.phi, 1 121 %i.cmp = icmp slt i32 %i.next, %n 122 br i1 %i.cmp, label %outer_loop_begin, label %exit 123 124exit: 125 ret void 126} 127 128; Check that non-trivial unswitching of a branch in an inner loop into the outer 129; loop invalidates both inner and outer. 130define void @test3(i32 %n, i32 %m, i1 %cond) { 131; Check that SCEV has no trip count before unswitching. 132; SCEV-LABEL: Determining loop execution counts for: @test3 133; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count. 134; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count. 135; 136; Now check that after unswitching and simplifying instructions we get clean 137; backedge-taken counts. 138; SCEV-LABEL: Determining loop execution counts for: @test3 139; SCEV: Loop %inner_loop_begin{{.*}}: backedge-taken count is (-1 + (1 smax %m))<nsw> 140; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw> 141; 142; And verify the code matches what we expect. 143; CHECK-LABEL: define void @test3( 144entry: 145 br label %outer_loop_begin 146; Ensure the outer loop didn't get unswitched. 147; CHECK: entry: 148; CHECK-NEXT: br label %outer_loop_begin 149 150outer_loop_begin: 151 %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ] 152 ; Block unswitching of the outer loop with a noduplicate call. 153 call void @f() noduplicate 154 br label %inner_loop_begin 155; Ensure the inner loop got unswitched into the outer loop. 156; CHECK: outer_loop_begin: 157; CHECK-NEXT: %{{.*}} = phi i32 158; CHECK-NEXT: call void @f() 159; CHECK-NEXT: br i1 %cond, 160 161inner_loop_begin: 162 %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ] 163 %j.tmp = add nsw i32 %j, 1 164 br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit 165 166inner_loop_latch: 167 %j.next = add nsw i32 %j, 1 168 %j.cmp = icmp slt i32 %j.next, %m 169 br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit 170 171inner_loop_early_exit: 172 %j.lcssa = phi i32 [ %j.tmp, %inner_loop_begin ] 173 br label %outer_loop_latch 174 175inner_loop_late_exit: 176 br label %outer_loop_latch 177 178outer_loop_latch: 179 %inc.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ 1, %inner_loop_late_exit ] 180 %i.next = add nsw i32 %i, %inc.phi 181 %i.cmp = icmp slt i32 %i.next, %n 182 br i1 %i.cmp, label %outer_loop_begin, label %exit 183 184exit: 185 ret void 186} 187