gcc/analyzer/call-string.cc

   1 /* Call stacks at program points.
   2    Copyright (C) 2019-2023 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 ("src_snode_idx",
 115                   new json::integer_number (e.m_callee->m_index));
 116       e_obj->set ("dst_snode_idx",
 117                   new json::integer_number (e.m_caller->m_index));
 118       e_obj->set ("funcname",
 119                   new json::string (function_name (e.m_caller->m_fun)));
 120       arr->append (e_obj);
 121     }
 122
 123   return arr;
 124 }
 125
 126 /* Get or create the call_string resulting from pushing the return
 127    superedge for CALL_SEDGE onto the end of this call_string.  */
 128
 129 const call_string *
 130 call_string::push_call (const supergraph &sg,
 131                         const call_superedge *call_sedge) const
 132 {
 133   gcc_assert (call_sedge);
 134   const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
 135   gcc_assert (return_sedge);
 136   return push_call (return_sedge->m_dest, return_sedge->m_src);
 137 }
 138
 139 /* Get or create the call_string resulting from pushing the call
 140    (caller, callee) onto the end of this call_string.  */
 141
 142 const call_string *
 143 call_string::push_call (const supernode *caller,
 144                         const supernode *callee) const
 145 {
 146   call_string::element_t e (caller, callee);
 147
 148   if (const call_string **slot = m_children.get (e))
 149     return *slot;
 150
 151   call_string *result = new call_string (*this, e);
 152   m_children.put (e, result);
 153   return result;
 154 }
 155
 156 /* Count the number of times the top-most call site appears in the
 157    stack.  */
 158 int
 159 call_string::calc_recursion_depth () const
 160 {
 161   if (m_elements.is_empty ())
 162     return 0;
 163   const call_string::element_t top_return_sedge
 164     = m_elements[m_elements.length () - 1];
 165
 166   int result = 0;
 167   for (const call_string::element_t &e : m_elements)
 168     if (e == top_return_sedge)
 169       ++result;
 170   return result;
 171 }
 172
 173 /* Count the number of times FUN appears in the string.  */
 174
 175 int
 176 call_string::count_occurrences_of_function (function *fun) const
 177 {
 178   int result = 0;
 179   for (const call_string::element_t &e : m_elements)
 180     {
 181       if (e.get_callee_function () == fun)
 182         result++;
 183       if (e.get_caller_function () == fun)
 184         result++;
 185     }
 186   return result;
 187 }
 188
 189 /* Comparator for call strings.
 190    This implements a version of lexicographical order.
 191    Return negative if A is before B.
 192    Return positive if B is after A.
 193    Return 0 if they are equal.  */
 194
 195 int
 196 call_string::cmp (const call_string &a,
 197                   const call_string &b)
 198 {
 199   unsigned len_a = a.length ();
 200   unsigned len_b = b.length ();
 201
 202   unsigned i = 0;
 203   while (1)
 204     {
 205       /* Consider index i; the strings have been equal up to it.  */
 206
 207       /* Have both strings run out?  */
 208       if (i >= len_a && i >= len_b)
 209         return 0;
 210
 211       /* Otherwise, has just one of the strings run out?  */
 212       if (i >= len_a)
 213         return 1;
 214       if (i >= len_b)
 215         return -1;
 216
 217       /* Otherwise, compare the node pairs.  */
 218       const call_string::element_t a_node_pair = a[i];
 219       const call_string::element_t b_node_pair = b[i];
 220       int src_cmp
 221         = a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
 222       if (src_cmp)
 223         return src_cmp;
 224       int dest_cmp
 225         = a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
 226       if (dest_cmp)
 227         return dest_cmp;
 228       i++;
 229       // TODO: test coverage for this
 230     }
 231 }
 232
 233 /* Comparator for use by vec<const call_string *>::qsort.  */
 234
 235 int
 236 call_string::cmp_ptr_ptr (const void *pa, const void *pb)
 237 {
 238   const call_string *cs_a = *static_cast <const call_string * const *> (pa);
 239   const call_string *cs_b = *static_cast <const call_string * const *> (pb);
 240   return cmp (*cs_a, *cs_b);
 241 }
 242
 243 /* Return the pointer to callee of the topmost call in the stack,
 244    or NULL if stack is empty.  */
 245 const supernode *
 246 call_string::get_callee_node () const
 247 {
 248   if(m_elements.is_empty ())
 249     return NULL;
 250   return m_elements[m_elements.length () - 1].m_callee;
 251 }
 252
 253 /* Return the pointer to caller of the topmost call in the stack,
 254    or NULL if stack is empty.  */
 255 const supernode *
 256 call_string::get_caller_node () const
 257 {
 258   if(m_elements.is_empty ())
 259     return NULL;
 260   return m_elements[m_elements.length () - 1].m_caller;
 261 }
 262
 263 /* Assert that this object is sane.  */
 264
 265 void
 266 call_string::validate () const
 267 {
 268   /* Skip this in a release build.  */
 269 #if !CHECKING_P
 270   return;
 271 #endif
 272
 273   gcc_assert (m_parent || m_elements.length () == 0);
 274
 275   /* Each entry's "caller" should be the "callee" of the previous entry.  */
 276   call_string::element_t *e;
 277   int i;
 278   FOR_EACH_VEC_ELT (m_elements, i, e)
 279     if (i > 0)
 280       gcc_assert (e->get_caller_function () ==
 281                   m_elements[i - 1].get_callee_function ());
 282 }
 283
 284 /* ctor for the root/empty call_string.  */
 285
 286 call_string::call_string ()
 287 : m_parent (NULL), m_elements ()
 288 {
 289 }
 290
 291 /* ctor for a child call_string.  */
 292
 293 call_string::call_string (const call_string &parent, const element_t &to_push)
 294 : m_parent (&parent),
 295   m_elements (parent.m_elements.length () + 1)
 296 {
 297   m_elements.splice (parent.m_elements);
 298   m_elements.quick_push (to_push);
 299 }
 300
 301 /* dtor for call_string: recursively delete children.  */
 302
 303 call_string::~call_string ()
 304 {
 305   for (auto child_iter : m_children)
 306     delete child_iter.second;
 307 }
 308
 309 /* Log this call_string and all its descendents recursively to LOGGER,
 310    using indentation and elision to highlight the hierarchy.  */
 311
 312 void
 313 call_string::recursive_log (logger *logger) const
 314 {
 315   logger->start_log_line ();
 316   pretty_printer *pp = logger->get_printer ();
 317   for (unsigned i = 0; i < length (); i++)
 318     pp_string (pp, "  ");
 319   if (length () > 0)
 320     {
 321       pp_string (pp, "[");
 322       /* Elide all but the final element, since they are shared with
 323          the parent call_string.  */
 324       for (unsigned i = 0; i < length (); i++)
 325         pp_string (pp, "..., ");
 326       /* Log the final element in detail.  */
 327       const element_t *e = &m_elements[m_elements.length () - 1];
 328       pp_printf (pp, "(SN: %i -> SN: %i in %s)]",
 329                  e->m_callee->m_index, e->m_caller->m_index,
 330                  function_name (e->m_caller->m_fun));
 331     }
 332   else
 333     pp_string (pp, "[]");
 334   logger->end_log_line ();
 335
 336   /* Recurse into children.  */
 337   {
 338     auto_vec<const call_string *> children (m_children.elements ());
 339     for (auto iter : m_children)
 340       children.safe_push (iter.second);
 341     children.qsort (call_string::cmp_ptr_ptr);
 342
 343     for (auto iter : children)
 344       iter->recursive_log (logger);
 345   }
 346 }
 347
 348 #endif /* #if ENABLE_ANALYZER */