Line data Source code
1 : /* Simplifying the supergraph.
2 : Copyright (C) 2025-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 : #define INCLUDE_DEQUE
22 : #define INCLUDE_SET
23 : #include "analyzer/common.h"
24 :
25 : #include "cgraph.h"
26 : #include "timevar.h"
27 :
28 : #include "analyzer/supergraph.h"
29 : #include "analyzer/analyzer-logging.h"
30 : #include "analyzer/supergraph-manipulation.h"
31 : #include "analyzer/bar-chart.h"
32 :
33 : #if ENABLE_ANALYZER
34 :
35 : namespace ana {
36 :
37 : namespace {
38 :
39 : /* A class for tracking a set of simplifications to a supergraph.
40 : supergraph.m_nodes and supergraph.m_edges may contain deleted object
41 : during the lifetime of this class; they are removed at the end. */
42 :
43 : class simplifier
44 : {
45 : public:
46 3377 : simplifier (supergraph &sg,
47 : ana::logger *logger)
48 3377 : : m_sg (sg),
49 3377 : m_nodes_to_remove (),
50 3377 : m_edges_to_remove (),
51 3377 : m_logger (logger),
52 3377 : m_stats ()
53 : {
54 197777 : for (auto node : sg.m_nodes)
55 187654 : m_worklist.ensure_node_queued (node, logger);
56 3377 : }
57 :
58 3377 : ~simplifier ()
59 : {
60 : // Remove nodes from m_sg.m_nodes and delete them
61 3377 : m_sg.delete_nodes (m_nodes_to_remove);
62 :
63 : // Remove edges from m_sg.m_edges and delete them
64 3377 : {
65 3377 : unsigned read_index, write_index;
66 3377 : superedge **elem_ptr;
67 190620 : VEC_ORDERED_REMOVE_IF (m_sg.m_edges, read_index, write_index, elem_ptr,
68 3377 : edge_to_be_removed_p (*elem_ptr));
69 8691 : for (auto iter : m_edges_to_remove)
70 5314 : delete iter;
71 : }
72 :
73 3377 : if (m_logger)
74 : {
75 5 : log_nesting_level sentinel (m_logger, "stats");
76 5 : m_stats.log (*m_logger);
77 5 : }
78 3377 : }
79 :
80 : /* Manipulations: logged, and refreshing the worklist. */
81 :
82 : void
83 5812 : set_edge_dest (superedge *edge, supernode *new_dest)
84 : {
85 5812 : if (edge->m_dest == new_dest)
86 0 : return;
87 5812 : log_nesting_level sentinel
88 : (m_logger, "updating edge dest: SN: %i -> SN: {%i, %i}",
89 5812 : edge->m_src->m_id,
90 : edge->m_dest->m_id,
91 5812 : new_dest->m_id);
92 5812 : m_worklist.ensure_node_queued (edge->m_src, m_logger);
93 5812 : m_worklist.ensure_node_queued (edge->m_dest, m_logger);
94 5812 : m_worklist.ensure_node_queued (new_dest, m_logger);
95 :
96 5812 : edge->set_dest (new_dest);
97 :
98 5812 : m_stats.m_num_set_edge_dest++;
99 5812 : }
100 :
101 : void
102 10879 : remove_node (supernode *node)
103 : {
104 10879 : log_nesting_level sentinel
105 10879 : (m_logger, "removing node: SN: %i", node->m_id);
106 32061 : for (auto in_edge : node->m_preds)
107 0 : remove_edge (in_edge);
108 37449 : for (auto out_edge : node->m_succs)
109 5314 : remove_edge (out_edge);
110 10879 : m_nodes_to_remove.insert (node);
111 10879 : m_stats.m_num_remove_node++;
112 10879 : }
113 :
114 : void
115 5314 : remove_edge (superedge *edge)
116 : {
117 5314 : log_nesting_level sentinel
118 : (m_logger, "removing edge dest: SN: %i -> SN: %i",
119 5314 : edge->m_src->m_id,
120 5314 : edge->m_dest->m_id);
121 5314 : gcc_assert (!edge->preserve_p ());
122 :
123 5314 : m_worklist.ensure_node_queued (edge->m_src, m_logger);
124 5314 : m_worklist.ensure_node_queued (edge->m_dest, m_logger);
125 :
126 5314 : edge->m_src->remove_out_edge (edge);
127 5314 : edge->m_dest->remove_in_edge (edge);
128 :
129 5314 : m_edges_to_remove.insert (edge);
130 :
131 5314 : m_stats.m_num_remove_edge++;
132 5314 : }
133 :
134 : /* High level ops. */
135 :
136 : supernode *
137 209881 : pop_next_node_in_queue ()
138 : {
139 209881 : return m_worklist.pop ();
140 : }
141 :
142 : void
143 206504 : consider_node (supernode *node)
144 : {
145 206504 : m_stats.m_num_iterations++;
146 :
147 206504 : log_nesting_level sentinel (m_logger, "considering SN: %i", node->m_id);
148 :
149 : /* Eliminate nodes with no in-edges that aren't function entry nodes. */
150 217095 : if (node->m_preds.length () == 0
151 206504 : && !node->entry_p ())
152 : {
153 10879 : log_nesting_level s2 (m_logger, "no in-edges");
154 10879 : remove_node (node);
155 10879 : return;
156 10879 : }
157 :
158 : /* Handle nodes with a single out-edge. */
159 364561 : if (node->m_succs.length () == 1)
160 174346 : if (consider_single_out_edge (node, node->m_succs[0]))
161 : return;
162 206504 : }
163 :
164 : bool
165 174346 : consider_single_out_edge (supernode *node,
166 : superedge *single_out_edge)
167 : {
168 174346 : if (node->preserve_p ())
169 : {
170 17746 : log_nesting_level s3
171 : (m_logger,
172 17746 : "node has preserve_p flag; preserving");
173 17746 : return false;
174 17746 : }
175 156600 : if (single_out_edge->preserve_p ())
176 : {
177 1702 : log_nesting_level s3
178 : (m_logger,
179 1702 : "edge has preserve_p flag; preserving");
180 1702 : return false;
181 : }
182 :
183 : /* Is the single out-edge a no-op? */
184 154898 : if (!single_out_edge->get_op ())
185 : {
186 : /* If the node doesn't add useful location information, we can
187 : redirect all in-edges to the node to point at the outedge's dst. */
188 33244 : log_nesting_level s2 (m_logger,
189 : "single outedge is no-op (to SN: %i)",
190 33244 : node->m_succs[0]->m_dest->m_id);
191 33244 : bool redirect = false;
192 33244 : if (node->m_loc == UNKNOWN_LOCATION)
193 : {
194 1317 : log_nesting_level s3
195 : (m_logger,
196 1317 : "node is at UNKNOWN_LOCATION; redirecting in-edges");
197 1317 : redirect = true;
198 1317 : }
199 31927 : else if (node->m_loc == single_out_edge->m_dest->m_loc)
200 : {
201 4093 : log_nesting_level s3
202 : (m_logger,
203 4093 : "node has same location as successor; redirecting in-edges");
204 4093 : redirect = true;
205 4093 : }
206 :
207 5410 : if (redirect)
208 : {
209 21774 : for (auto in_edge : node->m_preds)
210 5812 : set_edge_dest (in_edge, single_out_edge->m_dest);
211 : return true;
212 : }
213 :
214 : return false;
215 33244 : }
216 :
217 : gcc_assert (single_out_edge->get_op ());
218 :
219 : return false;
220 : }
221 :
222 : private:
223 187243 : bool edge_to_be_removed_p (superedge *edge)
224 : {
225 187243 : return m_edges_to_remove.find (edge) != m_edges_to_remove.end ();
226 : }
227 :
228 : supergraph &m_sg;
229 : supergraph_manipulation::worklist m_worklist;
230 : std::set<supernode *> m_nodes_to_remove;
231 : std::set<superedge *> m_edges_to_remove;
232 : ana::logger *m_logger;
233 : struct stats
234 : {
235 : stats () = default;
236 :
237 5 : void log (ana::logger &logger)
238 : {
239 5 : logger.log ("# iterations taken: " HOST_SIZE_T_PRINT_UNSIGNED,
240 5 : (fmt_size_t)m_num_iterations);
241 5 : logger.log ("# nodes removed: " HOST_SIZE_T_PRINT_UNSIGNED,
242 5 : (fmt_size_t)m_num_remove_node);
243 5 : logger.log ("# edges removed: " HOST_SIZE_T_PRINT_UNSIGNED,
244 5 : (fmt_size_t)m_num_remove_edge);
245 5 : logger.log ("# set_edge_dest: " HOST_SIZE_T_PRINT_UNSIGNED,
246 5 : (fmt_size_t)m_num_set_edge_dest);
247 5 : }
248 :
249 : size_t m_num_iterations;
250 : size_t m_num_remove_node;
251 : size_t m_num_remove_edge;
252 : size_t m_num_set_edge_dest;
253 :
254 : } m_stats;
255 : };
256 :
257 : } // anonymous namespace
258 :
259 : void
260 6754 : supergraph::log_stats (logger *logger) const
261 : {
262 6754 : if (!logger)
263 : return;
264 :
265 20 : logger->log ("# nodes: %u", m_nodes.length ());
266 20 : logger->log ("# edges: %u", m_edges.length ());
267 :
268 : /* Show per-function bar charts of supernodes per function. */
269 10 : {
270 10 : bar_chart snodes_per_function;
271 10 : logger->log ("snodes per function:");
272 :
273 10 : cgraph_node *cgnode;
274 22 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
275 : {
276 12 : function *fn = cgnode->get_fun ();
277 :
278 12 : int snodes_for_this_function = 0;
279 251 : for (auto node : m_nodes)
280 215 : if (node->get_function () == fn)
281 162 : ++snodes_for_this_function;
282 :
283 12 : pretty_printer pp;
284 12 : pp_format_decoder (&pp) = default_tree_printer;
285 12 : pp_printf (&pp, "%qD", fn->decl);
286 12 : snodes_per_function.add_item (pp_formatted_text (&pp),
287 : snodes_for_this_function);
288 12 : }
289 :
290 10 : snodes_per_function.print (logger->get_printer ());
291 10 : }
292 : }
293 :
294 : void
295 3377 : supergraph::simplify (logger *logger)
296 : {
297 3377 : auto_timevar tv (TV_ANALYZER_SUPERGRAPH_SIMPLIFY);
298 3377 : LOG_SCOPE (logger);
299 :
300 3377 : {
301 3377 : log_nesting_level sentinel (logger, "before simplification:");
302 3377 : log_stats (logger);
303 3377 : }
304 :
305 3377 : {
306 3377 : simplifier opt (*this, logger);
307 209881 : while (supernode *node = opt.pop_next_node_in_queue ())
308 206504 : opt.consider_node (node);
309 3377 : }
310 :
311 3377 : {
312 3377 : log_nesting_level sentinel (logger, "after simplification");
313 3377 : log_stats (logger);
314 3377 : }
315 3377 : }
316 :
317 : } // namespace ana
318 :
319 : #endif /* #if ENABLE_ANALYZER */
|
