#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 "langhooks.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "errors.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.h"
#include "bitmap.h"
#include "tree-flow.h"
#include "tree-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"
struct def_blocks_d
{
tree var;
bitmap def_blocks;
bitmap phi_blocks;
bitmap livein_blocks;
};
static htab_t def_blocks;
static VEC(tree_on_heap) *block_defs_stack;
DEF_VEC_MALLOC_P(basic_block);
struct mark_def_sites_global_data
{
bitmap kills;
sbitmap names_to_rename;
};
struct ssa_name_info
{
ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
tree current_def;
};
#define REWRITE_THIS_STMT(T) TREE_VISITED (T)
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));
return SSA_NAME_AUX (name);
}
static inline enum need_phi_state
get_phi_state (tree var)
{
if (TREE_CODE (var) == SSA_NAME)
return get_ssa_name_ann (var)->need_phi_state;
else
return var_ann (var)->need_phi_state;
}
static inline void
set_phi_state (tree var, enum need_phi_state state)
{
if (TREE_CODE (var) == SSA_NAME)
get_ssa_name_ann (var)->need_phi_state = state;
else
var_ann (var)->need_phi_state = state;
}
static inline tree
get_current_def (tree var)
{
if (TREE_CODE (var) == SSA_NAME)
return get_ssa_name_ann (var)->current_def;
else
return var_ann (var)->current_def;
}
static inline void
set_current_def (tree var, tree def)
{
if (TREE_CODE (var) == SSA_NAME)
get_ssa_name_ann (var)->current_def = def;
else
var_ann (var)->current_def = def;
}
void
compute_global_livein (bitmap livein, bitmap def_blocks)
{
basic_block bb, *worklist, *tos;
unsigned i;
bitmap_iterator bi;
tos = worklist
= (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
{
*tos++ = BASIC_BLOCK (i);
}
while (tos != worklist)
{
edge e;
edge_iterator ei;
bb = *--tos;
FOR_EACH_EDGE (e, ei, bb->preds)
{
basic_block pred = e->src;
int pred_index = pred->index;
if (pred != ENTRY_BLOCK_PTR
&& ! bitmap_bit_p (livein, pred_index)
&& ! bitmap_bit_p (def_blocks, pred_index))
{
*tos++ = pred;
bitmap_set_bit (livein, pred_index);
}
}
}
free (worklist);
}
static inline struct def_blocks_d *
get_def_blocks_for (tree var)
{
struct def_blocks_d db, *db_p;
void **slot;
db.var = var;
slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
if (*slot == NULL)
{
db_p = xmalloc (sizeof (*db_p));
db_p->var = var;
db_p->def_blocks = BITMAP_ALLOC (NULL);
db_p->phi_blocks = BITMAP_ALLOC (NULL);
db_p->livein_blocks = BITMAP_ALLOC (NULL);
*slot = (void *) db_p;
}
else
db_p = (struct def_blocks_d *) *slot;
return db_p;
}
static void
set_def_block (tree var, basic_block bb, bool phi_p, bool is_update)
{
struct def_blocks_d *db_p;
enum need_phi_state state;
if (!is_update && TREE_CODE (var) == SSA_NAME)
var = SSA_NAME_VAR (var);
state = get_phi_state (var);
db_p = get_def_blocks_for (var);
bitmap_set_bit (db_p->def_blocks, bb->index);
if (phi_p)
bitmap_set_bit (db_p->phi_blocks, bb->index);
if (state == NEED_PHI_STATE_UNKNOWN)
set_phi_state (var, NEED_PHI_STATE_NO);
else
set_phi_state (var, NEED_PHI_STATE_MAYBE);
}
static void
set_livein_block (tree var, basic_block bb)
{
struct def_blocks_d *db_p;
enum need_phi_state state = get_phi_state (var);
db_p = get_def_blocks_for (var);
bitmap_set_bit (db_p->livein_blocks, bb->index);
if (state == NEED_PHI_STATE_NO)
{
int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
if (def_block_index == -1
|| ! dominated_by_p (CDI_DOMINATORS, bb,
BASIC_BLOCK (def_block_index)))
set_phi_state (var, NEED_PHI_STATE_MAYBE);
}
else
set_phi_state (var, NEED_PHI_STATE_MAYBE);
}
static bool
prepare_use_operand_for_rename (use_operand_p op_p, size_t *uid_p)
{
tree use = USE_FROM_PTR (op_p);
tree var = (TREE_CODE (use) != SSA_NAME) ? use : SSA_NAME_VAR (use);
*uid_p = var_ann (var)->uid;
if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
return false;
if (TREE_CODE (use) == SSA_NAME)
SET_USE (op_p, var);
return true;
}
static bool
prepare_def_operand_for_rename (tree def, size_t *uid_p)
{
tree var = (TREE_CODE (def) != SSA_NAME) ? def : SSA_NAME_VAR (def);
*uid_p = var_ann (var)->uid;
if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
return false;
return true;
}
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;
bitmap kills = gd->kills;
size_t uid;
tree stmt, def;
use_operand_p use_p;
def_operand_p def_p;
ssa_op_iter iter;
stmt = bsi_stmt (bsi);
get_stmt_operands (stmt);
REWRITE_THIS_STMT (stmt) = 0;
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTDEFKILL)
{
if (prepare_use_operand_for_rename (use_p, &uid))
{
REWRITE_THIS_STMT (stmt) = 1;
if (!bitmap_bit_p (kills, uid))
set_livein_block (USE_FROM_PTR (use_p), bb);
}
}
FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
{
if (prepare_use_operand_for_rename (use_p, &uid))
{
if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
SET_DEF (def_p, USE_FROM_PTR (use_p));
set_livein_block (USE_FROM_PTR (use_p), bb);
set_def_block (DEF_FROM_PTR (def_p), bb, false, false);
REWRITE_THIS_STMT (stmt) = 1;
}
}
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
{
if (prepare_def_operand_for_rename (def, &uid))
{
set_def_block (def, bb, false, false);
bitmap_set_bit (kills, uid);
REWRITE_THIS_STMT (stmt) = 1;
}
}
}
static bitmap
find_idf (bitmap def_blocks, bitmap *dfs)
{
bitmap_iterator bi;
unsigned bb_index;
VEC(basic_block) *work_stack;
bitmap phi_insertion_points;
work_stack = VEC_alloc (basic_block, n_basic_blocks);
phi_insertion_points = BITMAP_ALLOC (NULL);
EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
VEC_safe_push (basic_block, work_stack, BASIC_BLOCK (bb_index));
while (VEC_length (basic_block, work_stack) > 0)
{
basic_block bb = VEC_pop (basic_block, work_stack);
bb_index = bb->index;
EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
0, bb_index, bi)
{
bb = BASIC_BLOCK (bb_index);
VEC_safe_push (basic_block, work_stack, bb);
bitmap_set_bit (phi_insertion_points, bb_index);
}
}
VEC_free (basic_block, work_stack);
return phi_insertion_points;
}
static inline struct def_blocks_d *
find_def_blocks_for (tree var)
{
struct def_blocks_d dm;
dm.var = var;
return (struct def_blocks_d *) htab_find (def_blocks, &dm);
}
static void
insert_phi_nodes_for (tree var, bitmap phi_insertion_points)
{
unsigned bb_index;
edge e;
tree phi;
basic_block bb;
bitmap_iterator bi;
struct def_blocks_d *def_map;
def_map = find_def_blocks_for (var);
bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
0, bb_index, bi)
{
bb = BASIC_BLOCK (bb_index);
phi = create_phi_node (var, bb);
if (TREE_CODE (var) == SSA_NAME)
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
add_phi_arg (phi, var, e);
}
}
}
static inline void
insert_phi_nodes_1 (tree var, bitmap *dfs)
{
struct def_blocks_d *def_map;
bitmap idf;
def_map = find_def_blocks_for (var);
if (def_map == NULL)
return;
idf = find_idf (def_map->def_blocks, dfs);
if (get_phi_state (var) != NEED_PHI_STATE_NO)
insert_phi_nodes_for (var, idf);
BITMAP_FREE (idf);
}
static void
insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
{
unsigned i;
bitmap_iterator bi;
timevar_push (TV_TREE_INSERT_PHI_NODES);
if (names_to_rename)
{
EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
if (ssa_name (i))
insert_phi_nodes_1 (ssa_name (i), dfs);
}
else if (vars_to_rename)
{
EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
insert_phi_nodes_1 (referenced_var (i), dfs);
}
else
{
for (i = 0; i < num_referenced_vars; i++)
insert_phi_nodes_1 (referenced_var (i), dfs);
}
timevar_pop (TV_TREE_INSERT_PHI_NODES);
}
void
register_new_def (tree def, VEC (tree_on_heap) **block_defs_p)
{
tree var = SSA_NAME_VAR (def);
tree currdef;
if (get_phi_state (var) == NEED_PHI_STATE_NO)
{
set_current_def (var, def);
return;
}
currdef = get_current_def (var);
VEC_safe_push (tree_on_heap, *block_defs_p, currdef ? currdef : var);
set_current_def (var, def);
}
static void
rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
tree phi;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree result = PHI_RESULT (phi);
register_new_def (result, &block_defs_stack);
}
}
static tree
get_reaching_def (tree var)
{
tree default_d, currdef_var, avar;
default_d = NULL_TREE;
currdef_var = get_current_def (var);
if (currdef_var == NULL_TREE)
{
if (TREE_CODE (var) == SSA_NAME)
avar = SSA_NAME_VAR (var);
else
avar = var;
default_d = default_def (avar);
if (default_d == NULL_TREE)
{
default_d = make_ssa_name (avar, build_empty_stmt ());
set_default_def (avar, default_d);
}
set_current_def (var, default_d);
}
return (currdef_var) ? currdef_var : default_d;
}
static inline void
rewrite_operand (use_operand_p op_p)
{
tree var = USE_FROM_PTR (op_p);
if (TREE_CODE (var) != SSA_NAME)
SET_USE (op_p, get_reaching_def (var));
else
{
#if defined ENABLE_CHECKING
tree sym = SSA_NAME_VAR (var);
if (bitmap_bit_p (vars_to_rename, var_ann (sym)->uid))
gcc_assert (var == get_reaching_def (SSA_NAME_VAR (var)));
#endif
}
}
static void
rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED,
block_stmt_iterator si)
{
stmt_ann_t ann;
tree stmt;
use_operand_p use_p;
def_operand_p def_p;
ssa_op_iter iter;
stmt = bsi_stmt (si);
ann = stmt_ann (stmt);
if (!REWRITE_THIS_STMT (stmt))
return;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Renaming statement ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
get_stmt_operands (stmt);
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
rewrite_operand (use_p);
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
{
if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
SET_DEF (def_p, make_ssa_name (DEF_FROM_PTR (def_p), stmt));
register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
}
}
static void
rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
tree phi;
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
tree currdef;
if (PHI_REWRITTEN (phi))
break;
currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
add_phi_arg (phi, currdef, e);
}
}
}
static void
rewrite_virtual_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
edge e;
use_operand_p op;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
tree phi;
if (e->dest == EXIT_BLOCK_PTR)
continue;
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
tree result = PHI_RESULT (phi);
op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
if (is_gimple_reg (result)
|| !bitmap_bit_p (vars_to_rename,
var_ann (SSA_NAME_VAR (result))->uid))
continue;
SET_USE (op, get_reaching_def (SSA_NAME_VAR (result)));
if (e->flags & EDGE_ABNORMAL)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
}
}
}
static void
rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED)
{
while (VEC_length (tree_on_heap, block_defs_stack) > 0)
{
tree tmp = VEC_pop (tree_on_heap, block_defs_stack);
tree saved_def, var;
if (tmp == NULL_TREE)
break;
if (TREE_CODE (tmp) == SSA_NAME)
{
saved_def = tmp;
var = SSA_NAME_VAR (saved_def);
}
else
{
saved_def = NULL;
var = tmp;
}
set_current_def (var, saved_def);
}
}
void
dump_tree_ssa (FILE *file)
{
basic_block bb;
const char *funcname
= lang_hooks.decl_printable_name (current_function_decl, 2);
fprintf (file, "SSA information for %s\n\n", funcname);
FOR_EACH_BB (bb)
{
dump_bb (bb, file, 0);
fputs (" ", file);
print_generic_stmt (file, phi_nodes (bb), dump_flags);
fputs ("\n\n", file);
}
}
void
debug_tree_ssa (void)
{
dump_tree_ssa (stderr);
}
static void
htab_statistics (FILE *file, htab_t htab)
{
fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
(long) htab_size (htab),
(long) htab_elements (htab),
htab_collisions (htab));
}
void
dump_tree_ssa_stats (FILE *file)
{
fprintf (file, "\nHash table statistics:\n");
fprintf (file, " def_blocks: ");
htab_statistics (file, def_blocks);
fprintf (file, "\n");
}
void
debug_tree_ssa_stats (void)
{
dump_tree_ssa_stats (stderr);
}
static hashval_t
def_blocks_hash (const void *p)
{
return htab_hash_pointer
((const void *)((const struct def_blocks_d *)p)->var);
}
static int
def_blocks_eq (const void *p1, const void *p2)
{
return ((const struct def_blocks_d *)p1)->var
== ((const struct def_blocks_d *)p2)->var;
}
static void
def_blocks_free (void *p)
{
struct def_blocks_d *entry = p;
BITMAP_FREE (entry->def_blocks);
BITMAP_FREE (entry->phi_blocks);
BITMAP_FREE (entry->livein_blocks);
free (entry);
}
static int
debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
{
struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
fprintf (stderr, "VAR: ");
print_generic_expr (stderr, db_p->var, dump_flags);
bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
return 1;
}
void
debug_def_blocks (void)
{
htab_traverse (def_blocks, debug_def_blocks_r, NULL);
}
static void
invalidate_name_tags (bitmap vars_to_rename)
{
unsigned i;
bool rename_name_tags_p;
bitmap_iterator bi;
rename_name_tags_p = false;
EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
{
if (POINTER_TYPE_P (TREE_TYPE (referenced_var (i))))
{
rename_name_tags_p = true;
break;
}
}
if (rename_name_tags_p)
for (i = 0; i < num_referenced_vars; i++)
{
var_ann_t ann = var_ann (referenced_var (i));
if (ann->mem_tag_kind == NAME_TAG)
{
size_t j;
varray_type may_aliases = ann->may_aliases;
bitmap_set_bit (vars_to_rename, ann->uid);
if (ann->may_aliases)
for (j = 0; j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
{
tree var = VARRAY_TREE (may_aliases, j);
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
}
}
}
}
static void
rewrite_blocks (bool fix_virtual_phis)
{
struct dom_walk_data walk_data;
timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
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 = rewrite_initialize_block;
walk_data.before_dom_children_walk_stmts = rewrite_stmt;
walk_data.before_dom_children_after_stmts = NULL;
if (!fix_virtual_phis)
walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
else
walk_data.before_dom_children_after_stmts = rewrite_virtual_phi_arguments;
walk_data.after_dom_children_before_stmts = NULL;
walk_data.after_dom_children_walk_stmts = NULL;
walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
walk_data.global_data = NULL;
walk_data.block_local_data_size = 0;
block_defs_stack = VEC_alloc (tree_on_heap, 10);
init_walk_dominator_tree (&walk_data);
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
fini_walk_dominator_tree (&walk_data);
if (dump_file && (dump_flags & TDF_STATS))
{
dump_dfa_stats (dump_file);
dump_tree_ssa_stats (dump_file);
}
htab_delete (def_blocks);
def_blocks = NULL;
VEC_free (tree_on_heap, block_defs_stack);
block_defs_stack = NULL;
timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
}
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;
bitmap kills = gd->kills;
bitmap_clear (kills);
}
static void
mark_def_site_blocks (void)
{
size_t i;
struct dom_walk_data walk_data;
struct mark_def_sites_global_data mark_def_sites_global_data;
def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
def_blocks_hash, def_blocks_eq, def_blocks_free);
for (i = 0; i < num_referenced_vars; i++)
set_current_def (referenced_var (i), NULL_TREE);
calculate_dominance_info (CDI_DOMINATORS);
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_block;
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;
walk_data.after_dom_children_walk_stmts = NULL;
walk_data.after_dom_children_after_stmts = NULL;
mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
walk_data.global_data = &mark_def_sites_global_data;
walk_data.block_local_data_size = 0;
init_walk_dominator_tree (&walk_data);
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
fini_walk_dominator_tree (&walk_data);
BITMAP_FREE (mark_def_sites_global_data.kills);
}
void
rewrite_into_ssa (bool all)
{
bitmap *dfs;
basic_block bb;
bitmap old_vars_to_rename = vars_to_rename;
timevar_push (TV_TREE_SSA_OTHER);
if (all)
vars_to_rename = NULL;
else
{
gcc_assert (vars_to_rename);
if (bitmap_empty_p (vars_to_rename))
{
timevar_pop (TV_TREE_SSA_OTHER);
return;
}
invalidate_name_tags (vars_to_rename);
remove_all_phi_nodes_for (vars_to_rename);
}
mark_def_site_blocks ();
dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
FOR_EACH_BB (bb)
dfs[bb->index] = BITMAP_ALLOC (NULL);
compute_dominance_frontiers (dfs);
insert_phi_nodes (dfs, NULL);
rewrite_blocks (false);
FOR_EACH_BB (bb)
BITMAP_FREE (dfs[bb->index]);
free (dfs);
vars_to_rename = old_vars_to_rename;
timevar_pop (TV_TREE_SSA_OTHER);
}
static void
rewrite_all_into_ssa (void)
{
rewrite_into_ssa (true);
}
struct tree_opt_pass pass_build_ssa =
{
"ssa",
NULL,
rewrite_all_into_ssa,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_referenced_vars,
PROP_ssa,
0,
0,
TODO_dump_func | TODO_verify_ssa,
0
};
void
rewrite_def_def_chains (void)
{
calculate_dominance_info (CDI_DOMINATORS);
mark_def_site_blocks ();
rewrite_blocks (true);
}
static void
ssa_rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED)
{
while (VEC_length (tree_on_heap, block_defs_stack) > 0)
{
tree var = VEC_pop (tree_on_heap, block_defs_stack);
tree saved_def;
if (var == NULL)
break;
saved_def = VEC_pop (tree_on_heap, block_defs_stack);
set_current_def (var, saved_def);
}
}
static void
ssa_register_new_def (tree var, tree def)
{
tree currdef;
if (get_phi_state (var) == NEED_PHI_STATE_NO)
{
set_current_def (var, def);
return;
}
currdef = get_current_def (var);
VEC_safe_push (tree_on_heap, block_defs_stack, currdef);
VEC_safe_push (tree_on_heap, block_defs_stack, var);
set_current_def (var, def);
}
static void
ssa_rewrite_stmt (struct dom_walk_data *walk_data,
basic_block bb ATTRIBUTE_UNUSED,
block_stmt_iterator si)
{
stmt_ann_t ann;
tree stmt, var;
ssa_op_iter iter;
use_operand_p use_p;
def_operand_p def_p;
sbitmap names_to_rename = walk_data->global_data;
stmt = bsi_stmt (si);
ann = stmt_ann (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Renaming statement ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
gcc_assert (!ann->modified);
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
{
if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
}
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
{
var = DEF_FROM_PTR (def_p);
if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (var)))
continue;
SET_DEF (def_p, duplicate_ssa_name (var, stmt));
ssa_register_new_def (var, DEF_FROM_PTR (def_p));
}
}
static void
ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
{
edge e;
sbitmap names_to_rename = walk_data->global_data;
use_operand_p op;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
tree phi;
if (e->dest == EXIT_BLOCK_PTR)
continue;
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
if (TREE_CODE (USE_FROM_PTR (op)) != SSA_NAME)
continue;
if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (op))))
continue;
SET_USE (op, get_reaching_def (USE_FROM_PTR (op)));
if (e->flags & EDGE_ABNORMAL)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
}
}
}
static void
ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
{
tree phi, new_name;
sbitmap names_to_rename = walk_data->global_data;
edge e;
bool abnormal_phi;
edge_iterator ei;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_ABNORMAL)
break;
abnormal_phi = (e != NULL);
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree result = PHI_RESULT (phi);
if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (result)))
{
new_name = duplicate_ssa_name (result, phi);
SET_PHI_RESULT (phi, new_name);
if (abnormal_phi)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
ssa_register_new_def (result, new_name);
}
}
}
static void
ssa_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;
bitmap kills = gd->kills;
size_t uid, def_uid;
tree stmt, use, def;
ssa_op_iter iter;
stmt = bsi_stmt (bsi);
get_stmt_operands (stmt);
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
{
uid = SSA_NAME_VERSION (use);
if (TEST_BIT (gd->names_to_rename, uid)
&& !bitmap_bit_p (kills, uid))
set_livein_block (use, bb);
}
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
{
def_uid = SSA_NAME_VERSION (def);
if (TEST_BIT (gd->names_to_rename, def_uid))
{
set_def_block (def, bb, false, true);
bitmap_set_bit (kills, def_uid);
}
}
}
static void
ssa_mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
basic_block bb)
{
struct mark_def_sites_global_data *gd = walk_data->global_data;
bitmap kills = gd->kills;
tree phi, def;
unsigned def_uid;
bitmap_clear (kills);
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
def = PHI_RESULT (phi);
def_uid = SSA_NAME_VERSION (def);
if (!TEST_BIT (gd->names_to_rename, def_uid))
continue;
set_def_block (def, bb, true, true);
bitmap_set_bit (kills, def_uid);
}
}
static void
ssa_mark_phi_uses (struct dom_walk_data *walk_data, basic_block bb)
{
struct mark_def_sites_global_data *gd = walk_data->global_data;
bitmap kills = gd->kills;
edge e;
tree phi, use;
unsigned uid;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
use = PHI_ARG_DEF_FROM_EDGE (phi, e);
if (TREE_CODE (use) != SSA_NAME)
continue;
uid = SSA_NAME_VERSION (use);
if (TEST_BIT (gd->names_to_rename, uid)
&& !bitmap_bit_p (kills, uid))
set_livein_block (use, bb);
}
}
}
void
rewrite_ssa_into_ssa (void)
{
bitmap *dfs;
basic_block bb;
struct dom_walk_data walk_data;
struct mark_def_sites_global_data mark_def_sites_global_data;
unsigned i;
sbitmap snames_to_rename;
bitmap to_rename;
bitmap_iterator bi;
if (!any_marked_for_rewrite_p ())
return;
to_rename = marked_ssa_names ();
timevar_push (TV_TREE_SSA_OTHER);
def_blocks = htab_create (num_ssa_names,
def_blocks_hash, def_blocks_eq, def_blocks_free);
dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
FOR_EACH_BB (bb)
dfs[bb->index] = BITMAP_ALLOC (NULL);
calculate_dominance_info (CDI_DOMINATORS);
compute_dominance_frontiers (dfs);
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
= ssa_mark_def_sites_initialize_block;
walk_data.before_dom_children_walk_stmts = ssa_mark_def_sites;
walk_data.before_dom_children_after_stmts = ssa_mark_phi_uses;
walk_data.after_dom_children_before_stmts = NULL;
walk_data.after_dom_children_walk_stmts = NULL;
walk_data.after_dom_children_after_stmts = NULL;
snames_to_rename = sbitmap_alloc (num_ssa_names);
sbitmap_zero (snames_to_rename);
EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
{
SET_BIT (snames_to_rename, i);
set_current_def (ssa_name (i), NULL_TREE);
}
mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
mark_def_sites_global_data.names_to_rename = snames_to_rename;
walk_data.global_data = &mark_def_sites_global_data;
block_defs_stack = VEC_alloc (tree_on_heap, 10);
walk_data.block_local_data_size = 0;
init_walk_dominator_tree (&walk_data);
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
fini_walk_dominator_tree (&walk_data);
BITMAP_FREE (mark_def_sites_global_data.kills);
insert_phi_nodes (dfs, to_rename);
timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
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 = ssa_rewrite_initialize_block;
walk_data.before_dom_children_walk_stmts = ssa_rewrite_stmt;
walk_data.before_dom_children_after_stmts = ssa_rewrite_phi_arguments;
walk_data.after_dom_children_before_stmts = NULL;
walk_data.after_dom_children_walk_stmts = NULL;
walk_data.after_dom_children_after_stmts = ssa_rewrite_finalize_block;
walk_data.global_data = snames_to_rename;
walk_data.block_local_data_size = 0;
init_walk_dominator_tree (&walk_data);
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
fini_walk_dominator_tree (&walk_data);
unmark_all_for_rewrite ();
EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
{
if (SSA_NAME_AUX (ssa_name (i)))
free (SSA_NAME_AUX (ssa_name (i)));
release_ssa_name (ssa_name (i));
}
sbitmap_free (snames_to_rename);
timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
if (dump_file && (dump_flags & TDF_STATS))
{
dump_dfa_stats (dump_file);
dump_tree_ssa_stats (dump_file);
}
FOR_EACH_BB (bb)
BITMAP_FREE (dfs[bb->index]);
free (dfs);
htab_delete (def_blocks);
#ifdef ENABLE_CHECKING
for (i = 1; i < num_ssa_names; i++)
{
tree name = ssa_name (i);
if (!name)
continue;
gcc_assert (SSA_NAME_AUX (name) == NULL);
}
#endif
BITMAP_FREE (to_rename);
VEC_free (tree_on_heap, block_defs_stack);
block_defs_stack = NULL;
timevar_pop (TV_TREE_SSA_OTHER);
}