1/* Trimming an exploded graph to a subset of nodes and edges.
2 Copyright (C) 2021-2024 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#define INCLUDE_MEMORY
23#include "system.h"
24#include "coretypes.h"
25#include "tree.h"
26#include "pretty-print.h"
27#include "gcc-rich-location.h"
28#include "gimple-pretty-print.h"
29#include "function.h"
30#include "diagnostic-core.h"
31#include "diagnostic-event-id.h"
32#include "diagnostic-path.h"
33#include "bitmap.h"
34#include "ordered-hash-map.h"
35#include "analyzer/analyzer.h"
36#include "analyzer/analyzer-logging.h"
37#include "analyzer/sm.h"
38#include "analyzer/pending-diagnostic.h"
39#include "analyzer/diagnostic-manager.h"
40#include "analyzer/call-string.h"
41#include "analyzer/program-point.h"
42#include "analyzer/store.h"
43#include "analyzer/region-model.h"
44#include "analyzer/constraint-manager.h"
45#include "analyzer/supergraph.h"
46#include "analyzer/program-state.h"
47#include "analyzer/exploded-graph.h"
48#include "analyzer/trimmed-graph.h"
49
50#if ENABLE_ANALYZER
51
52namespace ana {
53
54/* class trimmed_node : public dnode<tg_traits>. */
55
56/* Implementation of dump_dot vfunc, delegating to the inner node. */
57
58void
59trimmed_node::dump_dot (graphviz_out *gv,
60 const dump_args_t &args) const
61{
62 m_inner_node->dump_dot (gv, args: args.m_inner_args);
63}
64
65/* class trimmed_edge : public dedge<tg_traits>. */
66
67/* trimmed_edge's ctor. */
68
69trimmed_edge::trimmed_edge (trimmed_node *src, trimmed_node *dest,
70 const exploded_edge *inner_edge)
71: dedge<tg_traits> (src, dest), m_inner_edge (inner_edge)
72{
73}
74
75/* Implementation of dump_dot vfunc, delegating to the inner edge. */
76
77void
78trimmed_edge::dump_dot (graphviz_out *gv, const dump_args_t &args) const
79{
80 m_inner_edge->dump_dot (gv, args: args.m_inner_args);
81}
82
83/* class trimmed_graph : public digraph <tg_traits>. */
84
85/* Ctor for trimmed_graph: construct a graph equivalent to trimming
86 INNER_GRAPH to all nodes that can reach INNER_DST_NODE. */
87
88trimmed_graph::trimmed_graph (const exploded_graph &inner_graph,
89 const exploded_node *inner_dst_node)
90: m_enodes (), m_eedges ()
91{
92 /* Determine what subset of nodes and edges to include in the
93 trimmed graph.
94 Walk backwards from INNER_DST_NODE, finding nodes that reach it,
95 iteratively building the set of nodes and edges. */
96 auto_vec <const exploded_node *> worklist;
97 worklist.safe_push (obj: inner_dst_node);
98 m_enodes.add (k: inner_dst_node);
99 while (worklist.length () > 0)
100 {
101 const exploded_node *inner_node = worklist.pop ();
102 exploded_edge *inner_pred;
103 unsigned i;
104 FOR_EACH_VEC_ELT (inner_node->m_preds, i, inner_pred)
105 {
106 if (!m_enodes.contains (k: inner_pred->m_src))
107 {
108 worklist.safe_push (obj: inner_pred->m_src);
109 m_enodes.add (k: inner_pred->m_src);
110 }
111 m_eedges.add (k: inner_pred);
112 }
113 }
114
115 /* Create trimmed nodes for all enodes in the set. */
116 {
117 /* Iterate over the vec rather than the hash_set
118 to ensure deterministic order. */
119 exploded_node *inner_node;
120 unsigned i;
121 FOR_EACH_VEC_ELT (inner_graph.m_nodes, i, inner_node)
122 if (m_enodes.contains (k: inner_node))
123 {
124 trimmed_node *tnode = new trimmed_node (inner_node);
125 add_node (node: tnode);
126 m_map_from_enode_to_tnode.put (k: inner_node, v: tnode);
127 }
128 }
129
130 /* Create trimmed edges for all edges in the set. */
131 {
132 /* Iterate over the vec rather than the hash_set
133 to ensure deterministic order. */
134 exploded_edge *inner_edge;
135 unsigned i;
136 FOR_EACH_VEC_ELT (inner_graph.m_edges, i, inner_edge)
137 if (m_eedges.contains (k: inner_edge))
138 {
139 const exploded_node *inner_src = inner_edge->m_src;
140 const exploded_node *inner_dest = inner_edge->m_dest;
141 trimmed_node *tsrc = *m_map_from_enode_to_tnode.get (k: inner_src);
142 trimmed_node *tdest = *m_map_from_enode_to_tnode.get (k: inner_dest);
143 trimmed_edge *tedge = new trimmed_edge (tsrc, tdest, inner_edge);
144 add_edge (edge: tedge);
145 }
146 }
147}
148
149/* Dump stats about this graph to LOGGER. */
150
151void
152trimmed_graph::log_stats (logger *logger) const
153{
154 logger->log (fmt: "#nodes: %i", m_nodes.length ());
155 logger->log (fmt: "#edges: %i", m_edges.length ());
156}
157
158} // namespace ana
159
160#endif /* #if ENABLE_ANALYZER */
161

source code of gcc/analyzer/trimmed-graph.cc