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 778 : exploded_path::find_stmt_backwards (const gimple *search_stmt,
59 : int *out_idx) const
60 : {
61 8618 : for (int i = m_elements.size () - 1; i >= 0; --i)
62 : {
63 8510 : const element_t *element = &m_elements[i];
64 8510 : const exploded_edge *eedge = element->m_eedge;
65 8510 : 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 778 : if (auto op = eedge->maybe_get_op ())
70 562 : if (auto phis_op = op->dyn_cast_phis_for_edge_op ())
71 88 : if (phis_op->defines_ssa_name_p (gimple_phi_result (search_stmt)))
72 : {
73 40 : *out_idx = i;
74 40 : return true;
75 : }
76 : }
77 : else
78 : {
79 : /* Non-phi stmt. */
80 7732 : if (const gimple *stmt = eedge->maybe_get_stmt ())
81 5324 : if (stmt == search_stmt)
82 : {
83 630 : *out_idx = i;
84 630 : 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 12483 : exploded_path::get_final_enode () const
95 : {
96 12483 : gcc_assert (m_elements.size () > 0);
97 12483 : 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 : logger->start_log_line ();
141 0 : state.get_model ().dump_to_pp (logger->get_printer (), true, false);
142 0 : logger->end_log_line ();
143 : }
144 33 : }
145 :
146 0 : return true;
147 4 : }
148 :
149 : /* Dump this path in multiline form to PP.
150 : If EXT_STATE is non-NULL, then show the nodes. */
151 :
152 : void
153 0 : exploded_path::dump_to_pp (pretty_printer *pp,
154 : const extrinsic_state *ext_state) const
155 : {
156 0 : for (unsigned i = 0; i < m_elements.size (); ++i)
157 : {
158 0 : const element_t &element = m_elements[i];
159 0 : const exploded_edge *eedge = element.m_eedge;
160 0 : pp_printf (pp, "m_elements[%i]: EN %i -> EN %i",
161 : i,
162 0 : eedge->m_src->m_index,
163 0 : eedge->m_dest->m_index);
164 0 : if (element.m_state_transition)
165 : {
166 0 : pp_string (pp, " {");
167 0 : element.m_state_transition->dump_to_pp (pp);
168 0 : pp_string (pp, "}");
169 : }
170 0 : pp_newline (pp);
171 :
172 0 : if (ext_state)
173 0 : eedge->m_dest->dump_to_pp (pp, *ext_state);
174 : }
175 0 : }
176 :
177 : /* Dump this path in multiline form to FP. */
178 :
179 : void
180 0 : exploded_path::dump (FILE *fp, const extrinsic_state *ext_state) const
181 : {
182 0 : tree_dump_pretty_printer pp (fp);
183 0 : dump_to_pp (&pp, ext_state);
184 0 : }
185 :
186 : /* Dump this path in multiline form to stderr. */
187 :
188 : DEBUG_FUNCTION void
189 0 : exploded_path::dump (const extrinsic_state *ext_state) const
190 : {
191 0 : dump (stderr, ext_state);
192 0 : }
193 :
194 : /* Dump this path verbosely to FILENAME. */
195 :
196 : void
197 0 : exploded_path::dump_to_file (const char *filename,
198 : const extrinsic_state &ext_state) const
199 : {
200 0 : FILE *fp = fopen (filename, "w");
201 0 : if (!fp)
202 0 : return;
203 0 : pretty_printer pp;
204 0 : pp_format_decoder (&pp) = default_tree_printer;
205 0 : pp.set_output_stream (fp);
206 0 : dump_to_pp (&pp, &ext_state);
207 0 : pp_flush (&pp);
208 0 : fclose (fp);
209 0 : }
210 :
211 : /* Print a multiline form of this path to LOGGER, prefixing it with DESC. */
212 :
213 : void
214 8322 : exploded_path::maybe_log (logger *logger, const char *desc) const
215 : {
216 8322 : if (!logger)
217 : return;
218 4 : logger->start_log_line ();
219 4 : logger->log_partial ("%s: ", desc);
220 4 : logger->end_log_line ();
221 30 : for (unsigned idx = 0; idx < m_elements.size (); idx++)
222 : {
223 26 : const exploded_edge &eedge = *m_elements[idx].m_eedge;
224 26 : const exploded_node *src_node = eedge.m_src;
225 26 : const program_point &src_point = src_node->get_point ();
226 26 : const exploded_node *dst_node = eedge.m_dest;
227 26 : const program_point &dst_point = dst_node->get_point ();
228 :
229 26 : pretty_printer *pp = logger->get_printer ();
230 26 : logger->start_log_line ();
231 26 : pp_printf (pp, " [%i] EN %i -> EN %i: ",
232 : idx,
233 26 : src_node->m_index,
234 26 : dst_node->m_index);
235 26 : src_point.print (pp, format (false));
236 26 : pp_string (pp, " -> ");
237 26 : dst_point.print (pp, format (false));
238 26 : if (auto state_trans = m_elements[idx].m_state_transition.get ())
239 : {
240 0 : pp_string (pp, " {");
241 0 : state_trans->dump_to_pp (pp);
242 0 : pp_string (pp, "}");
243 : }
244 26 : logger->end_log_line ();
245 : }
246 : }
247 :
248 : void
249 6333 : exploded_path::reverse ()
250 : {
251 6333 : std::reverse (m_elements.begin (), m_elements.end ());
252 6333 : }
253 :
254 : } // namespace ana
255 :
256 : #endif /* #if ENABLE_ANALYZER */
|
