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