Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1209,8 +1209,7 @@
   Value *Cast1Src = Cast1->getOperand(0);
 
   // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
-  if ((!isa<ICmpInst>(Cast0Src) || !isa<ICmpInst>(Cast1Src)) &&
-      shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
+  if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
     Value *NewOp = Builder->CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
                                         I.getName());
     return CastInst::Create(CastOpcode, NewOp, DestTy);
Index: lib/Transforms/InstCombine/InstCombineCasts.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineCasts.cpp
+++ lib/Transforms/InstCombine/InstCombineCasts.cpp
@@ -623,7 +623,9 @@
 
         if (CI.getType() == In->getType())
           return replaceInstUsesWith(CI, In);
-        return CastInst::CreateIntegerCast(In, CI.getType(), false/*ZExt*/);
+
+        Value *IntCast = Builder->CreateIntCast(In, CI.getType(), false);
+        return replaceInstUsesWith(CI, IntCast);
       }
     }
   }
@@ -890,16 +892,27 @@
 
   BinaryOperator *SrcI = dyn_cast<BinaryOperator>(Src);
   if (SrcI && SrcI->getOpcode() == Instruction::Or) {
-    // zext (or icmp, icmp) --> or (zext icmp), (zext icmp) if at least one
-    // of the (zext icmp) will be transformed.
+    // zext (or icmp, icmp) -> or (zext icmp), (zext icmp) if at least one
+    // of the (zext icmp) can be eliminated. If so, immediately perform the
+    // according elimination.
     ICmpInst *LHS = dyn_cast<ICmpInst>(SrcI->getOperand(0));
     ICmpInst *RHS = dyn_cast<ICmpInst>(SrcI->getOperand(1));
     if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() &&
         (transformZExtICmp(LHS, CI, false) ||
          transformZExtICmp(RHS, CI, false))) {
-      Value *LCast = Builder->CreateZExt(LHS, CI.getType(), LHS->getName());
-      Value *RCast = Builder->CreateZExt(RHS, CI.getType(), RHS->getName());
-      return BinaryOperator::Create(Instruction::Or, LCast, RCast);
+      // zext (or icmp, icmp) -> or (zext icmp), (zext icmp)
+      auto *LCast = cast<ZExtInst>(
+          Builder->CreateZExt(LHS, CI.getType(), LHS->getName()));
+      auto *RCast = cast<ZExtInst>(
+          Builder->CreateZExt(RHS, CI.getType(), RHS->getName()));
+      BinaryOperator *Or =
+          BinaryOperator::Create(Instruction::Or, LCast, RCast);
+
+      // Perform the elimination.
+      transformZExtICmp(LHS, *LCast);
+      transformZExtICmp(RHS, *LCast);
+
+      return Or;
     }
   }
 
Index: test/Transforms/InstCombine/zext-or-icmp.ll
===================================================================
--- test/Transforms/InstCombine/zext-or-icmp.ll
+++ test/Transforms/InstCombine/zext-or-icmp.ll
@@ -13,8 +13,8 @@
 ; CHECK-LABEL: zext_or_icmp_icmp(
 ; CHECK-NEXT:    %mask = and i8 %a, 1
 ; CHECK-NEXT:    %toBool2 = icmp eq i8 %b, 0
-; CHECK-NEXT:    %1 = xor i8 %mask, 1
 ; CHECK-NEXT:    %toBool22 = zext i1 %toBool2 to i8
+; CHECK-NEXT:    %1 = xor i8 %mask, 1
 ; CHECK-NEXT:    %zext = or i8 %1, %toBool22
 ; CHECK-NEXT:    ret i8 %zext
 }
Index: test/Transforms/InstCombine/zext.ll
===================================================================
--- test/Transforms/InstCombine/zext.ll
+++ test/Transforms/InstCombine/zext.ll
@@ -70,3 +70,72 @@
   ret <2 x i64> %zext2
 }
 
+; Assert that zexts in and(zext(icmp), zext(icmp)) can be folded.
+; CHECK-LABEL: @fold_and_zext_icmp(
+; CHECK-NEXT:    [[ICMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK-NEXT:    [[ICMP2:%.*]] = icmp slt i64 %a, %c
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[ICMP1]], [[ICMP2]]
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[AND]] to i8
+; CHECK-NEXT:    ret i8 [[ZEXT]]
+define i8 @fold_and_zext_icmp(i64 %a, i64 %b, i64 %c) {
+  %1 = icmp sgt i64 %a, %b
+  %2 = zext i1 %1 to i8
+  %3 = icmp slt i64 %a, %c
+  %4 = zext i1 %3 to i8
+  %5 = and i8 %2, %4
+  ret i8 %5
+}
+
+; Assert that zexts in or(zext(icmp), zext(icmp)) can be folded.
+; CHECK-LABEL: @fold_or_zext_icmp(
+; CHECK-NEXT:    [[ICMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK-NEXT:    [[ICMP2:%.*]] = icmp slt i64 %a, %c
+; CHECK-NEXT:    [[OR:%.*]] = or i1 [[ICMP1]], [[ICMP2]]
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[OR]] to i8
+; CHECK-NEXT:    ret i8 [[ZEXT]]
+define i8 @fold_or_zext_icmp(i64 %a, i64 %b, i64 %c) {
+  %1 = icmp sgt i64 %a, %b
+  %2 = zext i1 %1 to i8
+  %3 = icmp slt i64 %a, %c
+  %4 = zext i1 %3 to i8
+  %5 = or i8 %2, %4
+  ret i8 %5
+}
+
+; Assert that zexts in xor(zext(icmp), zext(icmp)) can be folded.
+; CHECK-LABEL: @fold_xor_zext_icmp(
+; CHECK-NEXT:    [[ICMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK-NEXT:    [[ICMP2:%.*]] = icmp slt i64 %a, %c
+; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[ICMP1]], [[ICMP2]]
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[XOR]] to i8
+; CHECK-NEXT:    ret i8 [[ZEXT]]
+define i8 @fold_xor_zext_icmp(i64 %a, i64 %b, i64 %c) {
+  %1 = icmp sgt i64 %a, %b
+  %2 = zext i1 %1 to i8
+  %3 = icmp slt i64 %a, %c
+  %4 = zext i1 %3 to i8
+  %5 = xor i8 %2, %4
+  ret i8 %5
+}
+
+; Assert that zexts in logic(zext(icmp), zext(icmp)) are also folded accross
+; nested logical operators.
+; CHECK-LABEL: @fold_nested_logic_zext_icmp(
+; CHECK-NEXT:    [[ICMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK-NEXT:    [[ICMP2:%.*]] = icmp slt i64 %a, %c
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[ICMP1]], [[ICMP2]]
+; CHECK-NEXT:    [[ICMP3:%.*]] = icmp eq i64 %a, %d
+; CHECK-NEXT:    [[OR:%.*]] = or i1 [[AND]], [[ICMP3]]
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[OR]] to i8
+; CHECK-NEXT:    ret i8 [[ZEXT]]
+define i8 @fold_nested_logic_zext_icmp(i64 %a, i64 %b, i64 %c, i64 %d) {
+  %1 = icmp sgt i64 %a, %b
+  %2 = zext i1 %1 to i8
+  %3 = icmp slt i64 %a, %c
+  %4 = zext i1 %3 to i8
+  %5 = and i8 %2, %4
+  %6 = icmp eq i64 %a, %d
+  %7 = zext i1 %6 to i8
+  %8 = or i8 %5, %7
+  ret i8 %8
+}