This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] Merge PHI nodes. (Take 2)


Hi,

Attached is a revised version of the patch

http://gcc.gnu.org/ml/gcc-patches/2004-12/msg01587.html

I merged tree_forwarder_block_with_phi_p into tree_forwarder_block_p
by adding a new argument PHI_WANTED_P.  That was easy.

I attempted to merge remove_forwarder_block_with_phi into
remove_forwarder_block, but that seemed to be more trouble than
anything else.

For example, we cannot handle abnormal edges in
remove_forwarder_block_with_phi.  remove_forwarder_block contains

  if (has_abnormal_incoming_edge_p (bb))
    {
      seen_abnormal_edge = true;

      if (has_abnormal_incoming_edge_p (dest)
	  || phi_nodes (dest) != NULL_TREE)
	return false;
    }

If we are merging two PHI nodes, the inner "if" condition is always
true because phi_nodes (dest) must be nonzero, so the whole outer "if"
block does not apply to remove_forwarder_block_with_phi.

Here is another example.  remove_forwarder_block contains

  /* If there are phi nodes in DEST, and some of the blocks that are
     predecessors of BB are also predecessors of DEST, check that the
     phi node arguments match.  */
  if (phi_nodes (dest))
    {
      FOR_EACH_EDGE (e, ei, bb->preds)
	{
	  s = find_edge (e->src, dest);
	  if (!s)
	    continue;

	  if (!phi_alternatives_equal (dest, succ, s))
	    return false;
	}
    }

We handle this case in remove_forwarder_block_with_phi quite
differently.  Specifically, if we already have an edge S from E->src
to DEST, and S and E->dest's sole successor edge do not have the same
PHI arguments at DEST, we split edge E to create a forwarder block so
that we can merge PHI nodes.  It wouldn't make sense to do the same in
remove_forwarder_block because its purpose is to *remove* a forwarder
block.  It shouldn't create new ones.

Last but not least, the code to redirect each edge flowing into a
forwarder block is, again, quite different.  If we are mering PHI
nodes, we need to go through PENDING_STMT to remove mentions of the
PHI node being removed.  Otherwise, we don't have to worry about
PENDING_STMT.

So what could we possibly share?  We could share the first two "if"
statements, the check for infinite loops and nonlocal labels.  We
could also share the dominator updating code, but we cannot share the
main dish, the loop to redirect every incoming edge, without adding a
lot of "if" statements.

We could factor out the sharable part as functions if you like, but
even then, the big point would be missing; we would not be sharing the
main loop.

Here is the new timing in seconds of five runs of ./cc1 -quiet -O2 -o
/dev/null.

               original patched
fold-const.i     64.904  64.799 (0.161% down)
combine.i        26.707  26.629 (0.292% down)
reload1.i        22.362  22.274 (0.393% down)
reload.i         22.877  22.600 (1.210% down)
insn-attrtab.i  313.568 312.507 (0.338% down)

which is fairly consistent with the previous version of this patch.

http://gcc.gnu.org/ml/gcc-patches/2004-12/msg01587.html

Tested on i686-pc-linux-gnu.  OK to apply?

2005-01-19  Kazu Hirata  <kazu@cs.umass.edu>

	PR tree-optimization/15349
	* timevar.def (TV_TREE_MERGE_PHI): New.
	* tree-cfg.c (tree_forwarder_block_p): Add a new argument
	PHI_WANTED.
	(remove_forwarder_block, cleanup_forwarder_blocks): Adjust the
	calls to tree_forwarder_block_p.
	(remove_forwarder_block_with_phi, merge_phi_nodes,
	gate_merge_phi, pass_merge_phi): New.
	* tree-optimize.c (init_tree_optimization_passes): Add
	pass_merge_phi.
	* tree-pass.h: Add an extern for pass_merge_phi;

Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.41
diff -u -d -p -r1.41 timevar.def
--- timevar.def	29 Nov 2004 00:03:40 -0000	1.41
+++ timevar.def	18 Jan 2005 10:48:48 -0000
@@ -83,6 +83,7 @@ DEFTIMEVAR (TV_TREE_FORWPROP	     , "tre
 DEFTIMEVAR (TV_TREE_DCE		     , "tree conservative DCE")
 DEFTIMEVAR (TV_TREE_CD_DCE	     , "tree aggressive DCE")
 DEFTIMEVAR (TV_TREE_DSE		     , "tree DSE")
+DEFTIMEVAR (TV_TREE_MERGE_PHI	     , "PHI merge")
 DEFTIMEVAR (TV_TREE_LOOP	     , "tree loop optimization")
 DEFTIMEVAR (TV_TREE_LOOP_BOUNDS	     , "tree record loop bounds")
 DEFTIMEVAR (TV_LIM                   , "loop invariant motion")
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.139
diff -u -d -p -r2.139 tree-cfg.c
--- tree-cfg.c	17 Jan 2005 18:44:18 -0000	2.139
+++ tree-cfg.c	18 Jan 2005 10:48:49 -0000
@@ -119,7 +119,7 @@ static void split_critical_edges (void);
 static inline bool stmt_starts_bb_p (tree, tree);
 static int tree_verify_flow_info (void);
 static void tree_make_forwarder_block (edge);
-static bool tree_forwarder_block_p (basic_block);
+static bool tree_forwarder_block_p (basic_block, bool);
 static void tree_cfg2vcg (FILE *);
 
 /* Flowgraph optimization and cleanup.  */
@@ -3889,16 +3889,15 @@ tree_make_forwarder_block (edge fallthru
    ENTRY_BLOCK_PTR.  */
 
 static bool
-tree_forwarder_block_p (basic_block bb)
+tree_forwarder_block_p (basic_block bb, bool phi_wanted)
 {
   block_stmt_iterator bsi;
 
   /* BB must have a single outgoing edge.  */
   if (EDGE_COUNT (bb->succs) != 1
-      /* BB can not have any PHI nodes.  This could potentially be
-	 relaxed early in compilation if we re-rewrote the variables
-	 appearing in any PHI nodes in forwarder blocks.  */
-      || phi_nodes (bb)
+      /* If PHI_WANTED is false, BB must not have any PHI nodes.
+	 Otherwise, BB must have PHI nodes.  */
+      || (phi_nodes (bb) != NULL_TREE) != phi_wanted
       /* BB may not be a predecessor of EXIT_BLOCK_PTR.  */
       || EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR
       /* Nor should this be an infinite loop.  */
@@ -4040,7 +4039,7 @@ remove_forwarder_block (basic_block bb, 
 	     that it was not a forwarder before, since it used to have
 	     at least two outgoing edges, so we may just add it to
 	     worklist.  */
-	  if (tree_forwarder_block_p (s->src))
+	  if (tree_forwarder_block_p (s->src, false))
 	    *(*worklist)++ = s->src;
 	}
     }
@@ -4097,7 +4096,7 @@ cleanup_forwarder_blocks (void)
 
   FOR_EACH_BB (bb)
     {
-      if (tree_forwarder_block_p (bb))
+      if (tree_forwarder_block_p (bb, false))
 	*current++ = bb;
     }
 
@@ -4111,6 +4110,206 @@ cleanup_forwarder_blocks (void)
   return changed;
 }
 
+/* Merge the PHI nodes at BB into those at BB's sole successor.  */
+
+static void
+remove_forwarder_block_with_phi (basic_block bb)
+{
+  edge succ = EDGE_SUCC (bb, 0);
+  basic_block dest = succ->dest;
+  tree label;
+  basic_block dombb, domdest, dom;
+
+  /* We check for infinite loops already in tree_forwarder_block_p.
+     However it may happen that the infinite loop is created
+     afterwards due to removal of forwarders.  */
+  if (dest == bb)
+    return;
+
+  /* If the destination block consists of an nonlocal label, do not merge
+     it.  */
+  label = first_stmt (dest);
+  if (label
+      && TREE_CODE (label) == LABEL_EXPR
+      && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
+    return;
+
+  /* Redirect each incoming edge to BB to DEST.  */
+  while (EDGE_COUNT (bb->preds) > 0)
+    {
+      edge e = EDGE_PRED (bb, 0), s;
+      tree phi;
+
+      s = find_edge (e->src, dest);
+      if (s)
+	{
+	  /* We already have an edge S from E->src to DEST.  If S and
+	     E->dest's sole successor edge have the same PHI arguments
+	     at DEST, redirect S to DEST.  */
+	  if (phi_alternatives_equal (dest, s, succ))
+	    {
+	      e = redirect_edge_and_branch (e, dest);
+	      PENDING_STMT (e) = NULL_TREE;
+	      continue;
+	    }
+
+	  /* PHI arguemnts are different.  Create a forwarder block by
+	     splitting E so that we can merge PHI arguments on E to
+	     DEST.  */
+	  e = EDGE_SUCC (split_edge (e), 0);
+	}
+
+      s = redirect_edge_and_branch (e, dest);
+
+      /* redirect_edge_and_branch must not create a new edge.  */
+      gcc_assert (s == e);
+
+      /* Add to the PHI nodes at DEST each PHI argument removed at the
+	 destination of E.  */
+      for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
+	{
+	  tree def = PHI_ARG_DEF (phi, succ->dest_idx);
+
+	  if (TREE_CODE (def) == SSA_NAME)
+	    {
+	      tree var;
+
+	      /* If DEF is one of the results of PHI nodes removed during
+		 redirection, replace it with the PHI argument that used
+		 to be on E.  */
+	      for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
+		{
+		  tree old_arg = TREE_PURPOSE (var);
+		  tree new_arg = TREE_VALUE (var);
+
+		  if (def == old_arg)
+		    {
+		      def = new_arg;
+		      break;
+		    }
+		}
+	    }
+
+	  add_phi_arg (phi, def, s);
+	}
+
+      PENDING_STMT (e) = NULL;
+    }
+
+  /* Update the dominators.  */
+  dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
+  domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
+  if (domdest == bb)
+    {
+      /* Shortcut to avoid calling (relatively expensive)
+	 nearest_common_dominator unless necessary.  */
+      dom = dombb;
+    }
+  else
+    dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
+
+  set_immediate_dominator (CDI_DOMINATORS, dest, dom);
+  
+  /* Remove BB since all of BB's incoming edges have been redirected
+     to DEST.  */
+  delete_basic_block (bb);
+}
+
+/* This pass performs merges PHI nodes if one feeds into another.  For
+   example, suppose we have the following:
+
+  goto <bb 9> (<L9>);
+
+<L8>:;
+  tem_17 = foo ();
+
+  # tem_6 = PHI <tem_17(8), tem_23(7)>;
+<L9>:;
+
+  # tem_3 = PHI <tem_6(9), tem_2(5)>;
+<L10>:;
+
+  Then we merge the first PHI node into the second one like so:
+
+  goto <bb 9> (<L10>);
+
+<L8>:;
+  tem_17 = foo ();
+
+  # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
+<L10>:;
+*/
+
+static void
+merge_phi_nodes (void)
+{
+  basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
+  basic_block *current = worklist;
+  basic_block bb;
+
+  calculate_dominance_info (CDI_DOMINATORS);
+
+  /* Find all PHI nodes that we may be able to merge.  */
+  FOR_EACH_BB (bb)
+    {
+      basic_block dest;
+
+      /* Look for a forwarder block with PHI nodes.  */
+      if (!tree_forwarder_block_p (bb, true))
+	continue;
+
+      dest = EDGE_SUCC (bb, 0)->dest;
+
+      /* We have to feed into another basic block with PHI
+	 nodes.  */
+      if (!phi_nodes (dest)
+	  /* We don't want to deal with a basic block with
+	     abnormal edges.  */
+	  || has_abnormal_incoming_edge_p (bb))
+	continue;
+
+      if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
+	{
+	  /* If BB does not dominate DEST, then the PHI nodes at
+	     DEST must be the only users of the results of the PHI
+	     nodes at BB.  */
+	  *current++ = bb;
+	}
+    }
+
+  /* Now let's drain WORKLIST.  */
+  while (current != worklist)
+    {
+      bb = *--current;
+      remove_forwarder_block_with_phi (bb);
+    }
+
+  free (worklist);
+}
+
+static bool
+gate_merge_phi (void)
+{
+  return 1;
+}
+
+struct tree_opt_pass pass_merge_phi = {
+  "mergephi",			/* name */
+  gate_merge_phi,		/* gate */
+  merge_phi_nodes,		/* execute */
+  NULL,				/* sub */
+  NULL,				/* next */
+  0,				/* static_pass_number */
+  TV_TREE_MERGE_PHI,		/* tv_id */
+  PROP_cfg | PROP_ssa,		/* properties_required */
+  0,				/* properties_provided */
+  0,				/* properties_destroyed */
+  0,				/* todo_flags_start */
+  TODO_dump_func | TODO_ggc_collect	/* todo_flags_finish */
+  | TODO_verify_ssa,
+  0				/* letter */
+};
+
 /* Return a non-special label in the head of basic block BLOCK.
    Create one if it doesn't exist.  */
 
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.67
diff -u -d -p -r2.67 tree-optimize.c
--- tree-optimize.c	4 Jan 2005 01:54:26 -0000	2.67
+++ tree-optimize.c	18 Jan 2005 10:48:49 -0000
@@ -354,6 +354,7 @@ init_tree_optimization_passes (void)
   NEXT_PASS (pass_dominator);
   NEXT_PASS (pass_redundant_phi);
   NEXT_PASS (pass_dce);
+  NEXT_PASS (pass_merge_phi);
   NEXT_PASS (pass_forwprop);
   NEXT_PASS (pass_phiopt);
   NEXT_PASS (pass_may_alias);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.23
diff -u -d -p -r2.23 tree-pass.h
--- tree-pass.h	4 Jan 2005 01:54:26 -0000	2.23
+++ tree-pass.h	18 Jan 2005 10:48:49 -0000
@@ -142,7 +142,8 @@ extern struct tree_opt_pass pass_del_ssa
 extern struct tree_opt_pass pass_dominator;
 extern struct tree_opt_pass pass_dce;
 extern struct tree_opt_pass pass_cd_dce;
+extern struct tree_opt_pass pass_merge_phi;
 extern struct tree_opt_pass pass_may_alias;
 extern struct tree_opt_pass pass_split_crit_edges;
 extern struct tree_opt_pass pass_pre;
--- /dev/null	2004-12-11 18:32:38.815792656 -0500
+++ testsuite/gcc.dg/tree-ssa/pr15349.c	2005-01-18 12:18:38.000000000 -0500
@@ -0,0 +1,25 @@
+/* PR 15349.  Merge two PHI nodes.  */
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-mergephi" } */
+
+int
+foo (int a, int b)
+{
+  int t;
+
+  if (b)
+    {
+      if (a)
+	t = 3;
+      else
+	t = 5;
+
+      a = 0;
+    }
+  else
+    t = 7;
+
+  return t;
+}
+
+/* { dg-final { scan-tree-dump-times "PHI" 1 "mergephi"} } */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]