1 /* Classes for modeling the state of memory.
2 Copyright (C) 2019-2022 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/>. */
21 #ifndef GCC_ANALYZER_REGION_MODEL_H
22 #define GCC_ANALYZER_REGION_MODEL_H
24 /* Implementation of the region-based ternary model described in:
25 "A Memory Model for Static Analysis of C Programs"
26 (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
27 http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf */
29 #include "analyzer/svalue.h"
30 #include "analyzer/region.h"
36 extern void add_path_var (path_var pv
, hash
&hstate
);
37 } // namespace inchash
45 one_way_id_map (int num_ids
);
46 void put (T src
, T dst
);
47 T
get_dst_for_src (T src
) const;
48 void dump_to_pp (pretty_printer
*pp
) const;
50 void update (T
*) const;
53 auto_vec
<T
> m_src_to_dst
;
56 /* class one_way_id_map. */
58 /* one_way_id_map's ctor, which populates the map with dummy null values. */
61 inline one_way_id_map
<T
>::one_way_id_map (int num_svalues
)
62 : m_src_to_dst (num_svalues
)
64 for (int i
= 0; i
< num_svalues
; i
++)
65 m_src_to_dst
.quick_push (T::null ());
68 /* Record that SRC is to be mapped to DST. */
72 one_way_id_map
<T
>::put (T src
, T dst
)
74 m_src_to_dst
[src
.as_int ()] = dst
;
77 /* Get the new value for SRC within the map. */
81 one_way_id_map
<T
>::get_dst_for_src (T src
) const
85 return m_src_to_dst
[src
.as_int ()];
88 /* Dump this map to PP. */
92 one_way_id_map
<T
>::dump_to_pp (pretty_printer
*pp
) const
94 pp_string (pp
, "src to dst: {");
97 FOR_EACH_VEC_ELT (m_src_to_dst
, i
, dst
)
100 pp_string (pp
, ", ");
101 T
src (T::from_int (i
));
103 pp_string (pp
, " -> ");
110 /* Dump this map to stderr. */
112 template <typename T
>
113 DEBUG_FUNCTION
inline void
114 one_way_id_map
<T
>::dump () const
117 pp
.buffer
->stream
= stderr
;
122 /* Update *ID from the old value to its new value in this map. */
124 template <typename T
>
126 one_way_id_map
<T
>::update (T
*id
) const
128 *id
= get_dst_for_src (*id
);
131 /* A mapping from region to svalue for use when tracking state. */
133 class region_to_value_map
136 typedef hash_map
<const region
*, const svalue
*> hash_map_t
;
137 typedef hash_map_t::iterator iterator
;
139 region_to_value_map () : m_hash_map () {}
140 region_to_value_map (const region_to_value_map
&other
)
141 : m_hash_map (other
.m_hash_map
) {}
142 region_to_value_map
&operator= (const region_to_value_map
&other
);
144 bool operator== (const region_to_value_map
&other
) const;
145 bool operator!= (const region_to_value_map
&other
) const
147 return !(*this == other
);
150 iterator
begin () const { return m_hash_map
.begin (); }
151 iterator
end () const { return m_hash_map
.end (); }
153 const svalue
* const *get (const region
*reg
) const
155 return const_cast <hash_map_t
&> (m_hash_map
).get (reg
);
157 void put (const region
*reg
, const svalue
*sval
)
159 m_hash_map
.put (reg
, sval
);
161 void remove (const region
*reg
)
163 m_hash_map
.remove (reg
);
166 bool is_empty () const { return m_hash_map
.is_empty (); }
168 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
169 void dump (bool simple
) const;
171 bool can_merge_with_p (const region_to_value_map
&other
,
172 region_to_value_map
*out
) const;
174 void purge_state_involving (const svalue
*sval
);
177 hash_map_t m_hash_map
;
180 /* Various operations delete information from a region_model.
182 This struct tracks how many of each kind of entity were purged (e.g.
183 for selftests, and for debugging). */
190 m_num_equiv_classes (0),
191 m_num_constraints (0),
192 m_num_bounded_ranges_constraints (0),
193 m_num_client_items (0)
198 int m_num_equiv_classes
;
199 int m_num_constraints
;
200 int m_num_bounded_ranges_constraints
;
201 int m_num_client_items
;
204 /* A base class for visiting regions and svalues, with do-nothing
205 base implementations of the per-subclass vfuncs. */
210 virtual void visit_region_svalue (const region_svalue
*) {}
211 virtual void visit_constant_svalue (const constant_svalue
*) {}
212 virtual void visit_unknown_svalue (const unknown_svalue
*) {}
213 virtual void visit_poisoned_svalue (const poisoned_svalue
*) {}
214 virtual void visit_setjmp_svalue (const setjmp_svalue
*) {}
215 virtual void visit_initial_svalue (const initial_svalue
*) {}
216 virtual void visit_unaryop_svalue (const unaryop_svalue
*) {}
217 virtual void visit_binop_svalue (const binop_svalue
*) {}
218 virtual void visit_sub_svalue (const sub_svalue
*) {}
219 virtual void visit_repeated_svalue (const repeated_svalue
*) {}
220 virtual void visit_bits_within_svalue (const bits_within_svalue
*) {}
221 virtual void visit_unmergeable_svalue (const unmergeable_svalue
*) {}
222 virtual void visit_placeholder_svalue (const placeholder_svalue
*) {}
223 virtual void visit_widening_svalue (const widening_svalue
*) {}
224 virtual void visit_compound_svalue (const compound_svalue
*) {}
225 virtual void visit_conjured_svalue (const conjured_svalue
*) {}
226 virtual void visit_asm_output_svalue (const asm_output_svalue
*) {}
227 virtual void visit_const_fn_result_svalue (const const_fn_result_svalue
*) {}
229 virtual void visit_region (const region
*) {}
236 /* A class responsible for owning and consolidating region and svalue
238 region and svalue instances are immutable as far as clients are
239 concerned, so they are provided as "const" ptrs. */
241 class region_model_manager
244 region_model_manager (logger
*logger
= NULL
);
245 ~region_model_manager ();
247 /* call_string consolidation. */
248 const call_string
&get_empty_call_string () const
250 return m_empty_call_string
;
253 /* svalue consolidation. */
254 const svalue
*get_or_create_constant_svalue (tree cst_expr
);
255 const svalue
*get_or_create_int_cst (tree type
, poly_int64
);
256 const svalue
*get_or_create_unknown_svalue (tree type
);
257 const svalue
*get_or_create_setjmp_svalue (const setjmp_record
&r
,
259 const svalue
*get_or_create_poisoned_svalue (enum poison_kind kind
,
261 const svalue
*get_or_create_initial_value (const region
*reg
);
262 const svalue
*get_ptr_svalue (tree ptr_type
, const region
*pointee
);
263 const svalue
*get_or_create_unaryop (tree type
, enum tree_code op
,
265 const svalue
*get_or_create_cast (tree type
, const svalue
*arg
);
266 const svalue
*get_or_create_binop (tree type
,
268 const svalue
*arg0
, const svalue
*arg1
);
269 const svalue
*get_or_create_sub_svalue (tree type
,
270 const svalue
*parent_svalue
,
271 const region
*subregion
);
272 const svalue
*get_or_create_repeated_svalue (tree type
,
273 const svalue
*outer_size
,
274 const svalue
*inner_svalue
);
275 const svalue
*get_or_create_bits_within (tree type
,
276 const bit_range
&bits
,
277 const svalue
*inner_svalue
);
278 const svalue
*get_or_create_unmergeable (const svalue
*arg
);
279 const svalue
*get_or_create_widening_svalue (tree type
,
280 const program_point
&point
,
281 const svalue
*base_svalue
,
282 const svalue
*iter_svalue
);
283 const svalue
*get_or_create_compound_svalue (tree type
,
284 const binding_map
&map
);
285 const svalue
*get_or_create_conjured_svalue (tree type
, const gimple
*stmt
,
286 const region
*id_reg
,
287 const conjured_purge
&p
);
289 get_or_create_asm_output_svalue (tree type
,
290 const gasm
*asm_stmt
,
292 const vec
<const svalue
*> &inputs
);
294 get_or_create_const_fn_result_svalue (tree type
,
296 const vec
<const svalue
*> &inputs
);
298 const svalue
*maybe_get_char_from_string_cst (tree string_cst
,
299 tree byte_offset_cst
);
301 /* Dynamically-allocated svalue instances.
302 The number of these within the analysis can grow arbitrarily.
303 They are still owned by the manager. */
304 const svalue
*create_unique_svalue (tree type
);
306 /* region consolidation. */
307 const stack_region
* get_stack_region () const { return &m_stack_region
; }
308 const heap_region
*get_heap_region () const { return &m_heap_region
; }
309 const code_region
*get_code_region () const { return &m_code_region
; }
310 const globals_region
*get_globals_region () const
312 return &m_globals_region
;
314 const function_region
*get_region_for_fndecl (tree fndecl
);
315 const label_region
*get_region_for_label (tree label
);
316 const decl_region
*get_region_for_global (tree expr
);
317 const region
*get_field_region (const region
*parent
, tree field
);
318 const region
*get_element_region (const region
*parent
,
320 const svalue
*index
);
321 const region
*get_offset_region (const region
*parent
,
323 const svalue
*byte_offset
);
324 const region
*get_sized_region (const region
*parent
,
326 const svalue
*byte_size_sval
);
327 const region
*get_cast_region (const region
*original_region
,
329 const frame_region
*get_frame_region (const frame_region
*calling_frame
,
331 const region
*get_symbolic_region (const svalue
*sval
);
332 const string_region
*get_region_for_string (tree string_cst
);
333 const region
*get_bit_range (const region
*parent
, tree type
,
334 const bit_range
&bits
);
335 const var_arg_region
*get_var_arg_region (const frame_region
*parent
,
338 const region
*get_unknown_symbolic_region (tree region_type
);
341 get_region_for_unexpected_tree_code (region_model_context
*ctxt
,
343 const dump_location_t
&loc
);
345 unsigned alloc_region_id () { return m_next_region_id
++; }
347 store_manager
*get_store_manager () { return &m_store_mgr
; }
348 bounded_ranges_manager
*get_range_manager () const { return m_range_mgr
; }
350 /* Dynamically-allocated region instances.
351 The number of these within the analysis can grow arbitrarily.
352 They are still owned by the manager. */
353 const region
*create_region_for_heap_alloc ();
354 const region
*create_region_for_alloca (const frame_region
*frame
);
356 void log_stats (logger
*logger
, bool show_objs
) const;
358 void begin_checking_feasibility (void) { m_checking_feasibility
= true; }
359 void end_checking_feasibility (void) { m_checking_feasibility
= false; }
361 logger
*get_logger () const { return m_logger
; }
363 void dump_untracked_regions () const;
366 bool too_complex_p (const complexity
&c
) const;
367 bool reject_if_too_complex (svalue
*sval
);
369 const svalue
*maybe_fold_unaryop (tree type
, enum tree_code op
,
371 const svalue
*maybe_fold_binop (tree type
, enum tree_code op
,
372 const svalue
*arg0
, const svalue
*arg1
);
373 const svalue
*maybe_fold_sub_svalue (tree type
,
374 const svalue
*parent_svalue
,
375 const region
*subregion
);
376 const svalue
*maybe_fold_repeated_svalue (tree type
,
377 const svalue
*outer_size
,
378 const svalue
*inner_svalue
);
379 const svalue
*maybe_fold_bits_within_svalue (tree type
,
380 const bit_range
&bits
,
381 const svalue
*inner_svalue
);
382 const svalue
*maybe_undo_optimize_bit_field_compare (tree type
,
383 const compound_svalue
*compound_sval
,
384 tree cst
, const svalue
*arg1
);
385 const svalue
*maybe_fold_asm_output_svalue (tree type
,
386 const vec
<const svalue
*> &inputs
);
390 const call_string m_empty_call_string
;
392 unsigned m_next_region_id
;
393 root_region m_root_region
;
394 stack_region m_stack_region
;
395 heap_region m_heap_region
;
397 /* svalue consolidation. */
398 typedef hash_map
<tree
, constant_svalue
*> constants_map_t
;
399 constants_map_t m_constants_map
;
401 typedef hash_map
<tree
, unknown_svalue
*> unknowns_map_t
;
402 unknowns_map_t m_unknowns_map
;
403 const unknown_svalue
*m_unknown_NULL
;
405 typedef hash_map
<poisoned_svalue::key_t
,
406 poisoned_svalue
*> poisoned_values_map_t
;
407 poisoned_values_map_t m_poisoned_values_map
;
409 typedef hash_map
<setjmp_svalue::key_t
,
410 setjmp_svalue
*> setjmp_values_map_t
;
411 setjmp_values_map_t m_setjmp_values_map
;
413 typedef hash_map
<const region
*, initial_svalue
*> initial_values_map_t
;
414 initial_values_map_t m_initial_values_map
;
416 typedef hash_map
<region_svalue::key_t
, region_svalue
*> pointer_values_map_t
;
417 pointer_values_map_t m_pointer_values_map
;
419 typedef hash_map
<unaryop_svalue::key_t
,
420 unaryop_svalue
*> unaryop_values_map_t
;
421 unaryop_values_map_t m_unaryop_values_map
;
423 typedef hash_map
<binop_svalue::key_t
, binop_svalue
*> binop_values_map_t
;
424 binop_values_map_t m_binop_values_map
;
426 typedef hash_map
<sub_svalue::key_t
, sub_svalue
*> sub_values_map_t
;
427 sub_values_map_t m_sub_values_map
;
429 typedef hash_map
<repeated_svalue::key_t
,
430 repeated_svalue
*> repeated_values_map_t
;
431 repeated_values_map_t m_repeated_values_map
;
433 typedef hash_map
<bits_within_svalue::key_t
,
434 bits_within_svalue
*> bits_within_values_map_t
;
435 bits_within_values_map_t m_bits_within_values_map
;
437 typedef hash_map
<const svalue
*,
438 unmergeable_svalue
*> unmergeable_values_map_t
;
439 unmergeable_values_map_t m_unmergeable_values_map
;
441 typedef hash_map
<widening_svalue::key_t
,
443 widening_svalue::key_t::hash_map_traits*/
>
444 widening_values_map_t
;
445 widening_values_map_t m_widening_values_map
;
447 typedef hash_map
<compound_svalue::key_t
,
448 compound_svalue
*> compound_values_map_t
;
449 compound_values_map_t m_compound_values_map
;
451 typedef hash_map
<conjured_svalue::key_t
,
452 conjured_svalue
*> conjured_values_map_t
;
453 conjured_values_map_t m_conjured_values_map
;
455 typedef hash_map
<asm_output_svalue::key_t
,
456 asm_output_svalue
*> asm_output_values_map_t
;
457 asm_output_values_map_t m_asm_output_values_map
;
459 typedef hash_map
<const_fn_result_svalue::key_t
,
460 const_fn_result_svalue
*> const_fn_result_values_map_t
;
461 const_fn_result_values_map_t m_const_fn_result_values_map
;
463 bool m_checking_feasibility
;
465 /* "Dynamically-allocated" svalue instances.
466 The number of these within the analysis can grow arbitrarily.
467 They are still owned by the manager. */
468 auto_delete_vec
<svalue
> m_managed_dynamic_svalues
;
470 /* Maximum complexity of svalues that weren't rejected. */
471 complexity m_max_complexity
;
473 /* region consolidation. */
475 code_region m_code_region
;
476 typedef hash_map
<tree
, function_region
*> fndecls_map_t
;
477 typedef fndecls_map_t::iterator fndecls_iterator_t
;
478 fndecls_map_t m_fndecls_map
;
480 typedef hash_map
<tree
, label_region
*> labels_map_t
;
481 typedef labels_map_t::iterator labels_iterator_t
;
482 labels_map_t m_labels_map
;
484 globals_region m_globals_region
;
485 typedef hash_map
<tree
, decl_region
*> globals_map_t
;
486 typedef globals_map_t::iterator globals_iterator_t
;
487 globals_map_t m_globals_map
;
489 consolidation_map
<field_region
> m_field_regions
;
490 consolidation_map
<element_region
> m_element_regions
;
491 consolidation_map
<offset_region
> m_offset_regions
;
492 consolidation_map
<sized_region
> m_sized_regions
;
493 consolidation_map
<cast_region
> m_cast_regions
;
494 consolidation_map
<frame_region
> m_frame_regions
;
495 consolidation_map
<symbolic_region
> m_symbolic_regions
;
497 typedef hash_map
<tree
, string_region
*> string_map_t
;
498 string_map_t m_string_map
;
500 consolidation_map
<bit_range_region
> m_bit_range_regions
;
501 consolidation_map
<var_arg_region
> m_var_arg_regions
;
503 store_manager m_store_mgr
;
505 bounded_ranges_manager
*m_range_mgr
;
507 /* "Dynamically-allocated" region instances.
508 The number of these within the analysis can grow arbitrarily.
509 They are still owned by the manager. */
510 auto_delete_vec
<region
> m_managed_dynamic_regions
;
513 struct append_regions_cb_data
;
515 /* Helper class for handling calls to functions with known behavior.
516 Implemented in region-model-impl-calls.c. */
521 call_details (const gcall
*call
, region_model
*model
,
522 region_model_context
*ctxt
);
524 region_model_manager
*get_manager () const;
525 region_model_context
*get_ctxt () const { return m_ctxt
; }
526 uncertainty_t
*get_uncertainty () const;
527 tree
get_lhs_type () const { return m_lhs_type
; }
528 const region
*get_lhs_region () const { return m_lhs_region
; }
530 bool maybe_set_lhs (const svalue
*result
) const;
532 unsigned num_args () const;
534 const gcall
*get_call_stmt () const { return m_call
; }
536 tree
get_arg_tree (unsigned idx
) const;
537 tree
get_arg_type (unsigned idx
) const;
538 const svalue
*get_arg_svalue (unsigned idx
) const;
539 const char *get_arg_string_literal (unsigned idx
) const;
541 tree
get_fndecl_for_call () const;
543 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
544 void dump (bool simple
) const;
546 const svalue
*get_or_create_conjured_svalue (const region
*) const;
550 region_model
*m_model
;
551 region_model_context
*m_ctxt
;
553 const region
*m_lhs_region
;
556 /* A region_model encapsulates a representation of the state of memory, with
557 a tree of regions, along with their associated values.
558 The representation is graph-like because values can be pointers to
561 - a constraint_manager, capturing relationships between the values, and
562 - dynamic extents, mapping dynamically-allocated regions to svalues (their
568 typedef region_to_value_map dynamic_extents_t
;
570 region_model (region_model_manager
*mgr
);
571 region_model (const region_model
&other
);
573 region_model
&operator= (const region_model
&other
);
575 bool operator== (const region_model
&other
) const;
576 bool operator!= (const region_model
&other
) const
578 return !(*this == other
);
581 hashval_t
hash () const;
583 void print (pretty_printer
*pp
) const;
585 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
586 void dump (FILE *fp
, bool simple
, bool multiline
) const;
587 void dump (bool simple
) const;
591 void validate () const;
593 void canonicalize ();
594 bool canonicalized_p () const;
597 on_stmt_pre (const gimple
*stmt
,
598 bool *out_terminate_path
,
599 bool *out_unknown_side_effects
,
600 region_model_context
*ctxt
);
602 void on_assignment (const gassign
*stmt
, region_model_context
*ctxt
);
603 const svalue
*get_gassign_result (const gassign
*assign
,
604 region_model_context
*ctxt
);
605 void on_asm_stmt (const gasm
*asm_stmt
, region_model_context
*ctxt
);
606 bool on_call_pre (const gcall
*stmt
, region_model_context
*ctxt
,
607 bool *out_terminate_path
);
608 void on_call_post (const gcall
*stmt
,
609 bool unknown_side_effects
,
610 region_model_context
*ctxt
);
612 void purge_state_involving (const svalue
*sval
, region_model_context
*ctxt
);
614 /* Specific handling for on_call_pre. */
615 void impl_call_alloca (const call_details
&cd
);
616 void impl_call_analyzer_describe (const gcall
*call
,
617 region_model_context
*ctxt
);
618 void impl_call_analyzer_dump_capacity (const gcall
*call
,
619 region_model_context
*ctxt
);
620 void impl_call_analyzer_dump_escaped (const gcall
*call
);
621 void impl_call_analyzer_eval (const gcall
*call
,
622 region_model_context
*ctxt
);
623 void impl_call_builtin_expect (const call_details
&cd
);
624 void impl_call_calloc (const call_details
&cd
);
625 bool impl_call_error (const call_details
&cd
, unsigned min_args
,
626 bool *out_terminate_path
);
627 void impl_call_fgets (const call_details
&cd
);
628 void impl_call_fread (const call_details
&cd
);
629 void impl_call_free (const call_details
&cd
);
630 void impl_call_malloc (const call_details
&cd
);
631 void impl_call_memcpy (const call_details
&cd
);
632 void impl_call_memset (const call_details
&cd
);
633 void impl_call_putenv (const call_details
&cd
);
634 void impl_call_realloc (const call_details
&cd
);
635 void impl_call_strchr (const call_details
&cd
);
636 void impl_call_strcpy (const call_details
&cd
);
637 void impl_call_strlen (const call_details
&cd
);
638 void impl_call_operator_new (const call_details
&cd
);
639 void impl_call_operator_delete (const call_details
&cd
);
640 void impl_deallocation_call (const call_details
&cd
);
642 /* Implemented in varargs.cc. */
643 void impl_call_va_start (const call_details
&cd
);
644 void impl_call_va_copy (const call_details
&cd
);
645 void impl_call_va_arg (const call_details
&cd
);
646 void impl_call_va_end (const call_details
&cd
);
648 void handle_unrecognized_call (const gcall
*call
,
649 region_model_context
*ctxt
);
650 void get_reachable_svalues (svalue_set
*out
,
651 const svalue
*extra_sval
,
652 const uncertainty_t
*uncertainty
);
654 void on_return (const greturn
*stmt
, region_model_context
*ctxt
);
655 void on_setjmp (const gcall
*stmt
, const exploded_node
*enode
,
656 region_model_context
*ctxt
);
657 void on_longjmp (const gcall
*longjmp_call
, const gcall
*setjmp_call
,
658 int setjmp_stack_depth
, region_model_context
*ctxt
);
660 void update_for_phis (const supernode
*snode
,
661 const cfg_superedge
*last_cfg_superedge
,
662 region_model_context
*ctxt
);
664 void handle_phi (const gphi
*phi
, tree lhs
, tree rhs
,
665 const region_model
&old_state
,
666 region_model_context
*ctxt
);
668 bool maybe_update_for_edge (const superedge
&edge
,
669 const gimple
*last_stmt
,
670 region_model_context
*ctxt
,
671 rejected_constraint
**out
);
673 void update_for_gcall (const gcall
*call_stmt
,
674 region_model_context
*ctxt
,
675 function
*callee
= NULL
);
677 void update_for_return_gcall (const gcall
*call_stmt
,
678 region_model_context
*ctxt
);
680 const region
*push_frame (function
*fun
, const vec
<const svalue
*> *arg_sids
,
681 region_model_context
*ctxt
);
682 const frame_region
*get_current_frame () const { return m_current_frame
; }
683 function
* get_current_function () const;
684 void pop_frame (tree result_lvalue
,
685 const svalue
**out_result
,
686 region_model_context
*ctxt
);
687 int get_stack_depth () const;
688 const frame_region
*get_frame_at_index (int index
) const;
690 const region
*get_lvalue (path_var pv
, region_model_context
*ctxt
) const;
691 const region
*get_lvalue (tree expr
, region_model_context
*ctxt
) const;
692 const svalue
*get_rvalue (path_var pv
, region_model_context
*ctxt
) const;
693 const svalue
*get_rvalue (tree expr
, region_model_context
*ctxt
) const;
695 const region
*deref_rvalue (const svalue
*ptr_sval
, tree ptr_tree
,
696 region_model_context
*ctxt
) const;
698 const svalue
*get_rvalue_for_bits (tree type
,
700 const bit_range
&bits
,
701 region_model_context
*ctxt
) const;
703 void set_value (const region
*lhs_reg
, const svalue
*rhs_sval
,
704 region_model_context
*ctxt
);
705 void set_value (tree lhs
, tree rhs
, region_model_context
*ctxt
);
706 void clobber_region (const region
*reg
);
707 void purge_region (const region
*reg
);
708 void fill_region (const region
*reg
, const svalue
*sval
);
709 void zero_fill_region (const region
*reg
);
710 void mark_region_as_unknown (const region
*reg
, uncertainty_t
*uncertainty
);
712 tristate
eval_condition (const svalue
*lhs
,
714 const svalue
*rhs
) const;
715 tristate
eval_condition_without_cm (const svalue
*lhs
,
717 const svalue
*rhs
) const;
718 tristate
compare_initial_and_pointer (const initial_svalue
*init
,
719 const region_svalue
*ptr
) const;
720 tristate
eval_condition (tree lhs
,
723 region_model_context
*ctxt
);
724 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
725 region_model_context
*ctxt
);
726 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
727 region_model_context
*ctxt
,
728 rejected_constraint
**out
);
730 const region
*create_region_for_heap_alloc (const svalue
*size_in_bytes
,
731 region_model_context
*ctxt
);
732 const region
*create_region_for_alloca (const svalue
*size_in_bytes
,
733 region_model_context
*ctxt
);
735 tree
get_representative_tree (const svalue
*sval
) const;
737 get_representative_path_var (const svalue
*sval
,
738 svalue_set
*visited
) const;
740 get_representative_path_var (const region
*reg
,
741 svalue_set
*visited
) const;
744 constraint_manager
*get_constraints ()
746 return m_constraints
;
749 store
*get_store () { return &m_store
; }
750 const store
*get_store () const { return &m_store
; }
752 const dynamic_extents_t
&
753 get_dynamic_extents () const
755 return m_dynamic_extents
;
757 const svalue
*get_dynamic_extents (const region
*reg
) const;
758 void set_dynamic_extents (const region
*reg
,
759 const svalue
*size_in_bytes
,
760 region_model_context
*ctxt
);
761 void unset_dynamic_extents (const region
*reg
);
763 region_model_manager
*get_manager () const { return m_mgr
; }
764 bounded_ranges_manager
*get_range_manager () const
766 return m_mgr
->get_range_manager ();
769 void unbind_region_and_descendents (const region
*reg
,
770 enum poison_kind pkind
);
772 bool can_merge_with_p (const region_model
&other_model
,
773 const program_point
&point
,
774 region_model
*out_model
,
775 const extrinsic_state
*ext_state
= NULL
,
776 const program_state
*state_a
= NULL
,
777 const program_state
*state_b
= NULL
) const;
779 tree
get_fndecl_for_call (const gcall
*call
,
780 region_model_context
*ctxt
);
782 void get_regions_for_current_frame (auto_vec
<const decl_region
*> *out
) const;
783 static void append_regions_cb (const region
*base_reg
,
784 struct append_regions_cb_data
*data
);
786 const svalue
*get_store_value (const region
*reg
,
787 region_model_context
*ctxt
) const;
789 bool region_exists_p (const region
*reg
) const;
791 void loop_replay_fixup (const region_model
*dst_state
);
793 const svalue
*get_capacity (const region
*reg
) const;
795 /* Implemented in sm-malloc.cc */
796 void on_realloc_with_move (const call_details
&cd
,
797 const svalue
*old_ptr_sval
,
798 const svalue
*new_ptr_sval
);
801 const region
*get_lvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
802 const svalue
*get_rvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
805 get_representative_path_var_1 (const svalue
*sval
,
806 svalue_set
*visited
) const;
808 get_representative_path_var_1 (const region
*reg
,
809 svalue_set
*visited
) const;
811 bool add_constraint (const svalue
*lhs
,
814 region_model_context
*ctxt
);
815 bool add_constraints_from_binop (const svalue
*outer_lhs
,
816 enum tree_code outer_op
,
817 const svalue
*outer_rhs
,
819 region_model_context
*ctxt
);
821 void update_for_call_superedge (const call_superedge
&call_edge
,
822 region_model_context
*ctxt
);
823 void update_for_return_superedge (const return_superedge
&return_edge
,
824 region_model_context
*ctxt
);
825 void update_for_call_summary (const callgraph_superedge
&cg_sedge
,
826 region_model_context
*ctxt
);
827 bool apply_constraints_for_gcond (const cfg_superedge
&edge
,
828 const gcond
*cond_stmt
,
829 region_model_context
*ctxt
,
830 rejected_constraint
**out
);
831 bool apply_constraints_for_gswitch (const switch_cfg_superedge
&edge
,
832 const gswitch
*switch_stmt
,
833 region_model_context
*ctxt
,
834 rejected_constraint
**out
);
835 bool apply_constraints_for_exception (const gimple
*last_stmt
,
836 region_model_context
*ctxt
,
837 rejected_constraint
**out
);
839 int poison_any_pointers_to_descendents (const region
*reg
,
840 enum poison_kind pkind
);
842 void on_top_level_param (tree param
, region_model_context
*ctxt
);
844 bool called_from_main_p () const;
845 const svalue
*get_initial_value_for_global (const region
*reg
) const;
847 const svalue
*check_for_poison (const svalue
*sval
,
849 region_model_context
*ctxt
) const;
850 const region
* get_region_for_poisoned_expr (tree expr
) const;
852 void check_dynamic_size_for_taint (enum memory_space mem_space
,
853 const svalue
*size_in_bytes
,
854 region_model_context
*ctxt
) const;
856 void check_region_for_taint (const region
*reg
,
857 enum access_direction dir
,
858 region_model_context
*ctxt
) const;
860 void check_for_writable_region (const region
* dest_reg
,
861 region_model_context
*ctxt
) const;
862 void check_region_access (const region
*reg
,
863 enum access_direction dir
,
864 region_model_context
*ctxt
) const;
865 void check_region_for_write (const region
*dest_reg
,
866 region_model_context
*ctxt
) const;
867 void check_region_for_read (const region
*src_reg
,
868 region_model_context
*ctxt
) const;
869 void check_region_size (const region
*lhs_reg
, const svalue
*rhs_sval
,
870 region_model_context
*ctxt
) const;
872 void check_call_args (const call_details
&cd
) const;
873 void check_external_function_for_access_attr (const gcall
*call
,
875 region_model_context
*ctxt
) const;
877 /* Storing this here to avoid passing it around everywhere. */
878 region_model_manager
*const m_mgr
;
882 constraint_manager
*m_constraints
; // TODO: embed, rather than dynalloc?
884 const frame_region
*m_current_frame
;
886 /* Map from base region to size in bytes, for tracking the sizes of
887 dynamically-allocated regions.
888 This is part of the region_model rather than the region to allow for
889 memory regions to be resized (e.g. by realloc). */
890 dynamic_extents_t m_dynamic_extents
;
893 /* Some region_model activity could lead to warnings (e.g. attempts to use an
894 uninitialized value). This abstract base class encapsulates an interface
895 for the region model to use when emitting such warnings.
897 Having this as an abstract base class allows us to support the various
898 operations needed by program_state in the analyzer within region_model,
899 whilst keeping them somewhat modularized. */
901 class region_model_context
904 /* Hook for clients to store pending diagnostics.
905 Return true if the diagnostic was stored, or false if it was deleted. */
906 virtual bool warn (pending_diagnostic
*d
) = 0;
908 /* Hook for clients to add a note to the last previously stored pending diagnostic.
909 Takes ownership of the pending_node (or deletes it). */
910 virtual void add_note (pending_note
*pn
) = 0;
912 /* Hook for clients to be notified when an SVAL that was reachable
913 in a previous state is no longer live, so that clients can emit warnings
915 virtual void on_svalue_leak (const svalue
*sval
) = 0;
917 /* Hook for clients to be notified when the set of explicitly live
918 svalues changes, so that they can purge state relating to dead
920 virtual void on_liveness_change (const svalue_set
&live_svalues
,
921 const region_model
*model
) = 0;
923 virtual logger
*get_logger () = 0;
925 /* Hook for clients to be notified when the condition
926 "LHS OP RHS" is added to the region model.
927 This exists so that state machines can detect tests on edges,
928 and use them to trigger sm-state transitions (e.g. transitions due
929 to ptrs becoming known to be NULL or non-NULL, rather than just
931 virtual void on_condition (const svalue
*lhs
,
933 const svalue
*rhs
) = 0;
935 /* Hook for clients to be notified when the condition that
936 SVAL is within RANGES is added to the region model.
937 Similar to on_condition, but for use when handling switch statements.
938 RANGES is non-empty. */
939 virtual void on_bounded_ranges (const svalue
&sval
,
940 const bounded_ranges
&ranges
) = 0;
942 /* Hooks for clients to be notified when an unknown change happens
943 to SVAL (in response to a call to an unknown function). */
944 virtual void on_unknown_change (const svalue
*sval
, bool is_mutable
) = 0;
946 /* Hooks for clients to be notified when a phi node is handled,
947 where RHS is the pertinent argument. */
948 virtual void on_phi (const gphi
*phi
, tree rhs
) = 0;
950 /* Hooks for clients to be notified when the region model doesn't
951 know how to handle the tree code of T at LOC. */
952 virtual void on_unexpected_tree_code (tree t
,
953 const dump_location_t
&loc
) = 0;
955 /* Hook for clients to be notified when a function_decl escapes. */
956 virtual void on_escaped_function (tree fndecl
) = 0;
958 virtual uncertainty_t
*get_uncertainty () = 0;
960 /* Hook for clients to purge state involving SVAL. */
961 virtual void purge_state_involving (const svalue
*sval
) = 0;
963 /* Hook for clients to split state with a non-standard path.
964 Take ownership of INFO. */
965 virtual void bifurcate (custom_edge_info
*info
) = 0;
967 /* Hook for clients to terminate the standard path. */
968 virtual void terminate_path () = 0;
970 virtual const extrinsic_state
*get_ext_state () const = 0;
972 /* Hook for clients to access the "malloc" state machine in
973 any underlying program_state. */
974 virtual bool get_malloc_map (sm_state_map
**out_smap
,
975 const state_machine
**out_sm
,
976 unsigned *out_sm_idx
) = 0;
977 /* Likewise for the "taint" state machine. */
978 virtual bool get_taint_map (sm_state_map
**out_smap
,
979 const state_machine
**out_sm
,
980 unsigned *out_sm_idx
) = 0;
982 /* Get the current statement, if any. */
983 virtual const gimple
*get_stmt () const = 0;
986 /* A "do nothing" subclass of region_model_context. */
988 class noop_region_model_context
: public region_model_context
991 bool warn (pending_diagnostic
*) override
{ return false; }
992 void add_note (pending_note
*pn
) override
;
993 void on_svalue_leak (const svalue
*) override
{}
994 void on_liveness_change (const svalue_set
&,
995 const region_model
*) override
{}
996 logger
*get_logger () override
{ return NULL
; }
997 void on_condition (const svalue
*lhs ATTRIBUTE_UNUSED
,
998 enum tree_code op ATTRIBUTE_UNUSED
,
999 const svalue
*rhs ATTRIBUTE_UNUSED
) override
1002 void on_bounded_ranges (const svalue
&,
1003 const bounded_ranges
&) override
1006 void on_unknown_change (const svalue
*sval ATTRIBUTE_UNUSED
,
1007 bool is_mutable ATTRIBUTE_UNUSED
) override
1010 void on_phi (const gphi
*phi ATTRIBUTE_UNUSED
,
1011 tree rhs ATTRIBUTE_UNUSED
) override
1014 void on_unexpected_tree_code (tree
, const dump_location_t
&) override
{}
1016 void on_escaped_function (tree
) override
{}
1018 uncertainty_t
*get_uncertainty () override
{ return NULL
; }
1020 void purge_state_involving (const svalue
*sval ATTRIBUTE_UNUSED
) override
{}
1022 void bifurcate (custom_edge_info
*info
) override
;
1023 void terminate_path () override
;
1025 const extrinsic_state
*get_ext_state () const override
{ return NULL
; }
1027 bool get_malloc_map (sm_state_map
**,
1028 const state_machine
**,
1029 unsigned *) override
1033 bool get_taint_map (sm_state_map
**,
1034 const state_machine
**,
1035 unsigned *) override
1040 const gimple
*get_stmt () const override
{ return NULL
; }
1043 /* A subclass of region_model_context for determining if operations fail
1044 e.g. "can we generate a region for the lvalue of EXPR?". */
1046 class tentative_region_model_context
: public noop_region_model_context
1049 tentative_region_model_context () : m_num_unexpected_codes (0) {}
1051 void on_unexpected_tree_code (tree
, const dump_location_t
&)
1054 m_num_unexpected_codes
++;
1057 bool had_errors_p () const { return m_num_unexpected_codes
> 0; }
1060 int m_num_unexpected_codes
;
1063 /* Subclass of region_model_context that wraps another context, allowing
1064 for extra code to be added to the various hooks. */
1066 class region_model_context_decorator
: public region_model_context
1069 bool warn (pending_diagnostic
*d
) override
1071 return m_inner
->warn (d
);
1074 void add_note (pending_note
*pn
) override
1076 m_inner
->add_note (pn
);
1079 void on_svalue_leak (const svalue
*sval
) override
1081 m_inner
->on_svalue_leak (sval
);
1084 void on_liveness_change (const svalue_set
&live_svalues
,
1085 const region_model
*model
) override
1087 m_inner
->on_liveness_change (live_svalues
, model
);
1090 logger
*get_logger () override
1092 return m_inner
->get_logger ();
1095 void on_condition (const svalue
*lhs
,
1097 const svalue
*rhs
) override
1099 m_inner
->on_condition (lhs
, op
, rhs
);
1102 void on_bounded_ranges (const svalue
&sval
,
1103 const bounded_ranges
&ranges
) override
1105 m_inner
->on_bounded_ranges (sval
, ranges
);
1108 void on_unknown_change (const svalue
*sval
, bool is_mutable
) override
1110 m_inner
->on_unknown_change (sval
, is_mutable
);
1113 void on_phi (const gphi
*phi
, tree rhs
) override
1115 m_inner
->on_phi (phi
, rhs
);
1118 void on_unexpected_tree_code (tree t
,
1119 const dump_location_t
&loc
) override
1121 m_inner
->on_unexpected_tree_code (t
, loc
);
1124 void on_escaped_function (tree fndecl
) override
1126 m_inner
->on_escaped_function (fndecl
);
1129 uncertainty_t
*get_uncertainty () override
1131 return m_inner
->get_uncertainty ();
1134 void purge_state_involving (const svalue
*sval
) override
1136 m_inner
->purge_state_involving (sval
);
1139 void bifurcate (custom_edge_info
*info
) override
1141 m_inner
->bifurcate (info
);
1144 void terminate_path () override
1146 m_inner
->terminate_path ();
1149 const extrinsic_state
*get_ext_state () const override
1151 return m_inner
->get_ext_state ();
1154 bool get_malloc_map (sm_state_map
**out_smap
,
1155 const state_machine
**out_sm
,
1156 unsigned *out_sm_idx
) override
1158 return m_inner
->get_malloc_map (out_smap
, out_sm
, out_sm_idx
);
1161 bool get_taint_map (sm_state_map
**out_smap
,
1162 const state_machine
**out_sm
,
1163 unsigned *out_sm_idx
) override
1165 return m_inner
->get_taint_map (out_smap
, out_sm
, out_sm_idx
);
1168 const gimple
*get_stmt () const override
1170 return m_inner
->get_stmt ();
1174 region_model_context_decorator (region_model_context
*inner
)
1177 gcc_assert (m_inner
);
1180 region_model_context
*m_inner
;
1183 /* Subclass of region_model_context_decorator that adds a note
1184 when saving diagnostics. */
1186 class note_adding_context
: public region_model_context_decorator
1189 bool warn (pending_diagnostic
*d
) override
1191 if (m_inner
->warn (d
))
1193 add_note (make_note ());
1200 /* Hook to make the new note. */
1201 virtual pending_note
*make_note () = 0;
1204 note_adding_context (region_model_context
*inner
)
1205 : region_model_context_decorator (inner
)
1210 /* A bundle of data for use when attempting to merge two region_model
1211 instances to make a third. */
1215 model_merger (const region_model
*model_a
,
1216 const region_model
*model_b
,
1217 const program_point
&point
,
1218 region_model
*merged_model
,
1219 const extrinsic_state
*ext_state
,
1220 const program_state
*state_a
,
1221 const program_state
*state_b
)
1222 : m_model_a (model_a
), m_model_b (model_b
),
1224 m_merged_model (merged_model
),
1225 m_ext_state (ext_state
),
1226 m_state_a (state_a
), m_state_b (state_b
)
1230 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
1231 void dump (FILE *fp
, bool simple
) const;
1232 void dump (bool simple
) const;
1234 region_model_manager
*get_manager () const
1236 return m_model_a
->get_manager ();
1239 bool mergeable_svalue_p (const svalue
*) const;
1241 const region_model
*m_model_a
;
1242 const region_model
*m_model_b
;
1243 const program_point
&m_point
;
1244 region_model
*m_merged_model
;
1246 const extrinsic_state
*m_ext_state
;
1247 const program_state
*m_state_a
;
1248 const program_state
*m_state_b
;
1251 /* A record that can (optionally) be written out when
1252 region_model::add_constraint fails. */
1254 class rejected_constraint
1257 virtual ~rejected_constraint () {}
1258 virtual void dump_to_pp (pretty_printer
*pp
) const = 0;
1260 const region_model
&get_model () const { return m_model
; }
1263 rejected_constraint (const region_model
&model
)
1267 region_model m_model
;
1270 class rejected_op_constraint
: public rejected_constraint
1273 rejected_op_constraint (const region_model
&model
,
1274 tree lhs
, enum tree_code op
, tree rhs
)
1275 : rejected_constraint (model
),
1276 m_lhs (lhs
), m_op (op
), m_rhs (rhs
)
1279 void dump_to_pp (pretty_printer
*pp
) const final override
;
1282 enum tree_code m_op
;
1286 class rejected_ranges_constraint
: public rejected_constraint
1289 rejected_ranges_constraint (const region_model
&model
,
1290 tree expr
, const bounded_ranges
*ranges
)
1291 : rejected_constraint (model
),
1292 m_expr (expr
), m_ranges (ranges
)
1295 void dump_to_pp (pretty_printer
*pp
) const final override
;
1299 const bounded_ranges
*m_ranges
;
1302 /* A bundle of state. */
1307 engine (const supergraph
*sg
= NULL
, logger
*logger
= NULL
);
1308 const supergraph
*get_supergraph () { return m_sg
; }
1309 region_model_manager
*get_model_manager () { return &m_mgr
; }
1311 void log_stats (logger
*logger
) const;
1314 const supergraph
*m_sg
;
1315 region_model_manager m_mgr
;
1320 extern void debug (const region_model
&rmodel
);
1326 namespace selftest
{
1328 using namespace ::selftest
;
1330 /* An implementation of region_model_context for use in selftests, which
1331 stores any pending_diagnostic instances passed to it. */
1333 class test_region_model_context
: public noop_region_model_context
1336 bool warn (pending_diagnostic
*d
) final override
1338 m_diagnostics
.safe_push (d
);
1342 unsigned get_num_diagnostics () const { return m_diagnostics
.length (); }
1344 void on_unexpected_tree_code (tree t
, const dump_location_t
&)
1347 internal_error ("unhandled tree code: %qs",
1348 get_tree_code_name (TREE_CODE (t
)));
1352 /* Implicitly delete any diagnostics in the dtor. */
1353 auto_delete_vec
<pending_diagnostic
> m_diagnostics
;
1356 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1357 Verify that MODEL remains satisfiable. */
1359 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1360 SELFTEST_BEGIN_STMT \
1361 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1362 ASSERT_TRUE (sat); \
1365 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1366 Verify that the result is not satisfiable. */
1368 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1369 SELFTEST_BEGIN_STMT \
1370 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1371 ASSERT_FALSE (sat); \
1374 /* Implementation detail of the ASSERT_CONDITION_* macros. */
1376 void assert_condition (const location
&loc
,
1377 region_model
&model
,
1378 const svalue
*lhs
, tree_code op
, const svalue
*rhs
,
1381 void assert_condition (const location
&loc
,
1382 region_model
&model
,
1383 tree lhs
, tree_code op
, tree rhs
,
1386 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1389 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1390 SELFTEST_BEGIN_STMT \
1391 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1392 tristate (tristate::TS_TRUE)); \
1395 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1398 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1399 SELFTEST_BEGIN_STMT \
1400 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1401 tristate (tristate::TS_FALSE)); \
1404 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1407 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1408 SELFTEST_BEGIN_STMT \
1409 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1410 tristate (tristate::TS_UNKNOWN)); \
1413 } /* end of namespace selftest. */
1415 #endif /* #if CHECKING_P */
1419 #endif /* GCC_ANALYZER_REGION_MODEL_H */