15.3.311  src/lib/graph/dominator-tree.api

# This is the api of a dominator tree.
# The dominator tree includes lots of query methods.
# 
# -- Allen Leung

# Compiled by:
#     src/lib/graph/graphs.lib




###          "People that think logically are a
###           nice contrast to the real world."
###
###                          -- Matt Biershbach


stipulate
    package odg =  oop_digraph;                                 # oop_digraph   is from   src/lib/graph/oop-digraph.pkg
herein


    api Dominator_Tree {
        #
        package meg:  Make_Empty_Graph;                         # Make_Empty_Graph      is from   src/lib/graph/make-empty-graph.api

        exception DOMINATOR;

        Dom_Info(N,E,G);                                        # Here N,E,G stand stead for the types of client-package-supplied records associated with (respectively) nodes, edges and graphs.

        # Dominator/postdominator trees:

        Dominator_Tree( N, E, G)
            =
            odg::Digraph( N, Void,  Dom_Info( N, E, G ) );

        Postdominator_Tree( N, E, G)
            = 
            odg::Digraph( N, Void,  Dom_Info( N, E, G ) );

        Node = odg::Node_Id;

        # Compute the (post)dominator
        # tree from a flowgraph:
        # 
        make_dominator:         odg::Digraph(N,E,G) -> Dominator_Tree    (N,E,G);
        make_postdominator:     odg::Digraph(N,E,G) -> Postdominator_Tree(N,E,G); 

        # The following methods work on both
        # dominator and postdominator trees.
        #
        # When operating on a postdominator tree
        # the interpretation of these methods are
        # reversed in the obvious manner.


        #  Extract the original machcode_controlflow_graph 
        #
        mcg:         Dominator_Tree( N,E,G ) -> odg::Digraph(N,E,G);



        # The height of the dominator tree 
        #
        max_levels:  Dominator_Tree( N,E,G ) -> Int;


        # Return a map from node id -> level (level (root) = 0) 
        #
        levels_map:   Dominator_Tree( N,E,G ) -> rw_vector::Rw_Vector( Int );


        # Return a map from node id i -> the node_id j,
        # where j is the level 1 node that dominates i.
        # Special case: if i = ENTRY, then j = ENTRY.
        # This table is cached.
        #
        entry_pos:    Dominator_Tree( N,E,G ) -> rw_vector::Rw_Vector( Int );


        # Return a map from node id -> immediate (post)dominator 
        #
        idoms_map:    Dominator_Tree( N,E,G ) -> rw_vector::Rw_Vector( Int );


        # Immediately (post)dominates? 
        #
        immediately_dominates:  Dominator_Tree( N,E,G ) -> (Node, Node) -> Bool;


        # (Post)dominates? 
        #
        dominates:  Dominator_Tree( N,E,G ) -> (Node, Node) -> Bool;


        # Strictly (post)dominates? 
        #
        strictly_dominates:  Dominator_Tree( N,E,G ) -> (Node, Node) -> Bool;


        # Immediate (post)dominator of a node (-1 if none) 
        #
        idom:  Dominator_Tree( N,E,G ) -> Node -> Node;


        # Nodes that the node immediately (post)dominates 
        #
        idoms:  Dominator_Tree( N,E,G ) -> Node -> List( Node );


        # Nodes that the node (post)dominates (includes self) 
        #
        doms:  Dominator_Tree( N,E,G ) -> Node -> List( Node );


        # Return the level of a node in the tree 
        #
        level:  Dominator_Tree( N,E,G ) -> Node -> Int; 

        # Return the least common ancestor of a pair of nodes 
        #
        lca:  Dominator_Tree( N,E,G ) -> (Node, Node) -> Node; 



        # The following methods require both
        # the dominator and postdominator trees:

        # Are two nodes control equivalent? 
        #
        control_equivalent
            :
            (     Dominator_Tree( N,E,G ),
              Postdominator_Tree( N,E,G )
            )
            ->
            (Node, Node)
            ->
            Bool;

        # Compute the control equivalent
        # partitions of a graph:
        #
        control_equivalent_partitions:  
              (Dominator_Tree( N,E,G ), Postdominator_Tree( N,E,G )) ->
                  List( List( Node ) );

    };
end;