* Makefile.in (OBJC-common): Add tree-ssa-threadupdate.c

        (tree-ssa-threadupdate.o): Add dependencies.
        * tree-ssa-threadupdate.c: New file.
        * tree-flow.h (incoming_edge_threaded): New flag in block annotation.
        (rewrite_vars_out_of_ssa): Remove prototype.
        (cleanup_tree_cfg): Returns a bool.
        * tree.h (thread_through_all_blocks): Prototype.
        * tree-outof-ssa.c  (SSANORM_*): Move into here.
        (remove_ssa_form): Now static.
        (rewrite_vars_out_of_ssa): Kill.
        * tree-ssa-live.c (register_ssa_partitions_for_vars): Kill.
        * tree-ssa-live.h (SSANORM_*): Moved into tree-outof-ssa.c.
        (remove_ssa_form, register_partitions_for_vars): Kill declarations.
        * tree-cfg.c (cleanup_tree_cfg): Return a value indicating if
        anything was changed.
        * tree-phinodes.c (add_phi_arg): Get the block for the PHI
        from the PHI's annotation rather than the edge associated with
        the new argument.
        * tree-ssa-dom.c (redirection_edges): Kill.
        (redirect_edges_and_update_ssa_graph): Kill.
        (tree_ssa_dominator_optimize): Do not reset forwardable flag
        for blocks anymore.  Do not initialize redirection_edges.
        Call thread_through_all_blocks.  Simplify code for cleanup
        of the CFG and iterating.  No longer call cleanup_tree_cfg
        outside the iteration loop.
        (thread_across_edge): No longer mess with forwardable blocks.


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

1 files changed, 421 insertions, 0 deletions

diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
new file mode 100644
index 00000000000..37c893073de
--- /dev/null
+++ b/gcc/tree-ssa-threadupdate.c
@@ -0,0 +1,421 @@
+/* Thread edges through blocks and update the control flow and SSA graphs.
+   Copyright (C) 2004 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "flags.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "ggc.h"
+#include "basic-block.h"
+#include "output.h"
+#include "errors.h"
+#include "expr.h"
+#include "function.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "tree-pass.h"
+
+/* Given a block B, update the CFG and SSA graph to reflect redirecting
+   one or more in-edges to B to instead reach the destination of an
+   out-edge from B while preserving any side effects in B.
+
+   ie, given A->B and B->C, change A->B to be A->C yet still preserve the
+   side effects of executing B.
+
+     1. Make a copy of B (including its outgoing edges and statements).  Call
+	the copy B'.  Note B' has no incoming edges or PHIs at this time.
+
+     2. Remove the control statement at the end of B' and all outgoing edges
+	except B'->C.
+
+     3. Add a new argument to each PHI in C with the same value as the existing
+	argument associated with edge B->C.  Associate the new PHI arguments
+	with the edge B'->C.
+
+     4. For each PHI in B, find or create a PHI in B' with an identical
+	PHI_RESULT.  Add an argument to the PHI in B' which as the same
+	value as the PHI in B associated with the edge A->B.  Associate
+	the new argument in the PHI in B' with the edge A->B.
+
+     5. Change the edge A->B to A->B'.
+
+	5a. This automatically deletes any PHI arguments associated with the
+	    edge A->B in B.
+
+	5b. This automatically associates each new argument added in step 4
+	    with the edge A->B'.
+
+     6. Repeat for other incoming edges into B.
+
+     7. Put the duplicated resources in B and all the B' blocks into SSA form.
+
+   Note that block duplication can be minimized by first collecting the
+   the set of unique destination blocks that the incoming edges should
+   be threaded to.  Block duplication can be further minimized by using 
+   B instead of creating B' for one destination if all edges into B are
+   going to be threaded to a successor of B.  */
+
+
+/* Main data structure recording information regarding B's duplicate
+   blocks.  */
+
+struct redirection_data
+{
+  /* A duplicate of B with the trailing control statement removed and which
+     targets a single successor of B.  */
+  basic_block dup_block;
+
+  /* An outgoing edge from B.  DUP_BLOCK will have OUTGOING_EDGE->dest as
+     its single successor.  */
+  edge outgoing_edge;
+};
+
+/* For each PHI node in BB, find or create a PHI node in NEW_BB for the
+   same PHI_RESULT.  Add an argument to the PHI node in NEW_BB which
+   corresponds to the same PHI argument associated with edge E in BB.  */
+
+static void
+copy_phis_to_block (basic_block new_bb, basic_block bb, edge e)
+{
+  tree phi, arg;
+
+  /* Walk over every PHI in BB.  */
+  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+    {
+      tree new_phi;
+
+      /* First try to find a PHI node in NEW_BB which has the same
+         PHI_RESULT as the PHI from BB we are currently processing.  */
+      for (new_phi = phi_nodes (new_bb); new_phi;
+	   new_phi = PHI_CHAIN (new_phi))
+	if (PHI_RESULT (new_phi) == PHI_RESULT (phi))
+	  break;
+
+      /* If we did not find a suitable PHI in NEW_BB, create one.  */
+      if (!new_phi)
+	new_phi = create_phi_node (PHI_RESULT (phi), new_bb);
+
+      /* Extract the argument corresponding to E from the current PHI
+         node in BB.  */
+      arg = PHI_ARG_DEF_TREE (phi, phi_arg_from_edge (phi, e));
+
+      /* Now add that same argument to the new PHI node in block NEW_BB.  */
+      add_phi_arg (&new_phi, arg, e);
+    }
+}
+
+/* Remove the last statement in block BB which must be a COND_EXPR or
+   SWITCH_EXPR.  Also remove all outgoing edges except the edge which
+   reaches DEST_BB.
+
+   This is only used by jump threading which knows the last statement in
+   BB should be a COND_EXPR or SWITCH_EXPR.  If the block ends with any other
+   statement, then we abort.  */
+
+static void
+remove_last_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
+{
+  block_stmt_iterator bsi;
+  edge e, next;
+
+  bsi = bsi_last (bb);
+
+#ifdef ENABLE_CHECKING
+  if (TREE_CODE (bsi_stmt (bsi)) != COND_EXPR
+      && TREE_CODE (bsi_stmt (bsi)) != SWITCH_EXPR)
+    abort ();
+#endif
+
+  bsi_remove (&bsi);
+
+  next = NULL;
+  for (e = bb->succ; e; e = next)
+    {
+      next = e->succ_next;
+
+      if (e->dest != dest_bb)
+	ssa_remove_edge (e);
+    }
+
+  /* BB now has a single outgoing edge. We need to update the flags for
+     that single outgoing edge.  */
+  bb->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+  bb->succ->flags |= EDGE_FALLTHRU;
+}
+
+/* Create a duplicate of BB which only reaches the destination of the edge
+   stored in RD.  Record the duplicate block in RD.  */
+
+static void
+create_block_for_threading (basic_block bb, struct redirection_data *rd)
+{
+  tree phi;
+
+  /* We can use the generic block duplication code and simply remove
+     the stuff we do not need.  */
+  rd->dup_block = duplicate_block (bb, NULL);
+
+  /* The call to duplicate_block will copy everything, including the
+     useless COND_EXPR or SWITCH_EXPR at the end of the block.  We just remove
+     the useless COND_EXPR or SWITCH_EXPR here rather than having a
+     specialized block copier.  */
+  remove_last_stmt_and_useless_edges (rd->dup_block, rd->outgoing_edge->dest);
+
+  /* If there are any PHI nodes at the destination of the outgoing edge
+     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.  */
+  for (phi = phi_nodes (rd->dup_block->succ->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), rd->dup_block->succ);
+    }
+}
+
+/* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
+   is reached via one or more specific incoming edges, we know which
+   outgoing edge from BB will be traversed.
+
+   We want to redirect those incoming edges to the target of the 
+   appropriate outgoing edge.  Doing so avoids a conditional branch
+   and may expose new optimization opportunities.  Note that we have
+   to update dominator tree and SSA graph after such changes.
+
+   The key to keeping the SSA graph update managable is to duplicate
+   the side effects occuring in BB so that those side effects still
+   occur on the paths which bypass BB after redirecting edges.
+
+   We accomplish this by creating duplicates of BB and arranging for
+   the duplicates to unconditionally pass control to one specific
+   successor of BB.  We then revector the incoming edges into BB to
+   the appropriate duplicate of BB.
+
+   BB and its duplicates will have assignments to the same set of
+   SSA_NAMEs.  Right now, we just call into rewrite_ssa_into_ssa
+   to update the SSA graph for those names.
+
+   We are also going to experiment with a true incremental update
+   scheme for the duplicated resources.  Of of the interesting
+   properties we can exploit here is that all the resources set
+   in BB will have the same IDFS, so we have one IDFS computation
+   per block with incoming threaded edges, which can lower the
+   cost of the true incremental update algorithm.  */
+
+static void
+thread_block (basic_block bb)
+{
+  /* E is an incoming edge into BB that we may or may not want to
+     redirect to a duplicate of BB.  */
+  edge e;
+
+  /* The next edge in a predecessor list.  Used in loops where E->pred_next
+     may change within the loop.  */
+  edge next;
+
+  /* ALL indicates whether or not all incoming edges into BB should
+     be threaded to a duplicate of BB.  */
+  bool all = true;
+
+  /* Main data structure to hold information for duplicates of BB.  */
+  varray_type redirection_data;
+  unsigned int i;
+
+  VARRAY_GENERIC_PTR_INIT (redirection_data, 2, "redirection data");
+
+  /* Look at each incoming edge into BB.  Record each unique outgoing
+     edge that we want to thread an incoming edge to.  Also note if
+     all incoming edges are threaded or not.  */
+  for (e = bb->pred; e; e = e->pred_next)
+    {
+      if (!e->aux)
+	{
+	  all = false;
+	}
+      else
+	{
+	  unsigned int i;
+
+	  /* See if we can find an entry for the destination of this
+	     threaded edge that has already been recorded.  */
+	  for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
+	    {
+	      struct redirection_data *rd;
+	      edge e2;
+
+	      rd = VARRAY_GENERIC_PTR (redirection_data, i);
+	      e2 = e->aux;
+
+	      if (e2->dest == rd->outgoing_edge->dest)
+		break;
+	    }
+
+	  /* If the loop did not terminate early, then we have a new
+	     destination for the incoming threaded edges.  Record it.  */
+	  if (i == VARRAY_ACTIVE_SIZE (redirection_data))
+	    {
+	      struct redirection_data *rd;
+
+	      rd = xcalloc (1, sizeof (redirection_data));
+	      rd->outgoing_edge = e->aux;
+	      VARRAY_PUSH_GENERIC_PTR (redirection_data, rd);
+	    }
+	}
+    }
+
+  /* Now create duplicates of BB.  Note that if all incoming edges are
+     threaded, then BB is going to become unreachable.  In that case
+     we use BB for one of the duplicates rather than wasting memory
+     duplicating BB.  Thus the odd starting condition for the loop.  */
+  for (i = (all ? 1 : 0); i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
+    {
+      struct redirection_data *rd = VARRAY_GENERIC_PTR (redirection_data, i);
+      create_block_for_threading (bb, rd);
+    }
+
+  /* The loop above created the duplicate blocks (and the statements
+     within the duplicate blocks).  This loop creates PHI nodes for the
+     duplicated blocks and redirects the incoming edges into BB to reach
+     the duplicates of BB.
+
+     Note that redirecting the edge will change e->pred_next, so we have
+     to hold e->pred_next in a temporary. 
+
+     If this turns out to be a performance problem, then we could create
+     a list of incoming edges associated with each entry in 
+     REDIRECTION_DATA and walk over that list of edges instead.  */
+  next = NULL;
+  for (e = bb->pred; e; e = next)
+    {
+      edge new_dest = e->aux;
+
+      next = e->pred_next;
+
+      /* E was not threaded, then there is nothing to do.  */
+      if (!new_dest)
+	continue;
+
+      /* Go ahead and clear E->aux.  It's not needed anymore and failure
+         to clear it will cause all kinds of unpleasant problems later.  */
+      e->aux = NULL;
+
+      /* We know E is an edge we want to thread.  Find the entry associated
+         with E's new destination in the REDIRECTION_DATA array.  */
+      for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
+	{
+	  struct redirection_data *rd;
+
+	  rd = VARRAY_GENERIC_PTR (redirection_data, i);
+
+	  /* We have found the right entry if the outgoing edge in this
+	     entry matches E's new destination.  Note that if we have not
+	     created a duplicate block (rd->dup_block is NULL), then we
+	     are going to re-use BB as a duplicate and we do not need
+	     to create PHI nodes or redirect the edge.  */
+	  if (rd->outgoing_edge == new_dest && rd->dup_block)
+	    {
+	      edge e2;
+	      copy_phis_to_block (rd->dup_block, bb, e);
+
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
+			 e->src->index, e->dest->index, rd->dup_block->index);
+
+	      e2 = redirect_edge_and_branch (e, rd->dup_block);
+	      PENDING_STMT (e2) = NULL;
+
+	      if ((dump_file && (dump_flags & TDF_DETAILS))
+		  && e->src != e2->src)
+	      fprintf (dump_file, "    basic block %d created\n",
+		       e2->src->index);
+	      break;
+	    }
+	}
+    }
+
+  /* If all the incoming edges where threaded, then we used BB as one
+     of the duplicate blocks.  We need to fixup BB in that case so that
+     it no longer has a COND_EXPR or SWITCH_EXPR and reaches one destination
+     unconditionally.  */
+  if (all)
+    {
+      struct redirection_data *rd;
+
+      rd = VARRAY_GENERIC_PTR (redirection_data, 0);
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
+		 bb->pred->src->index, bb->index, bb->succ->dest->index);
+
+      remove_last_stmt_and_useless_edges (bb, rd->outgoing_edge->dest);
+    }
+
+  /* Done with this block.  Free any memory we have allocated, clear
+     REDIRECTION_DATA and unmark this block as needing incoming
+     edge redirections.  */
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
+    {
+      struct redirection_data *rd = VARRAY_GENERIC_PTR (redirection_data, i);
+      free (rd);
+    }
+  VARRAY_CLEAR (redirection_data);
+}
+
+/* Walk through all blocks and thread incoming edges to the block's 
+   destinations as requested.  This is the only entry point into this
+   file.
+
+   Blocks which have one or more incoming edges have INCOMING_EDGE_THREADED
+   set in the block's annotation.
+   this routine.
+
+   Each edge that should be threaded has the new destination edge stored in
+   the original edge's AUX field.
+
+   This routine (or one of its callees) will clear INCOMING_EDGE_THREADED
+   in the block annotations and the AUX field in the edges.
+
+   It is the caller's responsibility to fix the dominance information
+   and rewrite duplicated SSA_NAMEs back into SSA form.
+
+   Returns true if one or more edges were threaded, false otherwise.   */
+
+bool
+thread_through_all_blocks (void)
+{
+  basic_block bb;
+  bool retval = false;
+
+  FOR_EACH_BB (bb)
+    {
+      if (bb_ann (bb)->incoming_edge_threaded)
+	{
+	  thread_block (bb);
+	  retval = true;
+	  bb_ann (bb)->incoming_edge_threaded = false;
+	}
+    }
+  return retval;
+}