diff options
Diffstat (limited to 'lib/hipe/flow/ebb.inc')
| -rw-r--r-- | lib/hipe/flow/ebb.inc | 247 |
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. |