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>.
5 This file is part of GCC.
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)
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.
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/>. */
22 #define INCLUDE_MEMORY
23 #define INCLUDE_VECTOR
25 #include "coretypes.h"
27 #include "pretty-print.h"
28 #include "gcc-rich-location.h"
29 #include "gimple-pretty-print.h"
31 #include "diagnostic-core.h"
32 #include "diagnostic-event-id.h"
33 #include "diagnostic-path.h"
35 #include "ordered-hash-map.h"
36 #include "analyzer/analyzer.h"
37 #include "analyzer/analyzer-logging.h"
38 #include "analyzer/sm.h"
39 #include "analyzer/pending-diagnostic.h"
40 #include "analyzer/diagnostic-manager.h"
41 #include "analyzer/call-string.h"
42 #include "analyzer/program-point.h"
43 #include "analyzer/store.h"
44 #include "analyzer/region-model.h"
45 #include "analyzer/constraint-manager.h"
46 #include "analyzer/supergraph.h"
47 #include "analyzer/program-state.h"
48 #include "analyzer/exploded-graph.h"
49 #include "analyzer/trimmed-graph.h"
55 /* class trimmed_node : public dnode<tg_traits>. */
57 /* Implementation of dump_dot vfunc, delegating to the inner node. */
60 trimmed_node::dump_dot (graphviz_out
*gv
,
61 const dump_args_t
&args
) const
63 m_inner_node
->dump_dot (gv
, args
.m_inner_args
);
66 /* class trimmed_edge : public dedge<tg_traits>. */
68 /* trimmed_edge's ctor. */
70 trimmed_edge::trimmed_edge (trimmed_node
*src
, trimmed_node
*dest
,
71 const exploded_edge
*inner_edge
)
72 : dedge
<tg_traits
> (src
, dest
), m_inner_edge (inner_edge
)
76 /* Implementation of dump_dot vfunc, delegating to the inner edge. */
79 trimmed_edge::dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const
81 m_inner_edge
->dump_dot (gv
, args
.m_inner_args
);
84 /* class trimmed_graph : public digraph <tg_traits>. */
86 /* Ctor for trimmed_graph: construct a graph equivalent to trimming
87 INNER_GRAPH to all nodes that can reach INNER_DST_NODE. */
89 trimmed_graph::trimmed_graph (const exploded_graph
&inner_graph
,
90 const exploded_node
*inner_dst_node
)
91 : m_enodes (), m_eedges ()
93 /* Determine what subset of nodes and edges to include in the
95 Walk backwards from INNER_DST_NODE, finding nodes that reach it,
96 iteratively building the set of nodes and edges. */
97 auto_vec
<const exploded_node
*> worklist
;
98 worklist
.safe_push (inner_dst_node
);
99 m_enodes
.add (inner_dst_node
);
100 while (worklist
.length () > 0)
102 const exploded_node
*inner_node
= worklist
.pop ();
103 exploded_edge
*inner_pred
;
105 FOR_EACH_VEC_ELT (inner_node
->m_preds
, i
, inner_pred
)
107 if (!m_enodes
.contains (inner_pred
->m_src
))
109 worklist
.safe_push (inner_pred
->m_src
);
110 m_enodes
.add (inner_pred
->m_src
);
112 m_eedges
.add (inner_pred
);
116 /* Create trimmed nodes for all enodes in the set. */
118 /* Iterate over the vec rather than the hash_set
119 to ensure deterministic order. */
120 exploded_node
*inner_node
;
122 FOR_EACH_VEC_ELT (inner_graph
.m_nodes
, i
, inner_node
)
123 if (m_enodes
.contains (inner_node
))
125 trimmed_node
*tnode
= new trimmed_node (inner_node
);
127 m_map_from_enode_to_tnode
.put (inner_node
, tnode
);
131 /* Create trimmed edges for all edges in the set. */
133 /* Iterate over the vec rather than the hash_set
134 to ensure deterministic order. */
135 exploded_edge
*inner_edge
;
137 FOR_EACH_VEC_ELT (inner_graph
.m_edges
, i
, inner_edge
)
138 if (m_eedges
.contains (inner_edge
))
140 const exploded_node
*inner_src
= inner_edge
->m_src
;
141 const exploded_node
*inner_dest
= inner_edge
->m_dest
;
142 trimmed_node
*tsrc
= *m_map_from_enode_to_tnode
.get (inner_src
);
143 trimmed_node
*tdest
= *m_map_from_enode_to_tnode
.get (inner_dest
);
144 trimmed_edge
*tedge
= new trimmed_edge (tsrc
, tdest
, inner_edge
);
150 /* Dump stats about this graph to LOGGER. */
153 trimmed_graph::log_stats (logger
*logger
) const
155 logger
->log ("#nodes: %i", m_nodes
.length ());
156 logger
->log ("#edges: %i", m_edges
.length ());
161 #endif /* #if ENABLE_ANALYZER */