#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-pass.h"
#include "convert.h"
#include "params.h"
#include "cgraph.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_v_may_defs;
long num_vuses;
long num_v_must_defs;
};
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));
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;
cgraph_reset_static_var_maps ();
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,
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 = PHI_CHAIN (phi))
{
if (is_gimple_reg (PHI_RESULT (phi)))
{
if (!(flags & TDFA_USE_OPS))
continue;
}
else
{
if (!(flags & TDFA_USE_VOPS))
continue;
}
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);
}
}
}
void
free_df_for_stmt (tree stmt)
{
dataflow_t *df;
if (TREE_CODE (stmt) == PHI_NODE)
df = &PHI_DF (stmt);
else
{
stmt_ann_t ann = stmt_ann (stmt);
if (!ann)
return;
df = &ann->df;
}
if (!*df)
return;
if ((*df)->immediate_uses)
ggc_free ((*df)->immediate_uses);
ggc_free (*df);
*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 = PHI_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;
gcc_assert (TREE_CODE (phi) == PHI_NODE);
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))
{
tree use;
ssa_op_iter iter;
gcc_assert (TREE_CODE (stmt) != PHI_NODE);
if (flags & TDFA_USE_OPS)
{
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
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)
{
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
{
tree imm_rdef_stmt = SSA_NAME_DEF_STMT (use);
if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (use)))
add_immediate_use (imm_rdef_stmt, stmt);
}
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_KILLS)
{
tree imm_rdef_stmt = SSA_NAME_DEF_STMT (use);
if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (use)))
add_immediate_use (imm_rdef_stmt, stmt);
}
}
}
static void
add_immediate_use (tree stmt, tree use_stmt)
{
struct dataflow_d **df;
if (TREE_CODE (stmt) == PHI_NODE)
df = &PHI_DF (stmt);
else
{
stmt_ann_t ann = get_stmt_ann (stmt);
df = &ann->df;
}
if (*df == NULL)
{
*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 ((*df)->immediate_uses == NULL)
VARRAY_TREE_INIT ((*df)->immediate_uses, 4, "immediate_uses");
VARRAY_PUSH_TREE ((*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_immediate_uses (imm_stmt);
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)
{
ssa_op_iter iter;
tree val;
FOR_EACH_SSA_TREE_OPERAND (val, old, iter, SSA_OP_ALL_USES)
redirect_immediate_use (val, old, new);
}
var_ann_t
create_var_ann (tree t)
{
var_ann_t ann;
gcc_assert (t);
gcc_assert (DECL_P (t));
gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
ann = ggc_alloc (sizeof (*ann));
memset ((void *) ann, 0, sizeof (*ann));
ann->common.type = VAR_ANN;
t->common.ann = (tree_ann_t) ann;
return ann;
}
stmt_ann_t
create_stmt_ann (tree t)
{
stmt_ann_t ann;
gcc_assert (is_gimple_stmt (t));
gcc_assert (!t->common.ann || t->common.ann->common.type == STMT_ANN);
ann = ggc_alloc (sizeof (*ann));
memset ((void *) ann, 0, sizeof (*ann));
ann->common.type = STMT_ANN;
ann->modified = true;
t->common.ann = (tree_ann_t) ann;
return ann;
}
tree_ann_t
create_tree_ann (tree t)
{
tree_ann_t ann;
gcc_assert (t);
gcc_assert (!t->common.ann || t->common.ann->common.type == TREE_ANN_COMMON);
ann = ggc_alloc (sizeof (*ann));
memset ((void *) ann, 0, sizeof (*ann));
ann->common.type = TREE_ANN_COMMON;
t->common.ann = ann;
return ann;
}
tree
make_rename_temp (tree type, const char *prefix)
{
tree t = create_tmp_var (type, prefix);
if (referenced_vars)
{
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 (TREE_CODE (var) == SSA_NAME)
{
if (POINTER_TYPE_P (TREE_TYPE (var)))
dump_points_to_info_for (file, var);
var = SSA_NAME_VAR (var);
}
if (var == NULL_TREE)
{
fprintf (file, "<nil>");
return;
}
print_generic_expr (file, var, dump_flags);
ann = var_ann (var);
fprintf (file, ", UID %u", (unsigned) ann->uid);
fprintf (file, ", ");
print_generic_expr (file, TREE_TYPE (var), dump_flags);
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 (TREE_ADDRESSABLE (var))
fprintf (file, ", is addressable");
if (is_global_var (var))
fprintf (file, ", is global");
if (TREE_THIS_VOLATILE (var))
fprintf (file, ", is volatile");
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 = PHI_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++)
{
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_v_may_defs * sizeof (tree *);
total += size;
fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
SCALE (size), LABEL (size));
size = dfa_stats.num_v_must_defs * sizeof (tree *);
total += size;
fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
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;
gcc_assert (dfa_stats_p);
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 = PHI_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_v_may_defs +=
NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann));
dfa_stats_p->num_vuses += NUM_VUSES (VUSE_OPS (ann));
dfa_stats_p->num_v_must_defs +=
NUM_V_MUST_DEFS (V_MUST_DEF_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)
{
struct walk_state *walk_state = (struct walk_state *) data;
if (SSA_VAR_P (*tp))
add_referenced_var (*tp, walk_state);
else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
*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 (is_global_var (var))
mark_call_clobbered (var);
if (DECL_INITIAL (var)
&& POINTER_TYPE_P (TREE_TYPE (var)))
walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0);
}
}
tree
get_virtual_var (tree var)
{
STRIP_NOPS (var);
if (TREE_CODE (var) == SSA_NAME)
var = SSA_NAME_VAR (var);
while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
|| handled_component_p (var))
var = TREE_OPERAND (var, 0);
gcc_assert (SSA_VAR_P (var));
gcc_assert (!is_gimple_reg (var));
return var;
}
void
add_referenced_tmp_var (tree var)
{
add_referenced_var (var, NULL);
}
void
mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
{
ssa_op_iter iter;
tree val;
bitmap vars_in_vops_to_rename;
bool found_exposed_symbol = false;
int v_may_defs_before, v_may_defs_after;
int v_must_defs_before, v_must_defs_after;
vars_in_vops_to_rename = BITMAP_XMALLOC ();
v_may_defs_before = NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt));
v_must_defs_before = NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt));
FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter,
SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
{
if (!DECL_P (val))
val = SSA_NAME_VAR (val);
bitmap_set_bit (vars_in_vops_to_rename, var_ann (val)->uid);
}
modify_stmt (stmt);
get_stmt_operands (stmt);
v_may_defs_after = NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt));
v_must_defs_after = NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt));
FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_ALL_OPERANDS)
{
if (DECL_P (val))
{
found_exposed_symbol = true;
bitmap_set_bit (vars_to_rename, var_ann (val)->uid);
}
}
if (found_exposed_symbol
|| v_may_defs_before > v_may_defs_after
|| v_must_defs_before > v_must_defs_after)
bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
BITMAP_XFREE (vars_in_vops_to_rename);
}
static tree
find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
void *data ATTRIBUTE_UNUSED)
{
tree t = *tp;
if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
add_referenced_tmp_var (t);
if (IS_TYPE_OR_DECL_P (t))
*walk_subtrees = 0;
return NULL;
}
void
find_new_referenced_vars (tree *stmt_p)
{
walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
}