gcc/analyzer/call-string.h

   1 /* Call stacks at program points.
   2    Copyright (C) 2019-2022 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 #ifndef GCC_ANALYZER_CALL_STRING_H
  22 #define GCC_ANALYZER_CALL_STRING_H
  23
  24 namespace ana {
  25
  26 class supergraph;
  27 class supernode;
  28 class call_superedge;
  29 class return_superedge;
  30
  31
  32 /* A string of return_superedge pointers, representing a call stack
  33    at a program point.
  34
  35    This is used to ensure that we generate interprocedurally valid paths
  36    i.e. that we return to the same callsite that called us.
  37
  38    The class stores returning calls ( which may be represented by a
  39    returning superedge ). We do so because this is what we need to compare
  40    against.
  41
  42    Instances of call_string are consolidated by the region_model_manager,
  43    which effectively owns them: it owns the root/empty call_string, and each
  44    call_string instance tracks its children, lazily creating them on demand,
  45    so that the call_string instances form a tree-like hierarchy in memory.  */
  46
  47 class call_string
  48 {
  49 public:
  50   /* A struct representing an element in the call_string.
  51
  52    Each element represents a path from m_callee to m_caller which represents
  53    returning from function.  */
  54
  55   struct element_t
  56   {
  57     element_t (const supernode *caller, const supernode *callee)
  58     :  m_caller (caller), m_callee (callee)
  59     {
  60     }
  61
  62     bool operator== (const element_t &other) const;
  63     bool operator!= (const element_t &other) const;
  64
  65     /* Accessors */
  66     function *get_caller_function () const;
  67     function *get_callee_function () const;
  68
  69     const supernode *m_caller;
  70     const supernode *m_callee;
  71   };
  72
  73   void print (pretty_printer *pp) const;
  74
  75   json::value *to_json () const;
  76
  77   bool empty_p () const { return m_elements.is_empty (); }
  78
  79   const call_string *push_call (const supergraph &sg,
  80                                 const call_superedge *sedge) const;
  81
  82   const call_string *push_call (const supernode *src,
  83                                 const supernode *dest) const;
  84   const call_string *get_parent () const { return m_parent; }
  85
  86   int calc_recursion_depth () const;
  87
  88   static int cmp (const call_string &a,
  89                   const call_string &b);
  90
  91   static int cmp_ptr_ptr (const void *, const void *);
  92
  93   /* Accessors */
  94
  95   const supernode *get_callee_node () const;
  96   const supernode *get_caller_node () const;
  97   unsigned length () const { return m_elements.length (); }
  98   element_t operator[] (unsigned idx) const
  99   {
 100     return m_elements[idx];
 101   }
 102   const element_t &get_top_of_stack () const
 103   {
 104     gcc_assert (m_elements.length () > 0);
 105     return m_elements[m_elements.length () - 1];
 106   }
 107
 108   void validate () const;
 109
 110 private:
 111   struct hashmap_traits_t
 112   {
 113     typedef element_t key_type;
 114     typedef const call_string *value_type;
 115
 116     static const bool maybe_mx = false;
 117     static inline hashval_t hash (const key_type &k)
 118     {
 119       inchash::hash hstate;
 120       hstate.add_ptr (k.m_caller);
 121       hstate.add_ptr (k.m_callee);
 122       return hstate.end ();
 123     }
 124     static inline bool equal_keys (const key_type &k1, const key_type &k2)
 125     {
 126       return k1 == k2;
 127     }
 128     template <typename T> static inline void remove (T &entry)
 129     {
 130       entry.m_key = element_t (NULL, NULL);
 131     }
 132     static const bool empty_zero_p = true;
 133     template <typename T> static inline bool is_empty (const T &entry)
 134     {
 135       return entry.m_key.m_caller == NULL;
 136     }
 137     template <typename T> static inline bool is_deleted (const T &entry)
 138     {
 139       return entry.m_key.m_caller == reinterpret_cast<const supernode *> (1);
 140     }
 141     template <typename T> static inline void mark_empty (T &entry)
 142     {
 143       entry.m_key = element_t (NULL, NULL);
 144       entry.m_value = NULL;
 145     }
 146     template <typename T> static inline void mark_deleted (T &entry)
 147     {
 148       entry.m_key.m_caller = reinterpret_cast<const supernode *> (1);
 149     }
 150   };
 151
 152   friend class region_model_manager;
 153
 154   DISABLE_COPY_AND_ASSIGN (call_string);
 155
 156   call_string ();
 157   call_string (const call_string &parent, const element_t &to_push);
 158   ~call_string ();
 159
 160   void recursive_log (logger *logger) const;
 161
 162   const call_string *m_parent;
 163   auto_vec<element_t> m_elements;
 164   mutable hash_map<element_t, const call_string *, hashmap_traits_t> m_children;
 165 };
 166
 167 } // namespace ana
 168
 169 #endif /* GCC_ANALYZER_CALL_STRING_H */