Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1161,11 +1161,66 @@
   return nullptr;
 }
 
+static Instruction *
+shrinkLogicWithZextOpAndPhiOp(BinaryOperator &Logic,
+                              InstCombiner::BuilderTy &Builder) {
+  // Try to narrow a bitwise logic op with a zexted operand and a phi operand
+  // that may include the logic op itself and some number of constants:
+  // LogicOp phi [ C0, C1, ..., LogicOp ], (zext X) -->
+  // zext (LogicOp' phi [ C0', C1', ..., LogicOp'], X
+  auto *Phi = dyn_cast<PHINode>(Logic.getOperand(0));
+  Value *X;
+  if (!Phi || !Phi->hasOneUse() ||
+      !match(Logic.getOperand(1), m_OneUse(m_ZExt(m_Value(X)))))
+    return nullptr;
+
+  // The phi's incoming values must be the logic instruction itself or constants
+  // that fit in the narrower source type.
+  Type *DestTy = Logic.getType();
+  Type *SrcTy = X->getType();
+  SmallVector<Value *, 4> NarrowOps;
+  for (Value *PhiVal : Phi->incoming_values()) {
+    if (auto *C = dyn_cast<Constant>(PhiVal)) {
+      Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
+      Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy);
+      if (ZextTruncC != C)
+        return nullptr;
+      NarrowOps.push_back(TruncC);
+    } else if (PhiVal == &Logic) {
+      // Use X as a placeholder in the list. We'll replace it with a new narrow
+      // logic op if this transform works out.
+      NarrowOps.push_back(X);
+    } else {
+      return nullptr;
+    }
+  }
+
+  // All incoming values are safe to shrink. Replace the phi and logic op with
+  // narrower versions.
+  unsigned NumPhiOps = Phi->getNumOperands();
+  assert((NarrowOps.size() == NumPhiOps) &&
+         "Unexpected value while narrowing phi");
+
+  // Phi nodes must be inserted at the start of a basic block.
+  Builder.SetInsertPoint(Phi);
+  PHINode *NarrowPhi = Builder.CreatePHI(SrcTy, NumPhiOps);
+  Builder.SetInsertPoint(&Logic);
+  Value *NarrowLogic = Builder.CreateBinOp(Logic.getOpcode(), NarrowPhi, X);
+  for (unsigned i = 0; i != NumPhiOps; ++i) {
+    Value *NarrowVal = NarrowOps[i] == X ? NarrowLogic : NarrowOps[i];
+    NarrowPhi->addIncoming(NarrowVal, Phi->getIncomingBlock(i));
+  }
+  return new ZExtInst(NarrowLogic, DestTy);
+}
+
 /// Fold {and,or,xor} (cast X), Y.
 Instruction *InstCombiner::foldCastedBitwiseLogic(BinaryOperator &I) {
   auto LogicOpc = I.getOpcode();
   assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding");
 
+  if (Instruction *Ret = shrinkLogicWithZextOpAndPhiOp(I, *Builder))
+    return Ret;
+
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   CastInst *Cast0 = dyn_cast<CastInst>(Op0);
   if (!Cast0)
Index: test/Transforms/InstCombine/or.ll
===================================================================
--- test/Transforms/InstCombine/or.ll
+++ test/Transforms/InstCombine/or.ll
@@ -701,3 +701,43 @@
   %3 = or i1 %1, %.b
   ret i1 %3
 }
+
+; Shrink the 'or' and 'phi' which simplifies away the zext and final icmp.
+
+define i1 @SearchArray(i32 %needle, i32* %haystack) {
+; CHECK-LABEL: @SearchArray(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVAR:%.*]] = phi i32 [ 0, %entry ], [ [[INDVAR_NEXT:%.*]], %loop ]
+; CHECK-NEXT:    [[FOUND:%.*]] = phi i1 [ false, %entry ], [ [[OR:%.*]], %loop ]
+; CHECK-NEXT:    [[IDX:%.*]] = getelementptr i32, i32* %haystack, i32 [[INDVAR]]
+; CHECK-NEXT:    [[LD:%.*]] = load i32, i32* [[IDX]], align 4
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[LD]], %needle
+; CHECK-NEXT:    [[OR]] = or i1 [[FOUND]], [[CMP1]]
+; CHECK-NEXT:    [[INDVAR_NEXT]] = add i32 [[INDVAR]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INDVAR_NEXT]], 1000
+; CHECK-NEXT:    br i1 [[EXITCOND]], label %exit, label %loop
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+entry:
+  br label %loop
+
+loop:
+  %indvar = phi i32 [ 0, %entry ], [ %indvar.next, %loop ]
+  %found = phi i8 [ 0, %entry ], [ %or, %loop ]
+  %idx = getelementptr i32, i32* %haystack, i32 %indvar
+  %ld = load i32, i32* %idx
+  %cmp1 = icmp eq i32 %ld, %needle
+  %zext = zext i1 %cmp1 to i8
+  %or = or i8 %found, %zext
+  %indvar.next = add i32 %indvar, 1
+  %exitcond = icmp eq i32 %indvar.next, 1000
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  %tobool = icmp ne i8 %or, 0
+  ret i1 %tobool
+}
+