aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/icode/hipe_icode_callgraph.erl
diff options
context:
space:
mode:
authorErlang/OTP <[email protected]>2009-11-20 14:54:40 +0000
committerErlang/OTP <[email protected]>2009-11-20 14:54:40 +0000
commit84adefa331c4159d432d22840663c38f155cd4c1 (patch)
treebff9a9c66adda4df2106dfd0e5c053ab182a12bd /lib/hipe/icode/hipe_icode_callgraph.erl
downloadotp-84adefa331c4159d432d22840663c38f155cd4c1.tar.gz
otp-84adefa331c4159d432d22840663c38f155cd4c1.tar.bz2
otp-84adefa331c4159d432d22840663c38f155cd4c1.zip
The R13B03 release.OTP_R13B03
Diffstat (limited to 'lib/hipe/icode/hipe_icode_callgraph.erl')
-rw-r--r--lib/hipe/icode/hipe_icode_callgraph.erl217
1 files changed, 217 insertions, 0 deletions
diff --git a/lib/hipe/icode/hipe_icode_callgraph.erl b/lib/hipe/icode/hipe_icode_callgraph.erl
new file mode 100644
index 0000000000..95182fc002
--- /dev/null
+++ b/lib/hipe/icode/hipe_icode_callgraph.erl
@@ -0,0 +1,217 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2004-2009. 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 <[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]>
+%%
+%% $Id$
+%%-----------------------------------------------------------------------
+-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 :: [[atom()]]}).
+
+%%------------------------------------------------------------------------
+%% 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),
+ [{Mod, dict:fetch(Mod, Dict)} || Mod <- 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.