%%% -*- Erlang -*-
%%% -*- erlang-indent-level: 2 -*-
%%%
%%% Licensed under the Apache License, Version 2.0 (the "License");
%%% you may not use this file except in compliance with the License.
%%% You may obtain a copy of the License at
%%%
%%% http://www.apache.org/licenses/LICENSE-2.0
%%%
%%% Unless required by applicable law or agreed to in writing, software
%%% distributed under the License is distributed on an "AS IS" BASIS,
%%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%%% See the License for the specific language governing permissions and
%%% limitations under the License.
%%%
%%%-------------------------------------------------------------------
%%% File : hipe_ssa_copy_prop.inc
%%% Author : Tobias Lindahl <tobiasl@it.uu.se>
%%% Description : Copy propagation on SSA form.
%%%
%%% Created : 4 Apr 2003 by Tobias Lindahl <tobiasl@it.uu.se>
%%%-------------------------------------------------------------------
-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.
