On 5/5/26 11:21 AM, Patrick Palka wrote:
On Tue, 5 May 2026, Patrick Palka wrote:
On Tue, 5 May 2026, Patrick Palka wrote:
On Tue, 5 May 2026, Jakub Jelinek wrote:
On Mon, May 04, 2026 at 09:25:06PM -0400, Patrick Palka wrote:
+ else if (RECORD_OR_UNION_TYPE_P (t))
+ {
+ if (tree *slot = hash_map_safe_get (consteval_only_class_cache, t))
+ return *slot == boolean_true_node;
+
+ if (class_set.add (t))
+ /* Handle struct A { A* p; } etc. */
+ return false;
+
+ tristate r = COMPLETE_TYPE_P (t) ? false : tristate::unknown ();
+ for (tree member = TYPE_FIELDS (t); member; member = DECL_CHAIN (member))
+ if (TREE_CODE (member) == FIELD_DECL)
+ {
+ r = r || consteval_only_p_1 (TREE_TYPE (member), class_set);
+ if (r.is_true ())
+ break;
+ }
+
+ if (COMPLETE_TYPE_P (t))
+ {
+ if (r.is_true ())
+ hash_map_safe_put<hm_ggc> (consteval_only_class_cache,
+ t, boolean_true_node);
+ else if (r.is_false ())
+ hash_map_safe_put<hm_ggc> (consteval_only_class_cache,
+ t, boolean_false_node);
+ }
+
+ class_set.remove (t);
Doesn't the above stmt result in really bad compile time complexity?
If I have say
struct S1;
struct S2;
struct S3 { S2 *a; };
struct S4 { S3 *a; };
struct S5 { S4 *a; };
...
struct S9999 { S9998 *a; };
struct S2 { S9999 *a; S1 *b; };
then when asking if S2 is consteval-only, this will walk ~10000^2 types
rather than just ~10000 types. Wouldn't it be better to
class_set.add (t) and never remove, but if we trigger that return false;
in there, remember that we shouldn't cache r.is_false () results (perhaps
with the exception when this was the non-recursive call)?
Yes, and the current patch is buggy for:
struct B { A* p; };
struct A {
B m;
meta::info n;
};
We'd incorrectly deem B not consteval-only if we first walk it from A.
It's apparently important for the testcase from this PR to return false
rather than unknown when detecting mutual recursion, otherwise we still
get a 4x slowdown.
The reason it's important to optimistically return false upon hitting
mutual recursion is so that we get a chance to cache the result.
Otherwise we'll never cache the result for some mutually recursive
types; consteval_only_p_1 will always return unknown.
But if we must return false in the case of mutual
recursion then indeed it's not safe to cache r.is_false () results
except for the outermost class because of scenarios like B above.
To fix this efficiently I think we need to maintian both a class_seen
set and a class_stack. What do you think of the following?
-- >8 --
PR c++/125179
gcc/cp/ChangeLog:
* reflect.cc: Include <algorithm>.
(consteval_only_type_r): Remove this cp_walk_tree callback and
replace with ...
(consteval_only_p_state, consteval_only_class_cache)
(consteval_only_p_1): ... this recursive memoized implementation.
(consteval_only_p): Define in terms of consteval_only_p_1.
---
gcc/cp/reflect.cc | 138 ++++++++++++++++++++++++++++++++--------------
1 file changed, 97 insertions(+), 41 deletions(-)
diff --git a/gcc/cp/reflect.cc b/gcc/cp/reflect.cc
index 3b9f56ea5484..67a1e1b85895 100644
--- a/gcc/cp/reflect.cc
+++ b/gcc/cp/reflect.cc
@@ -20,6 +20,7 @@ along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#include "config.h"
+#define INCLUDE_ALGORITHM
#include "system.h"
#include "coretypes.h"
#include "target.h"
@@ -8561,47 +8562,22 @@ splice (tree refl)
return refl;
}
-/* A walker for consteval_only_p. It cannot be a lambda, because we
- have to call this recursively, sigh. */
+/* State maintained during consteval_only_p_1 recursion. */
-static tree
-consteval_only_type_r (tree *tp, int *walk_subtrees, void *data)
+struct consteval_only_p_state
{
- tree t = *tp;
- /* Types can contain themselves recursively, hence this. */
- auto visited = static_cast<hash_set<tree> *>(data);
-
- if (!TYPE_P (t))
- return NULL_TREE;
-
- if (REFLECTION_TYPE_P (t))
- return t;
-
- if (typedef_variant_p (t))
- /* Tell cp_walk_subtrees to look through typedefs. */
- *walk_subtrees = 2;
-
- if (RECORD_OR_UNION_TYPE_P (t))
- {
- /* Don't walk template arguments; A<info>::type isn't a consteval-only
- type. */
- *walk_subtrees = 0;
- /* So we have to walk the fields manually. */
- for (tree member = TYPE_FIELDS (t);
- member; member = DECL_CHAIN (member))
- if (TREE_CODE (member) == FIELD_DECL)
- if (tree r = cp_walk_tree (&TREE_TYPE (member),
- consteval_only_type_r, visited, visited))
- return r;
- }
+ /* The stack of class types we're recursively inside. */
+ auto_vec<tree> class_stack;
+ /* The set of class types we've seen. */
+ hash_set<tree> class_seen;
+ /* Whether we've seen mutual class recursion. */
+ bool seen_mutual_recursion = false;
+};
- return NULL_TREE;
-}
+static tristate consteval_only_p_1 (tree, consteval_only_p_state&);
-/* True if T is a consteval-only type as per [basic.types.general]:
- "A type is consteval-only if it is either std::meta::info or a type
- compounded from a consteval-only type", or something that has
- a consteval-only type. */
+/* True if T is a consteval-only type as per [basic.types.general], or
+ is a declaration with such a type, or a TREE_VEC thereof. */
bool
consteval_only_p (tree t)
@@ -8612,7 +8588,7 @@ consteval_only_p (tree t)
if (!TYPE_P (t))
t = TREE_TYPE (t);
- if (!t)
+ if (!t || t == error_mark_node)
return false;
if (TREE_CODE (t) == TREE_VEC)
@@ -8634,9 +8610,89 @@ consteval_only_p (tree t)
which could be consteval-only, depending on T. */
t = complete_type (t);
- /* Classes with std::meta::info members are also consteval-only. */
- hash_set<tree> visited;
- return !!cp_walk_tree (&t, consteval_only_type_r, &visited, &visited);
+ consteval_only_p_state state;
+ return consteval_only_p_1 (t, state).is_true ();
+}
+
+/* A cache of the boolean result of consteval_only_p_1 for class types, when
+ the result is known. */
+
+static GTY((cache)) type_tree_cache_map *consteval_only_class_cache;
+
+/* Recursive workhorse of consteval_only_p. Returns true if T is definitely
+ consteval-only, false if it's definitely not, and unknown if we saw an
+ incomplete type and therefore don't know. */
+
+static tristate
+consteval_only_p_1 (tree t, consteval_only_p_state& state)
+{
+ t = TYPE_MAIN_VARIANT (t);
+
+ if (REFLECTION_TYPE_P (t))
+ return true;
+ else if (INDIRECT_TYPE_P (t))
+ return consteval_only_p_1 (TREE_TYPE (t), state);
+ else if (TREE_CODE (t) == ARRAY_TYPE)
+ return consteval_only_p_1 (TREE_TYPE (t), state);
+ else if (FUNC_OR_METHOD_TYPE_P (t))
+ {
+ tristate r = consteval_only_p_1 (TREE_TYPE (t), state);
+ for (tree parm = TYPE_ARG_TYPES (t);
+ parm != NULL_TREE && parm != void_list_node;
+ parm = TREE_CHAIN (parm))
+ {
+ r = r || consteval_only_p_1 (TREE_VALUE (parm), state);
+ if (r.is_true ())
+ break;
+ }
+ return r;
+ }
+ else if (RECORD_OR_UNION_TYPE_P (t))
+ {
+ if (tree *slot = hash_map_safe_get (consteval_only_class_cache, t))
+ return *slot == boolean_true_node;
+
+ if (state.class_seen.add (t))
+ {
+ auto begin = state.class_stack.begin ();
+ auto end = state.class_stack.end ();
+ auto it = std::find (begin, end, t);
+ if (it != end && it != &state.class_stack.last ())
+ state.seen_mutual_recursion = true;
+
+ return false;
+ }
+ state.class_stack.safe_push (t);
+
+ tristate r = COMPLETE_TYPE_P (t) ? false : tristate::unknown ();
+ for (tree member = TYPE_FIELDS (t); member; member = DECL_CHAIN (member))
+ if (TREE_CODE (member) == FIELD_DECL)
+ {
+ r = r || consteval_only_p_1 (TREE_TYPE (member), state);
+ if (r.is_true ())
+ break;
+ }
+
+ if (!COMPLETE_TYPE_P (t))
+ /* Until the type is laid out, we can't trust that its TYPE_FIELDS
+ won't change. */;
+ else if (r.is_true ())
+ hash_map_safe_put<hm_ggc> (consteval_only_class_cache,
+ t, boolean_true_node);
+ else if (r.is_false ()
+ && (state.class_stack.length () == 1
+ || !state.seen_mutual_recursion))
D'oh, this !state.seen_mutual_recursion exception for caching nested
types is wrong.
struct A {
struct B { struct C *c; } b;
struct C { B b; } c;
};
Here if we start walking from A, which is not mutually recursively, we
first correctly deem B as unknown-consteval-only, but then go on to
deem the nested C as not consteval only _and_ cache it (since there's
no mutual recursion).
So being optimistic about mutually recursive types (the
'if (class_seen.add (t)) return false' early exit) is at odds
with caching the result for nested class types in general, unless
we significantly complicate things which is probably not worth it.
Oh, we can just remember if we ever took the early exit and only disable
false result caching for nested classes in that case. That should be
safe, I think (famous last words), and allow us to cache nested classes
in more cases. So for
struct A {
struct B { int n; } b;
};
the false result for B will be cached, but for
struct A {
struct B { A* a; } b;
struct C { int n; } c;
};
neither the false result for B or for C will be cached.
Here is v4 that introduces an 'optimistic_p' flag to that effect. This
reduces the -freflection slowdown for the TU to 1.1x from 1.2x compared
to v3.
-- >8 --
PR c++/125179
gcc/cp/ChangeLog:
* reflect.cc: (consteval_only_type_r): Remove this cp_walk_tree
callback and replace with ...
(consteval_only_p_state, consteval_only_class_cache)
(consteval_only_p_1): ... this recursive memoized implementation.
(consteval_only_p): Define in terms of consteval_only_p_1.
---
gcc/cp/reflect.cc | 136 ++++++++++++++++++++++++++++++++--------------
1 file changed, 95 insertions(+), 41 deletions(-)
diff --git a/gcc/cp/reflect.cc b/gcc/cp/reflect.cc
index 3b9f56ea5484..e9bd301fb84b 100644
--- a/gcc/cp/reflect.cc
+++ b/gcc/cp/reflect.cc
@@ -8561,47 +8561,23 @@ splice (tree refl)
return refl;
}
-/* A walker for consteval_only_p. It cannot be a lambda, because we
- have to call this recursively, sigh. */
+/* State maintained during consteval_only_p_1 recursion. */
-static tree
-consteval_only_type_r (tree *tp, int *walk_subtrees, void *data)
+struct consteval_only_p_state
{
- tree t = *tp;
- /* Types can contain themselves recursively, hence this. */
- auto visited = static_cast<hash_set<tree> *>(data);
-
- if (!TYPE_P (t))
- return NULL_TREE;
-
- if (REFLECTION_TYPE_P (t))
- return t;
-
- if (typedef_variant_p (t))
- /* Tell cp_walk_subtrees to look through typedefs. */
- *walk_subtrees = 2;
-
- if (RECORD_OR_UNION_TYPE_P (t))
- {
- /* Don't walk template arguments; A<info>::type isn't a consteval-only
- type. */
- *walk_subtrees = 0;
- /* So we have to walk the fields manually. */
- for (tree member = TYPE_FIELDS (t);
- member; member = DECL_CHAIN (member))
- if (TREE_CODE (member) == FIELD_DECL)
- if (tree r = cp_walk_tree (&TREE_TYPE (member),
- consteval_only_type_r, visited, visited))
- return r;
- }
+ /* The stack of class types we're recursively inside. */
+ auto_vec<tree> class_stack;
+ /* The set of class types we've seen. */
+ hash_set<tree> class_seen;
+ /* True if we've optimistically assumed an already-seen
+ consteval-unknown class type is not consteval. */
+ bool optimistic_p = false;
+};
- return NULL_TREE;
-}
+static tristate consteval_only_p_1 (tree, consteval_only_p_state&);
How about making this a member function of consteval_only_p_state
instead of a free function with a reference parameter?
-/* True if T is a consteval-only type as per [basic.types.general]:
- "A type is consteval-only if it is either std::meta::info or a type
- compounded from a consteval-only type", or something that has
- a consteval-only type. */
+/* True if T is a consteval-only type as per [basic.types.general], or
+ is a declaration with such a type, or a TREE_VEC thereof. */
bool
consteval_only_p (tree t)
@@ -8612,7 +8588,7 @@ consteval_only_p (tree t)
if (!TYPE_P (t))
t = TREE_TYPE (t);
- if (!t)
+ if (!t || t == error_mark_node)
return false;
if (TREE_CODE (t) == TREE_VEC)
@@ -8634,9 +8610,87 @@ consteval_only_p (tree t)
which could be consteval-only, depending on T. */
t = complete_type (t);
- /* Classes with std::meta::info members are also consteval-only. */
- hash_set<tree> visited;
- return !!cp_walk_tree (&t, consteval_only_type_r, &visited, &visited);
+ consteval_only_p_state state;
+ return consteval_only_p_1 (t, state).is_true ();
+}
+
+/* A cache of the boolean result of consteval_only_p_1 for class types, when
+ the result is known. */
+
+static GTY((cache)) type_tree_cache_map *consteval_only_class_cache;
Since you aren't actually returning the tree value, I guess you're using
type_tree_cache_map mostly because it's an existing type and there isn't
one for type to bool?
Also, from gty.texi:
Note that caches should generally use @code{deletable} instead;
@code{cache} is only preferable if the value is impractical to
recompute from the key when needed.
This seems like a ((deletable)) case to me, so we could just use
hash_map<tree,bool>.
+
+/* Recursive workhorse of consteval_only_p. Returns true if T is definitely
+ consteval-only, false if it's definitely not, and unknown if we saw an
+ incomplete type and therefore don't know. */
+
+static tristate
+consteval_only_p_1 (tree t, consteval_only_p_state& state)
+{
+ t = TYPE_MAIN_VARIANT (t);
+
+ if (REFLECTION_TYPE_P (t))
+ return true;
+ else if (INDIRECT_TYPE_P (t))
+ return consteval_only_p_1 (TREE_TYPE (t), state);
+ else if (TREE_CODE (t) == ARRAY_TYPE)
+ return consteval_only_p_1 (TREE_TYPE (t), state);
+ else if (FUNC_OR_METHOD_TYPE_P (t))
+ {
+ tristate r = consteval_only_p_1 (TREE_TYPE (t), state);
+ for (tree parm = TYPE_ARG_TYPES (t);
+ parm != NULL_TREE && parm != void_list_node;
+ parm = TREE_CHAIN (parm))
+ {
+ r = r || consteval_only_p_1 (TREE_VALUE (parm), state);
+ if (r.is_true ())
Let's move the is_true check before the || so that we don't look at the
first parm when the return type is consteval-only.
+ break;
+ }
+ return r;
+ }
+ else if (RECORD_OR_UNION_TYPE_P (t))
+ {
+ if (tree *slot = hash_map_safe_get (consteval_only_class_cache, t))
+ return *slot == boolean_true_node;
+
+ if (state.class_seen.add (t))
+ {
+ /* Optimistically assume this already seen consteval-unknown class is
+ not consteval only, for sake of mutually recursive classes. */
+ state.optimistic_p = true;
+ return false;
+ }
+ state.class_stack.safe_push (t);
+
+ tristate r = COMPLETE_TYPE_P (t) ? false : tristate::unknown ();
+ for (tree member = TYPE_FIELDS (t); member; member = DECL_CHAIN (member))
+ if (TREE_CODE (member) == FIELD_DECL)
+ {
+ r = r || consteval_only_p_1 (TREE_TYPE (member), state);
+ if (r.is_true ())
+ break;
+ }
+
+ if (!COMPLETE_TYPE_P (t))
+ /* Until the type is laid out, we can't trust that its TYPE_FIELDS
+ won't change. */;
+ else if (r.is_true ())
+ hash_map_safe_put<hm_ggc> (consteval_only_class_cache,
+ t, boolean_true_node);
+ else if (r.is_false ()
+ /* The optimistic assumption above is at odds with caching
+ 'false' results for a nested class type. */
+ && (state.class_stack.length () == 1 || !state.optimistic_p))
+ hash_map_safe_put<hm_ggc> (consteval_only_class_cache,
+ t, boolean_false_node);
+
+ state.class_stack.pop ();
+ return r;
+ }
+ else if (TYPE_PTRMEM_P (t))
+ return (consteval_only_p_1 (TYPE_PTRMEM_CLASS_TYPE (t), state)
+ || consteval_only_p_1 (TYPE_PTRMEM_POINTED_TO_TYPE (t), state));
+ else
+ return false;
}
/* A walker for check_out_of_consteval_use_r. It cannot be a lambda, because
