; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 4
; REQUIRES: asserts
; RUN: opt -S -passes=licm -ipt-expensive-asserts=true < %s | FileCheck %s

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

declare void @f() nounwind
declare void @llvm.experimental.guard(i1,...)

; constant fold on first ieration
define i32 @test1(ptr noalias nocapture readonly %a) nounwind uwtable {
; CHECK-LABEL: define i32 @test1(
; CHECK-SAME: ptr noalias readonly captures(none) [[A:%.*]]) #[[ATTR1:[0-9]+]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[CONTINUE:%.*]] ]
; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[CONTINUE]] ]
; CHECK-NEXT:    [[R_CHK:%.*]] = icmp ult i32 [[IV]], 2000
; CHECK-NEXT:    br i1 [[R_CHK]], label [[CONTINUE]], label [[FAIL:%.*]]
; CHECK:       continue:
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ]
; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
; CHECK:       fail:
; CHECK-NEXT:    call void @f()
; CHECK-NEXT:    ret i32 -1
;
entry:
  br label %for.body

for.body:
  %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
  %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
  %r.chk = icmp ult i32 %iv, 2000
  br i1 %r.chk, label %continue, label %fail
continue:
  %i1 = load i32, ptr %a, align 4
  %add = add nsw i32 %i1, %acc
  %inc = add nuw nsw i32 %iv, 1
  %exitcond = icmp eq i32 %inc, 1000
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret i32 %add

fail:
  call void @f()
  ret i32 -1
}

; Same as test1, but with a floating point IR and fcmp
define i32 @test_fcmp(ptr noalias nocapture readonly %a) nounwind uwtable {
; CHECK-LABEL: define i32 @test_fcmp(
; CHECK-SAME: ptr noalias readonly captures(none) [[A:%.*]]) #[[ATTR1]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[IV:%.*]] = phi float [ 0.000000e+00, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[CONTINUE:%.*]] ]
; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[CONTINUE]] ]
; CHECK-NEXT:    [[R_CHK:%.*]] = fcmp olt float [[IV]], 2.000000e+03
; CHECK-NEXT:    br i1 [[R_CHK]], label [[CONTINUE]], label [[FAIL:%.*]]
; CHECK:       continue:
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
; CHECK-NEXT:    [[INC]] = fadd float [[IV]], 1.000000e+00
; CHECK-NEXT:    [[EXITCOND:%.*]] = fcmp ogt float [[INC]], 1.000000e+03
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ]
; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
; CHECK:       fail:
; CHECK-NEXT:    call void @f()
; CHECK-NEXT:    ret i32 -1
;
entry:
  br label %for.body

for.body:
  %iv = phi float [ 0.0, %entry ], [ %inc, %continue ]
  %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
  %r.chk = fcmp olt float %iv, 2000.0
  br i1 %r.chk, label %continue, label %fail
continue:
  %i1 = load i32, ptr %a, align 4
  %add = add nsw i32 %i1, %acc
  %inc = fadd float %iv, 1.0
  %exitcond = fcmp ogt float %inc, 1000.0
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret i32 %add

fail:
  call void @f()
  ret i32 -1
}

; Count down from a.length w/entry guard
; TODO: currently unable to prove the following:
; ule i32 (add nsw i32 %len, -1), %len where len is [0, 512]
define i32 @test2(ptr noalias nocapture readonly %a) nounwind uwtable {
; CHECK-LABEL: define i32 @test2(
; CHECK-SAME: ptr noalias readonly captures(none) [[A:%.*]]) #[[ATTR1]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[A]], align 4, !range [[RNG0:![0-9]+]]
; CHECK-NEXT:    [[IS_NON_POS:%.*]] = icmp eq i32 [[LEN]], 0
; CHECK-NEXT:    br i1 [[IS_NON_POS]], label [[FAIL:%.*]], label [[PREHEADER:%.*]]
; CHECK:       preheader:
; CHECK-NEXT:    [[LENMINUSONE:%.*]] = add nsw i32 [[LEN]], -1
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LENMINUSONE]], [[PREHEADER]] ], [ [[DEC:%.*]], [[CONTINUE:%.*]] ]
; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[ADD:%.*]], [[CONTINUE]] ]
; CHECK-NEXT:    [[R_CHK:%.*]] = icmp ule i32 [[IV]], [[LEN]]
; CHECK-NEXT:    br i1 [[R_CHK]], label [[CONTINUE]], label [[FAIL_LOOPEXIT:%.*]]
; CHECK:       continue:
; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
; CHECK-NEXT:    [[DEC]] = add nsw i32 [[IV]], -1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[DEC]], 0
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ]
; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
; CHECK:       fail.loopexit:
; CHECK-NEXT:    br label [[FAIL]]
; CHECK:       fail:
; CHECK-NEXT:    call void @f()
; CHECK-NEXT:    ret i32 -1
;
entry:
  %len = load i32, ptr %a, align 4, !range !{i32 0, i32 512}
  %is.non.pos = icmp eq i32 %len, 0
  br i1 %is.non.pos, label %fail, label %preheader
preheader:
  %lenminusone = add nsw i32 %len, -1
  br label %for.body
for.body:
  %iv = phi i32 [ %lenminusone, %preheader ], [ %dec, %continue ]
  %acc = phi i32 [ 0, %preheader ], [ %add, %continue ]
  %r.chk = icmp ule i32 %iv, %len
  br i1 %r.chk, label %continue, label %fail
continue:
  %i1 = load i32, ptr %a, align 4
  %add = add nsw i32 %i1, %acc
  %dec = add nsw i32 %iv, -1
  %exitcond = icmp eq i32 %dec, 0
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret i32 %add

fail:
  call void @f()
  ret i32 -1
}

; trivially true for zero
define i32 @test3(ptr noalias nocapture readonly %a) nounwind uwtable {
; CHECK-LABEL: define i32 @test3(
; CHECK-SAME: ptr noalias readonly captures(none) [[A:%.*]]) #[[ATTR1]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[A]], align 4, !range [[RNG0]]
; CHECK-NEXT:    [[IS_ZERO:%.*]] = icmp eq i32 [[LEN]], 0
; CHECK-NEXT:    br i1 [[IS_ZERO]], label [[FAIL:%.*]], label [[PREHEADER:%.*]]
; CHECK:       preheader:
; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[INC:%.*]], [[CONTINUE:%.*]] ]
; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[ADD:%.*]], [[CONTINUE]] ]
; CHECK-NEXT:    [[R_CHK:%.*]] = icmp ule i32 [[IV]], [[LEN]]
; CHECK-NEXT:    br i1 [[R_CHK]], label [[CONTINUE]], label [[FAIL_LOOPEXIT:%.*]]
; CHECK:       continue:
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ]
; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
; CHECK:       fail.loopexit:
; CHECK-NEXT:    br label [[FAIL]]
; CHECK:       fail:
; CHECK-NEXT:    call void @f()
; CHECK-NEXT:    ret i32 -1
;
entry:
  %len = load i32, ptr %a, align 4, !range !{i32 0, i32 512}
  %is.zero = icmp eq i32 %len, 0
  br i1 %is.zero, label %fail, label %preheader
preheader:
  br label %for.body
for.body:
  %iv = phi i32 [ 0, %preheader ], [ %inc, %continue ]
  %acc = phi i32 [ 0, %preheader ], [ %add, %continue ]
  %r.chk = icmp ule i32 %iv, %len
  br i1 %r.chk, label %continue, label %fail
continue:
  %i1 = load i32, ptr %a, align 4
  %add = add nsw i32 %i1, %acc
  %inc = add nuw nsw i32 %iv, 1
  %exitcond = icmp eq i32 %inc, 1000
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret i32 %add

fail:
  call void @f()
  ret i32 -1
}

; Same as previous case, with commuted icmp.
define i32 @test3_commuted(ptr noalias nocapture readonly %a) nounwind uwtable {
; CHECK-LABEL: define i32 @test3_commuted(
; CHECK-SAME: ptr noalias readonly captures(none) [[A:%.*]]) #[[ATTR1]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[A]], align 4, !range [[RNG0]]
; CHECK-NEXT:    [[IS_ZERO:%.*]] = icmp eq i32 [[LEN]], 0
; CHECK-NEXT:    br i1 [[IS_ZERO]], label [[FAIL:%.*]], label [[PREHEADER:%.*]]
; CHECK:       preheader:
; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[INC:%.*]], [[CONTINUE:%.*]] ]
; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[ADD:%.*]], [[CONTINUE]] ]
; CHECK-NEXT:    [[R_CHK:%.*]] = icmp uge i32 [[LEN]], [[IV]]
; CHECK-NEXT:    br i1 [[R_CHK]], label [[CONTINUE]], label [[FAIL_LOOPEXIT:%.*]]
; CHECK:       continue:
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ]
; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
; CHECK:       fail.loopexit:
; CHECK-NEXT:    br label [[FAIL]]
; CHECK:       fail:
; CHECK-NEXT:    call void @f()
; CHECK-NEXT:    ret i32 -1
;
entry:
  %len = load i32, ptr %a, align 4, !range !{i32 0, i32 512}
  %is.zero = icmp eq i32 %len, 0
  br i1 %is.zero, label %fail, label %preheader
preheader:
  br label %for.body
for.body:
  %iv = phi i32 [ 0, %preheader ], [ %inc, %continue ]
  %acc = phi i32 [ 0, %preheader ], [ %add, %continue ]
  %r.chk = icmp uge i32 %len, %iv
  br i1 %r.chk, label %continue, label %fail
continue:
  %i1 = load i32, ptr %a, align 4
  %add = add nsw i32 %i1, %acc
  %inc = add nuw nsw i32 %iv, 1
  %exitcond = icmp eq i32 %inc, 1000
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret i32 %add

fail:
  call void @f()
  ret i32 -1
}

; requires fact length is non-zero
define i32 @test4(ptr noalias nocapture readonly %a) nounwind uwtable {
; CHECK-LABEL: define i32 @test4(
; CHECK-SAME: ptr noalias readonly captures(none) [[A:%.*]]) #[[ATTR1]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[A]], align 4, !range [[RNG0]]
; CHECK-NEXT:    [[IS_ZERO:%.*]] = icmp eq i32 [[LEN]], 0
; CHECK-NEXT:    br i1 [[IS_ZERO]], label [[FAIL:%.*]], label [[PREHEADER:%.*]]
; CHECK:       preheader:
; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[INC:%.*]], [[CONTINUE:%.*]] ]
; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[ADD:%.*]], [[CONTINUE]] ]
; CHECK-NEXT:    [[R_CHK:%.*]] = icmp ult i32 [[IV]], [[LEN]]
; CHECK-NEXT:    br i1 [[R_CHK]], label [[CONTINUE]], label [[FAIL_LOOPEXIT:%.*]]
; CHECK:       continue:
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ]
; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
; CHECK:       fail.loopexit:
; CHECK-NEXT:    br label [[FAIL]]
; CHECK:       fail:
; CHECK-NEXT:    call void @f()
; CHECK-NEXT:    ret i32 -1
;
entry:
  %len = load i32, ptr %a, align 4, !range !{i32 0, i32 512}
  %is.zero = icmp eq i32 %len, 0
  br i1 %is.zero, label %fail, label %preheader
preheader:
  br label %for.body
for.body:
  %iv = phi i32 [ 0, %preheader ], [ %inc, %continue ]
  %acc = phi i32 [ 0, %preheader ], [ %add, %continue ]
  %r.chk = icmp ult i32 %iv, %len
  br i1 %r.chk, label %continue, label %fail
continue:
  %i1 = load i32, ptr %a, align 4
  %add = add nsw i32 %i1, %acc
  %inc = add nuw nsw i32 %iv, 1
  %exitcond = icmp eq i32 %inc, 1000
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret i32 %add

fail:
  call void @f()
  ret i32 -1
}

; variation on test1 with branch swapped
define i32 @test-brswap(ptr noalias nocapture readonly %a) nounwind uwtable {
; CHECK-LABEL: define i32 @test-brswap(
; CHECK-SAME: ptr noalias readonly captures(none) [[A:%.*]]) #[[ATTR1]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[CONTINUE:%.*]] ]
; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[CONTINUE]] ]
; CHECK-NEXT:    [[R_CHK:%.*]] = icmp ugt i32 [[IV]], 2000
; CHECK-NEXT:    br i1 [[R_CHK]], label [[FAIL:%.*]], label [[CONTINUE]]
; CHECK:       continue:
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ]
; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
; CHECK:       fail:
; CHECK-NEXT:    call void @f()
; CHECK-NEXT:    ret i32 -1
;
entry:
  br label %for.body

for.body:
  %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
  %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
  %r.chk = icmp ugt i32 %iv, 2000
  br i1 %r.chk, label %fail, label %continue
continue:
  %i1 = load i32, ptr %a, align 4
  %add = add nsw i32 %i1, %acc
  %inc = add nuw nsw i32 %iv, 1
  %exitcond = icmp eq i32 %inc, 1000
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret i32 %add

fail:
  call void @f()
  ret i32 -1
}

define i32 @test-nonphi(ptr noalias nocapture readonly %a) nounwind uwtable {
; CHECK-LABEL: define i32 @test-nonphi(
; CHECK-SAME: ptr noalias readonly captures(none) [[A:%.*]]) #[[ATTR1]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[CONTINUE:%.*]] ]
; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[CONTINUE]] ]
; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[IV]], 72
; CHECK-NEXT:    [[R_CHK:%.*]] = icmp ugt i32 [[XOR]], 2000
; CHECK-NEXT:    br i1 [[R_CHK]], label [[FAIL:%.*]], label [[CONTINUE]]
; CHECK:       continue:
; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ]
; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
; CHECK:       fail:
; CHECK-NEXT:    call void @f()
; CHECK-NEXT:    ret i32 -1
;
entry:
  br label %for.body

for.body:
  %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
  %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
  %xor = xor i32 %iv, 72
  %r.chk = icmp ugt i32 %xor, 2000
  br i1 %r.chk, label %fail, label %continue
continue:
  %i1 = load i32, ptr %a, align 4
  %add = add nsw i32 %i1, %acc
  %inc = add nuw nsw i32 %iv, 1
  %exitcond = icmp eq i32 %inc, 1000
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret i32 %add

fail:
  call void @f()
  ret i32 -1
}

define i32 @test-wrongphi(ptr noalias nocapture readonly %a) nounwind uwtable {
; CHECK-LABEL: define i32 @test-wrongphi(
; CHECK-SAME: ptr noalias readonly captures(none) [[A:%.*]]) #[[ATTR1]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[CONTINUE:%.*]] ]
; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[CONTINUE]] ]
; CHECK-NEXT:    [[COND:%.*]] = icmp ult i32 [[IV]], 500
; CHECK-NEXT:    br i1 [[COND]], label [[DUMMY_BLOCK1:%.*]], label [[DUMMY_BLOCK2:%.*]]
; CHECK:       dummy_block1:
; CHECK-NEXT:    br label [[DUMMY_BLOCK2]]
; CHECK:       dummy_block2:
; CHECK-NEXT:    [[WRONGPHI:%.*]] = phi i32 [ 11, [[FOR_BODY]] ], [ 12, [[DUMMY_BLOCK1]] ]
; CHECK-NEXT:    [[R_CHK:%.*]] = icmp ugt i32 [[WRONGPHI]], 2000
; CHECK-NEXT:    br i1 [[R_CHK]], label [[FAIL:%.*]], label [[CONTINUE]]
; CHECK:       continue:
; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ]
; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
; CHECK:       fail:
; CHECK-NEXT:    call void @f()
; CHECK-NEXT:    ret i32 -1
;
entry:
  br label %for.body

for.body:
  %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
  %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
  %cond = icmp ult i32 %iv, 500
  br i1 %cond, label %dummy_block1, label %dummy_block2

dummy_block1:
  br label %dummy_block2

dummy_block2:
  %wrongphi = phi i32 [11, %for.body], [12, %dummy_block1]
  %r.chk = icmp ugt i32 %wrongphi, 2000
  br i1 %r.chk, label %fail, label %continue
continue:
  %i1 = load i32, ptr %a, align 4
  %add = add nsw i32 %i1, %acc
  %inc = add nuw nsw i32 %iv, 1
  %exitcond = icmp eq i32 %inc, 1000
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret i32 %add

fail:
  call void @f()
  ret i32 -1
}

; This works because loop-simplify is run implicitly, but test for it anyways
define i32 @test-multiple-latch(ptr noalias nocapture readonly %a) nounwind uwtable {
; CHECK-LABEL: define i32 @test-multiple-latch(
; CHECK-SAME: ptr noalias readonly captures(none) [[A:%.*]]) #[[ATTR1]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY_BACKEDGE:%.*]] ]
; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY_BACKEDGE]] ]
; CHECK-NEXT:    [[R_CHK:%.*]] = icmp ult i32 [[IV]], 2000
; CHECK-NEXT:    br i1 [[R_CHK]], label [[CONTINUE1:%.*]], label [[FAIL:%.*]]
; CHECK:       continue1:
; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[ADD]], 0
; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE2:%.*]], label [[FOR_BODY_BACKEDGE]]
; CHECK:       for.body.backedge:
; CHECK-NEXT:    br label [[FOR_BODY]]
; CHECK:       continue2:
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY_BACKEDGE]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE2]] ]
; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
; CHECK:       fail:
; CHECK-NEXT:    call void @f()
; CHECK-NEXT:    ret i32 -1
;
entry:
  br label %for.body

for.body:
  %iv = phi i32 [ 0, %entry ], [ %inc, %continue1 ], [ %inc, %continue2 ]
  %acc = phi i32 [ 0, %entry ], [ %add, %continue1 ], [ %add, %continue2 ]
  %r.chk = icmp ult i32 %iv, 2000
  br i1 %r.chk, label %continue1, label %fail
continue1:
  %i1 = load i32, ptr %a, align 4
  %add = add nsw i32 %i1, %acc
  %inc = add nuw nsw i32 %iv, 1
  %cmp = icmp eq i32 %add, 0
  br i1 %cmp, label %continue2, label %for.body
continue2:
  %exitcond = icmp eq i32 %inc, 1000
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret i32 %add

fail:
  call void @f()
  ret i32 -1
}

define void @test-hoisting-in-presence-of-guards(i1 %c, ptr %p) {
; CHECK-LABEL: define void @test-hoisting-in-presence-of-guards(
; CHECK-SAME: i1 [[C:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4
; CHECK-NEXT:    [[INVARIANT_COND:%.*]] = icmp ne i32 [[A]], 100
; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[INVARIANT_COND]]) [ "deopt"() ]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], 1000
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;

entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %iv.next = add i32 %iv, 1
  %a = load i32, ptr %p
  %invariant_cond = icmp ne i32 %a, 100
  call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ]
  %loop_cond = icmp slt i32 %iv.next, 1000
  br i1 %loop_cond, label %loop, label %exit

exit:
  ret void
}


declare void @may_throw() inaccessiblememonly

; Test that we can sink a mustexecute load from loop header even in presence of
; throwing instructions after it.
define void @test_hoist_from_header_01(ptr %p, i32 %n) {
; CHECK-LABEL: define void @test_hoist_from_header_01(
; CHECK-SAME: ptr [[P:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[P]], align 4
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    call void @may_throw()
; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV]], [[N]]
; CHECK-NEXT:    br i1 [[COND]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
; CHECK:       if.true:
; CHECK-NEXT:    [[A:%.*]] = add i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       if.false:
; CHECK-NEXT:    [[B:%.*]] = mul i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ [[A]], [[IF_TRUE]] ], [ [[B]], [[IF_FALSE]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[MERGE]]
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LOAD]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;

entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
  %load = load i32, ptr %p
  call void @may_throw()
  %cond = icmp slt i32 %iv, %n
  br i1 %cond, label %if.true, label %if.false

if.true:
  %a = add i32 %iv, %iv
  br label %backedge

if.false:
  %b = mul i32 %iv, %iv
  br label %backedge

backedge:
  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
  %iv.next = add i32 %iv, %merge
  %loop.cond = icmp ult i32 %iv.next, %load
  br i1 %loop.cond, label %loop, label %exit

exit:
  ret void
}

define void @test_hoist_from_header_02(ptr %p, i32 %n) {
; CHECK-LABEL: define void @test_hoist_from_header_02(
; CHECK-SAME: ptr [[P:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[P]], align 4
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV]], [[N]]
; CHECK-NEXT:    br i1 [[COND]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
; CHECK:       if.true:
; CHECK-NEXT:    call void @may_throw()
; CHECK-NEXT:    [[A:%.*]] = add i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       if.false:
; CHECK-NEXT:    [[B:%.*]] = mul i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ [[A]], [[IF_TRUE]] ], [ [[B]], [[IF_FALSE]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[MERGE]]
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LOAD]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;

entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
  %load = load i32, ptr %p
  %cond = icmp slt i32 %iv, %n
  br i1 %cond, label %if.true, label %if.false

if.true:
  call void @may_throw()
  %a = add i32 %iv, %iv
  br label %backedge

if.false:
  %b = mul i32 %iv, %iv
  br label %backedge

backedge:
  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
  %iv.next = add i32 %iv, %merge
  %loop.cond = icmp ult i32 %iv.next, %load
  br i1 %loop.cond, label %loop, label %exit

exit:
  ret void
}

define void @test_hoist_from_header_03(ptr %p, i32 %n) {
; CHECK-LABEL: define void @test_hoist_from_header_03(
; CHECK-SAME: ptr [[P:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[P]], align 4
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV]], [[N]]
; CHECK-NEXT:    br i1 [[COND]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
; CHECK:       if.true:
; CHECK-NEXT:    [[A:%.*]] = add i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       if.false:
; CHECK-NEXT:    [[B:%.*]] = mul i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ [[A]], [[IF_TRUE]] ], [ [[B]], [[IF_FALSE]] ]
; CHECK-NEXT:    call void @may_throw()
; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[MERGE]]
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LOAD]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;

entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
  %load = load i32, ptr %p
  %cond = icmp slt i32 %iv, %n
  br i1 %cond, label %if.true, label %if.false

if.true:
  %a = add i32 %iv, %iv
  br label %backedge

if.false:
  %b = mul i32 %iv, %iv
  br label %backedge

backedge:
  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
  call void @may_throw()
  %iv.next = add i32 %iv, %merge
  %loop.cond = icmp ult i32 %iv.next, %load
  br i1 %loop.cond, label %loop, label %exit

exit:
  ret void
}

; Check that a throwing instruction prohibits hoisting across it.
define void @test_hoist_from_header_04(ptr %p, i32 %n) {
; CHECK-LABEL: define void @test_hoist_from_header_04(
; CHECK-SAME: ptr [[P:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    call void @may_throw()
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[P]], align 4
; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV]], [[N]]
; CHECK-NEXT:    br i1 [[COND]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
; CHECK:       if.true:
; CHECK-NEXT:    [[A:%.*]] = add i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       if.false:
; CHECK-NEXT:    [[B:%.*]] = mul i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ [[A]], [[IF_TRUE]] ], [ [[B]], [[IF_FALSE]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[MERGE]]
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LOAD]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;

entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
  call void @may_throw()
  %load = load i32, ptr %p
  %cond = icmp slt i32 %iv, %n
  br i1 %cond, label %if.true, label %if.false

if.true:
  %a = add i32 %iv, %iv
  br label %backedge

if.false:
  %b = mul i32 %iv, %iv
  br label %backedge

backedge:
  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
  %iv.next = add i32 %iv, %merge
  %loop.cond = icmp ult i32 %iv.next, %load
  br i1 %loop.cond, label %loop, label %exit

exit:
  ret void
}

; Check that we can hoist a mustexecute load from backedge even if something
; throws after it.
define void @test_hoist_from_backedge_01(ptr %p, i32 %n) {
; CHECK-LABEL: define void @test_hoist_from_backedge_01(
; CHECK-SAME: ptr [[P:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[P]], align 4
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV]], [[N]]
; CHECK-NEXT:    br i1 [[COND]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
; CHECK:       if.true:
; CHECK-NEXT:    [[A:%.*]] = add i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       if.false:
; CHECK-NEXT:    [[B:%.*]] = mul i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ [[A]], [[IF_TRUE]] ], [ [[B]], [[IF_FALSE]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[MERGE]]
; CHECK-NEXT:    call void @may_throw()
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LOAD]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;

entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
  %cond = icmp slt i32 %iv, %n
  br i1 %cond, label %if.true, label %if.false

if.true:
  %a = add i32 %iv, %iv
  br label %backedge

if.false:
  %b = mul i32 %iv, %iv
  br label %backedge

backedge:
  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
  %iv.next = add i32 %iv, %merge
  %load = load i32, ptr %p
  call void @may_throw()
  %loop.cond = icmp ult i32 %iv.next, %load
  br i1 %loop.cond, label %loop, label %exit

exit:
  ret void
}

; Check that we don't hoist the load if something before it can throw.
define void @test_hoist_from_backedge_02(ptr %p, i32 %n) {
; CHECK-LABEL: define void @test_hoist_from_backedge_02(
; CHECK-SAME: ptr [[P:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV]], [[N]]
; CHECK-NEXT:    br i1 [[COND]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
; CHECK:       if.true:
; CHECK-NEXT:    [[A:%.*]] = add i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       if.false:
; CHECK-NEXT:    [[B:%.*]] = mul i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ [[A]], [[IF_TRUE]] ], [ [[B]], [[IF_FALSE]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[MERGE]]
; CHECK-NEXT:    call void @may_throw()
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[P]], align 4
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LOAD]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;

entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
  %cond = icmp slt i32 %iv, %n
  br i1 %cond, label %if.true, label %if.false

if.true:
  %a = add i32 %iv, %iv
  br label %backedge

if.false:
  %b = mul i32 %iv, %iv
  br label %backedge

backedge:
  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
  %iv.next = add i32 %iv, %merge
  call void @may_throw()
  %load = load i32, ptr %p
  %loop.cond = icmp ult i32 %iv.next, %load
  br i1 %loop.cond, label %loop, label %exit

exit:
  ret void
}

define void @test_hoist_from_backedge_03(ptr %p, i32 %n) {
; CHECK-LABEL: define void @test_hoist_from_backedge_03(
; CHECK-SAME: ptr [[P:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV]], [[N]]
; CHECK-NEXT:    br i1 [[COND]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
; CHECK:       if.true:
; CHECK-NEXT:    [[A:%.*]] = add i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       if.false:
; CHECK-NEXT:    [[B:%.*]] = mul i32 [[IV]], [[IV]]
; CHECK-NEXT:    call void @may_throw()
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ [[A]], [[IF_TRUE]] ], [ [[B]], [[IF_FALSE]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[MERGE]]
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[P]], align 4
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LOAD]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;

entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
  %cond = icmp slt i32 %iv, %n
  br i1 %cond, label %if.true, label %if.false

if.true:
  %a = add i32 %iv, %iv
  br label %backedge

if.false:
  %b = mul i32 %iv, %iv
  call void @may_throw()
  br label %backedge

backedge:
  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
  %iv.next = add i32 %iv, %merge
  %load = load i32, ptr %p
  %loop.cond = icmp ult i32 %iv.next, %load
  br i1 %loop.cond, label %loop, label %exit

exit:
  ret void
}

define void @test_hoist_from_backedge_04(ptr %p, i32 %n) {
; CHECK-LABEL: define void @test_hoist_from_backedge_04(
; CHECK-SAME: ptr [[P:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    call void @may_throw()
; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV]], [[N]]
; CHECK-NEXT:    br i1 [[COND]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
; CHECK:       if.true:
; CHECK-NEXT:    [[A:%.*]] = add i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       if.false:
; CHECK-NEXT:    [[B:%.*]] = mul i32 [[IV]], [[IV]]
; CHECK-NEXT:    br label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ [[A]], [[IF_TRUE]] ], [ [[B]], [[IF_FALSE]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], [[MERGE]]
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[P]], align 4
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LOAD]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;

entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
  call void @may_throw()
  %cond = icmp slt i32 %iv, %n
  br i1 %cond, label %if.true, label %if.false

if.true:
  %a = add i32 %iv, %iv
  br label %backedge

if.false:
  %b = mul i32 %iv, %iv
  br label %backedge

backedge:
  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
  %iv.next = add i32 %iv, %merge
  %load = load i32, ptr %p
  %loop.cond = icmp ult i32 %iv.next, %load
  br i1 %loop.cond, label %loop, label %exit

exit:
  ret void
}
;.
; CHECK: [[RNG0]] = !{i32 0, i32 512}
;.