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, 6 insertions, 0 deletions

diff --git a/gcc/analyzer/store.h b/gcc/analyzer/store.h
index 0f4e7ab..466c183 100644
--- a/gcc/analyzer/store.h
+++ b/gcc/analyzer/store.h
@@ -237,6 +237,8 @@ public:
 
   bool overlaps_p (const concrete_binding &other) const;
 
+  static int cmp_ptr_ptr (const void *, const void *);
+
 private:
   bit_offset_t m_start_bit_offset;
   bit_size_t m_size_in_bits;
@@ -282,6 +284,8 @@ public:
 
   const region *get_region () const { return m_region; }
 
+  static int cmp_ptr_ptr (const void *, const void *);
+
 private:
   const region *m_region;
 };
@@ -346,6 +350,8 @@ public:
   bool apply_ctor_to_region (const region *parent_reg, tree ctor,
 			     region_model_manager *mgr);
 
+  static int cmp (const binding_map &map1, const binding_map &map2);
+
 private:
   bool apply_ctor_val_to_range (const region *parent_reg,
 				region_model_manager *mgr,