Package com.ensoftcorp.open.commons.algorithms

Class DominanceAnalysis

  • public class DominanceAnalysis
extends PrioritizedCodemapStage
    Primary interface for computing dominance relationships. This also acts as a code map stage to pre-compute dominance relationships for control flow graphs.
    Author:
    Ben Holland

    • Field Detail

      • IDENTIFIER

        public static final java.lang.String IDENTIFIER
        The unique identifier for the PDG codemap stage
        See Also:
        Constant Field Values

      • DOMINATOR_TREE_EDGE

        public static final java.lang.String DOMINATOR_TREE_EDGE
        The immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n. Every node, except the entry node, has an immediate dominator. Because the immediate dominator is unique, it is a tree. The start node is the root of the tree.
        See Also:
        Constant Field Values

      • POST_DOMINATOR_TREE_EDGE

        public static final java.lang.String POST_DOMINATOR_TREE_EDGE
        Used to tag the edges from a node that post-dominate a node. Wikipedia: Analogous to the definition of dominance above, a node z is said to post-dominate a node n if all paths to the exit node of the graph starting at n must go through z. Similarly, the immediate post-dominator of a node n is the postdominator of n that doesn't strictly postdominate any other strict postdominators of n.
        See Also:
        Constant Field Values

      • DOMINANCE_FRONTIER_EDGE

        public static final java.lang.String DOMINANCE_FRONTIER_EDGE
        Used to tag the edges from a node that identify the node's dominance frontier. Wikipedia: The dominance frontier of a node d is the set of all nodes n such that d dominates an immediate predecessor of n, but d does not strictly dominate n. It is the set of nodes where d's dominance stops.
        See Also:
        Constant Field Values

      • POST_DOMINANCE_FRONTIER_EDGE

        public static final java.lang.String POST_DOMINANCE_FRONTIER_EDGE
        Used to tag the edges from a node that identify the node's post-dominance frontier. Wikipedia: The dominance frontier of a node d is the set of all nodes n such that d dominates an immediate predecessor of n, but d does not strictly dominate n. It is the set of nodes where d's dominance stops. Note that analogous to the definition of dominance above, a node z is said to post-dominate a node n if all paths to the exit node of the graph starting at n must go through z. Similarly, the immediate post-dominator of a node n is the postdominator of n that doesn't strictly postdominate any other strict postdominators of n.
        See Also:
        Constant Field Values

    • Constructor Detail

      • DominanceAnalysis

        public DominanceAnalysis()

    • Method Detail

      • getDominatorTreeEdges

        public static com.ensoftcorp.atlas.core.query.Q getDominatorTreeEdges()

      • getPostDominatorTreeEdges

        public static com.ensoftcorp.atlas.core.query.Q getPostDominatorTreeEdges()

      • getDominanceFrontierEdges

        public static com.ensoftcorp.atlas.core.query.Q getDominanceFrontierEdges()

      • getPostDominanceFrontierEdges

        public static com.ensoftcorp.atlas.core.query.Q getPostDominanceFrontierEdges()

      • getCodemapStageDependencies

        public java.lang.String[] getCodemapStageDependencies()
        Description copied from class: PrioritizedCodemapStage
        Returns a set of prioritized codemap stage identifier strings that should perform indexing before this prioritized codemap stage Note: this should represent a conservative set of the worst case dependencies. That is, if it is possible that under some configuration of the toolbox that the toolbox could depend on a prioritized codemap stage, then it should be listed here. Note: mutual dependencies are not supported!
        Specified by:
        getCodemapStageDependencies in class PrioritizedCodemapStage
        Returns:

      • performIndexing

        public boolean performIndexing​(org.eclipse.core.runtime.IProgressMonitor monitor)
        Description copied from class: PrioritizedCodemapStage
        The codemap stage indexing task to be performed.
        Specified by:
        performIndexing in class PrioritizedCodemapStage
        Returns:
        Returns true if the codemap stage was actually run.

      • computeSandboxedDominatorTree

        public static SandboxGraph computeSandboxedDominatorTree​(Sandbox sandbox,
                                                         UniqueEntryExitGraph ucfg)
        Returns the immediate dominator tree
        Parameters:
        ucfg -
        Returns:

      • computeSandboxedPostDominatorTree

        public static SandboxGraph computeSandboxedPostDominatorTree​(Sandbox sandbox,
                                                             UniqueEntryExitGraph ucfg)
        Returns the post dominator tree
        Parameters:
        ucfg -
        Returns:

      • computeSandboxedDominanceFrontier

        public static SandboxGraph computeSandboxedDominanceFrontier​(Sandbox sandbox,
                                                             UniqueEntryExitGraph ucfg)
        Returns the dominance frontier (each edge represents a frontier node for a given from node)
        Parameters:
        ucfg -
        Returns:

      • computeSandboxedPostDominanceFrontier

        public static SandboxGraph computeSandboxedPostDominanceFrontier​(Sandbox sandbox,
                                                                 UniqueEntryExitGraph ucfg)
        Returns the post-dominance frontier (each edge represents a frontier node for a given from node)
        Parameters:
        ucfg -
        Returns:

      • computeSandboxedDominance

        public static SandboxGraph computeSandboxedDominance​(Sandbox sandbox,
                                                     UniqueEntryExitGraph ucfg)
        Returns a graph of all dominance relationship edges
        Parameters:
        ucfg -
        Returns:

      • computeDominanceTree

        public static com.ensoftcorp.atlas.core.db.graph.Graph computeDominanceTree​(UniqueEntryExitGraph ucfg)
        Returns the immediate dominance tree
        Parameters:
        ucfg -
        Returns:

      • computeDominanceFrontier

        public static com.ensoftcorp.atlas.core.db.graph.Graph computeDominanceFrontier​(UniqueEntryExitGraph ucfg)
        Returns the dominance frontier
        Parameters:
        ucfg -
        Returns:

      • computePostDominanceTree

        public static com.ensoftcorp.atlas.core.db.graph.Graph computePostDominanceTree​(UniqueEntryExitGraph ucfg)
        Returns the post dominance graph
        Parameters:
        ucfg -
        Returns:

      • computePostDominanceFrontier

        public static com.ensoftcorp.atlas.core.db.graph.Graph computePostDominanceFrontier​(UniqueEntryExitGraph ucfg)
        Returns the post-dominance frontier
        Parameters:
        ucfg -
        Returns:

      • computeDominance

        public static com.ensoftcorp.atlas.core.db.graph.Graph computeDominance​(UniqueEntryExitGraph ucfg)
        Returns a graph of all dominance relationship edges
        Parameters:
        ucfg -
        Returns: