diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -2328,12 +2328,24 @@
   if (!PN)
     return true;
 
-  // Don't fold i1 branches on PHIs which contain binary operators.  These can
-  // often be turned into switches and other things.
+  // Return true if at least one of these is a 'not', and another is either
+  // a 'not' too, or a constant.
+  auto CanHoistNotFromBothValues = [](Value *V0, Value *V1) {
+    if (!match(V0, m_Not(m_Value())))
+      std::swap(V0, V1);
+    auto Invertible = m_CombineOr(m_Not(m_Value()), m_AnyIntegralConstant());
+    return match(V0, m_Not(m_Value())) && match(V1, Invertible);
+  };
+
+  // Don't fold i1 branches on PHIs which contain binary operators, unless one
+  // of the incoming values is an 'not' and another one is freely invertible.
+  // These can often be turned into switches and other things.
   if (PN->getType()->isIntegerTy(1) &&
       (isa<BinaryOperator>(PN->getIncomingValue(0)) ||
        isa<BinaryOperator>(PN->getIncomingValue(1)) ||
-       isa<BinaryOperator>(IfCond)))
+       isa<BinaryOperator>(IfCond)) &&
+      !CanHoistNotFromBothValues(PN->getIncomingValue(0),
+                                 PN->getIncomingValue(1)))
     return false;
 
   // If all PHI nodes are promotable, check to make sure that all instructions
diff --git a/llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll b/llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll
--- a/llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll
+++ b/llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll
@@ -104,18 +104,49 @@
 ; SIMPLIFYCFG-NEXT:    [[T7:%.*]] = xor i1 [[T6]], true
 ; SIMPLIFYCFG-NEXT:    ret i1 [[T7]]
 ;
-; INSTCOMBINE-LABEL: @will_overflow(
-; INSTCOMBINE-NEXT:  bb:
-; INSTCOMBINE-NEXT:    [[T0:%.*]] = icmp eq i64 [[ARG:%.*]], 0
-; INSTCOMBINE-NEXT:    br i1 [[T0]], label [[BB5:%.*]], label [[BB2:%.*]]
-; INSTCOMBINE:       bb2:
-; INSTCOMBINE-NEXT:    [[UMUL:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[ARG]], i64 [[ARG1:%.*]])
-; INSTCOMBINE-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
-; INSTCOMBINE-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
-; INSTCOMBINE-NEXT:    br label [[BB5]]
-; INSTCOMBINE:       bb5:
-; INSTCOMBINE-NEXT:    [[T6:%.*]] = phi i1 [ true, [[BB:%.*]] ], [ [[PHITMP]], [[BB2]] ]
-; INSTCOMBINE-NEXT:    ret i1 [[T6]]
+; INSTCOMBINEONLY-LABEL: @will_overflow(
+; INSTCOMBINEONLY-NEXT:  bb:
+; INSTCOMBINEONLY-NEXT:    [[T0:%.*]] = icmp eq i64 [[ARG:%.*]], 0
+; INSTCOMBINEONLY-NEXT:    br i1 [[T0]], label [[BB5:%.*]], label [[BB2:%.*]]
+; INSTCOMBINEONLY:       bb2:
+; INSTCOMBINEONLY-NEXT:    [[UMUL:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[ARG]], i64 [[ARG1:%.*]])
+; INSTCOMBINEONLY-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; INSTCOMBINEONLY-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
+; INSTCOMBINEONLY-NEXT:    br label [[BB5]]
+; INSTCOMBINEONLY:       bb5:
+; INSTCOMBINEONLY-NEXT:    [[T6:%.*]] = phi i1 [ true, [[BB:%.*]] ], [ [[PHITMP]], [[BB2]] ]
+; INSTCOMBINEONLY-NEXT:    ret i1 [[T6]]
+;
+; INSTCOMBINESIMPLIFYCFGDEFAULT-LABEL: @will_overflow(
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:  bb:
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    [[T0:%.*]] = icmp eq i64 [[ARG:%.*]], 0
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    br i1 [[T0]], label [[BB5:%.*]], label [[BB2:%.*]]
+; INSTCOMBINESIMPLIFYCFGDEFAULT:       bb2:
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    [[UMUL:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[ARG]], i64 [[ARG1:%.*]])
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    br label [[BB5]]
+; INSTCOMBINESIMPLIFYCFGDEFAULT:       bb5:
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    [[T6:%.*]] = phi i1 [ true, [[BB:%.*]] ], [ [[PHITMP]], [[BB2]] ]
+; INSTCOMBINESIMPLIFYCFGDEFAULT-NEXT:    ret i1 [[T6]]
+;
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-LABEL: @will_overflow(
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:  bb:
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    [[T0:%.*]] = icmp eq i64 [[ARG:%.*]], 0
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    [[UMUL:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[ARG]], i64 [[ARG1:%.*]])
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    [[T6:%.*]] = select i1 [[T0]], i1 true, i1 [[PHITMP]]
+; INSTCOMBINESIMPLIFYCFGCOSTLYONLY-NEXT:    ret i1 [[T6]]
+;
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-LABEL: @will_overflow(
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:  bb:
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    [[T0:%.*]] = icmp eq i64 [[ARG:%.*]], 0
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    [[UMUL:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[ARG]], i64 [[ARG1:%.*]])
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    [[T6:%.*]] = or i1 [[T0]], [[PHITMP]]
+; INSTCOMBINESIMPLIFYCFGCOSTLYINSTCOMBINE-NEXT:    ret i1 [[T6]]
 ;
 bb:
   %t0 = icmp eq i64 %arg, 0
diff --git a/llvm/test/Transforms/SimplifyCFG/unsigned-multiplication-will-overflow.ll b/llvm/test/Transforms/SimplifyCFG/unsigned-multiplication-will-overflow.ll
--- a/llvm/test/Transforms/SimplifyCFG/unsigned-multiplication-will-overflow.ll
+++ b/llvm/test/Transforms/SimplifyCFG/unsigned-multiplication-will-overflow.ll
@@ -8,18 +8,27 @@
 ; produced llvm.umul.with.overflow.
 
 define i1 @will_overflow(i64 %size, i64 %nmemb) {
-; ALL-LABEL: @will_overflow(
-; ALL-NEXT:  entry:
-; ALL-NEXT:    [[CMP:%.*]] = icmp eq i64 [[SIZE:%.*]], 0
-; ALL-NEXT:    br i1 [[CMP]], label [[LAND_END:%.*]], label [[LAND_RHS:%.*]]
-; ALL:       land.rhs:
-; ALL-NEXT:    [[UMUL:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[SIZE]], i64 [[NMEMB:%.*]])
-; ALL-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
-; ALL-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
-; ALL-NEXT:    br label [[LAND_END]]
-; ALL:       land.end:
-; ALL-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[UMUL_NOT_OV]], [[LAND_RHS]] ]
-; ALL-NEXT:    ret i1 [[TMP0]]
+; DEFAULT-LABEL: @will_overflow(
+; DEFAULT-NEXT:  entry:
+; DEFAULT-NEXT:    [[CMP:%.*]] = icmp eq i64 [[SIZE:%.*]], 0
+; DEFAULT-NEXT:    br i1 [[CMP]], label [[LAND_END:%.*]], label [[LAND_RHS:%.*]]
+; DEFAULT:       land.rhs:
+; DEFAULT-NEXT:    [[UMUL:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[SIZE]], i64 [[NMEMB:%.*]])
+; DEFAULT-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; DEFAULT-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
+; DEFAULT-NEXT:    br label [[LAND_END]]
+; DEFAULT:       land.end:
+; DEFAULT-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[UMUL_NOT_OV]], [[LAND_RHS]] ]
+; DEFAULT-NEXT:    ret i1 [[TMP0]]
+;
+; COSTLY-LABEL: @will_overflow(
+; COSTLY-NEXT:  entry:
+; COSTLY-NEXT:    [[CMP:%.*]] = icmp eq i64 [[SIZE:%.*]], 0
+; COSTLY-NEXT:    [[UMUL:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[SIZE]], i64 [[NMEMB:%.*]])
+; COSTLY-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i64, i1 } [[UMUL]], 1
+; COSTLY-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
+; COSTLY-NEXT:    [[TMP0:%.*]] = select i1 [[CMP]], i1 true, i1 [[UMUL_NOT_OV]]
+; COSTLY-NEXT:    ret i1 [[TMP0]]
 ;
 entry:
   %cmp = icmp eq i64 %size, 0