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