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>

12 files changed, 282 insertions, 214 deletions

diff --git a/gcc/analyzer/call-string.cc b/gcc/analyzer/call-string.cc
index 2ccd3cc..a09f569 100644
--- a/gcc/analyzer/call-string.cc
+++ b/gcc/analyzer/call-string.cc
@@ -25,7 +25,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree.h"
 #include "options.h"
 #include "json.h"
-#include "analyzer/call-string.h"
 #include "ordered-hash-map.h"
 #include "options.h"
 #include "cgraph.h"
@@ -35,6 +34,9 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple.h"
 #include "gimple-iterator.h"
 #include "digraph.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/analyzer-logging.h"
+#include "analyzer/call-string.h"
 #include "analyzer/supergraph.h"
 
 #if ENABLE_ANALYZER
@@ -74,45 +76,6 @@ call_string::element_t::get_callee_function () const
   return m_callee->get_function ();
 }
 
-/* call_string's copy ctor.  */
-
-call_string::call_string (const call_string &other)
-: m_elements (other.m_elements.length ())
-{
-  for (const call_string::element_t &e : other.m_elements)
-    m_elements.quick_push (e);
-}
-
-/* call_string's assignment operator.  */
-
-call_string&
-call_string::operator= (const call_string &other)
-{
-  // would be much simpler if we could rely on vec<> assignment op
-  m_elements.truncate (0);
-  m_elements.reserve (other.m_elements.length (), true);
-  call_string::element_t *e;
-  int i;
-  FOR_EACH_VEC_ELT (other.m_elements, i, e)
-    m_elements.quick_push (*e);
-  return *this;
-}
-
-/* call_string's equality operator.  */
-
-bool
-call_string::operator== (const call_string &other) const
-{
-  if (m_elements.length () != other.m_elements.length ())
-    return false;
-  call_string::element_t *e;
-  int i;
-  FOR_EACH_VEC_ELT (m_elements, i, e)
-    if (*e != other.m_elements[i])
-      return false;
-  return true;
-}
-
 /* Print this to PP.  */
 
 void
@@ -160,43 +123,34 @@ call_string::to_json () const
   return arr;
 }
 
-/* Generate a hash value for this call_string.  */
+/* Get or create the call_string resulting from pushing the return
+   superedge for CALL_SEDGE onto the end of this call_string.  */
 
-hashval_t
-call_string::hash () const
-{
-  inchash::hash hstate;
-  for (const call_string::element_t &e : m_elements)
-    hstate.add_ptr (e.m_caller);
-  return hstate.end ();
-}
-
-/* Push the return superedge for CALL_SEDGE onto the end of this
-   call_string.  */
-
-void
+const call_string *
 call_string::push_call (const supergraph &sg,
-			const call_superedge *call_sedge)
+			const call_superedge *call_sedge) const
 {
   gcc_assert (call_sedge);
   const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
   gcc_assert (return_sedge);
-  call_string::element_t e (return_sedge->m_dest, return_sedge->m_src);
-  m_elements.safe_push (e);
+  return push_call (return_sedge->m_dest, return_sedge->m_src);
 }
 
-void
+/* Get or create the call_string resulting from pushing the call
+   (caller, callee) onto the end of this call_string.  */
+
+const call_string *
 call_string::push_call (const supernode *caller,
-			const supernode *callee)
+			const supernode *callee) const
 {
   call_string::element_t e (caller, callee);
-  m_elements.safe_push (e);
-}
 
-call_string::element_t
-call_string::pop ()
-{
-  return m_elements.pop();
+  if (const call_string **slot = m_children.get (e))
+    return *slot;
+
+  call_string *result = new call_string (*this, e);
+  m_children.put (e, result);
+  return result;
 }
 
 /* Count the number of times the top-most call site appears in the
@@ -260,6 +214,16 @@ call_string::cmp (const call_string &a,
     }
 }
 
+/* Comparator for use by vec<const call_string *>::qsort.  */
+
+int
+call_string::cmp_ptr_ptr (const void *pa, const void *pb)
+{
+  const call_string *cs_a = *static_cast <const call_string * const *> (pa);
+  const call_string *cs_b = *static_cast <const call_string * const *> (pb);
+  return cmp (*cs_a, *cs_b);
+}
+
 /* Return the pointer to callee of the topmost call in the stack,
    or NULL if stack is empty.  */
 const supernode *
@@ -290,6 +254,8 @@ call_string::validate () const
   return;
 #endif
 
+  gcc_assert (m_parent || m_elements.length () == 0);
+
   /* Each entry's "caller" should be the "callee" of the previous entry.  */
   call_string::element_t *e;
   int i;
@@ -299,4 +265,68 @@ call_string::validate () const
 		  m_elements[i - 1].get_callee_function ());
 }
 
+/* ctor for the root/empty call_string.  */
+
+call_string::call_string ()
+: m_parent (NULL), m_elements ()
+{
+}
+
+/* ctor for a child call_string.  */
+
+call_string::call_string (const call_string &parent, const element_t &to_push)
+: m_parent (&parent),
+  m_elements (parent.m_elements.length () + 1)
+{
+  m_elements.splice (parent.m_elements);
+  m_elements.quick_push (to_push);
+}
+
+/* dtor for call_string: recursively delete children.  */
+
+call_string::~call_string ()
+{
+  for (auto child_iter : m_children)
+    delete child_iter.second;
+}
+
+/* Log this call_string and all its descendents recursively to LOGGER,
+   using indentation and elision to highlight the hierarchy.  */
+
+void
+call_string::recursive_log (logger *logger) const
+{
+  logger->start_log_line ();
+  pretty_printer *pp = logger->get_printer ();
+  for (unsigned i = 0; i < length (); i++)
+    pp_string (pp, "  ");
+  if (length () > 0)
+    {
+      pp_string (pp, "[");
+      /* Elide all but the final element, since they are shared with
+	 the parent call_string.  */
+      for (unsigned i = 0; i < length (); i++)
+	pp_string (pp, "..., ");
+      /* Log the final element in detail.  */
+      const element_t *e = &m_elements[m_elements.length () - 1];
+      pp_printf (pp, "(SN: %i -> SN: %i in %s)]",
+		 e->m_callee->m_index, e->m_caller->m_index,
+		 function_name (e->m_caller->m_fun));
+    }
+  else
+    pp_string (pp, "[]");
+  logger->end_log_line ();
+
+  /* Recurse into children.  */
+  {
+    auto_vec<const call_string *> children (m_children.elements ());
+    for (auto iter : m_children)
+      children.safe_push (iter.second);
+    children.qsort (call_string::cmp_ptr_ptr);
+
+    for (auto iter : children)
+      iter->recursive_log (logger);
+  }
+}
+
 #endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/call-string.h b/gcc/analyzer/call-string.h
index 87d04a1..c3cea90 100644
--- a/gcc/analyzer/call-string.h
+++ b/gcc/analyzer/call-string.h
@@ -36,8 +36,13 @@ class return_superedge;
    i.e. that we return to the same callsite that called us.
 
    The class stores returning calls ( which may be represented by a
-   returning superedge ). We do so because this is what we need to compare 
-   against.  */
+   returning superedge ). We do so because this is what we need to compare
+   against.
+
+   Instances of call_string are consolidated by the region_model_manager,
+   which effectively owns them: it 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.  */
 
 class call_string
 {
@@ -60,38 +65,31 @@ public:
     /* Accessors */
     function *get_caller_function () const;
     function *get_callee_function () const;
-    
+
     const supernode *m_caller;
     const supernode *m_callee;
   };
 
-  call_string () : m_elements () {}
-  call_string (const call_string &other);
-  call_string& operator= (const call_string &other);
-
-  bool operator== (const call_string &other) const;
-
   void print (pretty_printer *pp) const;
 
   json::value *to_json () const;
 
-  hashval_t hash () const;
-
   bool empty_p () const { return m_elements.is_empty (); }
 
-  void push_call (const supergraph &sg,
-		  const call_superedge *sedge);
-
-  void push_call (const supernode *src, 
-    const supernode *dest);
+  const call_string *push_call (const supergraph &sg,
+				const call_superedge *sedge) const;
 
-  element_t pop ();
+  const call_string *push_call (const supernode *src,
+				const supernode *dest) const;
+  const call_string *get_parent () const { return m_parent; }
 
   int calc_recursion_depth () const;
 
   static int cmp (const call_string &a,
 		  const call_string &b);
 
+  static int cmp_ptr_ptr (const void *, const void *);
+
   /* Accessors */
 
   const supernode *get_callee_node () const;
@@ -101,11 +99,69 @@ public:
   {
     return m_elements[idx];
   }
+  const element_t &get_top_of_stack () const
+  {
+    gcc_assert (m_elements.length () > 0);
+    return m_elements[m_elements.length () - 1];
+  }
 
   void validate () const;
 
 private:
+  struct hashmap_traits_t
+  {
+    typedef element_t key_type;
+    typedef const call_string *value_type;
+
+    static const bool maybe_mx = false;
+    static inline hashval_t hash (const key_type &k)
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (k.m_caller);
+      hstate.add_ptr (k.m_callee);
+      return hstate.end ();
+    }
+    static inline bool equal_keys (const key_type &k1, const key_type &k2)
+    {
+      return k1 == k2;
+    }
+    template <typename T> static inline void remove (T &entry)
+    {
+      entry.m_key = element_t (NULL, NULL);
+    }
+    static const bool empty_zero_p = true;
+    template <typename T> static inline bool is_empty (const T &entry)
+    {
+      return entry.m_key.m_caller == NULL;
+    }
+    template <typename T> static inline bool is_deleted (const T &entry)
+    {
+      return entry.m_key.m_caller == reinterpret_cast<const supernode *> (1);
+    }
+    template <typename T> static inline void mark_empty (T &entry)
+    {
+      entry.m_key = element_t (NULL, NULL);
+      entry.m_value = NULL;
+    }
+    template <typename T> static inline void mark_deleted (T &entry)
+    {
+      entry.m_key.m_caller = reinterpret_cast<const supernode *> (1);
+    }
+  };
+
+  friend class region_model_manager;
+
+  DISABLE_COPY_AND_ASSIGN (call_string);
+
+  call_string ();
+  call_string (const call_string &parent, const element_t &to_push);
+  ~call_string ();
+
+  void recursive_log (logger *logger) const;
+
+  const call_string *m_parent;
   auto_vec<element_t> m_elements;
+  mutable hash_map<element_t, const call_string *, hashmap_traits_t> m_children;
 };
 
 } // namespace ana
diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc
index 02e8ce9..4133a13 100644
--- a/gcc/analyzer/constraint-manager.cc
+++ b/gcc/analyzer/constraint-manager.cc
@@ -3923,10 +3923,10 @@ test_equality ()
 static void
 test_many_constants ()
 {
-  program_point point (program_point::origin ());
+  region_model_manager mgr;
+  program_point point (program_point::origin (mgr));
   tree a = build_global_decl ("a", integer_type_node);
 
-  region_model_manager mgr;
   region_model model (&mgr);
   auto_vec<tree> constants;
   for (int i = 0; i < 20; i++)
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 51dfe29..0674c8b 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -2374,8 +2374,9 @@ exploded_graph::exploded_graph (const supergraph &sg, logger *logger,
   m_functionless_stats (m_sg.num_nodes ()),
   m_PK_AFTER_SUPERNODE_per_snode (m_sg.num_nodes ())
 {
-  m_origin = get_or_create_node (program_point::origin (),
-				 program_state (ext_state), NULL);
+  m_origin = get_or_create_node
+    (program_point::origin (*ext_state.get_model_manager ()),
+     program_state (ext_state), NULL);
   for (int i = 0; i < m_sg.num_nodes (); i++)
     m_PK_AFTER_SUPERNODE_per_snode.quick_push (i);
 }
@@ -2526,7 +2527,9 @@ exploded_graph::add_function_entry (function *fun)
       return NULL;
     }
 
-  program_point point = program_point::from_function_entry (m_sg, fun);
+  program_point point
+    = program_point::from_function_entry (*m_ext_state.get_model_manager (),
+					  m_sg, fun);
   program_state state (m_ext_state);
   state.push_frame (m_ext_state, fun);
 
@@ -2979,7 +2982,8 @@ add_tainted_args_callback (exploded_graph *eg, tree field, tree fndecl,
   gcc_assert (fun);
 
   program_point point
-    = program_point::from_function_entry (eg->get_supergraph (), fun);
+    = program_point::from_function_entry (*ext_state.get_model_manager (),
+					  eg->get_supergraph (), fun);
   program_state state (ext_state);
   state.push_frame (ext_state, fun);
 
@@ -3341,7 +3345,7 @@ maybe_process_run_of_before_supernode_enodes (exploded_node *enode)
 
       if (point_2.get_kind () == PK_BEFORE_SUPERNODE
 	  && point_2.get_supernode () == snode
-	  && point_2.get_call_string () == point.get_call_string ())
+	  && &point_2.get_call_string () == &point.get_call_string ())
 	{
 	  enodes.safe_push (enode_2);
 	  m_worklist.take_next ();
@@ -4048,7 +4052,7 @@ exploded_graph::process_node (exploded_node *node)
 	if ((is_an_exit_block && !found_a_superedge)
 	    && (!point.get_call_string ().empty_p ()))
 	  {
-	    const call_string cs = point.get_call_string ();
+	    const call_string &cs = point.get_call_string ();
 	    program_point next_point
 	      = program_point::before_supernode (cs.get_caller_node (),
 						 NULL,
@@ -4736,7 +4740,7 @@ private:
 class function_call_string_cluster : public exploded_cluster
 {
 public:
-  function_call_string_cluster (function *fun, call_string cs)
+  function_call_string_cluster (function *fun, const call_string &cs)
   : m_fun (fun), m_cs (cs) {}
 
   ~function_call_string_cluster ()
@@ -4811,7 +4815,7 @@ public:
 
 private:
   function *m_fun;
-  call_string m_cs;
+  const call_string &m_cs;
   typedef ordered_hash_map<const supernode *, supernode_cluster *> map_t;
   map_t m_map;
 };
@@ -4820,14 +4824,15 @@ private:
 
 struct function_call_string
 {
-  function_call_string (function *fun, call_string cs)
+  function_call_string (function *fun, const call_string *cs)
   : m_fun (fun), m_cs (cs)
   {
     gcc_assert (fun);
+    gcc_assert (cs);
   }
 
   function *m_fun;
-  call_string m_cs;
+  const call_string *m_cs;
 };
 
 } // namespace ana
@@ -4842,7 +4847,8 @@ template <>
 inline hashval_t
 pod_hash_traits<function_call_string>::hash (value_type v)
 {
-  return pointer_hash <function>::hash (v.m_fun) ^ v.m_cs.hash ();
+  return (pointer_hash <function>::hash (v.m_fun)
+	  ^ pointer_hash <const call_string>::hash (v.m_cs));
 }
 
 template <>
@@ -4850,7 +4856,7 @@ inline bool
 pod_hash_traits<function_call_string>::equal (const value_type &existing,
 					      const value_type &candidate)
 {
-  return existing.m_fun == candidate.m_fun && existing.m_cs == candidate.m_cs;
+  return existing.m_fun == candidate.m_fun && &existing.m_cs == &candidate.m_cs;
 }
 template <>
 inline void
@@ -4925,7 +4931,7 @@ public:
       }
 
     const call_string &cs = en->get_point ().get_call_string ();
-    function_call_string key (fun, cs);
+    function_call_string key (fun, &cs);
     function_call_string_cluster **slot = m_map.get (key);
     if (slot)
       (*slot)->add_node (en);
@@ -4939,11 +4945,6 @@ public:
   }
 
 private:
-  /* This can't be an ordered_hash_map, as we can't store vec<call_string>,
-     since it's not a POD; vec<>::quick_push has:
-       *slot = obj;
-     and the slot isn't initialized, so the assignment op dies when cleaning up
-     un-inited *slot (within the truncate call).  */
   typedef hash_map<function_call_string, function_call_string_cluster *> map_t;
   map_t m_map;
 
@@ -5319,7 +5320,7 @@ public:
 	    FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode)
 	      {
 		if (enode->get_point ().get_function () == m_fun
-		    && enode->get_point ().get_call_string () == *cs)
+		    && &enode->get_point ().get_call_string () == cs)
 		  num_enodes++;
 	      }
 	    if (num_enodes > 0)
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index 101f4f9..0613f55 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -599,65 +599,10 @@ struct per_call_string_data
   : m_key (key), m_stats (num_supernodes)
   {}
 
-  const call_string m_key;
+  const call_string &m_key;
   stats m_stats;
 };
 
-/* Traits class for storing per-call_string data within
-   an exploded_graph.  */
-
-struct eg_call_string_hash_map_traits
-{
-  typedef const call_string *key_type;
-  typedef per_call_string_data *value_type;
-  typedef per_call_string_data *compare_type;
-
-  static inline hashval_t hash (const key_type &k)
-  {
-    gcc_assert (k != NULL);
-    gcc_assert (k != reinterpret_cast<key_type> (1));
-    return k->hash ();
-  }
-  static inline bool equal_keys (const key_type &k1, const key_type &k2)
-  {
-    gcc_assert (k1 != NULL);
-    gcc_assert (k2 != NULL);
-    gcc_assert (k1 != reinterpret_cast<key_type> (1));
-    gcc_assert (k2 != reinterpret_cast<key_type> (1));
-    if (k1 && k2)
-      return *k1 == *k2;
-    else
-      /* Otherwise they must both be non-NULL.  */
-      return k1 == k2;
-  }
-  template <typename T>
-  static inline void remove (T &)
-  {
-    /* empty; the nodes are handled elsewhere.  */
-  }
-  template <typename T>
-  static inline void mark_deleted (T &entry)
-  {
-    entry.m_key = reinterpret_cast<key_type> (1);
-  }
-  template <typename T>
-  static inline void mark_empty (T &entry)
-  {
-    entry.m_key = NULL;
-  }
-  template <typename T>
-  static inline bool is_deleted (const T &entry)
-  {
-    return entry.m_key == reinterpret_cast<key_type> (1);
-  }
-  template <typename T>
-  static inline bool is_empty (const T &entry)
-  {
-    return entry.m_key == NULL;
-  }
-  static const bool empty_zero_p = false;
-};
-
 /* Data about a particular function within an exploded_graph.  */
 
 struct per_function_data
@@ -791,8 +736,8 @@ private:
 class exploded_graph : public digraph<eg_traits>
 {
 public:
-  typedef hash_map <const call_string *, per_call_string_data *,
-		    eg_call_string_hash_map_traits> call_string_data_map_t;
+  typedef hash_map <const call_string *,
+		    per_call_string_data *> call_string_data_map_t;
 
   exploded_graph (const supergraph &sg, logger *logger,
 		  const extrinsic_state &ext_state,
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);
diff --git a/gcc/analyzer/program-point.h b/gcc/analyzer/program-point.h
index 6084c9e..63f7224 100644
--- a/gcc/analyzer/program-point.h
+++ b/gcc/analyzer/program-point.h
@@ -174,7 +174,7 @@ public:
   program_point (const function_point &fn_point,
 		 const call_string &call_string)
   : m_function_point (fn_point),
-    m_call_string (call_string)
+    m_call_string (&call_string)
   {
   }
 
@@ -197,7 +197,7 @@ public:
   /* Accessors.  */
 
   const function_point &get_function_point () const { return m_function_point; }
-  const call_string &get_call_string () const { return m_call_string; }
+  const call_string &get_call_string () const { return *m_call_string; }
 
   const supernode *get_supernode () const
   {
@@ -242,23 +242,14 @@ public:
   {
     if (get_kind () == PK_ORIGIN)
       return 0;
-    return m_call_string.length () + 1;
+    return get_call_string ().length () + 1;
   }
 
   /* Factory functions for making various kinds of program_point.  */
-  static program_point origin ()
-  {
-    return program_point (function_point (NULL, NULL,
-					  0, PK_ORIGIN),
-			  call_string ());
-  }
-
-  static program_point from_function_entry (const supergraph &sg,
-					    function *fun)
-  {
-    return program_point (function_point::from_function_entry (sg, fun),
-			  call_string ());
-  }
+  static program_point origin (const region_model_manager &mgr);
+  static program_point from_function_entry (const region_model_manager &mgr,
+					    const supergraph &sg,
+					    function *fun);
 
   static program_point before_supernode (const supernode *supernode,
 					 const superedge *from_edge,
@@ -288,11 +279,11 @@ public:
 
   static program_point empty ()
   {
-    return program_point (function_point::empty (), call_string ());
+    return program_point (function_point::empty ());
   }
   static program_point deleted ()
   {
-    return program_point (function_point::deleted (), call_string ());
+    return program_point (function_point::deleted ());
   }
 
   bool on_edge (exploded_graph &eg, const superedge *succ);
@@ -306,8 +297,14 @@ public:
   program_point get_next () const;
 
  private:
+  program_point (const function_point &fn_point)
+  : m_function_point (fn_point),
+    m_call_string (NULL)
+  {
+  }
+
   function_point m_function_point;
-  call_string m_call_string;
+  const call_string *m_call_string;
 };
 
 } // namespace ana
diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 7ad581c..295c6ae 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -1668,12 +1668,12 @@ test_program_state_merging ()
      malloc sm-state, pointing to a region on the heap.  */
   tree p = build_global_decl ("p", ptr_type_node);
 
-  program_point point (program_point::origin ());
+  engine eng;
+  region_model_manager *mgr = eng.get_model_manager ();
+  program_point point (program_point::origin (*mgr));
   auto_delete_vec <state_machine> checkers;
   checkers.safe_push (make_malloc_state_machine (NULL));
-  engine eng;
   extrinsic_state ext_state (checkers, &eng);
-  region_model_manager *mgr = eng.get_model_manager ();
 
   program_state s0 (ext_state);
   uncertainty_t uncertainty;
@@ -1736,10 +1736,11 @@ test_program_state_merging ()
 static void
 test_program_state_merging_2 ()
 {
-  program_point point (program_point::origin ());
+  engine eng;
+  region_model_manager *mgr = eng.get_model_manager ();
+  program_point point (program_point::origin (*mgr));
   auto_delete_vec <state_machine> checkers;
   checkers.safe_push (make_signal_state_machine (NULL));
-  engine eng;
   extrinsic_state ext_state (checkers, &eng);
 
   const state_machine::state test_state_0 ("test state 0", 0);
diff --git a/gcc/analyzer/region-model-manager.cc b/gcc/analyzer/region-model-manager.cc
index 3377f15..17713b0 100644
--- a/gcc/analyzer/region-model-manager.cc
+++ b/gcc/analyzer/region-model-manager.cc
@@ -68,6 +68,7 @@ namespace ana {
 
 region_model_manager::region_model_manager (logger *logger)
 : m_logger (logger),
+  m_empty_call_string (),
   m_next_region_id (0),
   m_root_region (alloc_region_id ()),
   m_stack_region (alloc_region_id (), &m_root_region),
@@ -1748,6 +1749,8 @@ void
 region_model_manager::log_stats (logger *logger, bool show_objs) const
 {
   LOG_SCOPE (logger);
+  logger->log ("call string consolidation");
+  m_empty_call_string.recursive_log (logger);
   logger->log ("svalue consolidation");
   log_uniq_map (logger, show_objs, "constant_svalue", m_constants_map);
   log_uniq_map (logger, show_objs, "unknown_svalue", m_unknowns_map);
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 6b49719..5bd5dc7 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -5460,9 +5460,9 @@ assert_region_models_merge (tree expr, tree val_a, tree val_b,
 			     region_model *out_merged_model,
 			     const svalue **out_merged_svalue)
 {
-  program_point point (program_point::origin ());
-  test_region_model_context ctxt;
   region_model_manager *mgr = out_merged_model->get_manager ();
+  program_point point (program_point::origin (*mgr));
+  test_region_model_context ctxt;
   region_model model0 (mgr);
   region_model model1 (mgr);
   if (val_a)
@@ -5511,8 +5511,8 @@ test_state_merging ()
 		       ptr_type_node);
   DECL_CONTEXT (q) = test_fndecl;
 
-  program_point point (program_point::origin ());
   region_model_manager mgr;
+  program_point point (program_point::origin (mgr));
 
   {
     region_model model0 (&mgr);
@@ -5852,7 +5852,7 @@ test_constraint_merging ()
 
   /* They should be mergeable; the merged constraints should
      be: (0 <= x < n).  */
-  program_point point (program_point::origin ());
+  program_point point (program_point::origin (mgr));
   region_model merged (&mgr);
   ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged));
 
@@ -5873,12 +5873,12 @@ test_constraint_merging ()
 static void
 test_widening_constraints ()
 {
-  program_point point (program_point::origin ());
+  region_model_manager mgr;
+  program_point point (program_point::origin (mgr));
   tree int_0 = build_int_cst (integer_type_node, 0);
   tree int_m1 = build_int_cst (integer_type_node, -1);
   tree int_1 = build_int_cst (integer_type_node, 1);
   tree int_256 = build_int_cst (integer_type_node, 256);
-  region_model_manager mgr;
   test_region_model_context ctxt;
   const svalue *int_0_sval = mgr.get_or_create_constant_svalue (int_0);
   const svalue *int_1_sval = mgr.get_or_create_constant_svalue (int_1);
@@ -5988,7 +5988,8 @@ test_widening_constraints ()
 static void
 test_iteration_1 ()
 {
-  program_point point (program_point::origin ());
+  region_model_manager mgr;
+  program_point point (program_point::origin (mgr));
 
   tree int_0 = build_int_cst (integer_type_node, 0);
   tree int_1 = build_int_cst (integer_type_node, 1);
@@ -5996,7 +5997,6 @@ test_iteration_1 ()
   tree int_257 = build_int_cst (integer_type_node, 257);
   tree i = build_global_decl ("i", integer_type_node);
 
-  region_model_manager mgr;
   test_region_model_context ctxt;
 
   /* model0: i: 0.  */
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index 1bfa56a..129aad2 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -244,6 +244,12 @@ public:
   region_model_manager (logger *logger = NULL);
   ~region_model_manager ();
 
+  /* call_string consolidation.  */
+  const call_string &get_empty_call_string () const
+  {
+    return m_empty_call_string;
+  }
+
   /* svalue consolidation.  */
   const svalue *get_or_create_constant_svalue (tree cst_expr);
   const svalue *get_or_create_int_cst (tree type, poly_int64);
@@ -381,6 +387,8 @@ private:
 
   logger *m_logger;
 
+  const call_string m_empty_call_string;
+
   unsigned m_next_region_id;
   root_region m_root_region;
   stack_region m_stack_region;
diff --git a/gcc/analyzer/sm-signal.cc b/gcc/analyzer/sm-signal.cc
index 1f48a09..b601f45 100644
--- a/gcc/analyzer/sm-signal.cc
+++ b/gcc/analyzer/sm-signal.cc
@@ -266,11 +266,13 @@ public:
     function *handler_fun = DECL_STRUCT_FUNCTION (m_fndecl);
     if (!handler_fun)
       return;
+    const extrinsic_state &ext_state = eg->get_ext_state ();
     program_point entering_handler
-      = program_point::from_function_entry (eg->get_supergraph (),
+      = program_point::from_function_entry (*ext_state.get_model_manager (),
+					    eg->get_supergraph (),
 					    handler_fun);
 
-    program_state state_entering_handler (eg->get_ext_state ());
+    program_state state_entering_handler (ext_state);
     update_model_for_signal_handler (state_entering_handler.m_region_model,
 				     handler_fun);
     state_entering_handler.m_checker_states[sm_idx]->set_global_state