1 ; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s 2 3 define void @f0(i1 %c) { 4 ; CHECK-LABEL: Classifying expressions for: @f0 5 entry: 6 %start = select i1 %c, i32 127, i32 0 7 %step = select i1 %c, i32 -1, i32 1 8 br label %loop 9 10 loop: 11 %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ] 12 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 13 ; CHECK: %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 14 ; CHECK-NEXT: --> {%start,+,%step}<%loop> U: [0,128) S: [0,128) 15 %iv.next = add i32 %iv, %step 16 %loop.iv.inc = add i32 %loop.iv, 1 17 %be.cond = icmp ne i32 %loop.iv.inc, 128 18 br i1 %be.cond, label %loop, label %leave 19 20 leave: 21 ret void 22 } 23 24 define void @f1(i1 %c) { 25 ; CHECK-LABEL: Classifying expressions for: @f1 26 entry: 27 %start = select i1 %c, i32 120, i32 0 28 %step = select i1 %c, i32 -8, i32 8 29 br label %loop 30 31 loop: 32 %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ] 33 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 34 35 ; CHECK: %iv.1 = add i32 %iv, 1 36 ; CHECK-NEXT: --> {(1 + %start)<nuw><nsw>,+,%step}<%loop> U: [1,122) S: [1,122) 37 ; CHECK: %iv.2 = add i32 %iv, 2 38 ; CHECK-NEXT: --> {(2 + %start)<nuw><nsw>,+,%step}<%loop> U: [2,123) S: [2,123) 39 ; CHECK: %iv.3 = add i32 %iv, 3 40 ; CHECK-NEXT: --> {(3 + %start)<nuw><nsw>,+,%step}<%loop> U: [3,124) S: [3,124) 41 ; CHECK: %iv.4 = add i32 %iv, 4 42 ; CHECK-NEXT: --> {(4 + %start)<nuw><nsw>,+,%step}<%loop> U: [4,125) S: [4,125) 43 ; CHECK: %iv.5 = add i32 %iv, 5 44 ; CHECK-NEXT: --> {(5 + %start)<nuw><nsw>,+,%step}<%loop> U: [5,126) S: [5,126) 45 ; CHECK: %iv.6 = add i32 %iv, 6 46 ; CHECK-NEXT: --> {(6 + %start)<nuw><nsw>,+,%step}<%loop> U: [6,127) S: [6,127) 47 ; CHECK: %iv.7 = add i32 %iv, 7 48 ; CHECK-NEXT: --> {(7 + %start)<nuw><nsw>,+,%step}<%loop> U: [7,128) S: [7,128) 49 50 %iv.1 = add i32 %iv, 1 51 %iv.2 = add i32 %iv, 2 52 %iv.3 = add i32 %iv, 3 53 %iv.4 = add i32 %iv, 4 54 %iv.5 = add i32 %iv, 5 55 %iv.6 = add i32 %iv, 6 56 %iv.7 = add i32 %iv, 7 57 58 ; CHECK: %iv.m1 = sub i32 %iv, 1 59 ; CHECK-NEXT: --> {(-1 + %start)<nsw>,+,%step}<%loop> U: [-1,120) S: [-1,120) 60 ; CHECK: %iv.m2 = sub i32 %iv, 2 61 ; CHECK-NEXT: --> {(-2 + %start)<nsw>,+,%step}<%loop> U: [-2,119) S: [-2,119) 62 ; CHECK: %iv.m3 = sub i32 %iv, 3 63 ; CHECK-NEXT: --> {(-3 + %start)<nsw>,+,%step}<%loop> U: [-3,118) S: [-3,118) 64 ; CHECK: %iv.m4 = sub i32 %iv, 4 65 ; CHECK-NEXT: --> {(-4 + %start)<nsw>,+,%step}<%loop> U: [-4,117) S: [-4,117) 66 ; CHECK: %iv.m5 = sub i32 %iv, 5 67 ; CHECK-NEXT: --> {(-5 + %start)<nsw>,+,%step}<%loop> U: [-5,116) S: [-5,116) 68 ; CHECK: %iv.m6 = sub i32 %iv, 6 69 ; CHECK-NEXT: --> {(-6 + %start)<nsw>,+,%step}<%loop> U: [-6,115) S: [-6,115) 70 ; CHECK: %iv.m7 = sub i32 %iv, 7 71 ; CHECK-NEXT: --> {(-7 + %start)<nsw>,+,%step}<%loop> U: [-7,114) S: [-7,114) 72 73 %iv.m1 = sub i32 %iv, 1 74 %iv.m2 = sub i32 %iv, 2 75 %iv.m3 = sub i32 %iv, 3 76 %iv.m4 = sub i32 %iv, 4 77 %iv.m5 = sub i32 %iv, 5 78 %iv.m6 = sub i32 %iv, 6 79 %iv.m7 = sub i32 %iv, 7 80 81 %iv.next = add i32 %iv, %step 82 %loop.iv.inc = add i32 %loop.iv, 1 83 %be.cond = icmp sgt i32 %loop.iv, 14 84 br i1 %be.cond, label %leave, label %loop 85 86 leave: 87 ret void 88 } 89 90 define void @f2(i1 %c) { 91 ; CHECK-LABEL: Classifying expressions for: @f2 92 entry: 93 %start = select i1 %c, i32 127, i32 0 94 %step = select i1 %c, i32 -1, i32 1 95 br label %loop 96 97 loop: 98 %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ] 99 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 100 %iv.sext = sext i32 %iv to i64 101 %iv.next = add i32 %iv, %step 102 ; CHECK: %iv.sext = sext i32 %iv to i64 103 ; CHECK-NEXT: --> {(sext i32 %start to i64),+,(sext i32 %step to i64)}<nsw><%loop> U: [0,128) S: [0,128) 104 %loop.iv.inc = add i32 %loop.iv, 1 105 %be.cond = icmp ne i32 %loop.iv.inc, 128 106 br i1 %be.cond, label %loop, label %leave 107 108 leave: 109 ret void 110 } 111 112 define void @f3(i1 %c) { 113 ; CHECK-LABEL: Classifying expressions for: @f3 114 entry: 115 116 ; NB! the i16 type (as opposed to i32), the choice of the constant 509 117 ; and the trip count are all related and not arbitrary. We want an 118 ; add recurrence that will look like it can unsign-overflow *unless* 119 ; SCEV is able to see the correlation between the two selects feeding 120 ; into the initial value and the step increment. 121 122 %start = select i1 %c, i16 1000, i16 0 123 %step = select i1 %c, i16 1, i16 509 124 br label %loop 125 126 loop: 127 %loop.iv = phi i16 [ 0, %entry ], [ %loop.iv.inc, %loop ] 128 %iv = phi i16 [ %start, %entry ], [ %iv.next, %loop ] 129 %iv.zext = zext i16 %iv to i64 130 ; CHECK: %iv.zext = zext i16 %iv to i64 131 ; CHECK-NEXT: --> {(zext i16 %start to i64),+,(zext i16 %step to i64)}<nuw><%loop> U: [0,64644) S: [0,64644) 132 %iv.next = add i16 %iv, %step 133 %loop.iv.inc = add i16 %loop.iv, 1 134 %be.cond = icmp ne i16 %loop.iv.inc, 128 135 br i1 %be.cond, label %loop, label %leave 136 137 leave: 138 ret void 139 } 140 141 define void @f4(i1 %c) { 142 ; CHECK-LABEL: Classifying expressions for: @f4 143 144 ; @f4() demonstrates a case where SCEV is not able to compute a 145 ; precise range for %iv.trunc, though it should be able to, in theory. 146 ; This is because SCEV looks into affine add recurrences only when the 147 ; backedge taken count of the loop has the same bitwidth as the 148 ; induction variable. 149 entry: 150 %start = select i1 %c, i32 127, i32 0 151 %step = select i1 %c, i32 -1, i32 1 152 br label %loop 153 154 loop: 155 %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ] 156 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 157 %iv.trunc = trunc i32 %iv to i16 158 ; CHECK: %iv.trunc = trunc i32 %iv to i16 159 ; CHECK-NEXT: --> {(trunc i32 %start to i16),+,(trunc i32 %step to i16)}<%loop> U: full-set S: full-set 160 %iv.next = add i32 %iv, %step 161 %loop.iv.inc = add i32 %loop.iv, 1 162 %be.cond = icmp ne i32 %loop.iv.inc, 128 163 br i1 %be.cond, label %loop, label %leave 164 165 leave: 166 ret void 167 } 168 169 define void @f5(i1 %c) { 170 ; CHECK-LABEL: Classifying expressions for: @f5 171 entry: 172 %start = select i1 %c, i32 127, i32 0 173 %step = select i1 %c, i32 -1, i32 1 174 br label %loop 175 176 loop: 177 %loop.iv = phi i16 [ 0, %entry ], [ %loop.iv.inc, %loop ] 178 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 179 %iv.trunc = trunc i32 %iv to i16 180 ; CHECK: %iv.trunc = trunc i32 %iv to i16 181 ; CHECK-NEXT: --> {(trunc i32 %start to i16),+,(trunc i32 %step to i16)}<%loop> U: [0,128) S: [0,128) 182 %iv.next = add i32 %iv, %step 183 184 %loop.iv.inc = add i16 %loop.iv, 1 185 %be.cond = icmp ne i16 %loop.iv.inc, 128 186 br i1 %be.cond, label %loop, label %leave 187 188 leave: 189 ret void 190 } 191 192 define void @f6(i1 %c) { 193 ; CHECK-LABEL: Classifying expressions for: @f6 194 entry: 195 %start = select i1 %c, i32 127, i32 0 196 %step = select i1 %c, i32 -2, i32 0 197 br label %loop 198 199 loop: 200 %loop.iv = phi i16 [ 0, %entry ], [ %loop.iv.inc, %loop ] 201 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 202 ; CHECK: %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 203 ; CHECK-NEXT: --> {%start,+,(1 + %step)<nuw><nsw>}<%loop> U: [0,128) S: [0,128) 204 205 %step.plus.one = add i32 %step, 1 206 %iv.next = add i32 %iv, %step.plus.one 207 %iv.sext = sext i32 %iv to i64 208 ; CHECK: %iv.sext = sext i32 %iv to i64 209 ; CHECK-NEXT: --> {(sext i32 %start to i64),+,(1 + (sext i32 %step to i64))<nsw>}<nsw><%loop> U: [0,128) S: [0,128) 210 %loop.iv.inc = add i16 %loop.iv, 1 211 %be.cond = icmp ne i16 %loop.iv.inc, 128 212 br i1 %be.cond, label %loop, label %leave 213 214 leave: 215 ret void 216 } 217 218 define void @f7(i1 %c) { 219 ; CHECK-LABEL: Classifying expressions for: @f7 220 entry: 221 %start = select i1 %c, i32 127, i32 0 222 %step = select i1 %c, i32 -1, i32 1 223 br label %loop 224 225 loop: 226 %loop.iv = phi i16 [ 0, %entry ], [ %loop.iv.inc, %loop ] 227 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 228 %iv.trunc = trunc i32 %iv to i16 229 ; CHECK: %iv.trunc = trunc i32 %iv to i16 230 ; CHECK-NEXT: --> {(trunc i32 %start to i16),+,(trunc i32 %step to i16)}<%loop> U: [0,128) S: [0,128) 231 %iv.next = add i32 %iv, %step 232 233 %iv.trunc.plus.one = add i16 %iv.trunc, 1 234 ; CHECK: %iv.trunc.plus.one = add i16 %iv.trunc, 1 235 ; CHECK-NEXT: --> {(1 + (trunc i32 %start to i16))<nuw><nsw>,+,(trunc i32 %step to i16)}<%loop> U: [1,129) S: [1,129) 236 237 %iv.trunc.plus.two = add i16 %iv.trunc, 2 238 ; CHECK: %iv.trunc.plus.two = add i16 %iv.trunc, 2 239 ; CHECK-NEXT: --> {(2 + (trunc i32 %start to i16))<nuw><nsw>,+,(trunc i32 %step to i16)}<%loop> U: [2,130) S: [2,130) 240 241 %loop.iv.inc = add i16 %loop.iv, 1 242 %be.cond = icmp ne i16 %loop.iv.inc, 128 243 br i1 %be.cond, label %loop, label %leave 244 245 leave: 246 ret void 247 } 248