test/Analysis/DependenceAnalysis/GCD.ll

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