The R13B03 release.OTP_R13B03

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.