Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]

[Patrick Palka <ppalka@redhat.com>]

On Fri, 29 Oct 2021, Jakub Jelinek wrote:

> On Thu, Oct 28, 2021 at 03:35:20PM -0400, Patrick Palka wrote:
> > > Is there a reason to turn this mode of evaluating everything twice if an
> > > error should be diagnosed all the time, rather than only if we actually see
> > > a TRUTH_*_EXPR we want to handle this way?
> > > If we don't see any TRUTH_*_EXPR, or if processing_template_decl, or if
> > > the first operand is already a constant, that seems like a waste of time.
> > 
> > Hmm yeah, at the very least it wouldn't hurt to check
> > processing_template_decl before doing the tf_error shenanigans.  I'm not
> > sure if we would gain anything by first looking for TRUTH_*_EXPR since
> > that'd involve walking the entire expression anyway IIUC.
> 
> I meant actually something like:
> --- gcc/cp/constexpr.c.jj	2021-10-28 20:07:48.566193259 +0200
> +++ gcc/cp/constexpr.c	2021-10-29 13:47:48.824026156 +0200
> @@ -8789,7 +8789,7 @@ potential_constant_expression_1 (tree t,
>  	      return false;
>  	    }
>  	  else if (!check_for_uninitialized_const_var
> -		   (tmp, /*constexpr_context_p=*/true, flags))
> +		   (tmp, /*constexpr_context_p=*/true, flags & ~(1 << 30)))
>  	    return false;
>  	}
>        return RECUR (tmp, want_rval);
> @@ -8896,14 +8896,36 @@ potential_constant_expression_1 (tree t,
>  	tree op1 = TREE_OPERAND (t, 1);
>  	if (!RECUR (op0, rval))
>  	  return false;
> -	if (!(flags & tf_error) && RECUR (op1, rval))
> -	  /* When quiet, try to avoid expensive trial evaluation by first
> -	     checking potentiality of the second operand.  */
> -	  return true;
> -	if (!processing_template_decl)
> -	  op0 = cxx_eval_outermost_constant_expr (op0, true);
> +	if (TREE_CODE (op0) != INTEGER_CST && !processing_template_decl)
> +	  {
> +	    /* If op0 is not a constant, we can either
> +	       cxx_eval_outermost_constant_expr first, or RECUR (op1, rval)
> +	       first.  If quiet, perform the latter first, if not quiet
> +	       and it is the outermost such TRUTH_*_EXPR, perform the
> +	       latter first in quiet mode, followed by the former and
> +	       retry with the latter in non-quiet mode.  */
> +	    if ((flags & (1 << 30)) != 0)
> +	      op0 = cxx_eval_outermost_constant_expr (op0, true);
> +	    else if ((flags & tf_error) != 0)
> +	      {
> +		flags &= ~tf_error;
> +		if (RECUR (op1, rval))
> +		  return true;
> +		op0 = cxx_eval_outermost_constant_expr (op0, true);
> +		flags |= tf_error | (1 << 30);
> +	      }
> +	    else
> +	      {
> +		if (RECUR (op1, rval))
> +		  return true;
> +		op0 = cxx_eval_outermost_constant_expr (op0, true);
> +		if (tree_int_cst_equal (op0, tmp))
> +		  return false;
> +		return true;
> +	      }
> +	  }
>  	if (tree_int_cst_equal (op0, tmp))
> -	  return (flags & tf_error) ? RECUR (op1, rval) : false;
> +	  return RECUR (op1, rval);
>  	else
>  	  return true;
>        }
> @@ -9112,17 +9134,6 @@ bool
>  potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
>  				 tsubst_flags_t flags)
>  {
> -  if (flags & tf_error)
> -    {
> -      /* Check potentiality quietly first, as that could be performed more
> -	 efficiently in some cases (currently only for TRUTH_*_EXPR).  If
> -	 that fails, replay the check noisily to give errors.  */
> -      flags &= ~tf_error;
> -      if (potential_constant_expression_1 (t, want_rval, strict, now, flags))
> -	return true;
> -      flags |= tf_error;
> -    }
> -
>    tree target = NULL_TREE;
>    return potential_constant_expression_1 (t, want_rval, strict, now,
>  					  flags, &target);
> 
> (perhaps with naming the 1 << 30 as tf_something or using different bit for
> that).  So no doubling of potential_constant_expression_1 evaluation
> for tf_error unless a TRUTH_*_EXPR is seen outside of template with
> potentially constant first operand other than INTEGER_CST, but similarly to
> what you did, make sure that there are at most two calls and not more.

That makes sense, though it's somewhat unfortunate that we'd have to
use/add an adhoc tsubst_flags_t flag with this approach :/

> 
> > > As I said, another possibility is something like:
> > > /* Try to quietly evaluate T to constant, but don't try too hard.  */
> > > 
> > > static tree
> > > potential_constant_expression_eval (tree t)
> > > {
> > >   auto o = make_temp_override (constexpr_ops_limit,
> > > 			       MIN (constexpr_ops_limit, 100));
> > >   return cxx_eval_outermost_constant_expr (t, true);
> > > }
> > > and using this new function instead of cxx_eval_outermost_constant_expr (op, true);
> > > everywhere in potential_constant_expression_1 should fix the quadraticness
> > > too.
> > 
> > This would technically fix the quadraticness but wouldn't it still mean
> > that a huge left-associated constant logical expression is quite a bit
> > slower to check than an equivalent right-associated one (depending on
> > what we set constexpr_ops_limit to)?  We should probably do this anyway
> > anyway but it doesn't seem sufficient on its own to make equivalent
> > left/right-associated logical expressions have the same performance
> > behavior IMHO.
> 
> The most expensive would be
> #define TEN true && true && true && true && true && true && true && true && true && true &&
> TEN TEN TEN TEN TEN false
> or something similar because if any of the && expressions (other than the
> last one) are more expensive to constant evaluate, it would just mean it
> would stop the quadratic behavior earlier.

Ah yeah, I see what you mean.

> 
> Though, of course this isn't either or, the potential_constant_expression_eval
> could be mixed either with your current version, or the one adjusted by
> the above untested patch, or by reversion of all the changes + linearization
> into a vector.

What do you think about combining your linearization idea with checking
potentiality of each term before resorting to trial evaluation?  The
most concise/efficient way of implementing this seems to be using a
recursive lambda that simultaneously linearizes and checks for
potentiality (and stops at the first non potentially constant term):

-- >8 --

gcc/cp/ChangeLog:

	* constexpr.c (potential_constant_expression_1) [RECUR_QUIETLY]:
	Define.
	<case TRUTH_*_EXPR>: Reimplement by linearizing all terms of the
	con/disjunction while continuing to check potentiality of each term
	before resorting to trial evaluation.
	(potential_constant_expression_1): Don't mess with tf_error.
---
 gcc/cp/constexpr.c | 74 +++++++++++++++++++++++++++++-----------------
 1 file changed, 47 insertions(+), 27 deletions(-)

diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 40fe165c2b7..7855443cdf6 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -8055,6 +8055,9 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
 {
 #define RECUR(T,RV) \
   potential_constant_expression_1 ((T), (RV), strict, now, flags, jump_target)
+#define RECUR_QUIETLY(T,RV) \
+  potential_constant_expression_1 ((T), (RV), strict, now, flags & ~tf_error, \
+				   jump_target)
 
   enum { any = false, rval = true };
   int i;
@@ -8885,27 +8888,55 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
 	 potentiality.  */
     case TRUTH_AND_EXPR:
     case TRUTH_ANDIF_EXPR:
-      tmp = boolean_true_node;
-      goto truth;
     case TRUTH_OR_EXPR:
     case TRUTH_ORIF_EXPR:
-      tmp = boolean_false_node;
-    truth:
       {
-	tree op0 = TREE_OPERAND (t, 0);
-	tree op1 = TREE_OPERAND (t, 1);
-	if (!RECUR (op0, rval))
-	  return false;
-	if (!(flags & tf_error) && RECUR (op1, rval))
-	  /* When quiet, try to avoid expensive trial evaluation by first
-	     checking potentiality of the second operand.  */
+	auto normalize_code = [] (tree_code c) -> tree_code {
+	  if (c == TRUTH_ANDIF_EXPR)
+	    c = TRUTH_AND_EXPR;
+	  else if (c == TRUTH_ORIF_EXPR)
+	    c = TRUTH_OR_EXPR;
+	  return c;
+	};
+	auto_vec<tree, 4> terms;
+	/* A recursive lambda that collects the terms of the con/disjunction
+	   R into the vector TERMS, stopping at the first term that isn't
+	   potentially constant.  Returns true iff all terms are potentially
+	   constant.  */
+	auto checked_linearize = [&] (tree r, auto& self) -> bool {
+	  if (normalize_code (TREE_CODE (r)) == normalize_code (TREE_CODE (t)))
+	    return self (TREE_OPERAND (r, 0), self)
+	      && self (TREE_OPERAND (r, 1), self);
+	  else
+	    {
+	      terms.safe_push (r);
+	      return RECUR_QUIETLY (r, rval);
+	    }
+	};
+	/* If all terms of T are potentially constant, then so is T.  */
+	if (checked_linearize (t, checked_linearize))
 	  return true;
-	if (!processing_template_decl)
-	  op0 = cxx_eval_outermost_constant_expr (op0, true);
-	if (tree_int_cst_equal (op0, tmp))
-	  return (flags & tf_error) ? RECUR (op1, rval) : false;
+	tree last_term = terms.pop ();
+	/* Otherwise, if trial evaluation of a potentially constant term
+	   yields something other than the non-short-circuit constant, then
+	   we must conservatively return true.  */
+	tree nsc_cst;
+	if (normalize_code (TREE_CODE (t)) == TRUTH_AND_EXPR)
+	  nsc_cst = boolean_true_node;
 	else
-	  return true;
+	  nsc_cst = boolean_false_node;
+	for (tree term : terms)
+	  {
+	    if (!processing_template_decl)
+	      term = cxx_eval_outermost_constant_expr (term, true);
+	    if (!tree_int_cst_equal (term, nsc_cst))
+	      return true;
+	  }
+	/* Otherwise, diagnose non-potentiality of the last term and return
+	   false.  */
+	if (flags & tf_error)
+	  RECUR (last_term, rval);
+	return false;
       }
 
     case PLUS_EXPR:
@@ -9112,17 +9143,6 @@ bool
 potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
 				 tsubst_flags_t flags)
 {
-  if (flags & tf_error)
-    {
-      /* Check potentiality quietly first, as that could be performed more
-	 efficiently in some cases (currently only for TRUTH_*_EXPR).  If
-	 that fails, replay the check noisily to give errors.  */
-      flags &= ~tf_error;
-      if (potential_constant_expression_1 (t, want_rval, strict, now, flags))
-	return true;
-      flags |= tf_error;
-    }
-
   tree target = NULL_TREE;
   return potential_constant_expression_1 (t, want_rval, strict, now,
 					  flags, &target);
-- 
2.34.0.rc0