Bug 67579 - [concepts] Memoization for constraint expressions
Summary: [concepts] Memoization for constraint expressions
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: c++ (show other bugs)
Version: 6.0
: P3 enhancement
Target Milestone: 6.2
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks: concepts
  Show dependency treegraph
 
Reported: 2015-09-14 19:31 UTC by Casey Carter
Modified: 2016-07-21 14:28 UTC (History)
4 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Casey Carter 2015-09-14 19:31:11 UTC
While implementing the Ranges TS I've found that the implementation of concepts in GCC scales very poorly to larger and more complex systems. I've been able to achieve 1-2 order of magnitude improvements in compile time and memory usage by hand coding memoization for some concepts with constexpr variable templates. E.g., replacing

  template </* parameters */>
  concept bool Foo = // requirements

with

  template </* parameters */>
  constexpr bool Foo_ = false;
  template </* parameters */>
    requires // requirements
  constexpr bool Foo_</* parameter names */> = true;

  template </* parameters */>
  concept bool Foo = Foo_</* parameter names */>;

which is fine when Foo need not participate in subsumption relationships. If Foo *does* need to participate in subsumption relationships then performing this transformation by hand is not possible since it hides the relationship between Foo and "requirements" from the compiler's view.

If concepts & constraint expressions are to be generally applicable the implementation must provide some means of reducing the cost of repeated evaluation.
Comment 1 Jason Merrill 2016-07-21 06:05:58 UTC
Author: jason
Date: Thu Jul 21 06:05:24 2016
New Revision: 238558

URL: https://gcc.gnu.org/viewcvs?rev=238558&root=gcc&view=rev
Log:
	Improving concepts performance and diagnostics.

	PR c++/67565
	PR c++/67579
	PR c++/71843
gcc/
	* timevar.def (TV_CONSTRAINT_SAT, TV_CONSTRAINT_SUB): New time vars
	for constraint satisfaction and subsumption.
	* timevar.h (auto_timevar): New constructor that matches the push/pop
	pattern of usage in pt.c.
gcc/cp/
	* cp-tree.def (CHECK_CONSTR): New.
	* cp-tree.h (CHECK_CONSTR_CONCEPT): New.
	(CHECK_CONSTR_ARGS): New.
	* constraint.cc (make_predicate_constraint): Remove in favor of
	normalize_expression.
	(resolve_constraint_check): Actually return error_mark_node when
	resolution fails.
	(resolve_variable_concept_check): Perform coercion as if processing
	a template. Also return errors on resolution failure.
	(lift_*): Remove all of these functions. Don't unnecessarily inline
	concepts.
	(learn_*): Add facilities to memoize implications for subsumption
	during normalization.
	(expanding_concept): New.
	(expand_concept): New. Return the inlined and normalized definition
	of a concept when needed.
	(transform_*, xform_*): Rename to normalize_* to better reflect the
	responsibility of those functions.
	(normalize_template_id_expression): Check for non-boolean operands
	when possible. Generate check constraints instead of normal variable
	references.
	(normalize_call_expression): Report errors when resolution fails.
	(check_for_logical_overloads): Rewrite this check to more accurately
	report the error.
	(normalize_atom): Check for overloaded calls and invalid types before
	determining if the expression refers to a concept.
	(build_constraints): Don't cache normalized constraints or decmposed
	assumptions.
	(finish_shorthand_constraint): Return a normalized expression instead
	of a predicate constraint.
	(finish_template_introduction): Same.
	(placeholder_extract_concept_and_args): Rewrite this since we only
	ever get check constraints here.
	(equivalent_placeholder_constraints): Rewrite in terms of check
	constraints, and handle error_mark_nodes correctly.
	(tsubst_check_constraint, tsubst_expr_constr, tsubst_type_constr)
	(tsubst_implicit_conversion_constr)
	(tsubst_argument_deduction_constr, tsubst_exception_constr)
	(tsubst_parameterized_constraint, tsubst_constraint): New.
	(tsbust_conjunection): Replace with tsubst_logical_operator and
	actually generate the right kind of constraint.
	(tsubst_requirement_body): Reverse the order of substituted arguments
	so that they appear in the order written (helps diagnostics).
	(satisfy_check_constraint): New.
	(satisfy_conjunction): Simplify.
	(satisfy_disjunction): Same.
	(satisfy_constraint_1): Handle check constraints.
	(eval_constr): New (private) global state.
	(evaluating_constraints_sentinel): New. Manages eval_constr.
	(satisfy_constraint): Add timing variables.
	(satisfy_associated_constraints): Add hooks for memoization.
	(evaluate_function_concept): Build a check constraint instead of
	normalizing its definition.
	(evaluate_variable_concept): Same.
	(evaluate_constraint_expression): Normalize, but in the current
	declaration processing context.
	(evaluating_constraints_p): New.
	(elide_constraint_failure_p): Actually emit constraint_thresh errors.
	(diagnose_*): Remove artificial indentation. Add a new parameter to
	each that tracks the current (complete) constraint prior to any
	substitutions.
	(diagnose_expression): Removed.
	(diagnose_call_expression): Same.
	(diagnose_template_id): Same.
	(diagnose_template_id): New.
	(diagnose_logical_constraint): New.
	(diagnose_expression_constraint): Show the original expression.
	(diagnose_type_constraint): Show the original type.
	(diagnose_implicit_conversion_constraint): Be specific about
	failures, don't re-diagnose a known-to-be-failed substitutions,
	and manage elisions properly.
	(diagnose_argument_deduction_constraint): Same.
	(diagnose_exception_constraint): Same.
	(diagnose_parameterized_constraint): Same.
	(constraint_p): Allow EXPR_PACK_EXPANSION.
	* logic.cc (next_by_distance): Removed. No longer used.
	(any_p): Renamed from any_of.
	(term_entry, term_hasher): New.
	(term_list): Rewrite to include a hash table for quick lookup.
	Also, make less stateful.
	(proof_state): Extend to allow goals to be discharged once
	satisfied.
	(non_atomic_constraint_p): New.
	(any_non_atomic_constraints_p): New.
	(...rest...): Previous implementation completely replaced with an
	iterative algorithm that opportunistically prunes the search space
	before committing to using more memory.
	* parser.c: (cp_parser_type_parameter): Normalize constraints.
	(cp_parser_explicit_template_declaration): Same.
	* pt.c: (finish_template_variable): Be less redundant with this error
	message.
	(template_args_equal): No longer static.
	(tsubst_decl): Don't try to find specializations of variables that
	have already been instantiated.
	(build_non_dependent_expr): Avoid infinite recursion during concept
	expansion.
	(make_constrained_auto): Normalize constraints.
	(do_auto_deduction): When doing auto deduction from a
	partial-concept-id, be sure to include the explicit args checking
	the constraints.
	(constraint_sat_*): New. Memoize satisfied constraints.
	(concept_spec_*): New. Memoize expressions associated with a concept
	specialization.
	(constraint_memos, concept_memos): New.
	(lookup_constraint_satisfaction, memoize_constraint_satisfaction): New.
	(lookup_concept_satisfaction, memoize_concept_satisfaction): New.
	(get_concept_expansion, save_concept_expansion): New.
	(hash_subsumption_args): New.
	(comp_subsumption_args): New.
	(subsumption_*): New. Memoize parts of the subsumption relation.
	(lookup_subsumption_result, save_subsumption_result): New.
	(init_constraint_processing): Initialize memo tables.
	(get_constraints): Shortcut if !flag_concepts.
	* decl.c (grokfndecl): Normalize constraints.
	* error.c (dump_simple_decl): Print "concept" when appropriate.
	(dump_function_decl): Same.
	(dump_template_decl): Don't write requirements when we're not
	printing the header.
	(dump_expr): Handle fold expressions.
	* cxx-pretty-print.c (cxx_pretty_printer::expression): Handle
	fold expressions.
	(get_fold_operator): New.
	(pp_cxx_unary_left_fold_expression): New.
	(pp_cxx_unary_right_fold_expression): New.
	(pp_cxx_binary_fold_expression): New.
	(pp_cxx_check_constraint): New.
	(pp_cxx_*_constraint): Rewrite the grammar of internal constraints
	to make them easier to read when debugging.
	* search.c (accessible_p): Don't shortcut when evaluating constraints.
	* tree.c (cp_tree_equal): Handle CHECK_CONSTR.

Added:
    trunk/gcc/testsuite/g++.dg/concepts/req19.C
    trunk/gcc/testsuite/g++.dg/concepts/req20.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cp/ChangeLog
    trunk/gcc/cp/constraint.cc
    trunk/gcc/cp/cp-tree.def
    trunk/gcc/cp/cp-tree.h
    trunk/gcc/cp/cxx-pretty-print.c
    trunk/gcc/cp/decl.c
    trunk/gcc/cp/error.c
    trunk/gcc/cp/logic.cc
    trunk/gcc/cp/parser.c
    trunk/gcc/cp/pt.c
    trunk/gcc/cp/ptree.c
    trunk/gcc/cp/search.c
    trunk/gcc/cp/tree.c
    trunk/gcc/testsuite/g++.dg/concepts/diagnostic1.C
    trunk/gcc/testsuite/g++.dg/concepts/dr1430.C
    trunk/gcc/testsuite/g++.dg/concepts/expression2.C
    trunk/gcc/testsuite/g++.dg/concepts/req4.C
    trunk/gcc/testsuite/g++.dg/concepts/req5.C
    trunk/gcc/testsuite/g++.dg/concepts/req6.C
    trunk/gcc/testsuite/g++.dg/concepts/var-templ1.C
    trunk/gcc/testsuite/g++.dg/concepts/variadic2.C
    trunk/gcc/timevar.def
    trunk/gcc/timevar.h
Comment 2 Jason Merrill 2016-07-21 06:18:40 UTC
Author: jason
Date: Thu Jul 21 06:18:06 2016
New Revision: 238577

URL: https://gcc.gnu.org/viewcvs?rev=238577&root=gcc&view=rev
Log:
	Improving concepts performance and diagnostics.

	PR c++/67565
	PR c++/67579
	PR c++/71843
gcc/
	* timevar.def (TV_CONSTRAINT_SAT, TV_CONSTRAINT_SUB): New time vars
	for constraint satisfaction and subsumption.
	* timevar.h (auto_timevar): New constructor that matches the push/pop
	pattern of usage in pt.c.
gcc/cp/
	* cp-tree.def (CHECK_CONSTR): New.
	* cp-tree.h (CHECK_CONSTR_CONCEPT): New.
	(CHECK_CONSTR_ARGS): New.
	* constraint.cc (make_predicate_constraint): Remove in favor of
	normalize_expression.
	(resolve_constraint_check): Actually return error_mark_node when
	resolution fails.
	(resolve_variable_concept_check): Perform coercion as if processing
	a template. Also return errors on resolution failure.
	(lift_*): Remove all of these functions. Don't unnecessarily inline
	concepts.
	(learn_*): Add facilities to memoize implications for subsumption
	during normalization.
	(expanding_concept): New.
	(expand_concept): New. Return the inlined and normalized definition
	of a concept when needed.
	(transform_*, xform_*): Rename to normalize_* to better reflect the
	responsibility of those functions.
	(normalize_template_id_expression): Check for non-boolean operands
	when possible. Generate check constraints instead of normal variable
	references.
	(normalize_call_expression): Report errors when resolution fails.
	(check_for_logical_overloads): Rewrite this check to more accurately
	report the error.
	(normalize_atom): Check for overloaded calls and invalid types before
	determining if the expression refers to a concept.
	(build_constraints): Don't cache normalized constraints or decmposed
	assumptions.
	(finish_shorthand_constraint): Return a normalized expression instead
	of a predicate constraint.
	(finish_template_introduction): Same.
	(placeholder_extract_concept_and_args): Rewrite this since we only
	ever get check constraints here.
	(equivalent_placeholder_constraints): Rewrite in terms of check
	constraints, and handle error_mark_nodes correctly.
	(tsubst_check_constraint, tsubst_expr_constr, tsubst_type_constr)
	(tsubst_implicit_conversion_constr)
	(tsubst_argument_deduction_constr, tsubst_exception_constr)
	(tsubst_parameterized_constraint, tsubst_constraint): New.
	(tsbust_conjunection): Replace with tsubst_logical_operator and
	actually generate the right kind of constraint.
	(tsubst_requirement_body): Reverse the order of substituted arguments
	so that they appear in the order written (helps diagnostics).
	(satisfy_check_constraint): New.
	(satisfy_conjunction): Simplify.
	(satisfy_disjunction): Same.
	(satisfy_constraint_1): Handle check constraints.
	(eval_constr): New (private) global state.
	(evaluating_constraints_sentinel): New. Manages eval_constr.
	(satisfy_constraint): Add timing variables.
	(satisfy_associated_constraints): Add hooks for memoization.
	(evaluate_function_concept): Build a check constraint instead of
	normalizing its definition.
	(evaluate_variable_concept): Same.
	(evaluate_constraint_expression): Normalize, but in the current
	declaration processing context.
	(evaluating_constraints_p): New.
	(elide_constraint_failure_p): Actually emit constraint_thresh errors.
	(diagnose_*): Remove artificial indentation. Add a new parameter to
	each that tracks the current (complete) constraint prior to any
	substitutions.
	(diagnose_expression): Removed.
	(diagnose_call_expression): Same.
	(diagnose_template_id): Same.
	(diagnose_template_id): New.
	(diagnose_logical_constraint): New.
	(diagnose_expression_constraint): Show the original expression.
	(diagnose_type_constraint): Show the original type.
	(diagnose_implicit_conversion_constraint): Be specific about
	failures, don't re-diagnose a known-to-be-failed substitutions,
	and manage elisions properly.
	(diagnose_argument_deduction_constraint): Same.
	(diagnose_exception_constraint): Same.
	(diagnose_parameterized_constraint): Same.
	(constraint_p): Allow EXPR_PACK_EXPANSION.
	* logic.cc (next_by_distance): Removed. No longer used.
	(any_p): Renamed from any_of.
	(term_entry, term_hasher): New.
	(term_list): Rewrite to include a hash table for quick lookup.
	Also, make less stateful.
	(proof_state): Extend to allow goals to be discharged once
	satisfied.
	(non_atomic_constraint_p): New.
	(any_non_atomic_constraints_p): New.
	(...rest...): Previous implementation completely replaced with an
	iterative algorithm that opportunistically prunes the search space
	before committing to using more memory.
	* parser.c: (cp_parser_type_parameter): Normalize constraints.
	(cp_parser_explicit_template_declaration): Same.
	* pt.c: (finish_template_variable): Be less redundant with this error
	message.
	(template_args_equal): No longer static.
	(tsubst_decl): Don't try to find specializations of variables that
	have already been instantiated.
	(build_non_dependent_expr): Avoid infinite recursion during concept
	expansion.
	(make_constrained_auto): Normalize constraints.
	(do_auto_deduction): When doing auto deduction from a
	partial-concept-id, be sure to include the explicit args checking
	the constraints.
	(constraint_sat_*): New. Memoize satisfied constraints.
	(concept_spec_*): New. Memoize expressions associated with a concept
	specialization.
	(constraint_memos, concept_memos): New.
	(lookup_constraint_satisfaction, memoize_constraint_satisfaction): New.
	(lookup_concept_satisfaction, memoize_concept_satisfaction): New.
	(get_concept_expansion, save_concept_expansion): New.
	(hash_subsumption_args): New.
	(comp_subsumption_args): New.
	(subsumption_*): New. Memoize parts of the subsumption relation.
	(lookup_subsumption_result, save_subsumption_result): New.
	(init_constraint_processing): Initialize memo tables.
	(get_constraints): Shortcut if !flag_concepts.
	* decl.c (grokfndecl): Normalize constraints.
	* error.c (dump_simple_decl): Print "concept" when appropriate.
	(dump_function_decl): Same.
	(dump_template_decl): Don't write requirements when we're not
	printing the header.
	(dump_expr): Handle fold expressions.
	* cxx-pretty-print.c (cxx_pretty_printer::expression): Handle
	fold expressions.
	(get_fold_operator): New.
	(pp_cxx_unary_left_fold_expression): New.
	(pp_cxx_unary_right_fold_expression): New.
	(pp_cxx_binary_fold_expression): New.
	(pp_cxx_check_constraint): New.
	(pp_cxx_*_constraint): Rewrite the grammar of internal constraints
	to make them easier to read when debugging.
	* search.c (accessible_p): Don't shortcut when evaluating constraints.
	* tree.c (cp_tree_equal): Handle CHECK_CONSTR.

Added:
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/req19.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/req20.C
Modified:
    branches/gcc-6-branch/gcc/ChangeLog
    branches/gcc-6-branch/gcc/cp/ChangeLog
    branches/gcc-6-branch/gcc/cp/constraint.cc
    branches/gcc-6-branch/gcc/cp/cp-tree.def
    branches/gcc-6-branch/gcc/cp/cp-tree.h
    branches/gcc-6-branch/gcc/cp/cxx-pretty-print.c
    branches/gcc-6-branch/gcc/cp/decl.c
    branches/gcc-6-branch/gcc/cp/error.c
    branches/gcc-6-branch/gcc/cp/logic.cc
    branches/gcc-6-branch/gcc/cp/parser.c
    branches/gcc-6-branch/gcc/cp/pt.c
    branches/gcc-6-branch/gcc/cp/ptree.c
    branches/gcc-6-branch/gcc/cp/search.c
    branches/gcc-6-branch/gcc/cp/tree.c
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/diagnostic1.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/dr1430.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/expression2.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/req4.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/req5.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/req6.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/var-templ1.C
    branches/gcc-6-branch/gcc/testsuite/g++.dg/concepts/variadic2.C
    branches/gcc-6-branch/gcc/timevar.def
    branches/gcc-6-branch/gcc/timevar.h
Comment 3 Jason Merrill 2016-07-21 14:28:12 UTC
Fixed for 6.2.