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
