public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [RFC][PATCH] Stabilize a few qsort comparison functions
@ 2018-02-07 16:58 Franz Sirl
  2018-02-08 15:33 ` Martin Jambor
  2018-06-12 21:49 ` Jeff Law
  0 siblings, 2 replies; 6+ messages in thread
From: Franz Sirl @ 2018-02-07 16:58 UTC (permalink / raw)
  To: GCC Patches; +Cc: Martin Jambor, Alexander Monakov

[-- 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;
 }
 

^ permalink raw reply	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2018-06-13 19:26 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-02-07 16:58 [RFC][PATCH] Stabilize a few qsort comparison functions Franz Sirl
2018-02-08 15:33 ` Martin Jambor
2018-06-12 21:49 ` Jeff Law
2018-06-13 11:50   ` Franz Sirl
2018-06-13 12:47     ` Alexander Monakov
2018-06-13 19:26     ` Jeff Law

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).