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