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

  In the testcase below the two left fold expressions each expand into a
logical expression with 1024 terms, for which potential_const_expr_1
takes more than a minute to return true.  This is because p_c_e_1
performs trial evaluation of the first operand of a &&/|| in order to
determine whether to consider its second operand.  And because the
expanded expression is left-associated, this trial evaluation causes
p_c_e_1 to be quadratic in the number of terms of the expression.

This patch fixes this quadratic behavior by making p_c_e_1 recurse only
into the first operand of a &&/|| when checking for potentiality.  This
means we'll consider more non-constant expressions as potentially
constant compared to the trial evaluation approach, but that should be
harmless as later constexpr evaluation of the expression will deem it
non-constant anyway.

As a nice bonus, this change also reduces compile time for the libstdc++
testcase 20_util/variant/87619.cc by about 15%, even though our <variant>
uses right folds instead of left folds.  Likewise for the testcase in
the PR, for which compile time is reduced by 30%.

Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for
trunk?

	PR c++/102780

gcc/cp/ChangeLog:

	* constexpr.c (potential_constant_expression_1) <case TRUTH_*_EXPR>:
	Only recurse into the first operand, and ignore the second.

gcc/testsuite/ChangeLog:

	* g++.dg/cpp1z/fold13.C: New test.
---
 gcc/cp/constexpr.c                  | 21 +++------------------
 gcc/testsuite/g++.dg/cpp1z/fold13.C | 29 +++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+), 18 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/cpp1z/fold13.C
  

On Tue, Oct 26, 2021 at 01:44:18PM -0400, Patrick Palka via Gcc-patches wrote:
> In the testcase below the two left fold expressions each expand into a
> logical expression with 1024 terms, for which potential_const_expr_1
> takes more than a minute to return true.  This is because p_c_e_1
> performs trial evaluation of the first operand of a &&/|| in order to
> determine whether to consider its second operand.  And because the
> expanded expression is left-associated, this trial evaluation causes
> p_c_e_1 to be quadratic in the number of terms of the expression.
> 
> This patch fixes this quadratic behavior by making p_c_e_1 recurse only
> into the first operand of a &&/|| when checking for potentiality.  This
> means we'll consider more non-constant expressions as potentially
> constant compared to the trial evaluation approach, but that should be
> harmless as later constexpr evaluation of the expression will deem it
> non-constant anyway.

For very large && or || expressions (but not mixed or with ! etc.) another
possibility would be to check if the lhs or rhs have the same code and if
so, linearize the trees and recurse only on the leafs (trees with other
TREE_CODE) and stop when first expression isn't equal to tmp.
For mixed &&/|| or with ! that could still be expensive though.

	Jakub
  

On Tue, Oct 26, 2021 at 2:46 PM Jakub Jelinek via Gcc-patches <
gcc-patches@gcc.gnu.org> wrote:

> On Tue, Oct 26, 2021 at 01:44:18PM -0400, Patrick Palka via Gcc-patches
> wrote:
> > In the testcase below the two left fold expressions each expand into a
> > logical expression with 1024 terms, for which potential_const_expr_1
> > takes more than a minute to return true.  This is because p_c_e_1
> > performs trial evaluation of the first operand of a &&/|| in order to
> > determine whether to consider its second operand.  And because the
> > expanded expression is left-associated, this trial evaluation causes
> > p_c_e_1 to be quadratic in the number of terms of the expression.
> >
> > This patch fixes this quadratic behavior by making p_c_e_1 recurse only
> > into the first operand of a &&/|| when checking for potentiality.  This
> > means we'll consider more non-constant expressions as potentially
> > constant compared to the trial evaluation approach, but that should be
> > harmless as later constexpr evaluation of the expression will deem it
> > non-constant anyway.
>

Fair, especially now that it seems that C++23 is removing the diagnostic
for a constexpr function that can't produce a constant expression.  And as
more functions become constexpr, the trial evaluation gets more expensive
to get to the point of failure.  I wonder if we want to stop calling
cxx_eval_outermost_constant_expression from pot_c_e_1 entirely, only check
whether the operand is already constant.

For very large && or || expressions (but not mixed or with ! etc.) another
> possibility would be to check if the lhs or rhs have the same code and if
> so, linearize the trees and recurse only on the leafs (trees with other
> TREE_CODE) and stop when first expression isn't equal to tmp.
>

This would be good if we wanted to keep the evaluation.

Jason
  

On Tue, Oct 26, 2021 at 03:29:02PM -0400, Jason Merrill wrote:
> On Tue, Oct 26, 2021 at 2:46 PM Jakub Jelinek via Gcc-patches <
> gcc-patches@gcc.gnu.org> wrote:
> 
> > On Tue, Oct 26, 2021 at 01:44:18PM -0400, Patrick Palka via Gcc-patches
> > wrote:
> > > In the testcase below the two left fold expressions each expand into a
> > > logical expression with 1024 terms, for which potential_const_expr_1
> > > takes more than a minute to return true.  This is because p_c_e_1
> > > performs trial evaluation of the first operand of a &&/|| in order to
> > > determine whether to consider its second operand.  And because the
> > > expanded expression is left-associated, this trial evaluation causes
> > > p_c_e_1 to be quadratic in the number of terms of the expression.
> > >
> > > This patch fixes this quadratic behavior by making p_c_e_1 recurse only
> > > into the first operand of a &&/|| when checking for potentiality.  This
> > > means we'll consider more non-constant expressions as potentially
> > > constant compared to the trial evaluation approach, but that should be
> > > harmless as later constexpr evaluation of the expression will deem it
> > > non-constant anyway.
> >
> 
> Fair, especially now that it seems that C++23 is removing the diagnostic
> for a constexpr function that can't produce a constant expression.  And as
> more functions become constexpr, the trial evaluation gets more expensive
> to get to the point of failure.  I wonder if we want to stop calling
> cxx_eval_outermost_constant_expression from pot_c_e_1 entirely, only check
> whether the operand is already constant.

That would make p_c_e_1 surely much faster, but on the other side we would
stop diagnosing some functions that can't be valid constant expressions
no matter with what arguments they are called.

Another option would be to do these cxx_eval_outermost_constant_expression
calls from p_c_e_1 only in a cheap mode, i.e. with constexpr_ops_limit
temporarily lowered to something very small, 100-ish or 1000-ish or so, so it would
handle small expressions like before, but would quietly punt on large
expressions.

	Jakub
  

On Tue, 26 Oct 2021, Jason Merrill wrote:

> On Tue, Oct 26, 2021 at 2:46 PM Jakub Jelinek via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>       On Tue, Oct 26, 2021 at 01:44:18PM -0400, Patrick Palka via Gcc-patches wrote:
>       > In the testcase below the two left fold expressions each expand into a
>       > logical expression with 1024 terms, for which potential_const_expr_1
>       > takes more than a minute to return true.  This is because p_c_e_1
>       > performs trial evaluation of the first operand of a &&/|| in order to
>       > determine whether to consider its second operand.  And because the
>       > expanded expression is left-associated, this trial evaluation causes
>       > p_c_e_1 to be quadratic in the number of terms of the expression.
>       >
>       > This patch fixes this quadratic behavior by making p_c_e_1 recurse only
>       > into the first operand of a &&/|| when checking for potentiality.  This
>       > means we'll consider more non-constant expressions as potentially
>       > constant compared to the trial evaluation approach, but that should be
>       > harmless as later constexpr evaluation of the expression will deem it
>       > non-constant anyway.
> 
> 
> Fair, especially now that it seems that C++23 is removing the diagnostic for a constexpr function that can't produce a constant expression.  And as more functions become constexpr, the trial evaluation gets
> more expensive to get to the point of failure.  I wonder if we want to stop calling cxx_eval_outermost_constant_expression from pot_c_e_1 entirely, only check whether the operand is already constant.

The performance impact of the other calls to cxx_eval_outermost_const_expr
from p_c_e_1 is probably already mostly mitigated by the constexpr call
cache and the fact that we try to evaluate all calls to constexpr
functions during cp_fold_function anyway (at least with -O).  So trial
evaluation of e.g. the condition of a for/while loop that contains an
expensive constexpr call shouldn't cause the compiler to perform more
work overall IIUC.

> 
>       For very large && or || expressions (but not mixed or with ! etc.) another
>       possibility would be to check if the lhs or rhs have the same code and if
>       so, linearize the trees and recurse only on the leafs (trees with other
>       TREE_CODE) and stop when first expression isn't equal to tmp.
> 
> 
> This would be good if we wanted to keep the evaluation.
>  
> Jason
> 
>
  

On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote:
> The performance impact of the other calls to cxx_eval_outermost_const_expr
> from p_c_e_1 is probably already mostly mitigated by the constexpr call
> cache and the fact that we try to evaluate all calls to constexpr
> functions during cp_fold_function anyway (at least with -O).  So trial

constexpr function bodies don't go through cp_fold_function (intentionally,
so that we don't optimize away UB), the bodies are copied before the trees of the
normal copy are folded.

	Jakub
  

On Tue, 26 Oct 2021, Jakub Jelinek wrote:

> On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote:
> > The performance impact of the other calls to cxx_eval_outermost_const_expr
> > from p_c_e_1 is probably already mostly mitigated by the constexpr call
> > cache and the fact that we try to evaluate all calls to constexpr
> > functions during cp_fold_function anyway (at least with -O).  So trial
> 
> constexpr function bodies don't go through cp_fold_function (intentionally,
> so that we don't optimize away UB), the bodies are copied before the trees of the
> normal copy are folded.

Ah right, I had forgotten about that..

Here's another approach that doesn't need to remove trial evaluation for
&&/||.  The idea is to first quietly check if the second operand is
potentially constant _before_ performing trial evaluation of the first
operand.  This speeds up the case we care about (both operands are
potentially constant) without regressing any diagnostics.  We have to be
careful about emitting bogus diagnostics when tf_error is set, hence the
first hunk below which makes p_c_e_1 always proceed quietly first, and
replay noisily in case of error (similar to how satisfaction works).

Would something like this be preferable?

-- >8 --

gcc/cp/ChangeLog:

	* constexpr.c (potential_constant_expression_1): When tf_error is
	set, proceed quietly first and return true if successful.
	<case TRUTH_*_EXPR>: When tf_error is not set, check potentiality
	of the second operand before performing trial evaluation of the
	first operand rather than after.


diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 6f83d303cdd..821bd41d994 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -8056,6 +8056,14 @@ 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)
 
+  if (flags & tf_error)
+    {
+      flags &= ~tf_error;
+      if (RECUR (t, want_rval))
+	return true;
+      flags |= tf_error;
+    }
+
   enum { any = false, rval = true };
   int i;
   tree tmp;
@@ -8892,13 +8900,16 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
       tmp = boolean_false_node;
     truth:
       {
-	tree op = TREE_OPERAND (t, 0);
-	if (!RECUR (op, rval))
+	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))
+	  return true;
 	if (!processing_template_decl)
-	  op = cxx_eval_outermost_constant_expr (op, true);
-	if (tree_int_cst_equal (op, tmp))
-	  return RECUR (TREE_OPERAND (t, 1), rval);
+	  op0 = cxx_eval_outermost_constant_expr (op0, true);
+	if (tree_int_cst_equal (op0, tmp))
+	  return (flags & tf_error) ? RECUR (op1, rval) : false;
 	else
 	  return true;
       }
  

On 10/27/21 14:54, Patrick Palka wrote:
> On Tue, 26 Oct 2021, Jakub Jelinek wrote:
> 
>> On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote:
>>> The performance impact of the other calls to cxx_eval_outermost_const_expr
>>> from p_c_e_1 is probably already mostly mitigated by the constexpr call
>>> cache and the fact that we try to evaluate all calls to constexpr
>>> functions during cp_fold_function anyway (at least with -O).  So trial
>>
>> constexpr function bodies don't go through cp_fold_function (intentionally,
>> so that we don't optimize away UB), the bodies are copied before the trees of the
>> normal copy are folded.
> 
> Ah right, I had forgotten about that..
> 
> Here's another approach that doesn't need to remove trial evaluation for
> &&/||.  The idea is to first quietly check if the second operand is
> potentially constant _before_ performing trial evaluation of the first
> operand.  This speeds up the case we care about (both operands are
> potentially constant) without regressing any diagnostics.  We have to be
> careful about emitting bogus diagnostics when tf_error is set, hence the
> first hunk below which makes p_c_e_1 always proceed quietly first, and
> replay noisily in case of error (similar to how satisfaction works).
> 
> Would something like this be preferable?

Seems plausible, though doubling the number of stack frames is a downside.

What did you think of Jakub's suggestion of linearizing the terms?

> -- >8 --
> 
> gcc/cp/ChangeLog:
> 
> 	* constexpr.c (potential_constant_expression_1): When tf_error is
> 	set, proceed quietly first and return true if successful.
> 	<case TRUTH_*_EXPR>: When tf_error is not set, check potentiality
> 	of the second operand before performing trial evaluation of the
> 	first operand rather than after.
> 
> 
> diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
> index 6f83d303cdd..821bd41d994 100644
> --- a/gcc/cp/constexpr.c
> +++ b/gcc/cp/constexpr.c
> @@ -8056,6 +8056,14 @@ 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)
>   
> +  if (flags & tf_error)
> +    {
> +      flags &= ~tf_error;
> +      if (RECUR (t, want_rval))
> +	return true;
> +      flags |= tf_error;
> +    }
> +
>     enum { any = false, rval = true };
>     int i;
>     tree tmp;
> @@ -8892,13 +8900,16 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
>         tmp = boolean_false_node;
>       truth:
>         {
> -	tree op = TREE_OPERAND (t, 0);
> -	if (!RECUR (op, rval))
> +	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))
> +	  return true;
>   	if (!processing_template_decl)
> -	  op = cxx_eval_outermost_constant_expr (op, true);
> -	if (tree_int_cst_equal (op, tmp))
> -	  return RECUR (TREE_OPERAND (t, 1), rval);
> +	  op0 = cxx_eval_outermost_constant_expr (op0, true);
> +	if (tree_int_cst_equal (op0, tmp))
> +	  return (flags & tf_error) ? RECUR (op1, rval) : false;
>   	else
>   	  return true;
>         }
>
  

On Wed, 27 Oct 2021, Jason Merrill wrote:

> On 10/27/21 14:54, Patrick Palka wrote:
> > On Tue, 26 Oct 2021, Jakub Jelinek wrote:
> > 
> > > On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote:
> > > > The performance impact of the other calls to
> > > > cxx_eval_outermost_const_expr
> > > > from p_c_e_1 is probably already mostly mitigated by the constexpr call
> > > > cache and the fact that we try to evaluate all calls to constexpr
> > > > functions during cp_fold_function anyway (at least with -O).  So trial
> > > 
> > > constexpr function bodies don't go through cp_fold_function
> > > (intentionally,
> > > so that we don't optimize away UB), the bodies are copied before the trees
> > > of the
> > > normal copy are folded.
> > 
> > Ah right, I had forgotten about that..
> > 
> > Here's another approach that doesn't need to remove trial evaluation for
> > &&/||.  The idea is to first quietly check if the second operand is
> > potentially constant _before_ performing trial evaluation of the first
> > operand.  This speeds up the case we care about (both operands are
> > potentially constant) without regressing any diagnostics.  We have to be
> > careful about emitting bogus diagnostics when tf_error is set, hence the
> > first hunk below which makes p_c_e_1 always proceed quietly first, and
> > replay noisily in case of error (similar to how satisfaction works).
> > 
> > Would something like this be preferable?
> 
> Seems plausible, though doubling the number of stack frames is a downside.

Whoops, good point..  The noisy -> quiet adjustment only needs to
be performed during the outermost call to p_c_e_1, and not also during
each recursive call.  The revised diff below fixes this thinko, and so
only a single extra stack frame is needed AFAICT.

> 
> What did you think of Jakub's suggestion of linearizing the terms?

IIUC that would fix the quadraticness, but it wouldn't address that
we end up evaluating the entire expression twice, once during the trial
evaluation of each term from p_c_e_1 and again during the proper
evaluation of the entire expression.  It'd be nice if we could somehow
avoid the double evaluation, as in the approach below (or in the first
patch).

-- >8 --

gcc/cp/ChangeLog:

	* constexpr.c (potential_constant_expression_1): When tf_error is
	set, proceed quietly first and return true if successful.
	<case TRUTH_*_EXPR>: When tf_error is not set, check potentiality
	of the second operand before performing trial evaluation of the
	first operand rather than after.

diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 6f83d303cdd..7855a948baf 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -8892,13 +8892,16 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
       tmp = boolean_false_node;
     truth:
       {
-	tree op = TREE_OPERAND (t, 0);
-	if (!RECUR (op, rval))
+	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))
+	  return true;
 	if (!processing_template_decl)
-	  op = cxx_eval_outermost_constant_expr (op, true);
-	if (tree_int_cst_equal (op, tmp))
-	  return RECUR (TREE_OPERAND (t, 1), rval);
+	  op0 = cxx_eval_outermost_constant_expr (op0, true);
+	if (tree_int_cst_equal (op0, tmp))
+	  return (flags & tf_error) ? RECUR (op1, rval) : false;
 	else
 	  return true;
       }
@@ -9107,6 +9110,14 @@ bool
 potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
 				 tsubst_flags_t flags)
 {
+  if (flags & tf_error)
+    {
+      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);
  

On 10/27/21 17:10, Patrick Palka wrote:
> On Wed, 27 Oct 2021, Jason Merrill wrote:
> 
>> On 10/27/21 14:54, Patrick Palka wrote:
>>> On Tue, 26 Oct 2021, Jakub Jelinek wrote:
>>>
>>>> On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote:
>>>>> The performance impact of the other calls to
>>>>> cxx_eval_outermost_const_expr
>>>>> from p_c_e_1 is probably already mostly mitigated by the constexpr call
>>>>> cache and the fact that we try to evaluate all calls to constexpr
>>>>> functions during cp_fold_function anyway (at least with -O).  So trial
>>>>
>>>> constexpr function bodies don't go through cp_fold_function
>>>> (intentionally,
>>>> so that we don't optimize away UB), the bodies are copied before the trees
>>>> of the
>>>> normal copy are folded.
>>>
>>> Ah right, I had forgotten about that..
>>>
>>> Here's another approach that doesn't need to remove trial evaluation for
>>> &&/||.  The idea is to first quietly check if the second operand is
>>> potentially constant _before_ performing trial evaluation of the first
>>> operand.  This speeds up the case we care about (both operands are
>>> potentially constant) without regressing any diagnostics.  We have to be
>>> careful about emitting bogus diagnostics when tf_error is set, hence the
>>> first hunk below which makes p_c_e_1 always proceed quietly first, and
>>> replay noisily in case of error (similar to how satisfaction works).
>>>
>>> Would something like this be preferable?
>>
>> Seems plausible, though doubling the number of stack frames is a downside.
> 
> Whoops, good point..  The noisy -> quiet adjustment only needs to
> be performed during the outermost call to p_c_e_1, and not also during
> each recursive call.  The revised diff below fixes this thinko, and so
> only a single extra stack frame is needed AFAICT.
> 
>> What did you think of Jakub's suggestion of linearizing the terms?
> 
> IIUC that would fix the quadraticness, but it wouldn't address that
> we end up evaluating the entire expression twice, once during the trial
> evaluation of each term from p_c_e_1 and again during the proper
> evaluation of the entire expression.  It'd be nice if we could somehow
> avoid the double evaluation, as in the approach below (or in the first
> patch).

OK with more comments to explain the tf_error hijinks.

> -- >8 --
> 
> gcc/cp/ChangeLog:
> 
> 	* constexpr.c (potential_constant_expression_1): When tf_error is
> 	set, proceed quietly first and return true if successful.
> 	<case TRUTH_*_EXPR>: When tf_error is not set, check potentiality
> 	of the second operand before performing trial evaluation of the
> 	first operand rather than after.
> 
> diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
> index 6f83d303cdd..7855a948baf 100644
> --- a/gcc/cp/constexpr.c
> +++ b/gcc/cp/constexpr.c
> @@ -8892,13 +8892,16 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
>         tmp = boolean_false_node;
>       truth:
>         {
> -	tree op = TREE_OPERAND (t, 0);
> -	if (!RECUR (op, rval))
> +	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))
> +	  return true;
>   	if (!processing_template_decl)
> -	  op = cxx_eval_outermost_constant_expr (op, true);
> -	if (tree_int_cst_equal (op, tmp))
> -	  return RECUR (TREE_OPERAND (t, 1), rval);
> +	  op0 = cxx_eval_outermost_constant_expr (op0, true);
> +	if (tree_int_cst_equal (op0, tmp))
> +	  return (flags & tf_error) ? RECUR (op1, rval) : false;
>   	else
>   	  return true;
>         }
> @@ -9107,6 +9110,14 @@ bool
>   potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
>   				 tsubst_flags_t flags)
>   {
> +  if (flags & tf_error)
> +    {
> +      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);
  

> On 10/27/21 17:10, Patrick Palka wrote:
> > On Wed, 27 Oct 2021, Jason Merrill wrote:
> > 
> > > On 10/27/21 14:54, Patrick Palka wrote:
> > > > On Tue, 26 Oct 2021, Jakub Jelinek wrote:
> > > > 
> > > > > On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote:
> > > > > > The performance impact of the other calls to
> > > > > > cxx_eval_outermost_const_expr
> > > > > > from p_c_e_1 is probably already mostly mitigated by the constexpr
> > > > > > call
> > > > > > cache and the fact that we try to evaluate all calls to constexpr
> > > > > > functions during cp_fold_function anyway (at least with -O).  So
> > > > > > trial
> > > > > 
> > > > > constexpr function bodies don't go through cp_fold_function
> > > > > (intentionally,
> > > > > so that we don't optimize away UB), the bodies are copied before the
> > > > > trees
> > > > > of the
> > > > > normal copy are folded.
> > > > 
> > > > Ah right, I had forgotten about that..
> > > > 
> > > > Here's another approach that doesn't need to remove trial evaluation for
> > > > &&/||.  The idea is to first quietly check if the second operand is
> > > > potentially constant _before_ performing trial evaluation of the first
> > > > operand.  This speeds up the case we care about (both operands are
> > > > potentially constant) without regressing any diagnostics.  We have to be
> > > > careful about emitting bogus diagnostics when tf_error is set, hence the
> > > > first hunk below which makes p_c_e_1 always proceed quietly first, and
> > > > replay noisily in case of error (similar to how satisfaction works).
> > > > 
> > > > Would something like this be preferable?
> > > 
> > > Seems plausible, though doubling the number of stack frames is a downside.
> > 
> > Whoops, good point..  The noisy -> quiet adjustment only needs to
> > be performed during the outermost call to p_c_e_1, and not also during
> > each recursive call.  The revised diff below fixes this thinko, and so
> > only a single extra stack frame is needed AFAICT.
> > 
> > > What did you think of Jakub's suggestion of linearizing the terms?
> > 
> > IIUC that would fix the quadraticness, but it wouldn't address that
> > we end up evaluating the entire expression twice, once during the trial
> > evaluation of each term from p_c_e_1 and again during the proper
> > evaluation of the entire expression.  It'd be nice if we could somehow
> > avoid the double evaluation, as in the approach below (or in the first
> > patch).
> 
> OK with more comments to explain the tf_error hijinks.

Thanks a lot, here's the complete committed patch for the record:

-- >8 --

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

In the testcase below the two left fold expressions each expand into a
constant logical expression with 1024 terms, for which potential_const_expr
takes more than a minute to return true.  This happens because p_c_e_1
performs trial evaluation of the first operand of a &&/|| in order to
determine whether to consider the potentiality of the second operand.
And because the expanded expression is left-associated, this trial
evaluation causes p_c_e_1 to be quadratic in the number of terms of the
expression.

This patch fixes this quadratic behavior by making p_c_e_1 preemptively
compute potentiality of the second operand of a &&/||, and perform trial
evaluation of the first operand only if the second operand isn't
potentially constant.  We must be careful to avoid emitting bogus
diagnostics during the preemptive computation; to that end, we perform
this shortcut only when tf_error is cleared, and when tf_error is set we
now first check potentiality of the whole expression quietly and replay
the check noisily for diagnostics.

Apart from fixing the quadraticness for left-associated logical exprs,
this change also reduces compile time for the libstdc++ testcase
20_util/variant/87619.cc by about 15% even though our <variant> uses
right folds instead of left folds.  Likewise for the testcase in the PR,
for which compile time is reduced by 30%.  The reason for these speedups
is that p_c_e_1 no longer performs expensive trial evaluation of each term
of large constant logical expressions when determining their potentiality.

	PR c++/102780

gcc/cp/ChangeLog:

	* constexpr.c (potential_constant_expression_1) <case TRUTH_*_EXPR>:
	When tf_error isn't set, preemptively check potentiality of the
	second operand before performing trial evaluation of the first
	operand.
	(potential_constant_expression_1): When tf_error is set, first check
	potentiality quietly and return true if successful, otherwise
	proceed noisily to give errors.

gcc/testsuite/ChangeLog:

	* g++.dg/cpp1z/fold13.C: New test.
---
 gcc/cp/constexpr.c                  | 26 +++++++++++++++++++++-----
 gcc/testsuite/g++.dg/cpp1z/fold13.C | 29 +++++++++++++++++++++++++++++
 2 files changed, 50 insertions(+), 5 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/cpp1z/fold13.C

diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index a31d12b7451..40fe165c2b7 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -8892,13 +8892,18 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
       tmp = boolean_false_node;
     truth:
       {
-	tree op = TREE_OPERAND (t, 0);
-	if (!RECUR (op, rval))
+	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.  */
+	  return true;
 	if (!processing_template_decl)
-	  op = cxx_eval_outermost_constant_expr (op, true);
-	if (tree_int_cst_equal (op, tmp))
-	  return RECUR (TREE_OPERAND (t, 1), rval);
+	  op0 = cxx_eval_outermost_constant_expr (op0, true);
+	if (tree_int_cst_equal (op0, tmp))
+	  return (flags & tf_error) ? RECUR (op1, rval) : false;
 	else
 	  return true;
       }
@@ -9107,6 +9112,17 @@ 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);
diff --git a/gcc/testsuite/g++.dg/cpp1z/fold13.C b/gcc/testsuite/g++.dg/cpp1z/fold13.C
new file mode 100644
index 00000000000..9d7554f8999
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1z/fold13.C
@@ -0,0 +1,29 @@
+// { dg-do compile { target c++17 } }
+// Verify constexpr evaluation of a large left fold logical expression
+// isn't quadratic in the size of the expanded expression.
+
+template<int> struct S { static constexpr bool value = true; };
+
+template<class T, T...> struct integer_sequence { };
+
+template<class T, T N>
+using make_integer_sequence
+#if __has_builtin(__make_integer_seq)
+  = __make_integer_seq<integer_sequence, T, N>;
+#else
+  = integer_sequence<T, __integer_pack(N)...>;
+#endif
+
+template<int... Is>
+constexpr bool f_impl(integer_sequence<int, Is...>) {
+  return (... && S<Is>::value);
+}
+
+static_assert(f_impl(make_integer_sequence<int, 1024>()));
+
+template<int... Is>
+constexpr bool g_impl(integer_sequence<int, Is...>) {
+  return (... || !S<Is>::value);
+}
+
+static_assert(!g_impl(make_integer_sequence<int, 1024>()));
  

On Thu, Oct 28, 2021 at 12:40:02PM -0400, Patrick Palka wrote:
> 	PR c++/102780
> 
> gcc/cp/ChangeLog:
> 
> 	* constexpr.c (potential_constant_expression_1) <case TRUTH_*_EXPR>:
> 	When tf_error isn't set, preemptively check potentiality of the
> 	second operand before performing trial evaluation of the first
> 	operand.
> 	(potential_constant_expression_1): When tf_error is set, first check
> 	potentiality quietly and return true if successful, otherwise
> 	proceed noisily to give errors.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* g++.dg/cpp1z/fold13.C: New test.
> ---
>  gcc/cp/constexpr.c                  | 26 +++++++++++++++++++++-----
>  gcc/testsuite/g++.dg/cpp1z/fold13.C | 29 +++++++++++++++++++++++++++++
>  2 files changed, 50 insertions(+), 5 deletions(-)
>  create mode 100644 gcc/testsuite/g++.dg/cpp1z/fold13.C

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.

So, can't we instead drop the second hunk, if processing_template_decl or
TREE_CODE (op0) == INTEGER_CST do what the code did before, and just
otherwise if flag & tf_error temporarily clear it, RECUR on op1 first, then
cxx_eval_outermost_constant_expr and if tree_int_cst_equal RECUR on op1
the second time with tf_error and some extra flag (1 << 30?) that will mean not to
RECUR on op1 twice in recursive invocations (to avoid bad compile time
complexity on
(x && (x && (x && (x && (x && (x && (x && (x && (x && (x && (x && (x && y))))))))))))
etc. if x constant evaluates to true and y is not potential constant
expression.

Though, I'm not sure that doing the RECUR (op1, rval) instead of
cxx_eval_outermost_constant_expr must be generally a win for compile time,
it can be if op0 is very large expression, but it can be a pessimization if
op1 is huge and op0 is simple and doesn't constexpr evaluate to tmp.

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.

> --- a/gcc/cp/constexpr.c
> +++ b/gcc/cp/constexpr.c
> @@ -8892,13 +8892,18 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
>        tmp = boolean_false_node;
>      truth:
>        {
> -	tree op = TREE_OPERAND (t, 0);
> -	if (!RECUR (op, rval))
> +	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.  */
> +	  return true;
>  	if (!processing_template_decl)
> -	  op = cxx_eval_outermost_constant_expr (op, true);
> -	if (tree_int_cst_equal (op, tmp))
> -	  return RECUR (TREE_OPERAND (t, 1), rval);
> +	  op0 = cxx_eval_outermost_constant_expr (op0, true);
> +	if (tree_int_cst_equal (op0, tmp))
> +	  return (flags & tf_error) ? RECUR (op1, rval) : false;
>  	else
>  	  return true;
>        }
> @@ -9107,6 +9112,17 @@ 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);

	Jakub
  

On Thu, 28 Oct 2021, Jakub Jelinek wrote:
> On Thu, Oct 28, 2021 at 12:40:02PM -0400, Patrick Palka wrote:
> > 	PR c++/102780
> > 
> > gcc/cp/ChangeLog:
> > 
> > 	* constexpr.c (potential_constant_expression_1) <case TRUTH_*_EXPR>:
> > 	When tf_error isn't set, preemptively check potentiality of the
> > 	second operand before performing trial evaluation of the first
> > 	operand.
> > 	(potential_constant_expression_1): When tf_error is set, first check
> > 	potentiality quietly and return true if successful, otherwise
> > 	proceed noisily to give errors.
> > 
> > gcc/testsuite/ChangeLog:
> > 
> > 	* g++.dg/cpp1z/fold13.C: New test.
> > ---
> >  gcc/cp/constexpr.c                  | 26 +++++++++++++++++++++-----
> >  gcc/testsuite/g++.dg/cpp1z/fold13.C | 29 +++++++++++++++++++++++++++++
> >  2 files changed, 50 insertions(+), 5 deletions(-)
> >  create mode 100644 gcc/testsuite/g++.dg/cpp1z/fold13.C
> 
> 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.

> 
> So, can't we instead drop the second hunk, if processing_template_decl or
> TREE_CODE (op0) == INTEGER_CST do what the code did before, and just
> otherwise if flag & tf_error temporarily clear it, RECUR on op1 first, then
> cxx_eval_outermost_constant_expr and if tree_int_cst_equal RECUR on op1
> the second time with tf_error and some extra flag (1 << 30?) that will mean not to
> RECUR on op1 twice in recursive invocations (to avoid bad compile time
> complexity on
> (x && (x && (x && (x && (x && (x && (x && (x && (x && (x && (x && (x && y))))))))))))
> etc. if x constant evaluates to true and y is not potential constant
> expression.

I considered this approach but I wasn't sure it was worth the added
complexity just to speed up the error case.  And the current approach is
already how constraint satisfaction works (it always proceeds quietly
first, and replays the whole thing noisily upon error if tf_error was
set) so there's also a precedence I suppose..

> 
> Though, I'm not sure that doing the RECUR (op1, rval) instead of
> cxx_eval_outermost_constant_expr must be generally a win for compile time,
> it can be if op0 is very large expression, but it can be a pessimization if
> op1 is huge and op0 is simple and doesn't constexpr evaluate to tmp.

True, it's not always a win but it seems to me that checking potentiality
of both operands first before doing the trial evaluation gives the most
consistent performance, at least for constant logical expressions.
Recursing on both operands takes time proportional to the size of the
operands, whereas trial evaluation can take arbitrarily long.

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

> 
> > --- a/gcc/cp/constexpr.c
> > +++ b/gcc/cp/constexpr.c
> > @@ -8892,13 +8892,18 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
> >        tmp = boolean_false_node;
> >      truth:
> >        {
> > -	tree op = TREE_OPERAND (t, 0);
> > -	if (!RECUR (op, rval))
> > +	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.  */
> > +	  return true;
> >  	if (!processing_template_decl)
> > -	  op = cxx_eval_outermost_constant_expr (op, true);
> > -	if (tree_int_cst_equal (op, tmp))
> > -	  return RECUR (TREE_OPERAND (t, 1), rval);
> > +	  op0 = cxx_eval_outermost_constant_expr (op0, true);
> > +	if (tree_int_cst_equal (op0, tmp))
> > +	  return (flags & tf_error) ? RECUR (op1, rval) : false;
> >  	else
> >  	  return true;
> >        }
> > @@ -9107,6 +9112,17 @@ 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);
> 
> 	Jakub
> 
>
  

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.

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

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.

	Jakub
  

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);
  

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