Index: llvm/include/llvm/IR/Dominators.h
===================================================================
--- llvm/include/llvm/IR/Dominators.h
+++ llvm/include/llvm/IR/Dominators.h
@@ -172,6 +172,8 @@
   /// never dominate the use.
   bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
   bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
+  /// Returns true if edge \p BBE1 dominates edge \p BBE2.
+  bool dominates(const BasicBlockEdge &BBE1, const BasicBlockEdge &BBE2) const;
 
   // Ensure base class overloads are visible.
   using Base::isReachableFromEntry;
Index: llvm/lib/IR/Dominators.cpp
===================================================================
--- llvm/lib/IR/Dominators.cpp
+++ llvm/lib/IR/Dominators.cpp
@@ -316,6 +316,14 @@
   return isReachableFromEntry(I->getParent());
 }
 
+// Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2.
+bool DominatorTree::dominates(const BasicBlockEdge &BBE1,
+                              const BasicBlockEdge &BBE2) const {
+  if (BBE1.getStart() == BBE2.getStart() && BBE1.getEnd() == BBE2.getEnd())
+    return true;
+  return dominates(BBE1, BBE2.getStart());
+}
+
 //===----------------------------------------------------------------------===//
 //  DominatorTreeAnalysis and related pass implementations
 //===----------------------------------------------------------------------===//
Index: llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp
+++ llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp
@@ -1129,6 +1129,77 @@
   return replaceInstUsesWith(FirstPhi, Undef);
 }
 
+static Value *SimplifyUsingControlFlow(InstCombiner &Self, PHINode &PN,
+                                       const DominatorTree &DT) {
+  // Simplify the following patterns:
+  //       if (cond)
+  //       /       \
+  //      ...      ...
+  //       \       /
+  //    phi [true] [false]
+  if (!PN.getType()->isIntegerTy(1))
+    return nullptr;
+
+  // TODO: This can be generalized for more than 2 inputs, but it will take
+  // more sophisticated dominance checks.
+  if (PN.getNumOperands() != 2)
+    return nullptr;
+
+  // Make sure all inputs are constants.
+  if (!all_of(PN.operands(), [](Value *V) { return isa<ConstantInt>(V); }))
+    return nullptr;
+
+  BasicBlock *BB = PN.getParent();
+  // Do not bother with unreachable instructions.
+  if (!DT.isReachableFromEntry(BB))
+    return nullptr;
+
+  // Same inputs.
+  if (PN.getOperand(0) == PN.getOperand(1))
+    return PN.getOperand(0);
+
+  BasicBlock *TruePred = nullptr, *FalsePred = nullptr;
+  for (auto *Pred : predecessors(BB)) {
+    auto *Input = cast<ConstantInt>(PN.getIncomingValueForBlock(Pred));
+    if (Input->isAllOnesValue())
+      TruePred = Pred;
+    else
+      FalsePred = Pred;
+  }
+  assert(TruePred && FalsePred && "Must be!");
+
+  // Check which edge of the dominator dominates the true input. If it is the
+  // false edge, we should invert the condition.
+  auto *IDom = DT.getNode(BB)->getIDom()->getBlock();
+  auto *BI = dyn_cast<BranchInst>(IDom->getTerminator());
+  if (!BI || BI->isUnconditional())
+    return nullptr;
+
+  // Check that edges outgoing from the idom's terminators dominate respective
+  // inputs of the Phi.
+  BasicBlockEdge TrueOutEdge(IDom, BI->getSuccessor(0));
+  BasicBlockEdge FalseOutEdge(IDom, BI->getSuccessor(1));
+
+  BasicBlockEdge TrueIncEdge(TruePred, BB);
+  BasicBlockEdge FalseIncEdge(FalsePred, BB);
+
+  auto *Cond = BI->getCondition();
+  if (DT.dominates(TrueOutEdge, TrueIncEdge) &&
+      DT.dominates(FalseOutEdge, FalseIncEdge))
+    // This Phi is actually equivalent to branching condition of IDom.
+    return Cond;
+  else if (DT.dominates(TrueOutEdge, FalseIncEdge) &&
+           DT.dominates(FalseOutEdge, TrueIncEdge)) {
+    // This Phi is actually opposite to branching condition of IDom. We invert
+    // the condition that will potentially open up some opportunities for
+    // sinking.
+    Self.Builder.SetInsertPoint(BB->getFirstNonPHI());
+    return Self.Builder.CreateNot(Cond);
+  }
+
+  return nullptr;
+}
+
 // PHINode simplification
 //
 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
@@ -1276,5 +1347,9 @@
     if (Instruction *Res = SliceUpIllegalIntegerPHI(PN))
       return Res;
 
+  // Try to simplify this Phi using knowledge of control flow.
+  if (Value *V = SimplifyUsingControlFlow(*this, PN, DT))
+    return replaceInstUsesWith(PN, V);
+
   return nullptr;
 }
Index: llvm/test/Transforms/CallSiteSplitting/callsite-split.ll
===================================================================
--- llvm/test/Transforms/CallSiteSplitting/callsite-split.ll
+++ llvm/test/Transforms/CallSiteSplitting/callsite-split.ll
@@ -73,9 +73,9 @@
 ;CHECK: call void @dummy4()
 ;CHECK-LABEL: NextCond.split:
 ;CHECK: call void @dummy3()
-;CheCK-LABEL: CallSiteBB:
-;CHECK: %phi.call = phi i1 [ true, %NextCond.split ], [ false, %Top.split ]
-;CHECK: call void @foo(i1 %phi.call)
+;CHECK-LABEL: CallSiteBB:
+;CHECK: [[NEG:%.*]] = xor i1 %tobool1, true
+;CHECK: call void @foo(i1 [[NEG]])
 define void @caller2(i1 %c, %struct.bitmap* %a_elt, %struct.bitmap* %b_elt, %struct.bitmap* %c_elt) {
 entry:
   br label %Top
Index: llvm/test/Transforms/InstCombine/icmp-constant-phi.ll
===================================================================
--- llvm/test/Transforms/InstCombine/icmp-constant-phi.ll
+++ llvm/test/Transforms/InstCombine/icmp-constant-phi.ll
@@ -11,10 +11,10 @@
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[COMPARE:%.*]] = phi i1 [ true, [[IF_FALSE]] ], [ false, [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    ret i1 [[COMPARE]]
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND]], true
+; CHECK-NEXT:    ret i1 [[TMP0]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
@@ -43,10 +43,9 @@
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[COMPARE:%.*]] = phi i1 [ false, [[IF_FALSE]] ], [ true, [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    ret i1 [[COMPARE]]
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
@@ -106,10 +105,9 @@
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[COMPARE:%.*]] = phi i1 [ false, [[IF_FALSE]] ], [ true, [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    ret i1 [[COMPARE]]
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
Index: llvm/test/Transforms/InstCombine/phi.ll
===================================================================
--- llvm/test/Transforms/InstCombine/phi.ll
+++ llvm/test/Transforms/InstCombine/phi.ll
@@ -416,10 +416,13 @@
 
 bb2:        ; preds = %bb1, %entry
     %cond = phi i1 [ true, %bb1 ], [ false, %entry ]        ; <i1> [#uses=1]
-; CHECK-NOT: %val = phi i32 [ %0, %bb1 ], [ 0, %entry ]
+; TODO: Can be further optimized by removing select.
+; CHECK-NOT: %cond
+; CHECK:     %val = phi i32 [ %0, %bb1 ], [ 0, %entry ]
+; CHECK:     %res = select i1 %a, i32 %val, i32 0
     %val = phi i32 [ %0, %bb1 ], [ 0, %entry ]        ; <i32> [#uses=1]
     %res = select i1 %cond, i32 %val, i32 0        ; <i32> [#uses=1]
-; CHECK: ret i32 %cond
+; CHECK:    ret i32 %res
     ret i32 %res
 }
 
Index: llvm/test/Transforms/InstCombine/select.ll
===================================================================
--- llvm/test/Transforms/InstCombine/select.ll
+++ llvm/test/Transforms/InstCombine/select.ll
@@ -448,8 +448,8 @@
 ; CHECK:       jump:
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
-; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 10, [[JUMP]] ], [ 20, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i32 [[A]]
+; CHECK-NEXT:    [[B:%.*]] = select i1 [[C]], i32 10, i32 20
+; CHECK-NEXT:    ret i32 [[B]]
 ;
 entry:
   br i1 %c, label %jump, label %ret
@@ -468,8 +468,8 @@
 ; CHECK:       jump:
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
-; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 20, [[ENTRY:%.*]] ], [ 10, [[JUMP]] ]
-; CHECK-NEXT:    ret i32 [[A]]
+; CHECK-NEXT:    [[B:%.*]] = select i1 [[COND]], i32 10, i32 20
+; CHECK-NEXT:    ret i32 [[B]]
 ;
 entry:
   br i1 %cond, label %jump, label %ret
@@ -489,8 +489,8 @@
 ; CHECK:       jump:
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
-; CHECK-NEXT:    [[P:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i32 [[P]]
+; CHECK-NEXT:    [[S:%.*]] = select i1 [[C]], i32 [[A:%.*]], i32 [[B:%.*]]
+; CHECK-NEXT:    ret i32 [[S]]
 ;
 entry:
   br i1 %c, label %jump, label %ret
@@ -509,8 +509,9 @@
 ; CHECK:       jump:
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
-; CHECK-NEXT:    [[P:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i32 [[P]]
+; CHECK-NEXT:    [[C:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND]], i32 [[A]], i32 [[C]]
+; CHECK-NEXT:    ret i32 [[S]]
 ;
 entry:
   br i1 %cond, label %jump, label %ret
@@ -530,10 +531,11 @@
 ; CHECK:       jump:
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
-; CHECK-NEXT:    [[P:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[C:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[NEXT:%.*]]
 ; CHECK:       next:
-; CHECK-NEXT:    ret i32 [[P]]
+; CHECK-NEXT:    [[S:%.*]] = select i1 [[COND]], i32 [[A]], i32 [[C]]
+; CHECK-NEXT:    ret i32 [[S]]
 ;
 entry:
   br i1 %cond, label %jump, label %ret
Index: llvm/test/Transforms/InstCombine/simple_phi_condition.ll
===================================================================
--- llvm/test/Transforms/InstCombine/simple_phi_condition.ll
+++ llvm/test/Transforms/InstCombine/simple_phi_condition.ll
@@ -12,8 +12,7 @@
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[IF_TRUE]] ], [ false, [[IF_FALSE]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
@@ -39,8 +38,8 @@
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ false, [[IF_TRUE]] ], [ true, [[IF_FALSE]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND]], true
+; CHECK-NEXT:    ret i1 [[TMP0]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
@@ -73,8 +72,7 @@
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[IF_TRUE_END]] ], [ false, [[IF_FALSE]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
@@ -116,8 +114,8 @@
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ false, [[IF_TRUE_END]] ], [ true, [[IF_FALSE]] ]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND]], true
+; CHECK-NEXT:    ret i1 [[TMP0]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
Index: llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll
===================================================================
--- llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll
+++ llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll
@@ -40,7 +40,7 @@
 ; ASSUMPTIONS-ON-LABEL: @caller1(
 ; ASSUMPTIONS-ON-NEXT:    br i1 [[C:%.*]], label [[TRUE1:%.*]], label [[FALSE1:%.*]]
 ; ASSUMPTIONS-ON:       true1:
-; ASSUMPTIONS-ON-NEXT:    [[C_PR:%.*]] = phi i1 [ false, [[FALSE1]] ], [ true, [[TMP0:%.*]] ]
+; ASSUMPTIONS-ON-NEXT:    [[C_PR:%.*]] = phi i1 [ [[C]], [[FALSE1]] ], [ true, [[TMP0:%.*]] ]
 ; ASSUMPTIONS-ON-NEXT:    [[PTRINT:%.*]] = ptrtoint i64* [[PTR:%.*]] to i64
 ; ASSUMPTIONS-ON-NEXT:    [[MASKEDPTR:%.*]] = and i64 [[PTRINT]], 7
 ; ASSUMPTIONS-ON-NEXT:    [[MASKCOND:%.*]] = icmp eq i64 [[MASKEDPTR]], 0
Index: llvm/test/Transforms/PhaseOrdering/simplifycfg-options.ll
===================================================================
--- llvm/test/Transforms/PhaseOrdering/simplifycfg-options.ll
+++ llvm/test/Transforms/PhaseOrdering/simplifycfg-options.ll
@@ -18,16 +18,16 @@
 ; ALL-NEXT:    call void @foo()
 ; ALL-NEXT:    br label [[IF_END]]
 ; ALL:       if.end:
-; ALL-NEXT:    [[CHANGED_1_OFF0:%.*]] = phi i1 [ true, [[IF_THEN]] ], [ false, [[ENTRY:%.*]] ]
-; ALL-NEXT:    [[TMP1:%.*]] = load i32, i32* [[C]], align 4
-; ALL-NEXT:    [[CMP_1:%.*]] = icmp eq i32 [[OR]], [[TMP1]]
+; ALL-NEXT:    [[TMP1:%.*]] = xor i1 [[CMP]], true
+; ALL-NEXT:    [[TMP2:%.*]] = load i32, i32* [[C]], align 4
+; ALL-NEXT:    [[CMP_1:%.*]] = icmp eq i32 [[OR]], [[TMP2]]
 ; ALL-NEXT:    br i1 [[CMP_1]], label [[IF_END_1:%.*]], label [[IF_THEN_1:%.*]]
 ; ALL:       if.then.1:
 ; ALL-NEXT:    store i32 [[OR]], i32* [[C]], align 4
 ; ALL-NEXT:    call void @foo()
 ; ALL-NEXT:    br label [[IF_END_1]]
 ; ALL:       if.end.1:
-; ALL-NEXT:    [[CHANGED_1_OFF0_1:%.*]] = phi i1 [ true, [[IF_THEN_1]] ], [ [[CHANGED_1_OFF0]], [[IF_END]] ]
+; ALL-NEXT:    [[CHANGED_1_OFF0_1:%.*]] = phi i1 [ true, [[IF_THEN_1]] ], [ [[TMP1]], [[IF_END]] ]
 ; ALL-NEXT:    ret i1 [[CHANGED_1_OFF0_1]]
 ;
 entry: