2021-07-12 Ankur Saini <arse...@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