LCOV - code coverage report
Current view: top level - gcc/analyzer - program-state.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 47 47 100.0 %
Date: 2020-03-28 11:57:23 Functions: 1 1 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Classes for representing the state of interest at a given path of analysis.
       2                 :            :    Copyright (C) 2019-2020 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_PROGRAM_STATE_H
      22                 :            : #define GCC_ANALYZER_PROGRAM_STATE_H
      23                 :            : 
      24                 :            : namespace ana {
      25                 :            : 
      26                 :            : /* Data shared by all program_state instances.  */
      27                 :            : 
      28                 :            : class extrinsic_state
      29                 :            : {
      30                 :            : public:
      31                 :        385 :   extrinsic_state (auto_delete_vec <state_machine> &checkers)
      32                 :        385 :   : m_checkers (checkers)
      33                 :            :   {
      34                 :            :   }
      35                 :            : 
      36                 :     761910 :   const state_machine &get_sm (int idx) const
      37                 :            :   {
      38                 :     678108 :     return *m_checkers[idx];
      39                 :            :   }
      40                 :            : 
      41                 :         84 :   const char *get_name (int idx) const
      42                 :            :   {
      43                 :         84 :     return m_checkers[idx]->get_name ();
      44                 :            :   }
      45                 :            : 
      46                 :     487928 :   unsigned get_num_checkers () const { return m_checkers.length (); }
      47                 :            : 
      48                 :            :   void dump_to_pp (pretty_printer *pp) const;
      49                 :            :   void dump_to_file (FILE *outf) const;
      50                 :            :   void dump () const;
      51                 :            : 
      52                 :            : private:
      53                 :            :   /* The state machines.  */
      54                 :            :   auto_delete_vec <state_machine> &m_checkers;
      55                 :            : };
      56                 :            : 
      57                 :            : } // namespace ana
      58                 :            : 
      59                 :            : template <> struct default_hash_traits<svalue_id>
      60                 :            : : public pod_hash_traits<svalue_id>
      61                 :            : {
      62                 :            :   static const bool empty_zero_p = false;
      63                 :            : };
      64                 :            : 
      65                 :            : template <>
      66                 :            : inline hashval_t
      67                 :     486097 : pod_hash_traits<svalue_id>::hash (value_type v)
      68                 :            : {
      69                 :     486097 :   return v.as_int ();
      70                 :            : }
      71                 :            : 
      72                 :            : template <>
      73                 :            : inline bool
      74                 :     301214 : pod_hash_traits<svalue_id>::equal (const value_type &existing,
      75                 :            :                                    const value_type &candidate)
      76                 :            : {
      77                 :     301214 :   return existing == candidate;
      78                 :            : }
      79                 :            : template <>
      80                 :            : inline void
      81                 :       7167 : pod_hash_traits<svalue_id>::mark_deleted (value_type &v)
      82                 :            : {
      83                 :       7167 :   v = svalue_id::from_int (-2);
      84                 :            : }
      85                 :            : template <>
      86                 :            : inline void
      87                 :   22579400 : pod_hash_traits<svalue_id>::mark_empty (value_type &v)
      88                 :            : {
      89                 :   22579400 :   v = svalue_id::null ();
      90                 :            : }
      91                 :            : template <>
      92                 :            : inline bool
      93                 :    8060296 : pod_hash_traits<svalue_id>::is_deleted (value_type v)
      94                 :            : {
      95                 :    8060296 :   return v.as_int () == -2;
      96                 :            : }
      97                 :            : template <>
      98                 :            : inline bool
      99                 :   55055600 : pod_hash_traits<svalue_id>::is_empty (value_type v)
     100                 :            : {
     101                 :   55055600 :   return v.null_p ();
     102                 :            : }
     103                 :            : 
     104                 :            : namespace ana {
     105                 :            : 
     106                 :            : /* Map from svalue_id to state machine state, also capturing the origin of
     107                 :            :    each state.  */
     108                 :            : 
     109                 :    1982840 : class sm_state_map
     110                 :            : {
     111                 :            : public:
     112                 :            :   /* An entry in the hash_map.  */
     113                 :            :   struct entry_t
     114                 :            :   {
     115                 :            :     /* Default ctor needed by hash_map::empty.  */
     116                 :            :     entry_t ()
     117                 :            :     : m_state (0), m_origin (svalue_id::null ())
     118                 :            :     {
     119                 :            :     }
     120                 :            : 
     121                 :      63293 :     entry_t (state_machine::state_t state,
     122                 :            :              svalue_id origin)
     123                 :      63293 :     : m_state (state), m_origin (origin)
     124                 :            :     {}
     125                 :            : 
     126                 :      31688 :     bool operator== (const entry_t &other) const
     127                 :            :     {
     128                 :      31688 :       return (m_state == other.m_state
     129                 :      28707 :               && m_origin == other.m_origin);
     130                 :            :     }
     131                 :      31688 :     bool operator!= (const entry_t &other) const
     132                 :            :     {
     133                 :      62767 :       return !(*this == other);
     134                 :            :     }
     135                 :            : 
     136                 :            :     state_machine::state_t m_state;
     137                 :            :     svalue_id m_origin;
     138                 :            :   };
     139                 :            :   typedef hash_map <svalue_id, entry_t> map_t;
     140                 :            :   typedef map_t::iterator iterator_t;
     141                 :            : 
     142                 :            :   sm_state_map ();
     143                 :            : 
     144                 :            :   sm_state_map *clone () const;
     145                 :            : 
     146                 :            :   sm_state_map *
     147                 :            :   clone_with_remapping (const one_way_svalue_id_map &id_map) const;
     148                 :            : 
     149                 :            :   void print (const state_machine &sm, const region_model *model,
     150                 :            :               pretty_printer *pp) const;
     151                 :            :   void dump (const state_machine &sm) const;
     152                 :            : 
     153                 :            :   bool is_empty_p () const;
     154                 :            : 
     155                 :            :   hashval_t hash () const;
     156                 :            : 
     157                 :            :   bool operator== (const sm_state_map &other) const;
     158                 :      61313 :   bool operator!= (const sm_state_map &other) const
     159                 :            :   {
     160                 :      61313 :     return !(*this == other);
     161                 :            :   }
     162                 :            : 
     163                 :            :   state_machine::state_t get_state (svalue_id sid) const;
     164                 :            :   svalue_id get_origin (svalue_id sid) const;
     165                 :            : 
     166                 :            :   void set_state (region_model *model,
     167                 :            :                   svalue_id sid,
     168                 :            :                   state_machine::state_t state,
     169                 :            :                   svalue_id origin);
     170                 :            :   bool set_state (const equiv_class &ec,
     171                 :            :                   state_machine::state_t state,
     172                 :            :                   svalue_id origin);
     173                 :            :   bool impl_set_state (svalue_id sid,
     174                 :            :                        state_machine::state_t state,
     175                 :            :                        svalue_id origin);
     176                 :            : 
     177                 :            :   void set_global_state (state_machine::state_t state);
     178                 :            :   state_machine::state_t get_global_state () const;
     179                 :            : 
     180                 :            :   void purge_for_unknown_fncall (const exploded_graph &eg,
     181                 :            :                                  const state_machine &sm,
     182                 :            :                                  const gcall *call, tree fndecl,
     183                 :            :                                  region_model *new_model,
     184                 :            :                                  region_model_context *ctxt);
     185                 :            : 
     186                 :            :   void remap_svalue_ids (const svalue_id_map &map);
     187                 :            : 
     188                 :            :   int on_svalue_purge (const state_machine &sm,
     189                 :            :                        int sm_idx,
     190                 :            :                        svalue_id first_unused_sid,
     191                 :            :                        const svalue_id_map &map,
     192                 :            :                        impl_region_model_context *ctxt);
     193                 :            : 
     194                 :            :   void on_inherited_svalue (svalue_id parent_sid,
     195                 :            :                             svalue_id child_sid);
     196                 :            : 
     197                 :            :   void on_cast (svalue_id src_sid,
     198                 :            :                 svalue_id dst_sid);
     199                 :            : 
     200                 :            :   void on_unknown_change (svalue_id sid);
     201                 :            : 
     202                 :            :   void validate (const state_machine &sm, int num_svalues) const;
     203                 :            : 
     204                 :      36490 :   iterator_t begin () const { return m_map.begin (); }
     205                 :      19890 :   iterator_t end () const { return m_map.end (); }
     206                 :            : 
     207                 :            : private:
     208                 :            :   map_t m_map;
     209                 :            :   state_machine::state_t m_global_state;
     210                 :            : };
     211                 :            : 
     212                 :            : /* A class for representing the state of interest at a given path of
     213                 :            :    analysis.
     214                 :            : 
     215                 :            :    Currently this is a combination of:
     216                 :            :    (a) a region_model, giving:
     217                 :            :       (a.1) a hierarchy of memory regions
     218                 :            :       (a.2) values for the regions
     219                 :            :       (a.3) inequalities between values
     220                 :            :    (b) sm_state_maps per state machine, giving a sparse mapping of
     221                 :            :        values to states.  */
     222                 :            : 
     223                 :            : class program_state
     224                 :            : {
     225                 :            : public:
     226                 :            :   program_state (const extrinsic_state &ext_state);
     227                 :            :   program_state (const program_state &other);
     228                 :            :   program_state& operator= (const program_state &other);
     229                 :            : 
     230                 :            : #if __cplusplus >= 201103
     231                 :            :   program_state (program_state &&other);
     232                 :            :   program_state& operator= (program_state &&other); // doesn't seem to be used
     233                 :            : #endif
     234                 :            : 
     235                 :            :   ~program_state ();
     236                 :            : 
     237                 :            :   hashval_t hash () const;
     238                 :            :   bool operator== (const program_state &other) const;
     239                 :       3861 :   bool operator!= (const program_state &other) const
     240                 :            :   {
     241                 :       3861 :     return !(*this == other);
     242                 :            :   }
     243                 :            : 
     244                 :            :   void print (const extrinsic_state &ext_state,
     245                 :            :               pretty_printer *pp) const;
     246                 :            : 
     247                 :            :   void dump_to_pp (const extrinsic_state &ext_state, bool summarize,
     248                 :            :                    pretty_printer *pp) const;
     249                 :            :   void dump_to_file (const extrinsic_state &ext_state, bool summarize,
     250                 :            :                      FILE *outf) const;
     251                 :            :   void dump (const extrinsic_state &ext_state, bool summarize) const;
     252                 :            : 
     253                 :            :   bool on_edge (exploded_graph &eg,
     254                 :            :                 const exploded_node &enode,
     255                 :            :                 const superedge *succ,
     256                 :            :                 state_change *change);
     257                 :            : 
     258                 :            :   program_state prune_for_point (exploded_graph &eg,
     259                 :            :                                  const program_point &point,
     260                 :            :                                  state_change *change) const;
     261                 :            : 
     262                 :            :   void remap_svalue_ids (const svalue_id_map &map);
     263                 :            : 
     264                 :            :   tree get_representative_tree (svalue_id sid) const;
     265                 :            : 
     266                 :      29274 :   bool can_purge_p (const extrinsic_state &ext_state,
     267                 :            :                     svalue_id sid)
     268                 :            :   {
     269                 :            :     /* Don't purge vars that have non-purgeable sm state, to avoid
     270                 :            :        generating false "leak" complaints.  */
     271                 :      29274 :     int i;
     272                 :      29274 :     sm_state_map *smap;
     273                 :     102098 :     FOR_EACH_VEC_ELT (m_checker_states, i, smap)
     274                 :            :       {
     275                 :      83801 :         const state_machine &sm = ext_state.get_sm (i);
     276                 :      83801 :         if (!sm.can_purge_p (smap->get_state (sid)))
     277                 :            :           return false;
     278                 :            :       }
     279                 :            :     return true;
     280                 :            :   }
     281                 :            : 
     282                 :            :   bool can_merge_with_p (const program_state &other,
     283                 :            :                          const extrinsic_state &ext_state,
     284                 :            :                          program_state *out) const;
     285                 :            : 
     286                 :            :   void validate (const extrinsic_state &ext_state) const;
     287                 :            : 
     288                 :            :   /* TODO: lose the pointer here (const-correctness issues?).  */
     289                 :            :   region_model *m_region_model;
     290                 :            :   auto_delete_vec<sm_state_map> m_checker_states;
     291                 :            : 
     292                 :            :   /* If false, then don't attempt to explore further states along this path.
     293                 :            :      For use in "handling" lvalues for tree codes we haven't yet
     294                 :            :      implemented.  */
     295                 :            :   bool m_valid;
     296                 :            : };
     297                 :            : 
     298                 :            : /* An abstract base class for use with for_each_state_change.  */
     299                 :            : 
     300                 :       4203 : class state_change_visitor
     301                 :            : {
     302                 :            : public:
     303                 :       4203 :   virtual ~state_change_visitor () {}
     304                 :            : 
     305                 :            :   /* Return true for early exit, false to keep iterating.  */
     306                 :            :   virtual bool on_global_state_change (const state_machine &sm,
     307                 :            :                                        state_machine::state_t src_sm_val,
     308                 :            :                                        state_machine::state_t dst_sm_val) = 0;
     309                 :            : 
     310                 :            :   /* Return true for early exit, false to keep iterating.  */
     311                 :            :   virtual bool on_state_change (const state_machine &sm,
     312                 :            :                                 state_machine::state_t src_sm_val,
     313                 :            :                                 state_machine::state_t dst_sm_val,
     314                 :            :                                 tree dst_rep,
     315                 :            :                                 svalue_id dst_origin_sid) = 0;
     316                 :            : };
     317                 :            : 
     318                 :            : extern bool for_each_state_change (const program_state &src_state,
     319                 :            :                                    const program_state &dst_state,
     320                 :            :                                    const extrinsic_state &ext_state,
     321                 :            :                                    state_change_visitor *visitor);
     322                 :            : 
     323                 :            : /* A class for recording "interesting" state changes.
     324                 :            :    This is used for annotating edges in the GraphViz output of the
     325                 :            :    exploded_graph, and for recording sm-state-changes, so that
     326                 :            :    values that change aren't purged (to make it easier to generate
     327                 :            :    state_change_event instances in the diagnostic_path).  */
     328                 :            : 
     329                 :      63163 : class state_change
     330                 :            : {
     331                 :            :  public:
     332                 :            :   struct sm_change
     333                 :            :   {
     334                 :       1508 :     sm_change (int sm_idx,
     335                 :            :                svalue_id new_sid,
     336                 :            :                state_machine::state_t old_state,
     337                 :            :                state_machine::state_t new_state)
     338                 :       1508 :     : m_sm_idx (sm_idx),
     339                 :            :       m_new_sid (new_sid),
     340                 :       1508 :       m_old_state (old_state), m_new_state (new_state)
     341                 :            :     {}
     342                 :            : 
     343                 :          1 :     const state_machine &get_sm (const extrinsic_state &ext_state) const
     344                 :            :     {
     345                 :          1 :       return ext_state.get_sm (m_sm_idx);
     346                 :            :     }
     347                 :            : 
     348                 :            :     void dump (pretty_printer *pp, const extrinsic_state &ext_state) const;
     349                 :            : 
     350                 :            :     void remap_svalue_ids (const svalue_id_map &map);
     351                 :            :     int on_svalue_purge (svalue_id first_unused_sid);
     352                 :            : 
     353                 :            :     void validate (const program_state &new_state,
     354                 :            :                    const extrinsic_state &ext_state) const;
     355                 :            : 
     356                 :            :     int m_sm_idx;
     357                 :            :     svalue_id m_new_sid;
     358                 :            :     state_machine::state_t m_old_state;
     359                 :            :     state_machine::state_t m_new_state;
     360                 :            :   };
     361                 :            : 
     362                 :            :   state_change ();
     363                 :            :   state_change (const state_change &other);
     364                 :            : 
     365                 :            :   void add_sm_change (int sm_idx,
     366                 :            :                       svalue_id new_sid,
     367                 :            :                       state_machine::state_t old_state,
     368                 :            :                       state_machine::state_t new_state);
     369                 :            : 
     370                 :            :   bool affects_p (svalue_id sid) const;
     371                 :            : 
     372                 :            :   void dump (pretty_printer *pp, const extrinsic_state &ext_state) const;
     373                 :            :   void dump (const extrinsic_state &ext_state) const;
     374                 :            : 
     375                 :            :   void remap_svalue_ids (const svalue_id_map &map);
     376                 :            :   int on_svalue_purge (svalue_id first_unused_sid);
     377                 :            : 
     378                 :            :   void validate (const program_state &new_state,
     379                 :            :                  const extrinsic_state &ext_state) const;
     380                 :            : 
     381                 :            :  private:
     382                 :            :   auto_vec<sm_change> m_sm_changes;
     383                 :            : };
     384                 :            : 
     385                 :            : } // namespace ana
     386                 :            : 
     387                 :            : #endif /* GCC_ANALYZER_PROGRAM_STATE_H */

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.