Package com.ensoftcorp.open.commons.algorithms.dominance

Class DominatorTree

  • public class DominatorTree
extends java.lang.Object
    An implementation of the O(n log n) Lengauer-Tarjan algorithm for building the dominator tree of a graph.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  DominatorTree.Multimap<T>
      Multimap maps a key to a set of values.

    • Constructor Summary

      Constructors 
      Constructor Description
      DominatorTree​(UniqueEntryExitGraph graph)
      Construct a DominatorTree from a root.
      DominatorTree​(UniqueEntryExitGraph graph, com.ensoftcorp.atlas.core.db.set.AtlasSet<com.ensoftcorp.atlas.core.db.graph.Node> explicitRoots)
      Construct a DominatorTree from a collection of "roots."

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      DominatorTree.Multimap<com.ensoftcorp.atlas.core.db.graph.Node> getDominanceFrontiers()
      Compute and/or fetch the dominance frontiers as a Multimap.
      DominatorTree.Multimap<com.ensoftcorp.atlas.core.db.graph.Node> getDominatorTree()
      Compute and/or fetch the dominator tree as a Multimap.
      java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​com.ensoftcorp.atlas.core.db.graph.Node> getIdoms()
      Returns the map of immediate dominators
      java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​java.lang.Integer> getSdoms()
      Returns the map of semi-dominators
      java.lang.Iterable<com.ensoftcorp.atlas.core.db.graph.Node> reverseTopologicalTraversal()
      Create and/or fetch a reverse topological traversal of the dominator tree, such that for every node, node appears before idom(node).
      java.util.List<com.ensoftcorp.atlas.core.db.graph.Node> topologicalTraversal()
      Create and/or fetch a topological traversal of the dominator tree, such that for every node, idom(node) appears before node.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • DominatorTree

        public DominatorTree​(UniqueEntryExitGraph graph)
        Construct a DominatorTree from a root.
        Parameters:
        root - the root of the graph.

      • DominatorTree

        public DominatorTree​(UniqueEntryExitGraph graph,
                     com.ensoftcorp.atlas.core.db.set.AtlasSet<com.ensoftcorp.atlas.core.db.graph.Node> explicitRoots)
        Construct a DominatorTree from a collection of "roots."
        Parameters:
        explicitRoots - the collection of roots; one of these is the true root of the flowgraph, the others are exception handlers that would otherwise be unreachable.

    • Method Detail

      • getIdoms

        public java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​com.ensoftcorp.atlas.core.db.graph.Node> getIdoms()
        Returns the map of immediate dominators
        Returns:
        the map from each block to its immediate dominator (if it has one).

      • getSdoms

        public java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​java.lang.Integer> getSdoms()
        Returns the map of semi-dominators

      • getDominatorTree

        public DominatorTree.Multimap<com.ensoftcorp.atlas.core.db.graph.Node> getDominatorTree()
        Compute and/or fetch the dominator tree as a Multimap.
        Returns:
        the dominator tree.

      • getDominanceFrontiers

        public DominatorTree.Multimap<com.ensoftcorp.atlas.core.db.graph.Node> getDominanceFrontiers()
        Compute and/or fetch the dominance frontiers as a Multimap.
        Returns:
        a Multimap where the set of nodes mapped to each key node is the set of nodes in the key node's dominance frontier.

      • topologicalTraversal

        public java.util.List<com.ensoftcorp.atlas.core.db.graph.Node> topologicalTraversal()
        Create and/or fetch a topological traversal of the dominator tree, such that for every node, idom(node) appears before node.
        Returns:
        the topological traversal of the dominator tree, as an immutable List.

      • reverseTopologicalTraversal

        public java.lang.Iterable<com.ensoftcorp.atlas.core.db.graph.Node> reverseTopologicalTraversal()
        Create and/or fetch a reverse topological traversal of the dominator tree, such that for every node, node appears before idom(node).
        Returns:
        a reverse topological traversal of the dominator tree, as an immutable List.