%% -*- erlang-indent-level: 2 -*-
%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
%%
%% http://www.apache.org/licenses/LICENSE-2.0
%%
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
%%
%%-----------------------------------------------------------------------
%% File : hipe_icode_callgraph.erl
%% Author : Tobias Lindahl <[email protected]>
%% 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 <[email protected]>
%%-----------------------------------------------------------------------
-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: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()]) -> ordsets: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.
