From 6a81cabc14426b642271647b03218a3af19d600f Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Thu, 23 Jan 2020 16:33:13 -0500 Subject: [PATCH] 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 | 12 ++++++++++++ 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 +--------------- 6 files changed, 21 insertions(+), 69 deletions(-) diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog index 345d40f3faf..4a99c3f12a7 100644 --- a/gcc/analyzer/ChangeLog +++ b/gcc/analyzer/ChangeLog @@ -1,3 +1,15 @@ +2020-01-27 David Malcolm + + * 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. + 2020-01-27 David Malcolm * analyzer.cc (is_named_call_p): Check that fndecl is "extern" 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 m_return_edges; }; diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index b39058f9c10..8961c557c49 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.30.2