llvm/test/Analysis/DependenceAnalysis/SymbolicSIV.ll

   1 ; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 \
   2 ; RUN: | FileCheck %s
   3
   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 (long int i = 0; i < n; i++) {
   9 ;;    A[2*i + n] = i;
  10 ;;    *B++ = A[3*i + 3*n];
  11
  12 define void @symbolicsiv0(ptr %A, ptr %B, i64 %n) nounwind uwtable ssp {
  13 entry:
  14   %cmp1 = icmp eq i64 %n, 0
  15   br i1 %cmp1, label %for.end, label %for.body.preheader
  16
  17 ; CHECK: da analyze - none!
  18 ; CHECK: da analyze - none!
  19 ; CHECK: da analyze - confused!
  20 ; CHECK: da analyze - none!
  21 ; CHECK: da analyze - confused!
  22 ; CHECK: da analyze - none!
  23
  24 for.body.preheader:                               ; preds = %entry
  25   br label %for.body
  26
  27 for.body:                                         ; preds = %for.body.preheader, %for.body
  28   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
  29   %B.addr.02 = phi ptr [ %incdec.ptr, %for.body ], [ %B, %for.body.preheader ]
  30   %conv = trunc i64 %i.03 to i32
  31   %mul = shl nsw i64 %i.03, 1
  32   %add = add i64 %mul, %n
  33   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %add
  34   store i32 %conv, ptr %arrayidx, align 4
  35   %mul14 = add i64 %i.03, %n
  36   %add3 = mul i64 %mul14, 3
  37   %arrayidx4 = getelementptr inbounds i32, ptr %A, i64 %add3
  38   %0 = load i32, ptr %arrayidx4, align 4
  39   %incdec.ptr = getelementptr inbounds i32, ptr %B.addr.02, i64 1
  40   store i32 %0, ptr %B.addr.02, align 4
  41   %inc = add nsw i64 %i.03, 1
  42   %exitcond = icmp ne i64 %inc, %n
  43   br i1 %exitcond, label %for.body, label %for.end.loopexit
  44
  45 for.end.loopexit:                                 ; preds = %for.body
  46   br label %for.end
  47
  48 for.end:                                          ; preds = %for.end.loopexit, %entry
  49   ret void
  50 }
  51
  52
  53 ;;  for (long int i = 0; i < n; i++) {
  54 ;;    A[2*i + 5*n] = i;
  55 ;;    *B++ = A[3*i + 2*n];
  56
  57 define void @symbolicsiv1(ptr %A, ptr %B, i64 %n) nounwind uwtable ssp {
  58 entry:
  59   %cmp1 = icmp eq i64 %n, 0
  60   br i1 %cmp1, label %for.end, label %for.body.preheader
  61
  62 ; CHECK: da analyze - none!
  63 ; CHECK: da analyze - none!
  64 ; CHECK: da analyze - confused!
  65 ; CHECK: da analyze - none!
  66 ; CHECK: da analyze - confused!
  67 ; CHECK: da analyze - none!
  68
  69 for.body.preheader:                               ; preds = %entry
  70   br label %for.body
  71
  72 for.body:                                         ; preds = %for.body.preheader, %for.body
  73   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
  74   %B.addr.02 = phi ptr [ %incdec.ptr, %for.body ], [ %B, %for.body.preheader ]
  75   %conv = trunc i64 %i.03 to i32
  76   %mul = shl nsw i64 %i.03, 1
  77   %mul1 = mul i64 %n, 5
  78   %add = add i64 %mul, %mul1
  79   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %add
  80   store i32 %conv, ptr %arrayidx, align 4
  81   %mul2 = mul nsw i64 %i.03, 3
  82   %mul3 = shl i64 %n, 1
  83   %add4 = add i64 %mul2, %mul3
  84   %arrayidx5 = getelementptr inbounds i32, ptr %A, i64 %add4
  85   %0 = load i32, ptr %arrayidx5, align 4
  86   %incdec.ptr = getelementptr inbounds i32, ptr %B.addr.02, i64 1
  87   store i32 %0, ptr %B.addr.02, align 4
  88   %inc = add nsw i64 %i.03, 1
  89   %exitcond = icmp ne i64 %inc, %n
  90   br i1 %exitcond, label %for.body, label %for.end.loopexit
  91
  92 for.end.loopexit:                                 ; preds = %for.body
  93   br label %for.end
  94
  95 for.end:                                          ; preds = %for.end.loopexit, %entry
  96   ret void
  97 }
  98
  99
 100 ;;  for (long int i = 0; i < n; i++) {
 101 ;;    A[2*i - n] = i;
 102 ;;    *B++ = A[-i + 2*n];
 103
 104 define void @symbolicsiv2(ptr %A, ptr %B, i64 %n) nounwind uwtable ssp {
 105 entry:
 106   %cmp1 = icmp eq i64 %n, 0
 107   br i1 %cmp1, label %for.end, label %for.body.preheader
 108
 109 ; CHECK: da analyze - none!
 110 ; CHECK: da analyze - none!
 111 ; CHECK: da analyze - confused!
 112 ; CHECK: da analyze - none!
 113 ; CHECK: da analyze - confused!
 114 ; CHECK: da analyze - none!
 115
 116 for.body.preheader:                               ; preds = %entry
 117   br label %for.body
 118
 119 for.body:                                         ; preds = %for.body.preheader, %for.body
 120   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
 121   %B.addr.02 = phi ptr [ %incdec.ptr, %for.body ], [ %B, %for.body.preheader ]
 122   %conv = trunc i64 %i.03 to i32
 123   %mul = shl nsw i64 %i.03, 1
 124   %sub = sub i64 %mul, %n
 125   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %sub
 126   store i32 %conv, ptr %arrayidx, align 4
 127   %mul2 = shl i64 %n, 1
 128   %add = sub i64 %mul2, %i.03
 129   %arrayidx3 = getelementptr inbounds i32, ptr %A, i64 %add
 130   %0 = load i32, ptr %arrayidx3, align 4
 131   %incdec.ptr = getelementptr inbounds i32, ptr %B.addr.02, i64 1
 132   store i32 %0, ptr %B.addr.02, align 4
 133   %inc = add nsw i64 %i.03, 1
 134   %exitcond = icmp ne i64 %inc, %n
 135   br i1 %exitcond, label %for.body, label %for.end.loopexit
 136
 137 for.end.loopexit:                                 ; preds = %for.body
 138   br label %for.end
 139
 140 for.end:                                          ; preds = %for.end.loopexit, %entry
 141   ret void
 142 }
 143
 144
 145 ;;  for (long int i = 0; i < n; i++) {
 146 ;;    A[-2*i + n + 1] = i;
 147 ;;    *B++ = A[i - 2*n];
 148
 149 define void @symbolicsiv3(ptr %A, ptr %B, i64 %n) nounwind uwtable ssp {
 150 entry:
 151   %cmp1 = icmp eq i64 %n, 0
 152   br i1 %cmp1, label %for.end, label %for.body.preheader
 153
 154 ; CHECK: da analyze - none!
 155 ; CHECK: da analyze - none!
 156 ; CHECK: da analyze - confused!
 157 ; CHECK: da analyze - none!
 158 ; CHECK: da analyze - confused!
 159 ; CHECK: da analyze - none!
 160
 161 for.body.preheader:                               ; preds = %entry
 162   br label %for.body
 163
 164 for.body:                                         ; preds = %for.body.preheader, %for.body
 165   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
 166   %B.addr.02 = phi ptr [ %incdec.ptr, %for.body ], [ %B, %for.body.preheader ]
 167   %conv = trunc i64 %i.03 to i32
 168   %mul = mul nsw i64 %i.03, -2
 169   %add = add i64 %mul, %n
 170   %add1 = add i64 %add, 1
 171   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %add1
 172   store i32 %conv, ptr %arrayidx, align 4
 173   %mul2 = shl i64 %n, 1
 174   %sub = sub i64 %i.03, %mul2
 175   %arrayidx3 = getelementptr inbounds i32, ptr %A, i64 %sub
 176   %0 = load i32, ptr %arrayidx3, align 4
 177   %incdec.ptr = getelementptr inbounds i32, ptr %B.addr.02, i64 1
 178   store i32 %0, ptr %B.addr.02, align 4
 179   %inc = add nsw i64 %i.03, 1
 180   %exitcond = icmp ne i64 %inc, %n
 181   br i1 %exitcond, label %for.body, label %for.end.loopexit
 182
 183 for.end.loopexit:                                 ; preds = %for.body
 184   br label %for.end
 185
 186 for.end:                                          ; preds = %for.end.loopexit, %entry
 187   ret void
 188 }
 189
 190
 191 ;;  for (long int i = 0; i < n; i++) {
 192 ;;    A[-2*i + 3*n] = i;
 193 ;;    *B++ = A[-i + n];
 194
 195 define void @symbolicsiv4(ptr %A, ptr %B, i64 %n) nounwind uwtable ssp {
 196 entry:
 197   %cmp1 = icmp eq i64 %n, 0
 198   br i1 %cmp1, label %for.end, label %for.body.preheader
 199
 200 ; CHECK: da analyze - none!
 201 ; CHECK: da analyze - none!
 202 ; CHECK: da analyze - confused!
 203 ; CHECK: da analyze - none!
 204 ; CHECK: da analyze - confused!
 205 ; CHECK: da analyze - none!
 206
 207 for.body.preheader:                               ; preds = %entry
 208   br label %for.body
 209
 210 for.body:                                         ; preds = %for.body.preheader, %for.body
 211   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
 212   %B.addr.02 = phi ptr [ %incdec.ptr, %for.body ], [ %B, %for.body.preheader ]
 213   %conv = trunc i64 %i.03 to i32
 214   %mul = mul nsw i64 %i.03, -2
 215   %mul1 = mul i64 %n, 3
 216   %add = add i64 %mul, %mul1
 217   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %add
 218   store i32 %conv, ptr %arrayidx, align 4
 219   %add2 = sub i64 %n, %i.03
 220   %arrayidx3 = getelementptr inbounds i32, ptr %A, i64 %add2
 221   %0 = load i32, ptr %arrayidx3, align 4
 222   %incdec.ptr = getelementptr inbounds i32, ptr %B.addr.02, i64 1
 223   store i32 %0, ptr %B.addr.02, align 4
 224   %inc = add nsw i64 %i.03, 1
 225   %exitcond = icmp ne i64 %inc, %n
 226   br i1 %exitcond, label %for.body, label %for.end.loopexit
 227
 228 for.end.loopexit:                                 ; preds = %for.body
 229   br label %for.end
 230
 231 for.end:                                          ; preds = %for.end.loopexit, %entry
 232   ret void
 233 }
 234
 235
 236 ;;  for (long int i = 0; i < n; i++) {
 237 ;;    A[-2*i - 2*n] = i;
 238 ;;    *B++ = A[-i - n];
 239
 240 define void @symbolicsiv5(ptr %A, ptr %B, i64 %n) nounwind uwtable ssp {
 241 entry:
 242   %cmp1 = icmp eq i64 %n, 0
 243   br i1 %cmp1, label %for.end, label %for.body.preheader
 244
 245 ; CHECK: da analyze - none!
 246 ; CHECK: da analyze - none!
 247 ; CHECK: da analyze - confused!
 248 ; CHECK: da analyze - none!
 249 ; CHECK: da analyze - confused!
 250 ; CHECK: da analyze - none!
 251
 252 for.body.preheader:                               ; preds = %entry
 253   br label %for.body
 254
 255 for.body:                                         ; preds = %for.body.preheader, %for.body
 256   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
 257   %B.addr.02 = phi ptr [ %incdec.ptr, %for.body ], [ %B, %for.body.preheader ]
 258   %conv = trunc i64 %i.03 to i32
 259   %mul = mul nsw i64 %i.03, -2
 260   %mul1 = shl i64 %n, 1
 261   %sub = sub i64 %mul, %mul1
 262   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %sub
 263   store i32 %conv, ptr %arrayidx, align 4
 264   %sub2 = sub nsw i64 0, %i.03
 265   %sub3 = sub i64 %sub2, %n
 266   %arrayidx4 = getelementptr inbounds i32, ptr %A, i64 %sub3
 267   %0 = load i32, ptr %arrayidx4, align 4
 268   %incdec.ptr = getelementptr inbounds i32, ptr %B.addr.02, i64 1
 269   store i32 %0, ptr %B.addr.02, align 4
 270   %inc = add nsw i64 %i.03, 1
 271   %exitcond = icmp ne i64 %inc, %n
 272   br i1 %exitcond, label %for.body, label %for.end.loopexit
 273
 274 for.end.loopexit:                                 ; preds = %for.body
 275   br label %for.end
 276
 277 for.end:                                          ; preds = %for.end.loopexit, %entry
 278   ret void
 279 }
 280
 281
 282 ;; why doesn't SCEV package understand that n >= 0?
 283 ;;  for (long unsigned i = 0; i < n; i++) {
 284 ;;    A[i + n + 1] = i;
 285 ;;    *B++ = A[-i];
 286
 287 define void @weaktest(ptr %A, ptr %B, i64 %n) nounwind uwtable ssp {
 288 entry:
 289   %cmp1 = icmp eq i64 %n, 0
 290   br i1 %cmp1, label %for.end, label %for.body.preheader
 291
 292 ; CHECK: da analyze - none!
 293 ; CHECK: da analyze - flow [*|<] splitable!
 294 ; CHECK: da analyze - split level = 1, iteration = ((0 smax (-4 + (-4 * %n))) /u 8)!
 295 ; CHECK: da analyze - confused!
 296 ; CHECK: da analyze - none!
 297 ; CHECK: da analyze - confused!
 298 ; CHECK: da analyze - none!
 299
 300 for.body.preheader:                               ; preds = %entry
 301   br label %for.body
 302
 303 for.body:                                         ; preds = %for.body.preheader, %for.body
 304   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
 305   %B.addr.02 = phi ptr [ %incdec.ptr, %for.body ], [ %B, %for.body.preheader ]
 306   %conv = trunc i64 %i.03 to i32
 307   %add = add i64 %i.03, %n
 308   %add1 = add i64 %add, 1
 309   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %add1
 310   store i32 %conv, ptr %arrayidx, align 4
 311   %sub = sub i64 0, %i.03
 312   %arrayidx2 = getelementptr inbounds i32, ptr %A, i64 %sub
 313   %0 = load i32, ptr %arrayidx2, align 4
 314   %incdec.ptr = getelementptr inbounds i32, ptr %B.addr.02, i64 1
 315   store i32 %0, ptr %B.addr.02, align 4
 316   %inc = add i64 %i.03, 1
 317   %exitcond = icmp ne i64 %inc, %n
 318   br i1 %exitcond, label %for.body, label %for.end.loopexit
 319
 320 for.end.loopexit:                                 ; preds = %for.body
 321   br label %for.end
 322
 323 for.end:                                          ; preds = %for.end.loopexit, %entry
 324   ret void
 325 }
 326
 327
 328 ;;  for (long int i = 0; i < n; i++) {
 329 ;;    A[4*N*i + M] = i;
 330 ;;    *B++ = A[4*N*i + 3*M + 1];
 331
 332 define void @symbolicsiv6(ptr %A, ptr %B, i64 %n, i64 %N, i64 %M) nounwind uwtable ssp {
 333 entry:
 334   %cmp1 = icmp eq i64 %n, 0
 335   br i1 %cmp1, label %for.end, label %for.body.preheader
 336
 337 ; CHECK-LABEL: symbolicsiv6
 338 ; CHECK: da analyze - none!
 339 ; CHECK: da analyze - none!
 340 ; CHECK: da analyze - confused!
 341 ; CHECK: da analyze - none!
 342 ; CHECK: da analyze - confused!
 343 ; CHECK: da analyze - none!
 344
 345 for.body.preheader:                               ; preds = %entry
 346   br label %for.body
 347
 348 for.body:                                         ; preds = %for.body.preheader, %for.body
 349   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
 350   %B.addr.02 = phi ptr [ %incdec.ptr, %for.body ], [ %B, %for.body.preheader ]
 351   %conv = trunc i64 %i.03 to i32
 352   %mul = shl i64 %N, 2
 353   %mul1 = mul i64 %mul, %i.03
 354   %add = add i64 %mul1, %M
 355   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %add
 356   store i32 %conv, ptr %arrayidx, align 4
 357   %mul2 = shl i64 %N, 2
 358   %mul3 = mul i64 %mul2, %i.03
 359   %mul4 = mul i64 %M, 3
 360   %add5 = add i64 %mul3, %mul4
 361   %add6 = add i64 %add5, 1
 362   %arrayidx7 = getelementptr inbounds i32, ptr %A, i64 %add6
 363   %0 = load i32, ptr %arrayidx7, align 4
 364   %incdec.ptr = getelementptr inbounds i32, ptr %B.addr.02, i64 1
 365   store i32 %0, ptr %B.addr.02, align 4
 366   %inc = add nsw i64 %i.03, 1
 367   %exitcond = icmp ne i64 %inc, %n
 368   br i1 %exitcond, label %for.body, label %for.end.loopexit
 369
 370 for.end.loopexit:                                 ; preds = %for.body
 371   br label %for.end
 372
 373 for.end:                                          ; preds = %for.end.loopexit, %entry
 374   ret void
 375 }
 376
 377
 378 ;;  for (long int i = 0; i < n; i++) {
 379 ;;    A[2*N*i + M] = i;
 380 ;;    *B++ = A[2*N*i - 3*M + 2];
 381
 382 define void @symbolicsiv7(ptr %A, ptr %B, i64 %n, i64 %N, i64 %M) nounwind uwtable ssp {
 383 entry:
 384   %cmp1 = icmp eq i64 %n, 0
 385   br i1 %cmp1, label %for.end, label %for.body.preheader
 386 ; CHECK-LABEL: symbolicsiv7
 387 ; CHECK: da analyze - none!
 388 ; CHECK: da analyze - flow [<>]!
 389 ; CHECK: da analyze - confused!
 390 ; CHECK: da analyze - none!
 391 ; CHECK: da analyze - confused!
 392 ; CHECK: da analyze - none!
 393
 394 for.body.preheader:                               ; preds = %entry
 395   br label %for.body
 396
 397 for.body:                                         ; preds = %for.body.preheader, %for.body
 398   %i.03 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
 399   %B.addr.02 = phi ptr [ %incdec.ptr, %for.body ], [ %B, %for.body.preheader ]
 400   %conv = trunc i64 %i.03 to i32
 401   %mul = shl i64 %N, 1
 402   %mul1 = mul i64 %mul, %i.03
 403   %add = add i64 %mul1, %M
 404   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %add
 405   store i32 %conv, ptr %arrayidx, align 4
 406   %mul2 = shl i64 %N, 1
 407   %mul3 = mul i64 %mul2, %i.03
 408   %0 = mul i64 %M, -3
 409   %sub = add i64 %mul3, %0
 410   %add5 = add i64 %sub, 2
 411   %arrayidx6 = getelementptr inbounds i32, ptr %A, i64 %add5
 412   %1 = load i32, ptr %arrayidx6, align 4
 413   %incdec.ptr = getelementptr inbounds i32, ptr %B.addr.02, i64 1
 414   store i32 %1, ptr %B.addr.02, align 4
 415   %inc = add nsw i64 %i.03, 1
 416   %exitcond = icmp ne i64 %inc, %n
 417   br i1 %exitcond, label %for.body, label %for.end.loopexit
 418
 419 for.end.loopexit:                                 ; preds = %for.body
 420   br label %for.end
 421
 422 for.end:                                          ; preds = %for.end.loopexit, %entry
 423   ret void
 424 }