From b0702ac5588333e27d7ec43d21d704521f7a05c6 Mon Sep 17 00:00:00 2001
From: David Malcolm <dmalcolm@redhat.com>
Date: Tue, 27 Oct 2020 09:51:19 -0400
Subject: 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.
---
 gcc/analyzer/program-point.h | 3 +++
 1 file changed, 3 insertions(+)

(limited to 'gcc/analyzer/program-point.h')

diff --git a/gcc/analyzer/program-point.h b/gcc/analyzer/program-point.h
index d804621..2d1c3ab 100644
--- a/gcc/analyzer/program-point.h
+++ b/gcc/analyzer/program-point.h
@@ -138,6 +138,9 @@ public:
 				     const function_point &point_b);
   static int cmp_within_supernode (const function_point &point_a,
 				   const function_point &point_b);
+  static int cmp (const function_point &point_a,
+		  const function_point &point_b);
+  static int cmp_ptr (const void *p1, const void *p2);
 
   /* For before_stmt, go to next stmt.  */
   void next_stmt ();
-- 
cgit v1.1