xref: /netbsd-src/external/gpl3/gcc/dist/gcc/analyzer/region-model.h (revision b1e838363e3c6fc78a55519254d99869742dd33c)
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