aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/flow/ebb.inc
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/flow/ebb.inc
downloadotp-84adefa331c4159d432d22840663c38f155cd4c1.tar.gz
otp-84adefa331c4159d432d22840663c38f155cd4c1.tar.bz2
otp-84adefa331c4159d432d22840663c38f155cd4c1.zip
The R13B03 release.OTP_R13B03
Diffstat (limited to 'lib/hipe/flow/ebb.inc')
-rw-r--r--lib/hipe/flow/ebb.inc247
1 files changed, 247 insertions, 0 deletions
diff --git a/lib/hipe/flow/ebb.inc b/lib/hipe/flow/ebb.inc
new file mode 100644
index 0000000000..42d7ff3793
--- /dev/null
+++ b/lib/hipe/flow/ebb.inc
@@ -0,0 +1,247 @@
+%% -*- Erlang -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2001-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%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% IDENTIFIES THE EXTENDED BASIC BLOCKS OF A CFG
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-export([cfg/1,
+ %% dag/2,
+ type/1,
+ node_label/1,
+ node_successors/1
+ ]).
+-ifdef(DEBUG_EBB).
+-export([pp/1]).
+-endif.
+
+-define(cfg, ?CFG).
+
+%%--------------------------------------------------------------------
+%% The extended basic block datatype
+%%
+%% An EBB is identified with the label of the root node.
+%% It's a tree
+%%
+%% EBB := {ebb_node, Label, [EBB]}
+%% | {ebb_leaf, SuccesorLabel}
+%%--------------------------------------------------------------------
+
+%% XXX: Cheating big time! no recursive types
+-type ebb() :: {ebb_node, icode_lbl(), _}
+ | {ebb_leaf, icode_lbl()}.
+
+-record(ebb_node, {label :: icode_lbl(), successors :: [ebb()]}).
+-record(ebb_leaf, {successor :: icode_lbl()}).
+
+%%--------------------------------------------------------------------
+%% Returns a list of extended basic blocks.
+%%--------------------------------------------------------------------
+
+-spec cfg(cfg()) -> [ebb()].
+
+cfg(CFG) ->
+ Start = ?cfg:start_label(CFG),
+ Labels = ?cfg:reverse_postorder(CFG),
+ Roots = [Start],
+ Blocks = Labels -- Roots,
+ Visited = new_visited(),
+ build_all_ebb(Roots, Blocks, Visited, CFG).
+
+new_visited() ->
+ gb_sets:empty().
+visited(L, Visited) ->
+ gb_sets:is_member(L, Visited).
+visit(L, Visited) ->
+ gb_sets:add(L, Visited).
+
+build_all_ebb(Roots, Blocks, Visited, CFG) ->
+ build_all_ebb(Roots, Blocks, Visited, CFG, []).
+
+build_all_ebb([], [], _, _CFG, Ebbs) ->
+ lists:reverse(Ebbs);
+build_all_ebb([], [BlockLeft|BlocksLeft], Visited, CFG, Ebbs) ->
+ case visited(BlockLeft, Visited) of
+ true ->
+ build_all_ebb([], BlocksLeft, Visited, CFG, Ebbs);
+ false ->
+ build_all_ebb([BlockLeft], BlocksLeft, Visited, CFG, Ebbs)
+ end;
+build_all_ebb([Root|Roots], Blocks, Visited, CFG, Ebbs) ->
+ {Ebb, NewVisited} = build_ebb(Root, Visited, CFG),
+ build_all_ebb(Roots, Blocks, NewVisited, CFG, [Ebb|Ebbs]).
+
+%%
+%% Build the extended basic block with Lbl as its root.
+%%
+
+build_ebb(Lbl, Visited, CFG) ->
+ build_ebb(Lbl, Visited,
+ fun (NodeL, NewVisited) -> {NodeL, NewVisited} end,
+ [], CFG).
+
+build_ebb(Lbl, Visited, MkFun, EBBs, CFG) ->
+ Succ = ?cfg:succ(CFG, Lbl),
+ add_succ(Succ, visit(Lbl, Visited), Lbl, MkFun, EBBs, CFG).
+
+add_succ([], Visited, Node, MkFun, EBBs, _CFG) ->
+ MkFun(mk_node(Node, lists:reverse(EBBs)), Visited);
+add_succ([Lbl|Lbls], Visited, Node, MkFun, EBBs, CFG) ->
+ case [visited(Lbl, Visited)|?cfg:pred(CFG, Lbl)] of
+ [false,_] ->
+ build_ebb(Lbl, Visited,
+ fun (NewEbb, Visited0) ->
+ add_succ(Lbls, Visited0, Node, MkFun, [NewEbb|EBBs], CFG)
+ end, [], CFG);
+ _ ->
+ add_succ(Lbls, Visited, Node, MkFun, [mk_leaf(Lbl)|EBBs], CFG)
+ end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Generate a list of dags.
+%%
+
+%% dag(EBBs, CFG) ->
+%% Start = ?cfg:start_label(CFG),
+%% Roots = [Start],
+%% Edges = all_adges(EBBs, Roots),
+%% start_dag(Roots, Edges, []).
+%%
+%% start_dag([], _Edges, _Visit) ->
+%% [];
+%% start_dag([Root|Roots], Edges, Visit) ->
+%% case lists:member(Root, Visit) of
+%% true ->
+%% start_dag(Roots, Edges, Visit);
+%% false ->
+%% {Dag, Roots0, Visit0} =
+%% fill_dag(Root, [Root], Edges, Roots, [Root|Visit]),
+%% [lists:reverse(Dag) | start_dag(Roots0, Edges, Visit0)]
+%% end.
+%%
+%% fill_dag(Lbl, Dag, Edges, Roots, Visit) ->
+%% Succ = find_succ(Lbl, Edges),
+%% add_dag_succ(Succ, Dag, Edges, Roots, Visit).
+%%
+%% add_dag_succ([], Dag, _Edges, Roots, Visit) ->
+%% {Dag, Roots, Visit};
+%% add_dag_succ([S|Ss], Dag, Edges, Roots, Visit) ->
+%% {Dag0, Roots0, Visit0} = add_dag_succ(Ss, Dag, Edges, Roots, Visit),
+%% Pred = find_pred(S, Edges),
+%% case all_in(Pred, Dag0) of
+%% true ->
+%% fill_dag(S, [S|Dag0], Edges, Roots0, [S|Visit0]);
+%% false ->
+%% {Dag0, [S|Roots], Visit0}
+%% end.
+%%
+%% find_succ(_Lbl, []) ->
+%% [];
+%% find_succ(Lbl, [{Lbl, Succ}|Edges]) ->
+%% [Succ | find_succ(Lbl, Edges)];
+%% find_succ(Lbl, [_|Edges]) ->
+%% find_succ(Lbl, Edges).
+%%
+%% find_pred(_Lbl, []) ->
+%% [];
+%% find_pred(Lbl, [{Pred, Lbl}|Edges]) ->
+%% [Pred | find_pred(Lbl, Edges)];
+%% find_pred(Lbl, [_|Edges]) ->
+%% find_pred(Lbl, Edges).
+%%
+%% all_edges([], _Roots) ->
+%% [];
+%% all_edges([EBB|EBBs], Roots) ->
+%% succ_edges(node_label(EBB), ebb_successors(EBB), EBBs, Roots).
+%%
+%% succ_edges(Lbl, [], EBBs, Roots) ->
+%% case lists:member(Lbl, Roots) of
+%% true ->
+%% [{start, Lbl} | all_edges(EBBs, Roots)];
+%% false ->
+%% all_edges(EBBs, Roots)
+%% end;
+%% succ_edges(Lbl, [S|Ss], EBBs, Roots) ->
+%% [{Lbl, S} | succ_edges(Lbl, Ss, EBBs, Roots)].
+%%
+%% all_in([], _List) ->
+%% true;
+%% all_in([X|Xs], List) ->
+%% lists:member(X, List) andalso all_in(Xs, List).
+%%
+%% find_ebb(Lbl, [EBB|EBBs]) ->
+%% case node_label(EBB) of
+%% Lbl ->
+%% EBB;
+%% _ ->
+%% find_ebb(Lbl, EBBs)
+%% end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-spec mk_node(icode_lbl(), [ebb()]) -> #ebb_node{}.
+mk_node(Label, Successors) -> #ebb_node{label=Label, successors=Successors}.
+
+-spec node_label(#ebb_node{}) -> icode_lbl().
+node_label(#ebb_node{label=Label}) -> Label.
+
+-spec node_successors(#ebb_node{}) -> [ebb()].
+node_successors(#ebb_node{successors=Successors}) -> Successors.
+
+-spec mk_leaf(icode_lbl()) -> #ebb_leaf{}.
+mk_leaf(NextEbb) -> #ebb_leaf{successor=NextEbb}.
+%% leaf_next(Leaf) -> Leaf#ebb_leaf.successor.
+
+-spec type(#ebb_node{}) -> 'node' ; (#ebb_leaf{}) -> 'leaf'.
+type(#ebb_node{}) -> node;
+type(#ebb_leaf{}) -> leaf.
+
+%% ebb_successors(EBB) ->
+%% ordsets:from_list(ebb_successors0(EBB)).
+%%
+%% ebb_successors0(#ebb_leaf{successor=NextEBB}) ->
+%% [NextEBB];
+%% ebb_successors0(#ebb_node{successors=SuccessorNodes}) ->
+%% lists:append(lists:map(fun ebb_successors0/1, SuccessorNodes)).
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Prettyprint a list of extended basic blocks
+%%
+
+-ifdef(DEBUG_EBB).
+
+pp(EBBs) ->
+ lists:map(fun(E) -> pp(E, 0) end, EBBs).
+
+pp(EBB, Indent) ->
+ io:format([$~]++integer_to_list(Indent)++[$c],[$ ]),
+ case type(EBB) of
+ node ->
+ io:format("~w~n", [node_label(EBB)]),
+ lists:map(fun(E) -> pp(E, Indent+3) end, node_successors(EBB));
+ leaf ->
+ io:format("* -> ~w~n", [leaf_next(EBB)])
+ end.
+
+-endif.