[X86] combineAddOrSubToADCOrSBB - Fold ADD/SUB + (AND(SRL(X,Y),1) -> ADC/SBB+BT(X,Y)

[RKSimon]

Summary

As suggested on PR35908, if we are adding/subtracting an extracted bit, attempt to use BT instead to fold the op and use a ADC/SBB op.

[pengfei]

attempt to use BT instead to fold the op and use a ADC/SBB op

Ues bit test to replace BT?

llvm/lib/Target/X86/X86ISelLowering.cpp

52303

Add parentheses to match with if block.

llvm/test/CodeGen/X86/add-sub-bool.ll

155

So the test actually tests for %x - (%y - bool(%z & (1 << 30))? The name seems misleading which implies it tests for test_sub in PR35256.

[craig.topper]

Is this still an interesting optimization if the ISD::SRL doesn't exist? Replacing (and X, 1) with bt X, 0 to get the carry flag?

[RKSimon]

In D122084#3394717, @craig.topper wrote:

Is this still an interesting optimization if the ISD::SRL doesn't exist? Replacing (and X, 1) with bt X, 0 to get the carry flag?

Yes, we have special cases for both the lsb and msb bits that don't get matched yet as LowerAndToBT doesn't currently handle them. I have a test for the msb case, but not the lsb one.

llvm/test/CodeGen/X86/add-sub-bool.ll

155

Sorry, I was trying to test all permutations of the adds/subs to see whether any folds stall further optimizations. I'll update the comment at the top.

[RKSimon]

address feedback

[RKSimon]

llvm/test/CodeGen/X86/add-sub-bool.ll

155

Ah - this is actually testing another yet combo, not the basic SBB pattern - I'll address this later

[pengfei]

LGTM.

[gulfem]

This patch has caused a segmentation fault in our builders:
https://ci.chromium.org/ui/p/fuchsia/builders/prod/clang-linux-x64/b8819074785049801761/overview

[2784/4086] Linking CXX executable bin/clang-ast-dump
FAILED: bin/clang-ast-dump 
: && /b/s/w/ir/x/w/staging/llvm_build/./bin/clang++ --sysroot=/b/s/w/ir/x/w/cipd/linux -stdlib=libc++ -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 -Wno-comment -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -ffunction-sections -fdata-sections -flto -ffile-prefix-map=/b/s/w/ir/x/w/staging/llvm_build/tools/clang/stage2-bins=../staging/llvm_build/tools/clang/stage2-bins -ffile-prefix-map=/b/s/w/ir/x/w/llvm-llvm-project/= -no-canonical-prefixes -fno-common -Woverloaded-virtual -Wno-nested-anon-types -O3 -DNDEBUG -static-libstdc++ -stdlib=libc++ -static-libstdc++ -fuse-ld=lld -Wl,--color-diagnostics -flto    -Wl,--lto-O0 -Wl,--gc-sections tools/clang/lib/Tooling/DumpTool/CMakeFiles/clang-ast-dump.dir/ASTSrcLocProcessor.cpp.o tools/clang/lib/Tooling/DumpTool/CMakeFiles/clang-ast-dump.dir/ClangSrcLocDump.cpp.o -o bin/clang-ast-dump  -Wl,-rpath,"\$ORIGIN/../lib"  lib/libLLVMOption.a  lib/libLLVMFrontendOpenMP.a  lib/libLLVMSupport.a  -lpthread  lib/libclangAST.a  lib/libclangASTMatchers.a  lib/libclangBasic.a  lib/libclangDriver.a  lib/libclangFrontend.a  lib/libclangSerialization.a  lib/libclangToolingCore.a  lib/libclangDriver.a  lib/libLLVMWindowsDriver.a  lib/libLLVMOption.a  lib/libclangParse.a  lib/libclangSema.a  lib/libclangEdit.a  lib/libclangAnalysis.a  lib/libclangASTMatchers.a  lib/libclangAST.a  lib/libLLVMFrontendOpenMP.a  lib/libLLVMScalarOpts.a  lib/libLLVMAggressiveInstCombine.a  lib/libLLVMInstCombine.a  lib/libLLVMTransformUtils.a  lib/libLLVMAnalysis.a  lib/libLLVMProfileData.a  lib/libLLVMSymbolize.a  lib/libLLVMDebugInfoPDB.a  lib/libLLVMDebugInfoMSF.a  lib/libLLVMDebugInfoDWARF.a  lib/libtf_xla_runtime.a  lib/Analysis/InlinerSizeModel.o  lib/libLLVMObject.a  lib/libLLVMMCParser.a  lib/libLLVMMC.a  lib/libLLVMDebugInfoCodeView.a  lib/libLLVMTextAPI.a  lib/libLLVMBitReader.a  lib/libLLVMCore.a  lib/libLLVMBinaryFormat.a  lib/libLLVMRemarks.a  lib/libLLVMBitstreamReader.a  lib/libclangRewrite.a  lib/libclangLex.a  lib/libclangBasic.a  lib/libLLVMSupport.a  -lrt  -ldl  -lpthread  -lm  /b/s/w/ir/x/w/staging/zlib_install/lib/libz.a  lib/libLLVMDemangle.a && :
clang++: error: unable to execute command: Segmentation fault

After debugging it a little, I'm seeing this trace:

Do not know how to promote this operator's operand!
UNREACHABLE executed at llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp:1580!
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /usr/local/google/home/gulfem/clang-ci-x64-relwith-debug-info-build/bin/ld.lld --sysroot=/usr/local/google/home/gulfem/fuchsia-sysroot --build-id --eh-frame-hdr -m elf_x86_64 -dynamic-linker /lib64/ld-linux-x86-64.so.2 -o bin/clang-ast-dump /usr/local/google/home/gulfem/fuchsia-sysroot/usr/lib/x86_64-linux-gnu/crt1.o /usr/local/google/home/gulfem/fuchsia-sysroot/usr/lib/x86_64-linux-gnu/crti.o /usr/local/google/home/gulfem/clang-ci-x64-relwith-debug-info-build/lib/clang/15.0.0/lib/x86_64-unknown-linux-gnu/clang_rt.crtbegin.o -L/usr/local/google/home/gulfem/clang-ci-x64-relwith-debug-info-build/bin/../lib/x86_64-unknown-linux-gnu -L/usr/local/google/home/gulfem/fuchsia-sysroot/usr/lib/gcc/x86_64-linux-gnu/8 -L/usr/local/google/home/gulfem/fuchsia-sysroot/lib/x86_64-linux-gnu -L/usr/local/google/home/gulfem/fuchsia-sysroot/lib/../lib64 -L/usr/local/google/home/gulfem/fuchsia-sysroot/usr/lib/x86_64-linux-gnu -L/usr/local/google/home/gulfem/fuchsia-sysroot/lib -L/usr/local/google/home/gulfem/fuchsia-sysroot/usr/lib -plugin-opt=mcpu=x86-64 -plugin-opt=O3 -plugin-opt=-function-sections -plugin-opt=-data-sections --color-diagnostics --lto-O0 --gc-sections tools/clang/lib/Tooling/DumpTool/CMakeFiles/clang-ast-dump.dir/ASTSrcLocProcessor.cpp.o tools/clang/lib/Tooling/DumpTool/CMakeFiles/clang-ast-dump.dir/ClangSrcLocDump.cpp.o -rpath $ORIGIN/../lib lib/libLLVMOption.a lib/libLLVMFrontendOpenMP.a lib/libLLVMSupport.a -lpthread lib/libclangAST.a lib/libclangASTMatchers.a lib/libclangBasic.a lib/libclangDriver.a lib/libclangFrontend.a lib/libclangSerialization.a lib/libclangToolingCore.a lib/libclangDriver.a lib/libLLVMWindowsDriver.a lib/libLLVMOption.a lib/libclangParse.a lib/libclangSema.a lib/libclangEdit.a lib/libclangAnalysis.a lib/libclangASTMatchers.a lib/libclangAST.a lib/libLLVMFrontendOpenMP.a lib/libLLVMScalarOpts.a lib/libLLVMAggressiveInstCombine.a lib/libLLVMInstCombine.a lib/libLLVMTransformUtils.a lib/libLLVMAnalysis.a lib/libLLVMProfileData.a lib/libLLVMSymbolize.a lib/libLLVMDebugInfoPDB.a lib/libLLVMDebugInfoMSF.a lib/libLLVMDebugInfoDWARF.a lib/libLLVMObject.a lib/libLLVMMCParser.a lib/libLLVMMC.a lib/libLLVMDebugInfoCodeView.a lib/libLLVMTextAPI.a lib/libLLVMBitReader.a lib/libLLVMCore.a lib/libLLVMBinaryFormat.a lib/libLLVMRemarks.a lib/libLLVMBitstreamReader.a lib/libclangRewrite.a lib/libclangLex.a lib/libclangBasic.a lib/libLLVMSupport.a -lrt -ldl -lpthread -lm lib/libLLVMDemangle.a -Bstatic -lc++ -Bdynamic -lm /usr/local/google/home/gulfem/clang-ci-x64-relwith-debug-info-build/lib/clang/15.0.0/lib/x86_64-unknown-linux-gnu/libclang_rt.builtins.a -lc /usr/local/google/home/gulfem/clang-ci-x64-relwith-debug-info-build/lib/clang/15.0.0/lib/x86_64-unknown-linux-gnu/libcl
ang_rt.builtins.a /usr/local/google/home/gulfem/clang-ci-x64-relwith-debug-info-build/lib/clang/15.0.0/lib/x86_64-unknown-linux-gnu/clang_rt.crtend.o /usr/local/google/home/gulfem/fuchsia-sysroot/usr/lib/x86_64-linux-gnu/crtn.o
1.      Running pass 'Function Pass Manager' on module 'ld-temp.o'.
2.      Running pass 'X86 DAG->DAG Instruction Selection' on function '@_ZN5clang4Stmt8childrenEv'
#0 0x0000000001d7d04d llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) ../../clang-ci-x64-relwith-debug-info-build/llvm/lib/Support/Unix/Signals.inc:573:8
#1 0x0000000001d7d04d PrintStackTraceSignalHandler(void*) ../../clang-ci-x64-relwith-debug-info-build/llvm/lib/Support/Unix/Signals.inc:631:3
clang++: error: unable to execute command: Aborted
clang++: error: linker command failed due to signal (use -v to see invocation)

[RKSimon]

@gulfem The original patch that I think caused this was reverted and an updated version committed with better type legalization - please can you confirm that fixes the build issues you saw?

[RKSimon]

In D122084#3398800, @RKSimon wrote:

@gulfem The original patch that I think caused this was reverted and an updated version committed with better type legalization - please can you confirm that fixes the build issues you saw?

Looking at https://ci.chromium.org/p/fuchsia/builders/prod/clang-linux-x64 - its looks like the reapplied patch succeeded

[gulfem]

In D122084#3398800, @RKSimon wrote:

@gulfem The original patch that I think caused this was reverted and an updated version committed with better type legalization - please can you confirm that fixes the build issues you saw?

@RKSimon,
I confirm that with your reland (https://github.com/llvm/llvm-project/commit/438ac282db97c584daf2d4d1a90e6b3d49ef9189), we do not see the segmentation fault anymore.

llvm/lib/Target/X86/X86ISelLowering.cpp

if (Divisor.isNonNegative())
     return SRA;
 
   Created.push_back(SRA.getNode());
   return DAG.getNode(ISD::SUB, DL, VT, Zero, SRA);
 }
 
 /// Result of 'and' is compared against zero. Change to a BT node if possible.
 /// Returns the BT node and the condition code needed to use it.
-static SDValue LowerAndToBT(SDValue And, ISD::CondCode CC,
-                            const SDLoc &dl, SelectionDAG &DAG,
-                            SDValue &X86CC) {
+static SDValue LowerAndToBT(SDValue And, ISD::CondCode CC, const SDLoc &dl,
+                            SelectionDAG &DAG, X86::CondCode &X86CC) {
   assert(And.getOpcode() == ISD::AND && "Expected AND node!");
   SDValue Op0 = And.getOperand(0);
   SDValue Op1 = And.getOperand(1);
   if (Op0.getOpcode() == ISD::TRUNCATE)
     Op0 = Op0.getOperand(0);
   if (Op1.getOpcode() == ISD::TRUNCATE)
     Op1 = Op1.getOperand(0);
 
if (Src.getValueType() == MVT::i64 &&
       DAG.MaskedValueIsZero(BitNo, APInt(BitNo.getValueSizeInBits(), 32)))
     Src = DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
 
   // If the operand types disagree, extend the shift amount to match.  Since
   // BT ignores high bits (like shifts) we can use anyextend.
   if (Src.getValueType() != BitNo.getValueType())
     BitNo = DAG.getNode(ISD::ANY_EXTEND, dl, Src.getValueType(), BitNo);
 
-  X86CC = DAG.getTargetConstant(CC == ISD::SETEQ ? X86::COND_AE : X86::COND_B,
-                                dl, MVT::i8);
+  X86CC = CC == ISD::SETEQ ? X86::COND_AE : X86::COND_B;
   return DAG.getNode(X86ISD::BT, dl, MVT::i32, Src, BitNo);
 }
 
 // Check if pre-AVX condcode can be performed by a single FCMP op.
 static bool cheapX86FSETCC_SSE(ISD::CondCode SetCCOpcode) {
   return (SetCCOpcode != ISD::SETONE) && (SetCCOpcode != ISD::SETUEQ);
 }
 
SDValue X86TargetLowering::emitFlagsForSetcc(SDValue Op0, SDValue Op1,
                                              SelectionDAG &DAG,
                                              SDValue &X86CC) const {
   // Optimize to BT if possible.
   // Lower (X & (1 << N)) == 0 to BT(X, N).
   // Lower ((X >>u N) & 1) != 0 to BT(X, N).
   // Lower ((X >>s N) & 1) != 0 to BT(X, N).
   if (Op0.getOpcode() == ISD::AND && Op0.hasOneUse() && isNullConstant(Op1) &&
       (CC == ISD::SETEQ || CC == ISD::SETNE)) {
-    if (SDValue BT = LowerAndToBT(Op0, CC, dl, DAG, X86CC))
+    X86::CondCode X86CondCode;
+    if (SDValue BT = LowerAndToBT(Op0, CC, dl, DAG, X86CondCode)) {
+      X86CC = DAG.getTargetConstant(X86CondCode, dl, MVT::i8);
       return BT;
     }
+  }
 
   // Try to use PTEST/PMOVMSKB for a tree ORs equality compared with 0.
   // TODO: We could do AND tree with all 1s as well by using the C flag.
   if (isNullConstant(Op1) && (CC == ISD::SETEQ || CC == ISD::SETNE))
     if (SDValue CmpZ =
             MatchVectorAllZeroTest(Op0, CC, dl, Subtarget, DAG, X86CC))
       return CmpZ;
 
SDValue X86TargetLowering::LowerSELECT(SDValue Op, SelectionDAG &DAG) const {
   if (AddTest) {
     // Look past the truncate if the high bits are known zero.
     if (isTruncWithZeroHighBitsInput(Cond, DAG))
       Cond = Cond.getOperand(0);
 
     // We know the result of AND is compared against zero. Try to match
     // it to BT.
     if (Cond.getOpcode() == ISD::AND && Cond.hasOneUse()) {
-      SDValue BTCC;
-      if (SDValue BT = LowerAndToBT(Cond, ISD::SETNE, DL, DAG, BTCC)) {
-        CC = BTCC;
+      X86::CondCode X86CondCode;
+      if (SDValue BT = LowerAndToBT(Cond, ISD::SETNE, DL, DAG, X86CondCode)) {
+        CC = DAG.getTargetConstant(X86CondCode, DL, MVT::i8);
         Cond = BT;
         AddTest = false;
       }
     }
   }
 
   if (AddTest) {
     CC = DAG.getTargetConstant(X86::COND_NE, DL, MVT::i8);
return DAG.getNode(X86ISD::ADC, SDLoc(N), N->getVTList(), LHS.getOperand(0),
                        LHS.getOperand(1), CarryIn);
 
   return SDValue();
 }
 
 /// If this is an add or subtract where one operand is produced by a cmp+setcc,
 /// then try to convert it to an ADC or SBB. This replaces TEST+SET+{ADD/SUB}
 /// with CMP+{ADC, SBB}.
+/// Also try (ADD/SUB)+(AND(SRL,1)) bit extraction pattern with BT+{ADC, SBB}.
 static SDValue combineAddOrSubToADCOrSBB(bool IsSub, const SDLoc &DL, EVT VT,
                                          SDValue X, SDValue Y,
                                          SelectionDAG &DAG) {
   // Look through a one-use zext.
   if (Y.getOpcode() == ISD::ZERO_EXTEND && Y.hasOneUse())
     Y = Y.getOperand(0);
 
-  if (Y.getOpcode() != X86ISD::SETCC || !Y.hasOneUse())
+  if (!Y.hasOneUse())
     return SDValue();
 
-  X86::CondCode CC = (X86::CondCode)Y.getConstantOperandVal(0);
-  SDValue EFLAGS = Y.getOperand(1);
+  X86::CondCode CC;
+  SDValue EFLAGS;
+  if (Y.getOpcode() == X86ISD::SETCC) {
+    CC = (X86::CondCode)Y.getConstantOperandVal(0);
+    EFLAGS = Y.getOperand(1);
+  } else if (Y.getOpcode() == ISD::AND && isOneConstant(Y.getOperand(1))) {
+    EFLAGS = LowerAndToBT(Y, ISD::SETNE, DL, DAG, CC);
+  }
+
+  if (!EFLAGS)
+    return SDValue();
 
   // If X is -1 or 0, then we have an opportunity to avoid constants required in
   // the general case below.
   auto *ConstantX = dyn_cast<ConstantSDNode>(X);
   if (ConstantX) {
     if ((!IsSub && CC == X86::COND_AE && ConstantX->isAllOnes()) ||
         (IsSub && CC == X86::COND_B && ConstantX->isZero())) {
       // This is a complicated way to get -1 or 0 from the carry flag:

llvm/test/CodeGen/X86/add-sub-bool.ll

 ;
 ; Constant Bit Indices
 ;
 
 define i32 @test_i32_add_add_idx(i32 %x, i32 %y, i32 %z) {
 ; X86-LABEL: test_i32_add_add_idx:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    addl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    shrl $30, %eax
-; X86-NEXT:    andl $1, %eax
-; X86-NEXT:    addl %ecx, %eax
+; X86-NEXT:    btl $30, {{[0-9]+}}(%esp)
+; X86-NEXT:    adcl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    retl
 ;
-; NOTBM-LABEL: test_i32_add_add_idx:
-; NOTBM:       # %bb.0:
-; NOTBM-NEXT:    # kill: def $esi killed $esi def $rsi
-; NOTBM-NEXT:    # kill: def $edi killed $edi def $rdi
-; NOTBM-NEXT:    leal (%rdi,%rsi), %eax
-; NOTBM-NEXT:    shrl $30, %edx
-; NOTBM-NEXT:    andl $1, %edx
-; NOTBM-NEXT:    addl %edx, %eax
-; NOTBM-NEXT:    retq
-;
-; TBM-LABEL: test_i32_add_add_idx:
-; TBM:       # %bb.0:
-; TBM-NEXT:    # kill: def $esi killed $esi def $rsi
-; TBM-NEXT:    # kill: def $edi killed $edi def $rdi
-; TBM-NEXT:    bextrl $286, %edx, %eax # imm = 0x11E
-; TBM-NEXT:    addl %edi, %eax
-; TBM-NEXT:    addl %esi, %eax
-; TBM-NEXT:    retq
+; X64-LABEL: test_i32_add_add_idx:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    btl $30, %edx
+; X64-NEXT:    adcl %esi, %eax
+; X64-NEXT:    retq
   %add = add i32 %y, %x
   %shift = lshr i32 %z, 30
   %mask = and i32 %shift, 1
   %add1 = add i32 %add, %mask
   ret i32 %add1
 }
 
 define i32 @test_i32_add_add_commute_idx(i32 %x, i32 %y, i32 %z) {
 ; X86-LABEL: test_i32_add_add_commute_idx:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    addl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    shrl $2, %eax
-; X86-NEXT:    andl $1, %eax
-; X86-NEXT:    addl %ecx, %eax
+; X86-NEXT:    btl $2, {{[0-9]+}}(%esp)
+; X86-NEXT:    adcl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    retl
 ;
-; NOTBM-LABEL: test_i32_add_add_commute_idx:
-; NOTBM:       # %bb.0:
-; NOTBM-NEXT:    # kill: def $esi killed $esi def $rsi
-; NOTBM-NEXT:    # kill: def $edi killed $edi def $rdi
-; NOTBM-NEXT:    leal (%rdi,%rsi), %eax
-; NOTBM-NEXT:    shrl $2, %edx
-; NOTBM-NEXT:    andl $1, %edx
-; NOTBM-NEXT:    addl %edx, %eax
-; NOTBM-NEXT:    retq
-;
-; TBM-LABEL: test_i32_add_add_commute_idx:
-; TBM:       # %bb.0:
-; TBM-NEXT:    # kill: def $esi killed $esi def $rsi
-; TBM-NEXT:    # kill: def $edi killed $edi def $rdi
-; TBM-NEXT:    bextrl $258, %edx, %eax # imm = 0x102
-; TBM-NEXT:    addl %edi, %eax
-; TBM-NEXT:    addl %esi, %eax
-; TBM-NEXT:    retq
+; X64-LABEL: test_i32_add_add_commute_idx:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    btl $2, %edx
+; X64-NEXT:    adcl %esi, %eax
+; X64-NEXT:    retq
   %add = add i32 %y, %x
   %shift = lshr i32 %z, 2
   %mask = and i32 %shift, 1
   %add1 = add i32 %mask, %add
   ret i32 %add1
 }
 
 define i32 @test_i32_add_add_idx0(i32 %x, i32 %y, i32 %z) {
; X64-NEXT:    retq
   %add = add i32 %sub, %mask
   ret i32 %add
 }
 
 define i32 @test_i32_add_sub_commute_idx(i32 %x, i32 %y, i32 %z) {
 ; X86-LABEL: test_i32_add_sub_commute_idx:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    subl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    shrl $8, %eax
-; X86-NEXT:    andl $1, %eax
-; X86-NEXT:    addl %ecx, %eax
+; X86-NEXT:    subl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    btl $8, {{[0-9]+}}(%esp)
+; X86-NEXT:    adcl $0, %eax
 ; X86-NEXT:    retl
 ;
-; NOTBM-LABEL: test_i32_add_sub_commute_idx:
-; NOTBM:       # %bb.0:
-; NOTBM-NEXT:    # kill: def $edx killed $edx def $rdx
-; NOTBM-NEXT:    # kill: def $edi killed $edi def $rdi
-; NOTBM-NEXT:    subl %esi, %edi
-; NOTBM-NEXT:    shrl $8, %edx
-; NOTBM-NEXT:    andl $1, %edx
-; NOTBM-NEXT:    leal (%rdx,%rdi), %eax
-; NOTBM-NEXT:    retq
-;
-; TBM-LABEL: test_i32_add_sub_commute_idx:
-; TBM:       # %bb.0:
-; TBM-NEXT:    subl %esi, %edi
-; TBM-NEXT:    bextrl $264, %edx, %eax # imm = 0x108
-; TBM-NEXT:    addl %edi, %eax
-; TBM-NEXT:    retq
+; X64-LABEL: test_i32_add_sub_commute_idx:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    subl %esi, %eax
+; X64-NEXT:    btl $8, %edx
+; X64-NEXT:    adcl $0, %eax
+; X64-NEXT:    retq
   %sub = sub i32 %x, %y
   %shift = lshr i32 %z, 8
   %mask = and i32 %shift, 1
   %add = add i32 %mask, %sub
   ret i32 %add
 }
 
 define i32 @test_i32_sub_add_idx(i32 %x, i32 %y, i32 %z) {
 ; X86-LABEL: test_i32_sub_add_idx:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    shrl %ecx
-; X86-NEXT:    andl $1, %ecx
-; X86-NEXT:    subl %ecx, %eax
+; X86-NEXT:    btl $1, {{[0-9]+}}(%esp)
+; X86-NEXT:    sbbl $0, %eax
 ; X86-NEXT:    retl
 ;
-; NOTBM-LABEL: test_i32_sub_add_idx:
-; NOTBM:       # %bb.0:
-; NOTBM-NEXT:    # kill: def $esi killed $esi def $rsi
-; NOTBM-NEXT:    # kill: def $edi killed $edi def $rdi
-; NOTBM-NEXT:    leal (%rdi,%rsi), %eax
-; NOTBM-NEXT:    shrl %edx
-; NOTBM-NEXT:    andl $1, %edx
-; NOTBM-NEXT:    subl %edx, %eax
-; NOTBM-NEXT:    retq
-;
-; TBM-LABEL: test_i32_sub_add_idx:
-; TBM:       # %bb.0:
-; TBM-NEXT:    # kill: def $esi killed $esi def $rsi
-; TBM-NEXT:    # kill: def $edi killed $edi def $rdi
-; TBM-NEXT:    leal (%rdi,%rsi), %eax
-; TBM-NEXT:    bextrl $257, %edx, %ecx # imm = 0x101
-; TBM-NEXT:    subl %ecx, %eax
-; TBM-NEXT:    retq
+; X64-LABEL: test_i32_sub_add_idx:
+; X64:       # %bb.0:
+; X64-NEXT:    # kill: def $esi killed $esi def $rsi
+; X64-NEXT:    # kill: def $edi killed $edi def $rdi
+; X64-NEXT:    leal (%rdi,%rsi), %eax
+; X64-NEXT:    btl $1, %edx
+; X64-NEXT:    sbbl $0, %eax
+; X64-NEXT:    retq
   %add = add i32 %y, %x
   %shift = lshr i32 %z, 1
   %mask = and i32 %shift, 1
   %sub = sub i32 %add, %mask
   ret i32 %sub
 }
 
 define i32 @test_i32_sub_sub_idx(i32 %x, i32 %y, i32 %z) {
 ; X86-LABEL: test_i32_sub_sub_idx:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    shrl $16, %eax
 ; X86-NEXT:    andl $1, %eax
 ; X86-NEXT:    subl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    retl
; TBM-NEXT:    retq
   %sub1 = sub i32 %x, %sub0
   ret i32 %sub1
 }
 
 define i32 @test_i32_sub_sub_commute_idx(i32 %x, i32 %y, i32 %z) {
 ; X86-LABEL: test_i32_sub_sub_commute_idx:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    shrl $15, %ecx
-; X86-NEXT:    andl $1, %ecx
-; X86-NEXT:    subl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    subl %ecx, %eax
+; X86-NEXT:    btl $15, {{[0-9]+}}(%esp)
+; X86-NEXT:    sbbl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    retl
 ;
-; NOTBM-LABEL: test_i32_sub_sub_commute_idx:
-; NOTBM:       # %bb.0:
-; NOTBM-NEXT:    movl %edi, %eax
-; NOTBM-NEXT:    shrl $15, %edx
-; NOTBM-NEXT:    andl $1, %edx
-; NOTBM-NEXT:    subl %esi, %eax
-; NOTBM-NEXT:    subl %edx, %eax
-; NOTBM-NEXT:    retq
-;
-; TBM-LABEL: test_i32_sub_sub_commute_idx:
-; TBM:       # %bb.0:
-; TBM-NEXT:    movl %edi, %eax
-; TBM-NEXT:    bextrl $271, %edx, %ecx # imm = 0x10F
-; TBM-NEXT:    subl %esi, %eax
-; TBM-NEXT:    subl %ecx, %eax
-; TBM-NEXT:    retq
+; X64-LABEL: test_i32_sub_sub_commute_idx:
+; X64:       # %bb.0:
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    btl $15, %edx
+; X64-NEXT:    sbbl %esi, %eax
+; X64-NEXT:    retq
   %shift = lshr i32 %z, 15
   %mask = and i32 %shift, 1
   %sub0 = sub i32 %x, %y
   %sub1 = sub i32 %sub0, %mask
   ret i32 %sub1
 }
 
 ;
 ; Variable Bit Indices
 ;
 
 define i32 @test_i32_add_add_var(i32 %x, i32 %y, i32 %z, i32 %w) {
 ; X86-LABEL: test_i32_add_add_var:
 ; X86:       # %bb.0:
-; X86-NEXT:    movb {{[0-9]+}}(%esp), %cl
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    addl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    shrl %cl, %eax
-; X86-NEXT:    andl $1, %eax
-; X86-NEXT:    addl %edx, %eax
+; X86-NEXT:    btl %ecx, %edx
+; X86-NEXT:    adcl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_i32_add_add_var:
 ; X64:       # %bb.0:
-; X64-NEXT:    # kill: def $esi killed $esi def $rsi
-; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    leal (%rdi,%rsi), %eax
-; X64-NEXT:    # kill: def $cl killed $cl killed $ecx
-; X64-NEXT:    shrl %cl, %edx
-; X64-NEXT:    andl $1, %edx
-; X64-NEXT:    addl %edx, %eax
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    btl %ecx, %edx
+; X64-NEXT:    adcl %esi, %eax
 ; X64-NEXT:    retq
   %add = add i32 %y, %x
   %shift = lshr i32 %z, %w
   %mask = and i32 %shift, 1
   %add1 = add i32 %add, %mask
   ret i32 %add1
 }
 
 define i32 @test_i32_add_add_commute_var(i32 %x, i32 %y, i32 %z, i32 %w) {
 ; X86-LABEL: test_i32_add_add_commute_var:
 ; X86:       # %bb.0:
-; X86-NEXT:    movb {{[0-9]+}}(%esp), %cl
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    addl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    shrl %cl, %eax
-; X86-NEXT:    andl $1, %eax
-; X86-NEXT:    addl %edx, %eax
+; X86-NEXT:    btl %ecx, %edx
+; X86-NEXT:    adcl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_i32_add_add_commute_var:
 ; X64:       # %bb.0:
-; X64-NEXT:    # kill: def $esi killed $esi def $rsi
-; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    leal (%rdi,%rsi), %eax
-; X64-NEXT:    # kill: def $cl killed $cl killed $ecx
-; X64-NEXT:    shrl %cl, %edx
-; X64-NEXT:    andl $1, %edx
-; X64-NEXT:    addl %edx, %eax
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    btl %ecx, %edx
+; X64-NEXT:    adcl %esi, %eax
 ; X64-NEXT:    retq
   %add = add i32 %y, %x
   %shift = lshr i32 %z, %w
   %mask = and i32 %shift, 1
   %add1 = add i32 %mask, %add
   ret i32 %add1
 }
 
 define i32 @test_i32_add_sub_var(i32 %x, i32 %y, i32 %z, i32 %w) {
 ; X86-LABEL: test_i32_add_sub_var:
 ; X86:       # %bb.0:
-; X86-NEXT:    movb {{[0-9]+}}(%esp), %cl
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    subl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    shrl %cl, %eax
-; X86-NEXT:    andl $1, %eax
-; X86-NEXT:    addl %edx, %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    subl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    btl %ecx, %edx
+; X86-NEXT:    adcl $0, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_i32_add_sub_var:
 ; X64:       # %bb.0:
-; X64-NEXT:    # kill: def $edx killed $edx def $rdx
-; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    subl %esi, %edi
-; X64-NEXT:    # kill: def $cl killed $cl killed $ecx
-; X64-NEXT:    shrl %cl, %edx
-; X64-NEXT:    andl $1, %edx
-; X64-NEXT:    leal (%rdx,%rdi), %eax
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    subl %esi, %eax
+; X64-NEXT:    btl %ecx, %edx
+; X64-NEXT:    adcl $0, %eax
 ; X64-NEXT:    retq
   %sub = sub i32 %x, %y
   %shift = lshr i32 %z, %w
   %mask = and i32 %shift, 1
   %add = add i32 %sub, %mask
   ret i32 %add
 }
 
 define i32 @test_i32_add_sub_commute_var(i32 %x, i32 %y, i32 %z, i32 %w) {
 ; X86-LABEL: test_i32_add_sub_commute_var:
 ; X86:       # %bb.0:
-; X86-NEXT:    movb {{[0-9]+}}(%esp), %cl
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    subl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    shrl %cl, %eax
-; X86-NEXT:    andl $1, %eax
-; X86-NEXT:    addl %edx, %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    subl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    btl %ecx, %edx
+; X86-NEXT:    adcl $0, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_i32_add_sub_commute_var:
 ; X64:       # %bb.0:
-; X64-NEXT:    # kill: def $edx killed $edx def $rdx
-; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    subl %esi, %edi
-; X64-NEXT:    # kill: def $cl killed $cl killed $ecx
-; X64-NEXT:    shrl %cl, %edx
-; X64-NEXT:    andl $1, %edx
-; X64-NEXT:    leal (%rdx,%rdi), %eax
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    subl %esi, %eax
+; X64-NEXT:    btl %ecx, %edx
+; X64-NEXT:    adcl $0, %eax
 ; X64-NEXT:    retq
   %sub = sub i32 %x, %y
   %shift = lshr i32 %z, %w
   %mask = and i32 %shift, 1
   %add = add i32 %mask, %sub
   ret i32 %add
 }
 
 define i32 @test_i32_sub_add_var(i32 %x, i32 %y, i32 %z, i32 %w) {
 ; X86-LABEL: test_i32_sub_add_var:
 ; X86:       # %bb.0:
-; X86-NEXT:    movb {{[0-9]+}}(%esp), %cl
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    shrl %cl, %edx
-; X86-NEXT:    andl $1, %edx
-; X86-NEXT:    subl %edx, %eax
+; X86-NEXT:    btl %ecx, %edx
+; X86-NEXT:    sbbl $0, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_i32_sub_add_var:
 ; X64:       # %bb.0:
 ; X64-NEXT:    # kill: def $esi killed $esi def $rsi
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
 ; X64-NEXT:    leal (%rdi,%rsi), %eax
-; X64-NEXT:    # kill: def $cl killed $cl killed $ecx
-; X64-NEXT:    shrl %cl, %edx
-; X64-NEXT:    andl $1, %edx
-; X64-NEXT:    subl %edx, %eax
+; X64-NEXT:    btl %ecx, %edx
+; X64-NEXT:    sbbl $0, %eax
 ; X64-NEXT:    retq
   %add = add i32 %y, %x
   %shift = lshr i32 %z, %w
   %mask = and i32 %shift, 1
   %sub = sub i32 %add, %mask
   ret i32 %sub
 }
 
; X64-NEXT:    retq
   %sub1 = sub i32 %x, %sub0
   ret i32 %sub1
 }
 
 define i32 @test_i32_sub_sub_commute_var(i32 %x, i32 %y, i32 %z, i32 %w) {
 ; X86-LABEL: test_i32_sub_sub_commute_var:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movb {{[0-9]+}}(%esp), %cl
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    shrl %cl, %edx
-; X86-NEXT:    andl $1, %edx
-; X86-NEXT:    subl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    subl %edx, %eax
+; X86-NEXT:    btl %ecx, %edx
+; X86-NEXT:    sbbl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_i32_sub_sub_commute_var:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    # kill: def $cl killed $cl killed $ecx
-; X64-NEXT:    shrl %cl, %edx
-; X64-NEXT:    andl $1, %edx
-; X64-NEXT:    subl %esi, %eax
-; X64-NEXT:    subl %edx, %eax
+; X64-NEXT:    btl %ecx, %edx
+; X64-NEXT:    sbbl %esi, %eax
 ; X64-NEXT:    retq
   %shift = lshr i32 %z, %w
   %mask = and i32 %shift, 1
   %sub0 = sub i32 %x, %y
   %sub1 = sub i32 %sub0, %mask
   ret i32 %sub1
 }