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
47class call_string
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 */
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
112private:
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

source code of gcc/analyzer/call-string.h