[Bug c++/109678] New: exponential time behavior on std::variant

["quentin.sabah at gmail dot com" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109678

            Bug ID: 109678
           Summary: exponential time behavior on std::variant
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: quentin.sabah at gmail dot com
  Target Milestone: ---

Hi,
I observe an exponential time behavior while compiling an std::variant with an
increasing number of alternatives (see testcase below).
It seems to be a regression in gcc 13 of the constant expression evaluation
while compiling "constexpr std::_Enable_default_constructor".

Found with gcc 13 shipped with Fedora 38.

Reproduced on Compiler Explorer:
Compiles in 20 seconds with gcc 13.1: https://godbolt.org/z/hhWx51sds
Compiles in a hundreds of milliseconds with gcc 12.2 and clang 16.

Testcase:

//=======================
#include <variant>

struct A {};
struct B {};
struct C {};
struct D {};
struct E {};
struct F {};
struct G {};
struct H {};
struct I {};
struct J {};
struct K {};
struct L {};
struct M {};
struct N {};
struct O {};
struct P {};
struct Q {};
struct R {};
struct S {};
struct T {};
struct U {};
struct V {};
struct W {
    // gcc13 + compiler explorer = 20000ms 
    // gcc12.2 + compiler explorer =   400ms
    int i;
};
struct X {};
struct Y {};
struct Z {};

using Foo = std::variant<A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R,
S, T, U, V, W, X, Y, Z>;

struct Bar {
    Foo f;
    static Bar dummy() {
        // issue is triggered by this initialization
        return {Z{}};
        // return {A{}}; // would be very quick
    }
};
//=======================



Compilation time reported on my machine (Intel(R) Core(TM) i7-4790 CPU @
3.60GHz)
$ time  g++ -v -std=c++17 -Wall -Wextra -c test.cpp 
...
GNU C++17 (GCC) version 13.0.1 20230401 (Red Hat 13.0.1-0)
(x86_64-redhat-linux)
        compiled by GNU C version 13.0.1 20230401 (Red Hat 13.0.1-0), GMP
version 6.2.1, MPFR version 4.1.1-p1, MPC version 1.3.1, isl version
isl-0.24-GMP
...
________________________________________________________
Executed in  131.43 secs    fish           external
   usr time  125.50 secs  659.00 micros  125.50 secs
   sys time    5.53 secs  109.00 micros    5.53 secs


perf report:
  29.51%  cc1plus  cc1plus               [.] cxx_eval_constant_expression       
  20.46%  cc1plus  cc1plus               [.] cxx_fold_indirect_ref_1            
   4.17%  cc1plus  cc1plus               [.] is_overloaded_fn



g++ -Q show that most time is spent in:
  constexpr std::_Enable_default_constructor<_Switch,
_Tag>::_Enable_default_constructor(std::_Enable_default_constructor_tag) [with
bool _Switch = true; _Tag = std::variant<A, B, C, D, E, F, G, H, I, J, K, L, M,
N, O, P, Q, R, S, T, U, V, W, X, Y, Z>]



g++ -ftime-report-details:
Time variable                                   usr           sys          wall
          GGC
 phase setup                        :   0.00 (  0%)   0.00 (  0%)   0.00 (  0%)
 1752k (  0%)
 phase parsing                      : 127.30 (100%)   4.76 (100%) 132.47 (100%)
16911M (100%)
 phase lang. deferred               :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
   19k (  0%)
 phase opt and generate             :   0.03 (  0%)   0.00 (  0%)   0.03 (  0%)
  103k (  0%)
 |name lookup                       :   0.02 (  0%)   0.01 (  0%)   0.04 (  0%)
  963k (  0%)
 |overload resolution               :   0.02 (  0%)   0.01 (  0%)   0.04 (  0%)
 3018k (  0%)
 garbage collection                 :   0.12 (  0%)   0.00 (  0%)   0.12 (  0%)
    0  (  0%)
 callgraph construction             :   0.03 (  0%)   0.00 (  0%)   0.03 (  0%)
  101k (  0%)
 preprocessing                      :   0.02 (  0%)   0.00 (  0%)   0.04 (  0%)
  361k (  0%)
 parser (global)                    :   0.01 (  0%)   0.02 (  0%)   0.05 (  0%)
 2957k (  0%)
 `- parser struct body              :   0.01 (  0%)   0.00 (  0%)   0.02 (  0%)
  669k (  0%)
 `- template instantiation          :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
   72k (  0%)
 `- preprocessing                   :   0.02 (  0%)   0.00 (  0%)   0.04 (  0%)
  361k (  0%)
 `- parser inl. func. body          :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
  263k (  0%)
 `- varconst                        :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
    0  (  0%)
 parser struct body                 :   0.02 (  0%)   0.02 (  0%)   0.04 (  0%)
 2568k (  0%)
 parser inl. func. body             :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
  362k (  0%)
 parser inl. meth. body             :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
  654k (  0%)
 `- garbage collection              :   0.12 (  0%)   0.00 (  0%)   0.12 (  0%)
    0  (  0%)
 `- template instantiation          :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
   13k (  0%)
 `- constant expression evaluation  : 127.02 (100%)   4.68 ( 98%) 132.10 (100%)
16896M (100%)
 template instantiation             :   0.06 (  0%)   0.04 (  1%)   0.12 (  0%)
 9062k (  0%)
 `- template instantiation          :   0.02 (  0%)   0.01 (  0%)   0.05 (  0%)
 1618k (  0%)
 `- symout                          :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
    0  (  0%)
 `- constant expression evaluation  :   0.02 (  0%)   0.00 (  0%)   0.00 (  0%)
   39k (  0%)
 constant expression evaluation     : 127.04 (100%)   4.68 ( 98%) 132.10 (100%)
16896M (100%)
 `- template instantiation          :   0.01 (  0%)   0.01 (  0%)   0.00 (  0%)
  345k (  0%)
 varconst                           :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
 4376  (  0%)
 symout                             :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
    0  (  0%)
 TOTAL                              : 127.33          4.76        132.51       
16913M