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

Aldy Hernandez aldyh@redhat.com
Thu Nov 25 16:33:04 GMT 2021


Pushed.

Sorry for the noise.

On Thu, Nov 25, 2021 at 1:51 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> On Thu, Nov 25, 2021 at 1:38 PM Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > On Thu, Nov 25, 2021 at 1:10 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> > >
> > > On Thu, Nov 25, 2021 at 12:57 PM Richard Biener
> > > <richard.guenther@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.
> >
> > I think so.  If ordering is important then that should be achieved in some
> > other ways (always a bit difficult for on-demand infrastructure).
>
> Nah, this isn't a correctness issue.  It's not worth it.
>
> I will revert the patch.
>
> Thanks.
> Aldy
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-path-solver-Revert-computation-of-ranges-in-gimple-o.patch
Type: text/x-patch
Size: 2686 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20211125/61a1e634/attachment-0001.bin>


More information about the Gcc-patches mailing list