This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Properly valueize values we value-number to


On Tue, 17 Feb 2015, Richard Biener wrote:

> 
> This is something I noticed some time ago and that I remembered when
> you added that looping SSA_NAME_VALUE to simplify_control_stmt_condition.
> Currently DOM doesn't make sure that when setting
> SSA_NAME_VALUE (x) = y that SSA_NAME_VALUE (y) == y, thus you could
> get SSA_NAME_VALUE forming a chain until you reach the final value.
> 
> Thus the following patch which fixes all occurances and removes the
> looping from simplify_control_stmt_condition.  Did you have any
> testcase when you added that looping?
> 
> Note that this is purely by code inspection and I don't have any
> testcase where a SSA_NAME_VALUE chain causes missed optimizations
> (you'd have to disable a lot of other optimizations before dom1
> to be able to create a reasonably simple one).
> 
> Anyway - the tree-ssa-dom.c part bootstrapped and tested ok on
> x86_64-unknown-linux-gnu, the tree-ssa-threadedge.c part bootstrapped
> ok ontop of that and testing is still in progress.

On a closer look the record_const_or_copy_1 hunk is redundant
(record_equality is really a bit obfuscated...).

And record_equality is where the SSA_NAME_VALUEs might end up
forming chains?  At least because we might record a SSA_NAME_VALUE
for sth that might be the target of a SSA_NAME_VALUE, as in

 a_1 = b_2;  SSA_NAME_VALUE (a_1) == b_2;
 if (b_2 == i_3(D))
   ... temporarily SSA_NAME_VALUE (b_2) == i_3(D)

thus under if (b_2 == i_3(D)) SSA_NAME_VALUE (a_1) == b_2 and
SSA_NAME_VALUE (SSA_NAME_VALUE (a_1)) == i_3(D)?  I guess we
can't easily avoid that because we don't keep track of a
reverse mapping (nor would we want to update that).

Btw, in record_equality, the == part of the <= check for the loop
depth will just randomly swap x and y while we should prefer
IL canonical order.  If we can't rely on the input being in IL
canonical order we should prepend the whole function with

 if (tree_swap_operands_p (x, y, false))
   std::swap (x, y);

and change <= to < for the loop-depth check.

For PR62217 it is that loop depth check which causes the equivalence
to be recorded that ends up being harmful (well, harmful is the
actual propagation of course).  Btw, we already inhibit propagation
into IV increments (cprop_operand) - so it looks like we may
want to inhibit BIV replacement completely instead?

Index: gcc/tree-ssa-dom.c
===================================================================
--- gcc/tree-ssa-dom.c  (revision 220755)
+++ gcc/tree-ssa-dom.c  (working copy)
@@ -2291,11 +2291,16 @@ cprop_operand (gimple stmt, use_operand_
       if (!may_propagate_copy (op, val))
        return;
 
-      /* Do not propagate copies into simple IV increment statements.
-         See PR23821 for how this can disturb IV analysis.  */
-      if (TREE_CODE (val) != INTEGER_CST
-         && simple_iv_increment_p (stmt))
-       return;
+      /* Do not propagate copies into BIVs.
+         See PR23821 and PR62217 for how this can disturb IV and
+        number of iteration analysis.  */
+      if (TREE_CODE (val) != INTEGER_CST)
+       {
+         gimple def = SSA_NAME_DEF_STMT (op);
+         if (gimple_code (def) == GIMPLE_PHI
+             && gimple_bb (def)->loop_father->header == gimple_bb (def))
+           return;
+       }
 
       /* Dump details.  */
       if (dump_file && (dump_flags & TDF_DETAILS))

So it would just extend an existing heuristic.

Richard.

> Ok?
> 
> Thanks,
> Richard.
> 
> 2015-02-17  Richard Biener  <rguenther@suse.de>
> 
> 	* tree-ssa-dom.c (record_equivalences_from_phis): Valueize PHI arg.
> 	(record_const_or_copy_1): Valueize y.
> 	(record_equivalences_from_stmt): Valueize rhs.
> 	* tree-ssa-threadedge.c (simplify_control_stmt_condition):
> 	Remove repeated valueization.
> 
> Index: gcc/tree-ssa-dom.c
> ===================================================================
> --- gcc/tree-ssa-dom.c	(revision 220751)
> +++ gcc/tree-ssa-dom.c	(working copy)
> @@ -1223,6 +1223,13 @@ record_equivalences_from_phis (basic_blo
>  	  if (lhs == t)
>  	    continue;
>  
> +	  /* Valueize t.  */
> +	  if (TREE_CODE (t) == SSA_NAME)
> +	    {
> +	      tree tmp = SSA_NAME_VALUE (t);
> +	      t = tmp ? tmp : t;
> +	    }
> +
>  	  /* If we have not processed an alternative yet, then set
>  	     RHS to this alternative.  */
>  	  if (rhs == NULL)
> @@ -1566,6 +1573,13 @@ record_conditions (struct edge_info *edg
>  static void
>  record_const_or_copy_1 (tree x, tree y, tree prev_x)
>  {
> +  /* Valueize y.  */
> +  if (TREE_CODE (y) == SSA_NAME)
> +    {
> +      tree tmp = SSA_NAME_VALUE (y);
> +      y = tmp ? tmp : y;
> +    }
> +
>    set_ssa_name_value (x, y);
>  
>    if (dump_file && (dump_flags & TDF_DETAILS))
> @@ -2184,18 +2198,25 @@ record_equivalences_from_stmt (gimple st
>        if (may_optimize_p
>  	  && (TREE_CODE (rhs) == SSA_NAME
>  	      || is_gimple_min_invariant (rhs)))
> -      {
> -	if (dump_file && (dump_flags & TDF_DETAILS))
> -	  {
> -	    fprintf (dump_file, "==== ASGN ");
> -	    print_generic_expr (dump_file, lhs, 0);
> -	    fprintf (dump_file, " = ");
> -	    print_generic_expr (dump_file, rhs, 0);
> -	    fprintf (dump_file, "\n");
> -	  }
> +	{
> +	  /* Valueize rhs.  */
> +	  if (TREE_CODE (rhs) == SSA_NAME)
> +	    {
> +	      tree tmp = SSA_NAME_VALUE (rhs);
> +	      rhs = tmp ? tmp : rhs;
> +	    }
>  
> -	set_ssa_name_value (lhs, rhs);
> -      }
> +	  if (dump_file && (dump_flags & TDF_DETAILS))
> +	    {
> +	      fprintf (dump_file, "==== ASGN ");
> +	      print_generic_expr (dump_file, lhs, 0);
> +	      fprintf (dump_file, " = ");
> +	      print_generic_expr (dump_file, rhs, 0);
> +	      fprintf (dump_file, "\n");
> +	    }
> +
> +	  set_ssa_name_value (lhs, rhs);
> +	}
>      }
>  
>    /* Make sure we can propagate &x + CST.  */
> Index: gcc/tree-ssa-threadedge.c
> ===================================================================
> --- gcc/tree-ssa-threadedge.c	(revision 220751)
> +++ gcc/tree-ssa-threadedge.c	(working copy)
> @@ -591,29 +591,13 @@ simplify_control_stmt_condition (edge e,
>        cond_code = gimple_cond_code (stmt);
>  
>        /* Get the current value of both operands.  */
> -      if (TREE_CODE (op0) == SSA_NAME)
> -	{
> -	  for (int i = 0; i < 2; i++)
> -	    {
> -	      if (TREE_CODE (op0) == SSA_NAME
> -		  && SSA_NAME_VALUE (op0))
> -		op0 = SSA_NAME_VALUE (op0);
> -	      else
> -		break;
> -	    }
> -	}
> -
> -      if (TREE_CODE (op1) == SSA_NAME)
> -	{
> -	  for (int i = 0; i < 2; i++)
> -	    {
> -	      if (TREE_CODE (op1) == SSA_NAME
> -		  && SSA_NAME_VALUE (op1))
> -		op1 = SSA_NAME_VALUE (op1);
> -	      else
> -		break;
> -	    }
> -	}
> +      if (TREE_CODE (op0) == SSA_NAME
> +	  && SSA_NAME_VALUE (op0))
> +	op0 = SSA_NAME_VALUE (op0);
> +
> +      if (TREE_CODE (op1) == SSA_NAME
> +	  && SSA_NAME_VALUE (op1))
> +	op1 = SSA_NAME_VALUE (op1);
>  
>        if (handle_dominating_asserts)
>  	{
> @@ -682,22 +666,11 @@ simplify_control_stmt_condition (edge e,
>        tree original_lhs = cond;
>        cached_lhs = cond;
>  
> -      /* Get the variable's current value from the equivalence chains.
> -
> -	 It is possible to get loops in the SSA_NAME_VALUE chains
> -	 (consider threading the backedge of a loop where we have
> -	 a loop invariant SSA_NAME used in the condition.  */
> -      if (cached_lhs)
> -	{
> -	  for (int i = 0; i < 2; i++)
> -	    {
> -	      if (TREE_CODE (cached_lhs) == SSA_NAME
> -		  && SSA_NAME_VALUE (cached_lhs))
> -		cached_lhs = SSA_NAME_VALUE (cached_lhs);
> -	      else
> -		break;
> -	    }
> -	}
> +      /* Get the variable's current value from the equivalence chains.  */
> +      if (cached_lhs
> +	  && TREE_CODE (cached_lhs) == SSA_NAME
> +	  && SSA_NAME_VALUE (cached_lhs))
> +	cached_lhs = SSA_NAME_VALUE (cached_lhs);
>  
>        /* If we're dominated by a suitable ASSERT_EXPR, then
>  	 update CACHED_LHS appropriately.  */
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Jennifer Guild,
Dilip Upmanyu, Graham Norton HRB 21284 (AG Nuernberg)


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]