analyzer: add enode status and revamp __analyzer_dump_exploded_nodes

The analyzer recognizes __analyzer_dump_exploded_nodes as a "magic"
function for use in DejaGnu tests: at the end of the pass, it issues
a warning at each such call, dumping the count of exploded nodes seen at
the call, which can be checked in test cases via dg-warning directives,
along with the IDs of the enodes (which is helpful when debugging).

My intent was to give a way of testing the results of the state-merging
code.

The state-merging code can generate duplicate exploded nodes at a point
when state merging occurs, taking a pair of enodes from the worklist
that share a program_point and sufficiently similar state.  For these
cases it generates a merged state, and adds edges from those enodes to
the merged-state enode (potentially a new or a pre-existing enode); the
input enodes don't have process_node called on them.

This means that at a CFG join point there can be an unpredictable number
of enodes that we don't care about, where the precise number depends on
the details of the state-merger code, immediately followed by a more
predictable number that we do care about.

I've been papering over this in the analyzer DejaGnu tests somewhat
by adding pairs of __analyzer_dump_exploded_nodes calls at CFG join
points, where the output at the first call is somewhat arbitrary, and
the second has the number we care about; the first number tends to
change "at random" as I tweak the state merging code, in ways that
aren't interesting, but require the tests to be updated.

See e.g. gcc.dg/analyzer/paths-6.c which had:

  __analyzer_dump_exploded_nodes (0); /* { dg-warning "2 exploded nodes" } */
  // FIXME: the above can vary between 2 and 3 exploded nodes
  __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 exploded node" } */

This patch remedies this situation by tracking which enodes are
processed, and which are merely "merger" enodes.  It updates the
output for __analyzer_dump_exploded_nodes so that count of enodes
only includes the *processed* enodes, and that the IDs are split
into "processed" and "merger" enodes.

The patch simplifies the testsuite by eliminating the redundant calls
described above; the example above becomes:

  __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */

where the output in question is now:

  warning: 1 processed enode: [EN: 94] merger(s): [EN: 93]

The patch also adds various checks on the status of enodes, to ensure
e.g. that each enode is processed at most once.

gcc/analyzer/ChangeLog:
	* engine.cc (exploded_node::dump_dot): Show merger enodes.
	(worklist::add_node): Assert that the node's m_status is
	STATUS_WORKLIST.
	(exploded_graph::process_worklist): Likewise for nodes from the
	worklist.  Set status of merged nodes to STATUS_MERGER.
	(exploded_graph::process_node): Set status of node to
	STATUS_PROCESSED.
	(exploded_graph::dump_exploded_nodes): Rework handling of
	"__analyzer_dump_exploded_nodes", splitting enodes by status into
	"processed" and "merger", showing the count of just the processed
	enodes at the call, rather than the count of all enodes.
	* exploded-graph.h (exploded_node::status): New enum.
	(exploded_node::exploded_node): Initialize m_status to
	STATUS_WORKLIST.
	(exploded_node::get_status): New getter.
	(exploded_node::set_status): New setter.
	(exploded_node::m_status): New field.

gcc/ChangeLog:
	* doc/analyzer.texi
	(Special Functions for Debugging the Analyzer): Update description
	of __analyzer_dump_exploded_nodes.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/data-model-1.c: Update for changed output to
	__analyzer_dump_exploded_nodes, dropping redundant call at merger.
	* gcc.dg/analyzer/data-model-7.c: Likewise.
	* gcc.dg/analyzer/loop-2.c: Update for changed output format.
	* gcc.dg/analyzer/loop-2a.c: Likewise.
	* gcc.dg/analyzer/loop-4.c: Likewise.
	* gcc.dg/analyzer/loop.c: Likewise.
	* gcc.dg/analyzer/malloc-paths-10.c: Likewise; drop redundant
	call at merger.
	* gcc.dg/analyzer/malloc-vs-local-1a.c: Likewise.
	* gcc.dg/analyzer/malloc-vs-local-1b.c: Likewise.
	* gcc.dg/analyzer/malloc-vs-local-2.c: Likewise.
	* gcc.dg/analyzer/malloc-vs-local-3.c: Likewise.
	* gcc.dg/analyzer/paths-1.c: Likewise.
	* gcc.dg/analyzer/paths-1a.c: Likewise.
	* gcc.dg/analyzer/paths-2.c: Likewise.
	* gcc.dg/analyzer/paths-3.c: Likewise.
	* gcc.dg/analyzer/paths-4.c: Update for changed output format.
	* gcc.dg/analyzer/paths-5.c: Likewise.
	* gcc.dg/analyzer/paths-6.c: Likewise; drop redundant calls
	at merger.
	* gcc.dg/analyzer/paths-7.c: Likewise.
	* gcc.dg/analyzer/torture/conditionals-2.c: Update for changed
	output format.
	* gcc.dg/analyzer/zlib-1.c: Likewise; drop redundant calls.
	* gcc.dg/analyzer/zlib-5.c: Update for changed output format.

3 files changed, 102 insertions, 14 deletions

diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog
index 8089280..0666d00 100644
--- a/gcc/analyzer/ChangeLog
+++ b/gcc/analyzer/ChangeLog
@@ -1,3 +1,22 @@
+2020-02-05  David Malcolm  <dmalcolm@redhat.com>
+
+	* engine.cc (exploded_node::dump_dot): Show merger enodes.
+	(worklist::add_node): Assert that the node's m_status is
+	STATUS_WORKLIST.
+	(exploded_graph::process_worklist): Likewise for nodes from the
+	worklist.  Set status of merged nodes to STATUS_MERGER.
+	(exploded_graph::process_node): Set status of node to
+	STATUS_PROCESSED.
+	(exploded_graph::dump_exploded_nodes): Rework handling of
+	"__analyzer_dump_exploded_nodes", splitting enodes by status into
+	"processed" and "merger", showing the count of just the processed
+	enodes at the call, rather than the count of all enodes.
+	* exploded-graph.h (exploded_node::status): New enum.
+	(exploded_node::exploded_node): Initialize m_status to
+	STATUS_WORKLIST.
+	(exploded_node::get_status): New getter.
+	(exploded_node::set_status): New setter.
+
 2020-02-04  David Malcolm  <dmalcolm@redhat.com>
 
 	PR analyzer/93543
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 81b8a76..63579da 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -827,6 +827,8 @@ exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const
   pp_write_text_to_stream (pp);
 
   pp_printf (pp, "EN: %i", m_index);
+  if (m_status == STATUS_MERGER)
+    pp_string (pp, " (merger)");
   pp_newline (pp);
 
   format f (true);
@@ -1638,6 +1640,7 @@ worklist::peek_next ()
 void
 worklist::add_node (exploded_node *enode)
 {
+  gcc_assert (enode->get_status () == exploded_node::STATUS_WORKLIST);
   m_queue.insert (key_t (*this, enode), enode);
 }
 
@@ -2124,6 +2127,7 @@ exploded_graph::process_worklist ()
   while (m_worklist.length () > 0)
     {
       exploded_node *node = m_worklist.take_next ();
+      gcc_assert (node->get_status () == exploded_node::STATUS_WORKLIST);
       gcc_assert (node->m_succs.length () == 0
 		  || node == m_origin);
 
@@ -2136,6 +2140,8 @@ exploded_graph::process_worklist ()
       if (flag_analyzer_state_merge && node != m_origin)
 	if (exploded_node *node_2 = m_worklist.peek_next ())
 	  {
+	    gcc_assert (node_2->get_status ()
+			== exploded_node::STATUS_WORKLIST);
 	    gcc_assert (node->m_succs.length () == 0);
 	    gcc_assert (node_2->m_succs.length () == 0);
 
@@ -2181,6 +2187,7 @@ exploded_graph::process_worklist ()
 
 			/* Remove node_2 from the worklist.  */
 			m_worklist.take_next ();
+			node_2->set_status (exploded_node::STATUS_MERGER);
 
 			/* Continue processing "node" below.  */
 		      }
@@ -2190,6 +2197,7 @@ exploded_graph::process_worklist ()
 			   in the worklist, to be processed on the next
 			   iteration.  */
 			add_edge (node, node_2, NULL, change);
+			node->set_status (exploded_node::STATUS_MERGER);
 			continue;
 		      }
 		    else
@@ -2232,12 +2240,18 @@ exploded_graph::process_worklist ()
 			if (merged_enode == node)
 			  m_worklist.add_node (merged_enode);
 			else
-			  add_edge (node, merged_enode, NULL, change);
+			  {
+			    add_edge (node, merged_enode, NULL, change);
+			    node->set_status (exploded_node::STATUS_MERGER);
+			  }
 
 			if (merged_enode == node_2)
 			  m_worklist.add_node (merged_enode);
 			else
-			  add_edge (node_2, merged_enode, NULL, change);
+			  {
+			    add_edge (node_2, merged_enode, NULL, change);
+			    node_2->set_status (exploded_node::STATUS_MERGER);
+			  }
 
 			continue;
 		      }
@@ -2320,6 +2334,8 @@ exploded_graph::process_node (exploded_node *node)
   logger * const logger = get_logger ();
   LOG_FUNC_1 (logger, "EN: %i", node->m_index);
 
+  node->set_status (exploded_node::STATUS_PROCESSED);
+
   const program_point &point = node->get_point ();
 
   /* Update cfun and input_location in case of an ICE: make it easier to
@@ -3180,8 +3196,16 @@ exploded_graph::dump_exploded_nodes () const
     }
 
   /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
-     giving the number of exploded nodes for "before-stmt", and their
-     IDs.  */
+     giving the number of processed exploded nodes for "before-stmt",
+     and the IDs of processed and merger enodes.
+
+     We highlight the count of *processed* enodes since this is of most
+     interest in DejaGnu tests for ensuring that state merger has
+     happened.
+
+     We don't show the count of merger enodes, as this is more of an
+     implementation detail of the merging that we don't want to bake
+     into our expected DejaGnu messages.  */
 
   unsigned i;
   exploded_node *enode;
@@ -3199,25 +3223,43 @@ exploded_graph::dump_exploded_nodes () const
 	      if (seen.contains (stmt))
 		continue;
 
+	      auto_vec<exploded_node *> processed_enodes;
+	      auto_vec<exploded_node *> merger_enodes;
 	      /* This is O(N^2).  */
 	      unsigned j;
-	      auto_vec<exploded_node *> enodes;
 	      exploded_node *other_enode;
 	      FOR_EACH_VEC_ELT (m_nodes, j, other_enode)
 		{
 		  if (other_enode->get_point ().get_kind () != PK_BEFORE_STMT)
 		    continue;
 		  if (other_enode->get_stmt () == stmt)
-		    enodes.safe_push (other_enode);
+		    switch (other_enode->get_status ())
+		      {
+		      default:
+			gcc_unreachable ();
+		      case exploded_node::STATUS_PROCESSED:
+			processed_enodes.safe_push (other_enode);
+			break;
+		      case exploded_node::STATUS_MERGER:
+			merger_enodes.safe_push (other_enode);
+			break;
+		      }
 		}
 
 	      pretty_printer pp;
-	      print_enode_indices (&pp, enodes);
+	      pp_character (&pp, '[');
+	      print_enode_indices (&pp, processed_enodes);
+	      if (merger_enodes.length () > 0)
+		{
+		  pp_string (&pp, "] merger(s): [");
+		  print_enode_indices (&pp, merger_enodes);
+		}
+	      pp_character (&pp, ']');
 
-	      warning_n (stmt->location, 0, enodes.length (),
-			 "%i exploded node: %s",
-			 "%i exploded nodes: %s",
-			 enodes.length (), pp_formatted_text (&pp));
+	      warning_n (stmt->location, 0, processed_enodes.length (),
+			 "%i processed enode: %s",
+			 "%i processed enodes: %s",
+			 processed_enodes.length (), pp_formatted_text (&pp));
 	      seen.add (stmt);
 
 	      /* If the argument is non-zero, then print all of the states
@@ -3233,10 +3275,11 @@ exploded_graph::dump_exploded_nodes () const
 	      if (i_arg)
 		{
 		  exploded_node *other_enode;
-		  FOR_EACH_VEC_ELT (enodes, j, other_enode)
+		  FOR_EACH_VEC_ELT (processed_enodes, j, other_enode)
 		    {
 		      fprintf (stderr, "%i of %i: EN %i:\n",
-			       j + 1, enodes.length (), other_enode->m_index);
+			       j + 1, processed_enodes.length (),
+			       other_enode->m_index);
 		      other_enode->dump_succs_and_preds (stderr);
 		      /* Dump state.  */
 		      other_enode->get_state ().dump (m_ext_state, false);
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index 6a1b9b2..e47816a 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -151,9 +151,26 @@ struct eg_traits
 class exploded_node : public dnode<eg_traits>
 {
  public:
+  /* Has this enode had exploded_graph::process_node called on it?
+     This allows us to distinguish enodes that were merged during
+     worklist-handling, and thus never had process_node called on them
+     (in favor of processing the merged node).  */
+  enum status
+  {
+    /* Node is in the worklist.  */
+    STATUS_WORKLIST,
+
+    /* Node has had exploded_graph::process_node called on it.  */
+    STATUS_PROCESSED,
+
+    /* Node was left unprocessed due to merger; it won't have had
+       exploded_graph::process_node called on it.  */
+    STATUS_MERGER
+  };
+
   exploded_node (point_and_state ps,
 		 int index)
-  : m_ps (ps), m_index (index)
+  : m_ps (ps), m_status (STATUS_WORKLIST), m_index (index)
   {
     gcc_checking_assert (ps.get_state ().m_region_model->canonicalized_p ());
   }
@@ -240,6 +257,13 @@ class exploded_node : public dnode<eg_traits>
 
   void dump_succs_and_preds (FILE *outf) const;
 
+  enum status get_status () const { return m_status; }
+  void set_status (enum status status)
+  {
+    gcc_assert (m_status == STATUS_WORKLIST);
+    m_status = status;
+  }
+
 private:
   DISABLE_COPY_AND_ASSIGN (exploded_node);
 
@@ -249,6 +273,8 @@ private:
      is immutable once the exploded_node has been created.  */
   const point_and_state m_ps;
 
+  enum status m_status;
+
 public:
   /* The index of this exploded_node.  */
   const int m_index;