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

(

)

References BITMAP_FREE, cfun, dead_stmts, FOR_EACH_BB_FN, gimple_purge_dead_eh_edges(), and simple_dce_from_worklist().

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, dump_flags, gimple_get_lhs(), print_generic_expr(), replace_uses_by(), SSA_NAME_VERSION, and TDF_DETAILS.

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

Part of 'scc_copy_prop::propagate ()'.   

References hash_set< KeyId, Lazy, Traits >::add(), hash_set< KeyId, Lazy, Traits >::contains(), SSA_NAME_DEF_STMT, and TREE_CODE.

Field Documentation

dead_stmts

bitmap scc_copy_prop::dead_stmts

private

Referenced by replace_scc_by_value(), scc_copy_prop(), and ~scc_copy_prop().

---

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

• gimple-ssa-sccopy.cc