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