#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "hashtab.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "errors.h"
#include "timevar.h"
#include "expr.h"
#include "ggc.h"
#include "langhooks.h"
#include "flags.h"
#include "function.h"
#include "diagnostic.h"
#include "tree-dump.h"
#include "tree-gimple.h"
#include "tree-flow.h"
#include "tree-inline.h"
#include "tree-alias-common.h"
#include "tree-pass.h"
#include "convert.h"
#include "params.h"
struct dfa_stats_d
{
long num_stmt_anns;
long num_var_anns;
long num_defs;
long num_uses;
long num_phis;
long num_phi_args;
int max_num_phi_args;
long num_vdefs;
long num_vuses;
};
struct walk_state
{
htab_t vars_found;
};
static void collect_dfa_stats (struct dfa_stats_d *);
static tree collect_dfa_stats_r (tree *, int *, void *);
static void add_immediate_use (tree, tree);
static tree find_vars_r (tree *, int *, void *);
static void add_referenced_var (tree, struct walk_state *);
static void compute_immediate_uses_for_phi (tree, bool (*)(tree));
static void compute_immediate_uses_for_stmt (tree, int, bool (*)(tree));
static void find_hidden_use_vars (tree);
static tree find_hidden_use_vars_r (tree *, int *, void *);
varray_type referenced_vars;
static void
find_referenced_vars (void)
{
htab_t vars_found;
basic_block bb;
block_stmt_iterator si;
struct walk_state walk_state;
tree block;
init_tree_ssa ();
block = DECL_INITIAL (current_function_decl);
while (block)
{
find_hidden_use_vars (block);
block = BLOCK_CHAIN (block);
}
vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
memset (&walk_state, 0, sizeof (walk_state));
walk_state.vars_found = vars_found;
FOR_EACH_BB (bb)
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree *stmt_p = bsi_stmt_ptr (si);
walk_tree (stmt_p, find_vars_r, &walk_state, NULL);
}
htab_delete (vars_found);
}
struct tree_opt_pass pass_referenced_vars =
{
NULL,
NULL,
find_referenced_vars,
NULL,
NULL,
0,
0,
PROP_gimple_leh | PROP_cfg,
PROP_referenced_vars,
0,
0,
0,
};
void
compute_immediate_uses (int flags, bool (*calc_for)(tree))
{
basic_block bb;
block_stmt_iterator si;
FOR_EACH_BB (bb)
{
tree phi;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
compute_immediate_uses_for_phi (phi, calc_for);
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree stmt = bsi_stmt (si);
get_stmt_operands (stmt);
compute_immediate_uses_for_stmt (stmt, flags, calc_for);
}
}
}
static void
free_df_for_stmt (tree stmt)
{
stmt_ann_t ann = stmt_ann (stmt);
if (ann && ann->df)
{
if (ann->df->immediate_uses)
ggc_free (ann->df->immediate_uses);
ggc_free (ann->df);
ann->df = NULL;
}
}
void
free_df (void)
{
basic_block bb;
block_stmt_iterator si;
FOR_EACH_BB (bb)
{
tree phi;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
free_df_for_stmt (phi);
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree stmt = bsi_stmt (si);
free_df_for_stmt (stmt);
}
}
}
static void
compute_immediate_uses_for_phi (tree phi, bool (*calc_for)(tree))
{
int i;
#ifdef ENABLE_CHECKING
if (TREE_CODE (phi) != PHI_NODE)
abort ();
#endif
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
tree arg = PHI_ARG_DEF (phi, i);
if (TREE_CODE (arg) == SSA_NAME && (!calc_for || calc_for (arg)))
{
tree imm_rdef_stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF (phi, i));
if (!IS_EMPTY_STMT (imm_rdef_stmt))
add_immediate_use (imm_rdef_stmt, phi);
}
}
}
static void
compute_immediate_uses_for_stmt (tree stmt, int flags, bool (*calc_for)(tree))
{
size_t i;
use_optype uses;
vuse_optype vuses;
vdef_optype vdefs;
stmt_ann_t ann;
#ifdef ENABLE_CHECKING
if (TREE_CODE (stmt) == PHI_NODE)
abort ();
#endif
ann = stmt_ann (stmt);
if (flags & TDFA_USE_OPS)
{
uses = USE_OPS (ann);
for (i = 0; i < NUM_USES (uses); i++)
{
tree use = USE_OP (uses, i);
tree imm_stmt = SSA_NAME_DEF_STMT (use);
if (!IS_EMPTY_STMT (imm_stmt) && (!calc_for || calc_for (use)))
add_immediate_use (imm_stmt, stmt);
}
}
if (flags & TDFA_USE_VOPS)
{
vuses = VUSE_OPS (ann);
for (i = 0; i < NUM_VUSES (vuses); i++)
{
tree vuse = VUSE_OP (vuses, i);
tree imm_rdef_stmt = SSA_NAME_DEF_STMT (vuse);
if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (vuse)))
add_immediate_use (imm_rdef_stmt, stmt);
}
vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_VDEFS (vdefs); i++)
{
tree vuse = VDEF_OP (vdefs, i);
tree imm_rdef_stmt = SSA_NAME_DEF_STMT (vuse);
if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (vuse)))
add_immediate_use (imm_rdef_stmt, stmt);
}
}
}
static void
add_immediate_use (tree stmt, tree use_stmt)
{
stmt_ann_t ann = get_stmt_ann (stmt);
struct dataflow_d *df;
df = ann->df;
if (df == NULL)
{
df = ann->df = ggc_alloc (sizeof (struct dataflow_d));
memset ((void *) df, 0, sizeof (struct dataflow_d));
df->uses[0] = use_stmt;
return;
}
if (!df->uses[1])
{
df->uses[1] = use_stmt;
return;
}
if (ann->df->immediate_uses == NULL)
VARRAY_TREE_INIT (ann->df->immediate_uses, 4, "immediate_uses");
VARRAY_PUSH_TREE (ann->df->immediate_uses, use_stmt);
}
static void
redirect_immediate_use (tree use, tree old, tree new)
{
tree imm_stmt = SSA_NAME_DEF_STMT (use);
struct dataflow_d *df = get_stmt_ann (imm_stmt)->df;
unsigned int num_uses = num_immediate_uses (df);
unsigned int i;
for (i = 0; i < num_uses; i++)
{
if (immediate_use (df, i) == old)
{
if (i == 0 || i == 1)
df->uses[i] = new;
else
VARRAY_TREE (df->immediate_uses, i - 2) = new;
}
}
}
void
redirect_immediate_uses (tree old, tree new)
{
stmt_ann_t ann = get_stmt_ann (old);
use_optype uses = USE_OPS (ann);
vuse_optype vuses = VUSE_OPS (ann);
vdef_optype vdefs = VDEF_OPS (ann);
unsigned int i;
for (i = 0; i < NUM_USES (uses); i++)
redirect_immediate_use (USE_OP (uses, i), old, new);
for (i = 0; i < NUM_VUSES (vuses); i++)
redirect_immediate_use (VUSE_OP (vuses, i), old, new);
for (i = 0; i < NUM_VDEFS (vdefs); i++)
redirect_immediate_use (VDEF_OP (vdefs, i), old, new);
}
var_ann_t
create_var_ann (tree t)
{
var_ann_t ann;
#if defined ENABLE_CHECKING
if (t == NULL_TREE
|| !DECL_P (t)
|| (t->common.ann
&& t->common.ann->common.type != VAR_ANN))
abort ();
#endif
ann = ggc_alloc (sizeof (*ann));
memset ((void *) ann, 0, sizeof (*ann));
ann->common.type = VAR_ANN;
t->common.ann = (tree_ann) ann;
return ann;
}
stmt_ann_t
create_stmt_ann (tree t)
{
stmt_ann_t ann;
#if defined ENABLE_CHECKING
if ((!is_gimple_stmt (t) && !is_essa_node (t))
|| (t->common.ann
&& t->common.ann->common.type != STMT_ANN))
abort ();
#endif
ann = ggc_alloc (sizeof (*ann));
memset ((void *) ann, 0, sizeof (*ann));
ann->common.type = STMT_ANN;
ann->modified = true;
t->common.ann = (tree_ann) ann;
return ann;
}
ssa_name_ann_t
create_ssa_name_ann (tree t)
{
ssa_name_ann_t ann;
#if defined ENABLE_CHECKING
if (t == NULL_TREE
|| (t->common.ann
&& t->common.ann->common.type != SSA_NAME_ANN))
abort ();
#endif
ann = ggc_alloc (sizeof (*ann));
memset ((void *) ann, 0, sizeof (*ann));
ann->common.type = SSA_NAME_ANN;
t->common.ann = (tree_ann) ann;
return ann;
}
tree
make_rename_temp (tree type, const char *prefix)
{
tree t = create_tmp_var (type, prefix);
add_referenced_tmp_var (t);
bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
return t;
}
void
dump_referenced_vars (FILE *file)
{
size_t i;
fprintf (file, "\nReferenced variables in %s: %u\n\n",
get_name (current_function_decl), (unsigned) num_referenced_vars);
for (i = 0; i < num_referenced_vars; i++)
{
tree var = referenced_var (i);
fprintf (file, "Variable: ");
dump_variable (file, var);
fprintf (file, "\n");
}
}
void
debug_referenced_vars (void)
{
dump_referenced_vars (stderr);
}
void
dump_variable (FILE *file, tree var)
{
var_ann_t ann;
if (var == NULL_TREE)
{
fprintf (file, "<nil>");
return;
}
print_generic_expr (file, var, dump_flags);
if (TREE_CODE (var) == SSA_NAME)
var = SSA_NAME_VAR (var);
ann = var_ann (var);
fprintf (file, ", UID %u", (unsigned) ann->uid);
if (ann->has_hidden_use)
fprintf (file, ", has hidden uses");
if (ann->type_mem_tag)
{
fprintf (file, ", type memory tag: ");
print_generic_expr (file, ann->type_mem_tag, dump_flags);
}
if (ann->is_alias_tag)
fprintf (file, ", is an alias tag");
if (needs_to_live_in_memory (var))
fprintf (file, ", is %s", TREE_STATIC (var) ? "static" : "global");
if (is_call_clobbered (var))
fprintf (file, ", call clobbered");
if (ann->default_def)
{
fprintf (file, ", default def: ");
print_generic_expr (file, ann->default_def, dump_flags);
}
if (ann->may_aliases)
{
fprintf (file, ", may aliases: ");
dump_may_aliases_for (file, var);
}
fprintf (file, "\n");
}
void
debug_variable (tree var)
{
dump_variable (stderr, var);
}
void
dump_immediate_uses (FILE *file)
{
basic_block bb;
block_stmt_iterator si;
const char *funcname
= lang_hooks.decl_printable_name (current_function_decl, 2);
fprintf (file, "\nDef-use edges for function %s\n", funcname);
FOR_EACH_BB (bb)
{
tree phi;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
dump_immediate_uses_for (file, phi);
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
dump_immediate_uses_for (file, bsi_stmt (si));
}
fprintf (file, "\n");
}
void
debug_immediate_uses (void)
{
dump_immediate_uses (stderr);
}
void
dump_immediate_uses_for (FILE *file, tree stmt)
{
dataflow_t df = get_immediate_uses (stmt);
int num_imm_uses = num_immediate_uses (df);
if (num_imm_uses > 0)
{
int i;
fprintf (file, "-> ");
print_generic_stmt (file, stmt, TDF_SLIM);
fprintf (file, "\n");
for (i = 0; i < num_imm_uses; i++)
{
basic_block bb = bb_for_stmt (immediate_use (df, i));
fprintf (file, "\t[%d]\t", bb->index);
print_generic_stmt (file, immediate_use (df, i), TDF_SLIM);
fprintf (file, "\n");
}
fprintf (file, "\n");
}
}
void
debug_immediate_uses_for (tree stmt)
{
dump_immediate_uses_for (stderr, stmt);
}
void
dump_dfa_stats (FILE *file)
{
struct dfa_stats_d dfa_stats;
unsigned long size, total = 0;
const char * const fmt_str = "%-30s%-13s%12s\n";
const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
const char * const fmt_str_3 = "%-43s%11lu%c\n";
const char *funcname
= lang_hooks.decl_printable_name (current_function_decl, 2);
collect_dfa_stats (&dfa_stats);
fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
fprintf (file, "---------------------------------------------------------\n");
fprintf (file, fmt_str, "", " Number of ", "Memory");
fprintf (file, fmt_str, "", " instances ", "used ");
fprintf (file, "---------------------------------------------------------\n");
size = num_referenced_vars * sizeof (tree);
total += size;
fprintf (file, fmt_str_1, "Referenced variables", num_referenced_vars,
SCALE (size), LABEL (size));
size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
total += size;
fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
SCALE (size), LABEL (size));
size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
total += size;
fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
SCALE (size), LABEL (size));
size = dfa_stats.num_uses * sizeof (tree *);
total += size;
fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
SCALE (size), LABEL (size));
size = dfa_stats.num_defs * sizeof (tree *);
total += size;
fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
SCALE (size), LABEL (size));
size = dfa_stats.num_vuses * sizeof (tree *);
total += size;
fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
SCALE (size), LABEL (size));
size = dfa_stats.num_vdefs * sizeof (tree *);
total += size;
fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
SCALE (size), LABEL (size));
size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
total += size;
fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
SCALE (size), LABEL (size));
size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
total += size;
fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
SCALE (size), LABEL (size));
fprintf (file, "---------------------------------------------------------\n");
fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
LABEL (total));
fprintf (file, "---------------------------------------------------------\n");
fprintf (file, "\n");
if (dfa_stats.num_phis)
fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
(float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
dfa_stats.max_num_phi_args);
fprintf (file, "\n");
}
void
debug_dfa_stats (void)
{
dump_dfa_stats (stderr);
}
static void
collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
{
htab_t htab;
basic_block bb;
block_stmt_iterator i;
if (dfa_stats_p == NULL)
abort ();
memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL);
for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
(void *) htab);
htab_delete (htab);
FOR_EACH_BB (bb)
{
tree phi;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
dfa_stats_p->num_phis++;
dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
}
}
}
static tree
collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
void *data)
{
tree t = *tp;
struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
if (t->common.ann)
{
switch (ann_type (t->common.ann))
{
case STMT_ANN:
{
stmt_ann_t ann = (stmt_ann_t) t->common.ann;
dfa_stats_p->num_stmt_anns++;
dfa_stats_p->num_defs += NUM_DEFS (DEF_OPS (ann));
dfa_stats_p->num_uses += NUM_USES (USE_OPS (ann));
dfa_stats_p->num_vdefs += NUM_VDEFS (VDEF_OPS (ann));
dfa_stats_p->num_vuses += NUM_VUSES (VUSE_OPS (ann));
break;
}
case VAR_ANN:
dfa_stats_p->num_var_anns++;
break;
default:
break;
}
}
return NULL;
}
static tree
find_vars_r (tree *tp, int *walk_subtrees, void *data)
{
tree t = *tp;
struct walk_state *walk_state = (struct walk_state *)data;
if (SSA_VAR_P (t))
{
add_referenced_var (t, walk_state);
}
else if (DECL_P (t)
|| TYPE_P (t)
|| TREE_CODE_CLASS (TREE_CODE (t)) == 'c')
{
*walk_subtrees = 0;
}
return NULL_TREE;
}
static void
add_referenced_var (tree var, struct walk_state *walk_state)
{
void **slot;
var_ann_t v_ann;
v_ann = get_var_ann (var);
if (walk_state)
slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
else
slot = NULL;
if (slot == NULL || *slot == NULL)
{
if (slot)
*slot = (void *) var;
v_ann->uid = num_referenced_vars;
VARRAY_PUSH_TREE (referenced_vars, var);
if (needs_to_live_in_memory (var))
mark_call_clobbered (var);
if (DECL_NONLOCAL (var))
v_ann->used = 1;
}
}
tree
get_virtual_var (tree var)
{
enum tree_code code;
STRIP_NOPS (var);
if (TREE_CODE (var) == SSA_NAME)
var = SSA_NAME_VAR (var);
code = TREE_CODE (var);
while (code == ARRAY_REF
|| code == COMPONENT_REF
|| code == REALPART_EXPR
|| code == IMAGPART_EXPR)
{
var = TREE_OPERAND (var, 0);
code = TREE_CODE (var);
}
#ifdef ENABLE_CHECKING
if (!SSA_VAR_P (var)
|| is_gimple_reg (var))
abort ();
#endif
return var;
}
static void
find_hidden_use_vars (tree block)
{
tree sub, decl, tem;
for (decl = BLOCK_VARS (block); decl; decl = TREE_CHAIN (decl))
{
int inside_vla = 0;
walk_tree (&decl, find_hidden_use_vars_r, &inside_vla, NULL);
}
for (sub = BLOCK_SUBBLOCKS (block); sub; sub = TREE_CHAIN (sub))
find_hidden_use_vars (sub);
tem = get_pending_sizes ();
put_pending_sizes (tem);
for (; tem; tem = TREE_CHAIN (tem))
{
int inside_vla = 1;
walk_tree (&TREE_VALUE (tem), find_hidden_use_vars_r, &inside_vla, NULL);
}
}
static tree
find_hidden_use_vars_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
void *data ATTRIBUTE_UNUSED)
{
int *inside_vla = (int *) data;
if (SSA_VAR_P (*tp)
&& ((DECL_SIZE (*tp)
&& ! really_constant_p (DECL_SIZE (*tp)))
|| (DECL_SIZE_UNIT (*tp)
&& ! really_constant_p (DECL_SIZE_UNIT (*tp)))))
{
int save = *inside_vla;
*inside_vla = 1;
walk_tree (&DECL_SIZE (*tp), find_hidden_use_vars_r, inside_vla, NULL);
walk_tree (&DECL_SIZE_UNIT (*tp), find_hidden_use_vars_r,
inside_vla, NULL);
*inside_vla = save;
}
else if (*inside_vla && SSA_VAR_P (*tp))
set_has_hidden_use (*tp);
return NULL_TREE;
}
void
add_referenced_tmp_var (tree var)
{
add_referenced_var (var, NULL);
}
static inline bool
vdefs_disappeared_p (vdef_optype vdefs_before, vdef_optype vdefs_after)
{
if (vdefs_before == NULL)
return false;
if (vdefs_after == NULL
|| NUM_VDEFS (vdefs_before) > NUM_VDEFS (vdefs_after))
return true;
return false;
}
void
mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
{
def_optype defs;
use_optype uses;
vdef_optype vdefs;
vuse_optype vuses;
size_t i;
bitmap vars_in_vops_to_rename;
bool found_exposed_symbol = false;
vdef_optype vdefs_before, vdefs_after;
stmt_ann_t ann;
vars_in_vops_to_rename = BITMAP_XMALLOC ();
ann = stmt_ann (stmt);
vdefs_before = vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_VDEFS (vdefs); i++)
{
tree var = VDEF_RESULT (vdefs, i);
if (!DECL_P (var))
var = SSA_NAME_VAR (var);
bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
}
vuses = VUSE_OPS (ann);
for (i = 0; i < NUM_VUSES (vuses); i++)
{
tree var = VUSE_OP (vuses, i);
if (!DECL_P (var))
var = SSA_NAME_VAR (var);
bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
}
modify_stmt (stmt);
get_stmt_operands (stmt);
defs = DEF_OPS (ann);
for (i = 0; i < NUM_DEFS (defs); i++)
{
tree var = DEF_OP (defs, i);
if (DECL_P (var))
{
found_exposed_symbol = true;
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
}
}
uses = USE_OPS (ann);
for (i = 0; i < NUM_USES (uses); i++)
{
tree var = USE_OP (uses, i);
if (DECL_P (var))
{
found_exposed_symbol = true;
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
}
}
vdefs_after = vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_VDEFS (vdefs); i++)
{
tree var = VDEF_RESULT (vdefs, i);
if (DECL_P (var))
{
found_exposed_symbol = true;
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
}
}
vuses = VUSE_OPS (ann);
for (i = 0; i < NUM_VUSES (vuses); i++)
{
tree var = VUSE_OP (vuses, i);
if (DECL_P (var))
{
found_exposed_symbol = true;
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
}
}
if (found_exposed_symbol
|| vdefs_disappeared_p (vdefs_before, vdefs_after))
bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
BITMAP_XFREE (vars_in_vops_to_rename);
}