diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
--- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
@@ -147,7 +147,10 @@
   State(DominatorTree &DT) : DT(DT) {}
 
   /// Process block \p BB and add known facts to work-list.
-  void addInfoFor(BasicBlock &BB);
+  /// If we cannot add a fact with an existing ICmpInst, temporary ICmpInst will
+  /// be created.
+  void addInfoFor(BasicBlock &BB,
+                  SmallVectorImpl<Instruction *> &TemporaryInsts);
 
   /// Returns true if we can add a known condition from BB to its successor
   /// block Succ.
@@ -762,7 +765,8 @@
 }
 #endif
 
-void State::addInfoFor(BasicBlock &BB) {
+void State::addInfoFor(BasicBlock &BB,
+                       SmallVectorImpl<Instruction *> &TemporaryInsts) {
   // True as long as long as the current instruction is guaranteed to execute.
   bool GuaranteedToExecute = true;
   // Queue conditions and assumes.
@@ -784,6 +788,25 @@
       continue;
     }
 
+    auto CreateTemporaryICmp = [&](ICmpInst::Predicate Pred, Value *Lhs,
+                                   Value *Rhs) {
+      auto Cmp = ICmpInst::Create(ICmpInst::ICmp, Pred, Lhs, Rhs);
+      TemporaryInsts.push_back(Cmp);
+      return Cmp;
+    };
+
+    if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(&I)) {
+      ICmpInst::Predicate Pred =
+          ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
+      WorkList.push_back(FactOrCheck::getFact(
+          DT.getNode(&BB),
+          CreateTemporaryICmp(Pred, MinMax, MinMax->getOperand(0))));
+      WorkList.push_back(FactOrCheck::getFact(
+          DT.getNode(&BB),
+          CreateTemporaryICmp(Pred, MinMax, MinMax->getOperand(1))));
+      continue;
+    }
+
     Value *Cond;
     // For now, just handle assumes with a single compare as condition.
     if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
@@ -1274,10 +1297,11 @@
 
   // First, collect conditions implied by branches and blocks with their
   // Dominator DFS in and out numbers.
+  SmallVector<Instruction *> TemporaryInsts;
   for (BasicBlock &BB : F) {
     if (!DT.getNode(&BB))
       continue;
-    S.addInfoFor(BB);
+    S.addInfoFor(BB, TemporaryInsts);
   }
 
   // Next, sort worklist by dominance, so that dominating conditions to check
@@ -1419,6 +1443,8 @@
 
   for (Instruction *I : ToRemove)
     I->eraseFromParent();
+  for (Instruction *I : TemporaryInsts)
+    I->deleteValue();
   return Changed;
 }
 
diff --git a/llvm/test/Transforms/ConstraintElimination/minmax.ll b/llvm/test/Transforms/ConstraintElimination/minmax.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/ConstraintElimination/minmax.ll
@@ -0,0 +1,392 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
+
+; Test from PR63896
+define i1 @umax_ugt_ugt(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @umax_ugt_ugt
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.umax.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[Y]], [[MAX]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %max = call i32 @llvm.umax.i32(i32 %x, i32 1)
+  %cmp = icmp ugt i32 %y, %max
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp ugt i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @umax_ugt_uge(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @umax_ugt_uge
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.umax.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[Y]], [[MAX]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %max = call i32 @llvm.umax.i32(i32 %x, i32 1)
+  %cmp = icmp ugt i32 %y, %max
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp uge i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @umax_uge_ugt_nofold(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @umax_uge_ugt_nofold
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.umax.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[Y]], [[MAX]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %max = call i32 @llvm.umax.i32(i32 %x, i32 1)
+  %cmp = icmp uge i32 %y, %max
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp ugt i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @umax_uge_uge(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @umax_uge_uge
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.umax.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[Y]], [[MAX]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %max = call i32 @llvm.umax.i32(i32 %x, i32 1)
+  %cmp = icmp uge i32 %y, %max
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp uge i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @umin_ult_ult(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @umin_ult_ult
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.umin.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[Y]], [[MIN]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %min = call i32 @llvm.umin.i32(i32 %x, i32 1)
+  %cmp = icmp ult i32 %y, %min
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp ult i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @umin_ult_ule(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @umin_ult_ule
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.umin.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[Y]], [[MIN]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %min = call i32 @llvm.umin.i32(i32 %x, i32 1)
+  %cmp = icmp ult i32 %y, %min
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp ule i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @umin_ule_ult_nofold(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @umin_ule_ult_nofold
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.umin.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[Y]], [[MIN]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %min = call i32 @llvm.umin.i32(i32 %x, i32 1)
+  %cmp = icmp ule i32 %y, %min
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp ult i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @umin_ule_ule(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @umin_ule_ule
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.umin.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[Y]], [[MIN]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ule i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %min = call i32 @llvm.umin.i32(i32 %x, i32 1)
+  %cmp = icmp ule i32 %y, %min
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp ule i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @smax_sgt_sgt(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @smax_sgt_sgt
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[Y]], [[MAX]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %max = call i32 @llvm.smax.i32(i32 %x, i32 1)
+  %cmp = icmp sgt i32 %y, %max
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp sgt i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @smax_sgt_sge(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @smax_sgt_sge
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[Y]], [[MAX]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sge i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %max = call i32 @llvm.smax.i32(i32 %x, i32 1)
+  %cmp = icmp sgt i32 %y, %max
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp sge i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @smax_sge_sgt_nofold(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @smax_sge_sgt_nofold
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[Y]], [[MAX]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %max = call i32 @llvm.smax.i32(i32 %x, i32 1)
+  %cmp = icmp sge i32 %y, %max
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp sgt i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @smax_sge_sge(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @smax_sge_sge
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[Y]], [[MAX]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sge i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %max = call i32 @llvm.smax.i32(i32 %x, i32 1)
+  %cmp = icmp sge i32 %y, %max
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp sge i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @smin_slt_slt(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @smin_slt_slt
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[Y]], [[MIN]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %min = call i32 @llvm.smin.i32(i32 %x, i32 1)
+  %cmp = icmp slt i32 %y, %min
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp slt i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @smin_slt_sle(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @smin_slt_sle
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[Y]], [[MIN]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %min = call i32 @llvm.smin.i32(i32 %x, i32 1)
+  %cmp = icmp slt i32 %y, %min
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp sle i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @smin_sle_slt_nofold(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @smin_sle_slt_nofold
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[Y]], [[MIN]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %min = call i32 @llvm.smin.i32(i32 %x, i32 1)
+  %cmp = icmp sle i32 %y, %min
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp slt i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+define i1 @smin_sle_sle(i32 %x, i32 %y) {
+; CHECK-LABEL: define i1 @smin_sle_sle
+; CHECK-SAME: (i32 [[X:%.*]], i32 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[X]], i32 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[Y]], [[MIN]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %min = call i32 @llvm.smin.i32(i32 %x, i32 1)
+  %cmp = icmp sle i32 %y, %min
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp sle i32 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+declare i32 @llvm.smin.i32(i32, i32)
+declare i32 @llvm.smax.i32(i32, i32)
+declare i32 @llvm.umin.i32(i32, i32)
+declare i32 @llvm.umax.i32(i32, i32)
diff --git a/llvm/test/Transforms/ConstraintElimination/reproducer-remarks.ll b/llvm/test/Transforms/ConstraintElimination/reproducer-remarks.ll
--- a/llvm/test/Transforms/ConstraintElimination/reproducer-remarks.ll
+++ b/llvm/test/Transforms/ConstraintElimination/reproducer-remarks.ll
@@ -322,3 +322,30 @@
 else:
   ret i1 false
 }
+
+define i1 @test_minmax(i8 %x, i8 %y) {
+; CHECK-LABEL: define i1 @"{{.+}}test_minmaxrepro"(i8 %max, i8 %x, i8 %y) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %0 = icmp uge i8 %max, 1
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %1 = icmp uge i8 %max, %x
+; CHECK-NEXT:   call void @llvm.assume(i1 %1)
+; CHECK-NEXT:   %2 = icmp ugt i8 %y, %max
+; CHECK-NEXT:   call void @llvm.assume(i1 %2)
+; CHECK-NEXT:   %cmp2 = icmp ugt i8 %y, %x
+; CHECK-NEXT:   ret i1 %cmp2
+; CHECK-NEXT: }
+;
+  %max = call i8 @llvm.umax.i8(i8 %x, i8 1)
+  %cmp = icmp ugt i8 %y, %max
+  br i1 %cmp, label %if, label %end
+
+if:
+  %cmp2 = icmp ugt i8 %y, %x
+  ret i1 %cmp2
+
+end:
+  ret i1 false
+}
+
+declare i8 @llvm.umax.i8(i8, i8)