[Bug c++/96979] New: Switch with case values derived from constexpr function takes unreasonable time to compile

[Bug c++/96979] New: Switch with case values derived from constexpr function takes unreasonable time to compile

[gcc at magey dot org]

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

            Bug ID: 96979
           Summary: Switch with case values derived from constexpr
                    function takes unreasonable time to compile
           Product: gcc
           Version: 10.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gcc at magey dot org
  Target Milestone: ---

Created attachment 49197
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49197&action=edit
Preprocessed source file

Using the result of a constexpr function (such as a compile-time hashing
function) as the value of a case label takes an unreasonably long time to
compile. The example attached takes ~26 seconds to compile on my system with
2000 case labels. The compile time increase is exponential; if I increase the
case count to 3000 it takes about 98 seconds to compile. Note that this example
(both with 2000 and 3000 cases) compiles in less than 1 second on clang 10,
msvc 19.27 and circle. Also note that the compilation time is unaffected by the
optimization level; it takes the same amount of time with O3 and O0. Another
thing I noticed is that it doesn't matter if the constexpr values are used
'indirectly', such as putting them in an enum and then using the enum values as
the case labels; it takes the same amount of time to compile.

% time g++-10 -v -o switch --save-temps switch.cpp
Using built-in specs.
COLLECT_GCC=g++-10
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/10/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa:hsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu
10.2.0-5ubuntu1~20.04' --with-bugurl=file:///usr/share/doc/gcc-10/README.Bugs
--enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++,m2 --prefix=/usr
--with-gcc-major-version-only --program-suffix=-10
--program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id
--libexecdir=/usr/lib --without-included-gettext --enable-threads=posix
--libdir=/usr/lib --enable-nls --enable-clocale=gnu --enable-libstdcxx-debug
--enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new
--enable-gnu-unique-object --disable-vtable-verify --enable-plugin
--enable-default-pie --with-system-zlib --enable-libphobos-checking=release
--with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch
--disable-werror --with-arch-32=i686 --with-abi=m64
--with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic
--enable-offload-targets=nvptx-none=/build/gcc-10-WJNXnb/gcc-10-10.2.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-10-WJNXnb/gcc-10-10.2.0/debian/tmp-gcn/usr,hsa
--without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu
--host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 10.2.0 (Ubuntu 10.2.0-5ubuntu1~20.04)
COLLECT_GCC_OPTIONS='-v' '-o' 'switch' '-save-temps' '-shared-libgcc'
'-mtune=generic' '-march=x86-64'
 /usr/lib/gcc/x86_64-linux-gnu/10/cc1plus -E -quiet -v -imultiarch
x86_64-linux-gnu -D_GNU_SOURCE switch.cpp -mtune=generic -march=x86-64
-fpch-preprocess -fasynchronous-unwind-tables -fstack-protector-strong -Wformat
-Wformat-security -fstack-clash-protection -fcf-protection -o switch.ii
ignoring duplicate directory "/usr/include/x86_64-linux-gnu/c++/10"
ignoring nonexistent directory "/usr/local/include/x86_64-linux-gnu"
ignoring nonexistent directory "/usr/lib/gcc/x86_64-linux-gnu/10/include-fixed"
ignoring nonexistent directory
"/usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/include/c++/10
 /usr/include/x86_64-linux-gnu/c++/10
 /usr/include/c++/10/backward
 /usr/lib/gcc/x86_64-linux-gnu/10/include
 /usr/local/include
 /usr/include/x86_64-linux-gnu
 /usr/include
End of search list.
COLLECT_GCC_OPTIONS='-v' '-o' 'switch' '-save-temps' '-shared-libgcc'
'-mtune=generic' '-march=x86-64'
 /usr/lib/gcc/x86_64-linux-gnu/10/cc1plus -fpreprocessed switch.ii -quiet
-dumpbase switch.cpp -mtune=generic -march=x86-64 -auxbase switch -version
-fasynchronous-unwind-tables -fstack-protector-strong -Wformat
-Wformat-security -fstack-clash-protection -fcf-protection -o switch.s
GNU C++14 (Ubuntu 10.2.0-5ubuntu1~20.04) version 10.2.0 (x86_64-linux-gnu)
        compiled by GNU C version 10.2.0, GMP version 6.2.0, MPFR version
4.0.2, MPC version 1.1.0, isl version isl-0.22.1-GMP

GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
GNU C++14 (Ubuntu 10.2.0-5ubuntu1~20.04) version 10.2.0 (x86_64-linux-gnu)
        compiled by GNU C version 10.2.0, GMP version 6.2.0, MPFR version
4.0.2, MPC version 1.1.0, isl version isl-0.22.1-GMP

GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
Compiler executable checksum: d716f9df9d1b12ebc8fe860554136f35
COLLECT_GCC_OPTIONS='-v' '-o' 'switch' '-save-temps' '-shared-libgcc'
'-mtune=generic' '-march=x86-64'
 as -v --64 -o switch.o switch.s
GNU assembler version 2.34 (x86_64-linux-gnu) using BFD version (GNU Binutils
for Ubuntu) 2.34
COMPILER_PATH=/usr/lib/gcc/x86_64-linux-gnu/10/:/usr/lib/gcc/x86_64-linux-gnu/10/:/usr/lib/gcc/x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/10/:/usr/lib/gcc/x86_64-linux-gnu/
LIBRARY_PATH=/usr/lib/gcc/x86_64-linux-gnu/10/:/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/10/../../../../lib/:/lib/x86_64-linux-gnu/:/lib/../lib/:/usr/lib/x86_64-linux-gnu/:/usr/lib/../lib/:/usr/lib/gcc/x86_64-linux-gnu/10/../../../:/lib/:/usr/lib/
COLLECT_GCC_OPTIONS='-v' '-o' 'switch' '-save-temps' '-shared-libgcc'
'-mtune=generic' '-march=x86-64'
 /usr/lib/gcc/x86_64-linux-gnu/10/collect2 -plugin
/usr/lib/gcc/x86_64-linux-gnu/10/liblto_plugin.so
-plugin-opt=/usr/lib/gcc/x86_64-linux-gnu/10/lto-wrapper
-plugin-opt=-fresolution=switch.res -plugin-opt=-pass-through=-lgcc_s
-plugin-opt=-pass-through=-lgcc -plugin-opt=-pass-through=-lc
-plugin-opt=-pass-through=-lgcc_s -plugin-opt=-pass-through=-lgcc --build-id
--eh-frame-hdr -m elf_x86_64 --hash-style=gnu --as-needed -dynamic-linker
/lib64/ld-linux-x86-64.so.2 -pie -z now -z relro -o switch
/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/Scrt1.o
/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crti.o
/usr/lib/gcc/x86_64-linux-gnu/10/crtbeginS.o -L/usr/lib/gcc/x86_64-linux-gnu/10
-L/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu
-L/usr/lib/gcc/x86_64-linux-gnu/10/../../../../lib -L/lib/x86_64-linux-gnu
-L/lib/../lib -L/usr/lib/x86_64-linux-gnu -L/usr/lib/../lib
-L/usr/lib/gcc/x86_64-linux-gnu/10/../../.. switch.o -lstdc++ -lm -lgcc_s -lgcc
-lc -lgcc_s -lgcc /usr/lib/gcc/x86_64-linux-gnu/10/crtendS.o
/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crtn.o
COLLECT_GCC_OPTIONS='-v' '-o' 'switch' '-save-temps' '-shared-libgcc'
'-mtune=generic' '-march=x86-64'
g++-10 -v -o switch --save-temps switch.cpp  25.61s user 0.00s system 99% cpu
25.656 total

% time clang++-10 -o switch --save-temps switch.cpp
clang++-10 -o switch --save-temps switch.cpp  0.18s user 0.03s system 89% cpu
0.244 total

[Bug tree-optimization/96979] Switch with case values derived from constexpr function takes unreasonable time to compile

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog
                 CC|                            |marxin at gcc dot gnu.org
     Ever confirmed|0                           |1
          Component|c++                         |tree-optimization
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2020-09-08

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  Interestingly -fsyntax-only is fast.  So we're in
switch-conversion:

    at /home/rguenther/src/gcc2/gcc/tree.h:5919
#2  0x0000000000e051a5 in wi::to_wide (t=<integer_cst 0x7ffff66659a8>, prec=64)
    at /home/rguenther/src/gcc2/gcc/tree.h:5930
#3  0x000000000111c193 in int_const_binop (code=MINUS_EXPR, 
    arg1=<integer_cst 0x7ffff66b4078>, arg2=<integer_cst 0x7ffff66659a8>, 
    overflowable=1) at /home/rguenther/src/gcc2/gcc/fold-const.c:1185
#4  0x000000000111c4a5 in const_binop (code=MINUS_EXPR, 
    arg1=<integer_cst 0x7ffff66b4078>, arg2=<integer_cst 0x7ffff66659a8>)
    at /home/rguenther/src/gcc2/gcc/fold-const.c:1242
#5  0x000000000111e901 in const_binop (code=MINUS_EXPR, 
    type=<integer_type 0x7ffff66270a8 u64>, arg1=<integer_cst 0x7ffff66b4078>, 
    arg2=<integer_cst 0x7ffff66659a8>)
    at /home/rguenther/src/gcc2/gcc/fold-const.c:1720
#6  0x00000000011444e6 in fold_binary_loc (loc=0, code=MINUS_EXPR, 
    type=<integer_type 0x7ffff66270a8 u64>, op0=<integer_cst 0x7ffff66b4078>, 
    op1=<integer_cst 0x7ffff66659a8>)
    at /home/rguenther/src/gcc2/gcc/fold-const.c:10286
#7  0x00000000011531b5 in fold_build2_loc (loc=0, code=MINUS_EXPR, 
    type=<integer_type 0x7ffff66270a8 u64>, op0=<integer_cst 0x7ffff66b4078>, 
--Type <RET> for more, q to quit, c to continue without paging--
    op1=<integer_cst 0x7ffff66659a8>)
    at /home/rguenther/src/gcc2/gcc/fold-const.c:13256
#8  0x00000000017fa079 in tree_switch_conversion::cluster::get_range (
    low=<integer_cst 0x7ffff66659a8>, high=<integer_cst 0x7ffff66b4078>)
    at /home/rguenther/src/gcc2/gcc/tree-switch-conversion.h:87
#9  0x00000000017f45e1 in
tree_switch_conversion::bit_test_cluster::can_be_handled (clusters=...,
start=168, end=839)
    at /home/rguenther/src/gcc2/gcc/tree-switch-conversion.c:1392
#10 0x00000000017f42b7 in
tree_switch_conversion::bit_test_cluster::find_bit_tests (clusters=...) at
/home/rguenther/src/gcc2/gcc/tree-switch-conversion.c:1322
#11 0x00000000017f5d0c in
tree_switch_conversion::switch_decision_tree::analyze_switch_statement
(this=0x7fffffffd990)

where tree_switch_conversion::bit_test_cluster::find_bit_tests takes ages
to complete.

[Bug tree-optimization/96979] [8/9/10/11 Regression] Switch with case values derived from constexpr function takes unreasonable time to compile

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |8.5
            Summary|Switch with case values     |[8/9/10/11 Regression]
                   |derived from constexpr      |Switch with case values
                   |function takes unreasonable |derived from constexpr
                   |time to compile             |function takes unreasonable
                   |                            |time to compile

[Bug tree-optimization/96979] [8/9/10/11 Regression] Switch with case values derived from constexpr function takes unreasonable time to compile

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Reduced testcase:

using u64 = unsigned long long;

constexpr inline u64
foo (const char *str) noexcept
{
  u64 value = 0xcbf29ce484222325ULL;
  for (u64 i = 0; str[i]; i++)
    value = (value ^ u64(str[i])) * 0x100000001b3ULL;
  return value;
}

struct V
{
  enum W
  {
#define A(n) n,
#define B(n) A(n##0) A(n##1) A(n##2) A(n##3) A(n##4) A(n##5) A(n##6) A(n##7)
A(n##8) A(n##9)
#define C(n) B(n##0) B(n##1) B(n##2) B(n##3) B(n##4) B(n##5) B(n##6) B(n##7)
B(n##8) B(n##9)
#define D(n) C(n##0) C(n##1) C(n##2) C(n##3) C(n##4) C(n##5) C(n##6) C(n##7)
C(n##8) C(n##9)
#define E D(foo1) D(foo2) D(foo3)
    E
    last
  };

  constexpr static W
  bar (const u64 h) noexcept
  {
    switch (h)
      {
#undef A
#define F(n) #n
#define A(n) case foo (F(n)): return n;
        E
      }
    return last;
  }
};

int
baz (const char *s)
{
  const u64 h = foo (s);
  return V::bar (h);
}

jump_table_cluster::find_jump_tables is indeed quadratic in the number of case
label clusters (3000 on the above testcase):
  for (unsigned i = 1; i <= l; i++)
    {
      /* Set minimal # of clusters with i-th item to infinite.  */
      min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));

      for (unsigned j = 0; j < i; j++)
        {
          unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
          if (i - j < case_values_threshold ())
            s += i - j;

          /* Prefer clusters with smaller number of numbers covered.  */
          if ((min[j].m_count + 1 < min[i].m_count
               || (min[j].m_count + 1 == min[i].m_count
                   && s < min[i].m_non_jt_cases))
              && can_be_handled (clusters, j, i - 1))
            min[i] = min_cluster_item (min[j].m_count + 1, j, s);
        }

      gcc_checking_assert (min[i].m_count != INT_MAX);
    }

[Bug tree-optimization/96979] [8/9/10/11 Regression] Switch with case values derived from constexpr function takes unreasonable time to compile

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |marxin at gcc dot gnu.org

--- Comment #3 from Martin Liška <marxin at gcc dot gnu.org> ---
Mine.

[Bug tree-optimization/96979] [8/9/10/11 Regression] Switch with case values derived from constexpr function takes unreasonable time to compile

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Martin Liska <marxin@gcc.gnu.org>:

https://gcc.gnu.org/g:c6df6039e9180c580945266302ec14047d358364

commit r11-3357-gc6df6039e9180c580945266302ec14047d358364
Author: Martin Liska <mliska@suse.cz>
Date:   Tue Sep 22 12:23:35 2020 +0200

    switch lowering: limit number of cluster attemps

    gcc/ChangeLog:

            PR tree-optimization/96979
            * doc/invoke.texi: Document new param
max-switch-clustering-attempts.
            * params.opt: Add new parameter.
            * tree-switch-conversion.c (jump_table_cluster::find_jump_tables):
            Limit number of attempts.
            (bit_test_cluster::find_bit_tests): Likewise.

    gcc/testsuite/ChangeLog:

            PR tree-optimization/96979
            * g++.dg/tree-ssa/pr96979.C: New test.

[Bug tree-optimization/96979] [9/10/11 Regression] Switch with case values derived from constexpr function takes unreasonable time to compile

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[8/9/10/11 Regression]      |[9/10/11 Regression] Switch
                   |Switch with case values     |with case values derived
                   |derived from constexpr      |from constexpr function
                   |function takes unreasonable |takes unreasonable time to
                   |time to compile             |compile
      Known to work|                            |11.0

--- Comment #5 from Martin Liška <marxin at gcc dot gnu.org> ---
GCC 8.x should be fine, compilation finished in 2 seconds.

[Bug tree-optimization/96979] [9/10/11 Regression] Switch with case values derived from constexpr function takes unreasonable time to compile

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Martin Liska <marxin@gcc.gnu.org>:

https://gcc.gnu.org/g:e46858e4eeee45d35ca4a7df1996186fe884879b

commit r11-3519-ge46858e4eeee45d35ca4a7df1996186fe884879b
Author: Martin Liska <mliska@suse.cz>
Date:   Thu Sep 24 13:34:13 2020 +0200

    switch conversion: make a rapid speed up

    gcc/ChangeLog:

            PR tree-optimization/96979
            * tree-switch-conversion.c (jump_table_cluster::can_be_handled):
            Make a fast bail out.
            (bit_test_cluster::can_be_handled): Likewise here.
            * tree-switch-conversion.h (get_range): Use wi::to_wide instead
            of a folding.

    gcc/testsuite/ChangeLog:

            PR tree-optimization/96979
            * g++.dg/tree-ssa/pr96979.C: New test.

[Bug tree-optimization/96979] [9/10/11 Regression] Switch with case values derived from constexpr function takes unreasonable time to compile

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Martin Liska
<marxin@gcc.gnu.org>:

https://gcc.gnu.org/g:b62c649466f3ae029bf348027ece9530f79d3ce1

commit r10-8839-gb62c649466f3ae029bf348027ece9530f79d3ce1
Author: Martin Liska <mliska@suse.cz>
Date:   Thu Sep 24 13:34:13 2020 +0200

    switch conversion: make a rapid speed up

    gcc/ChangeLog:

            PR tree-optimization/96979
            * tree-switch-conversion.c (jump_table_cluster::can_be_handled):
            Make a fast bail out.
            (bit_test_cluster::can_be_handled): Likewise here.
            * tree-switch-conversion.h (get_range): Use wi::to_wide instead
            of a folding.

    gcc/testsuite/ChangeLog:

            PR tree-optimization/96979
            * g++.dg/tree-ssa/pr96979.C: New test.

    (cherry picked from commit e46858e4eeee45d35ca4a7df1996186fe884879b)

[Bug tree-optimization/96979] [9/10/11 Regression] Switch with case values derived from constexpr function takes unreasonable time to compile

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #8 from Martin Liška <marxin at gcc dot gnu.org> ---
Not planning to backport to GCC 9 branch and older. The code is not 1:1 and I
don't want to introduce a new regression.