The R13B03 release.OTP_R13B03

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.