[InstCombine] Fold binop of select and cast of select condition

[antoniofrighetto]

Summary

InstCombine now simplifies binary operations, whose operands involve a select instruction and a cast of the select condition, into a select with folded arguments.

Fixes #63472.

Proofs: https://alive2.llvm.org/ce/z/c_JwwM

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1496

In this case, we don't have to require that False is a constant, right?

1502

And in this case, True can be non-constant.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1492

Redundant ().

llvm/test/Transforms/InstCombine/add.ll

3066 ↗

(On Diff #535329)

Can you please add these additional tests:

• Negative test where select and zext args are not the same.
• Multi-use test.
• Vector test.

[goldstein.w.n]

Can you add alive2 link for this? I think it also works a lot more binops than just add. If so, can you split to a helper so it can be used elsewhere.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1488

I had a lot of trouble following this comment can you make say:

(select cond, (add X, 1), X)
   -> (add X, (zext cond))

then some format for sext.

[antoniofrighetto]

Added proofs, added further tests, reviewed doc-comment, and added support for uitofp/sitofp conversion as well.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1496

Correct. This is not true when handling floating point though, for which it is required that both are constants.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

947

This entire function is in desperate need of comments.
Likewise the summary (commit message) should actually explain the transform being added.

Please comment this at the very least to make review simpler :)

llvm/test/Transforms/InstCombine/binop-select-cast-of-select-cond.ll

197

Can you split the tests to a seperate commit so we can see the diff generated by this patch?

[nikic]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

917

I don't think we should support uitofp/sitofp in this fold -- this seems way too contrived. It would be okay if this fell out of some generic handling, but not something we should spend lines of code on.

[antoniofrighetto]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

917

@nikic, I do not have any strong opinions here, no problem removing them, I just thought it could make sense to support fp ops, as follows:

float fadd_select_uitofp(unsigned int a, bool b) {
    float f1 = b ? 2.0 : 1.0;
    float f2 = (float) b;
    return f1 + f2;
}

Considering that the patch is meant to support the following use case – amongst the others:

int add_select_zext(unsigned int a, bool b) {
    int f1 = b ? 2 : 1;
    int f2 = (int) b;
    return f1 + f2;
}

They seem like less than 30 LOCs to me, they should not really harm. Might be a bit contrived, but it is still valid C code.

947

Thanks for the note, apologize for that, I'm fixing it right away to introduce more comments.

llvm/test/Transforms/InstCombine/binop-select-cast-of-select-cond.ll

197

Do you mean to open a different patch for the tests (or land them directly)?

[antoniofrighetto]

Introduced further comments, dropped support at the granularity of floating point casts.

[antoniofrighetto]

Split in two separate commits (cc/ @goldstein.w.n).

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

887

I don't see why the op must the Add or Sub. AFAICT the key is that (zext C) can be treated as 1 on the true arm and 0 on the false arm so we can just constant apply (select c, (binop 1, T), (binop 0, F)) which afaict works for just about any binop. (for sext its just -1 and 0).

911

I think cleaner would be:

Constant * CastConst = IsZExt ? Constant::getOne() : Constant::getAllOnes();
return Builder.CreateBinOp(Opc, C, CastConst);

[antoniofrighetto]

Should be a bit more on track now, thanks for the suggestion! Also polished up a bit, and updated proofs. I wonder if this should be extended to sdiv/udiv and have undef in the false arm (although, admittedly, I don't see much the point).

[goldstein.w.n]

So I'm going to propose something slightly different for accomplishing this patch.
Instead of making a combine for binops, I think you can just arbitrarily
constant propagate any usage of cond to the true/false arms.

I would suggest something along the following lines (pseudo code):

if (TrueVal->hasOneUse()) {
  SmallVector<std::optional<bool>> TrueReplacements;
  bool DoReplace = false;
  for (Value *Op : TrueVal->Operands()) {
    if (Op == CondVal || match(Op, m_ZExt(m_Specific(CondVal)))) {
      TrueReplacements.emplace_back(true);
      DoReplace = true;
    } else if (match(Op, m_SExt(m_Specific(CondVal)))) {
      TrueReplacements.emplace_back(false);
      DoReplace = true;

    } else
      TrueReplacements.emplace_back(std::nullopt);
  }
  if (DoReplace) {
    SmallVector<Value *> TrueOps;
    for (unsigned I = 0; I < TrueVal->numOperands(); ++I) {
      if (TrueReplacements[I]) {
        TrueOps->emplace_back(*TrueReplacement[I] ? Constant::getOneValue(Ty)
                                                  : Constant::getAllOnes(Ty));
      } else {
              TrueOps->emplace_back(TrueVal->getOperand(I);
      }
    }
    NewTrue = Builder.Create(TrueVal->getOpcode(), TrueOps);
  }
}

For false its always replace with zero.
Maybe put this in a lambda and if you get new true/false vals
then create new instructions.

Edit:
You could probably skip the oneuse check at the top, and wait to do that check until
after you see how many non-constant operands. Its possible you will be able to entirely
constant-fold some arms inwhich case any use-count is okay.

[antoniofrighetto]

In D153963#4482931, @goldstein.w.n wrote:

So I'm going to propose something slightly different for accomplishing this patch.
Instead of making a combine for binops, I think you can just arbitrarily
constant propagate any usage of cond to the true/false arms.

I guess with TrueVal->Operands() we actually mean the (unique) user of TrueVal? I'm not exactly following how we would benefit from this, where the operands of the select are constants in most of our use cases, here's just an example:

define i64 @src(i1 %c) {
  %sel = select i1 %c, i64 64, i64 1
  %ext = zext i1 %c to i64
  %add = add i64 %sel, %ext
  ret i64 %add
}

Conversely, wouldn't the proposed change be trying to catch the following orthogonal test case?

define i64 @src(i1 %c, i64 %a, i64 %b, i64 %d) {
  %ext = zext i1 %c to i64
  %add = add i64 %a, %ext
  %sub = sub i64 %b, %ext
  %sel = select i1 %c, i64 %add, i64 %sub
  ret i64 %sel
}

Where %add and %sub may be optimized respectively with %1 = add i64 %a, 1 and %2 = sub i64 %b, 0.

[goldstein.w.n]

In D153963#4485400, @antoniofrighetto wrote:

In D153963#4482931, @goldstein.w.n wrote:

So I'm going to propose something slightly different for accomplishing this patch.
Instead of making a combine for binops, I think you can just arbitrarily
constant propagate any usage of cond to the true/false arms.

I guess with TrueVal->Operands() we actually mean the (unique) user of TrueVal? I'm not exactly following how we would benefit from this, where the operands of the select are constants in most of our use cases, here's just an example:

No I mean the actual operands. The point is the select condition can be constant propagated to instruction on the true/false arm (usually). You can't do this for instructions that are not speculatable (although same is true for binops in your current patch).

define i64 @src(i1 %c) {
  %sel = select i1 %c, i64 64, i64 1
  %ext = zext i1 %c to i64
  %add = add i64 %sel, %ext
  ret i64 %add
}

Conversely, wouldn't the proposed change be trying to catch the following orthogonal test case?

define i64 @src(i1 %c, i64 %a, i64 %b, i64 %d) {
  %ext = zext i1 %c to i64
  %add = add i64 %a, %ext
  %sub = sub i64 %b, %ext
  %sel = select i1 %c, i64 %add, i64 %sub
  ret i64 %sel
}

Where %add and %sub may be optimized respectively with %1 = add i64 %a, 1 and %2 = sub i64 %b, 0.

Yes, what I'm proposing covers this case, it just doesn't stop at binops.
Basically for any instruction that we may speculate that uses the condition (or (ext %condition))
we can just arbitrarily replace %condition with 1/0 depending if its from the true/false
arm.

So instead of matching BinOps, just take any speculatable instruction, iterate through its
operands and replace all references to %condition with the constant. Its just a more
general implementation.

[nikic]

@goldstein.w.n Where would the transform be rooted in that case?

[goldstein.w.n]

In D153963#4485677, @nikic wrote:

@goldstein.w.n Where would the transform be rooted in that case?

that case? Not sure what you are saying.

[nikic]

@goldstein.w.n The transform needs to be called from somewhere. Currently it is called for a number of binops. The same transform is indeed possible for non-binop instructions, but I'm not sure it makes sense to plaster it everywhere.

The main sensible way of doing that I can see is to extend FoldOpIntoSelect() to handle this. We could extend constantFoldOperationIntoSelectOperand() to determine the constant for zext/sext of the condition, similar to the special case for icmps it currently has. However, this would also require relaxing various checks where we currently only call FoldOpIntoSelect() if we have a constant operand.

I guess if there is no compile-time impact to calling FoldOpIntoSelect() for non-constants, then doing that would be a pretty clean and general way to go about it.

[goldstein.w.n]

In D153963#4486495, @nikic wrote:

@goldstein.w.n The transform needs to be called from somewhere. Currently it is called for a number of binops. The same transform is indeed possible for non-binop instructions, but I'm not sure it makes sense to plaster it everywhere.

I see, thats a fair point.

The main sensible way of doing that I can see is to extend FoldOpIntoSelect() to handle this. We could extend constantFoldOperationIntoSelectOperand() to determine the constant for zext/sext of the condition, similar to the special case for icmps it currently has. However, this would also require relaxing various checks where we currently only call FoldOpIntoSelect() if we have a constant operand.

I guess if there is no compile-time impact to calling FoldOpIntoSelect() for non-constants, then doing that would be a pretty clean and general way to go about it.

Okay, guess we can leave that as a todo for the future. I may look into when I have the time.

@antoniofrighetto for now I think its okay to keep this only for binops, but please add a todo that
if FoldOpIntoSelect is updated, we should remove the binop specific function.

[antoniofrighetto]

TODO added, polished up the code. @goldstein.w.n, thanks for pointing that out.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

897

Is there a reason RHS must be the ext and LHS must be the select?

llvm/test/Transforms/InstCombine/binop-select-cast-of-select-cond.ll

157

Can you add the following tests:

1. where select is on the RHS of the binop.
2. Where the select is multi-use
3. Where the select has two non-const sides.

197

Open a different patch.

[antoniofrighetto]

@goldstein.w.n, added multiuse select and non-const sides tests (last three tests), proofs updated (https://alive2.llvm.org/ce/z/m_vGWd). Tests are on a dedicated commit.

It seems RHS ext & LHS sel operands are canonicalized as such in SimplifyAssociativeOrCommutative for add/mul. When the binop is a subtraction, being non-commutative, the semantic of the operation will change if the operands are swapped. I tried extending the helper to support swapped operands too (LHS ext & RHS sel), yet, the transformation we obtain appears to be correct only when the select has both const sides. With non-const sides, the transformation fails (proof: https://alive2.llvm.org/ce/z/BZU9cR, 2 transformations failed out of 4). I don't believe we should introduce specialization in the helper for const-only subs.

[goldstein.w.n]

In D153963#4498090, @antoniofrighetto wrote:

@goldstein.w.n, added multiuse select and non-const sides tests (last three tests), proofs updated (https://alive2.llvm.org/ce/z/m_vGWd). Tests are on a dedicated commit.

It seems RHS ext & LHS sel operands are canonicalized as such in SimplifyAssociativeOrCommutative for add/mul.

Okay thats fine (also other binops).

When the binop is a subtraction, being non-commutative, the semantic of the operation will change if the operands are swapped. I tried extending the helper to support swapped operands too (LHS ext & RHS sel), yet, the transformation we obtain appears to be correct only when the select has both const sides. With non-const sides, the transformation fails (proof: https://alive2.llvm.org/ce/z/BZU9cR, 2 transformations failed out of 4). I don't believe we should introduce specialization in the helper for const-only subs.

non-const is fine AFAICT, youre proof is just a little buggy: https://alive2.llvm.org/ce/z/4yWy3R
Its okay to skip for now, but please add TODO for sub.

[antoniofrighetto]

@goldstein.w.n, thanks for pointing that out, updated to support swapped operands too, added tests for it.

(EDIT: Updated proofs as well)

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

902

Can you put this duplicate logic for RHS/LHS in a lambda?

907

Since you capture the entire scope I think the IsCastOpRHS and IsZExt can just be computed in the lambda which makes the callsites clearer.

921

Imo cleaner as a whole is to seperate the decision about the constant from creating the binop i.e

Constant * C;
if(IsTrueArm) {
  C = 0
}
else if(IsZext) {
  C = 1
}
else {
  C = AllOnes
}

return IsConstOpRHS ? BinOp(Opc, V, C) : BinOp(Opc, C, V);

llvm/test/Transforms/InstCombine/binop-select-cast-of-select-cond.ll

197

still outstanding.

[antoniofrighetto]

Simplified, and opened a patch for tests at: https://reviews.llvm.org/D155510, thanks!

[goldstein.w.n]

We should see diffs to the tests. This patch should be rebased ontop of D155510. Once you set D155510 as the child of this commit, when you checkout this one, it will grab both. Then you can rebase + resubmit both of them and we will be able to see the actual changes this commit causes.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

936

Think the follow is cleaner:

if(CondVal == A || match(...)) {
bool IsInvertedByNot = CondVal != A;
return SelectInst::Create(CondVal, NewFoldedConst(IsInvertedByNot, TrueVal),
                              NewFoldedConst(IsInvertedByNot, FalseVal));
}

[antoniofrighetto]

@goldstein.w.n, thank you, I think it should work out properly now.

[goldstein.w.n]

In D153963#4507798, @antoniofrighetto wrote:

@goldstein.w.n, thank you, I think it should work out properly now.

We don't see any test changes as a result of the impl.
You need to do the following:

1. Update the tests in the test patch with LLVM compiled WITHOUT your change.
2. Update the tests in this patch with LLVM compiled WITH your change.

That way we can see exact what your change actually changes..

[antoniofrighetto]

@goldstein.w.n, totally makes sense, my bad, for some reason I thought the diff would show up automatically when chaining reviews by setting the child. We should be on track now.

[antoniofrighetto]

@goldstein.w.n, it seems like the order of the two simplified instructions for the lasts two tests on Windows is reversed compared to the ones it should expect, although I'm not able to reproduce the issue locally. Any idea?

[goldstein.w.n]

In D153963#4511593, @antoniofrighetto wrote:

@goldstein.w.n, it seems like the order of the two simplified instructions for the lasts two tests on Windows is reversed compared to the ones it should expect, although I'm not able to reproduce the issue locally. Any idea?

Sorry dont really understand what you mean. But personally have no idea about the subtle differences between LLVM on windows vs linux.

[antoniofrighetto]

@goldstein.w.n, looking at the CI failure on Windows, it seems like that for test sub_select_sext_op_swapped_non_const_args it expects sub i6 0, [[ARGF]] to be the first instruction, as opposed to the one on Linux, where that sub appears as second instruction. That may be the reason why FileCheck fails.

[goldstein.w.n]

In D153963#4511653, @antoniofrighetto wrote:

@goldstein.w.n, looking at the CI failure on Windows, it seems like that for test sub_select_sext_op_swapped_non_const_args it expects sub i6 0, [[ARGF]] to be the first instruction, as opposed to the one on Linux, where that sub appears as second instruction. That may be the reason why FileCheck fails.

Oh, I wouldn't worry about that. I don't think the CI for phabricator is really used. AFAIK we only do post commit testing for LLVM (atlthough some sub projects do pre commit testing).

[antoniofrighetto]

On track :)

[goldstein.w.n]

LGTM.

[dyung]

Hi @antoniofrighetto, this change seems to be causing the compiler to hit an assertion failure in one of our internal tests. I have put the details in bug #64040, can you take a look?

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if ((match(RHS, m_ZExt(m_Value(A))) &&
     return new ZExtInst(B, LHS->getType());
 
   // zext(A) + sext(A) --> 0 if A is i1
   if (match(&I, m_c_BinOp(m_ZExt(m_Value(A)), m_SExt(m_Deferred(A)))) &&
       A->getType()->isIntOrIntVectorTy(1))
     return replaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 
   // A+B --> A|B iff A and B have no bits set in common.
   if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
     return BinaryOperator::CreateOr(LHS, RHS);
 
   if (Instruction *Ext = narrowMathIfNoOverflow(I))
     return Ext;
 
   // (add (xor A, B) (and A, B)) --> (or A, B)
   // (add (and A, B) (xor A, B)) --> (or A, B)
   if (match(&I, m_c_BinOp(m_Xor(m_Value(A), m_Value(B)),
                           m_c_And(m_Deferred(A), m_Deferred(B)))))
     return BinaryOperator::CreateOr(A, B);
 
   // (add (or A, B) (and A, B)) --> (add A, B)
   // (add (and A, B) (or A, B)) --> (add A, B)
   if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
                           m_c_And(m_Deferred(A), m_Deferred(B))))) {
     // Replacing operands in-place to preserve nuw/nsw flags.
     replaceOperand(I, 0, A);
     replaceOperand(I, 1, B);
     return &I;
   }
 
   // (add A (or A, -A)) --> (and (add A, -1) A)
if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) &&
       haveNoCommonBitsSet(A, B, DL, &AC, &I, &DT))
     return replaceInstUsesWith(
         I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
                                    {Builder.CreateOr(A, B)}));
 
   if (Instruction *Res = foldBinOpOfDisplacedShifts(I))
     return Res;
 
+  if (Instruction *Res = foldBinOpOfSelectAndCastOfSelectCondition(I))
+    return Res;
+
   return Changed ? &I : nullptr;
 }
 
 /// Eliminate an op from a linear interpolation (lerp) pattern.
 static Instruction *factorizeLerp(BinaryOperator &I,
                                   InstCombiner::BuilderTy &Builder) {
   Value *X, *Y, *Z;
   if (!match(&I, m_c_FAdd(m_OneUse(m_c_FMul(m_Value(Y),
if (I.hasNoUnsignedWrap() || I.hasNoSignedWrap()) {
       Value *Sub =
           Builder.CreateSub(X, Y, "sub", /*HasNUW=*/false, /*HasNSW=*/true);
       Value *Call =
           Builder.CreateBinaryIntrinsic(Intrinsic::abs, Sub, Builder.getTrue());
       return replaceInstUsesWith(I, Call);
     }
   }
 
+  if (Instruction *Res = foldBinOpOfSelectAndCastOfSelectCondition(I))
+    return Res;
+
   return TryToNarrowDeduceFlags();
 }
 
 /// This eliminates floating-point negation in either 'fneg(X)' or
 /// 'fsub(-0.0, X)' form by combining into a constant operand.
 static Instruction *foldFNegIntoConstant(Instruction &I, const DataLayout &DL) {
   // This is limited with one-use because fneg is assumed better for
   // reassociation and cheaper in codegen than fmul/fdiv.

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
                                         Value *RHS);
 
   // (Binop1 (Binop2 (logic_shift X, C), C1), (logic_shift Y, C))
   //    -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C)
   // (Binop1 (Binop2 (logic_shift X, Amt), Mask), (logic_shift Y, Amt))
   //    -> (BinOp (logic_shift (BinOp X, Y)), Mask)
   Instruction *foldBinOpShiftWithShift(BinaryOperator &I);
 
+  /// Tries to simplify binops of select and cast of the select condition.
+  ///
+  /// (Binop (cast C), (select C, T, F))
+  ///    -> (select C, C0, C1)
+  Instruction *foldBinOpOfSelectAndCastOfSelectCondition(BinaryOperator &I);
+
   /// This tries to simplify binary operations by factorizing out common terms
   /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
   Value *tryFactorizationFolds(BinaryOperator &I);
 
   /// Match a select chain which produces one of three values based on whether
   /// the LHS is less than, equal to, or greater than RHS respectively.
   /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
   /// Equal and Greater values are saved in the matching process and returned to

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Value *Abs = Builder.CreateBinaryIntrinsic(
         Intrinsic::abs, X, ConstantInt::getBool(I.getContext(), HasNSW));
     Abs->takeName(&I);
     return replaceInstUsesWith(I, Abs);
   }
 
   if (Instruction *Ext = narrowMathIfNoOverflow(I))
     return Ext;
 
+  if (Instruction *Res = foldBinOpOfSelectAndCastOfSelectCondition(I))
+    return Res;
+
   // min(X, Y) * max(X, Y) => X * Y.
   if (match(&I, m_CombineOr(m_c_Mul(m_SMax(m_Value(X), m_Value(Y)),
                                     m_c_SMin(m_Deferred(X), m_Deferred(Y))),
                             m_c_Mul(m_UMax(m_Value(X), m_Value(Y)),
                                     m_c_UMin(m_Deferred(X), m_Deferred(Y))))))
     return BinaryOperator::CreateWithCopiedFlags(Instruction::Mul, X, Y, &I);
 
   // (mul Op0 Op1):

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

return BinaryOperator::Create(static_cast<Instruction::BinaryOps>(ShOpc),
                                   NewBinOp1, CShift);
   };
 
   if (Instruction *R = MatchBinOp(0))
     return R;
   return MatchBinOp(1);
 }
 
+// (Binop (zext C), (select C, T, F))
+//    -> (select C, (binop 1, T), (binop 0, F))
+//
+// (Binop (sext C), (select C, T, F))
+//    -> (select C, (binop -1, T), (binop 0, F))
+//
+// Attempt to simplify binary operations into a select with folded args, when
+// one operand of the binop is a select instruction and the other operand is a
+// zext/sext extension, whose value is the select condition.
+Instruction *
+InstCombinerImpl::foldBinOpOfSelectAndCastOfSelectCondition(BinaryOperator &I) {
+  // TODO: this simplification may be extended to any speculatable instruction,
+  // not just binops, and would possibly be handled better in FoldOpIntoSelect.
+  Instruction::BinaryOps Opc = I.getOpcode();
+  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+  Value *A, *CondVal, *TrueVal, *FalseVal;
+  Value *CastOp;
+
+  auto MatchSelectAndCast = [&](Value *CastOp, Value *SelectOp) {
+    return match(CastOp, m_ZExtOrSExt(m_Value(A))) &&
+           A->getType()->getScalarSizeInBits() == 1 &&
+           match(SelectOp, m_Select(m_Value(CondVal), m_Value(TrueVal),
+                                    m_Value(FalseVal)));
+  };
+
+  // Make sure one side of the binop is a select instruction, and the other is a
+  // zero/sign extension operating on a i1.
+  if (MatchSelectAndCast(LHS, RHS))
+    CastOp = LHS;
+  else if (MatchSelectAndCast(RHS, LHS))
+    CastOp = RHS;
+  else
+    return nullptr;
+
+  auto NewFoldedConst = [&](bool IsTrueArm, Value *V) {
+    bool IsCastOpRHS = (CastOp == RHS);
+    bool IsZExt = isa<ZExtInst>(CastOp);
+    Constant *C;
+
+    if (IsTrueArm) {
+      C = Constant::getNullValue(V->getType());
+    } else if (IsZExt) {
+      C = Constant::getIntegerValue(
+          V->getType(), APInt(V->getType()->getIntegerBitWidth(), 1));
+    } else {
+      C = Constant::getAllOnesValue(V->getType());
+    }
+
+    return IsCastOpRHS ? Builder.CreateBinOp(Opc, V, C)
+                       : Builder.CreateBinOp(Opc, C, V);
+  };
+
+  // If the value used in the zext/sext is the select condition, or the negated
+  // of the select condition, the binop can be simplified.
+  if (CondVal == A)
+    return SelectInst::Create(CondVal, NewFoldedConst(false, TrueVal),
+                              NewFoldedConst(true, FalseVal));
+
+  if (match(A, m_Not(m_Specific(CondVal))))
+    return SelectInst::Create(CondVal, NewFoldedConst(true, TrueVal),
+                              NewFoldedConst(false, FalseVal));
+
+  return nullptr;
+}
+
 Value *InstCombinerImpl::tryFactorizationFolds(BinaryOperator &I) {
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
   Instruction::BinaryOps TopLevelOpcode = I.getOpcode();
   Value *A, *B, *C, *D;
   Instruction::BinaryOps LHSOpcode, RHSOpcode;
 
   if (Op0)
     LHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op0, A, B);
   if (Op1)
     RHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op1, C, D);
 
   // The instruction has the form "(A op' B) op (C op' D)".  Try to factorize
   // a common term.
   if (Op0 && Op1 && LHSOpcode == RHSOpcode)
     if (Value *V = tryFactorization(I, SQ, Builder, LHSOpcode, A, B, C, D))
       return V;

llvm/test/Transforms/InstCombine/binop-select-cast-of-select-cond.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 define i64 @add_select_zext(i1 %c) {
 ; CHECK-LABEL: define i64 @add_select_zext
 ; CHECK-SAME: (i1 [[C:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i64 64, i64 1
-; CHECK-NEXT:    [[EXT:%.*]] = zext i1 [[C]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[SEL]], [[EXT]]
+; CHECK-NEXT:    [[ADD:%.*]] = select i1 [[C]], i64 65, i64 1
 ; CHECK-NEXT:    ret i64 [[ADD]]
 ;
   %sel = select i1 %c, i64 64, i64 1
   %ext = zext i1 %c to i64
   %add = add i64 %sel, %ext
   ret i64 %add
 }
 
 define i64 @add_select_sext(i1 %c) {
 ; CHECK-LABEL: define i64 @add_select_sext
 ; CHECK-SAME: (i1 [[C:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i64 64, i64 1
-; CHECK-NEXT:    [[EXT:%.*]] = sext i1 [[C]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[SEL]], [[EXT]]
+; CHECK-NEXT:    [[ADD:%.*]] = select i1 [[C]], i64 63, i64 1
 ; CHECK-NEXT:    ret i64 [[ADD]]
 ;
   %sel = select i1 %c, i64 64, i64 1
   %ext = sext i1 %c to i64
   %add = add i64 %sel, %ext
   ret i64 %add
 }
 
 define i64 @add_select_not_zext(i1 %c) {
 ; CHECK-LABEL: define i64 @add_select_not_zext
 ; CHECK-SAME: (i1 [[C:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i64 64, i64 1
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C]], true
-; CHECK-NEXT:    [[EXT:%.*]] = zext i1 [[NOT_C]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[SEL]], [[EXT]]
+; CHECK-NEXT:    [[ADD:%.*]] = select i1 [[C]], i64 64, i64 2
 ; CHECK-NEXT:    ret i64 [[ADD]]
 ;
   %sel = select i1 %c, i64 64, i64 1
   %not.c = xor i1 %c, true
   %ext = zext i1 %not.c to i64
   %add = add i64 %sel, %ext
   ret i64 %add
 }
 
 define i64 @add_select_not_sext(i1 %c) {
 ; CHECK-LABEL: define i64 @add_select_not_sext
 ; CHECK-SAME: (i1 [[C:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i64 64, i64 1
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C]], true
-; CHECK-NEXT:    [[EXT:%.*]] = sext i1 [[NOT_C]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[SEL]], [[EXT]]
+; CHECK-NEXT:    [[ADD:%.*]] = select i1 [[C]], i64 64, i64 0
 ; CHECK-NEXT:    ret i64 [[ADD]]
 ;
   %sel = select i1 %c, i64 64, i64 1
   %not.c = xor i1 %c, true
   %ext = sext i1 %not.c to i64
   %add = add i64 %sel, %ext
   ret i64 %add
 }
 
 define i64 @sub_select_sext(i1 %c, i64 %arg) {
 ; CHECK-LABEL: define i64 @sub_select_sext
 ; CHECK-SAME: (i1 [[C:%.*]], i64 [[ARG:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i64 64, i64 [[ARG]]
-; CHECK-NEXT:    [[EXT_NEG:%.*]] = zext i1 [[C]] to i64
-; CHECK-NEXT:    [[SUB:%.*]] = add i64 [[SEL]], [[EXT_NEG]]
+; CHECK-NEXT:    [[SUB:%.*]] = select i1 [[C]], i64 65, i64 [[ARG]]
 ; CHECK-NEXT:    ret i64 [[SUB]]
 ;
   %sel = select i1 %c, i64 64, i64 %arg
   %ext = sext i1 %c to i64
   %sub = sub i64 %sel, %ext
   ret i64 %sub
 }
 
 define i64 @sub_select_not_zext(i1 %c, i64 %arg) {
 ; CHECK-LABEL: define i64 @sub_select_not_zext
 ; CHECK-SAME: (i1 [[C:%.*]], i64 [[ARG:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i64 [[ARG]], i64 64
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C]], true
-; CHECK-NEXT:    [[EXT_NEG:%.*]] = sext i1 [[NOT_C]] to i64
-; CHECK-NEXT:    [[SUB:%.*]] = add i64 [[SEL]], [[EXT_NEG]]
+; CHECK-NEXT:    [[SUB:%.*]] = select i1 [[C]], i64 [[ARG]], i64 63
 ; CHECK-NEXT:    ret i64 [[SUB]]
 ;
   %sel = select i1 %c, i64 %arg, i64 64
   %not.c = xor i1 %c, true
   %ext = zext i1 %not.c to i64
   %sub = sub i64 %sel, %ext
   ret i64 %sub
 }
 
 define i64 @sub_select_not_sext(i1 %c, i64 %arg) {
 ; CHECK-LABEL: define i64 @sub_select_not_sext
 ; CHECK-SAME: (i1 [[C:%.*]], i64 [[ARG:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i64 [[ARG]], i64 64
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C]], true
-; CHECK-NEXT:    [[EXT_NEG:%.*]] = zext i1 [[NOT_C]] to i64
-; CHECK-NEXT:    [[SUB:%.*]] = add i64 [[SEL]], [[EXT_NEG]]
+; CHECK-NEXT:    [[SUB:%.*]] = select i1 [[C]], i64 [[ARG]], i64 65
 ; CHECK-NEXT:    ret i64 [[SUB]]
 ;
   %sel = select i1 %c, i64 %arg, i64 64
   %not.c = xor i1 %c, true
   %ext = sext i1 %not.c to i64
   %sub = sub i64 %sel, %ext
   ret i64 %sub
 }
 
 define i64 @mul_select_zext(i1 %c, i64 %arg) {
 ; CHECK-LABEL: define i64 @mul_select_zext
 ; CHECK-SAME: (i1 [[C:%.*]], i64 [[ARG:%.*]]) {
 ; CHECK-NEXT:    [[MUL:%.*]] = select i1 [[C]], i64 [[ARG]], i64 0
 ; CHECK-NEXT:    ret i64 [[MUL]]
 ;
   %sel = select i1 %c, i64 %arg, i64 1
   %ext = zext i1 %c to i64
   %mul = mul i64 %sel, %ext
   ret i64 %mul
 }
 
 define i64 @mul_select_sext(i1 %c) {
 ; CHECK-LABEL: define i64 @mul_select_sext
 ; CHECK-SAME: (i1 [[C:%.*]]) {
-; CHECK-NEXT:    [[EXT:%.*]] = sext i1 [[C]] to i64
-; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C]], i64 6, i64 0
-; CHECK-NEXT:    [[MUL:%.*]] = shl i64 [[EXT]], [[TMP1]]
+; CHECK-NEXT:    [[MUL:%.*]] = select i1 [[C]], i64 -64, i64 0
 ; CHECK-NEXT:    ret i64 [[MUL]]
 ;
   %sel = select i1 %c, i64 64, i64 1
   %ext = sext i1 %c to i64
   %mul = mul i64 %sel, %ext
   ret i64 %mul
 }
 
;
   %vec1 = insertelement <2 x i64> %vec0, i64 %ext, i32 1
   %add = add <2 x i64> %sel, %vec1
   ret <2 x i64> %add
 }
 
 define i64 @multiuse_add(i1 %c) {
 ; CHECK-LABEL: define i64 @multiuse_add
 ; CHECK-SAME: (i1 [[C:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i64 64, i64 1
-; CHECK-NEXT:    [[EXT:%.*]] = zext i1 [[C]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[SEL]], [[EXT]]
-; CHECK-NEXT:    [[ADD2:%.*]] = add nuw nsw i64 [[ADD]], 1
+; CHECK-NEXT:    [[ADD2:%.*]] = select i1 [[C]], i64 66, i64 2
 ; CHECK-NEXT:    ret i64 [[ADD2]]
 ;
   %sel = select i1 %c, i64 64, i64 1
   %ext = zext i1 %c to i64
   %add = add i64 %sel, %ext
   %add2 = add i64 %add, 1
   ret i64 %add2
 }
 
 define i64 @multiuse_select(i1 %c) {
 ; CHECK-LABEL: define i64 @multiuse_select
 ; CHECK-SAME: (i1 [[C:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i64 64, i64 0
-; CHECK-NEXT:    [[EXT_NEG:%.*]] = sext i1 [[C]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[SEL]], [[EXT_NEG]]
-; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[SEL]], [[ADD]]
+; CHECK-NEXT:    [[MUL:%.*]] = select i1 [[C]], i64 4032, i64 0
 ; CHECK-NEXT:    ret i64 [[MUL]]
 ;
   %sel = select i1 %c, i64 64, i64 0
   %ext = zext i1 %c to i64
   %add = sub i64 %sel, %ext
   %mul = mul i64 %sel, %add
   ret i64 %mul
 }
 
 define i64 @select_non_const_sides(i1 %c, i64 %arg1, i64 %arg2) {
 ; CHECK-LABEL: define i64 @select_non_const_sides
 ; CHECK-SAME: (i1 [[C:%.*]], i64 [[ARG1:%.*]], i64 [[ARG2:%.*]]) {
-; CHECK-NEXT:    [[EXT_NEG:%.*]] = sext i1 [[C]] to i64
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i64 [[ARG1]], i64 [[ARG2]]
-; CHECK-NEXT:    [[SUB:%.*]] = add i64 [[SEL]], [[EXT_NEG]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[ARG1]], -1
+; CHECK-NEXT:    [[SUB:%.*]] = select i1 [[C]], i64 [[TMP1]], i64 [[ARG2]]
 ; CHECK-NEXT:    ret i64 [[SUB]]
 ;
   %ext = zext i1 %c to i64
   %sel = select i1 %c, i64 %arg1, i64 %arg2
   %sub = sub i64 %sel, %ext
   ret i64 %sub
 }
 
 define i6 @sub_select_sext_op_swapped_non_const_args(i1 %c, i6 %argT, i6 %argF) {
 ; CHECK-LABEL: define i6 @sub_select_sext_op_swapped_non_const_args
 ; CHECK-SAME: (i1 [[C:%.*]], i6 [[ARGT:%.*]], i6 [[ARGF:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i6 [[ARGT]], i6 [[ARGF]]
-; CHECK-NEXT:    [[EXT:%.*]] = sext i1 [[C]] to i6
-; CHECK-NEXT:    [[SUB:%.*]] = sub i6 [[EXT]], [[SEL]]
+; CHECK-DAG:     [[TMP1:%.*]] = xor i6 [[ARGT]], -1
+; CHECK-DAG:     [[TMP2:%.*]] = sub i6 0, [[ARGF]]
+; CHECK-NEXT:    [[SUB:%.*]] = select i1 [[C]], i6 [[TMP1]], i6 [[TMP2]]
 ; CHECK-NEXT:    ret i6 [[SUB]]
 ;
   %sel = select i1 %c, i6 %argT, i6 %argF
   %ext = sext i1 %c to i6
   %sub = sub i6 %ext, %sel
   ret i6 %sub
 }
 
 define i6 @sub_select_zext_op_swapped_non_const_args(i1 %c, i6 %argT, i6 %argF) {
 ; CHECK-LABEL: define i6 @sub_select_zext_op_swapped_non_const_args
 ; CHECK-SAME: (i1 [[C:%.*]], i6 [[ARGT:%.*]], i6 [[ARGF:%.*]]) {
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i6 [[ARGT]], i6 [[ARGF]]
-; CHECK-NEXT:    [[EXT:%.*]] = zext i1 [[C]] to i6
-; CHECK-NEXT:    [[SUB:%.*]] = sub i6 [[EXT]], [[SEL]]
+; CHECK-DAG:     [[TMP1:%.*]] = sub i6 1, [[ARGT]]
+; CHECK-DAG:     [[TMP2:%.*]] = sub i6 0, [[ARGF]]
+; CHECK-NEXT:    [[SUB:%.*]] = select i1 [[C]], i6 [[TMP1]], i6 [[TMP2]]
 ; CHECK-NEXT:    ret i6 [[SUB]]
 ;
   %sel = select i1 %c, i6 %argT, i6 %argF
   %ext = zext i1 %c to i6
   %sub = sub i6 %ext, %sel
   ret i6 %sub
 }