diff mbox series

tree: Improve skip_simple_arithmetic [PR119183]

Message ID Z8/uroxageTgukBD@tucnak
State New
Headers
Series tree: Improve skip_simple_arithmetic [PR119183] |

Commit Message

Jakub Jelinek March 11, 2025, 8:05 a.m. UTC 
  Hi!

The following testcase takes very long time to compile, because
skip_simple_arithmetic decides to first call tree_invariant_p on
the second argument (and indirectly recurse there).  I think before
canonicalization of operands for commutative binary expressions
(and for non-commutative ones always) it is pretty common that the
first operand is a constant, something which tree_invariant_p handles
immediately, so the following patch special cases that; I've added
there a tree_invariant_p call too after the checks, while it is not
really needed currently, tree_invariant_p has the same checks, I wanted
to be prepared in case tree_invariant_p changes.  But if you think
I should avoid it, I can drop it too.

This is just a partial fix, I think one can certainly construct a testcase
which will still have horrible compile time complexity (but I've tried and
haven't managed to do so), so perhaps we should just limit the recursion
depth through skip_simple_arithmetic/tree_invariant_p with some defaulted
argument.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2025-03-11  Jakub Jelinek  <jakub@redhat.com>

	PR c/119183
	* tree.cc (skip_simple_arithmetic): If first operand of binary
	expr is TREE_CONSTANT or TREE_READONLY with no side-effects, call
	tree_invariant_p on that operand first instead of on the second.

	* gcc.dg/pr119183.c: New test.


	Jakub

Comments

Richard Biener March 11, 2025, 8:55 a.m. UTC | #1 
On Tue, 11 Mar 2025, Jakub Jelinek wrote:

> Hi!
> 
> The following testcase takes very long time to compile, because
> skip_simple_arithmetic decides to first call tree_invariant_p on
> the second argument (and indirectly recurse there).  I think before
> canonicalization of operands for commutative binary expressions
> (and for non-commutative ones always) it is pretty common that the
> first operand is a constant, something which tree_invariant_p handles
> immediately, so the following patch special cases that; I've added
> there a tree_invariant_p call too after the checks, while it is not
> really needed currently, tree_invariant_p has the same checks, I wanted
> to be prepared in case tree_invariant_p changes.  But if you think
> I should avoid it, I can drop it too.
> 
> This is just a partial fix, I think one can certainly construct a testcase
> which will still have horrible compile time complexity (but I've tried and
> haven't managed to do so), so perhaps we should just limit the recursion
> depth through skip_simple_arithmetic/tree_invariant_p with some defaulted
> argument.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Can you add a comment before the code?  OK with that change.

> 2025-03-11  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR c/119183
> 	* tree.cc (skip_simple_arithmetic): If first operand of binary
> 	expr is TREE_CONSTANT or TREE_READONLY with no side-effects, call
> 	tree_invariant_p on that operand first instead of on the second.
> 
> 	* gcc.dg/pr119183.c: New test.
> 
> --- gcc/tree.cc.jj	2025-03-08 00:07:01.848908327 +0100
> +++ gcc/tree.cc	2025-03-10 17:04:48.630157371 +0100
> @@ -4105,7 +4105,12 @@ skip_simple_arithmetic (tree expr)
>  	expr = TREE_OPERAND (expr, 0);
>        else if (BINARY_CLASS_P (expr))
>  	{
> -	  if (tree_invariant_p (TREE_OPERAND (expr, 1)))
> +	  if ((TREE_CONSTANT (TREE_OPERAND (expr, 0))
> +	       || (TREE_READONLY (TREE_OPERAND (expr, 0))
> +		   && !TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0))))
> +	      && tree_invariant_p (TREE_OPERAND (expr, 0)))
> +	    expr = TREE_OPERAND (expr, 1);
> +	  else if (tree_invariant_p (TREE_OPERAND (expr, 1)))
>  	    expr = TREE_OPERAND (expr, 0);
>  	  else if (tree_invariant_p (TREE_OPERAND (expr, 0)))
>  	    expr = TREE_OPERAND (expr, 1);
> --- gcc/testsuite/gcc.dg/pr119183.c.jj	2025-03-10 17:48:57.839774108 +0100
> +++ gcc/testsuite/gcc.dg/pr119183.c	2025-03-10 17:48:22.960253026 +0100
> @@ -0,0 +1,12 @@
> +/* PR c/119183 */
> +/* { dg-do compile } */
> +
> +int foo (void);
> +#define A(x) (1.0f * (1.0f * (1.0f * (1.0f * (1.0f * (1.0f * (1.0f * (1.0f * (x)))))))))
> +
> +float
> +bar (float r)
> +{
> +  r += A (A (A (A (A (A (A (A (foo ()))))))));
> +  return r;
> +}
> 
> 	Jakub
> 
>
diff mbox series

Patch

--- gcc/tree.cc.jj	2025-03-08 00:07:01.848908327 +0100
+++ gcc/tree.cc	2025-03-10 17:04:48.630157371 +0100
@@ -4105,7 +4105,12 @@  skip_simple_arithmetic (tree expr)
 	expr = TREE_OPERAND (expr, 0);
       else if (BINARY_CLASS_P (expr))
 	{
-	  if (tree_invariant_p (TREE_OPERAND (expr, 1)))
+	  if ((TREE_CONSTANT (TREE_OPERAND (expr, 0))
+	       || (TREE_READONLY (TREE_OPERAND (expr, 0))
+		   && !TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0))))
+	      && tree_invariant_p (TREE_OPERAND (expr, 0)))
+	    expr = TREE_OPERAND (expr, 1);
+	  else if (tree_invariant_p (TREE_OPERAND (expr, 1)))
 	    expr = TREE_OPERAND (expr, 0);
 	  else if (tree_invariant_p (TREE_OPERAND (expr, 0)))
 	    expr = TREE_OPERAND (expr, 1);
--- gcc/testsuite/gcc.dg/pr119183.c.jj	2025-03-10 17:48:57.839774108 +0100
+++ gcc/testsuite/gcc.dg/pr119183.c	2025-03-10 17:48:22.960253026 +0100
@@ -0,0 +1,12 @@ 
+/* PR c/119183 */
+/* { dg-do compile } */
+
+int foo (void);
+#define A(x) (1.0f * (1.0f * (1.0f * (1.0f * (1.0f * (1.0f * (1.0f * (1.0f * (x)))))))))
+
+float
+bar (float r)
+{
+  r += A (A (A (A (A (A (A (A (foo ()))))))));
+  return r;
+}