Patchwork Fix up reassoc (PR tree-optimization/58946)

login
register
mail settings
Submitter Jakub Jelinek
Date Nov. 1, 2013, 11:11 a.m.
Message ID <20131101111107.GB27813@tucnak.zalov.cz>
Download mbox | patch
Permalink /patch/287789/
State New
Headers show

Comments

Jakub Jelinek - Nov. 1, 2013, 11:11 a.m.
Hi!

My recent reassoc patch caused following regression (though, it only started
failing on this testcase with Andrew's ifcombine changes).

The issue is that update_ops relies on walking the same stmts as get_ops
did, and uses has_single_uses (either directly or indirectly through
is_reassociable_op).  optimize_range_tests itself doesn't change the IL
except for inserting new stmts using values on which get_ops already didn't
recurse (either because they were multiple uses or non-reassociable).
The problem in the testcase is when optimizing a GIMPLE_COND directly, there
is no guarantee of single use, we treat the condition as the starting point
of init_range_info and thus SSA_NAME != 0 or SSA_NAME == 0 etc. and that
is just fine if SSA_NAME has multiple uses, so if we first change the
condition to something else (as instructed by the changed ops[i]->op value
from NULL to some SSA_NAME), we might turn something update_ops looks at
from multiple uses into single use.

This patch fixes it by doing all the update_ops calls before changing
GIMPLE_CONDs themselves.  I believe it is safe, update_ops will walk only
single use SSA_NAMEs and thus they occur only in the single particular
update_ops call, and never removes anything, only adds new stmt (which
can make single use SSA_NAMEs into multiple use, but that happened after
we've walked that originally single use exactly ones from the single use),
and GIMPLE_COND adjustments never use has_single_use, thus they can be
safely done after all update_ops have been called.

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

2013-11-01  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/58946
	* tree-ssa-reassoc.c (maybe_optimize_range_tests): Update all
	bbs with bbinfo[idx].op != NULL before all blocks with
	bbinfo[idx].op == NULL.

	* gcc.c-torture/compile/pr58946.c: New test.


	Jakub
Richard Guenther - Nov. 4, 2013, 10:24 a.m.
On Fri, 1 Nov 2013, Jakub Jelinek wrote:

> Hi!
> 
> My recent reassoc patch caused following regression (though, it only started
> failing on this testcase with Andrew's ifcombine changes).
> 
> The issue is that update_ops relies on walking the same stmts as get_ops
> did, and uses has_single_uses (either directly or indirectly through
> is_reassociable_op).  optimize_range_tests itself doesn't change the IL
> except for inserting new stmts using values on which get_ops already didn't
> recurse (either because they were multiple uses or non-reassociable).
> The problem in the testcase is when optimizing a GIMPLE_COND directly, there
> is no guarantee of single use, we treat the condition as the starting point
> of init_range_info and thus SSA_NAME != 0 or SSA_NAME == 0 etc. and that
> is just fine if SSA_NAME has multiple uses, so if we first change the
> condition to something else (as instructed by the changed ops[i]->op value
> from NULL to some SSA_NAME), we might turn something update_ops looks at
> from multiple uses into single use.
> 
> This patch fixes it by doing all the update_ops calls before changing
> GIMPLE_CONDs themselves.  I believe it is safe, update_ops will walk only
> single use SSA_NAMEs and thus they occur only in the single particular
> update_ops call, and never removes anything, only adds new stmt (which
> can make single use SSA_NAMEs into multiple use, but that happened after
> we've walked that originally single use exactly ones from the single use),
> and GIMPLE_COND adjustments never use has_single_use, thus they can be
> safely done after all update_ops have been called.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Ok.

Thanks,
Richard.

> 2013-11-01  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/58946
> 	* tree-ssa-reassoc.c (maybe_optimize_range_tests): Update all
> 	bbs with bbinfo[idx].op != NULL before all blocks with
> 	bbinfo[idx].op == NULL.
> 
> 	* gcc.c-torture/compile/pr58946.c: New test.
> 
> --- gcc/tree-ssa-reassoc.c.jj	2013-10-24 10:19:21.000000000 +0200
> +++ gcc/tree-ssa-reassoc.c	2013-11-01 09:23:09.264615181 +0100
> @@ -2657,6 +2657,7 @@ maybe_optimize_range_tests (gimple stmt)
>    edge e;
>    vec<operand_entry_t> ops = vNULL;
>    vec<inter_bb_range_test_entry> bbinfo = vNULL;
> +  bool any_changes = false;
>  
>    /* Consider only basic blocks that end with GIMPLE_COND or
>       a cast statement satisfying final_range_test_p.  All
> @@ -2870,41 +2871,31 @@ maybe_optimize_range_tests (gimple stmt)
>  	break;
>      }
>    if (ops.length () > 1)
> +    any_changes = optimize_range_tests (ERROR_MARK, &ops);
> +  if (any_changes)
>      {
>        unsigned int idx;
> -      bool any_changes = optimize_range_tests (ERROR_MARK, &ops);
> -      for (bb = last_bb, idx = 0; any_changes; bb = single_pred (bb), idx++)
> +      /* update_ops relies on has_single_use predicates returning the
> +	 same values as it did during get_ops earlier.  Additionally it
> +	 never removes statements, only adds new ones and it should walk
> +	 from the single imm use and check the predicate already before
> +	 making those changes.
> +	 On the other side, the handling of GIMPLE_COND directly can turn
> +	 previously multiply used SSA_NAMEs into single use SSA_NAMEs, so
> +	 it needs to be done in a separate loop afterwards.  */
> +      for (bb = last_bb, idx = 0; ; bb = single_pred (bb), idx++)
>  	{
> -	  if (bbinfo[idx].first_idx < bbinfo[idx].last_idx)
> +	  if (bbinfo[idx].first_idx < bbinfo[idx].last_idx
> +	      && bbinfo[idx].op != NULL_TREE)
>  	    {
> -	      gimple stmt = last_stmt (bb);
>  	      tree new_op;
>  
> -	      if (bbinfo[idx].op == NULL_TREE)
> -		{
> -		  if (ops[bbinfo[idx].first_idx]->op != NULL_TREE)
> -		    {
> -		      if (integer_zerop (ops[bbinfo[idx].first_idx]->op))
> -			gimple_cond_make_false (stmt);
> -		      else if (integer_onep (ops[bbinfo[idx].first_idx]->op))
> -			gimple_cond_make_true (stmt);
> -		      else
> -			{
> -			  gimple_cond_set_code (stmt, NE_EXPR);
> -			  gimple_cond_set_lhs (stmt,
> -					       ops[bbinfo[idx].first_idx]->op);
> -			  gimple_cond_set_rhs (stmt, boolean_false_node);
> -			}
> -		      update_stmt (stmt);
> -		    }
> -		  bbinfo[idx].op = new_op = boolean_false_node;
> -		}
> -	      else
> -		new_op = update_ops (bbinfo[idx].op,
> -				     (enum tree_code)
> -				     ops[bbinfo[idx].first_idx]->rank,
> -				     ops, &bbinfo[idx].first_idx,
> -				     loop_containing_stmt (stmt));
> +	      stmt = last_stmt (bb);
> +	      new_op = update_ops (bbinfo[idx].op,
> +				   (enum tree_code)
> +				   ops[bbinfo[idx].first_idx]->rank,
> +				   ops, &bbinfo[idx].first_idx,
> +				   loop_containing_stmt (stmt));
>  	      if (new_op == NULL_TREE)
>  		{
>  		  gcc_assert (bb == last_bb);
> @@ -2955,6 +2946,28 @@ maybe_optimize_range_tests (gimple stmt)
>  	    }
>  	  if (bb == first_bb)
>  	    break;
> +	}
> +      for (bb = last_bb, idx = 0; ; bb = single_pred (bb), idx++)
> +	{
> +	  if (bbinfo[idx].first_idx < bbinfo[idx].last_idx
> +	      && bbinfo[idx].op == NULL_TREE
> +	      && ops[bbinfo[idx].first_idx]->op != NULL_TREE)
> +	    {
> +	      stmt = last_stmt (bb);
> +	      if (integer_zerop (ops[bbinfo[idx].first_idx]->op))
> +		gimple_cond_make_false (stmt);
> +	      else if (integer_onep (ops[bbinfo[idx].first_idx]->op))
> +		gimple_cond_make_true (stmt);
> +	      else
> +		{
> +		  gimple_cond_set_code (stmt, NE_EXPR);
> +		  gimple_cond_set_lhs (stmt, ops[bbinfo[idx].first_idx]->op);
> +		  gimple_cond_set_rhs (stmt, boolean_false_node);
> +		}
> +	      update_stmt (stmt);
> +	    }
> +	  if (bb == first_bb)
> +	    break;
>  	}
>      }
>    bbinfo.release ();
> --- gcc/testsuite/gcc.c-torture/compile/pr58946.c.jj	2013-11-01 08:29:52.484276440 +0100
> +++ gcc/testsuite/gcc.c-torture/compile/pr58946.c	2013-11-01 08:29:29.000000000 +0100
> @@ -0,0 +1,20 @@
> +/* PR tree-optimization/58946 */
> +
> +int
> +foo (unsigned int c)
> +{
> +  unsigned int d, e, f;
> +  if ((int) c < 0)
> +    d = 0;
> +  else
> +    d = c;
> +  if (d == 0)
> +    e = __INT_MAX__ + 1U;
> +  else
> +    e = d;
> +  if ((int) e < 0)
> +    f = 0;
> +  else
> +    f = e;
> +  return f;
> +}
> 
> 	Jakub
> 
>

Patch

--- gcc/tree-ssa-reassoc.c.jj	2013-10-24 10:19:21.000000000 +0200
+++ gcc/tree-ssa-reassoc.c	2013-11-01 09:23:09.264615181 +0100
@@ -2657,6 +2657,7 @@  maybe_optimize_range_tests (gimple stmt)
   edge e;
   vec<operand_entry_t> ops = vNULL;
   vec<inter_bb_range_test_entry> bbinfo = vNULL;
+  bool any_changes = false;
 
   /* Consider only basic blocks that end with GIMPLE_COND or
      a cast statement satisfying final_range_test_p.  All
@@ -2870,41 +2871,31 @@  maybe_optimize_range_tests (gimple stmt)
 	break;
     }
   if (ops.length () > 1)
+    any_changes = optimize_range_tests (ERROR_MARK, &ops);
+  if (any_changes)
     {
       unsigned int idx;
-      bool any_changes = optimize_range_tests (ERROR_MARK, &ops);
-      for (bb = last_bb, idx = 0; any_changes; bb = single_pred (bb), idx++)
+      /* update_ops relies on has_single_use predicates returning the
+	 same values as it did during get_ops earlier.  Additionally it
+	 never removes statements, only adds new ones and it should walk
+	 from the single imm use and check the predicate already before
+	 making those changes.
+	 On the other side, the handling of GIMPLE_COND directly can turn
+	 previously multiply used SSA_NAMEs into single use SSA_NAMEs, so
+	 it needs to be done in a separate loop afterwards.  */
+      for (bb = last_bb, idx = 0; ; bb = single_pred (bb), idx++)
 	{
-	  if (bbinfo[idx].first_idx < bbinfo[idx].last_idx)
+	  if (bbinfo[idx].first_idx < bbinfo[idx].last_idx
+	      && bbinfo[idx].op != NULL_TREE)
 	    {
-	      gimple stmt = last_stmt (bb);
 	      tree new_op;
 
-	      if (bbinfo[idx].op == NULL_TREE)
-		{
-		  if (ops[bbinfo[idx].first_idx]->op != NULL_TREE)
-		    {
-		      if (integer_zerop (ops[bbinfo[idx].first_idx]->op))
-			gimple_cond_make_false (stmt);
-		      else if (integer_onep (ops[bbinfo[idx].first_idx]->op))
-			gimple_cond_make_true (stmt);
-		      else
-			{
-			  gimple_cond_set_code (stmt, NE_EXPR);
-			  gimple_cond_set_lhs (stmt,
-					       ops[bbinfo[idx].first_idx]->op);
-			  gimple_cond_set_rhs (stmt, boolean_false_node);
-			}
-		      update_stmt (stmt);
-		    }
-		  bbinfo[idx].op = new_op = boolean_false_node;
-		}
-	      else
-		new_op = update_ops (bbinfo[idx].op,
-				     (enum tree_code)
-				     ops[bbinfo[idx].first_idx]->rank,
-				     ops, &bbinfo[idx].first_idx,
-				     loop_containing_stmt (stmt));
+	      stmt = last_stmt (bb);
+	      new_op = update_ops (bbinfo[idx].op,
+				   (enum tree_code)
+				   ops[bbinfo[idx].first_idx]->rank,
+				   ops, &bbinfo[idx].first_idx,
+				   loop_containing_stmt (stmt));
 	      if (new_op == NULL_TREE)
 		{
 		  gcc_assert (bb == last_bb);
@@ -2955,6 +2946,28 @@  maybe_optimize_range_tests (gimple stmt)
 	    }
 	  if (bb == first_bb)
 	    break;
+	}
+      for (bb = last_bb, idx = 0; ; bb = single_pred (bb), idx++)
+	{
+	  if (bbinfo[idx].first_idx < bbinfo[idx].last_idx
+	      && bbinfo[idx].op == NULL_TREE
+	      && ops[bbinfo[idx].first_idx]->op != NULL_TREE)
+	    {
+	      stmt = last_stmt (bb);
+	      if (integer_zerop (ops[bbinfo[idx].first_idx]->op))
+		gimple_cond_make_false (stmt);
+	      else if (integer_onep (ops[bbinfo[idx].first_idx]->op))
+		gimple_cond_make_true (stmt);
+	      else
+		{
+		  gimple_cond_set_code (stmt, NE_EXPR);
+		  gimple_cond_set_lhs (stmt, ops[bbinfo[idx].first_idx]->op);
+		  gimple_cond_set_rhs (stmt, boolean_false_node);
+		}
+	      update_stmt (stmt);
+	    }
+	  if (bb == first_bb)
+	    break;
 	}
     }
   bbinfo.release ();
--- gcc/testsuite/gcc.c-torture/compile/pr58946.c.jj	2013-11-01 08:29:52.484276440 +0100
+++ gcc/testsuite/gcc.c-torture/compile/pr58946.c	2013-11-01 08:29:29.000000000 +0100
@@ -0,0 +1,20 @@ 
+/* PR tree-optimization/58946 */
+
+int
+foo (unsigned int c)
+{
+  unsigned int d, e, f;
+  if ((int) c < 0)
+    d = 0;
+  else
+    d = c;
+  if (d == 0)
+    e = __INT_MAX__ + 1U;
+  else
+    e = d;
+  if ((int) e < 0)
+    f = 0;
+  else
+    f = e;
+  return f;
+}