gcc/analyzer/program-state.h

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