PreviousUpNext

15.4.268  src/lib/compiler/back/low/ir-archive/cdg.pkg

#
# This is a generic module for computing the control dependence graph
# from a graph with an entry and an exit.  
# The graph is treated as a control flow graph.  
# The edge predicate is used to determine whether an edge should be
# treated as a branch edge.
#
# -- Allen Leung


###            "Mostly, when you see programmers, they aren't doing anything.
###             One of the attractive things about programmers is that you
###             cannot tell whether or not they are working simply by looking
###             at them.
###
###             Very often they're sitting there seemingly drinking coffee and
###             gossiping, or just staring into space. What the programmer is
###             trying to do is get a handle on all the individual and unrelated
###             ideas that are scampering around in his head."
###
###                                        -- Charles M Strauss


generic package ControlDependenceGraph
   (package dom:        Dominator_Tree
    package meg:  Make_Empty_Graph
   ) : CONTROL_DEPENDENCE_GRAPH

{
    # Export to client packages:
    #
    package dom = Dom
    package g   = graph
    package meg = meg

    type cdg (N, E, G) = graph::graph (N, E, G) 

    fun control_dependence_graph' f_node f_edge f_graph is_conditional
             (PDom as g::GRAPH pdom) =
    let my g::GRAPH mcg        = Dom::mcg PDom
        N                  = mcg.capacity ()
        cdg_info           = f_graph mcg.graph_info
        my CDG as g::GRAPH cdg = gi::graph("CDG", cdg_info, N)
        ipdom              = Dom::idom PDom
        add_edge           = \\ e => cdg.add_edge (f_edge e)
        out_edges          = mcg.out_edges

        #  Create the control dependence nodes 
        mcg.forall_nodes (\\ n => cdg.add_node (f_node n))
 
        #  Create the control dependence edges 
        mcg.forall_nodes 
         (\\ node as (X, bb) =>
             let ipdom_X = ipdom X
                 fun loop (X, Z, L) =
                     if ipdom_X == -1 or ipdom_X != Z then
                     #  Z is immediately control dependent on X 
                       (add_edge (X, Z, L);
                        case ipdom Z of
                          -1 => ()
                        |  Z => loop (X, Z, L))
                     else ()
             in
                 apply (\\ (X, Z, L) => 
                           #  Z is a successor of X on label L 
                           if is_conditional L then loop (X, Z, L)
                           else ()
                     ) (out_edges X)
             end)
    in
        CDG
    end

    fun control_dependence_graph is_conditional =
          control_dependence_graph' 
          (\\ n => n) 
          (\\ e => e) 
          (\\ g => g) is_conditional

}


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext