Branch data Line data Source code
1 : : /* Finding reachable regions and values.
2 : : Copyright (C) 2020-2025 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 : : #include "analyzer/common.h"
22 : :
23 : : #include "ordered-hash-map.h"
24 : : #include "diagnostic.h"
25 : : #include "tree-diagnostic.h"
26 : :
27 : : #include "analyzer/analyzer-logging.h"
28 : : #include "analyzer/call-string.h"
29 : : #include "analyzer/program-point.h"
30 : : #include "analyzer/store.h"
31 : : #include "analyzer/region-model.h"
32 : : #include "analyzer/region-model-reachability.h"
33 : :
34 : : #if ENABLE_ANALYZER
35 : :
36 : : namespace ana {
37 : :
38 : 1207609 : reachable_regions::reachable_regions (region_model *model)
39 : 1207609 : : m_model (model), m_store (model->get_store ()),
40 : 1207609 : m_reachable_base_regs (), m_mutable_base_regs ()
41 : : {
42 : 1207609 : }
43 : :
44 : : /* Callback called for each cluster when initializing this object. */
45 : :
46 : : void
47 : 7735653 : reachable_regions::init_cluster_cb (const region *base_reg,
48 : : reachable_regions *this_ptr)
49 : : {
50 : 7735653 : this_ptr->init_cluster (base_reg);
51 : 7735653 : }
52 : :
53 : : /* Called for each cluster when initializing this object. */
54 : : void
55 : 7735653 : reachable_regions::init_cluster (const region *base_reg)
56 : : {
57 : : /* Mark any globals as mutable (and traverse what they point to). */
58 : 7735653 : const region *parent = base_reg->get_parent_region ();
59 : 7735653 : gcc_assert (parent);
60 : 7735653 : if (parent->get_kind () == RK_GLOBALS)
61 : 1074020 : add (base_reg, true);
62 : :
63 : : /* Mark any clusters that already escaped in previous unknown calls
64 : : as mutable (and traverse what they currently point to). */
65 : 7735653 : if (m_store->escaped_p (base_reg))
66 : 1955195 : add (base_reg, true);
67 : :
68 : 7735653 : if (const symbolic_region *sym_reg = base_reg->dyn_cast_symbolic_region ())
69 : : {
70 : 1512901 : const svalue *ptr = sym_reg->get_pointer ();
71 : 1512901 : if (ptr->implicitly_live_p (NULL, m_model))
72 : 1174537 : add (base_reg, true);
73 : 1512901 : switch (ptr->get_kind ())
74 : : {
75 : : default:
76 : : break;
77 : 1347956 : case SK_INITIAL:
78 : 1347956 : {
79 : : /* If BASE_REG is *INIT_VAL(REG) for some other REG, see if REG is
80 : : unbound and untouched. If so, then add BASE_REG as a root. */
81 : 1347956 : const initial_svalue *init_sval
82 : 1347956 : = as_a <const initial_svalue *> (ptr);
83 : 1347956 : const region *init_sval_reg = init_sval->get_region ();
84 : 1347956 : const region *other_base_reg = init_sval_reg->get_base_region ();
85 : 1347956 : const binding_cluster *other_cluster
86 : 1347956 : = m_store->get_cluster (other_base_reg);
87 : 1347956 : if (other_cluster == NULL
88 : 1347956 : || !other_cluster->touched_p ())
89 : 1294308 : add (base_reg, true);
90 : : }
91 : : break;
92 : :
93 : 51339 : case SK_UNKNOWN:
94 : 51339 : case SK_CONJURED:
95 : 51339 : {
96 : : /* If this cluster is due to dereferencing an unknown/conjured
97 : : pointer, any values written through the pointer could still
98 : : be live. */
99 : 51339 : add (base_reg, true);
100 : : }
101 : 51339 : break;
102 : : }
103 : : }
104 : 7735653 : }
105 : :
106 : : /* Lazily mark the cluster containing REG as being reachable, recursively
107 : : adding clusters reachable from REG's cluster. */
108 : : void
109 : 10939417 : reachable_regions::add (const region *reg, bool is_mutable)
110 : : {
111 : 10939417 : gcc_assert (reg);
112 : :
113 : 10939417 : const region *base_reg = const_cast <region *> (reg->get_base_region ());
114 : 10939417 : gcc_assert (base_reg);
115 : :
116 : : /* Bail out if this cluster is already in the sets at the IS_MUTABLE
117 : : level of mutability. */
118 : 10939417 : if (!is_mutable && m_reachable_base_regs.contains (base_reg))
119 : 3217525 : return;
120 : 10788658 : m_reachable_base_regs.add (base_reg);
121 : :
122 : 10788658 : if (is_mutable)
123 : : {
124 : 6617247 : if (m_mutable_base_regs.contains (base_reg))
125 : : return;
126 : : else
127 : 3550481 : m_mutable_base_regs.add (base_reg);
128 : : }
129 : :
130 : : /* Add values within the cluster. If any are pointers, add the pointee. */
131 : 7721892 : if (binding_cluster *bind_cluster = m_store->get_cluster (base_reg))
132 : 7498574 : bind_cluster->for_each_value (handle_sval_cb, this);
133 : : else
134 : 223318 : handle_sval (m_model->get_store_value (reg, NULL));
135 : : }
136 : :
137 : : void
138 : 8037037 : reachable_regions::handle_sval_cb (const svalue *sval,
139 : : reachable_regions *this_ptr)
140 : : {
141 : 8037037 : this_ptr->handle_sval (sval);
142 : 8037037 : }
143 : :
144 : : /* Add SVAL. If it is a pointer, add the pointed-to region. */
145 : :
146 : : void
147 : 8700268 : reachable_regions::handle_sval (const svalue *sval)
148 : : {
149 : 8700268 : m_reachable_svals.add (sval);
150 : 8700268 : m_mutable_svals.add (sval);
151 : 8700268 : if (const region_svalue *ptr = sval->dyn_cast_region_svalue ())
152 : : {
153 : 1072331 : const region *pointee = ptr->get_pointee ();
154 : : /* Use const-ness of pointer type to affect mutability. */
155 : 1072331 : bool ptr_is_mutable = true;
156 : 1072331 : if (ptr->get_type ()
157 : 1029685 : && TREE_CODE (ptr->get_type ()) == POINTER_TYPE
158 : 2100004 : && TYPE_READONLY (TREE_TYPE (ptr->get_type ())))
159 : : {
160 : : ptr_is_mutable = false;
161 : : }
162 : : else
163 : : {
164 : 1060309 : m_mutable_svals.add (sval);
165 : : }
166 : 1072331 : add (pointee, ptr_is_mutable);
167 : : }
168 : : /* Treat all svalues within a compound_svalue as reachable. */
169 : 17400536 : if (const compound_svalue *compound_sval
170 : 8700268 : = sval->dyn_cast_compound_svalue ())
171 : : {
172 : 18329 : for (compound_svalue::iterator_t iter = compound_sval->begin ();
173 : 36658 : iter != compound_sval->end (); ++iter)
174 : : {
175 : 13832 : const svalue *iter_sval = (*iter).second;
176 : 13832 : handle_sval (iter_sval);
177 : : }
178 : : }
179 : 8700268 : if (const svalue *cast = sval->maybe_undo_cast ())
180 : 103087 : handle_sval (cast);
181 : :
182 : : /* If SVAL is the result of a reversible operation, then the operands
183 : : are reachable. */
184 : 8700268 : switch (sval->get_kind ())
185 : : {
186 : : default:
187 : : break;
188 : 115525 : case SK_UNARYOP:
189 : 115525 : {
190 : 115525 : const unaryop_svalue *unaryop_sval = (const unaryop_svalue *)sval;
191 : 115525 : switch (unaryop_sval->get_op ())
192 : : {
193 : : default:
194 : : break;
195 : 10292 : case NEGATE_EXPR:
196 : 10292 : handle_sval (unaryop_sval->get_arg ());
197 : 10292 : break;
198 : : }
199 : : }
200 : : break;
201 : 715255 : case SK_BINOP:
202 : 715255 : {
203 : 715255 : const binop_svalue *binop_sval = (const binop_svalue *)sval;
204 : 715255 : switch (binop_sval->get_op ())
205 : : {
206 : : default:
207 : : break;
208 : 108984 : case POINTER_PLUS_EXPR:
209 : 108984 : handle_sval (binop_sval->get_arg0 ());
210 : 108984 : handle_sval (binop_sval->get_arg1 ());
211 : 108984 : break;
212 : : }
213 : : }
214 : : }
215 : 8700268 : }
216 : :
217 : : /* Add SVAL. If it is a pointer, add the pointed-to region.
218 : : Use PARAM_TYPE for determining mutability. */
219 : :
220 : : void
221 : 22010 : reachable_regions::handle_parm (const svalue *sval, tree param_type)
222 : : {
223 : 22010 : bool is_mutable = true;
224 : 22010 : if (param_type
225 : 20326 : && TREE_CODE (param_type) == POINTER_TYPE
226 : 36268 : && TYPE_READONLY (TREE_TYPE (param_type)))
227 : 3579 : is_mutable = false;
228 : 22010 : if (is_mutable)
229 : 18431 : m_mutable_svals.add (sval);
230 : : else
231 : 3579 : m_reachable_svals.add (sval);
232 : 22010 : if (const region *base_reg = sval->maybe_get_deref_base_region ())
233 : 9542 : add (base_reg, is_mutable);
234 : : /* Treat all svalues within a compound_svalue as reachable. */
235 : 44020 : if (const compound_svalue *compound_sval
236 : 22010 : = sval->dyn_cast_compound_svalue ())
237 : : {
238 : 341 : for (compound_svalue::iterator_t iter = compound_sval->begin ();
239 : 682 : iter != compound_sval->end (); ++iter)
240 : : {
241 : 278 : const svalue *iter_sval = (*iter).second;
242 : 278 : handle_sval (iter_sval);
243 : : }
244 : : }
245 : 22010 : if (const svalue *cast = sval->maybe_undo_cast ())
246 : 455 : handle_sval (cast);
247 : 22010 : }
248 : :
249 : : /* Update the store to mark the clusters that were found to be mutable
250 : : as having escaped.
251 : : Notify CTXT about escaping function_decls. */
252 : :
253 : : void
254 : 18836 : reachable_regions::mark_escaped_clusters (region_model_context *ctxt)
255 : : {
256 : 18836 : auto_vec<const function_region *> escaped_fn_regs
257 : 18836 : (m_mutable_base_regs.elements ());
258 : 51892 : for (hash_set<const region *>::iterator iter = m_mutable_base_regs.begin ();
259 : 84948 : iter != m_mutable_base_regs.end (); ++iter)
260 : : {
261 : 33056 : const region *base_reg = *iter;
262 : 33056 : m_store->mark_as_escaped (base_reg);
263 : :
264 : : /* If we have a function that's escaped, potentially add
265 : : it to the worklist. */
266 : 33056 : if (const function_region *fn_reg = base_reg->dyn_cast_function_region ())
267 : 217 : escaped_fn_regs.quick_push (fn_reg);
268 : : }
269 : 18836 : if (ctxt)
270 : : {
271 : : /* Sort to ensure deterministic results. */
272 : 12854 : escaped_fn_regs.qsort (region::cmp_ptr_ptr);
273 : : unsigned i;
274 : : const function_region *fn_reg;
275 : 29793 : FOR_EACH_VEC_ELT (escaped_fn_regs, i, fn_reg)
276 : 178 : ctxt->on_escaped_function (fn_reg->get_fndecl ());
277 : : }
278 : 18836 : }
279 : :
280 : : /* Dump SET to PP, sorting it to avoid churn when comparing dumps. */
281 : :
282 : : template <typename T>
283 : : static void
284 : 0 : dump_set (const hash_set<const T *> &set, pretty_printer *pp)
285 : : {
286 : 0 : auto_vec<const T *> elements (set.elements ());
287 : 0 : for (typename hash_set<const T *>::iterator iter = set.begin ();
288 : 0 : iter != set.end (); ++iter)
289 : 0 : elements.quick_push (*iter);
290 : :
291 : 0 : elements.qsort (T::cmp_ptr_ptr);
292 : :
293 : : unsigned i;
294 : : const T *element;
295 : 0 : FOR_EACH_VEC_ELT (elements, i, element)
296 : : {
297 : 0 : pp_string (pp, " ");
298 : 0 : element->dump_to_pp (pp, true);
299 : 0 : pp_newline (pp);
300 : : }
301 : 0 : }
302 : :
303 : : /* Dump a multiline representation of this object to PP. */
304 : :
305 : : void
306 : 0 : reachable_regions::dump_to_pp (pretty_printer *pp) const
307 : : {
308 : 0 : pp_string (pp, "reachable clusters: ");
309 : 0 : pp_newline (pp);
310 : 0 : dump_set (m_reachable_base_regs, pp);
311 : :
312 : 0 : pp_string (pp, "mutable clusters: ");
313 : 0 : pp_newline (pp);
314 : 0 : dump_set (m_mutable_base_regs, pp);
315 : :
316 : 0 : pp_string (pp, "reachable svals: ");
317 : 0 : pp_newline (pp);
318 : 0 : dump_set (m_reachable_svals, pp);
319 : :
320 : 0 : pp_string (pp, "mutable svals: ");
321 : 0 : pp_newline (pp);
322 : 0 : dump_set (m_mutable_svals, pp);
323 : 0 : }
324 : :
325 : : /* Dump a multiline representation of this object to stderr. */
326 : :
327 : : DEBUG_FUNCTION void
328 : 0 : reachable_regions::dump () const
329 : : {
330 : 0 : tree_dump_pretty_printer pp (stderr);
331 : 0 : dump_to_pp (&pp);
332 : 0 : }
333 : :
334 : : } // namespace ana
335 : :
336 : : #endif /* #if ENABLE_ANALYZER */
|
