diff options
Diffstat (limited to 'gcc/analyzer/program-state.h')
| -rw-r--r-- | gcc/analyzer/program-state.h | 363 |
1 files changed, 363 insertions, 0 deletions
diff --git a/gcc/analyzer/program-state.h b/gcc/analyzer/program-state.h new file mode 100644 index 0000000..75b65b7 --- /dev/null +++ b/gcc/analyzer/program-state.h @@ -0,0 +1,363 @@ +/* Classes for representing the state of interest at a given path of analysis. + Copyright (C) 2019-2020 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalcolm@redhat.com>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_ANALYZER_PROGRAM_STATE_H +#define GCC_ANALYZER_PROGRAM_STATE_H + +/* Data shared by all program_state instances. */ + +class extrinsic_state +{ +public: + extrinsic_state (auto_delete_vec <state_machine> &checkers) + : m_checkers (checkers) + { + } + + const state_machine &get_sm (int idx) const + { + return *m_checkers[idx]; + } + + const char *get_name (int idx) const + { + return m_checkers[idx]->get_name (); + } + + unsigned get_num_checkers () const { return m_checkers.length (); } + + /* The state machines. */ + auto_delete_vec <state_machine> &m_checkers; +}; + +template <> struct default_hash_traits<svalue_id> +: public pod_hash_traits<svalue_id> +{ + static const bool empty_zero_p = false; +}; + +template <> +inline hashval_t +pod_hash_traits<svalue_id>::hash (value_type v) +{ + return v.as_int (); +} + +template <> +inline bool +pod_hash_traits<svalue_id>::equal (const value_type &existing, + const value_type &candidate) +{ + return existing == candidate; +} +template <> +inline void +pod_hash_traits<svalue_id>::mark_deleted (value_type &v) +{ + v = svalue_id::from_int (-2); +} +template <> +inline void +pod_hash_traits<svalue_id>::mark_empty (value_type &v) +{ + v = svalue_id::null (); +} +template <> +inline bool +pod_hash_traits<svalue_id>::is_deleted (value_type v) +{ + return v.as_int () == -2; +} +template <> +inline bool +pod_hash_traits<svalue_id>::is_empty (value_type v) +{ + return v.null_p (); +} + +/* Map from svalue_id to state machine state, also capturing the origin of + each state. */ + +class sm_state_map +{ +public: + /* An entry in the hash_map. */ + struct entry_t + { + /* Default ctor needed by hash_map::empty. */ + entry_t () + : m_state (0), m_origin (svalue_id::null ()) + { + } + + entry_t (state_machine::state_t state, + svalue_id origin) + : m_state (state), m_origin (origin) + {} + + bool operator== (const entry_t &other) const + { + return (m_state == other.m_state + && m_origin == other.m_origin); + } + bool operator!= (const entry_t &other) const + { + return !(*this == other); + } + + state_machine::state_t m_state; + svalue_id m_origin; + }; + typedef hash_map <svalue_id, entry_t> map_t; + typedef typename map_t::iterator iterator_t; + + sm_state_map (); + + sm_state_map *clone () const; + + sm_state_map * + clone_with_remapping (const one_way_svalue_id_map &id_map) const; + + void print (const state_machine &sm, pretty_printer *pp) const; + void dump (const state_machine &sm) const; + + bool is_empty_p () const; + + hashval_t hash () const; + + bool operator== (const sm_state_map &other) const; + bool operator!= (const sm_state_map &other) const + { + return !(*this == other); + } + + state_machine::state_t get_state (svalue_id sid) const; + svalue_id get_origin (svalue_id sid) const; + + void set_state (region_model *model, + svalue_id sid, + state_machine::state_t state, + svalue_id origin); + void set_state (const equiv_class &ec, + state_machine::state_t state, + svalue_id origin); + void impl_set_state (svalue_id sid, + state_machine::state_t state, + svalue_id origin); + + void set_global_state (state_machine::state_t state); + state_machine::state_t get_global_state () const; + + void purge_for_unknown_fncall (const exploded_graph &eg, + const state_machine &sm, + const gcall *call, tree fndecl, + region_model *new_model); + + void remap_svalue_ids (const svalue_id_map &map); + + int on_svalue_purge (const state_machine &sm, + int sm_idx, + svalue_id first_unused_sid, + const svalue_id_map &map, + impl_region_model_context *ctxt); + + void on_inherited_svalue (svalue_id parent_sid, + svalue_id child_sid); + + void on_cast (svalue_id src_sid, + svalue_id dst_sid); + + void validate (const state_machine &sm, int num_svalues) const; + + iterator_t begin () const { return m_map.begin (); } + iterator_t end () const { return m_map.end (); } + +private: + map_t m_map; + state_machine::state_t m_global_state; +}; + +/* A class for representing the state of interest at a given path of + analysis. + + Currently this is a combination of: + (a) a region_model, giving: + (a.1) a hierarchy of memory regions + (a.2) values for the regions + (a.3) inequalities between values + (b) sm_state_maps per state machine, giving a sparse mapping of + values to states. */ + +class program_state +{ +public: + program_state (const extrinsic_state &ext_state); + program_state (const program_state &other); + program_state& operator= (const program_state &other); + +#if __cplusplus >= 201103 + program_state (program_state &&other); + program_state& operator= (program_state &&other); // doesn't seem to be used +#endif + + ~program_state (); + + hashval_t hash () const; + bool operator== (const program_state &other) const; + bool operator!= (const program_state &other) const + { + return !(*this == other); + } + + void print (const extrinsic_state &ext_state, + pretty_printer *pp) const; + + void dump_to_pp (const extrinsic_state &ext_state, bool summarize, + pretty_printer *pp) const; + void dump_to_file (const extrinsic_state &ext_state, bool summarize, + FILE *outf) const; + void dump (const extrinsic_state &ext_state, bool summarize) const; + + bool on_edge (exploded_graph &eg, + const exploded_node &enode, + const superedge *succ, + state_change *change); + + program_state prune_for_point (exploded_graph &eg, + const program_point &point, + state_change *change) const; + + void remap_svalue_ids (const svalue_id_map &map); + + tree get_representative_tree (svalue_id sid) const; + + bool can_purge_p (const extrinsic_state &ext_state, + svalue_id sid) + { + /* Don't purge vars that have non-purgeable sm state, to avoid + generating false "leak" complaints. */ + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (m_checker_states, i, smap) + { + const state_machine &sm = ext_state.get_sm (i); + if (!sm.can_purge_p (smap->get_state (sid))) + return false; + } + return true; + } + + bool can_merge_with_p (const program_state &other, + const extrinsic_state &ext_state, + program_state *out) const; + + void validate (const extrinsic_state &ext_state) const; + + /* TODO: lose the pointer here (const-correctness issues?). */ + region_model *m_region_model; + auto_delete_vec<sm_state_map> m_checker_states; +}; + +/* An abstract base class for use with for_each_state_change. */ + +class state_change_visitor +{ +public: + virtual ~state_change_visitor () {} + + /* Return true for early exit, false to keep iterating. */ + virtual bool on_global_state_change (const state_machine &sm, + state_machine::state_t src_sm_val, + state_machine::state_t dst_sm_val) = 0; + + /* Return true for early exit, false to keep iterating. */ + virtual bool on_state_change (const state_machine &sm, + state_machine::state_t src_sm_val, + state_machine::state_t dst_sm_val, + tree dst_rep, + svalue_id dst_origin_sid) = 0; +}; + +extern bool for_each_state_change (const program_state &src_state, + const program_state &dst_state, + const extrinsic_state &ext_state, + state_change_visitor *visitor); + +/* A class for recording "interesting" state changes. + This is used for annotating edges in the GraphViz output of the + exploded_graph, and for recording sm-state-changes, so that + values that change aren't purged (to make it easier to generate + state_change_event instances in the diagnostic_path). */ + +class state_change +{ + public: + struct sm_change + { + sm_change (int sm_idx, + svalue_id new_sid, + state_machine::state_t old_state, + state_machine::state_t new_state) + : m_sm_idx (sm_idx), + m_new_sid (new_sid), + m_old_state (old_state), m_new_state (new_state) + {} + + const state_machine &get_sm (const extrinsic_state &ext_state) const + { + return ext_state.get_sm (m_sm_idx); + } + + void dump (pretty_printer *pp, const extrinsic_state &ext_state) const; + + void remap_svalue_ids (const svalue_id_map &map); + int on_svalue_purge (svalue_id first_unused_sid); + + void validate (const program_state &new_state) const; + + int m_sm_idx; + svalue_id m_new_sid; + state_machine::state_t m_old_state; + state_machine::state_t m_new_state; + }; + + state_change (); + state_change (const state_change &other); + + void add_sm_change (int sm_idx, + svalue_id new_sid, + state_machine::state_t old_state, + state_machine::state_t new_state); + + bool affects_p (svalue_id sid) const; + + void dump (pretty_printer *pp, const extrinsic_state &ext_state) const; + void dump (const extrinsic_state &ext_state) const; + + void remap_svalue_ids (const svalue_id_map &map); + int on_svalue_purge (svalue_id first_unused_sid); + + void validate (const program_state &new_state) const; + + private: + auto_vec<sm_change> m_sm_changes; +}; + +#endif /* GCC_ANALYZER_PROGRAM_STATE_H */ |