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
*) {}
228 virtual void visit_region (const region
*) {}
235 /* A class responsible for owning and consolidating region and svalue
237 region and svalue instances are immutable as far as clients are
238 concerned, so they are provided as "const" ptrs. */
240 class region_model_manager
243 region_model_manager (logger
*logger
= NULL
);
244 ~region_model_manager ();
246 /* svalue consolidation. */
247 const svalue
*get_or_create_constant_svalue (tree cst_expr
);
248 const svalue
*get_or_create_int_cst (tree type
, poly_int64
);
249 const svalue
*get_or_create_unknown_svalue (tree type
);
250 const svalue
*get_or_create_setjmp_svalue (const setjmp_record
&r
,
252 const svalue
*get_or_create_poisoned_svalue (enum poison_kind kind
,
254 const svalue
*get_or_create_initial_value (const region
*reg
);
255 const svalue
*get_ptr_svalue (tree ptr_type
, const region
*pointee
);
256 const svalue
*get_or_create_unaryop (tree type
, enum tree_code op
,
258 const svalue
*get_or_create_cast (tree type
, const svalue
*arg
);
259 const svalue
*get_or_create_binop (tree type
,
261 const svalue
*arg0
, const svalue
*arg1
);
262 const svalue
*get_or_create_sub_svalue (tree type
,
263 const svalue
*parent_svalue
,
264 const region
*subregion
);
265 const svalue
*get_or_create_repeated_svalue (tree type
,
266 const svalue
*outer_size
,
267 const svalue
*inner_svalue
);
268 const svalue
*get_or_create_bits_within (tree type
,
269 const bit_range
&bits
,
270 const svalue
*inner_svalue
);
271 const svalue
*get_or_create_unmergeable (const svalue
*arg
);
272 const svalue
*get_or_create_widening_svalue (tree type
,
273 const program_point
&point
,
274 const svalue
*base_svalue
,
275 const svalue
*iter_svalue
);
276 const svalue
*get_or_create_compound_svalue (tree type
,
277 const binding_map
&map
);
278 const svalue
*get_or_create_conjured_svalue (tree type
, const gimple
*stmt
,
279 const region
*id_reg
);
281 get_or_create_asm_output_svalue (tree type
,
282 const gasm
*asm_stmt
,
284 const vec
<const svalue
*> &inputs
);
286 const svalue
*maybe_get_char_from_string_cst (tree string_cst
,
287 tree byte_offset_cst
);
289 /* Dynamically-allocated svalue instances.
290 The number of these within the analysis can grow arbitrarily.
291 They are still owned by the manager. */
292 const svalue
*create_unique_svalue (tree type
);
294 /* region consolidation. */
295 const stack_region
* get_stack_region () const { return &m_stack_region
; }
296 const heap_region
*get_heap_region () const { return &m_heap_region
; }
297 const code_region
*get_code_region () const { return &m_code_region
; }
298 const globals_region
*get_globals_region () const
300 return &m_globals_region
;
302 const function_region
*get_region_for_fndecl (tree fndecl
);
303 const label_region
*get_region_for_label (tree label
);
304 const decl_region
*get_region_for_global (tree expr
);
305 const region
*get_field_region (const region
*parent
, tree field
);
306 const region
*get_element_region (const region
*parent
,
308 const svalue
*index
);
309 const region
*get_offset_region (const region
*parent
,
311 const svalue
*byte_offset
);
312 const region
*get_sized_region (const region
*parent
,
314 const svalue
*byte_size_sval
);
315 const region
*get_cast_region (const region
*original_region
,
317 const frame_region
*get_frame_region (const frame_region
*calling_frame
,
319 const region
*get_symbolic_region (const svalue
*sval
);
320 const string_region
*get_region_for_string (tree string_cst
);
321 const region
*get_bit_range (const region
*parent
, tree type
,
322 const bit_range
&bits
);
325 get_region_for_unexpected_tree_code (region_model_context
*ctxt
,
327 const dump_location_t
&loc
);
329 unsigned alloc_region_id () { return m_next_region_id
++; }
331 store_manager
*get_store_manager () { return &m_store_mgr
; }
332 bounded_ranges_manager
*get_range_manager () const { return m_range_mgr
; }
334 /* Dynamically-allocated region instances.
335 The number of these within the analysis can grow arbitrarily.
336 They are still owned by the manager. */
337 const region
*create_region_for_heap_alloc ();
338 const region
*create_region_for_alloca (const frame_region
*frame
);
340 void log_stats (logger
*logger
, bool show_objs
) const;
342 void begin_checking_feasibility (void) { m_checking_feasibility
= true; }
343 void end_checking_feasibility (void) { m_checking_feasibility
= false; }
345 logger
*get_logger () const { return m_logger
; }
348 bool too_complex_p (const complexity
&c
) const;
349 bool reject_if_too_complex (svalue
*sval
);
351 const svalue
*maybe_fold_unaryop (tree type
, enum tree_code op
,
353 const svalue
*maybe_fold_binop (tree type
, enum tree_code op
,
354 const svalue
*arg0
, const svalue
*arg1
);
355 const svalue
*maybe_fold_sub_svalue (tree type
,
356 const svalue
*parent_svalue
,
357 const region
*subregion
);
358 const svalue
*maybe_fold_repeated_svalue (tree type
,
359 const svalue
*outer_size
,
360 const svalue
*inner_svalue
);
361 const svalue
*maybe_fold_bits_within_svalue (tree type
,
362 const bit_range
&bits
,
363 const svalue
*inner_svalue
);
364 const svalue
*maybe_undo_optimize_bit_field_compare (tree type
,
365 const compound_svalue
*compound_sval
,
366 tree cst
, const svalue
*arg1
);
367 const svalue
*maybe_fold_asm_output_svalue (tree type
,
368 const vec
<const svalue
*> &inputs
);
372 unsigned m_next_region_id
;
373 root_region m_root_region
;
374 stack_region m_stack_region
;
375 heap_region m_heap_region
;
377 /* svalue consolidation. */
378 typedef hash_map
<tree
, constant_svalue
*> constants_map_t
;
379 constants_map_t m_constants_map
;
381 typedef hash_map
<tree
, unknown_svalue
*> unknowns_map_t
;
382 unknowns_map_t m_unknowns_map
;
383 const unknown_svalue
*m_unknown_NULL
;
385 typedef hash_map
<poisoned_svalue::key_t
,
386 poisoned_svalue
*> poisoned_values_map_t
;
387 poisoned_values_map_t m_poisoned_values_map
;
389 typedef hash_map
<setjmp_svalue::key_t
,
390 setjmp_svalue
*> setjmp_values_map_t
;
391 setjmp_values_map_t m_setjmp_values_map
;
393 typedef hash_map
<const region
*, initial_svalue
*> initial_values_map_t
;
394 initial_values_map_t m_initial_values_map
;
396 typedef hash_map
<region_svalue::key_t
, region_svalue
*> pointer_values_map_t
;
397 pointer_values_map_t m_pointer_values_map
;
399 typedef hash_map
<unaryop_svalue::key_t
,
400 unaryop_svalue
*> unaryop_values_map_t
;
401 unaryop_values_map_t m_unaryop_values_map
;
403 typedef hash_map
<binop_svalue::key_t
, binop_svalue
*> binop_values_map_t
;
404 binop_values_map_t m_binop_values_map
;
406 typedef hash_map
<sub_svalue::key_t
, sub_svalue
*> sub_values_map_t
;
407 sub_values_map_t m_sub_values_map
;
409 typedef hash_map
<repeated_svalue::key_t
,
410 repeated_svalue
*> repeated_values_map_t
;
411 repeated_values_map_t m_repeated_values_map
;
413 typedef hash_map
<bits_within_svalue::key_t
,
414 bits_within_svalue
*> bits_within_values_map_t
;
415 bits_within_values_map_t m_bits_within_values_map
;
417 typedef hash_map
<const svalue
*,
418 unmergeable_svalue
*> unmergeable_values_map_t
;
419 unmergeable_values_map_t m_unmergeable_values_map
;
421 typedef hash_map
<widening_svalue::key_t
,
423 widening_svalue::key_t::hash_map_traits*/
>
424 widening_values_map_t
;
425 widening_values_map_t m_widening_values_map
;
427 typedef hash_map
<compound_svalue::key_t
,
428 compound_svalue
*> compound_values_map_t
;
429 compound_values_map_t m_compound_values_map
;
431 typedef hash_map
<conjured_svalue::key_t
,
432 conjured_svalue
*> conjured_values_map_t
;
433 conjured_values_map_t m_conjured_values_map
;
435 typedef hash_map
<asm_output_svalue::key_t
,
436 asm_output_svalue
*> asm_output_values_map_t
;
437 asm_output_values_map_t m_asm_output_values_map
;
439 bool m_checking_feasibility
;
441 /* "Dynamically-allocated" svalue instances.
442 The number of these within the analysis can grow arbitrarily.
443 They are still owned by the manager. */
444 auto_delete_vec
<svalue
> m_managed_dynamic_svalues
;
446 /* Maximum complexity of svalues that weren't rejected. */
447 complexity m_max_complexity
;
449 /* region consolidation. */
451 code_region m_code_region
;
452 typedef hash_map
<tree
, function_region
*> fndecls_map_t
;
453 typedef fndecls_map_t::iterator fndecls_iterator_t
;
454 fndecls_map_t m_fndecls_map
;
456 typedef hash_map
<tree
, label_region
*> labels_map_t
;
457 typedef labels_map_t::iterator labels_iterator_t
;
458 labels_map_t m_labels_map
;
460 globals_region m_globals_region
;
461 typedef hash_map
<tree
, decl_region
*> globals_map_t
;
462 typedef globals_map_t::iterator globals_iterator_t
;
463 globals_map_t m_globals_map
;
465 consolidation_map
<field_region
> m_field_regions
;
466 consolidation_map
<element_region
> m_element_regions
;
467 consolidation_map
<offset_region
> m_offset_regions
;
468 consolidation_map
<sized_region
> m_sized_regions
;
469 consolidation_map
<cast_region
> m_cast_regions
;
470 consolidation_map
<frame_region
> m_frame_regions
;
471 consolidation_map
<symbolic_region
> m_symbolic_regions
;
473 typedef hash_map
<tree
, string_region
*> string_map_t
;
474 string_map_t m_string_map
;
476 consolidation_map
<bit_range_region
> m_bit_range_regions
;
478 store_manager m_store_mgr
;
480 bounded_ranges_manager
*m_range_mgr
;
482 /* "Dynamically-allocated" region instances.
483 The number of these within the analysis can grow arbitrarily.
484 They are still owned by the manager. */
485 auto_delete_vec
<region
> m_managed_dynamic_regions
;
488 struct append_ssa_names_cb_data
;
490 /* Helper class for handling calls to functions with known behavior.
491 Implemented in region-model-impl-calls.c. */
496 call_details (const gcall
*call
, region_model
*model
,
497 region_model_context
*ctxt
);
499 region_model_context
*get_ctxt () const { return m_ctxt
; }
500 uncertainty_t
*get_uncertainty () const;
501 tree
get_lhs_type () const { return m_lhs_type
; }
502 const region
*get_lhs_region () const { return m_lhs_region
; }
504 bool maybe_set_lhs (const svalue
*result
) const;
506 unsigned num_args () const;
508 const gcall
*get_call_stmt () const { return m_call
; }
510 tree
get_arg_tree (unsigned idx
) const;
511 tree
get_arg_type (unsigned idx
) const;
512 const svalue
*get_arg_svalue (unsigned idx
) const;
513 const char *get_arg_string_literal (unsigned idx
) const;
515 tree
get_fndecl_for_call () const;
517 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
518 void dump (bool simple
) const;
520 const svalue
*get_or_create_conjured_svalue (const region
*) const;
524 region_model
*m_model
;
525 region_model_context
*m_ctxt
;
527 const region
*m_lhs_region
;
530 /* A region_model encapsulates a representation of the state of memory, with
531 a tree of regions, along with their associated values.
532 The representation is graph-like because values can be pointers to
535 - a constraint_manager, capturing relationships between the values, and
536 - dynamic extents, mapping dynamically-allocated regions to svalues (their
542 typedef region_to_value_map dynamic_extents_t
;
544 region_model (region_model_manager
*mgr
);
545 region_model (const region_model
&other
);
547 region_model
&operator= (const region_model
&other
);
549 bool operator== (const region_model
&other
) const;
550 bool operator!= (const region_model
&other
) const
552 return !(*this == other
);
555 hashval_t
hash () const;
557 void print (pretty_printer
*pp
) const;
559 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
560 void dump (FILE *fp
, bool simple
, bool multiline
) const;
561 void dump (bool simple
) const;
565 void validate () const;
567 void canonicalize ();
568 bool canonicalized_p () const;
571 on_stmt_pre (const gimple
*stmt
,
572 bool *out_terminate_path
,
573 bool *out_unknown_side_effects
,
574 region_model_context
*ctxt
);
576 void on_assignment (const gassign
*stmt
, region_model_context
*ctxt
);
577 const svalue
*get_gassign_result (const gassign
*assign
,
578 region_model_context
*ctxt
);
579 void on_asm_stmt (const gasm
*asm_stmt
, region_model_context
*ctxt
);
580 bool on_call_pre (const gcall
*stmt
, region_model_context
*ctxt
,
581 bool *out_terminate_path
);
582 void on_call_post (const gcall
*stmt
,
583 bool unknown_side_effects
,
584 region_model_context
*ctxt
);
586 void purge_state_involving (const svalue
*sval
, region_model_context
*ctxt
);
588 /* Specific handling for on_call_pre. */
589 void impl_call_alloca (const call_details
&cd
);
590 void impl_call_analyzer_describe (const gcall
*call
,
591 region_model_context
*ctxt
);
592 void impl_call_analyzer_dump_capacity (const gcall
*call
,
593 region_model_context
*ctxt
);
594 void impl_call_analyzer_dump_escaped (const gcall
*call
);
595 void impl_call_analyzer_eval (const gcall
*call
,
596 region_model_context
*ctxt
);
597 void impl_call_builtin_expect (const call_details
&cd
);
598 void impl_call_calloc (const call_details
&cd
);
599 bool impl_call_error (const call_details
&cd
, unsigned min_args
,
600 bool *out_terminate_path
);
601 void impl_call_fgets (const call_details
&cd
);
602 void impl_call_fread (const call_details
&cd
);
603 void impl_call_free (const call_details
&cd
);
604 void impl_call_malloc (const call_details
&cd
);
605 void impl_call_memcpy (const call_details
&cd
);
606 void impl_call_memset (const call_details
&cd
);
607 void impl_call_realloc (const call_details
&cd
);
608 void impl_call_strchr (const call_details
&cd
);
609 void impl_call_strcpy (const call_details
&cd
);
610 void impl_call_strlen (const call_details
&cd
);
611 void impl_call_operator_new (const call_details
&cd
);
612 void impl_call_operator_delete (const call_details
&cd
);
613 void impl_deallocation_call (const call_details
&cd
);
615 void handle_unrecognized_call (const gcall
*call
,
616 region_model_context
*ctxt
);
617 void get_reachable_svalues (svalue_set
*out
,
618 const svalue
*extra_sval
,
619 const uncertainty_t
*uncertainty
);
621 void on_return (const greturn
*stmt
, region_model_context
*ctxt
);
622 void on_setjmp (const gcall
*stmt
, const exploded_node
*enode
,
623 region_model_context
*ctxt
);
624 void on_longjmp (const gcall
*longjmp_call
, const gcall
*setjmp_call
,
625 int setjmp_stack_depth
, region_model_context
*ctxt
);
627 void update_for_phis (const supernode
*snode
,
628 const cfg_superedge
*last_cfg_superedge
,
629 region_model_context
*ctxt
);
631 void handle_phi (const gphi
*phi
, tree lhs
, tree rhs
,
632 const region_model
&old_state
,
633 region_model_context
*ctxt
);
635 bool maybe_update_for_edge (const superedge
&edge
,
636 const gimple
*last_stmt
,
637 region_model_context
*ctxt
,
638 rejected_constraint
**out
);
640 void update_for_gcall (const gcall
*call_stmt
,
641 region_model_context
*ctxt
,
642 function
*callee
= NULL
);
644 void update_for_return_gcall (const gcall
*call_stmt
,
645 region_model_context
*ctxt
);
647 const region
*push_frame (function
*fun
, const vec
<const svalue
*> *arg_sids
,
648 region_model_context
*ctxt
);
649 const frame_region
*get_current_frame () const { return m_current_frame
; }
650 function
* get_current_function () const;
651 void pop_frame (const region
*result_dst
,
652 const svalue
**out_result
,
653 region_model_context
*ctxt
);
654 int get_stack_depth () const;
655 const frame_region
*get_frame_at_index (int index
) const;
657 const region
*get_lvalue (path_var pv
, region_model_context
*ctxt
) const;
658 const region
*get_lvalue (tree expr
, region_model_context
*ctxt
) const;
659 const svalue
*get_rvalue (path_var pv
, region_model_context
*ctxt
) const;
660 const svalue
*get_rvalue (tree expr
, region_model_context
*ctxt
) const;
662 const region
*deref_rvalue (const svalue
*ptr_sval
, tree ptr_tree
,
663 region_model_context
*ctxt
) const;
665 const svalue
*get_rvalue_for_bits (tree type
,
667 const bit_range
&bits
,
668 region_model_context
*ctxt
) const;
670 void set_value (const region
*lhs_reg
, const svalue
*rhs_sval
,
671 region_model_context
*ctxt
);
672 void set_value (tree lhs
, tree rhs
, region_model_context
*ctxt
);
673 void clobber_region (const region
*reg
);
674 void purge_region (const region
*reg
);
675 void fill_region (const region
*reg
, const svalue
*sval
);
676 void zero_fill_region (const region
*reg
);
677 void mark_region_as_unknown (const region
*reg
, uncertainty_t
*uncertainty
);
679 void copy_region (const region
*dst_reg
, const region
*src_reg
,
680 region_model_context
*ctxt
);
681 tristate
eval_condition (const svalue
*lhs
,
683 const svalue
*rhs
) const;
684 tristate
eval_condition_without_cm (const svalue
*lhs
,
686 const svalue
*rhs
) const;
687 tristate
compare_initial_and_pointer (const initial_svalue
*init
,
688 const region_svalue
*ptr
) const;
689 tristate
eval_condition (tree lhs
,
692 region_model_context
*ctxt
);
693 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
694 region_model_context
*ctxt
);
695 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
696 region_model_context
*ctxt
,
697 rejected_constraint
**out
);
699 const region
*create_region_for_heap_alloc (const svalue
*size_in_bytes
,
700 region_model_context
*ctxt
);
701 const region
*create_region_for_alloca (const svalue
*size_in_bytes
,
702 region_model_context
*ctxt
);
704 tree
get_representative_tree (const svalue
*sval
) const;
706 get_representative_path_var (const svalue
*sval
,
707 svalue_set
*visited
) const;
709 get_representative_path_var (const region
*reg
,
710 svalue_set
*visited
) const;
713 constraint_manager
*get_constraints ()
715 return m_constraints
;
718 store
*get_store () { return &m_store
; }
719 const store
*get_store () const { return &m_store
; }
721 const dynamic_extents_t
&
722 get_dynamic_extents () const
724 return m_dynamic_extents
;
726 const svalue
*get_dynamic_extents (const region
*reg
) const;
727 void set_dynamic_extents (const region
*reg
,
728 const svalue
*size_in_bytes
,
729 region_model_context
*ctxt
);
730 void unset_dynamic_extents (const region
*reg
);
732 region_model_manager
*get_manager () const { return m_mgr
; }
733 bounded_ranges_manager
*get_range_manager () const
735 return m_mgr
->get_range_manager ();
738 void unbind_region_and_descendents (const region
*reg
,
739 enum poison_kind pkind
);
741 bool can_merge_with_p (const region_model
&other_model
,
742 const program_point
&point
,
743 region_model
*out_model
,
744 const extrinsic_state
*ext_state
= NULL
,
745 const program_state
*state_a
= NULL
,
746 const program_state
*state_b
= NULL
) const;
748 tree
get_fndecl_for_call (const gcall
*call
,
749 region_model_context
*ctxt
);
751 void get_ssa_name_regions_for_current_frame
752 (auto_vec
<const decl_region
*> *out
) const;
753 static void append_ssa_names_cb (const region
*base_reg
,
754 struct append_ssa_names_cb_data
*data
);
756 const svalue
*get_store_value (const region
*reg
,
757 region_model_context
*ctxt
) const;
759 bool region_exists_p (const region
*reg
) const;
761 void loop_replay_fixup (const region_model
*dst_state
);
763 const svalue
*get_capacity (const region
*reg
) const;
765 /* Implemented in sm-malloc.cc */
766 void on_realloc_with_move (const call_details
&cd
,
767 const svalue
*old_ptr_sval
,
768 const svalue
*new_ptr_sval
);
771 const region
*get_lvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
772 const svalue
*get_rvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
775 get_representative_path_var_1 (const svalue
*sval
,
776 svalue_set
*visited
) const;
778 get_representative_path_var_1 (const region
*reg
,
779 svalue_set
*visited
) const;
781 bool add_constraint (const svalue
*lhs
,
784 region_model_context
*ctxt
);
785 bool add_constraints_from_binop (const svalue
*outer_lhs
,
786 enum tree_code outer_op
,
787 const svalue
*outer_rhs
,
789 region_model_context
*ctxt
);
791 void update_for_call_superedge (const call_superedge
&call_edge
,
792 region_model_context
*ctxt
);
793 void update_for_return_superedge (const return_superedge
&return_edge
,
794 region_model_context
*ctxt
);
795 void update_for_call_summary (const callgraph_superedge
&cg_sedge
,
796 region_model_context
*ctxt
);
797 bool apply_constraints_for_gcond (const cfg_superedge
&edge
,
798 const gcond
*cond_stmt
,
799 region_model_context
*ctxt
,
800 rejected_constraint
**out
);
801 bool apply_constraints_for_gswitch (const switch_cfg_superedge
&edge
,
802 const gswitch
*switch_stmt
,
803 region_model_context
*ctxt
,
804 rejected_constraint
**out
);
805 bool apply_constraints_for_exception (const gimple
*last_stmt
,
806 region_model_context
*ctxt
,
807 rejected_constraint
**out
);
809 int poison_any_pointers_to_descendents (const region
*reg
,
810 enum poison_kind pkind
);
812 void on_top_level_param (tree param
, region_model_context
*ctxt
);
814 bool called_from_main_p () const;
815 const svalue
*get_initial_value_for_global (const region
*reg
) const;
817 const svalue
*check_for_poison (const svalue
*sval
,
819 region_model_context
*ctxt
) const;
820 const region
* get_region_for_poisoned_expr (tree expr
) const;
822 void check_dynamic_size_for_taint (enum memory_space mem_space
,
823 const svalue
*size_in_bytes
,
824 region_model_context
*ctxt
) const;
826 void check_region_for_taint (const region
*reg
,
827 enum access_direction dir
,
828 region_model_context
*ctxt
) const;
830 void check_for_writable_region (const region
* dest_reg
,
831 region_model_context
*ctxt
) const;
832 void check_region_access (const region
*reg
,
833 enum access_direction dir
,
834 region_model_context
*ctxt
) const;
835 void check_region_for_write (const region
*dest_reg
,
836 region_model_context
*ctxt
) const;
837 void check_region_for_read (const region
*src_reg
,
838 region_model_context
*ctxt
) const;
840 void check_call_args (const call_details
&cd
) const;
842 /* Storing this here to avoid passing it around everywhere. */
843 region_model_manager
*const m_mgr
;
847 constraint_manager
*m_constraints
; // TODO: embed, rather than dynalloc?
849 const frame_region
*m_current_frame
;
851 /* Map from base region to size in bytes, for tracking the sizes of
852 dynamically-allocated regions.
853 This is part of the region_model rather than the region to allow for
854 memory regions to be resized (e.g. by realloc). */
855 dynamic_extents_t m_dynamic_extents
;
858 /* Some region_model activity could lead to warnings (e.g. attempts to use an
859 uninitialized value). This abstract base class encapsulates an interface
860 for the region model to use when emitting such warnings.
862 Having this as an abstract base class allows us to support the various
863 operations needed by program_state in the analyzer within region_model,
864 whilst keeping them somewhat modularized. */
866 class region_model_context
869 /* Hook for clients to store pending diagnostics.
870 Return true if the diagnostic was stored, or false if it was deleted. */
871 virtual bool warn (pending_diagnostic
*d
) = 0;
873 /* Hook for clients to be notified when an SVAL that was reachable
874 in a previous state is no longer live, so that clients can emit warnings
876 virtual void on_svalue_leak (const svalue
*sval
) = 0;
878 /* Hook for clients to be notified when the set of explicitly live
879 svalues changes, so that they can purge state relating to dead
881 virtual void on_liveness_change (const svalue_set
&live_svalues
,
882 const region_model
*model
) = 0;
884 virtual logger
*get_logger () = 0;
886 /* Hook for clients to be notified when the condition
887 "LHS OP RHS" is added to the region model.
888 This exists so that state machines can detect tests on edges,
889 and use them to trigger sm-state transitions (e.g. transitions due
890 to ptrs becoming known to be NULL or non-NULL, rather than just
892 virtual void on_condition (const svalue
*lhs
,
894 const svalue
*rhs
) = 0;
896 /* Hooks for clients to be notified when an unknown change happens
897 to SVAL (in response to a call to an unknown function). */
898 virtual void on_unknown_change (const svalue
*sval
, bool is_mutable
) = 0;
900 /* Hooks for clients to be notified when a phi node is handled,
901 where RHS is the pertinent argument. */
902 virtual void on_phi (const gphi
*phi
, tree rhs
) = 0;
904 /* Hooks for clients to be notified when the region model doesn't
905 know how to handle the tree code of T at LOC. */
906 virtual void on_unexpected_tree_code (tree t
,
907 const dump_location_t
&loc
) = 0;
909 /* Hook for clients to be notified when a function_decl escapes. */
910 virtual void on_escaped_function (tree fndecl
) = 0;
912 virtual uncertainty_t
*get_uncertainty () = 0;
914 /* Hook for clients to purge state involving SVAL. */
915 virtual void purge_state_involving (const svalue
*sval
) = 0;
917 /* Hook for clients to split state with a non-standard path.
918 Take ownership of INFO. */
919 virtual void bifurcate (custom_edge_info
*info
) = 0;
921 /* Hook for clients to terminate the standard path. */
922 virtual void terminate_path () = 0;
924 virtual const extrinsic_state
*get_ext_state () const = 0;
926 /* Hook for clients to access the "malloc" state machine in
927 any underlying program_state. */
928 virtual bool get_malloc_map (sm_state_map
**out_smap
,
929 const state_machine
**out_sm
,
930 unsigned *out_sm_idx
) = 0;
931 /* Likewise for the "taint" state machine. */
932 virtual bool get_taint_map (sm_state_map
**out_smap
,
933 const state_machine
**out_sm
,
934 unsigned *out_sm_idx
) = 0;
937 /* A "do nothing" subclass of region_model_context. */
939 class noop_region_model_context
: public region_model_context
942 bool warn (pending_diagnostic
*) OVERRIDE
{ return false; }
943 void on_svalue_leak (const svalue
*) OVERRIDE
{}
944 void on_liveness_change (const svalue_set
&,
945 const region_model
*) OVERRIDE
{}
946 logger
*get_logger () OVERRIDE
{ return NULL
; }
947 void on_condition (const svalue
*lhs ATTRIBUTE_UNUSED
,
948 enum tree_code op ATTRIBUTE_UNUSED
,
949 const svalue
*rhs ATTRIBUTE_UNUSED
) OVERRIDE
952 void on_unknown_change (const svalue
*sval ATTRIBUTE_UNUSED
,
953 bool is_mutable ATTRIBUTE_UNUSED
) OVERRIDE
956 void on_phi (const gphi
*phi ATTRIBUTE_UNUSED
,
957 tree rhs ATTRIBUTE_UNUSED
) OVERRIDE
960 void on_unexpected_tree_code (tree
, const dump_location_t
&) OVERRIDE
{}
962 void on_escaped_function (tree
) OVERRIDE
{}
964 uncertainty_t
*get_uncertainty () OVERRIDE
{ return NULL
; }
966 void purge_state_involving (const svalue
*sval ATTRIBUTE_UNUSED
) OVERRIDE
{}
968 void bifurcate (custom_edge_info
*info
) OVERRIDE
;
969 void terminate_path () OVERRIDE
;
971 const extrinsic_state
*get_ext_state () const OVERRIDE
{ return NULL
; }
973 bool get_malloc_map (sm_state_map
**,
974 const state_machine
**,
979 bool get_taint_map (sm_state_map
**,
980 const state_machine
**,
987 /* A subclass of region_model_context for determining if operations fail
988 e.g. "can we generate a region for the lvalue of EXPR?". */
990 class tentative_region_model_context
: public noop_region_model_context
993 tentative_region_model_context () : m_num_unexpected_codes (0) {}
995 void on_unexpected_tree_code (tree
, const dump_location_t
&)
998 m_num_unexpected_codes
++;
1001 bool had_errors_p () const { return m_num_unexpected_codes
> 0; }
1004 int m_num_unexpected_codes
;
1007 /* A bundle of data for use when attempting to merge two region_model
1008 instances to make a third. */
1012 model_merger (const region_model
*model_a
,
1013 const region_model
*model_b
,
1014 const program_point
&point
,
1015 region_model
*merged_model
,
1016 const extrinsic_state
*ext_state
,
1017 const program_state
*state_a
,
1018 const program_state
*state_b
)
1019 : m_model_a (model_a
), m_model_b (model_b
),
1021 m_merged_model (merged_model
),
1022 m_ext_state (ext_state
),
1023 m_state_a (state_a
), m_state_b (state_b
)
1027 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
1028 void dump (FILE *fp
, bool simple
) const;
1029 void dump (bool simple
) const;
1031 region_model_manager
*get_manager () const
1033 return m_model_a
->get_manager ();
1036 bool mergeable_svalue_p (const svalue
*) const;
1038 const region_model
*m_model_a
;
1039 const region_model
*m_model_b
;
1040 const program_point
&m_point
;
1041 region_model
*m_merged_model
;
1043 const extrinsic_state
*m_ext_state
;
1044 const program_state
*m_state_a
;
1045 const program_state
*m_state_b
;
1048 /* A record that can (optionally) be written out when
1049 region_model::add_constraint fails. */
1051 class rejected_constraint
1054 virtual ~rejected_constraint () {}
1055 virtual void dump_to_pp (pretty_printer
*pp
) const = 0;
1057 const region_model
&get_model () const { return m_model
; }
1060 rejected_constraint (const region_model
&model
)
1064 region_model m_model
;
1067 class rejected_op_constraint
: public rejected_constraint
1070 rejected_op_constraint (const region_model
&model
,
1071 tree lhs
, enum tree_code op
, tree rhs
)
1072 : rejected_constraint (model
),
1073 m_lhs (lhs
), m_op (op
), m_rhs (rhs
)
1076 void dump_to_pp (pretty_printer
*pp
) const FINAL OVERRIDE
;
1079 enum tree_code m_op
;
1083 class rejected_ranges_constraint
: public rejected_constraint
1086 rejected_ranges_constraint (const region_model
&model
,
1087 tree expr
, const bounded_ranges
*ranges
)
1088 : rejected_constraint (model
),
1089 m_expr (expr
), m_ranges (ranges
)
1092 void dump_to_pp (pretty_printer
*pp
) const FINAL OVERRIDE
;
1096 const bounded_ranges
*m_ranges
;
1099 /* A bundle of state. */
1104 engine (logger
*logger
= NULL
);
1105 region_model_manager
*get_model_manager () { return &m_mgr
; }
1107 void log_stats (logger
*logger
) const;
1110 region_model_manager m_mgr
;
1116 extern void debug (const region_model
&rmodel
);
1122 namespace selftest
{
1124 using namespace ::selftest
;
1126 /* An implementation of region_model_context for use in selftests, which
1127 stores any pending_diagnostic instances passed to it. */
1129 class test_region_model_context
: public noop_region_model_context
1132 bool warn (pending_diagnostic
*d
) FINAL OVERRIDE
1134 m_diagnostics
.safe_push (d
);
1138 unsigned get_num_diagnostics () const { return m_diagnostics
.length (); }
1140 void on_unexpected_tree_code (tree t
, const dump_location_t
&)
1143 internal_error ("unhandled tree code: %qs",
1144 get_tree_code_name (TREE_CODE (t
)));
1148 /* Implicitly delete any diagnostics in the dtor. */
1149 auto_delete_vec
<pending_diagnostic
> m_diagnostics
;
1152 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1153 Verify that MODEL remains satisfiable. */
1155 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1156 SELFTEST_BEGIN_STMT \
1157 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1158 ASSERT_TRUE (sat); \
1161 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1162 Verify that the result is not satisfiable. */
1164 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1165 SELFTEST_BEGIN_STMT \
1166 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1167 ASSERT_FALSE (sat); \
1170 /* Implementation detail of the ASSERT_CONDITION_* macros. */
1172 void assert_condition (const location
&loc
,
1173 region_model
&model
,
1174 const svalue
*lhs
, tree_code op
, const svalue
*rhs
,
1177 void assert_condition (const location
&loc
,
1178 region_model
&model
,
1179 tree lhs
, tree_code op
, tree rhs
,
1182 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1185 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1186 SELFTEST_BEGIN_STMT \
1187 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1188 tristate (tristate::TS_TRUE)); \
1191 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1194 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1195 SELFTEST_BEGIN_STMT \
1196 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1197 tristate (tristate::TS_FALSE)); \
1200 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1203 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1204 SELFTEST_BEGIN_STMT \
1205 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1206 tristate (tristate::TS_UNKNOWN)); \
1209 } /* end of namespace selftest. */
1211 #endif /* #if CHECKING_P */
1215 #endif /* GCC_ANALYZER_REGION_MODEL_H */