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