Branch data Line data Source code
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_VECTOR
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 : 124 : trimmed_node::dump_dot (graphviz_out *gv,
60 : : const dump_args_t &args) const
61 : : {
62 : 124 : m_inner_node->dump_dot (gv, args.m_inner_args);
63 : 124 : }
64 : :
65 : : /* class trimmed_edge : public dedge<tg_traits>. */
66 : :
67 : : /* trimmed_edge's ctor. */
68 : :
69 : 173941 : trimmed_edge::trimmed_edge (trimmed_node *src, trimmed_node *dest,
70 : 173941 : const exploded_edge *inner_edge)
71 : 173941 : : dedge<tg_traits> (src, dest), m_inner_edge (inner_edge)
72 : : {
73 : 173941 : }
74 : :
75 : : /* Implementation of dump_dot vfunc, delegating to the inner edge. */
76 : :
77 : : void
78 : 116 : trimmed_edge::dump_dot (graphviz_out *gv, const dump_args_t &args) const
79 : : {
80 : 116 : m_inner_edge->dump_dot (gv, args.m_inner_args);
81 : 116 : }
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 : 6624 : trimmed_graph::trimmed_graph (const exploded_graph &inner_graph,
89 : 6624 : const exploded_node *inner_dst_node)
90 : 6624 : : 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 : 6624 : auto_vec <const exploded_node *> worklist;
97 : 6624 : worklist.safe_push (inner_dst_node);
98 : 6624 : m_enodes.add (inner_dst_node);
99 : 368052 : while (worklist.length () > 0)
100 : : {
101 : 174090 : const exploded_node *inner_node = worklist.pop ();
102 : 174090 : exploded_edge *inner_pred;
103 : 174090 : unsigned i;
104 : 515497 : FOR_EACH_VEC_ELT (inner_node->m_preds, i, inner_pred)
105 : : {
106 : 173941 : if (!m_enodes.contains (inner_pred->m_src))
107 : : {
108 : 167466 : worklist.safe_push (inner_pred->m_src);
109 : 167466 : m_enodes.add (inner_pred->m_src);
110 : : }
111 : 173941 : m_eedges.add (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 : 1667892 : FOR_EACH_VEC_ELT (inner_graph.m_nodes, i, inner_node)
122 : 1661268 : if (m_enodes.contains (inner_node))
123 : : {
124 : 174090 : trimmed_node *tnode = new trimmed_node (inner_node);
125 : 174090 : add_node (tnode);
126 : 174090 : m_map_from_enode_to_tnode.put (inner_node, tnode);
127 : : }
128 : : }
129 : :
130 : : /* Create trimmed edges for all edges in the set. */
131 : 6624 : {
132 : : /* Iterate over the vec rather than the hash_set
133 : : to ensure deterministic order. */
134 : 6624 : exploded_edge *inner_edge;
135 : 6624 : unsigned i;
136 : 1728529 : FOR_EACH_VEC_ELT (inner_graph.m_edges, i, inner_edge)
137 : 1715281 : if (m_eedges.contains (inner_edge))
138 : : {
139 : 173941 : const exploded_node *inner_src = inner_edge->m_src;
140 : 173941 : const exploded_node *inner_dest = inner_edge->m_dest;
141 : 173941 : trimmed_node *tsrc = *m_map_from_enode_to_tnode.get (inner_src);
142 : 173941 : trimmed_node *tdest = *m_map_from_enode_to_tnode.get (inner_dest);
143 : 173941 : trimmed_edge *tedge = new trimmed_edge (tsrc, tdest, inner_edge);
144 : 173941 : add_edge (tedge);
145 : : }
146 : : }
147 : 6624 : }
148 : :
149 : : /* Dump stats about this graph to LOGGER. */
150 : :
151 : : void
152 : 0 : trimmed_graph::log_stats (logger *logger) const
153 : : {
154 : 0 : logger->log ("#nodes: %i", m_nodes.length ());
155 : 0 : logger->log ("#edges: %i", m_edges.length ());
156 : 0 : }
157 : :
158 : : } // namespace ana
159 : :
160 : : #endif /* #if ENABLE_ANALYZER */
|
