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
@@ -784,6 +784,11 @@
       continue;
     }
 
+    if (isa<MinMaxIntrinsic>(&I)) {
+      WorkList.push_back(FactOrCheck::getFact(DT.getNode(&BB), &I));
+      continue;
+    }
+
     Value *Cond;
     // For now, just handle assumes with a single compare as condition.
     if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
@@ -1317,6 +1322,7 @@
   // Finally, process ordered worklist and eliminate implied conditions.
   SmallVector<StackEntry, 16> DFSInStack;
   SmallVector<ReproducerEntry> ReproducerCondStack;
+  SmallVector<CmpInst *> TemporaryInsts;
   for (FactOrCheck &CB : S.WorkList) {
     // First, pop entries from the stack that are out-of-scope for CB. Remove
     // the corresponding entry from the constraint system.
@@ -1365,16 +1371,14 @@
     }
 
     LLVM_DEBUG(dbgs() << "fact to add to the system: " << *CB.Inst << "\n");
-    ICmpInst::Predicate Pred;
-    Value *A, *B;
-    Value *Cmp = CB.Inst;
-    match(Cmp, m_Intrinsic<Intrinsic::assume>(m_Value(Cmp)));
-    if (match(Cmp, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
+
+    auto AddFact = [&](CmpInst::Predicate Pred, Value *A, Value *B,
+                       CmpInst *Cond) {
       if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) {
         LLVM_DEBUG(
             dbgs()
             << "Skip adding constraint because system has too many rows.\n");
-        continue;
+        return;
       }
 
       // Use the inverse predicate if required.
@@ -1382,8 +1386,13 @@
         Pred = CmpInst::getInversePredicate(Pred);
 
       Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
-      if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())
-        ReproducerCondStack.emplace_back(cast<CmpInst>(Cmp), CB.Not);
+      if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) {
+        if (!Cond) {
+          Cond = CmpInst::Create(Instruction::ICmp, Pred, A, B);
+          TemporaryInsts.push_back(Cond);
+        }
+        ReproducerCondStack.emplace_back(Cond, CB.Not);
+      }
 
       Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
       if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) {
@@ -1395,6 +1404,21 @@
           ReproducerCondStack.emplace_back(nullptr, false);
         }
       }
+    };
+
+    if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
+      AddFact(ICmpInst::getNonStrictPredicate(MinMax->getPredicate()), CB.Inst,
+              CB.Inst->getOperand(0), nullptr);
+      AddFact(ICmpInst::getNonStrictPredicate(MinMax->getPredicate()), CB.Inst,
+              CB.Inst->getOperand(1), nullptr);
+    }
+
+    ICmpInst::Predicate Pred;
+    Value *A, *B;
+    Value *Cmp = CB.Inst;
+    match(Cmp, m_Intrinsic<Intrinsic::assume>(m_Value(Cmp)));
+    if (match(Cmp, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
+      AddFact(Pred, A, B, dyn_cast<CmpInst>(Cmp));
     }
   }
 
@@ -1419,6 +1443,8 @@
 
   for (Instruction *I : ToRemove)
     I->eraseFromParent();
+  for (CmpInst *CI : TemporaryInsts)
+    CI->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,28 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
+
+define i1 @PR63896(i8 %x, i8 %y) {
+; CHECK-LABEL: define i1 @PR63896
+; CHECK-SAME: (i8 [[X:%.*]], i8 [[Y:%.*]]) {
+; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.umax.i8(i8 [[X]], i8 1)
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[Y]], [[MAX]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i8 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 true
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+  %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)
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 %x, i8 %max, i8 %y) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %0 = icmp uge i8 %max, %x
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %1 = icmp uge i8 %max, 1
+; 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)