; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5
; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 \
; RUN: | FileCheck %s

; The dependence test does not handle array accesses with difference between array accesses
; is not a multiple of the array element size.

; In this test, the element size is i32 = 4 bytes and the difference between the
; load and the store is 2 bytes.

define i32 @alias_with_different_offsets(ptr nocapture %A) {
; CHECK-LABEL: 'alias_with_different_offsets'
; CHECK-NEXT:  Src: store i32 2, ptr %arrayidx, align 1 --> Dst: store i32 2, ptr %arrayidx, align 1
; CHECK-NEXT:    da analyze - confused!
; CHECK-NEXT:  Src: store i32 2, ptr %arrayidx, align 1 --> Dst: %0 = load i32, ptr %A, align 1
; CHECK-NEXT:    da analyze - confused!
; CHECK-NEXT:  Src: %0 = load i32, ptr %A, align 1 --> Dst: %0 = load i32, ptr %A, align 1
; CHECK-NEXT:    da analyze - none!
;
entry:
  %arrayidx = getelementptr inbounds i8, ptr %A, i64 2
  store i32 2, ptr %arrayidx, align 1
  %0 = load i32, ptr %A, align 1
  ret i32 %0
}

define i32 @alias_with_parametric_offset(ptr nocapture %A, i64 %n) {
; CHECK-LABEL: 'alias_with_parametric_offset'
; CHECK-NEXT:  Src: store i32 2, ptr %arrayidx, align 1 --> Dst: store i32 2, ptr %arrayidx, align 1
; CHECK-NEXT:    da analyze - none!
; CHECK-NEXT:  Src: store i32 2, ptr %arrayidx, align 1 --> Dst: %0 = load i32, ptr %A, align 1
; CHECK-NEXT:    da analyze - flow [|<]!
; CHECK-NEXT:    Runtime Assumptions:
; CHECK-NEXT:    Equal predicate: (zext i2 (trunc i64 %n to i2) to i64) == 0
; CHECK-NEXT:  Src: %0 = load i32, ptr %A, align 1 --> Dst: %0 = load i32, ptr %A, align 1
; CHECK-NEXT:    da analyze - none!
; CHECK-NEXT:  Runtime Assumptions:
; CHECK-NEXT:  Equal predicate: (zext i2 (trunc i64 %n to i2) to i64) == 0
;
entry:
  %arrayidx = getelementptr inbounds i8, ptr %A, i64 %n
  store i32 2, ptr %arrayidx, align 1
  %0 = load i32, ptr %A, align 1
  ret i32 %0
}

define i32 @alias_with_parametric_expr(ptr nocapture %A, i64 %n, i64 %m) {
; CHECK-LABEL: 'alias_with_parametric_expr'
; CHECK-NEXT:  Src: store i32 2, ptr %arrayidx, align 1 --> Dst: store i32 2, ptr %arrayidx, align 1
; CHECK-NEXT:    da analyze - none!
; CHECK-NEXT:  Src: store i32 2, ptr %arrayidx, align 1 --> Dst: %0 = load i32, ptr %arrayidx1, align 1
; CHECK-NEXT:    da analyze - flow [|<]!
; CHECK-NEXT:    Runtime Assumptions:
; CHECK-NEXT:    Equal predicate: (zext i2 ((trunc i64 %m to i2) + (-2 * (trunc i64 %n to i2))) to i64) == 0
; CHECK-NEXT:    Equal predicate: (zext i2 (-2 + (trunc i64 %m to i2)) to i64) == 0
; CHECK-NEXT:  Src: %0 = load i32, ptr %arrayidx1, align 1 --> Dst: %0 = load i32, ptr %arrayidx1, align 1
; CHECK-NEXT:    da analyze - none!
; CHECK-NEXT:  Runtime Assumptions:
; CHECK-NEXT:  Equal predicate: (zext i2 ((trunc i64 %m to i2) + (-2 * (trunc i64 %n to i2))) to i64) == 0
; CHECK-NEXT:  Equal predicate: (zext i2 (-2 + (trunc i64 %m to i2)) to i64) == 0
;
entry:
  %mul = mul nsw i64 %n, 10
  %add = add nsw i64 %mul, %m
  %arrayidx = getelementptr inbounds i8, ptr %A, i64 %add
  store i32 2, ptr %arrayidx, align 1

  %add1 = add nsw i64 %m, 42
  %arrayidx1 = getelementptr inbounds i8, ptr %A, i64 %add1
  %0 = load i32, ptr %arrayidx1, align 1
  ret i32 %0
}

define i32 @gep_i8_vs_i32(ptr nocapture %A, i64 %n, i64 %m) {
; CHECK-LABEL: 'gep_i8_vs_i32'
; CHECK-NEXT:  Src: store i32 42, ptr %arrayidx0, align 1 --> Dst: store i32 42, ptr %arrayidx0, align 1
; CHECK-NEXT:    da analyze - none!
; CHECK-NEXT:  Src: store i32 42, ptr %arrayidx0, align 1 --> Dst: store i32 42, ptr %arrayidx1, align 4
; CHECK-NEXT:    da analyze - output [|<]!
; CHECK-NEXT:    Runtime Assumptions:
; CHECK-NEXT:    Equal predicate: (zext i2 (trunc i64 %n to i2) to i64) == 0
; CHECK-NEXT:  Src: store i32 42, ptr %arrayidx1, align 4 --> Dst: store i32 42, ptr %arrayidx1, align 4
; CHECK-NEXT:    da analyze - none!
; CHECK-NEXT:  Runtime Assumptions:
; CHECK-NEXT:  Equal predicate: (zext i2 (trunc i64 %n to i2) to i64) == 0
;
entry:
  %arrayidx0 = getelementptr inbounds i8, ptr %A, i64 %n
  store i32 42, ptr %arrayidx0, align 1

  %arrayidx1 = getelementptr inbounds i32, ptr %A, i64 %m
  store i32 42, ptr %arrayidx1, align 4
  ret i32 0
}

define void @linearized_accesses(i64 %n, i64 %m, i64 %o, ptr %A) {
; CHECK-LABEL: 'linearized_accesses'
; CHECK-NEXT:  Src: store i32 1, ptr %idx0, align 4 --> Dst: store i32 1, ptr %idx0, align 4
; CHECK-NEXT:    da analyze - output [* * *]!
; CHECK-NEXT:  Src: store i32 1, ptr %idx0, align 4 --> Dst: store i32 1, ptr %idx1, align 4
; CHECK-NEXT:    da analyze - output [* * *|<]!
; CHECK-NEXT:  Src: store i32 1, ptr %idx1, align 4 --> Dst: store i32 1, ptr %idx1, align 4
; CHECK-NEXT:    da analyze - none!
;
entry:
  br label %for.i

for.i:
  %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
  br label %for.j

for.j:
  %j = phi i64 [ 0, %for.i ], [ %j.inc, %for.j.inc ]
  br label %for.k

for.k:
  %k = phi i64 [ 0, %for.j ], [ %k.inc, %for.k.inc ]
  %subscript0 = mul i64 %i, %m
  %subscript1 = add i64 %j, %subscript0
  %subscript2 = mul i64 %subscript1, %o
  %subscript3 = add i64 %subscript2, %k
  %idx0 = getelementptr inbounds i64, ptr %A, i64 %subscript3  ; (i64*)(A) + i*m*o + j*o + k
  store i32 1, ptr %idx0
  %idx1 = getelementptr inbounds i32, ptr %A, i64 %subscript3  ; (i32*)(A) + i*m*o + j*o + k
  store i32 1, ptr %idx1
  br label %for.k.inc

for.k.inc:
  %k.inc = add nsw i64 %k, 1
  %k.exitcond = icmp eq i64 %k.inc, %o
  br i1 %k.exitcond, label %for.j.inc, label %for.k

for.j.inc:
  %j.inc = add nsw i64 %j, 1
  %j.exitcond = icmp eq i64 %j.inc, %m
  br i1 %j.exitcond, label %for.i.inc, label %for.j

for.i.inc:
  %i.inc = add nsw i64 %i, 1
  %i.exitcond = icmp eq i64 %i.inc, %n
  br i1 %i.exitcond, label %end, label %for.i

end:
  ret void
}

define void @multidim_accesses(ptr %A) {
; CHECK-LABEL: 'multidim_accesses'
; CHECK-NEXT:  Src: store i32 1, ptr %idx0, align 4 --> Dst: store i32 1, ptr %idx0, align 4
; CHECK-NEXT:    da analyze - none!
; CHECK-NEXT:  Src: store i32 1, ptr %idx0, align 4 --> Dst: store i32 1, ptr %idx1, align 4
; CHECK-NEXT:    da analyze - consistent output [0 0 0|<]!
; CHECK-NEXT:  Src: store i32 1, ptr %idx1, align 4 --> Dst: store i32 1, ptr %idx1, align 4
; CHECK-NEXT:    da analyze - none!
;
; FIXME: the dependence distance is not constant. Distance vector should be [* * *|<]!
; for (i = 0; i < 256; i++)
;   for (j = 0; j < 256; j++)
;      for (k = 0; k < 256; k++) {
;         int *idx0 = (int *)((long long *)(A) + 256*256*i + 256*j + k);
;         *idx0 = 1;
;         int *idx1 = (int *)((int *)(A) + 256*256*i + 256*j + k);
;         *idx1 = 1;
;      }
entry:
  br label %for.i

for.i:
  %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
  br label %for.j

for.j:
  %j = phi i64 [ 0, %for.i ], [ %j.inc, %for.j.inc ]
  br label %for.k

for.k:
  %k = phi i64 [ 0, %for.j ], [ %k.inc, %for.k.inc ]
  %idx0 = getelementptr inbounds [256 x [256 x [256 x i64]]], ptr %A, i64 0, i64 %i, i64 %j, i64 %k
  store i32 1, ptr %idx0
  %idx1 = getelementptr inbounds [256 x [256 x [256 x i32]]], ptr %A, i64 0, i64 %i, i64 %j, i64 %k
  store i32 1, ptr %idx1
  br label %for.k.inc

for.k.inc:
  %k.inc = add nsw i64 %k, 1
  %k.exitcond = icmp eq i64 %k.inc, 256
  br i1 %k.exitcond, label %for.j.inc, label %for.k

for.j.inc:
  %j.inc = add nsw i64 %j, 1
  %j.exitcond = icmp eq i64 %j.inc, 256
  br i1 %j.exitcond, label %for.i.inc, label %for.j

for.i.inc:
  %i.inc = add nsw i64 %i, 1
  %i.exitcond = icmp eq i64 %i.inc, 256
  br i1 %i.exitcond, label %end, label %for.i

end:
  ret void
}

; for (int i = 0; i < 256; i++)
;   for (int j = 0; j < 256; j++)
;      for (int k = 0; k < 256; k++) {
;        int *idx = (int *)((int *)(A) + 256*256*i + 256*j + k);
;        *((long long *)idx) = 1;
;      }
;
; There are loop-carried dependencies across iterations in the store.
define void @multidim_accesses2(ptr %A) {
; CHECK-LABEL: 'multidim_accesses2'
; CHECK-NEXT:  Src: store i64 1, ptr %idx, align 4 --> Dst: store i64 1, ptr %idx, align 4
; CHECK-NEXT:    da analyze - confused!
;
entry:
  br label %for.i

for.i:
  %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
  br label %for.j

for.j:
  %j = phi i64 [ 0, %for.i ], [ %j.inc, %for.j.inc ]
  br label %for.k

for.k:
  %k = phi i64 [ 0, %for.j ], [ %k.inc, %for.k ]
  %idx = getelementptr inbounds [256 x [256 x [256 x i32]]], ptr %A, i64 0, i64 %i, i64 %j, i64 %k
  store i64 1, ptr %idx
  %k.inc = add nsw i64 %k, 1
  %k.exitcond = icmp eq i64 %k.inc, 256
  br i1 %k.exitcond, label %for.j.inc, label %for.k

for.j.inc:
  %j.inc = add nsw i64 %j, 1
  %j.exitcond = icmp eq i64 %j.inc, 256
  br i1 %j.exitcond, label %for.i.inc, label %for.j

for.i.inc:
  %i.inc = add nsw i64 %i, 1
  %i.exitcond = icmp eq i64 %i.inc, 256
  br i1 %i.exitcond, label %end, label %for.i

end:
  ret void
}