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 | |
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 | #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 | |
56 | static tree |
57 | get_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 | |
87 | class gimple_op_visitor : public log_user |
88 | { |
89 | public: |
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 | |
147 | private: |
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 | |
178 | static bool |
179 | my_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 | |
185 | static bool |
186 | my_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 | |
192 | static bool |
193 | my_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 | |
204 | state_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 | |
266 | state_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 | |
277 | state_purge_per_decl & |
278 | state_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 | |
299 | state_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 | |
439 | bool |
440 | state_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 | |
448 | function_point |
449 | state_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 | |
463 | void |
464 | state_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 | |
499 | static bool |
500 | name_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 | |
519 | void |
520 | state_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 | |
682 | state_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 | |
699 | void |
700 | state_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 | |
708 | void |
709 | state_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 | |
721 | void |
722 | state_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 | |
784 | void |
785 | state_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 | |
824 | static bool |
825 | same_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 | |
841 | static bool |
842 | fully_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 | |
864 | void |
865 | state_purge_per_decl:: |
866 | process_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 | |
1003 | void |
1004 | state_purge_per_decl:: |
1005 | process_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 | |
1065 | bool |
1066 | state_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 | |
1079 | bool |
1080 | state_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 | |
1125 | static void |
1126 | print_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 | |
1155 | void |
1156 | state_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 | |
1185 | void |
1186 | state_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 | |