On 5/5/26 1:20 PM, Patrick Palka wrote:
On Tue, 5 May 2026, Jason Merrill wrote:
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?
Good idea, done.
-/* 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?
Yeah, though in an earlier version of the patch the mapped values were
tri-state so using bool wasn't an option. I'm not keen on creating
a new map type just for this case, at least as part of this patch, the
memory savings should be negligible due to padding and type_tree_cache_map
is heavily used and well tested.
Agreed.
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>.
Using ((deletable)) results in a 10x -freflection slowdown for the
testcase from the PR, vs 1.1x with ((cache)), I suspect because it gets
cleared every time we complete a class.
Hunh, I'm surprised GC would happen often enough for that. Never mind,
then, thanks for checking.
+/* 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.
Fixed.
Here's v5 which uses a member function and fixes the above. The cache
is still marked as ((cache)) instead of ((deletable)).
-- >8 --
PR c++/125179
gcc/cp/ChangeLog:
* reflect.cc: (consteval_only_type_r): Remove this cp_walk_tree
callback and replace with ...
(consteval_only_walker): ... this recursive memoized
implementation.
(consteval_only_p): Define in terms of consteval_only_walker.
---
gcc/cp/reflect.cc | 134 ++++++++++++++++++++++++++++++++--------------
1 file changed, 93 insertions(+), 41 deletions(-)
diff --git a/gcc/cp/reflect.cc b/gcc/cp/reflect.cc
index 3b9f56ea5484..6e7000f7de81 100644
--- a/gcc/cp/reflect.cc
+++ b/gcc/cp/reflect.cc
@@ -8561,47 +8561,26 @@ splice (tree refl)
return refl;
}
-/* A walker for consteval_only_p. It cannot be a lambda, because we
- have to call this recursively, sigh. */
+/* A cache of the known boolean result of consteval_only_p_walker::walk for
+ class types. */
-static tree
-consteval_only_type_r (tree *tp, int *walk_subtrees, void *data)
-{
- 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;
+static GTY((cache)) type_tree_cache_map *consteval_only_class_cache;
- 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;
- }
+struct consteval_only_p_walker
+{
+ /* 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;
-}
+ tristate walk (tree);
+};
-/* 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 +8591,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 +8613,82 @@ 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_walker walker;
+ return walker.walk (t).is_true ();
+}
+
+/* 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. */
+
+tristate
+consteval_only_p_walker::walk (tree t)
+{
+ t = TYPE_MAIN_VARIANT (t);
+
+ if (REFLECTION_TYPE_P (t))
+ return true;
+ else if (INDIRECT_TYPE_P (t))
+ return walk (TREE_TYPE (t));
+ else if (TREE_CODE (t) == ARRAY_TYPE)
+ return walk (TREE_TYPE (t));
+ else if (FUNC_OR_METHOD_TYPE_P (t))
+ {
+ tristate r = walk (TREE_TYPE (t));
+ for (tree parm = TYPE_ARG_TYPES (t);
+ parm != NULL_TREE && parm != void_list_node;
+ parm = TREE_CHAIN (parm))
+ {
+ if (r.is_true ())
+ break;
+ r = r || walk (TREE_VALUE (parm));
+ }
+ 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 (class_seen.add (t))
+ {
+ /* Optimistically assume this already seen consteval-unknown class is
+ not consteval only, for sake of mutually recursive classes. */
+ optimistic_p = true;
+ return false;
+ }
+ 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 || walk (TREE_TYPE (member));
+ 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. */;
We might move the COMPLETE_TYPE check...
+ else if (r.is_true ())
+ hash_map_safe_put<hm_ggc> (consteval_only_class_cache,
+ t, boolean_true_node);
+ else if (r.is_false ()
...into another exception for the is_false case, since I don't think the
TYPE_FIELDS can change in a way that would invalidate is_true().
Actually, checking COMPLETE_TYPE_P here seems redundant with checking it
in the initializer of r above; can we just drop it (and move the comment
up)?
+ /* The optimistic assumption above is at odds with caching
+ 'false' results for a nested class type. */
+ && (class_stack.length () == 1 || !optimistic_p))
+ hash_map_safe_put<hm_ggc> (consteval_only_class_cache,
+ t, boolean_false_node);
+
+ class_stack.pop ();
+ return r;
+ }
+ else if (TYPE_PTRMEM_P (t))
+ return (walk (TYPE_PTRMEM_CLASS_TYPE (t))
+ || walk (TYPE_PTRMEM_POINTED_TO_TYPE (t)));
+ else
+ return false;
}
/* A walker for check_out_of_consteval_use_r. It cannot be a lambda, because
