test/Analysis/DependenceAnalysis/Banerjee.ll

   1 ; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
   2
   3 ; ModuleID = 'Banerjee.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 (long int i = 1; i <= 10; i++)
   9 ;;    for (long int j = 1; j <= 10; j++) {
  10 ;;      A[10*i + j] = 0;
  11 ;;      *B++ = A[10*i + j - 1];
  12
  13 define void @banerjee0(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
  14 entry:
  15   br label %for.cond1.preheader
  16 ; CHECK: 'Dependence Analysis' for function 'banerjee0':
  17 ; CHECK: da analyze - none!
  18 ; CHECK: da analyze - flow [<= <>]!
  19 ; CHECK: da analyze - confused!
  20 ; CHECK: da analyze - none!
  21 ; CHECK: da analyze - confused!
  22 ; CHECK: da analyze - none!
  23
  24 for.cond1.preheader:                              ; preds = %entry, %for.inc7
  25   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
  26   %i.03 = phi i64 [ 1, %entry ], [ %inc8, %for.inc7 ]
  27   br label %for.body3
  28
  29 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
  30   %j.02 = phi i64 [ 1, %for.cond1.preheader ], [ %inc, %for.body3 ]
  31   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
  32   %mul = mul nsw i64 %i.03, 10
  33   %add = add nsw i64 %mul, %j.02
  34   %arrayidx = getelementptr inbounds i64* %A, i64 %add
  35   store i64 0, i64* %arrayidx, align 8
  36   %mul4 = mul nsw i64 %i.03, 10
  37   %add5 = add nsw i64 %mul4, %j.02
  38   %sub = add nsw i64 %add5, -1
  39   %arrayidx6 = getelementptr inbounds i64* %A, i64 %sub
  40   %0 = load i64* %arrayidx6, align 8
  41   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
  42   store i64 %0, i64* %B.addr.11, align 8
  43   %inc = add nsw i64 %j.02, 1
  44   %exitcond = icmp ne i64 %inc, 11
  45   br i1 %exitcond, label %for.body3, label %for.inc7
  46
  47 for.inc7:                                         ; preds = %for.body3
  48   %scevgep = getelementptr i64* %B.addr.04, i64 10
  49   %inc8 = add nsw i64 %i.03, 1
  50   %exitcond5 = icmp ne i64 %inc8, 11
  51   br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
  52
  53 for.end9:                                         ; preds = %for.inc7
  54   ret void
  55 }
  56
  57
  58 ;;  for (long int i = 1; i <= n; i++)
  59 ;;    for (long int j = 1; j <= m; j++) {
  60 ;;      A[10*i + j] = 0;
  61 ;;      *B++ = A[10*i + j - 1];
  62
  63 define void @banerjee1(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
  64 entry:
  65   %cmp4 = icmp sgt i64 %n, 0
  66   br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end9
  67
  68 ; CHECK: 'Dependence Analysis' for function 'banerjee1':
  69 ; CHECK: da analyze - output [* *]!
  70 ; CHECK: da analyze - flow [* <>]!
  71 ; CHECK: da analyze - confused!
  72 ; CHECK: da analyze - input [* *]!
  73 ; CHECK: da analyze - confused!
  74 ; CHECK: da analyze - output [* *]!
  75
  76 for.cond1.preheader.preheader:                    ; preds = %entry
  77   %0 = add i64 %n, 1
  78   br label %for.cond1.preheader
  79
  80 for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc7
  81   %B.addr.06 = phi i64* [ %B.addr.1.lcssa, %for.inc7 ], [ %B, %for.cond1.preheader.preheader ]
  82   %i.05 = phi i64 [ %inc8, %for.inc7 ], [ 1, %for.cond1.preheader.preheader ]
  83   %1 = add i64 %m, 1
  84   %cmp21 = icmp sgt i64 %m, 0
  85   br i1 %cmp21, label %for.body3.preheader, label %for.inc7
  86
  87 for.body3.preheader:                              ; preds = %for.cond1.preheader
  88   br label %for.body3
  89
  90 for.body3:                                        ; preds = %for.body3.preheader, %for.body3
  91   %j.03 = phi i64 [ %inc, %for.body3 ], [ 1, %for.body3.preheader ]
  92   %B.addr.12 = phi i64* [ %incdec.ptr, %for.body3 ], [ %B.addr.06, %for.body3.preheader ]
  93   %mul = mul nsw i64 %i.05, 10
  94   %add = add nsw i64 %mul, %j.03
  95   %arrayidx = getelementptr inbounds i64* %A, i64 %add
  96   store i64 0, i64* %arrayidx, align 8
  97   %mul4 = mul nsw i64 %i.05, 10
  98   %add5 = add nsw i64 %mul4, %j.03
  99   %sub = add nsw i64 %add5, -1
 100   %arrayidx6 = getelementptr inbounds i64* %A, i64 %sub
 101   %2 = load i64* %arrayidx6, align 8
 102   %incdec.ptr = getelementptr inbounds i64* %B.addr.12, i64 1
 103   store i64 %2, i64* %B.addr.12, align 8
 104   %inc = add nsw i64 %j.03, 1
 105   %exitcond = icmp eq i64 %inc, %1
 106   br i1 %exitcond, label %for.inc7.loopexit, label %for.body3
 107
 108 for.inc7.loopexit:                                ; preds = %for.body3
 109   %scevgep = getelementptr i64* %B.addr.06, i64 %m
 110   br label %for.inc7
 111
 112 for.inc7:                                         ; preds = %for.inc7.loopexit, %for.cond1.preheader
 113   %B.addr.1.lcssa = phi i64* [ %B.addr.06, %for.cond1.preheader ], [ %scevgep, %for.inc7.loopexit ]
 114   %inc8 = add nsw i64 %i.05, 1
 115   %exitcond7 = icmp eq i64 %inc8, %0
 116   br i1 %exitcond7, label %for.end9.loopexit, label %for.cond1.preheader
 117
 118 for.end9.loopexit:                                ; preds = %for.inc7
 119   br label %for.end9
 120
 121 for.end9:                                         ; preds = %for.end9.loopexit, %entry
 122   ret void
 123 }
 124
 125
 126 ;;  for (long int i = 0; i < 10; i++)
 127 ;;    for (long int j = 0; j < 10; j++) {
 128 ;;      A[10*i + j] = 0;
 129 ;;      *B++ = A[10*i + j + 100];
 130
 131 define void @banerjee2(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 132 entry:
 133   br label %for.cond1.preheader
 134
 135 ; CHECK: 'Dependence Analysis' for function 'banerjee2':
 136 ; CHECK: da analyze - none!
 137 ; CHECK: da analyze - none!
 138 ; CHECK: da analyze - confused!
 139 ; CHECK: da analyze - none!
 140 ; CHECK: da analyze - confused!
 141 ; CHECK: da analyze - none!
 142
 143 for.cond1.preheader:                              ; preds = %entry, %for.inc8
 144   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
 145   %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
 146   br label %for.body3
 147
 148 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 149   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 150   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 151   %mul = mul nsw i64 %i.03, 10
 152   %add = add nsw i64 %mul, %j.02
 153   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 154   store i64 0, i64* %arrayidx, align 8
 155   %mul4 = mul nsw i64 %i.03, 10
 156   %add5 = add nsw i64 %mul4, %j.02
 157   %add6 = add nsw i64 %add5, 100
 158   %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
 159   %0 = load i64* %arrayidx7, align 8
 160   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 161   store i64 %0, i64* %B.addr.11, align 8
 162   %inc = add nsw i64 %j.02, 1
 163   %exitcond = icmp ne i64 %inc, 10
 164   br i1 %exitcond, label %for.body3, label %for.inc8
 165
 166 for.inc8:                                         ; preds = %for.body3
 167   %scevgep = getelementptr i64* %B.addr.04, i64 10
 168   %inc9 = add nsw i64 %i.03, 1
 169   %exitcond5 = icmp ne i64 %inc9, 10
 170   br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
 171
 172 for.end10:                                        ; preds = %for.inc8
 173   ret void
 174 }
 175
 176
 177 ;;  for (long int i = 0; i < 10; i++)
 178 ;;    for (long int j = 0; j < 10; j++) {
 179 ;;      A[10*i + j] = 0;
 180 ;;      *B++ = A[10*i + j + 99];
 181
 182 define void @banerjee3(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 183 entry:
 184   br label %for.cond1.preheader
 185
 186 ; CHECK: 'Dependence Analysis' for function 'banerjee3':
 187 ; CHECK: da analyze - none!
 188 ; CHECK: da analyze - flow [> >]!
 189 ; CHECK: da analyze - confused!
 190 ; CHECK: da analyze - none!
 191 ; CHECK: da analyze - confused!
 192 ; CHECK: da analyze - none!
 193
 194 for.cond1.preheader:                              ; preds = %entry, %for.inc8
 195   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
 196   %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
 197   br label %for.body3
 198
 199 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 200   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 201   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 202   %mul = mul nsw i64 %i.03, 10
 203   %add = add nsw i64 %mul, %j.02
 204   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 205   store i64 0, i64* %arrayidx, align 8
 206   %mul4 = mul nsw i64 %i.03, 10
 207   %add5 = add nsw i64 %mul4, %j.02
 208   %add6 = add nsw i64 %add5, 99
 209   %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
 210   %0 = load i64* %arrayidx7, align 8
 211   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 212   store i64 %0, i64* %B.addr.11, align 8
 213   %inc = add nsw i64 %j.02, 1
 214   %exitcond = icmp ne i64 %inc, 10
 215   br i1 %exitcond, label %for.body3, label %for.inc8
 216
 217 for.inc8:                                         ; preds = %for.body3
 218   %scevgep = getelementptr i64* %B.addr.04, i64 10
 219   %inc9 = add nsw i64 %i.03, 1
 220   %exitcond5 = icmp ne i64 %inc9, 10
 221   br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
 222
 223 for.end10:                                        ; preds = %for.inc8
 224   ret void
 225 }
 226
 227
 228 ;;  for (long int i = 0; i < 10; i++)
 229 ;;    for (long int j = 0; j < 10; j++) {
 230 ;;      A[10*i + j] = 0;
 231 ;;      *B++ = A[10*i + j - 100];
 232
 233 define void @banerjee4(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 234 entry:
 235   br label %for.cond1.preheader
 236
 237 ; CHECK: 'Dependence Analysis' for function 'banerjee4':
 238 ; CHECK: da analyze - none!
 239 ; CHECK: da analyze - none!
 240 ; CHECK: da analyze - confused!
 241 ; CHECK: da analyze - none!
 242 ; CHECK: da analyze - confused!
 243 ; CHECK: da analyze - none!
 244
 245 for.cond1.preheader:                              ; preds = %entry, %for.inc7
 246   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
 247   %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
 248   br label %for.body3
 249
 250 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 251   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 252   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 253   %mul = mul nsw i64 %i.03, 10
 254   %add = add nsw i64 %mul, %j.02
 255   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 256   store i64 0, i64* %arrayidx, align 8
 257   %mul4 = mul nsw i64 %i.03, 10
 258   %add5 = add nsw i64 %mul4, %j.02
 259   %sub = add nsw i64 %add5, -100
 260   %arrayidx6 = getelementptr inbounds i64* %A, i64 %sub
 261   %0 = load i64* %arrayidx6, align 8
 262   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 263   store i64 %0, i64* %B.addr.11, align 8
 264   %inc = add nsw i64 %j.02, 1
 265   %exitcond = icmp ne i64 %inc, 10
 266   br i1 %exitcond, label %for.body3, label %for.inc7
 267
 268 for.inc7:                                         ; preds = %for.body3
 269   %scevgep = getelementptr i64* %B.addr.04, i64 10
 270   %inc8 = add nsw i64 %i.03, 1
 271   %exitcond5 = icmp ne i64 %inc8, 10
 272   br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
 273
 274 for.end9:                                         ; preds = %for.inc7
 275   ret void
 276 }
 277
 278
 279 ;;  for (long int i = 0; i < 10; i++)
 280 ;;    for (long int j = 0; j < 10; j++) {
 281 ;;      A[10*i + j] = 0;
 282 ;;      *B++ = A[10*i + j - 99];
 283
 284 define void @banerjee5(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 285 entry:
 286   br label %for.cond1.preheader
 287
 288 ; CHECK: 'Dependence Analysis' for function 'banerjee5':
 289 ; CHECK: da analyze - none!
 290 ; CHECK: da analyze - flow [< <]!
 291 ; CHECK: da analyze - confused!
 292 ; CHECK: da analyze - none!
 293 ; CHECK: da analyze - confused!
 294 ; CHECK: da analyze - none!
 295
 296 for.cond1.preheader:                              ; preds = %entry, %for.inc7
 297   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
 298   %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
 299   br label %for.body3
 300
 301 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 302   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 303   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 304   %mul = mul nsw i64 %i.03, 10
 305   %add = add nsw i64 %mul, %j.02
 306   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 307   store i64 0, i64* %arrayidx, align 8
 308   %mul4 = mul nsw i64 %i.03, 10
 309   %add5 = add nsw i64 %mul4, %j.02
 310   %sub = add nsw i64 %add5, -99
 311   %arrayidx6 = getelementptr inbounds i64* %A, i64 %sub
 312   %0 = load i64* %arrayidx6, align 8
 313   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 314   store i64 %0, i64* %B.addr.11, align 8
 315   %inc = add nsw i64 %j.02, 1
 316   %exitcond = icmp ne i64 %inc, 10
 317   br i1 %exitcond, label %for.body3, label %for.inc7
 318
 319 for.inc7:                                         ; preds = %for.body3
 320   %scevgep = getelementptr i64* %B.addr.04, i64 10
 321   %inc8 = add nsw i64 %i.03, 1
 322   %exitcond5 = icmp ne i64 %inc8, 10
 323   br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
 324
 325 for.end9:                                         ; preds = %for.inc7
 326   ret void
 327 }
 328
 329
 330 ;;  for (long int i = 0; i < 10; i++)
 331 ;;    for (long int j = 0; j < 10; j++) {
 332 ;;      A[10*i + j] = 0;
 333 ;;      *B++ = A[10*i + j + 9];
 334
 335 define void @banerjee6(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 336 entry:
 337   br label %for.cond1.preheader
 338
 339 ; CHECK: 'Dependence Analysis' for function 'banerjee6':
 340 ; CHECK: da analyze - none!
 341 ; CHECK: da analyze - flow [=> <>]!
 342 ; CHECK: da analyze - confused!
 343 ; CHECK: da analyze - none!
 344 ; CHECK: da analyze - confused!
 345 ; CHECK: da analyze - none!
 346
 347 for.cond1.preheader:                              ; preds = %entry, %for.inc8
 348   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
 349   %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
 350   br label %for.body3
 351
 352 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 353   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 354   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 355   %mul = mul nsw i64 %i.03, 10
 356   %add = add nsw i64 %mul, %j.02
 357   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 358   store i64 0, i64* %arrayidx, align 8
 359   %mul4 = mul nsw i64 %i.03, 10
 360   %add5 = add nsw i64 %mul4, %j.02
 361   %add6 = add nsw i64 %add5, 9
 362   %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
 363   %0 = load i64* %arrayidx7, align 8
 364   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 365   store i64 %0, i64* %B.addr.11, align 8
 366   %inc = add nsw i64 %j.02, 1
 367   %exitcond = icmp ne i64 %inc, 10
 368   br i1 %exitcond, label %for.body3, label %for.inc8
 369
 370 for.inc8:                                         ; preds = %for.body3
 371   %scevgep = getelementptr i64* %B.addr.04, i64 10
 372   %inc9 = add nsw i64 %i.03, 1
 373   %exitcond5 = icmp ne i64 %inc9, 10
 374   br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
 375
 376 for.end10:                                        ; preds = %for.inc8
 377   ret void
 378 }
 379
 380
 381 ;;  for (long int i = 0; i < 10; i++)
 382 ;;    for (long int j = 0; j < 10; j++) {
 383 ;;      A[10*i + j] = 0;
 384 ;;      *B++ = A[10*i + j + 10];
 385
 386 define void @banerjee7(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 387 entry:
 388   br label %for.cond1.preheader
 389
 390 ; CHECK: 'Dependence Analysis' for function 'banerjee7':
 391 ; CHECK: da analyze - none!
 392 ; CHECK: da analyze - flow [> <=]!
 393 ; CHECK: da analyze - confused!
 394 ; CHECK: da analyze - none!
 395 ; CHECK: da analyze - confused!
 396 ; CHECK: da analyze - none!
 397
 398 for.cond1.preheader:                              ; preds = %entry, %for.inc8
 399   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
 400   %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
 401   br label %for.body3
 402
 403 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 404   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 405   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 406   %mul = mul nsw i64 %i.03, 10
 407   %add = add nsw i64 %mul, %j.02
 408   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 409   store i64 0, i64* %arrayidx, align 8
 410   %mul4 = mul nsw i64 %i.03, 10
 411   %add5 = add nsw i64 %mul4, %j.02
 412   %add6 = add nsw i64 %add5, 10
 413   %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
 414   %0 = load i64* %arrayidx7, align 8
 415   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 416   store i64 %0, i64* %B.addr.11, align 8
 417   %inc = add nsw i64 %j.02, 1
 418   %exitcond = icmp ne i64 %inc, 10
 419   br i1 %exitcond, label %for.body3, label %for.inc8
 420
 421 for.inc8:                                         ; preds = %for.body3
 422   %scevgep = getelementptr i64* %B.addr.04, i64 10
 423   %inc9 = add nsw i64 %i.03, 1
 424   %exitcond5 = icmp ne i64 %inc9, 10
 425   br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
 426
 427 for.end10:                                        ; preds = %for.inc8
 428   ret void
 429 }
 430
 431
 432 ;;  for (long int i = 0; i < 10; i++)
 433 ;;    for (long int j = 0; j < 10; j++) {
 434 ;;      A[10*i + j] = 0;
 435 ;;      *B++ = A[10*i + j + 11];
 436
 437 define void @banerjee8(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 438 entry:
 439   br label %for.cond1.preheader
 440
 441 ; CHECK: 'Dependence Analysis' for function 'banerjee8':
 442 ; CHECK: da analyze - none!
 443 ; CHECK: da analyze - flow [> <>]!
 444 ; CHECK: da analyze - confused!
 445 ; CHECK: da analyze - none!
 446 ; CHECK: da analyze - confused!
 447 ; CHECK: da analyze - none!
 448
 449 for.cond1.preheader:                              ; preds = %entry, %for.inc8
 450   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
 451   %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
 452   br label %for.body3
 453
 454 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 455   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 456   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 457   %mul = mul nsw i64 %i.03, 10
 458   %add = add nsw i64 %mul, %j.02
 459   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 460   store i64 0, i64* %arrayidx, align 8
 461   %mul4 = mul nsw i64 %i.03, 10
 462   %add5 = add nsw i64 %mul4, %j.02
 463   %add6 = add nsw i64 %add5, 11
 464   %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
 465   %0 = load i64* %arrayidx7, align 8
 466   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 467   store i64 %0, i64* %B.addr.11, align 8
 468   %inc = add nsw i64 %j.02, 1
 469   %exitcond = icmp ne i64 %inc, 10
 470   br i1 %exitcond, label %for.body3, label %for.inc8
 471
 472 for.inc8:                                         ; preds = %for.body3
 473   %scevgep = getelementptr i64* %B.addr.04, i64 10
 474   %inc9 = add nsw i64 %i.03, 1
 475   %exitcond5 = icmp ne i64 %inc9, 10
 476   br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
 477
 478 for.end10:                                        ; preds = %for.inc8
 479   ret void
 480 }
 481
 482
 483 ;;  for (long int i = 0; i < 20; i++)
 484 ;;    for (long int j = 0; j < 20; j++) {
 485 ;;      A[30*i + 500*j] = 0;
 486 ;;      *B++ = A[i - 500*j + 11];
 487
 488 define void @banerjee9(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 489 entry:
 490   br label %for.cond1.preheader
 491
 492 ; CHECK: 'Dependence Analysis' for function 'banerjee9':
 493 ; CHECK: da analyze - output [* *]!
 494 ; CHECK: da analyze - flow [<= =|<]!
 495 ; CHECK: da analyze - confused!
 496 ; CHECK: da analyze - none!
 497 ; CHECK: da analyze - confused!
 498 ; CHECK: da analyze - none!
 499
 500 for.cond1.preheader:                              ; preds = %entry, %for.inc8
 501   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
 502   %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
 503   br label %for.body3
 504
 505 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 506   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 507   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 508   %mul = mul nsw i64 %i.03, 30
 509   %mul4 = mul nsw i64 %j.02, 500
 510   %add = add nsw i64 %mul, %mul4
 511   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 512   store i64 0, i64* %arrayidx, align 8
 513   %0 = mul i64 %j.02, -500
 514   %sub = add i64 %i.03, %0
 515   %add6 = add nsw i64 %sub, 11
 516   %arrayidx7 = getelementptr inbounds i64* %A, i64 %add6
 517   %1 = load i64* %arrayidx7, align 8
 518   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 519   store i64 %1, i64* %B.addr.11, align 8
 520   %inc = add nsw i64 %j.02, 1
 521   %exitcond = icmp ne i64 %inc, 20
 522   br i1 %exitcond, label %for.body3, label %for.inc8
 523
 524 for.inc8:                                         ; preds = %for.body3
 525   %scevgep = getelementptr i64* %B.addr.04, i64 20
 526   %inc9 = add nsw i64 %i.03, 1
 527   %exitcond5 = icmp ne i64 %inc9, 20
 528   br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
 529
 530 for.end10:                                        ; preds = %for.inc8
 531   ret void
 532 }
 533
 534
 535 ;;  for (long int i = 0; i < 20; i++)
 536 ;;    for (long int j = 0; j < 20; j++) {
 537 ;;      A[i + 500*j] = 0;
 538 ;;      *B++ = A[i - 500*j + 11];
 539
 540 define void @banerjee10(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 541 entry:
 542   br label %for.cond1.preheader
 543
 544 ; CHECK: 'Dependence Analysis' for function 'banerjee10':
 545 ; CHECK: da analyze - none!
 546 ; CHECK: da analyze - flow [<> =]!
 547 ; CHECK: da analyze - confused!
 548 ; CHECK: da analyze - none!
 549 ; CHECK: da analyze - confused!
 550 ; CHECK: da analyze - none!
 551
 552 for.cond1.preheader:                              ; preds = %entry, %for.inc7
 553   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
 554   %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
 555   br label %for.body3
 556
 557 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 558   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 559   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 560   %mul = mul nsw i64 %j.02, 500
 561   %add = add nsw i64 %i.03, %mul
 562   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 563   store i64 0, i64* %arrayidx, align 8
 564   %0 = mul i64 %j.02, -500
 565   %sub = add i64 %i.03, %0
 566   %add5 = add nsw i64 %sub, 11
 567   %arrayidx6 = getelementptr inbounds i64* %A, i64 %add5
 568   %1 = load i64* %arrayidx6, align 8
 569   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 570   store i64 %1, i64* %B.addr.11, align 8
 571   %inc = add nsw i64 %j.02, 1
 572   %exitcond = icmp ne i64 %inc, 20
 573   br i1 %exitcond, label %for.body3, label %for.inc7
 574
 575 for.inc7:                                         ; preds = %for.body3
 576   %scevgep = getelementptr i64* %B.addr.04, i64 20
 577   %inc8 = add nsw i64 %i.03, 1
 578   %exitcond5 = icmp ne i64 %inc8, 20
 579   br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
 580
 581 for.end9:                                         ; preds = %for.inc7
 582   ret void
 583 }
 584
 585
 586 ;;  for (long int i = 0; i < 20; i++)
 587 ;;    for (long int j = 0; j < 20; j++) {
 588 ;;      A[300*i + j] = 0;
 589 ;;      *B++ = A[250*i - j + 11];
 590
 591 define void @banerjee11(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 592 entry:
 593   br label %for.cond1.preheader
 594
 595 ; CHECK: 'Dependence Analysis' for function 'banerjee11':
 596 ; CHECK: da analyze - none!
 597 ; CHECK: da analyze - flow [<= <>]!
 598 ; CHECK: da analyze - confused!
 599 ; CHECK: da analyze - none!
 600 ; CHECK: da analyze - confused!
 601 ; CHECK: da analyze - none!
 602
 603 for.cond1.preheader:                              ; preds = %entry, %for.inc7
 604   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
 605   %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
 606   br label %for.body3
 607
 608 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 609   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 610   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 611   %mul = mul nsw i64 %i.03, 300
 612   %add = add nsw i64 %mul, %j.02
 613   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 614   store i64 0, i64* %arrayidx, align 8
 615   %mul4 = mul nsw i64 %i.03, 250
 616   %sub = sub nsw i64 %mul4, %j.02
 617   %add5 = add nsw i64 %sub, 11
 618   %arrayidx6 = getelementptr inbounds i64* %A, i64 %add5
 619   %0 = load i64* %arrayidx6, align 8
 620   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 621   store i64 %0, i64* %B.addr.11, align 8
 622   %inc = add nsw i64 %j.02, 1
 623   %exitcond = icmp ne i64 %inc, 20
 624   br i1 %exitcond, label %for.body3, label %for.inc7
 625
 626 for.inc7:                                         ; preds = %for.body3
 627   %scevgep = getelementptr i64* %B.addr.04, i64 20
 628   %inc8 = add nsw i64 %i.03, 1
 629   %exitcond5 = icmp ne i64 %inc8, 20
 630   br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
 631
 632 for.end9:                                         ; preds = %for.inc7
 633   ret void
 634 }
 635
 636
 637 ;;  for (long int i = 0; i < 20; i++)
 638 ;;    for (long int j = 0; j < 20; j++) {
 639 ;;      A[100*i + j] = 0;
 640 ;;      *B++ = A[100*i - j + 11];
 641
 642 define void @banerjee12(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 643 entry:
 644   br label %for.cond1.preheader
 645
 646 ; CHECK: 'Dependence Analysis' for function 'banerjee12':
 647 ; CHECK: da analyze - none!
 648 ; CHECK: da analyze - flow [= <>]!
 649 ; CHECK: da analyze - confused!
 650 ; CHECK: da analyze - none!
 651 ; CHECK: da analyze - confused!
 652 ; CHECK: da analyze - none!
 653
 654 for.cond1.preheader:                              ; preds = %entry, %for.inc7
 655   %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc7 ]
 656   %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
 657   br label %for.body3
 658
 659 for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
 660   %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
 661   %B.addr.11 = phi i64* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
 662   %mul = mul nsw i64 %i.03, 100
 663   %add = add nsw i64 %mul, %j.02
 664   %arrayidx = getelementptr inbounds i64* %A, i64 %add
 665   store i64 0, i64* %arrayidx, align 8
 666   %mul4 = mul nsw i64 %i.03, 100
 667   %sub = sub nsw i64 %mul4, %j.02
 668   %add5 = add nsw i64 %sub, 11
 669   %arrayidx6 = getelementptr inbounds i64* %A, i64 %add5
 670   %0 = load i64* %arrayidx6, align 8
 671   %incdec.ptr = getelementptr inbounds i64* %B.addr.11, i64 1
 672   store i64 %0, i64* %B.addr.11, align 8
 673   %inc = add nsw i64 %j.02, 1
 674   %exitcond = icmp ne i64 %inc, 20
 675   br i1 %exitcond, label %for.body3, label %for.inc7
 676
 677 for.inc7:                                         ; preds = %for.body3
 678   %scevgep = getelementptr i64* %B.addr.04, i64 20
 679   %inc8 = add nsw i64 %i.03, 1
 680   %exitcond5 = icmp ne i64 %inc8, 20
 681   br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
 682
 683 for.end9:                                         ; preds = %for.inc7
 684   ret void
 685 }