PreviousUpNext

15.4.298  src/lib/compiler/back/low/main/nextcode/find-nextcode-cccomponents.pkg

# find-nextcode-cccomponents.pkg                        # "cccomponent" == "callgraph connected component".
#
# We use the "union/find" algorithm to efficiently [1]
# find connected components in the function callgraph.
#
# By compiling each such component separately we
# maximize opportunities to do interprocedural
# register allocation and such while not choking
# the compiler with bigger collections of functions
# than necessary.
#
# For background on the union-find algorithm
# (and a more general implementation) see
#
#     src/lib/src/disjoint-sets-with-constant-time-union.api
#
# Our implementation here is not particularly sophisticated;
# it does neither union-by-rank nor path compression.                   # Should we switch to the standard implementation, which does this stuff right? XXX QUERO ANSWERME
#
#
#         "The unit of compilation is called a cluster which is
#          the smallest unit for inter-procedural optimizations.
#          A cluster will typically consist of several entry points
#          that may call each other, as well as call local functions
#          in the module."
#
#                              -- http://www.cs.nyu.edu/leunga/MLRISC/Doc/html/mlrisc-gen.html
#
#         "the [compiler backend lowhalf] uses two different internal representations.
#          The first, cluster, is a light-weight representation which is suitable for
#          simple compilers without extensive optimizations;"
#
#                              -- http://www.cs.nyu.edu/leunga/MLRISC/Doc/html/instrsel.html 
#
# Note[1] Except we seem to blow it and descend to O(N**2) behavior
#         due to not tuning the algorithm correctly. :-(

# Compiled by:
#     src/lib/compiler/core.sublib



stipulate
    package ncf =  nextcode_form;                                       # nextcode_form                 is from   src/lib/compiler/back/top/nextcode/nextcode-form.pkg
    package iht =  int_hashtable;                                       # int_hashtable                 is from   src/lib/src/int-hashtable.pkg
    package rwv =  rw_vector;                                           # rw_vector                     is from   src/lib/std/src/rw-vector.pkg
herein
    package find_nextcode_cccomponents
        #
        : (weak)  api {
                        find_nextcode_cccomponents
                            :
                            List( ncf::Function )
                            ->
                            List( List( ncf::Function ) );              # Each inner list is a connected component in the callgraph.
                      }
    {

        fun error msg
            =
            error_message::impossible ("Cluster." + msg);               # error_message                 is from   src/lib/compiler/front/basics/errormsg/error-message.pkg


        # Find connected components in the nextcode callgraph.
        # This function is called from:
        #
        #     src/lib/compiler/back/low/main/main/translate-nextcode-to-treecode-g.pkg
        #
        fun find_nextcode_cccomponents  functions       # "cccomponent" == "callgraph connected component".
            =
            {   function_count =   length functions;

                exception FUNCTION_IDENTIFIER;

                # First function in the function list must be
                # the first function  in the first cluster.             # Why? XXX QUERO ANSERME
                #
                # This is achieved by ensuring that the first  
                # function is mapped to the smallest id in our
                # consecutive (0..N-1) function ids.
                # This function id will map to the smallest cluster id. 
                # The function ids are then iterated in descending order.


                ######################################################
                # We start by constructing a mapping from function
                # (more precisely, function labels) to "function id"
                # -- consecutive integers (0..N-1).  Function ids will
                # allow us to use an efficient vector representation
                # for our union/find inverted-tree disjoint-sets. 


                # This table will map the function labels already present
                # in our nextcode functions to function_ids which we will
                # assign successively starting at zero:
                #
                my function_label_to_function_id_hashtable:   iht::Hashtable( Int )
                                                          =   iht::make_hashtable  { size_hint => function_count,  not_found_exception => FUNCTION_IDENTIFIER };

                function_label_to_function_id =   iht::get  function_label_to_function_id_hashtable;

                # The reverse mapping from (0..N-1) function ids to
                # nextcode functions can be done by a trivial vector lookup:
                #
                function_id_to_function_table =   rwv::make_rw_vector (function_count, head functions);

                # Assign function ids to all of our
                # functions in order, starting at zero:
                #
                make_function_id_table (functions, 0)
                where
                    add_function_label_to_table =   iht::set  function_label_to_function_id_hashtable;

                    fun make_function_id_table ((function as (_, f, _, _, _)) ! rest, id)
                            => 
                            {   add_function_label_to_table (f, id);  
                                rwv::set (function_id_to_function_table, id, function);
                                make_function_id_table (rest, id+1);
                            };

                        make_function_id_table ([], _) =>   ();
                    end;
                end;




                ######################################################
                # Now we find all connected components in the nextcode
                # callgraph defined by our function list.
                #
                # First, we make each function the sole member
                # of its very own connected component:
                
                trees = rwv::from_fn (function_count, fn i = i);                        # Do we know if the compiler is good enough to optimize away logging of
                                                                                        # stores into a rwv::Rw_Vector(Int)?  Or should we be using a typelocked vector here?   XXX THINKO ANSWERME

                # Now a little helper function.
                #
                # We need to be able to determine which 
                # set a function is currently in.
                #
                # Recall that we represent a set as an inverted
                # tree with each child pointing to its parent
                # and the root node pointing to itself.
                #
                # This function follows the pointers from the
                # given node up to the root node of its tree,
                # which we take to represent the set.
                #
                fun chase u
                    =
                    {   v =   rwv::get (trees, u);                                      # Follow child->parent pointer.

                        if (v == u)   u;                                                # Found root of tree.
                        else          chase v;                                          # Not yet at root, so keep following pointers.
                        fi;
                    };


                # Now we need to be able to take the union of
                # two sets.  We accept any two function ids
                # as naming the sets to which they currently
                # belong.  We find the root elements of each
                # set (tree) then point one to the other,
                # thus combining them into a single tree.
                # 
                fun union (t1, t2)
                    =
                    {   r1 =   chase t1;
                        r2 =   chase t2;

                        if (r1 != r2)
                            #                   
                            if (r1 < r2)   rwv::set (trees, r2, r1);
                            else           rwv::set (trees, r1, r2);
                            fi;
                        fi;
                    };


                # Now we conceptually iterate over all edges in the
                # callgraph, doing a union on the two nodesets
                # represented by calling-function and called-function.
                #
                # Since we don't actually have an explicit representation
                # of the callgraph, what we do is iterate over all of
                # our functions, and for function iterate over all the
                # instructions in the function body, looking for APPLY
                # instructions, which constitute the edges in our callgraph:
                #
                unify_all_nodes_joined_by_edge_in_callgraph
                    #   
                    functions
                where

                    fun unify_all_nodes_joined_by_edge_in_callgraph ((_, function_label, _, _, function_body) ! remaining_functions)
                            =>
                            {   do_all_calls_in  function_body;
                                #
                                unify_all_nodes_joined_by_edge_in_callgraph  remaining_functions;
                            }
                            where
                                function_id =   function_label_to_function_id  function_label;                                                          # This is one of the two callgraph nodes we need to do a untion.

                                fun do_all_calls_in (ncf::TAIL_CALL { func => ncf::LABEL function_label, ... })
                                        =>
                                        union (function_id, function_label_to_function_id function_label);                                              # Bingo! Unify the callgraph components of caller and callee.

                                    do_all_calls_in (ncf::TAIL_CALL _)                           =>  ();                                                # We ignore calls where we can't trivially figure out which fn is being called.
                                    #
                                    do_all_calls_in (ncf::DEFINE_RECORD          r)  =>  do_all_calls_in  r.next;                                       # We ignore all non-APPLY functions, merely looping to the next
                                    do_all_calls_in (ncf::GET_FIELD_I            r)  =>  do_all_calls_in  r.next;                                       # instruction in the function body.
                                    do_all_calls_in (ncf::GET_ADDRESS_OF_FIELD_I r)  =>  do_all_calls_in  r.next;
                                    #
                                    do_all_calls_in (ncf::STORE_TO_RAM           r)  =>  do_all_calls_in  r.next;
                                    do_all_calls_in (ncf::FETCH_FROM_RAM         r)  =>  do_all_calls_in  r.next;
                                    #
                                    do_all_calls_in (ncf::MATH                   r)  =>  do_all_calls_in  r.next;
                                    do_all_calls_in (ncf::PURE                   r)  =>  do_all_calls_in  r.next;
                                    do_all_calls_in (ncf::RAW_C_CALL             r)  =>  do_all_calls_in  r.next;
                                    #
                                    do_all_calls_in (ncf::IF_THEN_ELSE { then_next, else_next, ... })                                                   # IF_THEN_ELSE instructions have two 'next instruction' -- do both.
                                        =>                                                                                                              # Note that this cannot loop because at this point all looping
                                        {   do_all_calls_in  then_next;                                                                                 # is represented via function calls (APPLY nodes), which we do not follow.
                                            do_all_calls_in  else_next;
                                        };
                                    #
                                    do_all_calls_in (ncf::JUMPTABLE { nexts, ... })      =>  forall nexts;                                              # A JUMPTABLE has even more 'next instruction's than an IF_THEN_ELSE. Do them all.
                                    #
                                    do_all_calls_in (ncf::DEFINE_FUNS _)                    =>  error "do_all_calls_in::f: ncf::DEFINE_FUNS";
                                end

                                also
                                fun forall (e ! es) =>  {  do_all_calls_in e;  forall es;  };
                                    forall []       =>  ();
                                end;
                            end;


                        unify_all_nodes_joined_by_edge_in_callgraph [] =>   ();
                    end;                                                                                                                                # fun unify_all_nodes_joined_by_edge_in_callgraph 
                end;


                # At this point we have identified all of the connected
                # components in the nextcode callgraph;  we just need to
                # extract them from our funky trees-in-an-int-vector
                # representation and return them as a vanilla list.
                #
                # We will represent each connected component as a list
                # of nextcode functions, so our return value will be
                # a list of lists of nextcode functions: 
                #
                make_list_of_all_connected_components_in_callgraph ()
                where
                    # The first fun in the funs list
                    # must be the first function
                    # in the first cluster.
                    #
                    fun make_list_of_all_connected_components_in_callgraph ()
                        =
                        {   build_individual_connected_component_lists (function_count - 1)                             # Add each function to the appropriate connected-component list.
                            except
                                _ = ();

                            build_final_list_of_lists (function_count - 1, []);
                        }
                        where
                            callgraph_connected_components =   rwv::make_rw_vector (function_count, []);                # Make a vector in which to build up the individual connected-component lists of functions.

                            # Since our trees aren't optimized, this is probably O(N**2):
                            #   
                            fun build_individual_connected_component_lists  function_id                                 # Over all function ids.
                                =
                                {     root     = chase function_id;                                                     # To which connected component does this function belong?
                                      function = rwv::get (function_id_to_function_table, function_id);                 # Get the actual nextcode function corresponding to function_id.
                                      connected_component  = rwv::get (callgraph_connected_components, root);           # Get the actual connected-component list.
                                      rwv::set (callgraph_connected_components, root, function ! connected_component);  # Add our function to that list.

                                      build_individual_connected_component_lists (function_id - 1);
                                };


                            fun build_final_list_of_lists (-1, resultlist)
                                    =>
                                    resultlist;

                                build_final_list_of_lists (n, resultlist)
                                    => 
                                    case (rwv::get (callgraph_connected_components, n))
                                        #
                                        []                  =>   build_final_list_of_lists (n - 1,                       resultlist);
                                        connected_component =>   build_final_list_of_lists (n - 1, connected_component ! resultlist);
                                   esac;
                            end;
                        end;
                end;
            };                                                                  # fun find_nextcode_cccomponents 
    };                                                                          # package find_nextcode_cccomponents
end;


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext