gcc/analyzer/region.h

   1 /* Regions of memory.
   2    Copyright (C) 2019-2021 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_UNKNOWN
  64 };
  65
  66 /* Region and its subclasses.
  67
  68    The class hierarchy looks like this (using indentation to show
  69    inheritance, and with region_kinds shown for the concrete subclasses):
  70
  71    region
  72      space_region
  73        frame_region (RK_FRAME)
  74        globals_region (RK_GLOBALS)
  75        code_region (RK_CODE)
  76        stack_region (RK_STACK)
  77        heap_region (RK_HEAP)
  78      root_region (RK_ROOT)
  79      function_region (RK_FUNCTION)
  80      label_region (RK_LABEL)
  81      symbolic_region (RK_SYMBOLIC)
  82      decl_region (RK_DECL),
  83      field_region (RK_FIELD)
  84      element_region (RK_ELEMENT)
  85      offset_region (RK_OFFSET)
  86      sized_region (RK_SIZED)
  87      cast_region (RK_CAST)
  88      heap_allocated_region (RK_HEAP_ALLOCATED)
  89      alloca_region (RK_ALLOCA)
  90      string_region (RK_STRING)
  91      unknown_region (RK_UNKNOWN).  */
  92
  93 /* Abstract base class for representing ways of accessing chunks of memory.
  94
  95    Regions form a tree-like hierarchy, with a root region at the base,
  96    with memory space regions within it, representing the stack and
  97    globals, with frames within the stack, and regions for variables
  98    within the frames and the "globals" region.  Regions for structs
  99    can have subregions for fields.  */
 100
 101 class region
 102 {
 103 public:
 104   virtual ~region ();
 105
 106   unsigned get_id () const { return m_id; }
 107   static int cmp_ids (const region *reg1, const region *reg2);
 108
 109   virtual enum region_kind get_kind () const = 0;
 110   virtual const frame_region *
 111   dyn_cast_frame_region () const { return NULL; }
 112   virtual const function_region *
 113   dyn_cast_function_region () const { return NULL; }
 114   virtual const symbolic_region *
 115   dyn_cast_symbolic_region () const { return NULL; }
 116   virtual const decl_region *
 117   dyn_cast_decl_region () const { return NULL; }
 118   virtual const field_region *
 119   dyn_cast_field_region () const { return NULL; }
 120   virtual const element_region *
 121   dyn_cast_element_region () const { return NULL; }
 122   virtual const offset_region *
 123   dyn_cast_offset_region () const { return NULL; }
 124   virtual const sized_region *
 125   dyn_cast_sized_region () const { return NULL; }
 126   virtual const cast_region *
 127   dyn_cast_cast_region () const { return NULL; }
 128   virtual const string_region *
 129   dyn_cast_string_region () const { return NULL; }
 130
 131   virtual void accept (visitor *v) const;
 132
 133   const region *get_parent_region () const { return m_parent; }
 134   const region *get_base_region () const;
 135   bool base_region_p () const;
 136   bool descendent_of_p (const region *elder) const;
 137   const frame_region *maybe_get_frame_region () const;
 138   enum memory_space get_memory_space () const;
 139   bool can_have_initial_svalue_p () const;
 140
 141   tree maybe_get_decl () const;
 142
 143   tree get_type () const { return m_type; }
 144
 145   void print (const region_model &model,
 146               pretty_printer *pp) const;
 147   label_text get_desc (bool simple=true) const;
 148
 149   virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
 150   void dump (bool simple) const;
 151
 152   json::value *to_json () const;
 153
 154   bool non_null_p () const;
 155
 156   static int cmp_ptr_ptr (const void *, const void *);
 157
 158   bool involves_p (const svalue *sval) const;
 159
 160   region_offset get_offset () const;
 161
 162   /* Attempt to get the size of this region as a concrete number of bytes.
 163      If successful, return true and write the size to *OUT.
 164      Otherwise return false.  */
 165   virtual bool get_byte_size (byte_size_t *out) const;
 166
 167   /* Attempt to get the size of this region as a concrete number of bits.
 168      If successful, return true and write the size to *OUT.
 169      Otherwise return false.  */
 170   virtual bool get_bit_size (bit_size_t *out) const;
 171
 172   /* Get a symbolic value describing the size of this region in bytes
 173      (which could be "unknown").  */
 174   virtual const svalue *get_byte_size_sval (region_model_manager *mgr) const;
 175
 176   /* Attempt to get the offset in bits of this region relative to its parent.
 177      If successful, return true and write to *OUT.
 178      Otherwise return false.  */
 179   virtual bool get_relative_concrete_offset (bit_offset_t *out) const;
 180
 181   void
 182   get_subregions_for_binding (region_model_manager *mgr,
 183                               bit_offset_t start_bit_offset,
 184                               bit_size_t size_in_bits,
 185                               tree type,
 186                               auto_vec <const region *> *out) const;
 187
 188   bool symbolic_for_unknown_ptr_p () const;
 189
 190   const complexity &get_complexity () const { return m_complexity; }
 191
 192  protected:
 193   region (complexity c, unsigned id, const region *parent, tree type);
 194
 195  private:
 196   region_offset calc_offset () const;
 197
 198   complexity m_complexity;
 199   unsigned m_id; // purely for deterministic sorting at this stage, for dumps
 200   const region *m_parent;
 201   tree m_type;
 202
 203   mutable region_offset *m_cached_offset;
 204 };
 205
 206 } // namespace ana
 207
 208 template <>
 209 template <>
 210 inline bool
 211 is_a_helper <const region *>::test (const region *)
 212 {
 213   return true;
 214 }
 215
 216 namespace ana {
 217
 218 /* Abstract subclass of region, for regions that represent an untyped
 219    space within memory, such as the stack or the heap.  */
 220
 221 class space_region : public region
 222 {
 223 protected:
 224   space_region (unsigned id, const region *parent)
 225   : region (complexity (parent), id, parent, NULL_TREE)
 226   {}
 227 };
 228
 229 /* Concrete space_region subclass, representing a function frame on the stack,
 230    to contain the locals.
 231    The parent is the stack region; there's also a hierarchy of call-stack
 232    prefixes expressed via m_calling_frame.
 233    For example, given "oldest" calling "middle" called "newest" we would have
 234    - a stack depth of 3
 235    - frame (A) for "oldest" with index 0 for depth 1, calling_frame == NULL
 236    - frame (B) for "middle" with index 1 for depth 2, calling_frame == (A)
 237    - frame (C) for "newest" with index 2 for depth 3, calling_frame == (B)
 238    where the parent region for each of the frames is the "stack" region.
 239    The index is the count of frames earlier than this in the stack.  */
 240
 241 class frame_region : public space_region
 242 {
 243 public:
 244   /* A support class for uniquifying instances of frame_region.  */
 245   struct key_t
 246   {
 247     key_t (const frame_region *calling_frame, function *fun)
 248     : m_calling_frame (calling_frame), m_fun (fun)
 249     {
 250       /* calling_frame can be NULL.  */
 251       gcc_assert (fun);
 252     }
 253
 254     hashval_t hash () const
 255     {
 256       inchash::hash hstate;
 257       hstate.add_ptr (m_calling_frame);
 258       hstate.add_ptr (m_fun);
 259       return hstate.end ();
 260     }
 261
 262     bool operator== (const key_t &other) const
 263     {
 264       return (m_calling_frame == other.m_calling_frame && m_fun == other.m_fun);
 265     }
 266
 267     void mark_deleted () { m_fun = reinterpret_cast<function *> (1); }
 268     void mark_empty () { m_fun = NULL; }
 269     bool is_deleted () const
 270     {
 271       return m_fun == reinterpret_cast<function *> (1);
 272     }
 273     bool is_empty () const { return m_fun == NULL; }
 274
 275     const frame_region *m_calling_frame;
 276     function *m_fun;
 277   };
 278
 279   frame_region (unsigned id, const region *parent,
 280                 const frame_region *calling_frame,
 281                 function *fun, int index)
 282   : space_region (id, parent), m_calling_frame (calling_frame),
 283     m_fun (fun), m_index (index)
 284   {}
 285   ~frame_region ();
 286
 287   /* region vfuncs.  */
 288   enum region_kind get_kind () const FINAL OVERRIDE { return RK_FRAME; }
 289   const frame_region * dyn_cast_frame_region () const FINAL OVERRIDE
 290   {
 291     return this;
 292   }
 293   void accept (visitor *v) const FINAL OVERRIDE;
 294   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 295
 296   /* Accessors.  */
 297   const frame_region *get_calling_frame () const { return m_calling_frame; }
 298   function *get_function () const { return m_fun; }
 299   int get_index () const { return m_index; }
 300   int get_stack_depth () const { return m_index + 1; }
 301
 302   const decl_region *get_region_for_local (region_model_manager *mgr,
 303                                            tree expr) const;
 304
 305   unsigned get_num_locals () const { return m_locals.elements (); }
 306
 307  private:
 308   const frame_region *m_calling_frame;
 309   function *m_fun;
 310   int m_index;
 311
 312   /* The regions for the decls within this frame are managed by this
 313      object, rather than the region_model_manager, to make it a simple
 314      lookup by tree.  */
 315   typedef hash_map<tree, decl_region *> map_t;
 316   map_t m_locals;
 317 };
 318
 319 } // namespace ana
 320
 321 template <>
 322 template <>
 323 inline bool
 324 is_a_helper <const frame_region *>::test (const region *reg)
 325 {
 326   return reg->get_kind () == RK_FRAME;
 327 }
 328
 329 template <> struct default_hash_traits<frame_region::key_t>
 330 : public member_function_hash_traits<frame_region::key_t>
 331 {
 332   static const bool empty_zero_p = true;
 333 };
 334
 335 namespace ana {
 336
 337 /* Concrete space_region subclass, to hold global variables (data and bss).  */
 338
 339 class globals_region : public space_region
 340 {
 341  public:
 342   globals_region (unsigned id, const region *parent)
 343   : space_region (id, parent)
 344   {}
 345
 346   /* region vfuncs.  */
 347   enum region_kind get_kind () const FINAL OVERRIDE { return RK_GLOBALS; }
 348   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 349 };
 350
 351 } // namespace ana
 352
 353 template <>
 354 template <>
 355 inline bool
 356 is_a_helper <const globals_region *>::test (const region *reg)
 357 {
 358   return reg->get_kind () == RK_GLOBALS;
 359 }
 360
 361 namespace ana {
 362
 363 /* Concrete space_region subclass, representing the code segment
 364    containing functions.  */
 365
 366 class code_region : public space_region
 367 {
 368 public:
 369   code_region (unsigned id, const region *parent)
 370   : space_region (id, parent)
 371   {}
 372
 373   /* region vfuncs.  */
 374   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 375   enum region_kind get_kind () const FINAL OVERRIDE { return RK_CODE; }
 376
 377   const region *get_element (region_model *model,
 378                         const svalue *index,
 379                         region_model_context *ctxt);
 380 };
 381
 382 } // namespace ana
 383
 384 template <>
 385 template <>
 386 inline bool
 387 is_a_helper <const code_region *>::test (const region *reg)
 388 {
 389   return reg->get_kind () == RK_CODE;
 390 }
 391
 392 namespace ana {
 393
 394 /* Concrete region subclass.  A region representing the code for
 395    a particular function.  */
 396
 397 class function_region : public region
 398 {
 399 public:
 400   function_region (unsigned id, const code_region *parent, tree fndecl)
 401   : region (complexity (parent), id, parent, TREE_TYPE (fndecl)),
 402     m_fndecl (fndecl)
 403   {
 404     gcc_assert (FUNC_OR_METHOD_TYPE_P (TREE_TYPE (fndecl)));
 405   }
 406
 407   /* region vfuncs.  */
 408   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 409   enum region_kind get_kind () const FINAL OVERRIDE { return RK_FUNCTION; }
 410   const function_region *
 411   dyn_cast_function_region () const FINAL OVERRIDE{ return this; }
 412
 413   tree get_fndecl () const { return m_fndecl; }
 414
 415   region *get_element (region_model *model,
 416                         const svalue *index_sid,
 417                         region_model_context *ctxt);
 418
 419 private:
 420   tree m_fndecl;
 421 };
 422
 423 } // namespace ana
 424
 425 template <>
 426 template <>
 427 inline bool
 428 is_a_helper <const function_region *>::test (const region *reg)
 429 {
 430   return reg->get_kind () == RK_FUNCTION;
 431 }
 432
 433 namespace ana {
 434
 435 /* Concrete region subclass.  A region representing a particular label
 436    within a function.  */
 437
 438 class label_region : public region
 439 {
 440 public:
 441   label_region (unsigned id, const function_region *parent, tree label)
 442   : region (complexity (parent), id, parent, NULL_TREE), m_label (label)
 443   {
 444     gcc_assert (TREE_CODE (label) == LABEL_DECL);
 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_LABEL; }
 450
 451   tree get_label () const { return m_label; }
 452
 453 private:
 454   tree m_label;
 455 };
 456
 457 } // namespace ana
 458
 459 template <>
 460 template <>
 461 inline bool
 462 is_a_helper <const label_region *>::test (const region *reg)
 463 {
 464   return reg->get_kind () == RK_LABEL;
 465 }
 466
 467 namespace ana {
 468
 469 /* Concrete space_region subclass representing a stack, containing all stack
 470    frames.  */
 471
 472 class stack_region : public space_region
 473 {
 474 public:
 475   stack_region (unsigned id, region *parent)
 476   : space_region (id, parent)
 477   {}
 478
 479   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 480
 481   enum region_kind get_kind () const FINAL OVERRIDE { return RK_STACK; }
 482 };
 483
 484 } // namespace ana
 485
 486 template <>
 487 template <>
 488 inline bool
 489 is_a_helper <const stack_region *>::test (const region *reg)
 490 {
 491   return reg->get_kind () == RK_STACK;
 492 }
 493
 494 namespace ana {
 495
 496 /* Concrete space_region subclass: a region within which regions can be
 497    dynamically allocated.  */
 498
 499 class heap_region : public space_region
 500 {
 501 public:
 502   heap_region (unsigned id, region *parent)
 503   : space_region (id, parent)
 504   {}
 505
 506   enum region_kind get_kind () const FINAL OVERRIDE { return RK_HEAP; }
 507   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 508 };
 509
 510 } // namespace ana
 511
 512 template <>
 513 template <>
 514 inline bool
 515 is_a_helper <const heap_region *>::test (const region *reg)
 516 {
 517   return reg->get_kind () == RK_HEAP;
 518 }
 519
 520 namespace ana {
 521
 522 /* Concrete region subclass.  The root region, containing all regions
 523    (either directly, or as descendents).
 524    Unique within a region_model_manager.  */
 525
 526 class root_region : public region
 527 {
 528 public:
 529   root_region (unsigned id);
 530
 531   enum region_kind get_kind () const FINAL OVERRIDE { return RK_ROOT; }
 532   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 533 };
 534
 535 } // namespace ana
 536
 537 template <>
 538 template <>
 539 inline bool
 540 is_a_helper <const root_region *>::test (const region *reg)
 541 {
 542   return reg->get_kind () == RK_ROOT;
 543 }
 544
 545 namespace ana {
 546
 547 /* Concrete region subclass: a region to use when dereferencing an unknown
 548    pointer.  */
 549
 550 class symbolic_region : public region
 551 {
 552 public:
 553   /* A support class for uniquifying instances of symbolic_region.  */
 554   struct key_t
 555   {
 556     key_t (const region *parent, const svalue *sval_ptr)
 557     : m_parent (parent), m_sval_ptr (sval_ptr)
 558     {
 559       gcc_assert (sval_ptr);
 560     }
 561
 562     hashval_t hash () const
 563     {
 564       inchash::hash hstate;
 565       hstate.add_ptr (m_parent);
 566       hstate.add_ptr (m_sval_ptr);
 567       return hstate.end ();
 568     }
 569
 570     bool operator== (const key_t &other) const
 571     {
 572       return (m_parent == other.m_parent && m_sval_ptr == other.m_sval_ptr);
 573     }
 574
 575     void mark_deleted () { m_sval_ptr = reinterpret_cast<const svalue *> (1); }
 576     void mark_empty () { m_sval_ptr = NULL; }
 577     bool is_deleted () const
 578     {
 579       return m_sval_ptr == reinterpret_cast<const svalue *> (1);
 580     }
 581     bool is_empty () const { return m_sval_ptr == NULL; }
 582
 583     const region *m_parent;
 584     const svalue *m_sval_ptr;
 585   };
 586
 587   symbolic_region (unsigned id, region *parent, const svalue *sval_ptr);
 588
 589   const symbolic_region *
 590   dyn_cast_symbolic_region () const FINAL OVERRIDE { return this; }
 591
 592   enum region_kind get_kind () const FINAL OVERRIDE { return RK_SYMBOLIC; }
 593   void accept (visitor *v) const FINAL OVERRIDE;
 594   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 595
 596   const svalue *get_pointer () const { return m_sval_ptr; }
 597
 598 private:
 599   const svalue *m_sval_ptr;
 600 };
 601
 602 } // namespace ana
 603
 604 template <>
 605 template <>
 606 inline bool
 607 is_a_helper <const symbolic_region *>::test (const region *reg)
 608 {
 609   return reg->get_kind () == RK_SYMBOLIC;
 610 }
 611
 612 template <> struct default_hash_traits<symbolic_region::key_t>
 613 : public member_function_hash_traits<symbolic_region::key_t>
 614 {
 615   static const bool empty_zero_p = true;
 616 };
 617
 618 namespace ana {
 619
 620 /* Concrete region subclass representing the memory occupied by a
 621    variable (whether for a global or a local).  */
 622
 623 class decl_region : public region
 624 {
 625 public:
 626   decl_region (unsigned id, const region *parent, tree decl)
 627   : region (complexity (parent), id, parent, TREE_TYPE (decl)), m_decl (decl)
 628   {}
 629
 630   enum region_kind get_kind () const FINAL OVERRIDE { return RK_DECL; }
 631   const decl_region *
 632   dyn_cast_decl_region () const FINAL OVERRIDE { return this; }
 633
 634   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 635
 636   tree get_decl () const { return m_decl; }
 637   int get_stack_depth () const;
 638
 639   const svalue *maybe_get_constant_value (region_model_manager *mgr) const;
 640   const svalue *get_svalue_for_constructor (tree ctor,
 641                                             region_model_manager *mgr) const;
 642   const svalue *get_svalue_for_initializer (region_model_manager *mgr) const;
 643
 644 private:
 645   tree m_decl;
 646 };
 647
 648 } // namespace ana
 649
 650 template <>
 651 template <>
 652 inline bool
 653 is_a_helper <const decl_region *>::test (const region *reg)
 654 {
 655   return reg->get_kind () == RK_DECL;
 656 }
 657
 658 namespace ana {
 659
 660 /* Concrete region subclass representing the memory occupied by a
 661    field within a struct or union.  */
 662
 663 class field_region : public region
 664 {
 665 public:
 666   /* A support class for uniquifying instances of field_region.  */
 667   struct key_t
 668   {
 669     key_t (const region *parent, tree field)
 670     : m_parent (parent), m_field (field)
 671     {
 672       gcc_assert (field);
 673     }
 674
 675     hashval_t hash () const
 676     {
 677       inchash::hash hstate;
 678       hstate.add_ptr (m_parent);
 679       hstate.add_ptr (m_field);
 680       return hstate.end ();
 681     }
 682
 683     bool operator== (const key_t &other) const
 684     {
 685       return (m_parent == other.m_parent && m_field == other.m_field);
 686     }
 687
 688     void mark_deleted () { m_field = reinterpret_cast<tree> (1); }
 689     void mark_empty () { m_field = NULL_TREE; }
 690     bool is_deleted () const { return m_field == reinterpret_cast<tree> (1); }
 691     bool is_empty () const { return m_field == NULL_TREE; }
 692
 693     const region *m_parent;
 694     tree m_field;
 695   };
 696
 697   field_region (unsigned id, const region *parent, tree field)
 698   : region (complexity (parent), id, parent, TREE_TYPE (field)),
 699     m_field (field)
 700   {}
 701
 702   enum region_kind get_kind () const FINAL OVERRIDE { return RK_FIELD; }
 703
 704   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 705   const field_region *
 706   dyn_cast_field_region () const FINAL OVERRIDE { return this; }
 707
 708   tree get_field () const { return m_field; }
 709
 710   bool get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
 711
 712 private:
 713   tree m_field;
 714 };
 715
 716 } // namespace ana
 717
 718 template <>
 719 template <>
 720 inline bool
 721 is_a_helper <const field_region *>::test (const region *reg)
 722 {
 723   return reg->get_kind () == RK_FIELD;
 724 }
 725
 726 template <> struct default_hash_traits<field_region::key_t>
 727 : public member_function_hash_traits<field_region::key_t>
 728 {
 729   static const bool empty_zero_p = true;
 730 };
 731
 732 namespace ana {
 733
 734 /* An element within an array.  */
 735
 736 class element_region : public region
 737 {
 738 public:
 739   /* A support class for uniquifying instances of element_region.  */
 740   struct key_t
 741   {
 742     key_t (const region *parent, tree element_type, const svalue *index)
 743     : m_parent (parent), m_element_type (element_type), m_index (index)
 744     {
 745       gcc_assert (index);
 746     }
 747
 748     hashval_t hash () const
 749     {
 750       inchash::hash hstate;
 751       hstate.add_ptr (m_parent);
 752       hstate.add_ptr (m_element_type);
 753       hstate.add_ptr (m_index);
 754       return hstate.end ();
 755     }
 756
 757     bool operator== (const key_t &other) const
 758     {
 759       return (m_parent == other.m_parent
 760               && m_element_type == other.m_element_type
 761               && m_index == other.m_index);
 762     }
 763
 764     void mark_deleted () { m_index = reinterpret_cast<const svalue *> (1); }
 765     void mark_empty () { m_index = NULL; }
 766     bool is_deleted () const
 767     {
 768       return m_index == reinterpret_cast<const svalue *> (1);
 769     }
 770     bool is_empty () const { return m_index == NULL; }
 771
 772     const region *m_parent;
 773     tree m_element_type;
 774     const svalue *m_index;
 775   };
 776
 777   element_region (unsigned id, const region *parent, tree element_type,
 778                   const svalue *index)
 779   : region (complexity::from_pair (parent, index), id, parent, element_type),
 780     m_index (index)
 781   {}
 782
 783   enum region_kind get_kind () const FINAL OVERRIDE { return RK_ELEMENT; }
 784   const element_region *
 785   dyn_cast_element_region () const FINAL OVERRIDE { return this; }
 786
 787   void accept (visitor *v) const FINAL OVERRIDE;
 788
 789   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 790
 791   const svalue *get_index () const { return m_index; }
 792
 793   virtual bool
 794   get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
 795
 796 private:
 797   const svalue *m_index;
 798 };
 799
 800 } // namespace ana
 801
 802 template <>
 803 template <>
 804 inline bool
 805 is_a_helper <const element_region *>::test (const region *reg)
 806 {
 807   return reg->get_kind () == RK_ELEMENT;
 808 }
 809
 810 template <> struct default_hash_traits<element_region::key_t>
 811 : public member_function_hash_traits<element_region::key_t>
 812 {
 813   static const bool empty_zero_p = true;
 814 };
 815
 816 namespace ana {
 817
 818 /* A byte-offset within another region, for handling pointer arithmetic
 819    as a region.  */
 820
 821 class offset_region : public region
 822 {
 823 public:
 824   /* A support class for uniquifying instances of offset_region.  */
 825   struct key_t
 826   {
 827     key_t (const region *parent, tree element_type, const svalue *byte_offset)
 828     : m_parent (parent), m_element_type (element_type), m_byte_offset (byte_offset)
 829     {
 830       gcc_assert (byte_offset);
 831     }
 832
 833     hashval_t hash () const
 834     {
 835       inchash::hash hstate;
 836       hstate.add_ptr (m_parent);
 837       hstate.add_ptr (m_element_type);
 838       hstate.add_ptr (m_byte_offset);
 839       return hstate.end ();
 840     }
 841
 842     bool operator== (const key_t &other) const
 843     {
 844       return (m_parent == other.m_parent
 845               && m_element_type == other.m_element_type
 846               && m_byte_offset == other.m_byte_offset);
 847     }
 848
 849     void mark_deleted () { m_byte_offset = reinterpret_cast<const svalue *> (1); }
 850     void mark_empty () { m_byte_offset = NULL; }
 851     bool is_deleted () const
 852     {
 853       return m_byte_offset == reinterpret_cast<const svalue *> (1);
 854     }
 855     bool is_empty () const { return m_byte_offset == NULL; }
 856
 857     const region *m_parent;
 858     tree m_element_type;
 859     const svalue *m_byte_offset;
 860   };
 861
 862   offset_region (unsigned id, const region *parent, tree type,
 863                  const svalue *byte_offset)
 864   : region (complexity::from_pair (parent, byte_offset), id, parent, type),
 865     m_byte_offset (byte_offset)
 866   {}
 867
 868   enum region_kind get_kind () const FINAL OVERRIDE { return RK_OFFSET; }
 869   const offset_region *
 870   dyn_cast_offset_region () const FINAL OVERRIDE { return this; }
 871
 872   void accept (visitor *v) const FINAL OVERRIDE;
 873
 874   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 875
 876   const svalue *get_byte_offset () const { return m_byte_offset; }
 877
 878   bool get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
 879
 880 private:
 881   const svalue *m_byte_offset;
 882 };
 883
 884 } // namespace ana
 885
 886 template <>
 887 template <>
 888 inline bool
 889 is_a_helper <const offset_region *>::test (const region *reg)
 890 {
 891   return reg->get_kind () == RK_OFFSET;
 892 }
 893
 894 template <> struct default_hash_traits<offset_region::key_t>
 895 : public member_function_hash_traits<offset_region::key_t>
 896 {
 897   static const bool empty_zero_p = true;
 898 };
 899
 900 namespace ana {
 901
 902 /* A region that is size BYTES_SIZE_SVAL in size within its parent
 903    region (or possibly larger, which would lead to an overflow.  */
 904
 905 class sized_region : public region
 906 {
 907 public:
 908   /* A support class for uniquifying instances of sized_region.  */
 909   struct key_t
 910   {
 911     key_t (const region *parent, tree element_type,
 912            const svalue *byte_size_sval)
 913       : m_parent (parent), m_element_type (element_type),
 914         m_byte_size_sval (byte_size_sval)
 915     {
 916       gcc_assert (byte_size_sval);
 917     }
 918
 919     hashval_t hash () const
 920     {
 921       inchash::hash hstate;
 922       hstate.add_ptr (m_parent);
 923       hstate.add_ptr (m_element_type);
 924       hstate.add_ptr (m_byte_size_sval);
 925       return hstate.end ();
 926     }
 927
 928     bool operator== (const key_t &other) const
 929     {
 930       return (m_parent == other.m_parent
 931               && m_element_type == other.m_element_type
 932               && m_byte_size_sval == other.m_byte_size_sval);
 933     }
 934
 935     void mark_deleted () { m_byte_size_sval = reinterpret_cast<const svalue *> (1); }
 936     void mark_empty () { m_byte_size_sval = NULL; }
 937     bool is_deleted () const
 938     {
 939       return m_byte_size_sval == reinterpret_cast<const svalue *> (1);
 940     }
 941     bool is_empty () const { return m_byte_size_sval == NULL; }
 942
 943     const region *m_parent;
 944     tree m_element_type;
 945     const svalue *m_byte_size_sval;
 946     const svalue *m_end_offset;
 947   };
 948
 949   sized_region (unsigned id, const region *parent, tree type,
 950                 const svalue *byte_size_sval)
 951   : region (complexity::from_pair (parent, byte_size_sval),
 952             id, parent, type),
 953     m_byte_size_sval (byte_size_sval)
 954   {}
 955
 956   enum region_kind get_kind () const FINAL OVERRIDE { return RK_SIZED; }
 957   const sized_region *
 958   dyn_cast_sized_region () const FINAL OVERRIDE { return this; }
 959
 960   void accept (visitor *v) const FINAL OVERRIDE;
 961
 962   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
 963
 964   bool get_byte_size (byte_size_t *out) const FINAL OVERRIDE;
 965   bool get_bit_size (bit_size_t *out) const FINAL OVERRIDE;
 966
 967   const svalue *
 968   get_byte_size_sval (region_model_manager *) const FINAL OVERRIDE
 969   {
 970     return m_byte_size_sval;
 971   }
 972
 973 private:
 974   const svalue *m_byte_size_sval;
 975 };
 976
 977 } // namespace ana
 978
 979 template <>
 980 template <>
 981 inline bool
 982 is_a_helper <const sized_region *>::test (const region *reg)
 983 {
 984   return reg->get_kind () == RK_SIZED;
 985 }
 986
 987 template <> struct default_hash_traits<sized_region::key_t>
 988 : public member_function_hash_traits<sized_region::key_t>
 989 {
 990   static const bool empty_zero_p = true;
 991 };
 992
 993 namespace ana {
 994
 995 /* A region that views another region using a different type.  */
 996
 997 class cast_region : public region
 998 {
 999 public:
1000   /* A support class for uniquifying instances of cast_region.  */
1001   struct key_t
1002   {
1003     key_t (const region *original_region, tree type)
1004     : m_original_region (original_region), m_type (type)
1005     {
1006       gcc_assert (type);
1007     }
1008
1009     hashval_t hash () const
1010     {
1011       inchash::hash hstate;
1012       hstate.add_ptr (m_original_region);
1013       hstate.add_ptr (m_type);
1014       return hstate.end ();
1015     }
1016
1017     bool operator== (const key_t &other) const
1018     {
1019       return (m_original_region == other.m_original_region
1020               && m_type == other.m_type);
1021     }
1022
1023     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1024     void mark_empty () { m_type = NULL_TREE; }
1025     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1026     bool is_empty () const { return m_type == NULL_TREE; }
1027
1028     const region *m_original_region;
1029     tree m_type;
1030   };
1031
1032   cast_region (unsigned id, const region *original_region, tree type)
1033   : region (complexity (original_region), id,
1034             original_region->get_parent_region (), type),
1035     m_original_region (original_region)
1036   {}
1037
1038   enum region_kind get_kind () const FINAL OVERRIDE { return RK_CAST; }
1039   const cast_region *
1040   dyn_cast_cast_region () const FINAL OVERRIDE { return this; }
1041   void accept (visitor *v) const FINAL OVERRIDE;
1042   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1043
1044   const region *get_original_region () const { return m_original_region; }
1045
1046 private:
1047   const region *m_original_region;
1048 };
1049
1050 } // namespace ana
1051
1052 template <>
1053 template <>
1054 inline bool
1055 is_a_helper <const cast_region *>::test (const region *reg)
1056 {
1057   return reg->get_kind () == RK_CAST;
1058 }
1059
1060 template <> struct default_hash_traits<cast_region::key_t>
1061 : public member_function_hash_traits<cast_region::key_t>
1062 {
1063   static const bool empty_zero_p = true;
1064 };
1065
1066 namespace ana {
1067
1068 /* An untyped region dynamically allocated on the heap via "malloc"
1069    or similar.  */
1070
1071 class heap_allocated_region : public region
1072 {
1073 public:
1074   heap_allocated_region (unsigned id, const region *parent)
1075   : region (complexity (parent), id, parent, NULL_TREE)
1076   {}
1077
1078   enum region_kind
1079   get_kind () const FINAL OVERRIDE { return RK_HEAP_ALLOCATED; }
1080
1081   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1082 };
1083
1084 /* An untyped region dynamically allocated on the stack via "alloca".  */
1085
1086 class alloca_region : public region
1087 {
1088 public:
1089   alloca_region (unsigned id, const frame_region *parent)
1090   : region (complexity (parent), id, parent, NULL_TREE)
1091   {}
1092
1093   enum region_kind get_kind () const FINAL OVERRIDE { return RK_ALLOCA; }
1094
1095   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1096 };
1097
1098 /* A region for a STRING_CST.  */
1099
1100 class string_region : public region
1101 {
1102 public:
1103   string_region (unsigned id, const region *parent, tree string_cst)
1104   : region (complexity (parent), id, parent, TREE_TYPE (string_cst)),
1105     m_string_cst (string_cst)
1106   {}
1107
1108   const string_region *
1109   dyn_cast_string_region () const FINAL OVERRIDE { return this; }
1110
1111   enum region_kind get_kind () const FINAL OVERRIDE { return RK_STRING; }
1112
1113   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1114
1115   tree get_string_cst () const { return m_string_cst; }
1116
1117 private:
1118   tree m_string_cst;
1119 };
1120
1121 } // namespace ana
1122
1123 template <>
1124 template <>
1125 inline bool
1126 is_a_helper <const string_region *>::test (const region *reg)
1127 {
1128   return reg->get_kind () == RK_STRING;
1129 }
1130
1131 namespace ana {
1132
1133 /* An unknown region, for handling unimplemented tree codes.  */
1134
1135 class unknown_region : public region
1136 {
1137 public:
1138   unknown_region (unsigned id, const region *parent, tree type)
1139   : region (complexity (parent), id, parent, type)
1140   {}
1141
1142   enum region_kind get_kind () const FINAL OVERRIDE { return RK_UNKNOWN; }
1143
1144   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
1145 };
1146
1147 } // namespace ana
1148
1149 #endif /* GCC_ANALYZER_REGION_H */