[Bug c++/102780] New: Checking constraints using large fold expression is slow

["redi at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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

            Bug ID: 102780
           Summary: Checking constraints using large fold expression is
                    slow
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
  Target Milestone: ---

template<int I> struct S { };

template<typename T, T...> struct integer_sequence { };

template<typename T, T N>
  using make_integer_sequence
#if __has_builtin(__make_integer_seq)
    = __make_integer_seq<integer_sequence, T, N>;
#else
    = integer_sequence<T, __integer_pack(N)...>;
#endif

template<typename... _Types>
  concept trivially_destructible
    = (__has_trivial_destructor(_Types) && ...);

template<typename...> union variadic_union { static constexpr int size = 0; };

template<typename T, typename... U>
union variadic_union<T, U...>
{
  ~variadic_union() = default;

#ifndef TRIVIAL_ONLY
  // Conditionally non-trivial dtor, if required.
  constexpr ~variadic_union() requires (!trivially_destructible<T, U...>)
  { }
#endif

  T first;
  variadic_union<U...> rest;

  static constexpr int size = variadic_union<U...>::size + 1;
};


template <int... Is>
void f_impl(integer_sequence<int, Is...>)
{
  using V = variadic_union<S<Is>...>;
  // cause instantiation of V:
  static_assert( V::size == sizeof...(Is) );
}

  template <int I>
void f()
{
  f_impl(make_integer_sequence<int, I>());
}

int main()
{
  f<254>();
  f<255>();
  f<256>();
}


Compiled with -std=gnu++20 -ftime-report I get:

 TOTAL        :  10.46          3.58         14.08           78M

Adding -fno-checking helps a little:

 TOTAL        :   7.71          3.70         11.43           78M


Clang compiles this in under a second.


Full details:

> Time variable                                   usr           sys          wall           GGC
>  phase setup                        :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)  1589k (  2%)
>  phase lang. deferred               :   7.88 ( 75%)   3.68 (100%)  11.62 ( 82%)    69M ( 88%)
>  phase opt and generate             :   2.59 ( 25%)   0.00 (  0%)   2.60 ( 18%)  7297k (  9%)
>  |name lookup                       :   0.05 (  0%)   0.02 (  1%)   0.02 (  0%)   670k (  1%)
>  |overload resolution               :   7.35 ( 70%)   3.51 ( 95%)  10.91 ( 77%)    10M ( 13%)
>  garbage collection                 :   0.04 (  0%)   0.00 (  0%)   0.04 (  0%)     0  (  0%)
>  callgraph construction             :   2.56 ( 24%)   0.00 (  0%)   2.58 ( 18%)  7016k (  9%)
>  callgraph ipa passes               :   0.02 (  0%)   0.00 (  0%)   0.01 (  0%)    15k (  0%)
>  CFG verifier                       :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)     0  (  0%)
>  template instantiation             :   0.25 (  2%)   0.11 (  3%)   0.37 (  3%)    43M ( 56%)
>  constant expression evaluation     :   4.36 ( 42%)   2.02 ( 55%)   6.61 ( 46%)    72  (  0%)
>  constraint satisfaction            :   3.20 ( 31%)   1.55 ( 42%)   4.57 ( 32%)    20M ( 25%)
>  symout                             :   0.05 (  0%)   0.00 (  0%)   0.04 (  0%)  5726k (  7%)
>  initialize rtl                     :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)    12k (  0%)
>  TOTAL                              :  10.47          3.68         14.23           78M
> Extra diagnostic checks enabled; compiler may run slowly.
> Configure with --enable-checking=release to disable checks.


Defining -DTRIVIAL_ONLY makes it compile in under 2s, and 0.4s with
-DTRIVIAL_ONLY -fno-checking (almost as fast as clang)

The constraint satisfaction seems to be the problem, even though "template
instantiation" shows up as a larger percentage in the time report.