Branch data Line data Source code
1 : : /* Classes for purging state at function_points.
2 : : Copyright (C) 2019-2025 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_SET
22 : : #include "analyzer/common.h"
23 : :
24 : : #include "timevar.h"
25 : : #include "gimple-pretty-print.h"
26 : : #include "tree-vrp.h"
27 : : #include "gimple-ssa.h"
28 : : #include "stringpool.h"
29 : : #include "tree-ssanames.h"
30 : : #include "tree-phinodes.h"
31 : : #include "options.h"
32 : : #include "ssa-iterators.h"
33 : : #include "gimple-iterator.h"
34 : : #include "gimple-walk.h"
35 : : #include "cgraph.h"
36 : :
37 : : #include "analyzer/call-string.h"
38 : : #include "analyzer/supergraph.h"
39 : : #include "analyzer/program-point.h"
40 : : #include "analyzer/analyzer-logging.h"
41 : : #include "analyzer/state-purge.h"
42 : : #include "analyzer/store.h"
43 : : #include "analyzer/region-model.h"
44 : :
45 : : #if ENABLE_ANALYZER
46 : :
47 : : /* Given NODE at an access, determine if this access is within
48 : : a decl that could be consider for purging, and if so, return the decl. */
49 : :
50 : : static tree
51 : 38886 : get_candidate_for_purging (tree node)
52 : : {
53 : 38886 : tree iter = node;
54 : 53424 : while (1)
55 : 46155 : switch (TREE_CODE (iter))
56 : : {
57 : : default:
58 : : return NULL_TREE;
59 : :
60 : 7269 : case ADDR_EXPR:
61 : 7269 : case MEM_REF:
62 : 7269 : case COMPONENT_REF:
63 : 7269 : iter = TREE_OPERAND (iter, 0);
64 : 7269 : continue;
65 : :
66 : 25553 : case VAR_DECL:
67 : 25553 : if (is_global_var (iter))
68 : : return NULL_TREE;
69 : : else
70 : : return iter;
71 : :
72 : : case PARM_DECL:
73 : : case RESULT_DECL:
74 : : return iter;
75 : : }
76 : : }
77 : :
78 : : /* Class-based handler for walk_stmt_load_store_addr_ops at a particular
79 : : ana::operation, for populating the worklists within a state_purge_map. */
80 : :
81 : 272080 : class gimple_op_visitor : public log_user
82 : : {
83 : : public:
84 : 136040 : gimple_op_visitor (state_purge_map *map,
85 : : const superedge &sedge)
86 : 136040 : : log_user (map->get_logger ()),
87 : 136040 : m_map (map),
88 : 136040 : m_sedge (sedge),
89 : 136040 : m_fun (sedge.m_src->get_function ())
90 : : {
91 : 136040 : gcc_assert (m_fun);
92 : 136040 : }
93 : :
94 : 14011 : bool on_load (gimple *stmt, tree base, tree op)
95 : : {
96 : 14011 : LOG_FUNC (get_logger ());
97 : 14011 : if (get_logger ())
98 : : {
99 : 4 : pretty_printer pp;
100 : 4 : pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
101 : 4 : log ("on_load: %s; base: %qE, op: %qE",
102 : : pp_formatted_text (&pp), base, op);
103 : 4 : }
104 : 14011 : if (tree node = get_candidate_for_purging (base))
105 : 4116 : add_needed (node);
106 : 28022 : return true;
107 : 14011 : }
108 : :
109 : 10893 : bool on_store (gimple *stmt, tree base, tree op)
110 : : {
111 : 10893 : LOG_FUNC (get_logger ());
112 : 10893 : if (get_logger ())
113 : : {
114 : 1 : pretty_printer pp;
115 : 1 : pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
116 : 1 : log ("on_store: %s; base: %qE, op: %qE",
117 : : pp_formatted_text (&pp), base, op);
118 : 1 : }
119 : 21786 : return true;
120 : 10893 : }
121 : :
122 : 13671 : bool on_addr (gimple *stmt, tree base, tree op)
123 : : {
124 : 13671 : LOG_FUNC (get_logger ());
125 : 13671 : if (get_logger ())
126 : : {
127 : 1 : pretty_printer pp;
128 : 1 : pp_gimple_stmt_1 (&pp, stmt, 0, (dump_flags_t)0);
129 : 1 : log ("on_addr: %s; base: %qE, op: %qE",
130 : : pp_formatted_text (&pp), base, op);
131 : 1 : }
132 : 13671 : if (TREE_CODE (op) != ADDR_EXPR)
133 : : return true;
134 : 13615 : if (tree node = get_candidate_for_purging (base))
135 : : {
136 : 3572 : add_needed (node);
137 : 3572 : add_pointed_to (node);
138 : : }
139 : : return true;
140 : 13671 : }
141 : :
142 : : private:
143 : 7688 : void add_needed (tree decl)
144 : : {
145 : 7688 : gcc_assert (get_candidate_for_purging (decl) == decl);
146 : 7688 : state_purge_per_decl &data
147 : 7688 : = get_or_create_data_for_decl (decl);
148 : 7688 : data.add_needed_at (*m_sedge.m_src);
149 : 7688 : }
150 : :
151 : 3572 : void add_pointed_to (tree decl)
152 : : {
153 : 3572 : gcc_assert (get_candidate_for_purging (decl) == decl);
154 : 3572 : get_or_create_data_for_decl (decl).add_pointed_to_at (*m_sedge.m_src);
155 : 3572 : }
156 : :
157 : : state_purge_per_decl &
158 : 11260 : get_or_create_data_for_decl (tree decl)
159 : : {
160 : 11260 : return m_map->get_or_create_data_for_decl (*m_fun, decl);
161 : : }
162 : :
163 : : state_purge_map *m_map;
164 : : const superedge &m_sedge;
165 : : const function *m_fun;
166 : : };
167 : :
168 : : static bool
169 : 14011 : my_load_cb (gimple *stmt, tree base, tree op, void *user_data)
170 : : {
171 : 14011 : gimple_op_visitor *x = (gimple_op_visitor *)user_data;
172 : 14011 : return x->on_load (stmt, base, op);
173 : : }
174 : :
175 : : static bool
176 : 10893 : my_store_cb (gimple *stmt, tree base, tree op, void *user_data)
177 : : {
178 : 10893 : gimple_op_visitor *x = (gimple_op_visitor *)user_data;
179 : 10893 : return x->on_store (stmt, base, op);
180 : : }
181 : :
182 : : static bool
183 : 13671 : my_addr_cb (gimple *stmt, tree base, tree op, void *user_data)
184 : : {
185 : 13671 : gimple_op_visitor *x = (gimple_op_visitor *)user_data;
186 : 13671 : return x->on_addr (stmt, base, op);
187 : : }
188 : :
189 : : /* state_purge_map's ctor. Walk all SSA names in all functions, building
190 : : a state_purge_per_ssa_name instance for each.
191 : : Also, walk all loads and address-taken ops of local variables, building
192 : : a state_purge_per_decl as appropriate. */
193 : :
194 : 3310 : state_purge_map::state_purge_map (const supergraph &sg,
195 : : region_model_manager *mgr,
196 : 3310 : logger *logger)
197 : 3310 : : log_user (logger), m_sg (sg)
198 : : {
199 : 3310 : LOG_FUNC (logger);
200 : :
201 : 3310 : auto_timevar tv (TV_ANALYZER_STATE_PURGE);
202 : :
203 : 3310 : cgraph_node *node;
204 : 13432 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
205 : : {
206 : 10122 : function *fun = node->get_fun ();
207 : 10122 : gcc_assert (fun);
208 : 10122 : if (logger)
209 : 2 : log ("function: %s", function_name (fun));
210 : : tree name;
211 : : unsigned int i;;
212 : 145418 : FOR_EACH_SSA_NAME (i, name, fun)
213 : : {
214 : : /* For now, don't bother tracking the .MEM SSA names. */
215 : 135260 : if (tree var = SSA_NAME_VAR (name))
216 : 91829 : if (TREE_CODE (var) == VAR_DECL)
217 : 82661 : if (VAR_DECL_IS_VIRTUAL_OPERAND (var))
218 : 63745 : continue;
219 : 71515 : m_ssa_map.put (name, new state_purge_per_ssa_name (*this, name, *fun));
220 : : }
221 : : }
222 : :
223 : : /* Find all uses of local vars.
224 : : We iterate through all operations, finding loads, stores, and
225 : : address-taken operations on locals, building a pair of worklists. */
226 : 196703 : for (auto sedge : sg.m_edges)
227 : : {
228 : 186781 : if (logger)
229 : 37 : log ("edge: SN %i -> SN %i",
230 : 37 : sedge->m_src->m_id,
231 : 37 : sedge->m_dest->m_id);
232 : 186781 : if (auto op = sedge->get_op ())
233 : : {
234 : 136040 : gimple_op_visitor v (this, *sedge);
235 : 136040 : op->walk_load_store_addr_ops (&v,
236 : : my_load_cb, my_store_cb, my_addr_cb);
237 : 136040 : }
238 : : }
239 : :
240 : : /* Now iterate through the m_decl_map, processing each pair of worklists. */
241 : 3310 : for (state_purge_map::decl_iterator iter = begin_decls ();
242 : 10648 : iter != end_decls ();
243 : 3126 : ++iter)
244 : : {
245 : 3126 : state_purge_per_decl *per_decl_data = (*iter).second;
246 : 3126 : per_decl_data->process_worklists (*this, mgr);
247 : : }
248 : 3310 : }
249 : :
250 : : /* state_purge_map's dtor. */
251 : :
252 : 3310 : state_purge_map::~state_purge_map ()
253 : : {
254 : 77844 : for (auto iter : m_ssa_map)
255 : 143030 : delete iter.second;
256 : 7522 : for (auto iter : m_decl_map)
257 : 6252 : delete iter.second;
258 : 3310 : }
259 : :
260 : : /* Get the state_purge_per_decl for local DECL within FUN, creating it
261 : : if necessary. */
262 : :
263 : : state_purge_per_decl &
264 : 11260 : state_purge_map::get_or_create_data_for_decl (const function &fun, tree decl)
265 : : {
266 : 22520 : if (state_purge_per_decl **slot
267 : 11260 : = const_cast <decl_map_t&> (m_decl_map).get (decl))
268 : 8134 : return **slot;
269 : 3126 : state_purge_per_decl *result = new state_purge_per_decl (*this, decl, fun);
270 : 3126 : m_decl_map.put (decl, result);
271 : 3126 : return *result;
272 : : }
273 : :
274 : : void
275 : 0 : state_purge_map::on_duplicated_node (const supernode &old_snode,
276 : : const supernode &new_snode)
277 : : {
278 : 0 : for (auto iter : m_ssa_map)
279 : 0 : iter.second->on_duplicated_node (old_snode, new_snode);
280 : 0 : for (auto iter : m_decl_map)
281 : 0 : iter.second->on_duplicated_node (old_snode, new_snode);
282 : 0 : }
283 : :
284 : : /* class state_purge_per_ssa_name : public state_purge_per_tree. */
285 : :
286 : : /* state_purge_per_ssa_name's ctor.
287 : :
288 : : Locate all uses of VAR within FUN.
289 : : Walk backwards from each use, marking program points, until
290 : : we reach the def stmt, populating m_points_needing_var.
291 : :
292 : : We have to track program points rather than
293 : : just stmts since there could be empty basic blocks on the way. */
294 : :
295 : 71515 : state_purge_per_ssa_name::state_purge_per_ssa_name (const state_purge_map &map,
296 : : tree name,
297 : 71515 : const function &fun)
298 : 71515 : : state_purge_per_tree (fun), m_snodes_needing_name (), m_name (name)
299 : : {
300 : 71515 : LOG_FUNC (map.get_logger ());
301 : :
302 : 71515 : if (map.get_logger ())
303 : : {
304 : 16 : map.log ("SSA name: %qE within %qD", name, fun.decl);
305 : :
306 : : /* Show def stmt. */
307 : 16 : const gimple *def_stmt = SSA_NAME_DEF_STMT (name);
308 : 16 : pretty_printer pp;
309 : 16 : pp_gimple_stmt_1 (&pp, def_stmt, 0, (dump_flags_t)0);
310 : 16 : map.log ("def stmt: %s", pp_formatted_text (&pp));
311 : 16 : }
312 : :
313 : 71515 : auto_vec<const supernode *> worklist;
314 : :
315 : : /* Add all immediate uses of name to the worklist.
316 : : Compare with debug_immediate_uses. */
317 : 71515 : imm_use_iterator iter;
318 : 71515 : use_operand_p use_p;
319 : 235086 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
320 : : {
321 : 92056 : if (USE_STMT (use_p))
322 : : {
323 : 92056 : const gimple *use_stmt = USE_STMT (use_p);
324 : 92056 : if (map.get_logger ())
325 : : {
326 : 22 : pretty_printer pp;
327 : 22 : pp_gimple_stmt_1 (&pp, use_stmt, 0, (dump_flags_t)0);
328 : 22 : map.log ("used by stmt: %s", pp_formatted_text (&pp));
329 : 22 : }
330 : :
331 : 92056 : if (is_gimple_debug (use_stmt))
332 : : {
333 : : /* We skipped debug stmts when building the supergraph,
334 : : so ignore them now. */
335 : 276 : if (map.get_logger ())
336 : 0 : map.log ("skipping debug stmt");
337 : 276 : continue;
338 : : }
339 : :
340 : : /* If it's a use within a phi node, then we care about
341 : : which in-edge we came from. */
342 : 91780 : if (use_stmt->code == GIMPLE_PHI)
343 : : {
344 : 8928 : const gphi *phi = as_a <const gphi *> (use_stmt);
345 : : /* Find arguments (and thus CFG in-edges) which use NAME. */
346 : 34812 : for (unsigned arg_idx = 0;
347 : 34812 : arg_idx < gimple_phi_num_args (phi);
348 : : ++arg_idx)
349 : : {
350 : 25884 : if (name == gimple_phi_arg (phi, arg_idx)->def)
351 : : {
352 : 10578 : edge in_edge = gimple_phi_arg_edge (phi, arg_idx);
353 : 10578 : const superedge *in_sedge
354 : 10578 : = map.get_sg ().get_superedge_for_phis (in_edge);
355 : 10578 : if (in_sedge)
356 : : {
357 : 10512 : add_to_worklist (*in_sedge->m_src,
358 : : &worklist,
359 : : map.get_logger ());
360 : 10512 : m_snodes_needing_name.add (in_sedge->m_src);
361 : : }
362 : : else
363 : : {
364 : : /* Should only happen for abnormal edges, which
365 : : get skipped in supergraph construction. */
366 : 66 : gcc_assert (in_edge->flags & EDGE_ABNORMAL);
367 : : }
368 : : }
369 : : }
370 : : }
371 : : else
372 : : {
373 : 82852 : const supernode *snode
374 : 82852 : = map.get_sg ().get_supernode_for_stmt (use_stmt);
375 : 82852 : add_to_worklist (*snode, &worklist, map.get_logger ());
376 : 82852 : m_snodes_needing_name.add (snode);
377 : : }
378 : : }
379 : 71515 : }
380 : :
381 : : /* Process worklist by walking backwards until we reach the def stmt. */
382 : 71515 : {
383 : 71515 : log_scope s (map.get_logger (), "processing worklist");
384 : 414012 : while (worklist.length () > 0)
385 : : {
386 : 270982 : const supernode *snode = worklist.pop ();
387 : 270982 : gcc_assert (snode);
388 : 270982 : process_supernode (*snode, &worklist, map);
389 : : }
390 : 71515 : }
391 : :
392 : 71515 : if (map.get_logger ())
393 : : {
394 : 16 : map.log ("%qE in %qD is needed to process:", name, fun.decl);
395 : : /* Log m_snodes_needing_name, sorting it to avoid churn when comparing
396 : : dumps. */
397 : 16 : std::set<int> indices;
398 : 16 : auto_vec<const supernode *> snodes;
399 : 82 : for (auto iter : m_snodes_needing_name)
400 : 66 : indices.insert (iter->m_id);
401 : 82 : for (auto iter : indices)
402 : 66 : map.get_logger ()->log (" SN %i", iter);
403 : 16 : }
404 : 71515 : }
405 : :
406 : : /* Return true if the SSA name is needed at POINT. */
407 : :
408 : : bool
409 : 1220742 : state_purge_per_ssa_name::needed_at_supernode_p (const supernode *snode) const
410 : : {
411 : 1220742 : return const_cast <point_set_t &> (m_snodes_needing_name).contains (snode);
412 : : }
413 : :
414 : : /* Add SNODE to *WORKLIST if the supernode has not already been seen.
415 : : Subroutine of ctor. */
416 : :
417 : : void
418 : 304354 : state_purge_per_ssa_name::add_to_worklist (const supernode &snode,
419 : : auto_vec<const supernode *> *worklist,
420 : : logger *logger)
421 : : {
422 : 304354 : LOG_FUNC (logger);
423 : :
424 : 304354 : gcc_assert (snode.get_function () == &get_function ());
425 : :
426 : 304354 : if (m_snodes_needing_name.contains (&snode))
427 : : {
428 : 33372 : if (logger)
429 : 8 : logger->log ("SN %i already seen for %qE", snode.m_id, m_name);
430 : : }
431 : : else
432 : : {
433 : 270982 : if (logger)
434 : 66 : logger->log ("not seen; adding SN %i to worklist for %qE",
435 : 66 : snode.m_id, m_name);
436 : 270982 : m_snodes_needing_name.add (&snode);
437 : 270982 : worklist->safe_push (&snode);
438 : : }
439 : 304354 : }
440 : :
441 : : /* Process SNODE, popped from WORKLIST.
442 : : Iterate over predecessors of SNODE, adding to WORKLIST. */
443 : :
444 : : void
445 : 270982 : state_purge_per_ssa_name::process_supernode (const supernode &snode,
446 : : auto_vec<const supernode *> *worklist,
447 : : const state_purge_map &map)
448 : : {
449 : 270982 : logger *logger = map.get_logger ();
450 : 270982 : LOG_FUNC (logger);
451 : 270982 : if (logger)
452 : 66 : logger->log ("considering SN %i for %qE", snode.m_id, m_name);
453 : :
454 : 1072876 : for (auto in_edge : snode.m_preds)
455 : : {
456 : 277452 : if (logger)
457 : 70 : logger->log ("considering edge from SN %i", in_edge->m_src->m_id);
458 : 277452 : bool defines_ssa_name = false;
459 : 277452 : if (auto op = in_edge->get_op ())
460 : 230461 : if (op->defines_ssa_name_p (m_name))
461 : 66462 : defines_ssa_name = true;
462 : 66462 : if (defines_ssa_name)
463 : : {
464 : 66462 : if (logger)
465 : 18 : logger->log ("op defines %qE", m_name);
466 : : }
467 : : else
468 : 210990 : add_to_worklist (*in_edge->m_src, worklist, logger);
469 : : }
470 : 270982 : }
471 : :
472 : : void
473 : 0 : state_purge_per_ssa_name::on_duplicated_node (const supernode &old_snode,
474 : : const supernode &new_snode)
475 : : {
476 : 0 : if (m_snodes_needing_name.contains (&old_snode))
477 : 0 : m_snodes_needing_name.add (&new_snode);
478 : 0 : }
479 : :
480 : : /* class state_purge_per_decl : public state_purge_per_tree. */
481 : :
482 : : /* state_purge_per_decl's ctor. */
483 : :
484 : 3126 : state_purge_per_decl::state_purge_per_decl (const state_purge_map &map,
485 : : tree decl,
486 : 3126 : const function &fun)
487 : : : state_purge_per_tree (fun),
488 : 3126 : m_decl (decl)
489 : : {
490 : : /* The RESULT_DECL is always needed at the end of its function. */
491 : 3126 : if (TREE_CODE (decl) == RESULT_DECL)
492 : : {
493 : 34 : supernode *exit_snode = map.get_sg ().get_node_for_function_exit (fun);
494 : 34 : add_needed_at (*exit_snode);
495 : : }
496 : 3126 : }
497 : :
498 : : /* Mark the value of the decl (or a subvalue within it) as being needed
499 : : at SNODE. */
500 : :
501 : : void
502 : 7722 : state_purge_per_decl::add_needed_at (const supernode &snode)
503 : : {
504 : 7722 : m_snodes_needing_decl.add (&snode);
505 : 7722 : }
506 : :
507 : : /* Mark that a pointer to the decl (or a region within it) is taken
508 : : at SNODE. */
509 : :
510 : : void
511 : 3572 : state_purge_per_decl::add_pointed_to_at (const supernode &snode)
512 : : {
513 : 3572 : m_snodes_taking_address.add (&snode);
514 : 3572 : }
515 : :
516 : : /* Process the worklists for this decl:
517 : : (a) walk backwards from snodes where we know the value of the decl
518 : : is needed, marking snodes until we get to a stmt that fully overwrites
519 : : the decl.
520 : : (b) walk forwards from snodes where the address of the decl is taken,
521 : : marking snodes as potentially needing the value of the decl. */
522 : :
523 : : void
524 : 3126 : state_purge_per_decl::process_worklists (const state_purge_map &map,
525 : : region_model_manager *mgr)
526 : : {
527 : 3126 : logger *logger = map.get_logger ();
528 : 3126 : LOG_SCOPE (logger);
529 : 3126 : if (logger)
530 : 0 : logger->log ("decl: %qE within %qD", m_decl, get_fndecl ());
531 : :
532 : : /* Worklist for walking backwards from uses. */
533 : 3126 : {
534 : 3126 : auto_vec<const supernode *> worklist;
535 : 3126 : point_set_t seen;
536 : :
537 : : /* Add all uses of the decl to the worklist. */
538 : 10806 : for (auto iter : m_snodes_needing_decl)
539 : 7680 : worklist.safe_push (iter);
540 : :
541 : 3126 : region_model model (mgr);
542 : 3126 : model.push_frame (get_function (), nullptr, nullptr, nullptr);
543 : :
544 : : /* Process worklist by walking backwards until we reach a stmt
545 : : that fully overwrites the decl. */
546 : 3126 : {
547 : 3126 : log_scope s (logger, "processing worklist");
548 : 60220 : while (worklist.length () > 0)
549 : : {
550 : 53968 : const supernode *snode = worklist.pop ();
551 : 53968 : process_supernode_backwards (*snode, &worklist, &seen, map, model);
552 : : }
553 : 3126 : }
554 : 3126 : }
555 : :
556 : : /* Worklist for walking forwards from address-taken snodes. */
557 : 3126 : {
558 : 3126 : auto_vec<const supernode *> worklist;
559 : 3126 : point_set_t seen;
560 : :
561 : : /* Add all uses of the decl to the worklist. */
562 : 10214 : for (auto iter : m_snodes_taking_address)
563 : : {
564 : 3544 : worklist.safe_push (iter);
565 : :
566 : : /* Add to m_snodes_needing_decl (now that we traversed
567 : : it above for the backward worklist). */
568 : 3544 : m_snodes_needing_decl.add (iter);
569 : : }
570 : :
571 : : /* Process worklist by walking forwards. */
572 : 3126 : {
573 : 3126 : log_scope s (logger, "processing worklist");
574 : 56180 : while (worklist.length () > 0)
575 : : {
576 : 49928 : const supernode *snode = worklist.pop ();
577 : 49928 : process_supernode_forwards (*snode, &worklist, &seen, map);
578 : : }
579 : 3126 : }
580 : 3126 : }
581 : 3126 : }
582 : :
583 : : /* Add SNODE to *WORKLIST if the point is not already in *seen.
584 : : Add newly seen supernodes to *SEEN and to m_snodes_needing_name. */
585 : :
586 : : void
587 : 103456 : state_purge_per_decl::add_to_worklist (const supernode &snode,
588 : : auto_vec<const supernode *> *worklist,
589 : : point_set_t *seen,
590 : : logger *logger)
591 : : {
592 : 103456 : LOG_FUNC (logger);
593 : 103456 : if (logger)
594 : 0 : logger->log ("SN %i for worklist for %qE", snode.m_id, m_decl);
595 : :
596 : 103456 : gcc_assert (snode.get_function () == &get_function ());
597 : :
598 : 103456 : if (seen->contains (&snode))
599 : : {
600 : 10784 : if (logger)
601 : 0 : logger->log ("already seen for %qE", m_decl);
602 : : }
603 : : else
604 : : {
605 : 92672 : if (logger)
606 : 0 : logger->log ("not seen; adding to worklist for %qE", m_decl);
607 : 92672 : m_snodes_needing_decl.add (&snode);
608 : 92672 : seen->add (&snode);
609 : 92672 : worklist->safe_push (&snode);
610 : : }
611 : 103456 : }
612 : :
613 : : /* Determine if REG_A and REG_B express writing to exactly the same
614 : : set of bits.
615 : : For example, when "s.field" is the only field of "s", and there's no
616 : : padding, this should return true. */
617 : :
618 : : static bool
619 : 28102 : same_binding_p (const region *reg_a, const region *reg_b,
620 : : store_manager *store_mgr)
621 : : {
622 : 28102 : if (reg_a->get_base_region () != reg_b->get_base_region ())
623 : : return false;
624 : 3319 : if (reg_a->empty_p ())
625 : : return false;
626 : 3319 : const binding_key *bind_key_a = binding_key::make (store_mgr, reg_a);
627 : 3319 : if (reg_b->empty_p ())
628 : : return false;
629 : 3319 : const binding_key *bind_key_b = binding_key::make (store_mgr, reg_b);
630 : 3319 : return bind_key_a == bind_key_b;
631 : : }
632 : :
633 : : /* Return true if STMT fully overwrites DECL. */
634 : :
635 : : static bool
636 : 39858 : fully_overwrites_p (const gimple *stmt, tree decl,
637 : : const region_model &model)
638 : : {
639 : 39858 : if (tree lhs = gimple_get_lhs (stmt))
640 : : {
641 : : /* Determine if LHS fully overwrites DECL.
642 : : We can't just check for equality; consider the case of
643 : : "s.field = EXPR;" where the stmt writes to the only field
644 : : of "s", and there's no padding. */
645 : 28102 : const region *lhs_reg = model.get_lvalue (lhs, nullptr);
646 : 28102 : const region *decl_reg = model.get_lvalue (decl, nullptr);
647 : 28102 : if (same_binding_p (lhs_reg, decl_reg,
648 : : model.get_manager ()->get_store_manager ()))
649 : : return true;
650 : : }
651 : : return false;
652 : : }
653 : :
654 : : /* Process SNODE, popped from *WORKLIST.
655 : : Iterate over predecessors of SNODE, adding to *WORKLIST and *SEEN,
656 : : until we get to a stmt that fully overwrites the decl. */
657 : :
658 : : void
659 : 53968 : state_purge_per_decl::
660 : : process_supernode_backwards (const supernode &snode,
661 : : auto_vec<const supernode *> *worklist,
662 : : point_set_t *seen,
663 : : const state_purge_map &map,
664 : : const region_model &model)
665 : : {
666 : 53968 : logger *logger = map.get_logger ();
667 : 53968 : LOG_FUNC (logger);
668 : 53968 : if (logger)
669 : 0 : logger->log ("considering SN %i for %qE", snode.m_id, m_decl);
670 : :
671 : 208791 : for (auto in_edge : snode.m_preds)
672 : : {
673 : 53139 : if (logger)
674 : 0 : logger->log ("considering edge from SN %i", in_edge->m_src->m_id);
675 : :
676 : 53139 : bool fully_overwrites_decl = false;
677 : 53139 : if (auto op = in_edge->get_op ())
678 : : {
679 : : /* This is somewhat equivalent to how the SSA case handles
680 : : def-stmts. */
681 : 41856 : if (auto stmt = op->maybe_get_stmt ())
682 : 39858 : if (fully_overwrites_p (stmt, m_decl, model)
683 : : /* ...but we mustn't be at a point that also consumes the
684 : : current value of the decl when it's generating the new
685 : : value, for cases such as
686 : : struct st s;
687 : : s = foo ();
688 : : s = bar (s);
689 : : where we want to make sure that we don't stop at the:
690 : : s = bar (s);
691 : : since otherwise we would erroneously purge the state of "s"
692 : : after:
693 : : s = foo ();
694 : : */
695 : 39858 : && !m_snodes_needing_decl.contains (&snode))
696 : 0 : fully_overwrites_decl = true;
697 : : }
698 : 39858 : if (fully_overwrites_decl)
699 : : {
700 : 0 : if (logger)
701 : 0 : logger->log ("op fully overwrites %qE; terminating", m_decl);
702 : : }
703 : : else
704 : 53139 : add_to_worklist (*in_edge->m_src, worklist, seen, logger);
705 : : }
706 : 53968 : }
707 : :
708 : : /* Process SNODE, popped from *WORKLIST.
709 : : Iterate over successors of SNODE, adding to *WORKLIST and *SEEN. */
710 : :
711 : : void
712 : 49928 : state_purge_per_decl::
713 : : process_supernode_forwards (const supernode &snode,
714 : : auto_vec<const supernode *> *worklist,
715 : : point_set_t *seen,
716 : : const state_purge_map &map)
717 : : {
718 : 49928 : logger *logger = map.get_logger ();
719 : 49928 : LOG_FUNC (logger);
720 : 49928 : if (logger)
721 : 0 : logger->log ("considering SN %i for %qE", snode.m_id, m_decl);
722 : :
723 : 194809 : for (auto out_edge : snode.m_succs)
724 : 50317 : add_to_worklist (*out_edge->m_dest, worklist, seen, logger);
725 : 49928 : }
726 : :
727 : : /* Return true if the decl is needed at SNODE. */
728 : :
729 : : bool
730 : 202585 : state_purge_per_decl::needed_at_supernode_p (const supernode *snode) const
731 : : {
732 : 202585 : return const_cast <point_set_t &> (m_snodes_needing_decl).contains (snode);
733 : : }
734 : :
735 : : void
736 : 0 : state_purge_per_decl::on_duplicated_node (const supernode &old_snode,
737 : : const supernode &new_snode)
738 : : {
739 : 0 : if (m_snodes_needing_decl.contains (&old_snode))
740 : 0 : m_snodes_needing_decl.add (&new_snode);
741 : 0 : if (m_snodes_taking_address.contains (&old_snode))
742 : 0 : m_snodes_taking_address.add (&new_snode);
743 : 0 : }
744 : : /* class state_purge_annotator : public dot_annotator. */
745 : :
746 : : /* Implementation of dot_annotator::add_node_annotations vfunc for
747 : : state_purge_annotator.
748 : :
749 : : Add an additional record showing which names are purged on entry
750 : : to the supernode N. */
751 : :
752 : : /* Print V to GV as a comma-separated list in braces within a <TR>,
753 : : titling it with TITLE.
754 : :
755 : : Subroutine of state_purge_annotator::print_needed. */
756 : :
757 : : static void
758 : 382 : print_vec_of_names (graphviz_out *gv, const char *title,
759 : : const auto_vec<tree> &v)
760 : : {
761 : 382 : pretty_printer *pp = gv->get_pp ();
762 : 382 : tree name;
763 : 382 : unsigned i;
764 : 382 : gv->begin_trtd ();
765 : 382 : pp_printf (pp, "%s: {", title);
766 : 3134 : FOR_EACH_VEC_ELT (v, i, name)
767 : : {
768 : 2370 : if (i > 0)
769 : 2030 : pp_string (pp, ", ");
770 : 2370 : pp_printf (pp, "%qE", name);
771 : : }
772 : 382 : pp_printf (pp, "}");
773 : 382 : pp_write_text_as_html_like_dot_to_stream (pp);
774 : 382 : gv->end_tdtr ();
775 : 382 : pp_newline (pp);
776 : 382 : }
777 : :
778 : : void
779 : 191 : state_purge_annotator::add_node_annotations (graphviz_out *gv,
780 : : const supernode &snode) const
781 : : {
782 : 191 : if (m_map == nullptr)
783 : 0 : return;
784 : :
785 : 191 : auto_vec<tree> needed;
786 : 191 : auto_vec<tree> not_needed;
787 : 191 : for (state_purge_map::ssa_iterator iter = m_map->begin_ssas ();
788 : 9764 : iter != m_map->end_ssas ();
789 : 4691 : ++iter)
790 : : {
791 : 4691 : tree name = (*iter).first;
792 : 4691 : state_purge_per_ssa_name *per_name_data = (*iter).second;
793 : 4691 : if (&per_name_data->get_function () == snode.get_function ())
794 : : {
795 : 2370 : if (per_name_data->needed_at_supernode_p (&snode))
796 : 509 : needed.safe_push (name);
797 : : else
798 : 1861 : not_needed.safe_push (name);
799 : : }
800 : : }
801 : 191 : for (state_purge_map::decl_iterator iter = m_map->begin_decls ();
802 : 191 : iter != m_map->end_decls ();
803 : 0 : ++iter)
804 : : {
805 : 0 : tree decl = (*iter).first;
806 : 0 : state_purge_per_decl *per_decl_data = (*iter).second;
807 : 0 : if (&per_decl_data->get_function () == snode.get_function ())
808 : : {
809 : 0 : if (per_decl_data->needed_at_supernode_p (&snode))
810 : 0 : needed.safe_push (decl);
811 : : else
812 : 0 : not_needed.safe_push (decl);
813 : : }
814 : : }
815 : :
816 : 191 : print_vec_of_names (gv, "needed here", needed);
817 : 191 : print_vec_of_names (gv, "not needed here", not_needed);
818 : 191 : }
819 : :
820 : : #endif /* #if ENABLE_ANALYZER */
|
