Package soot.toolkits.graph

Class CytronDominanceFrontier<N>

java.lang.Object

soot.toolkits.graph.CytronDominanceFrontier<N>

All Implemented Interfaces:

DominanceFrontier<N>

public class CytronDominanceFrontier<N>
extends Object
implements DominanceFrontier<N>

Class to compute the DominanceFrontier using Cytron's celebrated efficient algorithm.

Author:

Navindra Umanee

See Also:

Efficiently Computing Static Single Assignment Form and the Control Dependence Graph

Field Summary

Fields

Modifier and Type	Field	Description
protected DominatorTree<N>	dt
protected Map<DominatorNode<N>,List<DominatorNode<N>>>	nodeToFrontier

Constructor Summary

Constructors

Constructor	Description
CytronDominanceFrontier(DominatorTree<N> dt)

Method Summary

Modifier and Type	Method	Description
protected void	bottomUpDispatch(DominatorNode<N> node)	Make sure we visit children first.
List<DominatorNode<N>>	getDominanceFrontierOf(DominatorNode<N> node)
protected boolean	isFrontierKnown(DominatorNode<N> node)
protected void	processNode(DominatorNode<N> node)	Calculate dominance frontier for a set of basic blocks.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

dt

protected DominatorTree<N> dt

nodeToFrontier

protected Map<DominatorNode<N>,List<DominatorNode<N>>> nodeToFrontier

Constructor Detail

CytronDominanceFrontier

public CytronDominanceFrontier(DominatorTree<N> dt)

Method Detail

getDominanceFrontierOf

public List<DominatorNode<N>> getDominanceFrontierOf(DominatorNode<N> node)

Specified by:

getDominanceFrontierOf in interface DominanceFrontier<N>

isFrontierKnown

protected boolean isFrontierKnown(DominatorNode<N> node)

bottomUpDispatch

protected void bottomUpDispatch(DominatorNode<N> node)

Make sure we visit children first. This is reverse topological order.

processNode

protected void processNode(DominatorNode<N> node)

Calculate dominance frontier for a set of basic blocks.

Uses the algorithm of Cytron et al., TOPLAS Oct. 91:

 
 for each X in a bottom-up traversal of the dominator tree do

      DF(X) < - null
      for each Y in Succ(X) do
        if (idom(Y)!=X) then DF(X) <- DF(X) U Y
      end
      for each Z in {idom(z) = X} do
        for each Y in DF(Z) do
              if (idom(Y)!=X) then DF(X) <- DF(X) U Y
        end
      end