From b094d6c4bf572654a031ecc4afe675154c886dc5 Mon Sep 17 00:00:00 2001 From: Jing Yu Date: Thu, 22 Jul 2010 14:03:48 -0700 Subject: commit gcc-4.4.3 which is used to build gcc-4.4.3 Android toolchain in master. The source is based on fsf gcc-4.4.3 and contains local patches which are recorded in gcc-4.4.3/README.google. Change-Id: Id8c6d6927df274ae9749196a1cc24dbd9abc9887 --- gcc-4.4.3/gcc/tree-ssa-dce.c | 1172 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1172 insertions(+) create mode 100644 gcc-4.4.3/gcc/tree-ssa-dce.c (limited to 'gcc-4.4.3/gcc/tree-ssa-dce.c') diff --git a/gcc-4.4.3/gcc/tree-ssa-dce.c b/gcc-4.4.3/gcc/tree-ssa-dce.c new file mode 100644 index 000000000..39126cd7d --- /dev/null +++ b/gcc-4.4.3/gcc/tree-ssa-dce.c @@ -0,0 +1,1172 @@ +/* Dead code elimination pass for the GNU compiler. + 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. + +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 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 COPYING3. If not see +. */ + +/* Dead code elimination. + + References: + + Building an Optimizing Compiler, + Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. + + Advanced Compiler Design and Implementation, + Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10. + + Dead-code elimination is the removal of statements which have no + impact on the program's output. "Dead statements" have no impact + on the program's output, while "necessary statements" may have + impact on the output. + + The algorithm consists of three phases: + 1. Marking as necessary all statements known to be necessary, + e.g. most function calls, writing a value to memory, etc; + 2. Propagating necessary statements, e.g., the statements + giving values to operands in necessary statements; and + 3. Removing dead statements. */ + +#include "config.h" +#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-flow.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" +#include "pointer-set.h" +#include "langhooks.h" + +static struct stmt_stats +{ + int total; + int total_phis; + int removed; + int removed_phis; +} stats; + +#define STMT_NECESSARY GF_PLF_1 + +DEF_VEC_P(use_operand_p); +DEF_VEC_ALLOC_P(use_operand_p, heap); + +static VEC(gimple,heap) *worklist; + +/* Vector indicating an SSA name has already been processed and marked + as necessary. */ +static sbitmap processed; + +/* Pointer set of stmt killed by delete. */ +static struct pointer_set_t *killed_by_delete; + +/* Vector indicating that last_stmt if a basic block has already been + marked as necessary. */ +static sbitmap last_stmt_necessary; + +/* Before we can determine whether a control branch is dead, we need to + compute which blocks are control dependent on which edges. + + We expect each block to be control dependent on very few edges so we + 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. */ +static bitmap *control_dependence_map; + +/* 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)) + + +/* 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) +{ + if (bb == ENTRY_BLOCK_PTR) + return; + 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) +{ + bitmap_clear (control_dependence_map[bb->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) +{ + gcc_assert (block != ENTRY_BLOCK_PTR); + + 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. */ + +static void +find_control_dependence (struct edge_list *el, int edge_index) +{ + basic_block current_block; + basic_block ending_block; + + 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 = single_succ (ENTRY_BLOCK_PTR); + else + ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index)); + + for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index); + current_block != ending_block && current_block != EXIT_BLOCK_PTR; + current_block = find_pdom (current_block)) + { + edge e = INDEX_EDGE (el, edge_index); + + /* For abnormal edges, we don't make current_block control + dependent because instructions that throw are always necessary + anyway. */ + if (e->flags & EDGE_ABNORMAL) + continue; + + set_control_dependence_map_bit (current_block, edge_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) +{ + int i; + + for (i = 0; i < NUM_EDGES (el); ++i) + find_control_dependence (el, i); +} + +/* 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 (gimple stmt, bool add_to_worklist) +{ + gcc_assert (stmt); + + if (gimple_plf (stmt, STMT_NECESSARY)) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Marking useful stmt: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + fprintf (dump_file, "\n"); + } + + gimple_set_plf (stmt, STMT_NECESSARY, true); + if (add_to_worklist) + VEC_safe_push (gimple, heap, worklist, stmt); +} + +/* Follow the UD chain to find the base pointer for + pointer PTR. */ + +static tree +find_base_ptr (tree ptr) +{ + STRIP_NOPS (ptr); + + if (TREE_CODE (ptr) != SSA_NAME) + return ptr; + + do + { + gimple stmt = SSA_NAME_DEF_STMT (ptr); + + if (!stmt || gimple_code (stmt) != GIMPLE_ASSIGN) + return ptr; + + if (gimple_assign_copy_p (stmt) + || gimple_assign_unary_nop_p (stmt) + || gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) + { + tree rhs = gimple_assign_rhs1 (stmt); + STRIP_NOPS (rhs); + if (TREE_CODE (rhs) != SSA_NAME) + return ptr; + else + ptr = rhs; + } + else + return ptr; + } while (true); + + return ptr; +} + +/* Returns true if the STMT's def is used by a global + delete call and there is no real uses of the definition + by the intervening stmts. */ + +static bool +is_killed_by_delete (gimple stmt) +{ + tree lhs, base, base_ptr; + gimple use_stmt, delete_stmt = NULL; + struct voptype_d *vdefs; + use_operand_p use_op; + imm_use_iterator iter; + + if (pointer_set_contains (killed_by_delete, stmt)) + return true; + + lhs = gimple_assign_lhs (stmt); + base = get_base_address (lhs); + if (TREE_CODE (base) != INDIRECT_REF) + return false; + base_ptr = TREE_OPERAND (base, 0); + base_ptr = find_base_ptr (base_ptr); + + vdefs = gimple_vdef_ops (stmt); + while (vdefs) + { + FOR_EACH_IMM_USE_FAST (use_op, iter, VDEF_RESULT (vdefs)) + { + use_stmt = USE_STMT (use_op); + if (is_global_delete_call (use_stmt)) + { + tree arg = gimple_call_arg (use_stmt, 0); + arg = find_base_ptr (arg); + if (base_ptr == arg) + { + delete_stmt = use_stmt; + break; + } + } + } + if (delete_stmt) + break; + vdefs = vdefs->next; + } + + if (!delete_stmt) + return false; + + /* Ideally we should check if DELETE_STMT post dominate stmt, but post + dominance information is not guaranteed to exist, so we just check + if they are in the same BB of if BB of delete is the single successor + of vptr init stmt's BB. */ + if (gimple_bb (delete_stmt) != gimple_bb (stmt) + && !(single_succ_p (gimple_bb (stmt)) + && single_succ (gimple_bb (stmt)) == gimple_bb (delete_stmt))) + return false; + + + /* Now check if all other use stmts are dominated by DELETE_STMT. */ + vdefs = gimple_vdef_ops (stmt); + while (vdefs) + { + FOR_EACH_IMM_USE_FAST (use_op, iter, VDEF_RESULT (vdefs)) + { + use_stmt = USE_STMT (use_op); + if (use_stmt != delete_stmt + && !stmt_dominates_stmt_p (delete_stmt, use_stmt)) + return false; + } + vdefs = vdefs->next; + } + pointer_set_insert (killed_by_delete, stmt); + return true; +} + +/* Mark the statement defining operand OP as necessary. */ + +static inline void +mark_operand_necessary (tree op) +{ + gimple stmt; + int ver; + + gcc_assert (op); + + ver = SSA_NAME_VERSION (op); + if (TEST_BIT (processed, ver)) + return; + SET_BIT (processed, ver); + + stmt = SSA_NAME_DEF_STMT (op); + + if (!stmt || gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt)) + return; + + if (is_vptr_init (stmt) && is_killed_by_delete (stmt)) + { + /* Do not mark STMT as necessary, but put it in worklist. + This allows uses to propagate up via Def-Def chain. */ + VEC_safe_push (gimple, heap, worklist, stmt); + return; + } + + 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. + + If AGGRESSIVE is false, control statements are conservatively marked as + necessary. */ + +static void +mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive) +{ + 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 + && 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 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 GIMPLE_PREDICT: + case GIMPLE_LABEL: + mark_stmt_necessary (stmt, false); + return; + + case GIMPLE_ASM: + case GIMPLE_RESX: + case GIMPLE_RETURN: + case GIMPLE_CHANGE_DYNAMIC_TYPE: + mark_stmt_necessary (stmt, true); + return; + + 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 (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 (lhs) == EXC_PTR_EXPR + || TREE_CODE (lhs) == FILTER_EXPR) + { + mark_stmt_necessary (stmt, true); + return; + } + break; + + case GIMPLE_GOTO: + gcc_assert (!simple_goto_p (stmt)); + mark_stmt_necessary (stmt, true); + return; + + case GIMPLE_COND: + gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2); + /* Fall through. */ + + case GIMPLE_SWITCH: + if (! aggressive) + mark_stmt_necessary (stmt, true); + break; + + default: + break; + } + + /* If the statement has volatile operands, it needs to be preserved. + Same for statements that can alter control flow in unpredictable + ways. */ + if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt)) + { + mark_stmt_necessary (stmt, true); + return; + } + + if (is_vptr_init (stmt)) + { + /* Initialization of the vptr field for the same object this + destructor is operating on won't be live out of the function + if it is not used within the function, so do not treat them + as a hidden global store. */ + if (lang_hooks.decls.is_decl_dtor (current_function_decl)) + { + tree base, base_ptr; + tree lhs = gimple_assign_lhs (stmt); + base = get_base_address (lhs); + if (TREE_CODE (base) == INDIRECT_REF) + { + base_ptr = TREE_OPERAND (base, 0); + base_ptr = find_base_ptr (base_ptr); + if ((TREE_CODE (base_ptr) == SSA_NAME) + && (gimple_nop_p (SSA_NAME_DEF_STMT (base_ptr)))) + return; + } + } + + if (is_killed_by_delete (stmt)) + return; + } + + if (is_hidden_global_store (stmt)) + { + mark_stmt_necessary (stmt, true); + return; + } + + 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. + + If EL is NULL, control statements are conservatively marked as + necessary. Otherwise it contains the list of edges used by control + dependence analysis. */ + +static void +find_obviously_necessary_stmts (struct edge_list *el) +{ + basic_block bb; + gimple_stmt_iterator gsi; + edge e; + gimple phi, stmt; + + FOR_EACH_BB (bb) + { + /* PHI nodes are never inherently necessary. */ + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + phi = gsi_stmt (gsi); + gimple_set_plf (phi, STMT_NECESSARY, false); + } + + /* Check all statements in the block. */ + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + stmt = gsi_stmt (gsi); + gimple_set_plf (stmt, STMT_NECESSARY, false); + mark_stmt_if_obviously_necessary (stmt, el != NULL); + } + } + + 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) + { + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->flags & EDGE_DFS_BACK) + mark_control_dependent_edges_necessary (e->dest, el); + } + } +} + + +/* 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) +{ + gimple stmt; + bool aggressive = (el ? true : false); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\nProcessing worklist:\n"); + + while (VEC_length (gimple, worklist) > 0) + { + /* Take STMT from worklist. */ + stmt = VEC_pop (gimple, worklist); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "processing: "); + 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 STMT is control dependent on, but only if we haven't + already done so. */ + 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); + } + } + + 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 + PHI node's arguments are always necessary. In aggressive mode, + we also consider the control dependent edges leading to the + predecessor block associated with each PHI alternative as + necessary. */ + size_t k; + + for (k = 0; k < gimple_phi_num_args (stmt); k++) + { + tree arg = PHI_ARG_DEF (stmt, k); + if (TREE_CODE (arg) == SSA_NAME) + mark_operand_necessary (arg); + } + + if (aggressive) + { + for (k = 0; k < gimple_phi_num_args (stmt); k++) + { + 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)) + { + SET_BIT (visited_control_parents, arg_bb->index); + mark_control_dependent_edges_necessary (arg_bb, el); + } + } + } + } + else + { + /* Propagate through the operands. Examine all the USE, VUSE and + 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 (VDEF operands allow us to follow def-def + links). */ + ssa_op_iter iter; + tree use; + int use_flags = SSA_OP_ALL_USES; + + /* Special case of dead vptr initialization + followed by operator delete -- non virtual + uses do not need to be propagated, but only + virtual uses which link up def-def chains. */ + if (!gimple_plf (stmt, STMT_NECESSARY)) + use_flags = SSA_OP_VIRTUAL_USES; + + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, use_flags) + mark_operand_necessary (use); + } + } +} + + +/* Remove dead PHI nodes from block BB. */ + +static bool +remove_dead_phis (basic_block bb) +{ + bool something_changed = false; + gimple_seq phis; + gimple phi; + gimple_stmt_iterator gsi; + phis = phi_nodes (bb); + + for (gsi = gsi_start (phis); !gsi_end_p (gsi);) + { + stats.total_phis++; + phi = gsi_stmt (gsi); + + if (!gimple_plf (phi, STMT_NECESSARY)) + { + something_changed = true; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Deleting : "); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); + fprintf (dump_file, "\n"); + } + + remove_phi_node (&gsi, true); + stats.removed_phis++; + } + else + { + 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 (gimple_stmt_iterator *i, basic_block bb) +{ + gimple stmt = gsi_stmt (*i); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Deleting : "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + fprintf (dump_file, "\n"); + } + + stats.removed++; + + /* If we have determined that a conditional branch statement contributes + 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 cleanup_tree_cfg if this change in the flow graph makes them + unreachable. */ + if (is_ctrl_stmt (stmt)) + { + basic_block post_dom_bb; + + /* The post dominance info has to be up-to-date. */ + 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); + + /* 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 + { + /* 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; + + /* 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); + + /* The lone outgoing edge from BB will be a fallthru edge. */ + EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU; + + /* Remove the remaining the outgoing edges. */ + while (!single_succ_p (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)); + } + } + + /* Due to imprecise def-use information, the deleted vptr init + assignment have uses, which need to be fixed to previous + versions of the virtual ops defined by STMT. */ + if (is_vptr_init (stmt) + && is_killed_by_delete (stmt)) + { + gimple_stmt_iterator gsi; + gimple next_stmt; + struct voptype_d *vdefs; + use_operand_p use_op; + imm_use_iterator iter; + + gsi = gsi_for_stmt (stmt); + gsi_next (&gsi); + if (!gsi_end_p (gsi)) + next_stmt = gsi_stmt (gsi); + else + { + basic_block nbb; + gcc_assert (single_succ_p (gimple_bb (stmt))); + nbb = single_succ (gimple_bb (stmt)); + gsi = gsi_after_labels (nbb); + gcc_assert (!gsi_end_p (gsi)); + next_stmt = gsi_stmt (gsi); + } + + /* Now fixup SSA. */ + vdefs = gimple_vdef_ops (stmt); + while (vdefs) + { + int n, j; + tree prev_nm; + VEC(use_operand_p, heap) *fixup_opnds = NULL; + + n = VDEF_NUM (vdefs); + gcc_assert (n == 1); + prev_nm = VDEF_OP (vdefs, 0); + FOR_EACH_IMM_USE_FAST (use_op, iter, VDEF_RESULT (vdefs)) + VEC_safe_push (use_operand_p, heap, fixup_opnds, use_op); + + for (j = 0; + VEC_iterate (use_operand_p, fixup_opnds, j, use_op); + ++j) + set_ssa_use_from_ptr (use_op, prev_nm); + + vdefs = vdefs->next; + } + } + 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) + { + /* Remove dead PHI nodes. */ + something_changed |= remove_dead_phis (bb); + } + + 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) +{ + 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); + + 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); +} + +/* Initialization for this pass. Set up the used data structures. */ + +static void +tree_dce_init (bool aggressive) +{ + memset ((void *) &stats, 0, sizeof (stats)); + + if (aggressive) + { + int i; + + control_dependence_map = XNEWVEC (bitmap, last_basic_block); + for (i = 0; i < last_basic_block; ++i) + control_dependence_map[i] = BITMAP_ALLOC (NULL); + + last_stmt_necessary = sbitmap_alloc (last_basic_block); + sbitmap_zero (last_stmt_necessary); + } + + processed = sbitmap_alloc (num_ssa_names + 1); + sbitmap_zero (processed); + + killed_by_delete = pointer_set_create (); + + worklist = VEC_alloc (gimple, heap, 64); + cfg_altered = false; +} + +/* Cleanup after this pass. */ + +static void +tree_dce_done (bool aggressive) +{ + if (aggressive) + { + int i; + + for (i = 0; i < last_basic_block; ++i) + BITMAP_FREE (control_dependence_map[i]); + free (control_dependence_map); + + sbitmap_free (visited_control_parents); + sbitmap_free (last_stmt_necessary); + } + + sbitmap_free (processed); + + pointer_set_destroy (killed_by_delete); + + VEC_free (gimple, heap, worklist); +} + +/* Main routine to eliminate dead code. + + AGGRESSIVE controls the aggressiveness of the algorithm. + In conservative mode, we ignore control dependence and simply declare + all but the most trivially dead branches necessary. This mode is fast. + In aggressive mode, control dependences are taken into account, which + results in more dead code elimination, but at the cost of some time. + + FIXME: Aggressive mode before PRE doesn't work currently because + the dominance info is not invalidated after DCE1. This is + not an issue right now because we only run aggressive DCE + as the last tree SSA pass, but keep this in mind when you + start experimenting with pass ordering. */ + +static unsigned int +perform_tree_ssa_dce (bool aggressive) +{ + struct edge_list *el = NULL; + bool something_changed = 0; + + tree_dce_init (aggressive); + + if (aggressive) + { + /* Compute control dependence. */ + timevar_push (TV_CONTROL_DEPENDENCES); + calculate_dominance_info (CDI_POST_DOMINATORS); + el = create_edge_list (); + 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 (); + } + + find_obviously_necessary_stmts (el); + + propagate_necessity (el); + + something_changed |= eliminate_unnecessary_stmts (); + something_changed |= cfg_altered; + + /* 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 + of incrementally updating dominators. */ + 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 && (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) +{ + return perform_tree_ssa_dce (/*aggressive=*/false); +} + +static unsigned int +tree_ssa_dce_loop (void) +{ + 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) +{ + return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2); +} + +static bool +gate_dce (void) +{ + return flag_tree_dce != 0; +} + +struct gimple_opt_pass pass_dce = +{ + { + GIMPLE_PASS, + "dce", /* name */ + gate_dce, /* gate */ + tree_ssa_dce, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_DCE, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ + } +}; + +struct gimple_opt_pass pass_dce_loop = +{ + { + GIMPLE_PASS, + "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, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ + } +}; + +struct gimple_opt_pass pass_cd_dce = +{ + { + GIMPLE_PASS, + "cddce", /* name */ + gate_dce, /* gate */ + tree_ssa_cd_dce, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_CD_DCE, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_verify_ssa + | TODO_verify_flow /* todo_flags_finish */ + } +}; -- cgit v1.2.3