llvm/test/Analysis/ScalarEvolution/trip-count-unknown-stride.ll

   1 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
   2
   3 ; ScalarEvolution should be able to compute trip count of the loop by proving
   4 ; that this is not an infinite loop with side effects.
   5
   6 ; CHECK-LABEL: Determining loop execution counts for: @foo1
   7 ; CHECK: backedge-taken count is ((-1 + (%n smax %s)) /u %s)
   8
   9 ; We should have a conservative estimate for the max backedge taken count for
  10 ; loops with unknown stride.
  11 ; CHECK: constant max backedge-taken count is -1
  12
  13 target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
  14
  15 define void @foo1(ptr nocapture %A, i32 %n, i32 %s) mustprogress {
  16 entry:
  17   %cmp4 = icmp sgt i32 %n, 0
  18   br i1 %cmp4, label %for.body, label %for.end
  19
  20 for.body:                                         ; preds = %entry, %for.body
  21   %i.05 = phi i32 [ %add, %for.body ], [ 0, %entry ]
  22   %arrayidx = getelementptr inbounds i32, ptr %A, i32 %i.05
  23   %0 = load i32, ptr %arrayidx, align 4
  24   %inc = add nsw i32 %0, 1
  25   store i32 %inc, ptr %arrayidx, align 4
  26   %add = add nsw i32 %i.05, %s
  27   %cmp = icmp slt i32 %add, %n
  28   br i1 %cmp, label %for.body, label %for.end
  29
  30 for.end:                                          ; preds = %for.body, %entry
  31   ret void
  32 }
  33
  34
  35 ; Check that we are able to compute trip count of a loop without an entry guard.
  36 ; CHECK: Determining loop execution counts for: @foo2
  37 ; CHECK: backedge-taken count is ((((-1 * (1 umin ((-1 * %s) + (%n smax %s))))<nuw><nsw> + (-1 * %s) + (%n smax %s)) /u (1 umax %s)) + (1 umin ((-1 * %s) + (%n smax %s))))
  38
  39 ; We should have a conservative estimate for the max backedge taken count for
  40 ; loops with unknown stride.
  41 ; CHECK: constant max backedge-taken count is -1
  42
  43 define void @foo2(ptr nocapture %A, i32 %n, i32 %s) mustprogress {
  44 entry:
  45   br label %for.body
  46
  47 for.body:                                         ; preds = %entry, %for.body
  48   %i.05 = phi i32 [ %add, %for.body ], [ 0, %entry ]
  49   %arrayidx = getelementptr inbounds i32, ptr %A, i32 %i.05
  50   %0 = load i32, ptr %arrayidx, align 4
  51   %inc = add nsw i32 %0, 1
  52   store i32 %inc, ptr %arrayidx, align 4
  53   %add = add nsw i32 %i.05, %s
  54   %cmp = icmp slt i32 %add, %n
  55   br i1 %cmp, label %for.body, label %for.end
  56
  57 for.end:                                          ; preds = %for.body, %entry
  58   ret void
  59 }
  60
  61 ; Check that without mustprogress we don't make assumptions about infinite
  62 ; loops being UB.
  63 ; CHECK-LABEL: Determining loop execution counts for: @foo3
  64 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
  65 ; CHECK: Loop %for.body: Unpredictable constant max backedge-taken count.
  66
  67 define void @foo3(ptr nocapture %A, i32 %n, i32 %s) {
  68 entry:
  69   br label %for.body
  70
  71 for.body:                                         ; preds = %entry, %for.body
  72   %i.05 = phi i32 [ %add, %for.body ], [ 0, %entry ]
  73   %arrayidx = getelementptr inbounds i32, ptr %A, i32 %i.05
  74   %0 = load i32, ptr %arrayidx, align 4
  75   %inc = add nsw i32 %0, 1
  76   store i32 %inc, ptr %arrayidx, align 4
  77   %add = add nsw i32 %i.05, %s
  78   %cmp = icmp slt i32 %add, %n
  79   br i1 %cmp, label %for.body, label %for.end
  80
  81 for.end:                                          ; preds = %for.body, %entry
  82   ret void
  83 }
  84
  85 ; Same as foo2, but with mustprogress on loop, not function
  86 ; CHECK: Determining loop execution counts for: @foo4
  87 ; CHECK: backedge-taken count is ((((-1 * (1 umin ((-1 * %s) + (%n smax %s))))<nuw><nsw> + (-1 * %s) + (%n smax %s)) /u (1 umax %s)) + (1 umin ((-1 * %s) + (%n smax %s))))
  88 ; CHECK: constant max backedge-taken count is -1
  89
  90 define void @foo4(ptr nocapture %A, i32 %n, i32 %s) {
  91 entry:
  92   br label %for.body
  93
  94 for.body:                                         ; preds = %entry, %for.body
  95   %i.05 = phi i32 [ %add, %for.body ], [ 0, %entry ]
  96   %arrayidx = getelementptr inbounds i32, ptr %A, i32 %i.05
  97   %0 = load i32, ptr %arrayidx, align 4
  98   %inc = add nsw i32 %0, 1
  99   store i32 %inc, ptr %arrayidx, align 4
 100   %add = add nsw i32 %i.05, %s
 101   %cmp = icmp slt i32 %add, %n
 102   br i1 %cmp, label %for.body, label %for.end, !llvm.loop !8
 103
 104 for.end:                                          ; preds = %for.body, %entry
 105   ret void
 106 }
 107
 108 ; A more complex case with pre-increment compare instead of post-increment.
 109 ; CHECK-LABEL: Determining loop execution counts for: @foo5
 110 ; CHECK: Loop %for.body: backedge-taken count is ((((-1 * (1 umin ((-1 * %start) + (%n smax %start))))<nuw><nsw> + (-1 * %start) + (%n smax %start)) /u (1 umax %s)) + (1 umin ((-1 * %start) + (%n smax %start))))
 111
 112 ; We should have a conservative estimate for the max backedge taken count for
 113 ; loops with unknown stride.
 114 ; CHECK: constant max backedge-taken count is -1
 115
 116 define void @foo5(ptr nocapture %A, i32 %n, i32 %s, i32 %start) mustprogress {
 117 entry:
 118   br label %for.body
 119
 120 for.body:                                         ; preds = %entry, %for.body
 121   %i.05 = phi i32 [ %add, %for.body ], [ %start, %entry ]
 122   %arrayidx = getelementptr inbounds i32, ptr %A, i32 %i.05
 123   %0 = load i32, ptr %arrayidx, align 4
 124   %inc = add nsw i32 %0, 1
 125   store i32 %inc, ptr %arrayidx, align 4
 126   %add = add nsw i32 %i.05, %s
 127   %cmp = icmp slt i32 %i.05, %n
 128   br i1 %cmp, label %for.body, label %for.end
 129
 130 for.end:                                          ; preds = %for.body, %entry
 131   ret void
 132 }
 133
 134 ; FIXME: Currently we are more conservative for known zero stride than
 135 ; for unknown but potentially zero stride.
 136 ; CHECK-LABEL: Determining loop execution counts for: @zero_stride
 137 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
 138 ; CHECK: Loop %for.body: Unpredictable constant max backedge-taken count.
 139 ; CHECK: Loop %for.body: Unpredictable predicated backedge-taken count.
 140 ; Note that this function is well defined only when %n <=s 0
 141 define void @zero_stride(ptr nocapture %A, i32 %n) {
 142 entry:
 143   br label %for.body
 144
 145 for.body:                                         ; preds = %entry, %for.body
 146   %i.05 = phi i32 [ %add, %for.body ], [ 0, %entry ]
 147   %arrayidx = getelementptr inbounds i32, ptr %A, i32 %i.05
 148   %0 = load i32, ptr %arrayidx, align 4
 149   %inc = add nsw i32 %0, 1
 150   store i32 %inc, ptr %arrayidx, align 4
 151   %add = add nsw i32 %i.05, 0
 152   %cmp = icmp slt i32 %add, %n
 153   br i1 %cmp, label %for.body, label %for.end, !llvm.loop !8
 154
 155 for.end:                                          ; preds = %for.body, %entry
 156   ret void
 157 }
 158
 159 ; CHECK-LABEL: Determining loop execution counts for: @zero_stride_ub
 160 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
 161 ; CHECK: Loop %for.body: Unpredictable constant max backedge-taken count.
 162 ; CHECK: Loop %for.body: Unpredictable predicated backedge-taken count.
 163 ; Note that this function will always execute undefined behavior and thus
 164 ; any value is valid for a backedge taken count.
 165 define void @zero_stride_ub(ptr nocapture %A) {
 166 entry:
 167   br label %for.body
 168
 169 for.body:                                         ; preds = %entry, %for.body
 170   %i.05 = phi i32 [ %add, %for.body ], [ 0, %entry ]
 171   %arrayidx = getelementptr inbounds i32, ptr %A, i32 %i.05
 172   %0 = load i32, ptr %arrayidx, align 4
 173   %inc = add nsw i32 %0, 1
 174   store i32 %inc, ptr %arrayidx, align 4
 175   %add = add nsw i32 %i.05, 0
 176   %cmp = icmp slt i32 %add, 2
 177   br i1 %cmp, label %for.body, label %for.end, !llvm.loop !8
 178
 179 for.end:                                          ; preds = %for.body, %entry
 180   ret void
 181 }
 182
 183 ; When %zero = 0, this loop is only well defined if %n < 0 and thus BTC = 0.
 184 ; CHECK-LABEL: Determining loop execution counts for: @zero_stride_symbolic
 185 ; CHECK: Loop %for.body: backedge-taken count is ((((-1 * (1 umin ((-1 * %zero) + (%n smax %zero))))<nuw><nsw> + (-1 * %zero) + (%n smax %zero)) /u (1 umax %zero)) + (1 umin ((-1 * %zero) + (%n smax %zero))))
 186 ; CHECK: Loop %for.body: constant max backedge-taken count is -1
 187
 188 define void @zero_stride_symbolic(ptr nocapture %A, i32 %n, i32 %zero) {
 189 entry:
 190   br label %for.body
 191
 192 for.body:                                         ; preds = %entry, %for.body
 193   %i.05 = phi i32 [ %add, %for.body ], [ 0, %entry ]
 194   %arrayidx = getelementptr inbounds i32, ptr %A, i32 %i.05
 195   %0 = load i32, ptr %arrayidx, align 4
 196   %inc = add nsw i32 %0, 1
 197   store i32 %inc, ptr %arrayidx, align 4
 198   %add = add nsw i32 %i.05, %zero
 199   %cmp = icmp slt i32 %add, %n
 200   br i1 %cmp, label %for.body, label %for.end, !llvm.loop !8
 201
 202 for.end:                                          ; preds = %for.body, %entry
 203   ret void
 204 }
 205
 206
 207 ; CHECK-LABEL: Determining loop execution counts for: @zero_stride_varying_rhs
 208 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
 209 ; CHECK: Loop %for.body: Unpredictable constant max backedge-taken count
 210
 211 define void @zero_stride_varying_rhs(ptr nocapture %A, ptr %n_p, i32 %zero) {
 212 entry:
 213   br label %for.body
 214
 215 for.body:                                         ; preds = %entry, %for.body
 216   %i.05 = phi i32 [ %add, %for.body ], [ 0, %entry ]
 217   %arrayidx = getelementptr inbounds i32, ptr %A, i32 %i.05
 218   %0 = load i32, ptr %arrayidx, align 4
 219   %inc = add nsw i32 %0, 1
 220   store i32 %inc, ptr %arrayidx, align 4
 221   %add = add nsw i32 %i.05, %zero
 222   %n = load i32, ptr %n_p
 223   %cmp = icmp slt i32 %add, %n
 224   br i1 %cmp, label %for.body, label %for.end, !llvm.loop !8
 225
 226 for.end:                                          ; preds = %for.body, %entry
 227   ret void
 228 }
 229
 230
 231
 232 !8 = distinct !{!8, !9}
 233 !9 = !{!"llvm.loop.mustprogress"}