gcc/analyzer/region.h

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