LCOV - code coverage report
Current view: top level - gcc/analyzer - symbolic-bit-contents.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 92.5 % 67 62
Test Date: 2026-11-14 16:39:50 Functions: 85.7 % 28 24
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Symbolic maps of bits e.g. "bytes [0-4): <bitvec>, bytes[16-20): <bitvec>"
       2              :    Copyright (C) 2019-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_SYMBOLIC_BIT_MAP_H
      22              : #define GCC_ANALYZER_SYMBOLIC_BIT_MAP_H
      23              : 
      24              : #include "analyzer/concrete-ranges.h"
      25              : #include "analyzer/symbolic-ranges.h"
      26              : #include "analyzer/string-scan.h"
      27              : #include "analyzer/symbolic-bit-vectors.h"
      28              : 
      29              : namespace ana {
      30              : 
      31              : namespace symbolic {
      32              : 
      33              : /* Abstract base class for representing a total function from
      34              :    symbolic bit ranges to symbolic bit vectors i.e. the contents
      35              :    of a region of memory.
      36              : 
      37              :    e.g. - "what is the value of bytes [8..16)?"
      38              :    - "what is the value of bit[100000]?"
      39              :    - "what is the value of byte[x]?" (for symbolic x)
      40              : 
      41              :    It's permissable to get/set things at negative offsets e.g. for the
      42              :    case of negative offsets from a symbolic pointer.
      43              : 
      44              :    Any range checking happens at a higher level.
      45              : 
      46              :    This is purely-functional: setters return a reference to a bit_contents
      47              :    instance holding the update.
      48              : 
      49              :    The class hierarchy looks like this (using indentation to show
      50              :    inheritance):
      51              : 
      52              :    symbolic::bit_contents (abstract)
      53              :      symbolic::uniform_bit_contents (abstract): something that ignores the input range
      54              :        symbolic::uninit_contents (concrete singleton): uninitialized everywhere
      55              :        symbolic::untracked_bit_contents (concrete): unknown everywhere, has a set of possibly-live values
      56              :        symbolic::zero_contents (concrete singleton): zero everywhere
      57              :      symbolic::unfoldable_bit_contents (abstract): unfoldable; hands out bit_vector_from_ubc instances
      58              :        symbolic::baseline_bit_contents (concrete): the initial contents of regions without known sizes
      59              :        symbolic::conjured_bit_contents (concrete): a bit_contents arising from a stmt
      60              :        symbolic::named_test_bit_contents (concrete): for use in selftests
      61              :      symbolic::bit_overlay (abstract): a baseline overridden at some places
      62              :        symbolic::concrete_bit_overlay (concrete)
      63              :        symbolic::symbolic_bit_overlay (concrete)
      64              :      symbolic::offset_bit_contents (concrete): offsets the coordinates of another bit_contents
      65              : */
      66              : 
      67              : class bit_contents : public symbolic::node
      68              : {
      69              : public:
      70              :   enum class kind
      71              :   {
      72              :     uninit,
      73              :     untracked,
      74              :     zero,
      75              :     baseline,
      76              :     conjured,
      77              :     named_test,
      78              :     concrete_overlay,
      79              :     symbolic_overlay,
      80              :     offset
      81              :   };
      82              : 
      83              :   virtual enum kind get_kind () const = 0;
      84              : 
      85        95261 :   node_manager &get_node_mgr () const { return m_node_mgr; }
      86              : 
      87              :   bit_contents_manager &
      88       874823 :   get_bit_contents_manager () const
      89              :   {
      90       874823 :     return m_node_mgr.get_bit_contents_manager ();
      91              :   }
      92              : 
      93              :   bit_vector_manager &
      94      4260177 :   get_bit_vector_manager () const
      95              :   {
      96      2091015 :     return m_node_mgr.get_bit_vector_manager ();
      97              :   }
      98              : 
      99              :   virtual const uniform_bit_contents *
     100            9 :   dyn_cast_uniform_bit_contents () const { return nullptr; }
     101              : 
     102              :   virtual const baseline_bit_contents *
     103        62336 :   dyn_cast_baseline_bit_contents () const { return nullptr; }
     104              : 
     105              :   virtual const conjured_bit_contents *
     106        56033 :   dyn_cast_conjured_bit_contents () const { return nullptr; }
     107              : 
     108              :   virtual const concrete_bit_overlay *
     109       331005 :   dyn_cast_concrete_bit_overlay () const { return nullptr; }
     110              : 
     111              :   virtual const symbolic_bit_overlay *
     112            0 :   dyn_cast_symbolic_bit_overlay () const { return nullptr; }
     113              : 
     114              :   virtual const offset_bit_contents *
     115            9 :   dyn_cast_offset_bit_contents () const { return nullptr; }
     116              : 
     117              :   const char *
     118        11896 :   get_any_dump_color () const override { return "bit_contents"; }
     119              : 
     120              :   // Getters
     121              : 
     122              :   virtual const bit_vector &
     123              :   get_bits (const symbolic_bit_range &bit_range) const = 0;
     124              : 
     125              :   const bit_vector &
     126              :   get_bits (const concrete_bit_range &bit_range) const;
     127              : 
     128              :   const bit_vector &
     129              :   get_bytes (const concrete_byte_range &byte_range) const;
     130              : 
     131              :   const bit_vector &
     132              :   get_bytes (const symbolic_byte_range &byte_range) const;
     133              : 
     134              :   const bit_vector &
     135          328 :   get_byte (integer_with_unit<units::byte> byte_offset) const
     136              :   {
     137          984 :     return get_bytes (concrete_byte_range (byte_offset, 1_byte));
     138              :   }
     139              : 
     140              :   // Setters
     141              : 
     142              :   const bit_contents &
     143              :   set_bits (const symbolic_bit_range &bit_range,
     144              :             const bit_vector &bv,
     145              :             uncertainty_t *uncertainty) const;
     146              : 
     147              :   const bit_contents &
     148              :   set_bits (const concrete_bit_range &bit_range,
     149              :             const bit_vector &bv,
     150              :             uncertainty_t *uncertainty) const;
     151              : 
     152              :   const bit_contents &
     153              :   set_bytes (const symbolic_byte_range &byte_range,
     154              :              const bit_vector &bv,
     155              :              uncertainty_t *uncertainty) const;
     156              : 
     157              :   const bit_contents &
     158              :   set_bytes (const concrete_byte_range &byte_range,
     159              :              const bit_vector &bv,
     160              :              uncertainty_t *uncertainty) const;
     161              : 
     162              :   const bit_contents &
     163              :   set_byte (integer_with_unit<units::byte> byte_offset,
     164              :             uint8_t value,
     165              :             uncertainty_t *uncertainty) const;
     166              : 
     167              :   virtual string_scan
     168              :   scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
     169              :     const = 0;
     170              : 
     171              :   virtual void
     172              :   get_representative_path_vars (const region_model *model,
     173              :                                 value_set *visited,
     174              :                                 const region *base_reg,
     175              :                                 const svalue *sval,
     176              :                                 tree desired_type,
     177              :                                 logger *logger,
     178              :                                 auto_vec<path_var> *out_pvs) const = 0;
     179              : 
     180              :   virtual const bit_contents &
     181              :   poison_any_pointers_to_descendents (const region *reg,
     182              :                                       enum poison_kind pkind) const = 0;
     183              : 
     184              :   virtual const bit_contents &
     185              :   purge_state_involving (const symbolic::node &node) const = 0;
     186              : 
     187              :   virtual bool
     188              :   bits_live_p (const bit_vector_from_ubc &bv_from_ubc) const = 0;
     189              : 
     190              : 
     191              :   /* vfunc for use by bit_contents_manager::get_offset_bit_contents.  */
     192              :   virtual const bit_contents *
     193           13 :   maybe_fold_offset (const symbolic_bit_offset &) const
     194              :   {
     195           13 :     return nullptr;
     196              :   }
     197              : 
     198              :   static const bit_contents *
     199              :   can_merge_p (const bit_contents &bit_contents_a,
     200              :                const bit_contents &bit_contents_b,
     201              :                tree type,
     202              :                model_merger *merger);
     203              : 
     204              :   virtual bool
     205       110496 :   conjured_p () const { return false; }
     206              : 
     207              :   virtual iter_result
     208              :   for_each_value (iter_result (*cb) (const symbolic::value_node &val,
     209              :                                      void *user_data),
     210              :                   void *user_data) const = 0;
     211              : 
     212              :   value_set
     213              :   get_maybe_live_values () const;
     214              : 
     215              : protected:
     216       112748 :   bit_contents (complexity c, node_manager &node_mgr)
     217              :   : node (c, node_mgr.alloc_node_id ()),
     218            9 :     m_node_mgr (node_mgr)
     219              :   {
     220              :   }
     221              : 
     222              : private:
     223              :   node_manager &m_node_mgr;
     224              : };
     225              : 
     226              : /* Abstract subclass of bit_contents for those classes that have
     227              :    the same bit content everywhere, and thus ignore the input bit_range.  */
     228              : 
     229              : class uniform_bit_contents : public bit_contents
     230              : {
     231              : public:
     232              :   const uniform_bit_contents *
     233            0 :   dyn_cast_uniform_bit_contents () const final override { return this; }
     234              : 
     235              :   const bit_contents *
     236              :   maybe_fold_offset (const symbolic_bit_offset &bit_offset)
     237              :     const final override;
     238              : 
     239              :   iter_result
     240              :   for_each_value (iter_result (*cb) (const symbolic::value_node &val,
     241              :                                      void *user_data),
     242              :                   void *user_data) const override;
     243              : 
     244              : protected:
     245        12238 :   uniform_bit_contents (complexity c, node_manager &node_mgr)
     246         3420 :   : bit_contents (c, node_mgr)
     247              :   {
     248              :   }
     249              : };
     250              : 
     251              : /* Concrete subclass that's always uninitialized.  */
     252              : 
     253              : class uninit_contents : public uniform_bit_contents
     254              : {
     255              : public:
     256              :   uninit_contents (node_manager &node_mgr);
     257              : 
     258              :   enum kind
     259      1509876 :   get_kind () const final override
     260              :   {
     261      1509876 :     return bit_contents::kind::uninit;
     262              :   }
     263              : 
     264              :   const bit_vector &
     265              :   get_bits (const symbolic_bit_range &bit_range) const final override;
     266              : 
     267              :   void
     268              :   print_dump_widget_label (pretty_printer *pp) const final override;
     269              : 
     270              :   void
     271              :   add_dump_widget_children (text_art::tree_widget &,
     272              :                             node_dump_state &nds) const final override;
     273              : 
     274              :   void
     275              :   accept_node_visitor (node_visitor &v) const final override;
     276              : 
     277              :   std::unique_ptr<json::object>
     278              :   to_json () const final override;
     279              : 
     280              :   std::unique_ptr<diagnostics::markup::node>
     281              :   make_markup_node (markup_context &markup_ctxt) const final override;
     282              : 
     283              :   string_scan
     284              :   scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
     285              :     const final override;
     286              : 
     287              :   void
     288              :   get_representative_path_vars (const region_model *model,
     289              :                                 value_set *visited,
     290              :                                 const region *base_reg,
     291              :                                 const svalue *sval,
     292              :                                 tree desired_type,
     293              :                                 logger *logger,
     294              :                                 auto_vec<path_var> *out_pvs)
     295              :     const final override;
     296              : 
     297              :   const bit_contents &
     298              :   poison_any_pointers_to_descendents (const region *reg,
     299              :                                       enum poison_kind pkind)
     300              :     const final override;
     301              : 
     302              :   const bit_contents &
     303              :   purge_state_involving (const symbolic::node &node) const final override;
     304              : 
     305              :   bool
     306          211 :   bits_live_p (const bit_vector_from_ubc &) const final override
     307              :   {
     308          211 :     return false;
     309              :   }
     310              : };
     311              : 
     312              : /* Concrete subclass where the bits are unknown everywhere,
     313              :    with a set of possibly-live values.
     314              : 
     315              :    Consolidation/canonicalization:
     316              :    - every value stored in the set must have true for
     317              :      untracked_bit_contents::track_value_liveness_p (val); other
     318              :      value nodes are redundant to liveness and are never added
     319              :      to untracked_bit_contents::m_maybe_live.  */
     320              : 
     321              : class untracked_bit_contents : public uniform_bit_contents
     322              : {
     323              : public:
     324       134760 :   struct key
     325              :   {
     326       127920 :     key (value_set &&maybe_live) : m_maybe_live (maybe_live) {}
     327              : 
     328              :     value_set m_maybe_live;
     329              : 
     330              :     bool
     331              :     operator< (const key &other) const;
     332              : 
     333              :     complexity
     334              :     get_complexity () const;
     335              :   };
     336              : 
     337              :   untracked_bit_contents (node_manager &node_mgr, const key &k);
     338              : 
     339              :   enum kind
     340        16402 :   get_kind () const final override
     341              :   {
     342        16402 :     return bit_contents::kind::untracked;
     343              :   }
     344              : 
     345              :   const bit_vector &
     346              :   get_bits (const symbolic_bit_range &bit_range) const final override;
     347              : 
     348              :   void
     349              :   print_dump_widget_label (pretty_printer *pp) const final override;
     350              : 
     351              :   void
     352              :   add_dump_widget_children (text_art::tree_widget &,
     353              :                             node_dump_state &nds) const final override;
     354              : 
     355              :   void
     356              :   accept_node_visitor (node_visitor &v) const final override;
     357              : 
     358              :   std::unique_ptr<json::object>
     359              :   to_json () const final override;
     360              : 
     361              :   std::unique_ptr<diagnostics::markup::node>
     362              :   make_markup_node (markup_context &markup_ctxt) const final override;
     363              : 
     364              :   string_scan
     365              :   scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
     366              :     const final override;
     367              : 
     368              :   void
     369              :   get_representative_path_vars (const region_model *model,
     370              :                                 value_set *visited,
     371              :                                 const region *base_reg,
     372              :                                 const svalue *sval,
     373              :                                 tree desired_type,
     374              :                                 logger *logger,
     375              :                                 auto_vec<path_var> *out_pvs)
     376              :     const final override;
     377              : 
     378              :   const bit_contents &
     379              :   poison_any_pointers_to_descendents (const region *reg,
     380              :                                       enum poison_kind pkind)
     381              :     const final override;
     382              : 
     383              :   const bit_contents &
     384              :   purge_state_involving (const symbolic::node &node) const final override;
     385              : 
     386              :   bool
     387              :   bits_live_p (const bit_vector_from_ubc &) const final override;
     388              : 
     389              :   iter_result
     390              :   for_each_value (iter_result (*cb) (const symbolic::value_node &val,
     391              :                                      void *user_data),
     392              :                   void *user_data) const final override;
     393              : 
     394              :   const value_set &
     395              :   get_maybe_live () const { return m_maybe_live; }
     396              : 
     397              :   static bool
     398              :   track_value_liveness_p (const symbolic::value_node &val);
     399              : 
     400              :   static bool
     401              :   track_bit_vector_liveness_p (const symbolic::bit_vector &bv);
     402              : 
     403              :   static bool
     404              :   track_svalue_liveness_p (const svalue &val);
     405              : 
     406              : private:
     407              :   value_set m_maybe_live;
     408              : };
     409              : 
     410              : /* Concrete subclass that's a zero bit everywhere.  */
     411              : 
     412              : class zero_contents : public uniform_bit_contents
     413              : {
     414              : public:
     415              :   zero_contents (node_manager &node_mgr);
     416              : 
     417              :   enum kind
     418         1236 :   get_kind () const final override
     419              :   {
     420         1236 :     return bit_contents::kind::zero;
     421              :   }
     422              : 
     423              :   const bit_vector &
     424              :   get_bits (const symbolic_bit_range &bit_range) const final override;
     425              : 
     426              :   void
     427              :   print_dump_widget_label (pretty_printer *pp) const final override;
     428              : 
     429              :   void
     430              :   add_dump_widget_children (text_art::tree_widget &,
     431              :                             node_dump_state &nds) const final override;
     432              : 
     433              :   void
     434              :   accept_node_visitor (node_visitor &v) const final override;
     435              : 
     436              :   std::unique_ptr<json::object>
     437              :   to_json () const final override;
     438              : 
     439              :   std::unique_ptr<diagnostics::markup::node>
     440              :   make_markup_node (markup_context &markup_ctxt) const final override;
     441              : 
     442              :   string_scan
     443              :   scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
     444              :     const final override;
     445              : 
     446              :   void
     447              :   get_representative_path_vars (const region_model *model,
     448              :                                 value_set *visited,
     449              :                                 const region *base_reg,
     450              :                                 const svalue *sval,
     451              :                                 tree desired_type,
     452              :                                 logger *logger,
     453              :                                 auto_vec<path_var> *out_pvs)
     454              :     const final override;
     455              : 
     456              :   const bit_contents &
     457              :   poison_any_pointers_to_descendents (const region *reg,
     458              :                                       enum poison_kind pkind)
     459              :     const final override;
     460              : 
     461              :   const bit_contents &
     462              :   purge_state_involving (const symbolic::node &node) const final override;
     463              : 
     464              :   bool
     465            0 :   bits_live_p (const bit_vector_from_ubc &) const final override
     466              :   {
     467            0 :     return false;
     468              :   }
     469              : };
     470              : 
     471              : /* Abstract bit_contents subclass that can't be folded.
     472              :    Hands out bit_vector_from_ubc instances when its bits
     473              :    are queried.  */
     474              : 
     475              : class unfoldable_bit_contents : public bit_contents
     476              : {
     477              : public:
     478              :   const symbolic::bit_vector &
     479              :   get_bits (const symbolic_bit_range &bit_range) const override;
     480              : 
     481              :   string_scan
     482              :   scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
     483              :     const final override;
     484              : 
     485              :   bool
     486              :   bits_live_p (const bit_vector_from_ubc &bv_from_ubc) const final override;
     487              : 
     488              :   void
     489              :   get_representative_path_vars (const region_model *model,
     490              :                                 value_set *visited,
     491              :                                 const region *base_reg,
     492              :                                 const svalue *sval,
     493              :                                 tree desired_type,
     494              :                                 logger *logger,
     495              :                                 auto_vec<path_var> *out_pvs)
     496              :     const final override;
     497              : 
     498              : protected:
     499        20253 :   unfoldable_bit_contents (complexity c, node_manager &node_mgr)
     500         8042 :   : bit_contents (c, node_mgr)
     501              :   {}
     502              : 
     503              : private:
     504              :   using map_type = std::map<symbolic_bit_range,
     505              :                             std::unique_ptr<bit_vector_from_ubc>>;
     506              :   mutable map_type m_range_to_bv_map;
     507              : };
     508              : 
     509              : /* A bit_contents representing the initial content of a base region that
     510              :    doesn't have a meaningful size.
     511              : 
     512              :    Consolidation/canonicalization:
     513              :    - the base region must not have meaningful size (otherwise we can build
     514              :      an concrete_bit_overlay for its initial contents using initial_svalue).  */
     515              : 
     516              : class baseline_bit_contents : public unfoldable_bit_contents
     517              : {
     518              : public:
     519              :   baseline_bit_contents (node_manager &node_mgr, const baseline_key &k);
     520              : 
     521              :   enum kind
     522        25019 :   get_kind () const final override
     523              :   {
     524        25019 :     return bit_contents::kind::baseline;
     525              :   }
     526              : 
     527              :   const baseline_bit_contents *
     528       283658 :   dyn_cast_baseline_bit_contents () const final override { return this; }
     529              : 
     530              :   void
     531              :   print_dump_widget_label (pretty_printer *pp) const final override;
     532              : 
     533              :   void
     534              :   add_dump_widget_children (text_art::tree_widget &,
     535              :                             node_dump_state &) const final override;
     536              : 
     537              :   void
     538              :   accept_node_visitor (node_visitor &v) const final override;
     539              : 
     540              :   std::unique_ptr<json::object>
     541              :   to_json () const final override;
     542              : 
     543              :   std::unique_ptr<diagnostics::markup::node>
     544              :   make_markup_node (markup_context &markup_ctxt) const final override;
     545              : 
     546              :   const bit_contents &
     547              :   poison_any_pointers_to_descendents (const region *reg,
     548              :                                       enum poison_kind pkind)
     549              :     const final override;
     550              : 
     551              :   const bit_contents &
     552              :   purge_state_involving (const symbolic::node &node) const final override;
     553              : 
     554              :   iter_result
     555              :   for_each_value (iter_result (*cb) (const symbolic::value_node &val,
     556              :                                      void *user_data),
     557              :                   void *user_data) const final override;
     558              : 
     559              :   const baseline_key &
     560              :   get_baseline_key () const { return m_baseline_key; }
     561              : 
     562              : private:
     563              :   baseline_key m_baseline_key;
     564              : };
     565              : 
     566              : /* A defined bit_contents arising from a statement.
     567              : 
     568              :    For example, this is used for the values of regions of unknown size
     569              :    that may have been touched when calling an unknown function.
     570              : 
     571              :    The bit_contents captures a region as well as a stmt in order to avoid
     572              :    falsely  aliasing the various values that could arise in one statement.
     573              :    For example, after:
     574              :       unknown_fn (&a, &b);
     575              :    we want nodes to clobber a and b with, but we don't want to use the
     576              :    same node, or it would falsely implicitly assume that a == b.  */
     577              : 
     578              : class conjured_bit_contents : public unfoldable_bit_contents
     579              : {
     580              : public:
     581              :   struct key
     582              :   {
     583        25532 :     key (const gimple *stmt,
     584              :          const region *id_reg,
     585              :          unsigned idx)
     586        25532 :     : m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
     587              :     {
     588              :     }
     589              : 
     590              :     bool operator< (const key &other) const;
     591              : 
     592              :     complexity
     593              :     get_complexity () const;
     594              : 
     595              :     const gimple *m_stmt;
     596              :     const region *m_id_reg;
     597              :     unsigned m_idx;
     598              :   };
     599              : 
     600              :   conjured_bit_contents (node_manager &node_mgr, const key &k);
     601              : 
     602              :   enum kind
     603        10564 :   get_kind () const final override
     604              :   {
     605        10564 :     return bit_contents::kind::conjured;
     606              :   }
     607              : 
     608              :   const conjured_bit_contents *
     609        11005 :   dyn_cast_conjured_bit_contents () const final override { return this; }
     610              : 
     611              :   void
     612              :   print_dump_widget_label (pretty_printer *pp) const final override;
     613              : 
     614              :   void
     615              :   add_dump_widget_children (text_art::tree_widget &,
     616              :                             node_dump_state &) const final override;
     617              : 
     618              :   void
     619              :   accept_node_visitor (node_visitor &v) const final override;
     620              : 
     621              :   std::unique_ptr<json::object>
     622              :   to_json () const final override;
     623              : 
     624              :   std::unique_ptr<diagnostics::markup::node>
     625              :   make_markup_node (markup_context &markup_ctxt) const final override;
     626              : 
     627              :   const bit_contents &
     628              :   poison_any_pointers_to_descendents (const region *reg,
     629              :                                       enum poison_kind pkind)
     630              :     const final override;
     631              : 
     632              :   const bit_contents &
     633              :   purge_state_involving (const symbolic::node &node) const final override;
     634              : 
     635              :   bool
     636        15847 :   conjured_p () const final override { return true; }
     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 final override;
     642              : 
     643              :   const gimple *get_stmt () const { return m_stmt; }
     644        11005 :   const region *get_id_region () const { return m_id_reg; }
     645              :   unsigned get_index () const { return m_idx; }
     646              : 
     647              : private:
     648              :   const gimple *m_stmt;
     649              :   const region *m_id_reg;
     650              :   unsigned m_idx;
     651              : };
     652              : 
     653              : /* Concrete subclass of unfoldable_bit_contents for use in selftests.  */
     654              : 
     655              : #if CHECKING_P
     656              : 
     657              : class named_test_bit_contents : public unfoldable_bit_contents
     658              : {
     659              : public:
     660              :   named_test_bit_contents (node_manager &node_mgr, std::string name);
     661              : 
     662              :   enum kind
     663          656 :   get_kind () const final override
     664              :   {
     665          656 :     return bit_contents::kind::named_test;
     666              :   }
     667              : 
     668              :   void
     669              :   print_dump_widget_label (pretty_printer *pp) const final override;
     670              : 
     671              :   void
     672              :   add_dump_widget_children (text_art::tree_widget &,
     673              :                             node_dump_state &) const final override;
     674              : 
     675              :   void
     676              :   accept_node_visitor (node_visitor &v) const final override;
     677              : 
     678              :   std::unique_ptr<json::object>
     679              :   to_json () const final override;
     680              : 
     681              :   std::unique_ptr<diagnostics::markup::node>
     682              :   make_markup_node (markup_context &markup_ctxt) const final override;
     683              : 
     684              :   const bit_contents &
     685              :   poison_any_pointers_to_descendents (const region *reg,
     686              :                                       enum poison_kind pkind)
     687              :     const final override;
     688              : 
     689              :   const bit_contents &
     690              :   purge_state_involving (const symbolic::node &node) const final override;
     691              : 
     692              :   iter_result
     693              :   for_each_value (iter_result (*cb) (const symbolic::value_node &val,
     694              :                                      void *user_data),
     695              :                   void *user_data) const final override;
     696              : 
     697              :   const char *
     698              :   get_name () const { return m_name.c_str (); }
     699              : 
     700              : private:
     701              :   std::string m_name;
     702              : };
     703              : 
     704              : #endif /* #if CHECKING_P */
     705              : 
     706              : /* Abstract bit_contents subclasses that uses a baseline
     707              :    bit_contents in most of the domain, but overrides it at
     708              :    one or more places; subclasses provide the concrete implementation.
     709              : 
     710              :    Consolidation/canonicalization:
     711              :    - no nesting of overlays: the baseline must not itself be a bit_overlay.  */
     712              : 
     713              : class bit_overlay : public bit_contents
     714              : {
     715              : public:
     716              :   const bit_contents &
     717      6456232 :   get_baseline () const { return m_baseline; }
     718              : 
     719              : protected:
     720        80248 :   bit_overlay (complexity c, const bit_contents &baseline)
     721              :   : bit_contents (c, baseline.get_node_mgr ()),
     722        80248 :     m_baseline (baseline)
     723              :   {
     724              :   }
     725              : 
     726              : private:
     727              :   const bit_contents &m_baseline;
     728              : };
     729              : 
     730              : /* A sparse mapping from concrete bit ranges to symbolic bit maps,
     731              :    overlaid on an underlying baseline bit_contents.
     732              : 
     733              :    Has no size; bounds-checking must happen at a higher level.
     734              : 
     735              :    Consolidation/canonicalization:
     736              :    - must have at least one entry in the map
     737              :    - no nesting of overlays: the baseline must not itself be a bit_overlay.
     738              :    - bit ranges in the map are ordered by start offset
     739              :    - no overlapping of bit ranges
     740              :    - no redundant bindings: the bit_vector bound to RANGE must not equal
     741              :      BASELINE.get_bits(RANGE)
     742              :    - the size of each bit_vector must be concrete and match that of the bit
     743              :      range it is bound to
     744              :    - no leading concrete-sized child elements of a concat_bit_vector: these
     745              :      are canonicalized by splitting out into separate mappings from range
     746              :      to component bit_vector.  */
     747              : 
     748              : class concrete_bit_overlay : public bit_overlay
     749              : {
     750              : public:
     751       855908 :   struct key
     752              :   {
     753              :     const bit_contents *m_baseline;
     754              :     std::map<concrete_bit_range, const bit_vector &> m_concrete_range_map;
     755              : 
     756              :     bool
     757              :     operator< (const key &other) const;
     758              : 
     759              :     complexity
     760              :     get_complexity () const;
     761              : 
     762              :     void
     763              :     remove_redundant_bindings ();
     764              :   };
     765              : 
     766              :   const concrete_bit_overlay *
     767       184708 :   dyn_cast_concrete_bit_overlay () const final override { return this; }
     768              : 
     769              :   concrete_bit_overlay (const key &k);
     770              : 
     771              :   enum kind
     772         7708 :   get_kind () const final override
     773              :   {
     774         7708 :     return bit_contents::kind::concrete_overlay;
     775              :   }
     776              : 
     777            8 :   size_t size () const { return m_concrete_range_map.size (); }
     778              : 
     779              :   const bit_vector &
     780              :   get_bits (const symbolic_bit_range &bit_range) const final override;
     781              : 
     782              :   void
     783              :   print_dump_widget_label (pretty_printer *pp) const final override;
     784              : 
     785              :   void
     786              :   add_dump_widget_children (text_art::tree_widget &,
     787              :                             node_dump_state &nds) const final override;
     788              : 
     789              :   void
     790              :   accept_node_visitor (node_visitor &v) const final override;
     791              : 
     792              :   std::unique_ptr<json::object>
     793              :   to_json () const final override;
     794              : 
     795              :   std::unique_ptr<diagnostics::markup::node>
     796              :   make_markup_node (markup_context &markup_ctxt) const final override;
     797              : 
     798              :   string_scan
     799              :   scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
     800              :     const final override;
     801              : 
     802              :   void
     803              :   get_representative_path_vars (const region_model *model,
     804              :                                 value_set *visited,
     805              :                                 const region *base_reg,
     806              :                                 const svalue *sval,
     807              :                                 tree desired_type,
     808              :                                 logger *logger,
     809              :                                 auto_vec<path_var> *out_pvs)
     810              :     const final override;
     811              : 
     812              :   const bit_contents &
     813              :   poison_any_pointers_to_descendents (const region *reg,
     814              :                                       enum poison_kind pkind)
     815              :     const final override;
     816              : 
     817              :   const bit_contents &
     818              :   purge_state_involving (const symbolic::node &node) const final override;
     819              : 
     820              :   bool
     821              :   bits_live_p (const bit_vector_from_ubc &bv_from_ubc) const final override;
     822              : 
     823              :   iter_result
     824              :   for_each_value (iter_result (*cb) (const symbolic::value_node &val,
     825              :                                      void *user_data),
     826              :                   void *user_data) const final override;
     827              : 
     828              :   const bit_vector &
     829              :   get_concrete_bits (const concrete_bit_range &bit_range) const;
     830              : 
     831              :   const bit_contents &
     832              :   set_concrete_bits (const concrete_bit_range &bit_range,
     833              :                      const bit_vector &bv) const;
     834              : 
     835              :   const svalue *
     836              :   maybe_get_var_arg_svalue () const;
     837              : 
     838              :   static const bit_contents *
     839              :   can_merge_p (const bit_contents &bit_contents_a,
     840              :                const bit_contents &bit_contents_b,
     841              :                const bit_contents &shared_baseline,
     842              :                const concrete_bit_overlay *conc_bit_overlay_a,
     843              :                const concrete_bit_overlay *conc_bit_overlay_b,
     844              :                tree type,
     845              :                model_merger *merger);
     846              : 
     847              :   static std::map<concrete_bit_range, const bit_vector &>
     848              :   canonicalize_new_bit_vec (const concrete_bit_range &new_bit_range,
     849              :                             const bit_vector &bv);
     850              : 
     851              :   static std::map<concrete_bit_range, const bit_vector &>
     852              :   consolidate_adjacent (std::map<concrete_bit_range, const bit_vector &> map,
     853              :                         bit_vector_manager &bv_mgr);
     854              : 
     855              :   bool
     856              :   bit_offset_is_bound_p (concrete_bit_offset) const;
     857              : 
     858              :   /* Map from concrete ranges of bits to symbolic bit vectors.
     859              :      The sizes must match.
     860              :      By construction, the bit ranges do not overlap.  */
     861              :   std::map<concrete_bit_range, const bit_vector &> m_concrete_range_map;
     862              : };
     863              : 
     864              : /* A sparse mapping from symbolic bit ranges to symbolic bit vectors,
     865              :    overlaid on an underlying baseline bit_contents.
     866              : 
     867              :    Has no size; bounds-checking must happen at a higher level.
     868              : 
     869              :    Consolidation/canonicalization:
     870              :    - must have exactly one entry in the map (attempts to create more than
     871              :      one symbolic key ought to be folded into the baseline)
     872              :      TODO(can probably use this to greatly simplify this implementation,
     873              :      and possibly merge it with concrete_bit_overlay).
     874              :    - no nesting of overlays: the baseline must not itself be a bit_overlay.
     875              :    - bit ranges in the map are not allowed to have "unknown" start offset
     876              :      TODO(design): are they allowed to have "unknown" size?
     877              :    - bit ranges in the map are not allowed to be fully concrete
     878              :    - no redundant bindings: the bit_vector bound to RANGE must not equal
     879              :      BASELINE.get_bits(RANGE).
     880              :    - the size of each bit_vector must match that of the bit
     881              :      range it is bound to (this size may be either concrete or symbolic).  */
     882              : 
     883              : class symbolic_bit_overlay : public bit_overlay
     884              : {
     885              : public:
     886        23791 :   struct key
     887              :   {
     888              :     const bit_contents *m_baseline;
     889              :     std::map<symbolic_bit_range, const bit_vector &> m_symbolic_range_map;
     890              : 
     891              :     bool
     892              :     operator< (const key &other) const;
     893              : 
     894              :     complexity
     895              :     get_complexity () const;
     896              : 
     897              :     void
     898              :     remove_redundant_bindings ();
     899              :   };
     900              : 
     901              :   const symbolic_bit_overlay *
     902            0 :   dyn_cast_symbolic_bit_overlay () const final override { return this; }
     903              : 
     904              :   symbolic_bit_overlay (const key &k);
     905              : 
     906              :   enum kind
     907          770 :   get_kind () const final override
     908              :   {
     909          770 :     return bit_contents::kind::symbolic_overlay;
     910              :   }
     911              : 
     912              :   size_t size () const { return m_symbolic_range_map.size (); }
     913              : 
     914              :   const bit_vector &
     915              :   get_bits (const symbolic_bit_range &bit_range) const final override;
     916              : 
     917              :   void
     918              :   print_dump_widget_label (pretty_printer *pp) const final override;
     919              : 
     920              :   void
     921              :   add_dump_widget_children (text_art::tree_widget &,
     922              :                             node_dump_state &nds) const final override;
     923              : 
     924              :   void
     925              :   accept_node_visitor (node_visitor &v) const final override;
     926              : 
     927              :   std::unique_ptr<json::object>
     928              :   to_json () const final override;
     929              : 
     930              :   std::unique_ptr<diagnostics::markup::node>
     931              :   make_markup_node (markup_context &markup_ctxt) const final override;
     932              : 
     933              :   string_scan
     934              :   scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
     935              :     const final override;
     936              : 
     937              :   void
     938              :   get_representative_path_vars (const region_model *model,
     939              :                                 value_set *visited,
     940              :                                 const region *base_reg,
     941              :                                 const svalue *sval,
     942              :                                 tree desired_type,
     943              :                                 logger *logger,
     944              :                                 auto_vec<path_var> *out_pvs)
     945              :     const final override;
     946              : 
     947              :   const bit_contents &
     948              :   poison_any_pointers_to_descendents (const region *reg,
     949              :                                       enum poison_kind pkind)
     950              :     const final override;
     951              : 
     952              :   const bit_contents &
     953              :   purge_state_involving (const symbolic::node &node) const final override;
     954              : 
     955              :   bool
     956              :   bits_live_p (const bit_vector_from_ubc &bv_from_ubc) const final override;
     957              : 
     958              :   iter_result
     959              :   for_each_value (iter_result (*cb) (const symbolic::value_node &val,
     960              :                                      void *user_data),
     961              :                   void *user_data) const final override;
     962              : 
     963              :   /* Map from symbolic ranges of bits to symbolic bit vectors.
     964              :      Note that in the current implementation the map has at most one
     965              :      entry, suggsesting future simplification possibilities.  */
     966              :   std::map<symbolic_bit_range, const bit_vector &> m_symbolic_range_map;
     967              : };
     968              : 
     969              : /* A bit_contents instance that offsets the coordinates of another
     970              :    bit_contents instance.
     971              : 
     972              :    Consolidation/canonicalization:
     973              :    - the offset cannot be zero
     974              :    - the inner bit_contents cannot be uniform
     975              :    - no nesting: the inner bit_contents cannot be an offset_bit_contents
     976              :      (we can simply fold by adding the offsets).  */
     977              : 
     978              : class offset_bit_contents : public bit_contents
     979              : {
     980              : public:
     981              :   struct key
     982              :   {
     983              :     const bit_contents *m_inner_bc;
     984              :     const symbolic_bit_offset *m_bit_offset;
     985              : 
     986              :     bool
     987              :     operator< (const key &other) const;
     988              : 
     989              :     complexity
     990              :     get_complexity () const;
     991              :   };
     992              : 
     993              :   const offset_bit_contents *
     994            4 :   dyn_cast_offset_bit_contents () const final override { return this; }
     995              : 
     996              :   offset_bit_contents (node_manager &node_mgr, const key &k);
     997              : 
     998              :   enum kind
     999            5 :   get_kind () const final override
    1000              :   {
    1001            5 :     return bit_contents::kind::offset;
    1002              :   }
    1003              : 
    1004              :   const bit_vector &
    1005              :   get_bits (const symbolic_bit_range &bit_range) const final override;
    1006              : 
    1007              :   void
    1008              :   print_dump_widget_label (pretty_printer *pp) const final override;
    1009              : 
    1010              :   void
    1011              :   add_dump_widget_children (text_art::tree_widget &,
    1012              :                             node_dump_state &nds) const final override;
    1013              : 
    1014              :   void
    1015              :   accept_node_visitor (node_visitor &v) const final override;
    1016              : 
    1017              :   std::unique_ptr<json::object>
    1018              :   to_json () const final override;
    1019              : 
    1020              :   std::unique_ptr<diagnostics::markup::node>
    1021              :   make_markup_node (markup_context &markup_ctxt) const final override;
    1022              : 
    1023              :   string_scan
    1024              :   scan_for_first_zero_byte (string_scan::byte_offset_type start_byte_offset)
    1025              :     const final override;
    1026              : 
    1027              :   void
    1028              :   get_representative_path_vars (const region_model *model,
    1029              :                                 value_set *visited,
    1030              :                                 const region *base_reg,
    1031              :                                 const svalue *sval,
    1032              :                                 tree desired_type,
    1033              :                                 logger *logger,
    1034              :                                 auto_vec<path_var> *out_pvs)
    1035              :     const final override;
    1036              : 
    1037              :   const bit_contents &
    1038              :   poison_any_pointers_to_descendents (const region *reg,
    1039              :                                       enum poison_kind pkind)
    1040              :     const final override;
    1041              : 
    1042              :   const bit_contents &
    1043              :   purge_state_involving (const symbolic::node &node) const final override;
    1044              : 
    1045              :   bool
    1046              :   bits_live_p (const bit_vector_from_ubc &bv_from_ubc) const final override;
    1047              : 
    1048              :   iter_result
    1049              :   for_each_value (iter_result (*cb) (const symbolic::value_node &val,
    1050              :                                      void *user_data),
    1051              :                   void *user_data) const final override;
    1052              : 
    1053              :   const bit_contents *
    1054              :   maybe_fold_offset (const symbolic_bit_offset &bit_offset)
    1055              :     const final override;
    1056              : 
    1057              :   const bit_contents &
    1058            4 :   get_inner_bit_contents () const { return m_inner_bc; }
    1059              : 
    1060              :   const symbolic_bit_offset &
    1061            4 :   get_bit_offset () const { return m_bit_offset; }
    1062              : 
    1063              : private:
    1064              :   const bit_contents &m_inner_bc;
    1065              :   const symbolic_bit_offset &m_bit_offset;
    1066              : };
    1067              : 
    1068              : /* A class with responsibility for allocating/consolidating
    1069              :    bit_contents instances.  A singleton relative to a node_manager.  */
    1070              : 
    1071              : class bit_contents_manager
    1072              : {
    1073              : public:
    1074              :   bit_contents_manager (node_manager &node_mgr);
    1075              : 
    1076              :   bit_contents_manager (const bit_contents_manager &) = delete;
    1077              : 
    1078              :   const uninit_contents &
    1079            4 :   get_uninitialized () const { return m_uninit_contents; }
    1080              : 
    1081              :   const bit_contents &
    1082              :   get_untracked (value_set maybe_live);
    1083              : 
    1084              :   const zero_contents &
    1085          206 :   get_all_zeros () const { return m_zero_contents; }
    1086              : 
    1087              :   const bit_contents &
    1088              :   set_bits (const bit_contents &original,
    1089              :             const symbolic_bit_range &bit_range,
    1090              :             const bit_vector &bv,
    1091              :             uncertainty_t *uncertainty);
    1092              : 
    1093              :   const bit_contents &
    1094              :   set_bits (const bit_contents &original,
    1095              :             const concrete_bit_range &bit_range,
    1096              :             const bit_vector &bv,
    1097              :             uncertainty_t *uncertainty);
    1098              : 
    1099              :   const bit_contents &
    1100              :   get_concrete_bit_overlay (concrete_bit_overlay::key k,
    1101              :                             uncertainty_t *uncertainty);
    1102              : 
    1103              :   const bit_contents &
    1104              :   get_symbolic_bit_overlay (symbolic_bit_overlay::key k,
    1105              :                             uncertainty_t *uncertainty);
    1106              : 
    1107              :   const bit_contents &
    1108              :   get_bit_contents_for_constant (tree tree_cst);
    1109              : 
    1110              :   const bit_contents &
    1111              :   get_baseline_contents (const region &base_reg,
    1112              :                          baseline_state bs);
    1113              : 
    1114              :   const bit_contents &
    1115              :   get_conjured_bit_contents (const region &base_reg,
    1116              :                              const gimple *stmt,
    1117              :                              const conjured_purge &p,
    1118              :                              unsigned idx = 0);
    1119              : 
    1120              : #if CHECKING_P
    1121              :   const bit_contents &
    1122              :   get_named_test_bit_contents (std::string name);
    1123              : #endif
    1124              : 
    1125              :   const bit_contents &
    1126              :   get_offset_bit_contents (const bit_contents &inner_bc,
    1127              :                            const symbolic_bit_offset &bit_offset);
    1128              : 
    1129              : private:
    1130              :   const bit_contents &
    1131              :   make_bit_contents_for_constant (tree tree_cst);
    1132              : 
    1133              :   const bit_contents &
    1134              :   make_baseline_contents (baseline_key k);
    1135              : 
    1136              :   node_manager &m_node_mgr;
    1137              : 
    1138              :   uninit_contents m_uninit_contents;
    1139              :   zero_contents m_zero_contents;
    1140              : 
    1141              :   std::map<untracked_bit_contents::key,
    1142              :            std::unique_ptr<untracked_bit_contents>> m_untracked_bit_contents;
    1143              : 
    1144              :   std::map<concrete_bit_overlay::key,
    1145              :            std::unique_ptr<concrete_bit_overlay>> m_concrete_bit_overlays;
    1146              : 
    1147              :   std::map<symbolic_bit_overlay::key,
    1148              :            std::unique_ptr<symbolic_bit_overlay>> m_symbolic_bit_overlays;
    1149              : 
    1150              :   std::map<conjured_bit_contents::key,
    1151              :            std::unique_ptr<conjured_bit_contents>> m_conjured_map;
    1152              :   std::vector<std::unique_ptr<unfoldable_bit_contents>> m_unfoldable_bit_contents;
    1153              : 
    1154              :   std::map<offset_bit_contents::key,
    1155              :            std::unique_ptr<offset_bit_contents>> m_offset_map;
    1156              : 
    1157              :   // Cached lookups
    1158              :   std::map<tree, const bit_contents &> m_bit_contents_for_constants;
    1159              :   std::map<baseline_key, const bit_contents &> m_baseline_contents;
    1160              : };
    1161              : 
    1162              : } // namespace ana::symbolic
    1163              : } // namespace ana
    1164              : 
    1165              : #endif /* GCC_ANALYZER_SYMBOLIC_BIT_MAP_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.