diff --git a/llvm/include/llvm/IR/InstrTypes.h b/llvm/include/llvm/IR/InstrTypes.h
--- a/llvm/include/llvm/IR/InstrTypes.h
+++ b/llvm/include/llvm/IR/InstrTypes.h
@@ -820,6 +820,9 @@
     return P >= FIRST_ICMP_PREDICATE && P <= LAST_ICMP_PREDICATE;
   }
 
+  /// Returns if this cmp is only used by a singular assume
+  bool isOnlyAssumedTrue() const;
+
   static StringRef getPredicateName(Predicate P);
 
   bool isFPPredicate() const { return isFPPredicate(getPredicate()); }
diff --git a/llvm/lib/Analysis/AssumptionCache.cpp b/llvm/lib/Analysis/AssumptionCache.cpp
--- a/llvm/lib/Analysis/AssumptionCache.cpp
+++ b/llvm/lib/Analysis/AssumptionCache.cpp
@@ -115,13 +115,26 @@
       AddAffectedFromEq(B);
     }
 
-    Value *X;
-    // Handle (A + C1) u< C2, which is the canonical form of A > C3 && A < C4,
-    // and recognized by LVI at least.
-    if (Pred == ICmpInst::ICMP_ULT &&
-        match(A, m_Add(m_Value(X), m_ConstantInt())) &&
-        match(B, m_ConstantInt()))
-      AddAffected(X);
+    else if (Pred == ICmpInst::ICMP_NE) {
+      Value *X, *Y;
+      // Handle (a & b != c). If a/b is a power of 2 we can use this
+      // information.
+      if (match(A, m_And(m_Value(X), m_Value(Y)))) {
+        AddAffected(X);
+        AddAffected(Y);
+      }
+      if (match(B, m_And(m_Value(X), m_Value(Y)))) {
+        AddAffected(X);
+        AddAffected(Y);
+      }
+    } else if (Pred == ICmpInst::ICMP_ULT) {
+      Value *X;
+      // Handle (A + C1) u< C2, which is the canonical form of A > C3 && A < C4,
+      // and recognized by LVI at least.
+      if (match(A, m_Add(m_Value(X), m_ConstantInt())) &&
+          match(B, m_ConstantInt()))
+        AddAffected(X);
+    }
   }
 
   if (TTI) {
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -639,6 +639,7 @@
     Value *RHS;
     CmpInst::Predicate Pred;
     auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V)));
+    // TODO: Also handle assume(V & M) and assume(V + C1 u< C2)
     if (!match(I->getArgOperand(0), m_c_ICmp(Pred, m_V, m_Value(RHS))))
       return false;
 
@@ -706,6 +707,9 @@
     if (!Cmp)
       continue;
 
+    if (!isValidAssumeForContext(I, Q.CxtI, Q.DT))
+      continue;
+
     // We are attempting to compute known bits for the operands of an assume.
     // Do not try to use other assumptions for those recursive calls because
     // that can lead to mutual recursion and a compile-time explosion.
@@ -726,16 +730,15 @@
       break;
     case ICmpInst::ICMP_EQ:
       // assume(v = a)
-      if (match(Cmp, m_c_ICmp(Pred, m_V, m_Value(A))) &&
-          isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+      if (match(Cmp, m_c_ICmp(Pred, m_V, m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         Known.Zero |= RHSKnown.Zero;
         Known.One  |= RHSKnown.One;
       // assume(v & b = a)
       } else if (match(Cmp,
-                       m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A))) &&
-                 isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+                       m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A)))) {
+
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits MaskKnown =
@@ -747,8 +750,7 @@
         Known.One  |= RHSKnown.One  & MaskKnown.One;
       // assume(~(v & b) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_c_And(m_V, m_Value(B))),
-                                     m_Value(A))) &&
-                 isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+                                     m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits MaskKnown =
@@ -760,8 +762,7 @@
         Known.One  |= RHSKnown.Zero & MaskKnown.One;
       // assume(v | b = a)
       } else if (match(Cmp,
-                       m_c_ICmp(Pred, m_c_Or(m_V, m_Value(B)), m_Value(A))) &&
-                 isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+                       m_c_ICmp(Pred, m_c_Or(m_V, m_Value(B)), m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits BKnown =
@@ -773,8 +774,7 @@
         Known.One  |= RHSKnown.One  & BKnown.Zero;
       // assume(~(v | b) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_c_Or(m_V, m_Value(B))),
-                                     m_Value(A))) &&
-                 isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+                                     m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits BKnown =
@@ -786,8 +786,7 @@
         Known.One  |= RHSKnown.Zero & BKnown.Zero;
       // assume(v ^ b = a)
       } else if (match(Cmp,
-                       m_c_ICmp(Pred, m_c_Xor(m_V, m_Value(B)), m_Value(A))) &&
-                 isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+                       m_c_ICmp(Pred, m_c_Xor(m_V, m_Value(B)), m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits BKnown =
@@ -802,8 +801,7 @@
         Known.One  |= RHSKnown.Zero & BKnown.One;
       // assume(~(v ^ b) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_c_Xor(m_V, m_Value(B))),
-                                     m_Value(A))) &&
-                 isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+                                     m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits BKnown =
@@ -819,7 +817,7 @@
       // assume(v << c = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Shl(m_V, m_ConstantInt(C)),
                                      m_Value(A))) &&
-                 isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
+                 C < BitWidth) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
@@ -832,7 +830,7 @@
       // assume(~(v << c) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_Shl(m_V, m_ConstantInt(C))),
                                      m_Value(A))) &&
-                 isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
+                 C < BitWidth) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         // For those bits in RHS that are known, we can propagate them inverted
@@ -844,7 +842,7 @@
       // assume(v >> c = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Shr(m_V, m_ConstantInt(C)),
                                      m_Value(A))) &&
-                 isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
+                 C < BitWidth) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         // For those bits in RHS that are known, we can propagate them to known
@@ -854,7 +852,7 @@
       // assume(~(v >> c) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_Shr(m_V, m_ConstantInt(C))),
                                      m_Value(A))) &&
-                 isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
+                 C < BitWidth) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         // For those bits in RHS that are known, we can propagate them inverted
@@ -865,8 +863,7 @@
       break;
     case ICmpInst::ICMP_SGE:
       // assume(v >=_s c) where c is non-negative
-      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
-          isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
 
@@ -878,8 +875,7 @@
       break;
     case ICmpInst::ICMP_SGT:
       // assume(v >_s c) where c is at least -1.
-      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
-          isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
 
@@ -891,8 +887,7 @@
       break;
     case ICmpInst::ICMP_SLE:
       // assume(v <=_s c) where c is negative
-      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
-          isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
 
@@ -904,8 +899,7 @@
       break;
     case ICmpInst::ICMP_SLT:
       // assume(v <_s c) where c is non-positive
-      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
-          isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
@@ -917,8 +911,7 @@
       break;
     case ICmpInst::ICMP_ULE:
       // assume(v <=_u c)
-      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
-          isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
@@ -928,8 +921,7 @@
       break;
     case ICmpInst::ICMP_ULT:
       // assume(v <_u c)
-      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
-          isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A)))) {
         KnownBits RHSKnown =
             computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
@@ -949,6 +941,30 @@
           Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros());
       }
       break;
+    case ICmpInst::ICMP_NE:
+      // assume (v & b != a)
+      if (match(Cmp, m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A)))) {
+        // We can figure out 1 bit in the following cases:
+        // 1. is_pow2(b) && b == a
+        //      v.zeros[log2(b)] = 1
+        // 2. is_pow2(b) && 0 == a
+        //      v.ones[log2(b)] = 1
+        KnownBits BKnown =
+            computeKnownBits(B, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
+        if (isKnownToBeAPowerOfTwo(B, false, Depth + 1, QueryNoAC)) {
+
+          if (A == B) {
+            Known.Zero |= BKnown.One;
+          } else {
+            KnownBits AKnown = computeKnownBits(A, Depth + 1, QueryNoAC)
+                                   .anyextOrTrunc(BitWidth);
+            if (AKnown.isZero()) {
+              Known.One |= BKnown.One;
+            }
+          }
+        }
+      }
+      break;
     }
   }
 
@@ -2307,8 +2323,10 @@
 }
 
 static bool isKnownNonNullFromDominatingCondition(const Value *V,
-                                                  const Instruction *CtxI,
-                                                  const DominatorTree *DT) {
+                                                  const Query &Q) {
+  const Instruction *CtxI = Q.CxtI;
+  const DominatorTree *DT = Q.DT;
+
   if (isa<Constant>(V))
     return false;
 
@@ -2344,20 +2362,58 @@
     // Consider only compare instructions uniquely controlling a branch
     Value *RHS;
     CmpInst::Predicate Pred;
-    if (!match(U, m_c_ICmp(Pred, m_Specific(V), m_Value(RHS))))
-      continue;
 
+    bool MatchExtraAdd = false;
     bool NonNullIfTrue;
-    if (cmpExcludesZero(Pred, RHS))
-      NonNullIfTrue = true;
-    else if (cmpExcludesZero(CmpInst::getInversePredicate(Pred), RHS))
-      NonNullIfTrue = false;
-    else
+    auto *CmpUse = U;
+    if (!match(U, m_c_ICmp(Pred, m_Specific(V), m_Value(RHS)))) {
+      CmpUse = nullptr;
+      bool MatchExtraAnd = false;
+      const APInt *AddC;
+      if (match(U, m_c_And(m_Specific(V), m_Value()))) {
+        // If And(A, B) is non-zero then neither A nor B can be zero.
+        if (isKnownNonZeroFromAssume(U, Q))
+          return true;
+        MatchExtraAnd = true;
+      } else if (match(U, m_c_Add(m_Specific(V), m_APInt(AddC))))
+        MatchExtraAdd = true;
+      if (MatchExtraAnd || MatchExtraAdd) {
+        for (const auto *U2 : U->users()) {
+          if (match(U2, m_c_ICmp(Pred, m_Specific(U), m_Value(RHS)))) {
+            // Only handle (A + C1) u< C2, which is the canonical form of A > C3
+            // && A < C4
+            if (MatchExtraAdd) {
+              auto *RHSC = dyn_cast<ConstantInt>(RHS);
+              if (RHSC == nullptr || Pred != ICmpInst::ICMP_ULT)
+                continue;
+              NonNullIfTrue = RHSC->getValue().ult(*AddC);
+              if(NonNullIfTrue && dyn_cast<ICmpInst>(U2)->isOnlyAssumedTrue())
+                  return true;
+            }
+            CmpUse = U2;
+            break;
+          }
+        }
+      }
+    }
+
+    if (CmpUse == nullptr)
       continue;
 
+
+    if(!MatchExtraAdd) {
+      if (cmpExcludesZero(Pred, RHS))
+        NonNullIfTrue = true;
+      else if (cmpExcludesZero(CmpInst::getInversePredicate(Pred), RHS))
+        NonNullIfTrue = false;
+      else
+        continue;
+    }
+
     SmallVector<const User *, 4> WorkList;
     SmallPtrSet<const User *, 4> Visited;
-    for (const auto *CmpU : U->users()) {
+    for (const auto *CmpU : CmpUse->users()) {
+
       assert(WorkList.empty() && "Should be!");
       if (Visited.insert(CmpU).second)
         WorkList.push_back(CmpU);
@@ -2377,6 +2433,7 @@
             continue;
           }
 
+
         if (const BranchInst *BI = dyn_cast<BranchInst>(Curr)) {
           assert(BI->isConditional() && "uses a comparison!");
 
@@ -2551,8 +2608,7 @@
     }
   }
 
-  if (!isa<Constant>(V) &&
-      isKnownNonNullFromDominatingCondition(V, Q.CxtI, Q.DT))
+  if (!isa<Constant>(V) && isKnownNonNullFromDominatingCondition(V, Q))
     return true;
 
   const Operator *I = dyn_cast<Operator>(V);
diff --git a/llvm/lib/IR/Instructions.cpp b/llvm/lib/IR/Instructions.cpp
--- a/llvm/lib/IR/Instructions.cpp
+++ b/llvm/lib/IR/Instructions.cpp
@@ -26,6 +26,7 @@
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Metadata.h"
@@ -4060,6 +4061,10 @@
   llvm_unreachable("Unsupported predicate kind");
 }
 
+bool CmpInst::isOnlyAssumedTrue() const {
+  return hasOneUse() && dyn_cast<AssumeInst>(user_back()) != nullptr;
+}
+
 CmpInst::Predicate CmpInst::getInversePredicate(Predicate pred) {
   switch (pred) {
     default: llvm_unreachable("Unknown cmp predicate!");
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -1296,7 +1296,48 @@
     if (XKnown.countMaxPopulation() == 1 && YKnown.countMinPopulation() >= 2)
       return new ICmpInst(Pred, X, Cmp.getOperand(1));
   }
-
+  // (icmp eq/ne (mul X Y)) ->
+  // if Y % 2 != 0 AND X % 2 != 0
+  //    (false/true)
+  // if X % 2 != 0
+  //    (icmp eq/ne Y)
+  // if Y % 2 != 0
+  //    (icmp eq/ne X)
+  // if X non-zero and Y non-zero and no_overflow(X * Y)
+  //    (false/true)
+  // if Y non-zero and no_overflow(X * Y)
+  //    (icmp eq/ne X)
+  // if X non-zero and no_overflow(X * Y)
+  //    (icmp eq/ne Y)
+  if (match(Cmp.getOperand(0), m_Mul(m_Value(X), m_Value(Y))) &&
+      ICmpInst::isEquality(Pred)) {
+    KnownBits XKnown = computeKnownBits(X, 0, &Cmp);
+    KnownBits YKnown = computeKnownBits(Y, 0, &Cmp);
+    bool XExtra = XKnown.countMaxTrailingZeros() == 0;
+    bool YExtra = YKnown.countMaxTrailingZeros() == 0;
+    if (!XExtra && !YExtra) {
+      BinaryOperator *BO0 = dyn_cast<BinaryOperator>(Cmp.getOperand(0));
+      if (BO0 && (BO0->hasNoUnsignedWrap() || BO0->hasNoSignedWrap())) {
+          const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
+          XExtra = llvm::isKnownNonZero(X, DL, 0, Q.AC, Q.CxtI, Q.DT);
+          YExtra = llvm::isKnownNonZero(Y, DL, 0, Q.AC, Q.CxtI, Q.DT);
+       }
+    }
+    // If both are odd the multiplication is non-zero
+    if (XExtra && YExtra)
+      return (Pred == ICmpInst::ICMP_EQ)
+                 ? replaceInstUsesWith(Cmp,
+                                       ConstantInt::getFalse(Cmp.getType()))
+                 : replaceInstUsesWith(Cmp,
+                                       ConstantInt::getTrue(Cmp.getType()));
+
+    // If one of the ops is odd, we can replace the multiplation with just
+    // testing the other op
+    else if (XExtra)
+      return new ICmpInst(Pred, Y, Cmp.getOperand(1));
+    else if (YExtra)
+      return new ICmpInst(Pred, X, Cmp.getOperand(1));
+  }
   return nullptr;
 }
 
@@ -2799,9 +2840,13 @@
 
   // (X + -1) <u C --> X <=u C (if X is never null)
   if (Pred == CmpInst::ICMP_ULT && C2->isAllOnes()) {
-    const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
-    if (llvm::isKnownNonZero(X, DL, 0, Q.AC, Q.CxtI, Q.DT))
-      return new ICmpInst(ICmpInst::ICMP_ULE, X, ConstantInt::get(Ty, C));
+    // Don't make this transform if the only use of this Cmp is assume as we
+    // both lose information and de-canonicalize the (A < C1 && A > C2) case
+    if (!Cmp.isOnlyAssumedTrue()) {
+      const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
+      if (llvm::isKnownNonZero(X, DL, 0, Q.AC, Q.CxtI, Q.DT))
+        return new ICmpInst(ICmpInst::ICMP_ULE, X, ConstantInt::get(Ty, C));
+    }
   }
 
   if (!Add->hasOneUse())
diff --git a/llvm/test/Transforms/InstCombine/icmp-binop.ll b/llvm/test/Transforms/InstCombine/icmp-binop.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/InstCombine/icmp-binop.ll
@@ -0,0 +1,4418 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+
+define i64 @mul_assume_V_oddC_u64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_V_oddC_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V:%.*]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %mul = mul i64 %v, 3
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_V_evenC_u64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_V_evenC_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[V:%.*]], 123132
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %mul = mul i64 %v, 123132
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_V_2C_u64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_V_2C_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MUL_MASK:%.*]] = and i64 [[V:%.*]], 9223372036854775807
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL_MASK]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %mul.mask = and i64 %v, 9223372036854775807
+  %tobool.not = icmp eq i64 %mul.mask, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_oddV_oddC_u64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_oddV_oddC_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %mul = mul i64 %v, 3
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_oddV_evenC_u64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_oddV_evenC_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %mul.mask = and i64 %v, 9223372036854775807
+  %tobool.not = icmp eq i64 %mul.mask, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_evenV_oddC_u64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_evenV_oddC_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp.not = icmp eq i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %mul = mul i64 %v, 3
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_evenV_evenC_u64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_evenV_evenC_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[MUL_MASK:%.*]] = and i64 [[V]], 9223372036854775806
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL_MASK]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp.not = icmp eq i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %mul.mask = and i64 %v, 9223372036854775806
+  %tobool.not = icmp eq i64 %mul.mask, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_V_oddV_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_V_oddV_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V:%.*]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %and = and i64 %other, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %mul = mul i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_V_evenV_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_V_evenV_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[OTHER]], [[V:%.*]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %and = and i64 %other, 1
+  %cmp.not = icmp eq i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %mul = mul i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_oddV_oddV_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_oddV_oddV_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2 = icmp ne i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  %mul = mul i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_oddV_evenV_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_oddV_evenV_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2_NOT:%.*]] = icmp eq i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2_NOT]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[OTHER]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2.not = icmp eq i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2.not)
+  %mul = mul i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_no_of_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_no_of_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[V:%.*]], 8
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i64 [[OTHER:%.*]], 8
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP1]])
+; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i64 [[OTHER]], [[V]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %cmp = icmp ult i64 %v, 8
+  tail call void @llvm.assume(i1 %cmp)
+  %cmp1 = icmp ult i64 %other, 8
+  tail call void @llvm.assume(i1 %cmp1)
+  %mul = mul nuw nsw i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_no_of_nz1_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz1_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[V:%.*]], -1
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i64 [[TMP0]], 7
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[OTHER:%.*]], 8
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[OTHER]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %0 = add i64 %v, -1
+  %or.cond = icmp ult i64 %0, 7
+  tail call void @llvm.assume(i1 %or.cond)
+  %cmp2 = icmp ult i64 %other, 8
+  tail call void @llvm.assume(i1 %cmp2)
+  %mul = mul nuw nsw i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_no_of_nz2_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz2_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[V:%.*]], -1
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i64 [[TMP0]], 7
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[OTHER:%.*]], -1
+; CHECK-NEXT:    [[OR_COND7:%.*]] = icmp ult i64 [[TMP1]], 7
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND7]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %0 = add i64 %v, -1
+  %or.cond = icmp ult i64 %0, 7
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i64 %other, -1
+  %or.cond7 = icmp ult i64 %1, 7
+  tail call void @llvm.assume(i1 %or.cond7)
+  ret i64 0
+}
+
+define i64 @mul_assume_no_of_nz3_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz3_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[V:%.*]], -2
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i64 [[TMP0]], 6
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[OTHER:%.*]], -1
+; CHECK-NEXT:    [[OR_COND7:%.*]] = icmp ult i64 [[TMP1]], 7
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND7]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %0 = add i64 %v, -2
+  %or.cond = icmp ult i64 %0, 6
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i64 %other, -1
+  %or.cond7 = icmp ult i64 %1, 7
+  tail call void @llvm.assume(i1 %or.cond7)
+  ret i64 0
+}
+
+define i64 @mul_assume_no_of_nz4_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz4_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[V:%.*]], -2
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i64 [[TMP0]], 6
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[OTHER:%.*]], -3
+; CHECK-NEXT:    [[OR_COND7:%.*]] = icmp ult i64 [[TMP1]], 5
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND7]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %0 = add i64 %v, -2
+  %or.cond = icmp ult i64 %0, 6
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i64 %other, -3
+  %or.cond7 = icmp ult i64 %1, 5
+  tail call void @llvm.assume(i1 %or.cond7)
+  ret i64 0
+}
+
+define i64 @mul_assume_may_of_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_may_of_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[V:%.*]], -2
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i64 [[TMP0]], 1073741819
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[OTHER:%.*]], -3
+; CHECK-NEXT:    [[OR_COND7:%.*]] = icmp ult i64 [[TMP1]], 536870908
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND7]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %0 = add i64 %v, -2
+  %or.cond = icmp ult i64 %0, 1073741819
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i64 %other, -3
+  %or.cond7 = icmp ult i64 %1, 536870908
+  tail call void @llvm.assume(i1 %or.cond7)
+  ret i64 0
+}
+
+define i64 @return_or_1_not_needed_u64(i64 %v) {
+; CHECK-LABEL: @return_or_1_not_needed_u64(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    ret i64 [[V]]
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %or = or i64 %v, 1
+  ret i64 %or
+}
+
+define i64 @return_or_1_needed_u64(i64 %v) {
+; CHECK-LABEL: @return_or_1_needed_u64(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[OR:%.*]] = or i64 [[V]], 1
+; CHECK-NEXT:    ret i64 [[OR]]
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp.not = icmp eq i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %or = or i64 %v, 1
+  ret i64 %or
+}
+
+define i64 @return_and_n2_not_needed_u64(i64 returned %v) {
+; CHECK-LABEL: @return_and_n2_not_needed_u64(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    ret i64 [[V]]
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp.not = icmp eq i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  ret i64 %v
+}
+
+define i64 @return_and_n2_needed_u64(i64 %v) {
+; CHECK-LABEL: @return_and_n2_needed_u64(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[V]], -2
+; CHECK-NEXT:    ret i64 [[AND1]]
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp.not = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %and1 = and i64 %v, -2
+  ret i64 %and1
+}
+
+define i64 @return_and_n2_not_needed_mod_u64(i64 returned %v) {
+; CHECK-LABEL: @return_and_n2_not_needed_mod_u64(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[REM:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[REM]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    ret i64 [[V]]
+;
+entry:
+  %rem = and i64 %v, 1
+  %cmp.not = icmp eq i64 %rem, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  ret i64 %v
+}
+
+define i64 @return_and_n2_needed_mod_u64(i64 %v) {
+; CHECK-LABEL: @return_and_n2_needed_mod_u64(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[REM:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp ne i64 [[REM]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V]], -2
+; CHECK-NEXT:    ret i64 [[AND]]
+;
+entry:
+  %rem = and i64 %v, 1
+  %cmp.not = icmp ne i64 %rem, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %and = and i64 %v, -2
+  ret i64 %and
+}
+
+define i64 @or_assume_V_oddV_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_V_oddV_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %other, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %or = or i64 %other, %v
+  %tobool.not = icmp eq i64 %or, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @or_assume_V_evenV_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_V_evenV_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[OTHER:%.*]], 3
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 2
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %other, 3
+  %cmp.not = icmp eq i64 %and, 2
+  tail call void @llvm.assume(i1 %cmp.not)
+  ret i64 0
+}
+
+define i64 @or_assume_oddV_oddV_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2 = icmp ne i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  %or = or i64 %other, %v
+  %tobool.not = icmp eq i64 %or, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @or_assume_oddV_evenV_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_oddV_evenV_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2_NOT:%.*]] = icmp eq i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2_NOT]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2.not = icmp eq i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2.not)
+  ret i64 0
+}
+
+define i64 @or_assume_oddV_oddV_and1_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_and1_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2 = icmp ne i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  ret i64 0
+}
+
+define i64 @or_assume_oddV_oddV_and2_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_and2_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2 = icmp ne i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  ret i64 0
+}
+
+define i64 @or_assume_oddV_oddV_and3_u64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_and3_u64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2 = icmp ne i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  ret i64 0
+}
+
+define i64 @mul_assume_V_oddC_s64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_V_oddC_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V:%.*]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %tobool.not = icmp eq i64 %v, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_V_evenC_s64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_V_evenC_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V:%.*]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %tobool.not = icmp eq i64 %v, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_V_2C_s64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_V_2C_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V:%.*]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %tobool.not = icmp eq i64 %v, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_oddV_oddC_s64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_oddV_oddC_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %tobool.not = icmp eq i64 %v, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_oddV_evenC_s64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_oddV_evenC_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %tobool.not = icmp eq i64 %v, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_evenV_oddC_s64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_evenV_oddC_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp.not = icmp eq i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %tobool.not = icmp eq i64 %v, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_evenV_evenC_s64_setz(i64 %v) {
+; CHECK-LABEL: @mul_assume_evenV_evenC_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp.not = icmp eq i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %tobool.not = icmp eq i64 %v, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_V_oddV_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_V_oddV_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V:%.*]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %and = and i64 %other, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %mul = mul nsw i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_V_evenV_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_V_evenV_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[OTHER]], [[V:%.*]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %and = and i64 %other, 1
+  %cmp.not = icmp eq i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %mul = mul nsw i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_oddV_oddV_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_oddV_oddV_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2 = icmp ne i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  %mul = mul nsw i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_oddV_evenV_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_oddV_evenV_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2_NOT:%.*]] = icmp eq i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2_NOT]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[OTHER]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2.not = icmp eq i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2.not)
+  %mul = mul nsw i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_no_of_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_no_of_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[V:%.*]], 8
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[OTHER:%.*]], 8
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP1]])
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[OTHER]], [[V]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %cmp = icmp slt i64 %v, 8
+  tail call void @llvm.assume(i1 %cmp)
+  %cmp1 = icmp slt i64 %other, 8
+  tail call void @llvm.assume(i1 %cmp1)
+  %mul = mul nsw i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_no_of_nz1_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz1_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[V:%.*]], 8
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i64 [[V]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP1]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i64 [[OTHER:%.*]], 8
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[OTHER]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %cmp = icmp slt i64 %v, 8
+  %cmp1 = icmp ne i64 %v, 0
+  tail call void @llvm.assume(i1 %cmp)
+  tail call void @llvm.assume(i1 %cmp1)
+  %cmp2 = icmp slt i64 %other, 8
+  tail call void @llvm.assume(i1 %cmp2)
+  %mul = mul nsw i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_no_of_nz2_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz2_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[V:%.*]], 8
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i64 [[V]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP1]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i64 [[OTHER:%.*]], 8
+; CHECK-NEXT:    [[CMP4:%.*]] = icmp ne i64 [[OTHER]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP4]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %cmp = icmp slt i64 %v, 8
+  %cmp1 = icmp ne i64 %v, 0
+  tail call void @llvm.assume(i1 %cmp)
+  tail call void @llvm.assume(i1 %cmp1)
+  %cmp2 = icmp slt i64 %other, 8
+  %cmp4 = icmp ne i64 %other, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  tail call void @llvm.assume(i1 %cmp4)
+  ret i64 0
+}
+
+define i64 @mul_assume_no_of_nz3_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz3_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[V:%.*]], -2
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i64 [[TMP0]], 6
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i64 [[OTHER:%.*]], 8
+; CHECK-NEXT:    [[CMP4:%.*]] = icmp ne i64 [[OTHER]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP4]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %0 = add i64 %v, -2
+  %or.cond = icmp ult i64 %0, 6
+  tail call void @llvm.assume(i1 %or.cond)
+  %cmp2 = icmp slt i64 %other, 8
+  %cmp4 = icmp ne i64 %other, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  tail call void @llvm.assume(i1 %cmp4)
+  %mul = mul nsw i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @mul_assume_no_of_nz4_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz4_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[V:%.*]], -2
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i64 [[TMP0]], 6
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[OTHER:%.*]], -3
+; CHECK-NEXT:    [[OR_COND7:%.*]] = icmp ult i64 [[TMP1]], 5
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND7]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %0 = add i64 %v, -2
+  %or.cond = icmp ult i64 %0, 6
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i64 %other, -3
+  %or.cond7 = icmp ult i64 %1, 5
+  tail call void @llvm.assume(i1 %or.cond7)
+  ret i64 0
+}
+
+define i64 @mul_assume_may_of_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_may_of_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[V:%.*]], -2
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i64 [[TMP0]], 1073741819
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[OTHER:%.*]], -3
+; CHECK-NEXT:    [[OR_COND7:%.*]] = icmp ult i64 [[TMP1]], 536870908
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND7]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %0 = add i64 %v, -2
+  %or.cond = icmp ult i64 %0, 1073741819
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i64 %other, -3
+  %or.cond7 = icmp ult i64 %1, 536870908
+  tail call void @llvm.assume(i1 %or.cond7)
+  ret i64 0
+}
+
+define i64 @mul_assume_bad_bounds_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @mul_assume_bad_bounds_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[V:%.*]], 9
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i64 [[TMP0]], 17
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[OTHER:%.*]], 10
+; CHECK-NEXT:    [[OR_COND7:%.*]] = icmp ult i64 [[TMP1]], 18
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND7]])
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[OTHER]], [[V]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[CONV]]
+;
+entry:
+  %0 = add i64 %v, 9
+  %or.cond = icmp ult i64 %0, 17
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i64 %other, 10
+  %or.cond7 = icmp ult i64 %1, 18
+  tail call void @llvm.assume(i1 %or.cond7)
+  %mul = mul nsw i64 %other, %v
+  %tobool.not = icmp eq i64 %mul, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @or_assume_V_oddV_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_V_oddV_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %other, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %or = or i64 %other, %v
+  %tobool.not = icmp eq i64 %or, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @or_assume_V_evenV_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_V_evenV_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[OTHER:%.*]], 3
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 2
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %other, 3
+  %cmp.not = icmp eq i64 %and, 2
+  tail call void @llvm.assume(i1 %cmp.not)
+  ret i64 0
+}
+
+define i64 @or_assume_oddV_oddV_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2 = icmp ne i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  %or = or i64 %other, %v
+  %tobool.not = icmp eq i64 %or, 0
+  %conv = zext i1 %tobool.not to i64
+  ret i64 %conv
+}
+
+define i64 @or_assume_oddV_evenV_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_oddV_evenV_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2_NOT:%.*]] = icmp eq i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2_NOT]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2.not = icmp eq i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2.not)
+  ret i64 0
+}
+
+define i64 @or_assume_oddV_oddV_and1_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_and1_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2 = icmp ne i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  ret i64 0
+}
+
+define i64 @or_assume_oddV_oddV_and2_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_and2_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2 = icmp ne i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  ret i64 0
+}
+
+define i64 @or_assume_oddV_oddV_and3_s64_setz(i64 %v, i64 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_and3_s64_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  %and = and i64 %v, 1
+  %cmp = icmp ne i64 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i64 %other, 1
+  %cmp2 = icmp ne i64 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  ret i64 0
+}
+
+define i32 @mul_assume_V_oddC_u32_brz(i32 %v) {
+; CHECK-LABEL: @mul_assume_V_oddC_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[V:%.*]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL1]], [[IF_END]] ], [ [[CALL]], [[IF_THEN]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %mul = mul i32 %v, 3
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %call1 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i32 [ %call1, %if.end ], [ %call, %if.then ]
+  ret i32 %retval.0
+}
+
+declare i32 @foo32(...)
+
+declare i32 @bar32(...)
+
+define i32 @mul_assume_V_evenC_u32_brz(i32 %v) {
+; CHECK-LABEL: @mul_assume_V_evenC_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[V:%.*]], 123132
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL1]], [[IF_END]] ], [ [[CALL]], [[IF_THEN]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %mul = mul i32 %v, 123132
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %call1 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i32 [ %call1, %if.end ], [ %call, %if.then ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_V_2C_u32_brz(i32 %v) {
+; CHECK-LABEL: @mul_assume_V_2C_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MUL_MASK:%.*]] = and i32 [[V:%.*]], 2147483647
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL_MASK]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL1]], [[IF_END]] ], [ [[CALL]], [[IF_THEN]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %mul.mask = and i32 %v, 2147483647
+  %tobool.not = icmp eq i32 %mul.mask, 0
+  br i1 %tobool.not, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %call1 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i32 [ %call1, %if.end ], [ %call, %if.then ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_oddV_oddC_u32_brz(i32 %v) {
+; CHECK-LABEL: @mul_assume_oddV_oddC_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    br i1 false, label [[IF_THEN1:%.*]], label [[IF_END2:%.*]]
+; CHECK:       if.then1:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end2:
+; CHECK-NEXT:    [[CALL3:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL3]], [[IF_END2]] ], [ poison, [[IF_THEN1]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %mul = mul i32 %v, 3
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then1, label %if.end2
+
+if.then1:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end2:                                          ; preds = %entry
+  %call3 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end2, %if.then1
+  %retval.0 = phi i32 [ %call3, %if.end2 ], [ %call, %if.then1 ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_oddV_evenC_u32_brz(i32 %v) {
+; CHECK-LABEL: @mul_assume_oddV_evenC_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    br i1 false, label [[IF_THEN1:%.*]], label [[IF_END2:%.*]]
+; CHECK:       if.then1:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end2:
+; CHECK-NEXT:    [[CALL3:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL3]], [[IF_END2]] ], [ poison, [[IF_THEN1]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %mul.mask = and i32 %v, 2147483647
+  %tobool.not = icmp eq i32 %mul.mask, 0
+  br i1 %tobool.not, label %if.then1, label %if.end2
+
+if.then1:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end2:                                          ; preds = %entry
+  %call3 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end2, %if.then1
+  %retval.0 = phi i32 [ %call3, %if.end2 ], [ %call, %if.then1 ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_evenV_oddC_u32_brz(i32 %v) {
+; CHECK-LABEL: @mul_assume_evenV_oddC_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[V]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN1:%.*]], label [[IF_END2:%.*]]
+; CHECK:       if.then1:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end2:
+; CHECK-NEXT:    [[CALL3:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL3]], [[IF_END2]] ], [ [[CALL]], [[IF_THEN1]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp.not = icmp eq i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %mul = mul i32 %v, 3
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then1, label %if.end2
+
+if.then1:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end2:                                          ; preds = %entry
+  %call3 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end2, %if.then1
+  %retval.0 = phi i32 [ %call3, %if.end2 ], [ %call, %if.then1 ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_evenV_evenC_u32_brz(i32 %v) {
+; CHECK-LABEL: @mul_assume_evenV_evenC_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[MUL_MASK:%.*]] = and i32 [[V]], 2147483646
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL_MASK]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN1:%.*]], label [[IF_END2:%.*]]
+; CHECK:       if.then1:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end2:
+; CHECK-NEXT:    [[CALL3:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL3]], [[IF_END2]] ], [ [[CALL]], [[IF_THEN1]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp.not = icmp eq i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %mul.mask = and i32 %v, 2147483646
+  %tobool.not = icmp eq i32 %mul.mask, 0
+  br i1 %tobool.not, label %if.then1, label %if.end2
+
+if.then1:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end2:                                          ; preds = %entry
+  %call3 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end2, %if.then1
+  %retval.0 = phi i32 [ %call3, %if.end2 ], [ %call, %if.then1 ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_V_oddV_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @mul_assume_V_oddV_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[V:%.*]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN1:%.*]], label [[IF_END2:%.*]]
+; CHECK:       if.then1:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end2:
+; CHECK-NEXT:    [[CALL3:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL3]], [[IF_END2]] ], [ [[CALL]], [[IF_THEN1]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %and = and i32 %other, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %mul = mul i32 %other, %v
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then1, label %if.end2
+
+if.then1:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end2:                                          ; preds = %entry
+  %call3 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end2, %if.then1
+  %retval.0 = phi i32 [ %call3, %if.end2 ], [ %call, %if.then1 ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_V_evenV_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @mul_assume_V_evenV_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[OTHER]], [[V:%.*]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN1:%.*]], label [[IF_END2:%.*]]
+; CHECK:       if.then1:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end2:
+; CHECK-NEXT:    [[CALL3:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL3]], [[IF_END2]] ], [ [[CALL]], [[IF_THEN1]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %and = and i32 %other, 1
+  %cmp.not = icmp eq i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %mul = mul i32 %other, %v
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then1, label %if.end2
+
+if.then1:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end2:                                          ; preds = %entry
+  %call3 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end2, %if.then1
+  %retval.0 = phi i32 [ %call3, %if.end2 ], [ %call, %if.then1 ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_oddV_oddV_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @mul_assume_oddV_oddV_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    br i1 false, label [[IF_THEN5:%.*]], label [[IF_END6:%.*]]
+; CHECK:       if.then5:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL7]], [[IF_END6]] ], [ poison, [[IF_THEN5]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i32 %other, 1
+  %cmp2 = icmp ne i32 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  %mul = mul i32 %other, %v
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then5, label %if.end6
+
+if.then5:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end6:                                          ; preds = %entry
+  %call7 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end6, %if.then5
+  %retval.0 = phi i32 [ %call7, %if.end6 ], [ %call, %if.then5 ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_oddV_evenV_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @mul_assume_oddV_evenV_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2_NOT:%.*]] = icmp eq i32 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2_NOT]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[OTHER]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN5:%.*]], label [[IF_END6:%.*]]
+; CHECK:       if.then5:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL7]], [[IF_END6]] ], [ [[CALL]], [[IF_THEN5]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i32 %other, 1
+  %cmp2.not = icmp eq i32 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2.not)
+  %mul = mul i32 %other, %v
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then5, label %if.end6
+
+if.then5:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end6:                                          ; preds = %entry
+  %call7 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end6, %if.then5
+  %retval.0 = phi i32 [ %call7, %if.end6 ], [ %call, %if.then5 ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_no_of_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @mul_assume_no_of_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[V:%.*]], 8
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[OTHER:%.*]], 8
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP1]])
+; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i32 [[OTHER]], [[V]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN4:%.*]], label [[IF_END5:%.*]]
+; CHECK:       if.then4:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end5:
+; CHECK-NEXT:    [[CALL6:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL6]], [[IF_END5]] ], [ [[CALL]], [[IF_THEN4]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %cmp = icmp ult i32 %v, 8
+  tail call void @llvm.assume(i1 %cmp)
+  %cmp1 = icmp ult i32 %other, 8
+  tail call void @llvm.assume(i1 %cmp1)
+  %mul = mul nuw nsw i32 %other, %v
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then4, label %if.end5
+
+if.then4:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end5:                                          ; preds = %entry
+  %call6 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end5, %if.then4
+  %retval.0 = phi i32 [ %call6, %if.end5 ], [ %call, %if.then4 ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_no_of_nz1_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz1_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[V:%.*]], -1
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i32 [[TMP0]], 7
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[OTHER:%.*]], 8
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[OTHER]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN5:%.*]], label [[IF_END6:%.*]]
+; CHECK:       if.then5:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL7]], [[IF_END6]] ], [ [[CALL]], [[IF_THEN5]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %0 = add i32 %v, -1
+  %or.cond = icmp ult i32 %0, 7
+  tail call void @llvm.assume(i1 %or.cond)
+  %cmp2 = icmp ult i32 %other, 8
+  tail call void @llvm.assume(i1 %cmp2)
+  %mul = mul nuw nsw i32 %other, %v
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then5, label %if.end6
+
+if.then5:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end6:                                          ; preds = %entry
+  %call7 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end6, %if.then5
+  %retval.0 = phi i32 [ %call7, %if.end6 ], [ %call, %if.then5 ]
+  ret i32 %retval.0
+}
+
+define i32 @mul_assume_no_of_nz2_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz2_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[V:%.*]], -1
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i32 [[TMP0]], 7
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[OTHER:%.*]], -1
+; CHECK-NEXT:    [[OR_COND10:%.*]] = icmp ult i32 [[TMP1]], 7
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND10]])
+; CHECK-NEXT:    [[CALL9:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    ret i32 [[CALL9]]
+;
+entry:
+  %0 = add i32 %v, -1
+  %or.cond = icmp ult i32 %0, 7
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i32 %other, -1
+  %or.cond10 = icmp ult i32 %1, 7
+  tail call void @llvm.assume(i1 %or.cond10)
+  %call9 = tail call i32 (...) @bar32()
+  ret i32 %call9
+}
+
+define i32 @mul_assume_no_of_nz3_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz3_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[V:%.*]], -2
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i32 [[TMP0]], 6
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[OTHER:%.*]], -1
+; CHECK-NEXT:    [[OR_COND10:%.*]] = icmp ult i32 [[TMP1]], 7
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND10]])
+; CHECK-NEXT:    [[CALL9:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    ret i32 [[CALL9]]
+;
+entry:
+  %0 = add i32 %v, -2
+  %or.cond = icmp ult i32 %0, 6
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i32 %other, -1
+  %or.cond10 = icmp ult i32 %1, 7
+  tail call void @llvm.assume(i1 %or.cond10)
+  %call9 = tail call i32 (...) @bar32()
+  ret i32 %call9
+}
+
+define i32 @mul_assume_no_of_nz4_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @mul_assume_no_of_nz4_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[V:%.*]], -2
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i32 [[TMP0]], 6
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[OTHER:%.*]], -3
+; CHECK-NEXT:    [[OR_COND10:%.*]] = icmp ult i32 [[TMP1]], 5
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND10]])
+; CHECK-NEXT:    [[CALL9:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    ret i32 [[CALL9]]
+;
+entry:
+  %0 = add i32 %v, -2
+  %or.cond = icmp ult i32 %0, 6
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i32 %other, -3
+  %or.cond10 = icmp ult i32 %1, 5
+  tail call void @llvm.assume(i1 %or.cond10)
+  %call9 = tail call i32 (...) @bar32()
+  ret i32 %call9
+}
+
+define i32 @mul_assume_may_of_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @mul_assume_may_of_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[V:%.*]], -2
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i32 [[TMP0]], 1073741819
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND]])
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[OTHER:%.*]], -3
+; CHECK-NEXT:    [[OR_COND10:%.*]] = icmp ult i32 [[TMP1]], 536870908
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR_COND10]])
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[OTHER]], [[V]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN7:%.*]], label [[IF_END8:%.*]]
+; CHECK:       if.then7:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end8:
+; CHECK-NEXT:    [[CALL9:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL9]], [[IF_END8]] ], [ [[CALL]], [[IF_THEN7]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %0 = add i32 %v, -2
+  %or.cond = icmp ult i32 %0, 1073741819
+  tail call void @llvm.assume(i1 %or.cond)
+  %1 = add i32 %other, -3
+  %or.cond10 = icmp ult i32 %1, 536870908
+  tail call void @llvm.assume(i1 %or.cond10)
+  %mul = mul i32 %other, %v
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.then7, label %if.end8
+
+if.then7:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end8:                                          ; preds = %entry
+  %call9 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end8, %if.then7
+  %retval.0 = phi i32 [ %call9, %if.end8 ], [ %call, %if.then7 ]
+  ret i32 %retval.0
+}
+
+define i32 @return_or_1_not_needed_u32(i32 %v) {
+; CHECK-LABEL: @return_or_1_not_needed_u32(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    ret i32 [[V]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %or = or i32 %v, 1
+  ret i32 %or
+}
+
+define i32 @return_or_1_needed_u32(i32 %v) {
+; CHECK-LABEL: @return_or_1_needed_u32(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[V]], 1
+; CHECK-NEXT:    ret i32 [[OR]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp.not = icmp eq i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %or = or i32 %v, 1
+  ret i32 %or
+}
+
+define i32 @return_and_n2_not_needed_u32(i32 returned %v) {
+; CHECK-LABEL: @return_and_n2_not_needed_u32(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    ret i32 [[V]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp.not = icmp eq i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  ret i32 %v
+}
+
+define i32 @return_and_n2_needed_u32(i32 %v) {
+; CHECK-LABEL: @return_and_n2_needed_u32(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[V]], -2
+; CHECK-NEXT:    ret i32 [[AND1]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp.not = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %and1 = and i32 %v, -2
+  ret i32 %and1
+}
+
+define i32 @return_and_n2_not_needed_mod_u32(i32 returned %v) {
+; CHECK-LABEL: @return_and_n2_not_needed_mod_u32(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[REM:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[REM]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    ret i32 [[V]]
+;
+entry:
+  %rem = and i32 %v, 1
+  %cmp.not = icmp eq i32 %rem, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  ret i32 %v
+}
+
+define i32 @return_and_n2_needed_mod_u32(i32 %v) {
+; CHECK-LABEL: @return_and_n2_needed_mod_u32(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[REM:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp ne i32 [[REM]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V]], -2
+; CHECK-NEXT:    ret i32 [[AND]]
+;
+entry:
+  %rem = and i32 %v, 1
+  %cmp.not = icmp ne i32 %rem, 0
+  tail call void @llvm.assume(i1 %cmp.not)
+  %and = and i32 %v, -2
+  ret i32 %and
+}
+
+define i32 @or_assume_V_oddV_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @or_assume_V_oddV_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    br i1 false, label [[IF_THEN1:%.*]], label [[IF_END2:%.*]]
+; CHECK:       if.then1:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end2:
+; CHECK-NEXT:    [[CALL3:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL3]], [[IF_END2]] ], [ poison, [[IF_THEN1]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %and = and i32 %other, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %or = or i32 %other, %v
+  %tobool.not = icmp eq i32 %or, 0
+  br i1 %tobool.not, label %if.then1, label %if.end2
+
+if.then1:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end2:                                          ; preds = %entry
+  %call3 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end2, %if.then1
+  %retval.0 = phi i32 [ %call3, %if.end2 ], [ %call, %if.then1 ]
+  ret i32 %retval.0
+}
+
+define i32 @or_assume_V_evenV_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @or_assume_V_evenV_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[OTHER:%.*]], 3
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 2
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
+; CHECK-NEXT:    [[CALL3:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    ret i32 [[CALL3]]
+;
+entry:
+  %and = and i32 %other, 3
+  %cmp.not = icmp eq i32 %and, 2
+  tail call void @llvm.assume(i1 %cmp.not)
+  %call3 = tail call i32 (...) @bar32()
+  ret i32 %call3
+}
+
+define i32 @or_assume_oddV_oddV_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    br i1 false, label [[IF_THEN5:%.*]], label [[IF_END6:%.*]]
+; CHECK:       if.then5:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL7]], [[IF_END6]] ], [ poison, [[IF_THEN5]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i32 %other, 1
+  %cmp2 = icmp ne i32 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  %or = or i32 %other, %v
+  %tobool.not = icmp eq i32 %or, 0
+  br i1 %tobool.not, label %if.then5, label %if.end6
+
+if.then5:                                         ; preds = %entry
+  %call = tail call i32 (...) @foo32()
+  br label %return
+
+if.end6:                                          ; preds = %entry
+  %call7 = tail call i32 (...) @bar32()
+  br label %return
+
+return:                                           ; preds = %if.end6, %if.then5
+  %retval.0 = phi i32 [ %call7, %if.end6 ], [ %call, %if.then5 ]
+  ret i32 %retval.0
+}
+
+define i32 @or_assume_oddV_evenV_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @or_assume_oddV_evenV_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2_NOT:%.*]] = icmp eq i32 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2_NOT]])
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    ret i32 [[CALL7]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i32 %other, 1
+  %cmp2.not = icmp eq i32 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2.not)
+  %call7 = tail call i32 (...) @bar32()
+  ret i32 %call7
+}
+
+define i32 @or_assume_oddV_oddV_and1_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_and1_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    [[CALL8:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    ret i32 [[CALL8]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i32 %other, 1
+  %cmp2 = icmp ne i32 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  %call8 = tail call i32 (...) @bar32()
+  ret i32 %call8
+}
+
+define i32 @or_assume_oddV_oddV_and2_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_and2_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    [[CALL8:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    ret i32 [[CALL8]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i32 %other, 1
+  %cmp2 = icmp ne i32 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  %call8 = tail call i32 (...) @bar32()
+  ret i32 %call8
+}
+
+define i32 @or_assume_oddV_oddV_and3_u32_brz(i32 %v, i32 %other) {
+; CHECK-LABEL: @or_assume_oddV_oddV_and3_u32_brz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    [[CALL9:%.*]] = tail call i32 (...) @bar32()
+; CHECK-NEXT:    ret i32 [[CALL9]]
+;
+entry:
+  %and = and i32 %v, 1
+  %cmp = icmp ne i32 %and, 0
+  tail call void @llvm.assume(i1 %cmp)
+  %and1 = and i32 %other, 1
+  %cmp2 = icmp ne i32 %and1, 0
+  tail call void @llvm.assume(i1 %cmp2)
+  %call9 = tail call i32 (...) @bar32()
+  ret i32 %call9
+}
+
+define signext i16 @mul_br_V_oddC_s16_brnz(i16 signext %v) {
+; CHECK-LABEL: @mul_br_V_oddC_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i16 [[V:%.*]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL1]], [[IF_END]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %tobool.not = icmp eq i16 %v, 0
+  br i1 %tobool.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %call1 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call1, %if.end ]
+  ret i16 %retval.0
+}
+
+declare signext i16 @foo16(...)
+
+declare signext i16 @bar16(...)
+
+define signext i16 @mul_br_V_evenC_s16_brnz(i16 signext %v) {
+; CHECK-LABEL: @mul_br_V_evenC_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i16 [[V:%.*]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL1]], [[IF_END]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %tobool.not = icmp eq i16 %v, 0
+  br i1 %tobool.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %call1 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call1, %if.end ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_V_2C_s16_brnz(i16 signext %v) {
+; CHECK-LABEL: @mul_br_V_2C_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i16 [[V:%.*]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL1]], [[IF_END]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %tobool.not = icmp eq i16 %v, 0
+  br i1 %tobool.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %call1 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call1, %if.end ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_oddV_oddC_s16_brnz(i16 signext %v) {
+; CHECK-LABEL: @mul_br_oddV_oddC_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_THEN3:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    [[CALL4:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL4]], [[IF_THEN3]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp = icmp eq i16 %0, 0
+  br i1 %cmp, label %if.then, label %if.then3
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.then3:                                         ; preds = %entry
+  %call4 = tail call signext i16 (...) @foo16()
+  br label %return
+
+return:                                           ; preds = %if.then3, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call4, %if.then3 ]
+  ret i16 %retval.0
+}
+
+declare signext i16 @baz16(...)
+
+define signext i16 @mul_br_oddV_evenC_s16_brnz(i16 signext %v) {
+; CHECK-LABEL: @mul_br_oddV_evenC_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_THEN3:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    [[CALL4:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL4]], [[IF_THEN3]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp = icmp eq i16 %0, 0
+  br i1 %cmp, label %if.then, label %if.then3
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.then3:                                         ; preds = %entry
+  %call4 = tail call signext i16 (...) @foo16()
+  br label %return
+
+return:                                           ; preds = %if.then3, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call4, %if.then3 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_evenV_oddC_s16_brnz(i16 signext %v) {
+; CHECK-LABEL: @mul_br_evenV_oddC_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i16 [[V]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END5:%.*]], label [[IF_THEN3:%.*]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    [[CALL4:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end5:
+; CHECK-NEXT:    [[CALL6:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL4]], [[IF_THEN3]] ], [ [[CALL6]], [[IF_END5]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp.not = icmp eq i16 %0, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %tobool.not = icmp eq i16 %v, 0
+  br i1 %tobool.not, label %if.end5, label %if.then3
+
+if.then3:                                         ; preds = %if.end
+  %call4 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end5:                                          ; preds = %if.end
+  %call6 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end5, %if.then3, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call4, %if.then3 ], [ %call6, %if.end5 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_evenV_evenC_s16_brnz(i16 signext %v) {
+; CHECK-LABEL: @mul_br_evenV_evenC_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i16 [[V]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END5:%.*]], label [[IF_THEN3:%.*]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    [[CALL4:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end5:
+; CHECK-NEXT:    [[CALL6:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL4]], [[IF_THEN3]] ], [ [[CALL6]], [[IF_END5]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp.not = icmp eq i16 %0, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %tobool.not = icmp eq i16 %v, 0
+  br i1 %tobool.not, label %if.end5, label %if.then3
+
+if.then3:                                         ; preds = %if.end
+  %call4 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end5:                                          ; preds = %if.end
+  %call6 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end5, %if.then3, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call4, %if.then3 ], [ %call6, %if.end5 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_V_oddV_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @mul_br_V_oddV_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i16 [[V:%.*]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END6:%.*]], label [[IF_THEN4:%.*]]
+; CHECK:       if.then4:
+; CHECK-NEXT:    [[CALL5:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL5]], [[IF_THEN4]] ], [ [[CALL7]], [[IF_END6]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %other to i32
+  %and = and i32 %conv, 1
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %conv2 = sext i16 %v to i32
+  %mul = mul nsw i32 %conv, %conv2
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.end6, label %if.then4
+
+if.then4:                                         ; preds = %if.end
+  %call5 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end6:                                          ; preds = %if.end
+  %call7 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end6, %if.then4, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call5, %if.then4 ], [ %call7, %if.end6 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_V_evenV_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @mul_br_V_evenV_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[OTHER:%.*]] to i32
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CONV]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[V:%.*]] to i32
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[CONV]], [[CONV2]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END6:%.*]], label [[IF_THEN4:%.*]]
+; CHECK:       if.then4:
+; CHECK-NEXT:    [[CALL5:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL5]], [[IF_THEN4]] ], [ [[CALL7]], [[IF_END6]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %other to i32
+  %and = and i32 %conv, 1
+  %cmp.not = icmp eq i32 %and, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %conv2 = sext i16 %v to i32
+  %mul = mul nsw i32 %conv, %conv2
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.end6, label %if.then4
+
+if.then4:                                         ; preds = %if.end
+  %call5 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end6:                                          ; preds = %if.end
+  %call7 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end6, %if.then4, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call5, %if.then4 ], [ %call7, %if.end6 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_oddV_oddV_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @mul_br_oddV_oddV_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[CMP4]], label [[IF_THEN6:%.*]], label [[IF_END8:%.*]]
+; CHECK:       if.then6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end8:
+; CHECK-NEXT:    br i1 false, label [[IF_END13:%.*]], label [[IF_THEN11:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    [[CALL12:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end13:
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL7]], [[IF_THEN6]] ], [ [[CALL12]], [[IF_THEN11]] ], [ poison, [[IF_END13]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %v to i32
+  %and = and i32 %conv, 1
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %conv2 = sext i16 %other to i32
+  %and3 = and i32 %conv2, 1
+  %cmp4 = icmp eq i32 %and3, 0
+  br i1 %cmp4, label %if.then6, label %if.end8
+
+if.then6:                                         ; preds = %if.end
+  %call7 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end8:                                          ; preds = %if.end
+  %mul = mul nsw i32 %conv2, %conv
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.end13, label %if.then11
+
+if.then11:                                        ; preds = %if.end8
+  %call12 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end13:                                         ; preds = %if.end8
+  %call14 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end13, %if.then11, %if.then6, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call7, %if.then6 ], [ %call12, %if.then11 ], [ %call14, %if.end13 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_oddV_evenV_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @mul_br_oddV_evenV_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP4_NOT:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[CMP4_NOT]], label [[IF_END8:%.*]], label [[IF_THEN6:%.*]]
+; CHECK:       if.then6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end8:
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i16 [[OTHER]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END13:%.*]], label [[IF_THEN11:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    [[CALL12:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end13:
+; CHECK-NEXT:    [[CALL14:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL7]], [[IF_THEN6]] ], [ [[CALL12]], [[IF_THEN11]] ], [ [[CALL14]], [[IF_END13]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %v to i32
+  %and = and i32 %conv, 1
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %conv2 = sext i16 %other to i32
+  %and3 = and i32 %conv2, 1
+  %cmp4.not = icmp eq i32 %and3, 0
+  br i1 %cmp4.not, label %if.end8, label %if.then6
+
+if.then6:                                         ; preds = %if.end
+  %call7 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end8:                                          ; preds = %if.end
+  %mul = mul nsw i32 %conv2, %conv
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.end13, label %if.then11
+
+if.then11:                                        ; preds = %if.end8
+  %call12 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end13:                                         ; preds = %if.end8
+  %call14 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end13, %if.then11, %if.then6, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call7, %if.then6 ], [ %call12, %if.then11 ], [ %call14, %if.end13 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_no_of_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @mul_br_no_of_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[V:%.*]] to i32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i16 [[V]], 7
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp sgt i16 [[OTHER:%.*]], 7
+; CHECK-NEXT:    br i1 [[CMP3]], label [[IF_THEN5:%.*]], label [[IF_END7:%.*]]
+; CHECK:       if.then5:
+; CHECK-NEXT:    [[CALL6:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end7:
+; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[OTHER]] to i32
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[CONV2]], [[CONV]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END12:%.*]], label [[IF_THEN10:%.*]]
+; CHECK:       if.then10:
+; CHECK-NEXT:    [[CALL11:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end12:
+; CHECK-NEXT:    [[CALL13:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL6]], [[IF_THEN5]] ], [ [[CALL11]], [[IF_THEN10]] ], [ [[CALL13]], [[IF_END12]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %v to i32
+  %cmp = icmp sgt i16 %v, 7
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %cmp3 = icmp sgt i16 %other, 7
+  br i1 %cmp3, label %if.then5, label %if.end7
+
+if.then5:                                         ; preds = %if.end
+  %call6 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end7:                                          ; preds = %if.end
+  %conv2 = sext i16 %other to i32
+  %mul = mul nsw i32 %conv2, %conv
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.end12, label %if.then10
+
+if.then10:                                        ; preds = %if.end7
+  %call11 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end12:                                         ; preds = %if.end7
+  %call13 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end12, %if.then10, %if.then5, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call6, %if.then5 ], [ %call11, %if.then10 ], [ %call13, %if.end12 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_no_of_nz1_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @mul_br_no_of_nz1_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[V:%.*]] to i32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i16 [[V]], 7
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp eq i16 [[V]], 0
+; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP3]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CMP6:%.*]] = icmp sgt i16 [[OTHER:%.*]], 7
+; CHECK-NEXT:    br i1 [[CMP6]], label [[IF_THEN8:%.*]], label [[IF_END10:%.*]]
+; CHECK:       if.then8:
+; CHECK-NEXT:    [[CALL9:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end10:
+; CHECK-NEXT:    [[CONV5:%.*]] = sext i16 [[OTHER]] to i32
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[CONV5]], [[CONV]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END15:%.*]], label [[IF_THEN13:%.*]]
+; CHECK:       if.then13:
+; CHECK-NEXT:    [[CALL14:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end15:
+; CHECK-NEXT:    [[CALL16:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL9]], [[IF_THEN8]] ], [ [[CALL14]], [[IF_THEN13]] ], [ [[CALL16]], [[IF_END15]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %v to i32
+  %cmp = icmp sgt i16 %v, 7
+  %cmp3 = icmp eq i16 %v, 0
+  %or.cond = or i1 %cmp, %cmp3
+  br i1 %or.cond, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %cmp6 = icmp sgt i16 %other, 7
+  br i1 %cmp6, label %if.then8, label %if.end10
+
+if.then8:                                         ; preds = %if.end
+  %call9 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end10:                                         ; preds = %if.end
+  %conv5 = sext i16 %other to i32
+  %mul = mul nsw i32 %conv5, %conv
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.end15, label %if.then13
+
+if.then13:                                        ; preds = %if.end10
+  %call14 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end15:                                         ; preds = %if.end10
+  %call16 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end15, %if.then13, %if.then8, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call9, %if.then8 ], [ %call14, %if.then13 ], [ %call16, %if.end15 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_no_of_nz2_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @mul_br_no_of_nz2_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[V:%.*]] to i32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i16 [[V]], 7
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp eq i16 [[V]], 0
+; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP3]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CMP6:%.*]] = icmp sgt i16 [[OTHER:%.*]], 7
+; CHECK-NEXT:    [[CMP10:%.*]] = icmp eq i16 [[OTHER]], 0
+; CHECK-NEXT:    [[OR_COND21:%.*]] = or i1 [[CMP6]], [[CMP10]]
+; CHECK-NEXT:    br i1 [[OR_COND21]], label [[IF_THEN12:%.*]], label [[IF_END14:%.*]]
+; CHECK:       if.then12:
+; CHECK-NEXT:    [[CALL13:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end14:
+; CHECK-NEXT:    [[CONV5:%.*]] = sext i16 [[OTHER]] to i32
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[CONV5]], [[CONV]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END19:%.*]], label [[IF_THEN17:%.*]]
+; CHECK:       if.then17:
+; CHECK-NEXT:    [[CALL18:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end19:
+; CHECK-NEXT:    [[CALL20:%.*]] = tail call signext i16 (...) @bar16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL13]], [[IF_THEN12]] ], [ [[CALL18]], [[IF_THEN17]] ], [ [[CALL20]], [[IF_END19]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %v to i32
+  %cmp = icmp sgt i16 %v, 7
+  %cmp3 = icmp eq i16 %v, 0
+  %or.cond = or i1 %cmp, %cmp3
+  br i1 %or.cond, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %cmp6 = icmp sgt i16 %other, 7
+  %cmp10 = icmp eq i16 %other, 0
+  %or.cond21 = or i1 %cmp6, %cmp10
+  br i1 %or.cond21, label %if.then12, label %if.end14
+
+if.then12:                                        ; preds = %if.end
+  %call13 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end14:                                         ; preds = %if.end
+  %conv5 = sext i16 %other to i32
+  %mul = mul nsw i32 %conv5, %conv
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.end19, label %if.then17
+
+if.then17:                                        ; preds = %if.end14
+  %call18 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end19:                                         ; preds = %if.end14
+  %call20 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end19, %if.then17, %if.then12, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call13, %if.then12 ], [ %call18, %if.then17 ], [ %call20, %if.end19 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_no_of_nz3_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @mul_br_no_of_nz3_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i16 [[V:%.*]], -8
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i16 [[TMP0]], -6
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CMP6:%.*]] = icmp sgt i16 [[OTHER:%.*]], 7
+; CHECK-NEXT:    [[CMP10:%.*]] = icmp eq i16 [[OTHER]], 0
+; CHECK-NEXT:    [[OR_COND21:%.*]] = or i1 [[CMP6]], [[CMP10]]
+; CHECK-NEXT:    br i1 [[OR_COND21]], label [[IF_THEN12:%.*]], label [[IF_END14:%.*]]
+; CHECK:       if.then12:
+; CHECK-NEXT:    [[CALL13:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end14:
+; CHECK-NEXT:    br i1 false, label [[IF_END19:%.*]], label [[IF_THEN17:%.*]]
+; CHECK:       if.then17:
+; CHECK-NEXT:    [[CALL18:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end19:
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL13]], [[IF_THEN12]] ], [ [[CALL18]], [[IF_THEN17]] ], [ poison, [[IF_END19]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %v to i32
+  %0 = add i16 %v, -8
+  %or.cond = icmp ult i16 %0, -6
+  br i1 %or.cond, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %cmp6 = icmp sgt i16 %other, 7
+  %cmp10 = icmp eq i16 %other, 0
+  %or.cond21 = or i1 %cmp6, %cmp10
+  br i1 %or.cond21, label %if.then12, label %if.end14
+
+if.then12:                                        ; preds = %if.end
+  %call13 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end14:                                         ; preds = %if.end
+  %conv5 = sext i16 %other to i32
+  %mul = mul nsw i32 %conv5, %conv
+  %tobool.not = icmp eq i32 %mul, 0
+  br i1 %tobool.not, label %if.end19, label %if.then17
+
+if.then17:                                        ; preds = %if.end14
+  %call18 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end19:                                         ; preds = %if.end14
+  %call20 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end19, %if.then17, %if.then12, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call13, %if.then12 ], [ %call18, %if.then17 ], [ %call20, %if.end19 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_no_of_nz4_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @mul_br_no_of_nz4_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i16 [[V:%.*]], -8
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i16 [[TMP0]], -6
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[OTHER:%.*]], -8
+; CHECK-NEXT:    [[OR_COND21:%.*]] = icmp ult i16 [[TMP1]], -5
+; CHECK-NEXT:    br i1 [[OR_COND21]], label [[IF_THEN12:%.*]], label [[IF_THEN17:%.*]]
+; CHECK:       if.then12:
+; CHECK-NEXT:    [[CALL13:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.then17:
+; CHECK-NEXT:    [[CALL18:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL13]], [[IF_THEN12]] ], [ [[CALL18]], [[IF_THEN17]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = add i16 %v, -8
+  %or.cond = icmp ult i16 %0, -6
+  br i1 %or.cond, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %1 = add i16 %other, -8
+  %or.cond21 = icmp ult i16 %1, -5
+  br i1 %or.cond21, label %if.then12, label %if.then17
+
+if.then12:                                        ; preds = %if.end
+  %call13 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.then17:                                        ; preds = %if.end
+  %call18 = tail call signext i16 (...) @foo16()
+  br label %return
+
+return:                                           ; preds = %if.then17, %if.then12, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call13, %if.then12 ], [ %call18, %if.then17 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @mul_br_may_of_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @mul_br_may_of_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i16 [[V:%.*]], -16381
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i16 [[TMP0]], -16379
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[OTHER:%.*]], -8191
+; CHECK-NEXT:    [[OR_COND21:%.*]] = icmp ult i16 [[TMP1]], -8188
+; CHECK-NEXT:    br i1 [[OR_COND21]], label [[IF_THEN12:%.*]], label [[IF_THEN17:%.*]]
+; CHECK:       if.then12:
+; CHECK-NEXT:    [[CALL13:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.then17:
+; CHECK-NEXT:    [[CALL18:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL13]], [[IF_THEN12]] ], [ [[CALL18]], [[IF_THEN17]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = add i16 %v, -16381
+  %or.cond = icmp ult i16 %0, -16379
+  br i1 %or.cond, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %1 = add i16 %other, -8191
+  %or.cond21 = icmp ult i16 %1, -8188
+  br i1 %or.cond21, label %if.then12, label %if.then17
+
+if.then12:                                        ; preds = %if.end
+  %call13 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.then17:                                        ; preds = %if.end
+  %call18 = tail call signext i16 (...) @foo16()
+  br label %return
+
+return:                                           ; preds = %if.then17, %if.then12, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call13, %if.then12 ], [ %call18, %if.then17 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @return_or_1_not_needed_s16(i16 signext %v) {
+; CHECK-LABEL: @return_or_1_not_needed_s16(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[OR:%.*]] = or i16 [[V]], 1
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[OR]], [[IF_END]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp = icmp eq i16 %0, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %or = or i16 %v, 1
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %or, %if.end ]
+  ret i16 %retval.0
+}
+
+define signext i16 @return_or_1_needed_s16(i16 signext %v) {
+; CHECK-LABEL: @return_or_1_needed_s16(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[OR:%.*]] = or i16 [[V]], 1
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[OR]], [[IF_END]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp.not = icmp eq i16 %0, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %or = or i16 %v, 1
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %or, %if.end ]
+  ret i16 %retval.0
+}
+
+define signext i16 @return_and_n2_not_needed_s16(i16 signext %v) {
+; CHECK-LABEL: @return_and_n2_not_needed_s16(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[AND3:%.*]] = and i16 [[V]], -2
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[AND3]], [[IF_END]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp.not = icmp eq i16 %0, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %and3 = and i16 %v, -2
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %and3, %if.end ]
+  ret i16 %retval.0
+}
+
+define signext i16 @return_and_n2_needed_s16(i16 signext %v) {
+; CHECK-LABEL: @return_and_n2_needed_s16(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT_NOT:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT_NOT]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[AND3:%.*]] = and i16 [[V]], -2
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[AND3]], [[IF_END]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp.not.not = icmp eq i16 %0, 0
+  br i1 %cmp.not.not, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %and3 = and i16 %v, -2
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %and3, %if.end ]
+  ret i16 %retval.0
+}
+
+define signext i16 @return_and_n2_not_needed_mod_s16(i16 signext %v) {
+; CHECK-LABEL: @return_and_n2_not_needed_mod_s16(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[V:%.*]] to i32
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[CONV]], -2147483647
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP0]], 1
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[AND:%.*]] = and i16 [[V]], -2
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[AND]], [[IF_END]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %v to i32
+  %0 = and i32 %conv, -2147483647
+  %cmp = icmp eq i32 %0, 1
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %and = and i16 %v, -2
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %and, %if.end ]
+  ret i16 %retval.0
+}
+
+define signext i16 @return_and_n2_needed_mod_s16(i16 signext %v) {
+; CHECK-LABEL: @return_and_n2_needed_mod_s16(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[V:%.*]] to i32
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[CONV]], -2147483647
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[TMP0]], 1
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[AND:%.*]] = and i16 [[V]], -2
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[AND]], [[IF_END]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %v to i32
+  %0 = and i32 %conv, -2147483647
+  %cmp.not = icmp eq i32 %0, 1
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %and = and i16 %v, -2
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %and, %if.end ]
+  ret i16 %retval.0
+}
+
+define signext i16 @or_br_V_oddV_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @or_br_V_oddV_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CALL5:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL5]], [[IF_END]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %other, 1
+  %cmp = icmp eq i16 %0, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %call5 = tail call signext i16 (...) @foo16()
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call5, %if.end ]
+  ret i16 %retval.0
+}
+
+define signext i16 @or_br_V_evenV_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @or_br_V_evenV_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[OTHER:%.*]], 3
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i16 [[TMP0]], 2
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_THEN3:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    [[CALL4:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL4]], [[IF_THEN3]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %other, 3
+  %cmp.not = icmp eq i16 %0, 2
+  br i1 %cmp.not, label %if.then3, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.then3:                                         ; preds = %entry
+  %call4 = tail call signext i16 (...) @foo16()
+  br label %return
+
+return:                                           ; preds = %if.then3, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call4, %if.then3 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @or_br_oddV_oddV_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @or_br_oddV_oddV_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[CMP4]], label [[IF_THEN6:%.*]], label [[IF_END8:%.*]]
+; CHECK:       if.then6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end8:
+; CHECK-NEXT:    br i1 false, label [[IF_END13:%.*]], label [[IF_THEN11:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    [[CALL12:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end13:
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL7]], [[IF_THEN6]] ], [ [[CALL12]], [[IF_THEN11]] ], [ poison, [[IF_END13]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %conv = sext i16 %v to i32
+  %and = and i32 %conv, 1
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %conv2 = sext i16 %other to i32
+  %and3 = and i32 %conv2, 1
+  %cmp4 = icmp eq i32 %and3, 0
+  br i1 %cmp4, label %if.then6, label %if.end8
+
+if.then6:                                         ; preds = %if.end
+  %call7 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end8:                                          ; preds = %if.end
+  %or = or i32 %conv2, %conv
+  %tobool.not = icmp eq i32 %or, 0
+  br i1 %tobool.not, label %if.end13, label %if.then11
+
+if.then11:                                        ; preds = %if.end8
+  %call12 = tail call signext i16 (...) @foo16()
+  br label %return
+
+if.end13:                                         ; preds = %if.end8
+  %call14 = tail call signext i16 (...) @bar16()
+  br label %return
+
+return:                                           ; preds = %if.end13, %if.then11, %if.then6, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call7, %if.then6 ], [ %call12, %if.then11 ], [ %call14, %if.end13 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @or_br_oddV_evenV_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @or_br_oddV_evenV_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP4_NOT:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[CMP4_NOT]], label [[IF_THEN10:%.*]], label [[IF_THEN6:%.*]]
+; CHECK:       if.then6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.then10:
+; CHECK-NEXT:    [[CALL11:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL7]], [[IF_THEN6]] ], [ [[CALL11]], [[IF_THEN10]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp = icmp eq i16 %0, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %1 = and i16 %other, 1
+  %cmp4.not = icmp eq i16 %1, 0
+  br i1 %cmp4.not, label %if.then10, label %if.then6
+
+if.then6:                                         ; preds = %if.end
+  %call7 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.then10:                                        ; preds = %if.end
+  %call11 = tail call signext i16 (...) @foo16()
+  br label %return
+
+return:                                           ; preds = %if.then10, %if.then6, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call7, %if.then6 ], [ %call11, %if.then10 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @or_br_oddV_oddV_and1_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @or_br_oddV_oddV_and1_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[CMP4]], label [[IF_THEN6:%.*]], label [[IF_THEN14:%.*]]
+; CHECK:       if.then6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.then14:
+; CHECK-NEXT:    [[CALL15:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL7]], [[IF_THEN6]] ], [ [[CALL15]], [[IF_THEN14]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp = icmp eq i16 %0, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %1 = and i16 %other, 1
+  %cmp4 = icmp eq i16 %1, 0
+  br i1 %cmp4, label %if.then6, label %if.then14
+
+if.then6:                                         ; preds = %if.end
+  %call7 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.then14:                                        ; preds = %if.end
+  %call15 = tail call signext i16 (...) @foo16()
+  br label %return
+
+return:                                           ; preds = %if.then14, %if.then6, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call7, %if.then6 ], [ %call15, %if.then14 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @or_br_oddV_oddV_and2_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @or_br_oddV_oddV_and2_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[CMP4]], label [[IF_THEN6:%.*]], label [[IF_THEN14:%.*]]
+; CHECK:       if.then6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.then14:
+; CHECK-NEXT:    [[CALL15:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL7]], [[IF_THEN6]] ], [ [[CALL15]], [[IF_THEN14]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp = icmp eq i16 %0, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %1 = and i16 %other, 1
+  %cmp4 = icmp eq i16 %1, 0
+  br i1 %cmp4, label %if.then6, label %if.then14
+
+if.then6:                                         ; preds = %if.end
+  %call7 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.then14:                                        ; preds = %if.end
+  %call15 = tail call signext i16 (...) @foo16()
+  br label %return
+
+return:                                           ; preds = %if.then14, %if.then6, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call7, %if.then6 ], [ %call15, %if.then14 ]
+  ret i16 %retval.0
+}
+
+define signext i16 @or_br_oddV_oddV_and3_s16_brnz(i16 signext %v, i16 signext %other) {
+; CHECK-LABEL: @or_br_oddV_oddV_and3_s16_brnz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i16 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i16 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[CMP4]], label [[IF_THEN6:%.*]], label [[IF_THEN17:%.*]]
+; CHECK:       if.then6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call signext i16 (...) @baz16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.then17:
+; CHECK-NEXT:    [[CALL18:%.*]] = tail call signext i16 (...) @foo16()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i16 [ [[CALL]], [[IF_THEN]] ], [ [[CALL7]], [[IF_THEN6]] ], [ [[CALL18]], [[IF_THEN17]] ]
+; CHECK-NEXT:    ret i16 [[RETVAL_0]]
+;
+entry:
+  %0 = and i16 %v, 1
+  %cmp = icmp eq i16 %0, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %1 = and i16 %other, 1
+  %cmp4 = icmp eq i16 %1, 0
+  br i1 %cmp4, label %if.then6, label %if.then17
+
+if.then6:                                         ; preds = %if.end
+  %call7 = tail call signext i16 (...) @baz16()
+  br label %return
+
+if.then17:                                        ; preds = %if.end
+  %call18 = tail call signext i16 (...) @foo16()
+  br label %return
+
+return:                                           ; preds = %if.then17, %if.then6, %if.then
+  %retval.0 = phi i16 [ %call, %if.then ], [ %call7, %if.then6 ], [ %call18, %if.then17 ]
+  ret i16 %retval.0
+}
+
+define zeroext i8 @mul_br_V_oddC_u8_setz(i8 zeroext %v) {
+; CHECK-LABEL: @mul_br_V_oddC_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[V:%.*]], 0
+; CHECK-NEXT:    [[CONV2:%.*]] = zext i1 [[TOBOOL]] to i8
+; CHECK-NEXT:    ret i8 [[CONV2]]
+;
+entry:
+  %tobool = icmp ne i8 %v, 0
+  %conv2 = zext i1 %tobool to i8
+  ret i8 %conv2
+}
+
+define zeroext i8 @mul_br_V_evenC_u8_setz(i8 zeroext %v) {
+; CHECK-LABEL: @mul_br_V_evenC_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[V:%.*]], 0
+; CHECK-NEXT:    [[CONV2:%.*]] = zext i1 [[TOBOOL]] to i8
+; CHECK-NEXT:    ret i8 [[CONV2]]
+;
+entry:
+  %tobool = icmp ne i8 %v, 0
+  %conv2 = zext i1 %tobool to i8
+  ret i8 %conv2
+}
+
+define zeroext i8 @mul_br_V_2C_u8_setz(i8 zeroext %v) {
+; CHECK-LABEL: @mul_br_V_2C_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[V:%.*]], 0
+; CHECK-NEXT:    [[CONV2:%.*]] = zext i1 [[TOBOOL]] to i8
+; CHECK-NEXT:    ret i8 [[CONV2]]
+;
+entry:
+  %tobool = icmp ne i8 %v, 0
+  %conv2 = zext i1 %tobool to i8
+  ret i8 %conv2
+}
+
+define zeroext i8 @mul_br_oddV_oddC_u8_setz(i8 zeroext %v) {
+; CHECK-LABEL: @mul_br_oddV_oddC_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[RETURN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp = icmp eq i8 %0, 0
+  br i1 %cmp, label %if.then, label %return
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+declare zeroext i8 @baz8(...)
+
+define zeroext i8 @mul_br_oddV_evenC_u8_setz(i8 zeroext %v) {
+; CHECK-LABEL: @mul_br_oddV_evenC_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[RETURN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp = icmp eq i8 %0, 0
+  br i1 %cmp, label %if.then, label %return
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_evenV_oddC_u8_setz(i8 zeroext %v) {
+; CHECK-LABEL: @mul_br_evenV_oddC_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[V]], 0
+; CHECK-NEXT:    [[CONV4:%.*]] = zext i1 [[TOBOOL]] to i8
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[CONV4]], [[IF_END]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp.not = icmp eq i8 %0, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %tobool = icmp ne i8 %v, 0
+  %conv4 = zext i1 %tobool to i8
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %conv4, %if.end ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_evenV_evenC_u8_setz(i8 zeroext %v) {
+; CHECK-LABEL: @mul_br_evenV_evenC_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[V]], 0
+; CHECK-NEXT:    [[CONV4:%.*]] = zext i1 [[TOBOOL]] to i8
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[CONV4]], [[IF_END]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp.not = icmp eq i8 %0, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %tobool = icmp ne i8 %v, 0
+  %conv4 = zext i1 %tobool to i8
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %conv4, %if.end ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_V_oddV_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_V_oddV_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[V:%.*]], 0
+; CHECK-NEXT:    [[CONV5:%.*]] = zext i1 [[TOBOOL]] to i8
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[CONV5]], [[IF_END]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %conv = zext i8 %other to i32
+  %and = and i32 %conv, 1
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %conv2 = zext i8 %v to i32
+  %mul = mul nuw nsw i32 %conv, %conv2
+  %tobool = icmp ne i32 %mul, 0
+  %conv5 = zext i1 %tobool to i8
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %conv5, %if.end ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_V_evenV_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_V_evenV_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CONV:%.*]] = zext i8 [[OTHER:%.*]] to i32
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CONV]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CONV2:%.*]] = zext i8 [[V:%.*]] to i32
+; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i32 [[CONV]], [[CONV2]]
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[MUL]], 0
+; CHECK-NEXT:    [[CONV5:%.*]] = zext i1 [[TOBOOL]] to i8
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[CONV5]], [[IF_END]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %conv = zext i8 %other to i32
+  %and = and i32 %conv, 1
+  %cmp.not = icmp eq i32 %and, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %conv2 = zext i8 %v to i32
+  %mul = mul nuw nsw i32 %conv, %conv2
+  %tobool = icmp ne i32 %mul, 0
+  %conv5 = zext i1 %tobool to i8
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %conv5, %if.end ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_oddV_oddV_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_oddV_oddV_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], [[OTHER:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP0]], 1
+; CHECK-NEXT:    [[OR_COND_NOT_NOT:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[OR_COND_NOT_NOT]], label [[RETURN_SINK_SPLIT:%.*]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL7]], [[RETURN_SINK_SPLIT]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, %other
+  %1 = and i8 %0, 1
+  %or.cond.not.not = icmp eq i8 %1, 0
+  br i1 %or.cond.not.not, label %return.sink.split, label %return
+
+return.sink.split:                                ; preds = %entry
+  %call7 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %return.sink.split
+  %retval.0 = phi i8 [ %call7, %return.sink.split ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_oddV_evenV_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_oddV_evenV_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP4_NOT:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[CMP4_NOT]], label [[IF_END8:%.*]], label [[IF_THEN6:%.*]]
+; CHECK:       if.then6:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end8:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[OTHER]], 0
+; CHECK-NEXT:    [[CONV12:%.*]] = zext i1 [[TOBOOL]] to i8
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[CALL7]], [[IF_THEN6]] ], [ [[CONV12]], [[IF_END8]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %conv = zext i8 %v to i32
+  %and = and i32 %conv, 1
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %conv2 = zext i8 %other to i32
+  %and3 = and i32 %conv2, 1
+  %cmp4.not = icmp eq i32 %and3, 0
+  br i1 %cmp4.not, label %if.end8, label %if.then6
+
+if.then6:                                         ; preds = %if.end
+  %call7 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end8:                                          ; preds = %if.end
+  %mul = mul nuw nsw i32 %conv2, %conv
+  %tobool = icmp ne i32 %mul, 0
+  %conv12 = zext i1 %tobool to i8
+  br label %return
+
+return:                                           ; preds = %if.end8, %if.then6, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %call7, %if.then6 ], [ %conv12, %if.end8 ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_no_of_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_no_of_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CONV:%.*]] = zext i8 [[V:%.*]] to i32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[V]], 7
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp ugt i8 [[OTHER:%.*]], 7
+; CHECK-NEXT:    br i1 [[CMP3]], label [[IF_THEN5:%.*]], label [[IF_END7:%.*]]
+; CHECK:       if.then5:
+; CHECK-NEXT:    [[CALL6:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end7:
+; CHECK-NEXT:    [[CONV2:%.*]] = zext i8 [[OTHER]] to i32
+; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i32 [[CONV2]], [[CONV]]
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[MUL]], 0
+; CHECK-NEXT:    [[CONV11:%.*]] = zext i1 [[TOBOOL]] to i8
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[CALL6]], [[IF_THEN5]] ], [ [[CONV11]], [[IF_END7]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %conv = zext i8 %v to i32
+  %cmp = icmp ugt i8 %v, 7
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %cmp3 = icmp ugt i8 %other, 7
+  br i1 %cmp3, label %if.then5, label %if.end7
+
+if.then5:                                         ; preds = %if.end
+  %call6 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end7:                                          ; preds = %if.end
+  %conv2 = zext i8 %other to i32
+  %mul = mul nuw nsw i32 %conv2, %conv
+  %tobool = icmp ne i32 %mul, 0
+  %conv11 = zext i1 %tobool to i8
+  br label %return
+
+return:                                           ; preds = %if.end7, %if.then5, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %call6, %if.then5 ], [ %conv11, %if.end7 ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_no_of_nz1_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_no_of_nz1_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i8 [[V:%.*]], -8
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i8 [[TMP0]], -7
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CMP6:%.*]] = icmp ugt i8 [[OTHER:%.*]], 7
+; CHECK-NEXT:    br i1 [[CMP6]], label [[IF_THEN8:%.*]], label [[IF_END10:%.*]]
+; CHECK:       if.then8:
+; CHECK-NEXT:    [[CALL9:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       if.end10:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[OTHER]], 0
+; CHECK-NEXT:    [[CONV14:%.*]] = zext i1 [[TOBOOL]] to i8
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[CALL9]], [[IF_THEN8]] ], [ [[CONV14]], [[IF_END10]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %conv = zext i8 %v to i32
+  %0 = add i8 %v, -8
+  %or.cond = icmp ult i8 %0, -7
+  br i1 %or.cond, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %cmp6 = icmp ugt i8 %other, 7
+  br i1 %cmp6, label %if.then8, label %if.end10
+
+if.then8:                                         ; preds = %if.end
+  %call9 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end10:                                         ; preds = %if.end
+  %conv5 = zext i8 %other to i32
+  %mul = mul nuw nsw i32 %conv5, %conv
+  %tobool = icmp ne i32 %mul, 0
+  %conv14 = zext i1 %tobool to i8
+  br label %return
+
+return:                                           ; preds = %if.end10, %if.then8, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %call9, %if.then8 ], [ %conv14, %if.end10 ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_no_of_nz2_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_no_of_nz2_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i8 [[V:%.*]], -8
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i8 [[TMP0]], -7
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[OTHER:%.*]], -8
+; CHECK-NEXT:    [[OR_COND19:%.*]] = icmp ult i8 [[TMP1]], -7
+; CHECK-NEXT:    [[OR_COND24:%.*]] = or i1 [[OR_COND]], [[OR_COND19]]
+; CHECK-NEXT:    br i1 [[OR_COND24]], label [[RETURN_SINK_SPLIT:%.*]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[CALL13:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL13]], [[RETURN_SINK_SPLIT]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = add i8 %v, -8
+  %or.cond = icmp ult i8 %0, -7
+  %1 = add i8 %other, -8
+  %or.cond19 = icmp ult i8 %1, -7
+  %or.cond24 = or i1 %or.cond, %or.cond19
+  br i1 %or.cond24, label %return.sink.split, label %return
+
+return.sink.split:                                ; preds = %entry
+  %call13 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %return.sink.split
+  %retval.0 = phi i8 [ %call13, %return.sink.split ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_no_of_nz3_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_no_of_nz3_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i8 [[V:%.*]], -8
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i8 [[TMP0]], -6
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[OTHER:%.*]], -8
+; CHECK-NEXT:    [[OR_COND19:%.*]] = icmp ult i8 [[TMP1]], -7
+; CHECK-NEXT:    [[OR_COND24:%.*]] = or i1 [[OR_COND]], [[OR_COND19]]
+; CHECK-NEXT:    br i1 [[OR_COND24]], label [[RETURN_SINK_SPLIT:%.*]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[CALL13:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL13]], [[RETURN_SINK_SPLIT]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = add i8 %v, -8
+  %or.cond = icmp ult i8 %0, -6
+  %1 = add i8 %other, -8
+  %or.cond19 = icmp ult i8 %1, -7
+  %or.cond24 = or i1 %or.cond, %or.cond19
+  br i1 %or.cond24, label %return.sink.split, label %return
+
+return.sink.split:                                ; preds = %entry
+  %call13 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %return.sink.split
+  %retval.0 = phi i8 [ %call13, %return.sink.split ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_no_of_nz4_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_no_of_nz4_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i8 [[V:%.*]], -8
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i8 [[TMP0]], -6
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[OTHER:%.*]], -8
+; CHECK-NEXT:    [[OR_COND19:%.*]] = icmp ult i8 [[TMP1]], -5
+; CHECK-NEXT:    [[OR_COND24:%.*]] = or i1 [[OR_COND]], [[OR_COND19]]
+; CHECK-NEXT:    br i1 [[OR_COND24]], label [[RETURN_SINK_SPLIT:%.*]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[CALL13:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL13]], [[RETURN_SINK_SPLIT]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = add i8 %v, -8
+  %or.cond = icmp ult i8 %0, -6
+  %1 = add i8 %other, -8
+  %or.cond19 = icmp ult i8 %1, -5
+  %or.cond24 = or i1 %or.cond, %or.cond19
+  br i1 %or.cond24, label %return.sink.split, label %return
+
+return.sink.split:                                ; preds = %entry
+  %call13 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %return.sink.split
+  %retval.0 = phi i8 [ %call13, %return.sink.split ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_may_of_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_may_of_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i8 [[V:%.*]], -61
+; CHECK-NEXT:    [[OR_COND:%.*]] = icmp ult i8 [[TMP0]], -59
+; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[OTHER:%.*]], -31
+; CHECK-NEXT:    [[OR_COND19:%.*]] = icmp ult i8 [[TMP1]], -28
+; CHECK-NEXT:    [[OR_COND24:%.*]] = or i1 [[OR_COND]], [[OR_COND19]]
+; CHECK-NEXT:    br i1 [[OR_COND24]], label [[RETURN_SINK_SPLIT:%.*]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[CALL13:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL13]], [[RETURN_SINK_SPLIT]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = add i8 %v, -61
+  %or.cond = icmp ult i8 %0, -59
+  %1 = add i8 %other, -31
+  %or.cond19 = icmp ult i8 %1, -28
+  %or.cond24 = or i1 %or.cond, %or.cond19
+  br i1 %or.cond24, label %return.sink.split, label %return
+
+return.sink.split:                                ; preds = %entry
+  %call13 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %return.sink.split
+  %retval.0 = phi i8 [ %call13, %return.sink.split ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @mul_br_bad_bounds_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @mul_br_bad_bounds_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    ret i8 [[CALL]]
+;
+entry:
+  %call = tail call zeroext i8 (...) @baz8()
+  ret i8 %call
+}
+
+define zeroext i8 @return_or_1_not_needed_u8(i8 zeroext %v) {
+; CHECK-LABEL: @return_or_1_not_needed_u8(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[OR:%.*]] = or i8 [[V]], 1
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[OR]], [[IF_END]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp = icmp eq i8 %0, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %or = or i8 %v, 1
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %or, %if.end ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @return_or_1_needed_u8(i8 zeroext %v) {
+; CHECK-LABEL: @return_or_1_needed_u8(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[OR:%.*]] = or i8 [[V]], 1
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[OR]], [[IF_END]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp.not = icmp eq i8 %0, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %or = or i8 %v, 1
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %or, %if.end ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @return_and_n2_not_needed_u8(i8 zeroext %v) {
+; CHECK-LABEL: @return_and_n2_not_needed_u8(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[AND3:%.*]] = and i8 [[V]], -2
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[AND3]], [[IF_END]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp.not = icmp eq i8 %0, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %and3 = and i8 %v, -2
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %and3, %if.end ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @return_and_n2_needed_u8(i8 zeroext %v) {
+; CHECK-LABEL: @return_and_n2_needed_u8(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT_NOT]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[AND3:%.*]] = and i8 [[V]], -2
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[AND3]], [[IF_END]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp.not.not = icmp eq i8 %0, 0
+  br i1 %cmp.not.not, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %and3 = and i8 %v, -2
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %and3, %if.end ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @return_and_n2_not_needed_mod_u8(i8 zeroext %v) {
+; CHECK-LABEL: @return_and_n2_not_needed_mod_u8(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[V]], -2
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[AND]], [[IF_END]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp.not = icmp eq i8 %0, 0
+  br i1 %cmp.not, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %and = and i8 %v, -2
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %and, %if.end ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @return_and_n2_needed_mod_u8(i8 zeroext %v) {
+; CHECK-LABEL: @return_and_n2_needed_mod_u8(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP_NOT_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT_NOT]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[V]], -2
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ [[AND]], [[IF_END]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp.not.not = icmp eq i8 %0, 0
+  br i1 %cmp.not.not, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+if.end:                                           ; preds = %entry
+  %and = and i8 %v, -2
+  br label %return
+
+return:                                           ; preds = %if.end, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ %and, %if.end ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @or_br_V_oddV_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @or_br_V_oddV_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[RETURN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %other, 1
+  %cmp = icmp eq i8 %0, 0
+  br i1 %cmp, label %if.then, label %return
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @or_br_V_evenV_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @or_br_V_evenV_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[OTHER:%.*]], 3
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 2
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[RETURN:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL]], [[IF_THEN]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %other, 3
+  %cmp.not = icmp eq i8 %0, 2
+  br i1 %cmp.not, label %return, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %if.then
+  %retval.0 = phi i8 [ %call, %if.then ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @or_br_oddV_oddV_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @or_br_oddV_oddV_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], [[OTHER:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP0]], 1
+; CHECK-NEXT:    [[OR_COND_NOT_NOT:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[OR_COND_NOT_NOT]], label [[RETURN_SINK_SPLIT:%.*]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL7]], [[RETURN_SINK_SPLIT]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, %other
+  %1 = and i8 %0, 1
+  %or.cond.not.not = icmp eq i8 %1, 0
+  br i1 %or.cond.not.not, label %return.sink.split, label %return
+
+return.sink.split:                                ; preds = %entry
+  %call7 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %return.sink.split
+  %retval.0 = phi i8 [ %call7, %return.sink.split ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @or_br_oddV_evenV_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @or_br_oddV_evenV_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[TMP0]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[OTHER:%.*]], 1
+; CHECK-NEXT:    [[CMP4_NOT:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[CMP]], [[CMP4_NOT]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[RETURN:%.*]], label [[RETURN_SINK_SPLIT:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL7]], [[RETURN_SINK_SPLIT]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, 1
+  %cmp = icmp ne i8 %0, 0
+  %1 = and i8 %other, 1
+  %cmp4.not = icmp eq i8 %1, 0
+  %or.cond = and i1 %cmp, %cmp4.not
+  br i1 %or.cond, label %return, label %return.sink.split
+
+return.sink.split:                                ; preds = %entry
+  %call7 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %return.sink.split
+  %retval.0 = phi i8 [ %call7, %return.sink.split ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @or_br_oddV_oddV_and1_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @or_br_oddV_oddV_and1_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], [[OTHER:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP0]], 1
+; CHECK-NEXT:    [[OR_COND_NOT_NOT:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[OR_COND_NOT_NOT]], label [[RETURN_SINK_SPLIT:%.*]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL7]], [[RETURN_SINK_SPLIT]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, %other
+  %1 = and i8 %0, 1
+  %or.cond.not.not = icmp eq i8 %1, 0
+  br i1 %or.cond.not.not, label %return.sink.split, label %return
+
+return.sink.split:                                ; preds = %entry
+  %call7 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %return.sink.split
+  %retval.0 = phi i8 [ %call7, %return.sink.split ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @or_br_oddV_oddV_and2_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @or_br_oddV_oddV_and2_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], [[OTHER:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP0]], 1
+; CHECK-NEXT:    [[OR_COND_NOT_NOT:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[OR_COND_NOT_NOT]], label [[RETURN_SINK_SPLIT:%.*]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL7]], [[RETURN_SINK_SPLIT]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, %other
+  %1 = and i8 %0, 1
+  %or.cond.not.not = icmp eq i8 %1, 0
+  br i1 %or.cond.not.not, label %return.sink.split, label %return
+
+return.sink.split:                                ; preds = %entry
+  %call7 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %return.sink.split
+  %retval.0 = phi i8 [ %call7, %return.sink.split ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+define zeroext i8 @or_br_oddV_oddV_and3_u8_setz(i8 zeroext %v, i8 zeroext %other) {
+; CHECK-LABEL: @or_br_oddV_oddV_and3_u8_setz(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[V:%.*]], [[OTHER:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP0]], 1
+; CHECK-NEXT:    [[OR_COND_NOT_NOT:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[OR_COND_NOT_NOT]], label [[RETURN_SINK_SPLIT:%.*]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[CALL7:%.*]] = tail call zeroext i8 (...) @baz8()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[CALL7]], [[RETURN_SINK_SPLIT]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[RETVAL_0]]
+;
+entry:
+  %0 = and i8 %v, %other
+  %1 = and i8 %0, 1
+  %or.cond.not.not = icmp eq i8 %1, 0
+  br i1 %or.cond.not.not, label %return.sink.split, label %return
+
+return.sink.split:                                ; preds = %entry
+  %call7 = tail call zeroext i8 (...) @baz8()
+  br label %return
+
+return:                                           ; preds = %entry, %return.sink.split
+  %retval.0 = phi i8 [ %call7, %return.sink.split ], [ 1, %entry ]
+  ret i8 %retval.0
+}
+
+declare void @llvm.assume(i1)
diff --git a/llvm/test/Transforms/InstCombine/pr38677.ll b/llvm/test/Transforms/InstCombine/pr38677.ll
--- a/llvm/test/Transforms/InstCombine/pr38677.ll
+++ b/llvm/test/Transforms/InstCombine/pr38677.ll
@@ -12,9 +12,7 @@
 ; CHECK-NEXT:    br label [[FINAL]]
 ; CHECK:       final:
 ; CHECK-NEXT:    [[USE2:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ select (i1 icmp eq (ptr @A, ptr @B), i32 2, i32 1), [[DELAY]] ]
-; CHECK-NEXT:    [[B7:%.*]] = mul i32 [[USE2]], 2147483647
-; CHECK-NEXT:    [[C3:%.*]] = icmp eq i32 [[B7]], 0
-; CHECK-NEXT:    store i1 [[C3]], ptr [[DST:%.*]], align 1
+; CHECK-NEXT:    store i1 false, ptr [[DST:%.*]], align 1
 ; CHECK-NEXT:    ret i32 [[USE2]]
 ;
 entry: