analyzer: consolidate call_string instances

ana::call_string is a wrapper around an auto_vec of callsites, leading
to non-trivial copying when copying around call_string instances, e.g.
in ana::program_point.

This patch consolidates call_string instances within the
region_model_manager: it now owns the root/empty call_string, and
each call_string instance tracks its children, lazily creating them on
demand, so that the call_string instances form a tree-like hierarchy in
memory.  Doing this requires passing the region_model_manager to the
various program_point factory methods, so that they can get at the root
call_string.

Instances of call_string become immutable (apart from their internal
cache for looking up their children); operations that previously
modified them now return the call_string for the result of the
operation.

I wasn't able to observe any performance impact of this, but it
simplifies call_string and program_point management, and thus I hope
will make it easier to improve call summarization.  In particular,
region_model_manager::log_stats will now print a hierarchical dump of
all the call_string instances used in the analysis (in -fdump-analyzer
and -fdump-analyzer-stderr).

gcc/analyzer/ChangeLog:
	* call-string.cc: Add includes of "analyzer/analyzer.h"
	and "analyzer/analyzer-logging.h".
	(call_string::call_string): Delete copy ctor.
	(call_string::operator=): Delete.
	(call_string::operator==): Delete.
	(call_string::hash): Delete.
	(call_string::push_call): Make const, returning the resulting
	call_string.
	(call_string::pop): Delete.
	(call_string::cmp_ptr_ptr): New.
	(call_string::validate): Assert that m_parent is non-NULL, or
	m_elements is empty.
	(call_string::call_string): Move default ctor here from
	call-string.h and reimplement.  Add ctor taking a parent
	and an element.
	(call_string::~call_string): New.
	(call_string::recursive_log): New.
	* call-string.h (call_string::call_string): Move default ctor's
	defn to call-string.cc.  Delete copy ctor.  Add ctor taking a
	parent and an element.
	(call_string::operator=): Delete.
	(call_string::operator==): Delete.
	(call_string::hash): Delete.
	(call_string::push_call): Make const, returning the resulting
	call_string.
	(call_string::pop): Delete decl.
	(call_string::get_parent): New.
	(call_string::cmp_ptr_ptr): New decl.
	(call_string::get_top_of_stack): New.
	(struct call_string::hashmap_traits_t): New.
	(class call_string): Add friend class region_model_manager.  Add
	DISABLE_COPY_AND_ASSIGN.
	(call_string::~call_string): New decl.
	(call_string::recursive_log): New decl.
	(call_string::m_parent): New field.
	(call_string::m_children): New field.
	* constraint-manager.cc (selftest::test_many_constants): Pass
	model manager to program_point::origin.
	* engine.cc (exploded_graph::exploded_graph): Likewise.
	(exploded_graph::add_function_entry): Likewise for
	program_point::from_function_entry.
	(add_tainted_args_callback): Likewise.
	(exploded_graph::maybe_process_run_of_before_supernode_enodes):
	Update for change to program_point.get_call_string.
	(exploded_graph::process_node): Likewise.
	(class function_call_string_cluster): Convert m_cs from a
	call_string to a const call_string &.
	(struct function_call_string): Likewise.
	(pod_hash_traits<function_call_string>::hash): Use pointer_hash
	for m_cs.
	(pod_hash_traits<function_call_string>::equal): Update for change
	to m_cs.
	(root_cluster::add_node): Update for change to
	function_call_string.
	(viz_callgraph_node::dump_dot): Update for change to call_string.
	* exploded-graph.h (per_call_string_data::m_key): Convert to a
	reference.
	(struct eg_call_string_hash_map_traits): Delete.
	(exploded_graph::call_string_data_map_t): Remove traits class.
	* program-point.cc: Move include of "analyzer/call-string.h" to
	after "analyzer/analyzer-logging.h".
	(program_point::print): Update for conversion of m_call_string to
	a pointer.
	(program_point::to_json): Likewise.
	(program_point::push_to_call_stack): Update for immutability of
	call strings.
	(program_point::pop_from_call_stack): Likewise.
	(program_point::hash): Use pointer hashing for m_call_string.
	(program_point::get_function_at_depth): Update for change to
	m_call_string.
	(program_point::validate): Update for changes to call_string.
	(program_point::on_edge): Likewise.
	(program_point::origin): Move here from call-string.h.  Add
	region_model_manager param and use it to get empty call string.
	(program_point::from_function_entry): Likewise.
	(selftest::test_function_point_ordering): Likewise.
	(selftest::test_function_point_ordering): Likewise.
	* program-point.h (program_point::program_point): Update for
	change to m_call_string.
	(program_point::get_call_string): Likewise.
	(program_point::get_stack_depth): Likewise.
	(program_point::origin): Add region_model_manager param, and move
	defn to call-string.cc.
	(program_point::from_function_entry): Likewise.
	(program_point::empty): Drop call_string.
	(program_point::deleted): Likewise.
	(program_point::program_point): New private ctor.
	(program_point::m_call_string): Convert from call_string to const
	call_string *.
	* program-state.cc (selftest::test_program_state_merging): Update
	for call_string changes.
	(selftest::test_program_state_merging_2): Likewise.
	* region-model-manager.cc
	(region_model_manager::region_model_manager): Construct
	m_empty_call_string.
	(region_model_manager::log_stats): Log the call strings.
	* region-model.cc (assert_region_models_merge): Pass the
	region_model_manager when creating program_point instances.
	(selftest::test_state_merging): Likewise.
	(selftest::test_constraint_merging): Likewise.
	(selftest::test_widening_constraints): Likewise.
	(selftest::test_iteration_1): Likewise.
	* region-model.h (region_model_manager::get_empty_call_string):
	New.
	(region_model_manager::m_empty_call_string): New.
	* sm-signal.cc (register_signal_handler::impl_transition): Update
	for changes to call_string.

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

1 files changed, 44 insertions, 19 deletions

diff --git a/gcc/analyzer/program-point.cc b/gcc/analyzer/program-point.cc
index 8fa7066..6c296d5 100644
--- a/gcc/analyzer/program-point.cc
+++ b/gcc/analyzer/program-point.cc
@@ -25,7 +25,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-pretty-print.h"
 #include "gcc-rich-location.h"
 #include "json.h"
-#include "analyzer/call-string.h"
 #include "ordered-hash-map.h"
 #include "options.h"
 #include "cgraph.h"
@@ -37,6 +36,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "digraph.h"
 #include "analyzer/analyzer.h"
 #include "analyzer/analyzer-logging.h"
+#include "analyzer/call-string.h"
 #include "analyzer/supergraph.h"
 #include "analyzer/program-point.h"
 #include "sbitmap.h"
@@ -290,7 +290,7 @@ void
 program_point::print (pretty_printer *pp, const format &f) const
 {
   pp_string (pp, "callstring: ");
-  m_call_string.print (pp);
+  m_call_string->print (pp);
   f.spacer (pp);
 
   m_function_point.print (pp, f);
@@ -340,7 +340,7 @@ program_point::to_json () const
       break;
     }
 
-  point_obj->set ("call_string", m_call_string.to_json ());
+  point_obj->set ("call_string", m_call_string->to_json ());
 
   return point_obj;
 }
@@ -353,14 +353,15 @@ void
 program_point::push_to_call_stack (const supernode *caller,
 				   const supernode *callee)
 {
-  m_call_string.push_call (callee, caller);
+  m_call_string = m_call_string->push_call (callee, caller);
 }
 
 /* Pop the topmost call from the current callstack.  */
 void
 program_point::pop_from_call_stack ()
 {
-  m_call_string.pop ();
+  m_call_string = m_call_string->get_parent ();
+  gcc_assert (m_call_string);
 }
 
 /* Generate a hash value for this program_point.  */
@@ -370,7 +371,7 @@ program_point::hash () const
 {
   inchash::hash hstate;
   hstate.merge_hash (m_function_point.hash ());
-  hstate.merge_hash (m_call_string.hash ());
+  hstate.add_ptr (m_call_string);
   return hstate.end ();
 }
 
@@ -379,11 +380,11 @@ program_point::hash () const
 function *
 program_point::get_function_at_depth (unsigned depth) const
 {
-  gcc_assert (depth <= m_call_string.length ());
-  if (depth == m_call_string.length ())
+  gcc_assert (depth <= m_call_string->length ());
+  if (depth == m_call_string->length ())
     return m_function_point.get_function ();
   else
-    return m_call_string[depth].get_caller_function ();
+    return get_call_string ()[depth].get_caller_function ();
 }
 
 /* Assert that this object is sane.  */
@@ -396,12 +397,13 @@ program_point::validate () const
   return;
 #endif
 
-  m_call_string.validate ();
+  m_call_string->validate ();
   /* The "callee" of the final entry in the callstring should be the
      function of the m_function_point.  */
-  if (m_call_string.length () > 0)
-    gcc_assert (m_call_string[m_call_string.length () - 1].get_callee_function ()
-		== get_function ());
+  if (m_call_string->length () > 0)
+    gcc_assert
+      ((*m_call_string)[m_call_string->length () - 1].get_callee_function ()
+       == get_function ());
 }
 
 /* Check to see if SUCC is a valid edge to take (ensuring that we have
@@ -444,14 +446,15 @@ program_point::on_edge (exploded_graph &eg,
 	  }
 
 	/* Add the callsite to the call string.  */
-	m_call_string.push_call (eg.get_supergraph (), call_sedge);
+	m_call_string = m_call_string->push_call (eg.get_supergraph (),
+						  call_sedge);
 
 	/* Impose a maximum recursion depth and don't analyze paths
 	   that exceed it further.
 	   This is something of a blunt workaround, but it only
 	   applies to recursion (and mutual recursion), not to
 	   general call stacks.  */
-	if (m_call_string.calc_recursion_depth ()
+	if (m_call_string->calc_recursion_depth ()
 	    > param_analyzer_max_recursion_depth)
 	  {
 	    if (logger)
@@ -465,13 +468,15 @@ program_point::on_edge (exploded_graph &eg,
     case SUPEREDGE_RETURN:
       {
 	/* Require that we return to the call site in the call string.  */
-	if (m_call_string.empty_p ())
+	if (m_call_string->empty_p ())
 	  {
 	    if (logger)
 	      logger->log ("rejecting return edge: empty call string");
 	    return false;
 	  }
-	const call_string::element_t top_of_stack = m_call_string.pop ();
+	const call_string::element_t &top_of_stack
+	  = m_call_string->get_top_of_stack ();
+	m_call_string = m_call_string->get_parent ();
 	call_string::element_t current_call_string_element (succ->m_dest,
 							    succ->m_src);
 	if (top_of_stack != current_call_string_element)
@@ -669,6 +674,25 @@ function_point::get_next () const
     }
 }
 
+/* class program_point.  */
+
+program_point
+program_point::origin (const region_model_manager &mgr)
+{
+  return program_point (function_point (NULL, NULL,
+					0, PK_ORIGIN),
+			mgr.get_empty_call_string ());
+}
+
+program_point
+program_point::from_function_entry (const region_model_manager &mgr,
+				    const supergraph &sg,
+				    function *fun)
+{
+  return program_point (function_point::from_function_entry (sg, fun),
+			mgr.get_empty_call_string ());
+}
+
 /* For those program points for which there is a uniquely-defined
    successor, return it.  */
 
@@ -721,7 +745,6 @@ static void
 test_function_point_ordering ()
 {
   const supernode *snode = NULL;
-  const call_string call_string;
 
   /* Populate an array with various points within the same
      snode, in order.  */
@@ -756,9 +779,11 @@ test_function_point_ordering ()
 static void
 test_program_point_equality ()
 {
+  region_model_manager mgr;
+
   const supernode *snode = NULL;
 
-  const call_string cs;
+  const call_string &cs = mgr.get_empty_call_string ();
 
   program_point a = program_point::before_supernode (snode, NULL,
 						     cs);