This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Dominator walker infrastructure improvement
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 12 Feb 2004 09:42:36 -0700
- Subject: [tree-ssa] Dominator walker infrastructure improvement
- Reply-to: law at redhat dot com
I have always planned for the dominator walker to have the capability to
walk statements either first->last or last->first within a block and for
that code to live in the dominator walker itself (rather than in the clients).
This patch adds that capability to the dominator walker, controlled by a
bit in the dominator walker structure each client initializes.
There are no checked-in clients of the backwards statement walk, though I
have used it here for a block-local dead store elimination pass.
Similarly I have always planned for the dominator walker to be able to
walk the post-dominator tree. Control over walking the dominator vs
post-dominator tree is also controlled by field in the dominator walker
structure each client initializes.
I have verified that the post-dominator walk visits blocks in the correct
order, but the skeleton code for DSE isn't really ready to take advantage
of the post-dominator tree walk to eliminate more dead stores.
Hopefully this is the last significant change to the dominator walker for
a while. The only remaining issue is that statement walking is currently
tree specific. One day it might be useful to change it so that it could
walk trees or RTL.
Bootstrapped and regression tested on i686-pc-linux-gnu.
* domwalk.c (walk_dominator_tree): Move statement walking from
clients into here. Walk statements in forward or backward order
as requested by the client. Walk either the dominator tree or
the post-dominator tree as requested by the client.
* domwalk.h (dom_walk_data): Add two fields to control direction of
statement walk and dominator vs post-dominator tree walk. Add
BSI argument to the per-statement callbacks.
* tree-ssa-dom.c (optimize_stmt): Update prototype so that it can
be directly used as a callback for the dominator tree walker.
Update stmts_to_rescan here.
(tree_ssa_dominator_optimize): Initialize new fields in the dominator
walker structure. Use optimize_stmt instead of dom_opt_walk_stmts
for statement callback.
(dom_opt_walk_stmts): Kill. No longer used.
* tree-ssa.c (mark_def_sites): Update prototype so that it can be
called as the per-statement callback. No longer walk statements here.
(mark_def_sites_initialize_block): New.
(rewrite_stmt): Update prototype so that it can be called as the
per-statement callback.
(rewrite_walk_stmts): Kill. No longer used.
(rewrite_into_ssa): Initialize new fields in the dominator walker
structure. Use rewrite_stmt instead of rewrite_walk_stmts. Add
mark_def_sites_initialize_block callback.
Index: domwalk.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/domwalk.c,v
retrieving revision 1.1.2.9
diff -c -3 -p -r1.1.2.9 domwalk.c
*** domwalk.c 9 Feb 2004 23:11:26 -0000 1.1.2.9
--- domwalk.c 12 Feb 2004 16:27:14 -0000
*************** Boston, MA 02111-1307, USA. */
*** 51,56 ****
--- 51,60 ----
we have a dominator tree.
+ [ Note this walker can also walk the post-dominator tree, which is
+ defined in a similar manner. ie, block B1 is said to post-dominate
+ block B2 if all paths from B2 to the exit block must pass through
+ B1. ]
For example, given the CFG
*************** Boston, MA 02111-1307, USA. */
*** 123,133 ****
TODO:
! Right now walking statements is left to to the statement walker
! callback itself. Instead the dominator optimizer itself should walk
! the statements calling a callback for each statement encountered.
! The direction of the statement walk would be determined by a flag
! in the main dominator walker structure. */
/* Recursively walk the dominator tree.
--- 127,135 ----
TODO:
! Walking statements is based on the block statement iterator abstraction,
! which is currently an abstraction over walking tree statements. Thus
! the dominator walker is currently only useful for trees. */
/* Recursively walk the dominator tree.
*************** walk_dominator_tree (struct dom_walk_dat
*** 142,147 ****
--- 144,150 ----
{
void *bd = NULL;
basic_block dest;
+ block_stmt_iterator bsi;
/* Callback to initialize the local data structure. */
if (walk_data->initialize_block_local_data)
*************** walk_dominator_tree (struct dom_walk_dat
*** 177,183 ****
/* Statement walk before walking dominator children. */
if (walk_data->before_dom_children_walk_stmts)
! (*walk_data->before_dom_children_walk_stmts) (walk_data, bb);
/* Callback for operations to execute before we have walked the
dominator children, and after we walk statements. */
--- 180,193 ----
/* Statement walk before walking dominator children. */
if (walk_data->before_dom_children_walk_stmts)
! {
! if (walk_data->walk_stmts_backward)
! for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
! (*walk_data->before_dom_children_walk_stmts) (walk_data, bb, bsi);
! else
! for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! (*walk_data->before_dom_children_walk_stmts) (walk_data, bb, bsi);
! }
/* Callback for operations to execute before we have walked the
dominator children, and after we walk statements. */
*************** walk_dominator_tree (struct dom_walk_dat
*** 185,193 ****
(*walk_data->before_dom_children_after_stmts) (walk_data, bb);
/* Recursively call ourselves on the dominator children of BB. */
! for (dest = first_dom_son (CDI_DOMINATORS, bb);
dest;
! dest = next_dom_son (CDI_DOMINATORS, dest))
{
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
--- 195,203 ----
(*walk_data->before_dom_children_after_stmts) (walk_data, bb);
/* Recursively call ourselves on the dominator children of BB. */
! for (dest = first_dom_son (walk_data->dom_direction, bb);
dest;
! dest = next_dom_son (walk_data->dom_direction, dest))
{
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
*************** walk_dominator_tree (struct dom_walk_dat
*** 202,208 ****
/* Statement walk after walking dominator children. */
if (walk_data->after_dom_children_walk_stmts)
! (*walk_data->after_dom_children_walk_stmts) (walk_data, bb);
/* Callback for operations to execute after we have walked the
dominator children and after we have walked statements. */
--- 212,225 ----
/* Statement walk after walking dominator children. */
if (walk_data->after_dom_children_walk_stmts)
! {
! if (walk_data->walk_stmts_backward)
! for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
! (*walk_data->after_dom_children_walk_stmts) (walk_data, bb, bsi);
! else
! for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! (*walk_data->after_dom_children_walk_stmts) (walk_data, bb, bsi);
! }
/* Callback for operations to execute after we have walked the
dominator children and after we have walked statements. */
Index: domwalk.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/domwalk.h,v
retrieving revision 1.1.2.6
diff -c -3 -p -r1.1.2.6 domwalk.h
*** domwalk.h 9 Feb 2004 23:11:26 -0000 1.1.2.6
--- domwalk.h 12 Feb 2004 16:27:14 -0000
*************** Boston, MA 02111-1307, USA. */
*** 21,30 ****
/* This is the main data structure for the dominator walker. It provides
the callback hooks as well as a convenient place to hang block local
! data. Eventually it will probably include pass global data as well. */
struct dom_walk_data
{
/* Function to initialize block local data.
Note that the dominator walker infrastructure may provide a new
--- 21,45 ----
/* This is the main data structure for the dominator walker. It provides
the callback hooks as well as a convenient place to hang block local
! data and pass-global data. */
struct dom_walk_data
{
+ /* This is the direction of the dominator tree we want to walk. ie,
+ if it is set to CDI_DOMINATORS, then we walk the dominator tree,
+ if it is set to CDI_POST_DOMINATORS, then we walk the post
+ dominator tree. */
+ ENUM_BITFIELD (cdi_direction) dom_direction : 2;
+
+ /* Nonzero if the statement walker should walk the statements from
+ last to first within a basic block instead of first to last.
+
+ Note this affects both statement walkers. We haven't yet needed
+ to use the second statement walker for anything, so it's hard to
+ predict if we really need the ability to select their direction
+ independently. */
+ bool walk_stmts_backward : 1;
+
/* Function to initialize block local data.
Note that the dominator walker infrastructure may provide a new
*************** struct dom_walk_data
*** 48,54 ****
/* Function to call to walk statements before the recursive walk
of the dominator children. */
void (*before_dom_children_walk_stmts) (struct dom_walk_data *,
! basic_block);
/* Function to call after the statement walk occurring before the
recursive walk of the dominator children. */
--- 63,69 ----
/* Function to call to walk statements before the recursive walk
of the dominator children. */
void (*before_dom_children_walk_stmts) (struct dom_walk_data *,
! basic_block, block_stmt_iterator);
/* Function to call after the statement walk occurring before the
recursive walk of the dominator children. */
*************** struct dom_walk_data
*** 63,69 ****
/* Function to call to walk statements after the recursive walk
of the dominator children. */
void (*after_dom_children_walk_stmts) (struct dom_walk_data *,
! basic_block);
/* Function to call after the statement walk occurring after the
recursive walk of the dominator children.
--- 78,84 ----
/* Function to call to walk statements after the recursive walk
of the dominator children. */
void (*after_dom_children_walk_stmts) (struct dom_walk_data *,
! basic_block, block_stmt_iterator);
/* Function to call after the statement walk occurring after the
recursive walk of the dominator children.
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.133
diff -c -3 -p -r1.1.2.133 tree-ssa-dom.c
*** tree-ssa-dom.c 10 Feb 2004 23:23:16 -0000 1.1.2.133
--- tree-ssa-dom.c 12 Feb 2004 16:27:23 -0000
*************** struct eq_expr_value
*** 208,214 ****
};
/* Local functions. */
! static bool optimize_stmt (struct dom_walk_data *, block_stmt_iterator);
static inline tree get_value_for (tree, varray_type table);
static inline void set_value_for (tree, tree, varray_type table);
static tree lookup_avail_expr (tree, varray_type *, bool);
--- 208,216 ----
};
/* Local functions. */
! static void optimize_stmt (struct dom_walk_data *,
! basic_block bb,
! block_stmt_iterator);
static inline tree get_value_for (tree, varray_type table);
static inline void set_value_for (tree, tree, varray_type table);
static tree lookup_avail_expr (tree, varray_type *, bool);
*************** static void dom_opt_finalize_block (stru
*** 248,254 ****
static void dom_opt_initialize_block_local_data (struct dom_walk_data *,
basic_block, bool);
static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
- static void dom_opt_walk_stmts (struct dom_walk_data *, basic_block);
static void cprop_into_phis (struct dom_walk_data *, basic_block);
static void remove_local_expressions_from_table (varray_type locals,
unsigned limit,
--- 250,255 ----
*************** tree_ssa_dominator_optimize (void)
*** 574,581 ****
--- 575,586 ----
/* Setup callbacks for the generic dominator tree walker. */
+ walk_data.walk_stmts_backward = false;
+ walk_data.dom_direction = CDI_DOMINATORS;
walk_data.initialize_block_local_data = dom_opt_initialize_block_local_data
;
walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
+ walk_data.before_dom_children_walk_stmts = optimize_stmt;
+ walk_data.before_dom_children_after_stmts = cprop_into_phis;
walk_data.after_dom_children_before_stmts = NULL;
walk_data.after_dom_children_walk_stmts = NULL;
walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
*************** tree_ssa_dominator_optimize (void)
*** 584,591 ****
structure. */
walk_data.global_data = NULL;
walk_data.block_local_data_size = sizeof (struct dom_walk_block_data);
- walk_data.before_dom_children_walk_stmts = dom_opt_walk_stmts;
- walk_data.before_dom_children_after_stmts = cprop_into_phis;
/* Now initialize the dominator walker. */
init_walk_dominator_tree (&walk_data);
--- 589,594 ----
*************** record_equivalences_from_incoming_edge (
*** 1433,1491 ****
&bd->const_and_copies);
}
- /* Perform a depth-first traversal of the dominator tree looking for
- redundant expressions and copy/constant propagation opportunities.
-
- Expressions computed by each statement are looked up in the
- AVAIL_EXPRS table. If a statement is found to make a redundant
- computation, it is marked for removal. Otherwise, the expression
- computed by the statement is assigned a value number and entered
- into the AVAIL_EXPRS table. See optimize_stmt for details on the
- types of redundancies handled during renaming.
-
- Once we've optimized the statements in this block we recursively
- optimize every dominator child of this block.
-
- Finally, remove all the expressions added to the AVAIL_EXPRS
- table during renaming. This is because the expressions made
- available to block BB and its dominator children are not valid for
- blocks above BB in the dominator tree.
-
- EDGE_FLAGS are the flags for the incoming edge from BB's dominator
- parent block. This is used to determine whether BB is the first block
- of a THEN_CLAUSE or an ELSE_CLAUSE.
-
- VARS_TO_RENAME is a bitmap representing variables that will need to be
- renamed into SSA after dominator optimization.
-
- CFG_ALTERED is set to true if cfg is altered. */
-
- static void
- dom_opt_walk_stmts (struct dom_walk_data *walk_data, basic_block bb)
- {
- block_stmt_iterator si;
- struct dom_walk_block_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
-
- /* Optimize each statement within the basic block. */
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
- {
- /* Optimization may have exposed new symbols that need to be renamed
- into SSA form. If that happens, queue the statement to re-scan its
- operands after finishing optimizing this block and its dominator
- children. Notice that we cannot re-scan the statement immediately
- because that would change the statement's value number. If the
- statement had been added to AVAIL_EXPRS, we would not be able to
- find it again. */
- if (optimize_stmt (walk_data, si))
- {
- if (! bd->stmts_to_rescan)
- VARRAY_TREE_INIT (bd->stmts_to_rescan, 20, "stmts_to_rescan");
- VARRAY_PUSH_TREE (bd->stmts_to_rescan, bsi_stmt (si));
- }
- }
- }
-
/* Dump SSA statistics on FILE. */
void
--- 1436,1441 ----
*************** record_equivalences_from_stmt (tree stmt
*** 2675,2686 ****
}
}
! /* Optimize the statement pointed by iterator SI into SSA form.
- BLOCK_AVAIL_EXPRS_P points to a stack with all the expressions that have
- been computed in this block and are available in children blocks to
- be reused.
-
We try to perform some simplistic global redundancy elimination and
constant propagation:
--- 2625,2632 ----
}
}
! /* Optimize the statement pointed by iterator SI.
We try to perform some simplistic global redundancy elimination and
constant propagation:
*************** record_equivalences_from_stmt (tree stmt
*** 2694,2701 ****
assignment is found, we map the value on the RHS of the assignment to
the variable in the LHS in the CONST_AND_COPIES table. */
! static bool
! optimize_stmt (struct dom_walk_data *walk_data, block_stmt_iterator si)
{
stmt_ann_t ann;
tree stmt;
--- 2640,2649 ----
assignment is found, we map the value on the RHS of the assignment to
the variable in the LHS in the CONST_AND_COPIES table. */
! static void
! optimize_stmt (struct dom_walk_data *walk_data,
! basic_block bb ATTRIBUTE_UNUSED,
! block_stmt_iterator si)
{
stmt_ann_t ann;
tree stmt;
*************** optimize_stmt (struct dom_walk_data *wal
*** 2815,2821 ****
cfg_altered = true;
}
! return may_have_exposed_new_symbols;
}
/* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
--- 2763,2774 ----
cfg_altered = true;
}
! if (may_have_exposed_new_symbols)
! {
! if (! bd->stmts_to_rescan)
! VARRAY_TREE_INIT (bd->stmts_to_rescan, 20, "stmts_to_rescan");
! VARRAY_PUSH_TREE (bd->stmts_to_rescan, bsi_stmt (si));
! }
}
/* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.197
diff -c -3 -p -r1.1.4.197 tree-ssa.c
*** tree-ssa.c 11 Feb 2004 16:59:43 -0000 1.1.4.197
--- tree-ssa.c 12 Feb 2004 16:27:30 -0000
*************** static void rewrite_finalize_block (stru
*** 164,178 ****
static void rewrite_initialize_block_local_data (struct dom_walk_data *,
basic_block, bool);
static void rewrite_initialize_block (struct dom_walk_data *, basic_block);
- static void rewrite_walk_stmts (struct dom_walk_data *, basic_block);
static void rewrite_add_phi_arguments (struct dom_walk_data *, basic_block);
! static void mark_def_sites (struct dom_walk_data *walk_data, basic_block bb);
static void compute_global_livein (bitmap, bitmap);
static void set_def_block (tree, basic_block);
static void set_livein_block (tree, basic_block);
static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
static void insert_phi_nodes (bitmap *);
! static void rewrite_stmt (block_stmt_iterator, varray_type *);
static inline void rewrite_operand (tree *);
static void insert_phi_nodes_for (tree, bitmap *);
static tree get_reaching_def (tree);
--- 164,182 ----
static void rewrite_initialize_block_local_data (struct dom_walk_data *,
basic_block, bool);
static void rewrite_initialize_block (struct dom_walk_data *, basic_block);
static void rewrite_add_phi_arguments (struct dom_walk_data *, basic_block);
! static void mark_def_sites (struct dom_walk_data *walk_data,
! basic_block bb, block_stmt_iterator);
! static void mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
! basic_block bb);
static void compute_global_livein (bitmap, bitmap);
static void set_def_block (tree, basic_block);
static void set_livein_block (tree, basic_block);
static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
static void insert_phi_nodes (bitmap *);
! static void rewrite_stmt (struct dom_walk_data *,
! basic_block,
! block_stmt_iterator);
static inline void rewrite_operand (tree *);
static void insert_phi_nodes_for (tree, bitmap *);
static tree get_reaching_def (tree);
*************** rewrite_into_ssa (void)
*** 392,399 ****
/* Setup callbacks for the generic dominator tree walker to find and
mark definition sites. */
walk_data.initialize_block_local_data = NULL;
! walk_data.before_dom_children_before_stmts = NULL;
walk_data.before_dom_children_walk_stmts = mark_def_sites;
walk_data.before_dom_children_after_stmts = NULL;
walk_data.after_dom_children_before_stmts = NULL;
--- 396,405 ----
/* Setup callbacks for the generic dominator tree walker to find and
mark definition sites. */
+ walk_data.walk_stmts_backward = false;
+ walk_data.dom_direction = CDI_DOMINATORS;
walk_data.initialize_block_local_data = NULL;
! walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_bloc
k;
walk_data.before_dom_children_walk_stmts = mark_def_sites;
walk_data.before_dom_children_after_stmts = NULL;
walk_data.after_dom_children_before_stmts = NULL;
*************** rewrite_into_ssa (void)
*** 428,436 ****
timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
/* Setup callbacks for the generic dominator tree walker. */
walk_data.initialize_block_local_data = rewrite_initialize_block_local_data
;
walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
! walk_data.before_dom_children_walk_stmts = rewrite_walk_stmts;
walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
walk_data.after_dom_children_before_stmts = NULL;
walk_data.after_dom_children_walk_stmts = NULL;
--- 434,444 ----
timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
/* Setup callbacks for the generic dominator tree walker. */
+ walk_data.walk_stmts_backward = false;
+ walk_data.dom_direction = CDI_DOMINATORS;
walk_data.initialize_block_local_data = rewrite_initialize_block_local_data
;
walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
! walk_data.before_dom_children_walk_stmts = rewrite_stmt;
walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
walk_data.after_dom_children_before_stmts = NULL;
walk_data.after_dom_children_walk_stmts = NULL;
*************** compute_global_livein (bitmap livein, bi
*** 536,541 ****
--- 544,561 ----
free (worklist);
}
+ /* Block initialization routine for mark_def_sites. Clear the
+ KILLS bitmap at the start of each block. */
+ static void
+ mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
+ basic_block bb ATTRIBUTE_UNUSED)
+ {
+ struct mark_def_sites_global_data *gd = walk_data->global_data;
+ sbitmap kills = gd->kills;
+
+ sbitmap_zero (kills);
+ }
+
/* Collect definition sites for every variable in the function.
Return a bitmap for the set of referenced variables which are
"nonlocal", ie those which are live across block boundaries.
*************** compute_global_livein (bitmap livein, bi
*** 543,628 ****
we create. */
static void
! mark_def_sites (struct dom_walk_data *walk_data, basic_block bb)
{
struct mark_def_sites_global_data *gd = walk_data->global_data;
sbitmap kills = gd->kills;
! block_stmt_iterator si;
/* Mark all the blocks that have definitions for each variable in the
VARS_TO_RENAME bitmap. */
! sbitmap_zero (kills);
! for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
! vdef_optype vdefs;
! vuse_optype vuses;
! def_optype defs;
! use_optype uses;
! size_t i, uid;
! tree stmt;
! stmt_ann_t ann;
! stmt = bsi_stmt (si);
! get_stmt_operands (stmt);
! ann = stmt_ann (stmt);
!
! /* If a variable is used before being set, then the variable
! is live across a block boundary, so add it to NONLOCAL_VARS. */
! uses = USE_OPS (ann);
! for (i = 0; i < NUM_USES (uses); i++)
! {
! tree *use_p = USE_OP_PTR (uses, i);
!
! if (prepare_operand_for_rename (use_p, &uid)
! && !TEST_BIT (kills, uid))
! set_livein_block (*use_p, bb);
! }
! /* Similarly for virtual uses. */
! vuses = VUSE_OPS (ann);
! for (i = 0; i < NUM_VUSES (vuses); i++)
! {
! tree *use_p = VUSE_OP_PTR (vuses, i);
! if (prepare_operand_for_rename (use_p, &uid)
! && !TEST_BIT (kills, uid))
! set_livein_block (*use_p, bb);
! }
! /* Note that virtual definitions are irrelevant for computing
! KILLED_VARS because a VDEF does not constitute a killing
! definition of the variable. However, the operand of a virtual
! definitions is a use of the variable, so it may affect
! GLOBALS. */
! vdefs = VDEF_OPS (ann);
! for (i = 0; i < NUM_VDEFS (vdefs); i++)
! {
! size_t dummy;
! if (prepare_operand_for_rename (VDEF_OP_PTR (vdefs, i), &uid)
! && prepare_operand_for_rename (VDEF_RESULT_PTR (vdefs, i),
! &dummy))
! {
! VDEF_RESULT (vdefs, i) = VDEF_OP (vdefs, i);
! set_def_block (VDEF_RESULT (vdefs, i), bb);
! if (!TEST_BIT (kills, uid))
! set_livein_block (VDEF_OP (vdefs, i), bb);
! }
}
! /* Now process the definition made by this statement. */
! defs = DEF_OPS (ann);
! for (i = 0; i < NUM_DEFS (defs); i++)
! {
! tree *def_p = DEF_OP_PTR (defs, i);
! if (prepare_operand_for_rename (def_p, &uid))
! {
! set_def_block (*def_p, bb);
! SET_BIT (kills, uid);
! }
}
}
}
--- 563,643 ----
we create. */
static void
! mark_def_sites (struct dom_walk_data *walk_data,
! basic_block bb,
! block_stmt_iterator bsi)
{
struct mark_def_sites_global_data *gd = walk_data->global_data;
sbitmap kills = gd->kills;
! vdef_optype vdefs;
! vuse_optype vuses;
! def_optype defs;
! use_optype uses;
! size_t i, uid;
! tree stmt;
! stmt_ann_t ann;
/* Mark all the blocks that have definitions for each variable in the
VARS_TO_RENAME bitmap. */
! stmt = bsi_stmt (bsi);
! get_stmt_operands (stmt);
! ann = stmt_ann (stmt);
! /* If a variable is used before being set, then the variable
! is live across a block boundary, so add it to NONLOCAL_VARS. */
! uses = USE_OPS (ann);
! for (i = 0; i < NUM_USES (uses); i++)
{
! tree *use_p = USE_OP_PTR (uses, i);
! if (prepare_operand_for_rename (use_p, &uid)
! && !TEST_BIT (kills, uid))
! set_livein_block (*use_p, bb);
! }
! /* Similarly for virtual uses. */
! vuses = VUSE_OPS (ann);
! for (i = 0; i < NUM_VUSES (vuses); i++)
! {
! tree *use_p = VUSE_OP_PTR (vuses, i);
! if (prepare_operand_for_rename (use_p, &uid)
! && !TEST_BIT (kills, uid))
! set_livein_block (*use_p, bb);
! }
! /* Note that virtual definitions are irrelevant for computing
! KILLED_VARS because a VDEF does not constitute a killing
! definition of the variable. However, the operand of a virtual
! definitions is a use of the variable, so it may affect
! GLOBALS. */
! vdefs = VDEF_OPS (ann);
! for (i = 0; i < NUM_VDEFS (vdefs); i++)
! {
! size_t dummy;
! if (prepare_operand_for_rename (VDEF_OP_PTR (vdefs, i), &uid)
! && prepare_operand_for_rename (VDEF_RESULT_PTR (vdefs, i),
! &dummy))
! {
! VDEF_RESULT (vdefs, i) = VDEF_OP (vdefs, i);
! set_def_block (VDEF_RESULT (vdefs, i), bb);
! if (!TEST_BIT (kills, uid))
! set_livein_block (VDEF_OP (vdefs, i), bb);
}
+ }
! /* Now process the definition made by this statement. */
! defs = DEF_OPS (ann);
! for (i = 0; i < NUM_DEFS (defs); i++)
! {
! tree *def_p = DEF_OP_PTR (defs, i);
! if (prepare_operand_for_rename (def_p, &uid))
! {
! set_def_block (*def_p, bb);
! SET_BIT (kills, uid);
}
}
}
*************** rewrite_initialize_block (struct dom_wal
*** 863,885 ****
}
}
- /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
- the block with its immediate reaching definitions. Update the current
- definition of a variable when a new real or virtual definition is found.
*/
-
- static void
- rewrite_walk_stmts (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
- basic_block bb)
- {
- block_stmt_iterator si;
- struct rewrite_block_data *bd
- = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->
block_data_stack);
-
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
- rewrite_stmt (si, &bd->block_defs);
- }
-
-
/* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
PHI nodes. For every PHI node found, add a new argument containing the
current reaching definition for the variable and the edge through which
--- 878,883 ----
*************** insert_phi_nodes_for (tree var, bitmap *
*** 3351,3365 ****
phi_insertion_points = NULL;
}
! /* Rewrite statement pointed by iterator SI into SSA form.
!
! BLOCK_DEFS_P points to a stack with all the definitions found in the
! block. This is used by the dominator tree walker callbacks to restore
! the current reaching definition for every variable defined in BB after
! visiting the immediate dominators of BB. */
static void
! rewrite_stmt (block_stmt_iterator si, varray_type *block_defs_p)
{
size_t i;
stmt_ann_t ann;
--- 3349,3362 ----
phi_insertion_points = NULL;
}
! /* SSA Rewriting Step 2. Rewrite every variable used in each statement in
! the block with its immediate reaching definitions. Update the current
! definition of a variable when a new real or virtual definition is found.
*/
static void
! rewrite_stmt (struct dom_walk_data *walk_data,
! basic_block bb ATTRIBUTE_UNUSED,
! block_stmt_iterator si)
{
size_t i;
stmt_ann_t ann;
*************** rewrite_stmt (block_stmt_iterator si, va
*** 3368,3373 ****
--- 3365,3373 ----
vdef_optype vdefs;
def_optype defs;
use_optype uses;
+ struct rewrite_block_data *bd;
+
+ bd = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
stmt = bsi_stmt (si);
ann = stmt_ann (stmt);
*************** rewrite_stmt (block_stmt_iterator si, va
*** 3411,3417 ****
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
register_new_def (SSA_NAME_VAR (*def_p), *def_p,
! block_defs_p, currdefs);
}
/* Register new virtual definitions made by the statement. */
--- 3411,3417 ----
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
register_new_def (SSA_NAME_VAR (*def_p), *def_p,
! &bd->block_defs, currdefs);
}
/* Register new virtual definitions made by the statement. */
*************** rewrite_stmt (block_stmt_iterator si, va
*** 3420,3431 ****
rewrite_operand (VDEF_OP_PTR (vdefs, i));
if (TREE_CODE (VDEF_RESULT (vdefs, i)) != SSA_NAME)
! *VDEF_RESULT_PTR (vdefs, i) = make_ssa_name (VDEF_RESULT (vdefs, i), stmt);
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
register_new_def (SSA_NAME_VAR (VDEF_RESULT (vdefs, i)),
! VDEF_RESULT (vdefs, i), block_defs_p, currdefs);
}
}
--- 3420,3432 ----
rewrite_operand (VDEF_OP_PTR (vdefs, i));
if (TREE_CODE (VDEF_RESULT (vdefs, i)) != SSA_NAME)
! *VDEF_RESULT_PTR (vdefs, i)
! = make_ssa_name (VDEF_RESULT (vdefs, i), stmt);
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
register_new_def (SSA_NAME_VAR (VDEF_RESULT (vdefs, i)),
! VDEF_RESULT (vdefs, i), &bd->block_defs, currdefs);
}
}