Tests + Improve cases for optimizing out some icmp(binop) patterns (mostly mul)

[goldstein.w.n]

Summary

Commit 1 (Tests):

Add tests for binops with conditions/assume constraints

Commit 2 (Code Changes):

Improve cases for optimizing out some icmp(binop) patterns (mostly mul)

1. Add some explicit cases for mul that were missing.
2. Improve ValueTracking analysis to better track the ICMP_NE and ICMP_ULT patterns.
   • Both for tracking on edges of BBs and for conditions that are used by llvm.assume

[goldstein.w.n]

ran alive2 on all transform.

Transforms/InstCombine/pr38677.ll: https://alive2.llvm.org/ce/z/atn3gZ

$> alive-tv --smt-to=2500000 BEFORE-icmp-binop.ll AFTER-icmp-binop.ll
...
Summary:

146 correct transformations
0 incorrect transformations
0 failed-to-prove transformations
0 Alive2 errors

[goldstein.w.n]

The revision has two commits, I created the revision with:

$> arc diff --create HEAD^^

Although it seems to have chosen the commit header for the 1st commit (tests before the change)
and the entire second commit message for the summary.

Sorry about that. I think I need to modify the message in arc diff when doing multi-commit
patches in the future.

[nikic]

This patch is mixing up a lot of different changes. Please split it up into self-contained changes to the degree that this is possible. I would recommend starting with just your changes in InstCombineCompares, as these look like they should be able to stand on their own (without changes to AssumptionCache machinery).

[goldstein.w.n]

In D140840#4021706, @nikic wrote:

This patch is mixing up a lot of different changes. Please split it up into self-contained changes to the degree that this is possible. I would recommend starting with just your changes in InstCombineCompares, as these look like they should be able to stand on their own (without changes to AssumptionCache machinery).

Sure, should I just post back to this one with the changes split into more commits or create a new review starting with
the InstCombineCompares change?

[nikic]

In D140840#4021722, @goldstein.w.n wrote:

In D140840#4021706, @nikic wrote:

This patch is mixing up a lot of different changes. Please split it up into self-contained changes to the degree that this is possible. I would recommend starting with just your changes in InstCombineCompares, as these look like they should be able to stand on their own (without changes to AssumptionCache machinery).

Sure, should I just post back to this one with the changes split into more commits or create a new review starting with
the InstCombineCompares change?

Locally you'd probably want to split into commits, but as far as Phabricator is concerned they should be separate reviews -- Phabricator does not allow reviewing individual commits in a review. I don't know how one does that through arc, I always upload patches via the web interface.

[goldstein.w.n]

In D140840#4021782, @nikic wrote:

In D140840#4021722, @goldstein.w.n wrote:

In D140840#4021706, @nikic wrote:

This patch is mixing up a lot of different changes. Please split it up into self-contained changes to the degree that this is possible. I would recommend starting with just your changes in InstCombineCompares, as these look like they should be able to stand on their own (without changes to AssumptionCache machinery).

Sure, should I just post back to this one with the changes split into more commits or create a new review starting with
the InstCombineCompares change?

Locally you'd probably want to split into commits, but as far as Phabricator is concerned they should be separate reviews -- Phabricator does not allow reviewing individual commits in a review. I don't know how one does that through arc, I always upload patches via the web interface.

Okay, I split it into 4 commits and 4 separate reviews:

Tests

https://reviews.llvm.org/D140849

InstCombineCompares

https://reviews.llvm.org/D140850

AssumptionCache

https://reviews.llvm.org/D140851

isKnownNonZero

https://reviews.llvm.org/D140852

Is there a way to close this review?

[goldstein.w.n]

@nikic This is somewhat unrelated so if this is not the place to ask, let me know.

I see your commit:

[InstCombine] Make TTI comment more forceful (NFC)

To save people not familiar with InstCombine from creating patches
that are immediately rejected by policy.

I was hoping to make a patch to avoid the de-optimization
that occurs in ShrinkDemandedConstant when the reduced
bits does something like break imm8 sign extension and forces
an imm64 (causes movabs for X86, ot movk + lsl/ldq on
aarch64).

I figured the best way to do this was with getIntImmCostInst
but your comment is pretty forceful.

Is this an acceptable use case that could warrant an exception?
If not, do you have an advise for how to avoid this de-optimization?

llvm/include/llvm/IR/InstrTypes.h

static_assert(FIRST_FCMP_PREDICATE == 0,
                   "FIRST_FCMP_PREDICATE is required to be 0");
     return P <= LAST_FCMP_PREDICATE;
   }
 
   static bool isIntPredicate(Predicate P) {
     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()); }
   bool isIntPredicate() const { return isIntPredicate(getPredicate()); }
 
   /// For example, EQ -> NE, UGT -> ULE, SLT -> SGE,
   ///              OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
   /// @returns the inverse predicate for the instruction's current predicate.

llvm/lib/Analysis/AssumptionCache.cpp

if (Pred == ICmpInst::ICMP_EQ) {
           AddAffected(A);
         }
       };
 
       AddAffectedFromEq(A);
       AddAffectedFromEq(B);
     }
 
+    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 (Pred == ICmpInst::ICMP_ULT &&
-        match(A, m_Add(m_Value(X), m_ConstantInt())) &&
+      if (match(A, m_Add(m_Value(X), m_ConstantInt())) &&
           match(B, m_ConstantInt()))
         AddAffected(X);
     }
+  }
 
   if (TTI) {
     const Value *Ptr;
     unsigned AS;
     std::tie(Ptr, AS) = TTI->getPredicatedAddrSpace(Cond);
     if (Ptr)
       AddAffected(const_cast<Value *>(Ptr->stripInBoundsOffsets()));
   }

llvm/lib/Analysis/ValueTracking.cpp

for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
     // runtime of ~O(#assumes * #values).
 
     assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
            "must be an assume intrinsic");
 
     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;
 
     if (cmpExcludesZero(Pred, RHS) && isValidAssumeForContext(I, Q.CxtI, Q.DT))
       return true;
   }
 
   return false;
for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
     // The remaining tests are all recursive, so bail out if we hit the limit.
     if (Depth == MaxAnalysisRecursionDepth)
       continue;
 
     ICmpInst *Cmp = dyn_cast<ICmpInst>(Arg);
     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.
     // An example of the mutual recursion: computeKnownBits can call
     // isKnownNonZero which calls computeKnownBitsFromAssume (this function)
     // and so on.
     Query QueryNoAC = Q;
     QueryNoAC.AC = nullptr;
 
     // Note that ptrtoint may change the bitwidth.
     Value *A, *B;
     auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V)));
 
     CmpInst::Predicate Pred;
     uint64_t C;
     switch (Cmp->getPredicate()) {
     default:
       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 =
             computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in the mask that are known to be one, we can propagate
         // known bits from the RHS to V.
         Known.Zero |= RHSKnown.Zero & MaskKnown.One;
         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 =
             computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in the mask that are known to be one, we can propagate
         // inverted known bits from the RHS to V.
         Known.Zero |= RHSKnown.One  & MaskKnown.One;
         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 =
             computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in B that are known to be zero, we can propagate known
         // bits from the RHS to V.
         Known.Zero |= RHSKnown.Zero & BKnown.Zero;
         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 =
             computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in B that are known to be zero, we can propagate
         // inverted known bits from the RHS to V.
         Known.Zero |= RHSKnown.One  & BKnown.Zero;
         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 =
             computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in B that are known to be zero, we can propagate known
         // bits from the RHS to V. For those bits in B that are known to be one,
         // we can propagate inverted known bits from the RHS to V.
         Known.Zero |= RHSKnown.Zero & BKnown.Zero;
         Known.One  |= RHSKnown.One  & BKnown.Zero;
         Known.Zero |= RHSKnown.One  & BKnown.One;
         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 =
             computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in B that are known to be zero, we can propagate
         // inverted known bits from the RHS to V. For those bits in B that are
         // known to be one, we can propagate known bits from the RHS to V.
         Known.Zero |= RHSKnown.One  & BKnown.Zero;
         Known.One  |= RHSKnown.Zero & BKnown.Zero;
         Known.Zero |= RHSKnown.Zero & BKnown.One;
         Known.One  |= RHSKnown.One  & BKnown.One;
       // 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);
 
         // For those bits in RHS that are known, we can propagate them to known
         // bits in V shifted to the right by C.
         RHSKnown.Zero.lshrInPlace(C);
         Known.Zero |= RHSKnown.Zero;
         RHSKnown.One.lshrInPlace(C);
         Known.One  |= RHSKnown.One;
       // 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
         // to known bits in V shifted to the right by C.
         RHSKnown.One.lshrInPlace(C);
         Known.Zero |= RHSKnown.One;
         RHSKnown.Zero.lshrInPlace(C);
         Known.One  |= RHSKnown.Zero;
       // 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
         // bits in V shifted to the right by C.
         Known.Zero |= RHSKnown.Zero << C;
         Known.One  |= RHSKnown.One  << C;
       // 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
         // to known bits in V shifted to the right by C.
         Known.Zero |= RHSKnown.One  << C;
         Known.One  |= RHSKnown.Zero << C;
       }
       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);
 
         if (RHSKnown.isNonNegative()) {
           // We know that the sign bit is zero.
           Known.makeNonNegative();
         }
       }
       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);
 
         if (RHSKnown.isAllOnes() || RHSKnown.isNonNegative()) {
           // We know that the sign bit is zero.
           Known.makeNonNegative();
         }
       }
       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);
 
         if (RHSKnown.isNegative()) {
           // We know that the sign bit is one.
           Known.makeNegative();
         }
       }
       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);
 
         if (RHSKnown.isZero() || RHSKnown.isNegative()) {
           // We know that the sign bit is one.
           Known.makeNegative();
         }
       }
       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);
 
         // Whatever high bits in c are zero are known to be zero.
         Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros());
       }
       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);
 
         // If the RHS is known zero, then this assumption must be wrong (nothing
         // is unsigned less than zero). Signal a conflict and get out of here.
         if (RHSKnown.isZero()) {
           Known.Zero.setAllBits();
           Known.One.setAllBits();
           break;
         }
 
         // Whatever high bits in c are zero are known to be zero (if c is a power
         // of 2, then one more).
         if (isKnownToBeAPowerOfTwo(A, false, Depth + 1, QueryNoAC))
           Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros() + 1);
         else
           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;
     }
   }
 
   // If assumptions conflict with each other or previous known bits, then we
   // have a logical fallacy. It's possible that the assumption is not reachable,
   // so this isn't a real bug. On the other hand, the program may have undefined
   // behavior, or we might have a bug in the compiler. We can't assert/crash, so
   // clear out the known bits, try to warn the user, and hope for the best.
for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
     if (isKnownNonZero(GTI.getOperand(), Depth, Q))
       return true;
   }
 
   return false;
 }
 
 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;
 
   if (!CtxI || !DT)
     return false;
 
   unsigned NumUsesExplored = 0;
   for (const auto *U : V->users()) {
if (V == getLoadStorePointerOperand(U)) {
                                 V->getType()->getPointerAddressSpace()) &&
           DT->dominates(I, CtxI))
         return true;
     }
 
     // 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;
+    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);
 
       while (!WorkList.empty()) {
         auto *Curr = WorkList.pop_back_val();
 
         // If a user is an AND, add all its users to the work list. We only
         // propagate "pred != null" condition through AND because it is only
         // correct to assume that all conditions of AND are met in true branch.
         // TODO: Support similar logic of OR and EQ predicate?
         if (NonNullIfTrue)
           if (match(Curr, m_LogicalAnd(m_Value(), m_Value()))) {
             for (const auto *CurrU : Curr->users())
               if (Visited.insert(CurrU).second)
                 WorkList.push_back(CurrU);
             continue;
           }
 
+
         if (const BranchInst *BI = dyn_cast<BranchInst>(Curr)) {
           assert(BI->isConditional() && "uses a comparison!");
 
           BasicBlock *NonNullSuccessor =
               BI->getSuccessor(NonNullIfTrue ? 0 : 1);
           BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
           if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
             return true;
if (PointerType *PtrTy = dyn_cast<PointerType>(V->getType())) {
     if (const auto *Call = dyn_cast<CallBase>(V)) {
       if (Call->isReturnNonNull())
         return true;
       if (const auto *RP = getArgumentAliasingToReturnedPointer(Call, true))
         return isKnownNonZero(RP, Depth, Q);
     }
   }
 
-  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);
   if (!I)
     return false;
 
   unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), Q.DL);
   switch (I->getOpcode()) {

llvm/lib/IR/Instructions.cpp

 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #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"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/AtomicOrdering.h"

 bool CmpInst::isEquality(Predicate P) {
   if (ICmpInst::isIntPredicate(P))
     return ICmpInst::isEquality(P);
   if (FCmpInst::isFPPredicate(P))
     return FCmpInst::isEquality(P);
   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!");
     case ICMP_EQ: return ICMP_NE;
     case ICMP_NE: return ICMP_EQ;
     case ICMP_UGT: return ICMP_ULE;
     case ICMP_ULT: return ICMP_UGE;
     case ICMP_UGE: return ICMP_ULT;

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpWithZero(ICmpInst &Cmp) {
   Value *X, *Y;
   if (match(Cmp.getOperand(0), m_URem(m_Value(X), m_Value(Y))) &&
       ICmpInst::isEquality(Pred)) {
     KnownBits XKnown = computeKnownBits(X, 0, &Cmp);
     KnownBits YKnown = computeKnownBits(Y, 0, &Cmp);
     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;
 }
 
 /// Fold icmp Pred X, C.
 /// TODO: This code structure does not make sense. The saturating add fold
 /// should be moved to some other helper and extended as noted below (it is also
 /// possible that code has been made unnecessary - do we canonicalize IR to
 /// overflow/saturating intrinsics or not?).
if (Pred == CmpInst::ICMP_SGT && C == *C2 - 1)
     return new ICmpInst(ICmpInst::ICMP_ULT, X, ConstantInt::get(Ty, SMax - C));
 
   // (X + C2) <s C --> X >u (C ^ SMAX) (if C == C2)
   if (Pred == CmpInst::ICMP_SLT && C == *C2)
     return new ICmpInst(ICmpInst::ICMP_UGT, X, ConstantInt::get(Ty, C ^ SMax));
 
   // (X + -1) <u C --> X <=u C (if X is never null)
   if (Pred == CmpInst::ICMP_ULT && C2->isAllOnes()) {
+    // 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())
     return nullptr;
 
   // X+C <u C2 -> (X & -C2) == C
   //   iff C & (C2-1) == 0
   //       C2 is a power of 2
   if (Pred == ICmpInst::ICMP_ULT && C.isPowerOf2() && (*C2 & (C - 1)) == 0)

llvm/test/Transforms/InstCombine/icmp-binop.ll

+; 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)

llvm/test/Transforms/InstCombine/pr38677.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ;RUN: opt -passes=instcombine -S %s | FileCheck %s
 
 @A = extern_weak global i32, align 4
 @B = extern_weak global i32, align 4
 
 define i32 @foo(i1 %which, ptr %dst) {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 true, label [[FINAL:%.*]], label [[DELAY:%.*]]
 ; CHECK:       delay:
 ; 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:
   br i1 true, label %final, label %delay
 
 delay:                                            ; preds = %entry
   br label %final
 
 final:                                            ; preds = %delay, %entry
   %use2 = phi i1 [ false, %entry ], [ icmp eq (ptr @A, ptr @B), %delay ]
   %value = select i1 %use2, i32 2, i32 1
   %B7 = mul i32 %value, 2147483647
   %C3 = icmp ule i32 %B7, 0
   store i1 %C3, ptr %dst
   ret i32 %value
 }