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

Class PostDominatorTree

  • public class PostDominatorTree
extends java.lang.Object
    An implementation of the O(n log n) Lengauer-Tarjan algorithm for building the dominator tree of a cfg. Adapted from: https://svn.apache.org/repos/asf/flex/falcon/trunk/compiler/src/org/apache/flex/abc/graph/algorithms/DominatorTree.java NOTE: This is an older revision of com.ensoftcorp.open.commons.algorithms.internal.DominatorTree, which specifically dealt with computing post-dominance relationships TODO: CAFEFULLY! Merge this code with the DominatorTree code...BE VERY CAFEFUL YOU COULD BREAK A LOT OF THINGS!

    • Nested Class Summary

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

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      PostDominatorTree.Multimap<com.ensoftcorp.atlas.core.db.graph.Node> getDominanceFrontiers()
      Compute and/or fetch the dominance frontiers as a Multimap.
      PostDominatorTree.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

      • PostDominatorTree

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

    • 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 PostDominatorTree.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 PostDominatorTree.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.