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


generate.tar.gz (426 Bytes)

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