[RFC][PATCH] Stabilize a few qsort comparison functions

[RFC][PATCH] Stabilize a few qsort comparison functions

[Franz Sirl]

[-- Attachment #1: Type: text/plain, Size: 1779 bytes --]

Hi,

this is the result of an attempt to minimize the differences between the
compile results of a Linux-based and a Cygwin64-based powerpc-eabi cross
toolchain.
The method used was:

     - find the -fverbose-asm assembler files that differ
     - compile that file again on both platforms with
        -O2 -g3 -fdump-tree-all-all -fdump-rtl-all -fdump-noaddr
     - look for the first dump file with differences and check that pass
       for qsort's
     - stabilize the compare functions

With some help on IRC to better understand the passes and some serious
debugging of GCC I came up with this patch. On the tested codebase the
differences in the assembler sources are now down to 0.
If the various pass maintainers have better ideas on how to stabilize
the compare functions, I'll be happy to verify them on the codebase.
For the SRA patch I already have an alternate version with an additional
ID member.

Comments?

Bootstrapped on linux-x86_64, no testsuite regressions.

Franz Sirl


2018-02-07  Franz Sirl <franz.sirl-kernel@lauterbach.com>

     * ira-build.c (object_range_compare_func): Stabilize sort.
     * tree-sra.c (compare_access_positions): Likewise.
     * varasm.c (output_object_block_compare): Likewise.
     * tree-ssa-loop-ivopts.c (group_compare_offset): Likewise.
     (struct iv_common_cand): New member.
     (record_common_cand): Initialize new member.
     (common_cand_cmp): Use new member to stabilize sort.
     * tree-vrp.c (struct assert_locus): New member.
     (register_new_assert_for): Initialize new member.
     (compare_assert_loc): Use new member to stabilize sort.



[-- Attachment #2: gcc-8-stabilize-sort-1.diff --]
[-- Type: text/plain, Size: 5030 bytes --]

Index: gcc/ira-build.c
===================================================================
--- gcc/ira-build.c	(revision 257438)
+++ gcc/ira-build.c	(working copy)
@@ -2787,8 +2787,10 @@ object_range_compare_func (const void *v1p, const
   if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
     return diff;
   if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
-     return diff;
-  return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
+    return diff;
+  if ((diff = ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2)) != 0)
+    return diff;
+  return OBJECT_SUBWORD (obj1) - OBJECT_SUBWORD (obj2);
 }
 
 /* Sort ira_object_id_map and set up conflict id of allocnos.  */
Index: gcc/tree-sra.c
===================================================================
--- gcc/tree-sra.c	(revision 257438)
+++ gcc/tree-sra.c	(working copy)
@@ -1567,7 +1567,13 @@ compare_access_positions (const void *a, const voi
   if (f1->size == f2->size)
     {
       if (f1->type == f2->type)
-	return 0;
+	{
+	  if (f1->stmt == f2->stmt)
+	    return 0;
+	  if (f1->stmt && f2->stmt)
+	    return gimple_uid (f1->stmt) - gimple_uid (f2->stmt);
+	  return f1->stmt ? -1 : 1;
+	}
       /* Put any non-aggregate type before any aggregate type.  */
       else if (!is_gimple_reg_type (f1->type)
 	  && is_gimple_reg_type (f2->type))
Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c	(revision 257438)
+++ gcc/tree-ssa-loop-ivopts.c	(working copy)
@@ -443,6 +443,7 @@ struct iv_common_cand
   /* IV uses from which this common candidate is derived.  */
   auto_vec<struct iv_use *> uses;
   hashval_t hash;
+  unsigned id;
 };
 
 /* Hashtable helpers.  */
@@ -2617,8 +2618,11 @@ group_compare_offset (const void *a, const void *b
 {
   const struct iv_use *const *u1 = (const struct iv_use *const *) a;
   const struct iv_use *const *u2 = (const struct iv_use *const *) b;
+  int diff;
 
-  return compare_sizes_for_sort ((*u1)->addr_offset, (*u2)->addr_offset);
+  if ((diff = compare_sizes_for_sort ((*u1)->addr_offset, (*u2)->addr_offset)) != 0)
+    return diff;
+  return (*u1)->id - (*u2)->id;
 }
 
 /* Check if small groups should be split.  Return true if no group
@@ -3378,6 +3382,7 @@ record_common_cand (struct ivopts_data *data, tree
   struct iv_common_cand ent;
   struct iv_common_cand **slot;
 
+  ent.id = data->iv_common_cands.length ();
   ent.base = base;
   ent.step = step;
   ent.hash = iterative_hash_expr (base, 0);
@@ -3387,6 +3392,7 @@ record_common_cand (struct ivopts_data *data, tree
   if (*slot == NULL)
     {
       *slot = new iv_common_cand ();
+      (*slot)->id = ent.id;
       (*slot)->base = base;
       (*slot)->step = step;
       (*slot)->uses.create (8);
@@ -3412,6 +3418,8 @@ common_cand_cmp (const void *p1, const void *p2)
 
   n1 = (*ccand1)->uses.length ();
   n2 = (*ccand2)->uses.length ();
+  if (n1 == n2)
+    return (*ccand1)->id - (*ccand2)->id;
   return n2 - n1;
 }
 
Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 257438)
+++ gcc/tree-vrp.c	(working copy)
@@ -101,6 +101,8 @@ struct assert_locus
   /* Predicate code for the ASSERT_EXPR.  Must be COMPARISON_CLASS_P.  */
   enum tree_code comp_code;
 
+  unsigned id;
+
   /* Value being compared against.  */
   tree val;
 
@@ -2814,6 +2816,7 @@ register_new_assert_for (tree name, tree expr,
 {
   assert_locus *n, *loc, *last_loc;
   basic_block dest_bb;
+  unsigned cnt = 0;
 
   gcc_checking_assert (bb == NULL || e == NULL);
 
@@ -2882,6 +2885,7 @@ register_new_assert_for (tree name, tree expr,
       /* Update the last node of the list and move to the next one.  */
       last_loc = loc;
       loc = loc->next;
+      cnt++;
     }
 
   /* If we didn't find an assertion already registered for
@@ -2895,6 +2899,7 @@ register_new_assert_for (tree name, tree expr,
   n->val = val;
   n->expr = expr;
   n->next = NULL;
+  n->id = cnt;
 
   if (last_loc)
     last_loc->next = n;
@@ -4591,9 +4596,15 @@ compare_assert_loc (const void *pa, const void *pb
 
   /* Break the tie using hashing and source/bb index.  */
   if (ha == hb)
-    return (a->e != NULL
-	    ? a->e->src->index - b->e->src->index
-	    : a->bb->index - b->bb->index);
+    {
+      if (a->e != NULL)
+	{
+	  if (a->e == b->e)
+	    return a->id - b->id;
+	  return a->e->src->index - b->e->src->index;
+	}
+      return a->bb->index - b->bb->index;
+    }
   return ha > hb ? 1 : -1;
 }
 
Index: gcc/varasm.c
===================================================================
--- gcc/varasm.c	(revision 257438)
+++ gcc/varasm.c	(working copy)
@@ -7632,7 +7632,11 @@ output_object_block_compare (const void *x, const
   unsigned f1 = p1->sect->common.flags;
   unsigned f2 = p2->sect->common.flags;
   if (f1 == f2)
-    return 0;
+    {
+      if (p1->anchors && p2->anchors)
+	return strcmp (XSTR ((*p1->anchors)[0], 0), XSTR ((*p2->anchors)[0], 0));
+      return 0;
+    }
   return f1 < f2 ? -1 : 1;
 }
 

Re: [RFC][PATCH] Stabilize a few qsort comparison functions

[Martin Jambor]

On Wed, Feb 07 2018, Franz Sirl wrote:
> Hi,
>
> this is the result of an attempt to minimize the differences between the
> compile results of a Linux-based and a Cygwin64-based powerpc-eabi cross
> toolchain.
> The method used was:
>
>      - find the -fverbose-asm assembler files that differ
>      - compile that file again on both platforms with
>         -O2 -g3 -fdump-tree-all-all -fdump-rtl-all -fdump-noaddr
>      - look for the first dump file with differences and check that pass
>        for qsort's
>      - stabilize the compare functions
>
> With some help on IRC to better understand the passes and some serious
> debugging of GCC I came up with this patch. On the tested codebase the
> differences in the assembler sources are now down to 0.
> If the various pass maintainers have better ideas on how to stabilize
> the compare functions, I'll be happy to verify them on the codebase.
> For the SRA patch I already have an alternate version with an additional
> ID member.
>
> Comments?

As I said on IRC, if you find this useful, I'm fine with having the SRA
hunk (but note that I cannot approve it).  In any event, IMHO this is
stage 1 material, however.

Thanks,

Martin


>
> Bootstrapped on linux-x86_64, no testsuite regressions.
>
> Franz Sirl
>
>
> 2018-02-07  Franz Sirl <franz.sirl-kernel@lauterbach.com>
>
>      * ira-build.c (object_range_compare_func): Stabilize sort.
>      * tree-sra.c (compare_access_positions): Likewise.
>      * varasm.c (output_object_block_compare): Likewise.
>      * tree-ssa-loop-ivopts.c (group_compare_offset): Likewise.
>      (struct iv_common_cand): New member.
>      (record_common_cand): Initialize new member.
>      (common_cand_cmp): Use new member to stabilize sort.
>      * tree-vrp.c (struct assert_locus): New member.
>      (register_new_assert_for): Initialize new member.
>      (compare_assert_loc): Use new member to stabilize sort.
>

Re: [RFC][PATCH] Stabilize a few qsort comparison functions

[Jeff Law]

On 02/07/2018 09:58 AM, Franz Sirl wrote:
> Hi,
> 
> this is the result of an attempt to minimize the differences between the
> compile results of a Linux-based and a Cygwin64-based powerpc-eabi cross
> toolchain.
> The method used was:
> 
>     - find the -fverbose-asm assembler files that differ
>     - compile that file again on both platforms with
>        -O2 -g3 -fdump-tree-all-all -fdump-rtl-all -fdump-noaddr
>     - look for the first dump file with differences and check that pass
>       for qsort's
>     - stabilize the compare functions
> 
> With some help on IRC to better understand the passes and some serious
> debugging of GCC I came up with this patch. On the tested codebase the
> differences in the assembler sources are now down to 0.
> If the various pass maintainers have better ideas on how to stabilize
> the compare functions, I'll be happy to verify them on the codebase.
> For the SRA patch I already have an alternate version with an additional
> ID member.
> 
> Comments?
> 
> Bootstrapped on linux-x86_64, no testsuite regressions.
> 
> Franz Sirl
> 
> 
> 2018-02-07  Franz Sirl <franz.sirl-kernel@lauterbach.com>
> 
>     * ira-build.c (object_range_compare_func): Stabilize sort.
>     * tree-sra.c (compare_access_positions): Likewise.
>     * varasm.c (output_object_block_compare): Likewise.
>     * tree-ssa-loop-ivopts.c (group_compare_offset): Likewise.
>     (struct iv_common_cand): New member.
>     (record_common_cand): Initialize new member.
>     (common_cand_cmp): Use new member to stabilize sort.
>     * tree-vrp.c (struct assert_locus): New member.
>     (register_new_assert_for): Initialize new member.
>     (compare_assert_loc): Use new member to stabilize sort.
This looks pretty reasonable.   I don't think you've contributed much
recently, do you still have write access to the repository?

jeff

Re: [RFC][PATCH] Stabilize a few qsort comparison functions

[Franz Sirl]

Am 2018-06-12 um 23:49 schrieb Jeff Law:
> On 02/07/2018 09:58 AM, Franz Sirl wrote:
>> Hi,
>>
>> this is the result of an attempt to minimize the differences between the
>> compile results of a Linux-based and a Cygwin64-based powerpc-eabi cross
>> toolchain.
>> The method used was:
>>
>>      - find the -fverbose-asm assembler files that differ
>>      - compile that file again on both platforms with
>>         -O2 -g3 -fdump-tree-all-all -fdump-rtl-all -fdump-noaddr
>>      - look for the first dump file with differences and check that pass
>>        for qsort's
>>      - stabilize the compare functions
>>
>> With some help on IRC to better understand the passes and some serious
>> debugging of GCC I came up with this patch. On the tested codebase the
>> differences in the assembler sources are now down to 0.
>> If the various pass maintainers have better ideas on how to stabilize
>> the compare functions, I'll be happy to verify them on the codebase.
>> For the SRA patch I already have an alternate version with an additional
>> ID member.
>>
>> Comments?
>>
>> Bootstrapped on linux-x86_64, no testsuite regressions.
>>
>> Franz Sirl
>>
>>
>> 2018-02-07  Franz Sirl <franz.sirl-kernel@lauterbach.com>
>>
>>      * ira-build.c (object_range_compare_func): Stabilize sort.
>>      * tree-sra.c (compare_access_positions): Likewise.
>>      * varasm.c (output_object_block_compare): Likewise.
>>      * tree-ssa-loop-ivopts.c (group_compare_offset): Likewise.
>>      (struct iv_common_cand): New member.
>>      (record_common_cand): Initialize new member.
>>      (common_cand_cmp): Use new member to stabilize sort.
>>      * tree-vrp.c (struct assert_locus): New member.
>>      (register_new_assert_for): Initialize new member.
>>      (compare_assert_loc): Use new member to stabilize sort.
> This looks pretty reasonable.   I don't think you've contributed much
> recently, do you still have write access to the repository?

Hi Jeff,

after Alexander Monakov's gcc_qsort changes, this patch is not necessary 
anymore. I've verified that with a backport (the 2 patches r260216 and 
r260222 applied cleanly) of gcc_qsort to the gcc-8-branch. The resulting 
powerpc-eabi crosscompilers produce no more unexpected differences 
between a Linux and a Cygwin host.
Tested (same like with my patch) by comparing the -fverbose-asm assembly 
output on a complete rebuild of the software here.
So, unless someone thinks one of the changes makes sense anyway, this 
patch is obsolete.

On the repository write access, yes, I don't have one anymore. But 
before reactivating that I need to do the legal paperwork, because 
unless before when GCC was a strictly private pet project for me, it now 
is work related. I already got permission from my company for that, just 
need to find some spare time to start the legal stuff.

Franz

Re: [RFC][PATCH] Stabilize a few qsort comparison functions

[Alexander Monakov]

On Wed, 13 Jun 2018, Franz Sirl wrote:
> So, unless someone thinks one of the changes makes sense anyway, this patch is
> obsolete.

Yeah, I think that in light of gcc_qsort work this patch is completely
unnecessary now, and shouldn't be applied. In fact, reversing earlier
artificial stabilization changes may be desirable.

Alexander

Re: [RFC][PATCH] Stabilize a few qsort comparison functions

[Jeff Law]

On 06/13/2018 05:50 AM, Franz Sirl wrote:
>>>
>>>
>>> 2018-02-07  Franz Sirl <franz.sirl-kernel@lauterbach.com>
>>>
>>>      * ira-build.c (object_range_compare_func): Stabilize sort.
>>>      * tree-sra.c (compare_access_positions): Likewise.
>>>      * varasm.c (output_object_block_compare): Likewise.
>>>      * tree-ssa-loop-ivopts.c (group_compare_offset): Likewise.
>>>      (struct iv_common_cand): New member.
>>>      (record_common_cand): Initialize new member.
>>>      (common_cand_cmp): Use new member to stabilize sort.
>>>      * tree-vrp.c (struct assert_locus): New member.
>>>      (register_new_assert_for): Initialize new member.
>>>      (compare_assert_loc): Use new member to stabilize sort.
>> This looks pretty reasonable.   I don't think you've contributed much
>> recently, do you still have write access to the repository?
> 
> Hi Jeff,
> 
> after Alexander Monakov's gcc_qsort changes, this patch is not necessary
> anymore. I've verified that with a backport (the 2 patches r260216 and
> r260222 applied cleanly) of gcc_qsort to the gcc-8-branch. The resulting
> powerpc-eabi crosscompilers produce no more unexpected differences
> between a Linux and a Cygwin host.
OK Good.

> Tested (same like with my patch) by comparing the -fverbose-asm assembly
> output on a complete rebuild of the software here.
> So, unless someone thinks one of the changes makes sense anyway, this
> patch is obsolete.
Let's drop then.


> 
> On the repository write access, yes, I don't have one anymore. But
> before reactivating that I need to do the legal paperwork, because
> unless before when GCC was a strictly private pet project for me, it now
> is work related. I already got permission from my company for that, just
> need to find some spare time to start the legal stuff.
Understood.  Good to have you back!

jeff