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"
39 extern void add_path_var (path_var pv
, hash
&hstate
);
40 } // namespace inchash
48 one_way_id_map (int num_ids
);
49 void put (T src
, T dst
);
50 T
get_dst_for_src (T src
) const;
51 void dump_to_pp (pretty_printer
*pp
) const;
53 void update (T
*) const;
56 auto_vec
<T
> m_src_to_dst
;
59 /* class one_way_id_map. */
61 /* one_way_id_map's ctor, which populates the map with dummy null values. */
64 inline one_way_id_map
<T
>::one_way_id_map (int num_svalues
)
65 : m_src_to_dst (num_svalues
)
67 for (int i
= 0; i
< num_svalues
; i
++)
68 m_src_to_dst
.quick_push (T::null ());
71 /* Record that SRC is to be mapped to DST. */
75 one_way_id_map
<T
>::put (T src
, T dst
)
77 m_src_to_dst
[src
.as_int ()] = dst
;
80 /* Get the new value for SRC within the map. */
84 one_way_id_map
<T
>::get_dst_for_src (T src
) const
88 return m_src_to_dst
[src
.as_int ()];
91 /* Dump this map to PP. */
95 one_way_id_map
<T
>::dump_to_pp (pretty_printer
*pp
) const
97 pp_string (pp
, "src to dst: {");
100 FOR_EACH_VEC_ELT (m_src_to_dst
, i
, dst
)
103 pp_string (pp
, ", ");
104 T
src (T::from_int (i
));
106 pp_string (pp
, " -> ");
113 /* Dump this map to stderr. */
115 template <typename T
>
116 DEBUG_FUNCTION
inline void
117 one_way_id_map
<T
>::dump () const
120 pp
.buffer
->stream
= stderr
;
125 /* Update *ID from the old value to its new value in this map. */
127 template <typename T
>
129 one_way_id_map
<T
>::update (T
*id
) const
131 *id
= get_dst_for_src (*id
);
134 /* A mapping from region to svalue for use when tracking state. */
136 class region_to_value_map
139 typedef hash_map
<const region
*, const svalue
*> hash_map_t
;
140 typedef hash_map_t::iterator iterator
;
142 region_to_value_map () : m_hash_map () {}
143 region_to_value_map (const region_to_value_map
&other
)
144 : m_hash_map (other
.m_hash_map
) {}
145 region_to_value_map
&operator= (const region_to_value_map
&other
);
147 bool operator== (const region_to_value_map
&other
) const;
148 bool operator!= (const region_to_value_map
&other
) const
150 return !(*this == other
);
153 iterator
begin () const { return m_hash_map
.begin (); }
154 iterator
end () const { return m_hash_map
.end (); }
156 const svalue
* const *get (const region
*reg
) const
158 return const_cast <hash_map_t
&> (m_hash_map
).get (reg
);
160 void put (const region
*reg
, const svalue
*sval
)
162 m_hash_map
.put (reg
, sval
);
164 void remove (const region
*reg
)
166 m_hash_map
.remove (reg
);
169 bool is_empty () const { return m_hash_map
.is_empty (); }
171 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
172 void dump (bool simple
) const;
174 bool can_merge_with_p (const region_to_value_map
&other
,
175 region_to_value_map
*out
) const;
177 void purge_state_involving (const svalue
*sval
);
180 hash_map_t m_hash_map
;
183 /* Various operations delete information from a region_model.
185 This struct tracks how many of each kind of entity were purged (e.g.
186 for selftests, and for debugging). */
193 m_num_equiv_classes (0),
194 m_num_constraints (0),
195 m_num_bounded_ranges_constraints (0),
196 m_num_client_items (0)
201 int m_num_equiv_classes
;
202 int m_num_constraints
;
203 int m_num_bounded_ranges_constraints
;
204 int m_num_client_items
;
207 /* A base class for visiting regions and svalues, with do-nothing
208 base implementations of the per-subclass vfuncs. */
213 virtual void visit_region_svalue (const region_svalue
*) {}
214 virtual void visit_constant_svalue (const constant_svalue
*) {}
215 virtual void visit_unknown_svalue (const unknown_svalue
*) {}
216 virtual void visit_poisoned_svalue (const poisoned_svalue
*) {}
217 virtual void visit_setjmp_svalue (const setjmp_svalue
*) {}
218 virtual void visit_initial_svalue (const initial_svalue
*) {}
219 virtual void visit_unaryop_svalue (const unaryop_svalue
*) {}
220 virtual void visit_binop_svalue (const binop_svalue
*) {}
221 virtual void visit_sub_svalue (const sub_svalue
*) {}
222 virtual void visit_repeated_svalue (const repeated_svalue
*) {}
223 virtual void visit_bits_within_svalue (const bits_within_svalue
*) {}
224 virtual void visit_unmergeable_svalue (const unmergeable_svalue
*) {}
225 virtual void visit_placeholder_svalue (const placeholder_svalue
*) {}
226 virtual void visit_widening_svalue (const widening_svalue
*) {}
227 virtual void visit_compound_svalue (const compound_svalue
*) {}
228 virtual void visit_conjured_svalue (const conjured_svalue
*) {}
229 virtual void visit_asm_output_svalue (const asm_output_svalue
*) {}
230 virtual void visit_const_fn_result_svalue (const const_fn_result_svalue
*) {}
232 virtual void visit_region (const region
*) {}
235 struct append_regions_cb_data
;
237 /* Helper class for handling calls to functions with known behavior.
238 Implemented in region-model-impl-calls.c. */
243 call_details (const gcall
*call
, region_model
*model
,
244 region_model_context
*ctxt
);
246 region_model
*get_model () const { return m_model
; }
247 region_model_manager
*get_manager () const;
248 region_model_context
*get_ctxt () const { return m_ctxt
; }
249 logger
*get_logger () const;
251 uncertainty_t
*get_uncertainty () const;
252 tree
get_lhs_type () const { return m_lhs_type
; }
253 const region
*get_lhs_region () const { return m_lhs_region
; }
255 bool maybe_set_lhs (const svalue
*result
) const;
257 unsigned num_args () const;
259 const gcall
*get_call_stmt () const { return m_call
; }
261 tree
get_arg_tree (unsigned idx
) const;
262 tree
get_arg_type (unsigned idx
) const;
263 const svalue
*get_arg_svalue (unsigned idx
) const;
264 const char *get_arg_string_literal (unsigned idx
) const;
266 tree
get_fndecl_for_call () const;
268 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
269 void dump (bool simple
) const;
271 const svalue
*get_or_create_conjured_svalue (const region
*) const;
275 region_model
*m_model
;
276 region_model_context
*m_ctxt
;
278 const region
*m_lhs_region
;
281 /* A region_model encapsulates a representation of the state of memory, with
282 a tree of regions, along with their associated values.
283 The representation is graph-like because values can be pointers to
286 - a constraint_manager, capturing relationships between the values, and
287 - dynamic extents, mapping dynamically-allocated regions to svalues (their
293 typedef region_to_value_map dynamic_extents_t
;
295 region_model (region_model_manager
*mgr
);
296 region_model (const region_model
&other
);
298 region_model
&operator= (const region_model
&other
);
300 bool operator== (const region_model
&other
) const;
301 bool operator!= (const region_model
&other
) const
303 return !(*this == other
);
306 hashval_t
hash () const;
308 void print (pretty_printer
*pp
) const;
310 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
311 void dump (FILE *fp
, bool simple
, bool multiline
) const;
312 void dump (bool simple
) const;
316 void validate () const;
318 void canonicalize ();
319 bool canonicalized_p () const;
322 on_stmt_pre (const gimple
*stmt
,
323 bool *out_terminate_path
,
324 bool *out_unknown_side_effects
,
325 region_model_context
*ctxt
);
327 void on_assignment (const gassign
*stmt
, region_model_context
*ctxt
);
328 const svalue
*get_gassign_result (const gassign
*assign
,
329 region_model_context
*ctxt
);
330 void on_asm_stmt (const gasm
*asm_stmt
, region_model_context
*ctxt
);
331 bool on_call_pre (const gcall
*stmt
, region_model_context
*ctxt
,
332 bool *out_terminate_path
);
333 void on_call_post (const gcall
*stmt
,
334 bool unknown_side_effects
,
335 region_model_context
*ctxt
);
337 void purge_state_involving (const svalue
*sval
, region_model_context
*ctxt
);
339 /* Specific handling for on_call_pre. */
340 void impl_call_alloca (const call_details
&cd
);
341 void impl_call_analyzer_describe (const gcall
*call
,
342 region_model_context
*ctxt
);
343 void impl_call_analyzer_dump_capacity (const gcall
*call
,
344 region_model_context
*ctxt
);
345 void impl_call_analyzer_dump_escaped (const gcall
*call
);
346 void impl_call_analyzer_eval (const gcall
*call
,
347 region_model_context
*ctxt
);
348 void impl_call_analyzer_get_unknown_ptr (const call_details
&cd
);
349 void impl_call_builtin_expect (const call_details
&cd
);
350 void impl_call_calloc (const call_details
&cd
);
351 bool impl_call_error (const call_details
&cd
, unsigned min_args
,
352 bool *out_terminate_path
);
353 void impl_call_fgets (const call_details
&cd
);
354 void impl_call_fread (const call_details
&cd
);
355 void impl_call_free (const call_details
&cd
);
356 void impl_call_malloc (const call_details
&cd
);
357 void impl_call_memcpy (const call_details
&cd
);
358 void impl_call_memset (const call_details
&cd
);
359 void impl_call_putenv (const call_details
&cd
);
360 void impl_call_realloc (const call_details
&cd
);
361 void impl_call_strchr (const call_details
&cd
);
362 void impl_call_strcpy (const call_details
&cd
);
363 void impl_call_strlen (const call_details
&cd
);
364 void impl_call_operator_new (const call_details
&cd
);
365 void impl_call_operator_delete (const call_details
&cd
);
366 void impl_deallocation_call (const call_details
&cd
);
368 /* Implemented in varargs.cc. */
369 void impl_call_va_start (const call_details
&cd
);
370 void impl_call_va_copy (const call_details
&cd
);
371 void impl_call_va_arg (const call_details
&cd
);
372 void impl_call_va_end (const call_details
&cd
);
374 const svalue
*maybe_get_copy_bounds (const region
*src_reg
,
375 const svalue
*num_bytes_sval
);
376 void update_for_zero_return (const call_details
&cd
,
378 void update_for_nonzero_return (const call_details
&cd
);
380 void handle_unrecognized_call (const gcall
*call
,
381 region_model_context
*ctxt
);
382 void get_reachable_svalues (svalue_set
*out
,
383 const svalue
*extra_sval
,
384 const uncertainty_t
*uncertainty
);
386 void on_return (const greturn
*stmt
, region_model_context
*ctxt
);
387 void on_setjmp (const gcall
*stmt
, const exploded_node
*enode
,
388 region_model_context
*ctxt
);
389 void on_longjmp (const gcall
*longjmp_call
, const gcall
*setjmp_call
,
390 int setjmp_stack_depth
, region_model_context
*ctxt
);
392 void update_for_phis (const supernode
*snode
,
393 const cfg_superedge
*last_cfg_superedge
,
394 region_model_context
*ctxt
);
396 void handle_phi (const gphi
*phi
, tree lhs
, tree rhs
,
397 const region_model
&old_state
,
398 region_model_context
*ctxt
);
400 bool maybe_update_for_edge (const superedge
&edge
,
401 const gimple
*last_stmt
,
402 region_model_context
*ctxt
,
403 rejected_constraint
**out
);
405 void update_for_gcall (const gcall
*call_stmt
,
406 region_model_context
*ctxt
,
407 function
*callee
= NULL
);
409 void update_for_return_gcall (const gcall
*call_stmt
,
410 region_model_context
*ctxt
);
412 const region
*push_frame (function
*fun
, const vec
<const svalue
*> *arg_sids
,
413 region_model_context
*ctxt
);
414 const frame_region
*get_current_frame () const { return m_current_frame
; }
415 function
* get_current_function () const;
416 void pop_frame (tree result_lvalue
,
417 const svalue
**out_result
,
418 region_model_context
*ctxt
);
419 int get_stack_depth () const;
420 const frame_region
*get_frame_at_index (int index
) const;
422 const region
*get_lvalue (path_var pv
, region_model_context
*ctxt
) const;
423 const region
*get_lvalue (tree expr
, region_model_context
*ctxt
) const;
424 const svalue
*get_rvalue (path_var pv
, region_model_context
*ctxt
) const;
425 const svalue
*get_rvalue (tree expr
, region_model_context
*ctxt
) const;
427 const region
*deref_rvalue (const svalue
*ptr_sval
, tree ptr_tree
,
428 region_model_context
*ctxt
) const;
430 const svalue
*get_rvalue_for_bits (tree type
,
432 const bit_range
&bits
,
433 region_model_context
*ctxt
) const;
435 void set_value (const region
*lhs_reg
, const svalue
*rhs_sval
,
436 region_model_context
*ctxt
);
437 void set_value (tree lhs
, tree rhs
, region_model_context
*ctxt
);
438 void clobber_region (const region
*reg
);
439 void purge_region (const region
*reg
);
440 void fill_region (const region
*reg
, const svalue
*sval
);
441 void zero_fill_region (const region
*reg
);
442 void mark_region_as_unknown (const region
*reg
, uncertainty_t
*uncertainty
);
444 tristate
eval_condition (const svalue
*lhs
,
446 const svalue
*rhs
) const;
447 tristate
eval_condition_without_cm (const svalue
*lhs
,
449 const svalue
*rhs
) const;
450 tristate
compare_initial_and_pointer (const initial_svalue
*init
,
451 const region_svalue
*ptr
) const;
452 tristate
symbolic_greater_than (const binop_svalue
*a
,
453 const svalue
*b
) const;
454 tristate
structural_equality (const svalue
*a
, const svalue
*b
) const;
455 tristate
eval_condition (tree lhs
,
458 region_model_context
*ctxt
);
459 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
460 region_model_context
*ctxt
);
461 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
462 region_model_context
*ctxt
,
463 rejected_constraint
**out
);
465 const region
*create_region_for_heap_alloc (const svalue
*size_in_bytes
,
466 region_model_context
*ctxt
);
467 const region
*create_region_for_alloca (const svalue
*size_in_bytes
,
468 region_model_context
*ctxt
);
470 tree
get_representative_tree (const svalue
*sval
) const;
471 tree
get_representative_tree (const region
*reg
) const;
473 get_representative_path_var (const svalue
*sval
,
474 svalue_set
*visited
) const;
476 get_representative_path_var (const region
*reg
,
477 svalue_set
*visited
) const;
480 constraint_manager
*get_constraints ()
482 return m_constraints
;
485 store
*get_store () { return &m_store
; }
486 const store
*get_store () const { return &m_store
; }
488 const dynamic_extents_t
&
489 get_dynamic_extents () const
491 return m_dynamic_extents
;
493 const svalue
*get_dynamic_extents (const region
*reg
) const;
494 void set_dynamic_extents (const region
*reg
,
495 const svalue
*size_in_bytes
,
496 region_model_context
*ctxt
);
497 void unset_dynamic_extents (const region
*reg
);
499 region_model_manager
*get_manager () const { return m_mgr
; }
500 bounded_ranges_manager
*get_range_manager () const
502 return m_mgr
->get_range_manager ();
505 void unbind_region_and_descendents (const region
*reg
,
506 enum poison_kind pkind
);
508 bool can_merge_with_p (const region_model
&other_model
,
509 const program_point
&point
,
510 region_model
*out_model
,
511 const extrinsic_state
*ext_state
= NULL
,
512 const program_state
*state_a
= NULL
,
513 const program_state
*state_b
= NULL
) const;
515 tree
get_fndecl_for_call (const gcall
*call
,
516 region_model_context
*ctxt
);
518 void get_regions_for_current_frame (auto_vec
<const decl_region
*> *out
) const;
519 static void append_regions_cb (const region
*base_reg
,
520 struct append_regions_cb_data
*data
);
522 const svalue
*get_store_value (const region
*reg
,
523 region_model_context
*ctxt
) const;
525 bool region_exists_p (const region
*reg
) const;
527 void loop_replay_fixup (const region_model
*dst_state
);
529 const svalue
*get_capacity (const region
*reg
) const;
531 const svalue
*get_string_size (const svalue
*sval
) const;
532 const svalue
*get_string_size (const region
*reg
) const;
534 bool replay_call_summary (call_summary_replay
&r
,
535 const region_model
&summary
);
537 void maybe_complain_about_infoleak (const region
*dst_reg
,
538 const svalue
*copied_sval
,
539 const region
*src_reg
,
540 region_model_context
*ctxt
);
542 /* Implemented in sm-malloc.cc */
543 void on_realloc_with_move (const call_details
&cd
,
544 const svalue
*old_ptr_sval
,
545 const svalue
*new_ptr_sval
);
547 /* Implemented in sm-taint.cc. */
548 void mark_as_tainted (const svalue
*sval
,
549 region_model_context
*ctxt
);
552 const region
*get_lvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
553 const svalue
*get_rvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
556 get_representative_path_var_1 (const svalue
*sval
,
557 svalue_set
*visited
) const;
559 get_representative_path_var_1 (const region
*reg
,
560 svalue_set
*visited
) const;
562 const known_function
*get_known_function (tree fndecl
) const;
564 bool add_constraint (const svalue
*lhs
,
567 region_model_context
*ctxt
);
568 bool add_constraints_from_binop (const svalue
*outer_lhs
,
569 enum tree_code outer_op
,
570 const svalue
*outer_rhs
,
572 region_model_context
*ctxt
);
574 void update_for_call_superedge (const call_superedge
&call_edge
,
575 region_model_context
*ctxt
);
576 void update_for_return_superedge (const return_superedge
&return_edge
,
577 region_model_context
*ctxt
);
578 bool apply_constraints_for_gcond (const cfg_superedge
&edge
,
579 const gcond
*cond_stmt
,
580 region_model_context
*ctxt
,
581 rejected_constraint
**out
);
582 bool apply_constraints_for_gswitch (const switch_cfg_superedge
&edge
,
583 const gswitch
*switch_stmt
,
584 region_model_context
*ctxt
,
585 rejected_constraint
**out
);
586 bool apply_constraints_for_exception (const gimple
*last_stmt
,
587 region_model_context
*ctxt
,
588 rejected_constraint
**out
);
590 int poison_any_pointers_to_descendents (const region
*reg
,
591 enum poison_kind pkind
);
593 void on_top_level_param (tree param
, region_model_context
*ctxt
);
595 bool called_from_main_p () const;
596 const svalue
*get_initial_value_for_global (const region
*reg
) const;
598 const svalue
*check_for_poison (const svalue
*sval
,
600 region_model_context
*ctxt
) const;
601 const region
* get_region_for_poisoned_expr (tree expr
) const;
603 void check_dynamic_size_for_taint (enum memory_space mem_space
,
604 const svalue
*size_in_bytes
,
605 region_model_context
*ctxt
) const;
606 void check_dynamic_size_for_floats (const svalue
*size_in_bytes
,
607 region_model_context
*ctxt
) const;
609 void check_region_for_taint (const region
*reg
,
610 enum access_direction dir
,
611 region_model_context
*ctxt
) const;
613 void check_for_writable_region (const region
* dest_reg
,
614 region_model_context
*ctxt
) const;
615 void check_region_access (const region
*reg
,
616 enum access_direction dir
,
617 region_model_context
*ctxt
) const;
618 void check_region_for_write (const region
*dest_reg
,
619 region_model_context
*ctxt
) const;
620 void check_region_for_read (const region
*src_reg
,
621 region_model_context
*ctxt
) const;
622 void check_region_size (const region
*lhs_reg
, const svalue
*rhs_sval
,
623 region_model_context
*ctxt
) const;
624 void check_symbolic_bounds (const region
*base_reg
,
625 const svalue
*sym_byte_offset
,
626 const svalue
*num_bytes_sval
,
627 const svalue
*capacity
,
628 enum access_direction dir
,
629 region_model_context
*ctxt
) const;
630 void check_region_bounds (const region
*reg
, enum access_direction dir
,
631 region_model_context
*ctxt
) const;
633 void check_call_args (const call_details
&cd
) const;
634 void check_external_function_for_access_attr (const gcall
*call
,
636 region_model_context
*ctxt
) const;
638 /* Storing this here to avoid passing it around everywhere. */
639 region_model_manager
*const m_mgr
;
643 constraint_manager
*m_constraints
; // TODO: embed, rather than dynalloc?
645 const frame_region
*m_current_frame
;
647 /* Map from base region to size in bytes, for tracking the sizes of
648 dynamically-allocated regions.
649 This is part of the region_model rather than the region to allow for
650 memory regions to be resized (e.g. by realloc). */
651 dynamic_extents_t m_dynamic_extents
;
654 /* Some region_model activity could lead to warnings (e.g. attempts to use an
655 uninitialized value). This abstract base class encapsulates an interface
656 for the region model to use when emitting such warnings.
658 Having this as an abstract base class allows us to support the various
659 operations needed by program_state in the analyzer within region_model,
660 whilst keeping them somewhat modularized. */
662 class region_model_context
665 /* Hook for clients to store pending diagnostics.
666 Return true if the diagnostic was stored, or false if it was deleted. */
667 virtual bool warn (pending_diagnostic
*d
) = 0;
669 /* Hook for clients to add a note to the last previously stored pending diagnostic.
670 Takes ownership of the pending_node (or deletes it). */
671 virtual void add_note (pending_note
*pn
) = 0;
673 /* Hook for clients to be notified when an SVAL that was reachable
674 in a previous state is no longer live, so that clients can emit warnings
676 virtual void on_svalue_leak (const svalue
*sval
) = 0;
678 /* Hook for clients to be notified when the set of explicitly live
679 svalues changes, so that they can purge state relating to dead
681 virtual void on_liveness_change (const svalue_set
&live_svalues
,
682 const region_model
*model
) = 0;
684 virtual logger
*get_logger () = 0;
686 /* Hook for clients to be notified when the condition
687 "LHS OP RHS" is added to the region model.
688 This exists so that state machines can detect tests on edges,
689 and use them to trigger sm-state transitions (e.g. transitions due
690 to ptrs becoming known to be NULL or non-NULL, rather than just
692 virtual void on_condition (const svalue
*lhs
,
694 const svalue
*rhs
) = 0;
696 /* Hook for clients to be notified when the condition that
697 SVAL is within RANGES is added to the region model.
698 Similar to on_condition, but for use when handling switch statements.
699 RANGES is non-empty. */
700 virtual void on_bounded_ranges (const svalue
&sval
,
701 const bounded_ranges
&ranges
) = 0;
703 /* Hooks for clients to be notified when an unknown change happens
704 to SVAL (in response to a call to an unknown function). */
705 virtual void on_unknown_change (const svalue
*sval
, bool is_mutable
) = 0;
707 /* Hooks for clients to be notified when a phi node is handled,
708 where RHS is the pertinent argument. */
709 virtual void on_phi (const gphi
*phi
, tree rhs
) = 0;
711 /* Hooks for clients to be notified when the region model doesn't
712 know how to handle the tree code of T at LOC. */
713 virtual void on_unexpected_tree_code (tree t
,
714 const dump_location_t
&loc
) = 0;
716 /* Hook for clients to be notified when a function_decl escapes. */
717 virtual void on_escaped_function (tree fndecl
) = 0;
719 virtual uncertainty_t
*get_uncertainty () = 0;
721 /* Hook for clients to purge state involving SVAL. */
722 virtual void purge_state_involving (const svalue
*sval
) = 0;
724 /* Hook for clients to split state with a non-standard path.
725 Take ownership of INFO. */
726 virtual void bifurcate (custom_edge_info
*info
) = 0;
728 /* Hook for clients to terminate the standard path. */
729 virtual void terminate_path () = 0;
731 virtual const extrinsic_state
*get_ext_state () const = 0;
733 /* Hook for clients to access the "malloc" state machine in
734 any underlying program_state. */
735 virtual bool get_malloc_map (sm_state_map
**out_smap
,
736 const state_machine
**out_sm
,
737 unsigned *out_sm_idx
) = 0;
738 /* Likewise for the "taint" state machine. */
739 virtual bool get_taint_map (sm_state_map
**out_smap
,
740 const state_machine
**out_sm
,
741 unsigned *out_sm_idx
) = 0;
743 /* Get the current statement, if any. */
744 virtual const gimple
*get_stmt () const = 0;
747 /* A "do nothing" subclass of region_model_context. */
749 class noop_region_model_context
: public region_model_context
752 bool warn (pending_diagnostic
*) override
{ return false; }
753 void add_note (pending_note
*pn
) override
;
754 void on_svalue_leak (const svalue
*) override
{}
755 void on_liveness_change (const svalue_set
&,
756 const region_model
*) override
{}
757 logger
*get_logger () override
{ return NULL
; }
758 void on_condition (const svalue
*lhs ATTRIBUTE_UNUSED
,
759 enum tree_code op ATTRIBUTE_UNUSED
,
760 const svalue
*rhs ATTRIBUTE_UNUSED
) override
763 void on_bounded_ranges (const svalue
&,
764 const bounded_ranges
&) override
767 void on_unknown_change (const svalue
*sval ATTRIBUTE_UNUSED
,
768 bool is_mutable ATTRIBUTE_UNUSED
) override
771 void on_phi (const gphi
*phi ATTRIBUTE_UNUSED
,
772 tree rhs ATTRIBUTE_UNUSED
) override
775 void on_unexpected_tree_code (tree
, const dump_location_t
&) override
{}
777 void on_escaped_function (tree
) override
{}
779 uncertainty_t
*get_uncertainty () override
{ return NULL
; }
781 void purge_state_involving (const svalue
*sval ATTRIBUTE_UNUSED
) override
{}
783 void bifurcate (custom_edge_info
*info
) override
;
784 void terminate_path () override
;
786 const extrinsic_state
*get_ext_state () const override
{ return NULL
; }
788 bool get_malloc_map (sm_state_map
**,
789 const state_machine
**,
794 bool get_taint_map (sm_state_map
**,
795 const state_machine
**,
801 const gimple
*get_stmt () const override
{ return NULL
; }
804 /* A subclass of region_model_context for determining if operations fail
805 e.g. "can we generate a region for the lvalue of EXPR?". */
807 class tentative_region_model_context
: public noop_region_model_context
810 tentative_region_model_context () : m_num_unexpected_codes (0) {}
812 void on_unexpected_tree_code (tree
, const dump_location_t
&)
815 m_num_unexpected_codes
++;
818 bool had_errors_p () const { return m_num_unexpected_codes
> 0; }
821 int m_num_unexpected_codes
;
824 /* Subclass of region_model_context that wraps another context, allowing
825 for extra code to be added to the various hooks. */
827 class region_model_context_decorator
: public region_model_context
830 bool warn (pending_diagnostic
*d
) override
832 return m_inner
->warn (d
);
835 void add_note (pending_note
*pn
) override
837 m_inner
->add_note (pn
);
840 void on_svalue_leak (const svalue
*sval
) override
842 m_inner
->on_svalue_leak (sval
);
845 void on_liveness_change (const svalue_set
&live_svalues
,
846 const region_model
*model
) override
848 m_inner
->on_liveness_change (live_svalues
, model
);
851 logger
*get_logger () override
853 return m_inner
->get_logger ();
856 void on_condition (const svalue
*lhs
,
858 const svalue
*rhs
) override
860 m_inner
->on_condition (lhs
, op
, rhs
);
863 void on_bounded_ranges (const svalue
&sval
,
864 const bounded_ranges
&ranges
) override
866 m_inner
->on_bounded_ranges (sval
, ranges
);
869 void on_unknown_change (const svalue
*sval
, bool is_mutable
) override
871 m_inner
->on_unknown_change (sval
, is_mutable
);
874 void on_phi (const gphi
*phi
, tree rhs
) override
876 m_inner
->on_phi (phi
, rhs
);
879 void on_unexpected_tree_code (tree t
,
880 const dump_location_t
&loc
) override
882 m_inner
->on_unexpected_tree_code (t
, loc
);
885 void on_escaped_function (tree fndecl
) override
887 m_inner
->on_escaped_function (fndecl
);
890 uncertainty_t
*get_uncertainty () override
892 return m_inner
->get_uncertainty ();
895 void purge_state_involving (const svalue
*sval
) override
897 m_inner
->purge_state_involving (sval
);
900 void bifurcate (custom_edge_info
*info
) override
902 m_inner
->bifurcate (info
);
905 void terminate_path () override
907 m_inner
->terminate_path ();
910 const extrinsic_state
*get_ext_state () const override
912 return m_inner
->get_ext_state ();
915 bool get_malloc_map (sm_state_map
**out_smap
,
916 const state_machine
**out_sm
,
917 unsigned *out_sm_idx
) override
919 return m_inner
->get_malloc_map (out_smap
, out_sm
, out_sm_idx
);
922 bool get_taint_map (sm_state_map
**out_smap
,
923 const state_machine
**out_sm
,
924 unsigned *out_sm_idx
) override
926 return m_inner
->get_taint_map (out_smap
, out_sm
, out_sm_idx
);
929 const gimple
*get_stmt () const override
931 return m_inner
->get_stmt ();
935 region_model_context_decorator (region_model_context
*inner
)
938 gcc_assert (m_inner
);
941 region_model_context
*m_inner
;
944 /* Subclass of region_model_context_decorator that adds a note
945 when saving diagnostics. */
947 class note_adding_context
: public region_model_context_decorator
950 bool warn (pending_diagnostic
*d
) override
952 if (m_inner
->warn (d
))
954 add_note (make_note ());
961 /* Hook to make the new note. */
962 virtual pending_note
*make_note () = 0;
965 note_adding_context (region_model_context
*inner
)
966 : region_model_context_decorator (inner
)
971 /* A bundle of data for use when attempting to merge two region_model
972 instances to make a third. */
976 model_merger (const region_model
*model_a
,
977 const region_model
*model_b
,
978 const program_point
&point
,
979 region_model
*merged_model
,
980 const extrinsic_state
*ext_state
,
981 const program_state
*state_a
,
982 const program_state
*state_b
)
983 : m_model_a (model_a
), m_model_b (model_b
),
985 m_merged_model (merged_model
),
986 m_ext_state (ext_state
),
987 m_state_a (state_a
), m_state_b (state_b
)
991 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
992 void dump (FILE *fp
, bool simple
) const;
993 void dump (bool simple
) const;
995 region_model_manager
*get_manager () const
997 return m_model_a
->get_manager ();
1000 bool mergeable_svalue_p (const svalue
*) const;
1001 const function_point
&get_function_point () const
1003 return m_point
.get_function_point ();
1006 const region_model
*m_model_a
;
1007 const region_model
*m_model_b
;
1008 const program_point
&m_point
;
1009 region_model
*m_merged_model
;
1011 const extrinsic_state
*m_ext_state
;
1012 const program_state
*m_state_a
;
1013 const program_state
*m_state_b
;
1016 /* A record that can (optionally) be written out when
1017 region_model::add_constraint fails. */
1019 class rejected_constraint
1022 virtual ~rejected_constraint () {}
1023 virtual void dump_to_pp (pretty_printer
*pp
) const = 0;
1025 const region_model
&get_model () const { return m_model
; }
1028 rejected_constraint (const region_model
&model
)
1032 region_model m_model
;
1035 class rejected_op_constraint
: public rejected_constraint
1038 rejected_op_constraint (const region_model
&model
,
1039 tree lhs
, enum tree_code op
, tree rhs
)
1040 : rejected_constraint (model
),
1041 m_lhs (lhs
), m_op (op
), m_rhs (rhs
)
1044 void dump_to_pp (pretty_printer
*pp
) const final override
;
1047 enum tree_code m_op
;
1051 class rejected_ranges_constraint
: public rejected_constraint
1054 rejected_ranges_constraint (const region_model
&model
,
1055 tree expr
, const bounded_ranges
*ranges
)
1056 : rejected_constraint (model
),
1057 m_expr (expr
), m_ranges (ranges
)
1060 void dump_to_pp (pretty_printer
*pp
) const final override
;
1064 const bounded_ranges
*m_ranges
;
1067 /* A bundle of state. */
1072 engine (const supergraph
*sg
= NULL
, logger
*logger
= NULL
);
1073 const supergraph
*get_supergraph () { return m_sg
; }
1074 region_model_manager
*get_model_manager () { return &m_mgr
; }
1075 known_function_manager
*get_known_function_manager ()
1077 return m_mgr
.get_known_function_manager ();
1080 void log_stats (logger
*logger
) const;
1083 const supergraph
*m_sg
;
1084 region_model_manager m_mgr
;
1089 extern void debug (const region_model
&rmodel
);
1095 namespace selftest
{
1097 using namespace ::selftest
;
1099 /* An implementation of region_model_context for use in selftests, which
1100 stores any pending_diagnostic instances passed to it. */
1102 class test_region_model_context
: public noop_region_model_context
1105 bool warn (pending_diagnostic
*d
) final override
1107 m_diagnostics
.safe_push (d
);
1111 unsigned get_num_diagnostics () const { return m_diagnostics
.length (); }
1113 void on_unexpected_tree_code (tree t
, const dump_location_t
&)
1116 internal_error ("unhandled tree code: %qs",
1117 get_tree_code_name (TREE_CODE (t
)));
1121 /* Implicitly delete any diagnostics in the dtor. */
1122 auto_delete_vec
<pending_diagnostic
> m_diagnostics
;
1125 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1126 Verify that MODEL remains satisfiable. */
1128 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1129 SELFTEST_BEGIN_STMT \
1130 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1131 ASSERT_TRUE (sat); \
1134 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1135 Verify that the result is not satisfiable. */
1137 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1138 SELFTEST_BEGIN_STMT \
1139 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1140 ASSERT_FALSE (sat); \
1143 /* Implementation detail of the ASSERT_CONDITION_* macros. */
1145 void assert_condition (const location
&loc
,
1146 region_model
&model
,
1147 const svalue
*lhs
, tree_code op
, const svalue
*rhs
,
1150 void assert_condition (const location
&loc
,
1151 region_model
&model
,
1152 tree lhs
, tree_code op
, tree rhs
,
1155 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1158 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1159 SELFTEST_BEGIN_STMT \
1160 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1161 tristate (tristate::TS_TRUE)); \
1164 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1167 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1168 SELFTEST_BEGIN_STMT \
1169 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1170 tristate (tristate::TS_FALSE)); \
1173 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1176 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1177 SELFTEST_BEGIN_STMT \
1178 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1179 tristate (tristate::TS_UNKNOWN)); \
1182 } /* end of namespace selftest. */
1184 #endif /* #if CHECKING_P */
1188 #endif /* GCC_ANALYZER_REGION_MODEL_H */