gcc/analyzer/program-state.h

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