X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftree-ssa-dce.c;h=d6fbe622df0242da38f15789e66a315c0763641c;hp=56f17ceeee10712e6cae2ff104340989f970782c;hb=3c25489e88a7ea2937c19abff9163d9f7d8ca53a;hpb=bfad1dc2c71ec30d4293b2b0c17a18ca3f67db9b diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c index 56f17ceeee1..d6fbe622df0 100644 --- a/gcc/tree-ssa-dce.c +++ b/gcc/tree-ssa-dce.c @@ -1,25 +1,25 @@ /* 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, 2009, 2010, 2011 + Free Software Foundation, Inc. Contributed by Ben Elliston and Andrew MacLeod Adapted to use control dependence by Steven Bosscher, SUSE Labs. - + 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 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 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. @@ -47,26 +47,20 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "system.h" #include "coretypes.h" #include "tm.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" -#include "diagnostic.h" +#include "tree-pretty-print.h" +#include "gimple-pretty-print.h" +#include "basic-block.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,16 +69,21 @@ 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. */ static sbitmap processed; -/* Vector indicating that last_stmt if a basic block has already been - marked as necessary. */ +/* Vector indicating that the last statement of a basic block has already + been marked as necessary. */ static sbitmap last_stmt_necessary; +/* Vector indicating that BB contains statements that are live. */ +static sbitmap bb_contains_live_stmts; + /* Before we can determine whether a control branch is dead, we need to compute which blocks are control dependent on which edges. @@ -112,30 +111,7 @@ static bool cfg_altered; 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); -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); - /* 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) @@ -147,24 +123,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. */ @@ -197,78 +182,85 @@ 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); + if (bb_contains_live_stmts && !is_gimple_debug (stmt)) + SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index); } -/* 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); ver = SSA_NAME_VERSION (op); if (TEST_BIT (processed, ver)) - return; + { + stmt = SSA_NAME_DEF_STMT (op); + gcc_assert (gimple_nop_p (stmt) + || gimple_plf (stmt, STMT_NECESSARY)); + return; + } SET_BIT (processed, ver); 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); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "marking necessary through "); + print_generic_expr (dump_file, op, 0); + fprintf (dump_file, " stmt "); + print_gimple_stmt (dump_file, stmt, 0, 0); + } + + gimple_set_plf (stmt, STMT_NECESSARY, true); + if (bb_contains_live_stmts) + SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index); + 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. @@ -277,90 +269,102 @@ 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; - /* 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)) + if (cfun->can_throw_non_call_exceptions && 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: mark_stmt_necessary (stmt, true); return; - case CALL_EXPR: - /* 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)) - { - mark_stmt_necessary (stmt, true); - return; - } + case GIMPLE_CALL: + { + tree callee = gimple_call_fndecl (stmt); + if (callee != NULL_TREE + && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) + switch (DECL_FUNCTION_CODE (callee)) + { + case BUILT_IN_MALLOC: + case BUILT_IN_CALLOC: + case BUILT_IN_ALLOCA: + case BUILT_IN_ALLOCA_WITH_ALIGN: + return; - /* 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) - { - mark_stmt_necessary (stmt, true); + default:; + } + /* 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 (gimple_has_side_effects (stmt)) + { + mark_stmt_necessary (stmt, true); + return; + } + if (!gimple_call_lhs (stmt)) return; - } - break; + break; + } + + case GIMPLE_DEBUG: + /* Debug temps without a value are not useful. ??? If we could + easily locate the debug temp bind stmt for a use thereof, + would could refrain from marking all debug temps here, and + mark them only if they're used. */ + if (!gimple_debug_bind_p (stmt) + || gimple_debug_bind_has_value_p (stmt) + || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL) + mark_stmt_necessary (stmt, false); + return; - 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; + case GIMPLE_ASSIGN: + if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME + && TREE_CLOBBER_P (gimple_assign_rhs1 (stmt))) + return; + break; + default: 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; @@ -374,7 +378,61 @@ mark_stmt_if_obviously_necessary (tree stmt, bool aggressive) return; } - + + +/* Mark the last statement of BB as necessary. */ + +static void +mark_last_stmt_necessary (basic_block bb) +{ + gimple stmt = last_stmt (bb); + + SET_BIT (last_stmt_necessary, bb->index); + SET_BIT (bb_contains_live_stmts, bb->index); + + /* We actually mark the statement only if it is a control statement. */ + if (stmt && is_ctrl_stmt (stmt)) + mark_stmt_necessary (stmt, true); +} + + +/* Mark control dependent edges of BB as necessary. We have to do this only + once for each basic block so we set the appropriate bit after we're done. + + When IGNORE_SELF is true, ignore BB in the list of control dependences. */ + +static void +mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el, + bool ignore_self) +{ + bitmap_iterator bi; + unsigned edge_number; + bool skipped = false; + + gcc_assert (bb != EXIT_BLOCK_PTR); + + if (bb == ENTRY_BLOCK_PTR) + return; + + EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number) + { + basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); + + if (ignore_self && cd_bb == bb) + { + skipped = true; + continue; + } + + if (!TEST_BIT (last_stmt_necessary, cd_bb->index)) + mark_last_stmt_necessary (cd_bb); + } + + if (!skipped) + SET_BIT (visited_control_parents, bb->index); +} + + /* Find obviously necessary statements. These are things like most function calls, and stores to file level variables. @@ -386,123 +444,284 @@ 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; + int flags; 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); } } + /* Pure and const functions are finite and thus have no infinite loops in + them. */ + flags = flags_from_decl_or_type (current_function_decl); + if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE)) + return; + + /* Prevent the empty possibly infinite loops from being removed. */ if (el) { - /* Prevent the loops from being removed. We must keep the infinite loops, - and we currently do not have a means to recognize the finite ones. */ - FOR_EACH_BB (bb) + loop_iterator li; + struct loop *loop; + scev_initialize (); + if (mark_irreducible_loops ()) + FOR_EACH_BB (bb) + { + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->succs) + if ((e->flags & EDGE_DFS_BACK) + && (e->flags & EDGE_IRREDUCIBLE_LOOP)) + { + if (dump_file) + fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n", + e->src->index, e->dest->index); + mark_control_dependent_edges_necessary (e->dest, el, false); + } + } + + FOR_EACH_LOOP (li, loop, 0) + if (!finite_loop_p (loop)) + { + if (dump_file) + fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num); + mark_control_dependent_edges_necessary (loop->latch, el, false); + } + scev_finalize (); + } +} + + +/* Return true if REF is based on an aliased base, otherwise false. */ + +static bool +ref_may_be_aliased (tree ref) +{ + gcc_assert (TREE_CODE (ref) != WITH_SIZE_EXPR); + while (handled_component_p (ref)) + ref = TREE_OPERAND (ref, 0); + if (TREE_CODE (ref) == MEM_REF + && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR) + ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0); + return !(DECL_P (ref) + && !may_be_aliased (ref)); +} + +static bitmap visited = NULL; +static unsigned int longest_chain = 0; +static unsigned int total_chain = 0; +static unsigned int nr_walks = 0; +static bool chain_ovfl = false; + +/* Worker for the walker that marks reaching definitions of REF, + which is based on a non-aliased decl, necessary. It returns + true whenever the defining statement of the current VDEF is + a kill for REF, as no dominating may-defs are necessary for REF + anymore. DATA points to the basic-block that contains the + stmt that refers to REF. */ + +static bool +mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data) +{ + gimple def_stmt = SSA_NAME_DEF_STMT (vdef); + + /* All stmts we visit are necessary. */ + mark_operand_necessary (vdef); + + /* If the stmt lhs kills ref, then we can stop walking. */ + if (gimple_has_lhs (def_stmt) + && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME + /* The assignment is not necessarily carried out if it can throw + and we can catch it in the current function where we could inspect + the previous value. + ??? We only need to care about the RHS throwing. For aggregate + assignments or similar calls and non-call exceptions the LHS + might throw as well. */ + && !stmt_can_throw_internal (def_stmt)) + { + tree base, lhs = gimple_get_lhs (def_stmt); + HOST_WIDE_INT size, offset, max_size; + ao_ref_base (ref); + base = get_ref_base_and_extent (lhs, &offset, &size, &max_size); + /* We can get MEM[symbol: sZ, index: D.8862_1] here, + so base == refd->base does not always hold. */ + if (base == ref->base) { - edge_iterator ei; - FOR_EACH_EDGE (e, ei, bb->succs) - if (e->flags & EDGE_DFS_BACK) - mark_control_dependent_edges_necessary (e->dest, el); + /* For a must-alias check we need to be able to constrain + the accesses properly. */ + if (size != -1 && size == max_size + && ref->max_size != -1) + { + if (offset <= ref->offset + && offset + size >= ref->offset + ref->max_size) + return true; + } + /* Or they need to be exactly the same. */ + else if (ref->ref + /* Make sure there is no induction variable involved + in the references (gcc.c-torture/execute/pr42142.c). + The simplest way is to check if the kill dominates + the use. */ + && dominated_by_p (CDI_DOMINATORS, (basic_block) data, + gimple_bb (def_stmt)) + && operand_equal_p (ref->ref, lhs, 0)) + return true; } } + + /* Otherwise keep walking. */ + return false; } - -/* 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) +mark_aliased_reaching_defs_necessary (gimple stmt, tree ref) { - bitmap_iterator bi; - unsigned edge_number; + unsigned int chain; + ao_ref refd; + gcc_assert (!chain_ovfl); + ao_ref_init (&refd, ref); + chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt), + mark_aliased_reaching_defs_necessary_1, + gimple_bb (stmt), NULL); + if (chain > longest_chain) + longest_chain = chain; + total_chain += chain; + nr_walks++; +} - gcc_assert (bb != EXIT_BLOCK_PTR); +/* Worker for the walker that marks reaching definitions of REF, which + is not based on a non-aliased decl. For simplicity we need to end + up marking all may-defs necessary that are not based on a non-aliased + decl. The only job of this walker is to skip may-defs based on + a non-aliased decl. */ - if (bb == ENTRY_BLOCK_PTR) - return; +static bool +mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED, + tree vdef, void *data ATTRIBUTE_UNUSED) +{ + gimple def_stmt = SSA_NAME_DEF_STMT (vdef); - EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number) + /* We have to skip already visited (and thus necessary) statements + to make the chaining work after we dropped back to simple mode. */ + if (chain_ovfl + && TEST_BIT (processed, SSA_NAME_VERSION (vdef))) { - tree t; - basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); + gcc_assert (gimple_nop_p (def_stmt) + || gimple_plf (def_stmt, STMT_NECESSARY)); + return false; + } - if (TEST_BIT (last_stmt_necessary, cd_bb->index)) - continue; - SET_BIT (last_stmt_necessary, cd_bb->index); + /* We want to skip stores to non-aliased variables. */ + if (!chain_ovfl + && gimple_assign_single_p (def_stmt)) + { + tree lhs = gimple_assign_lhs (def_stmt); + if (!ref_may_be_aliased (lhs)) + return false; + } - t = last_stmt (cd_bb); - if (t && is_ctrl_stmt (t)) - mark_stmt_necessary (t, true); + /* We want to skip statments that do not constitute stores but have + a virtual definition. */ + if (is_gimple_call (def_stmt)) + { + tree callee = gimple_call_fndecl (def_stmt); + if (callee != NULL_TREE + && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) + switch (DECL_FUNCTION_CODE (callee)) + { + case BUILT_IN_MALLOC: + case BUILT_IN_CALLOC: + case BUILT_IN_ALLOCA: + case BUILT_IN_ALLOCA_WITH_ALIGN: + case BUILT_IN_FREE: + return false; + + default:; + } } + + mark_operand_necessary (vdef); + + return false; +} + +static void +mark_all_reaching_defs_necessary (gimple stmt) +{ + walk_aliased_vdefs (NULL, gimple_vuse (stmt), + mark_all_reaching_defs_necessary_1, NULL, &visited); } - -/* 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. + +/* Return true for PHI nodes with one or identical arguments + can be removed. */ +static bool +degenerate_phi_p (gimple phi) +{ + unsigned int i; + tree op = gimple_phi_arg_def (phi, 0); + for (i = 1; i < gimple_phi_num_args (phi); i++) + if (gimple_phi_arg_def (phi, i) != op) + return false; + return 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. In conservative mode, EL is NULL. */ static void propagate_necessity (struct edge_list *el) { - tree i; - bool aggressive = (el ? true : false); + 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 + /* Mark the last statement of the basic blocks on which the block + containing STMT is control dependent, 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)) - { - SET_BIT (visited_control_parents, bb->index); - mark_control_dependent_edges_necessary (bb, el); - } + && !TEST_BIT (visited_control_parents, bb->index)) + mark_control_dependent_edges_necessary (bb, el, false); } - if (TREE_CODE (i) == PHI_NODE) + if (gimple_code (stmt) == GIMPLE_PHI + /* We do not process virtual PHI nodes nor do we track their + necessity. */ + && is_gimple_reg (gimple_phi_result (stmt))) { /* PHI nodes are somewhat special in that each PHI alternative has data and control dependencies. All the statements feeding the @@ -510,207 +729,439 @@ 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 PHI operands it matters from where the control flow arrives + to the BB. Consider the following example: + + a=exp1; + b=exp2; + if (test) + ; + else + ; + c=PHI(a,b) + + We need to mark control dependence of the empty basic blocks, since they + contains computation of PHI operands. + + Doing so is too restrictive in the case the predecestor block is in + the loop. Consider: + + if (b) + { + int i; + for (i = 0; i<1000; ++i) + ; + j = 0; + } + return j; + + There is PHI for J in the BB containing return statement. + In this case the control dependence of predecestor block (that is + within the empty loop) also contains the block determining number + of iterations of the block that would prevent removing of empty + loop in this case. + + This scenario can be avoided by splitting critical edges. + To save the critical edge splitting pass we identify how the control + dependence would look like if the edge was split. + + Consider the modified CFG created from current CFG by splitting + edge B->C. In the postdominance tree of modified CFG, C' is + always child of C. There are two cases how chlids of C' can look + like: + + 1) C' is leaf + + In this case the only basic block C' is control dependent on is B. + + 2) C' has single child that is B + + In this case control dependence of C' is same as control + dependence of B in original CFG except for block B itself. + (since C' postdominate B in modified CFG) + + Now how to decide what case happens? There are two basic options: + + a) C postdominate B. Then C immediately postdominate B and + case 2 happens iff there is no other way from B to C except + the edge B->C. + + There is other way from B to C iff there is succesor of B that + is not postdominated by B. Testing this condition is somewhat + expensive, because we need to iterate all succesors of B. + We are safe to assume that this does not happen: we will mark B + as needed when processing the other path from B to C that is + conrol dependent on B and marking control dependencies of B + itself is harmless because they will be processed anyway after + processing control statement in B. + + b) C does not postdominate B. Always case 1 happens since there is + path from C to exit that does not go through B and thus also C'. */ + + if (aggressive && !degenerate_phi_p (stmt)) { - 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; - if (arg_bb != ENTRY_BLOCK_PTR - && ! TEST_BIT (visited_control_parents, arg_bb->index)) + basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src; + + if (gimple_bb (stmt) + != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb)) { - SET_BIT (visited_control_parents, arg_bb->index); - mark_control_dependent_edges_necessary (arg_bb, el); + if (!TEST_BIT (last_stmt_necessary, arg_bb->index)) + mark_last_stmt_necessary (arg_bb); } + else if (arg_bb != ENTRY_BLOCK_PTR + && !TEST_BIT (visited_control_parents, + arg_bb->index)) + mark_control_dependent_edges_necessary (arg_bb, el, true); } } } else { /* Propagate through the operands. Examine all the USE, VUSE and - V_MAY_DEF operands in this statement. Mark all the statements + VDEF 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 - 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, false); - } - } -} + /* If this is a call to free which is directly fed by an + allocation function do not mark that necessary through + processing the argument. */ + if (gimple_call_builtin_p (stmt, BUILT_IN_FREE)) + { + tree ptr = gimple_call_arg (stmt, 0); + gimple def_stmt; + tree def_callee; + /* If the pointer we free is defined by an allocation + function do not add the call to the worklist. */ + if (TREE_CODE (ptr) == SSA_NAME + && is_gimple_call (def_stmt = SSA_NAME_DEF_STMT (ptr)) + && (def_callee = gimple_call_fndecl (def_stmt)) + && DECL_BUILT_IN_CLASS (def_callee) == BUILT_IN_NORMAL + && (DECL_FUNCTION_CODE (def_callee) == BUILT_IN_MALLOC + || DECL_FUNCTION_CODE (def_callee) == BUILT_IN_CALLOC)) + continue; + } + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) + mark_operand_necessary (use); -/* 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. */ + use = gimple_vuse (stmt); + if (!use) + continue; -static void -mark_really_necessary_kill_operand_phis (void) -{ - basic_block bb; - int i; + /* If we dropped to simple mode make all immediately + reachable definitions necessary. */ + if (chain_ovfl) + { + mark_all_reaching_defs_necessary (stmt); + continue; + } - /* 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 statements that may load from memory (have a VUSE) we + have to mark all reaching (may-)definitions as necessary. + We partition this task into two cases: + 1) explicit loads based on decls that are not aliased + 2) implicit loads (like calls) and explicit loads not + based on decls that are not aliased (like indirect + references or loads from globals) + For 1) we mark all reaching may-defs as necessary, stopping + at dominating kills. For 2) we want to mark all dominating + references necessary, but non-aliased ones which we handle + in 1). By keeping a global visited bitmap for references + we walk for 2) we avoid quadratic behavior for those. */ + + if (is_gimple_call (stmt)) { - for (i = 0; i < PHI_NUM_ARGS (phi); i++) - mark_operand_necessary (PHI_ARG_DEF (phi, i), true); + tree callee = gimple_call_fndecl (stmt); + unsigned i; + + /* Calls to functions that are merely acting as barriers + or that only store to memory do not make any previous + stores necessary. */ + if (callee != NULL_TREE + && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL + && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET + || DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET_CHK + || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC + || DECL_FUNCTION_CODE (callee) == BUILT_IN_CALLOC + || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE + || DECL_FUNCTION_CODE (callee) == BUILT_IN_VA_END + || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA + || (DECL_FUNCTION_CODE (callee) + == BUILT_IN_ALLOCA_WITH_ALIGN) + || DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE + || DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE + || DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED)) + continue; + + /* Calls implicitly load from memory, their arguments + in addition may explicitly perform memory loads. */ + mark_all_reaching_defs_necessary (stmt); + for (i = 0; i < gimple_call_num_args (stmt); ++i) + { + tree arg = gimple_call_arg (stmt, i); + if (TREE_CODE (arg) == SSA_NAME + || is_gimple_min_invariant (arg)) + continue; + if (TREE_CODE (arg) == WITH_SIZE_EXPR) + arg = TREE_OPERAND (arg, 0); + if (!ref_may_be_aliased (arg)) + mark_aliased_reaching_defs_necessary (stmt, arg); + } } - } - - for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) - { - tree stmt = bsi_stmt (bsi); - - if (NECESSARY (stmt)) + else if (gimple_assign_single_p (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 rhs; + /* If this is a load mark things necessary. */ + rhs = gimple_assign_rhs1 (stmt); + if (TREE_CODE (rhs) != SSA_NAME + && !is_gimple_min_invariant (rhs) + && TREE_CODE (rhs) != CONSTRUCTOR) { - tree use = USE_FROM_PTR (use_p); - mark_operand_necessary (use, true); + if (!ref_may_be_aliased (rhs)) + mark_aliased_reaching_defs_necessary (stmt, rhs); + else + mark_all_reaching_defs_necessary (stmt); } } + else if (gimple_code (stmt) == GIMPLE_RETURN) + { + tree rhs = gimple_return_retval (stmt); + /* A return statement may perform a load. */ + if (rhs + && TREE_CODE (rhs) != SSA_NAME + && !is_gimple_min_invariant (rhs) + && TREE_CODE (rhs) != CONSTRUCTOR) + { + if (!ref_may_be_aliased (rhs)) + mark_aliased_reaching_defs_necessary (stmt, rhs); + else + mark_all_reaching_defs_necessary (stmt); + } + } + else if (gimple_code (stmt) == GIMPLE_ASM) + { + unsigned i; + mark_all_reaching_defs_necessary (stmt); + /* Inputs may perform loads. */ + for (i = 0; i < gimple_asm_ninputs (stmt); ++i) + { + tree op = TREE_VALUE (gimple_asm_input_op (stmt, i)); + if (TREE_CODE (op) != SSA_NAME + && !is_gimple_min_invariant (op) + && TREE_CODE (op) != CONSTRUCTOR + && !ref_may_be_aliased (op)) + mark_aliased_reaching_defs_necessary (stmt, op); + } + } + else + gcc_unreachable (); + + /* If we over-used our alias oracle budget drop to simple + mode. The cost metric allows quadratic behavior + (number of uses times number of may-defs queries) up to + a constant maximal number of queries and after that falls back to + super-linear complexity. */ + if (/* Constant but quadratic for small functions. */ + total_chain > 128 * 128 + /* Linear in the number of may-defs. */ + && total_chain > 32 * longest_chain + /* Linear in the number of uses. */ + && total_chain > nr_walks * 32) + { + chain_ovfl = true; + if (visited) + bitmap_clear (visited); + } } } - - /* 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) +} + +/* Replace all uses of NAME by underlying variable and mark it + for renaming. */ + +void +mark_virtual_operand_for_renaming (tree name) +{ + bool used = false; + imm_use_iterator iter; + use_operand_p use_p; + gimple stmt; + tree name_var; + + name_var = SSA_NAME_VAR (name); + FOR_EACH_IMM_USE_STMT (stmt, iter, name) { - tree use = VEC_pop (tree, worklist); - - for (i = 0; i < PHI_NUM_ARGS (use); i++) - mark_operand_necessary (PHI_ARG_DEF (use, i), true); + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) + SET_USE (use_p, name_var); + update_stmt (stmt); + used = true; } + if (used) + mark_sym_for_renaming (name_var); } +/* Replace all uses of result of PHI by underlying variable and mark it + for renaming. */ - - -/* Eliminate unnecessary statements. Any instruction not marked as necessary - contributes nothing to the program, and can be deleted. */ - -static void -eliminate_unnecessary_stmts (void) +void +mark_virtual_phi_result_for_renaming (gimple phi) { - 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); + fprintf (dump_file, "Marking result for renaming : "); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); + fprintf (dump_file, "\n"); } - 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); - } - } - } - } - + mark_virtual_operand_for_renaming (gimple_phi_result (phi)); +} + + /* 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)) + /* We do not track necessity of virtual PHI nodes. Instead do + very simple dead PHI removal here. */ + if (!is_gimple_reg (gimple_phi_result (phi))) { - tree next = PHI_CHAIN (phi); + /* Virtual PHI nodes with one or identical arguments + can be removed. */ + if (degenerate_phi_p (phi)) + { + tree vdef = gimple_phi_result (phi); + tree vuse = gimple_phi_arg_def (phi, 0); + use_operand_p use_p; + imm_use_iterator iter; + gimple use_stmt; + FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef) + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) + SET_USE (use_p, vuse); + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef) + && TREE_CODE (vuse) == SSA_NAME) + SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1; + } + else + gimple_set_plf (phi, STMT_NECESSARY, true); + } + + if (!gimple_plf (phi, STMT_NECESSARY)) + { + 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; + continue; } - else + + gsi_next (&gsi); + } + return something_changed; +} + +/* Forward edge E to respective POST_DOM_BB and update PHIs. */ + +static edge +forward_edge_to_pdom (edge e, basic_block post_dom_bb) +{ + gimple_stmt_iterator gsi; + edge e2 = NULL; + edge_iterator ei; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index, + e->dest->index, post_dom_bb->index); + + e2 = redirect_edge_and_branch (e, post_dom_bb); + cfg_altered = true; + + /* If edge was already around, no updating is neccesary. */ + if (e2 != e) + return e2; + + if (!gimple_seq_empty_p (phi_nodes (post_dom_bb))) + { + /* We are sure that for every live PHI we are seeing control dependent BB. + This means that we can pick any edge to duplicate PHI args from. */ + FOR_EACH_EDGE (e2, ei, post_dom_bb->preds) + if (e2 != e) + break; + for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);) { - prev = phi; - phi = PHI_CHAIN (phi); + gimple phi = gsi_stmt (gsi); + tree op; + source_location locus; + + /* PHIs for virtuals have no control dependency relation on them. + We are lost here and must force renaming of the symbol. */ + if (!is_gimple_reg (gimple_phi_result (phi))) + { + mark_virtual_phi_result_for_renaming (phi); + remove_phi_node (&gsi, true); + continue; + } + + /* Dead PHI do not imply control dependency. */ + if (!gimple_plf (phi, STMT_NECESSARY)) + { + gsi_next (&gsi); + continue; + } + + op = gimple_phi_arg_def (phi, e2->dest_idx); + locus = gimple_phi_arg_location (phi, e2->dest_idx); + add_phi_arg (phi, op, e, locus); + /* The resulting PHI if not dead can only be degenerate. */ + gcc_assert (degenerate_phi_p (phi)); + gsi_next (&gsi); } } + return e; } - + /* 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"); } @@ -720,98 +1171,276 @@ 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; + edge e, e2; + edge_iterator ei; - /* The post dominance info has to be up-to-date. */ - 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); - /* There are three particularly problematical cases. + e = find_edge (bb, post_dom_bb); - 1. Blocks that do not have an immediate post dominator. This - can happen with infinite loops. + /* If edge is already there, try to use it. This avoids need to update + PHI nodes. Also watch for cases where post dominator does not exists + or is exit block. These can happen for infinite loops as we create + fake edges in the dominator tree. */ + if (e) + ; + else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR) + e = EDGE_SUCC (bb, 0); + else + e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb); + gcc_assert (e); + e->probability = REG_BR_PROB_BASE; + e->count = bb->count; - 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. + /* The edge is no longer associated with a conditional, so it does + not have TRUE/FALSE flags. */ + e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); - 3. If the post dominator has PHI nodes we may be able to compute - the right PHI args for them. + /* The lone outgoing edge from BB will be a fallthru edge. */ + e->flags |= EDGE_FALLTHRU; + + /* Remove the remaining outgoing edges. */ + for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); ) + if (e != e2) + { + cfg_altered = true; + remove_edge (e2); + } + else + ei_next (&ei); + } + unlink_stmt_vdef (stmt); + gsi_remove (i, true); + release_defs (stmt); +} - 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 +/* 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, psi; + gimple stmt; + tree call; + VEC (basic_block, heap) *h; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\nEliminating unnecessary statements:\n"); + + clear_special_calls (); + + /* Walking basic blocks and statements in reverse order avoids + releasing SSA names before any other DEFs that refer to them are + released. This helps avoid loss of debug information, as we get + a chance to propagate all RHSs of removed SSAs into debug uses, + rather than only the latest ones. E.g., consider: + + x_3 = y_1 + z_2; + a_5 = x_3 - b_4; + # DEBUG a => a_5 + + If we were to release x_3 before a_5, when we reached a_5 and + tried to substitute it into the debug stmt, we'd see x_3 there, + but x_3's DEF, type, etc would have already been disconnected. + By going backwards, the debug stmt first changes to: + + # DEBUG a => x_3 - b_4 + + and then to: + + # DEBUG a => y_1 + z_2 - b_4 + + as desired. */ + gcc_assert (dom_info_available_p (CDI_DOMINATORS)); + h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR)); + + while (VEC_length (basic_block, h)) + { + bb = VEC_pop (basic_block, h); + + /* Remove dead statements. */ + for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi) { - /* 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; + stmt = gsi_stmt (gsi); + + psi = gsi; + gsi_prev (&psi); + + stats.total++; + + /* We can mark a call to free as not necessary if the + defining statement of its argument is an allocation + function and that is not necessary itself. */ + if (gimple_call_builtin_p (stmt, BUILT_IN_FREE)) + { + tree ptr = gimple_call_arg (stmt, 0); + tree callee2; + gimple def_stmt; + if (TREE_CODE (ptr) != SSA_NAME) + continue; + def_stmt = SSA_NAME_DEF_STMT (ptr); + if (!is_gimple_call (def_stmt) + || gimple_plf (def_stmt, STMT_NECESSARY)) + continue; + callee2 = gimple_call_fndecl (def_stmt); + if (callee2 == NULL_TREE + || DECL_BUILT_IN_CLASS (callee2) != BUILT_IN_NORMAL + || (DECL_FUNCTION_CODE (callee2) != BUILT_IN_MALLOC + && DECL_FUNCTION_CODE (callee2) != BUILT_IN_CALLOC)) + continue; + gimple_set_plf (stmt, STMT_NECESSARY, false); + } + + /* If GSI is not necessary then remove it. */ + if (!gimple_plf (stmt, STMT_NECESSARY)) + { + if (!is_gimple_debug (stmt)) + something_changed = true; + remove_dead_stmt (&gsi, bb); + } + else if (is_gimple_call (stmt)) + { + call = gimple_call_fndecl (stmt); + if (call) + { + tree name; + + /* 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"); + } + + gimple_call_set_lhs (stmt, NULL_TREE); + maybe_clean_or_replace_eh_stmt (stmt, stmt); + update_stmt (stmt); + release_ssa_name (name); + } + notice_special_calls (stmt); + } + } } - 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. */ - EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); + VEC_free (basic_block, heap, h); - /* The lone outgoing edge from BB will be a fallthru edge. */ - EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU; + /* Since we don't track liveness of virtual PHI nodes, it is possible that we + rendered some PHI nodes unreachable while they are still in use. + Mark them for renaming. */ + if (cfg_altered) + { + basic_block prev_bb; - /* Remove the remaining the outgoing edges. */ - while (!single_succ_p (bb)) + find_unreachable_blocks (); + + /* Delete all unreachable basic blocks in reverse dominator order. */ + for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb) { - /* 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)); + prev_bb = bb->prev_bb; + + if (!TEST_BIT (bb_contains_live_stmts, bb->index) + || !(bb->flags & BB_REACHABLE)) + { + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi)))) + { + bool found = false; + imm_use_iterator iter; + + FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi))) + { + if (!(gimple_bb (stmt)->flags & BB_REACHABLE)) + continue; + if (gimple_code (stmt) == GIMPLE_PHI + || gimple_plf (stmt, STMT_NECESSARY)) + { + found = true; + BREAK_FROM_IMM_USE_STMT (iter); + } + } + if (found) + mark_virtual_phi_result_for_renaming (gsi_stmt (gsi)); + } + + if (!(bb->flags & BB_REACHABLE)) + { + /* Speed up the removal of blocks that don't + dominate others. Walking backwards, this should + be the common case. ??? Do we need to recompute + dominators because of cfg_altered? */ + if (!MAY_HAVE_DEBUG_STMTS + || !first_dom_son (CDI_DOMINATORS, bb)) + delete_basic_block (bb); + else + { + h = get_all_dominated_blocks (CDI_DOMINATORS, bb); + + while (VEC_length (basic_block, h)) + { + bb = VEC_pop (basic_block, h); + prev_bb = bb->prev_bb; + /* Rearrangements to the CFG may have failed + to update the dominators tree, so that + formerly-dominated blocks are now + otherwise reachable. */ + if (!!(bb->flags & BB_REACHABLE)) + continue; + delete_basic_block (bb); + } + + VEC_free (basic_block, heap, h); + } + } + } } } - - FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter, SSA_OP_VIRTUAL_DEFS) + 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); + + 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 @@ -829,12 +1458,14 @@ tree_dce_init (bool aggressive) last_stmt_necessary = sbitmap_alloc (last_basic_block); sbitmap_zero (last_stmt_necessary); + bb_contains_live_stmts = sbitmap_alloc (last_basic_block); + sbitmap_zero (bb_contains_live_stmts); } 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; } @@ -853,13 +1484,15 @@ tree_dce_done (bool aggressive) sbitmap_free (visited_control_parents); sbitmap_free (last_stmt_necessary); + sbitmap_free (bb_contains_live_stmts); + bb_contains_live_stmts = NULL; } 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. @@ -874,10 +1507,20 @@ 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; + + calculate_dominance_info (CDI_DOMINATORS); + + /* Preheaders are needed for SCEV to work. + Simple lateches and recorded exits improve chances that loop will + proved to be finite in testcases such as in loop-15.c and loop-24.c */ + if (aggressive) + loop_optimizer_init (LOOPS_NORMAL + | LOOPS_HAVE_RECORDED_EXITS); tree_dce_init (aggressive); @@ -898,13 +1541,22 @@ perform_tree_ssa_dce (bool aggressive) find_obviously_necessary_stmts (el); + if (aggressive) + loop_optimizer_finalize (); + + longest_chain = 0; + total_chain = 0; + nr_walks = 0; + chain_ovfl = false; + visited = BITMAP_ALLOC (NULL); propagate_necessity (el); + BITMAP_FREE (visited); - 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 @@ -912,37 +1564,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 @@ -951,8 +1614,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 */ @@ -960,21 +1625,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_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 */ @@ -982,19 +1644,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_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 */ @@ -1002,15 +1663,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_verify_ssa + | TODO_verify_flow /* todo_flags_finish */ + } };