soot.toolkits.graph
Class CytronDominanceFrontier

java.lang.Object
  soot.toolkits.graph.CytronDominanceFrontier

All Implemented Interfaces:

DominanceFrontier

public class CytronDominanceFrontier
extends Object
implements DominanceFrontier

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

protected DominatorTree	dt
protected Map<DominatorNode,List<DominatorNode>>	nodeToFrontier

Constructor Summary

CytronDominanceFrontier(DominatorTree dt)

Method Summary

protected void	bottomUpDispatch(DominatorNode node) Make sure we visit children first.
List	getDominanceFrontierOf(DominatorNode node)
protected boolean	isFrontierKnown(DominatorNode node)
protected void	processNode(DominatorNode 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 dt

nodeToFrontier

protected Map<DominatorNode,List<DominatorNode>> nodeToFrontier

Constructor Detail

CytronDominanceFrontier

public CytronDominanceFrontier(DominatorTree dt)

Method Detail

getDominanceFrontierOf

public List getDominanceFrontierOf(DominatorNode node)

Specified by:

getDominanceFrontierOf in interface DominanceFrontier

isFrontierKnown

protected boolean isFrontierKnown(DominatorNode node)

bottomUpDispatch

protected void bottomUpDispatch(DominatorNode node)

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

processNode

protected void processNode(DominatorNode 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