gcc/analyzer/region.h

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