Re: [PATCH] ipa: Sort ipa_param_body_adjustments::m_replacements (PR 108110)

[Martin Liška]

On 1/6/23 17:50, Martin Jambor wrote:

Hi,

On Fri, Jan 06 2023, Martin Liška wrote:

Hi Martin


+  key.unit_offset = unit_offset;
+  ipa_param_body_replacement *res
+= std::lower_bound (m_replacements.begin (), m_replacements.end (), key,
+   [] (const ipa_param_body_replacement ,
+   const ipa_param_body_replacement )
+   {
+ if (DECL_UID (elt.base) < DECL_UID (val.base))
+   return true;
+ if (DECL_UID (elt.base) > DECL_UID (val.base))
+   return false;
+ if (elt.unit_offset < val.unit_offset)
+   return true;
+ return false;
+   });


I'm curious if we can re-use compare_param_body_replacement as the introduced
lambda does a very similar thing, right?



Not directly, the qsort callback returns an integer that can be either
negative, positive or zero but the lower_bound returns only true or
false (the semantics is that it returns the first element for which it
returns false).  Plus one takes parameters which are pointer and other
needs references.


Hi.

I see, so leaving that up to you if you want to adjust it or not.

OK for both versions of the patch.

Cheers,
Martin



So I was lazy and just came up with a similar comparator lambda.  But
sure, I can call the qsort comparator from it, which I guess makes sense
at least for consistency.  I'll adjust the patch.

Thanks,

Martin

Re: [PATCH] ipa: Sort ipa_param_body_adjustments::m_replacements (PR 108110)

[Martin Jambor]

Hi,

On Fri, Jan 06 2023, Martin Liška wrote:
> Hi Martin
>
>> +  key.unit_offset = unit_offset;
>> +  ipa_param_body_replacement *res
>> += std::lower_bound (m_replacements.begin (), m_replacements.end (), key,
>> +[] (const ipa_param_body_replacement ,
>> +const ipa_param_body_replacement )
>> +{
>> +  if (DECL_UID (elt.base) < DECL_UID (val.base))
>> +return true;
>> +  if (DECL_UID (elt.base) > DECL_UID (val.base))
>> +return false;
>> +  if (elt.unit_offset < val.unit_offset)
>> +return true;
>> +  return false;
>> +});
>
> I'm curious if we can re-use compare_param_body_replacement as the introduced
> lambda does a very similar thing, right?
>

Not directly, the qsort callback returns an integer that can be either
negative, positive or zero but the lower_bound returns only true or
false (the semantics is that it returns the first element for which it
returns false).  Plus one takes parameters which are pointer and other
needs references.

So I was lazy and just came up with a similar comparator lambda.  But
sure, I can call the qsort comparator from it, which I guess makes sense
at least for consistency.  I'll adjust the patch.

Thanks,

Martin

Re: [PATCH] ipa: Sort ipa_param_body_adjustments::m_replacements (PR 108110)

[Martin Liška]

Hi Martin

> +  key.unit_offset = unit_offset;
> +  ipa_param_body_replacement *res
> += std::lower_bound (m_replacements.begin (), m_replacements.end (), key,
> + [] (const ipa_param_body_replacement ,
> + const ipa_param_body_replacement )
> + {
> +   if (DECL_UID (elt.base) < DECL_UID (val.base))
> + return true;
> +   if (DECL_UID (elt.base) > DECL_UID (val.base))
> + return false;
> +   if (elt.unit_offset < val.unit_offset)
> + return true;
> +   return false;
> + });

I'm curious if we can re-use compare_param_body_replacement as the introduced
lambda does a very similar thing, right?

Thanks,
Martin

[PATCH] ipa: Sort ipa_param_body_adjustments::m_replacements (PR 108110)

[Martin Jambor]

Hi,

the problem in PR 108110 is that elements describing the same base
parameter in ipa_param_body_adjustments::m_replacements are not
adjacent to each other, which is something that
ipa_param_body_adjustments::modify_call_stmt when it gathers all
replacements for a parameter.

One option would be to simply always keep looking until the end of the
vector (see bugzilla comment 15 for a one-line fix) but the correct
thing to do is to keep the elements of the vector sorted and thus make
such elements adjacent again.  This patch does that and then also
modifies the look-ups to take advantage of it.

Since the one user of ipa_param_body_adjustments that is not
tree-inline.cc, which is OpenMP declare SIMD cloning code, also
registers its own replacements and in theory pointers to elements of
the m_replacements vector can leak through public method
get_expr_replacement, I decided that in those cases it is the
responsibility of the user of the class to call the sorting method
between the replacement registrations and the first lookup.  That is
why the patch also adds a line to omp-simd-clone.cc.

Bootstrapped, tested and LTO-bootstrapped on x86_64-linux.  OK for
trunk?

Thanks,

Martin


gcc/ChangeLog:

2023-01-04  Martin Jambor  

* ipa-param-manipulation.h (ipa_param_body_adjustments): New members
sort_replacements, lookup_first_base_replacement and
m_sorted_replacements_p.
* ipa-param-manipulation.cc: Define INCLUDE_ALGORITHM.
(ipa_param_body_adjustments::register_replacement): Set
m_sorted_replacements_p to false.
(compare_param_body_replacement): New function.
(ipa_param_body_adjustments::sort_replacements): Likewise.
(ipa_param_body_adjustments::common_initialization): Call
sort_replacements.
(ipa_param_body_adjustments::ipa_param_body_adjustments): Initialize
m_sorted_replacements_p.
(ipa_param_body_adjustments::lookup_replacement_1): Rework to use
std::lower_bound.
(ipa_param_body_adjustments::lookup_first_base_replacement): New
function.
(ipa_param_body_adjustments::modify_call_stmt): Use
lookup_first_base_replacement.
* omp-simd-clone.cc (ipa_simd_modify_function_body): Call
adjustments->sort_replacements.

gcc/testsuite/ChangeLog:

2023-01-04  Martin Jambor  

* g++.dg/ipa/pr108110.C: New test.
---
 gcc/ipa-param-manipulation.cc   | 116 +---
 gcc/ipa-param-manipulation.h|   9 +++
 gcc/omp-simd-clone.cc   |   1 +
 gcc/testsuite/g++.dg/ipa/pr108110.C |  32 
 4 files changed, 132 insertions(+), 26 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/ipa/pr108110.C

diff --git a/gcc/ipa-param-manipulation.cc b/gcc/ipa-param-manipulation.cc
index a0e4098a3f1..8d78ef57c12 100644
--- a/gcc/ipa-param-manipulation.cc
+++ b/gcc/ipa-param-manipulation.cc
@@ -18,6 +18,7 @@ You should have received a copy of the GNU General Public 
License
 along with GCC; see the file COPYING3.  If not see
 .  */
 
+#define INCLUDE_ALGORITHM
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
@@ -1000,6 +1001,7 @@ ipa_param_body_adjustments::register_replacement (tree 
base,
   psr.dummy = NULL_TREE;
   psr.unit_offset = unit_offset;
   m_replacements.safe_push (psr);
+  m_sorted_replacements_p = false;
 }
 
 /* Register that REPLACEMENT should replace parameter described in APM.  */
@@ -1015,6 +1017,36 @@ ipa_param_body_adjustments::register_replacement 
(ipa_adjusted_param *apm,
replacement);
 }
 
+/* Comparator to qsort ipa_param_body_adjustments::m_replacements.  */
+
+static int
+compare_param_body_replacement (const void *va, const void *vb)
+{
+  const ipa_param_body_replacement *a = (const ipa_param_body_replacement *) 
va;
+  const ipa_param_body_replacement *b = (const ipa_param_body_replacement *) 
vb;
+
+  if (DECL_UID (a->base) < DECL_UID (b->base))
+return -1;
+  if (DECL_UID (a->base) > DECL_UID (b->base))
+return 1;
+  if (a->unit_offset < b->unit_offset)
+return -1;
+  if (a->unit_offset > b->unit_offset)
+return 1;
+  return 0;
+}
+
+/* Sort m_replacements and set m_sorted_replacements_p to true.  */
+
+void
+ipa_param_body_adjustments::sort_replacements ()
+{
+  if (m_sorted_replacements_p)
+return;
+  m_replacements.qsort (compare_param_body_replacement);
+  m_sorted_replacements_p = true;
+}
+
 /* Copy or not, as appropriate given m_id and decl context, a pre-existing
PARM_DECL T so that it can be included in the parameters of the modified
function.  */
@@ -1426,6 +1458,7 @@ ipa_param_body_adjustments::common_initialization (tree 
old_fndecl,
}
}
 }
+  sort_replacements ();
 
   if (tree_map)
 {
@@ -1503,7 +1536,7 @@ ipa_param_body_adjustments
 m_dead_stmt_debug_equiv (), m_fndecl (fndecl), m_id (NULL), m_oparms (),
 m_new_decls (), m_new_types (),