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] O(1) PHI argument look-up - Part 3/n (take 2)


Hi,

Attached is a patch to part 3 of my O(1) PHI argument look-up patch.

When a PHI array is lined up with its corresponding edge vector in
near future, an edge vector and a PHI array are syncronized.  That is,
they grow and shrink at the same time, so it does not make sense to
provide ability to remove a single PHI argument via remove_phi_arg.

The patch replaces remove_phi_arg with remove_phi_args, a new function
with goes through a PHI chain and removes PHI arguments associated
with a given edge.

Note that the new function remove_phi_args checks to see if a PHI
argument exists or not.  This is done because some pass, such as
threadupdate, removes an edge before adding complete PHI arguments for
that edge.  This "if" will go away once all of O(1) PHI argument
look-up is merged.  This is because we will always have a PHI argument
for every edge.

It is important that remove_phi_args take an edge as its argument, not
a predecessor basic block, because we will be able to replace

  phi_arg_from_edge (phi, e)

with 

  e->dest_idx

once a PHI array is lined up with its corresponding edge vector.  If
we took predecessor basic block bb as the argument, we would have at
best

  find_edge (bb, bb_for_stmt (phi))->dest_idx

which is quite ugly.

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

Kazu Hirata

2004-11-21  Kazu Hirata  <kazu@cs.umass.edu>

	* tree-flow.h: Remove the prototype for remove_phi_arg.
	Add a prototype for remove_phi_args.
	* tree-phinodes.c (remove_phi_arg): Remove.
	(remove_phi_args): New.
	* tree-ssa.c (ssa_remove_edge): Call remove_phi_args instead
	of remove_phi_arg.

Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.67
diff -u -d -p -r2.67 tree-flow.h
--- tree-flow.h	19 Nov 2004 18:21:42 -0000	2.67
+++ tree-flow.h	20 Nov 2004 14:58:37 -0000
@@ -510,7 +510,7 @@ extern stmt_ann_t create_stmt_ann (tree)
 extern tree_ann_t create_tree_ann (tree);
 extern tree create_phi_node (tree, basic_block);
 extern void add_phi_arg (tree *, tree, edge);
-extern void remove_phi_arg (tree, basic_block);
+extern void remove_phi_args (edge);
 extern void remove_phi_arg_num (tree, int);
 extern void remove_phi_node (tree, tree, basic_block);
 extern void remove_all_phi_nodes_for (bitmap);
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-phinodes.c,v
retrieving revision 2.21
diff -u -d -p -r2.21 tree-phinodes.c
--- tree-phinodes.c	9 Nov 2004 14:59:49 -0000	2.21
+++ tree-phinodes.c	20 Nov 2004 14:58:38 -0000
@@ -349,29 +349,6 @@ add_phi_arg (tree *phi, tree def, edge e
   PHI_NUM_ARGS (*phi)++;
 }
 
-/* Remove a PHI argument from PHI.  BLOCK is the predecessor block where
-   the PHI argument is coming from.  */
-
-void
-remove_phi_arg (tree phi, basic_block block)
-{
-  int i, num_elem = PHI_NUM_ARGS (phi);
-
-  for (i = 0; i < num_elem; i++)
-    {
-      basic_block src_bb;
-
-      src_bb = PHI_ARG_EDGE (phi, i)->src;
-
-      if (src_bb == block)
-	{
-	  remove_phi_arg_num (phi, i);
-	  return;
-	}
-    }
-}
-
-
 /* Remove the Ith argument from PHI's argument list.  This routine assumes
    ordering of alternatives in the vector is not important and implements
    removal by swapping the last alternative with the alternative we want to
@@ -400,6 +377,21 @@ remove_phi_arg_num (tree phi, int i)
   PHI_NUM_ARGS (phi)--;
 }
 
+/* Remove all PHI arguments associated with edge E.  */
+
+void
+remove_phi_args (edge e)
+{
+  tree phi;
+
+  for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
+    {
+      int index = phi_arg_from_edge (phi, e);
+      if (index >= 0)
+	remove_phi_arg_num (phi, index);
+    }
+}
+
 /* Remove PHI node PHI from basic block BB.  If PREV is non-NULL, it is
    used as the node immediately before PHI in the linked list.  */
 
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.59
diff -u -d -p -r2.59 tree-ssa.c
--- tree-ssa.c	19 Nov 2004 16:56:14 -0000	2.59
+++ tree-ssa.c	20 Nov 2004 14:58:38 -0000
@@ -53,14 +53,8 @@ Boston, MA 02111-1307, USA.  */
 void
 ssa_remove_edge (edge e)
 {
-  tree phi, next;
-
-  /* Remove the appropriate PHI arguments in E's destination block.  */
-  for (phi = phi_nodes (e->dest); phi; phi = next)
-    {
-      next = PHI_CHAIN (phi);
-      remove_phi_arg (phi, e->src);
-    }
+  /* Remove all PHI arguments for E.  */
+  remove_phi_args (e);
 
   remove_edge (e);
 }


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