Branch data Line data Source code
1 : : /* Strongly-connected copy propagation pass for the GNU compiler.
2 : : Copyright (C) 2023-2024 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 : :
42 : : /* Strongly connected copy propagation pass.
43 : :
44 : : This is a lightweight copy propagation pass that is also able to eliminate
45 : : redundant PHI statements. The pass considers the following types of copy
46 : : statements:
47 : :
48 : : 1 An assignment statement with a single argument.
49 : :
50 : : _3 = _2;
51 : : _4 = 5;
52 : :
53 : : 2 A degenerate PHI statement. A degenerate PHI is a PHI that only refers to
54 : : itself or one other value.
55 : :
56 : : _5 = PHI <_1>;
57 : : _6 = PHI <_6, _6, _1, _1>;
58 : : _7 = PHI <16, _7>;
59 : :
60 : : 3 A set of PHI statements that only refer to each other or to one other
61 : : value.
62 : :
63 : : _8 = PHI <_9, _10>;
64 : : _9 = PHI <_8, _10>;
65 : : _10 = PHI <_8, _9, _1>;
66 : :
67 : : All of these statements produce copies and can be eliminated from the
68 : : program. For a copy statement we identify the value it creates a copy of
69 : : and replace references to the statement with the value -- we propagate the
70 : : copy.
71 : :
72 : : _3 = _2; // Replace all occurences of _3 by _2
73 : :
74 : : _8 = PHI <_9, _10>;
75 : : _9 = PHI <_8, _10>;
76 : : _10 = PHI <_8, _9, _1>; // Replace all occurences of _8, _9 and _10 by _1
77 : :
78 : : To find all three types of copy statements we use an algorithm based on
79 : : strongly-connected components (SCCs) in dataflow graph. The algorithm was
80 : : introduced in an article from 2013[1]. We describe the algorithm bellow.
81 : :
82 : : To identify SCCs we implement the Robert Tarjan's SCC algorithm. For the
83 : : SCC computation we wrap potential copy statements in the 'vertex' struct.
84 : : To each of these statements we also assign a vertex number ('vxnum'). Since
85 : : the main algorithm has to be able to compute SCCs of subgraphs of the whole
86 : : dataflow graph we use GIMPLE stmt flags to prevent Tarjan's algorithm from
87 : : leaving the subgraph.
88 : :
89 : : References:
90 : :
91 : : [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
92 : : Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
93 : : Section 3.2. */
94 : :
95 : : /* Bitmap tracking statements which were propagated to be removed at the end of
96 : : the pass. */
97 : :
98 : : namespace {
99 : : static bitmap dead_stmts;
100 : :
101 : : /* State of vertex during SCC discovery.
102 : :
103 : : unvisited Vertex hasn't yet been popped from worklist.
104 : : vopen DFS has visited vertex for the first time. Vertex has been put
105 : : on Tarjan stack.
106 : : closed DFS has backtracked through vertex. At this point, vertex
107 : : doesn't have any unvisited neighbors.
108 : : in_scc Vertex has been popped from Tarjan stack. */
109 : :
110 : : enum vstate
111 : : {
112 : : unvisited,
113 : : vopen,
114 : : closed,
115 : : in_scc
116 : : };
117 : :
118 : : /* Information about a vertex. Used by SCC discovery. */
119 : :
120 : : struct vertex
121 : : {
122 : : bool active; /* scc_discovery::compute_sccs () only considers a subgraph of
123 : : the whole dataflow graph. It uses this flag so that it knows
124 : : which vertices are part of this subgraph. */
125 : : vstate state;
126 : : unsigned index;
127 : : unsigned lowlink;
128 : : };
129 : :
130 : : /* SCC discovery.
131 : :
132 : : Used to find SCCs in a dataflow graph. Implements Tarjan's SCC
133 : : algorithm. */
134 : :
135 : : class scc_discovery
136 : : {
137 : : public:
138 : : scc_discovery ();
139 : : ~scc_discovery ();
140 : : auto_vec<vec<gimple *>> compute_sccs (vec<gimple *> &stmts);
141 : :
142 : : private:
143 : : vertex* vertices; /* Indexed by SSA_NAME_VERSION. */
144 : : auto_vec<unsigned> worklist; /* DFS stack. */
145 : : auto_vec<unsigned> stack; /* Tarjan stack. */
146 : :
147 : : void visit_neighbor (tree neigh_tree, unsigned parent_vxnum);
148 : : };
149 : :
150 : 3156518 : scc_discovery::scc_discovery ()
151 : : {
152 : : /* Create vertex struct for each SSA name. */
153 : 6313036 : vertices = XNEWVEC (struct vertex, num_ssa_names);
154 : 3156518 : unsigned i = 0;
155 : 233044512 : for (i = 0; i < num_ssa_names; i++)
156 : 113365738 : vertices[i].active = false;
157 : 3156518 : }
158 : :
159 : 3156518 : scc_discovery::~scc_discovery ()
160 : : {
161 : 3156518 : XDELETEVEC (vertices);
162 : 3156518 : }
163 : :
164 : : /* Part of 'scc_discovery::compute_sccs ()'. */
165 : :
166 : : void
167 : 39671547 : scc_discovery::visit_neighbor (tree neigh_tree, unsigned parent_version)
168 : : {
169 : 39671547 : if (TREE_CODE (neigh_tree) != SSA_NAME)
170 : 30749205 : return; /* Skip any neighbor that isn't an SSA name. */
171 : 35769307 : unsigned neigh_version = SSA_NAME_VERSION (neigh_tree);
172 : :
173 : : /* Skip neighbors outside the subgraph that Tarjan currently works
174 : : with. */
175 : 35769307 : if (!vertices[neigh_version].active)
176 : : return;
177 : :
178 : 8922342 : vstate neigh_state = vertices[neigh_version].state;
179 : 8922342 : vstate parent_state = vertices[parent_version].state;
180 : 8922342 : if (parent_state == vopen) /* We're currently opening parent. */
181 : : {
182 : : /* Put unvisited neighbors on worklist. Update lowlink of parent
183 : : vertex according to indices of neighbors present on stack. */
184 : 3335920 : switch (neigh_state)
185 : : {
186 : 2359039 : case unvisited:
187 : 2359039 : worklist.safe_push (neigh_version);
188 : 2359039 : break;
189 : 468148 : case vopen:
190 : 468148 : case closed:
191 : 468148 : vertices[parent_version].lowlink
192 : 936296 : = std::min (vertices[parent_version].lowlink,
193 : 468148 : vertices[neigh_version].index);
194 : 468148 : break;
195 : : case in_scc:
196 : : /* Ignore these edges. */
197 : : break;
198 : : }
199 : : }
200 : 5586422 : else if (parent_state == closed) /* We're currently closing parent. */
201 : : {
202 : : /* Update lowlink of parent vertex according to lowlinks of
203 : : children of parent (in terms of DFS tree). */
204 : 3511800 : if (neigh_state == closed)
205 : : {
206 : 663008 : vertices[parent_version].lowlink
207 : 663008 : = std::min (vertices[parent_version].lowlink,
208 : 663008 : vertices[neigh_version].lowlink);
209 : : }
210 : : }
211 : : }
212 : :
213 : : /* Compute SCCs in dataflow graph on given statements 'stmts'. Ignore
214 : : statements outside 'stmts'. Return the SCCs in a reverse topological
215 : : order.
216 : :
217 : : stmt_may_generate_copy () must be true for all statements from 'stmts'! */
218 : :
219 : : auto_vec<vec<gimple *>>
220 : 9431458 : scc_discovery::compute_sccs (vec<gimple *> &stmts)
221 : : {
222 : 9431458 : auto_vec<vec<gimple *>> sccs;
223 : :
224 : 18608945 : for (gimple *stmt : stmts)
225 : : {
226 : 7053223 : unsigned i;
227 : 7053223 : switch (gimple_code (stmt))
228 : : {
229 : 22178 : case GIMPLE_ASSIGN:
230 : 22178 : i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
231 : 22178 : break;
232 : 7031045 : case GIMPLE_PHI:
233 : 7031045 : i = SSA_NAME_VERSION (gimple_phi_result (stmt));
234 : 7031045 : break;
235 : 0 : default:
236 : 0 : gcc_unreachable ();
237 : : }
238 : :
239 : 7053223 : vertices[i].index = 0;
240 : 7053223 : vertices[i].lowlink = 0;
241 : 7053223 : vertices[i].state = unvisited;
242 : 7053223 : vertices[i].active = true; /* Mark the subgraph we'll be working on so
243 : : that we don't leave it. */
244 : :
245 : 7053223 : worklist.safe_push (i);
246 : : }
247 : :
248 : : /* Worklist loop. */
249 : : unsigned curr_index = 0;
250 : 25896943 : while (!worklist.is_empty ())
251 : : {
252 : 16465485 : unsigned i = worklist.pop ();
253 : 16465485 : gimple *stmt = SSA_NAME_DEF_STMT (ssa_name (i));
254 : 16465485 : vstate state = vertices[i].state;
255 : :
256 : 16465485 : if (state == unvisited)
257 : : {
258 : 7053223 : vertices[i].state = vopen;
259 : :
260 : : /* Assign index to this vertex. */
261 : 7053223 : vertices[i].index = curr_index;
262 : 7053223 : vertices[i].lowlink = curr_index;
263 : 7053223 : curr_index++;
264 : :
265 : : /* Put vertex on stack and also on worklist to be closed later. */
266 : 7053223 : stack.safe_push (i);
267 : 7053223 : worklist.safe_push (i);
268 : : }
269 : 9412262 : else if (state == vopen)
270 : 7053223 : vertices[i].state = closed;
271 : :
272 : : /* Visit neighbors of this vertex. */
273 : 16465485 : tree op;
274 : 16465485 : gphi *phi;
275 : 16465485 : switch (gimple_code (stmt))
276 : : {
277 : 16420344 : case GIMPLE_PHI:
278 : 16420344 : phi = as_a <gphi *> (stmt);
279 : 16420344 : unsigned j;
280 : 72467094 : for (j = 0; j < gimple_phi_num_args (phi); j++)
281 : : {
282 : 39626406 : op = gimple_phi_arg_def (phi, j);
283 : 39626406 : visit_neighbor (op, i);
284 : : }
285 : : break;
286 : 45141 : case GIMPLE_ASSIGN:
287 : 45141 : op = gimple_assign_rhs1 (stmt);
288 : 45141 : visit_neighbor (op, i);
289 : 45141 : break;
290 : 0 : default:
291 : 0 : gcc_unreachable ();
292 : : }
293 : :
294 : : /* If we've just closed a root vertex of an scc, pop scc from stack. */
295 : 16465485 : if (state == vopen && vertices[i].lowlink == vertices[i].index)
296 : : {
297 : 6660189 : vec<gimple *> scc = vNULL;
298 : :
299 : 7053223 : unsigned j;
300 : 7053223 : do
301 : : {
302 : 7053223 : j = stack.pop ();
303 : 7053223 : scc.safe_push (SSA_NAME_DEF_STMT (ssa_name (j)));
304 : 7053223 : vertices[j].state = in_scc;
305 : : }
306 : 7053223 : while (j != i);
307 : :
308 : 6660189 : sccs.safe_push (scc);
309 : : }
310 : : }
311 : :
312 : 9431458 : if (!stack.is_empty ())
313 : 0 : gcc_unreachable ();
314 : :
315 : : /* Clear 'active' flags. */
316 : 18608945 : for (gimple *stmt : stmts)
317 : : {
318 : 7053223 : unsigned i;
319 : 7053223 : switch (gimple_code (stmt))
320 : : {
321 : 22178 : case GIMPLE_ASSIGN:
322 : 22178 : i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
323 : 22178 : break;
324 : 7031045 : case GIMPLE_PHI:
325 : 7031045 : i = SSA_NAME_VERSION (gimple_phi_result (stmt));
326 : 7031045 : break;
327 : 0 : default:
328 : 0 : gcc_unreachable ();
329 : : }
330 : :
331 : 7053223 : vertices[i].active = false;
332 : : }
333 : :
334 : 9431458 : return sccs;
335 : : }
336 : :
337 : : } // anon namespace
338 : :
339 : : /* Could this statement potentially be a copy statement?
340 : :
341 : : This pass only considers statements for which this function returns 'true'.
342 : : Those are basically PHI functions and assignment statements similar to
343 : :
344 : : _2 = _1;
345 : : or
346 : : _2 = 5; */
347 : :
348 : : static bool
349 : 134182039 : stmt_may_generate_copy (gimple *stmt)
350 : : {
351 : : /* A PHI may generate a copy. */
352 : 134182039 : if (gimple_code (stmt) == GIMPLE_PHI)
353 : : {
354 : 7206568 : gphi *phi = as_a <gphi *> (stmt);
355 : :
356 : : /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs. */
357 : 7206568 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi)))
358 : : return false;
359 : :
360 : : unsigned i;
361 : 24829932 : for (i = 0; i < gimple_phi_num_args (phi); i++)
362 : : {
363 : 17634493 : tree op = gimple_phi_arg_def (phi, i);
364 : 17634493 : if (TREE_CODE (op) == SSA_NAME
365 : 17634493 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
366 : : return false;
367 : : }
368 : :
369 : : /* If PHI has more than one unique non-SSA arguments, it won't generate a
370 : : copy. */
371 : : tree const_op = NULL_TREE;
372 : 24201609 : for (i = 0; i < gimple_phi_num_args (phi); i++)
373 : : {
374 : 17290419 : tree op = gimple_phi_arg_def (phi, i);
375 : 17290419 : if (TREE_CODE (op) != SSA_NAME)
376 : : {
377 : 2304998 : if (const_op && !operand_equal_p (op, const_op))
378 : : return false;
379 : : const_op = op;
380 : : }
381 : : }
382 : :
383 : : return true;
384 : : }
385 : :
386 : : /* Or a statement of type _2 = _1; OR _2 = 5; may generate a copy. */
387 : :
388 : 126975471 : if (!gimple_assign_single_p (stmt))
389 : : return false;
390 : :
391 : 26991406 : tree lhs = gimple_assign_lhs (stmt);
392 : 26991406 : tree rhs = gimple_assign_rhs1 (stmt);
393 : :
394 : 26991406 : if (TREE_CODE (lhs) != SSA_NAME)
395 : : return false;
396 : :
397 : : /* lhs shouldn't flow through any abnormal edges. */
398 : 12270568 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
399 : : return false;
400 : :
401 : 12269918 : if (is_gimple_min_invariant (rhs))
402 : : return true; /* A statement of type _2 = 5;. */
403 : :
404 : 12264486 : if (TREE_CODE (rhs) != SSA_NAME)
405 : : return false;
406 : :
407 : : /* rhs shouldn't flow through any abnormal edges. */
408 : 26590 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
409 : : return false;
410 : :
411 : : /* It is possible that lhs has more alignment or value range information. By
412 : : propagating we would lose this information. So in the case that alignment
413 : : or value range information differs, we are conservative and do not
414 : : propagate.
415 : :
416 : : FIXME: Propagate alignment and value range info the same way copy-prop
417 : : does. */
418 : 49227 : if (POINTER_TYPE_P (TREE_TYPE (lhs))
419 : 1877 : && POINTER_TYPE_P (TREE_TYPE (rhs))
420 : 27427 : && SSA_NAME_PTR_INFO (lhs) != SSA_NAME_PTR_INFO (rhs))
421 : : return false;
422 : 47482 : if (!POINTER_TYPE_P (TREE_TYPE (lhs))
423 : 23673 : && !POINTER_TYPE_P (TREE_TYPE (rhs))
424 : 47482 : && SSA_NAME_RANGE_INFO (lhs) != SSA_NAME_RANGE_INFO (rhs))
425 : : return false;
426 : :
427 : : return true; /* A statement of type _2 = _1;. */
428 : : }
429 : :
430 : : /* Return all statements in cfun that could generate copies. All statements
431 : : for which stmt_may_generate_copy returns 'true'. */
432 : :
433 : : static auto_vec<gimple *>
434 : 3156518 : get_all_stmt_may_generate_copy (void)
435 : : {
436 : 3156518 : auto_vec<gimple *> result;
437 : :
438 : 3156518 : basic_block bb;
439 : 22170807 : FOR_EACH_BB_FN (bb, cfun)
440 : : {
441 : 19014289 : gimple_stmt_iterator gsi;
442 : 165004049 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
443 : : {
444 : 126975471 : gimple *s = gsi_stmt (gsi);
445 : 126975471 : if (stmt_may_generate_copy (s))
446 : 22178 : result.safe_push (s);
447 : : }
448 : :
449 : 19014289 : gphi_iterator pi;
450 : 26220857 : for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
451 : : {
452 : 7206568 : gimple *s = pi.phi ();
453 : 7206568 : if (stmt_may_generate_copy (s))
454 : 6911190 : result.safe_push (s);
455 : : }
456 : : }
457 : :
458 : 3156518 : return result;
459 : : }
460 : :
461 : : /* For each statement from given SCC, replace its usages by value
462 : : VAL. */
463 : :
464 : : static void
465 : 385249 : replace_scc_by_value (vec<gimple *> scc, tree val)
466 : : {
467 : 1544651 : for (gimple *stmt : scc)
468 : : {
469 : 388904 : tree name = gimple_get_lhs (stmt);
470 : 388904 : replace_uses_by (name, val);
471 : 388904 : bitmap_set_bit (dead_stmts, SSA_NAME_VERSION (name));
472 : : }
473 : :
474 : 385249 : if (dump_file)
475 : 56 : fprintf (dump_file, "Replacing SCC of size %d\n", scc.length ());
476 : 385249 : }
477 : :
478 : : /* Part of 'sccopy_propagate ()'. */
479 : :
480 : : static void
481 : 16954705 : sccopy_visit_op (tree op, hash_set<tree> &outer_ops,
482 : : hash_set<gimple *> &scc_set, bool &is_inner,
483 : : tree &last_outer_op)
484 : : {
485 : 16954705 : bool op_in_scc = false;
486 : :
487 : 16954705 : if (TREE_CODE (op) == SSA_NAME)
488 : : {
489 : 15228856 : gimple *op_stmt = SSA_NAME_DEF_STMT (op);
490 : 15228856 : if (scc_set.contains (op_stmt))
491 : 968432 : op_in_scc = true;
492 : : }
493 : :
494 : 15228856 : if (!op_in_scc)
495 : : {
496 : 15986273 : outer_ops.add (op);
497 : 15986273 : last_outer_op = op;
498 : 15986273 : is_inner = false;
499 : : }
500 : 16954705 : }
501 : :
502 : : /* Main function of this pass. Find and propagate all three types of copy
503 : : statements (see pass description above).
504 : :
505 : : This is an implementation of an algorithm from the paper Simple and
506 : : Efficient Construction of Static Single Assignmemnt Form[1]. It is based
507 : : on strongly-connected components (SCCs) in dataflow graph. The original
508 : : algorithm only considers PHI statements. We extend it to also consider
509 : : assignment statements of type _2 = _1;.
510 : :
511 : : The algorithm is based on this definition of a set of redundant PHIs[1]:
512 : :
513 : : A non-empty set P of PHI functions is redundant iff the PHI functions just
514 : : reference each other or one other value
515 : :
516 : : It uses this lemma[1]:
517 : :
518 : : Let P be a redundant set of PHI functions. Then there is a
519 : : strongly-connected component S subset of P that is also redundant.
520 : :
521 : : The algorithm works in this way:
522 : :
523 : : 1 Find SCCs
524 : : 2 For each SCC S in topological order:
525 : : 3 Construct set 'inner' of statements that only have other statements
526 : : from S on their right hand side
527 : : 4 Construct set 'outer' of values that originate outside S and appear on
528 : : right hand side of some statement from S
529 : : 5 If |outer| = 1, outer only contains a value v. Statements in S only
530 : : refer to each other or to v -- they are redundant. Propagate v.
531 : : Else, recurse on statements in inner.
532 : :
533 : : The implementation is non-recursive.
534 : :
535 : : References:
536 : :
537 : : [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
538 : : Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
539 : : Section 3.2. */
540 : :
541 : : static void
542 : 3156518 : sccopy_propagate ()
543 : : {
544 : 3156518 : auto_vec<gimple *> useful_stmts = get_all_stmt_may_generate_copy ();
545 : 3156518 : scc_discovery discovery;
546 : :
547 : 3156518 : auto_vec<vec<gimple *>> worklist = discovery.compute_sccs (useful_stmts);
548 : :
549 : 13971700 : while (!worklist.is_empty ())
550 : : {
551 : 6660189 : vec<gimple *> scc = worklist.pop ();
552 : :
553 : 6660189 : auto_vec<gimple *> inner;
554 : 6660189 : hash_set<tree> outer_ops;
555 : 6660189 : tree last_outer_op = NULL_TREE;
556 : :
557 : : /* Prepare hash set of PHIs in scc to query later. */
558 : 6660189 : hash_set<gimple *> scc_set;
559 : 20373601 : for (gimple *stmt : scc)
560 : 7053223 : scc_set.add (stmt);
561 : :
562 : 20373601 : for (gimple *stmt : scc)
563 : : {
564 : 7053223 : bool is_inner = true;
565 : :
566 : 7053223 : gphi *phi;
567 : 7053223 : tree op;
568 : :
569 : 7053223 : switch (gimple_code (stmt))
570 : : {
571 : 7031045 : case GIMPLE_PHI:
572 : 7031045 : phi = as_a <gphi *> (stmt);
573 : 7031045 : unsigned j;
574 : 30994617 : for (j = 0; j < gimple_phi_num_args (phi); j++)
575 : : {
576 : 16932527 : op = gimple_phi_arg_def (phi, j);
577 : 16932527 : sccopy_visit_op (op, outer_ops, scc_set, is_inner,
578 : : last_outer_op);
579 : : }
580 : : break;
581 : 22178 : case GIMPLE_ASSIGN:
582 : 22178 : op = gimple_assign_rhs1 (stmt);
583 : 22178 : sccopy_visit_op (op, outer_ops, scc_set, is_inner,
584 : : last_outer_op);
585 : 22178 : break;
586 : 0 : default:
587 : 0 : gcc_unreachable ();
588 : : }
589 : :
590 : 7053223 : if (is_inner)
591 : 123079 : inner.safe_push (stmt);
592 : : }
593 : :
594 : 6660189 : if (outer_ops.elements () == 1)
595 : : {
596 : : /* The only operand in outer_ops. */
597 : 385249 : tree outer_op = last_outer_op;
598 : 385249 : replace_scc_by_value (scc, outer_op);
599 : : }
600 : 6274940 : else if (outer_ops.elements () > 1)
601 : : {
602 : : /* Add inner sccs to worklist. */
603 : 6274940 : auto_vec<vec<gimple *>> inner_sccs
604 : 6274940 : = discovery.compute_sccs (inner);
605 : 6501933 : for (vec<gimple *> inner_scc : inner_sccs)
606 : 99679 : worklist.safe_push (inner_scc);
607 : 6274940 : }
608 : : else
609 : 0 : gcc_unreachable ();
610 : :
611 : 6660189 : scc.release ();
612 : 6660189 : }
613 : 3156518 : }
614 : :
615 : : /* Called when pass execution starts. */
616 : :
617 : : static void
618 : 3156518 : init_sccopy (void)
619 : : {
620 : : /* For propagated statements. */
621 : 0 : dead_stmts = BITMAP_ALLOC (NULL);
622 : 0 : }
623 : :
624 : : /* Called before pass execution ends. */
625 : :
626 : : static void
627 : 3156518 : finalize_sccopy (void)
628 : : {
629 : : /* Remove all propagated statements. */
630 : 3156518 : simple_dce_from_worklist (dead_stmts);
631 : 3156518 : BITMAP_FREE (dead_stmts);
632 : :
633 : : /* Propagating a constant may create dead eh edges. */
634 : 3156518 : basic_block bb;
635 : 22170807 : FOR_EACH_BB_FN (bb, cfun)
636 : 19014289 : gimple_purge_dead_eh_edges (bb);
637 : 3156518 : }
638 : :
639 : : namespace {
640 : :
641 : : const pass_data pass_data_sccopy =
642 : : {
643 : : GIMPLE_PASS, /* type */
644 : : "sccopy", /* name */
645 : : OPTGROUP_NONE, /* optinfo_flags */
646 : : TV_NONE, /* tv_id */
647 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
648 : : 0, /* properties_provided */
649 : : 0, /* properties_destroyed */
650 : : 0, /* todo_flags_start */
651 : : TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
652 : : };
653 : :
654 : : class pass_sccopy : public gimple_opt_pass
655 : : {
656 : : public:
657 : 570378 : pass_sccopy (gcc::context *ctxt)
658 : 1140756 : : gimple_opt_pass (pass_data_sccopy, ctxt)
659 : : {}
660 : :
661 : : /* opt_pass methods: */
662 : 3156585 : virtual bool gate (function *) { return true; }
663 : : virtual unsigned int execute (function *);
664 : 285189 : opt_pass * clone () final override { return new pass_sccopy (m_ctxt); }
665 : : }; // class pass_sccopy
666 : :
667 : : unsigned
668 : 3156518 : pass_sccopy::execute (function *)
669 : : {
670 : 3156518 : init_sccopy ();
671 : 3156518 : sccopy_propagate ();
672 : 3156518 : finalize_sccopy ();
673 : 3156518 : return 0;
674 : : }
675 : :
676 : : } // anon namespace
677 : :
678 : : gimple_opt_pass *
679 : 285189 : make_pass_sccopy (gcc::context *ctxt)
680 : : {
681 : 285189 : return new pass_sccopy (ctxt);
682 : : }
|