diff options
Diffstat (limited to 'lib/hipe/flow/liveness.inc')
| -rw-r--r-- | lib/hipe/flow/liveness.inc | 332 |
1 files changed, 332 insertions, 0 deletions
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 |