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

;
; Tests to show cases where computeKnownBits should be able to determine
; the known bits of a phi based on limited recursion.
;

declare i64 @llvm.ctpop.i64(i64)


define i32 @single_entry_phi(i64 %x, i1 %c) {
; CHECK-LABEL: @single_entry_phi(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[BODY:%.*]]
; CHECK:       body:
; CHECK-NEXT:    br i1 [[C:%.*]], label [[END:%.*]], label [[BODY]]
; CHECK:       end:
; CHECK-NEXT:    [[Y:%.*]] = call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 [[X:%.*]])
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc nuw nsw i64 [[Y]] to i32
; CHECK-NEXT:    ret i32 [[TRUNC]]
;
entry:
  %y = call i64 @llvm.ctpop.i64(i64 %x)
  %trunc = trunc i64 %y to i32
  br label %body
body:
  br i1 %c, label %end, label %body
end:
  %phi = phi i32 [ %trunc, %body ]
  %res = and i32 %phi, 127
  ret i32 %res
}


define i32 @two_entry_phi_with_constant(i64 %x, i1 %c) {
; CHECK-LABEL: @two_entry_phi_with_constant(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[Y:%.*]] = call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 [[X:%.*]])
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc nuw nsw i64 [[Y]] to i32
; CHECK-NEXT:    br i1 [[C:%.*]], label [[END:%.*]], label [[BODY:%.*]]
; CHECK:       body:
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[TRUNC]], [[ENTRY:%.*]] ], [ 255, [[BODY]] ]
; CHECK-NEXT:    [[RES:%.*]] = and i32 [[PHI]], 255
; CHECK-NEXT:    ret i32 [[RES]]
;
entry:
  %y = call i64 @llvm.ctpop.i64(i64 %x)
  %trunc = trunc i64 %y to i32
  br i1 %c, label %end, label %body
body:
  br label %end
end:
  %phi = phi i32 [ %trunc, %entry ], [ 255, %body ]
  %res = and i32 %phi, 255
  ret i32 %res
}

define i32 @two_entry_phi_non_constant(i64 %x, i64 %x2, i1 %c) {
; CHECK-LABEL: @two_entry_phi_non_constant(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[Y:%.*]] = call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 [[X:%.*]])
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc nuw nsw i64 [[Y]] to i32
; CHECK-NEXT:    br i1 [[C:%.*]], label [[END:%.*]], label [[BODY:%.*]]
; CHECK:       body:
; CHECK-NEXT:    [[Y2:%.*]] = call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 [[X2:%.*]])
; CHECK-NEXT:    [[TRUNC2:%.*]] = trunc nuw nsw i64 [[Y2]] to i32
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[TRUNC]], [[ENTRY:%.*]] ], [ [[TRUNC2]], [[BODY]] ]
; CHECK-NEXT:    [[RES:%.*]] = and i32 [[PHI]], 255
; CHECK-NEXT:    ret i32 [[RES]]
;
entry:
  %y = call i64 @llvm.ctpop.i64(i64 %x)
  %trunc = trunc i64 %y to i32
  br i1 %c, label %end, label %body
body:
  %y2 = call i64 @llvm.ctpop.i64(i64 %x2)
  %trunc2 = trunc i64 %y2 to i32
  br label %end
end:
  %phi = phi i32 [ %trunc, %entry ], [ %trunc2, %body ]
  %res = and i32 %phi, 255
  ret i32 %res
}

define i32 @neg_many_branches(i64 %x) {
; CHECK-LABEL: @neg_many_branches(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[Y:%.*]] = call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 [[X:%.*]])
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc nuw nsw i64 [[Y]] to i32
; CHECK-NEXT:    switch i32 [[TRUNC]], label [[END:%.*]] [
; CHECK-NEXT:      i32 1, label [[ONE:%.*]]
; CHECK-NEXT:      i32 2, label [[TWO:%.*]]
; CHECK-NEXT:      i32 3, label [[THREE:%.*]]
; CHECK-NEXT:      i32 4, label [[FOUR:%.*]]
; CHECK-NEXT:    ]
; CHECK:       one:
; CHECK-NEXT:    [[A:%.*]] = add nuw nsw i32 [[TRUNC]], 1
; CHECK-NEXT:    br label [[END]]
; CHECK:       two:
; CHECK-NEXT:    [[B:%.*]] = add nuw nsw i32 [[TRUNC]], 2
; CHECK-NEXT:    br label [[END]]
; CHECK:       three:
; CHECK-NEXT:    [[C:%.*]] = add nuw nsw i32 [[TRUNC]], 3
; CHECK-NEXT:    br label [[END]]
; CHECK:       four:
; CHECK-NEXT:    [[D:%.*]] = add nuw nsw i32 [[TRUNC]], 4
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[TRUNC]], [[ENTRY:%.*]] ], [ [[A]], [[ONE]] ], [ [[B]], [[TWO]] ], [ [[C]], [[THREE]] ], [ [[D]], [[FOUR]] ]
; CHECK-NEXT:    [[RES:%.*]] = and i32 [[PHI]], 255
; CHECK-NEXT:    ret i32 [[RES]]
;
entry:
  %y = call i64 @llvm.ctpop.i64(i64 %x)
  %trunc = trunc i64 %y to i32
  switch i32 %trunc, label %end [
  i32 1, label %one
  i32 2, label %two
  i32 3, label %three
  i32 4, label %four
  ]
one:
  %a = add i32 %trunc, 1
  br label %end
two:
  %b = add i32 %trunc, 2
  br label %end
three:
  %c = add i32 %trunc, 3
  br label %end
four:
  %d = add i32 %trunc, 4
  br label %end
end:
  %phi = phi i32 [ %trunc, %entry ], [ %a, %one ], [ %b, %two ], [ %c, %three ], [ %d, %four ]
  %res = and i32 %phi, 255
  ret i32 %res
}