; RUN: opt -passes=loop-unroll -enable-peeling-for-iv -disable-output \
; RUN:     -pass-remarks-output=- %s | FileCheck %s
; RUN: opt -passes=loop-unroll-full -enable-peeling-for-iv -disable-output \
; RUN:     -pass-remarks-output=- %s | FileCheck %s

; void g(int);
declare void @g(i32)

; Check that phi analysis can handle a binary operator with an addition or a
; subtraction on loop-invariants or IVs. In the following case, the phis for x,
; y, a, and b become IVs by peeling.
;
;
; void g(int);
; void binary() {
;   int x = 0;
;   int y = 0;
;   int a = 42;
;   int b = 314;
;   for(int i = 0; i <100000; ++i) {
;     g(x);
;     g(b);
;     x = y;
;     y = a + 1;
;     a = i - 2;
;     b = i + a;
;   }
; }
;
;
; Consider the calls to g:
;
;                |   i |    g(x) |     g(b) |   x |   y |   a |     b |
; ---------------|-----|---------|----------|-----|-----|-----|-------|
;  1st iteration |   0 |    g(0) |   g(314) |   0 |  43 |  -2 |    -2 |
;  2nd iteration |   1 |    g(0) |    g(-2) |  43 |  -1 |  -1 |     0 |
;  3rd iteration |   2 |   g(43) |     g(0) |  -1 |   0 |   0 |     2 |
;  4th iteration |   3 |   g(-1) |     g(2) |   0 |   1 |   1 |     4 |
;  5th iteration |   4 |    g(0) |     g(4) |   1 |   2 |   2 |     6 |
; i-th iteration |   i |  g(i-5) | g(2*i-4) | i-4 | i-3 | i-2 | 2*i-4 |
;
; After the 4th iteration, the arguments to g become IVs, so peeling 3 times
; converts all PHIs into IVs.
;

; CHECK:      --- !Passed
; CHECK-NEXT: Pass:            loop-unroll
; CHECK-NEXT: Name:            Peeled
; CHECK-NEXT: Function:        binary_induction
; CHECK-NEXT: Args:
; CHECK-NEXT:   - String:          ' peeled loop by '
; CHECK-NEXT:   - PeelCount:       '3'
; CHECK-NEXT:   - String:          ' iterations'
; CHECK-NEXT: ...
define void @binary_induction() {
entry:
  br label %for.body

exit:
  ret void

for.body:
  %i = phi i32 [ 0, %entry ], [ %i.next, %for.body ]
  %x = phi i32 [ 0, %entry ], [ %y, %for.body ]
  %y = phi i32 [ 0, %entry ], [ %y.next, %for.body ]
  %a = phi i32 [ 42, %entry ], [ %a.next, %for.body ]
  %b = phi i32 [ 314, %entry ], [ %b.next, %for.body ]
  tail call void @g(i32 %x)
  tail call void @g(i32 %b)
  %i.next = add i32 %i, 1
  %y.next = add i32 %a, 1
  %a.next = sub i32 %i, 2
  %b.next = add i32 %i, %a
  %cmp = icmp ne i32 %i.next, 100000
  br i1 %cmp, label %for.body, label %exit
}

; Check that peeling works fine in the following case. This is based on TSVC
; s291, where peeling 1 time makes the variable im an IV so we can vectorize
; the loop.
;
; #define N 100
; void f(float * restrict a, float * restrict b) {
;   int im = N - 1;
;   for (int i = 0; i < N; i++) {
;     a[i] = b[i] + b[im];
;     im = i;
;   }
; }
;

; CHECK:      --- !Passed
; CHECK-NEXT: Pass:            loop-unroll
; CHECK-NEXT: Name:            Peeled
; CHECK-NEXT: Function:        tsvc_s291
; CHECK-NEXT: Args:
; CHECK-NEXT:   - String:          ' peeled loop by '
; CHECK-NEXT:   - PeelCount:       '1'
; CHECK-NEXT:   - String:          ' iterations'
; CHECK-NEXT: ...
define void @tsvc_s291(ptr noalias %a, ptr noalias %b) {
entry:
  br label %for.body

for.body:
  %i = phi i32 [0, %entry], [ %i.next, %for.body ]
  %im = phi i32 [ 99, %entry ], [ %i, %for.body ]
  %a.idx = getelementptr inbounds float, ptr %a, i32 %i
  %b.idx.0 = getelementptr inbounds float, ptr %b, i32 %i
  %b.idx.1 = getelementptr inbounds float, ptr %b, i32 %im
  %lhs = load float, ptr %b.idx.0, align 4
  %rhs = load float, ptr %b.idx.1, align 4
  %sum = fadd float %lhs, %rhs
  store float %sum, ptr %a.idx, align 4
  %i.next = add i32 %i, 1
  %cmp = icmp ne i32 %i.next, 100
  br i1 %cmp, label %for.body, label %exit

exit:
  ret void
}

; Check that the unnecessary peeling occurs in the following case. The cause is
; that the analyzer determines a casted IV as a non-IV.
;
; for (unsigned int i=0; i<10000; i++)
;   a[(unsigned long)j] = 10;
;

; CHECK:      --- !Passed
; CHECK-NEXT: Pass:            loop-unroll
; CHECK-NEXT: Name:            Peeled
; CHECK-NEXT: Function:        induction_undesirable_peel1
; CHECK-NEXT: Args:
; CHECK-NEXT:   - String:          ' peeled loop by '
; CHECK-NEXT:   - PeelCount:       '1'
; CHECK-NEXT:   - String:          ' iterations'
; CHECK-NEXT: ...
define void @induction_undesirable_peel1(ptr %a) {
entry:
  br label %for.body

for.body:
  %conv = phi i64 [ 0, %entry ], [ %conv.next, %for.body ]
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %for.body ]
  %arrayidx = getelementptr inbounds nuw i32, ptr %a, i64 %conv
  store i32 10, ptr %arrayidx, align 4
  %iv.next = add nsw nuw i32 %iv, 1
  %conv.next = zext i32 %iv.next to i64
  %cmp = icmp ugt i64 10000, %conv.next
  br i1 %cmp, label %for.body, label %exit

exit:
  ret void
}

; Check that the unnecessary peeling occurs in the following case. The analyzer
; cannot detect that the difference between the initial value of %i and %j is
; equal to the step value of the %i.
;
; int j = 0;
; for (int i=1; i<N; i++) {
;   a[j] = 10;
;   j = i;
; }

; CHECK:      --- !Passed
; CHECK-NEXT: Pass:            loop-unroll
; CHECK-NEXT: Name:            Peeled
; CHECK-NEXT: Function:        induction_undesirable_peel2
; CHECK-NEXT: Args:
; CHECK-NEXT:   - String:          ' peeled loop by '
; CHECK-NEXT:   - PeelCount:       '1'
; CHECK-NEXT:   - String:          ' iterations'
; CHECK-NEXT: ...
define void @induction_undesirable_peel2(ptr %a) {
entry:
  br label %for.body

for.body:
  %i = phi i32 [ 1, %entry ], [ %i.next, %for.body ]
  %j = phi i32 [ 0, %entry ], [ %i, %for.body ]
  %arrayidx = getelementptr i32, ptr %a, i32 %j
  store i32 10, ptr %arrayidx, align 4
  %i.next = add i32 %i, 1
  %cmp = icmp slt i32 %i, 10000
  br i1 %cmp, label %for.body, label %exit

exit:
  ret void
}

; Check that phi analysis can handle a binary operator with an addition or a
; subtraction on loop-invariants or IVs. In the following case, the phis for x,
; y, a, and b become IVs by peeling.
;
;
; void g(int);
; void binary() {
;   int x = 2;
;   for(int i = 0; i <100000; ++i) {
;     g(x);
;     tmp = i - 2;
;     x = i - tmp;
;   }
; }
;
;
; Consider the calls to g:
;
;                | i | g(x) | tmp | x |
; ---------------|---|------|-----|---|
;  1st iteration | 0 | g(2) |  -2 | 2 |
;  2nd iteration | 1 | g(2) |  -1 | 2 |
;  3rd iteration | 2 | g(2) |   0 | 2 |
;  4th iteration | 3 | g(2) |   1 | 2 |
;
; In this case, the value of x is always 2. However, the analyzer recognizes
; the expression "i - tmp" as an IV.
;

; CHECK:      --- !Passed
; CHECK-NEXT: Pass:            loop-unroll
; CHECK-NEXT: Name:            Peeled
; CHECK-NEXT: Function:        induction_undesirable_peel3
; CHECK-NEXT: Args:
; CHECK-NEXT:   - String:          ' peeled loop by '
; CHECK-NEXT:   - PeelCount:       '1'
; CHECK-NEXT:   - String:          ' iterations'
; CHECK-NEXT: ...
define void @induction_undesirable_peel3() {
entry:
  br label %for.body

exit:
  ret void

for.body:
  %i = phi i32 [ 0, %entry ], [ %i.next, %for.body ]
  %x = phi i32 [ 0, %entry ], [ %x.next, %for.body ]
  tail call void @g(i32 %x)
  %tmp = sub i32 %i, 2
  %x.next = sub i32 %i, %tmp
  %i.next = add i32 %i, 1
  %cmp = icmp ne i32 %i.next, 100000
  br i1 %cmp, label %for.body, label %exit
}