173 lines
5.0 KiB
C++
173 lines
5.0 KiB
C++
/* Trimming an exploded graph to a subset of nodes and edges.
|
|
Copyright (C) 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/>. */
|
|
|
|
#include "config.h"
|
|
#include "system.h"
|
|
#include "coretypes.h"
|
|
#include "tree.h"
|
|
#include "pretty-print.h"
|
|
#include "gcc-rich-location.h"
|
|
#include "gimple-pretty-print.h"
|
|
#include "function.h"
|
|
#include "diagnostic-core.h"
|
|
#include "diagnostic-event-id.h"
|
|
#include "diagnostic-path.h"
|
|
#include "alloc-pool.h"
|
|
#include "fibonacci_heap.h"
|
|
#include "shortest-paths.h"
|
|
#include "sbitmap.h"
|
|
#include "bitmap.h"
|
|
#include "tristate.h"
|
|
#include "selftest.h"
|
|
#include "ordered-hash-map.h"
|
|
#include "json.h"
|
|
#include "analyzer/analyzer.h"
|
|
#include "analyzer/analyzer-logging.h"
|
|
#include "analyzer/sm.h"
|
|
#include "analyzer/pending-diagnostic.h"
|
|
#include "analyzer/diagnostic-manager.h"
|
|
#include "analyzer/call-string.h"
|
|
#include "analyzer/program-point.h"
|
|
#include "analyzer/store.h"
|
|
#include "analyzer/region-model.h"
|
|
#include "analyzer/constraint-manager.h"
|
|
#include "cfg.h"
|
|
#include "basic-block.h"
|
|
#include "gimple.h"
|
|
#include "gimple-iterator.h"
|
|
#include "cgraph.h"
|
|
#include "digraph.h"
|
|
#include "analyzer/supergraph.h"
|
|
#include "analyzer/program-state.h"
|
|
#include "analyzer/exploded-graph.h"
|
|
#include "analyzer/trimmed-graph.h"
|
|
|
|
#if ENABLE_ANALYZER
|
|
|
|
namespace ana {
|
|
|
|
/* class trimmed_node : public dnode<tg_traits>. */
|
|
|
|
/* Implementation of dump_dot vfunc, delegating to the inner node. */
|
|
|
|
void
|
|
trimmed_node::dump_dot (graphviz_out *gv,
|
|
const dump_args_t &args) const
|
|
{
|
|
m_inner_node->dump_dot (gv, args.m_inner_args);
|
|
}
|
|
|
|
/* class trimmed_edge : public dedge<tg_traits>. */
|
|
|
|
/* trimmed_edge's ctor. */
|
|
|
|
trimmed_edge::trimmed_edge (trimmed_node *src, trimmed_node *dest,
|
|
const exploded_edge *inner_edge)
|
|
: dedge<tg_traits> (src, dest), m_inner_edge (inner_edge)
|
|
{
|
|
}
|
|
|
|
/* Implementation of dump_dot vfunc, delegating to the inner edge. */
|
|
|
|
void
|
|
trimmed_edge::dump_dot (graphviz_out *gv, const dump_args_t &args) const
|
|
{
|
|
m_inner_edge->dump_dot (gv, args.m_inner_args);
|
|
}
|
|
|
|
/* class trimmed_graph : public digraph <tg_traits>. */
|
|
|
|
/* Ctor for trimmed_graph: construct a graph equivalent to trimming
|
|
INNER_GRAPH to all nodes that can reach INNER_DST_NODE. */
|
|
|
|
trimmed_graph::trimmed_graph (const exploded_graph &inner_graph,
|
|
const exploded_node *inner_dst_node)
|
|
: m_enodes (), m_eedges ()
|
|
{
|
|
/* Determine what subset of nodes and edges to include in the
|
|
trimmed graph.
|
|
Walk backwards from INNER_DST_NODE, finding nodes that reach it,
|
|
iteratively building the set of nodes and edges. */
|
|
auto_vec <const exploded_node *> worklist;
|
|
worklist.safe_push (inner_dst_node);
|
|
m_enodes.add (inner_dst_node);
|
|
while (worklist.length () > 0)
|
|
{
|
|
const exploded_node *inner_node = worklist.pop ();
|
|
exploded_edge *inner_pred;
|
|
unsigned i;
|
|
FOR_EACH_VEC_ELT (inner_node->m_preds, i, inner_pred)
|
|
{
|
|
if (!m_enodes.contains (inner_pred->m_src))
|
|
{
|
|
worklist.safe_push (inner_pred->m_src);
|
|
m_enodes.add (inner_pred->m_src);
|
|
}
|
|
m_eedges.add (inner_pred);
|
|
}
|
|
}
|
|
|
|
/* Create trimmed nodes for all enodes in the set. */
|
|
{
|
|
/* Iterate over the vec rather than the hash_set
|
|
to ensure deterministic order. */
|
|
exploded_node *inner_node;
|
|
unsigned i;
|
|
FOR_EACH_VEC_ELT (inner_graph.m_nodes, i, inner_node)
|
|
if (m_enodes.contains (inner_node))
|
|
{
|
|
trimmed_node *tnode = new trimmed_node (inner_node);
|
|
add_node (tnode);
|
|
m_map_from_enode_to_tnode.put (inner_node, tnode);
|
|
}
|
|
}
|
|
|
|
/* Create trimmed edges for all edges in the set. */
|
|
{
|
|
/* Iterate over the vec rather than the hash_set
|
|
to ensure deterministic order. */
|
|
exploded_edge *inner_edge;
|
|
unsigned i;
|
|
FOR_EACH_VEC_ELT (inner_graph.m_edges, i, inner_edge)
|
|
if (m_eedges.contains (inner_edge))
|
|
{
|
|
const exploded_node *inner_src = inner_edge->m_src;
|
|
const exploded_node *inner_dest = inner_edge->m_dest;
|
|
trimmed_node *tsrc = *m_map_from_enode_to_tnode.get (inner_src);
|
|
trimmed_node *tdest = *m_map_from_enode_to_tnode.get (inner_dest);
|
|
trimmed_edge *tedge = new trimmed_edge (tsrc, tdest, inner_edge);
|
|
add_edge (tedge);
|
|
}
|
|
}
|
|
}
|
|
|
|
/* Dump stats about this graph to LOGGER. */
|
|
|
|
void
|
|
trimmed_graph::log_stats (logger *logger) const
|
|
{
|
|
logger->log ("#nodes: %i", m_nodes.length ());
|
|
logger->log ("#edges: %i", m_edges.length ());
|
|
}
|
|
|
|
} // namespace ana
|
|
|
|
#endif /* #if ENABLE_ANALYZER */
|