Index: lib/Transforms/InstCombine/InstCombineInternal.h
===================================================================
--- lib/Transforms/InstCombine/InstCombineInternal.h
+++ lib/Transforms/InstCombine/InstCombineInternal.h
@@ -703,6 +703,7 @@
   Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN);
   Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN);
   Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN);
+  Instruction *FoldPHIArgOrIntoPHI(PHINode &PN);
 
   /// If an integer typed PHI has only one use which is an IntToPtr operation,
   /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
Index: lib/Transforms/InstCombine/InstCombinePHI.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombinePHI.cpp
+++ lib/Transforms/InstCombine/InstCombinePHI.cpp
@@ -635,6 +635,84 @@
   return NewLI;
 }
 
+// FoldPHIArgOrIntoPHI finds a phi node, which has OR instruction
+// as an incoming value and AND instruction as its use.
+// If the OR and AND instructions take the same operand
+// as (%A OR %B) AND %B then replace the incoming value by %B.
+// For example,
+//   BB1:
+//     %or = or i64 %val, 1
+//     br %BB2
+//   BB2:
+//     %phi = phi i64 [ %or, %BB1 ], ... # -> phi i64 [ 1, %BB1 ], ...
+//     %and = and i64 %phi, 1
+// This optimization allows jump threading pass to find the opportunity
+// in method call whose return value is std::pair<int, bool>.
+Instruction *InstCombiner::FoldPHIArgOrIntoPHI(PHINode &Phi) {
+  Instruction *rc = nullptr;
+  for (User *User : Phi.users()) {
+    // Try to find OR - Phi - AND code sequence.
+    Value *UserVal = nullptr;
+    if (!match(User, m_And(m_Specific(&Phi), m_Value(UserVal))))
+      continue;
+
+    auto IsEligible = [&](Value *V) {
+      return match(V, m_Or(m_Value(), m_Specific(UserVal)));
+    };
+    if (llvm::none_of(Phi.incoming_values(), IsEligible))
+      continue;
+
+    PHINode* NewPhi = &Phi;
+    if (!Phi.hasOneUse()) {
+      // When Phi is used by other instruction, we need to create a new phi
+      // node for this AND instruction. To avoid increasing total code size,
+      // we create a new phi if the AND can be eliminated.
+      // So far, we do this when all incoming OR are used to mix two 32-bit
+      // integers, e.g. ((Shl(x, 32) OR ZExt(y)), and AND have a constant mask
+      // to extract bits only from one of the mixed integers. For such case,
+      // the AND instruction can be eliminated later by SimplifyDemandedBits.
+      if (!isa<ConstantInt>(UserVal)) continue;
+
+      // If the mask for the AND instruction has one in both high and low
+      // 32-bit, we cannot guarantee that the AND can be eliminated.
+      uint64_t Imm = dyn_cast<ConstantInt>(UserVal)->getZExtValue();
+      if ((Imm & 0xFFFFFFFF) != 0 && (Imm >> 32) != 0) continue;
+
+      const Constant *CI32 = ConstantInt::get(User->getType(), 32);
+      auto IsConcat = [&](Value *V) {
+        Value *LowVal = nullptr;
+        if (match(V, m_Or(m_Shl(m_Value(), m_Specific(CI32)),
+                          m_ZExt(m_Value(LowVal)))) &&
+            LowVal->getType()->getPrimitiveSizeInBits() == 32)
+          return true;
+        return false;
+      };
+      auto IsEligibleOrConcat = [&](Value *V) {
+        return IsEligible(V) || IsConcat(V);
+      };
+      if (!llvm::all_of(Phi.incoming_values(), IsEligibleOrConcat))
+        continue;
+
+      // If there is another use of the phi node, we create a new one
+      // for this AND instruction by cloning the original phi node.
+      NewPhi = cast<PHINode>(Phi.clone());
+      InsertNewInstBefore(NewPhi, Phi);
+      cast<Instruction>(User)->setOperand(0, NewPhi);
+    }
+
+    // We replace the incoming OR with UserVal.
+    for (unsigned Idx = 0; Idx < NewPhi->getNumIncomingValues(); Idx++) {
+      Value *V = NewPhi->getIncomingValue(Idx);
+      if (match(V, m_Or(m_Value(), m_Specific(UserVal))))
+        NewPhi->setIncomingValue(Idx, UserVal);
+    }
+
+    // Because we updated an operand, we return Phi.
+    rc = &Phi;
+  }
+  return rc;
+}
+
 /// TODO: This function could handle other cast types, but then it might
 /// require special-casing a cast from the 'i1' type. See the comment in
 /// FoldPHIArgOpIntoPHI() about pessimizing illegal integer types.
@@ -1130,6 +1208,9 @@
     if (Instruction *Result = FoldPHIArgOpIntoPHI(PN))
       return Result;
 
+  if (Instruction *Result = FoldPHIArgOrIntoPHI(PN))
+    return Result;
+
   // If this is a trivial cycle in the PHI node graph, remove it.  Basically, if
   // this PHI only has a single use (a PHI), and if that PHI only has one use (a
   // PHI)... break the cycle.
Index: test/Transforms/InstCombine/fold-or-phi.ll
===================================================================
--- /dev/null
+++ test/Transforms/InstCombine/fold-or-phi.ll
@@ -0,0 +1,146 @@
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+define signext i32 @test1(i1 %f, i32 signext %a, i32 signext %b) {
+; CHECK-LABEL: @test1
+; CHECK-LABEL: BB2
+; CHECK: [[PHI:%.*]] = phi i32 [ %a, %entry ], [ %b, %BB1 ]
+; CHECK: and i32 [[PHI]], %b
+entry:
+  br i1 %f, label %BB1, label %BB2
+
+BB1:
+  %or = or i32 %a, %b
+  br label %BB2
+
+BB2:
+  %phi = phi i32 [ %a, %entry ], [ %or, %BB1 ]
+  %and = and i32 %phi, %b
+  ret i32 %and
+}
+
+define signext i32 @test2(i1 %f, i32 signext %a, i32 signext %b) {
+; a test case for not creating a clone phi node to avoid code size bloat
+; CHECK-LABEL: @test2
+; CHECK-LABEL: BB2
+; CHECK: [[NewPHI:%.*]] = phi i32 [ %b, %entry ], [ %or, %BB1 ]
+entry:
+  br i1 %f, label %BB1, label %BB2
+
+BB1:
+  %or = or i32 %a, 1
+  br label %BB2
+
+BB2:
+  %phi = phi i32 [ %b, %entry ], [ %or, %BB1 ]
+  %and = and i32 %phi, 1
+  %add = add i32 %and, %phi
+  ret i32 %add
+}
+
+define signext i32 @testBI(i32 signext %v) {
+; Test with std::pair<bool, int>
+; based on the following C++ code
+; std::pair<bool, int> callee(int v) {
+;   int a = dummy(v);
+;   if (a) return std::make_pair(true, dummy(a));
+;   else return std::make_pair(v < 0, v);
+; }
+; int func(int v) {
+;   std::pair<bool, int> rc = callee(v);
+;   if (rc.first) dummy(0);
+;   return rc.second;
+; }
+
+; CHECK-LABEL: @testBI
+; CHECK-LABEL: _ZL6calleei.exit
+; CHECK: [[PHI:%.*]] = phi i1 [ false, %if.then.i ], [ [[V:%.*]], %if.else.i ]
+; CHECK: br i1 [[PHI]], label %if.end, label %if.then
+entry:
+  %call.i = call signext i32 @dummy(i32 signext %v)
+  %tobool.i = icmp eq i32 %call.i, 0
+  br i1 %tobool.i, label %if.else.i, label %if.then.i
+
+if.then.i:                                        ; preds = %entry
+  %call2.i = call signext i32 @dummy(i32 signext %call.i)
+  %retval.sroa.22.0.insert.ext.i.i = zext i32 %call2.i to i64
+  %retval.sroa.22.0.insert.shift.i.i = shl nuw i64 %retval.sroa.22.0.insert.ext.i.i, 32
+  %retval.sroa.0.0.insert.insert.i.i = or i64 %retval.sroa.22.0.insert.shift.i.i, 1
+  br label %_ZL6calleei.exit
+
+if.else.i:                                        ; preds = %entry
+  %.lobit.i = lshr i32 %v, 31
+  %0 = zext i32 %.lobit.i to i64
+  %retval.sroa.22.0.insert.ext.i8.i = zext i32 %v to i64
+  %retval.sroa.22.0.insert.shift.i9.i = shl nuw i64 %retval.sroa.22.0.insert.ext.i8.i, 32
+  %retval.sroa.0.0.insert.insert.i11.i = or i64 %retval.sroa.22.0.insert.shift.i9.i, %0
+  br label %_ZL6calleei.exit
+
+_ZL6calleei.exit:                                 ; preds = %if.then.i, %if.else.i
+  %retval.sroa.0.0.i = phi i64 [ %retval.sroa.0.0.insert.insert.i.i, %if.then.i ], [ %retval.sroa.0.0.insert.insert.i11.i, %if.else.i ]
+  %rc.sroa.43.0.extract.shift = lshr i64 %retval.sroa.0.0.i, 32
+  %rc.sroa.43.0.extract.trunc = trunc i64 %rc.sroa.43.0.extract.shift to i32
+  %1 = and i64 %retval.sroa.0.0.i, 1
+  %tobool = icmp eq i64 %1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %_ZL6calleei.exit
+  %call1 = call signext i32 @dummy(i32 signext 0)
+  br label %if.end
+
+if.end:                                           ; preds = %_ZL6calleei.exit, %if.then
+  ret i32 %rc.sroa.43.0.extract.trunc
+}
+
+define signext i32 @testIB(i32 signext %v) {
+; Test with std::pair<bool, int>
+; based on the following C++ code
+; std::pair<int, bool> callee(int v) {
+;   int a = dummy(v);
+;   if (a) return std::make_pair(dummy(v), true);
+;   else return std::make_pair(v, v < 0);
+; }
+; int func(int v) {
+;   std::pair<int, bool> rc = callee(v);
+;   if (rc.second) dummy(0);
+;   return rc.first;
+; }
+
+; CHECK-LABEL: @testIB
+; CHECK-LABEL: _ZL6calleei.exit
+; CHECK: [[PHI:%.*]] = phi i1 [ false, %if.then.i ], [ [[V:%.*]], %if.else.i ]
+; CHECK: br i1 [[PHI]], label %if.end, label %if.then
+entry:
+  %call.i = call signext i32 @dummy(i32 signext %v)
+  %tobool.i = icmp eq i32 %call.i, 0
+  br i1 %tobool.i, label %if.else.i, label %if.then.i
+
+if.then.i:                                        ; preds = %entry
+  %call1.i = call signext i32 @dummy(i32 signext %v)
+  %retval.sroa.0.0.insert.ext.i.i = zext i32 %call1.i to i64
+  %retval.sroa.0.0.insert.insert.i.i = or i64 %retval.sroa.0.0.insert.ext.i.i, 4294967296
+  br label %_ZL6calleei.exit
+
+if.else.i:                                        ; preds = %entry
+  %.lobit.i = lshr i32 %v, 31
+  %0 = zext i32 %.lobit.i to i64
+  %retval.sroa.2.0.insert.shift.i8.i = shl nuw nsw i64 %0, 32
+  %retval.sroa.0.0.insert.ext.i9.i = zext i32 %v to i64
+  %retval.sroa.0.0.insert.insert.i10.i = or i64 %retval.sroa.2.0.insert.shift.i8.i, %retval.sroa.0.0.insert.ext.i9.i
+  br label %_ZL6calleei.exit
+
+_ZL6calleei.exit:                                 ; preds = %if.then.i, %if.else.i
+  %retval.sroa.0.0.i = phi i64 [ %retval.sroa.0.0.insert.insert.i.i, %if.then.i ], [ %retval.sroa.0.0.insert.insert.i10.i, %if.else.i ]
+  %rc.sroa.0.0.extract.trunc = trunc i64 %retval.sroa.0.0.i to i32
+  %1 = and i64 %retval.sroa.0.0.i, 4294967296
+  %tobool = icmp eq i64 %1, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %_ZL6calleei.exit
+  %call1 = call signext i32 @dummy(i32 signext 0)
+  br label %if.end
+
+if.end:                                           ; preds = %_ZL6calleei.exit, %if.then
+  ret i32 %rc.sroa.0.0.extract.trunc
+}
+
+declare signext i32 @dummy(i32 signext %v)