%% -*- Erlang -*-
%%
%% 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.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% 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}
%%--------------------------------------------------------------------

-type ebb() :: ebb_node()
	     | ebb_leaf().

-record(ebb_node, {label :: icode_lbl(), successors :: [ebb()]}).
-type ebb_node() :: #ebb_node{}.

-record(ebb_leaf, {successor :: icode_lbl()}).
-type ebb_leaf() :: #ebb_leaf{}.

%%--------------------------------------------------------------------
%% 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.