gcc/analyzer/region.h

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