1 /* Classes for modeling the state of memory.
2 Copyright (C) 2019-2020 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 /* A tree, extended with stack frame information for locals, so that
30 we can distinguish between different values of locals within a potentially
31 recursive callstack. */
32 // TODO: would this be better as a new tree code?
33
34 using namespace ana;
35
36 namespace ana {
37
38 class path_var
39 {
40 public:
path_var(tree t,int stack_depth)41 path_var (tree t, int stack_depth)
42 : m_tree (t), m_stack_depth (stack_depth)
43 {
44 // TODO: ignore stack depth for globals and constants
45 }
46
47 bool operator== (const path_var &other) const
48 {
49 return (m_tree == other.m_tree
50 && m_stack_depth == other.m_stack_depth);
51 }
52
53 void dump (pretty_printer *pp) const;
54
55 tree m_tree;
56 int m_stack_depth; // or -1 for globals?
57 };
58
59 } // namespace ana
60
61 namespace inchash
62 {
63 extern void add_path_var (path_var pv, hash &hstate);
64 } // namespace inchash
65
66
67 namespace ana {
68
69 /* A region_model is effectively a graph of regions and symbolic values.
70 We store per-model IDs rather than pointers to make it easier to clone
71 and to compare graphs. */
72
73 /* An ID for an svalue within a region_model. Internally, this is an index
74 into a vector of svalue * within the region_model. */
75
76 class svalue_id
77 {
78 public:
null()79 static svalue_id null () { return svalue_id (-1); }
80
svalue_id()81 svalue_id () : m_idx (-1) {}
82
83 bool operator== (const svalue_id &other) const
84 {
85 return m_idx == other.m_idx;
86 }
87
88 bool operator!= (const svalue_id &other) const
89 {
90 return m_idx != other.m_idx;
91 }
92
null_p()93 bool null_p () const { return m_idx == -1; }
94
from_int(int idx)95 static svalue_id from_int (int idx) { return svalue_id (idx); }
as_int()96 int as_int () const { return m_idx; }
97
98 void print (pretty_printer *pp) const;
99 void dump_node_name_to_pp (pretty_printer *pp) const;
100
101 void validate (const region_model &model) const;
102
103 private:
svalue_id(int idx)104 svalue_id (int idx) : m_idx (idx) {}
105
106 int m_idx;
107 };
108
109 /* An ID for a region within a region_model. Internally, this is an index
110 into a vector of region * within the region_model. */
111
112 class region_id
113 {
114 public:
null()115 static region_id null () { return region_id (-1); }
116
region_id()117 region_id () : m_idx (-1) {}
118
119 bool operator== (const region_id &other) const
120 {
121 return m_idx == other.m_idx;
122 }
123
124 bool operator!= (const region_id &other) const
125 {
126 return m_idx != other.m_idx;
127 }
128
null_p()129 bool null_p () const { return m_idx == -1; }
130
from_int(int idx)131 static region_id from_int (int idx) { return region_id (idx); }
as_int()132 int as_int () const { return m_idx; }
133
134 void print (pretty_printer *pp) const;
135 void dump_node_name_to_pp (pretty_printer *pp) const;
136
137 void validate (const region_model &model) const;
138
139 private:
region_id(int idx)140 region_id (int idx) : m_idx (idx) {}
141
142 int m_idx;
143 };
144
145 /* A class for renumbering IDs within a region_model, mapping old IDs
146 to new IDs (e.g. when removing one or more elements, thus needing to
147 renumber). */
148 // TODO: could this be useful for equiv_class_ids?
149
150 template <typename T>
151 class id_map
152 {
153 public:
154 id_map (int num_ids);
155 void put (T src, T dst);
156 T get_dst_for_src (T src) const;
157 T get_src_for_dst (T dst) const;
158 void dump_to_pp (pretty_printer *pp) const;
159 void dump () const;
160 void update (T *) const;
161
162 private:
163 auto_vec<T> m_src_to_dst;
164 auto_vec<T> m_dst_to_src;
165 };
166
167 typedef id_map<svalue_id> svalue_id_map;
168 typedef id_map<region_id> region_id_map;
169
170 /* class id_map. */
171
172 /* id_map's ctor, which populates the map with dummy null values. */
173
174 template <typename T>
id_map(int num_svalues)175 inline id_map<T>::id_map (int num_svalues)
176 : m_src_to_dst (num_svalues),
177 m_dst_to_src (num_svalues)
178 {
179 for (int i = 0; i < num_svalues; i++)
180 {
181 m_src_to_dst.quick_push (T::null ());
182 m_dst_to_src.quick_push (T::null ());
183 }
184 }
185
186 /* Record that SRC is to be mapped to DST. */
187
188 template <typename T>
189 inline void
put(T src,T dst)190 id_map<T>::put (T src, T dst)
191 {
192 m_src_to_dst[src.as_int ()] = dst;
193 m_dst_to_src[dst.as_int ()] = src;
194 }
195
196 /* Get the new value for SRC within the map. */
197
198 template <typename T>
199 inline T
get_dst_for_src(T src)200 id_map<T>::get_dst_for_src (T src) const
201 {
202 if (src.null_p ())
203 return src;
204 return m_src_to_dst[src.as_int ()];
205 }
206
207 /* Given DST, a new value, determine which old value will be mapped to it
208 (the inverse of the map). */
209
210 template <typename T>
211 inline T
get_src_for_dst(T dst)212 id_map<T>::get_src_for_dst (T dst) const
213 {
214 if (dst.null_p ())
215 return dst;
216 return m_dst_to_src[dst.as_int ()];
217 }
218
219 /* Dump this id_map to PP. */
220
221 template <typename T>
222 inline void
dump_to_pp(pretty_printer * pp)223 id_map<T>::dump_to_pp (pretty_printer *pp) const
224 {
225 pp_string (pp, "src to dst: {");
226 unsigned i;
227 T *dst;
228 FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
229 {
230 if (i > 0)
231 pp_string (pp, ", ");
232 T src (T::from_int (i));
233 src.print (pp);
234 pp_string (pp, " -> ");
235 dst->print (pp);
236 }
237 pp_string (pp, "}");
238 pp_newline (pp);
239
240 pp_string (pp, "dst to src: {");
241 T *src;
242 FOR_EACH_VEC_ELT (m_dst_to_src, i, src)
243 {
244 if (i > 0)
245 pp_string (pp, ", ");
246 T dst (T::from_int (i));
247 dst.print (pp);
248 pp_string (pp, " <- ");
249 src->print (pp);
250 }
251 pp_string (pp, "}");
252 pp_newline (pp);
253 }
254
255 /* Dump this id_map to stderr. */
256
257 template <typename T>
258 DEBUG_FUNCTION inline void
dump()259 id_map<T>::dump () const
260 {
261 pretty_printer pp;
262 pp.buffer->stream = stderr;
263 dump_to_pp (&pp);
264 pp_flush (&pp);
265 }
266
267 /* Update *ID from the old value to its new value in this map. */
268
269 template <typename T>
270 inline void
update(T * id)271 id_map<T>::update (T *id) const
272 {
273 *id = get_dst_for_src (*id);
274 }
275
276 /* Variant of the above, which only stores things in one direction.
277 (e.g. for merging, when the number of destination regions is not
278 the same of the src regions, and can grow). */
279
280 template <typename T>
281 class one_way_id_map
282 {
283 public:
284 one_way_id_map (int num_ids);
285 void put (T src, T dst);
286 T get_dst_for_src (T src) const;
287 void dump_to_pp (pretty_printer *pp) const;
288 void dump () const;
289 void update (T *) const;
290
291 private:
292 auto_vec<T> m_src_to_dst;
293 };
294
295 typedef one_way_id_map<svalue_id> one_way_svalue_id_map;
296 typedef one_way_id_map<region_id> one_way_region_id_map;
297
298 /* class one_way_id_map. */
299
300 /* one_way_id_map's ctor, which populates the map with dummy null values. */
301
302 template <typename T>
one_way_id_map(int num_svalues)303 inline one_way_id_map<T>::one_way_id_map (int num_svalues)
304 : m_src_to_dst (num_svalues)
305 {
306 for (int i = 0; i < num_svalues; i++)
307 m_src_to_dst.quick_push (T::null ());
308 }
309
310 /* Record that SRC is to be mapped to DST. */
311
312 template <typename T>
313 inline void
put(T src,T dst)314 one_way_id_map<T>::put (T src, T dst)
315 {
316 m_src_to_dst[src.as_int ()] = dst;
317 }
318
319 /* Get the new value for SRC within the map. */
320
321 template <typename T>
322 inline T
get_dst_for_src(T src)323 one_way_id_map<T>::get_dst_for_src (T src) const
324 {
325 if (src.null_p ())
326 return src;
327 return m_src_to_dst[src.as_int ()];
328 }
329
330 /* Dump this map to PP. */
331
332 template <typename T>
333 inline void
dump_to_pp(pretty_printer * pp)334 one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
335 {
336 pp_string (pp, "src to dst: {");
337 unsigned i;
338 T *dst;
339 FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
340 {
341 if (i > 0)
342 pp_string (pp, ", ");
343 T src (T::from_int (i));
344 src.print (pp);
345 pp_string (pp, " -> ");
346 dst->print (pp);
347 }
348 pp_string (pp, "}");
349 pp_newline (pp);
350 }
351
352 /* Dump this map to stderr. */
353
354 template <typename T>
355 DEBUG_FUNCTION inline void
dump()356 one_way_id_map<T>::dump () const
357 {
358 pretty_printer pp;
359 pp.buffer->stream = stderr;
360 dump_to_pp (&pp);
361 pp_flush (&pp);
362 }
363
364 /* Update *ID from the old value to its new value in this map. */
365
366 template <typename T>
367 inline void
update(T * id)368 one_way_id_map<T>::update (T *id) const
369 {
370 *id = get_dst_for_src (*id);
371 }
372
373 /* A set of region_ids within a region_model. */
374
375 class region_id_set
376 {
377 public:
378 region_id_set (const region_model *model);
379
add_region(region_id rid)380 void add_region (region_id rid)
381 {
382 if (!rid.null_p ())
383 bitmap_set_bit (m_bitmap, rid.as_int ());
384 }
385
region_p(region_id rid)386 bool region_p (region_id rid) const
387 {
388 gcc_assert (!rid.null_p ());
389 return bitmap_bit_p (const_cast <auto_sbitmap &> (m_bitmap),
390 rid.as_int ());
391 }
392
num_regions()393 unsigned int num_regions ()
394 {
395 return bitmap_count_bits (m_bitmap);
396 }
397
398 private:
399 auto_sbitmap m_bitmap;
400 };
401
402 /* A set of svalue_ids within a region_model. */
403
404 class svalue_id_set
405 {
406 public:
407 svalue_id_set ();
408
add_svalue(svalue_id sid)409 void add_svalue (svalue_id sid)
410 {
411 if (!sid.null_p ())
412 bitmap_set_bit (m_bitmap, sid.as_int ());
413 }
414
svalue_p(svalue_id sid)415 bool svalue_p (svalue_id sid) const
416 {
417 gcc_assert (!sid.null_p ());
418 return bitmap_bit_p (const_cast <auto_bitmap &> (m_bitmap),
419 sid.as_int ());
420 }
421
422 private:
423 auto_bitmap m_bitmap;
424 };
425
426 /* Various operations delete information from a region_model.
427
428 This struct tracks how many of each kind of entity were purged (e.g.
429 for selftests, and for debugging). */
430
431 struct purge_stats
432 {
purge_statspurge_stats433 purge_stats ()
434 : m_num_svalues (0),
435 m_num_regions (0),
436 m_num_equiv_classes (0),
437 m_num_constraints (0),
438 m_num_client_items (0)
439 {}
440
441 int m_num_svalues;
442 int m_num_regions;
443 int m_num_equiv_classes;
444 int m_num_constraints;
445 int m_num_client_items;
446 };
447
448 /* An enum for discriminating between the different concrete subclasses
449 of svalue. */
450
451 enum svalue_kind
452 {
453 SK_REGION,
454 SK_CONSTANT,
455 SK_UNKNOWN,
456 SK_POISONED,
457 SK_SETJMP
458 };
459
460 /* svalue and its subclasses.
461
462 The class hierarchy looks like this (using indentation to show
463 inheritance, and with svalue_kinds shown for the concrete subclasses):
464
465 svalue
466 region_svalue (SK_REGION)
467 constant_svalue (SK_CONSTANT)
468 unknown_svalue (SK_UNKNOWN)
469 poisoned_svalue (SK_POISONED)
470 setjmp_svalue (SK_SETJMP). */
471
472 /* An abstract base class representing a value held by a region of memory. */
473
474 class svalue
475 {
476 public:
~svalue()477 virtual ~svalue () {}
478
479 bool operator== (const svalue &other) const;
480 bool operator!= (const svalue &other) const { return !(*this == other); }
481
482 virtual svalue *clone () const = 0;
483
get_type()484 tree get_type () const { return m_type; }
485
486 virtual enum svalue_kind get_kind () const = 0;
487
488 hashval_t hash () const;
489
490 void print (const region_model &model,
491 svalue_id this_sid,
492 pretty_printer *pp) const;
493
494 virtual void dump_dot_to_pp (const region_model &model,
495 svalue_id this_sid,
496 pretty_printer *pp) const;
497
dyn_cast_region_svalue()498 virtual region_svalue *dyn_cast_region_svalue () { return NULL; }
dyn_cast_constant_svalue()499 virtual constant_svalue *dyn_cast_constant_svalue () { return NULL; }
dyn_cast_constant_svalue()500 virtual const constant_svalue *dyn_cast_constant_svalue () const
501 { return NULL; }
dyn_cast_poisoned_svalue()502 virtual poisoned_svalue *dyn_cast_poisoned_svalue () { return NULL; }
dyn_cast_unknown_svalue()503 virtual unknown_svalue *dyn_cast_unknown_svalue () { return NULL; }
dyn_cast_setjmp_svalue()504 virtual setjmp_svalue *dyn_cast_setjmp_svalue () { return NULL; }
505
506 virtual void remap_region_ids (const region_id_map &map);
507
508 virtual void walk_for_canonicalization (canonicalization *c) const;
509
510 virtual svalue_id get_child_sid (region *parent, region *child,
511 region_model &model,
512 region_model_context *ctxt);
513
514 tree maybe_get_constant () const;
515
516 protected:
svalue(tree type)517 svalue (tree type) : m_type (type) {}
518
519 virtual void add_to_hash (inchash::hash &hstate) const = 0;
520
521 private:
522 virtual void print_details (const region_model &model,
523 svalue_id this_sid,
524 pretty_printer *pp) const = 0;
525 tree m_type;
526 };
527
528 /* Concrete subclass of svalue representing a pointer value that points to
529 a known region */
530
531 class region_svalue : public svalue
532 {
533 public:
region_svalue(tree type,region_id rid)534 region_svalue (tree type, region_id rid) : svalue (type), m_rid (rid)
535 {
536 /* Should we support NULL ptrs here? */
537 gcc_assert (!rid.null_p ());
538 }
539
540 bool compare_fields (const region_svalue &other) const;
541
clone()542 svalue *clone () const FINAL OVERRIDE
543 { return new region_svalue (get_type (), m_rid); }
544
get_kind()545 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_REGION; }
546
547 void dump_dot_to_pp (const region_model &model,
548 svalue_id this_sid,
549 pretty_printer *pp) const
550 FINAL OVERRIDE;
551
dyn_cast_region_svalue()552 region_svalue *dyn_cast_region_svalue () FINAL OVERRIDE { return this; }
553
get_pointee()554 region_id get_pointee () const { return m_rid; }
555
556 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
557
558 static void merge_values (const region_svalue ®ion_sval_a,
559 const region_svalue ®ion_sval_b,
560 svalue_id *merged_sid,
561 tree type,
562 model_merger *merger);
563
564 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
565
566 static tristate eval_condition (region_svalue *lhs_ptr,
567 enum tree_code op,
568 region_svalue *rhs_ptr);
569
570 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
571
572 private:
573 void print_details (const region_model &model,
574 svalue_id this_sid,
575 pretty_printer *pp) const
576 FINAL OVERRIDE;
577
578 region_id m_rid;
579 };
580
581 } // namespace ana
582
583 template <>
584 template <>
585 inline bool
test(svalue * sval)586 is_a_helper <region_svalue *>::test (svalue *sval)
587 {
588 return sval->get_kind () == SK_REGION;
589 }
590
591 namespace ana {
592
593 /* Concrete subclass of svalue representing a specific constant value. */
594
595 class constant_svalue : public svalue
596 {
597 public:
constant_svalue(tree cst_expr)598 constant_svalue (tree cst_expr)
599 : svalue (TREE_TYPE (cst_expr)), m_cst_expr (cst_expr)
600 {
601 gcc_assert (cst_expr);
602 gcc_assert (CONSTANT_CLASS_P (cst_expr));
603 }
604
605 bool compare_fields (const constant_svalue &other) const;
606
clone()607 svalue *clone () const FINAL OVERRIDE
608 { return new constant_svalue (m_cst_expr); }
609
get_kind()610 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_CONSTANT; }
611
612 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
613
dyn_cast_constant_svalue()614 constant_svalue *dyn_cast_constant_svalue () FINAL OVERRIDE { return this; }
dyn_cast_constant_svalue()615 const constant_svalue *dyn_cast_constant_svalue () const FINAL OVERRIDE
616 { return this; }
617
get_constant()618 tree get_constant () const { return m_cst_expr; }
619
620 static void merge_values (const constant_svalue &cst_sval_a,
621 const constant_svalue &cst_sval_b,
622 svalue_id *merged_sid,
623 model_merger *merger);
624
625 static tristate eval_condition (constant_svalue *lhs,
626 enum tree_code op,
627 constant_svalue *rhs);
628
629 svalue_id get_child_sid (region *parent, region *child,
630 region_model &model,
631 region_model_context *ctxt) FINAL OVERRIDE;
632
633 private:
634 void print_details (const region_model &model,
635 svalue_id this_sid,
636 pretty_printer *pp) const
637 FINAL OVERRIDE;
638
639 tree m_cst_expr;
640 };
641
642 } // namespace ana
643
644 template <>
645 template <>
646 inline bool
test(svalue * sval)647 is_a_helper <constant_svalue *>::test (svalue *sval)
648 {
649 return sval->get_kind () == SK_CONSTANT;
650 }
651
652 namespace ana {
653
654 /* Concrete subclass of svalue representing a unique but unknown value.
655 Comparisons of variables that share the same unknown value are known
656 to be equal, even if we don't know what the value is. */
657
658 class unknown_svalue : public svalue
659 {
660 public:
unknown_svalue(tree type)661 unknown_svalue (tree type)
662 : svalue (type)
663 {}
664
665 bool compare_fields (const unknown_svalue &other) const;
666
clone()667 svalue *clone () const FINAL OVERRIDE
668 { return new unknown_svalue (get_type ()); }
669
get_kind()670 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_UNKNOWN; }
671
672 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
673
dyn_cast_unknown_svalue()674 unknown_svalue *dyn_cast_unknown_svalue () FINAL OVERRIDE { return this; }
675
676 private:
677 void print_details (const region_model &model,
678 svalue_id this_sid,
679 pretty_printer *pp) const
680 FINAL OVERRIDE;
681 };
682
683 /* An enum describing a particular kind of "poisoned" value. */
684
685 enum poison_kind
686 {
687 /* For use to describe freed memory. */
688 POISON_KIND_FREED,
689
690 /* For use on pointers to regions within popped stack frames. */
691 POISON_KIND_POPPED_STACK
692 };
693
694 extern const char *poison_kind_to_str (enum poison_kind);
695
696 /* Concrete subclass of svalue representing a value that should not
697 be used (e.g. uninitialized memory, freed memory). */
698
699 class poisoned_svalue : public svalue
700 {
701 public:
poisoned_svalue(enum poison_kind kind,tree type)702 poisoned_svalue (enum poison_kind kind, tree type)
703 : svalue (type), m_kind (kind) {}
704
705 bool compare_fields (const poisoned_svalue &other) const;
706
clone()707 svalue *clone () const FINAL OVERRIDE
708 { return new poisoned_svalue (m_kind, get_type ()); }
709
get_kind()710 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_POISONED; }
711
712 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
713
dyn_cast_poisoned_svalue()714 poisoned_svalue *dyn_cast_poisoned_svalue () FINAL OVERRIDE { return this; }
715
get_poison_kind()716 enum poison_kind get_poison_kind () const { return m_kind; }
717
718 private:
719 void print_details (const region_model &model,
720 svalue_id this_sid,
721 pretty_printer *pp) const
722 FINAL OVERRIDE;
723
724 enum poison_kind m_kind;
725 };
726
727 } // namespace ana
728
729 template <>
730 template <>
731 inline bool
test(svalue * sval)732 is_a_helper <poisoned_svalue *>::test (svalue *sval)
733 {
734 return sval->get_kind () == SK_POISONED;
735 }
736
737 namespace ana {
738
739 /* A bundle of information recording a setjmp/sigsetjmp call, corresponding
740 roughly to a jmp_buf. */
741
742 struct setjmp_record
743 {
setjmp_recordsetjmp_record744 setjmp_record (const exploded_node *enode,
745 const gcall *setjmp_call)
746 : m_enode (enode), m_setjmp_call (setjmp_call)
747 {
748 }
749
750 bool operator== (const setjmp_record &other) const
751 {
752 return (m_enode == other.m_enode
753 && m_setjmp_call == other.m_setjmp_call);
754 }
755
756 const exploded_node *m_enode;
757 const gcall *m_setjmp_call;
758 };
759
760 /* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp,
761 so that longjmp/siglongjmp can potentially "return" to an entirely
762 different function. */
763
764 class setjmp_svalue : public svalue
765 {
766 public:
setjmp_svalue(const setjmp_record & setjmp_record,tree type)767 setjmp_svalue (const setjmp_record &setjmp_record,
768 tree type)
769 : svalue (type), m_setjmp_record (setjmp_record)
770 {}
771
772 bool compare_fields (const setjmp_svalue &other) const;
773
clone()774 svalue *clone () const FINAL OVERRIDE
775 { return new setjmp_svalue (m_setjmp_record, get_type ()); }
776
get_kind()777 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_SETJMP; }
778
779 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
780
dyn_cast_setjmp_svalue()781 setjmp_svalue *dyn_cast_setjmp_svalue () FINAL OVERRIDE { return this; }
782
783 int get_enode_index () const;
784
get_setjmp_record()785 const setjmp_record &get_setjmp_record () const { return m_setjmp_record; }
786
787 private:
788 void print_details (const region_model &model,
789 svalue_id this_sid,
790 pretty_printer *pp) const
791 FINAL OVERRIDE;
792
793 setjmp_record m_setjmp_record;
794 };
795
796 /* An enum for discriminating between the different concrete subclasses
797 of region. */
798
799 enum region_kind
800 {
801 RK_PRIMITIVE,
802 RK_STRUCT,
803 RK_UNION,
804 RK_FRAME,
805 RK_GLOBALS,
806 RK_CODE,
807 RK_FUNCTION,
808 RK_ARRAY,
809 RK_STACK,
810 RK_HEAP,
811 RK_ROOT,
812 RK_SYMBOLIC
813 };
814
815 extern const char *region_kind_to_str (enum region_kind);
816
817 /* Region and its subclasses.
818
819 The class hierarchy looks like this (using indentation to show
820 inheritance, and with region_kinds shown for the concrete subclasses):
821
822 region
823 primitive_region (RK_PRIMITIVE)
824 map_region
825 struct_or_union_region
826 struct_region (RK_STRUCT)
827 union_region (RK_UNION)
828 scope_region
829 frame_region (RK_FRAME)
830 globals_region (RK_GLOBALS)
831 code_region (RK_CODE)
832 function_region (RK_FUNCTION)
833 array_region (RK_ARRAY)
834 stack_region (RK_STACK)
835 heap_region (RK_HEAP)
836 root_region (RK_ROOT)
837 label_region (RK_FUNCTION)
838 symbolic_region (RK_SYMBOLIC). */
839
840 /* Abstract base class representing a chunk of memory.
841
842 Regions form a tree-like hierarchy, with a root region at the base,
843 with memory space regions within it, representing the stack and
844 globals, with frames within the stack, and regions for variables
845 within the frames and the "globals" region. Regions for structs
846 can have subregions for fields.
847
848 A region can optionally have a value, or inherit its value from
849 the first ancestor with a value. For example, the stack region
850 has a "uninitialized" poison value which is inherited by all
851 descendent regions that don't themselves have a value. */
852
853 class region
854 {
855 public:
~region()856 virtual ~region () {}
857
858 bool operator== (const region &other) const;
859 bool operator!= (const region &other) const { return !(*this == other); }
860
861 virtual region *clone () const = 0;
862
863 virtual enum region_kind get_kind () const = 0;
dyn_cast_map_region()864 virtual map_region *dyn_cast_map_region () { return NULL; }
dyn_cast_array_region()865 virtual array_region *dyn_cast_array_region () { return NULL; }
dyn_cast_symbolic_region()866 virtual symbolic_region *dyn_cast_symbolic_region () { return NULL; }
dyn_cast_symbolic_region()867 virtual const symbolic_region *dyn_cast_symbolic_region () const { return NULL; }
868
get_parent()869 region_id get_parent () const { return m_parent_rid; }
870 region *get_parent_region (const region_model &model) const;
871
872 void set_value (region_model &model, region_id this_rid, svalue_id rhs_sid,
873 region_model_context *ctxt);
874 svalue_id get_value (region_model &model, bool non_null,
875 region_model_context *ctxt);
get_value_direct()876 svalue_id get_value_direct () const { return m_sval_id; }
877
878 svalue_id get_inherited_child_sid (region *child,
879 region_model &model,
880 region_model_context *ctxt);
881
get_type()882 tree get_type () const { return m_type; }
883
884 hashval_t hash () const;
885
886 void print (const region_model &model,
887 region_id this_rid,
888 pretty_printer *pp) const;
889
890 virtual void dump_dot_to_pp (const region_model &model,
891 region_id this_rid,
892 pretty_printer *pp) const;
893
894 void dump_to_pp (const region_model &model,
895 region_id this_rid,
896 pretty_printer *pp,
897 const char *prefix,
898 bool is_last_child) const;
899 virtual void dump_child_label (const region_model &model,
900 region_id this_rid,
901 region_id child_rid,
902 pretty_printer *pp) const;
903
904 void remap_svalue_ids (const svalue_id_map &map);
905 virtual void remap_region_ids (const region_id_map &map);
906
907 virtual void walk_for_canonicalization (canonicalization *c) const = 0;
908
909 void add_view (region_id view_rid, region_model *model);
910 region_id get_view (tree type, region_model *model) const;
get_active_view()911 region_id get_active_view () const { return m_active_view_rid; }
is_view_p()912 bool is_view_p () const { return m_is_view; }
913
914 virtual void validate (const region_model &model) const;
915
916 bool non_null_p (const region_model &model) const;
917
918 protected:
919 region (region_id parent_rid, svalue_id sval_id, tree type);
920 region (const region &other);
921
922 virtual void add_to_hash (inchash::hash &hstate) const;
923 virtual void print_fields (const region_model &model,
924 region_id this_rid,
925 pretty_printer *pp) const;
926
927 private:
928 void become_active_view (region_model &model, region_id this_rid);
929 void deactivate_any_active_view (region_model &model);
930 void deactivate_view (region_model &model, region_id this_view_rid);
931
932 region_id m_parent_rid;
933 svalue_id m_sval_id;
934 tree m_type;
935 /* Child regions that are "views" (one per type). */
936 auto_vec<region_id> m_view_rids;
937
938 bool m_is_view;
939 region_id m_active_view_rid;
940 };
941
942 } // namespace ana
943
944 template <>
945 template <>
946 inline bool
test(region *)947 is_a_helper <region *>::test (region *)
948 {
949 return true;
950 }
951
952 namespace ana {
953
954 /* Concrete region subclass for storing "primitive" types (integral types,
955 pointers, etc). */
956
957 class primitive_region : public region
958 {
959 public:
primitive_region(region_id parent_rid,tree type)960 primitive_region (region_id parent_rid, tree type)
961 : region (parent_rid, svalue_id::null (), type)
962 {}
963
964 region *clone () const FINAL OVERRIDE;
965
get_kind()966 enum region_kind get_kind () const FINAL OVERRIDE { return RK_PRIMITIVE; }
967
968 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
969 };
970
971 /* A region that has children identified by tree keys.
972 For example a stack frame has subregions per local, and a region
973 for a struct has subregions per field. */
974
975 class map_region : public region
976 {
977 public:
978 typedef ordered_hash_map<tree, region_id> map_t;
979 typedef map_t::iterator iterator_t;
980
map_region(region_id parent_rid,tree type)981 map_region (region_id parent_rid, tree type)
982 : region (parent_rid, svalue_id::null (), type)
983 {}
984 map_region (const map_region &other);
985
dyn_cast_map_region()986 map_region *dyn_cast_map_region () FINAL OVERRIDE { return this; }
987
988 void dump_dot_to_pp (const region_model &model,
989 region_id this_rid,
990 pretty_printer *pp) const
991 FINAL OVERRIDE;
992
993 void dump_child_label (const region_model &model,
994 region_id this_rid,
995 region_id child_rid,
996 pretty_printer *pp) const
997 FINAL OVERRIDE;
998
999 region_id get_or_create (region_model *model,
1000 region_id this_rid,
1001 tree expr, tree type,
1002 region_model_context *ctxt);
1003 void unbind (tree expr);
1004 region_id *get (tree expr);
1005
1006 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
1007
1008 tree get_tree_for_child_region (region_id child_rid) const;
1009
1010 tree get_tree_for_child_region (region *child,
1011 const region_model &model) const;
1012
1013 static bool can_merge_p (const map_region *map_region_a,
1014 const map_region *map_region_b,
1015 map_region *merged_map_region,
1016 region_id merged_rid,
1017 model_merger *merger);
1018
1019 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
1020
1021 virtual bool valid_key_p (tree key) const = 0;
1022
1023 svalue_id get_value_by_name (tree identifier,
1024 const region_model &model) const;
1025
begin()1026 iterator_t begin () { return m_map.begin (); }
end()1027 iterator_t end () { return m_map.end (); }
elements()1028 size_t elements () const { return m_map.elements (); }
1029
1030 protected:
1031 bool compare_fields (const map_region &other) const;
1032 void add_to_hash (inchash::hash &hstate) const OVERRIDE;
1033 void print_fields (const region_model &model,
1034 region_id this_rid,
1035 pretty_printer *pp) const
1036 OVERRIDE;
1037 void validate (const region_model &model) const FINAL OVERRIDE;
1038
1039 private:
1040 /* Mapping from tree to child region. */
1041 map_t m_map;
1042 };
1043
1044 } // namespace ana
1045
1046 template <>
1047 template <>
1048 inline bool
test(region * reg)1049 is_a_helper <map_region *>::test (region *reg)
1050 {
1051 return (reg->dyn_cast_map_region () != NULL);
1052 }
1053
1054 namespace ana {
1055
1056 /* Abstract subclass representing a region with fields
1057 (either a struct or a union). */
1058
1059 class struct_or_union_region : public map_region
1060 {
1061 public:
1062 bool valid_key_p (tree key) const FINAL OVERRIDE;
1063
1064 protected:
struct_or_union_region(region_id parent_rid,tree type)1065 struct_or_union_region (region_id parent_rid, tree type)
1066 : map_region (parent_rid, type)
1067 {}
1068
1069 bool compare_fields (const struct_or_union_region &other) const;
1070 };
1071
1072 } // namespace ana
1073
1074 template <>
1075 template <>
1076 inline bool
test(region * reg)1077 is_a_helper <struct_or_union_region *>::test (region *reg)
1078 {
1079 return (reg->get_kind () == RK_STRUCT
1080 || reg->get_kind () == RK_UNION);
1081 }
1082
1083 namespace ana {
1084
1085 /* Concrete region subclass. A map_region representing a struct, using
1086 FIELD_DECLs for its keys. */
1087
1088 class struct_region : public struct_or_union_region
1089 {
1090 public:
struct_region(region_id parent_rid,tree type)1091 struct_region (region_id parent_rid, tree type)
1092 : struct_or_union_region (parent_rid, type)
1093 {
1094 gcc_assert (TREE_CODE (type) == RECORD_TYPE);
1095 }
1096
1097 region *clone () const FINAL OVERRIDE;
1098
get_kind()1099 enum region_kind get_kind () const FINAL OVERRIDE { return RK_STRUCT; }
1100
1101 bool compare_fields (const struct_region &other) const;
1102 };
1103
1104 } // namespace ana
1105
1106 template <>
1107 template <>
1108 inline bool
test(region * reg)1109 is_a_helper <struct_region *>::test (region *reg)
1110 {
1111 return reg->get_kind () == RK_STRUCT;
1112 }
1113
1114 namespace ana {
1115
1116 /* Concrete region subclass. A map_region representing a union, using
1117 FIELD_DECLs for its keys. */
1118
1119 class union_region : public struct_or_union_region
1120 {
1121 public:
union_region(region_id parent_rid,tree type)1122 union_region (region_id parent_rid, tree type)
1123 : struct_or_union_region (parent_rid, type)
1124 {
1125 gcc_assert (TREE_CODE (type) == UNION_TYPE);
1126 }
1127
1128 region *clone () const FINAL OVERRIDE;
1129
get_kind()1130 enum region_kind get_kind () const FINAL OVERRIDE { return RK_UNION; }
1131
1132 bool compare_fields (const union_region &other) const;
1133 };
1134
1135 } // namespace ana
1136
1137 template <>
1138 template <>
1139 inline bool
test(region * reg)1140 is_a_helper <union_region *>::test (region *reg)
1141 {
1142 return reg->get_kind () == RK_UNION;
1143 }
1144
1145 namespace ana {
1146
1147 /* Abstract map_region subclass for accessing decls, used as a base class
1148 for function frames and for the globals region. */
1149
1150 class scope_region : public map_region
1151 {
1152 public:
1153
1154 protected:
scope_region(region_id parent_rid)1155 scope_region (region_id parent_rid)
1156 : map_region (parent_rid, NULL_TREE)
1157 {}
1158
scope_region(const scope_region & other)1159 scope_region (const scope_region &other)
1160 : map_region (other)
1161 {
1162 }
1163
1164 bool compare_fields (const scope_region &other) const;
1165 };
1166
1167 /* Concrete region subclass, representing a function frame on the stack,
1168 to contain the locals. */
1169
1170 class frame_region : public scope_region
1171 {
1172 public:
frame_region(region_id parent_rid,function * fun,int depth)1173 frame_region (region_id parent_rid, function *fun, int depth)
1174 : scope_region (parent_rid), m_fun (fun), m_depth (depth)
1175 {}
1176
frame_region(const frame_region & other)1177 frame_region (const frame_region &other)
1178 : scope_region (other), m_fun (other.m_fun), m_depth (other.m_depth)
1179 {
1180 }
1181
1182 /* region vfuncs. */
1183 region *clone () const FINAL OVERRIDE;
get_kind()1184 enum region_kind get_kind () const FINAL OVERRIDE { return RK_FRAME; }
1185 void print_fields (const region_model &model,
1186 region_id this_rid,
1187 pretty_printer *pp) const
1188 FINAL OVERRIDE;
1189 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
1190
1191 /* map_region vfuncs. */
1192 bool valid_key_p (tree key) const FINAL OVERRIDE;
1193
1194 /* Accessors. */
get_function()1195 function *get_function () const { return m_fun; }
get_depth()1196 int get_depth () const { return m_depth; }
1197
1198 bool compare_fields (const frame_region &other) const;
1199
1200 private:
1201 function *m_fun;
1202 int m_depth;
1203 };
1204
1205 } // namespace ana
1206
1207 template <>
1208 template <>
1209 inline bool
test(region * reg)1210 is_a_helper <frame_region *>::test (region *reg)
1211 {
1212 return reg->get_kind () == RK_FRAME;
1213 }
1214
1215 namespace ana {
1216
1217 /* Concrete region subclass, to hold global variables (data and bss). */
1218
1219 class globals_region : public scope_region
1220 {
1221 public:
globals_region(region_id parent_rid)1222 globals_region (region_id parent_rid)
1223 : scope_region (parent_rid)
1224 {}
1225
globals_region(const globals_region & other)1226 globals_region (const globals_region &other)
1227 : scope_region (other)
1228 {
1229 }
1230
1231 /* region vfuncs. */
1232 region *clone () const FINAL OVERRIDE;
get_kind()1233 enum region_kind get_kind () const FINAL OVERRIDE { return RK_GLOBALS; }
1234
1235 /* map_region vfuncs. */
1236 bool valid_key_p (tree key) const FINAL OVERRIDE;
1237
1238 bool compare_fields (const globals_region &other) const;
1239 };
1240
1241 } // namespace ana
1242
1243 template <>
1244 template <>
1245 inline bool
test(region * reg)1246 is_a_helper <globals_region *>::test (region *reg)
1247 {
1248 return reg->get_kind () == RK_GLOBALS;
1249 }
1250
1251 namespace ana {
1252
1253 /* Concrete region subclass. A map_region representing the code, using
1254 FUNCTION_DECLs for its keys. */
1255
1256 class code_region : public map_region
1257 {
1258 public:
code_region(region_id parent_rid)1259 code_region (region_id parent_rid)
1260 : map_region (parent_rid, NULL_TREE)
1261 {}
code_region(const code_region & other)1262 code_region (const code_region &other)
1263 : map_region (other)
1264 {}
1265
1266 /* region vfuncs. */
1267 region *clone () const FINAL OVERRIDE;
get_kind()1268 enum region_kind get_kind () const FINAL OVERRIDE { return RK_CODE; }
1269
1270 /* map_region vfunc. */
1271 bool valid_key_p (tree key) const FINAL OVERRIDE;
1272
1273 region_id get_element (region_model *model,
1274 region_id this_rid,
1275 svalue_id index_sid,
1276 region_model_context *ctxt);
1277
1278 bool compare_fields (const code_region &other) const;
1279 };
1280
1281 } // namespace ana
1282
1283 template <>
1284 template <>
1285 inline bool
test(region * reg)1286 is_a_helper <code_region *>::test (region *reg)
1287 {
1288 return reg->get_kind () == RK_CODE;
1289 }
1290
1291 namespace ana {
1292
1293 /* Concrete region subclass. A map_region representing the code for
1294 a particular function, using LABEL_DECLs for its keys. */
1295
1296 class function_region : public map_region
1297 {
1298 public:
function_region(region_id parent_rid,tree type)1299 function_region (region_id parent_rid, tree type)
1300 : map_region (parent_rid, type)
1301 {
1302 gcc_assert (FUNC_OR_METHOD_TYPE_P (type));
1303 }
function_region(const function_region & other)1304 function_region (const function_region &other)
1305 : map_region (other)
1306 {}
1307
1308 /* region vfuncs. */
1309 region *clone () const FINAL OVERRIDE;
get_kind()1310 enum region_kind get_kind () const FINAL OVERRIDE { return RK_FUNCTION; }
1311
1312 /* map_region vfunc. */
1313 bool valid_key_p (tree key) const FINAL OVERRIDE;
1314
1315 region_id get_element (region_model *model,
1316 region_id this_rid,
1317 svalue_id index_sid,
1318 region_model_context *ctxt);
1319
1320 bool compare_fields (const function_region &other) const;
1321 };
1322
1323 } // namespace ana
1324
1325 template <>
1326 template <>
1327 inline bool
test(region * reg)1328 is_a_helper <function_region *>::test (region *reg)
1329 {
1330 return reg->get_kind () == RK_FUNCTION;
1331 }
1332
1333 namespace ana {
1334
1335 /* Concrete region subclass representing an array (or an array-like view
1336 of a parent region of memory.
1337 This can't be a map_region as we can't use trees as the keys: there's
1338 no guarantee about the uniqueness of an INTEGER_CST. */
1339
1340 class array_region : public region
1341 {
1342 public:
1343 #if 0
1344 wide_int m_test;
1345
1346 typedef wide_int key_t;
1347 typedef int_hash <wide_int, -1, -2> hash_t;
1348 typedef ordered_hash_map<hash_t, region_id> map_t;
1349 #else
1350 typedef int key_t;
1351 typedef int_hash <int, -1, -2> int_hash_t;
1352 typedef ordered_hash_map<int_hash_t, region_id> map_t;
1353 #endif
1354 typedef map_t::iterator iterator_t;
1355
array_region(region_id parent_rid,tree type)1356 array_region (region_id parent_rid, tree type)
1357 : region (parent_rid, svalue_id::null (), type)
1358 {
1359 gcc_assert (TREE_CODE (type) == ARRAY_TYPE);
1360 }
1361 array_region (const array_region &other);
1362
1363 void dump_dot_to_pp (const region_model &model,
1364 region_id this_rid,
1365 pretty_printer *pp) const
1366 FINAL OVERRIDE;
1367
1368 void dump_child_label (const region_model &model,
1369 region_id this_rid,
1370 region_id child_rid,
1371 pretty_printer *pp) const
1372 FINAL OVERRIDE;
1373
1374 /* region vfuncs. */
1375 region *clone () const FINAL OVERRIDE;
get_kind()1376 enum region_kind get_kind () const FINAL OVERRIDE { return RK_ARRAY; }
dyn_cast_array_region()1377 array_region *dyn_cast_array_region () { return this; }
1378
1379 region_id get_element (region_model *model,
1380 region_id this_rid,
1381 svalue_id index_sid,
1382 region_model_context *ctxt);
1383
1384 bool compare_fields (const array_region &other) const;
1385
1386 static bool can_merge_p (const array_region *array_region_a,
1387 const array_region *array_region_b,
1388 array_region *merged_array_region,
1389 region_id merged_rid,
1390 model_merger *merger);
1391
1392 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
1393
begin()1394 iterator_t begin () { return m_map.begin (); }
end()1395 iterator_t end () { return m_map.end (); }
elements()1396 size_t elements () const { return m_map.elements (); }
1397
1398 region_id get_or_create (region_model *model,
1399 region_id this_rid,
1400 key_t key, tree type,
1401 region_model_context *ctxt);
1402 // void unbind (int expr);
1403 region_id *get (key_t key);
1404
1405 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
1406
1407 bool get_key_for_child_region (region_id child_rid,
1408 key_t *out) const;
1409
1410 #if 0
1411 bool get_key_for_child_region (region *child,
1412 const region_model &model,
1413 key_t *out) const;
1414 #endif
1415
1416 void add_to_hash (inchash::hash &hstate) const OVERRIDE;
1417 void print_fields (const region_model &model,
1418 region_id this_rid,
1419 pretty_printer *pp) const
1420 OVERRIDE;
1421 void validate (const region_model &model) const FINAL OVERRIDE;
1422
1423 static key_t key_from_constant (tree cst);
1424 tree constant_from_key (key_t key);
1425
1426 private:
1427 static int key_cmp (const void *, const void *);
1428
1429 /* Mapping from tree to child region. */
1430 map_t m_map;
1431 };
1432
1433 } // namespace ana
1434
1435 template <>
1436 template <>
1437 inline bool
test(region * reg)1438 is_a_helper <array_region *>::test (region *reg)
1439 {
1440 return reg->get_kind () == RK_ARRAY;
1441 }
1442
1443 namespace ana {
1444
1445 /* Concrete region subclass representing a stack, containing all stack
1446 frames, and implicitly providing a POISON_KIND_UNINIT value to all
1447 child regions by default. */
1448
1449 class stack_region : public region
1450 {
1451 public:
stack_region(region_id parent_rid,svalue_id sval_id)1452 stack_region (region_id parent_rid, svalue_id sval_id)
1453 : region (parent_rid, sval_id, NULL_TREE)
1454 {}
1455
1456 stack_region (const stack_region &other);
1457
1458 bool compare_fields (const stack_region &other) const;
1459
1460 region *clone () const FINAL OVERRIDE;
1461
get_kind()1462 enum region_kind get_kind () const FINAL OVERRIDE { return RK_STACK; }
1463
1464 void dump_child_label (const region_model &model,
1465 region_id this_rid,
1466 region_id child_rid,
1467 pretty_printer *pp) const
1468 FINAL OVERRIDE;
1469
1470 void push_frame (region_id frame_rid);
1471 region_id get_current_frame_id () const;
1472 void pop_frame (region_model *model, region_id result_dst_rid,
1473 bool purge, purge_stats *stats,
1474 region_model_context *ctxt);
1475
1476 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
1477
get_num_frames()1478 unsigned get_num_frames () const { return m_frame_rids.length (); }
get_frame_rid(unsigned i)1479 region_id get_frame_rid (unsigned i) const { return m_frame_rids[i]; }
1480
1481 static bool can_merge_p (const stack_region *stack_region_a,
1482 const stack_region *stack_region_b,
1483 model_merger *merger);
1484
1485 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
1486
1487 svalue_id get_value_by_name (tree identifier,
1488 const region_model &model) const;
1489
1490 void validate (const region_model &model) const FINAL OVERRIDE;
1491
1492 private:
1493 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
1494 void print_fields (const region_model &model,
1495 region_id this_rid,
1496 pretty_printer *pp) const
1497 FINAL OVERRIDE;
1498
1499 auto_vec<region_id> m_frame_rids;
1500 };
1501
1502 } // namespace ana
1503
1504 template <>
1505 template <>
1506 inline bool
test(region * reg)1507 is_a_helper <stack_region *>::test (region *reg)
1508 {
1509 return reg->get_kind () == RK_STACK;
1510 }
1511
1512 namespace ana {
1513
1514 /* Concrete region subclass: a region within which regions can be
1515 dynamically allocated. */
1516
1517 class heap_region : public region
1518 {
1519 public:
heap_region(region_id parent_rid,svalue_id sval_id)1520 heap_region (region_id parent_rid, svalue_id sval_id)
1521 : region (parent_rid, sval_id, NULL_TREE)
1522 {}
1523 heap_region (const heap_region &other);
1524
1525 bool compare_fields (const heap_region &other) const;
1526
1527 region *clone () const FINAL OVERRIDE;
1528
get_kind()1529 enum region_kind get_kind () const FINAL OVERRIDE { return RK_HEAP; }
1530
1531 static bool can_merge_p (const heap_region *heap_a, region_id heap_a_rid,
1532 const heap_region *heap_b, region_id heap_b_rid,
1533 heap_region *merged_heap, region_id merged_heap_rid,
1534 model_merger *merger);
1535
1536 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
1537
1538 };
1539
1540 } // namespace ana
1541
1542 template <>
1543 template <>
1544 inline bool
test(region * reg)1545 is_a_helper <heap_region *>::test (region *reg)
1546 {
1547 return reg->get_kind () == RK_HEAP;
1548 }
1549
1550 namespace ana {
1551
1552 /* Concrete region subclass. The root region, containing all regions
1553 (either directly, or as descendents).
1554 Unique within a region_model. */
1555
1556 class root_region : public region
1557 {
1558 public:
1559 root_region ();
1560 root_region (const root_region &other);
1561
1562 bool compare_fields (const root_region &other) const;
1563
1564 region *clone () const FINAL OVERRIDE;
1565
get_kind()1566 enum region_kind get_kind () const FINAL OVERRIDE { return RK_ROOT; }
1567
1568 void dump_child_label (const region_model &model,
1569 region_id this_rid,
1570 region_id child_rid,
1571 pretty_printer *pp) const
1572 FINAL OVERRIDE;
1573
1574 region_id push_frame (region_model *model, function *fun,
1575 vec<svalue_id> *arg_sids,
1576 region_model_context *ctxt);
1577 region_id get_current_frame_id (const region_model &model) const;
1578 void pop_frame (region_model *model, region_id result_dst_rid,
1579 bool purge, purge_stats *stats,
1580 region_model_context *ctxt);
1581
1582 region_id ensure_stack_region (region_model *model);
get_stack_region_id()1583 region_id get_stack_region_id () const { return m_stack_rid; }
1584 stack_region *get_stack_region (const region_model *model) const;
1585
1586 region_id ensure_globals_region (region_model *model);
get_globals_region_id()1587 region_id get_globals_region_id () const { return m_globals_rid; }
1588 globals_region *get_globals_region (const region_model *model) const;
1589
1590 region_id ensure_code_region (region_model *model);
1591 code_region *get_code_region (const region_model *model) const;
1592
1593 region_id ensure_heap_region (region_model *model);
1594 heap_region *get_heap_region (const region_model *model) const;
1595
1596 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
1597
1598 static bool can_merge_p (const root_region *root_region_a,
1599 const root_region *root_region_b,
1600 root_region *merged_root_region,
1601 model_merger *merger);
1602
1603 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
1604
1605 svalue_id get_value_by_name (tree identifier,
1606 const region_model &model) const;
1607
1608 void validate (const region_model &model) const FINAL OVERRIDE;
1609
1610 private:
1611 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
1612 void print_fields (const region_model &model,
1613 region_id this_rid,
1614 pretty_printer *pp) const
1615 FINAL OVERRIDE;
1616
1617 region_id m_stack_rid;
1618 region_id m_globals_rid;
1619 region_id m_code_rid;
1620 region_id m_heap_rid;
1621 };
1622
1623 } // namespace ana
1624
1625 template <>
1626 template <>
1627 inline bool
test(region * reg)1628 is_a_helper <root_region *>::test (region *reg)
1629 {
1630 return reg->get_kind () == RK_ROOT;
1631 }
1632
1633 namespace ana {
1634
1635 /* Concrete region subclass: a region to use when dereferencing an unknown
1636 pointer. */
1637
1638 class symbolic_region : public region
1639 {
1640 public:
symbolic_region(region_id parent_rid,tree type,bool possibly_null)1641 symbolic_region (region_id parent_rid, tree type, bool possibly_null)
1642 : region (parent_rid, svalue_id::null (), type),
1643 m_possibly_null (possibly_null)
1644 {}
1645 symbolic_region (const symbolic_region &other);
1646
dyn_cast_symbolic_region()1647 const symbolic_region *dyn_cast_symbolic_region () const FINAL OVERRIDE
1648 { return this; }
dyn_cast_symbolic_region()1649 symbolic_region *dyn_cast_symbolic_region () FINAL OVERRIDE
1650 { return this; }
1651
1652 bool compare_fields (const symbolic_region &other) const;
1653
1654 region *clone () const FINAL OVERRIDE;
1655
get_kind()1656 enum region_kind get_kind () const FINAL OVERRIDE { return RK_SYMBOLIC; }
1657
1658 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
1659
1660 void print_fields (const region_model &model,
1661 region_id this_rid,
1662 pretty_printer *pp) const FINAL OVERRIDE;
1663
1664 bool m_possibly_null;
1665 };
1666
1667 /* A region_model encapsulates a representation of the state of memory, with
1668 a tree of regions, along with their associated values.
1669 The representation is graph-like because values can be pointers to
1670 regions.
1671 It also stores a constraint_manager, capturing relationships between
1672 the values. */
1673
1674 class region_model
1675 {
1676 public:
1677 region_model ();
1678 region_model (const region_model &other);
1679 ~region_model ();
1680
1681 #if 0//__cplusplus >= 201103
1682 region_model (region_model &&other);
1683 #endif
1684
1685 region_model &operator= (const region_model &other);
1686
1687 bool operator== (const region_model &other) const;
1688 bool operator!= (const region_model &other) const
1689 {
1690 return !(*this == other);
1691 }
1692
1693 hashval_t hash () const;
1694
1695 void print (pretty_printer *pp) const;
1696
1697 void print_svalue (svalue_id sid, pretty_printer *pp) const;
1698
1699 void dump_dot_to_pp (pretty_printer *pp) const;
1700 void dump_dot_to_file (FILE *fp) const;
1701 void dump_dot (const char *path) const;
1702
1703 void dump_to_pp (pretty_printer *pp, bool summarize) const;
1704 void dump (FILE *fp, bool summarize) const;
1705 void dump (bool summarize) const;
1706
1707 void debug () const;
1708
1709 void validate () const;
1710
1711 void canonicalize (region_model_context *ctxt);
1712 bool canonicalized_p () const;
1713
1714 void check_for_poison (tree expr, region_model_context *ctxt);
1715 void on_assignment (const gassign *stmt, region_model_context *ctxt);
1716 bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
1717 void on_call_post (const gcall *stmt,
1718 bool unknown_side_effects,
1719 region_model_context *ctxt);
1720 void handle_unrecognized_call (const gcall *call,
1721 region_model_context *ctxt);
1722 void on_return (const greturn *stmt, region_model_context *ctxt);
1723 void on_setjmp (const gcall *stmt, const exploded_node *enode,
1724 region_model_context *ctxt);
1725 void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
1726 int setjmp_stack_depth, region_model_context *ctxt);
1727
1728 void update_for_phis (const supernode *snode,
1729 const cfg_superedge *last_cfg_superedge,
1730 region_model_context *ctxt);
1731
1732 void handle_phi (const gphi *phi,
1733 tree lhs, tree rhs, bool is_back_edge,
1734 region_model_context *ctxt);
1735
1736 bool maybe_update_for_edge (const superedge &edge,
1737 const gimple *last_stmt,
1738 region_model_context *ctxt);
1739
get_root_rid()1740 region_id get_root_rid () const { return m_root_rid; }
1741 root_region *get_root_region () const;
1742
1743 region_id get_stack_region_id () const;
1744 region_id push_frame (function *fun, vec<svalue_id> *arg_sids,
1745 region_model_context *ctxt);
1746 region_id get_current_frame_id () const;
1747 function * get_current_function () const;
1748 void pop_frame (region_id result_dst_rid,
1749 bool purge, purge_stats *stats,
1750 region_model_context *ctxt);
1751 int get_stack_depth () const;
1752 function *get_function_at_depth (unsigned depth) const;
1753
1754 region_id get_globals_region_id () const;
1755
1756 svalue_id add_svalue (svalue *sval);
1757 void replace_svalue (svalue_id sid, svalue *new_sval);
1758
1759 region_id add_region (region *r);
1760
1761 region_id add_region_for_type (region_id parent_rid, tree type,
1762 region_model_context *ctxt);
1763
1764 svalue *get_svalue (svalue_id sval_id) const;
1765 region *get_region (region_id rid) const;
1766
1767 template <typename Subclass>
get_region(region_id rid)1768 Subclass *get_region (region_id rid) const
1769 {
1770 region *result = get_region (rid);
1771 if (result)
1772 gcc_assert (is_a<Subclass *> (result));
1773 return (Subclass *)result;
1774 }
1775
1776 region_id get_lvalue (path_var pv, region_model_context *ctxt);
1777 region_id get_lvalue (tree expr, region_model_context *ctxt);
1778 svalue_id get_rvalue (path_var pv, region_model_context *ctxt);
1779 svalue_id get_rvalue (tree expr, region_model_context *ctxt);
1780
1781 svalue_id get_or_create_ptr_svalue (tree ptr_type, region_id id);
1782 svalue_id get_or_create_constant_svalue (tree cst_expr);
1783 svalue_id get_svalue_for_fndecl (tree ptr_type, tree fndecl,
1784 region_model_context *ctxt);
1785 svalue_id get_svalue_for_label (tree ptr_type, tree label,
1786 region_model_context *ctxt);
1787
1788 region_id get_region_for_fndecl (tree fndecl, region_model_context *ctxt);
1789 region_id get_region_for_label (tree label, region_model_context *ctxt);
1790
1791 svalue_id maybe_cast (tree type, svalue_id sid, region_model_context *ctxt);
1792 svalue_id maybe_cast_1 (tree type, svalue_id sid);
1793
1794 region_id get_field_region (region_id rid, tree field,
1795 region_model_context *ctxt);
1796
1797 region_id deref_rvalue (svalue_id ptr_sid, region_model_context *ctxt);
1798 region_id deref_rvalue (tree ptr, region_model_context *ctxt);
1799
1800 void set_value (region_id lhs_rid, svalue_id rhs_sid,
1801 region_model_context *ctxt);
1802 void set_value (tree lhs, tree rhs, region_model_context *ctxt);
1803 svalue_id set_to_new_unknown_value (region_id dst_rid, tree type,
1804 region_model_context *ctxt);
1805
1806 void copy_region (region_id dst_rid, region_id src_rid,
1807 region_model_context *ctxt);
1808
1809 tristate eval_condition (svalue_id lhs,
1810 enum tree_code op,
1811 svalue_id rhs) const;
1812 tristate eval_condition_without_cm (svalue_id lhs,
1813 enum tree_code op,
1814 svalue_id rhs) const;
1815 tristate eval_condition (tree lhs,
1816 enum tree_code op,
1817 tree rhs,
1818 region_model_context *ctxt);
1819 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
1820 region_model_context *ctxt);
1821
1822 tree maybe_get_constant (svalue_id sid) const;
1823
1824 region_id add_new_malloc_region ();
1825
1826 tree get_representative_tree (svalue_id sid) const;
1827 path_var get_representative_path_var (region_id rid) const;
1828 void get_path_vars_for_svalue (svalue_id sid, vec<path_var> *out) const;
1829
1830 void purge_unused_svalues (purge_stats *out,
1831 region_model_context *ctxt,
1832 svalue_id_set *known_used_sids = NULL);
1833 void remap_svalue_ids (const svalue_id_map &map);
1834 void remap_region_ids (const region_id_map &map);
1835
1836 void purge_regions (const region_id_set &set,
1837 purge_stats *stats,
1838 logger *logger);
1839
get_num_svalues()1840 unsigned get_num_svalues () const { return m_svalues.length (); }
get_num_regions()1841 unsigned get_num_regions () const { return m_regions.length (); }
1842
1843 /* For selftests. */
get_constraints()1844 constraint_manager *get_constraints ()
1845 {
1846 return m_constraints;
1847 }
1848
1849 void get_descendents (region_id rid, region_id_set *out,
1850 region_id exclude_rid) const;
1851
1852 void delete_region_and_descendents (region_id rid,
1853 enum poison_kind pkind,
1854 purge_stats *stats,
1855 logger *logger);
1856
1857 bool can_merge_with_p (const region_model &other_model,
1858 region_model *out_model,
1859 svalue_id_merger_mapping *out) const;
1860 bool can_merge_with_p (const region_model &other_model,
1861 region_model *out_model) const;
1862
1863 svalue_id get_value_by_name (const char *name) const;
1864
1865 svalue_id convert_byte_offset_to_array_index (tree ptr_type,
1866 svalue_id offset_sid);
1867
1868 region_id get_or_create_mem_ref (tree type,
1869 svalue_id ptr_sid,
1870 svalue_id offset_sid,
1871 region_model_context *ctxt);
1872 region_id get_or_create_pointer_plus_expr (tree type,
1873 svalue_id ptr_sid,
1874 svalue_id offset_sid,
1875 region_model_context *ctxt);
1876 region_id get_or_create_view (region_id raw_rid, tree type,
1877 region_model_context *ctxt);
1878
1879 tree get_fndecl_for_call (const gcall *call,
1880 region_model_context *ctxt);
1881
1882 private:
1883 region_id get_lvalue_1 (path_var pv, region_model_context *ctxt);
1884 svalue_id get_rvalue_1 (path_var pv, region_model_context *ctxt);
1885
1886 void copy_struct_region (region_id dst_rid, struct_region *dst_reg,
1887 struct_region *src_reg, region_model_context *ctxt);
1888 void copy_union_region (region_id dst_rid, union_region *src_reg,
1889 region_model_context *ctxt);
1890 void copy_array_region (region_id dst_rid, array_region *dst_reg,
1891 array_region *src_reg, region_model_context *ctxt);
1892
1893 region_id make_region_for_unexpected_tree_code (region_model_context *ctxt,
1894 tree t,
1895 const dump_location_t &loc);
1896
1897 void add_any_constraints_from_ssa_def_stmt (tree lhs,
1898 enum tree_code op,
1899 tree rhs,
1900 region_model_context *ctxt);
1901 void add_any_constraints_from_gassign (enum tree_code op,
1902 tree rhs,
1903 const gassign *assign,
1904 region_model_context *ctxt);
1905 void add_any_constraints_from_gcall (enum tree_code op,
1906 tree rhs,
1907 const gcall *call,
1908 region_model_context *ctxt);
1909
1910 void update_for_call_superedge (const call_superedge &call_edge,
1911 region_model_context *ctxt);
1912 void update_for_return_superedge (const return_superedge &return_edge,
1913 region_model_context *ctxt);
1914 void update_for_call_summary (const callgraph_superedge &cg_sedge,
1915 region_model_context *ctxt);
1916 bool apply_constraints_for_gcond (const cfg_superedge &edge,
1917 const gcond *cond_stmt,
1918 region_model_context *ctxt);
1919 bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
1920 const gswitch *switch_stmt,
1921 region_model_context *ctxt);
1922
1923 void poison_any_pointers_to_bad_regions (const region_id_set &bad_regions,
1924 enum poison_kind pkind);
1925
1926 void dump_summary_of_rep_path_vars (pretty_printer *pp,
1927 auto_vec<path_var> *rep_path_vars,
1928 bool *is_first);
1929
1930 auto_delete_vec<svalue> m_svalues;
1931 auto_delete_vec<region> m_regions;
1932 region_id m_root_rid;
1933 constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
1934 };
1935
1936 /* Some region_model activity could lead to warnings (e.g. attempts to use an
1937 uninitialized value). This abstract base class encapsulates an interface
1938 for the region model to use when emitting such warnings.
1939
1940 It also provides an interface for being notified about svalue_ids being
1941 remapped, and being deleted.
1942
1943 Having this as an abstract base class allows us to support the various
1944 operations needed by program_state in the analyzer within region_model,
1945 whilst keeping them somewhat modularized. */
1946
1947 class region_model_context
1948 {
1949 public:
1950 virtual void warn (pending_diagnostic *d) = 0;
1951
1952 /* Hook for clients that store svalue_id instances, so that they
1953 can remap their IDs when the underlying region_model renumbers
1954 the IDs. */
1955 virtual void remap_svalue_ids (const svalue_id_map &map) = 0;
1956
1957 #if 0
1958 /* Return true if if's OK to purge SID when simplifying state.
1959 Subclasses can return false for values that have sm state,
1960 to avoid generating "leak" false positives. */
1961 virtual bool can_purge_p (svalue_id sid) = 0;
1962 #endif
1963
1964 /* Hook for clients to be notified when a range of SIDs have
1965 been purged, so that they can purge state relating to those
1966 values (and potentially emit warnings about leaks).
1967 All SIDs from FIRST_PURGED_SID numerically upwards are being
1968 purged.
1969 The return values is a count of how many items of data the client
1970 has purged (potentially for use in selftests).
1971 MAP has already been applied to the IDs, but is provided in case
1972 the client needs to figure out the old IDs. */
1973 virtual int on_svalue_purge (svalue_id first_purged_sid,
1974 const svalue_id_map &map) = 0;
1975
1976 virtual logger *get_logger () = 0;
1977
1978 /* Hook for clients to be notified when CHILD_SID is created
1979 from PARENT_SID, when "inheriting" a value for a region from a
1980 parent region.
1981 This exists so that state machines that inherit state can
1982 propagate the state from parent to child. */
1983 virtual void on_inherited_svalue (svalue_id parent_sid,
1984 svalue_id child_sid) = 0;
1985
1986 /* Hook for clients to be notified when DST_SID is created
1987 (or reused) as a cast from SRC_SID.
1988 This exists so that state machines can propagate the state
1989 from SRC_SID to DST_SID. */
1990 virtual void on_cast (svalue_id src_sid,
1991 svalue_id dst_sid) = 0;
1992
1993 /* Hook for clients to be notified when the condition
1994 "LHS OP RHS" is added to the region model.
1995 This exists so that state machines can detect tests on edges,
1996 and use them to trigger sm-state transitions (e.g. transitions due
1997 to ptrs becoming known to be NULL or non-NULL, rather than just
1998 "unchecked") */
1999 virtual void on_condition (tree lhs, enum tree_code op, tree rhs) = 0;
2000
2001 /* Hooks for clients to be notified when an unknown change happens
2002 to SID (in response to a call to an unknown function). */
2003 virtual void on_unknown_change (svalue_id sid) = 0;
2004
2005 /* Hooks for clients to be notified when a phi node is handled,
2006 where RHS is the pertinent argument. */
2007 virtual void on_phi (const gphi *phi, tree rhs) = 0;
2008
2009 /* Hooks for clients to be notified when the region model doesn't
2010 know how to handle the tree code of T at LOC. */
2011 virtual void on_unexpected_tree_code (tree t,
2012 const dump_location_t &loc) = 0;
2013 };
2014
2015 /* A "do nothing" subclass of region_model_context. */
2016
2017 class noop_region_model_context : public region_model_context
2018 {
2019 public:
warn(pending_diagnostic *)2020 void warn (pending_diagnostic *) OVERRIDE {}
remap_svalue_ids(const svalue_id_map &)2021 void remap_svalue_ids (const svalue_id_map &) OVERRIDE {}
on_svalue_purge(svalue_id,const svalue_id_map &)2022 int on_svalue_purge (svalue_id, const svalue_id_map &) OVERRIDE
2023 {
2024 return 0;
2025 }
get_logger()2026 logger *get_logger () OVERRIDE { return NULL; }
on_inherited_svalue(svalue_id parent_sid ATTRIBUTE_UNUSED,svalue_id child_sid ATTRIBUTE_UNUSED)2027 void on_inherited_svalue (svalue_id parent_sid ATTRIBUTE_UNUSED,
2028 svalue_id child_sid ATTRIBUTE_UNUSED)
2029 OVERRIDE
2030 {
2031 }
on_cast(svalue_id src_sid ATTRIBUTE_UNUSED,svalue_id dst_sid ATTRIBUTE_UNUSED)2032 void on_cast (svalue_id src_sid ATTRIBUTE_UNUSED,
2033 svalue_id dst_sid ATTRIBUTE_UNUSED) OVERRIDE
2034 {
2035 }
on_condition(tree lhs ATTRIBUTE_UNUSED,enum tree_code op ATTRIBUTE_UNUSED,tree rhs ATTRIBUTE_UNUSED)2036 void on_condition (tree lhs ATTRIBUTE_UNUSED,
2037 enum tree_code op ATTRIBUTE_UNUSED,
2038 tree rhs ATTRIBUTE_UNUSED) OVERRIDE
2039 {
2040 }
on_unknown_change(svalue_id sid ATTRIBUTE_UNUSED)2041 void on_unknown_change (svalue_id sid ATTRIBUTE_UNUSED) OVERRIDE
2042 {
2043 }
on_phi(const gphi * phi ATTRIBUTE_UNUSED,tree rhs ATTRIBUTE_UNUSED)2044 void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
2045 tree rhs ATTRIBUTE_UNUSED) OVERRIDE
2046 {
2047 }
on_unexpected_tree_code(tree,const dump_location_t &)2048 void on_unexpected_tree_code (tree, const dump_location_t &) OVERRIDE {}
2049 };
2050
2051 /* A subclass of region_model_context for determining if operations fail
2052 e.g. "can we generate a region for the lvalue of EXPR?". */
2053
2054 class tentative_region_model_context : public noop_region_model_context
2055 {
2056 public:
tentative_region_model_context()2057 tentative_region_model_context () : m_num_unexpected_codes (0) {}
2058
on_unexpected_tree_code(tree,const dump_location_t &)2059 void on_unexpected_tree_code (tree, const dump_location_t &)
2060 FINAL OVERRIDE
2061 {
2062 m_num_unexpected_codes++;
2063 }
2064
had_errors_p()2065 bool had_errors_p () const { return m_num_unexpected_codes > 0; }
2066
2067 private:
2068 int m_num_unexpected_codes;
2069 };
2070
2071 /* A bundle of data for use when attempting to merge two region_model
2072 instances to make a third. */
2073
2074 struct model_merger
2075 {
model_mergermodel_merger2076 model_merger (const region_model *model_a,
2077 const region_model *model_b,
2078 region_model *merged_model,
2079 svalue_id_merger_mapping *sid_mapping)
2080 : m_model_a (model_a), m_model_b (model_b),
2081 m_merged_model (merged_model),
2082 m_map_regions_from_a_to_m (model_a->get_num_regions ()),
2083 m_map_regions_from_b_to_m (model_b->get_num_regions ()),
2084 m_sid_mapping (sid_mapping)
2085 {
2086 gcc_assert (sid_mapping);
2087 }
2088
2089 void dump_to_pp (pretty_printer *pp) const;
2090 void dump (FILE *fp) const;
2091 void dump () const;
2092
2093 template <typename Subclass>
get_region_amodel_merger2094 Subclass *get_region_a (region_id rid_a) const
2095 {
2096 return m_model_a->get_region <Subclass> (rid_a);
2097 }
2098
2099 template <typename Subclass>
get_region_bmodel_merger2100 Subclass *get_region_b (region_id rid_b) const
2101 {
2102 return m_model_b->get_region <Subclass> (rid_b);
2103 }
2104
2105 bool can_merge_values_p (svalue_id sid_a,
2106 svalue_id sid_b,
2107 svalue_id *merged_sid);
2108
2109 void record_regions (region_id a_rid,
2110 region_id b_rid,
2111 region_id merged_rid);
2112
2113 void record_svalues (svalue_id a_sid,
2114 svalue_id b_sid,
2115 svalue_id merged_sid);
2116
2117 const region_model *m_model_a;
2118 const region_model *m_model_b;
2119 region_model *m_merged_model;
2120
2121 one_way_region_id_map m_map_regions_from_a_to_m;
2122 one_way_region_id_map m_map_regions_from_b_to_m;
2123 svalue_id_merger_mapping *m_sid_mapping;
2124 };
2125
2126 /* A bundle of data that can be optionally generated during merger of two
2127 region_models that describes how svalue_ids in each of the two inputs
2128 are mapped to svalue_ids in the merged output.
2129
2130 For use when merging sm-states within program_state. */
2131
2132 struct svalue_id_merger_mapping
2133 {
2134 svalue_id_merger_mapping (const region_model &a,
2135 const region_model &b);
2136
2137 void dump_to_pp (pretty_printer *pp) const;
2138 void dump (FILE *fp) const;
2139 void dump () const;
2140
2141 one_way_svalue_id_map m_map_from_a_to_m;
2142 one_way_svalue_id_map m_map_from_b_to_m;
2143 };
2144
2145 /* A bundle of data used when canonicalizing a region_model so that the
2146 order of regions and svalues is in a predictable order (thus increasing
2147 the chance of two region_models being equal).
2148
2149 This object is used to keep track of a recursive traversal across the
2150 svalues and regions within the model, made in a deterministic order,
2151 assigning new ids the first time each region or svalue is
2152 encountered. */
2153
2154 struct canonicalization
2155 {
2156 canonicalization (const region_model &model);
2157 void walk_rid (region_id rid);
2158 void walk_sid (svalue_id sid);
2159
2160 void dump_to_pp (pretty_printer *pp) const;
2161 void dump (FILE *fp) const;
2162 void dump () const;
2163
2164 const region_model &m_model;
2165 /* Maps from existing IDs to new IDs. */
2166 region_id_map m_rid_map;
2167 svalue_id_map m_sid_map;
2168 /* The next IDs to hand out. */
2169 int m_next_rid_int;
2170 int m_next_sid_int;
2171 };
2172
2173 } // namespace ana
2174
2175 namespace inchash
2176 {
2177 extern void add (svalue_id sid, hash &hstate);
2178 extern void add (region_id rid, hash &hstate);
2179 } // namespace inchash
2180
2181 extern void debug (const region_model &rmodel);
2182
2183 namespace ana {
2184
2185 #if CHECKING_P
2186
2187 namespace selftest {
2188
2189 using namespace ::selftest;
2190
2191 /* An implementation of region_model_context for use in selftests, which
2192 stores any pending_diagnostic instances passed to it. */
2193
2194 class test_region_model_context : public noop_region_model_context
2195 {
2196 public:
warn(pending_diagnostic * d)2197 void warn (pending_diagnostic *d) FINAL OVERRIDE
2198 {
2199 m_diagnostics.safe_push (d);
2200 }
2201
get_num_diagnostics()2202 unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
2203
on_unexpected_tree_code(tree t,const dump_location_t &)2204 void on_unexpected_tree_code (tree t, const dump_location_t &)
2205 FINAL OVERRIDE
2206 {
2207 internal_error ("unhandled tree code: %qs",
2208 t ? get_tree_code_name (TREE_CODE (t)) : "(null)");
2209 }
2210
2211 private:
2212 /* Implicitly delete any diagnostics in the dtor. */
2213 auto_delete_vec<pending_diagnostic> m_diagnostics;
2214 };
2215
2216 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
2217 Verify that MODEL remains satisfiable. */
2218
2219 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
2220 SELFTEST_BEGIN_STMT \
2221 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
2222 ASSERT_TRUE (sat); \
2223 SELFTEST_END_STMT
2224
2225 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
2226 Verify that the result is not satisfiable. */
2227
2228 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
2229 SELFTEST_BEGIN_STMT \
2230 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
2231 ASSERT_FALSE (sat); \
2232 SELFTEST_END_STMT
2233
2234 /* Implementation detail of the ASSERT_CONDITION_* macros. */
2235
2236 void assert_condition (const location &loc,
2237 region_model &model,
2238 tree lhs, tree_code op, tree rhs,
2239 tristate expected);
2240
2241 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
2242 as "true". */
2243
2244 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
2245 SELFTEST_BEGIN_STMT \
2246 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
2247 tristate (tristate::TS_TRUE)); \
2248 SELFTEST_END_STMT
2249
2250 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
2251 as "false". */
2252
2253 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
2254 SELFTEST_BEGIN_STMT \
2255 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
2256 tristate (tristate::TS_FALSE)); \
2257 SELFTEST_END_STMT
2258
2259 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
2260 as "unknown". */
2261
2262 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
2263 SELFTEST_BEGIN_STMT \
2264 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
2265 tristate (tristate::TS_UNKNOWN)); \
2266 SELFTEST_END_STMT
2267
2268 } /* end of namespace selftest. */
2269
2270 #endif /* #if CHECKING_P */
2271
2272 } // namespace ana
2273
2274 #endif /* GCC_ANALYZER_REGION_MODEL_H */
2275