; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -S -passes='loop(loop-rotate<header-duplication>)' %s | FileCheck %s --check-prefixes=CHECK,NO-EXIT-COUNT
; RUN: opt -S -passes='loop(loop-rotate<header-duplication;check-exit-count>)' %s | FileCheck %s --check-prefixes=CHECK,EXIT-COUNT

; Computable header exit, data-dependent latch exit. Rotated with check-exit-count.
define ptr @search_loop(ptr %begin, ptr %end, i8 %val) {
; NO-EXIT-COUNT-LABEL: @search_loop(
; NO-EXIT-COUNT-NEXT:  entry:
; NO-EXIT-COUNT-NEXT:    [[CMP_ENTRY:%.*]] = icmp eq ptr [[BEGIN:%.*]], [[END:%.*]]
; NO-EXIT-COUNT-NEXT:    br i1 [[CMP_ENTRY]], label [[EXIT:%.*]], label [[FOR_COND_PREHEADER:%.*]]
; NO-EXIT-COUNT:       for.cond.preheader:
; NO-EXIT-COUNT-NEXT:    br label [[FOR_COND:%.*]]
; NO-EXIT-COUNT:       for.cond:
; NO-EXIT-COUNT-NEXT:    [[PTR:%.*]] = phi ptr [ [[PTR_DEC:%.*]], [[FOR_BODY:%.*]] ], [ [[END]], [[FOR_COND_PREHEADER]] ]
; NO-EXIT-COUNT-NEXT:    [[PTR_DEC]] = getelementptr inbounds i8, ptr [[PTR]], i64 -1
; NO-EXIT-COUNT-NEXT:    [[CMP_END:%.*]] = icmp eq ptr [[PTR_DEC]], [[BEGIN]]
; NO-EXIT-COUNT-NEXT:    br i1 [[CMP_END]], label [[NOT_FOUND:%.*]], label [[FOR_BODY]]
; NO-EXIT-COUNT:       for.body:
; NO-EXIT-COUNT-NEXT:    [[LOAD:%.*]] = load i8, ptr [[PTR_DEC]], align 1
; NO-EXIT-COUNT-NEXT:    [[CMP_VAL:%.*]] = icmp eq i8 [[LOAD]], [[VAL:%.*]]
; NO-EXIT-COUNT-NEXT:    br i1 [[CMP_VAL]], label [[FOUND:%.*]], label [[FOR_COND]]
; NO-EXIT-COUNT:       found:
; NO-EXIT-COUNT-NEXT:    [[PTR_DEC_LCSSA1:%.*]] = phi ptr [ [[PTR_DEC]], [[FOR_BODY]] ]
; NO-EXIT-COUNT-NEXT:    ret ptr [[PTR_DEC_LCSSA1]]
; NO-EXIT-COUNT:       not.found:
; NO-EXIT-COUNT-NEXT:    br label [[EXIT]]
; NO-EXIT-COUNT:       exit:
; NO-EXIT-COUNT-NEXT:    ret ptr [[END]]
;
; EXIT-COUNT-LABEL: @search_loop(
; EXIT-COUNT-NEXT:  entry:
; EXIT-COUNT-NEXT:    [[CMP_ENTRY:%.*]] = icmp eq ptr [[BEGIN:%.*]], [[END:%.*]]
; EXIT-COUNT-NEXT:    br i1 [[CMP_ENTRY]], label [[EXIT:%.*]], label [[FOR_COND_PREHEADER:%.*]]
; EXIT-COUNT:       for.cond.preheader:
; EXIT-COUNT-NEXT:    [[PTR_DEC2:%.*]] = getelementptr inbounds i8, ptr [[END]], i64 -1
; EXIT-COUNT-NEXT:    [[CMP_END3:%.*]] = icmp eq ptr [[PTR_DEC2]], [[BEGIN]]
; EXIT-COUNT-NEXT:    br i1 [[CMP_END3]], label [[NOT_FOUND:%.*]], label [[FOR_BODY_LR_PH:%.*]]
; EXIT-COUNT:       for.body.lr.ph:
; EXIT-COUNT-NEXT:    br label [[FOR_BODY:%.*]]
; EXIT-COUNT:       for.cond:
; EXIT-COUNT-NEXT:    [[PTR:%.*]] = phi ptr [ [[PTR_DEC4:%.*]], [[FOR_BODY]] ]
; EXIT-COUNT-NEXT:    [[PTR_DEC:%.*]] = getelementptr inbounds i8, ptr [[PTR]], i64 -1
; EXIT-COUNT-NEXT:    [[CMP_END:%.*]] = icmp eq ptr [[PTR_DEC]], [[BEGIN]]
; EXIT-COUNT-NEXT:    br i1 [[CMP_END]], label [[FOR_COND_NOT_FOUND_CRIT_EDGE:%.*]], label [[FOR_BODY]]
; EXIT-COUNT:       for.body:
; EXIT-COUNT-NEXT:    [[PTR_DEC4]] = phi ptr [ [[PTR_DEC2]], [[FOR_BODY_LR_PH]] ], [ [[PTR_DEC]], [[FOR_COND:%.*]] ]
; EXIT-COUNT-NEXT:    [[LOAD:%.*]] = load i8, ptr [[PTR_DEC4]], align 1
; EXIT-COUNT-NEXT:    [[CMP_VAL:%.*]] = icmp eq i8 [[LOAD]], [[VAL:%.*]]
; EXIT-COUNT-NEXT:    br i1 [[CMP_VAL]], label [[FOUND:%.*]], label [[FOR_COND]]
; EXIT-COUNT:       found:
; EXIT-COUNT-NEXT:    [[PTR_DEC_LCSSA1:%.*]] = phi ptr [ [[PTR_DEC4]], [[FOR_BODY]] ]
; EXIT-COUNT-NEXT:    ret ptr [[PTR_DEC_LCSSA1]]
; EXIT-COUNT:       for.cond.not.found_crit_edge:
; EXIT-COUNT-NEXT:    br label [[NOT_FOUND]]
; EXIT-COUNT:       not.found:
; EXIT-COUNT-NEXT:    br label [[EXIT]]
; EXIT-COUNT:       exit:
; EXIT-COUNT-NEXT:    ret ptr [[END]]
;
entry:
  %cmp.entry = icmp eq ptr %begin, %end
  br i1 %cmp.entry, label %exit, label %for.cond

for.cond:
  %ptr = phi ptr [ %end, %entry ], [ %ptr.dec, %for.body ]
  %ptr.dec = getelementptr inbounds i8, ptr %ptr, i64 -1
  %cmp.end = icmp eq ptr %ptr.dec, %begin
  br i1 %cmp.end, label %not.found, label %for.body

for.body:
  %load = load i8, ptr %ptr.dec, align 1
  %cmp.val = icmp eq i8 %load, %val
  br i1 %cmp.val, label %found, label %for.cond

found:
  ret ptr %ptr.dec

not.found:
  br label %exit

exit:
  ret ptr %end
}

; Both exits are memory-dependent (not computable). Not rotated.
define i32 @both_mem_dependent(ptr %p, ptr %q, i32 %n) {
; CHECK-LABEL: @both_mem_dependent(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BODY:%.*]] ]
; CHECK-NEXT:    [[LOAD1:%.*]] = load i32, ptr [[P:%.*]], align 4
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[LOAD1]], 0
; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT1:%.*]], label [[BODY]]
; CHECK:       body:
; CHECK-NEXT:    [[LOAD2:%.*]] = load i32, ptr [[Q:%.*]], align 4
; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[LOAD2]], 0
; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
; CHECK-NEXT:    br i1 [[CMP2]], label [[EXIT2:%.*]], label [[LOOP]]
; CHECK:       exit1:
; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
; CHECK:       exit2:
; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BODY]] ]
; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
;
entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %body ]
  %load1 = load i32, ptr %p, align 4
  %cmp1 = icmp eq i32 %load1, 0
  br i1 %cmp1, label %exit1, label %body

body:
  %load2 = load i32, ptr %q, align 4
  %cmp2 = icmp eq i32 %load2, 0
  %iv.next = add i32 %iv, 1
  br i1 %cmp2, label %exit2, label %loop

exit1:
  ret i32 %iv

exit2:
  ret i32 %iv
}

; Latch is unconditional, already properly structured.
define void @already_rotated(ptr %p, i32 %n) {
; CHECK-LABEL: @already_rotated(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    store i32 [[IV]], ptr [[P:%.*]], align 4
; CHECK-NEXT:    [[IV_NEXT]] = add nuw i32 [[IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[IV_NEXT]], [[N:%.*]]
; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[LOOP]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;
entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  store i32 %iv, ptr %p, align 4
  %iv.next = add nuw i32 %iv, 1
  %cmp = icmp eq i32 %iv.next, %n
  br i1 %cmp, label %exit, label %loop

exit:
  ret void
}