1/* A graph for exploring trees of feasible paths through the egraph.
2 Copyright (C) 2021-2024 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#define INCLUDE_MEMORY
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 "cfg.h"
46#include "basic-block.h"
47#include "gimple.h"
48#include "gimple-iterator.h"
49#include "cgraph.h"
50#include "digraph.h"
51#include "analyzer/supergraph.h"
52#include "analyzer/program-state.h"
53#include "analyzer/exploded-graph.h"
54#include "analyzer/feasible-graph.h"
55
56#if ENABLE_ANALYZER
57
58namespace ana {
59
60/* class base_feasible_node : public dnode<fg_traits>. */
61
62/* Print an id to PP for this node suitable for use in .dot dumps. */
63
64void
65base_feasible_node::dump_dot_id (pretty_printer *pp) const
66{
67 pp_printf (pp, "fnode_%i", m_index);
68}
69
70/* class feasible_node : public base_feasible_node. */
71
72/* Implementation of dump_dot vfunc for feasible_node. */
73
74void
75feasible_node::dump_dot (graphviz_out *gv,
76 const dump_args_t &) const
77{
78 pretty_printer *pp = gv->get_pp ();
79
80 dump_dot_id (pp);
81 pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
82 m_inner_node->get_dot_fillcolor ());
83 pp_write_text_to_stream (pp);
84
85 pp_printf (pp, "FN: %i (EN: %i); len=%i", m_index, m_inner_node->m_index,
86 m_path_length);
87 pp_newline (pp);
88
89 format f (true);
90 m_inner_node->get_point ().print (pp, f);
91 pp_newline (pp);
92
93 /* Show the model at this point along expansion of the feasible path,
94 rather than the model within the enode. */
95 m_state.get_model ().dump_to_pp (pp, simple: true, multiline: true);
96 pp_newline (pp);
97
98 m_inner_node->dump_processed_stmts (pp);
99 m_inner_node->dump_saved_diagnostics (pp);
100
101 pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
102
103 pp_string (pp, "\"];\n\n");
104 pp_flush (pp);
105}
106
107/* Attempt to get the region_model for this node's state at TARGET_STMT.
108 Return true and write to *OUT if found.
109 Return false if there's a problem. */
110
111bool
112feasible_node::get_state_at_stmt (const gimple *target_stmt,
113 region_model *out) const
114{
115 if (!target_stmt)
116 return false;
117
118 feasibility_state result (m_state);
119
120 /* Update state for the stmts that were processed in each enode. */
121 for (unsigned stmt_idx = 0; stmt_idx < m_inner_node->m_num_processed_stmts;
122 stmt_idx++)
123 {
124 const gimple *stmt = m_inner_node->get_processed_stmt (idx: stmt_idx);
125 if (stmt == target_stmt)
126 {
127 *out = result.get_model ();
128 return true;
129 }
130 result.update_for_stmt (stmt);
131 }
132
133 /* TARGET_STMT not found; wrong node? */
134 return false;
135}
136
137/* Implementation of dump_dot vfunc for infeasible_node.
138 In particular, show the rejected constraint. */
139
140void
141infeasible_node::dump_dot (graphviz_out *gv,
142 const dump_args_t &) const
143{
144 pretty_printer *pp = gv->get_pp ();
145
146 dump_dot_id (pp);
147 pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
148 m_inner_node->get_dot_fillcolor ());
149 pp_write_text_to_stream (pp);
150
151 pp_printf (pp, "infeasible edge to EN: %i", m_inner_node->m_index);
152 pp_newline (pp);
153
154 pp_string (pp, "rejected constraint:");
155 pp_newline (pp);
156 m_rc->dump_to_pp (pp);
157
158 pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
159
160 pp_string (pp, "\"];\n\n");
161 pp_flush (pp);
162}
163
164/* class base_feasible_edge : public dedge<fg_traits>. */
165
166/* Implementation of dump_dot vfunc for base_easible_edge. */
167
168void
169base_feasible_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
170{
171 pretty_printer *pp = gv->get_pp ();
172
173 m_src->dump_dot_id (pp);
174 pp_string (pp, " -> ");
175 m_dest->dump_dot_id (pp);
176
177 m_inner_edge->dump_dot_label (pp);
178}
179
180/* class feasible_graph : public digraph <fg_traits>. */
181
182/* Ctor for feasible_graph. */
183
184feasible_graph::feasible_graph ()
185: m_num_infeasible (0)
186{
187}
188
189/* Add a feasible_node to this graph for ENODE, STATE with the
190 given PATH_LENGTH. */
191
192feasible_node *
193feasible_graph::add_node (const exploded_node *enode,
194 const feasibility_state &state,
195 unsigned path_length)
196{
197 /* We don't attempt get_or_create here. */
198 feasible_node *fnode = new feasible_node (enode, m_nodes.length (),
199 state, path_length);
200 digraph<fg_traits>::add_node (node: fnode);
201 return fnode;
202}
203
204/* Add an infeasible_node to this graph and an infeasible_edge connecting
205 to it from SRC_FNODE, capturing a failure of RC along EEDGE. */
206
207void
208feasible_graph::add_feasibility_problem (feasible_node *src_fnode,
209 const exploded_edge *eedge,
210 std::unique_ptr<rejected_constraint> rc)
211{
212 infeasible_node *dst_fnode
213 = new infeasible_node (eedge->m_dest, m_nodes.length (), std::move (rc));
214 digraph<fg_traits>::add_node (node: dst_fnode);
215 add_edge (edge: new infeasible_edge (src_fnode, dst_fnode, eedge));
216 m_num_infeasible++;
217}
218
219/* Make an exploded_path from the origin to FNODE's exploded_node,
220 following the edges in the feasible_graph. */
221
222std::unique_ptr<exploded_path>
223feasible_graph::make_epath (feasible_node *fnode) const
224{
225 std::unique_ptr<exploded_path> epath (new exploded_path ());
226
227 /* FG is actually a tree. Built the path backwards, by walking
228 backwards from FNODE until we reach the origin. */
229 while (fnode->get_inner_node ()->m_index != 0)
230 {
231 gcc_assert (fnode->m_preds.length () == 1);
232 feasible_edge *pred_fedge
233 = static_cast <feasible_edge *> (fnode->m_preds[0]);
234 epath->m_edges.safe_push (obj: pred_fedge->get_inner_edge ());
235 fnode = static_cast <feasible_node *> (pred_fedge->m_src);
236 }
237
238 /* Now reverse it. */
239 epath->m_edges.reverse ();
240
241 return epath;
242}
243
244/* Dump the path to DST_FNODE in textual form to PP. */
245
246void
247feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
248 pretty_printer *pp) const
249{
250 const feasible_node *fnode = &dst_fnode;
251
252 auto_vec<const feasible_edge *> fpath;
253
254 /* FG is actually a tree. Built the path backwards, by walking
255 backwards from FNODE until we reach the origin. */
256 while (fnode->get_inner_node ()->m_index != 0)
257 {
258 gcc_assert (fnode->m_preds.length () == 1);
259 feasible_edge *pred_fedge
260 = static_cast <feasible_edge *> (fnode->m_preds[0]);
261 fpath.safe_push (obj: pred_fedge);
262 fnode = static_cast <const feasible_node *> (pred_fedge->m_src);
263 }
264
265 /* Now reverse it. */
266 fpath.reverse ();
267
268 for (unsigned i = 0; i < fpath.length (); i++)
269 {
270 const feasible_edge *fedge = fpath[i];
271 const feasible_node *src_fnode
272 = static_cast <const feasible_node *> (fedge->m_src);
273 const feasible_node *dest_fnode
274 = static_cast <const feasible_node *> (fedge->m_dest);
275
276 pp_printf (pp, "fpath[%i]: FN %i (EN %i) -> FN %i (EN %i)",
277 i,
278 src_fnode->get_index (),
279 src_fnode->get_inner_node ()->m_index,
280 dest_fnode->get_index (),
281 dest_fnode->get_inner_node ()->m_index);
282 pp_newline (pp);
283 pp_printf (pp, " FN %i (EN %i):",
284 dest_fnode->get_index (),
285 dest_fnode->get_inner_node ()->m_index);
286 pp_newline (pp);
287 const program_point &point = dest_fnode->get_inner_node ()->get_point ();
288 point.print (pp, f: format (true));
289 dest_fnode->get_state ().dump_to_pp (pp, simple: true, multiline: true);
290 pp_newline (pp);
291 }
292}
293
294/* Dump the path to DST_FNODE in textual form to FILENAME. */
295
296void
297feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
298 const char *filename) const
299{
300 FILE *fp = fopen (filename: filename, modes: "w");
301 pretty_printer pp;
302 pp_format_decoder (&pp) = default_tree_printer;
303 pp.buffer->stream = fp;
304 dump_feasible_path (dst_fnode, pp: &pp);
305 pp_flush (&pp);
306 fclose (stream: fp);
307}
308
309/* Dump stats about this graph to LOGGER. */
310
311void
312feasible_graph::log_stats (logger *logger) const
313{
314 logger->log (fmt: "#nodes: %i", m_nodes.length ());
315 logger->log (fmt: "#edges: %i", m_edges.length ());
316 logger->log (fmt: "#feasible nodes: %i", m_nodes.length () - m_num_infeasible);
317 logger->log (fmt: "#feasible edges: %i", m_edges.length () - m_num_infeasible);
318 logger->log (fmt: "#infeasible nodes/edges: %i", m_num_infeasible);
319}
320
321} // namespace ana
322
323#endif /* #if ENABLE_ANALYZER */
324

source code of gcc/analyzer/feasible-graph.cc