1 /* Classes for modeling the state of memory.
2 Copyright (C) 2019-2021 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 /* Various operations delete information from a region_model.
132
133 This struct tracks how many of each kind of entity were purged (e.g.
134 for selftests, and for debugging). */
135
136 struct purge_stats
137 {
purge_statspurge_stats138 purge_stats ()
139 : m_num_svalues (0),
140 m_num_regions (0),
141 m_num_equiv_classes (0),
142 m_num_constraints (0),
143 m_num_client_items (0)
144 {}
145
146 int m_num_svalues;
147 int m_num_regions;
148 int m_num_equiv_classes;
149 int m_num_constraints;
150 int m_num_client_items;
151 };
152
153 /* A base class for visiting regions and svalues, with do-nothing
154 base implementations of the per-subclass vfuncs. */
155
156 class visitor
157 {
158 public:
visit_region_svalue(const region_svalue *)159 virtual void visit_region_svalue (const region_svalue *) {}
visit_constant_svalue(const constant_svalue *)160 virtual void visit_constant_svalue (const constant_svalue *) {}
visit_unknown_svalue(const unknown_svalue *)161 virtual void visit_unknown_svalue (const unknown_svalue *) {}
visit_poisoned_svalue(const poisoned_svalue *)162 virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
visit_setjmp_svalue(const setjmp_svalue *)163 virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
visit_initial_svalue(const initial_svalue *)164 virtual void visit_initial_svalue (const initial_svalue *) {}
visit_unaryop_svalue(const unaryop_svalue *)165 virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
visit_binop_svalue(const binop_svalue *)166 virtual void visit_binop_svalue (const binop_svalue *) {}
visit_sub_svalue(const sub_svalue *)167 virtual void visit_sub_svalue (const sub_svalue *) {}
visit_unmergeable_svalue(const unmergeable_svalue *)168 virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
visit_placeholder_svalue(const placeholder_svalue *)169 virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
visit_widening_svalue(const widening_svalue *)170 virtual void visit_widening_svalue (const widening_svalue *) {}
visit_compound_svalue(const compound_svalue *)171 virtual void visit_compound_svalue (const compound_svalue *) {}
visit_conjured_svalue(const conjured_svalue *)172 virtual void visit_conjured_svalue (const conjured_svalue *) {}
173
visit_region(const region *)174 virtual void visit_region (const region *) {}
175 };
176
177 } // namespace ana
178
179 namespace ana {
180
181 /* A class responsible for owning and consolidating region and svalue
182 instances.
183 region and svalue instances are immutable as far as clients are
184 concerned, so they are provided as "const" ptrs. */
185
186 class region_model_manager
187 {
188 public:
189 region_model_manager ();
190 ~region_model_manager ();
191
192 /* svalue consolidation. */
193 const svalue *get_or_create_constant_svalue (tree cst_expr);
194 const svalue *get_or_create_int_cst (tree type, poly_int64);
195 const svalue *get_or_create_unknown_svalue (tree type);
196 const svalue *get_or_create_setjmp_svalue (const setjmp_record &r,
197 tree type);
198 const svalue *get_or_create_poisoned_svalue (enum poison_kind kind,
199 tree type);
200 const svalue *get_or_create_initial_value (const region *reg);
201 const svalue *get_ptr_svalue (tree ptr_type, const region *pointee);
202 const svalue *get_or_create_unaryop (tree type, enum tree_code op,
203 const svalue *arg);
204 const svalue *get_or_create_cast (tree type, const svalue *arg);
205 const svalue *get_or_create_binop (tree type,
206 enum tree_code op,
207 const svalue *arg0, const svalue *arg1);
208 const svalue *get_or_create_sub_svalue (tree type,
209 const svalue *parent_svalue,
210 const region *subregion);
211 const svalue *get_or_create_unmergeable (const svalue *arg);
212 const svalue *get_or_create_widening_svalue (tree type,
213 const program_point &point,
214 const svalue *base_svalue,
215 const svalue *iter_svalue);
216 const svalue *get_or_create_compound_svalue (tree type,
217 const binding_map &map);
218 const svalue *get_or_create_conjured_svalue (tree type, const gimple *stmt,
219 const region *id_reg);
220
221 const svalue *maybe_get_char_from_string_cst (tree string_cst,
222 tree byte_offset_cst);
223
224 /* region consolidation. */
get_stack_region()225 const stack_region * get_stack_region () const { return &m_stack_region; }
get_heap_region()226 const heap_region *get_heap_region () const { return &m_heap_region; }
get_code_region()227 const code_region *get_code_region () const { return &m_code_region; }
get_globals_region()228 const globals_region *get_globals_region () const
229 {
230 return &m_globals_region;
231 }
232 const function_region *get_region_for_fndecl (tree fndecl);
233 const label_region *get_region_for_label (tree label);
234 const decl_region *get_region_for_global (tree expr);
235 const region *get_field_region (const region *parent, tree field);
236 const region *get_element_region (const region *parent,
237 tree element_type,
238 const svalue *index);
239 const region *get_offset_region (const region *parent,
240 tree type,
241 const svalue *byte_offset);
242 const region *get_cast_region (const region *original_region,
243 tree type);
244 const frame_region *get_frame_region (const frame_region *calling_frame,
245 function *fun);
246 const region *get_symbolic_region (const svalue *sval);
247 const string_region *get_region_for_string (tree string_cst);
248
249 const region *
250 get_region_for_unexpected_tree_code (region_model_context *ctxt,
251 tree t,
252 const dump_location_t &loc);
253
alloc_region_id()254 unsigned alloc_region_id () { return m_next_region_id++; }
255
get_store_manager()256 store_manager *get_store_manager () { return &m_store_mgr; }
257
258 /* Dynamically-allocated region instances.
259 The number of these within the analysis can grow arbitrarily.
260 They are still owned by the manager. */
261 const region *create_region_for_heap_alloc ();
262 const region *create_region_for_alloca (const frame_region *frame);
263
264 void log_stats (logger *logger, bool show_objs) const;
265
266 private:
267 bool too_complex_p (const complexity &c) const;
268 bool reject_if_too_complex (svalue *sval);
269
270 const svalue *maybe_fold_unaryop (tree type, enum tree_code op,
271 const svalue *arg);
272 const svalue *maybe_fold_binop (tree type, enum tree_code op,
273 const svalue *arg0, const svalue *arg1);
274 const svalue *maybe_fold_sub_svalue (tree type,
275 const svalue *parent_svalue,
276 const region *subregion);
277 const svalue *maybe_undo_optimize_bit_field_compare (tree type,
278 const compound_svalue *compound_sval,
279 tree cst, const svalue *arg1);
280
281 unsigned m_next_region_id;
282 root_region m_root_region;
283 stack_region m_stack_region;
284 heap_region m_heap_region;
285
286 /* svalue consolidation. */
287 typedef hash_map<tree, constant_svalue *> constants_map_t;
288 constants_map_t m_constants_map;
289
290 typedef hash_map<tree, unknown_svalue *> unknowns_map_t;
291 unknowns_map_t m_unknowns_map;
292 const unknown_svalue *m_unknown_NULL;
293
294 typedef hash_map<poisoned_svalue::key_t,
295 poisoned_svalue *> poisoned_values_map_t;
296 poisoned_values_map_t m_poisoned_values_map;
297
298 typedef hash_map<setjmp_svalue::key_t,
299 setjmp_svalue *> setjmp_values_map_t;
300 setjmp_values_map_t m_setjmp_values_map;
301
302 typedef hash_map<const region *, initial_svalue *> initial_values_map_t;
303 initial_values_map_t m_initial_values_map;
304
305 typedef hash_map<region_svalue::key_t, region_svalue *> pointer_values_map_t;
306 pointer_values_map_t m_pointer_values_map;
307
308 typedef hash_map<unaryop_svalue::key_t,
309 unaryop_svalue *> unaryop_values_map_t;
310 unaryop_values_map_t m_unaryop_values_map;
311
312 typedef hash_map<binop_svalue::key_t, binop_svalue *> binop_values_map_t;
313 binop_values_map_t m_binop_values_map;
314
315 typedef hash_map<sub_svalue::key_t, sub_svalue *> sub_values_map_t;
316 sub_values_map_t m_sub_values_map;
317
318 typedef hash_map<const svalue *,
319 unmergeable_svalue *> unmergeable_values_map_t;
320 unmergeable_values_map_t m_unmergeable_values_map;
321
322 typedef hash_map<widening_svalue::key_t,
323 widening_svalue */*,
324 widening_svalue::key_t::hash_map_traits*/>
325 widening_values_map_t;
326 widening_values_map_t m_widening_values_map;
327
328 typedef hash_map<compound_svalue::key_t,
329 compound_svalue *> compound_values_map_t;
330 compound_values_map_t m_compound_values_map;
331
332 typedef hash_map<conjured_svalue::key_t,
333 conjured_svalue *> conjured_values_map_t;
334 conjured_values_map_t m_conjured_values_map;
335
336 /* Maximum complexity of svalues that weren't rejected. */
337 complexity m_max_complexity;
338
339 /* region consolidation. */
340
341 code_region m_code_region;
342 typedef hash_map<tree, function_region *> fndecls_map_t;
343 typedef fndecls_map_t::iterator fndecls_iterator_t;
344 fndecls_map_t m_fndecls_map;
345
346 typedef hash_map<tree, label_region *> labels_map_t;
347 typedef labels_map_t::iterator labels_iterator_t;
348 labels_map_t m_labels_map;
349
350 globals_region m_globals_region;
351 typedef hash_map<tree, decl_region *> globals_map_t;
352 typedef globals_map_t::iterator globals_iterator_t;
353 globals_map_t m_globals_map;
354
355 consolidation_map<field_region> m_field_regions;
356 consolidation_map<element_region> m_element_regions;
357 consolidation_map<offset_region> m_offset_regions;
358 consolidation_map<cast_region> m_cast_regions;
359 consolidation_map<frame_region> m_frame_regions;
360 consolidation_map<symbolic_region> m_symbolic_regions;
361
362 typedef hash_map<tree, string_region *> string_map_t;
363 string_map_t m_string_map;
364
365 store_manager m_store_mgr;
366
367 /* "Dynamically-allocated" region instances.
368 The number of these within the analysis can grow arbitrarily.
369 They are still owned by the manager. */
370 auto_delete_vec<region> m_managed_dynamic_regions;
371 };
372
373 struct append_ssa_names_cb_data;
374
375 /* Helper class for handling calls to functions with known behavior.
376 Implemented in region-model-impl-calls.c. */
377
378 class call_details
379 {
380 public:
381 call_details (const gcall *call, region_model *model,
382 region_model_context *ctxt);
383
get_ctxt()384 region_model_context *get_ctxt () const { return m_ctxt; }
385 uncertainty_t *get_uncertainty () const;
get_lhs_type()386 tree get_lhs_type () const { return m_lhs_type; }
get_lhs_region()387 const region *get_lhs_region () const { return m_lhs_region; }
388
389 bool maybe_set_lhs (const svalue *result) const;
390
391 unsigned num_args () const;
392
393 tree get_arg_tree (unsigned idx) const;
394 tree get_arg_type (unsigned idx) const;
395 const svalue *get_arg_svalue (unsigned idx) const;
396
397 void dump_to_pp (pretty_printer *pp, bool simple) const;
398 void dump (bool simple) const;
399
400 private:
401 const gcall *m_call;
402 region_model *m_model;
403 region_model_context *m_ctxt;
404 tree m_lhs_type;
405 const region *m_lhs_region;
406 };
407
408 /* A region_model encapsulates a representation of the state of memory, with
409 a tree of regions, along with their associated values.
410 The representation is graph-like because values can be pointers to
411 regions.
412 It also stores a constraint_manager, capturing relationships between
413 the values. */
414
415 class region_model
416 {
417 public:
418 region_model (region_model_manager *mgr);
419 region_model (const region_model &other);
420 ~region_model ();
421
422 #if 0//__cplusplus >= 201103
423 region_model (region_model &&other);
424 #endif
425
426 region_model &operator= (const region_model &other);
427
428 bool operator== (const region_model &other) const;
429 bool operator!= (const region_model &other) const
430 {
431 return !(*this == other);
432 }
433
434 hashval_t hash () const;
435
436 void print (pretty_printer *pp) const;
437
438 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
439 void dump (FILE *fp, bool simple, bool multiline) const;
440 void dump (bool simple) const;
441
442 void debug () const;
443
444 void validate () const;
445
446 void canonicalize ();
447 bool canonicalized_p () const;
448
449 void on_assignment (const gassign *stmt, region_model_context *ctxt);
450 const svalue *get_gassign_result (const gassign *assign,
451 region_model_context *ctxt);
452 bool on_call_pre (const gcall *stmt, region_model_context *ctxt,
453 bool *out_terminate_path);
454 void on_call_post (const gcall *stmt,
455 bool unknown_side_effects,
456 region_model_context *ctxt);
457
458 /* Specific handling for on_call_pre. */
459 bool impl_call_alloca (const call_details &cd);
460 void impl_call_analyzer_describe (const gcall *call,
461 region_model_context *ctxt);
462 void impl_call_analyzer_eval (const gcall *call,
463 region_model_context *ctxt);
464 bool impl_call_builtin_expect (const call_details &cd);
465 bool impl_call_calloc (const call_details &cd);
466 bool impl_call_error (const call_details &cd, unsigned min_args,
467 bool *out_terminate_path);
468 void impl_call_free (const call_details &cd);
469 bool impl_call_malloc (const call_details &cd);
470 void impl_call_memcpy (const call_details &cd);
471 bool impl_call_memset (const call_details &cd);
472 void impl_call_realloc (const call_details &cd);
473 void impl_call_strcpy (const call_details &cd);
474 bool impl_call_strlen (const call_details &cd);
475 bool impl_call_operator_new (const call_details &cd);
476 bool impl_call_operator_delete (const call_details &cd);
477 void impl_deallocation_call (const call_details &cd);
478
479 void handle_unrecognized_call (const gcall *call,
480 region_model_context *ctxt);
481 void get_reachable_svalues (svalue_set *out,
482 const svalue *extra_sval,
483 const uncertainty_t *uncertainty);
484
485 void on_return (const greturn *stmt, region_model_context *ctxt);
486 void on_setjmp (const gcall *stmt, const exploded_node *enode,
487 region_model_context *ctxt);
488 void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
489 int setjmp_stack_depth, region_model_context *ctxt);
490
491 void update_for_phis (const supernode *snode,
492 const cfg_superedge *last_cfg_superedge,
493 region_model_context *ctxt);
494
495 void handle_phi (const gphi *phi, tree lhs, tree rhs,
496 region_model_context *ctxt);
497
498 bool maybe_update_for_edge (const superedge &edge,
499 const gimple *last_stmt,
500 region_model_context *ctxt,
501 rejected_constraint **out);
502
503 const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
504 region_model_context *ctxt);
get_current_frame()505 const frame_region *get_current_frame () const { return m_current_frame; }
506 function * get_current_function () const;
507 void pop_frame (const region *result_dst,
508 const svalue **out_result,
509 region_model_context *ctxt);
510 int get_stack_depth () const;
511 const frame_region *get_frame_at_index (int index) const;
512
513 const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
514 const region *get_lvalue (tree expr, region_model_context *ctxt) const;
515 const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
516 const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
517
518 const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
519 region_model_context *ctxt) const;
520
521 const svalue *get_rvalue_for_bits (tree type,
522 const region *reg,
523 const bit_range &bits) const;
524
525 void set_value (const region *lhs_reg, const svalue *rhs_sval,
526 region_model_context *ctxt);
527 void set_value (tree lhs, tree rhs, region_model_context *ctxt);
528 void clobber_region (const region *reg);
529 void purge_region (const region *reg);
530 void zero_fill_region (const region *reg);
531 void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
532
533 void copy_region (const region *dst_reg, const region *src_reg,
534 region_model_context *ctxt);
535 tristate eval_condition (const svalue *lhs,
536 enum tree_code op,
537 const svalue *rhs) const;
538 tristate eval_condition_without_cm (const svalue *lhs,
539 enum tree_code op,
540 const svalue *rhs) const;
541 tristate compare_initial_and_pointer (const initial_svalue *init,
542 const region_svalue *ptr) const;
543 tristate eval_condition (tree lhs,
544 enum tree_code op,
545 tree rhs,
546 region_model_context *ctxt);
547 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
548 region_model_context *ctxt);
549 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
550 region_model_context *ctxt,
551 rejected_constraint **out);
552
553 const region *create_region_for_heap_alloc (const svalue *size_in_bytes);
554 const region *create_region_for_alloca (const svalue *size_in_bytes);
555
556 tree get_representative_tree (const svalue *sval) const;
557 path_var
558 get_representative_path_var (const svalue *sval,
559 svalue_set *visited) const;
560 path_var
561 get_representative_path_var (const region *reg,
562 svalue_set *visited) const;
563
564 /* For selftests. */
get_constraints()565 constraint_manager *get_constraints ()
566 {
567 return m_constraints;
568 }
569
get_store()570 store *get_store () { return &m_store; }
get_store()571 const store *get_store () const { return &m_store; }
572
get_manager()573 region_model_manager *get_manager () const { return m_mgr; }
574
575 void unbind_region_and_descendents (const region *reg,
576 enum poison_kind pkind);
577
578 bool can_merge_with_p (const region_model &other_model,
579 const program_point &point,
580 region_model *out_model) const;
581
582 tree get_fndecl_for_call (const gcall *call,
583 region_model_context *ctxt);
584
585 void get_ssa_name_regions_for_current_frame
586 (auto_vec<const decl_region *> *out) const;
587 static void append_ssa_names_cb (const region *base_reg,
588 struct append_ssa_names_cb_data *data);
589
590 const svalue *get_store_value (const region *reg) const;
591
592 bool region_exists_p (const region *reg) const;
593
594 void loop_replay_fixup (const region_model *dst_state);
595
596 private:
597 const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
598 const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
599
600 path_var
601 get_representative_path_var_1 (const svalue *sval,
602 svalue_set *visited) const;
603 path_var
604 get_representative_path_var_1 (const region *reg,
605 svalue_set *visited) const;
606
607 void add_any_constraints_from_ssa_def_stmt (tree lhs,
608 enum tree_code op,
609 tree rhs,
610 region_model_context *ctxt);
611 void add_any_constraints_from_gassign (enum tree_code op,
612 tree rhs,
613 const gassign *assign,
614 region_model_context *ctxt);
615 void add_any_constraints_from_gcall (enum tree_code op,
616 tree rhs,
617 const gcall *call,
618 region_model_context *ctxt);
619
620 void update_for_call_superedge (const call_superedge &call_edge,
621 region_model_context *ctxt);
622 void update_for_return_superedge (const return_superedge &return_edge,
623 region_model_context *ctxt);
624 void update_for_call_summary (const callgraph_superedge &cg_sedge,
625 region_model_context *ctxt);
626 bool apply_constraints_for_gcond (const cfg_superedge &edge,
627 const gcond *cond_stmt,
628 region_model_context *ctxt,
629 rejected_constraint **out);
630 bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
631 const gswitch *switch_stmt,
632 region_model_context *ctxt,
633 rejected_constraint **out);
634 bool apply_constraints_for_exception (const gimple *last_stmt,
635 region_model_context *ctxt,
636 rejected_constraint **out);
637
638 int poison_any_pointers_to_descendents (const region *reg,
639 enum poison_kind pkind);
640
641 void on_top_level_param (tree param, region_model_context *ctxt);
642
643 void record_dynamic_extents (const region *reg,
644 const svalue *size_in_bytes);
645
646 bool called_from_main_p () const;
647 const svalue *get_initial_value_for_global (const region *reg) const;
648
649 void check_for_writable_region (const region* dest_reg,
650 region_model_context *ctxt) const;
651
652 /* Storing this here to avoid passing it around everywhere. */
653 region_model_manager *const m_mgr;
654
655 store m_store;
656
657 constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
658
659 const frame_region *m_current_frame;
660 };
661
662 /* Some region_model activity could lead to warnings (e.g. attempts to use an
663 uninitialized value). This abstract base class encapsulates an interface
664 for the region model to use when emitting such warnings.
665
666 Having this as an abstract base class allows us to support the various
667 operations needed by program_state in the analyzer within region_model,
668 whilst keeping them somewhat modularized. */
669
670 class region_model_context
671 {
672 public:
673 virtual void warn (pending_diagnostic *d) = 0;
674
675 /* Hook for clients to be notified when an SVAL that was reachable
676 in a previous state is no longer live, so that clients can emit warnings
677 about leaks. */
678 virtual void on_svalue_leak (const svalue *sval) = 0;
679
680 /* Hook for clients to be notified when the set of explicitly live
681 svalues changes, so that they can purge state relating to dead
682 svalues. */
683 virtual void on_liveness_change (const svalue_set &live_svalues,
684 const region_model *model) = 0;
685
686 virtual logger *get_logger () = 0;
687
688 /* Hook for clients to be notified when the condition
689 "LHS OP RHS" is added to the region model.
690 This exists so that state machines can detect tests on edges,
691 and use them to trigger sm-state transitions (e.g. transitions due
692 to ptrs becoming known to be NULL or non-NULL, rather than just
693 "unchecked") */
694 virtual void on_condition (tree lhs, enum tree_code op, tree rhs) = 0;
695
696 /* Hooks for clients to be notified when an unknown change happens
697 to SVAL (in response to a call to an unknown function). */
698 virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
699
700 /* Hooks for clients to be notified when a phi node is handled,
701 where RHS is the pertinent argument. */
702 virtual void on_phi (const gphi *phi, tree rhs) = 0;
703
704 /* Hooks for clients to be notified when the region model doesn't
705 know how to handle the tree code of T at LOC. */
706 virtual void on_unexpected_tree_code (tree t,
707 const dump_location_t &loc) = 0;
708
709 /* Hook for clients to be notified when a function_decl escapes. */
710 virtual void on_escaped_function (tree fndecl) = 0;
711
712 virtual uncertainty_t *get_uncertainty () = 0;
713 };
714
715 /* A "do nothing" subclass of region_model_context. */
716
717 class noop_region_model_context : public region_model_context
718 {
719 public:
warn(pending_diagnostic *)720 void warn (pending_diagnostic *) OVERRIDE {}
on_svalue_leak(const svalue *)721 void on_svalue_leak (const svalue *) OVERRIDE {}
on_liveness_change(const svalue_set &,const region_model *)722 void on_liveness_change (const svalue_set &,
723 const region_model *) OVERRIDE {}
get_logger()724 logger *get_logger () OVERRIDE { return NULL; }
on_condition(tree lhs ATTRIBUTE_UNUSED,enum tree_code op ATTRIBUTE_UNUSED,tree rhs ATTRIBUTE_UNUSED)725 void on_condition (tree lhs ATTRIBUTE_UNUSED,
726 enum tree_code op ATTRIBUTE_UNUSED,
727 tree rhs ATTRIBUTE_UNUSED) OVERRIDE
728 {
729 }
on_unknown_change(const svalue * sval ATTRIBUTE_UNUSED,bool is_mutable ATTRIBUTE_UNUSED)730 void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
731 bool is_mutable ATTRIBUTE_UNUSED) OVERRIDE
732 {
733 }
on_phi(const gphi * phi ATTRIBUTE_UNUSED,tree rhs ATTRIBUTE_UNUSED)734 void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
735 tree rhs ATTRIBUTE_UNUSED) OVERRIDE
736 {
737 }
on_unexpected_tree_code(tree,const dump_location_t &)738 void on_unexpected_tree_code (tree, const dump_location_t &) OVERRIDE {}
739
on_escaped_function(tree)740 void on_escaped_function (tree) OVERRIDE {}
741
get_uncertainty()742 uncertainty_t *get_uncertainty () OVERRIDE { return NULL; }
743 };
744
745 /* A subclass of region_model_context for determining if operations fail
746 e.g. "can we generate a region for the lvalue of EXPR?". */
747
748 class tentative_region_model_context : public noop_region_model_context
749 {
750 public:
tentative_region_model_context()751 tentative_region_model_context () : m_num_unexpected_codes (0) {}
752
on_unexpected_tree_code(tree,const dump_location_t &)753 void on_unexpected_tree_code (tree, const dump_location_t &)
754 FINAL OVERRIDE
755 {
756 m_num_unexpected_codes++;
757 }
758
had_errors_p()759 bool had_errors_p () const { return m_num_unexpected_codes > 0; }
760
761 private:
762 int m_num_unexpected_codes;
763 };
764
765 /* A bundle of data for use when attempting to merge two region_model
766 instances to make a third. */
767
768 struct model_merger
769 {
model_mergermodel_merger770 model_merger (const region_model *model_a,
771 const region_model *model_b,
772 const program_point &point,
773 region_model *merged_model)
774 : m_model_a (model_a), m_model_b (model_b),
775 m_point (point),
776 m_merged_model (merged_model)
777 {
778 }
779
780 void dump_to_pp (pretty_printer *pp, bool simple) const;
781 void dump (FILE *fp, bool simple) const;
782 void dump (bool simple) const;
783
get_managermodel_merger784 region_model_manager *get_manager () const
785 {
786 return m_model_a->get_manager ();
787 }
788
789 const region_model *m_model_a;
790 const region_model *m_model_b;
791 const program_point &m_point;
792 region_model *m_merged_model;
793 };
794
795 /* A record that can (optionally) be written out when
796 region_model::add_constraint fails. */
797
798 struct rejected_constraint
799 {
rejected_constraintrejected_constraint800 rejected_constraint (const region_model &model,
801 tree lhs, enum tree_code op, tree rhs)
802 : m_model (model), m_lhs (lhs), m_op (op), m_rhs (rhs)
803 {}
804
805 void dump_to_pp (pretty_printer *pp) const;
806
807 region_model m_model;
808 tree m_lhs;
809 enum tree_code m_op;
810 tree m_rhs;
811 };
812
813 /* A bundle of state. */
814
815 class engine
816 {
817 public:
get_model_manager()818 region_model_manager *get_model_manager () { return &m_mgr; }
819
820 void log_stats (logger *logger) const;
821
822 private:
823 region_model_manager m_mgr;
824
825 };
826
827 } // namespace ana
828
829 extern void debug (const region_model &rmodel);
830
831 namespace ana {
832
833 #if CHECKING_P
834
835 namespace selftest {
836
837 using namespace ::selftest;
838
839 /* An implementation of region_model_context for use in selftests, which
840 stores any pending_diagnostic instances passed to it. */
841
842 class test_region_model_context : public noop_region_model_context
843 {
844 public:
warn(pending_diagnostic * d)845 void warn (pending_diagnostic *d) FINAL OVERRIDE
846 {
847 m_diagnostics.safe_push (d);
848 }
849
get_num_diagnostics()850 unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
851
on_unexpected_tree_code(tree t,const dump_location_t &)852 void on_unexpected_tree_code (tree t, const dump_location_t &)
853 FINAL OVERRIDE
854 {
855 internal_error ("unhandled tree code: %qs",
856 get_tree_code_name (TREE_CODE (t)));
857 }
858
859 private:
860 /* Implicitly delete any diagnostics in the dtor. */
861 auto_delete_vec<pending_diagnostic> m_diagnostics;
862 };
863
864 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
865 Verify that MODEL remains satisfiable. */
866
867 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
868 SELFTEST_BEGIN_STMT \
869 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
870 ASSERT_TRUE (sat); \
871 SELFTEST_END_STMT
872
873 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
874 Verify that the result is not satisfiable. */
875
876 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
877 SELFTEST_BEGIN_STMT \
878 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
879 ASSERT_FALSE (sat); \
880 SELFTEST_END_STMT
881
882 /* Implementation detail of the ASSERT_CONDITION_* macros. */
883
884 void assert_condition (const location &loc,
885 region_model &model,
886 const svalue *lhs, tree_code op, const svalue *rhs,
887 tristate expected);
888
889 void assert_condition (const location &loc,
890 region_model &model,
891 tree lhs, tree_code op, tree rhs,
892 tristate expected);
893
894 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
895 as "true". */
896
897 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
898 SELFTEST_BEGIN_STMT \
899 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
900 tristate (tristate::TS_TRUE)); \
901 SELFTEST_END_STMT
902
903 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
904 as "false". */
905
906 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
907 SELFTEST_BEGIN_STMT \
908 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
909 tristate (tristate::TS_FALSE)); \
910 SELFTEST_END_STMT
911
912 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
913 as "unknown". */
914
915 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
916 SELFTEST_BEGIN_STMT \
917 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
918 tristate (tristate::TS_UNKNOWN)); \
919 SELFTEST_END_STMT
920
921 } /* end of namespace selftest. */
922
923 #endif /* #if CHECKING_P */
924
925 } // namespace ana
926
927 #endif /* GCC_ANALYZER_REGION_MODEL_H */
928