; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; Check that phi analysis can determine the number of iterations of the
; loop to peel such that the phi nodes (other than the iteration variable)
; have their resulting values known and are thus removed by peeling the loop
; at least that many times.

; RUN: opt < %s -S -passes=loop-unroll | FileCheck %s
; RUN: opt < %s -S -passes=loop-unroll-full | FileCheck %s

; void f(float);
; void g(int);
declare void @_Z1ff(float)
declare void @_Z1gi(i32 signext)

; Check that phi analysis can handle a cast.
define void @_Z8castTestv() {
; The phis become invariant through the chain of phis, with a unary
; instruction on a loop invariant.  Check that the phis for x, a, and y
; are removed since x is based on a cast of y, which is based on a, which is
; set on the backedge.
; Consider the calls to g and f.
; First iteration: g(0), x=0, f(0.0), y=0.0, a=5.0
; Second iteration: g(0), x=0, f(0.0), y=5.0, a=5.0
; Third iteration: g(0), x=5 (requires cast), f(5.0), a=5.0
; Fourth iteration (and subsequent): g(5), x=5, f(5.0), a=5.0
; Therefore, peeling 3 times removes the phi nodes, so check for 3 peels.
;
; void castTest() {
;   int x = 0;
;   float y = 0.0;
;   float a = 0.0;
;   for(int i = 0; i <100000; ++i) {
;     g(x);
;     x = y;
;     f(y);
;     y = a;
;     a = 5.0;
;   }
; }
;
; CHECK-LABEL: @_Z8castTestv(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[FOR_BODY_PEEL_BEGIN:%.*]]
; CHECK:       for.body.peel.begin:
; CHECK-NEXT:    br label [[FOR_BODY_PEEL:%.*]]
; CHECK:       for.body.peel:
; CHECK-NEXT:    tail call void @_Z1gi(i32 noundef signext 0)
; CHECK-NEXT:    [[CONV_PEEL:%.*]] = fptosi float 0.000000e+00 to i32
; CHECK-NEXT:    tail call void @_Z1ff(float noundef 0.000000e+00)
; CHECK-NEXT:    [[INC_PEEL:%.*]] = add nuw nsw i32 0, 1
; CHECK-NEXT:    [[EXITCOND_PEEL:%.*]] = icmp ne i32 [[INC_PEEL]], 100000
; CHECK-NEXT:    br i1 [[EXITCOND_PEEL]], label [[FOR_BODY_PEEL_NEXT:%.*]], label [[FOR_COND_CLEANUP:%.*]]
; CHECK:       for.body.peel.next:
; CHECK-NEXT:    br label [[FOR_BODY_PEEL2:%.*]]
; CHECK:       for.body.peel2:
; CHECK-NEXT:    tail call void @_Z1gi(i32 noundef signext [[CONV_PEEL]])
; CHECK-NEXT:    [[CONV_PEEL3:%.*]] = fptosi float 0.000000e+00 to i32
; CHECK-NEXT:    tail call void @_Z1ff(float noundef 0.000000e+00)
; CHECK-NEXT:    [[INC_PEEL4:%.*]] = add nuw nsw i32 [[INC_PEEL]], 1
; CHECK-NEXT:    [[EXITCOND_PEEL5:%.*]] = icmp ne i32 [[INC_PEEL4]], 100000
; CHECK-NEXT:    br i1 [[EXITCOND_PEEL5]], label [[FOR_BODY_PEEL_NEXT1:%.*]], label [[FOR_COND_CLEANUP]]
; CHECK:       for.body.peel.next1:
; CHECK-NEXT:    br label [[FOR_BODY_PEEL7:%.*]]
; CHECK:       for.body.peel7:
; CHECK-NEXT:    tail call void @_Z1gi(i32 noundef signext [[CONV_PEEL3]])
; CHECK-NEXT:    [[CONV_PEEL8:%.*]] = fptosi float 5.000000e+00 to i32
; CHECK-NEXT:    tail call void @_Z1ff(float noundef 5.000000e+00)
; CHECK-NEXT:    [[INC_PEEL9:%.*]] = add nuw nsw i32 [[INC_PEEL4]], 1
; CHECK-NEXT:    [[EXITCOND_PEEL10:%.*]] = icmp ne i32 [[INC_PEEL9]], 100000
; CHECK-NEXT:    br i1 [[EXITCOND_PEEL10]], label [[FOR_BODY_PEEL_NEXT6:%.*]], label [[FOR_COND_CLEANUP]]
; CHECK:       for.body.peel.next6:
; CHECK-NEXT:    br label [[FOR_BODY_PEEL_NEXT11:%.*]]
; CHECK:       for.body.peel.next11:
; CHECK-NEXT:    br label [[ENTRY_PEEL_NEWPH:%.*]]
; CHECK:       entry.peel.newph:
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.cond.cleanup.loopexit:
; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    ret void
; CHECK:       for.body:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INC_PEEL9]], [[ENTRY_PEEL_NEWPH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[CONV_PEEL8]], [[ENTRY_PEEL_NEWPH]] ], [ 5, [[FOR_BODY]] ]
; CHECK-NEXT:    tail call void @_Z1gi(i32 noundef signext [[X]])
; CHECK-NEXT:    tail call void @_Z1ff(float noundef 5.000000e+00)
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[INC]], 100000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], !llvm.loop [[LOOP0:![0-9]+]]
;
entry:
  br label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %a = phi float [ 0.000000e+00, %entry ], [ 5.000000e+00, %for.body ]
  %y = phi float [ 0.000000e+00, %entry ], [ %a, %for.body ]
  %x = phi i32 [ 0, %entry ], [ %conv, %for.body ]
  tail call void @_Z1gi(i32 noundef signext %x)
  %conv = fptosi float %y to i32
  tail call void @_Z1ff(float noundef %y)
  %inc = add nuw nsw i32 %i, 1
  %exitcond = icmp ne i32 %inc, 100000
  br i1 %exitcond, label %for.body, label %for.cond.cleanup
}

; Check that phi analysis can handle a binary operator.
define void @_Z6binaryv() {
; The phis become invariant through the chain of phis, with a unary
; instruction on a loop invariant.  Check that the phis for x, a, and y
; are removed since x is based on y, which is based on a, which is based
; on a binary add of a phi and a constant.
; Consider the calls to g:
; First iteration: g(0), x=0, g(0), y=1, a=5
; Second iteration: g(0), x=1, g(5), y=6(binary operator), a=5
; Third iteration: g(1), x=6, g(5), y=6, a=5
; Fourth iteration (and subsequent): g(6), x=6, g(5), y=6, a=5
; Therefore, peeling 3 times removes the phi nodes.
;
; void g(int);
; void binary() {
;   int x = 0;
;   int y = 0;
;   int a = 0;
;   for(int i = 0; i <100000; ++i) {
;     g(x);
;     x = y;
;     g(a);
;     y = a + 1;
;     a = 5;
;   }
; }
;
; CHECK-LABEL: @_Z6binaryv(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[FOR_BODY_PEEL_BEGIN:%.*]]
; CHECK:       for.body.peel.begin:
; CHECK-NEXT:    br label [[FOR_BODY_PEEL:%.*]]
; CHECK:       for.body.peel:
; CHECK-NEXT:    tail call void @_Z1gi(i32 signext 0)
; CHECK-NEXT:    tail call void @_Z1gi(i32 signext 0)
; CHECK-NEXT:    [[ADD_PEEL:%.*]] = add nuw nsw i32 0, 1
; CHECK-NEXT:    [[INC_PEEL:%.*]] = add nuw nsw i32 0, 1
; CHECK-NEXT:    [[EXITCOND_PEEL:%.*]] = icmp eq i32 [[INC_PEEL]], 100000
; CHECK-NEXT:    br i1 [[EXITCOND_PEEL]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY_PEEL_NEXT:%.*]]
; CHECK:       for.body.peel.next:
; CHECK-NEXT:    br label [[FOR_BODY_PEEL2:%.*]]
; CHECK:       for.body.peel2:
; CHECK-NEXT:    tail call void @_Z1gi(i32 signext 0)
; CHECK-NEXT:    tail call void @_Z1gi(i32 signext 5)
; CHECK-NEXT:    [[INC_PEEL4:%.*]] = add nuw nsw i32 [[INC_PEEL]], 1
; CHECK-NEXT:    [[EXITCOND_PEEL5:%.*]] = icmp eq i32 [[INC_PEEL4]], 100000
; CHECK-NEXT:    br i1 [[EXITCOND_PEEL5]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY_PEEL_NEXT1:%.*]]
; CHECK:       for.body.peel.next1:
; CHECK-NEXT:    br label [[FOR_BODY_PEEL7:%.*]]
; CHECK:       for.body.peel7:
; CHECK-NEXT:    tail call void @_Z1gi(i32 signext [[ADD_PEEL]])
; CHECK-NEXT:    tail call void @_Z1gi(i32 signext 5)
; CHECK-NEXT:    [[INC_PEEL9:%.*]] = add nuw nsw i32 [[INC_PEEL4]], 1
; CHECK-NEXT:    [[EXITCOND_PEEL10:%.*]] = icmp eq i32 [[INC_PEEL9]], 100000
; CHECK-NEXT:    br i1 [[EXITCOND_PEEL10]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY_PEEL_NEXT6:%.*]]
; CHECK:       for.body.peel.next6:
; CHECK-NEXT:    br label [[FOR_BODY_PEEL_NEXT11:%.*]]
; CHECK:       for.body.peel.next11:
; CHECK-NEXT:    br label [[ENTRY_PEEL_NEWPH:%.*]]
; CHECK:       entry.peel.newph:
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.cond.cleanup.loopexit:
; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    ret void
; CHECK:       for.body:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INC_PEEL9]], [[ENTRY_PEEL_NEWPH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
; CHECK-NEXT:    tail call void @_Z1gi(i32 signext 6)
; CHECK-NEXT:    tail call void @_Z1gi(i32 signext 5)
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 100000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], label [[FOR_BODY]], !llvm.loop [[LOOP2:![0-9]+]]
;
entry:
  br label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %a = phi i32 [ 0, %entry ], [ 5, %for.body ]
  %y = phi i32 [ 0, %entry ], [ %add, %for.body ]
  %x = phi i32 [ 0, %entry ], [ %y, %for.body ]
  tail call void @_Z1gi(i32 signext %x)
  tail call void @_Z1gi(i32 signext %a)
  %add = add nuw nsw i32 %a, 1
  %inc = add nuw nsw i32 %i, 1
  %exitcond = icmp eq i32 %inc, 100000
  br i1 %exitcond, label %for.cond.cleanup, label %for.body
}