[tree-ssa] SSA-aware edge manipulation [patch]

Diego Novillo dnovillo@redhat.com
Mon Apr 7 01:19:00 GMT 2003


- Introduces ssa_remove_edge and ssa_make_edge.  These two
  functions update PHI nodes at the destination block.

- Shows the block number where each argument is coming from when
  rendering PHI nodes in the pretty printer.

- Adds a check in the SSA->normal pass to make sure that
  arguments match edges in each PHI node.

- When removing dead COND_EXPRs and SWITCH_EXPRs, it update all
  the PHI nodes that had arguments coming from the conditional
  body.  From the documentation in tree-ssa-dce.c:remove_conditional:

  /* For every PHI node V_i at PDOM_BB, find the first argument V_j coming
     from a node dominated by BB.  That argument V_j will be used as the
     new argument for V_i, coming from the new edge BB -> PDOM_BB.

			+----------+
			| ...      |
			| if (...) | BB
			+----------+
			  /      \
			 /        \
			...       ...
		       +---+     +---+
		       |   | N   |   | M
		       +---+     +---+
			 \        /
			  \      /
	    +------------------------------------+
	    | V_i = PHI <..., V_j(N), V_j(M)...> | PDOM_BB
	    +------------------------------------+

     Notice that since the whole conditional structure is dead, it is
     impossible for V_j to have originated inside the conditional.
     Otherwise, the conditional would have live statements (namely, the
     statements that generate V_j).

     Therefore, the PHI node V_i is guaranteed to have up to two identical
     arguments V_j coming from inside the conditional.  Since V_j cannot
     have been generated inside the conditional, when we add a new edge
     BB->PDOM_BB, we can make V_j come from the new edge.  The transformed
     flowgraph will look as follows (after the call to cleanup_tree_cfg):

			+---------+
			| ...     |
			| (void)0 | BB
			+---------+
			     |
			     |
	    +-------------------------------+
	    | V_i = PHI <..., V_j(BB), ...> | PDOM_BB
	    +-------------------------------+

     The same property applies for SWITCH_EXPR conditionals.  */


Diego.

	* tree-cfg.c (remove_bb): Call ssa_remove_edge.
	(cleanup_cond_expr_graph): Likewise.
	(cleanup_switch_expr_graph): Likewise.
	(disconnect_unreachable_case_labels): Likewise.
	(merge_tree_blocks): Likewise.
	Update PHI nodes at BB2's successor.
	(dump_tree_bb): Show PHI nodes in the block.
	* tree-dfa.c (add_phi_arg): Update comment.
	(remove_phi_arg_num): New function.
	(remove_phi_arg): Call it.
	Move from tree-ssa.c.
	(remove_phi_node): Move from tree-ssa.c.
	* tree-flow.h (ssa_make_edge): Declare.
	(ssa_remove_edge): Declare.
	* tree-pretty-print.c (dump_generic_node): Show block where PHI
	arguments are coming from.
	* tree-ssa-dce.c (pdom_info): New local variable.
	(remove_dead_stmts): Initialize it and free it at the end.
	(remove_conditional): New function.
	(remove_dead_stmt): Call it.
	* tree-ssa.c (eliminate_phi): If the edge index is -1, abort
	compilation.
	(ssa_remove_edge): New function.
	(ssa_make_edge): New function.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.68
diff -d -u -p -r1.1.4.68 tree-cfg.c
--- tree-cfg.c	1 Apr 2003 23:04:02 -0000	1.1.4.68
+++ tree-cfg.c	6 Apr 2003 22:49:56 -0000
@@ -1103,17 +1103,9 @@ remove_bb (bb, remove_stmts)
       remove_edge (bb->pred);
     }
 
+  /* Remove edges to BB's successors.  */
   while (bb->succ != NULL)
-    {
-      tree phi;
-
-      /* PHI nodes in successors of this block now have one less
-         alternative.  */
-      for (phi = phi_nodes (bb->succ->dest); phi; phi = TREE_CHAIN (phi))
-	remove_phi_arg (phi, bb);
-
-      remove_edge (bb->succ);
-    }
+    ssa_remove_edge (bb->succ);
 
   bb->pred = NULL;
   bb->succ = NULL;
@@ -1384,15 +1376,7 @@ cleanup_cond_expr_graph (bb)
 	{
 	  next = e->succ_next;
 	  if (e != taken_edge)
-	    {
-	      tree phi;
-
-	      /* Remove the appropriate PHI alternative in the
-	         target block for each non executable edge.  */
-	      for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
-		remove_phi_arg (phi, e->dest);
-	      remove_edge (e);
-	    }
+	    ssa_remove_edge (e);
 	}
     }
 }
@@ -1431,15 +1415,7 @@ cleanup_switch_expr_graph (switch_bb)
 	  basic_block chain_bb = successor_block (switch_bb);
 	  edge e = find_edge (switch_bb, chain_bb);
 	  if (e)
-	    {
-	      tree phi;
-
-	      /* Remove the appropriate PHI alternative in the
-	         target block for each unexecutable edge.  */
-	      for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
-		remove_phi_arg (phi, e->src);
-	      remove_edge (e);
-	    }
+	    ssa_remove_edge (e);
 	  break;
 	}
     }
@@ -1474,15 +1450,7 @@ disconnect_unreachable_case_labels (bb)
 	{
 	  next = e->succ_next;
 	  if (e != taken_edge)
-	    {
-	      tree phi;
-
-	      /* Remove the appropriate PHI alternative in the
-	         target block for each non executable edge.  */
-	      for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
-		remove_phi_arg (phi, e->src);
-	      remove_edge (e);
-	    }
+	    ssa_remove_edge (e);
 	}
     }
 }
@@ -1749,6 +1717,7 @@ dump_tree_bb (outf, prefix, bb, indent)
   char *s_indent;
   basic_block loop_bb;
   block_stmt_iterator si;
+  tree phi;
 
   s_indent = (char *) alloca ((size_t) indent + 1);
   memset ((void *) s_indent, ' ', (size_t) indent);
@@ -1792,6 +1761,13 @@ dump_tree_bb (outf, prefix, bb, indent)
   else
     fprintf (outf, "nil\n");
 
+  for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+    {
+      fprintf (outf, "%s%s# ", s_indent, prefix);
+      print_generic_stmt (outf, phi, 0);
+      fprintf (outf, "\n");
+    }
+
   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
     {
       fprintf (outf, "%s%s%d  ", s_indent, prefix, get_lineno (bsi_stmt (si)));
@@ -3216,13 +3192,29 @@ merge_tree_blocks (basic_block bb1, basi
 
     /* BB2's successors are now BB1's.  */
     while (bb1->succ)
-      remove_edge (bb1->succ);
+      ssa_remove_edge (bb1->succ);
 
     while (bb2->succ)
       {
-	edge e = bb2->succ;
-	make_edge (bb1, e->dest, e->flags);
-	remove_edge (e);
+	tree phi;
+	edge new_edge, old_edge;
+	
+	old_edge = bb2->succ;
+	new_edge = make_edge (bb1, old_edge->dest, old_edge->flags);
+
+	/* Update PHI nodes at BB2's successor.  The arguments that used to
+	   come from BB2 now come from BB1.  */
+	for (phi = phi_nodes (old_edge->dest); phi; phi = TREE_CHAIN (phi))
+	  {
+	    int i;
+	    for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+	      if (PHI_ARG_EDGE (phi, i) == old_edge)
+		PHI_ARG_EDGE (phi, i) = new_edge;
+	  }
+
+	/* Note that we shouldn't call ssa_remove_edge here because we've
+	   already dealt with PHI nodes.  */
+	remove_edge (old_edge);
       }
 
     /* BB2's dominator children are now BB1's.  Also, remove BB2 as a
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.94
diff -d -u -p -r1.1.4.94 tree-dfa.c
--- tree-dfa.c	6 Apr 2003 03:36:41 -0000	1.1.4.94
+++ tree-dfa.c	6 Apr 2003 22:49:57 -0000
@@ -894,7 +894,8 @@ create_phi_node (var, bb)
 
 
 /* Add a new argument to PHI node PHI.  DEF is the incoming reaching
-    definition and E is the edge through which DEF reaches PHI.  */
+   definition and E is the edge through which DEF reaches PHI.  The new
+   argument is added at the end of the argument list.  */
 
 void
 add_phi_arg (phi, def, e)
@@ -911,6 +912,89 @@ add_phi_arg (phi, def, e)
   PHI_ARG_DEF (phi, i) = def;
   PHI_ARG_EDGE (phi, i) = 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 (phi, block)
+     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
+   delete, then shrinking the vector.  */
+
+void
+remove_phi_arg_num (tree phi, int i)
+{
+  int num_elem = PHI_NUM_ARGS (phi);
+
+  /* If we are not at the last element, switch the last element
+     with the element we want to delete.  */
+  if (i != num_elem - 1)
+    {
+      PHI_ARG_DEF (phi, i) = PHI_ARG_DEF (phi, num_elem - 1);
+      PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE (phi, num_elem - 1);
+    }
+
+  /* Shrink the vector and return.  */
+  PHI_ARG_DEF (phi, num_elem - 1) = NULL_TREE;
+  PHI_ARG_EDGE (phi, num_elem - 1) = NULL;
+  PHI_NUM_ARGS (phi)--;
+}
+
+
+/* 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.  */
+
+void
+remove_phi_node (phi, prev, bb)
+    tree phi;
+    tree prev;
+    basic_block bb;
+{
+  if (prev)
+    {
+      /* Rewire the list if we are given a PREV pointer.  */
+      TREE_CHAIN (prev) = TREE_CHAIN (phi);
+    }
+  else if (phi == phi_nodes (bb))
+    {
+      /* Update the list head if removing the first element.  */
+      bb_ann_t ann = bb_ann (bb);
+      ann->phi_nodes = TREE_CHAIN (phi);
+    }
+  else
+    {
+      /* Traverse the list looking for the node to remove.  */
+      tree prev, t;
+      prev = NULL_TREE;
+      for (t = phi_nodes (bb); t && t != phi; t = TREE_CHAIN (t))
+	prev = t;
+      if (t)
+	remove_phi_node (t, prev, bb);
+    }
 }
 
 
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.68
diff -d -u -p -r1.1.4.68 tree-flow.h
--- tree-flow.h	1 Apr 2003 23:04:02 -0000	1.1.4.68
+++ tree-flow.h	6 Apr 2003 22:49:57 -0000
@@ -406,6 +406,9 @@ extern var_ann_t create_var_ann 	PARAMS 
 extern stmt_ann_t create_stmt_ann 	PARAMS ((tree));
 extern tree create_phi_node		PARAMS ((tree, basic_block));
 extern void add_phi_arg			PARAMS ((tree, tree, edge));
+extern void remove_phi_arg		PARAMS ((tree, basic_block));
+extern void remove_phi_arg_num		PARAMS ((tree, int));
+extern void remove_phi_node		PARAMS ((tree, tree, basic_block));
 extern void dump_dfa_stats		PARAMS ((FILE *));
 extern void debug_dfa_stats		PARAMS ((void));
 extern void debug_referenced_vars	PARAMS ((void));
@@ -436,8 +439,6 @@ extern void add_vuse			PARAMS ((tree, tr
 /* In tree-ssa.c  */
 extern void rewrite_into_ssa		PARAMS ((tree));
 extern void rewrite_out_of_ssa		PARAMS ((tree));
-extern void remove_phi_arg		PARAMS ((tree, basic_block));
-extern void remove_phi_node		PARAMS ((tree, tree, basic_block));
 extern void dump_reaching_defs		PARAMS ((FILE *));
 extern void debug_reaching_defs		PARAMS ((void));
 extern void dump_tree_ssa		PARAMS ((FILE *));
@@ -445,6 +446,8 @@ extern void debug_tree_ssa		PARAMS ((voi
 extern void debug_def_blocks		PARAMS ((void));
 extern void dump_tree_ssa_stats		PARAMS ((FILE *));
 extern void debug_tree_ssa_stats	PARAMS ((void));
+extern edge ssa_make_edge		(basic_block, basic_block, int, tree);
+extern void ssa_remove_edge		(edge);
 
 /* In tree-ssa-pre.c  */
 extern void tree_perform_ssapre		PARAMS ((tree));
Index: tree-pretty-print.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-pretty-print.c,v
retrieving revision 1.1.2.20
diff -d -u -p -r1.1.2.20 tree-pretty-print.c
--- tree-pretty-print.c	1 Apr 2003 15:21:33 -0000	1.1.2.20
+++ tree-pretty-print.c	6 Apr 2003 22:49:57 -0000
@@ -1335,6 +1335,9 @@ dump_generic_node (buffer, node, spc, fl
 	for (i = 0; i < PHI_NUM_ARGS (node); i++)
 	  {
 	    dump_generic_node (buffer, PHI_ARG_DEF (node, i), spc, flags);
+	    output_add_string (buffer, "(");
+	    output_decimal (buffer, PHI_ARG_EDGE (node, i)->src->index);
+	    output_add_string (buffer, ")");
 	    if (i < PHI_NUM_ARGS (node) - 1)
 	      output_add_string (buffer, ", ");
 	  }
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.31
diff -d -u -p -r1.1.2.31 tree-ssa-dce.c
--- tree-ssa-dce.c	1 Apr 2003 01:09:14 -0000	1.1.2.31
+++ tree-ssa-dce.c	6 Apr 2003 22:49:57 -0000
@@ -70,6 +70,7 @@ static int dump_flags;
 
 static varray_type worklist;
 static dominance_info dom_info = NULL;
+static dominance_info pdom_info = NULL;
 
 static struct stmt_stats
 {
@@ -94,6 +95,7 @@ static void remove_dead_stmts			PARAMS (
 static void remove_dead_stmt			PARAMS ((block_stmt_iterator *,
       							 basic_block));
 static void remove_dead_phis			PARAMS ((basic_block));
+static void remove_conditional			(basic_block bb);
 
 
 /* Is a tree necessary?  */
@@ -406,6 +408,7 @@ remove_dead_stmts ()
   block_stmt_iterator i;
 
   dom_info = NULL;
+  pdom_info = NULL;
 
   FOR_EACH_BB (bb)
     {
@@ -429,6 +432,9 @@ remove_dead_stmts ()
   /* If we needed the dominance info, free it now.  */
   if (dom_info != NULL)
     free_dominance_info (dom_info);
+
+  if (pdom_info != NULL)
+    free_dominance_info (pdom_info);
 }
 
 
@@ -489,28 +495,18 @@ remove_dead_stmt (i, bb)
      post-dominator.  The flow graph will remove the blocks we are
      circumventing, and this block will then simply fall-thru to the
      post-dominator.  This prevents us from having to add any branch
-     instuctions to replace the conditional statement.  */
+     instuctions to replace the conditional statement.
+
+     Note that the call to remove_conditional can be relatively
+     expensive because of all the PHI node manipulation it needs to do.
+     Therefore, we only remove a conditional if its parent statement is
+     live.  This avoid unnecessary calls to remove_conditional in the
+     event of dead nested conditionals.  */
   if (TREE_CODE (t) == COND_EXPR || TREE_CODE (t) == SWITCH_EXPR)
     {
-      basic_block nb;
-      edge e;
-
-      /* Calculate the dominance info, if it hasn't been computed yet.  */
-      if (dom_info == NULL)
-	dom_info = calculate_dominance_info (CDI_POST_DOMINATORS);
-      nb = get_immediate_dominator (dom_info, bb);
-
-      /* Remove all outgoing edges, and add an edge to the
-         post dominator.  */
-      for (e = bb->succ; e != NULL;)
-	{
-	  edge tmp = e;
-	  e = e->succ_next;
-	  remove_edge (tmp);
-	}
-
-      if (nb)
-	make_edge (bb, nb, EDGE_FALLTHRU);
+      tree parent = parent_stmt (t);
+      if (parent == NULL_TREE || necessary_p (parent))
+	remove_conditional (bb);
     }
 
   bsi_remove (i);
@@ -562,4 +558,118 @@ tree_ssa_dce (fndecl)
   /* Dump the function tree after DCE.  */
   dump_function (TDI_dce, fndecl);
   print_stats ();
+}
+
+
+/* Remove the conditional statement starting at block BB.  */
+
+static void
+remove_conditional (basic_block bb)
+{
+  basic_block pdom_bb;
+  tree phi, phi_arg_list;
+  edge e;
+
+  /* Calculate dominance info, if it hasn't been computed yet.  */
+  if (pdom_info == NULL)
+    pdom_info = calculate_dominance_info (CDI_POST_DOMINATORS);
+
+  if (dom_info == NULL)
+    dom_info = calculate_dominance_info (CDI_DOMINATORS);
+
+  pdom_bb = get_immediate_dominator (pdom_info, bb);
+
+  /* Remove all outgoing edges.  */
+  for (e = bb->succ; e; )
+    {
+      edge tmp = e->succ_next;
+      /* If the edge BB->PDO_BB exists already, don't remove it.  */
+      if (e->dest != pdom_bb)
+	ssa_remove_edge (e);
+      e = tmp;
+    }
+
+  /* If we haven't removed all the edges, there is no need to update the
+     PHI nodes at PDOM_BB because all the superfluous arguments have been
+     removed by ssa_remove_edge and we don't need any new arguments.  */
+  if (bb->succ)
+    return;
+
+  /* For every PHI node V_i at PDOM_BB, find the first argument V_j coming
+     from a node dominated by BB.  That argument V_j will be used as the
+     new argument for V_i, coming from the new edge BB -> PDOM_BB.
+
+			+----------+
+			| ...      |
+			| if (...) | BB
+			+----------+
+			  /      \
+			 /        \
+			...       ...
+		       +---+     +---+
+		       |   | N   |   | M
+		       +---+     +---+
+			 \        /
+			  \      /
+	    +------------------------------------+
+	    | V_i = PHI <..., V_j(N), V_j(M)...> | PDOM_BB
+	    +------------------------------------+
+
+     Notice that since the whole conditional structure is dead, it is
+     impossible for V_j to have originated inside the conditional.
+     Otherwise, the conditional would have live statements (namely, the
+     statements that generate V_j).
+
+     Therefore, the PHI node V_i is guaranteed to have up to two identical
+     arguments V_j coming from inside the conditional.  Since V_j cannot
+     have been generated inside the conditional, when we add a new edge
+     BB->PDOM_BB, we can make V_j come from the new edge.  The transformed
+     flowgraph will look as follows (after the call to cleanup_tree_cfg):
+
+			+---------+
+			| ...     |
+			| (void)0 | BB
+			+---------+
+			     |
+			     |
+	    +-------------------------------+
+	    | V_i = PHI <..., V_j(BB), ...> | PDOM_BB
+	    +-------------------------------+
+
+     The same property applies for SWITCH_EXPR conditionals.  */
+  phi_arg_list = NULL_TREE;
+  for (phi = phi_nodes (pdom_bb); phi; phi = TREE_CHAIN (phi))
+    {
+      int found, i;
+      for (found = i = 0; i < PHI_NUM_ARGS (phi); i++)
+	{
+	  basic_block arg_bb = PHI_ARG_EDGE (phi, i)->src;
+
+	  if (dominated_by_p (dom_info, arg_bb, bb))
+	    {
+	      tree arg = build_tree_list (NULL_TREE, PHI_ARG_DEF (phi, i));
+
+	      if (phi_arg_list )
+		chainon (phi_arg_list, arg);
+	      else
+		phi_arg_list = arg;
+
+	      remove_phi_arg_num (phi, i);
+	      found = 1;
+	      break;
+	    }
+	}
+
+#if defined ENABLE_CHECKING
+      /* If we didn't find an argument coming from a block dominated by BB,
+	 something is wrong.  */
+      if (!found)
+	abort ();
+#endif
+    }
+
+  /* Add an edge to BB's post dominator.  Add PHI arguments to every PHI
+     node at PDOM_BB from the list of arguments computed above..  */
+  if (bb->succ == NULL)
+    ssa_make_edge (bb, pdom_bb, EDGE_FALLTHRU, phi_arg_list);
 }
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.63
diff -d -u -p -r1.1.4.63 tree-ssa.c
--- tree-ssa.c	4 Apr 2003 18:40:23 -0000	1.1.4.63
+++ tree-ssa.c	6 Apr 2003 22:49:58 -0000
@@ -1073,11 +1073,10 @@ eliminate_phi (e, i, g)
   int x, limit;
   basic_block B = e->dest;
 
-  /* TODO. Sometimes edges are removed and the PHI nodes are not updated.
-     This results in an out of date PHI entry, and we should'd process these
-     yet. This should never happen.... eventually.  */
+#if defined ENABLE_CHECKING
   if (i == -1)
-    return;
+    abort ();
+#endif
 
   for (phi = phi_nodes (B); phi; phi = TREE_CHAIN (phi))
     {
@@ -1341,73 +1340,59 @@ rewrite_out_of_ssa (fndecl)
 }
 
 
-/* Remove a PHI argument from PHI.  BLOCK is the predecessor block where
-   the PHI argument is coming from.
-
-   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 delete, then shrinking the vector.  */
+/* Remove edge E and remove the corresponding arguments from the PHI nodes
+   in E's destination block.  Return a TREE_LIST node with all the removed
+   PHI arguments.  */
 
 void
-remove_phi_arg (phi, block)
-     tree phi;
-     basic_block block;
+ssa_remove_edge (edge e)
 {
-  size_t 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;
+  tree phi;
 
-      if (src_bb == block)
-	{
-	  /* If we are not at the last element, switch the last element
-	     with the element we want to delete.  */
-	  if (i != num_elem - 1)
-	    {
-	      PHI_ARG_DEF (phi, i) = PHI_ARG_DEF(phi, num_elem - 1);
-	      PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE(phi, num_elem - 1);
-	    }
+  /* Remove the appropriate PHI arguments in E's destination block.  */
+  for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
+    remove_phi_arg (phi, e->src);
 
-	  /* Shrink the vector.  */
-	  PHI_NUM_ARGS (phi)--;
-	}
-    }
+  remove_edge (e);
 }
 
 
-/* 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.  */
+/* Make a new edge between BB1 and BB2.  All the PHI nodes at BB2 will
+   receive a new argument that should be provided in PHI_ARG_LIST.  */
 
-void
-remove_phi_node (phi, prev, bb)
-    tree phi;
-    tree prev;
-    basic_block bb;
+edge
+ssa_make_edge (basic_block bb1, basic_block bb2, int flags, tree phi_arg_list)
 {
-  if (prev)
-    {
-      /* Rewire the list if we are given a PREV pointer.  */
-      TREE_CHAIN (prev) = TREE_CHAIN (phi);
-    }
-  else if (phi == phi_nodes (bb))
-    {
-      /* Update the list head if removing the first element.  */
-      bb_ann_t ann = bb_ann (bb);
-      ann->phi_nodes = TREE_CHAIN (phi);
-    }
-  else
-    {
-      /* Traverse the list looking for the node to remove.  */
-      tree prev, t;
-      prev = NULL_TREE;
-      for (t = phi_nodes (bb); t && t != phi; t = TREE_CHAIN (t))
-	prev = t;
-      if (t)
-	remove_phi_node (t, prev, bb);
-    }
+  tree phi;
+  edge e;
+  
+  e = make_edge (bb1, bb2, flags);
+
+  /* Add a new argument to every PHI node in BB2.  FIXME: Hmm, double
+     linear scan.  This may slow things down.  */
+  if (phi_arg_list)
+    for (phi = phi_nodes (bb2); phi; phi = TREE_CHAIN (phi))
+      {
+	/* Look for the new argument to add in PHI_ARG_LIST.  */
+	tree node;
+
+	for (node = phi_arg_list; node; node = TREE_CHAIN (node))
+	  {
+	    tree arg = TREE_VALUE (node);
+	    if (SSA_NAME_VAR (arg) == SSA_NAME_VAR (PHI_RESULT (phi)))
+	      {
+		add_phi_arg (phi, arg, e);
+		break;
+	      }
+	  }
+
+	/* If we didn't find an argument for the PHI node, then PHI_ARG_LIST
+	  is wrong.  */
+	if (node == NULL_TREE)
+	  abort ();
+      }
+
+  return e;
 }
 
 



More information about the Gcc-patches mailing list