[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