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>
5 This file is part of GCC.
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
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
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/>. */
21 #define INCLUDE_ALGORITHM
24 #include "coretypes.h"
28 #include "tree-pass.h"
30 #include "gimple-iterator.h"
33 #include "ssa-iterators.h"
34 #include "gimple-fold.h"
39 #include "tree-ssa-dce.h"
40 #include "fold-const.h"
42 /* Strongly connected copy propagation pass.
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
48 1 An assignment statement with a single argument.
53 2 A degenerate PHI statement. A degenerate PHI is a PHI that only refers to
54 itself or one other value.
57 _6 = PHI <_6, _6, _1, _1>;
60 3 A set of PHI statements that only refer to each other or to one other
65 _10 = PHI <_8, _9, _1>;
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
72 _3 = _2; // Replace all occurences of _3 by _2
76 _10 = PHI <_8, _9, _1>; // Replace all occurences of _8, _9 and _10 by _1
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.
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
91 [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
92 Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
95 /* Bitmap tracking statements which were propagated to be removed at the end of
98 static bitmap dead_stmts
;
100 /* State of vertex during SCC discovery.
102 unvisited Vertex hasn't yet been popped from worklist.
103 vopen DFS has visited vertex for the first time. Vertex has been put
105 closed DFS has backtracked through vertex. At this point, vertex
106 doesn't have any unvisited neighbors.
107 in_scc Vertex has been popped from Tarjan stack. */
117 /* Information about a vertex. Used by SCC discovery. */
121 bool active
; /* scc_discovery::compute_sccs () only considers a subgraph of
122 the whole dataflow graph. It uses this flag so that it knows
123 which vertices are part of this subgraph. */
131 Used to find SCCs in a dataflow graph. Implements Tarjan's SCC
139 auto_vec
<vec
<gimple
*>> compute_sccs (vec
<gimple
*> &stmts
);
142 unsigned curr_generation
= 0;
143 vertex
* vertices
; /* Indexed by SSA_NAME_VERSION. */
144 auto_vec
<unsigned> worklist
; /* DFS stack. */
145 auto_vec
<unsigned> stack
; /* Tarjan stack. */
147 void visit_neighbor (tree neigh_tree
, unsigned parent_vxnum
);
150 scc_discovery::scc_discovery ()
152 /* Create vertex struct for each SSA name. */
153 vertices
= XNEWVEC (struct vertex
, num_ssa_names
);
155 for (i
= 0; i
< num_ssa_names
; i
++)
156 vertices
[i
].active
= false;
159 scc_discovery::~scc_discovery ()
161 XDELETEVEC (vertices
);
164 /* Part of 'scc_discovery::compute_sccs ()'. */
167 scc_discovery::visit_neighbor (tree neigh_tree
, unsigned parent_version
)
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
);
173 /* Skip neighbors outside the subgraph that Tarjan currently works
175 if (!vertices
[neigh_version
].active
)
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. */
182 /* Put unvisited neighbors on worklist. Update lowlink of parent
183 vertex according to indices of neighbors present on stack. */
187 worklist
.safe_push (neigh_version
);
191 vertices
[parent_version
].lowlink
192 = std::min (vertices
[parent_version
].lowlink
,
193 vertices
[neigh_version
].index
);
196 /* Ignore these edges. */
200 else if (parent_state
== closed
) /* We're currently closing parent. */
202 /* Update lowlink of parent vertex according to lowlinks of
203 children of parent (in terms of DFS tree). */
204 if (neigh_state
== closed
)
206 vertices
[parent_version
].lowlink
207 = std::min (vertices
[parent_version
].lowlink
,
208 vertices
[neigh_version
].lowlink
);
213 /* Compute SCCs in dataflow graph on given statements 'stmts'. Ignore
214 statements outside 'stmts'. Return the SCCs in a reverse topological
217 stmt_may_generate_copy () must be true for all statements from 'stmts'! */
219 auto_vec
<vec
<gimple
*>>
220 scc_discovery::compute_sccs (vec
<gimple
*> &stmts
)
222 auto_vec
<vec
<gimple
*>> sccs
;
224 for (gimple
*stmt
: stmts
)
227 switch (gimple_code (stmt
))
230 i
= SSA_NAME_VERSION (gimple_assign_lhs (stmt
));
233 i
= SSA_NAME_VERSION (gimple_phi_result (stmt
));
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. */
245 worklist
.safe_push (i
);
249 unsigned curr_index
= 0;
250 while (!worklist
.is_empty ())
252 unsigned i
= worklist
.pop ();
253 gimple
*stmt
= SSA_NAME_DEF_STMT (ssa_name (i
));
254 vstate state
= vertices
[i
].state
;
256 if (state
== unvisited
)
258 vertices
[i
].state
= vopen
;
260 /* Assign index to this vertex. */
261 vertices
[i
].index
= curr_index
;
262 vertices
[i
].lowlink
= curr_index
;
265 /* Put vertex on stack and also on worklist to be closed later. */
267 worklist
.safe_push (i
);
269 else if (state
== vopen
)
270 vertices
[i
].state
= closed
;
272 /* Visit neighbors of this vertex. */
275 switch (gimple_code (stmt
))
278 phi
= as_a
<gphi
*> (stmt
);
280 for (j
= 0; j
< gimple_phi_num_args (phi
); j
++)
282 op
= gimple_phi_arg_def (phi
, j
);
283 visit_neighbor (op
, i
);
287 op
= gimple_assign_rhs1 (stmt
);
288 visit_neighbor (op
, i
);
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
)
297 vec
<gimple
*> scc
= vNULL
;
303 scc
.safe_push (SSA_NAME_DEF_STMT (ssa_name (j
)));
304 vertices
[j
].state
= in_scc
;
308 sccs
.safe_push (scc
);
312 if (!stack
.is_empty ())
315 /* Clear 'active' flags. */
316 for (gimple
*stmt
: stmts
)
319 switch (gimple_code (stmt
))
322 i
= SSA_NAME_VERSION (gimple_assign_lhs (stmt
));
325 i
= SSA_NAME_VERSION (gimple_phi_result (stmt
));
331 vertices
[i
].active
= false;
337 /* Could this statement potentially be a copy statement?
339 This pass only considers statements for which this function returns 'true'.
340 Those are basically PHI functions and assignment statements similar to
347 stmt_may_generate_copy (gimple
*stmt
)
349 /* A PHI may generate a copy. */
350 if (gimple_code (stmt
) == GIMPLE_PHI
)
352 gphi
*phi
= as_a
<gphi
*> (stmt
);
354 /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs. */
355 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi
)))
359 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
361 tree op
= gimple_phi_arg_def (phi
, i
);
362 if (TREE_CODE (op
) == SSA_NAME
363 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
367 /* If PHI has more than one unique non-SSA arguments, it won't generate a
369 tree const_op
= NULL_TREE
;
370 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
372 tree op
= gimple_phi_arg_def (phi
, i
);
373 if (TREE_CODE (op
) != SSA_NAME
)
375 if (const_op
&& !operand_equal_p (op
, const_op
))
384 /* Or a statement of type _2 = _1; OR _2 = 5; may generate a copy. */
386 if (!gimple_assign_single_p (stmt
))
389 tree lhs
= gimple_assign_lhs (stmt
);
390 tree rhs
= gimple_assign_rhs1 (stmt
);
392 if (TREE_CODE (lhs
) != SSA_NAME
)
395 /* lhs shouldn't flow through any abnormal edges. */
396 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
399 if (is_gimple_min_invariant (rhs
))
400 return true; /* A statement of type _2 = 5;. */
402 if (TREE_CODE (rhs
) != SSA_NAME
)
405 /* rhs shouldn't flow through any abnormal edges. */
406 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
))
409 /* It is possible that lhs has more alignment or value range information. By
410 propagating we would lose this information. So in the case that alignment
411 or value range information differs, we are conservative and do not
414 FIXME: Propagate alignment and value range info the same way copy-prop
416 if (POINTER_TYPE_P (TREE_TYPE (lhs
))
417 && POINTER_TYPE_P (TREE_TYPE (rhs
))
418 && SSA_NAME_PTR_INFO (lhs
) != SSA_NAME_PTR_INFO (rhs
))
420 if (!POINTER_TYPE_P (TREE_TYPE (lhs
))
421 && !POINTER_TYPE_P (TREE_TYPE (rhs
))
422 && SSA_NAME_RANGE_INFO (lhs
) != SSA_NAME_RANGE_INFO (rhs
))
425 return true; /* A statement of type _2 = _1;. */
428 /* Return all statements in cfun that could generate copies. All statements
429 for which stmt_may_generate_copy returns 'true'. */
431 static auto_vec
<gimple
*>
432 get_all_stmt_may_generate_copy (void)
434 auto_vec
<gimple
*> result
;
437 FOR_EACH_BB_FN (bb
, cfun
)
439 gimple_stmt_iterator gsi
;
440 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
442 gimple
*s
= gsi_stmt (gsi
);
443 if (stmt_may_generate_copy (s
))
444 result
.safe_push (s
);
448 for (pi
= gsi_start_phis (bb
); !gsi_end_p (pi
); gsi_next (&pi
))
450 gimple
*s
= pi
.phi ();
451 if (stmt_may_generate_copy (s
))
452 result
.safe_push (s
);
459 /* For each statement from given SCC, replace its usages by value
463 replace_scc_by_value (vec
<gimple
*> scc
, tree val
)
465 for (gimple
*stmt
: scc
)
467 tree name
= gimple_get_lhs (stmt
);
468 replace_uses_by (name
, val
);
469 bitmap_set_bit (dead_stmts
, SSA_NAME_VERSION (name
));
473 fprintf (dump_file
, "Replacing SCC of size %d\n", scc
.length ());
476 /* Part of 'sccopy_propagate ()'. */
479 sccopy_visit_op (tree op
, hash_set
<tree
> &outer_ops
,
480 hash_set
<gimple
*> &scc_set
, bool &is_inner
,
483 bool op_in_scc
= false;
485 if (TREE_CODE (op
) == SSA_NAME
)
487 gimple
*op_stmt
= SSA_NAME_DEF_STMT (op
);
488 if (scc_set
.contains (op_stmt
))
500 /* Main function of this pass. Find and propagate all three types of copy
501 statements (see pass description above).
503 This is an implementation of an algorithm from the paper Simple and
504 Efficient Construction of Static Single Assignmemnt Form[1]. It is based
505 on strongly-connected components (SCCs) in dataflow graph. The original
506 algorithm only considers PHI statements. We extend it to also consider
507 assignment statements of type _2 = _1;.
509 The algorithm is based on this definition of a set of redundant PHIs[1]:
511 A non-empty set P of PHI functions is redundant iff the PHI functions just
512 reference each other or one other value
514 It uses this lemma[1]:
516 Let P be a redundant set of PHI functions. Then there is a
517 strongly-connected component S subset of P that is also redundant.
519 The algorithm works in this way:
522 2 For each SCC S in topological order:
523 3 Construct set 'inner' of statements that only have other statements
524 from S on their right hand side
525 4 Construct set 'outer' of values that originate outside S and appear on
526 right hand side of some statement from S
527 5 If |outer| = 1, outer only contains a value v. Statements in S only
528 refer to each other or to v -- they are redundant. Propagate v.
529 Else, recurse on statements in inner.
531 The implementation is non-recursive.
535 [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
536 Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
542 auto_vec
<gimple
*> useful_stmts
= get_all_stmt_may_generate_copy ();
543 scc_discovery discovery
;
545 auto_vec
<vec
<gimple
*>> worklist
= discovery
.compute_sccs (useful_stmts
);
547 while (!worklist
.is_empty ())
549 vec
<gimple
*> scc
= worklist
.pop ();
551 auto_vec
<gimple
*> inner
;
552 hash_set
<tree
> outer_ops
;
553 tree last_outer_op
= NULL_TREE
;
555 /* Prepare hash set of PHIs in scc to query later. */
556 hash_set
<gimple
*> scc_set
;
557 for (gimple
*stmt
: scc
)
560 for (gimple
*stmt
: scc
)
562 bool is_inner
= true;
567 switch (gimple_code (stmt
))
570 phi
= as_a
<gphi
*> (stmt
);
572 for (j
= 0; j
< gimple_phi_num_args (phi
); j
++)
574 op
= gimple_phi_arg_def (phi
, j
);
575 sccopy_visit_op (op
, outer_ops
, scc_set
, is_inner
,
580 op
= gimple_assign_rhs1 (stmt
);
581 sccopy_visit_op (op
, outer_ops
, scc_set
, is_inner
,
589 inner
.safe_push (stmt
);
592 if (outer_ops
.elements () == 1)
594 /* The only operand in outer_ops. */
595 tree outer_op
= last_outer_op
;
596 replace_scc_by_value (scc
, outer_op
);
598 else if (outer_ops
.elements () > 1)
600 /* Add inner sccs to worklist. */
601 auto_vec
<vec
<gimple
*>> inner_sccs
602 = discovery
.compute_sccs (inner
);
603 for (vec
<gimple
*> inner_scc
: inner_sccs
)
604 worklist
.safe_push (inner_scc
);
613 /* Called when pass execution starts. */
618 /* For propagated statements. */
619 dead_stmts
= BITMAP_ALLOC (NULL
);
622 /* Called before pass execution ends. */
625 finalize_sccopy (void)
627 /* Remove all propagated statements. */
628 simple_dce_from_worklist (dead_stmts
);
629 BITMAP_FREE (dead_stmts
);
631 /* Propagating a constant may create dead eh edges. */
633 FOR_EACH_BB_FN (bb
, cfun
)
634 gimple_purge_dead_eh_edges (bb
);
639 const pass_data pass_data_sccopy
=
641 GIMPLE_PASS
, /* type */
643 OPTGROUP_NONE
, /* optinfo_flags */
645 ( PROP_cfg
| PROP_ssa
), /* properties_required */
646 0, /* properties_provided */
647 0, /* properties_destroyed */
648 0, /* todo_flags_start */
649 TODO_update_ssa
| TODO_cleanup_cfg
, /* todo_flags_finish */
652 class pass_sccopy
: public gimple_opt_pass
655 pass_sccopy (gcc::context
*ctxt
)
656 : gimple_opt_pass (pass_data_sccopy
, ctxt
)
659 /* opt_pass methods: */
660 virtual bool gate (function
*) { return true; }
661 virtual unsigned int execute (function
*);
662 opt_pass
* clone () final override
{ return new pass_sccopy (m_ctxt
); }
663 }; // class pass_sccopy
666 pass_sccopy::execute (function
*)
677 make_pass_sccopy (gcc::context
*ctxt
)
679 return new pass_sccopy (ctxt
);