1 /* A graph for exploring trees of feasible paths through the egraph.
2 Copyright (C) 2021-2022 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 #include "system.h"
23 #include "coretypes.h"
24 #include "tree.h"
25 #include "pretty-print.h"
26 #include "gcc-rich-location.h"
27 #include "gimple-pretty-print.h"
28 #include "function.h"
29 #include "diagnostic-core.h"
30 #include "diagnostic-event-id.h"
31 #include "diagnostic-path.h"
32 #include "alloc-pool.h"
33 #include "fibonacci_heap.h"
34 #include "shortest-paths.h"
35 #include "sbitmap.h"
36 #include "bitmap.h"
37 #include "tristate.h"
38 #include "selftest.h"
39 #include "ordered-hash-map.h"
40 #include "json.h"
41 #include "analyzer/analyzer.h"
42 #include "analyzer/analyzer-logging.h"
43 #include "analyzer/sm.h"
44 #include "analyzer/pending-diagnostic.h"
45 #include "analyzer/diagnostic-manager.h"
46 #include "analyzer/call-string.h"
47 #include "analyzer/program-point.h"
48 #include "analyzer/store.h"
49 #include "analyzer/region-model.h"
50 #include "analyzer/constraint-manager.h"
51 #include "cfg.h"
52 #include "basic-block.h"
53 #include "gimple.h"
54 #include "gimple-iterator.h"
55 #include "cgraph.h"
56 #include "digraph.h"
57 #include "analyzer/supergraph.h"
58 #include "analyzer/program-state.h"
59 #include "analyzer/exploded-graph.h"
60 #include "analyzer/feasible-graph.h"
61
62 #if ENABLE_ANALYZER
63
64 namespace ana {
65
66 /* class base_feasible_node : public dnode<fg_traits>. */
67
68 /* Print an id to PP for this node suitable for use in .dot dumps. */
69
70 void
dump_dot_id(pretty_printer * pp) const71 base_feasible_node::dump_dot_id (pretty_printer *pp) const
72 {
73 pp_printf (pp, "fnode_%i", m_index);
74 }
75
76 /* class feasible_node : public base_feasible_node. */
77
78 /* Implementation of dump_dot vfunc for feasible_node. */
79
80 void
dump_dot(graphviz_out * gv,const dump_args_t &) const81 feasible_node::dump_dot (graphviz_out *gv,
82 const dump_args_t &) const
83 {
84 pretty_printer *pp = gv->get_pp ();
85
86 dump_dot_id (pp);
87 pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
88 m_inner_node->get_dot_fillcolor ());
89 pp_write_text_to_stream (pp);
90
91 pp_printf (pp, "FN: %i (EN: %i); len=%i", m_index, m_inner_node->m_index,
92 m_path_length);
93 pp_newline (pp);
94
95 format f (true);
96 m_inner_node->get_point ().print (pp, f);
97 pp_newline (pp);
98
99 /* Show the model at this point along expansion of the feasible path,
100 rather than the model within the enode. */
101 m_state.get_model ().dump_to_pp (pp, true, true);
102 pp_newline (pp);
103
104 m_inner_node->dump_processed_stmts (pp);
105 m_inner_node->dump_saved_diagnostics (pp);
106
107 pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
108
109 pp_string (pp, "\"];\n\n");
110 pp_flush (pp);
111 }
112
113 /* Implementation of dump_dot vfunc for infeasible_node.
114 In particular, show the rejected constraint. */
115
116 void
dump_dot(graphviz_out * gv,const dump_args_t &) const117 infeasible_node::dump_dot (graphviz_out *gv,
118 const dump_args_t &) const
119 {
120 pretty_printer *pp = gv->get_pp ();
121
122 dump_dot_id (pp);
123 pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
124 m_inner_node->get_dot_fillcolor ());
125 pp_write_text_to_stream (pp);
126
127 pp_printf (pp, "infeasible edge to EN: %i", m_inner_node->m_index);
128 pp_newline (pp);
129
130 pp_string (pp, "rejected constraint:");
131 pp_newline (pp);
132 m_rc->dump_to_pp (pp);
133
134 pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
135
136 pp_string (pp, "\"];\n\n");
137 pp_flush (pp);
138 }
139
140 /* class base_feasible_edge : public dedge<fg_traits>. */
141
142 /* Implementation of dump_dot vfunc for base_easible_edge. */
143
144 void
dump_dot(graphviz_out * gv,const dump_args_t &) const145 base_feasible_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
146 {
147 pretty_printer *pp = gv->get_pp ();
148
149 m_src->dump_dot_id (pp);
150 pp_string (pp, " -> ");
151 m_dest->dump_dot_id (pp);
152
153 m_inner_edge->dump_dot_label (pp);
154 }
155
156 /* class feasible_graph : public digraph <fg_traits>. */
157
158 /* Ctor for feasible_graph. */
159
feasible_graph()160 feasible_graph::feasible_graph ()
161 : m_num_infeasible (0)
162 {
163 }
164
165 /* Add a feasible_node to this graph for ENODE, STATE with the
166 given PATH_LENGTH. */
167
168 feasible_node *
add_node(const exploded_node * enode,const feasibility_state & state,unsigned path_length)169 feasible_graph::add_node (const exploded_node *enode,
170 const feasibility_state &state,
171 unsigned path_length)
172 {
173 /* We don't attempt get_or_create here. */
174 feasible_node *fnode = new feasible_node (enode, m_nodes.length (),
175 state, path_length);
176 digraph<fg_traits>::add_node (fnode);
177 return fnode;
178 }
179
180 /* Add an infeasible_node to this graph and an infeasible_edge connecting
181 to it from SRC_FNODE, capturing a failure of RC along EEDGE.
182 Takes ownership of RC. */
183
184 void
add_feasibility_problem(feasible_node * src_fnode,const exploded_edge * eedge,rejected_constraint * rc)185 feasible_graph::add_feasibility_problem (feasible_node *src_fnode,
186 const exploded_edge *eedge,
187 rejected_constraint *rc)
188 {
189 infeasible_node *dst_fnode
190 = new infeasible_node (eedge->m_dest, m_nodes.length (), rc);
191 digraph<fg_traits>::add_node (dst_fnode);
192 add_edge (new infeasible_edge (src_fnode, dst_fnode, eedge));
193 m_num_infeasible++;
194 }
195
196 /* Make an exploded_path from the origin to FNODE's exploded_node,
197 following the edges in the feasible_graph. */
198
199 exploded_path *
make_epath(feasible_node * fnode) const200 feasible_graph::make_epath (feasible_node *fnode) const
201 {
202 exploded_path *epath = new exploded_path ();
203
204 /* FG is actually a tree. Built the path backwards, by walking
205 backwards from FNODE until we reach the origin. */
206 while (fnode->get_inner_node ()->m_index != 0)
207 {
208 gcc_assert (fnode->m_preds.length () == 1);
209 feasible_edge *pred_fedge
210 = static_cast <feasible_edge *> (fnode->m_preds[0]);
211 epath->m_edges.safe_push (pred_fedge->get_inner_edge ());
212 fnode = static_cast <feasible_node *> (pred_fedge->m_src);
213 }
214
215 /* Now reverse it. */
216 epath->m_edges.reverse ();
217
218 return epath;
219 }
220
221 /* Dump the path to DST_FNODE in textual form to PP. */
222
223 void
dump_feasible_path(const feasible_node & dst_fnode,pretty_printer * pp) const224 feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
225 pretty_printer *pp) const
226 {
227 const feasible_node *fnode = &dst_fnode;
228
229 auto_vec<const feasible_edge *> fpath;
230
231 /* FG is actually a tree. Built the path backwards, by walking
232 backwards from FNODE until we reach the origin. */
233 while (fnode->get_inner_node ()->m_index != 0)
234 {
235 gcc_assert (fnode->m_preds.length () == 1);
236 feasible_edge *pred_fedge
237 = static_cast <feasible_edge *> (fnode->m_preds[0]);
238 fpath.safe_push (pred_fedge);
239 fnode = static_cast <const feasible_node *> (pred_fedge->m_src);
240 }
241
242 /* Now reverse it. */
243 fpath.reverse ();
244
245 for (unsigned i = 0; i < fpath.length (); i++)
246 {
247 const feasible_edge *fedge = fpath[i];
248 const feasible_node *src_fnode
249 = static_cast <const feasible_node *> (fedge->m_src);
250 const feasible_node *dest_fnode
251 = static_cast <const feasible_node *> (fedge->m_dest);
252
253 pp_printf (pp, "fpath[%i]: FN %i (EN %i) -> FN %i (EN %i)",
254 i,
255 src_fnode->get_index (),
256 src_fnode->get_inner_node ()->m_index,
257 dest_fnode->get_index (),
258 dest_fnode->get_inner_node ()->m_index);
259 pp_newline (pp);
260 pp_printf (pp, " FN %i (EN %i):",
261 dest_fnode->get_index (),
262 dest_fnode->get_inner_node ()->m_index);
263 pp_newline (pp);
264 const program_point &point = dest_fnode->get_inner_node ()->get_point ();
265 point.print (pp, format (true));
266 dest_fnode->get_state ().dump_to_pp (pp, true, true);
267 pp_newline (pp);
268 }
269 }
270
271 /* Dump the path to DST_FNODE in textual form to FILENAME. */
272
273 void
dump_feasible_path(const feasible_node & dst_fnode,const char * filename) const274 feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
275 const char *filename) const
276 {
277 FILE *fp = fopen (filename, "w");
278 pretty_printer pp;
279 pp_format_decoder (&pp) = default_tree_printer;
280 pp.buffer->stream = fp;
281 dump_feasible_path (dst_fnode, &pp);
282 pp_flush (&pp);
283 fclose (fp);
284 }
285
286 /* Dump stats about this graph to LOGGER. */
287
288 void
log_stats(logger * logger) const289 feasible_graph::log_stats (logger *logger) const
290 {
291 logger->log ("#nodes: %i", m_nodes.length ());
292 logger->log ("#edges: %i", m_edges.length ());
293 logger->log ("#feasible nodes: %i", m_nodes.length () - m_num_infeasible);
294 logger->log ("#feasible edges: %i", m_edges.length () - m_num_infeasible);
295 logger->log ("#infeasible nodes/edges: %i", m_num_infeasible);
296 }
297
298 } // namespace ana
299
300 #endif /* #if ENABLE_ANALYZER */
301