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.
gimple_set_plf (stmt, STMT_NECESSARY, true);
if (add_to_worklist)
VEC_safe_push (gimple, heap, worklist, stmt);
+ if (bb_contains_live_stmts)
+ 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);
}
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))
}
}
+ /* 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 ();
}
}
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
mark_operand_necessary (arg);
}
- if (aggressive)
+ if (aggressive && !degenerate_phi_p (stmt))
{
for (k = 0; k < gimple_phi_num_args (stmt); k++)
{
}
}
+/* Replace all uses of result of PHI by underlying variable and mark it
+ for renaming. */
+
+static void
+mark_virtual_phi_result_for_renaming (gimple phi)
+{
+ bool used = false;
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ gimple stmt;
+ 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");
+ }
+ FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (phi))
+ {
+ if (gimple_code (stmt) != GIMPLE_PHI
+ && !gimple_plf (stmt, STMT_NECESSARY))
+ continue;
+ FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+ SET_USE (use_p, SSA_NAME_VAR (gimple_phi_result (phi)));
+ update_stmt (stmt);
+ used = true;
+ }
+ if (used)
+ mark_sym_for_renaming (SSA_NAME_VAR (PHI_RESULT (phi)));
+}
/* 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;
}
+/* 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;
+
+ /* 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);
+ else
+ op = gimple_phi_arg_def (phi, e2->dest_idx);
+ add_phi_arg (phi, op, e);
+ 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. */
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.
+ 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.
+ 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);
}
}
}
-
+ /* 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 next_bb;
+ find_unreachable_blocks ();
+ for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; bb = next_bb)
+ {
+ next_bb = bb->next_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))
+ delete_basic_block (bb);
+ }
+ }
+ }
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;
+ /* 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;
chain_ovfl = false;
OSDN Git Service
