On Thu, Nov 25, 2021 at 12:57 PM Richard Biener
<richard.guent...@gmail.com> wrote:
>
> 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?
Hmmm, good point.
Perhaps this isn't worth it then. I mean, the underlying bug I'm
tackling is an excess of outgoing edge ranges, not the excess
recursion this patch attacks.
If you think the cost would be high for large ILs, I can revert the patch.
Aldy
