Pushed.
Sorry for the noise.
On Thu, Nov 25, 2021 at 1:51 PM Aldy Hernandez <al...@redhat.com> wrote:
>
> On Thu, Nov 25, 2021 at 1:38 PM Richard Biener
> <richard.guent...@gmail.com> wrote:
> >
> > On Thu, Nov 25, 2021 at 1:10 PM Aldy Hernandez <al...@redhat.com> wrote:
> > >
> > > 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.
> >
> > 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
From f21dc29d923f559c069fbd0b32e473f5a76de12c Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <al...@redhat.com>
Date: Thu, 25 Nov 2021 17:30:07 +0100
Subject: [PATCH] path solver: Revert computation of ranges in gimple order.
Revert the patch below, as it may slow down compilation with large CFGs.
commit 8acbd7bef6edbf537e3037174907029b530212f6
Author: Aldy Hernandez <al...@redhat.com>
Date: Wed Nov 24 09:43:36 2021 +0100
path solver: Compute ranges in path in gimple order.
---
gcc/gimple-range-path.cc | 33 +++++++++++----------------------
gcc/gimple-range-path.h | 1 -
2 files changed, 11 insertions(+), 23 deletions(-)
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 806bce9ff11..b9c71226c1c 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -401,27 +401,6 @@ 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))
- 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);
- }
-}
-
// Compute ranges defined in the current block, or exported to the
// next block.
@@ -444,7 +423,17 @@ path_range_query::compute_ranges_in_block (basic_block bb)
clear_cache (name);
}
- compute_ranges_defined (bb);
+ // 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);
+ }
if (at_exit ())
return;
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index 81c87d475dd..57a9ae9bdcd 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -58,7 +58,6 @@ 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
