[gcc r16-1187] c++: quadratic constexpr folding of arith expr [PR118340]

[Patrick Palka via Gcc-cvs]

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

commit r16-1187-ge71c0157478e49188cd754693dcc2059d63573e9
Author: Patrick Palka <ppa...@redhat.com>
Date:   Thu Jun 5 11:06:04 2025 -0400

    c++: quadratic constexpr folding of arith expr [PR118340]
    
    Here the PR's testcase demonstrates that the cp_fully_fold calls in
    cp_build_binary_op (for diagnosing arithmetic overflow) lead to
    quadratic behavior when building up a large arithmetic constant
    expression.  The problem is ultimately that maybe_constant_value's
    caching doesn't reuse intermediate values, unlike cp_fold.  (And
    unfortunately we can't leverage the cp_fold cache in this call site
    because here we want to evaluate constexpr calls even in -O0, which
    cp_fold avoids.)
    
    This patch fixes this by making maybe_constant_value look up each
    operand of the given expression to see if we've previously reduced it,
    and if so, rebuild the expression using the (presumably) reduced
    operands and evaluate that.  After this patch each version of the
    testcase from the PR compiles in ~0.1s on my machine.
    
            PR c++/118340
    
    gcc/cp/ChangeLog:
    
            * constexpr.cc (maybe_constant_value): First try looking up each
            operand in the cv_cache and reusing the result.
    
    Reviewed-by: Jason Merrill <ja...@redhat.com>

Diff:
---
 gcc/cp/constexpr.cc | 33 ++++++++++++++++++++++++++++++++-
 1 file changed, 32 insertions(+), 1 deletion(-)

diff --git a/gcc/cp/constexpr.cc b/gcc/cp/constexpr.cc
index c0e37b2fd35c..707883955b10 100644
--- a/gcc/cp/constexpr.cc
+++ b/gcc/cp/constexpr.cc
@@ -9488,8 +9488,35 @@ tree
 maybe_constant_value (tree t, tree decl /* = NULL_TREE */,
                      mce_value manifestly_const_eval /* = mce_unknown */)
 {
+  tree orig_t = t;
   tree r;
 
+  if (EXPR_P (t) && manifestly_const_eval == mce_unknown)
+    {
+      /* Look up each operand in the cv_cache first to see if we've already
+        reduced it, and reuse that result to avoid quadratic behavior if
+        we're called when building up a large expression.  */
+      int n = cp_tree_operand_length (t);
+      tree *ops = XALLOCAVEC (tree, n);
+      bool rebuild = false;
+      for (int i = 0; i < n; ++i)
+       {
+         ops[i] = TREE_OPERAND (t, i);
+         if (tree *cached = hash_map_safe_get (cv_cache, ops[i]))
+           if (*cached != ops[i])
+             {
+               ops[i] = *cached;
+               rebuild = true;
+             }
+       }
+      if (rebuild)
+       {
+         t = copy_node (t);
+         for (int i = 0; i < n; ++i)
+           TREE_OPERAND (t, i) = ops[i];
+       }
+    }
+
   if (!is_nondependent_constant_expression (t))
     {
       if (TREE_OVERFLOW_P (t)
@@ -9507,6 +9534,10 @@ maybe_constant_value (tree t, tree decl /* = NULL_TREE 
*/,
     return fold_to_constant (t);
 
   if (manifestly_const_eval != mce_unknown)
+    /* TODO: Extend the cache to be mce_value aware.  And if we have a
+       previously cached mce_unknown result that's TREE_CONSTANT, it means
+       the reduced value is independent of mce_value and so we should
+       be able to reuse it in the mce_true/false case.  */
     return cxx_eval_outermost_constant_expr (t, true, true,
                                             manifestly_const_eval, false, 
decl);
 
@@ -9536,7 +9567,7 @@ maybe_constant_value (tree t, tree decl /* = NULL_TREE */,
                       || (TREE_CONSTANT (t) && !TREE_CONSTANT (r))
                       || !cp_tree_equal (r, t));
   if (!c.evaluation_restricted_p ())
-    cv_cache->put (t, r);
+    cv_cache->put (orig_t, r);
   return r;
 }