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 : #include "text-art/widget.h"
25 : #include "text-art/tree-widget.h"
26 :
27 : namespace ana {
28 :
29 : class supergraph;
30 : class supernode;
31 : class call_and_return_op;
32 :
33 : /* A string of "elements" representing a call stack 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 : Instances of call_string are consolidated by the region_model_manager,
39 : which effectively owns them: it owns the root/empty call_string, and each
40 : call_string instance tracks its children, lazily creating them on demand,
41 : so that the call_string instances form a tree-like hierarchy in memory. */
42 :
43 : class call_string
44 : {
45 : public:
46 : /* A struct representing an element in the call_string.
47 :
48 : Each element represents a "call superedge" within the caller for which
49 : the op was a call_and_return_op.
50 : Returning from the callee to the caller will involve creating a custom
51 : exploded edge from the exit supernode in the callee to the destination
52 : of the call superedge within the caller. */
53 :
54 : struct element_t
55 : {
56 18100 : element_t (const superedge *call_sedge,
57 : const call_and_return_op *call_op,
58 : function *called_fun)
59 9577 : : m_call_sedge (call_sedge), m_call_op (call_op),
60 9577 : m_called_fun (called_fun)
61 : {
62 : }
63 :
64 : bool operator== (const element_t &other) const;
65 : bool operator!= (const element_t &other) const;
66 :
67 : static int cmp (const element_t &a, const element_t &b);
68 :
69 : /* Accessors */
70 : function *get_caller_function () const;
71 470103 : function *get_callee_function () const { return m_called_fun; }
72 : const supernode *get_call_snode_in_caller () const;
73 : const supernode *get_return_snode_in_caller () const;
74 : const gcall &get_call_stmt () const;
75 :
76 : std::unique_ptr<text_art::tree_widget>
77 : make_dump_widget (symbolic::node_dump_state &nds) const;
78 :
79 : const superedge *m_call_sedge;
80 : const call_and_return_op *m_call_op;
81 : function *m_called_fun;
82 : };
83 :
84 : void print (pretty_printer *pp) const;
85 :
86 : std::unique_ptr<json::value> to_json () const;
87 :
88 1412516 : bool empty_p () const { return m_elements.is_empty (); }
89 :
90 : const call_string *push_call (const superedge &call_sedge,
91 : const call_and_return_op &call_op,
92 : function &called_fun) const;
93 9870 : const call_string *get_parent () const { return m_parent; }
94 :
95 : int calc_recursion_depth () const;
96 :
97 : static int cmp (const call_string &a,
98 : const call_string &b);
99 :
100 : static int cmp_ptr_ptr (const void *, const void *);
101 :
102 : /* Accessors */
103 : const supernode *get_return_node_in_caller () const;
104 5709218 : unsigned length () const { return m_elements.length (); }
105 1621077 : element_t operator[] (unsigned idx) const
106 : {
107 1621077 : return m_elements[idx];
108 : }
109 9492 : const element_t &get_top_of_stack () const
110 : {
111 9492 : gcc_assert (m_elements.length () > 0);
112 9492 : return m_elements[m_elements.length () - 1];
113 : }
114 :
115 : int count_occurrences_of_function (function *) const;
116 :
117 : void validate () const;
118 :
119 : std::unique_ptr<text_art::tree_widget>
120 : make_dump_widget (symbolic::node_dump_state &nds) const;
121 :
122 : private:
123 : struct hashmap_traits_t
124 : {
125 : typedef element_t key_type;
126 : typedef const call_string *value_type;
127 :
128 : static const bool maybe_mx = false;
129 46584 : static inline hashval_t hash (const key_type &k)
130 : {
131 46584 : inchash::hash hstate;
132 46584 : hstate.add_ptr (k.m_call_sedge);
133 46584 : return hstate.end ();
134 : }
135 32051 : static inline bool equal_keys (const key_type &k1, const key_type &k2)
136 : {
137 32051 : return k1 == k2;
138 : }
139 8523 : template <typename T> static inline void remove (T &entry)
140 : {
141 8523 : entry.m_key = element_t (nullptr, nullptr, nullptr);
142 : }
143 : static const bool empty_zero_p = true;
144 645896 : template <typename T> static inline bool is_empty (const T &entry)
145 : {
146 637373 : return entry.m_key.m_call_sedge == nullptr;
147 : }
148 51964 : template <typename T> static inline bool is_deleted (const T &entry)
149 : {
150 51964 : return entry.m_key.m_call_sedge == reinterpret_cast<const superedge *> (1);
151 : }
152 0 : template <typename T> static inline void mark_empty (T &entry)
153 : {
154 0 : entry.m_key = element_t (nullptr, nullptr, nullptr);
155 0 : entry.m_value = nullptr;
156 : }
157 : template <typename T> static inline void mark_deleted (T &entry)
158 : {
159 : entry.m_key.m_call_sedge = reinterpret_cast<const superedge *> (1);
160 : }
161 : };
162 :
163 : friend class region_model_manager;
164 :
165 : DISABLE_COPY_AND_ASSIGN (call_string);
166 :
167 : call_string ();
168 : call_string (const call_string &parent, const element_t &to_push);
169 : ~call_string ();
170 :
171 : void recursive_log (logger *logger) const;
172 :
173 : const call_string *m_parent;
174 : auto_vec<element_t> m_elements;
175 : mutable hash_map<element_t, const call_string *, hashmap_traits_t> m_children;
176 : };
177 :
178 : } // namespace ana
179 :
180 : #endif /* GCC_ANALYZER_CALL_STRING_H */
|