diff options
Diffstat (limited to 'lib/hipe/flow')
| -rw-r--r-- | lib/hipe/flow/Makefile | 105 | ||||
| -rw-r--r-- | lib/hipe/flow/cfg.hrl | 53 | ||||
| -rw-r--r-- | lib/hipe/flow/cfg.inc | 949 | ||||
| -rw-r--r-- | lib/hipe/flow/ebb.inc | 247 | ||||
| -rw-r--r-- | lib/hipe/flow/hipe_bb.erl | 81 | ||||
| -rw-r--r-- | lib/hipe/flow/hipe_bb.hrl | 30 | ||||
| -rw-r--r-- | lib/hipe/flow/hipe_dominators.erl | 715 | ||||
| -rw-r--r-- | lib/hipe/flow/hipe_gen_cfg.erl | 37 | ||||
| -rw-r--r-- | lib/hipe/flow/liveness.inc | 332 |
9 files changed, 2549 insertions, 0 deletions
diff --git a/lib/hipe/flow/Makefile b/lib/hipe/flow/Makefile new file mode 100644 index 0000000000..5b9d0b7582 --- /dev/null +++ b/lib/hipe/flow/Makefile @@ -0,0 +1,105 @@ +# +# %CopyrightBegin% +# +# Copyright Ericsson AB 2001-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% +# + +ifndef EBIN +EBIN = ../ebin +endif + +ifndef DOCS +DOCS = ../doc +endif + +include $(ERL_TOP)/make/target.mk +include $(ERL_TOP)/make/$(TARGET)/otp.mk + +# ---------------------------------------------------- +# Application version +# ---------------------------------------------------- +include ../vsn.mk +VSN=$(HIPE_VSN) + +# ---------------------------------------------------- +# Release directory specification +# ---------------------------------------------------- +RELSYSDIR = $(RELEASE_PATH)/lib/hipe-$(VSN) + +# ---------------------------------------------------- +# Target Specs +# ---------------------------------------------------- +MODULES = hipe_bb hipe_dominators hipe_gen_cfg + + +HRL_FILES= +INC_FILES= cfg.inc ebb.inc liveness.inc +ERL_FILES= $(MODULES:%=%.erl) +TARGET_FILES= $(MODULES:%=$(EBIN)/%.$(EMULATOR)) +DOC_FILES= $(MODULES:%=$(DOCS)/%.html) + +# APP_FILE= +# APP_SRC= $(APP_FILE).src +# APP_TARGET= $(EBIN)/$(APP_FILE) +# +# APPUP_FILE= +# APPUP_SRC= $(APPUP_FILE).src +# APPUP_TARGET= $(EBIN)/$(APPUP_FILE) + +# ---------------------------------------------------- +# FLAGS +# ---------------------------------------------------- + +include ../native.mk + +ERL_COMPILE_FLAGS += +warn_exported_vars +warn_missing_spec +warn_untyped_record + +# ---------------------------------------------------- +# Targets +# ---------------------------------------------------- + +debug opt: $(TARGET_FILES) + +docs: $(DOC_FILES) + +clean: + rm -f $(TARGET_FILES) + rm -f core + +$(DOCS)/%.html:%.erl + erl -noshell -run edoc_run file '"$<"' '[{dir, "$(DOCS)"}]' -s init stop + +# ---------------------------------------------------- +# Special Build Targets +# ---------------------------------------------------- + + + +# ---------------------------------------------------- +# Release Target +# ---------------------------------------------------- +include $(ERL_TOP)/make/otp_release_targets.mk + +release_spec: opt + $(INSTALL_DIR) $(RELSYSDIR)/flow + $(INSTALL_DATA) $(ERL_FILES) $(HRL_FILES) $(INC_FILES) $(RELSYSDIR)/flow + $(INSTALL_DIR) $(RELSYSDIR)/ebin + $(INSTALL_DATA) $(TARGET_FILES) $(RELSYSDIR)/ebin + +release_docs_spec: + +$(EBIN)/hipe_bb.beam: hipe_bb.hrl +$(EBIN)/hipe_gen_cfg.beam: cfg.hrl cfg.inc ../main/hipe.hrl diff --git a/lib/hipe/flow/cfg.hrl b/lib/hipe/flow/cfg.hrl new file mode 100644 index 0000000000..62f47a707a --- /dev/null +++ b/lib/hipe/flow/cfg.hrl @@ -0,0 +1,53 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2007-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 : cfg.hrl +%% Author : Kostis Sagonas <[email protected]> +%% Purpose : Contains typed record declarations for the CFG data structures +%% +%% $Id$ +%%============================================================================ + +-type cfg_lbl() :: non_neg_integer(). + +%% +%% This is supposed to be local but appears here for the time being +%% just so that it is used below +%% +-record(cfg_info, {'fun' :: mfa(), + start_label :: cfg_lbl(), + is_closure :: boolean(), + closure_arity :: arity(), + is_leaf :: boolean(), + params, % :: list() + info = []}). %% this field seems not needed; take out?? + +%% +%% Data is a triple with a dict of constants, a list of labels and an integer +%% +-type cfg_data() :: {dict(), [cfg_lbl()], non_neg_integer()}. + +%% +%% The following is to be used by other modules +%% +-record(cfg, {table = gb_trees:empty() :: gb_tree(), + info :: #cfg_info{}, + data :: cfg_data()}). +-type cfg() :: #cfg{}. diff --git a/lib/hipe/flow/cfg.inc b/lib/hipe/flow/cfg.inc new file mode 100644 index 0000000000..62f399a81c --- /dev/null +++ b/lib/hipe/flow/cfg.inc @@ -0,0 +1,949 @@ +%% -*- Erlang -*- +%% -*- erlang-indent-level: 2 -*- +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-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% +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% CONTROL FLOW GRAPHS +%% +%% Construct and manipulate the control flow graph of a function (program?). +%% +%% Exports: +%% ~~~~~~~~ +%% init(Code) - makes a CFG out of code. +%% bb(CFG, Label) - returns the basic block named 'Label' from the CFG. +%% bb_add(CFG, Label, NewBB) - makes NewBB the basic block associated +%% with Label. +%% succ(Map, Label) - returns a list of successors of basic block 'Label'. +%% pred(Map, Label) - returns the predecessors of basic block 'Label'. +%% fallthrough(CFG, Label) - returns fall-through successor of basic +%% block 'Label' (or 'none'). +%% conditional(CFG, Label) - returns conditional successor (or 'none') +%% start_label(CFG) - returns the label of the entry basic block. +%% params(CFG) - returns the list of parameters to the CFG. +%% labels(CFG) - returns a list of labels of all basic blocks in the CFG. +%% postorder(CFG) - returns a list of labels in postorder. +%% reverse_postorder(CFG) - returns a list of labels in reverse postorder. +%% cfg_to_linear(CFG) - converts CFG to linearized code. +%% remove_trivial_bbs(CFG) - removes empty BBs or BBs with only a goto. +%% remove_unreachable_code(CFG) - removes unreachable BBs. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% TODO: +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%===================================================================== +%% The following are ugly as hell, but what else can I do??? +%%===================================================================== + +-ifdef(GEN_CFG). +-define(PRED_NEEDED,true). +-endif. + +-ifdef(ICODE_CFG). +-define(CLOSURE_ARITY_NEEDED,true). +-define(INFO_NEEDED,true). +-define(PARAMS_NEEDED,true). +-define(PARAMS_UPDATE_NEEDED,true). +-define(PRED_NEEDED,true). +-define(REMOVE_TRIVIAL_BBS_NEEDED,true). +-define(REMOVE_UNREACHABLE_CODE,true). +-define(START_LABEL_UPDATE_NEEDED,true). +-define(CFG_CAN_HAVE_PHI_NODES,true). +-endif. + +-ifdef(RTL_CFG). +-define(PREORDER,true). +-define(FIND_NEW_LABEL_NEEDED,true). +-define(INFO_NEEDED,true). +-define(PARAMS_NEEDED,true). +-define(PARAMS_UPDATE_NEEDED,true). +-define(PRED_NEEDED,true). +-define(REMOVE_TRIVIAL_BBS_NEEDED,true). +-define(REMOVE_UNREACHABLE_CODE,true). +-define(START_LABEL_UPDATE_NEEDED,true). +-define(CFG_CAN_HAVE_PHI_NODES,true). +-endif. + +-ifdef(SPARC_CFG). +-define(BREADTH_ORDER,true). % for linear scan +-define(PARAMS_NEEDED,true). +-define(START_LABEL_UPDATE_NEEDED,true). +-endif. + +%%===================================================================== + +-ifdef(START_LABEL_UPDATE_NEEDED). +-export([start_label_update/2]). +-endif. + +-ifdef(BREADTH_ORDER). +-export([breadthorder/1]). +-endif. + +-compile(inline). + +%%===================================================================== +%% +%% Interface functions that MUST be implemented in the including file: +%% +%% linear_to_cfg(LinearCode) -> CFG, constructs the cfg. +%% is_label(Instr) -> boolean(), true if instruction is a label. +%% label_name(Instr) -> term(), the name of a label. +%% branch_successors(Instr) -> [term()], the successors of a branch. +%% fails_to(Instr) -> [term()], the fail-successors of an instruction. +%% is_branch(Instr) -> boolean(), true if instruction is a branch. +%% is_comment(Instr) -> boolean(), +%% true if instruction is a comment, used by remove dead code. +%% is_goto(Instr) -> boolean(), +%% true if instruction is a pure goto, used by remove dead code. +%% redirect_jmp(Jmp, ToOld, ToNew) -> NewJmp, +%% redirect_ops(Labels, CFG, Map) -> CFG. +%% Rewrite instructions with labels in operands to use +%% the new label as given by map. +%% Use find_new_label(OldLab,Map) to get the new label. +%% (See hipe_sparc_cfg for example) +%% pp(CFG) -> ok, do some nifty output. +%% cfg_to_linear(CFG) -> LinearCode, linearizes the code of CFG +%% mk_goto(Label) -> instruction +%% is_phi(Instr) -> boolean(), true if the instruction is a phi-instruction. +%% phi_remove_pred(PhiInstr, Pred) -> NewPhi, +%% Removes the predecessor Pred from the phi instruction. +%% highest_var(Code) -> term(), +%% Returns the highest variable used or defined in the code. +%% +%%===================================================================== + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Primitives (not all of these are exported) +%% + +-spec start_label(cfg()) -> cfg_lbl(). +start_label(CFG) -> (CFG#cfg.info)#cfg_info.start_label. + +-ifndef(GEN_CFG). +-spec start_label_update(cfg(), cfg_lbl()) -> cfg(). +start_label_update(CFG, NewStartLabel) -> + Info = CFG#cfg.info, + CFG#cfg{info = Info#cfg_info{start_label = NewStartLabel}}. + +-spec function(cfg()) -> mfa(). +function(CFG) -> (CFG#cfg.info)#cfg_info.'fun'. + +-spec is_closure(cfg()) -> boolean(). +is_closure(CFG) -> (CFG#cfg.info)#cfg_info.is_closure. + +-spec is_leaf(cfg()) -> boolean(). +is_leaf(CFG) -> (CFG#cfg.info)#cfg_info.is_leaf. + +mk_empty_cfg(Fun, StartLbl, Data, Closure, Leaf, Params) -> + Info = #cfg_info{'fun' = Fun, + start_label = StartLbl, + is_closure = Closure, + is_leaf = Leaf, + params = Params}, + #cfg{table = gb_trees:empty(), data = Data, info = Info}. + +data(CFG) -> CFG#cfg.data. +-endif. % GEN_CFG + +-ifdef(REMOVE_TRIVIAL_BBS_NEEDED). +-spec update_data(cfg(), cfg_data()) -> cfg(). +update_data(CFG, D) -> + CFG#cfg{data = D}. +-endif. + +-ifdef(PARAMS_NEEDED). +params(CFG) -> (CFG#cfg.info)#cfg_info.params. +-endif. + +-ifdef(PARAMS_UPDATE_NEEDED). +params_update(CFG, NewParams) -> + Info = CFG#cfg.info, + CFG#cfg{info = Info#cfg_info{params = NewParams}}. +-endif. + +-ifdef(CLOSURE_ARITY_NEEDED). +-spec closure_arity(cfg()) -> arity(). +closure_arity(CFG) -> + Info = CFG#cfg.info, + Info#cfg_info.closure_arity. + +-spec closure_arity_update(cfg(), arity()) -> cfg(). +closure_arity_update(CFG, Arity) -> + Info = CFG#cfg.info, + CFG#cfg{info = Info#cfg_info{closure_arity = Arity}}. +-endif. + +%% %% Don't forget to do a start_label_update if necessary. +%% update_code(CFG, NewCode) -> +%% take_bbs(NewCode, CFG). + +-ifdef(INFO_NEEDED). +info(CFG) -> (CFG#cfg.info)#cfg_info.info. +%% info_add(CFG, A) -> +%% As = info(CFG), +%% Info = CFG#cfg.info, +%% CFG#cfg{info = Info#cfg_info{info = [A|As]}}. +info_update(CFG, I) -> + Info = CFG#cfg.info, + CFG#cfg{info = Info#cfg_info{info = I}}. +-endif. + +%%===================================================================== +-ifndef(GEN_CFG). + +-spec other_entrypoints(cfg()) -> [cfg_lbl()]. +%% @doc Returns a list of labels that are refered to from the data section. + +other_entrypoints(CFG) -> + hipe_consttab:referred_labels(data(CFG)). + +%% is_entry(Lbl, CFG) -> +%% Lbl =:= start_label(CFG) orelse +%% lists:member(Lbl, other_entrypoints(CFG)). + +%% @spec bb(CFG::cfg(), Label::cfg_lbl()) -> basic_block() +%% @doc Returns the basic block of the CFG which begins at the Label. +bb(CFG, Label) -> + HT = CFG#cfg.table, + case gb_trees:lookup(Label, HT) of + {value, {Block,_Succ,_Pred}} -> + Block; + none -> + not_found + end. + +%% Remove duplicates from a list. The first instance (in left-to-right +%% order) of an element is kept, remaining instances are removed. +-spec remove_duplicates([cfg_lbl()]) -> [cfg_lbl()]. +remove_duplicates(List) -> + remove_duplicates(List, []). + +-spec remove_duplicates([cfg_lbl()], [cfg_lbl()]) -> [cfg_lbl()]. +remove_duplicates([H|T], Acc) -> + NewAcc = + case lists:member(H, Acc) of + false -> [H|Acc]; + true -> Acc + end, + remove_duplicates(T, NewAcc); +remove_duplicates([], Acc) -> + lists:reverse(Acc). + + +-ifdef(RTL_CFG). %% this could be CFG_CAN_HAVE_PHI_NODES + %% if Icode also starts using this function + +%% @spec bb_insert_between(CFG::cfg(), +%% Label::cfg_lbl(), NewBB::basic_block(), +%% Pred::cfg_lbl(), Succ::cfg_lbl()) -> cfg() +%% +%% @doc Insert the new basic block with label Label in the edge from +%% Pred to Succ + +bb_insert_between(CFG, Label, NewBB, Pred, Succ) -> + Last = hipe_bb:last(NewBB), + %% Asserts that NewBB ends in a label + true = is_branch(Last), + %% Asserts that the only Successor of NewBB is Succ + [Succ] = remove_duplicates(branch_successors(Last)), + HT = CFG#cfg.table, + %% Asserts that Label does not exist in the CFG + none = gb_trees:lookup(Label, HT), + %% Updates the predecessor of NewBB + {value, {PBB, PSucc, PPred}} = gb_trees:lookup(Pred, HT), + NewPSucc = [Label|lists:delete(Succ, PSucc)], + PLast = hipe_bb:last(PBB), + PButLast = hipe_bb:butlast(PBB), + NewPBB = hipe_bb:code_update(PBB, PButLast++[redirect_jmp(PLast, Succ, Label)]), + HT1 = gb_trees:update(Pred, {NewPBB,NewPSucc,PPred}, HT), + %% Updates the successor of NewBB + {value, {SBB, SSucc, SPred}} = gb_trees:lookup(Succ, HT1), + NewSPred = [Label|lists:delete(Pred, SPred)], + SCode = hipe_bb:code(SBB), + NewSCode = redirect_phis(SCode, Pred, Label, []), + NewSBB = hipe_bb:code_update(SBB, NewSCode), + HT2 = gb_trees:update(Succ, {NewSBB,SSucc,NewSPred}, HT1), + %% Enters NewBB into the CFG + HT3 = gb_trees:insert(Label, {NewBB,[Succ],[Pred]}, HT2), + CFG#cfg{table = HT3}. + +redirect_phis([], _OldPred, _NewPred, Acc) -> + lists:reverse(Acc); +redirect_phis([I|Rest], OldPred, NewPred, Acc) -> + case is_phi(I) of + true -> + Phi = phi_redirect_pred(I, OldPred, NewPred), + redirect_phis(Rest, OldPred, NewPred, [Phi|Acc]); + false -> + redirect_phis(Rest, OldPred, NewPred, [I|Acc]) + end. + +-endif. + +%% @spec bb_add(CFG::cfg(), Label::cfg_lbl(), NewBB::basic_block()) -> cfg() +%% @doc Adds a new basic block to a CFG (or updates an existing block). +bb_add(CFG, Label, NewBB) -> + %% Asserting that the NewBB is a legal basic block + Last = hipe_bb:last(NewBB), + case is_branch(Last) of + true -> ok; + false -> throw({?MODULE, {"Basic block ends without branch", Last}}) + end, + %% The order of the elements from branch_successors/1 is + %% significant. It determines the basic block order when the CFG is + %% converted to linear form. That order may have been tuned for + %% branch prediction purposes. + Succ = remove_duplicates(branch_successors(Last)), + HT = CFG#cfg.table, + {OldSucc, OldPred} = case gb_trees:lookup(Label, HT) of + {value, {_Block, OSucc, OPred}} -> + {OSucc, OPred}; + none -> + {[], []} + end, + %% Change this block to contain new BB and new successors, but keep + %% the old predecessors which will be updated in the following steps + HT1 = gb_trees:enter(Label, {NewBB, Succ, OldPred}, HT), + %% Add this block as predecessor to its new successors + HT2 = lists:foldl(fun (P, HTAcc) -> + add_pred(HTAcc, P, Label) + end, + HT1, Succ -- OldSucc), + %% Remove this block as predecessor of its former successors + HT3 = lists:foldl(fun (S, HTAcc) -> + remove_pred(HTAcc, S, Label) + end, + HT2, OldSucc -- Succ), + CFG#cfg{table = HT3}. + +remove_pred(HT, FromL, PredL) -> + case gb_trees:lookup(FromL, HT) of + {value, {Block, Succ, Preds}} -> + Code = hipe_bb:code(Block), + NewCode = remove_pred_from_phis(Code, PredL, []), + NewBlock = hipe_bb:code_update(Block, NewCode), + gb_trees:update(FromL, {NewBlock,Succ,lists:delete(PredL,Preds)}, HT); + none -> + HT + end. + +add_pred(HT, ToL, PredL) -> + case gb_trees:lookup(ToL, HT) of + {value,{Block,Succ,Preds}} -> + gb_trees:update(ToL, {Block,Succ,[PredL|lists:delete(PredL,Preds)]}, HT); + none -> + gb_trees:insert(ToL, {[],[],[PredL]}, HT) + end. + +%% find_highest_label(CFG) -> +%% Labels = labels(CFG), +%% lists:foldl(fun(X, Acc) -> erlang:max(X, Acc) end, 0, Labels). +%% +%% find_highest_var(CFG) -> +%% Labels = labels(CFG), +%% Fun = fun(X, Max) -> +%% Code = hipe_bb:code(bb(CFG, X)), +%% NewMax = highest_var(Code), +%% erlang:max(Max, NewMax) +%% end, +%% lists:foldl(Fun, 0, Labels). + +-ifdef(CFG_CAN_HAVE_PHI_NODES). +%% phi-instructions in a removed block's successors must be aware of +%% the change. +remove_pred_from_phis(List = [I|Left], Label, Acc) -> + case is_phi(I) of + true -> + NewAcc = [phi_remove_pred(I, Label)|Acc], + remove_pred_from_phis(Left, Label, NewAcc); + false -> + lists:reverse(Acc) ++ List + end; +remove_pred_from_phis([], _Label, Acc) -> + lists:reverse(Acc). +-else. +%% this is used for code representations like those of back-ends which +%% do not have phi-nodes. +remove_pred_from_phis(Code, _Label, _Acc) -> + Code. +-endif. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Constructs a CFG from a list of instructions. +%% + +take_bbs([], CFG) -> + CFG; +take_bbs(Xs, CFG) -> + Lbl = hd(Xs), + case is_label(Lbl) of + true -> + case take_bb(tl(Xs), []) of + {Code, Rest} -> + NewCFG = bb_add(CFG, label_name(Lbl), hipe_bb:mk_bb(Code)), + take_bbs(Rest, NewCFG) + end; + false -> + erlang:error({?MODULE,"basic block doesn't start with a label",Xs}) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Take_bb returns: +%% - {Code, Rest}. +%% * Code is a list of all the instructions. +%% * Rest is the remainder of the instructions + +take_bb([], Code) -> + {lists:reverse(Code), []}; +take_bb([X, Y|Xs], Code) -> + case is_label(X) of + true -> %% Empty block fallthrough + {[mk_goto(label_name(X))], [X,Y|Xs]}; + false -> + case is_branch(X) of + true -> + case is_label(Y) of + true -> + {lists:reverse([X|Code]), [Y|Xs]}; + false -> + %% This should not happen... + %% move the problem to the next BB. + {lists:reverse([X|Code]), [Y|Xs]} + end; + false -> %% X not branch + case is_label(Y) of + true -> + {lists:reverse([mk_goto(label_name(Y)),X|Code]), [Y|Xs]}; + false -> + take_bb([Y|Xs], [X|Code]) + end + end + end; +take_bb([X], []) -> + case is_label(X) of + true -> + %% We don't want the CFG to just end with a label... + %% We loop forever instead... + {[X,mk_goto(label_name(X))],[]}; + false -> + {[X],[]} + end; +take_bb([X], Code) -> + case is_label(X) of + true -> + %% We don't want the CFG to just end with a label... + %% We loop for ever instead... + {lists:reverse(Code),[X,mk_goto(label_name(X))]}; + false -> + {lists:reverse([X|Code]),[]} + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Functions for extracting the names of the basic blocks in various +%% orders. +%% + +labels(CFG) -> + HT = CFG#cfg.table, + gb_trees:keys(HT). + +postorder(CFG) -> + lists:reverse(reverse_postorder(CFG)). + +reverse_postorder(CFG) -> + Start = start_label(CFG), + {Ordering, _Visited} = + depth_search([Start|other_entrypoints(CFG)], none_visited(), CFG, []), + Ordering. + +depth_search([N|Ns], Visited, CFG, Acc) -> + case is_visited(N, Visited) of + true -> + depth_search(Ns, Visited, CFG, Acc); + false -> + {Order, Vis} = depth_search(succ(CFG, N), visit(N, Visited), CFG, Acc), + depth_search(Ns, Vis, CFG, [N|Order]) + end; +depth_search([], Visited, _, Ordering) -> + {Ordering, Visited}. + +-ifdef(PREORDER). +preorder(CFG) -> + Start = start_label(CFG), + {Ordering, _Visited} = + preorder_search([Start|other_entrypoints(CFG)], none_visited(), CFG, []), + lists:reverse(Ordering). + +preorder_search([N|Ns], Visited, CFG, Acc) -> + case is_visited(N, Visited) of + true -> + preorder_search(Ns, Visited, CFG, Acc); + false -> + {Order, Vis} = + preorder_search(succ(CFG, N), visit(N, Visited), CFG, [N|Acc]), + preorder_search(Ns, Vis, CFG, Order) + end; +preorder_search([], Visited, _, Ordering) -> + {Ordering,Visited}. +-endif. % PREORDER + +-ifdef(BREADTH_ORDER). +breadthorder(CFG) -> + lists:reverse(reverse_breadthorder(CFG)). + +reverse_breadthorder(CFG) -> + Start = start_label(CFG), + {Vis, RBO1} = breadth_list([Start], none_visited(), CFG, []), + {_Vis1, RBO2} = breadth_list(other_entrypoints(CFG), Vis, CFG, RBO1), + RBO2. + +breadth_list([X|Xs], Vis, CFG, BO) -> + case is_visited(X, Vis) of + true -> + breadth_list(Xs, Vis, CFG, BO); + false -> + breadth_list(Xs ++ succ(CFG, X), visit(X, Vis), CFG, [X|BO]) + end; +breadth_list([], Vis, _CFG, BO) -> + {Vis, BO}. +-endif. + +-spec none_visited() -> gb_set(). +none_visited() -> + gb_sets:empty(). + +visit(X, Vis) -> + gb_sets:add(X, Vis). + +is_visited(X, Vis) -> + gb_sets:is_member(X, Vis). + +-endif. % GEN_CFG + +%%--------------------------------------------------------------------- + +succ(SuccMap, Label) -> + HT = SuccMap#cfg.table, + case gb_trees:lookup(Label, HT) of + {value, {_Block,Succ,_Pred}} -> + Succ; + none -> + erlang:error({"successor not found", Label, SuccMap}) + end. + +-ifdef(PRED_NEEDED). +pred(Map, Label) -> + HT = Map#cfg.table, + case gb_trees:lookup(Label, HT) of + {value, {_Block,_Succ,Pred}} -> + Pred; + none -> + erlang:error({"predecessor not found", Label, Map}) + end. +-endif. % PRED_NEEDED + +-ifndef(GEN_CFG). +fallthrough(CFG, Label) -> + HT = CFG#cfg.table, + case gb_trees:lookup(Label, HT) of + {value, {_Block, Succ, _}} -> + case Succ of + [X|_] -> X; + _ -> none + end; + none -> + erlang:error({"fallthrough label not found", Label}) + end. + +conditional(CFG, Label) -> + HT = CFG#cfg.table, + {value,{_Block,Succ,_}} = gb_trees:lookup(Label, HT), + case Succ of + [] -> none; + [_] -> none; + [_|Labels] -> Labels + end. +-endif. % GEN_CFG + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Linearize the code in a CFG. Returns a list of instructions. +%% + +-ifdef(GEN_CFG). +-else. +linearize_cfg(CFG) -> + Start = start_label(CFG), + Vis = none_visited(), + {Vis0, NestedCode} = lin_succ(Start, CFG, Vis), + BlocksInData = hipe_consttab:referred_labels(data(CFG)), + AllCode = lin_other_entries(NestedCode, CFG, BlocksInData, Vis0), + lists:flatten(AllCode). + +lin_succ(none, _CFG, Vis) -> + {Vis, []}; +lin_succ([Label|Labels], CFG, Vis) -> + {Vis1, Code1} = lin_succ(Label, CFG, Vis), + {Vis2, Code2} = lin_succ(Labels, CFG, Vis1), + {Vis2, [Code1,Code2]}; +lin_succ([], _CFG, Vis) -> + {Vis, []}; +lin_succ(Label, CFG, Vis) -> + case is_visited(Label, Vis) of + true -> + {Vis, []}; % already visited + false -> + Vis0 = visit(Label, Vis), + case bb(CFG, Label) of + not_found -> + erlang:error({?MODULE, "No basic block with label", Label}); + BB -> + Fallthrough = fallthrough(CFG, Label), + Cond = conditional(CFG, Label), + LblInstr = mk_label(Label), + {Vis1, Code1} = lin_succ(Fallthrough, CFG, Vis0), + {Vis2, Code2} = lin_succ(Cond, CFG, Vis1), + {Vis2, [[LblInstr|hipe_bb:code(BB)], Code1, Code2]} + end + end. + +lin_other_entries(Code, _CFG, [], _Vis) -> + Code; +lin_other_entries(Code, CFG, [E|Es], Vis) -> + {Vis0, MoreCode} = lin_succ(E, CFG, Vis), + lin_other_entries([Code, MoreCode], CFG, Es, Vis0). +-endif. + +-ifdef(FIND_NEW_LABEL_NEEDED). +find_new_label(Old, Map) -> + forward(Old, Map). +-endif. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Remove empty BBs. +%% +%% Removes basic blocks containing only a goto to another BB. +%% Branches to removed blocks are updated to the successor of the +%% removed block. +%% Loads (or other operations) on the label of the BB are also +%% updated. So are any references from the data section. +%% + +-ifdef(REMOVE_TRIVIAL_BBS_NEEDED). + +-spec remove_trivial_bbs(cfg()) -> cfg(). +remove_trivial_bbs(CFG) -> + ?opt_start_timer("Merge BBs"), + CFG0 = merge_bbs(rewrite_trivial_branches(CFG)), + ?opt_stop_timer("Merge BBs"), + %% pp(CFG0), + ?opt_start_timer("FindDead"), + {NewMap, CFG1} = remap(labels(CFG0), rd_map_new(), CFG0), + ?opt_stop_timer("FindDead"), + ?opt_start_timer("Labels"), + Labels = labels(CFG1), + ?opt_stop_timer("Labels"), + ?opt_start_timer("RedirectBranches"), + CFG2 = redirect_branches(NewMap, CFG1), + ?opt_stop_timer("RedirectBranches"), + ?opt_start_timer("RedirectOps"), + CFG3 = redirect_ops(Labels, CFG2, NewMap), + ?opt_stop_timer("RedirectOps"), + ?opt_start_timer("RedirectData"), + CFG4 = redirect_data(CFG3, NewMap), + ?opt_stop_timer("RedirectData"), + ?opt_start_timer("RedirectStart"), + CFG5 = redirect_start(CFG4, NewMap), + ?opt_stop_timer("RedirectStart"), + %% pp(CFG5), + CFG5. + +redirect_start(CFG, Map) -> + Start = start_label(CFG), + case forward(Start, Map) of + Start -> CFG; + NewStart -> + start_label_update(CFG, NewStart) + end. + +redirect_data(CFG, Map) -> + Data = data(CFG), + NewData = hipe_consttab:update_referred_labels(Data, rd_succs(Map)), + update_data(CFG, NewData). + +redirect_branches(Map, CFG) -> + lists:foldl(fun ({From,{newsuccs,Redirects}}, CFGAcc) -> + lists:foldl( + fun({ToOld,ToNew}, CFG1) -> + case bb(CFG1, From) of + not_found -> + CFG1; + _ -> + To = forward(ToNew, Map), + redirect(CFG1, From, ToOld, To) + end + end, + CFGAcc, + Redirects); + (_, CFGAcc) -> CFGAcc + end, + CFG, + gb_trees:to_list(Map)). + +redirect(CFG, From, ToOld, ToNew) -> + BB = bb(CFG, From), + LastInstr = hipe_bb:last(BB), + NewLastInstr = redirect_jmp(LastInstr, ToOld, ToNew), + NewBB = hipe_bb:mk_bb(hipe_bb:butlast(BB) ++ [NewLastInstr]), + bb_add(CFG, From, NewBB). + +bb_remove(CFG, Label) -> + HT = CFG#cfg.table, + case gb_trees:lookup(Label, HT) of + {value, {_Block, Succ, _Preds}} -> + %% Remove this block as a pred from all successors. + HT1 = lists:foldl(fun (S,HTAcc) -> + remove_pred(HTAcc, S, Label) + end, + HT, Succ), + CFG#cfg{table = gb_trees:delete(Label, HT1)}; + none -> + CFG + end. + +remap([L|Rest], Map, CFG) -> + case is_empty(bb(CFG, L)) of + true -> + case succ(CFG, L) of + [L] -> %% This is an empty (infinite) self loop. Leave it. + remap(Rest, Map, CFG); + [SuccL] -> + CFG1 = bb_remove(CFG, L), + NewMap = remap_to_succ(L, SuccL, Map, CFG), + remap(Rest, NewMap, CFG1) + end; + false -> + remap(Rest, Map, CFG) + end; +remap([], Map, CFG) -> + {Map, CFG}. + +remap_to_succ(L, SuccL, Map, PredMap) -> + insert_remap(L, forward(SuccL,Map), pred(PredMap,L), Map). + +%% Find the proxy for a BB +forward(L, Map) -> + case gb_trees:lookup(L, Map) of + {value, {dead, To}} -> + forward(To, Map); %% Hope this terminates. + _ -> L + end. + +%% A redirection map contains mappings from labels to +%% none -> this BB is not affected by the remapping. +%% {dead,To} -> this BB is dead, To is the new proxy. +%% {newsuccs,[{X,Y}|...]} -> The successor X is redirected to Y. + +rd_map_new() -> gb_trees:empty(). + +rd_succs(M) -> + lists:foldl(fun ({From,{dead,To}}, Acc) -> [{From,forward(To,M)}|Acc]; + (_, Acc) -> Acc + end, + [], + gb_trees:to_list(M)). + +add_redirectedto(L, From, To, Map) -> + case gb_trees:lookup(L, Map) of + {value, {newsuccs, NS}} -> + gb_trees:update(L,{newsuccs,[{From,To}|lists:keydelete(From,1,NS)]},Map); + {value, {dead, _}} -> Map; + none -> + gb_trees:insert(L, {newsuccs, [{From, To}]}, Map) + end. + +insert_remap(L, ToL, Preds, Map) -> + Map2 = gb_trees:enter(L, {dead, ToL}, Map), + lists:foldl(fun (Pred, AccMap) -> + add_redirectedto(Pred, L, ToL, AccMap) + end, + Map2, + Preds). + +is_empty(BB) -> + is_empty_bb(hipe_bb:code(BB)). + +is_empty_bb([I]) -> + is_goto(I); %% A BB with just a 'goto' is empty. +is_empty_bb([I|Is]) -> + case is_comment(I) of + true -> + is_empty_bb(Is); + false -> + false + end; +is_empty_bb([]) -> + true. + + +%% Rewrite all pure branches with one successor to goto:s + +-spec rewrite_trivial_branches(cfg()) -> cfg(). +rewrite_trivial_branches(CFG) -> + rewrite_trivial_branches(postorder(CFG), CFG). + +rewrite_trivial_branches([L|Left], CFG) -> + BB = bb(CFG, L), + Last = hipe_bb:last(BB), + case is_goto(Last) of + true -> + rewrite_trivial_branches(Left, CFG); + false -> + case is_pure_branch(Last) of + false -> + rewrite_trivial_branches(Left, CFG); + true -> + case succ(CFG, L) of + [Successor] -> + Head = hipe_bb:butlast(BB), + NewBB = hipe_bb:mk_bb(Head ++ [mk_goto(Successor)]), + NewCFG = bb_add(CFG, L, NewBB), + rewrite_trivial_branches(Left, NewCFG); + _ -> + rewrite_trivial_branches(Left, CFG) + end + end + end; +rewrite_trivial_branches([], CFG) -> + CFG. + + +%% Go through the CFG and find pairs of BBs that can be merged to one BB. +%% They are of the form: +%% +%% L +%% | +%% Successor +%% +%% That is, the block L has only one successor (Successor) and that +%% successor has no other predecessors than L. +%% +%% Note: calls might end a basic block + +merge_bbs(CFG) -> + lists:foldl(fun merge_successor/2, CFG, postorder(CFG)). + +%% If L fulfills the requirements, merge it with its successor. +merge_successor(L, CFG) -> + %% Get the BB L (If it still exists). + case bb(CFG, L) of + not_found -> CFG; + BB -> + StartLabel = start_label(CFG), + Last = hipe_bb:last(BB), + %% Note: Cannot use succ/2 since the instruction can have more than + %% one successor that are the same label. + case {branch_successors(Last), fails_to(Last)} of + {[Successor],[Successor]} -> + %% The single successor is the fail-label; don't merge. + CFG; + {[Successor],_} when Successor =/= StartLabel -> + %% Make sure the succesor only have this block as predecessor. + case [L] =:= pred(CFG, Successor) of + true -> + %% Remove the goto or remap fall-through in BB and merge the BBs + NewCode = merge(BB, bb(CFG, Successor), Successor), + NewBB = hipe_bb:mk_bb(NewCode), + bb_add(bb_remove(CFG, Successor), L, NewBB); + false -> + CFG + end; + _ -> + %% Not exactly one successor or tried to merge with the + %% entry point + CFG + end + end. + +%% Merge BB and BB2 +merge(BB, BB2, BB2_Label) -> + Head = hipe_bb:butlast(BB), + Last = hipe_bb:last(BB), + Tail = hipe_bb:code(BB2), + case is_goto(Last) of + true -> + %% Just ignore the goto. + Head ++ Tail; + false -> + %% The last instr is not a goto, + %% e.g. a call with only fall-through + %% Remove the fall-through with the []-label. + Head ++ [redirect_jmp(Last, BB2_Label, [])|Tail] + end. + +-endif. % REMOVE_TRIVIAL_BBS_NEEDED + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Remove unreachable BBs. +%% +%% A BB is unreachable if it cannot be reached by any path from the +%% start label of the function. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-ifdef(REMOVE_UNREACHABLE_CODE). + +-spec remove_unreachable_code(cfg()) -> cfg(). + +remove_unreachable_code(CFG) -> + Start = start_label(CFG), + Reachable = find_reachable([Start], CFG, gb_sets:from_list([Start])), + %% Reachable is an ordset: it comes from gb_sets:to_list/1. + %% So use ordset:subtract instead of '--' below. + Labels = ordsets:from_list(labels(CFG)), + case ordsets:subtract(Labels, Reachable) of + [] -> + CFG; + Remove -> + NewCFG = lists:foldl(fun(X, Acc) -> bb_remove(Acc, X) end, CFG, Remove), + remove_unreachable_code(NewCFG) + end. + +find_reachable([Label|Left], CFG, Acc) -> + NewAcc = gb_sets:add(Label, Acc), + Succ = succ(CFG, Label), + find_reachable([X || X <- Succ, not gb_sets:is_member(X, Acc)] ++ Left, + CFG, NewAcc); +find_reachable([], _CFG, Acc) -> + gb_sets:to_list(Acc). + +-endif. diff --git a/lib/hipe/flow/ebb.inc b/lib/hipe/flow/ebb.inc new file mode 100644 index 0000000000..42d7ff3793 --- /dev/null +++ b/lib/hipe/flow/ebb.inc @@ -0,0 +1,247 @@ +%% -*- Erlang -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-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% +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% IDENTIFIES THE EXTENDED BASIC BLOCKS OF A CFG +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-export([cfg/1, + %% dag/2, + type/1, + node_label/1, + node_successors/1 + ]). +-ifdef(DEBUG_EBB). +-export([pp/1]). +-endif. + +-define(cfg, ?CFG). + +%%-------------------------------------------------------------------- +%% The extended basic block datatype +%% +%% An EBB is identified with the label of the root node. +%% It's a tree +%% +%% EBB := {ebb_node, Label, [EBB]} +%% | {ebb_leaf, SuccesorLabel} +%%-------------------------------------------------------------------- + +%% XXX: Cheating big time! no recursive types +-type ebb() :: {ebb_node, icode_lbl(), _} + | {ebb_leaf, icode_lbl()}. + +-record(ebb_node, {label :: icode_lbl(), successors :: [ebb()]}). +-record(ebb_leaf, {successor :: icode_lbl()}). + +%%-------------------------------------------------------------------- +%% Returns a list of extended basic blocks. +%%-------------------------------------------------------------------- + +-spec cfg(cfg()) -> [ebb()]. + +cfg(CFG) -> + Start = ?cfg:start_label(CFG), + Labels = ?cfg:reverse_postorder(CFG), + Roots = [Start], + Blocks = Labels -- Roots, + Visited = new_visited(), + build_all_ebb(Roots, Blocks, Visited, CFG). + +new_visited() -> + gb_sets:empty(). +visited(L, Visited) -> + gb_sets:is_member(L, Visited). +visit(L, Visited) -> + gb_sets:add(L, Visited). + +build_all_ebb(Roots, Blocks, Visited, CFG) -> + build_all_ebb(Roots, Blocks, Visited, CFG, []). + +build_all_ebb([], [], _, _CFG, Ebbs) -> + lists:reverse(Ebbs); +build_all_ebb([], [BlockLeft|BlocksLeft], Visited, CFG, Ebbs) -> + case visited(BlockLeft, Visited) of + true -> + build_all_ebb([], BlocksLeft, Visited, CFG, Ebbs); + false -> + build_all_ebb([BlockLeft], BlocksLeft, Visited, CFG, Ebbs) + end; +build_all_ebb([Root|Roots], Blocks, Visited, CFG, Ebbs) -> + {Ebb, NewVisited} = build_ebb(Root, Visited, CFG), + build_all_ebb(Roots, Blocks, NewVisited, CFG, [Ebb|Ebbs]). + +%% +%% Build the extended basic block with Lbl as its root. +%% + +build_ebb(Lbl, Visited, CFG) -> + build_ebb(Lbl, Visited, + fun (NodeL, NewVisited) -> {NodeL, NewVisited} end, + [], CFG). + +build_ebb(Lbl, Visited, MkFun, EBBs, CFG) -> + Succ = ?cfg:succ(CFG, Lbl), + add_succ(Succ, visit(Lbl, Visited), Lbl, MkFun, EBBs, CFG). + +add_succ([], Visited, Node, MkFun, EBBs, _CFG) -> + MkFun(mk_node(Node, lists:reverse(EBBs)), Visited); +add_succ([Lbl|Lbls], Visited, Node, MkFun, EBBs, CFG) -> + case [visited(Lbl, Visited)|?cfg:pred(CFG, Lbl)] of + [false,_] -> + build_ebb(Lbl, Visited, + fun (NewEbb, Visited0) -> + add_succ(Lbls, Visited0, Node, MkFun, [NewEbb|EBBs], CFG) + end, [], CFG); + _ -> + add_succ(Lbls, Visited, Node, MkFun, [mk_leaf(Lbl)|EBBs], CFG) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Generate a list of dags. +%% + +%% dag(EBBs, CFG) -> +%% Start = ?cfg:start_label(CFG), +%% Roots = [Start], +%% Edges = all_adges(EBBs, Roots), +%% start_dag(Roots, Edges, []). +%% +%% start_dag([], _Edges, _Visit) -> +%% []; +%% start_dag([Root|Roots], Edges, Visit) -> +%% case lists:member(Root, Visit) of +%% true -> +%% start_dag(Roots, Edges, Visit); +%% false -> +%% {Dag, Roots0, Visit0} = +%% fill_dag(Root, [Root], Edges, Roots, [Root|Visit]), +%% [lists:reverse(Dag) | start_dag(Roots0, Edges, Visit0)] +%% end. +%% +%% fill_dag(Lbl, Dag, Edges, Roots, Visit) -> +%% Succ = find_succ(Lbl, Edges), +%% add_dag_succ(Succ, Dag, Edges, Roots, Visit). +%% +%% add_dag_succ([], Dag, _Edges, Roots, Visit) -> +%% {Dag, Roots, Visit}; +%% add_dag_succ([S|Ss], Dag, Edges, Roots, Visit) -> +%% {Dag0, Roots0, Visit0} = add_dag_succ(Ss, Dag, Edges, Roots, Visit), +%% Pred = find_pred(S, Edges), +%% case all_in(Pred, Dag0) of +%% true -> +%% fill_dag(S, [S|Dag0], Edges, Roots0, [S|Visit0]); +%% false -> +%% {Dag0, [S|Roots], Visit0} +%% end. +%% +%% find_succ(_Lbl, []) -> +%% []; +%% find_succ(Lbl, [{Lbl, Succ}|Edges]) -> +%% [Succ | find_succ(Lbl, Edges)]; +%% find_succ(Lbl, [_|Edges]) -> +%% find_succ(Lbl, Edges). +%% +%% find_pred(_Lbl, []) -> +%% []; +%% find_pred(Lbl, [{Pred, Lbl}|Edges]) -> +%% [Pred | find_pred(Lbl, Edges)]; +%% find_pred(Lbl, [_|Edges]) -> +%% find_pred(Lbl, Edges). +%% +%% all_edges([], _Roots) -> +%% []; +%% all_edges([EBB|EBBs], Roots) -> +%% succ_edges(node_label(EBB), ebb_successors(EBB), EBBs, Roots). +%% +%% succ_edges(Lbl, [], EBBs, Roots) -> +%% case lists:member(Lbl, Roots) of +%% true -> +%% [{start, Lbl} | all_edges(EBBs, Roots)]; +%% false -> +%% all_edges(EBBs, Roots) +%% end; +%% succ_edges(Lbl, [S|Ss], EBBs, Roots) -> +%% [{Lbl, S} | succ_edges(Lbl, Ss, EBBs, Roots)]. +%% +%% all_in([], _List) -> +%% true; +%% all_in([X|Xs], List) -> +%% lists:member(X, List) andalso all_in(Xs, List). +%% +%% find_ebb(Lbl, [EBB|EBBs]) -> +%% case node_label(EBB) of +%% Lbl -> +%% EBB; +%% _ -> +%% find_ebb(Lbl, EBBs) +%% end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-spec mk_node(icode_lbl(), [ebb()]) -> #ebb_node{}. +mk_node(Label, Successors) -> #ebb_node{label=Label, successors=Successors}. + +-spec node_label(#ebb_node{}) -> icode_lbl(). +node_label(#ebb_node{label=Label}) -> Label. + +-spec node_successors(#ebb_node{}) -> [ebb()]. +node_successors(#ebb_node{successors=Successors}) -> Successors. + +-spec mk_leaf(icode_lbl()) -> #ebb_leaf{}. +mk_leaf(NextEbb) -> #ebb_leaf{successor=NextEbb}. +%% leaf_next(Leaf) -> Leaf#ebb_leaf.successor. + +-spec type(#ebb_node{}) -> 'node' ; (#ebb_leaf{}) -> 'leaf'. +type(#ebb_node{}) -> node; +type(#ebb_leaf{}) -> leaf. + +%% ebb_successors(EBB) -> +%% ordsets:from_list(ebb_successors0(EBB)). +%% +%% ebb_successors0(#ebb_leaf{successor=NextEBB}) -> +%% [NextEBB]; +%% ebb_successors0(#ebb_node{successors=SuccessorNodes}) -> +%% lists:append(lists:map(fun ebb_successors0/1, SuccessorNodes)). + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Prettyprint a list of extended basic blocks +%% + +-ifdef(DEBUG_EBB). + +pp(EBBs) -> + lists:map(fun(E) -> pp(E, 0) end, EBBs). + +pp(EBB, Indent) -> + io:format([$~]++integer_to_list(Indent)++[$c],[$ ]), + case type(EBB) of + node -> + io:format("~w~n", [node_label(EBB)]), + lists:map(fun(E) -> pp(E, Indent+3) end, node_successors(EBB)); + leaf -> + io:format("* -> ~w~n", [leaf_next(EBB)]) + end. + +-endif. diff --git a/lib/hipe/flow/hipe_bb.erl b/lib/hipe/flow/hipe_bb.erl new file mode 100644 index 0000000000..16730f1dce --- /dev/null +++ b/lib/hipe/flow/hipe_bb.erl @@ -0,0 +1,81 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-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% +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Basic Block Module +%% +%% Exports: +%% ~~~~~~~~ +%% mk_bb(Code) - construct a basic block. +%% code(BB) - returns the code. +%% code_update(BB, NewCode) - replace the code in a basic block. +%% last(BB) - returns the last instruction. +%% butlast(BB) - returns the code with the last instruction removed. +%% + +-module(hipe_bb). + +-export([mk_bb/1, + code/1, + code_update/2, + is_bb/1, + last/1, + butlast/1]). + +-include("hipe_bb.hrl"). + +%% +%% Constructs a basic block. +%% Returns a basic block: {bb, Code} +%% * Code is a list of instructions + +-spec mk_bb([_]) -> bb(). + +mk_bb(Code) -> + #bb{code=Code}. + +-spec is_bb(_) -> boolean(). + +is_bb(#bb{}) -> true; +is_bb(_) -> false. + +-spec code_update(bb(), [_]) -> bb(). + +code_update(BB, Code) -> + BB#bb{code = Code}. + +-spec code(bb()) -> [_]. + +code(#bb{code = Code}) -> + Code. + +-spec last(bb()) -> _. + +last(#bb{code = Code}) -> + lists:last(Code). + +-spec butlast(bb()) -> [_]. + +butlast(#bb{code = Code}) -> + butlast_1(Code). + +butlast_1([X|Xs]) -> butlast_1(Xs,X). + +butlast_1([X|Xs],Y) -> [Y|butlast_1(Xs,X)]; +butlast_1([],_) -> []. diff --git a/lib/hipe/flow/hipe_bb.hrl b/lib/hipe/flow/hipe_bb.hrl new file mode 100644 index 0000000000..f4d426dad1 --- /dev/null +++ b/lib/hipe/flow/hipe_bb.hrl @@ -0,0 +1,30 @@ +%%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2007-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 : bb.hrl +%%% Author : Per Gustafsson <[email protected]> +%%% Description : Typed record declaration for basic blocks +%%% +%%% Created : 20 Dec 2007 by Per Gustafsson <[email protected]> +%%%------------------------------------------------------------------- + +-record(bb, {code=[] :: [_]}). + +-type bb() :: #bb{}. 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. diff --git a/lib/hipe/flow/hipe_gen_cfg.erl b/lib/hipe/flow/hipe_gen_cfg.erl new file mode 100644 index 0000000000..f9fb1f70c8 --- /dev/null +++ b/lib/hipe/flow/hipe_gen_cfg.erl @@ -0,0 +1,37 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2002-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% +%% + +-module(hipe_gen_cfg). + +-export([start_label/1, + succ/2, + pred/2 + ]). + +%%-define(DO_ASSERT, true). +-define(GEN_CFG, true). % needed for cfg.inc + +-include("../main/hipe.hrl"). +-include("cfg.hrl"). + +-spec succ(cfg(), cfg_lbl()) -> [cfg_lbl()]. +-spec pred(cfg(), cfg_lbl()) -> [cfg_lbl()]. + +-include("cfg.inc"). + diff --git a/lib/hipe/flow/liveness.inc b/lib/hipe/flow/liveness.inc new file mode 100644 index 0000000000..9c5eaf3e68 --- /dev/null +++ b/lib/hipe/flow/liveness.inc @@ -0,0 +1,332 @@ +%% -*- Erlang -*- +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-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% +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% LIVENESS ANALYSIS +%% +%% Exports: +%% ~~~~~~~ +%% analyze(CFG) - returns a liveness analysis of CFG. +%% liveout(Liveness, Label) - returns a set of variables that are live at +%% exit from basic block named Label. +%% livein(Liveness, Label) - returns a set of variables that are live at +%% entry to the basic block named Label. +%% livein_from_liveout(Instructions, LiveOut) - Given a list of instructions +%% and a liveout-set, returns a set of variables live at the +%% first instruction. +%% + +-export([analyze/1, + livein/2]). +-ifdef(LIVEOUT_NEEDED). +-export([liveout/2]). +-endif. +-ifdef(PRETTY_PRINT). +-export([pp/1]). +-endif. +%%-export([livein_from_liveout/2]). +-ifdef(DEBUG_LIVENESS). +-export([annotate_liveness/2]). +-endif. + +-include("../flow/cfg.hrl"). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Interface functions that MUST be implemented in the including file +%% +%% cfg_bb(CFG, L) -> BasicBlock, extract a basic block from a cfg. +%% cfg_postorder(CFG) -> [Labels], the labels of the cfg in postorder +%% cfg_succ(CFG, L) -> [Labels], +%% uses(Instr) -> +%% defines(Instr) -> +%% +%% Plus the following, if basic block annotations are needed +%% +%% cfg_labels(CFG) -> +%% cfg_bb_add(CFG, L, NewBB) -> +%% mk_comment(Text) -> + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% The generic liveness analysis +%% + +-spec analyze(cfg()) -> gb_tree(). + +-ifdef(HIPE_LIVENESS_CALC_LARGEST_LIVESET). +analyze(CFG) -> + PO = cfg_postorder(CFG), + InitLiveness = liveness_init(init(cfg_labels(CFG), CFG)), + _Max = case get(hipe_largest_liveset) of + undefined -> + put(hipe_largest_liveset, 0), + 0; + LL -> LL + end, + Res = merry_go_around(PO, InitLiveness,0), + case get(hipe_largest_liveset) > _Max of + true -> + io:format("Largest liveset: ~w \n", [get(hipe_largest_liveset)]); + _ -> ok + end, + Res. + +-else. + +analyze(CFG) -> + PO = cfg_postorder(CFG), + InitLiveness = liveness_init(init(PO, CFG)), + Res = merry_go_around(PO, InitLiveness, 0), + Res. +-endif. + +%% +%% The fixpoint iteration +%% + +merry_go_around(Labels, Liveness, Count) -> + case doit_once(Labels, Liveness, 0) of + {NewLiveness, 0} -> + %% io:format("Iterations ~w~n", [Count]), + NewLiveness; + {NewLiveness, _Changed} -> + merry_go_around(Labels, NewLiveness, Count+1) + end. + +%% +%% One iteration +%% + +-ifdef(HIPE_LIVENESS_CALC_LARGEST_LIVESET). +doit_once([], Liveness, Changed) -> + {Liveness, Changed}; +doit_once([L|Ls], Liveness, Changed) -> + LiveOut = liveout(Liveness, L), + Kill = ordsets:subtract(LiveOut, kill(L, Liveness)), + LiveIn = ordsets:union(Kill, gen(L,Liveness)), + {NewLiveness, ChangedP} = update_livein(L, LiveIn, Liveness), + Le = length(LiveIn), + Max = get(hipe_largest_liveset), + if Le > Max -> put(hipe_largest_liveset, Le); + true -> true + end, + doit_once(Ls, NewLiveness, Changed+ChangedP). + +-else. + +doit_once([], Liveness, Changed) -> + {Liveness, Changed}; +doit_once([L|Ls], Liveness, Changed) -> + LiveOut = liveout(Liveness, L), + Kill = ordsets:subtract(LiveOut, kill(L, Liveness)), + LiveIn = ordsets:union(Kill, gen(L,Liveness)), + {NewLiveness, ChangedP} = update_livein(L, LiveIn, Liveness), + doit_once(Ls, NewLiveness, Changed+ChangedP). +-endif. + +%% %% +%% %% Given a list of instructions and liveout, calculates livein +%% %% +%% livein_from_liveout(List, LiveOut) when is_list(List) -> +%% livein_from_liveout_1(lists:reverse(List), gb_sets:from_list(LiveOut)); +%% livein_from_liveout(Instr, LiveOut) -> +%% livein_from_liveout_1([Instr], gb_sets:from_list(LiveOut)). +%% +%% livein_from_liveout_1([], LiveOut) -> +%% gb_sets:to_list(LiveOut); +%% livein_from_liveout_1([I|Is], LiveOut) -> +%% Def = defines(I), +%% Use = uses(I), +%% DefSet = gb_sets:from_list(Def), +%% UseSet = gb_sets:from_list(Use), +%% LiveIn = gb_sets:union(gb_sets:difference(LiveOut, DefSet), UseSet), +%% Le = gb_sets:size(LiveIn), +%% Max = get(hipe_largest_liveset), +%% if Le > Max -> put(hipe_largest_liveset, Le); +%% true -> true +%% end, +%% livein_from_liveout_1(Is, LiveIn). + +%% +%% updates liveness for a basic block +%% - returns: {NewLiveness, ChangedP} +%% - ChangedP is 0 if the new LiveIn is equal to the old one +%% otherwise it's 1. +%% + +update_livein(Label, NewLiveIn, Liveness) -> + {GK, LiveIn, Successors} = liveness_lookup(Label, Liveness), + NewLiveness = liveness_update(Label, {GK, NewLiveIn, Successors}, Liveness), + if LiveIn =:= NewLiveIn -> + {NewLiveness, 0}; + true -> + {NewLiveness, 1} + end. + + +%% +%% LiveOut for a block is the union of the successors LiveIn +%% + +liveout(Liveness, L) -> + Succ = successors(L, Liveness), + case Succ of + [] -> % special case if no successors + liveout_no_succ(); + _ -> + liveout1(Succ, Liveness) + end. + +liveout1(Labels, Liveness) -> + liveout1(Labels, Liveness, ordsets:new()). + +liveout1([], _Liveness, Live) -> + Live; +liveout1([L|Ls], Liveness,Live) -> + liveout1(Ls, Liveness, ordsets:union(livein(Liveness, L), Live)). + +successors(L, Liveness) -> + {_GK, _LiveIn, Successors} = liveness_lookup(L, Liveness), + Successors. + +-spec livein(gb_tree(), _) -> [_]. + +livein(Liveness, L) -> + {_GK, LiveIn, _Successors} = liveness_lookup(L, Liveness), + LiveIn. + +kill(L, Liveness) -> + {{_Gen, Kill}, _LiveIn, _Successors} = liveness_lookup(L, Liveness), + Kill. + +gen(L, Liveness) -> + {{Gen, _Kill}, _LiveIn, _Successors} = liveness_lookup(L, Liveness), + Gen. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% init returns a list of: {Label, {{Gen, Kill}, LiveIn, Successors}} +%% - Label is the name of the basic block. +%% - Gen is the set of varables that are used by this block. +%% - Kill is the set of varables that are defined by this block. +%% - LiveIn is the set of variables that are alive at entry to the +%% block (initially empty). +%% - Successors is a list of the successors to the block. + +init([], _) -> + []; +init([L|Ls], CFG) -> + BB = cfg_bb(CFG, L), + Code = hipe_bb:code(BB), + Succ = cfg_succ(CFG, L), + Transfer = make_bb_transfer(Code, Succ), + [{L, {Transfer, ordsets:new(), Succ}} | init(Ls, CFG)]. + + +make_bb_transfer([], _Succ) -> + {ordsets:new(), ordsets:new()}; % {Gen, Kill} +make_bb_transfer([I|Is], Succ) -> + {Gen, Kill} = make_bb_transfer(Is, Succ), + InstrGen = ordsets:from_list(uses(I)), + InstrKill = ordsets:from_list(defines(I)), + Gen1 = ordsets:subtract(Gen, InstrKill), + Gen2 = ordsets:union(Gen1, InstrGen), + Kill1 = ordsets:union(Kill, InstrKill), + Kill2 = ordsets:subtract(Kill1, InstrGen), + {Gen2, Kill2}. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Annotate each basic block with liveness info +%% + +-ifdef(DEBUG_LIVENESS). + +annotate_liveness(CFG, Liveness) -> + Labels = cfg_labels(CFG), + annotate_liveness_bb(Labels, CFG, Liveness). + +annotate_liveness_bb([], CFG, _Liveness) -> + CFG; +annotate_liveness_bb([L|Ls], CFG, Liveness) -> + BB = cfg_bb(CFG, L), + Code0 = hipe_bb:code(BB), + LiveIn = strip(livein(Liveness, L)), + LiveOut = strip(liveout(Liveness, L)), + Code = [mk_comment({live_in, LiveIn}), + mk_comment({live_out, LiveOut}) + | Code0], + NewBB = hipe_bb:code_update(BB, Code), + NewCFG = cfg_bb_add(CFG, L, NewBB), + annotate_liveness_bb(Ls, NewCFG, Liveness). + +strip([]) -> + []; +strip([{_,Y}|Xs]) -> + [Y|strip(Xs)]. + +-endif. % DEBUG_LIVENESS + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +liveness_init(List) -> + liveness_init(List, gb_trees:empty()). + +liveness_init([{Lbl, Data}|Left], Acc) -> + liveness_init(Left, gb_trees:insert(Lbl, Data, Acc)); +liveness_init([], Acc) -> + Acc. + +liveness_lookup(Label, Liveness) -> + gb_trees:get(Label, Liveness). +liveness_update(Label, Val, Liveness) -> + gb_trees:update(Label, Val, Liveness). + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% pp/1 pretty prints liveness information for a CFG +%% + +-ifdef(PRETTY_PRINT). + +-spec pp(cfg()) -> 'ok'. +pp(Cfg) -> + Liveness = analyze(Cfg), + Labels = cfg_labels(Cfg), + ok = print_blocks(Labels, Liveness, Cfg). + +print_blocks([Lbl|Rest], Liveness, Cfg) -> + io:format("~nLivein:", []), + pp_liveness_info(livein(Liveness, Lbl)), + io:format("Label ~w:~n" , [Lbl]), + pp_block(Lbl, Cfg), + io:format("Liveout:", []), + pp_liveness_info(liveout(Liveness, Lbl)), + print_blocks(Rest, Liveness, Cfg); +print_blocks([], _Liveness, _Cfg) -> + ok. + +-endif. % PRETTY_PRINT |