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

; https://alive2.llvm.org/ce/z/5eCiWi
define i8 @urem_assume(i8 %x, i8 %n) {
; CHECK-LABEL: @urem_assume(
; CHECK-NEXT:    [[X_FR:%.*]] = freeze i8 [[X:%.*]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[X_FR]], [[N:%.*]]
; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X_FR]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[ADD]], [[N]]
; CHECK-NEXT:    [[OUT:%.*]] = select i1 [[TMP1]], i8 0, i8 [[ADD]]
; CHECK-NEXT:    ret i8 [[OUT]]
;
  %cmp = icmp ult i8 %x, %n
  tail call void @llvm.assume(i1 %cmp)
  %add = add nuw i8 %x, 1
  %out = urem i8 %add, %n
  ret i8 %out
}

; https://alive2.llvm.org/ce/z/MGgtYN
define i8 @urem_assume_without_nuw(i8 %x, i8 %n) {
; CHECK-LABEL: @urem_assume_without_nuw(
; CHECK-NEXT:    [[X_FR:%.*]] = freeze i8 [[X:%.*]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[X_FR]], [[N:%.*]]
; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X_FR]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[ADD]], [[N]]
; CHECK-NEXT:    [[OUT:%.*]] = select i1 [[TMP1]], i8 0, i8 [[ADD]]
; CHECK-NEXT:    ret i8 [[OUT]]
;
  %cmp = icmp ult i8 %x, %n
  tail call void @llvm.assume(i1 %cmp)
  %add = add i8 %x, 1
  %out = urem i8 %add, %n
  ret i8 %out
}

; Negative test: The assume is false
define i8 @urem_assume_eq(i8 %x, i8 %n) {
; CHECK-LABEL: @urem_assume_eq(
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], [[N:%.*]]
; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], 1
; CHECK-NEXT:    [[OUT:%.*]] = urem i8 [[ADD]], [[N]]
; CHECK-NEXT:    ret i8 [[OUT]]
;
  %cmp = icmp eq i8 %x, %n
  tail call void @llvm.assume(i1 %cmp)
  %add = add i8 %x, 1
  %out = urem i8 %add, %n
  ret i8 %out
}

; Negative test: The assume is false
define i8 @urem_assume_ne(i8 %x, i8 %n) {
; CHECK-LABEL: @urem_assume_ne(
; CHECK-NEXT:  start:
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[X:%.*]], [[N:%.*]]
; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], 1
; CHECK-NEXT:    [[OUT:%.*]] = urem i8 [[ADD]], [[N]]
; CHECK-NEXT:    ret i8 [[OUT]]
;
start:
  %cmp = icmp ne i8 %x, %n
  tail call void @llvm.assume(i1 %cmp)
  %add = add i8 %x, 1
  %out = urem i8 %add, %n
  ret i8 %out
}

; Negative test: The add constant is not 1
define i8 @urem_assume_with_unexpected_const(i8 %x, i8 %n) {
; CHECK-LABEL: @urem_assume_with_unexpected_const(
; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[X:%.*]], [[N:%.*]]
; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], 2
; CHECK-NEXT:    [[OUT:%.*]] = urem i8 [[ADD]], [[N]]
; CHECK-NEXT:    ret i8 [[OUT]]
;
  %cmp = icmp ult i8 %x, %n
  tail call void @llvm.assume(i1 %cmp)
  %add = add i8 %x, 2            ; Transform only when the constant is 1
  %out = urem i8 %add, %n
  ret i8 %out
}

; https://alive2.llvm.org/ce/z/gNhZ2x
define i8 @urem_without_assume(i8 %arg, i8 %arg2) {
; CHECK-LABEL: @urem_without_assume(
; CHECK-NEXT:    [[X:%.*]] = urem i8 [[ARG:%.*]], [[ARG2:%.*]]
; CHECK-NEXT:    [[X_FR:%.*]] = freeze i8 [[X]]
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X_FR]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[ADD]], [[ARG2]]
; CHECK-NEXT:    [[OUT:%.*]] = select i1 [[TMP1]], i8 0, i8 [[ADD]]
; CHECK-NEXT:    ret i8 [[OUT]]
;
  %x = urem i8 %arg, %arg2
  %add = add i8 %x, 1
  %out = urem i8 %add, %arg2
  ret i8 %out
}

; https://alive2.llvm.org/ce/z/eHkgRa
define i8 @urem_with_dominating_condition(i8 %x, i8 %n) {
; CHECK-LABEL: @urem_with_dominating_condition(
; CHECK-NEXT:  start:
; CHECK-NEXT:    [[X_FR:%.*]] = freeze i8 [[X:%.*]]
; CHECK-NEXT:    [[COND:%.*]] = icmp ult i8 [[X_FR]], [[N:%.*]]
; CHECK-NEXT:    br i1 [[COND]], label [[DOTBB0:%.*]], label [[DOTBB1:%.*]]
; CHECK:       .bb0:
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X_FR]], 1
; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i8 [[ADD]], [[N]]
; CHECK-NEXT:    [[OUT:%.*]] = select i1 [[TMP0]], i8 0, i8 [[ADD]]
; CHECK-NEXT:    ret i8 [[OUT]]
; CHECK:       .bb1:
; CHECK-NEXT:    ret i8 0
;
start:
  %cond = icmp ult i8 %x, %n
  br i1 %cond, label %.bb0, label %.bb1 ; Should also works for a dominating condition
.bb0:
  %add = add i8 %x, 1
  %out = urem i8 %add, %n
  ret i8 %out
.bb1:
  ret i8 0
}

; Revert the dominating condition and target branch at the same time.
define i8 @urem_with_dominating_condition_false(i8 %x, i8 %n) {
; CHECK-LABEL: @urem_with_dominating_condition_false(
; CHECK-NEXT:  start:
; CHECK-NEXT:    [[X_FR:%.*]] = freeze i8 [[X:%.*]]
; CHECK-NEXT:    [[COND_NOT:%.*]] = icmp ult i8 [[X_FR]], [[N:%.*]]
; CHECK-NEXT:    br i1 [[COND_NOT]], label [[DOTBB0:%.*]], label [[DOTBB1:%.*]]
; CHECK:       .bb0:
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X_FR]], 1
; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i8 [[ADD]], [[N]]
; CHECK-NEXT:    [[OUT:%.*]] = select i1 [[TMP0]], i8 0, i8 [[ADD]]
; CHECK-NEXT:    ret i8 [[OUT]]
; CHECK:       .bb1:
; CHECK-NEXT:    ret i8 0
;
start:
  %cond = icmp uge i8 %x, %n
  br i1 %cond, label %.bb1, label %.bb0 ; Swap the branch targets
.bb0:
  %add = add i8 %x, 1
  %out = urem i8 %add, %n
  ret i8 %out
.bb1:
  ret i8 0
}

; Negative test
define noundef i8 @urem_with_opposite_condition(i8 %x, i8 %n) {
; CHECK-LABEL: @urem_with_opposite_condition(
; CHECK-NEXT:    [[COND:%.*]] = icmp ult i8 [[X:%.*]], [[N:%.*]]
; CHECK-NEXT:    br i1 [[COND]], label [[DOTBB1:%.*]], label [[DOTBB0:%.*]]
; CHECK:       .bb0:
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], 1
; CHECK-NEXT:    [[OUT:%.*]] = urem i8 [[ADD]], [[N]]
; CHECK-NEXT:    ret i8 [[OUT]]
; CHECK:       .bb1:
; CHECK-NEXT:    ret i8 0
;
  %cond = icmp ult i8 %x, %n
  br i1 %cond, label %.bb1, label %.bb0 ; Revert the condition
.bb0:
  %add = add i8 %x, 1
  %out = urem i8 %add, %n
  ret i8 %out
.bb1:
  ret i8 0
}

declare void @llvm.assume(i1 noundef)