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
@@ -1099,6 +1099,41 @@
     ReproducerCondStack.pop_back();
 }
 
+/// Check if the first condition for an AND implies the second.
+static bool checkAndSecondOpImpliedByFirst(
+    FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule,
+    SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
+    SmallVectorImpl<StackEntry> &DFSInStack) {
+  CmpInst::Predicate Pred;
+  Value *A, *B;
+  Instruction *And = CB.getContextInst();
+  if (!match(And->getOperand(0), m_ICmp(Pred, m_Value(A), m_Value(B))))
+    return false;
+
+  // Optimistically add fact from first condition.
+  unsigned OldSize = DFSInStack.size();
+  Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
+  if (OldSize == DFSInStack.size())
+    return false;
+
+  bool Changed = false;
+  // Check if the second condition can be simplified now.
+  if (auto ImpliedCondition =
+          checkCondition(cast<ICmpInst>(And->getOperand(1)), Info, CB.NumIn,
+                         CB.NumOut, CB.getContextInst())) {
+    And->setOperand(1, ConstantInt::getBool(And->getType(), *ImpliedCondition));
+    Changed = true;
+  }
+
+  // Remove entries again.
+  while (OldSize < DFSInStack.size()) {
+    StackEntry E = DFSInStack.back();
+    removeEntryFromStack(E, Info, ReproducerModule, ReproducerCondStack,
+                         DFSInStack);
+  }
+  return Changed;
+}
+
 void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,
                              unsigned NumIn, unsigned NumOut,
                              SmallVectorImpl<StackEntry> &DFSInStack) {
@@ -1300,9 +1335,16 @@
       if (auto *II = dyn_cast<WithOverflowInst>(Inst)) {
         Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
       } else if (auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
-        Changed |= checkAndReplaceCondition(
+        bool Simplified = checkAndReplaceCondition(
             Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
             ReproducerModule.get(), ReproducerCondStack, S.DT);
+        if (!Simplified && match(CB.getContextInst(),
+                                 m_LogicalAnd(m_Value(), m_Specific(Inst)))) {
+          Simplified =
+              checkAndSecondOpImpliedByFirst(CB, Info, ReproducerModule.get(),
+                                             ReproducerCondStack, DFSInStack);
+        }
+        Changed |= Simplified;
       }
       continue;
     }
diff --git a/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll b/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll
--- a/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll
+++ b/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll
@@ -6,7 +6,7 @@
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], [[T_1]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
@@ -31,7 +31,7 @@
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 [[T_1]], i1 false
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
@@ -55,7 +55,7 @@
 ; CHECK-LABEL: @test_same_cond_for_and(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], [[C_1]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
@@ -78,7 +78,7 @@
 ; CHECK-LABEL: @test_same_cond_for_and_select_form(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
@@ -325,7 +325,7 @@
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], [[T_1]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 true
diff --git a/llvm/test/Transforms/ConstraintElimination/and.ll b/llvm/test/Transforms/ConstraintElimination/and.ll
--- a/llvm/test/Transforms/ConstraintElimination/and.ll
+++ b/llvm/test/Transforms/ConstraintElimination/and.ll
@@ -459,7 +459,7 @@
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i4 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ule i4 3, [[X]]
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ule i4 3, [[A:%.*]]
-; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false
+; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 true, i1 false
 ; CHECK-NEXT:    [[AND_2:%.*]] = select i1 [[AND_1]], i1 [[C_3]], i1 false
 ; CHECK-NEXT:    [[AND_3:%.*]] = select i1 [[C_4]], i1 [[AND_2]], i1 false
 ; CHECK-NEXT:    br i1 [[AND_3]], label [[BB1:%.*]], label [[EXIT:%.*]]
@@ -546,7 +546,7 @@
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i4 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ule i4 3, [[X]]
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ule i4 3, [[A:%.*]]
-; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false
+; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 true, i1 false
 ; CHECK-NEXT:    [[AND_2:%.*]] = select i1 [[AND_1]], i1 [[C_3]], i1 false
 ; CHECK-NEXT:    [[AND_3:%.*]] = select i1 [[C_4]], i1 [[AND_2]], i1 false
 ; CHECK-NEXT:    [[AND_4:%.*]] = select i1 [[AND_3]], i1 true, i1 false
diff --git a/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll b/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll
--- a/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll
+++ b/llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll
@@ -616,7 +616,7 @@
 ; CHECK:       step.check:
 ; CHECK-NEXT:    [[STEP_POS:%.*]] = icmp sge i16 [[STEP:%.*]], 0
 ; CHECK-NEXT:    [[STEP_SLT_N:%.*]] = icmp slt i16 [[STEP]], [[N]]
-; CHECK-NEXT:    [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_SLT_N]]
+; CHECK-NEXT:    [[AND_STEP:%.*]] = and i1 [[STEP_POS]], false
 ; CHECK-NEXT:    br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]]
 ; CHECK:       ptr.check:
 ; CHECK-NEXT:    [[SRC_STEP:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i16 [[STEP]]
diff --git a/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll b/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll
--- a/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll
+++ b/llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll
@@ -36,7 +36,7 @@
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
 ; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
@@ -65,7 +65,7 @@
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
 ; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
@@ -98,7 +98,7 @@
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
 ; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4