Line data Source code
1 : /* Call stacks at program points.
2 : Copyright (C) 2019-2026 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_and_return_op;
29 :
30 : /* A string of "elements" representing a call stack at a program point.
31 :
32 : This is used to ensure that we generate interprocedurally valid paths
33 : i.e. that we return to the same callsite that called us.
34 :
35 : Instances of call_string are consolidated by the region_model_manager,
36 : which effectively owns them: it owns the root/empty call_string, and each
37 : call_string instance tracks its children, lazily creating them on demand,
38 : so that the call_string instances form a tree-like hierarchy in memory. */
39 :
40 : class call_string
41 : {
42 : public:
43 : /* A struct representing an element in the call_string.
44 :
45 : Each element represents a "call superedge" within the caller for which
46 : the op was a call_and_return_op.
47 : Returning from the callee to the caller will involve creating a custom
48 : exploded edge from the exit supernode in the callee to the destination
49 : of the call superedge within the caller. */
50 :
51 : struct element_t
52 : {
53 12451 : element_t (const superedge *call_sedge,
54 : const call_and_return_op *call_op,
55 : function *called_fun)
56 6796 : : m_call_sedge (call_sedge), m_call_op (call_op),
57 6796 : m_called_fun (called_fun)
58 : {
59 : }
60 :
61 : bool operator== (const element_t &other) const;
62 : bool operator!= (const element_t &other) const;
63 :
64 : static int cmp (const element_t &a, const element_t &b);
65 :
66 : /* Accessors */
67 : function *get_caller_function () const;
68 383552 : function *get_callee_function () const { return m_called_fun; }
69 : const supernode *get_call_snode_in_caller () const;
70 : const supernode *get_return_snode_in_caller () const;
71 : const gcall &get_call_stmt () const;
72 :
73 : const superedge *m_call_sedge;
74 : const call_and_return_op *m_call_op;
75 : function *m_called_fun;
76 : };
77 :
78 : void print (pretty_printer *pp) const;
79 :
80 : std::unique_ptr<json::value> to_json () const;
81 :
82 2113747 : bool empty_p () const { return m_elements.is_empty (); }
83 :
84 : const call_string *push_call (const superedge &call_sedge,
85 : const call_and_return_op &call_op,
86 : function &called_fun) const;
87 7389 : const call_string *get_parent () const { return m_parent; }
88 :
89 : int calc_recursion_depth () const;
90 :
91 : static int cmp (const call_string &a,
92 : const call_string &b);
93 :
94 : static int cmp_ptr_ptr (const void *, const void *);
95 :
96 : /* Accessors */
97 : const supernode *get_return_node_in_caller () const;
98 6241017 : unsigned length () const { return m_elements.length (); }
99 1614071 : element_t operator[] (unsigned idx) const
100 : {
101 1614071 : return m_elements[idx];
102 : }
103 6873 : const element_t &get_top_of_stack () const
104 : {
105 6873 : gcc_assert (m_elements.length () > 0);
106 6873 : return m_elements[m_elements.length () - 1];
107 : }
108 :
109 : int count_occurrences_of_function (function *) const;
110 :
111 : void validate () const;
112 :
113 : private:
114 : struct hashmap_traits_t
115 : {
116 : typedef element_t key_type;
117 : typedef const call_string *value_type;
118 :
119 : static const bool maybe_mx = false;
120 28807 : static inline hashval_t hash (const key_type &k)
121 : {
122 28807 : inchash::hash hstate;
123 28807 : hstate.add_ptr (k.m_call_sedge);
124 28807 : return hstate.end ();
125 : }
126 18391 : static inline bool equal_keys (const key_type &k1, const key_type &k2)
127 : {
128 18391 : return k1 == k2;
129 : }
130 5655 : template <typename T> static inline void remove (T &entry)
131 : {
132 5655 : entry.m_key = element_t (nullptr, nullptr, nullptr);
133 : }
134 : static const bool empty_zero_p = true;
135 454128 : template <typename T> static inline bool is_empty (const T &entry)
136 : {
137 448473 : return entry.m_key.m_call_sedge == nullptr;
138 : }
139 31412 : template <typename T> static inline bool is_deleted (const T &entry)
140 : {
141 31412 : return entry.m_key.m_call_sedge == reinterpret_cast<const superedge *> (1);
142 : }
143 0 : template <typename T> static inline void mark_empty (T &entry)
144 : {
145 0 : entry.m_key = element_t (nullptr, nullptr, nullptr);
146 0 : entry.m_value = nullptr;
147 : }
148 : template <typename T> static inline void mark_deleted (T &entry)
149 : {
150 : entry.m_key.m_call_sedge = reinterpret_cast<const superedge *> (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 */
|
