ssa_name_values[SSA_NAME_VERSION (name)] = value;
}
-jump_threader::jump_threader (const_and_copies *copies,
- avail_exprs_stack *avails,
- jump_threader_simplifier *simplifier,
- evrp_range_analyzer *analyzer)
+jump_threader::jump_threader (jump_threader_simplifier *simplifier,
+ jt_state *state)
{
/* Initialize the per SSA_NAME value-handles array. */
gcc_assert (!ssa_name_values.exists ());
dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
integer_zero_node, NULL, NULL);
- m_const_and_copies = copies;
- m_avail_exprs_stack = avails;
- m_registry = new jump_thread_path_registry ();
+ m_registry = new fwd_jt_path_registry ();
m_simplifier = simplifier;
- m_evrp_range_analyzer = analyzer;
+ m_state = state;
}
jump_threader::~jump_threader (void)
return m_registry->thread_through_all_blocks (may_peel_loop_headers);
}
+static inline bool
+has_phis_p (basic_block bb)
+{
+ return !gsi_end_p (gsi_start_phis (bb));
+}
+
+/* Return TRUE for a block with PHIs but no statements. */
+
+static bool
+empty_block_with_phis_p (basic_block bb)
+{
+ return gsi_end_p (gsi_start_nondebug_bb (bb)) && has_phis_p (bb);
+}
+
/* Return TRUE if we may be able to thread an incoming edge into
BB to an outgoing edge from BB. Return FALSE otherwise. */
not optimized away because they forward from outside a loop
to the loop header. We want to thread through them as we can
sometimes thread to the loop exit, which is obviously profitable.
- the interesting case here is when the block has PHIs. */
- if (gsi_end_p (gsi_start_nondebug_bb (bb))
- && !gsi_end_p (gsi_start_phis (bb)))
+ The interesting case here is when the block has PHIs. */
+ if (empty_block_with_phis_p (bb))
return true;
/* If BB has a single successor or a single predecessor, then
if (!virtual_operand_p (dst))
stmt_count++;
- m_const_and_copies->record_const_or_copy (dst, src);
-
- /* Also update the value range associated with DST, using
- the range from SRC.
-
- Note that even if SRC is a constant we need to set a suitable
- output range so that VR_UNDEFINED ranges do not leak through. */
- if (m_evrp_range_analyzer)
- {
- /* Get an empty new VR we can pass to update_value_range and save
- away in the VR stack. */
- value_range_equiv *new_vr
- = m_evrp_range_analyzer->allocate_value_range_equiv ();
- new (new_vr) value_range_equiv ();
-
- /* There are three cases to consider:
-
- First if SRC is an SSA_NAME, then we can copy the value
- range from SRC into NEW_VR.
-
- Second if SRC is an INTEGER_CST, then we can just wet
- NEW_VR to a singleton range.
-
- Otherwise set NEW_VR to varying. This may be overly
- conservative. */
- if (TREE_CODE (src) == SSA_NAME)
- new_vr->deep_copy (m_evrp_range_analyzer->get_value_range (src));
- else if (TREE_CODE (src) == INTEGER_CST)
- new_vr->set (src);
- else
- new_vr->set_varying (TREE_TYPE (src));
-
- /* This is a temporary range for DST, so push it. */
- m_evrp_range_analyzer->push_value_range (dst, new_vr);
- }
+ m_state->register_equiv (dst, src, /*update_range=*/true);
}
return true;
}
return NULL;
}
- /* These are temporary ranges, do nto reflect them back into
- the global range data. */
- if (m_evrp_range_analyzer)
- m_evrp_range_analyzer->record_ranges_from_stmt (stmt, true);
+ m_state->record_ranges_from_stmt (stmt, true);
/* If this is not a statement that sets an SSA_NAME to a new
value, then do not try to simplify this statement as it will
SET_USE (use_p, tmp);
}
- cached_lhs = m_simplifier->simplify (stmt, stmt, e->src);
+ cached_lhs = m_simplifier->simplify (stmt, stmt, e->src, m_state);
/* Restore the statement's original uses/defs. */
i = 0;
if (cached_lhs
&& (TREE_CODE (cached_lhs) == SSA_NAME
|| is_gimple_min_invariant (cached_lhs)))
- m_const_and_copies->record_const_or_copy (gimple_get_lhs (stmt),
- cached_lhs);
+ m_state->register_equiv (gimple_get_lhs (stmt), cached_lhs);
}
return stmt;
}
= simplify_control_stmt_condition_1 (e, stmt, op0, cond_code, op1,
recursion_limit);
- /* If we were testing an integer/pointer against a constant, then
- we can use the FSM code to trace the value of the SSA_NAME. If
- a value is found, then the condition will collapse to a constant.
+ /* If we were testing an integer/pointer against a constant,
+ then we can trace the value of the SSA_NAME. If a value is
+ found, then the condition will collapse to a constant.
Return the SSA_NAME we want to trace back rather than the full
- expression and give the FSM threader a chance to find its value. */
+ expression and give the threader a chance to find its value. */
if (cached_lhs == NULL)
{
/* Recover the original operands. They may have been simplified
using context sensitive equivalences. Those context sensitive
- equivalences may not be valid on paths found by the FSM optimizer. */
+ equivalences may not be valid on paths. */
tree op0 = gimple_cond_lhs (stmt);
tree op1 = gimple_cond_rhs (stmt);
the label that is proven to be taken. */
gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
gimple_switch_set_index (dummy_switch, cached_lhs);
- cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src);
+ cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src,
+ m_state);
ggc_free (dummy_switch);
}
else
- cached_lhs = m_simplifier->simplify (stmt, stmt, e->src);
+ cached_lhs = m_simplifier->simplify (stmt, stmt, e->src, m_state);
}
/* We couldn't find an invariant. But, callers of this
then use the pass specific callback to simplify the condition. */
if (!res
|| !is_gimple_min_invariant (res))
- res = m_simplifier->simplify (dummy_cond, stmt, e->src);
+ res = m_simplifier->simplify (dummy_cond, stmt, e->src, m_state);
return res;
}
If it is threadable, add it to PATH and VISITED and recurse, ultimately
returning TRUE from the toplevel call. Otherwise do nothing and
- return false.
-
- The available expression table is referenced via AVAIL_EXPRS_STACK. */
+ return false. */
bool
jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
/* The key property of these blocks is that they need not be duplicated
when threading. Thus they cannot have visible side effects such
as PHI nodes. */
- if (!gsi_end_p (gsi_start_phis (bb)))
+ if (has_phis_p (bb))
return false;
/* Skip over DEBUG statements at the start of the block. */
if (!bitmap_bit_p (visited, taken_edge->dest->index))
{
- jump_thread_edge *x
- = m_registry->allocate_thread_edge (taken_edge,
- EDGE_NO_COPY_SRC_BLOCK);
- path->safe_push (x);
+ m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
bitmap_set_bit (visited, taken_edge->dest->index);
return thread_around_empty_blocks (path, taken_edge, visited);
}
return false;
bitmap_set_bit (visited, taken_edge->dest->index);
- jump_thread_edge *x
- = m_registry->allocate_thread_edge (taken_edge,
- EDGE_NO_COPY_SRC_BLOCK);
- path->safe_push (x);
+ m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
thread_around_empty_blocks (path, taken_edge, visited);
return true;
limited in that case to avoid short-circuiting the loop
incorrectly.
- STACK is used to undo temporary equivalences created during the walk of
- E->dest.
-
- Our caller is responsible for restoring the state of the expression
- and const_and_copies stacks.
-
Positive return value is success. Zero return value is failure, but
the block can still be duplicated as a joiner in a jump thread path,
negative indicates the block should not be duplicated and thus is not
jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
edge e, bitmap visited)
{
- /* We want to record any equivalences created by traversing E. */
- record_temporary_equivalences (e, m_const_and_copies, m_avail_exprs_stack);
+ m_state->register_equivs_on_edge (e);
/* PHIs create temporary equivalences.
Note that if we found a PHI that made the block non-threadable, then
{
/* First case. The statement simply doesn't have any instructions, but
does have PHIs. */
- if (gsi_end_p (gsi_start_nondebug_bb (e->dest))
- && !gsi_end_p (gsi_start_phis (e->dest)))
+ if (empty_block_with_phis_p (e->dest))
return 0;
/* Second case. */
/* Only push the EDGE_START_JUMP_THREAD marker if this is
first edge on the path. */
if (path->length () == 0)
- {
- jump_thread_edge *x
- = m_registry->allocate_thread_edge (e, EDGE_START_JUMP_THREAD);
- path->safe_push (x);
- }
+ m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
- jump_thread_edge *x
- = m_registry->allocate_thread_edge (taken_edge,
- EDGE_COPY_SRC_BLOCK);
- path->safe_push (x);
+ m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_BLOCK);
/* See if we can thread through DEST as well, this helps capture
secondary effects of threading without having to re-run DOM or
void
jump_threader::thread_across_edge (edge e)
{
- bitmap visited = BITMAP_ALLOC (NULL);
+ auto_bitmap visited;
- m_const_and_copies->push_marker ();
- m_avail_exprs_stack->push_marker ();
- if (m_evrp_range_analyzer)
- m_evrp_range_analyzer->push_marker ();
+ m_state->push (e);
stmt_count = 0;
vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
- bitmap_clear (visited);
bitmap_set_bit (visited, e->src->index);
bitmap_set_bit (visited, e->dest->index);
- int threaded;
+ int threaded = 0;
if ((e->flags & EDGE_DFS_BACK) == 0)
threaded = thread_through_normal_block (path, e, visited);
- else
- threaded = 0;
if (threaded > 0)
{
propagate_threaded_block_debug_into (path->last ()->e->dest,
e->dest);
- m_const_and_copies->pop_to_marker ();
- m_avail_exprs_stack->pop_to_marker ();
- if (m_evrp_range_analyzer)
- m_evrp_range_analyzer->pop_to_marker ();
- BITMAP_FREE (visited);
m_registry->register_jump_thread (path);
+ m_state->pop ();
return;
}
- else
- {
- /* Negative and zero return values indicate no threading was possible,
- thus there should be no edges on the thread path and no need to walk
- through the vector entries. */
- gcc_assert (path->length () == 0);
- path->release ();
- /* A negative status indicates the target block was deemed too big to
- duplicate. Just quit now rather than trying to use the block as
- a joiner in a jump threading path.
+ gcc_checking_assert (path->length () == 0);
+ path->release ();
+
+ if (threaded < 0)
+ {
+ /* The target block was deemed too big to duplicate. Just quit
+ now rather than trying to use the block as a joiner in a jump
+ threading path.
This prevents unnecessary code growth, but more importantly if we
do not look at all the statements in the block, then we may have
missed some invalidations if we had traversed a backedge! */
- if (threaded < 0)
- {
- BITMAP_FREE (visited);
- m_const_and_copies->pop_to_marker ();
- m_avail_exprs_stack->pop_to_marker ();
- if (m_evrp_range_analyzer)
- m_evrp_range_analyzer->pop_to_marker ();
- return;
- }
+ m_state->pop ();
+ return;
}
/* We were unable to determine what out edge from E->dest is taken. However,
FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
if (taken_edge->flags & EDGE_COMPLEX)
{
- m_const_and_copies->pop_to_marker ();
- m_avail_exprs_stack->pop_to_marker ();
- if (m_evrp_range_analyzer)
- m_evrp_range_analyzer->pop_to_marker ();
- BITMAP_FREE (visited);
+ m_state->pop ();
return;
}
|| (taken_edge->flags & EDGE_DFS_BACK) != 0)
continue;
- /* Push a fresh marker so we can unwind the equivalences created
- for each of E->dest's successors. */
- m_const_and_copies->push_marker ();
- m_avail_exprs_stack->push_marker ();
- if (m_evrp_range_analyzer)
- m_evrp_range_analyzer->push_marker ();
+ m_state->push (taken_edge);
/* Avoid threading to any block we have already visited. */
bitmap_clear (visited);
bitmap_set_bit (visited, e->src->index);
bitmap_set_bit (visited, e->dest->index);
bitmap_set_bit (visited, taken_edge->dest->index);
- vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
- /* Record whether or not we were able to thread through a successor
- of E->dest. */
- jump_thread_edge *x
- = m_registry->allocate_thread_edge (e, EDGE_START_JUMP_THREAD);
- path->safe_push (x);
+ vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
+ m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
+ m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
- x = m_registry->allocate_thread_edge (taken_edge,
- EDGE_COPY_SRC_JOINER_BLOCK);
- path->safe_push (x);
found = thread_around_empty_blocks (path, taken_edge, visited);
if (!found)
else
path->release ();
- /* And unwind the equivalence table. */
- if (m_evrp_range_analyzer)
- m_evrp_range_analyzer->pop_to_marker ();
- m_avail_exprs_stack->pop_to_marker ();
- m_const_and_copies->pop_to_marker ();
+ m_state->pop ();
}
- BITMAP_FREE (visited);
}
- if (m_evrp_range_analyzer)
- m_evrp_range_analyzer->pop_to_marker ();
- m_const_and_copies->pop_to_marker ();
- m_avail_exprs_stack->pop_to_marker ();
+ m_state->pop ();
+}
+
+/* Return TRUE if BB has a single successor to a block with multiple
+ incoming and outgoing edges. */
+
+bool
+single_succ_to_potentially_threadable_block (basic_block bb)
+{
+ int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
+ return (single_succ_p (bb)
+ && (single_succ_edge (bb)->flags & flags) == 0
+ && potentially_threadable_block (single_succ (bb)));
}
/* Examine the outgoing edges from BB and conditionally
outgoing edges, then we may be able to thread the edge, i.e., we
may be able to statically determine which of the outgoing edges
will be traversed when the incoming edge from BB is traversed. */
- if (single_succ_p (bb)
- && (single_succ_edge (bb)->flags & flags) == 0
- && potentially_threadable_block (single_succ (bb)))
- {
- thread_across_edge (single_succ_edge (bb));
- }
+ if (single_succ_to_potentially_threadable_block (bb))
+ thread_across_edge (single_succ_edge (bb));
else if ((last = last_stmt (bb))
&& gimple_code (last) == GIMPLE_COND
&& EDGE_COUNT (bb->succs) == 2
}
}
+jt_state::jt_state (const_and_copies *copies,
+ avail_exprs_stack *exprs,
+ evrp_range_analyzer *evrp)
+{
+ m_copies = copies;
+ m_exprs = exprs;
+ m_evrp = evrp;
+}
+
+// Record that E is being crossed.
+
+void
+jt_state::push (edge)
+{
+ if (m_copies)
+ m_copies->push_marker ();
+ if (m_exprs)
+ m_exprs->push_marker ();
+ if (m_evrp)
+ m_evrp->push_marker ();
+}
+
+// Pop to the last pushed state.
+
+void
+jt_state::pop ()
+{
+ if (m_copies)
+ m_copies->pop_to_marker ();
+ if (m_exprs)
+ m_exprs->pop_to_marker ();
+ if (m_evrp)
+ m_evrp->pop_to_marker ();
+}
+
+// Record an equivalence from DST to SRC. If UPDATE_RANGE is TRUE,
+// update the value range associated with DST.
+
+void
+jt_state::register_equiv (tree dst, tree src, bool update_range)
+{
+ if (m_copies)
+ m_copies->record_const_or_copy (dst, src);
+
+ /* If requested, update the value range associated with DST, using
+ the range from SRC. */
+ if (m_evrp && update_range)
+ {
+ /* Get new VR we can pass to push_value_range. */
+ value_range_equiv *new_vr = m_evrp->allocate_value_range_equiv ();
+ new (new_vr) value_range_equiv ();
+
+ /* There are three cases to consider:
+
+ First if SRC is an SSA_NAME, then we can copy the value range
+ from SRC into NEW_VR.
+
+ Second if SRC is an INTEGER_CST, then we can just set NEW_VR
+ to a singleton range. Note that even if SRC is a constant we
+ need to set a suitable output range so that VR_UNDEFINED
+ ranges do not leak through.
+
+ Otherwise set NEW_VR to varying. This may be overly
+ conservative. */
+ if (TREE_CODE (src) == SSA_NAME)
+ new_vr->deep_copy (m_evrp->get_value_range (src));
+ else if (TREE_CODE (src) == INTEGER_CST)
+ new_vr->set (src);
+ else
+ new_vr->set_varying (TREE_TYPE (src));
+
+ /* This is a temporary range for DST, so push it. */
+ m_evrp->push_value_range (dst, new_vr);
+ }
+}
+
+// Record any ranges calculated in STMT. If TEMPORARY is TRUE, then
+// this is a temporary equivalence and should be recorded into the
+// unwind table, instead of the global table.
+
+void
+jt_state::record_ranges_from_stmt (gimple *stmt, bool temporary)
+{
+ if (m_evrp)
+ m_evrp->record_ranges_from_stmt (stmt, temporary);
+}
+
+// Record any equivalences created by traversing E.
+
+void
+jt_state::register_equivs_on_edge (edge e)
+{
+ if (m_copies && m_exprs)
+ record_temporary_equivalences (e, m_copies, m_exprs);
+}
+
+jump_threader_simplifier::jump_threader_simplifier (vr_values *v)
+{
+ m_vr_values = v;
+}
+
+// Return the singleton that resolves STMT, if it is possible to
+// simplify it.
+//
+// STMT may be a dummy statement, not necessarily in the CFG, in which
+// case WITHIN_STMT can be used to determine the position in the CFG
+// where STMT should be evaluated as being in.
+
tree
jump_threader_simplifier::simplify (gimple *stmt,
gimple *within_stmt,
- basic_block)
+ basic_block,
+ jt_state *)
{
if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
{
projects / thirdparty / gcc.git / blobdiff