From 79c05c2bc49b4880ec4789d4078178e27821f268 Mon Sep 17 00:00:00 2001 From: Andrew Sutton Date: Thu, 24 Oct 2019 15:03:49 +0000 Subject: [PATCH] Finish moving constraint and logic functionality of out pt.c. Also, reimplement and re-enable subsumption caching. gcc/cp/ * config-lang.in (gtfiles): Add logic.cc. * constraint.cc (atomic_constraints_identical_p): Add assertions. (hash_atomic_constraint): Likewise. (constraints_equivalent_p): New. (inchash::add_constraint): New. (iterative_hash_constraint): New. (decl_constraints): Moved from pt.c. (get_constraints): Likewise. (set_constraints): Likewise. (remove_constraints): Likewise. * cp-tree.h (CONSTR_P): New. (init_constraint_processing): Remove. (constraints_equivalent_p, iterative_hash_constraint): Declare. * decl.c (cxx_init_decl_processing): Don't initialize constraints. * logic.cc (subsumption_entry): Moved from pt.c. (subsumption_hasher): Likewise. (subsumption_cache): Likewise. (lookup_subsumption): Likewise. (save_subsumption): Likewise. (subsumes_constraints_nonnull): Use subsumption cache. * pt.c: Move aforementioned declarations out of this file. (init_constraint_processing): Remove. From-SVN: r277407 --- gcc/cp/ChangeLog | 28 ++++++++ gcc/cp/config-lang.in | 2 +- gcc/cp/constraint.cc | 128 ++++++++++++++++++++++++++++++++++ gcc/cp/cp-tree.h | 11 ++- gcc/cp/decl.c | 3 - gcc/cp/logic.cc | 83 ++++++++++++++++++++-- gcc/cp/pt.c | 157 ------------------------------------------ 7 files changed, 244 insertions(+), 168 deletions(-) diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog index dcf192a7af9..1917b8c4f59 100644 --- a/gcc/cp/ChangeLog +++ b/gcc/cp/ChangeLog @@ -149,6 +149,34 @@ * decl.c (cxx_maybe_build_cleanup): When clearing location of cleanup, if cleanup is a nop, clear location of its operand too. +2019-10-15 Andrew Sutton + + Finish moving constraint and logic functionality of out pt.c. + Reimplement and re-enable subsumption caching. + + * config-lang.in (gtfiles): Add logic.cc. + * constraint.cc (atomic_constraints_identical_p): Add assertions. + (hash_atomic_constraint): Likewise. + (constraints_equivalent_p): New. + (inchash::add_constraint): New. + (iterative_hash_constraint): New. + (decl_constraints): Moved from pt.c. + (get_constraints): Likewise. + (set_constraints): Likewise. + (remove_constraints): Likewise. + * cp-tree.h (CONSTR_P): New. + (init_constraint_processing): Remove. + (constraints_equivalent_p, iterative_hash_constraint): Declare. + * decl.c (cxx_init_decl_processing): Don't initialize constraints. + * logic.cc (subsumption_entry): Moved from pt.c. + (subsumption_hasher): Likewise. + (subsumption_cache): Likewise. + (lookup_subsumption): Likewise. + (save_subsumption): Likewise. + (subsumes_constraints_nonnull): Use subsumption cache. + * pt.c: Move aforementioned declarations out of this file. + (init_constraint_processing): Remove. + 2019-10-15 Andrew Sutton * parser.c (cp_parser_constructor_declarator_p): Pass an empty diff --git a/gcc/cp/config-lang.in b/gcc/cp/config-lang.in index adfe1b2415d..0176866a045 100644 --- a/gcc/cp/config-lang.in +++ b/gcc/cp/config-lang.in @@ -46,7 +46,7 @@ gtfiles="\ \$(srcdir)/cp/except.c \ \$(srcdir)/cp/friend.c \ \$(srcdir)/cp/init.c \ -\$(srcdir)/cp/lambda.c \$(srcdir)/cp/lex.c \ +\$(srcdir)/cp/lambda.c \$(srcdir)/cp/lex.c \$(srcdir)/cp/logic.cc \ \$(srcdir)/cp/mangle.c \$(srcdir)/cp/method.c \ \$(srcdir)/cp/name-lookup.c \ \$(srcdir)/cp/parser.c \$(srcdir)/cp/pt.c \ diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index db4a81858f6..b8a2645d8c9 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -905,6 +905,9 @@ normalize_constraint_expression (tree expr, bool diag = false) bool atomic_constraints_identical_p (tree t1, tree t2) { + gcc_assert (TREE_CODE (t1) == ATOMIC_CONSTR); + gcc_assert (TREE_CODE (t2) == ATOMIC_CONSTR); + if (ATOMIC_CONSTR_EXPR (t1) != ATOMIC_CONSTR_EXPR (t2)) return false; @@ -914,9 +917,44 @@ atomic_constraints_identical_p (tree t1, tree t2) return true; } +/* True if T1 and T2 are equivalent, meaning they have the same syntactic + structure and all corresponding constraints are identical. */ + +bool +constraints_equivalent_p (tree t1, tree t2) +{ + gcc_assert (CONSTR_P (t1)); + gcc_assert (CONSTR_P (t2)); + + if (TREE_CODE (t1) != TREE_CODE (t2)) + return false; + + switch (TREE_CODE (t1)) + { + case CONJ_CONSTR: + case DISJ_CONSTR: + if (!constraints_equivalent_p (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0))) + return false; + if (!constraints_equivalent_p (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1))) + return false; + break; + case ATOMIC_CONSTR: + if (!atomic_constraints_identical_p(t1, t2)) + return false; + break; + default: + gcc_unreachable (); + } + return true; +} + +/* Compute the hash value for T. */ + hashval_t hash_atomic_constraint (tree t) { + gcc_assert (TREE_CODE (t) == ATOMIC_CONSTR); + /* Hash the identity of the expression. */ hashval_t val = htab_hash_pointer (ATOMIC_CONSTR_EXPR (t)); @@ -931,6 +969,41 @@ hash_atomic_constraint (tree t) return val; } +namespace inchash +{ + +static void +add_constraint (tree t, hash& h) +{ + h.add_int(TREE_CODE (t)); + switch (TREE_CODE (t)) + { + case CONJ_CONSTR: + case DISJ_CONSTR: + add_constraint (TREE_OPERAND (t, 0), h); + add_constraint (TREE_OPERAND (t, 1), h); + break; + case ATOMIC_CONSTR: + h.merge_hash (hash_atomic_constraint (t)); + break; + default: + gcc_unreachable (); + } +} + +} + +/* Computes a hash code for the constraint T. */ + +hashval_t +iterative_hash_constraint (tree t, hashval_t val) +{ + gcc_assert (CONSTR_P (t)); + inchash::hash h (val); + inchash::add_constraint (t, h); + return h.end (); +} + // -------------------------------------------------------------------------- // // Constraint Semantic Processing // @@ -1017,6 +1090,61 @@ build_constraints (tree tr, tree dr) return (tree)ci; } +/* A mapping from declarations to constraint information. */ + +static GTY ((cache)) tree_cache_map *decl_constraints; + +/* Returns the template constraints of declaration T. If T is not + constrained, return NULL_TREE. Note that T must be non-null. */ + +tree +get_constraints (tree t) +{ + if (!flag_concepts) + return NULL_TREE; + if (!decl_constraints) + return NULL_TREE; + + gcc_assert (DECL_P (t)); + if (TREE_CODE (t) == TEMPLATE_DECL) + t = DECL_TEMPLATE_RESULT (t); + tree* found = decl_constraints->get (t); + if (found) + return *found; + else + return NULL_TREE; +} + +/* Associate the given constraint information CI with the declaration + T. If T is a template, then the constraints are associated with + its underlying declaration. Don't build associations if CI is + NULL_TREE. */ + +void +set_constraints (tree t, tree ci) +{ + if (!ci) + return; + gcc_assert (t && flag_concepts); + if (TREE_CODE (t) == TEMPLATE_DECL) + t = DECL_TEMPLATE_RESULT (t); + bool found = hash_map_safe_put (decl_constraints, t, ci); + gcc_assert (!found); +} + +/* Remove the associated constraints of the declaration T. */ + +void +remove_constraints (tree t) +{ + gcc_assert (DECL_P (t)); + if (TREE_CODE (t) == TEMPLATE_DECL) + t = DECL_TEMPLATE_RESULT (t); + + if (decl_constraints) + decl_constraints->remove (t); +} + /* Returns the template-head requires clause for the template declaration T or NULL_TREE if none. */ diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h index e307ac8d9fd..7e0c41c222e 100644 --- a/gcc/cp/cp-tree.h +++ b/gcc/cp/cp-tree.h @@ -1551,6 +1551,12 @@ check_constraint_info (tree t) #define PLACEHOLDER_TYPE_CONSTRAINTS(NODE) \ DECL_SIZE_UNIT (TYPE_NAME (NODE)) +/* True if NODE is a constraint. */ +#define CONSTR_P(NODE) \ + (TREE_CODE (NODE) == ATOMIC_CONSTR \ + || TREE_CODE (NODE) == CONJ_CONSTR \ + || TREE_CODE (NODE) == DISJ_CONSTR) + /* Valid for any normalized constraint. */ #define CONSTR_CHECK(NODE) \ TREE_CHECK3 (NODE, ATOMIC_CONSTR, CONJ_CONSTR, DISJ_CONSTR) @@ -7693,7 +7699,6 @@ struct diagnosing_failed_constraint /* in constraint.cc */ -extern void init_constraint_processing (); extern cp_expr finish_constraint_or_expr (location_t, cp_expr, cp_expr); extern cp_expr finish_constraint_and_expr (location_t, cp_expr, cp_expr); extern cp_expr finish_constraint_primary_expr (cp_expr); @@ -7761,8 +7766,10 @@ extern bool subsumes_constraints (tree, tree); extern bool strictly_subsumes (tree, tree, tree); extern bool weakly_subsumes (tree, tree, tree); extern int more_constrained (tree, tree); +extern bool constraints_equivalent_p (tree, tree); extern bool atomic_constraints_identical_p (tree, tree); -extern hashval_t hash_atomic_constraint (tree); +extern hashval_t iterative_hash_constraint (tree, hashval_t); +extern hashval_t hash_atomic_constraint (tree); extern void diagnose_constraints (location_t, tree, tree); /* in logic.cc */ diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c index 5d51442362c..6c90b1d030a 100644 --- a/gcc/cp/decl.c +++ b/gcc/cp/decl.c @@ -4409,9 +4409,6 @@ cxx_init_decl_processing (void) /* Ensure attribs.c is initialized. */ init_attributes (); - /* Ensure constraint.cc is initialized. */ - init_constraint_processing (); - extvisattr = build_tree_list (get_identifier ("externally_visible"), NULL_TREE); newattrs = tree_cons (get_identifier ("alloc_size"), diff --git a/gcc/cp/logic.cc b/gcc/cp/logic.cc index 2d4abaf6edd..ee68b54c0ad 100644 --- a/gcc/cp/logic.cc +++ b/gcc/cp/logic.cc @@ -780,6 +780,73 @@ diagnose_constraint_size (tree t) return false; } +/* Key/value pair for caching subsumption results. This associates a pair of + constraints with a boolean value indicating the result. */ + +struct GTY((for_user)) subsumption_entry +{ + tree lhs; + tree rhs; + bool result; +}; + +/* Hashing function and equality for constraint entries. */ + +struct subsumption_hasher : ggc_ptr_hash +{ + static hashval_t hash (subsumption_entry *e) + { + hashval_t val = 0; + val = iterative_hash_constraint (e->lhs, val); + val = iterative_hash_constraint (e->rhs, val); + return val; + } + + static bool equal (subsumption_entry *e1, subsumption_entry *e2) + { + if (!constraints_equivalent_p (e1->lhs, e2->lhs)) + return false; + if (!constraints_equivalent_p (e1->rhs, e2->rhs)) + return false; + return true; + } +}; + +/* Caches the results of subsumes_non_null(t1, t1). */ + +static GTY ((deletable)) hash_table *subsumption_cache; + +/* Search for a previously cached subsumption result. */ + +static bool* +lookup_subsumption (tree t1, tree t2) +{ + if (!subsumption_cache) + return NULL; + subsumption_entry elt = { t1, t2, false }; + subsumption_entry* found = subsumption_cache->find (&elt); + if (found) + return &found->result; + else + return 0; +} + +/* Save a subsumption result. */ + +static bool +save_subsumption (tree t1, tree t2, bool result) +{ + if (!subsumption_cache) + subsumption_cache = hash_table::create_ggc(31); + subsumption_entry elt = {t1, t2, result}; + subsumption_entry** slot = subsumption_cache->find_slot (&elt, INSERT); + subsumption_entry* entry = ggc_alloc (); + *entry = elt; + *slot = entry; + return result; +} + + /* Returns true if the LEFT constraint subsume the RIGHT constraints. This is done by deriving a proof of the conclusions on the RIGHT from the assumptions on the LEFT assumptions. */ @@ -789,6 +856,9 @@ subsumes_constraints_nonnull (tree lhs, tree rhs) { auto_timevar time (TV_CONSTRAINT_SUB); + if (bool *b = lookup_subsumption(lhs, rhs)) + return *b; + int n1 = dnf_size (lhs); int n2 = cnf_size (rhs); @@ -803,19 +873,20 @@ subsumes_constraints_nonnull (tree lhs, tree rhs) } /* Decompose the smaller of the two formulas, and recursively - check the implication using the larger. Note that for - constraints that are largely comprised of conjunctions the - it will usually be the case that n1 <= n2. */ + check for implication of the larger. */ + bool result; if (n1 <= n2) { formula dnf = decompose_antecedents (lhs); - return derive_proofs (dnf, rhs, left); + result = derive_proofs (dnf, rhs, left); } else { formula cnf = decompose_consequents (rhs); - return derive_proofs (cnf, lhs, right); + result = derive_proofs (cnf, lhs, right); } + + return save_subsumption (lhs, rhs, result); } /* Returns true if the LEFT constraints subsume the RIGHT @@ -832,3 +903,5 @@ subsumes (tree lhs, tree rhs) return true; return subsumes_constraints_nonnull (lhs, rhs); } + +#include "gt-cp-logic.h" diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c index e154cac7b21..095bc32c542 100644 --- a/gcc/cp/pt.c +++ b/gcc/cp/pt.c @@ -28483,163 +28483,6 @@ convert_generic_types_to_packs (tree parm, int start_idx, int end_idx) return tsubst (parm, replacement, tf_none, NULL_TREE); } -/* A mapping from declarations to constraint information. Note that - both templates and their underlying declarations are mapped to the - same constraint information. - - FIXME: This is defined in pt.c because garbage collection - code is not being generated for constraint.cc. */ - -static GTY ((cache)) tree_cache_map *decl_constraints; - -/* Returns the template constraints of declaration T. If T is not - constrained, return NULL_TREE. Note that T must be non-null. */ - -tree -get_constraints (tree t) -{ - if (!flag_concepts) - return NULL_TREE; - if (!decl_constraints) - return NULL_TREE; - - gcc_assert (DECL_P (t)); - if (TREE_CODE (t) == TEMPLATE_DECL) - t = DECL_TEMPLATE_RESULT (t); - tree* found = decl_constraints->get (t); - if (found) - return *found; - else - return NULL_TREE; -} - -/* Associate the given constraint information CI with the declaration - T. If T is a template, then the constraints are associated with - its underlying declaration. Don't build associations if CI is - NULL_TREE. */ - -void -set_constraints (tree t, tree ci) -{ - if (!ci) - return; - gcc_assert (t && flag_concepts); - if (TREE_CODE (t) == TEMPLATE_DECL) - t = DECL_TEMPLATE_RESULT (t); - bool found = hash_map_safe_put (decl_constraints, t, ci); - gcc_assert (!found); -} - -/* Remove the associated constraints of the declaration T. */ - -void -remove_constraints (tree t) -{ - gcc_assert (DECL_P (t)); - if (TREE_CODE (t) == TEMPLATE_DECL) - t = DECL_TEMPLATE_RESULT (t); - - if (decl_constraints) - decl_constraints->remove (t); -} - -static hashval_t -hash_subsumption_args (tree t1, tree t2) -{ - gcc_assert (TREE_CODE (t1) == CHECK_CONSTR); - gcc_assert (TREE_CODE (t2) == CHECK_CONSTR); - int val = 0; - val = iterative_hash_object (CHECK_CONSTR_CONCEPT (t1), val); - val = iterative_hash_template_arg (CHECK_CONSTR_ARGS (t1), val); - val = iterative_hash_object (CHECK_CONSTR_CONCEPT (t2), val); - val = iterative_hash_template_arg (CHECK_CONSTR_ARGS (t2), val); - return val; -} - -/* Compare the constraints of two subsumption entries. The LEFT1 and - LEFT2 arguments comprise the first subsumption pair and the RIGHT1 - and RIGHT2 arguments comprise the second. These are all CHECK_CONSTRs. */ - -static bool -comp_subsumption_args (tree left1, tree left2, tree right1, tree right2) -{ - if (CHECK_CONSTR_CONCEPT (left1) == CHECK_CONSTR_CONCEPT (right1)) - if (CHECK_CONSTR_CONCEPT (left2) == CHECK_CONSTR_CONCEPT (right2)) - if (comp_template_args (CHECK_CONSTR_ARGS (left1), - CHECK_CONSTR_ARGS (right1))) - return comp_template_args (CHECK_CONSTR_ARGS (left2), - CHECK_CONSTR_ARGS (right2)); - return false; -} - -/* Key/value pair for learning and memoizing subsumption results. This - associates a pair of check constraints (including arguments) with - a boolean value indicating the result. */ - -struct GTY((for_user)) subsumption_entry -{ - tree t1; - tree t2; - bool result; -}; - -/* Hashing function and equality for constraint entries. */ - -struct subsumption_hasher : ggc_ptr_hash -{ - static hashval_t hash (subsumption_entry *e) - { - return hash_subsumption_args (e->t1, e->t2); - } - - static bool equal (subsumption_entry *e1, subsumption_entry *e2) - { - ++comparing_specializations; - bool eq = comp_subsumption_args(e1->t1, e1->t2, e2->t1, e2->t2); - --comparing_specializations; - return eq; - } -}; - -static GTY (()) hash_table *subsumption_table; - -/* Search for a previously cached subsumption result. */ - -bool* -lookup_subsumption_result (tree t1, tree t2) -{ - subsumption_entry elt = { t1, t2, false }; - subsumption_entry* found = subsumption_table->find (&elt); - if (found) - return &found->result; - else - return 0; -} - -/* Save a subsumption result. */ - -bool -save_subsumption_result (tree t1, tree t2, bool result) -{ - subsumption_entry elt = {t1, t2, result}; - subsumption_entry** slot = subsumption_table->find_slot (&elt, INSERT); - subsumption_entry* entry = ggc_alloc (); - *entry = elt; - *slot = entry; - return result; -} - -/* Set up the hash table for constraint association. */ - -void -init_constraint_processing (void) -{ - if (!flag_concepts) - return; - - subsumption_table = hash_table::create_ggc(37); -} - GTY(()) tree current_failed_constraint; /* __integer_pack(N) in a pack expansion expands to a sequence of numbers from -- 2.30.2