1/* Classes for purging state at function_points.
2 Copyright (C) 2019-2024 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#define INCLUDE_MEMORY
23#include "system.h"
24#include "coretypes.h"
25#include "tree.h"
26#include "timevar.h"
27#include "tree-ssa-alias.h"
28#include "function.h"
29#include "basic-block.h"
30#include "gimple.h"
31#include "stringpool.h"
32#include "tree-vrp.h"
33#include "gimple-ssa.h"
34#include "tree-ssanames.h"
35#include "tree-phinodes.h"
36#include "options.h"
37#include "ssa-iterators.h"
38#include "diagnostic-core.h"
39#include "gimple-pretty-print.h"
40#include "analyzer/analyzer.h"
41#include "analyzer/call-string.h"
42#include "analyzer/supergraph.h"
43#include "analyzer/program-point.h"
44#include "analyzer/analyzer-logging.h"
45#include "analyzer/state-purge.h"
46#include "analyzer/store.h"
47#include "analyzer/region-model.h"
48#include "gimple-walk.h"
49#include "cgraph.h"
50
51#if ENABLE_ANALYZER
52
53/* Given NODE at an access, determine if this access is within
54 a decl that could be consider for purging, and if so, return the decl. */
55
56static tree
57get_candidate_for_purging (tree node)
58{
59 tree iter = node;
60 while (1)
61 switch (TREE_CODE (iter))
62 {
63 default:
64 return NULL_TREE;
65
66 case ADDR_EXPR:
67 case MEM_REF:
68 case COMPONENT_REF:
69 iter = TREE_OPERAND (iter, 0);
70 continue;
71
72 case VAR_DECL:
73 if (is_global_var (t: iter))
74 return NULL_TREE;
75 else
76 return iter;
77
78 case PARM_DECL:
79 case RESULT_DECL:
80 return iter;
81 }
82}
83
84/* Class-based handler for walk_stmt_load_store_addr_ops at a particular
85 function_point, for populating the worklists within a state_purge_map. */
86
87class gimple_op_visitor : public log_user
88{
89public:
90 gimple_op_visitor (state_purge_map *map,
91 const function_point &point,
92 const function &fun)
93 : log_user (map->get_logger ()),
94 m_map (map),
95 m_point (point),
96 m_fun (fun)
97 {}
98
99 bool on_load (gimple *stmt, tree base, tree op)
100 {
101 LOG_FUNC (get_logger ());
102 if (get_logger ())
103 {
104 pretty_printer pp;
105 pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
106 log (fmt: "on_load: %s; base: %qE, op: %qE",
107 pp_formatted_text (&pp), base, op);
108 }
109 if (tree node = get_candidate_for_purging (node: base))
110 add_needed (decl: node);
111 return true;
112 }
113
114 bool on_store (gimple *stmt, tree base, tree op)
115 {
116 LOG_FUNC (get_logger ());
117 if (get_logger ())
118 {
119 pretty_printer pp;
120 pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
121 log (fmt: "on_store: %s; base: %qE, op: %qE",
122 pp_formatted_text (&pp), base, op);
123 }
124 return true;
125 }
126
127 bool on_addr (gimple *stmt, tree base, tree op)
128 {
129 LOG_FUNC (get_logger ());
130 if (get_logger ())
131 {
132 pretty_printer pp;
133 pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
134 log (fmt: "on_addr: %s; base: %qE, op: %qE",
135 pp_formatted_text (&pp), base, op);
136 }
137 if (TREE_CODE (op) != ADDR_EXPR)
138 return true;
139 if (tree node = get_candidate_for_purging (node: base))
140 {
141 add_needed (decl: node);
142 add_pointed_to (decl: node);
143 }
144 return true;
145 }
146
147private:
148 void add_needed (tree decl)
149 {
150 gcc_assert (get_candidate_for_purging (decl) == decl);
151 state_purge_per_decl &data
152 = get_or_create_data_for_decl (decl);
153 data.add_needed_at (point: m_point);
154
155 /* Handle calls: if we're seeing a use at a call, then add a use at the
156 "after-supernode" point (in case of interprocedural call superedges). */
157 if (m_point.final_stmt_p ())
158 data.add_needed_at (point: m_point.get_next ());
159 }
160
161 void add_pointed_to (tree decl)
162 {
163 gcc_assert (get_candidate_for_purging (decl) == decl);
164 get_or_create_data_for_decl (decl).add_pointed_to_at (point: m_point);
165 }
166
167 state_purge_per_decl &
168 get_or_create_data_for_decl (tree decl)
169 {
170 return m_map->get_or_create_data_for_decl (fun: m_fun, decl);
171 }
172
173 state_purge_map *m_map;
174 const function_point &m_point;
175 const function &m_fun;
176};
177
178static bool
179my_load_cb (gimple *stmt, tree base, tree op, void *user_data)
180{
181 gimple_op_visitor *x = (gimple_op_visitor *)user_data;
182 return x->on_load (stmt, base, op);
183}
184
185static bool
186my_store_cb (gimple *stmt, tree base, tree op, void *user_data)
187{
188 gimple_op_visitor *x = (gimple_op_visitor *)user_data;
189 return x->on_store (stmt, base, op);
190}
191
192static bool
193my_addr_cb (gimple *stmt, tree base, tree op, void *user_data)
194{
195 gimple_op_visitor *x = (gimple_op_visitor *)user_data;
196 return x->on_addr (stmt, base, op);
197}
198
199/* state_purge_map's ctor. Walk all SSA names in all functions, building
200 a state_purge_per_ssa_name instance for each.
201 Also, walk all loads and address-taken ops of local variables, building
202 a state_purge_per_decl as appropriate. */
203
204state_purge_map::state_purge_map (const supergraph &sg,
205 region_model_manager *mgr,
206 logger *logger)
207: log_user (logger), m_sg (sg)
208{
209 LOG_FUNC (logger);
210
211 auto_timevar tv (TV_ANALYZER_STATE_PURGE);
212
213 cgraph_node *node;
214 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
215 {
216 function *fun = node->get_fun ();
217 gcc_assert (fun);
218 if (logger)
219 log (fmt: "function: %s", function_name (fun));
220 tree name;
221 unsigned int i;;
222 FOR_EACH_SSA_NAME (i, name, fun)
223 {
224 /* For now, don't bother tracking the .MEM SSA names. */
225 if (tree var = SSA_NAME_VAR (name))
226 if (TREE_CODE (var) == VAR_DECL)
227 if (VAR_DECL_IS_VIRTUAL_OPERAND (var))
228 continue;
229 m_ssa_map.put (k: name, v: new state_purge_per_ssa_name (*this, name, *fun));
230 }
231 }
232
233 /* Find all uses of local vars.
234 We iterate through all function points, finding loads, stores, and
235 address-taken operations on locals, building a pair of worklists. */
236 for (auto snode : sg.m_nodes)
237 {
238 if (logger)
239 log (fmt: "SN: %i", snode->m_index);
240 /* We ignore m_returning_call and phi nodes. */
241 gimple *stmt;
242 unsigned i;
243 FOR_EACH_VEC_ELT (snode->m_stmts, i, stmt)
244 {
245 function *fun = snode->get_function ();
246 gcc_assert (fun);
247 function_point point (function_point::before_stmt (supernode: snode, stmt_idx: i));
248 gimple_op_visitor v (this, point, *fun);
249 walk_stmt_load_store_addr_ops (stmt, &v,
250 my_load_cb, my_store_cb, my_addr_cb);
251 }
252 }
253
254 /* Now iterate through the m_decl_map, processing each pair of worklists. */
255 for (state_purge_map::decl_iterator iter = begin_decls ();
256 iter != end_decls ();
257 ++iter)
258 {
259 state_purge_per_decl *per_decl_data = (*iter).second;
260 per_decl_data->process_worklists (map: *this, mgr);
261 }
262}
263
264/* state_purge_map's dtor. */
265
266state_purge_map::~state_purge_map ()
267{
268 for (auto iter : m_ssa_map)
269 delete iter.second;
270 for (auto iter : m_decl_map)
271 delete iter.second;
272}
273
274/* Get the state_purge_per_decl for local DECL within FUN, creating it
275 if necessary. */
276
277state_purge_per_decl &
278state_purge_map::get_or_create_data_for_decl (const function &fun, tree decl)
279{
280 if (state_purge_per_decl **slot
281 = const_cast <decl_map_t&> (m_decl_map).get (k: decl))
282 return **slot;
283 state_purge_per_decl *result = new state_purge_per_decl (*this, decl, fun);
284 m_decl_map.put (k: decl, v: result);
285 return *result;
286}
287
288/* class state_purge_per_ssa_name : public state_purge_per_tree. */
289
290/* state_purge_per_ssa_name's ctor.
291
292 Locate all uses of VAR within FUN.
293 Walk backwards from each use, marking program points, until
294 we reach the def stmt, populating m_points_needing_var.
295
296 We have to track program points rather than
297 just stmts since there could be empty basic blocks on the way. */
298
299state_purge_per_ssa_name::state_purge_per_ssa_name (const state_purge_map &map,
300 tree name,
301 const function &fun)
302: state_purge_per_tree (fun), m_points_needing_name (), m_name (name)
303{
304 LOG_FUNC (map.get_logger ());
305
306 if (map.get_logger ())
307 {
308 map.log (fmt: "SSA name: %qE within %qD", name, fun.decl);
309
310 /* Show def stmt. */
311 const gimple *def_stmt = SSA_NAME_DEF_STMT (name);
312 pretty_printer pp;
313 pp_gimple_stmt_1 (&pp, def_stmt, 0, (dump_flags_t)0);
314 map.log (fmt: "def stmt: %s", pp_formatted_text (&pp));
315 }
316
317 auto_vec<function_point> worklist;
318
319 /* Add all immediate uses of name to the worklist.
320 Compare with debug_immediate_uses. */
321 imm_use_iterator iter;
322 use_operand_p use_p;
323 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
324 {
325 if (USE_STMT (use_p))
326 {
327 const gimple *use_stmt = USE_STMT (use_p);
328 if (map.get_logger ())
329 {
330 pretty_printer pp;
331 pp_gimple_stmt_1 (&pp, use_stmt, 0, (dump_flags_t)0);
332 map.log (fmt: "used by stmt: %s", pp_formatted_text (&pp));
333 }
334
335 if (is_gimple_debug (gs: use_stmt))
336 {
337 /* We skipped debug stmts when building the supergraph,
338 so ignore them now. */
339 if (map.get_logger ())
340 map.log (fmt: "skipping debug stmt");
341 continue;
342 }
343
344 const supernode *snode
345 = map.get_sg ().get_supernode_for_stmt (stmt: use_stmt);
346
347 /* If it's a use within a phi node, then we care about
348 which in-edge we came from. */
349 if (use_stmt->code == GIMPLE_PHI)
350 {
351 for (gphi_iterator gpi
352 = const_cast<supernode *> (snode)->start_phis ();
353 !gsi_end_p (i: gpi); gsi_next (i: &gpi))
354 {
355 gphi *phi = gpi.phi ();
356 if (phi == use_stmt)
357 {
358 /* Find arguments (and thus in-edges) which use NAME. */
359 for (unsigned arg_idx = 0;
360 arg_idx < gimple_phi_num_args (gs: phi);
361 ++arg_idx)
362 {
363 if (name == gimple_phi_arg (gs: phi, index: arg_idx)->def)
364 {
365 edge in_edge = gimple_phi_arg_edge (phi, i: arg_idx);
366 const superedge *in_sedge
367 = map.get_sg ().get_edge_for_cfg_edge (e: in_edge);
368 function_point point
369 = function_point::before_supernode
370 (supernode: snode, from_edge: in_sedge);
371 add_to_worklist (point, worklist: &worklist,
372 logger: map.get_logger ());
373 m_points_needing_name.add (k: point);
374 }
375 }
376 }
377 }
378 }
379 else
380 {
381 function_point point = before_use_stmt (map, use_stmt);
382 add_to_worklist (point, worklist: &worklist, logger: map.get_logger ());
383 m_points_needing_name.add (k: point);
384
385 /* We also need to add uses for conditionals and switches,
386 where the stmt "happens" at the after_supernode, for filtering
387 the out-edges. */
388 if (use_stmt == snode->get_last_stmt ())
389 {
390 if (map.get_logger ())
391 map.log (fmt: "last stmt in BB");
392 function_point point
393 = function_point::after_supernode (supernode: snode);
394 add_to_worklist (point, worklist: &worklist, logger: map.get_logger ());
395 m_points_needing_name.add (k: point);
396 }
397 else
398 if (map.get_logger ())
399 map.log (fmt: "not last stmt in BB");
400 }
401 }
402 }
403
404 /* Process worklist by walking backwards until we reach the def stmt. */
405 {
406 log_scope s (map.get_logger (), "processing worklist");
407 while (worklist.length () > 0)
408 {
409 function_point point = worklist.pop ();
410 process_point (point, worklist: &worklist, map);
411 }
412 }
413
414 if (map.get_logger ())
415 {
416 map.log (fmt: "%qE in %qD is needed to process:", name, fun.decl);
417 /* Log m_points_needing_name, sorting it to avoid churn when comparing
418 dumps. */
419 auto_vec<function_point> points;
420 for (point_set_t::iterator iter = m_points_needing_name.begin ();
421 iter != m_points_needing_name.end ();
422 ++iter)
423 points.safe_push (obj: *iter);
424 points.qsort (function_point::cmp_ptr);
425 unsigned i;
426 function_point *point;
427 FOR_EACH_VEC_ELT (points, i, point)
428 {
429 map.start_log_line ();
430 map.get_logger ()->log_partial (fmt: " point: ");
431 point->print (pp: map.get_logger ()->get_printer (), f: format (false));
432 map.end_log_line ();
433 }
434 }
435}
436
437/* Return true if the SSA name is needed at POINT. */
438
439bool
440state_purge_per_ssa_name::needed_at_point_p (const function_point &point) const
441{
442 return const_cast <point_set_t &> (m_points_needing_name).contains (k: point);
443}
444
445/* Get the function_point representing immediately before USE_STMT.
446 Subroutine of ctor. */
447
448function_point
449state_purge_per_ssa_name::before_use_stmt (const state_purge_map &map,
450 const gimple *use_stmt)
451{
452 gcc_assert (use_stmt->code != GIMPLE_PHI);
453
454 const supernode *supernode
455 = map.get_sg ().get_supernode_for_stmt (stmt: use_stmt);
456 unsigned int stmt_idx = supernode->get_stmt_index (stmt: use_stmt);
457 return function_point::before_stmt (supernode, stmt_idx);
458}
459
460/* Add POINT to *WORKLIST if the point has not already been seen.
461 Subroutine of ctor. */
462
463void
464state_purge_per_ssa_name::add_to_worklist (const function_point &point,
465 auto_vec<function_point> *worklist,
466 logger *logger)
467{
468 LOG_FUNC (logger);
469 if (logger)
470 {
471 logger->start_log_line ();
472 logger->log_partial (fmt: "point: '");
473 point.print (pp: logger->get_printer (), f: format (false));
474 logger->log_partial (fmt: "' for worklist for %qE", m_name);
475 logger->end_log_line ();
476 }
477
478 gcc_assert (point.get_function () == &get_function ());
479 if (point.get_from_edge ())
480 gcc_assert (point.get_from_edge ()->get_kind () == SUPEREDGE_CFG_EDGE);
481
482 if (m_points_needing_name.contains (k: point))
483 {
484 if (logger)
485 logger->log (fmt: "already seen for %qE", m_name);
486 }
487 else
488 {
489 if (logger)
490 logger->log (fmt: "not seen; adding to worklist for %qE", m_name);
491 m_points_needing_name.add (k: point);
492 worklist->safe_push (obj: point);
493 }
494}
495
496/* Return true iff NAME is used by any of the phi nodes in SNODE
497 when processing the in-edge with PHI_ARG_IDX. */
498
499static bool
500name_used_by_phis_p (tree name, const supernode *snode,
501 size_t phi_arg_idx)
502{
503 gcc_assert (TREE_CODE (name) == SSA_NAME);
504
505 for (gphi_iterator gpi
506 = const_cast<supernode *> (snode)->start_phis ();
507 !gsi_end_p (i: gpi); gsi_next (i: &gpi))
508 {
509 gphi *phi = gpi.phi ();
510 if (gimple_phi_arg_def (gs: phi, index: phi_arg_idx) == name)
511 return true;
512 }
513 return false;
514}
515
516/* Process POINT, popped from WORKLIST.
517 Iterate over predecessors of POINT, adding to WORKLIST. */
518
519void
520state_purge_per_ssa_name::process_point (const function_point &point,
521 auto_vec<function_point> *worklist,
522 const state_purge_map &map)
523{
524 logger *logger = map.get_logger ();
525 LOG_FUNC (logger);
526 if (logger)
527 {
528 logger->start_log_line ();
529 logger->log_partial (fmt: "considering point: '");
530 point.print (pp: logger->get_printer (), f: format (false));
531 logger->log_partial (fmt: "' for %qE", m_name);
532 logger->end_log_line ();
533 }
534
535 gimple *def_stmt = SSA_NAME_DEF_STMT (m_name);
536
537 const supernode *snode = point.get_supernode ();
538
539 switch (point.get_kind ())
540 {
541 default:
542 gcc_unreachable ();
543
544 case PK_ORIGIN:
545 break;
546
547 case PK_BEFORE_SUPERNODE:
548 {
549 for (gphi_iterator gpi
550 = const_cast<supernode *> (snode)->start_phis ();
551 !gsi_end_p (i: gpi); gsi_next (i: &gpi))
552 {
553 gcc_assert (point.get_from_edge ());
554 const cfg_superedge *cfg_sedge
555 = point.get_from_edge ()->dyn_cast_cfg_superedge ();
556 gcc_assert (cfg_sedge);
557
558 gphi *phi = gpi.phi ();
559 /* Are we at the def-stmt for m_name? */
560 if (phi == def_stmt)
561 {
562 if (name_used_by_phis_p (name: m_name, snode,
563 phi_arg_idx: cfg_sedge->get_phi_arg_idx ()))
564 {
565 if (logger)
566 logger->log (fmt: "name in def stmt used within phis;"
567 " continuing");
568 }
569 else
570 {
571 if (logger)
572 logger->log (fmt: "name in def stmt not used within phis;"
573 " terminating");
574 return;
575 }
576 }
577 }
578
579 /* Add given pred to worklist. */
580 if (point.get_from_edge ())
581 {
582 gcc_assert (point.get_from_edge ()->m_src);
583 add_to_worklist
584 (point: function_point::after_supernode (supernode: point.get_from_edge ()->m_src),
585 worklist, logger);
586 }
587 else
588 {
589 /* Add any intraprocedually edge for a call. */
590 if (snode->m_returning_call)
591 {
592 gcall *returning_call = snode->m_returning_call;
593 cgraph_edge *cedge
594 = supergraph_call_edge (fun: snode->m_fun,
595 stmt: returning_call);
596 if(cedge)
597 {
598 superedge *sedge
599 = map.get_sg ().get_intraprocedural_edge_for_call (edge: cedge);
600 gcc_assert (sedge);
601 add_to_worklist
602 (point: function_point::after_supernode (supernode: sedge->m_src),
603 worklist, logger);
604 }
605 else
606 {
607 supernode *callernode
608 = map.get_sg ().get_supernode_for_stmt (stmt: returning_call);
609
610 gcc_assert (callernode);
611 add_to_worklist
612 (point: function_point::after_supernode (supernode: callernode),
613 worklist, logger);
614 }
615 }
616 }
617 }
618 break;
619
620 case PK_BEFORE_STMT:
621 {
622 if (def_stmt == point.get_stmt ())
623 {
624 if (logger)
625 logger->log (fmt: "def stmt; terminating");
626 return;
627 }
628 if (point.get_stmt_idx () > 0)
629 add_to_worklist (point: function_point::before_stmt
630 (supernode: snode, stmt_idx: point.get_stmt_idx () - 1),
631 worklist, logger);
632 else
633 {
634 /* Add before_supernode to worklist. This captures the in-edge,
635 so we have to do it once per in-edge. */
636 unsigned i;
637 superedge *pred;
638 FOR_EACH_VEC_ELT (snode->m_preds, i, pred)
639 add_to_worklist (point: function_point::before_supernode (supernode: snode,
640 from_edge: pred),
641 worklist, logger);
642 }
643 }
644 break;
645
646 case PK_AFTER_SUPERNODE:
647 {
648 if (snode->m_stmts.length ())
649 add_to_worklist
650 (point: function_point::before_stmt (supernode: snode,
651 stmt_idx: snode->m_stmts.length () - 1),
652 worklist, logger);
653 else
654 {
655 /* Add before_supernode to worklist. This captures the in-edge,
656 so we have to do it once per in-edge. */
657 unsigned i;
658 superedge *pred;
659 FOR_EACH_VEC_ELT (snode->m_preds, i, pred)
660 add_to_worklist (point: function_point::before_supernode (supernode: snode,
661 from_edge: pred),
662 worklist, logger);
663 /* If it's the initial BB, add it, to ensure that we
664 have "before supernode" for the initial ENTRY block, and don't
665 erroneously purge SSA names for initial values of parameters. */
666 if (snode->entry_p ())
667 {
668 add_to_worklist
669 (point: function_point::before_supernode (supernode: snode, NULL),
670 worklist, logger);
671 }
672 }
673 }
674 break;
675 }
676}
677
678/* class state_purge_per_decl : public state_purge_per_tree. */
679
680/* state_purge_per_decl's ctor. */
681
682state_purge_per_decl::state_purge_per_decl (const state_purge_map &map,
683 tree decl,
684 const function &fun)
685: state_purge_per_tree (fun),
686 m_decl (decl)
687{
688 /* The RESULT_DECL is always needed at the end of its function. */
689 if (TREE_CODE (decl) == RESULT_DECL)
690 {
691 supernode *exit_snode = map.get_sg ().get_node_for_function_exit (fun);
692 add_needed_at (point: function_point::after_supernode (supernode: exit_snode));
693 }
694}
695
696/* Mark the value of the decl (or a subvalue within it) as being needed
697 at POINT. */
698
699void
700state_purge_per_decl::add_needed_at (const function_point &point)
701{
702 m_points_needing_decl.add (k: point);
703}
704
705/* Mark that a pointer to the decl (or a region within it) is taken
706 at POINT. */
707
708void
709state_purge_per_decl::add_pointed_to_at (const function_point &point)
710{
711 m_points_taking_address.add (k: point);
712}
713
714/* Process the worklists for this decl:
715 (a) walk backwards from points where we know the value of the decl
716 is needed, marking points until we get to a stmt that fully overwrites
717 the decl.
718 (b) walk forwards from points where the address of the decl is taken,
719 marking points as potentially needing the value of the decl. */
720
721void
722state_purge_per_decl::process_worklists (const state_purge_map &map,
723 region_model_manager *mgr)
724{
725 logger *logger = map.get_logger ();
726 LOG_SCOPE (logger);
727 if (logger)
728 logger->log (fmt: "decl: %qE within %qD", m_decl, get_fndecl ());
729
730 /* Worklist for walking backwards from uses. */
731 {
732 auto_vec<function_point> worklist;
733 point_set_t seen;
734
735 /* Add all uses of the decl to the worklist. */
736 for (auto iter : m_points_needing_decl)
737 worklist.safe_push (obj: iter);
738
739 region_model model (mgr);
740 model.push_frame (fun: get_function (), NULL, NULL);
741
742 /* Process worklist by walking backwards until we reach a stmt
743 that fully overwrites the decl. */
744 {
745 log_scope s (logger, "processing worklist");
746 while (worklist.length () > 0)
747 {
748 function_point point = worklist.pop ();
749 process_point_backwards (point, worklist: &worklist, seen: &seen, map, model);
750 }
751 }
752 }
753
754 /* Worklist for walking forwards from address-taken points. */
755 {
756 auto_vec<function_point> worklist;
757 point_set_t seen;
758
759 /* Add all uses of the decl to the worklist. */
760 for (auto iter : m_points_taking_address)
761 {
762 worklist.safe_push (obj: iter);
763
764 /* Add to m_points_needing_decl (now that we traversed
765 it above for the backward worklist). */
766 m_points_needing_decl.add (k: iter);
767 }
768
769 /* Process worklist by walking forwards. */
770 {
771 log_scope s (logger, "processing worklist");
772 while (worklist.length () > 0)
773 {
774 function_point point = worklist.pop ();
775 process_point_forwards (point, worklist: &worklist, seen: &seen, map);
776 }
777 }
778 }
779}
780
781/* Add POINT to *WORKLIST if the point is not already in *seen.
782 Add newly seen points to *SEEN and to m_points_needing_name. */
783
784void
785state_purge_per_decl::add_to_worklist (const function_point &point,
786 auto_vec<function_point> *worklist,
787 point_set_t *seen,
788 logger *logger)
789{
790 LOG_FUNC (logger);
791 if (logger)
792 {
793 logger->start_log_line ();
794 logger->log_partial (fmt: "point: '");
795 point.print (pp: logger->get_printer (), f: format (false));
796 logger->log_partial (fmt: "' for worklist for %qE", m_decl);
797 logger->end_log_line ();
798 }
799
800 gcc_assert (point.get_function () == &get_function ());
801 if (point.get_from_edge ())
802 gcc_assert (point.get_from_edge ()->get_kind () == SUPEREDGE_CFG_EDGE);
803
804 if (seen->contains (k: point))
805 {
806 if (logger)
807 logger->log (fmt: "already seen for %qE", m_decl);
808 }
809 else
810 {
811 if (logger)
812 logger->log (fmt: "not seen; adding to worklist for %qE", m_decl);
813 m_points_needing_decl.add (k: point);
814 seen->add (k: point);
815 worklist->safe_push (obj: point);
816 }
817}
818
819/* Determine if REG_A and REG_B express writing to exactly the same
820 set of bits.
821 For example, when "s.field" is the only field of "s", and there's no
822 padding, this should return true. */
823
824static bool
825same_binding_p (const region *reg_a, const region *reg_b,
826 store_manager *store_mgr)
827{
828 if (reg_a->get_base_region () != reg_b->get_base_region ())
829 return false;
830 if (reg_a->empty_p ())
831 return false;
832 const binding_key *bind_key_a = binding_key::make (mgr: store_mgr, r: reg_a);
833 if (reg_b->empty_p ())
834 return false;
835 const binding_key *bind_key_b = binding_key::make (mgr: store_mgr, r: reg_b);
836 return bind_key_a == bind_key_b;
837}
838
839/* Return true if STMT fully overwrites DECL. */
840
841static bool
842fully_overwrites_p (const gimple *stmt, tree decl,
843 const region_model &model)
844{
845 if (tree lhs = gimple_get_lhs (stmt))
846 {
847 /* Determine if LHS fully overwrites DECL.
848 We can't just check for equality; consider the case of
849 "s.field = EXPR;" where the stmt writes to the only field
850 of "s", and there's no padding. */
851 const region *lhs_reg = model.get_lvalue (expr: lhs, NULL);
852 const region *decl_reg = model.get_lvalue (expr: decl, NULL);
853 if (same_binding_p (reg_a: lhs_reg, reg_b: decl_reg,
854 store_mgr: model.get_manager ()->get_store_manager ()))
855 return true;
856 }
857 return false;
858}
859
860/* Process POINT, popped from *WORKLIST.
861 Iterate over predecessors of POINT, adding to *WORKLIST and *SEEN,
862 until we get to a stmt that fully overwrites the decl. */
863
864void
865state_purge_per_decl::
866process_point_backwards (const function_point &point,
867 auto_vec<function_point> *worklist,
868 point_set_t *seen,
869 const state_purge_map &map,
870 const region_model &model)
871{
872 logger *logger = map.get_logger ();
873 LOG_FUNC (logger);
874 if (logger)
875 {
876 logger->start_log_line ();
877 logger->log_partial (fmt: "considering point: '");
878 point.print (pp: logger->get_printer (), f: format (false));
879 logger->log_partial (fmt: "' for %qE", m_decl);
880 logger->end_log_line ();
881 }
882 const supernode *snode = point.get_supernode ();
883
884 switch (point.get_kind ())
885 {
886 default:
887 gcc_unreachable ();
888
889 case PK_ORIGIN:
890 break;
891
892 case PK_BEFORE_SUPERNODE:
893 {
894 /* Add given pred to worklist. */
895 if (point.get_from_edge ())
896 {
897 gcc_assert (point.get_from_edge ()->m_src);
898 add_to_worklist
899 (point: function_point::after_supernode (supernode: point.get_from_edge ()->m_src),
900 worklist, seen, logger);
901 }
902 else
903 {
904 /* Add any intraprocedually edge for a call. */
905 if (snode->m_returning_call)
906 {
907 gcall *returning_call = snode->m_returning_call;
908 cgraph_edge *cedge
909 = supergraph_call_edge (fun: snode->m_fun,
910 stmt: returning_call);
911 if(cedge)
912 {
913 superedge *sedge
914 = map.get_sg ().get_intraprocedural_edge_for_call (edge: cedge);
915 gcc_assert (sedge);
916 add_to_worklist
917 (point: function_point::after_supernode (supernode: sedge->m_src),
918 worklist, seen, logger);
919 }
920 else
921 {
922 supernode *callernode
923 = map.get_sg ().get_supernode_for_stmt (stmt: returning_call);
924
925 gcc_assert (callernode);
926 add_to_worklist
927 (point: function_point::after_supernode (supernode: callernode),
928 worklist, seen, logger);
929 }
930 }
931 }
932 }
933 break;
934
935 case PK_BEFORE_STMT:
936 {
937 /* This is somewhat equivalent to how the SSA case handles
938 def-stmts. */
939 if (fully_overwrites_p (stmt: point.get_stmt (), decl: m_decl, model)
940 /* ...but we mustn't be at a point that also consumes the
941 current value of the decl when it's generating the new
942 value, for cases such as
943 struct st s;
944 s = foo ();
945 s = bar (s);
946 where we want to make sure that we don't stop at the:
947 s = bar (s);
948 since otherwise we would erroneously purge the state of "s"
949 after:
950 s = foo ();
951 */
952 && !m_points_needing_decl.contains (k: point))
953 {
954 if (logger)
955 logger->log (fmt: "stmt fully overwrites %qE; terminating", m_decl);
956 return;
957 }
958 if (point.get_stmt_idx () > 0)
959 add_to_worklist (point: function_point::before_stmt
960 (supernode: snode, stmt_idx: point.get_stmt_idx () - 1),
961 worklist, seen, logger);
962 else
963 {
964 /* Add before_supernode to worklist. This captures the in-edge,
965 so we have to do it once per in-edge. */
966 unsigned i;
967 superedge *pred;
968 FOR_EACH_VEC_ELT (snode->m_preds, i, pred)
969 add_to_worklist (point: function_point::before_supernode (supernode: snode,
970 from_edge: pred),
971 worklist, seen, logger);
972 }
973 }
974 break;
975
976 case PK_AFTER_SUPERNODE:
977 {
978 if (snode->m_stmts.length ())
979 add_to_worklist
980 (point: function_point::before_stmt (supernode: snode,
981 stmt_idx: snode->m_stmts.length () - 1),
982 worklist, seen, logger);
983 else
984 {
985 /* Add before_supernode to worklist. This captures the in-edge,
986 so we have to do it once per in-edge. */
987 unsigned i;
988 superedge *pred;
989 FOR_EACH_VEC_ELT (snode->m_preds, i, pred)
990 add_to_worklist (point: function_point::before_supernode (supernode: snode,
991 from_edge: pred),
992 worklist, seen, logger);
993 }
994 }
995 break;
996 }
997
998}
999
1000/* Process POINT, popped from *WORKLIST.
1001 Iterate over successors of POINT, adding to *WORKLIST and *SEEN. */
1002
1003void
1004state_purge_per_decl::
1005process_point_forwards (const function_point &point,
1006 auto_vec<function_point> *worklist,
1007 point_set_t *seen,
1008 const state_purge_map &map)
1009{
1010 logger *logger = map.get_logger ();
1011 LOG_FUNC (logger);
1012 if (logger)
1013 {
1014 logger->start_log_line ();
1015 logger->log_partial (fmt: "considering point: '");
1016 point.print (pp: logger->get_printer (), f: format (false));
1017 logger->log_partial (fmt: "' for %qE", m_decl);
1018 logger->end_log_line ();
1019 }
1020 const supernode *snode = point.get_supernode ();
1021
1022 switch (point.get_kind ())
1023 {
1024 default:
1025 case PK_ORIGIN:
1026 gcc_unreachable ();
1027
1028 case PK_BEFORE_SUPERNODE:
1029 {
1030 function_point next = point.get_next ();
1031 add_to_worklist (point: next, worklist, seen, logger);
1032 }
1033 break;
1034
1035 case PK_BEFORE_STMT:
1036 {
1037 /* Perhaps we should stop at a clobber of the decl,
1038 but that ought to purge state for us explicitly. */
1039 function_point next = point.get_next ();
1040 add_to_worklist (point: next, worklist, seen, logger);
1041 }
1042 break;
1043
1044 case PK_AFTER_SUPERNODE:
1045 {
1046 /* Look at interprocedural out-edges. */
1047 unsigned i;
1048 superedge *succ;
1049 FOR_EACH_VEC_ELT (snode->m_succs, i, succ)
1050 {
1051 enum edge_kind kind = succ->get_kind ();
1052 if (kind == SUPEREDGE_CFG_EDGE
1053 || kind == SUPEREDGE_INTRAPROCEDURAL_CALL)
1054 add_to_worklist (point: function_point::before_supernode (supernode: succ->m_dest,
1055 from_edge: succ),
1056 worklist, seen, logger);
1057 }
1058 }
1059 break;
1060 }
1061}
1062
1063/* Return true if the decl is needed at POINT. */
1064
1065bool
1066state_purge_per_decl::needed_at_point_p (const function_point &point) const
1067{
1068 return const_cast <point_set_t &> (m_points_needing_decl).contains (k: point);
1069}
1070
1071/* class state_purge_annotator : public dot_annotator. */
1072
1073/* Implementation of dot_annotator::add_node_annotations vfunc for
1074 state_purge_annotator.
1075
1076 Add an additional record showing which names are purged on entry
1077 to the supernode N. */
1078
1079bool
1080state_purge_annotator::add_node_annotations (graphviz_out *gv,
1081 const supernode &n,
1082 bool within_table) const
1083{
1084 if (m_map == NULL)
1085 return false;
1086
1087 if (within_table)
1088 return false;
1089
1090 pretty_printer *pp = gv->get_pp ();
1091
1092 pp_printf (pp, "annotation_for_node_%i", n.m_index);
1093 pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
1094 "lightblue");
1095 pp_write_text_to_stream (pp);
1096
1097 /* Different in-edges mean different names need purging.
1098 Determine which points to dump. */
1099 auto_vec<function_point> points;
1100 if (n.entry_p () || n.m_returning_call)
1101 points.safe_push (obj: function_point::before_supernode (supernode: &n, NULL));
1102 else
1103 for (auto inedge : n.m_preds)
1104 points.safe_push (obj: function_point::before_supernode (supernode: &n, from_edge: inedge));
1105 points.safe_push (obj: function_point::after_supernode (supernode: &n));
1106
1107 for (auto & point : points)
1108 {
1109 point.print (pp, f: format (true));
1110 pp_newline (pp);
1111 print_needed (gv, point, within_table: false);
1112 pp_newline (pp);
1113 }
1114
1115 pp_string (pp, "\"];\n\n");
1116 pp_flush (pp);
1117 return false;
1118}
1119
1120/* Print V to GV as a comma-separated list in braces, titling it with TITLE.
1121 If WITHIN_TABLE is true, print it within a <TR>
1122
1123 Subroutine of state_purge_annotator::print_needed. */
1124
1125static void
1126print_vec_of_names (graphviz_out *gv, const char *title,
1127 const auto_vec<tree> &v, bool within_table)
1128{
1129 pretty_printer *pp = gv->get_pp ();
1130 tree name;
1131 unsigned i;
1132 if (within_table)
1133 gv->begin_trtd ();
1134 pp_printf (pp, "%s: {", title);
1135 FOR_EACH_VEC_ELT (v, i, name)
1136 {
1137 if (i > 0)
1138 pp_string (pp, ", ");
1139 pp_printf (pp, "%qE", name);
1140 }
1141 pp_printf (pp, "}");
1142 if (within_table)
1143 {
1144 pp_write_text_as_html_like_dot_to_stream (pp);
1145 gv->end_tdtr ();
1146 }
1147 pp_newline (pp);
1148}
1149
1150/* Implementation of dot_annotator::add_stmt_annotations for
1151 state_purge_annotator.
1152
1153 Add text showing which names are purged at STMT. */
1154
1155void
1156state_purge_annotator::add_stmt_annotations (graphviz_out *gv,
1157 const gimple *stmt,
1158 bool within_row) const
1159{
1160 if (within_row)
1161 return;
1162
1163 if (m_map == NULL)
1164 return;
1165
1166 if (stmt->code == GIMPLE_PHI)
1167 return;
1168
1169 pretty_printer *pp = gv->get_pp ();
1170
1171 pp_newline (pp);
1172
1173 const supernode *supernode = m_map->get_sg ().get_supernode_for_stmt (stmt);
1174 unsigned int stmt_idx = supernode->get_stmt_index (stmt);
1175 function_point before_stmt
1176 (function_point::before_stmt (supernode, stmt_idx));
1177
1178 print_needed (gv, point: before_stmt, within_table: true);
1179}
1180
1181/* Get the decls and SSA names needed and not-needed at POINT, and
1182 print them to GV.
1183 If WITHIN_TABLE is true, print them within <TR> elements. */
1184
1185void
1186state_purge_annotator::print_needed (graphviz_out *gv,
1187 const function_point &point,
1188 bool within_table) const
1189{
1190 auto_vec<tree> needed;
1191 auto_vec<tree> not_needed;
1192 for (state_purge_map::ssa_iterator iter = m_map->begin_ssas ();
1193 iter != m_map->end_ssas ();
1194 ++iter)
1195 {
1196 tree name = (*iter).first;
1197 state_purge_per_ssa_name *per_name_data = (*iter).second;
1198 if (&per_name_data->get_function () == point.get_function ())
1199 {
1200 if (per_name_data->needed_at_point_p (point))
1201 needed.safe_push (obj: name);
1202 else
1203 not_needed.safe_push (obj: name);
1204 }
1205 }
1206 for (state_purge_map::decl_iterator iter = m_map->begin_decls ();
1207 iter != m_map->end_decls ();
1208 ++iter)
1209 {
1210 tree decl = (*iter).first;
1211 state_purge_per_decl *per_decl_data = (*iter).second;
1212 if (&per_decl_data->get_function () == point.get_function ())
1213 {
1214 if (per_decl_data->needed_at_point_p (point))
1215 needed.safe_push (obj: decl);
1216 else
1217 not_needed.safe_push (obj: decl);
1218 }
1219 }
1220
1221 print_vec_of_names (gv, title: "needed here", v: needed, within_table);
1222 print_vec_of_names (gv, title: "not needed here", v: not_needed, within_table);
1223}
1224
1225#endif /* #if ENABLE_ANALYZER */
1226

source code of gcc/analyzer/state-purge.cc