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 : : namespace {
96 : :
97 : : /* State of vertex during SCC discovery.
98 : :
99 : : unvisited Vertex hasn't yet been popped from worklist.
100 : : vopen DFS has visited vertex for the first time. Vertex has been put
101 : : on Tarjan stack.
102 : : closed DFS has backtracked through vertex. At this point, vertex
103 : : doesn't have any unvisited neighbors.
104 : : in_scc Vertex has been popped from Tarjan stack. */
105 : :
106 : : enum vstate
107 : : {
108 : : unvisited,
109 : : vopen,
110 : : closed,
111 : : in_scc
112 : : };
113 : :
114 : : /* Information about a vertex. Used by SCC discovery. */
115 : :
116 : : struct vertex
117 : : {
118 : : bool active; /* scc_discovery::compute_sccs () only considers a subgraph of
119 : : the whole dataflow graph. It uses this flag so that it knows
120 : : which vertices are part of this subgraph. */
121 : : vstate state;
122 : : unsigned index;
123 : : unsigned lowlink;
124 : : };
125 : :
126 : : /* SCC discovery.
127 : :
128 : : Used to find SCCs in a dataflow graph. Implements Tarjan's SCC
129 : : algorithm. */
130 : :
131 : : class scc_discovery
132 : : {
133 : : public:
134 : : scc_discovery ();
135 : : ~scc_discovery ();
136 : : auto_vec<vec<gimple *>> compute_sccs (vec<gimple *> &stmts);
137 : :
138 : : private:
139 : : vertex* vertices; /* Indexed by SSA_NAME_VERSION. */
140 : : auto_vec<unsigned> worklist; /* DFS stack. */
141 : : auto_vec<unsigned> stack; /* Tarjan stack. */
142 : :
143 : : void visit_neighbor (tree neigh_tree, unsigned parent_vxnum);
144 : : };
145 : :
146 : 3235055 : scc_discovery::scc_discovery ()
147 : : {
148 : : /* Create vertex struct for each SSA name. */
149 : 6470110 : vertices = XNEWVEC (struct vertex, num_ssa_names);
150 : 3235055 : unsigned i = 0;
151 : 121412152 : for (i = 0; i < num_ssa_names; i++)
152 : 118177097 : vertices[i].active = false;
153 : 3235055 : }
154 : :
155 : 3235055 : scc_discovery::~scc_discovery ()
156 : : {
157 : 3235055 : XDELETEVEC (vertices);
158 : 3235055 : }
159 : :
160 : : /* Part of 'scc_discovery::compute_sccs ()'. */
161 : :
162 : : void
163 : 41990187 : scc_discovery::visit_neighbor (tree neigh_tree, unsigned parent_version)
164 : : {
165 : 41990187 : if (TREE_CODE (neigh_tree) != SSA_NAME)
166 : 32170204 : return; /* Skip any neighbor that isn't an SSA name. */
167 : 37841980 : unsigned neigh_version = SSA_NAME_VERSION (neigh_tree);
168 : :
169 : : /* Skip neighbors outside the subgraph that Tarjan currently works
170 : : with. */
171 : 37841980 : if (!vertices[neigh_version].active)
172 : : return;
173 : :
174 : 9819983 : vstate neigh_state = vertices[neigh_version].state;
175 : 9819983 : vstate parent_state = vertices[parent_version].state;
176 : 9819983 : if (parent_state == vopen) /* We're currently opening parent. */
177 : : {
178 : : /* Put unvisited neighbors on worklist. Update lowlink of parent
179 : : vertex according to indices of neighbors present on stack. */
180 : 3670425 : switch (neigh_state)
181 : : {
182 : 2573392 : case unvisited:
183 : 2573392 : worklist.safe_push (neigh_version);
184 : 2573392 : break;
185 : 538692 : case vopen:
186 : 538692 : case closed:
187 : 538692 : vertices[parent_version].lowlink
188 : 538692 : = std::min (vertices[parent_version].lowlink,
189 : : vertices[neigh_version].index);
190 : 538692 : break;
191 : : case in_scc:
192 : : /* Ignore these edges. */
193 : : break;
194 : : }
195 : : }
196 : 6149558 : else if (parent_state == closed) /* We're currently closing parent. */
197 : : {
198 : : /* Update lowlink of parent vertex according to lowlinks of
199 : : children of parent (in terms of DFS tree). */
200 : 3842451 : if (neigh_state == closed)
201 : : {
202 : 724235 : vertices[parent_version].lowlink
203 : 724235 : = std::min (vertices[parent_version].lowlink,
204 : : vertices[neigh_version].lowlink);
205 : : }
206 : : }
207 : : }
208 : :
209 : : /* Compute SCCs in dataflow graph on given statements 'stmts'. Ignore
210 : : statements outside 'stmts'. Return the SCCs in a reverse topological
211 : : order.
212 : :
213 : : stmt_may_generate_copy () must be true for all statements from 'stmts'! */
214 : :
215 : : auto_vec<vec<gimple *>>
216 : 9853949 : scc_discovery::compute_sccs (vec<gimple *> &stmts)
217 : : {
218 : 9853949 : auto_vec<vec<gimple *>> sccs;
219 : :
220 : 19529276 : for (gimple *stmt : stmts)
221 : : {
222 : 7480769 : unsigned i;
223 : 7480769 : switch (gimple_code (stmt))
224 : : {
225 : 22521 : case GIMPLE_ASSIGN:
226 : 22521 : i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
227 : 22521 : break;
228 : 7458248 : case GIMPLE_PHI:
229 : 7458248 : i = SSA_NAME_VERSION (gimple_phi_result (stmt));
230 : 7458248 : break;
231 : 0 : default:
232 : 0 : gcc_unreachable ();
233 : : }
234 : :
235 : 7480769 : vertices[i].index = 0;
236 : 7480769 : vertices[i].lowlink = 0;
237 : 7480769 : vertices[i].state = unvisited;
238 : 7480769 : vertices[i].active = true; /* Mark the subgraph we'll be working on so
239 : : that we don't leave it. */
240 : :
241 : 7480769 : worklist.safe_push (i);
242 : : }
243 : :
244 : : /* Worklist loop. */
245 : : unsigned curr_index = 0;
246 : 27388879 : while (!worklist.is_empty ())
247 : : {
248 : 17534930 : unsigned i = worklist.pop ();
249 : 17534930 : gimple *stmt = SSA_NAME_DEF_STMT (ssa_name (i));
250 : 17534930 : vstate state = vertices[i].state;
251 : :
252 : 17534930 : if (state == unvisited)
253 : : {
254 : 7480769 : vertices[i].state = vopen;
255 : :
256 : : /* Assign index to this vertex. */
257 : 7480769 : vertices[i].index = curr_index;
258 : 7480769 : vertices[i].lowlink = curr_index;
259 : 7480769 : curr_index++;
260 : :
261 : : /* Put vertex on stack and also on worklist to be closed later. */
262 : 7480769 : stack.safe_push (i);
263 : 7480769 : worklist.safe_push (i);
264 : : }
265 : 10054161 : else if (state == vopen)
266 : 7480769 : vertices[i].state = closed;
267 : :
268 : : /* Visit neighbors of this vertex. */
269 : 17534930 : tree op;
270 : 17534930 : gphi *phi;
271 : 17534930 : switch (gimple_code (stmt))
272 : : {
273 : 17488999 : case GIMPLE_PHI:
274 : 17488999 : phi = as_a <gphi *> (stmt);
275 : 17488999 : unsigned j;
276 : 76922254 : for (j = 0; j < gimple_phi_num_args (phi); j++)
277 : : {
278 : 41944256 : op = gimple_phi_arg_def (phi, j);
279 : 41944256 : visit_neighbor (op, i);
280 : : }
281 : : break;
282 : 45931 : case GIMPLE_ASSIGN:
283 : 45931 : op = gimple_assign_rhs1 (stmt);
284 : 45931 : visit_neighbor (op, i);
285 : 45931 : break;
286 : 0 : default:
287 : 0 : gcc_unreachable ();
288 : : }
289 : :
290 : : /* If we've just closed a root vertex of an scc, pop scc from stack. */
291 : 17534930 : if (state == vopen && vertices[i].lowlink == vertices[i].index)
292 : : {
293 : 7026895 : vec<gimple *> scc = vNULL;
294 : :
295 : 7480769 : unsigned j;
296 : 7480769 : do
297 : : {
298 : 7480769 : j = stack.pop ();
299 : 7480769 : scc.safe_push (SSA_NAME_DEF_STMT (ssa_name (j)));
300 : 7480769 : vertices[j].state = in_scc;
301 : : }
302 : 7480769 : while (j != i);
303 : :
304 : 7026895 : sccs.safe_push (scc);
305 : : }
306 : : }
307 : :
308 : 9853949 : if (!stack.is_empty ())
309 : 0 : gcc_unreachable ();
310 : :
311 : : /* Clear 'active' flags. */
312 : 19529276 : for (gimple *stmt : stmts)
313 : : {
314 : 7480769 : unsigned i;
315 : 7480769 : switch (gimple_code (stmt))
316 : : {
317 : 22521 : case GIMPLE_ASSIGN:
318 : 22521 : i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
319 : 22521 : break;
320 : 7458248 : case GIMPLE_PHI:
321 : 7458248 : i = SSA_NAME_VERSION (gimple_phi_result (stmt));
322 : 7458248 : break;
323 : 0 : default:
324 : 0 : gcc_unreachable ();
325 : : }
326 : :
327 : 7480769 : vertices[i].active = false;
328 : : }
329 : :
330 : 9853949 : return sccs;
331 : : }
332 : :
333 : : } // anon namespace
334 : :
335 : : /* Could this statement potentially be a copy statement?
336 : :
337 : : This pass only considers statements for which this function returns 'true'.
338 : : Those are basically PHI functions and assignment statements similar to
339 : :
340 : : _2 = _1;
341 : : or
342 : : _2 = 5; */
343 : :
344 : : static bool
345 : 140386636 : stmt_may_generate_copy (gimple *stmt)
346 : : {
347 : : /* A PHI may generate a copy. */
348 : 140386636 : if (gimple_code (stmt) == GIMPLE_PHI)
349 : : {
350 : 7623036 : gphi *phi = as_a <gphi *> (stmt);
351 : :
352 : : /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs. */
353 : 7623036 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi)))
354 : : return false;
355 : :
356 : : unsigned i;
357 : 26185866 : for (i = 0; i < gimple_phi_num_args (phi); i++)
358 : : {
359 : 18574354 : tree op = gimple_phi_arg_def (phi, i);
360 : 18574354 : if (TREE_CODE (op) == SSA_NAME
361 : 18574354 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
362 : : return false;
363 : : }
364 : :
365 : : /* If PHI has more than one unique non-SSA arguments, it won't generate a
366 : : copy. */
367 : : tree const_op = NULL_TREE;
368 : 25518990 : for (i = 0; i < gimple_phi_num_args (phi); i++)
369 : : {
370 : 18209897 : tree op = gimple_phi_arg_def (phi, i);
371 : 18209897 : if (TREE_CODE (op) != SSA_NAME)
372 : : {
373 : 2443680 : if (const_op && !operand_equal_p (op, const_op))
374 : : return false;
375 : : const_op = op;
376 : : }
377 : : }
378 : :
379 : : return true;
380 : : }
381 : :
382 : : /* Or a statement of type _2 = _1; OR _2 = 5; may generate a copy. */
383 : :
384 : 132763600 : if (!gimple_assign_single_p (stmt))
385 : : return false;
386 : :
387 : 27735202 : tree lhs = gimple_assign_lhs (stmt);
388 : 27735202 : tree rhs = gimple_assign_rhs1 (stmt);
389 : :
390 : 27735202 : if (TREE_CODE (lhs) != SSA_NAME)
391 : : return false;
392 : :
393 : : /* lhs shouldn't flow through any abnormal edges. */
394 : 12720587 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
395 : : return false;
396 : :
397 : 12719933 : if (is_gimple_min_invariant (rhs))
398 : : return true; /* A statement of type _2 = 5;. */
399 : :
400 : 12714410 : if (TREE_CODE (rhs) != SSA_NAME)
401 : : return false;
402 : :
403 : : /* rhs shouldn't flow through any abnormal edges. */
404 : 28764 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
405 : : return false;
406 : :
407 : : /* It is possible that lhs has more alignment or value range information. By
408 : : propagating we would lose this information. So in the case that alignment
409 : : or value range information differs, we are conservative and do not
410 : : propagate.
411 : :
412 : : FIXME: Propagate alignment and value range info the same way copy-prop
413 : : does. */
414 : 53283 : if (POINTER_TYPE_P (TREE_TYPE (lhs))
415 : 2177 : && POINTER_TYPE_P (TREE_TYPE (rhs))
416 : 29905 : && SSA_NAME_PTR_INFO (lhs) != SSA_NAME_PTR_INFO (rhs))
417 : : return false;
418 : 51282 : if (!POINTER_TYPE_P (TREE_TYPE (lhs))
419 : 25551 : && !POINTER_TYPE_P (TREE_TYPE (rhs))
420 : 51282 : && SSA_NAME_RANGE_INFO (lhs) != SSA_NAME_RANGE_INFO (rhs))
421 : : return false;
422 : :
423 : : return true; /* A statement of type _2 = _1;. */
424 : : }
425 : :
426 : : /* Return all statements in cfun that could generate copies. All statements
427 : : for which stmt_may_generate_copy returns 'true'. */
428 : :
429 : : static auto_vec<gimple *>
430 : 3235055 : get_all_stmt_may_generate_copy (void)
431 : : {
432 : 3235055 : auto_vec<gimple *> result;
433 : :
434 : 3235055 : basic_block bb;
435 : 23072366 : FOR_EACH_BB_FN (bb, cfun)
436 : : {
437 : 19837311 : gimple_stmt_iterator gsi;
438 : 172438222 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
439 : : {
440 : 132763600 : gimple *s = gsi_stmt (gsi);
441 : 132763600 : if (stmt_may_generate_copy (s))
442 : 22521 : result.safe_push (s);
443 : : }
444 : :
445 : 19837311 : gphi_iterator pi;
446 : 27460347 : for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
447 : : {
448 : 7623036 : gimple *s = pi.phi ();
449 : 7623036 : if (stmt_may_generate_copy (s))
450 : 7309093 : result.safe_push (s);
451 : : }
452 : : }
453 : :
454 : 3235055 : return result;
455 : : }
456 : :
457 : : /* SCC copy propagation
458 : :
459 : : 'scc_copy_prop::propagate ()' is the main function of this pass. */
460 : :
461 : : class scc_copy_prop
462 : : {
463 : : public:
464 : : scc_copy_prop ();
465 : : ~scc_copy_prop ();
466 : : void propagate ();
467 : :
468 : : private:
469 : : /* Bitmap tracking statements which were propagated so that they can be
470 : : removed at the end of the pass. */
471 : : bitmap dead_stmts;
472 : :
473 : : void visit_op (tree op, hash_set<tree> &outer_ops,
474 : : hash_set<gimple *> &scc_set, bool &is_inner,
475 : : tree &last_outer_op);
476 : : void replace_scc_by_value (vec<gimple *> scc, tree val);
477 : : };
478 : :
479 : : /* For each statement from given SCC, replace its usages by value
480 : : VAL. */
481 : :
482 : : void
483 : 408001 : scc_copy_prop::replace_scc_by_value (vec<gimple *> scc, tree val)
484 : : {
485 : 1636522 : for (gimple *stmt : scc)
486 : : {
487 : 412519 : tree name = gimple_get_lhs (stmt);
488 : 412519 : replace_uses_by (name, val);
489 : 412519 : bitmap_set_bit (dead_stmts, SSA_NAME_VERSION (name));
490 : : }
491 : :
492 : 408001 : if (dump_file)
493 : 56 : fprintf (dump_file, "Replacing SCC of size %d\n", scc.length ());
494 : 408001 : }
495 : :
496 : : /* Part of 'scc_copy_prop::propagate ()'. */
497 : :
498 : : void
499 : 17888778 : scc_copy_prop::visit_op (tree op, hash_set<tree> &outer_ops,
500 : : hash_set<gimple *> &scc_set, bool &is_inner,
501 : : tree &last_outer_op)
502 : : {
503 : 17888778 : bool op_in_scc = false;
504 : :
505 : 17888778 : if (TREE_CODE (op) == SSA_NAME)
506 : : {
507 : 16060086 : gimple *op_stmt = SSA_NAME_DEF_STMT (op);
508 : 16060086 : if (scc_set.contains (op_stmt))
509 : 1098565 : op_in_scc = true;
510 : : }
511 : :
512 : 16060086 : if (!op_in_scc)
513 : : {
514 : 16790213 : outer_ops.add (op);
515 : 16790213 : last_outer_op = op;
516 : 16790213 : is_inner = false;
517 : : }
518 : 17888778 : }
519 : :
520 : : /* Main function of this pass. Find and propagate all three types of copy
521 : : statements (see pass description above).
522 : :
523 : : This is an implementation of an algorithm from the paper Simple and
524 : : Efficient Construction of Static Single Assignmemnt Form[1]. It is based
525 : : on strongly-connected components (SCCs) in dataflow graph. The original
526 : : algorithm only considers PHI statements. We extend it to also consider
527 : : assignment statements of type _2 = _1;.
528 : :
529 : : The algorithm is based on this definition of a set of redundant PHIs[1]:
530 : :
531 : : A non-empty set P of PHI functions is redundant iff the PHI functions just
532 : : reference each other or one other value
533 : :
534 : : It uses this lemma[1]:
535 : :
536 : : Let P be a redundant set of PHI functions. Then there is a
537 : : strongly-connected component S subset of P that is also redundant.
538 : :
539 : : The algorithm works in this way:
540 : :
541 : : 1 Find SCCs
542 : : 2 For each SCC S in topological order:
543 : : 3 Construct set 'inner' of statements that only have other statements
544 : : from S on their right hand side
545 : : 4 Construct set 'outer' of values that originate outside S and appear on
546 : : right hand side of some statement from S
547 : : 5 If |outer| = 1, outer only contains a value v. Statements in S only
548 : : refer to each other or to v -- they are redundant. Propagate v.
549 : : Else, recurse on statements in inner.
550 : :
551 : : The implementation is non-recursive.
552 : :
553 : : References:
554 : :
555 : : [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
556 : : Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
557 : : Section 3.2. */
558 : :
559 : : void
560 : 3235055 : scc_copy_prop::propagate ()
561 : : {
562 : 3235055 : auto_vec<gimple *> useful_stmts = get_all_stmt_may_generate_copy ();
563 : 3235055 : scc_discovery discovery;
564 : :
565 : 3235055 : auto_vec<vec<gimple *>> worklist = discovery.compute_sccs (useful_stmts);
566 : :
567 : 14518762 : while (!worklist.is_empty ())
568 : : {
569 : 7026895 : vec<gimple *> scc = worklist.pop ();
570 : :
571 : 7026895 : auto_vec<gimple *> inner;
572 : 7026895 : hash_set<tree> outer_ops;
573 : 7026895 : tree last_outer_op = NULL_TREE;
574 : :
575 : : /* Prepare hash set of PHIs in scc to query later. */
576 : 7026895 : hash_set<gimple *> scc_set;
577 : 21534559 : for (gimple *stmt : scc)
578 : 7480769 : scc_set.add (stmt);
579 : :
580 : 21534559 : for (gimple *stmt : scc)
581 : : {
582 : 7480769 : bool is_inner = true;
583 : :
584 : 7480769 : gphi *phi;
585 : 7480769 : tree op;
586 : :
587 : 7480769 : switch (gimple_code (stmt))
588 : : {
589 : 7458248 : case GIMPLE_PHI:
590 : 7458248 : phi = as_a <gphi *> (stmt);
591 : 7458248 : unsigned j;
592 : 32782753 : for (j = 0; j < gimple_phi_num_args (phi); j++)
593 : : {
594 : 17866257 : op = gimple_phi_arg_def (phi, j);
595 : 17866257 : visit_op (op, outer_ops, scc_set, is_inner, last_outer_op);
596 : : }
597 : : break;
598 : 22521 : case GIMPLE_ASSIGN:
599 : 22521 : op = gimple_assign_rhs1 (stmt);
600 : 22521 : visit_op (op, outer_ops, scc_set, is_inner, last_outer_op);
601 : 22521 : break;
602 : 0 : default:
603 : 0 : gcc_unreachable ();
604 : : }
605 : :
606 : 7480769 : if (is_inner)
607 : 153096 : inner.safe_push (stmt);
608 : : }
609 : :
610 : 7026895 : if (outer_ops.elements () == 1)
611 : : {
612 : : /* The only operand in outer_ops. */
613 : 408001 : tree outer_op = last_outer_op;
614 : 408001 : replace_scc_by_value (scc, outer_op);
615 : : }
616 : 6618894 : else if (outer_ops.elements () > 1)
617 : : {
618 : : /* Add inner sccs to worklist. */
619 : 6618894 : auto_vec<vec<gimple *>> inner_sccs
620 : 6618894 : = discovery.compute_sccs (inner);
621 : 6891968 : for (vec<gimple *> inner_scc : inner_sccs)
622 : 122030 : worklist.safe_push (inner_scc);
623 : 6618894 : }
624 : : else
625 : 0 : gcc_unreachable ();
626 : :
627 : 7026895 : scc.release ();
628 : 7026895 : }
629 : 3235055 : }
630 : :
631 : 3235055 : scc_copy_prop::scc_copy_prop ()
632 : : {
633 : : /* For propagated statements. */
634 : 3235055 : dead_stmts = BITMAP_ALLOC (NULL);
635 : 3235055 : }
636 : :
637 : 3235055 : scc_copy_prop::~scc_copy_prop ()
638 : : {
639 : : /* Remove all propagated statements. */
640 : 3235055 : simple_dce_from_worklist (dead_stmts);
641 : 3235055 : BITMAP_FREE (dead_stmts);
642 : :
643 : : /* Propagating a constant may create dead eh edges. */
644 : 3235055 : basic_block bb;
645 : 23072366 : FOR_EACH_BB_FN (bb, cfun)
646 : 19837311 : gimple_purge_dead_eh_edges (bb);
647 : 3235055 : }
648 : :
649 : : namespace {
650 : :
651 : : const pass_data pass_data_sccopy =
652 : : {
653 : : GIMPLE_PASS, /* type */
654 : : "sccopy", /* name */
655 : : OPTGROUP_NONE, /* optinfo_flags */
656 : : TV_NONE, /* tv_id */
657 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
658 : : 0, /* properties_provided */
659 : : 0, /* properties_destroyed */
660 : : 0, /* todo_flags_start */
661 : : TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
662 : : };
663 : :
664 : : class pass_sccopy : public gimple_opt_pass
665 : : {
666 : : public:
667 : 560228 : pass_sccopy (gcc::context *ctxt)
668 : 1120456 : : gimple_opt_pass (pass_data_sccopy, ctxt)
669 : : {}
670 : :
671 : : /* opt_pass methods: */
672 : 3235127 : virtual bool gate (function *) { return true; }
673 : : virtual unsigned int execute (function *);
674 : 280114 : opt_pass * clone () final override { return new pass_sccopy (m_ctxt); }
675 : : }; // class pass_sccopy
676 : :
677 : : unsigned
678 : 3235055 : pass_sccopy::execute (function *)
679 : : {
680 : 3235055 : scc_copy_prop sccopy;
681 : 3235055 : sccopy.propagate ();
682 : 6470110 : return 0;
683 : 3235055 : }
684 : :
685 : : } // anon namespace
686 : :
687 : : gimple_opt_pass *
688 : 280114 : make_pass_sccopy (gcc::context *ctxt)
689 : : {
690 : 280114 : return new pass_sccopy (ctxt);
691 : : }
|
