/* 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, 2010, 2011
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/>. */
#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 "gimple.h"
#include "tree-dump.h"
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.
/* 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)
{
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);
}
}
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);
}
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))
+ if (cfun->can_throw_non_call_exceptions && stmt_could_throw_p (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_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 GIMPLE_GOTO:
gcc_assert (!simple_goto_p (stmt));
mark_stmt_necessary (stmt, true);
}
-/* 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. */
+/* Mark the last statement of BB as necessary. */
+
static void
-mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
+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);
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);
+ if (ignore_self && cd_bb == bb)
+ {
+ skipped = true;
+ continue;
+ }
- stmt = last_stmt (cd_bb);
- if (stmt && is_ctrl_stmt (stmt))
- mark_stmt_necessary (stmt, true);
+ if (!TEST_BIT (last_stmt_necessary, cd_bb->index))
+ mark_last_stmt_necessary (cd_bb);
}
+
+ if (!skipped)
+ SET_BIT (visited_control_parents, bb->index);
}
gimple_stmt_iterator gsi;
edge e;
gimple phi, stmt;
+ int flags;
FOR_EACH_BB (bb)
{
}
}
+ /* 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)
- {
- 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, 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 ();
}
}
{
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 cached get_ref_base_and_extent data 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 ATTRIBUTE_UNUSED)
+mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
{
gimple def_stmt = SSA_NAME_DEF_STMT (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_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;
}
/* 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;
}
ao_ref_init (&refd, ref);
chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
mark_aliased_reaching_defs_necessary_1,
- NULL, NULL);
+ 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
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. */
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");
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
+ /* 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 = 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 (gimple_code (stmt) == GIMPLE_PHI
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 < 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))
+
+ 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
- VDEF 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;
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_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_ALLOCA
+ || 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);
{
tree rhs = gimple_return_retval (stmt);
/* A return statement may perform a load. */
- if (TREE_CODE (rhs) != SSA_NAME
+ if (rhs
+ && TREE_CODE (rhs) != SSA_NAME
&& !is_gimple_min_invariant (rhs))
{
if (!ref_may_be_aliased (rhs))
gcc_unreachable ();
/* If we over-used our alias oracle budget drop to simple
- mode. The cost metric allows quadratic behavior up to
- a constant maximal chain and after that falls back to
+ 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 (longest_chain > 256
- && total_chain > 256 * longest_chain)
+ 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)
}
}
+/* 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. */
very simple dead PHI removal here. */
if (!is_gimple_reg (gimple_phi_result (phi)))
{
- unsigned i;
- tree vuse;
-
/* Virtual PHI nodes with one or identical arguments
can be removed. */
- vuse = gimple_phi_arg_def (phi, 0);
- for (i = 1; i < gimple_phi_num_args (phi); ++i)
- {
- if (gimple_phi_arg_def (phi, i) != vuse)
- {
- vuse = NULL_TREE;
- break;
- }
- }
- if (vuse != NULL_TREE)
+ 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))
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
+ && TREE_CODE (vuse) == SSA_NAME)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
}
else
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);)
+ {
+ 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. */
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_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.
+ e = find_edge (bb, post_dom_bb);
- 3. If the post dominator has PHI nodes we may be able to compute
- the right PHI args for them.
-
- In each of these cases we must remove the control statement
- as it may reference SSA_NAMEs which are going to be removed and
- we remove all but one outgoing edge from the block. */
- 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;
-
- /* 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));
- }
+ 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);
+ 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. */
{
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))
{
+ bb = VEC_pop (basic_block, h);
+
/* 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))
{
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);
}
notice_special_calls (stmt);
}
- gsi_next (&gsi);
}
- else
+ }
+ }
+
+ 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))
{
- gsi_next (&gsi);
+ 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. */
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_free (visited_control_parents);
sbitmap_free (last_stmt_necessary);
+ sbitmap_free (bb_contains_live_stmts);
+ bb_contains_live_stmts = NULL;
}
sbitmap_free (processed);
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);
if (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);
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;
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
+ TODO_verify_ssa /* todo_flags_finish */
}
};
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
+ TODO_verify_ssa /* todo_flags_finish */
}
};
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_ssa
+ TODO_verify_ssa
| TODO_verify_flow /* todo_flags_finish */
}
};