analyzer: add new supergraph visualization

This patch extends -fdump-analyzer-supergraph so that rather than just
dumping a DUMP_BASE_NAME.supergraph.dot at the start of analysis, it
also dumps a DUMP_BASE_NAME.supergraph-eg.dot at the end.

The new dump file contains a concise dump of the exploded_graph,
organized with respect to the supergraph and its statements.  The
exploded nodes are colorized to show sm-state, but no other state
is shown.  Per exploded_node saved_diagnostics are also shown,
along with feasibility of the paths to reach them.

I've been finding this a useful way of tracking down issues in
exploded_graphs that are sufficiently large that the output of
-fdump-analyzer-exploded-graph becomes unwieldy.

The patch extends feasiblity-testing so that if the exploded_path
for a saved_diagnostic is found to be infeasible, the reason is
saved and written into the saved_diagnostic, so it can be shown in the
dump.  I've found this very useful when tracking down feasibility
issues.

I'm keeping the initial dump file as it's useful when tracking down
ICEs within the analyzer (which would stop the second dump file being
written).

gcc/analyzer/ChangeLog:
	* analyzer.h (class feasibility_problem): New forward decl.
	* diagnostic-manager.cc (saved_diagnostic::saved_diagnostic):
	Initialize new fields m_status, m_epath_length, and m_problem.
	(saved_diagnostic::~saved_diagnostic): Delete m_problem.
	(dedupe_candidate::dedupe_candidate): Convert "sd" param from a
	const ref to a mutable ptr.
	(dedupe_winners::add): Convert "sd" param from a const ref to a
	mutable ptr.  Record the length of the exploded_path.  Record the
	feasibility/infeasibility of sd into sd, capturing a
	feasibility_problem when feasible_p fails, and storing it in sd.
	(diagnostic_manager::emit_saved_diagnostics): Update for pass by
	ptr rather than by const ref.
	* diagnostic-manager.h (class saved_diagnostic): Add new enum
	status.  Add fields m_status, m_epath_length and m_problem.
	(saved_diagnostic::set_feasible): New member function.
	(saved_diagnostic::set_infeasible): New member function.
	(saved_diagnostic::get_feasibility_problem): New accessor.
	(saved_diagnostic::get_status): New accessor.
	(saved_diagnostic::set_epath_length): New member function.
	(saved_diagnostic::get_epath_length): New accessor.
	* engine.cc: Include "gimple-pretty-print.h".
	(exploded_path::feasible_p): Add OUT param and, if non-NULL, write
	a new feasibility_problem to it on failure.
	(viz_callgraph_node::dump_dot): Convert begin_tr calls to
	begin_trtd.  Convert end_tr calls to end_tdtr.
	(class exploded_graph_annotator): New subclass of dot_annotator.
	(impl_run_checkers): Add a second -fdump-analyzer-supergraph dump
	after the analysis runs, using exploded_graph_annotator. dumping
	to DUMP_BASE_NAME.supergraph-eg.dot.
	* exploded-graph.h (exploded_node::get_dot_fillcolor): Make
	public.
	(exploded_path::feasible_p): Add OUT param.
	(class feasibility_problem): New class.
	* state-purge.cc (state_purge_annotator::add_node_annotations):
	Return a bool, add a "within_table" param.
	(print_vec_of_names): Convert begin_tr calls to begin_trtd.
	Convert end_tr calls to end_tdtr.
	(state_purge_annotator::add_stmt_annotations): Add "within_row"
	param.
	* state-purge.h ((state_purge_annotator::add_node_annotations):
	Return a bool, add a "within_table" param.
	(state_purge_annotator::add_stmt_annotations): Add "within_row"
	param.
	* supergraph.cc (supernode::dump_dot): Call add_node_annotations
	twice: as before, passing false for "within_table", then again
	with true when within the TABLE element.  Convert some begin_tr
	calls to begin_trtd, and some end_tr calls to end_tdtr.
	Repeat each add_stmt_annotations call, distinguishing between
	calls that add TRs and those that add TDs to an existing TR.
	Add a call to add_after_node_annotations.
	* supergraph.h (dot_annotator::add_node_annotations): Add a
	"within_table" param.
	(dot_annotator::add_stmt_annotations): Add a "within_row" param.
	(dot_annotator::add_after_node_annotations): New vfunc.

gcc/ChangeLog:
	* doc/invoke.texi (-fdump-analyzer-supergraph): Document that this
	now emits two .dot files.
	* graphviz.cc (graphviz_out::begin_tr): Only emit a TR, not a TD.
	(graphviz_out::end_tr): Only close a TR, not a TD.
	(graphviz_out::begin_td): New.
	(graphviz_out::end_td): New.
	(graphviz_out::begin_trtd): New, replacing the old implementation
	of graphviz_out::begin_tr.
	(graphviz_out::end_tdtr): New, replacing the old implementation
	of graphviz_out::end_tr.
	* graphviz.h (graphviz_out::begin_td): New decl.
	(graphviz_out::end_td): New decl.
	(graphviz_out::begin_trtd): New decl.
	(graphviz_out::end_tdtr): New decl.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/dot-output.c: Check that
	dot-output.c.supergraph-eg.dot is valid.

10 files changed, 461 insertions, 48 deletions

diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog
index a04b5cc..ddb02af 100644
--- a/gcc/analyzer/ChangeLog
+++ b/gcc/analyzer/ChangeLog
@@ -1,5 +1,62 @@
 2020-03-27  David Malcolm  <dmalcolm@redhat.com>
 
+	* analyzer.h (class feasibility_problem): New forward decl.
+	* diagnostic-manager.cc (saved_diagnostic::saved_diagnostic):
+	Initialize new fields m_status, m_epath_length, and m_problem.
+	(saved_diagnostic::~saved_diagnostic): Delete m_problem.
+	(dedupe_candidate::dedupe_candidate): Convert "sd" param from a
+	const ref to a mutable ptr.
+	(dedupe_winners::add): Convert "sd" param from a const ref to a
+	mutable ptr.  Record the length of the exploded_path.  Record the
+	feasibility/infeasibility of sd into sd, capturing a
+	feasibility_problem when feasible_p fails, and storing it in sd.
+	(diagnostic_manager::emit_saved_diagnostics): Update for pass by
+	ptr rather than by const ref.
+	* diagnostic-manager.h (class saved_diagnostic): Add new enum
+	status.  Add fields m_status, m_epath_length and m_problem.
+	(saved_diagnostic::set_feasible): New member function.
+	(saved_diagnostic::set_infeasible): New member function.
+	(saved_diagnostic::get_feasibility_problem): New accessor.
+	(saved_diagnostic::get_status): New accessor.
+	(saved_diagnostic::set_epath_length): New member function.
+	(saved_diagnostic::get_epath_length): New accessor.
+	* engine.cc: Include "gimple-pretty-print.h".
+	(exploded_path::feasible_p): Add OUT param and, if non-NULL, write
+	a new feasibility_problem to it on failure.
+	(viz_callgraph_node::dump_dot): Convert begin_tr calls to
+	begin_trtd.  Convert end_tr calls to end_tdtr.
+	(class exploded_graph_annotator): New subclass of dot_annotator.
+	(impl_run_checkers): Add a second -fdump-analyzer-supergraph dump
+	after the analysis runs, using exploded_graph_annotator. dumping
+	to DUMP_BASE_NAME.supergraph-eg.dot.
+	* exploded-graph.h (exploded_node::get_dot_fillcolor): Make
+	public.
+	(exploded_path::feasible_p): Add OUT param.
+	(class feasibility_problem): New class.
+	* state-purge.cc (state_purge_annotator::add_node_annotations):
+	Return a bool, add a "within_table" param.
+	(print_vec_of_names): Convert begin_tr calls to begin_trtd.
+	Convert end_tr calls to end_tdtr.
+	(state_purge_annotator::add_stmt_annotations): Add "within_row"
+	param.
+	* state-purge.h ((state_purge_annotator::add_node_annotations):
+	Return a bool, add a "within_table" param.
+	(state_purge_annotator::add_stmt_annotations): Add "within_row"
+	param.
+	* supergraph.cc (supernode::dump_dot): Call add_node_annotations
+	twice: as before, passing false for "within_table", then again
+	with true when within the TABLE element.  Convert some begin_tr
+	calls to begin_trtd, and some end_tr calls to end_tdtr.
+	Repeat each add_stmt_annotations call, distinguishing between
+	calls that add TRs and those that add TDs to an existing TR.
+	Add a call to add_after_node_annotations.
+	* supergraph.h (dot_annotator::add_node_annotations): Add a
+	"within_table" param.
+	(dot_annotator::add_stmt_annotations): Add a "within_row" param.
+	(dot_annotator::add_after_node_annotations): New vfunc.
+
+2020-03-27  David Malcolm  <dmalcolm@redhat.com>
+
 	* diagnostic-manager.cc (dedupe_winners::add): Show the
 	exploded_node index in the log messages.
 	(diagnostic_manager::emit_saved_diagnostics): Log a summary of
diff --git a/gcc/analyzer/analyzer.h b/gcc/analyzer/analyzer.h
index 8d0d169..a740112 100644
--- a/gcc/analyzer/analyzer.h
+++ b/gcc/analyzer/analyzer.h
@@ -64,6 +64,7 @@ class program_state;
 class exploded_graph;
 class exploded_node;
 class exploded_edge;
+class feasibility_problem;
 class exploded_cluster;
 class exploded_path;
 class analysis_plan;
diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc
index e27e626..4b884c7 100644
--- a/gcc/analyzer/diagnostic-manager.cc
+++ b/gcc/analyzer/diagnostic-manager.cc
@@ -77,7 +77,8 @@ saved_diagnostic::saved_diagnostic (const state_machine *sm,
     outlive that.  */
   m_stmt_finder (stmt_finder ? stmt_finder->clone () : NULL),
   m_var (var), m_state (state),
-  m_d (d), m_trailing_eedge (NULL)
+  m_d (d), m_trailing_eedge (NULL),
+  m_status (STATUS_NEW), m_epath_length (0), m_problem (NULL)
 {
   gcc_assert (m_stmt || m_stmt_finder);
 
@@ -92,6 +93,7 @@ saved_diagnostic::~saved_diagnostic ()
 {
   delete m_stmt_finder;
   delete m_d;
+  delete m_problem;
 }
 
 bool
@@ -257,8 +259,8 @@ class dedupe_candidate
 public:
   // has the exploded_path
   dedupe_candidate (const shortest_exploded_paths &sp,
-		    const saved_diagnostic &sd)
-  : m_epath (sp.get_shortest_path (sd.m_enode)),
+		    saved_diagnostic *sd)
+  : m_epath (sp.get_shortest_path (sd->m_enode)),
     m_num_dupes (0)
   {
   }
@@ -344,12 +346,14 @@ public:
 
   void add (logger *logger,
 	    const shortest_exploded_paths &sp,
-	    const saved_diagnostic &sd)
+	    saved_diagnostic *sd)
   {
     /* Build a dedupe_candidate for SD.
        This uses SP to build an exploded_path.  */
     dedupe_candidate *dc = new dedupe_candidate (sp, sd);
 
+    sd->set_epath_length (dc->length ());
+
     /* Verify that the epath is feasible.
        State-merging means that not every path in the epath corresponds
        to a feasible one w.r.t. states.
@@ -359,26 +363,30 @@ public:
        feasible paths within the egraph.  */
     if (logger)
       logger->log ("considering %qs at EN: %i, SN: %i",
-		   sd.m_d->get_kind (), sd.m_enode->m_index,
-		   sd.m_snode->m_index);
+		   sd->m_d->get_kind (), sd->m_enode->m_index,
+		   sd->m_snode->m_index);
 
-    if (!dc->get_path ().feasible_p (logger))
+    feasibility_problem *p = NULL;
+    if (!dc->get_path ().feasible_p (logger, &p))
       {
 	if (logger)
 	  logger->log ("rejecting %qs at EN: %i, SN: %i"
 		       " due to infeasible path",
-		       sd.m_d->get_kind (), sd.m_enode->m_index,
-		       sd.m_snode->m_index);
+		       sd->m_d->get_kind (), sd->m_enode->m_index,
+		       sd->m_snode->m_index);
+	sd->set_infeasible (p);
 	delete dc;
 	return;
       }
     else
       if (logger)
 	logger->log ("accepting %qs at EN: %i, SN: %i with feasible path",
-		     sd.m_d->get_kind (), sd.m_enode->m_index,
-		     sd.m_snode->m_index);
+		     sd->m_d->get_kind (), sd->m_enode->m_index,
+		     sd->m_snode->m_index);
+
+    sd->set_feasible ();
 
-    dedupe_key *key = new dedupe_key (sd, dc->get_path ());
+    dedupe_key *key = new dedupe_key (*sd, dc->get_path ());
     if (dedupe_candidate **slot = m_map.get (key))
       {
 	if (logger)
@@ -495,7 +503,7 @@ diagnostic_manager::emit_saved_diagnostics (const exploded_graph &eg)
   int i;
   saved_diagnostic *sd;
   FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
-    best_candidates.add (get_logger (), sp, *sd);
+    best_candidates.add (get_logger (), sp, sd);
 
   /* For each dedupe-key, call emit_saved_diagnostic on the "best"
      saved_diagnostic.  */
diff --git a/gcc/analyzer/diagnostic-manager.h b/gcc/analyzer/diagnostic-manager.h
index 1c7bc74..c6f3c0c 100644
--- a/gcc/analyzer/diagnostic-manager.h
+++ b/gcc/analyzer/diagnostic-manager.h
@@ -28,6 +28,13 @@ namespace ana {
 class saved_diagnostic
 {
 public:
+  enum status
+  {
+   STATUS_NEW,
+   STATUS_INFEASIBLE_PATH,
+   STATUS_FEASIBLE_PATH
+  };
+
   saved_diagnostic (const state_machine *sm,
 		    const exploded_node *enode,
 		    const supernode *snode, const gimple *stmt,
@@ -38,6 +45,27 @@ public:
 
   bool operator== (const saved_diagnostic &other) const;
 
+  void set_feasible ()
+  {
+    gcc_assert (m_status == STATUS_NEW);
+    m_status = STATUS_FEASIBLE_PATH;
+  }
+  void set_infeasible (feasibility_problem *p)
+  {
+    gcc_assert (m_status == STATUS_NEW);
+    m_status = STATUS_INFEASIBLE_PATH;
+    m_problem = p; // take ownership
+  }
+  const feasibility_problem *get_feasibility_problem () const
+  {
+    return m_problem;
+  }
+
+  enum status get_status () const { return m_status; }
+
+  void set_epath_length (unsigned length) { m_epath_length = length; }
+  unsigned get_epath_length () const { return m_epath_length; }
+
   //private:
   const state_machine *m_sm;
   const exploded_node *m_enode;
@@ -51,6 +79,10 @@ public:
 
 private:
   DISABLE_COPY_AND_ASSIGN (saved_diagnostic);
+
+  enum status m_status;
+  unsigned m_epath_length;
+  feasibility_problem *m_problem;
 };
 
 class path_builder;
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 369110b..befd483 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -47,6 +47,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "basic-block.h"
 #include "gimple.h"
 #include "gimple-iterator.h"
+#include "gimple-pretty-print.h"
 #include "cgraph.h"
 #include "digraph.h"
 #include "analyzer/supergraph.h"
@@ -2842,10 +2843,12 @@ exploded_path::get_final_enode () const
   return m_edges[m_edges.length () - 1]->m_dest;
 }
 
-/* Check state along this path, returning true if it is feasible.  */
+/* Check state along this path, returning true if it is feasible.
+   If OUT is non-NULL, and the path is infeasible, write a new
+   feasibility_problem to *OUT.  */
 
 bool
-exploded_path::feasible_p (logger *logger) const
+exploded_path::feasible_p (logger *logger, feasibility_problem **out) const
 {
   LOG_SCOPE (logger);
 
@@ -2898,6 +2901,8 @@ exploded_path::feasible_p (logger *logger) const
 		  logger->log ("rejecting due to region model");
 		  model.dump_to_pp (logger->get_printer (), false);
 		}
+	      if (out)
+		*out = new feasibility_problem (i, model, *eedge, last_stmt);
 	      return false;
 	    }
 	}
@@ -3522,19 +3527,19 @@ public:
     pp_string (pp, "<TABLE BORDER=\"0\">");
     pp_write_text_to_stream (pp);
 
-    gv->begin_tr ();
+    gv->begin_trtd ();
     pp_printf (pp, "VCG: %i: %s", m_index, function_name (m_fun));
-    gv->end_tr ();
+    gv->end_tdtr ();
     pp_newline (pp);
 
-    gv->begin_tr ();
+    gv->begin_trtd ();
     pp_printf (pp, "supernodes: %i\n", m_num_supernodes);
-    gv->end_tr ();
+    gv->end_tdtr ();
     pp_newline (pp);
 
-    gv->begin_tr ();
+    gv->begin_trtd ();
     pp_printf (pp, "superedges: %i\n", m_num_superedges);
-    gv->end_tr ();
+    gv->end_tdtr ();
     pp_newline (pp);
 
     if (args.m_eg)
@@ -3547,9 +3552,9 @@ public:
 	    if (enode->get_point ().get_function () == m_fun)
 	      num_enodes++;
 	  }
-	gv->begin_tr ();
+	gv->begin_trtd ();
 	pp_printf (pp, "enodes: %i\n", num_enodes);
-	gv->end_tr ();
+	gv->end_tdtr ();
 	pp_newline (pp);
 
 	// TODO: also show the per-callstring breakdown
@@ -3571,11 +3576,11 @@ public:
 	      }
 	    if (num_enodes > 0)
 	      {
-		gv->begin_tr ();
+		gv->begin_trtd ();
 		cs->print (pp);
 		pp_printf (pp, ": %i\n", num_enodes);
 		pp_write_text_as_html_like_dot_to_stream (pp);
-		gv->end_tr ();
+		gv->end_tdtr ();
 	      }
 	  }
 
@@ -3584,10 +3589,10 @@ public:
 	if (data)
 	  {
 	    pp_newline (pp);
-	    gv->begin_tr ();
+	    gv->begin_trtd ();
 	    pp_printf (pp, "summaries: %i\n", data->m_summaries.length ());
 	    pp_write_text_as_html_like_dot_to_stream (pp);
-	    gv->end_tr ();
+	    gv->end_tdtr ();
 	  }
       }
 
@@ -3730,6 +3735,231 @@ dump_callgraph (const supergraph &sg, const exploded_graph *eg)
   free (filename);
 }
 
+/* Subclass of dot_annotator for implementing
+   DUMP_BASE_NAME.supergraph-eg.dot, a post-analysis dump of the supergraph.
+
+   Annotate the supergraph nodes by printing the exploded nodes in concise
+   form within them, next to their pertinent statements where appropriate,
+   colorizing the exploded nodes based on sm-state.
+   Also show saved diagnostics within the exploded nodes, giving information
+   on whether they were feasible, and, if infeasible, where the problem
+   was.  */
+
+class exploded_graph_annotator : public dot_annotator
+{
+public:
+  exploded_graph_annotator (const exploded_graph &eg)
+  : m_eg (eg)
+  {
+    /* Avoid O(N^2) by prepopulating m_enodes_per_snodes.  */
+    unsigned i;
+    supernode *snode;
+    FOR_EACH_VEC_ELT (eg.get_supergraph ().m_nodes, i, snode)
+      m_enodes_per_snodes.safe_push (new auto_vec <exploded_node *> ());
+    exploded_node *enode;
+    FOR_EACH_VEC_ELT (m_eg.m_nodes, i, enode)
+      if (enode->get_supernode ())
+	m_enodes_per_snodes[enode->get_supernode ()->m_index]->safe_push (enode);
+  }
+
+  /* Show exploded nodes for BEFORE_SUPERNODE points before N.  */
+  bool add_node_annotations (graphviz_out *gv, const supernode &n,
+			     bool within_table)
+    const FINAL OVERRIDE
+  {
+    if (!within_table)
+      return false;
+    gv->begin_tr ();
+    pretty_printer *pp = gv->get_pp ();
+
+    gv->begin_td ();
+    pp_string (pp, "BEFORE");
+    gv->end_td ();
+
+    unsigned i;
+    exploded_node *enode;
+    bool had_enode = false;
+    FOR_EACH_VEC_ELT (*m_enodes_per_snodes[n.m_index], i, enode)
+      {
+	gcc_assert (enode->get_supernode () == &n);
+	const program_point &point = enode->get_point ();
+	if (point.get_kind () != PK_BEFORE_SUPERNODE)
+	  continue;
+	print_enode (gv, enode);
+	had_enode = true;
+      }
+    if (!had_enode)
+      pp_string (pp, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
+    pp_flush (pp);
+    gv->end_tr ();
+    return true;
+  }
+
+  /* Show exploded nodes for STMT.  */
+  void add_stmt_annotations (graphviz_out *gv, const gimple *stmt,
+			     bool within_row)
+    const FINAL OVERRIDE
+  {
+    if (!within_row)
+      return;
+    pretty_printer *pp = gv->get_pp ();
+
+    const supernode *snode
+      = m_eg.get_supergraph ().get_supernode_for_stmt (stmt);
+    unsigned i;
+    exploded_node *enode;
+    bool had_td = false;
+    FOR_EACH_VEC_ELT (*m_enodes_per_snodes[snode->m_index], i, enode)
+      {
+	const program_point &point = enode->get_point ();
+	if (point.get_kind () != PK_BEFORE_STMT)
+	  continue;
+	if (point.get_stmt () != stmt)
+	  continue;
+	print_enode (gv, enode);
+	had_td = true;
+      }
+    pp_flush (pp);
+    if (!had_td)
+      {
+	gv->begin_td ();
+	gv->end_td ();
+      }
+  }
+
+  /* Show exploded nodes for AFTER_SUPERNODE points after N.  */
+  bool add_after_node_annotations (graphviz_out *gv, const supernode &n)
+    const FINAL OVERRIDE
+  {
+    gv->begin_tr ();
+    pretty_printer *pp = gv->get_pp ();
+
+    gv->begin_td ();
+    pp_string (pp, "AFTER");
+    gv->end_td ();
+
+    unsigned i;
+    exploded_node *enode;
+    FOR_EACH_VEC_ELT (*m_enodes_per_snodes[n.m_index], i, enode)
+      {
+	gcc_assert (enode->get_supernode () == &n);
+	const program_point &point = enode->get_point ();
+	if (point.get_kind () != PK_AFTER_SUPERNODE)
+	  continue;
+	print_enode (gv, enode);
+      }
+    pp_flush (pp);
+    gv->end_tr ();
+    return true;
+  }
+
+private:
+  /* Concisely print a TD element for ENODE, showing the index, status,
+     and any saved_diagnostics at the enode.  Colorize it to show sm-state.
+
+     Ideally we'd dump ENODE's state here, hidden behind some kind of
+     interactive disclosure method like a tooltip, so that the states
+     can be explored without overwhelming the graph.
+     However, I wasn't able to get graphviz/xdot to show tooltips on
+     individual elements within a HTML-like label.  */
+  void print_enode (graphviz_out *gv, const exploded_node *enode) const
+  {
+    pretty_printer *pp = gv->get_pp ();
+    pp_printf (pp, "<TD BGCOLOR=\"%s\">",
+	       enode->get_dot_fillcolor ());
+    pp_printf (pp, "<TABLE BORDER=\"0\">");
+    gv->begin_trtd ();
+    pp_printf (pp, "EN: %i", enode->m_index);
+    switch (enode->get_status ())
+      {
+      default:
+	gcc_unreachable ();
+      case exploded_node::STATUS_WORKLIST:
+	pp_string (pp, "(W)");
+	break;
+      case exploded_node::STATUS_PROCESSED:
+	break;
+      case exploded_node::STATUS_MERGER:
+	pp_string (pp, "(M)");
+	break;
+      }
+    gv->end_tdtr ();
+    /* Dump any saved_diagnostics at this enode.  */
+    {
+      const diagnostic_manager &dm = m_eg.get_diagnostic_manager ();
+      for (unsigned i = 0; i < dm.get_num_diagnostics (); i++)
+	{
+	  const saved_diagnostic *sd = dm.get_saved_diagnostic (i);
+	  if (sd->m_enode == enode)
+	    print_saved_diagnostic (gv, sd);
+	}
+    }
+    pp_printf (pp, "</TABLE>");
+    pp_printf (pp, "</TD>");
+  }
+
+  /* Print a TABLE element for SD, showing the kind, the length of the
+     exploded_path, whether the path was feasible, and if infeasible,
+     what the problem was.  */
+  void print_saved_diagnostic (graphviz_out *gv,
+			       const saved_diagnostic *sd) const
+  {
+    pretty_printer *pp = gv->get_pp ();
+    gv->begin_trtd ();
+    pp_printf (pp, "<TABLE BORDER=\"0\">");
+    gv->begin_tr ();
+    pp_string (pp, "<TD BGCOLOR=\"green\">");
+    pp_printf (pp, "DIAGNOSTIC: %s", sd->m_d->get_kind ());
+    gv->end_tdtr ();
+    gv->begin_trtd ();
+    pp_printf (pp, "epath length: %i", sd->get_epath_length ());
+    gv->end_tdtr ();
+    switch (sd->get_status ())
+      {
+      default:
+      case saved_diagnostic::STATUS_NEW:
+	gcc_unreachable ();
+	break;
+      case saved_diagnostic::STATUS_INFEASIBLE_PATH:
+	{
+	  gv->begin_trtd ();
+	  pp_printf (pp, "INFEASIBLE");
+	  gv->end_tdtr ();
+	  const feasibility_problem *p = sd->get_feasibility_problem ();
+	  gcc_assert (p);
+	  gv->begin_trtd ();
+	  pp_printf (pp, "at eedge %i: EN:%i -> EN:%i",
+		     p->m_eedge_idx,
+		     p->m_eedge.m_src->m_index,
+		     p->m_eedge.m_dest->m_index);
+	  pp_write_text_as_html_like_dot_to_stream (pp);
+	  gv->end_tdtr ();
+	  gv->begin_trtd ();
+	  p->m_eedge.m_sedge->dump (pp);
+	  pp_write_text_as_html_like_dot_to_stream (pp);
+	  gv->end_tdtr ();
+	  gv->begin_trtd ();
+	  pp_gimple_stmt_1 (pp, p->m_last_stmt, 0, (dump_flags_t)0);
+	  pp_write_text_as_html_like_dot_to_stream (pp);
+	  gv->end_tdtr ();
+	  /* Ideally we'd print p->m_model here; see the notes above about
+	     tooltips.  */
+	}
+	break;
+      case saved_diagnostic::STATUS_FEASIBLE_PATH:
+	gv->begin_trtd ();
+	pp_printf (pp, "FEASIBLE");
+	gv->end_tdtr ();
+	break;
+      }
+    pp_printf (pp, "</TABLE>");
+    gv->end_tdtr ();
+  }
+
+  const exploded_graph &m_eg;
+  auto_delete_vec<auto_vec <exploded_node *> > m_enodes_per_snodes;
+};
+
 /* Run the analysis "engine".  */
 
 void
@@ -3752,6 +3982,7 @@ impl_run_checkers (logger *logger)
 
   if (flag_dump_analyzer_supergraph)
     {
+      /* Dump supergraph pre-analysis.  */
       auto_timevar tv (TV_ANALYZER_DUMP);
       char *filename = concat (dump_base_name, ".supergraph.dot", NULL);
       supergraph::dump_args_t args ((enum supergraph_dot_flags)0, NULL);
@@ -3816,6 +4047,17 @@ impl_run_checkers (logger *logger)
   if (flag_dump_analyzer_callgraph)
     dump_callgraph (sg, &eg);
 
+  if (flag_dump_analyzer_supergraph)
+    {
+      /* Dump post-analysis form of supergraph.  */
+      auto_timevar tv (TV_ANALYZER_DUMP);
+      char *filename = concat (dump_base_name, ".supergraph-eg.dot", NULL);
+      exploded_graph_annotator a (eg);
+      supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a);
+      sg.dump_dot (filename, args);
+      free (filename);
+    }
+
   delete purge_map;
 }
 
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index b9a5618..b3e89d4 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -179,6 +179,7 @@ class exploded_node : public dnode<eg_traits>
 
   hashval_t hash () const { return m_ps.hash (); }
 
+  const char * get_dot_fillcolor () const;
   void dump_dot (graphviz_out *gv, const dump_args_t &args)
     const FINAL OVERRIDE;
   void dump_dot_id (pretty_printer *pp) const;
@@ -269,8 +270,6 @@ class exploded_node : public dnode<eg_traits>
 private:
   DISABLE_COPY_AND_ASSIGN (exploded_node);
 
-  const char * get_dot_fillcolor () const;
-
   /* The <program_point, program_state> pair.  This is const, as it
      is immutable once the exploded_node has been created.  */
   const point_and_state m_ps;
@@ -857,11 +856,30 @@ public:
   void dump (FILE *fp) const;
   void dump () const;
 
-  bool feasible_p (logger *logger) const;
+  bool feasible_p (logger *logger, feasibility_problem **out) const;
 
   auto_vec<const exploded_edge *> m_edges;
 };
 
+/* A reason why a particular exploded_path is infeasible.  */
+
+class feasibility_problem
+{
+public:
+  feasibility_problem (unsigned eedge_idx,
+		       const region_model &model,
+		       const exploded_edge &eedge,
+		       const gimple *last_stmt)
+  : m_eedge_idx (eedge_idx), m_model (model), m_eedge (eedge),
+    m_last_stmt (last_stmt)
+  {}
+
+  unsigned m_eedge_idx;
+  region_model m_model;
+  const exploded_edge &m_eedge;
+  const gimple *m_last_stmt;
+};
+
 /* Finding the shortest exploded_path within an exploded_graph.  */
 
 typedef shortest_paths<eg_traits, exploded_path> shortest_exploded_paths;
diff --git a/gcc/analyzer/state-purge.cc b/gcc/analyzer/state-purge.cc
index 01237f0..d5a24b4 100644
--- a/gcc/analyzer/state-purge.cc
+++ b/gcc/analyzer/state-purge.cc
@@ -419,12 +419,16 @@ state_purge_per_ssa_name::process_point (const function_point &point,
    Add an additional record showing which names are purged on entry
    to the supernode N.  */
 
-void
+bool
 state_purge_annotator::add_node_annotations (graphviz_out *gv,
-					     const supernode &n) const
+					     const supernode &n,
+					     bool within_table) const
 {
   if (m_map == NULL)
-    return;
+    return false;
+
+  if (within_table)
+    return false;
 
   pretty_printer *pp = gv->get_pp ();
 
@@ -455,6 +459,7 @@ state_purge_annotator::add_node_annotations (graphviz_out *gv,
 
    pp_string (pp, "\"];\n\n");
    pp_flush (pp);
+   return false;
 }
 
 /* Print V to GV as a comma-separated list in braces within a <TR>,
@@ -469,7 +474,7 @@ print_vec_of_names (graphviz_out *gv, const char *title,
   pretty_printer *pp = gv->get_pp ();
   tree name;
   unsigned i;
-  gv->begin_tr ();
+  gv->begin_trtd ();
   pp_printf (pp, "%s: {", title);
   FOR_EACH_VEC_ELT (v, i, name)
     {
@@ -479,7 +484,7 @@ print_vec_of_names (graphviz_out *gv, const char *title,
     }
   pp_printf (pp, "}");
   pp_write_text_as_html_like_dot_to_stream (pp);
-  gv->end_tr ();
+  gv->end_tdtr ();
   pp_newline (pp);
 }
 
@@ -490,8 +495,12 @@ print_vec_of_names (graphviz_out *gv, const char *title,
 
 void
 state_purge_annotator::add_stmt_annotations (graphviz_out *gv,
-					     const gimple *stmt) const
+					     const gimple *stmt,
+					     bool within_row) const
 {
+  if (within_row)
+    return;
+
   if (m_map == NULL)
     return;
 
diff --git a/gcc/analyzer/state-purge.h b/gcc/analyzer/state-purge.h
index ee7d10c..60464eb 100644
--- a/gcc/analyzer/state-purge.h
+++ b/gcc/analyzer/state-purge.h
@@ -151,10 +151,11 @@ class state_purge_annotator : public dot_annotator
 public:
   state_purge_annotator (const state_purge_map *map) : m_map (map) {}
 
-  void add_node_annotations (graphviz_out *gv, const supernode &n)
+  bool add_node_annotations (graphviz_out *gv, const supernode &n, bool)
     const FINAL OVERRIDE;
 
-  void add_stmt_annotations (graphviz_out *gv, const gimple *stmt)
+  void add_stmt_annotations (graphviz_out *gv, const gimple *stmt,
+			     bool within_row)
     const FINAL OVERRIDE;
 
 private:
diff --git a/gcc/analyzer/supergraph.cc b/gcc/analyzer/supergraph.cc
index 4ed016e..7c6fed3 100644
--- a/gcc/analyzer/supergraph.cc
+++ b/gcc/analyzer/supergraph.cc
@@ -458,7 +458,7 @@ supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
   pretty_printer *pp = gv->get_pp ();
 
   if (args.m_node_annotator)
-    args.m_node_annotator->add_node_annotations (gv, *this);
+    args.m_node_annotator->add_node_annotations (gv, *this, false);
 
   gv->write_indent ();
   dump_dot_id (pp);
@@ -470,19 +470,33 @@ supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
 
   bool had_row = false;
 
+  /* Give any annotator the chance to add its own per-node TR elements. */
+  if (args.m_node_annotator)
+    if (args.m_node_annotator->add_node_annotations (gv, *this, true))
+      had_row = true;
+
   if (m_returning_call)
     {
-      gv->begin_tr ();
+      gv->begin_trtd ();
       pp_string (pp, "returning call: ");
-      gv->end_tr ();
+      gv->end_tdtr ();
 
       gv->begin_tr ();
+      gv->begin_td ();
       pp_gimple_stmt_1 (pp, m_returning_call, 0, (dump_flags_t)0);
       pp_write_text_as_html_like_dot_to_stream (pp);
+      gv->end_td ();
+      /* Give any annotator the chance to add per-stmt TD elements to
+	 this row.  */
+      if (args.m_node_annotator)
+	args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
+						     true);
       gv->end_tr ();
 
+      /* Give any annotator the chance to add per-stmt TR elements.  */
       if (args.m_node_annotator)
-	args.m_node_annotator->add_stmt_annotations (gv, m_returning_call);
+	args.m_node_annotator->add_stmt_annotations (gv, m_returning_call,
+						     false);
       pp_newline (pp);
 
       had_row = true;
@@ -508,12 +522,19 @@ supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
     {
       const gimple *stmt = gsi_stmt (gpi);
       gv->begin_tr ();
+      gv->begin_td ();
       pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
       pp_write_text_as_html_like_dot_to_stream (pp);
+      gv->end_td ();
+      /* Give any annotator the chance to add per-phi TD elements to
+	 this row.  */
+      if (args.m_node_annotator)
+	args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
       gv->end_tr ();
 
+      /* Give any annotator the chance to add per-phi TR elements.  */
       if (args.m_node_annotator)
-	args.m_node_annotator->add_stmt_annotations (gv, stmt);
+	args.m_node_annotator->add_stmt_annotations (gv, stmt, false);
 
       pp_newline (pp);
       had_row = true;
@@ -525,17 +546,30 @@ supernode::dump_dot (graphviz_out *gv, const dump_args_t &args) const
   FOR_EACH_VEC_ELT (m_stmts, i, stmt)
     {
       gv->begin_tr ();
+      gv->begin_td ();
       pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
       pp_write_text_as_html_like_dot_to_stream (pp);
+      gv->end_td ();
+      /* Give any annotator the chance to add per-stmt TD elements to
+	 this row.  */
+      if (args.m_node_annotator)
+	args.m_node_annotator->add_stmt_annotations (gv, stmt, true);
       gv->end_tr ();
 
+      /* Give any annotator the chance to add per-stmt TR elements.  */
       if (args.m_node_annotator)
-	args.m_node_annotator->add_stmt_annotations (gv, stmt);
+	args.m_node_annotator->add_stmt_annotations (gv, stmt, false);
 
       pp_newline (pp);
       had_row = true;
     }
 
+  /* Give any annotator the chance to add additional per-node TR elements
+     to the end of the TABLE. */
+  if (args.m_node_annotator)
+    if (args.m_node_annotator->add_after_node_annotations (gv, *this))
+      had_row = true;
+
   /* Graphviz requires a TABLE element to have at least one TR
      (and each TR to have at least one TD).  */
   if (!had_row)
diff --git a/gcc/analyzer/supergraph.h b/gcc/analyzer/supergraph.h
index ddb674d..c25043d 100644
--- a/gcc/analyzer/supergraph.h
+++ b/gcc/analyzer/supergraph.h
@@ -569,12 +569,23 @@ class dot_annotator
 {
  public:
   virtual ~dot_annotator () {}
-  virtual void add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
-				     const supernode &n ATTRIBUTE_UNUSED)
-    const {}
+  virtual bool add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
+				     const supernode &n ATTRIBUTE_UNUSED,
+				     bool within_table ATTRIBUTE_UNUSED)
+    const
+  {
+    return false;
+  }
   virtual void add_stmt_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
-				     const gimple *stmt ATTRIBUTE_UNUSED)
+				     const gimple *stmt ATTRIBUTE_UNUSED,
+				     bool within_row ATTRIBUTE_UNUSED)
     const {}
+  virtual bool add_after_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
+					   const supernode &n ATTRIBUTE_UNUSED)
+    const
+  {
+    return false;
+  }
 };
 
 extern cgraph_edge *supergraph_call_edge (function *fun, gimple *stmt);