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 /* svalue consolidation. */
248 const svalue
*get_or_create_constant_svalue (tree cst_expr
);
249 const svalue
*get_or_create_int_cst (tree type
, poly_int64
);
250 const svalue
*get_or_create_unknown_svalue (tree type
);
251 const svalue
*get_or_create_setjmp_svalue (const setjmp_record
&r
,
253 const svalue
*get_or_create_poisoned_svalue (enum poison_kind kind
,
255 const svalue
*get_or_create_initial_value (const region
*reg
);
256 const svalue
*get_ptr_svalue (tree ptr_type
, const region
*pointee
);
257 const svalue
*get_or_create_unaryop (tree type
, enum tree_code op
,
259 const svalue
*get_or_create_cast (tree type
, const svalue
*arg
);
260 const svalue
*get_or_create_binop (tree type
,
262 const svalue
*arg0
, const svalue
*arg1
);
263 const svalue
*get_or_create_sub_svalue (tree type
,
264 const svalue
*parent_svalue
,
265 const region
*subregion
);
266 const svalue
*get_or_create_repeated_svalue (tree type
,
267 const svalue
*outer_size
,
268 const svalue
*inner_svalue
);
269 const svalue
*get_or_create_bits_within (tree type
,
270 const bit_range
&bits
,
271 const svalue
*inner_svalue
);
272 const svalue
*get_or_create_unmergeable (const svalue
*arg
);
273 const svalue
*get_or_create_widening_svalue (tree type
,
274 const program_point
&point
,
275 const svalue
*base_svalue
,
276 const svalue
*iter_svalue
);
277 const svalue
*get_or_create_compound_svalue (tree type
,
278 const binding_map
&map
);
279 const svalue
*get_or_create_conjured_svalue (tree type
, const gimple
*stmt
,
280 const region
*id_reg
);
282 get_or_create_asm_output_svalue (tree type
,
283 const gasm
*asm_stmt
,
285 const vec
<const svalue
*> &inputs
);
287 get_or_create_const_fn_result_svalue (tree type
,
289 const vec
<const svalue
*> &inputs
);
291 const svalue
*maybe_get_char_from_string_cst (tree string_cst
,
292 tree byte_offset_cst
);
294 /* Dynamically-allocated svalue instances.
295 The number of these within the analysis can grow arbitrarily.
296 They are still owned by the manager. */
297 const svalue
*create_unique_svalue (tree type
);
299 /* region consolidation. */
300 const stack_region
* get_stack_region () const { return &m_stack_region
; }
301 const heap_region
*get_heap_region () const { return &m_heap_region
; }
302 const code_region
*get_code_region () const { return &m_code_region
; }
303 const globals_region
*get_globals_region () const
305 return &m_globals_region
;
307 const function_region
*get_region_for_fndecl (tree fndecl
);
308 const label_region
*get_region_for_label (tree label
);
309 const decl_region
*get_region_for_global (tree expr
);
310 const region
*get_field_region (const region
*parent
, tree field
);
311 const region
*get_element_region (const region
*parent
,
313 const svalue
*index
);
314 const region
*get_offset_region (const region
*parent
,
316 const svalue
*byte_offset
);
317 const region
*get_sized_region (const region
*parent
,
319 const svalue
*byte_size_sval
);
320 const region
*get_cast_region (const region
*original_region
,
322 const frame_region
*get_frame_region (const frame_region
*calling_frame
,
324 const region
*get_symbolic_region (const svalue
*sval
);
325 const string_region
*get_region_for_string (tree string_cst
);
326 const region
*get_bit_range (const region
*parent
, tree type
,
327 const bit_range
&bits
);
330 get_region_for_unexpected_tree_code (region_model_context
*ctxt
,
332 const dump_location_t
&loc
);
334 unsigned alloc_region_id () { return m_next_region_id
++; }
336 store_manager
*get_store_manager () { return &m_store_mgr
; }
337 bounded_ranges_manager
*get_range_manager () const { return m_range_mgr
; }
339 /* Dynamically-allocated region instances.
340 The number of these within the analysis can grow arbitrarily.
341 They are still owned by the manager. */
342 const region
*create_region_for_heap_alloc ();
343 const region
*create_region_for_alloca (const frame_region
*frame
);
345 void log_stats (logger
*logger
, bool show_objs
) const;
347 void begin_checking_feasibility (void) { m_checking_feasibility
= true; }
348 void end_checking_feasibility (void) { m_checking_feasibility
= false; }
350 logger
*get_logger () const { return m_logger
; }
353 bool too_complex_p (const complexity
&c
) const;
354 bool reject_if_too_complex (svalue
*sval
);
356 const svalue
*maybe_fold_unaryop (tree type
, enum tree_code op
,
358 const svalue
*maybe_fold_binop (tree type
, enum tree_code op
,
359 const svalue
*arg0
, const svalue
*arg1
);
360 const svalue
*maybe_fold_sub_svalue (tree type
,
361 const svalue
*parent_svalue
,
362 const region
*subregion
);
363 const svalue
*maybe_fold_repeated_svalue (tree type
,
364 const svalue
*outer_size
,
365 const svalue
*inner_svalue
);
366 const svalue
*maybe_fold_bits_within_svalue (tree type
,
367 const bit_range
&bits
,
368 const svalue
*inner_svalue
);
369 const svalue
*maybe_undo_optimize_bit_field_compare (tree type
,
370 const compound_svalue
*compound_sval
,
371 tree cst
, const svalue
*arg1
);
372 const svalue
*maybe_fold_asm_output_svalue (tree type
,
373 const vec
<const svalue
*> &inputs
);
377 unsigned m_next_region_id
;
378 root_region m_root_region
;
379 stack_region m_stack_region
;
380 heap_region m_heap_region
;
382 /* svalue consolidation. */
383 typedef hash_map
<tree
, constant_svalue
*> constants_map_t
;
384 constants_map_t m_constants_map
;
386 typedef hash_map
<tree
, unknown_svalue
*> unknowns_map_t
;
387 unknowns_map_t m_unknowns_map
;
388 const unknown_svalue
*m_unknown_NULL
;
390 typedef hash_map
<poisoned_svalue::key_t
,
391 poisoned_svalue
*> poisoned_values_map_t
;
392 poisoned_values_map_t m_poisoned_values_map
;
394 typedef hash_map
<setjmp_svalue::key_t
,
395 setjmp_svalue
*> setjmp_values_map_t
;
396 setjmp_values_map_t m_setjmp_values_map
;
398 typedef hash_map
<const region
*, initial_svalue
*> initial_values_map_t
;
399 initial_values_map_t m_initial_values_map
;
401 typedef hash_map
<region_svalue::key_t
, region_svalue
*> pointer_values_map_t
;
402 pointer_values_map_t m_pointer_values_map
;
404 typedef hash_map
<unaryop_svalue::key_t
,
405 unaryop_svalue
*> unaryop_values_map_t
;
406 unaryop_values_map_t m_unaryop_values_map
;
408 typedef hash_map
<binop_svalue::key_t
, binop_svalue
*> binop_values_map_t
;
409 binop_values_map_t m_binop_values_map
;
411 typedef hash_map
<sub_svalue::key_t
, sub_svalue
*> sub_values_map_t
;
412 sub_values_map_t m_sub_values_map
;
414 typedef hash_map
<repeated_svalue::key_t
,
415 repeated_svalue
*> repeated_values_map_t
;
416 repeated_values_map_t m_repeated_values_map
;
418 typedef hash_map
<bits_within_svalue::key_t
,
419 bits_within_svalue
*> bits_within_values_map_t
;
420 bits_within_values_map_t m_bits_within_values_map
;
422 typedef hash_map
<const svalue
*,
423 unmergeable_svalue
*> unmergeable_values_map_t
;
424 unmergeable_values_map_t m_unmergeable_values_map
;
426 typedef hash_map
<widening_svalue::key_t
,
428 widening_svalue::key_t::hash_map_traits*/
>
429 widening_values_map_t
;
430 widening_values_map_t m_widening_values_map
;
432 typedef hash_map
<compound_svalue::key_t
,
433 compound_svalue
*> compound_values_map_t
;
434 compound_values_map_t m_compound_values_map
;
436 typedef hash_map
<conjured_svalue::key_t
,
437 conjured_svalue
*> conjured_values_map_t
;
438 conjured_values_map_t m_conjured_values_map
;
440 typedef hash_map
<asm_output_svalue::key_t
,
441 asm_output_svalue
*> asm_output_values_map_t
;
442 asm_output_values_map_t m_asm_output_values_map
;
444 typedef hash_map
<const_fn_result_svalue::key_t
,
445 const_fn_result_svalue
*> const_fn_result_values_map_t
;
446 const_fn_result_values_map_t m_const_fn_result_values_map
;
448 bool m_checking_feasibility
;
450 /* "Dynamically-allocated" svalue instances.
451 The number of these within the analysis can grow arbitrarily.
452 They are still owned by the manager. */
453 auto_delete_vec
<svalue
> m_managed_dynamic_svalues
;
455 /* Maximum complexity of svalues that weren't rejected. */
456 complexity m_max_complexity
;
458 /* region consolidation. */
460 code_region m_code_region
;
461 typedef hash_map
<tree
, function_region
*> fndecls_map_t
;
462 typedef fndecls_map_t::iterator fndecls_iterator_t
;
463 fndecls_map_t m_fndecls_map
;
465 typedef hash_map
<tree
, label_region
*> labels_map_t
;
466 typedef labels_map_t::iterator labels_iterator_t
;
467 labels_map_t m_labels_map
;
469 globals_region m_globals_region
;
470 typedef hash_map
<tree
, decl_region
*> globals_map_t
;
471 typedef globals_map_t::iterator globals_iterator_t
;
472 globals_map_t m_globals_map
;
474 consolidation_map
<field_region
> m_field_regions
;
475 consolidation_map
<element_region
> m_element_regions
;
476 consolidation_map
<offset_region
> m_offset_regions
;
477 consolidation_map
<sized_region
> m_sized_regions
;
478 consolidation_map
<cast_region
> m_cast_regions
;
479 consolidation_map
<frame_region
> m_frame_regions
;
480 consolidation_map
<symbolic_region
> m_symbolic_regions
;
482 typedef hash_map
<tree
, string_region
*> string_map_t
;
483 string_map_t m_string_map
;
485 consolidation_map
<bit_range_region
> m_bit_range_regions
;
487 store_manager m_store_mgr
;
489 bounded_ranges_manager
*m_range_mgr
;
491 /* "Dynamically-allocated" region instances.
492 The number of these within the analysis can grow arbitrarily.
493 They are still owned by the manager. */
494 auto_delete_vec
<region
> m_managed_dynamic_regions
;
497 struct append_ssa_names_cb_data
;
499 /* Helper class for handling calls to functions with known behavior.
500 Implemented in region-model-impl-calls.c. */
505 call_details (const gcall
*call
, region_model
*model
,
506 region_model_context
*ctxt
);
508 region_model_manager
*get_manager () const;
509 region_model_context
*get_ctxt () const { return m_ctxt
; }
510 uncertainty_t
*get_uncertainty () const;
511 tree
get_lhs_type () const { return m_lhs_type
; }
512 const region
*get_lhs_region () const { return m_lhs_region
; }
514 bool maybe_set_lhs (const svalue
*result
) const;
516 unsigned num_args () const;
518 const gcall
*get_call_stmt () const { return m_call
; }
520 tree
get_arg_tree (unsigned idx
) const;
521 tree
get_arg_type (unsigned idx
) const;
522 const svalue
*get_arg_svalue (unsigned idx
) const;
523 const char *get_arg_string_literal (unsigned idx
) const;
525 tree
get_fndecl_for_call () const;
527 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
528 void dump (bool simple
) const;
530 const svalue
*get_or_create_conjured_svalue (const region
*) const;
534 region_model
*m_model
;
535 region_model_context
*m_ctxt
;
537 const region
*m_lhs_region
;
540 /* A region_model encapsulates a representation of the state of memory, with
541 a tree of regions, along with their associated values.
542 The representation is graph-like because values can be pointers to
545 - a constraint_manager, capturing relationships between the values, and
546 - dynamic extents, mapping dynamically-allocated regions to svalues (their
552 typedef region_to_value_map dynamic_extents_t
;
554 region_model (region_model_manager
*mgr
);
555 region_model (const region_model
&other
);
557 region_model
&operator= (const region_model
&other
);
559 bool operator== (const region_model
&other
) const;
560 bool operator!= (const region_model
&other
) const
562 return !(*this == other
);
565 hashval_t
hash () const;
567 void print (pretty_printer
*pp
) const;
569 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
570 void dump (FILE *fp
, bool simple
, bool multiline
) const;
571 void dump (bool simple
) const;
575 void validate () const;
577 void canonicalize ();
578 bool canonicalized_p () const;
581 on_stmt_pre (const gimple
*stmt
,
582 bool *out_terminate_path
,
583 bool *out_unknown_side_effects
,
584 region_model_context
*ctxt
);
586 void on_assignment (const gassign
*stmt
, region_model_context
*ctxt
);
587 const svalue
*get_gassign_result (const gassign
*assign
,
588 region_model_context
*ctxt
);
589 void on_asm_stmt (const gasm
*asm_stmt
, region_model_context
*ctxt
);
590 bool on_call_pre (const gcall
*stmt
, region_model_context
*ctxt
,
591 bool *out_terminate_path
);
592 void on_call_post (const gcall
*stmt
,
593 bool unknown_side_effects
,
594 region_model_context
*ctxt
);
596 void purge_state_involving (const svalue
*sval
, region_model_context
*ctxt
);
598 /* Specific handling for on_call_pre. */
599 void impl_call_alloca (const call_details
&cd
);
600 void impl_call_analyzer_describe (const gcall
*call
,
601 region_model_context
*ctxt
);
602 void impl_call_analyzer_dump_capacity (const gcall
*call
,
603 region_model_context
*ctxt
);
604 void impl_call_analyzer_dump_escaped (const gcall
*call
);
605 void impl_call_analyzer_eval (const gcall
*call
,
606 region_model_context
*ctxt
);
607 void impl_call_builtin_expect (const call_details
&cd
);
608 void impl_call_calloc (const call_details
&cd
);
609 bool impl_call_error (const call_details
&cd
, unsigned min_args
,
610 bool *out_terminate_path
);
611 void impl_call_fgets (const call_details
&cd
);
612 void impl_call_fread (const call_details
&cd
);
613 void impl_call_free (const call_details
&cd
);
614 void impl_call_malloc (const call_details
&cd
);
615 void impl_call_memcpy (const call_details
&cd
);
616 void impl_call_memset (const call_details
&cd
);
617 void impl_call_realloc (const call_details
&cd
);
618 void impl_call_strchr (const call_details
&cd
);
619 void impl_call_strcpy (const call_details
&cd
);
620 void impl_call_strlen (const call_details
&cd
);
621 void impl_call_operator_new (const call_details
&cd
);
622 void impl_call_operator_delete (const call_details
&cd
);
623 void impl_deallocation_call (const call_details
&cd
);
625 void handle_unrecognized_call (const gcall
*call
,
626 region_model_context
*ctxt
);
627 void get_reachable_svalues (svalue_set
*out
,
628 const svalue
*extra_sval
,
629 const uncertainty_t
*uncertainty
);
631 void on_return (const greturn
*stmt
, region_model_context
*ctxt
);
632 void on_setjmp (const gcall
*stmt
, const exploded_node
*enode
,
633 region_model_context
*ctxt
);
634 void on_longjmp (const gcall
*longjmp_call
, const gcall
*setjmp_call
,
635 int setjmp_stack_depth
, region_model_context
*ctxt
);
637 void update_for_phis (const supernode
*snode
,
638 const cfg_superedge
*last_cfg_superedge
,
639 region_model_context
*ctxt
);
641 void handle_phi (const gphi
*phi
, tree lhs
, tree rhs
,
642 const region_model
&old_state
,
643 region_model_context
*ctxt
);
645 bool maybe_update_for_edge (const superedge
&edge
,
646 const gimple
*last_stmt
,
647 region_model_context
*ctxt
,
648 rejected_constraint
**out
);
650 void update_for_gcall (const gcall
*call_stmt
,
651 region_model_context
*ctxt
,
652 function
*callee
= NULL
);
654 void update_for_return_gcall (const gcall
*call_stmt
,
655 region_model_context
*ctxt
);
657 const region
*push_frame (function
*fun
, const vec
<const svalue
*> *arg_sids
,
658 region_model_context
*ctxt
);
659 const frame_region
*get_current_frame () const { return m_current_frame
; }
660 function
* get_current_function () const;
661 void pop_frame (const region
*result_dst
,
662 const svalue
**out_result
,
663 region_model_context
*ctxt
);
664 int get_stack_depth () const;
665 const frame_region
*get_frame_at_index (int index
) const;
667 const region
*get_lvalue (path_var pv
, region_model_context
*ctxt
) const;
668 const region
*get_lvalue (tree expr
, region_model_context
*ctxt
) const;
669 const svalue
*get_rvalue (path_var pv
, region_model_context
*ctxt
) const;
670 const svalue
*get_rvalue (tree expr
, region_model_context
*ctxt
) const;
672 const region
*deref_rvalue (const svalue
*ptr_sval
, tree ptr_tree
,
673 region_model_context
*ctxt
) const;
675 const svalue
*get_rvalue_for_bits (tree type
,
677 const bit_range
&bits
,
678 region_model_context
*ctxt
) const;
680 void set_value (const region
*lhs_reg
, const svalue
*rhs_sval
,
681 region_model_context
*ctxt
);
682 void set_value (tree lhs
, tree rhs
, region_model_context
*ctxt
);
683 void clobber_region (const region
*reg
);
684 void purge_region (const region
*reg
);
685 void fill_region (const region
*reg
, const svalue
*sval
);
686 void zero_fill_region (const region
*reg
);
687 void mark_region_as_unknown (const region
*reg
, uncertainty_t
*uncertainty
);
689 tristate
eval_condition (const svalue
*lhs
,
691 const svalue
*rhs
) const;
692 tristate
eval_condition_without_cm (const svalue
*lhs
,
694 const svalue
*rhs
) const;
695 tristate
compare_initial_and_pointer (const initial_svalue
*init
,
696 const region_svalue
*ptr
) const;
697 tristate
eval_condition (tree lhs
,
700 region_model_context
*ctxt
);
701 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
702 region_model_context
*ctxt
);
703 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
704 region_model_context
*ctxt
,
705 rejected_constraint
**out
);
707 const region
*create_region_for_heap_alloc (const svalue
*size_in_bytes
,
708 region_model_context
*ctxt
);
709 const region
*create_region_for_alloca (const svalue
*size_in_bytes
,
710 region_model_context
*ctxt
);
712 tree
get_representative_tree (const svalue
*sval
) const;
714 get_representative_path_var (const svalue
*sval
,
715 svalue_set
*visited
) const;
717 get_representative_path_var (const region
*reg
,
718 svalue_set
*visited
) const;
721 constraint_manager
*get_constraints ()
723 return m_constraints
;
726 store
*get_store () { return &m_store
; }
727 const store
*get_store () const { return &m_store
; }
729 const dynamic_extents_t
&
730 get_dynamic_extents () const
732 return m_dynamic_extents
;
734 const svalue
*get_dynamic_extents (const region
*reg
) const;
735 void set_dynamic_extents (const region
*reg
,
736 const svalue
*size_in_bytes
,
737 region_model_context
*ctxt
);
738 void unset_dynamic_extents (const region
*reg
);
740 region_model_manager
*get_manager () const { return m_mgr
; }
741 bounded_ranges_manager
*get_range_manager () const
743 return m_mgr
->get_range_manager ();
746 void unbind_region_and_descendents (const region
*reg
,
747 enum poison_kind pkind
);
749 bool can_merge_with_p (const region_model
&other_model
,
750 const program_point
&point
,
751 region_model
*out_model
,
752 const extrinsic_state
*ext_state
= NULL
,
753 const program_state
*state_a
= NULL
,
754 const program_state
*state_b
= NULL
) const;
756 tree
get_fndecl_for_call (const gcall
*call
,
757 region_model_context
*ctxt
);
759 void get_ssa_name_regions_for_current_frame
760 (auto_vec
<const decl_region
*> *out
) const;
761 static void append_ssa_names_cb (const region
*base_reg
,
762 struct append_ssa_names_cb_data
*data
);
764 const svalue
*get_store_value (const region
*reg
,
765 region_model_context
*ctxt
) const;
767 bool region_exists_p (const region
*reg
) const;
769 void loop_replay_fixup (const region_model
*dst_state
);
771 const svalue
*get_capacity (const region
*reg
) const;
773 /* Implemented in sm-malloc.cc */
774 void on_realloc_with_move (const call_details
&cd
,
775 const svalue
*old_ptr_sval
,
776 const svalue
*new_ptr_sval
);
779 const region
*get_lvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
780 const svalue
*get_rvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
783 get_representative_path_var_1 (const svalue
*sval
,
784 svalue_set
*visited
) const;
786 get_representative_path_var_1 (const region
*reg
,
787 svalue_set
*visited
) const;
789 bool add_constraint (const svalue
*lhs
,
792 region_model_context
*ctxt
);
793 bool add_constraints_from_binop (const svalue
*outer_lhs
,
794 enum tree_code outer_op
,
795 const svalue
*outer_rhs
,
797 region_model_context
*ctxt
);
799 void update_for_call_superedge (const call_superedge
&call_edge
,
800 region_model_context
*ctxt
);
801 void update_for_return_superedge (const return_superedge
&return_edge
,
802 region_model_context
*ctxt
);
803 void update_for_call_summary (const callgraph_superedge
&cg_sedge
,
804 region_model_context
*ctxt
);
805 bool apply_constraints_for_gcond (const cfg_superedge
&edge
,
806 const gcond
*cond_stmt
,
807 region_model_context
*ctxt
,
808 rejected_constraint
**out
);
809 bool apply_constraints_for_gswitch (const switch_cfg_superedge
&edge
,
810 const gswitch
*switch_stmt
,
811 region_model_context
*ctxt
,
812 rejected_constraint
**out
);
813 bool apply_constraints_for_exception (const gimple
*last_stmt
,
814 region_model_context
*ctxt
,
815 rejected_constraint
**out
);
817 int poison_any_pointers_to_descendents (const region
*reg
,
818 enum poison_kind pkind
);
820 void on_top_level_param (tree param
, region_model_context
*ctxt
);
822 bool called_from_main_p () const;
823 const svalue
*get_initial_value_for_global (const region
*reg
) const;
825 const svalue
*check_for_poison (const svalue
*sval
,
827 region_model_context
*ctxt
) const;
828 const region
* get_region_for_poisoned_expr (tree expr
) const;
830 void check_dynamic_size_for_taint (enum memory_space mem_space
,
831 const svalue
*size_in_bytes
,
832 region_model_context
*ctxt
) const;
834 void check_region_for_taint (const region
*reg
,
835 enum access_direction dir
,
836 region_model_context
*ctxt
) const;
838 void check_for_writable_region (const region
* dest_reg
,
839 region_model_context
*ctxt
) const;
840 void check_region_access (const region
*reg
,
841 enum access_direction dir
,
842 region_model_context
*ctxt
) const;
843 void check_region_for_write (const region
*dest_reg
,
844 region_model_context
*ctxt
) const;
845 void check_region_for_read (const region
*src_reg
,
846 region_model_context
*ctxt
) const;
848 void check_call_args (const call_details
&cd
) const;
849 void check_external_function_for_access_attr (const gcall
*call
,
851 region_model_context
*ctxt
) const;
853 /* Storing this here to avoid passing it around everywhere. */
854 region_model_manager
*const m_mgr
;
858 constraint_manager
*m_constraints
; // TODO: embed, rather than dynalloc?
860 const frame_region
*m_current_frame
;
862 /* Map from base region to size in bytes, for tracking the sizes of
863 dynamically-allocated regions.
864 This is part of the region_model rather than the region to allow for
865 memory regions to be resized (e.g. by realloc). */
866 dynamic_extents_t m_dynamic_extents
;
869 /* Some region_model activity could lead to warnings (e.g. attempts to use an
870 uninitialized value). This abstract base class encapsulates an interface
871 for the region model to use when emitting such warnings.
873 Having this as an abstract base class allows us to support the various
874 operations needed by program_state in the analyzer within region_model,
875 whilst keeping them somewhat modularized. */
877 class region_model_context
880 /* Hook for clients to store pending diagnostics.
881 Return true if the diagnostic was stored, or false if it was deleted. */
882 virtual bool warn (pending_diagnostic
*d
) = 0;
884 /* Hook for clients to be notified when an SVAL that was reachable
885 in a previous state is no longer live, so that clients can emit warnings
887 virtual void on_svalue_leak (const svalue
*sval
) = 0;
889 /* Hook for clients to be notified when the set of explicitly live
890 svalues changes, so that they can purge state relating to dead
892 virtual void on_liveness_change (const svalue_set
&live_svalues
,
893 const region_model
*model
) = 0;
895 virtual logger
*get_logger () = 0;
897 /* Hook for clients to be notified when the condition
898 "LHS OP RHS" is added to the region model.
899 This exists so that state machines can detect tests on edges,
900 and use them to trigger sm-state transitions (e.g. transitions due
901 to ptrs becoming known to be NULL or non-NULL, rather than just
903 virtual void on_condition (const svalue
*lhs
,
905 const svalue
*rhs
) = 0;
907 /* Hooks for clients to be notified when an unknown change happens
908 to SVAL (in response to a call to an unknown function). */
909 virtual void on_unknown_change (const svalue
*sval
, bool is_mutable
) = 0;
911 /* Hooks for clients to be notified when a phi node is handled,
912 where RHS is the pertinent argument. */
913 virtual void on_phi (const gphi
*phi
, tree rhs
) = 0;
915 /* Hooks for clients to be notified when the region model doesn't
916 know how to handle the tree code of T at LOC. */
917 virtual void on_unexpected_tree_code (tree t
,
918 const dump_location_t
&loc
) = 0;
920 /* Hook for clients to be notified when a function_decl escapes. */
921 virtual void on_escaped_function (tree fndecl
) = 0;
923 virtual uncertainty_t
*get_uncertainty () = 0;
925 /* Hook for clients to purge state involving SVAL. */
926 virtual void purge_state_involving (const svalue
*sval
) = 0;
928 /* Hook for clients to split state with a non-standard path.
929 Take ownership of INFO. */
930 virtual void bifurcate (custom_edge_info
*info
) = 0;
932 /* Hook for clients to terminate the standard path. */
933 virtual void terminate_path () = 0;
935 virtual const extrinsic_state
*get_ext_state () const = 0;
937 /* Hook for clients to access the "malloc" state machine in
938 any underlying program_state. */
939 virtual bool get_malloc_map (sm_state_map
**out_smap
,
940 const state_machine
**out_sm
,
941 unsigned *out_sm_idx
) = 0;
942 /* Likewise for the "taint" state machine. */
943 virtual bool get_taint_map (sm_state_map
**out_smap
,
944 const state_machine
**out_sm
,
945 unsigned *out_sm_idx
) = 0;
947 /* Get the current statement, if any. */
948 virtual const gimple
*get_stmt () const = 0;
951 /* A "do nothing" subclass of region_model_context. */
953 class noop_region_model_context
: public region_model_context
956 bool warn (pending_diagnostic
*) OVERRIDE
{ return false; }
957 void on_svalue_leak (const svalue
*) OVERRIDE
{}
958 void on_liveness_change (const svalue_set
&,
959 const region_model
*) OVERRIDE
{}
960 logger
*get_logger () OVERRIDE
{ return NULL
; }
961 void on_condition (const svalue
*lhs ATTRIBUTE_UNUSED
,
962 enum tree_code op ATTRIBUTE_UNUSED
,
963 const svalue
*rhs ATTRIBUTE_UNUSED
) OVERRIDE
966 void on_unknown_change (const svalue
*sval ATTRIBUTE_UNUSED
,
967 bool is_mutable ATTRIBUTE_UNUSED
) OVERRIDE
970 void on_phi (const gphi
*phi ATTRIBUTE_UNUSED
,
971 tree rhs ATTRIBUTE_UNUSED
) OVERRIDE
974 void on_unexpected_tree_code (tree
, const dump_location_t
&) OVERRIDE
{}
976 void on_escaped_function (tree
) OVERRIDE
{}
978 uncertainty_t
*get_uncertainty () OVERRIDE
{ return NULL
; }
980 void purge_state_involving (const svalue
*sval ATTRIBUTE_UNUSED
) OVERRIDE
{}
982 void bifurcate (custom_edge_info
*info
) OVERRIDE
;
983 void terminate_path () OVERRIDE
;
985 const extrinsic_state
*get_ext_state () const OVERRIDE
{ return NULL
; }
987 bool get_malloc_map (sm_state_map
**,
988 const state_machine
**,
993 bool get_taint_map (sm_state_map
**,
994 const state_machine
**,
1000 const gimple
*get_stmt () const OVERRIDE
{ return NULL
; }
1003 /* A subclass of region_model_context for determining if operations fail
1004 e.g. "can we generate a region for the lvalue of EXPR?". */
1006 class tentative_region_model_context
: public noop_region_model_context
1009 tentative_region_model_context () : m_num_unexpected_codes (0) {}
1011 void on_unexpected_tree_code (tree
, const dump_location_t
&)
1014 m_num_unexpected_codes
++;
1017 bool had_errors_p () const { return m_num_unexpected_codes
> 0; }
1020 int m_num_unexpected_codes
;
1023 /* A bundle of data for use when attempting to merge two region_model
1024 instances to make a third. */
1028 model_merger (const region_model
*model_a
,
1029 const region_model
*model_b
,
1030 const program_point
&point
,
1031 region_model
*merged_model
,
1032 const extrinsic_state
*ext_state
,
1033 const program_state
*state_a
,
1034 const program_state
*state_b
)
1035 : m_model_a (model_a
), m_model_b (model_b
),
1037 m_merged_model (merged_model
),
1038 m_ext_state (ext_state
),
1039 m_state_a (state_a
), m_state_b (state_b
)
1043 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
1044 void dump (FILE *fp
, bool simple
) const;
1045 void dump (bool simple
) const;
1047 region_model_manager
*get_manager () const
1049 return m_model_a
->get_manager ();
1052 bool mergeable_svalue_p (const svalue
*) const;
1054 const region_model
*m_model_a
;
1055 const region_model
*m_model_b
;
1056 const program_point
&m_point
;
1057 region_model
*m_merged_model
;
1059 const extrinsic_state
*m_ext_state
;
1060 const program_state
*m_state_a
;
1061 const program_state
*m_state_b
;
1064 /* A record that can (optionally) be written out when
1065 region_model::add_constraint fails. */
1067 class rejected_constraint
1070 virtual ~rejected_constraint () {}
1071 virtual void dump_to_pp (pretty_printer
*pp
) const = 0;
1073 const region_model
&get_model () const { return m_model
; }
1076 rejected_constraint (const region_model
&model
)
1080 region_model m_model
;
1083 class rejected_op_constraint
: public rejected_constraint
1086 rejected_op_constraint (const region_model
&model
,
1087 tree lhs
, enum tree_code op
, tree rhs
)
1088 : rejected_constraint (model
),
1089 m_lhs (lhs
), m_op (op
), m_rhs (rhs
)
1092 void dump_to_pp (pretty_printer
*pp
) const FINAL OVERRIDE
;
1095 enum tree_code m_op
;
1099 class rejected_ranges_constraint
: public rejected_constraint
1102 rejected_ranges_constraint (const region_model
&model
,
1103 tree expr
, const bounded_ranges
*ranges
)
1104 : rejected_constraint (model
),
1105 m_expr (expr
), m_ranges (ranges
)
1108 void dump_to_pp (pretty_printer
*pp
) const FINAL OVERRIDE
;
1112 const bounded_ranges
*m_ranges
;
1115 /* A bundle of state. */
1120 engine (logger
*logger
= NULL
);
1121 region_model_manager
*get_model_manager () { return &m_mgr
; }
1123 void log_stats (logger
*logger
) const;
1126 region_model_manager m_mgr
;
1132 extern void debug (const region_model
&rmodel
);
1138 namespace selftest
{
1140 using namespace ::selftest
;
1142 /* An implementation of region_model_context for use in selftests, which
1143 stores any pending_diagnostic instances passed to it. */
1145 class test_region_model_context
: public noop_region_model_context
1148 bool warn (pending_diagnostic
*d
) FINAL OVERRIDE
1150 m_diagnostics
.safe_push (d
);
1154 unsigned get_num_diagnostics () const { return m_diagnostics
.length (); }
1156 void on_unexpected_tree_code (tree t
, const dump_location_t
&)
1159 internal_error ("unhandled tree code: %qs",
1160 get_tree_code_name (TREE_CODE (t
)));
1164 /* Implicitly delete any diagnostics in the dtor. */
1165 auto_delete_vec
<pending_diagnostic
> m_diagnostics
;
1168 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1169 Verify that MODEL remains satisfiable. */
1171 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1172 SELFTEST_BEGIN_STMT \
1173 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1174 ASSERT_TRUE (sat); \
1177 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1178 Verify that the result is not satisfiable. */
1180 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1181 SELFTEST_BEGIN_STMT \
1182 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1183 ASSERT_FALSE (sat); \
1186 /* Implementation detail of the ASSERT_CONDITION_* macros. */
1188 void assert_condition (const location
&loc
,
1189 region_model
&model
,
1190 const svalue
*lhs
, tree_code op
, const svalue
*rhs
,
1193 void assert_condition (const location
&loc
,
1194 region_model
&model
,
1195 tree lhs
, tree_code op
, tree rhs
,
1198 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1201 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1202 SELFTEST_BEGIN_STMT \
1203 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1204 tristate (tristate::TS_TRUE)); \
1207 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1210 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1211 SELFTEST_BEGIN_STMT \
1212 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1213 tristate (tristate::TS_FALSE)); \
1216 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1219 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1220 SELFTEST_BEGIN_STMT \
1221 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1222 tristate (tristate::TS_UNKNOWN)); \
1225 } /* end of namespace selftest. */
1227 #endif /* #if CHECKING_P */
1231 #endif /* GCC_ANALYZER_REGION_MODEL_H */