#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"
#include "cfglayout.h"
#include "hashtab.h"
static const int initial_cfg_capacity = 20;
static GTY(()) varray_type label_to_block_map;
struct edge_to_cases_elt
{
edge e;
tree case_labels;
};
static htab_t edge_to_cases;
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 bool remove_fallthru_edge (VEC(edge) *);
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 tree_forwarder_block_p (basic_block, bool);
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 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 bool cleanup_forwarder_blocks (void);
static void
build_tree_cfg (tree *tp)
{
tree_register_cfg_hooks ();
alloc_rbi_pool ();
init_flow ();
profile_status = PROFILE_ABSENT;
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);
cleanup_dead_labels ();
group_case_labels ();
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,
0
};
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)
{
gcc_assert (!bb->tree_annotations);
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;
gcc_assert (!e);
bb = alloc_block ();
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;
}
void
fold_cond_expr_cond (void)
{
basic_block bb;
FOR_EACH_BB (bb)
{
tree stmt = last_stmt (bb);
if (stmt
&& TREE_CODE (stmt) == COND_EXPR)
{
tree cond = fold (COND_EXPR_COND (stmt));
if (integer_zerop (cond))
COND_EXPR_COND (stmt) = integer_zero_node;
else if (integer_onep (cond))
COND_EXPR_COND (stmt) = integer_one_node;
}
}
}
static void
make_edges (void)
{
basic_block bb;
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 (EDGE_COUNT (bb->succs) == 0)
make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
}
remove_fake_exit_edges ();
fold_cond_expr_cond ();
cleanup_tree_cfg ();
}
static void
make_ctrl_stmt_edges (basic_block bb)
{
tree last = last_stmt (bb);
gcc_assert (last);
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 (EDGE_COUNT (bb->succs) == 0)
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
break;
default:
gcc_unreachable ();
}
}
static void
make_exit_edges (basic_block bb)
{
tree last = last_stmt (bb), op;
gcc_assert (last);
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)
{
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
return;
}
make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
break;
case MODIFY_EXPR:
op = get_call_expr_in (last);
if (op && TREE_SIDE_EFFECTS (op)
&& current_function_has_nonlocal_label)
make_goto_expr_edges (bb);
make_eh_edges (last);
make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
break;
default:
gcc_unreachable ();
}
}
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;
gcc_assert (entry);
gcc_assert (TREE_CODE (entry) == COND_EXPR);
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 hashval_t
edge_to_cases_hash (const void *p)
{
edge e = ((struct edge_to_cases_elt *)p)->e;
return htab_hash_pointer (e);
}
static int
edge_to_cases_eq (const void *p1, const void *p2)
{
edge e1 = ((struct edge_to_cases_elt *)p1)->e;
edge e2 = ((struct edge_to_cases_elt *)p2)->e;
return e1 == e2;
}
static void
edge_to_cases_cleanup (void *p)
{
struct edge_to_cases_elt *elt = p;
tree t, next;
for (t = elt->case_labels; t; t = next)
{
next = TREE_CHAIN (t);
TREE_CHAIN (t) = NULL;
}
free (p);
}
static void
start_recording_case_labels (void)
{
gcc_assert (edge_to_cases == NULL);
edge_to_cases = htab_create (37,
edge_to_cases_hash,
edge_to_cases_eq,
edge_to_cases_cleanup);
}
static bool
recording_case_labels_p (void)
{
return (edge_to_cases != NULL);
}
static void
end_recording_case_labels (void)
{
htab_delete (edge_to_cases);
edge_to_cases = NULL;
}
static void
record_switch_edge (edge e, tree case_label)
{
struct edge_to_cases_elt *elt;
void **slot;
elt = xmalloc (sizeof (struct edge_to_cases_elt));
elt->e = e;
elt->case_labels = case_label;
slot = htab_find_slot (edge_to_cases, elt, INSERT);
if (*slot == NULL)
{
*slot = (void *)elt;
}
else
{
free (elt);
elt = (struct edge_to_cases_elt *) *slot;
TREE_CHAIN (case_label) = elt->case_labels;
elt->case_labels = case_label;
}
}
static tree
get_cases_for_edge (edge e, tree t)
{
struct edge_to_cases_elt elt, *elt_p;
void **slot;
size_t i, n;
tree vec;
if (!recording_case_labels_p ())
return NULL;
restart:
elt.e = e;
elt.case_labels = NULL;
slot = htab_find_slot (edge_to_cases, &elt, NO_INSERT);
if (slot)
{
elt_p = (struct edge_to_cases_elt *)*slot;
return elt_p->case_labels;
}
vec = SWITCH_LABELS (t);
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);
record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i));
}
goto restart;
}
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)
{
int uid = LABEL_DECL_UID (dest);
if ((errorcount || sorrycount) && uid < 0)
{
block_stmt_iterator bsi = bsi_start (BASIC_BLOCK (0));
tree stmt;
stmt = build1 (LABEL_EXPR, void_type_node, dest);
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
uid = LABEL_DECL_UID (dest);
}
return VARRAY_BB (label_to_block_map, uid);
}
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))
{
edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
#ifdef USE_MAPPED_LOCATION
e->goto_locus = EXPR_LOCATION (goto_t);
#else
e->goto_locus = EXPR_LOCUS (goto_t);
#endif
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 && EDGE_COUNT (bb->succs) == 0)
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
bool
cleanup_tree_cfg (void)
{
bool retval = false;
timevar_push (TV_TREE_CLEANUP_CFG);
retval = cleanup_control_flow ();
retval |= delete_unreachable_blocks ();
start_recording_case_labels ();
retval |= cleanup_forwarder_blocks ();
end_recording_case_labels ();
#ifdef ENABLE_CHECKING
if (retval)
{
gcc_assert (!cleanup_control_flow ());
gcc_assert (!delete_unreachable_blocks ());
gcc_assert (!cleanup_forwarder_blocks ());
}
#endif
retval |= merge_seq_blocks ();
compact_blocks ();
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
timevar_pop (TV_TREE_CLEANUP_CFG);
return retval;
}
static tree *label_for_bb;
static void
update_eh_label (struct eh_region *region)
{
tree old_label = get_eh_region_tree_label (region);
if (old_label)
{
tree new_label;
basic_block bb = label_to_block (old_label);
if (! bb)
return;
new_label = label_for_bb[bb->index];
set_eh_region_tree_label (region, new_label);
}
}
static tree
main_block_label (tree label)
{
basic_block bb = label_to_block (label);
if (!label_for_bb[bb->index])
label_for_bb[bb->index] = label;
return label_for_bb[bb->index];
}
void
cleanup_dead_labels (void)
{
basic_block bb;
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;
true_branch = COND_EXPR_THEN (stmt);
false_branch = COND_EXPR_ELSE (stmt);
GOTO_DESTINATION (true_branch)
= main_block_label (GOTO_DESTINATION (true_branch));
GOTO_DESTINATION (false_branch)
= main_block_label (GOTO_DESTINATION (false_branch));
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 elt = TREE_VEC_ELT (vec, i);
tree label = main_block_label (CASE_LABEL (elt));
CASE_LABEL (elt) = label;
}
break;
}
case GOTO_EXPR:
if (! computed_goto_p (stmt))
{
GOTO_DESTINATION (stmt)
= main_block_label (GOTO_DESTINATION (stmt));
break;
}
default:
break;
}
}
for_each_eh_region (update_eh_label);
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);
}
void
group_case_labels (void)
{
basic_block bb;
FOR_EACH_BB (bb)
{
tree stmt = last_stmt (bb);
if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
{
tree labels = SWITCH_LABELS (stmt);
int old_size = TREE_VEC_LENGTH (labels);
int i, j, new_size = old_size;
tree default_case = TREE_VEC_ELT (labels, old_size - 1);
tree default_label;
default_label = CASE_LABEL (default_case);
i = 0;
while (i < old_size - 1)
{
tree base_case, base_label, base_high, type;
base_case = TREE_VEC_ELT (labels, i);
gcc_assert (base_case);
base_label = CASE_LABEL (base_case);
if (base_label == default_label)
{
TREE_VEC_ELT (labels, i) = NULL_TREE;
i++;
new_size--;
continue;
}
type = TREE_TYPE (CASE_LOW (base_case));
base_high = CASE_HIGH (base_case) ?
CASE_HIGH (base_case) : CASE_LOW (base_case);
i++;
while (i < old_size - 1)
{
tree merge_case = TREE_VEC_ELT (labels, i);
tree merge_label = CASE_LABEL (merge_case);
tree t = int_const_binop (PLUS_EXPR, base_high,
integer_one_node, 1);
if (merge_label == base_label
&& tree_int_cst_equal (CASE_LOW (merge_case), t))
{
base_high = CASE_HIGH (merge_case) ?
CASE_HIGH (merge_case) : CASE_LOW (merge_case);
CASE_HIGH (base_case) = base_high;
TREE_VEC_ELT (labels, i) = NULL_TREE;
new_size--;
i++;
}
else
break;
}
}
for (i = 0, j = 0; i < new_size; i++)
{
while (! TREE_VEC_ELT (labels, j))
j++;
TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
}
TREE_VEC_LENGTH (labels) = new_size;
}
}
}
static bool
tree_can_merge_blocks_p (basic_block a, basic_block b)
{
tree stmt;
block_stmt_iterator bsi;
if (EDGE_COUNT (a->succs) != 1)
return false;
if (EDGE_SUCC (a, 0)->flags & EDGE_ABNORMAL)
return false;
if (EDGE_SUCC (a, 0)->dest != b)
return false;
if (EDGE_COUNT (b->preds) > 1)
return false;
if (b == EXIT_BLOCK_PTR)
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);
gcc_assert (EDGE_SUCC (a, 0)->flags & EDGE_FALLTHRU);
gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
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_HAS_LOCATION (stmt))
{
location_t loc = EXPR_LOCATION (stmt);
if (LOCATION_LINE (loc) > 0)
{
warning ("%Hwill never be executed", &loc);
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;
then_clause = COND_EXPR_THEN (*stmt_p);
else_clause = COND_EXPR_ELSE (*stmt_p);
cond = fold (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, op;
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);
op = get_call_expr_in (t);
if (op)
{
update_call_expr_flags (op);
notice_special_calls (op);
}
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 ASM_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,
0
};
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 (EDGE_COUNT (bb->preds) != 1
|| !(EDGE_PRED (bb, 0)->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
return;
cond = COND_EXPR_COND (last_stmt (EDGE_PRED (bb, 0)->src));
if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
{
var = cond;
val = (EDGE_PRED (bb, 0)->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 = (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE
? boolean_true_node : boolean_false_node);
}
else
{
if (EDGE_PRED (bb, 0)->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) == MODIFY_EXPR
&& (TREE_OPERAND (stmt, 0) == var
|| TREE_OPERAND (stmt, 0) == val)))
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 = PHI_CHAIN (phi);
remove_phi_node (phi, NULL_TREE, bb);
phi = next;
}
while (EDGE_COUNT (bb->succs) > 0)
remove_edge (EDGE_SUCC (bb, 0));
}
static void
remove_bb (basic_block bb)
{
block_stmt_iterator i;
source_locus loc = 0;
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);)
{
tree stmt = bsi_stmt (i);
if (TREE_CODE (stmt) == LABEL_EXPR
&& FORCED_LABEL (LABEL_EXPR_LABEL (stmt)))
{
basic_block new_bb = bb->prev_bb;
block_stmt_iterator new_bsi = bsi_start (new_bb);
bsi_remove (&i);
bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
}
else
{
release_defs (stmt);
set_bb_for_stmt (stmt, NULL);
bsi_remove (&i);
}
if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
{
source_locus t;
#ifdef USE_MAPPED_LOCATION
t = EXPR_LOCATION (stmt);
#else
t = EXPR_LOCUS (stmt);
#endif
if (t && LOCATION_LINE (*t) > 0)
loc = t;
}
}
if (warn_notreached && loc)
#ifdef USE_MAPPED_LOCATION
warning ("%Hwill never be executed", &loc);
#else
warning ("%Hwill never be executed", loc);
#endif
remove_phi_nodes_and_edges_for_unreachable_block (bb);
}
VEC(tree) *modified_noreturn_calls;
static bool
cleanup_control_flow (void)
{
basic_block bb;
block_stmt_iterator bsi;
bool retval = false;
tree stmt;
while (VEC_length (tree, modified_noreturn_calls))
{
stmt = VEC_pop (tree, modified_noreturn_calls);
bb = bb_for_stmt (stmt);
if (bb != NULL && last_stmt (bb) != stmt && noreturn_call_p (stmt))
split_block (bb, 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);
if (noreturn_call_p (stmt) && remove_fallthru_edge (bb->succs))
{
free_dominance_info (CDI_DOMINATORS);
retval = true;
}
}
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 (EDGE_COUNT (bb->succs) > 1)
{
edge e;
edge_iterator ei;
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:
gcc_unreachable ();
}
taken_edge = find_taken_edge (bb, val);
if (!taken_edge)
return false;
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
if (e != taken_edge)
{
taken_edge->probability += e->probability;
taken_edge->count += e->count;
remove_edge (e);
retval = true;
}
else
ei_next (&ei);
}
if (taken_edge->probability > REG_BR_PROB_BASE)
taken_edge->probability = REG_BR_PROB_BASE;
}
else
taken_edge = EDGE_SUCC (bb, 0);
bsi_remove (&bsi);
taken_edge->flags = EDGE_FALLTHRU;
free_dominance_info (CDI_DOMINATORS);
return retval;
}
static bool
remove_fallthru_edge (VEC(edge) *ev)
{
edge_iterator ei;
edge e;
FOR_EACH_EDGE (e, ei, ev)
if ((e->flags & EDGE_FALLTHRU) != 0)
{
remove_edge (e);
return true;
}
return false;
}
edge
find_taken_edge (basic_block bb, tree val)
{
tree stmt;
stmt = last_stmt (bb);
gcc_assert (stmt);
gcc_assert (is_ctrl_stmt (stmt));
gcc_assert (val);
if (TREE_CODE (val) != INTEGER_CST)
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);
gcc_unreachable ();
}
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);
gcc_assert (TREE_CODE (val) == INTEGER_CST);
return (zero_p (val) ? false_edge : true_edge);
}
static edge
find_taken_edge_switch_expr (basic_block bb, tree val)
{
tree switch_expr, taken_case;
basic_block dest_bb;
edge e;
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);
gcc_assert (e);
return e;
}
static tree
find_case_label_for_value (tree switch_expr, tree val)
{
tree vec = SWITCH_LABELS (switch_expr);
size_t low, high, n = TREE_VEC_LENGTH (vec);
tree default_case = TREE_VEC_ELT (vec, n - 1);
for (low = -1, high = n - 1; high - low > 1; )
{
size_t i = (high + low) / 2;
tree t = TREE_VEC_ELT (vec, i);
int cmp;
cmp = tree_int_cst_compare (CASE_LOW (t), val);
if (cmp > 0)
high = i;
else
low = i;
if (CASE_HIGH (t) == NULL)
{
if (cmp == 0)
return t;
}
else
{
if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
return t;
}
}
return default_case;
}
static bool
phi_alternatives_equal (basic_block dest, edge e1, edge e2)
{
int n1 = e1->dest_idx;
int n2 = e2->dest_idx;
tree phi;
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
{
tree val1 = PHI_ARG_DEF (phi, n1);
tree val2 = PHI_ARG_DEF (phi, n2);
gcc_assert (val1 != NULL_TREE);
gcc_assert (val2 != NULL_TREE);
if (!operand_equal_for_phi_arg_p (val1, val2))
return false;
}
return true;
}
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;
int n_edges;
basic_block bb;
const char * const fmt_str = "%-30s%-13s%12s\n";
const char * const fmt_str_1 = "%-30s%13d%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)
n_edges += EDGE_COUNT (bb->succs);
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;
edge_iterator ei;
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_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
{
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_EACH_EDGE (e, ei, bb->succs)
{
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;
gcc_assert (t);
call = get_call_expr_in (t);
if (call)
{
if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
return true;
if (call_expr_flags (call) & ECF_NORETURN)
return true;
}
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);
}
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;
edge_iterator ei;
tree stmt, label;
FOR_EACH_BB (bb)
{
last = bsi_last (bb);
stmt = last_stmt (bb);
if (stmt && TREE_CODE (stmt) == COND_EXPR)
{
e = find_edge (bb, bb->next_bb);
if (e)
{
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
gcc_unreachable ();
e->flags |= EDGE_FALLTHRU;
}
continue;
}
if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
{
gcc_assert (EDGE_COUNT (bb->succs) == 1);
gcc_assert (EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR);
if (bb->next_bb == EXIT_BLOCK_PTR
&& !TREE_OPERAND (stmt, 0))
{
bsi_remove (&last);
EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
}
continue;
}
if (stmt && is_ctrl_stmt (stmt))
continue;
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->flags & EDGE_FALLTHRU)
break;
if (!e || e->dest == bb->next_bb)
continue;
gcc_assert (e->dest != EXIT_BLOCK_PTR);
label = tree_block_label (e->dest);
stmt = build1 (GOTO_EXPR, void_type_node, label);
#ifdef USE_MAPPED_LOCATION
SET_EXPR_LOCATION (stmt, e->goto_locus);
#else
SET_EXPR_LOCUS (stmt, e->goto_locus);
#endif
bsi_insert_after (&last, stmt, BSI_NEW_STMT);
e->flags &= ~EDGE_FALLTHRU;
}
}
void
delete_tree_cfg_annotations (void)
{
basic_block bb;
if (n_basic_blocks > 0)
free_blocks_annotations ();
label_to_block_map = NULL;
free_rbi_pool ();
FOR_EACH_BB (bb)
bb->rbi = NULL;
}
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) == PHI_NODE)
PHI_BB (t) = bb;
else 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
gcc_assert (!bb || !VARRAY_BB (label_to_block_map, uid));
VARRAY_BB (label_to_block_map, uid) = bb;
}
}
}
extern block_stmt_iterator
bsi_for_stmt (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;
gcc_unreachable ();
}
void
bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
tsi_link_before (&i->tsi, t, m);
modify_stmt (t);
}
void
bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
tsi_link_after (&i->tsi, t, m);
modify_stmt (t);
}
void
bsi_remove (block_stmt_iterator *i)
{
tree t = bsi_stmt (*i);
set_bb_for_stmt (t, NULL);
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 (EDGE_COUNT (dest->preds) == 1
&& ! 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
&& EDGE_COUNT (src->succs) == 1
&& 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;
if (TREE_CODE (tmp) == RETURN_EXPR)
{
tree op = TREE_OPERAND (tmp, 0);
if (!is_gimple_val (op))
{
gcc_assert (TREE_CODE (op) == MODIFY_EXPR);
bsi_insert_before (bsi, op, BSI_NEW_STMT);
TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
}
bsi_prev (bsi);
return true;
}
}
dest = split_edge (e);
if (new_bb)
*new_bb = dest;
e = EDGE_PRED (dest, 0);
goto restart;
}
void
bsi_commit_edge_inserts (void)
{
basic_block bb;
edge e;
edge_iterator ei;
bsi_commit_one_edge_insert (EDGE_SUCC (ENTRY_BLOCK_PTR, 0), NULL);
FOR_EACH_BB (bb)
FOR_EACH_EDGE (e, ei, bb->succs)
bsi_commit_one_edge_insert (e, NULL);
}
void
bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
{
if (new_bb)
*new_bb = NULL;
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, new_bb))
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;
gcc_assert (!PENDING_STMT (e));
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 void
reinstall_phi_args (edge new_edge, edge old_edge)
{
tree var, phi;
if (!PENDING_STMT (old_edge))
return;
for (var = PENDING_STMT (old_edge), phi = phi_nodes (new_edge->dest);
var && phi;
var = TREE_CHAIN (var), phi = PHI_CHAIN (phi))
{
tree result = TREE_PURPOSE (var);
tree arg = TREE_VALUE (var);
gcc_assert (result == PHI_RESULT (phi));
add_phi_arg (phi, arg, new_edge);
}
PENDING_STMT (old_edge) = NULL;
}
static basic_block
tree_split_edge (edge edge_in)
{
basic_block new_bb, after_bb, dest, src;
edge new_edge, e;
gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
src = edge_in->src;
dest = edge_in->dest;
if (dest->prev_bb && find_edge (dest->prev_bb, dest))
after_bb = edge_in->src;
else
after_bb = dest->prev_bb;
new_bb = create_empty_bb (after_bb);
new_bb->frequency = EDGE_FREQUENCY (edge_in);
new_bb->count = edge_in->count;
new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
new_edge->probability = REG_BR_PROB_BASE;
new_edge->count = edge_in->count;
e = redirect_edge_and_branch (edge_in, new_bb);
gcc_assert (e);
reinstall_phi_args (new_edge, e);
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, void *data ATTRIBUTE_UNUSED)
{
tree t = *tp, x;
bool in_phi = (data != NULL);
if (TYPE_P (t))
*walk_subtrees = 0;
#define CHECK_OP(N, MSG) \
do { if (!CONSTANT_CLASS_P (TREE_OPERAND (t, N)) \
&& !is_gimple_val (TREE_OPERAND (t, N))) \
{ error (MSG); return TREE_OPERAND (t, N); }} while (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 t;
}
break;
case ADDR_EXPR:
if (in_phi)
break;
for (x = TREE_OPERAND (t, 0);
handled_component_p (x);
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 = COND_EXPR_COND (t);
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:
CHECK_OP (0, "Invalid operand to unary operator");
break;
case REALPART_EXPR:
case IMAGPART_EXPR:
case COMPONENT_REF:
case ARRAY_REF:
case ARRAY_RANGE_REF:
case BIT_FIELD_REF:
case VIEW_CONVERT_EXPR:
while (handled_component_p (t))
{
if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
CHECK_OP (2, "Invalid COMPONENT_REF offset operator");
else if (TREE_CODE (t) == ARRAY_REF
|| TREE_CODE (t) == ARRAY_RANGE_REF)
{
CHECK_OP (1, "Invalid array index.");
if (TREE_OPERAND (t, 2))
CHECK_OP (2, "Invalid array lower bound.");
if (TREE_OPERAND (t, 3))
CHECK_OP (3, "Invalid array stride.");
}
else if (TREE_CODE (t) == BIT_FIELD_REF)
{
CHECK_OP (1, "Invalid operand to BIT_FIELD_REF");
CHECK_OP (2, "Invalid operand to BIT_FIELD_REF");
}
t = TREE_OPERAND (t, 0);
}
if (!CONSTANT_CLASS_P (t) && !is_gimple_lvalue (t))
{
error ("Invalid reference prefix.");
return t;
}
*walk_subtrees = 0;
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 LTGT_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:
CHECK_OP (0, "Invalid operand to binary operator");
CHECK_OP (1, "Invalid operand to binary operator");
break;
default:
break;
}
return NULL;
#undef CHECK_OP
}
static bool
verify_stmt (tree stmt, bool last_in_block)
{
tree addr;
if (!is_gimple_stmt (stmt))
{
error ("Is not a valid GIMPLE statement.");
goto fail;
}
addr = walk_tree (&stmt, verify_expr, NULL, NULL);
if (addr)
{
debug_generic_stmt (addr);
return true;
}
if (lookup_stmt_eh_region (stmt) >= 0)
{
if (!tree_could_throw_p (stmt))
{
error ("Statement marked for throw, but doesn%'t.");
goto fail;
}
if (!last_in_block && tree_can_throw_internal (stmt))
{
error ("Statement marked for throw in middle of block.");
goto fail;
}
}
return false;
fail:
debug_generic_stmt (stmt);
return true;
}
static bool
tree_node_can_be_shared (tree t)
{
if (IS_TYPE_OR_DECL_P (t)
|| CONSTANT_CLASS_P (t)
|| is_gimple_min_invariant (t)
|| TREE_CODE (t) == SSA_NAME
|| t == error_mark_node)
return true;
if (TREE_CODE (t) == CASE_LABEL_EXPR)
return true;
while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
&& (CONSTANT_CLASS_P (TREE_OPERAND (t, 1))
|| 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 = PHI_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, (void *) 1, 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); )
{
tree stmt = bsi_stmt (bsi);
bsi_next (&bsi);
err |= verify_stmt (stmt, bsi_end_p (bsi));
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;
edge_iterator ei;
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_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
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;
stmt = NULL_TREE;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree prev_stmt = stmt;
stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) != LABEL_EXPR)
break;
if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
{
error ("Nonlocal label %s is not first "
"in a sequence of labels in bb %d",
IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
bb->index);
err = 1;
}
if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
{
error ("Label %s to block does not match in bb %d\n",
IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
bb->index);
err = 1;
}
if (decl_function_context (LABEL_EXPR_LABEL (stmt))
!= current_function_decl)
{
error ("Label %s has incorrect context in bb %d\n",
IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
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_EACH_EDGE (e, ei, bb->succs)
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))
|| EDGE_COUNT (bb->succs) >= 3)
{
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_EACH_EDGE (e, ei, bb->succs)
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 (EDGE_COUNT (bb->succs) != 1
|| (EDGE_SUCC (bb, 0)->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 (EDGE_SUCC (bb, 0)->dest != EXIT_BLOCK_PTR)
{
error ("Return edge does not point to exit in bb %d\n",
bb->index);
err = 1;
}
break;
case SWITCH_EXPR:
{
tree prev;
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);
gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
label_bb->aux = (void *)1;
}
prev = TREE_VEC_ELT (vec, 0);
for (i = 1; i < n - 1; ++i)
{
tree c = TREE_VEC_ELT (vec, i);
if (! CASE_LOW (c))
{
error ("Found default case not at end of case vector");
err = 1;
continue;
}
if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
{
error ("Case labels not sorted:\n ");
print_generic_expr (stderr, prev, 0);
fprintf (stderr," is greater than ");
print_generic_expr (stderr, c, 0);
fprintf (stderr," but comes before it.\n");
err = 1;
}
prev = c;
}
if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
{
error ("No default case found at end of case vector");
err = 1;
}
FOR_EACH_EDGE (e, ei, bb->succs)
{
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",
bb->index, label_bb->index);
err = 1;
}
}
FOR_EACH_EDGE (e, ei, bb->succs)
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;
edge_iterator ei;
basic_block dummy, bb;
tree phi, new_phi, var;
dummy = fallthru->src;
bb = fallthru->dest;
if (EDGE_COUNT (bb->preds) == 1)
return;
for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
{
var = PHI_RESULT (phi);
new_phi = create_phi_node (var, bb);
SSA_NAME_DEF_STMT (var) = new_phi;
SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
}
set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (e == fallthru)
continue;
flush_pending_stmts (e);
}
}
static bool
tree_forwarder_block_p (basic_block bb, bool phi_wanted)
{
block_stmt_iterator bsi;
if (EDGE_COUNT (bb->succs) != 1
|| (phi_nodes (bb) != NULL_TREE) != phi_wanted
|| EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR
|| EDGE_SUCC (bb, 0)->dest == bb
|| (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL))
return false;
#if ENABLE_CHECKING
gcc_assert (bb != ENTRY_BLOCK_PTR);
#endif
for (bsi = bsi_last (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:
return false;
}
}
if (find_edge (ENTRY_BLOCK_PTR, bb))
return false;
return true;
}
static inline bool
has_abnormal_incoming_edge_p (basic_block bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_ABNORMAL)
return true;
return false;
}
static bool
remove_forwarder_block (basic_block bb, basic_block **worklist)
{
edge succ = EDGE_SUCC (bb, 0), e, s;
basic_block dest = succ->dest;
tree label;
tree phi;
edge_iterator ei;
block_stmt_iterator bsi, bsi_to;
bool seen_abnormal_edge = false;
if (dest == bb)
return false;
label = first_stmt (dest);
if (label
&& TREE_CODE (label) == LABEL_EXPR
&& DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
return false;
if (has_abnormal_incoming_edge_p (bb))
{
seen_abnormal_edge = true;
if (has_abnormal_incoming_edge_p (dest)
|| phi_nodes (dest) != NULL_TREE)
return false;
}
if (phi_nodes (dest))
{
FOR_EACH_EDGE (e, ei, bb->preds)
{
s = find_edge (e->src, dest);
if (!s)
continue;
if (!phi_alternatives_equal (dest, succ, s))
return false;
}
}
for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
{
if (e->flags & EDGE_ABNORMAL)
{
s = redirect_edge_succ_nodup (e, dest);
}
else
s = redirect_edge_and_branch (e, dest);
if (s == e)
{
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s);
}
else
{
if (tree_forwarder_block_p (s->src, false))
*(*worklist)++ = s->src;
}
}
if (seen_abnormal_edge)
{
bsi_to = bsi_start (dest);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
{
label = bsi_stmt (bsi);
gcc_assert (TREE_CODE (label) == LABEL_EXPR);
bsi_remove (&bsi);
bsi_insert_before (&bsi_to, label, BSI_CONTINUE_LINKING);
}
}
if (dom_info_available_p (CDI_DOMINATORS))
{
basic_block dom, dombb, domdest;
dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
if (domdest == bb)
{
dom = dombb;
}
else
dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
set_immediate_dominator (CDI_DOMINATORS, dest, dom);
}
delete_basic_block (bb);
return true;
}
static bool
cleanup_forwarder_blocks (void)
{
basic_block bb;
bool changed = false;
basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
basic_block *current = worklist;
FOR_EACH_BB (bb)
{
if (tree_forwarder_block_p (bb, false))
*current++ = bb;
}
while (current != worklist)
{
bb = *--current;
changed |= remove_forwarder_block (bb, ¤t);
}
free (worklist);
return changed;
}
static void
remove_forwarder_block_with_phi (basic_block bb)
{
edge succ = EDGE_SUCC (bb, 0);
basic_block dest = succ->dest;
tree label;
basic_block dombb, domdest, dom;
if (dest == bb)
return;
label = first_stmt (dest);
if (label
&& TREE_CODE (label) == LABEL_EXPR
&& DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
return;
while (EDGE_COUNT (bb->preds) > 0)
{
edge e = EDGE_PRED (bb, 0), s;
tree phi;
s = find_edge (e->src, dest);
if (s)
{
if (phi_alternatives_equal (dest, s, succ))
{
e = redirect_edge_and_branch (e, dest);
PENDING_STMT (e) = NULL_TREE;
continue;
}
e = EDGE_SUCC (split_edge (e), 0);
}
s = redirect_edge_and_branch (e, dest);
gcc_assert (s == e);
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
{
tree def = PHI_ARG_DEF (phi, succ->dest_idx);
if (TREE_CODE (def) == SSA_NAME)
{
tree var;
for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
{
tree old_arg = TREE_PURPOSE (var);
tree new_arg = TREE_VALUE (var);
if (def == old_arg)
{
def = new_arg;
break;
}
}
}
add_phi_arg (phi, def, s);
}
PENDING_STMT (e) = NULL;
}
dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
if (domdest == bb)
{
dom = dombb;
}
else
dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
set_immediate_dominator (CDI_DOMINATORS, dest, dom);
delete_basic_block (bb);
}
static void
merge_phi_nodes (void)
{
basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
basic_block *current = worklist;
basic_block bb;
calculate_dominance_info (CDI_DOMINATORS);
FOR_EACH_BB (bb)
{
basic_block dest;
if (!tree_forwarder_block_p (bb, true))
continue;
dest = EDGE_SUCC (bb, 0)->dest;
if (!phi_nodes (dest)
|| has_abnormal_incoming_edge_p (bb))
continue;
if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
{
*current++ = bb;
}
}
while (current != worklist)
{
bb = *--current;
remove_forwarder_block_with_phi (bb);
}
free (worklist);
}
static bool
gate_merge_phi (void)
{
return 1;
}
struct tree_opt_pass pass_merge_phi = {
"mergephi",
gate_merge_phi,
merge_phi_nodes,
NULL,
NULL,
0,
TV_TREE_MERGE_PHI,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func | TODO_ggc_collect
| TODO_verify_ssa,
0
};
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;
block_stmt_iterator b;
tree stmt;
if (EDGE_COUNT (src->succs) != 2
|| EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
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:
gcc_unreachable ();
case SWITCH_EXPR:
{
tree cases = get_cases_for_edge (e, stmt);
if (cases)
{
edge e2 = find_edge (e->src, dest);
tree last, first;
first = cases;
while (cases)
{
last = cases;
CASE_LABEL (cases) = label;
cases = TREE_CHAIN (cases);
}
if (e2)
{
tree cases2 = get_cases_for_edge (e2, stmt);
TREE_CHAIN (last) = TREE_CHAIN (cases2);
TREE_CHAIN (cases2) = first;
}
}
else
{
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:
gcc_assert (e->flags & EDGE_FALLTHRU);
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);
gcc_assert (e);
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;
edge_iterator ei;
new_bb = create_empty_bb (bb);
new_bb->succs = bb->succs;
bb->succs = NULL;
FOR_EACH_EDGE (e, ei, new_bb->succs)
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;
tree phi, val;
ssa_op_iter op_iter;
new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
mark_for_rewrite (PHI_RESULT (phi));
create_phi_node (PHI_RESULT (phi), new_bb);
}
set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_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;
get_stmt_operands (stmt);
FOR_EACH_SSA_TREE_OPERAND (val, stmt, op_iter, SSA_OP_ALL_DEFS)
mark_for_rewrite (val);
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
add_phi_args_after_copy_bb (basic_block bb_copy)
{
basic_block bb, dest;
edge e, e_copy;
edge_iterator ei;
tree phi, phi_copy, phi_next, def;
bb = bb_copy->rbi->original;
FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
{
if (!phi_nodes (e_copy->dest))
continue;
if (e_copy->dest->rbi->duplicated)
dest = e_copy->dest->rbi->original;
else
dest = e_copy->dest;
e = find_edge (bb, dest);
if (!e)
{
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest->rbi->duplicated
&& e->dest->rbi->original == dest)
break;
gcc_assert (e != NULL);
}
for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
phi;
phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
{
phi_next = PHI_CHAIN (phi);
gcc_assert (PHI_RESULT (phi) == PHI_RESULT (phi_copy));
def = PHI_ARG_DEF_FROM_EDGE (phi, e);
add_phi_arg (phi_copy, def, e_copy);
}
}
}
void
add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
{
unsigned i;
for (i = 0; i < n_region; i++)
region_copy[i]->rbi->duplicated = 1;
for (i = 0; i < n_region; i++)
add_phi_args_after_copy_bb (region_copy[i]);
for (i = 0; i < n_region; i++)
region_copy[i]->rbi->duplicated = 0;
}
struct ssa_name_map_entry
{
tree from_name;
tree to_name;
};
static hashval_t
ssa_name_map_entry_hash (const void *entry)
{
const struct ssa_name_map_entry *en = entry;
return SSA_NAME_VERSION (en->from_name);
}
static int
ssa_name_map_entry_eq (const void *in_table, const void *ssa_name)
{
const struct ssa_name_map_entry *en = in_table;
return en->from_name == ssa_name;
}
void
allocate_ssa_names (bitmap definitions, htab_t *map)
{
tree name;
struct ssa_name_map_entry *entry;
PTR *slot;
unsigned ver;
bitmap_iterator bi;
if (!*map)
*map = htab_create (10, ssa_name_map_entry_hash,
ssa_name_map_entry_eq, free);
EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
{
name = ssa_name (ver);
slot = htab_find_slot_with_hash (*map, name, SSA_NAME_VERSION (name),
INSERT);
if (*slot)
entry = *slot;
else
{
entry = xmalloc (sizeof (struct ssa_name_map_entry));
entry->from_name = name;
*slot = entry;
}
entry->to_name = duplicate_ssa_name (name, SSA_NAME_DEF_STMT (name));
}
}
static void
rewrite_to_new_ssa_names_def (def_operand_p def, tree stmt, htab_t map)
{
tree name = DEF_FROM_PTR (def);
struct ssa_name_map_entry *entry;
gcc_assert (TREE_CODE (name) == SSA_NAME);
entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
if (!entry)
return;
SET_DEF (def, entry->to_name);
SSA_NAME_DEF_STMT (entry->to_name) = stmt;
}
static void
rewrite_to_new_ssa_names_use (use_operand_p use, htab_t map)
{
tree name = USE_FROM_PTR (use);
struct ssa_name_map_entry *entry;
if (TREE_CODE (name) != SSA_NAME)
return;
entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
if (!entry)
return;
SET_USE (use, entry->to_name);
}
void
rewrite_to_new_ssa_names_bb (basic_block bb, htab_t map)
{
unsigned i;
edge e;
edge_iterator ei;
tree phi, stmt;
block_stmt_iterator bsi;
use_optype uses;
vuse_optype vuses;
def_optype defs;
v_may_def_optype v_may_defs;
v_must_def_optype v_must_defs;
stmt_ann_t ann;
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_ABNORMAL)
break;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
rewrite_to_new_ssa_names_def (PHI_RESULT_PTR (phi), phi, map);
if (e)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
}
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
uses = USE_OPS (ann);
for (i = 0; i < NUM_USES (uses); i++)
rewrite_to_new_ssa_names_use (USE_OP_PTR (uses, i), map);
defs = DEF_OPS (ann);
for (i = 0; i < NUM_DEFS (defs); i++)
rewrite_to_new_ssa_names_def (DEF_OP_PTR (defs, i), stmt, map);
vuses = VUSE_OPS (ann);
for (i = 0; i < NUM_VUSES (vuses); i++)
rewrite_to_new_ssa_names_use (VUSE_OP_PTR (vuses, i), map);
v_may_defs = V_MAY_DEF_OPS (ann);
for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
{
rewrite_to_new_ssa_names_use
(V_MAY_DEF_OP_PTR (v_may_defs, i), map);
rewrite_to_new_ssa_names_def
(V_MAY_DEF_RESULT_PTR (v_may_defs, i), stmt, map);
}
v_must_defs = V_MUST_DEF_OPS (ann);
for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
{
rewrite_to_new_ssa_names_def
(V_MUST_DEF_RESULT_PTR (v_must_defs, i), stmt, map);
rewrite_to_new_ssa_names_use
(V_MUST_DEF_KILL_PTR (v_must_defs, i), map);
}
}
FOR_EACH_EDGE (e, ei, bb->succs)
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
rewrite_to_new_ssa_names_use
(PHI_ARG_DEF_PTR_FROM_EDGE (phi, e), map);
if (e->flags & EDGE_ABNORMAL)
{
tree op = PHI_ARG_DEF_FROM_EDGE (phi, e);
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) = 1;
}
}
}
void
rewrite_to_new_ssa_names (basic_block *region, unsigned n_region, htab_t map)
{
unsigned r;
for (r = 0; r < n_region; r++)
rewrite_to_new_ssa_names_bb (region[r], map);
}
bool
tree_duplicate_sese_region (edge entry, edge exit,
basic_block *region, unsigned n_region,
basic_block *region_copy)
{
unsigned i, n_doms, ver;
bool free_region_copy = false, copying_header = false;
struct loop *loop = entry->dest->loop_father;
edge exit_copy;
bitmap definitions;
tree phi;
basic_block *doms;
htab_t ssa_name_map = NULL;
edge redirected;
bitmap_iterator bi;
if (!can_copy_bbs_p (region, n_region))
return false;
for (i = 0; i < n_region; i++)
{
if (region[i]->loop_father != loop)
return false;
if (region[i] != entry->dest
&& region[i] == loop->header)
return false;
}
loop->copy = loop;
if (loop->header == entry->dest)
{
copying_header = true;
loop->copy = loop->outer;
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
return false;
for (i = 0; i < n_region; i++)
if (region[i] != exit->src
&& dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
return false;
}
if (!region_copy)
{
region_copy = xmalloc (sizeof (basic_block) * n_region);
free_region_copy = true;
}
gcc_assert (!any_marked_for_rewrite_p ());
doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
definitions = marked_ssa_names ();
if (copying_header)
{
loop->header = exit->dest;
loop->latch = exit->src;
}
redirected = redirect_edge_and_branch (entry, entry->dest->rbi->copy);
gcc_assert (redirected != NULL);
flush_pending_stmts (entry);
set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
doms[n_doms++] = entry->dest->rbi->original;
iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
free (doms);
add_phi_args_after_copy (region_copy, n_region);
EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
{
tree name = ssa_name (ver);
phi = create_phi_node (name, exit->dest);
add_phi_arg (phi, name, exit);
add_phi_arg (phi, name, exit_copy);
SSA_NAME_DEF_STMT (name) = phi;
}
allocate_ssa_names (definitions, &ssa_name_map);
rewrite_to_new_ssa_names (region, n_region, ssa_name_map);
allocate_ssa_names (definitions, &ssa_name_map);
rewrite_to_new_ssa_names (region_copy, n_region, ssa_name_map);
htab_delete (ssa_name_map);
if (free_region_copy)
free (region_copy);
unmark_all_for_rewrite ();
BITMAP_FREE (definitions);
return true;
}
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)
{
check_bb_profile (ENTRY_BLOCK_PTR, file);
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");
check_bb_profile (EXIT_BLOCK_PTR, file);
}
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 *, basic_block bb);
static void print_succ_bbs (FILE *, basic_block bb);
static void
print_pred_bbs (FILE *file, basic_block bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
fprintf (file, "bb_%d", e->src->index);
}
static void
print_succ_bbs (FILE *file, basic_block bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
fprintf (file, "bb_%d", e->src->index);
}
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, "%sloop_%d\n", s_indent, loop->num);
fprintf (file, "%s{\n", s_indent);
FOR_EACH_BB (bb)
if (bb->loop_father == loop)
{
fprintf (file, "%s bb_%d (preds = {", s_indent, bb->index);
print_pred_bbs (file, bb);
fprintf (file, "}, succs = {");
print_succ_bbs (file, bb);
fprintf (file, "})\n");
fprintf (file, "%s {\n", s_indent);
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);
if (bsi_end_p (bsi))
return false;
return get_call_expr_in (bsi_stmt (bsi)) != NULL;
}
static bool
tree_block_ends_with_condjump_p (basic_block bb)
{
block_stmt_iterator bsi = bsi_last (bb);
if (!bsi_end_p (bsi))
{
tree stmt = bsi_stmt (bsi);
return (TREE_CODE (stmt) == COND_EXPR);
}
else return false;
}
static bool
need_fake_edge_p (tree t)
{
tree call;
call = get_call_expr_in (t);
if (call
&& !(call_expr_flags (call) & (ECF_NORETURN | 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;
e = find_edge (bb, EXIT_BLOCK_PTR);
if (e)
{
bsi_insert_on_edge (e, build_empty_stmt ());
bsi_commit_edge_inserts ();
}
}
}
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)
{
e = find_edge (bb, EXIT_BLOCK_PTR);
gcc_assert (e == NULL);
}
#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;
}
bool
tree_purge_dead_eh_edges (basic_block bb)
{
bool changed = false;
edge e;
edge_iterator ei;
tree stmt = last_stmt (bb);
if (stmt && tree_can_throw_internal (stmt))
return false;
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
if (e->flags & EDGE_EH)
{
remove_edge (e);
changed = true;
}
else
ei_next (&ei);
}
if (changed)
free_dominance_info (CDI_DOMINATORS);
return changed;
}
bool
tree_purge_all_dead_eh_edges (bitmap blocks)
{
bool changed = false;
unsigned i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
{
changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
}
return changed;
}
static void
tree_execute_on_growing_pred (edge e)
{
basic_block bb = e->dest;
if (phi_nodes (bb))
reserve_phi_args_for_new_edge (bb);
}
static void
tree_execute_on_shrinking_pred (edge e)
{
if (phi_nodes (e->dest))
remove_phi_args (e);
}
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,
tree_execute_on_growing_pred,
tree_execute_on_shrinking_pred,
};
static void
split_critical_edges (void)
{
basic_block bb;
edge e;
edge_iterator ei;
start_recording_case_labels ();
FOR_ALL_BB (bb)
{
FOR_EACH_EDGE (e, ei, bb->succs)
if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
{
split_edge (e);
}
}
end_recording_case_labels ();
}
struct tree_opt_pass pass_split_crit_edges =
{
"crited",
NULL,
split_critical_edges,
NULL,
NULL,
0,
TV_TREE_SPLIT_EDGES,
PROP_cfg,
PROP_no_crit_edges,
0,
0,
TODO_dump_func,
0
};
tree
gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
{
tree t, new_stmt, orig_stmt;
if (is_gimple_val (exp))
return exp;
t = make_rename_temp (type, NULL);
new_stmt = build (MODIFY_EXPR, type, t, exp);
orig_stmt = bsi_stmt (*bsi);
SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
return t;
}
tree
gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
tree type, tree a, tree b, tree c)
{
tree ret;
ret = fold (build3 (code, type, a, b, c));
STRIP_NOPS (ret);
return gimplify_val (bsi, type, ret);
}
tree
gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
tree type, tree a, tree b)
{
tree ret;
ret = fold (build2 (code, type, a, b));
STRIP_NOPS (ret);
return gimplify_val (bsi, type, ret);
}
tree
gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
tree a)
{
tree ret;
ret = fold (build1 (code, type, a));
STRIP_NOPS (ret);
return gimplify_val (bsi, type, ret);
}
static void
execute_warn_function_return (void)
{
#ifdef USE_MAPPED_LOCATION
source_location location;
#else
location_t *locus;
#endif
tree last;
edge e;
edge_iterator ei;
if (warn_missing_noreturn
&& !TREE_THIS_VOLATILE (cfun->decl)
&& EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
&& !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)
&& EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
{
#ifdef USE_MAPPED_LOCATION
location = UNKNOWN_LOCATION;
#else
locus = NULL;
#endif
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
{
last = last_stmt (e->src);
if (TREE_CODE (last) == RETURN_EXPR
#ifdef USE_MAPPED_LOCATION
&& (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
#else
&& (locus = EXPR_LOCUS (last)) != NULL)
#endif
break;
}
#ifdef USE_MAPPED_LOCATION
if (location == UNKNOWN_LOCATION)
location = cfun->function_end_locus;
warning ("%H%<noreturn%> function does return", &location);
#else
if (!locus)
locus = &cfun->function_end_locus;
warning ("%H%<noreturn%> function does return", locus);
#endif
}
else if (warn_return_type
&& !TREE_NO_WARNING (cfun->decl)
&& EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
&& !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
{
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
{
tree last = last_stmt (e->src);
if (TREE_CODE (last) == RETURN_EXPR
&& TREE_OPERAND (last, 0) == NULL)
{
#ifdef USE_MAPPED_LOCATION
location = EXPR_LOCATION (last);
if (location == UNKNOWN_LOCATION)
location = cfun->function_end_locus;
warning ("%Hcontrol reaches end of non-void function", &location);
#else
locus = EXPR_LOCUS (last);
if (!locus)
locus = &cfun->function_end_locus;
warning ("%Hcontrol reaches end of non-void function", locus);
#endif
TREE_NO_WARNING (cfun->decl) = 1;
break;
}
}
}
}
void
extract_true_false_edges_from_block (basic_block b,
edge *true_edge,
edge *false_edge)
{
edge e = EDGE_SUCC (b, 0);
if (e->flags & EDGE_TRUE_VALUE)
{
*true_edge = e;
*false_edge = EDGE_SUCC (b, 1);
}
else
{
*false_edge = e;
*true_edge = EDGE_SUCC (b, 1);
}
}
struct tree_opt_pass pass_warn_function_return =
{
NULL,
NULL,
execute_warn_function_return,
NULL,
NULL,
0,
0,
PROP_cfg,
0,
0,
0,
0,
0
};
#include "gt-tree-cfg.h"