#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 "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"
#include "params.h"
#include "vecprim.h"
bool in_ssa_p;
struct def_blocks_d
{
tree var;
bitmap def_blocks;
bitmap phi_blocks;
bitmap livein_blocks;
};
static htab_t def_blocks;
static VEC(tree,heap) *block_defs_stack;
static sbitmap old_ssa_names;
static sbitmap new_ssa_names;
static bitmap syms_to_rename;
static bitmap names_to_release;
typedef VEC(tree, heap) *tree_vec;
DEF_VEC_P (tree_vec);
DEF_VEC_ALLOC_P (tree_vec, heap);
static VEC(tree_vec, heap) *phis_to_rewrite;
static bitmap blocks_with_phis_to_rewrite;
#define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
struct repl_map_d
{
tree name;
bitmap set;
};
static htab_t repl_tbl;
static bool need_to_initialize_update_ssa_p = true;
static bool need_to_update_vops_p = false;
struct update_ssa_stats_d
{
unsigned num_virtual_mappings;
unsigned num_total_mappings;
bitmap virtual_symbols;
unsigned num_virtual_symbols;
};
static struct update_ssa_stats_d update_ssa_stats;
struct mark_def_sites_global_data
{
bitmap kills;
sbitmap names_to_rename;
sbitmap interesting_blocks;
};
struct ssa_name_info
{
tree current_def;
ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
unsigned age;
};
typedef struct ssa_name_info *ssa_name_info_p;
DEF_VEC_P (ssa_name_info_p);
DEF_VEC_ALLOC_P (ssa_name_info_p, heap);
static VEC(ssa_name_info_p, heap) *info_for_ssa_name;
static unsigned current_info_for_ssa_name_age;
static bitmap blocks_to_update;
enum rewrite_mode {
REWRITE_ALL,
REWRITE_UPDATE
};
#define REWRITE_THIS_STMT(T) TREE_VISITED (T)
#define REGISTER_DEFS_IN_THIS_STMT(T) (T)->common.unsigned_flag
extern void dump_tree_ssa (FILE *);
extern void debug_tree_ssa (void);
extern void debug_def_blocks (void);
extern void dump_tree_ssa_stats (FILE *);
extern void debug_tree_ssa_stats (void);
void dump_update_ssa (FILE *);
void debug_update_ssa (void);
void dump_names_replaced_by (FILE *, tree);
void debug_names_replaced_by (tree);
static inline struct ssa_name_info *
get_ssa_name_ann (tree name)
{
unsigned ver = SSA_NAME_VERSION (name);
unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name);
struct ssa_name_info *info;
if (ver >= len)
{
unsigned new_len = num_ssa_names;
VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len);
while (len++ < new_len)
{
struct ssa_name_info *info = XCNEW (struct ssa_name_info);
info->age = current_info_for_ssa_name_age;
VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info);
}
}
info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver);
if (info->age < current_info_for_ssa_name_age)
{
info->need_phi_state = 0;
info->current_def = NULL_TREE;
info->age = current_info_for_ssa_name_age;
}
return info;
}
static void
clear_ssa_name_info (void)
{
current_info_for_ssa_name_age++;
}
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;
}
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;
}
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) * (last_basic_block + 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
initialize_flags_in_bb (basic_block bb)
{
tree phi, stmt;
block_stmt_iterator bsi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
REWRITE_THIS_STMT (phi) = 0;
REGISTER_DEFS_IN_THIS_STMT (phi) = 0;
}
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
gcc_assert (!stmt_modified_p (stmt));
REWRITE_THIS_STMT (stmt) = 0;
REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
}
}
static void
mark_block_for_update (basic_block bb)
{
gcc_assert (blocks_to_update != NULL);
if (bitmap_bit_p (blocks_to_update, bb->index))
return;
bitmap_set_bit (blocks_to_update, bb->index);
initialize_flags_in_bb (bb);
}
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 = XNEW (struct def_blocks_d);
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)
{
struct def_blocks_d *db_p;
enum need_phi_state 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 inline bool
symbol_marked_for_renaming (tree sym)
{
gcc_assert (DECL_P (sym));
return bitmap_bit_p (syms_to_rename, DECL_UID (sym));
}
static inline bool
is_old_name (tree name)
{
unsigned ver = SSA_NAME_VERSION (name);
return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);
}
static inline bool
is_new_name (tree name)
{
unsigned ver = SSA_NAME_VERSION (name);
return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver);
}
static hashval_t
repl_map_hash (const void *p)
{
return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
}
static int
repl_map_eq (const void *p1, const void *p2)
{
return ((const struct repl_map_d *)p1)->name
== ((const struct repl_map_d *)p2)->name;
}
static void
repl_map_free (void *p)
{
BITMAP_FREE (((struct repl_map_d *)p)->set);
free (p);
}
static inline bitmap
names_replaced_by (tree new)
{
struct repl_map_d m;
void **slot;
m.name = new;
slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
if (slot == NULL || *slot == NULL)
return NULL;
return ((struct repl_map_d *) *slot)->set;
}
static inline void
add_to_repl_tbl (tree new, tree old)
{
struct repl_map_d m, *mp;
void **slot;
m.name = new;
slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
if (*slot == NULL)
{
mp = XNEW (struct repl_map_d);
mp->name = new;
mp->set = BITMAP_ALLOC (NULL);
*slot = (void *) mp;
}
else
mp = (struct repl_map_d *) *slot;
bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
}
static void
add_new_name_mapping (tree new, tree old)
{
timevar_push (TV_TREE_SSA_INCREMENTAL);
gcc_assert (new != old && SSA_NAME_VAR (new) == SSA_NAME_VAR (old));
if (new_ssa_names->n_bits <= num_ssa_names - 1)
{
unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
}
if (!is_gimple_reg (new))
{
tree sym;
size_t uid;
need_to_update_vops_p = true;
sym = SSA_NAME_VAR (new);
uid = DECL_UID (sym);
update_ssa_stats.num_virtual_mappings++;
if (!bitmap_bit_p (update_ssa_stats.virtual_symbols, uid))
{
bitmap_set_bit (update_ssa_stats.virtual_symbols, uid);
update_ssa_stats.num_virtual_symbols++;
}
}
add_to_repl_tbl (new, old);
if (is_new_name (old))
bitmap_ior_into (names_replaced_by (new), names_replaced_by (old));
SET_BIT (new_ssa_names, SSA_NAME_VERSION (new));
SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));
update_ssa_stats.num_total_mappings++;
timevar_pop (TV_TREE_SSA_INCREMENTAL);
}
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 =
(struct mark_def_sites_global_data *) walk_data->global_data;
bitmap kills = gd->kills;
tree stmt, def;
use_operand_p use_p;
def_operand_p def_p;
ssa_op_iter iter;
stmt = bsi_stmt (bsi);
update_stmt_if_modified (stmt);
gcc_assert (blocks_to_update == NULL);
REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
REWRITE_THIS_STMT (stmt) = 0;
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTKILL)
{
tree sym = USE_FROM_PTR (use_p);
gcc_assert (DECL_P (sym));
if (!bitmap_bit_p (kills, DECL_UID (sym)))
set_livein_block (sym, bb);
REWRITE_THIS_STMT (stmt) = 1;
}
FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
{
tree sym = USE_FROM_PTR (use_p);
gcc_assert (DECL_P (sym));
set_livein_block (sym, bb);
set_def_block (sym, bb, false);
REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
REWRITE_THIS_STMT (stmt) = 1;
}
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
{
gcc_assert (DECL_P (def));
set_def_block (def, bb, false);
bitmap_set_bit (kills, DECL_UID (def));
REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
}
if (REWRITE_THIS_STMT (stmt) || REGISTER_DEFS_IN_THIS_STMT (stmt))
SET_BIT (gd->interesting_blocks, bb->index);
}
struct dom_dfsnum
{
unsigned bb_index;
unsigned dfs_num;
};
static int
cmp_dfsnum (const void *a, const void *b)
{
const struct dom_dfsnum *da = a;
const struct dom_dfsnum *db = b;
return (int) da->dfs_num - (int) db->dfs_num;
}
static unsigned
find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
{
unsigned f = 0, t = n, m;
while (t > f + 1)
{
m = (f + t) / 2;
if (defs[m].dfs_num <= s)
f = m;
else
t = m;
}
return defs[f].bb_index;
}
static void
prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
{
VEC(int, heap) *worklist;
bitmap_iterator bi;
unsigned i, b, p, u, top;
bitmap live_phis;
basic_block def_bb, use_bb;
edge e;
edge_iterator ei;
bitmap to_remove;
struct dom_dfsnum *defs;
unsigned n_defs, adef;
if (bitmap_empty_p (uses))
{
bitmap_clear (phis);
return;
}
to_remove = BITMAP_ALLOC (NULL);
bitmap_and_compl (to_remove, kills, uses);
bitmap_and_compl_into (phis, to_remove);
if (bitmap_empty_p (phis))
{
BITMAP_FREE (to_remove);
return;
}
bitmap_ior (to_remove, kills, phis);
n_defs = bitmap_count_bits (to_remove);
defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
defs[0].bb_index = 1;
defs[0].dfs_num = 0;
adef = 1;
EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
{
def_bb = BASIC_BLOCK (i);
defs[adef].bb_index = i;
defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
defs[adef + 1].bb_index = i;
defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
adef += 2;
}
BITMAP_FREE (to_remove);
gcc_assert (adef == 2 * n_defs + 1);
qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
gcc_assert (defs[0].bb_index == 1);
worklist = VEC_alloc (int, heap, n_defs + 1);
VEC_quick_push (int, worklist, 1);
top = 1;
n_defs = 1;
for (i = 1; i < adef; i++)
{
b = defs[i].bb_index;
if (b == top)
{
VEC_pop (int, worklist);
top = VEC_index (int, worklist, VEC_length (int, worklist) - 1);
defs[n_defs].bb_index = top;
defs[n_defs].dfs_num = defs[i].dfs_num + 1;
}
else
{
defs[n_defs].bb_index = defs[i].bb_index;
defs[n_defs].dfs_num = defs[i].dfs_num;
VEC_quick_push (int, worklist, b);
top = b;
}
if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
else
n_defs++;
}
VEC_pop (int, worklist);
gcc_assert (VEC_empty (int, worklist));
live_phis = BITMAP_ALLOC (NULL);
EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
{
VEC_safe_push (int, heap, worklist, i);
}
while (!VEC_empty (int, worklist))
{
b = VEC_pop (int, worklist);
if (b == ENTRY_BLOCK)
continue;
if (bitmap_bit_p (phis, b))
p = b;
else
{
use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b));
p = find_dfsnum_interval (defs, n_defs,
bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
if (!bitmap_bit_p (phis, p))
continue;
}
if (bitmap_bit_p (live_phis, p))
continue;
bitmap_set_bit (live_phis, p);
def_bb = BASIC_BLOCK (p);
FOR_EACH_EDGE (e, ei, def_bb->preds)
{
u = e->src->index;
if (bitmap_bit_p (uses, u))
continue;
if (bitmap_bit_p (kills, u))
continue;
bitmap_set_bit (uses, u);
VEC_safe_push (int, heap, worklist, u);
}
}
VEC_free (int, heap, worklist);
bitmap_copy (phis, live_phis);
BITMAP_FREE (live_phis);
free (defs);
}
static bitmap
find_idf (bitmap def_blocks, bitmap *dfs)
{
bitmap_iterator bi;
unsigned bb_index;
VEC(int,heap) *work_stack;
bitmap phi_insertion_points;
work_stack = VEC_alloc (int, heap, n_basic_blocks);
phi_insertion_points = BITMAP_ALLOC (NULL);
EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
VEC_quick_push (int, work_stack, bb_index);
while (VEC_length (int, work_stack) > 0)
{
bb_index = VEC_pop (int, work_stack);
gcc_assert (bb_index < (unsigned) last_basic_block);
EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
0, bb_index, bi)
{
VEC_safe_push (int, heap, work_stack, bb_index);
bitmap_set_bit (phi_insertion_points, bb_index);
}
}
VEC_free (int, heap, 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 inline tree
get_default_def_for (tree sym)
{
tree ddef = default_def (sym);
if (ddef == NULL_TREE)
{
ddef = make_ssa_name (sym, build_empty_stmt ());
set_default_def (sym, ddef);
}
return ddef;
}
static void
mark_phi_for_rewrite (basic_block bb, tree phi)
{
tree_vec phis;
unsigned i, idx = bb->index;
if (REWRITE_THIS_STMT (phi))
return;
REWRITE_THIS_STMT (phi) = 1;
if (!blocks_with_phis_to_rewrite)
return;
bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
VEC_reserve (tree_vec, heap, phis_to_rewrite, last_basic_block + 1);
for (i = VEC_length (tree_vec, phis_to_rewrite); i <= idx; i++)
VEC_quick_push (tree_vec, phis_to_rewrite, NULL);
phis = VEC_index (tree_vec, phis_to_rewrite, idx);
if (!phis)
phis = VEC_alloc (tree, heap, 10);
VEC_safe_push (tree, heap, phis, phi);
VEC_replace (tree_vec, phis_to_rewrite, idx, phis);
}
static void
insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
{
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);
gcc_assert (def_map);
bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
def_map->livein_blocks);
EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
{
bb = BASIC_BLOCK (bb_index);
if (update_p)
mark_block_for_update (bb);
if (update_p && TREE_CODE (var) == SSA_NAME)
{
edge_iterator ei;
tree new_lhs;
phi = create_phi_node (var, bb);
new_lhs = duplicate_ssa_name (var, phi);
SET_PHI_RESULT (phi, new_lhs);
add_new_name_mapping (new_lhs, var);
FOR_EACH_EDGE (e, ei, bb->preds)
add_phi_arg (phi, var, e);
}
else
{
tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
phi = create_phi_node (sym, bb);
}
REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
mark_phi_for_rewrite (bb, phi);
}
}
static void
insert_phi_nodes (bitmap *dfs)
{
referenced_var_iterator rvi;
tree var;
timevar_push (TV_TREE_INSERT_PHI_NODES);
FOR_EACH_REFERENCED_VAR (var, rvi)
{
struct def_blocks_d *def_map;
bitmap idf;
def_map = find_def_blocks_for (var);
if (def_map == NULL)
continue;
if (get_phi_state (var) != NEED_PHI_STATE_NO)
{
idf = find_idf (def_map->def_blocks, dfs);
insert_phi_nodes_for (var, idf, false);
BITMAP_FREE (idf);
}
}
timevar_pop (TV_TREE_INSERT_PHI_NODES);
}
void
register_new_def (tree def, VEC(tree,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, 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, 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 currdef_var, avar;
currdef_var = get_current_def (var);
if (currdef_var == NULL_TREE)
{
avar = DECL_P (var) ? var : SSA_NAME_VAR (var);
currdef_var = get_default_def_for (avar);
set_current_def (var, currdef_var);
}
return currdef_var;
}
static void
rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED,
block_stmt_iterator si)
{
tree stmt;
use_operand_p use_p;
def_operand_p def_p;
ssa_op_iter iter;
stmt = bsi_stmt (si);
gcc_assert (blocks_to_update == NULL);
if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_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");
}
if (REWRITE_THIS_STMT (stmt))
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
SSA_OP_ALL_USES|SSA_OP_ALL_KILLS)
{
tree var = USE_FROM_PTR (use_p);
gcc_assert (DECL_P (var));
SET_USE (use_p, get_reaching_def (var));
}
if (REGISTER_DEFS_IN_THIS_STMT (stmt))
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
{
tree var = DEF_FROM_PTR (def_p);
gcc_assert (DECL_P (var));
SET_DEF (def_p, make_ssa_name (var, 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;
currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
add_phi_arg (phi, currdef, e);
}
}
}
static void
rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED)
{
while (VEC_length (tree, block_defs_stack) > 0)
{
tree tmp = VEC_pop (tree, 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 = (struct def_blocks_d *) 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 inline void
register_new_update_single (tree new_name, tree old_name)
{
tree currdef = get_current_def (old_name);
VEC_reserve (tree, heap, block_defs_stack, 2);
VEC_quick_push (tree, block_defs_stack, currdef);
VEC_quick_push (tree, block_defs_stack, old_name);
set_current_def (old_name, new_name);
}
static inline void
register_new_update_set (tree new_name, bitmap old_names)
{
bitmap_iterator bi;
unsigned i;
EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
register_new_update_single (new_name, ssa_name (i));
}
static void
rewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
edge e;
edge_iterator ei;
tree phi;
bool is_abnormal_phi;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
bb->index);
VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
if (!bitmap_bit_p (blocks_to_update, bb->index))
return;
is_abnormal_phi = false;
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_ABNORMAL)
{
is_abnormal_phi = true;
break;
}
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree lhs, lhs_sym;
if (!REGISTER_DEFS_IN_THIS_STMT (phi))
continue;
lhs = PHI_RESULT (phi);
lhs_sym = SSA_NAME_VAR (lhs);
if (symbol_marked_for_renaming (lhs_sym))
register_new_update_single (lhs, lhs_sym);
else
{
if (is_new_name (lhs))
register_new_update_set (lhs, names_replaced_by (lhs));
if (is_old_name (lhs))
register_new_update_single (lhs, lhs);
}
if (is_abnormal_phi)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
}
}
static void
rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED)
{
while (VEC_length (tree, block_defs_stack) > 0)
{
tree var = VEC_pop (tree, block_defs_stack);
tree saved_def;
if (var == NULL)
return;
saved_def = VEC_pop (tree, block_defs_stack);
set_current_def (var, saved_def);
}
}
static inline void
maybe_replace_use (use_operand_p use_p)
{
tree rdef = NULL_TREE;
tree use = USE_FROM_PTR (use_p);
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
if (symbol_marked_for_renaming (sym))
rdef = get_reaching_def (sym);
else if (is_old_name (use))
rdef = get_reaching_def (use);
if (rdef && rdef != use)
SET_USE (use_p, rdef);
}
static inline void
maybe_register_def (def_operand_p def_p, tree stmt)
{
tree def = DEF_FROM_PTR (def_p);
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
if (symbol_marked_for_renaming (sym))
{
if (DECL_P (def))
{
def = make_ssa_name (def, stmt);
SET_DEF (def_p, def);
}
register_new_update_single (def, sym);
}
else
{
if (is_new_name (def))
register_new_update_set (def, names_replaced_by (def));
if (is_old_name (def))
register_new_update_single (def, def);
}
}
static void
rewrite_update_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);
gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
return;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Updating SSA information for statement ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
if (REWRITE_THIS_STMT (stmt))
{
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
maybe_replace_use (use_p);
if (need_to_update_vops_p)
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
maybe_replace_use (use_p);
}
if (REGISTER_DEFS_IN_THIS_STMT (stmt))
{
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
maybe_register_def (def_p, stmt);
if (need_to_update_vops_p)
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS)
maybe_register_def (def_p, stmt);
}
}
static inline void
replace_use (use_operand_p use_p, tree use)
{
tree rdef = get_reaching_def (use);
if (rdef != use)
SET_USE (use_p, rdef);
}
static void
rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
edge e;
edge_iterator ei;
unsigned i;
FOR_EACH_EDGE (e, ei, bb->succs)
{
tree phi;
tree_vec phis;
if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
continue;
phis = VEC_index (tree_vec, phis_to_rewrite, e->dest->index);
for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
{
tree arg;
use_operand_p arg_p;
gcc_assert (REWRITE_THIS_STMT (phi));
arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
arg = USE_FROM_PTR (arg_p);
if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
continue;
if (arg == NULL_TREE)
{
replace_use (arg_p, SSA_NAME_VAR (PHI_RESULT (phi)));
}
else
{
tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
if (symbol_marked_for_renaming (sym))
replace_use (arg_p, sym);
else if (is_old_name (arg))
replace_use (arg_p, arg);
}
if (e->flags & EDGE_ABNORMAL)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
}
}
}
static void
rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks)
{
struct dom_walk_data walk_data;
timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
memset (&walk_data, 0, sizeof (walk_data));
walk_data.dom_direction = CDI_DOMINATORS;
walk_data.interesting_blocks = blocks;
if (what == REWRITE_UPDATE)
walk_data.before_dom_children_before_stmts = rewrite_update_init_block;
else
walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
if (what == REWRITE_ALL)
walk_data.before_dom_children_walk_stmts = rewrite_stmt;
else if (what == REWRITE_UPDATE)
walk_data.before_dom_children_walk_stmts = rewrite_update_stmt;
else
gcc_unreachable ();
if (what == REWRITE_ALL)
walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
else if (what == REWRITE_UPDATE)
walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments;
else
gcc_unreachable ();
if (what == REWRITE_ALL)
walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
else if (what == REWRITE_UPDATE)
walk_data.after_dom_children_after_stmts = rewrite_update_fini_block;
else
gcc_unreachable ();
block_defs_stack = VEC_alloc (tree, heap, 10);
init_walk_dominator_tree (&walk_data);
walk_dominator_tree (&walk_data, entry);
fini_walk_dominator_tree (&walk_data);
if (dump_file && (dump_flags & TDF_STATS))
{
dump_dfa_stats (dump_file);
if (def_blocks)
dump_tree_ssa_stats (dump_file);
}
if (def_blocks)
{
htab_delete (def_blocks);
def_blocks = NULL;
}
VEC_free (tree, heap, block_defs_stack);
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 =
(struct mark_def_sites_global_data *) walk_data->global_data;
bitmap kills = gd->kills;
bitmap_clear (kills);
}
static void
mark_def_site_blocks (sbitmap interesting_blocks)
{
struct dom_walk_data walk_data;
struct mark_def_sites_global_data mark_def_sites_global_data;
referenced_var_iterator rvi;
tree var;
def_blocks = htab_create (num_referenced_vars,
def_blocks_hash, def_blocks_eq, def_blocks_free);
FOR_EACH_REFERENCED_VAR(var, rvi)
set_current_def (var, NULL_TREE);
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;
walk_data.interesting_blocks = NULL;
mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
mark_def_sites_global_data.interesting_blocks = interesting_blocks;
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);
}
static unsigned int
rewrite_into_ssa (void)
{
bitmap *dfs;
basic_block bb;
sbitmap interesting_blocks;
timevar_push (TV_TREE_SSA_OTHER);
init_ssa_operands ();
interesting_blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (interesting_blocks);
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);
mark_def_site_blocks (interesting_blocks);
insert_phi_nodes (dfs);
rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks);
FOR_EACH_BB (bb)
BITMAP_FREE (dfs[bb->index]);
free (dfs);
sbitmap_free (interesting_blocks);
timevar_pop (TV_TREE_SSA_OTHER);
in_ssa_p = true;
return 0;
}
struct tree_opt_pass pass_build_ssa =
{
"ssa",
NULL,
rewrite_into_ssa,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_referenced_vars,
PROP_ssa,
0,
0,
TODO_dump_func
| TODO_verify_ssa
| TODO_remove_unused_locals,
0
};
static void
mark_def_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
{
gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
if (insert_phi_p)
{
bool is_phi_p = TREE_CODE (stmt) == PHI_NODE;
set_def_block (var, bb, is_phi_p);
if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
{
bitmap_iterator bi;
unsigned i;
bitmap set = names_replaced_by (var);
if (set)
EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
set_def_block (ssa_name (i), bb, is_phi_p);
}
}
}
static inline void
mark_use_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
{
basic_block def_bb = bb_for_stmt (stmt);
mark_block_for_update (def_bb);
mark_block_for_update (bb);
if (TREE_CODE (stmt) == PHI_NODE)
mark_phi_for_rewrite (def_bb, stmt);
else
REWRITE_THIS_STMT (stmt) = 1;
if (insert_phi_p)
{
struct def_blocks_d *db_p = get_def_blocks_for (var);
if (!bitmap_bit_p (db_p->def_blocks, bb->index))
set_livein_block (var, bb);
}
}
static void
prepare_block_for_update (basic_block bb, bool insert_phi_p)
{
basic_block son;
block_stmt_iterator si;
tree phi;
edge e;
edge_iterator ei;
mark_block_for_update (bb);
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree lhs_sym, lhs = PHI_RESULT (phi);
lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
if (!symbol_marked_for_renaming (lhs_sym))
continue;
mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
FOR_EACH_EDGE (e, ei, bb->preds)
{
mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
}
}
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree stmt;
ssa_op_iter i;
use_operand_p use_p;
def_operand_p def_p;
stmt = bsi_stmt (si);
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
{
tree use = USE_FROM_PTR (use_p);
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
if (symbol_marked_for_renaming (sym))
mark_use_interesting (use, stmt, bb, insert_phi_p);
}
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
{
tree def = DEF_FROM_PTR (def_p);
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
if (symbol_marked_for_renaming (sym))
mark_def_interesting (def, stmt, bb, insert_phi_p);
}
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_VIRTUAL_DEFS)
{
tree def = DEF_FROM_PTR (def_p);
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
if (symbol_marked_for_renaming (sym))
{
mark_use_interesting (sym, stmt, bb, insert_phi_p);
mark_def_interesting (sym, stmt, bb, insert_phi_p);
}
}
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_VUSE)
{
tree use = USE_FROM_PTR (use_p);
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
if (symbol_marked_for_renaming (sym))
mark_use_interesting (sym, stmt, bb, insert_phi_p);
}
}
for (son = first_dom_son (CDI_DOMINATORS, bb);
son;
son = next_dom_son (CDI_DOMINATORS, son))
prepare_block_for_update (son, insert_phi_p);
}
static void
prepare_use_sites_for (tree name, bool insert_phi_p)
{
use_operand_p use_p;
imm_use_iterator iter;
FOR_EACH_IMM_USE_FAST (use_p, iter, name)
{
tree stmt = USE_STMT (use_p);
basic_block bb = bb_for_stmt (stmt);
if (TREE_CODE (stmt) == PHI_NODE)
{
int ix = PHI_ARG_INDEX_FROM_USE (use_p);
edge e = PHI_ARG_EDGE (stmt, ix);
mark_use_interesting (name, stmt, e->src, insert_phi_p);
}
else
{
mark_use_interesting (name, stmt, bb, insert_phi_p);
}
}
}
static void
prepare_def_site_for (tree name, bool insert_phi_p)
{
tree stmt;
basic_block bb;
gcc_assert (names_to_release == NULL
|| !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
stmt = SSA_NAME_DEF_STMT (name);
bb = bb_for_stmt (stmt);
if (bb)
{
gcc_assert (bb->index < last_basic_block);
mark_block_for_update (bb);
mark_def_interesting (name, stmt, bb, insert_phi_p);
}
}
static void
prepare_names_to_update (bool insert_phi_p)
{
unsigned i = 0;
bitmap_iterator bi;
sbitmap_iterator sbi;
if (names_to_release)
EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
RESET_BIT (new_ssa_names, i);
EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
prepare_def_site_for (ssa_name (i), insert_phi_p);
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
{
if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
prepare_def_site_for (ssa_name (i), insert_phi_p);
prepare_use_sites_for (ssa_name (i), insert_phi_p);
}
}
void
dump_names_replaced_by (FILE *file, tree name)
{
unsigned i;
bitmap old_set;
bitmap_iterator bi;
print_generic_expr (file, name, 0);
fprintf (file, " -> { ");
old_set = names_replaced_by (name);
EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
{
print_generic_expr (file, ssa_name (i), 0);
fprintf (file, " ");
}
fprintf (file, "}\n");
}
void
debug_names_replaced_by (tree name)
{
dump_names_replaced_by (stderr, name);
}
void
dump_update_ssa (FILE *file)
{
unsigned i = 0;
bitmap_iterator bi;
if (!need_ssa_update_p ())
return;
if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
{
sbitmap_iterator sbi;
fprintf (file, "\nSSA replacement table\n");
fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
"O_1, ..., O_j\n\n");
EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
dump_names_replaced_by (file, ssa_name (i));
fprintf (file, "\n");
fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
update_ssa_stats.num_virtual_mappings);
fprintf (file, "Number of real NEW -> OLD mappings: %7u\n",
update_ssa_stats.num_total_mappings
- update_ssa_stats.num_virtual_mappings);
fprintf (file, "Number of total NEW -> OLD mappings: %7u\n",
update_ssa_stats.num_total_mappings);
fprintf (file, "\nNumber of virtual symbols: %u\n",
update_ssa_stats.num_virtual_symbols);
}
if (syms_to_rename && !bitmap_empty_p (syms_to_rename))
{
fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
{
print_generic_expr (file, referenced_var (i), 0);
fprintf (file, " ");
}
}
if (names_to_release && !bitmap_empty_p (names_to_release))
{
fprintf (file, "\n\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\n");
}
void
debug_update_ssa (void)
{
dump_update_ssa (stderr);
}
static void
init_update_ssa (void)
{
old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
sbitmap_zero (old_ssa_names);
new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
sbitmap_zero (new_ssa_names);
repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
need_to_initialize_update_ssa_p = false;
need_to_update_vops_p = false;
syms_to_rename = BITMAP_ALLOC (NULL);
names_to_release = NULL;
memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
}
void
delete_update_ssa (void)
{
unsigned i;
bitmap_iterator bi;
sbitmap_free (old_ssa_names);
old_ssa_names = NULL;
sbitmap_free (new_ssa_names);
new_ssa_names = NULL;
htab_delete (repl_tbl);
repl_tbl = NULL;
need_to_initialize_update_ssa_p = true;
need_to_update_vops_p = false;
BITMAP_FREE (syms_to_rename);
BITMAP_FREE (update_ssa_stats.virtual_symbols);
if (names_to_release)
{
EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
release_ssa_name (ssa_name (i));
BITMAP_FREE (names_to_release);
}
clear_ssa_name_info ();
}
tree
create_new_def_for (tree old_name, tree stmt, def_operand_p def)
{
tree new_name = duplicate_ssa_name (old_name, stmt);
SET_DEF (def, new_name);
if (TREE_CODE (stmt) == PHI_NODE)
{
edge e;
edge_iterator ei;
basic_block bb = bb_for_stmt (stmt);
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_ABNORMAL)
{
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
break;
}
}
register_new_name_mapping (new_name, old_name);
set_current_def (old_name, new_name);
return new_name;
}
void
register_new_name_mapping (tree new, tree old)
{
if (need_to_initialize_update_ssa_p)
init_update_ssa ();
add_new_name_mapping (new, old);
}
void
mark_sym_for_renaming (tree sym)
{
if (need_to_initialize_update_ssa_p)
init_update_ssa ();
bitmap_set_bit (syms_to_rename, DECL_UID (sym));
if (!is_gimple_reg (sym))
need_to_update_vops_p = true;
}
void
mark_set_for_renaming (bitmap set)
{
bitmap_iterator bi;
unsigned i;
if (bitmap_empty_p (set))
return;
if (need_to_initialize_update_ssa_p)
init_update_ssa ();
bitmap_ior_into (syms_to_rename, set);
EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
if (!is_gimple_reg (referenced_var (i)))
{
need_to_update_vops_p = true;
break;
}
}
bool
need_ssa_update_p (void)
{
return syms_to_rename || old_ssa_names || new_ssa_names;
}
bool
name_registered_for_update_p (tree n)
{
if (!need_ssa_update_p ())
return false;
return is_new_name (n)
|| is_old_name (n)
|| symbol_marked_for_renaming (SSA_NAME_VAR (n));
}
bitmap
ssa_names_to_replace (void)
{
unsigned i = 0;
bitmap ret;
sbitmap_iterator sbi;
ret = BITMAP_ALLOC (NULL);
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
bitmap_set_bit (ret, i);
return ret;
}
void
release_ssa_name_after_update_ssa (tree name)
{
gcc_assert (!need_to_initialize_update_ssa_p);
if (names_to_release == NULL)
names_to_release = BITMAP_ALLOC (NULL);
bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
}
static void
insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
unsigned update_flags)
{
basic_block entry;
struct def_blocks_d *db;
bitmap idf, pruned_idf;
bitmap_iterator bi;
unsigned i;
#if defined ENABLE_CHECKING
if (TREE_CODE (var) == SSA_NAME)
gcc_assert (is_old_name (var));
else
gcc_assert (symbol_marked_for_renaming (var));
#endif
db = find_def_blocks_for (var);
if (db == NULL || bitmap_empty_p (db->def_blocks))
return;
idf = find_idf (db->def_blocks, dfs);
pruned_idf = BITMAP_ALLOC (NULL);
if (TREE_CODE (var) == SSA_NAME)
{
if (update_flags == TODO_update_ssa)
{
entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
db->def_blocks);
if (entry != ENTRY_BLOCK_PTR)
EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
if (BASIC_BLOCK (i) != entry
&& dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
bitmap_set_bit (pruned_idf, i);
}
else
{
gcc_assert (update_flags == TODO_update_ssa_full_phi);
bitmap_copy (pruned_idf, idf);
}
}
else
{
bitmap_copy (pruned_idf, idf);
}
if (!bitmap_empty_p (pruned_idf))
{
bitmap_ior_into (blocks, pruned_idf);
EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
{
edge e;
edge_iterator ei;
basic_block bb = BASIC_BLOCK (i);
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->src->index >= 0)
bitmap_set_bit (blocks, e->src->index);
}
insert_phi_nodes_for (var, pruned_idf, true);
}
BITMAP_FREE (pruned_idf);
BITMAP_FREE (idf);
}
static bool
switch_virtuals_to_full_rewrite_p (void)
{
if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS)
return false;
if (update_ssa_stats.num_virtual_mappings
> (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
* update_ssa_stats.num_virtual_symbols)
return true;
return false;
}
static void
switch_virtuals_to_full_rewrite (void)
{
unsigned i = 0;
sbitmap_iterator sbi;
if (dump_file)
{
fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n");
fprintf (dump_file, "\tNumber of virtual mappings: %7u\n",
update_ssa_stats.num_virtual_mappings);
fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n",
update_ssa_stats.num_virtual_symbols);
fprintf (dump_file, "Updating FUD-chains from top of CFG will be "
"faster than processing\nthe name mappings.\n\n");
}
EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
if (!is_gimple_reg (ssa_name (i)))
RESET_BIT (new_ssa_names, i);
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
if (!is_gimple_reg (ssa_name (i)))
RESET_BIT (old_ssa_names, i);
bitmap_ior_into (syms_to_rename, update_ssa_stats.virtual_symbols);
}
void
update_ssa (unsigned update_flags)
{
basic_block bb, start_bb;
bitmap_iterator bi;
unsigned i = 0;
sbitmap tmp;
bool insert_phi_p;
sbitmap_iterator sbi;
if (!need_ssa_update_p ())
return;
timevar_push (TV_TREE_SSA_INCREMENTAL);
blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
if (!phis_to_rewrite)
phis_to_rewrite = VEC_alloc (tree_vec, heap, last_basic_block);
blocks_to_update = BITMAP_ALLOC (NULL);
calculate_dominance_info (CDI_DOMINATORS);
gcc_assert (update_flags == TODO_update_ssa
|| update_flags == TODO_update_ssa_no_phi
|| update_flags == TODO_update_ssa_full_phi
|| update_flags == TODO_update_ssa_only_virtuals);
if (update_flags == TODO_update_ssa_only_virtuals)
{
sbitmap_zero (old_ssa_names);
sbitmap_zero (new_ssa_names);
htab_empty (repl_tbl);
}
insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
if (insert_phi_p)
{
def_blocks = htab_create (num_ssa_names, def_blocks_hash,
def_blocks_eq, def_blocks_free);
}
else
{
def_blocks = NULL;
}
if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
switch_virtuals_to_full_rewrite ();
if (sbitmap_first_set_bit (new_ssa_names) >= 0)
{
prepare_names_to_update (insert_phi_p);
if (sbitmap_first_set_bit (new_ssa_names) < 0
&& bitmap_empty_p (syms_to_rename))
goto done;
}
if (!bitmap_empty_p (syms_to_rename))
{
start_bb = ENTRY_BLOCK_PTR;
prepare_block_for_update (start_bb, insert_phi_p);
}
else
{
start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
blocks_to_update);
}
if (insert_phi_p)
{
bitmap *dfs;
dfs = XNEWVEC (bitmap, last_basic_block);
FOR_EACH_BB (bb)
dfs[bb->index] = BITMAP_ALLOC (NULL);
compute_dominance_frontiers (dfs);
if (sbitmap_first_set_bit (old_ssa_names) >= 0)
{
sbitmap_iterator sbi;
sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
sbitmap_copy (tmp, old_ssa_names);
EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
update_flags);
sbitmap_free (tmp);
}
EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
insert_updated_phi_nodes_for (referenced_var (i), dfs,
blocks_to_update, update_flags);
FOR_EACH_BB (bb)
BITMAP_FREE (dfs[bb->index]);
free (dfs);
if (start_bb != ENTRY_BLOCK_PTR)
start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
blocks_to_update);
}
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
set_current_def (ssa_name (i), NULL_TREE);
EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
set_current_def (referenced_var (i), NULL_TREE);
tmp = sbitmap_alloc (last_basic_block);
sbitmap_zero (tmp);
EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
SET_BIT (tmp, i);
rewrite_blocks (start_bb, REWRITE_UPDATE, tmp);
sbitmap_free (tmp);
if (dump_file)
{
int c;
unsigned i;
dump_update_ssa (dump_file);
fprintf (dump_file, "Incremental SSA update started at block: %d\n\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",
c, PERCENT (c, last_basic_block));
if (dump_flags & TDF_DETAILS)
{
fprintf (dump_file, "Affected blocks: ");
EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
fprintf (dump_file, "%u ", i);
fprintf (dump_file, "\n");
}
fprintf (dump_file, "\n\n");
}
done:
EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
{
tree_vec phis = VEC_index (tree_vec, phis_to_rewrite, i);
VEC_free (tree, heap, phis);
VEC_replace (tree_vec, phis_to_rewrite, i, NULL);
}
BITMAP_FREE (blocks_with_phis_to_rewrite);
BITMAP_FREE (blocks_to_update);
delete_update_ssa ();
timevar_pop (TV_TREE_SSA_INCREMENTAL);
}