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: extrinsic_state(auto_delete_vec<state_machine> & checkers)31 extrinsic_state (auto_delete_vec <state_machine> &checkers) 32 : m_checkers (checkers) 33 { 34 } 35 get_sm(int idx)36 const state_machine &get_sm (int idx) const 37 { 38 return *m_checkers[idx]; 39 } 40 get_name(int idx)41 const char *get_name (int idx) const 42 { 43 return m_checkers[idx]->get_name (); 44 } 45 get_num_checkers()46 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 pod_hash_traits<svalue_id>::hash (value_type v) 68 { 69 return v.as_int (); 70 } 71 72 template <> 73 inline bool 74 pod_hash_traits<svalue_id>::equal (const value_type &existing, 75 const value_type &candidate) 76 { 77 return existing == candidate; 78 } 79 template <> 80 inline void 81 pod_hash_traits<svalue_id>::mark_deleted (value_type &v) 82 { 83 v = svalue_id::from_int (-2); 84 } 85 template <> 86 inline void 87 pod_hash_traits<svalue_id>::mark_empty (value_type &v) 88 { 89 v = svalue_id::null (); 90 } 91 template <> 92 inline bool 93 pod_hash_traits<svalue_id>::is_deleted (value_type v) 94 { 95 return v.as_int () == -2; 96 } 97 template <> 98 inline bool 99 pod_hash_traits<svalue_id>::is_empty (value_type v) 100 { 101 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 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 entry_t (state_machine::state_t state, 122 svalue_id origin) 123 : m_state (state), m_origin (origin) 124 {} 125 126 bool operator== (const entry_t &other) const 127 { 128 return (m_state == other.m_state 129 && m_origin == other.m_origin); 130 } 131 bool operator!= (const entry_t &other) const 132 { 133 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 bool operator!= (const sm_state_map &other) const 159 { 160 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 iterator_t begin () const { return m_map.begin (); } 205 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 bool operator!= (const program_state &other) const 240 { 241 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 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 int i; 272 sm_state_map *smap; 273 FOR_EACH_VEC_ELT (m_checker_states, i, smap) 274 { 275 const state_machine &sm = ext_state.get_sm (i); 276 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 class state_change_visitor 301 { 302 public: 303 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 class state_change 330 { 331 public: 332 struct sm_change 333 { 334 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 : m_sm_idx (sm_idx), 339 m_new_sid (new_sid), 340 m_old_state (old_state), m_new_state (new_state) 341 {} 342 343 const state_machine &get_sm (const extrinsic_state &ext_state) const 344 { 345 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 */ 388