Branch data Line data Source code
1 : : /* Strongly-connected copy propagation pass for the GNU compiler.
2 : : Copyright (C) 2023-2025 Free Software Foundation, Inc.
3 : : Contributed by Filip Kastl <fkastl@suse.cz>
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it under
8 : : the terms of the GNU General Public License as published by the Free
9 : : Software Foundation; either version 3, or (at your option) any later
10 : : version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : : 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_ALGORITHM
22 : : #include "config.h"
23 : : #include "system.h"
24 : : #include "coretypes.h"
25 : : #include "backend.h"
26 : : #include "tree.h"
27 : : #include "gimple.h"
28 : : #include "tree-pass.h"
29 : : #include "ssa.h"
30 : : #include "gimple-iterator.h"
31 : : #include "vec.h"
32 : : #include "hash-set.h"
33 : : #include "ssa-iterators.h"
34 : : #include "gimple-fold.h"
35 : : #include "gimplify.h"
36 : : #include "tree-cfg.h"
37 : : #include "tree-eh.h"
38 : : #include "builtins.h"
39 : : #include "tree-ssa-dce.h"
40 : : #include "fold-const.h"
41 : : #include "tree-pretty-print.h"
42 : :
43 : : /* Strongly connected copy propagation pass.
44 : :
45 : : This is a lightweight copy propagation pass that is also able to eliminate
46 : : redundant PHI statements. The pass considers the following types of copy
47 : : statements:
48 : :
49 : : 1 An assignment statement with a single argument.
50 : :
51 : : _3 = _2;
52 : : _4 = 5;
53 : :
54 : : 2 A degenerate PHI statement. A degenerate PHI is a PHI that only refers to
55 : : itself or one other value.
56 : :
57 : : _5 = PHI <_1>;
58 : : _6 = PHI <_6, _6, _1, _1>;
59 : : _7 = PHI <16, _7>;
60 : :
61 : : 3 A set of PHI statements that only refer to each other or to one other
62 : : value.
63 : :
64 : : _8 = PHI <_9, _10>;
65 : : _9 = PHI <_8, _10>;
66 : : _10 = PHI <_8, _9, _1>;
67 : :
68 : : All of these statements produce copies and can be eliminated from the
69 : : program. For a copy statement we identify the value it creates a copy of
70 : : and replace references to the statement with the value -- we propagate the
71 : : copy.
72 : :
73 : : _3 = _2; // Replace all occurences of _3 by _2
74 : :
75 : : _8 = PHI <_9, _10>;
76 : : _9 = PHI <_8, _10>;
77 : : _10 = PHI <_8, _9, _1>; // Replace all occurences of _8, _9 and _10 by _1
78 : :
79 : : To find all three types of copy statements we use an algorithm based on
80 : : strongly-connected components (SCCs) in dataflow graph. The algorithm was
81 : : introduced in an article from 2013[1]. We describe the algorithm bellow.
82 : :
83 : : To identify SCCs we implement the Robert Tarjan's SCC algorithm. For the
84 : : SCC computation we wrap potential copy statements in the 'vertex' struct.
85 : : To each of these statements we also assign a vertex number ('vxnum'). Since
86 : : the main algorithm has to be able to compute SCCs of subgraphs of the whole
87 : : dataflow graph we use GIMPLE stmt flags to prevent Tarjan's algorithm from
88 : : leaving the subgraph.
89 : :
90 : : References:
91 : :
92 : : [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
93 : : Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
94 : : Section 3.2. */
95 : :
96 : : namespace {
97 : :
98 : : /* State of vertex during SCC discovery.
99 : :
100 : : unvisited Vertex hasn't yet been popped from worklist.
101 : : vopen DFS has visited vertex for the first time. Vertex has been put
102 : : on Tarjan stack.
103 : : closed DFS has backtracked through vertex. At this point, vertex
104 : : doesn't have any unvisited neighbors.
105 : : in_scc Vertex has been popped from Tarjan stack. */
106 : :
107 : : enum vstate
108 : : {
109 : : unvisited,
110 : : vopen,
111 : : closed,
112 : : in_scc
113 : : };
114 : :
115 : : /* Information about a vertex. Used by SCC discovery. */
116 : :
117 : : struct vertex
118 : : {
119 : : bool active; /* scc_discovery::compute_sccs () only considers a subgraph of
120 : : the whole dataflow graph. It uses this flag so that it knows
121 : : which vertices are part of this subgraph. */
122 : : vstate state;
123 : : unsigned index;
124 : : unsigned lowlink;
125 : : };
126 : :
127 : : /* SCC discovery.
128 : :
129 : : Used to find SCCs in a dataflow graph. Implements Tarjan's SCC
130 : : algorithm. */
131 : :
132 : : class scc_discovery
133 : : {
134 : : public:
135 : : scc_discovery ();
136 : : ~scc_discovery ();
137 : : auto_vec<vec<gimple *>> compute_sccs (vec<gimple *> &stmts);
138 : :
139 : : private:
140 : : vertex* vertices; /* Indexed by SSA_NAME_VERSION. */
141 : : auto_vec<unsigned> worklist; /* DFS stack. */
142 : : auto_vec<unsigned> stack; /* Tarjan stack. */
143 : :
144 : : void visit_neighbor (tree neigh_tree, unsigned parent_vxnum);
145 : : };
146 : :
147 : 3315974 : scc_discovery::scc_discovery ()
148 : : {
149 : : /* Create vertex struct for each SSA name. */
150 : 6631948 : vertices = XNEWVEC (struct vertex, num_ssa_names);
151 : 3315974 : unsigned i = 0;
152 : 124287064 : for (i = 0; i < num_ssa_names; i++)
153 : 120971090 : vertices[i].active = false;
154 : 3315974 : }
155 : :
156 : 3315974 : scc_discovery::~scc_discovery ()
157 : : {
158 : 3315974 : XDELETEVEC (vertices);
159 : 3315974 : }
160 : :
161 : : /* Part of 'scc_discovery::compute_sccs ()'. */
162 : :
163 : : void
164 : 42722989 : scc_discovery::visit_neighbor (tree neigh_tree, unsigned parent_version)
165 : : {
166 : 42722989 : if (TREE_CODE (neigh_tree) != SSA_NAME)
167 : 32733972 : return; /* Skip any neighbor that isn't an SSA name. */
168 : 38520758 : unsigned neigh_version = SSA_NAME_VERSION (neigh_tree);
169 : :
170 : : /* Skip neighbors outside the subgraph that Tarjan currently works
171 : : with. */
172 : 38520758 : if (!vertices[neigh_version].active)
173 : : return;
174 : :
175 : 9989017 : vstate neigh_state = vertices[neigh_version].state;
176 : 9989017 : vstate parent_state = vertices[parent_version].state;
177 : 9989017 : if (parent_state == vopen) /* We're currently opening parent. */
178 : : {
179 : : /* Put unvisited neighbors on worklist. Update lowlink of parent
180 : : vertex according to indices of neighbors present on stack. */
181 : 3739152 : switch (neigh_state)
182 : : {
183 : 2618953 : case unvisited:
184 : 2618953 : worklist.safe_push (neigh_version);
185 : 2618953 : break;
186 : 548086 : case vopen:
187 : 548086 : case closed:
188 : 548086 : vertices[parent_version].lowlink
189 : 548086 : = std::min (vertices[parent_version].lowlink,
190 : : vertices[neigh_version].index);
191 : 548086 : break;
192 : : case in_scc:
193 : : /* Ignore these edges. */
194 : : break;
195 : : }
196 : : }
197 : 6249865 : else if (parent_state == closed) /* We're currently closing parent. */
198 : : {
199 : : /* Update lowlink of parent vertex according to lowlinks of
200 : : children of parent (in terms of DFS tree). */
201 : 3906674 : if (neigh_state == closed)
202 : : {
203 : 722959 : vertices[parent_version].lowlink
204 : 722959 : = std::min (vertices[parent_version].lowlink,
205 : : vertices[neigh_version].lowlink);
206 : : }
207 : : }
208 : : }
209 : :
210 : : /* Compute SCCs in dataflow graph on given statements 'stmts'. Ignore
211 : : statements outside 'stmts'. Return the SCCs in a reverse topological
212 : : order.
213 : :
214 : : stmt_may_generate_copy () must be true for all statements from 'stmts'! */
215 : :
216 : : auto_vec<vec<gimple *>>
217 : 10059199 : scc_discovery::compute_sccs (vec<gimple *> &stmts)
218 : : {
219 : 10059199 : auto_vec<vec<gimple *>> sccs;
220 : :
221 : 19907931 : for (gimple *stmt : stmts)
222 : : {
223 : 7618346 : unsigned i;
224 : 7618346 : switch (gimple_code (stmt))
225 : : {
226 : 22625 : case GIMPLE_ASSIGN:
227 : 22625 : i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
228 : 22625 : break;
229 : 7595721 : case GIMPLE_PHI:
230 : 7595721 : i = SSA_NAME_VERSION (gimple_phi_result (stmt));
231 : 7595721 : break;
232 : 0 : default:
233 : 0 : gcc_unreachable ();
234 : : }
235 : :
236 : 7618346 : vertices[i].index = 0;
237 : 7618346 : vertices[i].lowlink = 0;
238 : 7618346 : vertices[i].state = unvisited;
239 : 7618346 : vertices[i].active = true; /* Mark the subgraph we'll be working on so
240 : : that we don't leave it. */
241 : :
242 : 7618346 : worklist.safe_push (i);
243 : : }
244 : :
245 : : /* Worklist loop. */
246 : : unsigned curr_index = 0;
247 : 27914844 : while (!worklist.is_empty ())
248 : : {
249 : 17855645 : unsigned i = worklist.pop ();
250 : 17855645 : gimple *stmt = SSA_NAME_DEF_STMT (ssa_name (i));
251 : 17855645 : vstate state = vertices[i].state;
252 : :
253 : 17855645 : if (state == unvisited)
254 : : {
255 : 7618346 : vertices[i].state = vopen;
256 : :
257 : : /* Assign index to this vertex. */
258 : 7618346 : vertices[i].index = curr_index;
259 : 7618346 : vertices[i].lowlink = curr_index;
260 : 7618346 : curr_index++;
261 : :
262 : : /* Put vertex on stack and also on worklist to be closed later. */
263 : 7618346 : stack.safe_push (i);
264 : 7618346 : worklist.safe_push (i);
265 : : }
266 : 10237299 : else if (state == vopen)
267 : 7618346 : vertices[i].state = closed;
268 : :
269 : : /* Visit neighbors of this vertex. */
270 : 17855645 : tree op;
271 : 17855645 : gphi *phi;
272 : 17855645 : switch (gimple_code (stmt))
273 : : {
274 : 17809435 : case GIMPLE_PHI:
275 : 17809435 : phi = as_a <gphi *> (stmt);
276 : 17809435 : unsigned j;
277 : 78295649 : for (j = 0; j < gimple_phi_num_args (phi); j++)
278 : : {
279 : 42676779 : op = gimple_phi_arg_def (phi, j);
280 : 42676779 : visit_neighbor (op, i);
281 : : }
282 : : break;
283 : 46210 : case GIMPLE_ASSIGN:
284 : 46210 : op = gimple_assign_rhs1 (stmt);
285 : 46210 : visit_neighbor (op, i);
286 : 46210 : break;
287 : 0 : default:
288 : 0 : gcc_unreachable ();
289 : : }
290 : :
291 : : /* If we've just closed a root vertex of an scc, pop scc from stack. */
292 : 17855645 : if (state == vopen && vertices[i].lowlink == vertices[i].index)
293 : : {
294 : 7158706 : vec<gimple *> scc = vNULL;
295 : :
296 : 7618346 : unsigned j;
297 : 7618346 : do
298 : : {
299 : 7618346 : j = stack.pop ();
300 : 7618346 : scc.safe_push (SSA_NAME_DEF_STMT (ssa_name (j)));
301 : 7618346 : vertices[j].state = in_scc;
302 : : }
303 : 7618346 : while (j != i);
304 : :
305 : 7158706 : sccs.safe_push (scc);
306 : : }
307 : : }
308 : :
309 : 10059199 : if (!stack.is_empty ())
310 : 0 : gcc_unreachable ();
311 : :
312 : : /* Clear 'active' flags. */
313 : 19907931 : for (gimple *stmt : stmts)
314 : : {
315 : 7618346 : unsigned i;
316 : 7618346 : switch (gimple_code (stmt))
317 : : {
318 : 22625 : case GIMPLE_ASSIGN:
319 : 22625 : i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
320 : 22625 : break;
321 : 7595721 : case GIMPLE_PHI:
322 : 7595721 : i = SSA_NAME_VERSION (gimple_phi_result (stmt));
323 : 7595721 : break;
324 : 0 : default:
325 : 0 : gcc_unreachable ();
326 : : }
327 : :
328 : 7618346 : vertices[i].active = false;
329 : : }
330 : :
331 : 10059199 : return sccs;
332 : : }
333 : :
334 : : } // anon namespace
335 : :
336 : : /* Could this statement potentially be a copy statement?
337 : :
338 : : This pass only considers statements for which this function returns 'true'.
339 : : Those are basically PHI functions and assignment statements similar to
340 : :
341 : : _2 = _1;
342 : : or
343 : : _2 = 5; */
344 : :
345 : : static bool
346 : 145749147 : stmt_may_generate_copy (gimple *stmt)
347 : : {
348 : : /* A PHI may generate a copy. */
349 : 145749147 : if (gimple_code (stmt) == GIMPLE_PHI)
350 : : {
351 : 7764947 : gphi *phi = as_a <gphi *> (stmt);
352 : :
353 : : /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs. */
354 : 7764947 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi)))
355 : : return false;
356 : :
357 : : unsigned i;
358 : 26655133 : for (i = 0; i < gimple_phi_num_args (phi); i++)
359 : : {
360 : 18901949 : tree op = gimple_phi_arg_def (phi, i);
361 : 18901949 : if (TREE_CODE (op) == SSA_NAME
362 : 18901949 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
363 : : return false;
364 : : }
365 : :
366 : : /* If PHI has more than one unique non-SSA arguments, it won't generate a
367 : : copy. */
368 : : tree const_op = NULL_TREE;
369 : 25980533 : for (i = 0; i < gimple_phi_num_args (phi); i++)
370 : : {
371 : 18534490 : tree op = gimple_phi_arg_def (phi, i);
372 : 18534490 : if (TREE_CODE (op) != SSA_NAME)
373 : : {
374 : 2475642 : if (const_op && !operand_equal_p (op, const_op))
375 : : return false;
376 : : const_op = op;
377 : : }
378 : : }
379 : :
380 : : return true;
381 : : }
382 : :
383 : : /* Or a statement of type _2 = _1; OR _2 = 5; may generate a copy. */
384 : :
385 : 137984200 : if (!gimple_assign_single_p (stmt))
386 : : return false;
387 : :
388 : 28257852 : tree lhs = gimple_assign_lhs (stmt);
389 : 28257852 : tree rhs = gimple_assign_rhs1 (stmt);
390 : :
391 : 28257852 : if (TREE_CODE (lhs) != SSA_NAME)
392 : : return false;
393 : :
394 : : /* lhs shouldn't flow through any abnormal edges. */
395 : 12972093 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
396 : : return false;
397 : :
398 : 12971437 : if (is_gimple_min_invariant (rhs))
399 : : return true; /* A statement of type _2 = 5;. */
400 : :
401 : 12965906 : if (TREE_CODE (rhs) != SSA_NAME)
402 : : return false;
403 : :
404 : : /* rhs shouldn't flow through any abnormal edges. */
405 : 29047 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
406 : : return false;
407 : :
408 : : /* It is possible that lhs has more alignment or value range information. By
409 : : propagating we would lose this information. So in the case that alignment
410 : : or value range information differs, we are conservative and do not
411 : : propagate.
412 : :
413 : : FIXME: Propagate alignment and value range info the same way copy-prop
414 : : does. */
415 : 53814 : if (POINTER_TYPE_P (TREE_TYPE (lhs))
416 : 2200 : && POINTER_TYPE_P (TREE_TYPE (rhs))
417 : 30205 : && SSA_NAME_PTR_INFO (lhs) != SSA_NAME_PTR_INFO (rhs))
418 : : return false;
419 : 51790 : if (!POINTER_TYPE_P (TREE_TYPE (lhs))
420 : 25805 : && !POINTER_TYPE_P (TREE_TYPE (rhs))
421 : 51790 : && SSA_NAME_RANGE_INFO (lhs) != SSA_NAME_RANGE_INFO (rhs))
422 : : return false;
423 : :
424 : : return true; /* A statement of type _2 = _1;. */
425 : : }
426 : :
427 : : /* Return all statements in cfun that could generate copies. All statements
428 : : for which stmt_may_generate_copy returns 'true'. */
429 : :
430 : : static auto_vec<gimple *>
431 : 3315974 : get_all_stmt_may_generate_copy (void)
432 : : {
433 : 3315974 : auto_vec<gimple *> result;
434 : :
435 : 3315974 : basic_block bb;
436 : 23556482 : FOR_EACH_BB_FN (bb, cfun)
437 : : {
438 : 20240508 : gimple_stmt_iterator gsi;
439 : 178465216 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
440 : : {
441 : 137984200 : gimple *s = gsi_stmt (gsi);
442 : 137984200 : if (stmt_may_generate_copy (s))
443 : 22625 : result.safe_push (s);
444 : : }
445 : :
446 : 20240508 : gphi_iterator pi;
447 : 28005455 : for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
448 : : {
449 : 7764947 : gimple *s = pi.phi ();
450 : 7764947 : if (stmt_may_generate_copy (s))
451 : 7446043 : result.safe_push (s);
452 : : }
453 : : }
454 : :
455 : 3315974 : return result;
456 : : }
457 : :
458 : : /* SCC copy propagation
459 : :
460 : : 'scc_copy_prop::propagate ()' is the main function of this pass. */
461 : :
462 : : class scc_copy_prop
463 : : {
464 : : public:
465 : : scc_copy_prop ();
466 : : ~scc_copy_prop ();
467 : : void propagate ();
468 : :
469 : : private:
470 : : /* Bitmap tracking statements which were propagated so that they can be
471 : : removed at the end of the pass. */
472 : : bitmap dead_stmts;
473 : :
474 : : void visit_op (tree op, hash_set<tree> &outer_ops,
475 : : hash_set<gimple *> &scc_set, bool &is_inner,
476 : : tree &last_outer_op);
477 : : void replace_scc_by_value (vec<gimple *> scc, tree val);
478 : : };
479 : :
480 : : /* For each statement from given SCC, replace its usages by value
481 : : VAL. */
482 : :
483 : : void
484 : 415480 : scc_copy_prop::replace_scc_by_value (vec<gimple *> scc, tree val)
485 : : {
486 : 1666612 : for (gimple *stmt : scc)
487 : : {
488 : 420172 : tree name = gimple_get_lhs (stmt);
489 : 420172 : if (dump_file && (dump_flags & TDF_DETAILS))
490 : : {
491 : 0 : fprintf (dump_file, "Replacing ");
492 : 0 : print_generic_expr (dump_file, name);
493 : 0 : fprintf (dump_file, " with ");
494 : 0 : print_generic_expr (dump_file, val);
495 : 0 : fprintf (dump_file, "\n");
496 : :
497 : : }
498 : 420172 : replace_uses_by (name, val);
499 : 420172 : bitmap_set_bit (dead_stmts, SSA_NAME_VERSION (name));
500 : : }
501 : :
502 : 415480 : if (dump_file)
503 : 56 : fprintf (dump_file, "Replacing SCC of size %d\n", scc.length ());
504 : 415480 : }
505 : :
506 : : /* Part of 'scc_copy_prop::propagate ()'. */
507 : :
508 : : void
509 : 18203918 : scc_copy_prop::visit_op (tree op, hash_set<tree> &outer_ops,
510 : : hash_set<gimple *> &scc_set, bool &is_inner,
511 : : tree &last_outer_op)
512 : : {
513 : 18203918 : bool op_in_scc = false;
514 : :
515 : 18203918 : if (TREE_CODE (op) == SSA_NAME)
516 : : {
517 : 16352921 : gimple *op_stmt = SSA_NAME_DEF_STMT (op);
518 : 16352921 : if (scc_set.contains (op_stmt))
519 : 1111674 : op_in_scc = true;
520 : : }
521 : :
522 : 16352921 : if (!op_in_scc)
523 : : {
524 : 17092244 : outer_ops.add (op);
525 : 17092244 : last_outer_op = op;
526 : 17092244 : is_inner = false;
527 : : }
528 : 18203918 : }
529 : :
530 : : /* Main function of this pass. Find and propagate all three types of copy
531 : : statements (see pass description above).
532 : :
533 : : This is an implementation of an algorithm from the paper Simple and
534 : : Efficient Construction of Static Single Assignmemnt Form[1]. It is based
535 : : on strongly-connected components (SCCs) in dataflow graph. The original
536 : : algorithm only considers PHI statements. We extend it to also consider
537 : : assignment statements of type _2 = _1;.
538 : :
539 : : The algorithm is based on this definition of a set of redundant PHIs[1]:
540 : :
541 : : A non-empty set P of PHI functions is redundant iff the PHI functions just
542 : : reference each other or one other value
543 : :
544 : : It uses this lemma[1]:
545 : :
546 : : Let P be a redundant set of PHI functions. Then there is a
547 : : strongly-connected component S subset of P that is also redundant.
548 : :
549 : : The algorithm works in this way:
550 : :
551 : : 1 Find SCCs
552 : : 2 For each SCC S in topological order:
553 : : 3 Construct set 'inner' of statements that only have other statements
554 : : from S on their right hand side
555 : : 4 Construct set 'outer' of values that originate outside S and appear on
556 : : right hand side of some statement from S
557 : : 5 If |outer| = 1, outer only contains a value v. Statements in S only
558 : : refer to each other or to v -- they are redundant. Propagate v.
559 : : Else, recurse on statements in inner.
560 : :
561 : : The implementation is non-recursive.
562 : :
563 : : References:
564 : :
565 : : [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
566 : : Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
567 : : Section 3.2. */
568 : :
569 : : void
570 : 3315974 : scc_copy_prop::propagate ()
571 : : {
572 : 3315974 : auto_vec<gimple *> useful_stmts = get_all_stmt_may_generate_copy ();
573 : 3315974 : scc_discovery discovery;
574 : :
575 : 3315974 : auto_vec<vec<gimple *>> worklist = discovery.compute_sccs (useful_stmts);
576 : :
577 : 14829742 : while (!worklist.is_empty ())
578 : : {
579 : 7158706 : vec<gimple *> scc = worklist.pop ();
580 : :
581 : : /* When we do 'replace_scc_by_value' it may happen that some EH edges
582 : : get removed. That means parts of CFG get removed. Those may
583 : : contain copy statements. For that reason we prune SCCs here. */
584 : 7158706 : unsigned i;
585 : 14777052 : for (i = 0; i < scc.length ();)
586 : 7618346 : if (gimple_bb (scc[i]) == NULL)
587 : 1 : scc.unordered_remove (i);
588 : : else
589 : 7618345 : i++;
590 : 7158706 : if (scc.is_empty ())
591 : : {
592 : 1 : scc.release ();
593 : 1 : continue;
594 : : }
595 : :
596 : 7158705 : auto_vec<gimple *> inner;
597 : 7158705 : hash_set<tree> outer_ops;
598 : 7158705 : tree last_outer_op = NULL_TREE;
599 : :
600 : : /* Prepare hash set of PHIs in scc to query later. */
601 : 7158705 : hash_set<gimple *> scc_set;
602 : 14777050 : for (gimple *stmt : scc)
603 : 7618345 : scc_set.add (stmt);
604 : :
605 : 14777050 : for (gimple *stmt : scc)
606 : : {
607 : 7618345 : bool is_inner = true;
608 : :
609 : 7618345 : gphi *phi;
610 : 7618345 : tree op;
611 : :
612 : 7618345 : switch (gimple_code (stmt))
613 : : {
614 : 7595720 : case GIMPLE_PHI:
615 : 7595720 : phi = as_a <gphi *> (stmt);
616 : 7595720 : unsigned j;
617 : 33372733 : for (j = 0; j < gimple_phi_num_args (phi); j++)
618 : : {
619 : 18181293 : op = gimple_phi_arg_def (phi, j);
620 : 18181293 : visit_op (op, outer_ops, scc_set, is_inner, last_outer_op);
621 : : }
622 : : break;
623 : 22625 : case GIMPLE_ASSIGN:
624 : 22625 : op = gimple_assign_rhs1 (stmt);
625 : 22625 : visit_op (op, outer_ops, scc_set, is_inner, last_outer_op);
626 : 22625 : break;
627 : 0 : default:
628 : 0 : gcc_unreachable ();
629 : : }
630 : :
631 : 7618345 : if (is_inner)
632 : 153809 : inner.safe_push (stmt);
633 : : }
634 : :
635 : 7158705 : if (outer_ops.elements () == 1)
636 : : {
637 : : /* The only operand in outer_ops. */
638 : 415480 : tree outer_op = last_outer_op;
639 : 415480 : replace_scc_by_value (scc, outer_op);
640 : : }
641 : 6743225 : else if (outer_ops.elements () > 1)
642 : : {
643 : : /* Add inner sccs to worklist. */
644 : 6743225 : auto_vec<vec<gimple *>> inner_sccs
645 : 6743225 : = discovery.compute_sccs (inner);
646 : 7017891 : for (vec<gimple *> inner_scc : inner_sccs)
647 : 122456 : worklist.safe_push (inner_scc);
648 : 6743225 : }
649 : : else
650 : 0 : gcc_unreachable ();
651 : :
652 : 7158705 : scc.release ();
653 : 7158705 : }
654 : 3315974 : }
655 : :
656 : 3315974 : scc_copy_prop::scc_copy_prop ()
657 : : {
658 : : /* For propagated statements. */
659 : 3315974 : dead_stmts = BITMAP_ALLOC (NULL);
660 : 3315974 : }
661 : :
662 : 3315974 : scc_copy_prop::~scc_copy_prop ()
663 : : {
664 : : /* Remove all propagated statements. */
665 : 3315974 : simple_dce_from_worklist (dead_stmts);
666 : 3315974 : BITMAP_FREE (dead_stmts);
667 : :
668 : : /* Propagating a constant may create dead eh edges. */
669 : 3315974 : basic_block bb;
670 : 23556478 : FOR_EACH_BB_FN (bb, cfun)
671 : 20240504 : gimple_purge_dead_eh_edges (bb);
672 : 3315974 : }
673 : :
674 : : namespace {
675 : :
676 : : const pass_data pass_data_sccopy =
677 : : {
678 : : GIMPLE_PASS, /* type */
679 : : "sccopy", /* name */
680 : : OPTGROUP_NONE, /* optinfo_flags */
681 : : TV_NONE, /* tv_id */
682 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
683 : : 0, /* properties_provided */
684 : : 0, /* properties_destroyed */
685 : : 0, /* todo_flags_start */
686 : : TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
687 : : };
688 : :
689 : : class pass_sccopy : public gimple_opt_pass
690 : : {
691 : : public:
692 : 566314 : pass_sccopy (gcc::context *ctxt)
693 : 1132628 : : gimple_opt_pass (pass_data_sccopy, ctxt)
694 : : {}
695 : :
696 : : /* opt_pass methods: */
697 : 3316048 : virtual bool gate (function *) { return true; }
698 : : virtual unsigned int execute (function *);
699 : 283157 : opt_pass * clone () final override { return new pass_sccopy (m_ctxt); }
700 : : }; // class pass_sccopy
701 : :
702 : : unsigned
703 : 3315974 : pass_sccopy::execute (function *)
704 : : {
705 : 3315974 : scc_copy_prop sccopy;
706 : 3315974 : sccopy.propagate ();
707 : 6631948 : return 0;
708 : 3315974 : }
709 : :
710 : : } // anon namespace
711 : :
712 : : gimple_opt_pass *
713 : 283157 : make_pass_sccopy (gcc::context *ctxt)
714 : : {
715 : 283157 : return new pass_sccopy (ctxt);
716 : : }
|
