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