145
|
1 /* Classes for purging state at function_points.
|
|
2 Copyright (C) 2019-2020 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 "config.h"
|
|
22 #include "system.h"
|
|
23 #include "coretypes.h"
|
|
24 #include "tree.h"
|
|
25 #include "timevar.h"
|
|
26 #include "tree-ssa-alias.h"
|
|
27 #include "function.h"
|
|
28 #include "basic-block.h"
|
|
29 #include "gimple.h"
|
|
30 #include "stringpool.h"
|
|
31 #include "tree-vrp.h"
|
|
32 #include "gimple-ssa.h"
|
|
33 #include "tree-ssanames.h"
|
|
34 #include "tree-phinodes.h"
|
|
35 #include "options.h"
|
|
36 #include "ssa-iterators.h"
|
|
37 #include "diagnostic-core.h"
|
|
38 #include "gimple-pretty-print.h"
|
|
39 #include "function.h"
|
|
40 #include "analyzer/analyzer.h"
|
|
41 #include "analyzer/call-string.h"
|
|
42 #include "digraph.h"
|
|
43 #include "ordered-hash-map.h"
|
|
44 #include "cfg.h"
|
|
45 #include "gimple-iterator.h"
|
|
46 #include "cgraph.h"
|
|
47 #include "analyzer/supergraph.h"
|
|
48 #include "analyzer/program-point.h"
|
|
49 #include "analyzer/analyzer-logging.h"
|
|
50 #include "analyzer/state-purge.h"
|
|
51
|
|
52 #if ENABLE_ANALYZER
|
|
53
|
|
54 /* state_purge_map's ctor. Walk all SSA names in all functions, building
|
|
55 a state_purge_per_ssa_name instance for each. */
|
|
56
|
|
57 state_purge_map::state_purge_map (const supergraph &sg,
|
|
58 logger *logger)
|
|
59 : log_user (logger), m_sg (sg)
|
|
60 {
|
|
61 LOG_FUNC (logger);
|
|
62
|
|
63 auto_timevar tv (TV_ANALYZER_STATE_PURGE);
|
|
64
|
|
65 cgraph_node *node;
|
|
66 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
|
|
67 {
|
|
68 function *fun = node->get_fun ();
|
|
69 if (logger)
|
|
70 log ("function: %s", function_name (fun));
|
|
71 tree name;
|
|
72 unsigned int i;;
|
|
73 FOR_EACH_SSA_NAME (i, name, fun)
|
|
74 {
|
|
75 /* For now, don't bother tracking the .MEM SSA names. */
|
|
76 if (tree var = SSA_NAME_VAR (name))
|
|
77 if (TREE_CODE (var) == VAR_DECL)
|
|
78 if (VAR_DECL_IS_VIRTUAL_OPERAND (var))
|
|
79 continue;
|
|
80 m_map.put (name, new state_purge_per_ssa_name (*this, name, fun));
|
|
81 }
|
|
82 }
|
|
83 }
|
|
84
|
|
85 /* state_purge_map's dtor. */
|
|
86
|
|
87 state_purge_map::~state_purge_map ()
|
|
88 {
|
|
89 for (iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
|
|
90 delete (*iter).second;
|
|
91 }
|
|
92
|
|
93 /* state_purge_per_ssa_name's ctor.
|
|
94
|
|
95 Locate all uses of VAR within FUN.
|
|
96 Walk backwards from each use, marking program points, until
|
|
97 we reach the def stmt, populating m_points_needing_var.
|
|
98
|
|
99 We have to track program points rather than
|
|
100 just stmts since there could be empty basic blocks on the way. */
|
|
101
|
|
102 state_purge_per_ssa_name::state_purge_per_ssa_name (const state_purge_map &map,
|
|
103 tree name,
|
|
104 function *fun)
|
|
105 : m_points_needing_name (), m_name (name), m_fun (fun)
|
|
106 {
|
|
107 LOG_FUNC (map.get_logger ());
|
|
108
|
|
109 if (map.get_logger ())
|
|
110 {
|
|
111 map.log ("SSA name: %qE within %qD", name, fun->decl);
|
|
112
|
|
113 /* Show def stmt. */
|
|
114 const gimple *def_stmt = SSA_NAME_DEF_STMT (name);
|
|
115 pretty_printer pp;
|
|
116 pp_gimple_stmt_1 (&pp, def_stmt, 0, (dump_flags_t)0);
|
|
117 map.log ("def stmt: %s", pp_formatted_text (&pp));
|
|
118 }
|
|
119
|
|
120 auto_vec<function_point> worklist;
|
|
121
|
|
122 /* Add all immediate uses of name to the worklist.
|
|
123 Compare with debug_immediate_uses. */
|
|
124 imm_use_iterator iter;
|
|
125 use_operand_p use_p;
|
|
126 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
|
|
127 {
|
|
128 if (USE_STMT (use_p))
|
|
129 {
|
|
130 const gimple *use_stmt = USE_STMT (use_p);
|
|
131 if (map.get_logger ())
|
|
132 {
|
|
133 pretty_printer pp;
|
|
134 pp_gimple_stmt_1 (&pp, use_stmt, 0, (dump_flags_t)0);
|
|
135 map.log ("used by stmt: %s", pp_formatted_text (&pp));
|
|
136 }
|
|
137
|
|
138 const supernode *snode
|
|
139 = map.get_sg ().get_supernode_for_stmt (use_stmt);
|
|
140
|
|
141 /* If it's a use within a phi node, then we care about
|
|
142 which in-edge we came from. */
|
|
143 if (use_stmt->code == GIMPLE_PHI)
|
|
144 {
|
|
145 for (gphi_iterator gpi
|
|
146 = const_cast<supernode *> (snode)->start_phis ();
|
|
147 !gsi_end_p (gpi); gsi_next (&gpi))
|
|
148 {
|
|
149 gphi *phi = gpi.phi ();
|
|
150 if (phi == use_stmt)
|
|
151 {
|
|
152 /* Find arguments (and thus in-edges) which use NAME. */
|
|
153 for (unsigned arg_idx = 0;
|
|
154 arg_idx < gimple_phi_num_args (phi);
|
|
155 ++arg_idx)
|
|
156 {
|
|
157 if (name == gimple_phi_arg (phi, arg_idx)->def)
|
|
158 {
|
|
159 edge in_edge = gimple_phi_arg_edge (phi, arg_idx);
|
|
160 const superedge *in_sedge
|
|
161 = map.get_sg ().get_edge_for_cfg_edge (in_edge);
|
|
162 function_point point
|
|
163 = function_point::before_supernode
|
|
164 (snode, in_sedge);
|
|
165 add_to_worklist (point, &worklist,
|
|
166 map.get_logger ());
|
|
167 m_points_needing_name.add (point);
|
|
168 }
|
|
169 }
|
|
170 }
|
|
171 }
|
|
172 }
|
|
173 else
|
|
174 {
|
|
175 function_point point = before_use_stmt (map, use_stmt);
|
|
176 add_to_worklist (point, &worklist, map.get_logger ());
|
|
177 m_points_needing_name.add (point);
|
|
178
|
|
179 /* We also need to add uses for conditionals and switches,
|
|
180 where the stmt "happens" at the after_supernode, for filtering
|
|
181 the out-edges. */
|
|
182 if (use_stmt == snode->get_last_stmt ())
|
|
183 {
|
|
184 if (map.get_logger ())
|
|
185 map.log ("last stmt in BB");
|
|
186 function_point point
|
|
187 = function_point::after_supernode (snode);
|
|
188 add_to_worklist (point, &worklist, map.get_logger ());
|
|
189 m_points_needing_name.add (point);
|
|
190 }
|
|
191 else
|
|
192 if (map.get_logger ())
|
|
193 map.log ("not last stmt in BB");
|
|
194 }
|
|
195 }
|
|
196 }
|
|
197
|
|
198 /* Process worklist by walking backwards until we reach the def stmt. */
|
|
199 {
|
|
200 log_scope s (map.get_logger (), "processing worklist");
|
|
201 while (worklist.length () > 0)
|
|
202 {
|
|
203 function_point point = worklist.pop ();
|
|
204 process_point (point, &worklist, map);
|
|
205 }
|
|
206 }
|
|
207
|
|
208 if (map.get_logger ())
|
|
209 {
|
|
210 map.log ("%qE in %qD is needed to process:", name, fun->decl);
|
|
211 for (point_set_t::iterator iter = m_points_needing_name.begin ();
|
|
212 iter != m_points_needing_name.end ();
|
|
213 ++iter)
|
|
214 {
|
|
215 map.start_log_line ();
|
|
216 map.get_logger ()->log_partial (" point: ");
|
|
217 (*iter).print (map.get_logger ()->get_printer (), format (false));
|
|
218 map.end_log_line ();
|
|
219 }
|
|
220 }
|
|
221 }
|
|
222
|
|
223 /* Return true if the SSA name is needed at POINT. */
|
|
224
|
|
225 bool
|
|
226 state_purge_per_ssa_name::needed_at_point_p (const function_point &point) const
|
|
227 {
|
|
228 return const_cast <point_set_t &> (m_points_needing_name).contains (point);
|
|
229 }
|
|
230
|
|
231 /* Get the function_point representing immediately before USE_STMT.
|
|
232 Subroutine of ctor. */
|
|
233
|
|
234 function_point
|
|
235 state_purge_per_ssa_name::before_use_stmt (const state_purge_map &map,
|
|
236 const gimple *use_stmt)
|
|
237 {
|
|
238 gcc_assert (use_stmt->code != GIMPLE_PHI);
|
|
239
|
|
240 const supernode *supernode
|
|
241 = map.get_sg ().get_supernode_for_stmt (use_stmt);
|
|
242 unsigned int stmt_idx = supernode->get_stmt_index (use_stmt);
|
|
243 return function_point::before_stmt (supernode, stmt_idx);
|
|
244 }
|
|
245
|
|
246 /* Add POINT to *WORKLIST if the point has not already been seen.
|
|
247 Subroutine of ctor. */
|
|
248
|
|
249 void
|
|
250 state_purge_per_ssa_name::add_to_worklist (const function_point &point,
|
|
251 auto_vec<function_point> *worklist,
|
|
252 logger *logger)
|
|
253 {
|
|
254 LOG_FUNC (logger);
|
|
255 if (logger)
|
|
256 {
|
|
257 logger->start_log_line ();
|
|
258 logger->log_partial ("point: '");
|
|
259 point.print (logger->get_printer (), format (false));
|
|
260 logger->log_partial ("' for worklist for %qE", m_name);
|
|
261 logger->end_log_line ();
|
|
262 }
|
|
263
|
|
264 gcc_assert (point.get_function () == m_fun);
|
|
265 if (point.get_from_edge ())
|
|
266 gcc_assert (point.get_from_edge ()->get_kind () == SUPEREDGE_CFG_EDGE);
|
|
267
|
|
268 if (m_points_needing_name.contains (point))
|
|
269 {
|
|
270 if (logger)
|
|
271 logger->log ("already seen for %qE", m_name);
|
|
272 }
|
|
273 else
|
|
274 {
|
|
275 if (logger)
|
|
276 logger->log ("not seen; adding to worklist for %qE", m_name);
|
|
277 m_points_needing_name.add (point);
|
|
278 worklist->safe_push (point);
|
|
279 }
|
|
280 }
|
|
281
|
|
282 /* Process POINT, popped from WORKLIST.
|
|
283 Iterate over predecessors of POINT, adding to WORKLIST. */
|
|
284
|
|
285 void
|
|
286 state_purge_per_ssa_name::process_point (const function_point &point,
|
|
287 auto_vec<function_point> *worklist,
|
|
288 const state_purge_map &map)
|
|
289 {
|
|
290 logger *logger = map.get_logger ();
|
|
291 LOG_FUNC (logger);
|
|
292 if (logger)
|
|
293 {
|
|
294 logger->start_log_line ();
|
|
295 logger->log_partial ("considering point: '");
|
|
296 point.print (logger->get_printer (), format (false));
|
|
297 logger->log_partial ("' for %qE", m_name);
|
|
298 logger->end_log_line ();
|
|
299 }
|
|
300
|
|
301 gimple *def_stmt = SSA_NAME_DEF_STMT (m_name);
|
|
302
|
|
303 const supernode *snode = point.get_supernode ();
|
|
304
|
|
305 switch (point.get_kind ())
|
|
306 {
|
|
307 default:
|
|
308 gcc_unreachable ();
|
|
309
|
|
310 case PK_ORIGIN:
|
|
311 break;
|
|
312
|
|
313 case PK_BEFORE_SUPERNODE:
|
|
314 {
|
|
315 for (gphi_iterator gpi
|
|
316 = const_cast<supernode *> (snode)->start_phis ();
|
|
317 !gsi_end_p (gpi); gsi_next (&gpi))
|
|
318 {
|
|
319 gphi *phi = gpi.phi ();
|
|
320 if (phi == def_stmt)
|
|
321 {
|
|
322 if (logger)
|
|
323 logger->log ("def stmt within phis; terminating");
|
|
324 return;
|
|
325 }
|
|
326 }
|
|
327
|
|
328 /* Add given pred to worklist. */
|
|
329 if (point.get_from_edge ())
|
|
330 {
|
|
331 gcc_assert (point.get_from_edge ()->m_src);
|
|
332 add_to_worklist
|
|
333 (function_point::after_supernode (point.get_from_edge ()->m_src),
|
|
334 worklist, logger);
|
|
335 }
|
|
336 else
|
|
337 {
|
|
338 /* Add any intraprocedually edge for a call. */
|
|
339 if (snode->m_returning_call)
|
|
340 {
|
|
341 cgraph_edge *cedge
|
|
342 = supergraph_call_edge (snode->m_fun,
|
|
343 snode->m_returning_call);
|
|
344 gcc_assert (cedge);
|
|
345 superedge *sedge
|
|
346 = map.get_sg ().get_intraprocedural_edge_for_call (cedge);
|
|
347 gcc_assert (sedge);
|
|
348 add_to_worklist
|
|
349 (function_point::after_supernode (sedge->m_src),
|
|
350 worklist, logger);
|
|
351 }
|
|
352 }
|
|
353 }
|
|
354 break;
|
|
355
|
|
356 case PK_BEFORE_STMT:
|
|
357 {
|
|
358 if (def_stmt == point.get_stmt ())
|
|
359 {
|
|
360 if (logger)
|
|
361 logger->log ("def stmt; terminating");
|
|
362 return;
|
|
363 }
|
|
364 if (point.get_stmt_idx () > 0)
|
|
365 add_to_worklist (function_point::before_stmt
|
|
366 (snode, point.get_stmt_idx () - 1),
|
|
367 worklist, logger);
|
|
368 else
|
|
369 {
|
|
370 /* Add before_supernode to worklist. This captures the in-edge,
|
|
371 so we have to do it once per in-edge. */
|
|
372 unsigned i;
|
|
373 superedge *pred;
|
|
374 FOR_EACH_VEC_ELT (snode->m_preds, i, pred)
|
|
375 add_to_worklist (function_point::before_supernode (snode,
|
|
376 pred),
|
|
377 worklist, logger);
|
|
378 }
|
|
379 }
|
|
380 break;
|
|
381
|
|
382 case PK_AFTER_SUPERNODE:
|
|
383 {
|
|
384 if (snode->m_stmts.length ())
|
|
385 add_to_worklist
|
|
386 (function_point::before_stmt (snode,
|
|
387 snode->m_stmts.length () - 1),
|
|
388 worklist, logger);
|
|
389 else
|
|
390 {
|
|
391 /* Add before_supernode to worklist. This captures the in-edge,
|
|
392 so we have to do it once per in-edge. */
|
|
393 unsigned i;
|
|
394 superedge *pred;
|
|
395 FOR_EACH_VEC_ELT (snode->m_preds, i, pred)
|
|
396 add_to_worklist (function_point::before_supernode (snode,
|
|
397 pred),
|
|
398 worklist, logger);
|
|
399 /* If it's the initial BB, add it, to ensure that we
|
|
400 have "before supernode" for the initial ENTRY block, and don't
|
|
401 erroneously purge SSA names for initial values of parameters. */
|
|
402 if (snode->entry_p ())
|
|
403 {
|
|
404 add_to_worklist
|
|
405 (function_point::before_supernode (snode, NULL),
|
|
406 worklist, logger);
|
|
407 }
|
|
408 }
|
|
409 }
|
|
410 break;
|
|
411 }
|
|
412 }
|
|
413
|
|
414 /* class state_purge_annotator : public dot_annotator. */
|
|
415
|
|
416 /* Implementation of dot_annotator::add_node_annotations vfunc for
|
|
417 state_purge_annotator.
|
|
418
|
|
419 Add an additional record showing which names are purged on entry
|
|
420 to the supernode N. */
|
|
421
|
|
422 void
|
|
423 state_purge_annotator::add_node_annotations (graphviz_out *gv,
|
|
424 const supernode &n) const
|
|
425 {
|
|
426 if (m_map == NULL)
|
|
427 return;
|
|
428
|
|
429 pretty_printer *pp = gv->get_pp ();
|
|
430
|
|
431 pp_printf (pp, "annotation_for_node_%i", n.m_index);
|
|
432 pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
|
|
433 "lightblue");
|
|
434 pp_write_text_to_stream (pp);
|
|
435
|
|
436 // FIXME: passing in a NULL in-edge means we get no hits
|
|
437 function_point before_supernode
|
|
438 (function_point::before_supernode (&n, NULL));
|
|
439
|
|
440 for (state_purge_map::iterator iter = m_map->begin ();
|
|
441 iter != m_map->end ();
|
|
442 ++iter)
|
|
443 {
|
|
444 tree name = (*iter).first;
|
|
445 state_purge_per_ssa_name *per_name_data = (*iter).second;
|
|
446 if (per_name_data->get_function () == n.m_fun)
|
|
447 {
|
|
448 if (per_name_data->needed_at_point_p (before_supernode))
|
|
449 pp_printf (pp, "%qE needed here", name);
|
|
450 else
|
|
451 pp_printf (pp, "%qE not needed here", name);
|
|
452 }
|
|
453 pp_newline (pp);
|
|
454 }
|
|
455
|
|
456 pp_string (pp, "\"];\n\n");
|
|
457 pp_flush (pp);
|
|
458 }
|
|
459
|
|
460 /* Print V to GV as a comma-separated list in braces within a <TR>,
|
|
461 titling it with TITLE.
|
|
462
|
|
463 Subroutine of state_purge_annotator::add_stmt_annotations. */
|
|
464
|
|
465 static void
|
|
466 print_vec_of_names (graphviz_out *gv, const char *title,
|
|
467 const auto_vec<tree> &v)
|
|
468 {
|
|
469 pretty_printer *pp = gv->get_pp ();
|
|
470 tree name;
|
|
471 unsigned i;
|
|
472 gv->begin_tr ();
|
|
473 pp_printf (pp, "%s: {", title);
|
|
474 FOR_EACH_VEC_ELT (v, i, name)
|
|
475 {
|
|
476 if (i > 0)
|
|
477 pp_string (pp, ", ");
|
|
478 pp_printf (pp, "%qE", name);
|
|
479 }
|
|
480 pp_printf (pp, "}");
|
|
481 pp_write_text_as_html_like_dot_to_stream (pp);
|
|
482 gv->end_tr ();
|
|
483 pp_newline (pp);
|
|
484 }
|
|
485
|
|
486 /* Implementation of dot_annotator::add_stmt_annotations for
|
|
487 state_purge_annotator.
|
|
488
|
|
489 Add text showing which names are purged at STMT. */
|
|
490
|
|
491 void
|
|
492 state_purge_annotator::add_stmt_annotations (graphviz_out *gv,
|
|
493 const gimple *stmt) const
|
|
494 {
|
|
495 if (m_map == NULL)
|
|
496 return;
|
|
497
|
|
498 if (stmt->code == GIMPLE_PHI)
|
|
499 return;
|
|
500
|
|
501 pretty_printer *pp = gv->get_pp ();
|
|
502
|
|
503 pp_newline (pp);
|
|
504
|
|
505 const supernode *supernode = m_map->get_sg ().get_supernode_for_stmt (stmt);
|
|
506 unsigned int stmt_idx = supernode->get_stmt_index (stmt);
|
|
507 function_point before_stmt
|
|
508 (function_point::before_stmt (supernode, stmt_idx));
|
|
509
|
|
510 auto_vec<tree> needed;
|
|
511 auto_vec<tree> not_needed;
|
|
512 for (state_purge_map::iterator iter = m_map->begin ();
|
|
513 iter != m_map->end ();
|
|
514 ++iter)
|
|
515 {
|
|
516 tree name = (*iter).first;
|
|
517 state_purge_per_ssa_name *per_name_data = (*iter).second;
|
|
518 if (per_name_data->get_function () == supernode->m_fun)
|
|
519 {
|
|
520 if (per_name_data->needed_at_point_p (before_stmt))
|
|
521 needed.safe_push (name);
|
|
522 else
|
|
523 not_needed.safe_push (name);
|
|
524 }
|
|
525 }
|
|
526
|
|
527 print_vec_of_names (gv, "needed here", needed);
|
|
528 print_vec_of_names (gv, "not needed here", not_needed);
|
|
529 }
|
|
530
|
|
531 #endif /* #if ENABLE_ANALYZER */
|