[COMMITTED] path solver: Compute ranges in path in gimple order.

[Richard Biener]

On Thu, Nov 25, 2021 at 11:55 AM Aldy Hernandez via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> Andrew's patch for this PR103254 papered over some underlying
> performance issues in the path solver that I'd like to address.
>
> We are currently solving the SSA's defined in the current block in
> bitmap order, which amounts to random order for all purposes.  This is
> causing unnecessary recursion in gori.  This patch changes the order
> to gimple order, thus solving dependencies before uses.
>
> There is no change in threadable paths with this change.
>
> Tested on x86-64 & ppc64le Linux.
>
> gcc/ChangeLog:
>
>         PR tree-optimization/103254
>         * gimple-range-path.cc (path_range_query::compute_ranges_defined): New
>         (path_range_query::compute_ranges_in_block): Move to
>         compute_ranges_defined.
>         * gimple-range-path.h (compute_ranges_defined): New.
> ---
>  gcc/gimple-range-path.cc | 33 ++++++++++++++++++++++-----------
>  gcc/gimple-range-path.h  |  1 +
>  2 files changed, 23 insertions(+), 11 deletions(-)
>
> diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
> index 4aa666d2c8b..e24086691c4 100644
> --- a/gcc/gimple-range-path.cc
> +++ b/gcc/gimple-range-path.cc
> @@ -401,6 +401,27 @@ path_range_query::compute_ranges_in_phis (basic_block bb)
>      }
>  }
>
> +// Compute ranges defined in block.
> +
> +void
> +path_range_query::compute_ranges_defined (basic_block bb)
> +{
> +  int_range_max r;
> +
> +  compute_ranges_in_phis (bb);
> +
> +  // Iterate in gimple order to minimize recursion.
> +  for (auto gsi = gsi_start_nondebug_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))

gsi_next_nondebug (&gsi)?

Of course this  all has the extra cost of iterating over a possibly very large
BB for just a few bits in m_imports?  How often does m_imports have
exactly one bit set?

> +    if (gimple_has_lhs (gsi_stmt (gsi)))
> +      {
> +       tree name = gimple_get_lhs (gsi_stmt (gsi));
> +       if (TREE_CODE (name) == SSA_NAME
> +           && bitmap_bit_p (m_imports, SSA_NAME_VERSION (name))
> +           && range_defined_in_block (r, name, bb))
> +         set_cache (r, name);
> +      }

So if you ever handle SSA DEFs in asms then this will not pick them.
I think more generic would be to do

    FOR_EACH_SSA_DEF_OPERAND (..., SSA_OP_DEF)



> +}
> +
>  // Compute ranges defined in the current block, or exported to the
>  // next block.
>
> @@ -423,17 +444,7 @@ path_range_query::compute_ranges_in_block (basic_block bb)
>         clear_cache (name);
>      }
>
> -  // Solve imports defined in this block, starting with the PHIs...
> -  compute_ranges_in_phis (bb);
> -  // ...and then the rest of the imports.
> -  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
> -    {
> -      tree name = ssa_name (i);
> -
> -      if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
> -         && range_defined_in_block (r, name, bb))
> -       set_cache (r, name);
> -    }
> +  compute_ranges_defined (bb);
>
>    if (at_exit ())
>      return;
> diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
> index 57a9ae9bdcd..81c87d475dd 100644
> --- a/gcc/gimple-range-path.h
> +++ b/gcc/gimple-range-path.h
> @@ -58,6 +58,7 @@ private:
>    // Methods to compute ranges for the given path.
>    bool range_defined_in_block (irange &, tree name, basic_block bb);
>    void compute_ranges_in_block (basic_block bb);
> +  void compute_ranges_defined (basic_block bb);
>    void compute_ranges_in_phis (basic_block bb);
>    void adjust_for_non_null_uses (basic_block bb);
>    void ssa_range_in_phi (irange &r, gphi *phi);
> --
> 2.31.1
>