analyzer: fixes to tree_cmp and other comparators
authorDavid Malcolm <dmalcolm@redhat.com>
Thu, 23 Jan 2020 21:33:13 +0000 (16:33 -0500)
committerDavid Malcolm <dmalcolm@redhat.com>
Mon, 27 Jan 2020 15:18:42 +0000 (10:18 -0500)
commit6a81cabc14426b642271647b03218a3af19d600f
tree56549e78861b12a7d50dee21f9c65dfdfffcc69d
parentc15893df6eafc32efd6184379dd7f02c36da7d12
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.
gcc/analyzer/ChangeLog
gcc/analyzer/call-string.cc
gcc/analyzer/call-string.h
gcc/analyzer/engine.cc
gcc/analyzer/exploded-graph.h
gcc/analyzer/region-model.cc