Re: [PATCH] Fix PR middle-end/39976, 200.sixtrack degradation

["William J. Schmidt" <wschmidt at linux dot vnet dot ibm dot com>]

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.


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);