gcc/analyzer/call-string.cc

   1 /* Call stacks at program points.
   2    Copyright (C) 2019-2021 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 #include "system.h"
  23 #include "coretypes.h"
  24 #include "pretty-print.h"
  25 #include "tree.h"
  26 #include "options.h"
  27 #include "json.h"
  28 #include "analyzer/call-string.h"
  29 #include "ordered-hash-map.h"
  30 #include "options.h"
  31 #include "cgraph.h"
  32 #include "function.h"
  33 #include "cfg.h"
  34 #include "basic-block.h"
  35 #include "gimple.h"
  36 #include "gimple-iterator.h"
  37 #include "digraph.h"
  38 #include "analyzer/supergraph.h"
  39
  40 #if ENABLE_ANALYZER
  41
  42 #if __GNUC__ >= 10
  43 #pragma GCC diagnostic ignored "-Wformat-diag"
  44 #endif
  45
  46 /* class call_string.  */
  47
  48 /* struct call_string::element_t.  */
  49
  50 /* call_string::element_t's equality operator.  */
  51
  52 bool
  53 call_string::element_t::operator== (const call_string::element_t &other) const
  54 {
  55   return (m_caller == other.m_caller && m_callee == other.m_callee);
  56 }
  57
  58 /* call_string::element_t's inequality operator.  */
  59 bool
  60 call_string::element_t::operator!= (const call_string::element_t &other) const
  61 {
  62   return !(*this == other);
  63 }
  64
  65 function *
  66 call_string::element_t::get_caller_function () const
  67 {
  68   return m_caller->get_function ();
  69 }
  70
  71 function *
  72 call_string::element_t::get_callee_function () const
  73 {
  74   return m_callee->get_function ();
  75 }
  76
  77 /* call_string's copy ctor.  */
  78
  79 call_string::call_string (const call_string &other)
  80 : m_elements (other.m_elements.length ())
  81 {
  82   for (const call_string::element_t &e : other.m_elements)
  83     m_elements.quick_push (e);
  84 }
  85
  86 /* call_string's assignment operator.  */
  87
  88 call_string&
  89 call_string::operator= (const call_string &other)
  90 {
  91   // would be much simpler if we could rely on vec<> assignment op
  92   m_elements.truncate (0);
  93   m_elements.reserve (other.m_elements.length (), true);
  94   call_string::element_t *e;
  95   int i;
  96   FOR_EACH_VEC_ELT (other.m_elements, i, e)
  97     m_elements.quick_push (*e);
  98   return *this;
  99 }
 100
 101 /* call_string's equality operator.  */
 102
 103 bool
 104 call_string::operator== (const call_string &other) const
 105 {
 106   if (m_elements.length () != other.m_elements.length ())
 107     return false;
 108   call_string::element_t *e;
 109   int i;
 110   FOR_EACH_VEC_ELT (m_elements, i, e)
 111     if (*e != other.m_elements[i])
 112       return false;
 113   return true;
 114 }
 115
 116 /* Print this to PP.  */
 117
 118 void
 119 call_string::print (pretty_printer *pp) const
 120 {
 121   pp_string (pp, "[");
 122
 123   call_string::element_t *e;
 124   int i;
 125   FOR_EACH_VEC_ELT (m_elements, i, e)
 126     {
 127       if (i > 0)
 128         pp_string (pp, ", ");
 129       pp_printf (pp, "(SN: %i -> SN: %i in %s)",
 130                  e->m_callee->m_index, e->m_caller->m_index,
 131                  function_name (e->m_caller->m_fun));
 132     }
 133
 134   pp_string (pp, "]");
 135 }
 136
 137 /* Return a new json::array of the form
 138    [{"src_snode_idx" : int,
 139      "dst_snode_idx" : int,
 140      "funcname" : str},
 141      ...for each element in the callstring].  */
 142
 143 json::value *
 144 call_string::to_json () const
 145 {
 146   json::array *arr = new json::array ();
 147
 148   for (const call_string::element_t &e : m_elements)
 149     {
 150       json::object *e_obj = new json::object ();
 151       e_obj->set ("src_snode_idx",
 152                   new json::integer_number (e.m_callee->m_index));
 153       e_obj->set ("dst_snode_idx",
 154                   new json::integer_number (e.m_caller->m_index));
 155       e_obj->set ("funcname",
 156                   new json::string (function_name (e.m_caller->m_fun)));
 157       arr->append (e_obj);
 158     }
 159
 160   return arr;
 161 }
 162
 163 /* Generate a hash value for this call_string.  */
 164
 165 hashval_t
 166 call_string::hash () const
 167 {
 168   inchash::hash hstate;
 169   for (const call_string::element_t &e : m_elements)
 170     hstate.add_ptr (e.m_caller);
 171   return hstate.end ();
 172 }
 173
 174 /* Push the return superedge for CALL_SEDGE onto the end of this
 175    call_string.  */
 176
 177 void
 178 call_string::push_call (const supergraph &sg,
 179                         const call_superedge *call_sedge)
 180 {
 181   gcc_assert (call_sedge);
 182   const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
 183   gcc_assert (return_sedge);
 184   call_string::element_t e (return_sedge->m_dest, return_sedge->m_src);
 185   m_elements.safe_push (e);
 186 }
 187
 188 void
 189 call_string::push_call (const supernode *caller,
 190                         const supernode *callee)
 191 {
 192   call_string::element_t e (caller, callee);
 193   m_elements.safe_push (e);
 194 }
 195
 196 call_string::element_t
 197 call_string::pop ()
 198 {
 199   return m_elements.pop();
 200 }
 201
 202 /* Count the number of times the top-most call site appears in the
 203    stack.  */
 204 int
 205 call_string::calc_recursion_depth () const
 206 {
 207   if (m_elements.is_empty ())
 208     return 0;
 209   const call_string::element_t top_return_sedge
 210     = m_elements[m_elements.length () - 1];
 211
 212   int result = 0;
 213   for (const call_string::element_t &e : m_elements)
 214     if (e == top_return_sedge)
 215       ++result;
 216   return result;
 217 }
 218
 219 /* Comparator for call strings.
 220    This implements a version of lexicographical order.
 221    Return negative if A is before B.
 222    Return positive if B is after A.
 223    Return 0 if they are equal.  */
 224
 225 int
 226 call_string::cmp (const call_string &a,
 227                   const call_string &b)
 228 {
 229   unsigned len_a = a.length ();
 230   unsigned len_b = b.length ();
 231
 232   unsigned i = 0;
 233   while (1)
 234     {
 235       /* Consider index i; the strings have been equal up to it.  */
 236
 237       /* Have both strings run out?  */
 238       if (i >= len_a && i >= len_b)
 239         return 0;
 240
 241       /* Otherwise, has just one of the strings run out?  */
 242       if (i >= len_a)
 243         return 1;
 244       if (i >= len_b)
 245         return -1;
 246
 247       /* Otherwise, compare the node pairs.  */
 248       const call_string::element_t a_node_pair = a[i];
 249       const call_string::element_t b_node_pair = b[i];
 250       int src_cmp
 251         = a_node_pair.m_callee->m_index - b_node_pair.m_callee->m_index;
 252       if (src_cmp)
 253         return src_cmp;
 254       int dest_cmp
 255         = a_node_pair.m_caller->m_index - b_node_pair.m_caller->m_index;
 256       if (dest_cmp)
 257         return dest_cmp;
 258       i++;
 259       // TODO: test coverage for this
 260     }
 261 }
 262
 263 /* Return the pointer to callee of the topmost call in the stack,
 264    or NULL if stack is empty.  */
 265 const supernode *
 266 call_string::get_callee_node () const
 267 {
 268   if(m_elements.is_empty ())
 269     return NULL;
 270   return m_elements[m_elements.length () - 1].m_callee;
 271 }
 272
 273 /* Return the pointer to caller of the topmost call in the stack,
 274    or NULL if stack is empty.  */
 275 const supernode *
 276 call_string::get_caller_node () const
 277 {
 278   if(m_elements.is_empty ())
 279     return NULL;
 280   return m_elements[m_elements.length () - 1].m_caller;
 281 }
 282
 283 /* Assert that this object is sane.  */
 284
 285 void
 286 call_string::validate () const
 287 {
 288   /* Skip this in a release build.  */
 289 #if !CHECKING_P
 290   return;
 291 #endif
 292
 293   /* Each entry's "caller" should be the "callee" of the previous entry.  */
 294   call_string::element_t *e;
 295   int i;
 296   FOR_EACH_VEC_ELT (m_elements, i, e)
 297     if (i > 0)
 298     {
 299       gcc_assert (e->get_caller_function () ==
 300                   m_elements[i - 1].get_callee_function ());
 301     }
 302 }
 303
 304 #endif /* #if ENABLE_ANALYZER */