From patchwork Sat Nov 16 01:23:30 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1196042 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-513766-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="LleOt5sb"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.b="jM6s/J2w"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47FHkb0PF8z9sPV for ; Sat, 16 Nov 2019 12:31:50 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :content-type:content-transfer-encoding; q=dns; s=default; b=pBb VI9pIjDjoCOkvglMsmnT4Ht3Zbj5ThbfYENRdDwS+d1DsWsEbm3TuwE8JzSeXpWG uNPxWqR61zkusBfFxjhlB89OURjQB1GN6pS1CvU6yc4VvyZ8eHxdhi42Imkpt3zR 87/+TwVIjoD93VSz5TlniNna1qWOu7h0kSJclOYE= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :content-type:content-transfer-encoding; s=default; bh=ik25nN8xS 0/ZETYXveoFYH23H2Y=; b=LleOt5sbzKtHVJbmLm3/XV7x0isdqKpzmqPW2qsbd DJ3ADDQ11tzxbKtoLB67SihGT6LR7bbCpHHDQ/kXl6qOJK7ZxaLZ0m2XAgubTlEi pA1m7i7T6nv7SOlsch/piXJ9Qjz/R0jkShSFSJ7Osix49Iuj/fxVrLyPgaLyPN0o CA= Received: (qmail 83530 invoked by alias); 16 Nov 2019 01:21:39 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 68202 invoked by uid 89); 16 Nov 2019 01:19:17 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.6 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, T_FILL_THIS_FORM_SHORT autolearn=ham version=3.3.1 spammy= X-HELO: us-smtp-1.mimecast.com Received: from us-smtp-delivery-1.mimecast.com (HELO us-smtp-1.mimecast.com) (207.211.31.120) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sat, 16 Nov 2019 01:19:12 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1573867150; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=dgWexEYjCel7XyAXkDdcjesXaeBUrZtjhwHJdGtJ8hg=; b=jM6s/J2wZorrG0MFa5U9cyrjvgiXiI/TAkZJ1QxPuLvyn95mwkTuceR4rO+GDbWi7gi/As p6CBqdTUVDxfV3aFzgSblXpvKiB/vpz8aEJaYiSCmxGZ7A0zWbOlrF7rifXvqxYDudSSXy SpCBLZ7hXDnC2SXG9KFZ0hA9TQluYPM= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-140-B6H00f_rOqKJwPYLQKJM8w-1; Fri, 15 Nov 2019 20:17:59 -0500 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 1ADB318B9FC1 for ; Sat, 16 Nov 2019 01:17:59 +0000 (UTC) Received: from c64.redhat.com (ovpn-112-32.phx2.redhat.com [10.3.112.32]) by smtp.corp.redhat.com (Postfix) with ESMTP id 3886610246FB; Sat, 16 Nov 2019 01:17:58 +0000 (UTC) From: David Malcolm To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [PATCH 43/49] analyzer: new file: exploded-graph.h Date: Fri, 15 Nov 2019 20:23:30 -0500 Message-Id: <1573867416-55618-44-git-send-email-dmalcolm@redhat.com> In-Reply-To: <1573867416-55618-1-git-send-email-dmalcolm@redhat.com> References: <1573867416-55618-1-git-send-email-dmalcolm@redhat.com> X-Mimecast-Spam-Score: 0 X-IsSubscribed: yes This patch adds exploded_graph and related classes, for managing exploring paths through the user's code as a directed graph of pairs. gcc/ChangeLog: * analyzer/exploded-graph.h: New file. --- gcc/analyzer/exploded-graph.h | 754 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 754 insertions(+) create mode 100644 gcc/analyzer/exploded-graph.h diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h new file mode 100644 index 0000000..f97d2b6 --- /dev/null +++ b/gcc/analyzer/exploded-graph.h @@ -0,0 +1,754 @@ +/* Classes for managing a directed graph of pairs. + Copyright (C) 2019 Free Software Foundation, Inc. + Contributed by David Malcolm . + +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 +. */ + +#ifndef GCC_ANALYZER_EXPLODED_GRAPH_H +#define GCC_ANALYZER_EXPLODED_GRAPH_H + +#include "fibonacci_heap.h" +#include "analyzer/analyzer-logging.h" +#include "analyzer/constraint-manager.h" +#include "analyzer/diagnostic-manager.h" +#include "analyzer/program-point.h" +#include "analyzer/program-state.h" +#include "analyzer/shortest-paths.h" + +/////////////////////////////////////////////////////////////////////////// + +/* 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 log_user +{ + public: + impl_region_model_context (exploded_graph &eg, + const 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, + state_change *change, + + const gimple *stmt, + stmt_finder *stmt_finder = NULL); + + impl_region_model_context (program_state *state, + state_change *change, + const extrinsic_state &ext_state); + + void warn (pending_diagnostic *d) FINAL OVERRIDE; + + void remap_svalue_ids (const svalue_id_map &map) FINAL OVERRIDE; + + int on_svalue_purge (svalue_id first_unused_sid, + const svalue_id_map &map) FINAL OVERRIDE; + + logger *get_logger () FINAL OVERRIDE + { + return log_user::get_logger (); + } + + void on_state_leak (const state_machine &sm, + int sm_idx, + svalue_id sid, + svalue_id first_unused_sid, + const svalue_id_map &map, + state_machine::state_t state); + + void on_inherited_svalue (svalue_id parent_sid, + svalue_id child_sid) FINAL OVERRIDE; + + void on_cast (svalue_id src_sid, + svalue_id dst_sid) FINAL OVERRIDE; + + void on_condition (tree lhs, enum tree_code op, tree rhs) FINAL OVERRIDE; + + exploded_graph *m_eg; + const exploded_node *m_enode_for_diag; + const program_state *m_old_state; + program_state *m_new_state; + state_change *m_change; + const gimple *m_stmt; + stmt_finder *m_stmt_finder; + const extrinsic_state &m_ext_state; +}; + +//////////////////////////////////////////////////////////////////////////// + +/* A 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. */ + +struct point_and_state +{ + 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 ()) + { + } + + 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; + } + + void set_state (const program_state &state) + { + m_state = state; + m_hash = m_point.hash () ^ m_state.hash (); + } + + 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) {} + const exploded_graph &m_eg; + }; + typedef exploded_cluster cluster_t; +}; + +/* An exploded_node is a unique, immutable pair within the + exploded_graph. + Each exploded_node has a unique index within the graph + (for ease of debugging). */ + +class exploded_node : public dnode +{ + public: + exploded_node (point_and_state ps, + int index) + : m_ps (ps), m_index (index) + { + gcc_checking_assert (ps.m_state.m_region_model->canonicalized_p ()); + } + + hashval_t hash () const { return m_ps.hash (); } + + 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; + + bool on_stmt (exploded_graph &eg, + const supernode *snode, + const gimple *stmt, + program_state *state, + state_change *change) const; + bool on_edge (exploded_graph &eg, + const superedge *succ, + program_point *next_point, + program_state *next_state, + state_change *change) const; + void on_longjmp (exploded_graph &eg, + const gcall *call, + program_state *new_state, + region_model_context *ctxt) const; + + void detect_leaks (exploded_graph &eg) const; + + const program_point &get_point () const { return m_ps.m_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 program_state &get_state () const { return m_ps.m_state; } + + const point_and_state *get_ps_key () const { return &m_ps; } + const program_point *get_point_key () const { return &m_ps.m_point; } + + void dump_succs_and_preds (FILE *outf) const; + +private: + const char * get_dot_fillcolor () const; + + /* The pair. This is const, as it + is immutable once the exploded_node has been created. */ + const point_and_state m_ps; + +public: + /* The index of this exploded_node. */ + const int m_index; +}; + +/* Extra data for an exploded_edge that represents a rewind from a + longjmp to a setjmp. */ + +class rewind_info_t +{ +public: + rewind_info_t (const exploded_node *enode_origin) + : m_enode_origin (enode_origin) + {} + + const program_point &get_setjmp_point () const + { + const program_point &origin_point = m_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 as_a (get_setjmp_point ().get_stmt ()); + } + + const exploded_node *get_enode_origin () const { return m_enode_origin; } + +private: + const exploded_node *m_enode_origin; +}; + +/* An edge within the exploded graph. + Some exploded_edges have an underlying superedge; others don't. */ + +class exploded_edge : public dedge +{ + public: + exploded_edge (exploded_node *src, exploded_node *dest, + const superedge *sedge, + const state_change &change, + rewind_info_t *rewind_info); + ~exploded_edge (); + void dump_dot (graphviz_out *gv, const dump_args_t &args) + const FINAL OVERRIDE; + + //private: + const superedge *const m_sedge; + + const state_change m_change; + + /* NULL for most edges; will be non-NULL for an unwind from a longjmp + to a setjmp (owned by this class). */ + rewind_info_t *m_rewind_info; +}; + +/* Statistics about aspects of an exploded_graph. */ + +struct stats +{ + stats (int num_supernodes); + void log (logger *logger) const; + void dump (FILE *out) 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 (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 (1)); + gcc_assert (k2 != reinterpret_cast (1)); + if (k1 && k2) + return *k1 == *k2; + else + /* Otherwise they must both be non-NULL. */ + return k1 == k2; + } + template + static inline void remove (T &) + { + /* empty; the nodes are handled elsewhere. */ + } + template + static inline void mark_deleted (T &entry) + { + entry.m_key = reinterpret_cast (1); + } + template + static inline void mark_empty (T &entry) + { + entry.m_key = NULL; + } + template + static inline bool is_deleted (const T &entry) + { + return entry.m_key == reinterpret_cast (1); + } + template + static inline bool is_empty (const T &entry) + { + return entry.m_key == NULL; + } +}; + +/* Per-program_point data for an exploded_graph. */ + +struct per_program_point_data +{ + per_program_point_data (const program_point &key) + : m_key (key) + {} + + program_point m_key; + auto_vec m_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 (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 (1)); + gcc_assert (k2 != reinterpret_cast (1)); + if (k1 && k2) + return *k1 == *k2; + else + /* Otherwise they must both be non-NULL. */ + return k1 == k2; + } + template + static inline void remove (T &) + { + /* empty; the nodes are handled elsewhere. */ + } + template + static inline void mark_deleted (T &entry) + { + entry.m_key = reinterpret_cast (1); + } + template + static inline void mark_empty (T &entry) + { + entry.m_key = NULL; + } + template + static inline bool is_deleted (const T &entry) + { + return entry.m_key == reinterpret_cast (1); + } + template + static inline bool is_empty (const T &entry) + { + return entry.m_key == NULL; + } +}; + +/* 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) + {} + + 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 (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 (1)); + gcc_assert (k2 != reinterpret_cast (1)); + if (k1 && k2) + return *k1 == *k2; + else + /* Otherwise they must both be non-NULL. */ + return k1 == k2; + } + template + static inline void remove (T &) + { + /* empty; the nodes are handled elsewhere. */ + } + template + static inline void mark_deleted (T &entry) + { + entry.m_key = reinterpret_cast (1); + } + template + static inline void mark_empty (T &entry) + { + entry.m_key = NULL; + } + template + static inline bool is_deleted (const T &entry) + { + return entry.m_key == reinterpret_cast (1); + } + template + static inline bool is_empty (const T &entry) + { + return entry.m_key == NULL; + } +}; + +/* 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 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; + +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 m_stack; + auto_vec 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); + +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_1 (const key_t &ka, const key_t &kb); + 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). */ + const exploded_graph &m_eg; + strongly_connected_components m_scc; + const analysis_plan &m_plan; + + /* Priority queue, backed by a fibonacci_heap. */ + typedef fibonacci_heap queue_t; + queue_t m_queue; +}; + +/* An exploded_graph is a directed graph of unique 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, public log_user +{ +public: + typedef hash_map 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 (); + + const supergraph &get_supergraph () const { return m_sg; } + const extrinsic_state &get_ext_state () const { return m_ext_state; } + 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 (); + void process_node (exploded_node *node); + + exploded_node *get_or_create_node (const program_point &point, + const program_state &state, + state_change *change); + void add_edge (exploded_node *src, exploded_node *dest, + const superedge *sedge, + const state_change &change, + rewind_info_t *rewind_info = NULL); + + per_program_point_data * + get_or_create_per_program_point_data (const program_point &); + + 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; + } + + 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; + + const call_string_data_map_t *get_per_call_string_data () const + { return &m_per_call_string_data; } + +private: + const supergraph &m_sg; + + /* 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 map_t; + map_t m_point_and_state_to_node; + + /* Map from program_point to per-program_point data. */ + typedef hash_map 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 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_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 m_PK_AFTER_SUPERNODE_per_snode; +}; + +/* A path within an exploded_graph: a sequence of edges. */ + +class exploded_path +{ +public: + exploded_path () : m_edges () {} + exploded_path (const exploded_path &other); + exploded_path & operator= (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; + void dump (FILE *fp) const; + void dump () const; + + bool feasible_p (logger *logger) const; + + auto_vec m_edges; +}; + +/* Finding the shortest exploded_path within an exploded_graph. */ + +typedef shortest_paths 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? + +#endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */