X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-dce.c;h=3c7504696826f9411e0426469cb790a0b01e2882;hb=6a167a57b73f180e3bdb2482a43db877c73f3084;hp=15c2ee417ff389777e731ba407a02908f9356df0;hpb=2a1990e9c656063ab626fab258ae2d418378c76d;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c index 15c2ee417ff..3c750469682 100644 --- a/gcc/tree-ssa-dce.c +++ b/gcc/tree-ssa-dce.c @@ -1,5 +1,6 @@ /* Dead code elimination pass for the GNU compiler. - Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008 + Free Software Foundation, Inc. Contributed by Ben Elliston and Andrew MacLeod Adapted to use control dependence by Steven Bosscher, SUSE Labs. @@ -8,7 +9,7 @@ This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the -Free Software Foundation; either version 2, or (at your option) any +Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT @@ -17,9 +18,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 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, 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301, USA. */ +along with GCC; see the file COPYING3. If not see +. */ /* Dead code elimination. @@ -59,14 +59,14 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "tree.h" #include "diagnostic.h" #include "tree-flow.h" -#include "tree-gimple.h" +#include "gimple.h" #include "tree-dump.h" #include "tree-pass.h" #include "timevar.h" #include "flags.h" #include "cfgloop.h" #include "tree-scalar-evolution.h" - + static struct stmt_stats { int total; @@ -75,7 +75,9 @@ static struct stmt_stats int removed_phis; } stats; -static VEC(tree,heap) *worklist; +#define STMT_NECESSARY GF_PLF_1 + +static VEC(gimple,heap) *worklist; /* Vector indicating an SSA name has already been processed and marked as necessary. */ @@ -105,42 +107,14 @@ static sbitmap visited_control_parents; to be recomputed. */ static bool cfg_altered; -/* 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) \ - { \ - bitmap_iterator bi; \ - \ - EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[N], 0, EDGE_NUMBER, bi) \ - { \ - CODE; \ - } \ - } - -/* Local function prototypes. */ -static inline void set_control_dependence_map_bit (basic_block, int); -static inline void clear_control_dependence_bitmap (basic_block); -static void find_all_control_dependences (struct edge_list *); -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, bool); - -static void mark_stmt_if_obviously_necessary (tree, bool); -static void find_obviously_necessary_stmts (struct edge_list *); - -static void mark_control_dependent_edges_necessary (basic_block, struct edge_list *); -static void propagate_necessity (struct edge_list *); - -static void eliminate_unnecessary_stmts (void); -static void remove_dead_phis (basic_block); -static void remove_dead_stmt (block_stmt_iterator *, basic_block); - -static void print_stats (void); -static void tree_dce_init (bool); -static void tree_dce_done (bool); - +/* 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)) + + /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */ static inline void set_control_dependence_map_bit (basic_block bb, int edge_index) @@ -152,24 +126,33 @@ set_control_dependence_map_bit (basic_block bb, int 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]); } -/* Record all blocks' control dependences on all edges in the edge - list EL, ala Morgan, Section 3.6. */ -static void -find_all_control_dependences (struct edge_list *el) +/* Find the immediate postdominator PDOM of the specified basic block BLOCK. + This function is necessary because some blocks have negative numbers. */ + +static inline basic_block +find_pdom (basic_block block) { - int i; + gcc_assert (block != ENTRY_BLOCK_PTR); - for (i = 0; i < NUM_EDGES (el); ++i) - find_control_dependence (el, i); + if (block == EXIT_BLOCK_PTR) + return EXIT_BLOCK_PTR; + else + { + basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block); + if (! bb) + return EXIT_BLOCK_PTR; + return bb; + } } + /* Determine all blocks' control dependences on the given edge with edge_list EL index EDGE_INDEX, ala Morgan, Section 3.6. */ @@ -202,57 +185,48 @@ find_control_dependence (struct edge_list *el, int edge_index) } } -/* Find the immediate postdominator PDOM of the specified basic block BLOCK. - This function is necessary because some blocks have negative numbers. */ -static inline basic_block -find_pdom (basic_block block) +/* Record all blocks' control dependences on all edges in the edge + list EL, ala Morgan, Section 3.6. */ + +static void +find_all_control_dependences (struct edge_list *el) { - gcc_assert (block != ENTRY_BLOCK_PTR); + int i; - if (block == EXIT_BLOCK_PTR) - return EXIT_BLOCK_PTR; - else - { - basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block); - if (! bb) - return EXIT_BLOCK_PTR; - return bb; - } + for (i = 0; i < NUM_EDGES (el); ++i) + find_control_dependence (el, i); } - -#define NECESSARY(stmt) stmt->common.asm_written_flag /* If STMT is not already marked necessary, mark it, and add it to the worklist if ADD_TO_WORKLIST is true. */ static inline void -mark_stmt_necessary (tree stmt, bool add_to_worklist) +mark_stmt_necessary (gimple stmt, bool add_to_worklist) { gcc_assert (stmt); - gcc_assert (!DECL_P (stmt)); - if (NECESSARY (stmt)) + if (gimple_plf (stmt, STMT_NECESSARY)) return; if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Marking useful stmt: "); - print_generic_stmt (dump_file, stmt, TDF_SLIM); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); fprintf (dump_file, "\n"); } - NECESSARY (stmt) = 1; + gimple_set_plf (stmt, STMT_NECESSARY, true); if (add_to_worklist) - VEC_safe_push (tree, heap, worklist, stmt); + VEC_safe_push (gimple, heap, worklist, stmt); } -/* Mark the statement defining operand OP as necessary. PHIONLY is true - if we should only mark it necessary if it is a phi node. */ + +/* Mark the statement defining operand OP as necessary. */ static inline void -mark_operand_necessary (tree op, bool phionly) +mark_operand_necessary (tree op) { - tree stmt; + gimple stmt; int ver; gcc_assert (op); @@ -265,15 +239,13 @@ mark_operand_necessary (tree op, bool phionly) stmt = SSA_NAME_DEF_STMT (op); gcc_assert (stmt); - if (NECESSARY (stmt) - || IS_EMPTY_STMT (stmt) - || (phionly && TREE_CODE (stmt) != PHI_NODE)) + if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt)) return; - NECESSARY (stmt) = 1; - VEC_safe_push (tree, heap, worklist, stmt); + gimple_set_plf (stmt, STMT_NECESSARY, true); + VEC_safe_push (gimple, heap, worklist, stmt); } - + /* Mark STMT as necessary if it obviously is. Add it to the worklist if it can make other statements necessary. @@ -282,76 +254,76 @@ mark_operand_necessary (tree op, bool phionly) necessary. */ static void -mark_stmt_if_obviously_necessary (tree stmt, bool aggressive) +mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive) { - stmt_ann_t ann; - tree op; - + tree lhs = NULL_TREE; /* 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)) + && stmt_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 - they are control flow, and we have no way of knowing whether they can be - removed. DCE can eliminate all the other statements in a block, and CFG - can then remove the block and labels. */ - switch (TREE_CODE (stmt)) + /* Statements that are implicitly live. Most function calls, asm + and return statements are required. Labels and GIMPLE_BIND nodes + are kept because they are control flow, and we have no way of + knowing whether they can be removed. DCE can eliminate all the + other statements in a block, and CFG can then remove the block + and labels. */ + switch (gimple_code (stmt)) { - case BIND_EXPR: - case LABEL_EXPR: - case CASE_LABEL_EXPR: + case GIMPLE_PREDICT: + case GIMPLE_LABEL: mark_stmt_necessary (stmt, false); return; - case ASM_EXPR: - case RESX_EXPR: - case RETURN_EXPR: + case GIMPLE_ASM: + case GIMPLE_RESX: + case GIMPLE_RETURN: + case GIMPLE_CHANGE_DYNAMIC_TYPE: mark_stmt_necessary (stmt, true); return; - case CALL_EXPR: + case GIMPLE_CALL: /* Most, but not all function calls are required. Function calls that produce no result and have no side effects (i.e. const pure functions) are unnecessary. */ - if (TREE_SIDE_EFFECTS (stmt)) - mark_stmt_necessary (stmt, true); - return; - - case MODIFY_EXPR: - op = get_call_expr_in (stmt); - if (op && TREE_SIDE_EFFECTS (op)) + if (gimple_has_side_effects (stmt)) { mark_stmt_necessary (stmt, true); return; } - + if (!gimple_call_lhs (stmt)) + return; + lhs = gimple_call_lhs (stmt); + /* Fall through */ + + case GIMPLE_ASSIGN: + if (!lhs) + lhs = gimple_assign_lhs (stmt); /* These values are mildly magic bits of the EH runtime. We can't see the entire lifetime of these values until landing pads are generated. */ - if (TREE_CODE (TREE_OPERAND (stmt, 0)) == EXC_PTR_EXPR - || TREE_CODE (TREE_OPERAND (stmt, 0)) == FILTER_EXPR) + if (TREE_CODE (lhs) == EXC_PTR_EXPR + || TREE_CODE (lhs) == FILTER_EXPR) { mark_stmt_necessary (stmt, true); return; } break; - case GOTO_EXPR: + case GIMPLE_GOTO: gcc_assert (!simple_goto_p (stmt)); mark_stmt_necessary (stmt, true); return; - case COND_EXPR: - gcc_assert (EDGE_COUNT (bb_for_stmt (stmt)->succs) == 2); + case GIMPLE_COND: + gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2); /* Fall through. */ - case SWITCH_EXPR: + case GIMPLE_SWITCH: if (! aggressive) mark_stmt_necessary (stmt, true); break; @@ -360,12 +332,10 @@ mark_stmt_if_obviously_necessary (tree stmt, bool aggressive) break; } - ann = stmt_ann (stmt); - /* If the statement has volatile operands, it needs to be preserved. Same for statements that can alter control flow in unpredictable ways. */ - if (ann->has_volatile_ops || is_ctrl_altering_stmt (stmt)) + if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt)) { mark_stmt_necessary (stmt, true); return; @@ -379,7 +349,38 @@ mark_stmt_if_obviously_necessary (tree stmt, bool aggressive) return; } - + + +/* Make corresponding control dependent edges necessary. We only + have to do this once for each basic block, so we clear the bitmap + after we're done. */ +static void +mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) +{ + bitmap_iterator bi; + unsigned edge_number; + + gcc_assert (bb != EXIT_BLOCK_PTR); + + if (bb == ENTRY_BLOCK_PTR) + return; + + EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number) + { + gimple stmt; + basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); + + if (TEST_BIT (last_stmt_necessary, cd_bb->index)) + continue; + SET_BIT (last_stmt_necessary, cd_bb->index); + + stmt = last_stmt (cd_bb); + if (stmt && is_ctrl_stmt (stmt)) + mark_stmt_necessary (stmt, true); + } +} + + /* Find obviously necessary statements. These are things like most function calls, and stores to file level variables. @@ -391,34 +392,24 @@ static void find_obviously_necessary_stmts (struct edge_list *el) { basic_block bb; - block_stmt_iterator i; + gimple_stmt_iterator gsi; edge e; + gimple phi, stmt; FOR_EACH_BB (bb) { - tree phi; - - /* Check any PHI nodes in the block. */ - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + /* PHI nodes are never inherently necessary. */ + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - NECESSARY (phi) = 0; - - /* PHIs for virtual variables do not directly affect code - generation and need not be considered inherently necessary - regardless of the bits set in their decl. - - Thus, we only need to mark PHIs for real variables which - need their result preserved as being inherently necessary. */ - if (is_gimple_reg (PHI_RESULT (phi)) - && is_global_var (SSA_NAME_VAR (PHI_RESULT (phi)))) - mark_stmt_necessary (phi, true); - } + phi = gsi_stmt (gsi); + gimple_set_plf (phi, STMT_NECESSARY, false); + } /* Check all statements in the block. */ - for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i)) + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - tree stmt = bsi_stmt (i); - NECESSARY (stmt) = 0; + stmt = gsi_stmt (gsi); + gimple_set_plf (stmt, STMT_NECESSARY, false); mark_stmt_if_obviously_necessary (stmt, el != NULL); } } @@ -436,68 +427,42 @@ find_obviously_necessary_stmts (struct edge_list *el) } } } - -/* Make corresponding control dependent edges necessary. We only - have to do this once for each basic block, so we clear the bitmap - after we're done. */ -static void -mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) -{ - unsigned edge_number; - gcc_assert (bb != EXIT_BLOCK_PTR); - if (bb == ENTRY_BLOCK_PTR) - return; - - EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number, - { - tree t; - basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); - - if (TEST_BIT (last_stmt_necessary, cd_bb->index)) - continue; - SET_BIT (last_stmt_necessary, cd_bb->index); - - 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 - the uses on each statement in the worklist, and add all feeding statements - which contribute to the calculation of this value to the worklist. +/* Propagate necessity using the operands of necessary statements. + Process the uses on each statement in the worklist, and add all + feeding statements which contribute to the calculation of this + value to the worklist. In conservative mode, EL is NULL. */ static void propagate_necessity (struct edge_list *el) { - tree i; + gimple stmt; bool aggressive = (el ? true : false); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "\nProcessing worklist:\n"); - while (VEC_length (tree, worklist) > 0) + while (VEC_length (gimple, worklist) > 0) { - /* Take `i' from worklist. */ - i = VEC_pop (tree, worklist); + /* Take STMT from worklist. */ + stmt = VEC_pop (gimple, worklist); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "processing: "); - print_generic_stmt (dump_file, i, TDF_SLIM); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); fprintf (dump_file, "\n"); } if (aggressive) { /* Mark the last statements of the basic blocks that the block - containing `i' is control dependent on, but only if we haven't + containing STMT is control dependent on, but only if we haven't already done so. */ - basic_block bb = bb_for_stmt (i); + basic_block bb = gimple_bb (stmt); if (bb != ENTRY_BLOCK_PTR && ! TEST_BIT (visited_control_parents, bb->index)) { @@ -506,7 +471,7 @@ propagate_necessity (struct edge_list *el) } } - if (TREE_CODE (i) == PHI_NODE) + if (gimple_code (stmt) == GIMPLE_PHI) { /* PHI nodes are somewhat special in that each PHI alternative has data and control dependencies. All the statements feeding the @@ -514,19 +479,20 @@ propagate_necessity (struct edge_list *el) we also consider the control dependent edges leading to the predecessor block associated with each PHI alternative as necessary. */ - int k; - for (k = 0; k < PHI_NUM_ARGS (i); k++) + size_t k; + + for (k = 0; k < gimple_phi_num_args (stmt); k++) { - tree arg = PHI_ARG_DEF (i, k); + tree arg = PHI_ARG_DEF (stmt, k); if (TREE_CODE (arg) == SSA_NAME) - mark_operand_necessary (arg, false); + mark_operand_necessary (arg); } if (aggressive) { - for (k = 0; k < PHI_NUM_ARGS (i); k++) + for (k = 0; k < gimple_phi_num_args (stmt); k++) { - basic_block arg_bb = PHI_ARG_EDGE (i, k)->src; + basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src; if (arg_bb != ENTRY_BLOCK_PTR && ! TEST_BIT (visited_control_parents, arg_bb->index)) { @@ -539,182 +505,72 @@ propagate_necessity (struct edge_list *el) else { /* Propagate through the operands. Examine all the USE, VUSE and - V_MAY_DEF operands in this statement. Mark all the statements - which feed this statement's uses as necessary. */ - ssa_op_iter iter; - tree use; - - /* The operands of V_MAY_DEF expressions are also needed as they + VDEF operands in this statement. Mark all the statements + which feed this statement's uses as necessary. The + operands of VDEF expressions are also needed as they represent potential definitions that may reach this - statement (V_MAY_DEF operands allow us to follow def-def + statement (VDEF operands allow us to follow def-def links). */ + ssa_op_iter iter; + tree use; - FOR_EACH_SSA_TREE_OPERAND (use, i, iter, SSA_OP_ALL_USES) - 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_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES) + mark_operand_necessary (use); } - - 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. */ - -static void -eliminate_unnecessary_stmts (void) -{ - basic_block bb; - block_stmt_iterator i; - - 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); - } - } - } - } - /* Remove dead PHI nodes from block BB. */ -static void +static bool remove_dead_phis (basic_block bb) { - tree prev, phi; + bool something_changed = false; + gimple_seq phis; + gimple phi; + gimple_stmt_iterator gsi; + phis = phi_nodes (bb); - prev = NULL_TREE; - phi = phi_nodes (bb); - while (phi) + for (gsi = gsi_start (phis); !gsi_end_p (gsi);) { stats.total_phis++; + phi = gsi_stmt (gsi); - if (! NECESSARY (phi)) + if (!gimple_plf (phi, STMT_NECESSARY)) { - tree next = PHI_CHAIN (phi); - + something_changed = true; if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Deleting : "); - print_generic_stmt (dump_file, phi, TDF_SLIM); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); fprintf (dump_file, "\n"); } - remove_phi_node (phi, prev); + remove_phi_node (&gsi, true); stats.removed_phis++; - phi = next; } else { - prev = phi; - phi = PHI_CHAIN (phi); + gsi_next (&gsi); } } + return something_changed; } - + + /* 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) +remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb) { - tree t = bsi_stmt (*i); - def_operand_p def_p; - - ssa_op_iter iter; + gimple stmt = gsi_stmt (*i); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Deleting : "); - print_generic_stmt (dump_file, t, TDF_SLIM); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); fprintf (dump_file, "\n"); } @@ -724,14 +580,14 @@ 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_tree_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)) + if (is_ctrl_stmt (stmt)) { basic_block post_dom_bb; /* The post dominance info has to be up-to-date. */ - gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK); + gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK); /* Get the immediate post dominator of bb. */ post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); @@ -747,7 +603,6 @@ remove_dead_stmt (block_stmt_iterator *i, basic_block bb) 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. */ @@ -760,6 +615,11 @@ remove_dead_stmt (block_stmt_iterator *i, basic_block bb) /* 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; + + /* It is not sufficient to set cfg_altered below during edge + removal, in case BB has two successors and one of them + is POST_DOM_BB. */ + cfg_altered = true; } EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE; EDGE_SUCC (bb, 0)->count = bb->count; @@ -784,38 +644,114 @@ remove_dead_stmt (block_stmt_iterator *i, basic_block bb) } } - FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter, SSA_OP_VIRTUAL_DEFS) + gsi_remove (i, true); + release_defs (stmt); +} + + +/* Eliminate unnecessary statements. Any instruction not marked as necessary + contributes nothing to the program, and can be deleted. */ + +static bool +eliminate_unnecessary_stmts (void) +{ + bool something_changed = false; + basic_block bb; + gimple_stmt_iterator gsi; + gimple stmt; + tree call; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\nEliminating unnecessary statements:\n"); + + clear_special_calls (); + FOR_EACH_BB (bb) { - tree def = DEF_FROM_PTR (def_p); - mark_sym_for_renaming (SSA_NAME_VAR (def)); + /* Remove dead PHI nodes. */ + something_changed |= remove_dead_phis (bb); } - bsi_remove (i, true); - release_defs (t); + + FOR_EACH_BB (bb) + { + /* Remove dead statements. */ + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) + { + stmt = gsi_stmt (gsi); + + stats.total++; + + /* If GSI is not necessary then remove it. */ + if (!gimple_plf (stmt, STMT_NECESSARY)) + { + remove_dead_stmt (&gsi, bb); + something_changed = true; + } + else if (is_gimple_call (stmt)) + { + call = gimple_call_fndecl (stmt); + if (call) + { + tree name; + gimple g; + + /* When LHS of var = call (); is dead, simplify it into + call (); saving one operand. */ + name = gimple_call_lhs (stmt); + if (name && TREE_CODE (name) == SSA_NAME + && !TEST_BIT (processed, SSA_NAME_VERSION (name))) + { + something_changed = true; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Deleting LHS of call: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + fprintf (dump_file, "\n"); + } + + push_stmt_changes (gsi_stmt_ptr (&gsi)); + g = gimple_copy (stmt); + gimple_call_set_lhs (g, NULL_TREE); + gsi_replace (&gsi, g, false); + maybe_clean_or_replace_eh_stmt (stmt, g); + mark_symbols_for_renaming (g); + pop_stmt_changes (gsi_stmt_ptr (&gsi)); + release_ssa_name (name); + } + notice_special_calls (stmt); + } + gsi_next (&gsi); + } + else + { + gsi_next (&gsi); + } + } + } + + return something_changed; } - + + /* Print out removed statement statistics. */ static void print_stats (void) { - if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS))) - { - float percg; + float percg; - percg = ((float) stats.removed / (float) stats.total) * 100; - fprintf (dump_file, "Removed %d of %d statements (%d%%)\n", - stats.removed, stats.total, (int) percg); + percg = ((float) stats.removed / (float) stats.total) * 100; + fprintf (dump_file, "Removed %d of %d statements (%d%%)\n", + stats.removed, stats.total, (int) percg); - if (stats.total_phis == 0) - percg = 0; - else - percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100; + if (stats.total_phis == 0) + percg = 0; + else + percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100; - fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n", - stats.removed_phis, stats.total_phis, (int) percg); - } + fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n", + stats.removed_phis, stats.total_phis, (int) percg); } - + /* Initialization for this pass. Set up the used data structures. */ static void @@ -838,7 +774,7 @@ tree_dce_init (bool aggressive) processed = sbitmap_alloc (num_ssa_names + 1); sbitmap_zero (processed); - worklist = VEC_alloc (tree, heap, 64); + worklist = VEC_alloc (gimple, heap, 64); cfg_altered = false; } @@ -861,9 +797,9 @@ tree_dce_done (bool aggressive) sbitmap_free (processed); - VEC_free (tree, heap, worklist); + VEC_free (gimple, heap, worklist); } - + /* Main routine to eliminate dead code. AGGRESSIVE controls the aggressiveness of the algorithm. @@ -878,10 +814,11 @@ tree_dce_done (bool aggressive) as the last tree SSA pass, but keep this in mind when you start experimenting with pass ordering. */ -static void +static unsigned int perform_tree_ssa_dce (bool aggressive) { struct edge_list *el = NULL; + bool something_changed = 0; tree_dce_init (aggressive); @@ -904,11 +841,11 @@ perform_tree_ssa_dce (bool aggressive) propagate_necessity (el); - mark_really_necessary_kill_operand_phis (); - eliminate_unnecessary_stmts (); + something_changed |= eliminate_unnecessary_stmts (); + something_changed |= cfg_altered; - if (aggressive) - free_dominance_info (CDI_POST_DOMINATORS); + /* We do not update postdominators, so free them unconditionally. */ + free_dominance_info (CDI_POST_DOMINATORS); /* If we removed paths in the CFG, then we need to update dominators as well. I haven't investigated the possibility @@ -916,37 +853,48 @@ perform_tree_ssa_dce (bool aggressive) if (cfg_altered) free_dominance_info (CDI_DOMINATORS); + statistics_counter_event (cfun, "Statements deleted", stats.removed); + statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis); + /* Debugging dumps. */ - if (dump_file) + if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS))) print_stats (); tree_dce_done (aggressive); free_edge_list (el); + + if (something_changed) + return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect + | TODO_remove_unused_locals); + else + return 0; } /* Pass entry points. */ static unsigned int tree_ssa_dce (void) { - perform_tree_ssa_dce (/*aggressive=*/false); - return 0; + return perform_tree_ssa_dce (/*aggressive=*/false); } 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; + unsigned int todo; + todo = perform_tree_ssa_dce (/*aggressive=*/false); + if (todo) + { + free_numbers_of_iterations_estimates (); + scev_reset (); + } + return todo; } static unsigned int tree_ssa_cd_dce (void) { - perform_tree_ssa_dce (/*aggressive=*/optimize >= 2); - return 0; + return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2); } static bool @@ -955,8 +903,10 @@ gate_dce (void) return flag_tree_dce != 0; } -struct tree_opt_pass pass_dce = +struct gimple_opt_pass pass_dce = { + { + GIMPLE_PASS, "dce", /* name */ gate_dce, /* gate */ tree_ssa_dce, /* execute */ @@ -964,21 +914,18 @@ struct tree_opt_pass pass_dce = NULL, /* next */ 0, /* static_pass_number */ TV_TREE_DCE, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + PROP_cfg | PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func - | TODO_update_ssa - | TODO_cleanup_cfg - | TODO_ggc_collect - | TODO_verify_ssa - | TODO_remove_unused_locals, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ + } }; -struct tree_opt_pass pass_dce_loop = +struct gimple_opt_pass pass_dce_loop = { + { + GIMPLE_PASS, "dceloop", /* name */ gate_dce, /* gate */ tree_ssa_dce_loop, /* execute */ @@ -986,19 +933,18 @@ struct tree_opt_pass pass_dce_loop = NULL, /* next */ 0, /* static_pass_number */ TV_TREE_DCE, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + PROP_cfg | PROP_ssa, /* 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 */ + TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ + } }; -struct tree_opt_pass pass_cd_dce = +struct gimple_opt_pass pass_cd_dce = { + { + GIMPLE_PASS, "cddce", /* name */ gate_dce, /* gate */ tree_ssa_cd_dce, /* execute */ @@ -1006,15 +952,11 @@ struct tree_opt_pass pass_cd_dce = NULL, /* next */ 0, /* static_pass_number */ TV_TREE_CD_DCE, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + PROP_cfg | PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func - | TODO_update_ssa - | TODO_cleanup_cfg - | TODO_ggc_collect - | TODO_verify_ssa - | TODO_verify_flow, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_ssa + | TODO_verify_flow /* todo_flags_finish */ + } };