path: root/lib/hipe/flow/hipe_dominators.erl

%% -*- 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_dominators.erl
%% Author  : Christoffer Vikstr�m <[email protected]>
%%           Daniel Deogun        <[email protected]>
%%           Jesper Bengtsson     <[email protected]>
%% Created : 18 Mar 2002
%%
%% @doc
%%   Contains utilities for creating and manipulating dominator trees
%%   and dominance frontiers from a CFG.
%% @end
%%------------------------------------------------------------------------ 
-module(hipe_dominators).

-export([domTree_create/1,
	 domTree_getChildren/2,
	 domTree_dominates/3,
	 domFrontier_create/2,
	 domFrontier_get/2]).

-export_type([domTree/0]).

-include("cfg.hrl").

%%========================================================================
%%
%% CODE FOR CREATING AND MANIPULATING DOMINATOR TREES.
%%
%%========================================================================

-record(workDataCell, {dfnum = 0       :: non_neg_integer(),
		       dfparent = none :: 'none' | cfg_lbl(),
		       semi = none     :: 'none' | cfg_lbl(),
		       ancestor = none :: 'none' | cfg_lbl(),
		       best = none     :: 'none' | cfg_lbl(),
		       samedom = none  :: 'none' | cfg_lbl(), 
		       bucket = []     :: [cfg_lbl()]}).

-record(domTree, {root                     :: cfg_lbl(),
		  size  = 0		   :: non_neg_integer(),
		  nodes = gb_trees:empty() :: gb_tree()}).
-type domTree() :: #domTree{}.

%%>----------------------------------------------------------------------<
%% Procedure : domTree_create/1
%% Purpose   : Creates a complete dominator tree given a CFG.
%% Arguments : CFG - a Control Flow Graph representation
%% Returns   : A dominator tree
%%>----------------------------------------------------------------------<

-spec domTree_create(cfg()) -> domTree().

domTree_create(CFG) ->
  {WorkData, DFS, N} = dfs(CFG),
  DomTree = domTree_empty(hipe_gen_cfg:start_label(CFG)),
  {DomData, WorkData2} = getIdoms(CFG, DomTree, WorkData, N, DFS),
  finalize(WorkData2, DomData, 1, N, DFS).

%%>----------------------------------------------------------------------<
%% Procedure : domTree_empty/0
%% Purpose   : Creates an empty dominator tree.
%% Arguments : The root node
%% Returns   : A dominator tree
%%>----------------------------------------------------------------------<

domTree_empty(Node) ->
  #domTree{root = Node}.

%%>----------------------------------------------------------------------<
%% Procedure : domTree_createNode/2
%% Purpose   : Creates a new node and inserts it into the dominator tree. 
%% Arguments : Node    - The new node
%%             DomTree - The target dominator tree
%% Returns   : A dominator tree
%%>----------------------------------------------------------------------<

domTree_createNode(Node, DomTree) ->
  DomTree2 = domTree_setNodes(DomTree,
			      gb_trees:enter(Node, {none,[]},
					     domTree_getNodes(DomTree))),
  domTree_incSize(DomTree2).

%%>----------------------------------------------------------------------<
%% Procedure : domTree_getNode/2
%% Purpose   : Returns a specific node in the dominator tree.
%% Arguments : Node - The new node
%%             DomTree - The target dominator tree
%% Returns   : Node
%%>----------------------------------------------------------------------<

domTree_getNode(Node, DomTree) ->
  gb_trees:lookup(Node, domTree_getNodes(DomTree)).

%%>----------------------------------------------------------------------<
%% Procedure : domTree_getNodes/1
%% Purpose   : Retrieves the nodes from a dominator tree.
%% Arguments : DomTree - The target dominator tree
%% Returns   : A map containing the nodes of the dominator tree.
%%>----------------------------------------------------------------------<

domTree_getNodes(#domTree{nodes=Nodes}) -> Nodes.

%%>----------------------------------------------------------------------<
%% Procedure : domTree_setNodes/2
%% Purpose   : Replaces the set of nodes in a dominator tree with a 
%%             new set of nodes.
%% Arguments : Nodes   - The new set of nodes
%%             DomTree - The target dominator tree
%% Returns   : DomTree
%%>----------------------------------------------------------------------<

domTree_setNodes(DomTree, Nodes) -> DomTree#domTree{nodes = Nodes}.

%%>----------------------------------------------------------------------<
%% Procedure : domTree_setSize/2
%% Purpose   : Sets the size of the dominator tree, i.e. the number of 
%%             nodes in it.
%% Arguments : Size    - The new size of the target dominator tree
%%             DomTree - The target dominator tree
%% Returns   : A dominator tree
%%>----------------------------------------------------------------------<

domTree_setSize(DomTree, Size) -> DomTree#domTree{size = Size}.

%%>----------------------------------------------------------------------<
%% Procedure : domTree_incSize/1
%% Purpose   : Increases the size of the dominator tree with one.
%% Arguments : DomTree - The target dominator tree
%% Returns   : DomTree
%%>----------------------------------------------------------------------<

domTree_incSize(DomTree) ->
  Size = domTree_getSize(DomTree),
  domTree_setSize(DomTree, Size + 1).

%%>----------------------------------------------------------------------<
%% Procedure : get IDom/2
%% Purpose   : Retrieves the immediate dominators of a node in the 
%%             dominator tree.
%% Arguments : Node    - The new node
%%             DomTree - The target dominator tree
%% Returns   : The immediate dominator
%%>----------------------------------------------------------------------<

domTree_getIDom(Node, DomTree) ->
  case domTree_getNode(Node, DomTree) of
    {value, {IDom, _}} ->
      IDom;
    none ->
      []
  end.

%%>----------------------------------------------------------------------<
%% Procedure : getChildren/2
%% Purpose   : Retrieves the children of a node in the dominator tree.
%% Arguments : Node    - The new node
%%             DomTree - The target dominator tree
%% Returns   : [children]
%%>----------------------------------------------------------------------<

-spec domTree_getChildren(cfg_lbl(), domTree()) -> [cfg_lbl()].

domTree_getChildren(Node, DomTree) ->
  case domTree_getNode(Node, DomTree) of
    {value, {_, Children}} ->
      Children;
    none ->
      []
  end.

%%>----------------------------------------------------------------------<
%% Procedure : domTree_getSize/1
%% Purpose   : Retrieves the size of a dominator tree.
%% Arguments : DomTree - The target dominator tree
%% Returns   : A number denoting the size of the dominator tree
%%>----------------------------------------------------------------------<

domTree_getSize(#domTree{size=Size}) -> Size.

%%>----------------------------------------------------------------------<
%% Procedure : domTree_getRoot/2
%% Purpose   : Retrieves the number of the root node in the dominator tree.
%% Arguments : DomTree - The target dominator tree
%% Returns   : Number
%%>----------------------------------------------------------------------<

domTree_getRoot(#domTree{root=Root}) -> Root.

%%>----------------------------------------------------------------------<
%% Procedure : domTree_addChild/3
%% Purpose   : Inserts a new node as a child to another node in the
%%             dominator tree.
%% Arguments : Node    - The old node that should get a new child
%%             Child   - The new child node
%%             DomTree - The target dominator tree
%% Returns   : DomTree
%%>----------------------------------------------------------------------<

domTree_addChild(Node, Child, DomTree) ->
  {IDom, Children} = case domTree_getNode(Node, DomTree) of
		       {value, Tuple} ->
			 Tuple;
		       none ->
			 {none, []}
		     end,
  Nodes = case lists:member(Child, Children) of 
	    true ->
	      domTree_getNodes(DomTree);
	    false ->
	      gb_trees:enter(Node, {IDom, [Child|Children]},
			     domTree_getNodes(DomTree))
	  end,
  domTree_setNodes(DomTree, Nodes).

%%>----------------------------------------------------------------------<
%% Procedure : setIDom/3
%% Purpose   : Sets the immediate domminator of a node in the domminator tree.
%% Arguments : Node    - The node whose immediate domminator we are seting
%%             IDom    - The immediate domminator
%%             DomTree - The target dominator tree
%% Returns   : DomTree
%% Notes     : Is used to build the dominator tree.
%%>----------------------------------------------------------------------<

setIDom(Node, IDom, DomTree) ->
  DomTree1 = case domTree_getNode(Node, DomTree) of
	       none ->
		 domTree_createNode(Node, DomTree);
	       _ ->
		 DomTree
	     end,
  DomTree2 = domTree_addChild(IDom, Node, DomTree1),
  {value, {_, Children}} = domTree_getNode(Node, DomTree2),
  domTree_setNodes(DomTree2,
		   gb_trees:enter(Node, {IDom, Children},
				  domTree_getNodes(DomTree2))).

%%>----------------------------------------------------------------------<
%% Procedure : lookup
%% Purpose   : This function is used as a wrapper for the lookup function.
%%             The function retrieves a particular element (defined by
%%             Field) stored in a workDataCell in the table (defined by
%%             Table).
%% Arguments : Field - Value defined in the workDataCell record
%%             Key   - Value used as a key in the table
%%             Table - Table storing workDataCells
%% Returns   : A value defined in the workDataCell record
%%>----------------------------------------------------------------------<

lookup({Field, Key}, Table) when is_integer(Key) ->
  WD = lookup_table(Key, Table),
  case Field of
    ancestor -> WD#workDataCell.ancestor;
    best     -> WD#workDataCell.best;
    bucket   -> WD#workDataCell.bucket;
    dfnum    -> WD#workDataCell.dfnum; 
    dfparent -> WD#workDataCell.dfparent; 
    samedom  -> WD#workDataCell.samedom;
    semi     -> WD#workDataCell.semi    
  end.

lookup_table(Key, Table) when is_integer(Key) ->
  case gb_trees:lookup(Key, Table) of
    {value, Data} ->
      Data;
    none ->
      #workDataCell{}
  end.

%%>----------------------------------------------------------------------<
%% Procedure : update
%% Purpose   : This function is used as a wrapper for the update function 
%%             The main purpose of the update function is therefore
%%             change a particular cell in the table (Table) to the
%%             value given as an argument (Value).
%% Arguments : Key   - Value used as a key in the table
%%             Field - Value defined in the workDataCell record.
%%             Value - The new value that should replace the old in the table
%%             Table - Table storing workDataCells
%% Returns   : NewTable               
%%>----------------------------------------------------------------------<

update(Key, {Field, Value}, Table) ->
  gb_trees:enter(Key, updateCell(Value, Field, lookup_table(Key, Table)), Table);
update(Key, List, Table) ->
  gb_trees:enter(Key, update(List, lookup_table(Key, Table)), Table).

update([{Field, Value} | T], WD) -> 
  update(T, updateCell(Value, Field, WD));
update([], WD) -> WD.

updateCell(Value, Field, WD) ->
  case Field of
    dfnum    -> WD#workDataCell{dfnum   = Value}; 
    dfparent -> WD#workDataCell{dfparent= Value}; 
    semi     -> WD#workDataCell{semi    = Value}; 
    ancestor -> WD#workDataCell{ancestor= Value}; 
    best     -> WD#workDataCell{best    = Value}; 
    samedom  -> WD#workDataCell{samedom = Value}; 
    bucket   -> WD#workDataCell{bucket  = Value}
  end.

%%>----------------------------------------------------------------------<
%% Procedure : dfs/1
%% Purpose   : The main purpose of this function is to traverse the CFG in
%%             a depth first order. It is aslo used to initialize certain 
%%             elements defined in a workDataCell.
%% Arguments : CFG - a Control Flow Graph representation
%% Returns   : A table (WorkData) and the total number of elements in
%%             the CFG.
%%>----------------------------------------------------------------------<

dfs(CFG) ->
  {WorkData, DFS, N} = dfs(CFG, hipe_gen_cfg:start_label(CFG), 
			   none, 1, gb_trees:empty(), gb_trees:empty()),
  {WorkData, DFS, N-1}.

dfs(CFG, Node, Parent, N, WorkData, DFS) ->
  case lookup({dfnum, Node}, WorkData) of
    0 -> 	  
      WorkData2 = update(Node, [{dfnum, N}, {dfparent, Parent}, 
				{semi, Node}, {best, Node}], WorkData),
      DFS2 = gb_trees:enter(N, Node, DFS),
      dfsTraverse(hipe_gen_cfg:succ(CFG, Node), CFG, Node, 
		  N + 1, WorkData2, DFS2);
    _ -> {WorkData, DFS, N}
  end.

%%>----------------------------------------------------------------------<
%% Procedure : dfsTraverse/6
%% Purpose   : This function acts as a help function for the dfs algorithm
%%             in the sence that it traverses a list of nodes given by the 
%%             CFG. 
%% Arguments : Node     - The first element in the node list
%%             SuccLst  - The remainder of the node list
%%             CFG      - Control Flow Graph representation
%%             Parent   - Node representing the parent of the Node defined
%%                        above.
%%             N        - The total number of processed nodes.
%%             WorkData - Table consisting of workDataCells
%% Returns   : An updated version of the table (WorkData) and the 
%%             total number of nodes processed.
%%>----------------------------------------------------------------------<

dfsTraverse([Node|T], CFG, Parent, N, WorkData, DFS) ->
  {WorkData2, DFS2, N2} = dfs(CFG, Node, Parent, N, WorkData, DFS),
  dfsTraverse(T, CFG, Parent, N2, WorkData2, DFS2);
dfsTraverse([], _, _, N, WorkData, DFS) -> {WorkData, DFS, N}.

%%>----------------------------------------------------------------------<
%% Procedure : getIdoms/6
%% Purpose   : The purpose of this function is to compute the immediate
%%             dominators. This is accomplished by traversing the CFG nodes
%%             by their depth first number in a bottom up manner. That is, 
%%             the nodes are processed in a backward order (highest to 
%%             lowest number).
%% Arguments : CFG      - Control Flow Graph representation
%%             DomData  - Table consisting of domTree cells
%%             WorkData - Table consisting of workDataCells
%%             Index    - The index used for retrieving the node to be 
%%                        processed
%% Returns   : An updated version of the tables DomData and WorkData
%%>----------------------------------------------------------------------<

getIdoms(CFG, DomData, WorkData, Index, DFS)
     when is_integer(Index), Index > 1 ->
  Node = lookup_table(Index, DFS),
  PredLst = hipe_gen_cfg:pred(CFG, Node),
  Par = lookup({dfparent, Node}, WorkData),
  DfNumN = lookup({dfnum, Node}, WorkData),
  {S, WorkData2} = getSemiDominator(PredLst, DfNumN, Par, WorkData),
  WorkData3 = update(Node, {semi, S}, WorkData2),
  OldBucket = lookup({bucket, S}, WorkData3),
  WorkData4 = update(S, {bucket, [Node | OldBucket]}, WorkData3),
  WorkData5 = linkTrees(Par, Node, WorkData4),
  {WorkData6, DomData2} = filterBucket(lookup({bucket, Par}, WorkData5), 
				       Par, WorkData5, DomData),
  WorkData7 = update(Par, {bucket, []}, WorkData6),
  getIdoms(CFG, DomData2, WorkData7, Index - 1, DFS);
getIdoms(_, DomData, WorkData, 1, _) ->
  {DomData, WorkData}.

%%>----------------------------------------------------------------------<
%% Procedure : getSemiDominator/4
%% Purpose   : The main purpose of this algorithm is to compute the semi 
%%             dominator of the node Node based on the Semidominator Theorem
%% Arguments : Preds    - The list of predecessors of the node Node
%%             Node     - Node in the CFG
%%             S        - Parent of node Node (depth first parent)
%%             WorkData - Table consisting of workDataCells
%% Returns   : A tuple containing the semidominator and an updated version
%%             of the table WorkData.
%%>----------------------------------------------------------------------<

getSemiDominator([Pred|Preds], DfNumChild, S, WorkData) ->
  {Sp, WorkData3} = 
    case lookup({dfnum, Pred}, WorkData) =< DfNumChild of
      true  -> 
	{Pred, WorkData};
      false ->  
	{AncLowSemi, WorkData2} = getAncestorWithLowestSemi(Pred, WorkData),	
	{lookup({semi, AncLowSemi}, WorkData2), WorkData2}
    end,
  S2 = case lookup({dfnum, Sp}, WorkData3) < lookup({dfnum, S}, WorkData3) of
	 true  -> Sp;
	 false -> S
       end,
  getSemiDominator(Preds, DfNumChild, S2, WorkData3);
getSemiDominator([], _, S, WorkData) ->
  {S, WorkData}.

%%>----------------------------------------------------------------------<
%% Procedure : getAncestorWithLowestSemi/2
%% Purpose   : The main purpose of this function is to retrieve the ancestor 
%%             of a node with the lowest depth first number (semi). The
%%             function is also using path compression, i.e. it remembers the
%%             best node (the one with the lowest semi number) and hence the
%%             algorithm is only processing the minimal number of nodes.
%% Arguments : Node     - Node in the tree
%%             WorkData - Table consisting of workDataCells
%% Returns   : A node (the one with the lowest semi) and an updated version
%%             of the table WorkData.
%%>----------------------------------------------------------------------<

getAncestorWithLowestSemi(Node, WorkData) ->
  Best = lookup({best, Node}, WorkData),
  case lookup({ancestor, Node}, WorkData) of
    none -> {Best, WorkData};
    A -> 
      case lookup({ancestor, A}, WorkData) of
	none -> 
	  {Best, WorkData};
	_ -> 
	  {B, WorkData2} = getAncestorWithLowestSemi(A, WorkData),
	  AncA = lookup({ancestor, A}, WorkData2),
	  WorkData3 = update(Node, {ancestor, AncA}, WorkData2),
	  DfSemiB = lookup({dfnum, lookup({semi, B}, WorkData3)}, WorkData3),
	  BestN = lookup({best, Node}, WorkData3),
	  SemiB = lookup({semi, BestN}, WorkData3),
	  DfSemiBestN = lookup({dfnum, SemiB}, WorkData3),
	  case DfSemiB < DfSemiBestN of
	    true  ->
	      {B, update(Node, {best, B}, WorkData3)};
	    false -> 
	      {BestN, WorkData3}
	  end
      end
  end.

%%>----------------------------------------------------------------------<
%% Procedure : linkTrees/3
%% Purpose   : The main purpose of this function is to combine two trees
%%             into one (accomplished by setting the ancestor for node 
%%             Node to Parent). The algorithm is also updating the best field
%%             in the workDataCell for node Node to the value of itself.
%% Arguments : Parent   - The parent of the node Node.
%%             Node     - The node to process
%%             WorkData - Table consisting of workDataCells
%% Returns   : An updated version of table WorkData
%%>----------------------------------------------------------------------<

linkTrees(Parent, Node, WorkData) ->
  update(Node, [{ancestor, Parent}, {best, Node}], WorkData).

%%>----------------------------------------------------------------------<
%% Procedure : filterBucket/4 
%% Purpose   : The purpose of this algorith is to compute the dominator of
%%             the node Node by utilizing the first clause of the Dominator
%%             Theorem. If the first clause of the theorem doesn't apply 
%%             then the computation of that particular node is deferred to
%%             a later stage (see finalize).
%% Arguments : Nodes    - The list of CFG nodes that need to be computed.
%%             Parent   - The parent of the nodes in the list Nodes
%%             WorkData - Table consisting of workDataCells
%%             DomData  - Table consisting of domTree cells.
%% Returns   : An updated version of the tables WorkData and DomData
%%>----------------------------------------------------------------------<

filterBucket([Node|Nodes], Parent, WorkData, DomData) ->
  {Y, WorkData2} = getAncestorWithLowestSemi(Node, WorkData),
  {WorkData3, DomData2} = 
    case lookup({semi, Y}, WorkData2) =:= lookup({semi, Node}, WorkData2) of
      true  -> {WorkData2, setIDom(Node, Parent, DomData)};
      false -> {update(Node, {samedom, Y}, WorkData2), DomData}
    end,
  filterBucket(Nodes, Parent, WorkData3, DomData2);
filterBucket([], _, WorkData, DomData) ->
  {WorkData, DomData}.	     

%%>----------------------------------------------------------------------<
%% Procedure : finalize/5
%% Purpose   : This algorithm finishes up the second clause of the Dominator
%%             Theorem. Hence, the main purpose of this function is therefore
%%             to update the dominator tree with the nodes that were deferred
%%             in the filterBucket algorithm.
%% Arguments : WorkData - Table consisting of workDataCells
%%             DomData  - Table consisting of domTree cells
%%             N        - The index used for retrieving the node to be 
%%                        processed
%%             Max      - Maximum node index
%% Returns   : An updated version of the table DomData
%%>----------------------------------------------------------------------<

finalize(WorkData, DomData, N, Max, DFS) when N =< Max ->
  Node = lookup_table(N, DFS),
  case lookup({samedom, Node}, WorkData) of
    none ->
      finalize(WorkData, DomData, N + 1, Max, DFS);
    SameDomN -> 
      case domTree_getIDom(SameDomN, DomData) of
	IdomSameDomN when is_integer(IdomSameDomN) ->
	  DomData2 = setIDom(Node, IdomSameDomN, DomData),
	  finalize(WorkData, DomData2, N + 1, Max, DFS)
      end
  end;
finalize(_, DomData, _, _, _) ->
  DomData.

%%>----------------------------------------------------------------------<
%% Procedure : domTree_dominates/3
%% Purpose   : checks wheter Node1 dominates Node2 with respect to the
%%             dominator tree DomTree
%% Arguments : Node1 the possible dominator, Node2 which might be dominated 
%%             and DomTree  - the target dominator tree.
%% Notes     : Relies on lists:any to return false when the a list is empty
%%>----------------------------------------------------------------------<     

-spec domTree_dominates(cfg_lbl(), cfg_lbl(), domTree()) -> boolean().

domTree_dominates(Node1, Node1, _DomTree) ->
  true;
domTree_dominates(Node1, Node2, DomTree) ->
  Children = domTree_getChildren(Node1, DomTree),
  lists:any(fun(X) -> domTree_dominates(X, Node2, DomTree) end, Children).

%%>----------------------------------------------------------------------<
%% Procedure : pp/1
%% Purpose   : Pretty Printing a dominator tree.
%% Arguments : DomTree  - the target dominator tree.
%% Notes     : Uses pp/2 and pp_children to perform its task.
%%>----------------------------------------------------------------------<     

-ifdef(DEBUG).

domTree_pp(DomTree) ->
  io:format("Domtree:\nRoot: ~w\nSize: ~w\n", [domTree_getRoot(DomTree),
					       domTree_getSize(DomTree)]),
  domTree_pp(domTree_getRoot(DomTree), DomTree).

domTree_pp(N, DomTree) ->
  case domTree_getNode(N, DomTree) of
    {value, {IDom, Children}} ->
      io:format("Node: ~w\n\tIDom: ~w\n\tChildren: ~w\n\n",
		[N, IDom, Children]),
      domTree_pp_children(Children, DomTree);
    none ->
      failed
  end.

domTree_pp_children([Child|T], DomTree) ->
  domTree_pp(Child, DomTree),
  domTree_pp_children(T, DomTree);
domTree_pp_children([], _) ->
  ok.

-endif.	%% DEBUG

%%========================================================================
%%
%% CODE FOR CREATING AND MANIPULATING DOMINANCE FRONTIERS.
%%
%%========================================================================

-type domFrontier() :: gb_tree().

%%>----------------------------------------------------------------------<
%% Procedure : domFrontier_create
%% Purpose   : This function calculates the Dominance Frontiers given
%%             a CFG and a Dominator Tree.
%% Arguments : SuccMap - The successor map of the CFG we are working with.
%%             DomTree - The dominance tree of the CFG.
%% Notes     : DomTree must actually be the dominance tree of the CFG.
%%>----------------------------------------------------------------------<

-spec domFrontier_create(cfg(), domTree()) -> domFrontier().

domFrontier_create(SuccMap, DomTree) ->
  df_create(domTree_getRoot(DomTree), SuccMap, DomTree, df__empty()).

df_create(Node, SuccMap, DomTree, DF) ->
  Children = domTree_getChildren(Node, DomTree),
  Succ = hipe_gen_cfg:succ(SuccMap, Node),
  DF1 = checkIDomList(Succ, Node, DomTree, DF),
  makeDFChildren(Children, Node, SuccMap, DomTree, DF1).

%%>----------------------------------------------------------------------<
%% Procedure : domFrontier_get
%% Purpose   : This function returns the Dominance Frontier for Node.
%% Arguments : Node - The node whose Dominance Frontier we request
%%             DF   - The Dominance Frontier structure
%% Returns   : 
%%>----------------------------------------------------------------------<

-spec domFrontier_get(cfg_lbl(), domFrontier()) -> [cfg_lbl()].

domFrontier_get(Node, DF) ->
  case gb_trees:lookup(Node, DF) of
    {value, List} -> List;
    none -> []
  end.

%%>----------------------------------------------------------------------<
%% Procedure : df__empty
%% Purpose   : This function creates an empty instance of the Dominance
%%             Frontiers (DF) structure.
%%>----------------------------------------------------------------------<

df__empty() ->
  gb_trees:empty().

%%>----------------------------------------------------------------------<
%% Procedure : df__add
%% Purpose   : This function adds Node to N in DF.
%% Arguments : N    - The value being inserted
%%             Node - The node getting the value
%%             DF   - The Dominance Frontiers
%% Returns   : DF
%% Notes     : If Node already exists at position N, it is not added again.
%%>----------------------------------------------------------------------<

df__add_to_node(N, Node, DF) ->
  case gb_trees:lookup(N, DF) of
    {value, DFList} ->
      case lists:member(Node, DFList) of
	true ->
	  DF;
	false ->
	  gb_trees:update(N, [Node|DFList], DF)
      end;
    none ->
      gb_trees:insert(N, [Node], DF)
  end.

%%>----------------------------------------------------------------------<
%% Procedure : makeDFChildren
%% Purpose   : This function calculates the dominance frontiers of the
%%             children of the parent and adds the nodes in these
%%             dominance frontiers who are not immediate dominantors of
%%             the parent to parents dominance frontier.
%% Arguments : ChildList - The list of children that the function traverses
%%             Parent - The parent of the children
%%             SuccMap - The successor map of the CFG
%%             DomTree - The dominantor tree of the CFG
%%             DF - The dominance frontiers so far
%%>----------------------------------------------------------------------<

makeDFChildren([Child|T], Parent, SuccMap, DomTree, DF) ->
  DF1 = df_create(Child, SuccMap, DomTree, DF),
  DF2 = checkIDomList(domFrontier_get(Child, DF1), Parent, DomTree, DF1),
  makeDFChildren(T, Parent, SuccMap, DomTree, DF2);
makeDFChildren([], _, _, _, DF) ->
  DF.

%%>----------------------------------------------------------------------<
%% Procedure : checIDomList
%% Purpose   : Adds all the nodes in the list to the parents dominance
%%             frontier who do not have parent as immediate dominator.
%% Arguments : NodeList - The list of nodes that the function traverses
%%             Parent - The parent of the nodes
%%             DomTree - Our dominator tree
%%             DF - The dominance frontiers so far
%%>----------------------------------------------------------------------<

checkIDomList([Node|T], Parent, DomTree, DF) ->
  DF1 = checkIDom(Node, Parent, DomTree, DF),
  checkIDomList(T, Parent, DomTree, DF1);
checkIDomList([], _, _, DF) ->
  DF.

%%>----------------------------------------------------------------------<
%% Procedure : checkIdom
%% Purpose   : Adds Node1 to Node2's dominance frontier if Node2 is not
%%             Node1's immediate dominator.
%% Arguments : Node1 - a node
%%             Node2 - another node
%%             DomTree - the dominator tree
%%             DF - the dominance frontier so far
%%>----------------------------------------------------------------------<

checkIDom(Node1, Node2, DomTree, DF) ->
  case domTree_getIDom(Node1, DomTree) of
    Node2 ->
      DF;
    none ->
      DF;
    _ ->
      df__add_to_node(Node2, Node1, DF)
  end.