1 files changed, 112 insertions, 91 deletions

diff --git a/gcc/tree-ssa.c b/gcc/tree-ssa.c
index a5026e8ce44..70fe0d4db19 100644
--- a/gcc/tree-ssa.c
+++ b/gcc/tree-ssa.c
@@ -46,7 +46,6 @@ Boston, MA 02111-1307, USA.  */
 #include "tree-dump.h"
 #include "tree-pass.h"
 
-
 /* Remove edge E and remove the corresponding arguments from the PHI nodes
    in E's destination block.  */
 
@@ -573,7 +572,6 @@ tree_ssa_useless_type_conversion (tree expr)
   return false;
 }
 
-
 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
    described in walk_use_def_chains.  VISITED is a bitmap used to mark
    visited SSA_NAMEs to avoid infinite loops.  */
@@ -726,58 +724,106 @@ replace_immediate_uses (tree var, tree repl)
     }
 }
 
-/* Raises value of phi node PHI by joining it with VAL.  Processes immediate
-   uses of PHI recursively.  */
+/* Gets the value VAR is equivalent to according to EQ_TO.  */
 
-static void
-raise_value (tree phi, tree val, tree *eq_to)
+static tree
+get_eq_name (tree *eq_to, tree var)
 {
-  int i, n;
-  tree var = PHI_RESULT (phi), stmt;
-  int ver = SSA_NAME_VERSION (var);
-  dataflow_t df;
+  unsigned ver;
+  tree val = var;
 
-  if (eq_to[ver] == var)
-    return;
+  while (TREE_CODE (val) == SSA_NAME)
+    {
+      ver = SSA_NAME_VERSION (val);
+      if (!eq_to[ver])
+	break;
+
+      val = eq_to[ver];
+    }
 
-  switch (TREE_CODE (val))
+  while (TREE_CODE (var) == SSA_NAME)
     {
-    case SSA_NAME:
-    case REAL_CST:
-    case COMPLEX_CST:
-      break;
-    case INTEGER_CST:
-      if (TREE_CODE (TREE_TYPE (var)) != POINTER_TYPE)
+      ver = SSA_NAME_VERSION (var);
+      if (!eq_to[ver])
 	break;
 
-    default:
-      /* Do not propagate pointer constants.  This might require folding
-	 things like *&foo and rewriting the ssa, which is not worth the
-	 trouble.  */
-      val = var;
+      var = eq_to[ver];
+      eq_to[ver] = val;
     }
 
-  if (eq_to[ver])
+  return val;
+}
+
+/* Checks whether phi node PHI is redundant and if it is, records the ssa name
+   its result is redundant to to EQ_TO array.  */
+
+static void
+check_phi_redundancy (tree phi, tree *eq_to)
+{
+  tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
+  unsigned i, ver = SSA_NAME_VERSION (res), n;
+  dataflow_t df;
+
+  /* It is unlikely that such large phi node would be redundant.  */
+  if (PHI_NUM_ARGS (phi) > 16)
+    return;
+
+  for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
     {
-      if (operand_equal_p (eq_to[ver], val, 0))
+      def = PHI_ARG_DEF (phi, i);
+
+      switch (TREE_CODE (def))
+	{
+	case SSA_NAME:
+	  def = get_eq_name (eq_to, def);
+	  if (def == res)
+	    continue;
+	  break;
+
+	case REAL_CST:
+	case COMPLEX_CST:
+	  break;
+
+	case INTEGER_CST:
+	  if (TREE_CODE (TREE_TYPE (def)) != POINTER_TYPE)
+	    break;
+
+	default:
+	  /* Do not propagate pointer constants.  This might require folding
+	     things like *&foo and rewriting the ssa, which is not worth the
+	     trouble.  */
+	  return;
+	}
+
+      if (val
+	  && !operand_equal_p (val, def, 0))
 	return;
 
-      eq_to[ver] = var;
+      val = def;
     }
-  else
-    eq_to[ver] = val;
 
-  df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
+  /* At least one of the arguments should not be equal to the result, or
+     something strange is happening.  */
+  if (!val)
+    abort ();
+
+  if (get_eq_name (eq_to, res) == val)
+    return;
+
+  if (!may_propagate_copy (res, val))
+    return;
+
+  eq_to[ver] = val;
+
+  df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
   n = num_immediate_uses (df);
 
   for (i = 0; i < n; i++)
     {
       stmt = immediate_use (df, i);
 
-      if (TREE_CODE (stmt) != PHI_NODE)
-	continue;
-
-      raise_value (stmt, eq_to[ver], eq_to);
+      if (TREE_CODE (stmt) == PHI_NODE)
+	check_phi_redundancy (stmt, eq_to);
     }
 }
 
@@ -798,30 +844,21 @@ raise_value (tree phi, tree val, tree *eq_to)
    The most important effect of this pass is to remove degenerate PHI
    nodes created by removing unreachable code.  */
 
-static void
+void
 kill_redundant_phi_nodes (void)
 {
   tree *eq_to, *ssa_names;
-  unsigned i, ver, aver;
+  unsigned i;
   basic_block bb;
-  tree phi, t, stmt, var;
-
-  /* The EQ_TO array holds the current value of the ssa name in the
-     lattice:
-
-          top
-         / | \
-     const   variables
-         \ | /
-        bottom
-
-     Bottom is represented by NULL and top by the variable itself.
-
-     Once the dataflow stabilizes, we know that the phi nodes we need to keep
-     are exactly those with top as their result. 
-
-     The remaining phi nodes have their uses replaced with their value
-     in the lattice and the phi node itself is removed.  */
+  tree phi, var, repl, stmt;
+
+  /* The EQ_TO[VER] holds the value by that the ssa name VER should be
+     replaced.  If EQ_TO[VER] is ssa name and it is decided to replace it by
+     other value, it may be necessary to follow the chain till the final value.
+     We perform path shortening (replacing the entries of the EQ_TO array with
+     heads of these chains) whenever we access the field to prevent quadratic
+     complexity (probably would not occur in practice anyway, but let us play
+     it safe).  */
   eq_to = xcalloc (highest_ssa_version, sizeof (tree));
 
   /* The SSA_NAMES array holds each SSA_NAME node we encounter
@@ -844,51 +881,35 @@ kill_redundant_phi_nodes (void)
       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 	{
 	  var = PHI_RESULT (phi);
-	  ver = SSA_NAME_VERSION (var);
-	  ssa_names[ver] = var;
-
-	  for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
-	    {
-	      t = PHI_ARG_DEF (phi, i);
-
-	      if (TREE_CODE (t) != SSA_NAME)
-		{
-		  raise_value (phi, t, eq_to);
-		  continue;
-		}
-
-	      stmt = SSA_NAME_DEF_STMT (t);
-	      aver = SSA_NAME_VERSION (t);
-	      ssa_names[aver] = t;
-
-	      /* If the defining statement for this argument is not a
-		 phi node or the argument is associated with an abnormal
-		 edge, then we need to recursively start the forward
-		 dataflow starting with PHI.  */
-	      if (TREE_CODE (stmt) != PHI_NODE
-		  || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (t))
-		{
-		  eq_to[aver] = t;
-		  raise_value (phi, t, eq_to);
-		}
-	    }
+	  ssa_names[SSA_NAME_VERSION (var)] = var;
+	  check_phi_redundancy (phi, eq_to);
 	}
     }
 
   /* Now propagate the values.  */
   for (i = 0; i < highest_ssa_version; i++)
-    if (eq_to[i]
-	&& eq_to[i] != ssa_names[i])
-      replace_immediate_uses (ssa_names[i], eq_to[i]);
+    {
+      if (!ssa_names[i])
+	continue;
+
+      repl = get_eq_name (eq_to, ssa_names[i]);
+      if (repl != ssa_names[i])
+	replace_immediate_uses (ssa_names[i], repl);
+    }
 
   /* And remove the dead phis.  */
   for (i = 0; i < highest_ssa_version; i++)
-    if (eq_to[i]
-	&& eq_to[i] != ssa_names[i])
-      {
-	stmt = SSA_NAME_DEF_STMT (ssa_names[i]);
-	remove_phi_node (stmt, 0, bb_for_stmt (stmt));
-      }
+    {
+      if (!ssa_names[i])
+	continue;
+
+      repl = get_eq_name (eq_to, ssa_names[i]);
+      if (repl != ssa_names[i])
+	{
+	  stmt = SSA_NAME_DEF_STMT (ssa_names[i]);
+	  remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
+	}
+    }
 
   free_df ();
   free (eq_to);