%% -*- Erlang -*-
%% -*- erlang-indent-level: 2 -*-
%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 2001-2014. 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_trees: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_trees: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
