Branch data Line data Source code
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 : 24608 : element_t (const supernode *caller, const supernode *callee)
58 : 19802 : : 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 : : std::unique_ptr<json::value> to_json () const;
76 : :
77 : 2504398 : 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 : 13766 : 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 : 5322467 : unsigned length () const { return m_elements.length (); }
98 : 1230725 : element_t operator[] (unsigned idx) const
99 : : {
100 : 1230725 : return m_elements[idx];
101 : : }
102 : 14153 : const element_t &get_top_of_stack () const
103 : : {
104 : 14153 : gcc_assert (m_elements.length () > 0);
105 : 14153 : 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 : 27048 : static inline hashval_t hash (const key_type &k)
120 : : {
121 : 27048 : inchash::hash hstate;
122 : 27048 : hstate.add_ptr (k.m_caller);
123 : 27048 : hstate.add_ptr (k.m_callee);
124 : 27048 : return hstate.end ();
125 : : }
126 : 18279 : static inline bool equal_keys (const key_type &k1, const key_type &k2)
127 : : {
128 : 18279 : return k1 == k2;
129 : : }
130 : 4806 : template <typename T> static inline void remove (T &entry)
131 : : {
132 : 4806 : entry.m_key = element_t (NULL, NULL);
133 : : }
134 : : static const bool empty_zero_p = true;
135 : 403850 : template <typename T> static inline bool is_empty (const T &entry)
136 : : {
137 : 399044 : return entry.m_key.m_caller == NULL;
138 : : }
139 : 29540 : template <typename T> static inline bool is_deleted (const T &entry)
140 : : {
141 : 29540 : return entry.m_key.m_caller == reinterpret_cast<const supernode *> (1);
142 : : }
143 : 0 : template <typename T> static inline void mark_empty (T &entry)
144 : : {
145 : 0 : entry.m_key = element_t (NULL, NULL);
146 : 0 : 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 */
|
