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 | |
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 | #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 | |
52 | namespace ana { |
53 | |
54 | /* class trimmed_node : public dnode<tg_traits>. */ |
55 | |
56 | /* Implementation of dump_dot vfunc, delegating to the inner node. */ |
57 | |
58 | void |
59 | trimmed_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 | |
69 | trimmed_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 | |
77 | void |
78 | trimmed_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 | |
88 | trimmed_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 | |
151 | void |
152 | trimmed_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 | |