#include "domwalk.h"
#include "ggc.h"
#include "params.h"
+#include "vecprim.h"
/* This file builds the SSA form for a function as described in:
R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
associated with the current block. */
static VEC(tree,heap) *block_defs_stack;
-/* Basic block vectors used in this file ought to be allocated in the
- heap. We use pointer vector, because ints can be easily passed by
- value. */
-DEF_VEC_I(int);
-DEF_VEC_ALLOC_I(int,heap);
-
/* Set of existing SSA names being replaced by update_ssa. */
static sbitmap old_ssa_names;
released after we finish updating the SSA web. */
static bitmap names_to_release;
+/* For each block, the phi nodes that need to be rewritten are stored into
+ these vectors. */
+
+typedef VEC(tree, heap) *tree_vec;
+DEF_VEC_P (tree_vec);
+DEF_VEC_ALLOC_P (tree_vec, heap);
+
+static VEC(tree_vec, heap) *phis_to_rewrite;
+
+/* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
+
+static bitmap blocks_with_phis_to_rewrite;
+
/* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
to grow as the callers to register_new_name_mapping will typically
create new names on the fly. FIXME. Currently set to 1/3 to avoid
/* Information stored for SSA names. */
struct ssa_name_info
{
+ /* The actual definition of the ssa name. */
+ tree current_def;
+
/* This field indicates whether or not the variable may need PHI nodes.
See the enum's definition for more detailed information about the
states. */
ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
- /* The actual definition of the ssa name. */
- tree current_def;
+ /* Age of this record (so that info_for_ssa_name table can be cleared
+ quicky); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
+ are assumed to be null. */
+ unsigned age;
};
+/* The information associated with names. */
+typedef struct ssa_name_info *ssa_name_info_p;
+DEF_VEC_P (ssa_name_info_p);
+DEF_VEC_ALLOC_P (ssa_name_info_p, heap);
+
+static VEC(ssa_name_info_p, heap) *info_for_ssa_name;
+static unsigned current_info_for_ssa_name_age;
+
+/* The set of blocks affected by update_ssa. */
+
+static bitmap blocks_to_update;
/* The main entry point to the SSA renamer (rewrite_blocks) may be
called several times to do different, but related, tasks.
static inline struct ssa_name_info *
get_ssa_name_ann (tree name)
{
- if (!SSA_NAME_AUX (name))
- SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
+ unsigned ver = SSA_NAME_VERSION (name);
+ unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name);
+ struct ssa_name_info *info;
+
+ if (ver >= len)
+ {
+ unsigned new_len = num_ssa_names;
+
+ VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len);
+ while (len++ < new_len)
+ {
+ struct ssa_name_info *info = XCNEW (struct ssa_name_info);
+ info->age = current_info_for_ssa_name_age;
+ VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info);
+ }
+ }
+
+ info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver);
+ if (info->age < current_info_for_ssa_name_age)
+ {
+ info->need_phi_state = 0;
+ info->current_def = NULL_TREE;
+ info->age = current_info_for_ssa_name_age;
+ }
- return (struct ssa_name_info *) SSA_NAME_AUX (name);
+ return info;
}
+/* Clears info for ssa names. */
+
+static void
+clear_ssa_name_info (void)
+{
+ current_info_for_ssa_name_age++;
+}
/* Gets phi_state field for VAR. */
}
+/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
+ all statements in basic block BB. */
+
+static void
+initialize_flags_in_bb (basic_block bb)
+{
+ tree phi, stmt;
+ block_stmt_iterator bsi;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ REWRITE_THIS_STMT (phi) = 0;
+ REGISTER_DEFS_IN_THIS_STMT (phi) = 0;
+ }
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ /* We are going to use the operand cache API, such as
+ SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
+ cache for each statement should be up-to-date. */
+ gcc_assert (!stmt_modified_p (stmt));
+ REWRITE_THIS_STMT (stmt) = 0;
+ REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
+ }
+}
+
+/* Mark block BB as interesting for update_ssa. */
+
+static void
+mark_block_for_update (basic_block bb)
+{
+ gcc_assert (blocks_to_update != NULL);
+ if (bitmap_bit_p (blocks_to_update, bb->index))
+ return;
+ bitmap_set_bit (blocks_to_update, bb->index);
+ initialize_flags_in_bb (bb);
+}
+
/* Return the set of blocks where variable VAR is defined and the blocks
where VAR is live on entry (livein). If no entry is found in
DEF_BLOCKS, a new one is created and returned. */
stmt = bsi_stmt (bsi);
update_stmt_if_modified (stmt);
+ gcc_assert (blocks_to_update == NULL);
REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
REWRITE_THIS_STMT (stmt) = 0;
SET_BIT (gd->interesting_blocks, bb->index);
}
+/* Structure used by prune_unused_phi_nodes to record bounds of the intervals
+ in the dfs numbering of the dominance tree. */
+
+struct dom_dfsnum
+{
+ /* Basic block whose index this entry corresponds to. */
+ unsigned bb_index;
+
+ /* The dfs number of this node. */
+ unsigned dfs_num;
+};
+
+/* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
+ for qsort. */
+
+static int
+cmp_dfsnum (const void *a, const void *b)
+{
+ const struct dom_dfsnum *da = a;
+ const struct dom_dfsnum *db = b;
+
+ return (int) da->dfs_num - (int) db->dfs_num;
+}
+
+/* Among the intervals starting at the N points specified in DEFS, find
+ the one that contains S, and return its bb_index. */
+
+static unsigned
+find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
+{
+ unsigned f = 0, t = n, m;
+
+ while (t > f + 1)
+ {
+ m = (f + t) / 2;
+ if (defs[m].dfs_num <= s)
+ f = m;
+ else
+ t = m;
+ }
+
+ return defs[f].bb_index;
+}
+
+/* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
+ KILLS is a bitmap of blocks where the value is defined before any use. */
+
+static void
+prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
+{
+ VEC(int, heap) *worklist;
+ bitmap_iterator bi;
+ unsigned i, b, p, u, top;
+ bitmap live_phis;
+ basic_block def_bb, use_bb;
+ edge e;
+ edge_iterator ei;
+ bitmap to_remove;
+ struct dom_dfsnum *defs;
+ unsigned n_defs, adef;
+
+ if (bitmap_empty_p (uses))
+ {
+ bitmap_clear (phis);
+ return;
+ }
+
+ /* The phi must dominate a use, or an argument of a live phi. Also, we
+ do not create any phi nodes in def blocks, unless they are also livein. */
+ to_remove = BITMAP_ALLOC (NULL);
+ bitmap_and_compl (to_remove, kills, uses);
+ bitmap_and_compl_into (phis, to_remove);
+ if (bitmap_empty_p (phis))
+ {
+ BITMAP_FREE (to_remove);
+ return;
+ }
+
+ /* We want to remove the unnecessary phi nodes, but we do not want to compute
+ liveness information, as that may be linear in the size of CFG, and if
+ there are lot of different variables to rewrite, this may lead to quadratic
+ behavior.
+
+ Instead, we basically emulate standard dce. We put all uses to worklist,
+ then for each of them find the nearest def that dominates them. If this
+ def is a phi node, we mark it live, and if it was not live before, we
+ add the predecessors of its basic block to the worklist.
+
+ To quickly locate the nearest def that dominates use, we use dfs numbering
+ of the dominance tree (that is already available in order to speed up
+ queries). For each def, we have the interval given by the dfs number on
+ entry to and on exit from the corresponding subtree in the dominance tree.
+ The nearest dominator for a given use is the smallest of these intervals
+ that contains entry and exit dfs numbers for the basic block with the use.
+ If we store the bounds for all the uses to an array and sort it, we can
+ locate the nearest dominating def in logarithmic time by binary search.*/
+ bitmap_ior (to_remove, kills, phis);
+ n_defs = bitmap_count_bits (to_remove);
+ defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
+ defs[0].bb_index = 1;
+ defs[0].dfs_num = 0;
+ adef = 1;
+ EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
+ {
+ def_bb = BASIC_BLOCK (i);
+ defs[adef].bb_index = i;
+ defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
+ defs[adef + 1].bb_index = i;
+ defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
+ adef += 2;
+ }
+ BITMAP_FREE (to_remove);
+ gcc_assert (adef == 2 * n_defs + 1);
+ qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
+ gcc_assert (defs[0].bb_index == 1);
+
+ /* Now each DEFS entry contains the number of the basic block to that the
+ dfs number corresponds. Change them to the number of basic block that
+ corresponds to the interval following the dfs number. Also, for the
+ dfs_out numbers, increase the dfs number by one (so that it corresponds
+ to the start of the following interval, not to the end of the current
+ one). We use WORKLIST as a stack. */
+ worklist = VEC_alloc (int, heap, n_defs + 1);
+ VEC_quick_push (int, worklist, 1);
+ top = 1;
+ n_defs = 1;
+ for (i = 1; i < adef; i++)
+ {
+ b = defs[i].bb_index;
+ if (b == top)
+ {
+ /* This is a closing element. Interval corresponding to the top
+ of the stack after removing it follows. */
+ VEC_pop (int, worklist);
+ top = VEC_index (int, worklist, VEC_length (int, worklist) - 1);
+ defs[n_defs].bb_index = top;
+ defs[n_defs].dfs_num = defs[i].dfs_num + 1;
+ }
+ else
+ {
+ /* Opening element. Nothing to do, just push it to the stack and move
+ it to the correct position. */
+ defs[n_defs].bb_index = defs[i].bb_index;
+ defs[n_defs].dfs_num = defs[i].dfs_num;
+ VEC_quick_push (int, worklist, b);
+ top = b;
+ }
+
+ /* If this interval starts at the same point as the previous one, cancel
+ the previous one. */
+ if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
+ defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
+ else
+ n_defs++;
+ }
+ VEC_pop (int, worklist);
+ gcc_assert (VEC_empty (int, worklist));
+
+ /* Now process the uses. */
+ live_phis = BITMAP_ALLOC (NULL);
+ EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
+ {
+ VEC_safe_push (int, heap, worklist, i);
+ }
+
+ while (!VEC_empty (int, worklist))
+ {
+ b = VEC_pop (int, worklist);
+ if (b == ENTRY_BLOCK)
+ continue;
+
+ /* If there is a phi node in USE_BB, it is made live. Otherwise,
+ find the def that dominates the immediate dominator of USE_BB
+ (the kill in USE_BB does not dominate the use). */
+ if (bitmap_bit_p (phis, b))
+ p = b;
+ else
+ {
+ use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b));
+ p = find_dfsnum_interval (defs, n_defs,
+ bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
+ if (!bitmap_bit_p (phis, p))
+ continue;
+ }
+
+ /* If the phi node is already live, there is nothing to do. */
+ if (bitmap_bit_p (live_phis, p))
+ continue;
+
+ /* Mark the phi as live, and add the new uses to the worklist. */
+ bitmap_set_bit (live_phis, p);
+ def_bb = BASIC_BLOCK (p);
+ FOR_EACH_EDGE (e, ei, def_bb->preds)
+ {
+ u = e->src->index;
+ if (bitmap_bit_p (uses, u))
+ continue;
+
+ /* In case there is a kill directly in the use block, do not record
+ the use (this is also necessary for correctness, as we assume that
+ uses dominated by a def directly in their block have been filtered
+ out before). */
+ if (bitmap_bit_p (kills, u))
+ continue;
+
+ bitmap_set_bit (uses, u);
+ VEC_safe_push (int, heap, worklist, u);
+ }
+ }
+
+ VEC_free (int, heap, worklist);
+ bitmap_copy (phis, live_phis);
+ BITMAP_FREE (live_phis);
+ free (defs);
+}
/* Given a set of blocks with variable definitions (DEF_BLOCKS),
return a bitmap with all the blocks in the iterated dominance
}
+/* Marks phi node PHI in basic block BB for rewrite. */
+
+static void
+mark_phi_for_rewrite (basic_block bb, tree phi)
+{
+ tree_vec phis;
+ unsigned i, idx = bb->index;
+
+ if (REWRITE_THIS_STMT (phi))
+ return;
+ REWRITE_THIS_STMT (phi) = 1;
+
+ if (!blocks_with_phis_to_rewrite)
+ return;
+
+ bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
+ VEC_reserve (tree_vec, heap, phis_to_rewrite, last_basic_block + 1);
+ for (i = VEC_length (tree_vec, phis_to_rewrite); i <= idx; i++)
+ VEC_quick_push (tree_vec, phis_to_rewrite, NULL);
+
+ phis = VEC_index (tree_vec, phis_to_rewrite, idx);
+ if (!phis)
+ phis = VEC_alloc (tree, heap, 10);
+
+ VEC_safe_push (tree, heap, phis, phi);
+ VEC_replace (tree_vec, phis_to_rewrite, idx, phis);
+}
+
/* Insert PHI nodes for variable VAR using the iterated dominance
frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
function assumes that the caller is incrementally updating the SSA
/* Remove the blocks where we already have PHI nodes for VAR. */
bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
- /* Now compute global livein for this variable. Note this modifies
- def_map->livein_blocks. */
- compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
+ /* Remove obviously useless phi nodes. */
+ prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
+ def_map->livein_blocks);
/* And insert the PHI nodes. */
- EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
- 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
{
bb = BASIC_BLOCK (bb_index);
+ if (update_p)
+ mark_block_for_update (bb);
if (update_p && TREE_CODE (var) == SSA_NAME)
{
/* Mark this PHI node as interesting for update_ssa. */
REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
- REWRITE_THIS_STMT (phi) = 1;
+ mark_phi_for_rewrite (bb, phi);
}
}
/* If mark_def_sites decided that we don't need to rewrite this
statement, ignore it. */
+ gcc_assert (blocks_to_update == NULL);
if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
return;
/* Mark the unwind point for this block. */
VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
+ if (!bitmap_bit_p (blocks_to_update, bb->index))
+ return;
+
/* Mark the LHS if any of the arguments flows through an abnormal
edge. */
is_abnormal_phi = false;
register it as a new definition for its corresponding name. Also
register definitions for names whose underlying symbols are
marked for renaming. */
+
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree lhs, lhs_sym;
stmt = bsi_stmt (si);
ann = stmt_ann (stmt);
+ gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
+
/* Only update marked statements. */
if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
return;
{
edge e;
edge_iterator ei;
+ unsigned i;
FOR_EACH_EDGE (e, ei, bb->succs)
{
tree phi;
+ tree_vec phis;
- for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
+ if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
+ continue;
+
+ phis = VEC_index (tree_vec, phis_to_rewrite, e->dest->index);
+ for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
{
tree arg;
use_operand_p arg_p;
- /* Skip PHI nodes that are not marked for rewrite. */
- if (!REWRITE_THIS_STMT (phi))
- continue;
+ gcc_assert (REWRITE_THIS_STMT (phi));
arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
arg = USE_FROM_PTR (arg_p);
Steps 3 and 4 are done using the dominator tree walker
(walk_dominator_tree). */
-static void
+static unsigned int
rewrite_into_ssa (void)
{
bitmap *dfs;
timevar_pop (TV_TREE_SSA_OTHER);
in_ssa_p = true;
+ return 0;
}
PROP_ssa, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */
+ TODO_dump_func
+ | TODO_verify_ssa
+ | TODO_remove_unused_locals, /* todo_flags_finish */
0 /* letter */
};
renamer. BLOCKS is the set of blocks that need updating. */
static void
-mark_def_interesting (tree var, tree stmt, basic_block bb, bitmap blocks,
- bool insert_phi_p)
+mark_def_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
{
+ gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
- bitmap_set_bit (blocks, bb->index);
if (insert_phi_p)
{
/* Mark the use of VAR at STMT and BB as interesting for the
renamer. INSERT_PHI_P is true if we are going to insert new PHI
- nodes. BLOCKS is the set of blocks that need updating. */
+ nodes. */
static inline void
-mark_use_interesting (tree var, tree stmt, basic_block bb, bitmap blocks,
- bool insert_phi_p)
+mark_use_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
{
- REWRITE_THIS_STMT (stmt) = 1;
- bitmap_set_bit (blocks, bb->index);
+ basic_block def_bb = bb_for_stmt (stmt);
+
+ mark_block_for_update (def_bb);
+ mark_block_for_update (bb);
+
+ if (TREE_CODE (stmt) == PHI_NODE)
+ mark_phi_for_rewrite (def_bb, stmt);
+ else
+ REWRITE_THIS_STMT (stmt) = 1;
/* If VAR has not been defined in BB, then it is live-on-entry
to BB. Note that we cannot just use the block holding VAR's
/* Do a dominator walk starting at BB processing statements that
reference symbols in SYMS_TO_RENAME. This is very similar to
mark_def_sites, but the scan handles statements whose operands may
- already be SSA names. Blocks that contain defs or uses of symbols
- in SYMS_TO_RENAME are added to BLOCKS.
+ already be SSA names.
If INSERT_PHI_P is true, mark those uses as live in the
corresponding block. This is later used by the PHI placement
algorithm to make PHI pruning decisions. */
static void
-prepare_block_for_update (basic_block bb, bitmap blocks, bool insert_phi_p)
+prepare_block_for_update (basic_block bb, bool insert_phi_p)
{
basic_block son;
block_stmt_iterator si;
tree phi;
+ edge e;
+ edge_iterator ei;
+
+ mark_block_for_update (bb);
/* Process PHI nodes marking interesting those that define or use
the symbols that we are interested in. */
lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
- if (symbol_marked_for_renaming (lhs_sym))
+ if (!symbol_marked_for_renaming (lhs_sym))
+ continue;
+ mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
+
+ /* Mark the uses in phi nodes as interesting. It would be more correct
+ to process the arguments of the phi nodes of the successor edges of
+ BB at the end of prepare_block_for_update, however, that turns out
+ to be significantly more expensive. Doing it here is conservatively
+ correct -- it may only cause us to believe a value to be live in a
+ block that also contains its definition, and thus insert a few more
+ phi nodes for it. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
{
- mark_use_interesting (lhs_sym, phi, bb, blocks, insert_phi_p);
- mark_def_interesting (lhs_sym, phi, bb, blocks, insert_phi_p);
+ mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
}
}
tree use = USE_FROM_PTR (use_p);
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
if (symbol_marked_for_renaming (sym))
- mark_use_interesting (use, stmt, bb, blocks, insert_phi_p);
+ mark_use_interesting (use, stmt, bb, insert_phi_p);
}
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
if (symbol_marked_for_renaming (sym))
- mark_def_interesting (def, stmt, bb, blocks, insert_phi_p);
+ mark_def_interesting (def, stmt, bb, insert_phi_p);
}
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_VIRTUAL_DEFS)
if (symbol_marked_for_renaming (sym))
{
- mark_use_interesting (sym, stmt, bb, blocks, insert_phi_p);
- mark_def_interesting (sym, stmt, bb, blocks, insert_phi_p);
+ mark_use_interesting (sym, stmt, bb, insert_phi_p);
+ mark_def_interesting (sym, stmt, bb, insert_phi_p);
}
}
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
if (symbol_marked_for_renaming (sym))
- mark_use_interesting (sym, stmt, bb, blocks, insert_phi_p);
+ mark_use_interesting (sym, stmt, bb, insert_phi_p);
}
}
for (son = first_dom_son (CDI_DOMINATORS, bb);
son;
son = next_dom_son (CDI_DOMINATORS, son))
- prepare_block_for_update (son, blocks, insert_phi_p);
+ prepare_block_for_update (son, insert_phi_p);
}
prepare_names_to_update. */
static void
-prepare_use_sites_for (tree name, bitmap blocks, bool insert_phi_p)
+prepare_use_sites_for (tree name, bool insert_phi_p)
{
use_operand_p use_p;
imm_use_iterator iter;
if (TREE_CODE (stmt) == PHI_NODE)
{
- /* Mark this use of NAME interesting for the renamer.
- Notice that we explicitly call mark_use_interesting with
- INSERT_PHI_P == false.
-
- This is to avoid marking NAME as live-in in this block
- BB. If we were to mark NAME live-in to BB, then NAME
- would be considered live-in through ALL incoming edges to
- BB which is not what we want. Since we are updating the
- SSA form for NAME, we don't really know what other names
- of NAME are coming in through other edges into BB.
-
- If we considered NAME live-in at BB, then the PHI
- placement algorithm may try to insert PHI nodes in blocks
- that are not only unnecessary but also the renamer would
- not know how to fill in. */
- mark_use_interesting (name, stmt, bb, blocks, false);
-
- /* As discussed above, we only want to mark NAME live-in
- through the edge corresponding to its slot inside the PHI
- argument list. So, we look for the block BB1 where NAME
- is flowing through. If BB1 does not contain a definition
- of NAME, then consider NAME live-in at BB1. */
- if (insert_phi_p)
- {
- int ix = PHI_ARG_INDEX_FROM_USE (use_p);
- edge e = PHI_ARG_EDGE (stmt, ix);
- basic_block bb1 = e->src;
- struct def_blocks_d *db = get_def_blocks_for (name);
-
- if (!bitmap_bit_p (db->def_blocks, bb1->index))
- set_livein_block (name, bb1);
- }
+ int ix = PHI_ARG_INDEX_FROM_USE (use_p);
+ edge e = PHI_ARG_EDGE (stmt, ix);
+ mark_use_interesting (name, stmt, e->src, insert_phi_p);
}
else
{
/* For regular statements, mark this as an interesting use
for NAME. */
- mark_use_interesting (name, stmt, bb, blocks, insert_phi_p);
+ mark_use_interesting (name, stmt, bb, insert_phi_p);
}
}
}
prepare_names_to_update. */
static void
-prepare_def_site_for (tree name, bitmap blocks, bool insert_phi_p)
+prepare_def_site_for (tree name, bool insert_phi_p)
{
tree stmt;
basic_block bb;
if (bb)
{
gcc_assert (bb->index < last_basic_block);
- mark_def_interesting (name, stmt, bb, blocks, insert_phi_p);
+ mark_block_for_update (bb);
+ mark_def_interesting (name, stmt, bb, insert_phi_p);
}
}
/* Mark definition and use sites of names in NEW_SSA_NAMES and
- OLD_SSA_NAMES. Add each definition block to BLOCKS. INSERT_PHI_P
- is true if the caller wants to insert PHI nodes for newly created
- names. */
+ OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
+ PHI nodes for newly created names. */
static void
-prepare_names_to_update (bitmap blocks, bool insert_phi_p)
+prepare_names_to_update (bool insert_phi_p)
{
unsigned i = 0;
bitmap_iterator bi;
names may be considered to be live-in on blocks that contain
definitions for their replacements. */
EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
- prepare_def_site_for (ssa_name (i), blocks, insert_phi_p);
+ prepare_def_site_for (ssa_name (i), insert_phi_p);
/* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
OLD_SSA_NAMES, but we have to ignore its definition site. */
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
{
if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
- prepare_def_site_for (ssa_name (i), blocks, insert_phi_p);
- prepare_use_sites_for (ssa_name (i), blocks, insert_phi_p);
+ prepare_def_site_for (ssa_name (i), insert_phi_p);
+ prepare_use_sites_for (ssa_name (i), insert_phi_p);
}
}
BITMAP_FREE (names_to_release);
}
- for (i = 1; i < num_ssa_names; i++)
- {
- tree n = ssa_name (i);
-
- if (n)
- {
- free (SSA_NAME_AUX (n));
- SSA_NAME_AUX (n) = NULL;
- }
- }
+ clear_ssa_name_info ();
}
void
update_ssa (unsigned update_flags)
{
- bitmap blocks;
basic_block bb, start_bb;
bitmap_iterator bi;
unsigned i = 0;
timevar_push (TV_TREE_SSA_INCREMENTAL);
+ blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
+ if (!phis_to_rewrite)
+ phis_to_rewrite = VEC_alloc (tree_vec, heap, last_basic_block);
+ blocks_to_update = BITMAP_ALLOC (NULL);
+
/* Ensure that the dominance information is up-to-date. */
calculate_dominance_info (CDI_DOMINATORS);
def_blocks = NULL;
}
- blocks = BITMAP_ALLOC (NULL);
-
- /* Clear the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags
- for every statement and PHI node. */
- FOR_EACH_BB (bb)
- {
- block_stmt_iterator si;
- tree phi;
-
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- {
- REWRITE_THIS_STMT (phi) = 0;
- REGISTER_DEFS_IN_THIS_STMT (phi) = 0;
- }
-
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
- {
- tree stmt = bsi_stmt (si);
- /* We are going to use the operand cache API, such as
- SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
- cache for each statement should be up-to-date. */
- gcc_assert (!stmt_modified_p (stmt));
- REWRITE_THIS_STMT (stmt) = 0;
- REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
- }
- }
-
/* Heuristic to avoid massive slow downs when the replacement
mappings include lots of virtual names. */
if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
OLD_SSA_NAMES. */
if (sbitmap_first_set_bit (new_ssa_names) >= 0)
{
- prepare_names_to_update (blocks, insert_phi_p);
+ prepare_names_to_update (insert_phi_p);
/* If all the names in NEW_SSA_NAMES had been marked for
removal, and there are no symbols to rename, then there's
in SYMS_TO_RENAME. Mark interesting blocks and statements
and set local live-in information for the PHI placement
heuristics. */
- prepare_block_for_update (start_bb, blocks, insert_phi_p);
+ prepare_block_for_update (start_bb, insert_phi_p);
}
else
{
/* Otherwise, the entry block to the region is the nearest
common dominator for the blocks in BLOCKS. */
- start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, blocks);
+ start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
+ blocks_to_update);
}
/* If requested, insert PHI nodes at the iterated dominance frontier
sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
sbitmap_copy (tmp, old_ssa_names);
EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
- insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks,
+ insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
update_flags);
sbitmap_free (tmp);
}
EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
- insert_updated_phi_nodes_for (referenced_var (i), dfs, blocks,
- update_flags);
+ insert_updated_phi_nodes_for (referenced_var (i), dfs,
+ blocks_to_update, update_flags);
FOR_EACH_BB (bb)
BITMAP_FREE (dfs[bb->index]);
We need to re-compute START_BB to include the newly added
blocks. */
if (start_bb != ENTRY_BLOCK_PTR)
- start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS, blocks);
+ start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
+ blocks_to_update);
}
/* Reset the current definition for name and symbol before renaming
/* Now start the renaming process at START_BB. */
tmp = sbitmap_alloc (last_basic_block);
sbitmap_zero (tmp);
- EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
+ EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
SET_BIT (tmp, i);
rewrite_blocks (start_bb, REWRITE_UPDATE, tmp);
start_bb->index);
c = 0;
- EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
+ EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
c++;
fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
if (dump_flags & TDF_DETAILS)
{
fprintf (dump_file, "Affected blocks: ");
- EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
+ EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
fprintf (dump_file, "%u ", i);
fprintf (dump_file, "\n");
}
/* Free allocated memory. */
done:
- BITMAP_FREE (blocks);
+ EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
+ {
+ tree_vec phis = VEC_index (tree_vec, phis_to_rewrite, i);
+
+ VEC_free (tree, heap, phis);
+ VEC_replace (tree_vec, phis_to_rewrite, i, NULL);
+ }
+ BITMAP_FREE (blocks_with_phis_to_rewrite);
+ BITMAP_FREE (blocks_to_update);
delete_update_ssa ();
timevar_pop (TV_TREE_SSA_INCREMENTAL);
OSDN Git Service
