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))) &&
@@ -1363,22 +1368,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) {
       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.
-      if (CB.Not)
-        Pred = CmpInst::getInversePredicate(Pred);
-
       Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
       if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())
         ReproducerCondStack.emplace_back(Pred, A, B);
@@ -1394,6 +1391,25 @@
                                            nullptr, nullptr);
         }
       }
+    };
+
+    ICmpInst::Predicate Pred;
+    if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
+      Pred = ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
+      AddFact(Pred, MinMax, MinMax->getLHS());
+      AddFact(Pred, MinMax, MinMax->getRHS());
+      continue;
+    }
+
+    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)))) {
+      // Use the inverse predicate if required.
+      if (CB.Not)
+        Pred = CmpInst::getInversePredicate(Pred);
+
+      AddFact(Pred, A, B);
     }
   }
 
diff --git a/llvm/test/Transforms/ConstraintElimination/minmax.ll b/llvm/test/Transforms/ConstraintElimination/minmax.ll
--- a/llvm/test/Transforms/ConstraintElimination/minmax.ll
+++ b/llvm/test/Transforms/ConstraintElimination/minmax.ll
@@ -11,7 +11,7 @@
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[Y]], [[X]]
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp uge i32 [[Y]], [[X]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], [[CMP3]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i1 true, true
 ; CHECK-NEXT:    ret i1 [[RET]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i1 false
@@ -39,7 +39,7 @@
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[Y]], [[X]]
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp uge i32 [[Y]], [[X]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], [[CMP3]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], true
 ; CHECK-NEXT:    ret i1 [[RET]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i1 false
@@ -67,7 +67,7 @@
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y]], [[X]]
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp ule i32 [[Y]], [[X]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], [[CMP3]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i1 true, true
 ; CHECK-NEXT:    ret i1 [[RET]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i1 false
@@ -95,7 +95,7 @@
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y]], [[X]]
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp ule i32 [[Y]], [[X]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], [[CMP3]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], true
 ; CHECK-NEXT:    ret i1 [[RET]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i1 false
@@ -123,7 +123,7 @@
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[Y]], [[X]]
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp sge i32 [[Y]], [[X]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], [[CMP3]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i1 true, true
 ; CHECK-NEXT:    ret i1 [[RET]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i1 false
@@ -151,7 +151,7 @@
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[Y]], [[X]]
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp sge i32 [[Y]], [[X]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], [[CMP3]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], true
 ; CHECK-NEXT:    ret i1 [[RET]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i1 false
@@ -179,7 +179,7 @@
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[Y]], [[X]]
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp sle i32 [[Y]], [[X]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], [[CMP3]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i1 true, true
 ; CHECK-NEXT:    ret i1 [[RET]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i1 false
@@ -207,7 +207,7 @@
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[Y]], [[X]]
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp sle i32 [[Y]], [[X]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], [[CMP3]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP2]], true
 ; CHECK-NEXT:    ret i1 [[RET]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i1 false
@@ -235,7 +235,7 @@
 ; 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-NEXT:    ret i1 true
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i1 false
 ;
@@ -297,7 +297,7 @@
 ; CHECK:       if:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[Z]], [[X]]
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp ugt i32 [[Z]], [[Y]]
-; CHECK-NEXT:    [[AND:%.*]] = xor i1 [[CMP2]], [[CMP3]]
+; CHECK-NEXT:    [[AND:%.*]] = xor i1 true, true
 ; CHECK-NEXT:    ret i1 [[AND]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i1 false
@@ -323,7 +323,7 @@
 ; CHECK-NEXT:    [[MIN:%.*]] = call i32 @llvm.smin.i32(i32 [[X]], i32 [[Y]])
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sle i32 [[MIN]], [[X]]
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[MIN]], [[X]]
-; CHECK-NEXT:    [[RET:%.*]] = xor i1 [[CMP1]], [[CMP2]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i1 true, false
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
 entry: