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 Fri, 24 Apr 2015, Jeff Law wrote:

> On 02/17/2015 07:58 AM, Richard Biener wrote:
> [ Restarting a old thread... ]
> 
> > On a closer look the record_const_or_copy_1 hunk is redundant
> > (record_equality is really a bit obfuscated...).
> Agreed.  I'm not entirely sure how it got to this point.
> 
> > 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).
> Right.  In general, the fact that we're in SSA form means that we ought not
> get loops in the SSA_NAME_VALUE chain since there's a single static assignment
> and we'll visit it once.
> 
> That nice model breaks down in two ways.  First we derive equivalences from
> equality conditions like you've shown above.  Second, when threading we can
> thread through a loop latch and start reprocessing a block.  The interaction
> between those two can result in loops in the value chain.
> 
> What I'm hoping to do in GCC6 is eliminate all this stuff with a threader that
> is independent of the dominator walk (and optimizer). Instead of walking
> forward through the dominator tree recording key nuggets, then removing those
> nuggets as we pop back up the tree, we instead we start with the conditional
> and walk up the use-def chains, simplifying as we go, with the goal of
> simplifying to a constant, of course.
> 
> You can see the beginnings of that with the FSM bits from Sebastian.
> 
> Obviously until those bits are in place, we should try to clean up any warts
> in the current implementation.
> 
> > 
> > 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.
> Agreed.  Makes perfect sense.

I'm now re-bootstrapping and testing the following.

Richard.

2015-04-27  Richard Biener  <rguenther@suse.de>

	* tree-ssa-dom.c (record_equivalences_from_phis): Valueize PHI arg.
	(record_equivalences_from_stmt): Valueize rhs.
	(record_equality): Canonicalize x and y order via
	tree_swap_operands_p.  Do not swap operands for same loop depth.

Index: gcc/tree-ssa-dom.c
===================================================================
*** gcc/tree-ssa-dom.c	(revision 222360)
--- gcc/tree-ssa-dom.c	(working copy)
*************** record_equivalences_from_phis (basic_blo
*** 1519,1524 ****
--- 1519,1531 ----
  	  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)
*************** record_equality (tree x, tree y)
*** 1752,1757 ****
--- 1759,1767 ----
  {
    tree prev_x = NULL, prev_y = NULL;
  
+   if (tree_swap_operands_p (x, y, false))
+     std::swap (x, y);
+ 
    if (TREE_CODE (x) == SSA_NAME)
      prev_x = SSA_NAME_VALUE (x);
    if (TREE_CODE (y) == SSA_NAME)
*************** record_equality (tree x, tree y)
*** 1766,1772 ****
    else if (is_gimple_min_invariant (x)
  	   /* ???  When threading over backedges the following is important
  	      for correctness.  See PR61757.  */
! 	   || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
      prev_x = x, x = y, y = prev_x, prev_x = prev_y;
    else if (prev_x && is_gimple_min_invariant (prev_x))
      x = y, y = prev_x, prev_x = prev_y;
--- 1776,1782 ----
    else if (is_gimple_min_invariant (x)
  	   /* ???  When threading over backedges the following is important
  	      for correctness.  See PR61757.  */
! 	   || (loop_depth_of_name (x) < loop_depth_of_name (y)))
      prev_x = x, x = y, y = prev_x, prev_x = prev_y;
    else if (prev_x && is_gimple_min_invariant (prev_x))
      x = y, y = prev_x, prev_x = prev_y;
*************** record_equivalences_from_stmt (gimple st
*** 2128,2145 ****
        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");
! 	  }
  
! 	set_ssa_name_value (lhs, rhs);
!       }
      }
  
    /* Make sure we can propagate &x + CST.  */
--- 2138,2162 ----
        if (may_optimize_p
  	  && (TREE_CODE (rhs) == SSA_NAME
  	      || is_gimple_min_invariant (rhs)))
! 	{
! 	  /* Valueize rhs.  */
! 	  if (TREE_CODE (rhs) == SSA_NAME)
! 	    {
! 	      tree tmp = SSA_NAME_VALUE (rhs);
! 	      rhs = tmp ? tmp : 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 Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]