Improving concepts performance and diagnostics.

23 files changed, 2298 insertions, 854 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 06179d1f748..f6d034fa897 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2016-03-24  Andrew Sutton  <andrew.n.sutton@gmail.com>
+
+	Improving concepts performance and diagnostics.
+	* 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.
+
 2016-06-21  Martin Liska  <mliska@suse.cz>
 
 	* predict.c (force_edge_cold): Replace imposisble with
diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 20e34d677ee..681f10afada 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,144 @@
+2016-03-24  Andrew Sutton  <andrew.n.sutton@gmail.com>
+
+	Improving concepts performance and diagnostics.
+	* cp-tree.def (CHECK_CONSTR): New.
+	* cp-tree.h (CHECK_CONSTR_CONCEPT): New.
+	(CHECK_CONSTR_ARGS): New.
+	(tsubst_template_args): Make extern.
+	(evaluating_constraints_p): New.
+	(lookup_constraint_satisfaction): New.
+	(memoize_constraint_satisfaction): New.
+	(lookup_concept_satisfaction): New.
+	(get_concept_expansion): New.
+	(save_concept_expansion): New.
+	(lookup_subsumption_result): New.
+	(save_subsumption_result): New.
+	* constraint.cc (make_predicate_constraint): Remove in favor of
+	normalize_expression.
+	(resolve_constraint_check): Actually return an error node when
+	resolution fails, allowing us to more accurately diagnose errors.
+	(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): New.
+	(tsbust_conjunection): Replace with tsbust_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.
+	* 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.
+	(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.
+	(iterative_hash_concept_arg): New. Handle argument pack selects
+	distinctly from what iterative_hash_template_arg does.
+	(hash_concept_and_args): New.
+	(concept_args_equal): Make equivalence agree with hashing.
+	(comp_concept_args): Same.
+	(concept_spec_*): New. Memoize expressions associated with a concept
+	specialization.
+	(constraint_memos, concept_memos): New.
+	(lookup_constraint_satisfaction, memoize_constraint_satisfaction): New,
+	but currently disabled for testing.
+	(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 subsmumption relation.
+	(lookup_subsumption_result, save_subsumption_result): New.
+	(init_constraint_processing): Initialize memo tables.
+	* 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.
+
 2016-06-21  Jason Merrill  <jason@redhat.com>
 
 	* constraint.cc (constraints_satisfied_p): Keep as many levels of
diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
index af7a593a4f6..6db74410cde 100644
--- a/gcc/cp/constraint.cc
+++ b/gcc/cp/constraint.cc
@@ -22,6 +22,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
+#include "timevar.h"
 #include "hash-set.h"
 #include "machmode.h"
 #include "vec.h"
@@ -55,7 +56,9 @@ along with GCC; see the file COPYING3.  If not see
 static inline bool
 constraint_p (tree_code c)
 {
-  return (PRED_CONSTR <= c && c <= DISJ_CONSTR) || c == ERROR_MARK;
+  return ((PRED_CONSTR <= c && c <= DISJ_CONSTR)
+          || c == EXPR_PACK_EXPANSION
+          || c == ERROR_MARK);
 }
 
 /* Returns true if T is a constraint. Note that error_mark_node
@@ -67,14 +70,6 @@ constraint_p (tree t)
   return constraint_p (TREE_CODE (t));
 }
 
-/* Make a predicate constraint from the given expression. */
-
-tree
-make_predicate_constraint (tree expr)
-{
-  return build_nt (PRED_CONSTR, expr);
-}
-
 /* Returns the conjunction of two constraints A and B. Note that
    conjoining a non-null constraint with NULL_TREE is an identity
    operation. That is, for non-null A,
@@ -132,6 +127,53 @@ function_concept_check_p (tree t)
   return false;
 }
 
+/* Returns true if any of the arguments in the template
+   argument list is a wildcard or wildcard pack.  */
+
+bool
+contains_wildcard_p (tree args)
+{
+  for (int i = 0; i < TREE_VEC_LENGTH (args); ++i)
+    {
+      tree arg = TREE_VEC_ELT (args, i);
+      if (TREE_CODE (arg) == WILDCARD_DECL)
+	return true;
+    }
+  return false;
+}
+
+/* Build a new call expression, but don't actually generate a
+   new function call. We just want the tree, not the semantics.  */
+
+inline tree
+build_call_check (tree id)
+{
+  ++processing_template_decl;
+  vec<tree, va_gc> *fargs = make_tree_vector();
+  tree call = finish_call_expr (id, &fargs, false, false, tf_none);
+  release_tree_vector (fargs);
+  --processing_template_decl;
+  return call;
+}
+
+/* Build an expression that will check a variable concept. If any
+   argument contains a wildcard, don't try to finish the variable
+   template because we can't substitute into a non-existent
+   declaration.  */
+
+tree
+build_variable_check (tree id)
+{
+  gcc_assert (TREE_CODE (id) == TEMPLATE_ID_EXPR);
+  if (contains_wildcard_p (TREE_OPERAND (id, 1)))
+    return id;
+
+  ++processing_template_decl;
+  tree var = finish_template_variable (id);
+  --processing_template_decl;
+  return var;
+}
+
 /*---------------------------------------------------------------------------
                     Resolution of qualified concept names
 ---------------------------------------------------------------------------*/
@@ -160,6 +202,7 @@ function_concept_check_p (tree t)
 static tree
 resolve_constraint_check (tree ovl, tree args)
 {
+  int nerrs = 0;
   tree cands = NULL_TREE;
   for (tree p = ovl; p != NULL_TREE; p = OVL_NEXT (p))
     {
@@ -185,15 +228,21 @@ resolve_constraint_check (tree ovl, tree args)
       ++processing_template_decl;
       tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl));
       if (tree subst = coerce_template_parms (parms, args, tmpl))
-        if (subst != error_mark_node)
+        {
+          if (subst == error_mark_node)
+            ++nerrs;
+          else
           cands = tree_cons (subst, fn, cands);
+        }
       --processing_template_decl;
     }
 
-  // If we didn't find a unique candidate, then this is
-  // not a constraint check.
-  if (!cands || TREE_CHAIN (cands))
-    return NULL_TREE;
+  if (!cands)
+    /* We either had no candidates or failed deductions.  */
+    return nerrs ? error_mark_node : NULL_TREE;
+  else if (TREE_CHAIN (cands))
+    /* There are multiple candidates.  */
+    return error_mark_node;
 
   return cands;
 }
@@ -250,14 +299,16 @@ resolve_variable_concept_check (tree id)
      assuming that it works.  Note that failing to deduce
      will result in diagnostics.  */
   tree parms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (tmpl));
+  ++processing_template_decl;
   tree result = coerce_template_parms (parms, args, tmpl);
+  --processing_template_decl;
   if (result != error_mark_node)
     {
       tree decl = DECL_TEMPLATE_RESULT (tmpl);
       return build_tree_list (result, decl);
     }
   else
-    return NULL_TREE;
+    return error_mark_node;
 }
 
 
@@ -315,45 +366,118 @@ deduce_concept_introduction (tree expr)
 namespace {
 
 /*---------------------------------------------------------------------------
-                       Lifting of concept definitions
+                       Constraint implication learning
 ---------------------------------------------------------------------------*/
 
-/* Part of constraint normalization.  Whenever we find a reference to
-   a variable concept or a call to a function concept, we lift or
-   inline that concept's definition into the constraint.  This ensures
-   that constraints are always checked in the immediate instantiation
-   context. */
+/* The implication context determines how we memoize concept checks.
+   Given two checks C1 and C2, the direction of implication depends
+   on whether we are learning implications a conjunction or disjunction.
+   For example:
 
-tree lift_expression (tree);
+      template<typename T> concept bool C = ...;
+      template<typenaem T> concept bool D = C<T> && true;
 
-/* If the tree T has operands, then lift any concepts out of them.  */
-tree
-lift_operands (tree t)
+   From this, we can learn that D<T> implies C<T>. We cannot learn,
+   without further testing, that C<T> does not implies D<T>. If, for
+   example, C<T> were defined as true, then these constraints would
+   be logically equivalent.
+
+   In rare cases, we may start with a logical equivalence. For example:
+
+      template<typename T> concept bool C = ...;
+      template<typename T> concept bool D = C<T>;
+
+   Here, we learn that C<T> implies D<T> and vice versa.   */
+
+enum implication_context
 {
-  if (int n = tree_operand_length (t))
+  conjunction_cxt, /* C1 implies C2. */
+  disjunction_cxt, /* C2 implies C1. */
+  equivalence_cxt  /* C1 implies C2, C2 implies C1. */
+};
+
+void learn_implications(tree, tree, implication_context);
+
+void
+learn_implication (tree parent, tree child, implication_context cxt)
+{
+  switch (cxt)
     {
-      t = copy_node (t);
-      for (int i = 0; i < n; ++i)
-        TREE_OPERAND (t, i) = lift_expression (TREE_OPERAND (t, i));
+      case conjunction_cxt:
+        save_subsumption_result (parent, child, true);
+        break;
+      case disjunction_cxt:
+        save_subsumption_result (child, parent, true);
+        break;
+      case equivalence_cxt:
+        save_subsumption_result (parent, child, true);
+        save_subsumption_result (child, parent, true);
+        break;
     }
-  return t;
 }
 
-/* Recursively lift all operands of the function call. Also, check
-   that the call target is not accidentally a variable concept
-   since that's ill-formed.  */
-tree
-lift_function_call (tree t)
+void
+learn_logical_operation (tree parent, tree constr, implication_context cxt)
 {
-  gcc_assert (TREE_CODE (t) == CALL_EXPR);
-  gcc_assert (!VAR_P (CALL_EXPR_FN (t)));
-  return lift_operands (t);
+  learn_implications (parent, TREE_OPERAND (constr, 0), cxt);
+  learn_implications (parent, TREE_OPERAND (constr, 1), cxt);
+}
+
+void
+learn_implications (tree parent, tree constr, implication_context cxt)
+{
+  switch (TREE_CODE (constr))
+    {
+      case CHECK_CONSTR:
+        return learn_implication (parent, constr, cxt);
+
+      case CONJ_CONSTR:
+        if (cxt == disjunction_cxt)
+          return;
+        return learn_logical_operation (parent, constr, cxt);
+
+      case DISJ_CONSTR:
+        if (cxt == conjunction_cxt)
+          return;
+        return learn_logical_operation (parent, constr, cxt);
+
+      default:
+        break;
+    }
 }
 
-/* Inline a function (concept) definition by substituting
-   ARGS into its body. */
+/* Quickly scan the top-level constraints of CONSTR to learn and
+   cache logical relations between concepts.  The search does not
+   include conjunctions of disjunctions or vice versa.  */
+
+void
+learn_implications (tree tmpl, tree args, tree constr)
+{
+  /* Don't memoize relations between non-dependent arguemnts. It's not helpful. */
+  if (!uses_template_parms (args))
+    return;
+
+  /* Buiild a check constraint for the purpose of caching. */
+  tree parent = build_nt (CHECK_CONSTR, tmpl, args);
+
+  /* Start learning based on the kind of the top-level contraint. */
+  if (TREE_CODE (constr) == CONJ_CONSTR)
+    return learn_logical_operation (parent, constr, conjunction_cxt);
+  else if (TREE_CODE (constr) == DISJ_CONSTR)
+    return learn_logical_operation (parent, constr, disjunction_cxt);
+  else if (TREE_CODE (constr) == CHECK_CONSTR)
+    /* This is the rare concept alias case. */
+    return learn_implication (parent, constr, equivalence_cxt);
+}
+
+/*---------------------------------------------------------------------------
+                       Expansion of concept definitions
+---------------------------------------------------------------------------*/
+
+/* Returns the expression of a function concept. */
+
 tree
-lift_function_definition (tree fn, tree args)
+get_returned_expression (tree fn)
 {
   /* Extract the body of the function minus the return expression.  */
   tree body = DECL_SAVED_TREE (fn);
@@ -364,202 +488,107 @@ lift_function_definition (tree fn, tree args)
   if (TREE_CODE (body) != RETURN_EXPR)
     return error_mark_node;
 
-  body = TREE_OPERAND (body, 0);
-
-  /* Substitute template arguments to produce our inline expression.  */
-  tree result = tsubst_expr (body, args, tf_none, NULL_TREE, false);
-  if (result == error_mark_node)
-    return error_mark_node;
-
-  return lift_expression (result);
+  return TREE_OPERAND (body, 0);
 }
 
-/* Inline a reference to a function concept.  */
-tree
-lift_call_expression (tree t)
-{
-  /* Try to resolve this function call as a concept.  If not, then
-     it can be returned as-is.  */
-  tree check = resolve_constraint_check (t);
-  if (!check)
-    return lift_function_call (t);
-  if (check == error_mark_node)
-    return error_mark_node;
-
-  tree fn = TREE_VALUE (check);
-  tree args = TREE_PURPOSE (check);
-  return lift_function_definition (fn, args);
-}
+/* Returns the initializer of a variable concept. */
 
 tree
-lift_variable_initializer (tree var, tree args)
+get_variable_initializer (tree var)
 {
-  /* Extract the body from the variable initializer.  */
   tree init = DECL_INITIAL (var);
   if (!init)
     return error_mark_node;
+  return init;
+}
 
-  /* Substitute the arguments to form our new inline expression.  */
-  tree result = tsubst_expr (init, args, tf_none, NULL_TREE, false);
-  if (result == error_mark_node)
-    return error_mark_node;
+/* Returns the definition of a variable or function concept.  */
 
-  return lift_expression (result);
+tree
+get_concept_definition (tree decl)
+{
+  if (TREE_CODE (decl) == VAR_DECL)
+    return get_variable_initializer (decl);
+  else if (TREE_CODE (decl) == FUNCTION_DECL)
+    return get_returned_expression (decl);
+  gcc_unreachable ();
 }
 
-/* Determine if a template-id is a variable concept and inline.  */
+int expansion_level = 0;
 
-tree
-lift_template_id (tree t)
+struct expanding_concept_sentinel
 {
-  if (tree info = resolve_variable_concept_check (t))
-    {
-      tree decl = TREE_VALUE (info);
-      tree args = TREE_PURPOSE (info);
-      return lift_variable_initializer (decl, args);
-    }
+  expanding_concept_sentinel ()
+  {
+    ++expansion_level;
+  }
 
-  /* Check that we didn't refer to a function concept like
-      a variable.
+  ~expanding_concept_sentinel()
+  {
+    --expansion_level;
+  }
+};
 
-     TODO: Add a note on how to fix this.  */
-  tree tmpl = TREE_OPERAND (t, 0);
-  if (TREE_CODE (tmpl) == OVERLOAD)
-    {
-      tree fn = OVL_FUNCTION (tmpl);
-      if (TREE_CODE (fn) == TEMPLATE_DECL
-          && DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (fn)))
-        {
-          error_at (location_of (t),
-		    "invalid reference to function concept %qD", fn);
-          return error_mark_node;
-        }
-    }
 
-  return t;
-}
+} /* namespace */
 
-/* Lift any constraints appearing in a nested requirement of
-   a requires-expression. */
-tree
-lift_requires_expression (tree t)
+/* Returns true when a concept is being expanded.  */
+
+bool
+expanding_concept()
 {
-  tree parms = TREE_OPERAND (t, 0);
-  tree reqs = TREE_OPERAND (t, 1);
-  tree result = NULL_TREE;
-  for (; reqs != NULL_TREE; reqs = TREE_CHAIN (reqs))
-    {
-      tree req = TREE_VALUE (reqs);
-      if (TREE_CODE (req) == NESTED_REQ)
-        {
-          tree expr = lift_expression (TREE_OPERAND (req, 0));
-          req = finish_nested_requirement (expr);
-        }
-      result = tree_cons (NULL_TREE, req, result);
-    }
-  return finish_requires_expr (parms, result);
+  return expansion_level > 0;
 }
 
-/* Inline references to specializations of concepts.  */
+/* Expand a concept declaration (not a template) and its arguments to
+   a constraint defined by the concept's initializer or definition.  */
+
 tree
-lift_expression (tree t)
+expand_concept (tree decl, tree args)
 {
-  if (t == NULL_TREE)
-    return NULL_TREE;
+  expanding_concept_sentinel sentinel;
 
-  if (t == error_mark_node)
-    return error_mark_node;
+  if (TREE_CODE (decl) == TEMPLATE_DECL)
+      decl = DECL_TEMPLATE_RESULT (decl);
+  tree tmpl = DECL_TI_TEMPLATE (decl);
 
-  /* Concepts can be referred to by call or variable. All other
-     nodes are preserved.  */
-  switch (TREE_CODE (t))
-    {
-    case CALL_EXPR:
-      return lift_call_expression (t);
+  /* Check for a previous specialization. */
+  if (tree spec = get_concept_expansion (tmpl, args))
+    return spec;
 
-    case TEMPLATE_ID_EXPR:
-      return lift_template_id (t);
+  /* Substitute the arguments to form a new definition expression.  */
+  tree def = get_concept_definition (decl);
 
-    case REQUIRES_EXPR:
-      return lift_requires_expression (t);
-
-    case EXPR_PACK_EXPANSION:
-      /* Use copy_node rather than make_pack_expansion so that
-	 PACK_EXPANSION_PARAMETER_PACKS stays the same.  */
-      t = copy_node (t);
-      SET_PACK_EXPANSION_PATTERN
-	(t, lift_expression (PACK_EXPANSION_PATTERN (t)));
-      return t;
-
-    case TREE_LIST:
-      {
-        t = copy_node (t);
-        TREE_VALUE (t) = lift_expression (TREE_VALUE (t));
-        TREE_CHAIN (t) = lift_expression (TREE_CHAIN (t));
-        return t;
-      }
+  ++processing_template_decl;
+  tree result = tsubst_expr (def, args, tf_none, NULL_TREE, true);
+  --processing_template_decl;
+  if (result == error_mark_node)
+    return error_mark_node;
 
-    default:
-      return lift_operands (t);
-    }
+  /* And lastly, normalize it, check for implications, and save
+     the specialization for later.. */
+  tree norm = normalize_expression (result);
+  learn_implications (tmpl, args, norm);
+  return save_concept_expansion (tmpl, args, norm);
 }
 
-/*---------------------------------------------------------------------------
-                Transformation of expressions into constraints
----------------------------------------------------------------------------*/
 
-/* Part of constraint normalization. The following functions rewrite
-   expressions as constraints.  */
-
-tree transform_expression (tree);
-
-/* Check that the logical-or or logical-and expression does
-   not result in a call to a user-defined user-defined operator
-   (temp.constr.op). Returns true if the logical operator is
-   admissible and false otherwise. */
-
-bool
-check_logical_expr (tree t)
-{
-  /* We can't do much for type dependent expressions. */
-  if (type_dependent_expression_p (t))
-    return true;
+/*---------------------------------------------------------------------------
+                Stepwise normalization of expressions
 
-  /* Resolve the logical operator. Note that template processing is
-     disabled so we get the actual call or target expression back.
-     not_processing_template_sentinel sentinel.
-
-     TODO: This check is actually subsumed by the requirement that
-     constraint operands have type bool. I'm not sure we need it
-     unless we allow conversions.  */
-  tree arg1 = TREE_OPERAND (t, 0);
-  tree arg2 = TREE_OPERAND (t, 1);
-  tree ovl = NULL_TREE;
-  tree expr = build_x_binary_op (EXPR_LOC_OR_LOC (arg2, input_location),
-                                 TREE_CODE (t),
-                                 arg1, TREE_CODE (arg1),
-                                 arg2, TREE_CODE (arg2),
-                                 &ovl,
-                                 tf_none);
-  if (TREE_CODE (expr) != TREE_CODE (t))
-    {
-      error ("user-defined operator %qs in constraint %q+E",
-	     operator_name_info[TREE_CODE (t)].name, t);
-      return false;
-    }
-  return true;
-}
+This set of functions will transform an expression into a constraint
+in a sequecne of steps. Normalization does not not look into concept
+definitions.
+---------------------------------------------------------------------------*/
 
 /* Transform a logical-or or logical-and expression into either
    a conjunction or disjunction. */
 
 tree
-xform_logical (tree t, tree_code c)
+normalize_logical_operation (tree t, tree_code c)
 {
-  if (!check_logical_expr (t))
-    return error_mark_node;
-  tree t0 = transform_expression (TREE_OPERAND (t, 0));
-  tree t1 = transform_expression (TREE_OPERAND (t, 1));
+  tree t0 = normalize_expression (TREE_OPERAND (t, 0));
+  tree t1 = normalize_expression (TREE_OPERAND (t, 1));
   return build_nt (c, t0, t1);
 }
 
@@ -567,7 +596,7 @@ xform_logical (tree t, tree_code c)
    for its expression. */
 
 inline tree
-xform_simple_requirement (tree t)
+normalize_simple_requirement (tree t)
 {
   return build_nt (EXPR_CONSTR, TREE_OPERAND (t, 0));
 }
@@ -575,7 +604,7 @@ xform_simple_requirement (tree t)
 /* A type requirement T introduce a type constraint for its type.  */
 
 inline tree
-xform_type_requirement (tree t)
+normalize_type_requirement (tree t)
 {
   return build_nt (TYPE_CONSTR, TREE_OPERAND (t, 0));
 }
@@ -589,7 +618,7 @@ xform_type_requirement (tree t)
    includes an exception constraint.  */
 
 tree
-xform_compound_requirement (tree t)
+normalize_compound_requirement (tree t)
 {
   tree expr = TREE_OPERAND (t, 0);
   tree constr = build_nt (EXPR_CONSTR, TREE_OPERAND (t, 0));
@@ -627,29 +656,29 @@ xform_compound_requirement (tree t)
    will guarantee that the constraint is never satisfied.  */
 
 inline tree
-xform_nested_requirement (tree t)
+normalize_nested_requirement (tree t)
 {
-  return transform_expression (TREE_OPERAND (t, 0));
+  return normalize_expression (TREE_OPERAND (t, 0));
 }
 
 /* Transform a requirement T into one or more constraints.  */
 
 tree
-xform_requirement (tree t)
+normalize_requirement (tree t)
 {
   switch (TREE_CODE (t))
     {
     case SIMPLE_REQ:
-      return xform_simple_requirement (t);
+      return normalize_simple_requirement (t);
 
     case TYPE_REQ:
-      return xform_type_requirement (t);
+      return normalize_type_requirement (t);
 
     case COMPOUND_REQ:
-      return xform_compound_requirement (t);
+      return normalize_compound_requirement (t);
 
     case NESTED_REQ:
-      return xform_nested_requirement (t);
+      return normalize_nested_requirement (t);
 
     default:
       gcc_unreachable ();
@@ -661,46 +690,168 @@ xform_requirement (tree t)
    constraints. */
 
 tree
-xform_requirements (tree t)
+normalize_requirements (tree t)
 {
   tree result = NULL_TREE;
   for (; t; t = TREE_CHAIN (t))
     {
-      tree constr = xform_requirement (TREE_VALUE (t));
+      tree constr = normalize_requirement (TREE_VALUE (t));
       result = conjoin_constraints (result, constr);
     }
   return result;
 }
 
-/* Transform a requires-expression into a parameterized constraint.  */
+/* The normal form of a requires-expression is a parameterized
+   constraint having the same parameters and a conjunction of
+   constraints representing the normal form of requirements.  */
 
 tree
-xform_requires_expr (tree t)
+normalize_requires_expression (tree t)
 {
-  tree operand = xform_requirements (TREE_OPERAND (t, 1));
+  tree operand = normalize_requirements (TREE_OPERAND (t, 1));
   if (tree parms = TREE_OPERAND (t, 0))
     return build_nt (PARM_CONSTR, parms, operand);
   else
     return operand;
 }
 
-/* Transform an expression into an atomic predicate constraint.
-   After substitution, the expression of a predicate constraint
-   shall have type bool (temp.constr.pred).  For non-type-dependent
-   expressions, we can check that now.  */
+/* For a template-id referring to a variable concept, returns
+   a check constraint. Otherwise, returns a predicate constraint. */
+
+tree
+normalize_template_id_expression (tree t)
+{
+  if (tree info = resolve_variable_concept_check (t))
+    {
+      if (info == error_mark_node)
+        {
+          /* We get this when the template arguments don't match
+             the variable concept. */
+          error ("invalid reference to concept %qE", t);
+          return error_mark_node;
+        }
+
+      tree decl = TREE_VALUE (info);
+      tree args = TREE_PURPOSE (info);
+      return build_nt (CHECK_CONSTR, decl, args);
+    }
+
+  /* Check that we didn't refer to a function concept like a variable.  */
+  tree tmpl = TREE_OPERAND (t, 0);
+  if (TREE_CODE (tmpl) == OVERLOAD)
+    {
+      tree fn = OVL_FUNCTION (tmpl);
+      if (TREE_CODE (fn) == TEMPLATE_DECL
+          && DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (fn)))
+        {
+          error_at (location_of (t),
+                    "invalid reference to function concept %qD", fn);
+          return error_mark_node;
+        }
+    }
+
+  return build_nt (PRED_CONSTR, t);
+}
+
+/* For a call expression to a function concept, returns a check
+   constraint. Otherwise, returns a predicate constraint. */
+
+tree
+normalize_call_expression (tree t)
+{
+  /* Try to resolve this function call as a concept.  If not, then
+     it can be returned as a predicate constraint.  */
+  tree check = resolve_constraint_check (t);
+  if (!check)
+    return build_nt (PRED_CONSTR, t);
+  if (check == error_mark_node)
+    {
+      /* TODO: Improve diagnostics. We could report why the reference
+         is invalid. */
+      error ("invalid reference to concept %qE", t);
+      return error_mark_node;
+    }
+
+  tree fn = TREE_VALUE (check);
+  tree args = TREE_PURPOSE (check);
+  return build_nt (CHECK_CONSTR, fn, args);
+}
+
+/* If T is a call to an overloaded && or || operator, diagnose that
+   as a non-SFINAEable error.  Returns true if an error is emitted.
+
+   TODO: It would be better to diagnose this at the point of definition,
+   if possible. Perhaps we should immediately do a first-pass normalization
+   of a concept definition to catch obvious non-dependent errors like
+   this.  */
+
+bool
+check_for_logical_overloads (tree t)
+{
+  if (TREE_CODE (t) != CALL_EXPR)
+    return false;
+
+  tree fn = CALL_EXPR_FN (t);
+
+  /* For member calls, try extracting the function from the
+     component ref.  */
+  if (TREE_CODE (fn) == COMPONENT_REF)
+    {
+      fn = TREE_OPERAND (fn, 1);
+      if (TREE_CODE (fn) == BASELINK)
+        fn = BASELINK_FUNCTIONS (fn);
+    }
+
+  if (TREE_CODE (fn) != FUNCTION_DECL)
+    return false;
+
+  tree name = DECL_NAME (fn);
+  if ((name == operator_name_info [TRUTH_ANDIF_EXPR].identifier)
+      || (name == operator_name_info [TRUTH_ORIF_EXPR].identifier))
+    {
+      location_t loc =
+        EXPR_HAS_LOCATION (t) ? EXPR_LOCATION (t) : input_location;
+      error_at (loc, "constraint %qE, uses overloaded operator", t);
+      return true;
+    }
+
+  return false;
+}
+
+/* The normal form of an atom depends on the expression. The normal
+   form of a function call to a function concept is a check constraint
+   for that concept. The normal form of a reference to a variable
+   concept is a check constraint for that concept. Otherwise, the
+   constraint is a predicate constraint.  */
 
 tree
-xform_atomic (tree t)
+normalize_atom (tree t)
 {
-  if (TREE_TYPE (t) && !type_dependent_expression_p (t))
+  /* We can get constraints pushed down through pack expansions, so
+     just return them. */
+  if (constraint_p (t))
+    return t;
+
+  tree type = TREE_TYPE (t);
+  if (!type || type_unknown_p (t) || TREE_CODE (type) == TEMPLATE_TYPE_PARM)
+    { }
+  else if (!dependent_type_p (type))
   {
-    tree type = cv_unqualified (TREE_TYPE (t));
+      if (check_for_logical_overloads (t))
+        return error_mark_node;
+
+      type = cv_unqualified (type);
     if (!same_type_p (type, boolean_type_node))
       {
         error ("predicate constraint %q+E does not have type %<bool%>", t);
         return error_mark_node;
       }
   }
+
+  if (TREE_CODE (t) == TEMPLATE_ID_EXPR)
+    return normalize_template_id_expression (t);
+  if (TREE_CODE (t) == CALL_EXPR)
+    return normalize_call_expression (t);
   return build_nt (PRED_CONSTR, t);
 }
 
@@ -735,49 +886,48 @@ push_down_pack_expansion (tree exp, tree pat)
    leaves of the constraint so that partial ordering will work.  */
 
 tree
-xform_pack_expansion (tree t)
+normalize_pack_expansion (tree t)
 {
-  tree pat = transform_expression (PACK_EXPANSION_PATTERN (t));
+  tree pat = normalize_expression (PACK_EXPANSION_PATTERN (t));
   return push_down_pack_expansion (t, pat);
 }
 
 /* Transform an expression into a constraint.  */
 
 tree
-xform_expr (tree t)
+normalize_any_expression (tree t)
 {
   switch (TREE_CODE (t))
     {
     case TRUTH_ANDIF_EXPR:
-      return xform_logical (t, CONJ_CONSTR);
+      return normalize_logical_operation (t, CONJ_CONSTR);
 
     case TRUTH_ORIF_EXPR:
-      return xform_logical (t, DISJ_CONSTR);
+      return normalize_logical_operation (t, DISJ_CONSTR);
 
     case REQUIRES_EXPR:
-      return xform_requires_expr (t);
+      return normalize_requires_expression (t);
 
     case BIND_EXPR:
-      return transform_expression (BIND_EXPR_BODY (t));
+      return normalize_expression (BIND_EXPR_BODY (t));
 
     case EXPR_PACK_EXPANSION:
-      return xform_pack_expansion (t);
+      return normalize_pack_expansion (t);
 
     default:
       /* All other constraints are atomic. */
-      return xform_atomic (t);
+      return normalize_atom (t);
     }
 }
 
 /* Transform a statement into an expression.  */
-
 tree
-xform_stmt (tree t)
+normalize_any_statement (tree t)
 {
   switch (TREE_CODE (t))
     {
     case RETURN_EXPR:
-      return transform_expression (TREE_OPERAND (t, 0));
+      return normalize_expression (TREE_OPERAND (t, 0));
     default:
       gcc_unreachable ();
     }
@@ -787,24 +937,22 @@ xform_stmt (tree t)
 /* Reduction rules for the declaration T.  */
 
 tree
-xform_decl (tree t)
+normalize_any_declaration (tree t)
 {
   switch (TREE_CODE (t))
     {
     case VAR_DECL:
-      return xform_atomic (t);
+      return normalize_atom (t);
     default:
       gcc_unreachable ();
     }
   return error_mark_node;
 }
 
-/* Transform a lifted expression into a constraint. This either
-   returns a constraint, or it returns error_mark_node when
-   a constraint cannot be formed.  */
+/* Returns the normal form of a constraint expression. */
 
 tree
-transform_expression (tree t)
+normalize_expression (tree t)
 {
   if (!t)
     return NULL_TREE;
@@ -818,20 +966,20 @@ transform_expression (tree t)
     case tcc_binary:
     case tcc_expression:
     case tcc_vl_exp:
-      return xform_expr (t);
+      return normalize_any_expression (t);
 
     case tcc_statement:
-      return xform_stmt (t);
+      return normalize_any_statement (t);
 
     case tcc_declaration:
-      return xform_decl (t);
+      return normalize_any_declaration (t);
 
     case tcc_exceptional:
     case tcc_constant:
     case tcc_reference:
     case tcc_comparison:
       /* These are all atomic predicate constraints. */
-      return xform_atomic (t);
+      return normalize_atom (t);
 
     default:
       /* Unhandled node kind. */
@@ -840,6 +988,7 @@ transform_expression (tree t)
   return error_mark_node;
 }
 
+
 /*---------------------------------------------------------------------------
                         Constraint normalization
 ---------------------------------------------------------------------------*/
@@ -879,8 +1028,7 @@ normalize_predicate_constraint (tree t)
 {
   ++processing_template_decl;
   tree expr = PRED_CONSTR_EXPR (t);
-  tree lifted = lift_expression (expr);
-  tree constr = transform_expression (lifted);
+  tree constr = normalize_expression (expr);
   --processing_template_decl;
   return constr;
 }
@@ -938,7 +1086,6 @@ normalize_constraint (tree t)
   return error_mark_node;
 }
 
-} /* namespace */
 
 
 // -------------------------------------------------------------------------- //
@@ -1028,61 +1175,15 @@ build_constraints (tree tmpl_reqs, tree decl_reqs)
   ci->declarator_reqs = decl_reqs;
   ci->associated_constr = conjoin_constraints (tmpl_reqs, decl_reqs);
 
-  ++processing_template_decl;
-  ci->normalized_constr = normalize_constraint (ci->associated_constr);
-  --processing_template_decl;
+  /* FIXME: I'm not using these any more. */
+  ci->normalized_constr = NULL_TREE;
+  ci->assumptions = NULL_TREE;
 
-  ci->assumptions = decompose_assumptions (ci->normalized_constr);
   return (tree)ci;
 }
 
 namespace {
 
-/* Returns true if any of the arguments in the template
-   argument list is a wildcard or wildcard pack. */
-bool
-contains_wildcard_p (tree args)
-{
-  for (int i = 0; i < TREE_VEC_LENGTH (args); ++i)
-    {
-      tree arg = TREE_VEC_ELT (args, i);
-      if (TREE_CODE (arg) == WILDCARD_DECL)
-	return true;
-    }
-  return false;
-}
-
-/* Build a new call expression, but don't actually generate
-   a new function call. We just want the tree, not the
-   semantics. */
-inline tree
-build_call_check (tree id)
-{
-  ++processing_template_decl;
-  vec<tree, va_gc> *fargs = make_tree_vector();
-  tree call = finish_call_expr (id, &fargs, false, false, tf_none);
-  release_tree_vector (fargs);
-  --processing_template_decl;
-  return call;
-}
-
-/* Build an expression that will check a variable concept. If any
-   argument contains a wildcard, don't try to finish the variable
-   template because we can't substitute into a non-existent
-   declaration.  */
-tree
-build_variable_check (tree id)
-{
-  gcc_assert (TREE_CODE (id) == TEMPLATE_ID_EXPR);
-  if (contains_wildcard_p (TREE_OPERAND (id, 1)))
-    return id;
-
-  ++processing_template_decl;
-  tree var = finish_template_variable (id);
-  --processing_template_decl;
-  return var;
-}
-
 /* Construct a sequence of template arguments by prepending
    ARG to REST. Either ARG or REST may be null. */
 tree
@@ -1158,7 +1259,9 @@ build_constrained_parameter (tree cnc, tree proto, tree args)
 
    Note that the constraints are neither reduced nor decomposed.
    That is done only after the requires clause has been parsed
-   (or not). */
+   (or not).
+
+   This will always return a CHECK_CONSTR. */
 tree
 finish_shorthand_constraint (tree decl, tree constr)
 {
@@ -1207,7 +1310,7 @@ finish_shorthand_constraint (tree decl, tree constr)
       TREE_TYPE (check) = boolean_type_node;
     }
 
-  return make_predicate_constraint (check);
+  return normalize_expression (check);
 }
 
 /* Returns a conjunction of shorthand requirements for the template
@@ -1346,7 +1449,7 @@ finish_template_introduction (tree tmpl_decl, tree intro_list)
 
   /* Associate the constraint. */
   tree check = build_concept_check (tmpl_decl, NULL_TREE, check_args);
-  tree constr = make_predicate_constraint (check);
+  tree constr = normalize_expression (check);
   TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = constr;
 
   return parm_list;
@@ -1362,41 +1465,28 @@ placeholder_extract_concept_and_args (tree t, tree &tmpl, tree &args)
 {
   if (TREE_CODE (t) == TYPE_DECL)
     {
-      /* A constrained parameter.  */
-      tmpl = DECL_TI_TEMPLATE (CONSTRAINED_PARM_CONCEPT (t));
-      args = CONSTRAINED_PARM_EXTRA_ARGS (t);
+      /* A constrained parameter.  Build a constraint check
+         based on the prototype parameter and then extract the
+         arguments from that.  */
+      tree proto = CONSTRAINED_PARM_PROTOTYPE (t);
+      tree check = finish_shorthand_constraint (proto, t);
+      placeholder_extract_concept_and_args (check, tmpl, args);
       return;
     }
 
-  gcc_assert (TREE_CODE (t) == PRED_CONSTR);
-  t = PRED_CONSTR_EXPR (t);
-  gcc_assert (TREE_CODE (t) == CALL_EXPR
-              || TREE_CODE (t) == TEMPLATE_ID_EXPR
-              || VAR_P (t));
-
-  if (TREE_CODE (t) == CALL_EXPR)
-    t = CALL_EXPR_FN (t);
-  if (TREE_CODE (t) == TEMPLATE_ID_EXPR)
+  if (TREE_CODE (t) == CHECK_CONSTR)
     {
-      tmpl = TREE_OPERAND (t, 0);
-      if (TREE_CODE (tmpl) == OVERLOAD)
-	{
-	  gcc_assert (OVL_CHAIN (tmpl) == NULL_TREE);
-	  tmpl = OVL_FUNCTION (tmpl);
-	}
-      args = TREE_OPERAND (t, 1);
-    }
-  else if (DECL_P (t))
-    {
-      tmpl = DECL_TI_TEMPLATE (t);
-      args = DECL_TI_ARGS (t);
+      tree decl = CHECK_CONSTR_CONCEPT (t);
+      tmpl = DECL_TI_TEMPLATE (decl);
+      args = CHECK_CONSTR_ARGS (t);
+      return;
     }
-  else
+
     gcc_unreachable ();
 }
 
 /* Returns true iff the placeholders C1 and C2 are equivalent.  C1
-   and C2 can be either PRED_CONSTR_EXPR or TEMPLATE_TYPE_PARM.  */
+   and C2 can be either CHECK_CONSTR or TEMPLATE_TYPE_PARM.  */
 
 bool
 equivalent_placeholder_constraints (tree c1, tree c2)
@@ -1411,6 +1501,11 @@ equivalent_placeholder_constraints (tree c1, tree c2)
     return true;
   if (!c1 || !c2)
     return false;
+  if (c1 == error_mark_node || c2 == error_mark_node)
+    /* We get here during satisfaction; when a deduction constraint
+       fails, substitution can produce an error_mark_node for the
+       placeholder constraints.  */
+    return false;
 
   tree t1, t2, a1, a2;
   placeholder_extract_concept_and_args (c1, t1, a1);
@@ -1419,21 +1514,20 @@ equivalent_placeholder_constraints (tree c1, tree c2)
   if (t1 != t2)
     return false;
 
-  /* Skip the first argument to avoid infinite recursion on the
-     placeholder auto itself.  */
-  bool skip1 = (TREE_CODE (c1) == PRED_CONSTR);
-  bool skip2 = (TREE_CODE (c2) == PRED_CONSTR);
-
-  int len1 = (a1 ? TREE_VEC_LENGTH (a1) : 0) - skip1;
-  int len2 = (a2 ? TREE_VEC_LENGTH (a2) : 0) - skip2;
-
+  int len1 = TREE_VEC_LENGTH (a1);
+  int len2 = TREE_VEC_LENGTH (a2);
   if (len1 != len2)
     return false;
 
-  for (int i = 0; i < len1; ++i)
-    if (!cp_tree_equal (TREE_VEC_ELT (a1, i + skip1),
-			TREE_VEC_ELT (a2, i + skip2)))
+  /* Skip the first argument so we don't infinitely recurse.
+     Also, they may differ in template parameter index.  */
+  for (int i = 1; i < len1; ++i)
+    {
+      tree t1 = TREE_VEC_ELT (a1, i);
+      tree t2 = TREE_VEC_ELT (a2, i);
+      if (!template_args_equal (t1, t2))
       return false;
+    }
   return true;
 }
 
@@ -1492,17 +1586,45 @@ tsubst_predicate_constraint (tree t, tree args,
   return build_nt (PRED_CONSTR, result);
 }
 
+/* Substitute into a check constraint. */
+
+tree
+tsubst_check_constraint (tree t, tree args,
+                         tsubst_flags_t complain, tree in_decl)
+{
+  tree decl = CHECK_CONSTR_CONCEPT (t);
+  tree tmpl = DECL_TI_TEMPLATE (decl);
+  tree targs = CHECK_CONSTR_ARGS (t);
+
+  /* Substitute through by building an template-id expression
+     and then substituting into that. */
+  tree expr = build_nt(TEMPLATE_ID_EXPR, tmpl, targs);
+  ++processing_template_decl;
+  tree result = tsubst_expr (expr, args, complain, in_decl, false);
+  --processing_template_decl;
+
+  if (result == error_mark_node)
+    return error_mark_node;
+
+  /* Extract the results and rebuild the check constraint. */
+  decl = DECL_TEMPLATE_RESULT (TREE_OPERAND (result, 0));
+  args = TREE_OPERAND (result, 1);
+
+  return build_nt (CHECK_CONSTR, decl, args);
+}
+
 /* Substitute into the conjunction of constraints. Returns
    error_mark_node if substitution into either operand fails. */
+
 tree
-tsubst_conjunction (tree t, tree args,
+tsubst_logical_operator (tree t, tree args,
                     tsubst_flags_t complain, tree in_decl)
 {
   tree t0 = TREE_OPERAND (t, 0);
   tree r0 = tsubst_constraint (t0, args, complain, in_decl);
   tree t1 = TREE_OPERAND (t, 1);
   tree r1 = tsubst_constraint (t1, args, complain, in_decl);
-  return build_nt (CONJ_CONSTR, r0, r1);
+  return build_nt (TREE_CODE (t), r0, r1);
 }
 
 /* Substitute ARGS into the constraint T. */
@@ -1511,12 +1633,19 @@ tsubst_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 {
   if (t == NULL_TREE)
     return t;
-  if (TREE_CODE (t) == CONJ_CONSTR)
-    return tsubst_conjunction (t, args, complain, in_decl);
-  else if (TREE_CODE (t) == PRED_CONSTR)
+  switch (TREE_CODE (t))
+  {
+    case PRED_CONSTR:
     return tsubst_predicate_constraint (t, args, complain, in_decl);
-  else
+    case CHECK_CONSTR:
+      return tsubst_check_constraint (t, args, complain, in_decl);
+    case CONJ_CONSTR:
+      return tsubst_logical_operator (t, args, complain, in_decl);
+    case DISJ_CONSTR:
+      return tsubst_logical_operator (t, args, complain, in_decl);
+    default:
     gcc_unreachable ();
+  }
   return error_mark_node;
 }
 
@@ -1662,7 +1791,8 @@ tsubst_requirement_body (tree t, tree args,
       r = tree_cons (NULL_TREE, e, r);
       t = TREE_CHAIN (t);
     }
-  return r;
+  /* Ensure that the order of constraints is the same as the original.  */
+  return nreverse (r);
 }
 
 } /* namespace */
@@ -1738,11 +1868,14 @@ satisfy_pack_expansion (tree t, tree args,
      gen_elem_of_pack_expansion_instantiation will check that each element of
      the expansion is satisfied.  */
   tree exprs = tsubst_pack_expansion (t, args, complain, in_decl);
+
   if (exprs == error_mark_node)
     return boolean_false_node;
-  int n = TREE_VEC_LENGTH (exprs);
 
-  for (int i = 0; i < n; ++i)
+  /* TODO: It might be better to normalize each expanded term
+     and evaluate them separately. That would provide better
+     opportunities for diagnostics.  */
+  for (int i = 0; i < TREE_VEC_LENGTH (exprs); ++i)
     if (TREE_VEC_ELT (exprs, i) != boolean_true_node)
       return boolean_false_node;
   return boolean_true_node;
@@ -1760,12 +1893,22 @@ tree
 satisfy_predicate_constraint (tree t, tree args,
                               tsubst_flags_t complain, tree in_decl)
 {
-  tree original = TREE_OPERAND (t, 0);
+  tree expr = TREE_OPERAND (t, 0);
 
   /* We should never have a naked pack expansion in a predicate constraint.  */
-  gcc_assert (TREE_CODE (original) != EXPR_PACK_EXPANSION);
-
-  tree expr = tsubst_expr (original, args, complain, in_decl, false);
+  gcc_assert (TREE_CODE (expr) != EXPR_PACK_EXPANSION);
+
+  /* If substitution into the expression fails, the constraint
+     is not satisfied.
+
+     FIXME: There is a (likely) bug related to this substitution.  When a
+     concept check expands to refer to a variable template, this expression
+      may include references to instantiations of those templates.  However,
+      the substitution below fails to preserve those instantiations, and
+      instead creates new uninstantiated specializations, causing the
+      constraint to fail with spurious constexpr errors.  This is explicitly
+      guarded against in tsbust_decl and satisfy_constraint.  */
+  expr = tsubst_expr (expr, args, complain, in_decl, false);
   if (expr == error_mark_node)
     return boolean_false_node;
 
@@ -1781,8 +1924,34 @@ satisfy_predicate_constraint (tree t, tree args,
       return boolean_false_node;
     }
 
-  tree value = cxx_constant_value (expr);
-  return value;
+  return cxx_constant_value (expr);
+}
+
+tree
+satisfy_check_constraint (tree t, tree args,
+                          tsubst_flags_t complain, tree in_decl)
+{
+  tree decl = CHECK_CONSTR_CONCEPT (t);
+  tree tmpl = DECL_TI_TEMPLATE (decl);
+  tree cargs = CHECK_CONSTR_ARGS (t);
+
+  /* Instantiate the concept check arguments.  */
+  tree targs = tsubst_template_args (cargs, args, tf_none, NULL_TREE);
+  if (targs == error_mark_node)
+    return memoize_concept_satisfaction (tmpl, args, boolean_false_node);
+
+  /* Search for a previous value.  */
+  if (tree prev = lookup_concept_satisfaction (tmpl, targs))
+    return prev;
+
+  /* Expand the concept; failure here implies non-satisfaction.  */
+  tree def = expand_concept (decl, targs);
+  if (def == error_mark_node)
+    return memoize_concept_satisfaction (tmpl, args, boolean_false_node);
+
+  /* Recursively satisfy the constraint.  */
+  tree result = satisfy_constraint_1 (def, targs, complain, in_decl);
+  return memoize_concept_satisfaction (tmpl, targs, result);
 }
 
 /* Check an expression constraint. The constraint is satisfied if
@@ -1803,7 +1972,6 @@ satisfy_expression_constraint (tree t, tree args,
     return boolean_false_node;
   if (!perform_deferred_access_checks (tf_none))
     return boolean_false_node;
-
   return boolean_true_node;
 }
 
@@ -1822,7 +1990,6 @@ satisfy_type_constraint (tree t, tree args,
     return boolean_false_node;
   if (!perform_deferred_access_checks (complain))
     return boolean_false_node;
-
   return boolean_true_node;
 }
 
@@ -1932,11 +2099,8 @@ satisfy_conjunction (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 {
   tree t0 = satisfy_constraint_1 (TREE_OPERAND (t, 0), args, complain, in_decl);
   if (t0 == boolean_false_node)
-    return t0;
-  tree t1 = satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl);
-  if (t1 == boolean_false_node)
-    return t1;
-  return boolean_true_node;
+    return boolean_false_node;
+  return satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl);
 }
 
 /* Check that the disjunction of constraints is satisfied. Note
@@ -1949,10 +2113,7 @@ satisfy_disjunction (tree t, tree args, tsubst_flags_t complain, tree in_decl)
   tree t0 = satisfy_constraint_1 (TREE_OPERAND (t, 0), args, complain, in_decl);
   if (t0 == boolean_true_node)
     return boolean_true_node;
-  tree t1 = satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl);
-  if (t1 == boolean_true_node)
-    return boolean_true_node;
-  return boolean_false_node;
+  return satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl);
 }
 
 /* Dispatch to an appropriate satisfaction routine depending on the
@@ -1974,6 +2135,9 @@ satisfy_constraint_1 (tree t, tree args, tsubst_flags_t complain, tree in_decl)
   case PRED_CONSTR:
     return satisfy_predicate_constraint (t, args, complain, in_decl);
 
+  case CHECK_CONSTR:
+    return satisfy_check_constraint (t, args, complain, in_decl);
+
   case EXPR_CONSTR:
     return satisfy_expression_constraint (t, args, complain, in_decl);
 
@@ -2007,6 +2171,23 @@ satisfy_constraint_1 (tree t, tree args, tsubst_flags_t complain, tree in_decl)
   return boolean_false_node;
 }
 
+
+static int eval_constr = 0;
+
+struct evaluating_constraints_sentinel
+{
+  evaluating_constraints_sentinel()
+  {
+    ++eval_constr;
+  }
+
+  ~evaluating_constraints_sentinel()
+  {
+    --eval_constr;
+  }
+};
+
+
 /* Check that the constraint is satisfied, according to the rules
    for that constraint. Note that each satisfy_* function returns
    true or false, depending on whether it is satisfied or not.  */
@@ -2014,15 +2195,22 @@ satisfy_constraint_1 (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 tree
 satisfy_constraint (tree t, tree args)
 {
+  auto_timevar time (TV_CONSTRAINT_SAT);
+
   /* Turn off template processing. Constraint satisfaction only applies
-     to non-dependent terms, so we want full checking here.  */
-  processing_template_decl_sentinel sentinel (true);
+     to non-dependent terms, so we want to ensure full checking here.  */
+  processing_template_decl_sentinel proc (true);
+
+  /* Note that we are evaluating constraints.  */
+  evaluating_constraints_sentinel eval;
+
   /* Avoid early exit in tsubst and tsubst_copy from null args; since earlier
      substitution was done with processing_template_decl forced on, there will
      be expressions that still need semantic processing, possibly buried in
      decltype or a template argument.  */
   if (args == NULL_TREE)
     args = make_tree_vec (1);
+
   return satisfy_constraint_1 (t, args, tf_none, NULL_TREE);
 }
 
@@ -2042,11 +2230,17 @@ satisfy_associated_constraints (tree ci, tree args)
   if (args && uses_template_parms (args))
     return boolean_true_node;
 
-  /* Invalid requirements cannot be satisfied. */
+  /* Don't memoize this kind of result.  */
   if (!valid_constraints_p (ci))
     return boolean_false_node;
 
-  return satisfy_constraint (CI_NORMALIZED_CONSTRAINTS (ci), args);
+  /* Check if we've seen a previous result. */
+  if (tree prev = lookup_constraint_satisfaction (ci, args))
+    return prev;
+
+  /* Actually test for satisfaction. */
+  tree result = satisfy_constraint (CI_ASSOCIATED_CONSTRAINTS (ci), args);
+  return memoize_constraint_satisfaction (ci, args, result);
 }
 
 } /* namespace */
@@ -2059,7 +2253,7 @@ tree
 evaluate_constraints (tree constr, tree args)
 {
   gcc_assert (constraint_p (constr));
-  return satisfy_constraint (normalize_constraint (constr), args);
+  return satisfy_constraint (constr, args);
 }
 
 /* Evaluate the function concept FN by substituting its own args
@@ -2070,14 +2264,7 @@ evaluate_constraints (tree constr, tree args)
 tree
 evaluate_function_concept (tree fn, tree args)
 {
-  ++processing_template_decl;
-  /* We lift using DECL_TI_ARGS because we want to delay producing
-     non-dependent expressions until we're doing satisfaction.  We can't just
-     go without any substitution because we need to lower the level of 'auto's
-     in type deduction constraints.  */
-  tree constr = transform_expression (lift_function_definition
-				      (fn, DECL_TI_ARGS (fn)));
-  --processing_template_decl;
+  tree constr = build_nt (CHECK_CONSTR, fn, args);
   return satisfy_constraint (constr, args);
 }
 
@@ -2087,12 +2274,9 @@ evaluate_function_concept (tree fn, tree args)
    boolean_false_node otherwise.  */
 
 tree
-evaluate_variable_concept (tree decl, tree args)
+evaluate_variable_concept (tree var, tree args)
 {
-  ++processing_template_decl;
-  tree constr = transform_expression (lift_variable_initializer
-				      (decl, DECL_TI_ARGS (decl)));
-  --processing_template_decl;
+  tree constr = build_nt (CHECK_CONSTR, var, args);
   return satisfy_constraint (constr, args);
 }
 
@@ -2103,9 +2287,7 @@ evaluate_variable_concept (tree decl, tree args)
 tree
 evaluate_constraint_expression (tree expr, tree args)
 {
-  ++processing_template_decl;
-  tree constr = transform_expression (lift_expression (expr));
-  --processing_template_decl;
+  tree constr = normalize_expression (expr);
   return satisfy_constraint (constr, args);
 }
 
@@ -2167,6 +2349,16 @@ constraint_expression_satisfied_p (tree expr, tree args)
 
 } /* namespace */
 
+/* Returns true when constraints are being evaluated for satisfaction.
+
+   TODO: This is only used in tsubst_decl to guard against a possible
+   bug in specialization registration/lookup for variable templates
+   instantiated during concept expansion.  */
+bool
+evaluating_constraints_p ()
+{
+  return eval_constr;
+}
 
 /*---------------------------------------------------------------------------
                 Semantic analysis of requires-expressions
@@ -2310,14 +2502,6 @@ equivalently_constrained (tree d1, tree d2)
                      Partial ordering of constraints
 ---------------------------------------------------------------------------*/
 
-/* Returns true when the the constraints in A subsume those in B.  */
-bool
-subsumes_constraints (tree a, tree b)
-{
-  gcc_assert (!a || TREE_CODE (a) == CONSTRAINT_INFO);
-  gcc_assert (!b || TREE_CODE (b) == CONSTRAINT_INFO);
-  return subsumes (a, b);
-}
 
 /* Returns true when the the constraints in A subsume those in B, but
    the constraints in B do not subsume the constraints in A.  */
@@ -2328,12 +2512,24 @@ strictly_subsumes (tree a, tree b)
   return subsumes (a, b) && !subsumes (b, a);
 }
 
+/* Returns true when the the constraints in A subsume those in B.  */
+
+bool
+subsumes_constraints (tree a, tree b)
+{
+  gcc_assert (!a || TREE_CODE (a) == CONSTRAINT_INFO);
+  gcc_assert (!b || TREE_CODE (b) == CONSTRAINT_INFO);
+  return subsumes (a, b);
+}
+
+
 /* Determines which of the declarations, A or B, is more constrained.
    That is, which declaration's constraints subsume but are not subsumed
    by the other's?
 
    Returns 1 if A is more constrained than B, -1 if B is more constrained
    than A, and 0 otherwise. */
+
 int
 more_constrained (tree d1, tree d2)
 {
@@ -2350,6 +2546,7 @@ more_constrained (tree d1, tree d2)
 /* Returns true if D1 is at least as constrained as D2. That is, the
    associated constraints of D1 subsume those of D2, or both declarations
    are unconstrained. */
+
 bool
 at_least_as_constrained (tree d1, tree d2)
 {
@@ -2361,49 +2558,71 @@ at_least_as_constrained (tree d1, tree d2)
 
 /*---------------------------------------------------------------------------
                         Constraint diagnostics
+
+FIXME: Normalize expressions into constraints before evaluating them.
+This should be the general pattern for all such diagnostics.
 ---------------------------------------------------------------------------*/
 
-/* The diagnosis of constraints performs a combination of
-   normalization and satisfaction testing. We recursively
-   walk through the conjunction (or disjunctions) of associated
-   constraints, testing each sub-expression in turn.
+/* The number of detailed constraint failures.  */
 
-   We currently restrict diagnostics to just the top-level
-   conjunctions within the associated constraints. A fully
-   recursive walk is possible, but it can generate a lot
-   of errors. */
+int constraint_errors = 0;
 
+/* Do not generate errors after diagnosing this number of constraint
+   failures.
 
-namespace {
+   FIXME: This is a really arbitrary number. Provide better control of
+   constraint diagnostics with a command line option.  */
 
-void diagnose_expression (location_t, tree, tree);
-void diagnose_constraint (location_t, tree, tree);
+int constraint_thresh = 20;
 
-/* Diagnose a conjunction of constraints. */
-void
-diagnose_logical_operation (location_t loc, tree t, tree args)
+
+/* Returns true if we should elide the diagnostic for a constraint failure.
+   This is the case when then number of errors has exceeded the pre-configured
+   threshold.  */
+
+inline bool
+elide_constraint_failure_p ()
 {
-  diagnose_expression (loc, TREE_OPERAND (t, 0), args);
-  diagnose_expression (loc, TREE_OPERAND (t, 0), args);
+  bool ret = constraint_thresh <= constraint_errors;
+  ++constraint_errors;
+  return ret;
 }
 
-/* Determine if the trait expression T is satisfied by ARGS.
-   Emit a precise diagnostic if it is not. */
+/* Returns the number of undiagnosed errors. */
+
+inline int
+undiagnosed_constraint_failures ()
+{
+  return constraint_errors - constraint_thresh;
+}
+
+/* The diagnosis of constraints performs a combination of normalization
+   and satisfaction testing. We recursively walk through the conjunction or
+   disjunction of associated constraints, testing each sub-constraint in
+   turn.  */
+
+namespace {
+
+void diagnose_constraint (location_t, tree, tree, tree);
+
+/* Emit a specific diagnostics for a failed trait.  */
+
 void
-diagnose_trait_expression (location_t loc, tree t, tree args)
+diagnose_trait_expression (location_t loc, tree, tree cur, tree args)
 {
-  if (constraint_expression_satisfied_p (t, args))
+  if (constraint_expression_satisfied_p (cur, args))
+    return;
+  if (elide_constraint_failure_p())
     return;
 
-  /* Rebuild the trait expression so we can diagnose the
-     specific failure. */
+  tree expr = PRED_CONSTR_EXPR (cur);
   ++processing_template_decl;
-  tree expr = tsubst_expr (t, args, tf_none, NULL_TREE, false);
+  expr = tsubst_expr (expr, args, tf_none, NULL_TREE, false);
   --processing_template_decl;
 
   tree t1 = TRAIT_EXPR_TYPE1 (expr);
   tree t2 = TRAIT_EXPR_TYPE2 (expr);
-  switch (TRAIT_EXPR_KIND (t))
+  switch (TRAIT_EXPR_KIND (expr))
     {
     case CPTK_HAS_NOTHROW_ASSIGN:
       inform (loc, "  %qT is not nothrow copy assignable", t1);
@@ -2473,93 +2692,52 @@ diagnose_trait_expression (location_t loc, tree t, tree args)
     }
 }
 
-/* Determine if the call expression T, when normalized as a constraint,
-   is satisfied by ARGS.
+/* Diagnose the expression of a predicate constraint.  */
 
-   TODO: If T is refers to a concept, We could recursively analyze
-   its definition to identify the exact failure, but that could
-   emit a *lot* of error messages (defeating the purpose of
-   improved diagnostics). Consider adding a flag to control the
-   depth of diagnostics. */
 void
-diagnose_call_expression (location_t loc, tree t, tree args)
+diagnose_other_expression (location_t loc, tree, tree cur, tree args)
 {
-  if (constraint_expression_satisfied_p (t, args))
+  if (constraint_expression_satisfied_p (cur, args))
     return;
-
-  /* Rebuild the expression for the purpose of diagnostics. */
-  ++processing_template_decl;
-  tree expr = tsubst_expr (t, args, tf_none, NULL_TREE, false);
-  --processing_template_decl;
-
-  /* If the function call is known to be a concept check, then
-     diagnose it differently (i.e., we may recurse). */
-  if (resolve_constraint_check (t))
-    inform (loc, "  concept %qE was not satisfied", expr);
-  else
-    inform (loc, "  %qE evaluated to false", expr);
-}
-
-/* Determine if the template-id T, when normalized as a constraint
-   is satisfied by ARGS. */
-void
-diagnose_template_id (location_t loc, tree t, tree args)
-{
-  /* Check for invalid template-ids. */
-  if (!variable_template_p (TREE_OPERAND (t, 0)))
-    {
-      inform (loc, "  invalid constraint %qE", t);
-      return;
-    }
-
-  if (constraint_expression_satisfied_p (t, args))
+  if (elide_constraint_failure_p())
     return;
+  inform (loc, "%qE evaluated to false", cur);
+}
 
-  /* Rebuild the expression for the purpose of diagnostics. */
-  ++processing_template_decl;
-  tree expr = tsubst_expr (t, args, tf_none, NULL_TREE, false);
-  --processing_template_decl;
+/* Do our best to infer meaning from predicates.  */
 
-  tree var = DECL_TEMPLATE_RESULT (TREE_OPERAND (t, 0));
-  if (DECL_DECLARED_CONCEPT_P (var))
-    inform (loc, "  concept %qE was not satisfied", expr);
+inline void
+diagnose_predicate_constraint (location_t loc, tree orig, tree cur, tree args)
+{
+  if (TREE_CODE (PRED_CONSTR_EXPR (cur)) == TRAIT_EXPR)
+    diagnose_trait_expression (loc, orig, cur, args);
   else
-    inform (loc, "  %qE evaluated to false", expr);
+    diagnose_other_expression (loc, orig, cur, args);
 }
 
-/* Determine if the requires-expression, when normalized as a
-   constraint is satisfied by ARGS.
+/* Diagnose a failed pack expansion, possibly containing constraints.  */
 
-   TODO: Build sets of expressions, types, and constraints
-   based on the requirements in T and emit specific diagnostics
-   for those. */
 void
-diagnose_requires_expression (location_t loc, tree t, tree args)
+diagnose_pack_expansion (location_t loc, tree, tree cur, tree args)
 {
-  if (constraint_expression_satisfied_p (t, args))
+  if (constraint_expression_satisfied_p (cur, args))
     return;
-  inform (loc, "requirements not satisfied");
-}
-
-void
-diagnose_pack_expansion (location_t loc, tree t, tree args)
-{
-  if (constraint_expression_satisfied_p (t, args))
+  if (elide_constraint_failure_p())
     return;
 
   /* Make sure that we don't have naked packs that we don't expect. */
-  if (!same_type_p (TREE_TYPE (t), boolean_type_node))
+  if (!same_type_p (TREE_TYPE (cur), boolean_type_node))
     {
-      inform (loc, "invalid pack expansion in constraint %qE", t);
+      inform (loc, "invalid pack expansion in constraint %qE", cur);
       return;
     }
 
-  inform (loc, "  in the expansion of %qE", t);
+  inform (loc, "in the expansion of %qE", cur);
 
   /* Get the vector of expanded arguments. Note that n must not
      be 0 since this constraint is not satisfied.  */
   ++processing_template_decl;
-  tree exprs = tsubst_pack_expansion (t, args, tf_none, NULL_TREE);
+  tree exprs = tsubst_pack_expansion (cur, args, tf_none, NULL_TREE);
   --processing_template_decl;
   if (exprs == error_mark_node)
     {
@@ -2578,82 +2756,260 @@ diagnose_pack_expansion (location_t loc, tree t, tree args)
     }
 }
 
-/* Diagnose an expression that would be characterized as
-   a predicate constraint. */
 void
-diagnose_other_expression (location_t loc, tree t, tree args)
+diagnose_check_constraint (location_t loc, tree orig, tree cur, tree args)
 {
-  if (constraint_expression_satisfied_p (t, args))
+  if (constraints_satisfied_p (cur, args))
     return;
-  inform (loc, "  %qE evaluated to false", t);
+
+  tree decl = CHECK_CONSTR_CONCEPT (cur);
+  tree cargs = CHECK_CONSTR_ARGS (cur);
+  tree tmpl = DECL_TI_TEMPLATE (decl);
+  tree check = build_nt (CHECK_CONSTR, decl, cargs);
+
+  /* Instantiate the concept check arguments.  */
+  tree targs = tsubst_template_args (cargs, args, tf_none, NULL_TREE);
+  if (targs == error_mark_node)
+    {
+      if (elide_constraint_failure_p ())
+        return;
+      inform (loc, "invalid use of the concept %qE", check);
+      tsubst_template_args (cargs, args, tf_warning_or_error, NULL_TREE);
+      return;
+    }
+
+  tree sub = build_tree_list (tmpl, targs);
+  /* Update to the expanded definitions. */
+  cur = expand_concept (decl, targs);
+  if (cur == error_mark_node)
+    {
+      if (elide_constraint_failure_p ())
+        return;
+      inform (loc, "in the expansion of concept %qE %S", check, sub);
+      cur = get_concept_definition (decl);
+      tsubst_expr (cur, targs, tf_warning_or_error, NULL_TREE, false);
+      return;
+    }
+
+  orig = get_concept_definition (CHECK_CONSTR_CONCEPT (orig));
+  orig = normalize_expression (orig);
+
+  location_t dloc = DECL_SOURCE_LOCATION (decl);
+  inform (dloc, "within %qS", sub);
+  diagnose_constraint (dloc, orig, cur, targs);
 }
 
 void
-diagnose_expression (location_t loc, tree t, tree args)
+diagnose_logical_constraint (location_t loc, tree orig, tree cur, tree args)
 {
-  switch (TREE_CODE (t))
-    {
-    case TRUTH_ANDIF_EXPR:
-      diagnose_logical_operation (loc, t, args);
-      break;
+  tree t0 = TREE_OPERAND (cur, 0);
+  tree t1 = TREE_OPERAND (cur, 1);
+  if (!constraints_satisfied_p (t0, args))
+    diagnose_constraint (loc, TREE_OPERAND (orig, 0), t0, args);
+  if (!constraints_satisfied_p (t1, args))
+    diagnose_constraint (loc, TREE_OPERAND (orig, 1), t1, args);
+}
 
-    case TRUTH_ORIF_EXPR:
-      diagnose_logical_operation (loc, t, args);
-      break;
+/* Diagnose a constraint failure. */
 
-    case CALL_EXPR:
-      diagnose_call_expression (loc, t, args);
-      break;
+void
+diagnose_expression_constraint (location_t loc, tree orig, tree cur, tree args)
+{
+  if (constraints_satisfied_p (cur, args))
+    return;
+  if (elide_constraint_failure_p())
+    return;
 
-    case TEMPLATE_ID_EXPR:
-      diagnose_template_id (loc, t, args);
-      break;
+  tree expr = EXPR_CONSTR_EXPR (orig);
+  inform (loc, "the required expression %qE would be ill-formed", expr);
 
-    case REQUIRES_EXPR:
-      diagnose_requires_expression (loc, t, args);
-      break;
+  // TODO: We should have a flag that controls this substitution.
+  // I'm finding it very useful for resolving concept check errors.
 
-    case TRAIT_EXPR:
-      diagnose_trait_expression (loc, t, args);
-      break;
+  // inform (input_location, "==== BEGIN DUMP ====");
+  // tsubst_expr (EXPR_CONSTR_EXPR (orig), args, tf_warning_or_error, NULL_TREE, false);
+  // inform (input_location, "==== END DUMP ====");
+}
 
-    case EXPR_PACK_EXPANSION:
-      diagnose_pack_expansion (loc, t, args);
-      break;
 
-    default:
-      diagnose_other_expression (loc, t, args);
-      break;
+/* Diagnose a potentially failed type constraint. */
+
+void
+diagnose_type_constraint (location_t loc, tree orig, tree cur, tree args)
+{
+  if (constraints_satisfied_p (cur, args))
+    return;
+  if (elide_constraint_failure_p())
+    return;
+
+  tree type = TYPE_CONSTR_TYPE (orig);
+  inform (loc, "the required type %qT would be ill-formed", type);
+}
+
+/* Diagnose a potentially unsatisfied conversion constraint. */
+
+void
+diagnose_implicit_conversion_constraint (location_t loc, tree orig, tree cur, tree args)
+{
+  if (constraints_satisfied_p (cur, args))
+    return;
+
+  /* The expression and type will previously have been substituted into,
+     and therefore may already be an error. Also, we will have already
+     diagnosed substitution failures into an expression since this must be
+     part of a compound requirement.  */
+  tree expr = ICONV_CONSTR_EXPR (cur);
+  if (error_operand_p (expr))
+    return;
+
+  /* Don't elide a previously diagnosed failure.  */
+  if (elide_constraint_failure_p())
+    return;
+
+  tree type = ICONV_CONSTR_TYPE (cur);
+  if (error_operand_p (type))
+    {
+      inform (loc, "substitution into type %qT failed", ICONV_CONSTR_TYPE (orig));
+      return;
     }
+
+  inform(loc, "%qE is not implicitly convertible to %qT", expr, type);
 }
 
-inline void
-diagnose_predicate_constraint (location_t loc, tree t, tree args)
+/* Diagnose an argument deduction constraint. */
+
+void
+diagnose_argument_deduction_constraint (location_t loc, tree orig, tree cur, tree args)
 {
-  diagnose_expression (loc, PRED_CONSTR_EXPR (t), args);
+  if (constraints_satisfied_p (cur, args))
+    return;
+
+  /* The expression and type will previously have been substituted into,
+     and therefore may already be an error. Also, we will have already
+     diagnosed substution failures into an expression since this must be
+     part of a compound requirement.  */
+  tree expr = DEDUCT_CONSTR_EXPR (cur);
+  if (error_operand_p (expr))
+    return;
+
+  /* Don't elide a previously diagnosed failure.  */
+  if (elide_constraint_failure_p())
+    return;
+
+  tree pattern = DEDUCT_CONSTR_PATTERN (cur);
+  if (error_operand_p (pattern))
+    {
+      inform (loc, "substitution into type %qT failed", DEDUCT_CONSTR_PATTERN (orig));
+      return;
+    }
+
+  inform (loc, "unable to deduce placeholder type %qT from %qE", pattern, expr);
 }
 
-inline void
-diagnose_conjunction (location_t loc, tree t, tree args)
+/* Diagnose an exception constraint. */
+
+void
+diagnose_exception_constraint (location_t loc, tree orig, tree cur, tree args)
 {
-  diagnose_constraint (loc, TREE_OPERAND (t, 0), args);
-  diagnose_constraint (loc, TREE_OPERAND (t, 1), args);
+  if (constraints_satisfied_p (cur, args))
+    return;
+  if (elide_constraint_failure_p ())
+    return;
+
+  /* Rebuild a noexcept expression. */
+  tree expr = EXCEPT_CONSTR_EXPR (cur);
+  if (error_operand_p (expr))
+    return;
+
+  inform (loc, "%qE evaluated to false", EXCEPT_CONSTR_EXPR (orig));
 }
 
-/* Diagnose the constraint T for the given ARGS. This is only
-   ever invoked on the associated constraints, so we can
-   only have conjunctions of predicate constraints. */
 void
-diagnose_constraint (location_t loc, tree t, tree args)
+diagnose_parameterized_constraint (location_t loc, tree orig, tree cur, tree args)
 {
-  switch (TREE_CODE (t))
+  if (constraints_satisfied_p (cur, args))
+    return;
+
+  local_specialization_stack stack;
+  tree parms = PARM_CONSTR_PARMS (cur);
+  tree vars = tsubst_constraint_variables (parms, args, tf_warning_or_error, NULL_TREE);
+  if (vars == error_mark_node)
     {
+      if (elide_constraint_failure_p ())
+        return;
+
+      /* TODO: Check which variable failed and use orig to diagnose
+         that substitution error.  */
+      inform (loc, "failed to instantiate constraint variables");
+      return;
+    }
+
+  /* TODO: It would be better write these in a list. */
+  while (vars)
+    {
+      inform (loc, "    with %q#D", vars);
+      vars = TREE_CHAIN (vars);
+    }
+  orig = PARM_CONSTR_OPERAND (orig);
+  cur = PARM_CONSTR_OPERAND (cur);
+  return diagnose_constraint (loc, orig, cur, args);
+}
+
+/* Diagnose the constraint CUR for the given ARGS. This is only ever invoked
+   on the associated constraints, so we can only have conjunctions of
+   predicate constraints.  The ORIGinal (dependent) constructs follow
+   the current constraints to enable better diagnostics.  Note that ORIG
+   and CUR must be the same kinds of node, except when CUR is an error.  */
+
+void
+diagnose_constraint (location_t loc, tree orig, tree cur, tree args)
+{
+  switch (TREE_CODE (cur))
+    {
+    case EXPR_CONSTR:
+      diagnose_expression_constraint (loc, orig, cur, args);
+      break;
+
+    case TYPE_CONSTR:
+      diagnose_type_constraint (loc, orig, cur, args);
+      break;
+
+    case ICONV_CONSTR:
+      diagnose_implicit_conversion_constraint (loc, orig, cur, args);
+      break;
+
+    case DEDUCT_CONSTR:
+      diagnose_argument_deduction_constraint (loc, orig, cur, args);
+      break;
+
+    case EXCEPT_CONSTR:
+      diagnose_exception_constraint (loc, orig, cur, args);
+      break;
+
     case CONJ_CONSTR:
-      diagnose_conjunction (loc, t, args);
+    case DISJ_CONSTR:
+      diagnose_logical_constraint (loc, orig, cur, args);
       break;
 
     case PRED_CONSTR:
-      diagnose_predicate_constraint (loc, t, args);
+      diagnose_predicate_constraint (loc, orig, cur, args);
+      break;
+
+    case PARM_CONSTR:
+      diagnose_parameterized_constraint (loc, orig, cur, args);
+      break;
+
+    case CHECK_CONSTR:
+      diagnose_check_constraint (loc, orig, cur, args);
+      break;
+
+    case EXPR_PACK_EXPANSION:
+      diagnose_pack_expansion (loc, orig, cur, args);
+      break;
+
+    case ERROR_MARK:
+      /* TODO: Can we improve the diagnostic with the original?  */
+      inform (input_location, "ill-formed constraint");
       break;
 
     default:
@@ -2687,7 +3043,8 @@ diagnose_declaration_constraints (location_t loc, tree decl, tree args)
     }
 
   /* Recursively diagnose the associated constraints.  */
-  diagnose_constraint (loc, CI_ASSOCIATED_CONSTRAINTS (ci), args);
+  tree t = CI_ASSOCIATED_CONSTRAINTS (ci);
+  diagnose_constraint (loc, t, t, args);
 }
 
 } // namespace
@@ -2699,8 +3056,17 @@ diagnose_declaration_constraints (location_t loc, tree decl, tree args)
 void
 diagnose_constraints (location_t loc, tree t, tree args)
 {
+  constraint_errors = 0;
+
   if (constraint_p (t))
-    diagnose_constraint (loc, t, args);
-  else
+    diagnose_constraint (loc, t, t, args);
+  else if (DECL_P (t))
     diagnose_declaration_constraints (loc, t, args);
+  else
+    gcc_unreachable ();
+
+  /* Note the number of elided failures. */
+  int n = undiagnosed_constraint_failures ();
+  if (n > 0)
+    inform (loc, "... and %d more constraint errors not shown", n);
 }
diff --git a/gcc/cp/cp-tree.def b/gcc/cp/cp-tree.def
index e6e5139aaa2..224f5089da4 100644
--- a/gcc/cp/cp-tree.def
+++ b/gcc/cp/cp-tree.def
@@ -536,6 +536,15 @@ DEFTREECODE (NESTED_REQ, "nested_req", tcc_expression, 1)
    PRED_CONSTR_EXPR has the expression to be evaluated. */
 DEFTREECODE (PRED_CONSTR, "pred_constr", tcc_expression, 1)
 
+
+/* A check constraint represents the checking of a concept
+   C. It has two operands: the template defining the concept
+   and a sequence of template arguments.
+
+   CHECK_CONSTR_CONCEPT has the concept definition
+   CHECK_CONSTR_ARGUMENTS are the template arguments */
+DEFTREECODE (CHECK_CONSTR, "check_constr", tcc_expression, 2)
+
 /* An expression constraint determines the validity of a expression E.
 
    EXPR_CONST_EXPR has the expression being validated. */
@@ -560,7 +569,7 @@ DEFTREECODE (ICONV_CONSTR, "iconv_constr", tcc_expression, 2)
    T must contain at least one place holder.
 
    DEDUCT_CONSTR_EXPR has the expression E
-   DEDUCT_CONSTR_PATTERN has the type patter T.
+   DEDUCT_CONSTR_PATTERN has the type pattern T.
    DEDUCT_CONSTR_PLACEHOLDERS has the list of placeholder nodes in T. */
 DEFTREECODE (DEDUCT_CONSTR, "deduct_constr", tcc_expression, 3)
 
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 5b87bb391d9..61356bd86b7 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -976,6 +976,14 @@ check_constraint_info (tree t)
 #define PRED_CONSTR_EXPR(NODE) \
   TREE_OPERAND (TREE_CHECK (NODE, PRED_CONSTR), 0)
 
+/* The concept of a concept check. */
+#define CHECK_CONSTR_CONCEPT(NODE) \
+  TREE_OPERAND (TREE_CHECK (NODE, CHECK_CONSTR), 0)
+
+/* The template arguments of a concept check. */
+#define CHECK_CONSTR_ARGS(NODE) \
+  TREE_OPERAND (TREE_CHECK (NODE, CHECK_CONSTR), 1)
+
 /* The expression validated by the predicate constraint. */
 #define EXPR_CONSTR_EXPR(NODE) \
   TREE_OPERAND (TREE_CHECK (NODE, EXPR_CONSTR), 0)
@@ -6118,6 +6126,7 @@ extern bool is_specialization_of_friend		(tree, tree);
 extern tree get_pattern_parm			(tree, tree);
 extern int comp_template_args			(tree, tree, tree * = NULL,
 						 tree * = NULL);
+extern int template_args_equal                  (tree, tree);
 extern tree maybe_process_partial_specialization (tree);
 extern tree most_specialized_instantiation	(tree);
 extern void print_candidates			(tree);
@@ -6130,6 +6139,8 @@ extern tree tsubst_copy_and_build		(tree, tree, tsubst_flags_t,
 extern tree tsubst_expr                         (tree, tree, tsubst_flags_t,
                                                  tree, bool);
 extern tree tsubst_pack_expansion               (tree, tree, tsubst_flags_t, tree);
+extern tree tsubst_template_arg                 (tree, tree, tsubst_flags_t, tree);
+extern tree tsubst_template_args                (tree, tree, tsubst_flags_t, tree);
 extern tree most_general_template		(tree);
 extern tree get_mostly_instantiated_function_type (tree);
 extern bool problematic_instantiation_changed	(void);
@@ -6847,7 +6858,6 @@ extern tree strip_using_decl                    (tree);
 /* in constraint.cc */
 extern void init_constraint_processing          ();
 extern bool constraint_p                        (tree);
-extern tree make_predicate_constraint           (tree);
 extern tree conjoin_constraints                 (tree, tree);
 extern tree conjoin_constraints                 (tree);
 extern bool valid_constraints_p                 (tree);
@@ -6881,13 +6891,24 @@ extern tree tsubst_requires_expr                (tree, tree, tsubst_flags_t, tre
 extern tree tsubst_constraint                   (tree, tree, tsubst_flags_t, tree);
 extern tree tsubst_constraint_info              (tree, tree, tsubst_flags_t, tree);
 extern bool function_concept_check_p            (tree);
-
+extern tree normalize_expression                (tree);
+extern tree expand_concept                      (tree, tree);
+extern bool expanding_concept                   ();
 extern tree evaluate_constraints                (tree, tree);
 extern tree evaluate_function_concept           (tree, tree);
 extern tree evaluate_variable_concept           (tree, tree);
 extern tree evaluate_constraint_expression      (tree, tree);
 extern bool constraints_satisfied_p             (tree);
 extern bool constraints_satisfied_p             (tree, tree);
+extern bool evaluating_constraints_p            ();
+extern tree lookup_constraint_satisfaction      (tree, tree);
+extern tree memoize_constraint_satisfaction     (tree, tree, tree);
+extern tree lookup_concept_satisfaction         (tree, tree);
+extern tree memoize_concept_satisfaction        (tree, tree, tree);
+extern tree get_concept_expansion               (tree, tree);
+extern tree save_concept_expansion              (tree, tree, tree);
+extern bool* lookup_subsumption_result          (tree, tree);
+extern bool save_subsumption_result             (tree, tree, bool);
 
 extern bool equivalent_constraints              (tree, tree);
 extern bool equivalently_constrained            (tree, tree);
diff --git a/gcc/cp/cxx-pretty-print.c b/gcc/cp/cxx-pretty-print.c
index 3b52a35a2e5..203db4a5739 100644
--- a/gcc/cp/cxx-pretty-print.c
+++ b/gcc/cp/cxx-pretty-print.c
@@ -22,6 +22,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "system.h"
 #include "coretypes.h"
 #include "cp-tree.h"
+#include "print-tree.h"
 #include "cxx-pretty-print.h"
 #include "tree-pretty-print.h"
 
@@ -35,7 +36,9 @@ static void pp_cxx_parameter_declaration_clause (cxx_pretty_printer *, tree);
 static void pp_cxx_template_parameter (cxx_pretty_printer *, tree);
 static void pp_cxx_cast_expression (cxx_pretty_printer *, tree);
 static void pp_cxx_typeid_expression (cxx_pretty_printer *, tree);
-
+static void pp_cxx_unary_left_fold_expression (cxx_pretty_printer *, tree);
+static void pp_cxx_unary_right_fold_expression (cxx_pretty_printer *, tree);
+static void pp_cxx_binary_fold_expression (cxx_pretty_printer *, tree);
 
 static inline void
 pp_cxx_nonconsecutive_character (cxx_pretty_printer *pp, int c)
@@ -1139,6 +1142,19 @@ cxx_pretty_printer::expression (tree t)
       pp_cxx_ws_string (this, "...");
       break;
 
+    case UNARY_LEFT_FOLD_EXPR:
+      pp_cxx_unary_left_fold_expression (this, t);
+      break;
+
+    case UNARY_RIGHT_FOLD_EXPR:
+      pp_cxx_unary_right_fold_expression (this, t);
+    break;
+
+    case BINARY_LEFT_FOLD_EXPR:
+    case BINARY_RIGHT_FOLD_EXPR:
+      pp_cxx_binary_fold_expression (this, t);
+      break;
+
     case TEMPLATE_ID_EXPR:
       pp_cxx_template_id (this, t);
       break;
@@ -1165,6 +1181,7 @@ cxx_pretty_printer::expression (tree t)
       break;
 
     case PRED_CONSTR:
+    case CHECK_CONSTR:
     case EXPR_CONSTR:
     case TYPE_CONSTR:
     case ICONV_CONSTR:
@@ -2198,6 +2215,11 @@ void
 pp_cxx_constrained_type_spec (cxx_pretty_printer *pp, tree c)
 {
   tree t, a;
+  if (c == error_mark_node)
+    {
+      pp_cxx_ws_string(pp, "<unsatisfied-constrained-placeholder>");
+      return;
+    }
   placeholder_extract_concept_and_args (c, t, a);
   pp->id_expression (t);
   if (TREE_VEC_LENGTH (a) > 1)
@@ -2407,6 +2429,103 @@ pp_cxx_offsetof_expression (cxx_pretty_printer *pp, tree t)
   pp_cxx_right_paren (pp);
 }
 
+static char const*
+get_fold_operator (tree t)
+{
+  int op = int_cst_value (FOLD_EXPR_OP (t));
+  if (FOLD_EXPR_MODIFY_P (t))
+    {
+      switch (op)
+        {
+        case NOP_EXPR: return "=";
+        case PLUS_EXPR: return "+=";
+        case MINUS_EXPR: return "-=";
+        case MULT_EXPR: return "*=";
+        case TRUNC_DIV_EXPR: return "/=";
+        case TRUNC_MOD_EXPR: return "%=";
+        case BIT_XOR_EXPR: return "^=";
+        case BIT_AND_EXPR: return "&=";
+        case BIT_IOR_EXPR: return "|=";
+        case LSHIFT_EXPR: return "<<=";
+        case RSHIFT_EXPR: return ">>=";
+        default: gcc_unreachable ();
+        }
+    }
+  else
+    {
+      switch (op)
+        {
+        case PLUS_EXPR: return "+";
+        case MINUS_EXPR: return "-";
+        case MULT_EXPR: return "*";
+        case TRUNC_DIV_EXPR: return "/";
+        case TRUNC_MOD_EXPR: return "%";
+        case BIT_XOR_EXPR: return "^";
+        case BIT_AND_EXPR: return "&";
+        case BIT_IOR_EXPR: return "|";
+        case LSHIFT_EXPR: return "<<";
+        case RSHIFT_EXPR: return ">>";
+        case EQ_EXPR: return "==";
+        case NE_EXPR: return "!=";
+        case LT_EXPR: return "<";
+        case GT_EXPR: return ">";
+        case LE_EXPR: return "<=";
+        case GE_EXPR: return ">=";
+        case TRUTH_ANDIF_EXPR: return "&&";
+        case TRUTH_ORIF_EXPR: return "||";
+        case MEMBER_REF: return "->*";
+        case DOTSTAR_EXPR: return ".*";
+        case OFFSET_REF: return ".*";
+        default: return ","; /* FIXME: Not the right default.  */
+        }
+    }
+}
+
+void
+pp_cxx_unary_left_fold_expression (cxx_pretty_printer *pp, tree t)
+{
+  char const* op = get_fold_operator (t);
+  tree expr = PACK_EXPANSION_PATTERN (FOLD_EXPR_PACK (t));
+  pp_cxx_left_paren (pp);
+  pp_cxx_ws_string (pp, "...");
+  pp_cxx_ws_string (pp, op);
+  pp->expression (expr);
+  pp_cxx_right_paren (pp);
+}
+
+void
+pp_cxx_unary_right_fold_expression (cxx_pretty_printer *pp, tree t)
+{
+  char const* op = get_fold_operator (t);
+  tree expr = PACK_EXPANSION_PATTERN (FOLD_EXPR_PACK (t));
+  pp_cxx_left_paren (pp);
+  pp->expression (expr);
+  pp_space (pp);
+  pp_cxx_ws_string (pp, op);
+  pp_cxx_ws_string (pp, "...");
+  pp_cxx_right_paren (pp);
+}
+
+void
+pp_cxx_binary_fold_expression (cxx_pretty_printer *pp, tree t)
+{
+  char const* op = get_fold_operator (t);
+  tree t1 = TREE_OPERAND (t, 1);
+  tree t2 = TREE_OPERAND (t, 2);
+  if (t1 == FOLD_EXPR_PACK (t))
+    t1 = PACK_EXPANSION_PATTERN (t1);
+  else
+    t2 = PACK_EXPANSION_PATTERN (t2);
+  pp_cxx_left_paren (pp);
+  pp->expression (t1);
+  pp_cxx_ws_string (pp, op);
+  pp_cxx_ws_string (pp, "...");
+  pp_cxx_ws_string (pp, op);
+  pp->expression (t2);
+  pp_cxx_right_paren (pp);
+}
+
+
 void
 pp_cxx_trait_expression (cxx_pretty_printer *pp, tree t)
 {
@@ -2617,6 +2736,7 @@ pp_cxx_compound_requirement (cxx_pretty_printer *pp, tree t)
       pp_cxx_ws_string (pp, "->");
       pp->type_id (type);
     }
+  pp_cxx_semicolon (pp);
 }
 
 /* nested requirement:
@@ -2632,74 +2752,94 @@ pp_cxx_nested_requirement (cxx_pretty_printer *pp, tree t)
 void
 pp_cxx_predicate_constraint (cxx_pretty_printer *pp, tree t)
 {
-  pp_string (pp, "predicate");
-  pp_left_paren (pp);
   pp->expression (TREE_OPERAND (t, 0));
-  pp_right_paren (pp);
+}
+
+void
+pp_cxx_check_constraint (cxx_pretty_printer *pp, tree t)
+{
+  tree decl = CHECK_CONSTR_CONCEPT (t);
+  tree tmpl = DECL_TI_TEMPLATE (decl);
+  tree args = CHECK_CONSTR_ARGS (t);
+  tree id = build_nt (TEMPLATE_ID_EXPR, tmpl, args);
+
+  if (TREE_CODE (decl) == VAR_DECL)
+    pp->expression (id);
+  else if (TREE_CODE (decl) == FUNCTION_DECL)
+    {
+      tree call = build_vl_exp (CALL_EXPR, 2);
+      TREE_OPERAND (call, 0) = integer_two_node;
+      TREE_OPERAND (call, 1) = id;
+      pp->expression (call);
+    }
+  else
+    gcc_unreachable ();
 }
 
 void
 pp_cxx_expression_constraint (cxx_pretty_printer *pp, tree t)
 {
-  pp_string (pp, "valid_expr");
-  pp_left_paren (pp);
+  pp_string (pp, "<valid-expression ");
+  pp_cxx_left_paren (pp);
   pp->expression (TREE_OPERAND (t, 0));
-  pp_right_paren (pp);
+  pp_cxx_right_paren (pp);
+  pp_string (pp, ">");
 }
 
 void
 pp_cxx_type_constraint (cxx_pretty_printer *pp, tree t)
 {
-  pp_string (pp, "valid_type");
-  pp_left_paren (pp);
+  pp_string (pp, "<valid-type ");
   pp->type_id (TREE_OPERAND (t, 0));
-  pp_right_paren (pp);
+  pp_string (pp, ">");
 }
 
 void
 pp_cxx_implicit_conversion_constraint (cxx_pretty_printer *pp, tree t)
 {
-  pp_string (pp, "convertible");
-  pp_left_paren (pp);
+  pp_string (pp, "<implicitly-conversion ");
+  pp_cxx_left_paren (pp);
   pp->expression (ICONV_CONSTR_EXPR (t));
-  pp_cxx_separate_with (pp, ',');
-  pp->expression (ICONV_CONSTR_TYPE (t));
-  pp_right_paren (pp);
+  pp_cxx_right_paren (pp);
+  pp_cxx_ws_string (pp, "to");
+  pp->type_id (ICONV_CONSTR_TYPE (t));
+  pp_string (pp, ">");
 }
 
 void
 pp_cxx_argument_deduction_constraint (cxx_pretty_printer *pp, tree t)
 {
-  pp_string (pp, "deducible");
-  pp_left_paren (pp);
+  pp_string (pp, "<argument-deduction ");
+  pp_cxx_left_paren (pp);
   pp->expression (DEDUCT_CONSTR_EXPR (t));
-  pp_cxx_separate_with (pp, ',');
+  pp_cxx_right_paren (pp);
+  pp_cxx_ws_string (pp, "as");
   pp->expression (DEDUCT_CONSTR_PATTERN (t));
-  pp_right_paren (pp);
+  pp_string (pp, ">");
 }
 
 void
 pp_cxx_exception_constraint (cxx_pretty_printer *pp, tree t)
 {
   pp_cxx_ws_string (pp, "noexcept");
-  pp_left_paren (pp);
+  pp_cxx_whitespace (pp);
+  pp_cxx_left_paren (pp);
   pp->expression (TREE_OPERAND (t, 0));
-  pp_right_paren (pp);
+  pp_cxx_right_paren (pp);
 }
 
 void
 pp_cxx_parameterized_constraint (cxx_pretty_printer *pp, tree t)
 {
   pp_left_paren (pp);
-  pp_string (pp, "forall");
+  pp_string (pp, "<requires ");
   if (tree parms = PARM_CONSTR_PARMS (t))
     {
-      if (parms)
 	pp_cxx_parameter_declaration_clause (pp, parms);
       pp_cxx_whitespace (pp);
     }
   pp_cxx_constraint (pp, PARM_CONSTR_OPERAND (t));
-  pp_right_paren (pp);
+  pp_string (pp, ">");
 }
 
 void
@@ -2730,6 +2870,10 @@ pp_cxx_constraint (cxx_pretty_printer *pp, tree t)
       pp_cxx_predicate_constraint (pp, t);
       break;
 
+    case CHECK_CONSTR:
+      pp_cxx_check_constraint (pp, t);
+      break;
+
     case EXPR_CONSTR:
       pp_cxx_expression_constraint (pp, t);
       break;
@@ -2762,6 +2906,10 @@ pp_cxx_constraint (cxx_pretty_printer *pp, tree t)
       pp_cxx_disjunction (pp, t);
       break;
 
+    case EXPR_PACK_EXPANSION:
+      pp->expression (TREE_OPERAND (t, 0));
+      break;
+
     default:
       gcc_unreachable ();
     }
diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c
index c86a131d489..854bc3359ec 100644
--- a/gcc/cp/decl.c
+++ b/gcc/cp/decl.c
@@ -7921,7 +7921,7 @@ grokfndecl (tree ctype,
 
       /* Adjust the required expression into a constraint. */
       if (decl_reqs)
-        decl_reqs = make_predicate_constraint (decl_reqs);
+        decl_reqs = normalize_expression (decl_reqs);
 
       tree ci = build_constraints (tmpl_reqs, decl_reqs);
       set_constraints (decl, ci);
diff --git a/gcc/cp/decl2.c b/gcc/cp/decl2.c
index 22f9eded291..bdfec92d8a8 100644
--- a/gcc/cp/decl2.c
+++ b/gcc/cp/decl2.c
@@ -31,6 +31,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "coretypes.h"
 #include "target.h"
 #include "cp-tree.h"
+#include "print-tree.h"
 #include "c-family/c-common.h"
 #include "timevar.h"
 #include "stringpool.h"
diff --git a/gcc/cp/error.c b/gcc/cp/error.c
index d5a7d0f9efd..85a345f9606 100644
--- a/gcc/cp/error.c
+++ b/gcc/cp/error.c
@@ -961,7 +961,12 @@ dump_simple_decl (cxx_pretty_printer *pp, tree t, tree type, int flags)
     {
       if (VAR_P (t)
 	  && DECL_DECLARED_CONSTEXPR_P (t))
+            {
+              if (DECL_DECLARED_CONCEPT_P (t))
+                pp_cxx_ws_string (pp, "concept");
+              else
 	pp_cxx_ws_string (pp, "constexpr");
+            }
       dump_type_prefix (pp, type, flags & ~TFF_UNQUALIFIED_NAME);
       pp_maybe_space (pp);
     }
@@ -1334,8 +1339,9 @@ dump_template_decl (cxx_pretty_printer *pp, tree t, int flags)
 	  if (TEMPLATE_TYPE_PARAMETER_PACK (TREE_TYPE (t)))
 	    pp_cxx_ws_string (pp, "...");
 	}
-    }
 
+      /* Only print the requirements if we're also printing
+         the template header.  */
   if (flag_concepts)
     if (tree ci = get_constraints (t))
       if (check_constraint_info (ci))
@@ -1344,6 +1350,8 @@ dump_template_decl (cxx_pretty_printer *pp, tree t, int flags)
 	    pp_cxx_requires_clause (pp, reqs);
 	    pp_cxx_whitespace (pp);
 	  }
+    }
+
 
   if (DECL_CLASS_TEMPLATE_P (t))
     dump_type (pp, TREE_TYPE (t),
@@ -1534,7 +1542,12 @@ dump_function_decl (cxx_pretty_printer *pp, tree t, int flags)
 	pp_cxx_ws_string (pp, "virtual");
 
       if (constexpr_p)
-	pp_cxx_ws_string (pp, "constexpr");
+        {
+          if (DECL_DECLARED_CONCEPT_P (t))
+            pp_cxx_ws_string (pp, "concept");
+          else
+	    pp_cxx_ws_string (pp, "constexpr");
+	}
     }
 
   /* Print the return type?  */
@@ -2665,6 +2678,10 @@ dump_expr (cxx_pretty_printer *pp, tree t, int flags)
       break;
 
     case EXPR_PACK_EXPANSION:
+    case UNARY_LEFT_FOLD_EXPR:
+    case UNARY_RIGHT_FOLD_EXPR:
+    case BINARY_LEFT_FOLD_EXPR:
+    case BINARY_RIGHT_FOLD_EXPR:
     case TYPEID_EXPR:
     case MEMBER_REF:
     case DOTSTAR_EXPR:
@@ -2737,6 +2754,7 @@ dump_expr (cxx_pretty_printer *pp, tree t, int flags)
       break;
 
     case PRED_CONSTR:
+    case CHECK_CONSTR:
     case EXPR_CONSTR:
     case TYPE_CONSTR:
     case ICONV_CONSTR:
diff --git a/gcc/cp/logic.cc b/gcc/cp/logic.cc
index c12c381d85c..77df28e322d 100644
--- a/gcc/cp/logic.cc
+++ b/gcc/cp/logic.cc
@@ -23,6 +23,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
+#include "timevar.h"
 #include "hash-set.h"
 #include "machmode.h"
 #include "vec.h"
@@ -33,6 +34,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "wide-int.h"
 #include "inchash.h"
 #include "tree.h"
+#include "print-tree.h"
 #include "stringpool.h"
 #include "attribs.h"
 #include "intl.h"
@@ -50,19 +52,52 @@ namespace {
 
 // Helper algorithms
 
-// Increment iter distance(first, last) times.
-template<typename I1, typename I2, typename I3>
-  I1 next_by_distance (I1 iter, I2 first, I3 last)
-  {
-    for ( ; first != last; ++first, ++iter)
-      ;
-    return iter;
-  }
+template<typename I>
+inline I
+next (I iter)
+{
+  return ++iter;
+}
+
+template<typename I, typename P>
+inline bool
+any_p (I first, I last, P pred)
+{
+  while (first != last)
+    {
+      if (pred(*first))
+        return true;
+      ++first;
+    }
+  return false;
+}
+
+bool prove_implication (tree, tree);
 
 /*---------------------------------------------------------------------------
                            Proof state
 ---------------------------------------------------------------------------*/
 
+struct term_entry
+{
+  tree t;
+};
+
+/* Hashing function and equality for constraint entries.  */
+
+struct term_hasher : ggc_ptr_hash<term_entry>
+{
+  static hashval_t hash (term_entry *e)
+  {
+    return iterative_hash_template_arg (e->t, 0);
+  }
+
+  static bool equal (term_entry *e1, term_entry *e2)
+  {
+    return cp_tree_equal (e1->t, e2->t);
+  }
+};
+
 /* A term list is a list of atomic constraints. It is used
    to maintain the lists of assumptions and conclusions in a
    proof goal.
@@ -70,109 +105,122 @@ template<typename I1, typename I2, typename I3>
    Each term list maintains an iterator that refers to the current
    term. This can be used by various tactics to support iteration
    and stateful manipulation of the list. */
-struct term_list : std::list<tree>
+struct term_list
 {
-  term_list ();
-  term_list (const term_list &x);
-  term_list& operator= (const term_list &x);
-
-  tree       current_term ()       { return *current; }
-  const_tree current_term () const { return *current; }
+  typedef std::list<tree>::iterator iterator;
 
+  term_list ();
+  term_list (tree);
 
-  void insert (tree t);
-  tree erase ();
+  bool includes (tree);
+  iterator insert (iterator, tree);
+  iterator push_back (tree);
+  iterator erase (iterator);
+  iterator replace (iterator, tree);
+  iterator replace (iterator, tree, tree);
 
-  void start ();
-  void next ();
-  bool done() const;
+  iterator begin() { return seq.begin(); }
+  iterator end() { return seq.end(); }
 
-  iterator current;
+  std::list<tree>         seq;
+  hash_table<term_hasher> tab;
 };
 
 inline
 term_list::term_list ()
-  : std::list<tree> (), current (end ())
-{ }
+  : seq(), tab (11)
+{
+}
 
-inline
-term_list::term_list (const term_list &x)
-  : std::list<tree> (x)
-  , current (next_by_distance (begin (), x.begin (), x.current))
-{ }
+/* Initialize a term list with an initial term. */
 
-inline term_list&
-term_list::operator= (const term_list &x)
+inline
+term_list::term_list (tree t)
+  : seq (), tab (11)
 {
-  std::list<tree>::operator=(x);
-  current = next_by_distance (begin (), x.begin (), x.current);
-  return *this;
+  push_back (t);
 }
 
-/* Try saving the term T into the list of terms. If
-   T is already in the list of terms, then no action is
-   performed. Otherwise, insert T before the current
-   position, making this term current.
+/* Returns true if T is the in the tree. */
 
-   Note that not inserting terms is an optimization
-   that corresponds to the structural rule of
-   contraction.
-
-   NOTE: With the contraction rule, this data structure
-   would be more efficiently represented as an ordered set
-   or hash set.  */
-void
-term_list::insert (tree t)
+inline bool
+term_list::includes (tree t)
 {
-  /* Search the current term list. If there is already
-     a matching term, do not add the new one.  */
-  for (iterator i = begin(); i != end(); ++i)
-    if (cp_tree_equal (*i, t))
-      return;
+  term_entry ent = {t};
+  return tab.find (&ent);
+}
 
-  current = std::list<tree>::insert (current, t);
+/* Append a term to the list. */
+inline term_list::iterator
+term_list::push_back (tree t)
+{
+  return insert (end(), t);
 }
 
-/* Remove the current term from the list, repositioning to
-   the term following the removed term. Note that the new
-   position could be past the end of the list.
+/* Insert a new (unseen) term T into the list before the proposition
+   indicated by ITER. Returns the iterator to the newly inserted
+   element.  */
 
-   The removed term is returned. */
-inline tree
-term_list::erase ()
+term_list::iterator
+term_list::insert (iterator iter, tree t)
 {
-  tree t = *current;
-  current = std::list<tree>::erase (current);
-  return t;
+  gcc_assert (!includes (t));
+  iter = seq.insert (iter, t);
+  term_entry ent = {t};
+  term_entry** slot = tab.find_slot (&ent, INSERT);
+  term_entry* ptr = ggc_alloc<term_entry> ();
+  *ptr = ent;
+  *slot = ptr;
+  return iter;
 }
 
-/* Initialize the current term to the first in the list. */
-inline void
-term_list::start ()
+/* Remove an existing term from the list. Returns an iterator referring
+   to the element after the removed term.  This may be end().  */
+
+term_list::iterator
+term_list::erase (iterator iter)
 {
-  current = begin ();
+  gcc_assert (includes (*iter));
+  term_entry ent = {*iter};
+  tab.remove_elt (&ent);
+  iter = seq.erase (iter);
+  return iter;
 }
 
-/* Advance to the next term in the list. */
-inline void
-term_list::next ()
+/* Replace the given term with that specified. If the term has
+   been previously seen, do not insert the term. Returns the
+   first iterator past the current term.  */
+
+term_list::iterator
+term_list::replace (iterator iter, tree t)
 {
-  ++current;
+  iter = erase (iter);
+  if (!includes (t))
+    insert (iter, t);
+  return iter;
 }
 
-/* Returns true when the current position is past the end. */
-inline bool
-term_list::done () const
+
+/* Replace the term at the given position by the supplied T1
+   followed by t2. This is used in certain logical operators to
+   load a list of assumptions or conclusions.  */
+
+term_list::iterator
+term_list::replace (iterator iter, tree t1, tree t2)
 {
-  return current == end ();
+  iter = erase (iter);
+  if (!includes (t1))
+    insert (iter, t1);
+  if (!includes (t2))
+    insert (iter, t2);
+  return iter;
 }
 
-
 /* A goal (or subgoal) models a sequent of the form
    'A |- C' where A and C are lists of assumptions and
    conclusions written as propositions in the constraint
-   language (i.e., lists of trees).
-*/
+   language (i.e., lists of trees). */
+
 struct proof_goal
 {
   term_list assumptions;
@@ -182,27 +230,27 @@ struct proof_goal
 /* A proof state owns a list of goals and tracks the
    current sub-goal. The class also provides facilities
    for managing subgoals and constructing term lists. */
+
 struct proof_state : std::list<proof_goal>
 {
   proof_state ();
 
   iterator branch (iterator i);
+  iterator discharge (iterator i);
 };
 
-/* An alias for proof state iterators. */
-typedef proof_state::iterator goal_iterator;
+/* Initialize the state with a single empty goal, and set that goal
+   as the current subgoal.  */
 
-/* Initialize the state with a single empty goal,
-   and set that goal as the current subgoal. */
 inline
 proof_state::proof_state ()
   : std::list<proof_goal> (1)
 { }
 
 
-/* Branch the current goal by creating a new subgoal,
-   returning a reference to // the new object. This does
-   not update the current goal. */
+/* Branch the current goal by creating a new subgoal, returning a
+   reference to the new object. This does not update the current goal. */
+
 inline proof_state::iterator
 proof_state::branch (iterator i)
 {
@@ -211,278 +259,538 @@ proof_state::branch (iterator i)
   return insert (++i, g);
 }
 
+
+/* Discharge the current goal, setting it equal to the
+   next non-satisfied goal. */
+
+inline proof_state::iterator
+proof_state::discharge (iterator i)
+{
+  gcc_assert (i != end());
+  return erase (i);
+}
+
+
 /*---------------------------------------------------------------------------
-                           Logical rules
+                        Debugging
 ---------------------------------------------------------------------------*/
 
-/*These functions modify the current state and goal by decomposing
-  logical expressions using the logical rules of sequent calculus for
-  first order logic.
+// void
+// debug (term_list& ts)
+// {
+//   for (term_list::iterator i = ts.begin(); i != ts.end(); ++i)
+//     verbatim ("  # %E", *i);
+// }
+//
+// void
+// debug (proof_goal& g)
+// {
+//   debug (g.assumptions);
+//   verbatim ("       |-");
+//   debug (g.conclusions);
+// }
 
-  Note that in each decomposition rule, the term T has been erased
-  from term list before the specific rule is applied. */
+/*---------------------------------------------------------------------------
+                        Atomicity of constraints
+---------------------------------------------------------------------------*/
 
-/* The left logical rule for conjunction adds both operands
-   to the current set of constraints. */
-void
-left_conjunction (proof_state &, goal_iterator i, tree t)
+/* Returns true if T is an atomic constraint.  */
+bool
+non_atomic_constraint_p (tree t)
 {
-  gcc_assert (TREE_CODE (t) == CONJ_CONSTR);
+  switch (TREE_CODE (t))
+    {
+    case PRED_CONSTR:
+    case EXPR_CONSTR:
+    case TYPE_CONSTR:
+    case ICONV_CONSTR:
+    case DEDUCT_CONSTR:
+    case EXCEPT_CONSTR:
+      return false;
+    case CHECK_CONSTR:
+    case PARM_CONSTR:
+    case CONJ_CONSTR:
+    case DISJ_CONSTR:
+      return true;
+    default:
+      gcc_unreachable ();
+    }
+}
 
-  /* Insert the operands into the current branch. Note that the
-     final order of insertion is left-to-right. */
-  term_list &l = i->assumptions;
-  l.insert (TREE_OPERAND (t, 1));
-  l.insert (TREE_OPERAND (t, 0));
+/* Returns true if any constraints in T are atomic.  */
+
+bool
+any_non_atomic_constraints_p (term_list& t)
+{
+  return any_p (t.begin(), t.end(), non_atomic_constraint_p);
 }
 
-/* The left logical rule for disjunction creates a new goal,
-   adding the first operand to the original set of
-   constraints and the second operand to the new set
-   of constraints. */
-void
-left_disjunction (proof_state &s, goal_iterator i, tree t)
+/*---------------------------------------------------------------------------
+                           Proof validations
+---------------------------------------------------------------------------*/
+
+enum proof_result
 {
-  gcc_assert (TREE_CODE (t) == DISJ_CONSTR);
+  invalid,
+  valid,
+  undecided
+};
+
+proof_result check_term (term_list&, tree);
 
-  /* Branch the current subgoal. */
-  goal_iterator j = s.branch (i);
-  term_list &l1 = i->assumptions;
-  term_list &l2 = j->assumptions;
 
-  /* Insert operands into the different branches. */
-  l1.insert (TREE_OPERAND (t, 0));
-  l2.insert (TREE_OPERAND (t, 1));
+proof_result
+analyze_atom (term_list& ts, tree t)
+{
+  /* FIXME: Hook into special cases, if any. */
+  /*
+  term_list::iterator iter = ts.begin();
+  term_list::iterator end = ts.end();
+  while (iter != end)
+    {
+      ++iter;
+    }
+  */
+
+  if (non_atomic_constraint_p (t))
+    return undecided;
+  if (any_non_atomic_constraints_p (ts))
+    return undecided;
+  return invalid;
 }
 
-/* The left logical rules for parameterized constraints
-   adds its operand to the current goal. The list of
-   parameters are effectively discarded. */
-void
-left_parameterized_constraint (proof_state &, goal_iterator i, tree t)
+/* Search for a pack expansion that in the list of assumptions that would
+   make this expansion valid.  */
+
+proof_result
+analyze_pack (term_list& ts, tree t)
 {
-  gcc_assert (TREE_CODE (t) == PARM_CONSTR);
-  term_list &l = i->assumptions;
-  l.insert (PARM_CONSTR_OPERAND (t));
+  tree c1 = normalize_expression (PACK_EXPANSION_PATTERN (t));
+  term_list::iterator iter = ts.begin();
+  term_list::iterator end = ts.end();
+  while (iter != end)
+    {
+      if (TREE_CODE (*iter) == TREE_CODE (t))
+        {
+          tree c2 = normalize_expression (PACK_EXPANSION_PATTERN (*iter));
+          if (prove_implication (c2, c1))
+            return valid;
+          else
+            return invalid;
+        }
+      ++iter;
+    }
+  return invalid;
 }
 
-/*---------------------------------------------------------------------------
-                           Decomposition
----------------------------------------------------------------------------*/
+/* Search for concept checks in TS that we know subsume T. */
+
+proof_result
+search_known_subsumptions (term_list& ts, tree t)
+{
+  for (term_list::iterator i = ts.begin(); i != ts.end(); ++i)
+    if (TREE_CODE (*i) == CHECK_CONSTR)
+      {
+        if (bool* b = lookup_subsumption_result (*i, t))
+          return *b ? valid : invalid;
+      }
+  return undecided;
+}
+
+/* Determine if the terms in TS provide sufficient support for proving
+   the proposition T. If any term in TS is a concept check that is known
+   to subsume T, then the proof is valid. Otherwise, we have to expand T
+   and continue searching for support.  */
 
-/* The following algorithms decompose expressions into sets of
-   atomic propositions. In terms of the sequent calculus, these
-   functions exercise the logical rules only.
+proof_result
+analyze_check (term_list& ts, tree t)
+{
+  proof_result r = search_known_subsumptions (ts, t);
+  if (r != undecided)
+    return r;
+
+  tree tmpl = CHECK_CONSTR_CONCEPT (t);
+  tree args = CHECK_CONSTR_ARGS (t);
+  tree c = expand_concept (tmpl, args);
+  return check_term (ts, c);
+}
 
-   This is equivalent, for the purpose of determining subsumption,
-   to rewriting a constraint in disjunctive normal form. It also
-   allows the resulting assumptions to be used as declarations
-   for the purpose of separate checking. */
+/* Recursively check constraints of the parameterized constraint. */
 
-/* Apply the left logical rules to the proof state. */
-void
-decompose_left_term (proof_state &s, goal_iterator i)
+proof_result
+analyze_parameterized (term_list& ts, tree t)
+{
+  return check_term (ts, PARM_CONSTR_OPERAND (t));
+}
+
+proof_result
+analyze_conjunction (term_list& ts, tree t)
+{
+  proof_result r = check_term (ts, TREE_OPERAND (t, 0));
+  if (r == invalid || r == undecided)
+    return r;
+  return check_term (ts, TREE_OPERAND (t, 1));
+}
+
+proof_result
+analyze_disjunction (term_list& ts, tree t)
+{
+  proof_result r = check_term (ts, TREE_OPERAND (t, 0));
+  if (r == valid)
+    return r;
+  return check_term (ts, TREE_OPERAND (t, 1));
+}
+
+proof_result
+analyze_term (term_list& ts, tree t)
 {
-  term_list &l = i->assumptions;
-  tree t = l.current_term ();
   switch (TREE_CODE (t))
     {
+    case CHECK_CONSTR:
+      return analyze_check (ts, t);
+
+    case PARM_CONSTR:
+      return analyze_parameterized (ts, t);
+
     case CONJ_CONSTR:
-      left_conjunction (s, i, l.erase ());
-      break;
+      return analyze_conjunction (ts, t);
     case DISJ_CONSTR:
-      left_disjunction (s, i, l.erase ());
-      break;
-    case PARM_CONSTR:
-      left_parameterized_constraint (s, i, l.erase ());
-      break;
+      return analyze_disjunction (ts, t);
+
+    case PRED_CONSTR:
+    case EXPR_CONSTR:
+    case TYPE_CONSTR:
+    case ICONV_CONSTR:
+    case DEDUCT_CONSTR:
+    case EXCEPT_CONSTR:
+      return analyze_atom (ts, t);
+
+    case EXPR_PACK_EXPANSION:
+      return analyze_pack (ts, t);
+
+    case ERROR_MARK:
+      /* Encountering an error anywhere in a constraint invalidates
+         the proof, since the constraint is ill-formed.  */
+      return invalid;
     default:
-      l.next ();
-      break;
+      gcc_unreachable ();
     }
 }
 
-/* Apply the left logical rules of the sequent calculus
-   until the current goal is fully decomposed into atomic
-   constraints. */
-void
-decompose_left_goal (proof_state &s, goal_iterator i)
+/* Check if a single term can be proven from a set of assumptions.
+   If the proof is no valid, then it is incomplete when either
+   the given term is non-atomic or any term in the list of assuumptions
+   is not-atomic.  */
+
+proof_result
+check_term (term_list& ts, tree t)
 {
-  term_list& l = i->assumptions;
-  l.start ();
-  while (!l.done ())
-    decompose_left_term (s, i);
+  /* Try the easy way; search for an equivalent term.  */
+  if (ts.includes (t))
+    return valid;
+
+  /* The hard way; actually consider what the term means.  */
+  return analyze_term (ts, t);
 }
 
-/* Apply the left logical rules of the sequent calculus
-   until the antecedents are fully decomposed into atomic
-   constraints. */
-void
-decompose_left (proof_state& s)
+/* Check to see if any term is proven by the assuumptions in the
+   proof goal. The proof is valid if the proof of any term is valid.
+   If validity cannot be determined, but there any particular
+   check was undecided than this goal is undecided.  */
+
+proof_result
+check_goal (proof_goal& g)
 {
-  goal_iterator iter = s.begin ();
-  goal_iterator end = s.end ();
-  for ( ; iter != end; ++iter)
-    decompose_left_goal (s, iter);
+  term_list::iterator iter = g.conclusions.begin ();
+  term_list::iterator end = g.conclusions.end ();
+  bool incomplete = false;
+  while (iter != end)
+    {
+      proof_result r = check_term (g.assumptions, *iter);
+      if (r == valid)
+        return r;
+      if (r == undecided)
+        incomplete = true;
+      ++iter;
+    }
+
+    /* Was the proof complete? */
+    if (incomplete)
+      return undecided;
+    else
+      return invalid;
 }
 
-/* Returns a vector of terms from the term list L. */
-tree
-extract_terms (term_list& l)
+/* Check if the the proof is valid. This is the case when all
+   goals can be discharged. If any goal is invalid, then the
+   entire proof is invalid. Otherwise, the proof is undecided.  */
+
+proof_result
+check_proof (proof_state& p)
 {
-  tree result = make_tree_vec (l.size());
-  term_list::iterator iter = l.begin();
-  term_list::iterator end = l.end();
-  for (int n = 0; iter != end; ++iter, ++n)
-    TREE_VEC_ELT (result, n) = *iter;
-  return result;
+  proof_state::iterator iter = p.begin();
+  proof_state::iterator end = p.end();
+  while (iter != end)
+    {
+      proof_result r = check_goal (*iter);
+      if (r == invalid)
+        return r;
+      if (r == valid)
+        iter = p.discharge (iter);
+      else
+        ++iter;
+    }
+
+  /* If all goals are discharged, then the proof is valid.  */
+  if (p.empty())
+    return valid;
+  else
+    return undecided;
 }
 
-/* Extract the assumptions from the proof state S
-   as a vector of vectors of atomic constraints. */
-inline tree
-extract_assumptions (proof_state& s)
+/*---------------------------------------------------------------------------
+                           Left logical rules
+---------------------------------------------------------------------------*/
+
+term_list::iterator
+load_check_assumption (term_list& ts, term_list::iterator i)
 {
-  tree result = make_tree_vec (s.size ());
-  goal_iterator iter = s.begin ();
-  goal_iterator end = s.end ();
-  for (int n = 0; iter != end; ++iter, ++n)
-    TREE_VEC_ELT (result, n) = extract_terms (iter->assumptions);
-  return result;
+  tree decl = CHECK_CONSTR_CONCEPT (*i);
+  tree tmpl = DECL_TI_TEMPLATE (decl);
+  tree args = CHECK_CONSTR_ARGS (*i);
+  return ts.replace(i, expand_concept (tmpl, args));
 }
 
-} // namespace
+term_list::iterator
+load_parameterized_assumption (term_list& ts, term_list::iterator i)
+{
+  return ts.replace(i, PARM_CONSTR_OPERAND(*i));
+}
 
-/* Decompose the required expression T into a constraint set: a
-   vector of vectors containing only atomic propositions. If T is
-   invalid, return an error. */
-tree
-decompose_assumptions (tree t)
+term_list::iterator
+load_conjunction_assumption (term_list& ts, term_list::iterator i)
 {
-  if (!t || t == error_mark_node)
-    return t;
+  tree t1 = TREE_OPERAND (*i, 0);
+  tree t2 = TREE_OPERAND (*i, 1);
+  return ts.replace(i, t1, t2);
+}
 
-  /* Create a proof state, and insert T as the sole assumption. */
-  proof_state s;
-  term_list &l = s.begin ()->assumptions;
-  l.insert (t);
+/* Examine the terms in the list, and apply left-logical rules to move
+   terms into the set of assumptions. */
 
-  /* Decompose the expression into a constraint set, and then
-     extract the terms for the AST. */
-  decompose_left (s);
-  return extract_assumptions (s);
+void
+load_assumptions (proof_goal& g)
+{
+  term_list::iterator iter = g.assumptions.begin();
+  term_list::iterator end = g.assumptions.end();
+  while (iter != end)
+    {
+      switch (TREE_CODE (*iter))
+        {
+        case CHECK_CONSTR:
+          iter = load_check_assumption (g.assumptions, iter);
+          break;
+        case PARM_CONSTR:
+          iter = load_parameterized_assumption (g.assumptions, iter);
+          break;
+        case CONJ_CONSTR:
+          iter = load_conjunction_assumption (g.assumptions, iter);
+          break;
+        default:
+          ++iter;
+          break;
+        }
+    }
 }
 
 
-/*---------------------------------------------------------------------------
-                           Subsumption Rules
----------------------------------------------------------------------------*/
+/* In each subgoal, load constraints into the assumption set.  */
 
-namespace {
+void
+load_assumptions(proof_state& p)
+{
+  proof_state::iterator iter = p.begin();
+  while (iter != p.end())
+    {
+      load_assumptions (*iter);
+      ++iter;
+    }
+}
 
-bool subsumes_constraint (tree, tree);
-bool subsumes_conjunction (tree, tree);
-bool subsumes_disjunction (tree, tree);
-bool subsumes_parameterized_constraint (tree, tree);
-bool subsumes_atomic_constraint (tree, tree);
+void
+explode_disjunction (proof_state& p, proof_state::iterator gi, term_list::iterator ti1)
+{
+  tree t1 = TREE_OPERAND (*ti1, 0);
+  tree t2 = TREE_OPERAND (*ti1, 1);
 
-/* Returns true if the assumption A matches the conclusion C. This
-   is generally the case when A and C have the same syntax.
+  /* Erase the current term from the goal. */
+  proof_goal& g1 = *gi;
+  proof_goal& g2 = *p.branch (gi);
 
-   NOTE: There will be specialized matching rules to accommodate
-   type equivalence, conversion, inheritance, etc. But this is not
-   in the current concepts draft. */
-inline bool
-match_terms (tree a, tree c)
-{
-  return cp_tree_equal (a, c);
+  /* Get an iterator to the equivalent position in th enew goal. */
+  int n = std::distance (g1.assumptions.begin (), ti1);
+  term_list::iterator ti2 = g2.assumptions.begin ();
+  std::advance (ti2, n);
+
+  /* Replace the disjunction in both branches. */
+  g1.assumptions.replace (ti1, t1);
+  g2.assumptions.replace (ti2, t2);
 }
 
-/* Returns true if the list of assumptions AS subsumes the atomic
-   proposition C. This is the case when we can find a proposition
-  in AS that entails the conclusion C. */
+
+/* Search the assumptions of the goal for the first disjunction. */
+
 bool
-subsumes_atomic_constraint (tree as, tree c)
+explode_goal (proof_state& p, proof_state::iterator gi)
 {
-  for (int i = 0; i < TREE_VEC_LENGTH (as); ++i)
-    if (match_terms (TREE_VEC_ELT (as, i), c))
-      return true;
+  term_list& ts = gi->assumptions;
+  term_list::iterator ti = ts.begin();
+  term_list::iterator end = ts.end();
+  while (ti != end)
+    {
+      if (TREE_CODE (*ti) == DISJ_CONSTR)
+        {
+          explode_disjunction (p, gi, ti);
+          return true;
+        }
+      else ++ti;
+    }
   return false;
 }
 
-/* Returns true when both operands of C are subsumed by the
-   assumptions AS. */
-inline bool
-subsumes_conjunction (tree as, tree c)
+/* Search for the first goal with a disjunction, and then branch
+   creating a clone of that subgoal. */
+
+void
+explode_assumptions(proof_state& p)
 {
-  tree l = TREE_OPERAND (c, 0);
-  tree r = TREE_OPERAND (c, 1);
-  return subsumes_constraint (as, l) && subsumes_constraint (as, r);
+  proof_state::iterator iter = p.begin();
+  proof_state::iterator end = p.end();
+  while (iter != end)
+    {
+      if (explode_goal (p, iter))
+        return;
+      ++iter;
+    }
 }
 
-/* Returns true when either operand of C is subsumed by the
-   assumptions AS. */
-inline bool
-subsumes_disjunction (tree as, tree c)
+
+/*---------------------------------------------------------------------------
+                           Right logical rules
+---------------------------------------------------------------------------*/
+
+term_list::iterator
+load_disjunction_conclusion (term_list& g, term_list::iterator i)
 {
-  tree l = TREE_OPERAND (c, 0);
-  tree r = TREE_OPERAND (c, 1);
-  return subsumes_constraint (as, l) || subsumes_constraint (as, r);
+  tree t1 = TREE_OPERAND (*i, 0);
+  tree t2 = TREE_OPERAND (*i, 1);
+  return g.replace(i, t1, t2);
 }
 
-/* Returns true when the operand of C is subsumed by the
-   assumptions in AS. The parameters are not considered in
-   the subsumption rules. */
-bool
-subsumes_parameterized_constraint (tree as, tree c)
+
+/* Apply logical rules to the right hand side. This will load the
+   conclusion set with all tpp-level disjunctions.  */
+
+void
+load_conclusions (proof_goal& g)
+{
+  term_list::iterator iter = g.conclusions.begin();
+  term_list::iterator end = g.conclusions.end();
+  while (iter != end)
+    {
+      if (TREE_CODE (*iter) == DISJ_CONSTR)
+        iter = load_disjunction_conclusion (g.conclusions, iter);
+      else
+        ++iter;
+    }
+}
+
+void
+load_conclusions(proof_state& p)
 {
-  tree t = PARM_CONSTR_OPERAND (c);
-  return subsumes_constraint (as, t);
+  proof_state::iterator iter = p.begin();
+  while (iter != p.end())
+    {
+      load_conclusions (*iter);
+      ++iter;
+    }
 }
 
 
-/* Returns true when the list of assumptions AS subsumes the
-   concluded proposition C. This is a simple recursive descent
-   on C, matching against propositions in the assumption list AS. */
+/*---------------------------------------------------------------------------
+                          High-level proof tactics
+---------------------------------------------------------------------------*/
+
+/* Given two constraints A and C, try to derive a proof that
+   A implies C.  */
+
 bool
-subsumes_constraint (tree as, tree c)
+prove_implication (tree a, tree c)
 {
-  switch (TREE_CODE (c))
+  /* Quick accept. */
+  if (cp_tree_equal (a, c))
+    return true;
+
+  /* Build the initial proof state. */
+  proof_state proof;
+  proof_goal& goal = proof.front();
+  goal.assumptions.push_back(a);
+  goal.conclusions.push_back(c);
+
+  /* Perform an initial right-expansion in the off-chance that the right
+     hand side contains disjunctions. */
+  load_conclusions (proof);
+
+  int step_max = 1 << 10;
+  int step_count = 0;              /* FIXME: We shouldn't have this. */
+  std::size_t branch_limit = 1024; /* FIXME: This nneds to be configurable. */
+  while (step_count < step_max && proof.size() < branch_limit)
     {
-    case CONJ_CONSTR:
-      return subsumes_conjunction (as, c);
-    case DISJ_CONSTR:
-      return subsumes_disjunction (as, c);
-    case PARM_CONSTR:
-      return subsumes_parameterized_constraint (as, c);
-    default:
-      return subsumes_atomic_constraint (as, c);
+      /* Determine if we can prove that the assumptions entail the
+         conclusions. If so, we're done. */
+      load_assumptions (proof);
+
+      /* Can we solve the proof based on this? */
+      proof_result r = check_proof (proof);
+      if (r != undecided)
+        return r == valid;
+
+      /* If not, then we need to dig into disjunctions.  */
+      explode_assumptions (proof);
+
+      ++step_count;
     }
+
+  if (step_count == step_max)
+    error ("subsumption failed to resolve");
+
+  if (proof.size() == branch_limit)
+    error ("exceeded maximum number of branches");
+
+  return false;
 }
 
-/* Returns true if the LEFT constraints subsume the RIGHT constraints.
-   This is done by checking that the RIGHT requirements follow from
-   each of the LEFT subgoals. */
+/* 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.  */
+
 bool
 subsumes_constraints_nonnull (tree left, tree right)
 {
   gcc_assert (check_constraint_info (left));
   gcc_assert (check_constraint_info (right));
 
-  /* Check that the required expression in RIGHT is subsumed by each
-     subgoal in the assumptions of LEFT. */
-  tree as = CI_ASSUMPTIONS (left);
-  tree c = CI_NORMALIZED_CONSTRAINTS (right);
-  for (int i = 0; i < TREE_VEC_LENGTH (as); ++i)
-    if (!subsumes_constraint (TREE_VEC_ELT (as, i), c))
-      return false;
-  return true;
+  auto_timevar time (TV_CONSTRAINT_SUB);
+  tree a = CI_ASSOCIATED_CONSTRAINTS (left);
+  tree c = CI_ASSOCIATED_CONSTRAINTS (right);
+  return prove_implication (a, c);
 }
 
 } /* namespace */
 
 /* Returns true if the LEFT constraints subsume the RIGHT
-   constraints. */
+   constraints.  */
+
 bool
 subsumes (tree left, tree right)
 {
diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c
index d1f06fdb861..afb129ae99d 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -22,6 +22,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "system.h"
 #include "coretypes.h"
 #include "cp-tree.h"
+#include "print-tree.h"
 #include "c-family/c-common.h"
 #include "timevar.h"
 #include "stringpool.h"
@@ -14691,10 +14692,13 @@ cp_parser_type_parameter (cp_parser* parser, bool *is_parameter_pack)
 	cp_parser_require (parser, CPP_GREATER, RT_GREATER);
 
         // If template requirements are present, parse them.
+	if (flag_concepts)
+          {
 	tree reqs = get_shorthand_constraints (current_template_parms);
 	if (tree r = cp_parser_requires_clause_opt (parser))
-	  reqs = conjoin_constraints (reqs, make_predicate_constraint (r));
+              reqs = conjoin_constraints (reqs, normalize_expression (r));
 	TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = reqs;
+          }
 
 	/* Look for the `class' or 'typename' keywords.  */
 	cp_parser_type_parameter_key (parser);
@@ -25704,10 +25708,13 @@ cp_parser_explicit_template_declaration (cp_parser* parser, bool member_p)
   cp_parser_skip_to_end_of_template_parameter_list (parser);
 
   /* Manage template requirements */
+  if (flag_concepts)
+  {
   tree reqs = get_shorthand_constraints (current_template_parms);
   if (tree r = cp_parser_requires_clause_opt (parser))
-    reqs = conjoin_constraints (reqs, make_predicate_constraint (r));
+      reqs = conjoin_constraints (reqs, normalize_expression (r));
   TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = reqs;
+  }
 
   cp_parser_template_declaration_after_parameters (parser, parameter_list,
 						   member_p);
@@ -37834,7 +37841,13 @@ synthesize_implicit_template_parm  (cp_parser *parser, tree constr)
       implicit template scope, and we're trying to synthesize a
       constrained parameter, try to find a previous parameter with
       the same name.  This is the same-type rule for abbreviated
-      function templates.  */
+      function templates.
+
+      NOTE: We can generate implicit parameters when tentatively
+      parsing a nested name specifier, only to reject that parse
+      later. However, matching the same template-id as part of a
+      direct-declarator should generate an identical template
+      parameter, so this rule will merge them. */
   if (parser->implicit_template_scope && constr)
     {
       tree t = parser->implicit_template_parms;
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index c5f65a7f677..fa7a85ec445 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -28,6 +28,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "system.h"
 #include "coretypes.h"
 #include "cp-tree.h"
+#include "print-tree.h"
 #include "timevar.h"
 #include "stringpool.h"
 #include "varasm.h"
@@ -179,8 +180,6 @@ static void template_parm_level_and_index (tree, int*, int*);
 static int unify_pack_expansion (tree, tree, tree,
 				 tree, unification_kind_t, bool, bool);
 static tree copy_template_args (tree);
-static tree tsubst_template_arg (tree, tree, tsubst_flags_t, tree);
-static tree tsubst_template_args (tree, tree, tsubst_flags_t, tree);
 static tree tsubst_template_parms (tree, tree, tsubst_flags_t);
 static tree most_specialized_partial_spec (tree, tsubst_flags_t);
 static tree tsubst_aggr_type (tree, tree, tsubst_flags_t, tree, int);
@@ -195,7 +194,6 @@ static tree try_class_unification (tree, tree, tree, tree, bool);
 static int coerce_template_template_parms (tree, tree, tsubst_flags_t,
 					   tree, tree);
 static bool template_template_parm_bindings_ok_p (tree, tree);
-static int template_args_equal (tree, tree);
 static void tsubst_default_arguments (tree, tsubst_flags_t);
 static tree for_each_template_parm_r (tree *, int *, void *);
 static tree copy_default_args_to_explicit_spec_1 (tree, tree);
@@ -7857,7 +7855,7 @@ coerce_innermost_template_parms (tree parms,
 
 /* Returns 1 if template args OT and NT are equivalent.  */
 
-static int
+int
 template_args_equal (tree ot, tree nt)
 {
   if (nt == ot)
@@ -8714,7 +8712,7 @@ finish_template_variable (tree var, tsubst_flags_t complain)
     {
       if (complain & tf_error)
 	{
-	  error ("constraints for %qD not satisfied", templ);
+          error ("use invalid variable template %qE", var);
 	  diagnose_constraints (location_of (var), templ, arglist);
 	}
       return error_mark_node;
@@ -10419,7 +10417,7 @@ instantiate_class_template (tree type)
   return ret;
 }
 
-static tree
+tree
 tsubst_template_arg (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 {
   tree r;
@@ -11217,7 +11215,7 @@ copy_template_args (tree t)
 
 /* Substitute ARGS into the vector or list of template arguments T.  */
 
-static tree
+tree
 tsubst_template_args (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 {
   tree orig_t = t;
@@ -12316,6 +12314,23 @@ tsubst_decl (tree t, tree args, tsubst_flags_t complain)
 
 	    if (!spec)
 	      {
+                if (evaluating_constraints_p()
+                    && VAR_P (t)
+                    && DECL_TEMPLATE_INSTANTIATED (t))
+                  {
+                    /* If the variable is already an instantiation, there are
+                       no viable substitutions.  We get here during constraint
+                       satisfaction where an expanded concept refers to a
+                       variable template, and later we later re-substitute
+                       in order to evaluate the constraint.
+
+                       FIXME: This seems to be masking a bug where the
+                       specialization lookup below fiails for a previously
+                       instantiated variable template.  */
+                    r = t;
+                    break;
+                  }
+
 		tmpl = DECL_TI_TEMPLATE (t);
 		gen_tmpl = most_general_template (tmpl);
 		argvec = tsubst (DECL_TI_ARGS (t), args, complain, in_decl);
@@ -16324,6 +16339,7 @@ tsubst_copy_and_build (tree t,
 	    --cp_unevaluated_operand;
 	    --c_inhibit_evaluation_warnings;
 	  }
+
         if (TYPE_P (op1))
 	  r = cxx_sizeof_or_alignof_type (op1, TREE_CODE (t),
 					  complain & tf_error);
@@ -17521,6 +17537,7 @@ instantiate_template_1 (tree tmpl, tree orig_args, tsubst_flags_t complain)
 	}
       return error_mark_node;
     }
+
   return fndecl;
 }
 
@@ -23742,7 +23759,10 @@ build_non_dependent_expr (tree expr)
       && cxx_dialect >= cxx11
       /* Don't do this during nsdmi parsing as it can lead to
 	 unexpected recursive instantiations.  */
-      && !parsing_nsdmi ())
+      && !parsing_nsdmi ()
+      /* Don't do this during concept expansion either and for
+         the same reason.  */
+      && !expanding_concept ())
     fold_non_dependent_expr (expr);
 
   /* Preserve OVERLOADs; the functions must be available to resolve
@@ -23880,7 +23900,7 @@ make_constrained_auto (tree con, tree args)
   else
     expr = build_concept_check (build_overload (tmpl, NULL_TREE), type, args);
 
-  tree constr = make_predicate_constraint (expr);
+  tree constr = normalize_expression (expr);
   PLACEHOLDER_TYPE_CONSTRAINTS (type) = constr;
 
   /* Our canonical type depends on the constraint.  */
@@ -24032,7 +24052,10 @@ do_auto_deduction (tree type, tree init, tree auto_node)
 /* Replace occurrences of 'auto' in TYPE with the appropriate type deduced
    from INIT.  AUTO_NODE is the TEMPLATE_TYPE_PARM used for 'auto' in TYPE.
    The CONTEXT determines the context in which auto deduction is performed
-   and is used to control error diagnostics.  */
+   and is used to control error diagnostics.
+
+   For partial-concept-ids, EXTRA_ARGS may be appended to the list of
+   deduced template prior to determining constraint satisfaction.  */
 
 tree
 do_auto_deduction (tree type, tree init, tree auto_node,
@@ -24139,8 +24162,19 @@ do_auto_deduction (tree type, tree init, tree auto_node,
   if (flag_concepts && !processing_template_decl)
     if (tree constr = PLACEHOLDER_TYPE_CONSTRAINTS (auto_node))
       {
-        /* Use the deduced type to check the associated constraints. */
-        if (!constraints_satisfied_p (constr, targs))
+        /* Use the deduced type to check the associated constraints. If we
+           have a partial-concept-id, rebuild the argument list so that
+           we check using the extra arguments. */
+        gcc_assert (TREE_CODE (constr) == CHECK_CONSTR);
+        tree cargs = CHECK_CONSTR_ARGS (constr);
+        if (TREE_VEC_LENGTH (cargs) > 1)
+          {
+            cargs = copy_node (cargs);
+            TREE_VEC_ELT (cargs, 0) = TREE_VEC_ELT (targs, 0);
+          }
+        else
+          cargs = targs;
+        if (!constraints_satisfied_p (constr, cargs))
           {
             if (complain & tf_warning_or_error)
               {
@@ -24525,14 +24559,346 @@ remove_constraints (tree t)
     decl_constraints->clear_slot (slot);
 }
 
+/* Momoized satisfaction results for declarations. This associates
+   maps the pair (constraint, arguments) to the result computed
+   by constraints_satisfied_p.  */
+
+struct GTY((for_user)) constraint_sat_entry
+{
+  tree ci;
+  tree args;
+  tree result;
+};
+
+/* Hashing function and equality for constraint entries. */
+
+struct constraint_sat_hasher : ggc_ptr_hash<constraint_sat_entry>
+{
+  static hashval_t hash (constraint_sat_entry *e)
+  {
+    hashval_t val = iterative_hash_object(e->ci, 0);
+    return iterative_hash_template_arg (e->args, val);
+  }
+
+  static bool equal (constraint_sat_entry *e1, constraint_sat_entry *e2)
+  {
+    return e1->ci == e2->ci && comp_template_args (e1->args, e2->args);
+  }
+};
+
+/* Adjusted hash function for concept arguments. This guarantees
+   that pack selections of different indexes into the same pack
+   yield (likely) different hash values.  */
+
+hashval_t
+iterative_hash_concept_arg (tree arg, hashval_t val)
+{
+  if (arg == NULL_TREE)
+    return iterative_hash_object (arg, val);
+
+  if (!TYPE_P (arg))
+    STRIP_NOPS (arg);
+
+  if (TREE_CODE (arg) == TREE_VEC)
+    {
+      /* Recurse on template arguments. */
+      for (int i = 0; i < TREE_VEC_LENGTH (arg); ++i)
+        val = iterative_hash_concept_arg (TREE_VEC_ELT (arg, i), val);
+      return val;
+    }
+
+  if (TREE_CODE (arg) == ARGUMENT_PACK_SELECT)
+    {
+      /* We can get these when checking the satisfaction of constraints
+         during pack expansion. Hash over both the pack and index.  */
+      tree pack = ARGUMENT_PACK_SELECT_FROM_PACK (arg);
+      int index = ARGUMENT_PACK_SELECT_INDEX (arg);
+      val = iterative_hash_template_arg (pack, val);
+      val = iterative_hash_object (index, val);
+      return val;
+    }
+
+  return iterative_hash_template_arg (arg, val);
+}
+
+
+/* Adjusted hash function for concept checks. */
+
+static hashval_t
+hash_concept_and_args (tree tmpl, tree args)
+{
+  hashval_t val = iterative_hash_object (DECL_UID (tmpl), 0);
+  return iterative_hash_concept_arg (args, val);
+}
+
+/* Returns true if concept arguments are equal.  */
+static bool
+concept_args_equal (tree t1, tree t2)
+{
+  if (t1 == t2)
+    return true;
+
+  if (!t1 || !t2)
+    return false;
+
+  /* Argument pack selections are equivalent only when the select
+     the same index from equivalent packs.  */
+  if (TREE_CODE (t1) == ARGUMENT_PACK_SELECT)
+    if (t2 && TREE_CODE (t2) == ARGUMENT_PACK_SELECT)
+      {
+        tree p1 = ARGUMENT_PACK_SELECT_FROM_PACK (t1);
+        tree p2 = ARGUMENT_PACK_SELECT_FROM_PACK (t2);
+        int n1 = ARGUMENT_PACK_SELECT_INDEX (t1);
+        int n2 = ARGUMENT_PACK_SELECT_INDEX (t2);
+        return n1 == n2 && template_args_equal (p1, p2);
+      }
+
+  return template_args_equal (t1, t2);
+}
+
+/* Adjusted comparison of concept arguments. This guarantees that
+   argument pack selections are equivalent only when they select the
+   same element.  */
+
+static bool
+comp_concept_args (tree a1, tree a2)
+{
+  if (a1 == a2)
+    return true;
+
+  if (!a1 || !a2)
+    return false;
+
+  if (TREE_VEC_LENGTH (a1) != TREE_VEC_LENGTH (a2))
+    return false;
+
+  for (int i = 0; i < TREE_VEC_LENGTH (a1); ++i)
+    {
+      tree t1 = TREE_VEC_ELT (a1, i);
+      tree t2 = TREE_VEC_ELT (a2, i);
+      if (!concept_args_equal (t1, t2))
+        return false;
+    }
+  return true;
+}
+
+/* Memoized satisfaction results for concept checks. */
+
+struct GTY((for_user)) concept_spec_entry
+{
+  tree tmpl;
+  tree args;
+  tree result;
+};
+
+/* Hashing function and equality for constraint entries.  */
+
+struct concept_spec_hasher : ggc_ptr_hash<concept_spec_entry>
+{
+  static hashval_t hash (concept_spec_entry *e)
+  {
+    return hash_concept_and_args (e->tmpl, e->args);
+  }
+
+  static bool equal (concept_spec_entry *e1, concept_spec_entry *e2)
+  {
+    ++comparing_specializations;
+    bool eq = e1->tmpl == e2->tmpl && comp_concept_args (e1->args, e2->args);
+    --comparing_specializations;
+    return eq;
+  }
+};
+
+static GTY (()) hash_table<constraint_sat_hasher> *constraint_memos;
+static GTY (()) hash_table<concept_spec_hasher> *concept_memos;
+
+/* Search for a memoized satisfaction results. Returns one of the
+   truth value nodes if previously memoized,and NULL_TREE otherwise.   */
+
+tree
+lookup_constraint_satisfaction (tree, tree)
+{
+  return NULL_TREE;
+  /*
+  constraint_sat_entry elt = { ci, args, NULL_TREE };
+  constraint_sat_entry* found = constraint_memos->find (&elt);
+  if (found)
+    return found->result;
+  else
+    return NULL_TREE;
+  */
+}
+
+/* Memoize the result of a satisfication test. Returns the saved result.  */
+
+tree
+memoize_constraint_satisfaction (tree, tree, tree result)
+{
+  return result;
+  /*
+  constraint_sat_entry elt = {ci, args, result};
+  constraint_sat_entry** slot = constraint_memos->find_slot (&elt, INSERT);
+  constraint_sat_entry* entry = ggc_alloc<constraint_sat_entry> ();
+  *entry = elt;
+  *slot = entry;
+  return result;
+  */
+}
+
+/* Search for a memoized satisfaction result for a concept. */
+
+tree
+lookup_concept_satisfaction (tree tmpl, tree args)
+{
+  concept_spec_entry elt = { tmpl, args, NULL_TREE };
+  concept_spec_entry* found = concept_memos->find (&elt);
+  if (found)
+    return found->result;
+  else
+    return NULL_TREE;
+}
+
+/* Memoize the result of a concept check. Returns the saved result.  */
+
+tree
+memoize_concept_satisfaction (tree tmpl, tree args, tree result)
+{
+  concept_spec_entry elt = {tmpl, args, result};
+  concept_spec_entry** slot = concept_memos->find_slot (&elt, INSERT);
+  concept_spec_entry* entry = ggc_alloc<concept_spec_entry> ();
+  *entry = elt;
+  *slot = entry;
+  return result;
+}
+
+static GTY (()) hash_table<concept_spec_hasher> *concept_expansions;
+
+/* Returns a prior concept specialization. This returns the substituted
+   and normalized constraints defined by the concept.  */
+
+tree
+get_concept_expansion (tree tmpl, tree args)
+{
+  concept_spec_entry elt = { tmpl, args, NULL_TREE };
+  concept_spec_entry* found = concept_expansions->find (&elt);
+  if (found)
+    return found->result;
+  else
+    return NULL_TREE;
+}
+
+/* Save a concept expansion for later.  */
+
+tree
+save_concept_expansion (tree tmpl, tree args, tree def)
+{
+  concept_spec_entry elt = {tmpl, args, def};
+  concept_spec_entry** slot = concept_expansions->find_slot (&elt, INSERT);
+  concept_spec_entry* entry = ggc_alloc<concept_spec_entry> ();
+  *entry = elt;
+  *slot = entry;
+  return def;
+}
+
+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_concept_arg (CHECK_CONSTR_ARGS (t1), val);
+  val = iterative_hash_object (CHECK_CONSTR_CONCEPT (t2), val);
+  val = iterative_hash_concept_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_concept_args (CHECK_CONSTR_ARGS (left1),
+                             CHECK_CONSTR_ARGS (right1)))
+        return comp_concept_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<subsumption_entry>
+{
+  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_hasher> *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<subsumption_entry> ();
+  *entry = elt;
+  *slot = entry;
+  return result;
+}
+
 /* Set up the hash table for constraint association. */
 
 void
 init_constraint_processing (void)
 {
   decl_constraints = hash_table<constr_hasher>::create_ggc(37);
+  constraint_memos = hash_table<constraint_sat_hasher>::create_ggc(37);
+  concept_memos = hash_table<concept_spec_hasher>::create_ggc(37);
+  concept_expansions = hash_table<concept_spec_hasher>::create_ggc(37);
+  subsumption_table = hash_table<subsumption_hasher>::create_ggc(37);
 }
 
+
 /* Set up the hash tables for template instantiations.  */
 
 void
diff --git a/gcc/cp/tree.c b/gcc/cp/tree.c
index 6010f63746f..a4986006482 100644
--- a/gcc/cp/tree.c
+++ b/gcc/cp/tree.c
@@ -3172,6 +3172,11 @@ cp_tree_equal (tree t1, tree t2)
       return cp_tree_equal (CI_ASSOCIATED_CONSTRAINTS (t1),
                             CI_ASSOCIATED_CONSTRAINTS (t2));
 
+    case CHECK_CONSTR:
+      return (CHECK_CONSTR_CONCEPT (t1) == CHECK_CONSTR_CONCEPT (t2)
+              && cp_tree_equal (CHECK_CONSTR_CONCEPT (t1),
+                                CHECK_CONSTR_CONCEPT (t2)));
+
     case TREE_VEC:
       {
 	unsigned ix;
diff --git a/gcc/testsuite/g++.dg/concepts/diagnostic1.C b/gcc/testsuite/g++.dg/concepts/diagnostic1.C
index aa98ffa752a..0552c4b0623 100644
--- a/gcc/testsuite/g++.dg/concepts/diagnostic1.C
+++ b/gcc/testsuite/g++.dg/concepts/diagnostic1.C
@@ -1,16 +1,30 @@
 // PR c++/67159
 // { dg-options "-std=c++1z -fconcepts" }
 
+template <class T, class U>
+concept bool SameAs = __is_same_as(T, U);
+
 template <class T>
-concept bool R = requires (T& t) {
+concept bool R1 = requires (T& t) {
   { t.begin() } -> T
+  { t.end() } -> SameAs<T*>;
+};
+
+template <class T>
+concept bool R2 = requires (T& t) {
+  { t.end() } -> SameAs<T*>;
 };
 
 struct foo {
   int* begin();
+  int* end();
 };
 
-R{T}
+R1{T}
 constexpr bool f() { return true; }
 
+R2{T}
+constexpr bool g() { return true; }
+
 static_assert(f<foo>());	// { dg-error "" }
+static_assert(g<foo>());	// { dg-error "" }
diff --git a/gcc/testsuite/g++.dg/concepts/dr1430.C b/gcc/testsuite/g++.dg/concepts/dr1430.C
index 3a7ba0363b1..178467a1691 100644
--- a/gcc/testsuite/g++.dg/concepts/dr1430.C
+++ b/gcc/testsuite/g++.dg/concepts/dr1430.C
@@ -24,11 +24,19 @@ template <typename T, typename U, typename... Args>
     return decltype(check<T, U, Args...>())::value;
   }
 
+template <typename T, typename U, typename... Args>
+  concept bool Similar = true;
+
 template <typename... Args>
-requires Same<Args...>()	// { dg-error "concept" }
+requires Same<Args...>() // { dg-error "invalid reference" }
   void foo( Args... args ) {}
 
+template <typename... Args>
+requires Similar<Args...> // { dg-error "invalid reference" }
+  void bar( Args... args ) {}
+
 int main()
 {
-  foo(1, 2, 3);			// { dg-error "" }
+  foo(1, 2, 3); // { dg-error "cannot call" }
+  bar(1, 2, 3); // { dg-error "cannot call" }
 }
diff --git a/gcc/testsuite/g++.dg/concepts/expression2.C b/gcc/testsuite/g++.dg/concepts/expression2.C
index ebdadc231f3..1c2db4e4bfb 100644
--- a/gcc/testsuite/g++.dg/concepts/expression2.C
+++ b/gcc/testsuite/g++.dg/concepts/expression2.C
@@ -31,12 +31,12 @@ class S
 int main()
 {
   f1(s); // { dg-error "cannot call" }
-  f2(s); // { dg-error "cannot call" }
+  f2(s); // { dg-error "" "" { xfail *-*-* } }
 
   // When used in non-SFINAE contexts, make sure that we fail
   // the constraint check before emitting the access check
   // failures. The context is being presented constistently
   // in both cases.
   static_assert(C1<S>(), ""); // { dg-error "failed" }
-  static_assert(C2<S>(), ""); // { dg-error "failed" }
+  static_assert(C2<S>(), ""); // { dg-error "" "" { xfail *-*-* } }
 }
diff --git a/gcc/testsuite/g++.dg/concepts/req4.C b/gcc/testsuite/g++.dg/concepts/req4.C
index e7e71a47bd2..2bd5f1552f9 100644
--- a/gcc/testsuite/g++.dg/concepts/req4.C
+++ b/gcc/testsuite/g++.dg/concepts/req4.C
@@ -9,10 +9,10 @@ template<typename T> constexpr fool p1() { return {}; }
 template<typename T> constexpr fool p2() { return {}; }
 
 template<typename T>
-  concept bool C() { return p1<T>() && p2<T>(); } // { dg-error "does not have type" }
+  concept bool C() { return p1<T>() && p2<T>(); }
 
 template<C T> void f(T x) { }
 
 int main() {
-  f(0); // { dg-error "cannot call" }
+  f(0); // { dg-error "cannot call|uses overloaded operator" }
 }
diff --git a/gcc/testsuite/g++.dg/concepts/req5.C b/gcc/testsuite/g++.dg/concepts/req5.C
index 17db0dd6abc..7953869360f 100644
--- a/gcc/testsuite/g++.dg/concepts/req5.C
+++ b/gcc/testsuite/g++.dg/concepts/req5.C
@@ -9,10 +9,10 @@ template<typename T> constexpr fool p1() { return {}; }
 template<typename T> constexpr fool p2() { return {}; }
 
 template<typename T>
-  concept bool C() { return p1<T>() && p2<T>(); } // { dg-error "does not have type" }
+  concept bool C() { return p1<T>() && p2<T>(); }
 
 template<C T> void f(T x) { }
 
 int main() {
-  f(0); // { dg-error "cannot call" }
+  f(0); // { dg-error "cannot call|uses overloaded operator" }
 }
diff --git a/gcc/testsuite/g++.dg/concepts/req6.C b/gcc/testsuite/g++.dg/concepts/req6.C
index e8e94c02ff2..6e111b260ac 100644
--- a/gcc/testsuite/g++.dg/concepts/req6.C
+++ b/gcc/testsuite/g++.dg/concepts/req6.C
@@ -7,7 +7,12 @@ template<typename T>
   concept bool C1() { return X(); }
 
 template<C1 T>
-  void h(T) { } // { dg-error "not|bool" }
+  void h(T) { } // OK until used.
+
+void f()
+{
+  h(0); // { dg-error "does not have|cannot call" }
+}
 
 template<typename T>
   concept bool C2() { return X() == X(); } // OK
diff --git a/gcc/testsuite/g++.dg/concepts/var-templ1.C b/gcc/testsuite/g++.dg/concepts/var-templ1.C
index 7dfa2400d3c..99ffdc0a483 100644
--- a/gcc/testsuite/g++.dg/concepts/var-templ1.C
+++ b/gcc/testsuite/g++.dg/concepts/var-templ1.C
@@ -13,4 +13,4 @@ template <class T>
 constexpr bool f() { return false; }
 
 static_assert(f<void>());
-static_assert(v<void>);		// { dg-error "constraints" }
+static_assert(v<void>);		// { dg-error "invalid" }
diff --git a/gcc/testsuite/g++.dg/concepts/variadic2.C b/gcc/testsuite/g++.dg/concepts/variadic2.C
index f7aa7108480..e60e9ff4013 100644
--- a/gcc/testsuite/g++.dg/concepts/variadic2.C
+++ b/gcc/testsuite/g++.dg/concepts/variadic2.C
@@ -4,10 +4,13 @@ template <class T> concept bool Copyable = requires (T t) { T(t); };
 template <class T> concept bool Constructable = requires { T(); };
 template <class T> concept bool Both = Copyable<T> && Constructable<T>;
 
-template <Copyable... Ts> void f(Ts...) { }
-template <Both... Ts> void f(Ts...) { }
+template <Copyable... Ts>
+constexpr int f(Ts...) { return 0; } // #1
+
+template <Both... Ts>
+constexpr int f(Ts...) { return 1; }     // #2
 
 int main()
 {
-  f(42);
+  static_assert(f(42) == 1);
 }
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 362aa6e4247..5f121182e14 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -137,6 +137,8 @@ DEFTIMEVAR (TV_PARSE_FUNC            , "parser function body")
 DEFTIMEVAR (TV_PARSE_INLINE          , "parser inl. func. body")
 DEFTIMEVAR (TV_PARSE_INMETH          , "parser inl. meth. body")
 DEFTIMEVAR (TV_TEMPLATE_INST         , "template instantiation")
+DEFTIMEVAR (TV_CONSTRAINT_SAT        , "constraint satisfaction")
+DEFTIMEVAR (TV_CONSTRAINT_SUB        , "constraint subsumption")
 DEFTIMEVAR (TV_FLATTEN_INLINING      , "flatten inlining")
 DEFTIMEVAR (TV_EARLY_INLINING        , "early inlining heuristics")
 DEFTIMEVAR (TV_INLINE_PARAMETERS     , "inline parameters")
diff --git a/gcc/timevar.h b/gcc/timevar.h
index 709770053f7..34653044d65 100644
--- a/gcc/timevar.h
+++ b/gcc/timevar.h
@@ -229,6 +229,14 @@ class auto_timevar
       m_timer->push (m_tv);
   }
 
+  explicit auto_timevar (timevar_id_t tv)
+    : m_timer (g_timer)
+    , m_tv (tv)
+  {
+    if (m_timer)
+      m_timer->push (m_tv);
+  }
+
   ~auto_timevar ()
   {
     if (m_timer)