1 /* Regions 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_H
22 #define GCC_ANALYZER_REGION_H
23
24 #include "analyzer/complexity.h"
25
26 namespace ana {
27
28 /* An enum for identifying different spaces within memory. */
29
30 enum memory_space
31 {
32 MEMSPACE_UNKNOWN,
33 MEMSPACE_CODE,
34 MEMSPACE_GLOBALS,
35 MEMSPACE_STACK,
36 MEMSPACE_HEAP,
37 MEMSPACE_READONLY_DATA
38 };
39
40 /* An enum for discriminating between the different concrete subclasses
41 of region. */
42
43 enum region_kind
44 {
45 RK_FRAME,
46 RK_GLOBALS,
47 RK_CODE,
48 RK_FUNCTION,
49 RK_LABEL,
50 RK_STACK,
51 RK_HEAP,
52 RK_ROOT,
53 RK_SYMBOLIC,
54 RK_DECL,
55 RK_FIELD,
56 RK_ELEMENT,
57 RK_OFFSET,
58 RK_SIZED,
59 RK_CAST,
60 RK_HEAP_ALLOCATED,
61 RK_ALLOCA,
62 RK_STRING,
63 RK_BIT_RANGE,
64 RK_UNKNOWN
65 };
66
67 /* Region and its subclasses.
68
69 The class hierarchy looks like this (using indentation to show
70 inheritance, and with region_kinds shown for the concrete subclasses):
71
72 region
73 space_region
74 frame_region (RK_FRAME)
75 globals_region (RK_GLOBALS)
76 code_region (RK_CODE)
77 stack_region (RK_STACK)
78 heap_region (RK_HEAP)
79 root_region (RK_ROOT)
80 function_region (RK_FUNCTION)
81 label_region (RK_LABEL)
82 symbolic_region (RK_SYMBOLIC)
83 decl_region (RK_DECL),
84 field_region (RK_FIELD)
85 element_region (RK_ELEMENT)
86 offset_region (RK_OFFSET)
87 sized_region (RK_SIZED)
88 cast_region (RK_CAST)
89 heap_allocated_region (RK_HEAP_ALLOCATED)
90 alloca_region (RK_ALLOCA)
91 string_region (RK_STRING)
92 bit_range_region (RK_BIT_RANGE)
93 unknown_region (RK_UNKNOWN). */
94
95 /* Abstract base class for representing ways of accessing chunks of memory.
96
97 Regions form a tree-like hierarchy, with a root region at the base,
98 with memory space regions within it, representing the stack and
99 globals, with frames within the stack, and regions for variables
100 within the frames and the "globals" region. Regions for structs
101 can have subregions for fields. */
102
103 class region
104 {
105 public:
106 virtual ~region ();
107
get_id()108 unsigned get_id () const { return m_id; }
109 static int cmp_ids (const region *reg1, const region *reg2);
110
111 virtual enum region_kind get_kind () const = 0;
112 virtual const frame_region *
dyn_cast_frame_region()113 dyn_cast_frame_region () const { return NULL; }
114 virtual const function_region *
dyn_cast_function_region()115 dyn_cast_function_region () const { return NULL; }
116 virtual const symbolic_region *
dyn_cast_symbolic_region()117 dyn_cast_symbolic_region () const { return NULL; }
118 virtual const decl_region *
dyn_cast_decl_region()119 dyn_cast_decl_region () const { return NULL; }
120 virtual const field_region *
dyn_cast_field_region()121 dyn_cast_field_region () const { return NULL; }
122 virtual const element_region *
dyn_cast_element_region()123 dyn_cast_element_region () const { return NULL; }
124 virtual const offset_region *
dyn_cast_offset_region()125 dyn_cast_offset_region () const { return NULL; }
126 virtual const sized_region *
dyn_cast_sized_region()127 dyn_cast_sized_region () const { return NULL; }
128 virtual const cast_region *
dyn_cast_cast_region()129 dyn_cast_cast_region () const { return NULL; }
130 virtual const string_region *
dyn_cast_string_region()131 dyn_cast_string_region () const { return NULL; }
132 virtual const bit_range_region *
dyn_cast_bit_range_region()133 dyn_cast_bit_range_region () const { return NULL; }
134
135 virtual void accept (visitor *v) const;
136
get_parent_region()137 const region *get_parent_region () const { return m_parent; }
138 const region *get_base_region () const;
139 bool base_region_p () const;
140 bool descendent_of_p (const region *elder) const;
141 const frame_region *maybe_get_frame_region () const;
142 enum memory_space get_memory_space () const;
143 bool can_have_initial_svalue_p () const;
144
145 tree maybe_get_decl () const;
146
get_type()147 tree get_type () const { return m_type; }
148
149 void print (const region_model &model,
150 pretty_printer *pp) const;
151 label_text get_desc (bool simple=true) const;
152
153 virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
154 void dump (bool simple) const;
155
156 json::value *to_json () const;
157
158 bool non_null_p () const;
159
160 static int cmp_ptr_ptr (const void *, const void *);
161
162 bool involves_p (const svalue *sval) const;
163
164 region_offset get_offset () const;
165
166 /* Attempt to get the size of this region as a concrete number of bytes.
167 If successful, return true and write the size to *OUT.
168 Otherwise return false. */
169 virtual bool get_byte_size (byte_size_t *out) const;
170
171 /* Attempt to get the size of this region as a concrete number of bits.
172 If successful, return true and write the size to *OUT.
173 Otherwise return false. */
174 virtual bool get_bit_size (bit_size_t *out) const;
175
176 /* Get a symbolic value describing the size of this region in bytes
177 (which could be "unknown"). */
178 virtual const svalue *get_byte_size_sval (region_model_manager *mgr) const;
179
180 /* Attempt to get the offset in bits of this region relative to its parent.
181 If successful, return true and write to *OUT.
182 Otherwise return false. */
183 virtual bool get_relative_concrete_offset (bit_offset_t *out) const;
184
185 /* Attempt to get the position and size of this region expressed as a
186 concrete range of bytes relative to its parent.
187 If successful, return true and write to *OUT.
188 Otherwise return false. */
189 bool get_relative_concrete_byte_range (byte_range *out) const;
190
191 void
192 get_subregions_for_binding (region_model_manager *mgr,
193 bit_offset_t start_bit_offset,
194 bit_size_t size_in_bits,
195 tree type,
196 auto_vec <const region *> *out) const;
197
198 bool symbolic_for_unknown_ptr_p () const;
199
200 /* For most base regions it makes sense to track the bindings of the region
201 within the store. As an optimization, some are not tracked (to avoid
202 bloating the store object with redundant binding clusters). */
tracked_p()203 virtual bool tracked_p () const { return true; }
204
get_complexity()205 const complexity &get_complexity () const { return m_complexity; }
206
207 bool is_named_decl_p (const char *decl_name) const;
208
209 protected:
210 region (complexity c, unsigned id, const region *parent, tree type);
211
212 private:
213 region_offset calc_offset () const;
214
215 complexity m_complexity;
216 unsigned m_id; // purely for deterministic sorting at this stage, for dumps
217 const region *m_parent;
218 tree m_type;
219
220 mutable region_offset *m_cached_offset;
221 };
222
223 } // namespace ana
224
225 template <>
226 template <>
227 inline bool
test(const region *)228 is_a_helper <const region *>::test (const region *)
229 {
230 return true;
231 }
232
233 namespace ana {
234
235 /* Abstract subclass of region, for regions that represent an untyped
236 space within memory, such as the stack or the heap. */
237
238 class space_region : public region
239 {
240 protected:
space_region(unsigned id,const region * parent)241 space_region (unsigned id, const region *parent)
242 : region (complexity (parent), id, parent, NULL_TREE)
243 {}
244 };
245
246 /* Concrete space_region subclass, representing a function frame on the stack,
247 to contain the locals.
248 The parent is the stack region; there's also a hierarchy of call-stack
249 prefixes expressed via m_calling_frame.
250 For example, given "oldest" calling "middle" called "newest" we would have
251 - a stack depth of 3
252 - frame (A) for "oldest" with index 0 for depth 1, calling_frame == NULL
253 - frame (B) for "middle" with index 1 for depth 2, calling_frame == (A)
254 - frame (C) for "newest" with index 2 for depth 3, calling_frame == (B)
255 where the parent region for each of the frames is the "stack" region.
256 The index is the count of frames earlier than this in the stack. */
257
258 class frame_region : public space_region
259 {
260 public:
261 /* A support class for uniquifying instances of frame_region. */
262 struct key_t
263 {
key_tkey_t264 key_t (const frame_region *calling_frame, function *fun)
265 : m_calling_frame (calling_frame), m_fun (fun)
266 {
267 /* calling_frame can be NULL. */
268 gcc_assert (fun);
269 }
270
hashkey_t271 hashval_t hash () const
272 {
273 inchash::hash hstate;
274 hstate.add_ptr (m_calling_frame);
275 hstate.add_ptr (m_fun);
276 return hstate.end ();
277 }
278
279 bool operator== (const key_t &other) const
280 {
281 return (m_calling_frame == other.m_calling_frame && m_fun == other.m_fun);
282 }
283
mark_deletedkey_t284 void mark_deleted () { m_fun = reinterpret_cast<function *> (1); }
mark_emptykey_t285 void mark_empty () { m_fun = NULL; }
is_deletedkey_t286 bool is_deleted () const
287 {
288 return m_fun == reinterpret_cast<function *> (1);
289 }
is_emptykey_t290 bool is_empty () const { return m_fun == NULL; }
291
292 const frame_region *m_calling_frame;
293 function *m_fun;
294 };
295
frame_region(unsigned id,const region * parent,const frame_region * calling_frame,function * fun,int index)296 frame_region (unsigned id, const region *parent,
297 const frame_region *calling_frame,
298 function *fun, int index)
299 : space_region (id, parent), m_calling_frame (calling_frame),
300 m_fun (fun), m_index (index)
301 {}
302 ~frame_region ();
303
304 /* region vfuncs. */
get_kind()305 enum region_kind get_kind () const FINAL OVERRIDE { return RK_FRAME; }
dyn_cast_frame_region()306 const frame_region * dyn_cast_frame_region () const FINAL OVERRIDE
307 {
308 return this;
309 }
310 void accept (visitor *v) const FINAL OVERRIDE;
311 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
312
313 /* Accessors. */
get_calling_frame()314 const frame_region *get_calling_frame () const { return m_calling_frame; }
get_function()315 function *get_function () const { return m_fun; }
get_fndecl()316 tree get_fndecl () const { return get_function ()->decl; }
get_index()317 int get_index () const { return m_index; }
get_stack_depth()318 int get_stack_depth () const { return m_index + 1; }
319
320 const decl_region *
321 get_region_for_local (region_model_manager *mgr,
322 tree expr,
323 const region_model_context *ctxt) const;
324
get_num_locals()325 unsigned get_num_locals () const { return m_locals.elements (); }
326
327 /* Implemented in region-model-manager.cc. */
328 void dump_untracked_regions () const;
329
330 private:
331 const frame_region *m_calling_frame;
332 function *m_fun;
333 int m_index;
334
335 /* The regions for the decls within this frame are managed by this
336 object, rather than the region_model_manager, to make it a simple
337 lookup by tree. */
338 typedef hash_map<tree, decl_region *> map_t;
339 map_t m_locals;
340 };
341
342 } // namespace ana
343
344 template <>
345 template <>
346 inline bool
test(const region * reg)347 is_a_helper <const frame_region *>::test (const region *reg)
348 {
349 return reg->get_kind () == RK_FRAME;
350 }
351
352 template <> struct default_hash_traits<frame_region::key_t>
353 : public member_function_hash_traits<frame_region::key_t>
354 {
355 static const bool empty_zero_p = true;
356 };
357
358 namespace ana {
359
360 /* Concrete space_region subclass, to hold global variables (data and bss). */
361
362 class globals_region : public space_region
363 {
364 public:
365 globals_region (unsigned id, const region *parent)
366 : space_region (id, parent)
367 {}
368
369 /* region vfuncs. */
370 enum region_kind get_kind () const FINAL OVERRIDE { return RK_GLOBALS; }
371 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
372 };
373
374 } // namespace ana
375
376 template <>
377 template <>
378 inline bool
379 is_a_helper <const globals_region *>::test (const region *reg)
380 {
381 return reg->get_kind () == RK_GLOBALS;
382 }
383
384 namespace ana {
385
386 /* Concrete space_region subclass, representing the code segment
387 containing functions. */
388
389 class code_region : public space_region
390 {
391 public:
392 code_region (unsigned id, const region *parent)
393 : space_region (id, parent)
394 {}
395
396 /* region vfuncs. */
397 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
398 enum region_kind get_kind () const FINAL OVERRIDE { return RK_CODE; }
399 };
400
401 } // namespace ana
402
403 template <>
404 template <>
405 inline bool
406 is_a_helper <const code_region *>::test (const region *reg)
407 {
408 return reg->get_kind () == RK_CODE;
409 }
410
411 namespace ana {
412
413 /* Concrete region subclass. A region representing the code for
414 a particular function. */
415
416 class function_region : public region
417 {
418 public:
419 function_region (unsigned id, const code_region *parent, tree fndecl)
420 : region (complexity (parent), id, parent, TREE_TYPE (fndecl)),
421 m_fndecl (fndecl)
422 {
423 gcc_assert (FUNC_OR_METHOD_TYPE_P (TREE_TYPE (fndecl)));
424 }
425
426 /* region vfuncs. */
427 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
428 enum region_kind get_kind () const FINAL OVERRIDE { return RK_FUNCTION; }
429 const function_region *
430 dyn_cast_function_region () const FINAL OVERRIDE{ return this; }
431
432 tree get_fndecl () const { return m_fndecl; }
433
434 private:
435 tree m_fndecl;
436 };
437
438 } // namespace ana
439
440 template <>
441 template <>
442 inline bool
443 is_a_helper <const function_region *>::test (const region *reg)
444 {
445 return reg->get_kind () == RK_FUNCTION;
446 }
447
448 namespace ana {
449
450 /* Concrete region subclass. A region representing a particular label
451 within a function. */
452
453 class label_region : public region
454 {
455 public:
456 label_region (unsigned id, const function_region *parent, tree label)
457 : region (complexity (parent), id, parent, NULL_TREE), m_label (label)
458 {
459 gcc_assert (TREE_CODE (label) == LABEL_DECL);
460 }
461
462 /* region vfuncs. */
463 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
464 enum region_kind get_kind () const FINAL OVERRIDE { return RK_LABEL; }
465
466 tree get_label () const { return m_label; }
467
468 private:
469 tree m_label;
470 };
471
472 } // namespace ana
473
474 template <>
475 template <>
476 inline bool
477 is_a_helper <const label_region *>::test (const region *reg)
478 {
479 return reg->get_kind () == RK_LABEL;
480 }
481
482 namespace ana {
483
484 /* Concrete space_region subclass representing a stack, containing all stack
485 frames. */
486
487 class stack_region : public space_region
488 {
489 public:
490 stack_region (unsigned id, region *parent)
491 : space_region (id, parent)
492 {}
493
494 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
495
496 enum region_kind get_kind () const FINAL OVERRIDE { return RK_STACK; }
497 };
498
499 } // namespace ana
500
501 template <>
502 template <>
503 inline bool
504 is_a_helper <const stack_region *>::test (const region *reg)
505 {
506 return reg->get_kind () == RK_STACK;
507 }
508
509 namespace ana {
510
511 /* Concrete space_region subclass: a region within which regions can be
512 dynamically allocated. */
513
514 class heap_region : public space_region
515 {
516 public:
517 heap_region (unsigned id, region *parent)
518 : space_region (id, parent)
519 {}
520
521 enum region_kind get_kind () const FINAL OVERRIDE { return RK_HEAP; }
522 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
523 };
524
525 } // namespace ana
526
527 template <>
528 template <>
529 inline bool
530 is_a_helper <const heap_region *>::test (const region *reg)
531 {
532 return reg->get_kind () == RK_HEAP;
533 }
534
535 namespace ana {
536
537 /* Concrete region subclass. The root region, containing all regions
538 (either directly, or as descendents).
539 Unique within a region_model_manager. */
540
541 class root_region : public region
542 {
543 public:
544 root_region (unsigned id);
545
546 enum region_kind get_kind () const FINAL OVERRIDE { return RK_ROOT; }
547 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
548 };
549
550 } // namespace ana
551
552 template <>
553 template <>
554 inline bool
555 is_a_helper <const root_region *>::test (const region *reg)
556 {
557 return reg->get_kind () == RK_ROOT;
558 }
559
560 namespace ana {
561
562 /* Concrete region subclass: a region to use when dereferencing an unknown
563 pointer. */
564
565 class symbolic_region : public region
566 {
567 public:
568 /* A support class for uniquifying instances of symbolic_region. */
569 struct key_t
570 {
571 key_t (const region *parent, const svalue *sval_ptr)
572 : m_parent (parent), m_sval_ptr (sval_ptr)
573 {
574 gcc_assert (sval_ptr);
575 }
576
577 hashval_t hash () const
578 {
579 inchash::hash hstate;
580 hstate.add_ptr (m_parent);
581 hstate.add_ptr (m_sval_ptr);
582 return hstate.end ();
583 }
584
585 bool operator== (const key_t &other) const
586 {
587 return (m_parent == other.m_parent && m_sval_ptr == other.m_sval_ptr);
588 }
589
590 void mark_deleted () { m_sval_ptr = reinterpret_cast<const svalue *> (1); }
591 void mark_empty () { m_sval_ptr = NULL; }
592 bool is_deleted () const
593 {
594 return m_sval_ptr == reinterpret_cast<const svalue *> (1);
595 }
596 bool is_empty () const { return m_sval_ptr == NULL; }
597
598 const region *m_parent;
599 const svalue *m_sval_ptr;
600 };
601
602 symbolic_region (unsigned id, region *parent, const svalue *sval_ptr);
603
604 const symbolic_region *
605 dyn_cast_symbolic_region () const FINAL OVERRIDE { return this; }
606
607 enum region_kind get_kind () const FINAL OVERRIDE { return RK_SYMBOLIC; }
608 void accept (visitor *v) const FINAL OVERRIDE;
609 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
610
611 const svalue *get_pointer () const { return m_sval_ptr; }
612
613 private:
614 const svalue *m_sval_ptr;
615 };
616
617 } // namespace ana
618
619 template <>
620 template <>
621 inline bool
622 is_a_helper <const symbolic_region *>::test (const region *reg)
623 {
624 return reg->get_kind () == RK_SYMBOLIC;
625 }
626
627 template <> struct default_hash_traits<symbolic_region::key_t>
628 : public member_function_hash_traits<symbolic_region::key_t>
629 {
630 static const bool empty_zero_p = true;
631 };
632
633 namespace ana {
634
635 /* Concrete region subclass representing the memory occupied by a
636 variable (whether for a global or a local).
637 Also used for representing SSA names, as if they were locals. */
638
639 class decl_region : public region
640 {
641 public:
642 decl_region (unsigned id, const region *parent, tree decl)
643 : region (complexity (parent), id, parent, TREE_TYPE (decl)), m_decl (decl),
644 m_tracked (calc_tracked_p (decl))
645 {}
646
647 enum region_kind get_kind () const FINAL OVERRIDE { return RK_DECL; }
648 const decl_region *
649 dyn_cast_decl_region () const FINAL OVERRIDE { return this; }
650
651 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
652
653 bool tracked_p () const FINAL OVERRIDE { return m_tracked; }
654
655 tree get_decl () const { return m_decl; }
656 int get_stack_depth () const;
657
658 const svalue *maybe_get_constant_value (region_model_manager *mgr) const;
659 const svalue *get_svalue_for_constructor (tree ctor,
660 region_model_manager *mgr) const;
661 const svalue *get_svalue_for_initializer (region_model_manager *mgr) const;
662
663 private:
664 static bool calc_tracked_p (tree decl);
665
666 tree m_decl;
667
668 /* Cached result of calc_tracked_p, so that we can quickly determine when
669 we don't to track a binding_cluster for this decl (to avoid bloating
670 store objects).
671 This can be debugged using -fdump-analyzer-untracked. */
672 bool m_tracked;
673 };
674
675 } // namespace ana
676
677 template <>
678 template <>
679 inline bool
680 is_a_helper <const decl_region *>::test (const region *reg)
681 {
682 return reg->get_kind () == RK_DECL;
683 }
684
685 namespace ana {
686
687 /* Concrete region subclass representing the memory occupied by a
688 field within a struct or union. */
689
690 class field_region : public region
691 {
692 public:
693 /* A support class for uniquifying instances of field_region. */
694 struct key_t
695 {
696 key_t (const region *parent, tree field)
697 : m_parent (parent), m_field (field)
698 {
699 gcc_assert (field);
700 }
701
702 hashval_t hash () const
703 {
704 inchash::hash hstate;
705 hstate.add_ptr (m_parent);
706 hstate.add_ptr (m_field);
707 return hstate.end ();
708 }
709
710 bool operator== (const key_t &other) const
711 {
712 return (m_parent == other.m_parent && m_field == other.m_field);
713 }
714
715 void mark_deleted () { m_field = reinterpret_cast<tree> (1); }
716 void mark_empty () { m_field = NULL_TREE; }
717 bool is_deleted () const { return m_field == reinterpret_cast<tree> (1); }
718 bool is_empty () const { return m_field == NULL_TREE; }
719
720 const region *m_parent;
721 tree m_field;
722 };
723
724 field_region (unsigned id, const region *parent, tree field)
725 : region (complexity (parent), id, parent, TREE_TYPE (field)),
726 m_field (field)
727 {}
728
729 enum region_kind get_kind () const FINAL OVERRIDE { return RK_FIELD; }
730
731 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
732 const field_region *
733 dyn_cast_field_region () const FINAL OVERRIDE { return this; }
734
735 tree get_field () const { return m_field; }
736
737 bool get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
738
739 private:
740 tree m_field;
741 };
742
743 } // namespace ana
744
745 template <>
746 template <>
747 inline bool
748 is_a_helper <const field_region *>::test (const region *reg)
749 {
750 return reg->get_kind () == RK_FIELD;
751 }
752
753 template <> struct default_hash_traits<field_region::key_t>
754 : public member_function_hash_traits<field_region::key_t>
755 {
756 static const bool empty_zero_p = true;
757 };
758
759 namespace ana {
760
761 /* An element within an array. */
762
763 class element_region : public region
764 {
765 public:
766 /* A support class for uniquifying instances of element_region. */
767 struct key_t
768 {
769 key_t (const region *parent, tree element_type, const svalue *index)
770 : m_parent (parent), m_element_type (element_type), m_index (index)
771 {
772 gcc_assert (index);
773 }
774
775 hashval_t hash () const
776 {
777 inchash::hash hstate;
778 hstate.add_ptr (m_parent);
779 hstate.add_ptr (m_element_type);
780 hstate.add_ptr (m_index);
781 return hstate.end ();
782 }
783
784 bool operator== (const key_t &other) const
785 {
786 return (m_parent == other.m_parent
787 && m_element_type == other.m_element_type
788 && m_index == other.m_index);
789 }
790
791 void mark_deleted () { m_index = reinterpret_cast<const svalue *> (1); }
792 void mark_empty () { m_index = NULL; }
793 bool is_deleted () const
794 {
795 return m_index == reinterpret_cast<const svalue *> (1);
796 }
797 bool is_empty () const { return m_index == NULL; }
798
799 const region *m_parent;
800 tree m_element_type;
801 const svalue *m_index;
802 };
803
804 element_region (unsigned id, const region *parent, tree element_type,
805 const svalue *index)
806 : region (complexity::from_pair (parent, index), id, parent, element_type),
807 m_index (index)
808 {}
809
810 enum region_kind get_kind () const FINAL OVERRIDE { return RK_ELEMENT; }
811 const element_region *
812 dyn_cast_element_region () const FINAL OVERRIDE { return this; }
813
814 void accept (visitor *v) const FINAL OVERRIDE;
815
816 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
817
818 const svalue *get_index () const { return m_index; }
819
820 virtual bool
821 get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
822
823 private:
824 const svalue *m_index;
825 };
826
827 } // namespace ana
828
829 template <>
830 template <>
831 inline bool
832 is_a_helper <const element_region *>::test (const region *reg)
833 {
834 return reg->get_kind () == RK_ELEMENT;
835 }
836
837 template <> struct default_hash_traits<element_region::key_t>
838 : public member_function_hash_traits<element_region::key_t>
839 {
840 static const bool empty_zero_p = true;
841 };
842
843 namespace ana {
844
845 /* A byte-offset within another region, for handling pointer arithmetic
846 as a region. */
847
848 class offset_region : public region
849 {
850 public:
851 /* A support class for uniquifying instances of offset_region. */
852 struct key_t
853 {
854 key_t (const region *parent, tree element_type, const svalue *byte_offset)
855 : m_parent (parent), m_element_type (element_type), m_byte_offset (byte_offset)
856 {
857 gcc_assert (byte_offset);
858 }
859
860 hashval_t hash () const
861 {
862 inchash::hash hstate;
863 hstate.add_ptr (m_parent);
864 hstate.add_ptr (m_element_type);
865 hstate.add_ptr (m_byte_offset);
866 return hstate.end ();
867 }
868
869 bool operator== (const key_t &other) const
870 {
871 return (m_parent == other.m_parent
872 && m_element_type == other.m_element_type
873 && m_byte_offset == other.m_byte_offset);
874 }
875
876 void mark_deleted () { m_byte_offset = reinterpret_cast<const svalue *> (1); }
877 void mark_empty () { m_byte_offset = NULL; }
878 bool is_deleted () const
879 {
880 return m_byte_offset == reinterpret_cast<const svalue *> (1);
881 }
882 bool is_empty () const { return m_byte_offset == NULL; }
883
884 const region *m_parent;
885 tree m_element_type;
886 const svalue *m_byte_offset;
887 };
888
889 offset_region (unsigned id, const region *parent, tree type,
890 const svalue *byte_offset)
891 : region (complexity::from_pair (parent, byte_offset), id, parent, type),
892 m_byte_offset (byte_offset)
893 {}
894
895 enum region_kind get_kind () const FINAL OVERRIDE { return RK_OFFSET; }
896 const offset_region *
897 dyn_cast_offset_region () const FINAL OVERRIDE { return this; }
898
899 void accept (visitor *v) const FINAL OVERRIDE;
900
901 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
902
903 const svalue *get_byte_offset () const { return m_byte_offset; }
904
905 bool get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
906
907 private:
908 const svalue *m_byte_offset;
909 };
910
911 } // namespace ana
912
913 template <>
914 template <>
915 inline bool
916 is_a_helper <const offset_region *>::test (const region *reg)
917 {
918 return reg->get_kind () == RK_OFFSET;
919 }
920
921 template <> struct default_hash_traits<offset_region::key_t>
922 : public member_function_hash_traits<offset_region::key_t>
923 {
924 static const bool empty_zero_p = true;
925 };
926
927 namespace ana {
928
929 /* A region that is size BYTES_SIZE_SVAL in size within its parent
930 region (or possibly larger, which would lead to an overflow. */
931
932 class sized_region : public region
933 {
934 public:
935 /* A support class for uniquifying instances of sized_region. */
936 struct key_t
937 {
938 key_t (const region *parent, tree element_type,
939 const svalue *byte_size_sval)
940 : m_parent (parent), m_element_type (element_type),
941 m_byte_size_sval (byte_size_sval)
942 {
943 gcc_assert (byte_size_sval);
944 }
945
946 hashval_t hash () const
947 {
948 inchash::hash hstate;
949 hstate.add_ptr (m_parent);
950 hstate.add_ptr (m_element_type);
951 hstate.add_ptr (m_byte_size_sval);
952 return hstate.end ();
953 }
954
955 bool operator== (const key_t &other) const
956 {
957 return (m_parent == other.m_parent
958 && m_element_type == other.m_element_type
959 && m_byte_size_sval == other.m_byte_size_sval);
960 }
961
962 void mark_deleted () { m_byte_size_sval = reinterpret_cast<const svalue *> (1); }
963 void mark_empty () { m_byte_size_sval = NULL; }
964 bool is_deleted () const
965 {
966 return m_byte_size_sval == reinterpret_cast<const svalue *> (1);
967 }
968 bool is_empty () const { return m_byte_size_sval == NULL; }
969
970 const region *m_parent;
971 tree m_element_type;
972 const svalue *m_byte_size_sval;
973 const svalue *m_end_offset;
974 };
975
976 sized_region (unsigned id, const region *parent, tree type,
977 const svalue *byte_size_sval)
978 : region (complexity::from_pair (parent, byte_size_sval),
979 id, parent, type),
980 m_byte_size_sval (byte_size_sval)
981 {}
982
983 enum region_kind get_kind () const FINAL OVERRIDE { return RK_SIZED; }
984 const sized_region *
985 dyn_cast_sized_region () const FINAL OVERRIDE { return this; }
986
987 void accept (visitor *v) const FINAL OVERRIDE;
988
989 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
990
991 bool get_byte_size (byte_size_t *out) const FINAL OVERRIDE;
992 bool get_bit_size (bit_size_t *out) const FINAL OVERRIDE;
993
994 const svalue *
995 get_byte_size_sval (region_model_manager *) const FINAL OVERRIDE
996 {
997 return m_byte_size_sval;
998 }
999
1000 private:
1001 const svalue *m_byte_size_sval;
1002 };
1003
1004 } // namespace ana
1005
1006 template <>
1007 template <>
1008 inline bool
1009 is_a_helper <const sized_region *>::test (const region *reg)
1010 {
1011 return reg->get_kind () == RK_SIZED;
1012 }
1013
1014 template <> struct default_hash_traits<sized_region::key_t>
1015 : public member_function_hash_traits<sized_region::key_t>
1016 {
1017 static const bool empty_zero_p = true;
1018 };
1019
1020 namespace ana {
1021
1022 /* A region that views another region using a different type. */
1023
1024 class cast_region : public region
1025 {
1026 public:
1027 /* A support class for uniquifying instances of cast_region. */
1028 struct key_t
1029 {
1030 key_t (const region *original_region, tree type)
1031 : m_original_region (original_region), m_type (type)
1032 {
1033 gcc_assert (type);
1034 }
1035
1036 hashval_t hash () const
1037 {
1038 inchash::hash hstate;
1039 hstate.add_ptr (m_original_region);
1040 hstate.add_ptr (m_type);
1041 return hstate.end ();
1042 }
1043
1044 bool operator== (const key_t &other) const
1045 {
1046 return (m_original_region == other.m_original_region
1047 && m_type == other.m_type);
1048 }
1049
1050 void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1051 void mark_empty () { m_type = NULL_TREE; }
1052 bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1053 bool is_empty () const { return m_type == NULL_TREE; }
1054
1055 const region *m_original_region;
1056 tree m_type;
1057 };
1058
1059 cast_region (unsigned id, const region *original_region, tree type)
1060 : region (complexity (original_region), id,
1061 original_region->get_parent_region (), type),
1062 m_original_region (original_region)
1063 {}
1064
1065 enum region_kind get_kind () const FINAL OVERRIDE { return RK_CAST; }
1066 const cast_region *
1067 dyn_cast_cast_region () const FINAL OVERRIDE { return this; }
1068 void accept (visitor *v) const FINAL OVERRIDE;
1069 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1070
1071 const region *get_original_region () const { return m_original_region; }
1072
1073 private:
1074 const region *m_original_region;
1075 };
1076
1077 } // namespace ana
1078
1079 template <>
1080 template <>
1081 inline bool
1082 is_a_helper <const cast_region *>::test (const region *reg)
1083 {
1084 return reg->get_kind () == RK_CAST;
1085 }
1086
1087 template <> struct default_hash_traits<cast_region::key_t>
1088 : public member_function_hash_traits<cast_region::key_t>
1089 {
1090 static const bool empty_zero_p = true;
1091 };
1092
1093 namespace ana {
1094
1095 /* An untyped region dynamically allocated on the heap via "malloc"
1096 or similar. */
1097
1098 class heap_allocated_region : public region
1099 {
1100 public:
1101 heap_allocated_region (unsigned id, const region *parent)
1102 : region (complexity (parent), id, parent, NULL_TREE)
1103 {}
1104
1105 enum region_kind
1106 get_kind () const FINAL OVERRIDE { return RK_HEAP_ALLOCATED; }
1107
1108 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1109 };
1110
1111 /* An untyped region dynamically allocated on the stack via "alloca". */
1112
1113 class alloca_region : public region
1114 {
1115 public:
1116 alloca_region (unsigned id, const frame_region *parent)
1117 : region (complexity (parent), id, parent, NULL_TREE)
1118 {}
1119
1120 enum region_kind get_kind () const FINAL OVERRIDE { return RK_ALLOCA; }
1121
1122 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1123 };
1124
1125 /* A region for a STRING_CST. */
1126
1127 class string_region : public region
1128 {
1129 public:
1130 string_region (unsigned id, const region *parent, tree string_cst)
1131 : region (complexity (parent), id, parent, TREE_TYPE (string_cst)),
1132 m_string_cst (string_cst)
1133 {}
1134
1135 const string_region *
1136 dyn_cast_string_region () const FINAL OVERRIDE { return this; }
1137
1138 enum region_kind get_kind () const FINAL OVERRIDE { return RK_STRING; }
1139
1140 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1141
1142 tree get_string_cst () const { return m_string_cst; }
1143
1144 private:
1145 tree m_string_cst;
1146 };
1147
1148 } // namespace ana
1149
1150 template <>
1151 template <>
1152 inline bool
1153 is_a_helper <const string_region *>::test (const region *reg)
1154 {
1155 return reg->get_kind () == RK_STRING;
1156 }
1157
1158 namespace ana {
1159
1160 /* A region for a specific range of bits within another region. */
1161
1162 class bit_range_region : public region
1163 {
1164 public:
1165 /* A support class for uniquifying instances of bit_range_region. */
1166 struct key_t
1167 {
1168 key_t (const region *parent, tree type, const bit_range &bits)
1169 : m_parent (parent), m_type (type), m_bits (bits)
1170 {
1171 gcc_assert (parent);
1172 }
1173
1174 hashval_t hash () const
1175 {
1176 inchash::hash hstate;
1177 hstate.add_ptr (m_parent);
1178 hstate.add_ptr (m_type);
1179 hstate.add_wide_int (m_bits.m_start_bit_offset);
1180 hstate.add_wide_int (m_bits.m_size_in_bits);
1181 return hstate.end ();
1182 }
1183
1184 bool operator== (const key_t &other) const
1185 {
1186 return (m_parent == other.m_parent
1187 && m_type == other.m_type
1188 && m_bits == other.m_bits);
1189 }
1190
1191 void mark_deleted () { m_parent = reinterpret_cast<const region *> (1); }
1192 void mark_empty () { m_parent = NULL; }
1193 bool is_deleted () const
1194 {
1195 return m_parent == reinterpret_cast<const region *> (1);
1196 }
1197 bool is_empty () const { return m_parent == NULL; }
1198
1199 const region *m_parent;
1200 tree m_type;
1201 bit_range m_bits;
1202 };
1203
1204 bit_range_region (unsigned id, const region *parent, tree type,
1205 const bit_range &bits)
1206 : region (complexity (parent), id, parent, type),
1207 m_bits (bits)
1208 {}
1209
1210 const bit_range_region *
1211 dyn_cast_bit_range_region () const FINAL OVERRIDE { return this; }
1212
1213 enum region_kind get_kind () const FINAL OVERRIDE { return RK_BIT_RANGE; }
1214
1215 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1216
1217 const bit_range &get_bits () const { return m_bits; }
1218
1219 bool get_byte_size (byte_size_t *out) const FINAL OVERRIDE;
1220 bool get_bit_size (bit_size_t *out) const FINAL OVERRIDE;
1221 const svalue *get_byte_size_sval (region_model_manager *mgr) const FINAL OVERRIDE;
1222 bool get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
1223
1224 private:
1225 bit_range m_bits;
1226 };
1227
1228 } // namespace ana
1229
1230 template <>
1231 template <>
1232 inline bool
1233 is_a_helper <const bit_range_region *>::test (const region *reg)
1234 {
1235 return reg->get_kind () == RK_BIT_RANGE;
1236 }
1237
1238 template <> struct default_hash_traits<bit_range_region::key_t>
1239 : public member_function_hash_traits<bit_range_region::key_t>
1240 {
1241 static const bool empty_zero_p = true;
1242 };
1243
1244 namespace ana {
1245
1246 /* An unknown region, for handling unimplemented tree codes. */
1247
1248 class unknown_region : public region
1249 {
1250 public:
1251 unknown_region (unsigned id, const region *parent, tree type)
1252 : region (complexity (parent), id, parent, type)
1253 {}
1254
1255 enum region_kind get_kind () const FINAL OVERRIDE { return RK_UNKNOWN; }
1256
1257 void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1258 };
1259
1260 } // namespace ana
1261
1262 #endif /* GCC_ANALYZER_REGION_H */
1263