It is caused by

Author: Chandler Carruth chandlerc@gmail.com
Date: Thu Jan 1 11:54:38 2015 +0000

[SROA] Teach SROA how to much more intelligently handle split loads and
stores.

When there are accesses to an entire alloca with an integer
load or store as well as accesses to small pieces of the alloca, SROA
splits up the large integer accesses. In order to do that, it uses bit
math to merge the small accesses into large integers. While this is
effective, it produces insane IR that can cause significant problems in
the rest of the optimizer:

- It can cause load and store mismatches with GVN on the non-alloca side
  where we end up loading an i64 (or some such) rather than loading
  specific elements that are stored.
- We can't always get rid of the integer bit math, which is why we can't
  always fix the loads and stores to work well with GVN.
- This is especially bad when we have operations that mix poorly with
  integer bit math such as floating point operations.
- It will block things like the vectorizer which might be able to handle
  the scalar stores that underly the aggregate.

At the same time, we can't just directly split up these loads and stores
in all cases. If there is actual integer arithmetic involved on the
values, then using integer bit math is actually the perfect lowering
because we can often combine it heavily with the surrounding math.

The solution this patch provides is to find places where SROA is
partitioning aggregates into small elements, and look for splittable
loads and stores that it can split all the way to some other adjacent
load and store. These are uniformly the cases where failing to split the
loads and stores hurts the optimizer that I have seen, and I've looked
extensively at the code produced both from more and less aggressive
approaches to this problem.

However, it is quite tricky to actually do this in SROA. We may have
loads and stores to the same alloca, or other complex patterns that are
hard to handle. This complexity leads to the somewhat subtle algorithm
implemented here. We have to do this entire process as a separate pass
over the partitioning of the alloca, and split up all of the loads prior
to splitting the stores so that we can handle safely the cases of
overlapping, including partially overlapping, loads and stores to the
same alloca. We also have to reconstitute the post-split slice
configuration so we can avoid iterating again over all the alloca uses
(the slow part of SROA). But we also have to ensure that when we split
up loads and stores to *other* allocas, we *do* re-iterate over them in
SROA to adapt to the more refined partitioning now required.

With this, I actually think we can fix a long-standing TODO in SROA
where I avoided splitting as many loads and stores as probably should be
splittable. This limitation historically mitigated the fallout of all
the bad things mentioned above. Now that we have more intelligent
handling, I plan to remove the FIXME and more aggressively mark integer
loads and stores as splittable. I'll do that in a follow-up patch to
help with bisecting any fallout.

The net result of this change should be more fine-grained and accurate
scalars being formed out of aggregates. At the very least, Clang now
generates perfect code for this high-level test case using
std::complex<float>:

  #include <complex>

  void g1(std::complex<float> &x, float a, float b) {
    x += std::complex<float>(a, b);
  }
  void g2(std::complex<float> &x, float a, float b) {
    x -= std::complex<float>(a, b);
  }

  void foo(const std::complex<float> &x, float a, float b,
           std::complex<float> &x1, std::complex<float> &x2) {
    std::complex<float> l1 = x;
    g1(l1, a, b);
    std::complex<float> l2 = x;
    g2(l2, a, b);
    x1 = l1;
    x2 = l2;
  }

This code isn't just hypothetical either. It was reduced out of the hot
inner loops of essentially every part of the Eigen math library when
using std::complex<float>. Those loops would consistently and
pervasively hop between the floating point unit and the integer unit due
to bit math extraction and insertion of floating point values that were
"stored" in a 64-bit integer register around the loop backedge.

So far, this change has passed a bootstrap and I have done some other
testing and so far, no issues. That doesn't mean there won't be though,
so I'll be prepared to help with any fallout. If you performance swings
in particular, please let me know. I'm very curious what all the impact
of this change will be. Stay tuned for the follow-up to also split more
integer loads and stores.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@225061 91177308-0d34-0410-b5e6-96231b3b80d8

The same thing happens on Linux/x86-64.

I am looking at this.. Apologies, I did bootstrap before commuting, but this failure didn't show up for me.

H.J.Lu, do you have the preprocessed file? Could you attach it to the bug?

[A testcase on Linuxhttps://user-images.githubusercontent.com/1072356/143750670-f70ad2bb-245a-4e81-9b1e-39a3b068b419.gz)
[hjl@gnu-tools-1 tmp]$ /export/build/gnu/llvm-clang-bootstrap/stage1/build-x86_64-linux/Release+Asserts/bin/clang++ -O3 -S x.ii -std=c++11
clang: /export/gnu/import/git/llvm/include/llvm/Support/Casting.h:237: typename llvm::cast_retty<X, Y*>::ret_type llvm::cast(Y*) [with X = llvm::Instruction; Y = llvm::Value; typename llvm::cast_retty<X, Y*>::ret_type = llvm::Instruction*]: Assertion `isa(Val) && "cast() argument of incompatible type!"' failed.
0 clang 0x0000000002811da2 llvm::sys::PrintStackTrace(_IO_FILE*) + 34
1 clang 0x000000000280ffe1
2 libpthread.so.0 0x0000003b6ea0f6d0
3 libc.so.6 0x0000003b6e6357b7 gsignal + 55
4 libc.so.6 0x0000003b6e636ea8 abort + 328
5 libc.so.6 0x0000003b6e62e716
6 libc.so.6 0x0000003b6e62e7c2
7 clang 0x00000000008a1014
8 clang 0x0000000002349524
9 clang 0x000000000234d0d7
10 clang 0x000000000279b23f llvm::FPPassManager::runOnFunction(llvm::Function&) + 655
11 clang 0x000000000279b363 llvm::legacy::FunctionPassManagerImpl::run(llvm::Function&) + 163
12 clang 0x000000000279b4c4 llvm::legacy::FunctionPassManager::run(llvm::Function&) + 36
13 clang 0x0000000000ad4565 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, llvm::raw_ostream*) + 3093
14 clang 0x0000000000ac68fc
15 clang 0x0000000000c75e43 clang::ParseAST(clang::Sema&, bool, bool) + 483
16 clang 0x0000000000ac760b clang::CodeGenAction::ExecuteAction() + 59
17 clang 0x00000000009296c6 clang::FrontendAction::Execute() + 118
18 clang 0x0000000000906b79 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) + 345
19 clang 0x00000000008eec0e clang::ExecuteCompilerInvocation(clang::CompilerInstance*) + 2014
20 clang 0x00000000008e7120 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) + 1344
21 clang 0x00000000008c2cc6 main + 4582
22 libc.so.6 0x0000003b6e621ca5 __libc_start_main + 245
23 clang 0x00000000008e5ebd
Stack dump:
0. Program arguments: /export/build/gnu/llvm-clang-bootstrap/stage1/build-x86_64-linux/Release+Asserts/bin/clang -cc1 -triple x86_64-pc-linux-gnu -S -disable-free -main-file-name x.ii -mrelocation-model static -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -target-linker-version 2.25.51.0.2.20141229 -momit-leaf-frame-pointer -dwarf-column-info -coverage-file /tmp/x.ii -resource-dir /export/build/gnu/llvm-clang-bootstrap/stage1/build-x86_64-linux/Release+Asserts/bin/../lib/clang/3.6.0 -O3 -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /tmp -ferror-limit 19 -fmessage-length 80 -mstackrealign -fobjc-runtime=gcc -fcxx-exceptions -fexceptions -fdiagnostics-show-option -fcolor-diagnostics -vectorize-loops -vectorize-slp -o x.s -x c++-cpp-output x.ii

1. parser at end of file
2. Per-function optimization
3. Running pass 'SROA' on function '@_Z14convertVersionN5clang12VersionTupleE'
   clang: error: unable to execute command: Aborted (core dumped)
   clang: error: clang frontend command failed due to signal (use -v to see invocation)
   clang version 3.6.0 (http://llvm.org/git/clang.git 2e98270d45c3201e0ad684a798d217a9d0bfb258) (http://llvm.org/git/llvm.git 3239978)
   Target: x86_64-pc-linux-gnu
   Thread model: posix
   clang: note: diagnostic msg: PLEASE submit a bug report to http://llvm.org/bugs/ and include the crash backtrace, preprocessed source, and associated run script.
   clang: note: diagnostic msg: Error generating preprocessed source(s) - no preprocessable inputs.
   [hjl@gnu-tools-1 tmp]$

H.J.Lu, do you have the preprocessed file? Could you attach it to the bug?

FWIW, I suspect I just didn't have assertions enabled in my selfhost, and this is an assertion-only failure (but may be a risk of miscompile).

I'm bootstrapping now w/ assertions and will hopefully be able to reproduce shortly. It has also shown up on some of the bootstrap build bots.

H.J.Lu, do you have the preprocessed file? Could you attach it to the bug?

FWIW, I suspect I just didn't have assertions enabled in my selfhost, and
this is an assertion-only failure (but may be a risk of miscompile).

I'm bootstrapping now w/ assertions and will hopefully be able to reproduce
shortly. It has also shown up on some of the bootstrap build bots.

Or H.J.Lu will get me a test case that simplifies debugging... should have this fixed shortly, this doesn't look scary, just a coding bug on my part.

Proximate cause fixed in r225068. Doing a fresh asserts bootstrap just to check for more fallout. Will close once that's clean.

Ok, that did fix the last issue I'm seeing with the bootstrap. Added a test case for this issue in r225070. Thanks for the report, and sorry for the inconvenience.

*** Bug llvm/llvm-bugzilla-archive#22089 has been marked as a duplicate of this bug. ***

mentioned in issue llvm/llvm-bugzilla-archive#22089