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

        * 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.

From-SVN: r85721

1 files changed, 24 insertions, 299 deletions

diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 036706f..26df9ed 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -63,6 +63,7 @@ static htab_t avail_exprs;
    have to perform in lookup_avail_expr and finally it allows us to
    significantly reduce the number of calls into the hashing routine
    itself.  */
+
 struct expr_hash_elt
 {
   /* The value (lhs) of this expression.  */
@@ -160,18 +161,6 @@ struct vrp_element
 
 static struct opt_stats_d opt_stats;
 
-/* This virtual array holds pairs of edges which describe a scheduled
-   edge redirection from jump threading.
-
-   The first entry in each pair is the edge we are going to redirect.
-
-   The second entry in each pair is the edge leading to our final
-   destination block.  By providing this as an edge rather than the
-   final target block itself we can correctly handle redirections
-   when the target block had PHIs which required edge insertions/splitting
-   to remove the PHIs.  */
-static GTY(()) varray_type redirection_edges;
-
 /* A virtual array holding value range records for the variable identified
    by the index, SSA_VERSION.  */
 static varray_type vrp_data;
@@ -267,7 +256,6 @@ static void restore_vars_to_original_value (varray_type locals,
 static void restore_currdefs_to_original_value (varray_type locals,
 						unsigned limit);
 static void register_definitions_for_stmt (stmt_ann_t, varray_type *);
-static void redirect_edges_and_update_ssa_graph (varray_type);
 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
 
 /* Local version of fold that doesn't introduce cruft.  */
@@ -301,240 +289,6 @@ set_value_for (tree var, tree value, varray_type table)
   VARRAY_TREE (table, SSA_NAME_VERSION (var)) = value;
 }
 
-/* REDIRECTION_EDGES contains edge pairs where we want to revector the
-   destination of the first edge to the destination of the second edge.
-
-   These redirections may significantly change the SSA graph since we
-   allow redirection through blocks with PHI nodes and blocks with
-   real instructions in some cases.
-
-   This routine will perform the requested redirections and incrementally
-   update the SSA graph. 
-
-   Note in some cases requested redirections may be ignored as they can
-   not be safely implemented.  */
-
-static void
-redirect_edges_and_update_ssa_graph (varray_type redirection_edges)
-{
-  basic_block tgt, bb;
-  tree phi;
-  unsigned int i;
-  size_t old_num_referenced_vars = num_referenced_vars;
-  bitmap virtuals_to_rename = BITMAP_XMALLOC ();
-
-  /* First note any variables which we are going to have to take
-     out of SSA form as well as any virtuals which need updating.  */
-  for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
-    {
-      block_stmt_iterator bsi;
-      edge e;
-      basic_block tgt;
-      tree phi;
-
-      e = VARRAY_EDGE (redirection_edges, i);
-      tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
-
-      /* All variables referenced in PHI nodes we bypass must be
-	 renamed.  */
-      for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
-	{
-	  tree result = SSA_NAME_VAR (PHI_RESULT (phi));
-
-	  if (is_gimple_reg (PHI_RESULT (phi)))
-	    bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
-	  else
-	    bitmap_set_bit (virtuals_to_rename, var_ann (result)->uid);
-        }
-
-      /* Any variables set by statements at the start of the block we
-	 are bypassing must also be taken our of SSA form.  */
-      for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
-	{
-	  unsigned int j;
-	  def_optype defs;
-	  v_may_def_optype v_may_defs;
-	  v_must_def_optype v_must_defs;
-	  tree stmt = bsi_stmt (bsi);
-	  stmt_ann_t ann = stmt_ann (stmt);
-
-	  if (TREE_CODE (stmt) == COND_EXPR)
-	    break;
-
-	  get_stmt_operands (stmt);
-
-	  defs = DEF_OPS (ann);
-	  for (j = 0; j < NUM_DEFS (defs); j++)
-	    {
-	      tree op = DEF_OP (defs, j);
-	      tree var = SSA_NAME_VAR (op);
-	      bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
-	    }
-
-	  v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
-	  for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++)
-	    {
-	      tree op = V_MAY_DEF_RESULT (v_may_defs, j);
-	      tree var = SSA_NAME_VAR (op);
-	      bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
-	    }
-	    
-	  v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
-	  for (j = 0; j < NUM_V_MUST_DEFS (v_must_defs); j++)
-	    {
-	      tree op = V_MUST_DEF_OP (v_must_defs, j);
-	      tree var = SSA_NAME_VAR (op);
-	      bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
-	    }
-	}
-
-      /* Finally, any variables in PHI nodes at our final destination
-         must also be taken out of SSA form.  */
-      for (phi = phi_nodes (tgt); phi; phi = PHI_CHAIN (phi))
-	{
-	  tree result = SSA_NAME_VAR (PHI_RESULT (phi));
-
-	  if (is_gimple_reg (PHI_RESULT (phi)))
-	    bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
-	  else
-	    bitmap_set_bit (virtuals_to_rename, var_ann (result)->uid);
-        }
-    }
-
-  /* Take those selected variables out of SSA form.  This must be
-     done before we start redirecting edges.  */
-  if (bitmap_first_set_bit (vars_to_rename) >= 0)
-    rewrite_vars_out_of_ssa (vars_to_rename);
-
-  /* The out of SSA translation above may split the edge from
-     E->src to E->dest.  This could potentially cause us to lose
-     an assignment leading to invalid warnings about uninitialized
-     variables or incorrect code.
-
-     Luckily, we can detect this by looking at the last statement
-     in E->dest.  If it is not a COND_EXPR or SWITCH_EXPR, then
-     the edge was split and instead of E, we want E->dest->succ.  */
-  for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
-    {
-      edge e = VARRAY_EDGE (redirection_edges, i);
-      tree last = last_stmt (e->dest);
-
-      if (last
-	  && TREE_CODE (last) != COND_EXPR
-	  && TREE_CODE (last) != SWITCH_EXPR)
-	{
-	  e = e->dest->succ;
-
-#ifdef ENABLE_CHECKING
-	  /* There should only be a single successor if the
-	     original edge was split.  */
-	  if (e->succ_next)
-	    abort ();
-#endif
-	  /* Replace the edge in REDIRECTION_EDGES for the
-	     loop below.  */
-	  VARRAY_EDGE (redirection_edges, i) = e;
-	}
-    }
-
-  /* If we created any new variables as part of the out-of-ssa
-     translation, then any jump threads must be invalidated if they
-     bypass a block in which we skipped instructions.
-
-     This is necessary as instructions which appeared to be NOPS
-     may be necessary after the out-of-ssa translation.  */
-  if (num_referenced_vars != old_num_referenced_vars)
-    {
-      for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
-	{
-	  block_stmt_iterator bsi;
-	  edge e;
-
-	  e = VARRAY_EDGE (redirection_edges, i);
-	  for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
-	    {
-	      tree stmt = bsi_stmt (bsi);
-
-	      if (IS_EMPTY_STMT (stmt)
-		  || TREE_CODE (stmt) == LABEL_EXPR)
-		continue;
-
-	      if (TREE_CODE (stmt) == COND_EXPR)
-		break;
-
-	      /* Invalidate the jump thread.  */
-	      VARRAY_EDGE (redirection_edges, i) = NULL;
-	      VARRAY_EDGE (redirection_edges, i + 1) = NULL;
-	      break;
-	    }
-	}
-    }
-
-  /* Now redirect the edges.  */
-  for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
-    {
-      basic_block src;
-      edge e;
-
-      e = VARRAY_EDGE (redirection_edges, i);
-      if (!e)
-	continue;
-
-      tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
-
-
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
-		 e->src->index, e->dest->index, tgt->index);
-
-      src = e->src;
-
-      e = redirect_edge_and_branch (e, tgt);
-      PENDING_STMT (e) = NULL_TREE;
-
-      /* Updating the dominance information would be nontrivial.  */
-      free_dominance_info (CDI_DOMINATORS);
-      
-      if ((dump_file && (dump_flags & TDF_DETAILS))
-	  && e->src != src)
-	fprintf (dump_file, "    basic block %d created\n",
-		 e->src->index);
-
-      cfg_altered = true;
-    }
-
-  VARRAY_CLEAR (redirection_edges);
-
-  for (i = old_num_referenced_vars; i < num_referenced_vars; i++)
-    {
-      bitmap_set_bit (vars_to_rename, i);
-      var_ann (referenced_var (i))->out_of_ssa_tag = 0;
-    }
-
-  bitmap_a_or_b (vars_to_rename, vars_to_rename, virtuals_to_rename);
-
-  /* We must remove any PHIs for virtual variables that we are going to
-     re-rename.  Hopefully we'll be able to simply update these incrementally
-     soon.  */
-  FOR_EACH_BB (bb)
-    {
-      tree next;
-
-      for (phi = phi_nodes (bb); phi; phi = next)
-	{
-	  tree result = PHI_RESULT (phi);
-
-	  next = PHI_CHAIN (phi);
-
-	  if (bitmap_bit_p (virtuals_to_rename,
-			    var_ann (SSA_NAME_VAR (result))->uid))
-	    remove_phi_node (phi, NULL, bb);
-	}
-    }
-
-  BITMAP_XFREE (virtuals_to_rename);
-}
-
 /* Jump threading, redundancy elimination and const/copy propagation. 
 
    This pass may expose new symbols that need to be renamed into SSA.  For
@@ -544,7 +298,6 @@ redirect_edges_and_update_ssa_graph (varray_type redirection_edges)
 static void
 tree_ssa_dominator_optimize (void)
 {
-  basic_block bb;
   struct dom_walk_data walk_data;
   unsigned int i;
 
@@ -560,7 +313,6 @@ tree_ssa_dominator_optimize (void)
   avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
   VARRAY_TREE_INIT (const_and_copies, num_ssa_names, "const_and_copies");
   nonzero_vars = BITMAP_XMALLOC ();
-  VARRAY_EDGE_INIT (redirection_edges, 20, "redirection_edges");
   VARRAY_GENERIC_PTR_INIT (vrp_data, num_ssa_names, "vrp_data");
   need_eh_cleanup = BITMAP_XMALLOC ();
 
@@ -583,11 +335,6 @@ tree_ssa_dominator_optimize (void)
   /* Now initialize the dominator walker.  */
   init_walk_dominator_tree (&walk_data);
 
-  /* Reset block_forwardable in each block's annotation.  We use that
-     attribute when threading through COND_EXPRs.  */
-  FOR_EACH_BB (bb)
-    bb_ann (bb)->forwardable = 1;
-
   calculate_dominance_info (CDI_DOMINATORS);
 
   /* If we prove certain blocks are unreachable, then we want to
@@ -603,43 +350,36 @@ tree_ssa_dominator_optimize (void)
       /* Recursively walk the dominator tree optimizing statements.  */
       walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 
-      /* Wipe the hash tables.  */
+      /* If we exposed any new variables, go ahead and put them into
+	 SSA form now, before we handle jump threading.  This simplifies
+	 interactions between rewriting of _DECL nodes into SSA form
+	 and rewriting SSA_NAME nodes into SSA form after block
+	 duplication and CFG manipulation.  */
+      if (bitmap_first_set_bit (vars_to_rename) >= 0)
+	{
+	  rewrite_into_ssa (false);
+	  bitmap_clear (vars_to_rename);
+	}
 
-      if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
-	redirect_edges_and_update_ssa_graph (redirection_edges);
+      /* Thread jumps, creating duplicate blocks as needed.  */
+      cfg_altered = thread_through_all_blocks ();
 
+      /* Removal of statements may make some EH edges dead.  Purge
+	 such edges from the CFG as needed.  */
       if (bitmap_first_set_bit (need_eh_cleanup) >= 0)
 	{
-	  cfg_altered = tree_purge_all_dead_eh_edges (need_eh_cleanup);
+	  cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
 	  bitmap_zero (need_eh_cleanup);
 	}
 
-      /* We may have made some basic blocks unreachable, remove them.  */
-      cfg_altered |= delete_unreachable_blocks ();
+      free_dominance_info (CDI_DOMINATORS);
+      cfg_altered = cleanup_tree_cfg ();
+      calculate_dominance_info (CDI_DOMINATORS);
 
-      /* If the CFG was altered, then recompute the dominator tree.  This
-	 is not strictly needed if we only removed unreachable blocks, but
-	 may produce better results.  If we threaded jumps, then rebuilding
-	 the dominator tree is strictly necessary.  Likewise with EH cleanup.
-	 Free the dominance info first so that cleanup_tree_cfg doesn't try
-	 to verify it.  */
-      if (cfg_altered)
-	{
-          free_dominance_info (CDI_DOMINATORS);
-	  cleanup_tree_cfg ();
-	  calculate_dominance_info (CDI_DOMINATORS);
-	}
+      rewrite_ssa_into_ssa ();
 
-      /* If we are going to iterate (CFG_ALTERED is true), then we must
-	 perform any queued renaming before the next iteration.  */
-      if (cfg_altered
-	  && bitmap_first_set_bit (vars_to_rename) >= 0)
+      if (VARRAY_ACTIVE_SIZE (const_and_copies) <= num_ssa_names)
 	{
-	  rewrite_into_ssa (false);
-	  bitmap_clear (vars_to_rename);
-
-	  /* The into SSA translation may have created new SSA_NAMES whic
-	     affect the size of CONST_AND_COPIES and VRP_DATA.  */
 	  VARRAY_GROW (const_and_copies, num_ssa_names);
 	  VARRAY_GROW (vrp_data, num_ssa_names);
 	}
@@ -655,9 +395,6 @@ tree_ssa_dominator_optimize (void)
     }
   while (cfg_altered);
 
-  /* Remove any unreachable blocks left behind and linearize the CFG.  */
-  cleanup_tree_cfg ();
-
   /* Debugging dumps.  */
   if (dump_file && (dump_flags & TDF_STATS))
     dump_dominator_optimization_stats (dump_file);
@@ -946,23 +683,11 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
 	  /* If we have a known destination for the conditional, then
 	     we can perform this optimization, which saves at least one
 	     conditional jump each time it applies since we get to
-	     bypass the conditional at our original destination. 
-
-	     Note that we can either thread through a block with PHIs
-	     or to a block with PHIs, but not both.  At this time the
-	     bookkeeping to keep the CFG & SSA up-to-date has proven
-	     difficult.  */
+	     bypass the conditional at our original destination.   */
 	  if (dest)
 	    {
-	      int saved_forwardable = bb_ann (e->src)->forwardable;
-	      edge tmp_edge;
-
-	      bb_ann (e->src)->forwardable = 0;
-	      tmp_edge = tree_block_forwards_to (dest);
-	      taken_edge = (tmp_edge ? tmp_edge : taken_edge);
-	      bb_ann (e->src)->forwardable = saved_forwardable;
-	      VARRAY_PUSH_EDGE (redirection_edges, e);
-	      VARRAY_PUSH_EDGE (redirection_edges, taken_edge);
+	      e->aux = taken_edge;
+	      bb_ann (e->dest)->incoming_edge_threaded = true;
 	    }
 	}
     }