X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-dce.c;h=684ea78f15c1f41cd6da161bc70e91d1d410e9dc;hb=4e970fe40fcb363c66c7d513409dbff8e35c611c;hp=3b08aa32de4c37046ccbfea16522700299d09408;hpb=fbf0afd116585a6d67ed32259d997197a15b5f31;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c index 3b08aa32de4..684ea78f15c 100644 --- a/gcc/tree-ssa-dce.c +++ b/gcc/tree-ssa-dce.c @@ -1,5 +1,5 @@ /* Dead code elimination pass for the GNU compiler. - Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. Contributed by Ben Elliston and Andrew MacLeod Adapted to use control dependence by Steven Bosscher, SUSE Labs. @@ -18,8 +18,8 @@ for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ /* Dead code elimination. @@ -47,13 +47,13 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "system.h" #include "coretypes.h" #include "tm.h" -#include "errors.h" #include "ggc.h" /* These RTL headers are needed for basic-block.h. */ #include "rtl.h" #include "tm_p.h" #include "hard-reg-set.h" +#include "obstack.h" #include "basic-block.h" #include "tree.h" @@ -64,6 +64,8 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tree-pass.h" #include "timevar.h" #include "flags.h" +#include "cfgloop.h" +#include "tree-scalar-evolution.h" static struct stmt_stats { @@ -73,7 +75,7 @@ static struct stmt_stats int removed_phis; } stats; -static varray_type worklist; +static VEC(tree,heap) *worklist; /* Vector indicating an SSA name has already been processed and marked as necessary. */ @@ -90,12 +92,25 @@ static sbitmap last_stmt_necessary; use a bitmap for each block recording its edges. An array holds the bitmap. The Ith bit in the bitmap is set if that block is dependent on the Ith edge. */ -bitmap *control_dependence_map; +static bitmap *control_dependence_map; -/* Execute CODE for each edge (given number EDGE_NUMBER within the CODE) - for which the block with index N is control dependent. */ -#define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE) \ - EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[N], 0, EDGE_NUMBER, CODE) +/* Vector indicating that a basic block has already had all the edges + processed that it is control dependent on. */ +static sbitmap visited_control_parents; + +/* TRUE if this pass alters the CFG (by removing control statements). + FALSE otherwise. + + If this pass alters the CFG, then it will arrange for the dominators + to be recomputed. */ +static bool cfg_altered; + +/* Execute code that follows the macro for each edge (given number + EDGE_NUMBER within the CODE) for which the block with index N is + control dependent. */ +#define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \ + EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \ + (EDGE_NUMBER), (BI)) /* Local function prototypes. */ static inline void set_control_dependence_map_bit (basic_block, int); @@ -105,7 +120,7 @@ static void find_control_dependence (struct edge_list *, int); static inline basic_block find_pdom (basic_block); static inline void mark_stmt_necessary (tree, bool); -static inline void mark_operand_necessary (tree); +static inline void mark_operand_necessary (tree, bool); static void mark_stmt_if_obviously_necessary (tree, bool); static void find_obviously_necessary_stmts (struct edge_list *); @@ -127,14 +142,13 @@ set_control_dependence_map_bit (basic_block bb, int edge_index) { if (bb == ENTRY_BLOCK_PTR) return; - if (bb == EXIT_BLOCK_PTR) - abort (); + gcc_assert (bb != EXIT_BLOCK_PTR); bitmap_set_bit (control_dependence_map[bb->index], edge_index); } /* Clear all control dependences for block BB. */ -static inline -void clear_control_dependence_bitmap (basic_block bb) +static inline void +clear_control_dependence_bitmap (basic_block bb) { bitmap_clear (control_dependence_map[bb->index]); } @@ -160,13 +174,10 @@ find_control_dependence (struct edge_list *el, int edge_index) basic_block current_block; basic_block ending_block; -#ifdef ENABLE_CHECKING - if (INDEX_EDGE_PRED_BB (el, edge_index) == EXIT_BLOCK_PTR) - abort (); -#endif + gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR); if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR) - ending_block = ENTRY_BLOCK_PTR->next_bb; + ending_block = single_succ (ENTRY_BLOCK_PTR); else ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index)); @@ -192,9 +203,9 @@ find_control_dependence (struct edge_list *el, int edge_index) static inline basic_block find_pdom (basic_block block) { - if (block == ENTRY_BLOCK_PTR) - abort (); - else if (block == EXIT_BLOCK_PTR) + gcc_assert (block != ENTRY_BLOCK_PTR); + + if (block == EXIT_BLOCK_PTR) return EXIT_BLOCK_PTR; else { @@ -212,12 +223,8 @@ find_pdom (basic_block block) static inline void mark_stmt_necessary (tree stmt, bool add_to_worklist) { -#ifdef ENABLE_CHECKING - if (stmt == NULL - || stmt == error_mark_node - || (stmt && DECL_P (stmt))) - abort (); -#endif + gcc_assert (stmt); + gcc_assert (!DECL_P (stmt)); if (NECESSARY (stmt)) return; @@ -231,21 +238,19 @@ mark_stmt_necessary (tree stmt, bool add_to_worklist) NECESSARY (stmt) = 1; if (add_to_worklist) - VARRAY_PUSH_TREE (worklist, stmt); + VEC_safe_push (tree, heap, worklist, stmt); } -/* Mark the statement defining operand OP as necessary. */ +/* Mark the statement defining operand OP as necessary. PHIONLY is true + if we should only mark it necessary if it is a phi node. */ static inline void -mark_operand_necessary (tree op) +mark_operand_necessary (tree op, bool phionly) { tree stmt; int ver; -#ifdef ENABLE_CHECKING - if (op == NULL) - abort (); -#endif + gcc_assert (op); ver = SSA_NAME_VERSION (op); if (TEST_BIT (processed, ver)) @@ -253,21 +258,19 @@ mark_operand_necessary (tree op) SET_BIT (processed, ver); stmt = SSA_NAME_DEF_STMT (op); -#ifdef ENABLE_CHECKING - if (stmt == NULL) - abort (); -#endif + gcc_assert (stmt); if (NECESSARY (stmt) - || IS_EMPTY_STMT (stmt)) + || IS_EMPTY_STMT (stmt) + || (phionly && TREE_CODE (stmt) != PHI_NODE)) return; NECESSARY (stmt) = 1; - VARRAY_PUSH_TREE (worklist, stmt); + VEC_safe_push (tree, heap, worklist, stmt); } -/* Mark STMT as necessary if it is obviously is. Add it to the worklist if +/* Mark STMT as necessary if it obviously is. Add it to the worklist if it can make other statements necessary. If AGGRESSIVE is false, control statements are conservatively marked as @@ -276,11 +279,17 @@ mark_operand_necessary (tree op) static void mark_stmt_if_obviously_necessary (tree stmt, bool aggressive) { - v_may_def_optype v_may_defs; - v_must_def_optype v_must_defs; stmt_ann_t ann; - tree op, def; - ssa_op_iter iter; + tree op; + + /* With non-call exceptions, we have to assume that all statements could + throw. If a statement may throw, it is inherently necessary. */ + if (flag_non_call_exceptions + && tree_could_throw_p (stmt)) + { + mark_stmt_necessary (stmt, true); + return; + } /* Statements that are implicitly live. Most function calls, asm and return statements are required. Labels and BIND_EXPR nodes are kept because @@ -329,22 +338,12 @@ mark_stmt_if_obviously_necessary (tree stmt, bool aggressive) break; case GOTO_EXPR: - if (! simple_goto_p (stmt)) - mark_stmt_necessary (stmt, true); + gcc_assert (!simple_goto_p (stmt)); + mark_stmt_necessary (stmt, true); return; case COND_EXPR: - if (GOTO_DESTINATION (COND_EXPR_THEN (stmt)) - == GOTO_DESTINATION (COND_EXPR_ELSE (stmt))) - { - /* A COND_EXPR is obviously dead if the target labels are the same. - We cannot kill the statement at this point, so to prevent the - statement from being marked necessary, we replace the condition - with a constant. The stmt is killed later on in cfg_cleanup. */ - COND_EXPR_COND (stmt) = integer_zero_node; - modify_stmt (stmt); - return; - } + gcc_assert (EDGE_COUNT (bb_for_stmt (stmt)->succs) == 2); /* Fall through. */ case SWITCH_EXPR: @@ -367,91 +366,10 @@ mark_stmt_if_obviously_necessary (tree stmt, bool aggressive) return; } - get_stmt_operands (stmt); - - FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) - { - if (is_global_var (SSA_NAME_VAR (def))) - { - mark_stmt_necessary (stmt, true); - return; - } - } - - /* Check virtual definitions. If we get here, the only virtual - definitions we should see are those generated by assignment - statements. */ - v_may_defs = V_MAY_DEF_OPS (ann); - v_must_defs = V_MUST_DEF_OPS (ann); - if (NUM_V_MAY_DEFS (v_may_defs) > 0 || NUM_V_MUST_DEFS (v_must_defs) > 0) + if (is_hidden_global_store (stmt)) { - tree lhs; - -#if defined ENABLE_CHECKING - if (TREE_CODE (stmt) != MODIFY_EXPR) - abort (); -#endif - - /* Note that we must not check the individual virtual operands - here. In particular, if this is an aliased store, we could - end up with something like the following (SSA notation - redacted for brevity): - - foo (int *p, int i) - { - int x; - p_1 = (i_2 > 3) ? &x : p_1; - - # x_4 = V_MAY_DEF - *p_1 = 5; - - return 2; - } - - Notice that the store to '*p_1' should be preserved, if we - were to check the virtual definitions in that store, we would - not mark it needed. This is because 'x' is not a global - variable. - - Therefore, we check the base address of the LHS. If the - address is a pointer, we check if its name tag or type tag is - a global variable. Otherwise, we check if the base variable - is a global. */ - lhs = TREE_OPERAND (stmt, 0); - if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r') - lhs = get_base_address (lhs); - - if (lhs == NULL_TREE) - { - /* If LHS is NULL, it means that we couldn't get the base - address of the reference. In which case, we should not - remove this store. */ - mark_stmt_necessary (stmt, true); - } - else if (DECL_P (lhs)) - { - /* If the store is to a global symbol, we need to keep it. */ - if (is_global_var (lhs)) - mark_stmt_necessary (stmt, true); - } - else if (TREE_CODE (lhs) == INDIRECT_REF) - { - tree ptr = TREE_OPERAND (lhs, 0); - struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); - tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE; - tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag; - - /* If either the name tag or the type tag for PTR is a - global variable, then the store is necessary. */ - if ((nmt && is_global_var (nmt)) - || (tmt && is_global_var (tmt))) - { - mark_stmt_necessary (stmt, true); - return; - } - } - else - abort (); + mark_stmt_necessary (stmt, true); + return; } return; @@ -498,11 +416,6 @@ find_obviously_necessary_stmts (struct edge_list *el) NECESSARY (stmt) = 0; mark_stmt_if_obviously_necessary (stmt, el != NULL); } - - /* Mark this basic block as `not visited'. A block will be marked - visited when the edges that it is control dependent on have been - marked. */ - bb->flags &= ~BB_VISITED; } if (el) @@ -511,7 +424,8 @@ find_obviously_necessary_stmts (struct edge_list *el) and we currently do not have a means to recognize the finite ones. */ FOR_EACH_BB (bb) { - for (e = bb->succ; e; e = e->succ_next) + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->succs) if (e->flags & EDGE_DFS_BACK) mark_control_dependent_edges_necessary (e->dest, el); } @@ -524,17 +438,15 @@ find_obviously_necessary_stmts (struct edge_list *el) static void mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) { - int edge_number; + bitmap_iterator bi; + unsigned edge_number; -#ifdef ENABLE_CHECKING - if (bb == EXIT_BLOCK_PTR) - abort (); -#endif + gcc_assert (bb != EXIT_BLOCK_PTR); if (bb == ENTRY_BLOCK_PTR) return; - EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number, + EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number) { tree t; basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); @@ -546,7 +458,7 @@ mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) t = last_stmt (cd_bb); if (t && is_ctrl_stmt (t)) mark_stmt_necessary (t, true); - }); + } } /* Propagate necessity using the operands of necessary statements. Process @@ -564,11 +476,10 @@ propagate_necessity (struct edge_list *el) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "\nProcessing worklist:\n"); - while (VARRAY_ACTIVE_SIZE (worklist) > 0) + while (VEC_length (tree, worklist) > 0) { /* Take `i' from worklist. */ - i = VARRAY_TOP_TREE (worklist); - VARRAY_POP (worklist); + i = VEC_pop (tree, worklist); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -583,9 +494,10 @@ propagate_necessity (struct edge_list *el) containing `i' is control dependent on, but only if we haven't already done so. */ basic_block bb = bb_for_stmt (i); - if (! (bb->flags & BB_VISITED)) + if (bb != ENTRY_BLOCK_PTR + && ! TEST_BIT (visited_control_parents, bb->index)) { - bb->flags |= BB_VISITED; + SET_BIT (visited_control_parents, bb->index); mark_control_dependent_edges_necessary (bb, el); } } @@ -603,7 +515,7 @@ propagate_necessity (struct edge_list *el) { tree arg = PHI_ARG_DEF (i, k); if (TREE_CODE (arg) == SSA_NAME) - mark_operand_necessary (arg); + mark_operand_necessary (arg, false); } if (aggressive) @@ -611,9 +523,10 @@ propagate_necessity (struct edge_list *el) for (k = 0; k < PHI_NUM_ARGS (i); k++) { basic_block arg_bb = PHI_ARG_EDGE (i, k)->src; - if (! (arg_bb->flags & BB_VISITED)) + if (arg_bb != ENTRY_BLOCK_PTR + && ! TEST_BIT (visited_control_parents, arg_bb->index)) { - arg_bb->flags |= BB_VISITED; + SET_BIT (visited_control_parents, arg_bb->index); mark_control_dependent_edges_necessary (arg_bb, el); } } @@ -627,19 +540,84 @@ propagate_necessity (struct edge_list *el) ssa_op_iter iter; tree use; - get_stmt_operands (i); - /* The operands of V_MAY_DEF expressions are also needed as they represent potential definitions that may reach this statement (V_MAY_DEF operands allow us to follow def-def links). */ FOR_EACH_SSA_TREE_OPERAND (use, i, iter, SSA_OP_ALL_USES) - mark_operand_necessary (use); + mark_operand_necessary (use, false); + } + } +} + + +/* Propagate necessity around virtual phi nodes used in kill operands. + The reason this isn't done during propagate_necessity is because we don't + want to keep phis around that are just there for must-defs, unless we + absolutely have to. After we've rewritten the reaching definitions to be + correct in the previous part of the fixup routine, we can simply propagate + around the information about which of these virtual phi nodes are really + used, and set the NECESSARY flag accordingly. + Note that we do the minimum here to ensure that we keep alive the phis that + are actually used in the corrected SSA form. In particular, some of these + phis may now have all of the same operand, and will be deleted by some + other pass. */ + +static void +mark_really_necessary_kill_operand_phis (void) +{ + basic_block bb; + int i; + + /* Seed the worklist with the new virtual phi arguments and virtual + uses */ + FOR_EACH_BB (bb) + { + block_stmt_iterator bsi; + tree phi; + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + if (!is_gimple_reg (PHI_RESULT (phi)) && NECESSARY (phi)) + { + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + mark_operand_necessary (PHI_ARG_DEF (phi, i), true); + } + } + + for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) + { + tree stmt = bsi_stmt (bsi); + + if (NECESSARY (stmt)) + { + use_operand_p use_p; + ssa_op_iter iter; + FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, + SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) + { + tree use = USE_FROM_PTR (use_p); + mark_operand_necessary (use, true); + } + } } } + + /* Mark all virtual phis still in use as necessary, and all of their + arguments that are phis as necessary. */ + while (VEC_length (tree, worklist) > 0) + { + tree use = VEC_pop (tree, worklist); + + for (i = 0; i < PHI_NUM_ARGS (use); i++) + mark_operand_necessary (PHI_ARG_DEF (use, i), true); + } } + + + /* Eliminate unnecessary statements. Any instruction not marked as necessary contributes nothing to the program, and can be deleted. */ @@ -651,33 +629,36 @@ eliminate_unnecessary_stmts (void) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "\nEliminating unnecessary statements:\n"); - + clear_special_calls (); FOR_EACH_BB (bb) { /* Remove dead PHI nodes. */ remove_dead_phis (bb); + } + FOR_EACH_BB (bb) + { /* Remove dead statements. */ for (i = bsi_start (bb); ! bsi_end_p (i) ; ) { - tree t = bsi_stmt (i); - - stats.total++; - - /* If `i' is not necessary then remove it. */ - if (! NECESSARY (t)) - remove_dead_stmt (&i, bb); - else - { - tree call = get_call_expr_in (t); - if (call) - notice_special_calls (call); - bsi_next (&i); - } + tree t = bsi_stmt (i); + + stats.total++; + + /* If `i' is not necessary then remove it. */ + if (! NECESSARY (t)) + remove_dead_stmt (&i, bb); + else + { + tree call = get_call_expr_in (t); + if (call) + notice_special_calls (call); + bsi_next (&i); + } } } -} + } /* Remove dead PHI nodes from block BB. */ @@ -703,7 +684,7 @@ remove_dead_phis (basic_block bb) fprintf (dump_file, "\n"); } - remove_phi_node (phi, prev, bb); + remove_phi_node (phi, prev); stats.removed_phis++; phi = next; } @@ -715,13 +696,16 @@ remove_dead_phis (basic_block bb) } } -/* Remove dead statement pointed by iterator I. Receives the basic block BB +/* Remove dead statement pointed to by iterator I. Receives the basic block BB containing I so that we don't have to look it up. */ static void remove_dead_stmt (block_stmt_iterator *i, basic_block bb) { tree t = bsi_stmt (*i); + def_operand_p def_p; + + ssa_op_iter iter; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -736,55 +720,73 @@ remove_dead_stmt (block_stmt_iterator *i, basic_block bb) nothing to the program, then we not only remove it, but we also change the flow graph so that the current block will simply fall-thru to its immediate post-dominator. The blocks we are circumventing will be - removed by cleaup_cfg if this change in the flow graph makes them + removed by cleanup_tree_cfg if this change in the flow graph makes them unreachable. */ if (is_ctrl_stmt (t)) { basic_block post_dom_bb; - edge e; -#ifdef ENABLE_CHECKING + /* The post dominance info has to be up-to-date. */ - if (dom_computed[CDI_POST_DOMINATORS] != DOM_OK) - abort (); -#endif + gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK); /* Get the immediate post dominator of bb. */ post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); - /* Some blocks don't have an immediate post dominator. This can happen - for example with infinite loops. Removing an infinite loop is an - inappropriate transformation anyway... */ - if (! post_dom_bb) + + /* There are three particularly problematical cases. + + 1. Blocks that do not have an immediate post dominator. This + can happen with infinite loops. + + 2. Blocks that are only post dominated by the exit block. These + can also happen for infinite loops as we create fake edges + in the dominator tree. + + 3. If the post dominator has PHI nodes we may be able to compute + the right PHI args for them. + + + In each of these cases we must remove the control statement + as it may reference SSA_NAMEs which are going to be removed and + we remove all but one outgoing edge from the block. */ + if (! post_dom_bb + || post_dom_bb == EXIT_BLOCK_PTR + || phi_nodes (post_dom_bb)) + ; + else { - bsi_next (i); - return; + /* Redirect the first edge out of BB to reach POST_DOM_BB. */ + redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb); + PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL; } - - /* Redirect the first edge out of BB to reach POST_DOM_BB. */ - redirect_edge_and_branch (bb->succ, post_dom_bb); - PENDING_STMT (bb->succ) = NULL; + EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE; + EDGE_SUCC (bb, 0)->count = bb->count; /* The edge is no longer associated with a conditional, so it does not have TRUE/FALSE flags. */ - bb->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); + EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); - /* If the edge reaches any block other than the exit, then it is a - fallthru edge; if it reaches the exit, then it is not a fallthru - edge. */ - if (post_dom_bb != EXIT_BLOCK_PTR) - bb->succ->flags |= EDGE_FALLTHRU; - else - bb->succ->flags &= ~EDGE_FALLTHRU; + /* The lone outgoing edge from BB will be a fallthru edge. */ + EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU; /* Remove the remaining the outgoing edges. */ - for (e = bb->succ->succ_next; e != NULL;) + while (!single_succ_p (bb)) { - edge tmp = e; - e = e->succ_next; - remove_edge (tmp); + /* FIXME. When we remove the edge, we modify the CFG, which + in turn modifies the dominator and post-dominator tree. + Is it safe to postpone recomputing the dominator and + post-dominator tree until the end of this pass given that + the post-dominators are used above? */ + cfg_altered = true; + remove_edge (EDGE_SUCC (bb, 1)); } } - - bsi_remove (i); - release_defs (t); + + FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter, SSA_OP_VIRTUAL_DEFS) + { + tree def = DEF_FROM_PTR (def_p); + mark_sym_for_renaming (SSA_NAME_VAR (def)); + } + bsi_remove (i, true); + release_defs (t); } /* Print out removed statement statistics. */ @@ -821,10 +823,9 @@ tree_dce_init (bool aggressive) { int i; - control_dependence_map - = xmalloc (last_basic_block * sizeof (bitmap)); + control_dependence_map = XNEWVEC (bitmap, last_basic_block); for (i = 0; i < last_basic_block; ++i) - control_dependence_map[i] = BITMAP_XMALLOC (); + control_dependence_map[i] = BITMAP_ALLOC (NULL); last_stmt_necessary = sbitmap_alloc (last_basic_block); sbitmap_zero (last_stmt_necessary); @@ -833,7 +834,8 @@ tree_dce_init (bool aggressive) processed = sbitmap_alloc (num_ssa_names + 1); sbitmap_zero (processed); - VARRAY_TREE_INIT (worklist, 64, "work list"); + worklist = VEC_alloc (tree, heap, 64); + cfg_altered = false; } /* Cleanup after this pass. */ @@ -846,13 +848,16 @@ tree_dce_done (bool aggressive) int i; for (i = 0; i < last_basic_block; ++i) - BITMAP_XFREE (control_dependence_map[i]); + BITMAP_FREE (control_dependence_map[i]); free (control_dependence_map); + sbitmap_free (visited_control_parents); sbitmap_free (last_stmt_necessary); } sbitmap_free (processed); + + VEC_free (tree, heap, worklist); } /* Main routine to eliminate dead code. @@ -885,6 +890,9 @@ perform_tree_ssa_dce (bool aggressive) find_all_control_dependences (el); timevar_pop (TV_CONTROL_DEPENDENCES); + visited_control_parents = sbitmap_alloc (last_basic_block); + sbitmap_zero (visited_control_parents); + mark_dfs_back_edges (); } @@ -892,19 +900,21 @@ perform_tree_ssa_dce (bool aggressive) propagate_necessity (el); + mark_really_necessary_kill_operand_phis (); eliminate_unnecessary_stmts (); if (aggressive) free_dominance_info (CDI_POST_DOMINATORS); - cleanup_tree_cfg (); + /* If we removed paths in the CFG, then we need to update + dominators as well. I haven't investigated the possibility + of incrementally updating dominators. */ + if (cfg_altered) + free_dominance_info (CDI_DOMINATORS); /* Debugging dumps. */ if (dump_file) - { - dump_function_to_file (current_function_decl, dump_file, dump_flags); - print_stats (); - } + print_stats (); tree_dce_done (aggressive); @@ -912,16 +922,27 @@ perform_tree_ssa_dce (bool aggressive) } /* Pass entry points. */ -static void +static unsigned int tree_ssa_dce (void) { perform_tree_ssa_dce (/*aggressive=*/false); + return 0; } -static void +static unsigned int +tree_ssa_dce_loop (void) +{ + perform_tree_ssa_dce (/*aggressive=*/false); + free_numbers_of_iterations_estimates (current_loops); + scev_reset (); + return 0; +} + +static unsigned int tree_ssa_cd_dce (void) { perform_tree_ssa_dce (/*aggressive=*/optimize >= 2); + return 0; } static bool @@ -943,7 +964,33 @@ struct tree_opt_pass pass_dce = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ + TODO_dump_func + | TODO_update_ssa + | TODO_cleanup_cfg + | TODO_ggc_collect + | TODO_verify_ssa + | TODO_remove_unused_locals, /* todo_flags_finish */ + 0 /* letter */ +}; + +struct tree_opt_pass pass_dce_loop = +{ + "dceloop", /* name */ + gate_dce, /* gate */ + tree_ssa_dce_loop, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_DCE, /* tv_id */ + PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func + | TODO_update_ssa + | TODO_cleanup_cfg + | TODO_verify_ssa, /* todo_flags_finish */ + 0 /* letter */ }; struct tree_opt_pass pass_cd_dce = @@ -959,7 +1006,11 @@ struct tree_opt_pass pass_cd_dce = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_ggc_collect | TODO_verify_ssa | TODO_verify_flow - /* todo_flags_finish */ + TODO_dump_func + | TODO_update_ssa + | TODO_cleanup_cfg + | TODO_ggc_collect + | TODO_verify_ssa + | TODO_verify_flow, /* todo_flags_finish */ + 0 /* letter */ }; -