Re: [PATCH] Fix path query compute_imports for external path

[Aldy Hernandez <aldyh@redhat.com>]

Looks good to me.

Thanks.
Aldy

On Wed, Aug 10, 2022 at 3:01 PM Richard Biener <rguenther@suse.de> wrote:
>
> The following fixes the use of compute_imports from the backwards
> threader which ends up accessing stale m_path from a previous
> threading attempt.  The fix is to pass in the path explicitely
> (and not the exit), and initializing it with the exit around this
> call from the backwards threader.  That unfortunately exposed that
> we rely on this broken behavior as the new testcase shows.  The
> missed threading can be restored by registering all relations
> from conditions on the path during solving, for the testcase the
> particular important case is for relations provided by the path
> entry conditional.
>
> I've verified that the GORI query for imported ranges on edges
> is not restricted this way.
>
> This regresses the new ssa-thread-19.c testcase which is exactly
> a case for the other patch re-doing how we compute imports since
> this misses imports for defs that are not on the dominating path
> from the exit.
>
> That's one of the cases this regresses (it also progresses a few
> due to more or the correct relations added).  Overall it
> reduces the number of threads from 98649 to 98620 on my set of
> cc1files.  I think it's a reasonable intermediate step to find
> a stable, less random ground to compare stats to.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> OK?
>
> Thanks,
> Richard.
>
>         * gimple-range-path.h (path_range_query::compute_imports):
>         Take path as argument, not the exit block.
>         * gimple-range-path.cc (path_range_query::compute_imports):
>         Likewise, and adjust, avoiding possibly stale m_path.
>         (path_range_query::compute_outgoing_relations): Register
>         relations for all conditionals.
>         * tree-ssa-threadbackward.cc (back_threader::find_paths):
>         Adjust.
>
>         * gcc.dg/tree-ssa/ssa-thread-18.c: New testcase.
>         * gcc.dg/tree-ssa/ssa-thread-19.c: Likewise, but XFAILed.
> ---
>  gcc/gimple-range-path.cc                      | 21 +++++-------
>  gcc/gimple-range-path.h                       |  2 +-
>  gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-18.c | 20 +++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-19.c | 33 +++++++++++++++++++
>  gcc/tree-ssa-threadbackward.cc                |  4 ++-
>  5 files changed, 65 insertions(+), 15 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-18.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-19.c
>
> diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
> index 43e7526b6fc..389faec260c 100644
> --- a/gcc/gimple-range-path.cc
> +++ b/gcc/gimple-range-path.cc
> @@ -549,7 +549,7 @@ path_range_query::add_to_imports (tree name, bitmap imports)
>    return false;
>  }
>
> -// Compute the imports to the path ending in EXIT.  These are
> +// Compute the imports to PATH.  These are
>  // essentially the SSA names used to calculate the final conditional
>  // along the path.
>  //
> @@ -559,9 +559,10 @@ path_range_query::add_to_imports (tree name, bitmap imports)
>  // we can solve.
>
>  void
> -path_range_query::compute_imports (bitmap imports, basic_block exit)
> +path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
>  {
>    // Start with the imports from the exit block...
> +  basic_block exit = path[0];
>    gori_compute &gori = m_ranger->gori ();
>    bitmap r_imports = gori.imports (exit);
>    bitmap_copy (imports, r_imports);
> @@ -599,7 +600,7 @@ path_range_query::compute_imports (bitmap imports, basic_block exit)
>               tree arg = gimple_phi_arg (phi, i)->def;
>
>               if (TREE_CODE (arg) == SSA_NAME
> -                 && m_path.contains (e->src)
> +                 && path.contains (e->src)
>                   && bitmap_set_bit (imports, SSA_NAME_VERSION (arg)))
>                 worklist.safe_push (arg);
>             }
> @@ -607,9 +608,9 @@ path_range_query::compute_imports (bitmap imports, basic_block exit)
>      }
>    // Exported booleans along the path, may help conditionals.
>    if (m_resolve)
> -    for (i = 0; i < m_path.length (); ++i)
> +    for (i = 0; i < path.length (); ++i)
>        {
> -       basic_block bb = m_path[i];
> +       basic_block bb = path[i];
>         tree name;
>         FOR_EACH_GORI_EXPORT_NAME (gori, bb, name)
>           if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
> @@ -636,7 +637,7 @@ path_range_query::compute_ranges (const vec<basic_block> &path,
>    if (imports)
>      bitmap_copy (m_imports, imports);
>    else
> -    compute_imports (m_imports, exit_bb ());
> +    compute_imports (m_imports, m_path);
>
>    if (m_resolve)
>      get_path_oracle ()->reset_path ();
> @@ -845,15 +846,9 @@ path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
>  void
>  path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
>  {
> -  gimple *stmt = last_stmt (bb);
> -
> -  if (stmt
> -      && gimple_code (stmt) == GIMPLE_COND
> -      && (import_p (gimple_cond_lhs (stmt))
> -         || import_p (gimple_cond_rhs (stmt))))
> +  if (gcond *cond = safe_dyn_cast <gcond *> (last_stmt (bb)))
>      {
>        int_range<2> r;
> -      gcond *cond = as_a<gcond *> (stmt);
>        edge e0 = EDGE_SUCC (bb, 0);
>        edge e1 = EDGE_SUCC (bb, 1);
>
> diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
> index 2c4624e4cef..e783e00b2f5 100644
> --- a/gcc/gimple-range-path.h
> +++ b/gcc/gimple-range-path.h
> @@ -37,7 +37,7 @@ public:
>    void compute_ranges (const vec<basic_block> &,
>                        const bitmap_head *imports = NULL);
>    void compute_ranges (edge e);
> -  void compute_imports (bitmap imports, basic_block exit);
> +  void compute_imports (bitmap imports, const vec<basic_block> &);
>    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 ();
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-18.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-18.c
> new file mode 100644
> index 00000000000..a899f4f3fc0
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-18.c
> @@ -0,0 +1,20 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-threadfull1-stats" } */
> +
> +void foo (int nest, int print_nest)
> +{
> +  _Bool t0 = nest != 0;
> +  _Bool t1 = nest == print_nest;
> +  _Bool t2 = t0 & t1;
> +  if (t2)
> +    __builtin_puts ("x");
> +  nest++;
> +  if (nest > 2)
> +    __builtin_abort ();
> +  if (print_nest == nest)
> +    __builtin_puts ("y");
> +}
> +
> +/* We should be able to thread (t2) to !(print_nest == nest) using the
> +   nest == print_nest relation implied by the entry block.  */
> +/* { dg-final { scan-tree-dump "Jumps threaded: 1" "threadfull1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-19.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-19.c
> new file mode 100644
> index 00000000000..58a872b8d25
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-19.c
> @@ -0,0 +1,33 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-threadfull1-stats" } */
> +
> +struct S;
> +struct S { struct S *next; };
> +int foo (struct S *chain, _Bool is_ctor, _Bool is_dtor)
> +{
> +  int num_args = 0;
> +  if (chain) /* A */
> +    {
> +      do {
> +          num_args++;
> +          chain = chain->next;
> +          if (!chain)
> +            break;
> +      } while (1);
> +    }
> +  if (is_ctor)
> +    num_args++; /* B */
> +  if (is_dtor)
> +    num_args++;
> +  else
> +    {
> +      if (num_args > 2) /* C */
> +        __builtin_puts ("x");
> +    }
> +  return num_args;
> +}
> +
> +/* We want to thread both paths from A with NULL chain to C, the one through
> +   B and one around it.
> +   ???  Ideally we'd thread one "path" containing the half-diamond with B.  */
> +/* { dg-final { scan-tree-dump "Jumps threaded: 2" "threadfull1" { xfail *-*-* } } } */
> diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
> index 30047c654fb..6585a30551d 100644
> --- a/gcc/tree-ssa-threadbackward.cc
> +++ b/gcc/tree-ssa-threadbackward.cc
> @@ -451,7 +451,9 @@ back_threader::find_paths (basic_block bb, tree name)
>        m_visited_bbs.empty ();
>        m_path.truncate (0);
>        m_name = name;
> -      m_solver->compute_imports (m_imports, bb);
> +      m_path.safe_push (bb);
> +      m_solver->compute_imports (m_imports, m_path);
> +      m_path.pop ();
>
>        auto_bitmap interesting;
>        bitmap_copy (interesting, m_imports);
> --
> 2.35.3
>