Message ID | 20220817115848.512165-1-aldyh@redhat.com |
---|---|
State | New |
Headers | show |
Series | Make path_range_query standalone and add reset_path. | expand |
FWIW, here is a rebased version with the latest trunk. There are no regressions, or differences in threading counts, and the performance change is negligible. Aldy On Wed, Aug 17, 2022 at 1:59 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > These are a bunch of cleanups inspired by Richi's suggestion of making > path_range_query standalone, instead of having to call > compute_ranges() for each path. > > I've made the ranger need explicit, and moved the responsibility for > its creation to the caller. > > I've also investigated and documented why the forward threader needs its > own compute exit dependencies variant. I can't wait for it to go away > :-/. > > I've also added constructors that take a path and dependencies, and > made compute_ranges() private. Unfortunately, reinstantiating > path_range_query in the forward threader caused a 14% performance > regression in DOM, because the old threader calls it over and over on > the same path to simplify statements (some of which not even in the > IL, but that's old news). > > In the meantime, I've left the ability to reset a path, but this time > appropriately called reset_path(). > > I've moved the verify_marked_backedges call to the threader. Is this > ok? > > Interestingly, comparing the thread counts for the patch yielded more > threads. I narrowed this down to a bug in the path oracle reset code > that's not cleaning things up as expected. I'll fix that before > committing this, but figured I'd post for comments in the meantime. > > Thoughts? > > gcc/ChangeLog: > > * gimple-range-path.cc (path_range_query::path_range_query): Add > various constructors to take a path. > (path_range_query::~path_range_query): Remove m_alloced_ranger. > (path_range_query::range_on_path_entry): Adjust for m_ranger being > a reference. > (path_range_query::set_path): Rename to... > (path_range_query::reset_path): ...this and call compute_ranges. > (path_range_query::ssa_range_in_phi): Adjust for m_ranger > reference. > (path_range_query::range_defined_in_block): Same. > (path_range_query::compute_ranges_in_block): Same. > (path_range_query::adjust_for_non_null_uses): Same. > (path_range_query::compute_exit_dependencies): Use m_path instead > of argument. > (path_range_query::compute_ranges): Remove path argument. > (path_range_query::range_of_stmt): Adjust for m_ranger reference. > (path_range_query::compute_outgoing_relations): Same. > * gimple-range-path.h (class path_range_query): Add various > constructors. > Make compute_ranges and compute_exit_dependencies private. > Rename set_path to reset_path. > Make m_ranger a reference. > Remove m_alloced_ranger. > * tree-ssa-dom.cc (pass_dominator::execute): Adjust constructor to > path_range_query. > * tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Take a > ranger and instantiate a new path_range_query every time. > (ch_base::copy_headers): Pass ranger instead of path_range_query. > * tree-ssa-threadbackward.cc (class back_threader): Remove m_solver. > (back_threader::~back_threader): Remove m_solver. > (back_threader::find_taken_edge_switch): Adjust for m_ranger > reference. > (back_threader::find_taken_edge_cond): Same. > (back_threader::dump): Remove m_solver. > (back_threader::back_threader): Move verify_marked_backedges > here from the path_range_query constructor. > * tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Move > some code from compute_ranges_from_state here. > (hybrid_jt_simplifier::compute_ranges_from_state): Rename... > (hybrid_jt_simplifier::compute_exit_dependencies): ...to this. > * tree-ssa-threadedge.h (class hybrid_jt_simplifier): Rename > compute_ranges_from_state to compute_exit_dependencies. > Remove m_path. > --- > gcc/gimple-range-path.cc | 112 +++++++++++++++++---------------- > gcc/gimple-range-path.h | 22 +++---- > gcc/tree-ssa-dom.cc | 2 +- > gcc/tree-ssa-loop-ch.cc | 12 ++-- > gcc/tree-ssa-threadbackward.cc | 27 ++++---- > gcc/tree-ssa-threadedge.cc | 30 +++++---- > gcc/tree-ssa-threadedge.h | 5 +- > 7 files changed, 111 insertions(+), 99 deletions(-) > > diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc > index c99d77dd340..d37605f4539 100644 > --- a/gcc/gimple-range-path.cc > +++ b/gcc/gimple-range-path.cc > @@ -36,33 +36,52 @@ along with GCC; see the file COPYING3. If not see > // Internal construct to help facilitate debugging of solver. > #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) > > -path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) > +path_range_query::path_range_query (gimple_ranger &ranger, > + const vec<basic_block> &path, > + const bitmap_head *dependencies, > + bool resolve) > : m_cache (new ssa_global_cache), > m_has_cache_entry (BITMAP_ALLOC (NULL)), > - m_resolve (resolve), > - m_alloced_ranger (!ranger) > + m_ranger (ranger), > + m_resolve (resolve) > { > - if (m_alloced_ranger) > - m_ranger = new gimple_ranger; > - else > - m_ranger = ranger; > + m_oracle = new path_oracle (m_ranger.oracle ()); > + > + reset_path (path, dependencies); > +} > > - m_oracle = new path_oracle (m_ranger->oracle ()); > +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) > + : m_cache (new ssa_global_cache), > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > + m_ranger (ranger), > + m_resolve (resolve) > +{ > + m_oracle = new path_oracle (m_ranger.oracle ()); > +} > > - if (m_resolve && flag_checking) > - verify_marked_backedges (cfun); > +path_range_query::path_range_query (gimple_ranger &ranger, > + edge e, > + bool resolve) > + : m_cache (new ssa_global_cache), > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > + m_ranger (ranger), > + m_resolve (resolve) > +{ > + m_oracle = new path_oracle (m_ranger.oracle ()); > + auto_vec<basic_block> bbs (2); > + bbs.quick_push (e->dest); > + bbs.quick_push (e->src); > + reset_path (bbs, NULL); > } > > path_range_query::~path_range_query () > { > delete m_oracle; > - if (m_alloced_ranger) > - delete m_ranger; > BITMAP_FREE (m_has_cache_entry); > delete m_cache; > } > > -// Return TRUE if NAME is an exit depenency for the path. > +// Return TRUE if NAME is an exit dependency for the path. > > bool > path_range_query::exit_dependency_p (tree name) > @@ -153,7 +172,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name) > { > gcc_checking_assert (defined_outside_path (name)); > basic_block entry = entry_bb (); > - m_ranger->range_on_entry (r, entry, name); > + m_ranger.range_on_entry (r, entry, name); > } > > // Return the range of NAME at the end of the path being analyzed. > @@ -211,19 +230,19 @@ path_range_query::unreachable_path_p () > return m_undefined_path; > } > > -// Initialize the current path to PATH. The current block is set to > -// the entry block to the path. > -// > -// Note that the blocks are in reverse order, so the exit block is > -// path[0]. > +// Reset the current path to PATH. > > void > -path_range_query::set_path (const vec<basic_block> &path) > +path_range_query::reset_path (const vec<basic_block> &path, > + const bitmap_head *dependencies) > { > gcc_checking_assert (path.length () > 1); > m_path = path.copy (); > m_pos = m_path.length () - 1; > + m_undefined_path = false; > bitmap_clear (m_has_cache_entry); > + > + compute_ranges (dependencies); > } > > bool > @@ -248,7 +267,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > if (at_entry ()) > { > - if (m_resolve && m_ranger->range_of_expr (r, name, phi)) > + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) > return; > > // Try to fold the phi exclusively with global or cached values. > @@ -290,7 +309,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > range_on_path_entry (r, arg); > else > r.set_varying (TREE_TYPE (name)); > - m_ranger->range_on_edge (tmp, e_in, arg); > + m_ranger.range_on_edge (tmp, e_in, arg); > r.intersect (tmp); > return; > } > @@ -325,7 +344,7 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) > } > > if (bb && POINTER_TYPE_P (TREE_TYPE (name))) > - m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); > + m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb); > > if (DEBUG_SOLVER && (bb || !r.varying_p ())) > { > @@ -442,7 +461,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) > p->set_root_oracle (nullptr); > } > > - gori_compute &g = m_ranger->gori (); > + gori_compute &g = m_ranger.gori (); > bitmap exports = g.exports (bb); > EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi) > { > @@ -496,7 +515,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) > else > r.set_varying (TREE_TYPE (name)); > > - if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) > + if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) > set_cache (r, name); > } > } > @@ -516,12 +535,11 @@ path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies) > // SSA names used to calculate the final conditional along the path. > > void > -path_range_query::compute_exit_dependencies (bitmap dependencies, > - const vec<basic_block> &path) > +path_range_query::compute_exit_dependencies (bitmap dependencies) > { > // Start with the imports from the exit block... > - basic_block exit = path[0]; > - gori_compute &gori = m_ranger->gori (); > + basic_block exit = m_path[0]; > + gori_compute &gori = m_ranger.gori (); > bitmap_copy (dependencies, gori.imports (exit)); > > auto_vec<tree> worklist (bitmap_count_bits (dependencies)); > @@ -539,7 +557,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > tree name = worklist.pop (); > gimple *def_stmt = SSA_NAME_DEF_STMT (name); > if (SSA_NAME_IS_DEFAULT_DEF (name) > - || !path.contains (gimple_bb (def_stmt))) > + || !m_path.contains (gimple_bb (def_stmt))) > continue; > > if (gphi *phi = dyn_cast <gphi *> (def_stmt)) > @@ -550,7 +568,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > tree arg = gimple_phi_arg (phi, i)->def; > > if (TREE_CODE (arg) == SSA_NAME > - && path.contains (e->src) > + && m_path.contains (e->src) > && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg))) > worklist.safe_push (arg); > } > @@ -582,9 +600,9 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > } > // Exported booleans along the path, may help conditionals. > if (m_resolve) > - for (i = 0; i < path.length (); ++i) > + for (i = 0; i < m_path.length (); ++i) > { > - basic_block bb = path[i]; > + basic_block bb = m_path[i]; > tree name; > FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) > if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) > @@ -600,19 +618,15 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > // calculated from the final conditional in the path. > > void > -path_range_query::compute_ranges (const vec<basic_block> &path, > - const bitmap_head *dependencies) > +path_range_query::compute_ranges (const bitmap_head *dependencies) > { > if (DEBUG_SOLVER) > fprintf (dump_file, "\n==============================================\n"); > > - set_path (path); > - m_undefined_path = false; > - > if (dependencies) > bitmap_copy (m_exit_dependencies, dependencies); > else > - compute_exit_dependencies (m_exit_dependencies, m_path); > + compute_exit_dependencies (m_exit_dependencies); > > if (m_resolve) > get_path_oracle ()->reset_path (); > @@ -620,9 +634,9 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > if (DEBUG_SOLVER) > { > fprintf (dump_file, "path_range_query: compute_ranges for path: "); > - for (unsigned i = path.length (); i > 0; --i) > + for (unsigned i = m_path.length (); i > 0; --i) > { > - basic_block bb = path[i - 1]; > + basic_block bb = m_path[i - 1]; > fprintf (dump_file, "%d", bb->index); > if (i > 1) > fprintf (dump_file, "->"); > @@ -650,18 +664,6 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > } > } > > -// Convenience function to compute ranges along a path consisting of > -// E->SRC and E->DEST. > - > -void > -path_range_query::compute_ranges (edge e) > -{ > - auto_vec<basic_block> bbs (2); > - bbs.quick_push (e->dest); > - bbs.quick_push (e->src); > - compute_ranges (bbs); > -} > - > // A folding aid used to register and query relations along a path. > // When queried, it returns relations as they would appear on exit to > // the path. > @@ -744,7 +746,7 @@ path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) > if (m_resolve) > { > fold_using_range f; > - jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); > + jt_fur_source src (stmt, this, &m_ranger.gori (), m_path); > if (!f.fold_stmt (r, stmt, src)) > r.set_varying (type); > } > @@ -834,7 +836,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) > else > gcc_unreachable (); > > - jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); > + jt_fur_source src (NULL, this, &m_ranger.gori (), m_path); > src.register_outgoing_edges (cond, r, e0, e1); > } > } > diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h > index 3cb794e34a9..483fde0d431 100644 > --- a/gcc/gimple-range-path.h > +++ b/gcc/gimple-range-path.h > @@ -32,13 +32,14 @@ along with GCC; see the file COPYING3. If not see > class path_range_query : public range_query > { > public: > - path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); > + path_range_query (class gimple_ranger &ranger, > + const vec<basic_block> &path, > + const bitmap_head *dependencies = NULL, > + bool resolve = true); > + path_range_query (gimple_ranger &ranger, bool resolve = true); > + path_range_query (gimple_ranger &ranger, edge e, bool resolve = true); > virtual ~path_range_query (); > - void compute_ranges (const vec<basic_block> &, > - const bitmap_head *dependencies = NULL); > - void compute_ranges (edge e); > - void compute_exit_dependencies (bitmap dependencies, > - const vec<basic_block> &); > + void reset_path (const vec<basic_block> &, const bitmap_head *dependencies); > bool range_of_expr (vrange &r, tree name, gimple * = NULL) override; > bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override; > bool unreachable_path_p (); > @@ -47,6 +48,8 @@ public: > > private: > bool internal_range_of_expr (vrange &r, tree name, gimple *); > + void compute_ranges (const bitmap_head *dependencies); > + void compute_exit_dependencies (bitmap_head *dependencies); > bool defined_outside_path (tree name); > void range_on_path_entry (vrange &r, tree name); > path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } > @@ -71,7 +74,6 @@ private: > bool relations_may_be_invalidated (edge); > > // Path navigation. > - void set_path (const vec<basic_block> &); > basic_block entry_bb () { return m_path[m_path.length () - 1]; } > basic_block exit_bb () { return m_path[0]; } > basic_block curr_bb () { return m_path[m_pos]; } > @@ -99,7 +101,7 @@ private: > > // A ranger used to resolve ranges for SSA names whose values come > // from outside the path. > - gimple_ranger *m_ranger; > + gimple_ranger &m_ranger; > > // Current path position. > unsigned m_pos; > @@ -109,10 +111,6 @@ private: > > // Set if there were any undefined expressions while pre-calculating path. > bool m_undefined_path; > - > - // True if m_ranger was allocated in this class and must be freed at > - // destruction. > - bool m_alloced_ranger; > }; > > #endif // GCC_TREE_SSA_THREADSOLVER_H > diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc > index 44dc27b464c..513e0c88254 100644 > --- a/gcc/tree-ssa-dom.cc > +++ b/gcc/tree-ssa-dom.cc > @@ -798,7 +798,7 @@ pass_dominator::execute (function *fun) > > /* Recursively walk the dominator tree optimizing statements. */ > gimple_ranger *ranger = enable_ranger (fun); > - path_range_query path_query (/*resolve=*/true, ranger); > + path_range_query path_query (*ranger); > dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query); > dom_jt_state state (const_and_copies, avail_exprs_stack); > jump_threader threader (&simplifier, &state); > diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc > index 3b91a89eaf5..96816b89287 100644 > --- a/gcc/tree-ssa-loop-ch.cc > +++ b/gcc/tree-ssa-loop-ch.cc > @@ -49,7 +49,7 @@ along with GCC; see the file COPYING3. If not see > be statically determined. */ > > static bool > -entry_loop_condition_is_static (class loop *l, path_range_query *query) > +entry_loop_condition_is_static (class loop *l, gimple_ranger *ranger) > { > edge e = loop_preheader_edge (l); > gcond *last = safe_dyn_cast <gcond *> (last_stmt (e->dest)); > @@ -72,8 +72,8 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query) > desired_static_value = boolean_true_node; > > int_range<2> r; > - query->compute_ranges (e); > - query->range_of_stmt (r, last); > + path_range_query query (*ranger, e); > + query.range_of_stmt (r, last); > return r == int_range<2> (desired_static_value, desired_static_value); > } > > @@ -385,7 +385,7 @@ ch_base::copy_headers (function *fun) > auto_vec<std::pair<edge, loop_p> > copied; > > mark_dfs_back_edges (); > - path_range_query *query = new path_range_query; > + gimple_ranger *ranger = new gimple_ranger; > for (auto loop : loops_list (cfun, 0)) > { > int initial_limit = param_max_loop_header_insns; > @@ -409,7 +409,7 @@ ch_base::copy_headers (function *fun) > iteration. */ > if (optimize_loop_for_size_p (loop) > && !loop->force_vectorize > - && !entry_loop_condition_is_static (loop, query)) > + && !entry_loop_condition_is_static (loop, ranger)) > { > if (dump_file && (dump_flags & TDF_DETAILS)) > fprintf (dump_file, > @@ -422,7 +422,7 @@ ch_base::copy_headers (function *fun) > candidates.safe_push (loop); > } > /* Do not use ranger after we change the IL and not have updated SSA. */ > - delete query; > + delete ranger; > > for (auto loop : candidates) > { > diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc > index b886027fccf..22748b9ec08 100644 > --- a/gcc/tree-ssa-threadbackward.cc > +++ b/gcc/tree-ssa-threadbackward.cc > @@ -99,7 +99,6 @@ private: > > back_threader_registry m_registry; > back_threader_profitability m_profit; > - path_range_query *m_solver; > > // Current path being analyzed. > auto_vec<basic_block> m_path; > @@ -119,6 +118,8 @@ private: > // with the ranger. Otherwise, unknown SSA names are assumed to be > // VARYING. Setting to true is more precise but slower. > function *m_fun; > + // Ranger for the path solver. > + gimple_ranger *m_ranger; > unsigned m_flags; > // Set to TRUE for the first of each thread[12] pass or the first of > // each threadfull[12] pass. This is used to differentiate between > @@ -145,14 +146,19 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) > > // The path solver needs EDGE_DFS_BACK in resolving mode. > if (flags & BT_RESOLVE) > - mark_dfs_back_edges (); > - m_solver = new path_range_query (flags & BT_RESOLVE); > + { > + mark_dfs_back_edges (); > + > + if (flag_checking) > + verify_marked_backedges (fun); > + } > + > + m_ranger = new gimple_ranger; > } > > back_threader::~back_threader () > { > - delete m_solver; > - > + delete m_ranger; > loop_optimizer_finalize (); > } > > @@ -290,8 +296,8 @@ back_threader::find_taken_edge_switch (const vec<basic_block> &path, > tree name = gimple_switch_index (sw); > int_range_max r; > > - m_solver->compute_ranges (path, m_imports); > - m_solver->range_of_expr (r, name, sw); > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > + solver.range_of_expr (r, name, sw); > > if (r.undefined_p ()) > return UNREACHABLE_EDGE; > @@ -314,10 +320,10 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path, > { > int_range_max r; > > - m_solver->compute_ranges (path, m_imports); > - m_solver->range_of_stmt (r, cond); > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > + solver.range_of_stmt (r, cond); > > - if (m_solver->unreachable_path_p ()) > + if (solver.unreachable_path_p ()) > return UNREACHABLE_EDGE; > > int_range<2> true_range (boolean_true_node, boolean_true_node); > @@ -588,7 +594,6 @@ debug (const vec <basic_block> &path) > void > back_threader::dump (FILE *out) > { > - m_solver->dump (out); > fprintf (out, "\nCandidates for pre-computation:\n"); > fprintf (out, "===================================\n"); > > diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc > index e64e4f209f7..905a98c8c68 100644 > --- a/gcc/tree-ssa-threadedge.cc > +++ b/gcc/tree-ssa-threadedge.cc > @@ -1399,7 +1399,6 @@ jt_state::register_equivs_stmt (gimple *stmt, basic_block bb, > > // Hybrid threader implementation. > > - > hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r, > path_range_query *q) > { > @@ -1411,7 +1410,12 @@ tree > hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > jt_state *state) > { > - compute_ranges_from_state (stmt, state); > + auto_bitmap dependencies; > + auto_vec<basic_block> path; > + > + state->get_path (path); > + compute_exit_dependencies (dependencies, path, stmt); > + m_query->reset_path (path, dependencies); > > if (gimple_code (stmt) == GIMPLE_COND > || gimple_code (stmt) == GIMPLE_ASSIGN) > @@ -1432,22 +1436,25 @@ hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > return NULL; > } > > -// Use STATE to generate the list of imports needed for the solver, > -// and calculate the ranges along the path. > +// Calculate the set of exit dependencies for a path and statement to > +// be simplified. This is different than the > +// compute_exit_dependencies in the path solver because the forward > +// threader asks questions about statements not necessarily in the > +// path. Using the default compute_exit_dependencies in the path > +// solver gets noticeably less threads. > > void > -hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > +hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies, > + const vec<basic_block> &path, > + gimple *stmt) > { > - auto_bitmap imports; > gori_compute &gori = m_ranger->gori (); > > - state->get_path (m_path); > - > // Start with the imports to the final conditional. > - bitmap_copy (imports, gori.imports (m_path[0])); > + bitmap_copy (dependencies, gori.imports (path[0])); > > // Add any other interesting operands we may have missed. > - if (gimple_bb (stmt) != m_path[0]) > + if (gimple_bb (stmt) != path[0]) > { > for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) > { > @@ -1455,8 +1462,7 @@ hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > if (op > && TREE_CODE (op) == SSA_NAME > && Value_Range::supports_type_p (TREE_TYPE (op))) > - bitmap_set_bit (imports, SSA_NAME_VERSION (op)); > + bitmap_set_bit (dependencies, SSA_NAME_VERSION (op)); > } > } > - m_query->compute_ranges (m_path, imports); > } > diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h > index ca70b33f5ed..790ac2ea538 100644 > --- a/gcc/tree-ssa-threadedge.h > +++ b/gcc/tree-ssa-threadedge.h > @@ -69,11 +69,12 @@ public: > tree simplify (gimple *stmt, gimple *, basic_block, jt_state *) override; > > private: > - void compute_ranges_from_state (gimple *stmt, jt_state *); > + void compute_exit_dependencies (bitmap dependencies, > + const vec<basic_block> &path, > + gimple *stmt); > > gimple_ranger *m_ranger; > path_range_query *m_query; > - auto_vec<basic_block> m_path; > }; > > // This is the high level threader. The entry point is > -- > 2.37.1 >
On Thu, Aug 18, 2022 at 9:58 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > FWIW, here is a rebased version with the latest trunk. > > There are no regressions, or differences in threading counts, and the > performance change is negligible. + { + mark_dfs_back_edges (); + + if (flag_checking) + verify_marked_backedges (fun); that looks redundant. Otherwise looks good - it might be possible to get rid of the reset_path use as well? Richard. > Aldy > > On Wed, Aug 17, 2022 at 1:59 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > These are a bunch of cleanups inspired by Richi's suggestion of making > > path_range_query standalone, instead of having to call > > compute_ranges() for each path. > > > > I've made the ranger need explicit, and moved the responsibility for > > its creation to the caller. > > > > I've also investigated and documented why the forward threader needs its > > own compute exit dependencies variant. I can't wait for it to go away > > :-/. > > > > I've also added constructors that take a path and dependencies, and > > made compute_ranges() private. Unfortunately, reinstantiating > > path_range_query in the forward threader caused a 14% performance > > regression in DOM, because the old threader calls it over and over on > > the same path to simplify statements (some of which not even in the > > IL, but that's old news). > > > > In the meantime, I've left the ability to reset a path, but this time > > appropriately called reset_path(). > > > > I've moved the verify_marked_backedges call to the threader. Is this > > ok? > > > > Interestingly, comparing the thread counts for the patch yielded more > > threads. I narrowed this down to a bug in the path oracle reset code > > that's not cleaning things up as expected. I'll fix that before > > committing this, but figured I'd post for comments in the meantime. > > > > Thoughts? > > > > gcc/ChangeLog: > > > > * gimple-range-path.cc (path_range_query::path_range_query): Add > > various constructors to take a path. > > (path_range_query::~path_range_query): Remove m_alloced_ranger. > > (path_range_query::range_on_path_entry): Adjust for m_ranger being > > a reference. > > (path_range_query::set_path): Rename to... > > (path_range_query::reset_path): ...this and call compute_ranges. > > (path_range_query::ssa_range_in_phi): Adjust for m_ranger > > reference. > > (path_range_query::range_defined_in_block): Same. > > (path_range_query::compute_ranges_in_block): Same. > > (path_range_query::adjust_for_non_null_uses): Same. > > (path_range_query::compute_exit_dependencies): Use m_path instead > > of argument. > > (path_range_query::compute_ranges): Remove path argument. > > (path_range_query::range_of_stmt): Adjust for m_ranger reference. > > (path_range_query::compute_outgoing_relations): Same. > > * gimple-range-path.h (class path_range_query): Add various > > constructors. > > Make compute_ranges and compute_exit_dependencies private. > > Rename set_path to reset_path. > > Make m_ranger a reference. > > Remove m_alloced_ranger. > > * tree-ssa-dom.cc (pass_dominator::execute): Adjust constructor to > > path_range_query. > > * tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Take a > > ranger and instantiate a new path_range_query every time. > > (ch_base::copy_headers): Pass ranger instead of path_range_query. > > * tree-ssa-threadbackward.cc (class back_threader): Remove m_solver. > > (back_threader::~back_threader): Remove m_solver. > > (back_threader::find_taken_edge_switch): Adjust for m_ranger > > reference. > > (back_threader::find_taken_edge_cond): Same. > > (back_threader::dump): Remove m_solver. > > (back_threader::back_threader): Move verify_marked_backedges > > here from the path_range_query constructor. > > * tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Move > > some code from compute_ranges_from_state here. > > (hybrid_jt_simplifier::compute_ranges_from_state): Rename... > > (hybrid_jt_simplifier::compute_exit_dependencies): ...to this. > > * tree-ssa-threadedge.h (class hybrid_jt_simplifier): Rename > > compute_ranges_from_state to compute_exit_dependencies. > > Remove m_path. > > --- > > gcc/gimple-range-path.cc | 112 +++++++++++++++++---------------- > > gcc/gimple-range-path.h | 22 +++---- > > gcc/tree-ssa-dom.cc | 2 +- > > gcc/tree-ssa-loop-ch.cc | 12 ++-- > > gcc/tree-ssa-threadbackward.cc | 27 ++++---- > > gcc/tree-ssa-threadedge.cc | 30 +++++---- > > gcc/tree-ssa-threadedge.h | 5 +- > > 7 files changed, 111 insertions(+), 99 deletions(-) > > > > diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc > > index c99d77dd340..d37605f4539 100644 > > --- a/gcc/gimple-range-path.cc > > +++ b/gcc/gimple-range-path.cc > > @@ -36,33 +36,52 @@ along with GCC; see the file COPYING3. If not see > > // Internal construct to help facilitate debugging of solver. > > #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) > > > > -path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) > > +path_range_query::path_range_query (gimple_ranger &ranger, > > + const vec<basic_block> &path, > > + const bitmap_head *dependencies, > > + bool resolve) > > : m_cache (new ssa_global_cache), > > m_has_cache_entry (BITMAP_ALLOC (NULL)), > > - m_resolve (resolve), > > - m_alloced_ranger (!ranger) > > + m_ranger (ranger), > > + m_resolve (resolve) > > { > > - if (m_alloced_ranger) > > - m_ranger = new gimple_ranger; > > - else > > - m_ranger = ranger; > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > + > > + reset_path (path, dependencies); > > +} > > > > - m_oracle = new path_oracle (m_ranger->oracle ()); > > +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) > > + : m_cache (new ssa_global_cache), > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > + m_ranger (ranger), > > + m_resolve (resolve) > > +{ > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > +} > > > > - if (m_resolve && flag_checking) > > - verify_marked_backedges (cfun); > > +path_range_query::path_range_query (gimple_ranger &ranger, > > + edge e, > > + bool resolve) > > + : m_cache (new ssa_global_cache), > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > + m_ranger (ranger), > > + m_resolve (resolve) > > +{ > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > + auto_vec<basic_block> bbs (2); > > + bbs.quick_push (e->dest); > > + bbs.quick_push (e->src); > > + reset_path (bbs, NULL); > > } > > > > path_range_query::~path_range_query () > > { > > delete m_oracle; > > - if (m_alloced_ranger) > > - delete m_ranger; > > BITMAP_FREE (m_has_cache_entry); > > delete m_cache; > > } > > > > -// Return TRUE if NAME is an exit depenency for the path. > > +// Return TRUE if NAME is an exit dependency for the path. > > > > bool > > path_range_query::exit_dependency_p (tree name) > > @@ -153,7 +172,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name) > > { > > gcc_checking_assert (defined_outside_path (name)); > > basic_block entry = entry_bb (); > > - m_ranger->range_on_entry (r, entry, name); > > + m_ranger.range_on_entry (r, entry, name); > > } > > > > // Return the range of NAME at the end of the path being analyzed. > > @@ -211,19 +230,19 @@ path_range_query::unreachable_path_p () > > return m_undefined_path; > > } > > > > -// Initialize the current path to PATH. The current block is set to > > -// the entry block to the path. > > -// > > -// Note that the blocks are in reverse order, so the exit block is > > -// path[0]. > > +// Reset the current path to PATH. > > > > void > > -path_range_query::set_path (const vec<basic_block> &path) > > +path_range_query::reset_path (const vec<basic_block> &path, > > + const bitmap_head *dependencies) > > { > > gcc_checking_assert (path.length () > 1); > > m_path = path.copy (); > > m_pos = m_path.length () - 1; > > + m_undefined_path = false; > > bitmap_clear (m_has_cache_entry); > > + > > + compute_ranges (dependencies); > > } > > > > bool > > @@ -248,7 +267,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > > > if (at_entry ()) > > { > > - if (m_resolve && m_ranger->range_of_expr (r, name, phi)) > > + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) > > return; > > > > // Try to fold the phi exclusively with global or cached values. > > @@ -290,7 +309,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > range_on_path_entry (r, arg); > > else > > r.set_varying (TREE_TYPE (name)); > > - m_ranger->range_on_edge (tmp, e_in, arg); > > + m_ranger.range_on_edge (tmp, e_in, arg); > > r.intersect (tmp); > > return; > > } > > @@ -325,7 +344,7 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) > > } > > > > if (bb && POINTER_TYPE_P (TREE_TYPE (name))) > > - m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); > > + m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb); > > > > if (DEBUG_SOLVER && (bb || !r.varying_p ())) > > { > > @@ -442,7 +461,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) > > p->set_root_oracle (nullptr); > > } > > > > - gori_compute &g = m_ranger->gori (); > > + gori_compute &g = m_ranger.gori (); > > bitmap exports = g.exports (bb); > > EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi) > > { > > @@ -496,7 +515,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) > > else > > r.set_varying (TREE_TYPE (name)); > > > > - if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > + if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > set_cache (r, name); > > } > > } > > @@ -516,12 +535,11 @@ path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies) > > // SSA names used to calculate the final conditional along the path. > > > > void > > -path_range_query::compute_exit_dependencies (bitmap dependencies, > > - const vec<basic_block> &path) > > +path_range_query::compute_exit_dependencies (bitmap dependencies) > > { > > // Start with the imports from the exit block... > > - basic_block exit = path[0]; > > - gori_compute &gori = m_ranger->gori (); > > + basic_block exit = m_path[0]; > > + gori_compute &gori = m_ranger.gori (); > > bitmap_copy (dependencies, gori.imports (exit)); > > > > auto_vec<tree> worklist (bitmap_count_bits (dependencies)); > > @@ -539,7 +557,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > tree name = worklist.pop (); > > gimple *def_stmt = SSA_NAME_DEF_STMT (name); > > if (SSA_NAME_IS_DEFAULT_DEF (name) > > - || !path.contains (gimple_bb (def_stmt))) > > + || !m_path.contains (gimple_bb (def_stmt))) > > continue; > > > > if (gphi *phi = dyn_cast <gphi *> (def_stmt)) > > @@ -550,7 +568,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > tree arg = gimple_phi_arg (phi, i)->def; > > > > if (TREE_CODE (arg) == SSA_NAME > > - && path.contains (e->src) > > + && m_path.contains (e->src) > > && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg))) > > worklist.safe_push (arg); > > } > > @@ -582,9 +600,9 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > } > > // Exported booleans along the path, may help conditionals. > > if (m_resolve) > > - for (i = 0; i < path.length (); ++i) > > + for (i = 0; i < m_path.length (); ++i) > > { > > - basic_block bb = path[i]; > > + basic_block bb = m_path[i]; > > tree name; > > FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) > > if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) > > @@ -600,19 +618,15 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > // calculated from the final conditional in the path. > > > > void > > -path_range_query::compute_ranges (const vec<basic_block> &path, > > - const bitmap_head *dependencies) > > +path_range_query::compute_ranges (const bitmap_head *dependencies) > > { > > if (DEBUG_SOLVER) > > fprintf (dump_file, "\n==============================================\n"); > > > > - set_path (path); > > - m_undefined_path = false; > > - > > if (dependencies) > > bitmap_copy (m_exit_dependencies, dependencies); > > else > > - compute_exit_dependencies (m_exit_dependencies, m_path); > > + compute_exit_dependencies (m_exit_dependencies); > > > > if (m_resolve) > > get_path_oracle ()->reset_path (); > > @@ -620,9 +634,9 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > if (DEBUG_SOLVER) > > { > > fprintf (dump_file, "path_range_query: compute_ranges for path: "); > > - for (unsigned i = path.length (); i > 0; --i) > > + for (unsigned i = m_path.length (); i > 0; --i) > > { > > - basic_block bb = path[i - 1]; > > + basic_block bb = m_path[i - 1]; > > fprintf (dump_file, "%d", bb->index); > > if (i > 1) > > fprintf (dump_file, "->"); > > @@ -650,18 +664,6 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > } > > } > > > > -// Convenience function to compute ranges along a path consisting of > > -// E->SRC and E->DEST. > > - > > -void > > -path_range_query::compute_ranges (edge e) > > -{ > > - auto_vec<basic_block> bbs (2); > > - bbs.quick_push (e->dest); > > - bbs.quick_push (e->src); > > - compute_ranges (bbs); > > -} > > - > > // A folding aid used to register and query relations along a path. > > // When queried, it returns relations as they would appear on exit to > > // the path. > > @@ -744,7 +746,7 @@ path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) > > if (m_resolve) > > { > > fold_using_range f; > > - jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); > > + jt_fur_source src (stmt, this, &m_ranger.gori (), m_path); > > if (!f.fold_stmt (r, stmt, src)) > > r.set_varying (type); > > } > > @@ -834,7 +836,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) > > else > > gcc_unreachable (); > > > > - jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); > > + jt_fur_source src (NULL, this, &m_ranger.gori (), m_path); > > src.register_outgoing_edges (cond, r, e0, e1); > > } > > } > > diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h > > index 3cb794e34a9..483fde0d431 100644 > > --- a/gcc/gimple-range-path.h > > +++ b/gcc/gimple-range-path.h > > @@ -32,13 +32,14 @@ along with GCC; see the file COPYING3. If not see > > class path_range_query : public range_query > > { > > public: > > - path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); > > + path_range_query (class gimple_ranger &ranger, > > + const vec<basic_block> &path, > > + const bitmap_head *dependencies = NULL, > > + bool resolve = true); > > + path_range_query (gimple_ranger &ranger, bool resolve = true); > > + path_range_query (gimple_ranger &ranger, edge e, bool resolve = true); > > virtual ~path_range_query (); > > - void compute_ranges (const vec<basic_block> &, > > - const bitmap_head *dependencies = NULL); > > - void compute_ranges (edge e); > > - void compute_exit_dependencies (bitmap dependencies, > > - const vec<basic_block> &); > > + void reset_path (const vec<basic_block> &, const bitmap_head *dependencies); > > bool range_of_expr (vrange &r, tree name, gimple * = NULL) override; > > bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override; > > bool unreachable_path_p (); > > @@ -47,6 +48,8 @@ public: > > > > private: > > bool internal_range_of_expr (vrange &r, tree name, gimple *); > > + void compute_ranges (const bitmap_head *dependencies); > > + void compute_exit_dependencies (bitmap_head *dependencies); > > bool defined_outside_path (tree name); > > void range_on_path_entry (vrange &r, tree name); > > path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } > > @@ -71,7 +74,6 @@ private: > > bool relations_may_be_invalidated (edge); > > > > // Path navigation. > > - void set_path (const vec<basic_block> &); > > basic_block entry_bb () { return m_path[m_path.length () - 1]; } > > basic_block exit_bb () { return m_path[0]; } > > basic_block curr_bb () { return m_path[m_pos]; } > > @@ -99,7 +101,7 @@ private: > > > > // A ranger used to resolve ranges for SSA names whose values come > > // from outside the path. > > - gimple_ranger *m_ranger; > > + gimple_ranger &m_ranger; > > > > // Current path position. > > unsigned m_pos; > > @@ -109,10 +111,6 @@ private: > > > > // Set if there were any undefined expressions while pre-calculating path. > > bool m_undefined_path; > > - > > - // True if m_ranger was allocated in this class and must be freed at > > - // destruction. > > - bool m_alloced_ranger; > > }; > > > > #endif // GCC_TREE_SSA_THREADSOLVER_H > > diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc > > index 44dc27b464c..513e0c88254 100644 > > --- a/gcc/tree-ssa-dom.cc > > +++ b/gcc/tree-ssa-dom.cc > > @@ -798,7 +798,7 @@ pass_dominator::execute (function *fun) > > > > /* Recursively walk the dominator tree optimizing statements. */ > > gimple_ranger *ranger = enable_ranger (fun); > > - path_range_query path_query (/*resolve=*/true, ranger); > > + path_range_query path_query (*ranger); > > dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query); > > dom_jt_state state (const_and_copies, avail_exprs_stack); > > jump_threader threader (&simplifier, &state); > > diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc > > index 3b91a89eaf5..96816b89287 100644 > > --- a/gcc/tree-ssa-loop-ch.cc > > +++ b/gcc/tree-ssa-loop-ch.cc > > @@ -49,7 +49,7 @@ along with GCC; see the file COPYING3. If not see > > be statically determined. */ > > > > static bool > > -entry_loop_condition_is_static (class loop *l, path_range_query *query) > > +entry_loop_condition_is_static (class loop *l, gimple_ranger *ranger) > > { > > edge e = loop_preheader_edge (l); > > gcond *last = safe_dyn_cast <gcond *> (last_stmt (e->dest)); > > @@ -72,8 +72,8 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query) > > desired_static_value = boolean_true_node; > > > > int_range<2> r; > > - query->compute_ranges (e); > > - query->range_of_stmt (r, last); > > + path_range_query query (*ranger, e); > > + query.range_of_stmt (r, last); > > return r == int_range<2> (desired_static_value, desired_static_value); > > } > > > > @@ -385,7 +385,7 @@ ch_base::copy_headers (function *fun) > > auto_vec<std::pair<edge, loop_p> > copied; > > > > mark_dfs_back_edges (); > > - path_range_query *query = new path_range_query; > > + gimple_ranger *ranger = new gimple_ranger; > > for (auto loop : loops_list (cfun, 0)) > > { > > int initial_limit = param_max_loop_header_insns; > > @@ -409,7 +409,7 @@ ch_base::copy_headers (function *fun) > > iteration. */ > > if (optimize_loop_for_size_p (loop) > > && !loop->force_vectorize > > - && !entry_loop_condition_is_static (loop, query)) > > + && !entry_loop_condition_is_static (loop, ranger)) > > { > > if (dump_file && (dump_flags & TDF_DETAILS)) > > fprintf (dump_file, > > @@ -422,7 +422,7 @@ ch_base::copy_headers (function *fun) > > candidates.safe_push (loop); > > } > > /* Do not use ranger after we change the IL and not have updated SSA. */ > > - delete query; > > + delete ranger; > > > > for (auto loop : candidates) > > { > > diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc > > index b886027fccf..22748b9ec08 100644 > > --- a/gcc/tree-ssa-threadbackward.cc > > +++ b/gcc/tree-ssa-threadbackward.cc > > @@ -99,7 +99,6 @@ private: > > > > back_threader_registry m_registry; > > back_threader_profitability m_profit; > > - path_range_query *m_solver; > > > > // Current path being analyzed. > > auto_vec<basic_block> m_path; > > @@ -119,6 +118,8 @@ private: > > // with the ranger. Otherwise, unknown SSA names are assumed to be > > // VARYING. Setting to true is more precise but slower. > > function *m_fun; > > + // Ranger for the path solver. > > + gimple_ranger *m_ranger; > > unsigned m_flags; > > // Set to TRUE for the first of each thread[12] pass or the first of > > // each threadfull[12] pass. This is used to differentiate between > > @@ -145,14 +146,19 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) > > > > // The path solver needs EDGE_DFS_BACK in resolving mode. > > if (flags & BT_RESOLVE) > > - mark_dfs_back_edges (); > > - m_solver = new path_range_query (flags & BT_RESOLVE); > > + { > > + mark_dfs_back_edges (); > > + > > + if (flag_checking) > > + verify_marked_backedges (fun); > > + } > > + > > + m_ranger = new gimple_ranger; > > } > > > > back_threader::~back_threader () > > { > > - delete m_solver; > > - > > + delete m_ranger; > > loop_optimizer_finalize (); > > } > > > > @@ -290,8 +296,8 @@ back_threader::find_taken_edge_switch (const vec<basic_block> &path, > > tree name = gimple_switch_index (sw); > > int_range_max r; > > > > - m_solver->compute_ranges (path, m_imports); > > - m_solver->range_of_expr (r, name, sw); > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > + solver.range_of_expr (r, name, sw); > > > > if (r.undefined_p ()) > > return UNREACHABLE_EDGE; > > @@ -314,10 +320,10 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path, > > { > > int_range_max r; > > > > - m_solver->compute_ranges (path, m_imports); > > - m_solver->range_of_stmt (r, cond); > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > + solver.range_of_stmt (r, cond); > > > > - if (m_solver->unreachable_path_p ()) > > + if (solver.unreachable_path_p ()) > > return UNREACHABLE_EDGE; > > > > int_range<2> true_range (boolean_true_node, boolean_true_node); > > @@ -588,7 +594,6 @@ debug (const vec <basic_block> &path) > > void > > back_threader::dump (FILE *out) > > { > > - m_solver->dump (out); > > fprintf (out, "\nCandidates for pre-computation:\n"); > > fprintf (out, "===================================\n"); > > > > diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc > > index e64e4f209f7..905a98c8c68 100644 > > --- a/gcc/tree-ssa-threadedge.cc > > +++ b/gcc/tree-ssa-threadedge.cc > > @@ -1399,7 +1399,6 @@ jt_state::register_equivs_stmt (gimple *stmt, basic_block bb, > > > > // Hybrid threader implementation. > > > > - > > hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r, > > path_range_query *q) > > { > > @@ -1411,7 +1410,12 @@ tree > > hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > jt_state *state) > > { > > - compute_ranges_from_state (stmt, state); > > + auto_bitmap dependencies; > > + auto_vec<basic_block> path; > > + > > + state->get_path (path); > > + compute_exit_dependencies (dependencies, path, stmt); > > + m_query->reset_path (path, dependencies); > > > > if (gimple_code (stmt) == GIMPLE_COND > > || gimple_code (stmt) == GIMPLE_ASSIGN) > > @@ -1432,22 +1436,25 @@ hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > return NULL; > > } > > > > -// Use STATE to generate the list of imports needed for the solver, > > -// and calculate the ranges along the path. > > +// Calculate the set of exit dependencies for a path and statement to > > +// be simplified. This is different than the > > +// compute_exit_dependencies in the path solver because the forward > > +// threader asks questions about statements not necessarily in the > > +// path. Using the default compute_exit_dependencies in the path > > +// solver gets noticeably less threads. > > > > void > > -hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > +hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies, > > + const vec<basic_block> &path, > > + gimple *stmt) > > { > > - auto_bitmap imports; > > gori_compute &gori = m_ranger->gori (); > > > > - state->get_path (m_path); > > - > > // Start with the imports to the final conditional. > > - bitmap_copy (imports, gori.imports (m_path[0])); > > + bitmap_copy (dependencies, gori.imports (path[0])); > > > > // Add any other interesting operands we may have missed. > > - if (gimple_bb (stmt) != m_path[0]) > > + if (gimple_bb (stmt) != path[0]) > > { > > for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) > > { > > @@ -1455,8 +1462,7 @@ hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > if (op > > && TREE_CODE (op) == SSA_NAME > > && Value_Range::supports_type_p (TREE_TYPE (op))) > > - bitmap_set_bit (imports, SSA_NAME_VERSION (op)); > > + bitmap_set_bit (dependencies, SSA_NAME_VERSION (op)); > > } > > } > > - m_query->compute_ranges (m_path, imports); > > } > > diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h > > index ca70b33f5ed..790ac2ea538 100644 > > --- a/gcc/tree-ssa-threadedge.h > > +++ b/gcc/tree-ssa-threadedge.h > > @@ -69,11 +69,12 @@ public: > > tree simplify (gimple *stmt, gimple *, basic_block, jt_state *) override; > > > > private: > > - void compute_ranges_from_state (gimple *stmt, jt_state *); > > + void compute_exit_dependencies (bitmap dependencies, > > + const vec<basic_block> &path, > > + gimple *stmt); > > > > gimple_ranger *m_ranger; > > path_range_query *m_query; > > - auto_vec<basic_block> m_path; > > }; > > > > // This is the high level threader. The entry point is > > -- > > 2.37.1 > >
On Thu, Aug 18, 2022, 11:34 Richard Biener <richard.guenther@gmail.com> wrote: > > On Thu, Aug 18, 2022 at 9:58 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > FWIW, here is a rebased version with the latest trunk. > > > > There are no regressions, or differences in threading counts, and the > > performance change is negligible. > > + { > + mark_dfs_back_edges (); > + > + if (flag_checking) > + verify_marked_backedges (fun); > > that looks redundant. Do you suggest somewhere else, or should we nuke verify_marked_backedges altogether since that's its only use? > > Otherwise looks good - it might be possible to get rid of the reset_path use > as well? That's what I mentioned wrt DOM threading. There's a 14% degradation from not reusing the path_range_query in the forward threader because it really abuses the query to try to simplify its statements. So I've left reset_path for it to use, but we can get rid of it when we nuke the old threader. Aldy Aldy > > Richard. > > > Aldy > > > > On Wed, Aug 17, 2022 at 1:59 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > > > These are a bunch of cleanups inspired by Richi's suggestion of making > > > path_range_query standalone, instead of having to call > > > compute_ranges() for each path. > > > > > > I've made the ranger need explicit, and moved the responsibility for > > > its creation to the caller. > > > > > > I've also investigated and documented why the forward threader needs its > > > own compute exit dependencies variant. I can't wait for it to go away > > > :-/. > > > > > > I've also added constructors that take a path and dependencies, and > > > made compute_ranges() private. Unfortunately, reinstantiating > > > path_range_query in the forward threader caused a 14% performance > > > regression in DOM, because the old threader calls it over and over on > > > the same path to simplify statements (some of which not even in the > > > IL, but that's old news). > > > > > > In the meantime, I've left the ability to reset a path, but this time > > > appropriately called reset_path(). > > > > > > I've moved the verify_marked_backedges call to the threader. Is this > > > ok? > > > > > > Interestingly, comparing the thread counts for the patch yielded more > > > threads. I narrowed this down to a bug in the path oracle reset code > > > that's not cleaning things up as expected. I'll fix that before > > > committing this, but figured I'd post for comments in the meantime. > > > > > > Thoughts? > > > > > > gcc/ChangeLog: > > > > > > * gimple-range-path.cc (path_range_query::path_range_query): Add > > > various constructors to take a path. > > > (path_range_query::~path_range_query): Remove m_alloced_ranger. > > > (path_range_query::range_on_path_entry): Adjust for m_ranger being > > > a reference. > > > (path_range_query::set_path): Rename to... > > > (path_range_query::reset_path): ...this and call compute_ranges. > > > (path_range_query::ssa_range_in_phi): Adjust for m_ranger > > > reference. > > > (path_range_query::range_defined_in_block): Same. > > > (path_range_query::compute_ranges_in_block): Same. > > > (path_range_query::adjust_for_non_null_uses): Same. > > > (path_range_query::compute_exit_dependencies): Use m_path instead > > > of argument. > > > (path_range_query::compute_ranges): Remove path argument. > > > (path_range_query::range_of_stmt): Adjust for m_ranger reference. > > > (path_range_query::compute_outgoing_relations): Same. > > > * gimple-range-path.h (class path_range_query): Add various > > > constructors. > > > Make compute_ranges and compute_exit_dependencies private. > > > Rename set_path to reset_path. > > > Make m_ranger a reference. > > > Remove m_alloced_ranger. > > > * tree-ssa-dom.cc (pass_dominator::execute): Adjust constructor to > > > path_range_query. > > > * tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Take a > > > ranger and instantiate a new path_range_query every time. > > > (ch_base::copy_headers): Pass ranger instead of path_range_query. > > > * tree-ssa-threadbackward.cc (class back_threader): Remove m_solver. > > > (back_threader::~back_threader): Remove m_solver. > > > (back_threader::find_taken_edge_switch): Adjust for m_ranger > > > reference. > > > (back_threader::find_taken_edge_cond): Same. > > > (back_threader::dump): Remove m_solver. > > > (back_threader::back_threader): Move verify_marked_backedges > > > here from the path_range_query constructor. > > > * tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Move > > > some code from compute_ranges_from_state here. > > > (hybrid_jt_simplifier::compute_ranges_from_state): Rename... > > > (hybrid_jt_simplifier::compute_exit_dependencies): ...to this. > > > * tree-ssa-threadedge.h (class hybrid_jt_simplifier): Rename > > > compute_ranges_from_state to compute_exit_dependencies. > > > Remove m_path. > > > --- > > > gcc/gimple-range-path.cc | 112 +++++++++++++++++---------------- > > > gcc/gimple-range-path.h | 22 +++---- > > > gcc/tree-ssa-dom.cc | 2 +- > > > gcc/tree-ssa-loop-ch.cc | 12 ++-- > > > gcc/tree-ssa-threadbackward.cc | 27 ++++---- > > > gcc/tree-ssa-threadedge.cc | 30 +++++---- > > > gcc/tree-ssa-threadedge.h | 5 +- > > > 7 files changed, 111 insertions(+), 99 deletions(-) > > > > > > diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc > > > index c99d77dd340..d37605f4539 100644 > > > --- a/gcc/gimple-range-path.cc > > > +++ b/gcc/gimple-range-path.cc > > > @@ -36,33 +36,52 @@ along with GCC; see the file COPYING3. If not see > > > // Internal construct to help facilitate debugging of solver. > > > #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) > > > > > > -path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) > > > +path_range_query::path_range_query (gimple_ranger &ranger, > > > + const vec<basic_block> &path, > > > + const bitmap_head *dependencies, > > > + bool resolve) > > > : m_cache (new ssa_global_cache), > > > m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > - m_resolve (resolve), > > > - m_alloced_ranger (!ranger) > > > + m_ranger (ranger), > > > + m_resolve (resolve) > > > { > > > - if (m_alloced_ranger) > > > - m_ranger = new gimple_ranger; > > > - else > > > - m_ranger = ranger; > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > + > > > + reset_path (path, dependencies); > > > +} > > > > > > - m_oracle = new path_oracle (m_ranger->oracle ()); > > > +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) > > > + : m_cache (new ssa_global_cache), > > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > + m_ranger (ranger), > > > + m_resolve (resolve) > > > +{ > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > +} > > > > > > - if (m_resolve && flag_checking) > > > - verify_marked_backedges (cfun); > > > +path_range_query::path_range_query (gimple_ranger &ranger, > > > + edge e, > > > + bool resolve) > > > + : m_cache (new ssa_global_cache), > > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > + m_ranger (ranger), > > > + m_resolve (resolve) > > > +{ > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > + auto_vec<basic_block> bbs (2); > > > + bbs.quick_push (e->dest); > > > + bbs.quick_push (e->src); > > > + reset_path (bbs, NULL); > > > } > > > > > > path_range_query::~path_range_query () > > > { > > > delete m_oracle; > > > - if (m_alloced_ranger) > > > - delete m_ranger; > > > BITMAP_FREE (m_has_cache_entry); > > > delete m_cache; > > > } > > > > > > -// Return TRUE if NAME is an exit depenency for the path. > > > +// Return TRUE if NAME is an exit dependency for the path. > > > > > > bool > > > path_range_query::exit_dependency_p (tree name) > > > @@ -153,7 +172,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name) > > > { > > > gcc_checking_assert (defined_outside_path (name)); > > > basic_block entry = entry_bb (); > > > - m_ranger->range_on_entry (r, entry, name); > > > + m_ranger.range_on_entry (r, entry, name); > > > } > > > > > > // Return the range of NAME at the end of the path being analyzed. > > > @@ -211,19 +230,19 @@ path_range_query::unreachable_path_p () > > > return m_undefined_path; > > > } > > > > > > -// Initialize the current path to PATH. The current block is set to > > > -// the entry block to the path. > > > -// > > > -// Note that the blocks are in reverse order, so the exit block is > > > -// path[0]. > > > +// Reset the current path to PATH. > > > > > > void > > > -path_range_query::set_path (const vec<basic_block> &path) > > > +path_range_query::reset_path (const vec<basic_block> &path, > > > + const bitmap_head *dependencies) > > > { > > > gcc_checking_assert (path.length () > 1); > > > m_path = path.copy (); > > > m_pos = m_path.length () - 1; > > > + m_undefined_path = false; > > > bitmap_clear (m_has_cache_entry); > > > + > > > + compute_ranges (dependencies); > > > } > > > > > > bool > > > @@ -248,7 +267,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > > > > > if (at_entry ()) > > > { > > > - if (m_resolve && m_ranger->range_of_expr (r, name, phi)) > > > + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) > > > return; > > > > > > // Try to fold the phi exclusively with global or cached values. > > > @@ -290,7 +309,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > > range_on_path_entry (r, arg); > > > else > > > r.set_varying (TREE_TYPE (name)); > > > - m_ranger->range_on_edge (tmp, e_in, arg); > > > + m_ranger.range_on_edge (tmp, e_in, arg); > > > r.intersect (tmp); > > > return; > > > } > > > @@ -325,7 +344,7 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) > > > } > > > > > > if (bb && POINTER_TYPE_P (TREE_TYPE (name))) > > > - m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); > > > + m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb); > > > > > > if (DEBUG_SOLVER && (bb || !r.varying_p ())) > > > { > > > @@ -442,7 +461,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) > > > p->set_root_oracle (nullptr); > > > } > > > > > > - gori_compute &g = m_ranger->gori (); > > > + gori_compute &g = m_ranger.gori (); > > > bitmap exports = g.exports (bb); > > > EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi) > > > { > > > @@ -496,7 +515,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) > > > else > > > r.set_varying (TREE_TYPE (name)); > > > > > > - if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > > + if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > > set_cache (r, name); > > > } > > > } > > > @@ -516,12 +535,11 @@ path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies) > > > // SSA names used to calculate the final conditional along the path. > > > > > > void > > > -path_range_query::compute_exit_dependencies (bitmap dependencies, > > > - const vec<basic_block> &path) > > > +path_range_query::compute_exit_dependencies (bitmap dependencies) > > > { > > > // Start with the imports from the exit block... > > > - basic_block exit = path[0]; > > > - gori_compute &gori = m_ranger->gori (); > > > + basic_block exit = m_path[0]; > > > + gori_compute &gori = m_ranger.gori (); > > > bitmap_copy (dependencies, gori.imports (exit)); > > > > > > auto_vec<tree> worklist (bitmap_count_bits (dependencies)); > > > @@ -539,7 +557,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > tree name = worklist.pop (); > > > gimple *def_stmt = SSA_NAME_DEF_STMT (name); > > > if (SSA_NAME_IS_DEFAULT_DEF (name) > > > - || !path.contains (gimple_bb (def_stmt))) > > > + || !m_path.contains (gimple_bb (def_stmt))) > > > continue; > > > > > > if (gphi *phi = dyn_cast <gphi *> (def_stmt)) > > > @@ -550,7 +568,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > tree arg = gimple_phi_arg (phi, i)->def; > > > > > > if (TREE_CODE (arg) == SSA_NAME > > > - && path.contains (e->src) > > > + && m_path.contains (e->src) > > > && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg))) > > > worklist.safe_push (arg); > > > } > > > @@ -582,9 +600,9 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > } > > > // Exported booleans along the path, may help conditionals. > > > if (m_resolve) > > > - for (i = 0; i < path.length (); ++i) > > > + for (i = 0; i < m_path.length (); ++i) > > > { > > > - basic_block bb = path[i]; > > > + basic_block bb = m_path[i]; > > > tree name; > > > FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) > > > if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) > > > @@ -600,19 +618,15 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > // calculated from the final conditional in the path. > > > > > > void > > > -path_range_query::compute_ranges (const vec<basic_block> &path, > > > - const bitmap_head *dependencies) > > > +path_range_query::compute_ranges (const bitmap_head *dependencies) > > > { > > > if (DEBUG_SOLVER) > > > fprintf (dump_file, "\n==============================================\n"); > > > > > > - set_path (path); > > > - m_undefined_path = false; > > > - > > > if (dependencies) > > > bitmap_copy (m_exit_dependencies, dependencies); > > > else > > > - compute_exit_dependencies (m_exit_dependencies, m_path); > > > + compute_exit_dependencies (m_exit_dependencies); > > > > > > if (m_resolve) > > > get_path_oracle ()->reset_path (); > > > @@ -620,9 +634,9 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > > if (DEBUG_SOLVER) > > > { > > > fprintf (dump_file, "path_range_query: compute_ranges for path: "); > > > - for (unsigned i = path.length (); i > 0; --i) > > > + for (unsigned i = m_path.length (); i > 0; --i) > > > { > > > - basic_block bb = path[i - 1]; > > > + basic_block bb = m_path[i - 1]; > > > fprintf (dump_file, "%d", bb->index); > > > if (i > 1) > > > fprintf (dump_file, "->"); > > > @@ -650,18 +664,6 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > > } > > > } > > > > > > -// Convenience function to compute ranges along a path consisting of > > > -// E->SRC and E->DEST. > > > - > > > -void > > > -path_range_query::compute_ranges (edge e) > > > -{ > > > - auto_vec<basic_block> bbs (2); > > > - bbs.quick_push (e->dest); > > > - bbs.quick_push (e->src); > > > - compute_ranges (bbs); > > > -} > > > - > > > // A folding aid used to register and query relations along a path. > > > // When queried, it returns relations as they would appear on exit to > > > // the path. > > > @@ -744,7 +746,7 @@ path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) > > > if (m_resolve) > > > { > > > fold_using_range f; > > > - jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); > > > + jt_fur_source src (stmt, this, &m_ranger.gori (), m_path); > > > if (!f.fold_stmt (r, stmt, src)) > > > r.set_varying (type); > > > } > > > @@ -834,7 +836,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) > > > else > > > gcc_unreachable (); > > > > > > - jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); > > > + jt_fur_source src (NULL, this, &m_ranger.gori (), m_path); > > > src.register_outgoing_edges (cond, r, e0, e1); > > > } > > > } > > > diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h > > > index 3cb794e34a9..483fde0d431 100644 > > > --- a/gcc/gimple-range-path.h > > > +++ b/gcc/gimple-range-path.h > > > @@ -32,13 +32,14 @@ along with GCC; see the file COPYING3. If not see > > > class path_range_query : public range_query > > > { > > > public: > > > - path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); > > > + path_range_query (class gimple_ranger &ranger, > > > + const vec<basic_block> &path, > > > + const bitmap_head *dependencies = NULL, > > > + bool resolve = true); > > > + path_range_query (gimple_ranger &ranger, bool resolve = true); > > > + path_range_query (gimple_ranger &ranger, edge e, bool resolve = true); > > > virtual ~path_range_query (); > > > - void compute_ranges (const vec<basic_block> &, > > > - const bitmap_head *dependencies = NULL); > > > - void compute_ranges (edge e); > > > - void compute_exit_dependencies (bitmap dependencies, > > > - const vec<basic_block> &); > > > + void reset_path (const vec<basic_block> &, const bitmap_head *dependencies); > > > bool range_of_expr (vrange &r, tree name, gimple * = NULL) override; > > > bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override; > > > bool unreachable_path_p (); > > > @@ -47,6 +48,8 @@ public: > > > > > > private: > > > bool internal_range_of_expr (vrange &r, tree name, gimple *); > > > + void compute_ranges (const bitmap_head *dependencies); > > > + void compute_exit_dependencies (bitmap_head *dependencies); > > > bool defined_outside_path (tree name); > > > void range_on_path_entry (vrange &r, tree name); > > > path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } > > > @@ -71,7 +74,6 @@ private: > > > bool relations_may_be_invalidated (edge); > > > > > > // Path navigation. > > > - void set_path (const vec<basic_block> &); > > > basic_block entry_bb () { return m_path[m_path.length () - 1]; } > > > basic_block exit_bb () { return m_path[0]; } > > > basic_block curr_bb () { return m_path[m_pos]; } > > > @@ -99,7 +101,7 @@ private: > > > > > > // A ranger used to resolve ranges for SSA names whose values come > > > // from outside the path. > > > - gimple_ranger *m_ranger; > > > + gimple_ranger &m_ranger; > > > > > > // Current path position. > > > unsigned m_pos; > > > @@ -109,10 +111,6 @@ private: > > > > > > // Set if there were any undefined expressions while pre-calculating path. > > > bool m_undefined_path; > > > - > > > - // True if m_ranger was allocated in this class and must be freed at > > > - // destruction. > > > - bool m_alloced_ranger; > > > }; > > > > > > #endif // GCC_TREE_SSA_THREADSOLVER_H > > > diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc > > > index 44dc27b464c..513e0c88254 100644 > > > --- a/gcc/tree-ssa-dom.cc > > > +++ b/gcc/tree-ssa-dom.cc > > > @@ -798,7 +798,7 @@ pass_dominator::execute (function *fun) > > > > > > /* Recursively walk the dominator tree optimizing statements. */ > > > gimple_ranger *ranger = enable_ranger (fun); > > > - path_range_query path_query (/*resolve=*/true, ranger); > > > + path_range_query path_query (*ranger); > > > dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query); > > > dom_jt_state state (const_and_copies, avail_exprs_stack); > > > jump_threader threader (&simplifier, &state); > > > diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc > > > index 3b91a89eaf5..96816b89287 100644 > > > --- a/gcc/tree-ssa-loop-ch.cc > > > +++ b/gcc/tree-ssa-loop-ch.cc > > > @@ -49,7 +49,7 @@ along with GCC; see the file COPYING3. If not see > > > be statically determined. */ > > > > > > static bool > > > -entry_loop_condition_is_static (class loop *l, path_range_query *query) > > > +entry_loop_condition_is_static (class loop *l, gimple_ranger *ranger) > > > { > > > edge e = loop_preheader_edge (l); > > > gcond *last = safe_dyn_cast <gcond *> (last_stmt (e->dest)); > > > @@ -72,8 +72,8 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query) > > > desired_static_value = boolean_true_node; > > > > > > int_range<2> r; > > > - query->compute_ranges (e); > > > - query->range_of_stmt (r, last); > > > + path_range_query query (*ranger, e); > > > + query.range_of_stmt (r, last); > > > return r == int_range<2> (desired_static_value, desired_static_value); > > > } > > > > > > @@ -385,7 +385,7 @@ ch_base::copy_headers (function *fun) > > > auto_vec<std::pair<edge, loop_p> > copied; > > > > > > mark_dfs_back_edges (); > > > - path_range_query *query = new path_range_query; > > > + gimple_ranger *ranger = new gimple_ranger; > > > for (auto loop : loops_list (cfun, 0)) > > > { > > > int initial_limit = param_max_loop_header_insns; > > > @@ -409,7 +409,7 @@ ch_base::copy_headers (function *fun) > > > iteration. */ > > > if (optimize_loop_for_size_p (loop) > > > && !loop->force_vectorize > > > - && !entry_loop_condition_is_static (loop, query)) > > > + && !entry_loop_condition_is_static (loop, ranger)) > > > { > > > if (dump_file && (dump_flags & TDF_DETAILS)) > > > fprintf (dump_file, > > > @@ -422,7 +422,7 @@ ch_base::copy_headers (function *fun) > > > candidates.safe_push (loop); > > > } > > > /* Do not use ranger after we change the IL and not have updated SSA. */ > > > - delete query; > > > + delete ranger; > > > > > > for (auto loop : candidates) > > > { > > > diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc > > > index b886027fccf..22748b9ec08 100644 > > > --- a/gcc/tree-ssa-threadbackward.cc > > > +++ b/gcc/tree-ssa-threadbackward.cc > > > @@ -99,7 +99,6 @@ private: > > > > > > back_threader_registry m_registry; > > > back_threader_profitability m_profit; > > > - path_range_query *m_solver; > > > > > > // Current path being analyzed. > > > auto_vec<basic_block> m_path; > > > @@ -119,6 +118,8 @@ private: > > > // with the ranger. Otherwise, unknown SSA names are assumed to be > > > // VARYING. Setting to true is more precise but slower. > > > function *m_fun; > > > + // Ranger for the path solver. > > > + gimple_ranger *m_ranger; > > > unsigned m_flags; > > > // Set to TRUE for the first of each thread[12] pass or the first of > > > // each threadfull[12] pass. This is used to differentiate between > > > @@ -145,14 +146,19 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) > > > > > > // The path solver needs EDGE_DFS_BACK in resolving mode. > > > if (flags & BT_RESOLVE) > > > - mark_dfs_back_edges (); > > > - m_solver = new path_range_query (flags & BT_RESOLVE); > > > + { > > > + mark_dfs_back_edges (); > > > + > > > + if (flag_checking) > > > + verify_marked_backedges (fun); > > > + } > > > + > > > + m_ranger = new gimple_ranger; > > > } > > > > > > back_threader::~back_threader () > > > { > > > - delete m_solver; > > > - > > > + delete m_ranger; > > > loop_optimizer_finalize (); > > > } > > > > > > @@ -290,8 +296,8 @@ back_threader::find_taken_edge_switch (const vec<basic_block> &path, > > > tree name = gimple_switch_index (sw); > > > int_range_max r; > > > > > > - m_solver->compute_ranges (path, m_imports); > > > - m_solver->range_of_expr (r, name, sw); > > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > > + solver.range_of_expr (r, name, sw); > > > > > > if (r.undefined_p ()) > > > return UNREACHABLE_EDGE; > > > @@ -314,10 +320,10 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path, > > > { > > > int_range_max r; > > > > > > - m_solver->compute_ranges (path, m_imports); > > > - m_solver->range_of_stmt (r, cond); > > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > > + solver.range_of_stmt (r, cond); > > > > > > - if (m_solver->unreachable_path_p ()) > > > + if (solver.unreachable_path_p ()) > > > return UNREACHABLE_EDGE; > > > > > > int_range<2> true_range (boolean_true_node, boolean_true_node); > > > @@ -588,7 +594,6 @@ debug (const vec <basic_block> &path) > > > void > > > back_threader::dump (FILE *out) > > > { > > > - m_solver->dump (out); > > > fprintf (out, "\nCandidates for pre-computation:\n"); > > > fprintf (out, "===================================\n"); > > > > > > diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc > > > index e64e4f209f7..905a98c8c68 100644 > > > --- a/gcc/tree-ssa-threadedge.cc > > > +++ b/gcc/tree-ssa-threadedge.cc > > > @@ -1399,7 +1399,6 @@ jt_state::register_equivs_stmt (gimple *stmt, basic_block bb, > > > > > > // Hybrid threader implementation. > > > > > > - > > > hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r, > > > path_range_query *q) > > > { > > > @@ -1411,7 +1410,12 @@ tree > > > hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > > jt_state *state) > > > { > > > - compute_ranges_from_state (stmt, state); > > > + auto_bitmap dependencies; > > > + auto_vec<basic_block> path; > > > + > > > + state->get_path (path); > > > + compute_exit_dependencies (dependencies, path, stmt); > > > + m_query->reset_path (path, dependencies); > > > > > > if (gimple_code (stmt) == GIMPLE_COND > > > || gimple_code (stmt) == GIMPLE_ASSIGN) > > > @@ -1432,22 +1436,25 @@ hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > > return NULL; > > > } > > > > > > -// Use STATE to generate the list of imports needed for the solver, > > > -// and calculate the ranges along the path. > > > +// Calculate the set of exit dependencies for a path and statement to > > > +// be simplified. This is different than the > > > +// compute_exit_dependencies in the path solver because the forward > > > +// threader asks questions about statements not necessarily in the > > > +// path. Using the default compute_exit_dependencies in the path > > > +// solver gets noticeably less threads. > > > > > > void > > > -hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > > +hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies, > > > + const vec<basic_block> &path, > > > + gimple *stmt) > > > { > > > - auto_bitmap imports; > > > gori_compute &gori = m_ranger->gori (); > > > > > > - state->get_path (m_path); > > > - > > > // Start with the imports to the final conditional. > > > - bitmap_copy (imports, gori.imports (m_path[0])); > > > + bitmap_copy (dependencies, gori.imports (path[0])); > > > > > > // Add any other interesting operands we may have missed. > > > - if (gimple_bb (stmt) != m_path[0]) > > > + if (gimple_bb (stmt) != path[0]) > > > { > > > for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) > > > { > > > @@ -1455,8 +1462,7 @@ hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > > if (op > > > && TREE_CODE (op) == SSA_NAME > > > && Value_Range::supports_type_p (TREE_TYPE (op))) > > > - bitmap_set_bit (imports, SSA_NAME_VERSION (op)); > > > + bitmap_set_bit (dependencies, SSA_NAME_VERSION (op)); > > > } > > > } > > > - m_query->compute_ranges (m_path, imports); > > > } > > > diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h > > > index ca70b33f5ed..790ac2ea538 100644 > > > --- a/gcc/tree-ssa-threadedge.h > > > +++ b/gcc/tree-ssa-threadedge.h > > > @@ -69,11 +69,12 @@ public: > > > tree simplify (gimple *stmt, gimple *, basic_block, jt_state *) override; > > > > > > private: > > > - void compute_ranges_from_state (gimple *stmt, jt_state *); > > > + void compute_exit_dependencies (bitmap dependencies, > > > + const vec<basic_block> &path, > > > + gimple *stmt); > > > > > > gimple_ranger *m_ranger; > > > path_range_query *m_query; > > > - auto_vec<basic_block> m_path; > > > }; > > > > > > // This is the high level threader. The entry point is > > > -- > > > 2.37.1 > > > >
On Thu, Aug 18, 2022 at 1:10 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > On Thu, Aug 18, 2022, 11:34 Richard Biener <richard.guenther@gmail.com> wrote: > > > > On Thu, Aug 18, 2022 at 9:58 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > > > FWIW, here is a rebased version with the latest trunk. > > > > > > There are no regressions, or differences in threading counts, and the > > > performance change is negligible. > > > > + { > > + mark_dfs_back_edges (); > > + > > + if (flag_checking) > > + verify_marked_backedges (fun); > > > > that looks redundant. > > Do you suggest somewhere else, or should we nuke > verify_marked_backedges altogether since that's its only use? Not sure. I'd leave the function around in any case. > > > > Otherwise looks good - it might be possible to get rid of the reset_path use > > as well? > > > That's what I mentioned wrt DOM threading. There's a 14% degradation > from not reusing the path_range_query in the forward threader because > it really abuses the query to try to simplify its statements. So I've > left reset_path for it to use, but we can get rid of it when we nuke > the old threader. Ah, I see. > Aldy > > > Aldy > > > > > Richard. > > > > > Aldy > > > > > > On Wed, Aug 17, 2022 at 1:59 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > > > > > These are a bunch of cleanups inspired by Richi's suggestion of making > > > > path_range_query standalone, instead of having to call > > > > compute_ranges() for each path. > > > > > > > > I've made the ranger need explicit, and moved the responsibility for > > > > its creation to the caller. > > > > > > > > I've also investigated and documented why the forward threader needs its > > > > own compute exit dependencies variant. I can't wait for it to go away > > > > :-/. > > > > > > > > I've also added constructors that take a path and dependencies, and > > > > made compute_ranges() private. Unfortunately, reinstantiating > > > > path_range_query in the forward threader caused a 14% performance > > > > regression in DOM, because the old threader calls it over and over on > > > > the same path to simplify statements (some of which not even in the > > > > IL, but that's old news). > > > > > > > > In the meantime, I've left the ability to reset a path, but this time > > > > appropriately called reset_path(). > > > > > > > > I've moved the verify_marked_backedges call to the threader. Is this > > > > ok? > > > > > > > > Interestingly, comparing the thread counts for the patch yielded more > > > > threads. I narrowed this down to a bug in the path oracle reset code > > > > that's not cleaning things up as expected. I'll fix that before > > > > committing this, but figured I'd post for comments in the meantime. > > > > > > > > Thoughts? > > > > > > > > gcc/ChangeLog: > > > > > > > > * gimple-range-path.cc (path_range_query::path_range_query): Add > > > > various constructors to take a path. > > > > (path_range_query::~path_range_query): Remove m_alloced_ranger. > > > > (path_range_query::range_on_path_entry): Adjust for m_ranger being > > > > a reference. > > > > (path_range_query::set_path): Rename to... > > > > (path_range_query::reset_path): ...this and call compute_ranges. > > > > (path_range_query::ssa_range_in_phi): Adjust for m_ranger > > > > reference. > > > > (path_range_query::range_defined_in_block): Same. > > > > (path_range_query::compute_ranges_in_block): Same. > > > > (path_range_query::adjust_for_non_null_uses): Same. > > > > (path_range_query::compute_exit_dependencies): Use m_path instead > > > > of argument. > > > > (path_range_query::compute_ranges): Remove path argument. > > > > (path_range_query::range_of_stmt): Adjust for m_ranger reference. > > > > (path_range_query::compute_outgoing_relations): Same. > > > > * gimple-range-path.h (class path_range_query): Add various > > > > constructors. > > > > Make compute_ranges and compute_exit_dependencies private. > > > > Rename set_path to reset_path. > > > > Make m_ranger a reference. > > > > Remove m_alloced_ranger. > > > > * tree-ssa-dom.cc (pass_dominator::execute): Adjust constructor to > > > > path_range_query. > > > > * tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Take a > > > > ranger and instantiate a new path_range_query every time. > > > > (ch_base::copy_headers): Pass ranger instead of path_range_query. > > > > * tree-ssa-threadbackward.cc (class back_threader): Remove m_solver. > > > > (back_threader::~back_threader): Remove m_solver. > > > > (back_threader::find_taken_edge_switch): Adjust for m_ranger > > > > reference. > > > > (back_threader::find_taken_edge_cond): Same. > > > > (back_threader::dump): Remove m_solver. > > > > (back_threader::back_threader): Move verify_marked_backedges > > > > here from the path_range_query constructor. > > > > * tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Move > > > > some code from compute_ranges_from_state here. > > > > (hybrid_jt_simplifier::compute_ranges_from_state): Rename... > > > > (hybrid_jt_simplifier::compute_exit_dependencies): ...to this. > > > > * tree-ssa-threadedge.h (class hybrid_jt_simplifier): Rename > > > > compute_ranges_from_state to compute_exit_dependencies. > > > > Remove m_path. > > > > --- > > > > gcc/gimple-range-path.cc | 112 +++++++++++++++++---------------- > > > > gcc/gimple-range-path.h | 22 +++---- > > > > gcc/tree-ssa-dom.cc | 2 +- > > > > gcc/tree-ssa-loop-ch.cc | 12 ++-- > > > > gcc/tree-ssa-threadbackward.cc | 27 ++++---- > > > > gcc/tree-ssa-threadedge.cc | 30 +++++---- > > > > gcc/tree-ssa-threadedge.h | 5 +- > > > > 7 files changed, 111 insertions(+), 99 deletions(-) > > > > > > > > diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc > > > > index c99d77dd340..d37605f4539 100644 > > > > --- a/gcc/gimple-range-path.cc > > > > +++ b/gcc/gimple-range-path.cc > > > > @@ -36,33 +36,52 @@ along with GCC; see the file COPYING3. If not see > > > > // Internal construct to help facilitate debugging of solver. > > > > #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) > > > > > > > > -path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) > > > > +path_range_query::path_range_query (gimple_ranger &ranger, > > > > + const vec<basic_block> &path, > > > > + const bitmap_head *dependencies, > > > > + bool resolve) > > > > : m_cache (new ssa_global_cache), > > > > m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > > - m_resolve (resolve), > > > > - m_alloced_ranger (!ranger) > > > > + m_ranger (ranger), > > > > + m_resolve (resolve) > > > > { > > > > - if (m_alloced_ranger) > > > > - m_ranger = new gimple_ranger; > > > > - else > > > > - m_ranger = ranger; > > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > > + > > > > + reset_path (path, dependencies); > > > > +} > > > > > > > > - m_oracle = new path_oracle (m_ranger->oracle ()); > > > > +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) > > > > + : m_cache (new ssa_global_cache), > > > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > > + m_ranger (ranger), > > > > + m_resolve (resolve) > > > > +{ > > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > > +} > > > > > > > > - if (m_resolve && flag_checking) > > > > - verify_marked_backedges (cfun); > > > > +path_range_query::path_range_query (gimple_ranger &ranger, > > > > + edge e, > > > > + bool resolve) > > > > + : m_cache (new ssa_global_cache), > > > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > > + m_ranger (ranger), > > > > + m_resolve (resolve) > > > > +{ > > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > > + auto_vec<basic_block> bbs (2); > > > > + bbs.quick_push (e->dest); > > > > + bbs.quick_push (e->src); > > > > + reset_path (bbs, NULL); > > > > } > > > > > > > > path_range_query::~path_range_query () > > > > { > > > > delete m_oracle; > > > > - if (m_alloced_ranger) > > > > - delete m_ranger; > > > > BITMAP_FREE (m_has_cache_entry); > > > > delete m_cache; > > > > } > > > > > > > > -// Return TRUE if NAME is an exit depenency for the path. > > > > +// Return TRUE if NAME is an exit dependency for the path. > > > > > > > > bool > > > > path_range_query::exit_dependency_p (tree name) > > > > @@ -153,7 +172,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name) > > > > { > > > > gcc_checking_assert (defined_outside_path (name)); > > > > basic_block entry = entry_bb (); > > > > - m_ranger->range_on_entry (r, entry, name); > > > > + m_ranger.range_on_entry (r, entry, name); > > > > } > > > > > > > > // Return the range of NAME at the end of the path being analyzed. > > > > @@ -211,19 +230,19 @@ path_range_query::unreachable_path_p () > > > > return m_undefined_path; > > > > } > > > > > > > > -// Initialize the current path to PATH. The current block is set to > > > > -// the entry block to the path. > > > > -// > > > > -// Note that the blocks are in reverse order, so the exit block is > > > > -// path[0]. > > > > +// Reset the current path to PATH. > > > > > > > > void > > > > -path_range_query::set_path (const vec<basic_block> &path) > > > > +path_range_query::reset_path (const vec<basic_block> &path, > > > > + const bitmap_head *dependencies) > > > > { > > > > gcc_checking_assert (path.length () > 1); > > > > m_path = path.copy (); > > > > m_pos = m_path.length () - 1; > > > > + m_undefined_path = false; > > > > bitmap_clear (m_has_cache_entry); > > > > + > > > > + compute_ranges (dependencies); > > > > } > > > > > > > > bool > > > > @@ -248,7 +267,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > > > > > > > if (at_entry ()) > > > > { > > > > - if (m_resolve && m_ranger->range_of_expr (r, name, phi)) > > > > + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) > > > > return; > > > > > > > > // Try to fold the phi exclusively with global or cached values. > > > > @@ -290,7 +309,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > > > range_on_path_entry (r, arg); > > > > else > > > > r.set_varying (TREE_TYPE (name)); > > > > - m_ranger->range_on_edge (tmp, e_in, arg); > > > > + m_ranger.range_on_edge (tmp, e_in, arg); > > > > r.intersect (tmp); > > > > return; > > > > } > > > > @@ -325,7 +344,7 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) > > > > } > > > > > > > > if (bb && POINTER_TYPE_P (TREE_TYPE (name))) > > > > - m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); > > > > + m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb); > > > > > > > > if (DEBUG_SOLVER && (bb || !r.varying_p ())) > > > > { > > > > @@ -442,7 +461,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) > > > > p->set_root_oracle (nullptr); > > > > } > > > > > > > > - gori_compute &g = m_ranger->gori (); > > > > + gori_compute &g = m_ranger.gori (); > > > > bitmap exports = g.exports (bb); > > > > EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi) > > > > { > > > > @@ -496,7 +515,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) > > > > else > > > > r.set_varying (TREE_TYPE (name)); > > > > > > > > - if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > > > + if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > > > set_cache (r, name); > > > > } > > > > } > > > > @@ -516,12 +535,11 @@ path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies) > > > > // SSA names used to calculate the final conditional along the path. > > > > > > > > void > > > > -path_range_query::compute_exit_dependencies (bitmap dependencies, > > > > - const vec<basic_block> &path) > > > > +path_range_query::compute_exit_dependencies (bitmap dependencies) > > > > { > > > > // Start with the imports from the exit block... > > > > - basic_block exit = path[0]; > > > > - gori_compute &gori = m_ranger->gori (); > > > > + basic_block exit = m_path[0]; > > > > + gori_compute &gori = m_ranger.gori (); > > > > bitmap_copy (dependencies, gori.imports (exit)); > > > > > > > > auto_vec<tree> worklist (bitmap_count_bits (dependencies)); > > > > @@ -539,7 +557,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > > tree name = worklist.pop (); > > > > gimple *def_stmt = SSA_NAME_DEF_STMT (name); > > > > if (SSA_NAME_IS_DEFAULT_DEF (name) > > > > - || !path.contains (gimple_bb (def_stmt))) > > > > + || !m_path.contains (gimple_bb (def_stmt))) > > > > continue; > > > > > > > > if (gphi *phi = dyn_cast <gphi *> (def_stmt)) > > > > @@ -550,7 +568,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > > tree arg = gimple_phi_arg (phi, i)->def; > > > > > > > > if (TREE_CODE (arg) == SSA_NAME > > > > - && path.contains (e->src) > > > > + && m_path.contains (e->src) > > > > && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg))) > > > > worklist.safe_push (arg); > > > > } > > > > @@ -582,9 +600,9 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > > } > > > > // Exported booleans along the path, may help conditionals. > > > > if (m_resolve) > > > > - for (i = 0; i < path.length (); ++i) > > > > + for (i = 0; i < m_path.length (); ++i) > > > > { > > > > - basic_block bb = path[i]; > > > > + basic_block bb = m_path[i]; > > > > tree name; > > > > FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) > > > > if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) > > > > @@ -600,19 +618,15 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > > // calculated from the final conditional in the path. > > > > > > > > void > > > > -path_range_query::compute_ranges (const vec<basic_block> &path, > > > > - const bitmap_head *dependencies) > > > > +path_range_query::compute_ranges (const bitmap_head *dependencies) > > > > { > > > > if (DEBUG_SOLVER) > > > > fprintf (dump_file, "\n==============================================\n"); > > > > > > > > - set_path (path); > > > > - m_undefined_path = false; > > > > - > > > > if (dependencies) > > > > bitmap_copy (m_exit_dependencies, dependencies); > > > > else > > > > - compute_exit_dependencies (m_exit_dependencies, m_path); > > > > + compute_exit_dependencies (m_exit_dependencies); > > > > > > > > if (m_resolve) > > > > get_path_oracle ()->reset_path (); > > > > @@ -620,9 +634,9 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > > > if (DEBUG_SOLVER) > > > > { > > > > fprintf (dump_file, "path_range_query: compute_ranges for path: "); > > > > - for (unsigned i = path.length (); i > 0; --i) > > > > + for (unsigned i = m_path.length (); i > 0; --i) > > > > { > > > > - basic_block bb = path[i - 1]; > > > > + basic_block bb = m_path[i - 1]; > > > > fprintf (dump_file, "%d", bb->index); > > > > if (i > 1) > > > > fprintf (dump_file, "->"); > > > > @@ -650,18 +664,6 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > > > } > > > > } > > > > > > > > -// Convenience function to compute ranges along a path consisting of > > > > -// E->SRC and E->DEST. > > > > - > > > > -void > > > > -path_range_query::compute_ranges (edge e) > > > > -{ > > > > - auto_vec<basic_block> bbs (2); > > > > - bbs.quick_push (e->dest); > > > > - bbs.quick_push (e->src); > > > > - compute_ranges (bbs); > > > > -} > > > > - > > > > // A folding aid used to register and query relations along a path. > > > > // When queried, it returns relations as they would appear on exit to > > > > // the path. > > > > @@ -744,7 +746,7 @@ path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) > > > > if (m_resolve) > > > > { > > > > fold_using_range f; > > > > - jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); > > > > + jt_fur_source src (stmt, this, &m_ranger.gori (), m_path); > > > > if (!f.fold_stmt (r, stmt, src)) > > > > r.set_varying (type); > > > > } > > > > @@ -834,7 +836,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) > > > > else > > > > gcc_unreachable (); > > > > > > > > - jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); > > > > + jt_fur_source src (NULL, this, &m_ranger.gori (), m_path); > > > > src.register_outgoing_edges (cond, r, e0, e1); > > > > } > > > > } > > > > diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h > > > > index 3cb794e34a9..483fde0d431 100644 > > > > --- a/gcc/gimple-range-path.h > > > > +++ b/gcc/gimple-range-path.h > > > > @@ -32,13 +32,14 @@ along with GCC; see the file COPYING3. If not see > > > > class path_range_query : public range_query > > > > { > > > > public: > > > > - path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); > > > > + path_range_query (class gimple_ranger &ranger, > > > > + const vec<basic_block> &path, > > > > + const bitmap_head *dependencies = NULL, > > > > + bool resolve = true); > > > > + path_range_query (gimple_ranger &ranger, bool resolve = true); > > > > + path_range_query (gimple_ranger &ranger, edge e, bool resolve = true); > > > > virtual ~path_range_query (); > > > > - void compute_ranges (const vec<basic_block> &, > > > > - const bitmap_head *dependencies = NULL); > > > > - void compute_ranges (edge e); > > > > - void compute_exit_dependencies (bitmap dependencies, > > > > - const vec<basic_block> &); > > > > + void reset_path (const vec<basic_block> &, const bitmap_head *dependencies); > > > > bool range_of_expr (vrange &r, tree name, gimple * = NULL) override; > > > > bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override; > > > > bool unreachable_path_p (); > > > > @@ -47,6 +48,8 @@ public: > > > > > > > > private: > > > > bool internal_range_of_expr (vrange &r, tree name, gimple *); > > > > + void compute_ranges (const bitmap_head *dependencies); > > > > + void compute_exit_dependencies (bitmap_head *dependencies); > > > > bool defined_outside_path (tree name); > > > > void range_on_path_entry (vrange &r, tree name); > > > > path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } > > > > @@ -71,7 +74,6 @@ private: > > > > bool relations_may_be_invalidated (edge); > > > > > > > > // Path navigation. > > > > - void set_path (const vec<basic_block> &); > > > > basic_block entry_bb () { return m_path[m_path.length () - 1]; } > > > > basic_block exit_bb () { return m_path[0]; } > > > > basic_block curr_bb () { return m_path[m_pos]; } > > > > @@ -99,7 +101,7 @@ private: > > > > > > > > // A ranger used to resolve ranges for SSA names whose values come > > > > // from outside the path. > > > > - gimple_ranger *m_ranger; > > > > + gimple_ranger &m_ranger; > > > > > > > > // Current path position. > > > > unsigned m_pos; > > > > @@ -109,10 +111,6 @@ private: > > > > > > > > // Set if there were any undefined expressions while pre-calculating path. > > > > bool m_undefined_path; > > > > - > > > > - // True if m_ranger was allocated in this class and must be freed at > > > > - // destruction. > > > > - bool m_alloced_ranger; > > > > }; > > > > > > > > #endif // GCC_TREE_SSA_THREADSOLVER_H > > > > diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc > > > > index 44dc27b464c..513e0c88254 100644 > > > > --- a/gcc/tree-ssa-dom.cc > > > > +++ b/gcc/tree-ssa-dom.cc > > > > @@ -798,7 +798,7 @@ pass_dominator::execute (function *fun) > > > > > > > > /* Recursively walk the dominator tree optimizing statements. */ > > > > gimple_ranger *ranger = enable_ranger (fun); > > > > - path_range_query path_query (/*resolve=*/true, ranger); > > > > + path_range_query path_query (*ranger); > > > > dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query); > > > > dom_jt_state state (const_and_copies, avail_exprs_stack); > > > > jump_threader threader (&simplifier, &state); > > > > diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc > > > > index 3b91a89eaf5..96816b89287 100644 > > > > --- a/gcc/tree-ssa-loop-ch.cc > > > > +++ b/gcc/tree-ssa-loop-ch.cc > > > > @@ -49,7 +49,7 @@ along with GCC; see the file COPYING3. If not see > > > > be statically determined. */ > > > > > > > > static bool > > > > -entry_loop_condition_is_static (class loop *l, path_range_query *query) > > > > +entry_loop_condition_is_static (class loop *l, gimple_ranger *ranger) > > > > { > > > > edge e = loop_preheader_edge (l); > > > > gcond *last = safe_dyn_cast <gcond *> (last_stmt (e->dest)); > > > > @@ -72,8 +72,8 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query) > > > > desired_static_value = boolean_true_node; > > > > > > > > int_range<2> r; > > > > - query->compute_ranges (e); > > > > - query->range_of_stmt (r, last); > > > > + path_range_query query (*ranger, e); > > > > + query.range_of_stmt (r, last); > > > > return r == int_range<2> (desired_static_value, desired_static_value); > > > > } > > > > > > > > @@ -385,7 +385,7 @@ ch_base::copy_headers (function *fun) > > > > auto_vec<std::pair<edge, loop_p> > copied; > > > > > > > > mark_dfs_back_edges (); > > > > - path_range_query *query = new path_range_query; > > > > + gimple_ranger *ranger = new gimple_ranger; > > > > for (auto loop : loops_list (cfun, 0)) > > > > { > > > > int initial_limit = param_max_loop_header_insns; > > > > @@ -409,7 +409,7 @@ ch_base::copy_headers (function *fun) > > > > iteration. */ > > > > if (optimize_loop_for_size_p (loop) > > > > && !loop->force_vectorize > > > > - && !entry_loop_condition_is_static (loop, query)) > > > > + && !entry_loop_condition_is_static (loop, ranger)) > > > > { > > > > if (dump_file && (dump_flags & TDF_DETAILS)) > > > > fprintf (dump_file, > > > > @@ -422,7 +422,7 @@ ch_base::copy_headers (function *fun) > > > > candidates.safe_push (loop); > > > > } > > > > /* Do not use ranger after we change the IL and not have updated SSA. */ > > > > - delete query; > > > > + delete ranger; > > > > > > > > for (auto loop : candidates) > > > > { > > > > diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc > > > > index b886027fccf..22748b9ec08 100644 > > > > --- a/gcc/tree-ssa-threadbackward.cc > > > > +++ b/gcc/tree-ssa-threadbackward.cc > > > > @@ -99,7 +99,6 @@ private: > > > > > > > > back_threader_registry m_registry; > > > > back_threader_profitability m_profit; > > > > - path_range_query *m_solver; > > > > > > > > // Current path being analyzed. > > > > auto_vec<basic_block> m_path; > > > > @@ -119,6 +118,8 @@ private: > > > > // with the ranger. Otherwise, unknown SSA names are assumed to be > > > > // VARYING. Setting to true is more precise but slower. > > > > function *m_fun; > > > > + // Ranger for the path solver. > > > > + gimple_ranger *m_ranger; > > > > unsigned m_flags; > > > > // Set to TRUE for the first of each thread[12] pass or the first of > > > > // each threadfull[12] pass. This is used to differentiate between > > > > @@ -145,14 +146,19 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) > > > > > > > > // The path solver needs EDGE_DFS_BACK in resolving mode. > > > > if (flags & BT_RESOLVE) > > > > - mark_dfs_back_edges (); > > > > - m_solver = new path_range_query (flags & BT_RESOLVE); > > > > + { > > > > + mark_dfs_back_edges (); > > > > + > > > > + if (flag_checking) > > > > + verify_marked_backedges (fun); > > > > + } > > > > + > > > > + m_ranger = new gimple_ranger; > > > > } > > > > > > > > back_threader::~back_threader () > > > > { > > > > - delete m_solver; > > > > - > > > > + delete m_ranger; > > > > loop_optimizer_finalize (); > > > > } > > > > > > > > @@ -290,8 +296,8 @@ back_threader::find_taken_edge_switch (const vec<basic_block> &path, > > > > tree name = gimple_switch_index (sw); > > > > int_range_max r; > > > > > > > > - m_solver->compute_ranges (path, m_imports); > > > > - m_solver->range_of_expr (r, name, sw); > > > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > > > + solver.range_of_expr (r, name, sw); > > > > > > > > if (r.undefined_p ()) > > > > return UNREACHABLE_EDGE; > > > > @@ -314,10 +320,10 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path, > > > > { > > > > int_range_max r; > > > > > > > > - m_solver->compute_ranges (path, m_imports); > > > > - m_solver->range_of_stmt (r, cond); > > > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > > > + solver.range_of_stmt (r, cond); > > > > > > > > - if (m_solver->unreachable_path_p ()) > > > > + if (solver.unreachable_path_p ()) > > > > return UNREACHABLE_EDGE; > > > > > > > > int_range<2> true_range (boolean_true_node, boolean_true_node); > > > > @@ -588,7 +594,6 @@ debug (const vec <basic_block> &path) > > > > void > > > > back_threader::dump (FILE *out) > > > > { > > > > - m_solver->dump (out); > > > > fprintf (out, "\nCandidates for pre-computation:\n"); > > > > fprintf (out, "===================================\n"); > > > > > > > > diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc > > > > index e64e4f209f7..905a98c8c68 100644 > > > > --- a/gcc/tree-ssa-threadedge.cc > > > > +++ b/gcc/tree-ssa-threadedge.cc > > > > @@ -1399,7 +1399,6 @@ jt_state::register_equivs_stmt (gimple *stmt, basic_block bb, > > > > > > > > // Hybrid threader implementation. > > > > > > > > - > > > > hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r, > > > > path_range_query *q) > > > > { > > > > @@ -1411,7 +1410,12 @@ tree > > > > hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > > > jt_state *state) > > > > { > > > > - compute_ranges_from_state (stmt, state); > > > > + auto_bitmap dependencies; > > > > + auto_vec<basic_block> path; > > > > + > > > > + state->get_path (path); > > > > + compute_exit_dependencies (dependencies, path, stmt); > > > > + m_query->reset_path (path, dependencies); > > > > > > > > if (gimple_code (stmt) == GIMPLE_COND > > > > || gimple_code (stmt) == GIMPLE_ASSIGN) > > > > @@ -1432,22 +1436,25 @@ hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > > > return NULL; > > > > } > > > > > > > > -// Use STATE to generate the list of imports needed for the solver, > > > > -// and calculate the ranges along the path. > > > > +// Calculate the set of exit dependencies for a path and statement to > > > > +// be simplified. This is different than the > > > > +// compute_exit_dependencies in the path solver because the forward > > > > +// threader asks questions about statements not necessarily in the > > > > +// path. Using the default compute_exit_dependencies in the path > > > > +// solver gets noticeably less threads. > > > > > > > > void > > > > -hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > > > +hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies, > > > > + const vec<basic_block> &path, > > > > + gimple *stmt) > > > > { > > > > - auto_bitmap imports; > > > > gori_compute &gori = m_ranger->gori (); > > > > > > > > - state->get_path (m_path); > > > > - > > > > // Start with the imports to the final conditional. > > > > - bitmap_copy (imports, gori.imports (m_path[0])); > > > > + bitmap_copy (dependencies, gori.imports (path[0])); > > > > > > > > // Add any other interesting operands we may have missed. > > > > - if (gimple_bb (stmt) != m_path[0]) > > > > + if (gimple_bb (stmt) != path[0]) > > > > { > > > > for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) > > > > { > > > > @@ -1455,8 +1462,7 @@ hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > > > if (op > > > > && TREE_CODE (op) == SSA_NAME > > > > && Value_Range::supports_type_p (TREE_TYPE (op))) > > > > - bitmap_set_bit (imports, SSA_NAME_VERSION (op)); > > > > + bitmap_set_bit (dependencies, SSA_NAME_VERSION (op)); > > > > } > > > > } > > > > - m_query->compute_ranges (m_path, imports); > > > > } > > > > diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h > > > > index ca70b33f5ed..790ac2ea538 100644 > > > > --- a/gcc/tree-ssa-threadedge.h > > > > +++ b/gcc/tree-ssa-threadedge.h > > > > @@ -69,11 +69,12 @@ public: > > > > tree simplify (gimple *stmt, gimple *, basic_block, jt_state *) override; > > > > > > > > private: > > > > - void compute_ranges_from_state (gimple *stmt, jt_state *); > > > > + void compute_exit_dependencies (bitmap dependencies, > > > > + const vec<basic_block> &path, > > > > + gimple *stmt); > > > > > > > > gimple_ranger *m_ranger; > > > > path_range_query *m_query; > > > > - auto_vec<basic_block> m_path; > > > > }; > > > > > > > > // This is the high level threader. The entry point is > > > > -- > > > > 2.37.1 > > > > > > >
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index c99d77dd340..d37605f4539 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -36,33 +36,52 @@ along with GCC; see the file COPYING3. If not see // Internal construct to help facilitate debugging of solver. #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) -path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) +path_range_query::path_range_query (gimple_ranger &ranger, + const vec<basic_block> &path, + const bitmap_head *dependencies, + bool resolve) : m_cache (new ssa_global_cache), m_has_cache_entry (BITMAP_ALLOC (NULL)), - m_resolve (resolve), - m_alloced_ranger (!ranger) + m_ranger (ranger), + m_resolve (resolve) { - if (m_alloced_ranger) - m_ranger = new gimple_ranger; - else - m_ranger = ranger; + m_oracle = new path_oracle (m_ranger.oracle ()); + + reset_path (path, dependencies); +} - m_oracle = new path_oracle (m_ranger->oracle ()); +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) + : m_cache (new ssa_global_cache), + m_has_cache_entry (BITMAP_ALLOC (NULL)), + m_ranger (ranger), + m_resolve (resolve) +{ + m_oracle = new path_oracle (m_ranger.oracle ()); +} - if (m_resolve && flag_checking) - verify_marked_backedges (cfun); +path_range_query::path_range_query (gimple_ranger &ranger, + edge e, + bool resolve) + : m_cache (new ssa_global_cache), + m_has_cache_entry (BITMAP_ALLOC (NULL)), + m_ranger (ranger), + m_resolve (resolve) +{ + m_oracle = new path_oracle (m_ranger.oracle ()); + auto_vec<basic_block> bbs (2); + bbs.quick_push (e->dest); + bbs.quick_push (e->src); + reset_path (bbs, NULL); } path_range_query::~path_range_query () { delete m_oracle; - if (m_alloced_ranger) - delete m_ranger; BITMAP_FREE (m_has_cache_entry); delete m_cache; } -// Return TRUE if NAME is an exit depenency for the path. +// Return TRUE if NAME is an exit dependency for the path. bool path_range_query::exit_dependency_p (tree name) @@ -153,7 +172,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name) { gcc_checking_assert (defined_outside_path (name)); basic_block entry = entry_bb (); - m_ranger->range_on_entry (r, entry, name); + m_ranger.range_on_entry (r, entry, name); } // Return the range of NAME at the end of the path being analyzed. @@ -211,19 +230,19 @@ path_range_query::unreachable_path_p () return m_undefined_path; } -// Initialize the current path to PATH. The current block is set to -// the entry block to the path. -// -// Note that the blocks are in reverse order, so the exit block is -// path[0]. +// Reset the current path to PATH. void -path_range_query::set_path (const vec<basic_block> &path) +path_range_query::reset_path (const vec<basic_block> &path, + const bitmap_head *dependencies) { gcc_checking_assert (path.length () > 1); m_path = path.copy (); m_pos = m_path.length () - 1; + m_undefined_path = false; bitmap_clear (m_has_cache_entry); + + compute_ranges (dependencies); } bool @@ -248,7 +267,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) if (at_entry ()) { - if (m_resolve && m_ranger->range_of_expr (r, name, phi)) + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) return; // Try to fold the phi exclusively with global or cached values. @@ -290,7 +309,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) range_on_path_entry (r, arg); else r.set_varying (TREE_TYPE (name)); - m_ranger->range_on_edge (tmp, e_in, arg); + m_ranger.range_on_edge (tmp, e_in, arg); r.intersect (tmp); return; } @@ -325,7 +344,7 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) } if (bb && POINTER_TYPE_P (TREE_TYPE (name))) - m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); + m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb); if (DEBUG_SOLVER && (bb || !r.varying_p ())) { @@ -442,7 +461,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) p->set_root_oracle (nullptr); } - gori_compute &g = m_ranger->gori (); + gori_compute &g = m_ranger.gori (); bitmap exports = g.exports (bb); EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi) { @@ -496,7 +515,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) else r.set_varying (TREE_TYPE (name)); - if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) + if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) set_cache (r, name); } } @@ -516,12 +535,11 @@ path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies) // SSA names used to calculate the final conditional along the path. void -path_range_query::compute_exit_dependencies (bitmap dependencies, - const vec<basic_block> &path) +path_range_query::compute_exit_dependencies (bitmap dependencies) { // Start with the imports from the exit block... - basic_block exit = path[0]; - gori_compute &gori = m_ranger->gori (); + basic_block exit = m_path[0]; + gori_compute &gori = m_ranger.gori (); bitmap_copy (dependencies, gori.imports (exit)); auto_vec<tree> worklist (bitmap_count_bits (dependencies)); @@ -539,7 +557,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, tree name = worklist.pop (); gimple *def_stmt = SSA_NAME_DEF_STMT (name); if (SSA_NAME_IS_DEFAULT_DEF (name) - || !path.contains (gimple_bb (def_stmt))) + || !m_path.contains (gimple_bb (def_stmt))) continue; if (gphi *phi = dyn_cast <gphi *> (def_stmt)) @@ -550,7 +568,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, tree arg = gimple_phi_arg (phi, i)->def; if (TREE_CODE (arg) == SSA_NAME - && path.contains (e->src) + && m_path.contains (e->src) && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg))) worklist.safe_push (arg); } @@ -582,9 +600,9 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, } // Exported booleans along the path, may help conditionals. if (m_resolve) - for (i = 0; i < path.length (); ++i) + for (i = 0; i < m_path.length (); ++i) { - basic_block bb = path[i]; + basic_block bb = m_path[i]; tree name; FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) @@ -600,19 +618,15 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, // calculated from the final conditional in the path. void -path_range_query::compute_ranges (const vec<basic_block> &path, - const bitmap_head *dependencies) +path_range_query::compute_ranges (const bitmap_head *dependencies) { if (DEBUG_SOLVER) fprintf (dump_file, "\n==============================================\n"); - set_path (path); - m_undefined_path = false; - if (dependencies) bitmap_copy (m_exit_dependencies, dependencies); else - compute_exit_dependencies (m_exit_dependencies, m_path); + compute_exit_dependencies (m_exit_dependencies); if (m_resolve) get_path_oracle ()->reset_path (); @@ -620,9 +634,9 @@ path_range_query::compute_ranges (const vec<basic_block> &path, if (DEBUG_SOLVER) { fprintf (dump_file, "path_range_query: compute_ranges for path: "); - for (unsigned i = path.length (); i > 0; --i) + for (unsigned i = m_path.length (); i > 0; --i) { - basic_block bb = path[i - 1]; + basic_block bb = m_path[i - 1]; fprintf (dump_file, "%d", bb->index); if (i > 1) fprintf (dump_file, "->"); @@ -650,18 +664,6 @@ path_range_query::compute_ranges (const vec<basic_block> &path, } } -// Convenience function to compute ranges along a path consisting of -// E->SRC and E->DEST. - -void -path_range_query::compute_ranges (edge e) -{ - auto_vec<basic_block> bbs (2); - bbs.quick_push (e->dest); - bbs.quick_push (e->src); - compute_ranges (bbs); -} - // A folding aid used to register and query relations along a path. // When queried, it returns relations as they would appear on exit to // the path. @@ -744,7 +746,7 @@ path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) if (m_resolve) { fold_using_range f; - jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); + jt_fur_source src (stmt, this, &m_ranger.gori (), m_path); if (!f.fold_stmt (r, stmt, src)) r.set_varying (type); } @@ -834,7 +836,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) else gcc_unreachable (); - jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); + jt_fur_source src (NULL, this, &m_ranger.gori (), m_path); src.register_outgoing_edges (cond, r, e0, e1); } } diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index 3cb794e34a9..483fde0d431 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -32,13 +32,14 @@ along with GCC; see the file COPYING3. If not see class path_range_query : public range_query { public: - path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); + path_range_query (class gimple_ranger &ranger, + const vec<basic_block> &path, + const bitmap_head *dependencies = NULL, + bool resolve = true); + path_range_query (gimple_ranger &ranger, bool resolve = true); + path_range_query (gimple_ranger &ranger, edge e, bool resolve = true); virtual ~path_range_query (); - void compute_ranges (const vec<basic_block> &, - const bitmap_head *dependencies = NULL); - void compute_ranges (edge e); - void compute_exit_dependencies (bitmap dependencies, - const vec<basic_block> &); + void reset_path (const vec<basic_block> &, const bitmap_head *dependencies); bool range_of_expr (vrange &r, tree name, gimple * = NULL) override; bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override; bool unreachable_path_p (); @@ -47,6 +48,8 @@ public: private: bool internal_range_of_expr (vrange &r, tree name, gimple *); + void compute_ranges (const bitmap_head *dependencies); + void compute_exit_dependencies (bitmap_head *dependencies); bool defined_outside_path (tree name); void range_on_path_entry (vrange &r, tree name); path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } @@ -71,7 +74,6 @@ private: bool relations_may_be_invalidated (edge); // Path navigation. - void set_path (const vec<basic_block> &); basic_block entry_bb () { return m_path[m_path.length () - 1]; } basic_block exit_bb () { return m_path[0]; } basic_block curr_bb () { return m_path[m_pos]; } @@ -99,7 +101,7 @@ private: // A ranger used to resolve ranges for SSA names whose values come // from outside the path. - gimple_ranger *m_ranger; + gimple_ranger &m_ranger; // Current path position. unsigned m_pos; @@ -109,10 +111,6 @@ private: // Set if there were any undefined expressions while pre-calculating path. bool m_undefined_path; - - // True if m_ranger was allocated in this class and must be freed at - // destruction. - bool m_alloced_ranger; }; #endif // GCC_TREE_SSA_THREADSOLVER_H diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc index 44dc27b464c..513e0c88254 100644 --- a/gcc/tree-ssa-dom.cc +++ b/gcc/tree-ssa-dom.cc @@ -798,7 +798,7 @@ pass_dominator::execute (function *fun) /* Recursively walk the dominator tree optimizing statements. */ gimple_ranger *ranger = enable_ranger (fun); - path_range_query path_query (/*resolve=*/true, ranger); + path_range_query path_query (*ranger); dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query); dom_jt_state state (const_and_copies, avail_exprs_stack); jump_threader threader (&simplifier, &state); diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc index 3b91a89eaf5..96816b89287 100644 --- a/gcc/tree-ssa-loop-ch.cc +++ b/gcc/tree-ssa-loop-ch.cc @@ -49,7 +49,7 @@ along with GCC; see the file COPYING3. If not see be statically determined. */ static bool -entry_loop_condition_is_static (class loop *l, path_range_query *query) +entry_loop_condition_is_static (class loop *l, gimple_ranger *ranger) { edge e = loop_preheader_edge (l); gcond *last = safe_dyn_cast <gcond *> (last_stmt (e->dest)); @@ -72,8 +72,8 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query) desired_static_value = boolean_true_node; int_range<2> r; - query->compute_ranges (e); - query->range_of_stmt (r, last); + path_range_query query (*ranger, e); + query.range_of_stmt (r, last); return r == int_range<2> (desired_static_value, desired_static_value); } @@ -385,7 +385,7 @@ ch_base::copy_headers (function *fun) auto_vec<std::pair<edge, loop_p> > copied; mark_dfs_back_edges (); - path_range_query *query = new path_range_query; + gimple_ranger *ranger = new gimple_ranger; for (auto loop : loops_list (cfun, 0)) { int initial_limit = param_max_loop_header_insns; @@ -409,7 +409,7 @@ ch_base::copy_headers (function *fun) iteration. */ if (optimize_loop_for_size_p (loop) && !loop->force_vectorize - && !entry_loop_condition_is_static (loop, query)) + && !entry_loop_condition_is_static (loop, ranger)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, @@ -422,7 +422,7 @@ ch_base::copy_headers (function *fun) candidates.safe_push (loop); } /* Do not use ranger after we change the IL and not have updated SSA. */ - delete query; + delete ranger; for (auto loop : candidates) { diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc index b886027fccf..22748b9ec08 100644 --- a/gcc/tree-ssa-threadbackward.cc +++ b/gcc/tree-ssa-threadbackward.cc @@ -99,7 +99,6 @@ private: back_threader_registry m_registry; back_threader_profitability m_profit; - path_range_query *m_solver; // Current path being analyzed. auto_vec<basic_block> m_path; @@ -119,6 +118,8 @@ private: // with the ranger. Otherwise, unknown SSA names are assumed to be // VARYING. Setting to true is more precise but slower. function *m_fun; + // Ranger for the path solver. + gimple_ranger *m_ranger; unsigned m_flags; // Set to TRUE for the first of each thread[12] pass or the first of // each threadfull[12] pass. This is used to differentiate between @@ -145,14 +146,19 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) // The path solver needs EDGE_DFS_BACK in resolving mode. if (flags & BT_RESOLVE) - mark_dfs_back_edges (); - m_solver = new path_range_query (flags & BT_RESOLVE); + { + mark_dfs_back_edges (); + + if (flag_checking) + verify_marked_backedges (fun); + } + + m_ranger = new gimple_ranger; } back_threader::~back_threader () { - delete m_solver; - + delete m_ranger; loop_optimizer_finalize (); } @@ -290,8 +296,8 @@ back_threader::find_taken_edge_switch (const vec<basic_block> &path, tree name = gimple_switch_index (sw); int_range_max r; - m_solver->compute_ranges (path, m_imports); - m_solver->range_of_expr (r, name, sw); + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); + solver.range_of_expr (r, name, sw); if (r.undefined_p ()) return UNREACHABLE_EDGE; @@ -314,10 +320,10 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path, { int_range_max r; - m_solver->compute_ranges (path, m_imports); - m_solver->range_of_stmt (r, cond); + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); + solver.range_of_stmt (r, cond); - if (m_solver->unreachable_path_p ()) + if (solver.unreachable_path_p ()) return UNREACHABLE_EDGE; int_range<2> true_range (boolean_true_node, boolean_true_node); @@ -588,7 +594,6 @@ debug (const vec <basic_block> &path) void back_threader::dump (FILE *out) { - m_solver->dump (out); fprintf (out, "\nCandidates for pre-computation:\n"); fprintf (out, "===================================\n"); diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc index e64e4f209f7..905a98c8c68 100644 --- a/gcc/tree-ssa-threadedge.cc +++ b/gcc/tree-ssa-threadedge.cc @@ -1399,7 +1399,6 @@ jt_state::register_equivs_stmt (gimple *stmt, basic_block bb, // Hybrid threader implementation. - hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r, path_range_query *q) { @@ -1411,7 +1410,12 @@ tree hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, jt_state *state) { - compute_ranges_from_state (stmt, state); + auto_bitmap dependencies; + auto_vec<basic_block> path; + + state->get_path (path); + compute_exit_dependencies (dependencies, path, stmt); + m_query->reset_path (path, dependencies); if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_ASSIGN) @@ -1432,22 +1436,25 @@ hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, return NULL; } -// Use STATE to generate the list of imports needed for the solver, -// and calculate the ranges along the path. +// Calculate the set of exit dependencies for a path and statement to +// be simplified. This is different than the +// compute_exit_dependencies in the path solver because the forward +// threader asks questions about statements not necessarily in the +// path. Using the default compute_exit_dependencies in the path +// solver gets noticeably less threads. void -hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) +hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies, + const vec<basic_block> &path, + gimple *stmt) { - auto_bitmap imports; gori_compute &gori = m_ranger->gori (); - state->get_path (m_path); - // Start with the imports to the final conditional. - bitmap_copy (imports, gori.imports (m_path[0])); + bitmap_copy (dependencies, gori.imports (path[0])); // Add any other interesting operands we may have missed. - if (gimple_bb (stmt) != m_path[0]) + if (gimple_bb (stmt) != path[0]) { for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) { @@ -1455,8 +1462,7 @@ hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) if (op && TREE_CODE (op) == SSA_NAME && Value_Range::supports_type_p (TREE_TYPE (op))) - bitmap_set_bit (imports, SSA_NAME_VERSION (op)); + bitmap_set_bit (dependencies, SSA_NAME_VERSION (op)); } } - m_query->compute_ranges (m_path, imports); } diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h index ca70b33f5ed..790ac2ea538 100644 --- a/gcc/tree-ssa-threadedge.h +++ b/gcc/tree-ssa-threadedge.h @@ -69,11 +69,12 @@ public: tree simplify (gimple *stmt, gimple *, basic_block, jt_state *) override; private: - void compute_ranges_from_state (gimple *stmt, jt_state *); + void compute_exit_dependencies (bitmap dependencies, + const vec<basic_block> &path, + gimple *stmt); gimple_ranger *m_ranger; path_range_query *m_query; - auto_vec<basic_block> m_path; }; // This is the high level threader. The entry point is