This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH][middle-end] Make qsort in tree-ssa-sccvn.c stable.


This patch stabilizes sort of SSC in tree-ssa-sccvn.c so that sort
result is not dependent of the implementation of qsort().  Previously,
instability in sort resuilt caused slightly different code to be
generated on OSX and Linux hosted gcc compiled for arm-none-eabi.  The
patch has been bootstrapped and regression tested natively on
x86_64-unknown-linux-gnu.

Okay to commit?

2009-05-11  Doug Kwan  <dougkwan@google.com>

        * tree-ssa-sccvn.c (compare_ops_1): Renamed from compare_ops.
        (compare_ops): Wrapper for original compare_ops to stabilize qsort.

Index: gcc/gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/gcc/tree-ssa-sccvn.c    (revision 147396)
+++ gcc/gcc/tree-ssa-sccvn.c    (working copy)
@@ -2411,7 +2411,7 @@ visit_use (tree use)
 /* Compare two operands by reverse postorder index */

 static int
-compare_ops (const void *pa, const void *pb)
+compare_ops_1 (const void *pa, const void *pb)
 {
   const tree opa = *((const tree *)pa);
   const tree opb = *((const tree *)pb);
@@ -2451,6 +2451,36 @@ compare_ops (const void *pa, const void
   return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
 }

+static int
+compare_ops (const void *pa, const void *pb)
+{
+  const tree opa = *((const tree *)pa);
+  const tree opb = *((const tree *)pb);
+  unsigned HOST_WIDE_INT uid_a, uid_b;
+  unsigned HOST_WIDE_INT ver_a, ver_b;
+  int status = compare_ops_1 (pa, pb);
+
+  if (status != 0)
+    return status;
+
+  /* Make qsort stable by doing addition comparisons. */
+  uid_a = DECL_UID (SSA_NAME_VAR (opa));
+  uid_b = DECL_UID (SSA_NAME_VAR (opb));
+  if (uid_a < uid_b)
+    return -1;
+  else if (uid_a > uid_b)
+    return 1;
+
+  ver_a = SSA_NAME_VERSION (opa);
+  ver_b = SSA_NAME_VERSION (opb);
+  if (ver_a < ver_b)
+    return -1;
+  else if (ver_a > ver_b)
+    return 1;
+  else
+    return 0;
+}
+
 /* Sort an array containing members of a strongly connected component
    SCC so that the members are ordered by RPO number.
    This means that when the sort is complete, iterating through the


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]