test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll

   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: [0,-1) 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: [0,-3) 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: [0,-1) 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))<nuw><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 }