Re: [PATCH] Fix PR50204

[Richard Guenther <rguenther at suse dot de>]

On Wed, 12 Oct 2011, Michael Matz wrote:

> Hi,
> 
> On Tue, 11 Oct 2011, Richard Guenther wrote:
> 
> > Since we have the alias oracle we no longer optimize the testcase below 
> > because I initially restricted the stmt walking to give up for PHIs with 
> > more than 2 arguments because of compile-time complexity issues. But 
> > it's easy to see that compile-time is not an issue when we reduce PHI 
> > args pairwise to a single dominating operand.
> 
> Of course it is, not a different complexity class, but a constant factor.  
> You have to do N-1 pairwise reductions, meaning with a large fan-in block 
> you pay N-1 times the price, not just once for one pair, and if the price 
> happens to be walking all up to the function start you indeed then are at 
> N*M.  I think there should be a cutoff, possibly not at two.  Think about 
> the generated testcases with many large switches.

Indeed we can do a little better by also caching at possible
branches.  The easiest is to have cache points at the first
store we visit in a basic-block (thus we have at most two bits
in the visited bitmap per BB).  We can also make the result
(more) independent on the order of PHI arguments by disambiguating
against a VUSE that (possibly) dominates all other VUSEs.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.

Richard.

2011-10-12  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-alias.c (maybe_skip_until): Cache also at the point
	of the first store we visit in a basic-block.
	(get_continuation_for_phi): Search for a candidate VUSE that
	might dominates all others.  Do pairwise disambiguation against
	that candidate.

Index: gcc/tree-ssa-alias.c
===================================================================
--- gcc/tree-ssa-alias.c	(revision 179849)
+++ gcc/tree-ssa-alias.c	(working copy)
@@ -1846,6 +1846,8 @@ static bool
 maybe_skip_until (gimple phi, tree target, ao_ref *ref,
 		  tree vuse, bitmap *visited)
 {
+  basic_block bb = gimple_bb (phi);
+
   if (!*visited)
     *visited = BITMAP_ALLOC (NULL);
 
@@ -1870,6 +1872,14 @@ maybe_skip_until (gimple phi, tree targe
       else if (gimple_nop_p (def_stmt)
 	       || stmt_may_clobber_ref_p_1 (def_stmt, ref))
 	return false;
+      /* If we reach a new basic-block see if we already skipped it
+         in a previous walk that ended successfully.  */
+      if (gimple_bb (def_stmt) != bb)
+	{
+	  if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (vuse)))
+	    return true;
+	  bb = gimple_bb (def_stmt);
+	}
       vuse = gimple_vuse (def_stmt);
     }
   return true;
@@ -1948,18 +1958,35 @@ get_continuation_for_phi (gimple phi, ao
      until we hit the phi argument definition that dominates the other one.  */
   else if (nargs >= 2)
     {
-      tree arg0 = PHI_ARG_DEF (phi, 0);
-      tree arg1;
-      unsigned i = 1;
-      do
+      tree arg0, arg1;
+      unsigned i;
+
+      /* Find a candidate for the virtual operand which definition
+	 dominates those of all others.  */
+      arg0 = PHI_ARG_DEF (phi, 0);
+      if (!SSA_NAME_IS_DEFAULT_DEF (arg0))
+	for (i = 1; i < nargs; ++i)
+	  {
+	    arg1 = PHI_ARG_DEF (phi, i);
+	    if (SSA_NAME_IS_DEFAULT_DEF (arg1))
+	      {
+		arg0 = arg1;
+		break;
+	      }
+	    if (dominated_by_p (CDI_DOMINATORS,
+				gimple_bb (SSA_NAME_DEF_STMT (arg0)),
+				gimple_bb (SSA_NAME_DEF_STMT (arg1))))
+	      arg0 = arg1;
+	  }
+
+      /* Then pairwise reduce against the found candidate.  */
+      for (i = 0; i < nargs; ++i)
 	{
 	  arg1 = PHI_ARG_DEF (phi, i);
 	  arg0 = get_continuation_for_phi_1 (phi, arg0, arg1, ref, visited);
 	  if (!arg0)
 	    return NULL_TREE;
-
 	}
-      while (++i < nargs);
 
       return arg0;
     }