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