Main function of this pass. Find and propagate all three types of copy
statements (see pass description above).
This is an implementation of an algorithm from the paper Simple and
Efficient Construction of Static Single Assignmemnt Form[1]. It is based
on strongly-connected components (SCCs) in dataflow graph. The original
algorithm only considers PHI statements. We extend it to also consider
assignment statements of type _2 = _1;.
The algorithm is based on this definition of a set of redundant PHIs[1]:
A non-empty set P of PHI functions is redundant iff the PHI functions just
reference each other or one other value
It uses this lemma[1]:
Let P be a redundant set of PHI functions. Then there is a
strongly-connected component S subset of P that is also redundant.
The algorithm works in this way:
1 Find SCCs
2 For each SCC S in topological order:
3 Construct set 'inner' of statements that only have other statements
from S on their right hand side
4 Construct set 'outer' of values that originate outside S and appear on
right hand side of some statement from S
5 If |outer| = 1, outer only contains a value v. Statements in S only
refer to each other or to v -- they are redundant. Propagate v.
Else, recurse on statements in inner.
The implementation is non-recursive.
References:
[1] Simple and Efficient Construction of Static Single Assignmemnt Form,
Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
Section 3.2.
References hash_set< KeyId, Lazy, Traits >::add(), as_a(), hash_set< KeyId, Lazy, Traits >::elements(), gcc_unreachable, get_all_stmt_may_generate_copy(), gimple_assign_rhs1(), gimple_bb(), gimple_phi_arg_def(), gimple_phi_num_args(), i, NULL, NULL_TREE, replace_scc_by_value(), visit_op(), and worklist.
