test/Analysis/DependenceAnalysis/StrongSIV.ll

   1 ; RUN: opt < %s -analyze -basicaa -indvars -da | FileCheck %s
   2
   3 ; ModuleID = 'StrongSIV.bc'
   4 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
   5 target triple = "x86_64-apple-macosx10.6.0"
   6
   7
   8 ;;  for (int i = 0; i < n; i++)
   9 ;;    A[i + 2] = ...
  10 ;;    ... = A[i];
  11
  12 define void @strong0(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
  13 entry:
  14   %cmp1 = icmp sgt i64 %n, 0
  15   br i1 %cmp1, label %for.body, label %for.end
  16
  17 for.body:                                         ; preds = %for.body, %entry
  18   %i.03 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  19   %B.addr.02 = phi i32* [ %incdec.ptr, %for.body ], [ %B, %entry ]
  20   %add = add nsw i32 %i.03, 2
  21   %idxprom = sext i32 %add to i64
  22   %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
  23   store i32 %i.03, i32* %arrayidx, align 4
  24   %idxprom2 = sext i32 %i.03 to i64
  25   %arrayidx3 = getelementptr inbounds i32* %A, i64 %idxprom2
  26   %0 = load i32* %arrayidx3, align 4
  27 ; CHECK: da analyze - consistent flow [2]!
  28   %incdec.ptr = getelementptr inbounds i32* %B.addr.02, i64 1
  29   store i32 %0, i32* %B.addr.02, align 4
  30   %inc = add nsw i32 %i.03, 1
  31   %conv = sext i32 %inc to i64
  32   %cmp = icmp slt i64 %conv, %n
  33   br i1 %cmp, label %for.body, label %for.end
  34
  35 for.end:                                          ; preds = %for.body, %entry
  36   ret void
  37 }
  38
  39
  40 ;;  for (long int i = 0; i < n; i++)
  41 ;;    A[i + 2] = ...
  42 ;;    ... = A[i];
  43
  44 define void @strong1(i32* %A, i32* %B, i32 %n) nounwind uwtable ssp {
  45 entry:
  46   %conv = sext i32 %n to i64
  47   %cmp1 = icmp sgt i32 %n, 0
  48   br i1 %cmp1, label %for.body, label %for.end
  49
  50 for.body:                                         ; preds = %for.body, %entry
  51   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
  52   %B.addr.02 = phi i32* [ %incdec.ptr, %for.body ], [ %B, %entry ]
  53   %conv2 = trunc i64 %i.03 to i32
  54   %add = add nsw i64 %i.03, 2
  55   %arrayidx = getelementptr inbounds i32* %A, i64 %add
  56   store i32 %conv2, i32* %arrayidx, align 4
  57   %arrayidx3 = getelementptr inbounds i32* %A, i64 %i.03
  58   %0 = load i32* %arrayidx3, align 4
  59 ; CHECK: da analyze - consistent flow [2]!
  60   %incdec.ptr = getelementptr inbounds i32* %B.addr.02, i64 1
  61   store i32 %0, i32* %B.addr.02, align 4
  62   %inc = add nsw i64 %i.03, 1
  63   %cmp = icmp slt i64 %inc, %conv
  64   br i1 %cmp, label %for.body, label %for.end
  65
  66 for.end:                                          ; preds = %for.body, %entry
  67   ret void
  68 }
  69
  70
  71 ;;  for (long unsigned i = 0; i < n; i++)
  72 ;;    A[i + 2] = ...
  73 ;;    ... = A[i];
  74
  75 define void @strong2(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
  76 entry:
  77   %cmp1 = icmp eq i64 %n, 0
  78   br i1 %cmp1, label %for.end, label %for.body
  79
  80 for.body:                                         ; preds = %for.body, %entry
  81   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
  82   %B.addr.02 = phi i32* [ %incdec.ptr, %for.body ], [ %B, %entry ]
  83   %conv = trunc i64 %i.03 to i32
  84   %add = add i64 %i.03, 2
  85   %arrayidx = getelementptr inbounds i32* %A, i64 %add
  86   store i32 %conv, i32* %arrayidx, align 4
  87   %arrayidx1 = getelementptr inbounds i32* %A, i64 %i.03
  88   %0 = load i32* %arrayidx1, align 4
  89 ; CHECK: da analyze - consistent flow [2]!
  90   %incdec.ptr = getelementptr inbounds i32* %B.addr.02, i64 1
  91   store i32 %0, i32* %B.addr.02, align 4
  92   %inc = add i64 %i.03, 1
  93   %cmp = icmp ult i64 %inc, %n
  94   br i1 %cmp, label %for.body, label %for.end
  95
  96 for.end:                                          ; preds = %for.body, %entry
  97   ret void
  98 }
  99
 100
 101 ;;  for (int i = 0; i < n; i++)
 102 ;;    A[i + 2] = ...
 103 ;;    ... = A[i];
 104
 105 define void @strong3(i32* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 106 entry:
 107   %cmp1 = icmp sgt i32 %n, 0
 108   br i1 %cmp1, label %for.body, label %for.end
 109
 110 for.body:                                         ; preds = %for.body, %entry
 111   %i.03 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 112   %B.addr.02 = phi i32* [ %incdec.ptr, %for.body ], [ %B, %entry ]
 113   %add = add nsw i32 %i.03, 2
 114   %idxprom = sext i32 %add to i64
 115   %arrayidx = getelementptr inbounds i32* %A, i64 %idxprom
 116   store i32 %i.03, i32* %arrayidx, align 4
 117   %idxprom1 = sext i32 %i.03 to i64
 118   %arrayidx2 = getelementptr inbounds i32* %A, i64 %idxprom1
 119   %0 = load i32* %arrayidx2, align 4
 120 ; CHECK: da analyze - consistent flow [2]!
 121   %incdec.ptr = getelementptr inbounds i32* %B.addr.02, i64 1
 122   store i32 %0, i32* %B.addr.02, align 4
 123   %inc = add nsw i32 %i.03, 1
 124   %cmp = icmp slt i32 %inc, %n
 125   br i1 %cmp, label %for.body, label %for.end
 126
 127 for.end:                                          ; preds = %for.body, %entry
 128   ret void
 129 }
 130
 131
 132 ;;  for (long unsigned i = 0; i < 19; i++)
 133 ;;    A[i + 19] = ...
 134 ;;    ... = A[i];
 135
 136 define void @strong4(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
 137 entry:
 138   br label %for.body
 139
 140 for.body:                                         ; preds = %for.body, %entry
 141   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
 142   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
 143   %conv = trunc i64 %i.02 to i32
 144   %add = add i64 %i.02, 19
 145   %arrayidx = getelementptr inbounds i32* %A, i64 %add
 146   store i32 %conv, i32* %arrayidx, align 4
 147   %arrayidx1 = getelementptr inbounds i32* %A, i64 %i.02
 148   %0 = load i32* %arrayidx1, align 4
 149 ; CHECK: da analyze - none!
 150   %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
 151   store i32 %0, i32* %B.addr.01, align 4
 152   %inc = add i64 %i.02, 1
 153   %cmp = icmp ult i64 %inc, 19
 154   br i1 %cmp, label %for.body, label %for.end
 155
 156 for.end:                                          ; preds = %for.body
 157   ret void
 158 }
 159
 160
 161 ;;  for (long unsigned i = 0; i < 20; i++)
 162 ;;    A[i + 19] = ...
 163 ;;    ... = A[i];
 164
 165 define void @strong5(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
 166 entry:
 167   br label %for.body
 168
 169 for.body:                                         ; preds = %for.body, %entry
 170   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
 171   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
 172   %conv = trunc i64 %i.02 to i32
 173   %add = add i64 %i.02, 19
 174   %arrayidx = getelementptr inbounds i32* %A, i64 %add
 175   store i32 %conv, i32* %arrayidx, align 4
 176   %arrayidx1 = getelementptr inbounds i32* %A, i64 %i.02
 177   %0 = load i32* %arrayidx1, align 4
 178 ; CHECK: da analyze - consistent flow [19]!
 179   %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
 180   store i32 %0, i32* %B.addr.01, align 4
 181   %inc = add i64 %i.02, 1
 182   %cmp = icmp ult i64 %inc, 20
 183   br i1 %cmp, label %for.body, label %for.end
 184
 185 for.end:                                          ; preds = %for.body
 186   ret void
 187 }
 188
 189
 190 ;;  for (long unsigned i = 0; i < 20; i++)
 191 ;;    A[2*i + 6] = ...
 192 ;;    ... = A[2*i];
 193
 194 define void @strong6(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
 195 entry:
 196   br label %for.body
 197
 198 for.body:                                         ; preds = %for.body, %entry
 199   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
 200   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
 201   %conv = trunc i64 %i.02 to i32
 202   %mul = shl i64 %i.02, 1
 203   %add = add i64 %mul, 6
 204   %arrayidx = getelementptr inbounds i32* %A, i64 %add
 205   store i32 %conv, i32* %arrayidx, align 4
 206   %mul1 = shl i64 %i.02, 1
 207   %arrayidx2 = getelementptr inbounds i32* %A, i64 %mul1
 208   %0 = load i32* %arrayidx2, align 4
 209 ; CHECK: da analyze - consistent flow [3]!
 210   %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
 211   store i32 %0, i32* %B.addr.01, align 4
 212   %inc = add i64 %i.02, 1
 213   %cmp = icmp ult i64 %inc, 20
 214   br i1 %cmp, label %for.body, label %for.end
 215
 216 for.end:                                          ; preds = %for.body
 217   ret void
 218 }
 219
 220
 221 ;;  for (long unsigned i = 0; i < 20; i++)
 222 ;;    A[2*i + 7] = ...
 223 ;;    ... = A[2*i];
 224
 225 define void @strong7(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
 226 entry:
 227   br label %for.body
 228
 229 for.body:                                         ; preds = %for.body, %entry
 230   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
 231   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
 232   %conv = trunc i64 %i.02 to i32
 233   %mul = shl i64 %i.02, 1
 234   %add = add i64 %mul, 7
 235   %arrayidx = getelementptr inbounds i32* %A, i64 %add
 236   store i32 %conv, i32* %arrayidx, align 4
 237   %mul1 = shl i64 %i.02, 1
 238   %arrayidx2 = getelementptr inbounds i32* %A, i64 %mul1
 239   %0 = load i32* %arrayidx2, align 4
 240 ; CHECK: da analyze - none!
 241   %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
 242   store i32 %0, i32* %B.addr.01, align 4
 243   %inc = add i64 %i.02, 1
 244   %cmp = icmp ult i64 %inc, 20
 245   br i1 %cmp, label %for.body, label %for.end
 246
 247 for.end:                                          ; preds = %for.body
 248   ret void
 249 }
 250
 251
 252 ;;  for (long unsigned i = 0; i < 20; i++)
 253 ;;    A[i + n] = ...
 254 ;;    ... = A[i];
 255
 256 define void @strong8(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
 257 entry:
 258   br label %for.body
 259
 260 for.body:                                         ; preds = %for.body, %entry
 261   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
 262   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
 263   %conv = trunc i64 %i.02 to i32
 264   %add = add i64 %i.02, %n
 265   %arrayidx = getelementptr inbounds i32* %A, i64 %add
 266   store i32 %conv, i32* %arrayidx, align 4
 267   %arrayidx1 = getelementptr inbounds i32* %A, i64 %i.02
 268   %0 = load i32* %arrayidx1, align 4
 269 ; CHECK: da analyze - consistent flow [%n|<]!
 270   %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
 271   store i32 %0, i32* %B.addr.01, align 4
 272   %inc = add i64 %i.02, 1
 273   %cmp = icmp ult i64 %inc, 20
 274   br i1 %cmp, label %for.body, label %for.end
 275
 276 for.end:                                          ; preds = %for.body
 277   ret void
 278 }
 279
 280
 281 ;;  for (long unsigned i = 0; i < n; i++)
 282 ;;    A[i + n] = ...
 283 ;;    ... = A[i + 2*n];
 284
 285 define void @strong9(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
 286 entry:
 287   %cmp1 = icmp eq i64 %n, 0
 288   br i1 %cmp1, label %for.end, label %for.body
 289
 290 for.body:                                         ; preds = %for.body, %entry
 291   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
 292   %B.addr.02 = phi i32* [ %incdec.ptr, %for.body ], [ %B, %entry ]
 293   %conv = trunc i64 %i.03 to i32
 294   %add = add i64 %i.03, %n
 295   %arrayidx = getelementptr inbounds i32* %A, i64 %add
 296   store i32 %conv, i32* %arrayidx, align 4
 297   %mul = shl i64 %n, 1
 298   %add1 = add i64 %i.03, %mul
 299   %arrayidx2 = getelementptr inbounds i32* %A, i64 %add1
 300   %0 = load i32* %arrayidx2, align 4
 301 ; CHECK: da analyze - none!
 302   %incdec.ptr = getelementptr inbounds i32* %B.addr.02, i64 1
 303   store i32 %0, i32* %B.addr.02, align 4
 304   %inc = add i64 %i.03, 1
 305   %cmp = icmp ult i64 %inc, %n
 306   br i1 %cmp, label %for.body, label %for.end
 307
 308 for.end:                                          ; preds = %for.body, %entry
 309   ret void
 310 }
 311
 312
 313 ;;  for (long unsigned i = 0; i < 1000; i++)
 314 ;;    A[n*i + 5] = ...
 315 ;;    ... = A[n*i + 5];
 316
 317 define void @strong10(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
 318 entry:
 319   br label %for.body
 320
 321 for.body:                                         ; preds = %for.body, %entry
 322   %i.02 = phi i64 [ 0, %entry ], [ %inc, %for.body ]
 323   %B.addr.01 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.body ]
 324   %conv = trunc i64 %i.02 to i32
 325   %mul = mul i64 %i.02, %n
 326   %add = add i64 %mul, 5
 327   %arrayidx = getelementptr inbounds i32* %A, i64 %add
 328   store i32 %conv, i32* %arrayidx, align 4
 329   %mul1 = mul i64 %i.02, %n
 330   %add2 = add i64 %mul1, 5
 331   %arrayidx3 = getelementptr inbounds i32* %A, i64 %add2
 332   %0 = load i32* %arrayidx3, align 4
 333 ; CHECK: da analyze - consistent flow [0|<]!
 334   %incdec.ptr = getelementptr inbounds i32* %B.addr.01, i64 1
 335   store i32 %0, i32* %B.addr.01, align 4
 336   %inc = add i64 %i.02, 1
 337   %cmp = icmp ult i64 %inc, 1000
 338   br i1 %cmp, label %for.body, label %for.end
 339
 340 for.end:                                          ; preds = %for.body
 341   ret void
 342 }