2004-11-01 Andrew MacLeod <amacleod@redhat.com>

	PR tree-optimization/16447
	* tree-cfg.c (bsi_commit_one_edge_insert): Rename from
	bsi_commit_edge_inserts_1, and make funtion external.  Return new block.
	(bsi_commit_edge_inserts): Use renamed bsi_commit_one_edge_insert.
	* tree-optimize.c (pass_cleanup_cfg_post_optimizing): Enable listing.
	* tree-flow.h (bsi_commit_one_edge_insert): Extern decl.
	* tree-outof-ssa.c (rewrite_trees): Don't commit edges here.
	(same_stmt_list_p): New.  Return TRUE if edge is to be forwarded.
	(identical_copies_p): New.  Return true is two copies are the same.
	(identical_stmt_lists_p): New.  Return true if stmt lists are the same.
	(analyze_edges_for_bb): New.  Determine how best to insert edge stmts
	for a basic block.
	(perform_edge_inserts): New.  Determine what to do with all stmts that
	have been inserted on edges.
	(remove_ssa_form):  Analyze and commit edges from here.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@89970 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 327 insertions, 2 deletions

diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c
index 827f91d1511..6d33c4731cf 100644
--- a/gcc/tree-outof-ssa.c
+++ b/gcc/tree-outof-ssa.c
@@ -1933,9 +1933,331 @@ rewrite_trees (var_map map, tree *values)
     }
 
   delete_elim_graph (g);
+}
+
+
+/* These are the local work structures used to determine the best place to 
+   insert the copies that were placed on edges by the SSA->normal pass..  */
+static varray_type edge_leader = NULL;
+static varray_type GTY(()) stmt_list = NULL;
+static bitmap leader_has_match = NULL;
+static edge leader_match = NULL;
+
+
+/* Pass this function to make_forwarder_block so that all the edges with
+   matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  */
+static bool 
+same_stmt_list_p (edge e)
+{
+  return (e->aux == (PTR) leader_match) ? true : false;
+}
+
+
+/* Return TRUE if S1 and S2 are equivalent copies.  */
+static inline bool
+identical_copies_p (tree s1, tree s2)
+{
+#ifdef ENABLE_CHECKING
+  gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
+  gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
+  gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
+  gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
+#endif
+
+  if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
+    return false;
+
+  s1 = TREE_OPERAND (s1, 1);
+  s2 = TREE_OPERAND (s2, 1);
+
+  if (s1 != s2)
+    return false;
+
+  return true;
+}
+
+
+/* Compare the PENDING_STMT list for two edges, and return true if the lists
+   contain the same sequence of copies.  */
+
+static inline bool 
+identical_stmt_lists_p (edge e1, edge e2)
+{
+  tree t1 = PENDING_STMT (e1);
+  tree t2 = PENDING_STMT (e2);
+  tree_stmt_iterator tsi1, tsi2;
+
+  gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
+  gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
+
+  for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
+       !tsi_end_p (tsi1) && !tsi_end_p (tsi2); 
+       tsi_next (&tsi1), tsi_next (&tsi2))
+    {
+      if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
+        break;
+    }
+
+  if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
+    return false;
+
+  return true;
+}
+
+
+/* Look at all the incoming edges to block BB, and decide where the best place
+   to insert the stmts on each edge are, and perform those insertions.   Output
+   any debug information to DEBUG_FILE.  Return true if anything other than a 
+   standard edge insertion is done.  */
+
+static bool 
+analyze_edges_for_bb (basic_block bb, FILE *debug_file)
+{
+  edge e;
+  edge_iterator ei;
+  int count;
+  unsigned int x;
+  bool have_opportunity;
+  block_stmt_iterator bsi;
+  tree stmt;
+  edge single_edge = NULL;
+  bool is_label;
+
+  count = 0;
+  /* Find out how many edges there are with interesting pending stmts on them.  
+     Commit the stmts on edges we are not interested in.  */
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      if (PENDING_STMT (e))
+        {
+	  gcc_assert (!(e->flags & EDGE_ABNORMAL));
+	  if (e->flags & EDGE_FALLTHRU)
+	    {
+	      bsi = bsi_start (e->src);
+	      if (!bsi_end_p (bsi))
+	        {
+		  stmt = bsi_stmt (bsi);
+		  bsi_next (&bsi);
+		  gcc_assert (stmt != NULL_TREE);
+		  is_label = (TREE_CODE (stmt) == LABEL_EXPR);
+		  /* Punt if it has non-label stmts, or isn't local.  */
+		  if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0)) 
+		      || !bsi_end_p (bsi))
+		    {
+		      bsi_commit_one_edge_insert (e, NULL);
+		      continue;
+		    }
+		}
+	    }
+	  single_edge = e;
+	  count++;
+	}
+    }
+
+  /* If there aren't at least 2 edges, no sharing will happen.  */
+  if (count < 2)
+    {
+      if (single_edge)
+        bsi_commit_one_edge_insert (single_edge, NULL);
+      return false;
+    }
+
+  /* Ensure that we have empty worklists.  */
+  if (edge_leader == NULL)
+    {
+      VARRAY_EDGE_INIT (edge_leader, 25, "edge_leader");
+      VARRAY_TREE_INIT (stmt_list, 25, "stmt_list");
+      leader_has_match = BITMAP_XMALLOC ();
+    }
+  else
+    {
+#ifdef ENABLE_CHECKING
+      gcc_assert (VARRAY_ACTIVE_SIZE (edge_leader) == 0);
+      gcc_assert (VARRAY_ACTIVE_SIZE (stmt_list) == 0);
+      gcc_assert (bitmap_first_set_bit (leader_has_match) == -1);
+#endif
+    }
+
+  /* Find the "leader" block for each set of unique stmt lists.  Preference is
+     given to FALLTHRU blocks since they would need a GOTO to arrive at another
+     block.  The leader edge destination is the block which all the other edges
+     with the same stmt list will be redirected to.  */
+  have_opportunity = false;
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      if (PENDING_STMT (e))
+	{
+	  bool found = false;
+
+	  /* Look for the same stmt list in edge leaders list.  */
+	  for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
+	    {
+	      edge leader = VARRAY_EDGE (edge_leader, x);
+	      if (identical_stmt_lists_p (leader, e))
+		{
+		  /* Give this edge the same stmt list pointer.  */
+		  PENDING_STMT (e) = NULL;
+		  e->aux = leader;
+		  bitmap_set_bit (leader_has_match, x);
+		  have_opportunity = found = true;
+		  break;
+		}
+	    }
+
+	  /* If no similar stmt list, add this edge to the leader list.  */
+	  if (!found)
+	    {
+	      VARRAY_PUSH_EDGE (edge_leader, e);
+	      VARRAY_PUSH_TREE (stmt_list, PENDING_STMT (e));
+	    }
+	}
+     }
+
+  /* If there are no similar lists, just issue the stmts.  */
+  if (!have_opportunity)
+    {
+      for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
+	bsi_commit_one_edge_insert (VARRAY_EDGE (edge_leader, x), NULL);
+      VARRAY_POP_ALL (edge_leader);
+      VARRAY_POP_ALL (stmt_list);
+      bitmap_clear (leader_has_match);
+      return false;
+    }
+
+
+  if (debug_file)
+    fprintf (debug_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
+	     bb->index);
+
+  
+  /* For each common list, create a forwarding block and issue the stmt's
+     in that block.  */
+  for (x = 0 ; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
+    if (bitmap_bit_p (leader_has_match, x))
+      {
+	edge new_edge, leader_edge;
+	block_stmt_iterator bsi;
+	tree curr_stmt_list;
+
+	leader_match = leader_edge = VARRAY_EDGE (edge_leader, x);
+
+	/* The tree_* cfg manipulation routines use the PENDING_EDGE field
+	   for various PHI manipulations, so it gets cleared whhen calls are 
+	   made to make_forwarder_block(). So make sure the edge is clear, 
+	   and use the saved stmt list.  */
+	PENDING_STMT (leader_edge) = NULL;
+	leader_edge->aux = leader_edge;
+	curr_stmt_list = VARRAY_TREE (stmt_list, x);
+
+        new_edge = make_forwarder_block (leader_edge->dest, same_stmt_list_p, 
+					 NULL);
+	bb = new_edge->dest;
+	if (debug_file)
+	  {
+	    fprintf (debug_file, "Splitting BB %d for Common stmt list.  ", 
+		     leader_edge->dest->index);
+	    fprintf (debug_file, "Original block is now BB%d.\n", bb->index);
+	    print_generic_stmt (debug_file, curr_stmt_list, TDF_VOPS);
+	  }
+
+	FOR_EACH_EDGE (e, ei, new_edge->src->preds)
+	  {
+	    e->aux = NULL;
+	    if (debug_file)
+	      fprintf (debug_file, "  Edge (%d->%d) lands here.\n", 
+		       e->src->index, e->dest->index);
+	  }
+
+	bsi = bsi_last (leader_edge->dest);
+	bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
+
+	leader_match = NULL;
+	/* We should never get a new block now.  */
+      }
+    else
+      {
+        e = VARRAY_EDGE (edge_leader, x);
+	PENDING_STMT (e) = VARRAY_TREE (stmt_list, x);
+	bsi_commit_one_edge_insert (e, NULL);
+      }
+
+   
+  /* Clear the working data structures.  */
+  VARRAY_POP_ALL (edge_leader);
+  VARRAY_POP_ALL (stmt_list);
+  bitmap_clear (leader_has_match);
+
+  return true;
+}
+
+
+/* This function will analyze the insertions which were performed on edges,
+   and decide whether they should be left on that edge, or whether it is more
+   efficient to emit some subset of them in a single block.  All stmts are
+   inserted somewhere, and if non-NULL, debug information is printed via 
+   DUMP_FILE.  */
+
+static void
+perform_edge_inserts (FILE *dump_file)
+{
+  basic_block bb;
+  bool changed = false;
+
+  if (dump_file)
+    fprintf(dump_file, "Analyzing Edge Insertions.\n");
+
+  FOR_EACH_BB (bb)
+    changed |= analyze_edges_for_bb (bb, dump_file);
+
+  changed |= analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
+
+  /* Clear out any tables which were created.  */
+  edge_leader = NULL;
+  if (leader_has_match != NULL)
+    {
+      free (leader_has_match);
+      leader_has_match = NULL;
+    }
 
-  /* If any copies were inserted on edges, actually insert them now.  */
-  bsi_commit_edge_inserts (NULL);
+  if (changed)
+    {
+      free_dominance_info (CDI_DOMINATORS);
+      free_dominance_info (CDI_POST_DOMINATORS);
+    }
+
+#ifdef ENABLE_CHECKING
+  {
+    edge_iterator ei;
+    edge e;
+    FOR_EACH_BB (bb)
+      {
+	FOR_EACH_EDGE (e, ei, bb->preds)
+	  {
+	    if (PENDING_STMT (e))
+	      error (" Pending stmts not issued on PRED edge (%d, %d)\n", 
+		     e->src->index, e->dest->index);
+	  }
+	FOR_EACH_EDGE (e, ei, bb->succs)
+	  {
+	    if (PENDING_STMT (e))
+	      error (" Pending stmts not issued on SUCC edge (%d, %d)\n", 
+		     e->src->index, e->dest->index);
+	  }
+      }
+    FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
+      {
+	if (PENDING_STMT (e))
+	  error (" Pending stmts not issued on ENTRY edge (%d, %d)\n", 
+		 e->src->index, e->dest->index);
+      }
+    FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+      {
+	if (PENDING_STMT (e))
+	  error (" Pending stmts not issued on EXIT edge (%d, %d)\n", 
+		 e->src->index, e->dest->index);
+      }
+  }
+#endif
 }
 
 
@@ -2022,6 +2344,9 @@ remove_ssa_form (FILE *dump, var_map map, int flags)
 	}
     }
 
+  /* If any copies were inserted on edges, analyze and insert them now.  */
+  perform_edge_inserts (dump_file);
+
   dump_file = save;
 }