]>
Commit | Line | Data |
---|---|---|
cd794c39 FK |
1 | /* Strongly-connected copy propagation pass for the GNU compiler. |
2 | Copyright (C) 2023 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 | ||
65e41f4f | 21 | #define INCLUDE_ALGORITHM |
cd794c39 FK |
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" | |
cd794c39 FK |
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 | ||
4554a151 | 98 | namespace { |
cd794c39 FK |
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: | |
cd794c39 FK |
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 | scc_discovery::scc_discovery () | |
151 | { | |
152 | /* Create vertex struct for each SSA name. */ | |
153 | vertices = XNEWVEC (struct vertex, num_ssa_names); | |
154 | unsigned i = 0; | |
155 | for (i = 0; i < num_ssa_names; i++) | |
156 | vertices[i].active = false; | |
157 | } | |
158 | ||
159 | scc_discovery::~scc_discovery () | |
160 | { | |
161 | XDELETEVEC (vertices); | |
162 | } | |
163 | ||
164 | /* Part of 'scc_discovery::compute_sccs ()'. */ | |
165 | ||
166 | void | |
167 | scc_discovery::visit_neighbor (tree neigh_tree, unsigned parent_version) | |
168 | { | |
169 | if (TREE_CODE (neigh_tree) != SSA_NAME) | |
170 | return; /* Skip any neighbor that isn't an SSA name. */ | |
171 | unsigned neigh_version = SSA_NAME_VERSION (neigh_tree); | |
172 | ||
173 | /* Skip neighbors outside the subgraph that Tarjan currently works | |
174 | with. */ | |
175 | if (!vertices[neigh_version].active) | |
176 | return; | |
177 | ||
178 | vstate neigh_state = vertices[neigh_version].state; | |
179 | vstate parent_state = vertices[parent_version].state; | |
180 | 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 | switch (neigh_state) | |
185 | { | |
186 | case unvisited: | |
187 | worklist.safe_push (neigh_version); | |
188 | break; | |
189 | case vopen: | |
190 | case closed: | |
191 | vertices[parent_version].lowlink | |
192 | = std::min (vertices[parent_version].lowlink, | |
193 | vertices[neigh_version].index); | |
194 | break; | |
195 | case in_scc: | |
196 | /* Ignore these edges. */ | |
197 | break; | |
198 | } | |
199 | } | |
200 | 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 | if (neigh_state == closed) | |
205 | { | |
206 | vertices[parent_version].lowlink | |
207 | = std::min (vertices[parent_version].lowlink, | |
208 | 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 | scc_discovery::compute_sccs (vec<gimple *> &stmts) | |
221 | { | |
222 | auto_vec<vec<gimple *>> sccs; | |
223 | ||
224 | for (gimple *stmt : stmts) | |
225 | { | |
226 | unsigned i; | |
227 | switch (gimple_code (stmt)) | |
228 | { | |
229 | case GIMPLE_ASSIGN: | |
230 | i = SSA_NAME_VERSION (gimple_assign_lhs (stmt)); | |
231 | break; | |
232 | case GIMPLE_PHI: | |
233 | i = SSA_NAME_VERSION (gimple_phi_result (stmt)); | |
234 | break; | |
235 | default: | |
236 | gcc_unreachable (); | |
237 | } | |
238 | ||
239 | vertices[i].index = 0; | |
240 | vertices[i].lowlink = 0; | |
241 | vertices[i].state = unvisited; | |
242 | vertices[i].active = true; /* Mark the subgraph we'll be working on so | |
243 | that we don't leave it. */ | |
244 | ||
245 | worklist.safe_push (i); | |
246 | } | |
247 | ||
248 | /* Worklist loop. */ | |
249 | unsigned curr_index = 0; | |
250 | while (!worklist.is_empty ()) | |
251 | { | |
252 | unsigned i = worklist.pop (); | |
253 | gimple *stmt = SSA_NAME_DEF_STMT (ssa_name (i)); | |
254 | vstate state = vertices[i].state; | |
255 | ||
256 | if (state == unvisited) | |
257 | { | |
258 | vertices[i].state = vopen; | |
259 | ||
260 | /* Assign index to this vertex. */ | |
261 | vertices[i].index = curr_index; | |
262 | vertices[i].lowlink = curr_index; | |
263 | curr_index++; | |
264 | ||
265 | /* Put vertex on stack and also on worklist to be closed later. */ | |
266 | stack.safe_push (i); | |
267 | worklist.safe_push (i); | |
268 | } | |
269 | else if (state == vopen) | |
270 | vertices[i].state = closed; | |
271 | ||
272 | /* Visit neighbors of this vertex. */ | |
273 | tree op; | |
274 | gphi *phi; | |
275 | switch (gimple_code (stmt)) | |
276 | { | |
277 | case GIMPLE_PHI: | |
278 | phi = as_a <gphi *> (stmt); | |
279 | unsigned j; | |
280 | for (j = 0; j < gimple_phi_num_args (phi); j++) | |
281 | { | |
282 | op = gimple_phi_arg_def (phi, j); | |
283 | visit_neighbor (op, i); | |
284 | } | |
285 | break; | |
286 | case GIMPLE_ASSIGN: | |
287 | op = gimple_assign_rhs1 (stmt); | |
288 | visit_neighbor (op, i); | |
289 | break; | |
290 | default: | |
291 | gcc_unreachable (); | |
292 | } | |
293 | ||
294 | /* If we've just closed a root vertex of an scc, pop scc from stack. */ | |
295 | if (state == vopen && vertices[i].lowlink == vertices[i].index) | |
296 | { | |
297 | vec<gimple *> scc = vNULL; | |
298 | ||
299 | unsigned j; | |
300 | do | |
301 | { | |
302 | j = stack.pop (); | |
303 | scc.safe_push (SSA_NAME_DEF_STMT (ssa_name (j))); | |
304 | vertices[j].state = in_scc; | |
305 | } | |
306 | while (j != i); | |
307 | ||
308 | sccs.safe_push (scc); | |
309 | } | |
310 | } | |
311 | ||
312 | if (!stack.is_empty ()) | |
313 | gcc_unreachable (); | |
314 | ||
315 | /* Clear 'active' flags. */ | |
316 | for (gimple *stmt : stmts) | |
317 | { | |
318 | unsigned i; | |
319 | switch (gimple_code (stmt)) | |
320 | { | |
321 | case GIMPLE_ASSIGN: | |
322 | i = SSA_NAME_VERSION (gimple_assign_lhs (stmt)); | |
323 | break; | |
324 | case GIMPLE_PHI: | |
325 | i = SSA_NAME_VERSION (gimple_phi_result (stmt)); | |
326 | break; | |
327 | default: | |
328 | gcc_unreachable (); | |
329 | } | |
330 | ||
331 | vertices[i].active = false; | |
332 | } | |
333 | ||
334 | return sccs; | |
335 | } | |
336 | ||
4554a151 AP |
337 | } // anon namespace |
338 | ||
cd794c39 FK |
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 | stmt_may_generate_copy (gimple *stmt) | |
350 | { | |
351 | /* A PHI may generate a copy. */ | |
352 | if (gimple_code (stmt) == GIMPLE_PHI) | |
353 | { | |
354 | gphi *phi = as_a <gphi *> (stmt); | |
355 | ||
356 | /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs. */ | |
357 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi))) | |
358 | return false; | |
359 | ||
360 | unsigned i; | |
361 | for (i = 0; i < gimple_phi_num_args (phi); i++) | |
362 | { | |
363 | tree op = gimple_phi_arg_def (phi, i); | |
364 | if (TREE_CODE (op) == SSA_NAME | |
365 | && 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 | for (i = 0; i < gimple_phi_num_args (phi); i++) | |
373 | { | |
374 | tree op = gimple_phi_arg_def (phi, i); | |
375 | if (TREE_CODE (op) != SSA_NAME) | |
376 | { | |
377 | 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 | if (!gimple_assign_single_p (stmt)) | |
389 | return false; | |
390 | ||
391 | tree lhs = gimple_assign_lhs (stmt); | |
392 | tree rhs = gimple_assign_rhs1 (stmt); | |
393 | ||
394 | if (TREE_CODE (lhs) != SSA_NAME) | |
395 | return false; | |
396 | ||
397 | /* lhs shouldn't flow through any abnormal edges. */ | |
398 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) | |
399 | return false; | |
400 | ||
401 | if (is_gimple_min_invariant (rhs)) | |
402 | return true; /* A statement of type _2 = 5;. */ | |
403 | ||
404 | if (TREE_CODE (rhs) != SSA_NAME) | |
405 | return false; | |
406 | ||
407 | /* rhs shouldn't flow through any abnormal edges. */ | |
408 | 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 | if (POINTER_TYPE_P (TREE_TYPE (lhs)) | |
419 | && POINTER_TYPE_P (TREE_TYPE (rhs)) | |
420 | && SSA_NAME_PTR_INFO (lhs) != SSA_NAME_PTR_INFO (rhs)) | |
421 | return false; | |
422 | if (!POINTER_TYPE_P (TREE_TYPE (lhs)) | |
423 | && !POINTER_TYPE_P (TREE_TYPE (rhs)) | |
424 | && 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 | get_all_stmt_may_generate_copy (void) | |
435 | { | |
436 | auto_vec<gimple *> result; | |
437 | ||
438 | basic_block bb; | |
439 | FOR_EACH_BB_FN (bb, cfun) | |
440 | { | |
441 | gimple_stmt_iterator gsi; | |
442 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
443 | { | |
444 | gimple *s = gsi_stmt (gsi); | |
445 | if (stmt_may_generate_copy (s)) | |
446 | result.safe_push (s); | |
447 | } | |
448 | ||
449 | gphi_iterator pi; | |
450 | for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) | |
451 | { | |
452 | gimple *s = pi.phi (); | |
453 | if (stmt_may_generate_copy (s)) | |
454 | result.safe_push (s); | |
455 | } | |
456 | } | |
457 | ||
458 | return result; | |
459 | } | |
460 | ||
461 | /* For each statement from given SCC, replace its usages by value | |
462 | VAL. */ | |
463 | ||
464 | static void | |
465 | replace_scc_by_value (vec<gimple *> scc, tree val) | |
466 | { | |
467 | for (gimple *stmt : scc) | |
468 | { | |
469 | tree name = gimple_get_lhs (stmt); | |
470 | replace_uses_by (name, val); | |
471 | bitmap_set_bit (dead_stmts, SSA_NAME_VERSION (name)); | |
472 | } | |
473 | ||
474 | if (dump_file) | |
475 | fprintf (dump_file, "Replacing SCC of size %d\n", scc.length ()); | |
476 | } | |
477 | ||
478 | /* Part of 'sccopy_propagate ()'. */ | |
479 | ||
480 | static void | |
481 | 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 | bool op_in_scc = false; | |
486 | ||
487 | if (TREE_CODE (op) == SSA_NAME) | |
488 | { | |
489 | gimple *op_stmt = SSA_NAME_DEF_STMT (op); | |
490 | if (scc_set.contains (op_stmt)) | |
491 | op_in_scc = true; | |
492 | } | |
493 | ||
494 | if (!op_in_scc) | |
495 | { | |
496 | outer_ops.add (op); | |
497 | last_outer_op = op; | |
498 | is_inner = false; | |
499 | } | |
500 | } | |
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 | sccopy_propagate () | |
543 | { | |
544 | auto_vec<gimple *> useful_stmts = get_all_stmt_may_generate_copy (); | |
545 | scc_discovery discovery; | |
546 | ||
547 | auto_vec<vec<gimple *>> worklist = discovery.compute_sccs (useful_stmts); | |
548 | ||
549 | while (!worklist.is_empty ()) | |
550 | { | |
551 | vec<gimple *> scc = worklist.pop (); | |
552 | ||
553 | auto_vec<gimple *> inner; | |
554 | hash_set<tree> outer_ops; | |
555 | tree last_outer_op = NULL_TREE; | |
556 | ||
557 | /* Prepare hash set of PHIs in scc to query later. */ | |
558 | hash_set<gimple *> scc_set; | |
559 | for (gimple *stmt : scc) | |
560 | scc_set.add (stmt); | |
561 | ||
562 | for (gimple *stmt : scc) | |
563 | { | |
564 | bool is_inner = true; | |
565 | ||
566 | gphi *phi; | |
567 | tree op; | |
568 | ||
569 | switch (gimple_code (stmt)) | |
570 | { | |
571 | case GIMPLE_PHI: | |
572 | phi = as_a <gphi *> (stmt); | |
573 | unsigned j; | |
574 | for (j = 0; j < gimple_phi_num_args (phi); j++) | |
575 | { | |
576 | op = gimple_phi_arg_def (phi, j); | |
577 | sccopy_visit_op (op, outer_ops, scc_set, is_inner, | |
578 | last_outer_op); | |
579 | } | |
580 | break; | |
581 | case GIMPLE_ASSIGN: | |
582 | op = gimple_assign_rhs1 (stmt); | |
583 | sccopy_visit_op (op, outer_ops, scc_set, is_inner, | |
584 | last_outer_op); | |
585 | break; | |
586 | default: | |
587 | gcc_unreachable (); | |
588 | } | |
589 | ||
590 | if (is_inner) | |
591 | inner.safe_push (stmt); | |
592 | } | |
593 | ||
594 | if (outer_ops.elements () == 1) | |
595 | { | |
596 | /* The only operand in outer_ops. */ | |
597 | tree outer_op = last_outer_op; | |
598 | replace_scc_by_value (scc, outer_op); | |
599 | } | |
600 | else if (outer_ops.elements () > 1) | |
601 | { | |
602 | /* Add inner sccs to worklist. */ | |
603 | auto_vec<vec<gimple *>> inner_sccs | |
604 | = discovery.compute_sccs (inner); | |
605 | for (vec<gimple *> inner_scc : inner_sccs) | |
606 | worklist.safe_push (inner_scc); | |
607 | } | |
608 | else | |
609 | gcc_unreachable (); | |
610 | ||
611 | scc.release (); | |
612 | } | |
613 | } | |
614 | ||
615 | /* Called when pass execution starts. */ | |
616 | ||
617 | static void | |
618 | init_sccopy (void) | |
619 | { | |
620 | /* For propagated statements. */ | |
621 | dead_stmts = BITMAP_ALLOC (NULL); | |
622 | } | |
623 | ||
624 | /* Called before pass execution ends. */ | |
625 | ||
626 | static void | |
627 | finalize_sccopy (void) | |
628 | { | |
629 | /* Remove all propagated statements. */ | |
630 | simple_dce_from_worklist (dead_stmts); | |
631 | BITMAP_FREE (dead_stmts); | |
632 | ||
633 | /* Propagating a constant may create dead eh edges. */ | |
634 | basic_block bb; | |
635 | FOR_EACH_BB_FN (bb, cfun) | |
636 | gimple_purge_dead_eh_edges (bb); | |
637 | } | |
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 | pass_sccopy (gcc::context *ctxt) | |
658 | : gimple_opt_pass (pass_data_sccopy, ctxt) | |
659 | {} | |
660 | ||
661 | /* opt_pass methods: */ | |
662 | virtual bool gate (function *) { return true; } | |
663 | virtual unsigned int execute (function *); | |
664 | opt_pass * clone () final override { return new pass_sccopy (m_ctxt); } | |
665 | }; // class pass_sccopy | |
666 | ||
667 | unsigned | |
668 | pass_sccopy::execute (function *) | |
669 | { | |
670 | init_sccopy (); | |
671 | sccopy_propagate (); | |
672 | finalize_sccopy (); | |
673 | return 0; | |
674 | } | |
675 | ||
676 | } // anon namespace | |
677 | ||
678 | gimple_opt_pass * | |
679 | make_pass_sccopy (gcc::context *ctxt) | |
680 | { | |
681 | return new pass_sccopy (ctxt); | |
682 | } |