# 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.sublibstipulate
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.pkgherein
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, \\ 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 { fn => 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::ARITH 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;