/* Rewrite a program in Normal form into SSA.
- Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
#include "tm.h"
#include "tree.h"
#include "flags.h"
-#include "rtl.h"
#include "tm_p.h"
#include "langhooks.h"
-#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "bitmap.h"
#include "tree-flow.h"
#include "gimple.h"
#include "tree-inline.h"
-#include "varray.h"
#include "timevar.h"
#include "hashtab.h"
#include "tree-dump.h"
#include "tree-pass.h"
#include "cfgloop.h"
#include "domwalk.h"
-#include "ggc.h"
#include "params.h"
#include "vecprim.h"
set_register_defs (stmt, false);
set_rewrite_uses (stmt, false);
+ if (is_gimple_debug (stmt))
+ return;
+
/* If a variable is used before being set, then the variable is live
across a block boundary, so mark it live-on-entry to BB. */
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
set_livein_block (sym, bb);
set_rewrite_uses (stmt, true);
}
-
+
/* Now process the defs. Mark BB as the definition block and add
each def to the set of killed symbols. */
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
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
VEC_replace (gimple_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
renamer will use the symbol on the LHS to get its
reaching definition. */
FOR_EACH_EDGE (e, ei, bb->preds)
- add_phi_arg (phi, var, e);
+ add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
}
else
{
+ tree tracked_var;
+
gcc_assert (DECL_P (var));
phi = create_phi_node (var, bb);
+
+ tracked_var = target_for_debug_bind (var);
+ if (tracked_var)
+ {
+ gimple note = gimple_build_debug_bind (tracked_var,
+ PHI_RESULT (phi),
+ phi);
+ gimple_stmt_iterator si = gsi_after_labels (bb);
+ gsi_insert_before (&si, note, GSI_SAME_STMT);
+ }
}
/* Mark this PHI node as interesting for update_ssa. */
insert_phi_nodes (bitmap *dfs)
{
referenced_var_iterator rvi;
+ bitmap_iterator bi;
tree var;
+ bitmap vars;
+ unsigned uid;
timevar_push (TV_TREE_INSERT_PHI_NODES);
-
+
+ /* Do two stages to avoid code generation differences for UID
+ differences but no UID ordering differences. */
+
+ vars = BITMAP_ALLOC (NULL);
FOR_EACH_REFERENCED_VAR (var, rvi)
{
struct def_blocks_d *def_map;
- bitmap idf;
def_map = find_def_blocks_for (var);
if (def_map == NULL)
continue;
if (get_phi_state (var) != NEED_PHI_STATE_NO)
- {
- idf = compute_idf (def_map->def_blocks, dfs);
- insert_phi_nodes_for (var, idf, false);
- BITMAP_FREE (idf);
- }
+ bitmap_set_bit (vars, DECL_UID (var));
}
+ EXECUTE_IF_SET_IN_BITMAP (vars, 0, uid, bi)
+ {
+ tree var = referenced_var (uid);
+ struct def_blocks_d *def_map;
+ bitmap idf;
+
+ def_map = find_def_blocks_for (var);
+ idf = compute_idf (def_map->def_blocks, dfs);
+ insert_phi_nodes_for (var, idf, false);
+ BITMAP_FREE (idf);
+ }
+
+ BITMAP_FREE (vars);
+
timevar_pop (TV_TREE_INSERT_PHI_NODES);
}
register_new_def (tree def, tree sym)
{
tree currdef;
-
+
/* If this variable is set in a single basic block and all uses are
dominated by the set(s) in that single basic block, then there is
no reason to record anything for this variable in the block local
2- Every statement in BB is rewritten. USE and VUSE operands are
rewritten with their corresponding reaching definition. DEF and
VDEF targets are registered as new definitions.
-
+
3- All the PHI nodes in successor blocks of BB are visited. The
argument corresponding to BB is replaced with its current reaching
definition.
get_reaching_def (tree var)
{
tree currdef;
-
+
/* Lookup the current reaching definition for VAR. */
currdef = get_current_def (var);
definition of a variable when a new real or virtual definition is found. */
static void
-rewrite_stmt (gimple stmt)
+rewrite_stmt (gimple_stmt_iterator si)
{
use_operand_p use_p;
def_operand_p def_p;
ssa_op_iter iter;
+ gimple stmt = gsi_stmt (si);
/* If mark_def_sites decided that we don't need to rewrite this
statement, ignore it. */
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
{
tree var = DEF_FROM_PTR (def_p);
+ tree name = make_ssa_name (var, stmt);
+ tree tracked_var;
gcc_assert (DECL_P (var));
- SET_DEF (def_p, make_ssa_name (var, stmt));
+ SET_DEF (def_p, name);
register_new_def (DEF_FROM_PTR (def_p), var);
+
+ tracked_var = target_for_debug_bind (var);
+ if (tracked_var)
+ {
+ gimple note = gimple_build_debug_bind (tracked_var, name, stmt);
+ gsi_insert_after (&si, note, GSI_SAME_STMT);
+ }
}
}
gsi_next (&gsi))
{
tree currdef;
+ gimple stmt;
+
phi = gsi_stmt (gsi);
currdef = get_reaching_def (SSA_NAME_VAR (gimple_phi_result (phi)));
- add_phi_arg (phi, currdef, e);
+ stmt = SSA_NAME_DEF_STMT (currdef);
+ add_phi_arg (phi, currdef, e, gimple_location (stmt));
}
}
}
of a variable when a new real or virtual definition is found. */
if (TEST_BIT (interesting_blocks, bb->index))
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- rewrite_stmt (gsi_stmt (gsi));
+ rewrite_stmt (gsi);
/* 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
saved_def = NULL;
var = tmp;
}
-
+
set_current_def (var, saved_def);
}
}
EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
{
- print_generic_expr (file, referenced_var (i), 0);
+ struct tree_decl_minimal in;
+ tree var;
+ in.uid = i;
+ var = (tree) htab_find_with_hash (gimple_referenced_vars (cfun),
+ &in, i);
+ if (var)
+ print_generic_expr (file, var, 0);
+ else
+ fprintf (file, "D.%u", i);
fprintf (file, " ");
}
for (j = (int) VEC_length (tree, block_defs_stack) - 1; j >= 0; j--)
{
tree name, var;
-
+
name = VEC_index (tree, block_defs_stack, j);
if (name == NULL_TREE)
{
{
FILE *file = (FILE *) data;
struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
-
+
fprintf (file, "VAR: ");
print_generic_expr (file, db_p->var, dump_flags);
bitmap_print (file, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
}
+/* Same as maybe_replace_use, but without introducing default stmts,
+ returning false to indicate a need to do so. */
+
+static inline bool
+maybe_replace_use_in_debug_stmt (use_operand_p use_p)
+{
+ tree rdef = NULL_TREE;
+ tree use = USE_FROM_PTR (use_p);
+ tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
+
+ if (symbol_marked_for_renaming (sym))
+ rdef = get_current_def (sym);
+ else if (is_old_name (use))
+ {
+ rdef = get_current_def (use);
+ /* We can't assume that, if there's no current definition, the
+ default one should be used. It could be the case that we've
+ rearranged blocks so that the earlier definition no longer
+ dominates the use. */
+ if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
+ rdef = use;
+ }
+ else
+ rdef = use;
+
+ if (rdef && rdef != use)
+ SET_USE (use_p, rdef);
+
+ return rdef != NULL_TREE;
+}
+
+
/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
register it as the current definition for the names replaced by
DEF_P. */
static inline void
-maybe_register_def (def_operand_p def_p, gimple stmt)
+maybe_register_def (def_operand_p def_p, gimple stmt,
+ gimple_stmt_iterator gsi)
{
tree def = DEF_FROM_PTR (def_p);
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
{
if (DECL_P (def))
{
+ tree tracked_var;
+
def = make_ssa_name (def, stmt);
SET_DEF (def_p, def);
+
+ tracked_var = target_for_debug_bind (sym);
+ if (tracked_var)
+ {
+ gimple note = gimple_build_debug_bind (tracked_var, def, stmt);
+ /* If stmt ends the bb, insert the debug stmt on the single
+ non-EH edge from the stmt. */
+ if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt))
+ {
+ basic_block bb = gsi_bb (gsi);
+ edge_iterator ei;
+ edge e, ef = NULL;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!(e->flags & EDGE_EH))
+ {
+ gcc_assert (!ef);
+ ef = e;
+ }
+ gcc_assert (ef
+ && single_pred_p (ef->dest)
+ && !phi_nodes (ef->dest)
+ && ef->dest != EXIT_BLOCK_PTR);
+ gsi_insert_on_edge_immediate (ef, note);
+ }
+ else
+ gsi_insert_after (&gsi, note, GSI_SAME_STMT);
+ }
}
register_new_update_single (def, sym);
in OLD_SSA_NAMES. */
static void
-rewrite_update_stmt (gimple stmt)
+rewrite_update_stmt (gimple stmt, gimple_stmt_iterator gsi)
{
use_operand_p use_p;
def_operand_p def_p;
/* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
symbol is marked for renaming. */
if (rewrite_uses_p (stmt))
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
- maybe_replace_use (use_p);
+ {
+ if (is_gimple_debug (stmt))
+ {
+ bool failed = false;
+
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+ if (!maybe_replace_use_in_debug_stmt (use_p))
+ {
+ failed = true;
+ break;
+ }
+
+ if (failed)
+ {
+ /* DOM sometimes threads jumps in such a way that a
+ debug stmt ends up referencing a SSA variable that no
+ longer dominates the debug stmt, but such that all
+ incoming definitions refer to the same definition in
+ an earlier dominator. We could try to recover that
+ definition somehow, but this will have to do for now.
+
+ Introducing a default definition, which is what
+ maybe_replace_use() would do in such cases, may
+ modify code generation, for the otherwise-unused
+ default definition would never go away, modifying SSA
+ version numbers all over. */
+ gimple_debug_bind_reset_value (stmt);
+ update_stmt (stmt);
+ }
+ }
+ else
+ {
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+ maybe_replace_use (use_p);
+ }
+ }
/* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
Also register definitions for names whose underlying symbol is
marked for renaming. */
if (register_defs_p (stmt))
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
- maybe_register_def (def_p, stmt);
+ maybe_register_def (def_p, stmt, gsi);
}
if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
continue;
-
+
phis = VEC_index (gimple_vec, phis_to_rewrite, e->dest->index);
for (i = 0; VEC_iterate (gimple, phis, i, phi); i++)
{
- tree arg, lhs_sym;
+ tree arg, lhs_sym, reaching_def = NULL;
use_operand_p arg_p;
gcc_assert (rewrite_uses_p (phi));
/* When updating a PHI node for a recently introduced
symbol we may find NULL arguments. That's why we
take the symbol from the LHS of the PHI node. */
- SET_USE (arg_p, get_reaching_def (lhs_sym));
+ reaching_def = get_reaching_def (lhs_sym);
+
}
else
{
tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
if (symbol_marked_for_renaming (sym))
- SET_USE (arg_p, get_reaching_def (sym));
+ reaching_def = get_reaching_def (sym);
else if (is_old_name (arg))
- SET_USE (arg_p, get_reaching_def (arg));
+ reaching_def = get_reaching_def (arg);
+ }
+
+ /* Update the argument if there is a reaching def. */
+ if (reaching_def)
+ {
+ gimple stmt;
+ source_location locus;
+ int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
+
+ SET_USE (arg_p, reaching_def);
+ stmt = SSA_NAME_DEF_STMT (reaching_def);
+
+ /* Single element PHI nodes behave like copies, so get the
+ location from the phi argument. */
+ if (gimple_code (stmt) == GIMPLE_PHI &&
+ gimple_phi_num_args (stmt) == 1)
+ locus = gimple_phi_arg_location (stmt, 0);
+ else
+ locus = gimple_location (stmt);
+
+ gimple_phi_arg_set_location (phi, arg_i, locus);
}
+
if (e->flags & EDGE_ABNORMAL)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
}
if (!register_defs_p (phi))
continue;
-
+
lhs = gimple_phi_result (phi);
lhs_sym = SSA_NAME_VAR (lhs);
the names replaced by LHS. */
if (is_new_name (lhs))
register_new_update_set (lhs, names_replaced_by (lhs));
-
+
/* If LHS is an OLD name, register it as a new definition
for itself. */
if (is_old_name (lhs))
/* Step 2. Rewrite every variable used in each statement in the block. */
if (TEST_BIT (interesting_blocks, bb->index))
- {
- gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
+ {
+ gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- rewrite_update_stmt (gsi_stmt (gsi));
- }
+ rewrite_update_stmt (gsi_stmt (gsi), gsi);
+ }
/* Step 3. Update PHI nodes. */
rewrite_update_phi_arguments (bb);
{
tree var = VEC_pop (tree, block_defs_stack);
tree saved_def;
-
+
/* NULL indicates the unwind stop point for this block (see
rewrite_update_enter_block). */
if (var == NULL)
/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
- form.
+ form.
ENTRY indicates the block where to start. Every block dominated by
ENTRY will be rewritten.
rewrite_blocks (basic_block entry, enum rewrite_mode what)
{
struct dom_walk_data walk_data;
-
+
/* Rewrite all the basic blocks in the program. */
timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
if (def_blocks)
dump_tree_ssa_stats (dump_file);
}
-
+
VEC_free (tree, heap, block_defs_stack);
timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
{
bitmap *dfs;
basic_block bb;
-
+
timevar_push (TV_TREE_SSA_OTHER);
/* Initialize operand data structures. */
BITMAP_FREE (dfs[bb->index]);
free (dfs);
+ sbitmap_free (interesting_blocks);
+
fini_ssa_renamer ();
timevar_pop (TV_TREE_SSA_OTHER);
}
-struct gimple_opt_pass pass_build_ssa =
+struct gimple_opt_pass pass_build_ssa =
{
{
GIMPLE_PASS,
if (gimple_code (stmt) == GIMPLE_PHI)
mark_phi_for_rewrite (def_bb, stmt);
else
- set_rewrite_uses (stmt, true);
+ {
+ set_rewrite_uses (stmt, true);
+
+ if (is_gimple_debug (stmt))
+ return;
+ }
/* 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
ssa_op_iter i;
use_operand_p use_p;
def_operand_p def_p;
-
+
stmt = gsi_stmt (si);
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
unsigned i = 0;
bitmap ret;
sbitmap_iterator sbi;
-
+
gcc_assert (update_ssa_initialized_fn == NULL
|| update_ssa_initialized_fn == cfun);
This is slightly different than the regular PHI insertion
algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
real names (i.e., GIMPLE registers) are inserted:
-
+
- If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
nodes inside the region affected by the block that defines VAR
and the blocks that define all its replacements. All these
OSDN Git Service
