/* Rewrite a program in Normal form into SSA.
- Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
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"
mark_block_for_update (basic_block bb)
{
gcc_assert (blocks_to_update != NULL);
- if (bitmap_bit_p (blocks_to_update, bb->index))
+ if (!bitmap_set_bit (blocks_to_update, bb->index))
return;
- bitmap_set_bit (blocks_to_update, bb->index);
initialize_flags_in_bb (bb);
}
/* Return true if symbol SYM is marked for renaming. */
-static inline bool
+bool
symbol_marked_for_renaming (tree sym)
{
return bitmap_bit_p (SYMS_TO_RENAME (cfun), DECL_UID (sym));
set_rewrite_uses (stmt, false);
if (is_gimple_debug (stmt))
- return;
+ {
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+ {
+ tree sym = USE_FROM_PTR (use_p);
+ gcc_assert (DECL_P (sym));
+ set_rewrite_uses (stmt, true);
+ }
+ if (rewrite_uses_p (stmt))
+ SET_BIT (interesting_blocks, bb->index);
+ 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. */
}
/* If the phi node is already live, there is nothing to do. */
- if (bitmap_bit_p (live_phis, p))
+ if (!bitmap_set_bit (live_phis, p))
continue;
- /* Mark the phi as live, and add the new uses to the worklist. */
- bitmap_set_bit (live_phis, p);
+ /* Add the new uses to the worklist. */
def_bb = BASIC_BLOCK (p);
FOR_EACH_EDGE (e, ei, def_bb->preds)
{
the flowgraph. */
static void
-insert_phi_nodes (bitmap *dfs)
+insert_phi_nodes (bitmap_head *dfs)
{
referenced_var_iterator rvi;
bitmap_iterator bi;
differences but no UID ordering differences. */
vars = BITMAP_ALLOC (NULL);
- FOR_EACH_REFERENCED_VAR (var, rvi)
+ FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
{
struct def_blocks_d *def_map;
}
+/* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
+
+static void
+rewrite_debug_stmt_uses (gimple stmt)
+{
+ use_operand_p use_p;
+ ssa_op_iter iter;
+ bool update = false;
+
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+ {
+ tree var = USE_FROM_PTR (use_p), def = NULL_TREE;
+ gcc_assert (DECL_P (var));
+ if (var_ann (var) == NULL)
+ {
+ if (TREE_CODE (var) == PARM_DECL && single_succ_p (ENTRY_BLOCK_PTR))
+ {
+ gimple_stmt_iterator gsi
+ = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
+ int lim;
+ /* Search a few source bind stmts at the start of first bb to
+ see if a DEBUG_EXPR_DECL can't be reused. */
+ for (lim = 32;
+ !gsi_end_p (gsi) && lim > 0;
+ gsi_next (&gsi), lim--)
+ {
+ gimple gstmt = gsi_stmt (gsi);
+ if (!gimple_debug_source_bind_p (gstmt))
+ break;
+ if (gimple_debug_source_bind_get_value (gstmt) == var)
+ {
+ def = gimple_debug_source_bind_get_var (gstmt);
+ if (TREE_CODE (def) == DEBUG_EXPR_DECL)
+ break;
+ else
+ def = NULL_TREE;
+ }
+ }
+ /* If not, add a new source bind stmt. */
+ if (def == NULL_TREE)
+ {
+ gimple def_temp;
+ def = make_node (DEBUG_EXPR_DECL);
+ def_temp = gimple_build_debug_source_bind (def, var, NULL);
+ DECL_ARTIFICIAL (def) = 1;
+ TREE_TYPE (def) = TREE_TYPE (var);
+ DECL_MODE (def) = DECL_MODE (var);
+ gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
+ gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
+ }
+ update = true;
+ }
+ }
+ else
+ {
+ def = get_current_def (var);
+ /* Check if get_current_def can be trusted. */
+ if (def)
+ {
+ basic_block bb = gimple_bb (stmt);
+ basic_block def_bb
+ = SSA_NAME_IS_DEFAULT_DEF (def)
+ ? NULL : gimple_bb (SSA_NAME_DEF_STMT (def));
+
+ /* If definition is in current bb, it is fine. */
+ if (bb == def_bb)
+ ;
+ /* If definition bb doesn't dominate the current bb,
+ it can't be used. */
+ else if (def_bb && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
+ def = NULL;
+ /* If there is just one definition and dominates the current
+ bb, it is fine. */
+ else if (get_phi_state (var) == NEED_PHI_STATE_NO)
+ ;
+ else
+ {
+ struct def_blocks_d *db_p = get_def_blocks_for (var);
+
+ /* If there are some non-debug uses in the current bb,
+ it is fine. */
+ if (bitmap_bit_p (db_p->livein_blocks, bb->index))
+ ;
+ /* Otherwise give up for now. */
+ else
+ def = NULL;
+ }
+ }
+ }
+ if (def == NULL)
+ {
+ gimple_debug_bind_reset_value (stmt);
+ update_stmt (stmt);
+ return;
+ }
+ SET_USE (use_p, def);
+ }
+ if (update)
+ update_stmt (stmt);
+}
+
/* 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. */
/* Step 1. Rewrite USES in the statement. */
if (rewrite_uses_p (stmt))
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
- {
- tree var = USE_FROM_PTR (use_p);
- gcc_assert (DECL_P (var));
- SET_USE (use_p, get_reaching_def (var));
- }
+ {
+ if (is_gimple_debug (stmt))
+ rewrite_debug_stmt_uses (stmt);
+ else
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+ {
+ tree var = USE_FROM_PTR (use_p);
+ gcc_assert (DECL_P (var));
+ SET_USE (use_p, get_reaching_def (var));
+ }
+ }
/* Step 2. Register the statement's DEF operands. */
if (register_defs_p (stmt))
EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
{
- print_generic_expr (file, referenced_var (i), 0);
+ tree var = referenced_var_lookup (cfun, i);
+ if (var)
+ print_generic_expr (file, var, 0);
+ else
+ fprintf (file, "D.%u", i);
fprintf (file, " ");
}
/* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
-void
+DEBUG_FUNCTION void
debug_decl_set (bitmap set)
{
dump_decl_set (stderr, set);
dumped. New levels are created when the dominator tree traversal
used for renaming enters a new sub-tree. */
-void
+DEBUG_FUNCTION void
debug_defs_stack (int n)
{
dump_defs_stack (stderr, n);
tree var;
fprintf (file, "\n\nCurrent reaching definitions\n\n");
- FOR_EACH_REFERENCED_VAR (var, i)
+ FOR_EACH_REFERENCED_VAR (cfun, var, i)
if (SYMS_TO_RENAME (cfun) == NULL
|| bitmap_bit_p (SYMS_TO_RENAME (cfun), DECL_UID (var)))
{
/* Dump the current reaching definition of every symbol to stderr. */
-void
+DEBUG_FUNCTION void
debug_currdefs (void)
{
dump_currdefs (stderr);
/* Dump SSA information to stderr. */
-void
+DEBUG_FUNCTION void
debug_tree_ssa (void)
{
dump_tree_ssa (stderr);
/* Dump SSA statistics on stderr. */
-void
+DEBUG_FUNCTION void
debug_tree_ssa_stats (void)
{
dump_tree_ssa_stats (stderr);
/* Dump the DEF_BLOCKS hash table on stderr. */
-void
+DEBUG_FUNCTION void
debug_def_blocks (void)
{
dump_def_blocks (stderr);
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);
+ /* If there are other predecessors to ef->dest, then
+ there must be PHI nodes for the modified
+ variable, and therefore there will be debug bind
+ stmts after the PHI nodes. The debug bind notes
+ we'd insert would force the creation of a new
+ block (diverging codegen) and be redundant with
+ the post-PHI bind stmts, so don't add them.
+
+ As for the exit edge, there wouldn't be redundant
+ bind stmts, but there wouldn't be a PC to bind
+ them to either, so avoid diverging the CFG. */
+ if (ef && single_pred_p (ef->dest)
+ && ef->dest != EXIT_BLOCK_PTR)
+ {
+ /* If there were PHI nodes in the node, we'd
+ have to make sure the value we're binding
+ doesn't need rewriting. But there shouldn't
+ be PHI nodes in a single-predecessor block,
+ so we just add the note. */
+ gsi_insert_on_edge_immediate (ef, note);
+ }
}
else
gsi_insert_after (&gsi, note, GSI_SAME_STMT);
{
fprintf (dump_file, "Updating SSA information for statement ");
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- fprintf (dump_file, "\n");
}
/* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
continue;
phis = VEC_index (gimple_vec, phis_to_rewrite, e->dest->index);
- for (i = 0; VEC_iterate (gimple, phis, i, phi); i++)
+ FOR_EACH_VEC_ELT (gimple, phis, i, phi)
{
tree arg, lhs_sym, reaching_def = NULL;
use_operand_p arg_p;
rewrite_update_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
- edge e;
- edge_iterator ei;
bool is_abnormal_phi;
gimple_stmt_iterator gsi;
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
+ fprintf (dump_file, "Registering new PHI nodes in block #%d\n",
bb->index);
/* Mark the unwind point for this block. */
/* Mark the LHS if any of the arguments flows through an abnormal
edge. */
- is_abnormal_phi = false;
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (e->flags & EDGE_ABNORMAL)
- {
- is_abnormal_phi = true;
- break;
- }
+ is_abnormal_phi = bb_has_abnormal_pred (bb);
/* If any of the PHI nodes is a replacement for a name in
OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
def_blocks = htab_create (num_referenced_vars, def_blocks_hash,
def_blocks_eq, def_blocks_free);
- FOR_EACH_REFERENCED_VAR(var, rvi)
+ FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
set_current_def (var, NULL_TREE);
}
static unsigned int
rewrite_into_ssa (void)
{
- bitmap *dfs;
+ bitmap_head *dfs;
basic_block bb;
- timevar_push (TV_TREE_SSA_OTHER);
-
/* Initialize operand data structures. */
init_ssa_operands ();
sbitmap_zero (interesting_blocks);
/* Initialize dominance frontier. */
- dfs = XNEWVEC (bitmap, last_basic_block);
+ dfs = XNEWVEC (bitmap_head, last_basic_block);
FOR_EACH_BB (bb)
- dfs[bb->index] = BITMAP_ALLOC (NULL);
+ bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
/* 1- Compute dominance frontiers. */
calculate_dominance_info (CDI_DOMINATORS);
/* Free allocated memory. */
FOR_EACH_BB (bb)
- BITMAP_FREE (dfs[bb->index]);
+ bitmap_clear (&dfs[bb->index]);
free (dfs);
sbitmap_free (interesting_blocks);
fini_ssa_renamer ();
- timevar_pop (TV_TREE_SSA_OTHER);
return 0;
}
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- TV_NONE, /* tv_id */
+ TV_TREE_SSA_OTHER, /* tv_id */
PROP_cfg | PROP_referenced_vars, /* properties_required */
PROP_ssa, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func
- | TODO_update_ssa_only_virtuals
+ TODO_update_ssa_only_virtuals
| TODO_verify_ssa
| TODO_remove_unused_locals /* todo_flags_finish */
}
/* Dump all the names replaced by NAME to stderr. */
-void
+DEBUG_FUNCTION void
debug_names_replaced_by (tree name)
{
dump_names_replaced_by (stderr, name);
if (!bitmap_empty_p (SYMS_TO_RENAME (cfun)))
{
- fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
+ fprintf (file, "\nSymbols to be put in SSA form\n");
dump_decl_set (file, SYMS_TO_RENAME (cfun));
fprintf (file, "\n");
}
if (names_to_release && !bitmap_empty_p (names_to_release))
{
- fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
+ fprintf (file, "\nSSA names to release after updating the SSA web\n\n");
EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
{
print_generic_expr (file, ssa_name (i), 0);
fprintf (file, " ");
}
+ fprintf (file, "\n");
}
-
- fprintf (file, "\n\n");
}
/* Dump SSA update information to stderr. */
-void
+DEBUG_FUNCTION void
debug_update_ssa (void)
{
dump_update_ssa (stderr);
if (gimple_code (stmt) == GIMPLE_PHI)
{
- edge e;
- edge_iterator ei;
basic_block bb = gimple_bb (stmt);
/* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (e->flags & EDGE_ABNORMAL)
- {
- SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
- break;
- }
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
}
register_new_name_mapping (new_name, old_name);
names is not pruned. PHI nodes are inserted at every IDF block. */
static void
-insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
+insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks,
unsigned update_flags)
{
basic_block entry;
bitmap_iterator bi;
unsigned i;
-#if defined ENABLE_CHECKING
if (TREE_CODE (var) == SSA_NAME)
- gcc_assert (is_old_name (var));
+ gcc_checking_assert (is_old_name (var));
else
- gcc_assert (symbol_marked_for_renaming (var));
-#endif
+ gcc_checking_assert (symbol_marked_for_renaming (var));
/* Get all the definition sites for VAR. */
db = find_def_blocks_for (var);
timevar_push (TV_TREE_SSA_INCREMENTAL);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\nUpdating SSA:\n");
+
if (!update_ssa_initialized_fn)
init_update_ssa (cfun);
gcc_assert (update_ssa_initialized_fn == cfun);
and for symbols in SYMS_TO_RENAME. */
if (insert_phi_p)
{
- bitmap *dfs;
+ bitmap_head *dfs;
/* If the caller requested PHI nodes to be added, compute
dominance frontiers. */
- dfs = XNEWVEC (bitmap, last_basic_block);
+ dfs = XNEWVEC (bitmap_head, last_basic_block);
FOR_EACH_BB (bb)
- dfs[bb->index] = BITMAP_ALLOC (NULL);
+ bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
compute_dominance_frontiers (dfs);
if (sbitmap_first_set_bit (old_ssa_names) >= 0)
update_flags);
FOR_EACH_BB (bb)
- BITMAP_FREE (dfs[bb->index]);
+ bitmap_clear (&dfs[bb->index]);
free (dfs);
/* Insertion of PHI nodes may have added blocks to the region.
dump_update_ssa (dump_file);
- fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
+ fprintf (dump_file, "Incremental SSA update started at block: %d\n",
start_bb->index);
c = 0;
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",
+ fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n",
c, PERCENT (c, last_basic_block));
if (dump_flags & TDF_DETAILS)