%% -*- erlang-indent-level: 2 -*-
%%
%% 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.
%%
%%%=======================================================================
%% File : hipe_icode_ssa_struct_reuse.erl
%% Author : Ragnar Osterlund <[email protected]>
%% student at the compiler techniques 2 course at UU 2007
%% Description : HiPE module that removes redundant or partially redundant
%% structure creations from Icode.
%% It does so by inserting redundant expressions as late
%% as possible in the CFG, with the exception of loops where
%% expressions are moved to just before the loop head.
%% Current Icode instructions that can be moved are mktuple()
%% and cons() primop calls. It also handles cases like
%% f({Z}) -> {Z}. It does so by looking at the structure of
%% the match, and recognizes tuples and conses.
%%=======================================================================
-module(hipe_icode_ssa_struct_reuse).
-export([struct_reuse/1]).
-include("../main/hipe.hrl").
-include("hipe_icode.hrl").
-include("hipe_icode_primops.hrl").
-include("../flow/cfg.hrl").
-define(SET, ordset).
-define(SETS, ordsets).
%%-define(DEBUG, true).
-define(MKTUPLE, mktuple).
-define(CONS, cons).
-define(SR_INSTR_TYPE, sr_instr_type).
-define(SR_STRUCT_INSTR_TYPE, sr_struct_instr_type).
-type struct_type() :: {?CONS | ?MKTUPLE, icode_term_arg(), any()}.
-type struct_elems() :: {icode_var(), non_neg_integer(), icode_term_arg()}.
%% DATATYPE AREA
%%-----------------------------------------------------------------------------
%% maps
%% The maps are used to identify variables and expressions.
%% The maps are:
%%
%% expr - a map that contains value numbered structure expressions, ie
%% mktuple and cons expression. The key is the value number and the value
%% is an expr record.
%%
%% instr - maps the semantic instruction to an expression value number,
%% that is, a key in the expr map above.
%%
%% var - maps variables to expression value numbers. These variables are
%% defined or used by the structure expressions.
-record(maps, {var = gb_trees:empty() :: gb_trees:tree(),
instr = gb_trees:empty() :: gb_trees:tree(),
expr = gb_trees:empty() :: gb_trees:tree()}).
maps_var(#maps{var = Out}) -> Out.
maps_instr(#maps{instr = Out}) -> Out.
maps_expr(#maps{expr = Out}) -> Out.
maps_expr_keys(Maps) -> gb_trees:keys(maps_expr(Maps)).
maps_expr_values(Maps) -> gb_trees:values(maps_expr(Maps)).
maps_instr_lookup(Instr, Maps) -> gb_trees:lookup(Instr, maps_instr(Maps)).
maps_instr_enter(Instr, ExprId, Maps) ->
NewInstr = gb_trees:enter(Instr, ExprId, maps_instr(Maps)),
Maps#maps{instr = NewInstr}.
maps_expr_get(Id, Maps) -> gb_trees:get(Id, maps_expr(Maps)).
maps_expr_enter(Expr, Maps) ->
NewExprMap = gb_trees:enter(expr_id(Expr), Expr, maps_expr(Maps)),
Maps#maps{expr = NewExprMap}.
maps_var_get(Var, Maps) -> gb_trees:get(Var, maps_var(Maps)).
maps_var_lookup(Var, #maps{var = VarMap}) -> gb_trees:lookup(Var, VarMap).
maps_var_enter(Var, Info, Maps = #maps{var = VarMap}) ->
NewMap = gb_trees:enter(Var, Info, VarMap),
Maps#maps{var = NewMap}.
maps_var_insert(Var, Info, Maps = #maps{var = VarMap}) ->
NewMap = gb_trees:insert(Var, Info, VarMap),
Maps#maps{var = NewMap}.
maps_balance(Maps) ->
Maps#maps{instr = gb_trees:balance(maps_instr(Maps)),
expr = gb_trees:balance(maps_expr(Maps)),
var = gb_trees:balance(maps_var(Maps))}.
maps_expr_key_enter(Expr, Maps) ->
NewMaps = maps_instr_enter(expr_key(Expr), expr_id(Expr), Maps),
maps_expr_enter(Expr, NewMaps).
%%-----------------------------------------------------------------------------
%% expr
%% An expression record. Contains information about a structure expression.
%% The fields are:
%%
%% id - the value number of the expression
%% key - the semantic instruction, as defined in icode, with destination
%% removed and arguments rewritten.
%% defs - destination variable to hold the value of the expression.
%% direct_replace - indicates whether the expression shall be replaced wherever
%% it occurs, although it might not have been inserted. This is used for
%% the expressions that are detected by the icode type constructs.
%% inserts - a list of node labels that will insert this expression
%% use - a list of expression value numbers that use the value of this
%% expression
-record(expr, {id = none :: 'none' | non_neg_integer(),
key = none :: 'none' | tuple(), % illegal_icode_instr()
defs = none :: 'none' | [icode_var()],
direct_replace = false :: boolean(),
inserts = ?SETS:new() :: ?SETS:?SET(_),
use = ?SETS:new() :: ?SETS:?SET(_)}).
expr_id(#expr{id = Out}) -> Out.
expr_defs(#expr{defs = Out}) -> Out.
expr_key(#expr{key = Out}) -> Out.
expr_inserts(#expr{inserts = Out}) -> Out.
expr_use(#expr{use = Out}) -> Out.
expr_direct_replace(#expr{direct_replace = Out}) -> Out.
expr_use_add(Expr = #expr{use = UseSet}, Use) ->
Expr#expr{use = ?SETS:add_element(Use, UseSet)}.
%% expr_key_set(Expr, In) -> Expr#expr{key = In}.
expr_direct_replace_set(Expr, In) -> Expr#expr{direct_replace = In}.
expr_inserts_set(Expr, In) -> Expr#expr{inserts = In}.
expr_create(Key, Defs) ->
NewExprId = new_expr_id(),
#expr{id = NewExprId, key = Key, defs = Defs}.
%%-----------------------------------------------------------------------------
%% varinfo
%% A variable mapping info. Contains info about variable references.
%% The fields are:
%%
%% use - a set of expression value numbers that use this variable
%% ref - the variable which value this variable will be assigned
%% when expression is replaced. This is encoded as {N, M} where
%% N is the expression value number and M is the nth destination
%% variable defined by the expression N.
%% elem - indicates that this variable has been detected to be a part of
%% a tuple. The field contains a {V, N} tuple where V is the variable
%% that refers to the structure that this variable is an element in
%% and N is the position that the element occurs on in the tuple. Eg.
%% {{var, 3}, 2} means that the variable {var, 3} refers to a tuple
%% in which this variable is on second place.
%% exprid - a expression value number which is the expression that
%% the variable is defined by.
-record(varinfo, {use = ?SETS:new() :: ?SETS:?SET(_),
ref = none :: 'none' | {non_neg_integer(), non_neg_integer()},
elem = none :: 'none' | {icode_var(), non_neg_integer()},
exprid = none :: 'none' | non_neg_integer()}).
varinfo_exprid(#varinfo{exprid = Out}) -> Out.
varinfo_use_add(#varinfo{use = UseSet} = I, Use) ->
I#varinfo{use = ?SETS:add_element(Use, UseSet)}.
%%-----------------------------------------------------------------------------
%% node - a node in the temp CFG.
%%
%% label - the label of the node in the original CFG
%% pred - a list of predecessors to this node
%% succ - a list of successors to this node
%% code - code from CFG filtered to only contain structure instructions
%% non_struct_defs - a list of variable definitions that are not defined
%% by structures
%% up_expr - upwards exposed expression value numbers
%% killed_expr - killed expressions value numbers
%% sub_inserts - a set of labels of nodes that defines one or more
%% expressions and that are in a subtree of this node
%% inserts - a set of expression value numbers to be inserted into the node
%% antic_in - a set of expression value numbers that are anticipated into
%% the node
%% antic_out - a set of expression value numbers that are anticipated out of
%% the node
%% phi - a tree of node labels which is defined in phi functions in the node
%% varmap - a list of variable tuples {V1, V2} that maps a variable that are
%% the output of phi functions in sub blocks, V1, into a variable
%% flowing from the block of this node, V2.
%% struct_type - a list of {V, N} tuples that indicates that V is a tuple
%% with N elements. These are added from the icode primop type().
%% struct_elems - a list of {VD, N, VS} tuples where VD is a variable in the N'th position
%% in VS. These are added from the icode primop unsafe_element()
-record(node, {
label = none :: 'none' | icode_lbl(),
pred = none :: 'none' | [icode_lbl()],
succ = none :: 'none' | [icode_lbl()],
code = [] :: [tuple()], % [illegal_icode_instr()]
phi = gb_trees:empty() :: gb_trees:tree(),
varmap = [] :: [{icode_var(), icode_var()}],
pre_loop = false :: boolean(),
non_struct_defs = gb_sets:new() :: gb_sets:set(),
up_expr = none :: 'none' | ?SETS:?SET(_),
killed_expr = none :: 'none' | ?SETS:?SET(_),
sub_inserts = ?SETS:new() :: ?SETS:?SET(_),
inserts = ?SETS:new() :: ?SETS:?SET(_),
antic_in = none :: 'none' | ?SETS:?SET(_),
antic_out = none :: 'none' | ?SETS:?SET(_),
struct_type = [] :: [struct_type()],
struct_elems = [] :: [struct_elems()]}).
node_sub_inserts(#node{sub_inserts = Out}) -> Out.
node_inserts(#node{inserts = Out}) -> Out.
node_antic_out(#node{antic_out = Out}) -> Out.
node_antic_in(#node{antic_in = Out}) -> Out.
node_killed_expr(#node{killed_expr = Out}) -> Out.
node_pred(#node{pred = Out}) -> Out.
node_succ(#node{succ = Out}) -> Out.
node_label(#node{label = Out}) -> Out.
node_code(#node{code = Out}) -> Out.
node_non_struct_defs(#node{non_struct_defs = Out}) -> Out.
node_up_expr(#node{up_expr = Out}) -> Out.
node_pre_loop(#node{pre_loop = Out}) -> Out.
node_struct_type(#node{struct_type = Out}) -> Out.
%% node_atom_type(#node{atom_type = Out}) -> Out.
node_struct_elems(#node{struct_elems = Out}) -> Out.
node_pre_loop_set(Node) -> Node#node{pre_loop = true}.
node_phi_add(Node = #node{phi = Phi}, Pred, Value) ->
NewList =
case gb_trees:lookup(Pred, Phi) of
{value, List} -> [Value | List];
none -> [Value]
end,
Node#node{phi = gb_trees:enter(Pred, NewList, Phi)}.
node_phi_get(#node{phi = Phi}, Pred) ->
case gb_trees:lookup(Pred, Phi) of
{value, List} -> List;
none -> []
end.
node_code_add(Node = #node{code = Code}, Instr) ->
Node#node{code = [Instr | Code]}.
node_code_rev(Node = #node{code = Code}) ->
Node#node{code = lists:reverse(Code)}.
node_struct_type_add(Node = #node{struct_type = T}, Value) ->
Node#node{struct_type = [Value | T]}.
%% node_atom_type_add(Node = #node{atom_type = T}, Value) ->
%% Node#node{atom_type = [Value | T]}.
node_struct_elems_add(Node = #node{struct_elems = T}, Value) ->
Node#node{struct_elems = [Value | T]}.
node_non_struct_defs_list(Node) ->
gb_sets:to_list(node_non_struct_defs(Node)).
node_non_struct_instr_add(Node, Instr) ->
DefList = hipe_icode:defines(Instr),
Tmp = gb_sets:union(node_non_struct_defs(Node), gb_sets:from_list(DefList)),
Node#node{non_struct_defs = Tmp}.
node_set_sub_inserts(Node, In) -> Node#node{sub_inserts = In}.
node_add_insert(Node, In) ->
NewIns = ?SETS:add_element(In, node_inserts(Node)),
Node#node{inserts = NewIns}.
node_union_sub_inserts(Node, SubIns) ->
NewSubIns = ?SETS:union(SubIns, node_sub_inserts(Node)),
node_set_sub_inserts(Node, NewSubIns).
node_varmap_set(Node, Vars) ->
Node#node{varmap = Vars}.
node_varmap_lookup(#node{varmap = Varmap}, Var) ->
case lists:keyfind(Var, 1, Varmap) of
{_, NewVar} -> NewVar;
false -> Var
end.
node_create(Label, Pred, Succ) ->
#node{label = Label, pred = Pred, succ = Succ}.
%%-----------------------------------------------------------------------------
%% nodes - describes the new temporary CFG
%%
%% domtree - the dominator tree of the original CFG
%% labels - the labels of the original CFG, filtered to only contain non fail trace paths
%% postorder - the postorder walk of labels of the original CFG, filtered to only contain non fail trace paths
%% rev_postorder - reverse of postorder.
%% start_label - the start basic block label.
%% all_expr - all expression value numbers that the CFG defines
%% tree - the tree of nodes, with labels as keys and node records as values
-record(nodes, {
domtree = none :: 'none' | hipe_dominators:domTree(),
labels = none :: 'none' | [icode_lbl()],
postorder = none :: 'none' | [icode_lbl()],
start_label = none :: 'none' | icode_lbl(),
rev_postorder = none :: 'none' | [icode_lbl()],
all_expr = none :: 'none' | [non_neg_integer()],
tree = gb_trees:empty() :: gb_trees:tree()}).
nodes_postorder(#nodes{postorder = Out}) -> Out.
nodes_rev_postorder(#nodes{rev_postorder = Out}) -> Out.
nodes_tree(#nodes{tree = Out}) -> Out.
nodes_domtree(#nodes{domtree = Out}) -> Out.
nodes_start_label(#nodes{start_label = Out}) -> Out.
nodes_tree_is_empty(#nodes{tree = Tree}) ->
gb_trees:is_empty(Tree).
nodes_tree_set(Tree, Nodes) -> Nodes#nodes{tree = Tree}.
nodes_all_expr_set(AllExpr, Nodes) -> Nodes#nodes{all_expr = AllExpr}.
nodes_tree_values(Nodes) ->
gb_trees:values(nodes_tree(Nodes)).
get_node(Label, Nodes) ->
gb_trees:get(Label, nodes_tree(Nodes)).
enter_node(Node, Nodes) ->
nodes_tree_set(gb_trees:enter(node_label(Node), Node, nodes_tree(Nodes)), Nodes).
remove_node(Node, Nodes) ->
nodes_tree_set(gb_trees:delete(node_label(Node), nodes_tree(Nodes)), Nodes).
nodes_create() -> #nodes{}.
%%-----------------------------------------------------------------------------
%% update
%% record used when updating the CFG, keeping track of which expressions
%% have been inserted and their mappings to variable names.
%%
%% inserted - maps an expression to a list of variables
%% del_red_test - flag that is set to true when the reduction test
%% has been inserted is used to move the reduction test.
-record(update, {inserted = gb_trees:empty() :: gb_trees:tree(),
del_red_test = false :: boolean()}).
update_inserted_lookup(#update{inserted = Inserted}, ExprId) ->
gb_trees:lookup(ExprId, Inserted).
update_inserted_add_new(Update = #update{inserted = Inserted}, ExprId, Defs) ->
VarList = [case hipe_icode:is_var(Def) of
true -> hipe_icode:mk_new_var();
false ->
case hipe_icode:is_reg(Def) of
true -> hipe_icode:mk_new_reg();
false ->
true = hipe_icode:is_fvar(Def),
hipe_icode:mk_new_fvar()
end
end || Def <- Defs],
NewInserted = gb_trees:enter(ExprId, VarList, Inserted),
{Update#update{inserted = NewInserted}, VarList}.
update_inserted_add(Update = #update{inserted = Inserted}, ExprId, Defs) ->
Update#update{inserted = gb_trees:enter(ExprId, Defs, Inserted)}.
update_del_red_test(#update{del_red_test = DelRed}) -> DelRed.
update_del_red_test_set(Update) ->
Update#update{del_red_test = true}.
%%-----------------------------------------------------------------------------
%% CODE AREA
%%-----------------------------------------------------------------------------
%% Main function called from the hipe_main module
-spec struct_reuse(cfg()) -> cfg().
struct_reuse(CFG) ->
%% debug_init_case_count(?SR_INSTR_TYPE),
%% debug_init_case_count(?SR_STRUCT_INSTR_TYPE),
%% debug_function({wings_ask,ask_unzip,3}, CFG),
%% debug_function(nil, CFG),
%% set_debug_flag(true),
%% debug_struct("CFG In: ", CFG),
%% debug_cfg_pp(CFG),
init_expr_id(),
Nodes = construct_nodes(CFG),
case nodes_tree_is_empty(Nodes) of
false ->
Maps = create_maps(Nodes),
Nodes3 = init_nodes(Nodes, Maps),
Nodes4 = calc_anticipated(Nodes3),
{Nodes5, Maps3} = calc_inserts(Nodes4, Maps),
Nodes6 = update_nodes_inserts(Nodes5, Maps3),
%% debug_list("ExprMap: ", gb_trees:to_list(Maps3#maps.expr)),
%% debug_list("VarMap: ", gb_trees:to_list(maps_var(Maps3))),
%% debug_nodes(Nodes6),
%% update the cfg
CFG1 = rewrite_cfg(CFG, Nodes6, Maps3),
CFG2 = hipe_icode_ssa:remove_dead_code(CFG1),
CFGOut = hipe_icode_ssa_copy_prop:cfg(CFG2),
%% CFGOut = CFG1,
%% print_struct("CFG: ", CFG),
%% debug_cfg_pp(CFG),
%% debug_cfg_pp(CFGOut),
%% debug_print_case_count(?SR_STRUCT_INSTR_TYPE),
%% debug_print_case_count(?SR_INSTR_TYPE),
%% debug("Done~n"),
%% debug_struct("CFG Out: ", CFGOut),
CFGOut;
true ->
CFG
end.
%%-----------------------------------------------------------------------------
%% Calculate simplified CFG with all fail paths removed
construct_nodes(CFG) ->
%% all important dominator tree
DomTree = hipe_dominators:domTree_create(CFG),
%% construct initial nodes
{Nodes, NonFailSet} = nodes_from_cfg(CFG, DomTree),
%% remove nodes on fail paths
NewNodes = prune_nodes(Nodes, NonFailSet),
%% fill in misc node tree info
Postorder = [Label || Label <- hipe_icode_cfg:postorder(CFG),
gb_sets:is_member(Label, NonFailSet)],
%% check postorder is valid
PostOrderTmp = hipe_icode_cfg:postorder(CFG),
LabelsTmp = hipe_icode_cfg:labels(CFG),
case length(PostOrderTmp) =/= length(LabelsTmp) of
true ->
print("Warning, Postorder and Labels differ!~n"),
print_struct("Postorder: ", PostOrderTmp),
print_struct("Labels: ", LabelsTmp);
false ->
done
end,
RevPostorder = lists:reverse(Postorder),
StartLabel = hipe_icode_cfg:start_label(CFG),
NewTree = gb_trees:balance(nodes_tree(NewNodes)),
NewNodes#nodes{postorder = Postorder,
rev_postorder = RevPostorder,
start_label = StartLabel,
tree = NewTree,
domtree = DomTree}.
%%-----------------------------------------------------------------------------
%% Constructs a tree of nodes, one node for each basic block in CFG
nodes_from_cfg(CFG, DomTree) ->
lists:foldl(fun(Label, {NodesAcc, NonFailAcc}) ->
Code = hipe_bb:code(hipe_icode_cfg:bb(CFG, Label)),
Pred = hipe_icode_cfg:pred(CFG, Label),
Succ = hipe_icode_cfg:succ(CFG, Label),
%% debug_struct("Label: ", Label),
%% debug_struct("Code: ", Code),
%% Find all structures and phi functions.
%% Find all defines in this bb that are not from structures
%% and add them to NonStructDefs, later to be used for calculating upwards
%% exposed expressions, and killed expressions.
%% Also find all non fail blocks, ie backtrace from return blocks,
%% and add them to NewNonFailAcc
Node = node_create(Label, Pred, Succ),
{NewNode, NewNonFailAcc, PreLoopPreds} =
lists:foldl(fun(Instr, {NodeAcc, NFAcc, PLPAcc}) ->
case instr_type(Instr) of
struct ->
{node_code_add(NodeAcc, Instr), NFAcc, PLPAcc};
return ->
{NodeAcc, get_back_trace_rec(CFG, Label, NFAcc), PLPAcc};
{struct_elems, NumElem, DstVar, SrcVar} ->
NewNodeAcc = node_struct_elems_add(NodeAcc, {DstVar, NumElem, SrcVar}),
{node_non_struct_instr_add(NewNodeAcc, Instr), NFAcc, PLPAcc};
{struct_type, NumElems, Var, Type} ->
{node_struct_type_add(NodeAcc, {Type, Var, NumElems}), NFAcc, PLPAcc};
{tuple_arity, Var, Cases} ->
NewNodeAcc =
lists:foldl(fun(Case, NAcc) ->
case Case of
{{const, {flat, Arity}}, _} ->
Tuple = {?MKTUPLE, Var, Arity},
node_struct_type_add(NAcc, Tuple);
_ -> NAcc
end
end, NodeAcc, Cases),
{NewNodeAcc, NFAcc, PLPAcc};
%% {atom_type, Atom, Var} ->
%% {node_atom_type_add(NodeAcc, {Var, Atom}), NFAcc, PLPAcc};
phi ->
Def = hipe_icode:phi_dst(Instr),
Part = lists:foldl(fun(P = {Pr, PredVar}, {IsDef, NotDom}) ->
case hipe_dominators:domTree_dominates(Label, Pr, DomTree) of
false ->
{IsDef, [P | NotDom]};
true ->
{IsDef andalso PredVar =:= Def, NotDom}
end
end, {true, []}, hipe_icode:phi_arglist(Instr)),
case Part of
{true, [{P, V}]} ->
%% This is the only case recognized so far. All phi
%% sub block references a static variable that is
%% assigned the same value again in the phi function.
{node_phi_add(NodeAcc, P, {Def, V}),
NFAcc, ?SETS:add_element(P, PLPAcc)};
{false, [{P, _}]} ->
{node_non_struct_instr_add(NodeAcc, Instr),
NFAcc, ?SETS:add_element(P, PLPAcc)};
_ ->
{node_non_struct_instr_add(NodeAcc, Instr), NFAcc, PLPAcc}
end;
_ ->
{node_non_struct_instr_add(NodeAcc, Instr), NFAcc, PLPAcc}
end
end, {Node, NonFailAcc, ?SETS:new()}, Code),
%% insert the new node
NewNodesAcc = enter_node(node_code_rev(NewNode), NodesAcc),
%% Set the pre loop flag of all nodes that are predecessor to this node
%% and that are the first nodes prior to a loop.
NewNodesAcc2 =
lists:foldl(fun(Lbl, NsAcc) ->
PredNode = get_node(Lbl, NsAcc),
NewPredNode = node_pre_loop_set(PredNode),
NewPredNode2 = node_varmap_set(NewPredNode, node_phi_get(NewNode, Lbl)),
enter_node(NewPredNode2, NsAcc)
end, NewNodesAcc, PreLoopPreds),
{NewNodesAcc2, NewNonFailAcc}
end, {nodes_create(), gb_sets:new()}, hipe_icode_cfg:reverse_postorder(CFG)).
%%-----------------------------------------------------------------------------
%% Get all labels from Label to root of CFG, ie backtraces from Label.
get_back_trace_rec(CFG, Label, LabelSet) ->
%% debug_struct("Label :", Label),
%% debug_struct("Set :", gb_sets:to_list(LabelSet)),
case gb_sets:is_member(Label, LabelSet) of
false ->
Preds = hipe_icode_cfg:pred(CFG, Label),
lists:foldl(fun(Lbl, SetAcc) ->
get_back_trace_rec(CFG, Lbl, SetAcc)
end, gb_sets:add(Label, LabelSet), Preds);
true -> LabelSet
end.
%%-----------------------------------------------------------------------------
%% Remove all fail block paths and successors and predecessors
%% That are on fail paths
prune_nodes(Nodes, NonFailSet) ->
lists:foldl(fun(Node, NodesAcc) ->
case gb_sets:is_member(node_label(Node), NonFailSet) of
true ->
NewSucc = [L || L <- node_succ(Node), gb_sets:is_member(L, NonFailSet)],
NewPred = [L || L <- node_pred(Node), gb_sets:is_member(L, NonFailSet)],
enter_node(Node#node{succ = NewSucc, pred = NewPred}, NodesAcc);
false ->
remove_node(Node, NodesAcc)
end
end, Nodes, nodes_tree_values(Nodes)).
%%-----------------------------------------------------------------------------
%% Map calculations.
%%-----------------------------------------------------------------------------
%% Create a maps structure from the Nodes record
create_maps(Nodes) ->
Maps = lists:foldl(fun(Label, MapsAcc) ->
Node = get_node(Label, Nodes),
NewMapsAcc = maps_from_node_struct_type(MapsAcc, Node),
NewMapsAcc2 = maps_from_node_struct_elems(NewMapsAcc, Node),
%% NewMapsAcc3 = maps_from_node_atom_type(NewMapsAcc2, Node),
maps_from_node_code(NewMapsAcc2, Node)
end, #maps{}, nodes_rev_postorder(Nodes)),
maps_balance(Maps).
%%-----------------------------------------------------------------------------
%% Add all elements in the struct_type list of Node to Maps as expressions
maps_from_node_struct_type(Maps, Node) ->
%% debug_struct("Node Label: ", node_label(Node)),
%% debug_struct("Node Tuple Type: ", node_struct_type(Node)),
lists:foldl(fun({Type, Var, Size}, MapsAcc) ->
Key = create_elem_expr_key(Size, Var, []),
InstrKey = hipe_icode:mk_primop([], Type, Key),
NewExpr2 = expr_create(InstrKey, [Var]),
NewExpr3 = expr_direct_replace_set(NewExpr2, true),
maps_expr_key_enter(NewExpr3, MapsAcc)
end, Maps, node_struct_type(Node)).
create_elem_expr_key(0, _, Key) -> Key;
create_elem_expr_key(N, Var, Key) ->
create_elem_expr_key(N - 1, Var, [{Var, N} | Key]).
%%-----------------------------------------------------------------------------
%%maps_from_node_atom_type(Maps, Node) ->
%% lists:foldl(fun({Var, Atom}, MapsAcc) ->
%% case maps_var_lookup(Var, MapsAcc) of
%% none ->
%% MapsAcc;
%% {value, #varinfo{elem = none}} ->
%% MapsAcc;
%% {value, #varinfo{elem = {Src, Num, ExprId}}} ->
%% Expr = maps_expr_get(ExprId, MapsAcc),
%% Key = expr_key(Expr),
%%
%% Filter = fun(Arg) ->
%% case Arg of
%% {Src, Num, ExprId} ->
%% hipe_icode:mk_const(Atom);
%% _ ->
%% Arg
%% end end,
%%
%% NewKey = replace_call_variables(Filter, Key),
%% NewExpr = expr_create(NewKey, expr_defs(Expr)),
%% maps_expr_key_enter(NewExpr, MapsAcc)
%% end
%% end, Maps, node_atom_type(Node)).
%%-----------------------------------------------------------------------------
%% Add all struct_elemns in Node to Maps as variables
maps_from_node_struct_elems(Maps, Node) ->
lists:foldl(fun({Dst, Num, Src}, MapsAcc) ->
VarInfo = #varinfo{elem = {Src, Num}},
maps_var_insert(Dst, VarInfo, MapsAcc)
end, Maps, node_struct_elems(Node)).
%%-----------------------------------------------------------------------------
%% Get all expressions defined by the Node and insert them into Maps.
%% Also insert information about all affected variables into Maps.
maps_from_node_code(Maps, Node) ->
%% debug_struct("Node Label: ", Label),
%% debug_struct("Node Code: ", Code),
%% Label = node_label(Node),
lists:foldl(fun(Instr, MapsAcc) ->
%% create two keys that are used to reference this structure creation
%% instruction, so that we can lookup its expression value number
%% later.
InstrKey = hipe_icode:call_dstlist_update(Instr, []),
%% Fetch the two keys from the instruction
{HasElems, RefKey, ElemKey} =
replace_call_vars_elems(MapsAcc, InstrKey),
%% create a new expr record or lookup an existing one.
case HasElems of
true ->
%% The instruction contains uses of variables that are
%% part of another structure.
case maps_instr_lookup(ElemKey, MapsAcc) of
{value, ExprId} ->
%% The instruction is equal to a structure that has
%% already been created. This is the f({Z}) -> {Z}
%% optimization. I.e. there is no need to create {Z} again.
%% Also lookup if ExprId is defining a variable that is
%% already an element in another structure. If so,
%% use that element. This takes care of nested structures
%% such as f({X, {Y, Z}}) -> {X, {Y, Z}}.
#expr{defs = [Var]} = maps_expr_get(ExprId, MapsAcc),
StructElem =
case maps_var_lookup(Var, MapsAcc) of
{value, #varinfo{elem = Elem, exprid = none}} when Elem =/= none ->
Elem;
_ -> none
end,
Defines = hipe_icode:defines(Instr),
maps_varinfos_create(Defines, ExprId, StructElem, MapsAcc);
none ->
%% create a new expression
maps_expr_varinfos_create(Instr, RefKey, MapsAcc)
end;
false ->
%% create a new expression
maps_expr_varinfos_create(Instr, RefKey, MapsAcc)
end
end, Maps, node_code(Node)).
%%-----------------------------------------------------------------------------
%% Creates varinfo structures with exprid set to ExprId for all
%% variables contained in Defines. These are put into MapsIn.
maps_varinfos_create(Defines, ExprId, Elem, MapsIn) ->
VarInfo = #varinfo{exprid = ExprId, elem = Elem},
{MapsOut, _} =
lists:foldl(fun (Def, {Maps, NumAcc}) ->
NewVarInfo = VarInfo#varinfo{ref = {ExprId, NumAcc}},
{maps_var_insert(Def, NewVarInfo, Maps), NumAcc + 1}
end, {MapsIn, 1}, Defines),
MapsOut.
%%-----------------------------------------------------------------------------
%% Creates a new expression from RefKey if RefKey is not already reffering
%% to an expression. Also creates varinfo structures for all variables defined
%% and used by Instr. Result is put in Maps.
maps_expr_varinfos_create(Instr, RefKey, Maps) ->
Defines = hipe_icode:defines(Instr),
{ExprId, Maps2} =
case maps_instr_lookup(RefKey, Maps) of
{value, EId} ->
{EId, Maps};
none ->
NewExpr = expr_create(RefKey, Defines),
{expr_id(NewExpr), maps_expr_key_enter(NewExpr, Maps)}
end,
Maps3 = maps_varinfos_create(Defines, ExprId, none, Maps2),
update_maps_var_use(Instr, ExprId, Maps3).
%%-----------------------------------------------------------------------------
%% A variable replacement function that returns a tuple of three elements
%% {T, K1, K2}, where T indicates if Instr contained variables that where
%% elements of other structures, K1 is the Instr with all variables that
%% references another structure replaced, and K2 is K1 but also with all
%% variables that are elements of other structures replaced.
replace_call_vars_elems(Maps, Instr) ->
VarMap = maps_var(Maps),
{HasElems, Vars, Elems} =
lists:foldr(fun(Arg, {HasElems, Vars, Elems}) ->
case hipe_icode:is_const(Arg) of
false ->
case gb_trees:lookup(Arg, VarMap) of
none ->
{HasElems, [Arg | Vars], [Arg | Elems]};
{value, #varinfo{ref = none, elem = none}} ->
{HasElems, [Arg | Vars], [Arg | Elems]};
{value, #varinfo{ref = Ref, elem = none}} ->
{HasElems, [Ref | Vars], [Ref | Elems]};
{value, #varinfo{ref = none, elem = Elem}} ->
{true, [Arg | Vars], [Elem | Elems]};
{value, #varinfo{ref = Ref, elem = Elem}} ->
{true, [Ref | Vars], [Elem | Elems]}
end;
true ->
{HasElems, [Arg | Vars], [Arg | Elems]}
end end, {false, [], []}, hipe_icode:args(Instr)),
{HasElems, hipe_icode:call_args_update(Instr, Vars),
hipe_icode:call_args_update(Instr, Elems)}.
%%-----------------------------------------------------------------------------
%% Updates the usage information of all variables used by Instr to also
%% contain Id and updates Maps to contain the new variable information.
%% Also updates the expressions where the updated variables are used to
%% contain the use information.
update_maps_var_use(Instr, Id, Maps) ->
lists:foldl(fun(Use, MapsAcc) ->
VarInfo = get_varinfo(Use, MapsAcc),
NewVarInfo = varinfo_use_add(VarInfo, Id),
MapsAcc2 = maps_var_enter(Use, NewVarInfo, MapsAcc),
case varinfo_exprid(VarInfo) of
none ->
MapsAcc2;
VarExprId ->
Expr = maps_expr_get(VarExprId, MapsAcc2),
NewExpr = expr_use_add(Expr, Id),
maps_expr_enter(NewExpr, MapsAcc2)
end
end, Maps, hipe_icode:uses(Instr)).
%%-----------------------------------------------------------------------------
%% Looks up an old variable info or creates a new one if none is found.
get_varinfo(Var, Maps) ->
case maps_var_lookup(Var, Maps) of
{value, Info} ->
Info;
none ->
#varinfo{}
end.
%%-----------------------------------------------------------------------------
%% filters all arguments to a function call Instr that are not constants
%% through the Filter function, and replaces the arguments in Instr with
%% the result.
replace_call_variables(Filter, Instr) ->
NewArgs = [case hipe_icode:is_const(Arg) of
false -> Filter(Arg);
true -> Arg
end || Arg <- hipe_icode:args(Instr)],
hipe_icode:call_args_update(Instr, NewArgs).
%%-----------------------------------------------------------------------------
%% Init nodes from node local expression information
init_nodes(Nodes, Maps) ->
AllExpr = maps_expr_keys(Maps),
lists:foldl(fun(Node, NodesAcc) ->
UEExpr = calc_up_exposed_expr(maps_var(Maps), Node),
%% print_list("Up ExprSet: ", ?SETS:to_list(UEExpr)),
KilledExpr = calc_killed_expr(Node, Maps),
%% print_list("Killed: ", ?SETS:to_list(KilledExpr)),
%% End nodes have no anticipated out
AnticOut =
case node_succ(Node) of
[] ->
?SETS:new();
_ ->
AllExpr
end,
enter_node(Node#node{up_expr = UEExpr,
killed_expr = KilledExpr,
antic_out = AnticOut}, NodesAcc)
end, nodes_all_expr_set(AllExpr, Nodes), nodes_tree_values(Nodes)).
%%-----------------------------------------------------------------------------
%% Calculate the upwards exposed expressions for a node.
calc_up_exposed_expr(VarMap, Node) ->
%% debug_struct("UpExpr label: ", node_label(Node)),
NonStructDefs = node_non_struct_defs(Node),
{_, ExprIdSet} =
lists:foldl(fun(Instr, {NotToUseAcc, ExprIdAcc}) ->
Defs = hipe_icode:defines(Instr),
Uses = hipe_icode:uses(Instr),
IsNotToUse =
lists:any(fun(Use) -> gb_sets:is_member(Use, NotToUseAcc) end, Uses),
case IsNotToUse of
false ->
NewExprIdAcc =
lists:foldl(fun(Def, Acc) ->
#varinfo{exprid = Id} = gb_trees:get(Def, VarMap),
?SETS:add_element(Id, Acc) end, ExprIdAcc, Defs),
{NotToUseAcc, NewExprIdAcc};
true ->
NewNotToUse =
gb_sets:union(gb_sets:from_list(Defs), NotToUseAcc),
{NewNotToUse, ExprIdAcc}
end
end, {NonStructDefs, ?SETS:new()}, node_code(Node)),
ExprIdSet.
%%-----------------------------------------------------------------------------
%% Calculate killed expression for node
calc_killed_expr(Node, Maps) ->
calc_killed_expr_defs(node_non_struct_defs_list(Node), ?SETS:new(), Maps).
calc_killed_expr_defs(Defs, UseSet, Maps) ->
lists:foldl(fun(Def, Acc) ->
case maps_var_lookup(Def, Maps) of
none ->
Acc;
{value, #varinfo{use = Use}} ->
?SETS:union(Acc, calc_killed_expr_use(Use, Maps))
end
end, UseSet, Defs).
calc_killed_expr_use(ExprIds, Maps) ->
?SETS:fold(fun(Id, Acc) ->
Expr = maps_expr_get(Id, Maps),
?SETS:union(Acc, calc_killed_expr_use(expr_use(Expr), Maps))
end, ExprIds, ExprIds).
%%-----------------------------------------------------------------------------
%% Calculate the anticipated in and anticipated out sets for each node
calc_anticipated(NodesIn) ->
calc_anticipated_rec(NodesIn, nodes_postorder(NodesIn)).
calc_anticipated_rec(NodesIn, []) -> NodesIn;
calc_anticipated_rec(NodesIn, WorkIn) ->
{NodesOut, WorkOut} =
lists:foldl(fun(Label, {NodesAcc, WorkAcc}) ->
Node = get_node(Label, NodesAcc),
%debug_struct("~nNode Label: ", Label),
AnticIn = ?SETS:union(node_up_expr(Node),
?SETS:subtract(node_antic_out(Node), node_killed_expr(Node))),
%debug_struct("AnticIn: ", AnticIn),
case (node_antic_in(Node) =:= AnticIn) of
false ->
NewNodes1 = enter_node(Node#node{antic_in = AnticIn}, NodesAcc),
Preds = node_pred(Node),
%debug_struct("Preds: ", Preds),
NewNodes2 =
lists:foldl(fun(Label2, NodesAcc2) ->
PredNode = get_node(Label2, NodesAcc2),
AnticOut = ?SETS:intersection(AnticIn, node_antic_out(PredNode)),
%debug_struct("Pred Node Label: ", Label2),
%debug_struct("Pred AnticOut: ", AnticOut),
enter_node(PredNode#node{antic_out = AnticOut}, NodesAcc2)
end, NewNodes1, Preds),
NewWork = add_work_list(Preds, WorkAcc),
%debug_struct("New Work: ", NewWork),
{NewNodes2, NewWork};
true ->
{NodesAcc, WorkAcc}
end
end, {NodesIn, new_work()}, WorkIn),
calc_anticipated_rec(NodesOut, get_work_list(WorkOut)).
%%-----------------------------------------------------------------------------
%% Function that adds inserts to expressions from nodes which either
%% have an upwards exposed expression or dominate more than one node
%% that inserts the same expression or the node is a prior to loop
%% node. The inserted info is stored in the #expr records in the expr
%% map of the #maps structure.
calc_inserts(NodesIn, MapsIn) ->
DomTree = nodes_domtree(NodesIn),
lists:foldl(fun(Label, {NodesAcc, MapsAcc}) ->
Node = get_node(Label, NodesAcc),
%% get some basic properties.
UpExpr = node_up_expr(Node),
AnticOut = node_antic_out(Node),
SubIns = node_sub_inserts(Node),
%% debug_struct("Label: ", Label),
{HasIns, NewMapsAcc} =
?SETS:fold(fun(ExprId, {HasInsAcc, MapsAcc2}) ->
Expr = maps_expr_get(ExprId, MapsAcc2),
ExprIns = expr_inserts(Expr),
ExprSubIns = ?SETS:intersection(ExprIns, SubIns),
%% There are three cases when to insert an expression
%% 1. The expression is defined at least twice in the subtree of this
%% node, that is length(ExprSubIns) > 1.
%% 2. It is defined in the node and is upwards exposed.
%% 3. The node is a block just above a loop, so we should move
%% all anticipated expressions to the node.
case length(ExprSubIns) > 1 orelse ?SETS:is_element(ExprId, UpExpr)
orelse node_pre_loop(Node) of
true ->
%% get labels of all sub blocks that inserts the expression and
%% that are dominated by the current node.
Dominates =
?SETS:filter(fun(SubLabel) ->
hipe_dominators:domTree_dominates(Label, SubLabel, DomTree)
end, ExprSubIns),
%% remove inserts labels from insert labelset.
NewIns = ?SETS:subtract(ExprIns, Dominates),
NewIns2 = ?SETS:add_element(Label, NewIns),
%% update the node.
NewMaps =
maps_expr_enter(expr_inserts_set(Expr, NewIns2), MapsAcc2),
{true, NewMaps};
false ->
{HasInsAcc, MapsAcc2}
end
end, {false, MapsAcc}, ?SETS:union(AnticOut, UpExpr)),
%% Check if there was an insert into this node,
%% and if so add to the sub inserts set.
NewSubIns =
case HasIns of
true ->
?SETS:add_element(Label, SubIns);
false ->
SubIns
end,
%% update sub inserts for all predecessors to the node.
NewNodes2 =
lists:foldl(fun(PredLabel, NodesAcc2) ->
PredNode = get_node(PredLabel, NodesAcc2),
enter_node(node_union_sub_inserts(PredNode, NewSubIns), NodesAcc2)
end, NodesAcc, node_pred(Node)),
{NewNodes2, NewMapsAcc}
end, {NodesIn, MapsIn}, nodes_postorder(NodesIn)).
%%-----------------------------------------------------------------------------
%% Update the insert sets of each node in the node tree.
%% That is, move the insert information from the expressions to
%% the actual nodes that perform the inserts.
update_nodes_inserts(Nodes, Maps) ->
lists:foldl(fun(Expr, NodesAcc) ->
ExprId = expr_id(Expr),
?SETS:fold(fun(Label, NsAcc) ->
Nd = get_node(Label, NsAcc),
enter_node(node_add_insert(Nd, ExprId), NsAcc)
end, NodesAcc, expr_inserts(Expr))
end, Nodes, maps_expr_values(Maps)).
%%-----------------------------------------------------------------------------
%% Rewrite CFG functions
%%-----------------------------------------------------------------------------
%% Do the code updating from the info in the nodes and maps structures. This
%% is a proxy function for rewrite_cfg/6
rewrite_cfg(CFG, Nodes, Maps) ->
{NewCFG, _Visited} =
rewrite_cfg(CFG, ?SETS:new(), #update{}, Nodes, Maps, [nodes_start_label(Nodes)]),
%% debug_struct("Visited: ", _Visited),
NewCFG.
%%-----------------------------------------------------------------------------
%% rewrite_cfg
%% traverse the CFG in reverse postorder and rewrite each basic block before
%% rewriteing its children. Pass along to each BB update the mappings of
%% inserted expressions in the Update record.
rewrite_cfg(CFG, Visited, Update, Nodes, Maps, Labels) ->
lists:foldl(fun(Label, {CFGAcc, VisitedAcc}) ->
case ?SETS:is_element(Label, VisitedAcc) of
false ->
%% debug_struct("Visit: ", Label),
Node = get_node(Label, Nodes),
NewVisitedAcc = ?SETS:add_element(Label, VisitedAcc),
{NewCFGAcc, NewUpdate} = rewrite_bb(CFGAcc, Update, Maps, Node),
%% debug_struct("Update inserted: ", update_inserted_list(NewUpdate)),
rewrite_cfg(NewCFGAcc, NewVisitedAcc, NewUpdate, Nodes, Maps, node_succ(Node));
true ->
{CFGAcc, VisitedAcc}
end
end, {CFG, Visited}, Labels).
%%-----------------------------------------------------------------------------
%% rewrite one single basic block in the CFG as described by the properties
%% in the Node for that block. Uses the Maps and Update info to lookup
%% the instructions and expressions to insert or delete.
rewrite_bb(CFG, Update, Maps, Node) ->
#node{pre_loop = PreLoop, label = Label, up_expr = UpExpr, inserts = Inserts} = Node,
Code = hipe_bb:code(hipe_icode_cfg:bb(CFG, Label)),
%debug_struct("RW Label: ", Label),
%debug_struct("Inserts", Inserts),
DelRed = update_del_red_test(Update),
Delete = ?SETS:subtract(UpExpr, Inserts),
%% local function that gets the instruction and defines list of an
%% expression id in the current node and and returns them.
GetInstrFunc = fun(Expr) ->
Instr = expr_key(Expr),
Defs = expr_defs(Expr),
NewInstr =
if
PreLoop ->
replace_call_variables(fun(Var) ->
node_varmap_lookup(Node,
Var)
end,
Instr);
true ->
Instr
end,
{NewInstr, Defs}
end,
%% go through all expressions defined by the node and replace
%% or remove them as indicated by the delete set. Also perform
%% reduction test replacement if neccessary.
{[CodeLast | CodeRest], NewUpdate, LocalAcc} =
lists:foldl(fun(Instr, {CodeAcc, UpdateAcc, LocalAcc}) ->
case struct_instr_type(Instr) of
struct ->
Defs = hipe_icode:defines(Instr),
#varinfo{exprid = ExprId} = maps_var_get(hd(Defs), Maps),
Expr = maps_expr_get(ExprId, Maps),
DirectReplace = expr_direct_replace(Expr),
%% Creates move intstructions from Vars to Defs
RemoveFuncVars = fun(Vars) ->
CodeAcc2 = mk_defs_moves(CodeAcc, Defs, Vars),
{CodeAcc2, UpdateAcc, LocalAcc} end,
%% Looks up an already inserted ExprId and makes moves
%% of variables from that expression to this expression.
RemoveFunc = fun() ->
{value, Vars} = update_inserted_lookup(UpdateAcc, ExprId),
RemoveFuncVars(Vars) end,
%% Is ExprId already inserted?
IsLocal = ?SETS:is_element(ExprId, LocalAcc),
case DirectReplace of
true ->
%% The Instr is reffering to an expression that is
%% defined as an identical already present instruction,
%% and can be removed directly.
RemoveFuncVars(expr_defs(Expr));
false when IsLocal ->
%% The instruction has already been inserted.
RemoveFunc();
_ ->
case ?SETS:is_element(ExprId, Delete) of
true ->
%% should not be inserted
RemoveFunc();
_ ->
%% Should remain
UpdateAcc2 = update_inserted_add(UpdateAcc, ExprId, Defs),
LocalAcc2 = ?SETS:add_element(ExprId, LocalAcc),
{[Instr | CodeAcc], UpdateAcc2, LocalAcc2}
end
end;
redtest when DelRed ->
%% delete reduction test
{CodeAcc, UpdateAcc, LocalAcc};
_ ->
{[Instr | CodeAcc], UpdateAcc, LocalAcc}
end
end, {[], Update, ?SETS:new()}, Code),
%debug_struct("RW Label 2: ", Label),
%% calculate the inserts that are new to this node, that is
%% the expressions that are in Inserts but not in UpExpr,
%% and that have not been added already,
%% that is not present in LocalAcc
NewInserts = ?SETS:subtract(?SETS:subtract(Inserts, UpExpr), LocalAcc),
{NewCodeRest, NewUpdate2} =
?SETS:fold(fun(ExprId, {CodeAcc, UpdateAcc}) ->
Expr = maps_expr_get(ExprId, Maps),
{ExprInstr, Defs} = GetInstrFunc(Expr),
{UpdateAcc2, NewDefs} = update_inserted_add_new(UpdateAcc, ExprId, Defs),
%% check if there exists an identical expression, so that
%% this expression can be replaced directly.
CodeAcc2 =
case expr_direct_replace(Expr) of
false ->
NewInstr = rewrite_expr(UpdateAcc2, ExprInstr, NewDefs),
[NewInstr | CodeAcc];
true ->
mk_defs_moves(CodeAcc, NewDefs, Defs)
end,
{CodeAcc2, UpdateAcc2}
end, {CodeRest, NewUpdate}, NewInserts),
NewCode = lists:reverse([CodeLast | NewCodeRest]),
%% Check if we are to insert new reduction test here...
{NewCode2, NewUpdate3} =
case PreLoop andalso ?SETS:size(Inserts) > 0 andalso not DelRed of
true ->
{[hipe_icode:mk_primop([], redtest, []) | NewCode], update_del_red_test_set(NewUpdate2)};
false ->
{NewCode, NewUpdate2}
end,
NewBB = hipe_bb:mk_bb(NewCode2),
NewCFG = hipe_icode_cfg:bb_add(CFG, Label, NewBB),
{NewCFG, NewUpdate3}.
%%-----------------------------------------------------------------------------
%% Create a new structure instruction from Instr with destination Defs
%% from the insert mapping in Update.
rewrite_expr(Update, Instr, Defs) ->
NewInstr =
replace_call_variables(fun(Ref) ->
case Ref of
{ExprId, Num} when is_integer(ExprId) ->
{value, DefList} = update_inserted_lookup(Update, ExprId),
lists:nth(Num, DefList);
_ -> Ref
end end, Instr),
hipe_icode:call_dstlist_update(NewInstr, Defs).
%%-----------------------------------------------------------------------------
%% Make move instructions from Defs list to all variables in
%% the Refs list and insert into Code.
mk_defs_moves(Code, [], []) -> Code;
mk_defs_moves(Code, [Ref | Refs], [Def | Defs]) ->
mk_defs_moves([hipe_icode:mk_move(Ref, Def) | Code], Refs, Defs).
%%-----------------------------------------------------------------------------
%% Utilities
new_work() ->
{[], gb_sets:new()}.
add_work_list(List, Work) ->
lists:foldl(fun(Label, WorkAcc) ->
add_work_label(Label, WorkAcc) end, Work, List).
add_work_label(Label, {List, Set}) ->
case gb_sets:is_member(Label, Set) of
false ->
{[Label | List], gb_sets:add(Label, Set)};
true ->
{List, Set}
end.
get_work_list({List, _}) ->
lists:reverse(List).
%%-----------------------------------------------------------------------------
%% instr_type
%% gets a tag for the type of instruction that is passed in I
struct_instr_type(I) ->
case I of
#icode_call{type = primop, 'fun' = mktuple} ->
%%debug_count_case(?SR_STRUCT_INSTR_TYPE, #call{type = primop, 'fun' = mktuple}),
struct;
#icode_call{type = primop, 'fun' = cons} ->
%%debug_count_case(?SR_STRUCT_INSTR_TYPE, #call{type = primop, 'fun' = cons}),
struct;
#icode_call{type = primop, 'fun' = redtest} ->
%%debug_count_case(?SR_STRUCT_INSTR_TYPE, #call{type = primop, 'fun' = redtest}),
redtest;
_ ->
%%debug_count_case(?SR_STRUCT_INSTR_TYPE, other),
other
end.
instr_type(I) ->
case I of
%#call{type = primop, dstlist = List} when length(List) >= 1 -> struct;
#icode_call{type = primop, 'fun' = {unsafe_element, Elem}, dstlist = [DstVar], args = [SrcVar]} ->
%%debug_count_case(?SR_INSTR_TYPE, #call{type = primop, 'fun' = {unsafe_element, num}}),
{struct_elems, Elem, DstVar, SrcVar};
#icode_phi{} ->
%%debug_count_case(?SR_INSTR_TYPE,#phi{}),
phi;
#icode_enter{} ->
%%debug_count_case(?SR_INSTR_TYPE,#enter{}),
return;
#icode_return{} ->
%%debug_count_case(?SR_INSTR_TYPE,#return{}),
return;
#icode_call{type = primop, 'fun' = mktuple} ->
%%debug_count_case(?SR_INSTR_TYPE, #call{type = primop, 'fun' = mktuple}),
struct;
#icode_call{type = primop, 'fun' = cons} ->
%%debug_count_case(?SR_INSTR_TYPE, #call{type = primop, 'fun' = cons}),
struct;
#icode_call{type = primop, 'fun' = redtest} ->
%%debug_count_case(?SR_INSTR_TYPE, #call{type = primop, 'fun' = redtest}),
redtest;
#icode_type{test = {tuple, Size}, args = [Var]} ->
%%debug_count_case(?SR_INSTR_TYPE, #type{type = {tuple, size}}),
{struct_type, Size, Var, ?MKTUPLE};
#icode_type{test = cons, args = [Var]} ->
%%debug_count_case(?SR_INSTR_TYPE,#type{type = cons}),
{struct_type, 2, Var, ?CONS};
%#type{type = {atom, Atom}, args = [Var]} -> {atom_type, Atom, Var};
#icode_call{type = primop, 'fun' = unsafe_hd,
dstlist = [DstVar], args = [SrcVar]} ->
%%debug_count_case(?SR_INSTR_TYPE,#call{type = primop, 'fun' = unsafe_hd}),
{struct_elems, 1, DstVar, SrcVar};
#icode_call{type = primop, 'fun' = unsafe_tl,
dstlist = [DstVar], args = [SrcVar]} ->
%%debug_count_case(?SR_INSTR_TYPE, #call{type = primop, 'fun' = unsafe_tl}),
{struct_elems, 2, DstVar, SrcVar};
#icode_switch_tuple_arity{term = Var, cases = Cases} ->
%%debug_count_case(?SR_INSTR_TYPE,#switch_tuple_arity{}),
{tuple_arity, Var, Cases};
_ -> other
end.
%%-----------------------------------------------------------------------------
%% Expression ID counter
init_expr_id() ->
put({struct_reuse, expr_id_count}, 0).
-spec new_expr_id() -> non_neg_integer().
new_expr_id() ->
V = get({struct_reuse, expr_id_count}),
put({struct_reuse, expr_id_count}, V+1),
V.
%%-----------------------------------------------------------------------------
%% Debug and print functions
print_struct(String, Struct) ->
io:format(String),
erlang:display(Struct).
print(String) ->
io:format(String).
-ifdef(DEBUG).
debug_count_case(Type, Case) ->
Cases = get(Type),
NewCases =
case gb_trees:lookup(Case, Cases) of
{value, Value} -> gb_trees:enter(Case, Value + 1, Cases);
none -> gb_trees:insert(Case, 1, Cases)
end,
put(Type, NewCases).
debug_init_case_count(Type) ->
case get(Type) of
undefined -> put(Type, gb_trees:empty());
_ -> ok
end.
debug_print_case_count(Type) ->
Cases = get(Type),
debug_struct("Case type: ", Type),
debug_list("Cases: ", gb_trees:to_list(Cases)).
set_debug_flag(Value) ->
put({struct_reuse, debug}, Value).
get_debug_flag() -> get({struct_reuse, debug}).
debug_function(FuncName, CFG) ->
Linear = hipe_icode_cfg:cfg_to_linear(CFG),
Func = hipe_icode:icode_fun(Linear),
case Func =:= FuncName orelse FuncName =:= nil of
true ->
set_debug_flag(true),
%% debug_struct("Code: ", hipe_icode_cfg:bb(CFG, 15)),
debug_struct("~nFunction name :", Func);
false ->
set_debug_flag(undefined)
end.
debug_cfg_pp(CFG) ->
case get_debug_flag() of
true -> hipe_icode_cfg:pp(CFG);
_ -> none
end.
debug_struct(String, Struct) ->
case get_debug_flag() of
true ->
io:format(String),
erlang:display(Struct);
_ -> none
end.
debug(String) ->
case get_debug_flag() of
true -> io:format(String);
_ -> none
end.
debug_list(String, List) ->
case get_debug_flag() of
true -> print_list(String, List);
_ -> none
end.
print_list(String, List) ->
io:format(String),
io:format("~n"),
print_list_rec(List),
io:format("~n").
print_list_rec([]) -> ok;
print_list_rec([Struct | List]) ->
erlang:display(Struct),
print_list_rec(List).
debug_nodes(Nodes) ->
lists:foreach(fun(Node) -> debug_node(Node) end, nodes_tree_values(Nodes)).
debug_node(Node) ->
case get_debug_flag() of
true ->
print_struct("Node Label: ", Node#node.label),
print_struct("Code: ", Node#node.code),
print_struct("Phi: ", Node#node.phi),
print_struct("PreLoop: ", Node#node.pre_loop),
print_struct("Preds: ", Node#node.pred),
print_struct("Succ: ", Node#node.succ),
print_struct("Up Expr: ", Node#node.up_expr),
print_struct("Kill : ", Node#node.killed_expr),
print_struct("AnticIn: ", Node#node.antic_in),
print_struct("AnticOut: ", Node#node.antic_out),
print_struct("SubInserts: ", Node#node.sub_inserts),
print_struct("Inserts: ", Node#node.inserts),
print_struct("NonStructDefs: ", Node#node.non_struct_defs),
print_struct("Params: ", Node#node.struct_type),
print_struct("Elems: ", Node#node.struct_elems),
io:format("~n");
_ -> none
end.
-endif.
