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
