Line data Source code
1 : /* Trimming an exploded graph to a subset of nodes and edges.
2 : Copyright (C) 2021-2026 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 74 : trimmed_node::dump_dot (graphviz_out *gv,
47 : const dump_args_t &args) const
48 : {
49 74 : m_inner_node->dump_dot (gv, args.m_inner_args);
50 74 : }
51 :
52 : /* class trimmed_edge : public dedge<tg_traits>. */
53 :
54 : /* trimmed_edge's ctor. */
55 :
56 156210 : trimmed_edge::trimmed_edge (trimmed_node *src, trimmed_node *dest,
57 156210 : const exploded_edge *inner_edge)
58 156210 : : dedge<tg_traits> (src, dest), m_inner_edge (inner_edge)
59 : {
60 156210 : }
61 :
62 : /* Implementation of dump_dot vfunc, delegating to the inner edge. */
63 :
64 : void
65 70 : trimmed_edge::dump_dot (graphviz_out *gv, const dump_args_t &args) const
66 : {
67 70 : m_inner_edge->dump_dot (gv, args.m_inner_args);
68 70 : }
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 6371 : trimmed_graph::trimmed_graph (const exploded_graph &inner_graph,
76 6371 : const exploded_node *inner_dst_node)
77 6371 : : 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 6371 : auto_vec <const exploded_node *> worklist;
84 6371 : worklist.safe_push (inner_dst_node);
85 6371 : m_enodes.add (inner_dst_node);
86 332017 : while (worklist.length () > 0)
87 : {
88 156452 : const exploded_node *inner_node = worklist.pop ();
89 156452 : exploded_edge *inner_pred;
90 156452 : unsigned i;
91 462743 : FOR_EACH_VEC_ELT (inner_node->m_preds, i, inner_pred)
92 : {
93 156210 : if (!m_enodes.contains (inner_pred->m_src))
94 : {
95 150081 : worklist.safe_push (inner_pred->m_src);
96 150081 : m_enodes.add (inner_pred->m_src);
97 : }
98 156210 : 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 1776059 : FOR_EACH_VEC_ELT (inner_graph.m_nodes, i, inner_node)
109 1769688 : if (m_enodes.contains (inner_node))
110 : {
111 156452 : trimmed_node *tnode = new trimmed_node (inner_node);
112 156452 : add_node (tnode);
113 156452 : m_map_from_enode_to_tnode.put (inner_node, tnode);
114 : }
115 : }
116 :
117 : /* Create trimmed edges for all edges in the set. */
118 6371 : {
119 : /* Iterate over the vec rather than the hash_set
120 : to ensure deterministic order. */
121 6371 : exploded_edge *inner_edge;
122 6371 : unsigned i;
123 1843323 : FOR_EACH_VEC_ELT (inner_graph.m_edges, i, inner_edge)
124 1830581 : if (m_eedges.contains (inner_edge))
125 : {
126 156210 : const exploded_node *inner_src = inner_edge->m_src;
127 156210 : const exploded_node *inner_dest = inner_edge->m_dest;
128 156210 : trimmed_node *tsrc = *m_map_from_enode_to_tnode.get (inner_src);
129 156210 : trimmed_node *tdest = *m_map_from_enode_to_tnode.get (inner_dest);
130 156210 : trimmed_edge *tedge = new trimmed_edge (tsrc, tdest, inner_edge);
131 156210 : add_edge (tedge);
132 : }
133 : }
134 6371 : }
135 :
136 : /* Dump stats about this graph to LOGGER. */
137 :
138 : void
139 2 : trimmed_graph::log_stats (logger *logger) const
140 : {
141 4 : logger->log ("#nodes: %i", m_nodes.length ());
142 4 : logger->log ("#edges: %i", m_edges.length ());
143 2 : }
144 :
145 : } // namespace ana
146 :
147 : #endif /* #if ENABLE_ANALYZER */
|
