gcc/analyzer/program-state.h

   1 /* Classes for representing the state of interest at a given path of analysis.
   2    Copyright (C) 2019-2023 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   extrinsic_state (auto_delete_vec <state_machine> &checkers,
  32                    engine *eng,
  33                    logger *logger = NULL)
  34   : m_checkers (checkers), m_logger (logger), m_engine (eng)
  35   {
  36   }
  37
  38   const state_machine &get_sm (int idx) const
  39   {
  40     return *m_checkers[idx];
  41   }
  42
  43   const char *get_name (int idx) const
  44   {
  45     return m_checkers[idx]->get_name ();
  46   }
  47
  48   unsigned get_num_checkers () const { return m_checkers.length (); }
  49
  50   logger *get_logger () const { return m_logger; }
  51
  52   void dump_to_pp (pretty_printer *pp) const;
  53   void dump_to_file (FILE *outf) const;
  54   void dump () const;
  55
  56   json::object *to_json () const;
  57
  58   engine *get_engine () const { return m_engine; }
  59   region_model_manager *get_model_manager () const;
  60
  61   bool get_sm_idx_by_name (const char *name, unsigned *out) const;
  62
  63 private:
  64   /* The state machines.  */
  65   auto_delete_vec <state_machine> &m_checkers;
  66
  67   logger *m_logger;
  68   engine *m_engine;
  69 };
  70
  71 /* Map from svalue * to state machine state, also capturing the origin of
  72    each state.  */
  73
  74 class sm_state_map
  75 {
  76 public:
  77   /* An entry in the hash_map.  */
  78   struct entry_t
  79   {
  80     /* Default ctor needed by hash_map::empty.  */
  81     entry_t ()
  82     : m_state (0), m_origin (NULL)
  83     {
  84     }
  85
  86     entry_t (state_machine::state_t state,
  87              const svalue *origin)
  88     : m_state (state), m_origin (origin)
  89     {}
  90
  91     bool operator== (const entry_t &other) const
  92     {
  93       return (m_state == other.m_state
  94               && m_origin == other.m_origin);
  95     }
  96     bool operator!= (const entry_t &other) const
  97     {
  98       return !(*this == other);
  99     }
 100
 101     static int cmp (const entry_t &entry_a, const entry_t &entry_b);
 102
 103     state_machine::state_t m_state;
 104     const svalue *m_origin;
 105   };
 106   typedef hash_map <const svalue *, entry_t> map_t;
 107   typedef map_t::iterator iterator_t;
 108
 109   sm_state_map (const state_machine &sm);
 110
 111   sm_state_map *clone () const;
 112
 113   void print (const region_model *model,
 114               bool simple, bool multiline,
 115               pretty_printer *pp) const;
 116   void dump (bool simple) const;
 117
 118   json::object *to_json () const;
 119
 120   bool is_empty_p () const;
 121
 122   hashval_t hash () const;
 123
 124   bool operator== (const sm_state_map &other) const;
 125   bool operator!= (const sm_state_map &other) const
 126   {
 127     return !(*this == other);
 128   }
 129
 130   state_machine::state_t get_state (const svalue *sval,
 131                                     const extrinsic_state &ext_state) const;
 132   const svalue *get_origin (const svalue *sval,
 133                             const extrinsic_state &ext_state) const;
 134
 135   void set_state (region_model *model,
 136                   const svalue *sval,
 137                   state_machine::state_t state,
 138                   const svalue *origin,
 139                   const extrinsic_state &ext_state);
 140   bool set_state (const equiv_class &ec,
 141                   state_machine::state_t state,
 142                   const svalue *origin,
 143                   const extrinsic_state &ext_state);
 144   bool impl_set_state (const svalue *sval,
 145                        state_machine::state_t state,
 146                        const svalue *origin,
 147                        const extrinsic_state &ext_state);
 148   void clear_any_state (const svalue *sval);
 149   void clear_all_per_svalue_state ();
 150
 151   void set_global_state (state_machine::state_t state);
 152   state_machine::state_t get_global_state () const;
 153
 154   void on_svalue_leak (const svalue *sval,
 155                        impl_region_model_context *ctxt);
 156   void on_liveness_change (const svalue_set &live_svalues,
 157                            const region_model *model,
 158                            impl_region_model_context *ctxt);
 159
 160   void on_unknown_change (const svalue *sval,
 161                           bool is_mutable,
 162                           const extrinsic_state &ext_state);
 163
 164   void purge_state_involving (const svalue *sval,
 165                               const extrinsic_state &ext_state);
 166
 167   iterator_t begin () const { return m_map.begin (); }
 168   iterator_t end () const { return m_map.end (); }
 169   size_t elements () const { return m_map.elements (); }
 170
 171   static int cmp (const sm_state_map &smap_a, const sm_state_map &smap_b);
 172
 173   static const svalue *
 174   canonicalize_svalue (const svalue *sval, const extrinsic_state &ext_state);
 175
 176   bool replay_call_summary (call_summary_replay &r,
 177                             const sm_state_map &summary);
 178
 179   bool can_merge_with_p (const sm_state_map &other,
 180                          const state_machine &sm,
 181                          const extrinsic_state &ext_state,
 182                          sm_state_map **out) const;
 183
 184 private:
 185   const state_machine &m_sm;
 186   map_t m_map;
 187   state_machine::state_t m_global_state;
 188 };
 189
 190 /* A class for representing the state of interest at a given path of
 191    analysis.
 192
 193    Currently this is a combination of:
 194    (a) a region_model, giving:
 195       (a.1) a hierarchy of memory regions
 196       (a.2) values for the regions
 197       (a.3) inequalities between values
 198    (b) sm_state_maps per state machine, giving a sparse mapping of
 199        values to states.  */
 200
 201 class program_state
 202 {
 203 public:
 204   program_state (const extrinsic_state &ext_state);
 205   program_state (const program_state &other);
 206   program_state& operator= (const program_state &other);
 207   program_state (program_state &&other);
 208   ~program_state ();
 209
 210   hashval_t hash () const;
 211   bool operator== (const program_state &other) const;
 212   bool operator!= (const program_state &other) const
 213   {
 214     return !(*this == other);
 215   }
 216
 217   void print (const extrinsic_state &ext_state,
 218               pretty_printer *pp) const;
 219
 220   void dump_to_pp (const extrinsic_state &ext_state, bool simple,
 221                    bool multiline, pretty_printer *pp) const;
 222   void dump_to_file (const extrinsic_state &ext_state, bool simple,
 223                      bool multiline, FILE *outf) const;
 224   void dump (const extrinsic_state &ext_state, bool simple) const;
 225
 226   json::object *to_json (const extrinsic_state &ext_state) const;
 227
 228   void push_frame (const extrinsic_state &ext_state, function *fun);
 229   function * get_current_function () const;
 230
 231   void push_call (exploded_graph &eg,
 232                   exploded_node *enode,
 233                   const gcall *call_stmt,
 234                   uncertainty_t *uncertainty);
 235
 236   void returning_call (exploded_graph &eg,
 237                        exploded_node *enode,
 238                        const gcall *call_stmt,
 239                        uncertainty_t *uncertainty);
 240
 241
 242   bool on_edge (exploded_graph &eg,
 243                 exploded_node *enode,
 244                 const superedge *succ,
 245                 uncertainty_t *uncertainty);
 246
 247   program_state prune_for_point (exploded_graph &eg,
 248                                  const program_point &point,
 249                                  exploded_node *enode_for_diag,
 250                                  uncertainty_t *uncertainty) const;
 251
 252   tree get_representative_tree (const svalue *sval) const;
 253
 254   bool can_purge_p (const extrinsic_state &ext_state,
 255                     const svalue *sval) const
 256   {
 257     /* Don't purge vars that have non-purgeable sm state, to avoid
 258        generating false "leak" complaints.  */
 259     int i;
 260     sm_state_map *smap;
 261     FOR_EACH_VEC_ELT (m_checker_states, i, smap)
 262       {
 263         const state_machine &sm = ext_state.get_sm (i);
 264         if (!sm.can_purge_p (smap->get_state (sval, ext_state)))
 265           return false;
 266       }
 267     return true;
 268   }
 269
 270   bool can_purge_base_region_p (const extrinsic_state &ext_state,
 271                                 const region *base_reg) const;
 272
 273   bool can_merge_with_p (const program_state &other,
 274                          const extrinsic_state &ext_state,
 275                          const program_point &point,
 276                          program_state *out) const;
 277
 278   void validate (const extrinsic_state &ext_state) const;
 279
 280   static void detect_leaks (const program_state &src_state,
 281                             const program_state &dest_state,
 282                             const svalue *extra_sval,
 283                             const extrinsic_state &ext_state,
 284                             region_model_context *ctxt);
 285
 286   bool replay_call_summary (call_summary_replay &r,
 287                             const program_state &summary);
 288
 289   void impl_call_analyzer_dump_state (const gcall *call,
 290                                       const extrinsic_state &ext_state,
 291                                       region_model_context *ctxt);
 292
 293   /* TODO: lose the pointer here (const-correctness issues?).  */
 294   region_model *m_region_model;
 295   auto_delete_vec<sm_state_map> m_checker_states;
 296
 297   /* If false, then don't attempt to explore further states along this path.
 298      For use in "handling" lvalues for tree codes we haven't yet
 299      implemented.  */
 300   bool m_valid;
 301 };
 302
 303 /* An abstract base class for use with for_each_state_change.  */
 304
 305 class state_change_visitor
 306 {
 307 public:
 308   virtual ~state_change_visitor () {}
 309
 310   /* Return true for early exit, false to keep iterating.  */
 311   virtual bool on_global_state_change (const state_machine &sm,
 312                                        state_machine::state_t src_sm_val,
 313                                        state_machine::state_t dst_sm_val) = 0;
 314
 315   /* Return true for early exit, false to keep iterating.  */
 316   virtual bool on_state_change (const state_machine &sm,
 317                                 state_machine::state_t src_sm_val,
 318                                 state_machine::state_t dst_sm_val,
 319                                 const svalue *dst_sval,
 320                                 const svalue *dst_origin_sval) = 0;
 321 };
 322
 323 extern bool for_each_state_change (const program_state &src_state,
 324                                     const program_state &dst_state,
 325                                     const extrinsic_state &ext_state,
 326                                     state_change_visitor *visitor);
 327
 328 } // namespace ana
 329
 330 #endif /* GCC_ANALYZER_PROGRAM_STATE_H */