llvm dev - Dec 2021 - Exploding compile times for long functions

Dear list,

we recently found very long compile times for generated functions with
many, many lines. I've extracted a tiny reproducer to mimic what is
going on, and the core problem seems to be calling a function that
takes a std::string_view and a newly heap-allocated pointer (see
generate.string_view.sh in the attached archive).

Generating 10k calls with
 $ ./generate_string_view.sh 10000 > generated.string_view.10000.cpp
and then compiling with
 $ clang++ -std=c++17 -O1 generated.string_view.10000.cpp -c
takes 27s (with Clang 12.0.1), while -O0 is only 1.5s. With more recent
versions of LLVM, it gets much worse: Clang 13.0.0 takes around 4m30s,
current main is in the same area.

Is this expected? Is this a case of "don't do it" (such long
functions)
or a problem that should be fixed in the optimization passes?

Some more notes:
 * For Clang 12.0.1, experimenting with the extracted LLVM IR points to
the instcombine pass; only running "opt -sroa -early-cse -instcombine"
takes around the same time as the full Clang invocation.
 * For Clang 13.0.0 and later, time appears to be spread out more; the
same "opt -sroa -early-cse -instcombine" takes "only" 28s
(compared to
4m30s).
 * Changing either of the arguments in the generated code brings time
back to normal:
   * Passing a "const char *" takes ~2 seconds.
   * Using only one "new" takes ~9 seconds.

Cheers
Jonas
-------------- next part --------------
A non-text attachment was scrubbed...
Name: generate.tar.gz
Type: application/x-compressed-tar
Size: 426 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211208/2c146a6b/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: This is a digitally signed message part
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211208/2c146a6b/attachment.sig>

> On Dec 8, 2021, at 16:59, Jonas Hahnfeld via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Dear list,
> 
> we recently found very long compile times for generated functions with
> many, many lines. I've extracted a tiny reproducer to mimic what is
> going on, and the core problem seems to be calling a function that
> takes a std::string_view and a newly heap-allocated pointer (see
> generate.string_view.sh in the attached archive).
> 
> Generating 10k calls with
> $ ./generate_string_view.sh 10000 > generated.string_view.10000.cpp
> and then compiling with
> $ clang++ -std=c++17 -O1 generated.string_view.10000.cpp -c
> takes 27s (with Clang 12.0.1), while -O0 is only 1.5s. With more recent
> versions of LLVM, it gets much worse: Clang 13.0.0 takes around 4m30s,
> current main is in the same area.
> 
> Is this expected? Is this a case of "don't do it" (such long
functions)
> or a problem that should be fixed in the optimization passes?
Unfortunately this is kind of expected. Large auto-generated can be very good at
highlighting inefficiencies in optimizations.

It seems there might be an issue in instcombine. Building a generated file with
1k calls spends ~0.25s in instcombine, for a file with 10k calls we spend 53s in
instcombine (as per -ftime-report).

Cheers,
Florian