Branch data Line data Source code
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 : :
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 : : #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 : :
58 : : namespace 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 : :
64 : : void
65 : 445 : base_feasible_node::dump_dot_id (pretty_printer *pp) const
66 : : {
67 : 445 : pp_printf (pp, "fnode_%i", m_index);
68 : 445 : }
69 : :
70 : : /* class feasible_node : public base_feasible_node. */
71 : :
72 : : /* Implementation of dump_dot vfunc for feasible_node. */
73 : :
74 : : void
75 : 155 : feasible_node::dump_dot (graphviz_out *gv,
76 : : const dump_args_t &) const
77 : : {
78 : 155 : pretty_printer *pp = gv->get_pp ();
79 : :
80 : 155 : dump_dot_id (pp);
81 : 155 : pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
82 : 155 : m_inner_node->get_dot_fillcolor ());
83 : 155 : pp_write_text_to_stream (pp);
84 : :
85 : 155 : pp_printf (pp, "FN: %i (EN: %i); len=%i", m_index, m_inner_node->m_index,
86 : 155 : m_path_length);
87 : 155 : pp_newline (pp);
88 : :
89 : 155 : format f (true);
90 : 155 : m_inner_node->get_point ().print (pp, f);
91 : 155 : 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 : 155 : m_state.get_model ().dump_to_pp (pp, true, true);
96 : 155 : pp_newline (pp);
97 : :
98 : 155 : m_inner_node->dump_processed_stmts (pp);
99 : 155 : m_inner_node->dump_saved_diagnostics (pp);
100 : :
101 : 155 : pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
102 : :
103 : 155 : pp_string (pp, "\"];\n\n");
104 : 155 : pp_flush (pp);
105 : 155 : }
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 : :
111 : : bool
112 : 1359 : feasible_node::get_state_at_stmt (const gimple *target_stmt,
113 : : region_model *out) const
114 : : {
115 : 1359 : if (!target_stmt)
116 : : return false;
117 : :
118 : 1359 : feasibility_state result (m_state);
119 : :
120 : : /* Update state for the stmts that were processed in each enode. */
121 : 3013 : for (unsigned stmt_idx = 0; stmt_idx < m_inner_node->m_num_processed_stmts;
122 : : stmt_idx++)
123 : : {
124 : 2874 : const gimple *stmt = m_inner_node->get_processed_stmt (stmt_idx);
125 : 2874 : if (stmt == target_stmt)
126 : : {
127 : 1220 : *out = result.get_model ();
128 : 1220 : return true;
129 : : }
130 : 1654 : result.update_for_stmt (stmt);
131 : : }
132 : :
133 : : /* TARGET_STMT not found; wrong node? */
134 : : return false;
135 : 1359 : }
136 : :
137 : : /* Implementation of dump_dot vfunc for infeasible_node.
138 : : In particular, show the rejected constraint. */
139 : :
140 : : void
141 : 0 : infeasible_node::dump_dot (graphviz_out *gv,
142 : : const dump_args_t &) const
143 : : {
144 : 0 : pretty_printer *pp = gv->get_pp ();
145 : :
146 : 0 : dump_dot_id (pp);
147 : 0 : pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
148 : 0 : m_inner_node->get_dot_fillcolor ());
149 : 0 : pp_write_text_to_stream (pp);
150 : :
151 : 0 : pp_printf (pp, "infeasible edge to EN: %i", m_inner_node->m_index);
152 : 0 : pp_newline (pp);
153 : :
154 : 0 : pp_string (pp, "rejected constraint:");
155 : 0 : pp_newline (pp);
156 : 0 : m_rc->dump_to_pp (pp);
157 : :
158 : 0 : pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
159 : :
160 : 0 : pp_string (pp, "\"];\n\n");
161 : 0 : pp_flush (pp);
162 : 0 : }
163 : :
164 : : /* class base_feasible_edge : public dedge<fg_traits>. */
165 : :
166 : : /* Implementation of dump_dot vfunc for base_easible_edge. */
167 : :
168 : : void
169 : 145 : base_feasible_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
170 : : {
171 : 145 : pretty_printer *pp = gv->get_pp ();
172 : :
173 : 145 : m_src->dump_dot_id (pp);
174 : 145 : pp_string (pp, " -> ");
175 : 145 : m_dest->dump_dot_id (pp);
176 : :
177 : 145 : m_inner_edge->dump_dot_label (pp);
178 : 145 : }
179 : :
180 : : /* class feasible_graph : public digraph <fg_traits>. */
181 : :
182 : : /* Ctor for feasible_graph. */
183 : :
184 : 7768 : feasible_graph::feasible_graph ()
185 : 7768 : : m_num_infeasible (0)
186 : : {
187 : 7768 : }
188 : :
189 : : /* Add a feasible_node to this graph for ENODE, STATE with the
190 : : given PATH_LENGTH. */
191 : :
192 : : feasible_node *
193 : 192279 : feasible_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 : 192279 : feasible_node *fnode = new feasible_node (enode, m_nodes.length (),
199 : 376790 : state, path_length);
200 : 192279 : digraph<fg_traits>::add_node (fnode);
201 : 192279 : 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 : :
207 : : void
208 : 2366 : feasible_graph::add_feasibility_problem (feasible_node *src_fnode,
209 : : const exploded_edge *eedge,
210 : : std::unique_ptr<rejected_constraint> rc)
211 : : {
212 : 2366 : infeasible_node *dst_fnode
213 : 4732 : = new infeasible_node (eedge->m_dest, m_nodes.length (), std::move (rc));
214 : 2366 : digraph<fg_traits>::add_node (dst_fnode);
215 : 2366 : add_edge (new infeasible_edge (src_fnode, dst_fnode, eedge));
216 : 2366 : m_num_infeasible++;
217 : 2366 : }
218 : :
219 : : /* Make an exploded_path from the origin to FNODE's exploded_node,
220 : : following the edges in the feasible_graph. */
221 : :
222 : : std::unique_ptr<exploded_path>
223 : 7440 : feasible_graph::make_epath (feasible_node *fnode) const
224 : : {
225 : 7440 : 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 : 123976 : while (fnode->get_inner_node ()->m_index != 0)
230 : : {
231 : 116536 : gcc_assert (fnode->m_preds.length () == 1);
232 : 116536 : feasible_edge *pred_fedge
233 : 116536 : = static_cast <feasible_edge *> (fnode->m_preds[0]);
234 : 116536 : epath->m_edges.safe_push (pred_fedge->get_inner_edge ());
235 : 116536 : fnode = static_cast <feasible_node *> (pred_fedge->m_src);
236 : : }
237 : :
238 : : /* Now reverse it. */
239 : 7440 : epath->m_edges.reverse ();
240 : :
241 : 7440 : return epath;
242 : : }
243 : :
244 : : /* Dump the path to DST_FNODE in textual form to PP. */
245 : :
246 : : void
247 : 10 : feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
248 : : pretty_printer *pp) const
249 : : {
250 : 10 : const feasible_node *fnode = &dst_fnode;
251 : :
252 : 10 : 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 : 155 : while (fnode->get_inner_node ()->m_index != 0)
257 : : {
258 : 145 : gcc_assert (fnode->m_preds.length () == 1);
259 : 145 : feasible_edge *pred_fedge
260 : 145 : = static_cast <feasible_edge *> (fnode->m_preds[0]);
261 : 145 : fpath.safe_push (pred_fedge);
262 : 145 : fnode = static_cast <const feasible_node *> (pred_fedge->m_src);
263 : : }
264 : :
265 : : /* Now reverse it. */
266 : 10 : fpath.reverse ();
267 : :
268 : 310 : for (unsigned i = 0; i < fpath.length (); i++)
269 : : {
270 : 145 : const feasible_edge *fedge = fpath[i];
271 : 145 : const feasible_node *src_fnode
272 : : = static_cast <const feasible_node *> (fedge->m_src);
273 : 145 : const feasible_node *dest_fnode
274 : : = static_cast <const feasible_node *> (fedge->m_dest);
275 : :
276 : 145 : pp_printf (pp, "fpath[%i]: FN %i (EN %i) -> FN %i (EN %i)",
277 : : i,
278 : : src_fnode->get_index (),
279 : 145 : src_fnode->get_inner_node ()->m_index,
280 : : dest_fnode->get_index (),
281 : 145 : dest_fnode->get_inner_node ()->m_index);
282 : 145 : pp_newline (pp);
283 : 145 : pp_printf (pp, " FN %i (EN %i):",
284 : : dest_fnode->get_index (),
285 : 145 : dest_fnode->get_inner_node ()->m_index);
286 : 145 : pp_newline (pp);
287 : 145 : const program_point &point = dest_fnode->get_inner_node ()->get_point ();
288 : 145 : point.print (pp, format (true));
289 : 145 : dest_fnode->get_state ().dump_to_pp (pp, true, true);
290 : 145 : pp_newline (pp);
291 : : }
292 : 10 : }
293 : :
294 : : /* Dump the path to DST_FNODE in textual form to FILENAME. */
295 : :
296 : : void
297 : 10 : feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
298 : : const char *filename) const
299 : : {
300 : 10 : FILE *fp = fopen (filename, "w");
301 : 10 : pretty_printer pp;
302 : 10 : pp_format_decoder (&pp) = default_tree_printer;
303 : 10 : pp.buffer->stream = fp;
304 : 10 : dump_feasible_path (dst_fnode, &pp);
305 : 10 : pp_flush (&pp);
306 : 10 : fclose (fp);
307 : 10 : }
308 : :
309 : : /* Dump stats about this graph to LOGGER. */
310 : :
311 : : void
312 : 0 : feasible_graph::log_stats (logger *logger) const
313 : : {
314 : 0 : logger->log ("#nodes: %i", m_nodes.length ());
315 : 0 : logger->log ("#edges: %i", m_edges.length ());
316 : 0 : logger->log ("#feasible nodes: %i", m_nodes.length () - m_num_infeasible);
317 : 0 : logger->log ("#feasible edges: %i", m_edges.length () - m_num_infeasible);
318 : 0 : logger->log ("#infeasible nodes/edges: %i", m_num_infeasible);
319 : 0 : }
320 : :
321 : : } // namespace ana
322 : :
323 : : #endif /* #if ENABLE_ANALYZER */
|
