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 : #include "analyzer/liveness-context.h"
34 :
35 : #if ENABLE_ANALYZER
36 :
37 : namespace ana {
38 :
39 : static bool
40 99352736 : recurse_into_children_p (const symbolic::value_node &val)
41 : {
42 : /* Don't recurse into children for cropped bit vectors:
43 : the values aren't complete, so aren't live. */
44 99352736 : if (auto *bv = val.dyn_cast_bit_vector ())
45 23123418 : if (bv->get_kind () == symbolic::bit_vector::kind::cropped)
46 52399 : return false;
47 : return true;
48 : }
49 :
50 904435 : reachable_regions::reachable_regions (region_model *model)
51 904435 : : m_model (model), m_store (model->get_store ()),
52 904435 : m_reachable_base_regs (), m_mutable_base_regs ()
53 : {
54 904435 : }
55 :
56 : /* Callback called for each cluster when initializing this object. */
57 :
58 : void
59 5189414 : reachable_regions::init_cluster_cb (const region *base_reg,
60 : reachable_regions *this_ptr)
61 : {
62 5189414 : this_ptr->init_cluster (base_reg);
63 5189414 : }
64 :
65 : /* Called for each cluster when initializing this object. */
66 : void
67 5189414 : reachable_regions::init_cluster (const region *base_reg)
68 : {
69 : /* Mark any globals as mutable (and traverse what they point to). */
70 5189414 : const region *parent = base_reg->get_parent_region ();
71 5189414 : gcc_assert (parent);
72 5189414 : if (parent->get_kind () == RK_GLOBALS)
73 408091 : add (base_reg, true);
74 :
75 : /* Mark any clusters that already escaped in previous unknown calls
76 : as mutable (and traverse what they currently point to). */
77 5189414 : if (m_store->escaped_p (base_reg))
78 1207928 : add (base_reg, true);
79 :
80 5189414 : if (const symbolic_region *sym_reg = base_reg->dyn_cast_symbolic_region ())
81 : {
82 1098350 : const svalue *ptr = sym_reg->get_pointer ();
83 1098350 : symbolic::liveness_context liveness_ctxt (value_set (), *m_model);
84 1098350 : if (ptr->implicitly_live_p (liveness_ctxt))
85 902073 : add (base_reg, true);
86 1098350 : switch (ptr->get_kind ())
87 : {
88 : default:
89 : break;
90 893646 : case SK_INITIAL:
91 893646 : {
92 : /* If BASE_REG is *INIT_VAL(REG) for some other REG, see if REG is
93 : unbound and untouched. If so, then add BASE_REG as a root. */
94 893646 : const initial_svalue *init_sval
95 893646 : = as_a <const initial_svalue *> (ptr);
96 893646 : const region *init_sval_reg = init_sval->get_region ();
97 893646 : const region *other_base_reg = init_sval_reg->get_base_region ();
98 893646 : const binding_cluster *other_cluster
99 893646 : = m_store->get_cluster (other_base_reg);
100 893646 : if (other_cluster == nullptr
101 893646 : || !other_cluster->touched_p ())
102 877222 : add (base_reg, true);
103 : }
104 : break;
105 :
106 0 : case SK_UNKNOWN:
107 0 : {
108 : /* If this cluster is due to dereferencing an unknown pointer,
109 : any values written through the pointer could still
110 : be live. */
111 0 : add (base_reg, true);
112 : }
113 0 : break;
114 : }
115 1098350 : }
116 5189414 : }
117 :
118 : /* Lazily mark the cluster containing REG as being reachable, recursively
119 : adding clusters reachable from REG's cluster. */
120 : void
121 8975548 : reachable_regions::add (const region *reg, bool is_mutable)
122 : {
123 8975548 : gcc_assert (reg);
124 :
125 8975548 : const region *base_reg = const_cast <region *> (reg->get_base_region ());
126 8975548 : gcc_assert (base_reg);
127 :
128 : /* Bail out if this cluster is already in the sets at the IS_MUTABLE
129 : level of mutability. */
130 8975548 : if (!is_mutable && m_reachable_base_regs.contains (base_reg))
131 3715133 : return;
132 8851942 : m_reachable_base_regs.add (base_reg);
133 :
134 8851942 : if (is_mutable)
135 : {
136 5723659 : if (m_mutable_base_regs.contains (base_reg))
137 : return;
138 : else
139 2132132 : m_mutable_base_regs.add (base_reg);
140 : }
141 :
142 : /* Add values within the cluster. If any are pointers, add the pointee. */
143 5260415 : if (binding_cluster *bind_cluster = m_store->get_cluster (base_reg))
144 : {
145 4999099 : bind_cluster->for_each_value
146 4999099 : ([] (const symbolic::value_node &val,
147 : void *user_data) -> iter_result
148 : {
149 : ((reachable_regions *)user_data)->handle_value (val);
150 : return iter_result::keep_going;
151 : },
152 : this);
153 : }
154 : }
155 :
156 : void
157 0 : reachable_regions::handle_sval_cb (const svalue *sval,
158 : reachable_regions *this_ptr)
159 : {
160 0 : this_ptr->handle_value (*sval);
161 0 : }
162 :
163 : /* Add VAL. If it is a pointer, add the pointed-to region. */
164 :
165 : void
166 23502881 : reachable_regions::handle_value (const symbolic::value_node &val)
167 : {
168 122855617 : auto cb = [] (const symbolic::value_node &val, void *user_data) -> bool
169 : {
170 99352736 : reachable_regions *rr = (reachable_regions *)user_data;
171 99352736 : if (!rr->m_reachable_svals.contains (&val))
172 : {
173 9353598 : rr->m_reachable_svals.insert (&val);
174 9353598 : rr->handle_value (val);
175 : }
176 :
177 99352736 : return recurse_into_children_p (val);
178 : };
179 :
180 23502881 : symbolic::value_node_visitor v {cb, this};
181 23502881 : val.accept_node_visitor (v);
182 :
183 23502881 : m_mutable_svals.insert (&val);
184 :
185 23502881 : if (auto sval = val.dyn_cast_svalue ())
186 : {
187 13522980 : if (auto *bit_vec_sval = sval->dyn_cast_svalue_from_bit_vector ())
188 1334600 : handle_value (bit_vec_sval->get_bit_vector ());
189 :
190 13522980 : if (auto *ptr = sval->maybe_get_symbolic_pointer ())
191 : {
192 : /* Use const-ness of pointer type to affect mutability. */
193 2344128 : bool ptr_is_mutable = true;
194 2344128 : if (sval->get_type ()
195 2344128 : && TREE_CODE (sval->get_type ()) == POINTER_TYPE
196 4684838 : && TYPE_READONLY (TREE_TYPE (sval->get_type ())))
197 : {
198 : ptr_is_mutable = false;
199 : }
200 : else
201 : {
202 2321528 : m_mutable_svals.insert (sval);
203 : }
204 2344128 : add (&ptr->get_base_region (), ptr_is_mutable);
205 : }
206 13522980 : if (const svalue *cast = sval->maybe_undo_cast ())
207 2095073 : handle_value (*cast);
208 :
209 : /* If SVAL is the result of a reversible operation, then the operands
210 : are reachable. */
211 13522980 : switch (sval->get_kind ())
212 : {
213 : default:
214 : break;
215 2161680 : case SK_UNARYOP:
216 2161680 : {
217 2161680 : const unaryop_svalue *unaryop_sval = (const unaryop_svalue *)sval;
218 2161680 : switch (unaryop_sval->get_op ())
219 : {
220 : default:
221 : break;
222 56868 : case NEGATE_EXPR:
223 56868 : handle_value (*unaryop_sval->get_arg ());
224 56868 : break;
225 : }
226 : }
227 : break;
228 3287237 : case SK_BINOP:
229 3287237 : {
230 3287237 : const binop_svalue *binop_sval = (const binop_svalue *)sval;
231 3287237 : switch (binop_sval->get_op ())
232 : {
233 : default:
234 : break;
235 264880 : case POINTER_PLUS_EXPR:
236 264880 : handle_value (*binop_sval->get_arg0 ());
237 264880 : handle_value (*binop_sval->get_arg1 ());
238 264880 : break;
239 : }
240 : }
241 : }
242 : }
243 :
244 23502881 : if (auto *bv = val.dyn_cast_bit_vector ())
245 9979901 : if (auto *from_svalue = bv->dyn_cast_bit_vector_from_svalue ())
246 4917453 : handle_value (from_svalue->get_svalue ());
247 23502881 : }
248 :
249 : /* Add SVAL. If it is a pointer, add the pointed-to region.
250 : Use PARAM_TYPE for determining mutability. */
251 :
252 : void
253 19424 : reachable_regions::handle_parm (const svalue *sval, tree param_type)
254 : {
255 19424 : bool is_mutable = true;
256 19424 : if (param_type
257 17932 : && TREE_CODE (param_type) == POINTER_TYPE
258 31853 : && TYPE_READONLY (TREE_TYPE (param_type)))
259 3125 : is_mutable = false;
260 19424 : if (is_mutable)
261 16299 : m_mutable_svals.insert (sval);
262 : else
263 3125 : m_reachable_svals.insert (sval);
264 19424 : if (const region *base_reg = sval->maybe_get_deref_base_region ())
265 8467 : add (base_reg, is_mutable);
266 19424 : if (auto *sval_from_bv = sval->dyn_cast_svalue_from_bit_vector ())
267 : {
268 2088 : auto &bv = sval_from_bv->get_bit_vector ();
269 2088 : if (auto *concat_bv = bv.dyn_cast_concat_bit_vector ())
270 233 : for (auto child_bv : *concat_bv)
271 202 : if (auto *bv_from_sval = child_bv->dyn_cast_bit_vector_from_svalue ())
272 186 : handle_value (bv_from_sval->get_svalue ());
273 : }
274 19424 : if (const svalue *cast = sval->maybe_undo_cast ())
275 313 : handle_value (*cast);
276 19424 : }
277 :
278 : /* Update the store to mark the clusters that were found to be mutable
279 : as having escaped.
280 : Notify CTXT about escaping function_decls. */
281 :
282 : void
283 17547 : reachable_regions::mark_escaped_clusters (region_model_context *ctxt)
284 : {
285 17547 : auto_vec<const function_region *> escaped_fn_regs
286 17547 : (m_mutable_base_regs.elements ());
287 41144 : for (hash_set<const region *>::iterator iter = m_mutable_base_regs.begin ();
288 41144 : iter != m_mutable_base_regs.end (); ++iter)
289 : {
290 23597 : const region *base_reg = *iter;
291 23597 : m_store->mark_as_escaped (base_reg,
292 23597 : m_model->get_baseline_state ());
293 :
294 : /* If we have a function that's escaped, potentially add
295 : it to the worklist. */
296 23597 : if (const function_region *fn_reg = base_reg->dyn_cast_function_region ())
297 615 : escaped_fn_regs.quick_push (fn_reg);
298 : }
299 17547 : if (ctxt)
300 : {
301 : /* Sort to ensure deterministic results. */
302 12166 : escaped_fn_regs.qsort (region::cmp_ptr_ptr);
303 12166 : unsigned i;
304 12166 : const function_region *fn_reg;
305 27764 : FOR_EACH_VEC_ELT (escaped_fn_regs, i, fn_reg)
306 309 : ctxt->on_escaped_function (fn_reg->get_fndecl ());
307 : }
308 17547 : }
309 :
310 : /* Dump SET to PP, sorting it to avoid churn when comparing dumps. */
311 :
312 : template <typename T>
313 : static void
314 0 : dump_set (const hash_set<const T *> &set, pretty_printer *pp)
315 : {
316 0 : auto_vec<const T *> elements (set.elements ());
317 0 : for (typename hash_set<const T *>::iterator iter = set.begin ();
318 0 : iter != set.end (); ++iter)
319 0 : elements.quick_push (*iter);
320 :
321 0 : elements.qsort (T::cmp_ptr_ptr);
322 :
323 : unsigned i;
324 : const T *element;
325 0 : FOR_EACH_VEC_ELT (elements, i, element)
326 : {
327 0 : pp_string (pp, " ");
328 0 : element->dump_to_pp (pp, true);
329 0 : pp_newline (pp);
330 : }
331 0 : }
332 :
333 : /* Dump a multiline representation of this object to PP. */
334 :
335 : void
336 0 : reachable_regions::dump_to_pp (pretty_printer *pp) const
337 : {
338 0 : pp_string (pp, "reachable clusters: ");
339 0 : pp_newline (pp);
340 0 : dump_set (m_reachable_base_regs, pp);
341 :
342 0 : pp_string (pp, "mutable clusters: ");
343 0 : pp_newline (pp);
344 0 : dump_set (m_mutable_base_regs, pp);
345 :
346 0 : pp_string (pp, "reachable svals: ");
347 0 : pp_newline (pp);
348 0 : m_reachable_svals.dump_to_pp (pp);
349 :
350 0 : pp_string (pp, "mutable svals: ");
351 0 : pp_newline (pp);
352 0 : m_mutable_svals.dump_to_pp (pp);
353 0 : }
354 :
355 : /* Dump a multiline representation of this object to stderr. */
356 :
357 : DEBUG_FUNCTION void
358 0 : reachable_regions::dump () const
359 : {
360 0 : tree_dump_pretty_printer pp (stderr);
361 0 : dump_to_pp (&pp);
362 0 : }
363 :
364 : } // namespace ana
365 :
366 : #endif /* #if ENABLE_ANALYZER */
|