aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/ssa/hipe_ssa_copy_prop.inc
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/ssa/hipe_ssa_copy_prop.inc')
-rw-r--r--lib/hipe/ssa/hipe_ssa_copy_prop.inc198
1 files changed, 198 insertions, 0 deletions
diff --git a/lib/hipe/ssa/hipe_ssa_copy_prop.inc b/lib/hipe/ssa/hipe_ssa_copy_prop.inc
new file mode 100644
index 0000000000..311940a1fc
--- /dev/null
+++ b/lib/hipe/ssa/hipe_ssa_copy_prop.inc
@@ -0,0 +1,198 @@
+%%% -*- Erlang -*-
+%%% -*- erlang-indent-level: 2 -*-
+%%%
+%%% %CopyrightBegin%
+%%%
+%%% Copyright Ericsson AB 2003-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_ssa_copy_prop.inc
+%%% Author : Tobias Lindahl <[email protected]>
+%%% Description : Copy propagation on SSA form.
+%%%
+%%% Created : 4 Apr 2003 by Tobias Lindahl <[email protected]>
+%%%-------------------------------------------------------------------
+
+-export([cfg/1]).
+
+%%--------------------------------------------------------------------
+%% Two passes through the code visiting the blocks in reverse
+%% postorder. The first pass binds all destinations of copying moves
+%% to the sources, and the second propagates the copies and removes
+%% the copying moves.
+%%
+%% Problem:
+%% Since phi-nodes are implemented as instructions they are not
+%% atomic. If we are not careful we can get the situation (after propagation):
+%%
+%% v0 = phi(v0, v2)
+%% v1 = phi(v0, v3)
+%% ^^
+%% where the underlined v0 really corresponds to the v0 before the first
+%% phi-instruction.
+%%
+%% Solution:
+%% * Find all dependencies between the uses of a phi-instruction to
+%% the destination of any earlier phi-instruction in the same phi-node;
+%% * Keep the copying move that defines the variable used in the
+%% latter phi-instruction; and
+%% * Do not propagate the copy into the phi-instruction
+%%
+%%--------------------------------------------------------------------
+
+-spec cfg(#cfg{}) -> #cfg{}.
+
+cfg(Cfg) ->
+ Labels = ?cfg:reverse_postorder(Cfg),
+ {Info,PhiDep} = analyse(Labels, Cfg, gb_trees:empty(), gb_trees:empty()),
+ rewrite(Labels, Cfg, Info, PhiDep).
+
+analyse([Label|Left], Cfg, Info, PhiDep) ->
+ BB = ?cfg:bb(Cfg, Label),
+ Code = hipe_bb:code(BB),
+ NewPhiDep = get_phi_dep(Code, gb_sets:empty(), PhiDep),
+ NewInfo = analyse_code(Code, Info),
+ analyse(Left, Cfg, NewInfo, NewPhiDep);
+analyse([], _Cfg, Info, PhiDep) ->
+ {Info,PhiDep}.
+
+get_phi_dep([I|Left], Defined, Dep) ->
+ case ?code:is_phi(I) of
+ true ->
+ Use = ?code:uses(I),
+ [Def] = ?code:defines(I),
+ NewDep = add_dep(Use, Defined, Dep),
+ get_phi_dep(Left, gb_sets:insert(Def, Defined), NewDep);
+ false ->
+ Dep
+ end;
+get_phi_dep([], _Defined, Dep) ->
+ Dep.
+
+add_dep([Use|Left], Defined, Dep) ->
+ case gb_trees:lookup(Use, Dep) of
+ none ->
+ add_dep(Left, Defined, gb_trees:insert(Use, Defined, Dep));
+ {value, Set} ->
+ NewSet = gb_sets:union(Defined, Set),
+ add_dep(Left, Defined, gb_trees:enter(Use, NewSet, Dep))
+ end;
+add_dep([], _Defined, Dep) ->
+ Dep.
+
+has_dep(Use, Def, Dep) ->
+ case gb_trees:lookup(Use, Dep) of
+ none ->
+ false;
+ {value, Set} ->
+ gb_sets:is_member(Def, Set)
+ end.
+
+analyse_code([I|Left], Info) ->
+ case ?code:is_move(I) of
+ true ->
+ NewInfo = get_info_move(I, Info),
+ analyse_code(Left, NewInfo);
+ false ->
+ analyse_code(Left, Info)
+ end;
+analyse_code([], Info) ->
+ Info.
+
+get_info_move(I, Info) ->
+ case ?code:uses(I) of
+ [] -> %% Constant.
+ Info;
+ [Src] ->
+ add_binding(?code:defines(I), Src, Info)
+ end.
+
+rewrite([Label|Left], Cfg, Info, PhiDep) ->
+ BB = ?cfg:bb(Cfg, Label),
+ Code = hipe_bb:code(BB),
+ NewCode = rewrite_code(Code, Info, PhiDep, []),
+ NewBB = hipe_bb:code_update(BB, NewCode),
+ rewrite(Left, ?cfg:bb_add(Cfg, Label, NewBB), Info, PhiDep);
+rewrite([], Cfg, _Info, _PhiDep) ->
+ Cfg.
+
+rewrite_code([I|Left], Info, PhiDep, Acc) ->
+ case ?code:is_move(I) of
+ true ->
+ Fun = fun(X, Y) -> ?code:mk_move(X, Y) end,
+ NewI = rewrite_move(I, Fun, Info, PhiDep),
+ rewrite_code(Left, Info, PhiDep, NewI++Acc);
+ false ->
+ NewI = rewrite_instr(I, Info, PhiDep),
+ rewrite_code(Left, Info, PhiDep, [NewI|Acc])
+ end;
+rewrite_code([], _Info, _PhiDep, Acc) ->
+ lists:reverse(Acc).
+
+rewrite_move(I, Fun, Info, PhiDep) ->
+ case ?code:uses(I) of
+ [] ->%% Constant move. Keep it!
+ [I];
+ _ ->
+ Dst = hd(?code:defines(I)),
+ case gb_trees:lookup(Dst, Info) of
+ {value, Root} ->
+ case has_dep(Dst, Root, PhiDep) of
+ true -> %% Must keep the copying move!
+ [Fun(Dst, Root)];
+ false ->
+ []
+ end;
+ none ->
+ []
+ end
+ end.
+
+rewrite_instr(I, Info, PhiDep) ->
+ rewrite_instr0(I, ?code:uses(I), Info, PhiDep, []).
+
+rewrite_instr0(I, [Key|Left], Info, PhiDep, UpdateInfo) ->
+ case gb_trees:lookup(Key, Info) of
+ none ->
+ rewrite_instr0(I, Left, Info, PhiDep, UpdateInfo);
+ {value, Root} ->
+ case gb_trees:lookup(Key, Info) of
+ {value, Root} ->
+ case has_dep(Key, Root, PhiDep) of
+ true -> %% Must keep Key!
+ rewrite_instr0(I, Left, Info, PhiDep, UpdateInfo);
+ false ->
+ rewrite_instr0(I, Left, Info, PhiDep, [{Key, Root}|UpdateInfo])
+ end;
+ _ ->
+ rewrite_instr0(I, Left, Info, PhiDep, UpdateInfo)
+ end
+ end;
+rewrite_instr0(I, [], _Info, _PhiDep, UpdateInfo) ->
+ ?code:subst(UpdateInfo, I).
+
+add_binding([Key|Left], Val, Info) ->
+ %% Make sure the key is bound to the end of any copy-chains.
+ NewInfo =
+ case gb_trees:lookup(Val, Info) of
+ {value, NewVal} ->
+ gb_trees:insert(Key, NewVal, Info);
+ none ->
+ gb_trees:insert(Key, Val, Info)
+ end,
+ add_binding(Left, Val, NewInfo);
+add_binding([], _, Info) ->
+ Info.
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-08 12:02:29 +0000