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 8/n


Hi,

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

This patch uses one of the new CFG hooks, execute_on_growing_pred, to
reserve space in a PHI array whenever the predecessor edge vector
grows by one element.

In turn, add_phi_arg no longer needs to resize a PHI array, so the
patch removes that code for that.

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

Kazu Hirata

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

	* tree-cfg.c (tree_execute_on_growing_pred): New.
	(tree_cfg_hooks): Add tree_execute_on_growing_pred.
	* tree-flow.h: Add a prototype for
	reserve_phi_args_for_new_edge.
	* tree-phinodes.c (reserve_phi_args_for_new_edge): New.
	(add_phi_arg): Don't resize a PHI array.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.116
diff -u -d -p -r2.116 tree-cfg.c
--- tree-cfg.c	22 Nov 2004 22:12:52 -0000	2.116
+++ tree-cfg.c	22 Nov 2004 22:16:39 -0000
@@ -5339,6 +5339,18 @@ tree_purge_all_dead_eh_edges (bitmap blo
   return changed;
 }
 
+/* This function is called whenever a new edge is created or
+   redirected.  */
+
+static void
+tree_execute_on_growing_pred (edge e)
+{
+  basic_block bb = e->dest;
+
+  if (phi_nodes (bb))
+    reserve_phi_args_for_new_edge (bb);
+}
+
 /* This function is called immediately before edge E is removed from
    the edge vector E->dest->preds.  */
 
@@ -5371,7 +5383,7 @@ struct cfg_hooks tree_cfg_hooks = {
   tree_block_ends_with_call_p,	/* block_ends_with_call_p */
   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
   tree_flow_call_edges_add,     /* flow_call_edges_add */
-  NULL,	/* execute_on_growing_pred */
+  tree_execute_on_growing_pred,	/* execute_on_growing_pred */
   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
 };
 
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.70
diff -u -d -p -r2.70 tree-flow.h
--- tree-flow.h	22 Nov 2004 22:12:56 -0000	2.70
+++ tree-flow.h	22 Nov 2004 22:16:39 -0000
@@ -508,6 +508,7 @@ extern void dump_generic_bb (FILE *, bas
 extern var_ann_t create_var_ann (tree);
 extern stmt_ann_t create_stmt_ann (tree);
 extern tree_ann_t create_tree_ann (tree);
+extern void reserve_phi_args_for_new_edge (basic_block);
 extern tree create_phi_node (tree, basic_block);
 extern void add_phi_arg (tree *, tree, edge);
 extern void remove_phi_args (edge);
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-phinodes.c,v
retrieving revision 2.23
diff -u -d -p -r2.23 tree-phinodes.c
--- tree-phinodes.c	22 Nov 2004 22:08:11 -0000	2.23
+++ tree-phinodes.c	22 Nov 2004 22:16:40 -0000
@@ -269,6 +269,33 @@ resize_phi_node (tree *phi, int len)
   *phi = new_phi;
 }
 
+/* Reserve PHI arguments for a new edge to basic block BB.  */
+
+void
+reserve_phi_args_for_new_edge (basic_block bb)
+{
+  tree *loc;
+  int len = EDGE_COUNT (bb->preds);
+  int cap = ideal_phi_node_len (len + 4);
+
+  for (loc = &(bb_ann (bb)->phi_nodes);
+       *loc;
+       loc = &PHI_CHAIN (*loc))
+    {
+      if (len > PHI_ARG_CAPACITY (*loc))
+	{
+	  tree old_phi = *loc;
+
+	  resize_phi_node (loc, cap);
+
+	  /* The result of the phi is defined by this phi node.  */
+	  SSA_NAME_DEF_STMT (PHI_RESULT (*loc)) = *loc;
+
+	  release_phi_node (old_phi);
+	}
+    }
+}
+
 /* Create a new PHI node for variable VAR at basic block BB.  */
 
 tree
@@ -302,38 +329,9 @@ add_phi_arg (tree *phi, tree def, edge e
 
   gcc_assert (bb == bb_for_stmt (*phi));
 
-  if (i >= PHI_ARG_CAPACITY (*phi))
-    {
-      tree old_phi = *phi;
-
-      /* Resize the phi.  Unfortunately, this will relocate it.  */
-      resize_phi_node (phi, ideal_phi_node_len (i + 4));
-
-      /* resize_phi_node will necessarily relocate the phi.  */
-      gcc_assert (*phi != old_phi);
-
-      /* The result of the phi is defined by this phi node.  */
-      SSA_NAME_DEF_STMT (PHI_RESULT (*phi)) = *phi;
-
-      release_phi_node (old_phi);
-
-      /* Update the list head if replacing the first listed phi.  */
-      if (phi_nodes (bb) == old_phi)
-	bb_ann (bb)->phi_nodes = *phi;
-      else
-	{
-	  /* Traverse the list looking for the phi node to chain to.  */
-	  tree p;
-
-	  for (p = phi_nodes (bb);
-	       p && PHI_CHAIN (p) != old_phi;
-	       p = PHI_CHAIN (p))
-	    ;
-
-	  gcc_assert (p);
-	  PHI_CHAIN (p) = *phi;
-	}
-    }
+  /* We resize PHI nodes upon edge creation.  We should always have
+     enough room at this point.  */
+  gcc_assert (PHI_NUM_ARGS (*phi) < PHI_ARG_CAPACITY (*phi));
 
   /* Copy propagation needs to know what object occur in abnormal
      PHI nodes.  This is a convenient place to record such information.  */


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