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