/* Dead code elimination pass for the GNU compiler.
- Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
Contributed by Ben Elliston <bje@redhat.com>
and Andrew MacLeod <amacleod@redhat.com>
#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"
/* 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. */
+ after we're done.
+
+ When IGNORE_SELF it true, ignore BB from the list of control dependences. */
static void
-mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
+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);
gimple stmt;
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))
continue;
SET_BIT (last_stmt_necessary, cd_bb->index);
if (stmt && is_ctrl_stmt (stmt))
mark_stmt_necessary (stmt, true);
}
+ if (!skipped)
+ SET_BIT (visited_control_parents, bb->index);
}
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);
+ mark_control_dependent_edges_necessary (e->dest, el, false);
}
}
{
if (dump_file)
fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
- mark_control_dependent_edges_necessary (loop->latch, el);
+ mark_control_dependent_edges_necessary (loop->latch, el, false);
}
scev_finalize ();
}
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);
- }
+ mark_control_dependent_edges_necessary (bb, el, false);
}
if (gimple_code (stmt) == GIMPLE_PHI
mark_operand_necessary (arg);
}
+ /* 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))
+ {
+ gimple stmt2;
+ SET_BIT (last_stmt_necessary, arg_bb->index);
+ SET_BIT (bb_contains_live_stmts, arg_bb->index);
+
+ stmt2 = last_stmt (arg_bb);
+ if (stmt2 && is_ctrl_stmt (stmt2))
+ mark_stmt_necessary (stmt2, true);
+ }
}
+ else if (arg_bb != ENTRY_BLOCK_PTR
+ && ! TEST_BIT (visited_control_parents, arg_bb->index))
+ mark_control_dependent_edges_necessary (arg_bb, el, true);
}
}
}
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
if (e2 != e)
return e2;
- if (phi_nodes (post_dom_bb))
+ 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 look up the end of control dependent path leading
- to the PHI itself. */
+ 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 && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src))
+ if (e2 != e)
break;
for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (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. */
+ /* 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;
}
- 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
+
+ /* Dead PHI do not imply control dependency. */
+ if (!gimple_plf (phi, STMT_NECESSARY))
{
- op = gimple_phi_arg_def (phi, e2->dest_idx);
- locus = gimple_phi_arg_location (phi, e2->dest_idx);
+ 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);
- gcc_assert (e2 || degenerate_phi_p (phi));
+ /* The resulting PHI if not dead can only be degenerate. */
+ gcc_assert (degenerate_phi_p (phi));
gsi_next (&gsi);
}
}
edge e, e2;
edge_iterator ei;
- post_dom_bb = get_live_post_dom (bb);
+ post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
e = find_edge (bb, post_dom_bb);
OSDN Git Service
