gcc/analyzer/store.h

   1 /* Classes for modeling the state of memory.
   2    Copyright (C) 2020-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_STORE_H
  22 #define GCC_ANALYZER_STORE_H
  23
  24 /* Implementation of the region-based ternary model described in:
  25      "A Memory Model for Static Analysis of C Programs"
  26       (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
  27      http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf  */
  28
  29 /* The store models memory as a collection of "clusters", where regions
  30    are partitioned into clusters via their base region.
  31
  32    For example, given:
  33      int a, b, c;
  34      struct coord { double x; double y; } verts[3];
  35    then "verts[0].y" and "verts[1].x" both have "verts" as their base region.
  36    Each of a, b, c, and verts will have their own clusters, so that we
  37    know that writes to e.g. "verts[1].x".don't affect e.g. "a".
  38
  39    Within each cluster we store a map of bindings to values, where the
  40    binding keys can be either concrete or symbolic.
  41
  42    Concrete bindings affect a specific range of bits relative to the start
  43    of the base region of the cluster, whereas symbolic bindings affect
  44    a specific subregion within the cluster.
  45
  46    Consider (from the symbolic-1.c testcase):
  47
  48      char arr[1024];
  49      arr[2] = a;  (1)
  50      arr[3] = b;  (2)
  51        After (1) and (2), the cluster for "arr" has concrete bindings
  52        for bits 16-23 and for bits 24-31, with svalues "INIT_VAL(a)"
  53        and "INIT_VAL(b)" respectively:
  54        cluster: {bits 16-23: "INIT_VAL(a)",
  55                  bits 24-31: "INIT_VAL(b)";
  56                  flags: {}}
  57        Attempting to query unbound subregions e.g. arr[4] will
  58        return "UNINITIALIZED".
  59        "a" and "b" are each in their own clusters, with no explicit
  60        bindings, and thus implicitly have value INIT_VAL(a) and INIT_VAL(b).
  61
  62      arr[3] = c;  (3)
  63        After (3), the concrete binding for bits 24-31 is replaced with the
  64        svalue "INIT_VAL(c)":
  65        cluster: {bits 16-23: "INIT_VAL(a)",  (from before)
  66                  bits 24-31: "INIT_VAL(c)";  (updated)
  67                  flags: {}}
  68
  69      arr[i] = d;  (4)
  70        After (4), we lose the concrete bindings and replace them with a
  71        symbolic binding for "arr[i]", with svalue "INIT_VAL(d)".  We also
  72        mark the cluster as having been "symbolically touched": future
  73        attempts to query the values of subregions other than "arr[i]",
  74        such as "arr[3]" are "UNKNOWN", since we don't know if the write
  75        to arr[i] affected them.
  76        cluster: {symbolic_key(arr[i]): "INIT_VAL(d)";
  77                  flags: {TOUCHED}}
  78
  79      arr[j] = e;  (5)
  80        After (5), we lose the symbolic binding for "arr[i]" since we could
  81        have overwritten it, and add a symbolic binding for "arr[j]".
  82        cluster: {symbolic_key(arr[j]): "INIT_VAL(d)"; (different symbolic
  83                  flags: {TOUCHED}}                     binding)
  84
  85      arr[3] = f;  (6)
  86        After (6), we lose the symbolic binding for "arr[j]" since we could
  87        have overwritten it, and gain a concrete binding for bits 24-31
  88        again, this time with svalue "INIT_VAL(e)":
  89        cluster: {bits 24-31: "INIT_VAL(d)";
  90                  flags: {TOUCHED}}
  91        The cluster is still flagged as touched, so that we know that
  92        accesses to other elements are "UNKNOWN" rather than
  93        "UNINITIALIZED".
  94
  95    Handling symbolic regions requires us to handle aliasing.
  96
  97    In the first example above, each of a, b, c and verts are non-symbolic
  98    base regions and so their clusters are "concrete clusters", whereas given:
  99        struct coord *p, *q;
 100    then "*p" and "*q" are symbolic base regions, and thus "*p" and "*q"
 101    have "symbolic clusters".
 102
 103    In the above, "verts[i].x" will have a symbolic *binding* within a
 104    concrete cluster for "verts", whereas "*p" is a symbolic *cluster*.
 105
 106    Writes to concrete clusters can't affect other concrete clusters,
 107    but can affect symbolic clusters; e.g. after:
 108        verts[0].x = 42;
 109    we bind 42 in the cluster for "verts", but the clusters for "b" and "c"
 110    can't be affected.  Any symbolic clusters for *p and for *q can be
 111    affected, *p and *q could alias verts.
 112
 113    Writes to a symbolic cluster can affect other clusters, both
 114    concrete and symbolic; e.g. after:
 115        p->x = 17;
 116    we bind 17 within the cluster for "*p".  The concrete clusters for a, b,
 117    c, and verts could be affected, depending on whether *p aliases them.
 118    Similarly, the symbolic cluster to *q could be affected.  */
 119
 120 namespace ana {
 121
 122 /* A class for keeping track of aspects of a program_state that we don't
 123    know about, to avoid false positives about leaks.
 124
 125    Consider:
 126
 127       p->field = malloc (1024);
 128       q->field = NULL;
 129
 130    where we don't know whether or not p and q point to the same memory,
 131    and:
 132
 133       p->field = malloc (1024);
 134       unknown_fn (p);
 135
 136    In both cases, the svalue for the address of the allocated buffer
 137    goes from being bound to p->field to not having anything explicitly bound
 138    to it.
 139
 140    Given that we conservatively discard bindings due to possible aliasing or
 141    calls to unknown function, the store loses references to svalues,
 142    but these svalues could still be live.  We don't want to warn about
 143    them leaking - they're effectively in a "maybe live" state.
 144
 145    This "maybe live" information is somewhat transient.
 146
 147    We don't want to store this "maybe live" information in the program_state,
 148    region_model, or store, since we don't want to bloat these objects (and
 149    potentially bloat the exploded_graph with more nodes).
 150    However, we can't store it in the region_model_context, as these context
 151    objects sometimes don't last long enough to be around when comparing the
 152    old vs the new state.
 153
 154    This class is a way to track a set of such svalues, so that we can
 155    temporarily capture that they are in a "maybe live" state whilst
 156    comparing old and new states.  */
 157
 158 class uncertainty_t
 159 {
 160 public:
 161   typedef hash_set<const svalue *>::iterator iterator;
 162
 163   void on_maybe_bound_sval (const svalue *sval)
 164   {
 165     m_maybe_bound_svals.add (sval);
 166   }
 167   void on_mutable_sval_at_unknown_call (const svalue *sval)
 168   {
 169     m_mutable_at_unknown_call_svals.add (sval);
 170   }
 171
 172   bool unknown_sm_state_p (const svalue *sval)
 173   {
 174     return (m_maybe_bound_svals.contains (sval)
 175             || m_mutable_at_unknown_call_svals.contains (sval));
 176   }
 177
 178   void dump_to_pp (pretty_printer *pp, bool simple) const;
 179   void dump (bool simple) const;
 180
 181   iterator begin_maybe_bound_svals () const
 182   {
 183     return m_maybe_bound_svals.begin ();
 184   }
 185   iterator end_maybe_bound_svals () const
 186   {
 187     return m_maybe_bound_svals.end ();
 188   }
 189
 190 private:
 191
 192   /* svalues that might or might not still be bound.  */
 193   hash_set<const svalue *> m_maybe_bound_svals;
 194
 195   /* svalues that have mutable sm-state at unknown calls.  */
 196   hash_set<const svalue *> m_mutable_at_unknown_call_svals;
 197 };
 198
 199 class byte_range;
 200 class concrete_binding;
 201 class symbolic_binding;
 202
 203 /* Abstract base class for describing ranges of bits within a binding_map
 204    that can have svalues bound to them.  */
 205
 206 class binding_key
 207 {
 208 public:
 209   virtual ~binding_key () {}
 210   virtual bool concrete_p () const = 0;
 211   bool symbolic_p () const { return !concrete_p (); }
 212
 213   static const binding_key *make (store_manager *mgr, const region *r);
 214
 215   virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
 216   void dump (bool simple) const;
 217   label_text get_desc (bool simple=true) const;
 218
 219   static int cmp_ptrs (const void *, const void *);
 220   static int cmp (const binding_key *, const binding_key *);
 221
 222   virtual const concrete_binding *dyn_cast_concrete_binding () const
 223   { return NULL; }
 224   virtual const symbolic_binding *dyn_cast_symbolic_binding () const
 225   { return NULL; }
 226 };
 227
 228 /* A concrete range of bits.  */
 229
 230 struct bit_range
 231 {
 232   bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
 233   : m_start_bit_offset (start_bit_offset),
 234     m_size_in_bits (size_in_bits)
 235   {}
 236
 237   void dump_to_pp (pretty_printer *pp) const;
 238   void dump () const;
 239
 240   bool empty_p () const
 241   {
 242     return m_size_in_bits == 0;
 243   }
 244
 245   bit_offset_t get_start_bit_offset () const
 246   {
 247     return m_start_bit_offset;
 248   }
 249   bit_offset_t get_next_bit_offset () const
 250   {
 251     return m_start_bit_offset + m_size_in_bits;
 252   }
 253   bit_offset_t get_last_bit_offset () const
 254   {
 255     gcc_assert (!empty_p ());
 256     return get_next_bit_offset () - 1;
 257   }
 258
 259   bool contains_p (bit_offset_t offset) const
 260   {
 261     return (offset >= get_start_bit_offset ()
 262             && offset < get_next_bit_offset ());
 263   }
 264
 265   bool contains_p (const bit_range &other, bit_range *out) const;
 266
 267   bool operator== (const bit_range &other) const
 268   {
 269     return (m_start_bit_offset == other.m_start_bit_offset
 270             && m_size_in_bits == other.m_size_in_bits);
 271   }
 272
 273   bool intersects_p (const bit_range &other) const
 274   {
 275     return (get_start_bit_offset () < other.get_next_bit_offset ()
 276             && other.get_start_bit_offset () < get_next_bit_offset ());
 277   }
 278   bool intersects_p (const bit_range &other,
 279                      bit_range *out_this,
 280                      bit_range *out_other) const;
 281
 282   static int cmp (const bit_range &br1, const bit_range &br2);
 283
 284   bit_range operator- (bit_offset_t offset) const;
 285
 286   static bool from_mask (unsigned HOST_WIDE_INT mask, bit_range *out);
 287
 288   bool as_byte_range (byte_range *out) const;
 289
 290   bit_offset_t m_start_bit_offset;
 291   bit_size_t m_size_in_bits;
 292 };
 293
 294 /* A concrete range of bytes.  */
 295
 296 struct byte_range
 297 {
 298   byte_range (byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
 299   : m_start_byte_offset (start_byte_offset),
 300     m_size_in_bytes (size_in_bytes)
 301   {}
 302
 303   void dump_to_pp (pretty_printer *pp) const;
 304   void dump () const;
 305
 306   bool empty_p () const
 307   {
 308     return m_size_in_bytes == 0;
 309   }
 310
 311   bool contains_p (byte_offset_t offset) const
 312   {
 313     return (offset >= get_start_byte_offset ()
 314             && offset < get_next_byte_offset ());
 315   }
 316   bool contains_p (const byte_range &other, byte_range *out) const;
 317
 318   bool operator== (const byte_range &other) const
 319   {
 320     return (m_start_byte_offset == other.m_start_byte_offset
 321             && m_size_in_bytes == other.m_size_in_bytes);
 322   }
 323
 324   bool intersects_p (const byte_range &other,
 325                      byte_size_t *out_num_overlap_bytes) const;
 326
 327   bool exceeds_p (const byte_range &other,
 328                   byte_range *out_overhanging_byte_range) const;
 329
 330   bool falls_short_of_p (byte_offset_t offset,
 331                          byte_range *out_fall_short_bytes) const;
 332
 333   byte_offset_t get_start_byte_offset () const
 334   {
 335     return m_start_byte_offset;
 336   }
 337   byte_offset_t get_next_byte_offset () const
 338   {
 339     return m_start_byte_offset + m_size_in_bytes;
 340   }
 341   byte_offset_t get_last_byte_offset () const
 342   {
 343     gcc_assert (!empty_p ());
 344     return m_start_byte_offset + m_size_in_bytes - 1;
 345   }
 346
 347   bit_range as_bit_range () const
 348   {
 349     return bit_range (m_start_byte_offset * BITS_PER_UNIT,
 350                       m_size_in_bytes * BITS_PER_UNIT);
 351   }
 352
 353   static int cmp (const byte_range &br1, const byte_range &br2);
 354
 355   byte_offset_t m_start_byte_offset;
 356   byte_size_t m_size_in_bytes;
 357 };
 358
 359 /* Concrete subclass of binding_key, for describing a concrete range of
 360    bits within the binding_map (e.g. "bits 8-15").  */
 361
 362 class concrete_binding : public binding_key
 363 {
 364 public:
 365   /* This class is its own key for the purposes of consolidation.  */
 366   typedef concrete_binding key_t;
 367
 368   concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
 369   : m_bit_range (start_bit_offset, size_in_bits)
 370   {}
 371   bool concrete_p () const final override { return true; }
 372
 373   hashval_t hash () const
 374   {
 375     inchash::hash hstate;
 376     hstate.add_wide_int (m_bit_range.m_start_bit_offset);
 377     hstate.add_wide_int (m_bit_range.m_size_in_bits);
 378     return hstate.end ();
 379   }
 380   bool operator== (const concrete_binding &other) const
 381   {
 382     return m_bit_range == other.m_bit_range;
 383   }
 384
 385   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
 386
 387   const concrete_binding *dyn_cast_concrete_binding () const final override
 388   { return this; }
 389
 390   const bit_range &get_bit_range () const { return m_bit_range; }
 391
 392   bit_offset_t get_start_bit_offset () const
 393   {
 394     return m_bit_range.m_start_bit_offset;
 395   }
 396   bit_size_t get_size_in_bits () const
 397   {
 398     return m_bit_range.m_size_in_bits;
 399   }
 400   /* Return the next bit offset after the end of this binding.  */
 401   bit_offset_t get_next_bit_offset () const
 402   {
 403     return m_bit_range.get_next_bit_offset ();
 404   }
 405
 406   bool overlaps_p (const concrete_binding &other) const;
 407
 408   static int cmp_ptr_ptr (const void *, const void *);
 409
 410   void mark_deleted () { m_bit_range.m_start_bit_offset = -1; }
 411   void mark_empty () { m_bit_range.m_start_bit_offset = -2; }
 412   bool is_deleted () const { return m_bit_range.m_start_bit_offset == -1; }
 413   bool is_empty () const { return m_bit_range.m_start_bit_offset == -2; }
 414
 415 private:
 416   bit_range m_bit_range;
 417 };
 418
 419 } // namespace ana
 420
 421 template <>
 422 template <>
 423 inline bool
 424 is_a_helper <const ana::concrete_binding *>::test (const ana::binding_key *key)
 425 {
 426   return key->concrete_p ();
 427 }
 428
 429 template <> struct default_hash_traits<ana::concrete_binding>
 430 : public member_function_hash_traits<ana::concrete_binding>
 431 {
 432   static const bool empty_zero_p = false;
 433 };
 434
 435 namespace ana {
 436
 437 /* Concrete subclass of binding_key, for describing a symbolic set of
 438    bits within the binding_map in terms of a region (e.g. "arr[i]").  */
 439
 440 class symbolic_binding : public binding_key
 441 {
 442 public:
 443   /* This class is its own key for the purposes of consolidation.  */
 444   typedef symbolic_binding key_t;
 445
 446   symbolic_binding (const region *region) : m_region (region) {}
 447   bool concrete_p () const final override { return false; }
 448
 449   hashval_t hash () const
 450   {
 451     return (intptr_t)m_region;
 452   }
 453   bool operator== (const symbolic_binding &other) const
 454   {
 455     return m_region == other.m_region;
 456   }
 457
 458   void dump_to_pp (pretty_printer *pp, bool simple) const final override;
 459
 460   const symbolic_binding *dyn_cast_symbolic_binding () const final override
 461   { return this; }
 462
 463   const region *get_region () const { return m_region; }
 464
 465   static int cmp_ptr_ptr (const void *, const void *);
 466
 467   void mark_deleted () { m_region = reinterpret_cast<const region *> (1); }
 468   void mark_empty () { m_region = NULL; }
 469   bool is_deleted () const
 470   { return m_region == reinterpret_cast<const region *> (1); }
 471   bool is_empty () const { return m_region == NULL; }
 472
 473 private:
 474   const region *m_region;
 475 };
 476
 477 } // namespace ana
 478
 479 template <> struct default_hash_traits<ana::symbolic_binding>
 480 : public member_function_hash_traits<ana::symbolic_binding>
 481 {
 482   static const bool empty_zero_p = true;
 483 };
 484
 485 namespace ana {
 486
 487 /* A mapping from binding_keys to svalues, for use by binding_cluster
 488    and compound_svalue.  */
 489
 490 class binding_map
 491 {
 492 public:
 493   typedef hash_map <const binding_key *, const svalue *> map_t;
 494   typedef map_t::iterator iterator_t;
 495
 496   binding_map () : m_map () {}
 497   binding_map (const binding_map &other);
 498   binding_map& operator=(const binding_map &other);
 499
 500   bool operator== (const binding_map &other) const;
 501   bool operator!= (const binding_map &other) const
 502   {
 503     return !(*this == other);
 504   }
 505
 506   hashval_t hash () const;
 507
 508   const svalue *get (const binding_key *key) const
 509   {
 510     const svalue **slot = const_cast<map_t &> (m_map).get (key);
 511     if (slot)
 512       return *slot;
 513     else
 514       return NULL;
 515   }
 516   bool put (const binding_key *k, const svalue *v)
 517   {
 518     gcc_assert (v);
 519     return m_map.put (k, v);
 520   }
 521
 522   void remove (const binding_key *k) { m_map.remove (k); }
 523   void empty () { m_map.empty (); }
 524
 525   iterator_t begin () const { return m_map.begin (); }
 526   iterator_t end () const { return m_map.end (); }
 527   size_t elements () const { return m_map.elements (); }
 528
 529   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 530   void dump (bool simple) const;
 531
 532   json::object *to_json () const;
 533
 534   bool apply_ctor_to_region (const region *parent_reg, tree ctor,
 535                              region_model_manager *mgr);
 536
 537   static int cmp (const binding_map &map1, const binding_map &map2);
 538
 539   void remove_overlapping_bindings (store_manager *mgr,
 540                                     const binding_key *drop_key,
 541                                     uncertainty_t *uncertainty,
 542                                     bool always_overlap);
 543
 544 private:
 545   void get_overlapping_bindings (const binding_key *key,
 546                                  auto_vec<const binding_key *> *out);
 547   bool apply_ctor_val_to_range (const region *parent_reg,
 548                                 region_model_manager *mgr,
 549                                 tree min_index, tree max_index,
 550                                 tree val);
 551   bool apply_ctor_pair_to_child_region (const region *parent_reg,
 552                                         region_model_manager *mgr,
 553                                         tree index, tree val);
 554
 555   map_t m_map;
 556 };
 557
 558 /* Concept: BindingVisitor, for use by binding_cluster::for_each_binding
 559    and store::for_each_binding.
 560
 561    Should implement:
 562      void on_binding (const binding_key *key, const svalue *&sval);
 563 */
 564
 565 /* All of the bindings within a store for regions that share the same
 566    base region.  */
 567
 568 class binding_cluster
 569 {
 570 public:
 571   friend class store;
 572
 573   typedef hash_map <const binding_key *, const svalue *> map_t;
 574   typedef map_t::iterator iterator_t;
 575
 576   binding_cluster (const region *base_region);
 577   binding_cluster (const binding_cluster &other);
 578   binding_cluster& operator=(const binding_cluster &other);
 579
 580   bool operator== (const binding_cluster &other) const;
 581   bool operator!= (const binding_cluster &other) const
 582   {
 583     return !(*this == other);
 584   }
 585
 586   hashval_t hash () const;
 587
 588   bool symbolic_p () const;
 589
 590   const region *get_base_region () const { return m_base_region; }
 591
 592   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
 593   void dump (bool simple) const;
 594
 595   void validate () const;
 596
 597   json::object *to_json () const;
 598
 599   void bind (store_manager *mgr, const region *, const svalue *);
 600
 601   void clobber_region (store_manager *mgr, const region *reg);
 602   void purge_region (store_manager *mgr, const region *reg);
 603   void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
 604   void zero_fill_region (store_manager *mgr, const region *reg);
 605   void mark_region_as_unknown (store_manager *mgr,
 606                                const region *reg_to_bind,
 607                                const region *reg_for_overlap,
 608                                uncertainty_t *uncertainty);
 609   void purge_state_involving (const svalue *sval,
 610                               region_model_manager *sval_mgr);
 611
 612   const svalue *get_binding (store_manager *mgr, const region *reg) const;
 613   const svalue *get_binding_recursive (store_manager *mgr,
 614                                         const region *reg) const;
 615   const svalue *get_any_binding (store_manager *mgr,
 616                                   const region *reg) const;
 617   const svalue *maybe_get_compound_binding (store_manager *mgr,
 618                                              const region *reg) const;
 619
 620   void remove_overlapping_bindings (store_manager *mgr, const region *reg,
 621                                     uncertainty_t *uncertainty);
 622
 623   template <typename T>
 624   void for_each_value (void (*cb) (const svalue *sval, T user_data),
 625                        T user_data) const
 626   {
 627     for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
 628       cb ((*iter).second, user_data);
 629   }
 630
 631   static bool can_merge_p (const binding_cluster *cluster_a,
 632                            const binding_cluster *cluster_b,
 633                            binding_cluster *out_cluster,
 634                            store *out_store,
 635                            store_manager *mgr,
 636                            model_merger *merger);
 637   void make_unknown_relative_to (const binding_cluster *other_cluster,
 638                                  store *out_store,
 639                                  store_manager *mgr);
 640
 641   void mark_as_escaped ();
 642   void on_unknown_fncall (const gcall *call, store_manager *mgr,
 643                           const conjured_purge &p);
 644   void on_asm (const gasm *stmt, store_manager *mgr,
 645                const conjured_purge &p);
 646
 647   bool escaped_p () const { return m_escaped; }
 648   bool touched_p () const { return m_touched; }
 649
 650   bool redundant_p () const;
 651   bool empty_p () const { return m_map.elements () == 0; }
 652
 653   void get_representative_path_vars (const region_model *model,
 654                                      svalue_set *visited,
 655                                      const region *base_reg,
 656                                      const svalue *sval,
 657                                      auto_vec<path_var> *out_pvs) const;
 658
 659   const svalue *maybe_get_simple_value (store_manager *mgr) const;
 660
 661   template <typename BindingVisitor>
 662   void for_each_binding (BindingVisitor &v) const
 663   {
 664     for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
 665       {
 666         const binding_key *key = (*iter).first;
 667         const svalue *&sval = (*iter).second;
 668         v.on_binding (key, sval);
 669       }
 670   }
 671
 672   iterator_t begin () const { return m_map.begin (); }
 673   iterator_t end () const { return m_map.end (); }
 674
 675   const binding_map &get_map () const { return m_map; }
 676
 677 private:
 678   const svalue *get_any_value (const binding_key *key) const;
 679   void bind_compound_sval (store_manager *mgr,
 680                            const region *reg,
 681                            const compound_svalue *compound_sval);
 682   void bind_key (const binding_key *key, const svalue *sval);
 683
 684   const region *m_base_region;
 685
 686   binding_map m_map;
 687
 688   /* Has a pointer to this cluster "escaped" into a part of the program
 689      we don't know about (via a call to a function with an unknown body,
 690      or by being passed in as a pointer param of a "top-level" function call).
 691      Such regions could be overwritten when other such functions are called,
 692      even if the region is no longer reachable by pointers that we are
 693      tracking. */
 694   bool m_escaped;
 695
 696   /* Has this cluster been written to via a symbolic binding?
 697      If so, then we don't know anything about unbound subregions,
 698      so we can't use initial_svalue, treat them as uninitialized, or
 699      inherit values from a parent region.  */
 700   bool m_touched;
 701 };
 702
 703 /* The mapping from regions to svalues.
 704    This is actually expressed by subdividing into clusters, to better
 705    handle aliasing.  */
 706
 707 class store
 708 {
 709 public:
 710   typedef hash_map <const region *, binding_cluster *> cluster_map_t;
 711
 712   store ();
 713   store (const store &other);
 714   ~store ();
 715
 716   store &operator= (const store &other);
 717
 718   bool operator== (const store &other) const;
 719   bool operator!= (const store &other) const
 720   {
 721     return !(*this == other);
 722   }
 723
 724   hashval_t hash () const;
 725
 726   void dump_to_pp (pretty_printer *pp, bool summarize, bool multiline,
 727                    store_manager *mgr) const;
 728   void dump (bool simple) const;
 729   void summarize_to_pp (pretty_printer *pp, bool simple) const;
 730
 731   void validate () const;
 732
 733   json::object *to_json () const;
 734
 735   const svalue *get_any_binding (store_manager *mgr, const region *reg) const;
 736
 737   bool called_unknown_fn_p () const { return m_called_unknown_fn; }
 738
 739   void set_value (store_manager *mgr, const region *lhs_reg,
 740                   const svalue *rhs_sval,
 741                   uncertainty_t *uncertainty);
 742   void clobber_region (store_manager *mgr, const region *reg);
 743   void purge_region (store_manager *mgr, const region *reg);
 744   void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
 745   void zero_fill_region (store_manager *mgr, const region *reg);
 746   void mark_region_as_unknown (store_manager *mgr, const region *reg,
 747                                uncertainty_t *uncertainty);
 748   void purge_state_involving (const svalue *sval,
 749                               region_model_manager *sval_mgr);
 750
 751   const binding_cluster *get_cluster (const region *base_reg) const;
 752   binding_cluster *get_cluster (const region *base_reg);
 753   binding_cluster *get_or_create_cluster (const region *base_reg);
 754   void purge_cluster (const region *base_reg);
 755
 756   template <typename T>
 757   void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
 758                          T user_data) const
 759   {
 760     for (cluster_map_t::iterator iter = m_cluster_map.begin ();
 761          iter != m_cluster_map.end (); ++iter)
 762       cb ((*iter).first, user_data);
 763   }
 764
 765   static bool can_merge_p (const store *store_a, const store *store_b,
 766                            store *out_store, store_manager *mgr,
 767                            model_merger *merger);
 768
 769   void mark_as_escaped (const region *base_reg);
 770   void on_unknown_fncall (const gcall *call, store_manager *mgr,
 771                           const conjured_purge &p);
 772   bool escaped_p (const region *reg) const;
 773
 774   void get_representative_path_vars (const region_model *model,
 775                                      svalue_set *visited,
 776                                      const svalue *sval,
 777                                      auto_vec<path_var> *out_pvs) const;
 778
 779   cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
 780   cluster_map_t::iterator end () const { return m_cluster_map.end (); }
 781
 782   tristate eval_alias (const region *base_reg_a,
 783                        const region *base_reg_b) const;
 784
 785   template <typename BindingVisitor>
 786   void for_each_binding (BindingVisitor &v)
 787   {
 788     for (cluster_map_t::iterator iter = m_cluster_map.begin ();
 789          iter != m_cluster_map.end (); ++iter)
 790       (*iter).second->for_each_binding (v);
 791   }
 792
 793   void canonicalize (store_manager *mgr);
 794   void loop_replay_fixup (const store *other_store,
 795                           region_model_manager *mgr);
 796
 797   void replay_call_summary (call_summary_replay &r,
 798                             const store &summary);
 799   void replay_call_summary_cluster (call_summary_replay &r,
 800                                     const store &summary,
 801                                     const region *base_reg);
 802
 803 private:
 804   void remove_overlapping_bindings (store_manager *mgr, const region *reg,
 805                                     uncertainty_t *uncertainty);
 806   tristate eval_alias_1 (const region *base_reg_a,
 807                          const region *base_reg_b) const;
 808
 809   cluster_map_t m_cluster_map;
 810
 811   /* If this is true, then unknown code has been called, and so
 812      any global variable that isn't currently modelled by the store
 813      has unknown state, rather than being in an "initial state".
 814      This is to avoid having to mark (and thus explicitly track)
 815      every global when an unknown function is called; instead, they
 816      can be tracked implicitly.  */
 817   bool m_called_unknown_fn;
 818 };
 819
 820 /* A class responsible for owning and consolidating binding keys
 821    (both concrete and symbolic).
 822    Key instances are immutable as far as clients are concerned, so they
 823    are provided as "const" ptrs.  */
 824
 825 class store_manager
 826 {
 827 public:
 828   store_manager (region_model_manager *mgr) : m_mgr (mgr) {}
 829
 830   logger *get_logger () const;
 831
 832   /* binding consolidation.  */
 833   const concrete_binding *
 834   get_concrete_binding (bit_offset_t start_bit_offset,
 835                         bit_offset_t size_in_bits);
 836   const concrete_binding *
 837   get_concrete_binding (const bit_range &bits)
 838   {
 839     return get_concrete_binding (bits.get_start_bit_offset (),
 840                                  bits.m_size_in_bits);
 841   }
 842   const symbolic_binding *
 843   get_symbolic_binding (const region *region);
 844
 845   region_model_manager *get_svalue_manager () const
 846   {
 847     return m_mgr;
 848   }
 849
 850   void log_stats (logger *logger, bool show_objs) const;
 851
 852 private:
 853   region_model_manager *m_mgr;
 854   consolidation_map<concrete_binding> m_concrete_binding_key_mgr;
 855   consolidation_map<symbolic_binding> m_symbolic_binding_key_mgr;
 856 };
 857
 858 } // namespace ana
 859
 860 #endif /* GCC_ANALYZER_STORE_H */