This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
New scheme for updating after threading jumps
- From: Jeffrey A Law <law at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 09 Aug 2004 13:12:36 -0600
- Subject: New scheme for updating after threading jumps
- Organization: Red Hat, Inc
- Reply-to: law at redhat dot com
Here's the code to implement the new scheme for updating the SSA
graph after threading jumps.
The key improvement with this patch over the old scheme is we no
longer have to take variables out of SSA form. That saves us a
pretty expensive walk over the IL, which shows up as nearly a
20% improvement in the compile-time performance of the dominator
optimizer and a 1.3% net improvement for cc1.
I'm going to be on the road or in the process of moving cross town
for most of the next two weeks -- meaning further updates will be
correspondingly delayed.
* 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.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1340
diff -c -p -r1.1340 Makefile.in
*** Makefile.in 9 Aug 2004 16:58:41 -0000 1.1340
--- Makefile.in 9 Aug 2004 18:58:42 -0000
*************** OBJS-common = \
*** 898,904 ****
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o
\
tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o
tree-iterator.o \
tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o
tree-ssa-loop.o \
! tree-ssa-loop-niter.o tree-ssa-loop-manip.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o
\
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o
loop-unroll.o \
--- 898,904 ----
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o
\
tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o
tree-iterator.o \
tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o
tree-ssa-loop.o \
! tree-ssa-loop-niter.o tree-ssa-loop-manip.o
tree-ssa-threadupdate.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o
\
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o
loop-unroll.o \
*************** tree-ssa-dom.o : tree-ssa-dom.c $(TREE_F
*** 1632,1637 ****
--- 1632,1641 ----
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h
diagnostic.h \
errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H)
\
$(BASIC_BLOCK_H) domwalk.h real.h tree-pass.h $(FLAGS_H)
langhooks.h
+ tree-ssa-threadupdate.o : tree-ssa-threadupdate.c $(TREE_FLOW_H)
$(CONFIG_H) \
+ $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H)
output.h \
+ diagnostic.h errors.h function.h $(TM_H) coretypes.h $(TREE_DUMP_H)
\
+ $(BASIC_BLOCK_H) $(FLAGS_H) tree-pass.h
tree-ssanames.o : tree-ssanames.c $(CONFIG_H) $(SYSTEM_H) coretypes.h
\
$(TM_H) $(TREE_H) varray.h $(GGC_H) gt-tree-ssanames.h
$(TREE_FLOW_H)
tree-phinodes.o : tree-phinodes.c $(CONFIG_H) $(SYSTEM_H) coretypes.h
\
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.38
diff -c -p -r2.38 tree-cfg.c
*** tree-cfg.c 4 Aug 2004 21:37:06 -0000 2.38
--- tree-cfg.c 9 Aug 2004 18:58:50 -0000
*************** make_goto_expr_edges (basic_block bb)
*** 717,726 ****
/* Remove unreachable blocks and other miscellaneous clean up work.
*/
! void
cleanup_tree_cfg (void)
{
bool something_changed = true;
timevar_push (TV_TREE_CLEANUP_CFG);
--- 717,727 ----
/* Remove unreachable blocks and other miscellaneous clean up work.
*/
! bool
cleanup_tree_cfg (void)
{
bool something_changed = true;
+ bool retval = false;
timevar_push (TV_TREE_CLEANUP_CFG);
*************** cleanup_tree_cfg (void)
*** 731,736 ****
--- 732,738 ----
something_changed = cleanup_control_flow ();
something_changed |= delete_unreachable_blocks ();
something_changed |= thread_jumps ();
+ retval |= something_changed;
}
/* Merging the blocks creates no new opportunities for the other
*************** cleanup_tree_cfg (void)
*** 743,748 ****
--- 745,751 ----
verify_flow_info ();
#endif
timevar_pop (TV_TREE_CLEANUP_CFG);
+ return retval;
}
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.31
diff -c -p -r2.31 tree-flow.h
*** tree-flow.h 5 Aug 2004 21:33:20 -0000 2.31
--- tree-flow.h 9 Aug 2004 18:58:52 -0000
*************** struct bb_ann_d GTY(())
*** 356,361 ****
--- 356,365 ----
/* Nonzero if this block contains an escape point (see
is_escape_site). */
unsigned has_escape_site : 1;
+ /* Nonzero if one or more incoming edges to this block should be
threaded
+ to an outgoing edge of this block. */
+ unsigned incoming_edge_threaded : 1;
+
struct edge_prediction *predictions;
};
*************** extern void debug_loop_ir (void);
*** 474,480 ****
extern void print_loop_ir (FILE *);
extern void cleanup_dead_labels (void);
extern void group_case_labels (void);
! extern void cleanup_tree_cfg (void);
extern tree first_stmt (basic_block);
extern tree last_stmt (basic_block);
extern tree *last_stmt_ptr (basic_block);
--- 478,484 ----
extern void print_loop_ir (FILE *);
extern void cleanup_dead_labels (void);
extern void group_case_labels (void);
! extern bool cleanup_tree_cfg (void);
extern tree first_stmt (basic_block);
extern tree last_stmt (basic_block);
extern tree *last_stmt_ptr (basic_block);
*************** typedef bool (*walk_use_def_chains_fn) (
*** 561,567 ****
/* In tree-ssa.c */
extern void init_tree_ssa (void);
- extern void rewrite_vars_out_of_ssa (bitmap);
extern void dump_reaching_defs (FILE *);
extern void debug_reaching_defs (void);
extern void dump_tree_ssa (FILE *);
--- 565,570 ----
Index: tree-outof-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-outof-ssa.c,v
retrieving revision 2.13
diff -c -p -r2.13 tree-outof-ssa.c
*** tree-outof-ssa.c 28 Jul 2004 05:13:08 -0000 2.13
--- tree-outof-ssa.c 9 Aug 2004 18:58:55 -0000
*************** Boston, MA 02111-1307, USA. */
*** 48,53 ****
--- 48,61 ----
#include "tree-ssa-live.h"
#include "tree-pass.h"
+ /* Flags to pass to remove_ssa_form. */
+
+ #define SSANORM_PERFORM_TER 0x1
+ #define SSANORM_COMBINE_TEMPS 0x2
+ #define SSANORM_REMOVE_ALL_PHIS 0x4
+ #define SSANORM_COALESCE_PARTITIONS 0x8
+ #define SSANORM_USE_COALESCE_LIST 0x10
+
/* Used to hold all the components required to do SSA PHI elimination.
The node and pred/succ list is a simple linear list of nodes and
edges represented as pairs of nodes.
*************** rewrite_trees (var_map map, tree *values
*** 1956,1962 ****
/* Remove the variables specified in MAP from SSA form. Any debug
information
is sent to DUMP. FLAGS indicate what options should be used. */
! void
remove_ssa_form (FILE *dump, var_map map, int flags)
{
tree_live_info_p liveinfo;
--- 1964,1970 ----
/* Remove the variables specified in MAP from SSA form. Any debug
information
is sent to DUMP. FLAGS indicate what options should be used. */
! static void
remove_ssa_form (FILE *dump, var_map map, int flags)
{
tree_live_info_p liveinfo;
*************** remove_ssa_form (FILE *dump, var_map map
*** 2039,2160 ****
dump_file = save;
}
-
- /* Take a subset of the variables VARS in the current function out of
SSA
- form. */
-
- void
- rewrite_vars_out_of_ssa (bitmap vars)
- {
- if (bitmap_first_set_bit (vars) >= 0)
- {
- var_map map;
- basic_block bb;
- tree phi;
- int i;
- int ssa_flags;
-
- /* Search for PHIs in which one of the PHI arguments is marked
for
- translation out of SSA form, but for which the PHI result is not
- marked for translation out of SSA form.
-
- Our per-variable out of SSA translation can not handle that case;
- however we can easily handle it here by creating a new instance
- of the PHI result's underlying variable and initializing it to
- the offending PHI argument on the edge associated with the
- PHI argument. We then change the PHI argument to use our new
- instead of the PHI's underlying variable.
-
- You might think we could register partitions for the out-of-ssa
- translation here and avoid a second walk of the PHI nodes. No
- such luck since the size of the var map will change if we have
- to manually take variables out of SSA form here. */
- FOR_EACH_BB (bb)
- {
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- {
- tree result = SSA_NAME_VAR (PHI_RESULT (phi));
-
- /* If the definition is marked for renaming, then we need
- to do nothing more for this PHI node. */
- if (bitmap_bit_p (vars, var_ann (result)->uid))
- continue;
-
- /* Look at all the arguments and see if any of them are
- marked for renaming. If so, we need to handle them
- specially. */
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
- {
- tree arg = PHI_ARG_DEF (phi, i);
-
- /* If the argument is not an SSA_NAME, then we can ignore
- this argument. */
- if (TREE_CODE (arg) != SSA_NAME)
- continue;
-
- /* If this argument is marked for renaming, then we need
- to undo the copy propagation so that we can take
- the argument out of SSA form without taking the
- result out of SSA form. */
- arg = SSA_NAME_VAR (arg);
- if (bitmap_bit_p (vars, var_ann (arg)->uid))
- {
- tree new_name, copy;
-
- /* Get a new SSA_NAME for the copy, it is based on
- the result, not the argument! We use the PHI
- as the definition since we haven't created the
- definition statement yet. */
- new_name = make_ssa_name (result, phi);
-
- /* Now create the copy statement. */
- copy = build (MODIFY_EXPR, TREE_TYPE (arg),
- new_name, PHI_ARG_DEF (phi, i));
-
- /* Now update SSA_NAME_DEF_STMT to point to the
- newly created statement. */
- SSA_NAME_DEF_STMT (new_name) = copy;
-
- /* Now make the argument reference our new SSA_NAME. */
- SET_PHI_ARG_DEF (phi, i, new_name);
-
- /* Queue the statement for insertion. */
- bsi_insert_on_edge (PHI_ARG_EDGE (phi, i), copy);
- modify_stmt (copy);
- }
- }
- }
- }
-
- /* If any copies were inserted on edges, actually insert them
now. */
- bsi_commit_edge_inserts (NULL);
-
- /* Now register partitions for all instances of the variables we
- are taking out of SSA form. */
- map = init_var_map (num_ssa_names + 1);
- register_ssa_partitions_for_vars (vars, map);
-
- /* Now that we have all the partitions registered, translate the
- appropriate variables out of SSA form. */
- ssa_flags = SSANORM_COALESCE_PARTITIONS;
- if (flag_tree_combine_temps)
- ssa_flags |= SSANORM_COMBINE_TEMPS;
- remove_ssa_form (dump_file, map, ssa_flags);
-
- /* And finally, reset the out_of_ssa flag for each of the vars
- we just took out of SSA form. */
- EXECUTE_IF_SET_IN_BITMAP (vars, 0, i,
- {
- var_ann (referenced_var (i))->out_of_ssa_tag = 0;
- });
-
- /* Free the map as we are done with it. */
- delete_var_map (map);
-
- }
- }
-
-
/* Take the current function out of SSA form, as described in
R. Morgan, ``Building an Optimizing Compiler'',
Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
--- 2047,2052 ----
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-phinodes.c,v
retrieving revision 2.6
diff -c -p -r2.6 tree-phinodes.c
*** tree-phinodes.c 22 Jul 2004 16:39:48 -0000 2.6
--- tree-phinodes.c 9 Aug 2004 18:58:57 -0000
*************** add_phi_arg (tree *phi, tree def, edge e
*** 335,351 ****
release the old PHI node. */
if (*phi != old_phi)
{
release_phi_node (old_phi);
/* Update the list head if replacing the first listed phi. */
! if (phi_nodes (e->dest) == old_phi)
! bb_ann (e->dest)->phi_nodes = *phi;
else
{
/* Traverse the list looking for the phi node to chain to. */
tree p;
! for (p = phi_nodes (e->dest);
p && PHI_CHAIN (p) != old_phi;
p = PHI_CHAIN (p))
;
--- 335,358 ----
release the old PHI node. */
if (*phi != old_phi)
{
+ /* Extract the basic block for the PHI from the PHI's annotation
+ rather than the edge. This works better as the edge's
+ destination may not currently be the block with the PHI
+ node if we are in the process of threading the edge to
+ a new destination. */
+ basic_block bb = bb_for_stmt (*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))
;
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.28
diff -c -p -r2.28 tree-ssa-dom.c
*** tree-ssa-dom.c 28 Jul 2004 05:13:08 -0000 2.28
--- tree-ssa-dom.c 9 Aug 2004 18:59:01 -0000
*************** static htab_t avail_exprs;
*** 63,68 ****
--- 63,69 ----
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. */
*************** struct vrp_element
*** 160,177 ****
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;
--- 161,166 ----
*************** static void restore_vars_to_original_val
*** 267,273 ****
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. */
--- 256,261 ----
*************** set_value_for (tree var, tree value, var
*** 301,540 ****
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
--- 289,294 ----
*************** redirect_edges_and_update_ssa_graph (var
*** 544,550 ****
static void
tree_ssa_dominator_optimize (void)
{
- basic_block bb;
struct dom_walk_data walk_data;
unsigned int i;
--- 298,303 ----
*************** tree_ssa_dominator_optimize (void)
*** 560,566 ****
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 ();
--- 313,318 ----
*************** tree_ssa_dominator_optimize (void)
*** 583,593 ****
/* 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
--- 335,340 ----
*************** tree_ssa_dominator_optimize (void)
*** 603,645 ****
/* Recursively walk the dominator tree optimizing statements.
*/
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
! /* Wipe the hash tables. */
! if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
! redirect_edges_and_update_ssa_graph (redirection_edges);
if (bitmap_first_set_bit (need_eh_cleanup) >= 0)
{
! 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 ();
! /* 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);
! }
!
! /* 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)
{
- 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);
}
--- 350,385 ----
/* Recursively walk the dominator tree optimizing statements.
*/
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
! /* 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);
! }
! /* 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);
bitmap_zero (need_eh_cleanup);
}
! free_dominance_info (CDI_DOMINATORS);
! cfg_altered = cleanup_tree_cfg ();
! calculate_dominance_info (CDI_DOMINATORS);
!
! rewrite_ssa_into_ssa ();
! if (VARRAY_ACTIVE_SIZE (const_and_copies) <= num_ssa_names)
{
VARRAY_GROW (const_and_copies, num_ssa_names);
VARRAY_GROW (vrp_data, num_ssa_names);
}
*************** tree_ssa_dominator_optimize (void)
*** 655,663 ****
}
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);
--- 395,400 ----
*************** thread_across_edge (struct dom_walk_data
*** 946,968 ****
/* 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. */
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);
}
}
}
--- 683,693 ----
/* 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. */
if (dest)
{
! e->aux = taken_edge;
! bb_ann (e->dest)->incoming_edge_threaded = true;
}
}
}
Index: tree-ssa-live.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-live.c,v
retrieving revision 2.12
diff -c -p -r2.12 tree-ssa-live.c
*** tree-ssa-live.c 22 Jul 2004 18:04:42 -0000 2.12
--- tree-ssa-live.c 9 Aug 2004 18:59:04 -0000
*************** dump_live_info (FILE *f, tree_live_info_
*** 1827,1921 ****
}
}
}
-
- /* Register partitions in MAP so that we can take VARS out of SSA
form.
- This requires a walk over all the PHI nodes and all the
statements. */
-
- void
- register_ssa_partitions_for_vars (bitmap vars, var_map map)
- {
- basic_block bb;
-
- if (bitmap_first_set_bit (vars) >= 0)
- {
-
- /* Find every instance (SSA_NAME) of variables in VARs and
- register a new partition for them. This requires examining
- every statement and every PHI node once. */
- FOR_EACH_BB (bb)
- {
- block_stmt_iterator bsi;
- tree next;
- tree phi;
-
- /* Register partitions for SSA_NAMEs appearing in the PHI
- nodes in this basic block.
-
- Note we delete PHI nodes in this loop if they are
- associated with virtual vars which are going to be
- renamed. */
- for (phi = phi_nodes (bb); phi; phi = next)
- {
- tree result = SSA_NAME_VAR (PHI_RESULT (phi));
-
- next = PHI_CHAIN (phi);
- if (bitmap_bit_p (vars, var_ann (result)->uid))
- {
- if (! is_gimple_reg (result))
- remove_phi_node (phi, NULL_TREE, bb);
- else
- {
- int i;
-
- /* Register a partition for the result. */
- register_ssa_partition (map, PHI_RESULT (phi), 0);
-
- /* Register a partition for each argument as needed. */
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
- {
- tree arg = PHI_ARG_DEF (phi, i);
-
- if (TREE_CODE (arg) != SSA_NAME)
- continue;
- if (!bitmap_bit_p (vars,
- var_ann (SSA_NAME_VAR (arg))->uid))
- continue;
-
- register_ssa_partition (map, arg, 1);
- }
- }
- }
- }
-
- /* Now register partitions for SSA_NAMEs appearing in each
- statement in this block. */
- for (bsi = bsi_start (bb); ! bsi_end_p (bsi); bsi_next (&bsi))
- {
- stmt_ann_t ann = stmt_ann (bsi_stmt (bsi));
- use_optype uses = USE_OPS (ann);
- def_optype defs = DEF_OPS (ann);
- unsigned int i;
-
- for (i = 0; i < NUM_USES (uses); i++)
- {
- tree op = USE_OP (uses, i);
-
- if (TREE_CODE (op) == SSA_NAME
- && bitmap_bit_p (vars, var_ann (SSA_NAME_VAR (op))->uid))
- register_ssa_partition (map, op, 1);
- }
-
- for (i = 0; i < NUM_DEFS (defs); i++)
- {
- tree op = DEF_OP (defs, i);
-
- if (TREE_CODE (op) == SSA_NAME
- && bitmap_bit_p (vars,
- var_ann (SSA_NAME_VAR (op))->uid))
- register_ssa_partition (map, op, 0);
- }
- }
- }
- }
- }
-
--- 1827,1829 ----
Index: tree-ssa-live.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-live.h,v
retrieving revision 2.4
diff -c -p -r2.4 tree-ssa-live.h
*** tree-ssa-live.h 3 Jun 2004 15:01:08 -0000 2.4
--- tree-ssa-live.h 9 Aug 2004 18:59:07 -0000
*************** typedef struct _var_map
*** 58,79 ****
#define VARMAP_NORMAL 0
#define VARMAP_NO_SINGLE_DEFS 1
- /* Flags to pass to remove_ssa_form. */
-
- #define SSANORM_PERFORM_TER 0x1
- #define SSANORM_COMBINE_TEMPS 0x2
- #define SSANORM_REMOVE_ALL_PHIS 0x4
- #define SSANORM_COALESCE_PARTITIONS 0x8
- #define SSANORM_USE_COALESCE_LIST 0x10
-
extern var_map init_var_map (int);
extern void delete_var_map (var_map);
extern void dump_var_map (FILE *, var_map);
extern int var_union (var_map, tree, tree);
extern void change_partition_var (var_map, tree, int);
extern void compact_var_map (var_map, int);
- extern void remove_ssa_form (FILE *, var_map, int);
- extern void register_ssa_partitions_for_vars (bitmap vars, var_map
map);
extern tree make_ssa_temp (tree);
static inline int num_var_partitions (var_map);
--- 58,69 ----
Index: tree-ssa-threadupdate.c
===================================================================
RCS file: tree-ssa-threadupdate.c
diff -N tree-ssa-threadupdate.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-ssa-threadupdate.c 9 Aug 2004 18:59:07 -0000
***************
*** 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;
+ }
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.584
diff -c -p -r1.584 tree.h
*** tree.h 9 Aug 2004 07:14:17 -0000 1.584
--- tree.h 9 Aug 2004 18:59:15 -0000
*************** extern bool in_gimple_form;
*** 3770,3773 ****
--- 3770,3776 ----
tree lower_bound_in_type (tree, tree);
tree upper_bound_in_type (tree, tree);
+ /* In tree-ssa-threadupdate.c. */
+ extern bool thread_through_all_blocks (void);
+
#endif /* GCC_TREE_H */