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.

1 files changed, 57 insertions, 0 deletions

diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 2313a66..6a91554 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.  */