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 4 target triple = "x86_64-unknown-linux-gnu" 5 6 declare void @f() 7 8 ; Check that trivially unswitching an inner loop resets both the inner and outer 9 ; loop trip count. 10 define 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( 24 entry: 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 30 outer_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 41 inner_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 45 inner_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 50 inner_loop_early_exit: 51 %j.lcssa = phi i32 [ %i, %inner_loop_begin ] 52 br label %outer_loop_latch 53 54 inner_loop_late_exit: 55 br label %outer_loop_latch 56 57 outer_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 63 exit: 64 ret void 65 } 66 67 ; Check that trivially unswitching an inner loop resets both the inner and outer 68 ; loop trip count. 69 define 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( 82 entry: 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 88 outer_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 99 inner_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 106 inner_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 111 inner_loop_early_exit: 112 %j.lcssa = phi i32 [ %i, %inner_loop_begin ] 113 br label %outer_loop_latch 114 115 inner_loop_late_exit: 116 br label %outer_loop_latch 117 118 outer_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 124 exit: 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. 130 define 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( 144 entry: 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 150 outer_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 161 inner_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 166 inner_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 171 inner_loop_early_exit: 172 %j.lcssa = phi i32 [ %j.tmp, %inner_loop_begin ] 173 br label %outer_loop_latch 174 175 inner_loop_late_exit: 176 br label %outer_loop_latch 177 178 outer_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 184 exit: 185 ret void 186 } 187
