[InstCombine] Fold overflow bit of [u|s]mul.with.overflow in a poison-safe way

[aqjune]

Summary

As discussed in D101191, this patch adds a poison-safe folding of overflow bit check:

  %Op0 = icmp ne i4 %X, 0
  %Agg = call { i4, i1 } @llvm.[us]mul.with.overflow.i4(i4 %X, i4 %Y)
  %Op1 = extractvalue { i4, i1 } %Agg, 1
  %ret = select i1 %Op0, i1 %Op1, i1 false
=>
  %Y.fr = freeze %Y
  %Agg = call { i4, i1 } @llvm.[us]mul.with.overflow.i4(i4 %X, i4 %Y.fr)
  %Op1 = extractvalue { i4, i1 } %Agg, 1
  %ret = %Op1

https://alive2.llvm.org/ce/z/zgPUGT
https://alive2.llvm.org/ce/z/h2gZ_6

Note that there are cases where inserting freeze is not necessary: e.g. %Y is noundef.
In this case, LLVM is already good because %ret is already successfully folded into and,
triggering the pre-existing optimization in InstSimplify: https://godbolt.org/z/v6qena15K

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2588

The function below is based on InstSimplify's version.

llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll

8 ↗

(On Diff #341062)

-instcombine-unsafe-select-transform=0 is added to show the impact of this patch.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2588

Duplicating so much code feels wrong. Could we just call the simplify code from here with something like:

// Simulate a bitwise logic op for a select with a constant operand. 
if (match(FalseVal, m_Zero())) {
  if (Value *Simplified =
          SimplifyAndInst(CondVal, TrueVal, SQ.getWithInstruction(&SI))) {
    // create freeze and return
  }
}
if (match(TrueVal, m_One())) {
  if (Value *Simplified =
          SimplifyOrInst(CondVal, FalseVal, SQ.getWithInstruction(&SI))) {
    // create freeze and return
  }
}

llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll

8 ↗

(On Diff #341062)

I would prefer to leave this file unchanged with this patch, so we still have an indicator to represent the overall behavior of the optimizer.

We should add minimal tests for this patch under test/Transforms/InstCombine. These could be based on the test files from D65150 / D65151 - just replace the and/or logic instructions with select?

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2588

I think we still need to look into the expression because we should determine which variable to freeze.

If there is a header file that InstSimplify and InstCombine can share would be a great place for this function?

llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll

8 ↗

(On Diff #341062)

No problem, I'll make tests like those in the next iteration.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2588

Don't we only need to freeze the operand that is not in the icmp expression? That is, CondVal of the select must match as an icmp with a non-zero operand, and it's the other value that must be frozen.

I don't know of a shared header in Analysis for general logic. We do have things like VectorUtils and CmpInstAnalysis, so we could invent some new place.

[lebedev.ri]

I have a really 'are you nuts' proposal.
How about we canonicalize all i1 and/or's into select form?
Then that instsimplify code becomes dead, and we can simply port it here.
And we'll weed out all the remaining patterns that still only handle the and/or forms/

[aqjune]

In D101423#2723737, @lebedev.ri wrote:

I have a really 'are you nuts' proposal.
How about we canonicalize all i1 and/or's into select form?
Then that instsimplify code becomes dead, and we can simply port it here.
And we'll weed out all the remaining patterns that still only handle the and/or forms/

This will reduce a lot of complexity between having both select and or/and i1, but one concern is that select isn't commutative. :(
I mean, and i1 %a, %b == and i1 %b, %a, but in case of select select i1 %a, %b, false != select i1 %b, %a, false due to poison.
So we'll have to carefully choose which form to use, which can be a hard problem.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2588

Don't we only need to freeze the operand that is not in the icmp expression? That is, CondVal of the select must match as an icmp with a non-zero operand, and it's the other value that must be frozen.

Yep, the variable is the one to freeze.
My concern was about code duplication: the pattern matching code should still be copied here to pick the variable...

I don't know of a shared header in Analysis for general logic. We do have things like VectorUtils and CmpInstAnalysis, so we could invent some new place.

Actually to me having a separate header like CmpInstAnalysis and VectorUtil looks great.
Would creating something like OverflowInstAnalysis make sense?
If it is too much, having InstSimplifyUtils.h in llvm/lib/Analysis & including it from InstCombineSelect.cpp?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2588

An Overflow analysis file sounds good. At this point, I think there's only the mul code that would go in there, but we might find other common code later.

[aqjune]

• Move the function into the new header file
• Update ValueTracking's impliesPoison to convert select to and/or if valid.

This avoids redundant freeze insertion (see div-by-0-guard-before-smul_ov-not.ll 's t1_commutative)

[aqjune]

clang-format

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

5023

This update adds an inferences that if a is poison, extract(mul_with_overflow(a, _), _) is also poison.

This enables transformation

select(extract(mul_with_overflow(a, _), _), (a == 0), false)
=>
and(extract(mul_with_overflow(a, _), _), (a == 0))
```.

[spatel]

LGTM - see inline for some small improvements.

llvm/include/llvm/Analysis/OverflowInstAnalysis.h

34

This is confusing if we do not have the context of the callers that we can see in this patch.
The comment should say something like: "Match one of the patterns up to the select/logic op. Callers are expected to align that with the operands of the select/logic op user."

36

"is used" -> "are used"

37

"is one" -> "match one"

llvm/lib/Analysis/ValueTracking.cpp

5024

Use "is_contained" ?
Is it possible to separate this change (with an independent test)?

llvm/include/llvm/Analysis/OverflowInstAnalysis.h

+//===-- OverflowInstAnalysis.h - Utils to fold overflow insts ----*- C++ -*-==//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file holds routines to help analyse overflow instructions
+// and fold them into constants or other overflow instructions
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_OVERFLOWINSTANALYSIS_H
+#define LLVM_ANALYSIS_OVERFLOWINSTANALYSIS_H
+
+#include "llvm/IR/InstrTypes.h"
+
+namespace llvm {
+  class Value;
+  class Use;
+
+  /// Look for:
+  ///   %Op0 = icmp ne i4 %X, 0
+  ///   %Agg = call { i4, i1 } @llvm.[us]mul.with.overflow.i4(i4 %X, i4 %Y)
+  ///   %Op1 = extractvalue { i4, i1 } %Agg, 1
+  ///   %ret = select i1 %Op0, i1 %Op1, i1 false / %ret = and i1 %Op0, %Op1
+  ///
+  ///   %Op0 = icmp eq i4 %X, 0
+  ///   %Agg = call { i4, i1 } @llvm.[us]mul.with.overflow.i4(i4 %X, i4 %Y)
+  ///   %NotOp1 = extractvalue { i4, i1 } %Agg, 1
+  ///   %Op1 = xor i1 %NotOp1, true
+  ///   %ret = select i1 %Op0, i1 true, i1 %Op1 / %ret = or i1 %Op0, %Op1
+  ///
+  /// IsAnd is set to true if the Op0 and Op1 is used as the first pattern.
+  /// If Op0 and Op1 is one of the patterns above, return true and fill Y's use.
+
+  bool isCheckForZeroAndMulWithOverflow(Value *Op0, Value *Op1, bool IsAnd,
+                                        Use *&Y);
+  bool isCheckForZeroAndMulWithOverflow(Value *Op0, Value *Op1, bool IsAnd);
+} // end namespace llvm
+
+#endif

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   MemorySSAUpdater.cpp
   ModuleDebugInfoPrinter.cpp
   ModuleSummaryAnalysis.cpp
   MustExecute.cpp
   ObjCARCAliasAnalysis.cpp
   ObjCARCAnalysisUtils.cpp
   ObjCARCInstKind.cpp
   OptimizationRemarkEmitter.cpp
+  OverflowInstAnalysis.cpp
   PHITransAddr.cpp
   PhiValues.cpp
   PostDominators.cpp
   ProfileSummaryInfo.cpp
   PtrUseVisitor.cpp
   RegionInfo.cpp
   RegionPass.cpp
   RegionPrinter.cpp

llvm/lib/Analysis/InstructionSimplify.cpp

 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/CmpInstAnalysis.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/OverflowInstAnalysis.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/InstrTypes.h"
static Value *simplifyAndOrOfCmps(const SimplifyQuery &Q,
   // If we looked through casts, we can only handle a constant simplification
   // because we are not allowed to create a cast instruction here.
   if (auto *C = dyn_cast<Constant>(V))
     return ConstantExpr::getCast(Cast0->getOpcode(), C, Cast0->getType());
 
   return nullptr;
 }
 
-/// Check that the Op1 is in expected form, i.e.:
-///   %Agg = tail call { i4, i1 } @llvm.[us]mul.with.overflow.i4(i4 %X, i4 %???)
-///   %Op1 = extractvalue { i4, i1 } %Agg, 1
-static bool omitCheckForZeroBeforeMulWithOverflowInternal(Value *Op1,
-                                                          Value *X) {
-  auto *Extract = dyn_cast<ExtractValueInst>(Op1);
-  // We should only be extracting the overflow bit.
-  if (!Extract || !Extract->getIndices().equals(1))
-    return false;
-  Value *Agg = Extract->getAggregateOperand();
-  // This should be a multiplication-with-overflow intrinsic.
-  if (!match(Agg, m_CombineOr(m_Intrinsic<Intrinsic::umul_with_overflow>(),
-                              m_Intrinsic<Intrinsic::smul_with_overflow>())))
-    return false;
-  // One of its multipliers should be the value we checked for zero before.
-  if (!match(Agg, m_CombineOr(m_Argument<0>(m_Specific(X)),
-                              m_Argument<1>(m_Specific(X)))))
-    return false;
-  return true;
-}
-
-/// The @llvm.[us]mul.with.overflow intrinsic could have been folded from some
-/// other form of check, e.g. one that was using division; it may have been
-/// guarded against division-by-zero. We can drop that check now.
-/// Look for:
-///   %Op0 = icmp ne i4 %X, 0
-///   %Agg = tail call { i4, i1 } @llvm.[us]mul.with.overflow.i4(i4 %X, i4 %???)
-///   %Op1 = extractvalue { i4, i1 } %Agg, 1
-///   %??? = and i1 %Op0, %Op1
-/// We can just return  %Op1
-static Value *omitCheckForZeroBeforeMulWithOverflow(Value *Op0, Value *Op1) {
-  ICmpInst::Predicate Pred;
-  Value *X;
-  if (!match(Op0, m_ICmp(Pred, m_Value(X), m_Zero())) ||
-      Pred != ICmpInst::Predicate::ICMP_NE)
-    return nullptr;
-  // Is Op1 in expected form?
-  if (!omitCheckForZeroBeforeMulWithOverflowInternal(Op1, X))
-    return nullptr;
-  // Can omit 'and', and just return the overflow bit.
-  return Op1;
-}
-
-/// The @llvm.[us]mul.with.overflow intrinsic could have been folded from some
-/// other form of check, e.g. one that was using division; it may have been
-/// guarded against division-by-zero. We can drop that check now.
-/// Look for:
-///   %Op0 = icmp eq i4 %X, 0
-///   %Agg = tail call { i4, i1 } @llvm.[us]mul.with.overflow.i4(i4 %X, i4 %???)
-///   %Op1 = extractvalue { i4, i1 } %Agg, 1
-///   %NotOp1 = xor i1 %Op1, true
-///   %or = or i1 %Op0, %NotOp1
-/// We can just return  %NotOp1
-static Value *omitCheckForZeroBeforeInvertedMulWithOverflow(Value *Op0,
-                                                            Value *NotOp1) {
-  ICmpInst::Predicate Pred;
-  Value *X;
-  if (!match(Op0, m_ICmp(Pred, m_Value(X), m_Zero())) ||
-      Pred != ICmpInst::Predicate::ICMP_EQ)
-    return nullptr;
-  // We expect the other hand of an 'or' to be a 'not'.
-  Value *Op1;
-  if (!match(NotOp1, m_Not(m_Value(Op1))))
-    return nullptr;
-  // Is Op1 in expected form?
-  if (!omitCheckForZeroBeforeMulWithOverflowInternal(Op1, X))
-    return nullptr;
-  // Can omit 'and', and just return the inverted overflow bit.
-  return NotOp1;
-}
-
 /// Given a bitwise logic op, check if the operands are add/sub with a common
 /// source value and inverted constant (identity: C - X -> ~(X + ~C)).
 static Value *simplifyLogicOfAddSub(Value *Op0, Value *Op1,
                                     Instruction::BinaryOps Opcode) {
   assert(Op0->getType() == Op1->getType() && "Mismatched binop types");
   assert(BinaryOperator::isBitwiseLogicOp(Opcode) && "Expected logic op");
   Value *X;
   Constant *C1, *C2;
if (match(Op1, m_APInt(Mask))) {
     if (match(Op0, m_LShr(m_Value(X), m_APInt(ShAmt))) &&
         (~(*Mask)).shl(*ShAmt).isNullValue())
       return Op0;
   }
 
   // If we have a multiplication overflow check that is being 'and'ed with a
   // check that one of the multipliers is not zero, we can omit the 'and', and
   // only keep the overflow check.
-  if (Value *V = omitCheckForZeroBeforeMulWithOverflow(Op0, Op1))
-    return V;
-  if (Value *V = omitCheckForZeroBeforeMulWithOverflow(Op1, Op0))
-    return V;
+  if (isCheckForZeroAndMulWithOverflow(Op0, Op1, true))
+    return Op1;
+  if (isCheckForZeroAndMulWithOverflow(Op1, Op0, true))
+    return Op0;
 
   // A & (-A) = A if A is a power of two or zero.
   if (match(Op0, m_Neg(m_Specific(Op1))) ||
       match(Op1, m_Neg(m_Specific(Op0)))) {
     if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
                                Q.DT))
       return Op0;
     if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
if (match(Op1, m_c_And(m_CombineAnd(m_Value(NotA), m_Not(m_Value(A))),
     return NotA;
 
   if (Value *V = simplifyAndOrOfCmps(Q, Op0, Op1, false))
     return V;
 
   // If we have a multiplication overflow check that is being 'and'ed with a
   // check that one of the multipliers is not zero, we can omit the 'and', and
   // only keep the overflow check.
-  if (Value *V = omitCheckForZeroBeforeInvertedMulWithOverflow(Op0, Op1))
-    return V;
-  if (Value *V = omitCheckForZeroBeforeInvertedMulWithOverflow(Op1, Op0))
-    return V;
+  if (isCheckForZeroAndMulWithOverflow(Op0, Op1, false))
+    return Op1;
+  if (isCheckForZeroAndMulWithOverflow(Op1, Op0, false))
+    return Op0;
 
   // Try some generic simplifications for associative operations.
   if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q,
                                           MaxRecurse))
     return V;
 
   // Or distributes over And.  Try some generic simplifications based on this.
   if (Value *V = expandCommutativeBinOp(Instruction::Or, Op0, Op1,

llvm/lib/Analysis/OverflowInstAnalysis.cpp

+//==-- OverflowInstAnalysis.cpp - Utils to fold overflow insts ----*- C++ -*-=//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file holds routines to help analyse overflow instructions
+// and fold them into constants or other overflow instructions
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/OverflowInstAnalysis.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/PatternMatch.h"
+
+using namespace llvm;
+using namespace llvm::PatternMatch;
+
+bool llvm::isCheckForZeroAndMulWithOverflow(Value *Op0, Value *Op1, bool IsAnd,
+                                            Use *&Y) {
+  ICmpInst::Predicate Pred;
+  Value *X, *NotOp1;
+  int XIdx;
+  IntrinsicInst *II;
+
+  if (!match(Op0, m_ICmp(Pred, m_Value(X), m_Zero())))
+    return false;
+
+  ///   %Agg = call { i4, i1 } @llvm.[us]mul.with.overflow.i4(i4 %X, i4 %???)
+  ///   %V = extractvalue { i4, i1 } %Agg, 1
+  auto matchMulOverflowCheck = [X, &II, &XIdx](Value *V) {
+    auto *Extract = dyn_cast<ExtractValueInst>(V);
+    // We should only be extracting the overflow bit.
+    if (!Extract || !Extract->getIndices().equals(1))
+      return false;
+
+    II = dyn_cast<IntrinsicInst>(Extract->getAggregateOperand());
+    if (!match(II, m_CombineOr(m_Intrinsic<Intrinsic::umul_with_overflow>(),
+                               m_Intrinsic<Intrinsic::smul_with_overflow>())))
+      return false;
+
+    if (II->getArgOperand(0) == X)
+      XIdx = 0;
+    else if (II->getArgOperand(1) == X)
+      XIdx = 1;
+    else
+      return false;
+    return true;
+  };
+
+  bool Matched = (IsAnd && Pred == ICmpInst::Predicate::ICMP_NE &&
+        matchMulOverflowCheck(Op1)) ||
+      (!IsAnd && Pred == ICmpInst::Predicate::ICMP_EQ &&
+        match(Op1, m_Not(m_Value(NotOp1))) &&
+        matchMulOverflowCheck(NotOp1));
+
+  if (!Matched)
+    return false;
+
+  Y = &II->getArgOperandUse(!XIdx);
+  return true;
+}
+
+bool llvm::isCheckForZeroAndMulWithOverflow(Value *Op0, Value *Op1, bool IsAnd) {
+  Use *Y;
+  return isCheckForZeroAndMulWithOverflow(Op0, Op1, IsAnd, Y);
+}
 No newline at end of file

llvm/lib/Analysis/ValueTracking.cpp

 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (const auto *I = dyn_cast<Instruction>(V)) {
     if (const auto *SI = dyn_cast<SelectInst>(I))
       return directlyImpliesPoison(ValAssumedPoison, SI->getCondition(),
                                    Depth + 1);
     // V  = extractvalue V0, idx
     // V2 = extractvalue V0, idx2
     // V0's elements are all poison or not. (e.g., add_with_overflow)
     const WithOverflowInst *II;
     if (match(I, m_ExtractValue(m_WithOverflowInst(II))) &&
-        match(ValAssumedPoison, m_ExtractValue(m_Specific(II))))
+        (match(ValAssumedPoison, m_ExtractValue(m_Specific(II))) ||
+         llvm::find(II->arg_operands(), ValAssumedPoison) != II->arg_end()))
       return true;
   }
   return false;
 }
 
 static bool impliesPoison(const Value *ValAssumedPoison, const Value *V,
                           unsigned Depth) {
   if (isGuaranteedNotToBeUndefOrPoison(ValAssumedPoison))

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

 //===- InstCombineSelect.cpp ----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visitSelect function.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CmpInstAnalysis.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Analysis/OverflowInstAnalysis.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
static Value *foldSelectWithFrozenICmp(SelectInst &Sel, InstCombiner::BuilderTy &Builder) {
   if (FI->hasOneUse() &&
       match(Cond, m_c_ICmp(Pred, m_Specific(TrueVal), m_Specific(FalseVal))) &&
       (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)) {
     return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
   }
 
   return nullptr;
 }
 
 Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) {
   Value *CondVal = SI.getCondition();
   Value *TrueVal = SI.getTrueValue();
   Value *FalseVal = SI.getFalseValue();
   Type *SelType = SI.getType();
 
   // FIXME: Remove this workaround when freeze related patches are done.
   // For select with undef operand which feeds into an equality comparison,
if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
       return replaceOperand(SI, 0, A);
 
     if (Value *S = SimplifyWithOpReplaced(TrueVal, CondVal, One, SQ,
                                           /* AllowRefinement */ true))
       return replaceOperand(SI, 1, S);
     if (Value *S = SimplifyWithOpReplaced(FalseVal, CondVal, Zero, SQ,
                                           /* AllowRefinement */ true))
       return replaceOperand(SI, 2, S);
+
+    if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {
+      Use *Y = nullptr;
+      bool IsAnd = match(FalseVal, m_Zero()) ? true : false;
+      Value *Op1 = IsAnd ? TrueVal : FalseVal;
+      if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {
+        auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
+        InsertNewInstBefore(FI, *cast<Instruction>(Y->getUser()));
+        replaceUse(*Y, FI);
+        return replaceInstUsesWith(SI, Op1);
+      }
+    }
   }
 
   // Selecting between two integer or vector splat integer constants?
   //
   // Note that we don't handle a scalar select of vectors:
   // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
   // because that may need 3 instructions to splat the condition value:
   // extend, insertelement, shufflevector.

llvm/test/Transforms/InstCombine/div-by-0-guard-before-smul_ov-not.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S -instcombine-unsafe-select-transform=0 | FileCheck %s
 
 declare { i4, i1 } @llvm.smul.with.overflow.i4(i4, i4) #1
 
 define i1 @t0_umul(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @t0_umul(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i4 [[SIZE:%.*]], 0
-; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
+; CHECK-NEXT:    [[NMEMB_FR:%.*]] = freeze i4 [[NMEMB:%.*]]
+; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE:%.*]], i4 [[NMEMB_FR]])
 ; CHECK-NEXT:    [[SMUL_OV:%.*]] = extractvalue { i4, i1 } [[SMUL]], 1
 ; CHECK-NEXT:    [[PHITMP:%.*]] = xor i1 [[SMUL_OV]], true
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[CMP]], i1 true, i1 [[PHITMP]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    ret i1 [[PHITMP]]
 ;
   %cmp = icmp eq i4 %size, 0
   %smul = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 %size, i4 %nmemb)
   %smul.ov = extractvalue { i4, i1 } %smul, 1
   %phitmp = xor i1 %smul.ov, true
   %or = select i1 %cmp, i1 true, i1 %phitmp
   ret i1 %or
 }
 
 define i1 @t1_commutative(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @t1_commutative(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i4 [[SIZE:%.*]], 0
-; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
+; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE:%.*]], i4 [[NMEMB:%.*]])
 ; CHECK-NEXT:    [[SMUL_OV:%.*]] = extractvalue { i4, i1 } [[SMUL]], 1
 ; CHECK-NEXT:    [[PHITMP:%.*]] = xor i1 [[SMUL_OV]], true
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[PHITMP]], i1 true, i1 [[CMP]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    ret i1 [[PHITMP]]
 ;
   %cmp = icmp eq i4 %size, 0
   %smul = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 %size, i4 %nmemb)
   %smul.ov = extractvalue { i4, i1 } %smul, 1
   %phitmp = xor i1 %smul.ov, true
   %or = select i1 %phitmp, i1 true, i1 %cmp ; swapped
   ret i1 %or
 }

llvm/test/Transforms/InstCombine/div-by-0-guard-before-smul_ov.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S -instcombine-unsafe-select-transform=0 | FileCheck %s
 
 declare { i4, i1 } @llvm.smul.with.overflow.i4(i4, i4) #1
 
 define i1 @t0_smul(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @t0_smul(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i4 [[SIZE:%.*]], 0
-; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
+; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE:%.*]], i4 [[NMEMB:%.*]])
 ; CHECK-NEXT:    [[SMUL_OV:%.*]] = extractvalue { i4, i1 } [[SMUL]], 1
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[SMUL_OV]], i1 [[CMP]], i1 false
-; CHECK-NEXT:    ret i1 [[AND]]
+; CHECK-NEXT:    ret i1 [[SMUL_OV]]
 ;
   %cmp = icmp ne i4 %size, 0
   %smul = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 %size, i4 %nmemb)
   %smul.ov = extractvalue { i4, i1 } %smul, 1
   %and = select i1 %smul.ov, i1 %cmp, i1 false
   ret i1 %and
 }
 
 define i1 @t1_commutative(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @t1_commutative(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i4 [[SIZE:%.*]], 0
-; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
+; CHECK-NEXT:    [[NMEMB_FR:%.*]] = freeze i4 [[NMEMB:%.*]]
+; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE:%.*]], i4 [[NMEMB_FR]])
 ; CHECK-NEXT:    [[SMUL_OV:%.*]] = extractvalue { i4, i1 } [[SMUL]], 1
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[CMP]], i1 [[SMUL_OV]], i1 false
-; CHECK-NEXT:    ret i1 [[AND]]
+; CHECK-NEXT:    ret i1 [[SMUL_OV]]
 ;
   %cmp = icmp ne i4 %size, 0
   %smul = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 %size, i4 %nmemb)
   %smul.ov = extractvalue { i4, i1 } %smul, 1
   %and = select i1 %cmp, i1 %smul.ov, i1 false ; swapped
   ret i1 %and
 }
 
;
   ret i1 %and
 }
 
 define i1 @n3_wrong_pred(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @n3_wrong_pred(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i4 [[SIZE:%.*]], 0
 ; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
 ; CHECK-NEXT:    [[SMUL_OV:%.*]] = extractvalue { i4, i1 } [[SMUL]], 1
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[SMUL_OV]], i1 [[CMP]], i1 false
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[SMUL_OV]], [[CMP]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %cmp = icmp eq i4 %size, 0 ; not 'ne'
   %smul = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 %size, i4 %nmemb)
   %smul.ov = extractvalue { i4, i1 } %smul, 1
   %and = select i1 %smul.ov, i1 %cmp, i1 false
   ret i1 %and
 }
 
 define i1 @n4_not_and(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @n4_not_and(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i4 [[SIZE:%.*]], 0
 ; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
 ; CHECK-NEXT:    [[SMUL_OV:%.*]] = extractvalue { i4, i1 } [[SMUL]], 1
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[SMUL_OV]], i1 true, i1 [[CMP]]
+; CHECK-NEXT:    [[AND:%.*]] = or i1 [[SMUL_OV]], [[CMP]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %cmp = icmp ne i4 %size, 0
   %smul = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 %size, i4 %nmemb)
   %smul.ov = extractvalue { i4, i1 } %smul, 1
   %and = select i1 %smul.ov, i1 true, i1 %cmp ; not 'and'
   ret i1 %and
 }
 
 define i1 @n5_not_zero(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @n5_not_zero(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i4 [[SIZE:%.*]], 1
 ; CHECK-NEXT:    [[SMUL:%.*]] = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
 ; CHECK-NEXT:    [[SMUL_OV:%.*]] = extractvalue { i4, i1 } [[SMUL]], 1
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[SMUL_OV]], i1 [[CMP]], i1 false
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[SMUL_OV]], [[CMP]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %cmp = icmp ne i4 %size, 1 ; should be '0'
   %smul = tail call { i4, i1 } @llvm.smul.with.overflow.i4(i4 %size, i4 %nmemb)
   %smul.ov = extractvalue { i4, i1 } %smul, 1
   %and = select i1 %smul.ov, i1 %cmp, i1 false
   ret i1 %and
 }

llvm/test/Transforms/InstCombine/div-by-0-guard-before-umul_ov-not.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S -instcombine-unsafe-select-transform=0 | FileCheck %s
 
 declare { i4, i1 } @llvm.umul.with.overflow.i4(i4, i4) #1
 
 define i1 @t0_umul(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @t0_umul(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i4 [[SIZE:%.*]], 0
-; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
+; CHECK-NEXT:    [[NMEMB_FR:%.*]] = freeze i4 [[NMEMB:%.*]]
+; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE:%.*]], i4 [[NMEMB_FR]])
 ; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i4, i1 } [[UMUL]], 1
 ; CHECK-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[CMP]], i1 true, i1 [[PHITMP]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    ret i1 [[PHITMP]]
 ;
   %cmp = icmp eq i4 %size, 0
   %umul = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 %size, i4 %nmemb)
   %umul.ov = extractvalue { i4, i1 } %umul, 1
   %phitmp = xor i1 %umul.ov, true
   %or = select i1 %cmp, i1 true, i1 %phitmp
   ret i1 %or
 }
 
 define i1 @t1_commutative(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @t1_commutative(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i4 [[SIZE:%.*]], 0
-; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
+; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE:%.*]], i4 [[NMEMB:%.*]])
 ; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i4, i1 } [[UMUL]], 1
 ; CHECK-NEXT:    [[PHITMP:%.*]] = xor i1 [[UMUL_OV]], true
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[PHITMP]], i1 true, i1 [[CMP]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    ret i1 [[PHITMP]]
 ;
   %cmp = icmp eq i4 %size, 0
   %umul = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 %size, i4 %nmemb)
   %umul.ov = extractvalue { i4, i1 } %umul, 1
   %phitmp = xor i1 %umul.ov, true
   %or = select i1 %phitmp, i1 true, i1 %cmp ; swapped
   ret i1 %or
 }

llvm/test/Transforms/InstCombine/div-by-0-guard-before-umul_ov.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S -instcombine-unsafe-select-transform=0 | FileCheck %s
 
 declare { i4, i1 } @llvm.umul.with.overflow.i4(i4, i4) #1
 
 define i1 @t0_umul(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @t0_umul(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i4 [[SIZE:%.*]], 0
-; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
+; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE:%.*]], i4 [[NMEMB:%.*]])
 ; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i4, i1 } [[UMUL]], 1
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[UMUL_OV]], i1 [[CMP]], i1 false
-; CHECK-NEXT:    ret i1 [[AND]]
+; CHECK-NEXT:    ret i1 [[UMUL_OV]]
 ;
   %cmp = icmp ne i4 %size, 0
   %umul = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 %size, i4 %nmemb)
   %umul.ov = extractvalue { i4, i1 } %umul, 1
   %and = select i1 %umul.ov, i1 %cmp, i1 false
   ret i1 %and
 }
 
 define i1 @t1_commutative(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @t1_commutative(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i4 [[SIZE:%.*]], 0
-; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
+; CHECK-NEXT:    [[NMEMB_FR:%.*]] = freeze i4 [[NMEMB:%.*]]
+; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE:%.*]], i4 [[NMEMB_FR]])
 ; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i4, i1 } [[UMUL]], 1
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[CMP]], i1 [[UMUL_OV]], i1 false
-; CHECK-NEXT:    ret i1 [[AND]]
+; CHECK-NEXT:    ret i1 [[UMUL_OV]]
 ;
   %cmp = icmp ne i4 %size, 0
   %umul = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 %size, i4 %nmemb)
   %umul.ov = extractvalue { i4, i1 } %umul, 1
   %and = select i1 %cmp, i1 %umul.ov, i1 false ; swapped
   ret i1 %and
 }
 
;
   ret i1 %and
 }
 
 define i1 @n3_wrong_pred(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @n3_wrong_pred(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i4 [[SIZE:%.*]], 0
 ; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
 ; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i4, i1 } [[UMUL]], 1
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[UMUL_OV]], i1 [[CMP]], i1 false
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[UMUL_OV]], [[CMP]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %cmp = icmp eq i4 %size, 0 ; not 'ne'
   %umul = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 %size, i4 %nmemb)
   %umul.ov = extractvalue { i4, i1 } %umul, 1
   %and = select i1 %umul.ov, i1 %cmp, i1 false
   ret i1 %and
 }
 
 define i1 @n4_not_and(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @n4_not_and(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i4 [[SIZE:%.*]], 0
 ; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
 ; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i4, i1 } [[UMUL]], 1
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[UMUL_OV]], i1 true, i1 [[CMP]]
+; CHECK-NEXT:    [[AND:%.*]] = or i1 [[UMUL_OV]], [[CMP]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %cmp = icmp ne i4 %size, 0
   %umul = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 %size, i4 %nmemb)
   %umul.ov = extractvalue { i4, i1 } %umul, 1
   %and = select i1 %umul.ov, i1 true, i1 %cmp ; not 'and'
   ret i1 %and
 }
 
 define i1 @n5_not_zero(i4 %size, i4 %nmemb) {
 ; CHECK-LABEL: @n5_not_zero(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i4 [[SIZE:%.*]], 1
 ; CHECK-NEXT:    [[UMUL:%.*]] = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 [[SIZE]], i4 [[NMEMB:%.*]])
 ; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i4, i1 } [[UMUL]], 1
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[UMUL_OV]], i1 [[CMP]], i1 false
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[UMUL_OV]], [[CMP]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %cmp = icmp ne i4 %size, 1 ; should be '0'
   %umul = tail call { i4, i1 } @llvm.umul.with.overflow.i4(i4 %size, i4 %nmemb)
   %umul.ov = extractvalue { i4, i1 } %umul, 1
   %and = select i1 %umul.ov, i1 %cmp, i1 false
   ret i1 %and
 }