hipe_dominators.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 700 行 · 第 1/2 页

%% -*- erlang-indent-level: 2 -*-
%%------------------------------------------------------------------------
%% File    : hipe_dominators.erl
%% Author  : Christoffer Vikstr鰉 <[e-mail]>
%%           Daniel Deogun        <[e-mail]>
%%           Jesper Bengtsson     <[e-mail]>
%% 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]).

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

-record(domTree, {root, size, nodes}).

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

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

domTree_create(CFG) ->
  PredMap = hipe_gen_cfg:pred_map(CFG),
  {WorkData, DFS, N} = dfs(CFG),
  {DomData, WorkData2} = getIdoms(CFG,
				  domTree_empty(hipe_gen_cfg:start_label(CFG)),
				  WorkData, N, DFS, PredMap),
  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,
	   size = 0,
	   nodes = gb_trees:empty()}.

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

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) ->
  WD = lookup(Key, Table),
  lookup(Field, WD);
lookup(Node, DomTree = #domTree{}) ->
  case gb_trees:lookup(Node, domTree_getNodes(DomTree)) of
    {value, Data} ->
      Data;
    none ->
      {none, []}
  end;
lookup(Field, WD = #workDataCell{}) ->
  case Field of
    dfnum    -> WD#workDataCell.dfnum; 
    dfparent -> WD#workDataCell.dfparent; 
    semi     -> WD#workDataCell.semi;
    ancestor -> WD#workDataCell.ancestor;
    best     -> WD#workDataCell.best;
    samedom  -> WD#workDataCell.samedom;
    bucket   -> WD#workDataCell.bucket;
    _Other   -> erlang:fault({?MODULE, lookup, 2})
  end;
lookup(N, Table) when is_integer(N) ->
  case gb_trees:lookup(N, 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(Key, Table)), Table);
update(Key, List, Table) ->
  gb_trees:enter(Key, update(List, lookup(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);