Branch data Line data Source code
1 : : /* Classes for modeling the state of memory.
2 : : Copyright (C) 2019-2025 Free Software Foundation, Inc.
3 : : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
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)
10 : : any later version.
11 : :
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.
16 : :
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/>. */
20 : :
21 : : #ifndef GCC_ANALYZER_REGION_MODEL_H
22 : : #define GCC_ANALYZER_REGION_MODEL_H
23 : :
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 */
28 : :
29 : : #include "bitmap.h"
30 : : #include "stringpool.h"
31 : : #include "attribs.h" // for rdwr_map
32 : : #include "selftest.h"
33 : : #include "analyzer/svalue.h"
34 : : #include "analyzer/region.h"
35 : : #include "analyzer/known-function-manager.h"
36 : : #include "analyzer/region-model-manager.h"
37 : : #include "analyzer/pending-diagnostic.h"
38 : : #include "text-art/widget.h"
39 : : #include "text-art/dump.h"
40 : :
41 : : using namespace ana;
42 : :
43 : : namespace inchash
44 : : {
45 : : extern void add_path_var (path_var pv, hash &hstate);
46 : : } // namespace inchash
47 : :
48 : : namespace ana {
49 : :
50 : : template <typename T>
51 : 1062158 : class one_way_id_map
52 : : {
53 : : public:
54 : : one_way_id_map (int num_ids);
55 : : void put (T src, T dst);
56 : : T get_dst_for_src (T src) const;
57 : : void dump_to_pp (pretty_printer *pp) const;
58 : : void dump () const;
59 : : void update (T *) const;
60 : :
61 : : private:
62 : : auto_vec<T> m_src_to_dst;
63 : : };
64 : :
65 : : /* class one_way_id_map. */
66 : :
67 : : /* one_way_id_map's ctor, which populates the map with dummy null values. */
68 : :
69 : : template <typename T>
70 : 1062158 : inline one_way_id_map<T>::one_way_id_map (int num_svalues)
71 : 1062158 : : m_src_to_dst (num_svalues)
72 : : {
73 : 4089250 : for (int i = 0; i < num_svalues; i++)
74 : 3027092 : m_src_to_dst.quick_push (T::null ());
75 : 1062158 : }
76 : :
77 : : /* Record that SRC is to be mapped to DST. */
78 : :
79 : : template <typename T>
80 : : inline void
81 : 2996832 : one_way_id_map<T>::put (T src, T dst)
82 : : {
83 : 2996832 : m_src_to_dst[src.as_int ()] = dst;
84 : : }
85 : :
86 : : /* Get the new value for SRC within the map. */
87 : :
88 : : template <typename T>
89 : : inline T
90 : 3940503 : one_way_id_map<T>::get_dst_for_src (T src) const
91 : : {
92 : 3940503 : if (src.null_p ())
93 : 0 : return src;
94 : 3940503 : return m_src_to_dst[src.as_int ()];
95 : : }
96 : :
97 : : /* Dump this map to PP. */
98 : :
99 : : template <typename T>
100 : : inline void
101 : 0 : one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
102 : : {
103 : 0 : pp_string (pp, "src to dst: {");
104 : : unsigned i;
105 : : T *dst;
106 : 0 : FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
107 : : {
108 : 0 : if (i > 0)
109 : 0 : pp_string (pp, ", ");
110 : 0 : T src (T::from_int (i));
111 : 0 : src.print (pp);
112 : 0 : pp_string (pp, " -> ");
113 : 0 : dst->print (pp);
114 : : }
115 : 0 : pp_string (pp, "}");
116 : 0 : pp_newline (pp);
117 : 0 : }
118 : :
119 : : /* Dump this map to stderr. */
120 : :
121 : : template <typename T>
122 : : DEBUG_FUNCTION inline void
123 : 0 : one_way_id_map<T>::dump () const
124 : : {
125 : 0 : pretty_printer pp;
126 : 0 : pp.set_output_stream (stderr);
127 : 0 : dump_to_pp (&pp);
128 : 0 : pp_flush (&pp);
129 : 0 : }
130 : :
131 : : /* Update *ID from the old value to its new value in this map. */
132 : :
133 : : template <typename T>
134 : : inline void
135 : 3940503 : one_way_id_map<T>::update (T *id) const
136 : : {
137 : 1977217 : *id = get_dst_for_src (*id);
138 : : }
139 : :
140 : : /* A mapping from region to svalue for use when tracking state. */
141 : :
142 : 4024242 : class region_to_value_map
143 : : {
144 : : public:
145 : : typedef hash_map<const region *, const svalue *> hash_map_t;
146 : : typedef hash_map_t::iterator iterator;
147 : :
148 : 351898 : region_to_value_map () : m_hash_map () {}
149 : 3672344 : region_to_value_map (const region_to_value_map &other)
150 : 3672344 : : m_hash_map (other.m_hash_map) {}
151 : : region_to_value_map &operator= (const region_to_value_map &other);
152 : :
153 : : bool operator== (const region_to_value_map &other) const;
154 : 685913 : bool operator!= (const region_to_value_map &other) const
155 : : {
156 : 685913 : return !(*this == other);
157 : : }
158 : :
159 : 814588 : iterator begin () const { return m_hash_map.begin (); }
160 : 815140 : iterator end () const { return m_hash_map.end (); }
161 : :
162 : 347529 : const svalue * const *get (const region *reg) const
163 : : {
164 : 347529 : return const_cast <hash_map_t &> (m_hash_map).get (reg);
165 : : }
166 : 29677 : void put (const region *reg, const svalue *sval)
167 : : {
168 : 29677 : m_hash_map.put (reg, sval);
169 : : }
170 : 58783 : void remove (const region *reg)
171 : : {
172 : 58783 : m_hash_map.remove (reg);
173 : : }
174 : :
175 : 1965 : bool is_empty () const { return m_hash_map.is_empty (); }
176 : :
177 : : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
178 : : void dump (bool simple) const;
179 : :
180 : : std::unique_ptr<json::object> to_json () const;
181 : :
182 : : std::unique_ptr<text_art::tree_widget>
183 : : make_dump_widget (const text_art::dump_widget_info &dwi) const;
184 : :
185 : : bool can_merge_with_p (const region_to_value_map &other,
186 : : region_to_value_map *out) const;
187 : :
188 : : void purge_state_involving (const svalue *sval);
189 : :
190 : : private:
191 : : hash_map_t m_hash_map;
192 : : };
193 : :
194 : : /* Various operations delete information from a region_model.
195 : :
196 : : This struct tracks how many of each kind of entity were purged (e.g.
197 : : for selftests, and for debugging). */
198 : :
199 : : struct purge_stats
200 : : {
201 : : purge_stats ()
202 : : : m_num_svalues (0),
203 : : m_num_regions (0),
204 : : m_num_equiv_classes (0),
205 : : m_num_constraints (0),
206 : : m_num_bounded_ranges_constraints (0),
207 : : m_num_client_items (0)
208 : : {}
209 : :
210 : : int m_num_svalues;
211 : : int m_num_regions;
212 : : int m_num_equiv_classes;
213 : : int m_num_constraints;
214 : : int m_num_bounded_ranges_constraints;
215 : : int m_num_client_items;
216 : : };
217 : :
218 : : /* A base class for visiting regions and svalues, with do-nothing
219 : : base implementations of the per-subclass vfuncs. */
220 : :
221 : 917623 : class visitor
222 : : {
223 : : public:
224 : 974941 : virtual void visit_region_svalue (const region_svalue *) {}
225 : 2401012 : virtual void visit_constant_svalue (const constant_svalue *) {}
226 : 2065625 : virtual void visit_unknown_svalue (const unknown_svalue *) {}
227 : 15718 : virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
228 : 1556 : virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
229 : 1576923 : virtual void visit_initial_svalue (const initial_svalue *) {}
230 : 673736 : virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
231 : 1109968 : virtual void visit_binop_svalue (const binop_svalue *) {}
232 : 280907 : virtual void visit_sub_svalue (const sub_svalue *) {}
233 : 65858 : virtual void visit_repeated_svalue (const repeated_svalue *) {}
234 : 21361 : virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
235 : 10776 : virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
236 : 54743 : virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
237 : 122600 : virtual void visit_widening_svalue (const widening_svalue *) {}
238 : 42 : virtual void visit_compound_svalue (const compound_svalue *) {}
239 : 1455833 : virtual void visit_conjured_svalue (const conjured_svalue *) {}
240 : 6984 : virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
241 : 24304 : virtual void visit_const_fn_result_svalue (const const_fn_result_svalue *) {}
242 : :
243 : 4048915 : virtual void visit_region (const region *) {}
244 : : };
245 : :
246 : : struct append_regions_cb_data;
247 : :
248 : : typedef void (*pop_frame_callback) (const region_model *model,
249 : : const region_model *prev_model,
250 : : const svalue *retval,
251 : : region_model_context *ctxt);
252 : :
253 : : /* Roughly equivalent to a struct __cxa_exception, except we store a std::vector
254 : : rather than a linked list. */
255 : :
256 : : struct exception_node
257 : : {
258 : 5597 : exception_node (const svalue *exception_sval,
259 : : const svalue *typeinfo_sval,
260 : : const svalue *destructor_sval)
261 : 5597 : : m_exception_sval (exception_sval),
262 : 5597 : m_typeinfo_sval (typeinfo_sval),
263 : 5597 : m_destructor_sval (destructor_sval)
264 : : {
265 : : }
266 : :
267 : : bool operator== (const exception_node &other) const;
268 : :
269 : : void dump_to_pp (pretty_printer *pp, bool simple) const;
270 : : void dump (FILE *fp, bool simple) const;
271 : : void dump (bool simple) const;
272 : : void dump () const;
273 : :
274 : : std::unique_ptr<json::object> to_json () const;
275 : :
276 : : std::unique_ptr<text_art::tree_widget>
277 : : make_dump_widget (const text_art::dump_widget_info &dwi) const;
278 : :
279 : : tree maybe_get_type () const;
280 : :
281 : : void add_to_reachable_regions (reachable_regions &) const;
282 : :
283 : : const svalue *m_exception_sval;
284 : : const svalue *m_typeinfo_sval;
285 : : const svalue *m_destructor_sval;
286 : : };
287 : :
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
291 : : regions.
292 : : It also stores:
293 : : - a constraint_manager, capturing relationships between the values, and
294 : : - dynamic extents, mapping dynamically-allocated regions to svalues (their
295 : : capacities). */
296 : :
297 : : class region_model
298 : : {
299 : : public:
300 : : typedef region_to_value_map dynamic_extents_t;
301 : :
302 : : region_model (region_model_manager *mgr);
303 : : region_model (const region_model &other);
304 : : ~region_model ();
305 : : region_model &operator= (const region_model &other);
306 : :
307 : : bool operator== (const region_model &other) const;
308 : 28 : bool operator!= (const region_model &other) const
309 : : {
310 : 28 : return !(*this == other);
311 : : }
312 : :
313 : : hashval_t hash () const;
314 : :
315 : : void print (pretty_printer *pp) const;
316 : :
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;
320 : : void dump () const;
321 : :
322 : : void debug () const;
323 : :
324 : : std::unique_ptr<json::object> to_json () const;
325 : :
326 : : std::unique_ptr<text_art::tree_widget>
327 : : make_dump_widget (const text_art::dump_widget_info &dwi) const;
328 : :
329 : : void validate () const;
330 : :
331 : : void canonicalize ();
332 : : bool canonicalized_p () const;
333 : :
334 : : void
335 : : on_stmt_pre (const gimple *stmt,
336 : : bool *out_unknown_side_effects,
337 : : region_model_context *ctxt);
338 : :
339 : : void on_assignment (const gassign *stmt, region_model_context *ctxt);
340 : : const svalue *get_gassign_result (const gassign *assign,
341 : : region_model_context *ctxt);
342 : : void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
343 : : bool on_call_pre (const gcall &stmt, region_model_context *ctxt);
344 : : void on_call_post (const gcall &stmt,
345 : : bool unknown_side_effects,
346 : : region_model_context *ctxt);
347 : :
348 : : void purge_state_involving (const svalue *sval, region_model_context *ctxt);
349 : :
350 : : void impl_deallocation_call (const call_details &cd);
351 : :
352 : : const svalue *maybe_get_copy_bounds (const region *src_reg,
353 : : const svalue *num_bytes_sval);
354 : : void update_for_int_cst_return (const call_details &cd,
355 : : int retval,
356 : : bool unmergeable);
357 : : void update_for_zero_return (const call_details &cd,
358 : : bool unmergeable);
359 : : void update_for_nonzero_return (const call_details &cd);
360 : :
361 : : void handle_unrecognized_call (const gcall &call,
362 : : region_model_context *ctxt);
363 : : void get_reachable_svalues (svalue_set *out,
364 : : const svalue *extra_sval,
365 : : const uncertainty_t *uncertainty);
366 : :
367 : : void on_return (const greturn *stmt, region_model_context *ctxt);
368 : : void on_setjmp (const gcall &stmt, const exploded_node *enode,
369 : : region_model_context *ctxt);
370 : : void on_longjmp (const gcall &longjmp_call, const gcall &setjmp_call,
371 : : int setjmp_stack_depth, region_model_context *ctxt);
372 : :
373 : : void update_for_phis (const supernode *snode,
374 : : const cfg_superedge *last_cfg_superedge,
375 : : region_model_context *ctxt);
376 : :
377 : : void handle_phi (const gphi *phi, tree lhs, tree rhs,
378 : : const region_model &old_state,
379 : : hash_set<const svalue *> &svals_changing_meaning,
380 : : region_model_context *ctxt);
381 : :
382 : : bool maybe_update_for_edge (const superedge &edge,
383 : : const gimple *last_stmt,
384 : : region_model_context *ctxt,
385 : : std::unique_ptr<rejected_constraint> *out);
386 : :
387 : : void update_for_gcall (const gcall &call_stmt,
388 : : region_model_context *ctxt,
389 : : function *callee = nullptr);
390 : :
391 : : void update_for_return_gcall (const gcall &call_stmt,
392 : : region_model_context *ctxt);
393 : :
394 : : const region *push_frame (const function &fun,
395 : : const gcall *call_stmt,
396 : : const vec<const svalue *> *arg_sids,
397 : : region_model_context *ctxt);
398 : 9130061 : const frame_region *get_current_frame () const { return m_current_frame; }
399 : : const function *get_current_function () const;
400 : : void pop_frame (tree result_lvalue,
401 : : const svalue **out_result,
402 : : region_model_context *ctxt,
403 : : const gcall *call_stmt,
404 : : bool eval_return_svalue = true);
405 : : int get_stack_depth () const;
406 : : const frame_region *get_frame_at_index (int index) const;
407 : :
408 : : const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
409 : : const region *get_lvalue (tree expr, region_model_context *ctxt) const;
410 : : const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
411 : : const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
412 : :
413 : : const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
414 : : region_model_context *ctxt,
415 : : bool add_nonnull_constraint = true) const;
416 : :
417 : : const svalue *get_rvalue_for_bits (tree type,
418 : : const region *reg,
419 : : const bit_range &bits,
420 : : region_model_context *ctxt) const;
421 : :
422 : : void set_value (const region *lhs_reg, const svalue *rhs_sval,
423 : : region_model_context *ctxt);
424 : : void set_value (tree lhs, tree rhs, region_model_context *ctxt);
425 : : void clobber_region (const region *reg);
426 : : void purge_region (const region *reg);
427 : : void fill_region (const region *reg,
428 : : const svalue *sval,
429 : : region_model_context *ctxt);
430 : : void zero_fill_region (const region *reg,
431 : : region_model_context *ctxt);
432 : : void write_bytes (const region *dest_reg,
433 : : const svalue *num_bytes_sval,
434 : : const svalue *sval,
435 : : region_model_context *ctxt);
436 : : const svalue *read_bytes (const region *src_reg,
437 : : tree src_ptr_expr,
438 : : const svalue *num_bytes_sval,
439 : : region_model_context *ctxt) const;
440 : : void copy_bytes (const region *dest_reg,
441 : : const region *src_reg,
442 : : tree src_ptr_expr,
443 : : const svalue *num_bytes_sval,
444 : : region_model_context *ctxt);
445 : : void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
446 : :
447 : : tristate eval_condition (const svalue *lhs,
448 : : enum tree_code op,
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,
456 : : enum tree_code op,
457 : : tree rhs,
458 : : region_model_context *ctxt) const;
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 : : std::unique_ptr<rejected_constraint> *out);
464 : :
465 : : const region *
466 : : get_or_create_region_for_heap_alloc (const svalue *size_in_bytes,
467 : : region_model_context *ctxt,
468 : : bool update_state_machine = false,
469 : : const call_details *cd = nullptr);
470 : :
471 : : const region *create_region_for_alloca (const svalue *size_in_bytes,
472 : : region_model_context *ctxt);
473 : : void get_referenced_base_regions (auto_bitmap &out_ids) const;
474 : :
475 : : tree get_representative_tree (const svalue *sval,
476 : : logger *logger = nullptr) const;
477 : : tree get_representative_tree (const region *reg,
478 : : logger *logger = nullptr) const;
479 : : path_var
480 : : get_representative_path_var (const svalue *sval,
481 : : svalue_set *visited,
482 : : logger *logger) const;
483 : : path_var
484 : : get_representative_path_var (const region *reg,
485 : : svalue_set *visited,
486 : : logger *logger) const;
487 : :
488 : : /* For selftests. */
489 : 626186 : constraint_manager *get_constraints ()
490 : : {
491 : 626186 : return m_constraints;
492 : : }
493 : :
494 : 1224414 : store *get_store () { return &m_store; }
495 : 154654 : const store *get_store () const { return &m_store; }
496 : :
497 : : const dynamic_extents_t &
498 : 296290 : get_dynamic_extents () const
499 : : {
500 : 296290 : return m_dynamic_extents;
501 : : }
502 : : const svalue *get_dynamic_extents (const region *reg) const;
503 : : void set_dynamic_extents (const region *reg,
504 : : const svalue *size_in_bytes,
505 : : region_model_context *ctxt);
506 : : void unset_dynamic_extents (const region *reg);
507 : :
508 : 73933 : region_model_manager *get_manager () const { return m_mgr; }
509 : 7849 : bounded_ranges_manager *get_range_manager () const
510 : : {
511 : 7849 : return m_mgr->get_range_manager ();
512 : : }
513 : :
514 : : void unbind_region_and_descendents (const region *reg,
515 : : enum poison_kind pkind);
516 : :
517 : : bool can_merge_with_p (const region_model &other_model,
518 : : const program_point &point,
519 : : region_model *out_model,
520 : : const extrinsic_state *ext_state = nullptr,
521 : : const program_state *state_a = nullptr,
522 : : const program_state *state_b = nullptr) const;
523 : :
524 : : tree get_fndecl_for_call (const gcall &call,
525 : : region_model_context *ctxt);
526 : :
527 : : void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
528 : : static void append_regions_cb (const region *base_reg,
529 : : struct append_regions_cb_data *data);
530 : :
531 : : const svalue *get_store_value (const region *reg,
532 : : region_model_context *ctxt) const;
533 : : const svalue *get_store_bytes (const region *base_reg,
534 : : const byte_range &bytes,
535 : : region_model_context *ctxt) const;
536 : : const svalue *scan_for_null_terminator (const region *reg,
537 : : tree expr,
538 : : const svalue **out_sval,
539 : : region_model_context *ctxt) const;
540 : : const svalue *scan_for_null_terminator_1 (const region *reg,
541 : : tree expr,
542 : : const svalue **out_sval,
543 : : region_model_context *ctxt) const;
544 : :
545 : : bool region_exists_p (const region *reg) const;
546 : :
547 : : void loop_replay_fixup (const region_model *dst_state);
548 : :
549 : : const svalue *get_capacity (const region *reg) const;
550 : :
551 : : bool replay_call_summary (call_summary_replay &r,
552 : : const region_model &summary);
553 : :
554 : : void maybe_complain_about_infoleak (const region *dst_reg,
555 : : const svalue *copied_sval,
556 : : const region *src_reg,
557 : : region_model_context *ctxt);
558 : :
559 : : void set_errno (const call_details &cd);
560 : :
561 : : /* Implemented in sm-fd.cc */
562 : : void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
563 : :
564 : : /* Implemented in sm-malloc.cc */
565 : : void on_realloc_with_move (const call_details &cd,
566 : : const svalue *old_ptr_sval,
567 : : const svalue *new_ptr_sval);
568 : :
569 : : /* Implemented in sm-malloc.cc. */
570 : : void
571 : : transition_ptr_sval_non_null (region_model_context *ctxt,
572 : : const svalue *new_ptr_sval);
573 : :
574 : : /* Implemented in sm-taint.cc. */
575 : : void mark_as_tainted (const svalue *sval,
576 : : region_model_context *ctxt);
577 : :
578 : : bool add_constraint (const svalue *lhs,
579 : : enum tree_code op,
580 : : const svalue *rhs,
581 : : region_model_context *ctxt);
582 : :
583 : : const svalue *check_for_poison (const svalue *sval,
584 : : tree expr,
585 : : const region *src_region,
586 : : region_model_context *ctxt) const;
587 : :
588 : : void check_region_for_write (const region *dest_reg,
589 : : const svalue *sval_hint,
590 : : region_model_context *ctxt) const;
591 : :
592 : : const svalue *
593 : : check_for_null_terminated_string_arg (const call_details &cd,
594 : : unsigned idx) const;
595 : : const svalue *
596 : : check_for_null_terminated_string_arg (const call_details &cd,
597 : : unsigned idx,
598 : : bool include_terminator,
599 : : const svalue **out_sval) const;
600 : :
601 : : const builtin_known_function *
602 : : get_builtin_kf (const gcall &call,
603 : : region_model_context *ctxt = nullptr) const;
604 : :
605 : : static void
606 : : register_pop_frame_callback (const pop_frame_callback &callback)
607 : : {
608 : : pop_frame_callbacks.safe_push (callback);
609 : : }
610 : :
611 : : static void
612 : 25668 : notify_on_pop_frame (const region_model *model,
613 : : const region_model *prev_model,
614 : : const svalue *retval,
615 : : region_model_context *ctxt)
616 : : {
617 : 25671 : for (auto &callback : pop_frame_callbacks)
618 : 1 : callback (model, prev_model, retval, ctxt);
619 : 25668 : }
620 : :
621 : : bool called_from_main_p () const;
622 : :
623 : 5696 : void push_thrown_exception (const exception_node &node)
624 : : {
625 : 5696 : m_thrown_exceptions_stack.push_back (node);
626 : 99 : }
627 : 434 : const exception_node *get_current_thrown_exception () const
628 : : {
629 : 434 : if (m_thrown_exceptions_stack.empty ())
630 : : return nullptr;
631 : 434 : return &m_thrown_exceptions_stack.back ();
632 : : }
633 : 174 : exception_node pop_thrown_exception ()
634 : : {
635 : 174 : gcc_assert (!m_thrown_exceptions_stack.empty ());
636 : 174 : const exception_node retval = m_thrown_exceptions_stack.back ();
637 : 174 : m_thrown_exceptions_stack.pop_back ();
638 : 174 : return retval;
639 : : }
640 : :
641 : 174 : void push_caught_exception (const exception_node &node)
642 : : {
643 : 174 : m_caught_exceptions_stack.push_back (node);
644 : : }
645 : 189 : const exception_node *get_current_caught_exception () const
646 : : {
647 : 189 : if (m_caught_exceptions_stack.empty ())
648 : : return nullptr;
649 : 189 : return &m_caught_exceptions_stack.back ();
650 : : }
651 : 204 : exception_node pop_caught_exception ()
652 : : {
653 : 204 : gcc_assert (!m_caught_exceptions_stack.empty ());
654 : 204 : const exception_node retval = m_caught_exceptions_stack.back ();
655 : 204 : m_caught_exceptions_stack.pop_back ();
656 : 204 : return retval;
657 : : }
658 : :
659 : : bool
660 : : apply_constraints_for_eh_dispatch_try
661 : : (const eh_dispatch_try_cfg_superedge &edge,
662 : : region_model_context *ctxt,
663 : : tree exception_type,
664 : : std::unique_ptr<rejected_constraint> *out);
665 : :
666 : : bool
667 : : apply_constraints_for_eh_dispatch_allowed
668 : : (const eh_dispatch_allowed_cfg_superedge &edge,
669 : : region_model_context *ctxt,
670 : : tree exception_type,
671 : : std::unique_ptr<rejected_constraint> *out);
672 : :
673 : : private:
674 : : const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
675 : : const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
676 : :
677 : : path_var
678 : : get_representative_path_var_1 (const svalue *sval,
679 : : svalue_set *visited,
680 : : logger *logger) const;
681 : : path_var
682 : : get_representative_path_var_1 (const region *reg,
683 : : svalue_set *visited,
684 : : logger *logger) const;
685 : :
686 : : const known_function *get_known_function (tree fndecl,
687 : : const call_details &cd) const;
688 : : const known_function *get_known_function (enum internal_fn) const;
689 : :
690 : : bool add_constraints_from_binop (const svalue *outer_lhs,
691 : : enum tree_code outer_op,
692 : : const svalue *outer_rhs,
693 : : bool *out,
694 : : region_model_context *ctxt);
695 : :
696 : : void update_for_call_superedge (const call_superedge &call_edge,
697 : : region_model_context *ctxt);
698 : : void update_for_return_superedge (const return_superedge &return_edge,
699 : : region_model_context *ctxt);
700 : : bool apply_constraints_for_gcond (const cfg_superedge &edge,
701 : : const gcond *cond_stmt,
702 : : region_model_context *ctxt,
703 : : std::unique_ptr<rejected_constraint> *out);
704 : : bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
705 : : const gswitch *switch_stmt,
706 : : region_model_context *ctxt,
707 : : std::unique_ptr<rejected_constraint> *out);
708 : : bool apply_constraints_for_ggoto (const cfg_superedge &edge,
709 : : const ggoto *goto_stmt,
710 : : region_model_context *ctxt);
711 : :
712 : : bool
713 : : apply_constraints_for_eh_dispatch (const eh_dispatch_cfg_superedge &edge,
714 : : const geh_dispatch *eh_dispatch_stmt,
715 : : region_model_context *ctxt,
716 : : std::unique_ptr<rejected_constraint> *out);
717 : :
718 : : int poison_any_pointers_to_descendents (const region *reg,
719 : : enum poison_kind pkind);
720 : :
721 : : void on_top_level_param (tree param,
722 : : bool nonnull,
723 : : region_model_context *ctxt);
724 : :
725 : : const svalue *get_initial_value_for_global (const region *reg) const;
726 : :
727 : : const region * get_region_for_poisoned_expr (tree expr) const;
728 : :
729 : : void check_dynamic_size_for_taint (enum memory_space mem_space,
730 : : const svalue *size_in_bytes,
731 : : region_model_context *ctxt) const;
732 : : void check_dynamic_size_for_floats (const svalue *size_in_bytes,
733 : : region_model_context *ctxt) const;
734 : :
735 : : void check_region_for_taint (const region *reg,
736 : : enum access_direction dir,
737 : : region_model_context *ctxt) const;
738 : :
739 : : void check_for_writable_region (const region* dest_reg,
740 : : region_model_context *ctxt) const;
741 : : bool check_region_access (const region *reg,
742 : : enum access_direction dir,
743 : : const svalue *sval_hint,
744 : : region_model_context *ctxt) const;
745 : : bool check_region_for_read (const region *src_reg,
746 : : region_model_context *ctxt) const;
747 : : void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
748 : : region_model_context *ctxt) const;
749 : :
750 : : /* Implemented in bounds-checking.cc */
751 : : bool check_symbolic_bounds (const region *base_reg,
752 : : const svalue *sym_byte_offset,
753 : : const svalue *num_bytes_sval,
754 : : const svalue *capacity,
755 : : enum access_direction dir,
756 : : const svalue *sval_hint,
757 : : region_model_context *ctxt) const;
758 : : bool check_region_bounds (const region *reg, enum access_direction dir,
759 : : const svalue *sval_hint,
760 : : region_model_context *ctxt) const;
761 : :
762 : : void check_call_args (const call_details &cd) const;
763 : : void check_call_format_attr (const call_details &cd,
764 : : tree format_attr) const;
765 : : void check_function_attr_access (const gcall &call,
766 : : tree callee_fndecl,
767 : : region_model_context *ctxt,
768 : : rdwr_map &rdwr_idx) const;
769 : : void check_function_attr_null_terminated_string_arg (const gcall &call,
770 : : tree callee_fndecl,
771 : : region_model_context *ctxt,
772 : : rdwr_map &rdwr_idx);
773 : : void check_one_function_attr_null_terminated_string_arg (const gcall &call,
774 : : tree callee_fndecl,
775 : : region_model_context *ctxt,
776 : : rdwr_map &rdwr_idx,
777 : : tree attr);
778 : : void check_function_attrs (const gcall &call,
779 : : tree callee_fndecl,
780 : : region_model_context *ctxt);
781 : :
782 : : void check_for_throw_inside_call (const gcall &call,
783 : : tree fndecl,
784 : : region_model_context *ctxt);
785 : :
786 : : static auto_vec<pop_frame_callback> pop_frame_callbacks;
787 : : /* Storing this here to avoid passing it around everywhere. */
788 : : region_model_manager *const m_mgr;
789 : :
790 : : store m_store;
791 : :
792 : : constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
793 : :
794 : : const frame_region *m_current_frame;
795 : :
796 : : std::vector<exception_node> m_thrown_exceptions_stack;
797 : : std::vector<exception_node> m_caught_exceptions_stack;
798 : :
799 : : /* Map from base region to size in bytes, for tracking the sizes of
800 : : dynamically-allocated regions.
801 : : This is part of the region_model rather than the region to allow for
802 : : memory regions to be resized (e.g. by realloc). */
803 : : dynamic_extents_t m_dynamic_extents;
804 : : };
805 : :
806 : : /* Some region_model activity could lead to warnings (e.g. attempts to use an
807 : : uninitialized value). This abstract base class encapsulates an interface
808 : : for the region model to use when emitting such warnings.
809 : :
810 : : Having this as an abstract base class allows us to support the various
811 : : operations needed by program_state in the analyzer within region_model,
812 : : whilst keeping them somewhat modularized. */
813 : :
814 : 1455877 : class region_model_context
815 : : {
816 : : public:
817 : : /* Hook for clients to store pending diagnostics.
818 : : Return true if the diagnostic was stored, or false if it was deleted.
819 : : Optionally provide a custom stmt_finder. */
820 : : virtual bool warn (std::unique_ptr<pending_diagnostic> d,
821 : : const stmt_finder *custom_finder = nullptr) = 0;
822 : :
823 : : /* Hook for clients to add a note to the last previously stored
824 : : pending diagnostic. */
825 : : virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
826 : :
827 : : /* Hook for clients to add an event to the last previously stored
828 : : pending diagnostic. */
829 : : virtual void add_event (std::unique_ptr<checker_event> event) = 0;
830 : :
831 : : /* Hook for clients to be notified when an SVAL that was reachable
832 : : in a previous state is no longer live, so that clients can emit warnings
833 : : about leaks. */
834 : : virtual void on_svalue_leak (const svalue *sval) = 0;
835 : :
836 : : /* Hook for clients to be notified when the set of explicitly live
837 : : svalues changes, so that they can purge state relating to dead
838 : : svalues. */
839 : : virtual void on_liveness_change (const svalue_set &live_svalues,
840 : : const region_model *model) = 0;
841 : :
842 : : virtual logger *get_logger () = 0;
843 : :
844 : : /* Hook for clients to be notified when the condition
845 : : "LHS OP RHS" is added to the region model.
846 : : This exists so that state machines can detect tests on edges,
847 : : and use them to trigger sm-state transitions (e.g. transitions due
848 : : to ptrs becoming known to be NULL or non-NULL, rather than just
849 : : "unchecked") */
850 : : virtual void on_condition (const svalue *lhs,
851 : : enum tree_code op,
852 : : const svalue *rhs) = 0;
853 : :
854 : : /* Hook for clients to be notified when the condition that
855 : : SVAL is within RANGES is added to the region model.
856 : : Similar to on_condition, but for use when handling switch statements.
857 : : RANGES is non-empty. */
858 : : virtual void on_bounded_ranges (const svalue &sval,
859 : : const bounded_ranges &ranges) = 0;
860 : :
861 : : /* Hook for clients to be notified when a frame is popped from the stack. */
862 : : virtual void on_pop_frame (const frame_region *) = 0;
863 : :
864 : : /* Hooks for clients to be notified when an unknown change happens
865 : : to SVAL (in response to a call to an unknown function). */
866 : : virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
867 : :
868 : : /* Hooks for clients to be notified when a phi node is handled,
869 : : where RHS is the pertinent argument. */
870 : : virtual void on_phi (const gphi *phi, tree rhs) = 0;
871 : :
872 : : /* Hooks for clients to be notified when the region model doesn't
873 : : know how to handle the tree code of T at LOC. */
874 : : virtual void on_unexpected_tree_code (tree t,
875 : : const dump_location_t &loc) = 0;
876 : :
877 : : /* Hook for clients to be notified when a function_decl escapes. */
878 : : virtual void on_escaped_function (tree fndecl) = 0;
879 : :
880 : : virtual uncertainty_t *get_uncertainty () = 0;
881 : :
882 : : /* Hook for clients to purge state involving SVAL. */
883 : : virtual void purge_state_involving (const svalue *sval) = 0;
884 : :
885 : : /* Hook for clients to split state with a non-standard path. */
886 : : virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
887 : :
888 : : /* Hook for clients to terminate the standard path. */
889 : : virtual void terminate_path () = 0;
890 : :
891 : : virtual const extrinsic_state *get_ext_state () const = 0;
892 : :
893 : : /* Hook for clients to access the a specific state machine in
894 : : any underlying program_state. */
895 : : virtual bool
896 : : get_state_map_by_name (const char *name,
897 : : sm_state_map **out_smap,
898 : : const state_machine **out_sm,
899 : : unsigned *out_sm_idx,
900 : : std::unique_ptr<sm_context> *out_sm_context) = 0;
901 : :
902 : : /* Precanned ways for clients to access specific state machines. */
903 : 796 : bool get_fd_map (sm_state_map **out_smap,
904 : : const state_machine **out_sm,
905 : : unsigned *out_sm_idx,
906 : : std::unique_ptr<sm_context> *out_sm_context)
907 : : {
908 : 796 : return get_state_map_by_name ("file-descriptor", out_smap, out_sm,
909 : : out_sm_idx, out_sm_context);
910 : : }
911 : 307 : bool get_malloc_map (sm_state_map **out_smap,
912 : : const state_machine **out_sm,
913 : : unsigned *out_sm_idx)
914 : : {
915 : 307 : return get_state_map_by_name ("malloc", out_smap, out_sm, out_sm_idx,
916 : : nullptr);
917 : : }
918 : 705156 : bool get_taint_map (sm_state_map **out_smap,
919 : : const state_machine **out_sm,
920 : : unsigned *out_sm_idx)
921 : : {
922 : 705156 : return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx,
923 : : nullptr);
924 : : }
925 : :
926 : : bool possibly_tainted_p (const svalue *sval);
927 : :
928 : : /* Get the current statement, if any. */
929 : : virtual const gimple *get_stmt () const = 0;
930 : :
931 : : virtual const exploded_graph *get_eg () const = 0;
932 : :
933 : : virtual const program_state *get_state () const = 0;
934 : :
935 : : /* Hooks for detecting infinite loops. */
936 : : virtual void maybe_did_work () = 0;
937 : : virtual bool checking_for_infinite_loop_p () const = 0;
938 : : virtual void on_unusable_in_infinite_loop () = 0;
939 : : };
940 : :
941 : : /* A "do nothing" subclass of region_model_context. */
942 : :
943 : 22267 : class noop_region_model_context : public region_model_context
944 : : {
945 : : public:
946 : 13 : bool warn (std::unique_ptr<pending_diagnostic>,
947 : 13 : const stmt_finder *) override { return false; }
948 : : void add_note (std::unique_ptr<pending_note>) override;
949 : : void add_event (std::unique_ptr<checker_event>) override;
950 : 0 : void on_svalue_leak (const svalue *) override {}
951 : 0 : void on_liveness_change (const svalue_set &,
952 : 0 : const region_model *) override {}
953 : 21459 : logger *get_logger () override { return nullptr; }
954 : 44 : void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
955 : : enum tree_code op ATTRIBUTE_UNUSED,
956 : : const svalue *rhs ATTRIBUTE_UNUSED) override
957 : : {
958 : 44 : }
959 : 115 : void on_bounded_ranges (const svalue &,
960 : : const bounded_ranges &) override
961 : : {
962 : 115 : }
963 : 178 : void on_pop_frame (const frame_region *) override {}
964 : 0 : void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
965 : : bool is_mutable ATTRIBUTE_UNUSED) override
966 : : {
967 : 0 : }
968 : 6975 : void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
969 : : tree rhs ATTRIBUTE_UNUSED) override
970 : : {
971 : 6975 : }
972 : 0 : void on_unexpected_tree_code (tree, const dump_location_t &) override {}
973 : :
974 : 0 : void on_escaped_function (tree) override {}
975 : :
976 : 7377 : uncertainty_t *get_uncertainty () override { return nullptr; }
977 : :
978 : 185 : void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
979 : :
980 : : void bifurcate (std::unique_ptr<custom_edge_info> info) override;
981 : : void terminate_path () override;
982 : :
983 : 2709 : const extrinsic_state *get_ext_state () const override { return nullptr; }
984 : :
985 : 21395 : bool get_state_map_by_name (const char *,
986 : : sm_state_map **,
987 : : const state_machine **,
988 : : unsigned *,
989 : : std::unique_ptr<sm_context> *) override
990 : : {
991 : 21395 : return false;
992 : : }
993 : :
994 : 7333 : const gimple *get_stmt () const override { return nullptr; }
995 : 0 : const exploded_graph *get_eg () const override { return nullptr; }
996 : 0 : const program_state *get_state () const override { return nullptr; }
997 : :
998 : 1 : void maybe_did_work () override {}
999 : 44 : bool checking_for_infinite_loop_p () const override { return false; }
1000 : 0 : void on_unusable_in_infinite_loop () override {}
1001 : : };
1002 : :
1003 : : /* A subclass of region_model_context for determining if operations fail
1004 : : e.g. "can we generate a region for the lvalue of EXPR?". */
1005 : :
1006 : : class tentative_region_model_context : public noop_region_model_context
1007 : : {
1008 : : public:
1009 : : tentative_region_model_context () : m_num_unexpected_codes (0) {}
1010 : :
1011 : 0 : void on_unexpected_tree_code (tree, const dump_location_t &)
1012 : : final override
1013 : : {
1014 : 0 : m_num_unexpected_codes++;
1015 : 0 : }
1016 : :
1017 : : bool had_errors_p () const { return m_num_unexpected_codes > 0; }
1018 : :
1019 : : private:
1020 : : int m_num_unexpected_codes;
1021 : : };
1022 : :
1023 : : /* Subclass of region_model_context that wraps another context, allowing
1024 : : for extra code to be added to the various hooks. */
1025 : :
1026 : : class region_model_context_decorator : public region_model_context
1027 : : {
1028 : : public:
1029 : 0 : bool warn (std::unique_ptr<pending_diagnostic> d,
1030 : : const stmt_finder *custom_finder) override
1031 : : {
1032 : 0 : if (m_inner)
1033 : 0 : return m_inner->warn (std::move (d), custom_finder);
1034 : : else
1035 : : return false;
1036 : : }
1037 : :
1038 : 233 : void add_note (std::unique_ptr<pending_note> pn) override
1039 : : {
1040 : 233 : if (m_inner)
1041 : 233 : m_inner->add_note (std::move (pn));
1042 : 233 : }
1043 : : void add_event (std::unique_ptr<checker_event> event) override;
1044 : :
1045 : 0 : void on_svalue_leak (const svalue *sval) override
1046 : : {
1047 : 0 : if (m_inner)
1048 : 0 : m_inner->on_svalue_leak (sval);
1049 : 0 : }
1050 : :
1051 : 0 : void on_liveness_change (const svalue_set &live_svalues,
1052 : : const region_model *model) override
1053 : : {
1054 : 0 : if (m_inner)
1055 : 0 : m_inner->on_liveness_change (live_svalues, model);
1056 : 0 : }
1057 : :
1058 : 25248 : logger *get_logger () override
1059 : : {
1060 : 25248 : if (m_inner)
1061 : 16365 : return m_inner->get_logger ();
1062 : : else
1063 : : return nullptr;
1064 : : }
1065 : :
1066 : 0 : void on_condition (const svalue *lhs,
1067 : : enum tree_code op,
1068 : : const svalue *rhs) override
1069 : : {
1070 : 0 : if (m_inner)
1071 : 0 : m_inner->on_condition (lhs, op, rhs);
1072 : 0 : }
1073 : :
1074 : 0 : void on_bounded_ranges (const svalue &sval,
1075 : : const bounded_ranges &ranges) override
1076 : : {
1077 : 0 : if (m_inner)
1078 : 0 : m_inner->on_bounded_ranges (sval, ranges);
1079 : 0 : }
1080 : :
1081 : 0 : void on_pop_frame (const frame_region *frame_reg) override
1082 : : {
1083 : 0 : if (m_inner)
1084 : 0 : m_inner->on_pop_frame (frame_reg);
1085 : 0 : }
1086 : :
1087 : 0 : void on_unknown_change (const svalue *sval, bool is_mutable) override
1088 : : {
1089 : 0 : if (m_inner)
1090 : 0 : m_inner->on_unknown_change (sval, is_mutable);
1091 : 0 : }
1092 : :
1093 : 0 : void on_phi (const gphi *phi, tree rhs) override
1094 : : {
1095 : 0 : if (m_inner)
1096 : 0 : m_inner->on_phi (phi, rhs);
1097 : 0 : }
1098 : :
1099 : 0 : void on_unexpected_tree_code (tree t,
1100 : : const dump_location_t &loc) override
1101 : : {
1102 : 0 : if (m_inner)
1103 : 0 : m_inner->on_unexpected_tree_code (t, loc);
1104 : 0 : }
1105 : :
1106 : 0 : void on_escaped_function (tree fndecl) override
1107 : : {
1108 : 0 : if (m_inner)
1109 : 0 : m_inner->on_escaped_function (fndecl);
1110 : 0 : }
1111 : :
1112 : 4161 : uncertainty_t *get_uncertainty () override
1113 : : {
1114 : 4161 : if (m_inner)
1115 : 3248 : return m_inner->get_uncertainty ();
1116 : : else
1117 : : return nullptr;
1118 : : }
1119 : :
1120 : 0 : void purge_state_involving (const svalue *sval) override
1121 : : {
1122 : 0 : if (m_inner)
1123 : 0 : m_inner->purge_state_involving (sval);
1124 : 0 : }
1125 : :
1126 : 0 : void bifurcate (std::unique_ptr<custom_edge_info> info) override
1127 : : {
1128 : 0 : if (m_inner)
1129 : 0 : m_inner->bifurcate (std::move (info));
1130 : 0 : }
1131 : :
1132 : 0 : void terminate_path () override
1133 : : {
1134 : 0 : if (m_inner)
1135 : 0 : m_inner->terminate_path ();
1136 : 0 : }
1137 : :
1138 : 4989 : const extrinsic_state *get_ext_state () const override
1139 : : {
1140 : 4989 : if (m_inner)
1141 : 4989 : return m_inner->get_ext_state ();
1142 : : else
1143 : : return nullptr;
1144 : : }
1145 : :
1146 : 7384 : bool get_state_map_by_name (const char *name,
1147 : : sm_state_map **out_smap,
1148 : : const state_machine **out_sm,
1149 : : unsigned *out_sm_idx,
1150 : : std::unique_ptr<sm_context> *out_sm_context)
1151 : : override
1152 : : {
1153 : 7384 : if (m_inner)
1154 : 5025 : return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx,
1155 : 5025 : out_sm_context);
1156 : : else
1157 : : return false;
1158 : : }
1159 : :
1160 : 97 : const gimple *get_stmt () const override
1161 : : {
1162 : 97 : if (m_inner)
1163 : 97 : return m_inner->get_stmt ();
1164 : : else
1165 : : return nullptr;
1166 : : }
1167 : :
1168 : 0 : const exploded_graph *get_eg () const override
1169 : : {
1170 : 0 : if (m_inner)
1171 : 0 : return m_inner->get_eg ();
1172 : : else
1173 : : return nullptr;
1174 : : }
1175 : :
1176 : 0 : const program_state *get_state () const override
1177 : : {
1178 : 0 : if (m_inner)
1179 : 0 : return m_inner->get_state ();
1180 : : else
1181 : : return nullptr;
1182 : : }
1183 : :
1184 : 0 : void maybe_did_work () override
1185 : : {
1186 : 0 : if (m_inner)
1187 : 0 : m_inner->maybe_did_work ();
1188 : 0 : }
1189 : :
1190 : 0 : bool checking_for_infinite_loop_p () const override
1191 : : {
1192 : 0 : if (m_inner)
1193 : 0 : return m_inner->checking_for_infinite_loop_p ();
1194 : : return false;
1195 : : }
1196 : 0 : void on_unusable_in_infinite_loop () override
1197 : : {
1198 : 0 : if (m_inner)
1199 : 0 : m_inner->on_unusable_in_infinite_loop ();
1200 : 0 : }
1201 : :
1202 : : protected:
1203 : 13138 : region_model_context_decorator (region_model_context *inner)
1204 : 4161 : : m_inner (inner)
1205 : : {
1206 : : }
1207 : :
1208 : : region_model_context *m_inner;
1209 : : };
1210 : :
1211 : : /* Subclass of region_model_context_decorator with a hook for adding
1212 : : notes/events when saving diagnostics. */
1213 : :
1214 : : class annotating_context : public region_model_context_decorator
1215 : : {
1216 : : public:
1217 : 232 : bool warn (std::unique_ptr<pending_diagnostic> d,
1218 : : const stmt_finder *custom_finder) override
1219 : : {
1220 : 232 : if (m_inner)
1221 : 228 : if (m_inner->warn (std::move (d), custom_finder))
1222 : : {
1223 : 224 : add_annotations ();
1224 : 224 : return true;
1225 : : }
1226 : : return false;
1227 : : }
1228 : :
1229 : : /* Hook to add new event(s)/note(s) */
1230 : : virtual void add_annotations () = 0;
1231 : :
1232 : : protected:
1233 : 8977 : annotating_context (region_model_context *inner)
1234 : 8977 : : region_model_context_decorator (inner)
1235 : : {
1236 : : }
1237 : : };
1238 : :
1239 : : /* A bundle of data for use when attempting to merge two region_model
1240 : : instances to make a third. */
1241 : :
1242 : 166622 : struct model_merger
1243 : : {
1244 : 166622 : model_merger (const region_model *model_a,
1245 : : const region_model *model_b,
1246 : : const program_point &point,
1247 : : region_model *merged_model,
1248 : : const extrinsic_state *ext_state,
1249 : : const program_state *state_a,
1250 : : const program_state *state_b)
1251 : 166622 : : m_model_a (model_a), m_model_b (model_b),
1252 : 166622 : m_point (point),
1253 : 166622 : m_merged_model (merged_model),
1254 : 166622 : m_ext_state (ext_state),
1255 : 166622 : m_state_a (state_a), m_state_b (state_b)
1256 : : {
1257 : : }
1258 : :
1259 : : void dump_to_pp (pretty_printer *pp, bool simple) const;
1260 : : void dump (FILE *fp, bool simple) const;
1261 : : void dump (bool simple) const;
1262 : :
1263 : : region_model_manager *get_manager () const
1264 : : {
1265 : : return m_model_a->get_manager ();
1266 : : }
1267 : :
1268 : : bool mergeable_svalue_p (const svalue *) const;
1269 : 3381 : const function_point &get_function_point () const
1270 : : {
1271 : 3381 : return m_point.get_function_point ();
1272 : : }
1273 : :
1274 : : void on_widening_reuse (const widening_svalue *widening_sval);
1275 : :
1276 : : const region_model *m_model_a;
1277 : : const region_model *m_model_b;
1278 : : const program_point &m_point;
1279 : : region_model *m_merged_model;
1280 : :
1281 : : const extrinsic_state *m_ext_state;
1282 : : const program_state *m_state_a;
1283 : : const program_state *m_state_b;
1284 : :
1285 : : hash_set<const svalue *> m_svals_changing_meaning;
1286 : : };
1287 : :
1288 : : /* A record that can (optionally) be written out when
1289 : : region_model::add_constraint fails. */
1290 : :
1291 : : class rejected_constraint
1292 : : {
1293 : : public:
1294 : : virtual ~rejected_constraint () {}
1295 : : virtual void dump_to_pp (pretty_printer *pp) const = 0;
1296 : :
1297 : 4 : const region_model &get_model () const { return m_model; }
1298 : :
1299 : : protected:
1300 : 1967 : rejected_constraint (const region_model &model)
1301 : 0 : : m_model (model)
1302 : : {}
1303 : :
1304 : : region_model m_model;
1305 : : };
1306 : :
1307 : : class rejected_op_constraint : public rejected_constraint
1308 : : {
1309 : : public:
1310 : 1883 : rejected_op_constraint (const region_model &model,
1311 : : tree lhs, enum tree_code op, tree rhs)
1312 : 1883 : : rejected_constraint (model),
1313 : 1883 : m_lhs (lhs), m_op (op), m_rhs (rhs)
1314 : : {}
1315 : :
1316 : : void dump_to_pp (pretty_printer *pp) const final override;
1317 : :
1318 : : tree m_lhs;
1319 : : enum tree_code m_op;
1320 : : tree m_rhs;
1321 : : };
1322 : :
1323 : : class rejected_default_case : public rejected_constraint
1324 : : {
1325 : : public:
1326 : 0 : rejected_default_case (const region_model &model)
1327 : 0 : : rejected_constraint (model)
1328 : : {}
1329 : :
1330 : : void dump_to_pp (pretty_printer *pp) const final override;
1331 : : };
1332 : :
1333 : : class rejected_ranges_constraint : public rejected_constraint
1334 : : {
1335 : : public:
1336 : 84 : rejected_ranges_constraint (const region_model &model,
1337 : : tree expr, const bounded_ranges *ranges)
1338 : 84 : : rejected_constraint (model),
1339 : 84 : m_expr (expr), m_ranges (ranges)
1340 : : {}
1341 : :
1342 : : void dump_to_pp (pretty_printer *pp) const final override;
1343 : :
1344 : : private:
1345 : : tree m_expr;
1346 : : const bounded_ranges *m_ranges;
1347 : : };
1348 : :
1349 : : /* A bundle of state. */
1350 : :
1351 : 3328 : class engine
1352 : : {
1353 : : public:
1354 : : engine (const supergraph *sg = nullptr, logger *logger = nullptr);
1355 : 323577 : const supergraph *get_supergraph () { return m_sg; }
1356 : 11774380 : region_model_manager *get_model_manager () { return &m_mgr; }
1357 : 6616 : known_function_manager *get_known_function_manager ()
1358 : : {
1359 : 3308 : return m_mgr.get_known_function_manager ();
1360 : : }
1361 : :
1362 : : void log_stats (logger *logger) const;
1363 : :
1364 : : private:
1365 : : const supergraph *m_sg;
1366 : : region_model_manager m_mgr;
1367 : : };
1368 : :
1369 : : } // namespace ana
1370 : :
1371 : : extern void debug (const region_model &rmodel);
1372 : :
1373 : : namespace ana {
1374 : :
1375 : : #if CHECKING_P
1376 : :
1377 : : namespace selftest {
1378 : :
1379 : : using namespace ::selftest;
1380 : :
1381 : : /* An implementation of region_model_context for use in selftests, which
1382 : : stores any pending_diagnostic instances passed to it. */
1383 : :
1384 : 228 : class test_region_model_context : public noop_region_model_context
1385 : : {
1386 : : public:
1387 : 4 : bool warn (std::unique_ptr<pending_diagnostic> d,
1388 : : const stmt_finder *) final override
1389 : : {
1390 : 4 : m_diagnostics.safe_push (d.release ());
1391 : 4 : return true;
1392 : : }
1393 : :
1394 : 4 : unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1395 : :
1396 : 0 : void on_unexpected_tree_code (tree t, const dump_location_t &)
1397 : : final override
1398 : : {
1399 : 0 : internal_error ("unhandled tree code: %qs",
1400 : 0 : get_tree_code_name (TREE_CODE (t)));
1401 : : }
1402 : :
1403 : : private:
1404 : : /* Implicitly delete any diagnostics in the dtor. */
1405 : : auto_delete_vec<pending_diagnostic> m_diagnostics;
1406 : : };
1407 : :
1408 : : /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1409 : : Verify that MODEL remains satisfiable. */
1410 : :
1411 : : #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1412 : : SELFTEST_BEGIN_STMT \
1413 : : bool sat = (MODEL).add_constraint (LHS, OP, RHS, nullptr); \
1414 : : ASSERT_TRUE (sat); \
1415 : : SELFTEST_END_STMT
1416 : :
1417 : : /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1418 : : Verify that the result is not satisfiable. */
1419 : :
1420 : : #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1421 : : SELFTEST_BEGIN_STMT \
1422 : : bool sat = (MODEL).add_constraint (LHS, OP, RHS, nullptr); \
1423 : : ASSERT_FALSE (sat); \
1424 : : SELFTEST_END_STMT
1425 : :
1426 : : /* Implementation detail of the ASSERT_CONDITION_* macros. */
1427 : :
1428 : : void assert_condition (const location &loc,
1429 : : region_model &model,
1430 : : const svalue *lhs, tree_code op, const svalue *rhs,
1431 : : tristate expected);
1432 : :
1433 : : void assert_condition (const location &loc,
1434 : : region_model &model,
1435 : : tree lhs, tree_code op, tree rhs,
1436 : : tristate expected);
1437 : :
1438 : : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1439 : : as "true". */
1440 : :
1441 : : #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1442 : : SELFTEST_BEGIN_STMT \
1443 : : assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1444 : : tristate (tristate::TS_TRUE)); \
1445 : : SELFTEST_END_STMT
1446 : :
1447 : : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1448 : : as "false". */
1449 : :
1450 : : #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1451 : : SELFTEST_BEGIN_STMT \
1452 : : assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1453 : : tristate (tristate::TS_FALSE)); \
1454 : : SELFTEST_END_STMT
1455 : :
1456 : : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1457 : : as "unknown". */
1458 : :
1459 : : #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1460 : : SELFTEST_BEGIN_STMT \
1461 : : assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1462 : : tristate (tristate::TS_UNKNOWN)); \
1463 : : SELFTEST_END_STMT
1464 : :
1465 : : } /* end of namespace selftest. */
1466 : :
1467 : : #endif /* #if CHECKING_P */
1468 : :
1469 : : } // namespace ana
1470 : :
1471 : : #endif /* GCC_ANALYZER_REGION_MODEL_H */
|