#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.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 "flags.h"
#include "function.h"
#include "expr.h"
#include "ggc.h"
#include "langhooks.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-pass.h"
#include "toplev.h"
#include "except.h"
#include "cfgloop.h"
static const int initial_cfg_capacity = 20;
static GTY(()) varray_type label_to_block_map;
struct cfg_stats_d
{
long num_merged_labels;
};
static struct cfg_stats_d cfg_stats;
static bool found_computed_goto;
static basic_block create_bb (void *, void *, basic_block);
static void create_block_annotation (basic_block);
static void free_blocks_annotations (void);
static void clear_blocks_annotations (void);
static void make_blocks (tree);
static void factor_computed_gotos (void);
static void make_edges (void);
static void make_ctrl_stmt_edges (basic_block);
static void make_exit_edges (basic_block);
static void make_cond_expr_edges (basic_block);
static void make_switch_expr_edges (basic_block);
static void make_goto_expr_edges (basic_block);
static edge tree_redirect_edge_and_branch (edge, basic_block);
static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
static void split_critical_edges (void);
static inline bool stmt_starts_bb_p (tree, tree);
static int tree_verify_flow_info (void);
static void tree_make_forwarder_block (edge);
static bool thread_jumps (void);
static bool tree_forwarder_block_p (basic_block);
static void bsi_commit_edge_inserts_1 (edge e);
static void tree_cfg2vcg (FILE *);
static void tree_merge_blocks (basic_block, basic_block);
static bool tree_can_merge_blocks_p (basic_block, basic_block);
static void remove_bb (basic_block);
static void cleanup_dead_labels (void);
static bool cleanup_control_flow (void);
static bool cleanup_control_expr_graph (basic_block, block_stmt_iterator);
static edge find_taken_edge_cond_expr (basic_block, tree);
static edge find_taken_edge_switch_expr (basic_block, tree);
static tree find_case_label_for_value (tree, tree);
static bool phi_alternatives_equal (basic_block, edge, edge);
static void
build_tree_cfg (tree *tp)
{
tree_register_cfg_hooks ();
alloc_rbi_pool ();
init_flow ();
n_basic_blocks = 0;
last_basic_block = 0;
VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
VARRAY_BB_INIT (label_to_block_map, initial_cfg_capacity,
"label to block map");
ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
found_computed_goto = 0;
make_blocks (*tp);
if (found_computed_goto)
factor_computed_gotos ();
if (n_basic_blocks == 0)
create_empty_bb (ENTRY_BLOCK_PTR);
create_block_annotation (ENTRY_BLOCK_PTR);
create_block_annotation (EXIT_BLOCK_PTR);
VARRAY_GROW (basic_block_info, n_basic_blocks);
make_edges ();
{
int local_dump_flags;
FILE *dump_file = dump_begin (TDI_vcg, &local_dump_flags);
if (dump_file)
{
tree_cfg2vcg (dump_file);
dump_end (TDI_vcg, dump_file);
}
}
if (dump_file)
dump_tree_cfg (dump_file, dump_flags);
}
static void
execute_build_cfg (void)
{
build_tree_cfg (&DECL_SAVED_TREE (current_function_decl));
}
struct tree_opt_pass pass_build_cfg =
{
"cfg",
NULL,
execute_build_cfg,
NULL,
NULL,
0,
TV_TREE_CFG,
PROP_gimple_leh,
PROP_cfg,
0,
0,
TODO_verify_stmts
};
static void
factor_computed_gotos (void)
{
basic_block bb;
tree factored_label_decl = NULL;
tree var = NULL;
tree factored_computed_goto_label = NULL;
tree factored_computed_goto = NULL;
FOR_EACH_BB (bb)
{
block_stmt_iterator bsi = bsi_last (bb);
tree last;
if (bsi_end_p (bsi))
continue;
last = bsi_stmt (bsi);
if (last == factored_computed_goto)
continue;
if (computed_goto_p (last))
{
tree assignment;
if (! factored_computed_goto)
{
basic_block new_bb = create_empty_bb (bb);
block_stmt_iterator new_bsi = bsi_start (new_bb);
var = create_tmp_var (ptr_type_node, "gotovar");
factored_label_decl = create_artificial_label ();
factored_computed_goto_label
= build1 (LABEL_EXPR, void_type_node, factored_label_decl);
bsi_insert_after (&new_bsi, factored_computed_goto_label,
BSI_NEW_STMT);
factored_computed_goto = build1 (GOTO_EXPR, void_type_node, var);
bsi_insert_after (&new_bsi, factored_computed_goto,
BSI_NEW_STMT);
}
assignment = build (MODIFY_EXPR, ptr_type_node,
var, GOTO_DESTINATION (last));
bsi_insert_before (&bsi, assignment, BSI_SAME_STMT);
GOTO_DESTINATION (last) = factored_label_decl;
}
}
}
static void
create_block_annotation (basic_block bb)
{
if (bb->tree_annotations)
abort ();
bb->tree_annotations = ggc_alloc_cleared (sizeof (struct bb_ann_d));
}
static void free_blocks_annotations (void)
{
clear_blocks_annotations ();
}
static void
clear_blocks_annotations (void)
{
basic_block bb;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
bb->tree_annotations = NULL;
}
static void
make_blocks (tree stmt_list)
{
tree_stmt_iterator i = tsi_start (stmt_list);
tree stmt = NULL;
bool start_new_block = true;
bool first_stmt_of_list = true;
basic_block bb = ENTRY_BLOCK_PTR;
while (!tsi_end_p (i))
{
tree prev_stmt;
prev_stmt = stmt;
stmt = tsi_stmt (i);
if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
{
if (!first_stmt_of_list)
stmt_list = tsi_split_statement_list_before (&i);
bb = create_basic_block (stmt_list, NULL, bb);
start_new_block = false;
}
set_bb_for_stmt (stmt, bb);
if (computed_goto_p (stmt))
found_computed_goto = true;
if (stmt_ends_bb_p (stmt))
start_new_block = true;
tsi_next (&i);
first_stmt_of_list = false;
}
}
static basic_block
create_bb (void *h, void *e, basic_block after)
{
basic_block bb;
if (e)
abort ();
bb = alloc_block ();
memset (bb, 0, sizeof (*bb));
bb->index = last_basic_block;
bb->flags = BB_NEW;
bb->stmt_list = h ? h : alloc_stmt_list ();
link_block (bb, after);
if ((size_t) last_basic_block == VARRAY_SIZE (basic_block_info))
{
size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
VARRAY_GROW (basic_block_info, new_size);
}
BASIC_BLOCK (last_basic_block) = bb;
create_block_annotation (bb);
n_basic_blocks++;
last_basic_block++;
initialize_bb_rbi (bb);
return bb;
}
static void
make_edges (void)
{
basic_block bb;
edge e;
make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
FOR_EACH_BB (bb)
{
tree first = first_stmt (bb);
tree last = last_stmt (bb);
if (first)
{
if (is_ctrl_stmt (last))
make_ctrl_stmt_edges (bb);
if (is_ctrl_altering_stmt (last))
make_exit_edges (bb);
}
if (bb->succ == NULL)
make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
}
for (e = EXIT_BLOCK_PTR->prev_bb->succ; e; e = e->succ_next)
if (e->flags & EDGE_FALLTHRU)
break;
if (e && e->dest == EXIT_BLOCK_PTR)
{
block_stmt_iterator bsi;
basic_block ret_bb = EXIT_BLOCK_PTR->prev_bb;
tree x;
if (e != ret_bb->succ || e->succ_next)
{
ret_bb = split_edge (e);
e = ret_bb->succ;
}
e->flags &= ~EDGE_FALLTHRU;
x = build (RETURN_EXPR, void_type_node, NULL_TREE);
bsi = bsi_last (ret_bb);
bsi_insert_after (&bsi, x, BSI_NEW_STMT);
}
remove_fake_edges ();
cleanup_dead_labels ();
cleanup_tree_cfg ();
}
static void
make_ctrl_stmt_edges (basic_block bb)
{
tree last = last_stmt (bb);
tree first = first_stmt (bb);
#if defined ENABLE_CHECKING
if (last == NULL_TREE)
abort();
#endif
if (TREE_CODE (first) == LABEL_EXPR
&& DECL_NONLOCAL (LABEL_EXPR_LABEL (first)))
make_edge (ENTRY_BLOCK_PTR, bb, EDGE_ABNORMAL);
switch (TREE_CODE (last))
{
case GOTO_EXPR:
make_goto_expr_edges (bb);
break;
case RETURN_EXPR:
make_edge (bb, EXIT_BLOCK_PTR, 0);
break;
case COND_EXPR:
make_cond_expr_edges (bb);
break;
case SWITCH_EXPR:
make_switch_expr_edges (bb);
break;
case RESX_EXPR:
make_eh_edges (last);
if (bb->succ == NULL)
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
break;
default:
abort ();
}
}
static void
make_exit_edges (basic_block bb)
{
tree last = last_stmt (bb);
if (last == NULL_TREE)
abort ();
switch (TREE_CODE (last))
{
case CALL_EXPR:
if (TREE_SIDE_EFFECTS (last)
&& current_function_has_nonlocal_label)
make_goto_expr_edges (bb);
make_eh_edges (last);
if (call_expr_flags (last) & (ECF_NORETURN | ECF_LONGJMP))
{
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
return;
}
make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
break;
case MODIFY_EXPR:
if (TREE_CODE (TREE_OPERAND (last, 1)) == CALL_EXPR
&& TREE_SIDE_EFFECTS (TREE_OPERAND (last, 1))
&& current_function_has_nonlocal_label)
make_goto_expr_edges (bb);
make_eh_edges (last);
make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
break;
default:
abort ();
}
}
static void
make_cond_expr_edges (basic_block bb)
{
tree entry = last_stmt (bb);
basic_block then_bb, else_bb;
tree then_label, else_label;
#if defined ENABLE_CHECKING
if (entry == NULL_TREE || TREE_CODE (entry) != COND_EXPR)
abort ();
#endif
then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
then_bb = label_to_block (then_label);
else_bb = label_to_block (else_label);
make_edge (bb, then_bb, EDGE_TRUE_VALUE);
make_edge (bb, else_bb, EDGE_FALSE_VALUE);
}
static void
make_switch_expr_edges (basic_block bb)
{
tree entry = last_stmt (bb);
size_t i, n;
tree vec;
vec = SWITCH_LABELS (entry);
n = TREE_VEC_LENGTH (vec);
for (i = 0; i < n; ++i)
{
tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
basic_block label_bb = label_to_block (lab);
make_edge (bb, label_bb, 0);
}
}
basic_block
label_to_block (tree dest)
{
return VARRAY_BB (label_to_block_map, LABEL_DECL_UID (dest));
}
static void
make_goto_expr_edges (basic_block bb)
{
tree goto_t, dest;
basic_block target_bb;
int for_call;
block_stmt_iterator last = bsi_last (bb);
goto_t = bsi_stmt (last);
if (TREE_CODE (goto_t) != GOTO_EXPR)
{
dest = error_mark_node;
for_call = 1;
}
else
{
dest = GOTO_DESTINATION (goto_t);
for_call = 0;
if (simple_goto_p (goto_t))
{
make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
bsi_remove (&last);
return;
}
if (TREE_CODE (dest) == LABEL_DECL)
return;
}
FOR_EACH_BB (target_bb)
{
block_stmt_iterator bsi;
for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree target = bsi_stmt (bsi);
if (TREE_CODE (target) != LABEL_EXPR)
break;
if (
(FORCED_LABEL (LABEL_EXPR_LABEL (target)) && for_call == 0)
|| (DECL_NONLOCAL (LABEL_EXPR_LABEL (target)) && for_call == 1))
{
make_edge (bb, target_bb, EDGE_ABNORMAL);
break;
}
}
}
if (!for_call && !bb->succ)
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
void
cleanup_tree_cfg (void)
{
bool something_changed = true;
timevar_push (TV_TREE_CLEANUP_CFG);
while (something_changed)
{
something_changed = cleanup_control_flow ();
something_changed |= thread_jumps ();
something_changed |= delete_unreachable_blocks ();
}
merge_seq_blocks ();
compact_blocks ();
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
timevar_pop (TV_TREE_CLEANUP_CFG);
}
static void
cleanup_dead_labels (void)
{
basic_block bb;
tree *label_for_bb = xcalloc (last_basic_block, sizeof (tree));
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
{
tree label, stmt = bsi_stmt (i);
if (TREE_CODE (stmt) != LABEL_EXPR)
break;
label = LABEL_EXPR_LABEL (stmt);
if (! label_for_bb[bb->index])
{
label_for_bb[bb->index] = label;
continue;
}
if (! DECL_ARTIFICIAL (label)
&& DECL_ARTIFICIAL (label_for_bb[bb->index]))
{
label_for_bb[bb->index] = label;
break;
}
}
}
FOR_EACH_BB (bb)
{
tree stmt = last_stmt (bb);
if (!stmt)
continue;
switch (TREE_CODE (stmt))
{
case COND_EXPR:
{
tree true_branch, false_branch;
basic_block true_bb, false_bb;
true_branch = COND_EXPR_THEN (stmt);
false_branch = COND_EXPR_ELSE (stmt);
true_bb = label_to_block (GOTO_DESTINATION (true_branch));
false_bb = label_to_block (GOTO_DESTINATION (false_branch));
GOTO_DESTINATION (true_branch) = label_for_bb[true_bb->index];
GOTO_DESTINATION (false_branch) = label_for_bb[false_bb->index];
break;
}
case SWITCH_EXPR:
{
size_t i;
tree vec = SWITCH_LABELS (stmt);
size_t n = TREE_VEC_LENGTH (vec);
for (i = 0; i < n; ++i)
{
tree label = CASE_LABEL (TREE_VEC_ELT (vec, i));
CASE_LABEL (TREE_VEC_ELT (vec, i)) =
label_for_bb[label_to_block (label)->index];
}
break;
}
default:
break;
}
}
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
tree label_for_this_bb = label_for_bb[bb->index];
if (! label_for_this_bb)
continue;
for (i = bsi_start (bb); !bsi_end_p (i); )
{
tree label, stmt = bsi_stmt (i);
if (TREE_CODE (stmt) != LABEL_EXPR)
break;
label = LABEL_EXPR_LABEL (stmt);
if (label == label_for_this_bb
|| ! DECL_ARTIFICIAL (label)
|| DECL_NONLOCAL (label))
bsi_next (&i);
else
bsi_remove (&i);
}
}
free (label_for_bb);
}
static bool
tree_can_merge_blocks_p (basic_block a, basic_block b)
{
tree stmt;
block_stmt_iterator bsi;
if (!a->succ
|| a->succ->succ_next)
return false;
if (a->succ->flags & EDGE_ABNORMAL)
return false;
if (a->succ->dest != b)
return false;
if (b == EXIT_BLOCK_PTR)
return false;
if (b->pred->pred_next)
return false;
stmt = last_stmt (a);
if (stmt && stmt_ends_bb_p (stmt))
return false;
if (stmt && TREE_CODE (stmt) == LABEL_EXPR
&& DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
return false;
if (phi_nodes (b))
return false;
for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) != LABEL_EXPR)
break;
if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
return false;
}
return true;
}
static void
tree_merge_blocks (basic_block a, basic_block b)
{
block_stmt_iterator bsi;
tree_stmt_iterator last;
if (dump_file)
fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
move_block_after (b, a);
if (!(a->succ->flags & EDGE_FALLTHRU))
abort ();
if (last_stmt (a)
&& stmt_ends_bb_p (last_stmt (a)))
abort ();
for (bsi = bsi_start (b); !bsi_end_p (bsi);)
{
if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
bsi_remove (&bsi);
else
{
set_bb_for_stmt (bsi_stmt (bsi), a);
bsi_next (&bsi);
}
}
last = tsi_last (a->stmt_list);
tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
b->stmt_list = NULL;
}
struct rus_data
{
tree *last_goto;
bool repeat;
bool may_throw;
bool may_branch;
bool has_label;
};
static void remove_useless_stmts_1 (tree *, struct rus_data *);
static bool
remove_useless_stmts_warn_notreached (tree stmt)
{
if (EXPR_LOCUS (stmt))
{
warning ("%Hwill never be executed", EXPR_LOCUS (stmt));
return true;
}
switch (TREE_CODE (stmt))
{
case STATEMENT_LIST:
{
tree_stmt_iterator i;
for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
return true;
}
break;
case COND_EXPR:
if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
return true;
if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
return true;
if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
return true;
break;
case TRY_FINALLY_EXPR:
case TRY_CATCH_EXPR:
if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
return true;
if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
return true;
break;
case CATCH_EXPR:
return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
case EH_FILTER_EXPR:
return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
case BIND_EXPR:
return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
default:
break;
}
return false;
}
static void
remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
{
tree then_clause, else_clause, cond;
bool save_has_label, then_has_label, else_has_label;
save_has_label = data->has_label;
data->has_label = false;
data->last_goto = NULL;
remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
then_has_label = data->has_label;
data->has_label = false;
data->last_goto = NULL;
remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
else_has_label = data->has_label;
data->has_label = save_has_label | then_has_label | else_has_label;
fold_stmt (stmt_p);
then_clause = COND_EXPR_THEN (*stmt_p);
else_clause = COND_EXPR_ELSE (*stmt_p);
cond = COND_EXPR_COND (*stmt_p);
if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
{
*stmt_p = build_empty_stmt ();
data->repeat = true;
}
else if (integer_nonzerop (cond) && !else_has_label)
{
if (warn_notreached)
remove_useless_stmts_warn_notreached (else_clause);
*stmt_p = then_clause;
data->repeat = true;
}
else if (integer_zerop (cond) && !then_has_label)
{
if (warn_notreached)
remove_useless_stmts_warn_notreached (then_clause);
*stmt_p = else_clause;
data->repeat = true;
}
else
{
tree then_stmt = expr_only (then_clause);
tree else_stmt = expr_only (else_clause);
if (then_stmt && else_stmt
&& TREE_CODE (then_stmt) == GOTO_EXPR
&& TREE_CODE (else_stmt) == GOTO_EXPR
&& (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
{
*stmt_p = then_stmt;
data->repeat = true;
}
else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
{
if (else_stmt
&& TREE_CODE (else_stmt) == MODIFY_EXPR
&& TREE_OPERAND (else_stmt, 0) == cond
&& integer_zerop (TREE_OPERAND (else_stmt, 1)))
COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
}
else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
&& (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
|| TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
&& TREE_CONSTANT (TREE_OPERAND (cond, 1)))
{
tree stmt = (TREE_CODE (cond) == EQ_EXPR
? then_stmt : else_stmt);
tree *location = (TREE_CODE (cond) == EQ_EXPR
? &COND_EXPR_THEN (*stmt_p)
: &COND_EXPR_ELSE (*stmt_p));
if (stmt
&& TREE_CODE (stmt) == MODIFY_EXPR
&& TREE_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
&& TREE_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
*location = alloc_stmt_list ();
}
}
data->last_goto = NULL;
}
static void
remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
{
bool save_may_branch, save_may_throw;
bool this_may_branch, this_may_throw;
save_may_branch = data->may_branch;
save_may_throw = data->may_throw;
data->may_branch = false;
data->may_throw = false;
data->last_goto = NULL;
remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
this_may_branch = data->may_branch;
this_may_throw = data->may_throw;
data->may_branch |= save_may_branch;
data->may_throw |= save_may_throw;
data->last_goto = NULL;
remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
{
*stmt_p = TREE_OPERAND (*stmt_p, 1);
data->repeat = true;
}
else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
{
*stmt_p = TREE_OPERAND (*stmt_p, 0);
data->repeat = true;
}
else if (!this_may_branch && !this_may_throw)
{
tree stmt = *stmt_p;
*stmt_p = TREE_OPERAND (stmt, 0);
append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
data->repeat = true;
}
}
static void
remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
{
bool save_may_throw, this_may_throw;
tree_stmt_iterator i;
tree stmt;
save_may_throw = data->may_throw;
data->may_throw = false;
data->last_goto = NULL;
remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
this_may_throw = data->may_throw;
data->may_throw = save_may_throw;
if (!this_may_throw)
{
if (warn_notreached)
remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
*stmt_p = TREE_OPERAND (*stmt_p, 0);
data->repeat = true;
return;
}
this_may_throw = true;
i = tsi_start (TREE_OPERAND (*stmt_p, 1));
stmt = tsi_stmt (i);
data->last_goto = NULL;
switch (TREE_CODE (stmt))
{
case CATCH_EXPR:
for (; !tsi_end_p (i); tsi_next (&i))
{
stmt = tsi_stmt (i);
if (CATCH_TYPES (stmt) == NULL)
this_may_throw = false;
data->last_goto = NULL;
remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
}
break;
case EH_FILTER_EXPR:
if (EH_FILTER_MUST_NOT_THROW (stmt))
this_may_throw = false;
else if (EH_FILTER_TYPES (stmt) == NULL)
this_may_throw = false;
remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
break;
default:
remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
{
*stmt_p = TREE_OPERAND (*stmt_p, 0);
data->repeat = true;
}
break;
}
data->may_throw |= this_may_throw;
}
static void
remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
{
tree block;
remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
block = BIND_EXPR_BLOCK (*stmt_p);
if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
&& *stmt_p != DECL_SAVED_TREE (current_function_decl)
&& (! block
|| ! BLOCK_ABSTRACT_ORIGIN (block)
|| (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
!= FUNCTION_DECL)))
{
*stmt_p = BIND_EXPR_BODY (*stmt_p);
data->repeat = true;
}
}
static void
remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
{
tree dest = GOTO_DESTINATION (*stmt_p);
data->may_branch = true;
data->last_goto = NULL;
if (TREE_CODE (dest) == LABEL_DECL)
data->last_goto = stmt_p;
}
static void
remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
{
tree label = LABEL_EXPR_LABEL (*stmt_p);
data->has_label = true;
if (DECL_NONLOCAL (label))
data->last_goto = NULL;
else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
{
*data->last_goto = build_empty_stmt ();
data->repeat = true;
}
}
static void
update_call_expr_flags (tree call)
{
tree decl = get_callee_fndecl (call);
if (!decl)
return;
if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
TREE_SIDE_EFFECTS (call) = 0;
if (TREE_NOTHROW (decl))
TREE_NOTHROW (call) = 1;
}
void
notice_special_calls (tree t)
{
int flags = call_expr_flags (t);
if (flags & ECF_MAY_BE_ALLOCA)
current_function_calls_alloca = true;
if (flags & ECF_RETURNS_TWICE)
current_function_calls_setjmp = true;
}
void
clear_special_calls (void)
{
current_function_calls_alloca = false;
current_function_calls_setjmp = false;
}
static void
remove_useless_stmts_1 (tree *tp, struct rus_data *data)
{
tree t = *tp;
switch (TREE_CODE (t))
{
case COND_EXPR:
remove_useless_stmts_cond (tp, data);
break;
case TRY_FINALLY_EXPR:
remove_useless_stmts_tf (tp, data);
break;
case TRY_CATCH_EXPR:
remove_useless_stmts_tc (tp, data);
break;
case BIND_EXPR:
remove_useless_stmts_bind (tp, data);
break;
case GOTO_EXPR:
remove_useless_stmts_goto (tp, data);
break;
case LABEL_EXPR:
remove_useless_stmts_label (tp, data);
break;
case RETURN_EXPR:
fold_stmt (tp);
data->last_goto = NULL;
data->may_branch = true;
break;
case CALL_EXPR:
fold_stmt (tp);
data->last_goto = NULL;
notice_special_calls (t);
update_call_expr_flags (t);
if (tree_could_throw_p (t))
data->may_throw = true;
break;
case MODIFY_EXPR:
data->last_goto = NULL;
fold_stmt (tp);
if (TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR)
{
update_call_expr_flags (TREE_OPERAND (t, 1));
notice_special_calls (TREE_OPERAND (t, 1));
}
if (tree_could_throw_p (t))
data->may_throw = true;
break;
case STATEMENT_LIST:
{
tree_stmt_iterator i = tsi_start (t);
while (!tsi_end_p (i))
{
t = tsi_stmt (i);
if (IS_EMPTY_STMT (t))
{
tsi_delink (&i);
continue;
}
remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
t = tsi_stmt (i);
if (TREE_CODE (t) == STATEMENT_LIST)
{
tsi_link_before (&i, t, TSI_SAME_STMT);
tsi_delink (&i);
}
else
tsi_next (&i);
}
}
break;
case SWITCH_EXPR:
fold_stmt (tp);
data->last_goto = NULL;
break;
default:
data->last_goto = NULL;
break;
}
}
static void
remove_useless_stmts (void)
{
struct rus_data data;
clear_special_calls ();
do
{
memset (&data, 0, sizeof (data));
remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
}
while (data.repeat);
}
struct tree_opt_pass pass_remove_useless_stmts =
{
"useless",
NULL,
remove_useless_stmts,
NULL,
NULL,
0,
0,
PROP_gimple_any,
0,
0,
0,
TODO_dump_func
};
static void
cfg_remove_useless_stmts_bb (basic_block bb)
{
block_stmt_iterator bsi;
tree stmt = NULL_TREE;
tree cond, var = NULL_TREE, val = NULL_TREE;
struct var_ann_d *ann;
if (!bb->pred
|| bb->pred->pred_next
|| !(bb->pred->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
return;
cond = COND_EXPR_COND (last_stmt (bb->pred->src));
if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
{
var = cond;
val = (bb->pred->flags & EDGE_FALSE_VALUE
? boolean_false_node : boolean_true_node);
}
else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
&& (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
|| TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL))
{
var = TREE_OPERAND (cond, 0);
val = (bb->pred->flags & EDGE_FALSE_VALUE
? boolean_true_node : boolean_false_node);
}
else
{
if (bb->pred->flags & EDGE_FALSE_VALUE)
cond = invert_truthvalue (cond);
if (TREE_CODE (cond) == EQ_EXPR
&& (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
|| TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
&& (TREE_CODE (TREE_OPERAND (cond, 1)) == VAR_DECL
|| TREE_CODE (TREE_OPERAND (cond, 1)) == PARM_DECL
|| TREE_CONSTANT (TREE_OPERAND (cond, 1))))
{
var = TREE_OPERAND (cond, 0);
val = TREE_OPERAND (cond, 1);
}
else
return;
}
ann = var_ann (var);
if (!ann
|| ann->may_aliases
|| TREE_ADDRESSABLE (var))
return;
if (! TREE_CONSTANT (val))
{
ann = var_ann (val);
if (!ann
|| ann->may_aliases
|| TREE_ADDRESSABLE (val))
return;
}
if (FLOAT_TYPE_P (TREE_TYPE (var)))
return;
for (bsi = bsi_start (bb); !bsi_end_p (bsi);)
{
stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) == MODIFY_EXPR
&& TREE_OPERAND (stmt, 0) == var
&& operand_equal_p (val, TREE_OPERAND (stmt, 1), 0))
{
bsi_remove (&bsi);
continue;
}
if (TREE_CODE (stmt) == ASM_EXPR
|| TREE_CODE (stmt) == VA_ARG_EXPR
|| (TREE_CODE (stmt) == MODIFY_EXPR
&& (TREE_OPERAND (stmt, 0) == var
|| TREE_OPERAND (stmt, 0) == val
|| TREE_CODE (TREE_OPERAND (stmt, 1)) == VA_ARG_EXPR)))
return;
bsi_next (&bsi);
}
}
void
cfg_remove_useless_stmts (void)
{
basic_block bb;
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
FOR_EACH_BB (bb)
{
cfg_remove_useless_stmts_bb (bb);
}
}
static void
remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
{
tree phi;
phi = phi_nodes (bb);
while (phi)
{
tree next = TREE_CHAIN (phi);
remove_phi_node (phi, NULL_TREE, bb);
phi = next;
}
while (bb->succ != NULL)
ssa_remove_edge (bb->succ);
}
static void
remove_bb (basic_block bb)
{
block_stmt_iterator i;
location_t *loc = NULL;
if (dump_file)
{
fprintf (dump_file, "Removing basic block %d\n", bb->index);
if (dump_flags & TDF_DETAILS)
{
dump_bb (bb, dump_file, 0);
fprintf (dump_file, "\n");
}
}
for (i = bsi_start (bb); !bsi_end_p (i); bsi_remove (&i))
{
tree stmt = bsi_stmt (i);
set_bb_for_stmt (stmt, NULL);
if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_LOCUS (stmt) && !loc)
loc = EXPR_LOCUS (stmt);
}
if (warn_notreached && loc)
warning ("%Hwill never be executed", loc);
remove_phi_nodes_and_edges_for_unreachable_block (bb);
}
edge
tree_block_forwards_to (basic_block bb)
{
block_stmt_iterator bsi;
bb_ann_t ann = bb_ann (bb);
tree stmt;
if (! ann->forwardable)
return NULL;
ann->forwardable = 0;
if (bb == EXIT_BLOCK_PTR
|| bb == ENTRY_BLOCK_PTR
|| !bb->succ
|| bb->succ->succ_next
|| bb->succ->dest == EXIT_BLOCK_PTR
|| (bb->succ->flags & EDGE_ABNORMAL) != 0
|| phi_nodes (bb)
|| phi_nodes (bb->succ->dest))
return NULL;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) != LABEL_EXPR)
break;
}
if (bsi_end_p (bsi))
{
edge dest;
dest = tree_block_forwards_to (bb->succ->dest);
if (!dest)
dest = bb->succ;
ann->forwardable = 1;
return dest;
}
return NULL;
}
static bool
cleanup_control_flow (void)
{
basic_block bb;
block_stmt_iterator bsi;
bool retval = false;
tree stmt;
FOR_EACH_BB (bb)
{
bsi = bsi_last (bb);
if (bsi_end_p (bsi))
continue;
stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) == COND_EXPR
|| TREE_CODE (stmt) == SWITCH_EXPR)
retval |= cleanup_control_expr_graph (bb, bsi);
}
return retval;
}
static bool
cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi)
{
edge taken_edge;
bool retval = false;
tree expr = bsi_stmt (bsi), val;
if (bb->succ->succ_next)
{
edge e, next;
switch (TREE_CODE (expr))
{
case COND_EXPR:
val = COND_EXPR_COND (expr);
break;
case SWITCH_EXPR:
val = SWITCH_COND (expr);
if (TREE_CODE (val) != INTEGER_CST)
return false;
break;
default:
abort ();
}
taken_edge = find_taken_edge (bb, val);
if (!taken_edge)
return false;
for (e = bb->succ; e; e = next)
{
next = e->succ_next;
if (e != taken_edge)
{
taken_edge->probability += e->probability;
taken_edge->count += e->count;
ssa_remove_edge (e);
retval = true;
}
if (taken_edge->probability > REG_BR_PROB_BASE)
taken_edge->probability = REG_BR_PROB_BASE;
}
if (taken_edge->probability > REG_BR_PROB_BASE)
taken_edge->probability = REG_BR_PROB_BASE;
}
else
taken_edge = bb->succ;
bsi_remove (&bsi);
taken_edge->flags = EDGE_FALLTHRU;
if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
dom_computed[CDI_DOMINATORS] = DOM_CONS_OK;
return retval;
}
edge
find_taken_edge (basic_block bb, tree val)
{
tree stmt;
stmt = last_stmt (bb);
#if defined ENABLE_CHECKING
if (stmt == NULL_TREE || !is_ctrl_stmt (stmt))
abort ();
#endif
if (val == NULL || !really_constant_p (val))
return NULL;
if (TREE_CODE (stmt) == COND_EXPR)
return find_taken_edge_cond_expr (bb, val);
if (TREE_CODE (stmt) == SWITCH_EXPR)
return find_taken_edge_switch_expr (bb, val);
return bb->succ;
}
static edge
find_taken_edge_cond_expr (basic_block bb, tree val)
{
edge true_edge, false_edge;
extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
if (true_edge->dest == false_edge->dest)
return true_edge;
if (integer_nonzerop (val))
return true_edge;
else if (integer_zerop (val))
return false_edge;
else
return NULL;
}
static edge
find_taken_edge_switch_expr (basic_block bb, tree val)
{
tree switch_expr, taken_case;
basic_block dest_bb;
edge e;
if (TREE_CODE (val) != INTEGER_CST)
return NULL;
switch_expr = last_stmt (bb);
taken_case = find_case_label_for_value (switch_expr, val);
dest_bb = label_to_block (CASE_LABEL (taken_case));
e = find_edge (bb, dest_bb);
if (!e)
abort ();
return e;
}
static tree
find_case_label_for_value (tree switch_expr, tree val)
{
tree vec = SWITCH_LABELS (switch_expr);
size_t i, n = TREE_VEC_LENGTH (vec);
tree default_case = NULL;
for (i = 0; i < n; ++i)
{
tree t = TREE_VEC_ELT (vec, i);
if (CASE_LOW (t) == NULL)
default_case = t;
else if (CASE_HIGH (t) == NULL)
{
if (tree_int_cst_equal (CASE_LOW (t), val))
return t;
}
else
{
if (tree_int_cst_compare (CASE_LOW (t), val) <= 0
&& tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
return t;
}
}
if (!default_case)
abort ();
return default_case;
}
static bool
phi_alternatives_equal (basic_block dest, edge e1, edge e2)
{
tree phi, val1, val2;
int n1, n2;
for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
{
n1 = phi_arg_from_edge (phi, e1);
n2 = phi_arg_from_edge (phi, e2);
#ifdef ENABLE_CHECKING
if (n1 < 0 || n2 < 0)
abort ();
#endif
val1 = PHI_ARG_DEF (phi, n1);
val2 = PHI_ARG_DEF (phi, n2);
if (!operand_equal_p (val1, val2, 0))
return false;
}
return true;
}
static void
compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done)
{
edge e;
basic_block c;
SET_BIT (done, bb->index);
for (c = first_dom_son (CDI_DOMINATORS, bb);
c;
c = next_dom_son (CDI_DOMINATORS, c))
{
if (! TEST_BIT (done, c->index))
compute_dominance_frontiers_1 (frontiers, c, done);
}
for (e = bb->succ; e; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb)
bitmap_set_bit (frontiers[bb->index], e->dest->index);
}
for (c = first_dom_son (CDI_DOMINATORS, bb);
c;
c = next_dom_son (CDI_DOMINATORS, c))
{
int x;
EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x,
{
if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
bitmap_set_bit (frontiers[bb->index], x);
});
}
}
void
compute_dominance_frontiers (bitmap *frontiers)
{
sbitmap done = sbitmap_alloc (last_basic_block);
timevar_push (TV_DOM_FRONTIERS);
sbitmap_zero (done);
compute_dominance_frontiers_1 (frontiers, ENTRY_BLOCK_PTR->succ->dest, done);
sbitmap_free (done);
timevar_pop (TV_DOM_FRONTIERS);
}
void
tree_dump_bb (basic_block bb, FILE *outf, int indent)
{
dump_generic_bb (outf, bb, indent, TDF_VOPS);
}
void
debug_tree_bb (basic_block bb)
{
dump_bb (bb, stderr, 0);
}
basic_block
debug_tree_bb_n (int n)
{
debug_tree_bb (BASIC_BLOCK (n));
return BASIC_BLOCK (n);
}
void
debug_tree_cfg (int flags)
{
dump_tree_cfg (stderr, flags);
}
void
dump_tree_cfg (FILE *file, int flags)
{
if (flags & TDF_DETAILS)
{
const char *funcname
= lang_hooks.decl_printable_name (current_function_decl, 2);
fputc ('\n', file);
fprintf (file, ";; Function %s\n\n", funcname);
fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
n_basic_blocks, n_edges, last_basic_block);
brief_dump_cfg (file);
fprintf (file, "\n");
}
if (flags & TDF_STATS)
dump_cfg_stats (file);
dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
}
void
dump_cfg_stats (FILE *file)
{
static long max_num_merged_labels = 0;
unsigned long size, total = 0;
long n_edges;
basic_block bb;
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);
fprintf (file, "\nCFG 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 = n_basic_blocks * sizeof (struct basic_block_def);
total += size;
fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks, SCALE (size),
LABEL (size));
n_edges = 0;
FOR_EACH_BB (bb)
{
edge e;
for (e = bb->succ; e; e = e->succ_next)
n_edges++;
}
size = n_edges * sizeof (struct edge_def);
total += size;
fprintf (file, fmt_str_1, "Edges", n_edges, SCALE (size), LABEL (size));
size = n_basic_blocks * sizeof (struct bb_ann_d);
total += size;
fprintf (file, fmt_str_1, "Basic block annotations", n_basic_blocks,
SCALE (size), LABEL (size));
fprintf (file, "---------------------------------------------------------\n");
fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
LABEL (total));
fprintf (file, "---------------------------------------------------------\n");
fprintf (file, "\n");
if (cfg_stats.num_merged_labels > max_num_merged_labels)
max_num_merged_labels = cfg_stats.num_merged_labels;
fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
cfg_stats.num_merged_labels, max_num_merged_labels);
fprintf (file, "\n");
}
void
debug_cfg_stats (void)
{
dump_cfg_stats (stderr);
}
static void
tree_cfg2vcg (FILE *file)
{
edge e;
basic_block bb;
const char *funcname
= lang_hooks.decl_printable_name (current_function_decl, 2);
fprintf (file, "graph: { title: \"%s\"\n", funcname);
fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
{
fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
e->dest->index);
if (e->flags & EDGE_FAKE)
fprintf (file, " linestyle: dotted priority: 10");
else
fprintf (file, " linestyle: solid priority: 100");
fprintf (file, " }\n");
}
fputc ('\n', file);
FOR_EACH_BB (bb)
{
enum tree_code head_code, end_code;
const char *head_name, *end_name;
int head_line = 0;
int end_line = 0;
tree first = first_stmt (bb);
tree last = last_stmt (bb);
if (first)
{
head_code = TREE_CODE (first);
head_name = tree_code_name[head_code];
head_line = get_lineno (first);
}
else
head_name = "no-statement";
if (last)
{
end_code = TREE_CODE (last);
end_name = tree_code_name[end_code];
end_line = get_lineno (last);
}
else
end_name = "no-statement";
fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
bb->index, bb->index, head_name, head_line, end_name,
end_line);
for (e = bb->succ; e; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
else
fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
if (e->flags & EDGE_FAKE)
fprintf (file, " priority: 10 linestyle: dotted");
else
fprintf (file, " priority: 100 linestyle: solid");
fprintf (file, " }\n");
}
if (bb->next_bb != EXIT_BLOCK_PTR)
fputc ('\n', file);
}
fputs ("}\n\n", file);
}
bool
is_ctrl_stmt (tree t)
{
return (TREE_CODE (t) == COND_EXPR
|| TREE_CODE (t) == SWITCH_EXPR
|| TREE_CODE (t) == GOTO_EXPR
|| TREE_CODE (t) == RETURN_EXPR
|| TREE_CODE (t) == RESX_EXPR);
}
bool
is_ctrl_altering_stmt (tree t)
{
tree call = t;
#if defined ENABLE_CHECKING
if (t == NULL)
abort ();
#endif
switch (TREE_CODE (t))
{
case MODIFY_EXPR:
call = TREE_OPERAND (t, 1);
if (TREE_CODE (call) != CALL_EXPR)
break;
case CALL_EXPR:
if (TREE_SIDE_EFFECTS (t)
&& current_function_has_nonlocal_label)
return true;
if (call_expr_flags (call) & (ECF_NORETURN | ECF_LONGJMP))
return true;
break;
default:
return false;
}
return tree_can_throw_internal (t);
}
bool
computed_goto_p (tree t)
{
return (TREE_CODE (t) == GOTO_EXPR
&& TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
}
bool
simple_goto_p (tree expr)
{
return (TREE_CODE (expr) == GOTO_EXPR
&& TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL
&& (decl_function_context (GOTO_DESTINATION (expr))
== current_function_decl));
}
static inline bool
stmt_starts_bb_p (tree t, tree prev_t)
{
enum tree_code code;
if (t == NULL_TREE)
return false;
code = TREE_CODE (t);
if (code == LABEL_EXPR)
{
if (code == LABEL_EXPR
&& (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
|| FORCED_LABEL (LABEL_EXPR_LABEL (t))))
return true;
if (prev_t && TREE_CODE (prev_t) == code)
{
if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
return true;
cfg_stats.num_merged_labels++;
return false;
}
else
return true;
}
return false;
}
bool
stmt_ends_bb_p (tree t)
{
return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
}
void
disband_implicit_edges (void)
{
basic_block bb;
block_stmt_iterator last;
edge e;
tree stmt, label, forward;
FOR_EACH_BB (bb)
{
last = bsi_last (bb);
stmt = last_stmt (bb);
if (stmt && TREE_CODE (stmt) == COND_EXPR)
{
for (e = bb->succ; e; e = e->succ_next)
{
if (e->dest != bb->next_bb)
continue;
if (e->flags & EDGE_TRUE_VALUE)
COND_EXPR_THEN (stmt) = build_empty_stmt ();
else if (e->flags & EDGE_FALSE_VALUE)
COND_EXPR_ELSE (stmt) = build_empty_stmt ();
else
abort ();
e->flags |= EDGE_FALLTHRU;
}
continue;
}
if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
{
if (!bb->succ
|| bb->succ->succ_next
|| bb->succ->dest != EXIT_BLOCK_PTR)
abort ();
if (bb->next_bb == EXIT_BLOCK_PTR
&& !TREE_OPERAND (stmt, 0))
{
bsi_remove (&last);
bb->succ->flags |= EDGE_FALLTHRU;
}
continue;
}
if (stmt && is_ctrl_stmt (stmt))
continue;
for (e = bb->succ; e; e = e->succ_next)
if (e->flags & EDGE_FALLTHRU)
break;
if (!e
|| e->dest == bb->next_bb)
continue;
if (e->dest == EXIT_BLOCK_PTR)
abort ();
label = tree_block_label (e->dest);
forward = last_and_only_stmt (e->dest);
if (forward
&& TREE_CODE (forward) == GOTO_EXPR)
label = GOTO_DESTINATION (forward);
bsi_insert_after (&last,
build1 (GOTO_EXPR, void_type_node, label),
BSI_NEW_STMT);
e->flags &= ~EDGE_FALLTHRU;
}
}
void
delete_tree_cfg (void)
{
if (n_basic_blocks > 0)
free_blocks_annotations ();
free_basic_block_vars ();
basic_block_info = NULL;
label_to_block_map = NULL;
free_rbi_pool ();
}
tree
first_stmt (basic_block bb)
{
block_stmt_iterator i = bsi_start (bb);
return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
}
tree
last_stmt (basic_block bb)
{
block_stmt_iterator b = bsi_last (bb);
return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
}
tree *
last_stmt_ptr (basic_block bb)
{
block_stmt_iterator last = bsi_last (bb);
return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
}
tree
last_and_only_stmt (basic_block bb)
{
block_stmt_iterator i = bsi_last (bb);
tree last, prev;
if (bsi_end_p (i))
return NULL_TREE;
last = bsi_stmt (i);
bsi_prev (&i);
if (bsi_end_p (i))
return last;
prev = bsi_stmt (i);
if (TREE_CODE (prev) == LABEL_EXPR)
return last;
else
return NULL_TREE;
}
void
set_bb_for_stmt (tree t, basic_block bb)
{
if (TREE_CODE (t) == STATEMENT_LIST)
{
tree_stmt_iterator i;
for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
set_bb_for_stmt (tsi_stmt (i), bb);
}
else
{
stmt_ann_t ann = get_stmt_ann (t);
ann->bb = bb;
if (TREE_CODE (t) == LABEL_EXPR)
{
int uid;
t = LABEL_EXPR_LABEL (t);
uid = LABEL_DECL_UID (t);
if (uid == -1)
{
LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
if (VARRAY_SIZE (label_to_block_map) <= (unsigned) uid)
VARRAY_GROW (label_to_block_map, 3 * uid / 2);
}
else
{
#ifdef ENABLE_CHECKING
if (bb && VARRAY_BB (label_to_block_map, uid))
abort ();
#endif
}
VARRAY_BB (label_to_block_map, uid) = bb;
}
}
}
extern block_stmt_iterator
stmt_bsi (tree stmt)
{
block_stmt_iterator bsi;
for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
if (bsi_stmt (bsi) == stmt)
return bsi;
abort ();
}
void
bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
modify_stmt (t);
tsi_link_before (&i->tsi, t, m);
}
void
bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
modify_stmt (t);
tsi_link_after (&i->tsi, t, m);
}
void
bsi_remove (block_stmt_iterator *i)
{
tree t = bsi_stmt (*i);
set_bb_for_stmt (t, NULL);
modify_stmt (t);
tsi_delink (&i->tsi);
}
void
bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
{
tree stmt = bsi_stmt (*from);
bsi_remove (from);
bsi_insert_after (to, stmt, BSI_SAME_STMT);
}
void
bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
{
tree stmt = bsi_stmt (*from);
bsi_remove (from);
bsi_insert_before (to, stmt, BSI_SAME_STMT);
}
void
bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
{
block_stmt_iterator last = bsi_last (bb);
if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
bsi_move_before (from, &last);
else
bsi_move_after (from, &last);
}
void
bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool preserve_eh_info)
{
int eh_region;
tree orig_stmt = bsi_stmt (*bsi);
SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
set_bb_for_stmt (stmt, bsi->bb);
if (preserve_eh_info)
{
eh_region = lookup_stmt_eh_region (orig_stmt);
if (eh_region >= 0)
add_stmt_to_eh_region (stmt, eh_region);
}
*bsi_stmt_ptr (*bsi) = stmt;
modify_stmt (stmt);
}
static bool
tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
basic_block *new_bb)
{
basic_block dest, src;
tree tmp;
dest = e->dest;
restart:
if (dest->pred->pred_next == NULL
&& ! phi_nodes (dest)
&& dest != EXIT_BLOCK_PTR)
{
*bsi = bsi_start (dest);
if (bsi_end_p (*bsi))
return true;
tmp = bsi_stmt (*bsi);
while (TREE_CODE (tmp) == LABEL_EXPR)
{
bsi_next (bsi);
if (bsi_end_p (*bsi))
break;
tmp = bsi_stmt (*bsi);
}
if (bsi_end_p (*bsi))
{
*bsi = bsi_last (dest);
return true;
}
else
return false;
}
src = e->src;
if ((e->flags & EDGE_ABNORMAL) == 0
&& src->succ->succ_next == NULL
&& src != ENTRY_BLOCK_PTR)
{
*bsi = bsi_last (src);
if (bsi_end_p (*bsi))
return true;
tmp = bsi_stmt (*bsi);
if (!stmt_ends_bb_p (tmp))
return true;
}
dest = split_edge (e);
if (new_bb)
*new_bb = dest;
e = dest->pred;
goto restart;
}
void
bsi_commit_edge_inserts (int *new_blocks)
{
basic_block bb;
edge e;
int blocks;
blocks = n_basic_blocks;
bsi_commit_edge_inserts_1 (ENTRY_BLOCK_PTR->succ);
FOR_EACH_BB (bb)
for (e = bb->succ; e; e = e->succ_next)
bsi_commit_edge_inserts_1 (e);
if (new_blocks)
*new_blocks = n_basic_blocks - blocks;
}
static void
bsi_commit_edge_inserts_1 (edge e)
{
if (PENDING_STMT (e))
{
block_stmt_iterator bsi;
tree stmt = PENDING_STMT (e);
PENDING_STMT (e) = NULL_TREE;
if (tree_find_edge_insert_loc (e, &bsi, NULL))
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
else
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
}
}
void
bsi_insert_on_edge (edge e, tree stmt)
{
append_to_statement_list (stmt, &PENDING_STMT (e));
}
basic_block
bsi_insert_on_edge_immediate (edge e, tree stmt)
{
block_stmt_iterator bsi;
basic_block new_bb = NULL;
if (PENDING_STMT (e))
abort ();
if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
else
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
return new_bb;
}
static basic_block
tree_split_edge (edge edge_in)
{
basic_block new_bb, after_bb, dest, src;
edge new_edge, e;
tree phi;
int i, num_elem;
if (edge_in->flags & EDGE_ABNORMAL)
abort ();
src = edge_in->src;
dest = edge_in->dest;
for (e = dest->pred; e; e = e->pred_next)
if (e->src->next_bb == dest)
break;
if (!e)
after_bb = dest->prev_bb;
else
after_bb = edge_in->src;
new_bb = create_empty_bb (after_bb);
new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
{
num_elem = PHI_NUM_ARGS (phi);
for (i = 0; i < num_elem; i++)
if (PHI_ARG_EDGE (phi, i) == edge_in)
{
PHI_ARG_EDGE (phi, i) = new_edge;
break;
}
}
if (!redirect_edge_and_branch (edge_in, new_bb))
abort ();
if (PENDING_STMT (edge_in))
abort ();
return new_bb;
}
static bool
has_label_p (basic_block bb, tree label)
{
block_stmt_iterator bsi;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) != LABEL_EXPR)
return false;
if (LABEL_EXPR_LABEL (stmt) == label)
return true;
}
return false;
}
static tree
verify_expr (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
void *data ATTRIBUTE_UNUSED)
{
tree t = *tp, x;
if (TYPE_P (t))
*walk_subtrees = 0;
switch (TREE_CODE (t))
{
case SSA_NAME:
if (SSA_NAME_IN_FREE_LIST (t))
{
error ("SSA name in freelist but still referenced");
return *tp;
}
break;
case MODIFY_EXPR:
x = TREE_OPERAND (t, 0);
if (TREE_CODE (x) == BIT_FIELD_REF
&& is_gimple_reg (TREE_OPERAND (x, 0)))
{
error ("GIMPLE register modified with BIT_FIELD_REF");
return *tp;
}
break;
case ADDR_EXPR:
x = TREE_OPERAND (t, 0);
while (TREE_CODE (x) == ARRAY_REF
|| TREE_CODE (x) == COMPONENT_REF
|| TREE_CODE (x) == REALPART_EXPR
|| TREE_CODE (x) == IMAGPART_EXPR)
x = TREE_OPERAND (x, 0);
if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
return NULL;
if (!TREE_ADDRESSABLE (x))
{
error ("address taken, but ADDRESSABLE bit not set");
return x;
}
break;
case COND_EXPR:
x = TREE_OPERAND (t, 0);
if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
{
error ("non-boolean used in condition");
return x;
}
break;
case NOP_EXPR:
case CONVERT_EXPR:
case FIX_TRUNC_EXPR:
case FIX_CEIL_EXPR:
case FIX_FLOOR_EXPR:
case FIX_ROUND_EXPR:
case FLOAT_EXPR:
case NEGATE_EXPR:
case ABS_EXPR:
case BIT_NOT_EXPR:
case NON_LVALUE_EXPR:
case TRUTH_NOT_EXPR:
x = TREE_OPERAND (t, 0);
if (TREE_CODE_CLASS (TREE_CODE (x)) != 'c'
&& !is_gimple_val (x))
{
error ("Invalid operand to unary operator");
return x;
}
break;
case REALPART_EXPR:
case IMAGPART_EXPR:
break;
case LT_EXPR:
case LE_EXPR:
case GT_EXPR:
case GE_EXPR:
case EQ_EXPR:
case NE_EXPR:
case UNORDERED_EXPR:
case ORDERED_EXPR:
case UNLT_EXPR:
case UNLE_EXPR:
case UNGT_EXPR:
case UNGE_EXPR:
case UNEQ_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
case MULT_EXPR:
case TRUNC_DIV_EXPR:
case CEIL_DIV_EXPR:
case FLOOR_DIV_EXPR:
case ROUND_DIV_EXPR:
case TRUNC_MOD_EXPR:
case CEIL_MOD_EXPR:
case FLOOR_MOD_EXPR:
case ROUND_MOD_EXPR:
case RDIV_EXPR:
case EXACT_DIV_EXPR:
case MIN_EXPR:
case MAX_EXPR:
case LSHIFT_EXPR:
case RSHIFT_EXPR:
case LROTATE_EXPR:
case RROTATE_EXPR:
case BIT_IOR_EXPR:
case BIT_XOR_EXPR:
case BIT_AND_EXPR:
x = TREE_OPERAND (t, 0);
if (TREE_CODE_CLASS (TREE_CODE (x)) != 'c'
&& !is_gimple_val (x))
{
error ("Invalid operand to binary operator");
return x;
}
x = TREE_OPERAND (t, 1);
if (TREE_CODE_CLASS (TREE_CODE (x)) != 'c'
&& !is_gimple_val (x))
{
error ("Invalid operand to binary operator");
return x;
}
break;
default:
break;
}
return NULL;
}
static bool
verify_stmt (tree stmt)
{
tree addr;
if (!is_gimple_stmt (stmt))
{
error ("Is not a valid GIMPLE statement.");
debug_generic_stmt (stmt);
return true;
}
addr = walk_tree (&stmt, verify_expr, NULL, NULL);
if (addr)
{
debug_generic_stmt (addr);
return true;
}
return false;
}
static bool
tree_node_can_be_shared (tree t)
{
if (TYPE_P (t) || DECL_P (t)
|| TREE_CODE_CLASS (TREE_CODE (t)) == 'c'
|| is_gimple_min_invariant (t)
|| TREE_CODE (t) == SSA_NAME)
return true;
while ((TREE_CODE (t) == ARRAY_REF
&& (TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 1))) == 'c'
|| is_gimple_min_invariant (TREE_OPERAND (t, 1))))
|| (TREE_CODE (t) == COMPONENT_REF
|| TREE_CODE (t) == REALPART_EXPR
|| TREE_CODE (t) == IMAGPART_EXPR))
t = TREE_OPERAND (t, 0);
if (DECL_P (t))
return true;
return false;
}
static tree
verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
{
htab_t htab = (htab_t) data;
void **slot;
if (tree_node_can_be_shared (*tp))
{
*walk_subtrees = false;
return NULL;
}
slot = htab_find_slot (htab, *tp, INSERT);
if (*slot)
return *slot;
*slot = *tp;
return NULL;
}
void
verify_stmts (void)
{
basic_block bb;
block_stmt_iterator bsi;
bool err = false;
htab_t htab;
tree addr;
timevar_push (TV_TREE_STMT_VERIFY);
htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
FOR_EACH_BB (bb)
{
tree phi;
int i;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
int phi_num_args = PHI_NUM_ARGS (phi);
for (i = 0; i < phi_num_args; i++)
{
tree t = PHI_ARG_DEF (phi, i);
tree addr;
if (TREE_CODE (t) != SSA_NAME
&& TREE_CODE (t) != FUNCTION_DECL
&& !is_gimple_val (t))
{
error ("PHI def is not a GIMPLE value");
debug_generic_stmt (phi);
debug_generic_stmt (t);
err |= true;
}
addr = walk_tree (&t, verify_expr, NULL, NULL);
if (addr)
{
debug_generic_stmt (addr);
err |= true;
}
addr = walk_tree (&t, verify_node_sharing, htab, NULL);
if (addr)
{
error ("Incorrect sharing of tree nodes");
debug_generic_stmt (phi);
debug_generic_stmt (addr);
err |= true;
}
}
}
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
err |= verify_stmt (stmt);
addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
if (addr)
{
error ("Incorrect sharing of tree nodes");
debug_generic_stmt (stmt);
debug_generic_stmt (addr);
err |= true;
}
}
}
if (err)
internal_error ("verify_stmts failed.");
htab_delete (htab);
timevar_pop (TV_TREE_STMT_VERIFY);
}
static int
tree_verify_flow_info (void)
{
int err = 0;
basic_block bb;
block_stmt_iterator bsi;
tree stmt;
edge e;
if (ENTRY_BLOCK_PTR->stmt_list)
{
error ("ENTRY_BLOCK has a statement list associated with it\n");
err = 1;
}
if (EXIT_BLOCK_PTR->stmt_list)
{
error ("EXIT_BLOCK has a statement list associated with it\n");
err = 1;
}
for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
if (e->flags & EDGE_FALLTHRU)
{
error ("Fallthru to exit from bb %d\n", e->src->index);
err = 1;
}
FOR_EACH_BB (bb)
{
bool found_ctrl_stmt = false;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
if (TREE_CODE (bsi_stmt (bsi)) != LABEL_EXPR)
break;
if (label_to_block (LABEL_EXPR_LABEL (bsi_stmt (bsi))) != bb)
{
error ("Label %s to block does not match in bb %d\n",
IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi))),
bb->index);
err = 1;
}
if (decl_function_context (LABEL_EXPR_LABEL (bsi_stmt (bsi)))
!= current_function_decl)
{
error ("Label %s has incorrect context in bb %d\n",
IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi))),
bb->index);
err = 1;
}
}
for (; !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (found_ctrl_stmt)
{
error ("Control flow in the middle of basic block %d\n",
bb->index);
err = 1;
}
if (stmt_ends_bb_p (stmt))
found_ctrl_stmt = true;
if (TREE_CODE (stmt) == LABEL_EXPR)
{
error ("Label %s in the middle of basic block %d\n",
IDENTIFIER_POINTER (DECL_NAME (stmt)),
bb->index);
err = 1;
}
}
bsi = bsi_last (bb);
if (bsi_end_p (bsi))
continue;
stmt = bsi_stmt (bsi);
if (is_ctrl_stmt (stmt))
{
for (e = bb->succ; e; e = e->succ_next)
if (e->flags & EDGE_FALLTHRU)
{
error ("Fallthru edge after a control statement in bb %d \n",
bb->index);
err = 1;
}
}
switch (TREE_CODE (stmt))
{
case COND_EXPR:
{
edge true_edge;
edge false_edge;
if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
|| TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
{
error ("Structured COND_EXPR at the end of bb %d\n", bb->index);
err = 1;
}
extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
if (!true_edge || !false_edge
|| !(true_edge->flags & EDGE_TRUE_VALUE)
|| !(false_edge->flags & EDGE_FALSE_VALUE)
|| (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
|| (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
|| bb->succ->succ_next->succ_next)
{
error ("Wrong outgoing edge flags at end of bb %d\n",
bb->index);
err = 1;
}
if (!has_label_p (true_edge->dest,
GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
{
error ("`then' label does not match edge at end of bb %d\n",
bb->index);
err = 1;
}
if (!has_label_p (false_edge->dest,
GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
{
error ("`else' label does not match edge at end of bb %d\n",
bb->index);
err = 1;
}
}
break;
case GOTO_EXPR:
if (simple_goto_p (stmt))
{
error ("Explicit goto at end of bb %d\n", bb->index);
err = 1;
}
else
{
for (e = bb->succ; e; e = e->succ_next)
if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE))
|| !(e->flags & EDGE_ABNORMAL))
{
error ("Wrong outgoing edge flags at end of bb %d\n",
bb->index);
err = 1;
}
}
break;
case RETURN_EXPR:
if (!bb->succ || bb->succ->succ_next
|| (bb->succ->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
| EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
{
error ("Wrong outgoing edge flags at end of bb %d\n", bb->index);
err = 1;
}
if (bb->succ->dest != EXIT_BLOCK_PTR)
{
error ("Return edge does not point to exit in bb %d\n",
bb->index);
err = 1;
}
break;
case SWITCH_EXPR:
{
edge e;
size_t i, n;
tree vec;
vec = SWITCH_LABELS (stmt);
n = TREE_VEC_LENGTH (vec);
for (i = 0; i < n; ++i)
{
tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
basic_block label_bb = label_to_block (lab);
if (label_bb->aux && label_bb->aux != (void *)1)
abort ();
label_bb->aux = (void *)1;
}
for (e = bb->succ; e; e = e->succ_next)
{
if (!e->dest->aux)
{
error ("Extra outgoing edge %d->%d\n",
bb->index, e->dest->index);
err = 1;
}
e->dest->aux = (void *)2;
if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
| EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
{
error ("Wrong outgoing edge flags at end of bb %d\n",
bb->index);
err = 1;
}
}
for (i = 0; i < n; ++i)
{
tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
basic_block label_bb = label_to_block (lab);
if (label_bb->aux != (void *)2)
{
error ("Missing edge %i->%i\n",
bb->index, label_bb->index);
err = 1;
}
}
for (e = bb->succ; e; e = e->succ_next)
e->dest->aux = (void *)0;
}
default: ;
}
}
if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
verify_dominators (CDI_DOMINATORS);
return err;
}
static void
tree_make_forwarder_block (edge fallthru)
{
edge e;
basic_block dummy, bb;
tree phi, new_phi, var;
dummy = fallthru->src;
bb = fallthru->dest;
if (!bb->pred->pred_next)
return;
for (phi = phi_nodes (dummy); phi; phi = TREE_CHAIN (phi))
{
var = PHI_RESULT (phi);
new_phi = create_phi_node (var, bb);
SSA_NAME_DEF_STMT (var) = new_phi;
PHI_RESULT (phi) = make_ssa_name (SSA_NAME_VAR (var), phi);
add_phi_arg (&new_phi, PHI_RESULT (phi), fallthru);
}
set_phi_nodes (bb, nreverse (phi_nodes (bb)));
for (e = bb->pred; e; e = e->pred_next)
{
if (e == fallthru)
continue;
for (phi = phi_nodes (bb), var = PENDING_STMT (e);
phi;
phi = TREE_CHAIN (phi), var = TREE_CHAIN (var))
add_phi_arg (&phi, TREE_VALUE (var), e);
PENDING_STMT (e) = NULL;
}
}
static bool
tree_forwarder_block_p (basic_block bb)
{
block_stmt_iterator bsi;
edge e;
if (! bb_ann (bb)->forwardable)
return false;
if (!bb->succ
|| bb->succ->succ_next
|| bb->succ->dest == EXIT_BLOCK_PTR
|| (bb->succ->flags & EDGE_ABNORMAL)
|| bb == ENTRY_BLOCK_PTR)
{
bb_ann (bb)->forwardable = 0;
return false;
}
for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
if (e->dest == bb)
{
bb_ann (bb)->forwardable = 0;
return false;
}
if (phi_nodes (bb))
{
bb_ann (bb)->forwardable = 0;
return false;
}
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
switch (TREE_CODE (stmt))
{
case LABEL_EXPR:
if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
return false;
break;
default:
bb_ann (bb)->forwardable = 0;
return false;
}
}
return true;
}
static bool
thread_jumps (void)
{
edge e, next, last, old;
basic_block bb, dest, tmp;
tree phi;
int arg, old_forwardable;
bool retval = false;
mark_dfs_back_edges ();
FOR_EACH_BB (bb)
{
for (e = bb->pred; e; e = e->pred_next)
if (e->flags & EDGE_DFS_BACK)
break;
bb_ann (bb)->forwardable = (e == NULL);
}
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
if (!bb->pred)
continue;
if (tree_forwarder_block_p (bb))
continue;
old_forwardable = bb_ann (bb)->forwardable;
bb_ann (bb)->forwardable = 0;
for (e = bb->succ; e; e = next)
{
next = e->succ_next;
if ((e->flags & EDGE_ABNORMAL)
|| !tree_forwarder_block_p (e->dest))
continue;
last = e->dest->succ;
bb_ann (e->dest)->forwardable = 0;
for (dest = e->dest->succ->dest;
tree_forwarder_block_p (dest);
last = dest->succ,
dest = dest->succ->dest)
{
if (dest->succ->dest == EXIT_BLOCK_PTR)
break;
bb_ann (dest)->forwardable = 0;
}
for (tmp = e->dest;
tmp != dest;
tmp = tmp->succ->dest)
bb_ann (tmp)->forwardable = 1;
if (dest == e->dest)
continue;
old = find_edge (bb, dest);
if (old)
{
if (!phi_alternatives_equal (dest, last, old))
{
dest = last->src;
if (dest == e->dest)
continue;
old = find_edge (bb, dest);
}
}
retval = true;
e = redirect_edge_and_branch (e, dest);
free_dominance_info (CDI_DOMINATORS);
if (!old)
{
for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
{
arg = phi_arg_from_edge (phi, last);
if (arg < 0)
abort ();
add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
}
}
}
bb_ann (bb)->forwardable = old_forwardable;
}
return retval;
}
tree
tree_block_label (basic_block bb)
{
block_stmt_iterator i, s = bsi_start (bb);
bool first = true;
tree label, stmt;
for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
{
stmt = bsi_stmt (i);
if (TREE_CODE (stmt) != LABEL_EXPR)
break;
label = LABEL_EXPR_LABEL (stmt);
if (!DECL_NONLOCAL (label))
{
if (!first)
bsi_move_before (&i, &s);
return label;
}
}
label = create_artificial_label ();
stmt = build1 (LABEL_EXPR, void_type_node, label);
bsi_insert_before (&s, stmt, BSI_NEW_STMT);
return label;
}
static edge
tree_try_redirect_by_replacing_jump (edge e, basic_block target)
{
basic_block src = e->src;
edge tmp;
block_stmt_iterator b;
tree stmt;
for (tmp = src->succ; tmp; tmp = tmp->succ_next)
if (tmp->dest != target && tmp != e)
break;
if (tmp)
return NULL;
b = bsi_last (src);
if (bsi_end_p (b))
return NULL;
stmt = bsi_stmt (b);
if (TREE_CODE (stmt) == COND_EXPR
|| TREE_CODE (stmt) == SWITCH_EXPR)
{
bsi_remove (&b);
e = ssa_redirect_edge (e, target);
e->flags = EDGE_FALLTHRU;
return e;
}
return NULL;
}
static edge
tree_redirect_edge_and_branch (edge e, basic_block dest)
{
basic_block bb = e->src;
block_stmt_iterator bsi;
edge ret;
tree label, stmt;
if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
return NULL;
if (e->src != ENTRY_BLOCK_PTR
&& (ret = tree_try_redirect_by_replacing_jump (e, dest)))
return ret;
if (e->dest == dest)
return e;
label = tree_block_label (dest);
bsi = bsi_last (bb);
stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
{
case COND_EXPR:
stmt = (e->flags & EDGE_TRUE_VALUE
? COND_EXPR_THEN (stmt)
: COND_EXPR_ELSE (stmt));
GOTO_DESTINATION (stmt) = label;
break;
case GOTO_EXPR:
abort ();
case SWITCH_EXPR:
{
tree vec = SWITCH_LABELS (stmt);
size_t i, n = TREE_VEC_LENGTH (vec);
for (i = 0; i < n; ++i)
{
tree elt = TREE_VEC_ELT (vec, i);
if (label_to_block (CASE_LABEL (elt)) == e->dest)
CASE_LABEL (elt) = label;
}
}
break;
case RETURN_EXPR:
bsi_remove (&bsi);
e->flags |= EDGE_FALLTHRU;
break;
default:
if (!(e->flags & EDGE_FALLTHRU))
abort ();
break;
}
e = ssa_redirect_edge (e, dest);
return e;
}
static basic_block
tree_redirect_edge_and_branch_force (edge e, basic_block dest)
{
e = tree_redirect_edge_and_branch (e, dest);
if (!e)
abort ();
return NULL;
}
static basic_block
tree_split_block (basic_block bb, void *stmt)
{
block_stmt_iterator bsi, bsi_tgt;
tree act;
basic_block new_bb;
edge e;
new_bb = create_empty_bb (bb);
new_bb->succ = bb->succ;
bb->succ = NULL;
for (e = new_bb->succ; e; e = e->succ_next)
e->src = new_bb;
if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
stmt = NULL;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
act = bsi_stmt (bsi);
if (TREE_CODE (act) == LABEL_EXPR)
continue;
if (!stmt)
break;
if (stmt == act)
{
bsi_next (&bsi);
break;
}
}
bsi_tgt = bsi_start (new_bb);
while (!bsi_end_p (bsi))
{
bool was_modified;
act = bsi_stmt (bsi);
was_modified = stmt_modified_p (act);
bsi_remove (&bsi);
bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
if (!was_modified)
unmodify_stmt (act);
}
return new_bb;
}
static bool
tree_move_block_after (basic_block bb, basic_block after)
{
if (bb->prev_bb == after)
return true;
unlink_block (bb);
link_block (bb, after);
return true;
}
static bool
tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
{
return true;
}
static basic_block
tree_duplicate_bb (basic_block bb)
{
basic_block new_bb;
block_stmt_iterator bsi, bsi_tgt;
new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
bsi_tgt = bsi_start (new_bb);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
tree copy;
if (TREE_CODE (stmt) == LABEL_EXPR)
continue;
copy = unshare_expr (stmt);
get_stmt_ann (copy);
copy_virtual_operands (copy, stmt);
bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
}
return new_bb;
}
void
dump_function_to_file (tree fn, FILE *file, int flags)
{
tree arg, vars, var;
bool ignore_topmost_bind = false, any_var = false;
basic_block bb;
tree chain;
fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
arg = DECL_ARGUMENTS (fn);
while (arg)
{
print_generic_expr (file, arg, dump_flags);
if (TREE_CHAIN (arg))
fprintf (file, ", ");
arg = TREE_CHAIN (arg);
}
fprintf (file, ")\n");
if (flags & TDF_RAW)
{
dump_node (fn, TDF_SLIM | flags, file);
return;
}
if (cfun && cfun->unexpanded_var_list)
{
ignore_topmost_bind = true;
fprintf (file, "{\n");
for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
{
var = TREE_VALUE (vars);
print_generic_decl (file, var, flags);
fprintf (file, "\n");
any_var = true;
}
}
if (basic_block_info)
{
if (!ignore_topmost_bind)
fprintf (file, "{\n");
if (any_var && n_basic_blocks)
fprintf (file, "\n");
FOR_EACH_BB (bb)
dump_generic_bb (file, bb, 2, flags);
fprintf (file, "}\n");
}
else
{
int indent;
chain = DECL_SAVED_TREE (fn);
if (TREE_CODE (chain) == BIND_EXPR)
{
if (ignore_topmost_bind)
{
chain = BIND_EXPR_BODY (chain);
indent = 2;
}
else
indent = 0;
}
else
{
if (!ignore_topmost_bind)
fprintf (file, "{\n");
indent = 2;
}
if (any_var)
fprintf (file, "\n");
print_generic_stmt_indented (file, chain, flags, indent);
if (ignore_topmost_bind)
fprintf (file, "}\n");
}
fprintf (file, "\n\n");
}
static void print_loop (FILE *, struct loop *, int);
static void print_pred_bbs (FILE *, edge);
static void print_succ_bbs (FILE *, edge);
static void
print_pred_bbs (FILE *file, edge e)
{
if (e == NULL)
return;
else if (e->pred_next == NULL)
fprintf (file, "%d", e->src->index);
else
{
fprintf (file, "%d ", e->src->index);
print_pred_bbs (file, e->pred_next);
}
}
static void
print_succ_bbs (FILE *file, edge e)
{
if (e == NULL)
return;
else if (e->succ_next == NULL)
fprintf (file, "bb_%d", e->dest->index);
else
{
fprintf (file, "%d ", e->dest->index);
print_succ_bbs (file, e->succ_next);
}
}
static void
print_loop (FILE *file, struct loop *loop, int indent)
{
char *s_indent;
basic_block bb;
if (loop == NULL)
return;
s_indent = (char *) alloca ((size_t) indent + 1);
memset ((void *) s_indent, ' ', (size_t) indent);
s_indent[indent] = '\0';
fprintf (file, "%s(loop (num %d)", s_indent, loop->num);
if (loop_nb_iterations (loop))
{
fprintf (file, " (nb_iterations ");
print_generic_expr (file, loop_nb_iterations (loop), 0);
fprintf (file, ")");
}
else
fprintf (file, " (nb_iterations not_analyzed_yet)");
fprintf (file, " (body (\n");
FOR_EACH_BB (bb)
if (bb->loop_father == loop)
{
fprintf (file, "%s (bb (num %d) (preds ", s_indent, bb->index);
print_pred_bbs (file, bb->pred);
fprintf (file, ") (succs ");
print_succ_bbs (file, bb->succ);
fprintf (file, ") (stmts (\n");
tree_dump_bb (bb, file, indent + 4);
fprintf (file, "%s )))\n", s_indent);
}
print_loop (file, loop->inner, indent + 2);
fprintf (file, "%s)))\n", s_indent);
print_loop (file, loop->next, indent);
}
void
print_loop_ir (FILE *file)
{
basic_block bb;
bb = BASIC_BLOCK (0);
if (bb && bb->loop_father)
print_loop (file, bb->loop_father, 0);
}
void
tree_debug_loops (void)
{
print_loop_ir (stderr);
}
void
tree_debug_loop (struct loop *loop)
{
print_loop (stderr, loop, 0);
}
static bool
tree_block_ends_with_call_p (basic_block bb)
{
block_stmt_iterator bsi = bsi_last (bb);
tree t = tsi_stmt (bsi.tsi);
if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
t = TREE_OPERAND (t, 0);
if (TREE_CODE (t) == MODIFY_EXPR)
t = TREE_OPERAND (t, 1);
return TREE_CODE (t) == CALL_EXPR;
}
static bool
tree_block_ends_with_condjump_p (basic_block bb)
{
tree stmt = tsi_stmt (bsi_last (bb).tsi);
return (TREE_CODE (stmt) == COND_EXPR);
}
static bool
need_fake_edge_p (tree t)
{
if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
t = TREE_OPERAND (t, 0);
if (TREE_CODE (t) == MODIFY_EXPR)
t = TREE_OPERAND (t, 1);
if (TREE_CODE (t) == CALL_EXPR
&& !(call_expr_flags (t) &
(ECF_NORETURN | ECF_LONGJMP | ECF_ALWAYS_RETURN)))
return true;
if (TREE_CODE (t) == ASM_EXPR
&& (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
return true;
return false;
}
static int
tree_flow_call_edges_add (sbitmap blocks)
{
int i;
int blocks_split = 0;
int last_bb = last_basic_block;
bool check_last_block = false;
if (n_basic_blocks == 0)
return 0;
if (! blocks)
check_last_block = true;
else
check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
if (check_last_block)
{
basic_block bb = EXIT_BLOCK_PTR->prev_bb;
block_stmt_iterator bsi = bsi_last (bb);
tree t = NULL_TREE;
if (!bsi_end_p (bsi))
t = bsi_stmt (bsi);
if (need_fake_edge_p (t))
{
edge e;
for (e = bb->succ; e; e = e->succ_next)
if (e->dest == EXIT_BLOCK_PTR)
{
bsi_insert_on_edge (e, build_empty_stmt ());
bsi_commit_edge_inserts ((int *)NULL);
break;
}
}
}
for (i = 0; i < last_bb; i++)
{
basic_block bb = BASIC_BLOCK (i);
block_stmt_iterator bsi;
tree stmt, last_stmt;
if (!bb)
continue;
if (blocks && !TEST_BIT (blocks, i))
continue;
bsi = bsi_last (bb);
if (!bsi_end_p (bsi))
{
last_stmt = bsi_stmt (bsi);
do
{
stmt = bsi_stmt (bsi);
if (need_fake_edge_p (stmt))
{
edge e;
#ifdef ENABLE_CHECKING
if (stmt == last_stmt)
for (e = bb->succ; e; e = e->succ_next)
if (e->dest == EXIT_BLOCK_PTR)
abort ();
#endif
if (stmt != last_stmt)
{
e = split_block (bb, stmt);
if (e)
blocks_split++;
}
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
bsi_prev (&bsi);
}
while (!bsi_end_p (bsi));
}
}
if (blocks_split)
verify_flow_info ();
return blocks_split;
}
struct cfg_hooks tree_cfg_hooks = {
"tree",
tree_verify_flow_info,
tree_dump_bb,
create_bb,
tree_redirect_edge_and_branch,
tree_redirect_edge_and_branch_force,
remove_bb,
tree_split_block,
tree_move_block_after,
tree_can_merge_blocks_p,
tree_merge_blocks,
tree_predict_edge,
tree_predicted_by_p,
tree_can_duplicate_bb_p,
tree_duplicate_bb,
tree_split_edge,
tree_make_forwarder_block,
NULL,
tree_block_ends_with_call_p,
tree_block_ends_with_condjump_p,
tree_flow_call_edges_add
};
static void
split_critical_edges (void)
{
basic_block bb;
edge e;
FOR_ALL_BB (bb)
{
for (e = bb->succ; e ; e = e->succ_next)
if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
{
split_edge (e);
}
}
}
struct tree_opt_pass pass_split_crit_edges =
{
NULL,
NULL,
split_critical_edges,
NULL,
NULL,
0,
TV_TREE_SPLIT_EDGES,
PROP_cfg,
PROP_no_crit_edges,
0,
0,
0,
};
static void
execute_warn_function_return (void)
{
location_t *locus;
tree last;
edge e;
if (warn_missing_noreturn
&& !TREE_THIS_VOLATILE (cfun->decl)
&& EXIT_BLOCK_PTR->pred == NULL
&& !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
warning ("%Jfunction might be possible candidate for attribute `noreturn'",
cfun->decl);
if (TREE_THIS_VOLATILE (cfun->decl)
&& EXIT_BLOCK_PTR->pred != NULL)
{
locus = NULL;
for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
{
last = last_stmt (e->src);
if (TREE_CODE (last) == RETURN_EXPR
&& (locus = EXPR_LOCUS (last)) != NULL)
break;
}
if (!locus)
locus = &cfun->function_end_locus;
warning ("%H`noreturn' function does return", locus);
}
else if (warn_return_type
&& EXIT_BLOCK_PTR->pred != NULL
&& !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
{
for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
{
tree last = last_stmt (e->src);
if (TREE_CODE (last) == RETURN_EXPR
&& TREE_OPERAND (last, 0) == NULL)
{
locus = EXPR_LOCUS (last);
if (!locus)
locus = &cfun->function_end_locus;
warning ("%Hcontrol reaches end of non-void function", locus);
break;
}
}
}
}
void
extract_true_false_edges_from_block (basic_block b,
edge *true_edge,
edge *false_edge)
{
edge e = b->succ;
if (e->flags & EDGE_TRUE_VALUE)
{
*true_edge = e;
*false_edge = e->succ_next;
}
else
{
*false_edge = e;
*true_edge = e->succ_next;
}
}
struct tree_opt_pass pass_warn_function_return =
{
NULL,
NULL,
execute_warn_function_return,
NULL,
NULL,
0,
0,
PROP_ssa,
0,
0,
0,
0
};
#include "gt-tree-cfg.h"