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

Patrick Palka ppalka@redhat.com
Mon Nov 1 19:08:58 GMT 2021


On Mon, 1 Nov 2021, Patrick Palka wrote:

> 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 {

Whoops, I forgot that auto lambda parms are C++14 not C++11, so that
essentially rules out using recursive lambdas.  I guess using an ordinary
recursive function instead would make interleaving linearization with
checking for potentiality too messy due to all the state we'd have to
explicitly pass around.  But we could just perform those two separately
instead (at the cost of another loop over 'terms'), if we were to go
with this kind of approach.

> +	  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
> 
> 



More information about the Gcc-patches mailing list