Page MenuHomePhabricator

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

Authored by RKSimon on Mar 19 2022, 2:40 PM.

Details

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.

Diff Detail

Event Timeline

RKSimon created this revision.Mar 19 2022, 2:40 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 19 2022, 2:40 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
RKSimon requested review of this revision.Mar 19 2022, 2:40 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 19 2022, 2:40 PM

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
129

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.

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 planned changes to this revision.Mar 20 2022, 1:36 AM

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
129

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 updated this revision to Diff 416766.Mar 20 2022, 2:38 AM

address feedback

RKSimon added inline comments.Mar 20 2022, 3:22 AM
llvm/test/CodeGen/X86/add-sub-bool.ll
129

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

pengfei accepted this revision.Mar 20 2022, 3:51 AM

LGTM.

This revision is now accepted and ready to land.Mar 20 2022, 3:51 AM
gulfem added a subscriber: gulfem.Mar 21 2022, 8:41 PM

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)

@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?

@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 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.