GCC Middle and Back End API Reference
scc_copy_prop Class Reference
Collaboration diagram for scc_copy_prop:

Public Member Functions

 scc_copy_prop ()
 
 ~scc_copy_prop ()
 
void propagate ()
 

Private Member Functions

void visit_op (tree op, hash_set< tree > &outer_ops, hash_set< gimple * > &scc_set, bool &is_inner, tree &last_outer_op)
 
void replace_scc_by_value (vec< gimple * > scc, tree val)
 

Private Attributes

bitmap dead_stmts
 

Detailed Description

SCC copy propagation

'scc_copy_prop::propagate ()' is the main function of this pass.   

Constructor & Destructor Documentation

◆ scc_copy_prop()

scc_copy_prop::scc_copy_prop ( )

References BITMAP_ALLOC, dead_stmts, and NULL.

◆ ~scc_copy_prop()

scc_copy_prop::~scc_copy_prop ( )

Member Function Documentation

◆ propagate()

void scc_copy_prop::propagate ( )
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.

◆ replace_scc_by_value()

void scc_copy_prop::replace_scc_by_value ( vec< gimple * > scc,
tree val )
private
For each statement from given SCC, replace its usages by value
VAL.   

References bitmap_set_bit, dead_stmts, dump_file, gimple_get_lhs(), replace_uses_by(), and SSA_NAME_VERSION.

Referenced by propagate().

◆ visit_op()

void scc_copy_prop::visit_op ( tree op,
hash_set< tree > & outer_ops,
hash_set< gimple * > & scc_set,
bool & is_inner,
tree & last_outer_op )
private

Field Documentation

◆ dead_stmts

bitmap scc_copy_prop::dead_stmts
private

The documentation for this class was generated from the following file: