analyzer: fixes to tree_cmp and other comparators

region_model.cc's tree_cmp attempted to verify that the ordering
is symmetric by asserting that
  tree_cmp (x, y) == -tree_cmp (y, x)

This condition is too strong: it's only required for a comparator that
  sign (tree_cmp (x, y)) == -sign (tree_cmp (y, x))
and the incorrect form of the assertion doesn't hold e.g. on s390x where
for certain inputs x, y, tree_cmp (x, y) == 1 and tree_cmp (y, x) == -2,
breaking the build in "make selftest" in stage1.

In any case, these checks are redundant, since qsort_chk performs them.

Additionally, there is a potential lack of transitivity in
worklist::key_t::cmp where hashval_t values are compared by subtraction,
which could fail to be transitive if overflows occur.

This patch eliminates the redundant checks and reimplements the hashval_t
comparisons in terms of < and >, fixing these issues.

gcc/analyzer/ChangeLog:
	* call-string.cc (call_string::cmp_1): Delete, moving body to...
	(call_string::cmp): ...here.
	* call-string.h (call_string::cmp_1): Delete decl.
	* engine.cc (worklist::key_t::cmp_1): Delete, moving body to...
	(worklist::key_t::cmp): ...here.  Implement hash comparisons
	via comparison rather than subtraction to avoid overflow issues.
	* exploded-graph.h (worklist::key_t::cmp_1): Delete decl.
	* region-model.cc (tree_cmp): Eliminate buggy checking for
	symmetry.

1 files changed, 1 insertions, 22 deletions

diff --git a/gcc/analyzer/call-string.cc b/gcc/analyzer/call-string.cc
index 3d398c39a88..288953ed37c 100644
--- a/gcc/analyzer/call-string.cc
+++ b/gcc/analyzer/call-string.cc
@@ -149,6 +149,7 @@ call_string::calc_recursion_depth () const
 }
 
 /* Comparator for call strings.
+   This implements a version of lexicographical order.
    Return negative if A is before B.
    Return positive if B is after A.
    Return 0 if they are equal.  */
@@ -157,28 +158,6 @@ int
 call_string::cmp (const call_string &a,
 		  const call_string &b)
 {
-  int result = cmp_1 (a, b);
-
-  /* Check that the ordering is symmetric  */
-#if CHECKING_P
-  int reversed = cmp_1 (b, a);
-  gcc_assert (reversed == -result);
-#endif
-
-  /* We should only have 0 for equal pairs.  */
-  gcc_assert (result != 0
-	      || a == b);
-
-  return result;
-}
-
-/* Implementation of call_string::cmp.
-   This implements a version of lexicographical order.  */
-
-int
-call_string::cmp_1 (const call_string &a,
-		    const call_string &b)
-{
   unsigned len_a = a.length ();
   unsigned len_b = b.length ();