[InstCombine] More aggressively try and fold irem/idiv/mul into selects.

[goldstein.w.n]

Summary

Don't only do constant cases, also try cases were we can't constant
fold both sides. In the same we can't constant fold both sides, only
do transform if the select is single use.

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[nikic]

This is not generally legal for div/rem, see https://alive2.llvm.org/ce/z/2iiR26 using one of your tests. This is only legal if the operation is speculatable.

[goldstein.w.n]

In D146350#4204295, @nikic wrote:

This is not generally legal for div/rem, see https://alive2.llvm.org/ce/z/2iiR26 using one of your tests. This is only legal if the operation is speculatable.

Is there a flag for speculatable?

[nikic]

In D146350#4222729, @goldstein.w.n wrote:

In D146350#4204295, @nikic wrote:

This is not generally legal for div/rem, see https://alive2.llvm.org/ce/z/2iiR26 using one of your tests. This is only legal if the operation is speculatable.

Is there a flag for speculatable?

There is isSafeToSpeculativelyExecute().

[nikic]

Err, I probably misunderstood the question: There are no div/rem variants that are always speculatable, we can only speculate them if we know that the divisor is non-zero (or the more complex conditions for the signed case are met).

[goldstein.w.n]

Only do rem/div if denominator known non zero

[goldstein.w.n]

In D146350#4232936, @nikic wrote:

Err, I probably misunderstood the question: There are no div/rem variants that are always speculatable, we can only speculate them if we know that the divisor is non-zero (or the more complex conditions for the signed case are met).

Done + test cases for it (*fail_no_speculation).

[goldstein.w.n]

Rebase

[goldstein.w.n]

ping.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

191

Comment that it returns MultiUse.

193

Matching against all-wildcards is a bit silly :)

1011

Please use isSafeToSpeculativelyExecute() here. This check is not sufficient for sdiv (due to INT_MIN / -1), and we don't want to duplicate logic.

1840

Same here.

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

642–667

Also test the straightforward case where the mul has a constant operand? Or is that already handled somewhere else (and if so, can we remove it)?

[goldstein.w.n]

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

642–667

hmm? Not sure what you mean by this comment.

[goldstein.w.n]

Use isSafeToSpeculate to check if allows on non-imm operands

[nikic]

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

642–667

I mean something like (c ? x : C1) * C2, that isn't based on the select condition.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

206

Is this code in here so the case where the div is always folded away is always handled, as we're at worst going to relax to poison there and not introduce UB?

If so, I think it might be more elegant to sink this check into FoldOpIntoSelect and use the isSafeToSpeculativelyExecute variant that accepts operands, so we can check the operation that we're actually going to introduce (and thus also skip the check if we're not going to introduce one).

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

206

and use the isSafeToSpeculativelyExecute variant that accepts operands

Well, it looks like I imagined that variant... So ignore that bit (or leave a TODO for possible future improvement) and just take the bit about only checking it if we're going to introduce an op.

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1834–1838

Updatr comment?

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

206

Without that variant we end up with regressions in:

LLVM :: Transforms/InstCombine/div.ll
LLVM :: Transforms/InstCombine/rem.ll

I'm happy to just add the variant and use that, but I'm not sure what to do with load/call instructions.
Maybe just return false in those cases as they aren't really needed here?

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

206

There are regressions either way. Would prefer to keep it this way if thats okay with you.

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

642–667

done although unaffected by this patch.

[goldstein.w.n]

Update comments

[xbolva00]

We generally fail to call 'foldBinOpIntoSelectOrPhi' in commonIDivTransforms and commonIRemTransforms

How hard would be to add support for PHIs in your shouldFoldOp helper? (Can be followup).

[goldstein.w.n]

In D146350#4313194, @xbolva00 wrote:

We generally fail to call 'foldBinOpIntoSelectOrPhi' in commonIDivTransforms and commonIRemTransforms

How hard would be to add support for PHIs in your shouldFoldOp helper? (Can be followup).

Well we match explicitly against m_Select(...) to check the all constant case so that wouldn't apply.
The speculative execution check can be reused, however.

Personally to add PHI support I'd create a new function "shouldFoldOpIntoX(...)" then have a variant
for select/phi and base the imm match on what X is.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

206

ping @nikic, okay with as is or okay with regressions or something else?

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

206

ping2 @nikic.

[nikic]

I think this is basically okay if you drop the mul handling. As @xbolva00 pointed out (thanks, this is the bit I was missing here!) the mul case is already handled by foldBinOpIntoSelectOrPhi() and you're duplicating the transform for a special case now. If we want to extend handling to more cases, we should do so generically inside foldBinOpIntoSelectOrPhi(), not by repeating the transform with different arguments.

[goldstein.w.n]

In D146350#4359337, @nikic wrote:

I think this is basically okay if you drop the mul handling. As @xbolva00 pointed out (thanks, this is the bit I was missing here!) the mul case is already handled by foldBinOpIntoSelectOrPhi() and you're duplicating the transform for a special case now. If we want to extend handling to more cases, we should do so generically inside foldBinOpIntoSelectOrPhi(), not by repeating the transform with different arguments.

Ah, I had misunderstood his comment. I can move all the logics for div/mul/rem/etc.. into foldBinOpInstoSelectOrPhi. We actually call it for udiv as well (with really weak speculative checks).

[goldstein.w.n]

Move all new logic into foldBinOpIntoSelectOrPhi.

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase + remove issafetospeculativelyexecute patch dependency

[goldstein.w.n]

Use bespoke speculation tracking for div/rem

[goldstein.w.n]

(no rush) @nikic, I dropped the dependencies on the generic issafetospeculate... patch. Can take a look at this when you have the time.

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   /// Given an instruction with a select as one operand and a constant as the
   /// other operand, try to fold the binary operator into the select arguments.
   /// This also works for Cast instructions, which obviously do not have a
   /// second operand.
   Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
                                 bool FoldWithMultiUse = false);
 
   /// This is a convenience wrapper function for the above two functions.
-  Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
+  Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I, bool SelectOnly=false);
 
   Instruction *foldAddWithConstant(BinaryOperator &Add);
 
   /// Try to rotate an operation below a PHI node, using PHI nodes for
   /// its operands.
   Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
   Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
   Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

static Value *foldMulShl1(BinaryOperator &Mul, bool CommuteOperands,
   }
 
   return nullptr;
 }
 
 static Value *takeLog2(IRBuilderBase &Builder, Value *Op, unsigned Depth,
                        bool AssumeNonZero, bool DoFold);
 
 Instruction *InstCombinerImpl::visitMul(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   if (Value *V =
           simplifyMulInst(Op0, Op1, I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
                           SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
   if (SimplifyAssociativeOrCommutative(I))
     return &I;
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
   if (Instruction *Phi = foldBinopWithPhiOperands(I))
     return Phi;
 
   if (Value *V = foldUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   Type *Ty = I.getType();
   const unsigned BitWidth = Ty->getScalarSizeInBits();
   const bool HasNSW = I.hasNoSignedWrap();
   const bool HasNUW = I.hasNoUnsignedWrap();
 
Instruction *InstCombinerImpl::commonIDivTransforms(BinaryOperator &I) {
   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
     return replaceOperand(I, 1, V);
 
   // Handle cases involving: [su]div X, (select Cond, Y, Z)
   // This does not apply for fdiv.
   if (simplifyDivRemOfSelectWithZeroOp(I))
     return &I;
 
-  // If the divisor is a select-of-constants, try to constant fold all div ops:
-  // C / (select Cond, TrueC, FalseC) --> select Cond, (C / TrueC), (C / FalseC)
+  const APInt *C2;
+
+  // Try to fold the `div` into select/phi nodes. For select we proceed if we
+  // will be able to do some degree of constant foldings. This doesn't require
+  // constant operands as `foldBinOpIntoSelectOrPhi` will use the dominating
+  // select condition to deduce constants in the context of the select inst.
+  // Only try to fold with phi nodes if we have constant non-zero denominator.
   // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
-  if (match(Op0, m_ImmConstant()) &&
-      match(Op1, m_Select(m_Value(), m_ImmConstant(), m_ImmConstant()))) {
-    if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1),
-                                          /*FoldWithMultiUse*/ true))
-      return R;
-  }
+  if (Instruction *R =
+      foldBinOpIntoSelectOrPhi(I, /*SelectOnly*/!match(Op1, m_APInt(C2)) || C2->isZero()))
 
-  const APInt *C2;
   if (match(Op1, m_APInt(C2))) {
     Value *X;
     const APInt *C1;
 
     // (X / C1) / C2  -> X / (C1*C2)
     if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) ||
         (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) {
       APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
if (IsSigned &&
       return BinaryOperator::CreateNSWAdd(X, ConstantInt::get(Ty, Quotient));
     }
     if (!IsSigned &&
         match(Op0, m_NUWAdd(m_NUWMul(m_Value(X), m_SpecificInt(*C2)),
                             m_APInt(C1)))) {
       return BinaryOperator::CreateNUWAdd(X,
                                           ConstantInt::get(Ty, C1->udiv(*C2)));
     }
-
-    if (!C2->isZero()) // avoid X udiv 0
-      if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
-        return FoldedDiv;
   }
 
   if (match(Op0, m_One())) {
     assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
     if (IsSigned) {
       // 1 / 0 --> undef ; 1 / 1 --> 1 ; 1 / -1 --> -1 ; 1 / anything else --> 0
       // (Op1 + 1) u< 3 ? Op1 : 0
       // Op1 must be frozen because we are increasing its number of uses.
Instruction *InstCombinerImpl::commonIRemTransforms(BinaryOperator &I) {
   // The RHS is known non-zero.
   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
     return replaceOperand(I, 1, V);
 
   // Handle cases involving: rem X, (select Cond, Y, Z)
   if (simplifyDivRemOfSelectWithZeroOp(I))
     return &I;
 
-  // If the divisor is a select-of-constants, try to constant fold all rem ops:
-  // C % (select Cond, TrueC, FalseC) --> select Cond, (C % TrueC), (C % FalseC)
+  // Try to fold the `div` into select nodes. For select we proceed if we
+  // will be able to do some degree of constant foldings. This doesn't require
+  // constant operands as `foldBinOpIntoSelectOrPhi` will use the dominating
+  // select condition to deduce constants in the context of the select inst.
+  // Only try to fold with phi nodes if we have constant non-zero denominator.
   // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
-  if (match(Op0, m_ImmConstant()) &&
-      match(Op1, m_Select(m_Value(), m_ImmConstant(), m_ImmConstant()))) {
-    if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1),
-                                          /*FoldWithMultiUse*/ true))
-      return R;
-  }
+  if (Instruction *R = foldBinOpIntoSelectOrPhi(I, /*SelectOnly*/ true))
 
   if (isa<Constant>(Op1)) {
     if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
       if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
         if (Instruction *R = FoldOpIntoSelect(I, SI))
           return R;
       } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
         const APInt *Op1Int;

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Instruction *InstCombinerImpl::foldBinopWithPhiOperands(BinaryOperator &BO) {
 
   // Replace the binop with a phi of the new values. The old phis are dead.
   PHINode *NewPhi = PHINode::Create(BO.getType(), 2);
   NewPhi->addIncoming(NewBO, OtherBB);
   NewPhi->addIncoming(NewC, ConstBB);
   return NewPhi;
 }
 
-Instruction *InstCombinerImpl::foldBinOpIntoSelectOrPhi(BinaryOperator &I) {
-  if (!isa<Constant>(I.getOperand(1)))
-    return nullptr;
+// Return std::nullopt if we should not fold. Return true if we should fold
+// multi-use select and false for single-use select.
+static std::optional<bool> shouldFoldOpIntoSelect(BinaryOperator &I, Value *Op,
+                                                  Value *OpOther) {
+  if (isa<SelectInst>(Op))
+    // If we will be able to constant fold the incorperated binop, then
+    // multi-use. Otherwise single-use.
+    return match(OpOther, m_ImmConstant()) &&
+           match(Op, m_Select(m_Value(), m_ImmConstant(), m_ImmConstant()));
+
+  return std::nullopt;
+}
+
+Instruction *InstCombinerImpl::foldBinOpIntoSelectOrPhi(BinaryOperator &I,
+                                                        bool SelectOnly) {
+
+  std::optional<bool> CanSpeculativelyExecuteRes;
+  auto CanSpeculativelyExecute = [&]() -> bool {
+    if (!CanSpeculativelyExecuteRes) {
+      const SimplifyQuery Q = SQ.getWithInstruction(&I);
+      CanSpeculativelyExecuteRes =
+          isSafeToSpeculativelyExecute(&I, Q.CxtI, Q.AC, Q.DT, &TLI);
+      // isSafeToSpeculativelyExecute doesn't look through knownbits to see if
+      // div/rem are speculatable. This is non-trivial to generically implement
+      // in isSafeToSpeculativelyExecute as some of its users expect to be able
+      // to perform transformations that invalidate the knownbits analysis and
+      // maintain the isSafeToSpeculativelyExecute property. So for now,
+      // implement knownbits checks here.
+      // TODO: If isSafeToSpeculativelyExecute is updated to use knownbits
+      // analysis for div/rem remove this code.
+      if (!(*CanSpeculativelyExecuteRes)) {
+        if (!isGuaranteedNotToBePoison(I.getOperand(1), Q.AC, Q.CxtI, Q.DT))
+          return false;
+        switch (I.getOpcode()) {
+        case Instruction::UDiv:
+        case Instruction::URem:
+          // Unsigned is safe as long as denominator is non-poison and non-zero.
+          CanSpeculativelyExecuteRes = isKnownNonZero(
+              I.getOperand(1), DL, /*Depth*/ 0, Q.AC, Q.CxtI, Q.DT);
+          break;
+        case Instruction::SDiv:
+        case Instruction::SRem: {
+          KnownBits KnownDenom = llvm::computeKnownBits(
+              I.getOperand(1), DL, /*Depth*/ 0, Q.AC, Q.CxtI, Q.DT);
+          if (!(KnownDenom.isNonZero() ||
+                isKnownNonZero(I.getOperand(1), DL, /*Depth*/ 0, Q.AC, Q.CxtI,
+                               Q.DT)))
+            return false;
+
+          KnownBits KnownNum = llvm::computeKnownBits(
+              I.getOperand(0), DL, /*Depth*/ 0, Q.AC, Q.CxtI, Q.DT);
+          // Signed is safe if either denominator is (non-poison and non-zero)
+          // OR (denominator != -1 or numerator is non-poison and numerator !=
+          // INT_MIN).
+          CanSpeculativelyExecuteRes =
+              !KnownDenom.getMaxValue().isAllOnes() ||
+              (isGuaranteedNotToBePoison(I.getOperand(0), Q.AC, Q.CxtI, Q.DT) &&
+               KnownNum.getSignedMinValue().isMinSignedValue());
+        } break;
+        default:
+          break;
+        }
+      }
+    }
+    return *CanSpeculativelyExecuteRes;
+  };
 
-  if (auto *Sel = dyn_cast<SelectInst>(I.getOperand(0))) {
-    if (Instruction *NewSel = FoldOpIntoSelect(I, Sel))
+  for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx) {
+    // Slightly more involved logic for select. For select we use the condition
+    // to to infer information about the arm. This allows us to constant-fold
+    // even when the select arm(s) are not constant. For example if we have: `(X
+    // == 10 ? 19 : Y) * X`, we can entirely contant fold the true arm as `X ==
+    // 10` dominates it. So we end up with `X == 10 ? 190 : (X * Y))`.
+    if (auto MultiUse = shouldFoldOpIntoSelect(I, I.getOperand(OpIdx),
+                                               I.getOperand(1 - OpIdx))) {
+      if (*MultiUse || CanSpeculativelyExecute())
+        if (Instruction *NewSel = FoldOpIntoSelect(
+                I, cast<SelectInst>(I.getOperand(OpIdx)), *MultiUse))
           return NewSel;
-  } else if (auto *PN = dyn_cast<PHINode>(I.getOperand(0))) {
+    }
+  }
+
+  if (!isa<Constant>(I.getOperand(1)) || SelectOnly)
+    return nullptr;
+
+  if (auto *PN = dyn_cast<PHINode>(I.getOperand(0))) {
     if (Instruction *NewPhi = foldOpIntoPhi(I, PN))
       return NewPhi;
   }
   return nullptr;
 }
 
 static bool shouldMergeGEPs(GEPOperator &GEP, GEPOperator &Src) {
   // If this GEP has only 0 indices, it is the same pointer as

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

;
   %r = and i32 %s, 1
   ret i32 %r
 }
 
 define i32 @and_sel_op0_use(i1 %b) {
 ; CHECK-LABEL: @and_sel_op0_use(
 ; CHECK-NEXT:    [[S:%.*]] = select i1 [[B:%.*]], i32 25, i32 0
 ; CHECK-NEXT:    call void @use(i32 [[S]])
-; CHECK-NEXT:    [[R:%.*]] = and i32 [[S]], 1
+; CHECK-NEXT:    [[R:%.*]] = zext i1 [[B]] to i32
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %s = select i1 %b, i32 25, i32 0
   call void @use(i32 %s)
   %r = and i32 %s, 1
   ret i32 %r
 }
 
;
   %s = select i1 %b, i32 2, i32 0
   call void @use(i32 %s)
   %r = ashr i32 -2, %s
   ret i32 %r
 }
 
 define <2 x i32> @test_udiv_to_const_shr(i1 %c, <2 x i32> %x, <2 x i32> %yy) {
 ; CHECK-LABEL: @test_udiv_to_const_shr(
-; CHECK-NEXT:    [[Y:%.*]] = shl nuw <2 x i32> <i32 1, i32 1>, [[YY:%.*]]
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[C:%.*]], <2 x i32> <i32 7, i32 8>, <2 x i32> [[Y]]
-; CHECK-NEXT:    [[DIV:%.*]] = udiv <2 x i32> <i32 42, i32 42>, [[COND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i32> <i32 42, i32 42>, [[YY:%.*]]
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C:%.*]], <2 x i32> <i32 6, i32 5>, <2 x i32> [[TMP1]]
 ; CHECK-NEXT:    ret <2 x i32> [[DIV]]
 ;
   %y = shl <2 x i32> <i32 1, i32 1>, %yy
   %cond = select i1 %c, <2 x i32> <i32 7, i32 8>, <2 x i32> %y
   %div = udiv <2 x i32> <i32 42, i32 42>, %cond
   ret <2 x i32> %div
 }
 
;
   %div = udiv i32 42, %cond
   call void @use(i32 %cond)
   ret i32 %div
 }
 
 define i32 @test_udiv_to_const_Cudiv(i32 %x) {
 ; CHECK-LABEL: @test_udiv_to_const_Cudiv(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], 90
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[C]], i32 7, i32 19
-; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[X]], [[COND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[X]], 19
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C]], i32 12, i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %c = icmp eq i32 %x, 90
   %cond = select i1 %c, i32 7, i32 19
   %div = udiv i32 %x, %cond
   ret i32 %div
 }
 
;
   ret i32 %div
 }
 
 define i32 @test_udiv_partial_const(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test_udiv_partial_const(
 ; CHECK-NEXT:    [[YNZ:%.*]] = icmp ne i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[YNZ]])
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], 90
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[C]], i32 19, i32 [[Y]]
-; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[X]], [[COND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C]], i32 4, i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %ynz = icmp ne i32 %y, 0
   call void @llvm.assume(i1 %ynz)
   %c = icmp eq i32 %x, 90
   %cond = select i1 %c, i32 19, i32 %y
   %div = udiv i32 %x, %cond
   ret i32 %div
;
   %cond = select i1 %c, i32 7, i32 19
   %div = udiv i32 %x, %cond
   ret i32 %div
 }
 
 define <2 x i32> @test_sdiv_to_const_Csdiv(<2 x i32> %x) {
 ; CHECK-LABEL: @test_sdiv_to_const_Csdiv(
 ; CHECK-NEXT:    [[C_NOT:%.*]] = icmp eq <2 x i32> [[X:%.*]], <i32 89, i32 91>
-; CHECK-NEXT:    [[COND:%.*]] = select <2 x i1> [[C_NOT]], <2 x i32> <i32 17, i32 5>, <2 x i32> <i32 7, i32 9>
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv <2 x i32> [[X]], [[COND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sdiv <2 x i32> [[X]], <i32 7, i32 9>
+; CHECK-NEXT:    [[DIV:%.*]] = select <2 x i1> [[C_NOT]], <2 x i32> <i32 5, i32 18>, <2 x i32> [[TMP1]]
 ; CHECK-NEXT:    ret <2 x i32> [[DIV]]
 ;
   %c = icmp ne <2 x i32> %x, <i32 89, i32 91>
   %cond = select <2 x i1> %c, <2 x i32> <i32 7, i32 9>, <2 x i32> <i32 17, i32 5>
   %div = sdiv <2 x i32> %x, %cond
   ret <2 x i32> %div
 }
 
 define <2 x i32> @test_sdiv_to_const_Csdiv_todo_no_common_bit(<2 x i32> %x) {
 ; CHECK-LABEL: @test_sdiv_to_const_Csdiv_todo_no_common_bit(
 ; CHECK-NEXT:    [[C_NOT:%.*]] = icmp eq <2 x i32> [[X:%.*]], <i32 90, i32 91>
-; CHECK-NEXT:    [[COND:%.*]] = select <2 x i1> [[C_NOT]], <2 x i32> <i32 16, i32 4>, <2 x i32> <i32 7, i32 9>
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv <2 x i32> [[X]], [[COND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sdiv <2 x i32> [[X]], <i32 7, i32 9>
+; CHECK-NEXT:    [[DIV:%.*]] = select <2 x i1> [[C_NOT]], <2 x i32> <i32 5, i32 22>, <2 x i32> [[TMP1]]
 ; CHECK-NEXT:    ret <2 x i32> [[DIV]]
 ;
   %c = icmp ne <2 x i32> %x, <i32 90, i32 91>
   %cond = select <2 x i1> %c, <2 x i32> <i32 7, i32 9>, <2 x i32> <i32 16, i32 4>
   %div = sdiv <2 x i32> %x, %cond
   ret <2 x i32> %div
 }
 
 define i32 @test_srem_to_const_Csrem(i32 %x) {
 ; CHECK-LABEL: @test_srem_to_const_Csrem(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], 24
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[C]], i32 18, i32 16
-; CHECK-NEXT:    [[DIV:%.*]] = srem i32 [[X]], [[COND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = srem i32 [[X]], 16
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C]], i32 6, i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %c = icmp eq i32 %x, 24
   %cond = select i1 %c, i32 18, i32 16
   %div = srem i32 %x, %cond
   ret i32  %div
 }
 
 define i32 @test_srem_to_const_Csrem_todo_no_common_bits(i32 %x) {
 ; CHECK-LABEL: @test_srem_to_const_Csrem_todo_no_common_bits(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], 24
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[C]], i32 7, i32 16
-; CHECK-NEXT:    [[DIV:%.*]] = srem i32 [[X]], [[COND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = srem i32 [[X]], 16
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C]], i32 3, i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %c = icmp eq i32 %x, 24
   %cond = select i1 %c, i32 7, i32 16
   %div = srem i32 %x, %cond
   ret i32  %div
 }
 
;
   %div = srem i32 %x, %cond
   call void @use(i32 %cond)
   ret i32 %div
 }
 
 define i32 @test_srem_fail_no_speculation(i32 %x) {
 ; CHECK-LABEL: @test_srem_fail_no_speculation(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], 24
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[C]], i32 7, i32 -1
-; CHECK-NEXT:    [[DIV:%.*]] = srem i32 [[X]], [[COND]]
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C]], i32 3, i32 0
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %c = icmp eq i32 %x, 24
   %cond = select i1 %c, i32 7, i32 -1
   %div = srem i32 %x, %cond
   ret i32 %div
 }
 
 
 define i32 @test_urem_to_const_and_ind_x(i32 %x, i32 %yy) {
 ; CHECK-LABEL: @test_urem_to_const_and_ind_x(
-; CHECK-NEXT:    [[Y:%.*]] = shl nuw i32 1, [[YY:%.*]]
 ; CHECK-NEXT:    [[C_NOT:%.*]] = icmp eq i32 [[X:%.*]], 24
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[C_NOT]], i32 19, i32 [[Y]]
-; CHECK-NEXT:    [[DIV:%.*]] = urem i32 [[X]], [[COND]]
+; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[YY:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[NOTMASK]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X]]
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C_NOT]], i32 5, i32 [[TMP2]]
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %y = shl i32 1, %yy
   %c = icmp ne i32 %x, 24
   %cond = select i1 %c, i32 %y, i32 19
   %div = urem i32 %x, %cond
   ret i32 %div
 }
 
 define i32 @test_urem_to_const_and(i1 %c, i32 %yy) {
 ; CHECK-LABEL: @test_urem_to_const_and(
-; CHECK-NEXT:    [[Y:%.*]] = shl nuw i32 1, [[YY:%.*]]
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[C:%.*]], i32 [[Y]], i32 19
-; CHECK-NEXT:    [[DIV:%.*]] = urem i32 44, [[COND]]
+; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[YY:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[NOTMASK]], 44
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 44
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C:%.*]], i32 [[TMP2]], i32 6
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %y = shl i32 1, %yy
   %cond = select i1 %c, i32 %y, i32 19
   %div = urem i32 44, %cond
   ret i32 %div
 }
 
 define i32 @test_urem_to_const_and_fail_no_speculation(i1 %c, i32 %yy) {
 ; CHECK-LABEL: @test_urem_to_const_and_fail_no_speculation(
 ; CHECK-NEXT:    [[Y:%.*]] = shl i32 2, [[YY:%.*]]
 ; CHECK-NEXT:    [[COND:%.*]] = select i1 [[C:%.*]], i32 [[Y]], i32 19
 ; CHECK-NEXT:    [[DIV:%.*]] = urem i32 44, [[COND]]
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %y = shl i32 2, %yy
   %cond = select i1 %c, i32 %y, i32 19
   %div = urem i32 44, %cond
   ret i32 %div
 }
 
 define i32 @test_mul_to_const_Cmul(i32 %x) {
 ; CHECK-LABEL: @test_mul_to_const_Cmul(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], 61
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[C]], i32 9, i32 14
-; CHECK-NEXT:    [[DIV:%.*]] = mul i32 [[COND]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[X]], 14
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C]], i32 549, i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %c = icmp eq i32 %x, 61
   %cond = select i1 %c, i32 9, i32 14
   %div = mul i32 %x, %cond
   ret i32 %div
 }
 
 define i32 @test_Cmul_const_folded_in(i32 %x) {
 ; CHECK-LABEL: @test_Cmul_const_folded_in(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], 61
 ; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C]], i32 854, i32 126
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %c = icmp eq i32 %x, 61
   %cond = select i1 %c, i32 %x, i32 9
   %div = mul i32 %cond, 14
   ret i32 %div
 }
 
 define i32 @test_Cmul_expr_folded_in(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test_Cmul_expr_folded_in(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], 61
 ; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[Y:%.*]], 14
 ; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[C]], i32 [[TMP1]], i32 126
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %c = icmp eq i32 %x, 61
   %cond = select i1 %c, i32 %y, i32 9
   %div = mul i32 %cond, 14
   ret i32 %div
 }

llvm/test/Transforms/InstCombine/extractelement.ll

 ;
   %s = select <3 x i1> %c, <3 x i32> <i32 2, i32 3, i32 4>, <3 x i32> <i32 5, i32 6, i32 7>
   %r = extractelement <3 x i32> %s, i32 2
   ret i32 %r
 }
 
 define i32 @extelt_select_const_operand_extractelt_use(i1 %c) {
 ; ANY-LABEL: @extelt_select_const_operand_extractelt_use(
-; ANY-NEXT:    [[E:%.*]] = select i1 [[C:%.*]], i32 4, i32 7
-; ANY-NEXT:    [[M:%.*]] = shl nuw nsw i32 [[E]], 1
-; ANY-NEXT:    [[M_2:%.*]] = shl nuw nsw i32 [[E]], 2
-; ANY-NEXT:    [[R:%.*]] = mul nuw nsw i32 [[M]], [[M_2]]
+; ANY-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i32 128, i32 392
 ; ANY-NEXT:    ret i32 [[R]]
 ;
   %s = select i1 %c, <3 x i32> <i32 2, i32 3, i32 4>, <3 x i32> <i32 5, i32 6, i32 7>
   %e = extractelement <3 x i32> %s, i32 2
   %m = mul i32 %e, 2
   %m.2 = mul i32 %e, 4
   %r = mul i32 %m, %m.2
   ret i32 %r