Re: [PATCH] Make path_range_query standalone and add reset_path.

[Aldy Hernandez <aldyh@redhat.com>]

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
> > >
>