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

source code of gcc/analyzer/region.h