1 /* Finding reachable regions and values.
2 Copyright (C) 2020-2024 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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)
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.
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/>. */
22 #define INCLUDE_MEMORY
23 #define INCLUDE_VECTOR
25 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "gimple-iterator.h"
31 #include "diagnostic-core.h"
36 #include "stringpool.h"
39 #include "fold-const.h"
40 #include "tree-pretty-print.h"
42 #include "analyzer/analyzer.h"
43 #include "analyzer/analyzer-logging.h"
44 #include "ordered-hash-map.h"
46 #include "analyzer/call-string.h"
47 #include "analyzer/program-point.h"
48 #include "analyzer/store.h"
49 #include "analyzer/region-model.h"
50 #include "analyzer/region-model-reachability.h"
51 #include "diagnostic.h"
52 #include "tree-diagnostic.h"
58 reachable_regions::reachable_regions (region_model
*model
)
59 : m_model (model
), m_store (model
->get_store ()),
60 m_reachable_base_regs (), m_mutable_base_regs ()
64 /* Callback called for each cluster when initializing this object. */
67 reachable_regions::init_cluster_cb (const region
*base_reg
,
68 reachable_regions
*this_ptr
)
70 this_ptr
->init_cluster (base_reg
);
73 /* Called for each cluster when initializing this object. */
75 reachable_regions::init_cluster (const region
*base_reg
)
77 /* Mark any globals as mutable (and traverse what they point to). */
78 const region
*parent
= base_reg
->get_parent_region ();
80 if (parent
->get_kind () == RK_GLOBALS
)
83 /* Mark any clusters that already escaped in previous unknown calls
84 as mutable (and traverse what they currently point to). */
85 if (m_store
->escaped_p (base_reg
))
88 if (const symbolic_region
*sym_reg
= base_reg
->dyn_cast_symbolic_region ())
90 const svalue
*ptr
= sym_reg
->get_pointer ();
91 if (ptr
->implicitly_live_p (NULL
, m_model
))
93 switch (ptr
->get_kind ())
99 /* If BASE_REG is *INIT_VAL(REG) for some other REG, see if REG is
100 unbound and untouched. If so, then add BASE_REG as a root. */
101 const initial_svalue
*init_sval
102 = as_a
<const initial_svalue
*> (ptr
);
103 const region
*init_sval_reg
= init_sval
->get_region ();
104 const region
*other_base_reg
= init_sval_reg
->get_base_region ();
105 const binding_cluster
*other_cluster
106 = m_store
->get_cluster (other_base_reg
);
107 if (other_cluster
== NULL
108 || !other_cluster
->touched_p ())
109 add (base_reg
, true);
116 /* If this cluster is due to dereferencing an unknown/conjured
117 pointer, any values written through the pointer could still
119 add (base_reg
, true);
126 /* Lazily mark the cluster containing REG as being reachable, recursively
127 adding clusters reachable from REG's cluster. */
129 reachable_regions::add (const region
*reg
, bool is_mutable
)
133 const region
*base_reg
= const_cast <region
*> (reg
->get_base_region ());
134 gcc_assert (base_reg
);
136 /* Bail out if this cluster is already in the sets at the IS_MUTABLE
137 level of mutability. */
138 if (!is_mutable
&& m_reachable_base_regs
.contains (base_reg
))
140 m_reachable_base_regs
.add (base_reg
);
144 if (m_mutable_base_regs
.contains (base_reg
))
147 m_mutable_base_regs
.add (base_reg
);
150 /* Add values within the cluster. If any are pointers, add the pointee. */
151 if (binding_cluster
*bind_cluster
= m_store
->get_cluster (base_reg
))
152 bind_cluster
->for_each_value (handle_sval_cb
, this);
154 handle_sval (m_model
->get_store_value (reg
, NULL
));
158 reachable_regions::handle_sval_cb (const svalue
*sval
,
159 reachable_regions
*this_ptr
)
161 this_ptr
->handle_sval (sval
);
164 /* Add SVAL. If it is a pointer, add the pointed-to region. */
167 reachable_regions::handle_sval (const svalue
*sval
)
169 m_reachable_svals
.add (sval
);
170 m_mutable_svals
.add (sval
);
171 if (const region_svalue
*ptr
= sval
->dyn_cast_region_svalue ())
173 const region
*pointee
= ptr
->get_pointee ();
174 /* Use const-ness of pointer type to affect mutability. */
175 bool ptr_is_mutable
= true;
177 && TREE_CODE (ptr
->get_type ()) == POINTER_TYPE
178 && TYPE_READONLY (TREE_TYPE (ptr
->get_type ())))
180 ptr_is_mutable
= false;
184 m_mutable_svals
.add (sval
);
186 add (pointee
, ptr_is_mutable
);
188 /* Treat all svalues within a compound_svalue as reachable. */
189 if (const compound_svalue
*compound_sval
190 = sval
->dyn_cast_compound_svalue ())
192 for (compound_svalue::iterator_t iter
= compound_sval
->begin ();
193 iter
!= compound_sval
->end (); ++iter
)
195 const svalue
*iter_sval
= (*iter
).second
;
196 handle_sval (iter_sval
);
199 if (const svalue
*cast
= sval
->maybe_undo_cast ())
202 /* If SVAL is the result of a reversible operation, then the operands
204 switch (sval
->get_kind ())
210 const unaryop_svalue
*unaryop_sval
= (const unaryop_svalue
*)sval
;
211 switch (unaryop_sval
->get_op ())
216 handle_sval (unaryop_sval
->get_arg ());
223 const binop_svalue
*binop_sval
= (const binop_svalue
*)sval
;
224 switch (binop_sval
->get_op ())
228 case POINTER_PLUS_EXPR
:
229 handle_sval (binop_sval
->get_arg0 ());
230 handle_sval (binop_sval
->get_arg1 ());
237 /* Add SVAL. If it is a pointer, add the pointed-to region.
238 Use PARAM_TYPE for determining mutability. */
241 reachable_regions::handle_parm (const svalue
*sval
, tree param_type
)
243 bool is_mutable
= true;
245 && TREE_CODE (param_type
) == POINTER_TYPE
246 && TYPE_READONLY (TREE_TYPE (param_type
)))
249 m_mutable_svals
.add (sval
);
251 m_reachable_svals
.add (sval
);
252 if (const region
*base_reg
= sval
->maybe_get_deref_base_region ())
253 add (base_reg
, is_mutable
);
254 /* Treat all svalues within a compound_svalue as reachable. */
255 if (const compound_svalue
*compound_sval
256 = sval
->dyn_cast_compound_svalue ())
258 for (compound_svalue::iterator_t iter
= compound_sval
->begin ();
259 iter
!= compound_sval
->end (); ++iter
)
261 const svalue
*iter_sval
= (*iter
).second
;
262 handle_sval (iter_sval
);
265 if (const svalue
*cast
= sval
->maybe_undo_cast ())
269 /* Update the store to mark the clusters that were found to be mutable
271 Notify CTXT about escaping function_decls. */
274 reachable_regions::mark_escaped_clusters (region_model_context
*ctxt
)
276 auto_vec
<const function_region
*> escaped_fn_regs
277 (m_mutable_base_regs
.elements ());
278 for (hash_set
<const region
*>::iterator iter
= m_mutable_base_regs
.begin ();
279 iter
!= m_mutable_base_regs
.end (); ++iter
)
281 const region
*base_reg
= *iter
;
282 m_store
->mark_as_escaped (base_reg
);
284 /* If we have a function that's escaped, potentially add
285 it to the worklist. */
286 if (const function_region
*fn_reg
= base_reg
->dyn_cast_function_region ())
287 escaped_fn_regs
.quick_push (fn_reg
);
291 /* Sort to ensure deterministic results. */
292 escaped_fn_regs
.qsort (region::cmp_ptr_ptr
);
294 const function_region
*fn_reg
;
295 FOR_EACH_VEC_ELT (escaped_fn_regs
, i
, fn_reg
)
296 ctxt
->on_escaped_function (fn_reg
->get_fndecl ());
300 /* Dump SET to PP, sorting it to avoid churn when comparing dumps. */
302 template <typename T
>
304 dump_set (const hash_set
<const T
*> &set
, pretty_printer
*pp
)
306 auto_vec
<const T
*> elements (set
.elements ());
307 for (typename hash_set
<const T
*>::iterator iter
= set
.begin ();
308 iter
!= set
.end (); ++iter
)
309 elements
.quick_push (*iter
);
311 elements
.qsort (T::cmp_ptr_ptr
);
315 FOR_EACH_VEC_ELT (elements
, i
, element
)
318 element
->dump_to_pp (pp
, true);
323 /* Dump a multiline representation of this object to PP. */
326 reachable_regions::dump_to_pp (pretty_printer
*pp
) const
328 pp_string (pp
, "reachable clusters: ");
330 dump_set (m_reachable_base_regs
, pp
);
332 pp_string (pp
, "mutable clusters: ");
334 dump_set (m_mutable_base_regs
, pp
);
336 pp_string (pp
, "reachable svals: ");
338 dump_set (m_reachable_svals
, pp
);
340 pp_string (pp
, "mutable svals: ");
342 dump_set (m_mutable_svals
, pp
);
345 /* Dump a multiline representation of this object to stderr. */
348 reachable_regions::dump () const
351 pp_format_decoder (&pp
) = default_tree_printer
;
352 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
353 pp
.set_output_stream (stderr
);
360 #endif /* #if ENABLE_ANALYZER */