LCOV - code coverage report
Current view: top level - gcc/analyzer - store.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 59.3 % 59 35
Test Date: 2026-11-14 16:39:50 Functions: 50.0 % 8 4
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Classes for modeling the state of memory.
       2              :    Copyright (C) 2020-2026 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              : #include "text-art/tree-widget.h"
      25              : #include "analyzer/complexity.h"
      26              : #include "analyzer/concrete-ranges.h"
      27              : #include "analyzer/symbolic-ranges.h"
      28              : #include "analyzer/symbolic-bit-contents.h"
      29              : #include "analyzer/symbolic-memory-ranges.h"
      30              : 
      31              : /* Implementation of the region-based ternary model described in:
      32              :      "A Memory Model for Static Analysis of C Programs"
      33              :       (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
      34              :      http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf  */
      35              : 
      36              : /* Binding clusters
      37              :    ================
      38              : 
      39              :    The store models memory as a collection of "clusters", where regions
      40              :    are partitioned into clusters via their base region.
      41              : 
      42              :    For example, given:
      43              :      int a, b, c;
      44              :      struct coord { double x; double y; } verts[3];
      45              :    then "verts[0].y" and "verts[1].x" both have "verts" as their base region.
      46              :    Each of a, b, c, and verts will have their own clusters, so that we
      47              :    know that writes to e.g. "verts[1].x".don't affect e.g. "a".
      48              : 
      49              :    For each cluster that's been touched by the user's code we track an
      50              :    immutable bit_contents instance, updating it to point to a different
      51              :    bit_contents instance after each change.
      52              : 
      53              :    Handling symbolic regions requires us to handle aliasing.
      54              : 
      55              :    In the example above, each of a, b, c and verts are non-symbolic
      56              :    base regions and so their clusters are "concrete clusters", whereas given:
      57              :        struct coord *p, *q;
      58              :    then "*p" and "*q" are symbolic base regions, and thus "*p" and "*q"
      59              :    have "symbolic clusters".
      60              : 
      61              :    In the above, "verts[i].x" will have a symbolic *binding* within a
      62              :    concrete cluster for "verts", whereas "*p" is a symbolic *cluster*.
      63              : 
      64              :    Writes to concrete clusters can't affect other concrete clusters,
      65              :    but can affect symbolic clusters; e.g. after:
      66              :        verts[0].x = 42;
      67              :    we bind 42 in the cluster for "verts", but the clusters for "b" and "c"
      68              :    can't be affected.  Any symbolic clusters for *p and for *q can be
      69              :    affected, *p and *q could alias "verts".
      70              : 
      71              :    Writes to a symbolic cluster can affect other clusters, both
      72              :    concrete and symbolic; e.g. after:
      73              :        p->x = 17;
      74              :    we bind 17 within the cluster for "*p".  The concrete clusters for a, b,
      75              :    c, and verts could be affected, depending on whether *p aliases them.
      76              :    Similarly, the symbolic cluster to *q could be affected.
      77              : 
      78              : 
      79              :    Tracking the state within a binding cluster
      80              :    ===========================================
      81              : 
      82              :    Reads and writes to memory are handled as reading and writing bits to
      83              :    a cluster, where the memory ranges relative to the start of the cluster
      84              :    can be either fully concrete, or be symbolic (with a symbolic start offset
      85              :    and/or size).
      86              : 
      87              :    Consider this example (taken from
      88              :    gcc/testsuite/c-c++-common/analyzer/symbolic-1.c, adding calls to
      89              :    __analyzer_dump (); at the pertinent places):
      90              : 
      91              :      char arr[1024];
      92              :      arr[2] = a;  (1)
      93              :      arr[3] = b;  (2)
      94              :        After (1) and (2), we have this state:
      95              :          | program_state
      96              :          | ╰─ Region Model
      97              :          |    ├─ Current Frame: frame: ‘test_1’@1
      98              :          |    ╰─ Store
      99              :          |       ├─ m_called_unknown_fn: false
     100              :          |       ╰─ frame: ‘test_1’@1
     101              :          |          ╰─ arr:
     102              :          |             ╰─ (616): concrete bit overlay
     103              :          |                ├─ concrete ranges
     104              :          |                │  ├─ [byte 2]: (605): bit_vector_from_svalue[size: 1 byte]
     105              :          |                │  │  ╰─ m_sval: (604): ‘char’: initial_svalue
     106              :          |                │  │     ├─ value_range: {[irange] char VARYING}
     107              :          |                │  │     ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
     108              :          |                │  │        ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     109              :          |                │  │           ╰─ parent: (1): stack region
     110              :          |                │  │              ╰─ parent: (0): root region
     111              :          |                │  ╰─ [byte 3]: (613): bit_vector_from_svalue[size: 1 byte]
     112              :          |                │     ╰─ m_sval: (612): ‘char’: initial_svalue
     113              :          |                │        ├─ value_range: {[irange] char VARYING}
     114              :          |                │        ╰─ m_reg: (611): ‘char’: decl_region(‘b_50(D)’)
     115              :          |                │           ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     116              :          |                │              ╰─ {as above; descendents: 3, depth: 3}
     117              :          |                ╰─ baseline: (7): uninitialized contents
     118              :        The cluster for "arr" has a concrete_bit_overlay for its contents,
     119              :        with bytes 2 and 3 bound to bit_vectors for the target encoding
     120              :        of svalues for the initial values of "a" and "b" respectively.  This
     121              :        is overlaid on top of the baseline "uninitialized" everywhere else, so
     122              :        that attempting to query e.g. arr[4] will return "uninitialized".
     123              : 
     124              :        "a" and "b" are each in their own clusters, with no explicit
     125              :        bindings, and thus have their "implicit contents": in this case
     126              :        concrete_bit_overlay instances bound at [0..sizeof(int)) to the bit
     127              :        vectors for the initial_svalue of "a" and "b" respectively.
     128              : 
     129              :      arr[3] = c;  (3)
     130              :        After (3), the contents of the cluster for "arr" has been replaced by
     131              :        a new concrete_bit_overlay instance, the same as the previous one,
     132              :        but with byte 3 now bound to a bit vector for the
     133              :        initial_svalue for "c":
     134              :          | program_state
     135              :          | ╰─ Region Model
     136              :          |    ├─ Current Frame: frame: ‘test_1’@1
     137              :          |    ╰─ Store
     138              :          |       ├─ m_called_unknown_fn: false
     139              :          |       ╰─ frame: ‘test_1’@1
     140              :          |          ╰─ arr:
     141              :          |             ╰─ (648): concrete bit overlay
     142              :          |                ├─ concrete ranges
     143              :          |                │  ├─ [byte 2]: (605): bit_vector_from_svalue[size: 1 byte]
     144              :          |                │  │  ╰─ m_sval: (604): ‘char’: initial_svalue
     145              :          |                │  │     ├─ value_range: {[irange] char VARYING}
     146              :          |                │  │     ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
     147              :          |                │  │        ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     148              :          |                │  │           ╰─ parent: (1): stack region
     149              :          |                │  │              ╰─ parent: (0): root region
     150              :          |                │  ╰─ [byte 3]: (645): bit_vector_from_svalue[size: 1 byte]
     151              :          |                │     ╰─ m_sval: (644): ‘char’: initial_svalue
     152              :          |                │        ├─ value_range: {[irange] char VARYING}
     153              :          |                │        ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
     154              :          |                │           ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     155              :          |                │              ╰─ {as above; descendents: 3, depth: 3}
     156              :          |                ╰─ baseline: (7): uninitialized contents
     157              :        Note that the concrete_bit_overlay (and other bit_contents instances)
     158              :        are immutable and pure-functional - when a cluster is written to, we
     159              :        update the cluster's m_contents to point to a different bit_contents.
     160              : 
     161              :      arr[i] = d;  (4)
     162              :        After the write to the symbolic array index at (4), the cluster for
     163              :        "arr" no longer uses the concrete_bit_overlay and instead points to
     164              :        a symbolic_bit_overlay, where the bytes at element [i] are bound to
     165              :        the bit_vector fot the initial value of "d":
     166              :          | program_state
     167              :          | ╰─ Region Model
     168              :          |    ├─ Current Frame: frame: ‘test_1’@1
     169              :          |    ╰─ Store
     170              :          |       ├─ m_called_unknown_fn: false
     171              :          |       ╰─ frame: ‘test_1’@1
     172              :          |          ╰─ arr:
     173              :          |             ╰─ (670): symbolic bit overlay
     174              :          |                ├─ symbolic ranges
     175              :          |                │  ├─ symbolic range
     176              :          |                │  │  ├─ start offset: (571): bits_from_bytes_scalar
     177              :          |                │  │  │  ╰─ (570): scalar_from_svalue<bytes>
     178              :          |                │  │  │     ╰─ (565): ‘int’: initial_svalue
     179              :          |                │  │  │        ├─ value_range: {[irange] int VARYING}
     180              :          |                │  │  │        ╰─ m_reg: (564): ‘int’: decl_region(‘i_61(D)’)
     181              :          |                │  │  │           ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     182              :          |                │  │  │              ╰─ parent: (1): stack region
     183              :          |                │  │  │                 ╰─ parent: (0): root region
     184              :          |                │  │  ╰─ size: (11): concrete_scalar<bits>: 8
     185              :          |                │  ╰─ (657): bit_vector_from_svalue[size: 1 byte]
     186              :          |                │     ╰─ m_sval: (656): ‘char’: initial_svalue
     187              :          |                │        ├─ value_range: {[irange] char VARYING}
     188              :          |                │        ╰─ m_reg: (655): ‘char’: decl_region(‘d_62(D)’)
     189              :          |                │           ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     190              :          |                │              ╰─ {as above; descendents: 3, depth: 3}
     191              :          |                ╰─ baseline: (669): untracked_bit_contents
     192              :          |                   ╰─ maybe live values
     193              :          |                      ├─ (605): bit_vector_from_svalue[size: 1 byte]
     194              :          |                      │  ╰─ m_sval: (604): ‘char’: initial_svalue
     195              :          |                      │     ├─ value_range: {[irange] char VARYING}
     196              :          |                      │     ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
     197              :          |                      │        ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     198              :          |                      │           ╰─ {as above; descendents: 3, depth: 3}
     199              :          |                      ╰─ (645): bit_vector_from_svalue[size: 1 byte]
     200              :          |                         ╰─ m_sval: (644): ‘char’: initial_svalue
     201              :          |                            ├─ value_range: {[irange] char VARYING}
     202              :          |                            ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
     203              :          |                               ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     204              :          |                                  ╰─ {as above; descendents: 3, depth: 3}
     205              :        We also set the baseline for this overlay to an untracked_bit_contents
     206              :        instance.  This indicates that we've given up on tracking the contents
     207              :        of "arr" at other locations (reads will return "unknown", rather than
     208              :        "uninitialized").  The untracked_bit_contents has a set of values that
     209              :        are "maybe live", capturing that the initial values of "a" and "c" may
     210              :        still be live within "arr" (to avoid leak false +ves), since we don't
     211              :        know if i == 3 or 4.
     212              : 
     213              :        Note how the IDs of the "maybe live values" nodes below match those
     214              :        within the concrete_bit_overlay above: the symbolic::node instances
     215              :        persist through the analysis.
     216              : 
     217              :      arr[j] = e;  (5)
     218              :        After (5), the user's code has written to a possibly-different
     219              :        symbolic index within "arr", so we have a new symbolic_bit_overlay,
     220              :        binding the byte at [j] to the bit vector for the initial value of "e",
     221              :        and the "maybe live values" has gained the value that was at [i], since
     222              :        we don't know whether j == i (or j == 3, or j == 4):
     223              :          | program_state
     224              :          | ╰─ Region Model
     225              :          |    ├─ Current Frame: frame: ‘test_1’@1
     226              :          |    ╰─ Store
     227              :          |       ├─ m_called_unknown_fn: false
     228              :          |       ╰─ frame: ‘test_1’@1
     229              :          |          ╰─ arr:
     230              :          |             ╰─ (685): symbolic bit overlay
     231              :          |                ├─ symbolic ranges
     232              :          |                │  ├─ symbolic range
     233              :          |                │  │  ├─ start offset: (590): bits_from_bytes_scalar
     234              :          |                │  │  │  ╰─ (589): scalar_from_svalue<bytes>
     235              :          |                │  │  │     ╰─ (584): ‘int’: initial_svalue
     236              :          |                │  │  │        ├─ value_range: {[irange] int VARYING}
     237              :          |                │  │  │        ╰─ m_reg: (583): ‘int’: decl_region(‘j_68(D)’)
     238              :          |                │  │  │           ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     239              :          |                │  │  │              ╰─ parent: (1): stack region
     240              :          |                │  │  │                 ╰─ parent: (0): root region
     241              :          |                │  │  ╰─ size: (11): concrete_scalar<bits>: 8
     242              :          |                │  ╰─ (676): bit_vector_from_svalue[size: 1 byte]
     243              :          |                │     ╰─ m_sval: (675): ‘char’: initial_svalue
     244              :          |                │        ├─ value_range: {[irange] char VARYING}
     245              :          |                │        ╰─ m_reg: (674): ‘char’: decl_region(‘e_69(D)’)
     246              :          |                │           ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     247              :          |                │              ╰─ {as above; descendents: 3, depth: 3}
     248              :          |                ╰─ baseline: (684): untracked_bit_contents
     249              :          |                   ╰─ maybe live values
     250              :          |                      ├─ (605): bit_vector_from_svalue[size: 1 byte]
     251              :          |                      │  ╰─ m_sval: (604): ‘char’: initial_svalue
     252              :          |                      │     ├─ value_range: {[irange] char VARYING}
     253              :          |                      │     ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
     254              :          |                      │        ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     255              :          |                      │           ╰─ {as above; descendents: 3, depth: 3}
     256              :          |                      ├─ (645): bit_vector_from_svalue[size: 1 byte]
     257              :          |                      │  ╰─ m_sval: (644): ‘char’: initial_svalue
     258              :          |                      │     ├─ value_range: {[irange] char VARYING}
     259              :          |                      │     ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
     260              :          |                      │        ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     261              :          |                      │           ╰─ {as above; descendents: 3, depth: 3}
     262              :          |                      ╰─ (657): bit_vector_from_svalue[size: 1 byte]
     263              :          |                         ╰─ m_sval: (656): ‘char’: initial_svalue
     264              :          |                            ├─ value_range: {[irange] char VARYING}
     265              :          |                            ╰─ m_reg: (655): ‘char’: decl_region(‘d_62(D)’)
     266              :          |                               ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     267              :          |                                  ╰─ {as above; descendents: 3, depth: 3}
     268              : 
     269              :      arr[3] = f;  (6)
     270              :        After (6), we have a concrete_bit_overlay again, this, with a binding
     271              :        at byte [3], where the baseline is an untracked_bit_contents, with all
     272              :        the various other values we're written into "arr" as "maybe live":
     273              :          | program_state
     274              :          | ╰─ Region Model
     275              :          |    ├─ Current Frame: frame: ‘test_1’@1
     276              :          |    ╰─ Store
     277              :          |       ├─ m_called_unknown_fn: false
     278              :          |       ╰─ frame: ‘test_1’@1
     279              :          |          ╰─ arr:
     280              :          |             ╰─ (691): concrete bit overlay
     281              :          |                ├─ concrete ranges
     282              :          |                │  ╰─ [byte 3]: (688): bit_vector_from_svalue[size: 1 byte]
     283              :          |                │     ╰─ m_sval: (687): ‘char’: initial_svalue
     284              :          |                │        ├─ value_range: {[irange] char VARYING}
     285              :          |                │        ╰─ m_reg: (686): ‘char’: decl_region(‘f_74(D)’)
     286              :          |                │           ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     287              :          |                │              ╰─ parent: (1): stack region
     288              :          |                │                 ╰─ parent: (0): root region
     289              :          |                ╰─ baseline: (690): untracked_bit_contents
     290              :          |                   ╰─ maybe live values
     291              :          |                      ├─ (605): bit_vector_from_svalue[size: 1 byte]
     292              :          |                      │  ╰─ m_sval: (604): ‘char’: initial_svalue
     293              :          |                      │     ├─ value_range: {[irange] char VARYING}
     294              :          |                      │     ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
     295              :          |                      │        ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     296              :          |                      │           ╰─ {as above; descendents: 3, depth: 3}
     297              :          |                      ├─ (645): bit_vector_from_svalue[size: 1 byte]
     298              :          |                      │  ╰─ m_sval: (644): ‘char’: initial_svalue
     299              :          |                      │     ├─ value_range: {[irange] char VARYING}
     300              :          |                      │     ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
     301              :          |                      │        ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     302              :          |                      │           ╰─ {as above; descendents: 3, depth: 3}
     303              :          |                      ├─ (657): bit_vector_from_svalue[size: 1 byte]
     304              :          |                      │  ╰─ m_sval: (656): ‘char’: initial_svalue
     305              :          |                      │     ├─ value_range: {[irange] char VARYING}
     306              :          |                      │     ╰─ m_reg: (655): ‘char’: decl_region(‘d_62(D)’)
     307              :          |                      │        ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     308              :          |                      │           ╰─ {as above; descendents: 3, depth: 3}
     309              :          |                      ╰─ (676): bit_vector_from_svalue[size: 1 byte]
     310              :          |                         ╰─ m_sval: (675): ‘char’: initial_svalue
     311              :          |                            ├─ value_range: {[irange] char VARYING}
     312              :          |                            ╰─ m_reg: (674): ‘char’: decl_region(‘e_69(D)’)
     313              :          |                               ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
     314              :          |                                  ╰─ {as above; descendents: 3, depth: 3}
     315              : */
     316              : 
     317              : 
     318              : namespace ana {
     319              : 
     320              : /* A class for keeping track of aspects of a program_state that we don't
     321              :    know about, to avoid false positives about leaks.
     322              : 
     323              :    Consider:
     324              : 
     325              :       p->field = malloc (1024);
     326              :       q->field = NULL;
     327              : 
     328              :    where we don't know whether or not p and q point to the same memory,
     329              :    and:
     330              : 
     331              :       p->field = malloc (1024);
     332              :       unknown_fn (p);
     333              : 
     334              :    In both cases, the svalue for the address of the allocated buffer
     335              :    goes from being bound to p->field to not having anything explicitly bound
     336              :    to it.
     337              : 
     338              :    Given that we conservatively discard bindings due to possible aliasing or
     339              :    calls to unknown function, the store loses references to svalues,
     340              :    but these svalues could still be live.  We don't want to warn about
     341              :    them leaking - they're effectively in a "maybe live" state.
     342              : 
     343              :    This "maybe live" information is somewhat transient.
     344              : 
     345              :    We don't want to store this "maybe live" information in the program_state,
     346              :    region_model, or store, since we don't want to bloat these objects (and
     347              :    potentially bloat the exploded_graph with more nodes).
     348              :    However, we can't store it in the region_model_context, as these context
     349              :    objects sometimes don't last long enough to be around when comparing the
     350              :    old vs the new state.
     351              : 
     352              :    This class is a way to track a set of such svalues, so that we can
     353              :    temporarily capture that they are in a "maybe live" state whilst
     354              :    comparing old and new states.  */
     355              : 
     356       956689 : class uncertainty_t
     357              : {
     358              : public:
     359              :   typedef hash_set<const symbolic::value_node *>::iterator iterator;
     360              : 
     361              :   void on_maybe_bound_value (const symbolic::value_node &val);
     362              :   void on_mutable_value_at_unknown_call (const symbolic::value_node &val);
     363              : 
     364              :   bool unknown_sm_state_p (const svalue *sval);
     365              : 
     366              :   void add_bit_contents (const symbolic::bit_contents &bc);
     367              : 
     368              :   void dump () const;
     369              :   void dump_to_logger (logger &) const;
     370              : 
     371              :   std::unique_ptr<text_art::tree_widget>
     372              :   make_dump_widget (symbolic::node_dump_state &nds) const;
     373              : 
     374       383020 :   iterator begin_maybe_bound_svals () const
     375              :   {
     376       383020 :     return m_maybe_bound_vals.begin ();
     377              :   }
     378       410211 :   iterator end_maybe_bound_svals () const
     379              :   {
     380       410211 :     return m_maybe_bound_vals.end ();
     381              :   }
     382              : 
     383              : private:
     384              : 
     385              :   /* Values that might or might not still be bound.  */
     386              :   hash_set<const symbolic::value_node *> m_maybe_bound_vals;
     387              : 
     388              :   /* Values that have mutable sm-state at unknown calls.  */
     389              :   hash_set<const  symbolic::value_node *> m_mutable_at_unknown_call_vals;
     390              : };
     391              : 
     392              : class byte_range;
     393              : 
     394              : // TODO: eliminate this in favor of concrete_bit_range:
     395              : /* A concrete range of bits.  */
     396              : 
     397              : struct bit_range
     398              : {
     399          146 :   bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
     400          194 :   : m_start_bit_offset (start_bit_offset),
     401          178 :     m_size_in_bits (size_in_bits)
     402              :   {}
     403              : 
     404              :   void dump_to_pp (pretty_printer *pp) const;
     405              :   void dump () const;
     406              : 
     407              :   std::unique_ptr<json::object> to_json () const;
     408              : 
     409            0 :   bool empty_p () const
     410              :   {
     411            0 :     return m_size_in_bits == 0;
     412              :   }
     413              : 
     414          354 :   bit_offset_t get_start_bit_offset () const
     415              :   {
     416          186 :     return m_start_bit_offset;
     417              :   }
     418            8 :   bit_offset_t get_next_bit_offset () const
     419              :   {
     420          104 :     return m_start_bit_offset + m_size_in_bits;
     421              :   }
     422            0 :   bit_offset_t get_last_bit_offset () const
     423              :   {
     424            0 :     gcc_assert (!empty_p ());
     425            0 :     return get_next_bit_offset () - 1;
     426              :   }
     427              : 
     428            0 :   bool contains_p (bit_offset_t offset) const
     429              :   {
     430            0 :     return (offset >= get_start_bit_offset ()
     431            0 :             && offset < get_next_bit_offset ());
     432              :   }
     433              : 
     434              :   bool contains_p (const bit_range &other, bit_range *out) const;
     435              : 
     436              :   bool operator== (const bit_range &other) const
     437              :   {
     438              :     return (m_start_bit_offset == other.m_start_bit_offset
     439              :             && m_size_in_bits == other.m_size_in_bits);
     440              :   }
     441              : 
     442           88 :   bool intersects_p (const bit_range &other) const
     443              :   {
     444           88 :     return (get_start_bit_offset () < other.get_next_bit_offset ()
     445          160 :             && other.get_start_bit_offset () < get_next_bit_offset ());
     446              :   }
     447              :   bool intersects_p (const bit_range &other,
     448              :                      bit_size_t *out_num_overlap_bits) const;
     449              :   bool intersects_p (const bit_range &other,
     450              :                      bit_range *out_this,
     451              :                      bit_range *out_other) const;
     452              : 
     453              :   bool exceeds_p (const bit_range &other,
     454              :                   bit_range *out_overhanging_bit_range) const;
     455              : 
     456              :   bool falls_short_of_p (bit_offset_t offset,
     457              :                          bit_range *out_fall_short_bits) const;
     458              : 
     459              :   static int cmp (const bit_range &br1, const bit_range &br2);
     460              : 
     461              :   bit_range operator- (bit_offset_t offset) const;
     462              : 
     463              :   bool as_byte_range (byte_range *out) const;
     464              : 
     465              :   bool
     466              :   operator< (const bit_range &other) const
     467              :   {
     468              :     if (m_start_bit_offset < other.m_start_bit_offset)
     469              :       return true;
     470              :     if (m_start_bit_offset > other.m_start_bit_offset)
     471              :       return false;
     472              :     return (m_size_in_bits < other.m_size_in_bits);
     473              :   }
     474              : 
     475              :   hashval_t hash () const
     476              :   {
     477              :     inchash::hash hstate;
     478              :     hstate.add_wide_int (m_start_bit_offset);
     479              :     hstate.add_wide_int (m_size_in_bits);
     480              :     return hstate.end ();
     481              :   }
     482              : 
     483              :   bit_offset_t m_start_bit_offset;
     484              :   bit_size_t m_size_in_bits;
     485              : };
     486              : 
     487              : inline concrete::range<integer_with_unit<units::bit>>
     488          130 : convert_from_bit_range (bit_range old_bits)
     489              : {
     490          130 :   return concrete::range<integer_with_unit<units::bit>>
     491          260 :     (convert_from_bit_offset_t (old_bits.get_start_bit_offset ()),
     492          260 :      convert_from_bit_size_t (old_bits.m_size_in_bits));
     493              : }
     494              : 
     495              : inline bit_range
     496              : convert_to_bit_range (concrete::range<integer_with_unit<units::bit>> new_bits)
     497              : {
     498              :   return bit_range
     499              :     (convert_to_bit_offset_t (new_bits.get_start_offset ()),
     500              :      convert_to_bit_size_t (new_bits.get_size ()));
     501              : }
     502              : 
     503              : // TODO: eliminate this in favor of concrete_byte_range:
     504              : /* A concrete range of bytes.  */
     505              : 
     506              : struct byte_range
     507              : {
     508            0 :   byte_range (byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
     509            0 :   : m_start_byte_offset (start_byte_offset),
     510            0 :     m_size_in_bytes (size_in_bytes)
     511              :   {}
     512              : 
     513              :   void dump_to_pp (pretty_printer *pp) const;
     514              :   void dump () const;
     515              : 
     516              :   std::unique_ptr<json::object> to_json () const;
     517              : 
     518            0 :   bool empty_p () const
     519              :   {
     520            0 :     return m_size_in_bytes == 0;
     521              :   }
     522              : 
     523            0 :   bool contains_p (byte_offset_t offset) const
     524              :   {
     525            0 :     return (offset >= get_start_byte_offset ()
     526            0 :             && offset < get_next_byte_offset ());
     527              :   }
     528              :   bool contains_p (const byte_range &other, byte_range *out) const;
     529              : 
     530              :   bool operator== (const byte_range &other) const
     531              :   {
     532              :     return (m_start_byte_offset == other.m_start_byte_offset
     533              :             && m_size_in_bytes == other.m_size_in_bytes);
     534              :   }
     535              : 
     536            0 :   byte_offset_t get_start_byte_offset () const
     537              :   {
     538            0 :     return m_start_byte_offset;
     539              :   }
     540            0 :   byte_offset_t get_next_byte_offset () const
     541              :   {
     542            0 :     return m_start_byte_offset + m_size_in_bytes;
     543              :   }
     544            0 :   byte_offset_t get_last_byte_offset () const
     545              :   {
     546            0 :     gcc_assert (!empty_p ());
     547            0 :     return m_start_byte_offset + m_size_in_bytes - 1;
     548              :   }
     549              : 
     550              :   bit_range as_bit_range () const
     551              :   {
     552              :     return bit_range (m_start_byte_offset * BITS_PER_UNIT,
     553              :                       m_size_in_bytes * BITS_PER_UNIT);
     554              :   }
     555              : 
     556              :   bit_offset_t get_start_bit_offset () const
     557              :   {
     558              :     return m_start_byte_offset * BITS_PER_UNIT;
     559              :   }
     560              :   bit_offset_t get_next_bit_offset () const
     561              :   {
     562              :     return get_next_byte_offset () * BITS_PER_UNIT;
     563              :   }
     564              :   bit_size_t get_size_in_bits () const
     565              :   {
     566              :     return m_size_in_bytes * BITS_PER_UNIT;
     567              :   }
     568              : 
     569              :   static int cmp (const byte_range &br1, const byte_range &br2);
     570              : 
     571              :   byte_offset_t m_start_byte_offset;
     572              :   byte_size_t m_size_in_bytes;
     573              : };
     574              : 
     575              : /* All of the bindings within a store for regions that share the same
     576              :    base region.
     577              : 
     578              :    Invariants:
     579              :    - the region must be a base region
     580              :    - region->tracked_p () must be true
     581              :    - region->symbolic_for_unknown_ptr_p () must be false (we must not be
     582              :      dereferencing an UNKNOWN ptr).  */
     583              : 
     584              : class binding_cluster
     585              : {
     586              : public:
     587              :   friend class store;
     588              : 
     589              :   binding_cluster (symbolic::node_manager &node_mgr,
     590              :                    const region *base_region,
     591              :                    const symbolic::bit_contents &contents);
     592              :   binding_cluster (const binding_cluster &other);
     593              :   binding_cluster& operator=(const binding_cluster &other);
     594              : 
     595              :   bool operator== (const binding_cluster &other) const;
     596      1908648 :   bool operator!= (const binding_cluster &other) const
     597              :   {
     598      1908648 :     return !(*this == other);
     599              :   }
     600              : 
     601              :   hashval_t hash () const;
     602              : 
     603              :   bool symbolic_p () const;
     604              : 
     605          172 :   const region *get_base_region () const { return m_base_region; }
     606              : 
     607              :   void dump () const;
     608              : 
     609              :   void validate () const;
     610              : 
     611              :   std::unique_ptr<json::object> to_json () const;
     612              : 
     613              :   std::unique_ptr<text_art::tree_widget>
     614              :   make_dump_widget (symbolic::node_dump_state &nds) const;
     615              : 
     616              :   const symbolic::bit_vector &
     617              :   get_bits (symbolic_bit_range bit_range) const;
     618              : 
     619              :   void
     620              :   set_bits (symbolic_bit_range bit_range,
     621              :             const symbolic::bit_vector &bits,
     622              :             uncertainty_t *uncertainty);
     623              : 
     624              :   const symbolic::bit_contents &
     625        10897 :   get_bit_contents () const { return *m_contents; }
     626              : 
     627              :   void
     628         6467 :   set_bit_contents (const symbolic::bit_contents &bc)
     629              :   {
     630         6467 :     m_contents = &bc;
     631              :   }
     632              : 
     633              :   void mark_as_untracked (symbolic::node_manager &node_mgr,
     634              :                           uncertainty_t *uncertainty,
     635              :                           value_set *maybe_live_values);
     636              :   void purge_state_involving (const symbolic::node &node);
     637              : 
     638              :   iter_result
     639              :   for_each_value (iter_result (*cb) (const symbolic::value_node &val,
     640              :                                      void *user_data),
     641              :                   void *user_data) const;
     642              : 
     643              :   static bool can_merge_p (const binding_cluster *cluster_a,
     644              :                            const binding_cluster *cluster_b,
     645              :                            binding_cluster *out_cluster,
     646              :                            store *out_store,
     647              :                            model_merger *merger);
     648              :   void make_unknown_relative_to (const binding_cluster *other_cluster,
     649              :                                  store *out_store,
     650              :                                  baseline_state bs);
     651              : 
     652              :   void mark_as_escaped ();
     653              :   void on_unknown_fncall (const gcall &call, 
     654              :                           const conjured_purge &p);
     655              :   void
     656              :   mark_region_as_conjured (const gimple &stmt,
     657              :                            const conjured_purge &p);
     658              : 
     659              :   void on_asm (const gasm *stmt, 
     660              :                const conjured_purge &p);
     661              : 
     662              :   bool escaped_p () const;
     663       120862 :   bool touched_p () const { return m_touched; }
     664              : 
     665              :   bool redundant_p (const store &store_,
     666              :                     baseline_state bs) const;
     667              : 
     668              :   void get_representative_path_vars (const region_model *model,
     669              :                                      value_set *visited,
     670              :                                      const region *base_reg,
     671              :                                      const svalue *sval,
     672              :                                      logger *logger,
     673              :                                      auto_vec<path_var> *out_pvs) const;
     674              : 
     675              :   void
     676              :   poison_any_pointers_to_descendents (const region *reg,
     677              :                                       enum poison_kind pkind);
     678              : 
     679              :   bool
     680              :   bits_live_p (const symbolic::bit_vector_from_ubc &bv_from_ubc) const;
     681              : 
     682              : private:
     683              :   symbolic::node_manager &m_node_mgr;
     684              : 
     685              :   const region *m_base_region;
     686              : 
     687              :   const symbolic::bit_contents *m_contents;
     688              : 
     689              :   /* Has a pointer to this cluster "escaped" into a part of the program
     690              :      we don't know about (via a call to a function with an unknown body,
     691              :      or by being passed in as a pointer param of a "top-level" function call).
     692              :      Such regions could be overwritten when other such functions are called,
     693              :      even if the region is no longer reachable by pointers that we are
     694              :      tracking. */
     695              :   bool m_escaped;
     696              : 
     697              :   /* Has this cluster been written to via a symbolic binding?
     698              :      If so, then we don't know anything about unbound subregions,
     699              :      so we can't use initial_svalue, treat them as uninitialized, or
     700              :      inherit values from a parent region.  */
     701              :   bool m_touched;
     702              : };
     703              : 
     704              : /* The mapping from regions to svalues.
     705              :    This is actually expressed by subdividing into clusters, to better
     706              :    handle aliasing.  */
     707              : 
     708              : class store
     709              : {
     710              : public:
     711              :   typedef hash_map <const region *, binding_cluster *> cluster_map_t;
     712              : 
     713              :   store (symbolic::node_manager &node_mgr);
     714              :   store (const store &other);
     715              :   ~store ();
     716              : 
     717              :   store &operator= (const store &other);
     718              : 
     719              :   bool operator== (const store &other) const;
     720       437680 :   bool operator!= (const store &other) const
     721              :   {
     722       437680 :     return !(*this == other);
     723              :   }
     724              : 
     725              :   hashval_t hash () const;
     726              : 
     727              :   void dump () const;
     728              :   void summarize_to_pp (pretty_printer *pp, bool simple) const;
     729              : 
     730              :   void validate () const;
     731              : 
     732              :   std::unique_ptr<json::object> to_json () const;
     733              : 
     734              :   std::unique_ptr<text_art::tree_widget>
     735              :   make_dump_widget (symbolic::node_dump_state &nds) const;
     736              : 
     737              :   const symbolic::bit_vector &
     738              :   get_bits (const symbolic::memory_range &mem_range,
     739              :             baseline_state bs) const;
     740              : 
     741              :   const symbolic::bit_contents &
     742              :   get_bit_contents (const region &base_reg,
     743              :                     baseline_state bs) const;
     744              : 
     745            0 :   bool called_unknown_fn_p () const { return m_called_unknown_fn; }
     746              : 
     747              :   void
     748              :   set_bits (const region *lhs_reg,
     749              :             const symbolic::bit_vector &bv,
     750              :             uncertainty_t *uncertainty,
     751              :             const region_model &model);
     752              : 
     753              :   void
     754              :   set_bits (const symbolic::memory_range &mem_range,
     755              :             const symbolic::bit_vector &bv,
     756              :             uncertainty_t *uncertainty,
     757              :             const region_model &model);
     758              : 
     759              :   void
     760              :   set_bit_contents_raw (const region &base_reg,
     761              :                         const symbolic::bit_contents &bc,
     762              :                         const region_model &model);
     763              : 
     764              :   void clobber_region (const region *reg,
     765              :                        baseline_state bs,
     766              :                        region_model_manager &rmm);
     767              :   void purge_region (const region *reg);
     768              :   void mark_region_as_unknown (const region *reg,
     769              :                                baseline_state bs,
     770              :                                uncertainty_t *uncertainty,
     771              :                                const region_model &model);
     772              :   void purge_state_involving (const symbolic::node &node);
     773              : 
     774              :   const binding_cluster *get_cluster (const region *base_reg) const;
     775              :   binding_cluster *get_cluster (const region *base_reg);
     776              :   binding_cluster *
     777              :   get_or_create_cluster (const region *base_reg,
     778              :                          baseline_state bs);
     779              :   void purge_cluster (const region *base_reg);
     780              : 
     781              :   template <typename T>
     782      1276187 :   void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
     783              :                          T user_data) const
     784              :   {
     785      1276187 :     for (cluster_map_t::iterator iter = m_cluster_map.begin ();
     786      8430736 :          iter != m_cluster_map.end (); ++iter)
     787      7154549 :       cb ((*iter).first, user_data);
     788      1276187 :   }
     789              : 
     790              :   static bool can_merge_p (const store *store_a, const store *store_b,
     791              :                            store *out_store, 
     792              :                            model_merger *merger);
     793              : 
     794              :   void mark_as_escaped (const region *base_reg,
     795              :                         baseline_state bs);
     796              :   void on_unknown_fncall (const gcall &call, 
     797              :                           const conjured_purge &p);
     798              :   void
     799              :   mark_region_as_conjured (const region &base_reg,
     800              :                            baseline_state bs,
     801              :                            const gimple &stmt,
     802              :                            const conjured_purge &p);
     803              : 
     804              :   bool escaped_p (const region *reg) const;
     805              : 
     806              :   void get_representative_path_vars (const region_model *model,
     807              :                                      value_set *visited,
     808              :                                      const svalue *sval,
     809              :                                      logger *logger,
     810              :                                      auto_vec<path_var> *out_pvs) const;
     811              : 
     812       988442 :   cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
     813      6296164 :   cluster_map_t::iterator end () const { return m_cluster_map.end (); }
     814              : 
     815              :   tristate eval_alias (const region *base_reg_a,
     816              :                        const region *base_reg_b,
     817              :                        const region_model &model) const;
     818              : 
     819              :   void canonicalize ();
     820              :   void loop_replay_fixup (const store *other_store,
     821              :                           baseline_state bs,
     822              :                           region_model_manager *mgr);
     823              : 
     824              :   bool replay_call_summary (call_summary_replay &r,
     825              :                             const store &summary);
     826              :   bool replay_call_summary_cluster (call_summary_replay &r,
     827              :                                     const store &summary,
     828              :                                     const region *base_reg);
     829              :   bool
     830              :   replay_call_summary_bit_contents (call_summary_replay &r,
     831              :                                     const store &summary,
     832              :                                     const region &summary_base_reg,
     833              :                                     const region &caller_dest_reg,
     834              :                                     const symbolic::bit_contents &caller_bc);
     835              : 
     836              :   void on_maybe_live_values (const value_set &maybe_live_values,
     837              :                              baseline_state bs);
     838              : 
     839              :   bool
     840              :   bits_live_p (const symbolic::bit_vector_from_ubc &bv_from_ubc,
     841              :                const region_model &model) const;
     842              : 
     843              :   const symbolic::bit_contents &
     844              :   get_implicit_contents (const region &base_reg,
     845              :                          baseline_state bs) const;
     846              : 
     847              : private:
     848              :   const symbolic::bit_contents &
     849              :   get_baseline_contents (const region &base_reg,
     850              :                          baseline_state bs) const;
     851              : 
     852              :   tristate eval_alias_1 (const region *base_reg_a,
     853              :                          const region *base_reg_b,
     854              :                          const region_model &model) const;
     855              : 
     856              :   symbolic::node_manager &m_node_mgr;
     857              : 
     858              :   cluster_map_t m_cluster_map;
     859              : 
     860              :   /* If this is true, then unknown code has been called since the beginning
     861              :      of some path reaching this point in the analysis.  All externally
     862              :      visible non-readonly global variables that aren't currently modelled by
     863              :      the store are affected by this flag: they are implicitly either all in their
     864              :      "initial state" (m_called_unknown_fn==false), or all in unknown state
     865              :      (m_called_unknown_fn==true).
     866              : 
     867              :      This is to avoid having to mark (and thus explicitly track)
     868              :      every global when an unknown function is called; instead, they
     869              :      can be tracked implicitly.  */
     870              :   bool m_called_unknown_fn;
     871              : };
     872              : 
     873              : } // namespace ana
     874              : 
     875              : #endif /* GCC_ANALYZER_STORE_H */
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.