From bf1b5dae440de8884f66d0dbe9ad539102682e00 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Tue, 27 Oct 2020 09:52:00 -0400 Subject: [PATCH] analyzer: eliminate non-deterministic behavior This patch is a followup to the previous one, eliminating non-determinism in the behavior of the analyzer (rather than just in the logs), by sorting whenever the result previously depended on pointer values. Tested as per the previous patch. gcc/analyzer/ChangeLog: * constraint-manager.cc (svalue_cmp_by_ptr): Delete. (equiv_class::canonicalize): Use svalue::cmp_ptr_ptr instead. (equiv_class_cmp): Eliminate pointer comparison. * diagnostic-manager.cc (dedupe_key::comparator): If they are at the same location, also compare epath ength and pending_diagnostic kind. * engine.cc (readability_comparator): If two path_vars have the same readability, then impose an arbitrary ordering on them. (worklist::key_t::cmp): If two points have the same plan ordering, continue the comparison. Call sm_state_map::cmp rather than comparing hash values. * program-state.cc (sm_state_map::entry_t::cmp): New. (sm_state_map::cmp): New. * program-state.h (sm_state_map::entry_t::cmp): New decl. (sm_state_map::elements): New. (sm_state_map::cmp): New. --- gcc/analyzer/constraint-manager.cc | 22 ++---------- gcc/analyzer/diagnostic-manager.cc | 10 +++++- gcc/analyzer/engine.cc | 39 ++++++++++++++------ gcc/analyzer/program-state.cc | 57 ++++++++++++++++++++++++++++++ gcc/analyzer/program-state.h | 5 +++ 5 files changed, 102 insertions(+), 31 deletions(-) diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc index 603b22811c1..2978f1b212d 100644 --- a/gcc/analyzer/constraint-manager.cc +++ b/gcc/analyzer/constraint-manager.cc @@ -423,26 +423,12 @@ equiv_class::get_representative () const return m_vars[0]; } -/* Comparator for use by equiv_class::canonicalize. */ - -static int -svalue_cmp_by_ptr (const void *p1, const void *p2) -{ - const svalue *sval1 = *(const svalue * const *)p1; - const svalue *sval2 = *(const svalue * const *)p2; - if (sval1 < sval2) - return 1; - if (sval1 > sval2) - return -1; - return 0; -} - /* Sort the svalues within this equiv_class. */ void equiv_class::canonicalize () { - m_vars.qsort (svalue_cmp_by_ptr); + m_vars.qsort (svalue::cmp_ptr_ptr); } /* Get a debug string for C_OP. */ @@ -1693,11 +1679,7 @@ equiv_class_cmp (const void *p1, const void *p2) gcc_assert (rep1); gcc_assert (rep2); - if (rep1 < rep2) - return 1; - if (rep1 > rep2) - return -1; - return 0; + return svalue::cmp_ptr (rep1, rep2); } /* Comparator for use by constraint_manager::canonicalize. diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc index cb95a95ff0b..93f270f7c2c 100644 --- a/gcc/analyzer/diagnostic-manager.cc +++ b/gcc/analyzer/diagnostic-manager.cc @@ -318,7 +318,15 @@ public: location_t loc1 = pk1->get_location (); location_t loc2 = pk2->get_location (); - return linemap_compare_locations (line_table, loc2, loc1); + if (int cmp = linemap_compare_locations (line_table, loc2, loc1)) + return cmp; + if (int cmp = ((int)pk1->m_sd.get_epath_length () + - (int)pk2->m_sd.get_epath_length ())) + return cmp; + if (int cmp = strcmp (pk1->m_sd.m_d->get_kind (), + pk2->m_sd.m_d->get_kind ())) + return cmp; + return 0; } const saved_diagnostic &m_sd; diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index 49cd33e94da..d247ebbc20e 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -517,6 +517,29 @@ readability_comparator (const void *p1, const void *p2) if (int cmp = pv2.m_stack_depth - pv1.m_stack_depth) return cmp; + /* Otherwise, if they have the same readability, then impose an + arbitrary deterministic ordering on them. */ + + if (int cmp = TREE_CODE (pv1.m_tree) - TREE_CODE (pv2.m_tree)) + return cmp; + + switch (TREE_CODE (pv1.m_tree)) + { + default: + break; + case SSA_NAME: + if (int cmp = (SSA_NAME_VERSION (pv1.m_tree) + - SSA_NAME_VERSION (pv2.m_tree))) + return cmp; + break; + case PARM_DECL: + case VAR_DECL: + case RESULT_DECL: + if (int cmp = DECL_UID (pv1.m_tree) - DECL_UID (pv2.m_tree)) + return cmp; + break; + } + /* TODO: We ought to find ways of sorting such cases. */ return 0; } @@ -1824,8 +1847,9 @@ worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb) && point_b.get_function () != NULL && point_a.get_function () != point_b.get_function ()) { - return ka.m_worklist.m_plan.cmp_function (point_a.get_function (), - point_b.get_function ()); + if (int cmp = ka.m_worklist.m_plan.cmp_function (point_a.get_function (), + point_b.get_function ())) + return cmp; } /* First, order by SCC. */ @@ -1876,20 +1900,15 @@ worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb) const program_state &state_b = kb.m_enode->get_state (); /* Sort by sm-state, so that identical sm-states are grouped - together in the worklist. - For now, sort by the hash value (might not be deterministic). */ + together in the worklist. */ for (unsigned sm_idx = 0; sm_idx < state_a.m_checker_states.length (); ++sm_idx) { sm_state_map *smap_a = state_a.m_checker_states[sm_idx]; sm_state_map *smap_b = state_b.m_checker_states[sm_idx]; - 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; + if (int smap_cmp = sm_state_map::cmp (*smap_a, *smap_b)) + return smap_cmp; } /* Otherwise, we have two enodes at the same program point but with diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc index 2313a662e36..6a91554357c 100644 --- a/gcc/analyzer/program-state.cc +++ b/gcc/analyzer/program-state.cc @@ -131,6 +131,25 @@ extrinsic_state::get_model_manager () const return NULL; /* for selftests. */ } +/* struct sm_state_map::entry_t. */ + +int +sm_state_map::entry_t::cmp (const entry_t &entry_a, const entry_t &entry_b) +{ + gcc_assert (entry_a.m_state); + gcc_assert (entry_b.m_state); + if (int cmp_state = ((int)entry_a.m_state->get_id () + - (int)entry_b.m_state->get_id ())) + return cmp_state; + if (entry_a.m_origin && entry_b.m_origin) + return svalue::cmp_ptr (entry_a.m_origin, entry_b.m_origin); + if (entry_a.m_origin) + return 1; + if (entry_b.m_origin) + return -1; + return 0; +} + /* class sm_state_map. */ /* sm_state_map's ctor. */ @@ -553,6 +572,44 @@ sm_state_map::on_unknown_change (const svalue *sval, impl_set_state (*iter, (state_machine::state_t)0, NULL, ext_state); } +/* Comparator for imposing an order on sm_state_map instances. */ + +int +sm_state_map::cmp (const sm_state_map &smap_a, const sm_state_map &smap_b) +{ + if (int cmp_count = smap_a.elements () - smap_b.elements ()) + return cmp_count; + + auto_vec keys_a (smap_a.elements ()); + for (map_t::iterator iter = smap_a.begin (); + iter != smap_a.end (); + ++iter) + keys_a.quick_push ((*iter).first); + keys_a.qsort (svalue::cmp_ptr_ptr); + + auto_vec keys_b (smap_b.elements ()); + for (map_t::iterator iter = smap_b.begin (); + iter != smap_b.end (); + ++iter) + keys_b.quick_push ((*iter).first); + keys_b.qsort (svalue::cmp_ptr_ptr); + + unsigned i; + const svalue *sval_a; + FOR_EACH_VEC_ELT (keys_a, i, sval_a) + { + const svalue *sval_b = keys_b[i]; + if (int cmp_sval = svalue::cmp_ptr (sval_a, sval_b)) + return cmp_sval; + const entry_t *e_a = const_cast (smap_a.m_map).get (sval_a); + const entry_t *e_b = const_cast (smap_b.m_map).get (sval_b); + if (int cmp_entry = entry_t::cmp (*e_a, *e_b)) + return cmp_entry; + } + + return 0; +} + /* Canonicalize SVAL before getting/setting it within the map. Convert all NULL pointers to (void *) to avoid state explosions involving all of the various (foo *)NULL vs (bar *)NULL. */ diff --git a/gcc/analyzer/program-state.h b/gcc/analyzer/program-state.h index 094d2562656..c44fc948864 100644 --- a/gcc/analyzer/program-state.h +++ b/gcc/analyzer/program-state.h @@ -96,6 +96,8 @@ public: return !(*this == other); } + static int cmp (const entry_t &entry_a, const entry_t &entry_b); + state_machine::state_t m_state; const svalue *m_origin; }; @@ -157,6 +159,9 @@ public: iterator_t begin () const { return m_map.begin (); } iterator_t end () const { return m_map.end (); } + size_t elements () const { return m_map.elements (); } + + static int cmp (const sm_state_map &smap_a, const sm_state_map &smap_b); static const svalue * canonicalize_svalue (const svalue *sval, const extrinsic_state &ext_state); -- 2.30.2