aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/ssa/hipe_ssa_liveness.inc
diff options
context:
space:
mode:
authorErlang/OTP <[email protected]>2009-11-20 14:54:40 +0000
committerErlang/OTP <[email protected]>2009-11-20 14:54:40 +0000
commit84adefa331c4159d432d22840663c38f155cd4c1 (patch)
treebff9a9c66adda4df2106dfd0e5c053ab182a12bd /lib/hipe/ssa/hipe_ssa_liveness.inc
downloadotp-84adefa331c4159d432d22840663c38f155cd4c1.tar.gz
otp-84adefa331c4159d432d22840663c38f155cd4c1.tar.bz2
otp-84adefa331c4159d432d22840663c38f155cd4c1.zip
The R13B03 release.OTP_R13B03
Diffstat (limited to 'lib/hipe/ssa/hipe_ssa_liveness.inc')
-rw-r--r--lib/hipe/ssa/hipe_ssa_liveness.inc328
1 files changed, 328 insertions, 0 deletions
diff --git a/lib/hipe/ssa/hipe_ssa_liveness.inc b/lib/hipe/ssa/hipe_ssa_liveness.inc
new file mode 100644
index 0000000000..05c8a88059
--- /dev/null
+++ b/lib/hipe/ssa/hipe_ssa_liveness.inc
@@ -0,0 +1,328 @@
+%% -*- Erlang -*-
+%% -*- 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%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% GENERIC MODULE TO PERFORM LIVENESS ANALYSIS ON SSA FORM
+%%
+%% Exports:
+%% ~~~~~~~
+%% analyze(CFG) - returns a liveness analysis of CFG.
+%% liveout(Liveness, Label) - returns the list of variables that are
+%% live at exit from basic block named Label.
+%% livein(Liveness, Label) - returns the list of variables that are
+%% live on entry to the basic block named Label.
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%% Uncomment the following if this is ever needed as an independent module
+%%
+-ifdef(LIVENESS_NEEDED).
+-export([ssa_liveness__analyze/1,
+ ssa_liveness__livein/2]).
+%% ssa_liveness__livein/3],
+%% ssa_liveness__liveout/2]).
+-endif.
+%% -ifdef(DEBUG_LIVENESS).
+%% -export([pp_liveness/1]).
+%% -endif.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Interface functions that MUST be implemented in the supporting files
+%%
+%% In the CFG file:
+%% ----------------
+%% - bb(CFG, L) -> BasicBlock, extract a basic block from a cfg.
+%% - postorder(CFG) -> [Labels], the labels of the cfg in postorder
+%% - succ(CFG, L) -> [Labels],
+%% - function(CFG) -> {M,F,A}
+%%
+%% In the CODE file:
+%% -----------------
+%% - uses(Instr) ->
+%% - defines(Instr) ->
+%% - is_phi(Instr) -> Boolean
+%% - phi_arglist(Instr) -> [{Pred, Var}]
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% The generic liveness analysis on SSA form
+%%
+ssa_liveness__analyze(CFG) ->
+ PO = ?CFG:postorder(CFG),
+ InitLiveness = liveness_init(init(PO, CFG)),
+ merry_go_around(PO, InitLiveness).
+
+%%
+%% The fixpoint iteration
+%%
+
+merry_go_around(Labels, Liveness) ->
+ case doit_once(Labels, Liveness) of
+ {fixpoint, NewLiveness} ->
+ NewLiveness;
+ {value, NewLiveness} ->
+ merry_go_around(Labels, NewLiveness)
+ end.
+
+%%
+%% One iteration
+%%
+
+doit_once(Labels, Liveness) ->
+ doit_once(Labels, Liveness, true).
+
+doit_once([], Liveness, FixPoint) ->
+ if FixPoint -> {fixpoint, Liveness};
+ true -> {value, Liveness}
+ end;
+doit_once([L|Ls], Liveness, FixPoint) ->
+ LiveOut = join_livein(Liveness, L),
+ NewLiveness = update_liveout(L, LiveOut, Liveness),
+ Kill = set_subtract(LiveOut, kill(L, NewLiveness)),
+ LiveIn = set_union(Kill, gen(L, NewLiveness)),
+ case update_livein(L, LiveIn, NewLiveness) of
+ fixpoint -> doit_once(Ls, NewLiveness, FixPoint);
+ {value, NewLiveness1} -> doit_once(Ls, NewLiveness1, false)
+ end.
+
+%%
+%% updates liveness for a basic block
+%%
+
+update_livein(Label, NewLiveIn, Liveness) ->
+ {GKD, LiveIn, LiveOut, Succ} = liveness_lookup(Label, Liveness),
+ case LiveIn of
+ NewLiveIn ->
+ fixpoint;
+ _ ->
+ {value, liveness_update(Label, {GKD,NewLiveIn,LiveOut,Succ}, Liveness)}
+ end.
+
+update_liveout(Label, NewLiveOut, Liveness) ->
+ {GKD, LiveIn, _LiveOut, Succ} = liveness_lookup(Label, Liveness),
+ liveness_update(Label, {GKD,LiveIn,NewLiveOut,Succ}, Liveness).
+
+%%
+%% Join live in to get the new live out.
+%%
+
+join_livein(Liveness, L) ->
+ Succ = successors(L, Liveness),
+ case Succ of
+ [] -> % special case if no successors
+ gb_sets:from_list(liveout_no_succ());
+ _ ->
+ join_livein1(L, Succ, Liveness)
+ end.
+
+join_livein1(Pred, Labels, Liveness) ->
+ join_livein1(Pred, Labels, Liveness, new_set()).
+
+join_livein1(_Pred, [], _Liveness, Live) ->
+ Live;
+join_livein1(Pred, [L|Ls], Liveness, Live) ->
+ OldLivein = livein_set(Liveness, L, Pred),
+ NewLive = set_union(OldLivein, Live),
+ join_livein1(Pred, Ls, Liveness, NewLive).
+
+
+ssa_liveness__liveout(Liveness, L) ->
+ {_GKD, _LiveIn, LiveOut, Successors} = liveness_lookup(L, Liveness),
+ case Successors of
+ [] -> % special case if no successors
+ liveout_no_succ();
+ _ ->
+ set_to_list(LiveOut)
+ end.
+
+-ifdef(LIVENESS_NEEDED).
+ssa_liveness__livein(Liveness, L) ->
+ set_to_list(livein_set(Liveness, L)).
+
+%% ssa_liveness__livein(Liveness, L, Pred) ->
+%% set_to_list(livein_set(Liveness, L, Pred)).
+
+livein_set(Liveness, L) ->
+ {{_Gen,_Kill,{TotalDirGen, _DirGen}}, LiveIn, _LiveOut, _Successors} =
+ liveness_lookup(L, Liveness),
+ set_union(TotalDirGen, LiveIn).
+-endif.
+
+livein_set(Liveness, L, Pred) ->
+ {{_Gen,_Kill,{_TotalDirGen, DirGen}}, LiveIn, _LiveOut, _Successors} =
+ liveness_lookup(L, Liveness),
+ case gb_trees:lookup(Pred, DirGen) of
+ none ->
+ LiveIn;
+ {value, LiveInFromPred} ->
+ set_union(LiveInFromPred, LiveIn)
+ end.
+
+successors(L, Liveness) ->
+ {_GKD, _LiveIn, _LiveOut, Successors} = liveness_lookup(L, Liveness),
+ Successors.
+
+kill(L, Liveness) ->
+ {{_Gen,Kill,_DirGen},_LiveIn,_LiveOut,_Successors} =
+ liveness_lookup(L, Liveness),
+ Kill.
+
+gen(L, Liveness) ->
+ {{Gen,_Kill,_DirGen},_LiveIn,_LiveOut,_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),
+ {Gen, Kill} = make_bb_transfer(Code, Succ),
+ DirectedGen = get_directed_gen(Code),
+ [{L, {{Gen, Kill, DirectedGen}, new_set(), new_set(), Succ}}
+ | init(Ls, CFG)].
+
+make_bb_transfer([], _Succ) ->
+ {new_set(), new_set()}; % {Gen, Kill}
+make_bb_transfer([I|Is], Succ) ->
+ {Gen, Kill} = make_bb_transfer(Is, Succ),
+ case ?CODE:is_phi(I) of
+ true ->
+ InstrKill = set_from_list(?CODE:defines(I)),
+ Gen1 = set_subtract(Gen, InstrKill),
+ Kill1 = set_union(Kill, InstrKill),
+ {Gen1, Kill1};
+ false ->
+ InstrGen = set_from_list(?CODE:uses(I)),
+ InstrKill = set_from_list(?CODE:defines(I)),
+ Gen1 = set_subtract(Gen, InstrKill),
+ Gen2 = set_union(Gen1, InstrGen),
+ Kill1 = set_union(Kill, InstrKill),
+ Kill2 = set_subtract(Kill1, InstrGen),
+ {Gen2, Kill2}
+ end.
+
+get_directed_gen(Code) ->
+ Map = get_directed_gen_1(Code),
+ TotalGen = lists:foldl(fun({_Pred, Gen}, Acc) ->
+ set_union(Gen, Acc)
+ end, new_set(), gb_trees:to_list(Map)),
+ {TotalGen, Map}.
+
+get_directed_gen_1([I|Left])->
+ case ?CODE:is_phi(I) of
+ false ->
+ gb_trees:empty();
+ true ->
+ Map = get_directed_gen_1(Left),
+ ArgList = ?CODE:phi_arglist(I),
+ lists:foldl(fun update_directed_gen/2, Map, ArgList)
+ end.
+
+update_directed_gen({Pred, Var}, Map)->
+ case gb_trees:lookup(Pred, Map) of
+ none -> gb_trees:insert(Pred, set_from_list([Var]), Map);
+ {value, Set} -> gb_trees:update(Pred, set_add(Var, Set), Map)
+ end.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% liveness
+%%
+
+liveness_init(List) ->
+ liveness_init1(List, gb_trees:empty()).
+
+liveness_init1([{Label, Info}|Left], Map) ->
+ liveness_init1(Left, gb_trees:insert(Label, Info, Map));
+liveness_init1([], Map) ->
+ Map.
+
+liveness_lookup(Label, Map) ->
+ {value, Info} = gb_trees:lookup(Label, Map),
+ Info.
+
+liveness_update(Label, NewInfo, Map) ->
+ gb_trees:update(Label, NewInfo, Map).
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Sets
+%%
+
+new_set() ->
+ gb_sets:empty().
+
+set_union(S1, S2) ->
+ gb_sets:union(S1, S2).
+
+set_subtract(S1, S2) ->
+ gb_sets:subtract(S1, S2).
+
+set_from_list(List) ->
+ gb_sets:from_list(List).
+
+set_to_list(Set) ->
+ gb_sets:to_list(Set).
+
+set_add(Var, Set) ->
+ gb_sets:add(Var, Set).
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Pretty printer
+%%
+
+-ifdef(DEBUG_LIVENESS).
+
+pp_liveness(CFG) ->
+ io:format("Liveness for ~p:\n", [?CFG:function(CGF)]),
+ Liveness = analyze(CFG),
+ RevPostorder = lists:reverse(?CFG:postorder(CFG)),
+ Edges = [{X, Y} || X <- RevPostorder, Y <- ?CFG:succ(CFG, X)],
+ pp_liveness_edges(Edges, Liveness).
+
+pp_liveness_edges([{From, To}|Left], Liveness)->
+ LiveIn = livein(Liveness, To, From),
+ io:format("Label ~w -> Label ~w: ~p\n", [From, To, LiveIn]),
+ LiveOut = liveout(Liveness, From),
+ io:format("Total live out from Label ~w: ~p\n", [From, LiveOut]),
+ pp_liveness_edges(Left, Liveness);
+pp_liveness_edges([], _Liveness) ->
+ ok.
+
+-endif.