analyzer: eliminate non-determinism in logs

This patch and the followup eliminate various forms of non-determinism
in the analyzer due to changing pointer values.

This patch fixes churn seen when diffing analyzer logs.  The patch
avoids embedding pointers in various places, and adds sorting when
dumping hash_set and hash_map for various analyzer types.  Doing so
requires implementing a way to sort svalue instances, and assigning UIDs
to gimple statements.

Tested both patches together via a script that runs a testcase 100 times,
and then using diff and md5sum to verify that the results are consistent
in the face of address space randomization:

FILENAME=$1
rm $FILENAME.*
for i in `seq 1 100`; do
    echo "iteration: $i"
    ./xgcc -B. -fanalyzer -c ../../src/gcc/testsuite/gcc.dg/analyzer/$FILENAME \
       --Wanalyzer-too-complex \
       -fdump-analyzer-supergraph \
       -fdump-analyzer-exploded-graph \
       -fdump-analyzer \
       -fdump-noaddr \
       -fdump-analyzer-exploded-nodes-2
    mv $FILENAME.supergraph.dot $FILENAME.$i.supergraph.dot
    mv $FILENAME.analyzer.txt $FILENAME.$i.analyzer.txt
    mv $FILENAME.supergraph-eg.dot $FILENAME.$i.supergraph-eg.dot
    mv $FILENAME.eg.txt $FILENAME.$i.eg.txt
    mv $FILENAME.eg.dot $FILENAME.$i.eg.dot
done

gcc/analyzer/ChangeLog:
	* engine.cc (setjmp_record::cmp): New.
	(supernode_cluster::dump_dot): Avoid embedding pointer in cluster
	name.
	(supernode_cluster::cmp_ptr_ptr): New.
	(function_call_string_cluster::dump_dot): Avoid embedding pointer
	in cluster name.  Sort m_map when dumping child clusters.
	(function_call_string_cluster::cmp_ptr_ptr): New.
	(root_cluster::dump_dot): Sort m_map when dumping child clusters.
	* program-point.cc (function_point::cmp): New.
	(function_point::cmp_ptr): New.
	* program-point.h (function_point::cmp): New decl.
	(function_point::cmp_ptr): New decl.
	* program-state.cc (sm_state_map::print): Sort the values.  Guard
	the printing of pointers with !flag_dump_noaddr.
	(program_state::prune_for_point): Sort the regions.
	(log_set_of_svalues): Sort the values.  Guard the printing of
	pointers with !flag_dump_noaddr.
	* region-model-manager.cc (log_uniq_map): Sort the values.
	* region-model-reachability.cc (dump_set): New function template.
	(reachable_regions::dump_to_pp): Use it.
	* region-model.h (svalue::cmp_ptr): New decl.
	(svalue::cmp_ptr_ptr): New decl.
	(setjmp_record::cmp): New decl.
	(placeholder_svalue::get_name): New accessor.
	(widening_svalue::get_point): New accessor.
	(compound_svalue::get_map): New accessor.
	(conjured_svalue::get_stmt): New accessor.
	(conjured_svalue::get_id_region): New accessor.
	(region::cmp_ptrs): Rename to...
	(region::cmp_ptr_ptr): ...this.
	* region.cc (region::cmp_ptrs): Rename to...
	(region::cmp_ptr_ptr): ...this.
	* state-purge.cc
	(state_purge_per_ssa_name::state_purge_per_ssa_name): Sort
	m_points_needing_name when dumping.
	* store.cc (concrete_binding::cmp_ptr_ptr): New.
	(symbolic_binding::cmp_ptr_ptr): New.
	(binding_map::cmp): New.
	(get_sorted_parent_regions): Update for renaming of
	region::cmp_ptrs to region::cmp_ptr_ptr.
	(store::dump_to_pp): Likewise.
	(store::to_json): Likewise.
	(store::can_merge_p): Sort the base regions before considering
	them.
	* store.h (concrete_binding::cmp_ptr_ptr): New decl.
	(symbolic_binding::cmp_ptr_ptr): New decl.
	(binding_map::cmp): New decl.
	* supergraph.cc (supergraph::supergraph): Assign UIDs to the
	gimple stmts.
	* svalue.cc (cmp_cst): New.
	(svalue::cmp_ptr): New.
	(svalue::cmp_ptr_ptr): New.

1 files changed, 30 insertions, 28 deletions

diff --git a/gcc/analyzer/region-model-reachability.cc b/gcc/analyzer/region-model-reachability.cc
index 3a6b312..52525e1 100644
--- a/gcc/analyzer/region-model-reachability.cc
+++ b/gcc/analyzer/region-model-reachability.cc
@@ -227,6 +227,29 @@ reachable_regions::mark_escaped_clusters (region_model_context *ctxt)
     }
 }
 
+/* Dump SET to PP, sorting it to avoid churn when comparing dumps.  */
+
+template <typename T>
+static void
+dump_set (const hash_set<const T *> &set, pretty_printer *pp)
+{
+  auto_vec<const T *> elements (set.elements ());
+  for (typename hash_set<const T *>::iterator iter = set.begin ();
+       iter != set.end (); ++iter)
+    elements.quick_push (*iter);
+
+  elements.qsort (T::cmp_ptr_ptr);
+
+  unsigned i;
+  const T *element;
+  FOR_EACH_VEC_ELT (elements, i, element)
+    {
+      pp_string (pp, "  ");
+      element->dump_to_pp (pp, true);
+      pp_newline (pp);
+    }
+}
+
 /* Dump a multiline representation of this object to PP.  */
 
 void
@@ -234,40 +257,19 @@ reachable_regions::dump_to_pp (pretty_printer *pp) const
 {
   pp_string (pp, "reachable clusters: ");
   pp_newline (pp);
-  for (hash_set<const region *>::iterator iter = m_reachable_base_regs.begin ();
-       iter != m_reachable_base_regs.end (); ++iter)
-    {
-      pp_string (pp, "  ");
-      (*iter)->dump_to_pp (pp, true);
-      pp_newline (pp);
-    }
+  dump_set (m_reachable_base_regs, pp);
+
   pp_string (pp, "mutable clusters: ");
   pp_newline (pp);
-  for (hash_set<const region *>::iterator iter = m_mutable_base_regs.begin ();
-       iter != m_mutable_base_regs.end (); ++iter)
-    {
-      pp_string (pp, "  ");
-      (*iter)->dump_to_pp (pp, true);
-      pp_newline (pp);
-    }
+  dump_set (m_mutable_base_regs, pp);
+
   pp_string (pp, "reachable svals: ");
   pp_newline (pp);
-  for (svalue_set::iterator iter = m_reachable_svals.begin ();
-       iter != m_reachable_svals.end (); ++iter)
-    {
-      pp_string (pp, "  ");
-      (*iter)->dump_to_pp (pp, true);
-      pp_newline (pp);
-    }
+  dump_set (m_reachable_svals, pp);
+
   pp_string (pp, "mutable svals: ");
   pp_newline (pp);
-  for (svalue_set::iterator iter = m_mutable_svals.begin ();
-       iter != m_mutable_svals.end (); ++iter)
-    {
-      pp_string (pp, "  ");
-      (*iter)->dump_to_pp (pp, true);
-      pp_newline (pp);
-    }
+  dump_set (m_mutable_svals, pp);
 }
 
 /* Dump a multiline representation of this object to stderr.  */