[InstCombine] matchRotate - add support for matching general funnel shifts with constant shift amounts (PR46896)

[RKSimon]

Summary

First step towards extending the existing rotation support to full funnel shift handling now that the backend legalization support has improved.

This enables us to match the shift by constant cases, which are pretty trivial to expand again if necessary.

D88420 will add non-uniform support for funnel shifts as well once its been finalized.

[RKSimon]

rebase

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2055–2056

This is expanded now - change name/code comment to matchFunnelShift()?

2060–2062

Update comment to acknowledge different ShVals.

2099

The comment doesn't read clearly to me. Is the restriction temporary/artificial, or do we not want to match general funnels here?

// For variable shift amounts, we only match rotates, not the more general funnel shift
// because...

llvm/test/Transforms/InstCombine/funnel.ll

33

Remove stale comment.

68

Remove stale comment.

[RKSimon]

address @spatel's feedback

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2060–2061

Remove "with the same shifted operand".

2088–2089

Sorry - it's still not clear to me *why* we have this clause. Are we regressing something without this restriction, or is the expanded IR pattern with a variable shift amount different between general funnel vs. rotate?

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2088–2089

The fold doesn't work for general funnel shifts: https://alive2.llvm.org/ce/z/L6YpuX

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2088–2089

Ah, I was looking at some of the unchanged regression tests similar to:
https://alive2.llvm.org/ce/z/wM5Xt4
...so I didn't make the connection that this is a different pattern. Do we want to add a 'TODO' then to get the alternate pattern(s) that do correspond to general funnel with variable shift op?

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2088–2089

@spatel I've updated D88783 so it works as a basic alternative pattern for non-constant funnel shift handling.

[nathanchance]

This patch breaks building the PowerPC Linux kernel with clang.

$ make -skj"$(nproc)" ARCH=powerpc CROSS_COMPILE=powerpc-linux-gnu- LLVM=1 distclean ppc44x_defconfig vmlinux
...
Do not know how to custom type legalize this operation!
UNREACHABLE executed at /home/nathan/cbl/github/tc-build/llvm-project/llvm/lib/Target/PowerPC/PPCISelLowering.cpp:10984!
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12 -cc1 -triple powerpc-unknown-linux-gnu -S -disable-free -main-file-name siphash.c -mrelocation-model static -fno-delete-null-pointer-checks -mllvm -warn-stack-size=1024 -mframe-pointer=none -relaxed-aliasing -fmath-errno -fno-rounding-math -no-integrated-as -mconstructor-aliases -target-cpu ppc64 -target-feature -altivec -target-feature -vsx -target-feature -spe -target-feature -hard-float -msoft-float -mfloat-abi soft -fno-split-dwarf-inlining -debugger-tuning=gdb -nostdsysteminc -nobuiltininc -resource-dir /home/nathan/cbl/github/tc-build/build/llvm/stage1/lib/clang/12.0.0 -dependency-file lib/.siphash.o.d -MT lib/siphash.o -isystem /home/nathan/cbl/github/tc-build/build/llvm/stage1/lib/clang/12.0.0/include -include ./include/linux/kconfig.h -include ./include/linux/compiler_types.h -I ./arch/powerpc/include -I ./arch/powerpc/include/generated -I ./include -I ./arch/powerpc/include/uapi -I ./arch/powerpc/include/generated/uapi -I ./include/uapi -I ./include/generated/uapi -D __KERNEL__ -I ./arch/powerpc -D KBUILD_MODFILE="lib/siphash" -D KBUILD_BASENAME="siphash" -D KBUILD_MODNAME="siphash" -fmacro-prefix-map=./= -O2 -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs -Werror=implicit-function-declaration -Werror=implicit-int -Wno-format-security -Werror=unknown-warning-option -Wno-frame-address -Wno-address-of-packed-member -Wno-format-invalid-specifier -Wno-gnu -Wno-unused-const-variable -Wdeclaration-after-statement -Wvla -Wno-pointer-sign -Wno-array-bounds -Werror=date-time -Werror=incompatible-pointer-types -Wno-initializer-overrides -Wno-format -Wno-sign-compare -Wno-format-zero-length -Wno-pointer-to-enum-cast -Wno-tautological-constant-out-of-range-compare -std=gnu89 -fno-dwarf-directory-asm -fdebug-compilation-dir /home/nathan/src/linux -ferror-limit 19 -fwrapv -fno-signed-char -fwchar-type=short -fno-signed-wchar -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -o /tmp/siphash-d2f058.s -x c lib/siphash.c 
1.	<eof> parser at end of file
2.	Code generation
3.	Running pass 'Function Pass Manager' on module 'lib/siphash.c'.
4.	Running pass 'PowerPC DAG->DAG Pattern Instruction Selection' on function '@siphash_1u64'
 #0 0x0000000002a141e3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x2a141e3)
 #1 0x0000000002a11f9e llvm::sys::RunSignalHandlers() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x2a11f9e)
 #2 0x0000000002a146a5 SignalHandler(int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x2a146a5)
 #3 0x00007f7586c383c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x153c0)
 #4 0x00007f75866fd18b raise (/lib/x86_64-linux-gnu/libc.so.6+0x4618b)
 #5 0x00007f75866dc859 abort (/lib/x86_64-linux-gnu/libc.so.6+0x25859)
 #6 0x00000000029a9f01 (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x29a9f01)
 #7 0x00000000018c7774 llvm::PPCTargetLowering::ReplaceNodeResults(llvm::SDNode*, llvm::SmallVectorImpl<llvm::SDValue>&, llvm::SelectionDAG&) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x18c7774)
 #8 0x0000000003871d83 llvm::DAGTypeLegalizer::CustomLowerNode(llvm::SDNode*, llvm::EVT, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x3871d83)
 #9 0x00000000038ca240 llvm::DAGTypeLegalizer::ExpandIntegerResult(llvm::SDNode*, unsigned int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x38ca240)
#10 0x000000000386dac2 llvm::DAGTypeLegalizer::run() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x386dac2)
#11 0x00000000038738e5 llvm::SelectionDAG::LegalizeTypes() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x38738e5)
#12 0x000000000385c28a llvm::SelectionDAGISel::CodeGenAndEmitDAG() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x385c28a)
#13 0x000000000385adbf llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x385adbf)
#14 0x0000000003857960 llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x3857960)
#15 0x00000000018eb22e (anonymous namespace)::PPCDAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x18eb22e)
#16 0x0000000001f749fd llvm::MachineFunctionPass::runOnFunction(llvm::Function&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x1f749fd)
#17 0x0000000002390e18 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x2390e18)
#18 0x00000000023973c1 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x23973c1)
#19 0x0000000002391437 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x2391437)
#20 0x0000000002c253a1 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x2c253a1)
#21 0x000000000343ab96 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x343ab96)
#22 0x0000000003c27d04 clang::ParseAST(clang::Sema&, bool, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x3c27d04)
#23 0x000000000339e033 clang::FrontendAction::Execute() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x339e033)
#24 0x00000000032fc563 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x32fc563)
#25 0x0000000003435284 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x3435284)
#26 0x0000000001859f18 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x1859f18)
#27 0x000000000185809c ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x185809c)
#28 0x0000000001857dfc main (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x1857dfc)
#29 0x00007f75866de0b3 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b3)
#30 0x0000000001854dbe _start (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-12+0x1854dbe)
clang-12: error: unable to execute command: Aborted
clang-12: error: clang frontend command failed due to signal (use -v to see invocation)
ClangBuiltLinux clang version 12.0.0 (https://github.com/llvm/llvm-project 2b96dcebfae65485859d956954f10f409abaae79)
Target: powerpc-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/nathan/cbl/github/tc-build/build/llvm/stage1/bin
clang-12: note: diagnostic msg: 
********************

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang-12: note: diagnostic msg: /tmp/siphash-5a6c0b.c
clang-12: note: diagnostic msg: /tmp/siphash-5a6c0b.sh
clang-12: note: diagnostic msg: 

********************
...

cvise spits out:

$ cat siphash.i
long long a;
b;
d() {
  a ^= 2;
  unsigned long long c = a;
  b = c << 1 | c >> 63;
}

$ clang --target=powerpc-linux-gnu -m32 -mcpu=powerpc64 -O2 -c -o /dev/null siphash.i
Do not know how to custom type legalize this operation!
UNREACHABLE executed at /home/nathan/cbl/github/tc-build/llvm-project/llvm/lib/Target/PowerPC/PPCISelLowering.cpp:10984!
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang --target=powerpc-linux-gnu -m32 -mcpu=powerpc64 -O2 -c -o /dev/null siphash.i 
1.	<eof> parser at end of file
2.	Code generation
3.	Running pass 'Function Pass Manager' on module 'siphash.i'.
4.	Running pass 'PowerPC DAG->DAG Pattern Instruction Selection' on function '@d'
 #0 0x0000000002a141e3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2a141e3)
 #1 0x0000000002a11f9e llvm::sys::RunSignalHandlers() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2a11f9e)
 #2 0x0000000002a135ad llvm::sys::CleanupOnSignal(unsigned long) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2a135ad)
 #3 0x00000000029a54e3 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x29a54e3)
 #4 0x00000000029a561e CrashRecoverySignalHandler(int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x29a561e)
 #5 0x00007f8b20fac3c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x153c0)
 #6 0x00007f8b20a7118b raise (/lib/x86_64-linux-gnu/libc.so.6+0x4618b)
 #7 0x00007f8b20a50859 abort (/lib/x86_64-linux-gnu/libc.so.6+0x25859)
 #8 0x00000000029a9f01 (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x29a9f01)
 #9 0x00000000018c7774 llvm::PPCTargetLowering::ReplaceNodeResults(llvm::SDNode*, llvm::SmallVectorImpl<llvm::SDValue>&, llvm::SelectionDAG&) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x18c7774)
#10 0x0000000003871d83 llvm::DAGTypeLegalizer::CustomLowerNode(llvm::SDNode*, llvm::EVT, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x3871d83)
#11 0x00000000038ca240 llvm::DAGTypeLegalizer::ExpandIntegerResult(llvm::SDNode*, unsigned int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x38ca240)
#12 0x000000000386dac2 llvm::DAGTypeLegalizer::run() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x386dac2)
#13 0x00000000038738e5 llvm::SelectionDAG::LegalizeTypes() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x38738e5)
#14 0x000000000385c28a llvm::SelectionDAGISel::CodeGenAndEmitDAG() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x385c28a)
#15 0x000000000385adbf llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x385adbf)
#16 0x0000000003857960 llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x3857960)
#17 0x00000000018eb22e (anonymous namespace)::PPCDAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x18eb22e)
#18 0x0000000001f749fd llvm::MachineFunctionPass::runOnFunction(llvm::Function&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x1f749fd)
#19 0x0000000002390e18 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2390e18)
#20 0x00000000023973c1 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x23973c1)
#21 0x0000000002391437 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2391437)
#22 0x0000000002c253a1 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x2c253a1)
#23 0x000000000343ab96 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x343ab96)
#24 0x0000000003c27d04 clang::ParseAST(clang::Sema&, bool, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x3c27d04)
#25 0x000000000339e033 clang::FrontendAction::Execute() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x339e033)
#26 0x00000000032fc563 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x32fc563)
#27 0x0000000003435284 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x3435284)
#28 0x0000000001859f18 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x1859f18)
#29 0x000000000185809c ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x185809c)
#30 0x00000000031be142 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const::$_1>(long) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x31be142)
#31 0x00000000029a53f7 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x29a53f7)
#32 0x00000000031bd8b7 clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x31bd8b7)
#33 0x0000000003187cfb clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x3187cfb)
#34 0x0000000003187ef7 clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x3187ef7)
#35 0x000000000319f5c8 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x319f5c8)
#36 0x0000000001857a58 main (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x1857a58)
#37 0x00007f8b20a520b3 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b3)
#38 0x0000000001854dbe _start (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang+0x1854dbe)
clang-12: error: clang frontend command failed with exit code 134 (use -v to see invocation)
ClangBuiltLinux clang version 12.0.0 (https://github.com/llvm/llvm-project 2b96dcebfae65485859d956954f10f409abaae79)
Target: powerpc-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/nathan/cbl/github/tc-build/build/llvm/stage1/bin
clang-12: note: diagnostic msg: Error generating preprocessed source(s) - no preprocessable inputs. 

I guess it is a little odd to have -m32 -mcpu=powerpc64 but everything worked fine before this patch.

$ git bisect log
# bad: [e1c38dd55d9dab332ccabb7c83a80ca92c373af0] [CSKY 1/n] Add basic stub or infra of csky backend
# good: [80ac6da98e8fb88ed68308acc8e8689420a54f90] [NFC][SCEV] Add a test with some patterns where we could treat inttoptr/ptrtoint as semi-transparent
git bisect start 'e1c38dd55d9dab332ccabb7c83a80ca92c373af0' '80ac6da98e8fb88ed68308acc8e8689420a54f90'
# good: [bef27e50b9a2dd272a0c48e5237daeab50f77c7a] [NFC][InstCombine] Autogenerate a few tests being affected by upcoming patch
git bisect good bef27e50b9a2dd272a0c48e5237daeab50f77c7a
# bad: [cf402a1987591923492fe697b2e84b1affbae6dd] [mlir][vector] Add unit test for vector distribute by block
git bisect bad cf402a1987591923492fe697b2e84b1affbae6dd
# good: [9824d5c83844495ac00c04dc1789c3529a68c1ac] [Test] Add test showing that we fail to eliminate implied exit conditions
git bisect good 9824d5c83844495ac00c04dc1789c3529a68c1ac
# bad: [d4a7c70751cf5c0b0ce344555e3966ddc80290d2] [lldb] Add a cmake warning about the python/swig incompatibility
git bisect bad d4a7c70751cf5c0b0ce344555e3966ddc80290d2
# bad: [30e6033b455bfa4b888eedb2cfe808a61845ed5f] [mlir][Linalg] Add TensorsToBuffers support for Constant ops.
git bisect bad 30e6033b455bfa4b888eedb2cfe808a61845ed5f
# bad: [1e75668821f7c2abfdb4a25af76239b9120ae0ca] [AMDGPU][MC][GFX1030] Disabled v_mac_f32
git bisect bad 1e75668821f7c2abfdb4a25af76239b9120ae0ca
# good: [c1fd4305b68500c754a7ce6a86fe297c36e21d3b] [mlir] Add basic support for dynamic tensor results in TensorToBuffers.cpp.
git bisect good c1fd4305b68500c754a7ce6a86fe297c36e21d3b
# bad: [7d01bb8f56f5f1d8e180e1b8d47c00b45aa0555b] [llvm-objdump] Ensure we consistently use the llvm::stable_sort wrappers.
git bisect bad 7d01bb8f56f5f1d8e180e1b8d47c00b45aa0555b
# bad: [e1d4ca00094a4267b6fd70f613f2e0390b2a8cbf] [InstCombine] matchRotate - add support for matching general funnel shifts with constant shift amounts (PR46896)
git bisect bad e1d4ca00094a4267b6fd70f613f2e0390b2a8cbf
# first bad commit: [e1d4ca00094a4267b6fd70f613f2e0390b2a8cbf] [InstCombine] matchRotate - add support for matching general funnel shifts with constant shift amounts (PR46896)

The original preprocessed file and interestingness case can be found here: https://github.com/nathanchance/creduce-files/tree/ea3b761f6f3938d2a21e3225b05131212db107f3/D88834

[RKSimon]

Thanks @nathanchance I think I see whats going on

[RKSimon]

@nathanchance Please can you confirm rG2c3e4a21f93d fixes the issue?

[nathanchance]

In D88834#2323565, @RKSimon wrote:

@nathanchance Please can you confirm rG2c3e4a21f93d fixes the issue?

It does, thank you a lot for the quick fix!

[saugustine]

Google has tracked down a failure in openssl for powerpc to this change. (And the fix for the 32-bit vs 64-bit issue below doesn't seem to fix this.)

I'm trying to get a smaller reproduction. But just so that is on your radar.

[RKSimon]

In D88834#2326590, @saugustine wrote:

Google has tracked down a failure in openssl for powerpc to this change. (And the fix for the 32-bit vs 64-bit issue below doesn't seem to fix this.)

I'm trying to get a smaller reproduction. But just so that is on your radar.

np @saugustine - I made some further regression reverts/fixes yesterday so if you can test against a more recent trunk that'd be very useful.

[saugustine]

PowerPC still doesn't seem to be fixed as of 6713332fddb7. We have someone trying to narrow it down.

[RKSimon]

@saugustine Any update on this? Please can you tell me if its an assert, crash or miscompile?

[hans]

We bisected a false positive in MSan to this patch, see https://bugs.llvm.org/show_bug.cgi?id=50840

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombinerImpl::matchBSwap(BinaryOperator &Or) {
   Instruction *LastInst = Insts.pop_back_val();
   LastInst->removeFromParent();
 
   for (auto *Inst : Insts)
     Worklist.push(Inst);
   return LastInst;
 }
 
-/// Transform UB-safe variants of bitwise rotate to the funnel shift intrinsic.
-static Instruction *matchRotate(Instruction &Or) {
+/// Match UB-safe variants of the funnel shift intrinsic.
+static Instruction *matchFunnelShift(Instruction &Or) {
   // TODO: Can we reduce the code duplication between this and the related
   // rotate matching code under visitSelect and visitTrunc?
   unsigned Width = Or.getType()->getScalarSizeInBits();
 
-  // First, find an or'd pair of opposite shifts with the same shifted operand:
-  // or (lshr ShVal, ShAmt0), (shl ShVal, ShAmt1)
+  // First, find an or'd pair of opposite shifts:
+  // or (lshr ShVal0, ShAmt0), (shl ShVal1, ShAmt1)
   BinaryOperator *Or0, *Or1;
   if (!match(Or.getOperand(0), m_BinOp(Or0)) ||
       !match(Or.getOperand(1), m_BinOp(Or1)))
     return nullptr;
 
-  Value *ShVal, *ShAmt0, *ShAmt1;
-  if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal), m_Value(ShAmt0)))) ||
-      !match(Or1, m_OneUse(m_LogicalShift(m_Specific(ShVal), m_Value(ShAmt1)))))
+  Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;
+  if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal0), m_Value(ShAmt0)))) ||
+      !match(Or1, m_OneUse(m_LogicalShift(m_Value(ShVal1), m_Value(ShAmt1)))))
     return nullptr;
 
   BinaryOperator::BinaryOps ShiftOpcode0 = Or0->getOpcode();
   BinaryOperator::BinaryOps ShiftOpcode1 = Or1->getOpcode();
   if (ShiftOpcode0 == ShiftOpcode1)
     return nullptr;
 
-  // Match the shift amount operands for a rotate pattern. This always matches
-  // a subtraction on the R operand.
-  auto matchShiftAmount = [](Value *L, Value *R, unsigned Width) -> Value * {
+  // Match the shift amount operands for a funnel shift pattern. This always
+  // matches a subtraction on the R operand.
+  auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width) -> Value * {
     // Check for constant shift amounts that sum to the bitwidth.
     // TODO: Support non-uniform shift amounts.
     const APInt *LC, *RC;
     if (match(L, m_APIntAllowUndef(LC)) && match(R, m_APIntAllowUndef(RC)))
       if (LC->ult(Width) && RC->ult(Width) && (*LC + *RC) == Width)
         return ConstantInt::get(L->getType(), *LC);
 
+    // For non-constant cases, the following patterns currently only work for
+    // rotation patterns.
+    // TODO: Add general funnel-shift compatible patterns.
+    if (ShVal0 != ShVal1)
+      return nullptr;
+
     // For non-constant cases we don't support non-pow2 shift masks.
     // TODO: Is it worth matching urem as well?
     if (!isPowerOf2_32(Width))
       return nullptr;
 
     // The shift amount may be masked with negation:
     // (shl ShVal, (X & (Width - 1))) | (lshr ShVal, ((-X) & (Width - 1)))
     Value *X;
     unsigned Mask = Width - 1;
     if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) &&
         match(R, m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask))))
       return X;
 
     // Similar to above, but the shift amount may be extended after masking,
static Instruction *matchFunnelShift(Instruction &Or) {
   }
   if (!ShAmt)
     return nullptr;
 
   bool IsFshl = (!SubIsOnLHS && ShiftOpcode0 == BinaryOperator::Shl) ||
                 (SubIsOnLHS && ShiftOpcode1 == BinaryOperator::Shl);
   Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
   Function *F = Intrinsic::getDeclaration(Or.getModule(), IID, Or.getType());
-  return IntrinsicInst::Create(F, { ShVal, ShVal, ShAmt });
+  return IntrinsicInst::Create(
+      F, {IsFshl ? ShVal0 : ShVal1, IsFshl ? ShVal1 : ShVal0, ShAmt});
 }
 
 /// Attempt to combine or(zext(x),shl(zext(y),bw/2) concat packing patterns.
 static Instruction *matchOrConcat(Instruction &Or,
                                   InstCombiner::BuilderTy &Builder) {
   assert(Or.getOpcode() == Instruction::Or && "bswap requires an 'or'");
   Value *Op0 = Or.getOperand(0), *Op1 = Or.getOperand(1);
   Type *Ty = Or.getType();
if (Value *V = SimplifyBSwap(I, Builder))
     return replaceInstUsesWith(I, V);
 
   if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
     return FoldedLogic;
 
   if (Instruction *BSwap = matchBSwap(I))
     return BSwap;
 
-  if (Instruction *Rotate = matchRotate(I))
-    return Rotate;
+  if (Instruction *Funnel = matchFunnelShift(I))
+    return Funnel;
 
   if (Instruction *Concat = matchOrConcat(I, Builder))
     return replaceInstUsesWith(I, Concat);
 
   Value *X, *Y;
   const APInt *CV;
   if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) &&
       !CV->isAllOnesValue() && MaskedValueIsZero(Y, *CV, 0, &I)) {

llvm/test/Transforms/InstCombine/funnel.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
 
-; TODO: Canonicalize or(shl,lshr) by constant to funnel shift intrinsics.
+; Canonicalize or(shl,lshr) by constant to funnel shift intrinsics.
 ; This should help cost modeling for vectorization, inlining, etc.
 ; If a target does not have a fshl instruction, the expansion will
 ; be exactly these same 3 basic ops (shl/lshr/or).
 
 define i32 @fshl_i32_constant(i32 %x, i32 %y) {
 ; CHECK-LABEL: @fshl_i32_constant(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], 11
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 [[Y:%.*]], 21
-; CHECK-NEXT:    [[R:%.*]] = or i32 [[SHR]], [[SHL]]
+; CHECK-NEXT:    [[R:%.*]] = call i32 @llvm.fshl.i32(i32 [[X:%.*]], i32 [[Y:%.*]], i32 11)
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %shl = shl i32 %x, 11
   %shr = lshr i32 %y, 21
   %r = or i32 %shr, %shl
   ret i32 %r
 }
 
 define i42 @fshr_i42_constant(i42 %x, i42 %y) {
 ; CHECK-LABEL: @fshr_i42_constant(
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i42 [[X:%.*]], 31
-; CHECK-NEXT:    [[SHL:%.*]] = shl i42 [[Y:%.*]], 11
-; CHECK-NEXT:    [[R:%.*]] = or i42 [[SHR]], [[SHL]]
+; CHECK-NEXT:    [[R:%.*]] = call i42 @llvm.fshl.i42(i42 [[Y:%.*]], i42 [[X:%.*]], i42 11)
 ; CHECK-NEXT:    ret i42 [[R]]
 ;
   %shr = lshr i42 %x, 31
   %shl = shl i42 %y, 11
   %r = or i42 %shr, %shl
   ret i42 %r
 }
 
-; TODO: Vector types are allowed.
+; Vector types are allowed.
 
 define <2 x i16> @fshl_v2i16_constant_splat(<2 x i16> %x, <2 x i16> %y) {
 ; CHECK-LABEL: @fshl_v2i16_constant_splat(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i16> [[X:%.*]], <i16 1, i16 1>
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i16> [[Y:%.*]], <i16 15, i16 15>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i16> [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i16> @llvm.fshl.v2i16(<2 x i16> [[X:%.*]], <2 x i16> [[Y:%.*]], <2 x i16> <i16 1, i16 1>)
 ; CHECK-NEXT:    ret <2 x i16> [[R]]
 ;
   %shl = shl <2 x i16> %x, <i16 1, i16 1>
   %shr = lshr <2 x i16> %y, <i16 15, i16 15>
   %r = or <2 x i16> %shl, %shr
   ret <2 x i16> %r
 }
 
 define <2 x i16> @fshl_v2i16_constant_splat_undef0(<2 x i16> %x, <2 x i16> %y) {
 ; CHECK-LABEL: @fshl_v2i16_constant_splat_undef0(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i16> [[X:%.*]], <i16 undef, i16 1>
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i16> [[Y:%.*]], <i16 15, i16 15>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i16> [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i16> @llvm.fshl.v2i16(<2 x i16> [[X:%.*]], <2 x i16> [[Y:%.*]], <2 x i16> <i16 1, i16 1>)
 ; CHECK-NEXT:    ret <2 x i16> [[R]]
 ;
   %shl = shl <2 x i16> %x, <i16 undef, i16 1>
   %shr = lshr <2 x i16> %y, <i16 15, i16 15>
   %r = or <2 x i16> %shl, %shr
   ret <2 x i16> %r
 }
 
 define <2 x i16> @fshl_v2i16_constant_splat_undef1(<2 x i16> %x, <2 x i16> %y) {
 ; CHECK-LABEL: @fshl_v2i16_constant_splat_undef1(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i16> [[X:%.*]], <i16 1, i16 1>
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i16> [[Y:%.*]], <i16 15, i16 undef>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i16> [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i16> @llvm.fshl.v2i16(<2 x i16> [[X:%.*]], <2 x i16> [[Y:%.*]], <2 x i16> <i16 1, i16 1>)
 ; CHECK-NEXT:    ret <2 x i16> [[R]]
 ;
   %shl = shl <2 x i16> %x, <i16 1, i16 1>
   %shr = lshr <2 x i16> %y, <i16 15, i16 undef>
   %r = or <2 x i16> %shl, %shr
   ret <2 x i16> %r
 }
 
-; TODO: Non-power-of-2 vector types are allowed.
+; Non-power-of-2 vector types are allowed.
 
 define <2 x i17> @fshr_v2i17_constant_splat(<2 x i17> %x, <2 x i17> %y) {
 ; CHECK-LABEL: @fshr_v2i17_constant_splat(
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i17> [[X:%.*]], <i17 12, i17 12>
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i17> [[Y:%.*]], <i17 5, i17 5>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i17> [[SHR]], [[SHL]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i17> @llvm.fshl.v2i17(<2 x i17> [[Y:%.*]], <2 x i17> [[X:%.*]], <2 x i17> <i17 5, i17 5>)
 ; CHECK-NEXT:    ret <2 x i17> [[R]]
 ;
   %shr = lshr <2 x i17> %x, <i17 12, i17 12>
   %shl = shl <2 x i17> %y, <i17 5, i17 5>
   %r = or <2 x i17> %shr, %shl
   ret <2 x i17> %r
 }
 
 define <2 x i17> @fshr_v2i17_constant_splat_undef0(<2 x i17> %x, <2 x i17> %y) {
 ; CHECK-LABEL: @fshr_v2i17_constant_splat_undef0(
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i17> [[X:%.*]], <i17 12, i17 undef>
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i17> [[Y:%.*]], <i17 undef, i17 5>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i17> [[SHR]], [[SHL]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i17> @llvm.fshl.v2i17(<2 x i17> [[Y:%.*]], <2 x i17> [[X:%.*]], <2 x i17> <i17 5, i17 5>)
 ; CHECK-NEXT:    ret <2 x i17> [[R]]
 ;
   %shr = lshr <2 x i17> %x, <i17 12, i17 undef>
   %shl = shl <2 x i17> %y, <i17 undef, i17 5>
   %r = or <2 x i17> %shr, %shl
   ret <2 x i17> %r
 }
 
 define <2 x i17> @fshr_v2i17_constant_splat_undef1(<2 x i17> %x, <2 x i17> %y) {
 ; CHECK-LABEL: @fshr_v2i17_constant_splat_undef1(
-; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i17> [[X:%.*]], <i17 12, i17 undef>
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i17> [[Y:%.*]], <i17 5, i17 undef>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i17> [[SHR]], [[SHL]]
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i17> @llvm.fshl.v2i17(<2 x i17> [[Y:%.*]], <2 x i17> [[X:%.*]], <2 x i17> <i17 5, i17 5>)
 ; CHECK-NEXT:    ret <2 x i17> [[R]]
 ;
   %shr = lshr <2 x i17> %x, <i17 12, i17 undef>
   %shl = shl <2 x i17> %y, <i17 5, i17 undef>
   %r = or <2 x i17> %shr, %shl
   ret <2 x i17> %r
 }