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