This is the mail archive of the gcc@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]

[RFC] Mixed results with O(1) PHI arg lookup


Hi,

I implemented most of what's needed for O(1) PHI arg lookup, and I
have some mixed results.

2 runs of insn-attrtab.i

      original patched
real: 148.050  142.523 (3.733% down)
user: 146.648  139.828 (4.650% down)  <- wow!

10 runs of fold-const.i

      original patched
real: 137.473  137.755 (0.205% up)
user: 135.958  136.183 (0.165% up)

3 runs of insn-recog.c

      original patched
real: 79.175   79.414 (0.301% up)
user: 78.281   78.827 (0.697% up) <- ugh!

Here is what I've done in a nutshell.

o PHI arguments are lined up with edge vector.

o edge knows its index in the destination edge vector.
  That is, we always have EDGE_PRED (e->dest, e->dest_idx) == e.

o I added two CFG hooks so that the PHI arg arrays can grow (and
  shrink) at the same time edge vectors grow (and shrink).

o phi_arg_from_edge (phi, e) has collapsed down to e->dest_idx.

Here are some guesses for the slow down.

o e->dest_idx adds extra overhead in memory consumption.  When I just
  added e->dest_idx and related optimizations of cfg.c (but nothing
  else), I saw performance gain of 2% or so on insn-attrtab.i but loss
  on some other files.

o Every time an edge is added or removed, I call a callback function
  to appropriately resize PHI arg arrays.  This adds some overhead.
  In particular, we don't have PHI nodes in RTL.  Even in tree, not
  every basic block has PHI node.

o There may be some instances left where people do the equivalent of
  phi_arg_from_edge without using phi_arg_from_edge.  I've found some
  of these cases and fixed them.  One example would be tree-ssa-dom.c.

I thought about not adding CFG hooks and having add_phi_arg resize PHI
arrays the first time add_phi_arg is called after adding edges, but
this is a little dirty because we have some time period when
PHI_NUM_ARGS != EDGE_COUNT.

The patch survived a bootstrap, but it should not pass testsuite
because I have not fixed a part of tree_vectorizer.c that directly
writes PHI_ARG_EDGE.

Any comments?

By the way, you can find a rough ChangeLog at:

  http://dberlin.org/gccwiki/index.php/PhiLookUp

Kazu Hirata

Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.223
diff -u -d -p -r1.223 basic-block.h
--- basic-block.h	29 Oct 2004 08:40:51 -0000	1.223
+++ basic-block.h	5 Nov 2004 04:25:58 -0000
@@ -148,6 +148,9 @@ struct edge_def GTY(())
   int probability;		/* biased by REG_BR_PROB_BASE */
   gcov_type count;		/* Expected number of executions calculated
 				   in profile.c  */
+
+  /* The index within edge vector dest->preds.  */
+  unsigned int dest_idx;
 };
 
 typedef struct edge_def *edge;
@@ -634,7 +637,7 @@ ei_safe_edge (edge_iterator i)
    FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
      {
 	IF (e != taken_edge)
-	  ssa_remove_edge (e);
+	  remove_edge (e);
 	ELSE
 	  ei_next (&ei);
      }
Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.72
diff -u -d -p -r1.72 cfg.c
--- cfg.c	25 Oct 2004 21:48:25 -0000	1.72
+++ cfg.c	5 Nov 2004 04:25:58 -0000
@@ -276,6 +276,9 @@ unchecked_make_edge (basic_block src, ba
   e->src = src;
   e->dest = dst;
   e->flags = flags;
+  e->dest_idx = EDGE_COUNT (dst->preds) - 1;
+
+  execute_on_new_edge (e);
 
   return e;
 }
@@ -355,11 +358,15 @@ remove_edge (edge e)
 {
   edge tmp;
   basic_block src, dest;
+  unsigned int dest_idx;
   bool found = false;
   edge_iterator ei;
 
+  execute_on_removing_edge (e);
+
   src = e->src;
   dest = e->dest;
+  dest_idx = e->dest_idx;
 
   for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
     {
@@ -375,20 +382,9 @@ remove_edge (edge e)
 
   gcc_assert (found);
 
-  found = false;
-  for (ei = ei_start (dest->preds); (tmp = ei_safe_edge (ei)); )
-    {
-      if (tmp == e)
-	{
-	  VEC_unordered_remove (edge, dest->preds, ei.index);
-	  found = true;
-	  break;
-	}
-      else
-	ei_next (&ei);
-    }
-
-  gcc_assert (found);
+  VEC_unordered_remove (edge, dest->preds, dest_idx);
+  if (dest_idx < EDGE_COUNT (dest->preds))
+    EDGE_I (dest->preds, dest_idx)->dest_idx = dest_idx;
 
   free_edge (e);
 }
@@ -398,28 +394,20 @@ remove_edge (edge e)
 void
 redirect_edge_succ (edge e, basic_block new_succ)
 {
-  edge tmp;
-  edge_iterator ei;
-  bool found = false;
+  basic_block dest = e->dest;
+  unsigned int dest_idx = e->dest_idx;
 
-  /* Disconnect the edge from the old successor block.  */
-  for (ei = ei_start (e->dest->preds); (tmp = ei_safe_edge (ei)); )
-    {
-      if (tmp == e)
-	{
-	  VEC_unordered_remove (edge, e->dest->preds, ei.index);
-	  found = true;
-	  break;
-	}
-      else
-	ei_next (&ei);
-    }
+  execute_on_removing_edge (e);
 
-  gcc_assert (found);
+  VEC_unordered_remove (edge, dest->preds, dest_idx);
+  if (dest_idx < EDGE_COUNT (dest->preds))
+    EDGE_I (dest->preds, dest_idx)->dest_idx = dest_idx;
 
   /* Reconnect the edge to the new successor block.  */
   VEC_safe_push (edge, new_succ->preds, e);
   e->dest = new_succ;
+  e->dest_idx = EDGE_COUNT (new_succ->preds) - 1;
+  execute_on_new_edge (e);
 }
 
 /* Like previous but avoid possible duplicate edge.  */
@@ -460,6 +448,8 @@ redirect_edge_pred (edge e, basic_block 
   edge_iterator ei;
   bool found = false;
 
+  execute_on_removing_edge (e);
+
   /* Disconnect the edge from the old predecessor block.  */
   for (ei = ei_start (e->src->succs); (tmp = ei_safe_edge (ei)); )
     {
@@ -478,6 +468,7 @@ redirect_edge_pred (edge e, basic_block 
   /* Reconnect the edge to the new predecessor block.  */
   VEC_safe_push (edge, new_pred->succs, e);
   e->src = new_pred;
+  execute_on_new_edge (e);
 }
 
 /* Clear all basic block flags, with the exception of partitioning.  */
Index: cfghooks.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.c,v
retrieving revision 1.18
diff -u -d -p -r1.18 cfghooks.c
--- cfghooks.c	4 Nov 2004 22:02:55 -0000	1.18
+++ cfghooks.c	5 Nov 2004 04:25:58 -0000
@@ -791,3 +791,22 @@ flow_call_edges_add (sbitmap blocks)
 
   return (cfg_hooks->flow_call_edges_add) (blocks);
 }
+
+/* This function is called whenever a new edge is created or
+   redirected.  */
+
+void
+execute_on_new_edge (edge e)
+{
+  if (cfg_hooks->execute_on_new_edge)
+    cfg_hooks->execute_on_new_edge (e);
+}
+
+/* This function is called whenever an edge is being removed.  */
+
+void
+execute_on_removing_edge (edge e)
+{
+  if (cfg_hooks->execute_on_removing_edge)
+    cfg_hooks->execute_on_removing_edge (e);
+}
Index: cfghooks.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.h,v
retrieving revision 1.11
diff -u -d -p -r1.11 cfghooks.h
--- cfghooks.h	13 May 2004 06:39:32 -0000	1.11
+++ cfghooks.h	5 Nov 2004 04:25:58 -0000
@@ -100,6 +100,13 @@ struct cfg_hooks
      The goal is to expose cases in which entering a basic block does not imply
      that all subsequent instructions must be executed.  */
   int (*flow_call_edges_add) (sbitmap);
+
+  /* This function is called whenever a new edge is created or
+     redirected.  */
+  void (*execute_on_new_edge) (edge);
+
+  /* This function is called whenever an edge is being removed.  */
+  void (*execute_on_removing_edge) (edge);
 };
 
 extern void verify_flow_info (void);
@@ -126,6 +133,8 @@ extern basic_block duplicate_block (basi
 extern bool block_ends_with_call_p (basic_block bb);
 extern bool block_ends_with_condjump_p (basic_block bb);
 extern int flow_call_edges_add (sbitmap);
+extern void execute_on_new_edge (edge);
+extern void execute_on_removing_edge (edge);
 
 /* Hooks containers.  */
 extern struct cfg_hooks tree_cfg_hooks;
Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.144
diff -u -d -p -r1.144 cfgrtl.c
--- cfgrtl.c	4 Nov 2004 23:20:22 -0000	1.144
+++ cfgrtl.c	5 Nov 2004 04:25:59 -0000
@@ -3074,7 +3074,9 @@ struct cfg_hooks rtl_cfg_hooks = {
   rtl_tidy_fallthru_edge,
   rtl_block_ends_with_call_p,
   rtl_block_ends_with_condjump_p,
-  rtl_flow_call_edges_add
+  rtl_flow_call_edges_add,
+  NULL, /* execute_on_new_edge */
+  NULL /* execute_on_removing_edge */
 };
 
 /* Implementation of CFG manipulation for cfg layout RTL, where
@@ -3110,6 +3112,8 @@ struct cfg_hooks cfg_layout_rtl_cfg_hook
   NULL,
   rtl_block_ends_with_call_p,
   rtl_block_ends_with_condjump_p,
-  rtl_flow_call_edges_add
+  rtl_flow_call_edges_add,
+  NULL, /* execute_on_new_edge */
+  NULL /* execute_on_removing_edge */
 };
 
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.100
diff -u -d -p -r2.100 tree-cfg.c
--- tree-cfg.c	4 Nov 2004 22:07:37 -0000	2.100
+++ tree-cfg.c	5 Nov 2004 04:26:00 -0000
@@ -1782,7 +1782,7 @@ remove_phi_nodes_and_edges_for_unreachab
 
   /* Remove edges to BB's successors.  */
   while (EDGE_COUNT (bb->succs) > 0)
-    ssa_remove_edge (EDGE_SUCC (bb, 0));
+    remove_edge (EDGE_SUCC (bb, 0));
 }
 
 
@@ -1919,7 +1919,7 @@ cleanup_control_expr_graph (basic_block 
 	    {
 	      taken_edge->probability += e->probability;
 	      taken_edge->count += e->count;
-	      ssa_remove_edge (e);
+	      remove_edge (e);
 	      retval = true;
 	    }
 	  else
@@ -2080,16 +2080,11 @@ static bool
 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
 {
   tree phi, val1, val2;
-  int n1, n2;
+  int n1 = e1->dest_idx;
+  int n2 = e2->dest_idx;
 
   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
     {
-      n1 = phi_arg_from_edge (phi, e1);
-      n2 = phi_arg_from_edge (phi, e2);
-
-      gcc_assert (n1 >= 0);
-      gcc_assert (n2 >= 0);
-
       val1 = PHI_ARG_DEF (phi, n1);
       val2 = PHI_ARG_DEF (phi, n2);
 
@@ -2937,6 +2932,29 @@ bsi_insert_on_edge_immediate (edge e, tr
 	     Tree specific functions for CFG manipulation
 ---------------------------------------------------------------------------*/
 
+static void
+reinstall_phi_args (edge new_edge, edge old_edge)
+{
+  tree var, phi;
+
+  if (!PENDING_STMT (old_edge))
+    return;
+  
+  for (var = PENDING_STMT (old_edge), phi = phi_nodes (new_edge->dest);
+       var && phi;
+       var = TREE_CHAIN (var), phi = PHI_CHAIN (phi))
+    {
+      tree result = TREE_PURPOSE (var);
+      tree arg = TREE_VALUE (var);
+
+      gcc_assert (result == PHI_RESULT (phi));
+
+      add_phi_arg (&phi, arg, new_edge);
+    }
+
+  PENDING_STMT (old_edge) = NULL;
+}
+
 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
    Abort on abnormal edges.  */
 
@@ -2945,8 +2963,6 @@ tree_split_edge (edge edge_in)
 {
   basic_block new_bb, after_bb, dest, src;
   edge new_edge, e;
-  tree phi;
-  int i, num_elem;
   edge_iterator ei;
 
   /* Abnormal edges cannot be split.  */
@@ -2973,23 +2989,9 @@ tree_split_edge (edge edge_in)
   new_edge->probability = REG_BR_PROB_BASE;
   new_edge->count = edge_in->count;
 
-  /* Find all the PHI arguments on the original edge, and change them to
-     the new edge.  Do it before redirection, so that the argument does not
-     get removed.  */
-  for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
-    {
-      num_elem = PHI_NUM_ARGS (phi);
-      for (i = 0; i < num_elem; i++)
-	if (PHI_ARG_EDGE (phi, i) == edge_in)
-	  {
-	    PHI_ARG_EDGE (phi, i) = new_edge;
-	    break;
-	  }
-    }
-
   e = redirect_edge_and_branch (edge_in, new_bb);
   gcc_assert (e);
-  gcc_assert (!PENDING_STMT (edge_in));
+  reinstall_phi_args (new_edge, e);
 
   return new_bb;
 }
@@ -3407,6 +3409,16 @@ tree_verify_flow_info (void)
     {
       bool found_ctrl_stmt = false;
 
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	{
+	  if (ei.index != e->dest_idx)
+	    {
+	      error ("dest_idx at bb %d is not consistent",
+		     bb->index);
+	      err = 1;
+	    }
+	}
+
       /* Skip labels on the start of basic block.  */
       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 	{
@@ -3774,7 +3786,6 @@ thread_jumps_from_bb (basic_block bb)
       edge last, old;
       basic_block dest, tmp, curr, old_dest;
       tree phi;
-      int arg;
 
       /* If the edge is abnormal or its destination is not
 	 forwardable, then there's nothing to do.  */
@@ -3861,12 +3872,10 @@ thread_jumps_from_bb (basic_block bb)
 	     have the same value as the argument associated with LAST.
 	     Otherwise we would have changed our target block
 	     above.  */
+	  int arg = last->dest_idx;
+
 	  for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
-	    {
-	      arg = phi_arg_from_edge (phi, last);
-	      gcc_assert (arg >= 0);
-	      add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
-	    }
+	    add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
 	}
 
       /* Remove the unreachable blocks (observe that if all blocks
@@ -5093,7 +5102,7 @@ tree_purge_dead_eh_edges (basic_block bb
     {
       if (e->flags & EDGE_EH)
 	{
-	  ssa_remove_edge (e);
+	  remove_edge (e);
 	  changed = true;
 	}
       else
@@ -5138,6 +5147,27 @@ 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_new_edge (edge e)
+{
+  basic_block bb = e->dest;
+
+  if (phi_nodes (bb))
+    reserve_phi_args_for_new_edge (bb);
+}
+
+/* This function is called whenever an edge is being removed.  */
+
+static void
+tree_execute_on_removing_edge (edge e)
+{
+  if (phi_nodes (e->dest))
+    remove_phi_args (e);
+}
+
 struct cfg_hooks tree_cfg_hooks = {
   "tree",
   tree_verify_flow_info,
@@ -5159,7 +5189,9 @@ struct cfg_hooks tree_cfg_hooks = {
   NULL,				/* tidy_fallthru_edge  */
   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 */
+  tree_flow_call_edges_add,     /* flow_call_edges_add */
+  tree_execute_on_new_edge,	/* execute_on_new_edge */
+  tree_execute_on_removing_edge, /* execute_on_removing_edge */
 };
 
 
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.25
diff -u -d -p -r2.25 tree-flow-inline.h
--- tree-flow-inline.h	27 Oct 2004 17:45:19 -0000	2.25
+++ tree-flow-inline.h	5 Nov 2004 04:26:00 -0000
@@ -391,17 +391,14 @@ set_phi_nodes (basic_block bb, tree l)
 
 /* Return the phi index number for an edge.  */
 static inline int
-phi_arg_from_edge (tree phi, edge e)
+phi_arg_from_edge (tree phi ATTRIBUTE_UNUSED, edge e)
 {
-  int i;
+#if 0
   gcc_assert (phi);
   gcc_assert (TREE_CODE (phi) == PHI_NODE);
-
-  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
-    if (PHI_ARG_EDGE (phi, i) == e)
-      return i;
-
-  return -1;
+  gcc_assert (PHI_ARG_EDGE (phi, e->dest_idx) == e);
+#endif
+  return e->dest_idx;
 }
 
 /* Mark VAR as used, so that it'll be preserved during rtl expansion.  */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.58
diff -u -d -p -r2.58 tree-flow.h
--- tree-flow.h	2 Nov 2004 00:23:04 -0000	2.58
+++ tree-flow.h	5 Nov 2004 04:26:00 -0000
@@ -510,10 +510,10 @@ 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_arg (tree, basic_block);
-extern void remove_phi_arg_num (tree, int);
+extern void remove_phi_args (edge);
 extern void remove_phi_node (tree, tree, basic_block);
 extern void remove_all_phi_nodes_for (bitmap);
 extern void dump_dfa_stats (FILE *);
@@ -572,7 +572,6 @@ extern void debug_tree_ssa (void);
 extern void debug_def_blocks (void);
 extern void dump_tree_ssa_stats (FILE *);
 extern void debug_tree_ssa_stats (void);
-extern void ssa_remove_edge (edge);
 extern edge ssa_redirect_edge (edge, basic_block);
 extern void flush_pending_stmts (edge e);
 extern bool tree_ssa_useless_type_conversion (tree);
Index: tree-if-conv.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-if-conv.c,v
retrieving revision 2.11
diff -u -d -p -r2.11 tree-if-conv.c
--- tree-if-conv.c	14 Oct 2004 18:19:46 -0000	2.11
+++ tree-if-conv.c	5 Nov 2004 04:26:00 -0000
@@ -893,9 +893,9 @@ combine_blocks (struct loop *loop)
 
       /* It is time to remove this basic block.	 First remove edges.  */
       while (EDGE_COUNT (bb->succs) > 0)
-	ssa_remove_edge (EDGE_SUCC (bb, 0));
+	remove_edge (EDGE_SUCC (bb, 0));
       while (EDGE_COUNT (bb->preds) > 0)
-	ssa_remove_edge (EDGE_PRED (bb, 0));
+	remove_edge (EDGE_PRED (bb, 0));
 
       /* Remove labels and make stmts member of loop->header.  */
       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
Index: tree-outof-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-outof-ssa.c,v
retrieving revision 2.30
diff -u -d -p -r2.30 tree-outof-ssa.c
--- tree-outof-ssa.c	4 Nov 2004 08:41:14 -0000	2.30
+++ tree-outof-ssa.c	5 Nov 2004 04:26:00 -0000
@@ -357,17 +357,7 @@ eliminate_build (elim_graph g, basic_blo
       if (T0 == NULL_TREE)
 	continue;
 
-      if (PHI_ARG_EDGE (phi, i) == g->e)
-	Ti = PHI_ARG_DEF (phi, i);
-      else
-        {
-	  /* On rare occasions, a PHI node may not have the arguments
-	     in the same order as all of the other PHI nodes. If they don't 
-	     match, find the appropriate index here.  */
-	  pi = phi_arg_from_edge (phi, g->e);
-	  gcc_assert (pi != -1);
-	  Ti = PHI_ARG_DEF (phi, pi);
-	}
+      Ti = PHI_ARG_DEF (phi, i);
 
       /* If this argument is a constant, or a SSA_NAME which is being
 	 left in SSA form, just queue a copy to be emitted on this
@@ -601,10 +591,7 @@ coalesce_abnormal_edges (var_map map, co
 	    if (x == NO_PARTITION)
 	      continue;
 
-	    y = phi_arg_from_edge (phi, e);
-	    gcc_assert (y != -1);
-
-	    tmp = PHI_ARG_DEF (phi, y);
+	    tmp = PHI_ARG_DEF (phi, e->dest_idx);
 #ifdef ENABLE_CHECKING
 	    if (!phi_ssa_name_p (tmp))
 	      {
@@ -1929,7 +1916,7 @@ rewrite_trees (var_map map, tree *values
         {
 	  edge_iterator ei;
 	  FOR_EACH_EDGE (e, ei, bb->preds)
-	    eliminate_phi (e, phi_arg_from_edge (phi, e), g);
+	    eliminate_phi (e, e->dest_idx, g);
 	}
     }
 
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-phinodes.c,v
retrieving revision 2.19
diff -u -d -p -r2.19 tree-phinodes.c
--- tree-phinodes.c	4 Nov 2004 23:30:16 -0000	2.19
+++ tree-phinodes.c	5 Nov 2004 04:26:01 -0000
@@ -206,25 +206,30 @@ static tree
 make_phi_node (tree var, int len)
 {
   tree phi;
+  int cap;
 
-  len = ideal_phi_node_len (len);
+  cap = ideal_phi_node_len (len);
 
-  phi = allocate_phi_node (len);
+  phi = allocate_phi_node (cap);
 
   /* We do not have to clear a part of the PHI node that stores PHI
      arguments, which is safe because we tell the garbage collector to
      scan up to num_args elements in the array of PHI arguments.  In
      other words, the garbage collector will not follow garbage
      pointers in the unused portion of the array.  */
-  memset (phi, 0, sizeof (struct tree_phi_node) - sizeof (struct phi_arg_d));
+  memset (phi, 0, (sizeof (struct tree_phi_node)
+		   - sizeof (struct phi_arg_d)
+		   + len * sizeof (struct phi_arg_d)));
   TREE_SET_CODE (phi, PHI_NODE);
-  PHI_ARG_CAPACITY (phi) = len;
+  PHI_ARG_CAPACITY (phi) = cap;
   TREE_TYPE (phi) = TREE_TYPE (var);
   if (TREE_CODE (var) == SSA_NAME)
     SET_PHI_RESULT (phi, var);
   else
     SET_PHI_RESULT (phi, make_ssa_name (var, phi));
 
+  PHI_NUM_ARGS (phi) = len;
+
   return phi;
 }
 
@@ -269,6 +274,35 @@ 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 = ideal_phi_node_len (EDGE_COUNT (bb->preds) + 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, len);
+
+	  /* The result of the phi is defined by this phi node.  */
+	  SSA_NAME_DEF_STMT (PHI_RESULT (*loc)) = *loc;
+
+	  release_phi_node (old_phi);
+	}
+      PHI_NUM_ARGS (*loc)++;
+      gcc_assert ((unsigned int) PHI_NUM_ARGS (*loc)
+		  == EDGE_COUNT (bb->preds));
+    }
+}
+
 /* Create a new PHI node for variable VAR at basic block BB.  */
 
 tree
@@ -298,42 +332,16 @@ void
 add_phi_arg (tree *phi, tree def, edge e)
 {
   basic_block bb = e->dest;
-  int i = PHI_NUM_ARGS (*phi);
 
   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))
-	    ;
+  /* 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));
 
-	  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 (e->dest_idx < (unsigned int) PHI_NUM_ARGS (*phi));
 
   /* Copy propagation needs to know what object occur in abnormal
      PHI nodes.  This is a convenient place to record such information.  */
@@ -343,32 +351,8 @@ add_phi_arg (tree *phi, tree def, edge e
       SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (*phi)) = 1;
     }
 
-  SET_PHI_ARG_DEF (*phi, i, def);
-  PHI_ARG_EDGE (*phi, i) = e;
-  PHI_ARG_NONZERO (*phi, i) = false;
-  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;
-	}
-    }
+  SET_PHI_ARG_DEF (*phi, e->dest_idx, def);
+  PHI_ARG_NONZERO (*phi, e->dest_idx) = false;
 }
 
 
@@ -377,7 +361,7 @@ remove_phi_arg (tree phi, basic_block bl
    removal by swapping the last alternative with the alternative we want to
    delete, then shrinking the vector.  */
 
-void
+static void
 remove_phi_arg_num (tree phi, int i)
 {
   int num_elem = PHI_NUM_ARGS (phi);
@@ -389,7 +373,6 @@ remove_phi_arg_num (tree phi, int i)
   if (i != num_elem - 1)
     {
       SET_PHI_ARG_DEF (phi, i, PHI_ARG_DEF (phi, num_elem - 1));
-      PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE (phi, num_elem - 1);
       PHI_ARG_NONZERO (phi, i) = PHI_ARG_NONZERO (phi, num_elem - 1);
     }
 
@@ -400,6 +383,17 @@ remove_phi_arg_num (tree phi, int i)
   PHI_NUM_ARGS (phi)--;
 }
 
+/* Remove all PHI arguments for E.  */
+
+void
+remove_phi_args (edge e)
+{
+  tree phi;
+
+  for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
+    remove_phi_arg_num (phi, e->dest_idx);
+}
+
 /* 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-pretty-print.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pretty-print.c,v
retrieving revision 2.47
diff -u -d -p -r2.47 tree-pretty-print.c
--- tree-pretty-print.c	27 Oct 2004 17:45:20 -0000	2.47
+++ tree-pretty-print.c	5 Nov 2004 04:26:01 -0000
@@ -1439,6 +1439,9 @@ dump_generic_node (pretty_printer *buffe
 	pp_string (buffer, " = PHI <");
 	for (i = 0; i < PHI_NUM_ARGS (node); i++)
 	  {
+	    if (!PHI_ARG_DEF (node, i))
+	      continue;
+	      
 	    dump_generic_node (buffer, PHI_ARG_DEF (node, i), spc, flags, false);
 	    pp_string (buffer, "(");
 	    pp_decimal_int (buffer, PHI_ARG_EDGE (node, i)->src->index);
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.65
diff -u -d -p -r2.65 tree-ssa-dom.c
--- tree-ssa-dom.c	30 Oct 2004 12:15:09 -0000	2.65
+++ tree-ssa-dom.c	5 Nov 2004 04:26:01 -0000
@@ -2292,7 +2292,6 @@ cprop_into_successor_phis (basic_block b
   FOR_EACH_EDGE (e, ei, bb->succs)
     {
       tree phi;
-      int phi_num_args;
       int hint;
 
       /* If this is an abnormal edge, then we do not want to copy propagate
@@ -2304,43 +2303,13 @@ cprop_into_successor_phis (basic_block b
       if (! phi)
 	continue;
 
-      /* There is no guarantee that for any two PHI nodes in a block that
-	 the phi alternative associated with a particular edge will be
-	 at the same index in the phi alternative array.
-
-	 However, it is very likely they will be the same.  So we keep
-	 track of the index of the alternative where we found the edge in
-	 the previous phi node and check that index first in the next
-	 phi node.  If that hint fails, then we actually search all
-	 the entries.  */
-      phi_num_args = PHI_NUM_ARGS (phi);
-      hint = phi_num_args;
+      hint = e->dest_idx;
       for ( ; phi; phi = PHI_CHAIN (phi))
 	{
-	  int i;
 	  tree new;
 	  use_operand_p orig_p;
 	  tree orig;
 
-	  /* If the hint is valid (!= phi_num_args), see if it points
-	     us to the desired phi alternative.  */
-	  if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
-	    ;
-	  else
-	    {
-	      /* The hint was either invalid or did not point to the
-		 correct phi alternative.  Search all the alternatives
-		 for the correct one.  Update the hint.  */
-	      for (i = 0; i < phi_num_args; i++)
-		if (PHI_ARG_EDGE (phi, i) == e)
-		  break;
-	      hint = i;
-	    }
-
-	  /* If we did not find the proper alternative, then something is
-	     horribly wrong.  */
-	  gcc_assert (hint != phi_num_args);
-
 	  /* The alternative may be associated with a constant, so verify
 	     it is an SSA_NAME before doing anything with it.  */
 	  orig_p = PHI_ARG_DEF_PTR (phi, hint);
Index: tree-ssa-threadupdate.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-threadupdate.c,v
retrieving revision 2.12
diff -u -d -p -r2.12 tree-ssa-threadupdate.c
--- tree-ssa-threadupdate.c	2 Nov 2004 12:51:09 -0000	2.12
+++ tree-ssa-threadupdate.c	5 Nov 2004 04:26:01 -0000
@@ -155,7 +155,7 @@ remove_ctrl_stmt_and_useless_edges (basi
   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
     {
       if (e->dest != dest_bb)
-	ssa_remove_edge (e);
+	remove_edge (e);
       else
 	ei_next (&ei);
     }
@@ -306,6 +306,7 @@ thread_block (basic_block bb)
       struct redirection_data *rd = VARRAY_GENERIC_PTR (redirection_data, i);
       tree phi;
       edge e;
+      int indx;
 
       e = make_edge (rd->dup_block, rd->outgoing_edge->dest, EDGE_FALLTHRU);
 
@@ -313,11 +314,9 @@ thread_block (basic_block bb)
 	 from the duplicate block, then we will need to add a new argument
 	 to them.  The argument should have the same value as the argument
 	 associated with the outgoing edge stored in RD.  */
+      indx = rd->outgoing_edge->dest_idx;
       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
-	{
-	  int indx = phi_arg_from_edge (phi, rd->outgoing_edge);
-	  add_phi_arg (&phi, PHI_ARG_DEF_TREE (phi, indx), e);
-	}
+	add_phi_arg (&phi, PHI_ARG_DEF_TREE (phi, indx), e);
     }
 
   /* The loop above created the duplicate blocks (and the statements
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.55
diff -u -d -p -r2.55 tree-ssa.c
--- tree-ssa.c	4 Nov 2004 20:10:59 -0000	2.55
+++ tree-ssa.c	5 Nov 2004 04:26:02 -0000
@@ -46,24 +46,6 @@ Boston, MA 02111-1307, USA.  */
 #include "tree-pass.h"
 
 
-/* Remove edge E and remove the corresponding arguments from the PHI nodes
-   in E's destination block.  */
-
-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_edge (e);
-}
-
 /* Remove the corresponding arguments from the PHI nodes in E's
    destination block and redirect it to DEST.  Return redirected edge.
    The list of removed arguments is stored in PENDING_STMT (e).  */
@@ -74,24 +56,22 @@ ssa_redirect_edge (edge e, basic_block d
   tree phi, next;
   tree list = NULL, *last = &list;
   tree src, dst, node;
-  int i;
+  unsigned int dest_idx = e->dest_idx;
 
   /* Remove the appropriate PHI arguments in E's destination block.  */
   for (phi = phi_nodes (e->dest); phi; phi = next)
     {
       next = PHI_CHAIN (phi);
 
-      i = phi_arg_from_edge (phi, e);
-      if (i < 0)
-	continue;
-
-      src = PHI_ARG_DEF (phi, i);
+      src = PHI_ARG_DEF (phi, dest_idx);
       dst = PHI_RESULT (phi);
-      node = build_tree_list (dst, src);
-      *last = node;
-      last = &TREE_CHAIN (node);
 
-      remove_phi_arg_num (phi, i);
+      if (src)
+	{
+	  node = build_tree_list (dst, src);
+	  *last = node;
+	  last = &TREE_CHAIN (node);
+	}
     }
 
   e = redirect_edge_succ_nodup (e, dest);
@@ -301,6 +281,16 @@ verify_phi_args (tree phi, basic_block b
   int i, phi_num_args = PHI_NUM_ARGS (phi);
   edge_iterator ei;
 
+  if ((unsigned int) phi_num_args != EDGE_COUNT (bb->preds))
+    {
+      error ("The number of PHI arguments, %d, does not match "
+	     "the number of incoming edges, %d, to bb %d.\n",
+	     phi_num_args,
+	     EDGE_COUNT (bb->preds),
+	     bb->index);
+      err = true;
+    }
+
   /* Mark all the incoming edges.  */
   FOR_EACH_EDGE (e, ei, bb->preds)
     e->aux = (void *) 1;
@@ -619,7 +609,9 @@ verify_ssa (void)
 	  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 	    {
 	      tree def = PHI_ARG_DEF (phi, i);
-	      if (TREE_CODE (def) != SSA_NAME && !is_gimple_min_invariant (def))
+	      if (def
+		  && TREE_CODE (def) != SSA_NAME
+		  && !is_gimple_min_invariant (def))
 		{
 		  error ("PHI argument is not SSA_NAME, or invariant");
 		  print_generic_stmt (stderr, phi, TDF_VOPS);
Index: tree-vectorizer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vectorizer.c,v
retrieving revision 2.24
diff -u -d -p -r2.24 tree-vectorizer.c
--- tree-vectorizer.c	4 Nov 2004 13:48:59 -0000	2.24
+++ tree-vectorizer.c	5 Nov 2004 04:26:03 -0000
@@ -586,7 +586,7 @@ update_phi_nodes_for_guard (edge guard_t
 		edge e = EDGE_SUCC (loop->exit_edges[0]->dest, 0);
 
 		SET_PHI_ARG_DEF (phi1, 
-				 phi_arg_from_edge (phi1, e),
+				 e->dest_idx,
 				 PHI_RESULT (new_phi)); 
 	      }
 	  }
@@ -2973,7 +2973,10 @@ vect_update_ivs_after_vectorizer (struct
 		  if (PHI_ARG_DEF (phi1, j) == def)
 		    {
 		      SET_PHI_ARG_DEF (phi1, j, ni_name);
+#if 0
 		      PHI_ARG_EDGE (phi1, j) = EDGE_SUCC (new_bb, 0);		      
+#endif
+		      gcc_unreachable ();
 		      break;
  		    }		    
 	      }
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.647
diff -u -d -p -r1.647 tree.h
--- tree.h	4 Nov 2004 23:30:16 -0000	1.647
+++ tree.h	5 Nov 2004 04:26:03 -0000
@@ -1374,7 +1374,7 @@ struct tree_ssa_name GTY(())
 #define PHI_NUM_ARGS(NODE)		PHI_NODE_CHECK (NODE)->phi.num_args
 #define PHI_ARG_CAPACITY(NODE)		PHI_NODE_CHECK (NODE)->phi.capacity
 #define PHI_ARG_ELT(NODE, I)		PHI_NODE_ELT_CHECK (NODE, I)
-#define PHI_ARG_EDGE(NODE, I)		PHI_NODE_ELT_CHECK (NODE, I).e
+#define PHI_ARG_EDGE(NODE, I)	(EDGE_I (bb_for_stmt ((NODE))->preds, I))
 #define PHI_ARG_NONZERO(NODE, I) 	PHI_NODE_ELT_CHECK (NODE, I).nonzero
 #define PHI_BB(NODE)			PHI_NODE_CHECK (NODE)->phi.bb
 #define PHI_DF(NODE)			PHI_NODE_CHECK (NODE)->phi.df
@@ -1384,7 +1384,6 @@ struct edge_def;
 struct phi_arg_d GTY(())
 {
   tree def;
-  struct edge_def * GTY((skip (""))) e;
   bool nonzero;
 };
 


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