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

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