/* Control flow functions for trees.
- Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
#include "except.h"
#include "cfgloop.h"
#include "cfglayout.h"
-#include "hashtab.h"
#include "tree-ssa-propagate.h"
#include "value-prof.h"
+#include "pointer-set.h"
/* This file contains functions for building the Control Flow Graph (CFG)
for a function tree. */
more persistent. The key is getting notification of changes to
the CFG (particularly edge removal, creation and redirection). */
-struct edge_to_cases_elt
-{
- /* The edge itself. Necessary for hashing and equality tests. */
- edge e;
-
- /* The case labels associated with this edge. We link these up via
- their TREE_CHAIN field, then we wipe out the TREE_CHAIN fields
- when we destroy the hash table. This prevents problems when copying
- SWITCH_EXPRs. */
- tree case_labels;
-};
-
-static htab_t edge_to_cases;
+static struct pointer_map_t *edge_to_cases;
/* CFG statistics. */
struct cfg_stats_d
n_basic_blocks = NUM_FIXED_BLOCKS;
last_basic_block = NUM_FIXED_BLOCKS;
basic_block_info = VEC_alloc (basic_block, gc, initial_cfg_capacity);
- VEC_safe_grow (basic_block, gc, basic_block_info, initial_cfg_capacity);
- memset (VEC_address (basic_block, basic_block_info), 0,
- sizeof (basic_block) * initial_cfg_capacity);
+ VEC_safe_grow_cleared (basic_block, gc, basic_block_info,
+ initial_cfg_capacity);
/* Build a mapping of labels to their associated blocks. */
label_to_block_map = VEC_alloc (basic_block, gc, initial_cfg_capacity);
- VEC_safe_grow (basic_block, gc, label_to_block_map, initial_cfg_capacity);
- memset (VEC_address (basic_block, label_to_block_map),
- 0, sizeof (basic_block) * initial_cfg_capacity);
+ VEC_safe_grow_cleared (basic_block, gc, label_to_block_map,
+ initial_cfg_capacity);
SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
/* Adjust the size of the array. */
if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
- {
- size_t old_size = VEC_length (basic_block, basic_block_info);
- basic_block *p;
- VEC_safe_grow (basic_block, gc, basic_block_info, n_basic_blocks);
- p = VEC_address (basic_block, basic_block_info);
- memset (&p[old_size], 0,
- sizeof (basic_block) * (n_basic_blocks - old_size));
- }
+ VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks);
/* To speed up statement iterator walks, we first purge dead labels. */
cleanup_dead_labels ();
PROP_cfg, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_verify_stmts, /* todo_flags_finish */
+ TODO_verify_stmts | TODO_cleanup_cfg, /* todo_flags_finish */
0 /* letter */
};
}
/* Copy the original computed goto's destination into VAR. */
- assignment = build2_gimple (GIMPLE_MODIFY_STMT,
- var, GOTO_DESTINATION (last));
+ assignment = build_gimple_modify_stmt (var,
+ GOTO_DESTINATION (last));
bsi_insert_before (&bsi, assignment, BSI_SAME_STMT);
/* And re-vector the computed goto to the new destination. */
bb->index = last_basic_block;
bb->flags = BB_NEW;
- bb->stmt_list = h ? (tree) h : alloc_stmt_list ();
+ bb->il.tree = GGC_CNEW (struct tree_bb_info);
+ set_bb_stmt_list (bb, h ? (tree) h : alloc_stmt_list ());
/* Add the new block to the linked list of blocks. */
link_block (bb, after);
/* Grow the basic block array if needed. */
if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
{
- size_t old_size = VEC_length (basic_block, basic_block_info);
size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
- basic_block *p;
- VEC_safe_grow (basic_block, gc, basic_block_info, new_size);
- p = VEC_address (basic_block, basic_block_info);
- memset (&p[old_size], 0, sizeof (basic_block) * (new_size - old_size));
+ VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
}
/* Add the newly created block to the array. */
if (stmt
&& TREE_CODE (stmt) == COND_EXPR)
{
- tree cond = fold (COND_EXPR_COND (stmt));
- if (integer_zerop (cond))
+ tree cond;
+ bool zerop, onep;
+
+ fold_defer_overflow_warnings ();
+ cond = fold (COND_EXPR_COND (stmt));
+ zerop = integer_zerop (cond);
+ onep = integer_onep (cond);
+ fold_undefer_overflow_warnings (((zerop || onep)
+ && !TREE_NO_WARNING (stmt)),
+ stmt,
+ WARN_STRICT_OVERFLOW_CONDITIONAL);
+ if (zerop)
COND_EXPR_COND (stmt) = boolean_false_node;
- else if (integer_onep (cond))
+ else if (onep)
COND_EXPR_COND (stmt) = boolean_true_node;
}
}
/* Fold COND_EXPR_COND of each COND_EXPR. */
fold_cond_expr_cond ();
-
- /* Clean up the graph and warn for unreachable code. */
- cleanup_tree_cfg ();
}
e->goto_locus = EXPR_LOCUS (COND_EXPR_ELSE (entry));
#endif
}
-}
-/* Hashing routine for EDGE_TO_CASES. */
-
-static hashval_t
-edge_to_cases_hash (const void *p)
-{
- edge e = ((struct edge_to_cases_elt *)p)->e;
-
- /* Hash on the edge itself (which is a pointer). */
- return htab_hash_pointer (e);
+ /* We do not need the gotos anymore. */
+ COND_EXPR_THEN (entry) = NULL_TREE;
+ COND_EXPR_ELSE (entry) = NULL_TREE;
}
-/* Equality routine for EDGE_TO_CASES, edges are unique, so testing
- for equality is just a pointer comparison. */
-
-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;
-}
/* Called for each element in the hash table (P) as we delete the
edge to cases hash table.
SWITCH_EXPRs and structure sharing rules, then free the hash table
element. */
-static void
-edge_to_cases_cleanup (void *p)
+static bool
+edge_to_cases_cleanup (void *key ATTRIBUTE_UNUSED, void **value,
+ void *data ATTRIBUTE_UNUSED)
{
- struct edge_to_cases_elt *elt = (struct edge_to_cases_elt *) p;
tree t, next;
- for (t = elt->case_labels; t; t = next)
+ for (t = (tree) *value; t; t = next)
{
next = TREE_CHAIN (t);
TREE_CHAIN (t) = NULL;
}
- free (p);
+
+ *value = NULL;
+ return false;
}
/* Start recording information mapping edges to case labels. */
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);
+ edge_to_cases = pointer_map_create ();
}
/* Return nonzero if we are recording information for case labels. */
void
end_recording_case_labels (void)
{
- htab_delete (edge_to_cases);
+ pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
+ pointer_map_destroy (edge_to_cases);
edge_to_cases = NULL;
}
-/* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E. */
-
-static void
-record_switch_edge (edge e, tree case_label)
-{
- struct edge_to_cases_elt *elt;
- void **slot;
-
- /* Build a hash table element so we can see if E is already
- in the table. */
- elt = XNEW (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)
- {
- /* E was not in the hash table. Install E into the hash table. */
- *slot = (void *)elt;
- }
- else
- {
- /* E was already in the hash table. Free ELT as we do not need it
- anymore. */
- free (elt);
-
- /* Get the entry stored in the hash table. */
- elt = (struct edge_to_cases_elt *) *slot;
-
- /* Add it to the chain of CASE_LABEL_EXPRs referencing E. */
- TREE_CHAIN (case_label) = elt->case_labels;
- elt->case_labels = case_label;
- }
-}
-
/* If we are inside a {start,end}_recording_cases block, then return
a chain of CASE_LABEL_EXPRs from T which reference E.
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);
-
+ slot = pointer_map_contains (edge_to_cases, e);
if (slot)
- {
- elt_p = (struct edge_to_cases_elt *)*slot;
- return elt_p->case_labels;
- }
+ return (tree) *slot;
/* If we did not find E in the hash table, then this must be the first
time we have been queried for information about E & T. Add all the
n = TREE_VEC_LENGTH (vec);
for (i = 0; i < n; i++)
{
- tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
+ tree elt = TREE_VEC_ELT (vec, i);
+ tree lab = CASE_LABEL (elt);
basic_block label_bb = label_to_block (lab);
- record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i));
+ edge this_edge = find_edge (e->src, label_bb);
+
+ /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
+ a new chain. */
+ slot = pointer_map_insert (edge_to_cases, this_edge);
+ TREE_CHAIN (elt) = (tree) *slot;
+ *slot = elt;
}
- goto restart;
+
+ return (tree) *pointer_map_contains (edge_to_cases, e);
}
/* Create the edges for a SWITCH_EXPR starting at block BB.
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));
+ if (true_branch)
+ GOTO_DESTINATION (true_branch)
+ = main_block_label (GOTO_DESTINATION (true_branch));
+ if (false_branch)
+ GOTO_DESTINATION (false_branch)
+ = main_block_label (GOTO_DESTINATION (false_branch));
break;
}
tree rhs;
fold_stmt_inplace (stmt);
+ if (cfgcleanup_altered_bbs)
+ bitmap_set_bit (cfgcleanup_altered_bbs, bb_for_stmt (stmt)->index);
/* FIXME. This should go in pop_stmt_changes. */
rhs = get_rhs (stmt);
}
}
- gcc_assert (zero_imm_uses_p (name));
+ gcc_assert (has_zero_uses (name));
/* Also update the trees stored in loop structures. */
if (current_loops)
with ordering of phi nodes. This is because A is the single
predecessor of B, therefore results of the phi nodes cannot
appear as arguments of the phi nodes. */
- copy = build2_gimple (GIMPLE_MODIFY_STMT, def, use);
+ copy = build_gimple_modify_stmt (def, use);
bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
SSA_NAME_DEF_STMT (def) = copy;
+ remove_phi_node (phi, NULL, false);
}
else
- replace_uses_by (def, use);
-
- remove_phi_node (phi, NULL, false);
+ {
+ replace_uses_by (def, use);
+ remove_phi_node (phi, NULL, true);
+ }
}
/* Ensure that B follows A. */
}
/* Merge the chains. */
- last = tsi_last (a->stmt_list);
- tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
- b->stmt_list = NULL;
+ last = tsi_last (bb_stmt_list (a));
+ tsi_link_after (&last, bb_stmt_list (b), TSI_NEW_STMT);
+ set_bb_stmt_list (b, NULL_TREE);
+
+ if (cfgcleanup_altered_bbs)
+ bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
}
}
/* Remove all the instructions in the block. */
- for (i = bsi_start (bb); !bsi_end_p (i);)
+ if (bb_stmt_list (bb) != NULL_TREE)
{
- tree stmt = bsi_stmt (i);
- if (TREE_CODE (stmt) == LABEL_EXPR
- && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
- || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
+ for (i = bsi_start (bb); !bsi_end_p (i);)
{
- basic_block new_bb;
- block_stmt_iterator new_bsi;
+ tree stmt = bsi_stmt (i);
+ if (TREE_CODE (stmt) == LABEL_EXPR
+ && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
+ || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
+ {
+ basic_block new_bb;
+ block_stmt_iterator new_bsi;
- /* A non-reachable non-local label may still be referenced.
- But it no longer needs to carry the extra semantics of
- non-locality. */
- if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
+ /* A non-reachable non-local label may still be referenced.
+ But it no longer needs to carry the extra semantics of
+ non-locality. */
+ if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
+ {
+ DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
+ FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
+ }
+
+ new_bb = bb->prev_bb;
+ new_bsi = bsi_start (new_bb);
+ bsi_remove (&i, false);
+ bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
+ }
+ else
{
- DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
- FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
+ /* Release SSA definitions if we are in SSA. Note that we
+ may be called when not in SSA. For example,
+ final_cleanup calls this function via
+ cleanup_tree_cfg. */
+ if (gimple_in_ssa_p (cfun))
+ release_defs (stmt);
+
+ bsi_remove (&i, true);
}
- new_bb = bb->prev_bb;
- new_bsi = bsi_start (new_bb);
- bsi_remove (&i, false);
- bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
- }
- else
- {
- /* Release SSA definitions if we are in SSA. Note that we
- may be called when not in SSA. For example,
- final_cleanup calls this function via
- cleanup_tree_cfg. */
- if (gimple_in_ssa_p (cfun))
- release_defs (stmt);
-
- bsi_remove (&i, true);
- }
-
- /* Don't warn for removed gotos. Gotos are often removed due to
- jump threading, thus resulting in bogus warnings. Not great,
- since this way we lose warnings for gotos in the original
- program that are indeed unreachable. */
- if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
- {
+ /* Don't warn for removed gotos. Gotos are often removed due to
+ jump threading, thus resulting in bogus warnings. Not great,
+ since this way we lose warnings for gotos in the original
+ program that are indeed unreachable. */
+ if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
+ {
#ifdef USE_MAPPED_LOCATION
- if (EXPR_HAS_LOCATION (stmt))
- loc = EXPR_LOCATION (stmt);
+ if (EXPR_HAS_LOCATION (stmt))
+ loc = EXPR_LOCATION (stmt);
#else
- source_locus t;
- t = EXPR_LOCUS (stmt);
- if (t && LOCATION_LINE (*t) > 0)
- loc = t;
+ source_locus t;
+ t = EXPR_LOCUS (stmt);
+ if (t && LOCATION_LINE (*t) > 0)
+ loc = t;
#endif
+ }
}
}
#endif
remove_phi_nodes_and_edges_for_unreachable_block (bb);
+ bb->il.tree = NULL;
}
return find_taken_edge_switch_expr (bb, val);
if (computed_goto_p (stmt))
- return find_taken_edge_computed_goto (bb, TREE_OPERAND( val, 0));
+ {
+ /* Only optimize if the argument is a label, if the argument is
+ not a label then we can not construct a proper CFG.
+
+ It may be the case that we only need to allow the LABEL_REF to
+ appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
+ appear inside a LABEL_EXPR just to be safe. */
+ if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
+ && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
+ return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
+ return NULL;
+ }
gcc_unreachable ();
}
return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
}
-
-/* Add gotos that used to be represented implicitly in the CFG. */
+/* Remove block annotations and other datastructures. */
void
-disband_implicit_edges (void)
+delete_tree_cfg_annotations (void)
{
basic_block bb;
- block_stmt_iterator last;
- edge e;
- edge_iterator ei;
- tree stmt, label;
+ block_stmt_iterator bsi;
+ /* Remove annotations from every tree in the function. */
FOR_EACH_BB (bb)
- {
- last = bsi_last (bb);
- stmt = last_stmt (bb);
-
- if (stmt && TREE_CODE (stmt) == COND_EXPR)
- {
- /* Remove superfluous gotos from COND_EXPR branches. Moved
- from cfg_remove_useless_stmts here since it violates the
- invariants for tree--cfg correspondence and thus fits better
- here where we do it anyway. */
- 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)
- {
- /* Remove the RETURN_EXPR if we may fall though to the exit
- instead. */
- gcc_assert (single_succ_p (bb));
- gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
-
- if (bb->next_bb == EXIT_BLOCK_PTR
- && !TREE_OPERAND (stmt, 0))
- {
- bsi_remove (&last, true);
- single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
- }
- continue;
- }
-
- /* There can be no fallthru edge if the last statement is a control
- one. */
- if (stmt && is_ctrl_stmt (stmt))
- continue;
-
- /* Find a fallthru edge and emit the goto if necessary. */
- 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;
- }
-}
-
-/* Remove block annotations and other datastructures. */
-
-void
-delete_tree_cfg_annotations (void)
-{
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ ggc_free (stmt->base.ann);
+ stmt->base.ann = NULL;
+ }
label_to_block_map = NULL;
}
LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
if (old_len <= (unsigned) uid)
{
- basic_block *addr;
unsigned new_len = 3 * uid / 2;
- VEC_safe_grow (basic_block, gc, label_to_block_map,
- new_len);
- addr = VEC_address (basic_block, label_to_block_map);
- memset (&addr[old_len],
- 0, sizeof (basic_block) * (new_len - old_len));
+ VEC_safe_grow_cleared (basic_block, gc, label_to_block_map,
+ new_len);
}
}
else
int eh_region;
tree orig_stmt = bsi_stmt (*bsi);
+ if (stmt == orig_stmt)
+ return;
SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
set_bb_for_stmt (stmt, bsi->bb);
{
remove_stmt_from_eh_region (orig_stmt);
add_stmt_to_eh_region (stmt, eh_region);
- gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
- gimple_remove_stmt_histograms (cfun, orig_stmt);
}
}
+ gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
+ gimple_remove_stmt_histograms (cfun, orig_stmt);
delink_stmt_imm_use (orig_stmt);
*bsi_stmt_ptr (*bsi) = stmt;
mark_stmt_modified (stmt);
new_edge->count = edge_in->count;
e = redirect_edge_and_branch (edge_in, new_bb);
- gcc_assert (e);
+ gcc_assert (e == edge_in);
reinstall_phi_args (new_edge, e);
return new_bb;
}
-
-/* Return true when BB has label LABEL in it. */
-
-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;
-}
-
-
/* Callback for walk_tree, check that all elements with address taken are
properly noticed as such. The DATA is an int* that is 1 if TP was seen
inside a PHI node. */
static tree
verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
{
- htab_t htab = (htab_t) data;
- void **slot;
+ struct pointer_set_t *visited = (struct pointer_set_t *) data;
if (tree_node_can_be_shared (*tp))
{
return NULL;
}
- slot = htab_find_slot (htab, *tp, INSERT);
- if (*slot)
- return (tree) *slot;
- *slot = *tp;
+ if (pointer_set_insert (visited, *tp))
+ return *tp;
return NULL;
}
return walk_tree (&t, verify_gimple_tuples_1, NULL, NULL) != NULL;
}
+static bool eh_error_found;
+static int
+verify_eh_throw_stmt_node (void **slot, void *data)
+{
+ struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
+ struct pointer_set_t *visited = (struct pointer_set_t *) data;
+
+ if (!pointer_set_contains (visited, node->stmt))
+ {
+ error ("Dead STMT in EH table");
+ debug_generic_stmt (node->stmt);
+ eh_error_found = true;
+ }
+ return 0;
+}
+
/* Verify the GIMPLE statement chain. */
void
basic_block bb;
block_stmt_iterator bsi;
bool err = false;
- htab_t htab;
+ struct pointer_set_t *visited, *visited_stmts;
tree addr;
timevar_push (TV_TREE_STMT_VERIFY);
- htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+ visited = pointer_set_create ();
+ visited_stmts = pointer_set_create ();
FOR_EACH_BB (bb)
{
{
int phi_num_args = PHI_NUM_ARGS (phi);
+ pointer_set_insert (visited_stmts, phi);
if (bb_for_stmt (phi) != bb)
{
error ("bb_for_stmt (phi) is set to a wrong basic block");
err |= true;
}
- addr = walk_tree (&t, verify_node_sharing, htab, NULL);
+ addr = walk_tree (&t, verify_node_sharing, visited, NULL);
if (addr)
{
error ("incorrect sharing of tree nodes");
{
tree stmt = bsi_stmt (bsi);
+ pointer_set_insert (visited_stmts, stmt);
err |= verify_gimple_tuples (stmt);
if (bb_for_stmt (stmt) != bb)
bsi_next (&bsi);
err |= verify_stmt (stmt, bsi_end_p (bsi));
- addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
+ addr = walk_tree (&stmt, verify_node_sharing, visited, NULL);
if (addr)
{
error ("incorrect sharing of tree nodes");
}
}
}
+ eh_error_found = false;
+ if (get_eh_throw_stmt_table (cfun))
+ htab_traverse (get_eh_throw_stmt_table (cfun),
+ verify_eh_throw_stmt_node,
+ visited_stmts);
- if (err)
+ if (err | eh_error_found)
internal_error ("verify_stmts failed");
- htab_delete (htab);
+ pointer_set_destroy (visited);
+ pointer_set_destroy (visited_stmts);
verify_histograms ();
timevar_pop (TV_TREE_STMT_VERIFY);
}
edge e;
edge_iterator ei;
- if (ENTRY_BLOCK_PTR->stmt_list)
+ if (ENTRY_BLOCK_PTR->il.tree)
{
- error ("ENTRY_BLOCK has a statement list associated with it");
+ error ("ENTRY_BLOCK has IL associated with it");
err = 1;
}
- if (EXIT_BLOCK_PTR->stmt_list)
+ if (EXIT_BLOCK_PTR->il.tree)
{
- error ("EXIT_BLOCK has a statement list associated with it");
+ error ("EXIT_BLOCK has IL associated with it");
err = 1;
}
{
edge true_edge;
edge false_edge;
- if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
- || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
+
+ if (COND_EXPR_THEN (stmt) != NULL_TREE
+ || COND_EXPR_ELSE (stmt) != NULL_TREE)
{
- error ("structured COND_EXPR at the end of bb %d", bb->index);
+ error ("COND_EXPR with code in branches at the end of bb %d",
+ bb->index);
err = 1;
}
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",
- 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",
- bb->index);
- err = 1;
- }
}
break;
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;
+ /* For COND_EXPR, we only need to redirect the edge. */
break;
case GOTO_EXPR:
return e;
}
+/* Returns true if it is possible to remove edge E by redirecting
+ it to the destination of the other edge from E->src. */
+
+static bool
+tree_can_remove_branch_p (edge e)
+{
+ if (e->flags & EDGE_ABNORMAL)
+ return false;
+
+ return true;
+}
/* Simple wrapper, as we can always redirect fallthru edges. */
{
block_stmt_iterator bsi;
tree_stmt_iterator tsi_tgt;
- tree act;
+ tree act, list;
basic_block new_bb;
edge e;
edge_iterator ei;
brings ugly quadratic memory consumption in the inliner.
(We are still quadratic since we need to update stmt BB pointers,
sadly.) */
- new_bb->stmt_list = tsi_split_statement_list_before (&bsi.tsi);
- for (tsi_tgt = tsi_start (new_bb->stmt_list);
+ list = tsi_split_statement_list_before (&bsi.tsi);
+ set_bb_stmt_list (new_bb, list);
+ for (tsi_tgt = tsi_start (list);
!tsi_end_p (tsi_tgt); tsi_next (&tsi_tgt))
change_bb_for_stmt (tsi_stmt (tsi_tgt), new_bb);
if (p->new_label_map)
{
struct tree_map in, *out;
- in.from = t;
+ in.base.from = t;
out = htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
if (out)
*tp = t = out->to;
block_stmt_iterator si;
struct move_stmt_d d;
unsigned old_len, new_len;
- basic_block *addr;
+
+ /* Remove BB from dominance structures. */
+ delete_from_dominance_info (CDI_DOMINATORS, bb);
/* Link BB to the new linked list. */
move_block_after (bb, after);
/* Grow DEST_CFUN's basic block array if needed. */
cfg = dest_cfun->cfg;
cfg->x_n_basic_blocks++;
- if (bb->index > cfg->x_last_basic_block)
- cfg->x_last_basic_block = bb->index;
+ if (bb->index >= cfg->x_last_basic_block)
+ cfg->x_last_basic_block = bb->index + 1;
old_len = VEC_length (basic_block, cfg->x_basic_block_info);
if ((unsigned) cfg->x_last_basic_block >= old_len)
{
new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
- VEC_safe_grow (basic_block, gc, cfg->x_basic_block_info, new_len);
- addr = VEC_address (basic_block, cfg->x_basic_block_info);
- memset (&addr[old_len], 0, sizeof (basic_block) * (new_len - old_len));
+ VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
+ new_len);
}
VEC_replace (basic_block, cfg->x_basic_block_info,
if (old_len <= (unsigned) uid)
{
new_len = 3 * uid / 2;
- VEC_safe_grow (basic_block, gc, cfg->x_label_to_block_map,
- new_len);
- addr = VEC_address (basic_block, cfg->x_label_to_block_map);
- memset (&addr[old_len], 0,
- sizeof (basic_block) * (new_len - old_len));
+ VEC_safe_grow_cleared (basic_block, gc,
+ cfg->x_label_to_block_map, new_len);
}
VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
m = xmalloc (sizeof (struct tree_map));
m->hash = DECL_UID (decl);
- m->from = decl;
+ m->base.from = decl;
m->to = create_artificial_label ();
LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
dump_function_to_file (tree fn, FILE *file, int flags)
{
tree arg, vars, var;
+ struct function *dsf;
bool ignore_topmost_bind = false, any_var = false;
basic_block bb;
tree chain;
}
fprintf (file, ")\n");
- if (flags & TDF_DETAILS)
- dump_eh_tree (file, DECL_STRUCT_FUNCTION (fn));
+ dsf = DECL_STRUCT_FUNCTION (fn);
+ if (dsf && (flags & TDF_DETAILS))
+ dump_eh_tree (file, dsf);
+
if (flags & TDF_RAW)
{
dump_node (fn, TDF_SLIM | flags, file);
return changed;
}
+/* Stores all basic blocks dominated by BB to DOM_BBS. */
+
+static void
+get_all_dominated_blocks (basic_block bb, VEC (basic_block, heap) **dom_bbs)
+{
+ basic_block son;
+
+ VEC_safe_push (basic_block, heap, *dom_bbs, bb);
+ for (son = first_dom_son (CDI_DOMINATORS, bb);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ get_all_dominated_blocks (son, dom_bbs);
+}
+
+/* Removes edge E and all the blocks dominated by it, and updates dominance
+ information. The IL in E->src needs to be updated separately.
+ If dominance info is not available, only the edge E is removed.*/
+
+void
+remove_edge_and_dominated_blocks (edge e)
+{
+ VEC (basic_block, heap) *bbs_to_remove = NULL;
+ VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
+ bitmap df, df_idom;
+ edge f;
+ edge_iterator ei;
+ bool none_removed = false;
+ unsigned i;
+ basic_block bb, dbb;
+ bitmap_iterator bi;
+
+ if (!dom_computed[CDI_DOMINATORS])
+ {
+ remove_edge (e);
+ return;
+ }
+
+ /* No updating is needed for edges to exit. */
+ if (e->dest == EXIT_BLOCK_PTR)
+ {
+ if (cfgcleanup_altered_bbs)
+ bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
+ remove_edge (e);
+ return;
+ }
+
+ /* First, we find the basic blocks to remove. If E->dest has a predecessor
+ that is not dominated by E->dest, then this set is empty. Otherwise,
+ all the basic blocks dominated by E->dest are removed.
+
+ Also, to DF_IDOM we store the immediate dominators of the blocks in
+ the dominance frontier of E (i.e., of the successors of the
+ removed blocks, if there are any, and of E->dest otherwise). */
+ FOR_EACH_EDGE (f, ei, e->dest->preds)
+ {
+ if (f == e)
+ continue;
+
+ if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
+ {
+ none_removed = true;
+ break;
+ }
+ }
+
+ df = BITMAP_ALLOC (NULL);
+ df_idom = BITMAP_ALLOC (NULL);
+
+ if (none_removed)
+ bitmap_set_bit (df_idom,
+ get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
+ else
+ {
+ get_all_dominated_blocks (e->dest, &bbs_to_remove);
+ for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
+ {
+ FOR_EACH_EDGE (f, ei, bb->succs)
+ {
+ if (f->dest != EXIT_BLOCK_PTR)
+ bitmap_set_bit (df, f->dest->index);
+ }
+ }
+ for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
+ bitmap_clear_bit (df, bb->index);
+
+ EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
+ {
+ bb = BASIC_BLOCK (i);
+ bitmap_set_bit (df_idom,
+ get_immediate_dominator (CDI_DOMINATORS, bb)->index);
+ }
+ }
+
+ if (cfgcleanup_altered_bbs)
+ {
+ /* Record the set of the altered basic blocks. */
+ bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
+ bitmap_ior_into (cfgcleanup_altered_bbs, df);
+ }
+
+ /* Remove E and the cancelled blocks. */
+ if (none_removed)
+ remove_edge (e);
+ else
+ {
+ for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
+ delete_basic_block (bb);
+ }
+
+ /* Update the dominance information. The immediate dominator may change only
+ for blocks whose immediate dominator belongs to DF_IDOM:
+
+ Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
+ removal. Let Z the arbitrary block such that idom(Z) = Y and
+ Z dominates X after the removal. Before removal, there exists a path P
+ from Y to X that avoids Z. Let F be the last edge on P that is
+ removed, and let W = F->dest. Before removal, idom(W) = Y (since Y
+ dominates W, and because of P, Z does not dominate W), and W belongs to
+ the dominance frontier of E. Therefore, Y belongs to DF_IDOM. */
+ EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
+ {
+ bb = BASIC_BLOCK (i);
+ for (dbb = first_dom_son (CDI_DOMINATORS, bb);
+ dbb;
+ dbb = next_dom_son (CDI_DOMINATORS, dbb))
+ VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
+ }
+
+ iterate_fix_dominators (CDI_DOMINATORS,
+ VEC_address (basic_block, bbs_to_fix_dom),
+ VEC_length (basic_block, bbs_to_fix_dom));
+
+ BITMAP_FREE (df);
+ BITMAP_FREE (df_idom);
+ VEC_free (basic_block, heap, bbs_to_remove);
+ VEC_free (basic_block, heap, bbs_to_fix_dom);
+}
+
/* Purge dead EH edges from basic block BB. */
bool
{
if (e->flags & EDGE_EH)
{
- remove_edge (e);
+ remove_edge_and_dominated_blocks (e);
changed = true;
}
else
ei_next (&ei);
}
- /* Removal of dead EH edges might change dominators of not
- just immediate successors. E.g. when bb1 is changed so that
- it no longer can throw and bb1->bb3 and bb1->bb4 are dead
- eh edges purged by this function in:
- 0
- / \
- v v
- 1-->2
- / \ |
- v v |
- 3-->4 |
- \ v
- --->5
- |
- -
- idom(bb5) must be recomputed. For now just free the dominance
- info. */
- if (changed)
- free_dominance_info (CDI_DOMINATORS);
-
return changed;
}
SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
the destination of the ELSE part. */
static void
-tree_lv_add_condition_to_bb (basic_block first_head, basic_block second_head,
- basic_block cond_bb, void *cond_e)
+tree_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
+ basic_block second_head ATTRIBUTE_UNUSED,
+ basic_block cond_bb, void *cond_e)
{
block_stmt_iterator bsi;
- tree goto1 = NULL_TREE;
- tree goto2 = NULL_TREE;
tree new_cond_expr = NULL_TREE;
tree cond_expr = (tree) cond_e;
edge e0;
/* Build new conditional expr */
- goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
- goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
- new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
+ new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr,
+ NULL_TREE, NULL_TREE);
/* Add new cond in cond_bb. */
bsi = bsi_start (cond_bb);
create_bb, /* create_basic_block */
tree_redirect_edge_and_branch,/* redirect_edge_and_branch */
tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force */
+ tree_can_remove_branch_p, /* can_remove_branch_p */
remove_bb, /* delete_basic_block */
tree_split_block, /* split_block */
tree_move_block_after, /* move_block_after */
return exp;
t = make_rename_temp (type, NULL);
- new_stmt = build2_gimple (GIMPLE_MODIFY_STMT, t, exp);
+ new_stmt = build_gimple_modify_stmt (t, exp);
orig_stmt = bsi_stmt (*bsi);
SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));