Require target lra in gcc.dg/pr108095.c
[official-gcc.git] / gcc / analyzer / feasible-graph.cc
blobd5e94b6152dd2e7aefcae5c005dd5a07849d7c59
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)
10 any later version.
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/>. */
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"
56 #if ENABLE_ANALYZER
58 namespace ana {
60 /* class base_feasible_node : public dnode<fg_traits>. */
62 /* Print an id to PP for this node suitable for use in .dot dumps. */
64 void
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. */
74 void
75 feasible_node::dump_dot (graphviz_out *gv,
76 const dump_args_t &) const
78 pretty_printer *pp = gv->get_pp ();
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);
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);
89 format f (true);
90 m_inner_node->get_point ().print (pp, f);
91 pp_newline (pp);
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);
96 pp_newline (pp);
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");
104 pp_flush (pp);
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. */
111 bool
112 feasible_node::get_state_at_stmt (const gimple *target_stmt,
113 region_model *out) const
115 if (!target_stmt)
116 return false;
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;
122 stmt_idx++)
124 const gimple *stmt = m_inner_node->get_processed_stmt (stmt_idx);
125 if (stmt == target_stmt)
127 *out = result.get_model ();
128 return true;
130 result.update_for_stmt (stmt);
133 /* TARGET_STMT not found; wrong node? */
134 return false;
137 /* Implementation of dump_dot vfunc for infeasible_node.
138 In particular, show the rejected constraint. */
140 void
141 infeasible_node::dump_dot (graphviz_out *gv,
142 const dump_args_t &) const
144 pretty_printer *pp = gv->get_pp ();
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);
151 pp_printf (pp, "infeasible edge to EN: %i", m_inner_node->m_index);
152 pp_newline (pp);
154 pp_string (pp, "rejected constraint:");
155 pp_newline (pp);
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");
161 pp_flush (pp);
164 /* class base_feasible_edge : public dedge<fg_traits>. */
166 /* Implementation of dump_dot vfunc for base_easible_edge. */
168 void
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. */
192 feasible_node *
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 (),
199 state, path_length);
200 digraph<fg_traits>::add_node (fnode);
201 return 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. */
207 void
208 feasible_graph::add_feasibility_problem (feasible_node *src_fnode,
209 const exploded_edge *eedge,
210 std::unique_ptr<rejected_constraint> rc)
212 infeasible_node *dst_fnode
213 = new infeasible_node (eedge->m_dest, m_nodes.length (), std::move (rc));
214 digraph<fg_traits>::add_node (dst_fnode);
215 add_edge (new infeasible_edge (src_fnode, dst_fnode, eedge));
216 m_num_infeasible++;
219 /* Make an exploded_path from the origin to FNODE's exploded_node,
220 following the edges in the feasible_graph. */
222 std::unique_ptr<exploded_path>
223 feasible_graph::make_epath (feasible_node *fnode) const
225 std::unique_ptr<exploded_path> epath (new exploded_path ());
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)
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 (pred_fedge->get_inner_edge ());
235 fnode = static_cast <feasible_node *> (pred_fedge->m_src);
238 /* Now reverse it. */
239 epath->m_edges.reverse ();
241 return epath;
244 /* Dump the path to DST_FNODE in textual form to PP. */
246 void
247 feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
248 pretty_printer *pp) const
250 const feasible_node *fnode = &dst_fnode;
252 auto_vec<const feasible_edge *> fpath;
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)
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 (pred_fedge);
262 fnode = static_cast <const feasible_node *> (pred_fedge->m_src);
265 /* Now reverse it. */
266 fpath.reverse ();
268 for (unsigned i = 0; i < fpath.length (); i++)
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);
276 pp_printf (pp, "fpath[%i]: FN %i (EN %i) -> FN %i (EN %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, format (true));
289 dest_fnode->get_state ().dump_to_pp (pp, true, true);
290 pp_newline (pp);
294 /* Dump the path to DST_FNODE in textual form to FILENAME. */
296 void
297 feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
298 const char *filename) const
300 FILE *fp = fopen (filename, "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);
305 pp_flush (&pp);
306 fclose (fp);
309 /* Dump stats about this graph to LOGGER. */
311 void
312 feasible_graph::log_stats (logger *logger) const
314 logger->log ("#nodes: %i", m_nodes.length ());
315 logger->log ("#edges: %i", m_edges.length ());
316 logger->log ("#feasible nodes: %i", m_nodes.length () - m_num_infeasible);
317 logger->log ("#feasible edges: %i", m_edges.length () - m_num_infeasible);
318 logger->log ("#infeasible nodes/edges: %i", m_num_infeasible);
321 } // namespace ana
323 #endif /* #if ENABLE_ANALYZER */