[Bug c++/80290] [6/7 Regression] g++ uses unreasonable amount of memory compiling nested string maps

[rguenth at gcc dot gnu.org]

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

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
typedef std::pair<unsigned, std::pair<const char *, std::pair<const char *,
std::pair<const char *, const char *> > > > FruMap;
extern const FruMap frus[] = {
    { 1, { "", { "", {"",""}, }, }, },
};

is twice as fast as

typedef std::pair<unsigned, std::pair<const char *, std::pair<const char *,
std::pair<const char *, std::pair<const char *, const char *> > > > > FruMap;

extern const FruMap frus[] = {
    { 1, { "", { "", { "", {"",""}, }, } }, },
};

the latter with 70713 implicit_conversion calls while the former with "only"
14331 implicit_conversion calls.  Removing another std::pair<> level reduces
it to 4389 calls (still 10689 tsubst_copy_and_build calls(!)).

typedef std::pair<unsigned, std::pair<const char *, std::pair<const char *,
const char *> > > FruMap;
extern const FruMap frus[] = {
    { 1, { "", {"",""}, }, },
};  

constexpr evaluation seems to cause quite some bits of it.  The constexpr hash
is quite big and we arrive with following exprs to evaluate/cache:

{}
0 || 0
std::_PCC<false, const char*, const char*>::_ConstructiblePair<const char*,
const char*> ()
!std::_PCC<false, const char*, const char*>::_ImplicitlyConvertiblePair<const
char*, const char*> ()
std::_PCC<false, const char*, const char*>::_ConstructiblePair<const char*,
const char*> () && !std::_PCC<false, const char*, const
char*>::_ImplicitlyConvertiblePair<const char*, const char*> ()

and for the && we don't use the cached LHS we computed above because
we don't use maybe_constant_value for example in cxx_eval_logical_expression
but we recurse into cxx_eval_constant_expression!

A simple patch like

Index: gcc/cp/constexpr.c
===================================================================
--- gcc/cp/constexpr.c  (revision 246678)
+++ gcc/cp/constexpr.c  (working copy)
@@ -3860,6 +3860,9 @@ lookup_placeholder (const constexpr_ctx
   return ob;
 }

+static GTY((deletable)) hash_map<tree, tree> *cv_cache;
+
+
 /* Attempt to reduce the expression T to a constant value.
    On failure, issue diagnostic and return error_mark_node.  */
 /* FIXME unify with c_fully_fold */
@@ -3874,6 +3877,11 @@ cxx_eval_constant_expression (const cons
   constexpr_ctx new_ctx;
   tree r = t;

+  tree *cached;
+  if (cv_cache
+      && (cached = cv_cache->get (t)))
+    return *cached;
+
   if (jump_target && *jump_target)
     {
       /* If we are jumping, ignore all statements/expressions except those
@@ -4824,8 +4832,6 @@ fold_simple (tree t)
    Otherwise, if T does not have TREE_CONSTANT set, returns T.
    Otherwise, returns a version of T without TREE_CONSTANT.  */

-static GTY((deletable)) hash_map<tree, tree> *cv_cache;
-
 tree
 maybe_constant_value (tree t, tree decl)
 {

should improve this, but while it catches some cases it doesn't result in
an overall improvement.  The patch is likely incorrect anyway.

But I think it shows the issue (and likely the patch doesn't help because
"equivalent" calls are not detected as such by the cv_cache map which
ends up with pointer equivalence AFAICS).

Oh, and there are constexpr evaluations that do not go through the cache
anyway (potential_constant_expression, cxx_constant_value)