1 /* Classes for modeling the state of memory.
2 Copyright (C) 2019-2023 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 "selftest.h"
31 #include "analyzer/svalue.h"
32 #include "analyzer/region.h"
33 #include "analyzer/known-function-manager.h"
34 #include "analyzer/region-model-manager.h"
35 #include "analyzer/pending-diagnostic.h"
36
37 using namespace ana;
38
39 namespace inchash
40 {
41 extern void add_path_var (path_var pv, hash &hstate);
42 } // namespace inchash
43
44 namespace ana {
45
46 template <typename T>
47 class one_way_id_map
48 {
49 public:
50 one_way_id_map (int num_ids);
51 void put (T src, T dst);
52 T get_dst_for_src (T src) const;
53 void dump_to_pp (pretty_printer *pp) const;
54 void dump () const;
55 void update (T *) const;
56
57 private:
58 auto_vec<T> m_src_to_dst;
59 };
60
61 /* class one_way_id_map. */
62
63 /* one_way_id_map's ctor, which populates the map with dummy null values. */
64
65 template <typename T>
66 inline one_way_id_map<T>::one_way_id_map (int num_svalues)
67 : m_src_to_dst (num_svalues)
68 {
69 for (int i = 0; i < num_svalues; i++)
70 m_src_to_dst.quick_push (T::null ());
71 }
72
73 /* Record that SRC is to be mapped to DST. */
74
75 template <typename T>
76 inline void
77 one_way_id_map<T>::put (T src, T dst)
78 {
79 m_src_to_dst[src.as_int ()] = dst;
80 }
81
82 /* Get the new value for SRC within the map. */
83
84 template <typename T>
85 inline T
86 one_way_id_map<T>::get_dst_for_src (T src) const
87 {
88 if (src.null_p ())
89 return src;
90 return m_src_to_dst[src.as_int ()];
91 }
92
93 /* Dump this map to PP. */
94
95 template <typename T>
96 inline void
97 one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
98 {
99 pp_string (pp, "src to dst: {");
100 unsigned i;
101 T *dst;
102 FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
103 {
104 if (i > 0)
105 pp_string (pp, ", ");
106 T src (T::from_int (i));
107 src.print (pp);
108 pp_string (pp, " -> ");
109 dst->print (pp);
110 }
111 pp_string (pp, "}");
112 pp_newline (pp);
113 }
114
115 /* Dump this map to stderr. */
116
117 template <typename T>
118 DEBUG_FUNCTION inline void
119 one_way_id_map<T>::dump () const
120 {
121 pretty_printer pp;
122 pp.buffer->stream = stderr;
123 dump_to_pp (&pp);
124 pp_flush (&pp);
125 }
126
127 /* Update *ID from the old value to its new value in this map. */
128
129 template <typename T>
130 inline void
131 one_way_id_map<T>::update (T *id) const
132 {
133 *id = get_dst_for_src (*id);
134 }
135
136 /* A mapping from region to svalue for use when tracking state. */
137
138 class region_to_value_map
139 {
140 public:
141 typedef hash_map<const region *, const svalue *> hash_map_t;
142 typedef hash_map_t::iterator iterator;
143
144 region_to_value_map () : m_hash_map () {}
145 region_to_value_map (const region_to_value_map &other)
146 : m_hash_map (other.m_hash_map) {}
147 region_to_value_map &operator= (const region_to_value_map &other);
148
149 bool operator== (const region_to_value_map &other) const;
150 bool operator!= (const region_to_value_map &other) const
151 {
152 return !(*this == other);
153 }
154
155 iterator begin () const { return m_hash_map.begin (); }
156 iterator end () const { return m_hash_map.end (); }
157
158 const svalue * const *get (const region *reg) const
159 {
160 return const_cast <hash_map_t &> (m_hash_map).get (reg);
161 }
162 void put (const region *reg, const svalue *sval)
163 {
164 m_hash_map.put (reg, sval);
165 }
166 void remove (const region *reg)
167 {
168 m_hash_map.remove (reg);
169 }
170
171 bool is_empty () const { return m_hash_map.is_empty (); }
172
173 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
174 void dump (bool simple) const;
175
176 bool can_merge_with_p (const region_to_value_map &other,
177 region_to_value_map *out) const;
178
179 void purge_state_involving (const svalue *sval);
180
181 private:
182 hash_map_t m_hash_map;
183 };
184
185 /* Various operations delete information from a region_model.
186
187 This struct tracks how many of each kind of entity were purged (e.g.
188 for selftests, and for debugging). */
189
190 struct purge_stats
191 {
192 purge_stats ()
193 : m_num_svalues (0),
194 m_num_regions (0),
195 m_num_equiv_classes (0),
196 m_num_constraints (0),
197 m_num_bounded_ranges_constraints (0),
198 m_num_client_items (0)
199 {}
200
201 int m_num_svalues;
202 int m_num_regions;
203 int m_num_equiv_classes;
204 int m_num_constraints;
205 int m_num_bounded_ranges_constraints;
206 int m_num_client_items;
207 };
208
209 /* A base class for visiting regions and svalues, with do-nothing
210 base implementations of the per-subclass vfuncs. */
211
212 class visitor
213 {
214 public:
215 virtual void visit_region_svalue (const region_svalue *) {}
216 virtual void visit_constant_svalue (const constant_svalue *) {}
217 virtual void visit_unknown_svalue (const unknown_svalue *) {}
218 virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
219 virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
220 virtual void visit_initial_svalue (const initial_svalue *) {}
221 virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
222 virtual void visit_binop_svalue (const binop_svalue *) {}
223 virtual void visit_sub_svalue (const sub_svalue *) {}
224 virtual void visit_repeated_svalue (const repeated_svalue *) {}
225 virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
226 virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
227 virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
228 virtual void visit_widening_svalue (const widening_svalue *) {}
229 virtual void visit_compound_svalue (const compound_svalue *) {}
230 virtual void visit_conjured_svalue (const conjured_svalue *) {}
231 virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
232 virtual void visit_const_fn_result_svalue (const const_fn_result_svalue *) {}
233
234 virtual void visit_region (const region *) {}
235 };
236
237 struct append_regions_cb_data;
238
239 /* A region_model encapsulates a representation of the state of memory, with
240 a tree of regions, along with their associated values.
241 The representation is graph-like because values can be pointers to
242 regions.
243 It also stores:
244 - a constraint_manager, capturing relationships between the values, and
245 - dynamic extents, mapping dynamically-allocated regions to svalues (their
246 capacities). */
247
248 class region_model
249 {
250 public:
251 typedef region_to_value_map dynamic_extents_t;
252
253 region_model (region_model_manager *mgr);
254 region_model (const region_model &other);
255 ~region_model ();
256 region_model &operator= (const region_model &other);
257
258 bool operator== (const region_model &other) const;
259 bool operator!= (const region_model &other) const
260 {
261 return !(*this == other);
262 }
263
264 hashval_t hash () const;
265
266 void print (pretty_printer *pp) const;
267
268 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
269 void dump (FILE *fp, bool simple, bool multiline) const;
270 void dump (bool simple) const;
271
272 void debug () const;
273
274 void validate () const;
275
276 void canonicalize ();
277 bool canonicalized_p () const;
278
279 void
280 on_stmt_pre (const gimple *stmt,
281 bool *out_unknown_side_effects,
282 region_model_context *ctxt);
283
284 void on_assignment (const gassign *stmt, region_model_context *ctxt);
285 const svalue *get_gassign_result (const gassign *assign,
286 region_model_context *ctxt);
287 void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
288 bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
289 void on_call_post (const gcall *stmt,
290 bool unknown_side_effects,
291 region_model_context *ctxt);
292
293 void purge_state_involving (const svalue *sval, region_model_context *ctxt);
294
295 void impl_deallocation_call (const call_details &cd);
296
297 const svalue *maybe_get_copy_bounds (const region *src_reg,
298 const svalue *num_bytes_sval);
299 void update_for_int_cst_return (const call_details &cd,
300 int retval,
301 bool unmergeable);
302 void update_for_zero_return (const call_details &cd,
303 bool unmergeable);
304 void update_for_nonzero_return (const call_details &cd);
305
306 void handle_unrecognized_call (const gcall *call,
307 region_model_context *ctxt);
308 void get_reachable_svalues (svalue_set *out,
309 const svalue *extra_sval,
310 const uncertainty_t *uncertainty);
311
312 void on_return (const greturn *stmt, region_model_context *ctxt);
313 void on_setjmp (const gcall *stmt, const exploded_node *enode,
314 region_model_context *ctxt);
315 void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
316 int setjmp_stack_depth, region_model_context *ctxt);
317
318 void update_for_phis (const supernode *snode,
319 const cfg_superedge *last_cfg_superedge,
320 region_model_context *ctxt);
321
322 void handle_phi (const gphi *phi, tree lhs, tree rhs,
323 const region_model &old_state,
324 region_model_context *ctxt);
325
326 bool maybe_update_for_edge (const superedge &edge,
327 const gimple *last_stmt,
328 region_model_context *ctxt,
329 rejected_constraint **out);
330
331 void update_for_gcall (const gcall *call_stmt,
332 region_model_context *ctxt,
333 function *callee = NULL);
334
335 void update_for_return_gcall (const gcall *call_stmt,
336 region_model_context *ctxt);
337
338 const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
339 region_model_context *ctxt);
340 const frame_region *get_current_frame () const { return m_current_frame; }
341 function * get_current_function () const;
342 void pop_frame (tree result_lvalue,
343 const svalue **out_result,
344 region_model_context *ctxt,
345 bool eval_return_svalue = true);
346 int get_stack_depth () const;
347 const frame_region *get_frame_at_index (int index) const;
348
349 const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
350 const region *get_lvalue (tree expr, region_model_context *ctxt) const;
351 const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
352 const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
353
354 const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
355 region_model_context *ctxt) const;
356
357 const svalue *get_rvalue_for_bits (tree type,
358 const region *reg,
359 const bit_range &bits,
360 region_model_context *ctxt) const;
361
362 void set_value (const region *lhs_reg, const svalue *rhs_sval,
363 region_model_context *ctxt);
364 void set_value (tree lhs, tree rhs, region_model_context *ctxt);
365 void clobber_region (const region *reg);
366 void purge_region (const region *reg);
367 void fill_region (const region *reg, const svalue *sval);
368 void zero_fill_region (const region *reg);
369 void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
370
371 tristate eval_condition (const svalue *lhs,
372 enum tree_code op,
373 const svalue *rhs) const;
374 tristate compare_initial_and_pointer (const initial_svalue *init,
375 const region_svalue *ptr) const;
376 tristate symbolic_greater_than (const binop_svalue *a,
377 const svalue *b) const;
378 tristate structural_equality (const svalue *a, const svalue *b) const;
379 tristate eval_condition (tree lhs,
380 enum tree_code op,
381 tree rhs,
382 region_model_context *ctxt) const;
383 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
384 region_model_context *ctxt);
385 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
386 region_model_context *ctxt,
387 rejected_constraint **out);
388
389 const region *
390 get_or_create_region_for_heap_alloc (const svalue *size_in_bytes,
391 region_model_context *ctxt);
392 const region *create_region_for_alloca (const svalue *size_in_bytes,
393 region_model_context *ctxt);
394 void get_referenced_base_regions (auto_bitmap &out_ids) const;
395
396 tree get_representative_tree (const svalue *sval) const;
397 tree get_representative_tree (const region *reg) const;
398 path_var
399 get_representative_path_var (const svalue *sval,
400 svalue_set *visited) const;
401 path_var
402 get_representative_path_var (const region *reg,
403 svalue_set *visited) const;
404
405 /* For selftests. */
406 constraint_manager *get_constraints ()
407 {
408 return m_constraints;
409 }
410
411 store *get_store () { return &m_store; }
412 const store *get_store () const { return &m_store; }
413
414 const dynamic_extents_t &
415 get_dynamic_extents () const
416 {
417 return m_dynamic_extents;
418 }
419 const svalue *get_dynamic_extents (const region *reg) const;
420 void set_dynamic_extents (const region *reg,
421 const svalue *size_in_bytes,
422 region_model_context *ctxt);
423 void unset_dynamic_extents (const region *reg);
424
425 region_model_manager *get_manager () const { return m_mgr; }
426 bounded_ranges_manager *get_range_manager () const
427 {
428 return m_mgr->get_range_manager ();
429 }
430
431 void unbind_region_and_descendents (const region *reg,
432 enum poison_kind pkind);
433
434 bool can_merge_with_p (const region_model &other_model,
435 const program_point &point,
436 region_model *out_model,
437 const extrinsic_state *ext_state = NULL,
438 const program_state *state_a = NULL,
439 const program_state *state_b = NULL) const;
440
441 tree get_fndecl_for_call (const gcall *call,
442 region_model_context *ctxt);
443
444 void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
445 static void append_regions_cb (const region *base_reg,
446 struct append_regions_cb_data *data);
447
448 const svalue *get_store_value (const region *reg,
449 region_model_context *ctxt) const;
450
451 bool region_exists_p (const region *reg) const;
452
453 void loop_replay_fixup (const region_model *dst_state);
454
455 const svalue *get_capacity (const region *reg) const;
456
457 const svalue *get_string_size (const svalue *sval) const;
458 const svalue *get_string_size (const region *reg) const;
459
460 bool replay_call_summary (call_summary_replay &r,
461 const region_model &summary);
462
463 void maybe_complain_about_infoleak (const region *dst_reg,
464 const svalue *copied_sval,
465 const region *src_reg,
466 region_model_context *ctxt);
467
468 void set_errno (const call_details &cd);
469
470 /* Implemented in sm-fd.cc */
471 void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
472
473 /* Implemented in sm-malloc.cc */
474 void on_realloc_with_move (const call_details &cd,
475 const svalue *old_ptr_sval,
476 const svalue *new_ptr_sval);
477
478 /* Implemented in sm-taint.cc. */
479 void mark_as_tainted (const svalue *sval,
480 region_model_context *ctxt);
481
482 bool add_constraint (const svalue *lhs,
483 enum tree_code op,
484 const svalue *rhs,
485 region_model_context *ctxt);
486
487 const svalue *check_for_poison (const svalue *sval,
488 tree expr,
489 const region *src_region,
490 region_model_context *ctxt) const;
491
492 void check_region_for_write (const region *dest_reg,
493 region_model_context *ctxt) const;
494
495 private:
496 const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
497 const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
498
499 path_var
500 get_representative_path_var_1 (const svalue *sval,
501 svalue_set *visited) const;
502 path_var
503 get_representative_path_var_1 (const region *reg,
504 svalue_set *visited) const;
505
506 const known_function *get_known_function (tree fndecl,
507 const call_details &cd) const;
508 const known_function *get_known_function (enum internal_fn) const;
509
510 bool add_constraints_from_binop (const svalue *outer_lhs,
511 enum tree_code outer_op,
512 const svalue *outer_rhs,
513 bool *out,
514 region_model_context *ctxt);
515
516 void update_for_call_superedge (const call_superedge &call_edge,
517 region_model_context *ctxt);
518 void update_for_return_superedge (const return_superedge &return_edge,
519 region_model_context *ctxt);
520 bool apply_constraints_for_gcond (const cfg_superedge &edge,
521 const gcond *cond_stmt,
522 region_model_context *ctxt,
523 rejected_constraint **out);
524 bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
525 const gswitch *switch_stmt,
526 region_model_context *ctxt,
527 rejected_constraint **out);
528 bool apply_constraints_for_exception (const gimple *last_stmt,
529 region_model_context *ctxt,
530 rejected_constraint **out);
531
532 int poison_any_pointers_to_descendents (const region *reg,
533 enum poison_kind pkind);
534
535 void on_top_level_param (tree param,
536 bool nonnull,
537 region_model_context *ctxt);
538
539 bool called_from_main_p () const;
540 const svalue *get_initial_value_for_global (const region *reg) const;
541
542 const region * get_region_for_poisoned_expr (tree expr) const;
543
544 void check_dynamic_size_for_taint (enum memory_space mem_space,
545 const svalue *size_in_bytes,
546 region_model_context *ctxt) const;
547 void check_dynamic_size_for_floats (const svalue *size_in_bytes,
548 region_model_context *ctxt) const;
549
550 void check_region_for_taint (const region *reg,
551 enum access_direction dir,
552 region_model_context *ctxt) const;
553
554 void check_for_writable_region (const region* dest_reg,
555 region_model_context *ctxt) const;
556 void check_region_access (const region *reg,
557 enum access_direction dir,
558 region_model_context *ctxt) const;
559 void check_region_for_read (const region *src_reg,
560 region_model_context *ctxt) const;
561 void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
562 region_model_context *ctxt) const;
563
564 /* Implemented in bounds-checking.cc */
565 void check_symbolic_bounds (const region *base_reg,
566 const svalue *sym_byte_offset,
567 const svalue *num_bytes_sval,
568 const svalue *capacity,
569 enum access_direction dir,
570 region_model_context *ctxt) const;
571 void check_region_bounds (const region *reg, enum access_direction dir,
572 region_model_context *ctxt) const;
573
574 void check_call_args (const call_details &cd) const;
575 void check_external_function_for_access_attr (const gcall *call,
576 tree callee_fndecl,
577 region_model_context *ctxt) const;
578
579 /* Storing this here to avoid passing it around everywhere. */
580 region_model_manager *const m_mgr;
581
582 store m_store;
583
584 constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
585
586 const frame_region *m_current_frame;
587
588 /* Map from base region to size in bytes, for tracking the sizes of
589 dynamically-allocated regions.
590 This is part of the region_model rather than the region to allow for
591 memory regions to be resized (e.g. by realloc). */
592 dynamic_extents_t m_dynamic_extents;
593 };
594
595 /* Some region_model activity could lead to warnings (e.g. attempts to use an
596 uninitialized value). This abstract base class encapsulates an interface
597 for the region model to use when emitting such warnings.
598
599 Having this as an abstract base class allows us to support the various
600 operations needed by program_state in the analyzer within region_model,
601 whilst keeping them somewhat modularized. */
602
603 class region_model_context
604 {
605 public:
606 /* Hook for clients to store pending diagnostics.
607 Return true if the diagnostic was stored, or false if it was deleted. */
608 virtual bool warn (std::unique_ptr<pending_diagnostic> d) = 0;
609
610 /* Hook for clients to add a note to the last previously stored
611 pending diagnostic. */
612 virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
613
614 /* Hook for clients to be notified when an SVAL that was reachable
615 in a previous state is no longer live, so that clients can emit warnings
616 about leaks. */
617 virtual void on_svalue_leak (const svalue *sval) = 0;
618
619 /* Hook for clients to be notified when the set of explicitly live
620 svalues changes, so that they can purge state relating to dead
621 svalues. */
622 virtual void on_liveness_change (const svalue_set &live_svalues,
623 const region_model *model) = 0;
624
625 virtual logger *get_logger () = 0;
626
627 /* Hook for clients to be notified when the condition
628 "LHS OP RHS" is added to the region model.
629 This exists so that state machines can detect tests on edges,
630 and use them to trigger sm-state transitions (e.g. transitions due
631 to ptrs becoming known to be NULL or non-NULL, rather than just
632 "unchecked") */
633 virtual void on_condition (const svalue *lhs,
634 enum tree_code op,
635 const svalue *rhs) = 0;
636
637 /* Hook for clients to be notified when the condition that
638 SVAL is within RANGES is added to the region model.
639 Similar to on_condition, but for use when handling switch statements.
640 RANGES is non-empty. */
641 virtual void on_bounded_ranges (const svalue &sval,
642 const bounded_ranges &ranges) = 0;
643
644 /* Hook for clients to be notified when a frame is popped from the stack. */
645 virtual void on_pop_frame (const frame_region *) = 0;
646
647 /* Hooks for clients to be notified when an unknown change happens
648 to SVAL (in response to a call to an unknown function). */
649 virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
650
651 /* Hooks for clients to be notified when a phi node is handled,
652 where RHS is the pertinent argument. */
653 virtual void on_phi (const gphi *phi, tree rhs) = 0;
654
655 /* Hooks for clients to be notified when the region model doesn't
656 know how to handle the tree code of T at LOC. */
657 virtual void on_unexpected_tree_code (tree t,
658 const dump_location_t &loc) = 0;
659
660 /* Hook for clients to be notified when a function_decl escapes. */
661 virtual void on_escaped_function (tree fndecl) = 0;
662
663 virtual uncertainty_t *get_uncertainty () = 0;
664
665 /* Hook for clients to purge state involving SVAL. */
666 virtual void purge_state_involving (const svalue *sval) = 0;
667
668 /* Hook for clients to split state with a non-standard path. */
669 virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
670
671 /* Hook for clients to terminate the standard path. */
672 virtual void terminate_path () = 0;
673
674 virtual const extrinsic_state *get_ext_state () const = 0;
675
676 /* Hook for clients to access the a specific state machine in
677 any underlying program_state. */
678 virtual bool
679 get_state_map_by_name (const char *name,
680 sm_state_map **out_smap,
681 const state_machine **out_sm,
682 unsigned *out_sm_idx,
683 std::unique_ptr<sm_context> *out_sm_context) = 0;
684
685 /* Precanned ways for clients to access specific state machines. */
686 bool get_fd_map (sm_state_map **out_smap,
687 const state_machine **out_sm,
688 unsigned *out_sm_idx,
689 std::unique_ptr<sm_context> *out_sm_context)
690 {
691 return get_state_map_by_name ("file-descriptor", out_smap, out_sm,
692 out_sm_idx, out_sm_context);
693 }
694 bool get_malloc_map (sm_state_map **out_smap,
695 const state_machine **out_sm,
696 unsigned *out_sm_idx)
697 {
698 return get_state_map_by_name ("malloc", out_smap, out_sm, out_sm_idx, NULL);
699 }
700 bool get_taint_map (sm_state_map **out_smap,
701 const state_machine **out_sm,
702 unsigned *out_sm_idx)
703 {
704 return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx, NULL);
705 }
706
707 bool possibly_tainted_p (const svalue *sval);
708
709 /* Get the current statement, if any. */
710 virtual const gimple *get_stmt () const = 0;
711 };
712
713 /* A "do nothing" subclass of region_model_context. */
714
715 class noop_region_model_context : public region_model_context
716 {
717 public:
718 bool warn (std::unique_ptr<pending_diagnostic>) override { return false; }
719 void add_note (std::unique_ptr<pending_note>) override;
720 void on_svalue_leak (const svalue *) override {}
721 void on_liveness_change (const svalue_set &,
722 const region_model *) override {}
723 logger *get_logger () override { return NULL; }
724 void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
725 enum tree_code op ATTRIBUTE_UNUSED,
726 const svalue *rhs ATTRIBUTE_UNUSED) override
727 {
728 }
729 void on_bounded_ranges (const svalue &,
730 const bounded_ranges &) override
731 {
732 }
733 void on_pop_frame (const frame_region *) override {}
734 void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
735 bool is_mutable ATTRIBUTE_UNUSED) override
736 {
737 }
738 void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
739 tree rhs ATTRIBUTE_UNUSED) override
740 {
741 }
742 void on_unexpected_tree_code (tree, const dump_location_t &) override {}
743
744 void on_escaped_function (tree) override {}
745
746 uncertainty_t *get_uncertainty () override { return NULL; }
747
748 void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
749
750 void bifurcate (std::unique_ptr<custom_edge_info> info) override;
751 void terminate_path () override;
752
753 const extrinsic_state *get_ext_state () const override { return NULL; }
754
755 bool get_state_map_by_name (const char *,
756 sm_state_map **,
757 const state_machine **,
758 unsigned *,
759 std::unique_ptr<sm_context> *) override
760 {
761 return false;
762 }
763
764 const gimple *get_stmt () const override { return NULL; }
765 };
766
767 /* A subclass of region_model_context for determining if operations fail
768 e.g. "can we generate a region for the lvalue of EXPR?". */
769
770 class tentative_region_model_context : public noop_region_model_context
771 {
772 public:
773 tentative_region_model_context () : m_num_unexpected_codes (0) {}
774
775 void on_unexpected_tree_code (tree, const dump_location_t &)
776 final override
777 {
778 m_num_unexpected_codes++;
779 }
780
781 bool had_errors_p () const { return m_num_unexpected_codes > 0; }
782
783 private:
784 int m_num_unexpected_codes;
785 };
786
787 /* Subclass of region_model_context that wraps another context, allowing
788 for extra code to be added to the various hooks. */
789
790 class region_model_context_decorator : public region_model_context
791 {
792 public:
793 bool warn (std::unique_ptr<pending_diagnostic> d) override
794 {
795 return m_inner->warn (std::move (d));
796 }
797
798 void add_note (std::unique_ptr<pending_note> pn) override
799 {
800 m_inner->add_note (std::move (pn));
801 }
802
803 void on_svalue_leak (const svalue *sval) override
804 {
805 m_inner->on_svalue_leak (sval);
806 }
807
808 void on_liveness_change (const svalue_set &live_svalues,
809 const region_model *model) override
810 {
811 m_inner->on_liveness_change (live_svalues, model);
812 }
813
814 logger *get_logger () override
815 {
816 return m_inner->get_logger ();
817 }
818
819 void on_condition (const svalue *lhs,
820 enum tree_code op,
821 const svalue *rhs) override
822 {
823 m_inner->on_condition (lhs, op, rhs);
824 }
825
826 void on_bounded_ranges (const svalue &sval,
827 const bounded_ranges &ranges) override
828 {
829 m_inner->on_bounded_ranges (sval, ranges);
830 }
831
832 void on_pop_frame (const frame_region *frame_reg) override
833 {
834 m_inner->on_pop_frame (frame_reg);
835 }
836
837 void on_unknown_change (const svalue *sval, bool is_mutable) override
838 {
839 m_inner->on_unknown_change (sval, is_mutable);
840 }
841
842 void on_phi (const gphi *phi, tree rhs) override
843 {
844 m_inner->on_phi (phi, rhs);
845 }
846
847 void on_unexpected_tree_code (tree t,
848 const dump_location_t &loc) override
849 {
850 m_inner->on_unexpected_tree_code (t, loc);
851 }
852
853 void on_escaped_function (tree fndecl) override
854 {
855 m_inner->on_escaped_function (fndecl);
856 }
857
858 uncertainty_t *get_uncertainty () override
859 {
860 return m_inner->get_uncertainty ();
861 }
862
863 void purge_state_involving (const svalue *sval) override
864 {
865 m_inner->purge_state_involving (sval);
866 }
867
868 void bifurcate (std::unique_ptr<custom_edge_info> info) override
869 {
870 m_inner->bifurcate (std::move (info));
871 }
872
873 void terminate_path () override
874 {
875 m_inner->terminate_path ();
876 }
877
878 const extrinsic_state *get_ext_state () const override
879 {
880 return m_inner->get_ext_state ();
881 }
882
883 bool get_state_map_by_name (const char *name,
884 sm_state_map **out_smap,
885 const state_machine **out_sm,
886 unsigned *out_sm_idx,
887 std::unique_ptr<sm_context> *out_sm_context)
888 override
889 {
890 return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx,
891 out_sm_context);
892 }
893
894 const gimple *get_stmt () const override
895 {
896 return m_inner->get_stmt ();
897 }
898
899 protected:
900 region_model_context_decorator (region_model_context *inner)
901 : m_inner (inner)
902 {
903 gcc_assert (m_inner);
904 }
905
906 region_model_context *m_inner;
907 };
908
909 /* Subclass of region_model_context_decorator that adds a note
910 when saving diagnostics. */
911
912 class note_adding_context : public region_model_context_decorator
913 {
914 public:
915 bool warn (std::unique_ptr<pending_diagnostic> d) override
916 {
917 if (m_inner->warn (std::move (d)))
918 {
919 add_note (make_note ());
920 return true;
921 }
922 else
923 return false;
924 }
925
926 /* Hook to make the new note. */
927 virtual std::unique_ptr<pending_note> make_note () = 0;
928
929 protected:
930 note_adding_context (region_model_context *inner)
931 : region_model_context_decorator (inner)
932 {
933 }
934 };
935
936 /* A bundle of data for use when attempting to merge two region_model
937 instances to make a third. */
938
939 struct model_merger
940 {
941 model_merger (const region_model *model_a,
942 const region_model *model_b,
943 const program_point &point,
944 region_model *merged_model,
945 const extrinsic_state *ext_state,
946 const program_state *state_a,
947 const program_state *state_b)
948 : m_model_a (model_a), m_model_b (model_b),
949 m_point (point),
950 m_merged_model (merged_model),
951 m_ext_state (ext_state),
952 m_state_a (state_a), m_state_b (state_b)
953 {
954 }
955
956 void dump_to_pp (pretty_printer *pp, bool simple) const;
957 void dump (FILE *fp, bool simple) const;
958 void dump (bool simple) const;
959
960 region_model_manager *get_manager () const
961 {
962 return m_model_a->get_manager ();
963 }
964
965 bool mergeable_svalue_p (const svalue *) const;
966 const function_point &get_function_point () const
967 {
968 return m_point.get_function_point ();
969 }
970
971 const region_model *m_model_a;
972 const region_model *m_model_b;
973 const program_point &m_point;
974 region_model *m_merged_model;
975
976 const extrinsic_state *m_ext_state;
977 const program_state *m_state_a;
978 const program_state *m_state_b;
979 };
980
981 /* A record that can (optionally) be written out when
982 region_model::add_constraint fails. */
983
984 class rejected_constraint
985 {
986 public:
987 virtual ~rejected_constraint () {}
988 virtual void dump_to_pp (pretty_printer *pp) const = 0;
989
990 const region_model &get_model () const { return m_model; }
991
992 protected:
993 rejected_constraint (const region_model &model)
994 : m_model (model)
995 {}
996
997 region_model m_model;
998 };
999
1000 class rejected_op_constraint : public rejected_constraint
1001 {
1002 public:
1003 rejected_op_constraint (const region_model &model,
1004 tree lhs, enum tree_code op, tree rhs)
1005 : rejected_constraint (model),
1006 m_lhs (lhs), m_op (op), m_rhs (rhs)
1007 {}
1008
1009 void dump_to_pp (pretty_printer *pp) const final override;
1010
1011 tree m_lhs;
1012 enum tree_code m_op;
1013 tree m_rhs;
1014 };
1015
1016 class rejected_default_case : public rejected_constraint
1017 {
1018 public:
1019 rejected_default_case (const region_model &model)
1020 : rejected_constraint (model)
1021 {}
1022
1023 void dump_to_pp (pretty_printer *pp) const final override;
1024 };
1025
1026 class rejected_ranges_constraint : public rejected_constraint
1027 {
1028 public:
1029 rejected_ranges_constraint (const region_model &model,
1030 tree expr, const bounded_ranges *ranges)
1031 : rejected_constraint (model),
1032 m_expr (expr), m_ranges (ranges)
1033 {}
1034
1035 void dump_to_pp (pretty_printer *pp) const final override;
1036
1037 private:
1038 tree m_expr;
1039 const bounded_ranges *m_ranges;
1040 };
1041
1042 /* A bundle of state. */
1043
1044 class engine
1045 {
1046 public:
1047 engine (const supergraph *sg = NULL, logger *logger = NULL);
1048 const supergraph *get_supergraph () { return m_sg; }
1049 region_model_manager *get_model_manager () { return &m_mgr; }
1050 known_function_manager *get_known_function_manager ()
1051 {
1052 return m_mgr.get_known_function_manager ();
1053 }
1054
1055 void log_stats (logger *logger) const;
1056
1057 private:
1058 const supergraph *m_sg;
1059 region_model_manager m_mgr;
1060 };
1061
1062 } // namespace ana
1063
1064 extern void debug (const region_model &rmodel);
1065
1066 namespace ana {
1067
1068 #if CHECKING_P
1069
1070 namespace selftest {
1071
1072 using namespace ::selftest;
1073
1074 /* An implementation of region_model_context for use in selftests, which
1075 stores any pending_diagnostic instances passed to it. */
1076
1077 class test_region_model_context : public noop_region_model_context
1078 {
1079 public:
1080 bool warn (std::unique_ptr<pending_diagnostic> d) final override
1081 {
1082 m_diagnostics.safe_push (d.release ());
1083 return true;
1084 }
1085
1086 unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1087
1088 void on_unexpected_tree_code (tree t, const dump_location_t &)
1089 final override
1090 {
1091 internal_error ("unhandled tree code: %qs",
1092 get_tree_code_name (TREE_CODE (t)));
1093 }
1094
1095 private:
1096 /* Implicitly delete any diagnostics in the dtor. */
1097 auto_delete_vec<pending_diagnostic> m_diagnostics;
1098 };
1099
1100 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1101 Verify that MODEL remains satisfiable. */
1102
1103 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1104 SELFTEST_BEGIN_STMT \
1105 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1106 ASSERT_TRUE (sat); \
1107 SELFTEST_END_STMT
1108
1109 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1110 Verify that the result is not satisfiable. */
1111
1112 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1113 SELFTEST_BEGIN_STMT \
1114 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1115 ASSERT_FALSE (sat); \
1116 SELFTEST_END_STMT
1117
1118 /* Implementation detail of the ASSERT_CONDITION_* macros. */
1119
1120 void assert_condition (const location &loc,
1121 region_model &model,
1122 const svalue *lhs, tree_code op, const svalue *rhs,
1123 tristate expected);
1124
1125 void assert_condition (const location &loc,
1126 region_model &model,
1127 tree lhs, tree_code op, tree rhs,
1128 tristate expected);
1129
1130 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1131 as "true". */
1132
1133 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1134 SELFTEST_BEGIN_STMT \
1135 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1136 tristate (tristate::TS_TRUE)); \
1137 SELFTEST_END_STMT
1138
1139 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1140 as "false". */
1141
1142 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1143 SELFTEST_BEGIN_STMT \
1144 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1145 tristate (tristate::TS_FALSE)); \
1146 SELFTEST_END_STMT
1147
1148 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1149 as "unknown". */
1150
1151 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1152 SELFTEST_BEGIN_STMT \
1153 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1154 tristate (tristate::TS_UNKNOWN)); \
1155 SELFTEST_END_STMT
1156
1157 } /* end of namespace selftest. */
1158
1159 #endif /* #if CHECKING_P */
1160
1161 } // namespace ana
1162
1163 #endif /* GCC_ANALYZER_REGION_MODEL_H */