Mercurial > hg > CbC > CbC_gcc
diff gcc/tree-ssa-dce.c @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 12 Feb 2010 23:39:51 +0900 |
parents | a06113de4d67 |
children | b7f97abdc517 |
line wrap: on
line diff
--- a/gcc/tree-ssa-dce.c Sun Feb 07 18:28:00 2010 +0900 +++ b/gcc/tree-ssa-dce.c Fri Feb 12 23:39:51 2010 +0900 @@ -1,22 +1,22 @@ /* Dead code elimination pass for the GNU compiler. - Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008 + Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc. Contributed by Ben Elliston <bje@redhat.com> and Andrew MacLeod <amacleod@redhat.com> 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 <http://www.gnu.org/licenses/>. */ @@ -87,6 +87,9 @@ 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. @@ -218,6 +221,8 @@ gimple_set_plf (stmt, STMT_NECESSARY, true); if (add_to_worklist) 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); } @@ -233,7 +238,12 @@ 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); @@ -242,7 +252,17 @@ if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt)) return; + 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); } @@ -282,7 +302,6 @@ case GIMPLE_ASM: case GIMPLE_RESX: case GIMPLE_RETURN: - case GIMPLE_CHANGE_DYNAMIC_TYPE: mark_stmt_necessary (stmt, true); return; @@ -303,17 +322,18 @@ 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_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_has_value_p (stmt) + || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL) + mark_stmt_necessary (stmt, false); + return; + case GIMPLE_GOTO: gcc_assert (!simple_goto_p (stmt)); mark_stmt_necessary (stmt, true); @@ -373,6 +393,7 @@ if (TEST_BIT (last_stmt_necessary, cd_bb->index)) continue; SET_BIT (last_stmt_necessary, cd_bb->index); + SET_BIT (bb_contains_live_stmts, cd_bb->index); stmt = last_stmt (cd_bb); if (stmt && is_ctrl_stmt (stmt)) @@ -414,25 +435,192 @@ } } + /* Pure and const functions are finite and thus have no infinite loops in + them. */ + if ((TREE_READONLY (current_function_decl) + || DECL_PURE_P (current_function_decl)) + && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)) + 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) - { - edge_iterator ei; - FOR_EACH_EDGE (e, ei, bb->succs) - if (e->flags & EDGE_DFS_BACK) - mark_control_dependent_edges_necessary (e->dest, el); - } + 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); + } + } + + 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); + } + scev_finalize (); } } +/* Return true if REF is based on an aliased base, otherwise false. */ + +static bool +ref_may_be_aliased (tree ref) +{ + while (handled_component_p (ref)) + ref = TREE_OPERAND (ref, 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) + { + 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) + { + /* 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; +} + +static void +mark_aliased_reaching_defs_necessary (gimple stmt, tree ref) +{ + 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++; +} + +/* 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. */ + +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); + + /* 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))) + { + gcc_assert (gimple_nop_p (def_stmt) + || gimple_plf (def_stmt, STMT_NECESSARY)); + return false; + } + + /* 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; + } + + 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); +} + +/* 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. + value to the worklist. In conservative mode, EL is NULL. */ @@ -440,7 +628,7 @@ propagate_necessity (struct edge_list *el) { gimple stmt; - bool aggressive = (el ? true : false); + bool aggressive = (el ? true : false); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "\nProcessing worklist:\n"); @@ -471,7 +659,10 @@ } } - if (gimple_code (stmt) == GIMPLE_PHI) + 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 @@ -488,7 +679,7 @@ mark_operand_necessary (arg); } - if (aggressive) + if (aggressive && !degenerate_phi_p (stmt)) { for (k = 0; k < gimple_phi_num_args (stmt); k++) { @@ -505,21 +696,165 @@ 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). */ + VDEF operands in this statement. Mark all the statements + which feed this statement's uses as necessary. */ ssa_op_iter iter; tree use; - FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES) + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) mark_operand_necessary (use); + + use = gimple_vuse (stmt); + if (!use) + continue; + + /* If we dropped to simple mode make all immediately + reachable definitions necessary. */ + if (chain_ovfl) + { + mark_all_reaching_defs_necessary (stmt); + continue; + } + + /* 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)) + { + 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_MALLOC + || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE)) + 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 (!ref_may_be_aliased (arg)) + mark_aliased_reaching_defs_necessary (stmt, arg); + } + } + else if (gimple_assign_single_p (stmt)) + { + tree rhs; + bool rhs_aliased = false; + /* If this is a load mark things necessary. */ + rhs = gimple_assign_rhs1 (stmt); + if (TREE_CODE (rhs) != SSA_NAME + && !is_gimple_min_invariant (rhs)) + { + if (!ref_may_be_aliased (rhs)) + mark_aliased_reaching_defs_necessary (stmt, rhs); + else + rhs_aliased = true; + } + if (rhs_aliased) + 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 (TREE_CODE (rhs) != SSA_NAME + && !is_gimple_min_invariant (rhs)) + { + 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) + && !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); + } } } } +/* Replace all uses of result of PHI by underlying variable and mark it + for renaming. */ + +void +mark_virtual_phi_result_for_renaming (gimple phi) +{ + bool used = false; + imm_use_iterator iter; + use_operand_p use_p; + gimple stmt; + tree result_ssa, result_var; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Marking result for renaming : "); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); + fprintf (dump_file, "\n"); + } + + result_ssa = gimple_phi_result (phi); + result_var = SSA_NAME_VAR (result_ssa); + FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa) + { + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) + SET_USE (use_p, result_var); + update_stmt (stmt); + used = true; + } + if (used) + mark_sym_for_renaming (result_var); +} /* Remove dead PHI nodes from block BB. */ @@ -537,6 +872,31 @@ stats.total_phis++; phi = gsi_stmt (gsi); + /* 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))) + { + /* 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; @@ -549,15 +909,108 @@ remove_phi_node (&gsi, true); stats.removed_phis++; + continue; } - else - { - gsi_next (&gsi); - } + + gsi_next (&gsi); } return something_changed; } +/* Find first live post dominator of BB. */ + +static basic_block +get_live_post_dom (basic_block bb) +{ + 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); + /* And look for first live one. */ + while (post_dom_bb != EXIT_BLOCK_PTR + && !TEST_BIT (bb_contains_live_stmts, post_dom_bb->index)) + post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, post_dom_bb); + + return post_dom_bb; +} + +/* 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 (phi_nodes (post_dom_bb)) + { + /* We are sure that for every live PHI we are seeing control dependent BB. + This means that we can look up the end of control dependent path leading + to the PHI itself. */ + FOR_EACH_EDGE (e2, ei, post_dom_bb->preds) + if (e2 != e && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src)) + break; + for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);) + { + gimple phi = gsi_stmt (gsi); + tree op; + source_location locus; + + /* Dead PHI do not imply control dependency. */ + if (!gimple_plf (phi, STMT_NECESSARY) + && is_gimple_reg (gimple_phi_result (phi))) + { + gsi_next (&gsi); + continue; + } + if (gimple_phi_arg_def (phi, e->dest_idx)) + { + gsi_next (&gsi); + continue; + } + + /* We didn't find edge to update. This can happen for PHIs on virtuals + since there is 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; + } + if (!e2) + { + op = gimple_phi_arg_def (phi, e->dest_idx == 0 ? 1 : 0); + locus = gimple_phi_arg_location (phi, e->dest_idx == 0 ? 1 : 0); + } + else + { + 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); + gcc_assert (e2 || 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. */ @@ -585,70 +1038,50 @@ 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. + edge e, e2; + edge_iterator ei; - 1. Blocks that do not have an immediate post dominator. This - can happen with infinite loops. + post_dom_bb = get_live_post_dom (bb); - 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. + e = find_edge (bb, post_dom_bb); - 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)) - ; + /* 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 - { - /* 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; + 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; /* 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); + e->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; + e->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)); - } + /* 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); } - - gsi_remove (i, true); - release_defs (stmt); + + unlink_stmt_vdef (stmt); + 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. */ @@ -657,34 +1090,61 @@ { bool something_changed = false; basic_block bb; - gimple_stmt_iterator gsi; + 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 (); - FOR_EACH_BB (bb) + + /* 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)) { - /* Remove dead PHI nodes. */ - something_changed |= remove_dead_phis (bb); - } + bb = VEC_pop (basic_block, h); - FOR_EACH_BB (bb) - { /* Remove dead statements. */ - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) + for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi) { stmt = gsi_stmt (gsi); + psi = gsi; + gsi_prev (&psi); + stats.total++; /* 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); - something_changed = true; } else if (is_gimple_call (stmt)) { @@ -692,7 +1152,6 @@ if (call) { tree name; - gimple g; /* When LHS of var = call (); is dead, simplify it into call (); saving one operand. */ @@ -707,27 +1166,96 @@ 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)); + + 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); } - gsi_next (&gsi); - } - else - { - gsi_next (&gsi); } } } + VEC_free (basic_block, heap, h); + + /* 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; + + 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) + { + 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_BB (bb) + { + /* Remove dead PHI nodes. */ + something_changed |= remove_dead_phis (bb); + } + return something_changed; } @@ -769,6 +1297,8 @@ 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); @@ -793,6 +1323,8 @@ sbitmap_free (visited_control_parents); sbitmap_free (last_stmt_necessary); + sbitmap_free (bb_contains_live_stmts); + bb_contains_live_stmts = NULL; } sbitmap_free (processed); @@ -820,6 +1352,13 @@ struct edge_list *el = NULL; bool something_changed = 0; + /* 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); if (aggressive) @@ -839,7 +1378,16 @@ 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); something_changed |= eliminate_unnecessary_stmts (); something_changed |= cfg_altered; @@ -865,7 +1413,7 @@ free_edge_list (el); if (something_changed) - return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect + return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect | TODO_remove_unused_locals); else return 0;