Avoid further recomputations in path_range_query once path is finalized.

  [Richi, I'm trying to make things more obvious for others working for the
cose base.  What do you think?]

This makes a few things explicit to avoid misuse.  First, we add a
flag to differentiate between a path whose depdenency ranges are being
computed, and a path that is finalized and no further calculations
should be done.  I've also enhanced the comments to document what
queries are supported.  Finally, I added some asserts to make sure
range_of_expr is only used on the final conditional once the path has
been finalized.

Unfortunately, the forward threader builds dummy statements it passes
to the path solver.  Most of these don't have a BB associated with
them.  I've cleared the BB field for the one that still had one, to
make the asserts above work.

No difference in thread counts over my cc1 .ii files.

gcc/ChangeLog:

	* gimple-range-path.cc (path_range_query::path_range_query):
	Initialized m_path_finalized.
	(path_range_query::internal_range_of_expr): Avoid further
	recomputations once path is finalized.
	Take basic_block instead of stmt as argument.
	(path_range_query::range_of_expr): Document.  Add asserts.
	(path_range_query::compute_ranges): Set m_path_finalized.
	* gimple-range-path.h (path_range_query::internal_range_of_expr):
	Replace statement argument with basic block.
	(class path_range_query): Add m_path_finalized.
	* tree-ssa-threadedge.cc
	(jump_threader::simplify_control_stmt_condition): Clear BB field
	in dummy_switch.
---
 gcc/gimple-range-path.cc   | 50 ++++++++++++++++++++++++++++++++++----
 gcc/gimple-range-path.h    |  7 +++++-
 gcc/tree-ssa-threadedge.cc |  1 +
 3 files changed, 52 insertions(+), 6 deletions(-)
  

On Tue, Aug 16, 2022 at 3:59 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> [Richi, I'm trying to make things more obvious for others working for the
> cose base.  What do you think?]
>
> This makes a few things explicit to avoid misuse.  First, we add a
> flag to differentiate between a path whose depdenency ranges are being
> computed, and a path that is finalized and no further calculations
> should be done.  I've also enhanced the comments to document what
> queries are supported.  Finally, I added some asserts to make sure
> range_of_expr is only used on the final conditional once the path has
> been finalized.
>
> Unfortunately, the forward threader builds dummy statements it passes
> to the path solver.  Most of these don't have a BB associated with
> them.  I've cleared the BB field for the one that still had one, to
> make the asserts above work.
>
> No difference in thread counts over my cc1 .ii files.
>
> gcc/ChangeLog:
>
>         * gimple-range-path.cc (path_range_query::path_range_query):
>         Initialized m_path_finalized.
>         (path_range_query::internal_range_of_expr): Avoid further
>         recomputations once path is finalized.
>         Take basic_block instead of stmt as argument.
>         (path_range_query::range_of_expr): Document.  Add asserts.
>         (path_range_query::compute_ranges): Set m_path_finalized.
>         * gimple-range-path.h (path_range_query::internal_range_of_expr):
>         Replace statement argument with basic block.
>         (class path_range_query): Add m_path_finalized.
>         * tree-ssa-threadedge.cc
>         (jump_threader::simplify_control_stmt_condition): Clear BB field
>         in dummy_switch.
> ---
>  gcc/gimple-range-path.cc   | 50 ++++++++++++++++++++++++++++++++++----
>  gcc/gimple-range-path.h    |  7 +++++-
>  gcc/tree-ssa-threadedge.cc |  1 +
>  3 files changed, 52 insertions(+), 6 deletions(-)
>
> diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
> index c99d77dd340..a8412dd090b 100644
> --- a/gcc/gimple-range-path.cc
> +++ b/gcc/gimple-range-path.cc
> @@ -40,7 +40,8 @@ path_range_query::path_range_query (bool resolve, gimple_ranger *ranger)
>    : m_cache (new ssa_global_cache),
>      m_has_cache_entry (BITMAP_ALLOC (NULL)),
>      m_resolve (resolve),
> -    m_alloced_ranger (!ranger)
> +    m_alloced_ranger (!ranger),
> +    m_path_finalized (false)
>  {
>    if (m_alloced_ranger)
>      m_ranger = new gimple_ranger;
> @@ -159,7 +160,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name)
>  // Return the range of NAME at the end of the path being analyzed.
>
>  bool
> -path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
> +path_range_query::internal_range_of_expr (vrange &r, tree name, basic_block bb)
>  {
>    if (!r.supports_type_p (TREE_TYPE (name)))
>      return false;
> @@ -174,8 +175,16 @@ path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
>        return true;
>      }
>
> -  if (stmt
> -      && range_defined_in_block (r, name, gimple_bb (stmt)))
> +  // Avoid further recomputations once the path has been finalized.
> +  if (m_path_finalized)
> +    {
> +      gimple_range_global (r, name);

I suppose we can't assert here instead?

> +      return true;
> +    }
> +
> +  // We're being called as part of the calculation of ranges for exit
> +  // dependencies.  Set the cache as we traverse the path top-down.
> +  if (bb && range_defined_in_block (r, name, bb))
>      {
>        if (TREE_CODE (name) == SSA_NAME)
>         {
> @@ -192,10 +201,37 @@ path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
>    return true;
>  }
>
> +// This, as well as range_of_stmt, are the main entry points for
> +// making queries about a path.
> +//
> +// Once the ranges for the exit dependencies have been pre-calculated,
> +// the path is considered finalized, and the only valid query is
> +// asking the range of a NAME at the end of the path.
> +//
> +// Note that this method can also be called internally before the path
> +// is finalized, as part of the path traversal pre-calculating the
> +// ranges for exit dependencies.  In this case, it may be called on
> +// statements that are not the final conditional as described above.
> +
>  bool
>  path_range_query::range_of_expr (vrange &r, tree name, gimple *stmt)
>  {
> -  if (internal_range_of_expr (r, name, stmt))
> +  basic_block bb = stmt ? gimple_bb (stmt) : NULL;
> +
> +  // Once a path is finalized, the only valid queries are of the final
> +  // statement in the exit block.

why?  shouldn't we support queries for all dependent ranges (what
the user specified as imports argument to compute_ranges)?

If we want to restrict things this way shouldn't we simply not expose
this function but instead just path_range_query::range_of_exit,
or even what the threader uses as find_taken_edge?

The loop header copying case would also work with this,
it's interested in the known outgoing edge of the path.

> +  if (flag_checking && m_path_finalized && stmt)
> +    {
> +      // The forward threader may query dummy statements without a
> +      // basic block.
> +      if (bb)
> +       {
> +         gcc_assert (stmt == last_stmt (bb));
> +         gcc_assert (bb == exit_bb ());
> +       }
> +    }
> +
> +  if (internal_range_of_expr (r, name, bb))
>      {
>        if (r.undefined_p ())
>         m_undefined_path = true;
> @@ -608,6 +644,7 @@ path_range_query::compute_ranges (const vec<basic_block> &path,
>
>    set_path (path);
>    m_undefined_path = false;
> +  m_path_finalized = false;
>
>    if (dependencies)
>      bitmap_copy (m_exit_dependencies, dependencies);
> @@ -642,6 +679,7 @@ path_range_query::compute_ranges (const vec<basic_block> &path,
>
>        move_next ();
>      }
> +  m_path_finalized = true;
>
>    if (DEBUG_SOLVER)
>      {
> @@ -730,6 +768,8 @@ jt_fur_source::query_relation (tree op1, tree op2)
>  }
>
>  // Return the range of STMT at the end of the path being analyzed.
> +//
> +// See notes in range_of_expr as to what are considered valid queries.
>
>  bool
>  path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree)
> diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
> index 3cb794e34a9..61a7d0f656e 100644
> --- a/gcc/gimple-range-path.h
> +++ b/gcc/gimple-range-path.h
> @@ -46,7 +46,7 @@ public:
>    void debug ();
>
>  private:
> -  bool internal_range_of_expr (vrange &r, tree name, gimple *);
> +  bool internal_range_of_expr (vrange &r, tree name, basic_block);
>    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; }
> @@ -113,6 +113,11 @@ private:
>    // True if m_ranger was allocated in this class and must be freed at
>    // destruction.
>    bool m_alloced_ranger;
> +
> +// Once the ranges for the exit dependencies have been pre-calculated,
> +// the path is considered finalized and this is set to TRUE.
> +// Otherwise, the path is being analyzed.
> +  bool m_path_finalized;
>  };
>
>  #endif // GCC_TREE_SSA_THREADSOLVER_H
> diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc
> index e64e4f209f7..213796c10cc 100644
> --- a/gcc/tree-ssa-threadedge.cc
> +++ b/gcc/tree-ssa-threadedge.cc
> @@ -451,6 +451,7 @@ jump_threader::simplify_control_stmt_condition (edge e, gimple *stmt)
>                  possible, the simplified value will be a CASE_LABEL_EXPR of
>                  the label that is proven to be taken.  */
>               gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
> +             gimple_set_bb (dummy_switch, NULL);

I think it's not wrong to say the stmt is in the block though

>               gimple_switch_set_index (dummy_switch, cached_lhs);
>               cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src,
>                                                    m_state);
> --
> 2.37.1
>
  

On Tue, Aug 16, 2022 at 4:12 PM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Tue, Aug 16, 2022 at 3:59 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > [Richi, I'm trying to make things more obvious for others working for the
> > cose base.  What do you think?]
> >
> > This makes a few things explicit to avoid misuse.  First, we add a
> > flag to differentiate between a path whose depdenency ranges are being
> > computed, and a path that is finalized and no further calculations
> > should be done.  I've also enhanced the comments to document what
> > queries are supported.  Finally, I added some asserts to make sure
> > range_of_expr is only used on the final conditional once the path has
> > been finalized.
> >
> > Unfortunately, the forward threader builds dummy statements it passes
> > to the path solver.  Most of these don't have a BB associated with
> > them.  I've cleared the BB field for the one that still had one, to
> > make the asserts above work.
> >
> > No difference in thread counts over my cc1 .ii files.
> >
> > gcc/ChangeLog:
> >
> >         * gimple-range-path.cc (path_range_query::path_range_query):
> >         Initialized m_path_finalized.
> >         (path_range_query::internal_range_of_expr): Avoid further
> >         recomputations once path is finalized.
> >         Take basic_block instead of stmt as argument.
> >         (path_range_query::range_of_expr): Document.  Add asserts.
> >         (path_range_query::compute_ranges): Set m_path_finalized.
> >         * gimple-range-path.h (path_range_query::internal_range_of_expr):
> >         Replace statement argument with basic block.
> >         (class path_range_query): Add m_path_finalized.
> >         * tree-ssa-threadedge.cc
> >         (jump_threader::simplify_control_stmt_condition): Clear BB field
> >         in dummy_switch.
> > ---
> >  gcc/gimple-range-path.cc   | 50 ++++++++++++++++++++++++++++++++++----
> >  gcc/gimple-range-path.h    |  7 +++++-
> >  gcc/tree-ssa-threadedge.cc |  1 +
> >  3 files changed, 52 insertions(+), 6 deletions(-)
> >
> > diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
> > index c99d77dd340..a8412dd090b 100644
> > --- a/gcc/gimple-range-path.cc
> > +++ b/gcc/gimple-range-path.cc
> > @@ -40,7 +40,8 @@ path_range_query::path_range_query (bool resolve, gimple_ranger *ranger)
> >    : m_cache (new ssa_global_cache),
> >      m_has_cache_entry (BITMAP_ALLOC (NULL)),
> >      m_resolve (resolve),
> > -    m_alloced_ranger (!ranger)
> > +    m_alloced_ranger (!ranger),
> > +    m_path_finalized (false)
> >  {
> >    if (m_alloced_ranger)
> >      m_ranger = new gimple_ranger;
> > @@ -159,7 +160,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name)
> >  // Return the range of NAME at the end of the path being analyzed.
> >
> >  bool
> > -path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
> > +path_range_query::internal_range_of_expr (vrange &r, tree name, basic_block bb)
> >  {
> >    if (!r.supports_type_p (TREE_TYPE (name)))
> >      return false;
> > @@ -174,8 +175,16 @@ path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
> >        return true;
> >      }
> >
> > -  if (stmt
> > -      && range_defined_in_block (r, name, gimple_bb (stmt)))
> > +  // Avoid further recomputations once the path has been finalized.
> > +  if (m_path_finalized)
> > +    {
> > +      gimple_range_global (r, name);
>
> I suppose we can't assert here instead?
>
> > +      return true;
> > +    }
> > +
> > +  // We're being called as part of the calculation of ranges for exit
> > +  // dependencies.  Set the cache as we traverse the path top-down.
> > +  if (bb && range_defined_in_block (r, name, bb))
> >      {
> >        if (TREE_CODE (name) == SSA_NAME)
> >         {
> > @@ -192,10 +201,37 @@ path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
> >    return true;
> >  }
> >
> > +// This, as well as range_of_stmt, are the main entry points for
> > +// making queries about a path.
> > +//
> > +// Once the ranges for the exit dependencies have been pre-calculated,
> > +// the path is considered finalized, and the only valid query is
> > +// asking the range of a NAME at the end of the path.
> > +//
> > +// Note that this method can also be called internally before the path
> > +// is finalized, as part of the path traversal pre-calculating the
> > +// ranges for exit dependencies.  In this case, it may be called on
> > +// statements that are not the final conditional as described above.
> > +
> >  bool
> >  path_range_query::range_of_expr (vrange &r, tree name, gimple *stmt)
> >  {
> > -  if (internal_range_of_expr (r, name, stmt))
> > +  basic_block bb = stmt ? gimple_bb (stmt) : NULL;
> > +
> > +  // Once a path is finalized, the only valid queries are of the final
> > +  // statement in the exit block.
>
> why?  shouldn't we support queries for all dependent ranges (what
> the user specified as imports argument to compute_ranges)?

Yes, we allow queries of all dependent ranges, but as viewed from the
exit from the path.

>
> If we want to restrict things this way shouldn't we simply not expose
> this function but instead just path_range_query::range_of_exit,
> or even what the threader uses as find_taken_edge?

Hmm, that's a very good point.  For that matter, the original
implementation just had a range_of_exit public method.  It evolved to
the current version, because having it behave like a range_query has
other benefits.  For example, I thought that you could pass the path
query to things like simplify_using_ranges, to simplify a statement
given a path.  In reality, that hasn't happened.

So lemme put this aside for now, while I think and experiment a little.

Thanks for the feedback.
Aldy

>
> The loop header copying case would also work with this,
> it's interested in the known outgoing edge of the path.
>
> > +  if (flag_checking && m_path_finalized && stmt)
> > +    {
> > +      // The forward threader may query dummy statements without a
> > +      // basic block.
> > +      if (bb)
> > +       {
> > +         gcc_assert (stmt == last_stmt (bb));
> > +         gcc_assert (bb == exit_bb ());
> > +       }
> > +    }
> > +
> > +  if (internal_range_of_expr (r, name, bb))
> >      {
> >        if (r.undefined_p ())
> >         m_undefined_path = true;
> > @@ -608,6 +644,7 @@ path_range_query::compute_ranges (const vec<basic_block> &path,
> >
> >    set_path (path);
> >    m_undefined_path = false;
> > +  m_path_finalized = false;
> >
> >    if (dependencies)
> >      bitmap_copy (m_exit_dependencies, dependencies);
> > @@ -642,6 +679,7 @@ path_range_query::compute_ranges (const vec<basic_block> &path,
> >
> >        move_next ();
> >      }
> > +  m_path_finalized = true;
> >
> >    if (DEBUG_SOLVER)
> >      {
> > @@ -730,6 +768,8 @@ jt_fur_source::query_relation (tree op1, tree op2)
> >  }
> >
> >  // Return the range of STMT at the end of the path being analyzed.
> > +//
> > +// See notes in range_of_expr as to what are considered valid queries.
> >
> >  bool
> >  path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree)
> > diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
> > index 3cb794e34a9..61a7d0f656e 100644
> > --- a/gcc/gimple-range-path.h
> > +++ b/gcc/gimple-range-path.h
> > @@ -46,7 +46,7 @@ public:
> >    void debug ();
> >
> >  private:
> > -  bool internal_range_of_expr (vrange &r, tree name, gimple *);
> > +  bool internal_range_of_expr (vrange &r, tree name, basic_block);
> >    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; }
> > @@ -113,6 +113,11 @@ private:
> >    // True if m_ranger was allocated in this class and must be freed at
> >    // destruction.
> >    bool m_alloced_ranger;
> > +
> > +// Once the ranges for the exit dependencies have been pre-calculated,
> > +// the path is considered finalized and this is set to TRUE.
> > +// Otherwise, the path is being analyzed.
> > +  bool m_path_finalized;
> >  };
> >
> >  #endif // GCC_TREE_SSA_THREADSOLVER_H
> > diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc
> > index e64e4f209f7..213796c10cc 100644
> > --- a/gcc/tree-ssa-threadedge.cc
> > +++ b/gcc/tree-ssa-threadedge.cc
> > @@ -451,6 +451,7 @@ jump_threader::simplify_control_stmt_condition (edge e, gimple *stmt)
> >                  possible, the simplified value will be a CASE_LABEL_EXPR of
> >                  the label that is proven to be taken.  */
> >               gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
> > +             gimple_set_bb (dummy_switch, NULL);
>
> I think it's not wrong to say the stmt is in the block though
>
> >               gimple_switch_set_index (dummy_switch, cached_lhs);
> >               cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src,
> >                                                    m_state);
> > --
> > 2.37.1
> >
>