gcc/analyzer/call-string.cc

   1 /* Call stacks at program points.
   2    Copyright (C) 2019-2024 Free Software Foundation, Inc.
   3    Contributed by David Malcolm <dmalcolm@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #define INCLUDE_MEMORY
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "pretty-print.h"
  26 #include "tree.h"
  27 #include "options.h"
  28 #include "ordered-hash-map.h"
  29 #include "options.h"
  30 #include "cgraph.h"
  31 #include "function.h"
  32 #include "cfg.h"
  33 #include "basic-block.h"
  34 #include "gimple.h"
  35 #include "gimple-iterator.h"
  36 #include "digraph.h"
  37 #include "analyzer/analyzer.h"
  38 #include "analyzer/analyzer-logging.h"
  39 #include "analyzer/call-string.h"
  40 #include "analyzer/supergraph.h"
  41
  42 #if ENABLE_ANALYZER
  43
  44 #if __GNUC__ >= 10
  45 #pragma GCC diagnostic ignored "-Wformat-diag"
  46 #endif
  47
  48 /* class call_string.  */
  49
  50 /* struct call_string::element_t.  */
  51
  52 /* call_string::element_t's equality operator.  */
  53
  54 bool
  55 call_string::element_t::operator== (const call_string::element_t &other) const
  56 {
  57   return (m_caller == other.m_caller && m_callee == other.m_callee);
  58 }
  59
  60 /* call_string::element_t's inequality operator.  */
  61 bool
  62 call_string::element_t::operator!= (const call_string::element_t &other) const
  63 {
  64   return !(*this == other);
  65 }
  66
  67 function *
  68 call_string::element_t::get_caller_function () const
  69 {
  70   return m_caller->get_function ();
  71 }
  72
  73 function *
  74 call_string::element_t::get_callee_function () const
  75 {
  76   return m_callee->get_function ();
  77 }
  78
  79 /* Print this to PP.  */
  80
  81 void
  82 call_string::print (pretty_printer *pp) const
  83 {
  84   pp_string (pp, "[");
  85
  86   call_string::element_t *e;
  87   int i;
  88   FOR_EACH_VEC_ELT (m_elements, i, e)
  89     {
  90       if (i > 0)
  91         pp_string (pp, ", ");
  92       pp_printf (pp, "(SN: %i -> SN: %i in %s)",
  93                  e->m_callee->m_index, e->m_caller->m_index,
  94                  function_name (e->m_caller->m_fun));
  95     }
  96
  97   pp_string (pp, "]");
  98 }
  99
 100 /* Return a new json::array of the form
 101    [{"src_snode_idx" : int,
 102      "dst_snode_idx" : int,
 103      "funcname" : str},
 104      ...for each element in the callstring].  */
 105
 106 json::value *
 107 call_string::to_json () const
 108 {
 109   json::array *arr = new json::array ();
 110
 111   for (const call_string::element_t &e : m_elements)
 112     {
 113       json::object *e_obj = new json::object ();
 114       e_obj->set_integer ("src_snode_idx", e.m_callee->m_index);
 115       e_obj->set_integer ("dst_snode_idx", e.m_caller->m_index);
 116       e_obj->set_string ("funcname", function_name (e.m_caller->m_fun));
 117       arr->append (e_obj);
 118     }
 119
 120   return arr;
 121 }
 122
 123 /* Get or create the call_string resulting from pushing the return
 124    superedge for CALL_SEDGE onto the end of this call_string.  */
 125
 126 const call_string *
 127 call_string::push_call (const supergraph &sg,
 128                         const call_superedge *call_sedge) const
 129 {
 130   gcc_assert (call_sedge);
 131   const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
 132   gcc_assert (return_sedge);
 133   return push_call (return_sedge->m_dest, return_sedge->m_src);
 134 }
 135
 136 /* Get or create the call_string resulting from pushing the call
 137    (caller, callee) onto the end of this call_string.  */
 138
 139 const call_string *
 140 call_string::push_call (const supernode *caller,
 141                         const supernode *callee) const
 142 {
 143   call_string::element_t e (caller, callee);
 144
 145   if (const call_string **slot = m_children.get (e))
 146     return *slot;
 147
 148   call_string *result = new call_string (*this, e);
 149   m_children.put (e, result);
 150   return result;
 151 }
 152
 153 /* Count the number of times the top-most call site appears in the
 154    stack.  */
 155 int
 156 call_string::calc_recursion_depth () const
 157 {
 158   if (m_elements.is_empty ())
 159     return 0;
 160   const call_string::element_t top_return_sedge
 161     = m_elements[m_elements.length () - 1];
 162
 163   int result = 0;
 164   for (const call_string::element_t &e : m_elements)
 165     if (e == top_return_sedge)
 166       ++result;
 167   return result;
 168 }
 169
 170 /* Count the number of times FUN appears in the string.  */
 171
 172 int
 173 call_string::count_occurrences_of_function (function *fun) const
 174 {
 175   int result = 0;
 176   for (const call_string::element_t &e : m_elements)
 177     {
 178       if (e.get_callee_function () == fun)
 179         result++;
 180       if (e.get_caller_function () == fun)
 181         result++;
 182     }
 183   return result;
 184 }
 185
 186 /* Comparator for call strings.
 187    This implements a version of lexicographical order.
 188    Return negative if A is before B.
 189    Return positive if B is after A.
 190    Return 0 if they are equal.  */
 191
 192 int
 193 call_string::cmp (const call_string &a,
 194                   const call_string &b)
 195 {
 196   unsigned len_a = a.length ();
 197   unsigned len_b = b.length ();
 198
 199   unsigned i = 0;
 200   while (1)
 201     {
 202       /* Consider index i; the strings have been equal up to it.  */
 203
 204       /* Have both strings run out?  */
 205       if (i >= len_a && i >= len_b)
 206         return 0;
 207
 208       /* Otherwise, has just one of the strings run out?  */
 209       if (i >= len_a)
 210         return 1;
 211       if (i >= len_b)
 212         return -1;
 213
 214       /* Otherwise, compare the node pairs.  */
 215       const call_string::element_t a_node_pair = a[i];
 216       const call_string::element_t b_node_pair = b[i];
 217       int src_cmp
 218         = a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
 219       if (src_cmp)
 220         return src_cmp;
 221       int dest_cmp
 222         = a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
 223       if (dest_cmp)
 224         return dest_cmp;
 225       i++;
 226       // TODO: test coverage for this
 227     }
 228 }
 229
 230 /* Comparator for use by vec<const call_string *>::qsort.  */
 231
 232 int
 233 call_string::cmp_ptr_ptr (const void *pa, const void *pb)
 234 {
 235   const call_string *cs_a = *static_cast <const call_string * const *> (pa);
 236   const call_string *cs_b = *static_cast <const call_string * const *> (pb);
 237   return cmp (*cs_a, *cs_b);
 238 }
 239
 240 /* Return the pointer to callee of the topmost call in the stack,
 241    or NULL if stack is empty.  */
 242 const supernode *
 243 call_string::get_callee_node () const
 244 {
 245   if(m_elements.is_empty ())
 246     return NULL;
 247   return m_elements[m_elements.length () - 1].m_callee;
 248 }
 249
 250 /* Return the pointer to caller of the topmost call in the stack,
 251    or NULL if stack is empty.  */
 252 const supernode *
 253 call_string::get_caller_node () const
 254 {
 255   if(m_elements.is_empty ())
 256     return NULL;
 257   return m_elements[m_elements.length () - 1].m_caller;
 258 }
 259
 260 /* Assert that this object is sane.  */
 261
 262 void
 263 call_string::validate () const
 264 {
 265   /* Skip this in a release build.  */
 266 #if !CHECKING_P
 267   return;
 268 #endif
 269
 270   gcc_assert (m_parent || m_elements.length () == 0);
 271
 272   /* Each entry's "caller" should be the "callee" of the previous entry.  */
 273   call_string::element_t *e;
 274   int i;
 275   FOR_EACH_VEC_ELT (m_elements, i, e)
 276     if (i > 0)
 277       gcc_assert (e->get_caller_function () ==
 278                   m_elements[i - 1].get_callee_function ());
 279 }
 280
 281 /* ctor for the root/empty call_string.  */
 282
 283 call_string::call_string ()
 284 : m_parent (NULL), m_elements ()
 285 {
 286 }
 287
 288 /* ctor for a child call_string.  */
 289
 290 call_string::call_string (const call_string &parent, const element_t &to_push)
 291 : m_parent (&parent),
 292   m_elements (parent.m_elements.length () + 1)
 293 {
 294   m_elements.splice (parent.m_elements);
 295   m_elements.quick_push (to_push);
 296 }
 297
 298 /* dtor for call_string: recursively delete children.  */
 299
 300 call_string::~call_string ()
 301 {
 302   for (auto child_iter : m_children)
 303     delete child_iter.second;
 304 }
 305
 306 /* Log this call_string and all its descendents recursively to LOGGER,
 307    using indentation and elision to highlight the hierarchy.  */
 308
 309 void
 310 call_string::recursive_log (logger *logger) const
 311 {
 312   logger->start_log_line ();
 313   pretty_printer *pp = logger->get_printer ();
 314   for (unsigned i = 0; i < length (); i++)
 315     pp_string (pp, "  ");
 316   if (length () > 0)
 317     {
 318       pp_string (pp, "[");
 319       /* Elide all but the final element, since they are shared with
 320          the parent call_string.  */
 321       for (unsigned i = 0; i < length (); i++)
 322         pp_string (pp, "..., ");
 323       /* Log the final element in detail.  */
 324       const element_t *e = &m_elements[m_elements.length () - 1];
 325       pp_printf (pp, "(SN: %i -> SN: %i in %s)]",
 326                  e->m_callee->m_index, e->m_caller->m_index,
 327                  function_name (e->m_caller->m_fun));
 328     }
 329   else
 330     pp_string (pp, "[]");
 331   logger->end_log_line ();
 332
 333   /* Recurse into children.  */
 334   {
 335     auto_vec<const call_string *> children (m_children.elements ());
 336     for (auto iter : m_children)
 337       children.safe_push (iter.second);
 338     children.qsort (call_string::cmp_ptr_ptr);
 339
 340     for (auto iter : children)
 341       iter->recursive_log (logger);
 342   }
 343 }
 344
 345 #endif /* #if ENABLE_ANALYZER */