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 */
30 #include "analyzer/svalue.h"
31 #include "analyzer/region.h"
32 #include "analyzer/known-function-manager.h"
33 #include "analyzer/region-model-manager.h"
34 #include "analyzer/pending-diagnostic.h"
40 extern void add_path_var (path_var pv
, hash
&hstate
);
41 } // namespace inchash
49 one_way_id_map (int num_ids
);
50 void put (T src
, T dst
);
51 T
get_dst_for_src (T src
) const;
52 void dump_to_pp (pretty_printer
*pp
) const;
54 void update (T
*) const;
57 auto_vec
<T
> m_src_to_dst
;
60 /* class one_way_id_map. */
62 /* one_way_id_map's ctor, which populates the map with dummy null values. */
65 inline one_way_id_map
<T
>::one_way_id_map (int num_svalues
)
66 : m_src_to_dst (num_svalues
)
68 for (int i
= 0; i
< num_svalues
; i
++)
69 m_src_to_dst
.quick_push (T::null ());
72 /* Record that SRC is to be mapped to DST. */
76 one_way_id_map
<T
>::put (T src
, T dst
)
78 m_src_to_dst
[src
.as_int ()] = dst
;
81 /* Get the new value for SRC within the map. */
85 one_way_id_map
<T
>::get_dst_for_src (T src
) const
89 return m_src_to_dst
[src
.as_int ()];
92 /* Dump this map to PP. */
96 one_way_id_map
<T
>::dump_to_pp (pretty_printer
*pp
) const
98 pp_string (pp
, "src to dst: {");
101 FOR_EACH_VEC_ELT (m_src_to_dst
, i
, dst
)
104 pp_string (pp
, ", ");
105 T
src (T::from_int (i
));
107 pp_string (pp
, " -> ");
114 /* Dump this map to stderr. */
116 template <typename T
>
117 DEBUG_FUNCTION
inline void
118 one_way_id_map
<T
>::dump () const
121 pp
.buffer
->stream
= stderr
;
126 /* Update *ID from the old value to its new value in this map. */
128 template <typename T
>
130 one_way_id_map
<T
>::update (T
*id
) const
132 *id
= get_dst_for_src (*id
);
135 /* A mapping from region to svalue for use when tracking state. */
137 class region_to_value_map
140 typedef hash_map
<const region
*, const svalue
*> hash_map_t
;
141 typedef hash_map_t::iterator iterator
;
143 region_to_value_map () : m_hash_map () {}
144 region_to_value_map (const region_to_value_map
&other
)
145 : m_hash_map (other
.m_hash_map
) {}
146 region_to_value_map
&operator= (const region_to_value_map
&other
);
148 bool operator== (const region_to_value_map
&other
) const;
149 bool operator!= (const region_to_value_map
&other
) const
151 return !(*this == other
);
154 iterator
begin () const { return m_hash_map
.begin (); }
155 iterator
end () const { return m_hash_map
.end (); }
157 const svalue
* const *get (const region
*reg
) const
159 return const_cast <hash_map_t
&> (m_hash_map
).get (reg
);
161 void put (const region
*reg
, const svalue
*sval
)
163 m_hash_map
.put (reg
, sval
);
165 void remove (const region
*reg
)
167 m_hash_map
.remove (reg
);
170 bool is_empty () const { return m_hash_map
.is_empty (); }
172 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
173 void dump (bool simple
) const;
175 bool can_merge_with_p (const region_to_value_map
&other
,
176 region_to_value_map
*out
) const;
178 void purge_state_involving (const svalue
*sval
);
181 hash_map_t m_hash_map
;
184 /* Various operations delete information from a region_model.
186 This struct tracks how many of each kind of entity were purged (e.g.
187 for selftests, and for debugging). */
194 m_num_equiv_classes (0),
195 m_num_constraints (0),
196 m_num_bounded_ranges_constraints (0),
197 m_num_client_items (0)
202 int m_num_equiv_classes
;
203 int m_num_constraints
;
204 int m_num_bounded_ranges_constraints
;
205 int m_num_client_items
;
208 /* A base class for visiting regions and svalues, with do-nothing
209 base implementations of the per-subclass vfuncs. */
214 virtual void visit_region_svalue (const region_svalue
*) {}
215 virtual void visit_constant_svalue (const constant_svalue
*) {}
216 virtual void visit_unknown_svalue (const unknown_svalue
*) {}
217 virtual void visit_poisoned_svalue (const poisoned_svalue
*) {}
218 virtual void visit_setjmp_svalue (const setjmp_svalue
*) {}
219 virtual void visit_initial_svalue (const initial_svalue
*) {}
220 virtual void visit_unaryop_svalue (const unaryop_svalue
*) {}
221 virtual void visit_binop_svalue (const binop_svalue
*) {}
222 virtual void visit_sub_svalue (const sub_svalue
*) {}
223 virtual void visit_repeated_svalue (const repeated_svalue
*) {}
224 virtual void visit_bits_within_svalue (const bits_within_svalue
*) {}
225 virtual void visit_unmergeable_svalue (const unmergeable_svalue
*) {}
226 virtual void visit_placeholder_svalue (const placeholder_svalue
*) {}
227 virtual void visit_widening_svalue (const widening_svalue
*) {}
228 virtual void visit_compound_svalue (const compound_svalue
*) {}
229 virtual void visit_conjured_svalue (const conjured_svalue
*) {}
230 virtual void visit_asm_output_svalue (const asm_output_svalue
*) {}
231 virtual void visit_const_fn_result_svalue (const const_fn_result_svalue
*) {}
233 virtual void visit_region (const region
*) {}
236 struct append_regions_cb_data
;
238 /* Helper class for handling calls to functions with known behavior.
239 Implemented in region-model-impl-calls.c. */
244 call_details (const gcall
*call
, region_model
*model
,
245 region_model_context
*ctxt
);
247 region_model
*get_model () const { return m_model
; }
248 region_model_manager
*get_manager () const;
249 region_model_context
*get_ctxt () const { return m_ctxt
; }
250 logger
*get_logger () const;
252 uncertainty_t
*get_uncertainty () const;
253 tree
get_lhs_type () const { return m_lhs_type
; }
254 const region
*get_lhs_region () const { return m_lhs_region
; }
256 bool maybe_set_lhs (const svalue
*result
) const;
258 unsigned num_args () const;
260 const gcall
*get_call_stmt () const { return m_call
; }
262 tree
get_arg_tree (unsigned idx
) const;
263 tree
get_arg_type (unsigned idx
) const;
264 const svalue
*get_arg_svalue (unsigned idx
) const;
265 const char *get_arg_string_literal (unsigned idx
) const;
267 tree
get_fndecl_for_call () const;
269 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
270 void dump (bool simple
) const;
272 const svalue
*get_or_create_conjured_svalue (const region
*) const;
276 region_model
*m_model
;
277 region_model_context
*m_ctxt
;
279 const region
*m_lhs_region
;
282 /* A region_model encapsulates a representation of the state of memory, with
283 a tree of regions, along with their associated values.
284 The representation is graph-like because values can be pointers to
287 - a constraint_manager, capturing relationships between the values, and
288 - dynamic extents, mapping dynamically-allocated regions to svalues (their
294 typedef region_to_value_map dynamic_extents_t
;
296 region_model (region_model_manager
*mgr
);
297 region_model (const region_model
&other
);
299 region_model
&operator= (const region_model
&other
);
301 bool operator== (const region_model
&other
) const;
302 bool operator!= (const region_model
&other
) const
304 return !(*this == other
);
307 hashval_t
hash () const;
309 void print (pretty_printer
*pp
) const;
311 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
312 void dump (FILE *fp
, bool simple
, bool multiline
) const;
313 void dump (bool simple
) const;
317 void validate () const;
319 void canonicalize ();
320 bool canonicalized_p () const;
323 on_stmt_pre (const gimple
*stmt
,
324 bool *out_terminate_path
,
325 bool *out_unknown_side_effects
,
326 region_model_context
*ctxt
);
328 void on_assignment (const gassign
*stmt
, region_model_context
*ctxt
);
329 const svalue
*get_gassign_result (const gassign
*assign
,
330 region_model_context
*ctxt
);
331 void on_asm_stmt (const gasm
*asm_stmt
, region_model_context
*ctxt
);
332 bool on_call_pre (const gcall
*stmt
, region_model_context
*ctxt
,
333 bool *out_terminate_path
);
334 void on_call_post (const gcall
*stmt
,
335 bool unknown_side_effects
,
336 region_model_context
*ctxt
);
338 void purge_state_involving (const svalue
*sval
, region_model_context
*ctxt
);
340 /* Specific handling for on_call_pre. */
341 void impl_call_alloca (const call_details
&cd
);
342 void impl_call_analyzer_describe (const gcall
*call
,
343 region_model_context
*ctxt
);
344 void impl_call_analyzer_dump_capacity (const gcall
*call
,
345 region_model_context
*ctxt
);
346 void impl_call_analyzer_dump_escaped (const gcall
*call
);
347 void impl_call_analyzer_dump_named_constant (const gcall
*call
,
348 region_model_context
*ctxt
);
349 void impl_call_analyzer_eval (const gcall
*call
,
350 region_model_context
*ctxt
);
351 void impl_call_analyzer_get_unknown_ptr (const call_details
&cd
);
352 void impl_call_builtin_expect (const call_details
&cd
);
353 void impl_call_calloc (const call_details
&cd
);
354 void impl_call_errno_location (const call_details
&cd
);
355 bool impl_call_error (const call_details
&cd
, unsigned min_args
,
356 bool *out_terminate_path
);
357 void impl_call_fgets (const call_details
&cd
);
358 void impl_call_fread (const call_details
&cd
);
359 void impl_call_free (const call_details
&cd
);
360 void impl_call_malloc (const call_details
&cd
);
361 void impl_call_memcpy (const call_details
&cd
);
362 void impl_call_memset (const call_details
&cd
);
363 void impl_call_pipe (const call_details
&cd
);
364 void impl_call_putenv (const call_details
&cd
);
365 void impl_call_realloc (const call_details
&cd
);
366 void impl_call_strchr (const call_details
&cd
);
367 void impl_call_strcpy (const call_details
&cd
);
368 void impl_call_strlen (const call_details
&cd
);
369 void impl_call_operator_new (const call_details
&cd
);
370 void impl_call_operator_delete (const call_details
&cd
);
371 void impl_deallocation_call (const call_details
&cd
);
373 /* Implemented in varargs.cc. */
374 void impl_call_va_start (const call_details
&cd
);
375 void impl_call_va_copy (const call_details
&cd
);
376 void impl_call_va_arg (const call_details
&cd
);
377 void impl_call_va_end (const call_details
&cd
);
379 const svalue
*maybe_get_copy_bounds (const region
*src_reg
,
380 const svalue
*num_bytes_sval
);
381 void update_for_int_cst_return (const call_details
&cd
,
384 void update_for_zero_return (const call_details
&cd
,
386 void update_for_nonzero_return (const call_details
&cd
);
388 void handle_unrecognized_call (const gcall
*call
,
389 region_model_context
*ctxt
);
390 void get_reachable_svalues (svalue_set
*out
,
391 const svalue
*extra_sval
,
392 const uncertainty_t
*uncertainty
);
394 void on_return (const greturn
*stmt
, region_model_context
*ctxt
);
395 void on_setjmp (const gcall
*stmt
, const exploded_node
*enode
,
396 region_model_context
*ctxt
);
397 void on_longjmp (const gcall
*longjmp_call
, const gcall
*setjmp_call
,
398 int setjmp_stack_depth
, region_model_context
*ctxt
);
400 void update_for_phis (const supernode
*snode
,
401 const cfg_superedge
*last_cfg_superedge
,
402 region_model_context
*ctxt
);
404 void handle_phi (const gphi
*phi
, tree lhs
, tree rhs
,
405 const region_model
&old_state
,
406 region_model_context
*ctxt
);
408 bool maybe_update_for_edge (const superedge
&edge
,
409 const gimple
*last_stmt
,
410 region_model_context
*ctxt
,
411 rejected_constraint
**out
);
413 void update_for_gcall (const gcall
*call_stmt
,
414 region_model_context
*ctxt
,
415 function
*callee
= NULL
);
417 void update_for_return_gcall (const gcall
*call_stmt
,
418 region_model_context
*ctxt
);
420 const region
*push_frame (function
*fun
, const vec
<const svalue
*> *arg_sids
,
421 region_model_context
*ctxt
);
422 const frame_region
*get_current_frame () const { return m_current_frame
; }
423 function
* get_current_function () const;
424 void pop_frame (tree result_lvalue
,
425 const svalue
**out_result
,
426 region_model_context
*ctxt
);
427 int get_stack_depth () const;
428 const frame_region
*get_frame_at_index (int index
) const;
430 const region
*get_lvalue (path_var pv
, region_model_context
*ctxt
) const;
431 const region
*get_lvalue (tree expr
, region_model_context
*ctxt
) const;
432 const svalue
*get_rvalue (path_var pv
, region_model_context
*ctxt
) const;
433 const svalue
*get_rvalue (tree expr
, region_model_context
*ctxt
) const;
435 const region
*deref_rvalue (const svalue
*ptr_sval
, tree ptr_tree
,
436 region_model_context
*ctxt
) const;
438 const svalue
*get_rvalue_for_bits (tree type
,
440 const bit_range
&bits
,
441 region_model_context
*ctxt
) const;
443 void set_value (const region
*lhs_reg
, const svalue
*rhs_sval
,
444 region_model_context
*ctxt
);
445 void set_value (tree lhs
, tree rhs
, region_model_context
*ctxt
);
446 void clobber_region (const region
*reg
);
447 void purge_region (const region
*reg
);
448 void fill_region (const region
*reg
, const svalue
*sval
);
449 void zero_fill_region (const region
*reg
);
450 void mark_region_as_unknown (const region
*reg
, uncertainty_t
*uncertainty
);
452 tristate
eval_condition (const svalue
*lhs
,
454 const svalue
*rhs
) const;
455 tristate
compare_initial_and_pointer (const initial_svalue
*init
,
456 const region_svalue
*ptr
) const;
457 tristate
symbolic_greater_than (const binop_svalue
*a
,
458 const svalue
*b
) const;
459 tristate
structural_equality (const svalue
*a
, const svalue
*b
) const;
460 tristate
eval_condition (tree lhs
,
463 region_model_context
*ctxt
) const;
464 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
465 region_model_context
*ctxt
);
466 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
467 region_model_context
*ctxt
,
468 rejected_constraint
**out
);
470 const region
*create_region_for_heap_alloc (const svalue
*size_in_bytes
,
471 region_model_context
*ctxt
);
472 const region
*create_region_for_alloca (const svalue
*size_in_bytes
,
473 region_model_context
*ctxt
);
475 tree
get_representative_tree (const svalue
*sval
) const;
476 tree
get_representative_tree (const region
*reg
) const;
478 get_representative_path_var (const svalue
*sval
,
479 svalue_set
*visited
) const;
481 get_representative_path_var (const region
*reg
,
482 svalue_set
*visited
) const;
485 constraint_manager
*get_constraints ()
487 return m_constraints
;
490 store
*get_store () { return &m_store
; }
491 const store
*get_store () const { return &m_store
; }
493 const dynamic_extents_t
&
494 get_dynamic_extents () const
496 return m_dynamic_extents
;
498 const svalue
*get_dynamic_extents (const region
*reg
) const;
499 void set_dynamic_extents (const region
*reg
,
500 const svalue
*size_in_bytes
,
501 region_model_context
*ctxt
);
502 void unset_dynamic_extents (const region
*reg
);
504 region_model_manager
*get_manager () const { return m_mgr
; }
505 bounded_ranges_manager
*get_range_manager () const
507 return m_mgr
->get_range_manager ();
510 void unbind_region_and_descendents (const region
*reg
,
511 enum poison_kind pkind
);
513 bool can_merge_with_p (const region_model
&other_model
,
514 const program_point
&point
,
515 region_model
*out_model
,
516 const extrinsic_state
*ext_state
= NULL
,
517 const program_state
*state_a
= NULL
,
518 const program_state
*state_b
= NULL
) const;
520 tree
get_fndecl_for_call (const gcall
*call
,
521 region_model_context
*ctxt
);
523 void get_regions_for_current_frame (auto_vec
<const decl_region
*> *out
) const;
524 static void append_regions_cb (const region
*base_reg
,
525 struct append_regions_cb_data
*data
);
527 const svalue
*get_store_value (const region
*reg
,
528 region_model_context
*ctxt
) const;
530 bool region_exists_p (const region
*reg
) const;
532 void loop_replay_fixup (const region_model
*dst_state
);
534 const svalue
*get_capacity (const region
*reg
) const;
536 const svalue
*get_string_size (const svalue
*sval
) const;
537 const svalue
*get_string_size (const region
*reg
) const;
539 bool replay_call_summary (call_summary_replay
&r
,
540 const region_model
&summary
);
542 void maybe_complain_about_infoleak (const region
*dst_reg
,
543 const svalue
*copied_sval
,
544 const region
*src_reg
,
545 region_model_context
*ctxt
);
547 void set_errno (const call_details
&cd
);
549 /* Implemented in sm-fd.cc */
550 void mark_as_valid_fd (const svalue
*sval
, region_model_context
*ctxt
);
552 /* Implemented in sm-malloc.cc */
553 void on_realloc_with_move (const call_details
&cd
,
554 const svalue
*old_ptr_sval
,
555 const svalue
*new_ptr_sval
);
557 /* Implemented in sm-taint.cc. */
558 void mark_as_tainted (const svalue
*sval
,
559 region_model_context
*ctxt
);
562 const region
*get_lvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
563 const svalue
*get_rvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
566 get_representative_path_var_1 (const svalue
*sval
,
567 svalue_set
*visited
) const;
569 get_representative_path_var_1 (const region
*reg
,
570 svalue_set
*visited
) const;
572 const known_function
*get_known_function (tree fndecl
) const;
574 bool add_constraint (const svalue
*lhs
,
577 region_model_context
*ctxt
);
578 bool add_constraints_from_binop (const svalue
*outer_lhs
,
579 enum tree_code outer_op
,
580 const svalue
*outer_rhs
,
582 region_model_context
*ctxt
);
584 void update_for_call_superedge (const call_superedge
&call_edge
,
585 region_model_context
*ctxt
);
586 void update_for_return_superedge (const return_superedge
&return_edge
,
587 region_model_context
*ctxt
);
588 bool apply_constraints_for_gcond (const cfg_superedge
&edge
,
589 const gcond
*cond_stmt
,
590 region_model_context
*ctxt
,
591 rejected_constraint
**out
);
592 bool apply_constraints_for_gswitch (const switch_cfg_superedge
&edge
,
593 const gswitch
*switch_stmt
,
594 region_model_context
*ctxt
,
595 rejected_constraint
**out
);
596 bool apply_constraints_for_exception (const gimple
*last_stmt
,
597 region_model_context
*ctxt
,
598 rejected_constraint
**out
);
600 int poison_any_pointers_to_descendents (const region
*reg
,
601 enum poison_kind pkind
);
603 void on_top_level_param (tree param
, region_model_context
*ctxt
);
605 bool called_from_main_p () const;
606 const svalue
*get_initial_value_for_global (const region
*reg
) const;
608 const svalue
*check_for_poison (const svalue
*sval
,
610 region_model_context
*ctxt
) const;
611 const region
* get_region_for_poisoned_expr (tree expr
) const;
613 void check_dynamic_size_for_taint (enum memory_space mem_space
,
614 const svalue
*size_in_bytes
,
615 region_model_context
*ctxt
) const;
616 void check_dynamic_size_for_floats (const svalue
*size_in_bytes
,
617 region_model_context
*ctxt
) const;
619 void check_region_for_taint (const region
*reg
,
620 enum access_direction dir
,
621 region_model_context
*ctxt
) const;
623 void check_for_writable_region (const region
* dest_reg
,
624 region_model_context
*ctxt
) const;
625 void check_region_access (const region
*reg
,
626 enum access_direction dir
,
627 region_model_context
*ctxt
) const;
628 void check_region_for_write (const region
*dest_reg
,
629 region_model_context
*ctxt
) const;
630 void check_region_for_read (const region
*src_reg
,
631 region_model_context
*ctxt
) const;
632 void check_region_size (const region
*lhs_reg
, const svalue
*rhs_sval
,
633 region_model_context
*ctxt
) const;
634 void check_symbolic_bounds (const region
*base_reg
,
635 const svalue
*sym_byte_offset
,
636 const svalue
*num_bytes_sval
,
637 const svalue
*capacity
,
638 enum access_direction dir
,
639 region_model_context
*ctxt
) const;
640 void check_region_bounds (const region
*reg
, enum access_direction dir
,
641 region_model_context
*ctxt
) const;
643 void check_call_args (const call_details
&cd
) const;
644 void check_external_function_for_access_attr (const gcall
*call
,
646 region_model_context
*ctxt
) const;
648 /* Storing this here to avoid passing it around everywhere. */
649 region_model_manager
*const m_mgr
;
653 constraint_manager
*m_constraints
; // TODO: embed, rather than dynalloc?
655 const frame_region
*m_current_frame
;
657 /* Map from base region to size in bytes, for tracking the sizes of
658 dynamically-allocated regions.
659 This is part of the region_model rather than the region to allow for
660 memory regions to be resized (e.g. by realloc). */
661 dynamic_extents_t m_dynamic_extents
;
664 /* Some region_model activity could lead to warnings (e.g. attempts to use an
665 uninitialized value). This abstract base class encapsulates an interface
666 for the region model to use when emitting such warnings.
668 Having this as an abstract base class allows us to support the various
669 operations needed by program_state in the analyzer within region_model,
670 whilst keeping them somewhat modularized. */
672 class region_model_context
675 /* Hook for clients to store pending diagnostics.
676 Return true if the diagnostic was stored, or false if it was deleted. */
677 virtual bool warn (std::unique_ptr
<pending_diagnostic
> d
) = 0;
679 /* Hook for clients to add a note to the last previously stored
680 pending diagnostic. */
681 virtual void add_note (std::unique_ptr
<pending_note
> pn
) = 0;
683 /* Hook for clients to be notified when an SVAL that was reachable
684 in a previous state is no longer live, so that clients can emit warnings
686 virtual void on_svalue_leak (const svalue
*sval
) = 0;
688 /* Hook for clients to be notified when the set of explicitly live
689 svalues changes, so that they can purge state relating to dead
691 virtual void on_liveness_change (const svalue_set
&live_svalues
,
692 const region_model
*model
) = 0;
694 virtual logger
*get_logger () = 0;
696 /* Hook for clients to be notified when the condition
697 "LHS OP RHS" is added to the region model.
698 This exists so that state machines can detect tests on edges,
699 and use them to trigger sm-state transitions (e.g. transitions due
700 to ptrs becoming known to be NULL or non-NULL, rather than just
702 virtual void on_condition (const svalue
*lhs
,
704 const svalue
*rhs
) = 0;
706 /* Hook for clients to be notified when the condition that
707 SVAL is within RANGES is added to the region model.
708 Similar to on_condition, but for use when handling switch statements.
709 RANGES is non-empty. */
710 virtual void on_bounded_ranges (const svalue
&sval
,
711 const bounded_ranges
&ranges
) = 0;
713 /* Hook for clients to be notified when a frame is popped from the stack. */
714 virtual void on_pop_frame (const frame_region
*) = 0;
716 /* Hooks for clients to be notified when an unknown change happens
717 to SVAL (in response to a call to an unknown function). */
718 virtual void on_unknown_change (const svalue
*sval
, bool is_mutable
) = 0;
720 /* Hooks for clients to be notified when a phi node is handled,
721 where RHS is the pertinent argument. */
722 virtual void on_phi (const gphi
*phi
, tree rhs
) = 0;
724 /* Hooks for clients to be notified when the region model doesn't
725 know how to handle the tree code of T at LOC. */
726 virtual void on_unexpected_tree_code (tree t
,
727 const dump_location_t
&loc
) = 0;
729 /* Hook for clients to be notified when a function_decl escapes. */
730 virtual void on_escaped_function (tree fndecl
) = 0;
732 virtual uncertainty_t
*get_uncertainty () = 0;
734 /* Hook for clients to purge state involving SVAL. */
735 virtual void purge_state_involving (const svalue
*sval
) = 0;
737 /* Hook for clients to split state with a non-standard path. */
738 virtual void bifurcate (std::unique_ptr
<custom_edge_info
> info
) = 0;
740 /* Hook for clients to terminate the standard path. */
741 virtual void terminate_path () = 0;
743 virtual const extrinsic_state
*get_ext_state () const = 0;
745 /* Hook for clients to access the a specific state machine in
746 any underlying program_state. */
747 virtual bool get_state_map_by_name (const char *name
,
748 sm_state_map
**out_smap
,
749 const state_machine
**out_sm
,
750 unsigned *out_sm_idx
) = 0;
752 /* Precanned ways for clients to access specific state machines. */
753 bool get_fd_map (sm_state_map
**out_smap
,
754 const state_machine
**out_sm
,
755 unsigned *out_sm_idx
)
757 return get_state_map_by_name ("file-descriptor", out_smap
, out_sm
,
760 bool get_malloc_map (sm_state_map
**out_smap
,
761 const state_machine
**out_sm
,
762 unsigned *out_sm_idx
)
764 return get_state_map_by_name ("malloc", out_smap
, out_sm
, out_sm_idx
);
766 bool get_taint_map (sm_state_map
**out_smap
,
767 const state_machine
**out_sm
,
768 unsigned *out_sm_idx
)
770 return get_state_map_by_name ("taint", out_smap
, out_sm
, out_sm_idx
);
773 /* Get the current statement, if any. */
774 virtual const gimple
*get_stmt () const = 0;
777 /* A "do nothing" subclass of region_model_context. */
779 class noop_region_model_context
: public region_model_context
782 bool warn (std::unique_ptr
<pending_diagnostic
>) override
{ return false; }
783 void add_note (std::unique_ptr
<pending_note
>) override
;
784 void on_svalue_leak (const svalue
*) override
{}
785 void on_liveness_change (const svalue_set
&,
786 const region_model
*) override
{}
787 logger
*get_logger () override
{ return NULL
; }
788 void on_condition (const svalue
*lhs ATTRIBUTE_UNUSED
,
789 enum tree_code op ATTRIBUTE_UNUSED
,
790 const svalue
*rhs ATTRIBUTE_UNUSED
) override
793 void on_bounded_ranges (const svalue
&,
794 const bounded_ranges
&) override
797 void on_pop_frame (const frame_region
*) override
{}
798 void on_unknown_change (const svalue
*sval ATTRIBUTE_UNUSED
,
799 bool is_mutable ATTRIBUTE_UNUSED
) override
802 void on_phi (const gphi
*phi ATTRIBUTE_UNUSED
,
803 tree rhs ATTRIBUTE_UNUSED
) override
806 void on_unexpected_tree_code (tree
, const dump_location_t
&) override
{}
808 void on_escaped_function (tree
) override
{}
810 uncertainty_t
*get_uncertainty () override
{ return NULL
; }
812 void purge_state_involving (const svalue
*sval ATTRIBUTE_UNUSED
) override
{}
814 void bifurcate (std::unique_ptr
<custom_edge_info
> info
) override
;
815 void terminate_path () override
;
817 const extrinsic_state
*get_ext_state () const override
{ return NULL
; }
819 bool get_state_map_by_name (const char *,
821 const state_machine
**,
827 const gimple
*get_stmt () const override
{ return NULL
; }
830 /* A subclass of region_model_context for determining if operations fail
831 e.g. "can we generate a region for the lvalue of EXPR?". */
833 class tentative_region_model_context
: public noop_region_model_context
836 tentative_region_model_context () : m_num_unexpected_codes (0) {}
838 void on_unexpected_tree_code (tree
, const dump_location_t
&)
841 m_num_unexpected_codes
++;
844 bool had_errors_p () const { return m_num_unexpected_codes
> 0; }
847 int m_num_unexpected_codes
;
850 /* Subclass of region_model_context that wraps another context, allowing
851 for extra code to be added to the various hooks. */
853 class region_model_context_decorator
: public region_model_context
856 bool warn (std::unique_ptr
<pending_diagnostic
> d
) override
858 return m_inner
->warn (std::move (d
));
861 void add_note (std::unique_ptr
<pending_note
> pn
) override
863 m_inner
->add_note (std::move (pn
));
866 void on_svalue_leak (const svalue
*sval
) override
868 m_inner
->on_svalue_leak (sval
);
871 void on_liveness_change (const svalue_set
&live_svalues
,
872 const region_model
*model
) override
874 m_inner
->on_liveness_change (live_svalues
, model
);
877 logger
*get_logger () override
879 return m_inner
->get_logger ();
882 void on_condition (const svalue
*lhs
,
884 const svalue
*rhs
) override
886 m_inner
->on_condition (lhs
, op
, rhs
);
889 void on_bounded_ranges (const svalue
&sval
,
890 const bounded_ranges
&ranges
) override
892 m_inner
->on_bounded_ranges (sval
, ranges
);
895 void on_pop_frame (const frame_region
*frame_reg
) override
897 m_inner
->on_pop_frame (frame_reg
);
900 void on_unknown_change (const svalue
*sval
, bool is_mutable
) override
902 m_inner
->on_unknown_change (sval
, is_mutable
);
905 void on_phi (const gphi
*phi
, tree rhs
) override
907 m_inner
->on_phi (phi
, rhs
);
910 void on_unexpected_tree_code (tree t
,
911 const dump_location_t
&loc
) override
913 m_inner
->on_unexpected_tree_code (t
, loc
);
916 void on_escaped_function (tree fndecl
) override
918 m_inner
->on_escaped_function (fndecl
);
921 uncertainty_t
*get_uncertainty () override
923 return m_inner
->get_uncertainty ();
926 void purge_state_involving (const svalue
*sval
) override
928 m_inner
->purge_state_involving (sval
);
931 void bifurcate (std::unique_ptr
<custom_edge_info
> info
) override
933 m_inner
->bifurcate (std::move (info
));
936 void terminate_path () override
938 m_inner
->terminate_path ();
941 const extrinsic_state
*get_ext_state () const override
943 return m_inner
->get_ext_state ();
946 bool get_state_map_by_name (const char *name
,
947 sm_state_map
**out_smap
,
948 const state_machine
**out_sm
,
949 unsigned *out_sm_idx
) override
951 return m_inner
->get_state_map_by_name (name
, out_smap
, out_sm
, out_sm_idx
);
954 const gimple
*get_stmt () const override
956 return m_inner
->get_stmt ();
960 region_model_context_decorator (region_model_context
*inner
)
963 gcc_assert (m_inner
);
966 region_model_context
*m_inner
;
969 /* Subclass of region_model_context_decorator that adds a note
970 when saving diagnostics. */
972 class note_adding_context
: public region_model_context_decorator
975 bool warn (std::unique_ptr
<pending_diagnostic
> d
) override
977 if (m_inner
->warn (std::move (d
)))
979 add_note (make_note ());
986 /* Hook to make the new note. */
987 virtual std::unique_ptr
<pending_note
> make_note () = 0;
990 note_adding_context (region_model_context
*inner
)
991 : region_model_context_decorator (inner
)
996 /* A bundle of data for use when attempting to merge two region_model
997 instances to make a third. */
1001 model_merger (const region_model
*model_a
,
1002 const region_model
*model_b
,
1003 const program_point
&point
,
1004 region_model
*merged_model
,
1005 const extrinsic_state
*ext_state
,
1006 const program_state
*state_a
,
1007 const program_state
*state_b
)
1008 : m_model_a (model_a
), m_model_b (model_b
),
1010 m_merged_model (merged_model
),
1011 m_ext_state (ext_state
),
1012 m_state_a (state_a
), m_state_b (state_b
)
1016 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
1017 void dump (FILE *fp
, bool simple
) const;
1018 void dump (bool simple
) const;
1020 region_model_manager
*get_manager () const
1022 return m_model_a
->get_manager ();
1025 bool mergeable_svalue_p (const svalue
*) const;
1026 const function_point
&get_function_point () const
1028 return m_point
.get_function_point ();
1031 const region_model
*m_model_a
;
1032 const region_model
*m_model_b
;
1033 const program_point
&m_point
;
1034 region_model
*m_merged_model
;
1036 const extrinsic_state
*m_ext_state
;
1037 const program_state
*m_state_a
;
1038 const program_state
*m_state_b
;
1041 /* A record that can (optionally) be written out when
1042 region_model::add_constraint fails. */
1044 class rejected_constraint
1047 virtual ~rejected_constraint () {}
1048 virtual void dump_to_pp (pretty_printer
*pp
) const = 0;
1050 const region_model
&get_model () const { return m_model
; }
1053 rejected_constraint (const region_model
&model
)
1057 region_model m_model
;
1060 class rejected_op_constraint
: public rejected_constraint
1063 rejected_op_constraint (const region_model
&model
,
1064 tree lhs
, enum tree_code op
, tree rhs
)
1065 : rejected_constraint (model
),
1066 m_lhs (lhs
), m_op (op
), m_rhs (rhs
)
1069 void dump_to_pp (pretty_printer
*pp
) const final override
;
1072 enum tree_code m_op
;
1076 class rejected_ranges_constraint
: public rejected_constraint
1079 rejected_ranges_constraint (const region_model
&model
,
1080 tree expr
, const bounded_ranges
*ranges
)
1081 : rejected_constraint (model
),
1082 m_expr (expr
), m_ranges (ranges
)
1085 void dump_to_pp (pretty_printer
*pp
) const final override
;
1089 const bounded_ranges
*m_ranges
;
1092 /* A bundle of state. */
1097 engine (const supergraph
*sg
= NULL
, logger
*logger
= NULL
);
1098 const supergraph
*get_supergraph () { return m_sg
; }
1099 region_model_manager
*get_model_manager () { return &m_mgr
; }
1100 known_function_manager
*get_known_function_manager ()
1102 return m_mgr
.get_known_function_manager ();
1105 void log_stats (logger
*logger
) const;
1108 const supergraph
*m_sg
;
1109 region_model_manager m_mgr
;
1114 extern void debug (const region_model
&rmodel
);
1120 namespace selftest
{
1122 using namespace ::selftest
;
1124 /* An implementation of region_model_context for use in selftests, which
1125 stores any pending_diagnostic instances passed to it. */
1127 class test_region_model_context
: public noop_region_model_context
1130 bool warn (std::unique_ptr
<pending_diagnostic
> d
) final override
1132 m_diagnostics
.safe_push (d
.release ());
1136 unsigned get_num_diagnostics () const { return m_diagnostics
.length (); }
1138 void on_unexpected_tree_code (tree t
, const dump_location_t
&)
1141 internal_error ("unhandled tree code: %qs",
1142 get_tree_code_name (TREE_CODE (t
)));
1146 /* Implicitly delete any diagnostics in the dtor. */
1147 auto_delete_vec
<pending_diagnostic
> m_diagnostics
;
1150 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1151 Verify that MODEL remains satisfiable. */
1153 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1154 SELFTEST_BEGIN_STMT \
1155 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1156 ASSERT_TRUE (sat); \
1159 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1160 Verify that the result is not satisfiable. */
1162 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1163 SELFTEST_BEGIN_STMT \
1164 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1165 ASSERT_FALSE (sat); \
1168 /* Implementation detail of the ASSERT_CONDITION_* macros. */
1170 void assert_condition (const location
&loc
,
1171 region_model
&model
,
1172 const svalue
*lhs
, tree_code op
, const svalue
*rhs
,
1175 void assert_condition (const location
&loc
,
1176 region_model
&model
,
1177 tree lhs
, tree_code op
, tree rhs
,
1180 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1183 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1184 SELFTEST_BEGIN_STMT \
1185 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1186 tristate (tristate::TS_TRUE)); \
1189 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1192 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1193 SELFTEST_BEGIN_STMT \
1194 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1195 tristate (tristate::TS_FALSE)); \
1198 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1201 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1202 SELFTEST_BEGIN_STMT \
1203 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1204 tristate (tristate::TS_UNKNOWN)); \
1207 } /* end of namespace selftest. */
1209 #endif /* #if CHECKING_P */
1213 #endif /* GCC_ANALYZER_REGION_MODEL_H */