[PATCH] Fix comparison of trees via tree_cmp

[PATCH] Fix comparison of trees via tree_cmp

[Stefan Schulze Frielinghaus]

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

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

[-- Attachment #2: strcmp.patch --]
[-- Type: text/plain, Size: 1346 bytes --]

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 ();

Re: [PATCH] Fix comparison of trees via tree_cmp

[Alexander Monakov]

On Wed, 22 Jan 2020, Stefan Schulze Frielinghaus wrote:

> 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?

It's more appropriate to fix the assert rather than the comparator, like

  gcc_assert (sign (reversed) == -sign (result));

But qsort_chk already checks that, and more, so why is the assert there?
Shouldn't it be simply removed?

Alexander

Re: [PATCH] Fix comparison of trees via tree_cmp

[Jakub Jelinek]

On Wed, Jan 22, 2020 at 08:08:32PM +0300, Alexander Monakov wrote:
> 
> 
> On Wed, 22 Jan 2020, Stefan Schulze Frielinghaus wrote:
> 
> > 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?
> 
> It's more appropriate to fix the assert rather than the comparator, like
> 
>   gcc_assert (sign (reversed) == -sign (result));
> 
> But qsort_chk already checks that, and more, so why is the assert there?
> Shouldn't it be simply removed?

Yeah.  Note there is also return DECL_UID (t1) - DECL_UID (t2); that also
doesn't guarantee -1/0/1 return values, so the patch as posted isn't
sufficient.

	Jakub

Re: [PATCH] Fix comparison of trees via tree_cmp

[David Malcolm]

On Wed, 2020-01-22 at 19:02 +0100, Jakub Jelinek wrote:
> On Wed, Jan 22, 2020 at 08:08:32PM +0300, Alexander Monakov wrote:
> > 
> > On Wed, 22 Jan 2020, Stefan Schulze Frielinghaus wrote:
> > 
> > > 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?
> > 
> > It's more appropriate to fix the assert rather than the comparator,
> > like
> > 
> >   gcc_assert (sign (reversed) == -sign (result));
> > 
> > But qsort_chk already checks that, and more, so why is the assert
> > there?
> > Shouldn't it be simply removed?
> 
> Yeah.  Note there is also return DECL_UID (t1) - DECL_UID (t2); that
> also
> doesn't guarantee -1/0/1 return values, so the patch as posted isn't
> sufficient.

Sorry about the breakage; to be specific, I've reproduced this on
s390x-ibm-linux-gnu, where it fails the selftests in stage 1, breaking
the build (unless configured with --disable-analyzer).

Removing the assertions fixes it for me (a stage1 build, at least, and
it then passes the testsuite).

I've made this blunder in four places in the analyzer:

  call-string.cc:162:  call_string::cmp
  engine.cc:1820:  worklist::key_t::cmp
  program-point.cc:461:  function_point::cmp_within_supernode
  region-model.cc:1878:  tree_cmp

IIRC, I added these checks as I was finding it difficult to debug
things when qsort_chk failed - the first three of the comparators in
the list above build on each other:  worklist::key_t::cmp uses both
function_point::cmp_within_supernode and call_string::cmp (and various
other things), so if the worklist qsort_chk fails, it sometimes
required a fair bit of digging into which of the nested comparators had
failed (also, all the void * don't help; I'd love to have a template
that does a typesafe qsort without needing casts in the comparator).

Some approaches for fixing this:
(a) I can simply remove these checks on all the comparators
(b) I could fix the checks so that they merely look at the signedness
of the results
(c) Remove the checks from tree_cmp, but retain them in the other
places, fixing them to just look at signedness, for ease of debugging.

I think I prefer (c) as it makes debugging failures easier, though I
appreciate it's rather redundant.

Thoughts?

Dave

Re: [PATCH] Fix comparison of trees via tree_cmp

[Alexander Monakov]

On Thu, 23 Jan 2020, David Malcolm wrote:

> Removing the assertions fixes it for me (a stage1 build, at least, and
> it then passes the testsuite).
> 
> I've made this blunder in four places in the analyzer:
> 
>   call-string.cc:162:  call_string::cmp
>   program-point.cc:461:  function_point::cmp_within_supernode

These two don't raise concerns on brief inspection.

>   engine.cc:1820:  worklist::key_t::cmp

This one tries to use signed difference of hashes as return value, this is
not going to work in general while passing your assert almost always (except
when difference of hashes is exactly -2^31). The problem is, difference of
hashes leads to non-transitive comparison and qsort_chk can catch it on a
suitable testcase.

>   region-model.cc:1878:  tree_cmp

This is the one under discussion here.

> IIRC, I added these checks as I was finding it difficult to debug
> things when qsort_chk failed - the first three of the comparators in
> the list above build on each other:  worklist::key_t::cmp uses both
> function_point::cmp_within_supernode and call_string::cmp (and various
> other things), so if the worklist qsort_chk fails, it sometimes
> required a fair bit of digging into which of the nested comparators had
> failed (also, all the void * don't help; I'd love to have a template
> that does a typesafe qsort without needing casts in the comparator).

FWIW qsort_chk_error is a separate function to make that easier: if you place a
breakpoint on qsort_chk_error you just need to step a few times to get into a
comparator that is under suspicion, and don't need to type out casts in gdb.

Alexander

[PATCH] analyzer: fixes to tree_cmp and other comparators

[David Malcolm]

On Thu, 2020-01-23 at 18:46 +0300, Alexander Monakov wrote:
> On Thu, 23 Jan 2020, David Malcolm wrote:
> 
> > Removing the assertions fixes it for me (a stage1 build, at least,
> > and
> > it then passes the testsuite).
> > 
> > I've made this blunder in four places in the analyzer:
> > 
> >   call-string.cc:162:  call_string::cmp
> >   program-point.cc:461:  function_point::cmp_within_supernode
> 
> These two don't raise concerns on brief inspection.
> 
> >   engine.cc:1820:  worklist::key_t::cmp
> 
> This one tries to use signed difference of hashes as return value,
> this is
> not going to work in general while passing your assert almost always
> (except
> when difference of hashes is exactly -2^31). The problem is,
> difference of
> hashes leads to non-transitive comparison and qsort_chk can catch it
> on a
> suitable testcase.
> 
> >   region-model.cc:1878:  tree_cmp
> 
> This is the one under discussion here.
> 
> > IIRC, I added these checks as I was finding it difficult to debug
> > things when qsort_chk failed - the first three of the comparators
> > in
> > the list above build on each other:  worklist::key_t::cmp uses both
> > function_point::cmp_within_supernode and call_string::cmp (and
> > various
> > other things), so if the worklist qsort_chk fails, it sometimes
> > required a fair bit of digging into which of the nested comparators
> > had
> > failed (also, all the void * don't help; I'd love to have a
> > template
> > that does a typesafe qsort without needing casts in the
> > comparator).
> 
> FWIW qsort_chk_error is a separate function to make that easier: if
> you place a
> breakpoint on qsort_chk_error you just need to step a few times to
> get into a
> comparator that is under suspicion, and don't need to type out casts
> in gdb.
> 
> Alexander

Thanks - that makes much more sense to me now.

How does the following patch look:

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.

Fixes build on s390x-ibm-linux-gnu for stage 1, at least, with no
testsuite regressions.  Full bootstrap and regression test run
in progress.

OK for master if it passes?

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.
---
 gcc/analyzer/call-string.cc   | 23 +----------------------
 gcc/analyzer/call-string.h    |  3 ---
 gcc/analyzer/engine.cc        | 35 +++++++----------------------------
 gcc/analyzer/exploded-graph.h |  1 -
 gcc/analyzer/region-model.cc  | 16 +---------------
 5 files changed, 9 insertions(+), 69 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.  */
@@ -156,28 +157,6 @@ call_string::calc_recursion_depth () const
 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 ();
diff --git a/gcc/analyzer/call-string.h b/gcc/analyzer/call-string.h
index 5e362d8cadb..1b5db0a4a20 100644
--- a/gcc/analyzer/call-string.h
+++ b/gcc/analyzer/call-string.h
@@ -69,9 +69,6 @@ public:
   void validate () const;
 
 private:
-  static int cmp_1 (const call_string &a,
-		    const call_string &b);
-
   auto_vec<const return_superedge *> m_return_edges;
 };
 
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 1fdedf49224..939401140e7 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -1634,7 +1634,7 @@ worklist::add_node (exploded_node *enode)
    Return 0 if they are equal.  */
 
 int
-worklist::key_t::cmp_1 (const worklist::key_t &ka, const worklist::key_t &kb)
+worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb)
 {
   const program_point &point_a = ka.m_enode->get_point ();
   const program_point &point_b = kb.m_enode->get_point ();
@@ -1710,9 +1710,12 @@ worklist::key_t::cmp_1 (const worklist::key_t &ka, const worklist::key_t &kb)
       sm_state_map *smap_a = state_a.m_checker_states[sm_idx];
       sm_state_map *smap_b = state_b.m_checker_states[sm_idx];
 
-      int sm_cmp = smap_a->hash () - smap_b->hash ();
-      if (sm_cmp)
-	return sm_cmp;
+      hashval_t hash_a = smap_a->hash ();
+      hashval_t hash_b = smap_b->hash ();
+      if (hash_a < hash_b)
+	return -1;
+      else if (hash_a > hash_b)
+	return 1;
     }
 
   /* Otherwise, we have two enodes at the same program point but with
@@ -1722,30 +1725,6 @@ worklist::key_t::cmp_1 (const worklist::key_t &ka, const worklist::key_t &kb)
   return ka.m_enode->m_index - kb.m_enode->m_index;
 }
 
-/* Comparator for implementing worklist::key_t comparison operators.
-   Return negative if KA is before KB
-   Return positive if KA is after KB
-   Return 0 if they are equal.  */
-
-int
-worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb)
-{
-  int result = cmp_1 (ka, kb);
-
-  /* Check that the ordering is symmetric  */
-#if CHECKING_P
-  int reversed = cmp_1 (kb, ka);
-  gcc_assert (reversed == -result);
-#endif
-
-  /* We should only have 0 for equal (point, state) pairs.  */
-  gcc_assert (result != 0
-	      || (*ka.m_enode->get_ps_key ()
-		  == *kb.m_enode->get_ps_key ()));
-
-  return result;
-}
-
 /* exploded_graph's ctor.  */
 
 exploded_graph::exploded_graph (const supergraph &sg, logger *logger,
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index a3e758ed751..c72319cb5c1 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -652,7 +652,6 @@ private:
     }
 
   private:
-    static int cmp_1 (const key_t &ka, const key_t &kb);
     static int cmp (const key_t &ka, const key_t &kb);
 
     int get_scc_id (const exploded_node *enode) const
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 985f1bd56ac..a986549b597 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -1843,21 +1843,7 @@ tree_cmp (const void *p1, const void *p2)
   const_tree t1 = *(const_tree const *)p1;
   const_tree t2 = *(const_tree const *)p2;
 
-  int result = tree_cmp (t1, t2);
-
-  /* Check that the ordering is symmetric  */
-#if CHECKING_P
-  int reversed = tree_cmp (t2, t1);
-  gcc_assert (reversed == -result);
-#endif
-
-  /* We should only have 0 for equal pairs.  */
-#if 0
-  gcc_assert (result != 0
-	      || t1 == t2);
-#endif
-
-  return result;
+  return tree_cmp (t1, t2);
 }
 
 /* Attempt to merge MAP_REGION_A and MAP_REGION_B into MERGED_MAP_REGION,
-- 
2.21.0

Re: [PATCH] analyzer: fixes to tree_cmp and other comparators

[Stefan Schulze Frielinghaus]

On Thu, Jan 23, 2020 at 05:13:20PM -0500, David Malcolm wrote:
[...]
> 
> Fixes build on s390x-ibm-linux-gnu for stage 1, at least, with no
> testsuite regressions.  Full bootstrap and regression test run
> in progress.

Thank you for taking care of this! With your new patch I can
successfully bootstrap + regtest.

Cheers,
Stefan

Re: [PATCH] analyzer: fixes to tree_cmp and other comparators

[David Malcolm]

On Fri, 2020-01-24 at 11:16 +0100, Stefan Schulze Frielinghaus wrote:
> On Thu, Jan 23, 2020 at 05:13:20PM -0500, David Malcolm wrote:
> [...]
> > Fixes build on s390x-ibm-linux-gnu for stage 1, at least, with no
> > testsuite regressions.  Full bootstrap and regression test run
> > in progress.
> 
> Thank you for taking care of this! With your new patch I can
> successfully bootstrap + regtest.

Thanks.  I've committed this to master as
6a81cabc14426b642271647b03218a3af19d600f.