; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
; RUN: opt < %s -mtriple=x86_64-unknown-unknown --loop-simplify -codegenprepare -S | FileCheck %s

declare void @use.i32(i32)
declare void @use.2xi64(<2 x i64>)
declare void @do_stuff0()
declare void @do_stuff1()
declare i1 @get.i1()
declare i32 @get.i32()

define void @simple_urem_to_sel(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0:[0-9]+]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[REM:%.*]] = phi i32 [ 0, %[[FOR_BODY_PREHEADER]] ], [ [[TMP3:%.*]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i32 [[REM]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], [[REM_AMT]]
; CHECK-NEXT:    [[TMP3]] = select i1 [[TMP2]], i32 0, i32 [[TMP1]]
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_fail_not_in_loop(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_fail_not_in_loop(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    [[I_05:%.*]] = phi i32 [ 0, %[[ENTRY]] ], [ [[INC:%.*]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_05]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC]], %[[FOR_BODY]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    tail call void @use.i32(i32 [[I_04]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  %i.05 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  %rem = urem i32 %i.05, %rem_amt
  tail call void @use.i32(i32 %rem)
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  tail call void @use.i32(i32 %i.04)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_inner_loop(i32 %N, i32 %M) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_inner_loop(
; CHECK-SAME: i32 [[N:%.*]], i32 [[M:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[REM_AMT:%.*]] = call i32 @get.i32()
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[REM:%.*]] = phi i32 [ 0, %[[FOR_BODY_PREHEADER]] ], [ [[TMP3:%.*]], %[[FOR_INNER_COND_CLEANUP:.*]] ]
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_INNER_COND_CLEANUP]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[CMP_INNER:%.*]] = icmp eq i32 [[M]], 0
; CHECK-NEXT:    br i1 [[CMP_INNER]], label %[[FOR_INNER_COND_CLEANUP]], label %[[FOR_INNER_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_INNER_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_INNER_BODY:.*]]
; CHECK:       [[FOR_INNER_BODY]]:
; CHECK-NEXT:    [[J:%.*]] = phi i32 [ [[INC_INNER:%.*]], %[[FOR_INNER_BODY]] ], [ 0, %[[FOR_INNER_BODY_PREHEADER]] ]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC_INNER]] = add nuw i32 [[J]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[INC_INNER]], [[M]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[FOR_INNER_COND_CLEANUP]], label %[[FOR_INNER_BODY]]
; CHECK:       [[FOR_INNER_COND_CLEANUP]]:
; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i32 [[REM]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], [[REM_AMT]]
; CHECK-NEXT:    [[TMP3]] = select i1 [[TMP2]], i32 0, i32 [[TMP1]]
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %rem_amt = call i32 @get.i32()
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.inner.cond.cleanup ], [ 0, %entry ]

  %cmp_inner = icmp eq i32 %M, 0
  br i1 %cmp_inner, label %for.inner.cond.cleanup, label %for.inner.body

for.inner.body:
  %j = phi i32 [ %inc_inner, %for.inner.body ], [ 0, %for.body ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc_inner = add nuw i32 %j, 1
  %exitcond_inner = icmp eq i32 %inc_inner, %M
  br i1 %exitcond_inner, label %for.inner.cond.cleanup, label %for.inner.body

for.inner.cond.cleanup:
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_inner_loop_fail_not_invariant(i32 %N, i32 %M) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_inner_loop_fail_not_invariant(
; CHECK-SAME: i32 [[N:%.*]], i32 [[M:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_INNER_COND_CLEANUP:.*]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[REM_AMT:%.*]] = call i32 @get.i32()
; CHECK-NEXT:    [[CMP_INNER:%.*]] = icmp eq i32 [[M]], 0
; CHECK-NEXT:    br i1 [[CMP_INNER]], label %[[FOR_INNER_COND_CLEANUP]], label %[[FOR_INNER_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_INNER_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_INNER_BODY:.*]]
; CHECK:       [[FOR_INNER_BODY]]:
; CHECK-NEXT:    [[J:%.*]] = phi i32 [ [[INC_INNER:%.*]], %[[FOR_INNER_BODY]] ], [ 0, %[[FOR_INNER_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_04]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC_INNER]] = add nuw i32 [[J]], 1
; CHECK-NEXT:    [[EXITCOND_INNER:%.*]] = icmp eq i32 [[INC_INNER]], [[M]]
; CHECK-NEXT:    br i1 [[EXITCOND_INNER]], label %[[FOR_INNER_COND_CLEANUP]], label %[[FOR_INNER_BODY]]
; CHECK:       [[FOR_INNER_COND_CLEANUP]]:
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.inner.cond.cleanup ], [ 0, %entry ]
  %rem_amt = call i32 @get.i32()
  %cmp_inner = icmp eq i32 %M, 0
  br i1 %cmp_inner, label %for.inner.cond.cleanup, label %for.inner.body

for.inner.body:
  %j = phi i32 [ %inc_inner, %for.inner.body ], [ 0, %for.body ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc_inner = add nuw i32 %j, 1
  %exitcond_inner = icmp eq i32 %inc_inner, %M
  br i1 %exitcond_inner, label %for.inner.cond.cleanup, label %for.inner.body

for.inner.cond.cleanup:
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_nested2(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_nested2(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[REM:%.*]] = phi i32 [ 0, %[[FOR_BODY_PREHEADER]] ], [ [[TMP3:%.*]], %[[FOR_BODY_TAIL:.*]] ]
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY_TAIL]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[COND0:%.*]] = call i1 @get.i1()
; CHECK-NEXT:    br i1 [[COND0]], label %[[FOR_BODY0:.*]], label %[[FOR_BODY_TAIL]]
; CHECK:       [[FOR_BODY0]]:
; CHECK-NEXT:    [[COND1:%.*]] = call i1 @get.i1()
; CHECK-NEXT:    br i1 [[COND1]], label %[[FOR_BODY1:.*]], label %[[FOR_BODY2:.*]]
; CHECK:       [[FOR_BODY2]]:
; CHECK-NEXT:    [[COND2:%.*]] = call i1 @get.i1()
; CHECK-NEXT:    br i1 [[COND2]], label %[[FOR_BODY1]], label %[[FOR_BODY_TAIL]]
; CHECK:       [[FOR_BODY1]]:
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    br label %[[FOR_BODY_TAIL]]
; CHECK:       [[FOR_BODY_TAIL]]:
; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i32 [[REM]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], [[REM_AMT]]
; CHECK-NEXT:    [[TMP3]] = select i1 [[TMP2]], i32 0, i32 [[TMP1]]
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body.tail ], [ 0, %entry ]
  %cond0 = call i1 @get.i1()
  br i1 %cond0, label %for.body0, label %for.body.tail
for.body0:
  %cond1 = call i1 @get.i1()
  br i1 %cond1, label %for.body1, label %for.body2
for.body2:
  %cond2 = call i1 @get.i1()
  br i1 %cond2, label %for.body1, label %for.body.tail
for.body1:
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  br label %for.body.tail
for.body.tail:
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_fail_bad_incr3(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_fail_bad_incr3(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[COND0:%.*]] = call i1 @get.i1()
; CHECK-NEXT:    br i1 [[COND0]], label %[[FOR_BODY0:.*]], label %[[FOR_BODY2:.*]]
; CHECK:       [[FOR_BODY0]]:
; CHECK-NEXT:    [[COND1:%.*]] = call i1 @get.i1()
; CHECK-NEXT:    [[VAL:%.*]] = call i32 @get.i32()
; CHECK-NEXT:    [[INC:%.*]] = add nuw i32 [[VAL]], 1
; CHECK-NEXT:    br i1 [[COND1]], label %[[FOR_BODY1:.*]], label %[[FOR_BODY_TAIL:.*]]
; CHECK:       [[FOR_BODY2]]:
; CHECK-NEXT:    [[COND2:%.*]] = call i1 @get.i1()
; CHECK-NEXT:    br i1 [[COND2]], label %[[FOR_BODY1]], label %[[FOR_BODY_TAIL]]
; CHECK:       [[FOR_BODY1]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC]], %[[FOR_BODY0]] ], [ 0, %[[FOR_BODY2]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_04]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    br label %[[FOR_BODY_TAIL]]
; CHECK:       [[FOR_BODY_TAIL]]:
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = call i1 @get.i1()
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %cond0 = call i1 @get.i1()
  br i1 %cond0, label %for.body0, label %for.body2
for.body0:
  %cond1 = call i1 @get.i1()
  %val = call i32 @get.i32()
  %inc = add nuw i32 %val, 1
  br i1 %cond1, label %for.body1, label %for.body.tail
for.body2:
  %cond2 = call i1 @get.i1()
  br i1 %cond2, label %for.body1, label %for.body.tail
for.body1:
  %i.04 = phi i32 [ %inc, %for.body0], [ 0, %for.body2 ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  br label %for.body.tail
for.body.tail:
  %exitcond.not = call i1 @get.i1()
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_vec(<2 x i64> %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_vec(
; CHECK-SAME: <2 x i64> [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP:.*]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[REM:%.*]] = phi <2 x i64> [ zeroinitializer, %[[ENTRY]] ], [ [[TMP3:%.*]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[I_04:%.*]] = phi <2 x i64> [ [[INC:%.*]], %[[FOR_BODY]] ], [ zeroinitializer, %[[ENTRY]] ]
; CHECK-NEXT:    tail call void @use.2xi64(<2 x i64> [[REM]])
; CHECK-NEXT:    [[TMP1:%.*]] = add nuw <2 x i64> [[REM]], splat (i64 1)
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq <2 x i64> [[TMP1]], [[REM_AMT]]
; CHECK-NEXT:    [[TMP3]] = select <2 x i1> [[TMP2]], <2 x i64> zeroinitializer, <2 x i64> [[TMP1]]
; CHECK-NEXT:    [[INC]] = add nuw <2 x i64> [[I_04]], splat (i64 1)
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = call i1 @get.i1()
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  br label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi <2 x i64> [ %inc, %for.body ], [ zeroinitializer, %entry ]
  %rem = urem <2 x i64> %i.04, %rem_amt
  tail call void @use.2xi64(<2 x i64> %rem)
  %inc = add nuw <2 x i64> %i.04, <i64 1, i64 1>
  %exitcond.not = call i1 @get.i1()
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_fail_bad_incr(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_fail_bad_incr(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_03:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY_TAIL:.*]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[COND0:%.*]] = call i1 @get.i1()
; CHECK-NEXT:    br i1 [[COND0]], label %[[FOR_BODY0:.*]], label %[[FOR_BODY_TAIL]]
; CHECK:       [[FOR_BODY0]]:
; CHECK-NEXT:    [[SOME_VAL:%.*]] = call i32 @get.i32()
; CHECK-NEXT:    br label %[[FOR_BODY_TAIL]]
; CHECK:       [[FOR_BODY_TAIL]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[I_03]], %[[FOR_BODY]] ], [ [[SOME_VAL]], %[[FOR_BODY0]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_04]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.03 = phi i32 [ %inc, %for.body.tail ], [ 0, %entry ]
  %cond0 = call i1 @get.i1()
  br i1 %cond0, label %for.body0, label %for.body.tail
for.body0:
  %some_val = call i32 @get.i32()
  br label %for.body.tail

for.body.tail:
  %i.04 = phi i32 [ %i.03, %for.body ], [ %some_val, %for.body0 ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_second_acc(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_second_acc(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp ult i32 [[N]], 2
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[REM:%.*]] = phi i32 [ 0, %[[FOR_BODY_PREHEADER]] ], [ [[TMP3:%.*]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[I_05:%.*]] = phi i32 [ [[INC2:%.*]], %[[FOR_BODY]] ], [ 1, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i32 [[REM]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], [[REM_AMT]]
; CHECK-NEXT:    [[TMP3]] = select i1 [[TMP2]], i32 0, i32 [[TMP1]]
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[INC2]] = add nuw i32 [[I_05]], 2
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp ugt i32 [[INC2]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp ult i32 %N, 2
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  %i.05 = phi i32 [ %inc2, %for.body ], [ 1, %entry ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %inc2 = add nuw i32 %i.05, 2
  %exitcond.not = icmp ugt i32 %inc2, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_fail_srem(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_fail_srem(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[I_04]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  %rem = srem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_fail_missing_nuw(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_fail_missing_nuw(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_04]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nsw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_fail_bad_incr2(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_fail_bad_incr2(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_04]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 2
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 2
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_non_zero_entry4(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_non_zero_entry4(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 4, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_04]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 4, %entry ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_skip_const_rem_amt(i32 %N) nounwind {
; CHECK-LABEL: define void @simple_urem_skip_const_rem_amt(
; CHECK-SAME: i32 [[N:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 4, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_04]], 19
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 4, %entry ]
  %rem = urem i32 %i.04, 19
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_fail_no_preheader_non_canonical(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_fail_no_preheader_non_canonical(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_BODY_PREHEADER:.*]], label %[[FOR_BODY1:.*]]
; CHECK:       [[FOR_COND_CLEANUP:.*]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY1]]:
; CHECK-NEXT:    br label %[[FOR_BODY_PREHEADER]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    [[I_04_PH:%.*]] = phi i32 [ 1, %[[FOR_BODY1]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ [[I_04_PH]], %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_04]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.body0, label %for.body1

for.cond.cleanup:
  ret void

for.body0:
  br label %for.body

for.body1:
  br label %for.body

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 0, %for.body0 ], [ 1, %for.body1 ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_multi_latch_non_canonical(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_multi_latch_non_canonical(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ 0, %[[FOR_BODY_PREHEADER]] ], [ [[INC:%.*]], %[[FOR_BODY]] ], [ [[INC]], %[[FOR_BODY0:.*]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_04]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[COND:%.*]] = call i1 @get.i1()
; CHECK-NEXT:    call void @do_stuff0()
; CHECK-NEXT:    br i1 [[COND]], label %[[FOR_BODY0]], label %[[FOR_BODY]]
; CHECK:       [[FOR_BODY0]]:
; CHECK-NEXT:    call void @do_stuff1()
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ %inc, %for.body0 ], [ 0, %entry ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %cond = call i1 @get.i1()
  call void @do_stuff0()
  br i1 %cond, label %for.body0, label %for.body
for.body0:
  call void @do_stuff1()
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_fail_bad_loop(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_fail_bad_loop(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[CALL:%.*]] = call i32 @get.i32()
; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[CALL]], 0
; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label %[[FOR_COND:.*]], label %[[HALFWAY:.*]]
; CHECK:       [[FOR_COND]]:
; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ [[INC:%.*]], %[[HALFWAY]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[I_0]], [[N]]
; CHECK-NEXT:    br i1 [[CMP]], label %[[FOR_BODY:.*]], label %[[FOR_END:.*]]
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[I_0]], 1
; CHECK-NEXT:    call void @use.i32(i32 [[XOR]])
; CHECK-NEXT:    br label %[[HALFWAY]]
; CHECK:       [[HALFWAY]]:
; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ poison, %[[ENTRY]] ], [ [[I_0]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_1]], [[REM_AMT]]
; CHECK-NEXT:    call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_1]], 1
; CHECK-NEXT:    br label %[[FOR_COND]]
; CHECK:       [[FOR_END]]:
; CHECK-NEXT:    ret void
;
entry:
  %call = call i32 @get.i32()
  %tobool.not = icmp eq i32 %call, 0
  br i1 %tobool.not, label %for.cond, label %halfway

for.cond:
  %i.0 = phi i32 [ %inc, %halfway ], [ 0, %entry ]
  %cmp = icmp ult i32 %i.0, %N
  br i1 %cmp, label %for.body, label %for.end

for.body:
  %xor = xor i32 %i.0, 1
  call void @use.i32(i32 %xor)
  br label %halfway

halfway:
  %i.1 = phi i32 [ poison, %entry ], [ %i.0, %for.body ]
  %rem = urem i32 %i.1, %rem_amt
  call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.1, 1
  br label %for.cond

for.end:
  ret void
}

define void @simple_urem_fail_intermediate_inc(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_fail_intermediate_inc(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp eq i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 0, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[INC2:%.*]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[INC2]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp eq i32 %N, 0
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  %inc2 = add nuw i32 %i.04, 1
  %rem = urem i32 %inc2, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @weird_loop(i64 %sub.ptr.div.i56) personality ptr null {
; CHECK-LABEL: define void @weird_loop(
; CHECK-SAME: i64 [[SUB_PTR_DIV_I56:%.*]]) personality ptr null {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[ADD74_US:%.*]] = add nuw i64 0, 1
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[ADD74_US]], [[SUB_PTR_DIV_I56]]
; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 0, i64 [[ADD74_US]]
; CHECK-NEXT:    [[ADD74_US1:%.*]] = add nuw i64 0, 1
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    br label %[[FOR_BODY]]
;
entry:
  br label %for.preheader

for.preheader:
  %i57.0540.us = phi i64 [ 0, %entry ], [ %add74.us, %for.body ]
  %add74.us = add nuw i64 %i57.0540.us, 1
  br label %for.body

for.body:
  %rem.us = urem i64 %i57.0540.us, %sub.ptr.div.i56
  br i1 false, label %for.preheader, label %for.body
}

define void @simple_urem_to_sel_non_zero_start_fail(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_non_zero_start_fail(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp ult i32 [[N]], 3
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 2, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_04]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp ult i32 %N, 3
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 2, %entry ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_non_zero_start_okay(i32 %N, i32 %rem_amt_in) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_non_zero_start_okay(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT_IN:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[REM_AMT:%.*]] = or i32 [[REM_AMT_IN]], 16
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp ult i32 [[N]], 3
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[REM:%.*]] = phi i32 [ 2, %[[FOR_BODY_PREHEADER]] ], [ [[TMP3:%.*]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 2, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i32 [[REM]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], [[REM_AMT]]
; CHECK-NEXT:    [[TMP3]] = select i1 [[TMP2]], i32 0, i32 [[TMP1]]
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %rem_amt = or i32 %rem_amt_in, 16
  %cmp3.not = icmp ult i32 %N, 3
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 2, %entry ]
  %rem = urem i32 %i.04, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_non_zero_start_through_add(i32 %N, i32 %rem_amt_in) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_non_zero_start_through_add(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT_IN:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[REM_AMT:%.*]] = or i32 [[REM_AMT_IN]], 16
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp ult i32 [[N]], 3
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[REM:%.*]] = phi i32 [ 7, %[[FOR_BODY_PREHEADER]] ], [ [[TMP3:%.*]], %[[FOR_BODY]] ]
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 2, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i32 [[REM]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], [[REM_AMT]]
; CHECK-NEXT:    [[TMP3]] = select i1 [[TMP2]], i32 0, i32 [[TMP1]]
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %rem_amt = or i32 %rem_amt_in, 16
  %cmp3.not = icmp ult i32 %N, 3
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 2, %entry ]
  %i_with_off = add nuw i32 %i.04, 5
  %rem = urem i32 %i_with_off, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_non_zero_start_through_add_fail_missing_nuw(i32 %N, i32 %rem_amt_in) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_non_zero_start_through_add_fail_missing_nuw(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT_IN:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[REM_AMT:%.*]] = or i32 [[REM_AMT_IN]], 16
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp ult i32 [[N]], 3
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 2, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[I_WITH_OFF:%.*]] = add i32 [[I_04]], 5
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_WITH_OFF]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %rem_amt = or i32 %rem_amt_in, 16
  %cmp3.not = icmp ult i32 %N, 3
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 2, %entry ]
  %i_with_off = add i32 %i.04, 5
  %rem = urem i32 %i_with_off, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_non_zero_start_through_add_fail_no_simplify_rem(i32 %N, i32 %rem_amt) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_non_zero_start_through_add_fail_no_simplify_rem(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp ult i32 [[N]], 3
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ 2, %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[I_WITH_OFF:%.*]] = add nuw i32 [[I_04]], 5
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_WITH_OFF]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp ult i32 %N, 3
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ 2, %entry ]
  %i_with_off = add nuw i32 %i.04, 5
  %rem = urem i32 %i_with_off, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_non_zero_start_through_sub(i32 %N, i32 %rem_amt, i32 %start) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_non_zero_start_through_sub(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]], i32 [[START:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp ule i32 [[N]], [[START]]
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ [[START]], %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[I_WITH_OFF:%.*]] = sub nuw i32 [[I_04]], [[START]]
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_WITH_OFF]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp ule i32 %N, %start
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ %start, %entry ]
  %i_with_off = sub nuw i32 %i.04, %start
  %rem = urem i32 %i_with_off, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @simple_urem_to_sel_non_zero_start_through_sub_no_simplfy(i32 %N, i32 %rem_amt, i32 %start) nounwind {
; CHECK-LABEL: define void @simple_urem_to_sel_non_zero_start_through_sub_no_simplfy(
; CHECK-SAME: i32 [[N:%.*]], i32 [[REM_AMT:%.*]], i32 [[START:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP3_NOT:%.*]] = icmp ule i32 [[N]], [[START]]
; CHECK-NEXT:    br i1 [[CMP3_NOT]], label %[[FOR_COND_CLEANUP:.*]], label %[[FOR_BODY_PREHEADER:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
; CHECK:       [[FOR_COND_CLEANUP]]:
; CHECK-NEXT:    ret void
; CHECK:       [[FOR_BODY]]:
; CHECK-NEXT:    [[I_04:%.*]] = phi i32 [ [[INC:%.*]], %[[FOR_BODY]] ], [ [[START]], %[[FOR_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[I_WITH_OFF:%.*]] = sub nuw i32 [[I_04]], 2
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[I_WITH_OFF]], [[REM_AMT]]
; CHECK-NEXT:    tail call void @use.i32(i32 [[REM]])
; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_04]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label %[[FOR_COND_CLEANUP]], label %[[FOR_BODY]]
;
entry:
  %cmp3.not = icmp ule i32 %N, %start
  br i1 %cmp3.not, label %for.cond.cleanup, label %for.body

for.cond.cleanup:
  ret void

for.body:
  %i.04 = phi i32 [ %inc, %for.body ], [ %start, %entry ]
  %i_with_off = sub nuw i32 %i.04, 2
  %rem = urem i32 %i_with_off, %rem_amt
  tail call void @use.i32(i32 %rem)
  %inc = add nuw i32 %i.04, 1
  %exitcond.not = icmp eq i32 %inc, %N
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}