[Patch 4/4]: Use cannoical patterns `(A > C1 && A < C2)` and `(A & B != C)` in `isKnownNonZero`

[goldstein.w.n]

Summary

Both patterns where missed because they go through a level of
indirection:

1. A > C1 && A < C2 cannonicalizes to ICMP_ULT (A + C3, C4)
   • Try and match this pattern explicitly in isKnownNonNullFromDominatingCondition

2. A & B != C
   • Since cmp ne (A & B, 0) implies cmp ne (A, 0) just match that as an additional generic pattern in isKnownNonNullFromDominatingCondition. This was already done in the final worklist loop.

The rationale is C-code like:

int foo(int A, int B) {
    if(A % 2 == 0) {
        // A is provably odd but `isKnownNonZero(A)` will not find any
        // cmp directly acting on A. The same applies for the ICMP_ULT
        // case.
        return !!(A * B);
    }
    ...
}

[goldstein.w.n]

Note:

I have run alive2 to verify all the transformations from this patch in relation to D140849 although I have not verified the changes from D140850 and D140851 individually.

[goldstein.w.n]

propegating changes from rebase

[goldstein.w.n]

Closing in favor the series starting at: D142827

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/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 (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
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

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

 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:    [[MUL:%.*]] = mul nuw nsw i64 [[OTHER]], [[V]]
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; 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

 ; 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:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V]], 0
-; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
-; CHECK-NEXT:    ret i64 [[CONV]]
+; 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)

 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:    [[MUL:%.*]] = mul nuw nsw i32 [[OTHER]], [[V]]
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; 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:

 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:    [[CONV:%.*]] = sext i16 [[OTHER:%.*]] to i32
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CONV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; 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:    [[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:    [[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:

 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:    [[CONV:%.*]] = sext i16 [[V:%.*]] to i32
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CONV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; 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:    [[CONV2:%.*]] = sext i16 [[OTHER:%.*]] to i32
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[CONV2]], 1
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i32 [[AND3]], 0
+; 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:    [[MUL:%.*]] = mul nsw i32 [[CONV2]], [[CONV]]
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END13:%.*]], label [[IF_THEN11:%.*]]
+; 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:    [[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:    [[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
 

 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:    [[CONV:%.*]] = sext i16 [[V:%.*]] to i32
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CONV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; 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:    [[CONV2:%.*]] = sext i16 [[OTHER:%.*]] to i32
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[CONV2]], 1
-; CHECK-NEXT:    [[CMP4_NOT:%.*]] = icmp eq i32 [[AND3]], 0
+; 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:    [[MUL:%.*]] = mul nsw i32 [[CONV2]], [[CONV]]
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; 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:

 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:    [[CONV:%.*]] = sext i16 [[V:%.*]] to i32
-; CHECK-NEXT:    [[TMP0:%.*]] = add i16 [[V]], -8
+; 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:    [[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-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:    [[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:    [[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
 

 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:    [[CONV:%.*]] = sext i16 [[V:%.*]] to i32
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CONV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; 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:    [[CONV2:%.*]] = sext i16 [[OTHER:%.*]] to i32
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[CONV2]], 1
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i32 [[AND3]], 0
+; 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:    [[OR:%.*]] = or i32 [[CONV2]], [[CONV]]
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[OR]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END13:%.*]], label [[IF_THEN11:%.*]]
+; 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:    [[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:    [[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
 

 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:    [[CONV:%.*]] = zext i8 [[OTHER:%.*]] to i32
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CONV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; 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:    [[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:    [[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

 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:    [[CONV:%.*]] = zext i8 [[V:%.*]] to i32
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CONV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; 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:    [[CONV2:%.*]] = zext i8 [[OTHER:%.*]] to i32
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[CONV2]], 1
-; CHECK-NEXT:    [[CMP4_NOT:%.*]] = icmp eq i32 [[AND3]], 0
+; 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:    [[MUL:%.*]] = mul nuw nsw i32 [[CONV2]], [[CONV]]
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[MUL]], 0
+; 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

 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:    [[CONV:%.*]] = zext i8 [[V:%.*]] to i32
-; CHECK-NEXT:    [[TMP0:%.*]] = add i8 [[V]], -8
+; 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:    [[CONV5:%.*]] = zext i8 [[OTHER]] to i32
-; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i32 [[CONV5]], [[CONV]]
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[MUL]], 0
+; 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