diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -228,6 +228,58 @@
   return false;
 }
 
+// CanFoldToConstantUsingOneOperand returns a constant after folding "L Op R"
+// after using only one of L or R, but not both.
+// Formally, it returns a constant X s.t. "L Op Y --> X" or "Y Op R --> X" holds
+//   for any Y (E --> V stands for simplifying E to V).
+//
+// ex)  Given "0 & R", X is 0.
+// ex2) Given "L | -1", X is -1.
+// ex3) Given "0 + 0", there is no such X.
+//
+// If L or R is undef, whenever undef in L is chosen to be a specific
+// constant, it should be assumed that R's value has changed (and vice versa).
+//
+// ex4) Given "undef + 0", X cannot be 0: if L = undef is chosen to be 0,
+//      R cannot be 0 anymore.
+// ex5) Given "undef + undef", X cannot be 0: If L = undef is chosen to be 0,
+//      R may have changed into 1, causing X to be 1.
+// ex6) Given "undef & R", X is 0. If L = undef is chosen to be 0, the result
+//      is 0 regardless of R.
+static Constant *FoldUsingOneOperand(Instruction::BinaryOps Op, Value *L,
+                                     Value *R) {
+  switch (Op) {
+  case Instruction::Mul:
+  case Instruction::And:
+    // ? * 0 = 0, ? & 0 = 0
+    // ? * undef --> 0, ? & undef --> 0
+    return match(L, m_CombineOr(m_Undef(), m_Zero())) ||
+                   match(R, m_CombineOr(m_Undef(), m_Zero()))
+               ? Constant::getNullValue(L->getType())
+               : nullptr;
+  case Instruction::Or:
+    // ? | -1 = -1
+    // ? | undef --> 0
+    return match(L, m_CombineOr(m_Undef(), m_AllOnes())) ||
+                   match(R, m_CombineOr(m_Undef(), m_AllOnes()))
+               ? Constant::getAllOnesValue(L->getType())
+               : nullptr;
+  case Instruction::Add:
+  case Instruction::Sub:
+    return nullptr;
+  case Instruction::Shl:
+  case Instruction::AShr:
+  case Instruction::LShr:
+    // If L is zero, we can always fold the result into zero.
+    // (If shiftamt >= LHS's bitwidth, the result is poison, but it can be
+    //  folded into zero)
+    return match(L, m_Zero()) ? Constant::getNullValue(L->getType()) : nullptr;
+  default:
+    break;
+  }
+  return nullptr;
+}
+
 /// Try to simplify a binary operator of form "V op OtherOp" where V is
 /// "(B0 opex B1)" by distributing 'op' across 'opex' as
 /// "(B0 op OtherOp) opex (B1 op OtherOp)".
@@ -245,6 +297,21 @@
   if (!R)
     return nullptr;
 
+  // If OtherOp contains undef in its subexpression, the undef should be folded
+  // into the same constant by the two previous SimplifyBinOp calls.
+  // Implementing this 'entanglement' in InstSimplify is non-trivial, however.
+  // So, use a simpler approach instead:
+  // (1) If "L Op' R" can be folded into a constant by using only L
+  //     or R, fold it. This is valid because it does not consider the other
+  //     simplification.
+  if (Constant *Res = FoldUsingOneOperand(OpcodeToExpand, L, R)) {
+    ++NumExpand;
+    return Res;
+  }
+  // (2) If OtherOp may be undef or poison, give up.
+  if (!isGuaranteedNotToBeUndefOrPoison(OtherOp, Q.CxtI, Q.DT))
+    return nullptr;
+
   // Does the expanded pair of binops simplify to the existing binop?
   if ((L == B0 && R == B1) ||
       (Instruction::isCommutative(OpcodeToExpand) && L == B1 && R == B0)) {
diff --git a/llvm/test/Transforms/InstCombine/and-or-icmps.ll b/llvm/test/Transforms/InstCombine/and-or-icmps.ll
--- a/llvm/test/Transforms/InstCombine/and-or-icmps.ll
+++ b/llvm/test/Transforms/InstCombine/and-or-icmps.ll
@@ -218,12 +218,14 @@
 ; CHECK-NEXT:    [[C7:%.*]] = icmp slt i16 [[L7]], 0
 ; CHECK-NEXT:    [[B15:%.*]] = xor i1 [[C7]], [[C10]]
 ; CHECK-NEXT:    [[B19:%.*]] = xor i1 [[C11]], [[B15]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[C10]], [[C5]]
-; CHECK-NEXT:    [[C3:%.*]] = and i1 [[TMP2]], [[B19]]
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[C10]], true
-; CHECK-NEXT:    [[C18:%.*]] = or i1 [[C7]], [[TMP3]]
-; CHECK-NEXT:    [[TMP4:%.*]] = sext i1 [[C3]] to i64
-; CHECK-NEXT:    [[G26:%.*]] = getelementptr i1, i1* null, i64 [[TMP4]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i1 [[C11]], true
+; CHECK-NEXT:    [[C6:%.*]] = or i1 [[B19]], [[TMP2]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[C10]], [[C5]]
+; CHECK-NEXT:    [[C3:%.*]] = and i1 [[TMP3]], [[C6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[C10]], true
+; CHECK-NEXT:    [[C18:%.*]] = or i1 [[C7]], [[TMP4]]
+; CHECK-NEXT:    [[TMP5:%.*]] = sext i1 [[C3]] to i64
+; CHECK-NEXT:    [[G26:%.*]] = getelementptr i1, i1* null, i64 [[TMP5]]
 ; CHECK-NEXT:    store i16 [[L7]], i16* undef, align 2
 ; CHECK-NEXT:    store i1 [[C18]], i1* undef, align 1
 ; CHECK-NEXT:    store i1* [[G26]], i1** undef, align 8