test/Analysis/DependenceAnalysis/StrongSIV.ll

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