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