; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -instsimplify < %s -S | FileCheck %s

define i1 @test(i8* %pq, i8 %B) {
; CHECK-LABEL: @test(
; CHECK-NEXT:    ret i1 false
;
  %q = load i8, i8* %pq, !range !0 ; %q is known nonzero; no known bits
  %A = add nsw i8 %B, %q
  %cmp = icmp eq i8 %A, %B
  ret i1 %cmp
}

define i1 @test2(i8 %a, i8 %b) {
; CHECK-LABEL: @test2(
; CHECK-NEXT:    ret i1 false
;
  %A = or i8 %a, 2    ; %A[1] = 1
  %B = and i8 %b, -3  ; %B[1] = 0
  %cmp = icmp eq i8 %A, %B ; %A[1] and %B[1] are contradictory.
  ret i1 %cmp
}

define i1 @test3(i8 %B) {
; CHECK-LABEL: @test3(
; CHECK-NEXT:    ret i1 false
;
  %A = add nsw i8 %B, 1
  %cmp = icmp eq i8 %A, %B
  ret i1 %cmp
}

define i1 @sext(i8 %B) {
; CHECK-LABEL: @sext(
; CHECK-NEXT:    ret i1 false
;
  %A = add nsw i8 %B, 1
  %A.cast = sext i8 %A to i32
  %B.cast = sext i8 %B to i32
  %cmp = icmp eq i32 %A.cast, %B.cast
  ret i1 %cmp
}

define i1 @zext(i8 %B) {
; CHECK-LABEL: @zext(
; CHECK-NEXT:    ret i1 false
;
  %A = add nsw i8 %B, 1
  %A.cast = zext i8 %A to i32
  %B.cast = zext i8 %B to i32
  %cmp = icmp eq i32 %A.cast, %B.cast
  ret i1 %cmp
}

define i1 @inttoptr(i32 %B) {
; CHECK-LABEL: @inttoptr(
; CHECK-NEXT:    [[A:%.*]] = add nsw i32 [[B:%.*]], 1
; CHECK-NEXT:    [[A_CAST:%.*]] = inttoptr i32 [[A]] to i8*
; CHECK-NEXT:    [[B_CAST:%.*]] = inttoptr i32 [[B]] to i8*
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8* [[A_CAST]], [[B_CAST]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A = add nsw i32 %B, 1
  %A.cast = inttoptr i32 %A to i8*
  %B.cast = inttoptr i32 %B to i8*
  %cmp = icmp eq i8* %A.cast, %B.cast
  ret i1 %cmp
}

define i1 @ptrtoint(i32* %B) {
; CHECK-LABEL: @ptrtoint(
; CHECK-NEXT:    [[A:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i32 1
; CHECK-NEXT:    [[A_CAST:%.*]] = ptrtoint i32* [[A]] to i32
; CHECK-NEXT:    [[B_CAST:%.*]] = ptrtoint i32* [[B]] to i32
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[A_CAST]], [[B_CAST]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A = getelementptr inbounds i32, i32* %B, i32 1
  %A.cast = ptrtoint i32* %A to i32
  %B.cast = ptrtoint i32* %B to i32
  %cmp = icmp eq i32 %A.cast, %B.cast
  ret i1 %cmp
}

define i1 @add1(i8 %B, i8 %C) {
; CHECK-LABEL: @add1(
; CHECK-NEXT:    ret i1 false
;
  %A = add i8 %B, 1
  %A.op = add i8 %A, %C
  %B.op = add i8 %B, %C

  %cmp = icmp eq i8 %A.op, %B.op
  ret i1 %cmp
}

define i1 @add2(i8 %B, i8 %C) {
; CHECK-LABEL: @add2(
; CHECK-NEXT:    ret i1 false
;
  %A = add i8 %B, 1
  %A.op = add i8 %C, %A
  %B.op = add i8 %C, %B

  %cmp = icmp eq i8 %A.op, %B.op
  ret i1 %cmp
}

define i1 @sub1(i8 %B, i8 %C) {
; CHECK-LABEL: @sub1(
; CHECK-NEXT:    ret i1 false
;
  %A = add i8 %B, 1
  %A.op = sub i8 %A, %C
  %B.op = sub i8 %B, %C

  %cmp = icmp eq i8 %A.op, %B.op
  ret i1 %cmp
}

define i1 @sub2(i8 %B, i8 %C) {
; CHECK-LABEL: @sub2(
; CHECK-NEXT:    ret i1 false
;
  %A = add i8 %B, 1
  %A.op = sub i8 %C, %A
  %B.op = sub i8 %C, %B

  %cmp = icmp eq i8 %A.op, %B.op
  ret i1 %cmp
}

; op could wrap mapping two values to the same output value.
define i1 @mul1(i8 %B) {
; CHECK-LABEL: @mul1(
; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
; CHECK-NEXT:    [[A_OP:%.*]] = mul i8 [[A]], 27
; CHECK-NEXT:    [[B_OP:%.*]] = mul i8 [[B]], 27
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP]], [[B_OP]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A = add i8 %B, 1
  %A.op = mul i8 %A, 27
  %B.op = mul i8 %B, 27

  %cmp = icmp eq i8 %A.op, %B.op
  ret i1 %cmp
}

define i1 @mul2(i8 %B) {
; CHECK-LABEL: @mul2(
; CHECK-NEXT:    ret i1 false
;
  %A = add i8 %B, 1
  %A.op = mul nuw i8 %A, 27
  %B.op = mul nuw i8 %B, 27

  %cmp = icmp eq i8 %A.op, %B.op
  ret i1 %cmp
}

define i1 @mul3(i8 %B) {
; CHECK-LABEL: @mul3(
; CHECK-NEXT:    ret i1 false
;
  %A = add i8 %B, 1
  %A.op = mul nsw i8 %A, 27
  %B.op = mul nsw i8 %B, 27

  %cmp = icmp eq i8 %A.op, %B.op
  ret i1 %cmp
}

; Multiply by zero collapses all values to one
define i1 @mul4(i8 %B) {
; CHECK-LABEL: @mul4(
; CHECK-NEXT:    ret i1 true
;
  %A = add i8 %B, 1
  %A.op = mul nuw i8 %A, 0
  %B.op = mul nuw i8 %B, 0

  %cmp = icmp eq i8 %A.op, %B.op
  ret i1 %cmp
}

; C might be zero, we can't tell
define i1 @mul5(i8 %B, i8 %C) {
; CHECK-LABEL: @mul5(
; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
; CHECK-NEXT:    [[A_OP:%.*]] = mul nuw nsw i8 [[A]], [[C:%.*]]
; CHECK-NEXT:    [[B_OP:%.*]] = mul nuw nsw i8 [[B]], [[C]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP]], [[B_OP]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A = add i8 %B, 1
  %A.op = mul nsw nuw i8 %A, %C
  %B.op = mul nsw nuw i8 %B, %C

  %cmp = icmp eq i8 %A.op, %B.op
  ret i1 %cmp
}

@g = external global i16, align 1

define i1 @mul_constantexpr(i16 %a) {
; CHECK-LABEL: @mul_constantexpr(
; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i16 [[A:%.*]], 3
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 mul nsw (i16 ptrtoint (i16* @g to i16), i16 -1), [[MUL]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul nsw i16 %a, 3
  %cmp = icmp eq i16 mul nsw (i16 ptrtoint (i16* @g to i16), i16 -1), %mul
  ret i1 %cmp
}

define i1 @mul_nuw(i16 %x) {
; CHECK-LABEL: @mul_nuw(
; CHECK-NEXT:    ret i1 false
;
  %nz = or i16 %x, 2
  %mul = mul nuw i16 %nz, 2
  %cmp = icmp eq i16 %nz, %mul
  ret i1 %cmp
}

define i1 @mul_nuw_comm(i16 %x) {
; CHECK-LABEL: @mul_nuw_comm(
; CHECK-NEXT:    ret i1 false
;
  %nz = or i16 %x, 2
  %mul = mul nuw i16 %nz, 2
  %cmp = icmp eq i16 %mul, %nz
  ret i1 %cmp
}

define i1 @mul_nsw(i16 %x) {
; CHECK-LABEL: @mul_nsw(
; CHECK-NEXT:    ret i1 false
;
  %nz = or i16 %x, 2
  %mul = mul nsw i16 %nz, 2
  %cmp = icmp eq i16 %nz, %mul
  ret i1 %cmp
}

define i1 @mul_nsw_comm(i16 %x) {
; CHECK-LABEL: @mul_nsw_comm(
; CHECK-NEXT:    ret i1 false
;
  %nz = or i16 %x, 2
  %mul = mul nsw i16 %nz, 2
  %cmp = icmp eq i16 %mul, %nz
  ret i1 %cmp
}

define i1 @mul_may_wrap(i16 %x) {
; CHECK-LABEL: @mul_may_wrap(
; CHECK-NEXT:    [[NZ:%.*]] = or i16 [[X:%.*]], 2
; CHECK-NEXT:    [[MUL:%.*]] = mul i16 [[NZ]], 2
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %nz = or i16 %x, 2
  %mul = mul i16 %nz, 2
  %cmp = icmp eq i16 %nz, %mul
  ret i1 %cmp
}

define i1 @mul_may_be_zero(i16 %x) {
; CHECK-LABEL: @mul_may_be_zero(
; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i16 [[X:%.*]], 2
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[X]], [[MUL]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = mul nuw i16 %x, 2
  %cmp = icmp eq i16 %x, %mul
  ret i1 %cmp
}

define i1 @mul_other_may_be_zero_or_one(i16 %x, i16 %y) {
; CHECK-LABEL: @mul_other_may_be_zero_or_one(
; CHECK-NEXT:    [[NZ:%.*]] = or i16 [[X:%.*]], 2
; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i16 [[NZ]], [[Y:%.*]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %nz = or i16 %x, 2
  %mul = mul nuw i16 %nz, %y
  %cmp = icmp eq i16 %nz, %mul
  ret i1 %cmp
}

define i1 @known_non_equal_phis(i8 %p, i8* %pq, i8 %n, i8 %r) {
; CHECK-LABEL: @known_non_equal_phis(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[A:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[NEXT]] = mul nsw i8 [[A]], 2
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 true
;
entry:
  br label %loop
loop:
  %A = phi i8 [ 2, %entry ], [ %next, %loop ]
  %B = phi i8 [ 3, %entry ], [ %A, %loop ]
  %next = mul nsw i8 %A, 2
  %cmp1 = icmp eq i8 %A, %n
  br i1 %cmp1, label %exit, label %loop
exit:
  %cmp = icmp ne i8 %A, %B
  ret i1 %cmp
}

define i1 @known_non_equal_phis_fail(i8 %p, i8* %pq, i8 %n, i8 %r) {
; CHECK-LABEL: @known_non_equal_phis_fail(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[A:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B:%.*]] = phi i8 [ 2, [[ENTRY]] ], [ [[A]], [[LOOP]] ]
; CHECK-NEXT:    [[NEXT]] = mul nsw i8 [[A]], 2
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[A]], [[N:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[EXIT:%.*]], label [[LOOP]]
; CHECK:       exit:
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[A]], [[B]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
entry:
  br label %loop
loop:
  %A = phi i8 [ 2, %entry ], [ %next, %loop ]
  %B = phi i8 [ 2, %entry ], [ %A, %loop ]
  %next = mul nsw i8 %A, 2
  %cmp1 = icmp eq i8 %A, %n
  br i1 %cmp1, label %exit, label %loop
exit:
  %cmp = icmp ne i8 %A, %B
  ret i1 %cmp
}

define i1 @shl_nuw(i16 %x) {
; CHECK-LABEL: @shl_nuw(
; CHECK-NEXT:    ret i1 false
;
  %nz = or i16 %x, 2
  %mul = shl nuw i16 %nz, 1
  %cmp = icmp eq i16 %nz, %mul
  ret i1 %cmp
}

define i1 @shl_nsw(i16 %x) {
; CHECK-LABEL: @shl_nsw(
; CHECK-NEXT:    ret i1 false
;
  %nz = or i16 %x, 2
  %mul = shl nsw i16 %nz, 1
  %cmp = icmp eq i16 %nz, %mul
  ret i1 %cmp
}

define i1 @shl_may_wrap(i16 %x) {
; CHECK-LABEL: @shl_may_wrap(
; CHECK-NEXT:    [[NZ:%.*]] = or i16 [[X:%.*]], 2
; CHECK-NEXT:    [[MUL:%.*]] = shl i16 [[NZ]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %nz = or i16 %x, 2
  %mul = shl i16 %nz, 1
  %cmp = icmp eq i16 %nz, %mul
  ret i1 %cmp
}

define i1 @shl_shift_may_be_zero(i16 %x, i16 %shift) {
; CHECK-LABEL: @shl_shift_may_be_zero(
; CHECK-NEXT:    [[NZ:%.*]] = or i16 [[X:%.*]], 2
; CHECK-NEXT:    [[MUL:%.*]] = shl nuw i16 [[NZ]], [[SHIFT:%.*]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[NZ]], [[MUL]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %nz = or i16 %x, 2
  %mul = shl nuw i16 %nz, %shift
  %cmp = icmp eq i16 %nz, %mul
  ret i1 %cmp
}

define i1 @shl_op_may_be_zero(i16 %x) {
; CHECK-LABEL: @shl_op_may_be_zero(
; CHECK-NEXT:    [[MUL:%.*]] = shl nuw i16 [[X:%.*]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[X]], [[MUL]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %mul = shl nuw i16 %x, 1
  %cmp = icmp eq i16 %x, %mul
  ret i1 %cmp
}

; The additional muls in these tests are necessary to actually
; test the isKnownNonEqual() code, rather than InstSimplify's own
; comparison folding.

define i1 @shl_shl_nuw(i8 %B, i8 %shift) {
; CHECK-LABEL: @shl_shl_nuw(
; CHECK-NEXT:    ret i1 false
;
  %A = add i8 %B, 1
  %A.op = shl nuw i8 %A, %shift
  %B.op = shl nuw i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @shl_shl_nsw(i8 %B, i8 %shift) {
; CHECK-LABEL: @shl_shl_nsw(
; CHECK-NEXT:    ret i1 false
;
  %A = add i8 %B, 1
  %A.op = shl nsw i8 %A, %shift
  %B.op = shl nsw i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @shl_shl_may_wrap(i8 %B, i8 %shift) {
; CHECK-LABEL: @shl_shl_may_wrap(
; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
; CHECK-NEXT:    [[A_OP:%.*]] = shl i8 [[A]], [[SHIFT:%.*]]
; CHECK-NEXT:    [[B_OP:%.*]] = shl nsw i8 [[B]], [[SHIFT]]
; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A = add i8 %B, 1
  %A.op = shl i8 %A, %shift
  %B.op = shl nsw i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @shl_shl_mixed_wrap(i8 %B, i8 %shift) {
; CHECK-LABEL: @shl_shl_mixed_wrap(
; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
; CHECK-NEXT:    [[A_OP:%.*]] = shl nuw i8 [[A]], [[SHIFT:%.*]]
; CHECK-NEXT:    [[B_OP:%.*]] = shl nsw i8 [[B]], [[SHIFT]]
; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A = add i8 %B, 1
  %A.op = shl nuw i8 %A, %shift
  %B.op = shl nsw i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @shl_shl_may_be_equal(i8 %A, i8 %B, i8 %shift) {
; CHECK-LABEL: @shl_shl_may_be_equal(
; CHECK-NEXT:    [[A_OP:%.*]] = shl nuw i8 [[A:%.*]], [[SHIFT:%.*]]
; CHECK-NEXT:    [[B_OP:%.*]] = shl nuw i8 [[B:%.*]], [[SHIFT]]
; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A.op = shl nuw i8 %A, %shift
  %B.op = shl nuw i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @ashr_ashr_exact(i8 %B, i8 %shift) {
; CHECK-LABEL: @ashr_ashr_exact(
; CHECK-NEXT:    ret i1 false
;
  %A = add i8 %B, 1
  %A.op = ashr exact i8 %A, %shift
  %B.op = ashr exact i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @ashr_ashr_discard_bits(i8 %B, i8 %shift) {
; CHECK-LABEL: @ashr_ashr_discard_bits(
; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
; CHECK-NEXT:    [[A_OP:%.*]] = ashr i8 [[A]], [[SHIFT:%.*]]
; CHECK-NEXT:    [[B_OP:%.*]] = ashr exact i8 [[B]], [[SHIFT]]
; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A = add i8 %B, 1
  %A.op = ashr i8 %A, %shift
  %B.op = ashr exact i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @ashr_ashr_may_be_equal(i8 %A, i8 %B, i8 %shift) {
; CHECK-LABEL: @ashr_ashr_may_be_equal(
; CHECK-NEXT:    [[A_OP:%.*]] = ashr exact i8 [[A:%.*]], [[SHIFT:%.*]]
; CHECK-NEXT:    [[B_OP:%.*]] = ashr exact i8 [[B:%.*]], [[SHIFT]]
; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A.op = ashr exact i8 %A, %shift
  %B.op = ashr exact i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @lshr_lshr_exact(i8 %B, i8 %shift) {
; CHECK-LABEL: @lshr_lshr_exact(
; CHECK-NEXT:    ret i1 false
;
  %A = add i8 %B, 1
  %A.op = lshr exact i8 %A, %shift
  %B.op = lshr exact i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @lshr_lshr_discard_bits(i8 %B, i8 %shift) {
; CHECK-LABEL: @lshr_lshr_discard_bits(
; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
; CHECK-NEXT:    [[A_OP:%.*]] = lshr i8 [[A]], [[SHIFT:%.*]]
; CHECK-NEXT:    [[B_OP:%.*]] = lshr exact i8 [[B]], [[SHIFT]]
; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A = add i8 %B, 1
  %A.op = lshr i8 %A, %shift
  %B.op = lshr exact i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @lshr_lshr_may_be_equal(i8 %A, i8 %B, i8 %shift) {
; CHECK-LABEL: @lshr_lshr_may_be_equal(
; CHECK-NEXT:    [[A_OP:%.*]] = lshr exact i8 [[A:%.*]], [[SHIFT:%.*]]
; CHECK-NEXT:    [[B_OP:%.*]] = lshr exact i8 [[B:%.*]], [[SHIFT]]
; CHECK-NEXT:    [[A_OP2:%.*]] = mul nuw i8 [[A_OP]], 3
; CHECK-NEXT:    [[B_OP2:%.*]] = mul nuw i8 [[B_OP]], 3
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP2]], [[B_OP2]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %A.op = lshr exact i8 %A, %shift
  %B.op = lshr exact i8 %B, %shift
  %A.op2 = mul nuw i8 %A.op, 3
  %B.op2 = mul nuw i8 %B.op, 3
  %cmp = icmp eq i8 %A.op2, %B.op2
  ret i1 %cmp
}

define i1 @recurrence_add_neq(i8 %A) {
; CHECK-LABEL: @recurrence_add_neq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = add i8 %A.iv, 1
  %B.iv.next = add i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_add_eq(i8 %A) {
; CHECK-LABEL: @recurrence_add_eq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 0
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = add i8 %A.iv, 1
  %B.iv.next = add i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_add_unknown(i8 %A, i8 %B) {
; CHECK-LABEL: @recurrence_add_unknown(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = add i8 %A.iv, 1
  %B.iv.next = add i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

; If the steps are different, the invertibility is not enough
; (Though, in this case, we could prove neq with different logic)
define i1 @recurrence_add_diff_step(i8 %A) {
; CHECK-LABEL: @recurrence_add_diff_step(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 2
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = add i8 %A.iv, 1
  %B.iv.next = add i8 %B.iv, 2
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_add_op_order(i8 %A) {
; CHECK-LABEL: @recurrence_add_op_order(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 1, [[A_IV]]
; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 1, [[B_IV]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = add i8 1, %A.iv
  %B.iv.next = add i8 1, %B.iv
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

; Just to show that phi operand order doesn't matter
define i1 @recurrence_add_neq_phi_order(i8 %A) {
; CHECK-LABEL: @recurrence_add_neq_phi_order(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A_IV_NEXT:%.*]], [[LOOP]] ], [ [[A]], [[ENTRY]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B_IV_NEXT:%.*]], [[LOOP]] ], [ [[B]], [[ENTRY]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [%iv.next, %loop], [0, %entry]
  %A.iv = phi i8 [%A.iv.next, %loop], [%A, %entry]
  %B.iv = phi i8 [%B.iv.next, %loop], [%B, %entry]
  %iv.next = add i64 %iv, 1
  %A.iv.next = add i8 %A.iv, 1
  %B.iv.next = add i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

; Demonstrate case where phi operand orders differ and thus
; there's no single operand index to recurse through
define i1 @recurrence_add_phi_different_order1(i8 %A) {
; CHECK-LABEL: @recurrence_add_phi_different_order1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B_IV_NEXT:%.*]], [[LOOP]] ], [ [[B]], [[ENTRY]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [%iv.next, %loop], [0, %entry]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B.iv.next, %loop], [%B, %entry]
  %iv.next = add i64 %iv, 1
  %A.iv.next = add i8 %A.iv, 1
  %B.iv.next = add i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_add_phi_different_order2(i8 %A) {
; CHECK-LABEL: @recurrence_add_phi_different_order2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A_IV_NEXT:%.*]], [[LOOP]] ], [ [[A]], [[ENTRY]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = add i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = add i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [%iv.next, %loop], [0, %entry]
  %A.iv = phi i8 [%A.iv.next, %loop], [%A, %entry]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = add i8 %A.iv, 1
  %B.iv.next = add i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_sub_neq(i8 %A) {
; CHECK-LABEL: @recurrence_sub_neq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = sub i8 %A.iv, 1
  %B.iv.next = sub i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_sub_eq(i8 %A) {
; CHECK-LABEL: @recurrence_sub_eq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 0
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = sub i8 %A.iv, 1
  %B.iv.next = sub i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_sub_unknown(i8 %A, i8 %B) {
; CHECK-LABEL: @recurrence_sub_unknown(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = sub i8 %A.iv, 1
  %B.iv.next = sub i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_sub_op_order(i8 %A) {
; CHECK-LABEL: @recurrence_sub_op_order(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 1, [[A_IV]]
; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 1, [[B_IV]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = sub i8 1, %A.iv
  %B.iv.next = sub i8 1, %B.iv
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_sub_op_order2(i8 %A) {
; CHECK-LABEL: @recurrence_sub_op_order2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 1, [[A_IV]]
; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = sub i8 1, %A.iv
  %B.iv.next = sub i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}


define i1 @recurrence_mul_neq(i8 %A) {
; CHECK-LABEL: @recurrence_mul_neq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = mul nuw i8 [[A_IV]], 2
; CHECK-NEXT:    [[B_IV_NEXT]] = mul nuw i8 [[B_IV]], 2
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = mul nuw i8 %A.iv, 2
  %B.iv.next = mul nuw i8 %B.iv, 2
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_mul_eq(i8 %A) {
; CHECK-LABEL: @recurrence_mul_eq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = mul nuw i8 [[A_IV]], 2
; CHECK-NEXT:    [[B_IV_NEXT]] = mul nuw i8 [[B_IV]], 2
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 0
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = mul nuw i8 %A.iv, 2
  %B.iv.next = mul nuw i8 %B.iv, 2
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_mul_unknown(i8 %A, i8 %B) {
; CHECK-LABEL: @recurrence_mul_unknown(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = mul nuw i8 [[A_IV]], 2
; CHECK-NEXT:    [[B_IV_NEXT]] = mul nuw i8 [[B_IV]], 2
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = mul nuw i8 %A.iv, 2
  %B.iv.next = mul nuw i8 %B.iv, 2
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_mul_noflags(i8 %A) {
; CHECK-LABEL: @recurrence_mul_noflags(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = mul i8 [[A_IV]], 2
; CHECK-NEXT:    [[B_IV_NEXT]] = mul i8 [[B_IV]], 2
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = mul i8 %A.iv, 2
  %B.iv.next = mul i8 %B.iv, 2
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_shl_neq(i8 %A) {
; CHECK-LABEL: @recurrence_shl_neq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = shl nuw i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = shl nuw i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = shl nuw i8 %A.iv, 1
  %B.iv.next = shl nuw i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_shl_eq(i8 %A) {
; CHECK-LABEL: @recurrence_shl_eq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = shl nuw i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = shl nuw i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 0
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = shl nuw i8 %A.iv, 1
  %B.iv.next = shl nuw i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_shl_unknown(i8 %A, i8 %B) {
; CHECK-LABEL: @recurrence_shl_unknown(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = shl nuw i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = shl nuw i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = shl nuw i8 %A.iv, 1
  %B.iv.next = shl nuw i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_shl_noflags(i8 %A) {
; CHECK-LABEL: @recurrence_shl_noflags(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = shl i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = shl i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = shl i8 %A.iv, 1
  %B.iv.next = shl i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

; Represents a power function, but still invertable!
define i1 @recurrence_shl_op_order(i8 %A) {
; CHECK-LABEL: @recurrence_shl_op_order(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = shl nuw i8 1, [[A_IV]]
; CHECK-NEXT:    [[B_IV_NEXT]] = shl nuw i8 1, [[B_IV]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = shl nuw i8 1, %A.iv
  %B.iv.next = shl nuw i8 1, %B.iv
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_lshr_neq(i8 %A) {
; CHECK-LABEL: @recurrence_lshr_neq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = lshr exact i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = lshr exact i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = lshr exact i8 %A.iv, 1
  %B.iv.next = lshr exact i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_lshr_eq(i8 %A) {
; CHECK-LABEL: @recurrence_lshr_eq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = lshr exact i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = lshr exact i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 0
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = lshr exact i8 %A.iv, 1
  %B.iv.next = lshr exact i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_lshr_unknown(i8 %A, i8 %B) {
; CHECK-LABEL: @recurrence_lshr_unknown(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = lshr exact i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = lshr exact i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = lshr exact i8 %A.iv, 1
  %B.iv.next = lshr exact i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_lshr_noflags(i8 %A) {
; CHECK-LABEL: @recurrence_lshr_noflags(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = lshr i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = lshr i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = lshr i8 %A.iv, 1
  %B.iv.next = lshr i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_lshr_op_order(i8 %A) {
; CHECK-LABEL: @recurrence_lshr_op_order(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ 1, [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ 1, [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = lshr exact i8 1, %A.iv
  %B.iv.next = lshr exact i8 1, %B.iv
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}


define i1 @recurrence_ashr_neq(i8 %A) {
; CHECK-LABEL: @recurrence_ashr_neq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = ashr exact i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = ashr exact i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i1 false
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = ashr exact i8 %A.iv, 1
  %B.iv.next = ashr exact i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_ashr_eq(i8 %A) {
; CHECK-LABEL: @recurrence_ashr_eq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = ashr exact i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = ashr exact i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 0
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = ashr exact i8 %A.iv, 1
  %B.iv.next = ashr exact i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_ashr_unknown(i8 %A, i8 %B) {
; CHECK-LABEL: @recurrence_ashr_unknown(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B:%.*]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = ashr exact i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = ashr exact i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = ashr exact i8 %A.iv, 1
  %B.iv.next = ashr exact i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @recurrence_ashr_noflags(i8 %A) {
; CHECK-LABEL: @recurrence_ashr_noflags(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = ashr i8 [[A_IV]], 1
; CHECK-NEXT:    [[B_IV_NEXT]] = ashr i8 [[B_IV]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = ashr i8 %A.iv, 1
  %B.iv.next = ashr i8 %B.iv, 1
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @PR50191_A(i32 %x) {
; CHECK-LABEL: @PR50191_A(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[P1:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY]] ], [ [[SUB1:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[P2:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[SUB2:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[SUB1]] = sub i32 [[P1]], [[P2]]
; CHECK-NEXT:    [[SUB2]] = sub i32 42, [[P2]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i32 [[P1]], [[P2]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %p1 = phi i32 [%x, %entry ], [ %sub1, %loop ]
  %p2 = phi i32 [%x, %entry ], [ %sub2, %loop ]
  %iv.next = add i64 %iv, 1
  %sub1 = sub i32 %p1, %p2
  %sub2 = sub i32 42, %p2
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i32 %p1, %p2
  ret i1 %res
}

define i1 @PR50191_B(i32 %x) {
; CHECK-LABEL: @PR50191_B(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[P1:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY]] ], [ [[SUB1:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[P2:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[SUB2:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[SUB1]] = sub i32 [[P2]], [[P1]]
; CHECK-NEXT:    [[SUB2]] = sub i32 [[P2]], 42
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i32 [[P1]], [[P2]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %p1 = phi i32 [%x, %entry ], [ %sub1, %loop ]
  %p2 = phi i32 [%x, %entry ], [ %sub2, %loop ]
  %iv.next = add i64 %iv, 1
  %sub1 = sub i32 %p2, %p1
  %sub2 = sub i32 %p2, 42
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i32 %p1, %p2
  ret i1 %res
}


define i1 @mutual_recurrence_neq(i8 %A) {
; CHECK-LABEL: @mutual_recurrence_neq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[A_IV_NEXT]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%A.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = sub i8 %A.iv, %B.iv
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

define i1 @mutual_recurrence_eq(i8 %A) {
; CHECK-LABEL: @mutual_recurrence_eq(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A:%.*]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = sub i8 %A.iv, %B.iv
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}

; Illustrate a case where A_IV_i == B_IV_i for all i > 0, but A_IV_0 != B_IV_0.
; (E.g. This pair of mutually defined recurrences are not invertible.)
define i1 @recurrence_collapse(i8 %A) {
; CHECK-LABEL: @recurrence_collapse(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[B:%.*]] = add i8 [[A:%.*]], 1
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[A_IV:%.*]] = phi i8 [ [[A]], [[ENTRY]] ], [ [[A_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[B_IV:%.*]] = phi i8 [ [[B]], [[ENTRY]] ], [ [[B_IV_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[A_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    [[B_IV_NEXT]] = sub i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[IV_NEXT]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[A_IV]], [[B_IV]]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %B = add i8 %A, 1
  br label %loop
loop:
  %iv = phi i64 [0, %entry], [%iv.next, %loop]
  %A.iv = phi i8 [%A, %entry], [%A.iv.next, %loop]
  %B.iv = phi i8 [%B, %entry], [%B.iv.next, %loop]
  %iv.next = add i64 %iv, 1
  %A.iv.next = sub i8 %A.iv, %B.iv
  %B.iv.next = sub i8 %A.iv, %B.iv
  %cmp = icmp ne i64 %iv.next, 10
  br i1 %cmp, label %loop, label %exit
exit:
  %res = icmp eq i8 %A.iv, %B.iv
  ret i1 %res
}


!0 = !{ i8 1, i8 5 }