diff options
Diffstat (limited to 'lib/hipe/flow/hipe_dominators.erl')
| -rw-r--r-- | lib/hipe/flow/hipe_dominators.erl | 715 |
1 files changed, 715 insertions, 0 deletions
diff --git a/lib/hipe/flow/hipe_dominators.erl b/lib/hipe/flow/hipe_dominators.erl new file mode 100644 index 0000000000..3bfa6d43c4 --- /dev/null +++ b/lib/hipe/flow/hipe_dominators.erl @@ -0,0 +1,715 @@ +%% -*- 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]). + +-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. |