diff options
| -rw-r--r-- | gcc/ChangeLog | 26 | ||||
| -rw-r--r-- | gcc/tree-cfg.c | 165 | ||||
| -rw-r--r-- | gcc/tree-cfgcleanup.c | 308 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 2 | ||||
| -rw-r--r-- | gcc/tree-inline.c | 7 |
5 files changed, 349 insertions, 159 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 726e783..2b6d43c 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,29 @@ +2007-04-27 Zdenek Dvorak <dvorakz@suse.cz> + + * tree-cfgcleanup.c (cfgcleanup_altered_bbs): New global variable. + (remove_fallthru_edge): Use remove_edge_and_dominated_blocks. + (cleanup_control_expr_graph): Do not invalidate dominance info. + Record altered blocks. + (cleanup_control_flow, cleanup_forwarder_blocks): Removed. + (cleanup_control_flow_bb, split_bbs_on_noreturn_calls, + cleanup_tree_cfg_bb): New functions. + (remove_forwarder_block): Do not maintain the worklist of blocks. + Record altered blocks. + (cleanup_tree_cfg_1): Iterate over cfgcleanup_altered_bbs, + not over whole cfg. + (cleanup_tree_cfg): Do not iterate cleanup_tree_cfg_1. Only call + delete_unreachable_blocks if dominators are not available. + * tree-inline.c (optimize_inline_calls): Free dominance information + earlier. + * tree-flow.h (remove_edge_and_dominated_blocks, + cfgcleanup_altered_bbs): Altered. + * tree-cfg.c (replace_uses_by, tree_merge_blocks): Record altered + blocks. + (get_all_dominated_blocks, remove_edge_and_dominated_blocks): New + functions. + (tree_purge_dead_eh_edges): Use remove_edge_and_dominated_blocks, + do not invalidate dominators. + 2007-04-26 Anatoly Sokolov <aesok@post.ru> * config/avr/avr.c (avr_mcu_types): Add support for ATmega8HVA and diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index a621d9d..878ba6f 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -1199,6 +1199,8 @@ replace_uses_by (tree name, tree val) 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); @@ -1312,6 +1314,9 @@ tree_merge_blocks (basic_block a, basic_block b) 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); } @@ -5429,6 +5434,144 @@ tree_purge_dead_abnormal_call_edges (basic_block bb) 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 @@ -5446,33 +5589,13 @@ tree_purge_dead_eh_edges (basic_block bb) { 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; } diff --git a/gcc/tree-cfgcleanup.c b/gcc/tree-cfgcleanup.c index 39dcfe7..92ac237 100644 --- a/gcc/tree-cfgcleanup.c +++ b/gcc/tree-cfgcleanup.c @@ -48,6 +48,15 @@ Boston, MA 02110-1301, USA. */ #include "tree-ssa-propagate.h" #include "tree-scalar-evolution.h" +/* The set of blocks in that at least one of the following changes happened: + -- the statement at the end of the block was changed + -- the block was newly created + -- the set of the predecessors of the block changed + -- the set of the successors of the block changed + ??? Maybe we could track these changes separately, since they determine + what cleanups it makes sense to try on the block. */ +bitmap cfgcleanup_altered_bbs; + /* Remove any fallthru edge from EV. Return true if an edge was removed. */ static bool @@ -59,7 +68,7 @@ remove_fallthru_edge (VEC(edge,gc) *ev) FOR_EACH_EDGE (e, ei, ev) if ((e->flags & EDGE_FALLTHRU) != 0) { - remove_edge (e); + remove_edge_and_dominated_blocks (e); return true; } return false; @@ -124,7 +133,7 @@ cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi) taken_edge->probability += e->probability; taken_edge->count += e->count; - remove_edge (e); + remove_edge_and_dominated_blocks (e); retval = true; } else @@ -138,106 +147,82 @@ cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi) else taken_edge = single_succ_edge (bb); + bitmap_set_bit (cfgcleanup_altered_bbs, bb->index); bsi_remove (&bsi, true); taken_edge->flags = EDGE_FALLTHRU; - /* We removed some paths from the cfg. */ - free_dominance_info (CDI_DOMINATORS); - return retval; } -/* Try to remove superfluous control structures. */ +/* Try to remove superfluous control structures in basic block BB. Returns + true if anything changes. */ static bool -cleanup_control_flow (void) +cleanup_control_flow_bb (basic_block bb) { - basic_block bb; block_stmt_iterator bsi; bool retval = false; tree stmt; - /* Detect cases where a mid-block call is now known not to return. */ - if (cfun->gimple_df) - while (VEC_length (tree, MODIFIED_NORETURN_CALLS (cfun))) - { - stmt = VEC_pop (tree, MODIFIED_NORETURN_CALLS (cfun)); - bb = bb_for_stmt (stmt); - if (bb != NULL && last_stmt (bb) != stmt && noreturn_call_p (stmt)) - split_block (bb, stmt); - } - - FOR_EACH_BB (bb) + /* If the last statement of the block could throw and now cannot, + we need to prune cfg. */ + retval |= tree_purge_dead_eh_edges (bb); + + bsi = bsi_last (bb); + if (bsi_end_p (bsi)) + return retval; + + stmt = bsi_stmt (bsi); + + if (TREE_CODE (stmt) == COND_EXPR + || TREE_CODE (stmt) == SWITCH_EXPR) + retval |= cleanup_control_expr_graph (bb, bsi); + /* If we had a computed goto which has a compile-time determinable + destination, then we can eliminate the goto. */ + else if (TREE_CODE (stmt) == GOTO_EXPR + && TREE_CODE (GOTO_DESTINATION (stmt)) == ADDR_EXPR + && (TREE_CODE (TREE_OPERAND (GOTO_DESTINATION (stmt), 0)) + == LABEL_DECL)) { - bsi = bsi_last (bb); - - /* If the last statement of the block could throw and now cannot, - we need to prune cfg. */ - retval |= tree_purge_dead_eh_edges (bb); - - if (bsi_end_p (bsi)) - continue; + edge e; + tree label; + edge_iterator ei; + basic_block target_block; - stmt = bsi_stmt (bsi); - - if (TREE_CODE (stmt) == COND_EXPR - || TREE_CODE (stmt) == SWITCH_EXPR) - retval |= cleanup_control_expr_graph (bb, bsi); - /* If we had a computed goto which has a compile-time determinable - destination, then we can eliminate the goto. */ - else if (TREE_CODE (stmt) == GOTO_EXPR - && TREE_CODE (GOTO_DESTINATION (stmt)) == ADDR_EXPR - && (TREE_CODE (TREE_OPERAND (GOTO_DESTINATION (stmt), 0)) - == LABEL_DECL)) + /* First look at all the outgoing edges. Delete any outgoing + edges which do not go to the right block. For the one + edge which goes to the right block, fix up its flags. */ + label = TREE_OPERAND (GOTO_DESTINATION (stmt), 0); + target_block = label_to_block (label); + for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) { - edge e; - tree label; - edge_iterator ei; - basic_block target_block; - bool removed_edge = false; - - /* First look at all the outgoing edges. Delete any outgoing - edges which do not go to the right block. For the one - edge which goes to the right block, fix up its flags. */ - label = TREE_OPERAND (GOTO_DESTINATION (stmt), 0); - target_block = label_to_block (label); - for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) + if (e->dest != target_block) + remove_edge_and_dominated_blocks (e); + else { - if (e->dest != target_block) - { - removed_edge = true; - remove_edge (e); - } - else - { - /* Turn off the EDGE_ABNORMAL flag. */ - e->flags &= ~EDGE_ABNORMAL; - - /* And set EDGE_FALLTHRU. */ - e->flags |= EDGE_FALLTHRU; - ei_next (&ei); - } - } + /* Turn off the EDGE_ABNORMAL flag. */ + e->flags &= ~EDGE_ABNORMAL; - /* If we removed one or more edges, then we will need to fix the - dominators. It may be possible to incrementally update them. */ - if (removed_edge) - free_dominance_info (CDI_DOMINATORS); - - /* Remove the GOTO_EXPR as it is not needed. The CFG has all the - relevant information we need. */ - bsi_remove (&bsi, true); - retval = true; + /* And set EDGE_FALLTHRU. */ + e->flags |= EDGE_FALLTHRU; + ei_next (&ei); + } } - /* Check for indirect calls that have been turned into - noreturn calls. */ - else if (noreturn_call_p (stmt) && remove_fallthru_edge (bb->succs)) - { - free_dominance_info (CDI_DOMINATORS); - retval = true; - } + bitmap_set_bit (cfgcleanup_altered_bbs, bb->index); + bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index); + + /* Remove the GOTO_EXPR as it is not needed. The CFG has all the + relevant information we need. */ + bsi_remove (&bsi, true); + retval = true; } + + /* Check for indirect calls that have been turned into + noreturn calls. */ + else if (noreturn_call_p (stmt) && remove_fallthru_edge (bb->succs)) + retval = true; + return retval; } @@ -366,12 +351,10 @@ phi_alternatives_equal (basic_block dest, edge e1, edge e2) return true; } -/* Removes forwarder block BB. Returns false if this failed. If a new - forwarder block is created due to redirection of edges, it is - stored to worklist. */ +/* Removes forwarder block BB. Returns false if this failed. */ static bool -remove_forwarder_block (basic_block bb, basic_block **worklist) +remove_forwarder_block (basic_block bb) { edge succ = single_succ_edge (bb), e, s; basic_block dest = succ->dest; @@ -434,6 +417,8 @@ remove_forwarder_block (basic_block bb, basic_block **worklist) /* Redirect the edges. */ for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) { + bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index); + if (e->flags & EDGE_ABNORMAL) { /* If there is an abnormal edge, redirect it anyway, and @@ -450,15 +435,6 @@ remove_forwarder_block (basic_block bb, basic_block **worklist) for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s); } - else - { - /* The source basic block might become a forwarder. We know - that it was not a forwarder before, since it used to have - at least two outgoing edges, so we may just add it to - worklist. */ - if (tree_forwarder_block_p (s->src, false)) - *(*worklist)++ = s->src; - } } if (seen_abnormal_edge) @@ -476,6 +452,8 @@ remove_forwarder_block (basic_block bb, basic_block **worklist) } } + bitmap_set_bit (cfgcleanup_altered_bbs, dest->index); + /* Update the dominators. */ if (dom_info_available_p (CDI_DOMINATORS)) { @@ -501,65 +479,120 @@ remove_forwarder_block (basic_block bb, basic_block **worklist) return true; } -/* Removes forwarder blocks. */ +/* Split basic blocks on calls in the middle of a basic block that are now + known not to return, and remove the unreachable code. */ static bool -cleanup_forwarder_blocks (void) +split_bbs_on_noreturn_calls (void) { - basic_block bb; bool changed = false; - basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks); - basic_block *current = worklist; - - FOR_EACH_BB (bb) - { - if (tree_forwarder_block_p (bb, false)) - *current++ = bb; - } + tree stmt; + basic_block bb; - while (current != worklist) - { - bb = *--current; - changed |= remove_forwarder_block (bb, ¤t); - } + /* Detect cases where a mid-block call is now known not to return. */ + if (cfun->gimple_df) + while (VEC_length (tree, MODIFIED_NORETURN_CALLS (cfun))) + { + stmt = VEC_pop (tree, MODIFIED_NORETURN_CALLS (cfun)); + bb = bb_for_stmt (stmt); + if (bb == NULL + || last_stmt (bb) == stmt + || !noreturn_call_p (stmt)) + continue; + + changed = true; + split_block (bb, stmt); + remove_fallthru_edge (bb->succs); + } - free (worklist); return changed; } -/* Do one round of CFG cleanup. */ +/* Tries to cleanup cfg in basic block BB. Returns true if anything + changes. */ static bool -cleanup_tree_cfg_1 (void) +cleanup_tree_cfg_bb (basic_block bb) { - bool retval; + bool retval = false; - retval = cleanup_control_flow (); - retval |= delete_unreachable_blocks (); + retval = cleanup_control_flow_bb (bb); /* Forwarder blocks can carry line number information which is useful when debugging, so we only clean them up when optimizing. */ - if (optimize > 0) - { - /* cleanup_forwarder_blocks can redirect edges out of - SWITCH_EXPRs, which can get expensive. So we want to enable - recording of edge to CASE_LABEL_EXPR mappings around the call - to cleanup_forwarder_blocks. */ - start_recording_case_labels (); - retval |= cleanup_forwarder_blocks (); - end_recording_case_labels (); - } + if (optimize > 0 + && tree_forwarder_block_p (bb, false) + && remove_forwarder_block (bb)) + return true; /* Merging the blocks may create new opportunities for folding conditional branches (due to the elimination of single-valued PHI nodes). */ - retval |= merge_seq_blocks (); + if (single_succ_p (bb) + && can_merge_blocks_p (bb, single_succ (bb))) + { + merge_blocks (bb, single_succ (bb)); + return true; + } return retval; } +/* Iterate the cfg cleanups, while anything changes. */ + +static bool +cleanup_tree_cfg_1 (void) +{ + bool retval = false; + basic_block bb; + unsigned i, n; + + retval |= split_bbs_on_noreturn_calls (); + + /* Prepare the worklists of altered blocks. */ + cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL); + + /* During forwarder block cleanup, we may redirect edges out of + SWITCH_EXPRs, which can get expensive. So we want to enable + recording of edge to CASE_LABEL_EXPR. */ + start_recording_case_labels (); + + /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB, + since the basic blocks may get removed. */ + n = last_basic_block; + for (i = NUM_FIXED_BLOCKS; i < n; i++) + { + bb = BASIC_BLOCK (i); + if (bb) + retval |= cleanup_tree_cfg_bb (bb); + } + + /* Now process the altered blocks, as long as any are available. */ + while (!bitmap_empty_p (cfgcleanup_altered_bbs)) + { + i = bitmap_first_set_bit (cfgcleanup_altered_bbs); + bitmap_clear_bit (cfgcleanup_altered_bbs, i); + if (i < NUM_FIXED_BLOCKS) + continue; + + bb = BASIC_BLOCK (i); + if (!bb) + continue; + + retval |= cleanup_tree_cfg_bb (bb); + + /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn + calls. */ + retval |= split_bbs_on_noreturn_calls (); + } + + end_recording_case_labels (); + BITMAP_FREE (cfgcleanup_altered_bbs); + return retval; +} + /* Remove unreachable blocks and other miscellaneous clean up work. Return true if the flowgraph was modified, false otherwise. */ @@ -567,20 +600,26 @@ cleanup_tree_cfg_1 (void) bool cleanup_tree_cfg (void) { - bool retval, changed; + bool changed; timevar_push (TV_TREE_CLEANUP_CFG); /* Iterate until there are no more cleanups left to do. If any - iteration changed the flowgraph, set CHANGED to true. */ - changed = false; - do + iteration changed the flowgraph, set CHANGED to true. + + If dominance information is available, there cannot be any unreachable + blocks. */ + if (!dom_computed[CDI_DOMINATORS]) { - retval = cleanup_tree_cfg_1 (); - changed |= retval; + changed = delete_unreachable_blocks (); + calculate_dominance_info (CDI_DOMINATORS); } - while (retval); + else + changed = false; + changed |= cleanup_tree_cfg_1 (); + + gcc_assert (dom_computed[CDI_DOMINATORS]); compact_blocks (); #ifdef ENABLE_CHECKING @@ -602,7 +641,6 @@ cleanup_tree_cfg_loop (void) if (changed && current_loops != NULL) { bitmap changed_bbs = BITMAP_ALLOC (NULL); - calculate_dominance_info (CDI_DOMINATORS); fix_loop_structure (changed_bbs); /* This usually does nothing. But sometimes parts of cfg that originally diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 4d9b36e..b7f6585 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -778,8 +778,10 @@ extern void start_recording_case_labels (void); extern void end_recording_case_labels (void); extern basic_block move_sese_region_to_fn (struct function *, basic_block, basic_block); +void remove_edge_and_dominated_blocks (edge); /* In tree-cfgcleanup.c */ +extern bitmap cfgcleanup_altered_bbs; extern bool cleanup_tree_cfg (void); extern bool cleanup_tree_cfg_loop (void); diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c index 77d3864..ba8a71e 100644 --- a/gcc/tree-inline.c +++ b/gcc/tree-inline.c @@ -2804,6 +2804,10 @@ optimize_inline_calls (tree fn) push_gimplify_context (); + /* We make no attempts to keep dominance info up-to-date. */ + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); + /* Reach the trees by walking over the CFG, and note the enclosing basic-blocks in the call edges. */ /* We walk the blocks going forward, because inlined function bodies @@ -2840,9 +2844,6 @@ optimize_inline_calls (tree fn) fold_cond_expr_cond (); if (current_function_has_nonlocal_label) make_nonlocal_label_edges (); - /* We make no attempts to keep dominance info up-to-date. */ - free_dominance_info (CDI_DOMINATORS); - free_dominance_info (CDI_POST_DOMINATORS); /* It would be nice to check SSA/CFG/statement consistency here, but it is not possible yet - the IPA passes might make various functions to not throw and they don't care to proactively update local EH info. This is |