[Bug c++/111660] New: Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[Bug c++/111660] New: Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[envia at envia dot pe.kr]

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

            Bug ID: 111660
           Summary: Compilation of constexpr function returning enum takes
                    exponential time with -std=c++2a
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: envia at envia dot pe.kr
  Target Milestone: ---

Created attachment 56024
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56024&action=edit
It took more than 30 minutes.

It took more than 30 minutes when I compiled testcase.cc with g++ 14.0.0
20231001 on Debian GNU/Linux 12 with -std=gnu++2a (or gnu++20, c++2a, c++20).
I guess it is a regression because it finishes within 0.1 second with g++
13.2.0 or 12.3.0.
The testcase is based on GetOneCharToken() of V8.

[Bug c++/111660] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[envia at envia dot pe.kr]

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

--- Comment #1 from Hwang Joonhyung <envia at envia dot pe.kr> ---
Created attachment 56025
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56025&action=edit
It took 138 seconds.

[Bug c++/111660] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[envia at envia dot pe.kr]

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

--- Comment #2 from Hwang Joonhyung <envia at envia dot pe.kr> ---
Created attachment 56026
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56026&action=edit
It took 70 seconds.

[Bug c++/111660] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[envia at envia dot pe.kr]

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

--- Comment #3 from Hwang Joonhyung <envia at envia dot pe.kr> ---
Created attachment 56027
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56027&action=edit
It took 36 seconds.

[Bug c++/111660] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[envia at envia dot pe.kr]

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

--- Comment #4 from Hwang Joonhyung <envia at envia dot pe.kr> ---
I can see the time spent changes exponentially when I change the number of
ternary operators in the constexpr function.

[Bug c++/111660] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note for non-C++11 constexpr, using switch here would most likely be better .

[Bug c++/111660] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Hwang Joonhyung from comment #0)
> It took more than 30 minutes when I compiled testcase.cc with g++ 14.0.0
> 20231001 on Debian GNU/Linux 12 with -std=gnu++2a (or gnu++20, c++2a, c++20).
> I guess it is a regression because it finishes within 0.1 second with g++
> 13.2.0 or 12.3.0.
> The testcase is based on GetOneCharToken() of V8.

Does -fno-checking solve the performance issue?

[Bug c++/111660] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
  38.25%  cc1plus  cc1plus               [.] walk_tree_1        
  34.60%  cc1plus  cc1plus               [.] cp_fold_immediate_r    
  20.08%  cc1plus  cc1plus               [.] cp_walk_subtrees

[Bug c++/111660] [14 Regression] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-10-02
   Target Milestone|---                         |14.0
            Summary|Compilation of constexpr    |[14 Regression] Compilation
                   |function returning enum     |of constexpr function
                   |takes exponential time with |returning enum takes
                   |-std=c++2a                  |exponential time with
                   |                            |-std=c++2a

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I suspect r14-4140-g6851e3423c2b5e introduced the compile time slowness.

[Bug c++/111660] [14 Regression] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[envia at envia dot pe.kr]

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

--- Comment #9 from Hwang Joonhyung <envia at envia dot pe.kr> ---
(In reply to Andrew Pinski from comment #6)
> (In reply to Hwang Joonhyung from comment #0)
> > It took more than 30 minutes when I compiled testcase.cc with g++ 14.0.0
> > 20231001 on Debian GNU/Linux 12 with -std=gnu++2a (or gnu++20, c++2a, c++20).
> > I guess it is a regression because it finishes within 0.1 second with g++
> > 13.2.0 or 12.3.0.
> > The testcase is based on GetOneCharToken() of V8.
> 
> Does -fno-checking solve the performance issue?

No. It took almost the same time. I used -std=gnu++2a -fno-checking.

[Bug c++/111660] [14 Regression] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[envia at envia dot pe.kr]

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

--- Comment #10 from Hwang Joonhyung <envia at envia dot pe.kr> ---
(In reply to Andrew Pinski from comment #5)
> Note for non-C++11 constexpr, using switch here would most likely be better .

Thank you for the comment. It helped me to solve my problem.

[Bug c++/111660] [14 Regression] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[ppalka at gcc dot gnu.org]

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

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mpolacek at gcc dot gnu.org,
                   |                            |ppalka at gcc dot gnu.org

--- Comment #11 from Patrick Palka <ppalka at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #8)
> I suspect r14-4140-g6851e3423c2b5e introduced the compile time slowness.

Confirmed.

[Bug c++/111660] [14 Regression] Compilation of constexpr function returning enum takes exponential time with -std=c++2a

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

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

[Bug c++/111660] [14 Regression] Compilation of constexpr function returning enum takes exponential time with -std=c++2a since r14-4140-g6851e3423c2b5e

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

[Bug c++/111660] [14 Regression] Compilation of constexpr function returning enum takes exponential time with -std=c++2a since r14-4140-g6851e3423c2b5e

[mpolacek at gcc dot gnu.org]

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

--- Comment #12 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Candidate fix:

--- a/gcc/cp/cp-gimplify.cc
+++ b/gcc/cp/cp-gimplify.cc
@@ -1072,7 +1072,7 @@ cp_fold_immediate_r (tree *stmt_p, int *walk_subtrees,
void *data_)
       /* We're done here.  Don't clear *walk_subtrees here though: we're
called
     from cp_fold_r and we must let it recurse on the expression with
     cp_fold.  */
-      break;
+      return integer_zero_node;
     case PTRMEM_CST:
       if (TREE_CODE (PTRMEM_CST_MEMBER (stmt)) == FUNCTION_DECL
      && DECL_IMMEDIATE_FUNCTION_P (PTRMEM_CST_MEMBER (stmt)))
@@ -1145,7 +1145,8 @@ cp_fold_immediate (tree *tp, mce_value
manifestly_const_eval)
     flags |= ff_mce_false;

   cp_fold_data data (flags);
-  return !!cp_walk_tree_without_duplicates (tp, cp_fold_immediate_r, &data);
+  tree r = cp_walk_tree_without_duplicates (tp, cp_fold_immediate_r, &data);
+  return r == error_mark_node;
 }

 /* Perform any pre-gimplification folding of C++ front end trees to

[Bug c++/111660] [14 Regression] Compilation of constexpr function returning enum takes exponential time with -std=c++2a since r14-4140-g6851e3423c2b5e

[cvs-commit at gcc dot gnu.org]

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

--- Comment #13 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Marek Polacek <mpolacek@gcc.gnu.org>:

https://gcc.gnu.org/g:765c3b8f82d50961008c214ac2113f35e7532aa9

commit r14-4693-g765c3b8f82d50961008c214ac2113f35e7532aa9
Author: Marek Polacek <polacek@redhat.com>
Date:   Thu Oct 12 15:58:05 2023 -0400

    c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

    My recent patch introducing cp_fold_immediate_r caused exponential
    compile time with nested COND_EXPRs.  The problem is that the COND_EXPR
    case recursively walks the arms of a COND_EXPR, but after processing
    both arms it doesn't end the walk; it proceeds to walk the
    sub-expressions of the outermost COND_EXPR, triggering again walking
    the arms of the nested COND_EXPR, and so on.  This patch brings the
    compile time down to about 0m0.030s.

    The ff_fold_immediate flag is unused after this patch but since I'm
    using it in the P2564 patch, I'm not removing it now.  Maybe at_eof
    can be used instead and then we can remove ff_fold_immediate.

            PR c++/111660

    gcc/cp/ChangeLog:

            * cp-gimplify.cc (cp_fold_immediate_r) <case COND_EXPR>: Don't
            handle it here.
            (cp_fold_r): Handle COND_EXPR here.

    gcc/testsuite/ChangeLog:

            * g++.dg/cpp0x/hog1.C: New test.
            * g++.dg/cpp2a/consteval36.C: New test.

[Bug c++/111660] [14 Regression] Compilation of constexpr function returning enum takes exponential time with -std=c++2a since r14-4140-g6851e3423c2b5e

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

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

--- Comment #14 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Fixed.