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 */
31 #include "analyzer/svalue.h"
32 #include "analyzer/region.h"
33 #include "analyzer/known-function-manager.h"
34 #include "analyzer/region-model-manager.h"
35 #include "analyzer/pending-diagnostic.h"
41 extern void add_path_var (path_var pv
, hash
&hstate
);
42 } // namespace inchash
50 one_way_id_map (int num_ids
);
51 void put (T src
, T dst
);
52 T
get_dst_for_src (T src
) const;
53 void dump_to_pp (pretty_printer
*pp
) const;
55 void update (T
*) const;
58 auto_vec
<T
> m_src_to_dst
;
61 /* class one_way_id_map. */
63 /* one_way_id_map's ctor, which populates the map with dummy null values. */
66 inline one_way_id_map
<T
>::one_way_id_map (int num_svalues
)
67 : m_src_to_dst (num_svalues
)
69 for (int i
= 0; i
< num_svalues
; i
++)
70 m_src_to_dst
.quick_push (T::null ());
73 /* Record that SRC is to be mapped to DST. */
77 one_way_id_map
<T
>::put (T src
, T dst
)
79 m_src_to_dst
[src
.as_int ()] = dst
;
82 /* Get the new value for SRC within the map. */
86 one_way_id_map
<T
>::get_dst_for_src (T src
) const
90 return m_src_to_dst
[src
.as_int ()];
93 /* Dump this map to PP. */
97 one_way_id_map
<T
>::dump_to_pp (pretty_printer
*pp
) const
99 pp_string (pp
, "src to dst: {");
102 FOR_EACH_VEC_ELT (m_src_to_dst
, i
, dst
)
105 pp_string (pp
, ", ");
106 T
src (T::from_int (i
));
108 pp_string (pp
, " -> ");
115 /* Dump this map to stderr. */
117 template <typename T
>
118 DEBUG_FUNCTION
inline void
119 one_way_id_map
<T
>::dump () const
122 pp
.buffer
->stream
= stderr
;
127 /* Update *ID from the old value to its new value in this map. */
129 template <typename T
>
131 one_way_id_map
<T
>::update (T
*id
) const
133 *id
= get_dst_for_src (*id
);
136 /* A mapping from region to svalue for use when tracking state. */
138 class region_to_value_map
141 typedef hash_map
<const region
*, const svalue
*> hash_map_t
;
142 typedef hash_map_t::iterator iterator
;
144 region_to_value_map () : m_hash_map () {}
145 region_to_value_map (const region_to_value_map
&other
)
146 : m_hash_map (other
.m_hash_map
) {}
147 region_to_value_map
&operator= (const region_to_value_map
&other
);
149 bool operator== (const region_to_value_map
&other
) const;
150 bool operator!= (const region_to_value_map
&other
) const
152 return !(*this == other
);
155 iterator
begin () const { return m_hash_map
.begin (); }
156 iterator
end () const { return m_hash_map
.end (); }
158 const svalue
* const *get (const region
*reg
) const
160 return const_cast <hash_map_t
&> (m_hash_map
).get (reg
);
162 void put (const region
*reg
, const svalue
*sval
)
164 m_hash_map
.put (reg
, sval
);
166 void remove (const region
*reg
)
168 m_hash_map
.remove (reg
);
171 bool is_empty () const { return m_hash_map
.is_empty (); }
173 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
174 void dump (bool simple
) const;
176 bool can_merge_with_p (const region_to_value_map
&other
,
177 region_to_value_map
*out
) const;
179 void purge_state_involving (const svalue
*sval
);
182 hash_map_t m_hash_map
;
185 /* Various operations delete information from a region_model.
187 This struct tracks how many of each kind of entity were purged (e.g.
188 for selftests, and for debugging). */
195 m_num_equiv_classes (0),
196 m_num_constraints (0),
197 m_num_bounded_ranges_constraints (0),
198 m_num_client_items (0)
203 int m_num_equiv_classes
;
204 int m_num_constraints
;
205 int m_num_bounded_ranges_constraints
;
206 int m_num_client_items
;
209 /* A base class for visiting regions and svalues, with do-nothing
210 base implementations of the per-subclass vfuncs. */
215 virtual void visit_region_svalue (const region_svalue
*) {}
216 virtual void visit_constant_svalue (const constant_svalue
*) {}
217 virtual void visit_unknown_svalue (const unknown_svalue
*) {}
218 virtual void visit_poisoned_svalue (const poisoned_svalue
*) {}
219 virtual void visit_setjmp_svalue (const setjmp_svalue
*) {}
220 virtual void visit_initial_svalue (const initial_svalue
*) {}
221 virtual void visit_unaryop_svalue (const unaryop_svalue
*) {}
222 virtual void visit_binop_svalue (const binop_svalue
*) {}
223 virtual void visit_sub_svalue (const sub_svalue
*) {}
224 virtual void visit_repeated_svalue (const repeated_svalue
*) {}
225 virtual void visit_bits_within_svalue (const bits_within_svalue
*) {}
226 virtual void visit_unmergeable_svalue (const unmergeable_svalue
*) {}
227 virtual void visit_placeholder_svalue (const placeholder_svalue
*) {}
228 virtual void visit_widening_svalue (const widening_svalue
*) {}
229 virtual void visit_compound_svalue (const compound_svalue
*) {}
230 virtual void visit_conjured_svalue (const conjured_svalue
*) {}
231 virtual void visit_asm_output_svalue (const asm_output_svalue
*) {}
232 virtual void visit_const_fn_result_svalue (const const_fn_result_svalue
*) {}
234 virtual void visit_region (const region
*) {}
237 struct append_regions_cb_data
;
239 /* Helper class for handling calls to functions with known behavior.
240 Implemented in region-model-impl-calls.c. */
245 call_details (const gcall
*call
, region_model
*model
,
246 region_model_context
*ctxt
);
248 region_model
*get_model () const { return m_model
; }
249 region_model_manager
*get_manager () const;
250 region_model_context
*get_ctxt () const { return m_ctxt
; }
251 logger
*get_logger () const;
253 uncertainty_t
*get_uncertainty () const;
254 tree
get_lhs_type () const { return m_lhs_type
; }
255 const region
*get_lhs_region () const { return m_lhs_region
; }
257 bool maybe_set_lhs (const svalue
*result
) const;
259 unsigned num_args () const;
260 bool arg_is_pointer_p (unsigned idx
) const
262 return POINTER_TYPE_P (get_arg_type (idx
));
264 bool arg_is_size_p (unsigned idx
) const;
266 const gcall
*get_call_stmt () const { return m_call
; }
267 location_t
get_location () const;
269 tree
get_arg_tree (unsigned idx
) const;
270 tree
get_arg_type (unsigned idx
) const;
271 const svalue
*get_arg_svalue (unsigned idx
) const;
272 const char *get_arg_string_literal (unsigned idx
) const;
274 tree
get_fndecl_for_call () const;
276 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
277 void dump (bool simple
) const;
279 const svalue
*get_or_create_conjured_svalue (const region
*) const;
283 region_model
*m_model
;
284 region_model_context
*m_ctxt
;
286 const region
*m_lhs_region
;
289 /* A region_model encapsulates a representation of the state of memory, with
290 a tree of regions, along with their associated values.
291 The representation is graph-like because values can be pointers to
294 - a constraint_manager, capturing relationships between the values, and
295 - dynamic extents, mapping dynamically-allocated regions to svalues (their
301 typedef region_to_value_map dynamic_extents_t
;
303 region_model (region_model_manager
*mgr
);
304 region_model (const region_model
&other
);
306 region_model
&operator= (const region_model
&other
);
308 bool operator== (const region_model
&other
) const;
309 bool operator!= (const region_model
&other
) const
311 return !(*this == other
);
314 hashval_t
hash () const;
316 void print (pretty_printer
*pp
) const;
318 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
319 void dump (FILE *fp
, bool simple
, bool multiline
) const;
320 void dump (bool simple
) const;
324 void validate () const;
326 void canonicalize ();
327 bool canonicalized_p () const;
330 on_stmt_pre (const gimple
*stmt
,
331 bool *out_unknown_side_effects
,
332 region_model_context
*ctxt
);
334 void on_assignment (const gassign
*stmt
, region_model_context
*ctxt
);
335 const svalue
*get_gassign_result (const gassign
*assign
,
336 region_model_context
*ctxt
);
337 void on_asm_stmt (const gasm
*asm_stmt
, region_model_context
*ctxt
);
338 bool on_call_pre (const gcall
*stmt
, region_model_context
*ctxt
);
339 void on_call_post (const gcall
*stmt
,
340 bool unknown_side_effects
,
341 region_model_context
*ctxt
);
343 void purge_state_involving (const svalue
*sval
, region_model_context
*ctxt
);
345 void impl_deallocation_call (const call_details
&cd
);
347 const svalue
*maybe_get_copy_bounds (const region
*src_reg
,
348 const svalue
*num_bytes_sval
);
349 void update_for_int_cst_return (const call_details
&cd
,
352 void update_for_zero_return (const call_details
&cd
,
354 void update_for_nonzero_return (const call_details
&cd
);
356 void handle_unrecognized_call (const gcall
*call
,
357 region_model_context
*ctxt
);
358 void get_reachable_svalues (svalue_set
*out
,
359 const svalue
*extra_sval
,
360 const uncertainty_t
*uncertainty
);
362 void on_return (const greturn
*stmt
, region_model_context
*ctxt
);
363 void on_setjmp (const gcall
*stmt
, const exploded_node
*enode
,
364 region_model_context
*ctxt
);
365 void on_longjmp (const gcall
*longjmp_call
, const gcall
*setjmp_call
,
366 int setjmp_stack_depth
, region_model_context
*ctxt
);
368 void update_for_phis (const supernode
*snode
,
369 const cfg_superedge
*last_cfg_superedge
,
370 region_model_context
*ctxt
);
372 void handle_phi (const gphi
*phi
, tree lhs
, tree rhs
,
373 const region_model
&old_state
,
374 region_model_context
*ctxt
);
376 bool maybe_update_for_edge (const superedge
&edge
,
377 const gimple
*last_stmt
,
378 region_model_context
*ctxt
,
379 rejected_constraint
**out
);
381 void update_for_gcall (const gcall
*call_stmt
,
382 region_model_context
*ctxt
,
383 function
*callee
= NULL
);
385 void update_for_return_gcall (const gcall
*call_stmt
,
386 region_model_context
*ctxt
);
388 const region
*push_frame (function
*fun
, const vec
<const svalue
*> *arg_sids
,
389 region_model_context
*ctxt
);
390 const frame_region
*get_current_frame () const { return m_current_frame
; }
391 function
* get_current_function () const;
392 void pop_frame (tree result_lvalue
,
393 const svalue
**out_result
,
394 region_model_context
*ctxt
);
395 int get_stack_depth () const;
396 const frame_region
*get_frame_at_index (int index
) const;
398 const region
*get_lvalue (path_var pv
, region_model_context
*ctxt
) const;
399 const region
*get_lvalue (tree expr
, region_model_context
*ctxt
) const;
400 const svalue
*get_rvalue (path_var pv
, region_model_context
*ctxt
) const;
401 const svalue
*get_rvalue (tree expr
, region_model_context
*ctxt
) const;
403 const region
*deref_rvalue (const svalue
*ptr_sval
, tree ptr_tree
,
404 region_model_context
*ctxt
) const;
406 const svalue
*get_rvalue_for_bits (tree type
,
408 const bit_range
&bits
,
409 region_model_context
*ctxt
) const;
411 void set_value (const region
*lhs_reg
, const svalue
*rhs_sval
,
412 region_model_context
*ctxt
);
413 void set_value (tree lhs
, tree rhs
, region_model_context
*ctxt
);
414 void clobber_region (const region
*reg
);
415 void purge_region (const region
*reg
);
416 void fill_region (const region
*reg
, const svalue
*sval
);
417 void zero_fill_region (const region
*reg
);
418 void mark_region_as_unknown (const region
*reg
, uncertainty_t
*uncertainty
);
420 tristate
eval_condition (const svalue
*lhs
,
422 const svalue
*rhs
) const;
423 tristate
compare_initial_and_pointer (const initial_svalue
*init
,
424 const region_svalue
*ptr
) const;
425 tristate
symbolic_greater_than (const binop_svalue
*a
,
426 const svalue
*b
) const;
427 tristate
structural_equality (const svalue
*a
, const svalue
*b
) const;
428 tristate
eval_condition (tree lhs
,
431 region_model_context
*ctxt
) const;
432 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
433 region_model_context
*ctxt
);
434 bool add_constraint (tree lhs
, enum tree_code op
, tree rhs
,
435 region_model_context
*ctxt
,
436 rejected_constraint
**out
);
439 get_or_create_region_for_heap_alloc (const svalue
*size_in_bytes
,
440 region_model_context
*ctxt
);
441 const region
*create_region_for_alloca (const svalue
*size_in_bytes
,
442 region_model_context
*ctxt
);
443 void get_referenced_base_regions (auto_sbitmap
&out_ids
) const;
445 tree
get_representative_tree (const svalue
*sval
) const;
446 tree
get_representative_tree (const region
*reg
) const;
448 get_representative_path_var (const svalue
*sval
,
449 svalue_set
*visited
) const;
451 get_representative_path_var (const region
*reg
,
452 svalue_set
*visited
) const;
455 constraint_manager
*get_constraints ()
457 return m_constraints
;
460 store
*get_store () { return &m_store
; }
461 const store
*get_store () const { return &m_store
; }
463 const dynamic_extents_t
&
464 get_dynamic_extents () const
466 return m_dynamic_extents
;
468 const svalue
*get_dynamic_extents (const region
*reg
) const;
469 void set_dynamic_extents (const region
*reg
,
470 const svalue
*size_in_bytes
,
471 region_model_context
*ctxt
);
472 void unset_dynamic_extents (const region
*reg
);
474 region_model_manager
*get_manager () const { return m_mgr
; }
475 bounded_ranges_manager
*get_range_manager () const
477 return m_mgr
->get_range_manager ();
480 void unbind_region_and_descendents (const region
*reg
,
481 enum poison_kind pkind
);
483 bool can_merge_with_p (const region_model
&other_model
,
484 const program_point
&point
,
485 region_model
*out_model
,
486 const extrinsic_state
*ext_state
= NULL
,
487 const program_state
*state_a
= NULL
,
488 const program_state
*state_b
= NULL
) const;
490 tree
get_fndecl_for_call (const gcall
*call
,
491 region_model_context
*ctxt
);
493 void get_regions_for_current_frame (auto_vec
<const decl_region
*> *out
) const;
494 static void append_regions_cb (const region
*base_reg
,
495 struct append_regions_cb_data
*data
);
497 const svalue
*get_store_value (const region
*reg
,
498 region_model_context
*ctxt
) const;
500 bool region_exists_p (const region
*reg
) const;
502 void loop_replay_fixup (const region_model
*dst_state
);
504 const svalue
*get_capacity (const region
*reg
) const;
506 const svalue
*get_string_size (const svalue
*sval
) const;
507 const svalue
*get_string_size (const region
*reg
) const;
509 bool replay_call_summary (call_summary_replay
&r
,
510 const region_model
&summary
);
512 void maybe_complain_about_infoleak (const region
*dst_reg
,
513 const svalue
*copied_sval
,
514 const region
*src_reg
,
515 region_model_context
*ctxt
);
517 void set_errno (const call_details
&cd
);
519 /* Implemented in sm-fd.cc */
520 void mark_as_valid_fd (const svalue
*sval
, region_model_context
*ctxt
);
522 /* Implemented in sm-malloc.cc */
523 void on_realloc_with_move (const call_details
&cd
,
524 const svalue
*old_ptr_sval
,
525 const svalue
*new_ptr_sval
);
527 /* Implemented in sm-taint.cc. */
528 void mark_as_tainted (const svalue
*sval
,
529 region_model_context
*ctxt
);
531 bool add_constraint (const svalue
*lhs
,
534 region_model_context
*ctxt
);
536 const svalue
*check_for_poison (const svalue
*sval
,
538 region_model_context
*ctxt
) const;
540 void check_region_for_write (const region
*dest_reg
,
541 region_model_context
*ctxt
) const;
544 const region
*get_lvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
545 const svalue
*get_rvalue_1 (path_var pv
, region_model_context
*ctxt
) const;
548 get_representative_path_var_1 (const svalue
*sval
,
549 svalue_set
*visited
) const;
551 get_representative_path_var_1 (const region
*reg
,
552 svalue_set
*visited
) const;
554 const known_function
*get_known_function (tree fndecl
,
555 const call_details
&cd
) const;
556 const known_function
*get_known_function (enum internal_fn
) const;
558 bool add_constraints_from_binop (const svalue
*outer_lhs
,
559 enum tree_code outer_op
,
560 const svalue
*outer_rhs
,
562 region_model_context
*ctxt
);
564 void update_for_call_superedge (const call_superedge
&call_edge
,
565 region_model_context
*ctxt
);
566 void update_for_return_superedge (const return_superedge
&return_edge
,
567 region_model_context
*ctxt
);
568 bool apply_constraints_for_gcond (const cfg_superedge
&edge
,
569 const gcond
*cond_stmt
,
570 region_model_context
*ctxt
,
571 rejected_constraint
**out
);
572 bool apply_constraints_for_gswitch (const switch_cfg_superedge
&edge
,
573 const gswitch
*switch_stmt
,
574 region_model_context
*ctxt
,
575 rejected_constraint
**out
);
576 bool apply_constraints_for_exception (const gimple
*last_stmt
,
577 region_model_context
*ctxt
,
578 rejected_constraint
**out
);
580 int poison_any_pointers_to_descendents (const region
*reg
,
581 enum poison_kind pkind
);
583 void on_top_level_param (tree param
, region_model_context
*ctxt
);
585 bool called_from_main_p () const;
586 const svalue
*get_initial_value_for_global (const region
*reg
) const;
588 const region
* get_region_for_poisoned_expr (tree expr
) const;
590 void check_dynamic_size_for_taint (enum memory_space mem_space
,
591 const svalue
*size_in_bytes
,
592 region_model_context
*ctxt
) const;
593 void check_dynamic_size_for_floats (const svalue
*size_in_bytes
,
594 region_model_context
*ctxt
) const;
596 void check_region_for_taint (const region
*reg
,
597 enum access_direction dir
,
598 region_model_context
*ctxt
) const;
600 void check_for_writable_region (const region
* dest_reg
,
601 region_model_context
*ctxt
) const;
602 void check_region_access (const region
*reg
,
603 enum access_direction dir
,
604 region_model_context
*ctxt
) const;
605 void check_region_for_read (const region
*src_reg
,
606 region_model_context
*ctxt
) const;
607 void check_region_size (const region
*lhs_reg
, const svalue
*rhs_sval
,
608 region_model_context
*ctxt
) const;
610 /* Implemented in bounds-checking.cc */
611 void check_symbolic_bounds (const region
*base_reg
,
612 const svalue
*sym_byte_offset
,
613 const svalue
*num_bytes_sval
,
614 const svalue
*capacity
,
615 enum access_direction dir
,
616 region_model_context
*ctxt
) const;
617 void check_region_bounds (const region
*reg
, enum access_direction dir
,
618 region_model_context
*ctxt
) const;
620 void check_call_args (const call_details
&cd
) const;
621 void check_external_function_for_access_attr (const gcall
*call
,
623 region_model_context
*ctxt
) const;
625 /* Storing this here to avoid passing it around everywhere. */
626 region_model_manager
*const m_mgr
;
630 constraint_manager
*m_constraints
; // TODO: embed, rather than dynalloc?
632 const frame_region
*m_current_frame
;
634 /* Map from base region to size in bytes, for tracking the sizes of
635 dynamically-allocated regions.
636 This is part of the region_model rather than the region to allow for
637 memory regions to be resized (e.g. by realloc). */
638 dynamic_extents_t m_dynamic_extents
;
641 /* Some region_model activity could lead to warnings (e.g. attempts to use an
642 uninitialized value). This abstract base class encapsulates an interface
643 for the region model to use when emitting such warnings.
645 Having this as an abstract base class allows us to support the various
646 operations needed by program_state in the analyzer within region_model,
647 whilst keeping them somewhat modularized. */
649 class region_model_context
652 /* Hook for clients to store pending diagnostics.
653 Return true if the diagnostic was stored, or false if it was deleted. */
654 virtual bool warn (std::unique_ptr
<pending_diagnostic
> d
) = 0;
656 /* Hook for clients to add a note to the last previously stored
657 pending diagnostic. */
658 virtual void add_note (std::unique_ptr
<pending_note
> pn
) = 0;
660 /* Hook for clients to be notified when an SVAL that was reachable
661 in a previous state is no longer live, so that clients can emit warnings
663 virtual void on_svalue_leak (const svalue
*sval
) = 0;
665 /* Hook for clients to be notified when the set of explicitly live
666 svalues changes, so that they can purge state relating to dead
668 virtual void on_liveness_change (const svalue_set
&live_svalues
,
669 const region_model
*model
) = 0;
671 virtual logger
*get_logger () = 0;
673 /* Hook for clients to be notified when the condition
674 "LHS OP RHS" is added to the region model.
675 This exists so that state machines can detect tests on edges,
676 and use them to trigger sm-state transitions (e.g. transitions due
677 to ptrs becoming known to be NULL or non-NULL, rather than just
679 virtual void on_condition (const svalue
*lhs
,
681 const svalue
*rhs
) = 0;
683 /* Hook for clients to be notified when the condition that
684 SVAL is within RANGES is added to the region model.
685 Similar to on_condition, but for use when handling switch statements.
686 RANGES is non-empty. */
687 virtual void on_bounded_ranges (const svalue
&sval
,
688 const bounded_ranges
&ranges
) = 0;
690 /* Hook for clients to be notified when a frame is popped from the stack. */
691 virtual void on_pop_frame (const frame_region
*) = 0;
693 /* Hooks for clients to be notified when an unknown change happens
694 to SVAL (in response to a call to an unknown function). */
695 virtual void on_unknown_change (const svalue
*sval
, bool is_mutable
) = 0;
697 /* Hooks for clients to be notified when a phi node is handled,
698 where RHS is the pertinent argument. */
699 virtual void on_phi (const gphi
*phi
, tree rhs
) = 0;
701 /* Hooks for clients to be notified when the region model doesn't
702 know how to handle the tree code of T at LOC. */
703 virtual void on_unexpected_tree_code (tree t
,
704 const dump_location_t
&loc
) = 0;
706 /* Hook for clients to be notified when a function_decl escapes. */
707 virtual void on_escaped_function (tree fndecl
) = 0;
709 virtual uncertainty_t
*get_uncertainty () = 0;
711 /* Hook for clients to purge state involving SVAL. */
712 virtual void purge_state_involving (const svalue
*sval
) = 0;
714 /* Hook for clients to split state with a non-standard path. */
715 virtual void bifurcate (std::unique_ptr
<custom_edge_info
> info
) = 0;
717 /* Hook for clients to terminate the standard path. */
718 virtual void terminate_path () = 0;
720 virtual const extrinsic_state
*get_ext_state () const = 0;
722 /* Hook for clients to access the a specific state machine in
723 any underlying program_state. */
725 get_state_map_by_name (const char *name
,
726 sm_state_map
**out_smap
,
727 const state_machine
**out_sm
,
728 unsigned *out_sm_idx
,
729 std::unique_ptr
<sm_context
> *out_sm_context
) = 0;
731 /* Precanned ways for clients to access specific state machines. */
732 bool get_fd_map (sm_state_map
**out_smap
,
733 const state_machine
**out_sm
,
734 unsigned *out_sm_idx
,
735 std::unique_ptr
<sm_context
> *out_sm_context
)
737 return get_state_map_by_name ("file-descriptor", out_smap
, out_sm
,
738 out_sm_idx
, out_sm_context
);
740 bool get_malloc_map (sm_state_map
**out_smap
,
741 const state_machine
**out_sm
,
742 unsigned *out_sm_idx
)
744 return get_state_map_by_name ("malloc", out_smap
, out_sm
, out_sm_idx
, NULL
);
746 bool get_taint_map (sm_state_map
**out_smap
,
747 const state_machine
**out_sm
,
748 unsigned *out_sm_idx
)
750 return get_state_map_by_name ("taint", out_smap
, out_sm
, out_sm_idx
, NULL
);
753 /* Get the current statement, if any. */
754 virtual const gimple
*get_stmt () const = 0;
757 /* A "do nothing" subclass of region_model_context. */
759 class noop_region_model_context
: public region_model_context
762 bool warn (std::unique_ptr
<pending_diagnostic
>) override
{ return false; }
763 void add_note (std::unique_ptr
<pending_note
>) override
;
764 void on_svalue_leak (const svalue
*) override
{}
765 void on_liveness_change (const svalue_set
&,
766 const region_model
*) override
{}
767 logger
*get_logger () override
{ return NULL
; }
768 void on_condition (const svalue
*lhs ATTRIBUTE_UNUSED
,
769 enum tree_code op ATTRIBUTE_UNUSED
,
770 const svalue
*rhs ATTRIBUTE_UNUSED
) override
773 void on_bounded_ranges (const svalue
&,
774 const bounded_ranges
&) override
777 void on_pop_frame (const frame_region
*) override
{}
778 void on_unknown_change (const svalue
*sval ATTRIBUTE_UNUSED
,
779 bool is_mutable ATTRIBUTE_UNUSED
) override
782 void on_phi (const gphi
*phi ATTRIBUTE_UNUSED
,
783 tree rhs ATTRIBUTE_UNUSED
) override
786 void on_unexpected_tree_code (tree
, const dump_location_t
&) override
{}
788 void on_escaped_function (tree
) override
{}
790 uncertainty_t
*get_uncertainty () override
{ return NULL
; }
792 void purge_state_involving (const svalue
*sval ATTRIBUTE_UNUSED
) override
{}
794 void bifurcate (std::unique_ptr
<custom_edge_info
> info
) override
;
795 void terminate_path () override
;
797 const extrinsic_state
*get_ext_state () const override
{ return NULL
; }
799 bool get_state_map_by_name (const char *,
801 const state_machine
**,
803 std::unique_ptr
<sm_context
> *) override
808 const gimple
*get_stmt () const override
{ return NULL
; }
811 /* A subclass of region_model_context for determining if operations fail
812 e.g. "can we generate a region for the lvalue of EXPR?". */
814 class tentative_region_model_context
: public noop_region_model_context
817 tentative_region_model_context () : m_num_unexpected_codes (0) {}
819 void on_unexpected_tree_code (tree
, const dump_location_t
&)
822 m_num_unexpected_codes
++;
825 bool had_errors_p () const { return m_num_unexpected_codes
> 0; }
828 int m_num_unexpected_codes
;
831 /* Subclass of region_model_context that wraps another context, allowing
832 for extra code to be added to the various hooks. */
834 class region_model_context_decorator
: public region_model_context
837 bool warn (std::unique_ptr
<pending_diagnostic
> d
) override
839 return m_inner
->warn (std::move (d
));
842 void add_note (std::unique_ptr
<pending_note
> pn
) override
844 m_inner
->add_note (std::move (pn
));
847 void on_svalue_leak (const svalue
*sval
) override
849 m_inner
->on_svalue_leak (sval
);
852 void on_liveness_change (const svalue_set
&live_svalues
,
853 const region_model
*model
) override
855 m_inner
->on_liveness_change (live_svalues
, model
);
858 logger
*get_logger () override
860 return m_inner
->get_logger ();
863 void on_condition (const svalue
*lhs
,
865 const svalue
*rhs
) override
867 m_inner
->on_condition (lhs
, op
, rhs
);
870 void on_bounded_ranges (const svalue
&sval
,
871 const bounded_ranges
&ranges
) override
873 m_inner
->on_bounded_ranges (sval
, ranges
);
876 void on_pop_frame (const frame_region
*frame_reg
) override
878 m_inner
->on_pop_frame (frame_reg
);
881 void on_unknown_change (const svalue
*sval
, bool is_mutable
) override
883 m_inner
->on_unknown_change (sval
, is_mutable
);
886 void on_phi (const gphi
*phi
, tree rhs
) override
888 m_inner
->on_phi (phi
, rhs
);
891 void on_unexpected_tree_code (tree t
,
892 const dump_location_t
&loc
) override
894 m_inner
->on_unexpected_tree_code (t
, loc
);
897 void on_escaped_function (tree fndecl
) override
899 m_inner
->on_escaped_function (fndecl
);
902 uncertainty_t
*get_uncertainty () override
904 return m_inner
->get_uncertainty ();
907 void purge_state_involving (const svalue
*sval
) override
909 m_inner
->purge_state_involving (sval
);
912 void bifurcate (std::unique_ptr
<custom_edge_info
> info
) override
914 m_inner
->bifurcate (std::move (info
));
917 void terminate_path () override
919 m_inner
->terminate_path ();
922 const extrinsic_state
*get_ext_state () const override
924 return m_inner
->get_ext_state ();
927 bool get_state_map_by_name (const char *name
,
928 sm_state_map
**out_smap
,
929 const state_machine
**out_sm
,
930 unsigned *out_sm_idx
,
931 std::unique_ptr
<sm_context
> *out_sm_context
)
934 return m_inner
->get_state_map_by_name (name
, out_smap
, out_sm
, out_sm_idx
,
938 const gimple
*get_stmt () const override
940 return m_inner
->get_stmt ();
944 region_model_context_decorator (region_model_context
*inner
)
947 gcc_assert (m_inner
);
950 region_model_context
*m_inner
;
953 /* Subclass of region_model_context_decorator that adds a note
954 when saving diagnostics. */
956 class note_adding_context
: public region_model_context_decorator
959 bool warn (std::unique_ptr
<pending_diagnostic
> d
) override
961 if (m_inner
->warn (std::move (d
)))
963 add_note (make_note ());
970 /* Hook to make the new note. */
971 virtual std::unique_ptr
<pending_note
> make_note () = 0;
974 note_adding_context (region_model_context
*inner
)
975 : region_model_context_decorator (inner
)
980 /* A bundle of data for use when attempting to merge two region_model
981 instances to make a third. */
985 model_merger (const region_model
*model_a
,
986 const region_model
*model_b
,
987 const program_point
&point
,
988 region_model
*merged_model
,
989 const extrinsic_state
*ext_state
,
990 const program_state
*state_a
,
991 const program_state
*state_b
)
992 : m_model_a (model_a
), m_model_b (model_b
),
994 m_merged_model (merged_model
),
995 m_ext_state (ext_state
),
996 m_state_a (state_a
), m_state_b (state_b
)
1000 void dump_to_pp (pretty_printer
*pp
, bool simple
) const;
1001 void dump (FILE *fp
, bool simple
) const;
1002 void dump (bool simple
) const;
1004 region_model_manager
*get_manager () const
1006 return m_model_a
->get_manager ();
1009 bool mergeable_svalue_p (const svalue
*) const;
1010 const function_point
&get_function_point () const
1012 return m_point
.get_function_point ();
1015 const region_model
*m_model_a
;
1016 const region_model
*m_model_b
;
1017 const program_point
&m_point
;
1018 region_model
*m_merged_model
;
1020 const extrinsic_state
*m_ext_state
;
1021 const program_state
*m_state_a
;
1022 const program_state
*m_state_b
;
1025 /* A record that can (optionally) be written out when
1026 region_model::add_constraint fails. */
1028 class rejected_constraint
1031 virtual ~rejected_constraint () {}
1032 virtual void dump_to_pp (pretty_printer
*pp
) const = 0;
1034 const region_model
&get_model () const { return m_model
; }
1037 rejected_constraint (const region_model
&model
)
1041 region_model m_model
;
1044 class rejected_op_constraint
: public rejected_constraint
1047 rejected_op_constraint (const region_model
&model
,
1048 tree lhs
, enum tree_code op
, tree rhs
)
1049 : rejected_constraint (model
),
1050 m_lhs (lhs
), m_op (op
), m_rhs (rhs
)
1053 void dump_to_pp (pretty_printer
*pp
) const final override
;
1056 enum tree_code m_op
;
1060 class rejected_ranges_constraint
: public rejected_constraint
1063 rejected_ranges_constraint (const region_model
&model
,
1064 tree expr
, const bounded_ranges
*ranges
)
1065 : rejected_constraint (model
),
1066 m_expr (expr
), m_ranges (ranges
)
1069 void dump_to_pp (pretty_printer
*pp
) const final override
;
1073 const bounded_ranges
*m_ranges
;
1076 /* A bundle of state. */
1081 engine (const supergraph
*sg
= NULL
, logger
*logger
= NULL
);
1082 const supergraph
*get_supergraph () { return m_sg
; }
1083 region_model_manager
*get_model_manager () { return &m_mgr
; }
1084 known_function_manager
*get_known_function_manager ()
1086 return m_mgr
.get_known_function_manager ();
1089 void log_stats (logger
*logger
) const;
1092 const supergraph
*m_sg
;
1093 region_model_manager m_mgr
;
1098 extern void debug (const region_model
&rmodel
);
1104 namespace selftest
{
1106 using namespace ::selftest
;
1108 /* An implementation of region_model_context for use in selftests, which
1109 stores any pending_diagnostic instances passed to it. */
1111 class test_region_model_context
: public noop_region_model_context
1114 bool warn (std::unique_ptr
<pending_diagnostic
> d
) final override
1116 m_diagnostics
.safe_push (d
.release ());
1120 unsigned get_num_diagnostics () const { return m_diagnostics
.length (); }
1122 void on_unexpected_tree_code (tree t
, const dump_location_t
&)
1125 internal_error ("unhandled tree code: %qs",
1126 get_tree_code_name (TREE_CODE (t
)));
1130 /* Implicitly delete any diagnostics in the dtor. */
1131 auto_delete_vec
<pending_diagnostic
> m_diagnostics
;
1134 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1135 Verify that MODEL remains satisfiable. */
1137 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1138 SELFTEST_BEGIN_STMT \
1139 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1140 ASSERT_TRUE (sat); \
1143 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1144 Verify that the result is not satisfiable. */
1146 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1147 SELFTEST_BEGIN_STMT \
1148 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1149 ASSERT_FALSE (sat); \
1152 /* Implementation detail of the ASSERT_CONDITION_* macros. */
1154 void assert_condition (const location
&loc
,
1155 region_model
&model
,
1156 const svalue
*lhs
, tree_code op
, const svalue
*rhs
,
1159 void assert_condition (const location
&loc
,
1160 region_model
&model
,
1161 tree lhs
, tree_code op
, tree rhs
,
1164 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1167 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1168 SELFTEST_BEGIN_STMT \
1169 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1170 tristate (tristate::TS_TRUE)); \
1173 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1176 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1177 SELFTEST_BEGIN_STMT \
1178 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1179 tristate (tristate::TS_FALSE)); \
1182 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1185 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1186 SELFTEST_BEGIN_STMT \
1187 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1188 tristate (tristate::TS_UNKNOWN)); \
1191 } /* end of namespace selftest. */
1193 #endif /* #if CHECKING_P */
1197 #endif /* GCC_ANALYZER_REGION_MODEL_H */