/* SSA Jump Threading
- Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
+ Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
Free Software Foundation, Inc.
Contributed by Jeff Law <law@redhat.com>
switch (get_gimple_rhs_class (subcode))
{
case GIMPLE_SINGLE_RHS:
- {
- tree rhs = gimple_assign_rhs1 (stmt);
-
- if (TREE_CODE (rhs) == COND_EXPR)
- {
- /* Sadly, we have to handle conditional assignments specially
- here, because fold expects all the operands of an expression
- to be folded before the expression itself is folded, but we
- can't just substitute the folded condition here. */
- tree cond = fold (COND_EXPR_COND (rhs));
- if (cond == boolean_true_node)
- rhs = COND_EXPR_THEN (rhs);
- else if (cond == boolean_false_node)
- rhs = COND_EXPR_ELSE (rhs);
- }
-
- return fold (rhs);
- }
+ return fold (gimple_assign_rhs1 (stmt));
case GIMPLE_UNARY_RHS:
{
tree op0 = gimple_assign_rhs1 (stmt);
tree op1 = gimple_assign_rhs2 (stmt);
tree op2 = gimple_assign_rhs3 (stmt);
+
+ /* Sadly, we have to handle conditional assignments specially
+ here, because fold expects all the operands of an expression
+ to be folded before the expression itself is folded, but we
+ can't just substitute the folded condition here. */
+ if (gimple_assign_rhs_code (stmt) == COND_EXPR)
+ op0 = fold (op0);
+
return fold_ternary (subcode, TREE_TYPE (lhs), op0, op1, op2);
}
return cached_lhs;
}
+/* TAKEN_EDGE represents the an edge taken as a result of jump threading.
+ See if we can thread around TAKEN_EDGE->dest as well. If so, return
+ the edge out of TAKEN_EDGE->dest that we can statically compute will be
+ traversed.
+
+ We are much more restrictive as to the contents of TAKEN_EDGE->dest
+ as the path isolation code in tree-ssa-threadupdate.c isn't prepared
+ to handle copying intermediate blocks on a threaded path.
+
+ Long term a more consistent and structured approach to path isolation
+ would be a huge help. */
+static edge
+thread_around_empty_block (edge taken_edge,
+ gimple dummy_cond,
+ bool handle_dominating_asserts,
+ tree (*simplify) (gimple, gimple),
+ bitmap visited)
+{
+ basic_block bb = taken_edge->dest;
+ gimple_stmt_iterator gsi;
+ gimple stmt;
+ tree cond;
+
+ /* This block must have a single predecessor (E->dest). */
+ if (!single_pred_p (bb))
+ return NULL;
+
+ /* This block must have more than one successor. */
+ if (single_succ_p (bb))
+ return NULL;
+
+ /* This block can have no PHI nodes. This is overly conservative. */
+ if (!gsi_end_p (gsi_start_phis (bb)))
+ return NULL;
+
+ /* Skip over DEBUG statements at the start of the block. */
+ gsi = gsi_start_nondebug_bb (bb);
+
+ if (gsi_end_p (gsi))
+ return NULL;
+
+ /* This block can have no statements other than its control altering
+ statement. This is overly conservative. */
+ stmt = gsi_stmt (gsi);
+ if (gimple_code (stmt) != GIMPLE_COND
+ && gimple_code (stmt) != GIMPLE_GOTO
+ && gimple_code (stmt) != GIMPLE_SWITCH)
+ return NULL;
+
+ /* Extract and simplify the condition. */
+ cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond,
+ simplify, handle_dominating_asserts);
+
+ /* If the condition can be statically computed and we have not already
+ visited the destination edge, then add the taken edge to our thread
+ path. */
+ if (cond && is_gimple_min_invariant (cond))
+ {
+ edge taken_edge = find_taken_edge (bb, cond);
+
+ if (bitmap_bit_p (visited, taken_edge->dest->index))
+ return NULL;
+ bitmap_set_bit (visited, taken_edge->dest->index);
+ return taken_edge;
+ }
+
+ return NULL;
+}
+
+/* E1 and E2 are edges into the same basic block. Return TRUE if the
+ PHI arguments associated with those edges are equal or there are no
+ PHI arguments, otherwise return FALSE. */
+
+static bool
+phi_args_equal_on_edges (edge e1, edge e2)
+{
+ gimple_stmt_iterator gsi;
+ int indx1 = e1->dest_idx;
+ int indx2 = e2->dest_idx;
+
+ for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+
+ if (!operand_equal_p (gimple_phi_arg_def (phi, indx1),
+ gimple_phi_arg_def (phi, indx2), 0))
+ return false;
+ }
+ return true;
+}
+
/* We are exiting E->src, see if E->dest ends with a conditional
jump which has a known value when reached via E.
tree cond;
/* Extract and simplify the condition. */
- cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify, handle_dominating_asserts);
+ cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
+ handle_dominating_asserts);
if (cond && is_gimple_min_invariant (cond))
{
edge taken_edge = find_taken_edge (e->dest, cond);
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
+ bitmap visited;
+ edge e2;
if (dest == e->dest)
goto fail;
+ /* DEST could be null for a computed jump to an absolute
+ address. If DEST is not null, then see if we can thread
+ through it as well, this helps capture secondary effects
+ of threading without having to re-run DOM or VRP. */
+ if (dest)
+ {
+ /* We don't want to thread back to a block we have already
+ visited. This may be overly conservative. */
+ visited = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (visited, dest->index);
+ bitmap_set_bit (visited, e->dest->index);
+ do
+ {
+ e2 = thread_around_empty_block (taken_edge,
+ dummy_cond,
+ handle_dominating_asserts,
+ simplify,
+ visited);
+ if (e2)
+ taken_edge = e2;
+ }
+ while (e2);
+ BITMAP_FREE (visited);
+ }
+
remove_temporary_equivalences (stack);
- register_jump_thread (e, taken_edge);
+ register_jump_thread (e, taken_edge, NULL);
+ return;
}
}
+ /* We were unable to determine what out edge from E->dest is taken. However,
+ we might still be able to thread through successors of E->dest. This
+ often occurs when E->dest is a joiner block which then fans back out
+ based on redundant tests.
+
+ If so, we'll copy E->dest and redirect the appropriate predecessor to
+ the copy. Within the copy of E->dest, we'll thread one or more edges
+ to points deeper in the CFG.
+
+ This is a stopgap until we have a more structured approach to path
+ isolation. */
+ {
+ edge e2, e3, taken_edge;
+ edge_iterator ei;
+ bool found = false;
+ bitmap visited = BITMAP_ALLOC (NULL);
+
+ /* Look at each successor of E->dest to see if we can thread through it. */
+ FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
+ {
+ /* Avoid threading to any block we have already visited. */
+ bitmap_clear (visited);
+ bitmap_set_bit (visited, taken_edge->dest->index);
+ bitmap_set_bit (visited, e->dest->index);
+
+ /* Record whether or not we were able to thread through a successor
+ of E->dest. */
+ found = false;
+ e3 = taken_edge;
+ do
+ {
+ e2 = thread_around_empty_block (e3,
+ dummy_cond,
+ handle_dominating_asserts,
+ simplify,
+ visited);
+ if (e2)
+ {
+ e3 = e2;
+ found = true;
+ }
+ }
+ while (e2);
+
+ /* If we were able to thread through a successor of E->dest, then
+ record the jump threading opportunity. */
+ if (found)
+ {
+ edge tmp;
+ /* If there is already an edge from the block to be duplicated
+ (E2->src) to the final target (E3->dest), then make sure that
+ the PHI args associated with the edges E2 and E3 are the
+ same. */
+ tmp = find_edge (taken_edge->src, e3->dest);
+ if (!tmp || phi_args_equal_on_edges (tmp, e3))
+ register_jump_thread (e, taken_edge, e3);
+ }
+
+ }
+ BITMAP_FREE (visited);
+ }
+
fail:
remove_temporary_equivalences (stack);
}