Line data Source code
1 : /* Paths within an exploded_graph.
2 : Copyright (C) 2019-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 "analyzer/exploded-path.h"
24 :
25 : #if ENABLE_ANALYZER
26 :
27 : namespace ana {
28 :
29 : // struct diagnostic_state
30 :
31 : void
32 21 : diagnostic_state::dump_to_pp (pretty_printer *pp) const
33 : {
34 21 : pp_printf (pp, "%s: {", m_debug_desc.c_str ());
35 21 : if (m_region_holding_value)
36 : {
37 7 : pp_string (pp, "region holding value: ");
38 7 : m_region_holding_value->dump_to_pp (pp, false);
39 : }
40 21 : pp_string (pp, "}");
41 21 : }
42 :
43 : void
44 0 : diagnostic_state::dump () const
45 : {
46 0 : tree_dump_pretty_printer pp (stderr);
47 0 : dump_to_pp (&pp);
48 0 : pp_newline (&pp);
49 0 : }
50 :
51 : /* class exploded_path. */
52 :
53 : /* Look for the last use of SEARCH_STMT within this path.
54 : If found write the edge's index to *OUT_IDX and return true, otherwise
55 : return false. */
56 :
57 : bool
58 696 : exploded_path::find_stmt_backwards (const gimple *search_stmt,
59 : int *out_idx) const
60 : {
61 11227 : for (int i = m_elements.size () - 1; i >= 0; --i)
62 : {
63 11162 : const element_t *element = &m_elements[i];
64 11162 : const exploded_edge *eedge = element->m_eedge;
65 11162 : if (search_stmt->code == GIMPLE_PHI)
66 : {
67 : /* Each phis_for_edge_op instance handles multiple phi stmts
68 : at once, so we have to special-case the search for a phi stmt. */
69 632 : if (auto op = eedge->maybe_get_op ())
70 446 : if (auto phis_op = op->dyn_cast_phis_for_edge_op ())
71 66 : if (phis_op->defines_ssa_name_p (gimple_phi_result (search_stmt)))
72 : {
73 34 : *out_idx = i;
74 34 : return true;
75 : }
76 : }
77 : else
78 : {
79 : /* Non-phi stmt. */
80 10530 : if (const gimple *stmt = eedge->maybe_get_stmt ())
81 7588 : if (stmt == search_stmt)
82 : {
83 597 : *out_idx = i;
84 597 : return true;
85 : }
86 : }
87 : }
88 : return false;
89 : }
90 :
91 : /* Get the final exploded_node in this path, which must be non-empty. */
92 :
93 : exploded_node *
94 13158 : exploded_path::get_final_enode () const
95 : {
96 13158 : gcc_assert (m_elements.size () > 0);
97 13158 : return m_elements.back ().m_eedge->m_dest;
98 : }
99 :
100 : /* Check state along this path, returning true if it is feasible.
101 : If OUT is non-NULL, and the path is infeasible, write a new
102 : feasibility_problem to *OUT. */
103 :
104 : bool
105 4 : exploded_path::feasible_p (logger *logger,
106 : std::unique_ptr<feasibility_problem> *out,
107 : engine *eng, const exploded_graph *eg) const
108 : {
109 4 : LOG_SCOPE (logger);
110 :
111 4 : feasibility_state state (eng->get_model_manager (),
112 4 : eg->get_supergraph ());
113 :
114 : /* Traverse the path, updating this state. */
115 33 : for (unsigned edge_idx = 0; edge_idx < m_elements.size (); ++edge_idx)
116 : {
117 33 : const exploded_edge *eedge = m_elements[edge_idx].m_eedge;
118 33 : if (logger)
119 0 : logger->log ("considering edge %i: EN:%i -> EN:%i",
120 : edge_idx,
121 0 : eedge->m_src->m_index,
122 0 : eedge->m_dest->m_index);
123 :
124 33 : std::unique_ptr <rejected_constraint> rc;
125 33 : if (!state.maybe_update_for_edge (logger, eedge, nullptr, &rc))
126 : {
127 4 : gcc_assert (rc);
128 4 : if (out)
129 8 : *out = std::make_unique<feasibility_problem> (edge_idx, *eedge,
130 4 : std::move (rc));
131 4 : return false;
132 : }
133 :
134 29 : if (logger)
135 : {
136 0 : logger->log ("state after edge %i: EN:%i -> EN:%i",
137 : edge_idx,
138 0 : eedge->m_src->m_index,
139 0 : eedge->m_dest->m_index);
140 0 : state.get_model ().dump_to_logger (*logger);
141 : }
142 33 : }
143 :
144 0 : return true;
145 4 : }
146 :
147 : /* Dump this path in multiline form to PP.
148 : If EXT_STATE is non-NULL, then show the nodes. */
149 :
150 : void
151 0 : exploded_path::dump_to_pp (pretty_printer *pp,
152 : const extrinsic_state *ext_state) const
153 : {
154 0 : for (unsigned i = 0; i < m_elements.size (); ++i)
155 : {
156 0 : const element_t &element = m_elements[i];
157 0 : const exploded_edge *eedge = element.m_eedge;
158 0 : pp_printf (pp, "m_elements[%i]: EN %i -> EN %i",
159 : i,
160 0 : eedge->m_src->m_index,
161 0 : eedge->m_dest->m_index);
162 0 : if (element.m_state_transition)
163 : {
164 0 : pp_string (pp, " {");
165 0 : element.m_state_transition->dump_to_pp (pp);
166 0 : pp_string (pp, "}");
167 : }
168 0 : pp_newline (pp);
169 :
170 0 : if (ext_state)
171 0 : eedge->m_dest->dump_to_pp (pp);
172 : }
173 0 : }
174 :
175 : /* Dump this path in multiline form to FP. */
176 :
177 : void
178 0 : exploded_path::dump (FILE *fp, const extrinsic_state *ext_state) const
179 : {
180 0 : tree_dump_pretty_printer pp (fp);
181 0 : dump_to_pp (&pp, ext_state);
182 0 : }
183 :
184 : /* Dump this path in multiline form to stderr. */
185 :
186 : DEBUG_FUNCTION void
187 0 : exploded_path::dump (const extrinsic_state *ext_state) const
188 : {
189 0 : dump (stderr, ext_state);
190 0 : }
191 :
192 : /* Dump this path verbosely to FILENAME. */
193 :
194 : void
195 0 : exploded_path::dump_to_file (const char *filename,
196 : const extrinsic_state &ext_state) const
197 : {
198 0 : FILE *fp = fopen (filename, "w");
199 0 : if (!fp)
200 : return;
201 0 : pretty_printer pp;
202 0 : pp_format_decoder (&pp) = default_tree_printer;
203 0 : pp.set_output_stream (fp);
204 0 : dump_to_pp (&pp, &ext_state);
205 0 : pp_flush (&pp);
206 0 : fclose (fp);
207 0 : }
208 :
209 : /* Print a multiline form of this path to LOGGER, prefixing it with DESC. */
210 :
211 : void
212 8772 : exploded_path::maybe_log (logger *logger, const char *desc) const
213 : {
214 8772 : if (!logger)
215 : return;
216 4 : logger->start_log_line ();
217 4 : logger->log_partial ("%s: ", desc);
218 4 : logger->end_log_line ();
219 34 : for (unsigned idx = 0; idx < m_elements.size (); idx++)
220 : {
221 26 : const exploded_edge &eedge = *m_elements[idx].m_eedge;
222 26 : const exploded_node *src_node = eedge.m_src;
223 26 : const program_point &src_point = src_node->get_point ();
224 26 : const exploded_node *dst_node = eedge.m_dest;
225 26 : const program_point &dst_point = dst_node->get_point ();
226 :
227 26 : pretty_printer *pp = logger->get_printer ();
228 26 : logger->start_log_line ();
229 26 : pp_printf (pp, " [%i] EN %i -> EN %i: ",
230 : idx,
231 26 : src_node->m_index,
232 26 : dst_node->m_index);
233 26 : src_point.print (pp, format (false));
234 26 : pp_string (pp, " -> ");
235 26 : dst_point.print (pp, format (false));
236 26 : if (auto state_trans = m_elements[idx].m_state_transition.get ())
237 : {
238 0 : pp_string (pp, " {");
239 0 : state_trans->dump_to_pp (pp);
240 0 : pp_string (pp, "}");
241 : }
242 26 : logger->end_log_line ();
243 : }
244 : }
245 :
246 : void
247 6451 : exploded_path::reverse ()
248 : {
249 6451 : std::reverse (m_elements.begin (), m_elements.end ());
250 6451 : }
251 :
252 : } // namespace ana
253 :
254 : #endif /* #if ENABLE_ANALYZER */
|