[PATCH] Analyzer: Refactor callstring to work with pairs of supernodes.

[PATCH] Analyzer: Refactor callstring to work with pairs of supernodes.

[Ankur Saini]

[-- Attachment #1: Type: text/plain, Size: 317 bytes --]

The patch generalises how analyzer's call_string tracks function calls, including the calls that doesn’t have an underlying call graph edge, making it possible to work with function calls which are not discovered by GCC's middle end.

Successfully bootstrapped and completed regress tests on x86_64-linux-gnu.


[-- Attachment #2: call_string.patch --]
[-- Type: application/octet-stream, Size: 14400 bytes --]

From 50702fd83b5f9031a4555d745d60311637692ade Mon Sep 17 00:00:00 2001
From: Ankur Saini <arsenic@sourceware.org>
Date: Sat, 3 Jul 2021 11:10:39 +0530
Subject: [PATCH] Analyzer: Refactor callstring to work with pairs of
 supernodes.
 
2021-07-12  Ankur Saini  <arsenic@sourceware.org>

gcc/analyzer/ChangeLog:
	* call-string.cc (call_string::element_t::operator==): New operator.
	(call_String::element_t::operator!=): New operator.
	(call_string::element_t::get_caller_function): New function.
	(call_string::element_t::get_callee_function): New function.
	(call_string::call_string): Refactor to Initialise m_elements.
	(call_string::operator=): Refactor to work with m_elements.
	(call_string::operator==): Likewise.
	(call_string::to_json): Likewise.
	(call_string::hash): Refactor to hash e.m_caller.
	(call_string::push_call): Refactor to work with m_elements.
	(call_string::push_call): New overload to push call via supernodes.
	(call_string::pop): Refactor to work with m_elements.
	(call_string::calc_recursion_depth): Likewise.
	(call_string::cmp): Likewise.
	(call_string::validate): Likewise.
	(call_string::operator[]): Likewise.
	* call-string.h (class supernode): New forward decl.
	(struct call_string::element_t): New struct.
	(call_string::call_string): Refactor to initialise m_elements.
	(call_string::bool empty_p): Refactor to work with m_elements.
	(call_string::get_callee_node): New decl.
	(call_string::get_caller_node): New decl.
	(m_elements): Replaces m_return_edges.
	* program-point.cc (program_point::get_function_at_depth): Refactor to
	work with new call-string format.
	(program_point::validate): Likewise.
	(program_point::on_edge): Likewise.
---
 gcc/analyzer/call-string.cc   | 147 +++++++++++++++++++++++++---------
 gcc/analyzer/call-string.h    |  54 ++++++++++---
 gcc/analyzer/program-point.cc |  10 ++-
 3 files changed, 159 insertions(+), 52 deletions(-)

diff --git a/gcc/analyzer/call-string.cc b/gcc/analyzer/call-string.cc
index 9f4f77ab3a9..2e7c8256cbb 100644
--- a/gcc/analyzer/call-string.cc
+++ b/gcc/analyzer/call-string.cc
@@ -45,13 +45,46 @@ along with GCC; see the file COPYING3.  If not see
 
 /* class call_string.  */
 
+/* struct call_string::element_t.  */
+
+/* call_string::element_t's equality operator.  */
+
+bool
+call_string::element_t::operator== (const call_string::element_t &other) const
+{
+  if (m_caller == other.m_caller && m_callee == other.m_callee)
+    return true;
+  return false;
+}
+
+/* call_string::element_t's inequality operator.  */
+bool
+call_string::element_t::operator!= (const call_string::element_t &other) const
+{
+  if (m_caller != other.m_caller || m_callee != other.m_callee)
+    return true;
+  return false;
+}
+
+function *
+call_string::element_t::get_caller_function () const
+{
+  return m_caller->get_function ();
+}
+
+function *
+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_return_edges (other.m_return_edges.length ())
+: m_elements (other.m_elements.length ())
 {
-  for (const return_superedge *e : other.m_return_edges)
-    m_return_edges.quick_push (e);
+  for (const call_string::element_t &e : other.m_elements)
+    m_elements.quick_push (e);
 }
 
 /* call_string's assignment operator.  */
@@ -60,12 +93,12 @@ call_string&
 call_string::operator= (const call_string &other)
 {
   // would be much simpler if we could rely on vec<> assignment op
-  m_return_edges.truncate (0);
-  m_return_edges.reserve (other.m_return_edges.length (), true);
-  const return_superedge *e;
+  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_return_edges, i, e)
-    m_return_edges.quick_push (e);
+  FOR_EACH_VEC_ELT (other.m_elements, i, e)
+    m_elements.quick_push (*e);
   return *this;
 }
 
@@ -74,12 +107,12 @@ call_string::operator= (const call_string &other)
 bool
 call_string::operator== (const call_string &other) const
 {
-  if (m_return_edges.length () != other.m_return_edges.length ())
+  if (m_elements.length () != other.m_elements.length ())
     return false;
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
-    if (e != other.m_return_edges[i])
+  FOR_EACH_VEC_ELT (m_elements, i, e)
+    if (*e != other.m_elements[i])
       return false;
   return true;
 }
@@ -91,15 +124,15 @@ call_string::print (pretty_printer *pp) const
 {
   pp_string (pp, "[");
 
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
+  FOR_EACH_VEC_ELT (m_elements, i, e)
     {
       if (i > 0)
 	pp_string (pp, ", ");
       pp_printf (pp, "(SN: %i -> SN: %i in %s)",
-		 e->m_src->m_index, e->m_dest->m_index,
-		 function_name (e->m_dest->m_fun));
+		 e->m_callee->m_index, e->m_caller->m_index,
+		 function_name (e->m_caller->m_fun));
     }
 
   pp_string (pp, "]");
@@ -109,22 +142,22 @@ call_string::print (pretty_printer *pp) const
    [{"src_snode_idx" : int,
      "dst_snode_idx" : int,
      "funcname" : str},
-     ...for each return_superedge in the callstring].  */
+     ...for each element in the callstring].  */
 
 json::value *
 call_string::to_json () const
 {
   json::array *arr = new json::array ();
 
-  for (const return_superedge *e : m_return_edges)
+  for (const call_string::element_t &e : m_elements)
     {
       json::object *e_obj = new json::object ();
       e_obj->set ("src_snode_idx",
-		  new json::integer_number (e->m_src->m_index));
+		  new json::integer_number (e.m_callee->m_index));
       e_obj->set ("dst_snode_idx",
-		  new json::integer_number (e->m_dest->m_index));
+		  new json::integer_number (e.m_caller->m_index));
       e_obj->set ("funcname",
-		  new json::string (function_name (e->m_dest->m_fun)));
+		  new json::string (function_name (e.m_caller->m_fun)));
       arr->append (e_obj);
     }
 
@@ -137,8 +170,8 @@ hashval_t
 call_string::hash () const
 {
   inchash::hash hstate;
-  for (const return_superedge *e : m_return_edges)
-    hstate.add_ptr (e);
+  for (const call_string::element_t &e : m_elements)
+    hstate.add_ptr (e.m_caller);
   return hstate.end ();
 }
 
@@ -152,22 +185,36 @@ call_string::push_call (const supergraph &sg,
   gcc_assert (call_sedge);
   const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
   gcc_assert (return_sedge);
-  m_return_edges.safe_push (return_sedge);
+  call_string::element_t e (return_sedge->m_dest, return_sedge->m_src);
+  m_elements.safe_push (e);
+}
+
+void
+call_string::push_call (const supernode *caller,
+			const supernode *callee)
+{
+  call_string::element_t e (caller, callee);
+  m_elements.safe_push (e);
+}
+
+call_string::element_t
+call_string::pop ()
+{
+  return m_elements.pop();
 }
 
 /* Count the number of times the top-most call site appears in the
    stack.  */
-
 int
 call_string::calc_recursion_depth () const
 {
-  if (m_return_edges.is_empty ())
+  if (m_elements.is_empty ())
     return 0;
-  const return_superedge *top_return_sedge
-    = m_return_edges[m_return_edges.length () - 1];
+  const call_string::element_t top_return_sedge 
+    = m_elements[m_elements.length () - 1];
 
   int result = 0;
-  for (const return_superedge *e : m_return_edges)
+  for (const call_string::element_t &e : m_elements)
     if (e == top_return_sedge)
       ++result;
   return result;
@@ -201,13 +248,15 @@ call_string::cmp (const call_string &a,
       if (i >= len_b)
 	return -1;
 
-      /* Otherwise, compare the edges.  */
-      const return_superedge *edge_a = a[i];
-      const return_superedge *edge_b = b[i];
-      int src_cmp = edge_a->m_src->m_index - edge_b->m_src->m_index;
+      /* Otherwise, compare the node pairs.  */
+      const call_string::element_t a_node_pair = a[i];
+      const call_string::element_t b_node_pair = b[i];
+      int src_cmp 
+      	= a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
       if (src_cmp)
 	return src_cmp;
-      int dest_cmp = edge_a->m_dest->m_index - edge_b->m_dest->m_index;
+      int dest_cmp 
+      	= a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
       if (dest_cmp)
 	return dest_cmp;
       i++;
@@ -215,6 +264,26 @@ call_string::cmp (const call_string &a,
     }
 }
 
+/* return the opinter to callee of the topmost call in the stack,
+   or NULL if stack is empty */
+const supernode *
+call_string::get_callee_node () const
+{
+  if(m_elements.is_empty ())
+    return NULL;
+  return m_elements[m_elements.length () - 1].m_callee;
+}
+
+/* return the pointer to caller of the topmost call in the stack,
+   or NULL if stack is empty */
+const supernode * 
+call_string::get_caller_node () const
+{
+  if(m_elements.is_empty ())
+    return NULL;
+  return m_elements[m_elements.length () - 1].m_caller;
+}
+
 /* Assert that this object is sane.  */
 
 void
@@ -226,12 +295,14 @@ call_string::validate () const
 #endif
 
   /* Each entry's "caller" should be the "callee" of the previous entry.  */
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
+  FOR_EACH_VEC_ELT (m_elements, i, e)
     if (i > 0)
-      gcc_assert (e->get_caller_function ()
-		  == m_return_edges[i - 1]->get_callee_function ());
+    {
+      gcc_assert (e->get_caller_function () == 
+      		  m_elements[i - 1].get_callee_function ());
+    }
 }
 
 #endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/call-string.h b/gcc/analyzer/call-string.h
index 7721571ed60..5d5f8080571 100644
--- a/gcc/analyzer/call-string.h
+++ b/gcc/analyzer/call-string.h
@@ -24,22 +24,48 @@ along with GCC; see the file COPYING3.  If not see
 namespace ana {
 
 class supergraph;
+class supernode;
 class call_superedge;
 class return_superedge;
 
+
 /* A string of return_superedge pointers, representing a call stack
    at a program point.
 
    This is used to ensure that we generate interprocedurally valid paths
-   i.e. that we return to the same callsite that called us.
+   i.e. that we return to the same callsite that called us. 
 
-   The class actually stores the return edges, rather than the call edges,
-   since that's what we need to compare against.  */
+   The class stores returing calls ( which may be represented by a 
+   returning superedge ). We do so because this is what we need to compare 
+   against. */
 
 class call_string
 {
 public:
-  call_string () : m_return_edges () {}
+  /* A struct representing an element in the call_string 
+
+   each element represnts a path from m_callee to m_caller which represents
+   returning from the called function */
+
+  struct element_t
+  {
+    element_t (const supernode *caller, const supernode *callee)
+    :  m_caller (caller), m_callee (callee)
+    {
+    }
+
+    bool operator== (const element_t &other) const;
+    bool operator!= (const element_t &other) const;
+
+    /* 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);
 
@@ -51,27 +77,35 @@ public:
 
   hashval_t hash () const;
 
-  bool empty_p () const { return m_return_edges.is_empty (); }
+  bool empty_p () const { return m_elements.is_empty (); }
 
   void push_call (const supergraph &sg,
 		  const call_superedge *sedge);
-  const return_superedge *pop () { return m_return_edges.pop (); }
+
+  void push_call (const supernode *src, 
+    const supernode *dest);
+
+  element_t pop ();
 
   int calc_recursion_depth () const;
 
   static int cmp (const call_string &a,
 		  const call_string &b);
 
-  unsigned length () const { return m_return_edges.length (); }
-  const return_superedge *operator[] (unsigned idx) const
+  /* Accessors */
+
+  const supernode *get_callee_node () const;
+  const supernode *get_caller_node () const;
+  unsigned length () const { return m_elements.length (); }
+  element_t operator[] (unsigned idx) const
   {
-    return m_return_edges[idx];
+    return m_elements[idx];
   }
 
   void validate () const;
 
 private:
-  auto_vec<const return_superedge *> m_return_edges;
+  auto_vec<element_t> m_elements;
 };
 
 } // namespace ana
diff --git a/gcc/analyzer/program-point.cc b/gcc/analyzer/program-point.cc
index d8cfc61975e..e3d35511551 100644
--- a/gcc/analyzer/program-point.cc
+++ b/gcc/analyzer/program-point.cc
@@ -343,7 +343,7 @@ program_point::get_function_at_depth (unsigned depth) const
   if (depth == m_call_string.length ())
     return m_function_point.get_function ();
   else
-    return m_call_string[depth]->get_caller_function ();
+    return m_call_string[depth].get_caller_function ();
 }
 
 /* Assert that this object is sane.  */
@@ -360,7 +360,7 @@ program_point::validate () const
   /* 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 ()
+    gcc_assert (m_call_string[m_call_string.length () - 1].get_callee_function ()
 		== get_function ());
 }
 
@@ -431,8 +431,10 @@ program_point::on_edge (exploded_graph &eg,
 	      logger->log ("rejecting return edge: empty call string");
 	    return false;
 	  }
-	const return_superedge *top_of_stack = m_call_string.pop ();
-	if (top_of_stack != succ)
+	const call_string::element_t top_of_stack = m_call_string.pop ();
+	call_string::element_t current_call_string_element (succ->m_src, 
+							    succ->m_dest);
+	if (top_of_stack != current_call_string_element)
 	  {
 	    if (logger)
 	      logger->log ("rejecting return edge: return to wrong callsite");
-- 
2.32.0


[-- Attachment #3: Type: text/plain, Size: 17 bytes --]



Thanks 
- Ankur

Re: [PATCH] Analyzer: Refactor callstring to work with pairs of supernodes.

[David Malcolm]

On Sat, 2021-07-24 at 15:22 +0530, Ankur Saini wrote:
> The patch generalises how analyzer's call_string tracks function calls,
> including the calls that doesn’t have an underlying call graph edge,
> making it possible to work with function calls which are not discovered
> by GCC's middle end.
> 
> Successfully bootstrapped and completed regress tests on x86_64-linux-
> gnu.

Great!

[...snip...]

I have some very minor nitpicks for you to fix before you commit this.
Sorry if this seems overly pedantic, but it's good to get into the
habit of following the project's coding conventions...

Sentences in comments should be captitalized, so:

> +/* return the opinter to callee of the topmost call in the stack,
      ~~~~~~~~~~~~~~~~~~
     "Return the pointer"

> +   or NULL if stack is empty */

Our convention is a trailing period/full-stop then two spaces, so:

      or NULL if stack is empty.  */

> +const supernode *
> +call_string::get_callee_node () const
> +{
> +  if(m_elements.is_empty ())
> +    return NULL;
> +  return m_elements[m_elements.length () - 1].m_callee;
> +}
> +
> +/* return the pointer to caller of the topmost call in the stack,
> +   or NULL if stack is empty */

Similarly, initial capital for "return" at the start of sentence, full-stop
at the end, then two spaces before terminating the comment.


> +const supernode * 
> +call_string::get_caller_node () const
> +{
> +  if(m_elements.is_empty ())
> +    return NULL;
> +  return m_elements[m_elements.length () - 1].m_caller;
> +}
> +

[...snip...]

>  /* A string of return_superedge pointers, representing a call stack
>     at a program point.
>  
>     This is used to ensure that we generate interprocedurally valid paths
> -   i.e. that we return to the same callsite that called us.
> +   i.e. that we return to the same callsite that called us.

The patch adds a trailing whitespace to the above line.  Please try to
avoid such unnecessary changes as they create noise in "git blame" and
other logs.

 
> -   The class actually stores the return edges, rather than the call edges,
> -   since that's what we need to compare against.  */
> +   The class stores returing calls ( which may be represented by a

Typo: "returing" -> "returning"


> +   returning superedge ). We do so because this is what we need to compare 
> +   against. */
>  
>  class call_string
>  {
>  public:
> -  call_string () : m_return_edges () {}
> +  /* A struct representing an element in the call_string 
> +
> +   each element represnts a path from m_callee to m_caller which represents
      ~~~~         ~~~~~~~~~
      Each         represents



> +   returning from the called function */
                                ~~~~~~~~~~~
				function.  */

[...snip...]

With those minor nitpicks, the patch is ready to commit, so please go
ahead and push it to trunk.

Thanks
Dave

Re: [PATCH] Analyzer: Refactor callstring to work with pairs of supernodes.

[Ankur Saini]

[-- Attachment #1: Type: text/plain, Size: 90 bytes --]

Here is the new patch after fixing all the issues pointed out in the previous version.


[-- Attachment #2: call_string.patch --]
[-- Type: application/octet-stream, Size: 14264 bytes --]

From 140a3bbf9b1bb620520de8c0c4d42f3ddf57b0b9 Mon Sep 17 00:00:00 2001
From: Ankur Saini <arsenic@sourceware.org>
Date: Sun, 25 Jul 2021 14:47:53 +0530
Subject: [PATCH] 2021-07-25  Ankur Saini  <arsenic@sourceware.org>

gcc/analyzer/ChangeLog:
	* call-string.cc (call_string::element_t::operator==): New operator.
	(call_String::element_t::operator!=): New operator.
	(call_string::element_t::get_caller_function): New function.
	(call_string::element_t::get_callee_function): New function.
	(call_string::call_string): Refactor to Initialise m_elements.
	(call_string::operator=): Refactor to work with m_elements.
	(call_string::operator==): Likewise.
	(call_string::to_json): Likewise.
	(call_string::hash): Refactor to hash e.m_caller.
	(call_string::push_call): Refactor to work with m_elements.
	(call_string::push_call): New overload to push call via supernodes.
	(call_string::pop): Refactor to work with m_elements.
	(call_string::calc_recursion_depth): Likewise.
	(call_string::cmp): Likewise.
	(call_string::validate): Likewise.
	(call_string::operator[]): Likewise.
	* call-string.h (class supernode): New forward decl.
	(struct call_string::element_t): New struct.
	(call_string::call_string): Refactor to initialise m_elements.
	(call_string::bool empty_p): Refactor to work with m_elements.
	(call_string::get_callee_node): New decl.
	(call_string::get_caller_node): New decl.
	(m_elements): Replaces m_return_edges.
	* program-point.cc (program_point::get_function_at_depth): Refactor to
	work with new call-string format.
	(program_point::validate): Likewise.
	(program_point::on_edge): Likewise.
---
 gcc/analyzer/call-string.cc   | 147 +++++++++++++++++++++++++---------
 gcc/analyzer/call-string.h    |  52 +++++++++---
 gcc/analyzer/program-point.cc |  10 ++-
 3 files changed, 158 insertions(+), 51 deletions(-)

diff --git a/gcc/analyzer/call-string.cc b/gcc/analyzer/call-string.cc
index 9f4f77ab3a9..f7bf286bc2c 100644
--- a/gcc/analyzer/call-string.cc
+++ b/gcc/analyzer/call-string.cc
@@ -45,13 +45,46 @@ along with GCC; see the file COPYING3.  If not see
 
 /* class call_string.  */
 
+/* struct call_string::element_t.  */
+
+/* call_string::element_t's equality operator.  */
+
+bool
+call_string::element_t::operator== (const call_string::element_t &other) const
+{
+  if (m_caller == other.m_caller && m_callee == other.m_callee)
+    return true;
+  return false;
+}
+
+/* call_string::element_t's inequality operator.  */
+bool
+call_string::element_t::operator!= (const call_string::element_t &other) const
+{
+  if (m_caller != other.m_caller || m_callee != other.m_callee)
+    return true;
+  return false;
+}
+
+function *
+call_string::element_t::get_caller_function () const
+{
+  return m_caller->get_function ();
+}
+
+function *
+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_return_edges (other.m_return_edges.length ())
+: m_elements (other.m_elements.length ())
 {
-  for (const return_superedge *e : other.m_return_edges)
-    m_return_edges.quick_push (e);
+  for (const call_string::element_t &e : other.m_elements)
+    m_elements.quick_push (e);
 }
 
 /* call_string's assignment operator.  */
@@ -60,12 +93,12 @@ call_string&
 call_string::operator= (const call_string &other)
 {
   // would be much simpler if we could rely on vec<> assignment op
-  m_return_edges.truncate (0);
-  m_return_edges.reserve (other.m_return_edges.length (), true);
-  const return_superedge *e;
+  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_return_edges, i, e)
-    m_return_edges.quick_push (e);
+  FOR_EACH_VEC_ELT (other.m_elements, i, e)
+    m_elements.quick_push (*e);
   return *this;
 }
 
@@ -74,12 +107,12 @@ call_string::operator= (const call_string &other)
 bool
 call_string::operator== (const call_string &other) const
 {
-  if (m_return_edges.length () != other.m_return_edges.length ())
+  if (m_elements.length () != other.m_elements.length ())
     return false;
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
-    if (e != other.m_return_edges[i])
+  FOR_EACH_VEC_ELT (m_elements, i, e)
+    if (*e != other.m_elements[i])
       return false;
   return true;
 }
@@ -91,15 +124,15 @@ call_string::print (pretty_printer *pp) const
 {
   pp_string (pp, "[");
 
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
+  FOR_EACH_VEC_ELT (m_elements, i, e)
     {
       if (i > 0)
 	pp_string (pp, ", ");
       pp_printf (pp, "(SN: %i -> SN: %i in %s)",
-		 e->m_src->m_index, e->m_dest->m_index,
-		 function_name (e->m_dest->m_fun));
+		 e->m_callee->m_index, e->m_caller->m_index,
+		 function_name (e->m_caller->m_fun));
     }
 
   pp_string (pp, "]");
@@ -109,22 +142,22 @@ call_string::print (pretty_printer *pp) const
    [{"src_snode_idx" : int,
      "dst_snode_idx" : int,
      "funcname" : str},
-     ...for each return_superedge in the callstring].  */
+     ...for each element in the callstring].  */
 
 json::value *
 call_string::to_json () const
 {
   json::array *arr = new json::array ();
 
-  for (const return_superedge *e : m_return_edges)
+  for (const call_string::element_t &e : m_elements)
     {
       json::object *e_obj = new json::object ();
       e_obj->set ("src_snode_idx",
-		  new json::integer_number (e->m_src->m_index));
+		  new json::integer_number (e.m_callee->m_index));
       e_obj->set ("dst_snode_idx",
-		  new json::integer_number (e->m_dest->m_index));
+		  new json::integer_number (e.m_caller->m_index));
       e_obj->set ("funcname",
-		  new json::string (function_name (e->m_dest->m_fun)));
+		  new json::string (function_name (e.m_caller->m_fun)));
       arr->append (e_obj);
     }
 
@@ -137,8 +170,8 @@ hashval_t
 call_string::hash () const
 {
   inchash::hash hstate;
-  for (const return_superedge *e : m_return_edges)
-    hstate.add_ptr (e);
+  for (const call_string::element_t &e : m_elements)
+    hstate.add_ptr (e.m_caller);
   return hstate.end ();
 }
 
@@ -152,22 +185,36 @@ call_string::push_call (const supergraph &sg,
   gcc_assert (call_sedge);
   const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
   gcc_assert (return_sedge);
-  m_return_edges.safe_push (return_sedge);
+  call_string::element_t e (return_sedge->m_dest, return_sedge->m_src);
+  m_elements.safe_push (e);
+}
+
+void
+call_string::push_call (const supernode *caller,
+			const supernode *callee)
+{
+  call_string::element_t e (caller, callee);
+  m_elements.safe_push (e);
+}
+
+call_string::element_t
+call_string::pop ()
+{
+  return m_elements.pop();
 }
 
 /* Count the number of times the top-most call site appears in the
    stack.  */
-
 int
 call_string::calc_recursion_depth () const
 {
-  if (m_return_edges.is_empty ())
+  if (m_elements.is_empty ())
     return 0;
-  const return_superedge *top_return_sedge
-    = m_return_edges[m_return_edges.length () - 1];
+  const call_string::element_t top_return_sedge 
+    = m_elements[m_elements.length () - 1];
 
   int result = 0;
-  for (const return_superedge *e : m_return_edges)
+  for (const call_string::element_t &e : m_elements)
     if (e == top_return_sedge)
       ++result;
   return result;
@@ -201,13 +248,15 @@ call_string::cmp (const call_string &a,
       if (i >= len_b)
 	return -1;
 
-      /* Otherwise, compare the edges.  */
-      const return_superedge *edge_a = a[i];
-      const return_superedge *edge_b = b[i];
-      int src_cmp = edge_a->m_src->m_index - edge_b->m_src->m_index;
+      /* Otherwise, compare the node pairs.  */
+      const call_string::element_t a_node_pair = a[i];
+      const call_string::element_t b_node_pair = b[i];
+      int src_cmp 
+      	= a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
       if (src_cmp)
 	return src_cmp;
-      int dest_cmp = edge_a->m_dest->m_index - edge_b->m_dest->m_index;
+      int dest_cmp 
+      	= a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
       if (dest_cmp)
 	return dest_cmp;
       i++;
@@ -215,6 +264,26 @@ call_string::cmp (const call_string &a,
     }
 }
 
+/* Return the pointer to callee of the topmost call in the stack,
+   or NULL if stack is empty.  */
+const supernode *
+call_string::get_callee_node () const
+{
+  if(m_elements.is_empty ())
+    return NULL;
+  return m_elements[m_elements.length () - 1].m_callee;
+}
+
+/* Return the pointer to caller of the topmost call in the stack,
+   or NULL if stack is empty.  */
+const supernode * 
+call_string::get_caller_node () const
+{
+  if(m_elements.is_empty ())
+    return NULL;
+  return m_elements[m_elements.length () - 1].m_caller;
+}
+
 /* Assert that this object is sane.  */
 
 void
@@ -226,12 +295,14 @@ call_string::validate () const
 #endif
 
   /* Each entry's "caller" should be the "callee" of the previous entry.  */
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
+  FOR_EACH_VEC_ELT (m_elements, i, e)
     if (i > 0)
-      gcc_assert (e->get_caller_function ()
-		  == m_return_edges[i - 1]->get_callee_function ());
+    {
+      gcc_assert (e->get_caller_function () == 
+      		  m_elements[i - 1].get_callee_function ());
+    }
 }
 
 #endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/call-string.h b/gcc/analyzer/call-string.h
index 7721571ed60..a1ac60db4e9 100644
--- a/gcc/analyzer/call-string.h
+++ b/gcc/analyzer/call-string.h
@@ -24,22 +24,48 @@ along with GCC; see the file COPYING3.  If not see
 namespace ana {
 
 class supergraph;
+class supernode;
 class call_superedge;
 class return_superedge;
 
+
 /* A string of return_superedge pointers, representing a call stack
    at a program point.
 
    This is used to ensure that we generate interprocedurally valid paths
    i.e. that we return to the same callsite that called us.
 
-   The class actually stores the return edges, rather than the call edges,
-   since that's what we need to compare against.  */
+   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.  */
 
 class call_string
 {
 public:
-  call_string () : m_return_edges () {}
+  /* A struct representing an element in the call_string.
+
+   Each element represents a path from m_callee to m_caller which represents
+   returning from function.  */
+
+  struct element_t
+  {
+    element_t (const supernode *caller, const supernode *callee)
+    :  m_caller (caller), m_callee (callee)
+    {
+    }
+
+    bool operator== (const element_t &other) const;
+    bool operator!= (const element_t &other) const;
+
+    /* 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);
 
@@ -51,27 +77,35 @@ public:
 
   hashval_t hash () const;
 
-  bool empty_p () const { return m_return_edges.is_empty (); }
+  bool empty_p () const { return m_elements.is_empty (); }
 
   void push_call (const supergraph &sg,
 		  const call_superedge *sedge);
-  const return_superedge *pop () { return m_return_edges.pop (); }
+
+  void push_call (const supernode *src, 
+    const supernode *dest);
+
+  element_t pop ();
 
   int calc_recursion_depth () const;
 
   static int cmp (const call_string &a,
 		  const call_string &b);
 
-  unsigned length () const { return m_return_edges.length (); }
-  const return_superedge *operator[] (unsigned idx) const
+  /* Accessors */
+
+  const supernode *get_callee_node () const;
+  const supernode *get_caller_node () const;
+  unsigned length () const { return m_elements.length (); }
+  element_t operator[] (unsigned idx) const
   {
-    return m_return_edges[idx];
+    return m_elements[idx];
   }
 
   void validate () const;
 
 private:
-  auto_vec<const return_superedge *> m_return_edges;
+  auto_vec<element_t> m_elements;
 };
 
 } // namespace ana
diff --git a/gcc/analyzer/program-point.cc b/gcc/analyzer/program-point.cc
index d8cfc61975e..e3d35511551 100644
--- a/gcc/analyzer/program-point.cc
+++ b/gcc/analyzer/program-point.cc
@@ -343,7 +343,7 @@ program_point::get_function_at_depth (unsigned depth) const
   if (depth == m_call_string.length ())
     return m_function_point.get_function ();
   else
-    return m_call_string[depth]->get_caller_function ();
+    return m_call_string[depth].get_caller_function ();
 }
 
 /* Assert that this object is sane.  */
@@ -360,7 +360,7 @@ program_point::validate () const
   /* 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 ()
+    gcc_assert (m_call_string[m_call_string.length () - 1].get_callee_function ()
 		== get_function ());
 }
 
@@ -431,8 +431,10 @@ program_point::on_edge (exploded_graph &eg,
 	      logger->log ("rejecting return edge: empty call string");
 	    return false;
 	  }
-	const return_superedge *top_of_stack = m_call_string.pop ();
-	if (top_of_stack != succ)
+	const call_string::element_t top_of_stack = m_call_string.pop ();
+	call_string::element_t current_call_string_element (succ->m_src, 
+							    succ->m_dest);
+	if (top_of_stack != current_call_string_element)
 	  {
 	    if (logger)
 	      logger->log ("rejecting return edge: return to wrong callsite");
-- 
2.32.0


[-- Attachment #3: Type: text/plain, Size: 260 bytes --]



—

Question :

1. The mail id I am using here to send the patch ( arsenic.secondary@gmail.com ) and the mail id in the patch ( arsenic@sourceware.org ) are different from one and other, will this affect the process in any ways ?


Thanks 
- Ankur

Re: [PATCH] Analyzer: Refactor callstring to work with pairs of supernodes.

[Prathamesh Kulkarni]

On Sun, 25 Jul 2021 at 16:03, Ankur Saini via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> Here is the new patch after fixing all the issues pointed out in the previous version.
Just a nitpick:

+/* call_string::element_t's inequality operator.  */
+bool
+call_string::element_t::operator!= (const call_string::element_t &other) const
+{
+  if (m_caller != other.m_caller || m_callee != other.m_callee)
+    return true;
+  return false;
+}

Since you define operator== above, perhaps just implement operator != as:
return !(*this == other) ?

Thanks,
Prathamesh
>
>
>
> —
>
> Question :
>
> 1. The mail id I am using here to send the patch ( arsenic.secondary@gmail.com ) and the mail id in the patch ( arsenic@sourceware.org ) are different from one and other, will this affect the process in any ways ?
>
>
> Thanks
> - Ankur

Re: [PATCH] Analyzer: Refactor callstring to work with pairs of supernodes.

[Ankur Saini]

> On 25-Jul-2021, at 7:59 PM, Prathamesh Kulkarni <prathamesh.kulkarni@linaro.org> wrote:
> 
> !(*this == other)

Thanks for the suggestion.

Here is the updated patch.



Thank you
- Ankur 

Re: [PATCH] Analyzer: Refactor callstring to work with pairs of supernodes.

[Ankur Saini]

[-- Attachment #1: Type: text/plain, Size: 98 bytes --]


Here is the latest patch after fixing all the nit picks and issues pointed out by everyone. 


[-- Attachment #2: call_string.patch --]
[-- Type: application/octet-stream, Size: 14159 bytes --]

From 35786a741f5b7180840fb098fc5643b6018b0050 Mon Sep 17 00:00:00 2001
From: Ankur Saini <arsenic@sourceware.org>
Date: Sun, 25 Jul 2021 14:47:53 +0530
Subject: [PATCH] 2021-07-25  Ankur Saini  <arsenic@sourceware.org>

gcc/analyzer/ChangeLog:
	* call-string.cc (call_string::element_t::operator==): New operator.
	(call_String::element_t::operator!=): New operator.
	(call_string::element_t::get_caller_function): New function.
	(call_string::element_t::get_callee_function): New function.
	(call_string::call_string): Refactor to Initialise m_elements.
	(call_string::operator=): Refactor to work with m_elements.
	(call_string::operator==): Likewise.
	(call_string::to_json): Likewise.
	(call_string::hash): Refactor to hash e.m_caller.
	(call_string::push_call): Refactor to work with m_elements.
	(call_string::push_call): New overload to push call via supernodes.
	(call_string::pop): Refactor to work with m_elements.
	(call_string::calc_recursion_depth): Likewise.
	(call_string::cmp): Likewise.
	(call_string::validate): Likewise.
	(call_string::operator[]): Likewise.
	* call-string.h (class supernode): New forward decl.
	(struct call_string::element_t): New struct.
	(call_string::call_string): Refactor to initialise m_elements.
	(call_string::bool empty_p): Refactor to work with m_elements.
	(call_string::get_callee_node): New decl.
	(call_string::get_caller_node): New decl.
	(m_elements): Replaces m_return_edges.
	* program-point.cc (program_point::get_function_at_depth): Refactor to
	work with new call-string format.
	(program_point::validate): Likewise.
	(program_point::on_edge): Likewise.
---
 gcc/analyzer/call-string.cc   | 143 +++++++++++++++++++++++++---------
 gcc/analyzer/call-string.h    |  52 ++++++++++---
 gcc/analyzer/program-point.cc |  10 ++-
 3 files changed, 154 insertions(+), 51 deletions(-)

diff --git a/gcc/analyzer/call-string.cc b/gcc/analyzer/call-string.cc
index 9f4f77ab3a9..1e652a08a5a 100644
--- a/gcc/analyzer/call-string.cc
+++ b/gcc/analyzer/call-string.cc
@@ -45,13 +45,42 @@ along with GCC; see the file COPYING3.  If not see
 
 /* class call_string.  */
 
+/* struct call_string::element_t.  */
+
+/* call_string::element_t's equality operator.  */
+
+bool
+call_string::element_t::operator== (const call_string::element_t &other) const
+{
+  return (m_caller == other.m_caller && m_callee == other.m_callee);
+}
+
+/* call_string::element_t's inequality operator.  */
+bool
+call_string::element_t::operator!= (const call_string::element_t &other) const
+{
+  return !(*this == other);
+}
+
+function *
+call_string::element_t::get_caller_function () const
+{
+  return m_caller->get_function ();
+}
+
+function *
+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_return_edges (other.m_return_edges.length ())
+: m_elements (other.m_elements.length ())
 {
-  for (const return_superedge *e : other.m_return_edges)
-    m_return_edges.quick_push (e);
+  for (const call_string::element_t &e : other.m_elements)
+    m_elements.quick_push (e);
 }
 
 /* call_string's assignment operator.  */
@@ -60,12 +89,12 @@ call_string&
 call_string::operator= (const call_string &other)
 {
   // would be much simpler if we could rely on vec<> assignment op
-  m_return_edges.truncate (0);
-  m_return_edges.reserve (other.m_return_edges.length (), true);
-  const return_superedge *e;
+  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_return_edges, i, e)
-    m_return_edges.quick_push (e);
+  FOR_EACH_VEC_ELT (other.m_elements, i, e)
+    m_elements.quick_push (*e);
   return *this;
 }
 
@@ -74,12 +103,12 @@ call_string::operator= (const call_string &other)
 bool
 call_string::operator== (const call_string &other) const
 {
-  if (m_return_edges.length () != other.m_return_edges.length ())
+  if (m_elements.length () != other.m_elements.length ())
     return false;
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
-    if (e != other.m_return_edges[i])
+  FOR_EACH_VEC_ELT (m_elements, i, e)
+    if (*e != other.m_elements[i])
       return false;
   return true;
 }
@@ -91,15 +120,15 @@ call_string::print (pretty_printer *pp) const
 {
   pp_string (pp, "[");
 
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
+  FOR_EACH_VEC_ELT (m_elements, i, e)
     {
       if (i > 0)
 	pp_string (pp, ", ");
       pp_printf (pp, "(SN: %i -> SN: %i in %s)",
-		 e->m_src->m_index, e->m_dest->m_index,
-		 function_name (e->m_dest->m_fun));
+		 e->m_callee->m_index, e->m_caller->m_index,
+		 function_name (e->m_caller->m_fun));
     }
 
   pp_string (pp, "]");
@@ -109,22 +138,22 @@ call_string::print (pretty_printer *pp) const
    [{"src_snode_idx" : int,
      "dst_snode_idx" : int,
      "funcname" : str},
-     ...for each return_superedge in the callstring].  */
+     ...for each element in the callstring].  */
 
 json::value *
 call_string::to_json () const
 {
   json::array *arr = new json::array ();
 
-  for (const return_superedge *e : m_return_edges)
+  for (const call_string::element_t &e : m_elements)
     {
       json::object *e_obj = new json::object ();
       e_obj->set ("src_snode_idx",
-		  new json::integer_number (e->m_src->m_index));
+		  new json::integer_number (e.m_callee->m_index));
       e_obj->set ("dst_snode_idx",
-		  new json::integer_number (e->m_dest->m_index));
+		  new json::integer_number (e.m_caller->m_index));
       e_obj->set ("funcname",
-		  new json::string (function_name (e->m_dest->m_fun)));
+		  new json::string (function_name (e.m_caller->m_fun)));
       arr->append (e_obj);
     }
 
@@ -137,8 +166,8 @@ hashval_t
 call_string::hash () const
 {
   inchash::hash hstate;
-  for (const return_superedge *e : m_return_edges)
-    hstate.add_ptr (e);
+  for (const call_string::element_t &e : m_elements)
+    hstate.add_ptr (e.m_caller);
   return hstate.end ();
 }
 
@@ -152,22 +181,36 @@ call_string::push_call (const supergraph &sg,
   gcc_assert (call_sedge);
   const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
   gcc_assert (return_sedge);
-  m_return_edges.safe_push (return_sedge);
+  call_string::element_t e (return_sedge->m_dest, return_sedge->m_src);
+  m_elements.safe_push (e);
+}
+
+void
+call_string::push_call (const supernode *caller,
+			const supernode *callee)
+{
+  call_string::element_t e (caller, callee);
+  m_elements.safe_push (e);
+}
+
+call_string::element_t
+call_string::pop ()
+{
+  return m_elements.pop();
 }
 
 /* Count the number of times the top-most call site appears in the
    stack.  */
-
 int
 call_string::calc_recursion_depth () const
 {
-  if (m_return_edges.is_empty ())
+  if (m_elements.is_empty ())
     return 0;
-  const return_superedge *top_return_sedge
-    = m_return_edges[m_return_edges.length () - 1];
+  const call_string::element_t top_return_sedge 
+    = m_elements[m_elements.length () - 1];
 
   int result = 0;
-  for (const return_superedge *e : m_return_edges)
+  for (const call_string::element_t &e : m_elements)
     if (e == top_return_sedge)
       ++result;
   return result;
@@ -201,13 +244,15 @@ call_string::cmp (const call_string &a,
       if (i >= len_b)
 	return -1;
 
-      /* Otherwise, compare the edges.  */
-      const return_superedge *edge_a = a[i];
-      const return_superedge *edge_b = b[i];
-      int src_cmp = edge_a->m_src->m_index - edge_b->m_src->m_index;
+      /* Otherwise, compare the node pairs.  */
+      const call_string::element_t a_node_pair = a[i];
+      const call_string::element_t b_node_pair = b[i];
+      int src_cmp 
+      	= a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
       if (src_cmp)
 	return src_cmp;
-      int dest_cmp = edge_a->m_dest->m_index - edge_b->m_dest->m_index;
+      int dest_cmp 
+      	= a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
       if (dest_cmp)
 	return dest_cmp;
       i++;
@@ -215,6 +260,26 @@ call_string::cmp (const call_string &a,
     }
 }
 
+/* Return the pointer to callee of the topmost call in the stack,
+   or NULL if stack is empty.  */
+const supernode *
+call_string::get_callee_node () const
+{
+  if(m_elements.is_empty ())
+    return NULL;
+  return m_elements[m_elements.length () - 1].m_callee;
+}
+
+/* Return the pointer to caller of the topmost call in the stack,
+   or NULL if stack is empty.  */
+const supernode * 
+call_string::get_caller_node () const
+{
+  if(m_elements.is_empty ())
+    return NULL;
+  return m_elements[m_elements.length () - 1].m_caller;
+}
+
 /* Assert that this object is sane.  */
 
 void
@@ -226,12 +291,14 @@ call_string::validate () const
 #endif
 
   /* Each entry's "caller" should be the "callee" of the previous entry.  */
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
+  FOR_EACH_VEC_ELT (m_elements, i, e)
     if (i > 0)
-      gcc_assert (e->get_caller_function ()
-		  == m_return_edges[i - 1]->get_callee_function ());
+    {
+      gcc_assert (e->get_caller_function () == 
+      		  m_elements[i - 1].get_callee_function ());
+    }
 }
 
 #endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/call-string.h b/gcc/analyzer/call-string.h
index 7721571ed60..a1ac60db4e9 100644
--- a/gcc/analyzer/call-string.h
+++ b/gcc/analyzer/call-string.h
@@ -24,22 +24,48 @@ along with GCC; see the file COPYING3.  If not see
 namespace ana {
 
 class supergraph;
+class supernode;
 class call_superedge;
 class return_superedge;
 
+
 /* A string of return_superedge pointers, representing a call stack
    at a program point.
 
    This is used to ensure that we generate interprocedurally valid paths
    i.e. that we return to the same callsite that called us.
 
-   The class actually stores the return edges, rather than the call edges,
-   since that's what we need to compare against.  */
+   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.  */
 
 class call_string
 {
 public:
-  call_string () : m_return_edges () {}
+  /* A struct representing an element in the call_string.
+
+   Each element represents a path from m_callee to m_caller which represents
+   returning from function.  */
+
+  struct element_t
+  {
+    element_t (const supernode *caller, const supernode *callee)
+    :  m_caller (caller), m_callee (callee)
+    {
+    }
+
+    bool operator== (const element_t &other) const;
+    bool operator!= (const element_t &other) const;
+
+    /* 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);
 
@@ -51,27 +77,35 @@ public:
 
   hashval_t hash () const;
 
-  bool empty_p () const { return m_return_edges.is_empty (); }
+  bool empty_p () const { return m_elements.is_empty (); }
 
   void push_call (const supergraph &sg,
 		  const call_superedge *sedge);
-  const return_superedge *pop () { return m_return_edges.pop (); }
+
+  void push_call (const supernode *src, 
+    const supernode *dest);
+
+  element_t pop ();
 
   int calc_recursion_depth () const;
 
   static int cmp (const call_string &a,
 		  const call_string &b);
 
-  unsigned length () const { return m_return_edges.length (); }
-  const return_superedge *operator[] (unsigned idx) const
+  /* Accessors */
+
+  const supernode *get_callee_node () const;
+  const supernode *get_caller_node () const;
+  unsigned length () const { return m_elements.length (); }
+  element_t operator[] (unsigned idx) const
   {
-    return m_return_edges[idx];
+    return m_elements[idx];
   }
 
   void validate () const;
 
 private:
-  auto_vec<const return_superedge *> m_return_edges;
+  auto_vec<element_t> m_elements;
 };
 
 } // namespace ana
diff --git a/gcc/analyzer/program-point.cc b/gcc/analyzer/program-point.cc
index d73b6211141..d9f50daeb3c 100644
--- a/gcc/analyzer/program-point.cc
+++ b/gcc/analyzer/program-point.cc
@@ -350,7 +350,7 @@ program_point::get_function_at_depth (unsigned depth) const
   if (depth == m_call_string.length ())
     return m_function_point.get_function ();
   else
-    return m_call_string[depth]->get_caller_function ();
+    return m_call_string[depth].get_caller_function ();
 }
 
 /* Assert that this object is sane.  */
@@ -367,7 +367,7 @@ program_point::validate () const
   /* 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 ()
+    gcc_assert (m_call_string[m_call_string.length () - 1].get_callee_function ()
 		== get_function ());
 }
 
@@ -438,8 +438,10 @@ program_point::on_edge (exploded_graph &eg,
 	      logger->log ("rejecting return edge: empty call string");
 	    return false;
 	  }
-	const return_superedge *top_of_stack = m_call_string.pop ();
-	if (top_of_stack != succ)
+	const call_string::element_t top_of_stack = m_call_string.pop ();
+	call_string::element_t current_call_string_element (succ->m_dest,
+							    succ->m_src);
+	if (top_of_stack != current_call_string_element)
 	  {
 	    if (logger)
 	      logger->log ("rejecting return edge: return to wrong callsite");
-- 
2.32.0


[-- Attachment #3: Type: text/plain, Size: 21 bytes --]



Thanks you 
- Ankur

Re: [PATCH] Analyzer: Refactor callstring to work with pairs of supernodes.

[David Malcolm]

On Mon, 2021-07-26 at 21:04 +0530, Ankur Saini wrote:
> 
> Here is the latest patch after fixing all the nit picks and issues
> pointed out by everyone. 
> 

Looks good to me.

Thanks
Dave

[PATCH] Analyzer: Refactor callstring to work with pairs of supernodes.

[Ankur Saini]

2021-07-12  Ankur Saini  <arsenic@sourceware.org>

gcc/analyzer/ChangeLog:
	* call-string.cc (call_string::element_t::operator==): New operator.
	(call_String::element_t::operator!=): New operator.
	(call_string::element_t::get_caller_function): New function.
	(call_string::element_t::get_callee_function): New function.
	(call_string::call_string): Refactor to Initialise m_elements.
	(call_string::operator=): Refactor to work with m_elements.
	(call_string::operator==): Likewise.
	(call_string::to_json): Likewise.
	(call_string::hash): Refactor to hash e.m_caller.
	(call_string::push_call): Refactor to work with m_elements.
	(call_string::push_call): New overload to push call via supernodes.
	(call_string::pop): Refactor to work with m_elements.
	(call_string::calc_recursion_depth): Likewise.
	(call_string::cmp): Likewise.
	(call_string::validate): Likewise.
	(call_string::operator[]): Likewise.
	* call-string.h (class supernode): New forward decl.
	(struct call_string::element_t): New struct.
	(call_string::call_string): Refactor to initialise m_elements.
	(call_string::bool empty_p): Refactor to work with m_elements.
	(call_string::get_callee_node): New decl.
	(call_string::get_caller_node): New decl.
	(m_elements): Replaces m_return_edges.
	* program-point.cc (program_point::get_function_at_depth): Refactor to
	work with new call-string format.
	(program_point::validate): Likewise.
	(program_point::on_edge): Likewise.
---
 gcc/analyzer/call-string.cc   | 147 +++++++++++++++++++++++++---------
 gcc/analyzer/call-string.h    |  54 ++++++++++---
 gcc/analyzer/program-point.cc |  10 ++-
 3 files changed, 159 insertions(+), 52 deletions(-)

diff --git a/gcc/analyzer/call-string.cc b/gcc/analyzer/call-string.cc
index 9f4f77ab3a9..2e7c8256cbb 100644
--- a/gcc/analyzer/call-string.cc
+++ b/gcc/analyzer/call-string.cc
@@ -45,13 +45,46 @@ along with GCC; see the file COPYING3.  If not see
 
 /* class call_string.  */
 
+/* struct call_string::element_t.  */
+
+/* call_string::element_t's equality operator.  */
+
+bool
+call_string::element_t::operator== (const call_string::element_t &other) const
+{
+  if (m_caller == other.m_caller && m_callee == other.m_callee)
+    return true;
+  return false;
+}
+
+/* call_string::element_t's inequality operator.  */
+bool
+call_string::element_t::operator!= (const call_string::element_t &other) const
+{
+  if (m_caller != other.m_caller || m_callee != other.m_callee)
+    return true;
+  return false;
+}
+
+function *
+call_string::element_t::get_caller_function () const
+{
+  return m_caller->get_function ();
+}
+
+function *
+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_return_edges (other.m_return_edges.length ())
+: m_elements (other.m_elements.length ())
 {
-  for (const return_superedge *e : other.m_return_edges)
-    m_return_edges.quick_push (e);
+  for (const call_string::element_t &e : other.m_elements)
+    m_elements.quick_push (e);
 }
 
 /* call_string's assignment operator.  */
@@ -60,12 +93,12 @@ call_string&
 call_string::operator= (const call_string &other)
 {
   // would be much simpler if we could rely on vec<> assignment op
-  m_return_edges.truncate (0);
-  m_return_edges.reserve (other.m_return_edges.length (), true);
-  const return_superedge *e;
+  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_return_edges, i, e)
-    m_return_edges.quick_push (e);
+  FOR_EACH_VEC_ELT (other.m_elements, i, e)
+    m_elements.quick_push (*e);
   return *this;
 }
 
@@ -74,12 +107,12 @@ call_string::operator= (const call_string &other)
 bool
 call_string::operator== (const call_string &other) const
 {
-  if (m_return_edges.length () != other.m_return_edges.length ())
+  if (m_elements.length () != other.m_elements.length ())
     return false;
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
-    if (e != other.m_return_edges[i])
+  FOR_EACH_VEC_ELT (m_elements, i, e)
+    if (*e != other.m_elements[i])
       return false;
   return true;
 }
@@ -91,15 +124,15 @@ call_string::print (pretty_printer *pp) const
 {
   pp_string (pp, "[");
 
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
+  FOR_EACH_VEC_ELT (m_elements, i, e)
     {
       if (i > 0)
 	pp_string (pp, ", ");
       pp_printf (pp, "(SN: %i -> SN: %i in %s)",
-		 e->m_src->m_index, e->m_dest->m_index,
-		 function_name (e->m_dest->m_fun));
+		 e->m_callee->m_index, e->m_caller->m_index,
+		 function_name (e->m_caller->m_fun));
     }
 
   pp_string (pp, "]");
@@ -109,22 +142,22 @@ call_string::print (pretty_printer *pp) const
    [{"src_snode_idx" : int,
      "dst_snode_idx" : int,
      "funcname" : str},
-     ...for each return_superedge in the callstring].  */
+     ...for each element in the callstring].  */
 
 json::value *
 call_string::to_json () const
 {
   json::array *arr = new json::array ();
 
-  for (const return_superedge *e : m_return_edges)
+  for (const call_string::element_t &e : m_elements)
     {
       json::object *e_obj = new json::object ();
       e_obj->set ("src_snode_idx",
-		  new json::integer_number (e->m_src->m_index));
+		  new json::integer_number (e.m_callee->m_index));
       e_obj->set ("dst_snode_idx",
-		  new json::integer_number (e->m_dest->m_index));
+		  new json::integer_number (e.m_caller->m_index));
       e_obj->set ("funcname",
-		  new json::string (function_name (e->m_dest->m_fun)));
+		  new json::string (function_name (e.m_caller->m_fun)));
       arr->append (e_obj);
     }
 
@@ -137,8 +170,8 @@ hashval_t
 call_string::hash () const
 {
   inchash::hash hstate;
-  for (const return_superedge *e : m_return_edges)
-    hstate.add_ptr (e);
+  for (const call_string::element_t &e : m_elements)
+    hstate.add_ptr (e.m_caller);
   return hstate.end ();
 }
 
@@ -152,22 +185,36 @@ call_string::push_call (const supergraph &sg,
   gcc_assert (call_sedge);
   const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
   gcc_assert (return_sedge);
-  m_return_edges.safe_push (return_sedge);
+  call_string::element_t e (return_sedge->m_dest, return_sedge->m_src);
+  m_elements.safe_push (e);
+}
+
+void
+call_string::push_call (const supernode *caller,
+			const supernode *callee)
+{
+  call_string::element_t e (caller, callee);
+  m_elements.safe_push (e);
+}
+
+call_string::element_t
+call_string::pop ()
+{
+  return m_elements.pop();
 }
 
 /* Count the number of times the top-most call site appears in the
    stack.  */
-
 int
 call_string::calc_recursion_depth () const
 {
-  if (m_return_edges.is_empty ())
+  if (m_elements.is_empty ())
     return 0;
-  const return_superedge *top_return_sedge
-    = m_return_edges[m_return_edges.length () - 1];
+  const call_string::element_t top_return_sedge 
+    = m_elements[m_elements.length () - 1];
 
   int result = 0;
-  for (const return_superedge *e : m_return_edges)
+  for (const call_string::element_t &e : m_elements)
     if (e == top_return_sedge)
       ++result;
   return result;
@@ -201,13 +248,15 @@ call_string::cmp (const call_string &a,
       if (i >= len_b)
 	return -1;
 
-      /* Otherwise, compare the edges.  */
-      const return_superedge *edge_a = a[i];
-      const return_superedge *edge_b = b[i];
-      int src_cmp = edge_a->m_src->m_index - edge_b->m_src->m_index;
+      /* Otherwise, compare the node pairs.  */
+      const call_string::element_t a_node_pair = a[i];
+      const call_string::element_t b_node_pair = b[i];
+      int src_cmp 
+      	= a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
       if (src_cmp)
 	return src_cmp;
-      int dest_cmp = edge_a->m_dest->m_index - edge_b->m_dest->m_index;
+      int dest_cmp 
+      	= a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
       if (dest_cmp)
 	return dest_cmp;
       i++;
@@ -215,6 +264,26 @@ call_string::cmp (const call_string &a,
     }
 }
 
+/* return the opinter to callee of the topmost call in the stack,
+   or NULL if stack is empty */
+const supernode *
+call_string::get_callee_node () const
+{
+  if(m_elements.is_empty ())
+    return NULL;
+  return m_elements[m_elements.length () - 1].m_callee;
+}
+
+/* return the pointer to caller of the topmost call in the stack,
+   or NULL if stack is empty */
+const supernode * 
+call_string::get_caller_node () const
+{
+  if(m_elements.is_empty ())
+    return NULL;
+  return m_elements[m_elements.length () - 1].m_caller;
+}
+
 /* Assert that this object is sane.  */
 
 void
@@ -226,12 +295,14 @@ call_string::validate () const
 #endif
 
   /* Each entry's "caller" should be the "callee" of the previous entry.  */
-  const return_superedge *e;
+  call_string::element_t *e;
   int i;
-  FOR_EACH_VEC_ELT (m_return_edges, i, e)
+  FOR_EACH_VEC_ELT (m_elements, i, e)
     if (i > 0)
-      gcc_assert (e->get_caller_function ()
-		  == m_return_edges[i - 1]->get_callee_function ());
+    {
+      gcc_assert (e->get_caller_function () == 
+      		  m_elements[i - 1].get_callee_function ());
+    }
 }
 
 #endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/call-string.h b/gcc/analyzer/call-string.h
index 7721571ed60..5d5f8080571 100644
--- a/gcc/analyzer/call-string.h
+++ b/gcc/analyzer/call-string.h
@@ -24,22 +24,48 @@ along with GCC; see the file COPYING3.  If not see
 namespace ana {
 
 class supergraph;
+class supernode;
 class call_superedge;
 class return_superedge;
 
+
 /* A string of return_superedge pointers, representing a call stack
    at a program point.
 
    This is used to ensure that we generate interprocedurally valid paths
-   i.e. that we return to the same callsite that called us.
+   i.e. that we return to the same callsite that called us. 
 
-   The class actually stores the return edges, rather than the call edges,
-   since that's what we need to compare against.  */
+   The class stores returing calls ( which may be represented by a 
+   returning superedge ). We do so because this is what we need to compare 
+   against. */
 
 class call_string
 {
 public:
-  call_string () : m_return_edges () {}
+  /* A struct representing an element in the call_string 
+
+   each element represnts a path from m_callee to m_caller which represents
+   returning from the called function */
+
+  struct element_t
+  {
+    element_t (const supernode *caller, const supernode *callee)
+    :  m_caller (caller), m_callee (callee)
+    {
+    }
+
+    bool operator== (const element_t &other) const;
+    bool operator!= (const element_t &other) const;
+
+    /* 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);
 
@@ -51,27 +77,35 @@ public:
 
   hashval_t hash () const;
 
-  bool empty_p () const { return m_return_edges.is_empty (); }
+  bool empty_p () const { return m_elements.is_empty (); }
 
   void push_call (const supergraph &sg,
 		  const call_superedge *sedge);
-  const return_superedge *pop () { return m_return_edges.pop (); }
+
+  void push_call (const supernode *src, 
+    const supernode *dest);
+
+  element_t pop ();
 
   int calc_recursion_depth () const;
 
   static int cmp (const call_string &a,
 		  const call_string &b);
 
-  unsigned length () const { return m_return_edges.length (); }
-  const return_superedge *operator[] (unsigned idx) const
+  /* Accessors */
+
+  const supernode *get_callee_node () const;
+  const supernode *get_caller_node () const;
+  unsigned length () const { return m_elements.length (); }
+  element_t operator[] (unsigned idx) const
   {
-    return m_return_edges[idx];
+    return m_elements[idx];
   }
 
   void validate () const;
 
 private:
-  auto_vec<const return_superedge *> m_return_edges;
+  auto_vec<element_t> m_elements;
 };
 
 } // namespace ana
diff --git a/gcc/analyzer/program-point.cc b/gcc/analyzer/program-point.cc
index d8cfc61975e..e3d35511551 100644
--- a/gcc/analyzer/program-point.cc
+++ b/gcc/analyzer/program-point.cc
@@ -343,7 +343,7 @@ program_point::get_function_at_depth (unsigned depth) const
   if (depth == m_call_string.length ())
     return m_function_point.get_function ();
   else
-    return m_call_string[depth]->get_caller_function ();
+    return m_call_string[depth].get_caller_function ();
 }
 
 /* Assert that this object is sane.  */
@@ -360,7 +360,7 @@ program_point::validate () const
   /* 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 ()
+    gcc_assert (m_call_string[m_call_string.length () - 1].get_callee_function ()
 		== get_function ());
 }
 
@@ -431,8 +431,10 @@ program_point::on_edge (exploded_graph &eg,
 	      logger->log ("rejecting return edge: empty call string");
 	    return false;
 	  }
-	const return_superedge *top_of_stack = m_call_string.pop ();
-	if (top_of_stack != succ)
+	const call_string::element_t top_of_stack = m_call_string.pop ();
+	call_string::element_t current_call_string_element (succ->m_src, 
+							    succ->m_dest);
+	if (top_of_stack != current_call_string_element)
 	  {
 	    if (logger)
 	      logger->log ("rejecting return edge: return to wrong callsite");
-- 
2.32.0