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
state_purge_map(const supergraph & sg,logger * logger)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
~state_purge_map()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
state_purge_per_ssa_name(const state_purge_map & map,tree name,function * fun)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
needed_at_point_p(const function_point & point) const226 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
before_use_stmt(const state_purge_map & map,const gimple * use_stmt)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
add_to_worklist(const function_point & point,auto_vec<function_point> * worklist,logger * logger)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
process_point(const function_point & point,auto_vec<function_point> * worklist,const state_purge_map & map)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 bool
add_node_annotations(graphviz_out * gv,const supernode & n,bool within_table) const423 state_purge_annotator::add_node_annotations (graphviz_out *gv,
424 const supernode &n,
425 bool within_table) const
426 {
427 if (m_map == NULL)
428 return false;
429
430 if (within_table)
431 return false;
432
433 pretty_printer *pp = gv->get_pp ();
434
435 pp_printf (pp, "annotation_for_node_%i", n.m_index);
436 pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
437 "lightblue");
438 pp_write_text_to_stream (pp);
439
440 // FIXME: passing in a NULL in-edge means we get no hits
441 function_point before_supernode
442 (function_point::before_supernode (&n, NULL));
443
444 for (state_purge_map::iterator iter = m_map->begin ();
445 iter != m_map->end ();
446 ++iter)
447 {
448 tree name = (*iter).first;
449 state_purge_per_ssa_name *per_name_data = (*iter).second;
450 if (per_name_data->get_function () == n.m_fun)
451 {
452 if (per_name_data->needed_at_point_p (before_supernode))
453 pp_printf (pp, "%qE needed here", name);
454 else
455 pp_printf (pp, "%qE not needed here", name);
456 }
457 pp_newline (pp);
458 }
459
460 pp_string (pp, "\"];\n\n");
461 pp_flush (pp);
462 return false;
463 }
464
465 /* Print V to GV as a comma-separated list in braces within a <TR>,
466 titling it with TITLE.
467
468 Subroutine of state_purge_annotator::add_stmt_annotations. */
469
470 static void
print_vec_of_names(graphviz_out * gv,const char * title,const auto_vec<tree> & v)471 print_vec_of_names (graphviz_out *gv, const char *title,
472 const auto_vec<tree> &v)
473 {
474 pretty_printer *pp = gv->get_pp ();
475 tree name;
476 unsigned i;
477 gv->begin_trtd ();
478 pp_printf (pp, "%s: {", title);
479 FOR_EACH_VEC_ELT (v, i, name)
480 {
481 if (i > 0)
482 pp_string (pp, ", ");
483 pp_printf (pp, "%qE", name);
484 }
485 pp_printf (pp, "}");
486 pp_write_text_as_html_like_dot_to_stream (pp);
487 gv->end_tdtr ();
488 pp_newline (pp);
489 }
490
491 /* Implementation of dot_annotator::add_stmt_annotations for
492 state_purge_annotator.
493
494 Add text showing which names are purged at STMT. */
495
496 void
add_stmt_annotations(graphviz_out * gv,const gimple * stmt,bool within_row) const497 state_purge_annotator::add_stmt_annotations (graphviz_out *gv,
498 const gimple *stmt,
499 bool within_row) const
500 {
501 if (within_row)
502 return;
503
504 if (m_map == NULL)
505 return;
506
507 if (stmt->code == GIMPLE_PHI)
508 return;
509
510 pretty_printer *pp = gv->get_pp ();
511
512 pp_newline (pp);
513
514 const supernode *supernode = m_map->get_sg ().get_supernode_for_stmt (stmt);
515 unsigned int stmt_idx = supernode->get_stmt_index (stmt);
516 function_point before_stmt
517 (function_point::before_stmt (supernode, stmt_idx));
518
519 auto_vec<tree> needed;
520 auto_vec<tree> not_needed;
521 for (state_purge_map::iterator iter = m_map->begin ();
522 iter != m_map->end ();
523 ++iter)
524 {
525 tree name = (*iter).first;
526 state_purge_per_ssa_name *per_name_data = (*iter).second;
527 if (per_name_data->get_function () == supernode->m_fun)
528 {
529 if (per_name_data->needed_at_point_p (before_stmt))
530 needed.safe_push (name);
531 else
532 not_needed.safe_push (name);
533 }
534 }
535
536 print_vec_of_names (gv, "needed here", needed);
537 print_vec_of_names (gv, "not needed here", not_needed);
538 }
539
540 #endif /* #if ENABLE_ANALYZER */
541