1 /* Classes for modeling the state of memory.
2 Copyright (C) 2019-2022 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
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 "analyzer/svalue.h"
30 #include "analyzer/region.h"
31
32 using namespace ana;
33
34 namespace inchash
35 {
36 extern void add_path_var (path_var pv, hash &hstate);
37 } // namespace inchash
38
39 namespace ana {
40
41 template <typename T>
42 class one_way_id_map
43 {
44 public:
45 one_way_id_map (int num_ids);
46 void put (T src, T dst);
47 T get_dst_for_src (T src) const;
48 void dump_to_pp (pretty_printer *pp) const;
49 void dump () const;
50 void update (T *) const;
51
52 private:
53 auto_vec<T> m_src_to_dst;
54 };
55
56 /* class one_way_id_map. */
57
58 /* one_way_id_map's ctor, which populates the map with dummy null values. */
59
60 template <typename T>
one_way_id_map(int num_svalues)61 inline one_way_id_map<T>::one_way_id_map (int num_svalues)
62 : m_src_to_dst (num_svalues)
63 {
64 for (int i = 0; i < num_svalues; i++)
65 m_src_to_dst.quick_push (T::null ());
66 }
67
68 /* Record that SRC is to be mapped to DST. */
69
70 template <typename T>
71 inline void
put(T src,T dst)72 one_way_id_map<T>::put (T src, T dst)
73 {
74 m_src_to_dst[src.as_int ()] = dst;
75 }
76
77 /* Get the new value for SRC within the map. */
78
79 template <typename T>
80 inline T
get_dst_for_src(T src)81 one_way_id_map<T>::get_dst_for_src (T src) const
82 {
83 if (src.null_p ())
84 return src;
85 return m_src_to_dst[src.as_int ()];
86 }
87
88 /* Dump this map to PP. */
89
90 template <typename T>
91 inline void
dump_to_pp(pretty_printer * pp)92 one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
93 {
94 pp_string (pp, "src to dst: {");
95 unsigned i;
96 T *dst;
97 FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
98 {
99 if (i > 0)
100 pp_string (pp, ", ");
101 T src (T::from_int (i));
102 src.print (pp);
103 pp_string (pp, " -> ");
104 dst->print (pp);
105 }
106 pp_string (pp, "}");
107 pp_newline (pp);
108 }
109
110 /* Dump this map to stderr. */
111
112 template <typename T>
113 DEBUG_FUNCTION inline void
dump()114 one_way_id_map<T>::dump () const
115 {
116 pretty_printer pp;
117 pp.buffer->stream = stderr;
118 dump_to_pp (&pp);
119 pp_flush (&pp);
120 }
121
122 /* Update *ID from the old value to its new value in this map. */
123
124 template <typename T>
125 inline void
update(T * id)126 one_way_id_map<T>::update (T *id) const
127 {
128 *id = get_dst_for_src (*id);
129 }
130
131 /* A mapping from region to svalue for use when tracking state. */
132
133 class region_to_value_map
134 {
135 public:
136 typedef hash_map<const region *, const svalue *> hash_map_t;
137 typedef hash_map_t::iterator iterator;
138
region_to_value_map()139 region_to_value_map () : m_hash_map () {}
region_to_value_map(const region_to_value_map & other)140 region_to_value_map (const region_to_value_map &other)
141 : m_hash_map (other.m_hash_map) {}
142 region_to_value_map &operator= (const region_to_value_map &other);
143
144 bool operator== (const region_to_value_map &other) const;
145 bool operator!= (const region_to_value_map &other) const
146 {
147 return !(*this == other);
148 }
149
begin()150 iterator begin () const { return m_hash_map.begin (); }
end()151 iterator end () const { return m_hash_map.end (); }
152
get(const region * reg)153 const svalue * const *get (const region *reg) const
154 {
155 return const_cast <hash_map_t &> (m_hash_map).get (reg);
156 }
put(const region * reg,const svalue * sval)157 void put (const region *reg, const svalue *sval)
158 {
159 m_hash_map.put (reg, sval);
160 }
remove(const region * reg)161 void remove (const region *reg)
162 {
163 m_hash_map.remove (reg);
164 }
165
is_empty()166 bool is_empty () const { return m_hash_map.is_empty (); }
167
168 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
169 void dump (bool simple) const;
170
171 bool can_merge_with_p (const region_to_value_map &other,
172 region_to_value_map *out) const;
173
174 void purge_state_involving (const svalue *sval);
175
176 private:
177 hash_map_t m_hash_map;
178 };
179
180 /* Various operations delete information from a region_model.
181
182 This struct tracks how many of each kind of entity were purged (e.g.
183 for selftests, and for debugging). */
184
185 struct purge_stats
186 {
purge_statspurge_stats187 purge_stats ()
188 : m_num_svalues (0),
189 m_num_regions (0),
190 m_num_equiv_classes (0),
191 m_num_constraints (0),
192 m_num_bounded_ranges_constraints (0),
193 m_num_client_items (0)
194 {}
195
196 int m_num_svalues;
197 int m_num_regions;
198 int m_num_equiv_classes;
199 int m_num_constraints;
200 int m_num_bounded_ranges_constraints;
201 int m_num_client_items;
202 };
203
204 /* A base class for visiting regions and svalues, with do-nothing
205 base implementations of the per-subclass vfuncs. */
206
207 class visitor
208 {
209 public:
visit_region_svalue(const region_svalue *)210 virtual void visit_region_svalue (const region_svalue *) {}
visit_constant_svalue(const constant_svalue *)211 virtual void visit_constant_svalue (const constant_svalue *) {}
visit_unknown_svalue(const unknown_svalue *)212 virtual void visit_unknown_svalue (const unknown_svalue *) {}
visit_poisoned_svalue(const poisoned_svalue *)213 virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
visit_setjmp_svalue(const setjmp_svalue *)214 virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
visit_initial_svalue(const initial_svalue *)215 virtual void visit_initial_svalue (const initial_svalue *) {}
visit_unaryop_svalue(const unaryop_svalue *)216 virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
visit_binop_svalue(const binop_svalue *)217 virtual void visit_binop_svalue (const binop_svalue *) {}
visit_sub_svalue(const sub_svalue *)218 virtual void visit_sub_svalue (const sub_svalue *) {}
visit_repeated_svalue(const repeated_svalue *)219 virtual void visit_repeated_svalue (const repeated_svalue *) {}
visit_bits_within_svalue(const bits_within_svalue *)220 virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
visit_unmergeable_svalue(const unmergeable_svalue *)221 virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
visit_placeholder_svalue(const placeholder_svalue *)222 virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
visit_widening_svalue(const widening_svalue *)223 virtual void visit_widening_svalue (const widening_svalue *) {}
visit_compound_svalue(const compound_svalue *)224 virtual void visit_compound_svalue (const compound_svalue *) {}
visit_conjured_svalue(const conjured_svalue *)225 virtual void visit_conjured_svalue (const conjured_svalue *) {}
visit_asm_output_svalue(const asm_output_svalue *)226 virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
visit_const_fn_result_svalue(const const_fn_result_svalue *)227 virtual void visit_const_fn_result_svalue (const const_fn_result_svalue *) {}
228
visit_region(const region *)229 virtual void visit_region (const region *) {}
230 };
231
232 } // namespace ana
233
234 namespace ana {
235
236 /* A class responsible for owning and consolidating region and svalue
237 instances.
238 region and svalue instances are immutable as far as clients are
239 concerned, so they are provided as "const" ptrs. */
240
241 class region_model_manager
242 {
243 public:
244 region_model_manager (logger *logger = NULL);
245 ~region_model_manager ();
246
247 /* svalue consolidation. */
248 const svalue *get_or_create_constant_svalue (tree cst_expr);
249 const svalue *get_or_create_int_cst (tree type, poly_int64);
250 const svalue *get_or_create_null_ptr (tree pointer_type);
251 const svalue *get_or_create_unknown_svalue (tree type);
252 const svalue *get_or_create_setjmp_svalue (const setjmp_record &r,
253 tree type);
254 const svalue *get_or_create_poisoned_svalue (enum poison_kind kind,
255 tree type);
256 const svalue *get_or_create_initial_value (const region *reg);
257 const svalue *get_ptr_svalue (tree ptr_type, const region *pointee);
258 const svalue *get_or_create_unaryop (tree type, enum tree_code op,
259 const svalue *arg);
260 const svalue *get_or_create_cast (tree type, const svalue *arg);
261 const svalue *get_or_create_binop (tree type,
262 enum tree_code op,
263 const svalue *arg0, const svalue *arg1);
264 const svalue *get_or_create_sub_svalue (tree type,
265 const svalue *parent_svalue,
266 const region *subregion);
267 const svalue *get_or_create_repeated_svalue (tree type,
268 const svalue *outer_size,
269 const svalue *inner_svalue);
270 const svalue *get_or_create_bits_within (tree type,
271 const bit_range &bits,
272 const svalue *inner_svalue);
273 const svalue *get_or_create_unmergeable (const svalue *arg);
274 const svalue *get_or_create_widening_svalue (tree type,
275 const program_point &point,
276 const svalue *base_svalue,
277 const svalue *iter_svalue);
278 const svalue *get_or_create_compound_svalue (tree type,
279 const binding_map &map);
280 const svalue *get_or_create_conjured_svalue (tree type, const gimple *stmt,
281 const region *id_reg,
282 const conjured_purge &p);
283 const svalue *
284 get_or_create_asm_output_svalue (tree type,
285 const gasm *asm_stmt,
286 unsigned output_idx,
287 const vec<const svalue *> &inputs);
288 const svalue *
289 get_or_create_const_fn_result_svalue (tree type,
290 tree fndecl,
291 const vec<const svalue *> &inputs);
292
293 const svalue *maybe_get_char_from_string_cst (tree string_cst,
294 tree byte_offset_cst);
295
296 /* Dynamically-allocated svalue instances.
297 The number of these within the analysis can grow arbitrarily.
298 They are still owned by the manager. */
299 const svalue *create_unique_svalue (tree type);
300
301 /* region consolidation. */
get_stack_region()302 const stack_region * get_stack_region () const { return &m_stack_region; }
get_heap_region()303 const heap_region *get_heap_region () const { return &m_heap_region; }
get_code_region()304 const code_region *get_code_region () const { return &m_code_region; }
get_globals_region()305 const globals_region *get_globals_region () const
306 {
307 return &m_globals_region;
308 }
309 const function_region *get_region_for_fndecl (tree fndecl);
310 const label_region *get_region_for_label (tree label);
311 const decl_region *get_region_for_global (tree expr);
312 const region *get_field_region (const region *parent, tree field);
313 const region *get_element_region (const region *parent,
314 tree element_type,
315 const svalue *index);
316 const region *get_offset_region (const region *parent,
317 tree type,
318 const svalue *byte_offset);
319 const region *get_sized_region (const region *parent,
320 tree type,
321 const svalue *byte_size_sval);
322 const region *get_cast_region (const region *original_region,
323 tree type);
324 const frame_region *get_frame_region (const frame_region *calling_frame,
325 function *fun);
326 const region *get_symbolic_region (const svalue *sval);
327 const string_region *get_region_for_string (tree string_cst);
328 const region *get_bit_range (const region *parent, tree type,
329 const bit_range &bits);
330
331 const region *get_unknown_symbolic_region (tree region_type);
332
333 const region *
334 get_region_for_unexpected_tree_code (region_model_context *ctxt,
335 tree t,
336 const dump_location_t &loc);
337
alloc_region_id()338 unsigned alloc_region_id () { return m_next_region_id++; }
339
get_store_manager()340 store_manager *get_store_manager () { return &m_store_mgr; }
get_range_manager()341 bounded_ranges_manager *get_range_manager () const { return m_range_mgr; }
342
343 /* Dynamically-allocated region instances.
344 The number of these within the analysis can grow arbitrarily.
345 They are still owned by the manager. */
346 const region *create_region_for_heap_alloc ();
347 const region *create_region_for_alloca (const frame_region *frame);
348
349 void log_stats (logger *logger, bool show_objs) const;
350
begin_checking_feasibility(void)351 void begin_checking_feasibility (void) { m_checking_feasibility = true; }
end_checking_feasibility(void)352 void end_checking_feasibility (void) { m_checking_feasibility = false; }
353
get_logger()354 logger *get_logger () const { return m_logger; }
355
356 void dump_untracked_regions () const;
357
358 private:
359 bool too_complex_p (const complexity &c) const;
360 bool reject_if_too_complex (svalue *sval);
361
362 const svalue *maybe_fold_unaryop (tree type, enum tree_code op,
363 const svalue *arg);
364 const svalue *maybe_fold_binop (tree type, enum tree_code op,
365 const svalue *arg0, const svalue *arg1);
366 const svalue *maybe_fold_sub_svalue (tree type,
367 const svalue *parent_svalue,
368 const region *subregion);
369 const svalue *maybe_fold_repeated_svalue (tree type,
370 const svalue *outer_size,
371 const svalue *inner_svalue);
372 const svalue *maybe_fold_bits_within_svalue (tree type,
373 const bit_range &bits,
374 const svalue *inner_svalue);
375 const svalue *maybe_undo_optimize_bit_field_compare (tree type,
376 const compound_svalue *compound_sval,
377 tree cst, const svalue *arg1);
378 const svalue *maybe_fold_asm_output_svalue (tree type,
379 const vec<const svalue *> &inputs);
380
381 logger *m_logger;
382
383 unsigned m_next_region_id;
384 root_region m_root_region;
385 stack_region m_stack_region;
386 heap_region m_heap_region;
387
388 /* svalue consolidation. */
389 typedef hash_map<tree, constant_svalue *> constants_map_t;
390 constants_map_t m_constants_map;
391
392 typedef hash_map<tree, unknown_svalue *> unknowns_map_t;
393 unknowns_map_t m_unknowns_map;
394 const unknown_svalue *m_unknown_NULL;
395
396 typedef hash_map<poisoned_svalue::key_t,
397 poisoned_svalue *> poisoned_values_map_t;
398 poisoned_values_map_t m_poisoned_values_map;
399
400 typedef hash_map<setjmp_svalue::key_t,
401 setjmp_svalue *> setjmp_values_map_t;
402 setjmp_values_map_t m_setjmp_values_map;
403
404 typedef hash_map<const region *, initial_svalue *> initial_values_map_t;
405 initial_values_map_t m_initial_values_map;
406
407 typedef hash_map<region_svalue::key_t, region_svalue *> pointer_values_map_t;
408 pointer_values_map_t m_pointer_values_map;
409
410 typedef hash_map<unaryop_svalue::key_t,
411 unaryop_svalue *> unaryop_values_map_t;
412 unaryop_values_map_t m_unaryop_values_map;
413
414 typedef hash_map<binop_svalue::key_t, binop_svalue *> binop_values_map_t;
415 binop_values_map_t m_binop_values_map;
416
417 typedef hash_map<sub_svalue::key_t, sub_svalue *> sub_values_map_t;
418 sub_values_map_t m_sub_values_map;
419
420 typedef hash_map<repeated_svalue::key_t,
421 repeated_svalue *> repeated_values_map_t;
422 repeated_values_map_t m_repeated_values_map;
423
424 typedef hash_map<bits_within_svalue::key_t,
425 bits_within_svalue *> bits_within_values_map_t;
426 bits_within_values_map_t m_bits_within_values_map;
427
428 typedef hash_map<const svalue *,
429 unmergeable_svalue *> unmergeable_values_map_t;
430 unmergeable_values_map_t m_unmergeable_values_map;
431
432 typedef hash_map<widening_svalue::key_t,
433 widening_svalue */*,
434 widening_svalue::key_t::hash_map_traits*/>
435 widening_values_map_t;
436 widening_values_map_t m_widening_values_map;
437
438 typedef hash_map<compound_svalue::key_t,
439 compound_svalue *> compound_values_map_t;
440 compound_values_map_t m_compound_values_map;
441
442 typedef hash_map<conjured_svalue::key_t,
443 conjured_svalue *> conjured_values_map_t;
444 conjured_values_map_t m_conjured_values_map;
445
446 typedef hash_map<asm_output_svalue::key_t,
447 asm_output_svalue *> asm_output_values_map_t;
448 asm_output_values_map_t m_asm_output_values_map;
449
450 typedef hash_map<const_fn_result_svalue::key_t,
451 const_fn_result_svalue *> const_fn_result_values_map_t;
452 const_fn_result_values_map_t m_const_fn_result_values_map;
453
454 bool m_checking_feasibility;
455
456 /* "Dynamically-allocated" svalue instances.
457 The number of these within the analysis can grow arbitrarily.
458 They are still owned by the manager. */
459 auto_delete_vec<svalue> m_managed_dynamic_svalues;
460
461 /* Maximum complexity of svalues that weren't rejected. */
462 complexity m_max_complexity;
463
464 /* region consolidation. */
465
466 code_region m_code_region;
467 typedef hash_map<tree, function_region *> fndecls_map_t;
468 typedef fndecls_map_t::iterator fndecls_iterator_t;
469 fndecls_map_t m_fndecls_map;
470
471 typedef hash_map<tree, label_region *> labels_map_t;
472 typedef labels_map_t::iterator labels_iterator_t;
473 labels_map_t m_labels_map;
474
475 globals_region m_globals_region;
476 typedef hash_map<tree, decl_region *> globals_map_t;
477 typedef globals_map_t::iterator globals_iterator_t;
478 globals_map_t m_globals_map;
479
480 consolidation_map<field_region> m_field_regions;
481 consolidation_map<element_region> m_element_regions;
482 consolidation_map<offset_region> m_offset_regions;
483 consolidation_map<sized_region> m_sized_regions;
484 consolidation_map<cast_region> m_cast_regions;
485 consolidation_map<frame_region> m_frame_regions;
486 consolidation_map<symbolic_region> m_symbolic_regions;
487
488 typedef hash_map<tree, string_region *> string_map_t;
489 string_map_t m_string_map;
490
491 consolidation_map<bit_range_region> m_bit_range_regions;
492
493 store_manager m_store_mgr;
494
495 bounded_ranges_manager *m_range_mgr;
496
497 /* "Dynamically-allocated" region instances.
498 The number of these within the analysis can grow arbitrarily.
499 They are still owned by the manager. */
500 auto_delete_vec<region> m_managed_dynamic_regions;
501 };
502
503 struct append_regions_cb_data;
504
505 /* Helper class for handling calls to functions with known behavior.
506 Implemented in region-model-impl-calls.c. */
507
508 class call_details
509 {
510 public:
511 call_details (const gcall *call, region_model *model,
512 region_model_context *ctxt);
513
514 region_model_manager *get_manager () const;
get_ctxt()515 region_model_context *get_ctxt () const { return m_ctxt; }
516 uncertainty_t *get_uncertainty () const;
get_lhs_type()517 tree get_lhs_type () const { return m_lhs_type; }
get_lhs_region()518 const region *get_lhs_region () const { return m_lhs_region; }
519
520 bool maybe_set_lhs (const svalue *result) const;
521
522 unsigned num_args () const;
523
get_call_stmt()524 const gcall *get_call_stmt () const { return m_call; }
525
526 tree get_arg_tree (unsigned idx) const;
527 tree get_arg_type (unsigned idx) const;
528 const svalue *get_arg_svalue (unsigned idx) const;
529 const char *get_arg_string_literal (unsigned idx) const;
530
531 tree get_fndecl_for_call () const;
532
533 void dump_to_pp (pretty_printer *pp, bool simple) const;
534 void dump (bool simple) const;
535
536 const svalue *get_or_create_conjured_svalue (const region *) const;
537
538 private:
539 const gcall *m_call;
540 region_model *m_model;
541 region_model_context *m_ctxt;
542 tree m_lhs_type;
543 const region *m_lhs_region;
544 };
545
546 /* A region_model encapsulates a representation of the state of memory, with
547 a tree of regions, along with their associated values.
548 The representation is graph-like because values can be pointers to
549 regions.
550 It also stores:
551 - a constraint_manager, capturing relationships between the values, and
552 - dynamic extents, mapping dynamically-allocated regions to svalues (their
553 capacities). */
554
555 class region_model
556 {
557 public:
558 typedef region_to_value_map dynamic_extents_t;
559
560 region_model (region_model_manager *mgr);
561 region_model (const region_model &other);
562 ~region_model ();
563 region_model &operator= (const region_model &other);
564
565 bool operator== (const region_model &other) const;
566 bool operator!= (const region_model &other) const
567 {
568 return !(*this == other);
569 }
570
571 hashval_t hash () const;
572
573 void print (pretty_printer *pp) const;
574
575 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
576 void dump (FILE *fp, bool simple, bool multiline) const;
577 void dump (bool simple) const;
578
579 void debug () const;
580
581 void validate () const;
582
583 void canonicalize ();
584 bool canonicalized_p () const;
585
586 void
587 on_stmt_pre (const gimple *stmt,
588 bool *out_terminate_path,
589 bool *out_unknown_side_effects,
590 region_model_context *ctxt);
591
592 void on_assignment (const gassign *stmt, region_model_context *ctxt);
593 const svalue *get_gassign_result (const gassign *assign,
594 region_model_context *ctxt);
595 void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
596 bool on_call_pre (const gcall *stmt, region_model_context *ctxt,
597 bool *out_terminate_path);
598 void on_call_post (const gcall *stmt,
599 bool unknown_side_effects,
600 region_model_context *ctxt);
601
602 void purge_state_involving (const svalue *sval, region_model_context *ctxt);
603
604 /* Specific handling for on_call_pre. */
605 void impl_call_alloca (const call_details &cd);
606 void impl_call_analyzer_describe (const gcall *call,
607 region_model_context *ctxt);
608 void impl_call_analyzer_dump_capacity (const gcall *call,
609 region_model_context *ctxt);
610 void impl_call_analyzer_dump_escaped (const gcall *call);
611 void impl_call_analyzer_eval (const gcall *call,
612 region_model_context *ctxt);
613 void impl_call_builtin_expect (const call_details &cd);
614 void impl_call_calloc (const call_details &cd);
615 bool impl_call_error (const call_details &cd, unsigned min_args,
616 bool *out_terminate_path);
617 void impl_call_fgets (const call_details &cd);
618 void impl_call_fread (const call_details &cd);
619 void impl_call_free (const call_details &cd);
620 void impl_call_malloc (const call_details &cd);
621 void impl_call_memcpy (const call_details &cd);
622 void impl_call_memset (const call_details &cd);
623 void impl_call_realloc (const call_details &cd);
624 void impl_call_strchr (const call_details &cd);
625 void impl_call_strcpy (const call_details &cd);
626 void impl_call_strlen (const call_details &cd);
627 void impl_call_operator_new (const call_details &cd);
628 void impl_call_operator_delete (const call_details &cd);
629 void impl_deallocation_call (const call_details &cd);
630
631 void handle_unrecognized_call (const gcall *call,
632 region_model_context *ctxt);
633 void get_reachable_svalues (svalue_set *out,
634 const svalue *extra_sval,
635 const uncertainty_t *uncertainty);
636
637 void on_return (const greturn *stmt, region_model_context *ctxt);
638 void on_setjmp (const gcall *stmt, const exploded_node *enode,
639 region_model_context *ctxt);
640 void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
641 int setjmp_stack_depth, region_model_context *ctxt);
642
643 void update_for_phis (const supernode *snode,
644 const cfg_superedge *last_cfg_superedge,
645 region_model_context *ctxt);
646
647 void handle_phi (const gphi *phi, tree lhs, tree rhs,
648 const region_model &old_state,
649 region_model_context *ctxt);
650
651 bool maybe_update_for_edge (const superedge &edge,
652 const gimple *last_stmt,
653 region_model_context *ctxt,
654 rejected_constraint **out);
655
656 void update_for_gcall (const gcall *call_stmt,
657 region_model_context *ctxt,
658 function *callee = NULL);
659
660 void update_for_return_gcall (const gcall *call_stmt,
661 region_model_context *ctxt);
662
663 const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
664 region_model_context *ctxt);
get_current_frame()665 const frame_region *get_current_frame () const { return m_current_frame; }
666 function * get_current_function () const;
667 void pop_frame (tree result_lvalue,
668 const svalue **out_result,
669 region_model_context *ctxt,
670 bool eval_return_svalue = true);
671 int get_stack_depth () const;
672 const frame_region *get_frame_at_index (int index) const;
673
674 const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
675 const region *get_lvalue (tree expr, region_model_context *ctxt) const;
676 const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
677 const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
678
679 const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
680 region_model_context *ctxt) const;
681
682 const svalue *get_rvalue_for_bits (tree type,
683 const region *reg,
684 const bit_range &bits,
685 region_model_context *ctxt) const;
686
687 void set_value (const region *lhs_reg, const svalue *rhs_sval,
688 region_model_context *ctxt);
689 void set_value (tree lhs, tree rhs, region_model_context *ctxt);
690 void clobber_region (const region *reg);
691 void purge_region (const region *reg);
692 void fill_region (const region *reg, const svalue *sval);
693 void zero_fill_region (const region *reg);
694 void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
695
696 tristate eval_condition (const svalue *lhs,
697 enum tree_code op,
698 const svalue *rhs) const;
699 tristate eval_condition_without_cm (const svalue *lhs,
700 enum tree_code op,
701 const svalue *rhs) const;
702 tristate compare_initial_and_pointer (const initial_svalue *init,
703 const region_svalue *ptr) const;
704 tristate eval_condition (tree lhs,
705 enum tree_code op,
706 tree rhs,
707 region_model_context *ctxt);
708 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
709 region_model_context *ctxt);
710 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
711 region_model_context *ctxt,
712 rejected_constraint **out);
713
714 const region *create_region_for_heap_alloc (const svalue *size_in_bytes,
715 region_model_context *ctxt);
716 const region *create_region_for_alloca (const svalue *size_in_bytes,
717 region_model_context *ctxt);
718
719 tree get_representative_tree (const svalue *sval) const;
720 path_var
721 get_representative_path_var (const svalue *sval,
722 svalue_set *visited) const;
723 path_var
724 get_representative_path_var (const region *reg,
725 svalue_set *visited) const;
726
727 /* For selftests. */
get_constraints()728 constraint_manager *get_constraints ()
729 {
730 return m_constraints;
731 }
732
get_store()733 store *get_store () { return &m_store; }
get_store()734 const store *get_store () const { return &m_store; }
735
736 const dynamic_extents_t &
get_dynamic_extents()737 get_dynamic_extents () const
738 {
739 return m_dynamic_extents;
740 }
741 const svalue *get_dynamic_extents (const region *reg) const;
742 void set_dynamic_extents (const region *reg,
743 const svalue *size_in_bytes,
744 region_model_context *ctxt);
745 void unset_dynamic_extents (const region *reg);
746
get_manager()747 region_model_manager *get_manager () const { return m_mgr; }
get_range_manager()748 bounded_ranges_manager *get_range_manager () const
749 {
750 return m_mgr->get_range_manager ();
751 }
752
753 void unbind_region_and_descendents (const region *reg,
754 enum poison_kind pkind);
755
756 bool can_merge_with_p (const region_model &other_model,
757 const program_point &point,
758 region_model *out_model,
759 const extrinsic_state *ext_state = NULL,
760 const program_state *state_a = NULL,
761 const program_state *state_b = NULL) const;
762
763 tree get_fndecl_for_call (const gcall *call,
764 region_model_context *ctxt);
765
766 void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
767 static void append_regions_cb (const region *base_reg,
768 struct append_regions_cb_data *data);
769
770 const svalue *get_store_value (const region *reg,
771 region_model_context *ctxt) const;
772
773 bool region_exists_p (const region *reg) const;
774
775 void loop_replay_fixup (const region_model *dst_state);
776
777 const svalue *get_capacity (const region *reg) const;
778
779 /* Implemented in sm-malloc.cc */
780 void on_realloc_with_move (const call_details &cd,
781 const svalue *old_ptr_sval,
782 const svalue *new_ptr_sval);
783
784 private:
785 const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
786 const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
787
788 path_var
789 get_representative_path_var_1 (const svalue *sval,
790 svalue_set *visited) const;
791 path_var
792 get_representative_path_var_1 (const region *reg,
793 svalue_set *visited) const;
794
795 bool add_constraint (const svalue *lhs,
796 enum tree_code op,
797 const svalue *rhs,
798 region_model_context *ctxt);
799 bool add_constraints_from_binop (const svalue *outer_lhs,
800 enum tree_code outer_op,
801 const svalue *outer_rhs,
802 bool *out,
803 region_model_context *ctxt);
804
805 void update_for_call_superedge (const call_superedge &call_edge,
806 region_model_context *ctxt);
807 void update_for_return_superedge (const return_superedge &return_edge,
808 region_model_context *ctxt);
809 void update_for_call_summary (const callgraph_superedge &cg_sedge,
810 region_model_context *ctxt);
811 bool apply_constraints_for_gcond (const cfg_superedge &edge,
812 const gcond *cond_stmt,
813 region_model_context *ctxt,
814 rejected_constraint **out);
815 bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
816 const gswitch *switch_stmt,
817 region_model_context *ctxt,
818 rejected_constraint **out);
819 bool apply_constraints_for_exception (const gimple *last_stmt,
820 region_model_context *ctxt,
821 rejected_constraint **out);
822
823 int poison_any_pointers_to_descendents (const region *reg,
824 enum poison_kind pkind);
825
826 void on_top_level_param (tree param,
827 bool nonnull,
828 region_model_context *ctxt);
829
830 bool called_from_main_p () const;
831 const svalue *get_initial_value_for_global (const region *reg) const;
832
833 const svalue *check_for_poison (const svalue *sval,
834 tree expr,
835 region_model_context *ctxt) const;
836 const region * get_region_for_poisoned_expr (tree expr) const;
837
838 void check_dynamic_size_for_taint (enum memory_space mem_space,
839 const svalue *size_in_bytes,
840 region_model_context *ctxt) const;
841
842 void check_region_for_taint (const region *reg,
843 enum access_direction dir,
844 region_model_context *ctxt) const;
845
846 void check_for_writable_region (const region* dest_reg,
847 region_model_context *ctxt) const;
848 void check_region_access (const region *reg,
849 enum access_direction dir,
850 region_model_context *ctxt) const;
851 void check_region_for_write (const region *dest_reg,
852 region_model_context *ctxt) const;
853 void check_region_for_read (const region *src_reg,
854 region_model_context *ctxt) const;
855
856 void check_call_args (const call_details &cd) const;
857 void check_external_function_for_access_attr (const gcall *call,
858 tree callee_fndecl,
859 region_model_context *ctxt) const;
860
861 /* Storing this here to avoid passing it around everywhere. */
862 region_model_manager *const m_mgr;
863
864 store m_store;
865
866 constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
867
868 const frame_region *m_current_frame;
869
870 /* Map from base region to size in bytes, for tracking the sizes of
871 dynamically-allocated regions.
872 This is part of the region_model rather than the region to allow for
873 memory regions to be resized (e.g. by realloc). */
874 dynamic_extents_t m_dynamic_extents;
875 };
876
877 /* Some region_model activity could lead to warnings (e.g. attempts to use an
878 uninitialized value). This abstract base class encapsulates an interface
879 for the region model to use when emitting such warnings.
880
881 Having this as an abstract base class allows us to support the various
882 operations needed by program_state in the analyzer within region_model,
883 whilst keeping them somewhat modularized. */
884
885 class region_model_context
886 {
887 public:
888 /* Hook for clients to store pending diagnostics.
889 Return true if the diagnostic was stored, or false if it was deleted. */
890 virtual bool warn (pending_diagnostic *d) = 0;
891
892 /* Hook for clients to add a note to the last previously stored pending diagnostic.
893 Takes ownership of the pending_node (or deletes it). */
894 virtual void add_note (pending_note *pn) = 0;
895
896 /* Hook for clients to be notified when an SVAL that was reachable
897 in a previous state is no longer live, so that clients can emit warnings
898 about leaks. */
899 virtual void on_svalue_leak (const svalue *sval) = 0;
900
901 /* Hook for clients to be notified when the set of explicitly live
902 svalues changes, so that they can purge state relating to dead
903 svalues. */
904 virtual void on_liveness_change (const svalue_set &live_svalues,
905 const region_model *model) = 0;
906
907 virtual logger *get_logger () = 0;
908
909 /* Hook for clients to be notified when the condition
910 "LHS OP RHS" is added to the region model.
911 This exists so that state machines can detect tests on edges,
912 and use them to trigger sm-state transitions (e.g. transitions due
913 to ptrs becoming known to be NULL or non-NULL, rather than just
914 "unchecked") */
915 virtual void on_condition (const svalue *lhs,
916 enum tree_code op,
917 const svalue *rhs) = 0;
918
919 /* Hooks for clients to be notified when an unknown change happens
920 to SVAL (in response to a call to an unknown function). */
921 virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
922
923 /* Hooks for clients to be notified when a phi node is handled,
924 where RHS is the pertinent argument. */
925 virtual void on_phi (const gphi *phi, tree rhs) = 0;
926
927 /* Hooks for clients to be notified when the region model doesn't
928 know how to handle the tree code of T at LOC. */
929 virtual void on_unexpected_tree_code (tree t,
930 const dump_location_t &loc) = 0;
931
932 /* Hook for clients to be notified when a function_decl escapes. */
933 virtual void on_escaped_function (tree fndecl) = 0;
934
935 virtual uncertainty_t *get_uncertainty () = 0;
936
937 /* Hook for clients to purge state involving SVAL. */
938 virtual void purge_state_involving (const svalue *sval) = 0;
939
940 /* Hook for clients to split state with a non-standard path.
941 Take ownership of INFO. */
942 virtual void bifurcate (custom_edge_info *info) = 0;
943
944 /* Hook for clients to terminate the standard path. */
945 virtual void terminate_path () = 0;
946
947 virtual const extrinsic_state *get_ext_state () const = 0;
948
949 /* Hook for clients to access the "malloc" state machine in
950 any underlying program_state. */
951 virtual bool get_malloc_map (sm_state_map **out_smap,
952 const state_machine **out_sm,
953 unsigned *out_sm_idx) = 0;
954 /* Likewise for the "taint" state machine. */
955 virtual bool get_taint_map (sm_state_map **out_smap,
956 const state_machine **out_sm,
957 unsigned *out_sm_idx) = 0;
958
959 /* Get the current statement, if any. */
960 virtual const gimple *get_stmt () const = 0;
961 };
962
963 /* A "do nothing" subclass of region_model_context. */
964
965 class noop_region_model_context : public region_model_context
966 {
967 public:
warn(pending_diagnostic *)968 bool warn (pending_diagnostic *) OVERRIDE { return false; }
969 void add_note (pending_note *pn) OVERRIDE;
on_svalue_leak(const svalue *)970 void on_svalue_leak (const svalue *) OVERRIDE {}
on_liveness_change(const svalue_set &,const region_model *)971 void on_liveness_change (const svalue_set &,
972 const region_model *) OVERRIDE {}
get_logger()973 logger *get_logger () OVERRIDE { return NULL; }
on_condition(const svalue * lhs ATTRIBUTE_UNUSED,enum tree_code op ATTRIBUTE_UNUSED,const svalue * rhs ATTRIBUTE_UNUSED)974 void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
975 enum tree_code op ATTRIBUTE_UNUSED,
976 const svalue *rhs ATTRIBUTE_UNUSED) OVERRIDE
977 {
978 }
on_unknown_change(const svalue * sval ATTRIBUTE_UNUSED,bool is_mutable ATTRIBUTE_UNUSED)979 void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
980 bool is_mutable ATTRIBUTE_UNUSED) OVERRIDE
981 {
982 }
on_phi(const gphi * phi ATTRIBUTE_UNUSED,tree rhs ATTRIBUTE_UNUSED)983 void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
984 tree rhs ATTRIBUTE_UNUSED) OVERRIDE
985 {
986 }
on_unexpected_tree_code(tree,const dump_location_t &)987 void on_unexpected_tree_code (tree, const dump_location_t &) OVERRIDE {}
988
on_escaped_function(tree)989 void on_escaped_function (tree) OVERRIDE {}
990
get_uncertainty()991 uncertainty_t *get_uncertainty () OVERRIDE { return NULL; }
992
purge_state_involving(const svalue * sval ATTRIBUTE_UNUSED)993 void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) OVERRIDE {}
994
995 void bifurcate (custom_edge_info *info) OVERRIDE;
996 void terminate_path () OVERRIDE;
997
get_ext_state()998 const extrinsic_state *get_ext_state () const OVERRIDE { return NULL; }
999
get_malloc_map(sm_state_map **,const state_machine **,unsigned *)1000 bool get_malloc_map (sm_state_map **,
1001 const state_machine **,
1002 unsigned *) OVERRIDE
1003 {
1004 return false;
1005 }
get_taint_map(sm_state_map **,const state_machine **,unsigned *)1006 bool get_taint_map (sm_state_map **,
1007 const state_machine **,
1008 unsigned *) OVERRIDE
1009 {
1010 return false;
1011 }
1012
get_stmt()1013 const gimple *get_stmt () const OVERRIDE { return NULL; }
1014 };
1015
1016 /* A subclass of region_model_context for determining if operations fail
1017 e.g. "can we generate a region for the lvalue of EXPR?". */
1018
1019 class tentative_region_model_context : public noop_region_model_context
1020 {
1021 public:
tentative_region_model_context()1022 tentative_region_model_context () : m_num_unexpected_codes (0) {}
1023
on_unexpected_tree_code(tree,const dump_location_t &)1024 void on_unexpected_tree_code (tree, const dump_location_t &)
1025 FINAL OVERRIDE
1026 {
1027 m_num_unexpected_codes++;
1028 }
1029
had_errors_p()1030 bool had_errors_p () const { return m_num_unexpected_codes > 0; }
1031
1032 private:
1033 int m_num_unexpected_codes;
1034 };
1035
1036 /* Subclass of region_model_context that wraps another context, allowing
1037 for extra code to be added to the various hooks. */
1038
1039 class region_model_context_decorator : public region_model_context
1040 {
1041 public:
warn(pending_diagnostic * d)1042 bool warn (pending_diagnostic *d) OVERRIDE
1043 {
1044 return m_inner->warn (d);
1045 }
1046
add_note(pending_note * pn)1047 void add_note (pending_note *pn) OVERRIDE
1048 {
1049 m_inner->add_note (pn);
1050 }
1051
on_svalue_leak(const svalue * sval)1052 void on_svalue_leak (const svalue *sval) OVERRIDE
1053 {
1054 m_inner->on_svalue_leak (sval);
1055 }
1056
on_liveness_change(const svalue_set & live_svalues,const region_model * model)1057 void on_liveness_change (const svalue_set &live_svalues,
1058 const region_model *model) OVERRIDE
1059 {
1060 m_inner->on_liveness_change (live_svalues, model);
1061 }
1062
get_logger()1063 logger *get_logger () OVERRIDE
1064 {
1065 return m_inner->get_logger ();
1066 }
1067
on_condition(const svalue * lhs,enum tree_code op,const svalue * rhs)1068 void on_condition (const svalue *lhs,
1069 enum tree_code op,
1070 const svalue *rhs) OVERRIDE
1071 {
1072 m_inner->on_condition (lhs, op, rhs);
1073 }
1074
on_unknown_change(const svalue * sval,bool is_mutable)1075 void on_unknown_change (const svalue *sval, bool is_mutable) OVERRIDE
1076 {
1077 m_inner->on_unknown_change (sval, is_mutable);
1078 }
1079
on_phi(const gphi * phi,tree rhs)1080 void on_phi (const gphi *phi, tree rhs) OVERRIDE
1081 {
1082 m_inner->on_phi (phi, rhs);
1083 }
1084
on_unexpected_tree_code(tree t,const dump_location_t & loc)1085 void on_unexpected_tree_code (tree t,
1086 const dump_location_t &loc) OVERRIDE
1087 {
1088 m_inner->on_unexpected_tree_code (t, loc);
1089 }
1090
on_escaped_function(tree fndecl)1091 void on_escaped_function (tree fndecl) OVERRIDE
1092 {
1093 m_inner->on_escaped_function (fndecl);
1094 }
1095
get_uncertainty()1096 uncertainty_t *get_uncertainty () OVERRIDE
1097 {
1098 return m_inner->get_uncertainty ();
1099 }
1100
purge_state_involving(const svalue * sval)1101 void purge_state_involving (const svalue *sval) OVERRIDE
1102 {
1103 m_inner->purge_state_involving (sval);
1104 }
1105
bifurcate(custom_edge_info * info)1106 void bifurcate (custom_edge_info *info) OVERRIDE
1107 {
1108 m_inner->bifurcate (info);
1109 }
1110
terminate_path()1111 void terminate_path () OVERRIDE
1112 {
1113 m_inner->terminate_path ();
1114 }
1115
get_ext_state()1116 const extrinsic_state *get_ext_state () const OVERRIDE
1117 {
1118 return m_inner->get_ext_state ();
1119 }
1120
get_malloc_map(sm_state_map ** out_smap,const state_machine ** out_sm,unsigned * out_sm_idx)1121 bool get_malloc_map (sm_state_map **out_smap,
1122 const state_machine **out_sm,
1123 unsigned *out_sm_idx) OVERRIDE
1124 {
1125 return m_inner->get_malloc_map (out_smap, out_sm, out_sm_idx);
1126 }
1127
get_taint_map(sm_state_map ** out_smap,const state_machine ** out_sm,unsigned * out_sm_idx)1128 bool get_taint_map (sm_state_map **out_smap,
1129 const state_machine **out_sm,
1130 unsigned *out_sm_idx) OVERRIDE
1131 {
1132 return m_inner->get_taint_map (out_smap, out_sm, out_sm_idx);
1133 }
1134
get_stmt()1135 const gimple *get_stmt () const OVERRIDE
1136 {
1137 return m_inner->get_stmt ();
1138 }
1139
1140 protected:
region_model_context_decorator(region_model_context * inner)1141 region_model_context_decorator (region_model_context *inner)
1142 : m_inner (inner)
1143 {
1144 gcc_assert (m_inner);
1145 }
1146
1147 region_model_context *m_inner;
1148 };
1149
1150 /* Subclass of region_model_context_decorator that adds a note
1151 when saving diagnostics. */
1152
1153 class note_adding_context : public region_model_context_decorator
1154 {
1155 public:
warn(pending_diagnostic * d)1156 bool warn (pending_diagnostic *d) OVERRIDE
1157 {
1158 if (m_inner->warn (d))
1159 {
1160 add_note (make_note ());
1161 return true;
1162 }
1163 else
1164 return false;
1165 }
1166
1167 /* Hook to make the new note. */
1168 virtual pending_note *make_note () = 0;
1169
1170 protected:
note_adding_context(region_model_context * inner)1171 note_adding_context (region_model_context *inner)
1172 : region_model_context_decorator (inner)
1173 {
1174 }
1175 };
1176
1177 /* A bundle of data for use when attempting to merge two region_model
1178 instances to make a third. */
1179
1180 struct model_merger
1181 {
model_mergermodel_merger1182 model_merger (const region_model *model_a,
1183 const region_model *model_b,
1184 const program_point &point,
1185 region_model *merged_model,
1186 const extrinsic_state *ext_state,
1187 const program_state *state_a,
1188 const program_state *state_b)
1189 : m_model_a (model_a), m_model_b (model_b),
1190 m_point (point),
1191 m_merged_model (merged_model),
1192 m_ext_state (ext_state),
1193 m_state_a (state_a), m_state_b (state_b)
1194 {
1195 }
1196
1197 void dump_to_pp (pretty_printer *pp, bool simple) const;
1198 void dump (FILE *fp, bool simple) const;
1199 void dump (bool simple) const;
1200
get_managermodel_merger1201 region_model_manager *get_manager () const
1202 {
1203 return m_model_a->get_manager ();
1204 }
1205
1206 bool mergeable_svalue_p (const svalue *) const;
1207
1208 const region_model *m_model_a;
1209 const region_model *m_model_b;
1210 const program_point &m_point;
1211 region_model *m_merged_model;
1212
1213 const extrinsic_state *m_ext_state;
1214 const program_state *m_state_a;
1215 const program_state *m_state_b;
1216 };
1217
1218 /* A record that can (optionally) be written out when
1219 region_model::add_constraint fails. */
1220
1221 class rejected_constraint
1222 {
1223 public:
~rejected_constraint()1224 virtual ~rejected_constraint () {}
1225 virtual void dump_to_pp (pretty_printer *pp) const = 0;
1226
get_model()1227 const region_model &get_model () const { return m_model; }
1228
1229 protected:
rejected_constraint(const region_model & model)1230 rejected_constraint (const region_model &model)
1231 : m_model (model)
1232 {}
1233
1234 region_model m_model;
1235 };
1236
1237 class rejected_op_constraint : public rejected_constraint
1238 {
1239 public:
rejected_op_constraint(const region_model & model,tree lhs,enum tree_code op,tree rhs)1240 rejected_op_constraint (const region_model &model,
1241 tree lhs, enum tree_code op, tree rhs)
1242 : rejected_constraint (model),
1243 m_lhs (lhs), m_op (op), m_rhs (rhs)
1244 {}
1245
1246 void dump_to_pp (pretty_printer *pp) const FINAL OVERRIDE;
1247
1248 tree m_lhs;
1249 enum tree_code m_op;
1250 tree m_rhs;
1251 };
1252
1253 class rejected_ranges_constraint : public rejected_constraint
1254 {
1255 public:
rejected_ranges_constraint(const region_model & model,tree expr,const bounded_ranges * ranges)1256 rejected_ranges_constraint (const region_model &model,
1257 tree expr, const bounded_ranges *ranges)
1258 : rejected_constraint (model),
1259 m_expr (expr), m_ranges (ranges)
1260 {}
1261
1262 void dump_to_pp (pretty_printer *pp) const FINAL OVERRIDE;
1263
1264 private:
1265 tree m_expr;
1266 const bounded_ranges *m_ranges;
1267 };
1268
1269 /* A bundle of state. */
1270
1271 class engine
1272 {
1273 public:
1274 engine (const supergraph *sg = NULL, logger *logger = NULL);
get_supergraph()1275 const supergraph *get_supergraph () { return m_sg; }
get_model_manager()1276 region_model_manager *get_model_manager () { return &m_mgr; }
1277
1278 void log_stats (logger *logger) const;
1279
1280 private:
1281 const supergraph *m_sg;
1282 region_model_manager m_mgr;
1283 };
1284
1285 } // namespace ana
1286
1287 extern void debug (const region_model &rmodel);
1288
1289 namespace ana {
1290
1291 #if CHECKING_P
1292
1293 namespace selftest {
1294
1295 using namespace ::selftest;
1296
1297 /* An implementation of region_model_context for use in selftests, which
1298 stores any pending_diagnostic instances passed to it. */
1299
1300 class test_region_model_context : public noop_region_model_context
1301 {
1302 public:
warn(pending_diagnostic * d)1303 bool warn (pending_diagnostic *d) FINAL OVERRIDE
1304 {
1305 m_diagnostics.safe_push (d);
1306 return true;
1307 }
1308
get_num_diagnostics()1309 unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1310
on_unexpected_tree_code(tree t,const dump_location_t &)1311 void on_unexpected_tree_code (tree t, const dump_location_t &)
1312 FINAL OVERRIDE
1313 {
1314 internal_error ("unhandled tree code: %qs",
1315 get_tree_code_name (TREE_CODE (t)));
1316 }
1317
1318 private:
1319 /* Implicitly delete any diagnostics in the dtor. */
1320 auto_delete_vec<pending_diagnostic> m_diagnostics;
1321 };
1322
1323 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1324 Verify that MODEL remains satisfiable. */
1325
1326 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1327 SELFTEST_BEGIN_STMT \
1328 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1329 ASSERT_TRUE (sat); \
1330 SELFTEST_END_STMT
1331
1332 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1333 Verify that the result is not satisfiable. */
1334
1335 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1336 SELFTEST_BEGIN_STMT \
1337 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1338 ASSERT_FALSE (sat); \
1339 SELFTEST_END_STMT
1340
1341 /* Implementation detail of the ASSERT_CONDITION_* macros. */
1342
1343 void assert_condition (const location &loc,
1344 region_model &model,
1345 const svalue *lhs, tree_code op, const svalue *rhs,
1346 tristate expected);
1347
1348 void assert_condition (const location &loc,
1349 region_model &model,
1350 tree lhs, tree_code op, tree rhs,
1351 tristate expected);
1352
1353 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1354 as "true". */
1355
1356 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1357 SELFTEST_BEGIN_STMT \
1358 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1359 tristate (tristate::TS_TRUE)); \
1360 SELFTEST_END_STMT
1361
1362 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1363 as "false". */
1364
1365 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1366 SELFTEST_BEGIN_STMT \
1367 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1368 tristate (tristate::TS_FALSE)); \
1369 SELFTEST_END_STMT
1370
1371 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1372 as "unknown". */
1373
1374 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1375 SELFTEST_BEGIN_STMT \
1376 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1377 tristate (tristate::TS_UNKNOWN)); \
1378 SELFTEST_END_STMT
1379
1380 } /* end of namespace selftest. */
1381
1382 #endif /* #if CHECKING_P */
1383
1384 } // namespace ana
1385
1386 #endif /* GCC_ANALYZER_REGION_MODEL_H */
1387