* [PATCH] Abstract out (forward) jump threader state handling.
@ 2021-07-27 10:19 Aldy Hernandez
2021-07-27 15:15 ` Jeff Law
0 siblings, 1 reply; 4+ messages in thread
From: Aldy Hernandez @ 2021-07-27 10:19 UTC (permalink / raw)
To: GCC patches, Jeff Law
The *forward* jump threader has multiple places where it pushes and
pops state, and where it sets context up for the jump threading
simplifier callback. Not only are the idioms repetitive, but the only
reason for passing const_and_copies, avail_exprs_stack, and the evrp
engine around are so we can set up context.
As part of my jump threading work, I will divorce the evrp engine from
the DOM jump threader, replacing it with a subset of the path solver I
have just contributed. Since this will entail passing even more
context around, I've abstracted out the state handling so it can be
passed around in one object. This cleans up the code, and also makes
it trivial to set up context with another engine in the future.
FWIW, I've used these cleanups with the path solver in a
proof-of-concept to improve DOM's threaded edges by an additional 5%,
and the overall threading opportunities in the compiler by 1%. This
is in addition to the gains I have documented in the backwards threader
rewrite.
There are no functional changes with this patch.
Tested on x86-64 Linux.
OK?
gcc/ChangeLog:
* tree-ssa-dom.c (dom_jump_threader_simplifier):
Put avail_exprs_stack in the class, instead of passing it to
jump_threader_simplifier.
(dom_jump_threader_simplifier::simplify): Add state argument.
(dom_opt_dom_walker): Add state.
(pass_dominator::execute): Pass state to threader.
(dom_opt_dom_walker::before_dom_children): Use state.
* tree-ssa-threadedge.c (jump_threader::jump_threader): Replace
arguments by state.
(jump_threader::record_temporary_equivalences_from_phis):
Register equivalences through the state variable.
(jump_threader::record_temporary_equivalences_from_stmts_at_dest):
Record ranges in a statement through the state variable.
(jump_threader::simplify_control_stmt_condition): Pass state to
simplify.
(jump_threader::simplify_control_stmt_condition_1): Same.
(jump_threader::thread_around_empty_blocks): Remove obsolete
comment.
(jump_threader::thread_through_normal_block): Record equivalences
on edge through the state variable.
(jump_threader::thread_across_edge): Abstract state pushing.
(jt_state::jt_state): New.
(jt_state::push): New.
(jt_state::pop): New.
(jt_state::register_equiv): New.
(jt_state::record_ranges_from_stmt): New.
(jt_state::register_equivs_on_edge): New.
(jump_threader_simplifier::jump_threader_simplifier): Move from
header.
(jump_threader_simplifier::simplify): Add state argument.
* tree-ssa-threadedge.h (class jt_state): New.
(class jump_threader): Add state to constructor.
(class jump_threader_simplifier): Add state to simplify. Remove
avail_exprs_stack from class.
* tree-vrp.c (vrp_jump_threader_simplifier::simplify): Add state
argument.
(vrp_jump_threader::vrp_jump_threader): Add state.
(vrp_jump_threader::~vrp_jump_threader): Cleanup state.
---
gcc/tree-ssa-dom.c | 21 ++--
gcc/tree-ssa-threadedge.c | 219 +++++++++++++++++++++-----------------
gcc/tree-ssa-threadedge.h | 39 ++++---
gcc/tree-vrp.c | 16 +--
4 files changed, 172 insertions(+), 123 deletions(-)
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index c231e6c8467..a0df492df10 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -590,16 +590,18 @@ class dom_jump_threader_simplifier : public jump_threader_simplifier
public:
dom_jump_threader_simplifier (vr_values *v,
avail_exprs_stack *avails)
- : jump_threader_simplifier (v, avails) {}
+ : jump_threader_simplifier (v), m_avail_exprs_stack (avails) { }
private:
- tree simplify (gimple *, gimple *, basic_block);
+ tree simplify (gimple *, gimple *, basic_block, jt_state *) override;
+ avail_exprs_stack *m_avail_exprs_stack;
};
tree
dom_jump_threader_simplifier::simplify (gimple *stmt,
gimple *within_stmt,
- basic_block bb)
+ basic_block bb,
+ jt_state *state)
{
/* First see if the conditional is in the hash table. */
tree cached_lhs = m_avail_exprs_stack->lookup_avail_expr (stmt,
@@ -607,7 +609,7 @@ dom_jump_threader_simplifier::simplify (gimple *stmt,
if (cached_lhs)
return cached_lhs;
- return jump_threader_simplifier::simplify (stmt, within_stmt, bb);
+ return jump_threader_simplifier::simplify (stmt, within_stmt, bb, state);
}
class dom_opt_dom_walker : public dom_walker
@@ -615,12 +617,14 @@ class dom_opt_dom_walker : public dom_walker
public:
dom_opt_dom_walker (cdi_direction direction,
jump_threader *threader,
+ jt_state *state,
evrp_range_analyzer *analyzer,
const_and_copies *const_and_copies,
avail_exprs_stack *avail_exprs_stack)
: dom_walker (direction, REACHABLE_BLOCKS)
{
m_evrp_range_analyzer = analyzer;
+ m_state = state;
m_dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
integer_zero_node, NULL, NULL);
m_const_and_copies = const_and_copies;
@@ -651,6 +655,7 @@ private:
jump_threader *m_threader;
evrp_range_analyzer *m_evrp_range_analyzer;
+ jt_state *m_state;
};
/* Jump threading, redundancy elimination and const/copy propagation.
@@ -748,10 +753,11 @@ pass_dominator::execute (function *fun)
/* Recursively walk the dominator tree optimizing statements. */
evrp_range_analyzer analyzer (true);
dom_jump_threader_simplifier simplifier (&analyzer, avail_exprs_stack);
- jump_threader threader (const_and_copies, avail_exprs_stack,
- &simplifier, &analyzer);
+ jt_state state (const_and_copies, avail_exprs_stack, &analyzer);
+ jump_threader threader (&simplifier, &state);
dom_opt_dom_walker walker (CDI_DOMINATORS,
&threader,
+ &state,
&analyzer,
const_and_copies,
avail_exprs_stack);
@@ -1419,8 +1425,7 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
continue;
}
- /* Compute range information and optimize the stmt. */
- m_evrp_range_analyzer->record_ranges_from_stmt (gsi_stmt (gsi), false);
+ m_state->record_ranges_from_stmt (gsi_stmt (gsi), false);
bool removed_p = false;
taken_edge = this->optimize_stmt (bb, &gsi, &removed_p);
if (!removed_p)
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 6ce32644aa5..24ccf014416 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -61,10 +61,8 @@ set_ssa_name_value (tree name, tree value)
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 ());
@@ -73,11 +71,9 @@ jump_threader::jump_threader (const_and_copies *copies,
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_simplifier = simplifier;
- m_evrp_range_analyzer = analyzer;
+ m_state = state;
}
jump_threader::~jump_threader (void)
@@ -168,41 +164,7 @@ jump_threader::record_temporary_equivalences_from_phis (edge e)
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;
}
@@ -304,10 +266,7 @@ jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
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
@@ -408,7 +367,7 @@ jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
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;
@@ -422,8 +381,7 @@ jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
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;
}
@@ -552,11 +510,12 @@ jump_threader::simplify_control_stmt_condition (edge e, gimple *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
@@ -733,7 +692,7 @@ jump_threader::simplify_control_stmt_condition_1
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;
}
@@ -880,9 +839,7 @@ propagate_threaded_block_debug_into (basic_block dest, basic_block src)
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,
@@ -997,12 +954,6 @@ jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
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
@@ -1012,8 +963,7 @@ int
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
@@ -1186,10 +1136,7 @@ jump_threader::thread_across_edge (edge e)
{
bitmap visited = BITMAP_ALLOC (NULL);
- 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;
@@ -1208,10 +1155,7 @@ jump_threader::thread_across_edge (edge e)
{
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 ();
+ m_state->pop ();
BITMAP_FREE (visited);
m_registry->register_jump_thread (path);
return;
@@ -1234,10 +1178,7 @@ jump_threader::thread_across_edge (edge e)
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 ();
+ m_state->pop ();
return;
}
}
@@ -1263,10 +1204,7 @@ jump_threader::thread_across_edge (edge e)
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 ();
+ m_state->pop ();
BITMAP_FREE (visited);
return;
}
@@ -1278,12 +1216,7 @@ jump_threader::thread_across_edge (edge e)
|| (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);
@@ -1320,19 +1253,12 @@ jump_threader::thread_across_edge (edge e)
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 ();
}
/* Examine the outgoing edges from BB and conditionally
@@ -1375,10 +1301,113 @@ jump_threader::thread_outgoing_edges (basic_block bb)
}
}
+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)
+{
+ m_copies->push_marker ();
+ m_exprs->push_marker ();
+ if (m_evrp)
+ m_evrp->push_marker ();
+}
+
+// Pop to the last pushed state.
+
+void
+jt_state::pop ()
+{
+ m_copies->pop_to_marker ();
+ 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)
+{
+ 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)
+{
+ 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))
{
diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h
index 48735f2bc27..c0d3c921e0f 100644
--- a/gcc/tree-ssa-threadedge.h
+++ b/gcc/tree-ssa-threadedge.h
@@ -20,6 +20,27 @@ along with GCC; see the file COPYING3. If not see
#ifndef GCC_TREE_SSA_THREADEDGE_H
#define GCC_TREE_SSA_THREADEDGE_H
+// Class used to maintain path state in the jump threader and pass it
+// to the jump threader simplifier.
+
+class jt_state
+{
+public:
+ jt_state (class const_and_copies *,
+ class avail_exprs_stack *,
+ class evrp_range_analyzer *);
+ void push (edge);
+ void pop ();
+ void register_equiv (tree dest, tree src, bool update_range = false);
+ void register_equivs_on_edge (edge e);
+ void record_ranges_from_stmt (gimple *stmt, bool temporary);
+
+private:
+ const_and_copies *m_copies;
+ avail_exprs_stack *m_exprs;
+ evrp_range_analyzer *m_evrp;
+};
+
// This is the high level threader. The entry point is
// thread_outgoing_edges(), which calculates and registers paths to be
// threaded. When all candidates have been registered,
@@ -28,10 +49,7 @@ along with GCC; see the file COPYING3. If not see
class jump_threader
{
public:
- jump_threader (class const_and_copies *,
- avail_exprs_stack *,
- class jump_threader_simplifier *,
- class evrp_range_analyzer * = NULL);
+ jump_threader (class jump_threader_simplifier *, class jt_state *);
~jump_threader ();
void thread_outgoing_edges (basic_block);
void remove_jump_threads_including (edge_def *);
@@ -57,11 +75,9 @@ private:
// Dummy condition to avoid creating lots of throw away statements.
gcond *dummy_cond;
- const_and_copies *m_const_and_copies;
- avail_exprs_stack *m_avail_exprs_stack;
class jump_thread_path_registry *m_registry;
jump_threader_simplifier *m_simplifier;
- evrp_range_analyzer *m_evrp_range_analyzer;
+ jt_state *m_state;
};
// Statement simplifier callback for the jump threader.
@@ -69,17 +85,12 @@ private:
class jump_threader_simplifier
{
public:
- jump_threader_simplifier (class vr_values *v,
- avail_exprs_stack *avails)
- : m_vr_values (v),
- m_avail_exprs_stack (avails)
- { }
+ jump_threader_simplifier (class vr_values *v);
virtual ~jump_threader_simplifier () { }
- virtual tree simplify (gimple *, gimple *, basic_block);
+ virtual tree simplify (gimple *, gimple *, basic_block, jt_state *);
protected:
vr_values *m_vr_values;
- avail_exprs_stack *m_avail_exprs_stack;
};
extern void propagate_threaded_block_debug_into (basic_block, basic_block);
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 58111f83183..d1b6910fcbb 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -4165,16 +4165,18 @@ class vrp_jump_threader_simplifier : public jump_threader_simplifier
{
public:
vrp_jump_threader_simplifier (vr_values *v, avail_exprs_stack *avails)
- : jump_threader_simplifier (v, avails) {}
+ : jump_threader_simplifier (v), m_avail_exprs_stack (avails) { }
private:
- tree simplify (gimple *, gimple *, basic_block) OVERRIDE;
+ tree simplify (gimple *, gimple *, basic_block, jt_state *) OVERRIDE;
+ avail_exprs_stack *m_avail_exprs_stack;
};
tree
vrp_jump_threader_simplifier::simplify (gimple *stmt,
gimple *within_stmt,
- basic_block bb)
+ basic_block bb,
+ jt_state *state)
{
/* First see if the conditional is in the hash table. */
tree cached_lhs = m_avail_exprs_stack->lookup_avail_expr (stmt, false, true);
@@ -4206,7 +4208,7 @@ vrp_jump_threader_simplifier::simplify (gimple *stmt,
return find_case_label_range (switch_stmt, vr);
}
- return jump_threader_simplifier::simplify (stmt, within_stmt, bb);
+ return jump_threader_simplifier::simplify (stmt, within_stmt, bb, state);
}
/* Blocks which have more than one predecessor and more than
@@ -4257,6 +4259,7 @@ private:
hash_table<expr_elt_hasher> *m_avail_exprs;
vrp_jump_threader_simplifier *m_simplifier;
jump_threader *m_threader;
+ jt_state *m_state;
};
vrp_jump_threader::vrp_jump_threader (struct function *fun, vr_values *v)
@@ -4282,11 +4285,11 @@ vrp_jump_threader::vrp_jump_threader (struct function *fun, vr_values *v)
m_vr_values = v;
m_avail_exprs = new hash_table<expr_elt_hasher> (1024);
m_avail_exprs_stack = new avail_exprs_stack (m_avail_exprs);
+ m_state = new jt_state (m_const_and_copies, m_avail_exprs_stack, NULL);
m_simplifier = new vrp_jump_threader_simplifier (m_vr_values,
m_avail_exprs_stack);
- m_threader = new jump_threader (m_const_and_copies, m_avail_exprs_stack,
- m_simplifier);
+ m_threader = new jump_threader (m_simplifier, m_state);
}
vrp_jump_threader::~vrp_jump_threader ()
@@ -4299,6 +4302,7 @@ vrp_jump_threader::~vrp_jump_threader ()
delete m_avail_exprs_stack;
delete m_simplifier;
delete m_threader;
+ delete m_state;
}
/* Called before processing dominator children of BB. We want to look
--
2.31.1
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Abstract out (forward) jump threader state handling.
2021-07-27 10:19 [PATCH] Abstract out (forward) jump threader state handling Aldy Hernandez
@ 2021-07-27 15:15 ` Jeff Law
2021-07-27 16:21 ` Aldy Hernandez
0 siblings, 1 reply; 4+ messages in thread
From: Jeff Law @ 2021-07-27 15:15 UTC (permalink / raw)
To: Aldy Hernandez, GCC patches
On 7/27/2021 4:19 AM, Aldy Hernandez wrote:
> The *forward* jump threader has multiple places where it pushes and
> pops state, and where it sets context up for the jump threading
> simplifier callback. Not only are the idioms repetitive, but the only
> reason for passing const_and_copies, avail_exprs_stack, and the evrp
> engine around are so we can set up context.
>
> As part of my jump threading work, I will divorce the evrp engine from
> the DOM jump threader, replacing it with a subset of the path solver I
> have just contributed. Since this will entail passing even more
> context around, I've abstracted out the state handling so it can be
> passed around in one object. This cleans up the code, and also makes
> it trivial to set up context with another engine in the future.
>
> FWIW, I've used these cleanups with the path solver in a
> proof-of-concept to improve DOM's threaded edges by an additional 5%,
> and the overall threading opportunities in the compiler by 1%. This
> is in addition to the gains I have documented in the backwards threader
> rewrite.
>
> There are no functional changes with this patch.
>
> Tested on x86-64 Linux.
>
> OK?
>
> gcc/ChangeLog:
>
> * tree-ssa-dom.c (dom_jump_threader_simplifier):
> Put avail_exprs_stack in the class, instead of passing it to
> jump_threader_simplifier.
> (dom_jump_threader_simplifier::simplify): Add state argument.
> (dom_opt_dom_walker): Add state.
> (pass_dominator::execute): Pass state to threader.
> (dom_opt_dom_walker::before_dom_children): Use state.
> * tree-ssa-threadedge.c (jump_threader::jump_threader): Replace
> arguments by state.
> (jump_threader::record_temporary_equivalences_from_phis):
> Register equivalences through the state variable.
> (jump_threader::record_temporary_equivalences_from_stmts_at_dest):
> Record ranges in a statement through the state variable.
> (jump_threader::simplify_control_stmt_condition): Pass state to
> simplify.
> (jump_threader::simplify_control_stmt_condition_1): Same.
> (jump_threader::thread_around_empty_blocks): Remove obsolete
> comment.
> (jump_threader::thread_through_normal_block): Record equivalences
> on edge through the state variable.
> (jump_threader::thread_across_edge): Abstract state pushing.
> (jt_state::jt_state): New.
> (jt_state::push): New.
> (jt_state::pop): New.
> (jt_state::register_equiv): New.
> (jt_state::record_ranges_from_stmt): New.
> (jt_state::register_equivs_on_edge): New.
> (jump_threader_simplifier::jump_threader_simplifier): Move from
> header.
> (jump_threader_simplifier::simplify): Add state argument.
> * tree-ssa-threadedge.h (class jt_state): New.
> (class jump_threader): Add state to constructor.
> (class jump_threader_simplifier): Add state to simplify. Remove
> avail_exprs_stack from class.
> * tree-vrp.c (vrp_jump_threader_simplifier::simplify): Add state
> argument.
> (vrp_jump_threader::vrp_jump_threader): Add state.
> (vrp_jump_threader::~vrp_jump_threader): Cleanup state.
Repetitive and not terribly consistent IIRC. The amount of state
certainly grew over time and I never went back and reorganized everything.
My recollection is there's also a case where the location of the state
push/pops are highly unintuitive. I always meant to put in some sanity
checking on the push/pops, then go back and bring some sanity to that
code as well. The one time I recall trying to clean this up (without
the sanity checking) I mucked it up badly -- and the only symptom was we
just started missing various jump threading opportunities ;( Mentioning
it for awareness.
OK and thanks so much for cleaning this up.
jeff
> ---
> gcc/tree-ssa-dom.c | 21 ++--
> gcc/tree-ssa-threadedge.c | 219 +++++++++++++++++++++-----------------
> gcc/tree-ssa-threadedge.h | 39 ++++---
> gcc/tree-vrp.c | 16 +--
> 4 files changed, 172 insertions(+), 123 deletions(-)
>
> diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
> index c231e6c8467..a0df492df10 100644
> --- a/gcc/tree-ssa-dom.c
> +++ b/gcc/tree-ssa-dom.c
> @@ -590,16 +590,18 @@ class dom_jump_threader_simplifier : public jump_threader_simplifier
> public:
> dom_jump_threader_simplifier (vr_values *v,
> avail_exprs_stack *avails)
> - : jump_threader_simplifier (v, avails) {}
> + : jump_threader_simplifier (v), m_avail_exprs_stack (avails) { }
>
> private:
> - tree simplify (gimple *, gimple *, basic_block);
> + tree simplify (gimple *, gimple *, basic_block, jt_state *) override;
> + avail_exprs_stack *m_avail_exprs_stack;
> };
>
> tree
> dom_jump_threader_simplifier::simplify (gimple *stmt,
> gimple *within_stmt,
> - basic_block bb)
> + basic_block bb,
> + jt_state *state)
> {
> /* First see if the conditional is in the hash table. */
> tree cached_lhs = m_avail_exprs_stack->lookup_avail_expr (stmt,
> @@ -607,7 +609,7 @@ dom_jump_threader_simplifier::simplify (gimple *stmt,
> if (cached_lhs)
> return cached_lhs;
>
> - return jump_threader_simplifier::simplify (stmt, within_stmt, bb);
> + return jump_threader_simplifier::simplify (stmt, within_stmt, bb, state);
> }
>
> class dom_opt_dom_walker : public dom_walker
> @@ -615,12 +617,14 @@ class dom_opt_dom_walker : public dom_walker
> public:
> dom_opt_dom_walker (cdi_direction direction,
> jump_threader *threader,
> + jt_state *state,
> evrp_range_analyzer *analyzer,
> const_and_copies *const_and_copies,
> avail_exprs_stack *avail_exprs_stack)
> : dom_walker (direction, REACHABLE_BLOCKS)
> {
> m_evrp_range_analyzer = analyzer;
> + m_state = state;
> m_dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
> integer_zero_node, NULL, NULL);
> m_const_and_copies = const_and_copies;
> @@ -651,6 +655,7 @@ private:
>
> jump_threader *m_threader;
> evrp_range_analyzer *m_evrp_range_analyzer;
> + jt_state *m_state;
> };
>
> /* Jump threading, redundancy elimination and const/copy propagation.
> @@ -748,10 +753,11 @@ pass_dominator::execute (function *fun)
> /* Recursively walk the dominator tree optimizing statements. */
> evrp_range_analyzer analyzer (true);
> dom_jump_threader_simplifier simplifier (&analyzer, avail_exprs_stack);
> - jump_threader threader (const_and_copies, avail_exprs_stack,
> - &simplifier, &analyzer);
> + jt_state state (const_and_copies, avail_exprs_stack, &analyzer);
> + jump_threader threader (&simplifier, &state);
> dom_opt_dom_walker walker (CDI_DOMINATORS,
> &threader,
> + &state,
> &analyzer,
> const_and_copies,
> avail_exprs_stack);
> @@ -1419,8 +1425,7 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
> continue;
> }
>
> - /* Compute range information and optimize the stmt. */
> - m_evrp_range_analyzer->record_ranges_from_stmt (gsi_stmt (gsi), false);
> + m_state->record_ranges_from_stmt (gsi_stmt (gsi), false);
> bool removed_p = false;
> taken_edge = this->optimize_stmt (bb, &gsi, &removed_p);
> if (!removed_p)
> diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
> index 6ce32644aa5..24ccf014416 100644
> --- a/gcc/tree-ssa-threadedge.c
> +++ b/gcc/tree-ssa-threadedge.c
> @@ -61,10 +61,8 @@ set_ssa_name_value (tree name, tree value)
> 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 ());
> @@ -73,11 +71,9 @@ jump_threader::jump_threader (const_and_copies *copies,
> 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_simplifier = simplifier;
> - m_evrp_range_analyzer = analyzer;
> + m_state = state;
> }
>
> jump_threader::~jump_threader (void)
> @@ -168,41 +164,7 @@ jump_threader::record_temporary_equivalences_from_phis (edge e)
> 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;
> }
> @@ -304,10 +266,7 @@ jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
> 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
> @@ -408,7 +367,7 @@ jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
> 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;
> @@ -422,8 +381,7 @@ jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
> 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;
> }
> @@ -552,11 +510,12 @@ jump_threader::simplify_control_stmt_condition (edge e, gimple *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
> @@ -733,7 +692,7 @@ jump_threader::simplify_control_stmt_condition_1
> 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;
> }
> @@ -880,9 +839,7 @@ propagate_threaded_block_debug_into (basic_block dest, basic_block src)
>
> 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,
> @@ -997,12 +954,6 @@ jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
> 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
> @@ -1012,8 +963,7 @@ int
> 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
> @@ -1186,10 +1136,7 @@ jump_threader::thread_across_edge (edge e)
> {
> bitmap visited = BITMAP_ALLOC (NULL);
>
> - 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;
>
> @@ -1208,10 +1155,7 @@ jump_threader::thread_across_edge (edge e)
> {
> 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 ();
> + m_state->pop ();
> BITMAP_FREE (visited);
> m_registry->register_jump_thread (path);
> return;
> @@ -1234,10 +1178,7 @@ jump_threader::thread_across_edge (edge e)
> 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 ();
> + m_state->pop ();
> return;
> }
> }
> @@ -1263,10 +1204,7 @@ jump_threader::thread_across_edge (edge e)
> 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 ();
> + m_state->pop ();
> BITMAP_FREE (visited);
> return;
> }
> @@ -1278,12 +1216,7 @@ jump_threader::thread_across_edge (edge e)
> || (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);
> @@ -1320,19 +1253,12 @@ jump_threader::thread_across_edge (edge e)
> 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 ();
> }
>
> /* Examine the outgoing edges from BB and conditionally
> @@ -1375,10 +1301,113 @@ jump_threader::thread_outgoing_edges (basic_block bb)
> }
> }
>
> +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)
> +{
> + m_copies->push_marker ();
> + m_exprs->push_marker ();
> + if (m_evrp)
> + m_evrp->push_marker ();
> +}
> +
> +// Pop to the last pushed state.
> +
> +void
> +jt_state::pop ()
> +{
> + m_copies->pop_to_marker ();
> + 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)
> +{
> + 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)
> +{
> + 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))
> {
> diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h
> index 48735f2bc27..c0d3c921e0f 100644
> --- a/gcc/tree-ssa-threadedge.h
> +++ b/gcc/tree-ssa-threadedge.h
> @@ -20,6 +20,27 @@ along with GCC; see the file COPYING3. If not see
> #ifndef GCC_TREE_SSA_THREADEDGE_H
> #define GCC_TREE_SSA_THREADEDGE_H
>
> +// Class used to maintain path state in the jump threader and pass it
> +// to the jump threader simplifier.
> +
> +class jt_state
> +{
> +public:
> + jt_state (class const_and_copies *,
> + class avail_exprs_stack *,
> + class evrp_range_analyzer *);
> + void push (edge);
> + void pop ();
> + void register_equiv (tree dest, tree src, bool update_range = false);
> + void register_equivs_on_edge (edge e);
> + void record_ranges_from_stmt (gimple *stmt, bool temporary);
> +
> +private:
> + const_and_copies *m_copies;
> + avail_exprs_stack *m_exprs;
> + evrp_range_analyzer *m_evrp;
> +};
> +
> // This is the high level threader. The entry point is
> // thread_outgoing_edges(), which calculates and registers paths to be
> // threaded. When all candidates have been registered,
> @@ -28,10 +49,7 @@ along with GCC; see the file COPYING3. If not see
> class jump_threader
> {
> public:
> - jump_threader (class const_and_copies *,
> - avail_exprs_stack *,
> - class jump_threader_simplifier *,
> - class evrp_range_analyzer * = NULL);
> + jump_threader (class jump_threader_simplifier *, class jt_state *);
> ~jump_threader ();
> void thread_outgoing_edges (basic_block);
> void remove_jump_threads_including (edge_def *);
> @@ -57,11 +75,9 @@ private:
> // Dummy condition to avoid creating lots of throw away statements.
> gcond *dummy_cond;
>
> - const_and_copies *m_const_and_copies;
> - avail_exprs_stack *m_avail_exprs_stack;
> class jump_thread_path_registry *m_registry;
> jump_threader_simplifier *m_simplifier;
> - evrp_range_analyzer *m_evrp_range_analyzer;
> + jt_state *m_state;
> };
>
> // Statement simplifier callback for the jump threader.
> @@ -69,17 +85,12 @@ private:
> class jump_threader_simplifier
> {
> public:
> - jump_threader_simplifier (class vr_values *v,
> - avail_exprs_stack *avails)
> - : m_vr_values (v),
> - m_avail_exprs_stack (avails)
> - { }
> + jump_threader_simplifier (class vr_values *v);
> virtual ~jump_threader_simplifier () { }
> - virtual tree simplify (gimple *, gimple *, basic_block);
> + virtual tree simplify (gimple *, gimple *, basic_block, jt_state *);
>
> protected:
> vr_values *m_vr_values;
> - avail_exprs_stack *m_avail_exprs_stack;
> };
>
> extern void propagate_threaded_block_debug_into (basic_block, basic_block);
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 58111f83183..d1b6910fcbb 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -4165,16 +4165,18 @@ class vrp_jump_threader_simplifier : public jump_threader_simplifier
> {
> public:
> vrp_jump_threader_simplifier (vr_values *v, avail_exprs_stack *avails)
> - : jump_threader_simplifier (v, avails) {}
> + : jump_threader_simplifier (v), m_avail_exprs_stack (avails) { }
>
> private:
> - tree simplify (gimple *, gimple *, basic_block) OVERRIDE;
> + tree simplify (gimple *, gimple *, basic_block, jt_state *) OVERRIDE;
> + avail_exprs_stack *m_avail_exprs_stack;
> };
>
> tree
> vrp_jump_threader_simplifier::simplify (gimple *stmt,
> gimple *within_stmt,
> - basic_block bb)
> + basic_block bb,
> + jt_state *state)
> {
> /* First see if the conditional is in the hash table. */
> tree cached_lhs = m_avail_exprs_stack->lookup_avail_expr (stmt, false, true);
> @@ -4206,7 +4208,7 @@ vrp_jump_threader_simplifier::simplify (gimple *stmt,
> return find_case_label_range (switch_stmt, vr);
> }
>
> - return jump_threader_simplifier::simplify (stmt, within_stmt, bb);
> + return jump_threader_simplifier::simplify (stmt, within_stmt, bb, state);
> }
>
> /* Blocks which have more than one predecessor and more than
> @@ -4257,6 +4259,7 @@ private:
> hash_table<expr_elt_hasher> *m_avail_exprs;
> vrp_jump_threader_simplifier *m_simplifier;
> jump_threader *m_threader;
> + jt_state *m_state;
> };
>
> vrp_jump_threader::vrp_jump_threader (struct function *fun, vr_values *v)
> @@ -4282,11 +4285,11 @@ vrp_jump_threader::vrp_jump_threader (struct function *fun, vr_values *v)
> m_vr_values = v;
> m_avail_exprs = new hash_table<expr_elt_hasher> (1024);
> m_avail_exprs_stack = new avail_exprs_stack (m_avail_exprs);
> + m_state = new jt_state (m_const_and_copies, m_avail_exprs_stack, NULL);
>
> m_simplifier = new vrp_jump_threader_simplifier (m_vr_values,
> m_avail_exprs_stack);
> - m_threader = new jump_threader (m_const_and_copies, m_avail_exprs_stack,
> - m_simplifier);
> + m_threader = new jump_threader (m_simplifier, m_state);
> }
>
> vrp_jump_threader::~vrp_jump_threader ()
> @@ -4299,6 +4302,7 @@ vrp_jump_threader::~vrp_jump_threader ()
> delete m_avail_exprs_stack;
> delete m_simplifier;
> delete m_threader;
> + delete m_state;
> }
>
> /* Called before processing dominator children of BB. We want to look
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Abstract out (forward) jump threader state handling.
2021-07-27 15:15 ` Jeff Law
@ 2021-07-27 16:21 ` Aldy Hernandez
2021-07-27 16:58 ` Jeff Law
0 siblings, 1 reply; 4+ messages in thread
From: Aldy Hernandez @ 2021-07-27 16:21 UTC (permalink / raw)
To: Jeff Law, GCC patches
On 7/27/21 5:15 PM, Jeff Law wrote:
> My recollection is there's also a case where the location of the state
> push/pops are highly unintuitive. I always meant to put in some sanity
> checking on the push/pops, then go back and bring some sanity to that
> code as well. The one time I recall trying to clean this up (without
> the sanity checking) I mucked it up badly -- and the only symptom was we
> just started missing various jump threading opportunities ;( Mentioning
> it for awareness.
Yes, I noticed that things were somewhat tricky.
For instance, the caller (DOM / VRP) can also push and pop
avails_exprs_stack/evrp/etc state, but I decided to ignore those since
the threader only cares about the threading candidates it's considering.
My ulterior purpose for this patch is to have a set of blocks / edges
that indicate a path, and pass those to the jump threader simplify callback.
In doing this I also found that the edges are not the only information
denoting a path. We also have (some) blocks pushed into the
jump_thread_edge (at least the EDGE_*COPY_SRC_BLOCK ones). I will be
adding the capacity to add those in a follow-up.
And yes it's been somewhat painful. What I've been doing is plugging
into the evrp use in DOM threader, and making sure that the my follow-up
changes to the path solver can simplify all the conds/switches that the
DOM/VRP threader simplifier can handle.
Ughhh, did any of this make sense? I manage to even confuse myself
while explaining it :).
>
> OK and thanks so much for cleaning this up.
NP. Thanks for reviewing them!
Aldy
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Abstract out (forward) jump threader state handling.
2021-07-27 16:21 ` Aldy Hernandez
@ 2021-07-27 16:58 ` Jeff Law
0 siblings, 0 replies; 4+ messages in thread
From: Jeff Law @ 2021-07-27 16:58 UTC (permalink / raw)
To: Aldy Hernandez, GCC patches
On 7/27/2021 10:21 AM, Aldy Hernandez wrote:
> On 7/27/21 5:15 PM, Jeff Law wrote:
>
>> My recollection is there's also a case where the location of the
>> state push/pops are highly unintuitive. I always meant to put in
>> some sanity checking on the push/pops, then go back and bring some
>> sanity to that code as well. The one time I recall trying to clean
>> this up (without the sanity checking) I mucked it up badly -- and the
>> only symptom was we just started missing various jump threading
>> opportunities ;( Mentioning it for awareness.
>
> Yes, I noticed that things were somewhat tricky.
>
> For instance, the caller (DOM / VRP) can also push and pop
> avails_exprs_stack/evrp/etc state, but I decided to ignore those since
> the threader only cares about the threading candidates it's considering.
Well, what's interesting is that DOM needs to save state before handing
off to the threader so that it's tables aren't polluted by the
threader. I think this is where those unintuitive push/pops were -- one
operation was in DOM and the other in the threader. Ugh!
>
> My ulterior purpose for this patch is to have a set of blocks / edges
> that indicate a path, and pass those to the jump threader simplify
> callback.
Right.
>
> In doing this I also found that the edges are not the only information
> denoting a path. We also have (some) blocks pushed into the
> jump_thread_edge (at least the EDGE_*COPY_SRC_BLOCK ones). I will be
> adding the capacity to add those in a follow-up.
Right those blocks are join points in the CFG. We don't know the static
result of the branch in the join block, but the join point may have a
successor with a conditional branch that we can thread. See:
https://gcc.gnu.org/legacy-ml/gcc-patches/2011-06/msg01190.html
A good mental model to use for this case is to imagine making a copy of
that block for each incoming edge. ie, each copy is only reachable from
one predecessor. That in turn allows jump threading to look deeper
through the CFG. If we find threadable jumps deeper in the CFG, then
we'll actually make those copies and scramble the CFG appropriately.
>
> And yes it's been somewhat painful. What I've been doing is plugging
> into the evrp use in DOM threader, and making sure that the my
> follow-up changes to the path solver can simplify all the
> conds/switches that the DOM/VRP threader simplifier can handle.
>
> Ughhh, did any of this make sense? I manage to even confuse myself
> while explaining it :).
Generally yes. In fact, it's forcing me to page in all kinds of things
I'd forgotten.
jeff
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2021-07-27 16:58 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-07-27 10:19 [PATCH] Abstract out (forward) jump threader state handling Aldy Hernandez
2021-07-27 15:15 ` Jeff Law
2021-07-27 16:21 ` Aldy Hernandez
2021-07-27 16:58 ` Jeff Law
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).