Branch data 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 : 12754 : element_t (const superedge *call_sedge,
54 : : const call_and_return_op *call_op,
55 : : function *called_fun)
56 : 7000 : : m_call_sedge (call_sedge), m_call_op (call_op),
57 : 7000 : 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 : 415222 : 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 : 1905805 : 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 : 7583 : 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 : 6138817 : unsigned length () const { return m_elements.length (); }
99 : 1762759 : element_t operator[] (unsigned idx) const
100 : : {
101 : 1762759 : return m_elements[idx];
102 : : }
103 : 7046 : const element_t &get_top_of_stack () const
104 : : {
105 : 7046 : gcc_assert (m_elements.length () > 0);
106 : 7046 : 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 : 30018 : static inline hashval_t hash (const key_type &k)
121 : : {
122 : 30018 : inchash::hash hstate;
123 : 30018 : hstate.add_ptr (k.m_call_sedge);
124 : 30018 : return hstate.end ();
125 : : }
126 : 19720 : static inline bool equal_keys (const key_type &k1, const key_type &k2)
127 : : {
128 : 19720 : return k1 == k2;
129 : : }
130 : 5754 : template <typename T> static inline void remove (T &entry)
131 : : {
132 : 5754 : entry.m_key = element_t (nullptr, nullptr, nullptr);
133 : : }
134 : : static const bool empty_zero_p = true;
135 : 460759 : template <typename T> static inline bool is_empty (const T &entry)
136 : : {
137 : 455005 : return entry.m_key.m_call_sedge == nullptr;
138 : : }
139 : 33052 : template <typename T> static inline bool is_deleted (const T &entry)
140 : : {
141 : 33052 : 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 */
|
