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 | #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 | int count_occurrences_of_function (function *) const; |
109 | |
110 | void validate () const; |
111 | |
112 | private: |
113 | struct hashmap_traits_t |
114 | { |
115 | typedef element_t key_type; |
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 (ptr: k.m_caller); |
123 | hstate.add_ptr (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 | |
154 | friend class region_model_manager; |
155 | |
156 | DISABLE_COPY_AND_ASSIGN (call_string); |
157 | |
158 | call_string (); |
159 | call_string (const call_string &parent, const element_t &to_push); |
160 | ~call_string (); |
161 | |
162 | void recursive_log (logger *logger) const; |
163 | |
164 | const call_string *m_parent; |
165 | auto_vec<element_t> m_elements; |
166 | mutable hash_map<element_t, const call_string *, hashmap_traits_t> m_children; |
167 | }; |
168 | |
169 | } // namespace ana |
170 | |
171 | #endif /* GCC_ANALYZER_CALL_STRING_H */ |
172 | |