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
>
