#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 "tree-alias-common.h"
#include "hashtab.h"
#include "tree-dump.h"
#include "tree-pass.h"
#include "cfgloop.h"
#include "domwalk.h"
struct def_blocks_d
{
tree var;
bitmap def_blocks;
bitmap phi_blocks;
bitmap livein_blocks;
};
static htab_t def_blocks;
struct mark_def_sites_global_data
{
sbitmap kills;
sbitmap names_to_rename;
tree *ssa_names;
};
struct rewrite_block_data
{
varray_type block_defs;
};
static void rewrite_finalize_block (struct dom_walk_data *, basic_block);
static void rewrite_initialize_block_local_data (struct dom_walk_data *,
basic_block, bool);
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);
static void set_livein_block (tree, basic_block);
static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
static void insert_phi_nodes (bitmap *, bitmap, tree *);
static void rewrite_stmt (struct dom_walk_data *, basic_block,
block_stmt_iterator);
static inline void rewrite_operand (tree *);
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 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 index;
tos = worklist
= (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
EXECUTE_IF_SET_IN_BITMAP (livein, 0, index,
*tos++ = BASIC_BLOCK (index));
while (tos != worklist)
{
edge e;
bb = *--tos;
for (e = bb->pred; e; e = e->pred_next)
{
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;
gd->ssa_names[def_uid] = def;
set_def_block (def, bb, 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;
for (e = bb->succ; e; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
{
use = phi_element_for_edge (phi, e)->def;
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;
vdef_optype vdefs;
vuse_optype vuses;
def_optype defs;
use_optype uses;
size_t i, uid;
tree stmt;
stmt_ann_t ann;
stmt = bsi_stmt (bsi);
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
uses = USE_OPS (ann);
for (i = 0; i < NUM_USES (uses); i++)
{
tree *use_p = USE_OP_PTR (uses, i);
if (prepare_operand_for_rename (use_p, &uid)
&& !TEST_BIT (kills, uid))
set_livein_block (*use_p, bb);
}
vuses = VUSE_OPS (ann);
for (i = 0; i < NUM_VUSES (vuses); i++)
{
tree *use_p = VUSE_OP_PTR (vuses, i);
if (prepare_operand_for_rename (use_p, &uid)
&& !TEST_BIT (kills, uid))
set_livein_block (*use_p, bb);
}
vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_VDEFS (vdefs); i++)
{
size_t dummy;
if (prepare_operand_for_rename (VDEF_OP_PTR (vdefs, i), &uid)
&& prepare_operand_for_rename (VDEF_RESULT_PTR (vdefs, i), &dummy))
{
VDEF_RESULT (vdefs, i) = VDEF_OP (vdefs, i);
if (!TEST_BIT (kills, uid))
set_livein_block (VDEF_OP (vdefs, i), bb);
set_def_block (VDEF_RESULT (vdefs, i), bb, false);
}
}
defs = DEF_OPS (ann);
for (i = 0; i < NUM_DEFS (defs); i++)
{
tree *def_p = DEF_OP_PTR (defs, i);
if (prepare_operand_for_rename (def_p, &uid))
{
set_def_block (*def_p, bb, 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;
vdef_optype vdefs;
vuse_optype vuses;
def_optype defs;
use_optype uses;
size_t i, uid, def_uid;
tree stmt, use, def;
stmt_ann_t ann;
stmt = bsi_stmt (bsi);
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
uses = USE_OPS (ann);
for (i = 0; i < NUM_USES (uses); i++)
{
use = USE_OP (uses, i);
uid = SSA_NAME_VERSION (use);
if (TEST_BIT (gd->names_to_rename, uid)
&& !TEST_BIT (kills, uid))
set_livein_block (use, bb);
}
vuses = VUSE_OPS (ann);
for (i = 0; i < NUM_VUSES (vuses); i++)
{
use = VUSE_OP (vuses, i);
uid = SSA_NAME_VERSION (use);
if (TEST_BIT (gd->names_to_rename, uid)
&& !TEST_BIT (kills, uid))
set_livein_block (use, bb);
}
vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_VDEFS (vdefs); i++)
{
def = VDEF_RESULT (vdefs, i);
def_uid = SSA_NAME_VERSION (def);
use = VDEF_OP (vdefs, i);
uid = SSA_NAME_VERSION (use);
if (TEST_BIT (gd->names_to_rename, uid)
&& !TEST_BIT (kills, uid))
set_livein_block (use, bb);
if (TEST_BIT (gd->names_to_rename, def_uid))
{
gd->ssa_names[def_uid] = def;
set_def_block (def, bb, false);
SET_BIT (kills, def_uid);
}
}
defs = DEF_OPS (ann);
for (i = 0; i < NUM_DEFS (defs); i++)
{
def = DEF_OP (defs, i);
def_uid = SSA_NAME_VERSION (def);
if (TEST_BIT (gd->names_to_rename, def_uid))
{
gd->ssa_names[def_uid] = def;
set_def_block (def, bb, false);
SET_BIT (kills, def_uid);
}
}
}
static void
set_def_block (tree var, basic_block bb, bool phi_p)
{
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->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_operand_for_rename (tree *op_p, size_t *uid_p)
{
tree var = (TREE_CODE (*op_p) != SSA_NAME) ? *op_p : SSA_NAME_VAR (*op_p);
*uid_p = var_ann (var)->uid;
if (vars_to_rename && !bitmap_bit_p (vars_to_rename, *uid_p))
return false;
if (TREE_CODE (*op_p) == SSA_NAME)
{
if (default_def (SSA_NAME_VAR (*op_p)) != *op_p)
release_ssa_name (*op_p);
*op_p = var;
}
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, tree *ssa_names)
{
size_t i;
varray_type work_stack;
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,
{
if (ssa_names[i])
insert_phi_nodes_1 (ssa_names[i], dfs, &work_stack);
});
}
else if (vars_to_rename)
EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i,
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_local_data (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED,
bool recycled ATTRIBUTE_UNUSED)
{
#ifdef ENABLE_CHECKING
struct rewrite_block_data *bd
= (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
if (recycled && bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
abort ();
#endif
}
static void
rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
{
tree phi;
struct rewrite_block_data *bd
= (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
tree result = PHI_RESULT (phi);
register_new_def (result, &bd->block_defs);
}
}
tree
duplicate_ssa_name (tree name, tree stmt)
{
tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt);
ssa_name_ann_t old_ann = get_ssa_name_ann (name);
ssa_name_ann_t ann = get_ssa_name_ann (new_name);
*ann = *old_ann;
if (old_ann->pt_vars)
{
ann->pt_vars = BITMAP_GGC_ALLOC ();
bitmap_copy (ann->pt_vars, old_ann->pt_vars);
}
return new_name;
}
static void
ssa_register_new_def (tree var, tree def, varray_type *block_defs_p)
{
tree currdef;
if (get_phi_state (var) == NEED_PHI_STATE_NO)
{
set_current_def (var, def);
return;
}
currdef = get_current_def (var);
if (! *block_defs_p)
VARRAY_TREE_INIT (*block_defs_p, 20, "block_defs");
VARRAY_PUSH_TREE (*block_defs_p, var);
VARRAY_PUSH_TREE (*block_defs_p, currdef);
set_current_def (var, def);
}
static void
ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
{
tree phi, new_name;
struct rewrite_block_data *bd
= (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
sbitmap names_to_rename = walk_data->global_data;
edge e;
bool abnormal_phi;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
for (e = bb->pred; e; e = e->pred_next)
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);
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, &bd->block_defs);
}
}
static void
rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
edge e;
for (e = bb->succ; e; e = e->succ_next)
{
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
ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
{
edge e;
sbitmap names_to_rename = walk_data->global_data;
tree *op;
for (e = bb->succ; e; e = e->succ_next)
{
tree phi;
if (e->dest == EXIT_BLOCK_PTR)
continue;
for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
{
op = &phi_element_for_edge (phi, e)->def;
if (TREE_CODE (*op) != SSA_NAME)
continue;
if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (*op)))
continue;
*op = get_reaching_def (*op);
if (e->flags & EDGE_ABNORMAL)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (*op) = 1;
}
}
}
static void
rewrite_finalize_block (struct dom_walk_data *walk_data,
basic_block bb ATTRIBUTE_UNUSED)
{
struct rewrite_block_data *bd
= (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
while (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
{
tree tmp = VARRAY_TOP_TREE (bd->block_defs);
tree saved_def, var;
VARRAY_POP (bd->block_defs);
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,
basic_block bb ATTRIBUTE_UNUSED)
{
struct rewrite_block_data *bd
= (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
while (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
{
tree var;
tree saved_def = VARRAY_TOP_TREE (bd->block_defs);
VARRAY_POP (bd->block_defs);
var = VARRAY_TOP_TREE (bd->block_defs);
VARRAY_POP (bd->block_defs);
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;
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,
{
VARRAY_PUSH_GENERIC_PTR_NOGC (*work_stack, BASIC_BLOCK (bb_index));
});
while (VARRAY_ACTIVE_SIZE (*work_stack) > 0)
{
int dfs_index;
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,
{
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,
do
{
bb = BASIC_BLOCK (bb_index);
phi = create_phi_node (var, bb);
if (TREE_CODE (var) == SSA_NAME)
{
for (e = bb->pred; e; e = e->pred_next)
add_phi_arg (&phi, var, e);
}
}
while (0));
BITMAP_XFREE (phi_insertion_points);
}
static void
rewrite_stmt (struct dom_walk_data *walk_data,
basic_block bb ATTRIBUTE_UNUSED,
block_stmt_iterator si)
{
size_t i;
stmt_ann_t ann;
tree stmt;
vuse_optype vuses;
vdef_optype vdefs;
def_optype defs;
use_optype uses;
struct rewrite_block_data *bd;
bd = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
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");
}
#if defined ENABLE_CHECKING
if (ann->modified)
abort ();
#endif
defs = DEF_OPS (ann);
uses = USE_OPS (ann);
vuses = VUSE_OPS (ann);
vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_USES (uses); i++)
rewrite_operand (USE_OP_PTR (uses, i));
for (i = 0; i < NUM_VUSES (vuses); i++)
rewrite_operand (VUSE_OP_PTR (vuses, i));
for (i = 0; i < NUM_DEFS (defs); i++)
{
tree *def_p = DEF_OP_PTR (defs, i);
if (TREE_CODE (*def_p) != SSA_NAME)
*def_p = make_ssa_name (*def_p, stmt);
register_new_def (*def_p, &bd->block_defs);
}
for (i = 0; i < NUM_VDEFS (vdefs); i++)
{
rewrite_operand (VDEF_OP_PTR (vdefs, i));
if (TREE_CODE (VDEF_RESULT (vdefs, i)) != SSA_NAME)
*VDEF_RESULT_PTR (vdefs, i)
= make_ssa_name (VDEF_RESULT (vdefs, i), stmt);
register_new_def (VDEF_RESULT (vdefs, i), &bd->block_defs);
}
}
static void
ssa_rewrite_stmt (struct dom_walk_data *walk_data,
basic_block bb ATTRIBUTE_UNUSED,
block_stmt_iterator si)
{
size_t i;
stmt_ann_t ann;
tree stmt, var, *use_p;
vuse_optype vuses;
vdef_optype vdefs;
def_optype defs;
use_optype uses;
struct rewrite_block_data *bd;
sbitmap names_to_rename = walk_data->global_data;
bd = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
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");
}
#if defined ENABLE_CHECKING
if (ann->modified)
abort ();
#endif
defs = DEF_OPS (ann);
uses = USE_OPS (ann);
vuses = VUSE_OPS (ann);
vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_USES (uses); i++)
{
use_p = USE_OP_PTR (uses, i);
if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (*use_p)))
*use_p = get_reaching_def (*use_p);
}
for (i = 0; i < NUM_VUSES (vuses); i++)
{
use_p = VUSE_OP_PTR (vuses, i);
if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (*use_p)))
*use_p = get_reaching_def (*use_p);
}
for (i = 0; i < NUM_DEFS (defs); i++)
{
tree *def_p = DEF_OP_PTR (defs, i);
var = *def_p;
if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (*def_p)))
continue;
*def_p = duplicate_ssa_name (var, stmt);
ssa_register_new_def (var, *def_p, &bd->block_defs);
}
for (i = 0; i < NUM_VDEFS (vdefs); i++)
{
tree *def_p = VDEF_RESULT_PTR (vdefs, i);
var = *def_p;
use_p = VDEF_OP_PTR (vdefs, i);
if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (*use_p)))
*use_p = get_reaching_def (*use_p);
if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (*def_p)))
continue;
*def_p = duplicate_ssa_name (var, stmt);
ssa_register_new_def (var, *def_p, &bd->block_defs);
}
}
static inline void
rewrite_operand (tree *op_p)
{
if (TREE_CODE (*op_p) != SSA_NAME)
*op_p = get_reaching_def (*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);
if (! *block_defs_p)
VARRAY_TREE_INIT (*block_defs_p, 20, "block_defs");
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;
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,
fprintf (stderr, "%ld ", i));
fprintf (stderr, "}");
fprintf (stderr, ", LIVEIN_BLOCKS: { ");
EXECUTE_IF_SET_IN_BITMAP (db_p->livein_blocks, 0, i,
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;
rename_name_tags_p = false;
EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i,
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);
}
}
}
}
void
rewrite_into_ssa (bool all)
{
bitmap *dfs;
basic_block bb;
struct dom_walk_data walk_data;
struct mark_def_sites_global_data mark_def_sites_global_data;
bitmap old_vars_to_rename = vars_to_rename;
unsigned i;
timevar_push (TV_TREE_SSA_OTHER);
if (all)
vars_to_rename = NULL;
else
{
if (vars_to_rename == NULL)
abort ();
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);
}
def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
def_blocks_hash, def_blocks_eq, def_blocks_free);
dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
FOR_EACH_BB (bb)
{
edge e;
int count = 0;
for (e = bb->pred; e; e = e->pred_next)
count++;
bb_ann (bb)->num_preds = count;
dfs[bb->index] = BITMAP_XMALLOC ();
}
for (i = 0; i < num_referenced_vars; i++)
set_current_def (referenced_var (i), NULL_TREE);
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 = 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);
insert_phi_nodes (dfs, NULL, NULL);
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 = rewrite_initialize_block_local_data;
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 = rewrite_add_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 = sizeof (struct rewrite_block_data);
init_walk_dominator_tree (&walk_data);
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
fini_walk_dominator_tree (&walk_data);
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);
vars_to_rename = old_vars_to_rename;
timevar_pop (TV_TREE_SSA_OTHER);
}
void
rewrite_ssa_into_ssa (bitmap names_to_rename)
{
bitmap *dfs;
basic_block bb;
struct dom_walk_data walk_data;
struct mark_def_sites_global_data mark_def_sites_global_data;
tree *ssa_names;
unsigned i;
sbitmap snames_to_rename;
if (bitmap_first_set_bit (names_to_rename) < 0)
return;
timevar_push (TV_TREE_SSA_OTHER);
def_blocks = htab_create (highest_ssa_version,
def_blocks_hash, def_blocks_eq, def_blocks_free);
ssa_names = xcalloc (highest_ssa_version, sizeof (tree));
dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
FOR_EACH_BB (bb)
{
edge e;
int count = 0;
for (e = bb->pred; e; e = e->pred_next)
count++;
bb_ann (bb)->num_preds = count;
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 (highest_ssa_version);
sbitmap_zero (snames_to_rename);
EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i,
SET_BIT (snames_to_rename, i));
mark_def_sites_global_data.kills = sbitmap_alloc (highest_ssa_version);
mark_def_sites_global_data.names_to_rename = snames_to_rename;
mark_def_sites_global_data.ssa_names = ssa_names;
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);
for (i = 0; i < highest_ssa_version; i++)
if (ssa_names[i])
set_current_def (ssa_names[i], NULL_TREE);
insert_phi_nodes (dfs, names_to_rename, ssa_names);
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
= rewrite_initialize_block_local_data;
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 = sizeof (struct rewrite_block_data);
init_walk_dominator_tree (&walk_data);
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
fini_walk_dominator_tree (&walk_data);
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);
free (ssa_names);
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
};