Message ID | 20211125105459.2084694-1-aldyh@redhat.com |
---|---|
State | New |
Headers | show |
Series | [COMMITTED] path solver: Compute ranges in path in gimple order. | expand |
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 >
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. Aldy
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). Richard. > > Aldy >
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
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
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)) + 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. @@ -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);