soot.toolkits.graph.pdg
Class HashMutablePDG

java.lang.Object
  soot.toolkits.graph.HashMutableEdgeLabelledDirectedGraph
      soot.toolkits.graph.pdg.HashMutablePDG

All Implemented Interfaces:

Iterable, DirectedGraph, MutableEdgeLabelledDirectedGraph, ProgramDependenceGraph

public class HashMutablePDG
extends HashMutableEdgeLabelledDirectedGraph
implements ProgramDependenceGraph

This class implements a Program Dependence Graph as defined in Ferrante, J., Ottenstein, K. J., and Warren, J. D. 1987. The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst. 9, 3 (Jul. 1987), 319-349. DOI= http://doi.acm.org/10.1145/24039.24041 Note: the implementation is not exactly as in the above paper. It first finds the regions of control dependence then uses part of the algorithm given in the above paper to build the graph. The constructor accepts a UnitGraph, which can be a BriefUnitGraph, an ExceptionalUnitGraph, or an EnhancedUnitGraph. At the absence of exception handling constructs in a method, all of these work the same. However, at the presence of exception handling constructs, BriefUnitGraph is multi-headed and potentially multi-tailed which makes the results of RegionAnalysis and PDG construction unreliable (It's not clear if it would be useful anyway); Also, ExceptionalGraph's usefulness when exception handling is present is not so clear since almost every unit can throw exception hence the dependency is affected. Currently, the PDG is based on a UnitGraph (BlockGraph) and does not care whether flow is exceptional or not. The nodes in a PDG are of type PDGNode and the edges can have three labels: "dependency", "dependency-back", and "controlflow"; however, the "controlflow" edges are auxiliary and the dependencies are represented by the labels beginning with "dependency". Other labels can be added later for application or domain-specific cases. To support methods that contain exception-handling and multiple-heads or tails, use EnhancedUnitGraph. It does not represent exceptional flow in the way ExceptionalUnitGraph does, but it integrates them in a concise way. Also, it adds START/STOP nodes to graph if necessary to make the graph single entry single exit.

Author:

Hossein Sadat-Mohtasham Sep 2009

Field Summary

protected BlockGraph	m_blockCFG
protected Body	m_body
protected UnitGraph	m_cfg
protected SootClass	m_class
protected Hashtable<Object,PDGNode>	m_obj2pdgNode
protected List<PDGRegion>	m_pdgRegions
protected PDGNode	m_startNode
protected List<Region>	m_strongRegions
protected List<Region>	m_weakRegions

Fields inherited from class soot.toolkits.graph.HashMutableEdgeLabelledDirectedGraph

edgeToLabels, heads, labelToEdges, nodeToPreds, nodeToSuccs, tails

Constructor Summary

HashMutablePDG(UnitGraph cfg)

Method Summary

protected void	constructPDG() This is the heart of the PDG contruction.
boolean	dependentOn(PDGNode node1, PDGNode node2) This method determines if node1 is control-dependent on node2 in this PDG.
UnitGraph	getCFG()
List<PDGNode>	getDependents(PDGNode node) This method returns the list of all dependents of a node in the PDG.
PDGNode	getPDGNode(Object cfgNode) This method returns the PDGNode in the PDG corresponding to the given CFG node.
List<PDGRegion>	getPDGRegions() This method returns the list of PDGRegions computed by the construction method.
static List<PDGRegion>	getPostorderPDGRegionList(PDGNode r) This method returns a list of regions obtained by post-order traversal of the region hierarchy.
static List<IRegion>	getPostorderRegionList(IRegion r)
static List<IRegion>	getPreorderRegionList(IRegion r)
PDGNode	GetStartNode()
IRegion	GetStartRegion()
List<Region>	getStrongRegions()
List<Region>	getWeakRegions()
void	removeAllEdges(Object from, Object to) The existing removeAllEdges in the parent class seems to be throwing concurrentmodification exception most of the time.
String	toString()

Methods inherited from class soot.toolkits.graph.HashMutableEdgeLabelledDirectedGraph

addEdge, addNode, clearAll, clone, containsAnyEdge, containsAnyEdge, containsEdge, containsNode, getEdgesForLabel, getHeads, getLabelsForEdges, getNodes, getPredsOf, getSuccsOf, getTails, iterator, printGraph, removeAllEdges, removeEdge, removeNode, size

Methods inherited from class java.lang.Object

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

Methods inherited from interface soot.toolkits.graph.MutableEdgeLabelledDirectedGraph

addEdge, addNode, containsAnyEdge, containsAnyEdge, containsEdge, containsNode, getEdgesForLabel, getLabelsForEdges, getNodes, removeAllEdges, removeEdge, removeNode

Methods inherited from interface soot.toolkits.graph.DirectedGraph

getHeads, getPredsOf, getSuccsOf, getTails, iterator, size

Field Detail

m_body

protected Body m_body

m_class

protected SootClass m_class

m_cfg

protected UnitGraph m_cfg

m_blockCFG

protected BlockGraph m_blockCFG

m_obj2pdgNode

protected Hashtable<Object,PDGNode> m_obj2pdgNode

m_weakRegions

protected List<Region> m_weakRegions

m_strongRegions

protected List<Region> m_strongRegions

m_startNode

protected PDGNode m_startNode

m_pdgRegions

protected List<PDGRegion> m_pdgRegions

Constructor Detail

HashMutablePDG

public HashMutablePDG(UnitGraph cfg)

Method Detail

constructPDG

protected void constructPDG()

This is the heart of the PDG contruction. It is huge and definitely needs some refactorings, but since it's been evlovong to cover some boundary cases it has become hard to rafactor. It uses the list of weak regions, along with the dominator and post-dominator trees to construct the PDG nodes.

getCFG

public UnitGraph getCFG()

Returns:

The Corresponding UnitGraph

getWeakRegions

public List<Region> getWeakRegions()

Specified by:

getWeakRegions in interface ProgramDependenceGraph

Returns:

A List of weak regions, generated by RegionAnalysis for the corresponding control flow graph (These are Regions and not PDGRegions.)

getStrongRegions

public List<Region> getStrongRegions()

Specified by:

getStrongRegions in interface ProgramDependenceGraph

Returns:

A List of strong regions, generated when constructing the program dependence graph (These are Regions and not PDGRegions.)

GetStartRegion

public IRegion GetStartRegion()

Specified by:

GetStartRegion in interface ProgramDependenceGraph

Returns:

The root region of the PDG.

GetStartNode

public PDGNode GetStartNode()

Specified by:

GetStartNode in interface ProgramDependenceGraph

Returns:

The root node of the PDG, which is essentially the same as the start region but packaged in its PDGNode, which can be used to traverse the graph, etc.

getPreorderRegionList

public static List<IRegion> getPreorderRegionList(IRegion r)

getPostorderRegionList

public static List<IRegion> getPostorderRegionList(IRegion r)

getPDGRegions

public List<PDGRegion> getPDGRegions()

This method returns the list of PDGRegions computed by the construction method.

Specified by:

getPDGRegions in interface ProgramDependenceGraph

Returns:

The list of PDGRegions

getPostorderPDGRegionList

public static List<PDGRegion> getPostorderPDGRegionList(PDGNode r)

This method returns a list of regions obtained by post-order traversal of the region hierarchy. This takes advantage of the hierarchical (parent/child) information encoded within the PDGNodes at construction time; it should be noted that, we have not counted the strong regions that represent the loop header as a separate region; instead, a PDGRegion that represents both the loop header and its body are counted.

Parameters:

The - root from which the traversal should begin.

Returns:

The list of regions obtained thru post-order traversal of the region hierarchy.

dependentOn

public boolean dependentOn(PDGNode node1,
                           PDGNode node2)

This method determines if node1 is control-dependent on node2 in this PDG.

Specified by:

dependentOn in interface ProgramDependenceGraph

Returns:

returns true if node1 is dependent on node2

getDependents

public List<PDGNode> getDependents(PDGNode node)

This method returns the list of all dependents of a node in the PDG.

Specified by:

getDependents in interface ProgramDependenceGraph

Parameters:

node - is the PDG node whose dependents are desired.

Returns:

a list of dependent nodes

getPDGNode

public PDGNode getPDGNode(Object cfgNode)

This method returns the PDGNode in the PDG corresponding to the given CFG node. Note that currently the CFG node has to be a Block.

Specified by:

getPDGNode in interface ProgramDependenceGraph

Parameters:

cfgNode - is expected to be a node in CFG (currently only Block).

Returns:

The node in PDG corresponding to cfgNode.

removeAllEdges

public void removeAllEdges(Object from,
                           Object to)

The existing removeAllEdges in the parent class seems to be throwing concurrentmodification exception most of the time. Here is a version that doesn't throw that exception.

Specified by:

removeAllEdges in interface MutableEdgeLabelledDirectedGraph

Overrides:

removeAllEdges in class HashMutableEdgeLabelledDirectedGraph

Parameters:

from - out node for the edges to remove.

to - in node for the edges to remove.

toString

public String toString()

Specified by:

toString in interface ProgramDependenceGraph

Overrides:

toString in class Object

Returns:

A human readable description of the PDG.