GCC Middle and Back End API Reference
call-string.h
Go to the documentation of this file.
1/* Call stacks at program points.
2 Copyright (C) 2019-2024 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
24namespace ana {
25
26class supergraph;
27class supernode;
28class call_superedge;
29class 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
48{
49public:
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 */
68
71 };
72
73 void print (pretty_printer *pp) const;
74
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
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 }
103 {
104 gcc_assert (m_elements.length () > 0);
105 return m_elements[m_elements.length () - 1];
106 }
107
109
110 void validate () const;
111
112private:
114 {
116 typedef const call_string *value_type;
117
118 static const bool maybe_mx = false;
119 static inline hashval_t hash (const key_type &k)
120 {
121 inchash::hash hstate;
122 hstate.add_ptr (k.m_caller);
123 hstate.add_ptr (k.m_callee);
124 return hstate.end ();
125 }
126 static inline bool equal_keys (const key_type &k1, const key_type &k2)
127 {
128 return k1 == k2;
129 }
130 template <typename T> static inline void remove (T &entry)
131 {
132 entry.m_key = element_t (NULL, NULL);
133 }
134 static const bool empty_zero_p = true;
135 template <typename T> static inline bool is_empty (const T &entry)
136 {
137 return entry.m_key.m_caller == NULL;
138 }
139 template <typename T> static inline bool is_deleted (const T &entry)
140 {
141 return entry.m_key.m_caller == reinterpret_cast<const supernode *> (1);
142 }
143 template <typename T> static inline void mark_empty (T &entry)
144 {
145 entry.m_key = element_t (NULL, NULL);
146 entry.m_value = NULL;
147 }
148 template <typename T> static inline void mark_deleted (T &entry)
149 {
150 entry.m_key.m_caller = reinterpret_cast<const supernode *> (1);
151 }
152 };
153
155
157
159 call_string (const call_string &parent, const element_t &to_push);
161
163
167};
168
169} // namespace ana
170
171#endif /* GCC_ANALYZER_CALL_STRING_H */
Definition call-string.h:48
const supernode * get_caller_node() const
const call_string * get_parent() const
Definition call-string.h:84
static int cmp(const call_string &a, const call_string &b)
void recursive_log(logger *logger) const
void print(pretty_printer *pp) const
DISABLE_COPY_AND_ASSIGN(call_string)
element_t operator[](unsigned idx) const
Definition call-string.h:98
int calc_recursion_depth() const
hash_map< element_t, const call_string *, hashmap_traits_t > m_children
Definition call-string.h:166
json::value * to_json() const
void validate() const
auto_vec< element_t > m_elements
Definition call-string.h:165
int count_occurrences_of_function(function *) const
const supernode * get_callee_node() const
const call_string * push_call(const supergraph &sg, const call_superedge *sedge) const
call_string(const call_string &parent, const element_t &to_push)
const call_string * push_call(const supernode *src, const supernode *dest) const
const call_string * m_parent
Definition call-string.h:164
const element_t & get_top_of_stack() const
Definition call-string.h:102
bool empty_p() const
Definition call-string.h:77
static int cmp_ptr_ptr(const void *, const void *)
unsigned length() const
Definition call-string.h:97
Definition supergraph.h:446
Definition analyzer-logging.h:34
Definition region-model-manager.h:32
Definition supergraph.h:109
Definition supergraph.h:235
Definition vec.h:1656
Definition hash-map.h:40
Definition inchash.h:38
hashval_t end()
Definition inchash.h:49
void add_ptr(const void *ptr)
Definition inchash.h:94
Definition json.h:79
Definition pretty-print.h:255
Definition access-diagram.h:30
Ca const poly_int< N, Cb > & b
Definition poly-int.h:767
Ca & a
Definition poly-int.h:766
Definition call-string.h:56
bool operator==(const element_t &other) const
const supernode * m_caller
Definition call-string.h:69
element_t(const supernode *caller, const supernode *callee)
Definition call-string.h:57
function * get_callee_function() const
bool operator!=(const element_t &other) const
function * get_caller_function() const
const supernode * m_callee
Definition call-string.h:70
Definition call-string.h:114
static void mark_deleted(T &entry)
Definition call-string.h:148
static void mark_empty(T &entry)
Definition call-string.h:143
static bool is_deleted(const T &entry)
Definition call-string.h:139
static hashval_t hash(const key_type &k)
Definition call-string.h:119
static const bool empty_zero_p
Definition call-string.h:134
static void remove(T &entry)
Definition call-string.h:130
static bool equal_keys(const key_type &k1, const key_type &k2)
Definition call-string.h:126
static bool is_empty(const T &entry)
Definition call-string.h:135
const call_string * value_type
Definition call-string.h:116
static const bool maybe_mx
Definition call-string.h:118
element_t key_type
Definition call-string.h:115
Definition function.h:249
#define NULL
Definition system.h:50
#define gcc_assert(EXPR)
Definition system.h:821