[InstCombine] Expand `foldSelectICmpAndOr` -> `foldSelectICmpAndBinOp` to work for more binops

[goldstein.w.n]

Summary

This just expands on the existing logic that worked for Or and
applies it to any binop where 0 is the identity value on the RHS
i.e: add, or, xor, shl, etc...

Proofs For Some: https://alive2.llvm.org/ce/z/XZo6JD

[goldstein.w.n]

Rebase

[nikic]

Why is this legal for all binops? Doesn't this transform require that the neutral element of the binop is zero? So it would work for or, xor or add, but not for mul or and for example?

I think this entire transform should probably be handled as a two step process: First, Cond ? X : BinOp(X, C) should become BinOp(X, Cond ? NeutralC : C) and then this fold should work on Cond ? 0 : C as the root. We actually already do the former canonicalization, but not in the case where C is constant. This will cleanly separate out the actual binop handling. Only disadvantage is that we won't be able to handle the case where the binop has multiple uses anymore, but that's a general issue with composable folds that we can ignore unless there is reason to believe that multi-use is motivating for the current handling.

[goldstein.w.n]

In D148414#4290296, @nikic wrote:

Why is this legal for all binops? Doesn't this transform require that the neutral element of the binop is zero? So it would work for or, xor or add, but not for mul or and for example?

Yeah you are right. Not sure what I was thinking...

I think this entire transform should probably be handled as a two step process: First, Cond ? X : BinOp(X, C) should become BinOp(X, Cond ? NeutralC : C) and then this fold should work on Cond ? 0 : C as the root.
We actually already do the former canonicalization, but not in the case where C is constant.

Where do we do the canonicalization?

This will cleanly separate out the actual binop handling. Only disadvantage is that we won't be able to handle the case where the binop has multiple uses anymore, but that's a general issue with composable folds that we can ignore unless there is reason to believe that multi-use is motivating for the current handling.

Why won't we be able to handle multi-use anymore? If we do it like this, seems this function can be deleted once we get the canonicalization of Cond ? X : BinOp(X, C) -> BinOp(X, Cond ? NeutralC : C)?

[nikic]

In D148414#4290762, @goldstein.w.n wrote:

I think this entire transform should probably be handled as a two step process: First, Cond ? X : BinOp(X, C) should become BinOp(X, Cond ? NeutralC : C) and then this fold should work on Cond ? 0 : C as the root.
We actually already do the former canonicalization, but not in the case where C is constant.

Where do we do the canonicalization?

In foldSelectIntoOp(), with the current constant restriction at https://github.com/llvm/llvm-project/blob/8d163e5045073a5ac570225cc8e14cc9f6d72f09/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp#L507.

[goldstein.w.n]

In D148414#4290787, @nikic wrote:

In D148414#4290762, @goldstein.w.n wrote:

I think this entire transform should probably be handled as a two step process: First, Cond ? X : BinOp(X, C) should become BinOp(X, Cond ? NeutralC : C) and then this fold should work on Cond ? 0 : C as the root.
We actually already do the former canonicalization, but not in the case where C is constant.

Where do we do the canonicalization?

In foldSelectIntoOp(), with the current constant restriction at https://github.com/llvm/llvm-project/blob/8d163e5045073a5ac570225cc8e14cc9f6d72f09/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp#L507.

Thanks. So how does the following sound:

1. Patch foldSelectICmpAnd ->FoldSelectICmpPow2OrZero so we can handle:

define i8 @should_be_doable(i8 %x) {
  %xm1 = sub i8 %x, 1
  %xa = and i8 %xm1, %x
  %cmp = icmp eq i8 %xa, 16
  %s = select i1 %cmp, i8 64, i8 0
  ret i8 %s
}

2. Update foldSelectIntoOp to do constants iff isPow2(abs(TC - FC)) and Cond is either (ICmp eq Pow2OrZero, C_Pow2) or a SignTest

At that point this function should be mostly redundant. There may be some edgecases with NeutralC is non-zero (i.e mul) which
we will still miss (currently as well) but I'm going to try and remove this function.

[nikic]

In D148414#4290790, @goldstein.w.n wrote:

2. Update foldSelectIntoOp to do constants iff isPow2(abs(TC - FC)) and Cond is either (ICmp eq Pow2OrZero, C_Pow2) or a SignTest

Ideally we would just remove the limitation entirely -- at the IR level, we would certainly prefer having a select on constants. However, this would likely need a backend undo transform, because that saves materializing the zero constant and likely allows folding the other constant into an immediate operand.

[goldstein.w.n]

In D148414#4290852, @nikic wrote:

In D148414#4290790, @goldstein.w.n wrote:

2. Update foldSelectIntoOp to do constants iff isPow2(abs(TC - FC)) and Cond is either (ICmp eq Pow2OrZero, C_Pow2) or a SignTest

Ideally we would just remove the limitation entirely -- at the IR level, we would certainly prefer having a select on constants. However, this would likely need a backend undo transform, because that saves materializing the zero constant and likely allows folding the other constant into an immediate operand.

Yeah that makes sense.

I'll get started on a series to do that.

[goldstein.w.n]

In D148414#4290852, @nikic wrote:

In D148414#4290790, @goldstein.w.n wrote:

2. Update foldSelectIntoOp to do constants iff isPow2(abs(TC - FC)) and Cond is either (ICmp eq Pow2OrZero, C_Pow2) or a SignTest

Ideally we would just remove the limitation entirely -- at the IR level, we would certainly prefer having a select on constants. However, this would likely need a backend undo transform, because that saves materializing the zero constant and likely allows folding the other constant into an immediate operand.

@nikic so the backend has code to undo this already. Its just not enabled for scalars. I enabled it on a branch for x86 here:
https://github.com/goldsteinn/llvm-project/pull/new/enable-select-backend
but a lot of regressions. Maybe simpler to just handle the known cases here?

[nikic]

In D148414#4291480, @goldstein.w.n wrote:

In D148414#4290852, @nikic wrote:

In D148414#4290790, @goldstein.w.n wrote:

2. Update foldSelectIntoOp to do constants iff isPow2(abs(TC - FC)) and Cond is either (ICmp eq Pow2OrZero, C_Pow2) or a SignTest

Ideally we would just remove the limitation entirely -- at the IR level, we would certainly prefer having a select on constants. However, this would likely need a backend undo transform, because that saves materializing the zero constant and likely allows folding the other constant into an immediate operand.

@nikic so the backend has code to undo this already. Its just not enabled for scalars. I enabled it on a branch for x86 here:
https://github.com/goldsteinn/llvm-project/pull/new/enable-select-backend
but a lot of regressions. Maybe simpler to just handle the known cases here?

I think your patch handles a few more cases than we are interested in here. Per the code in getSelectFoldableOperands() we don't do this transform for div/rem, so I don't think we need the additional handling for those. More importantly, it looks like your patch will also do the undo transform for the case where the select has the identity as one element and a non-constant as the other. I think the diffs will look better if you limited the scalar case to two constant operands. The constant + non-constant case can probably also be beneficial, but the heuristics for that are less obvious.

[goldstein.w.n]

In D148414#4291664, @nikic wrote:

In D148414#4291480, @goldstein.w.n wrote:

In D148414#4290852, @nikic wrote:

In D148414#4290790, @goldstein.w.n wrote:

2. Update foldSelectIntoOp to do constants iff isPow2(abs(TC - FC)) and Cond is either (ICmp eq Pow2OrZero, C_Pow2) or a SignTest

Ideally we would just remove the limitation entirely -- at the IR level, we would certainly prefer having a select on constants. However, this would likely need a backend undo transform, because that saves materializing the zero constant and likely allows folding the other constant into an immediate operand.

@nikic so the backend has code to undo this already. Its just not enabled for scalars. I enabled it on a branch for x86 here:
https://github.com/goldsteinn/llvm-project/pull/new/enable-select-backend
but a lot of regressions. Maybe simpler to just handle the known cases here?

I think your patch handles a few more cases than we are interested in here. Per the code in getSelectFoldableOperands() we don't do this transform for div/rem, so I don't think we need the additional handling for those. More importantly, it looks like your patch will also do the undo transform for the case where the select has the identity as one element and a non-constant as the other. I think the diffs will look better if you limited the scalar case to two constant operands. The constant + non-constant case can probably also be beneficial, but the heuristics for that are less obvious.

Posted WIP, then saw this. Updating so we can specify if both arms constant only.

[goldstein.w.n]

Fix to only use some binops

[goldstein.w.n]

In D148414#4290296, @nikic wrote:

Why is this legal for all binops? Doesn't this transform require that the neutral element of the binop is zero? So it would work for or, xor or add, but not for mul or and for example?

I think this entire transform should probably be handled as a two step process: First, Cond ? X : BinOp(X, C) should become BinOp(X, Cond ? NeutralC : C) and then this fold should work on Cond ? 0 : C as the root. We actually already do the former canonicalization, but not in the case where C is constant. This will cleanly separate out the actual binop handling. Only disadvantage is that we won't be able to handle the case where the binop has multiple uses anymore, but that's a general issue with composable folds that we can ignore unless there is reason to believe that multi-use is motivating for the current handling.

Fixed, have proofs for all the binops I added.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

722

Possibly make this a check that getBinOpIdentity() with AllowRHSConstant=true is zero instead?

Or at least comment on what the criterion for valid binops is...

[goldstein.w.n]

Use getIdentityBinOp instead of just having a table

[goldstein.w.n]

Rebase

[nikic]

LGTM

[DavidSpickett]

Since this change, our 2 stage 32 bit Armv7 builder has been failing to build the second stage: https://lab.llvm.org/buildbot/#/builders/182/builds/7193/steps/9/logs/stdio

FAILED: lib/Target/X86/CMakeFiles/LLVMX86CodeGen.dir/X86ISelLowering.cpp.o 
/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage1.install/bin/clang++ -DGTEST_HAS_RTTI=0 -D_DEBUG -D_FILE_OFFSET_BITS=64 -D_GLIBCXX_ASSERTIONS -D_GNU_SOURCE -D_LARGEFILE_SOURCE -D_LIBCPP_ENABLE_HARDENED_MODE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage2/lib/Target/X86 -I/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/llvm/llvm/lib/Target/X86 -I/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage2/include -I/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/llvm/llvm/include -mcpu=cortex-a15 -mfpu=vfpv3 -marm -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -Wctad-maybe-unsupported -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG -fvisibility=hidden  -fno-exceptions -funwind-tables -fno-rtti -UNDEBUG -std=c++17 -MD -MT lib/Target/X86/CMakeFiles/LLVMX86CodeGen.dir/X86ISelLowering.cpp.o -MF lib/Target/X86/CMakeFiles/LLVMX86CodeGen.dir/X86ISelLowering.cpp.o.d -o lib/Target/X86/CMakeFiles/LLVMX86CodeGen.dir/X86ISelLowering.cpp.o -c /home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/llvm/llvm/lib/Target/X86/X86ISelLowering.cpp
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage1.install/bin/clang++ -DGTEST_HAS_RTTI=0 -D_DEBUG -D_FILE_OFFSET_BITS=64 -D_GLIBCXX_ASSERTIONS -D_GNU_SOURCE -D_LARGEFILE_SOURCE -D_LIBCPP_ENABLE_HARDENED_MODE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage2/lib/Target/X86 -I/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/llvm/llvm/lib/Target/X86 -I/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage2/include -I/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/llvm/llvm/include -mcpu=cortex-a15 -mfpu=vfpv3 -marm -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -Wctad-maybe-unsupported -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG -fvisibility=hidden -fno-exceptions -funwind-tables -fno-rtti -UNDEBUG -std=c++17 -MD -MT lib/Target/X86/CMakeFiles/LLVMX86CodeGen.dir/X86ISelLowering.cpp.o -MF lib/Target/X86/CMakeFiles/LLVMX86CodeGen.dir/X86ISelLowering.cpp.o.d -o lib/Target/X86/CMakeFiles/LLVMX86CodeGen.dir/X86ISelLowering.cpp.o -c /home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/llvm/llvm/lib/Target/X86/X86ISelLowering.cpp
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x03ae2214 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage1.install/bin/clang+++0x3246214)
 #1 0x03adfb88 llvm::sys::RunSignalHandlers() (/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage1.install/bin/clang+++0x3243b88)
 #2 0x03ae1248 llvm::sys::CleanupOnSignal(unsigned int) (/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage1.install/bin/clang+++0x3245248)
 #3 0x03a4998c CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #4 0xf790e530 __default_sa_restorer /build/glibc-9MGTF6/glibc-2.31/signal/../sysdeps/unix/sysv/linux/arm/sigrestorer.S:67:0
 #5 0x033a2ad4 llvm::Constant::isNullValue() const (/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage1.install/bin/clang+++0x2b06ad4)
 #6 0x0376b91c foldSelectICmpAndBinOp(llvm::ICmpInst const*, llvm::Value*, llvm::Value*, llvm::IRBuilder<llvm::TargetFolder, llvm::IRBuilderCallbackInserter>&) InstCombineSelect.cpp:0:0
 #7 0x0376a104 llvm::InstCombinerImpl::foldSelectInstWithICmp(llvm::SelectInst&, llvm::ICmpInst*) (/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage1.install/bin/clang+++0x2ece104)
 #8 0x03770248 llvm::InstCombinerImpl::visitSelectInst(llvm::SelectInst&) (/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage1.install/bin/clang+++0x2ed4248)
 #9 0x036a5f74 llvm::InstCombinerImpl::run() (/home/tcwg-buildbot/worker/clang-armv7-vfpv3-2stage/stage1.install/bin/clang+++0x2e09f74)
<...>

You have many patches in that build and I'm picking out this one just due to foldSelectICmpAndBinOp.

It's not failing on the other 32 bit Arm builders because they are a few hours behind.

I'm not sure if I can cleanly revert this patch but before I look at that I'll get a reproducer for you.

[DavidSpickett]

I've confirmed just this commit is enough to hit the issue, and here's the reproducer:

X86ISelLowering-82e2a2.zip8 MBDownload

[goldstein.w.n]

In D148414#4594813, @DavidSpickett wrote:

I've confirmed just this commit is enough to hit the issue, and here's the reproducer:

X86ISelLowering-82e2a2.zip8 MBDownload

Thank you for creating the repro and reverting this.
Issue was it was missing a nullptr check when checking the identity constant.

@nikic I've retested this. Going to repush in a few days unless anyone objects.

[goldstein.w.n]

Add nullptr check when checking identity constant

[nikic]

Can you please also add a test for that case (unless you already committed it)?

[goldstein.w.n]

Add tests for reproducing prior bug

[nikic]

Thanks, LGTM.

[chapuni]

Seems this still miscompiles llvm-rc/ResourceFileWriter.cpp for targeting x86-64. Investigating.

[chapuni]

FYI, similar miscompilation in llvm-rc; https://lab.llvm.org/buildbot/#/builders/124/builds/8260

[goldstein.w.n]

In D148414#4616067, @chapuni wrote:

FYI, similar miscompilation in llvm-rc; https://lab.llvm.org/buildbot/#/builders/124/builds/8260

Investigating, if don't see obvious fix shortly will revert.

[goldstein.w.n]

In D148414#4616052, @chapuni wrote:

Seems this still miscompiles llvm-rc/ResourceFileWriter.cpp for targeting x86-64. Investigating.

Are you certain its this? I just checked and the IR for llvm-rc/ResourceFileWriter.cpp is unchanged with/without this commit.

[goldstein.w.n]

Re-reverted to be safe. Will look into this more tomorrow

[chapuni]

I am using ubuntu-20.04 (amd64) and stage2-clang uses libstdc++ for bootstrapping.

Ubuntu (aarch64) didn't complain. (I don't know why)

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

757

Would it be right if BinOp is not commutative?
I saw a malformed lshr in the miscompilation.

%spec.select = lshr i64 %sub78, %foo was transformed to %spec.select = lshr i64 %bar, %sub78.

llvm/test/Transforms/InstCombine/select-with-bitwise-ops.ll

1616

XOR (and %xor) is odd here, even if this checks that instructions are not transformed. (ditto in the next test)

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

757

Yup, this is it. Didn't see that original code had inverted the operands.

[goldstein.w.n]

Seems overkill for adding tests for each binop, but ran them offline and all transform verify with alive2:

; $> /home/noah/programs/opensource/llvm-dev/src/alive2/build/alive-tv (-smt-to=200000000)

----------------------------------------
define i8 @select_icmp_eq_and_1_0_add_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %badd = add i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %badd
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_add_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = add i8 %1, %y
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_add_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %badd = add i8 %y, 2
  %select = select i1 %cmp, i8 %badd, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_add_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = add i8 %1, %y
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_or_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %bor = or i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %bor
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_or_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = or i8 %1, %y
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_or_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %bor = or i8 %y, 2
  %select = select i1 %cmp, i8 %bor, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_or_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = or i8 %1, %y
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_xor_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %bxor = xor i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %bxor
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_xor_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = xor i8 %1, %y
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_xor_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %bxor = xor i8 %y, 2
  %select = select i1 %cmp, i8 %bxor, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_xor_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = xor i8 %1, %y
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_mul_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %bmul = mul i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %bmul
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_mul_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = and i8 %x, 1
  %select = shl i8 %y, %and
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_mul_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %bmul = mul i8 %y, 2
  %select = select i1 %cmp, i8 %bmul, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_mul_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = and i8 %x, 1
  %select = shl i8 %y, %and
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_and_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %band = and i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %band
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_and_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %band = and i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %band
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_and_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %band = and i8 %y, 2
  %select = select i1 %cmp, i8 %band, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_and_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = and i8 %x, 1
  %cmp.not = icmp eq i8 %and, 0
  %band = and i8 %y, 2
  %select = select i1 %cmp.not, i8 %y, i8 %band
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_sub_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %bsub = sub i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %bsub
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_sub_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %bsub = add i8 %y, 254
  %select = select i1 %cmp, i8 %y, i8 %bsub
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_sub_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %bsub = sub i8 %y, 2
  %select = select i1 %cmp, i8 %bsub, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_sub_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = and i8 %x, 1
  %cmp.not = icmp eq i8 %and, 0
  %bsub = add i8 %y, 254
  %select = select i1 %cmp.not, i8 %y, i8 %bsub
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_shl_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %bshl = shl i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %bshl
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_shl_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = shl i8 %y, %1
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_shl_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %bshl = shl i8 %y, 2
  %select = select i1 %cmp, i8 %bshl, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_shl_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = shl i8 %y, %1
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_lshr_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %blshr = lshr i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %blshr
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_lshr_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = lshr i8 %y, %1
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_lshr_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %blshr = lshr i8 %y, 2
  %select = select i1 %cmp, i8 %blshr, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_lshr_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = lshr i8 %y, %1
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_ashr_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %bashr = ashr i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %bashr
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_ashr_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = ashr i8 %y, %1
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_ashr_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %bashr = ashr i8 %y, 2
  %select = select i1 %cmp, i8 %bashr, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_ashr_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = shl i8 %x, 1
  %1 = and i8 %and, 2
  %select = ashr i8 %y, %1
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_sdiv_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %bsdiv = sdiv i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %bsdiv
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_sdiv_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %bsdiv = sdiv i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %bsdiv
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_sdiv_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %bsdiv = sdiv i8 %y, 2
  %select = select i1 %cmp, i8 %bsdiv, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_sdiv_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = and i8 %x, 1
  %cmp.not = icmp eq i8 %and, 0
  %bsdiv = sdiv i8 %y, 2
  %select = select i1 %cmp.not, i8 %y, i8 %bsdiv
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_udiv_fv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp eq i8 %and, 0
  %budiv = udiv i8 %y, 2
  %select = select i1 %cmp, i8 %y, i8 %budiv
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_udiv_fv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = and i8 %x, 1
  %select = lshr i8 %y, %and
  ret i8 %select
}
Transformation seems to be correct!


----------------------------------------
define i8 @select_icmp_eq_and_1_0_udiv_tv(i8 %x, i8 %y) {
%0:
  %and = and i8 %x, 1
  %cmp = icmp ne i8 %and, 0
  %budiv = udiv i8 %y, 2
  %select = select i1 %cmp, i8 %budiv, i8 %y
  ret i8 %select
}
=>
define i8 @select_icmp_eq_and_1_0_udiv_tv(i8 %x, i8 %y) nofree willreturn memory(none) {
%0:
  %and = and i8 %x, 1
  %select = lshr i8 %y, %and
  ret i8 %select
}
Transformation seems to be correct!

Summary:
  22 correct transformations
  0 incorrect transformations
  0 failed-to-prove transformations
  0 Alive2 errors

[goldstein.w.n]

Don't commute V and Y when creating final binop

[chapuni]

Thanks for the fix.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

655–660

Could you update expressions in the comment please?

[goldstein.w.n]

Update comment

[goldstein.w.n]

Okay for push this for attempt #3?

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

if (match(TrueVal, m_LShr(m_Value(X), m_Value(Y))) &&
     bool IsExact = Ashr->isExact() && cast<Instruction>(TrueVal)->isExact();
     return Builder.CreateAShr(X, Y, IC->getName(), IsExact);
   }
 
   return nullptr;
 }
 
 /// We want to turn:
-///   (select (icmp eq (and X, C1), 0), Y, (or Y, C2))
+///   (select (icmp eq (and X, C1), 0), Y, (BinOp Y, C2))
 /// into:
-///   (or (shl (and X, C1), C3), Y)
+///   IF C2 u>= C1
+///     (BinOp (shl (and X, C1), C3), Y)
+///   ELSE
+///     (BinOp (lshr (and X, C1), C3), Y)
 /// iff:
+///   0 on the RHS is the identity value (i.e add, xor, shl, etc...)
 ///   C1 and C2 are both powers of 2
 /// where:
-///   C3 = Log(C2) - Log(C1)
+///   IF C2 u>= C1
+///     C3 = Log(C2) - Log(C1)
+///   ELSE
+///     C3 = Log(C1) - Log(C2)
 ///
 /// This transform handles cases where:
 /// 1. The icmp predicate is inverted
 /// 2. The select operands are reversed
 /// 3. The magnitude of C2 and C1 are flipped
-static Value *foldSelectICmpAndOr(const ICmpInst *IC, Value *TrueVal,
+static Value *foldSelectICmpAndBinOp(const ICmpInst *IC, Value *TrueVal,
                                   Value *FalseVal,
                                   InstCombiner::BuilderTy &Builder) {
   // Only handle integer compares. Also, if this is a vector select, we need a
   // vector compare.
   if (!TrueVal->getType()->isIntOrIntVectorTy() ||
-      TrueVal->getType()->isVectorTy() != IC->getType()->isVectorTy())
     return nullptr;
 
   Value *CmpLHS = IC->getOperand(0);
   Value *CmpRHS = IC->getOperand(1);
 
   unsigned C1Log;
   bool NeedAnd = false;
   CmpInst::Predicate Pred = IC->getPredicate();
if (IC->isEquality()) {
     if (!decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, CmpLHS, C1) ||
         !C1.isPowerOf2())
       return nullptr;
 
     C1Log = C1.logBase2();
     NeedAnd = true;
   }
 
-  Value *Or, *Y, *V = CmpLHS;
+  Value *Y, *V = CmpLHS;
+  BinaryOperator *BinOp;
   const APInt *C2;
   bool NeedXor;
-  if (match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)))) {
+  if (match(FalseVal, m_BinOp(m_Specific(TrueVal), m_Power2(C2)))) {
     Y = TrueVal;
-    Or = FalseVal;
+    BinOp = cast<BinaryOperator>(FalseVal);
     NeedXor = Pred == ICmpInst::ICMP_NE;
-  } else if (match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2)))) {
+  } else if (match(TrueVal, m_BinOp(m_Specific(FalseVal), m_Power2(C2)))) {
     Y = FalseVal;
-    Or = TrueVal;
+    BinOp = cast<BinaryOperator>(TrueVal);
     NeedXor = Pred == ICmpInst::ICMP_EQ;
   } else {
     return nullptr;
   }
 
+  // Check that 0 on RHS is identity value for this binop.
+  if (!ConstantExpr::getBinOpIdentity(BinOp->getOpcode(), BinOp->getType(),
+                                      /*AllowRHSConstant*/ true)
+           ->isNullValue())
+    return nullptr;
+
   unsigned C2Log = C2->logBase2();
 
   bool NeedShift = C1Log != C2Log;
   bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() !=
                        V->getType()->getScalarSizeInBits();
 
   // Make sure we don't create more instructions than we save.
   if ((NeedShift + NeedXor + NeedZExtTrunc + NeedAnd) >
-      (IC->hasOneUse() + Or->hasOneUse()))
+      (IC->hasOneUse() + BinOp->hasOneUse()))
     return nullptr;
 
   if (NeedAnd) {
     // Insert the AND instruction on the input to the truncate.
     APInt C1 = APInt::getOneBitSet(V->getType()->getScalarSizeInBits(), C1Log);
     V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), C1));
   }
 
   if (C2Log > C1Log) {
     V = Builder.CreateZExtOrTrunc(V, Y->getType());
     V = Builder.CreateShl(V, C2Log - C1Log);
   } else if (C1Log > C2Log) {
     V = Builder.CreateLShr(V, C1Log - C2Log);
     V = Builder.CreateZExtOrTrunc(V, Y->getType());
   } else
     V = Builder.CreateZExtOrTrunc(V, Y->getType());
 
   if (NeedXor)
     V = Builder.CreateXor(V, *C2);
 
-  return Builder.CreateOr(V, Y);
+  return Builder.CreateBinOp(BinOp->getOpcode(), V, Y);
 }
 
 /// Canonicalize a set or clear of a masked set of constant bits to
 /// select-of-constants form.
 static Instruction *foldSetClearBits(SelectInst &Sel,
                                      InstCombiner::BuilderTy &Builder) {
   Value *Cond = Sel.getCondition();
   Value *T = Sel.getTrueValue();
if (Instruction *V =
     return V;
 
   if (Instruction *V = foldSelectCtlzToCttz(ICI, TrueVal, FalseVal, Builder))
     return V;
 
   if (Instruction *V = foldSelectZeroOrOnes(ICI, TrueVal, FalseVal, Builder))
     return V;
 
-  if (Value *V = foldSelectICmpAndOr(ICI, TrueVal, FalseVal, Builder))
+  if (Value *V = foldSelectICmpAndBinOp(ICI, TrueVal, FalseVal, Builder))
     return replaceInstUsesWith(SI, V);
 
   if (Value *V = foldSelectICmpLshrAshr(ICI, TrueVal, FalseVal, Builder))
     return replaceInstUsesWith(SI, V);
 
   if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
     return replaceInstUsesWith(SI, V);
 

llvm/test/Transforms/InstCombine/select-with-bitwise-ops.ll

;
   %cmp = icmp eq <2 x i32> %and, zeroinitializer
   %or = or <2 x i32> %y, <i32 2, i32 2>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
 }
 
 define i32 @select_icmp_eq_and_1_0_xor_2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_eq_and_1_0_xor_2(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 2
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[XOR]]
+; CHECK-NEXT:    [[AND:%.*]] = shl i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 2
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[SELECT]]
 ;
   %and = and i32 %x, 1
   %cmp = icmp eq i32 %and, 0
   %xor = xor i32 %y, 2
   %select = select i1 %cmp, i32 %y, i32 %xor
   ret i32 %select
 }
;
   %cmp = icmp eq <2 x i32> %and, zeroinitializer
   %or = or <2 x i32> %y, <i32 8, i32 8>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
 }
 
 define i32 @select_icmp_eq_and_32_0_xor_8(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_eq_and_32_0_xor_8(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 32
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 8
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[XOR]]
+; CHECK-NEXT:    [[AND:%.*]] = lshr i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 8
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[SELECT]]
 ;
   %and = and i32 %x, 32
   %cmp = icmp eq i32 %and, 0
   %xor = xor i32 %y, 8
   %select = select i1 %cmp, i32 %y, i32 %xor
   ret i32 %select
 }
;
   %or = or <2 x i32> %y, <i32 4096, i32 4096>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
 }
 
 define i32 @select_icmp_ne_0_and_4096_xor_4096(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_ne_0_and_4096_xor_4096(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 4096
-; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 4096
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP_NOT]], i32 [[XOR]], i32 [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[AND]], [[Y:%.*]]
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP1]], 4096
 ; CHECK-NEXT:    ret i32 [[SELECT]]
 ;
   %and = and i32 %x, 4096
   %cmp = icmp ne i32 0, %and
   %xor = xor i32 %y, 4096
   %select = select i1 %cmp, i32 %y, i32 %xor
   ret i32 %select
 }
;
   %or = or <2 x i32> %y, <i32 4096, i32 4096>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
 }
 
 define i32 @select_icmp_eq_and_4096_0_xor_4096(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_eq_and_4096_0_xor_4096(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 4096
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 4096
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[XOR]]
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[AND]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[SELECT]]
 ;
   %and = and i32 %x, 4096
   %cmp = icmp eq i32 %and, 0
   %xor = xor i32 %y, 4096
   %select = select i1 %cmp, i32 %y, i32 %xor
   ret i32 %select
 }
;
   %or = or <2 x i32> %y, <i32 1, i32 1>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
 }
 
 define i32 @select_icmp_eq_0_and_1_xor_1(i64 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_eq_0_and_1_xor_1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[X:%.*]] to i32
-; CHECK-NEXT:    [[XOR:%.*]] = and i32 [[TMP1]], 1
-; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[XOR]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 1
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP2]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[SELECT]]
 ;
   %and = and i64 %x, 1
   %cmp = icmp eq i64 %and, 0
   %xor = xor i32 %y, 1
   %select = select i1 %cmp, i32 %y, i32 %xor
   ret i32 %select
 }
;
   %cmp = icmp ne i32 0, %and
   %or = or i32 %y, 32
   %select = select i1 %cmp, i32 %y, i32 %or
   ret i32 %select
 }
 
 define i32 @select_icmp_ne_0_and_4096_xor_32(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_ne_0_and_4096_xor_32(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 4096
-; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 32
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP_NOT]], i32 [[XOR]], i32 [[Y]]
+; CHECK-NEXT:    [[AND:%.*]] = lshr i32 [[X:%.*]], 7
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 32
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP2]], 32
 ; CHECK-NEXT:    ret i32 [[SELECT]]
 ;
   %and = and i32 %x, 4096
   %cmp = icmp ne i32 0, %and
   %xor = xor i32 %y, 32
   %select = select i1 %cmp, i32 %y, i32 %xor
   ret i32 %select
 }
;
   %cmp = icmp ne <2 x i32> zeroinitializer, %and
   %or = or <2 x i32> %y, <i32 4096, i32 4096>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
 }
 
 define i32 @select_icmp_ne_0_and_32_xor_4096(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_ne_0_and_32_xor_4096(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 32
-; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 4096
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP_NOT]], i32 [[XOR]], i32 [[Y]]
+; CHECK-NEXT:    [[AND:%.*]] = shl i32 [[X:%.*]], 7
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 4096
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP2]], 4096
 ; CHECK-NEXT:    ret i32 [[SELECT]]
 ;
   %and = and i32 %x, 32
   %cmp = icmp ne i32 0, %and
   %xor = xor i32 %y, 4096
   %select = select i1 %cmp, i32 %y, i32 %xor
   ret i32 %select
 }
;
   %xor = xor i32 %x, 8
   %xor.x = select i1 %cmp, i32 %xor, i32 %x
   ret i32 %xor.x
 }
 
 define i64 @select_icmp_x_and_8_eq_0_y_xor_8(i32 %x, i64 %y) {
 ; CHECK-LABEL: @select_icmp_x_and_8_eq_0_y_xor_8(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 8
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[Y:%.*]], 8
-; CHECK-NEXT:    [[Y_XOR:%.*]] = select i1 [[CMP]], i64 [[Y]], i64 [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[AND]] to i64
+; CHECK-NEXT:    [[Y_XOR:%.*]] = xor i64 [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i64 [[Y_XOR]]
 ;
   %and = and i32 %x, 8
   %cmp = icmp eq i32 %and, 0
   %xor = xor i64 %y, 8
   %y.xor = select i1 %cmp, i64 %y, i64 %xor
   ret i64 %y.xor
 }
 
 define i64 @select_icmp_x_and_8_ne_0_y_xor_8(i32 %x, i64 %y) {
 ; CHECK-LABEL: @select_icmp_x_and_8_ne_0_y_xor_8(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 8
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[Y:%.*]], 8
-; CHECK-NEXT:    [[XOR_Y:%.*]] = select i1 [[CMP]], i64 [[XOR]], i64 [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[AND]], 8
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[TMP1]] to i64
+; CHECK-NEXT:    [[XOR_Y:%.*]] = xor i64 [[TMP2]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i64 [[XOR_Y]]
 ;
   %and = and i32 %x, 8
   %cmp = icmp eq i32 %and, 0
   %xor = xor i64 %y, 8
   %xor.y = select i1 %cmp, i64 %xor, i64 %y
   ret i64 %xor.y
 }
;
   %cmp = icmp eq <2 x i32> %and, zeroinitializer
   %or = or <2 x i32> %y, <i32 2, i32 2>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
 }
 
 define i32 @test68_xor(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test68_xor(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 128
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 2
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[XOR]]
+; CHECK-NEXT:    [[AND:%.*]] = lshr i32 [[X:%.*]], 6
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 2
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[SELECT]]
 ;
   %and = and i32 %x, 128
   %cmp = icmp eq i32 %and, 0
   %xor = xor i32 %y, 2
   %select = select i1 %cmp, i32 %y, i32 %xor
   ret i32 %select
 }
;
   %cmp = icmp ne <2 x i32> %and, zeroinitializer
   %or = or <2 x i32> %y, <i32 2, i32 2>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
 }
 
 define i32 @test69_xor(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test69_xor(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 128
-; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 2
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP_NOT]], i32 [[XOR]], i32 [[Y]]
+; CHECK-NEXT:    [[AND:%.*]] = lshr i32 [[X:%.*]], 6
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP2]], 2
 ; CHECK-NEXT:    ret i32 [[SELECT]]
 ;
   %and = and i32 %x, 128
   %cmp = icmp ne i32 %and, 0
   %xor = xor i32 %y, 2
   %select = select i1 %cmp, i32 %y, i32 %xor
   ret i32 %select
 }
;
   %or = or i32 %y, 2
   %select = select i1 %cmp, i32 %y, i32 %or
   %res = mul i32 %select, %or ; to bump up use count of the Or
   ret i32 %res
 }
 
 define i32 @shift_no_xor_multiuse_xor(i32 %x, i32 %y) {
 ; CHECK-LABEL: @shift_no_xor_multiuse_xor(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 2
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[XOR]]
+; CHECK-NEXT:    [[AND:%.*]] = shl i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 2
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP1]], [[Y]]
 ; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[SELECT]], [[XOR]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %and = and i32 %x, 1
   %cmp = icmp eq i32 %and, 0
   %xor = xor i32 %y, 2
   %select = select i1 %cmp, i32 %y, i32 %xor
   %res = mul i32 %select, %xor ; to bump up use count of the Xor
;
   %select = select i1 %cmp, i32 %y, i32 %or
   %res = mul i32 %select, %or ; to bump up use count of the Or
   ret i32 %res
 }
 
 define i32 @no_shift_no_xor_multiuse_xor(i32 %x, i32 %y) {
 ; CHECK-LABEL: @no_shift_no_xor_multiuse_xor(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 4096
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 4096
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[XOR]]
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[AND]], [[Y]]
 ; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[SELECT]], [[XOR]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %and = and i32 %x, 4096
   %cmp = icmp eq i32 %and, 0
   %xor = xor i32 %y, 4096
   %select = select i1 %cmp, i32 %y, i32 %xor
   %res = mul i32 %select, %xor ; to bump up use count of the Xor
;
   %select = select i1 %cmp, i32 %y, i32 %or
   %res = mul i32 %select, %or ; to bump up use count of the Or
   ret i32 %res
 }
 
 define i32 @no_shift_xor_multiuse_xor(i32 %x, i32 %y) {
 ; CHECK-LABEL: @no_shift_xor_multiuse_xor(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 4096
-; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 4096
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP_NOT]], i32 [[XOR]], i32 [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[AND]], [[Y]]
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP1]], 4096
 ; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[SELECT]], [[XOR]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %and = and i32 %x, 4096
   %cmp = icmp ne i32 0, %and
   %xor = xor i32 %y, 4096
   %select = select i1 %cmp, i32 %y, i32 %xor
   %res = mul i32 %select, %xor ; to bump up use count of the Xor
;
   %res = mul i32 %select, %select2
   ret i32 %res
 }
 
 define i32 @shift_no_xor_multiuse_cmp_with_xor(i32 %x, i32 %y, i32 %z, i32 %w) {
 ; CHECK-LABEL: @shift_no_xor_multiuse_cmp_with_xor(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 2
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 [[AND]], 1
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP]], i32 [[Z:%.*]], i32 [[W:%.*]]
 ; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[SELECT]], [[SELECT2]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %and = and i32 %x, 1
   %cmp = icmp eq i32 %and, 0
   %xor = xor i32 %y, 2
   %select = select i1 %cmp, i32 %y, i32 %xor
;
   %res = mul i32 %select, %select2
   ret i32 %res
 }
 
 define i32 @no_shift_no_xor_multiuse_cmp_with_xor(i32 %x, i32 %y, i32 %z, i32 %w) {
 ; CHECK-LABEL: @no_shift_no_xor_multiuse_cmp_with_xor(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 4096
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 4096
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[XOR]]
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[AND]], [[Y:%.*]]
 ; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP]], i32 [[Z:%.*]], i32 [[W:%.*]]
 ; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[SELECT]], [[SELECT2]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %and = and i32 %x, 4096
   %cmp = icmp eq i32 %and, 0
   %xor = xor i32 %y, 4096
   %select = select i1 %cmp, i32 %y, i32 %xor
;
   %res = mul i32 %select, %select2
   ret i32 %res
 }
 
 define i32 @no_shift_xor_multiuse_cmp_with_xor(i32 %x, i32 %y, i32 %z, i32 %w) {
 ; CHECK-LABEL: @no_shift_xor_multiuse_cmp_with_xor(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 4096
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 4096
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP_NOT]], i32 [[XOR]], i32 [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[AND]], [[Y:%.*]]
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[TMP1]], 4096
 ; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP_NOT]], i32 [[W:%.*]], i32 [[Z:%.*]]
 ; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[SELECT]], [[SELECT2]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %and = and i32 %x, 4096
   %cmp = icmp ne i32 0, %and
   %xor = xor i32 %y, 4096
   %select = select i1 %cmp, i32 %y, i32 %xor
;
   ret i32 %res2
 }
 
 define i32 @no_shift_no_xor_multiuse_cmp_xor(i32 %x, i32 %y, i32 %z, i32 %w) {
 ; CHECK-LABEL: @no_shift_no_xor_multiuse_cmp_xor(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 4096
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y:%.*]], 4096
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[XOR]]
+; CHECK-NEXT:    [[SELECT:%.*]] = xor i32 [[AND]], [[Y]]
 ; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP]], i32 [[Z:%.*]], i32 [[W:%.*]]
 ; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[SELECT]], [[SELECT2]]
 ; CHECK-NEXT:    [[RES2:%.*]] = mul i32 [[RES]], [[XOR]]
 ; CHECK-NEXT:    ret i32 [[RES2]]
 ;
   %and = and i32 %x, 4096
   %cmp = icmp eq i32 %and, 0
   %xor = xor i32 %y, 4096
;
   %cmp = icmp eq i8 %xx, 0
   %z = xor i64 %y, -9223372036854775808
   %r = select i1 %cmp, i64 %z, i64 %y
   ret i64 %r
 }
 
 define i64 @xor_i8_to_i64_shl_save_and_ne(i8 %x, i64 %y) {
 ; CHECK-LABEL: @xor_i8_to_i64_shl_save_and_ne(
-; CHECK-NEXT:    [[XX:%.*]] = and i8 [[X:%.*]], 1
-; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[XX]], 0
-; CHECK-NEXT:    [[Z:%.*]] = xor i64 [[Y:%.*]], -9223372036854775808
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP_NOT]], i64 [[Y]], i64 [[Z]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i64 [[TMP1]], 63
+; CHECK-NEXT:    [[R:%.*]] = xor i64 [[TMP2]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i64 [[R]]
 ;
   %xx = and i8 %x, 1
   %cmp = icmp ne i8 %xx, 0
   %z = xor i64 %y, -9223372036854775808
   %r = select i1 %cmp, i64 %z, i64 %y
   ret i64 %r
 }