Branch data Line data Source code
1 : : /* Trimming an exploded graph to a subset of nodes and edges.
2 : : Copyright (C) 2021-2025 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 "analyzer/common.h"
22 : :
23 : : #include "analyzer/analyzer-logging.h"
24 : : #include "analyzer/sm.h"
25 : : #include "analyzer/pending-diagnostic.h"
26 : : #include "analyzer/diagnostic-manager.h"
27 : : #include "analyzer/call-string.h"
28 : : #include "analyzer/program-point.h"
29 : : #include "analyzer/store.h"
30 : : #include "analyzer/region-model.h"
31 : : #include "analyzer/constraint-manager.h"
32 : : #include "analyzer/supergraph.h"
33 : : #include "analyzer/program-state.h"
34 : : #include "analyzer/exploded-graph.h"
35 : : #include "analyzer/trimmed-graph.h"
36 : :
37 : : #if ENABLE_ANALYZER
38 : :
39 : : namespace ana {
40 : :
41 : : /* class trimmed_node : public dnode<tg_traits>. */
42 : :
43 : : /* Implementation of dump_dot vfunc, delegating to the inner node. */
44 : :
45 : : void
46 : 124 : trimmed_node::dump_dot (graphviz_out *gv,
47 : : const dump_args_t &args) const
48 : : {
49 : 124 : m_inner_node->dump_dot (gv, args.m_inner_args);
50 : 124 : }
51 : :
52 : : /* class trimmed_edge : public dedge<tg_traits>. */
53 : :
54 : : /* trimmed_edge's ctor. */
55 : :
56 : 168699 : trimmed_edge::trimmed_edge (trimmed_node *src, trimmed_node *dest,
57 : 168699 : const exploded_edge *inner_edge)
58 : 168699 : : dedge<tg_traits> (src, dest), m_inner_edge (inner_edge)
59 : : {
60 : 168699 : }
61 : :
62 : : /* Implementation of dump_dot vfunc, delegating to the inner edge. */
63 : :
64 : : void
65 : 116 : trimmed_edge::dump_dot (graphviz_out *gv, const dump_args_t &args) const
66 : : {
67 : 116 : m_inner_edge->dump_dot (gv, args.m_inner_args);
68 : 116 : }
69 : :
70 : : /* class trimmed_graph : public digraph <tg_traits>. */
71 : :
72 : : /* Ctor for trimmed_graph: construct a graph equivalent to trimming
73 : : INNER_GRAPH to all nodes that can reach INNER_DST_NODE. */
74 : :
75 : 6737 : trimmed_graph::trimmed_graph (const exploded_graph &inner_graph,
76 : 6737 : const exploded_node *inner_dst_node)
77 : 6737 : : m_enodes (), m_eedges ()
78 : : {
79 : : /* Determine what subset of nodes and edges to include in the
80 : : trimmed graph.
81 : : Walk backwards from INNER_DST_NODE, finding nodes that reach it,
82 : : iteratively building the set of nodes and edges. */
83 : 6737 : auto_vec <const exploded_node *> worklist;
84 : 6737 : worklist.safe_push (inner_dst_node);
85 : 6737 : m_enodes.add (inner_dst_node);
86 : 359273 : while (worklist.length () > 0)
87 : : {
88 : 169531 : const exploded_node *inner_node = worklist.pop ();
89 : 169531 : exploded_edge *inner_pred;
90 : 169531 : unsigned i;
91 : 501024 : FOR_EACH_VEC_ELT (inner_node->m_preds, i, inner_pred)
92 : : {
93 : 168699 : if (!m_enodes.contains (inner_pred->m_src))
94 : : {
95 : 162794 : worklist.safe_push (inner_pred->m_src);
96 : 162794 : m_enodes.add (inner_pred->m_src);
97 : : }
98 : 168699 : m_eedges.add (inner_pred);
99 : : }
100 : : }
101 : :
102 : : /* Create trimmed nodes for all enodes in the set. */
103 : : {
104 : : /* Iterate over the vec rather than the hash_set
105 : : to ensure deterministic order. */
106 : : exploded_node *inner_node;
107 : : unsigned i;
108 : 1652916 : FOR_EACH_VEC_ELT (inner_graph.m_nodes, i, inner_node)
109 : 1646179 : if (m_enodes.contains (inner_node))
110 : : {
111 : 169531 : trimmed_node *tnode = new trimmed_node (inner_node);
112 : 169531 : add_node (tnode);
113 : 169531 : m_map_from_enode_to_tnode.put (inner_node, tnode);
114 : : }
115 : : }
116 : :
117 : : /* Create trimmed edges for all edges in the set. */
118 : 6737 : {
119 : : /* Iterate over the vec rather than the hash_set
120 : : to ensure deterministic order. */
121 : 6737 : exploded_edge *inner_edge;
122 : 6737 : unsigned i;
123 : 1711419 : FOR_EACH_VEC_ELT (inner_graph.m_edges, i, inner_edge)
124 : 1697945 : if (m_eedges.contains (inner_edge))
125 : : {
126 : 168699 : const exploded_node *inner_src = inner_edge->m_src;
127 : 168699 : const exploded_node *inner_dest = inner_edge->m_dest;
128 : 168699 : trimmed_node *tsrc = *m_map_from_enode_to_tnode.get (inner_src);
129 : 168699 : trimmed_node *tdest = *m_map_from_enode_to_tnode.get (inner_dest);
130 : 168699 : trimmed_edge *tedge = new trimmed_edge (tsrc, tdest, inner_edge);
131 : 168699 : add_edge (tedge);
132 : : }
133 : : }
134 : 6737 : }
135 : :
136 : : /* Dump stats about this graph to LOGGER. */
137 : :
138 : : void
139 : 0 : trimmed_graph::log_stats (logger *logger) const
140 : : {
141 : 0 : logger->log ("#nodes: %i", m_nodes.length ());
142 : 0 : logger->log ("#edges: %i", m_edges.length ());
143 : 0 : }
144 : :
145 : : } // namespace ana
146 : :
147 : : #endif /* #if ENABLE_ANALYZER */
|
