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;
259 bool arg_is_pointer_p (unsigned idx) const
261 return POINTER_TYPE_P (get_arg_type (idx));
263 bool arg_is_size_p (unsigned idx) const;
265 const gcall *get_call_stmt () const { return m_call; }
266 location_t get_location () const;
268 tree get_arg_tree (unsigned idx) const;
269 tree get_arg_type (unsigned idx) const;
270 const svalue *get_arg_svalue (unsigned idx) const;
271 const char *get_arg_string_literal (unsigned idx) const;
273 tree get_fndecl_for_call () const;
275 void dump_to_pp (pretty_printer *pp, bool simple) const;
276 void dump (bool simple) const;
278 const svalue *get_or_create_conjured_svalue (const region *) const;
282 region_model *m_model;
283 region_model_context *m_ctxt;
285 const region *m_lhs_region;
288 /* A region_model encapsulates a representation of the state of memory, with
289 a tree of regions, along with their associated values.
290 The representation is graph-like because values can be pointers to
293 - a constraint_manager, capturing relationships between the values, and
294 - dynamic extents, mapping dynamically-allocated regions to svalues (their
300 typedef region_to_value_map dynamic_extents_t;
302 region_model (region_model_manager *mgr);
303 region_model (const region_model &other);
305 region_model &operator= (const region_model &other);
307 bool operator== (const region_model &other) const;
308 bool operator!= (const region_model &other) const
310 return !(*this == other);
313 hashval_t hash () const;
315 void print (pretty_printer *pp) const;
317 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
318 void dump (FILE *fp, bool simple, bool multiline) const;
319 void dump (bool simple) const;
323 void validate () const;
325 void canonicalize ();
326 bool canonicalized_p () const;
329 on_stmt_pre (const gimple *stmt,
330 bool *out_unknown_side_effects,
331 region_model_context *ctxt);
333 void on_assignment (const gassign *stmt, region_model_context *ctxt);
334 const svalue *get_gassign_result (const gassign *assign,
335 region_model_context *ctxt);
336 void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
337 bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
338 void on_call_post (const gcall *stmt,
339 bool unknown_side_effects,
340 region_model_context *ctxt);
342 void purge_state_involving (const svalue *sval, region_model_context *ctxt);
344 void impl_deallocation_call (const call_details &cd);
346 const svalue *maybe_get_copy_bounds (const region *src_reg,
347 const svalue *num_bytes_sval);
348 void update_for_int_cst_return (const call_details &cd,
351 void update_for_zero_return (const call_details &cd,
353 void update_for_nonzero_return (const call_details &cd);
355 void handle_unrecognized_call (const gcall *call,
356 region_model_context *ctxt);
357 void get_reachable_svalues (svalue_set *out,
358 const svalue *extra_sval,
359 const uncertainty_t *uncertainty);
361 void on_return (const greturn *stmt, region_model_context *ctxt);
362 void on_setjmp (const gcall *stmt, const exploded_node *enode,
363 region_model_context *ctxt);
364 void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
365 int setjmp_stack_depth, region_model_context *ctxt);
367 void update_for_phis (const supernode *snode,
368 const cfg_superedge *last_cfg_superedge,
369 region_model_context *ctxt);
371 void handle_phi (const gphi *phi, tree lhs, tree rhs,
372 const region_model &old_state,
373 region_model_context *ctxt);
375 bool maybe_update_for_edge (const superedge &edge,
376 const gimple *last_stmt,
377 region_model_context *ctxt,
378 rejected_constraint **out);
380 void update_for_gcall (const gcall *call_stmt,
381 region_model_context *ctxt,
382 function *callee = NULL);
384 void update_for_return_gcall (const gcall *call_stmt,
385 region_model_context *ctxt);
387 const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
388 region_model_context *ctxt);
389 const frame_region *get_current_frame () const { return m_current_frame; }
390 function * get_current_function () const;
391 void pop_frame (tree result_lvalue,
392 const svalue **out_result,
393 region_model_context *ctxt);
394 int get_stack_depth () const;
395 const frame_region *get_frame_at_index (int index) const;
397 const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
398 const region *get_lvalue (tree expr, region_model_context *ctxt) const;
399 const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
400 const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
402 const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
403 region_model_context *ctxt) const;
405 const svalue *get_rvalue_for_bits (tree type,
407 const bit_range &bits,
408 region_model_context *ctxt) const;
410 void set_value (const region *lhs_reg, const svalue *rhs_sval,
411 region_model_context *ctxt);
412 void set_value (tree lhs, tree rhs, region_model_context *ctxt);
413 void clobber_region (const region *reg);
414 void purge_region (const region *reg);
415 void fill_region (const region *reg, const svalue *sval);
416 void zero_fill_region (const region *reg);
417 void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
419 tristate eval_condition (const svalue *lhs,
421 const svalue *rhs) const;
422 tristate compare_initial_and_pointer (const initial_svalue *init,
423 const region_svalue *ptr) const;
424 tristate symbolic_greater_than (const binop_svalue *a,
425 const svalue *b) const;
426 tristate structural_equality (const svalue *a, const svalue *b) const;
427 tristate eval_condition (tree lhs,
430 region_model_context *ctxt) const;
431 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
432 region_model_context *ctxt);
433 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
434 region_model_context *ctxt,
435 rejected_constraint **out);
437 const region *create_region_for_heap_alloc (const svalue *size_in_bytes,
438 region_model_context *ctxt);
439 const region *create_region_for_alloca (const svalue *size_in_bytes,
440 region_model_context *ctxt);
442 tree get_representative_tree (const svalue *sval) const;
443 tree get_representative_tree (const region *reg) const;
445 get_representative_path_var (const svalue *sval,
446 svalue_set *visited) const;
448 get_representative_path_var (const region *reg,
449 svalue_set *visited) const;
452 constraint_manager *get_constraints ()
454 return m_constraints;
457 store *get_store () { return &m_store; }
458 const store *get_store () const { return &m_store; }
460 const dynamic_extents_t &
461 get_dynamic_extents () const
463 return m_dynamic_extents;
465 const svalue *get_dynamic_extents (const region *reg) const;
466 void set_dynamic_extents (const region *reg,
467 const svalue *size_in_bytes,
468 region_model_context *ctxt);
469 void unset_dynamic_extents (const region *reg);
471 region_model_manager *get_manager () const { return m_mgr; }
472 bounded_ranges_manager *get_range_manager () const
474 return m_mgr->get_range_manager ();
477 void unbind_region_and_descendents (const region *reg,
478 enum poison_kind pkind);
480 bool can_merge_with_p (const region_model &other_model,
481 const program_point &point,
482 region_model *out_model,
483 const extrinsic_state *ext_state = NULL,
484 const program_state *state_a = NULL,
485 const program_state *state_b = NULL) const;
487 tree get_fndecl_for_call (const gcall *call,
488 region_model_context *ctxt);
490 void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
491 static void append_regions_cb (const region *base_reg,
492 struct append_regions_cb_data *data);
494 const svalue *get_store_value (const region *reg,
495 region_model_context *ctxt) const;
497 bool region_exists_p (const region *reg) const;
499 void loop_replay_fixup (const region_model *dst_state);
501 const svalue *get_capacity (const region *reg) const;
503 const svalue *get_string_size (const svalue *sval) const;
504 const svalue *get_string_size (const region *reg) const;
506 bool replay_call_summary (call_summary_replay &r,
507 const region_model &summary);
509 void maybe_complain_about_infoleak (const region *dst_reg,
510 const svalue *copied_sval,
511 const region *src_reg,
512 region_model_context *ctxt);
514 void set_errno (const call_details &cd);
516 /* Implemented in sm-fd.cc */
517 void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
519 /* Implemented in sm-malloc.cc */
520 void on_realloc_with_move (const call_details &cd,
521 const svalue *old_ptr_sval,
522 const svalue *new_ptr_sval);
524 /* Implemented in sm-taint.cc. */
525 void mark_as_tainted (const svalue *sval,
526 region_model_context *ctxt);
528 bool add_constraint (const svalue *lhs,
531 region_model_context *ctxt);
533 const svalue *check_for_poison (const svalue *sval,
535 region_model_context *ctxt) const;
537 void check_region_for_write (const region *dest_reg,
538 region_model_context *ctxt) const;
541 const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
542 const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
545 get_representative_path_var_1 (const svalue *sval,
546 svalue_set *visited) const;
548 get_representative_path_var_1 (const region *reg,
549 svalue_set *visited) const;
551 const known_function *get_known_function (tree fndecl,
552 const call_details &cd) const;
553 const known_function *get_known_function (enum internal_fn) const;
555 bool add_constraints_from_binop (const svalue *outer_lhs,
556 enum tree_code outer_op,
557 const svalue *outer_rhs,
559 region_model_context *ctxt);
561 void update_for_call_superedge (const call_superedge &call_edge,
562 region_model_context *ctxt);
563 void update_for_return_superedge (const return_superedge &return_edge,
564 region_model_context *ctxt);
565 bool apply_constraints_for_gcond (const cfg_superedge &edge,
566 const gcond *cond_stmt,
567 region_model_context *ctxt,
568 rejected_constraint **out);
569 bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
570 const gswitch *switch_stmt,
571 region_model_context *ctxt,
572 rejected_constraint **out);
573 bool apply_constraints_for_exception (const gimple *last_stmt,
574 region_model_context *ctxt,
575 rejected_constraint **out);
577 int poison_any_pointers_to_descendents (const region *reg,
578 enum poison_kind pkind);
580 void on_top_level_param (tree param, region_model_context *ctxt);
582 bool called_from_main_p () const;
583 const svalue *get_initial_value_for_global (const region *reg) const;
585 const region * get_region_for_poisoned_expr (tree expr) const;
587 void check_dynamic_size_for_taint (enum memory_space mem_space,
588 const svalue *size_in_bytes,
589 region_model_context *ctxt) const;
590 void check_dynamic_size_for_floats (const svalue *size_in_bytes,
591 region_model_context *ctxt) const;
593 void check_region_for_taint (const region *reg,
594 enum access_direction dir,
595 region_model_context *ctxt) const;
597 void check_for_writable_region (const region* dest_reg,
598 region_model_context *ctxt) const;
599 void check_region_access (const region *reg,
600 enum access_direction dir,
601 region_model_context *ctxt) const;
602 void check_region_for_read (const region *src_reg,
603 region_model_context *ctxt) const;
604 void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
605 region_model_context *ctxt) const;
606 void check_symbolic_bounds (const region *base_reg,
607 const svalue *sym_byte_offset,
608 const svalue *num_bytes_sval,
609 const svalue *capacity,
610 enum access_direction dir,
611 region_model_context *ctxt) const;
612 void check_region_bounds (const region *reg, enum access_direction dir,
613 region_model_context *ctxt) const;
615 void check_call_args (const call_details &cd) const;
616 void check_external_function_for_access_attr (const gcall *call,
618 region_model_context *ctxt) const;
620 /* Storing this here to avoid passing it around everywhere. */
621 region_model_manager *const m_mgr;
625 constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
627 const frame_region *m_current_frame;
629 /* Map from base region to size in bytes, for tracking the sizes of
630 dynamically-allocated regions.
631 This is part of the region_model rather than the region to allow for
632 memory regions to be resized (e.g. by realloc). */
633 dynamic_extents_t m_dynamic_extents;
636 /* Some region_model activity could lead to warnings (e.g. attempts to use an
637 uninitialized value). This abstract base class encapsulates an interface
638 for the region model to use when emitting such warnings.
640 Having this as an abstract base class allows us to support the various
641 operations needed by program_state in the analyzer within region_model,
642 whilst keeping them somewhat modularized. */
644 class region_model_context
647 /* Hook for clients to store pending diagnostics.
648 Return true if the diagnostic was stored, or false if it was deleted. */
649 virtual bool warn (std::unique_ptr<pending_diagnostic> d) = 0;
651 /* Hook for clients to add a note to the last previously stored
652 pending diagnostic. */
653 virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
655 /* Hook for clients to be notified when an SVAL that was reachable
656 in a previous state is no longer live, so that clients can emit warnings
658 virtual void on_svalue_leak (const svalue *sval) = 0;
660 /* Hook for clients to be notified when the set of explicitly live
661 svalues changes, so that they can purge state relating to dead
663 virtual void on_liveness_change (const svalue_set &live_svalues,
664 const region_model *model) = 0;
666 virtual logger *get_logger () = 0;
668 /* Hook for clients to be notified when the condition
669 "LHS OP RHS" is added to the region model.
670 This exists so that state machines can detect tests on edges,
671 and use them to trigger sm-state transitions (e.g. transitions due
672 to ptrs becoming known to be NULL or non-NULL, rather than just
674 virtual void on_condition (const svalue *lhs,
676 const svalue *rhs) = 0;
678 /* Hook for clients to be notified when the condition that
679 SVAL is within RANGES is added to the region model.
680 Similar to on_condition, but for use when handling switch statements.
681 RANGES is non-empty. */
682 virtual void on_bounded_ranges (const svalue &sval,
683 const bounded_ranges &ranges) = 0;
685 /* Hook for clients to be notified when a frame is popped from the stack. */
686 virtual void on_pop_frame (const frame_region *) = 0;
688 /* Hooks for clients to be notified when an unknown change happens
689 to SVAL (in response to a call to an unknown function). */
690 virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
692 /* Hooks for clients to be notified when a phi node is handled,
693 where RHS is the pertinent argument. */
694 virtual void on_phi (const gphi *phi, tree rhs) = 0;
696 /* Hooks for clients to be notified when the region model doesn't
697 know how to handle the tree code of T at LOC. */
698 virtual void on_unexpected_tree_code (tree t,
699 const dump_location_t &loc) = 0;
701 /* Hook for clients to be notified when a function_decl escapes. */
702 virtual void on_escaped_function (tree fndecl) = 0;
704 virtual uncertainty_t *get_uncertainty () = 0;
706 /* Hook for clients to purge state involving SVAL. */
707 virtual void purge_state_involving (const svalue *sval) = 0;
709 /* Hook for clients to split state with a non-standard path. */
710 virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
712 /* Hook for clients to terminate the standard path. */
713 virtual void terminate_path () = 0;
715 virtual const extrinsic_state *get_ext_state () const = 0;
717 /* Hook for clients to access the a specific state machine in
718 any underlying program_state. */
720 get_state_map_by_name (const char *name,
721 sm_state_map **out_smap,
722 const state_machine **out_sm,
723 unsigned *out_sm_idx,
724 std::unique_ptr<sm_context> *out_sm_context) = 0;
726 /* Precanned ways for clients to access specific state machines. */
727 bool get_fd_map (sm_state_map **out_smap,
728 const state_machine **out_sm,
729 unsigned *out_sm_idx,
730 std::unique_ptr<sm_context> *out_sm_context)
732 return get_state_map_by_name ("file-descriptor", out_smap, out_sm,
733 out_sm_idx, out_sm_context);
735 bool get_malloc_map (sm_state_map **out_smap,
736 const state_machine **out_sm,
737 unsigned *out_sm_idx)
739 return get_state_map_by_name ("malloc", out_smap, out_sm, out_sm_idx, NULL);
741 bool get_taint_map (sm_state_map **out_smap,
742 const state_machine **out_sm,
743 unsigned *out_sm_idx)
745 return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx, NULL);
748 /* Get the current statement, if any. */
749 virtual const gimple *get_stmt () const = 0;
752 /* A "do nothing" subclass of region_model_context. */
754 class noop_region_model_context : public region_model_context
757 bool warn (std::unique_ptr<pending_diagnostic>) override { return false; }
758 void add_note (std::unique_ptr<pending_note>) override;
759 void on_svalue_leak (const svalue *) override {}
760 void on_liveness_change (const svalue_set &,
761 const region_model *) override {}
762 logger *get_logger () override { return NULL; }
763 void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
764 enum tree_code op ATTRIBUTE_UNUSED,
765 const svalue *rhs ATTRIBUTE_UNUSED) override
768 void on_bounded_ranges (const svalue &,
769 const bounded_ranges &) override
772 void on_pop_frame (const frame_region *) override {}
773 void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
774 bool is_mutable ATTRIBUTE_UNUSED) override
777 void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
778 tree rhs ATTRIBUTE_UNUSED) override
781 void on_unexpected_tree_code (tree, const dump_location_t &) override {}
783 void on_escaped_function (tree) override {}
785 uncertainty_t *get_uncertainty () override { return NULL; }
787 void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
789 void bifurcate (std::unique_ptr<custom_edge_info> info) override;
790 void terminate_path () override;
792 const extrinsic_state *get_ext_state () const override { return NULL; }
794 bool get_state_map_by_name (const char *,
796 const state_machine **,
798 std::unique_ptr<sm_context> *) override
803 const gimple *get_stmt () const override { return NULL; }
806 /* A subclass of region_model_context for determining if operations fail
807 e.g. "can we generate a region for the lvalue of EXPR?". */
809 class tentative_region_model_context : public noop_region_model_context
812 tentative_region_model_context () : m_num_unexpected_codes (0) {}
814 void on_unexpected_tree_code (tree, const dump_location_t &)
817 m_num_unexpected_codes++;
820 bool had_errors_p () const { return m_num_unexpected_codes > 0; }
823 int m_num_unexpected_codes;
826 /* Subclass of region_model_context that wraps another context, allowing
827 for extra code to be added to the various hooks. */
829 class region_model_context_decorator : public region_model_context
832 bool warn (std::unique_ptr<pending_diagnostic> d) override
834 return m_inner->warn (std::move (d));
837 void add_note (std::unique_ptr<pending_note> pn) override
839 m_inner->add_note (std::move (pn));
842 void on_svalue_leak (const svalue *sval) override
844 m_inner->on_svalue_leak (sval);
847 void on_liveness_change (const svalue_set &live_svalues,
848 const region_model *model) override
850 m_inner->on_liveness_change (live_svalues, model);
853 logger *get_logger () override
855 return m_inner->get_logger ();
858 void on_condition (const svalue *lhs,
860 const svalue *rhs) override
862 m_inner->on_condition (lhs, op, rhs);
865 void on_bounded_ranges (const svalue &sval,
866 const bounded_ranges &ranges) override
868 m_inner->on_bounded_ranges (sval, ranges);
871 void on_pop_frame (const frame_region *frame_reg) override
873 m_inner->on_pop_frame (frame_reg);
876 void on_unknown_change (const svalue *sval, bool is_mutable) override
878 m_inner->on_unknown_change (sval, is_mutable);
881 void on_phi (const gphi *phi, tree rhs) override
883 m_inner->on_phi (phi, rhs);
886 void on_unexpected_tree_code (tree t,
887 const dump_location_t &loc) override
889 m_inner->on_unexpected_tree_code (t, loc);
892 void on_escaped_function (tree fndecl) override
894 m_inner->on_escaped_function (fndecl);
897 uncertainty_t *get_uncertainty () override
899 return m_inner->get_uncertainty ();
902 void purge_state_involving (const svalue *sval) override
904 m_inner->purge_state_involving (sval);
907 void bifurcate (std::unique_ptr<custom_edge_info> info) override
909 m_inner->bifurcate (std::move (info));
912 void terminate_path () override
914 m_inner->terminate_path ();
917 const extrinsic_state *get_ext_state () const override
919 return m_inner->get_ext_state ();
922 bool get_state_map_by_name (const char *name,
923 sm_state_map **out_smap,
924 const state_machine **out_sm,
925 unsigned *out_sm_idx,
926 std::unique_ptr<sm_context> *out_sm_context)
929 return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx,
933 const gimple *get_stmt () const override
935 return m_inner->get_stmt ();
939 region_model_context_decorator (region_model_context *inner)
942 gcc_assert (m_inner);
945 region_model_context *m_inner;
948 /* Subclass of region_model_context_decorator that adds a note
949 when saving diagnostics. */
951 class note_adding_context : public region_model_context_decorator
954 bool warn (std::unique_ptr<pending_diagnostic> d) override
956 if (m_inner->warn (std::move (d)))
958 add_note (make_note ());
965 /* Hook to make the new note. */
966 virtual std::unique_ptr<pending_note> make_note () = 0;
969 note_adding_context (region_model_context *inner)
970 : region_model_context_decorator (inner)
975 /* A bundle of data for use when attempting to merge two region_model
976 instances to make a third. */
980 model_merger (const region_model *model_a,
981 const region_model *model_b,
982 const program_point &point,
983 region_model *merged_model,
984 const extrinsic_state *ext_state,
985 const program_state *state_a,
986 const program_state *state_b)
987 : m_model_a (model_a), m_model_b (model_b),
989 m_merged_model (merged_model),
990 m_ext_state (ext_state),
991 m_state_a (state_a), m_state_b (state_b)
995 void dump_to_pp (pretty_printer *pp, bool simple) const;
996 void dump (FILE *fp, bool simple) const;
997 void dump (bool simple) const;
999 region_model_manager *get_manager () const
1001 return m_model_a->get_manager ();
1004 bool mergeable_svalue_p (const svalue *) const;
1005 const function_point &get_function_point () const
1007 return m_point.get_function_point ();
1010 const region_model *m_model_a;
1011 const region_model *m_model_b;
1012 const program_point &m_point;
1013 region_model *m_merged_model;
1015 const extrinsic_state *m_ext_state;
1016 const program_state *m_state_a;
1017 const program_state *m_state_b;
1020 /* A record that can (optionally) be written out when
1021 region_model::add_constraint fails. */
1023 class rejected_constraint
1026 virtual ~rejected_constraint () {}
1027 virtual void dump_to_pp (pretty_printer *pp) const = 0;
1029 const region_model &get_model () const { return m_model; }
1032 rejected_constraint (const region_model &model)
1036 region_model m_model;
1039 class rejected_op_constraint : public rejected_constraint
1042 rejected_op_constraint (const region_model &model,
1043 tree lhs, enum tree_code op, tree rhs)
1044 : rejected_constraint (model),
1045 m_lhs (lhs), m_op (op), m_rhs (rhs)
1048 void dump_to_pp (pretty_printer *pp) const final override;
1051 enum tree_code m_op;
1055 class rejected_ranges_constraint : public rejected_constraint
1058 rejected_ranges_constraint (const region_model &model,
1059 tree expr, const bounded_ranges *ranges)
1060 : rejected_constraint (model),
1061 m_expr (expr), m_ranges (ranges)
1064 void dump_to_pp (pretty_printer *pp) const final override;
1068 const bounded_ranges *m_ranges;
1071 /* A bundle of state. */
1076 engine (const supergraph *sg = NULL, logger *logger = NULL);
1077 const supergraph *get_supergraph () { return m_sg; }
1078 region_model_manager *get_model_manager () { return &m_mgr; }
1079 known_function_manager *get_known_function_manager ()
1081 return m_mgr.get_known_function_manager ();
1084 void log_stats (logger *logger) const;
1087 const supergraph *m_sg;
1088 region_model_manager m_mgr;
1093 extern void debug (const region_model &rmodel);
1099 namespace selftest {
1101 using namespace ::selftest;
1103 /* An implementation of region_model_context for use in selftests, which
1104 stores any pending_diagnostic instances passed to it. */
1106 class test_region_model_context : public noop_region_model_context
1109 bool warn (std::unique_ptr<pending_diagnostic> d) final override
1111 m_diagnostics.safe_push (d.release ());
1115 unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1117 void on_unexpected_tree_code (tree t, const dump_location_t &)
1120 internal_error ("unhandled tree code: %qs",
1121 get_tree_code_name (TREE_CODE (t)));
1125 /* Implicitly delete any diagnostics in the dtor. */
1126 auto_delete_vec<pending_diagnostic> m_diagnostics;
1129 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1130 Verify that MODEL remains satisfiable. */
1132 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1133 SELFTEST_BEGIN_STMT \
1134 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1135 ASSERT_TRUE (sat); \
1138 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1139 Verify that the result is not satisfiable. */
1141 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1142 SELFTEST_BEGIN_STMT \
1143 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1144 ASSERT_FALSE (sat); \
1147 /* Implementation detail of the ASSERT_CONDITION_* macros. */
1149 void assert_condition (const location &loc,
1150 region_model &model,
1151 const svalue *lhs, tree_code op, const svalue *rhs,
1154 void assert_condition (const location &loc,
1155 region_model &model,
1156 tree lhs, tree_code op, tree rhs,
1159 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1162 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1163 SELFTEST_BEGIN_STMT \
1164 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1165 tristate (tristate::TS_TRUE)); \
1168 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1171 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1172 SELFTEST_BEGIN_STMT \
1173 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1174 tristate (tristate::TS_FALSE)); \
1177 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1180 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1181 SELFTEST_BEGIN_STMT \
1182 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1183 tristate (tristate::TS_UNKNOWN)); \
1186 } /* end of namespace selftest. */
1188 #endif /* #if CHECKING_P */
1192 #endif /* GCC_ANALYZER_REGION_MODEL_H */