#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 "ggc.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"
void
ssa_remove_edge (edge e)
{
tree phi, next;
for (phi = phi_nodes (e->dest); phi; phi = next)
{
next = TREE_CHAIN (phi);
remove_phi_arg (phi, e->src);
}
remove_edge (e);
}
edge
ssa_redirect_edge (edge e, basic_block dest)
{
tree phi, next;
tree list = NULL, *last = &list;
tree src, dst, node;
int i;
for (phi = phi_nodes (e->dest); phi; phi = next)
{
next = TREE_CHAIN (phi);
i = phi_arg_from_edge (phi, e);
if (i < 0)
continue;
src = PHI_ARG_DEF (phi, i);
dst = PHI_RESULT (phi);
node = build_tree_list (dst, src);
*last = node;
last = &TREE_CHAIN (node);
remove_phi_arg_num (phi, i);
}
e = redirect_edge_succ_nodup (e, dest);
PENDING_STMT (e) = list;
return e;
}
static bool
verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
tree stmt)
{
bool err = false;
if (TREE_CODE (ssa_name) != SSA_NAME)
{
error ("Expected an SSA_NAME object");
debug_generic_stmt (ssa_name);
debug_generic_stmt (stmt);
}
if (definition_block[SSA_NAME_VERSION (ssa_name)])
{
error ("SSA_NAME created in two different blocks %i and %i",
definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
fprintf (stderr, "SSA_NAME: ");
debug_generic_stmt (ssa_name);
debug_generic_stmt (stmt);
err = true;
}
definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
{
error ("SSA_NAME_DEF_STMT is wrong");
fprintf (stderr, "SSA_NAME: ");
debug_generic_stmt (ssa_name);
fprintf (stderr, "Expected definition statement:\n");
debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name));
fprintf (stderr, "\nActual definition statement:\n");
debug_generic_stmt (stmt);
err = true;
}
return err;
}
static bool
verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
tree stmt, bool check_abnormal)
{
bool err = false;
if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name)))
;
else if (!def_bb)
{
error ("Missing definition");
err = true;
}
else if (bb != def_bb
&& !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
{
error ("Definition in block %i does not dominate use in block %i",
def_bb->index, bb->index);
err = true;
}
if (check_abnormal
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
{
error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
err = true;
}
if (err)
{
fprintf (stderr, "for SSA_NAME: ");
debug_generic_stmt (ssa_name);
fprintf (stderr, "in statement:\n");
debug_generic_stmt (stmt);
}
return err;
}
static bool
verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
{
edge e;
bool err = false;
int i, phi_num_args = PHI_NUM_ARGS (phi);
for (e = bb->pred; e; e = e->pred_next)
e->aux = (void *) 1;
for (i = 0; i < phi_num_args; i++)
{
tree op = PHI_ARG_DEF (phi, i);
e = PHI_ARG_EDGE (phi, i);
if (TREE_CODE (op) == SSA_NAME)
err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
phi, e->flags & EDGE_ABNORMAL);
if (e->dest != bb)
{
error ("Wrong edge %d->%d for PHI argument\n",
e->src->index, e->dest->index, bb->index);
err = true;
}
if (e->aux == (void *) 0)
{
error ("PHI argument flowing through dead edge %d->%d\n",
e->src->index, e->dest->index);
err = true;
}
if (e->aux == (void *) 2)
{
error ("PHI argument duplicated for edge %d->%d\n", e->src->index,
e->dest->index);
err = true;
}
if (err)
{
fprintf (stderr, "PHI argument\n");
debug_generic_stmt (op);
}
e->aux = (void *) 2;
}
for (e = bb->pred; e; e = e->pred_next)
{
if (e->aux != (void *) 2)
{
error ("No argument flowing through edge %d->%d\n", e->src->index,
e->dest->index);
err = true;
}
e->aux = (void *) 0;
}
if (err)
{
fprintf (stderr, "for PHI node\n");
debug_generic_stmt (phi);
}
return err;
}
void
verify_ssa (void)
{
bool err = false;
basic_block bb;
basic_block *definition_block = xcalloc (highest_ssa_version,
sizeof (basic_block));
timevar_push (TV_TREE_SSA_VERIFY);
calculate_dominance_info (CDI_DOMINATORS);
FOR_EACH_BB (bb)
{
tree phi;
block_stmt_iterator bsi;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
err |= verify_def (bb, definition_block, PHI_RESULT (phi), phi);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt;
stmt_ann_t ann;
unsigned int j;
vdef_optype vdefs;
def_optype defs;
stmt = bsi_stmt (bsi);
ann = stmt_ann (stmt);
get_stmt_operands (stmt);
vdefs = VDEF_OPS (ann);
for (j = 0; j < NUM_VDEFS (vdefs); j++)
{
tree op = VDEF_RESULT (vdefs, j);
if (is_gimple_reg (op))
{
error ("Found a virtual definition for a GIMPLE register");
debug_generic_stmt (op);
debug_generic_stmt (stmt);
err = true;
}
err |= verify_def (bb, definition_block, op, stmt);
}
defs = DEF_OPS (ann);
for (j = 0; j < NUM_DEFS (defs); j++)
{
tree op = DEF_OP (defs, j);
if (TREE_CODE (op) == SSA_NAME && !is_gimple_reg (op))
{
error ("Found a real definition for a non-GIMPLE register");
debug_generic_stmt (op);
debug_generic_stmt (stmt);
err = true;
}
err |= verify_def (bb, definition_block, op, stmt);
}
}
}
FOR_EACH_BB (bb)
{
edge e;
tree phi;
block_stmt_iterator bsi;
for (e = bb->pred; e; e = e->pred_next)
{
if (e->aux)
{
error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
e->dest->index);
err = true;
}
}
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
err |= verify_phi_args (phi, bb, definition_block);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
stmt_ann_t ann = stmt_ann (stmt);
unsigned int j;
vuse_optype vuses;
vdef_optype vdefs;
use_optype uses;
vuses = VUSE_OPS (ann);
for (j = 0; j < NUM_VUSES (vuses); j++)
{
tree op = VUSE_OP (vuses, j);
if (is_gimple_reg (op))
{
error ("Found a virtual use for a GIMPLE register");
debug_generic_stmt (op);
debug_generic_stmt (stmt);
err = true;
}
err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
op, stmt, false);
}
vdefs = VDEF_OPS (ann);
for (j = 0; j < NUM_VDEFS (vdefs); j++)
{
tree op = VDEF_OP (vdefs, j);
if (is_gimple_reg (op))
{
error ("Found a virtual use for a GIMPLE register");
debug_generic_stmt (op);
debug_generic_stmt (stmt);
err = true;
}
err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
op, stmt, false);
}
uses = USE_OPS (ann);
for (j = 0; j < NUM_USES (uses); j++)
{
tree op = USE_OP (uses, j);
if (TREE_CODE (op) == SSA_NAME && !is_gimple_reg (op))
{
error ("Found a real use of a non-GIMPLE register");
debug_generic_stmt (op);
debug_generic_stmt (stmt);
err = true;
}
err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
op, stmt, false);
}
}
}
free (definition_block);
timevar_pop (TV_TREE_SSA_VERIFY);
if (err)
internal_error ("verify_ssa failed.");
}
void
set_is_used (tree t)
{
while (1)
{
if (SSA_VAR_P (t))
break;
switch (TREE_CODE (t))
{
case ARRAY_REF:
case COMPONENT_REF:
case REALPART_EXPR:
case IMAGPART_EXPR:
case BIT_FIELD_REF:
case INDIRECT_REF:
t = TREE_OPERAND (t, 0);
break;
default:
return;
}
}
if (TREE_CODE (t) == SSA_NAME)
t = SSA_NAME_VAR (t);
var_ann (t)->used = 1;
}
void
init_tree_ssa (void)
{
VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
call_clobbered_vars = BITMAP_XMALLOC ();
init_ssa_operands ();
init_ssanames ();
init_phinodes ();
global_var = NULL_TREE;
aliases_computed_p = false;
}
void
delete_tree_ssa (void)
{
size_t i;
basic_block bb;
block_stmt_iterator bsi;
FOR_EACH_BB (bb)
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
bsi_stmt (bsi)->common.ann = NULL;
if (referenced_vars)
{
for (i = 0; i < num_referenced_vars; i++)
referenced_var (i)->common.ann = NULL;
referenced_vars = NULL;
}
fini_ssanames ();
fini_phinodes ();
fini_ssa_operands ();
global_var = NULL_TREE;
BITMAP_XFREE (call_clobbered_vars);
call_clobbered_vars = NULL;
aliases_computed_p = false;
}
bool
tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
{
if (inner_type == outer_type
|| (lang_hooks.types_compatible_p (inner_type, outer_type)))
return true;
else if (POINTER_TYPE_P (inner_type)
&& POINTER_TYPE_P (outer_type)
&& TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
return true;
else if (POINTER_TYPE_P (inner_type)
&& POINTER_TYPE_P (outer_type)
&& lang_hooks.types_compatible_p (inner_type, outer_type))
return true;
else if (INTEGRAL_TYPE_P (inner_type)
&& INTEGRAL_TYPE_P (outer_type)
&& TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
&& TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
&& TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
return true;
else if (TREE_CODE (inner_type) == COMPLEX_TYPE
&& TREE_CODE (outer_type) == COMPLEX_TYPE
&& tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
TREE_TYPE (inner_type)))
return true;
return false;
}
bool
tree_ssa_useless_type_conversion (tree expr)
{
if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
TREE_TYPE (TREE_OPERAND (expr,
0)));
return false;
}
static bool
walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
bitmap visited)
{
tree def_stmt;
if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
return false;
bitmap_set_bit (visited, SSA_NAME_VERSION (var));
def_stmt = SSA_NAME_DEF_STMT (var);
if (TREE_CODE (def_stmt) != PHI_NODE)
{
return (*fn) (var, def_stmt, data);
}
else
{
int i;
for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
{
tree arg = PHI_ARG_DEF (def_stmt, i);
if (TREE_CODE (arg) == SSA_NAME
&& walk_use_def_chains_1 (arg, fn, data, visited))
return true;
if ((*fn) (arg, def_stmt, data))
return true;
}
}
return false;
}
void
walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data)
{
tree def_stmt;
#if defined ENABLE_CHECKING
if (TREE_CODE (var) != SSA_NAME)
abort ();
#endif
def_stmt = SSA_NAME_DEF_STMT (var);
if (TREE_CODE (def_stmt) != PHI_NODE)
(*fn) (var, def_stmt, data);
else
{
bitmap visited = BITMAP_XMALLOC ();
walk_use_def_chains_1 (var, fn, data, visited);
BITMAP_XFREE (visited);
}
}
static void
replace_immediate_uses (tree var, tree repl)
{
use_optype uses;
vuse_optype vuses;
vdef_optype vdefs;
int i, j, n;
dataflow_t df;
tree stmt;
stmt_ann_t ann;
df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
n = num_immediate_uses (df);
for (i = 0; i < n; i++)
{
stmt = immediate_use (df, i);
ann = stmt_ann (stmt);
if (TREE_CODE (stmt) == PHI_NODE)
{
for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
if (PHI_ARG_DEF (stmt, j) == var)
{
PHI_ARG_DEF (stmt, j) = repl;
if (TREE_CODE (repl) == SSA_NAME
&& PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
}
continue;
}
get_stmt_operands (stmt);
if (is_gimple_reg (SSA_NAME_VAR (var)))
{
uses = USE_OPS (ann);
for (j = 0; j < (int) NUM_USES (uses); j++)
if (USE_OP (uses, j) == var)
propagate_value (USE_OP_PTR (uses, j), repl);
}
else
{
vuses = VUSE_OPS (ann);
for (j = 0; j < (int) NUM_VUSES (vuses); j++)
if (VUSE_OP (vuses, j) == var)
propagate_value (VUSE_OP_PTR (vuses, j), repl);
vdefs = VDEF_OPS (ann);
for (j = 0; j < (int) NUM_VDEFS (vdefs); j++)
if (VDEF_OP (vdefs, j) == var)
propagate_value (VDEF_OP_PTR (vdefs, j), repl);
}
modify_stmt (stmt);
if (POINTER_TYPE_P (TREE_TYPE (repl)))
mark_new_vars_to_rename (stmt, vars_to_rename);
}
}
static tree
get_eq_name (tree *eq_to, tree var)
{
unsigned ver;
tree val = var;
while (TREE_CODE (val) == SSA_NAME)
{
ver = SSA_NAME_VERSION (val);
if (!eq_to[ver])
break;
val = eq_to[ver];
}
while (TREE_CODE (var) == SSA_NAME)
{
ver = SSA_NAME_VERSION (var);
if (!eq_to[ver])
break;
var = eq_to[ver];
eq_to[ver] = val;
}
return val;
}
static void
check_phi_redundancy (tree phi, tree *eq_to)
{
tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
unsigned i, ver = SSA_NAME_VERSION (res), n;
dataflow_t df;
if (PHI_NUM_ARGS (phi) > 16)
return;
for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
{
def = PHI_ARG_DEF (phi, i);
switch (TREE_CODE (def))
{
case SSA_NAME:
def = get_eq_name (eq_to, def);
if (def == res)
continue;
break;
case REAL_CST:
case COMPLEX_CST:
break;
case INTEGER_CST:
if (TREE_CODE (TREE_TYPE (def)) != POINTER_TYPE)
break;
default:
return;
}
if (val
&& !operand_equal_p (val, def, 0))
return;
val = def;
}
if (!val)
abort ();
if (get_eq_name (eq_to, res) == val)
return;
if (!may_propagate_copy (res, val))
return;
eq_to[ver] = val;
df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
n = num_immediate_uses (df);
for (i = 0; i < n; i++)
{
stmt = immediate_use (df, i);
if (TREE_CODE (stmt) == PHI_NODE)
check_phi_redundancy (stmt, eq_to);
}
}
void
kill_redundant_phi_nodes (void)
{
tree *eq_to, *ssa_names;
unsigned i;
basic_block bb;
tree phi, var, repl, stmt;
eq_to = xcalloc (highest_ssa_version, sizeof (tree));
ssa_names = xcalloc (highest_ssa_version, sizeof (tree));
compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
var = PHI_RESULT (phi);
ssa_names[SSA_NAME_VERSION (var)] = var;
check_phi_redundancy (phi, eq_to);
}
}
for (i = 0; i < highest_ssa_version; i++)
{
if (!ssa_names[i])
continue;
repl = get_eq_name (eq_to, ssa_names[i]);
if (repl != ssa_names[i])
replace_immediate_uses (ssa_names[i], repl);
}
for (i = 0; i < highest_ssa_version; i++)
{
if (!ssa_names[i])
continue;
repl = get_eq_name (eq_to, ssa_names[i]);
if (repl != ssa_names[i])
{
stmt = SSA_NAME_DEF_STMT (ssa_names[i]);
remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
}
}
free_df ();
free (eq_to);
free (ssa_names);
}
struct tree_opt_pass pass_redundant_phi =
{
"redphi",
NULL,
kill_redundant_phi_nodes,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func | TODO_rename_vars
| TODO_ggc_collect | TODO_verify_ssa
};
static void
warn_uninit (tree t, const char *msgid, location_t *locus)
{
tree var = SSA_NAME_VAR (t);
tree def = SSA_NAME_DEF_STMT (t);
if (!IS_EMPTY_STMT (def))
return;
if (TREE_CODE (var) == PARM_DECL)
return;
if (DECL_HARD_REGISTER (var))
return;
if (TREE_NO_WARNING (var))
return;
if (!locus)
locus = &DECL_SOURCE_LOCATION (var);
warning (msgid, locus, var);
TREE_NO_WARNING (var) = 1;
}
static tree
warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
{
location_t *locus = data;
tree t = *tp;
if (TREE_CODE (t) == SSA_NAME)
{
warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
*walk_subtrees = 0;
}
else if (DECL_P (t) || TYPE_P (t))
*walk_subtrees = 0;
return NULL_TREE;
}
static void
warn_uninitialized_phi (tree phi)
{
int i, n = PHI_NUM_ARGS (phi);
if (!is_gimple_reg (PHI_RESULT (phi)))
return;
for (i = 0; i < n; ++i)
{
tree op = PHI_ARG_DEF (phi, i);
if (TREE_CODE (op) == SSA_NAME)
warn_uninit (op, "%H'%D' may be used uninitialized in this function",
NULL);
}
}
static void
execute_early_warn_uninitialized (void)
{
block_stmt_iterator bsi;
basic_block bb;
FOR_EACH_BB (bb)
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
EXPR_LOCUS (bsi_stmt (bsi)), NULL);
}
static void
execute_late_warn_uninitialized (void)
{
basic_block bb;
tree phi;
execute_early_warn_uninitialized ();
FOR_EACH_BB (bb)
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
warn_uninitialized_phi (phi);
}
static bool
gate_warn_uninitialized (void)
{
return warn_uninitialized != 0;
}
struct tree_opt_pass pass_early_warn_uninitialized =
{
NULL,
gate_warn_uninitialized,
execute_early_warn_uninitialized,
NULL,
NULL,
0,
0,
PROP_ssa,
0,
0,
0,
0
};
struct tree_opt_pass pass_late_warn_uninitialized =
{
NULL,
gate_warn_uninitialized,
execute_late_warn_uninitialized,
NULL,
NULL,
0,
0,
PROP_ssa,
0,
0,
0,
0
};