Patchwork Fix PR middle-end/39976, 200.sixtrack degradation

login
register
mail settings
Submitter William J. Schmidt
Date Dec. 2, 2011, 8:10 p.m.
Message ID <1322856650.29073.31.camel@gnopaine>
Download mbox | patch
Permalink /patch/128953/
State New
Headers show

Comments

William J. Schmidt - Dec. 2, 2011, 8:10 p.m.
OK, one more version.  This removes the basic block test and instead
implements Michael's suggestion:

On Fri, 2011-12-02 at 18:40 +0100, Michael Matz wrote:
> But I wonder why it's not enough to just do a push/pop sequence on 
> avail_exprs_stack around your new PHI processing in dom_opt_enter_block, 
> ala
> 
> +  VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
>    /* Create equivalences from redundant PHIs.  */
>    for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
>      eliminate_redundant_computations (&gsi);
> +  remove_local_expressions_from_table ();
> 
> on top of your current version.  That ought to remove the added PHI 
> expressions (and only them) from the hash table but retain the information 
> of equality in the const_or_copies_stack.  Checking the BB wouldn't be 
> required then.

Bootstrapped and regression tested on powerpc64-linux.

Thanks,
Bill


2011-12-02  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

	PR middle-end/39976
	* tree-ssa-dom.c (enum expr_kind): Add EXPR_PHI.
	(struct hashable_expr): Add struct phi field.
	(initialize_hash_element): Handle phis.
	(hashable_expr_equal_p): Likewise.
	(iterative_hash_hashable_expr): Likewise.
	(print_expr_hash_elt): Likewise.
	(dom_opt_enter_block): Create equivalences from redundant phis.
	(eliminate_redundant_computations): Handle redundant phis.
	(lookup_avail_expr): Handle phis.
Michael Matz - Dec. 5, 2011, 1:59 p.m.
Hi,

On Fri, 2 Dec 2011, William J. Schmidt wrote:

> > on top of your current version.  That ought to remove the added PHI 
> > expressions (and only them) from the hash table but retain the 
> > information of equality in the const_or_copies_stack.  Checking the BB 
> > wouldn't be required then.
> 
> Bootstrapped and regression tested on powerpc64-linux.

Another nit (sorry I didn't see this before :-/) :

> +      expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));

This leaks, because you missed to add freeing to free_expr_hash_elt.
Apart from that looks good to me, but I can't approve.


Ciao,
Michael.
William J. Schmidt - Dec. 5, 2011, 2:36 p.m.
On Mon, 2011-12-05 at 14:59 +0100, Michael Matz wrote:
> Hi,
> 
> On Fri, 2 Dec 2011, William J. Schmidt wrote:
> 
> > > on top of your current version.  That ought to remove the added PHI 
> > > expressions (and only them) from the hash table but retain the 
> > > information of equality in the const_or_copies_stack.  Checking the BB 
> > > wouldn't be required then.
> > 
> > Bootstrapped and regression tested on powerpc64-linux.
> 
> Another nit (sorry I didn't see this before :-/) :
> 
> > +      expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));
> 
> This leaks, because you missed to add freeing to free_expr_hash_elt.
> Apart from that looks good to me, but I can't approve.
> 

/facered :(

Thanks.  Will fix...

Bill

> 
> Ciao,
> Michael.
>
William J. Schmidt - Dec. 5, 2011, 2:52 p.m.
On Mon, 2011-12-05 at 08:36 -0600, William J. Schmidt wrote:
> 
> On Mon, 2011-12-05 at 14:59 +0100, Michael Matz wrote:
> > Hi,
> > 
> > On Fri, 2 Dec 2011, William J. Schmidt wrote:
> > 
> > > > on top of your current version.  That ought to remove the added PHI 
> > > > expressions (and only them) from the hash table but retain the 
> > > > information of equality in the const_or_copies_stack.  Checking the BB 
> > > > wouldn't be required then.
> > > 
> > > Bootstrapped and regression tested on powerpc64-linux.
> > 
> > Another nit (sorry I didn't see this before :-/) :
> > 
> > > +      expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));
> > 
> > This leaks, because you missed to add freeing to free_expr_hash_elt.
> > Apart from that looks good to me, but I can't approve.
> > 
> 
> /facered :(
> 
> Thanks.  Will fix...
> 
> Bill

Richard -- OK with this change?

> 
> > 
> > Ciao,
> > Michael.
> >
Richard Guenther - Dec. 8, 2011, 2:11 p.m.
On Mon, Dec 5, 2011 at 3:52 PM, William J. Schmidt
<wschmidt@linux.vnet.ibm.com> wrote:
>
>
> On Mon, 2011-12-05 at 08:36 -0600, William J. Schmidt wrote:
>>
>> On Mon, 2011-12-05 at 14:59 +0100, Michael Matz wrote:
>> > Hi,
>> >
>> > On Fri, 2 Dec 2011, William J. Schmidt wrote:
>> >
>> > > > on top of your current version.  That ought to remove the added PHI
>> > > > expressions (and only them) from the hash table but retain the
>> > > > information of equality in the const_or_copies_stack.  Checking the BB
>> > > > wouldn't be required then.
>> > >
>> > > Bootstrapped and regression tested on powerpc64-linux.
>> >
>> > Another nit (sorry I didn't see this before :-/) :
>> >
>> > > +      expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));
>> >
>> > This leaks, because you missed to add freeing to free_expr_hash_elt.
>> > Apart from that looks good to me, but I can't approve.
>> >
>>
>> /facered :(
>>
>> Thanks.  Will fix...
>>
>> Bill
>
> Richard -- OK with this change?

Yes.

Thanks,
Richard.

>>
>> >
>> > Ciao,
>> > Michael.
>> >
>
Jakub Jelinek - Dec. 8, 2011, 2:18 p.m.
On Thu, Dec 08, 2011 at 03:11:44PM +0100, Richard Guenther wrote:
> >> > Another nit (sorry I didn't see this before :-/) :
> >> >
> >> > > +      expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));
> >> >
> >> > This leaks, because you missed to add freeing to free_expr_hash_elt.
> >> > Apart from that looks good to me, but I can't approve.
> >> >
> >>
> >> /facered :(
> >>
> >> Thanks.  Will fix...
> >>
> >> Bill
> >
> > Richard -- OK with this change?
> 
> Yes.

But please use:
  expr->ops.phi.args = XCNEWVEC (tree, nargs);
instead of the above.

	Jakub
William J. Schmidt - Dec. 8, 2011, 2:43 p.m.
On Thu, 2011-12-08 at 15:18 +0100, Jakub Jelinek wrote:
> On Thu, Dec 08, 2011 at 03:11:44PM +0100, Richard Guenther wrote:
> > >> > Another nit (sorry I didn't see this before :-/) :
> > >> >
> > >> > > +      expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));
> > >> >
> > >> > This leaks, because you missed to add freeing to free_expr_hash_elt.
> > >> > Apart from that looks good to me, but I can't approve.
> > >> >
> > >>
> > >> /facered :(
> > >>
> > >> Thanks.  Will fix...
> > >>
> > >> Bill
> > >
> > > Richard -- OK with this change?
> > 
> > Yes.
> 
> But please use:
>   expr->ops.phi.args = XCNEWVEC (tree, nargs);
> instead of the above.

Good call.  This was copied from another xcalloc call nearby, so I will
plan to correct that one as well, as long as I'm in there.

Bill

> 
> 	Jakub
>

Patch

Index: gcc/tree-ssa-dom.c
===================================================================
--- gcc/tree-ssa-dom.c	(revision 181929)
+++ gcc/tree-ssa-dom.c	(working copy)
@@ -52,7 +52,8 @@  enum expr_kind
   EXPR_UNARY,
   EXPR_BINARY,
   EXPR_TERNARY,
-  EXPR_CALL
+  EXPR_CALL,
+  EXPR_PHI
 };
 
 struct hashable_expr
@@ -65,6 +66,7 @@  struct hashable_expr
     struct { enum tree_code op;  tree opnd0, opnd1; } binary;
     struct { enum tree_code op;  tree opnd0, opnd1, opnd2; } ternary;
     struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call;
+    struct { size_t nargs; tree *args; } phi;
   } ops;
 };
 
@@ -281,6 +283,19 @@  initialize_hash_element (gimple stmt, tree lhs,
       expr->kind = EXPR_SINGLE;
       expr->ops.single.rhs = gimple_goto_dest (stmt);
     }
+  else if (code == GIMPLE_PHI)
+    {
+      size_t nargs = gimple_phi_num_args (stmt);
+      size_t i;
+
+      expr->type = TREE_TYPE (gimple_phi_result (stmt));
+      expr->kind = EXPR_PHI;
+      expr->ops.phi.nargs = nargs;
+      expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));
+
+      for (i = 0; i < nargs; i++)
+        expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
+    }
   else
     gcc_unreachable ();
 
@@ -439,6 +454,21 @@  hashable_expr_equal_p (const struct hashable_expr
         return true;
       }
 
+    case EXPR_PHI:
+      {
+        size_t i;
+
+        if (expr0->ops.phi.nargs !=  expr1->ops.phi.nargs)
+          return false;
+
+        for (i = 0; i < expr0->ops.phi.nargs; i++)
+          if (! operand_equal_p (expr0->ops.phi.args[i],
+                                 expr1->ops.phi.args[i], 0))
+            return false;
+
+        return true;
+      }
+
     default:
       gcc_unreachable ();
     }
@@ -516,6 +546,15 @@  iterative_hash_hashable_expr (const struct hashabl
       }
       break;
 
+    case EXPR_PHI:
+      {
+        size_t i;
+
+        for (i = 0; i < expr->ops.phi.nargs; i++)
+          val = iterative_hash_expr (expr->ops.phi.args[i], val);
+      }
+      break;
+
     default:
       gcc_unreachable ();
     }
@@ -588,6 +627,22 @@  print_expr_hash_elt (FILE * stream, const struct e
           fprintf (stream, ")");
         }
         break;
+
+      case EXPR_PHI:
+        {
+          size_t i;
+          size_t nargs = element->expr.ops.phi.nargs;
+
+          fprintf (stream, "PHI <");
+          for (i = 0; i < nargs; i++)
+            {
+              print_generic_expr (stream, element->expr.ops.phi.args[i], 0);
+              if (i + 1 < nargs)
+                fprintf (stream, ", ");
+            }
+          fprintf (stream, ">");
+        }
+        break;
     }
   fprintf (stream, "\n");
 
@@ -1688,6 +1743,14 @@  dom_opt_enter_block (struct dom_walk_data *walk_da
   /* PHI nodes can create equivalences too.  */
   record_equivalences_from_phis (bb);
 
+  /* Create equivalences from redundant PHIs.  PHIs are only truly
+     redundant when they exist in the same block, so push another
+     marker and unwind right afterwards.  */
+  VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
+  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    eliminate_redundant_computations (&gsi);
+  remove_local_expressions_from_table ();
+
   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     optimize_stmt (bb, gsi);
 
@@ -1818,12 +1881,16 @@  eliminate_redundant_computations (gimple_stmt_iter
 {
   tree expr_type;
   tree cached_lhs;
+  tree def;
   bool insert = true;
   bool assigns_var_p = false;
 
   gimple stmt = gsi_stmt (*gsi);
 
-  tree def = gimple_get_lhs (stmt);
+  if (gimple_code (stmt) == GIMPLE_PHI)
+    def = gimple_phi_result (stmt);
+  else
+    def = gimple_get_lhs (stmt);
 
   /* Certain expressions on the RHS can be optimized away, but can not
      themselves be entered into the hash tables.  */
@@ -1857,6 +1924,16 @@  eliminate_redundant_computations (gimple_stmt_iter
     }
   else if (gimple_code (stmt) == GIMPLE_SWITCH)
     expr_type = TREE_TYPE (gimple_switch_index (stmt));
+  else if (gimple_code (stmt) == GIMPLE_PHI)
+    /* We can't propagate into a phi, so the logic below doesn't apply.
+       Instead record an equivalence between the cached LHS and the
+       PHI result of this statement, provided they are in the same block.
+       This should be sufficient to kill the redundant phi.  */
+    {
+      if (def && cached_lhs)
+	record_const_or_copy (def, cached_lhs);
+      return;
+    }
   else
     gcc_unreachable ();
 
@@ -2299,8 +2376,11 @@  lookup_avail_expr (gimple stmt, bool insert)
   tree temp;
   struct expr_hash_elt element;
 
-  /* Get LHS of assignment or call, else NULL_TREE.  */
-  lhs = gimple_get_lhs (stmt);
+  /* Get LHS of phi, assignment, or call; else NULL_TREE.  */
+  if (gimple_code (stmt) == GIMPLE_PHI)
+    lhs = gimple_phi_result (stmt);
+  else
+    lhs = gimple_get_lhs (stmt);
 
   initialize_hash_element (stmt, lhs, &element);