Re: [PATCH] Fix parts of PR61607

[Richard Biener <rguenther@suse.de>]

On Thu, 26 Jun 2014, Richard Biener wrote:

> On Thu, 26 Jun 2014, Richard Biener wrote:
> 
> > On Wed, 25 Jun 2014, Jeff Law wrote:
> > 
> > > On 06/25/14 08:05, Richard Biener wrote:
> > > > 
> > > > This removes restrictions in DOM cprop_operand that inhibit
> > > > some optimizations.  The volatile pointer thing is really realy
> > > > old and no longer necessary while the loop-depth consideration
> > > > is only valid for loop-closed PHI nodes (but we're not in
> > > > loop-closed SSA in DOM) - the coalescing is handled in out-of-SSA
> > > > phase by inserting copies appropriately.
> > > > 
> > > > Bootstrapped on x86_64-unknown-linux-gnu, ok?
> > > > 
> > > > Thanks,
> > > > Richard.
> > > > 
> > > > 2014-06-25  Richard Biener  <rguenther@suse.de>
> > > > 
> > > > 	PR tree-optimization/61607
> > > > 	* tree-ssa-dom.c (cprop_operand): Remove restriction on
> > > > 	propagating volatile pointers and on loop depth.
> > > The first hunk is OK.
> > > 
> > > I thought we had tests for the do not copy propagate out of a loop nest in the
> > > suite.  Did you check that tests in BZ 19038 still generate good code after
> > > this change?  If we still generate good code for those tests, then this hunk
> > > is fine too.
> > 
> > I have applied the first hunk and will investigate further.  Testing 
> > didn't show any issue and I know how to retain the check but not
> > cause the missed optimization shown in PR61607.
> 
> Let's try to summarize what the restriction is supposed to avoid.
> It tries to avoid introducing uses of SSA names defined inside a
> loop outside of it because if the SSA name is live over the backedge
> we will then have an overlapping life-range which prevents out-of-SSA
> from coalescing it to a single register.
> 
> Now, the existing test is not working in that way.
> 
> Rather the best way we have to ensure this property (all outside
> uses go through a copy that is placed on exit edges rather than
> possibly on the backedge) is to go into loop-closed SSA form.
> This is also where the PHI nodes that confuse DOM in PR61607
> come from in the first place.
> 
> Now as the existing measure is ineffective in some cases out-of-SSA
> has gotten the ability to deal with this (or a subset):
> 
>   /* If elimination of a PHI requires inserting a copy on a backedge,
>      then we will have to split the backedge which has numerous
>      undesirable performance effects.
> 
>      A significant number of such cases can be handled here by inserting
>      copies into the loop itself.  */
>   insert_backedge_copies ();
> 
> now, this doesn't seem to deal with outside uses.  But eventually
> the coalescing code already assigns proper cost to backedge copies
> so that we choose to place copies on the exit edges rather than
> the backedge ones - seems not so from looking at coalesce_cost_edge.
> 
> So I think that we should remove the copy-propagation restrictions
> and instead address this in out-of-SSA.
> 
> For now the following patch retains the exact same restriction in
> DOM as it is present in copyprop (but not in FRE - ok my recent fault,
> or in VRP).  By avoiding to record the equivalency for PHIs
> (where we know that either all or no uses should be covered by
> the loop depth check) we retain the ability to record the equivalency
> for the two loop exit PHI nodes and thus the threading (if only
> on the false path).
> 
> Bootstrap and regtest running on x86_64-unknown-linux-gnu.
> 
> I'll try to see what happens to the PR19038 testcases (though
> that PR is a mess ...)

I checked the very original one (thin6d.f from sixtrack) and the
generated assembly for -Ofast is the same without any patch
and with _all_ loop_depth_of_name restrictions removed from
both DOM and copyprop (thus making loop_depth_of_name dead).

The cost of out-of-SSA copies for backedges (or in the case
of the PR, loop latch edges causing an edge split) is dealt
with by

  /* Inserting copy on critical edge costs more than inserting it 
elsewhere.  */
  if (EDGE_CRITICAL_P (e))
    mult = 2;

in coalesce_cost_edge.

So in the end, without a testcase to investigate, I'd propose
to get rid of those restrictions.  I'm still going forward
with the patch below for now.

Richard.

> Richard.
> 
> 2014-06-26  Richard Biener  <rguenther@suse.de>
> 
> 	PR tree-optimization/61607
> 	* tree-ssa-copy.c (copy_prop_visit_phi_node): Adjust comment
> 	explaining why we restrict copies on loop depth.
> 	* tree-ssa-dom.c (cprop_operand): Remove restriction on
> 	on loop depth.
> 	(record_equivalences_from_phis): Instead add it here.
> 
> 	* gcc.dg/tree-ssa/ssa-dom-thread-5.c: New testcase.
> 
> Index: gcc/tree-ssa-copy.c
> ===================================================================
> --- gcc/tree-ssa-copy.c	(revision 212012)
> +++ gcc/tree-ssa-copy.c	(working copy)
> @@ -401,11 +401,8 @@ copy_prop_visit_phi_node (gimple phi)
>  	arg_value = valueize_val (arg);
>  
>        /* Avoid copy propagation from an inner into an outer loop.
> -	 Otherwise, this may move loop variant variables outside of
> -	 their loops and prevent coalescing opportunities.  If the
> -	 value was loop invariant, it will be hoisted by LICM and
> -	 exposed for copy propagation.
> -	 ???  The value will be always loop invariant.
> +	 Otherwise, this may introduce uses of loop variant variables
> +	 outside of their loops and prevent coalescing opportunities.
>  	 In loop-closed SSA form do not copy-propagate through
>  	 PHI nodes in blocks with a loop exit edge predecessor.  */
>        if (TREE_CODE (arg_value) == SSA_NAME
> Index: gcc/tree-ssa-dom.c
> ===================================================================
> --- gcc/tree-ssa-dom.c	(revision 212013)
> +++ gcc/tree-ssa-dom.c	(working copy)
> @@ -1234,7 +1234,13 @@ record_equivalences_from_phis (basic_blo
>  	 this, since this is a true assignment and not an equivalence
>  	 inferred from a comparison.  All uses of this ssa name are dominated
>  	 by this assignment, so unwinding just costs time and space.  */
> -      if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs))
> +      if (i == gimple_phi_num_args (phi)
> +	  && may_propagate_copy (lhs, rhs)
> +	  /* Do not propagate copies if the propagated value is at a deeper loop
> +	     depth than the propagatee.  Otherwise, this may introduce uses
> +	     of loop variant variables outside of their loops and prevent
> +	     coalescing opportunities.  */
> +	  && !(loop_depth_of_name (rhs) > loop_depth_of_name (lhs)))
>  	set_ssa_name_value (lhs, rhs);
>      }
>  }
> @@ -2247,14 +2253,6 @@ cprop_operand (gimple stmt, use_operand_
>        if (!may_propagate_copy (op, val))
>  	return;
>  
> -      /* Do not propagate copies if the propagated value is at a deeper loop
> -	 depth than the propagatee.  Otherwise, this may move loop variant
> -	 variables outside of their loops and prevent coalescing
> -	 opportunities.  If the value was loop invariant, it will be hoisted
> -	 by LICM and exposed for copy propagation.  */
> -      if (loop_depth_of_name (val) > loop_depth_of_name (op))
> -	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
> Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-5.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-5.c	(revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-5.c	(working copy)
> @@ -0,0 +1,23 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Os -fno-tree-fre -fdump-tree-dom1-details" } */
> +
> +void foo(int *);
> +void f2(int dst[3], int R)
> +{
> +  int i, inter[2];
> +  _Bool inter0p = 0;
> +  _Bool inter1p = 0;
> +  for (i = 1; i < R; i++)
> +    {
> +      inter0p = 1;
> +      inter1p = 1;
> +    }
> +  if (inter0p)
> +    inter[0] = 1;
> +  if (inter1p)
> +    inter[1] = 1;
> +  foo(inter);
> +}
> +
> +/* { dg-final { scan-tree-dump "Threaded jump" "dom1" } } */
> +/* { dg-final { cleanup-tree-dump "dom1" } } */
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer