#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 varray_type block_defs_stack;
struct mark_def_sites_global_data
{
sbitmap kills;
sbitmap names_to_rename;
};
struct ssa_name_info
{
ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
tree current_def;
};
static void rewrite_finalize_block (struct dom_walk_data *, basic_block);
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 set_def_block (tree, basic_block, bool, bool);
static void set_livein_block (tree, basic_block);
static bool prepare_use_operand_for_rename (use_operand_p, size_t *uid_p);
static bool prepare_def_operand_for_rename (tree def, size_t *uid_p);
static void insert_phi_nodes (bitmap *, bitmap);
static void rewrite_stmt (struct dom_walk_data *, basic_block,
block_stmt_iterator);
static inline void rewrite_operand (use_operand_p);
static void insert_phi_nodes_for (tree, bitmap *, varray_type *);
static tree get_reaching_def (tree);
static hashval_t def_blocks_hash (const void *);
static int def_blocks_eq (const void *, const void *);
static void def_blocks_free (void *);
static int debug_def_blocks_r (void **, void *);
static inline struct def_blocks_d *get_def_blocks_for (tree);
static inline struct def_blocks_d *find_def_blocks_for (tree);
static void htab_statistics (FILE *, htab_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;
int 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 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);
}
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;
sbitmap kills = gd->kills;
tree phi, def;
unsigned def_uid;
sbitmap_zero (kills);
for (phi = phi_nodes (bb); phi; phi = TREE_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);
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;
sbitmap 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 = TREE_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)
&& !TEST_BIT (kills, uid))
set_livein_block (use, bb);
}
}
}
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;
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);
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)
&& !TEST_BIT (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);
}
}
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);
SET_BIT (kills, uid);
}
}
}
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;
sbitmap 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)
&& !TEST_BIT (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);
SET_BIT (kills, def_uid);
}
}
}
static void
set_def_block (tree var, basic_block bb, bool phi_p, bool ssa_p)
{
struct def_blocks_d *db_p;
enum need_phi_state state;
if (!ssa_p
&& 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 inline
void insert_phi_nodes_1 (tree var, bitmap *dfs, varray_type *work_stack)
{
if (get_phi_state (var) != NEED_PHI_STATE_NO)
insert_phi_nodes_for (var, dfs, work_stack);
}
static void
insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
{
size_t i;
varray_type work_stack;
bitmap_iterator bi;
timevar_push (TV_TREE_INSERT_PHI_NODES);
VARRAY_GENERIC_PTR_NOGC_INIT (work_stack, last_basic_block, "work_stack");
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, &work_stack);
}
}
else if (vars_to_rename)
EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
{
insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
}
else
for (i = 0; i < num_referenced_vars; i++)
insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
VARRAY_FREE (work_stack);
timevar_pop (TV_TREE_INSERT_PHI_NODES);
}
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);
VARRAY_PUSH_TREE (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 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);
VARRAY_PUSH_TREE (block_defs_stack, currdef);
VARRAY_PUSH_TREE (block_defs_stack, var);
set_current_def (var, def);
}
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);
VARRAY_PUSH_TREE (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 = TREE_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;
}
else
new_name = result;
ssa_register_new_def (result, new_name);
}
}
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 = TREE_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
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 = TREE_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
rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED)
{
while (VARRAY_ACTIVE_SIZE (block_defs_stack) > 0)
{
tree tmp = VARRAY_TOP_TREE (block_defs_stack);
tree saved_def, var;
VARRAY_POP (block_defs_stack);
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);
}
}
static void
ssa_rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED)
{
while (VARRAY_ACTIVE_SIZE (block_defs_stack) > 0)
{
tree var = VARRAY_TOP_TREE (block_defs_stack);
tree saved_def;
VARRAY_POP (block_defs_stack);
if (var == NULL)
break;
saved_def = VARRAY_TOP_TREE (block_defs_stack);
VARRAY_POP (block_defs_stack);
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);
}
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 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));
}
static void
insert_phi_nodes_for (tree var, bitmap *dfs, varray_type *work_stack)
{
struct def_blocks_d *def_map;
bitmap phi_insertion_points;
int bb_index;
edge e;
tree phi;
basic_block bb;
bitmap_iterator bi;
def_map = find_def_blocks_for (var);
if (def_map == NULL)
return;
phi_insertion_points = BITMAP_XMALLOC ();
EXECUTE_IF_SET_IN_BITMAP (def_map->def_blocks, 0, bb_index, bi)
{
VARRAY_PUSH_GENERIC_PTR_NOGC (*work_stack, BASIC_BLOCK (bb_index));
}
while (VARRAY_ACTIVE_SIZE (*work_stack) > 0)
{
int dfs_index;
bitmap_iterator bi;
bb = VARRAY_TOP_GENERIC_PTR_NOGC (*work_stack);
bb_index = bb->index;
VARRAY_POP (*work_stack);
EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index],
phi_insertion_points,
0, dfs_index, bi)
{
basic_block bb = BASIC_BLOCK (dfs_index);
VARRAY_PUSH_GENERIC_PTR_NOGC (*work_stack, bb);
bitmap_set_bit (phi_insertion_points, dfs_index);
}
}
bitmap_operation (phi_insertion_points, phi_insertion_points,
def_map->phi_blocks, BITMAP_AND_COMPL);
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);
}
}
BITMAP_XFREE (phi_insertion_points);
}
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 (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)
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
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 inline void
rewrite_operand (use_operand_p op_p)
{
if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
SET_USE (op_p, get_reaching_def (USE_FROM_PTR (op_p)));
}
void
register_new_def (tree def, varray_type *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);
VARRAY_PUSH_TREE (*block_defs_p, currdef ? currdef : var);
set_current_def (var, def);
}
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 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_XFREE (entry->def_blocks);
BITMAP_XFREE (entry->phi_blocks);
BITMAP_XFREE (entry->livein_blocks);
free (entry);
}
void
debug_def_blocks (void)
{
htab_traverse (def_blocks, debug_def_blocks_r, NULL);
}
static int
debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
{
unsigned long i;
struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
bitmap_iterator bi;
fprintf (stderr, "VAR: ");
print_generic_expr (stderr, db_p->var, dump_flags);
fprintf (stderr, ", DEF_BLOCKS: { ");
EXECUTE_IF_SET_IN_BITMAP (db_p->def_blocks, 0, i, bi)
{
fprintf (stderr, "%ld ", i);
}
fprintf (stderr, "}");
fprintf (stderr, ", LIVEIN_BLOCKS: { ");
EXECUTE_IF_SET_IN_BITMAP (db_p->livein_blocks, 0, i, bi)
{
fprintf (stderr, "%ld ", i);
}
fprintf (stderr, "}\n");
return 1;
}
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 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_XMALLOC ();
db_p->phi_blocks = BITMAP_XMALLOC ();
db_p->livein_blocks = BITMAP_XMALLOC ();
*slot = (void *) db_p;
}
else
db_p = (struct def_blocks_d *) *slot;
return db_p;
}
static void
invalidate_name_tags (bitmap vars_to_rename)
{
size_t 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;
VARRAY_TREE_INIT (block_defs_stack, 10, "Block DEFS Stack");
init_walk_dominator_tree (&walk_data);
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
fini_walk_dominator_tree (&walk_data);
htab_delete (def_blocks);
timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
}
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 = sbitmap_alloc (num_referenced_vars);
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);
sbitmap_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_first_set_bit (vars_to_rename) < 0)
{
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_XMALLOC ();
compute_dominance_frontiers (dfs);
insert_phi_nodes (dfs, NULL);
rewrite_blocks (false);
if (dump_file && (dump_flags & TDF_STATS))
{
dump_dfa_stats (dump_file);
dump_tree_ssa_stats (dump_file);
}
FOR_EACH_BB (bb)
BITMAP_XFREE (dfs[bb->index]);
free (dfs);
vars_to_rename = old_vars_to_rename;
timevar_pop (TV_TREE_SSA_OTHER);
}
void
rewrite_def_def_chains (void)
{
calculate_dominance_info (CDI_DOMINATORS);
mark_def_site_blocks ();
rewrite_blocks (true);
}
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;
tree name;
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_XMALLOC ();
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);
}
mark_def_sites_global_data.kills = sbitmap_alloc (num_ssa_names);
mark_def_sites_global_data.names_to_rename = snames_to_rename;
walk_data.global_data = &mark_def_sites_global_data;
VARRAY_TREE_INIT (block_defs_stack, 10, "Block DEFS Stack");
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);
sbitmap_free (mark_def_sites_global_data.kills);
for (i = 1; i < num_ssa_names; i++)
if (ssa_name (i))
set_current_def (ssa_name (i), NULL_TREE);
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)
{
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_XFREE (dfs[bb->index]);
free (dfs);
htab_delete (def_blocks);
for (i = 1; i < num_ssa_names; i++)
{
name = ssa_name (i);
if (!name || !SSA_NAME_AUX (name))
continue;
free (SSA_NAME_AUX (name));
SSA_NAME_AUX (name) = NULL;
}
BITMAP_XFREE (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
};