| /* Classes for managing a directed graph of <point, state> pairs. |
| Copyright (C) 2019-2021 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_EXPLODED_GRAPH_H |
| #define GCC_ANALYZER_EXPLODED_GRAPH_H |
| |
| namespace ana { |
| |
| /* Concrete implementation of region_model_context, wiring it up to the |
| rest of the analysis engine. */ |
| |
| class impl_region_model_context : public region_model_context |
| { |
| public: |
| impl_region_model_context (exploded_graph &eg, |
| exploded_node *enode_for_diag, |
| |
| /* TODO: should we be getting the ECs from the |
| old state, rather than the new? */ |
| const program_state *old_state, |
| program_state *new_state, |
| uncertainty_t *uncertainty, |
| path_context *path_ctxt, |
| |
| const gimple *stmt, |
| stmt_finder *stmt_finder = NULL); |
| |
| impl_region_model_context (program_state *state, |
| const extrinsic_state &ext_state, |
| uncertainty_t *uncertainty, |
| logger *logger = NULL); |
| |
| bool warn (pending_diagnostic *d) FINAL OVERRIDE; |
| void on_svalue_leak (const svalue *) OVERRIDE; |
| void on_liveness_change (const svalue_set &live_svalues, |
| const region_model *model) FINAL OVERRIDE; |
| logger *get_logger () FINAL OVERRIDE |
| { |
| return m_logger.get_logger (); |
| } |
| |
| void on_state_leak (const state_machine &sm, |
| const svalue *sval, |
| state_machine::state_t state); |
| |
| void on_condition (const svalue *lhs, |
| enum tree_code op, |
| const svalue *rhs) FINAL OVERRIDE; |
| |
| void on_unknown_change (const svalue *sval, bool is_mutable) FINAL OVERRIDE; |
| |
| void on_phi (const gphi *phi, tree rhs) FINAL OVERRIDE; |
| |
| void on_unexpected_tree_code (tree t, |
| const dump_location_t &loc) FINAL OVERRIDE; |
| |
| void on_escaped_function (tree fndecl) FINAL OVERRIDE; |
| |
| uncertainty_t *get_uncertainty () FINAL OVERRIDE; |
| |
| void purge_state_involving (const svalue *sval) FINAL OVERRIDE; |
| |
| void bifurcate (custom_edge_info *info) FINAL OVERRIDE; |
| void terminate_path () FINAL OVERRIDE; |
| const extrinsic_state *get_ext_state () const FINAL OVERRIDE |
| { |
| return &m_ext_state; |
| } |
| bool get_malloc_map (sm_state_map **out_smap, |
| const state_machine **out_sm, |
| unsigned *out_sm_idx) FINAL OVERRIDE; |
| |
| exploded_graph *m_eg; |
| log_user m_logger; |
| exploded_node *m_enode_for_diag; |
| const program_state *m_old_state; |
| program_state *m_new_state; |
| const gimple *m_stmt; |
| stmt_finder *m_stmt_finder; |
| const extrinsic_state &m_ext_state; |
| uncertainty_t *m_uncertainty; |
| path_context *m_path_ctxt; |
| }; |
| |
| /* A <program_point, program_state> pair, used internally by |
| exploded_node as its immutable data, and as a key for identifying |
| exploded_nodes we've already seen in the graph. */ |
| |
| class point_and_state |
| { |
| public: |
| point_and_state (const program_point &point, |
| const program_state &state) |
| : m_point (point), |
| m_state (state), |
| m_hash (m_point.hash () ^ m_state.hash ()) |
| { |
| /* We shouldn't be building point_and_states and thus exploded_nodes |
| for states that aren't valid. */ |
| gcc_assert (state.m_valid); |
| } |
| |
| hashval_t hash () const |
| { |
| return m_hash; |
| } |
| bool operator== (const point_and_state &other) const |
| { |
| return m_point == other.m_point && m_state == other.m_state; |
| } |
| |
| const program_point &get_point () const { return m_point; } |
| const program_state &get_state () const { return m_state; } |
| |
| void set_state (const program_state &state) |
| { |
| m_state = state; |
| m_hash = m_point.hash () ^ m_state.hash (); |
| } |
| |
| void validate (const extrinsic_state &ext_state) const; |
| |
| private: |
| program_point m_point; |
| program_state m_state; |
| hashval_t m_hash; |
| }; |
| |
| /* A traits class for exploded graphs and their nodes and edges. */ |
| |
| struct eg_traits |
| { |
| typedef exploded_node node_t; |
| typedef exploded_edge edge_t; |
| typedef exploded_graph graph_t; |
| struct dump_args_t |
| { |
| dump_args_t (const exploded_graph &eg) : m_eg (eg) {} |
| |
| bool show_enode_details_p (const exploded_node &enode) const; |
| |
| virtual void |
| dump_extra_info (const exploded_node *, pretty_printer *) const {} |
| |
| const exploded_graph &m_eg; |
| }; |
| typedef exploded_cluster cluster_t; |
| }; |
| |
| /* An exploded_node is a unique, immutable <point, state> pair within the |
| exploded_graph. |
| Each exploded_node has a unique index within the graph |
| (for ease of debugging). */ |
| |
| class exploded_node : public dnode<eg_traits> |
| { |
| public: |
| /* Has this enode had exploded_graph::process_node called on it? |
| This allows us to distinguish enodes that were merged during |
| worklist-handling, and thus never had process_node called on them |
| (in favor of processing the merged node). */ |
| enum status |
| { |
| /* Node is in the worklist. */ |
| STATUS_WORKLIST, |
| |
| /* Node has had exploded_graph::process_node called on it. */ |
| STATUS_PROCESSED, |
| |
| /* Node was left unprocessed due to merger; it won't have had |
| exploded_graph::process_node called on it. */ |
| STATUS_MERGER, |
| |
| /* Node was processed by maybe_process_run_of_before_supernode_enodes. */ |
| STATUS_BULK_MERGED |
| }; |
| static const char * status_to_str (enum status s); |
| |
| exploded_node (const point_and_state &ps, int index); |
| |
| hashval_t hash () const { return m_ps.hash (); } |
| |
| const char * get_dot_fillcolor () const; |
| void dump_dot (graphviz_out *gv, const dump_args_t &args) |
| const FINAL OVERRIDE; |
| void dump_dot_id (pretty_printer *pp) const; |
| |
| void dump_to_pp (pretty_printer *pp, const extrinsic_state &ext_state) const; |
| void dump (FILE *fp, const extrinsic_state &ext_state) const; |
| void dump (const extrinsic_state &ext_state) const; |
| |
| void dump_processed_stmts (pretty_printer *pp) const; |
| void dump_saved_diagnostics (pretty_printer *pp) const; |
| |
| json::object *to_json (const extrinsic_state &ext_state) const; |
| |
| /* The result of on_stmt. */ |
| struct on_stmt_flags |
| { |
| on_stmt_flags () : m_terminate_path (false) |
| {} |
| |
| static on_stmt_flags terminate_path () |
| { |
| return on_stmt_flags (true); |
| } |
| |
| /* Should we stop analyzing this path (on_stmt may have already |
| added nodes/edges, e.g. when handling longjmp). */ |
| bool m_terminate_path : 1; |
| |
| private: |
| on_stmt_flags (bool terminate_path) |
| : m_terminate_path (terminate_path) |
| {} |
| }; |
| |
| on_stmt_flags on_stmt (exploded_graph &eg, |
| const supernode *snode, |
| const gimple *stmt, |
| program_state *state, |
| uncertainty_t *uncertainty, |
| path_context *path_ctxt); |
| void on_stmt_pre (exploded_graph &eg, |
| const gimple *stmt, |
| program_state *state, |
| bool *out_terminate_path, |
| bool *out_unknown_side_effects, |
| region_model_context *ctxt); |
| void on_stmt_post (const gimple *stmt, |
| program_state *state, |
| bool unknown_side_effects, |
| region_model_context *ctxt); |
| |
| bool on_edge (exploded_graph &eg, |
| const superedge *succ, |
| program_point *next_point, |
| program_state *next_state, |
| uncertainty_t *uncertainty); |
| void on_longjmp (exploded_graph &eg, |
| const gcall *call, |
| program_state *new_state, |
| region_model_context *ctxt); |
| |
| void detect_leaks (exploded_graph &eg); |
| |
| const program_point &get_point () const { return m_ps.get_point (); } |
| const supernode *get_supernode () const |
| { |
| return get_point ().get_supernode (); |
| } |
| function *get_function () const |
| { |
| return get_point ().get_function (); |
| } |
| int get_stack_depth () const |
| { |
| return get_point ().get_stack_depth (); |
| } |
| const gimple *get_stmt () const { return get_point ().get_stmt (); } |
| const gimple *get_processed_stmt (unsigned idx) const; |
| |
| const program_state &get_state () const { return m_ps.get_state (); } |
| |
| const point_and_state *get_ps_key () const { return &m_ps; } |
| const program_point *get_point_key () const { return &m_ps.get_point (); } |
| |
| void dump_succs_and_preds (FILE *outf) const; |
| |
| enum status get_status () const { return m_status; } |
| void set_status (enum status status) |
| { |
| gcc_assert (m_status == STATUS_WORKLIST); |
| m_status = status; |
| } |
| |
| void add_diagnostic (const saved_diagnostic *sd) |
| { |
| m_saved_diagnostics.safe_push (sd); |
| } |
| unsigned get_num_diagnostics () const |
| { |
| return m_saved_diagnostics.length (); |
| } |
| const saved_diagnostic *get_saved_diagnostic (unsigned idx) const |
| { |
| return m_saved_diagnostics[idx]; |
| } |
| |
| private: |
| DISABLE_COPY_AND_ASSIGN (exploded_node); |
| |
| /* The <program_point, program_state> pair. This is const, as it |
| is immutable once the exploded_node has been created. */ |
| const point_and_state m_ps; |
| |
| enum status m_status; |
| |
| /* The saved_diagnostics at this enode, borrowed from the |
| diagnostic_manager. */ |
| auto_vec <const saved_diagnostic *> m_saved_diagnostics; |
| |
| public: |
| /* The index of this exploded_node. */ |
| const int m_index; |
| |
| /* The number of stmts that were processed when process_node was |
| called on this enode. */ |
| unsigned m_num_processed_stmts; |
| }; |
| |
| /* An edge within the exploded graph. |
| Some exploded_edges have an underlying superedge; others don't. */ |
| |
| class exploded_edge : public dedge<eg_traits> |
| { |
| public: |
| exploded_edge (exploded_node *src, exploded_node *dest, |
| const superedge *sedge, |
| custom_edge_info *custom_info); |
| ~exploded_edge (); |
| void dump_dot (graphviz_out *gv, const dump_args_t &args) |
| const FINAL OVERRIDE; |
| void dump_dot_label (pretty_printer *pp) const; |
| |
| json::object *to_json () const; |
| |
| //private: |
| const superedge *const m_sedge; |
| |
| /* NULL for most edges; will be non-NULL for special cases |
| such as an unwind from a longjmp to a setjmp, or when |
| a signal is delivered to a signal-handler. |
| |
| Owned by this class. */ |
| custom_edge_info *m_custom_info; |
| |
| private: |
| DISABLE_COPY_AND_ASSIGN (exploded_edge); |
| }; |
| |
| /* Extra data for an exploded_edge that represents dynamic call info ( calls |
| that doesn't have an underlying superedge representing the call ). */ |
| |
| class dynamic_call_info_t : public custom_edge_info |
| { |
| public: |
| dynamic_call_info_t (const gcall *dynamic_call, |
| const bool is_returning_call = false) |
| : m_dynamic_call (dynamic_call), |
| m_is_returning_call (is_returning_call) |
| {} |
| |
| void print (pretty_printer *pp) const FINAL OVERRIDE |
| { |
| if (m_is_returning_call) |
| pp_string (pp, "dynamic_return"); |
| else |
| pp_string (pp, "dynamic_call"); |
| } |
| |
| bool update_model (region_model *model, |
| const exploded_edge *eedge, |
| region_model_context *ctxt) const FINAL OVERRIDE; |
| |
| void add_events_to_path (checker_path *emission_path, |
| const exploded_edge &eedge) const FINAL OVERRIDE; |
| private: |
| const gcall *m_dynamic_call; |
| const bool m_is_returning_call; |
| }; |
| |
| |
| /* Extra data for an exploded_edge that represents a rewind from a |
| longjmp to a setjmp (or from a siglongjmp to a sigsetjmp). */ |
| |
| class rewind_info_t : public custom_edge_info |
| { |
| public: |
| rewind_info_t (const setjmp_record &setjmp_record, |
| const gcall *longjmp_call) |
| : m_setjmp_record (setjmp_record), |
| m_longjmp_call (longjmp_call) |
| {} |
| |
| void print (pretty_printer *pp) const FINAL OVERRIDE |
| { |
| pp_string (pp, "rewind"); |
| } |
| |
| bool update_model (region_model *model, |
| const exploded_edge *eedge, |
| region_model_context *ctxt) const FINAL OVERRIDE; |
| |
| void add_events_to_path (checker_path *emission_path, |
| const exploded_edge &eedge) const FINAL OVERRIDE; |
| |
| const program_point &get_setjmp_point () const |
| { |
| const program_point &origin_point = get_enode_origin ()->get_point (); |
| |
| /* "origin_point" ought to be before the call to "setjmp". */ |
| gcc_assert (origin_point.get_kind () == PK_BEFORE_STMT); |
| |
| /* TODO: assert that it's the final stmt in its supernode. */ |
| |
| return origin_point; |
| } |
| |
| const gcall *get_setjmp_call () const |
| { |
| return m_setjmp_record.m_setjmp_call; |
| } |
| |
| const gcall *get_longjmp_call () const |
| { |
| return m_longjmp_call; |
| } |
| |
| const exploded_node *get_enode_origin () const |
| { |
| return m_setjmp_record.m_enode; |
| } |
| |
| private: |
| setjmp_record m_setjmp_record; |
| const gcall *m_longjmp_call; |
| }; |
| |
| /* Statistics about aspects of an exploded_graph. */ |
| |
| struct stats |
| { |
| stats (int num_supernodes); |
| void log (logger *logger) const; |
| void dump (FILE *out) const; |
| |
| int get_total_enodes () const; |
| |
| int m_num_nodes[NUM_POINT_KINDS]; |
| int m_node_reuse_count; |
| int m_node_reuse_after_merge_count; |
| int m_num_supernodes; |
| }; |
| |
| /* Traits class for ensuring uniqueness of point_and_state data within |
| an exploded_graph. */ |
| |
| struct eg_hash_map_traits |
| { |
| typedef const point_and_state *key_type; |
| typedef exploded_node *value_type; |
| typedef exploded_node *compare_type; |
| |
| static inline hashval_t hash (const key_type &k) |
| { |
| gcc_assert (k != NULL); |
| gcc_assert (k != reinterpret_cast<key_type> (1)); |
| return k->hash (); |
| } |
| static inline bool equal_keys (const key_type &k1, const key_type &k2) |
| { |
| gcc_assert (k1 != NULL); |
| gcc_assert (k2 != NULL); |
| gcc_assert (k1 != reinterpret_cast<key_type> (1)); |
| gcc_assert (k2 != reinterpret_cast<key_type> (1)); |
| if (k1 && k2) |
| return *k1 == *k2; |
| else |
| /* Otherwise they must both be non-NULL. */ |
| return k1 == k2; |
| } |
| template <typename T> |
| static inline void remove (T &) |
| { |
| /* empty; the nodes are handled elsewhere. */ |
| } |
| template <typename T> |
| static inline void mark_deleted (T &entry) |
| { |
| entry.m_key = reinterpret_cast<key_type> (1); |
| } |
| template <typename T> |
| static inline void mark_empty (T &entry) |
| { |
| entry.m_key = NULL; |
| } |
| template <typename T> |
| static inline bool is_deleted (const T &entry) |
| { |
| return entry.m_key == reinterpret_cast<key_type> (1); |
| } |
| template <typename T> |
| static inline bool is_empty (const T &entry) |
| { |
| return entry.m_key == NULL; |
| } |
| static const bool empty_zero_p = false; |
| }; |
| |
| /* Per-program_point data for an exploded_graph. */ |
| |
| struct per_program_point_data |
| { |
| per_program_point_data (const program_point &key) |
| : m_key (key), m_excess_enodes (0) |
| {} |
| |
| const program_point m_key; |
| auto_vec<exploded_node *> m_enodes; |
| /* The number of attempts to create an enode for this point |
| after exceeding --param=analyzer-max-enodes-per-program-point. */ |
| int m_excess_enodes; |
| }; |
| |
| /* Traits class for storing per-program_point data within |
| an exploded_graph. */ |
| |
| struct eg_point_hash_map_traits |
| { |
| typedef const program_point *key_type; |
| typedef per_program_point_data *value_type; |
| typedef per_program_point_data *compare_type; |
| |
| static inline hashval_t hash (const key_type &k) |
| { |
| gcc_assert (k != NULL); |
| gcc_assert (k != reinterpret_cast<key_type> (1)); |
| return k->hash (); |
| } |
| static inline bool equal_keys (const key_type &k1, const key_type &k2) |
| { |
| gcc_assert (k1 != NULL); |
| gcc_assert (k2 != NULL); |
| gcc_assert (k1 != reinterpret_cast<key_type> (1)); |
| gcc_assert (k2 != reinterpret_cast<key_type> (1)); |
| if (k1 && k2) |
| return *k1 == *k2; |
| else |
| /* Otherwise they must both be non-NULL. */ |
| return k1 == k2; |
| } |
| template <typename T> |
| static inline void remove (T &) |
| { |
| /* empty; the nodes are handled elsewhere. */ |
| } |
| template <typename T> |
| static inline void mark_deleted (T &entry) |
| { |
| entry.m_key = reinterpret_cast<key_type> (1); |
| } |
| template <typename T> |
| static inline void mark_empty (T &entry) |
| { |
| entry.m_key = NULL; |
| } |
| template <typename T> |
| static inline bool is_deleted (const T &entry) |
| { |
| return entry.m_key == reinterpret_cast<key_type> (1); |
| } |
| template <typename T> |
| static inline bool is_empty (const T &entry) |
| { |
| return entry.m_key == NULL; |
| } |
| static const bool empty_zero_p = false; |
| }; |
| |
| /* Data about a particular call_string within an exploded_graph. */ |
| |
| struct per_call_string_data |
| { |
| per_call_string_data (const call_string &key, int num_supernodes) |
| : m_key (key), m_stats (num_supernodes) |
| {} |
| |
| const call_string m_key; |
| stats m_stats; |
| }; |
| |
| /* Traits class for storing per-call_string data within |
| an exploded_graph. */ |
| |
| struct eg_call_string_hash_map_traits |
| { |
| typedef const call_string *key_type; |
| typedef per_call_string_data *value_type; |
| typedef per_call_string_data *compare_type; |
| |
| static inline hashval_t hash (const key_type &k) |
| { |
| gcc_assert (k != NULL); |
| gcc_assert (k != reinterpret_cast<key_type> (1)); |
| return k->hash (); |
| } |
| static inline bool equal_keys (const key_type &k1, const key_type &k2) |
| { |
| gcc_assert (k1 != NULL); |
| gcc_assert (k2 != NULL); |
| gcc_assert (k1 != reinterpret_cast<key_type> (1)); |
| gcc_assert (k2 != reinterpret_cast<key_type> (1)); |
| if (k1 && k2) |
| return *k1 == *k2; |
| else |
| /* Otherwise they must both be non-NULL. */ |
| return k1 == k2; |
| } |
| template <typename T> |
| static inline void remove (T &) |
| { |
| /* empty; the nodes are handled elsewhere. */ |
| } |
| template <typename T> |
| static inline void mark_deleted (T &entry) |
| { |
| entry.m_key = reinterpret_cast<key_type> (1); |
| } |
| template <typename T> |
| static inline void mark_empty (T &entry) |
| { |
| entry.m_key = NULL; |
| } |
| template <typename T> |
| static inline bool is_deleted (const T &entry) |
| { |
| return entry.m_key == reinterpret_cast<key_type> (1); |
| } |
| template <typename T> |
| static inline bool is_empty (const T &entry) |
| { |
| return entry.m_key == NULL; |
| } |
| static const bool empty_zero_p = false; |
| }; |
| |
| /* Data about a particular function within an exploded_graph. */ |
| |
| struct per_function_data |
| { |
| per_function_data () {} |
| |
| void add_call_summary (exploded_node *node) |
| { |
| m_summaries.safe_push (node); |
| } |
| |
| auto_vec<exploded_node *> m_summaries; |
| }; |
| |
| |
| /* The strongly connected components of a supergraph. |
| In particular, this allows us to compute a partial ordering |
| of supernodes. */ |
| |
| class strongly_connected_components |
| { |
| public: |
| strongly_connected_components (const supergraph &sg, logger *logger); |
| |
| int get_scc_id (int node_index) const |
| { |
| return m_per_node[node_index].m_lowlink; |
| } |
| |
| void dump () const; |
| |
| json::array *to_json () const; |
| |
| private: |
| struct per_node_data |
| { |
| per_node_data () |
| : m_index (-1), m_lowlink (-1), m_on_stack (false) |
| {} |
| |
| int m_index; |
| int m_lowlink; |
| bool m_on_stack; |
| }; |
| |
| void strong_connect (unsigned index); |
| |
| const supergraph &m_sg; |
| auto_vec<unsigned> m_stack; |
| auto_vec<per_node_data> m_per_node; |
| }; |
| |
| /* The worklist of exploded_node instances that have been added to |
| an exploded_graph, but that haven't yet been processed to find |
| their successors (or warnings). |
| |
| The enodes are stored in a priority queue, ordered by a topological |
| sort of the SCCs in the supergraph, so that enodes for the same |
| program_point should appear at the front of the queue together. |
| This allows for state-merging at CFG join-points, so that |
| sufficiently-similar enodes can be merged into one. */ |
| |
| class worklist |
| { |
| public: |
| worklist (const exploded_graph &eg, const analysis_plan &plan); |
| unsigned length () const; |
| exploded_node *take_next (); |
| exploded_node *peek_next (); |
| void add_node (exploded_node *enode); |
| int get_scc_id (const supernode &snode) const |
| { |
| return m_scc.get_scc_id (snode.m_index); |
| } |
| |
| json::object *to_json () const; |
| |
| private: |
| class key_t |
| { |
| public: |
| key_t (const worklist &w, exploded_node *enode) |
| : m_worklist (w), m_enode (enode) |
| {} |
| |
| bool operator< (const key_t &other) const |
| { |
| return cmp (*this, other) < 0; |
| } |
| |
| bool operator== (const key_t &other) const |
| { |
| return cmp (*this, other) == 0; |
| } |
| |
| bool operator> (const key_t &other) const |
| { |
| return !(*this == other || *this < other); |
| } |
| |
| private: |
| static int cmp (const key_t &ka, const key_t &kb); |
| |
| int get_scc_id (const exploded_node *enode) const |
| { |
| const supernode *snode = enode->get_supernode (); |
| if (snode == NULL) |
| return 0; |
| return m_worklist.m_scc.get_scc_id (snode->m_index); |
| } |
| |
| const worklist &m_worklist; |
| exploded_node *m_enode; |
| }; |
| |
| /* The order is important here: m_scc needs to stick around |
| until after m_queue has finished being cleaned up (the dtor |
| calls the ordering fns). */ |
| strongly_connected_components m_scc; |
| const analysis_plan &m_plan; |
| |
| /* Priority queue, backed by a fibonacci_heap. */ |
| typedef fibonacci_heap<key_t, exploded_node> queue_t; |
| queue_t m_queue; |
| }; |
| |
| /* An exploded_graph is a directed graph of unique <point, state> pairs. |
| It also has a worklist of nodes that are waiting for their successors |
| to be added to the graph. */ |
| |
| class exploded_graph : public digraph<eg_traits> |
| { |
| public: |
| typedef hash_map <const call_string *, per_call_string_data *, |
| eg_call_string_hash_map_traits> call_string_data_map_t; |
| |
| exploded_graph (const supergraph &sg, logger *logger, |
| const extrinsic_state &ext_state, |
| const state_purge_map *purge_map, |
| const analysis_plan &plan, |
| int verbosity); |
| ~exploded_graph (); |
| |
| logger *get_logger () const { return m_logger.get_logger (); } |
| |
| const supergraph &get_supergraph () const { return m_sg; } |
| const extrinsic_state &get_ext_state () const { return m_ext_state; } |
| engine *get_engine () const { return m_ext_state.get_engine (); } |
| const state_purge_map *get_purge_map () const { return m_purge_map; } |
| const analysis_plan &get_analysis_plan () const { return m_plan; } |
| |
| exploded_node *get_origin () const { return m_origin; } |
| |
| exploded_node *add_function_entry (function *fun); |
| |
| void build_initial_worklist (); |
| void process_worklist (); |
| bool maybe_process_run_of_before_supernode_enodes (exploded_node *node); |
| void process_node (exploded_node *node); |
| |
| bool maybe_create_dynamic_call (const gcall *call, |
| tree fn_decl, |
| exploded_node *node, |
| program_state next_state, |
| program_point &next_point, |
| uncertainty_t *uncertainty, |
| logger *logger); |
| |
| exploded_node *get_or_create_node (const program_point &point, |
| const program_state &state, |
| exploded_node *enode_for_diag); |
| exploded_edge *add_edge (exploded_node *src, exploded_node *dest, |
| const superedge *sedge, |
| custom_edge_info *custom = NULL); |
| |
| per_program_point_data * |
| get_or_create_per_program_point_data (const program_point &); |
| per_program_point_data * |
| get_per_program_point_data (const program_point &) const; |
| |
| per_call_string_data * |
| get_or_create_per_call_string_data (const call_string &); |
| |
| per_function_data * |
| get_or_create_per_function_data (function *); |
| per_function_data *get_per_function_data (function *) const; |
| |
| void save_diagnostic (const state_machine &sm, |
| const exploded_node *enode, |
| const supernode *node, const gimple *stmt, |
| stmt_finder *finder, |
| tree var, state_machine::state_t state, |
| pending_diagnostic *d); |
| |
| diagnostic_manager &get_diagnostic_manager () |
| { |
| return m_diagnostic_manager; |
| } |
| const diagnostic_manager &get_diagnostic_manager () const |
| { |
| return m_diagnostic_manager; |
| } |
| |
| stats *get_global_stats () { return &m_global_stats; } |
| stats *get_or_create_function_stats (function *fn); |
| void log_stats () const; |
| void dump_stats (FILE *) const; |
| void dump_states_for_supernode (FILE *, const supernode *snode) const; |
| void dump_exploded_nodes () const; |
| |
| json::object *to_json () const; |
| |
| exploded_node *get_node_by_index (int idx) const; |
| |
| const call_string_data_map_t *get_per_call_string_data () const |
| { return &m_per_call_string_data; } |
| |
| int get_scc_id (const supernode &node) const |
| { |
| return m_worklist.get_scc_id (node); |
| } |
| |
| void on_escaped_function (tree fndecl); |
| |
| private: |
| void print_bar_charts (pretty_printer *pp) const; |
| |
| DISABLE_COPY_AND_ASSIGN (exploded_graph); |
| |
| const supergraph &m_sg; |
| |
| log_user m_logger; |
| |
| /* Map from point/state to exploded node. |
| To avoid duplication we store point_and_state |
| *pointers* as keys, rather than point_and_state, using the |
| instance from within the exploded_node, with a custom hasher. */ |
| typedef hash_map <const point_and_state *, exploded_node *, |
| eg_hash_map_traits> map_t; |
| map_t m_point_and_state_to_node; |
| |
| /* Map from program_point to per-program_point data. */ |
| typedef hash_map <const program_point *, per_program_point_data *, |
| eg_point_hash_map_traits> point_map_t; |
| point_map_t m_per_point_data; |
| |
| worklist m_worklist; |
| |
| exploded_node *m_origin; |
| |
| const extrinsic_state &m_ext_state; |
| |
| const state_purge_map *const m_purge_map; |
| |
| const analysis_plan &m_plan; |
| |
| typedef hash_map<function *, per_function_data *> per_function_data_t; |
| per_function_data_t m_per_function_data; |
| |
| diagnostic_manager m_diagnostic_manager; |
| |
| /* Stats. */ |
| stats m_global_stats; |
| typedef ordered_hash_map<function *, stats *> function_stat_map_t; |
| function_stat_map_t m_per_function_stats; |
| stats m_functionless_stats; |
| |
| call_string_data_map_t m_per_call_string_data; |
| |
| auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; |
| |
| /* Functions with a top-level enode, to make add_function_entry |
| be idempotent, for use in handling callbacks. */ |
| hash_set<function *> m_functions_with_enodes; |
| }; |
| |
| /* A path within an exploded_graph: a sequence of edges. */ |
| |
| class exploded_path |
| { |
| public: |
| exploded_path () : m_edges () {} |
| exploded_path (const exploded_path &other); |
| |
| unsigned length () const { return m_edges.length (); } |
| |
| bool find_stmt_backwards (const gimple *search_stmt, |
| int *out_idx) const; |
| |
| exploded_node *get_final_enode () const; |
| |
| void dump_to_pp (pretty_printer *pp, |
| const extrinsic_state *ext_state) const; |
| void dump (FILE *fp, const extrinsic_state *ext_state) const; |
| void dump (const extrinsic_state *ext_state = NULL) const; |
| void dump_to_file (const char *filename, |
| const extrinsic_state &ext_state) const; |
| |
| bool feasible_p (logger *logger, feasibility_problem **out, |
| engine *eng, const exploded_graph *eg) const; |
| |
| auto_vec<const exploded_edge *> m_edges; |
| }; |
| |
| /* A reason why a particular exploded_path is infeasible. */ |
| |
| class feasibility_problem |
| { |
| public: |
| feasibility_problem (unsigned eedge_idx, |
| const exploded_edge &eedge, |
| const gimple *last_stmt, |
| rejected_constraint *rc) |
| : m_eedge_idx (eedge_idx), m_eedge (eedge), |
| m_last_stmt (last_stmt), m_rc (rc) |
| {} |
| ~feasibility_problem () { delete m_rc; } |
| |
| void dump_to_pp (pretty_printer *pp) const; |
| |
| unsigned m_eedge_idx; |
| const exploded_edge &m_eedge; |
| const gimple *m_last_stmt; |
| rejected_constraint *m_rc; |
| }; |
| |
| /* A class for capturing the state of a node when checking a path |
| through the exploded_graph for feasibility. */ |
| |
| class feasibility_state |
| { |
| public: |
| feasibility_state (region_model_manager *manager, |
| const supergraph &sg); |
| feasibility_state (const feasibility_state &other); |
| |
| bool maybe_update_for_edge (logger *logger, |
| const exploded_edge *eedge, |
| rejected_constraint **out_rc); |
| |
| const region_model &get_model () const { return m_model; } |
| const auto_sbitmap &get_snodes_visited () const { return m_snodes_visited; } |
| |
| private: |
| region_model m_model; |
| auto_sbitmap m_snodes_visited; |
| }; |
| |
| /* Finding the shortest exploded_path within an exploded_graph. */ |
| |
| typedef shortest_paths<eg_traits, exploded_path> shortest_exploded_paths; |
| |
| /* Abstract base class for use when passing NULL as the stmt for |
| a possible warning, allowing the choice of stmt to be deferred |
| until after we have an emission path (and know we're emitting a |
| warning). */ |
| |
| class stmt_finder |
| { |
| public: |
| virtual ~stmt_finder () {} |
| virtual stmt_finder *clone () const = 0; |
| virtual const gimple *find_stmt (const exploded_path &epath) = 0; |
| }; |
| |
| // TODO: split the above up? |
| |
| } // namespace ana |
| |
| #endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */ |