[PATCH] Fix comparison of trees via tree_cmp

[Stefan Schulze Frielinghaus]

Hi David,

In function `tree_cmp` an invariant [1] is assumed which does not necessarily
exist. In case both input trees are finally compared via `strcmp`, then

  tree_cmp (t1, t2) == -tree_cmp (t2, t1)

does not hold in general, since function `strcmp (x, y)` guarantees only that a
negative integer is returned in case x<y or a positive integer in case x>y.
Currently this breaks s390x where, for example, for certain inputs x,y
`tree_cmp (x, y) == 1` and `tree_cmp (y, x) == -2` hold.  The attached patch
normalizes the output from `strcmp` to -1, 0, or 1 while using an auxiliary
function `sign` (stolen from the Hacker's Delight book ;-)).

Bootstrapped and tested on s390x. Any thoughts?

Cheers,
Stefan

[1] 
https://gcc.gnu.org/git/gitweb.cgi?p=gcc.git;a=blob;f=gcc/analyzer/region-model.cc;h=9474c6737d54d68f5b36893903cfa6d19df0efed;hb=HEAD#l1849

diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 9474c6737d5..bdd9a97e5f8 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -62,6 +62,20 @@ along with GCC; see the file COPYING3.  If not see
 
 #if ENABLE_ANALYZER
 
+/* Normalize X to either -1, 0, or 1.
+
+   Basically performs the same as
+     if (x < 0) return -1;
+     else if (x > 0) return 1;
+     else return 0;
+   but in a concise way trying to prevent branches.  */
+
+static int
+sign (int x)
+{
+  return (x > 0) - (x < 0);
+}
+
 /* Dump T to PP in language-independent form, for debugging/logging/dumping
    purposes.  */
 
@@ -1768,8 +1782,8 @@ tree_cmp (const_tree t1, const_tree t2)
   if (DECL_P (t1))
     {
       if (DECL_NAME (t1) && DECL_NAME (t2))
-       return strcmp (IDENTIFIER_POINTER (DECL_NAME (t1)),
-                      IDENTIFIER_POINTER (DECL_NAME (t2)));
+       return sign (strcmp (IDENTIFIER_POINTER (DECL_NAME (t1)),
+                            IDENTIFIER_POINTER (DECL_NAME (t2))));
       else
        {
          if (DECL_NAME (t1))
@@ -1819,8 +1833,8 @@ tree_cmp (const_tree t1, const_tree t2)
       }
 
     case STRING_CST:
-      return strcmp (TREE_STRING_POINTER (t1),
-                    TREE_STRING_POINTER (t2));
+      return sign (strcmp (TREE_STRING_POINTER (t1),
+                          TREE_STRING_POINTER (t2)));
 
     default:
       gcc_unreachable ();