%% -*- erlang-indent-level: 2 -*- %% %% %CopyrightBegin% %% %% Copyright Ericsson AB 2004-2011. All Rights Reserved. %% %% The contents of this file are subject to the Erlang Public License, %% Version 1.1, (the "License"); you may not use this file except in %% compliance with the License. You should have received a copy of the %% Erlang Public License along with this software. If not, it can be %% retrieved online at http://www.erlang.org/. %% %% Software distributed under the License is distributed on an "AS IS" %% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See %% the License for the specific language governing rights and limitations %% under the License. %% %% %CopyrightEnd% %% %%----------------------------------------------------------------------- %% File : hipe_icode_callgraph.erl %% Author : Tobias Lindahl <tobiasl@it.uu.se> %% Purpose : Creates a call graph to find out in what order functions %% in a module have to be compiled to gain best information %% in hipe_icode_type.erl. %% %% Created : 7 Jun 2004 by Tobias Lindahl <tobiasl@it.uu.se> %%----------------------------------------------------------------------- -module(hipe_icode_callgraph). -export([construct/1, get_called_modules/1, to_list/1, construct_callgraph/1]). -define(NO_UNUSED, true). -ifndef(NO_UNUSED). -export([is_empty/1, take_first/1, pp/1]). -endif. -include("hipe_icode.hrl"). -include("hipe_icode_primops.hrl"). %%------------------------------------------------------------------------ -type mfa_icode() :: {mfa(), #icode{}}. -record(icode_callgraph, {codedict :: dict(), ordered_sccs :: [[mfa()]]}). %%------------------------------------------------------------------------ %% Exported functions %%------------------------------------------------------------------------ -spec construct([mfa_icode()]) -> #icode_callgraph{}. construct(List) -> Calls = get_local_calls(List), %% io:format("Calls: ~p\n", [lists:keysort(1, Calls)]), Edges = get_edges(Calls), %% io:format("Edges: ~p\n", [Edges]), DiGraph = hipe_digraph:from_list(Edges), Nodes = ordsets:from_list([MFA || {MFA, _} <- List]), DiGraph1 = hipe_digraph:add_node_list(Nodes, DiGraph), SCCs = hipe_digraph:reverse_preorder_sccs(DiGraph1), #icode_callgraph{codedict = dict:from_list(List), ordered_sccs = SCCs}. -spec construct_callgraph([mfa_icode()]) -> hipe_digraph:hdg(). construct_callgraph(List) -> Calls = get_local_calls2(List), Edges = get_edges(Calls), hipe_digraph:from_list(Edges). -spec to_list(#icode_callgraph{}) -> [mfa_icode()]. to_list(#icode_callgraph{codedict = Dict, ordered_sccs = SCCs}) -> FlatList = lists:flatten(SCCs), [{MFA, dict:fetch(MFA, Dict)} || MFA <- FlatList]. %%------------------------------------------------------------------------ -ifndef(NO_UNUSED). -spec is_empty(#icode_callgraph{}) -> boolean(). is_empty(#icode_callgraph{ordered_sccs = SCCs}) -> SCCs =:= []. -spec take_first(#icode_callgraph{}) -> {[mfa_icode()], #icode_callgraph{}}. take_first(#icode_callgraph{codedict = Dict, ordered_sccs = [H|T]} = CG) -> SCCCode = [{Mod, dict:fetch(Mod, Dict)} || Mod <- H], {SCCCode, CG#icode_callgraph{ordered_sccs = T}}. -spec pp(#icode_callgraph{}) -> 'ok'. pp(#icode_callgraph{ordered_sccs = SCCs}) -> io:format("Callgraph ~p\n", [SCCs]). -endif. %%------------------------------------------------------------------------ %% Get the modules called from this module -spec get_called_modules([mfa_icode()]) -> ordset(atom()). get_called_modules(List) -> get_remote_calls(List, []). get_remote_calls([{_MFA, Icode}|Left], Acc) -> CallSet = get_remote_calls_1(hipe_icode:icode_code(Icode), Acc), get_remote_calls(Left, ordsets:union(Acc, CallSet)); get_remote_calls([], Acc) -> Acc. get_remote_calls_1([I|Left], Set) -> NewSet = case I of #icode_call{} -> case hipe_icode:call_type(I) of remote -> {M, _F, _A} = hipe_icode:call_fun(I), ordsets:add_element(M, Set); _ -> Set end; #icode_enter{} -> case hipe_icode:enter_type(I) of remote -> {M, _F, _A} = hipe_icode:enter_fun(I), ordsets:add_element(M, Set); _ -> Set end; _ -> Set end, get_remote_calls_1(Left, NewSet); get_remote_calls_1([], Set) -> Set. %%------------------------------------------------------------------------ %% Find functions called (or entered) by each function. get_local_calls(List) -> RemoveFun = fun ordsets:del_element/2, get_local_calls(List, RemoveFun, []). get_local_calls2(List) -> RemoveFun = fun(_,Set) -> Set end, get_local_calls(List, RemoveFun, []). get_local_calls([{{_M, _F, _A} = MFA, Icode}|Left], RemoveFun, Acc) -> CallSet = get_local_calls_1(hipe_icode:icode_code(Icode)), %% Exclude recursive calls. CallSet1 = RemoveFun(MFA, CallSet), get_local_calls(Left, RemoveFun, [{MFA, CallSet1}|Acc]); get_local_calls([], _RemoveFun, Acc) -> Acc. get_local_calls_1(Icode) -> get_local_calls_1(Icode, []). get_local_calls_1([I|Left], Set) -> NewSet = case I of #icode_call{} -> case hipe_icode:call_type(I) of local -> Fun = hipe_icode:call_fun(I), ordsets:add_element(Fun, Set); primop -> case hipe_icode:call_fun(I) of #mkfun{mfa = Fun} -> ordsets:add_element(Fun, Set); _ -> Set end; remote -> Set end; #icode_enter{} -> case hipe_icode:enter_type(I) of local -> Fun = hipe_icode:enter_fun(I), ordsets:add_element(Fun, Set); primop -> case hipe_icode:enter_fun(I) of #mkfun{mfa = Fun} -> ordsets:add_element(Fun, Set); _ -> Set end; remote -> Set end; _ -> Set end, get_local_calls_1(Left, NewSet); get_local_calls_1([], Set) -> Set. %%------------------------------------------------------------------------ %% Find the edges in the callgraph. get_edges(Calls) -> get_edges(Calls, []). get_edges([{MFA, Set}|Left], Edges) -> EdgeList = [{MFA, X} || X <- Set], EdgeSet = ordsets:from_list(EdgeList), get_edges(Left, ordsets:union(EdgeSet, Edges)); get_edges([], Edges) -> Edges.