analyzer: revamp side-effects of call summaries [PR107072]

With -fanalyzer-call-summaries the analyzer canl attempt to summarize
the effects of some function calls at their call site, rather than
simulate the call directly, which can avoid big slowdowns during
analysis.

Previously, this summarization was extremely simplistic: no attempt
was made to update sm-state, and region_model::update_for_call_summary
would simply set the return value of the function to UNKNOWN, and assume
the function had no side effects.

This patch implements less simplistic summarizations: it tracks each
possible return enode from the called function, and attempts to generate
a successor enode from the callsite for each that have compatible
conditions, mapping state changes in the summary to state changes
at the callsite.  It also implements the beginnings of heuristics for
generating user-facing descriptions of a summary e.g.
  "when 'foo' returns NULL"
versus:
  "when 'foo' returns a heap-allocated buffer"

This still has some bugs, but much more accurately tracks the effects
of a call, and so is an improvement; it should only have an effect
when -fanalyzer-call-summaries is enabled.

As before, -fanalyzer-call-summaries is disabled by default in
analyzer.opt (but enabled by default in the test suite).

gcc/ChangeLog:
	PR analyzer/107072
	* Makefile.in (ANALYZER_OBJS): Add analyzer/call-summary.o.

gcc/analyzer/ChangeLog:
	PR analyzer/107072
	* analyzer-logging.h: Include "diagnostic-core.h".
	* analyzer.h: Include "function.h".
	(class call_summary): New forward decl.
	(class call_summary_replay): New forward decl.
	(struct per_function_data): New forward decl.
	(struct interesting_t): New forward decl.
	(custom_edge_info::update_state): New vfunc.
	* call-info.cc (custom_edge_info::update_state): New.
	* call-summary.cc: New file.
	* call-summary.h: New file.
	* constraint-manager.cc: Include "analyzer/call-summary.h".
	(class replay_fact_visitor): New.
	(constraint_manager::replay_call_summary): New.
	* constraint-manager.h (constraint_manager::replay_call_summary):
	New.
	* engine.cc: Include "analyzer/call-summary.h".
	(exploded_node::on_stmt): Handle call summaries.
	(class call_summary_edge_info): New.
	(exploded_node::replay_call_summaries): New.
	(exploded_node::replay_call_summary): New.
	(per_function_data::~per_function_data): New.
	(per_function_data::add_call_summary): Move here from header and
	reimplement.
	(exploded_graph::process_node): Call update_state rather than
	update_model when handling bifurcation
	(viz_callgraph_node::dump_dot): Use a regular label rather
	than an HTML table; add summaries to dump.
	* exploded-graph.h: Include "alloc-pool.h", "fibonacci_heap.h",
	"supergraph.h", "sbitmap.h", "shortest-paths.h", "analyzer/sm.h",
	"analyzer/program-state.h", and "analyzer/diagnostic-manager.h".
	(exploded_node::replay_call_summaries): New decl.
	(exploded_node::replay_call_summary): New decl.
	(per_function_data::~per_function_data): New decl.
	(per_function_data::add_call_summary): Move implemention from
	header.
	(per_function_data::m_summaries): Update type of element.
	* known-function-manager.h: Include "analyzer/analyzer-logging.h".
	* program-point.h: Include "pretty-print.h" and
	"analyzer/call-string.h".
	* program-state.cc: Include "analyzer/call-summary.h".
	(sm_state_map::replay_call_summary): New.
	(program_state::replay_call_summary): New.
	* program-state.h (sm_state_map::replay_call_summary): New decl.
	(program_state::replay_call_summary): New decl.
	* region-model-manager.cc
	(region_model_manager::get_or_create_asm_output_svalue): New
	overload.
	* region-model-manager.h
	(region_model_manager::get_or_create_asm_output_svalue): New
	overload decl.
	* region-model.cc: Include "analyzer/call-summary.h".
	(region_model::maybe_update_for_edge): Remove call to
	region_model::update_for_call_summary on
	SUPEREDGE_INTRAPROCEDURAL_CALL.
	(region_model::update_for_call_summary): Delete.
	(region_model::replay_call_summary): New.
	* region-model.h (region_model::replay_call_summary): New decl.
	(region_model::update_for_call_summary): Delete decl.
	* store.cc: Include "analyzer/call-summary.h".
	(store::replay_call_summary): New.
	(store::replay_call_summary_cluster): New.
	* store.h: Include "tristate.h".
	(is_a_helper <const ana::concrete_binding *>::test): New.
	(store::replay_call_summary): New decl.
	(store::replay_call_summary_cluster): New decl.
	* supergraph.cc (get_ultimate_function_for_cgraph_edge): Remove
	"static" from decl.
	(supergraph_call_edge): Make stmt param const.
	* supergraph.h: Include "ordered-hash-map.h", "cfg.h",
	"basic-block.h", "gimple.h", "gimple-iterator.h", and "digraph.h".
	(supergraph_call_edge): Make stmt param const.
	(get_ultimate_function_for_cgraph_edge): New decl.
	* svalue.cc (compound_svalue::compound_svalue): Assert that we're
	not nesting compound_svalues.
	* svalue.h: Include "json.h", "analyzer/store.h", and
	"analyzer/program-point.h".
	(asm_output_svalue::get_num_outputs): New accessor.

gcc/testsuite/ChangeLog:
	PR analyzer/107072
	* gcc.dg/analyzer/call-summaries-2.c: New test.
	* gcc.dg/analyzer/call-summaries-3.c: New test.
	* gcc.dg/analyzer/call-summaries-asm-x86.c: New test.
	* gcc.dg/analyzer/call-summaries-malloc.c: New test.
	* gcc.dg/analyzer/call-summaries-pr107072.c: New test.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>

1 files changed, 183 insertions, 18 deletions

diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 742ac02..b4deee5 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -72,6 +72,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "attribs.h"
 #include "tree-dfa.h"
 #include "analyzer/known-function-manager.h"
+#include "analyzer/call-summary.h"
 
 /* For an overview, see gcc/doc/analyzer.texi.  */
 
@@ -1425,6 +1426,26 @@ exploded_node::on_stmt (exploded_graph &eg,
 				  &old_state, state, uncertainty,
 				  path_ctxt, stmt);
 
+  /* Handle call summaries here.  */
+  if (cgraph_edge *cgedge
+	  = supergraph_call_edge (snode->get_function (), stmt))
+    if (eg.get_analysis_plan ().use_summary_p (cgedge))
+      {
+	function *called_fn = get_ultimate_function_for_cgraph_edge (cgedge);
+	per_function_data *called_fn_data
+	  = eg.get_per_function_data (called_fn);
+	if (called_fn_data)
+	  return replay_call_summaries (eg,
+					snode,
+					as_a <const gcall *> (stmt),
+					state,
+					uncertainty,
+					path_ctxt,
+					called_fn,
+					called_fn_data,
+					&ctxt);
+      }
+
   bool unknown_side_effects = false;
   bool terminate_path = false;
 
@@ -1520,6 +1541,142 @@ exploded_node::on_stmt_post (const gimple *stmt,
     state->m_region_model->on_call_post (call, unknown_side_effects, ctxt);
 }
 
+/* A concrete call_info subclass representing a replay of a call summary.  */
+
+class call_summary_edge_info : public call_info
+{
+public:
+  call_summary_edge_info (const call_details &cd,
+			  function *called_fn,
+			  call_summary *summary,
+			  const extrinsic_state &ext_state)
+  : call_info (cd),
+    m_called_fn (called_fn),
+    m_summary (summary),
+    m_ext_state (ext_state)
+  {}
+
+  bool update_state (program_state *state,
+		     const exploded_edge *,
+		     region_model_context *ctxt) const final override
+  {
+    /* Update STATE based on summary_end_state.  */
+    call_details cd (get_call_details (state->m_region_model, ctxt));
+    call_summary_replay r (cd, m_called_fn, m_summary, m_ext_state);
+    const program_state &summary_end_state = m_summary->get_state ();
+    return state->replay_call_summary (r, summary_end_state);
+  }
+
+  bool update_model (region_model *model,
+		     const exploded_edge *,
+		     region_model_context *ctxt) const final override
+  {
+    /* Update STATE based on summary_end_state.  */
+    call_details cd (get_call_details (model, ctxt));
+    call_summary_replay r (cd, m_called_fn, m_summary, m_ext_state);
+    const program_state &summary_end_state = m_summary->get_state ();
+    model->replay_call_summary (r, *summary_end_state.m_region_model);
+    return true;
+  }
+
+  label_text get_desc (bool /*can_colorize*/) const final override
+  {
+    return m_summary->get_desc ();
+  }
+
+private:
+  function *m_called_fn;
+  call_summary *m_summary;
+  const extrinsic_state &m_ext_state;
+};
+
+/* Use PATH_CTXT to bifurcate, which when handled will add custom edges
+   for a replay of the various feasible summaries in CALLED_FN_DATA.  */
+
+exploded_node::on_stmt_flags
+exploded_node::replay_call_summaries (exploded_graph &eg,
+				      const supernode *snode,
+				      const gcall *call_stmt,
+				      program_state *state,
+				      uncertainty_t *uncertainty,
+				      path_context *path_ctxt,
+				      function *called_fn,
+				      per_function_data *called_fn_data,
+				      region_model_context *ctxt)
+{
+  logger *logger = eg.get_logger ();
+  LOG_SCOPE (logger);
+
+  gcc_assert (called_fn);
+  gcc_assert (called_fn_data);
+
+  /* Each summary will call bifurcate on the PATH_CTXT.  */
+  for (auto summary : called_fn_data->m_summaries)
+    replay_call_summary (eg, snode, call_stmt, state, uncertainty,
+			 path_ctxt, called_fn, summary, ctxt);
+  path_ctxt->terminate_path ();
+
+  return on_stmt_flags ();
+}
+
+/* Use PATH_CTXT to bifurcate, which when handled will add a
+   custom edge for a replay of SUMMARY, if the summary's
+   conditions are feasible based on the current state.  */
+
+void
+exploded_node::replay_call_summary (exploded_graph &eg,
+				    const supernode *snode,
+				    const gcall *call_stmt,
+				    program_state *old_state,
+				    uncertainty_t *uncertainty,
+				    path_context *path_ctxt,
+				    function *called_fn,
+				    call_summary *summary,
+				    region_model_context *ctxt)
+{
+  logger *logger = eg.get_logger ();
+  LOG_SCOPE (logger);
+  gcc_assert (snode);
+  gcc_assert (call_stmt);
+  gcc_assert (old_state);
+  gcc_assert (called_fn);
+  gcc_assert (summary);
+
+  if (logger)
+    logger->log ("using %s as summary for call to %qE from %qE",
+		 summary->get_desc ().get (),
+		 called_fn->decl,
+		 snode->get_function ()->decl);
+  const extrinsic_state &ext_state = eg.get_ext_state ();
+  const program_state &summary_end_state = summary->get_state ();
+  if (logger)
+    {
+      pretty_printer *pp = logger->get_printer ();
+
+      logger->start_log_line ();
+      pp_string (pp, "callsite state: ");
+      old_state->dump_to_pp (ext_state, true, false, pp);
+      logger->end_log_line ();
+
+      logger->start_log_line ();
+      pp_string (pp, "summary end state: ");
+      summary_end_state.dump_to_pp (ext_state, true, false, pp);
+      logger->end_log_line ();
+    }
+
+  program_state new_state (*old_state);
+
+  call_details cd (call_stmt, new_state.m_region_model, ctxt);
+  call_summary_replay r (cd, called_fn, summary, ext_state);
+
+  if (path_ctxt)
+    path_ctxt->bifurcate (new call_summary_edge_info (cd,
+						      called_fn,
+						      summary,
+						      ext_state));
+}
+
+
 /* Consider the effect of following superedge SUCC from this node.
 
    Return true if it's feasible to follow the edge, or false
@@ -2115,6 +2272,20 @@ stats::get_total_enodes () const
   return result;
 }
 
+/* struct per_function_data.  */
+
+per_function_data::~per_function_data ()
+{
+  for (auto iter : m_summaries)
+    delete iter;
+}
+
+void
+per_function_data::add_call_summary (exploded_node *node)
+{
+  m_summaries.safe_push (new call_summary (this, node));
+}
+
 /* strongly_connected_components's ctor.  Tarjan's SCC algorithm.  */
 
 strongly_connected_components::
@@ -3980,7 +4151,7 @@ exploded_graph::process_node (exploded_node *node)
 				NULL, // uncertainty_t *uncertainty
 				NULL, // path_context *path_ctxt
 				stmt);
-	    if (edge_info->update_model (bifurcated_new_state.m_region_model,
+	    if (edge_info->update_state (&bifurcated_new_state,
 					 NULL, /* no exploded_edge yet.  */
 					 &bifurcation_ctxt))
 	      {
@@ -5350,24 +5521,17 @@ public:
     pretty_printer *pp = gv->get_pp ();
 
     dump_dot_id (pp);
-    pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
+    pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
 	       "lightgrey");
-    pp_string (pp, "<TABLE BORDER=\"0\">");
     pp_write_text_to_stream (pp);
 
-    gv->begin_trtd ();
     pp_printf (pp, "VCG: %i: %s", m_index, function_name (m_fun));
-    gv->end_tdtr ();
     pp_newline (pp);
 
-    gv->begin_trtd ();
     pp_printf (pp, "supernodes: %i\n", m_num_supernodes);
-    gv->end_tdtr ();
     pp_newline (pp);
 
-    gv->begin_trtd ();
     pp_printf (pp, "superedges: %i\n", m_num_superedges);
-    gv->end_tdtr ();
     pp_newline (pp);
 
     if (args.m_eg)
@@ -5380,9 +5544,7 @@ public:
 	    if (enode->get_point ().get_function () == m_fun)
 	      num_enodes++;
 	  }
-	gv->begin_trtd ();
 	pp_printf (pp, "enodes: %i\n", num_enodes);
-	gv->end_tdtr ();
 	pp_newline (pp);
 
 	// TODO: also show the per-callstring breakdown
@@ -5404,11 +5566,8 @@ public:
 	      }
 	    if (num_enodes > 0)
 	      {
-		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_tdtr ();
 	      }
 	  }
 
@@ -5417,14 +5576,20 @@ public:
 	if (data)
 	  {
 	    pp_newline (pp);
-	    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_tdtr ();
+	    for (auto summary : data->m_summaries)
+	      {
+		pp_printf (pp, "\nsummary: %s:\n", summary->get_desc ().get ());
+		const extrinsic_state &ext_state = args.m_eg->get_ext_state ();
+		const program_state &state = summary->get_state ();
+		state.dump_to_pp (ext_state, false, true, pp);
+		pp_newline (pp);
+	      }
 	  }
       }
 
-    pp_string (pp, "</TABLE>>];\n\n");
+    pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
+    pp_string (pp, "\"];\n\n");
     pp_flush (pp);
   }