1 /* A graph for exploring trees of feasible paths through the egraph.
2 Copyright (C) 2021-2023 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
24 #include "coretypes.h"
26 #include "pretty-print.h"
27 #include "gcc-rich-location.h"
28 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "diagnostic-event-id.h"
32 #include "diagnostic-path.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"
46 #include "basic-block.h"
48 #include "gimple-iterator.h"
51 #include "analyzer/supergraph.h"
52 #include "analyzer/program-state.h"
53 #include "analyzer/exploded-graph.h"
54 #include "analyzer/feasible-graph.h"
60 /* class base_feasible_node : public dnode<fg_traits>. */
62 /* Print an id to PP for this node suitable for use in .dot dumps. */
65 base_feasible_node::dump_dot_id (pretty_printer
*pp
) const
67 pp_printf (pp
, "fnode_%i", m_index
);
70 /* class feasible_node : public base_feasible_node. */
72 /* Implementation of dump_dot vfunc for feasible_node. */
75 feasible_node::dump_dot (graphviz_out
*gv
,
76 const dump_args_t
&) const
78 pretty_printer
*pp
= gv
->get_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
);
85 pp_printf (pp
, "FN: %i (EN: %i); len=%i", m_index
, m_inner_node
->m_index
,
90 m_inner_node
->get_point ().print (pp
, f
);
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
, true, true);
98 m_inner_node
->dump_processed_stmts (pp
);
99 m_inner_node
->dump_saved_diagnostics (pp
);
101 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/true);
103 pp_string (pp
, "\"];\n\n");
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. */
112 feasible_node::get_state_at_stmt (const gimple
*target_stmt
,
113 region_model
*out
) const
118 feasibility_state
result (m_state
);
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
;
124 const gimple
*stmt
= m_inner_node
->get_processed_stmt (stmt_idx
);
125 if (stmt
== target_stmt
)
127 *out
= result
.get_model ();
130 result
.update_for_stmt (stmt
);
133 /* TARGET_STMT not found; wrong node? */
137 /* Implementation of dump_dot vfunc for infeasible_node.
138 In particular, show the rejected constraint. */
141 infeasible_node::dump_dot (graphviz_out
*gv
,
142 const dump_args_t
&) const
144 pretty_printer
*pp
= gv
->get_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
);
151 pp_printf (pp
, "infeasible edge to EN: %i", m_inner_node
->m_index
);
154 pp_string (pp
, "rejected constraint:");
156 m_rc
->dump_to_pp (pp
);
158 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/true);
160 pp_string (pp
, "\"];\n\n");
164 /* class base_feasible_edge : public dedge<fg_traits>. */
166 /* Implementation of dump_dot vfunc for base_easible_edge. */
169 base_feasible_edge::dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
171 pretty_printer
*pp
= gv
->get_pp ();
173 m_src
->dump_dot_id (pp
);
174 pp_string (pp
, " -> ");
175 m_dest
->dump_dot_id (pp
);
177 m_inner_edge
->dump_dot_label (pp
);
180 /* class feasible_graph : public digraph <fg_traits>. */
182 /* Ctor for feasible_graph. */
184 feasible_graph::feasible_graph ()
185 : m_num_infeasible (0)
189 /* Add a feasible_node to this graph for ENODE, STATE with the
190 given PATH_LENGTH. */
193 feasible_graph::add_node (const exploded_node
*enode
,
194 const feasibility_state
&state
,
195 unsigned path_length
)
197 /* We don't attempt get_or_create here. */
198 feasible_node
*fnode
= new feasible_node (enode
, m_nodes
.length (),
200 digraph
<fg_traits
>::add_node (fnode
);
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 Takes ownership of RC. */
209 feasible_graph::add_feasibility_problem (feasible_node
*src_fnode
,
210 const exploded_edge
*eedge
,
211 rejected_constraint
*rc
)
213 infeasible_node
*dst_fnode
214 = new infeasible_node (eedge
->m_dest
, m_nodes
.length (), rc
);
215 digraph
<fg_traits
>::add_node (dst_fnode
);
216 add_edge (new infeasible_edge (src_fnode
, dst_fnode
, eedge
));
220 /* Make an exploded_path from the origin to FNODE's exploded_node,
221 following the edges in the feasible_graph. */
223 std::unique_ptr
<exploded_path
>
224 feasible_graph::make_epath (feasible_node
*fnode
) const
226 std::unique_ptr
<exploded_path
> epath (new exploded_path ());
228 /* FG is actually a tree. Built the path backwards, by walking
229 backwards from FNODE until we reach the origin. */
230 while (fnode
->get_inner_node ()->m_index
!= 0)
232 gcc_assert (fnode
->m_preds
.length () == 1);
233 feasible_edge
*pred_fedge
234 = static_cast <feasible_edge
*> (fnode
->m_preds
[0]);
235 epath
->m_edges
.safe_push (pred_fedge
->get_inner_edge ());
236 fnode
= static_cast <feasible_node
*> (pred_fedge
->m_src
);
239 /* Now reverse it. */
240 epath
->m_edges
.reverse ();
245 /* Dump the path to DST_FNODE in textual form to PP. */
248 feasible_graph::dump_feasible_path (const feasible_node
&dst_fnode
,
249 pretty_printer
*pp
) const
251 const feasible_node
*fnode
= &dst_fnode
;
253 auto_vec
<const feasible_edge
*> fpath
;
255 /* FG is actually a tree. Built the path backwards, by walking
256 backwards from FNODE until we reach the origin. */
257 while (fnode
->get_inner_node ()->m_index
!= 0)
259 gcc_assert (fnode
->m_preds
.length () == 1);
260 feasible_edge
*pred_fedge
261 = static_cast <feasible_edge
*> (fnode
->m_preds
[0]);
262 fpath
.safe_push (pred_fedge
);
263 fnode
= static_cast <const feasible_node
*> (pred_fedge
->m_src
);
266 /* Now reverse it. */
269 for (unsigned i
= 0; i
< fpath
.length (); i
++)
271 const feasible_edge
*fedge
= fpath
[i
];
272 const feasible_node
*src_fnode
273 = static_cast <const feasible_node
*> (fedge
->m_src
);
274 const feasible_node
*dest_fnode
275 = static_cast <const feasible_node
*> (fedge
->m_dest
);
277 pp_printf (pp
, "fpath[%i]: FN %i (EN %i) -> FN %i (EN %i)",
279 src_fnode
->get_index (),
280 src_fnode
->get_inner_node ()->m_index
,
281 dest_fnode
->get_index (),
282 dest_fnode
->get_inner_node ()->m_index
);
284 pp_printf (pp
, " FN %i (EN %i):",
285 dest_fnode
->get_index (),
286 dest_fnode
->get_inner_node ()->m_index
);
288 const program_point
&point
= dest_fnode
->get_inner_node ()->get_point ();
289 point
.print (pp
, format (true));
290 dest_fnode
->get_state ().dump_to_pp (pp
, true, true);
295 /* Dump the path to DST_FNODE in textual form to FILENAME. */
298 feasible_graph::dump_feasible_path (const feasible_node
&dst_fnode
,
299 const char *filename
) const
301 FILE *fp
= fopen (filename
, "w");
303 pp_format_decoder (&pp
) = default_tree_printer
;
304 pp
.buffer
->stream
= fp
;
305 dump_feasible_path (dst_fnode
, &pp
);
310 /* Dump stats about this graph to LOGGER. */
313 feasible_graph::log_stats (logger
*logger
) const
315 logger
->log ("#nodes: %i", m_nodes
.length ());
316 logger
->log ("#edges: %i", m_edges
.length ());
317 logger
->log ("#feasible nodes: %i", m_nodes
.length () - m_num_infeasible
);
318 logger
->log ("#feasible edges: %i", m_edges
.length () - m_num_infeasible
);
319 logger
->log ("#infeasible nodes/edges: %i", m_num_infeasible
);
324 #endif /* #if ENABLE_ANALYZER */