Branch data Line data Source code
1 : : /* Classes for modeling the state of memory.
2 : : Copyright (C) 2019-2024 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 : 1019710 : 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 : 1019710 : inline one_way_id_map<T>::one_way_id_map (int num_svalues)
71 : 1019710 : : m_src_to_dst (num_svalues)
72 : : {
73 : 3935325 : for (int i = 0; i < num_svalues; i++)
74 : 2915615 : m_src_to_dst.quick_push (T::null ());
75 : 1019710 : }
76 : :
77 : : /* Record that SRC is to be mapped to DST. */
78 : :
79 : : template <typename T>
80 : : inline void
81 : 2885489 : one_way_id_map<T>::put (T src, T dst)
82 : : {
83 : 2885489 : 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 : 3751146 : one_way_id_map<T>::get_dst_for_src (T src) const
91 : : {
92 : 3751146 : if (src.null_p ())
93 : 0 : return src;
94 : 3751146 : 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 : 3751146 : one_way_id_map<T>::update (T *id) const
136 : : {
137 : 1882433 : *id = get_dst_for_src (*id);
138 : : }
139 : :
140 : : /* A mapping from region to svalue for use when tracking state. */
141 : :
142 : 3866400 : 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 : 338513 : region_to_value_map () : m_hash_map () {}
149 : 3527887 : region_to_value_map (const region_to_value_map &other)
150 : 3527887 : : 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 : 658044 : bool operator!= (const region_to_value_map &other) const
155 : : {
156 : 658044 : return !(*this == other);
157 : : }
158 : :
159 : 773310 : iterator begin () const { return m_hash_map.begin (); }
160 : 773862 : iterator end () const { return m_hash_map.end (); }
161 : :
162 : 342501 : const svalue * const *get (const region *reg) const
163 : : {
164 : 342501 : return const_cast <hash_map_t &> (m_hash_map).get (reg);
165 : : }
166 : 29864 : void put (const region *reg, const svalue *sval)
167 : : {
168 : 29864 : m_hash_map.put (reg, sval);
169 : : }
170 : 57502 : void remove (const region *reg)
171 : : {
172 : 57502 : m_hash_map.remove (reg);
173 : : }
174 : :
175 : 1956 : 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 : 884519 : class visitor
222 : : {
223 : : public:
224 : 882854 : virtual void visit_region_svalue (const region_svalue *) {}
225 : 2421265 : virtual void visit_constant_svalue (const constant_svalue *) {}
226 : 2113963 : virtual void visit_unknown_svalue (const unknown_svalue *) {}
227 : 16291 : virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
228 : 1463 : virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
229 : 1480375 : virtual void visit_initial_svalue (const initial_svalue *) {}
230 : 689773 : virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
231 : 1120434 : virtual void visit_binop_svalue (const binop_svalue *) {}
232 : 286031 : virtual void visit_sub_svalue (const sub_svalue *) {}
233 : 67432 : virtual void visit_repeated_svalue (const repeated_svalue *) {}
234 : 19409 : virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
235 : 11140 : virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
236 : 55206 : virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
237 : 122381 : virtual void visit_widening_svalue (const widening_svalue *) {}
238 : 42 : virtual void visit_compound_svalue (const compound_svalue *) {}
239 : 1449400 : virtual void visit_conjured_svalue (const conjured_svalue *) {}
240 : 6988 : virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
241 : 24394 : virtual void visit_const_fn_result_svalue (const const_fn_result_svalue *) {}
242 : :
243 : 3896542 : 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 : : /* A region_model encapsulates a representation of the state of memory, with
254 : : a tree of regions, along with their associated values.
255 : : The representation is graph-like because values can be pointers to
256 : : regions.
257 : : It also stores:
258 : : - a constraint_manager, capturing relationships between the values, and
259 : : - dynamic extents, mapping dynamically-allocated regions to svalues (their
260 : : capacities). */
261 : :
262 : : class region_model
263 : : {
264 : : public:
265 : : typedef region_to_value_map dynamic_extents_t;
266 : :
267 : : region_model (region_model_manager *mgr);
268 : : region_model (const region_model &other);
269 : : ~region_model ();
270 : : region_model &operator= (const region_model &other);
271 : :
272 : : bool operator== (const region_model &other) const;
273 : 28 : bool operator!= (const region_model &other) const
274 : : {
275 : 28 : return !(*this == other);
276 : : }
277 : :
278 : : hashval_t hash () const;
279 : :
280 : : void print (pretty_printer *pp) const;
281 : :
282 : : void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
283 : : void dump (FILE *fp, bool simple, bool multiline) const;
284 : : void dump (bool simple) const;
285 : : void dump () const;
286 : :
287 : : void debug () const;
288 : :
289 : : std::unique_ptr<json::object> to_json () const;
290 : :
291 : : std::unique_ptr<text_art::tree_widget>
292 : : make_dump_widget (const text_art::dump_widget_info &dwi) const;
293 : :
294 : : void validate () const;
295 : :
296 : : void canonicalize ();
297 : : bool canonicalized_p () const;
298 : :
299 : : void
300 : : on_stmt_pre (const gimple *stmt,
301 : : bool *out_unknown_side_effects,
302 : : region_model_context *ctxt);
303 : :
304 : : void on_assignment (const gassign *stmt, region_model_context *ctxt);
305 : : const svalue *get_gassign_result (const gassign *assign,
306 : : region_model_context *ctxt);
307 : : void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
308 : : bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
309 : : void on_call_post (const gcall *stmt,
310 : : bool unknown_side_effects,
311 : : region_model_context *ctxt);
312 : :
313 : : void purge_state_involving (const svalue *sval, region_model_context *ctxt);
314 : :
315 : : void impl_deallocation_call (const call_details &cd);
316 : :
317 : : const svalue *maybe_get_copy_bounds (const region *src_reg,
318 : : const svalue *num_bytes_sval);
319 : : void update_for_int_cst_return (const call_details &cd,
320 : : int retval,
321 : : bool unmergeable);
322 : : void update_for_zero_return (const call_details &cd,
323 : : bool unmergeable);
324 : : void update_for_nonzero_return (const call_details &cd);
325 : :
326 : : void handle_unrecognized_call (const gcall *call,
327 : : region_model_context *ctxt);
328 : : void get_reachable_svalues (svalue_set *out,
329 : : const svalue *extra_sval,
330 : : const uncertainty_t *uncertainty);
331 : :
332 : : void on_return (const greturn *stmt, region_model_context *ctxt);
333 : : void on_setjmp (const gcall *stmt, const exploded_node *enode,
334 : : region_model_context *ctxt);
335 : : void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
336 : : int setjmp_stack_depth, region_model_context *ctxt);
337 : :
338 : : void update_for_phis (const supernode *snode,
339 : : const cfg_superedge *last_cfg_superedge,
340 : : region_model_context *ctxt);
341 : :
342 : : void handle_phi (const gphi *phi, tree lhs, tree rhs,
343 : : const region_model &old_state,
344 : : hash_set<const svalue *> &svals_changing_meaning,
345 : : region_model_context *ctxt);
346 : :
347 : : bool maybe_update_for_edge (const superedge &edge,
348 : : const gimple *last_stmt,
349 : : region_model_context *ctxt,
350 : : std::unique_ptr<rejected_constraint> *out);
351 : :
352 : : void update_for_gcall (const gcall *call_stmt,
353 : : region_model_context *ctxt,
354 : : function *callee = NULL);
355 : :
356 : : void update_for_return_gcall (const gcall *call_stmt,
357 : : region_model_context *ctxt);
358 : :
359 : : const region *push_frame (const function &fun, const vec<const svalue *> *arg_sids,
360 : : region_model_context *ctxt);
361 : 8908184 : const frame_region *get_current_frame () const { return m_current_frame; }
362 : : const function *get_current_function () const;
363 : : void pop_frame (tree result_lvalue,
364 : : const svalue **out_result,
365 : : region_model_context *ctxt,
366 : : const gcall *call_stmt,
367 : : bool eval_return_svalue = true);
368 : : int get_stack_depth () const;
369 : : const frame_region *get_frame_at_index (int index) const;
370 : :
371 : : const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
372 : : const region *get_lvalue (tree expr, region_model_context *ctxt) const;
373 : : const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
374 : : const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
375 : :
376 : : const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
377 : : region_model_context *ctxt,
378 : : bool add_nonnull_constraint = true) const;
379 : :
380 : : const svalue *get_rvalue_for_bits (tree type,
381 : : const region *reg,
382 : : const bit_range &bits,
383 : : region_model_context *ctxt) const;
384 : :
385 : : void set_value (const region *lhs_reg, const svalue *rhs_sval,
386 : : region_model_context *ctxt);
387 : : void set_value (tree lhs, tree rhs, region_model_context *ctxt);
388 : : void clobber_region (const region *reg);
389 : : void purge_region (const region *reg);
390 : : void fill_region (const region *reg,
391 : : const svalue *sval,
392 : : region_model_context *ctxt);
393 : : void zero_fill_region (const region *reg,
394 : : region_model_context *ctxt);
395 : : void write_bytes (const region *dest_reg,
396 : : const svalue *num_bytes_sval,
397 : : const svalue *sval,
398 : : region_model_context *ctxt);
399 : : const svalue *read_bytes (const region *src_reg,
400 : : tree src_ptr_expr,
401 : : const svalue *num_bytes_sval,
402 : : region_model_context *ctxt) const;
403 : : void copy_bytes (const region *dest_reg,
404 : : const region *src_reg,
405 : : tree src_ptr_expr,
406 : : const svalue *num_bytes_sval,
407 : : region_model_context *ctxt);
408 : : void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
409 : :
410 : : tristate eval_condition (const svalue *lhs,
411 : : enum tree_code op,
412 : : const svalue *rhs) const;
413 : : tristate compare_initial_and_pointer (const initial_svalue *init,
414 : : const region_svalue *ptr) const;
415 : : tristate symbolic_greater_than (const binop_svalue *a,
416 : : const svalue *b) const;
417 : : tristate structural_equality (const svalue *a, const svalue *b) const;
418 : : tristate eval_condition (tree lhs,
419 : : enum tree_code op,
420 : : tree rhs,
421 : : region_model_context *ctxt) const;
422 : : bool add_constraint (tree lhs, enum tree_code op, tree rhs,
423 : : region_model_context *ctxt);
424 : : bool add_constraint (tree lhs, enum tree_code op, tree rhs,
425 : : region_model_context *ctxt,
426 : : std::unique_ptr<rejected_constraint> *out);
427 : :
428 : : const region *
429 : : get_or_create_region_for_heap_alloc (const svalue *size_in_bytes,
430 : : region_model_context *ctxt,
431 : : bool update_state_machine = false,
432 : : const call_details *cd = nullptr);
433 : :
434 : : const region *create_region_for_alloca (const svalue *size_in_bytes,
435 : : region_model_context *ctxt);
436 : : void get_referenced_base_regions (auto_bitmap &out_ids) const;
437 : :
438 : : tree get_representative_tree (const svalue *sval,
439 : : logger *logger = nullptr) const;
440 : : tree get_representative_tree (const region *reg,
441 : : logger *logger = nullptr) const;
442 : : path_var
443 : : get_representative_path_var (const svalue *sval,
444 : : svalue_set *visited,
445 : : logger *logger) const;
446 : : path_var
447 : : get_representative_path_var (const region *reg,
448 : : svalue_set *visited,
449 : : logger *logger) const;
450 : :
451 : : /* For selftests. */
452 : 611199 : constraint_manager *get_constraints ()
453 : : {
454 : 611199 : return m_constraints;
455 : : }
456 : :
457 : 1188887 : store *get_store () { return &m_store; }
458 : 135744 : const store *get_store () const { return &m_store; }
459 : :
460 : : const dynamic_extents_t &
461 : 289711 : get_dynamic_extents () const
462 : : {
463 : 289711 : return m_dynamic_extents;
464 : : }
465 : : const svalue *get_dynamic_extents (const region *reg) const;
466 : : void set_dynamic_extents (const region *reg,
467 : : const svalue *size_in_bytes,
468 : : region_model_context *ctxt);
469 : : void unset_dynamic_extents (const region *reg);
470 : :
471 : 66953 : region_model_manager *get_manager () const { return m_mgr; }
472 : 8028 : bounded_ranges_manager *get_range_manager () const
473 : : {
474 : 8028 : return m_mgr->get_range_manager ();
475 : : }
476 : :
477 : : void unbind_region_and_descendents (const region *reg,
478 : : enum poison_kind pkind);
479 : :
480 : : bool can_merge_with_p (const region_model &other_model,
481 : : const program_point &point,
482 : : region_model *out_model,
483 : : const extrinsic_state *ext_state = NULL,
484 : : const program_state *state_a = NULL,
485 : : const program_state *state_b = NULL) const;
486 : :
487 : : tree get_fndecl_for_call (const gcall *call,
488 : : region_model_context *ctxt);
489 : :
490 : : void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
491 : : static void append_regions_cb (const region *base_reg,
492 : : struct append_regions_cb_data *data);
493 : :
494 : : const svalue *get_store_value (const region *reg,
495 : : region_model_context *ctxt) const;
496 : : const svalue *get_store_bytes (const region *base_reg,
497 : : const byte_range &bytes,
498 : : region_model_context *ctxt) const;
499 : : const svalue *scan_for_null_terminator (const region *reg,
500 : : tree expr,
501 : : const svalue **out_sval,
502 : : region_model_context *ctxt) const;
503 : : const svalue *scan_for_null_terminator_1 (const region *reg,
504 : : tree expr,
505 : : const svalue **out_sval,
506 : : region_model_context *ctxt) const;
507 : :
508 : : bool region_exists_p (const region *reg) const;
509 : :
510 : : void loop_replay_fixup (const region_model *dst_state);
511 : :
512 : : const svalue *get_capacity (const region *reg) const;
513 : :
514 : : bool replay_call_summary (call_summary_replay &r,
515 : : const region_model &summary);
516 : :
517 : : void maybe_complain_about_infoleak (const region *dst_reg,
518 : : const svalue *copied_sval,
519 : : const region *src_reg,
520 : : region_model_context *ctxt);
521 : :
522 : : void set_errno (const call_details &cd);
523 : :
524 : : /* Implemented in sm-fd.cc */
525 : : void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
526 : :
527 : : /* Implemented in sm-malloc.cc */
528 : : void on_realloc_with_move (const call_details &cd,
529 : : const svalue *old_ptr_sval,
530 : : const svalue *new_ptr_sval);
531 : :
532 : : /* Implemented in sm-malloc.cc. */
533 : : void
534 : : transition_ptr_sval_non_null (region_model_context *ctxt,
535 : : const svalue *new_ptr_sval);
536 : :
537 : : /* Implemented in sm-taint.cc. */
538 : : void mark_as_tainted (const svalue *sval,
539 : : region_model_context *ctxt);
540 : :
541 : : bool add_constraint (const svalue *lhs,
542 : : enum tree_code op,
543 : : const svalue *rhs,
544 : : region_model_context *ctxt);
545 : :
546 : : const svalue *check_for_poison (const svalue *sval,
547 : : tree expr,
548 : : const region *src_region,
549 : : region_model_context *ctxt) const;
550 : :
551 : : void check_region_for_write (const region *dest_reg,
552 : : const svalue *sval_hint,
553 : : region_model_context *ctxt) const;
554 : :
555 : : const svalue *
556 : : check_for_null_terminated_string_arg (const call_details &cd,
557 : : unsigned idx) const;
558 : : const svalue *
559 : : check_for_null_terminated_string_arg (const call_details &cd,
560 : : unsigned idx,
561 : : bool include_terminator,
562 : : const svalue **out_sval) const;
563 : :
564 : : const builtin_known_function *
565 : : get_builtin_kf (const gcall *call,
566 : : region_model_context *ctxt = NULL) const;
567 : :
568 : : static void
569 : : register_pop_frame_callback (const pop_frame_callback &callback)
570 : : {
571 : : pop_frame_callbacks.safe_push (callback);
572 : : }
573 : :
574 : : static void
575 : 18106 : notify_on_pop_frame (const region_model *model,
576 : : const region_model *prev_model,
577 : : const svalue *retval,
578 : : region_model_context *ctxt)
579 : : {
580 : 18109 : for (auto &callback : pop_frame_callbacks)
581 : 1 : callback (model, prev_model, retval, ctxt);
582 : 18106 : }
583 : :
584 : : bool called_from_main_p () const;
585 : :
586 : : private:
587 : : const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
588 : : const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
589 : :
590 : : path_var
591 : : get_representative_path_var_1 (const svalue *sval,
592 : : svalue_set *visited,
593 : : logger *logger) const;
594 : : path_var
595 : : get_representative_path_var_1 (const region *reg,
596 : : svalue_set *visited,
597 : : logger *logger) const;
598 : :
599 : : const known_function *get_known_function (tree fndecl,
600 : : const call_details &cd) const;
601 : : const known_function *get_known_function (enum internal_fn) const;
602 : :
603 : : bool add_constraints_from_binop (const svalue *outer_lhs,
604 : : enum tree_code outer_op,
605 : : const svalue *outer_rhs,
606 : : bool *out,
607 : : region_model_context *ctxt);
608 : :
609 : : void update_for_call_superedge (const call_superedge &call_edge,
610 : : region_model_context *ctxt);
611 : : void update_for_return_superedge (const return_superedge &return_edge,
612 : : region_model_context *ctxt);
613 : : bool apply_constraints_for_gcond (const cfg_superedge &edge,
614 : : const gcond *cond_stmt,
615 : : region_model_context *ctxt,
616 : : std::unique_ptr<rejected_constraint> *out);
617 : : bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
618 : : const gswitch *switch_stmt,
619 : : region_model_context *ctxt,
620 : : std::unique_ptr<rejected_constraint> *out);
621 : : bool apply_constraints_for_ggoto (const cfg_superedge &edge,
622 : : const ggoto *goto_stmt,
623 : : region_model_context *ctxt);
624 : : bool apply_constraints_for_exception (const gimple *last_stmt,
625 : : region_model_context *ctxt,
626 : : std::unique_ptr<rejected_constraint> *out);
627 : :
628 : : int poison_any_pointers_to_descendents (const region *reg,
629 : : enum poison_kind pkind);
630 : :
631 : : void on_top_level_param (tree param,
632 : : bool nonnull,
633 : : region_model_context *ctxt);
634 : :
635 : : const svalue *get_initial_value_for_global (const region *reg) const;
636 : :
637 : : const region * get_region_for_poisoned_expr (tree expr) const;
638 : :
639 : : void check_dynamic_size_for_taint (enum memory_space mem_space,
640 : : const svalue *size_in_bytes,
641 : : region_model_context *ctxt) const;
642 : : void check_dynamic_size_for_floats (const svalue *size_in_bytes,
643 : : region_model_context *ctxt) const;
644 : :
645 : : void check_region_for_taint (const region *reg,
646 : : enum access_direction dir,
647 : : region_model_context *ctxt) const;
648 : :
649 : : void check_for_writable_region (const region* dest_reg,
650 : : region_model_context *ctxt) const;
651 : : bool check_region_access (const region *reg,
652 : : enum access_direction dir,
653 : : const svalue *sval_hint,
654 : : region_model_context *ctxt) const;
655 : : bool check_region_for_read (const region *src_reg,
656 : : region_model_context *ctxt) const;
657 : : void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
658 : : region_model_context *ctxt) const;
659 : :
660 : : /* Implemented in bounds-checking.cc */
661 : : bool check_symbolic_bounds (const region *base_reg,
662 : : const svalue *sym_byte_offset,
663 : : const svalue *num_bytes_sval,
664 : : const svalue *capacity,
665 : : enum access_direction dir,
666 : : const svalue *sval_hint,
667 : : region_model_context *ctxt) const;
668 : : bool check_region_bounds (const region *reg, enum access_direction dir,
669 : : const svalue *sval_hint,
670 : : region_model_context *ctxt) const;
671 : :
672 : : void check_call_args (const call_details &cd) const;
673 : : void check_call_format_attr (const call_details &cd,
674 : : tree format_attr) const;
675 : : void check_function_attr_access (const gcall *call,
676 : : tree callee_fndecl,
677 : : region_model_context *ctxt,
678 : : rdwr_map &rdwr_idx) const;
679 : : void check_function_attr_null_terminated_string_arg (const gcall *call,
680 : : tree callee_fndecl,
681 : : region_model_context *ctxt,
682 : : rdwr_map &rdwr_idx);
683 : : void check_one_function_attr_null_terminated_string_arg (const gcall *call,
684 : : tree callee_fndecl,
685 : : region_model_context *ctxt,
686 : : rdwr_map &rdwr_idx,
687 : : tree attr);
688 : : void check_function_attrs (const gcall *call,
689 : : tree callee_fndecl,
690 : : region_model_context *ctxt);
691 : :
692 : : static auto_vec<pop_frame_callback> pop_frame_callbacks;
693 : : /* Storing this here to avoid passing it around everywhere. */
694 : : region_model_manager *const m_mgr;
695 : :
696 : : store m_store;
697 : :
698 : : constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
699 : :
700 : : const frame_region *m_current_frame;
701 : :
702 : : /* Map from base region to size in bytes, for tracking the sizes of
703 : : dynamically-allocated regions.
704 : : This is part of the region_model rather than the region to allow for
705 : : memory regions to be resized (e.g. by realloc). */
706 : : dynamic_extents_t m_dynamic_extents;
707 : : };
708 : :
709 : : /* Some region_model activity could lead to warnings (e.g. attempts to use an
710 : : uninitialized value). This abstract base class encapsulates an interface
711 : : for the region model to use when emitting such warnings.
712 : :
713 : : Having this as an abstract base class allows us to support the various
714 : : operations needed by program_state in the analyzer within region_model,
715 : : whilst keeping them somewhat modularized. */
716 : :
717 : 1416238 : class region_model_context
718 : : {
719 : : public:
720 : : /* Hook for clients to store pending diagnostics.
721 : : Return true if the diagnostic was stored, or false if it was deleted.
722 : : Optionally provide a custom stmt_finder. */
723 : : virtual bool warn (std::unique_ptr<pending_diagnostic> d,
724 : : const stmt_finder *custom_finder = NULL) = 0;
725 : :
726 : : /* Hook for clients to add a note to the last previously stored
727 : : pending diagnostic. */
728 : : virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
729 : :
730 : : /* Hook for clients to add an event to the last previously stored
731 : : pending diagnostic. */
732 : : virtual void add_event (std::unique_ptr<checker_event> event) = 0;
733 : :
734 : : /* Hook for clients to be notified when an SVAL that was reachable
735 : : in a previous state is no longer live, so that clients can emit warnings
736 : : about leaks. */
737 : : virtual void on_svalue_leak (const svalue *sval) = 0;
738 : :
739 : : /* Hook for clients to be notified when the set of explicitly live
740 : : svalues changes, so that they can purge state relating to dead
741 : : svalues. */
742 : : virtual void on_liveness_change (const svalue_set &live_svalues,
743 : : const region_model *model) = 0;
744 : :
745 : : virtual logger *get_logger () = 0;
746 : :
747 : : /* Hook for clients to be notified when the condition
748 : : "LHS OP RHS" is added to the region model.
749 : : This exists so that state machines can detect tests on edges,
750 : : and use them to trigger sm-state transitions (e.g. transitions due
751 : : to ptrs becoming known to be NULL or non-NULL, rather than just
752 : : "unchecked") */
753 : : virtual void on_condition (const svalue *lhs,
754 : : enum tree_code op,
755 : : const svalue *rhs) = 0;
756 : :
757 : : /* Hook for clients to be notified when the condition that
758 : : SVAL is within RANGES is added to the region model.
759 : : Similar to on_condition, but for use when handling switch statements.
760 : : RANGES is non-empty. */
761 : : virtual void on_bounded_ranges (const svalue &sval,
762 : : const bounded_ranges &ranges) = 0;
763 : :
764 : : /* Hook for clients to be notified when a frame is popped from the stack. */
765 : : virtual void on_pop_frame (const frame_region *) = 0;
766 : :
767 : : /* Hooks for clients to be notified when an unknown change happens
768 : : to SVAL (in response to a call to an unknown function). */
769 : : virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
770 : :
771 : : /* Hooks for clients to be notified when a phi node is handled,
772 : : where RHS is the pertinent argument. */
773 : : virtual void on_phi (const gphi *phi, tree rhs) = 0;
774 : :
775 : : /* Hooks for clients to be notified when the region model doesn't
776 : : know how to handle the tree code of T at LOC. */
777 : : virtual void on_unexpected_tree_code (tree t,
778 : : const dump_location_t &loc) = 0;
779 : :
780 : : /* Hook for clients to be notified when a function_decl escapes. */
781 : : virtual void on_escaped_function (tree fndecl) = 0;
782 : :
783 : : virtual uncertainty_t *get_uncertainty () = 0;
784 : :
785 : : /* Hook for clients to purge state involving SVAL. */
786 : : virtual void purge_state_involving (const svalue *sval) = 0;
787 : :
788 : : /* Hook for clients to split state with a non-standard path. */
789 : : virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
790 : :
791 : : /* Hook for clients to terminate the standard path. */
792 : : virtual void terminate_path () = 0;
793 : :
794 : : virtual const extrinsic_state *get_ext_state () const = 0;
795 : :
796 : : /* Hook for clients to access the a specific state machine in
797 : : any underlying program_state. */
798 : : virtual bool
799 : : get_state_map_by_name (const char *name,
800 : : sm_state_map **out_smap,
801 : : const state_machine **out_sm,
802 : : unsigned *out_sm_idx,
803 : : std::unique_ptr<sm_context> *out_sm_context) = 0;
804 : :
805 : : /* Precanned ways for clients to access specific state machines. */
806 : 796 : bool get_fd_map (sm_state_map **out_smap,
807 : : const state_machine **out_sm,
808 : : unsigned *out_sm_idx,
809 : : std::unique_ptr<sm_context> *out_sm_context)
810 : : {
811 : 796 : return get_state_map_by_name ("file-descriptor", out_smap, out_sm,
812 : : out_sm_idx, out_sm_context);
813 : : }
814 : 308 : bool get_malloc_map (sm_state_map **out_smap,
815 : : const state_machine **out_sm,
816 : : unsigned *out_sm_idx)
817 : : {
818 : 308 : return get_state_map_by_name ("malloc", out_smap, out_sm, out_sm_idx, NULL);
819 : : }
820 : 690588 : bool get_taint_map (sm_state_map **out_smap,
821 : : const state_machine **out_sm,
822 : : unsigned *out_sm_idx)
823 : : {
824 : 690588 : return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx, NULL);
825 : : }
826 : :
827 : : bool possibly_tainted_p (const svalue *sval);
828 : :
829 : : /* Get the current statement, if any. */
830 : : virtual const gimple *get_stmt () const = 0;
831 : :
832 : : virtual const exploded_graph *get_eg () const = 0;
833 : :
834 : : /* Hooks for detecting infinite loops. */
835 : : virtual void maybe_did_work () = 0;
836 : : virtual bool checking_for_infinite_loop_p () const = 0;
837 : : virtual void on_unusable_in_infinite_loop () = 0;
838 : : };
839 : :
840 : : /* A "do nothing" subclass of region_model_context. */
841 : :
842 : 21752 : class noop_region_model_context : public region_model_context
843 : : {
844 : : public:
845 : 10 : bool warn (std::unique_ptr<pending_diagnostic>,
846 : 10 : const stmt_finder *) override { return false; }
847 : : void add_note (std::unique_ptr<pending_note>) override;
848 : : void add_event (std::unique_ptr<checker_event>) override;
849 : 0 : void on_svalue_leak (const svalue *) override {}
850 : 0 : void on_liveness_change (const svalue_set &,
851 : 0 : const region_model *) override {}
852 : 21208 : logger *get_logger () override { return NULL; }
853 : 44 : void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
854 : : enum tree_code op ATTRIBUTE_UNUSED,
855 : : const svalue *rhs ATTRIBUTE_UNUSED) override
856 : : {
857 : 44 : }
858 : 115 : void on_bounded_ranges (const svalue &,
859 : : const bounded_ranges &) override
860 : : {
861 : 115 : }
862 : 166 : void on_pop_frame (const frame_region *) override {}
863 : 0 : void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
864 : : bool is_mutable ATTRIBUTE_UNUSED) override
865 : : {
866 : 0 : }
867 : 6967 : void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
868 : : tree rhs ATTRIBUTE_UNUSED) override
869 : : {
870 : 6967 : }
871 : 0 : void on_unexpected_tree_code (tree, const dump_location_t &) override {}
872 : :
873 : 0 : void on_escaped_function (tree) override {}
874 : :
875 : 7282 : uncertainty_t *get_uncertainty () override { return NULL; }
876 : :
877 : 8 : void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
878 : :
879 : : void bifurcate (std::unique_ptr<custom_edge_info> info) override;
880 : : void terminate_path () override;
881 : :
882 : 2694 : const extrinsic_state *get_ext_state () const override { return NULL; }
883 : :
884 : 21192 : bool get_state_map_by_name (const char *,
885 : : sm_state_map **,
886 : : const state_machine **,
887 : : unsigned *,
888 : : std::unique_ptr<sm_context> *) override
889 : : {
890 : 21192 : return false;
891 : : }
892 : :
893 : 7235 : const gimple *get_stmt () const override { return NULL; }
894 : 0 : const exploded_graph *get_eg () const override { return NULL; }
895 : 1 : void maybe_did_work () override {}
896 : 44 : bool checking_for_infinite_loop_p () const override { return false; }
897 : 0 : void on_unusable_in_infinite_loop () override {}
898 : : };
899 : :
900 : : /* A subclass of region_model_context for determining if operations fail
901 : : e.g. "can we generate a region for the lvalue of EXPR?". */
902 : :
903 : : class tentative_region_model_context : public noop_region_model_context
904 : : {
905 : : public:
906 : : tentative_region_model_context () : m_num_unexpected_codes (0) {}
907 : :
908 : 0 : void on_unexpected_tree_code (tree, const dump_location_t &)
909 : : final override
910 : : {
911 : 0 : m_num_unexpected_codes++;
912 : 0 : }
913 : :
914 : : bool had_errors_p () const { return m_num_unexpected_codes > 0; }
915 : :
916 : : private:
917 : : int m_num_unexpected_codes;
918 : : };
919 : :
920 : : /* Subclass of region_model_context that wraps another context, allowing
921 : : for extra code to be added to the various hooks. */
922 : :
923 : : class region_model_context_decorator : public region_model_context
924 : : {
925 : : public:
926 : 0 : bool warn (std::unique_ptr<pending_diagnostic> d,
927 : : const stmt_finder *custom_finder) override
928 : : {
929 : 0 : if (m_inner)
930 : 0 : return m_inner->warn (std::move (d), custom_finder);
931 : : else
932 : : return false;
933 : : }
934 : :
935 : 215 : void add_note (std::unique_ptr<pending_note> pn) override
936 : : {
937 : 215 : if (m_inner)
938 : 215 : m_inner->add_note (std::move (pn));
939 : 215 : }
940 : : void add_event (std::unique_ptr<checker_event> event) override;
941 : :
942 : 0 : void on_svalue_leak (const svalue *sval) override
943 : : {
944 : 0 : if (m_inner)
945 : 0 : m_inner->on_svalue_leak (sval);
946 : 0 : }
947 : :
948 : 0 : void on_liveness_change (const svalue_set &live_svalues,
949 : : const region_model *model) override
950 : : {
951 : 0 : if (m_inner)
952 : 0 : m_inner->on_liveness_change (live_svalues, model);
953 : 0 : }
954 : :
955 : 24917 : logger *get_logger () override
956 : : {
957 : 24917 : if (m_inner)
958 : 15977 : return m_inner->get_logger ();
959 : : else
960 : : return nullptr;
961 : : }
962 : :
963 : 0 : void on_condition (const svalue *lhs,
964 : : enum tree_code op,
965 : : const svalue *rhs) override
966 : : {
967 : 0 : if (m_inner)
968 : 0 : m_inner->on_condition (lhs, op, rhs);
969 : 0 : }
970 : :
971 : 0 : void on_bounded_ranges (const svalue &sval,
972 : : const bounded_ranges &ranges) override
973 : : {
974 : 0 : if (m_inner)
975 : 0 : m_inner->on_bounded_ranges (sval, ranges);
976 : 0 : }
977 : :
978 : 0 : void on_pop_frame (const frame_region *frame_reg) override
979 : : {
980 : 0 : if (m_inner)
981 : 0 : m_inner->on_pop_frame (frame_reg);
982 : 0 : }
983 : :
984 : 0 : void on_unknown_change (const svalue *sval, bool is_mutable) override
985 : : {
986 : 0 : if (m_inner)
987 : 0 : m_inner->on_unknown_change (sval, is_mutable);
988 : 0 : }
989 : :
990 : 0 : void on_phi (const gphi *phi, tree rhs) override
991 : : {
992 : 0 : if (m_inner)
993 : 0 : m_inner->on_phi (phi, rhs);
994 : 0 : }
995 : :
996 : 0 : void on_unexpected_tree_code (tree t,
997 : : const dump_location_t &loc) override
998 : : {
999 : 0 : if (m_inner)
1000 : 0 : m_inner->on_unexpected_tree_code (t, loc);
1001 : 0 : }
1002 : :
1003 : 0 : void on_escaped_function (tree fndecl) override
1004 : : {
1005 : 0 : if (m_inner)
1006 : 0 : m_inner->on_escaped_function (fndecl);
1007 : 0 : }
1008 : :
1009 : 3629 : uncertainty_t *get_uncertainty () override
1010 : : {
1011 : 3629 : if (m_inner)
1012 : 2719 : return m_inner->get_uncertainty ();
1013 : : else
1014 : : return nullptr;
1015 : : }
1016 : :
1017 : 0 : void purge_state_involving (const svalue *sval) override
1018 : : {
1019 : 0 : if (m_inner)
1020 : 0 : m_inner->purge_state_involving (sval);
1021 : 0 : }
1022 : :
1023 : 0 : void bifurcate (std::unique_ptr<custom_edge_info> info) override
1024 : : {
1025 : 0 : if (m_inner)
1026 : 0 : m_inner->bifurcate (std::move (info));
1027 : 0 : }
1028 : :
1029 : 0 : void terminate_path () override
1030 : : {
1031 : 0 : if (m_inner)
1032 : 0 : m_inner->terminate_path ();
1033 : 0 : }
1034 : :
1035 : 4421 : const extrinsic_state *get_ext_state () const override
1036 : : {
1037 : 4421 : if (m_inner)
1038 : 4421 : return m_inner->get_ext_state ();
1039 : : else
1040 : : return nullptr;
1041 : : }
1042 : :
1043 : 6813 : bool get_state_map_by_name (const char *name,
1044 : : sm_state_map **out_smap,
1045 : : const state_machine **out_sm,
1046 : : unsigned *out_sm_idx,
1047 : : std::unique_ptr<sm_context> *out_sm_context)
1048 : : override
1049 : : {
1050 : 6813 : if (m_inner)
1051 : 4457 : return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx,
1052 : 4457 : out_sm_context);
1053 : : else
1054 : : return false;
1055 : : }
1056 : :
1057 : 97 : const gimple *get_stmt () const override
1058 : : {
1059 : 97 : if (m_inner)
1060 : 97 : return m_inner->get_stmt ();
1061 : : else
1062 : : return nullptr;
1063 : : }
1064 : :
1065 : 0 : const exploded_graph *get_eg () const override
1066 : : {
1067 : 0 : if (m_inner)
1068 : 0 : return m_inner->get_eg ();
1069 : : else
1070 : : return nullptr;
1071 : : }
1072 : :
1073 : 0 : void maybe_did_work () override
1074 : : {
1075 : 0 : if (m_inner)
1076 : 0 : m_inner->maybe_did_work ();
1077 : 0 : }
1078 : :
1079 : 0 : bool checking_for_infinite_loop_p () const override
1080 : : {
1081 : 0 : if (m_inner)
1082 : 0 : return m_inner->checking_for_infinite_loop_p ();
1083 : : return false;
1084 : : }
1085 : 0 : void on_unusable_in_infinite_loop () override
1086 : : {
1087 : 0 : if (m_inner)
1088 : 0 : m_inner->on_unusable_in_infinite_loop ();
1089 : 0 : }
1090 : :
1091 : : protected:
1092 : 12723 : region_model_context_decorator (region_model_context *inner)
1093 : 3629 : : m_inner (inner)
1094 : : {
1095 : : }
1096 : :
1097 : : region_model_context *m_inner;
1098 : : };
1099 : :
1100 : : /* Subclass of region_model_context_decorator with a hook for adding
1101 : : notes/events when saving diagnostics. */
1102 : :
1103 : : class annotating_context : public region_model_context_decorator
1104 : : {
1105 : : public:
1106 : 214 : bool warn (std::unique_ptr<pending_diagnostic> d,
1107 : : const stmt_finder *custom_finder) override
1108 : : {
1109 : 214 : if (m_inner)
1110 : 210 : if (m_inner->warn (std::move (d), custom_finder))
1111 : : {
1112 : 206 : add_annotations ();
1113 : 206 : return true;
1114 : : }
1115 : : return false;
1116 : : }
1117 : :
1118 : : /* Hook to add new event(s)/note(s) */
1119 : : virtual void add_annotations () = 0;
1120 : :
1121 : : protected:
1122 : 9094 : annotating_context (region_model_context *inner)
1123 : 9094 : : region_model_context_decorator (inner)
1124 : : {
1125 : : }
1126 : : };
1127 : :
1128 : : /* A bundle of data for use when attempting to merge two region_model
1129 : : instances to make a third. */
1130 : :
1131 : 151668 : struct model_merger
1132 : : {
1133 : 151668 : model_merger (const region_model *model_a,
1134 : : const region_model *model_b,
1135 : : const program_point &point,
1136 : : region_model *merged_model,
1137 : : const extrinsic_state *ext_state,
1138 : : const program_state *state_a,
1139 : : const program_state *state_b)
1140 : 151668 : : m_model_a (model_a), m_model_b (model_b),
1141 : 151668 : m_point (point),
1142 : 151668 : m_merged_model (merged_model),
1143 : 151668 : m_ext_state (ext_state),
1144 : 151668 : m_state_a (state_a), m_state_b (state_b)
1145 : : {
1146 : : }
1147 : :
1148 : : void dump_to_pp (pretty_printer *pp, bool simple) const;
1149 : : void dump (FILE *fp, bool simple) const;
1150 : : void dump (bool simple) const;
1151 : :
1152 : : region_model_manager *get_manager () const
1153 : : {
1154 : : return m_model_a->get_manager ();
1155 : : }
1156 : :
1157 : : bool mergeable_svalue_p (const svalue *) const;
1158 : 3238 : const function_point &get_function_point () const
1159 : : {
1160 : 3238 : return m_point.get_function_point ();
1161 : : }
1162 : :
1163 : : void on_widening_reuse (const widening_svalue *widening_sval);
1164 : :
1165 : : const region_model *m_model_a;
1166 : : const region_model *m_model_b;
1167 : : const program_point &m_point;
1168 : : region_model *m_merged_model;
1169 : :
1170 : : const extrinsic_state *m_ext_state;
1171 : : const program_state *m_state_a;
1172 : : const program_state *m_state_b;
1173 : :
1174 : : hash_set<const svalue *> m_svals_changing_meaning;
1175 : : };
1176 : :
1177 : : /* A record that can (optionally) be written out when
1178 : : region_model::add_constraint fails. */
1179 : :
1180 : : class rejected_constraint
1181 : : {
1182 : : public:
1183 : : virtual ~rejected_constraint () {}
1184 : : virtual void dump_to_pp (pretty_printer *pp) const = 0;
1185 : :
1186 : 4 : const region_model &get_model () const { return m_model; }
1187 : :
1188 : : protected:
1189 : 2014 : rejected_constraint (const region_model &model)
1190 : 2014 : : m_model (model)
1191 : : {}
1192 : :
1193 : : region_model m_model;
1194 : : };
1195 : :
1196 : : class rejected_op_constraint : public rejected_constraint
1197 : : {
1198 : : public:
1199 : 1916 : rejected_op_constraint (const region_model &model,
1200 : : tree lhs, enum tree_code op, tree rhs)
1201 : 1916 : : rejected_constraint (model),
1202 : 1916 : m_lhs (lhs), m_op (op), m_rhs (rhs)
1203 : : {}
1204 : :
1205 : : void dump_to_pp (pretty_printer *pp) const final override;
1206 : :
1207 : : tree m_lhs;
1208 : : enum tree_code m_op;
1209 : : tree m_rhs;
1210 : : };
1211 : :
1212 : : class rejected_default_case : public rejected_constraint
1213 : : {
1214 : : public:
1215 : 0 : rejected_default_case (const region_model &model)
1216 : 0 : : rejected_constraint (model)
1217 : : {}
1218 : :
1219 : : void dump_to_pp (pretty_printer *pp) const final override;
1220 : : };
1221 : :
1222 : : class rejected_ranges_constraint : public rejected_constraint
1223 : : {
1224 : : public:
1225 : 98 : rejected_ranges_constraint (const region_model &model,
1226 : : tree expr, const bounded_ranges *ranges)
1227 : 98 : : rejected_constraint (model),
1228 : 98 : m_expr (expr), m_ranges (ranges)
1229 : : {}
1230 : :
1231 : : void dump_to_pp (pretty_printer *pp) const final override;
1232 : :
1233 : : private:
1234 : : tree m_expr;
1235 : : const bounded_ranges *m_ranges;
1236 : : };
1237 : :
1238 : : /* A bundle of state. */
1239 : :
1240 : 3219 : class engine
1241 : : {
1242 : : public:
1243 : : engine (const supergraph *sg = NULL, logger *logger = NULL);
1244 : 319151 : const supergraph *get_supergraph () { return m_sg; }
1245 : 11512010 : region_model_manager *get_model_manager () { return &m_mgr; }
1246 : 6398 : known_function_manager *get_known_function_manager ()
1247 : : {
1248 : 3199 : return m_mgr.get_known_function_manager ();
1249 : : }
1250 : :
1251 : : void log_stats (logger *logger) const;
1252 : :
1253 : : private:
1254 : : const supergraph *m_sg;
1255 : : region_model_manager m_mgr;
1256 : : };
1257 : :
1258 : : } // namespace ana
1259 : :
1260 : : extern void debug (const region_model &rmodel);
1261 : :
1262 : : namespace ana {
1263 : :
1264 : : #if CHECKING_P
1265 : :
1266 : : namespace selftest {
1267 : :
1268 : : using namespace ::selftest;
1269 : :
1270 : : /* An implementation of region_model_context for use in selftests, which
1271 : : stores any pending_diagnostic instances passed to it. */
1272 : :
1273 : 228 : class test_region_model_context : public noop_region_model_context
1274 : : {
1275 : : public:
1276 : 4 : bool warn (std::unique_ptr<pending_diagnostic> d,
1277 : : const stmt_finder *) final override
1278 : : {
1279 : 4 : m_diagnostics.safe_push (d.release ());
1280 : 4 : return true;
1281 : : }
1282 : :
1283 : 4 : unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1284 : :
1285 : 0 : void on_unexpected_tree_code (tree t, const dump_location_t &)
1286 : : final override
1287 : : {
1288 : 0 : internal_error ("unhandled tree code: %qs",
1289 : 0 : get_tree_code_name (TREE_CODE (t)));
1290 : : }
1291 : :
1292 : : private:
1293 : : /* Implicitly delete any diagnostics in the dtor. */
1294 : : auto_delete_vec<pending_diagnostic> m_diagnostics;
1295 : : };
1296 : :
1297 : : /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1298 : : Verify that MODEL remains satisfiable. */
1299 : :
1300 : : #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1301 : : SELFTEST_BEGIN_STMT \
1302 : : bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1303 : : ASSERT_TRUE (sat); \
1304 : : SELFTEST_END_STMT
1305 : :
1306 : : /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1307 : : Verify that the result is not satisfiable. */
1308 : :
1309 : : #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1310 : : SELFTEST_BEGIN_STMT \
1311 : : bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1312 : : ASSERT_FALSE (sat); \
1313 : : SELFTEST_END_STMT
1314 : :
1315 : : /* Implementation detail of the ASSERT_CONDITION_* macros. */
1316 : :
1317 : : void assert_condition (const location &loc,
1318 : : region_model &model,
1319 : : const svalue *lhs, tree_code op, const svalue *rhs,
1320 : : tristate expected);
1321 : :
1322 : : void assert_condition (const location &loc,
1323 : : region_model &model,
1324 : : tree lhs, tree_code op, tree rhs,
1325 : : tristate expected);
1326 : :
1327 : : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1328 : : as "true". */
1329 : :
1330 : : #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1331 : : SELFTEST_BEGIN_STMT \
1332 : : assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1333 : : tristate (tristate::TS_TRUE)); \
1334 : : SELFTEST_END_STMT
1335 : :
1336 : : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1337 : : as "false". */
1338 : :
1339 : : #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1340 : : SELFTEST_BEGIN_STMT \
1341 : : assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1342 : : tristate (tristate::TS_FALSE)); \
1343 : : SELFTEST_END_STMT
1344 : :
1345 : : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1346 : : as "unknown". */
1347 : :
1348 : : #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1349 : : SELFTEST_BEGIN_STMT \
1350 : : assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1351 : : tristate (tristate::TS_UNKNOWN)); \
1352 : : SELFTEST_END_STMT
1353 : :
1354 : : } /* end of namespace selftest. */
1355 : :
1356 : : #endif /* #if CHECKING_P */
1357 : :
1358 : : } // namespace ana
1359 : :
1360 : : #endif /* GCC_ANALYZER_REGION_MODEL_H */
|