Package soot.toolkits.graph.pdg

Class HashMutablePDG

  • All Implemented Interfaces:
    Iterable<PDGNode>, DirectedGraph<PDGNode>, EdgeLabelledDirectedGraph<PDGNode,​String>, MutableEdgeLabelledDirectedGraph<PDGNode,​String>, ProgramDependenceGraph
    public class HashMutablePDG
extends HashMutableEdgeLabelledDirectedGraph<PDGNode,​String>
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

    • Constructor Detail

      • HashMutablePDG

        public HashMutablePDG​(UnitGraph cfg)

    • Method Detail

      • constructPDG

        protected void constructPDG()
        This is the heart of the PDG construction. It is huge and definitely needs some refactorings, but since it's been evolving to cover some boundary cases it has become hard to refactor. 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.)

      • 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)

      • getPostorderPDGRegionList

        public static List<PDGRegion> getPostorderPDGRegionList​(PDGNode root)
        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:
        root - The root node 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.