%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 2018. All Rights Reserved.
%%
%% 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.
%%
%% %CopyrightEnd%
%%
%% Purpose: Type definitions and utilities for the SSA format.
-module(beam_ssa).
-export([add_anno/3,get_anno/2,get_anno/3,
clobbers_xregs/1,def/2,def_unused/3,
definitions/1,
dominators/1,common_dominators/3,
flatmapfold_instrs_rpo/4,
fold_po/3,fold_po/4,fold_rpo/3,fold_rpo/4,
fold_instrs_rpo/4,
linearize/1,
mapfold_blocks_rpo/4,
mapfold_instrs_rpo/4,
normalize/1,
no_side_effect/1,
predecessors/1,
rename_vars/3,
rpo/1,rpo/2,
split_blocks/3,
successors/1,successors/2,
trim_unreachable/1,
update_phi_labels/4,used/1,
uses/1,uses/2]).
-export_type([b_module/0,b_function/0,b_blk/0,b_set/0,
b_ret/0,b_br/0,b_switch/0,terminator/0,
b_var/0,b_literal/0,b_remote/0,b_local/0,
value/0,argument/0,label/0,
var_name/0,var_base/0,literal_value/0,
op/0,anno/0,block_map/0,dominator_map/0,
rename_map/0,rename_proplist/0,usage_map/0,
definition_map/0]).
-include("beam_ssa.hrl").
-type b_module() :: #b_module{}.
-type b_function() :: #b_function{}.
-type b_blk() :: #b_blk{}.
-type b_set() :: #b_set{}.
-type b_br() :: #b_br{}.
-type b_ret() :: #b_ret{}.
-type b_switch() :: #b_switch{}.
-type terminator() :: b_br() | b_ret() | b_switch().
-type construct() :: b_module() | b_function() | b_blk() | b_set() |
terminator().
-type b_var() :: #b_var{}.
-type b_literal() :: #b_literal{}.
-type b_remote() :: #b_remote{}.
-type b_local() :: #b_local{}.
-type value() :: b_var() | b_literal().
-type phi_value() :: {value(),label()}.
-type argument() :: value() | b_remote() | b_local() | phi_value().
-type label() :: non_neg_integer().
-type var_name() :: var_base() | {var_base(),non_neg_integer()}.
-type var_base() :: atom() | non_neg_integer().
-type literal_value() :: atom() | integer() | float() | list() |
nil() | tuple() | map() | binary() | fun().
-type op() :: {'bif',atom()} | {'float',float_op()} | prim_op() | cg_prim_op().
-type anno() :: #{atom() := any()}.
-type block_map() :: #{label():=b_blk()}.
-type dominator_map() :: #{label():=[label()]}.
-type numbering_map() :: #{label():=non_neg_integer()}.
-type usage_map() :: #{b_var():=[{label(),b_set() | terminator()}]}.
-type definition_map() :: #{b_var():=b_set()}.
-type rename_map() :: #{b_var():=value()}.
-type rename_proplist() :: [{b_var(),value()}].
%% Note: By default, dialyzer will collapse this type to atom().
%% To avoid the collapsing, change the value of SET_LIMIT to 50 in the
%% file erl_types.erl in the hipe application.
-type prim_op() :: 'bs_add' | 'bs_extract' | 'bs_get_tail' |
'bs_init' | 'bs_init_writable' |
'bs_match' | 'bs_put' | 'bs_start_match' | 'bs_test_tail' |
'bs_utf16_size' | 'bs_utf8_size' | 'build_stacktrace' |
'call' | 'catch_end' |
'extract' | 'exception_trampoline' |
'get_hd' | 'get_map_element' | 'get_tl' | 'get_tuple_element' |
'has_map_field' |
'is_nonempty_list' | 'is_tagged_tuple' |
'kill_try_tag' |
'landingpad' |
'make_fun' | 'new_try_tag' |
'peek_message' | 'phi' | 'put_list' | 'put_map' | 'put_tuple' |
'raw_raise' | 'recv_next' | 'remove_message' | 'resume' |
'succeeded' |
'timeout' |
'wait' | 'wait_timeout'.
-type float_op() :: 'checkerror' | 'clearerror' | 'convert' | 'get' | 'put' |
'+' | '-' | '*' | '/'.
%% Primops only used internally during code generation.
-type cg_prim_op() :: 'bs_get' | 'bs_get_position' | 'bs_match_string' |
'bs_restore' | 'bs_save' | 'bs_set_position' | 'bs_skip' |
'copy' | 'match_fail' | 'put_tuple_arity' |
'put_tuple_element' | 'put_tuple_elements' |
'set_tuple_element'.
-import(lists, [foldl/3,keyfind/3,mapfoldl/3,member/2,reverse/1]).
-spec add_anno(Key, Value, Construct) -> Construct when
Key :: atom(),
Value :: any(),
Construct :: construct().
add_anno(Key, Val, #b_function{anno=Anno}=Bl) ->
Bl#b_function{anno=Anno#{Key=>Val}};
add_anno(Key, Val, #b_blk{anno=Anno}=Bl) ->
Bl#b_blk{anno=Anno#{Key=>Val}};
add_anno(Key, Val, #b_set{anno=Anno}=Bl) ->
Bl#b_set{anno=Anno#{Key=>Val}};
add_anno(Key, Val, #b_br{anno=Anno}=Bl) ->
Bl#b_br{anno=Anno#{Key=>Val}};
add_anno(Key, Val, #b_ret{anno=Anno}=Bl) ->
Bl#b_ret{anno=Anno#{Key=>Val}};
add_anno(Key, Val, #b_switch{anno=Anno}=Bl) ->
Bl#b_switch{anno=Anno#{Key=>Val}}.
-spec get_anno(atom(), construct()) -> any().
get_anno(Key, Construct) ->
map_get(Key, get_anno(Construct)).
-spec get_anno(atom(), construct(),any()) -> any().
get_anno(Key, Construct, Default) ->
maps:get(Key, get_anno(Construct), Default).
get_anno(#b_function{anno=Anno}) -> Anno;
get_anno(#b_blk{anno=Anno}) -> Anno;
get_anno(#b_set{anno=Anno}) -> Anno;
get_anno(#b_br{anno=Anno}) -> Anno;
get_anno(#b_ret{anno=Anno}) -> Anno;
get_anno(#b_switch{anno=Anno}) -> Anno.
%% clobbers_xregs(#b_set{}) -> true|false.
%% Test whether the instruction invalidates all X registers.
-spec clobbers_xregs(b_set()) -> boolean().
clobbers_xregs(#b_set{op=Op}) ->
case Op of
bs_init_writable -> true;
build_stacktrace -> true;
call -> true;
landingpad -> true;
make_fun -> true;
peek_message -> true;
raw_raise -> true;
_ -> false
end.
%% no_side_effect(#b_set{}) -> true|false.
%% Test whether this instruction has no side effect and thus is safe
%% not to execute if its value is not used. Note that even if `true`
%% is returned, the instruction could still be impure (e.g. bif:get).
-spec no_side_effect(b_set()) -> boolean().
no_side_effect(#b_set{op=Op}) ->
case Op of
{bif,_} -> true;
{float,get} -> true;
bs_init -> true;
bs_extract -> true;
bs_match -> true;
bs_start_match -> true;
bs_test_tail -> true;
bs_get_tail -> true;
bs_put -> true;
extract -> true;
get_hd -> true;
get_tl -> true;
get_map_element -> true;
get_tuple_element -> true;
has_map_field -> true;
is_nonempty_list -> true;
is_tagged_tuple -> true;
make_fun -> true;
put_map -> true;
put_list -> true;
put_tuple -> true;
succeeded -> true;
_ -> false
end.
-spec predecessors(Blocks) -> #{BlockNumber:=[Predecessor]} when
Blocks :: block_map(),
BlockNumber :: label(),
Predecessor :: label().
predecessors(Blocks) ->
P0 = [{S,L} || {L,Blk} <- maps:to_list(Blocks),
S <- successors(Blk)],
P1 = sofs:relation(P0),
P2 = sofs:rel2fam(P1),
P3 = sofs:to_external(P2),
P = [{0,[]}|P3],
maps:from_list(P).
-spec successors(b_blk()) -> [label()].
successors(#b_blk{last=Terminator}) ->
case Terminator of
#b_br{bool=#b_literal{val=true},succ=Succ} ->
[Succ];
#b_br{bool=#b_literal{val=false},fail=Fail} ->
[Fail];
#b_br{succ=Succ,fail=Fail} ->
[Fail,Succ];
#b_switch{fail=Fail,list=List} ->
[Fail|[L || {_,L} <- List]];
#b_ret{} ->
[]
end.
%% normalize(Instr0) -> Instr.
%% Normalize instructions to help optimizations.
%%
%% For commutative operators (such as '+' and 'or'), always
%% place a variable operand before a literal operand.
%%
%% Normalize #b_br{} to one of the following forms:
%%
%% #b_br{b_literal{val=true},succ=Label,fail=Label}
%% #b_br{b_var{},succ=Label1,fail=Label2} where Label1 =/= Label2
%%
%% Simplify a #b_switch{} with a literal argument to a #b_br{}.
%%
%% Simplify a #b_switch{} with a variable argument and an empty
%% switch list to a #b_br{}.
-spec normalize(b_set() | terminator()) ->
b_set() | terminator().
normalize(#b_set{op={bif,Bif},args=Args}=Set) ->
case {is_commutative(Bif),Args} of
{false,_} ->
Set;
{true,[#b_literal{}=Lit,#b_var{}=Var]} ->
Set#b_set{args=[Var,Lit]};
{true,_} ->
Set
end;
normalize(#b_set{}=Set) ->
Set;
normalize(#b_br{}=Br) ->
case Br of
#b_br{bool=Bool,succ=Same,fail=Same} ->
case Bool of
#b_literal{val=true} ->
Br;
_ ->
Br#b_br{bool=#b_literal{val=true}}
end;
#b_br{bool=#b_literal{val=true},succ=Succ} ->
Br#b_br{fail=Succ};
#b_br{bool=#b_literal{val=false},fail=Fail} ->
Br#b_br{bool=#b_literal{val=true},succ=Fail};
#b_br{} ->
Br
end;
normalize(#b_switch{arg=Arg,fail=Fail,list=List}=Sw) ->
case Arg of
#b_literal{} ->
case keyfind(Arg, 1, List) of
false ->
#b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail};
{Arg,L} ->
#b_br{bool=#b_literal{val=true},succ=L,fail=L}
end;
#b_var{} when List =:= [] ->
#b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail};
#b_var{} ->
Sw
end;
normalize(#b_ret{}=Ret) ->
Ret.
-spec successors(label(), block_map()) -> [label()].
successors(L, Blocks) ->
successors(map_get(L, Blocks)).
-spec def(Ls, Blocks) -> Def when
Ls :: [label()],
Blocks :: block_map(),
Def :: ordsets:ordset(var_name()).
def(Ls, Blocks) ->
Top = rpo(Ls, Blocks),
Blks = [map_get(L, Blocks) || L <- Top],
def_1(Blks, []).
-spec def_unused(Ls, Used, Blocks) -> {Def,Unused} when
Ls :: [label()],
Used :: ordsets:ordset(var_name()),
Blocks :: block_map(),
Def :: ordsets:ordset(var_name()),
Unused :: ordsets:ordset(var_name()).
def_unused(Ls, Unused, Blocks) ->
Top = rpo(Ls, Blocks),
Blks = [map_get(L, Blocks) || L <- Top],
Preds = cerl_sets:from_list(Top),
def_unused_1(Blks, Preds, [], Unused).
%% dominators(BlockMap) -> {Dominators,Numbering}.
%% Calculate the dominator tree, returning a map where each entry
%% in the map is a list that gives the path from that block to
%% the top of the dominator tree. (Note that the suffixes of the
%% paths are shared with each other, which make the representation
%% of the dominator tree highly memory-efficient.)
%%
%% The implementation is based on:
%%
%% http://www.hipersoft.rice.edu/grads/publications/dom14.pdf
%% Cooper, Keith D.; Harvey, Timothy J; Kennedy, Ken (2001).
%% A Simple, Fast Dominance Algorithm.
-spec dominators(Blocks) -> Result when
Blocks :: block_map(),
Result :: {dominator_map(), numbering_map()}.
dominators(Blocks) ->
Preds = predecessors(Blocks),
Top0 = rpo(Blocks),
Df = maps:from_list(number(Top0, 0)),
[{0,[]}|Top] = [{L,map_get(L, Preds)} || L <- Top0],
%% The flow graph for an Erlang function is reducible, and
%% therefore one traversal in reverse postorder is sufficient.
Acc = #{0=>[0]},
{dominators_1(Top, Df, Acc),Df}.
%% common_dominators([Label], Dominators, Numbering) -> [Label].
%% Calculate the common dominators for the given list of blocks
%% and Dominators and Numbering as returned from dominators/1.
-spec common_dominators([label()], dominator_map(), numbering_map()) -> [label()].
common_dominators(Ls, Dom, Numbering) ->
Doms = [map_get(L, Dom) || L <- Ls],
dom_intersection(Doms, Numbering).
-spec fold_instrs_rpo(Fun, From, Acc0, Blocks) -> any() when
Fun :: fun((b_blk()|terminator(), any()) -> any()),
From :: [label()],
Acc0 :: any(),
Blocks :: block_map().
fold_instrs_rpo(Fun, From, Acc0, Blocks) ->
Top = rpo(From, Blocks),
fold_instrs_rpo_1(Top, Fun, Blocks, Acc0).
%% Like mapfold_instrs_rpo but at the block level to support lookahead and
%% scope-dependent transformations.
-spec mapfold_blocks_rpo(Fun, From, Acc, Blocks) -> Result when
Fun :: fun((label(), b_blk(), any()) -> {b_blk(), any()}),
From :: [label()],
Acc :: any(),
Blocks :: block_map(),
Result :: {block_map(), any()}.
mapfold_blocks_rpo(Fun, From, Acc, Blocks) ->
Successors = rpo(From, Blocks),
foldl(fun(Lbl, A) ->
mapfold_blocks_rpo_1(Fun, Lbl, A)
end, {Blocks, Acc}, Successors).
mapfold_blocks_rpo_1(Fun, Lbl, {Blocks0, Acc0}) ->
Block0 = map_get(Lbl, Blocks0),
{Block, Acc} = Fun(Lbl, Block0, Acc0),
Blocks = Blocks0#{Lbl:=Block},
{Blocks, Acc}.
-spec mapfold_instrs_rpo(Fun, From, Acc0, Blocks0) -> {Blocks,Acc} when
Fun :: fun((b_blk()|terminator(), any()) -> any()),
From :: [label()],
Acc0 :: any(),
Acc :: any(),
Blocks0 :: block_map(),
Blocks :: block_map().
mapfold_instrs_rpo(Fun, From, Acc0, Blocks) ->
Top = rpo(From, Blocks),
mapfold_instrs_rpo_1(Top, Fun, Blocks, Acc0).
-spec flatmapfold_instrs_rpo(Fun, From, Acc0, Blocks0) -> {Blocks,Acc} when
Fun :: fun((b_blk()|terminator(), any()) -> any()),
From :: [label()],
Acc0 :: any(),
Acc :: any(),
Blocks0 :: block_map(),
Blocks :: block_map().
flatmapfold_instrs_rpo(Fun, From, Acc0, Blocks) ->
Top = rpo(From, Blocks),
flatmapfold_instrs_rpo_1(Top, Fun, Blocks, Acc0).
-type fold_fun() :: fun((label(), b_blk(), any()) -> any()).
%% fold_rpo(Fun, [Label], Acc0, Blocks) -> Acc.
%% Fold over all blocks a reverse postorder traversal of the block
%% graph; that is, first visit a block, then visit its successors.
-spec fold_rpo(Fun, Acc0, Blocks) -> any() when
Fun :: fold_fun(),
Acc0 :: any(),
Blocks :: #{label():=b_blk()}.
fold_rpo(Fun, Acc0, Blocks) ->
fold_rpo(Fun, [0], Acc0, Blocks).
%% fold_rpo(Fun, [Label], Acc0, Blocks) -> Acc. Fold over all blocks
%% reachable from a given set of labels in a reverse postorder
%% traversal of the block graph; that is, first visit a block, then
%% visit its successors.
-spec fold_rpo(Fun, Labels, Acc0, Blocks) -> any() when
Fun :: fold_fun(),
Labels :: [label()],
Acc0 :: any(),
Blocks :: #{label():=b_blk()}.
fold_rpo(Fun, From, Acc0, Blocks) ->
Top = rpo(From, Blocks),
fold_rpo_1(Top, Fun, Blocks, Acc0).
%% fold_po(Fun, Acc0, Blocks) -> Acc.
%% Fold over all blocks in a postorder traversal of the block graph;
%% that is, first visit all successors of block, then the block
%% itself.
-spec fold_po(Fun, Acc0, Blocks) -> any() when
Fun :: fold_fun(),
Acc0 :: any(),
Blocks :: #{label():=b_blk()}.
%% fold_po(Fun, From, Acc0, Blocks) -> Acc.
%% Fold over the blocks reachable from the block numbers given
%% by From in a postorder traversal of the block graph.
fold_po(Fun, Acc0, Blocks) ->
fold_po(Fun, [0], Acc0, Blocks).
-spec fold_po(Fun, Labels, Acc0, Blocks) -> any() when
Fun :: fold_fun(),
Labels :: [label()],
Acc0 :: any(),
Blocks :: block_map().
fold_po(Fun, From, Acc0, Blocks) ->
Top = reverse(rpo(From, Blocks)),
fold_rpo_1(Top, Fun, Blocks, Acc0).
%% linearize(Blocks) -> [{BlockLabel,#b_blk{}}].
%% Linearize the intermediate representation of the code.
%% Unreachable blocks will be discarded, and phi nodes will
%% be adjusted so that they no longer refers to discarded
%% blocks or to blocks that no longer are predecessors of
%% the phi node block.
-spec linearize(Blocks) -> Linear when
Blocks :: block_map(),
Linear :: [{label(),b_blk()}].
linearize(Blocks) ->
Seen = cerl_sets:new(),
{Linear0,_} = linearize_1([0], Blocks, Seen, []),
Linear = fix_phis(Linear0, #{}),
Linear.
-spec rpo(Blocks) -> [Label] when
Blocks :: block_map(),
Label :: label().
rpo(Blocks) ->
rpo([0], Blocks).
-spec rpo(From, Blocks) -> Labels when
From :: [label()],
Blocks :: block_map(),
Labels :: [label()].
rpo(From, Blocks) ->
Seen = cerl_sets:new(),
{Ls,_} = rpo_1(From, Blocks, Seen, []),
Ls.
-spec rename_vars(Rename, [label()], block_map()) -> block_map() when
Rename :: rename_map() | rename_proplist().
rename_vars(Rename, From, Blocks) when is_list(Rename) ->
rename_vars(maps:from_list(Rename), From, Blocks);
rename_vars(Rename, From, Blocks) when is_map(Rename)->
Top = rpo(From, Blocks),
Preds = cerl_sets:from_list(Top),
F = fun(#b_set{op=phi,args=Args0}=Set) ->
Args = rename_phi_vars(Args0, Preds, Rename),
Set#b_set{args=Args};
(#b_set{args=Args0}=Set) ->
Args = [rename_var(A, Rename) || A <- Args0],
Set#b_set{args=Args};
(#b_switch{arg=Bool}=Sw) ->
Sw#b_switch{arg=rename_var(Bool, Rename)};
(#b_br{bool=Bool}=Br) ->
Br#b_br{bool=rename_var(Bool, Rename)};
(#b_ret{arg=Arg}=Ret) ->
Ret#b_ret{arg=rename_var(Arg, Rename)}
end,
map_instrs_1(Top, F, Blocks).
%% split_blocks(Predicate, Blocks0, Count0) -> {Blocks,Count}.
%% Call Predicate(Instruction) for each instruction in all
%% blocks. If Predicate/1 returns true, split the block
%% before this instruction.
-spec split_blocks(Pred, Blocks0, Count0) -> {Blocks,Count} when
Pred :: fun((b_set()) -> boolean()),
Blocks :: block_map(),
Count0 :: beam_ssa:label(),
Blocks0 :: block_map(),
Blocks :: block_map(),
Count :: beam_ssa:label().
split_blocks(P, Blocks, Count) ->
Ls = beam_ssa:rpo(Blocks),
split_blocks_1(Ls, P, Blocks, Count).
-spec trim_unreachable(Blocks0) -> Blocks when
Blocks0 :: block_map(),
Blocks :: block_map().
%% trim_unreachable(Blocks0) -> Blocks.
%% Remove all unreachable blocks. Adjust all phi nodes so
%% they don't refer to blocks that has been removed or no
%% no longer branch to the phi node in question.
trim_unreachable(Blocks) ->
%% Could perhaps be optimized if there is any need.
maps:from_list(linearize(Blocks)).
%% update_phi_labels([BlockLabel], Old, New, Blocks0) -> Blocks.
%% In the given blocks, replace label Old in with New in all
%% phi nodes. This is useful after merging or splitting
%% blocks.
-spec update_phi_labels(From, Old, New, Blocks0) -> Blocks when
From :: [label()],
Old :: label(),
New :: label(),
Blocks0 :: block_map(),
Blocks :: block_map().
update_phi_labels([L|Ls], Old, New, Blocks0) ->
case Blocks0 of
#{L:=#b_blk{is=[#b_set{op=phi}|_]=Is0}=Blk0} ->
Is = update_phi_labels_is(Is0, Old, New),
Blk = Blk0#b_blk{is=Is},
Blocks = Blocks0#{L:=Blk},
update_phi_labels(Ls, Old, New, Blocks);
#{L:=#b_blk{}} ->
%% No phi nodes in this block.
update_phi_labels(Ls, Old, New, Blocks0)
end;
update_phi_labels([], _, _, Blocks) -> Blocks.
-spec used(b_blk() | b_set() | terminator()) -> [var_name()].
used(#b_blk{is=Is,last=Last}) ->
used_1([Last|Is], ordsets:new());
used(#b_br{bool=#b_var{}=V}) ->
[V];
used(#b_ret{arg=#b_var{}=V}) ->
[V];
used(#b_set{op=phi,args=Args}) ->
ordsets:from_list([V || {#b_var{}=V,_} <- Args]);
used(#b_set{args=Args}) ->
ordsets:from_list(used_args(Args));
used(#b_switch{arg=#b_var{}=V}) ->
[V];
used(_) -> [].
-spec definitions(Blocks :: block_map()) -> definition_map().
definitions(Blocks) ->
fold_instrs_rpo(fun(#b_set{ dst = Var }=I, Acc) ->
Acc#{Var => I};
(_Terminator, Acc) ->
Acc
end, [0], #{}, Blocks).
-spec uses(Blocks :: block_map()) -> usage_map().
uses(Blocks) ->
uses([0], Blocks).
-spec uses(From, Blocks) -> usage_map() when
From :: [label()],
Blocks :: block_map().
uses(From, Blocks) ->
fold_rpo(fun fold_uses_block/3, From, #{}, Blocks).
fold_uses_block(Lbl, #b_blk{is=Is,last=Last}, UseMap0) ->
F = fun(I, UseMap) ->
foldl(fun(Var, Acc) ->
Uses0 = maps:get(Var, Acc, []),
Uses = [{Lbl, I} | Uses0],
maps:put(Var, Uses, Acc)
end, UseMap, used(I))
end,
F(Last, foldl(F, UseMap0, Is)).
%%%
%%% Internal functions.
%%%
is_commutative('and') -> true;
is_commutative('or') -> true;
is_commutative('xor') -> true;
is_commutative('band') -> true;
is_commutative('bor') -> true;
is_commutative('bxor') -> true;
is_commutative('+') -> true;
is_commutative('*') -> true;
is_commutative('=:=') -> true;
is_commutative('==') -> true;
is_commutative('=/=') -> true;
is_commutative('/=') -> true;
is_commutative(_) -> false.
def_unused_1([#b_blk{is=Is,last=Last}|Bs], Preds, Def0, Unused0) ->
Unused1 = ordsets:subtract(Unused0, used(Last)),
{Def,Unused} = def_unused_is(Is, Preds, Def0, Unused1),
def_unused_1(Bs, Preds, Def, Unused);
def_unused_1([], _Preds, Def, Unused) ->
{ordsets:from_list(Def), Unused}.
def_unused_is([#b_set{op=phi,dst=Dst,args=Args}|Is],
Preds, Def0, Unused0) ->
Def = [Dst|Def0],
%% We must be careful to only include variables that will
%% be used when arriving from one of the predecessor blocks
%% in Preds.
Unused1 = [V || {#b_var{}=V,L} <- Args, cerl_sets:is_element(L, Preds)],
Unused = ordsets:subtract(Unused0, ordsets:from_list(Unused1)),
def_unused_is(Is, Preds, Def, Unused);
def_unused_is([#b_set{dst=Dst}=I|Is], Preds, Def0, Unused0) ->
Def = [Dst|Def0],
Unused = ordsets:subtract(Unused0, used(I)),
def_unused_is(Is, Preds, Def, Unused);
def_unused_is([], _Preds, Def, Unused) ->
{Def,Unused}.
def_1([#b_blk{is=Is}|Bs], Def0) ->
Def = def_is(Is, Def0),
def_1(Bs, Def);
def_1([], Def) ->
ordsets:from_list(Def).
def_is([#b_set{dst=Dst}|Is], Def) ->
def_is(Is, [Dst|Def]);
def_is([], Def) -> Def.
dominators_1([{L,Preds}|Ls], Df, Doms) ->
DomPreds = [map_get(P, Doms) || P <- Preds, is_map_key(P, Doms)],
Dom = [L|dom_intersection(DomPreds, Df)],
dominators_1(Ls, Df, Doms#{L=>Dom});
dominators_1([], _Df, Doms) -> Doms.
dom_intersection([S], _Df) ->
S;
dom_intersection([S|Ss], Df) ->
dom_intersection(S, Ss, Df).
dom_intersection(S1, [S2|Ss], Df) ->
dom_intersection(dom_intersection_1(S1, S2, Df), Ss, Df);
dom_intersection(S, [], _Df) -> S.
dom_intersection_1([E1|Es1]=Set1, [E2|Es2]=Set2, Df) ->
%% Blocks are numbered in the order they are found in
%% reverse postorder.
#{E1:=Df1,E2:=Df2} = Df,
if Df1 > Df2 ->
dom_intersection_1(Es1, Set2, Df);
Df2 > Df1 ->
dom_intersection_1(Es2, Set1, Df); %switch arguments!
true -> %Set1 == Set2
%% The common suffix of the sets is the intersection.
Set1
end.
number([L|Ls], N) ->
[{L,N}|number(Ls, N+1)];
number([], _) -> [].
fold_rpo_1([L|Ls], Fun, Blocks, Acc0) ->
Block = map_get(L, Blocks),
Acc = Fun(L, Block, Acc0),
fold_rpo_1(Ls, Fun, Blocks, Acc);
fold_rpo_1([], _, _, Acc) -> Acc.
fold_instrs_rpo_1([L|Ls], Fun, Blocks, Acc0) ->
#b_blk{is=Is,last=Last} = map_get(L, Blocks),
Acc1 = foldl(Fun, Acc0, Is),
Acc = Fun(Last, Acc1),
fold_instrs_rpo_1(Ls, Fun, Blocks, Acc);
fold_instrs_rpo_1([], _, _, Acc) -> Acc.
mapfold_instrs_rpo_1([L|Ls], Fun, Blocks0, Acc0) ->
#b_blk{is=Is0,last=Last0} = Block0 = map_get(L, Blocks0),
{Is,Acc1} = mapfoldl(Fun, Acc0, Is0),
{Last,Acc} = Fun(Last0, Acc1),
Block = Block0#b_blk{is=Is,last=Last},
Blocks = Blocks0#{L:=Block},
mapfold_instrs_rpo_1(Ls, Fun, Blocks, Acc);
mapfold_instrs_rpo_1([], _, Blocks, Acc) ->
{Blocks,Acc}.
flatmapfold_instrs_rpo_1([L|Ls], Fun, Blocks0, Acc0) ->
#b_blk{is=Is0,last=Last0} = Block0 = map_get(L, Blocks0),
{Is,Acc1} = flatmapfoldl(Fun, Acc0, Is0),
{[Last],Acc} = Fun(Last0, Acc1),
Block = Block0#b_blk{is=Is,last=Last},
Blocks = Blocks0#{L:=Block},
flatmapfold_instrs_rpo_1(Ls, Fun, Blocks, Acc);
flatmapfold_instrs_rpo_1([], _, Blocks, Acc) ->
{Blocks,Acc}.
linearize_1([L|Ls], Blocks, Seen0, Acc0) ->
case cerl_sets:is_element(L, Seen0) of
true ->
linearize_1(Ls, Blocks, Seen0, Acc0);
false ->
Seen1 = cerl_sets:add_element(L, Seen0),
Block = map_get(L, Blocks),
Successors = successors(Block),
{Acc,Seen} = linearize_1(Successors, Blocks, Seen1, Acc0),
linearize_1(Ls, Blocks, Seen, [{L,Block}|Acc])
end;
linearize_1([], _, Seen, Acc) ->
{Acc,Seen}.
fix_phis([{L,Blk0}|Bs], S) ->
Blk = case Blk0 of
#b_blk{is=[#b_set{op=phi}|_]=Is0} ->
Is = fix_phis_1(Is0, L, S),
Blk0#b_blk{is=Is};
#b_blk{} ->
Blk0
end,
Successors = successors(Blk),
[{L,Blk}|fix_phis(Bs, S#{L=>Successors})];
fix_phis([], _) -> [].
fix_phis_1([#b_set{op=phi,args=Args0}=I|Is], L, S) ->
Args = [{Val,Pred} || {Val,Pred} <- Args0,
is_successor(L, Pred, S)],
[I#b_set{args=Args}|fix_phis_1(Is, L, S)];
fix_phis_1(Is, _, _) -> Is.
is_successor(L, Pred, S) ->
case S of
#{Pred:=Successors} ->
member(L, Successors);
#{} ->
%% This block has been removed.
false
end.
rpo_1([L|Ls], Blocks, Seen0, Acc0) ->
case cerl_sets:is_element(L, Seen0) of
true ->
rpo_1(Ls, Blocks, Seen0, Acc0);
false ->
Block = map_get(L, Blocks),
Seen1 = cerl_sets:add_element(L, Seen0),
Successors = successors(Block),
{Acc,Seen} = rpo_1(Successors, Blocks, Seen1, Acc0),
rpo_1(Ls, Blocks, Seen, [L|Acc])
end;
rpo_1([], _, Seen, Acc) ->
{Acc,Seen}.
rename_var(#b_var{}=Old, Rename) ->
case Rename of
#{Old:=New} -> New;
#{} -> Old
end;
rename_var(#b_remote{mod=Mod0,name=Name0}=Remote, Rename) ->
Mod = rename_var(Mod0, Rename),
Name = rename_var(Name0, Rename),
Remote#b_remote{mod=Mod,name=Name};
rename_var(Old, _) -> Old.
rename_phi_vars([{Var,L}|As], Preds, Ren) ->
case cerl_sets:is_element(L, Preds) of
true ->
[{rename_var(Var, Ren),L}|rename_phi_vars(As, Preds, Ren)];
false ->
[{Var,L}|rename_phi_vars(As, Preds, Ren)]
end;
rename_phi_vars([], _, _) -> [].
map_instrs_1([L|Ls], Fun, Blocks0) ->
#b_blk{is=Is0,last=Last0} = Blk0 = map_get(L, Blocks0),
Is = [Fun(I) || I <- Is0],
Last = Fun(Last0),
Blk = Blk0#b_blk{is=Is,last=Last},
Blocks = Blocks0#{L:=Blk},
map_instrs_1(Ls, Fun, Blocks);
map_instrs_1([], _, Blocks) -> Blocks.
flatmapfoldl(F, Accu0, [Hd|Tail]) ->
{R,Accu1} = F(Hd, Accu0),
{Rs,Accu2} = flatmapfoldl(F, Accu1, Tail),
{R++Rs,Accu2};
flatmapfoldl(_, Accu, []) -> {[],Accu}.
split_blocks_1([L|Ls], P, Blocks0, Count0) ->
#b_blk{is=Is0} = Blk = map_get(L, Blocks0),
case split_blocks_is(Is0, P, []) of
{yes,Bef,Aft} ->
NewLbl = Count0,
Count = Count0 + 1,
Br = #b_br{bool=#b_literal{val=true},succ=NewLbl,fail=NewLbl},
BefBlk = Blk#b_blk{is=Bef,last=Br},
NewBlk = Blk#b_blk{is=Aft},
Blocks1 = Blocks0#{L:=BefBlk,NewLbl=>NewBlk},
Successors = successors(NewBlk),
Blocks = update_phi_labels(Successors, L, NewLbl, Blocks1),
split_blocks_1([NewLbl|Ls], P, Blocks, Count);
no ->
split_blocks_1(Ls, P, Blocks0, Count0)
end;
split_blocks_1([], _, Blocks, Count) ->
{Blocks,Count}.
split_blocks_is([I|Is], P, []) ->
split_blocks_is(Is, P, [I]);
split_blocks_is([I|Is], P, Acc) ->
case P(I) of
true ->
{yes,reverse(Acc),[I|Is]};
false ->
split_blocks_is(Is, P, [I|Acc])
end;
split_blocks_is([], _, _) -> no.
update_phi_labels_is([#b_set{op=phi,args=Args0}=I0|Is], Old, New) ->
Args = [{Arg,rename_label(Lbl, Old, New)} || {Arg,Lbl} <- Args0],
I = I0#b_set{args=Args},
[I|update_phi_labels_is(Is, Old, New)];
update_phi_labels_is(Is, _, _) -> Is.
rename_label(Old, Old, New) -> New;
rename_label(Lbl, _Old, _New) -> Lbl.
used_args([#b_var{}=V|As]) ->
[V|used_args(As)];
used_args([#b_remote{mod=Mod,name=Name}|As]) ->
used_args([Mod,Name|As]);
used_args([_|As]) ->
used_args(As);
used_args([]) -> [].
used_1([H|T], Used0) ->
Used = ordsets:union(used(H), Used0),
used_1(T, Used);
used_1([], Used) -> Used.
