Line data Source code
1 : /* Finding reachable regions and values.
2 : Copyright (C) 2020-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 : #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 1004713 : reachable_regions::reachable_regions (region_model *model)
39 1004713 : : m_model (model), m_store (model->get_store ()),
40 1004713 : m_reachable_base_regs (), m_mutable_base_regs ()
41 : {
42 1004713 : }
43 :
44 : /* Callback called for each cluster when initializing this object. */
45 :
46 : void
47 8734054 : reachable_regions::init_cluster_cb (const region *base_reg,
48 : reachable_regions *this_ptr)
49 : {
50 8734054 : this_ptr->init_cluster (base_reg);
51 8734054 : }
52 :
53 : /* Called for each cluster when initializing this object. */
54 : void
55 8734054 : reachable_regions::init_cluster (const region *base_reg)
56 : {
57 : /* Mark any globals as mutable (and traverse what they point to). */
58 8734054 : const region *parent = base_reg->get_parent_region ();
59 8734054 : gcc_assert (parent);
60 8734054 : if (parent->get_kind () == RK_GLOBALS)
61 732279 : 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 8734054 : if (m_store->escaped_p (base_reg))
66 2064065 : add (base_reg, true);
67 :
68 8734054 : if (const symbolic_region *sym_reg = base_reg->dyn_cast_symbolic_region ())
69 : {
70 1768938 : const svalue *ptr = sym_reg->get_pointer ();
71 1768938 : if (ptr->implicitly_live_p (nullptr, m_model))
72 1520395 : add (base_reg, true);
73 1768938 : switch (ptr->get_kind ())
74 : {
75 : default:
76 : break;
77 1646784 : case SK_INITIAL:
78 1646784 : {
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 1646784 : const initial_svalue *init_sval
82 1646784 : = as_a <const initial_svalue *> (ptr);
83 1646784 : const region *init_sval_reg = init_sval->get_region ();
84 1646784 : const region *other_base_reg = init_sval_reg->get_base_region ();
85 1646784 : const binding_cluster *other_cluster
86 1646784 : = m_store->get_cluster (other_base_reg);
87 1646784 : if (other_cluster == nullptr
88 1646784 : || !other_cluster->touched_p ())
89 1589898 : add (base_reg, true);
90 : }
91 : break;
92 :
93 45288 : case SK_UNKNOWN:
94 45288 : case SK_CONJURED:
95 45288 : {
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 45288 : add (base_reg, true);
100 : }
101 45288 : break;
102 : }
103 : }
104 8734054 : }
105 :
106 : /* Lazily mark the cluster containing REG as being reachable, recursively
107 : adding clusters reachable from REG's cluster. */
108 : void
109 12521700 : reachable_regions::add (const region *reg, bool is_mutable)
110 : {
111 12521700 : gcc_assert (reg);
112 :
113 12521700 : const region *base_reg = const_cast <region *> (reg->get_base_region ());
114 12521700 : 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 12521700 : if (!is_mutable && m_reachable_base_regs.contains (base_reg))
119 3672070 : return;
120 12397065 : m_reachable_base_regs.add (base_reg);
121 :
122 12397065 : if (is_mutable)
123 : {
124 6852799 : if (m_mutable_base_regs.contains (base_reg))
125 : return;
126 : else
127 3305364 : m_mutable_base_regs.add (base_reg);
128 : }
129 :
130 : /* Add values within the cluster. If any are pointers, add the pointee. */
131 8849630 : if (binding_cluster *bind_cluster = m_store->get_cluster (base_reg))
132 8580851 : bind_cluster->for_each_value (handle_sval_cb, this);
133 : else
134 268779 : handle_sval (m_model->get_store_value (reg, nullptr));
135 : }
136 :
137 : void
138 10858385 : reachable_regions::handle_sval_cb (const svalue *sval,
139 : reachable_regions *this_ptr)
140 : {
141 10858385 : this_ptr->handle_sval (sval);
142 10858385 : }
143 :
144 : /* Add SVAL. If it is a pointer, add the pointed-to region. */
145 :
146 : void
147 12352252 : reachable_regions::handle_sval (const svalue *sval)
148 : {
149 12352252 : m_reachable_svals.add (sval);
150 12352252 : m_mutable_svals.add (sval);
151 12352252 : if (const region_svalue *ptr = sval->dyn_cast_region_svalue ())
152 : {
153 902500 : const region *pointee = ptr->get_pointee ();
154 : /* Use const-ness of pointer type to affect mutability. */
155 902500 : bool ptr_is_mutable = true;
156 902500 : if (ptr->get_type ()
157 870952 : && TREE_CODE (ptr->get_type ()) == POINTER_TYPE
158 1772328 : && TYPE_READONLY (TREE_TYPE (ptr->get_type ())))
159 : {
160 : ptr_is_mutable = false;
161 : }
162 : else
163 : {
164 893950 : m_mutable_svals.add (sval);
165 : }
166 902500 : add (pointee, ptr_is_mutable);
167 : }
168 : /* Treat all svalues within a compound_svalue as reachable. */
169 24704504 : if (const compound_svalue *compound_sval
170 12352252 : = sval->dyn_cast_compound_svalue ())
171 : {
172 3075 : for (auto iter = compound_sval->begin ();
173 12786 : iter != compound_sval->end (); ++iter)
174 : {
175 9711 : const svalue *iter_sval = iter.get_svalue ();
176 9711 : handle_sval (iter_sval);
177 : }
178 : }
179 12352252 : if (const svalue *cast = sval->maybe_undo_cast ())
180 817488 : handle_sval (cast);
181 :
182 : /* If SVAL is the result of a reversible operation, then the operands
183 : are reachable. */
184 12352252 : switch (sval->get_kind ())
185 : {
186 : default:
187 : break;
188 849616 : case SK_UNARYOP:
189 849616 : {
190 849616 : const unaryop_svalue *unaryop_sval = (const unaryop_svalue *)sval;
191 849616 : switch (unaryop_sval->get_op ())
192 : {
193 : default:
194 : break;
195 30220 : case NEGATE_EXPR:
196 30220 : handle_sval (unaryop_sval->get_arg ());
197 30220 : break;
198 : }
199 : }
200 : break;
201 3013155 : case SK_BINOP:
202 3013155 : {
203 3013155 : const binop_svalue *binop_sval = (const binop_svalue *)sval;
204 3013155 : switch (binop_sval->get_op ())
205 : {
206 : default:
207 : break;
208 173307 : case POINTER_PLUS_EXPR:
209 173307 : handle_sval (binop_sval->get_arg0 ());
210 173307 : handle_sval (binop_sval->get_arg1 ());
211 173307 : break;
212 : }
213 : }
214 : }
215 12352252 : }
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 18668 : reachable_regions::handle_parm (const svalue *sval, tree param_type)
222 : {
223 18668 : bool is_mutable = true;
224 18668 : if (param_type
225 17304 : && TREE_CODE (param_type) == POINTER_TYPE
226 31012 : && TYPE_READONLY (TREE_TYPE (param_type)))
227 3018 : is_mutable = false;
228 18668 : if (is_mutable)
229 15650 : m_mutable_svals.add (sval);
230 : else
231 3018 : m_reachable_svals.add (sval);
232 18668 : if (const region *base_reg = sval->maybe_get_deref_base_region ())
233 8507 : add (base_reg, is_mutable);
234 : /* Treat all svalues within a compound_svalue as reachable. */
235 37336 : if (const compound_svalue *compound_sval
236 18668 : = sval->dyn_cast_compound_svalue ())
237 : {
238 59 : for (auto iter = compound_sval->begin ();
239 329 : iter != compound_sval->end (); ++iter)
240 : {
241 270 : const svalue *iter_sval = iter.get_svalue ();
242 270 : handle_sval (iter_sval);
243 : }
244 : }
245 18668 : if (const svalue *cast = sval->maybe_undo_cast ())
246 377 : handle_sval (cast);
247 18668 : }
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 16848 : reachable_regions::mark_escaped_clusters (region_model_context *ctxt)
255 : {
256 16848 : auto_vec<const function_region *> escaped_fn_regs
257 16848 : (m_mutable_base_regs.elements ());
258 41543 : for (hash_set<const region *>::iterator iter = m_mutable_base_regs.begin ();
259 66238 : iter != m_mutable_base_regs.end (); ++iter)
260 : {
261 24695 : const region *base_reg = *iter;
262 24695 : store_manager *store_mgr = m_model->get_manager ()->get_store_manager ();
263 24695 : m_store->mark_as_escaped (*store_mgr, base_reg);
264 :
265 : /* If we have a function that's escaped, potentially add
266 : it to the worklist. */
267 24695 : if (const function_region *fn_reg = base_reg->dyn_cast_function_region ())
268 314 : escaped_fn_regs.quick_push (fn_reg);
269 : }
270 16848 : if (ctxt)
271 : {
272 : /* Sort to ensure deterministic results. */
273 12201 : escaped_fn_regs.qsort (region::cmp_ptr_ptr);
274 : unsigned i;
275 : const function_region *fn_reg;
276 27148 : FOR_EACH_VEC_ELT (escaped_fn_regs, i, fn_reg)
277 310 : ctxt->on_escaped_function (fn_reg->get_fndecl ());
278 : }
279 16848 : }
280 :
281 : /* Dump SET to PP, sorting it to avoid churn when comparing dumps. */
282 :
283 : template <typename T>
284 : static void
285 0 : dump_set (const hash_set<const T *> &set, pretty_printer *pp)
286 : {
287 0 : auto_vec<const T *> elements (set.elements ());
288 0 : for (typename hash_set<const T *>::iterator iter = set.begin ();
289 0 : iter != set.end (); ++iter)
290 0 : elements.quick_push (*iter);
291 :
292 0 : elements.qsort (T::cmp_ptr_ptr);
293 :
294 : unsigned i;
295 : const T *element;
296 0 : FOR_EACH_VEC_ELT (elements, i, element)
297 : {
298 0 : pp_string (pp, " ");
299 0 : element->dump_to_pp (pp, true);
300 0 : pp_newline (pp);
301 : }
302 0 : }
303 :
304 : /* Dump a multiline representation of this object to PP. */
305 :
306 : void
307 0 : reachable_regions::dump_to_pp (pretty_printer *pp) const
308 : {
309 0 : pp_string (pp, "reachable clusters: ");
310 0 : pp_newline (pp);
311 0 : dump_set (m_reachable_base_regs, pp);
312 :
313 0 : pp_string (pp, "mutable clusters: ");
314 0 : pp_newline (pp);
315 0 : dump_set (m_mutable_base_regs, pp);
316 :
317 0 : pp_string (pp, "reachable svals: ");
318 0 : pp_newline (pp);
319 0 : dump_set (m_reachable_svals, pp);
320 :
321 0 : pp_string (pp, "mutable svals: ");
322 0 : pp_newline (pp);
323 0 : dump_set (m_mutable_svals, pp);
324 0 : }
325 :
326 : /* Dump a multiline representation of this object to stderr. */
327 :
328 : DEBUG_FUNCTION void
329 0 : reachable_regions::dump () const
330 : {
331 0 : tree_dump_pretty_printer pp (stderr);
332 0 : dump_to_pp (&pp);
333 0 : }
334 :
335 : } // namespace ana
336 :
337 : #endif /* #if ENABLE_ANALYZER */
|
