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.
Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
Pushed to master as bf1b5dae440de8884f66d0dbe9ad539102682e00.
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 <const svalue *> 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 <const svalue *> 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 <map_t &> (smap_a.m_map).get (sval_a);
+ const entry_t *e_b = const_cast <map_t &> (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.26.2
