aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler
diff options
context:
space:
mode:
Diffstat (limited to 'lib/compiler')
-rw-r--r--lib/compiler/doc/src/notes.xml32
-rwxr-xr-xlib/compiler/scripts/smoke1
-rw-r--r--lib/compiler/scripts/smoke-mix.exs8
-rw-r--r--lib/compiler/src/beam_jump.erl8
-rw-r--r--lib/compiler/src/beam_kernel_to_ssa.erl10
-rw-r--r--lib/compiler/src/beam_ssa_dead.erl364
-rw-r--r--lib/compiler/src/beam_ssa_opt.erl124
-rw-r--r--lib/compiler/src/beam_ssa_type.erl3
-rw-r--r--lib/compiler/src/beam_validator.erl2144
-rw-r--r--lib/compiler/src/cerl_sets.erl2
-rw-r--r--lib/compiler/src/v3_kernel.erl85
-rw-r--r--lib/compiler/test/beam_except_SUITE.erl13
-rw-r--r--lib/compiler/test/beam_jump_SUITE.erl47
-rw-r--r--lib/compiler/test/beam_validator_SUITE.erl76
-rw-r--r--lib/compiler/test/beam_validator_SUITE_data/merge_undefined.S4
-rw-r--r--lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S4
-rw-r--r--lib/compiler/test/float_SUITE.erl23
-rw-r--r--lib/compiler/test/receive_SUITE.erl30
-rw-r--r--lib/compiler/vsn.mk2
19 files changed, 1817 insertions, 1163 deletions
diff --git a/lib/compiler/doc/src/notes.xml b/lib/compiler/doc/src/notes.xml
index 02e6203137..d45dfef8f3 100644
--- a/lib/compiler/doc/src/notes.xml
+++ b/lib/compiler/doc/src/notes.xml
@@ -32,6 +32,38 @@
<p>This document describes the changes made to the Compiler
application.</p>
+<section><title>Compiler 7.3.2</title>
+
+ <section><title>Fixed Bugs and Malfunctions</title>
+ <list>
+ <item>
+ <p>An expression such as <c>(A / B) band 16#ff</c> would
+ crash the compiler.</p>
+ <p>
+ Own Id: OTP-15518 Aux Id: ERL-829 </p>
+ </item>
+ <item>
+ <p>There could be an incorrect warning when the
+ <c>tuple_calls</c> option was given. The generated code
+ would be correct. Here is an example of code that would
+ trigger the warning:</p>
+ <p><c>(list_to_atom("prefix_" ++
+ atom_to_list(suffix))):doit(X)</c>.</p>
+ <p>
+ Own Id: OTP-15552 Aux Id: ERL-838 </p>
+ </item>
+ <item>
+ <p>Optimize (again) Dialyzer's handling of
+ left-associative use of <c>andalso</c> and <c>orelse</c>
+ in guards.</p>
+ <p>
+ Own Id: OTP-15577 Aux Id: ERL-851, PR-2141, PR-1944 </p>
+ </item>
+ </list>
+ </section>
+
+</section>
+
<section><title>Compiler 7.3.1</title>
<section><title>Fixed Bugs and Malfunctions</title>
diff --git a/lib/compiler/scripts/smoke b/lib/compiler/scripts/smoke
index 2429f104c0..ae31c923b8 100755
--- a/lib/compiler/scripts/smoke
+++ b/lib/compiler/scripts/smoke
@@ -54,6 +54,7 @@ setup_mix() ->
ElixirBin = filename:join([SmokeDir,"elixir","bin"]),
PATH = ElixirBin ++ ":" ++ os:getenv("PATH"),
os:putenv("PATH", PATH),
+ mix("local.hex --force"),
mix("local.rebar --force"),
ok.
diff --git a/lib/compiler/scripts/smoke-mix.exs b/lib/compiler/scripts/smoke-mix.exs
index 82ae3370fe..ba0815e465 100644
--- a/lib/compiler/scripts/smoke-mix.exs
+++ b/lib/compiler/scripts/smoke-mix.exs
@@ -25,6 +25,14 @@ defmodule Smoke.MixProject do
[
{:bear, "~> 0.8.7"},
{:cloudi_core, "~> 1.7"},
+ {:cloudi_service_monitoring, "~> 1.7"},
+ {:cloudi_service_tcp, "~> 1.7"},
+ {:cloudi_service_queue, "~> 1.7"},
+ {:cloudi_service_udp, "~> 1.7"},
+ {:cloudi_service_map_reduce, "~> 1.7"},
+ {:cloudi_service_api_requests, "~> 1.7"},
+ {:cloudi_service_router, "~> 1.7"},
+ {:cloudi_service_request_rate, "~> 1.7"},
{:concuerror, "~> 0.20.0"},
{:cowboy, "~> 2.6.1"},
{:ecto, "~> 3.0.6"},
diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl
index 6f50bfdb9c..74f80ca70e 100644
--- a/lib/compiler/src/beam_jump.erl
+++ b/lib/compiler/src/beam_jump.erl
@@ -179,8 +179,9 @@ function({function,Name,Arity,CLabel,Asm0}, Lc0) ->
eliminate_moves(Is) ->
eliminate_moves(Is, #{}, []).
-eliminate_moves([{select,select_val,Reg,_,List}=I|Is], D0, Acc) ->
- D = update_value_dict(List, Reg, D0),
+eliminate_moves([{select,select_val,Reg,{f,Fail},List}=I|Is], D0, Acc) ->
+ D1 = add_unsafe_label(Fail, D0),
+ D = update_value_dict(List, Reg, D1),
eliminate_moves(Is, D, [I|Acc]);
eliminate_moves([{test,is_eq_exact,_,[Reg,Val]}=I,
{block,BlkIs0}|Is], D0, Acc) ->
@@ -229,6 +230,9 @@ update_value_dict([Lit,{f,Lbl}|T], Reg, D0) ->
update_value_dict(T, Reg, D);
update_value_dict([], _, D) -> D.
+add_unsafe_label(L, D) ->
+ D#{L=>unsafe}.
+
update_unsafe_labels(I, D) ->
Ls = instr_labels(I),
update_unsafe_labels_1(Ls, D).
diff --git a/lib/compiler/src/beam_kernel_to_ssa.erl b/lib/compiler/src/beam_kernel_to_ssa.erl
index 410bafe0bb..df95749fb3 100644
--- a/lib/compiler/src/beam_kernel_to_ssa.erl
+++ b/lib/compiler/src/beam_kernel_to_ssa.erl
@@ -327,7 +327,7 @@ select_bin_seg(#k_val_clause{val=#k_bin_seg{size=Size,unit=U,type=T,
{Mis,St1} = select_extract_bin(Next, Size, U, T, Fs, Fail,
Ctx, LineAnno, St0),
{Extracted,St2} = new_ssa_var(Seg#k_var.name, St1),
- {Bis,St} = bin_match_cg(Size, B, Fail, St2),
+ {Bis,St} = match_cg(B, Fail, St2),
BsGet = #b_set{op=bs_extract,dst=Extracted,args=[ssa_arg(Next, St)]},
Is = Mis ++ [BsGet] ++ Bis,
{Is,St};
@@ -362,14 +362,6 @@ select_bin_seg(#k_val_clause{val=#k_bin_int{size=Sz,unit=U,flags=Fs,
end,
{Is,St}.
-bin_match_cg(#k_atom{val=all}, B0, Fail, St) ->
- #k_select{types=Types} = B0,
- [#k_type_clause{type=k_bin_end,values=Values}] = Types,
- [#k_val_clause{val=#k_bin_end{},body=B}] = Values,
- match_cg(B, Fail, St);
-bin_match_cg(_, B, Fail, St) ->
- match_cg(B, Fail, St).
-
get_context(#k_var{}=Var, St) ->
ssa_arg(Var, St).
diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl
index 2cca9ebadf..bb43a550ae 100644
--- a/lib/compiler/src/beam_ssa_dead.erl
+++ b/lib/compiler/src/beam_ssa_dead.erl
@@ -27,7 +27,8 @@
-export([opt/1]).
-include("beam_ssa.hrl").
--import(lists, [append/1,last/1,member/2,takewhile/2,reverse/1]).
+-import(lists, [append/1,keymember/3,last/1,member/2,
+ takewhile/2,reverse/1]).
-type used_vars() :: #{beam_ssa:label():=ordsets:ordset(beam_ssa:var_name())}.
@@ -58,7 +59,7 @@ opt(Linear) ->
Blocks0 = maps:from_list(Linear),
St0 = #st{bs=Blocks0,us=Used,skippable=Skippable},
St = shortcut_opt(St0),
- #st{bs=Blocks} = combine_eqs(St),
+ #st{bs=Blocks} = combine_eqs(St#st{us=#{}}),
beam_ssa:linearize(Blocks).
%%%
@@ -87,13 +88,22 @@ shortcut_opt(#st{bs=Blocks}=St) ->
%% opportunities for optimizations compared to post order. (Based on
%% running scripts/diffable with both PO and RPO and looking at
%% the diff.)
+ %%
+ %% Unfortunately, processing the blocks in reverse post order
+ %% potentially makes the time complexity quadratic or even cubic if
+ %% the ordset of unset variables grows large, instead of
+ %% linear for post order processing. We try to still get reasonable
+ %% compilation times by optimizations that will keep the constant
+ %% factor as low as possible, and we try to avoid the cubic time
+ %% complexity by trying to keep the set of unset variables as small
+ %% as possible.
+
Ls = beam_ssa:rpo(Blocks),
- shortcut_opt(Ls, #{from=>0}, St).
+ shortcut_opt(Ls, #{}, St).
-shortcut_opt([L|Ls], Bs0, #st{bs=Blocks0}=St) ->
+shortcut_opt([L|Ls], Bs, #st{bs=Blocks0}=St) ->
#b_blk{is=Is,last=Last0} = Blk0 = get_block(L, St),
- Bs = Bs0#{from:=L},
- case shortcut_terminator(Last0, Is, Bs, St) of
+ case shortcut_terminator(Last0, Is, L, Bs, St) of
Last0 ->
%% No change. No need to update the block.
shortcut_opt(Ls, Bs, St);
@@ -107,17 +117,17 @@ shortcut_opt([L|Ls], Bs0, #st{bs=Blocks0}=St) ->
shortcut_opt([], _, St) -> St.
shortcut_terminator(#b_br{bool=#b_literal{val=true},succ=Succ0},
- _Is, Bs, St0) ->
+ _Is, From, Bs, St0) ->
St = St0#st{rel_op=none},
- shortcut(Succ0, Bs, St);
+ shortcut(Succ0, From, Bs, St);
shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br,
- Is, Bs, St0) ->
+ Is, From, Bs, St0) ->
St = St0#st{target=one_way},
RelOp = get_rel_op(Bool, Is),
SuccBs = bind_var(Bool, #b_literal{val=true}, Bs),
- BrSucc = shortcut(Succ0, SuccBs, St#st{rel_op=RelOp}),
+ BrSucc = shortcut(Succ0, From, SuccBs, St#st{rel_op=RelOp}),
FailBs = bind_var(Bool, #b_literal{val=false}, Bs),
- BrFail = shortcut(Fail0, FailBs, St#st{rel_op=invert_op(RelOp)}),
+ BrFail = shortcut(Fail0, From, FailBs, St#st{rel_op=invert_op(RelOp)}),
case {BrSucc,BrFail} of
{#b_br{bool=#b_literal{val=true},succ=Succ},
#b_br{bool=#b_literal{val=true},succ=Fail}}
@@ -128,25 +138,25 @@ shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br,
%% No change.
Br
end;
-shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, Bs, St) ->
- List = shortcut_switch(List0, Bool, Bs, St),
+shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, From, Bs, St) ->
+ List = shortcut_switch(List0, Bool, From, Bs, St),
beam_ssa:normalize(Sw#b_switch{list=List});
-shortcut_terminator(Last, _Is, _Bs, _St) ->
+shortcut_terminator(Last, _Is, _Bs, _From, _St) ->
Last.
-shortcut_switch([{Lit,L0}|T], Bool, Bs, St0) ->
+shortcut_switch([{Lit,L0}|T], Bool, From, Bs, St0) ->
RelOp = {'=:=',Bool,Lit},
St = St0#st{rel_op=RelOp},
#b_br{bool=#b_literal{val=true},succ=L} =
- shortcut(L0, bind_var(Bool, Lit, Bs), St#st{target=one_way}),
- [{Lit,L}|shortcut_switch(T, Bool, Bs, St0)];
-shortcut_switch([], _, _, _) -> [].
+ shortcut(L0, From, bind_var(Bool, Lit, Bs), St#st{target=one_way}),
+ [{Lit,L}|shortcut_switch(T, Bool, From, Bs, St0)];
+shortcut_switch([], _, _, _, _) -> [].
-shortcut(L, Bs, St) ->
- shortcut_1(L, Bs, ordsets:new(), St).
+shortcut(L, From, Bs, St) ->
+ shortcut_1(L, From, Bs, ordsets:new(), St).
-shortcut_1(L, Bs0, UnsetVars0, St) ->
- case shortcut_2(L, Bs0, UnsetVars0, St) of
+shortcut_1(L, From, Bs0, UnsetVars0, St) ->
+ case shortcut_2(L, From, Bs0, UnsetVars0, St) of
none ->
%% No more shortcuts found. Package up the previous
%% label in an unconditional branch.
@@ -156,13 +166,13 @@ shortcut_1(L, Bs0, UnsetVars0, St) ->
Br;
{#b_br{bool=#b_literal{val=true},succ=Succ},Bs,UnsetVars} ->
%% This is a safe `br`, but try to find a better one.
- shortcut_1(Succ, Bs#{from:=L}, UnsetVars, St)
+ shortcut_1(Succ, L, Bs, UnsetVars, St)
end.
%% Try to shortcut this block, branching to a successor.
-shortcut_2(L, Bs0, UnsetVars0, St) ->
+shortcut_2(L, From, Bs0, UnsetVars0, St) ->
#b_blk{is=Is,last=Last} = get_block(L, St),
- case eval_is(Is, Bs0, St) of
+ case eval_is(Is, From, Bs0, St) of
none ->
%% It is not safe to avoid this block because it
%% has instructions with potential side effects.
@@ -181,139 +191,147 @@ shortcut_2(L, Bs0, UnsetVars0, St) ->
%% We have a potentially suitable br.
%% Now update the set of variables that will never
%% be set if this block will be skipped.
- SetInThisBlock = [V || #b_set{dst=V} <- Is],
- UnsetVars = update_unset_vars(L, Br, SetInThisBlock,
- UnsetVars0, St),
-
- %% Continue checking whether this br is suitable.
- shortcut_3(Br, Bs#{from:=L}, UnsetVars, St)
+ case update_unset_vars(L, Is, Br, UnsetVars0, St) of
+ unsafe ->
+ %% It is unsafe to use this br,
+ %% because it refers to a variable defined
+ %% in this block.
+ shortcut_unsafe_br(Br, L, Bs, UnsetVars0, St);
+ UnsetVars ->
+ %% Continue checking whether this br is
+ %% suitable.
+ shortcut_test_br(Br, L, Bs, UnsetVars, St)
+ end
end
end.
-shortcut_3(Br, Bs, UnsetVars, #st{target=Target}=St) ->
+shortcut_test_br(Br, From, Bs, UnsetVars, St) ->
case is_br_safe(UnsetVars, Br, St) of
false ->
- %% Branching using this `br` is unsafe, either because it
- %% is an unconditional branch to a phi node, or because
- %% one or more of the variables that are not set will be
- %% used. Try to follow branches of this `br`, to find a
- %% safe `br`.
- case Br of
- #b_br{bool=#b_literal{val=true},succ=L} ->
- case Target of
- L ->
- %% We have reached the forced target, and it
- %% is unsafe. Give up.
- none;
- _ ->
- %% Try following this branch to see whether it
- %% leads to a safe `br`.
- shortcut_2(L, Bs, UnsetVars, St)
- end;
- #b_br{bool=#b_var{},succ=Succ,fail=Fail} ->
- case {Succ,Fail} of
- {L,Target} ->
- %% The failure label is the forced target.
- %% Try following the success label to see
- %% whether it also ultimately ends up at the
- %% forced target.
- shortcut_2(L, Bs, UnsetVars, St);
- {Target,L} ->
- %% The success label is the forced target.
- %% Try following the failure label to see
- %% whether it also ultimately ends up at the
- %% forced target.
- shortcut_2(L, Bs, UnsetVars, St);
- {_,_} ->
- case Target of
- any ->
- %% This two-way branch is unsafe. Try reducing
- %% it to a one-way branch.
- shortcut_two_way(Br, Bs, UnsetVars, St);
- one_way ->
- %% This two-way branch is unsafe. Try reducing
- %% it to a one-way branch.
- shortcut_two_way(Br, Bs, UnsetVars, St);
- _ when is_integer(Target) ->
- %% This two-way branch is unsafe, and
- %% there already is a forced target.
- %% Give up.
- none
- end
- end
- end;
+ shortcut_unsafe_br(Br, From, Bs, UnsetVars, St);
true ->
- %% This `br` instruction is safe. It does not
- %% branch to a phi node, and all variables that
- %% will be used are guaranteed to be defined.
- case Br of
- #b_br{bool=#b_literal{val=true},succ=L} ->
- %% This is a one-way branch.
+ shortcut_safe_br(Br, From, Bs, UnsetVars, St)
+ end.
+
+shortcut_unsafe_br(Br, From, Bs, UnsetVars, #st{target=Target}=St) ->
+ %% Branching using this `br` is unsafe, either because it
+ %% is an unconditional branch to a phi node, or because
+ %% one or more of the variables that are not set will be
+ %% used. Try to follow branches of this `br`, to find a
+ %% safe `br`.
+ case Br of
+ #b_br{bool=#b_literal{val=true},succ=L} ->
+ case Target of
+ L ->
+ %% We have reached the forced target, and it
+ %% is unsafe. Give up.
+ none;
+ _ ->
+ %% Try following this branch to see whether it
+ %% leads to a safe `br`.
+ shortcut_2(L, From, Bs, UnsetVars, St)
+ end;
+ #b_br{bool=#b_var{},succ=Succ,fail=Fail} ->
+ case {Succ,Fail} of
+ {L,Target} ->
+ %% The failure label is the forced target.
+ %% Try following the success label to see
+ %% whether it also ultimately ends up at the
+ %% forced target.
+ shortcut_2(L, From, Bs, UnsetVars, St);
+ {Target,L} ->
+ %% The success label is the forced target.
+ %% Try following the failure label to see
+ %% whether it also ultimately ends up at the
+ %% forced target.
+ shortcut_2(L, From, Bs, UnsetVars, St);
+ {_,_} ->
case Target of
any ->
- %% No forced target. Success!
- {Br,Bs,UnsetVars};
+ %% This two-way branch is unsafe. Try
+ %% reducing it to a one-way branch.
+ shortcut_two_way(Br, From, Bs, UnsetVars, St);
one_way ->
- %% The target must be a one-way branch, which this
- %% `br` is. Success!
- {Br,Bs,UnsetVars};
- L when is_integer(Target) ->
- %% The forced target is L. Success!
- {Br,Bs,UnsetVars};
+ %% This two-way branch is unsafe. Try
+ %% reducing it to a one-way branch.
+ shortcut_two_way(Br, From, Bs, UnsetVars, St);
_ when is_integer(Target) ->
- %% Wrong forced target. Try following this branch
- %% to see if it ultimately ends up at the forced
- %% target.
- shortcut_2(L, Bs, UnsetVars, St)
- end;
- #b_br{bool=#b_var{}} ->
- %% This is a two-way branch.
- if
- Target =:= any; Target =:= one_way ->
- %% No specific forced target. Try to reduce the
- %% two-way branch to an one-way branch.
- case shortcut_two_way(Br, Bs, UnsetVars, St) of
- none when Target =:= any ->
- %% This `br` can't be reduced to a one-way
- %% branch. Return the `br` as-is.
- {Br,Bs,UnsetVars};
- none when Target =:= one_way ->
- %% This `br` can't be reduced to a one-way
- %% branch. The caller wants a one-way branch.
- %% Give up.
- none;
- {_,_,_}=Res ->
- %% This `br` was successfully reduced to a
- %% one-way branch.
- Res
- end;
- is_integer(Target) ->
- %% There is a forced target, which can't
- %% be reached because this `br` is a two-way
- %% branch. Give up.
+ %% This two-way branch is unsafe, and
+ %% there already is a forced target.
+ %% Give up.
none
end
end
end.
-update_unset_vars(L, Br, SetInThisBlock, UnsetVars, #st{skippable=Skippable}) ->
+shortcut_safe_br(Br, From, Bs, UnsetVars, #st{target=Target}=St) ->
+ %% This `br` instruction is safe. It does not branch to a phi
+ %% node, and all variables that will be used are guaranteed to be
+ %% defined.
+ case Br of
+ #b_br{bool=#b_literal{val=true},succ=L} ->
+ %% This is a one-way branch.
+ case Target of
+ any ->
+ %% No forced target. Success!
+ {Br,Bs,UnsetVars};
+ one_way ->
+ %% The target must be a one-way branch, which this
+ %% `br` is. Success!
+ {Br,Bs,UnsetVars};
+ L when is_integer(Target) ->
+ %% The forced target is L. Success!
+ {Br,Bs,UnsetVars};
+ _ when is_integer(Target) ->
+ %% Wrong forced target. Try following this branch
+ %% to see if it ultimately ends up at the forced
+ %% target.
+ shortcut_2(L, From, Bs, UnsetVars, St)
+ end;
+ #b_br{bool=#b_var{}} ->
+ %% This is a two-way branch.
+ if
+ Target =:= any; Target =:= one_way ->
+ %% No specific forced target. Try to reduce the
+ %% two-way branch to an one-way branch.
+ case shortcut_two_way(Br, From, Bs, UnsetVars, St) of
+ none when Target =:= any ->
+ %% This `br` can't be reduced to a one-way
+ %% branch. Return the `br` as-is.
+ {Br,Bs,UnsetVars};
+ none when Target =:= one_way ->
+ %% This `br` can't be reduced to a one-way
+ %% branch. The caller wants a one-way
+ %% branch. Give up.
+ none;
+ {_,_,_}=Res ->
+ %% This `br` was successfully reduced to a
+ %% one-way branch.
+ Res
+ end;
+ is_integer(Target) ->
+ %% There is a forced target, which can't
+ %% be reached because this `br` is a two-way
+ %% branch. Give up.
+ none
+ end
+ end.
+
+update_unset_vars(L, Is, Br, UnsetVars, #st{skippable=Skippable}) ->
case is_map_key(L, Skippable) of
true ->
%% None of the variables used in this block are used in
- %% the successors. We can speed up compilation by avoiding
- %% adding variables to the UnsetVars if the presence of
- %% those variable would not change the outcome of the
- %% tests in is_br_safe/2.
+ %% the successors. Thus, there is no need to add the
+ %% variables to the set of unset variables.
case Br of
- #b_br{bool=Bool} ->
- case member(Bool, SetInThisBlock) of
+ #b_br{bool=#b_var{}=Bool} ->
+ case keymember(Bool, #b_set.dst, Is) of
true ->
%% Bool is a variable defined in this
- %% block. It will change the outcome of
- %% the `not member(V, UnsetVars)` check in
- %% is_br_safe/2. The other variables
- %% defined in this block will not.
- ordsets:add_element(Bool, UnsetVars);
+ %% block. Using the br instruction from
+ %% this block (and skipping the body of
+ %% the block) is unsafe.
+ unsafe;
false ->
%% Bool is either a variable not defined
%% in this block or a literal. Adding it
@@ -321,18 +339,24 @@ update_unset_vars(L, Br, SetInThisBlock, UnsetVars, #st{skippable=Skippable}) ->
%% the outcome of the tests in
%% is_br_safe/2.
UnsetVars
- end
+ end;
+ #b_br{} ->
+ UnsetVars
end;
false ->
+ %% Some variables defined in this block are used by
+ %% successors. We must update the set of unset variables.
+ SetInThisBlock = [V || #b_set{dst=V} <- Is],
ordsets:union(UnsetVars, ordsets:from_list(SetInThisBlock))
end.
-shortcut_two_way(#b_br{succ=Succ,fail=Fail}, Bs0, UnsetVars0, St) ->
- case shortcut_2(Succ, Bs0, UnsetVars0, St#st{target=Fail}) of
+shortcut_two_way(#b_br{succ=Succ,fail=Fail}, From, Bs0, UnsetVars0, St0) ->
+ case shortcut_2(Succ, From, Bs0, UnsetVars0, St0#st{target=Fail}) of
{#b_br{bool=#b_literal{},succ=Fail},_,_}=Res ->
Res;
none ->
- case shortcut_2(Fail, Bs0, UnsetVars0, St#st{target=Succ}) of
+ St = St0#st{target=Succ},
+ case shortcut_2(Fail, From, Bs0, UnsetVars0, St) of
{#b_br{bool=#b_literal{},succ=Succ},_,_}=Res ->
Res;
none ->
@@ -374,40 +398,42 @@ is_forbidden(L, St) ->
%% Return the updated bindings, or 'none' if there is
%% any instruction with potential side effects.
-eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], Bs0, St) ->
- From = map_get(from, Bs0),
- [Val] = [Val || {Val,Pred} <- Args, Pred =:= From],
+eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], From, Bs0, St) ->
+ Val = get_phi_arg(Args, From),
Bs = bind_var(Dst, Val, Bs0),
- eval_is(Is, Bs, St);
-eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], Bs, St) ->
+ eval_is(Is, From, Bs, St);
+eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], From, Bs, St) ->
I = sub(I0, Bs),
case eval_bif(I, St) of
#b_literal{}=Val ->
- eval_is(Is, bind_var(Dst, Val, Bs), St);
+ eval_is(Is, From, bind_var(Dst, Val, Bs), St);
none ->
- eval_is(Is, Bs, St)
+ eval_is(Is, From, Bs, St)
end;
-eval_is([#b_set{op=Op,dst=Dst}=I|Is], Bs, St)
+eval_is([#b_set{op=Op,dst=Dst}=I|Is], From, Bs, St)
when Op =:= is_tagged_tuple; Op =:= is_nonempty_list ->
#b_set{args=Args} = sub(I, Bs),
case eval_rel_op(Op, Args, St) of
#b_literal{}=Val ->
- eval_is(Is, bind_var(Dst, Val, Bs), St);
+ eval_is(Is, From, bind_var(Dst, Val, Bs), St);
none ->
- eval_is(Is, Bs, St)
+ eval_is(Is, From, Bs, St)
end;
-eval_is([#b_set{}=I|Is], Bs, St) ->
+eval_is([#b_set{}=I|Is], From, Bs, St) ->
case beam_ssa:no_side_effect(I) of
true ->
%% This instruction has no side effects. It can
%% safely be omitted.
- eval_is(Is, Bs, St);
+ eval_is(Is, From, Bs, St);
false ->
%% This instruction may have some side effect.
%% It is not safe to avoid this instruction.
none
end;
-eval_is([], Bs, _St) -> Bs.
+eval_is([], _From, Bs, _St) -> Bs.
+
+get_phi_arg([{Val,From}|_], From) -> Val;
+get_phi_arg([_|As], From) -> get_phi_arg(As, From).
eval_terminator(#b_br{bool=#b_var{}=Bool}=Br, Bs, _St) ->
Val = get_value(Bool, Bs),
@@ -477,20 +503,31 @@ eval_bif(#b_set{op={bif,Bif},args=Args}, St) ->
false ->
none;
true ->
- case [Lit || #b_literal{val=Lit} <- Args] of
- LitArgs when length(LitArgs) =:= Arity ->
+ case get_lit_args(Args) of
+ none ->
+ %% Not literal arguments. Try to evaluate
+ %% it based on a previous relational operator.
+ eval_rel_op({bif,Bif}, Args, St);
+ LitArgs ->
try apply(erlang, Bif, LitArgs) of
Val -> #b_literal{val=Val}
catch
error:_ -> none
- end;
- _ ->
- %% Not literal arguments. Try to evaluate
- %% it based on a previous relational operator.
- eval_rel_op({bif,Bif}, Args, St)
+ end
end
end.
+get_lit_args([#b_literal{val=Lit1}]) ->
+ [Lit1];
+get_lit_args([#b_literal{val=Lit1},
+ #b_literal{val=Lit2}]) ->
+ [Lit1,Lit2];
+get_lit_args([#b_literal{val=Lit1},
+ #b_literal{val=Lit2},
+ #b_literal{val=Lit3}]) ->
+ [Lit1,Lit2,Lit3];
+get_lit_args(_) -> none.
+
%%%
%%% Handling of relational operators.
%%%
@@ -1026,11 +1063,12 @@ used_vars_is([], Used) ->
sub(#b_set{args=Args}=I, Sub) ->
I#b_set{args=[sub_arg(A, Sub) || A <- Args]}.
-sub_arg(Old, Sub) ->
+sub_arg(#b_var{}=Old, Sub) ->
case Sub of
#{Old:=New} -> New;
#{} -> Old
- end.
+ end;
+sub_arg(Old, _Sub) -> Old.
rel2fam(S0) ->
S1 = sofs:relation(S0),
diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl
index 6e548dd529..90c0d3cf16 100644
--- a/lib/compiler/src/beam_ssa_opt.erl
+++ b/lib/compiler/src/beam_ssa_opt.erl
@@ -175,6 +175,7 @@ epilogue_passes(Opts) ->
?PASS(ssa_opt_blockify),
?PASS(ssa_opt_sink),
?PASS(ssa_opt_merge_blocks),
+ ?PASS(ssa_opt_get_tuple_element),
?PASS(ssa_opt_trim_unreachable)],
passes_1(Ps, Opts).
@@ -682,6 +683,14 @@ record_opt_is([#b_set{op={bif,is_tuple},dst=Bool,args=[Tuple]}=Set],
no ->
[Set]
end;
+record_opt_is([I|Is]=Is0, #b_br{bool=Bool}=Last, Blocks) ->
+ case is_tagged_tuple_1(Is0, Last, Blocks) of
+ {yes,_Fail,Tuple,Arity,Tag} ->
+ Args = [Tuple,Arity,Tag],
+ [I#b_set{op=is_tagged_tuple,dst=Bool,args=Args}];
+ no ->
+ [I|record_opt_is(Is, Last, Blocks)]
+ end;
record_opt_is([I|Is], Last, Blocks) ->
[I|record_opt_is(Is, Last, Blocks)];
record_opt_is([], _Last, _Blocks) -> [].
@@ -689,29 +698,30 @@ record_opt_is([], _Last, _Blocks) -> [].
is_tagged_tuple(#b_var{}=Tuple, Bool,
#b_br{bool=Bool,succ=Succ,fail=Fail},
Blocks) ->
- SuccBlk = map_get(Succ, Blocks),
- is_tagged_tuple_1(SuccBlk, Tuple, Fail, Blocks);
+ #b_blk{is=Is,last=Last} = map_get(Succ, Blocks),
+ case is_tagged_tuple_1(Is, Last, Blocks) of
+ {yes,Fail,Tuple,Arity,Tag} ->
+ {yes,Arity,Tag};
+ _ ->
+ no
+ end;
is_tagged_tuple(_, _, _, _) -> no.
-is_tagged_tuple_1(#b_blk{is=Is,last=Last}, Tuple, Fail, Blocks) ->
- case Is of
- [#b_set{op={bif,tuple_size},dst=ArityVar,
- args=[#b_var{}=Tuple]},
- #b_set{op={bif,'=:='},
- dst=Bool,
- args=[ArityVar, #b_literal{val=ArityVal}=Arity]}]
- when is_integer(ArityVal) ->
- case Last of
- #b_br{bool=Bool,succ=Succ,fail=Fail} ->
- SuccBlk = map_get(Succ, Blocks),
- case is_tagged_tuple_2(SuccBlk, Tuple, Fail) of
- no ->
- no;
- {yes,Tag} ->
- {yes,Arity,Tag}
- end;
- _ ->
- no
+is_tagged_tuple_1(Is, Last, Blocks) ->
+ case {Is,Last} of
+ {[#b_set{op={bif,tuple_size},dst=ArityVar,
+ args=[#b_var{}=Tuple]},
+ #b_set{op={bif,'=:='},
+ dst=Bool,
+ args=[ArityVar, #b_literal{val=ArityVal}=Arity]}],
+ #b_br{bool=Bool,succ=Succ,fail=Fail}}
+ when is_integer(ArityVal) ->
+ SuccBlk = map_get(Succ, Blocks),
+ case is_tagged_tuple_2(SuccBlk, Tuple, Fail) of
+ no ->
+ no;
+ {yes,Tag} ->
+ {yes,Fail,Tuple,Arity,Tag}
end;
_ ->
no
@@ -901,6 +911,11 @@ ssa_opt_float({#st{ssa=Linear0,cnt=Count0}=St, FuncDb}) ->
{Linear,Count} = float_opt(Linear0, Count0, Fs),
{St#st{ssa=Linear,cnt=Count}, FuncDb}.
+float_blk_is_in_guard(#b_blk{last=#b_br{fail=F}}, #fs{non_guards=NonGuards}) ->
+ not gb_sets:is_member(F, NonGuards);
+float_blk_is_in_guard(#b_blk{}, #fs{}) ->
+ false.
+
float_non_guards([{L,#b_blk{is=Is}}|Bs]) ->
case Is of
[#b_set{op=landingpad}|_] ->
@@ -910,21 +925,18 @@ float_non_guards([{L,#b_blk{is=Is}}|Bs]) ->
end;
float_non_guards([]) -> [?BADARG_BLOCK].
-float_opt([{L,#b_blk{last=#b_br{fail=F}}=Blk}|Bs0],
- Count0, #fs{non_guards=NonGuards}=Fs) ->
- case gb_sets:is_member(F, NonGuards) of
+float_opt([{L,Blk}|Bs0], Count0, Fs) ->
+ case float_blk_is_in_guard(Blk, Fs) of
true ->
- %% This block is not inside a guard.
- %% We can do the optimization.
- float_opt_1(L, Blk, Bs0, Count0, Fs);
- false ->
%% This block is inside a guard. Don't do
%% any floating point optimizations.
{Bs,Count} = float_opt(Bs0, Count0, Fs),
- {[{L,Blk}|Bs],Count}
+ {[{L,Blk}|Bs],Count};
+ false ->
+ %% This block is not inside a guard.
+ %% We can do the optimization.
+ float_opt_1(L, Blk, Bs0, Count0, Fs)
end;
-float_opt([{L,Blk}|Bs], Count, Fs) ->
- float_opt_1(L, Blk, Bs, Count, Fs);
float_opt([], Count, _Fs) ->
{[],Count}.
@@ -1000,10 +1012,14 @@ float_conv([{L,#b_blk{is=Is0}=Blk0}|Bs0], Fail, Count0) ->
float_maybe_flush(Blk0, #fs{s=cleared,fail=Fail,bs=Blocks}=Fs0, Count0) ->
#b_blk{last=#b_br{bool=#b_var{},succ=Succ}=Br} = Blk0,
- #b_blk{is=Is} = map_get(Succ, Blocks),
+
+ %% If the success block starts with a floating point operation, we can
+ %% defer flushing to that block as long as it isn't a guard.
+ #b_blk{is=Is} = SuccBlk = map_get(Succ, Blocks),
+ SuccIsGuard = float_blk_is_in_guard(SuccBlk, Fs0),
+
case Is of
- [#b_set{anno=#{float_op:=_}}|_] ->
- %% The next operation is also a floating point operation.
+ [#b_set{anno=#{float_op:=_}}|_] when not SuccIsGuard ->
%% No flush needed.
{[],Blk0,Fs0,Count0};
_ ->
@@ -2174,6 +2190,46 @@ insert_def_is([#b_set{op=Op}=I|Is]=Is0, V, Def) ->
insert_def_is([], _V, Def) ->
[Def].
+%%%
+%%% Order consecutive get_tuple_element instructions in ascending
+%%% position order. This will give the loader more opportunities
+%%% for combining get_tuple_element instructions.
+%%%
+
+ssa_opt_get_tuple_element({#st{ssa=Blocks0}=St, FuncDb}) ->
+ Blocks = opt_get_tuple_element(maps:to_list(Blocks0), Blocks0),
+ {St#st{ssa=Blocks}, FuncDb}.
+
+opt_get_tuple_element([{L,#b_blk{is=Is0}=Blk0}|Bs], Blocks) ->
+ case opt_get_tuple_element_is(Is0, false, []) of
+ {yes,Is} ->
+ Blk = Blk0#b_blk{is=Is},
+ opt_get_tuple_element(Bs, Blocks#{L:=Blk});
+ no ->
+ opt_get_tuple_element(Bs, Blocks)
+ end;
+opt_get_tuple_element([], Blocks) -> Blocks.
+
+opt_get_tuple_element_is([#b_set{op=get_tuple_element,
+ args=[#b_var{}=Src,_]}=I0|Is0],
+ _AnyChange, Acc) ->
+ {GetIs0,Is} = collect_get_tuple_element(Is0, Src, [I0]),
+ GetIs1 = sort([{Pos,I} || #b_set{args=[_,Pos]}=I <- GetIs0]),
+ GetIs = [I || {_,I} <- GetIs1],
+ opt_get_tuple_element_is(Is, true, reverse(GetIs, Acc));
+opt_get_tuple_element_is([I|Is], AnyChange, Acc) ->
+ opt_get_tuple_element_is(Is, AnyChange, [I|Acc]);
+opt_get_tuple_element_is([], AnyChange, Acc) ->
+ case AnyChange of
+ true -> {yes,reverse(Acc)};
+ false -> no
+ end.
+
+collect_get_tuple_element([#b_set{op=get_tuple_element,
+ args=[Src,_]}=I|Is], Src, Acc) ->
+ collect_get_tuple_element(Is, Src, [I|Acc]);
+collect_get_tuple_element(Is, _Src, Acc) ->
+ {Acc,Is}.
%%%
%%% Common utilities.
diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl
index aa4720d222..c01ea4af91 100644
--- a/lib/compiler/src/beam_ssa_type.erl
+++ b/lib/compiler/src/beam_ssa_type.erl
@@ -170,7 +170,8 @@ opt_finish_1([], [], ParamInfo) ->
validator_anno(#t_tuple{size=Size,exact=Exact,elements=Elements0}) ->
Elements = maps:fold(fun(Index, Type, Acc) ->
- Acc#{ Index => validator_anno(Type) }
+ Key = beam_validator:type_anno(integer, Index),
+ Acc#{ Key => validator_anno(Type) }
end, #{}, Elements0),
beam_validator:type_anno(tuple, Size, Exact, Elements);
validator_anno(#t_integer{elements={Same,Same}}) ->
diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index 5175be3ad5..4fba3fa1c6 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -28,8 +28,7 @@
-export([module/2, format_error/1]).
-export([type_anno/1, type_anno/2, type_anno/4]).
--import(lists, [any/2,dropwhile/2,foldl/3,map/2,member/2,reverse/1,
- seq/2,sort/1,zip/2]).
+-import(lists, [dropwhile/2,foldl/3,member/2,reverse/1,sort/1,zip/2]).
%% To be called by the compiler.
@@ -51,7 +50,7 @@ module({Mod,Exp,Attr,Fs,Lc}=Code, _Opts)
-spec type_anno(term()) -> term().
type_anno(atom) -> {atom,[]};
type_anno(bool) -> bool;
-type_anno({binary,_}) -> term;
+type_anno({binary,_}) -> binary;
type_anno(cons) -> cons;
type_anno(float) -> {float,[]};
type_anno(integer) -> {integer,[]};
@@ -62,9 +61,9 @@ type_anno(number) -> number;
type_anno(nil) -> nil.
-spec type_anno(term(), term()) -> term().
-type_anno(atom, Value) -> {atom, Value};
-type_anno(float, Value) -> {float, Value};
-type_anno(integer, Value) -> {integer, Value}.
+type_anno(atom, Value) when is_atom(Value) -> {atom, Value};
+type_anno(float, Value) when is_float(Value) -> {float, Value};
+type_anno(integer, Value) when is_integer(Value) -> {integer, Value}.
-spec type_anno(term(), term(), term(), term()) -> term().
type_anno(tuple, Size, Exact, Elements) when is_integer(Size), Size >= 0,
@@ -137,43 +136,100 @@ validate_0(Module, [{function,Name,Ar,Entry,Code}|Fs], Ft) ->
erlang:raise(Class, Error, Stack)
end.
+-record(value_ref, {id :: index()}).
+-record(value, {op :: term(), args :: [argument()], type :: type()}).
+
+-type argument() :: #value_ref{} | literal().
+
-type index() :: non_neg_integer().
--type reg_tab() :: gb_trees:tree(index(), 'none' | {'value', _}).
-
--record(st, %Emulation state
- {x :: reg_tab(), %x register info.
- y :: reg_tab(), %y register info.
- f=init_fregs(), %
- numy=none, %Number of y registers.
- h=0, %Available heap size.
- hf=0, %Available heap size for floats.
- fls=undefined, %Floating point state.
- ct=[], %List of hot catch/try labels
- setelem=false, %Previous instruction was setelement/3.
- puts_left=none, %put/1 instructions left.
- defs=#{}, %Defining expression for each register.
- aliases=#{}
- }).
+
+-type literal() :: {atom, [] | atom()} |
+ {float, [] | float()} |
+ {integer, [] | integer()} |
+ {literal, term()} |
+ nil.
+
+-type tuple_sz() :: [non_neg_integer()] | %% Inexact
+ non_neg_integer(). %% Exact.
+
+%% Match context type.
+-record(ms,
+ {id=make_ref() :: reference(), %Unique ID.
+ valid=0 :: non_neg_integer(), %Valid slots
+ slots=0 :: non_neg_integer() %Number of slots
+ }).
+
+-type type() :: binary |
+ cons |
+ list |
+ map |
+ nil |
+ #ms{} |
+ ms_position |
+ none |
+ number |
+ term |
+ tuple_in_progress |
+ {tuple, tuple_sz(), #{ literal() => type() }} |
+ literal().
+
+-type tag() :: initialized |
+ uninitialized |
+ {catchtag, [label()]} |
+ {trytag, [label()]}.
+
+-type x_regs() :: #{ {x, index()} => #value_ref{} }.
+-type y_regs() :: #{ {y, index()} => tag() | #value_ref{} }.
+
+%% Emulation state
+-record(st,
+ {%% All known values.
+ vs=#{} :: #{ #value_ref{} => #value{} },
+ %% Register states.
+ xs=#{} :: x_regs(),
+ ys=#{} :: y_regs(),
+ f=init_fregs(),
+ %% A set of all registers containing "fragile" terms. That is, terms
+ %% that don't exist on our process heap and would be destroyed by a
+ %% GC.
+ fragile=cerl_sets:new() :: cerl_sets:set(),
+ %% Number of Y registers.
+ %%
+ %% Note that this may be 0 if there's a frame without saved values,
+ %% such as on a body-recursive call.
+ numy=none :: none | undecided | index(),
+ %% Available heap size.
+ h=0,
+ %Available heap size for floats.
+ hf=0,
+ %% Floating point state.
+ fls=undefined,
+ %% List of hot catch/try labels
+ ct=[],
+ %% Previous instruction was setelement/3.
+ setelem=false,
+ %% put/1 instructions left.
+ puts_left=none
+ }).
-type label() :: integer().
-type label_set() :: gb_sets:set(label()).
-type branched_tab() :: gb_trees:tree(label(), #st{}).
-type ft_tab() :: gb_trees:tree().
--record(vst, %Validator state
- {current=none :: #st{} | 'none', %Current state
- branched=gb_trees:empty() :: branched_tab(), %States at jumps
- labels=gb_sets:empty() :: label_set(), %All defined labels
- ft=gb_trees:empty() :: ft_tab() %Some other functions
- % in the module (those that start with bs_start_match2).
- }).
-
-%% Match context type.
--record(ms,
- {id=make_ref() :: reference(), %Unique ID.
- valid=0 :: non_neg_integer(), %Valid slots
- slots=0 :: non_neg_integer() %Number of slots
- }).
+%% Validator state
+-record(vst,
+ {%% Current state
+ current=none :: #st{} | 'none',
+ %% States at labels
+ branched=gb_trees:empty() :: branched_tab(),
+ %% All defined labels
+ labels=gb_sets:empty() :: label_set(),
+ %% Argument information of other functions in the module
+ ft=gb_trees:empty() :: ft_tab(),
+ %% Counter for #value_ref{} creation
+ ref_ctr=0 :: index()
+ }).
index_parameter_types([{function,_,_,Entry,Code0}|Fs], Acc0) ->
Code = dropwhile(fun({label,L}) when L =:= Entry -> false;
@@ -238,7 +294,7 @@ validate_fun_info_branches_1(X, {Mod,Name,Arity}=MFA, Vst) ->
#vst{current=#st{numy=Size}} ->
error({unexpected_stack_frame,Size})
end,
- get_term_type({x,X}, Vst)
+ assert_term({x,X}, Vst)
catch Error ->
I = {func_info,{atom,Mod},{atom,Name},Arity},
Offset = 2,
@@ -260,24 +316,21 @@ labels_1(Is, R) ->
{reverse(R),Is}.
init_vst(Arity, Ls1, Ls2, Ft) ->
- Xs = init_regs(Arity, term),
- Ys = init_regs(0, initialized),
- St = #st{x=Xs,y=Ys},
- Branches = gb_trees_from_list([{L,St} || L <- Ls1]),
+ Vst0 = init_function_args(Arity - 1, #vst{current=#st{}}),
+ Branches = gb_trees_from_list([{L,Vst0#vst.current} || L <- Ls1]),
Labels = gb_sets:from_list(Ls1++Ls2),
- #vst{branched=Branches,
- current=St,
- labels=Labels,
- ft=Ft}.
+ Vst0#vst{branched=Branches,
+ labels=Labels,
+ ft=Ft}.
+
+init_function_args(-1, Vst) ->
+ Vst;
+init_function_args(X, Vst) ->
+ init_function_args(X - 1, create_term(term, argument, [], {x,X}, Vst)).
kill_heap_allocation(St) ->
St#st{h=0,hf=0}.
-init_regs(0, _) ->
- gb_trees:empty();
-init_regs(N, Type) ->
- gb_trees_from_list([{R,Type} || R <- seq(0, N-1)]).
-
valfun([], MFA, _Offset, #vst{branched=Targets0,labels=Labels0}=Vst) ->
Targets = gb_trees:keys(Targets0),
Labels = gb_sets:to_list(Labels0),
@@ -298,20 +351,25 @@ valfun([I|Is], MFA, Offset, Vst0) ->
%% Instructions that are allowed in dead code or when failing,
%% that is while the state is undecided in some way.
-valfun_1({label,Lbl}, #vst{current=St0,branched=B,labels=Lbls}=Vst) ->
- St = merge_states(Lbl, St0, B),
- Vst#vst{current=St,branched=gb_trees:enter(Lbl, St, B),
- labels=gb_sets:add(Lbl, Lbls)};
+valfun_1({label,Lbl}, #vst{current=St0,
+ ref_ctr=Counter0,
+ branched=B,
+ labels=Lbls}=Vst) ->
+ {St, Counter} = merge_states(Lbl, St0, B, Counter0),
+ Vst#vst{current=St,
+ ref_ctr=Counter,
+ branched=gb_trees:enter(Lbl, St, B),
+ labels=gb_sets:add(Lbl, Lbls)};
valfun_1(_I, #vst{current=none}=Vst) ->
%% Ignore instructions after erlang:error/1,2, which
%% the original R10B compiler thought would return.
Vst;
valfun_1({badmatch,Src}, Vst) ->
- assert_not_fragile(Src, Vst),
+ assert_durable_term(Src, Vst),
verify_y_init(Vst),
kill_state(Vst);
valfun_1({case_end,Src}, Vst) ->
- assert_not_fragile(Src, Vst),
+ assert_durable_term(Src, Vst),
verify_y_init(Vst),
kill_state(Vst);
valfun_1(if_end, Vst) ->
@@ -319,7 +377,7 @@ valfun_1(if_end, Vst) ->
kill_state(Vst);
valfun_1({try_case_end,Src}, Vst) ->
verify_y_init(Vst),
- assert_not_fragile(Src, Vst),
+ assert_durable_term(Src, Vst),
kill_state(Vst);
%% Instructions that cannot cause exceptions
valfun_1({bs_get_tail,Ctx,Dst,Live}, Vst0) ->
@@ -363,17 +421,17 @@ valfun_1({bif,Op,{f,_},Ss,Dst}=I, Vst) ->
end;
%% Put instructions.
valfun_1({put_list,A,B,Dst}, Vst0) ->
- assert_not_fragile(A, Vst0),
- assert_not_fragile(B, Vst0),
+ assert_term(A, Vst0),
+ assert_term(B, Vst0),
Vst = eat_heap(2, Vst0),
create_term(cons, put_list, [A, B], Dst, Vst);
valfun_1({put_tuple2,Dst,{list,Elements}}, Vst0) ->
- _ = [assert_not_fragile(El, Vst0) || El <- Elements],
+ _ = [assert_term(El, Vst0) || El <- Elements],
Size = length(Elements),
Vst = eat_heap(Size+1, Vst0),
{Es,_} = foldl(fun(Val, {Es0, Index}) ->
Type = get_term_type(Val, Vst0),
- Es = set_element_type(Index, Type, Es0),
+ Es = set_element_type({integer,Index}, Type, Es0),
{Es, Index + 1}
end, {#{}, 1}, Elements),
Type = {tuple,Size,Es},
@@ -385,18 +443,19 @@ valfun_1({put_tuple,Sz,Dst}, Vst0) when is_integer(Sz) ->
St = St0#st{puts_left={Sz,{Dst,Sz,#{}}}},
Vst#vst{current=St};
valfun_1({put,Src}, Vst0) ->
- assert_not_fragile(Src, Vst0),
+ assert_term(Src, Vst0),
Vst = eat_heap(1, Vst0),
#vst{current=St0} = Vst,
case St0 of
#st{puts_left=none} ->
error(not_building_a_tuple);
- #st{puts_left={1,{Dst,Sz,Es}}} ->
+ #st{puts_left={1,{Dst,Sz,Es0}}} ->
+ Es = Es0#{ {integer,Sz} => get_term_type(Src, Vst0) },
St = St0#st{puts_left=none},
create_term({tuple,Sz,Es}, put_tuple, [], Dst, Vst#vst{current=St});
#st{puts_left={PutsLeft,{Dst,Sz,Es0}}} when is_integer(PutsLeft) ->
Index = Sz - PutsLeft + 1,
- Es = Es0#{ Index => get_term_type(Src, Vst0) },
+ Es = Es0#{ {integer,Index} => get_term_type(Src, Vst0) },
St = St0#st{puts_left={PutsLeft-1,{Dst,Sz,Es}}},
Vst#vst{current=St}
end;
@@ -417,6 +476,14 @@ valfun_1({'%', {type_info, Reg, Type}}, Vst) ->
%% that Reg has a certain type, so that we can accept cross-function type
%% optimizations.
update_type(fun meet/2, Type, Reg, Vst);
+valfun_1({'%', {remove_fragility, Reg}}, Vst) ->
+ %% This is a hack to make prim_eval:'receive'/2 work.
+ %%
+ %% Normally it's illegal to pass fragile terms as a function argument as we
+ %% have no way of knowing what the callee will do with it, but we know that
+ %% prim_eval:'receive'/2 won't leak the term, nor cause a GC since it's
+ %% disabled while matching messages.
+ remove_fragility(Reg, Vst);
valfun_1({'%',_}, Vst) ->
Vst;
valfun_1({line,_}, Vst) ->
@@ -438,13 +505,13 @@ valfun_1(_I, #vst{current=#st{ct=undecided}}) ->
%%
%% Allocate and deallocate, et.al
valfun_1({allocate,Stk,Live}, Vst) ->
- allocate(false, Stk, 0, Live, Vst);
+ allocate(uninitialized, Stk, 0, Live, Vst);
valfun_1({allocate_heap,Stk,Heap,Live}, Vst) ->
- allocate(false, Stk, Heap, Live, Vst);
+ allocate(uninitialized, Stk, Heap, Live, Vst);
valfun_1({allocate_zero,Stk,Live}, Vst) ->
- allocate(true, Stk, 0, Live, Vst);
+ allocate(initialized, Stk, 0, Live, Vst);
valfun_1({allocate_heap_zero,Stk,Heap,Live}, Vst) ->
- allocate(true, Stk, Heap, Live, Vst);
+ allocate(initialized, Stk, Heap, Live, Vst);
valfun_1({deallocate,StkSize}, #vst{current=#st{numy=StkSize}}=Vst) ->
verify_no_ct(Vst),
deallocate(Vst);
@@ -508,46 +575,66 @@ valfun_1({get_tl,Src,Dst}, Vst) ->
valfun_1({get_tuple_element,Src,N,Dst}, Vst) ->
assert_not_literal(Src),
assert_type({tuple_element,N+1}, Src, Vst),
- Type = get_element_type(N+1, Src, Vst),
- extract_term(Type, get_tuple_element, [Src], Dst, Vst);
+ Index = {integer,N+1},
+ Type = get_element_type(Index, Src, Vst),
+ extract_term(Type, {bif,element}, [Index, Src], Dst, Vst);
valfun_1({jump,{f,Lbl}}, Vst) ->
- kill_state(branch_state(Lbl, Vst));
+ branch(Lbl, Vst,
+ fun(SuccVst) ->
+ %% The next instruction is never executed.
+ kill_state(SuccVst)
+ end);
valfun_1(I, Vst) ->
valfun_2(I, Vst).
init_try_catch_branch(Tag, Dst, Fail, Vst0) ->
Vst1 = create_tag({Tag,[Fail]}, 'try_catch', [], Dst, Vst0),
#vst{current=#st{ct=Fails}=St0} = Vst1,
- CurrentSt = St0#st{ct=[[Fail]|Fails]},
-
- %% Set the initial state at the try/catch label.
- %% Assume that Y registers contain terms or try/catch
- %% tags.
- Yregs0 = map(fun({Y,uninitialized}) -> {Y,term};
- ({Y,initialized}) -> {Y,term};
- (E) -> E
- end, gb_trees:to_list(CurrentSt#st.y)),
- Yregs = gb_trees:from_orddict(Yregs0),
- BranchSt = CurrentSt#st{y=Yregs},
-
- Vst = branch_state(Fail, Vst1#vst{current=BranchSt}),
- Vst#vst{current=CurrentSt}.
-
-%% Update branched state if necessary and try next set of instructions.
-valfun_2(I, #vst{current=#st{ct=[]}}=Vst) ->
- valfun_3(I, Vst);
+ St = St0#st{ct=[[Fail]|Fails]},
+ Vst = Vst0#vst{current=St},
+
+ branch(Fail, Vst,
+ fun(CatchVst) ->
+ #vst{current=#st{ys=Ys}} = CatchVst,
+ maps:fold(fun init_catch_handler_1/3, CatchVst, Ys)
+ end,
+ fun(SuccVst) ->
+ %% All potentially-throwing instructions after this
+ %% one will implicitly branch to the fail label;
+ %% see valfun_2/2
+ SuccVst
+ end).
+
+%% Set the initial state at the try/catch label. Assume that Y registers
+%% contain terms or try/catch tags.
+init_catch_handler_1(Reg, initialized, Vst) ->
+ create_term(term, 'catch_handler', [], Reg, Vst);
+init_catch_handler_1(Reg, uninitialized, Vst) ->
+ create_term(term, 'catch_handler', [], Reg, Vst);
+init_catch_handler_1(_, _, Vst) ->
+ Vst.
+
valfun_2(I, #vst{current=#st{ct=[[Fail]|_]}}=Vst) when is_integer(Fail) ->
- %% Update branched state.
+ %% We have an active try/catch tag and we can jump there from this
+ %% instruction, so we need to update the branched state of the try/catch
+ %% handler.
valfun_3(I, branch_state(Fail, Vst));
+valfun_2(I, #vst{current=#st{ct=[]}}=Vst) ->
+ valfun_3(I, Vst);
valfun_2(_, _) ->
error(ambiguous_catch_try_state).
%% Handle the remaining floating point instructions here.
%% Floating point.
-valfun_3({fconv,Src,{fr,_}=Dst}, Vst0) ->
- assert_term(Src, Vst0),
- Vst = update_type(fun meet/2, number, Src, Vst0),
- set_freg(Dst, Vst);
+valfun_3({fconv,Src,{fr,_}=Dst}, Vst) ->
+ assert_term(Src, Vst),
+
+ %% An exception is raised on error, hence branching to 0.
+ branch(0, Vst,
+ fun(SuccVst0) ->
+ SuccVst = update_type(fun meet/2, number, Src, SuccVst0),
+ set_freg(Dst, SuccVst)
+ end);
valfun_3({bif,fadd,_,[_,_]=Ss,Dst}, Vst) ->
float_op(Ss, Dst, Vst);
valfun_3({bif,fdiv,_,[_,_]=Ss,Dst}, Vst) ->
@@ -608,68 +695,87 @@ valfun_4({call_ext_last,_,_,_}, #vst{current=#st{numy=NumY}}) ->
valfun_4({make_fun2,_,_,_,Live}, Vst) ->
call(make_fun, Live, Vst);
%% Other BIFs
-valfun_4({bif,element,{f,Fail},[Pos,Tuple],Dst}, Vst0) ->
- PosType = get_durable_term_type(Pos, Vst0),
- ElementType = case PosType of
- {integer,I} -> get_element_type(I, Tuple, Vst0);
- _ -> term
- end,
- InferredType = {tuple,[get_tuple_size(PosType)],#{}},
- Vst1 = branch_state(Fail, Vst0),
- Vst = update_type(fun meet/2, InferredType, Tuple, Vst1),
- extract_term(ElementType, {bif,element}, [Tuple], Dst, Vst);
+valfun_4({bif,element,{f,Fail},[Pos,Src],Dst}, Vst) ->
+ branch(Fail, Vst,
+ fun(SuccVst0) ->
+ PosType = get_term_type(Pos, SuccVst0),
+ TupleType = {tuple,[get_tuple_size(PosType)],#{}},
+
+ SuccVst1 = update_type(fun meet/2, TupleType,
+ Src, SuccVst0),
+ SuccVst = update_type(fun meet/2, {integer,[]},
+ Pos, SuccVst1),
+
+ ElementType = get_element_type(PosType, Src, SuccVst),
+ extract_term(ElementType, {bif,element}, [Pos,Src],
+ Dst, SuccVst)
+ end);
valfun_4({bif,raise,{f,0},Src,_Dst}, Vst) ->
validate_src(Src, Vst),
kill_state(Vst);
valfun_4(raw_raise=I, Vst) ->
call(I, 3, Vst);
-valfun_4({bif,Op,{f,Fail},[Cons]=Ss,Dst}, Vst0)
- when Op =:= hd; Op =:= tl ->
- validate_src(Ss, Vst0),
- Vst = type_test(Fail, cons, Cons, Vst0),
- Type = bif_return_type(Op, Ss, Vst),
- extract_term(Type, {bif,Op}, Ss, Dst, Vst);
-valfun_4({bif,Op,{f,Fail},Ss,Dst}, Vst0) ->
- validate_src(Ss, Vst0),
- Vst1 = branch_state(Fail, Vst0),
-
- %% Infer argument types. Note that we can't type_test in the general case
- %% as the BIF could fail for reasons other than bad arguments.
- ArgTypes = bif_arg_types(Op, Ss),
- Vst = foldl(fun({Arg, T}, Vsti) ->
- update_type(fun meet/2, T, Arg, Vsti)
- end, Vst1, zip(Ss, ArgTypes)),
-
- Type = bif_return_type(Op, Ss, Vst),
- extract_term(Type, {bif,Op}, Ss, Dst, Vst);
+valfun_4({bif,Op,{f,Fail},[Src]=Ss,Dst}, Vst) when Op =:= hd; Op =:= tl ->
+ assert_term(Src, Vst),
+ branch(Fail, Vst,
+ fun(FailVst) ->
+ update_type(fun subtract/2, cons, Src, FailVst)
+ end,
+ fun(SuccVst0) ->
+ SuccVst = update_type(fun meet/2, cons, Src, SuccVst0),
+ extract_term(term, {bif,Op}, Ss, Dst, SuccVst)
+ end);
+valfun_4({bif,Op,{f,Fail},Ss,Dst}, Vst) ->
+ validate_src(Ss, Vst),
+ branch(Fail, Vst,
+ fun(SuccVst0) ->
+ %% Infer argument types. Note that we can't subtract
+ %% types as the BIF could fail for reasons other than
+ %% bad argument types.
+ ArgTypes = bif_arg_types(Op, Ss),
+ SuccVst = foldl(fun({Arg, T}, V) ->
+ update_type(fun meet/2, T, Arg, V)
+ end, SuccVst0, zip(Ss, ArgTypes)),
+ Type = bif_return_type(Op, Ss, SuccVst),
+ extract_term(Type, {bif,Op}, Ss, Dst, SuccVst)
+ end);
valfun_4({gc_bif,Op,{f,Fail},Live,Ss,Dst}, #vst{current=St0}=Vst0) ->
validate_src(Ss, Vst0),
verify_live(Live, Vst0),
verify_y_init(Vst0),
+
+ %% Heap allocations and X registers are killed regardless of whether we
+ %% fail or not, as we may fail after GC.
St = kill_heap_allocation(St0),
- Vst1 = Vst0#vst{current=St},
- Vst2 = branch_state(Fail, Vst1),
+ Vst = prune_x_regs(Live, Vst0#vst{current=St}),
- ArgTypes = bif_arg_types(Op, Ss),
- Vst3 = foldl(fun({Arg, T}, Vsti) ->
- update_type(fun meet/2, T, Arg, Vsti)
- end, Vst2, zip(Ss, ArgTypes)),
+ branch(Fail, Vst,
+ fun(SuccVst0) ->
+ ArgTypes = bif_arg_types(Op, Ss),
+ SuccVst = foldl(fun({Arg, T}, V) ->
+ update_type(fun meet/2, T, Arg, V)
+ end, SuccVst0, zip(Ss, ArgTypes)),
- Type = bif_return_type(Op, Ss, Vst3),
- Vst = prune_x_regs(Live, Vst3),
- extract_term(Type, {gc_bif,Op}, Ss, Dst, Vst, Vst0);
+ Type = bif_return_type(Op, Ss, SuccVst),
+
+ %% We're passing Vst0 as the original because the
+ %% registers were pruned before the branch.
+ extract_term(Type, {gc_bif,Op}, Ss, Dst, SuccVst, Vst0)
+ end);
valfun_4(return, #vst{current=#st{numy=none}}=Vst) ->
- assert_not_fragile({x,0}, Vst),
+ assert_durable_term({x,0}, Vst),
kill_state(Vst);
valfun_4(return, #vst{current=#st{numy=NumY}}) ->
error({stack_frame,NumY});
-valfun_4({loop_rec,{f,Fail},Dst}, Vst0) ->
- Vst = branch_state(Fail, Vst0),
- %% This term may not be part of the root set until
- %% remove_message/0 is executed. If control transfers
- %% to the loop_rec_end/1 instruction, no part of
- %% this term must be stored in a Y register.
- create_term({fragile,term}, loop_rec, [], Dst, Vst);
+valfun_4({loop_rec,{f,Fail},Dst}, Vst) ->
+ %% This term may not be part of the root set until remove_message/0 is
+ %% executed. If control transfers to the loop_rec_end/1 instruction, no
+ %% part of this term must be stored in a Y register.
+ branch(Fail, Vst,
+ fun(SuccVst0) ->
+ {Ref, SuccVst} = new_value(term, loop_rec, [], SuccVst0),
+ mark_fragile(Dst, set_reg_vref(Ref, Dst, SuccVst))
+ end);
valfun_4({wait,_}, Vst) ->
verify_y_init(Vst),
kill_state(Vst);
@@ -680,30 +786,30 @@ valfun_4({wait_timeout,_,Src}, Vst) ->
valfun_4({loop_rec_end,_}, Vst) ->
verify_y_init(Vst),
kill_state(Vst);
-valfun_4(timeout, #vst{current=St}=Vst) ->
- Vst#vst{current=St#st{x=init_regs(0, term)}};
+valfun_4(timeout, Vst) ->
+ prune_x_regs(0, Vst);
valfun_4(send, Vst) ->
call(send, 2, Vst);
valfun_4({set_tuple_element,Src,Tuple,N}, Vst) ->
I = N + 1,
- assert_not_fragile(Src, Vst),
+ assert_term(Src, Vst),
assert_type({tuple_element,I}, Tuple, Vst),
%% Manually update the tuple type; we can't rely on the ordinary update
%% helpers as we must support overwriting (rather than just widening or
%% narrowing) known elements, and we can't use extract_term either since
%% the source tuple may be aliased.
{tuple, Sz, Es0} = get_term_type(Tuple, Vst),
- Es = set_element_type(I, get_term_type(Src, Vst), Es0),
+ Es = set_element_type({integer,I}, get_term_type(Src, Vst), Es0),
override_type({tuple, Sz, Es}, Tuple, Vst);
%% Match instructions.
-valfun_4({select_val,Src,{f,Fail},{list,Choices}}, Vst0) ->
- assert_term(Src, Vst0),
+valfun_4({select_val,Src,{f,Fail},{list,Choices}}, Vst) ->
+ assert_term(Src, Vst),
assert_choices(Choices),
- select_val_branches(Fail, Src, Choices, Vst0);
+ validate_select_val(Fail, Choices, Src, Vst);
valfun_4({select_tuple_arity,Tuple,{f,Fail},{list,Choices}}, Vst) ->
assert_type(tuple, Tuple, Vst),
assert_arities(Choices),
- select_arity_branches(Fail, Choices, Tuple, Vst);
+ validate_select_tuple_arity(Fail, Choices, Tuple, Vst);
%% New bit syntax matching instructions.
valfun_4({test,bs_start_match3,{f,Fail},Live,[Src],Dst}, Vst) ->
@@ -712,17 +818,17 @@ valfun_4({test,bs_start_match2,{f,Fail},Live,[Src,Slots],Dst}, Vst) ->
validate_bs_start_match(Fail, Live, bsm_match_state(Slots), Src, Dst, Vst);
valfun_4({test,bs_match_string,{f,Fail},[Ctx,_,_]}, Vst) ->
bsm_validate_context(Ctx, Vst),
- branch_state(Fail, Vst);
+ branch(Fail, Vst, fun(V) -> V end);
valfun_4({test,bs_skip_bits2,{f,Fail},[Ctx,Src,_,_]}, Vst) ->
bsm_validate_context(Ctx, Vst),
assert_term(Src, Vst),
- branch_state(Fail, Vst);
+ branch(Fail, Vst, fun(V) -> V end);
valfun_4({test,bs_test_tail2,{f,Fail},[Ctx,_]}, Vst) ->
bsm_validate_context(Ctx, Vst),
- branch_state(Fail, Vst);
+ branch(Fail, Vst, fun(V) -> V end);
valfun_4({test,bs_test_unit,{f,Fail},[Ctx,_]}, Vst) ->
bsm_validate_context(Ctx, Vst),
- branch_state(Fail, Vst);
+ branch(Fail, Vst, fun(V) -> V end);
valfun_4({test,bs_skip_utf8,{f,Fail},[Ctx,Live,_]}, Vst) ->
validate_bs_skip_utf(Fail, Ctx, Live, Vst);
valfun_4({test,bs_skip_utf16,{f,Fail},[Ctx,Live,_]}, Vst) ->
@@ -750,15 +856,23 @@ valfun_4({bs_get_position, Ctx, Dst, Live}, Vst0) ->
verify_live(Live, Vst0),
verify_y_init(Vst0),
Vst = prune_x_regs(Live, Vst0),
- create_term(bs_position, bs_get_position, [Ctx], Dst, Vst);
+ create_term(ms_position, bs_get_position, [Ctx], Dst, Vst, Vst0);
valfun_4({bs_set_position, Ctx, Pos}, Vst) ->
bsm_validate_context(Ctx, Vst),
- assert_type(bs_position, Pos, Vst),
+ assert_type(ms_position, Pos, Vst),
Vst;
%% Other test instructions.
+valfun_4({test,has_map_fields,{f,Lbl},Src,{list,List}}, Vst) ->
+ assert_type(map, Src, Vst),
+ assert_unique_map_keys(List),
+ branch(Lbl, Vst, fun(V) -> V end);
valfun_4({test,is_atom,{f,Lbl},[Src]}, Vst) ->
type_test(Lbl, {atom,[]}, Src, Vst);
+valfun_4({test,is_binary,{f,Lbl},[Src]}, Vst) ->
+ type_test(Lbl, binary, Src, Vst);
+valfun_4({test,is_bitstr,{f,Lbl},[Src]}, Vst) ->
+ type_test(Lbl, binary, Src, Vst);
valfun_4({test,is_boolean,{f,Lbl},[Src]}, Vst) ->
type_test(Lbl, bool, Src, Vst);
valfun_4({test,is_float,{f,Lbl},[Src]}, Vst) ->
@@ -769,63 +883,72 @@ valfun_4({test,is_integer,{f,Lbl},[Src]}, Vst) ->
type_test(Lbl, {integer,[]}, Src, Vst);
valfun_4({test,is_nonempty_list,{f,Lbl},[Src]}, Vst) ->
type_test(Lbl, cons, Src, Vst);
+valfun_4({test,is_number,{f,Lbl},[Src]}, Vst) ->
+ type_test(Lbl, number, Src, Vst);
valfun_4({test,is_list,{f,Lbl},[Src]}, Vst) ->
type_test(Lbl, list, Src, Vst);
-valfun_4({test,is_nil,{f,Lbl},[Src]}, Vst) ->
- type_test(Lbl, nil, Src, Vst);
valfun_4({test,is_map,{f,Lbl},[Src]}, Vst) ->
- case Src of
- {Tag,_} when Tag =:= x; Tag =:= y ->
- type_test(Lbl, map, Src, Vst);
- {literal,Map} when is_map(Map) ->
- Vst;
- _ ->
- assert_term(Src, Vst),
- kill_state(Vst)
- end;
-valfun_4({test,test_arity,{f,Lbl},[Tuple,Sz]}, Vst0) when is_integer(Sz) ->
- assert_type(tuple, Tuple, Vst0),
- Vst = branch_state(Lbl, Vst0),
- update_type(fun meet/2, {tuple,Sz,#{}}, Tuple, Vst);
-valfun_4({test,is_tagged_tuple,{f,Lbl},[Src,Sz,Atom]}, Vst0) ->
- assert_term(Src, Vst0),
- Vst = branch_state(Lbl, Vst0),
- update_type(fun meet/2, {tuple,Sz,#{ 1 => Atom }}, Src, Vst);
-valfun_4({test,has_map_fields,{f,Lbl},Src,{list,List}}, Vst) ->
- assert_type(map, Src, Vst),
- assert_unique_map_keys(List),
- branch_state(Lbl, Vst);
+ type_test(Lbl, map, Src, Vst);
+valfun_4({test,is_nil,{f,Lbl},[Src]}, Vst) ->
+ %% is_nil is an exact check against the 'nil' value, and should not be
+ %% treated as a simple type test.
+ assert_term(Src, Vst),
+ branch(Lbl, Vst,
+ fun(FailVst) ->
+ update_ne_types(Src, nil, FailVst)
+ end,
+ fun(SuccVst) ->
+ update_eq_types(Src, nil, SuccVst)
+ end);
+valfun_4({test,test_arity,{f,Lbl},[Tuple,Sz]}, Vst) when is_integer(Sz) ->
+ assert_type(tuple, Tuple, Vst),
+ Type = {tuple, Sz, #{}},
+ type_test(Lbl, Type, Tuple, Vst);
+valfun_4({test,is_tagged_tuple,{f,Lbl},[Src,Sz,Atom]}, Vst) ->
+ assert_term(Src, Vst),
+ Type = {tuple, Sz, #{ {integer,1} => Atom }},
+ type_test(Lbl, Type, Src, Vst);
valfun_4({test,is_eq_exact,{f,Lbl},[Src,Val]=Ss}, Vst) ->
validate_src(Ss, Vst),
- complex_test(Lbl,
- fun(FailVst) ->
- update_ne_types(Src, Val, FailVst)
- end,
- fun(SuccVst) ->
- update_eq_types(Src, Val, SuccVst)
- end, Vst);
+ branch(Lbl, Vst,
+ fun(FailVst) ->
+ update_ne_types(Src, Val, FailVst)
+ end,
+ fun(SuccVst) ->
+ update_eq_types(Src, Val, SuccVst)
+ end);
valfun_4({test,is_ne_exact,{f,Lbl},[Src,Val]=Ss}, Vst) ->
validate_src(Ss, Vst),
- complex_test(Lbl,
- fun(FailVst) ->
- update_eq_types(Src, Val, FailVst)
- end,
- fun(SuccVst) ->
- update_ne_types(Src, Val, SuccVst)
- end, Vst);
+ branch(Lbl, Vst,
+ fun(FailVst) ->
+ update_eq_types(Src, Val, FailVst)
+ end,
+ fun(SuccVst) ->
+ update_ne_types(Src, Val, SuccVst)
+ end);
valfun_4({test,_Op,{f,Lbl},Src}, Vst) ->
+ %% is_pid, is_reference, et cetera.
validate_src(Src, Vst),
- branch_state(Lbl, Vst);
+ branch(Lbl, Vst, fun(V) -> V end);
valfun_4({bs_add,{f,Fail},[A,B,_],Dst}, Vst) ->
- assert_not_fragile(A, Vst),
- assert_not_fragile(B, Vst),
- create_term({integer,[]}, bs_add, [A, B], Dst, branch_state(Fail, Vst));
+ assert_term(A, Vst),
+ assert_term(B, Vst),
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ create_term({integer,[]}, bs_add, [A, B], Dst, SuccVst)
+ end);
valfun_4({bs_utf8_size,{f,Fail},A,Dst}, Vst) ->
assert_term(A, Vst),
- create_term({integer,[]}, bs_utf8_size, [A], Dst, branch_state(Fail, Vst));
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ create_term({integer,[]}, bs_utf8_size, [A], Dst, SuccVst)
+ end);
valfun_4({bs_utf16_size,{f,Fail},A,Dst}, Vst) ->
assert_term(A, Vst),
- create_term({integer,[]}, bs_utf16_size, [A], Dst, branch_state(Fail, Vst));
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ create_term({integer,[]}, bs_utf16_size, [A], Dst, SuccVst)
+ end);
valfun_4({bs_init2,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) ->
verify_live(Live, Vst0),
verify_y_init(Vst0),
@@ -833,12 +956,14 @@ valfun_4({bs_init2,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) ->
is_integer(Sz) ->
ok;
true ->
- assert_not_fragile(Sz, Vst0)
+ assert_term(Sz, Vst0)
end,
- Vst1 = heap_alloc(Heap, Vst0),
- Vst2 = branch_state(Fail, Vst1),
- Vst = prune_x_regs(Live, Vst2),
- create_term(binary, bs_init2, [], Dst, Vst);
+ Vst = heap_alloc(Heap, Vst0),
+ branch(Fail, Vst,
+ fun(SuccVst0) ->
+ SuccVst = prune_x_regs(Live, SuccVst0),
+ create_term(binary, bs_init2, [], Dst, SuccVst, SuccVst0)
+ end);
valfun_4({bs_init_bits,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) ->
verify_live(Live, Vst0),
verify_y_init(Vst0),
@@ -848,47 +973,71 @@ valfun_4({bs_init_bits,{f,Fail},Sz,Heap,Live,_,Dst}, Vst0) ->
true ->
assert_term(Sz, Vst0)
end,
- Vst1 = heap_alloc(Heap, Vst0),
- Vst2 = branch_state(Fail, Vst1),
- Vst = prune_x_regs(Live, Vst2),
- create_term(binary, bs_init_bits, [], Dst, Vst);
+ Vst = heap_alloc(Heap, Vst0),
+ branch(Fail, Vst,
+ fun(SuccVst0) ->
+ SuccVst = prune_x_regs(Live, SuccVst0),
+ create_term(binary, bs_init_bits, [], Dst, SuccVst)
+ end);
valfun_4({bs_append,{f,Fail},Bits,Heap,Live,_Unit,Bin,_Flags,Dst}, Vst0) ->
verify_live(Live, Vst0),
verify_y_init(Vst0),
- assert_not_fragile(Bits, Vst0),
- assert_not_fragile(Bin, Vst0),
- Vst1 = heap_alloc(Heap, Vst0),
- Vst2 = branch_state(Fail, Vst1),
- Vst = prune_x_regs(Live, Vst2),
- create_term(binary, bs_append, [Bin], Dst, Vst);
-valfun_4({bs_private_append,{f,Fail},Bits,_Unit,Bin,_Flags,Dst}, Vst0) ->
- assert_not_fragile(Bits, Vst0),
- assert_not_fragile(Bin, Vst0),
- Vst = branch_state(Fail, Vst0),
- create_term(binary, bs_private_append, [Bin], Dst, Vst);
+ assert_term(Bits, Vst0),
+ assert_term(Bin, Vst0),
+ Vst = heap_alloc(Heap, Vst0),
+ branch(Fail, Vst,
+ fun(SuccVst0) ->
+ SuccVst = prune_x_regs(Live, SuccVst0),
+ create_term(binary, bs_append, [Bin], Dst, SuccVst, SuccVst0)
+ end);
+valfun_4({bs_private_append,{f,Fail},Bits,_Unit,Bin,_Flags,Dst}, Vst) ->
+ assert_term(Bits, Vst),
+ assert_term(Bin, Vst),
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ create_term(binary, bs_private_append, [Bin], Dst, SuccVst)
+ end);
valfun_4({bs_put_string,Sz,_}, Vst) when is_integer(Sz) ->
Vst;
valfun_4({bs_put_binary,{f,Fail},Sz,_,_,Src}, Vst) ->
- assert_not_fragile(Sz, Vst),
- assert_not_fragile(Src, Vst),
- branch_state(Fail, Vst);
+ assert_term(Sz, Vst),
+ assert_term(Src, Vst),
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ update_type(fun meet/2, binary, Src, SuccVst)
+ end);
valfun_4({bs_put_float,{f,Fail},Sz,_,_,Src}, Vst) ->
- assert_not_fragile(Sz, Vst),
- assert_not_fragile(Src, Vst),
- branch_state(Fail, Vst);
+ assert_term(Sz, Vst),
+ assert_term(Src, Vst),
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ update_type(fun meet/2, {float,[]}, Src, SuccVst)
+ end);
valfun_4({bs_put_integer,{f,Fail},Sz,_,_,Src}, Vst) ->
- assert_not_fragile(Sz, Vst),
- assert_not_fragile(Src, Vst),
- branch_state(Fail, Vst);
+ assert_term(Sz, Vst),
+ assert_term(Src, Vst),
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ update_type(fun meet/2, {integer,[]}, Src, SuccVst)
+ end);
valfun_4({bs_put_utf8,{f,Fail},_,Src}, Vst) ->
- assert_not_fragile(Src, Vst),
- branch_state(Fail, Vst);
+ assert_term(Src, Vst),
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ update_type(fun meet/2, {integer,[]}, Src, SuccVst)
+ end);
valfun_4({bs_put_utf16,{f,Fail},_,Src}, Vst) ->
- assert_not_fragile(Src, Vst),
- branch_state(Fail, Vst);
+ assert_term(Src, Vst),
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ update_type(fun meet/2, {integer,[]}, Src, SuccVst)
+ end);
valfun_4({bs_put_utf32,{f,Fail},_,Src}, Vst) ->
- assert_not_fragile(Src, Vst),
- branch_state(Fail, Vst);
+ assert_term(Src, Vst),
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ update_type(fun meet/2, {integer,[]}, Src, SuccVst)
+ end);
%% Map instructions.
valfun_4({put_map_assoc=Op,{f,Fail},Src,Dst,Live,{list,List}}, Vst) ->
verify_put_map(Op, Fail, Src, Dst, Live, List, Vst);
@@ -903,15 +1052,15 @@ verify_get_map(Fail, Src, List, Vst0) ->
assert_not_literal(Src), %OTP 22.
assert_type(map, Src, Vst0),
- complex_test(Fail,
- fun(FailVst) ->
- clobber_map_vals(List, Src, FailVst)
- end,
- fun(SuccVst) ->
- Keys = extract_map_keys(List),
- assert_unique_map_keys(Keys),
- extract_map_vals(List, Src, SuccVst, SuccVst)
- end, Vst0).
+ branch(Fail, Vst0,
+ fun(FailVst) ->
+ clobber_map_vals(List, Src, FailVst)
+ end,
+ fun(SuccVst) ->
+ Keys = extract_map_keys(List),
+ assert_unique_map_keys(Keys),
+ extract_map_vals(List, Src, SuccVst, SuccVst)
+ end).
%% get_map_elements may leave its destinations in an inconsistent state when
%% the fail label is taken. Consider the following:
@@ -945,13 +1094,16 @@ verify_put_map(Op, Fail, Src, Dst, Live, List, Vst0) ->
assert_type(map, Src, Vst0),
verify_live(Live, Vst0),
verify_y_init(Vst0),
- [assert_not_fragile(Term, Vst0) || Term <- List],
- Vst1 = heap_alloc(0, Vst0),
- Vst2 = branch_state(Fail, Vst1),
- Vst = prune_x_regs(Live, Vst2),
- Keys = extract_map_keys(List),
- assert_unique_map_keys(Keys),
- create_term(map, Op, [Src], Dst, Vst).
+ _ = [assert_term(Term, Vst0) || Term <- List],
+ Vst = heap_alloc(0, Vst0),
+
+ branch(Fail, Vst,
+ fun(SuccVst0) ->
+ SuccVst = prune_x_regs(Live, SuccVst0),
+ Keys = extract_map_keys(List),
+ assert_unique_map_keys(Keys),
+ create_term(map, Op, [Src], Dst, SuccVst, SuccVst0)
+ end).
%%
%% Common code for validating bs_start_match* instructions.
@@ -962,40 +1114,62 @@ validate_bs_start_match(Fail, Live, Type, Src, Dst, Vst) ->
verify_y_init(Vst),
%% #ms{} can represent either a match context or a term, so we have to mark
- %% the source as a term if it fails, and retain the incoming type if it
- %% succeeds (match context or not).
- %%
- %% The override_type hack is only needed until we get proper union types.
- complex_test(Fail,
- fun(FailVst) ->
- override_type(term, Src, FailVst)
- end,
- fun(SuccVst0) ->
- SuccVst = prune_x_regs(Live, SuccVst0),
- extract_term(Type, bs_start_match, [Src], Dst,
- SuccVst, Vst)
- end, Vst).
+ %% the source as a term if it fails with a match context as an input. This
+ %% hack is only needed until we get proper union types.
+ branch(Fail, Vst,
+ fun(FailVst) ->
+ case get_movable_term_type(Src, FailVst) of
+ #ms{} -> override_type(term, Src, FailVst);
+ _ -> FailVst
+ end
+ end,
+ fun(SuccVst0) ->
+ SuccVst1 = update_type(fun meet/2, binary,
+ Src, SuccVst0),
+ SuccVst = prune_x_regs(Live, SuccVst1),
+ extract_term(Type, bs_start_match, [Src], Dst,
+ SuccVst, SuccVst0)
+ end).
%%
%% Common code for validating bs_get* instructions.
%%
-validate_bs_get(Op, Fail, Ctx, Live, Type, Dst, Vst0) ->
- bsm_validate_context(Ctx, Vst0),
- verify_live(Live, Vst0),
- verify_y_init(Vst0),
- Vst1 = prune_x_regs(Live, Vst0),
- Vst = branch_state(Fail, Vst1),
- extract_term(Type, Op, [Ctx], Dst, Vst).
+validate_bs_get(Op, Fail, Ctx, Live, Type, Dst, Vst) ->
+ bsm_validate_context(Ctx, Vst),
+ verify_live(Live, Vst),
+ verify_y_init(Vst),
+
+ branch(Fail, Vst,
+ fun(SuccVst0) ->
+ SuccVst = prune_x_regs(Live, SuccVst0),
+ extract_term(Type, Op, [Ctx], Dst, SuccVst, SuccVst0)
+ end).
%%
%% Common code for validating bs_skip_utf* instructions.
%%
-validate_bs_skip_utf(Fail, Ctx, Live, Vst0) ->
- bsm_validate_context(Ctx, Vst0),
- verify_y_init(Vst0),
- verify_live(Live, Vst0),
- Vst = prune_x_regs(Live, Vst0),
- branch_state(Fail, Vst).
+validate_bs_skip_utf(Fail, Ctx, Live, Vst) ->
+ bsm_validate_context(Ctx, Vst),
+ verify_y_init(Vst),
+ verify_live(Live, Vst),
+
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ prune_x_regs(Live, SuccVst)
+ end).
+
+%%
+%% Common code for is_$type instructions.
+%%
+type_test(Fail, Type, Reg, Vst) ->
+ assert_term(Reg, Vst),
+ branch(Fail, Vst,
+ fun(FailVst) ->
+ update_type(fun subtract/2, Type, Reg, FailVst)
+ end,
+ fun(SuccVst) ->
+ update_type(fun meet/2, Type, Reg, SuccVst)
+ end).
%%
%% Special state handling for setelement/3 and set_tuple_element/3 instructions.
@@ -1032,7 +1206,7 @@ call(Name, Live, #vst{current=St0}=Vst0) ->
case call_return_type(Name, Vst0) of
Type when Type =/= exception ->
%% Type is never 'exception' because it has been handled earlier.
- St = St0#st{f=init_fregs(),aliases=#{}},
+ St = St0#st{f=init_fregs()},
Vst = prune_x_regs(0, Vst0#vst{current=St}),
create_term(Type, call, [], {x,0}, Vst)
end.
@@ -1059,14 +1233,15 @@ verify_call_args(_, Live, _) ->
verify_remote_args_1(-1, _) ->
ok;
verify_remote_args_1(X, Vst) ->
- assert_not_fragile({x, X}, Vst),
+ assert_durable_term({x, X}, Vst),
verify_remote_args_1(X - 1, Vst).
verify_local_args(-1, _Lbl, _CtxIds, _Vst) ->
ok;
verify_local_args(X, Lbl, CtxIds, Vst) ->
Reg = {x, X},
- case get_raw_type(Reg, Vst) of
+ assert_not_fragile(Reg, Vst),
+ case get_movable_term_type(Reg, Vst) of
#ms{id=Id}=Type ->
case CtxIds of
#{ Id := Other } ->
@@ -1075,8 +1250,6 @@ verify_local_args(X, Lbl, CtxIds, Vst) ->
verify_arg_type(Lbl, Reg, Type, Vst),
verify_local_args(X - 1, Lbl, CtxIds#{ Id => Reg }, Vst)
end;
- {fragile,_} ->
- error({fragile_message_reference, Reg});
Type ->
verify_arg_type(Lbl, Reg, Type, Vst),
verify_local_args(X - 1, Lbl, CtxIds, Vst)
@@ -1092,56 +1265,89 @@ verify_arg_type(Lbl, Reg, #ms{}, #vst{ft=Ft}) ->
end;
verify_arg_type(Lbl, Reg, GivenType, #vst{ft=Ft}) ->
case gb_trees:lookup({Lbl, Reg}, Ft) of
- {value, bool} when GivenType =:= {atom, true};
- GivenType =:= {atom, false};
- GivenType =:= {atom, []} ->
- %% We don't yet support upgrading true/false to bool, so we
- %% assume unknown atoms can be bools when validating calls.
- ok;
{value, #ms{}} ->
%% Functions that accept match contexts also accept all other
%% terms. This will change once we support union types.
ok;
{value, RequiredType} ->
- case meet(GivenType, RequiredType) of
- none -> error({bad_arg_type, Reg, GivenType, RequiredType});
- _ -> ok
+ case vat_1(GivenType, RequiredType) of
+ true -> ok;
+ false -> error({bad_arg_type, Reg, GivenType, RequiredType})
end;
none ->
ok
end.
-allocate(Zero, Stk, Heap, Live, #vst{current=#st{numy=none}}=Vst0) ->
+%% Checks whether the Given argument is compatible with the Required one. This
+%% is essentially a relaxed version of 'meet(Given, Req) =:= Given', where we
+%% accept that the Given value has the right type but not necessarily the exact
+%% same value; if {atom,gurka} is required, we'll consider {atom,[]} valid.
+%%
+%% This will catch all problems that could crash the emulator, like passing a
+%% 1-tuple when the callee expects a 3-tuple, but some value errors might slip
+%% through.
+vat_1(Same, Same) -> true;
+vat_1({atom,A}, {atom,B}) -> A =:= B orelse is_list(A) orelse is_list(B);
+vat_1({atom,A}, bool) -> is_boolean(A) orelse is_list(A);
+vat_1(bool, {atom,B}) -> is_boolean(B) orelse is_list(B);
+vat_1(cons, list) -> true;
+vat_1({float,A}, {float,B}) -> A =:= B orelse is_list(A) orelse is_list(B);
+vat_1({float,_}, number) -> true;
+vat_1({integer,A}, {integer,B}) -> A =:= B orelse is_list(A) orelse is_list(B);
+vat_1({integer,_}, number) -> true;
+vat_1(_, {literal,_}) -> false;
+vat_1({literal,_}=Lit, Required) -> vat_1(get_literal_type(Lit), Required);
+vat_1(nil, list) -> true;
+vat_1({tuple,SzA,EsA}, {tuple,SzB,EsB}) ->
+ if
+ is_list(SzB) ->
+ tuple_sz(SzA) >= tuple_sz(SzB) andalso vat_elements(EsA, EsB);
+ SzA =:= SzB ->
+ vat_elements(EsA, EsB);
+ SzA =/= SzB ->
+ false
+ end;
+vat_1(_, _) -> false.
+
+vat_elements(EsA, EsB) ->
+ maps:fold(fun(Key, Req, Acc) ->
+ case EsA of
+ #{ Key := Given } -> Acc andalso vat_1(Given, Req);
+ #{} -> false
+ end
+ end, true, EsB).
+
+allocate(Tag, Stk, Heap, Live, #vst{current=#st{numy=none}=St}=Vst0) ->
verify_live(Live, Vst0),
- Vst = #vst{current=St} = prune_x_regs(Live, Vst0),
- Ys = init_regs(Stk, case Zero of
- true -> initialized;
- false -> uninitialized
- end),
- heap_alloc(Heap, Vst#vst{current=St#st{y=Ys,numy=Stk}});
+ Vst1 = Vst0#vst{current=St#st{numy=Stk}},
+ Vst2 = prune_x_regs(Live, Vst1),
+ Vst = init_stack(Tag, Stk - 1, Vst2),
+ heap_alloc(Heap, Vst);
allocate(_, _, _, _, #vst{current=#st{numy=Numy}}) ->
error({existing_stack_frame,{size,Numy}}).
deallocate(#vst{current=St}=Vst) ->
- Vst#vst{current=St#st{y=init_regs(0, initialized),numy=none}}.
-
-trim_stack(From, To, Top, #st{y=Ys0}=St) when From =:= Top ->
- Ys = foldl(fun(Y, Acc) ->
- gb_trees:delete(Y, Acc)
- end, Ys0, seq(To, From - 1)),
- %% Note that all aliases and defs are wiped. This is perhaps a bit too
- %% conservative, but preserving them won't be easy until type management
- %% is refactored.
- St#st{aliases=#{},defs=#{},numy=To,y=Ys};
+ Vst#vst{current=St#st{ys=#{},numy=none}}.
+
+init_stack(_Tag, -1, Vst) ->
+ Vst;
+init_stack(Tag, Y, Vst) ->
+ init_stack(Tag, Y - 1, create_tag(Tag, allocate, [], {y,Y}, Vst)).
+
+trim_stack(From, To, Top, #st{ys=Ys0}=St) when From =:= Top ->
+ Ys = maps:filter(fun({y,Y}, _) -> Y < To end, Ys0),
+ St#st{numy=To,ys=Ys};
trim_stack(From, To, Top, St0) ->
- #st{y=Ys0} = St0,
+ Src = {y, From},
+ Dst = {y, To},
- Ys = case gb_trees:lookup(From, Ys0) of
- none -> error({invalid_shift,{y,From},{y,To}});
- {value,Type} -> gb_trees:enter(To, Type, Ys0)
+ #st{ys=Ys0} = St0,
+ Ys = case Ys0 of
+ #{ Src := Ref } -> Ys0#{ Dst => Ref };
+ #{} -> error({invalid_shift,Src,Dst})
end,
+ St = St0#st{ys=Ys},
- St = St0#st{y=Ys},
trim_stack(From + 1, To + 1, Top, St).
test_heap(Heap, Live, Vst0) ->
@@ -1168,24 +1374,17 @@ heap_alloc_2([{floats,Floats}|T], St0) ->
heap_alloc_2(T, St);
heap_alloc_2([], St) -> St.
-prune_x_regs(Live, #vst{current=St0}=Vst)
- when is_integer(Live) ->
- #st{x=Xs0,defs=Defs0,aliases=Aliases0} = St0,
- Xs1 = gb_trees:to_list(Xs0),
- Xs = [P || {R,_}=P <- Xs1, R < Live],
- Defs = maps:filter(fun({x,X}, _) -> X < Live;
- ({y,_}, _) -> true
- end, Defs0),
- Aliases = maps:filter(fun({x,X1}, {x,X2}) ->
- X1 < Live andalso X2 < Live;
- ({x,X}, _) ->
- X < Live;
- (_, {x,X}) ->
- X < Live;
- (_, _) ->
- true
- end, Aliases0),
- St = St0#st{x=gb_trees:from_orddict(Xs),defs=Defs,aliases=Aliases},
+prune_x_regs(Live, #vst{current=St0}=Vst) when is_integer(Live) ->
+ #st{fragile=Fragile0,xs=Xs0} = St0,
+ Fragile = cerl_sets:filter(fun({x,X}) ->
+ X < Live;
+ ({y,_}) ->
+ true
+ end, Fragile0),
+ Xs = maps:filter(fun({x,X}, _) ->
+ X < Live
+ end, Xs0),
+ St = St0#st{fragile=Fragile,xs=Xs},
Vst#vst{current=St}.
%% All choices in a select_val list must be integers, floats, or atoms.
@@ -1231,7 +1430,7 @@ assert_arities(_) -> error(bad_tuple_arity_list).
%%%
float_op(Ss, Dst, Vst0) ->
- [assert_freg_set(S, Vst0) || S <- Ss],
+ _ = [assert_freg_set(S, Vst0) || S <- Ss],
assert_fls(cleared, Vst0),
Vst = set_fls(cleared, Vst0),
set_freg(Dst, Vst).
@@ -1249,8 +1448,7 @@ get_fls(#vst{current=#st{fls=Fls}}) when is_atom(Fls) -> Fls.
init_fregs() -> 0.
-set_freg({fr,Fr}=Freg, #vst{current=#st{f=Fregs0}=St}=Vst)
- when is_integer(Fr), 0 =< Fr ->
+set_freg({fr,Fr}=Freg, #vst{current=#st{f=Fregs0}=St}=Vst) ->
check_limit(Freg),
Bit = 1 bsl Fr,
if
@@ -1308,19 +1506,13 @@ bsm_validate_context(Reg, Vst) ->
_ = bsm_get_context(Reg, Vst),
ok.
-bsm_get_context({x,X}=Reg, #vst{current=#st{x=Xs}}=_Vst) when is_integer(X) ->
- case gb_trees:lookup(X, Xs) of
- {value,#ms{}=Ctx} -> Ctx;
- {value,{fragile,#ms{}=Ctx}} -> Ctx;
- _ -> error({no_bsm_context,Reg})
- end;
-bsm_get_context({y,Y}=Reg, #vst{current=#st{y=Ys}}=_Vst) when is_integer(Y) ->
- case gb_trees:lookup(Y, Ys) of
- {value,#ms{}=Ctx} -> Ctx;
- {value,{fragile,#ms{}=Ctx}} -> Ctx;
- _ -> error({no_bsm_context,Reg})
+bsm_get_context({Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y->
+ case get_movable_term_type(Reg, Vst) of
+ #ms{}=Ctx -> Ctx;
+ _ -> error({no_bsm_context,Reg})
end;
-bsm_get_context(Reg, _) -> error({bad_source,Reg}).
+bsm_get_context(Reg, _) ->
+ error({bad_source,Reg}).
bsm_save(Reg, {atom,start}, Vst) ->
%% Save point refering to where the match started.
@@ -1350,81 +1542,98 @@ bsm_restore(Reg, SavePoint, Vst) ->
_ -> error({illegal_restore,SavePoint,range})
end.
-select_val_branches(Fail, Src, Choices, Vst0) ->
- Vst = svb_1(Choices, Src, Vst0),
- kill_state(branch_state(Fail, Vst)).
-
-svb_1([Val,{f,L}|T], Src, Vst0) ->
- Vst = complex_test(L,
- fun(BranchVst) ->
- update_eq_types(Val, Src, BranchVst)
- end,
- fun(FailVst) ->
- update_ne_types(Val, Src, FailVst)
- end, Vst0),
- svb_1(T, Src, Vst);
-svb_1([], _, Vst) ->
- Vst.
-
-select_arity_branches(Fail, List, Tuple, Vst0) ->
- Type = get_durable_term_type(Tuple, Vst0),
- Vst = sab_1(List, Tuple, Type, Vst0),
- kill_state(branch_state(Fail, Vst)).
-
-sab_1([Sz,{f,L}|T], Tuple, {tuple,[_],Es}=Type0, Vst0) ->
- #vst{current=St0} = Vst0,
- Vst1 = update_type(fun meet/2, {tuple,Sz,Es}, Tuple, Vst0),
- Vst2 = branch_state(L, Vst1),
- Vst = Vst2#vst{current=St0},
-
- sab_1(T, Tuple, Type0, Vst);
-sab_1([Sz,{f,L}|T], Tuple, {tuple,Sz,_Es}=Type, Vst0) ->
- %% The type is already correct. (This test is redundant.)
- Vst = branch_state(L, Vst0),
- sab_1(T, Tuple, Type, Vst);
-sab_1([_,{f,_}|T], Tuple, Type, Vst) ->
- %% We already have an established different exact size for the tuple.
- %% This label can't possibly be reached.
- sab_1(T, Tuple, Type, Vst);
-sab_1([], _, _, #vst{}=Vst) ->
- Vst.
+validate_select_val(_Fail, _Choices, _Src, #vst{current=none}=Vst) ->
+ %% We've already branched on all of Src's possible values, so we know we
+ %% can't reach the fail label or any of the remaining choices.
+ Vst;
+validate_select_val(Fail, [Val,{f,L}|T], Src, Vst0) ->
+ Vst = branch(L, Vst0,
+ fun(BranchVst) ->
+ update_eq_types(Src, Val, BranchVst)
+ end,
+ fun(FailVst) ->
+ update_ne_types(Src, Val, FailVst)
+ end),
+ validate_select_val(Fail, T, Src, Vst);
+validate_select_val(Fail, [], _, Vst) ->
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ %% The next instruction is never executed.
+ kill_state(SuccVst)
+ end).
+
+validate_select_tuple_arity(_Fail, _Choices, _Src, #vst{current=none}=Vst) ->
+ %% We've already branched on all of Src's possible values, so we know we
+ %% can't reach the fail label or any of the remaining choices.
+ Vst;
+validate_select_tuple_arity(Fail, [Arity,{f,L}|T], Tuple, Vst0) ->
+ Type = {tuple, Arity, #{}},
+ Vst = branch(L, Vst0,
+ fun(BranchVst) ->
+ update_type(fun meet/2, Type, Tuple, BranchVst)
+ end,
+ fun(FailVst) ->
+ update_type(fun subtract/2, Type, Tuple, FailVst)
+ end),
+ validate_select_tuple_arity(Fail, T, Tuple, Vst);
+validate_select_tuple_arity(Fail, [], _, #vst{}=Vst) ->
+ branch(Fail, Vst,
+ fun(SuccVst) ->
+ %% The next instruction is never executed.
+ kill_state(SuccVst)
+ end).
+
+infer_types({Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y ->
+ infer_types(get_reg_vref(Reg, Vst), Vst);
+infer_types(#value_ref{}=Ref, #vst{current=#st{vs=Vs}}) ->
+ case Vs of
+ #{ Ref := Entry } -> infer_types_1(Entry);
+ #{} -> fun(_, S) -> S end
+ end;
+infer_types(_, #vst{}) ->
+ fun(_, S) -> S end.
-infer_types(Src, Vst) ->
- case get_def(Src, Vst) of
- {{bif,tuple_size}, [Tuple]} ->
- fun({integer,Arity}, S) ->
- update_type(fun meet/2, {tuple,Arity,#{}}, Tuple, S);
- (_, S) -> S
- end;
- {{bif,'=:='},[ArityReg,{integer,_}=Val]} when ArityReg =/= Src ->
- fun({atom,true}, S) ->
- Infer = infer_types(ArityReg, S),
- Infer(Val, S);
- (_, S) -> S
- end;
- {{bif,is_atom},[Src]} ->
- infer_type_test_bif({atom,[]}, Src);
- {{bif,is_boolean},[Src]} ->
- infer_type_test_bif(bool, Src);
- {{bif,is_binary},[Src]} ->
- infer_type_test_bif(binary, Src);
- {{bif,is_bitstring},[Src]} ->
- infer_type_test_bif(binary, Src);
- {{bif,is_float},[Src]} ->
- infer_type_test_bif(float, Src);
- {{bif,is_integer},[Src]} ->
- infer_type_test_bif({integer,{}}, Src);
- {{bif,is_list},[Src]} ->
- infer_type_test_bif(list, Src);
- {{bif,is_map},[Src]} ->
- infer_type_test_bif(map, Src);
- {{bif,is_number},[Src]} ->
- infer_type_test_bif(number, Src);
- {{bif,is_tuple},[Src]} ->
- infer_type_test_bif({tuple,[0],#{}}, Src);
- _ ->
- fun(_, S) -> S end
- end.
+infer_types_1(#value{op={bif,'=:='},args=[LHS,RHS]}) ->
+ fun({atom,true}, S) ->
+ %% Either side might contain something worth inferring, so we need
+ %% to check them both.
+ Infer_L = infer_types(RHS, S),
+ Infer_R = infer_types(LHS, S),
+ Infer_R(RHS, Infer_L(LHS, S));
+ (_, S) -> S
+ end;
+infer_types_1(#value{op={bif,element},args=[{integer,Index}=Key,Tuple]}) ->
+ fun(Val, S) ->
+ Type = get_term_type(Val, S),
+ update_type(fun meet/2,{tuple,[Index],#{ Key => Type }}, Tuple, S)
+ end;
+infer_types_1(#value{op={bif,is_atom},args=[Src]}) ->
+ infer_type_test_bif({atom,[]}, Src);
+infer_types_1(#value{op={bif,is_boolean},args=[Src]}) ->
+ infer_type_test_bif(bool, Src);
+infer_types_1(#value{op={bif,is_binary},args=[Src]}) ->
+ infer_type_test_bif(binary, Src);
+infer_types_1(#value{op={bif,is_bitstring},args=[Src]}) ->
+ infer_type_test_bif(binary, Src);
+infer_types_1(#value{op={bif,is_float},args=[Src]}) ->
+ infer_type_test_bif(float, Src);
+infer_types_1(#value{op={bif,is_integer},args=[Src]}) ->
+ infer_type_test_bif({integer,{}}, Src);
+infer_types_1(#value{op={bif,is_list},args=[Src]}) ->
+ infer_type_test_bif(list, Src);
+infer_types_1(#value{op={bif,is_map},args=[Src]}) ->
+ infer_type_test_bif(map, Src);
+infer_types_1(#value{op={bif,is_number},args=[Src]}) ->
+ infer_type_test_bif(number, Src);
+infer_types_1(#value{op={bif,is_tuple},args=[Src]}) ->
+ infer_type_test_bif({tuple,[0],#{}}, Src);
+infer_types_1(#value{op={bif,tuple_size}, args=[Tuple]}) ->
+ fun({integer,Arity}, S) ->
+ update_type(fun meet/2, {tuple,Arity,#{}}, Tuple, S);
+ (_, S) -> S
+ end;
+infer_types_1(_) ->
+ fun(_, S) -> S end.
infer_type_test_bif(Type, Src) ->
fun({atom,true}, S) ->
@@ -1445,69 +1654,76 @@ assign({y,_}=Src, {y,_}=Dst, Vst) ->
initialized -> create_tag(initialized, init, [], Dst, Vst);
_ -> assign_1(Src, Dst, Vst)
end;
-assign({Kind,_}=Reg, Dst, Vst) when Kind =:= x; Kind =:= y ->
- assign_1(Reg, Dst, Vst);
+assign({Kind,_}=Src, Dst, Vst) when Kind =:= x; Kind =:= y ->
+ assign_1(Src, Dst, Vst);
assign(Literal, Dst, Vst) ->
- Type = get_term_type(Literal, Vst),
+ Type = get_literal_type(Literal),
create_term(Type, move, [Literal], Dst, Vst).
-%% Creates a special tag value that isn't a regular term, such as
-%% 'initialized' or 'catchtag'
-create_tag(Type, Op, Ss, {y,_}=Dst, Vst) ->
- set_type_reg_expr(Type, {Op, Ss}, Dst, Vst);
-create_tag(_Type, _Op, _Ss, Dst, _Vst) ->
+%% Creates a special tag value that isn't a regular term, such as 'initialized'
+%% or 'catchtag'
+create_tag(Tag, _Op, _Ss, {y,_}=Dst, #vst{current=#st{ys=Ys0}=St0}=Vst) ->
+ case maps:get(Dst, Ys0, uninitialized) of
+ {catchtag,_}=Prev ->
+ error(Prev);
+ {trytag,_}=Prev ->
+ error(Prev);
+ _ ->
+ check_try_catch_tags(Tag, Dst, Vst),
+ Ys = Ys0#{ Dst => Tag },
+ St = St0#st{ys=Ys},
+ remove_fragility(Dst, Vst#vst{current=St})
+ end;
+create_tag(_Tag, _Op, _Ss, Dst, _Vst) ->
error({invalid_tag_register, Dst}).
%% Wipes a special tag, leaving the register initialized but empty.
-kill_tag({y,Y}=Reg, #vst{current=#st{y=Ys0}=St0}=Vst) ->
+kill_tag({y,_}=Reg, #vst{current=#st{ys=Ys0}=St0}=Vst) ->
_ = get_tag_type(Reg, Vst), %Assertion.
- Ys = gb_trees:update(Y, initialized, Ys0),
- Vst#vst{current=St0#st{y=Ys}}.
+ Ys = Ys0#{ Reg => initialized },
+ Vst#vst{current=St0#st{ys=Ys}}.
%% Creates a completely new term with the given type.
-create_term(Type, Op, Ss, Dst, Vst) ->
- set_type_reg_expr(Type, {Op, Ss}, Dst, Vst).
+create_term(Type, Op, Ss0, Dst, Vst0) ->
+ create_term(Type, Op, Ss0, Dst, Vst0, Vst0).
-%% Extracts a term from Ss, propagating fragility.
-extract_term(Type, Op, Ss, Dst, Vst) ->
- extract_term(Type, Op, Ss, Dst, Vst, Vst).
-
-%% As extract_term/4, but uses the incoming Vst for fragility in case x-regs
-%% have been pruned and the sources can no longer be found.
-extract_term(Type0, Op, Ss, Dst, Vst, OrigVst) ->
- Type = propagate_fragility(Type0, Ss, OrigVst),
- set_type_reg_expr(Type, {Op, Ss}, Dst, Vst).
-
-%% Helper functions for tests that alter state on both the success and fail
-%% branches, keeping the states from tainting each other.
-complex_test(Fail, FailFun, SuccFun, Vst0) ->
- #vst{current=St0} = Vst0,
- Vst1 = FailFun(Vst0),
- Vst2 = branch_state(Fail, Vst1),
- Vst = Vst2#vst{current=St0},
- SuccFun(Vst).
+%% As create_term/4, but uses the incoming Vst for argument resolution in
+%% case x-regs have been pruned and the sources can no longer be found.
+create_term(Type, Op, Ss0, Dst, Vst0, OrigVst) ->
+ {Ref, Vst1} = new_value(Type, Op, resolve_args(Ss0, OrigVst), Vst0),
+ Vst = remove_fragility(Dst, Vst1),
+ set_reg_vref(Ref, Dst, Vst).
-%% Helper function for simple "is_type" tests.
-type_test(Fail, Type, Reg, Vst) ->
- assert_term(Reg, Vst),
- complex_test(Fail,
- fun(FailVst) ->
- update_type(fun subtract/2, Type, Reg, FailVst)
- end,
- fun(SuccVst) ->
- update_type(fun meet/2, Type, Reg, SuccVst)
- end, Vst).
+%% Extracts a term from Ss, propagating fragility.
+extract_term(Type, Op, Ss0, Dst, Vst0) ->
+ extract_term(Type, Op, Ss0, Dst, Vst0, Vst0).
+
+%% As extract_term/4, but uses the incoming Vst for argument resolution in
+%% case x-regs have been pruned and the sources can no longer be found.
+extract_term(Type, Op, Ss0, Dst, Vst0, OrigVst) ->
+ {Ref, Vst1} = new_value(Type, Op, resolve_args(Ss0, OrigVst), Vst0),
+ Vst = propagate_fragility(Dst, Ss0, Vst1),
+ set_reg_vref(Ref, Dst, Vst).
+
+%% Translates instruction arguments into the argument() type, decoupling them
+%% from their registers, allowing us to infer their types after they've been
+%% clobbered or moved.
+resolve_args([{Kind,_}=Src | Args], Vst) when Kind =:= x; Kind =:= y ->
+ [get_reg_vref(Src, Vst) | resolve_args(Args, Vst)];
+resolve_args([Lit | Args], Vst) ->
+ assert_literal(Lit),
+ [Lit | resolve_args(Args, Vst)];
+resolve_args([], _Vst) ->
+ [].
%% Overrides the type of Reg. This is ugly but a necessity for certain
%% destructive operations.
override_type(Type, Reg, Vst) ->
- %% Once the new type format is in, this should be expressed as:
- %% update_type(fun(_, T) -> T end, Type, Reg, Vst).
- set_aliased_type(Type, Reg, Vst).
+ update_type(fun(_, T) -> T end, Type, Reg, Vst).
%% This is used when linear code finds out more and more information about a
%% type, so that the type gets more specialized.
-update_type(Merge, Type0, Reg, Vst) ->
+update_type(Merge, With, #value_ref{}=Ref, Vst) ->
%% If the old type can't be merged with the new one, the type information
%% is inconsistent and we know that some instructions will never be
%% executed at run-time. For example:
@@ -1516,23 +1732,57 @@ update_type(Merge, Type0, Reg, Vst) ->
%% {test,is_tuple,Fail,[Reg]}.
%% {test,test_arity,Fail,[Reg,5]}.
%%
- %% Note that the test_arity instruction can never be reached, so we use the
- %% new type instead of 'none'.
- Type = case Merge(get_durable_term_type(Reg, Vst), Type0) of
- none -> Type0;
- T -> T
- end,
- set_aliased_type(Type, Reg, Vst).
+ %% Note that the test_arity instruction can never be reached, so we need to
+ %% kill the state to avoid raising an error when we encounter it.
+ %%
+ %% Simply returning `kill_state(Vst)` is unsafe however as we might be in
+ %% the middle of an instruction, and altering the rest of the validator
+ %% (eg. prune_x_regs/2) to no-op on dead states is prone to error.
+ %%
+ %% We therefore throw a 'type_conflict' error instead, which causes
+ %% validation to fail unless we're in a context where such errors can be
+ %% handled, such as in a branch handler.
+ Current = get_raw_type(Ref, Vst),
+ case Merge(Current, With) of
+ none -> throw({type_conflict, Current, With});
+ Type -> set_type(Type, Ref, Vst)
+ end;
+update_type(Merge, With, {Kind,_}=Reg, Vst) when Kind =:= x; Kind =:= y ->
+ update_type(Merge, With, get_reg_vref(Reg, Vst), Vst);
+update_type(Merge, With, Literal, Vst) ->
+ assert_literal(Literal),
+ %% Literals always retain their type, but we still need to bail on type
+ %% conflicts.
+ case Merge(Literal, With) of
+ none -> throw({type_conflict, Literal, With});
+ _Type -> Vst
+ end.
update_ne_types(LHS, RHS, Vst) ->
- update_type(fun subtract/2, get_durable_term_type(RHS, Vst), LHS, Vst).
+ %% While updating types on equality is fairly straightforward, inequality
+ %% is a bit trickier since all we know is that the *value* of LHS differs
+ %% from RHS, so we can't blindly subtract their types.
+ %%
+ %% Consider `number =/= {integer,[]}`; all we know is that LHS isn't equal
+ %% to some *specific integer* of unknown value, and if we were to subtract
+ %% {integer,[]} we would erroneously infer that the new type is {float,[]}.
+ %%
+ %% Therefore, we only subtract when we know that RHS has a specific value.
+ RType = get_term_type(RHS, Vst),
+ case is_literal(RType) of
+ true -> update_type(fun subtract/2, RType, LHS, Vst);
+ false -> Vst
+ end.
update_eq_types(LHS, RHS, Vst0) ->
- Infer = infer_types(LHS, Vst0),
- Vst1 = Infer(RHS, Vst0),
+ %% Either side might contain something worth inferring, so we need
+ %% to check them both.
+ Infer_L = infer_types(RHS, Vst0),
+ Infer_R = infer_types(LHS, Vst0),
+ Vst1 = Infer_R(RHS, Infer_L(LHS, Vst0)),
- T1 = get_durable_term_type(LHS, Vst1),
- T2 = get_durable_term_type(RHS, Vst1),
+ T1 = get_term_type(LHS, Vst1),
+ T2 = get_term_type(RHS, Vst1),
Vst = update_type(fun meet/2, T2, LHS, Vst1),
update_type(fun meet/2, T1, RHS, Vst).
@@ -1540,102 +1790,69 @@ update_eq_types(LHS, RHS, Vst0) ->
%% Helper functions for the above.
assign_1(Src, Dst, Vst0) ->
- Type = get_move_term_type(Src, Vst0),
- Def = get_def(Src, Vst0),
-
- Vst = set_type_reg_expr(Type, Def, Dst, Vst0),
-
- #vst{current=St0} = Vst,
- #st{aliases=Aliases0} = St0,
-
- Aliases = Aliases0#{Src=>Dst,Dst=>Src},
-
- St = St0#st{aliases=Aliases},
- Vst#vst{current=St}.
-
-set_aliased_type(Type, Reg, #vst{current=#st{aliases=Aliases}}=Vst0) ->
- Vst1 = set_type(Type, Reg, Vst0),
- case Aliases of
- #{Reg:=OtherReg} ->
- Vst = set_type_reg(Type, OtherReg, Vst1),
- #vst{current=St} = Vst,
- Vst#vst{current=St#st{aliases=Aliases}};
+ assert_movable(Src, Vst0),
+ Vst = propagate_fragility(Dst, [Src], Vst0),
+ set_reg_vref(get_reg_vref(Src, Vst), Dst, Vst).
+
+set_reg_vref(Ref, {x,_}=Dst, Vst) ->
+ check_limit(Dst),
+ #vst{current=#st{xs=Xs0}=St0} = Vst,
+ St = St0#st{xs=Xs0#{ Dst => Ref }},
+ Vst#vst{current=St};
+set_reg_vref(Ref, {y,_}=Dst, #vst{current=#st{ys=Ys0}=St0} = Vst) ->
+ check_limit(Dst),
+ case Ys0 of
+ #{ Dst := {catchtag,_}=Tag } ->
+ error(Tag);
+ #{ Dst := {trytag,_}=Tag } ->
+ error(Tag);
+ #{ Dst := _ } ->
+ St = St0#st{ys=Ys0#{ Dst => Ref }},
+ Vst#vst{current=St};
#{} ->
- Vst1
+ %% Storing into a non-existent Y register means that we haven't set
+ %% up a (sufficiently large) stack.
+ error({invalid_store, Dst})
end.
-kill_aliases(Reg, #st{aliases=Aliases0}=St) ->
- case Aliases0 of
- #{Reg:=OtherReg} ->
- Aliases = maps:without([Reg,OtherReg], Aliases0),
- St#st{aliases=Aliases};
+get_reg_vref({x,_}=Src, #vst{current=#st{xs=Xs}}) ->
+ check_limit(Src),
+ case Xs of
+ #{ Src := #value_ref{}=Ref } ->
+ Ref;
#{} ->
- St
+ error({uninitialized_reg, Src})
+ end;
+get_reg_vref({y,_}=Src, #vst{current=#st{ys=Ys}}) ->
+ check_limit(Src),
+ case Ys of
+ #{ Src := #value_ref{}=Ref } ->
+ Ref;
+ #{ Src := initialized } ->
+ error({unassigned, Src});
+ #{ Src := Tag } when Tag =/= uninitialized ->
+ error(Tag);
+ #{} ->
+ error({uninitialized_reg, Src})
end.
-set_type(Type, {x,_}=Reg, Vst) ->
- set_type_reg(Type, Reg, Reg, Vst);
-set_type(Type, {y,_}=Reg, Vst) ->
- set_type_reg(Type, Reg, Reg, Vst);
-set_type(_, _, #vst{}=Vst) -> Vst.
-
-set_type_reg(Type, Src, Dst, Vst) ->
- case get_raw_type(Src, Vst) of
- uninitialized ->
- error({uninitialized_reg, Src});
- {fragile,_} ->
- set_type_reg(make_fragile(Type), Dst, Vst);
- _ ->
- set_type_reg(Type, Dst, Vst)
+set_type(Type, #value_ref{}=Ref, #vst{current=#st{vs=Vs0}=St}=Vst) ->
+ case Vs0 of
+ #{ Ref := #value{}=Entry } ->
+ Vs = Vs0#{ Ref => Entry#value{type=Type} },
+ Vst#vst{current=St#st{vs=Vs}};
+ #{} ->
+ %% Dead references may happen during type inference and are not an
+ %% error in and of themselves. If a problem were to arise from this
+ %% it'll explode elsewhere.
+ Vst
end.
-set_type_reg(Type, Reg, Vst) ->
- set_type_reg_expr(Type, none, Reg, Vst).
-
-set_type_reg_expr(Type, Expr, {x,_}=Reg, Vst) ->
- set_type_x(Type, Expr, Reg, Vst);
-set_type_reg_expr(Type, Expr, Reg, Vst) ->
- set_type_y(Type, Expr, Reg, Vst).
-
-set_type_x(Type, Expr, {x,X}=Reg, #vst{current=#st{x=Xs0,defs=Defs0}=St0}=Vst)
- when is_integer(X), 0 =< X ->
- check_limit(Reg),
- Xs = case gb_trees:lookup(X, Xs0) of
- none ->
- gb_trees:insert(X, Type, Xs0);
- {value,{fragile,_}} ->
- gb_trees:update(X, make_fragile(Type), Xs0);
- {value,_} ->
- gb_trees:update(X, Type, Xs0)
- end,
- Defs = Defs0#{Reg=>Expr},
- St = kill_aliases(Reg, St0),
- Vst#vst{current=St#st{x=Xs,defs=Defs}};
-set_type_x(Type, _Expr, Reg, #vst{}) ->
- error({invalid_store,Reg,Type}).
-
-set_type_y(Type, Expr, {y,Y}=Reg, #vst{current=#st{y=Ys0,defs=Defs0}=St0}=Vst)
- when is_integer(Y), 0 =< Y ->
- check_limit(Reg),
- Ys = case gb_trees:lookup(Y, Ys0) of
- none ->
- error({invalid_store,Reg,Type});
- {value,{catchtag,_}=Tag} ->
- error(Tag);
- {value,{trytag,_}=Tag} ->
- error(Tag);
- {value,_} ->
- gb_trees:update(Y, Type, Ys0)
- end,
- check_try_catch_tags(Type, Reg, Vst),
- Defs = Defs0#{Reg=>Expr},
- St = kill_aliases(Reg, St0),
- Vst#vst{current=St#st{y=Ys,defs=Defs}};
-set_type_y(Type, _Expr, Reg, #vst{}) ->
- error({invalid_store,Reg,Type}).
-
-make_fragile({fragile,_}=Type) -> Type;
-make_fragile(Type) -> {fragile,Type}.
+new_value(Type, Op, Ss, #vst{current=#st{vs=Vs0}=St,ref_ctr=Counter}=Vst) ->
+ Ref = #value_ref{id=Counter},
+ Vs = Vs0#{ Ref => #value{op=Op,args=Ss,type=Type} },
+
+ {Ref, Vst#vst{current=St#st{vs=Vs},ref_ctr=Counter+1}}.
kill_catch_tag(Reg, #vst{current=#st{ct=[Fail|Fails]}=St}=Vst0) ->
Vst = Vst0#vst{current=St#st{ct=Fails,fls=undefined}},
@@ -1657,36 +1874,36 @@ check_try_catch_tags(Type, {y,N}=Reg, Vst) ->
ok
end.
-is_reg_defined({x,_}=Reg, Vst) -> is_type_defined_x(Reg, Vst);
-is_reg_defined({y,_}=Reg, Vst) -> is_type_defined_y(Reg, Vst);
+is_reg_defined({x,_}=Reg, #vst{current=#st{xs=Xs}}) -> is_map_key(Reg, Xs);
+is_reg_defined({y,_}=Reg, #vst{current=#st{ys=Ys}}) -> is_map_key(Reg, Ys);
is_reg_defined(V, #vst{}) -> error({not_a_register, V}).
-is_type_defined_x({x,X}, #vst{current=#st{x=Xs}}) ->
- gb_trees:is_defined(X,Xs).
-
-is_type_defined_y({y,Y}, #vst{current=#st{y=Ys}}) ->
- gb_trees:is_defined(Y,Ys).
-
assert_term(Src, Vst) ->
- get_term_type(Src, Vst),
+ _ = get_term_type(Src, Vst),
ok.
-assert_not_fragile(Src, Vst) ->
- case get_term_type(Src, Vst) of
- {fragile, _} -> error({fragile_message_reference, Src});
- _ -> ok
+assert_movable(Src, Vst) ->
+ _ = get_movable_term_type(Src, Vst),
+ ok.
+
+assert_literal(Src) ->
+ case is_literal(Src) of
+ true -> ok;
+ false -> error({literal_required,Src})
end.
-assert_literal(nil) -> ok;
-assert_literal({atom,A}) when is_atom(A) -> ok;
-assert_literal({float,F}) when is_float(F) -> ok;
-assert_literal({integer,I}) when is_integer(I) -> ok;
-assert_literal({literal,_L}) -> ok;
-assert_literal(T) -> error({literal_required,T}).
+assert_not_literal(Src) ->
+ case is_literal(Src) of
+ true -> error({literal_not_allowed,Src});
+ false -> ok
+ end.
-assert_not_literal({x,_}) -> ok;
-assert_not_literal({y,_}) -> ok;
-assert_not_literal(Literal) -> error({literal_not_allowed,Literal}).
+is_literal(nil) -> true;
+is_literal({atom,A}) when is_atom(A) -> true;
+is_literal({float,F}) when is_float(F) -> true;
+is_literal({integer,I}) when is_integer(I) -> true;
+is_literal({literal,_L}) -> true;
+is_literal(_) -> false.
%% The possible types.
%%
@@ -1753,16 +1970,106 @@ assert_not_literal(Literal) -> error({literal_not_allowed,Literal}).
%%
%% none A conflict in types. There will be an exception at runtime.
%%
-%% FRAGILITY
-%% ---------
-%%
-%% The loop_rec/2 instruction may return a reference to a term that is
-%% not part of the root set. That term or any part of it must not be
-%% included in a garbage collection. Therefore, the term (or any part
-%% of it) must not be stored in an Y register.
-%%
-%% Such terms are wrapped in a {fragile,Type} tuple, where Type is one
-%% of the types described above.
+
+%% join(Type1, Type2) -> Type
+%% Return the most specific type possible.
+join(Same, Same) ->
+ Same;
+join(none, Other) ->
+ Other;
+join(Other, none) ->
+ Other;
+join({literal,_}=T1, T2) ->
+ join_literal(T1, T2);
+join(T1, {literal,_}=T2) ->
+ join_literal(T2, T1);
+join({tuple,Size,EsA}, {tuple,Size,EsB}) ->
+ Es = join_tuple_elements(tuple_sz(Size), EsA, EsB),
+ {tuple, Size, Es};
+join({tuple,A,EsA}, {tuple,B,EsB}) ->
+ Size = min(tuple_sz(A), tuple_sz(B)),
+ Es = join_tuple_elements(Size, EsA, EsB),
+ {tuple, [Size], Es};
+join({Type,A}, {Type,B})
+ when Type =:= atom; Type =:= integer; Type =:= float ->
+ if A =:= B -> {Type,A};
+ true -> {Type,[]}
+ end;
+join({Type,_}, number)
+ when Type =:= integer; Type =:= float ->
+ number;
+join(number, {Type,_})
+ when Type =:= integer; Type =:= float ->
+ number;
+join({integer,_}, {float,_}) ->
+ number;
+join({float,_}, {integer,_}) ->
+ number;
+join(bool, {atom,A}) ->
+ join_bool(A);
+join({atom,A}, bool) ->
+ join_bool(A);
+join({atom,A}, {atom,B}) when is_boolean(A), is_boolean(B) ->
+ bool;
+join({atom,_}, {atom,_}) ->
+ {atom,[]};
+join(#ms{id=Id1,valid=B1,slots=Slots1},
+ #ms{id=Id2,valid=B2,slots=Slots2}) ->
+ Id = if
+ Id1 =:= Id2 -> Id1;
+ true -> make_ref()
+ end,
+ #ms{id=Id,valid=B1 band B2,slots=min(Slots1, Slots2)};
+join(T1, T2) when T1 =/= T2 ->
+ %% We've exhaused all other options, so the type must either be a list or
+ %% a 'term'.
+ join_list(T1, T2).
+
+join_tuple_elements(Limit, EsA, EsB) ->
+ Es0 = join_elements(EsA, EsB),
+ maps:filter(fun({integer,Index}, _Type) -> Index =< Limit end, Es0).
+
+join_elements(Es1, Es2) ->
+ Keys = if
+ map_size(Es1) =< map_size(Es2) -> maps:keys(Es1);
+ map_size(Es1) > map_size(Es2) -> maps:keys(Es2)
+ end,
+ join_elements_1(Keys, Es1, Es2, #{}).
+
+join_elements_1([Key | Keys], Es1, Es2, Acc0) ->
+ Type = case {Es1, Es2} of
+ {#{ Key := Same }, #{ Key := Same }} -> Same;
+ {#{ Key := Type1 }, #{ Key := Type2 }} -> join(Type1, Type2);
+ {#{}, #{}} -> term
+ end,
+ Acc = set_element_type(Key, Type, Acc0),
+ join_elements_1(Keys, Es1, Es2, Acc);
+join_elements_1([], _Es1, _Es2, Acc) ->
+ Acc.
+
+%% Joins types of literals; note that the left argument must either be a
+%% literal or exactly equal to the second argument.
+join_literal(Same, Same) ->
+ Same;
+join_literal({literal,_}=Lit, T) ->
+ join_literal(T, get_literal_type(Lit));
+join_literal(T1, T2) ->
+ %% We're done extracting the types, try merging them again.
+ join(T1, T2).
+
+join_list(nil, cons) -> list;
+join_list(nil, list) -> list;
+join_list(cons, list) -> list;
+join_list(T, nil) -> join_list(nil, T);
+join_list(T, cons) -> join_list(cons, T);
+join_list(_, _) ->
+ %% Not a list, so it must be a term.
+ term.
+
+join_bool([]) -> {atom,[]};
+join_bool(true) -> bool;
+join_bool(false) -> bool;
+join_bool(_) -> {atom,[]}.
%% meet(Type1, Type2) -> Type
%% Return the meet of two types. The meet is a more specific type.
@@ -1770,14 +2077,23 @@ assert_not_literal(Literal) -> error({literal_not_allowed,Literal}).
meet(Same, Same) ->
Same;
-meet({literal,_}=T1, T2) ->
- meet_literal(T1, T2);
-meet(T1, {literal,_}=T2) ->
- meet_literal(T2, T1);
meet(term, Other) ->
Other;
meet(Other, term) ->
Other;
+meet(#ms{}, binary) ->
+ #ms{};
+meet(binary, #ms{}) ->
+ #ms{};
+meet({literal,_}, {literal,_}) ->
+ none;
+meet(T1, {literal,_}=T2) ->
+ meet(T2, T1);
+meet({literal,_}=T1, T2) ->
+ case meet(get_literal_type(T1), T2) of
+ none -> none;
+ _ -> T1
+ end;
meet(T1, T2) ->
case {erlang:min(T1, T2),erlang:max(T1, T2)} of
{{atom,_}=A,{atom,[]}} -> A;
@@ -1810,13 +2126,6 @@ meet(T1, T2) ->
{_,_} -> none
end.
-%% Meets types of literals.
-meet_literal({literal,_}=Lit, T) ->
- meet_literal(T, get_literal_type(Lit));
-meet_literal(T1, T2) ->
- %% We're done extracting the types, try merging them again.
- meet(T1, T2).
-
meet_elements(Es1, Es2) ->
Keys = maps:keys(Es1) ++ maps:keys(Es2),
meet_elements_1(Keys, Es1, Es2, #{}).
@@ -1838,7 +2147,7 @@ meet_elements_1([], _Es1, _Es2, Acc) ->
%% No tuple elements may have an index above the known size.
assert_tuple_elements(Limit, Es) ->
- true = maps:fold(fun(Index, _T, true) ->
+ true = maps:fold(fun({integer,Index}, _T, true) ->
Index =< Limit
end, true, Es). %Assertion.
@@ -1846,6 +2155,7 @@ assert_tuple_elements(Limit, Es) ->
%% Subtract Type2 from Type2. Example:
%% subtract(list, nil) -> cons
+subtract(Same, Same) -> none;
subtract(list, nil) -> cons;
subtract(list, cons) -> nil;
subtract(number, {integer,[]}) -> {float,[]};
@@ -1855,7 +2165,7 @@ subtract(bool, {atom,true}) -> {atom, false};
subtract(Type, _) -> Type.
assert_type(WantedType, Term, Vst) ->
- Type = get_durable_term_type(Term, Vst),
+ Type = get_term_type(Term, Vst),
assert_type(WantedType, Type).
assert_type(Correct, Correct) -> ok;
@@ -1876,13 +2186,12 @@ assert_type(Needed, Actual) ->
error({bad_type,{needed,Needed},{actual,Actual}}).
get_element_type(Key, Src, Vst) ->
- get_element_type_1(Key, get_durable_term_type(Src, Vst)).
+ get_element_type_1(Key, get_term_type(Src, Vst)).
-get_element_type_1(Index, {tuple,Sz,Es}) ->
+get_element_type_1({integer,_}=Key, {tuple,_Sz,Es}) ->
case Es of
- #{ Index := Type } -> Type;
- #{} when Index =< Sz -> term;
- #{} -> none
+ #{ Key := Type } -> Type;
+ #{} -> term
end;
get_element_type_1(_Index, _Type) ->
term.
@@ -1899,7 +2208,7 @@ get_tuple_size({integer,Sz}) -> Sz;
get_tuple_size(_) -> 0.
validate_src(Ss, Vst) when is_list(Ss) ->
- [assert_term(S, Vst) || S <- Ss],
+ _ = [assert_term(S, Vst) || S <- Ss],
ok.
%% get_term_type(Src, ValidatorState) -> Type
@@ -1907,33 +2216,23 @@ validate_src(Ss, Vst) when is_list(Ss) ->
%% a standard Erlang type (no catch/try tags or match contexts).
get_term_type(Src, Vst) ->
- case get_move_term_type(Src, Vst) of
+ case get_movable_term_type(Src, Vst) of
#ms{} -> error({match_context,Src});
Type -> Type
end.
-%% get_durable_term_type(Src, ValidatorState) -> Type
-%% Get the type of the source Src. The returned type Type will be
-%% a standard Erlang type (no catch/try tags or match contexts).
-%% Fragility will be stripped.
-
-get_durable_term_type(Src, Vst) ->
- case get_term_type(Src, Vst) of
- {fragile,Type} -> Type;
- Type -> Type
- end.
-
-%% get_move_term_type(Src, ValidatorState) -> Type
+%% get_movable_term_type(Src, ValidatorState) -> Type
%% Get the type of the source Src. The returned type Type will be
%% a standard Erlang type (no catch/try tags). Match contexts are OK.
-get_move_term_type(Src, Vst) ->
+get_movable_term_type(Src, Vst) ->
case get_raw_type(Src, Vst) of
initialized -> error({unassigned,Src});
uninitialized -> error({uninitialized_reg,Src});
{catchtag,_} -> error({catchtag,Src});
{trytag,_} -> error({trytag,Src});
tuple_in_progress -> error({tuple_in_progress,Src});
+ {literal,_}=Lit -> get_literal_type(Lit);
Type -> Type
end.
@@ -1952,26 +2251,29 @@ get_tag_type(Src, _) ->
error({invalid_tag_register,Src}).
%% get_raw_type(Src, ValidatorState) -> Type
-%% Return the type of a register without doing any validity checks.
-get_raw_type({x,X}, #vst{current=#st{x=Xs}}) when is_integer(X) ->
- case gb_trees:lookup(X, Xs) of
- {value,Type} -> Type;
- none -> uninitialized
+%% Return the type of a register without doing any validity checks or
+%% conversions.
+get_raw_type({x,X}=Src, #vst{current=#st{xs=Xs}}=Vst) when is_integer(X) ->
+ check_limit(Src),
+ case Xs of
+ #{ Src := #value_ref{}=Ref } -> get_raw_type(Ref, Vst);
+ #{} -> uninitialized
+ end;
+get_raw_type({y,Y}=Src, #vst{current=#st{ys=Ys}}=Vst) when is_integer(Y) ->
+ check_limit(Src),
+ case Ys of
+ #{ Src := #value_ref{}=Ref } -> get_raw_type(Ref, Vst);
+ #{ Src := Tag } -> Tag;
+ #{} -> uninitialized
end;
-get_raw_type({y,Y}, #vst{current=#st{y=Ys}}) when is_integer(Y) ->
- case gb_trees:lookup(Y, Ys) of
- {value,Type} -> Type;
- none -> uninitialized
+get_raw_type(#value_ref{}=Ref, #vst{current=#st{vs=Vs}}) ->
+ case Vs of
+ #{ Ref := #value{type=Type} } -> Type;
+ #{} -> none
end;
get_raw_type(Src, #vst{}) ->
get_literal_type(Src).
-get_def(Src, #vst{current=#st{defs=Defs}}) ->
- case Defs of
- #{Src:=Def} -> Def;
- #{} -> none
- end.
-
get_literal_type(nil=T) -> T;
get_literal_type({atom,A}=T) when is_atom(A) -> T;
get_literal_type({float,F}=T) when is_float(F) -> T;
@@ -1979,59 +2281,201 @@ get_literal_type({integer,I}=T) when is_integer(I) -> T;
get_literal_type({literal,[_|_]}) -> cons;
get_literal_type({literal,Bitstring}) when is_bitstring(Bitstring) -> binary;
get_literal_type({literal,Map}) when is_map(Map) -> map;
-get_literal_type({literal,Tuple}) when is_tuple(Tuple) -> value_to_type(Tuple);
+get_literal_type({literal,Tuple}) when is_tuple(Tuple) -> glt_1(Tuple);
get_literal_type({literal,_}) -> term;
get_literal_type(T) -> error({not_literal,T}).
-value_to_type([]) -> nil;
-value_to_type(A) when is_atom(A) -> {atom, A};
-value_to_type(F) when is_float(F) -> {float, F};
-value_to_type(I) when is_integer(I) -> {integer, I};
-value_to_type(T) when is_tuple(T) ->
- {Es,_} = foldl(fun(Val, {Es0, Index}) ->
- Type = value_to_type(Val),
- Es = set_element_type(Index, Type, Es0),
- {Es, Index + 1}
- end, {#{}, 1}, tuple_to_list(T)),
- {tuple, tuple_size(T), Es};
-value_to_type(L) -> {literal, L}.
+glt_1([]) -> nil;
+glt_1(A) when is_atom(A) -> {atom, A};
+glt_1(F) when is_float(F) -> {float, F};
+glt_1(I) when is_integer(I) -> {integer, I};
+glt_1(T) when is_tuple(T) ->
+ {Es,_} = foldl(fun(Val, {Es0, Index}) ->
+ Type = glt_1(Val),
+ Es = set_element_type({integer,Index}, Type, Es0),
+ {Es, Index + 1}
+ end, {#{}, 1}, tuple_to_list(T)),
+ {tuple, tuple_size(T), Es};
+glt_1(L) ->
+ {literal, L}.
+%%%
+%%% Branch tracking
+%%%
+
+%% Forks the execution flow, with the provided funs returning the new state of
+%% their respective branch; the "fail" fun returns the state where the branch
+%% is taken, and the "success" fun returns the state where it's not.
+%%
+%% If either path is known not to be taken at runtime (eg. due to a type
+%% conflict), it will simply be discarded.
+-spec branch(Lbl :: label(),
+ Original :: #vst{},
+ FailFun :: BranchFun,
+ SuccFun :: BranchFun) -> #vst{} when
+ BranchFun :: fun((#vst{}) -> #vst{}).
+branch(Lbl, Vst0, FailFun, SuccFun) ->
+ #vst{current=St0} = Vst0,
+ try FailFun(Vst0) of
+ Vst1 ->
+ Vst2 = branch_state(Lbl, Vst1),
+ Vst = Vst2#vst{current=St0},
+ try SuccFun(Vst) of
+ V -> V
+ catch
+ {type_conflict, _, _} ->
+ %% The instruction is guaranteed to fail; kill the state.
+ kill_state(Vst)
+ end
+ catch
+ {type_conflict, _, _} ->
+ %% This instruction is guaranteed not to fail, so we run the
+ %% success branch *without* catching type conflicts to avoid hiding
+ %% errors in the validator itself; one of the branches must
+ %% succeed.
+ SuccFun(Vst0)
+ end.
+
+%% A shorthand version of branch/4 for when the state is only altered on
+%% success.
+branch(Fail, Vst, SuccFun) ->
+ branch(Fail, Vst, fun(V) -> V end, SuccFun).
+
+%% Directly branches off the state. This is an "internal" operation that should
+%% be used sparingly.
branch_state(0, #vst{}=Vst) ->
- %% If the instruction fails, the stack may be scanned
- %% looking for a catch tag. Therefore the Y registers
- %% must be initialized at this point.
+ %% If the instruction fails, the stack may be scanned looking for a catch
+ %% tag. Therefore the Y registers must be initialized at this point.
verify_y_init(Vst),
Vst;
-branch_state(L, #vst{current=St,branched=B}=Vst) ->
- Vst#vst{
- branched=case gb_trees:is_defined(L, B) of
- false ->
- gb_trees:insert(L, St, B);
- true ->
- MergedSt = merge_states(L, St, B),
- gb_trees:update(L, MergedSt, B)
- end}.
-
-%% merge_states/3 is used when there are more than one way to arrive
-%% at this point, and the type states for the different paths has
-%% to be merged. The type states are downgraded to the least common
-%% subset for the subsequent code.
-
-merge_states(L, St, Branched) when L =/= 0 ->
+branch_state(L, #vst{current=St,branched=B,ref_ctr=Counter0}=Vst) ->
+ case gb_trees:is_defined(L, B) of
+ true ->
+ {MergedSt, Counter} = merge_states(L, St, B, Counter0),
+ Branched = gb_trees:update(L, MergedSt, B),
+ Vst#vst{branched=Branched,ref_ctr=Counter};
+ false ->
+ Vst#vst{branched=gb_trees:insert(L, St, B)}
+ end.
+
+%% merge_states/3 is used when there's more than one way to arrive at a
+%% certain point, requiring the states to be merged down to the least
+%% common subset for the subsequent code.
+
+merge_states(L, St, Branched, Counter) when L =/= 0 ->
case gb_trees:lookup(L, Branched) of
- none -> St;
- {value,OtherSt} when St =:= none -> OtherSt;
- {value,OtherSt} -> merge_states_1(St, OtherSt)
+ none ->
+ {St, Counter};
+ {value,OtherSt} when St =:= none ->
+ {OtherSt, Counter};
+ {value,OtherSt} ->
+ merge_states_1(St, OtherSt, Counter)
end.
-merge_states_1(#st{x=Xs0,y=Ys0,numy=NumY0,h=H0,ct=Ct0,aliases=Aliases0},
- #st{x=Xs1,y=Ys1,numy=NumY1,h=H1,ct=Ct1,aliases=Aliases1}) ->
- NumY = merge_stk(NumY0, NumY1),
- Xs = merge_regs(Xs0, Xs1),
- Ys = merge_y_regs(Ys0, Ys1),
- Ct = merge_ct(Ct0, Ct1),
- Aliases = merge_aliases(Aliases0, Aliases1),
- #st{x=Xs,y=Ys,numy=NumY,h=min(H0, H1),ct=Ct,aliases=Aliases}.
+merge_states_1(#st{xs=XsA,ys=YsA,vs=VsA,fragile=FragA,numy=NumYA,h=HA,ct=CtA},
+ #st{xs=XsB,ys=YsB,vs=VsB,fragile=FragB,numy=NumYB,h=HB,ct=CtB},
+ Counter0) ->
+ %% When merging registers we drop all registers that aren't defined in both
+ %% states, and resolve conflicts by creating new values (similar to phi
+ %% nodes in SSA).
+ %%
+ %% While doing this we build a "merge map" detailing which values need to
+ %% be kept and which new values need to be created to resolve conflicts.
+ %% This map is then used to create a new value database where the types of
+ %% all values have been joined.
+ {Xs, Merge0, Counter1} = merge_regs(XsA, XsB, #{}, Counter0),
+ {Ys, Merge, Counter} = merge_regs(YsA, YsB, Merge0, Counter1),
+ Vs = merge_values(Merge, VsA, VsB),
+
+ Fragile = merge_fragility(FragA, FragB),
+ NumY = merge_stk(NumYA, NumYB),
+ Ct = merge_ct(CtA, CtB),
+
+ St = #st{xs=Xs,ys=Ys,vs=Vs,fragile=Fragile,numy=NumY,h=min(HA, HB),ct=Ct},
+ {St, Counter}.
+
+%% Merges the contents of two register maps, returning the updated "merge map"
+%% and the new registers.
+merge_regs(RsA, RsB, Merge, Counter) ->
+ Keys = if
+ map_size(RsA) =< map_size(RsB) -> maps:keys(RsA);
+ map_size(RsA) > map_size(RsB) -> maps:keys(RsB)
+ end,
+ merge_regs_1(Keys, RsA, RsB, #{}, Merge, Counter).
+
+merge_regs_1([Reg | Keys], RsA, RsB, Regs, Merge0, Counter0) ->
+ case {RsA, RsB} of
+ {#{ Reg := #value_ref{}=RefA }, #{ Reg := #value_ref{}=RefB }} ->
+ {Ref, Merge, Counter} = merge_vrefs(RefA, RefB, Merge0, Counter0),
+ merge_regs_1(Keys, RsA, RsB, Regs#{ Reg => Ref }, Merge, Counter);
+ {#{ Reg := TagA }, #{ Reg := TagB }} ->
+ %% Tags describe the state of the register rather than the value it
+ %% contains, so if a register contains a tag in one state we have
+ %% to merge it as a tag regardless of whether the other state says
+ %% it's a value.
+ {y, _} = Reg, %Assertion.
+ merge_regs_1(Keys, RsA, RsB, Regs#{ Reg => merge_tags(TagA,TagB) },
+ Merge0, Counter0);
+ {#{}, #{}} ->
+ merge_regs_1(Keys, RsA, RsB, Regs, Merge0, Counter0)
+ end;
+merge_regs_1([], _, _, Regs, Merge, Counter) ->
+ {Regs, Merge, Counter}.
+
+merge_tags(Same, Same) ->
+ Same;
+merge_tags(uninitialized, _) ->
+ uninitialized;
+merge_tags(_, uninitialized) ->
+ uninitialized;
+merge_tags({catchtag,T0}, {catchtag,T1}) ->
+ {catchtag, ordsets:from_list(T0 ++ T1)};
+merge_tags({trytag,T0}, {trytag,T1}) ->
+ {trytag, ordsets:from_list(T0 ++ T1)};
+merge_tags(_A, _B) ->
+ %% All other combinations leave the register initialized. Errors arising
+ %% from this will be caught later on.
+ initialized.
+
+merge_vrefs(Ref, Ref, Merge, Counter) ->
+ %% We have two (potentially) different versions of the same value, so we
+ %% should join their types into the same value.
+ {Ref, Merge#{ Ref => Ref }, Counter};
+merge_vrefs(RefA, RefB, Merge, Counter) ->
+ %% We have two different values, so we need to create a new value from
+ %% their joined type if we haven't already done so.
+ Key = {RefA, RefB},
+ case Merge of
+ #{ Key := Ref } ->
+ {Ref, Merge, Counter};
+ #{} ->
+ Ref = #value_ref{id=Counter},
+ {Ref, Merge#{ Key => Ref }, Counter + 1}
+ end.
+
+merge_values(Merge, VsA, VsB) ->
+ maps:fold(fun(Spec, New, Acc) ->
+ merge_values_1(Spec, New, VsA, VsB, Acc)
+ end, #{}, Merge).
+
+merge_values_1(Same, Same, VsA, VsB, Acc) ->
+ %% We're merging different versions of the same value, so it's safe to
+ %% reuse old entries if the type's unchanged.
+ #value{type=TypeA}=EntryA = map_get(Same, VsA),
+ #value{type=TypeB}=EntryB = map_get(Same, VsB),
+ Entry = case join(TypeA, TypeB) of
+ TypeA -> EntryA;
+ TypeB -> EntryB;
+ JoinedType -> EntryA#value{type=JoinedType}
+ end,
+ Acc#{ Same => Entry };
+merge_values_1({RefA, RefB}, New, VsA, VsB, Acc) ->
+ #value{type=TypeA} = map_get(RefA, VsA),
+ #value{type=TypeB} = map_get(RefB, VsB),
+ Acc#{ New => #value{op=join,args=[],type=join(TypeA, TypeB)} }.
+
+merge_fragility(FragileA, FragileB) ->
+ cerl_sets:union(FragileA, FragileB).
merge_stk(S, S) -> S;
merge_stk(_, _) -> undecided.
@@ -2044,174 +2488,17 @@ merge_ct_1([C0|Ct0], [C1|Ct1]) ->
merge_ct_1([], []) -> [];
merge_ct_1(_, _) -> undecided.
-merge_regs(Rs0, Rs1) ->
- Rs = merge_regs_1(gb_trees:to_list(Rs0), gb_trees:to_list(Rs1)),
- gb_trees_from_list(Rs).
-
-merge_regs_1([Same|Rs1], [Same|Rs2]) ->
- [Same|merge_regs_1(Rs1, Rs2)];
-merge_regs_1([{R1,_}|Rs1], [{R2,_}|_]=Rs2) when R1 < R2 ->
- merge_regs_1(Rs1, Rs2);
-merge_regs_1([{R1,_}|_]=Rs1, [{R2,_}|Rs2]) when R1 > R2 ->
- merge_regs_1(Rs1, Rs2);
-merge_regs_1([{R,Type1}|Rs1], [{R,Type2}|Rs2]) ->
- [{R,join(Type1, Type2)}|merge_regs_1(Rs1, Rs2)];
-merge_regs_1([], []) -> [];
-merge_regs_1([], [_|_]) -> [];
-merge_regs_1([_|_], []) -> [].
-
-merge_y_regs(Rs0, Rs1) ->
- case {gb_trees:size(Rs0),gb_trees:size(Rs1)} of
- {Sz0,Sz1} when Sz0 < Sz1 ->
- merge_y_regs_1(Sz0-1, Rs1, Rs0);
- {_,Sz1} ->
- merge_y_regs_1(Sz1-1, Rs0, Rs1)
- end.
-
-merge_y_regs_1(Y, S, Regs0) when Y >= 0 ->
- Type0 = gb_trees:get(Y, Regs0),
- case gb_trees:get(Y, S) of
- Type0 ->
- merge_y_regs_1(Y-1, S, Regs0);
- Type1 ->
- Type = join(Type0, Type1),
- Regs = gb_trees:update(Y, Type, Regs0),
- merge_y_regs_1(Y-1, S, Regs)
- end;
-merge_y_regs_1(_, _, Regs) -> Regs.
-
-%% join(Type1, Type2) -> Type
-%% Return the most specific type possible.
-%% Note: Type1 must NOT be the same as Type2.
-join({literal,_}=T1, T2) ->
- join_literal(T1, T2);
-join(T1, {literal,_}=T2) ->
- join_literal(T2, T1);
-join({fragile,Same}=Type, Same) ->
- Type;
-join({fragile,T1}, T2) ->
- make_fragile(join(T1, T2));
-join(Same, {fragile,Same}=Type) ->
- Type;
-join(T1, {fragile,T2}) ->
- make_fragile(join(T1, T2));
-join(uninitialized=I, _) -> I;
-join(_, uninitialized=I) -> I;
-join(initialized=I, _) -> I;
-join(_, initialized=I) -> I;
-join({catchtag,T0},{catchtag,T1}) ->
- {catchtag,ordsets:from_list(T0++T1)};
-join({trytag,T0},{trytag,T1}) ->
- {trytag,ordsets:from_list(T0++T1)};
-join({tuple,Size,EsA}, {tuple,Size,EsB}) ->
- Es = join_tuple_elements(tuple_sz(Size), EsA, EsB),
- {tuple, Size, Es};
-join({tuple,A,EsA}, {tuple,B,EsB}) ->
- Size = min(tuple_sz(A), tuple_sz(B)),
- Es = join_tuple_elements(Size, EsA, EsB),
- {tuple, [Size], Es};
-join({Type,A}, {Type,B})
- when Type =:= atom; Type =:= integer; Type =:= float ->
- if A =:= B -> {Type,A};
- true -> {Type,[]}
- end;
-join({Type,_}, number)
- when Type =:= integer; Type =:= float ->
- number;
-join(number, {Type,_})
- when Type =:= integer; Type =:= float ->
- number;
-join(bool, {atom,A}) ->
- join_bool(A);
-join({atom,A}, bool) ->
- join_bool(A);
-join({atom,_}, {atom,_}) ->
- {atom,[]};
-join(#ms{id=Id1,valid=B1,slots=Slots1},
- #ms{id=Id2,valid=B2,slots=Slots2}) ->
- Id = if
- Id1 =:= Id2 -> Id1;
- true -> make_ref()
- end,
- #ms{id=Id,valid=B1 band B2,slots=min(Slots1, Slots2)};
-join(T1, T2) when T1 =/= T2 ->
- %% We've exhaused all other options, so the type must either be a list or
- %% a 'term'.
- join_list(T1, T2).
-
-join_tuple_elements(Limit, EsA, EsB) ->
- Es0 = join_elements(EsA, EsB),
- maps:filter(fun(Index, _Type) -> Index =< Limit end, Es0).
-
-join_elements(Es1, Es2) ->
- Keys = if
- map_size(Es1) =< map_size(Es2) -> maps:keys(Es1);
- map_size(Es1) > map_size(Es2) -> maps:keys(Es2)
- end,
- join_elements_1(Keys, Es1, Es2, #{}).
-
-join_elements_1([Key | Keys], Es1, Es2, Acc0) ->
- Type = case {Es1, Es2} of
- {#{ Key := Same }, #{ Key := Same }} -> Same;
- {#{ Key := Type1 }, #{ Key := Type2 }} -> join(Type1, Type2);
- {#{}, #{}} -> term
- end,
- Acc = set_element_type(Key, Type, Acc0),
- join_elements_1(Keys, Es1, Es2, Acc);
-join_elements_1([], _Es1, _Es2, Acc) ->
- Acc.
-
-%% Joins types of literals; note that the left argument must either be a
-%% literal or exactly equal to the second argument.
-join_literal(Same, Same) ->
- Same;
-join_literal({literal,_}=Lit, T) ->
- join_literal(T, get_literal_type(Lit));
-join_literal(T1, T2) ->
- %% We're done extracting the types, try merging them again.
- join(T1, T2).
-
-join_list(nil, cons) -> list;
-join_list(nil, list) -> list;
-join_list(cons, list) -> list;
-join_list(T, nil) -> join_list(nil, T);
-join_list(T, cons) -> join_list(cons, T);
-join_list(_, _) ->
- %% Not a list, so it must be a term.
- term.
-
-join_bool([]) -> {atom,[]};
-join_bool(true) -> bool;
-join_bool(false) -> bool;
-join_bool(_) -> {atom,[]}.
-
tuple_sz([Sz]) -> Sz;
tuple_sz(Sz) -> Sz.
-merge_aliases(Al0, Al1) when map_size(Al0) =< map_size(Al1) ->
- maps:filter(fun(K, V) ->
- case Al1 of
- #{K:=V} -> true;
- #{} -> false
- end
- end, Al0);
-merge_aliases(Al0, Al1) ->
- merge_aliases(Al1, Al0).
-
-verify_y_init(#vst{current=#st{numy=NumY,y=Ys}}=Vst)
- when is_integer(NumY), NumY > 0 ->
- {HighestY, _} = gb_trees:largest(Ys),
+verify_y_init(#vst{current=#st{numy=NumY,ys=Ys}}=Vst) when is_integer(NumY) ->
+ HighestY = maps:fold(fun({y,Y}, _, Acc) -> max(Y, Acc) end, -1, Ys),
true = NumY > HighestY, %Assertion.
verify_y_init_1(NumY - 1, Vst),
ok;
-verify_y_init(#vst{current=#st{numy=undecided,y=Ys}}=Vst) ->
- case gb_trees:is_empty(Ys) of
- true ->
- ok;
- false ->
- {HighestY, _} = gb_trees:largest(Ys),
- verify_y_init_1(HighestY, Vst)
- end;
+verify_y_init(#vst{current=#st{numy=undecided,ys=Ys}}=Vst) ->
+ HighestY = maps:fold(fun({y,Y}, _, Acc) -> max(Y, Acc) end, -1, Ys),
+ verify_y_init_1(HighestY, Vst);
verify_y_init(#vst{}) ->
ok.
@@ -2219,15 +2506,10 @@ verify_y_init_1(-1, _Vst) ->
ok;
verify_y_init_1(Y, Vst) ->
Reg = {y, Y},
+ assert_not_fragile(Reg, Vst),
case get_raw_type(Reg, Vst) of
- uninitialized ->
- error({uninitialized_reg,Reg});
- {fragile, _} ->
- %% Unsafe. This term may be outside any heap belonging to the
- %% process and would be corrupted by a GC.
- error({fragile_message_reference,Reg});
- _ ->
- verify_y_init_1(Y - 1, Vst)
+ uninitialized -> error({uninitialized_reg,Reg});
+ _ -> verify_y_init_1(Y - 1, Vst)
end.
verify_live(0, _Vst) ->
@@ -2287,27 +2569,68 @@ eat_heap_float(#vst{current=#st{hf=HeapFloats0}=St}=Vst) ->
Vst#vst{current=St#st{hf=HeapFloats}}
end.
-remove_fragility(#vst{current=#st{x=Xs0,y=Ys0}=St0}=Vst) ->
- F = fun(_, {fragile,Type}) -> Type;
- (_, Type) -> Type
- end,
- Xs = gb_trees:map(F, Xs0),
- Ys = gb_trees:map(F, Ys0),
- St = St0#st{x=Xs,y=Ys},
+%%% FRAGILITY
+%%%
+%%% The loop_rec/2 instruction may return a reference to a term that is not
+%%% part of the root set. That term or any part of it must not be included in a
+%%% garbage collection. Therefore, the term (or any part of it) must not be
+%%% passed to another function, placed in another term, or live in a Y register
+%%% over an instruction that may GC.
+%%%
+%%% Fragility is marked on a per-register (rather than per-value) basis.
+
+%% Marks Reg as fragile.
+mark_fragile(Reg, Vst) ->
+ #vst{current=#st{fragile=Fragile0}=St0} = Vst,
+ Fragile = cerl_sets:add_element(Reg, Fragile0),
+ St = St0#st{fragile=Fragile},
Vst#vst{current=St}.
-propagate_fragility(Type, Ss, Vst) ->
- F = fun(S) ->
- case get_raw_type(S, Vst) of
- {fragile,_} -> true;
- _ -> false
- end
- end,
- case any(F, Ss) of
- true -> make_fragile(Type);
- false -> Type
+propagate_fragility(Reg, Args, #vst{current=St0}=Vst) ->
+ #st{fragile=Fragile0} = St0,
+
+ Sources = cerl_sets:from_list(Args),
+ Fragile = case cerl_sets:is_disjoint(Sources, Fragile0) of
+ true -> cerl_sets:del_element(Reg, Fragile0);
+ false -> cerl_sets:add_element(Reg, Fragile0)
+ end,
+
+ St = St0#st{fragile=Fragile},
+ Vst#vst{current=St}.
+
+%% Marks Reg as durable, must be used when assigning a newly created value to
+%% a register.
+remove_fragility(Reg, Vst) ->
+ #vst{current=#st{fragile=Fragile0}=St0} = Vst,
+ case cerl_sets:is_element(Reg, Fragile0) of
+ true ->
+ Fragile = cerl_sets:del_element(Reg, Fragile0),
+ St = St0#st{fragile=Fragile},
+ Vst#vst{current=St};
+ false ->
+ Vst
end.
+%% Marks all registers as durable.
+remove_fragility(#vst{current=St0}=Vst) ->
+ St = St0#st{fragile=cerl_sets:new()},
+ Vst#vst{current=St}.
+
+assert_durable_term(Src, Vst) ->
+ assert_term(Src, Vst),
+ assert_not_fragile(Src, Vst).
+
+assert_not_fragile({Kind,_}=Src, Vst) when Kind =:= x; Kind =:= y ->
+ check_limit(Src),
+ #vst{current=#st{fragile=Fragile}} = Vst,
+ case cerl_sets:is_element(Src, Fragile) of
+ true -> error({fragile_message_reference, Src});
+ false -> ok
+ end;
+assert_not_fragile(Lit, #vst{}) ->
+ assert_literal(Lit),
+ ok.
+
%%%
%%% Return/argument types of BIFs
%%%
@@ -2319,7 +2642,7 @@ bif_return_type('+', Src, Vst) ->
bif_return_type('*', Src, Vst) ->
arith_return_type(Src, Vst);
bif_return_type(abs, [Num], Vst) ->
- case get_durable_term_type(Num, Vst) of
+ case get_term_type(Num, Vst) of
{float,_}=T -> T;
{integer,_}=T -> T;
_ -> number
@@ -2327,8 +2650,10 @@ bif_return_type(abs, [Num], Vst) ->
bif_return_type(float, _, _) -> {float,[]};
bif_return_type('/', _, _) -> {float,[]};
%% Binary operations
-bif_return_type('byte_size', _, _) -> {integer,[]};
-bif_return_type('bit_size', _, _) -> {integer,[]};
+bif_return_type('binary_part', [_,_], _) -> binary;
+bif_return_type('binary_part', [_,_,_], _) -> binary;
+bif_return_type('bit_size', [_], _) -> {integer,[]};
+bif_return_type('byte_size', [_], _) -> {integer,[]};
%% Integer operations.
bif_return_type(ceil, [_], _) -> {integer,[]};
bif_return_type('div', [_,_], _) -> {integer,[]};
@@ -2362,6 +2687,7 @@ bif_return_type(is_boolean, [_], _) -> bool;
bif_return_type(is_binary, [_], _) -> bool;
bif_return_type(is_float, [_], _) -> bool;
bif_return_type(is_function, [_], _) -> bool;
+bif_return_type(is_function, [_,_], _) -> bool;
bif_return_type(is_integer, [_], _) -> bool;
bif_return_type(is_list, [_], _) -> bool;
bif_return_type(is_map, [_], _) -> bool;
@@ -2372,6 +2698,7 @@ bif_return_type(is_reference, [_], _) -> bool;
bif_return_type(is_tuple, [_], _) -> bool;
%% Misc.
bif_return_type(tuple_size, [_], _) -> {integer,[]};
+bif_return_type(map_size, [_], _) -> {integer,[]};
bif_return_type(node, [], _) -> {atom,[]};
bif_return_type(node, [_], _) -> {atom,[]};
bif_return_type(hd, [_], _) -> term;
@@ -2393,14 +2720,24 @@ bif_arg_types('and', [_,_]) -> [bool, bool];
bif_arg_types('or', [_,_]) -> [bool, bool];
bif_arg_types('xor', [_,_]) -> [bool, bool];
%% Binary
-bif_arg_types('byte_size', [_]) -> [binary];
+bif_arg_types('binary_part', [_,_]) ->
+ PosLen = {tuple, 2, #{ {integer,1} => {integer,[]},
+ {integer,2} => {integer,[]} }},
+ [binary, PosLen];
+bif_arg_types('binary_part', [_,_,_]) ->
+ [binary, {integer,[]}, {integer,[]}];
bif_arg_types('bit_size', [_]) -> [binary];
+bif_arg_types('byte_size', [_]) -> [binary];
%% Numerical
bif_arg_types('-', [_]) -> [number];
+bif_arg_types('-', [_,_]) -> [number,number];
bif_arg_types('+', [_]) -> [number];
+bif_arg_types('+', [_,_]) -> [number,number];
bif_arg_types('*', [_,_]) -> [number, number];
bif_arg_types('/', [_,_]) -> [number, number];
+bif_arg_types(abs, [_]) -> [number];
bif_arg_types(ceil, [_]) -> [number];
+bif_arg_types(float, [_]) -> [number];
bif_arg_types(floor, [_]) -> [number];
bif_arg_types(trunc, [_]) -> [number];
bif_arg_types(round, [_]) -> [number];
@@ -2446,14 +2783,14 @@ is_bif_safe(_, _) -> false.
arith_return_type([A], Vst) ->
%% Unary '+' or '-'.
- case get_durable_term_type(A, Vst) of
+ case get_term_type(A, Vst) of
{integer,_} -> {integer,[]};
{float,_} -> {float,[]};
_ -> number
end;
arith_return_type([A,B], Vst) ->
- TypeA = get_durable_term_type(A, Vst),
- TypeB = get_durable_term_type(B, Vst),
+ TypeA = get_term_type(A, Vst),
+ TypeB = get_term_type(B, Vst),
case {TypeA, TypeB} of
{{integer,_},{integer,_}} -> {integer,[]};
{{float,_},_} -> {float,[]};
@@ -2482,7 +2819,7 @@ call_return_type_1(erlang, setelement, 3, Vst) ->
case meet({tuple,[I],#{}}, TupleType) of
{tuple, Sz, Es0} ->
ValueType = get_term_type({x,2}, Vst),
- Es = set_element_type(I, ValueType, Es0),
+ Es = set_element_type({integer,I}, ValueType, Es0),
{tuple, Sz, Es};
none ->
TupleType
@@ -2542,19 +2879,33 @@ math_mod_return_type(fmod, 2) -> {float,[]};
math_mod_return_type(pi, 0) -> {float,[]};
math_mod_return_type(F, A) when is_atom(F), is_integer(A), A >= 0 -> term.
+lists_mod_return_type(all, 2, _Vst) ->
+ bool;
+lists_mod_return_type(any, 2, _Vst) ->
+ bool;
+lists_mod_return_type(keymember, 3, _Vst) ->
+ bool;
+lists_mod_return_type(member, 2, _Vst) ->
+ bool;
+lists_mod_return_type(prefix, 2, _Vst) ->
+ bool;
+lists_mod_return_type(suffix, 2, _Vst) ->
+ bool;
lists_mod_return_type(dropwhile, 2, _Vst) ->
list;
lists_mod_return_type(duplicate, 2, _Vst) ->
list;
lists_mod_return_type(filter, 2, _Vst) ->
list;
+lists_mod_return_type(flatten, 1, _Vst) ->
+ list;
lists_mod_return_type(flatten, 2, _Vst) ->
list;
lists_mod_return_type(map, 2, Vst) ->
same_length_type({x,1}, Vst);
lists_mod_return_type(MF, 3, Vst) when MF =:= mapfoldl; MF =:= mapfoldr ->
ListType = same_length_type({x,2}, Vst),
- {tuple,2,#{1=>ListType}};
+ {tuple,2,#{ {integer,1} => ListType} };
lists_mod_return_type(partition, 2, _Vst) ->
two_tuple(list, list);
lists_mod_return_type(reverse, 1, Vst) ->
@@ -2590,7 +2941,8 @@ lists_mod_return_type(_, _, _) ->
term.
two_tuple(Type1, Type2) ->
- {tuple,2,#{1=>Type1,2=>Type2}}.
+ {tuple,2,#{ {integer,1} => Type1,
+ {integer,2} => Type2 }}.
same_length_type(Reg, Vst) ->
case get_term_type(Reg, Vst) of
@@ -2600,15 +2952,25 @@ same_length_type(Reg, Vst) ->
_ -> list
end.
-check_limit({x,X}) when is_integer(X), X < 1023 ->
- %% Note: x(1023) is reserved for use by the BEAM loader.
- ok;
-check_limit({y,Y}) when is_integer(Y), Y < 1024 ->
- ok;
-check_limit({fr,Fr}) when is_integer(Fr), Fr < 1024 ->
- ok;
-check_limit(_) ->
- error(limit).
+check_limit({x,X}=Src) when is_integer(X) ->
+ if
+ %% Note: x(1023) is reserved for use by the BEAM loader.
+ 0 =< X, X < 1023 -> ok;
+ 1023 =< X -> error(limit);
+ X < 0 -> error({bad_register, Src})
+ end;
+check_limit({y,Y}=Src) when is_integer(Y) ->
+ if
+ 0 =< Y, Y < 1024 -> ok;
+ 1024 =< Y -> error(limit);
+ Y < 0 -> error({bad_register, Src})
+ end;
+check_limit({fr,Fr}=Src) when is_integer(Fr) ->
+ if
+ 0 =< Fr, Fr < 1023 -> ok;
+ 1023 =< Fr -> error(limit);
+ Fr < 0 -> error({bad_register, Src})
+ end.
min(A, B) when is_integer(A), is_integer(B), A < B -> A;
min(A, B) when is_integer(A), is_integer(B) -> B.
diff --git a/lib/compiler/src/cerl_sets.erl b/lib/compiler/src/cerl_sets.erl
index 0361186713..f489baf238 100644
--- a/lib/compiler/src/cerl_sets.erl
+++ b/lib/compiler/src/cerl_sets.erl
@@ -204,4 +204,4 @@ fold(F, Init, D) ->
Set2 :: set(Element).
filter(F, D) ->
- maps:from_list(lists:filter(fun({K,_}) -> F(K) end, maps:to_list(D))).
+ maps:filter(fun(K,_) -> F(K) end, D).
diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl
index 86351bc0c5..e2b8787224 100644
--- a/lib/compiler/src/v3_kernel.erl
+++ b/lib/compiler/src/v3_kernel.erl
@@ -1590,19 +1590,12 @@ match_var([U|Us], Cs0, Def, St) ->
%% constructor/constant as first argument. Group the constructors
%% according to type, the order is really irrelevant but tries to be
%% smart.
-
-match_con(Us, Cs0, Def, St) ->
- %% Expand literals at the top level.
- Cs = [expand_pat_lit_clause(C) || C <- Cs0],
- match_con_1(Us, Cs, Def, St).
-
-match_con_1([U|_Us] = L, Cs, Def, St0) ->
+match_con([U|_Us] = L, Cs, Def, St0) ->
%% Extract clauses for different constructors (types).
%%ok = io:format("match_con ~p~n", [Cs]),
- Ttcs0 = select_types([k_binary], Cs) ++ select_bin_con(Cs) ++
- select_types([k_cons,k_tuple,k_map,k_atom,k_float,
- k_int,k_nil], Cs),
- Ttcs = opt_single_valued(Ttcs0),
+ Ttcs0 = select_types(Cs, [], [], [], [], [], [], [], [], []),
+ Ttcs1 = [{T, Types} || {T, [_ | _] = Types} <- Ttcs0],
+ Ttcs = opt_single_valued(Ttcs1),
%%ok = io:format("ttcs = ~p~n", [Ttcs]),
{Scs,St1} =
mapfoldl(fun ({T,Tcs}, St) ->
@@ -1613,8 +1606,41 @@ match_con_1([U|_Us] = L, Cs, Def, St0) ->
St0, Ttcs),
{build_alt_1st_no_fail(build_select(U, Scs), Def),St1}.
-select_types(Types, Cs) ->
- [{T,Tcs} || T <- Types, begin Tcs = select(T, Cs), Tcs =/= [] end].
+select_types([NoExpC | Cs], Bin, BinCon, Cons, Tuple, Map, Atom, Float, Int, Nil) ->
+ C = expand_pat_lit_clause(NoExpC),
+ case clause_con(C) of
+ k_binary ->
+ select_types(Cs, [C |Bin], BinCon, Cons, Tuple, Map, Atom, Float, Int, Nil);
+ k_bin_seg ->
+ select_types(Cs, Bin, [C | BinCon], Cons, Tuple, Map, Atom, Float, Int, Nil);
+ k_bin_end ->
+ select_types(Cs, Bin, [C | BinCon], Cons, Tuple, Map, Atom, Float, Int, Nil);
+ k_cons ->
+ select_types(Cs, Bin, BinCon, [C | Cons], Tuple, Map, Atom, Float, Int, Nil);
+ k_tuple ->
+ select_types(Cs, Bin, BinCon, Cons, [C | Tuple], Map, Atom, Float, Int, Nil);
+ k_map ->
+ select_types(Cs, Bin, BinCon, Cons, Tuple, [C | Map], Atom, Float, Int, Nil);
+ k_atom ->
+ select_types(Cs, Bin, BinCon, Cons, Tuple, Map, [C | Atom], Float, Int, Nil);
+ k_float ->
+ select_types(Cs, Bin, BinCon, Cons, Tuple, Map, Atom, [C | Float], Int, Nil);
+ k_int ->
+ select_types(Cs, Bin, BinCon, Cons, Tuple, Map, Atom, Float, [C | Int], Nil);
+ k_nil ->
+ select_types(Cs, Bin, BinCon, Cons, Tuple, Map, Atom, Float, Int, [C | Nil])
+ end;
+select_types([], Bin, BinCon, Cons, Tuple, Map, Atom, Float, Int, Nil) ->
+ [{k_binary, reverse(Bin)}] ++ handle_bin_con(reverse(BinCon)) ++
+ [
+ {k_cons, reverse(Cons)},
+ {k_tuple, reverse(Tuple)},
+ {k_map, reverse(Map)},
+ {k_atom, reverse(Atom)},
+ {k_float, reverse(Float)},
+ {k_int, reverse(Int)},
+ {k_nil, reverse(Nil)}
+ ].
expand_pat_lit_clause(#iclause{pats=[#ialias{pat=#k_literal{anno=A,val=Val}}=Alias|Ps]}=C) ->
P = expand_pat_lit(Val, A),
@@ -1743,20 +1769,12 @@ combine_bin_segs(#k_bin_end{}) ->
combine_bin_segs(_) ->
throw(not_possible).
-%% select_bin_con([Clause]) -> [{Type,[Clause]}].
-%% Extract clauses for the k_bin_seg constructor. As k_bin_seg
+%% handle_bin_con([Clause]) -> [{Type,[Clause]}].
+%% Handle clauses for the k_bin_seg constructor. As k_bin_seg
%% matching can overlap, the k_bin_seg constructors cannot be
%% reordered, only grouped.
-select_bin_con(Cs0) ->
- Cs1 = lists:filter(fun (C) ->
- Con = clause_con(C),
- (Con =:= k_bin_seg) or (Con =:= k_bin_end)
- end, Cs0),
- select_bin_con_1(Cs1).
-
-
-select_bin_con_1(Cs) ->
+handle_bin_con(Cs) ->
try
%% The usual way to match literals is to first extract the
%% value to a register, and then compare the register to the
@@ -1795,14 +1813,14 @@ select_bin_con_1(Cs) ->
end
catch
throw:not_possible ->
- select_bin_con_2(Cs)
+ handle_bin_con_not_possible(Cs)
end.
-select_bin_con_2([C1|Cs]) ->
+handle_bin_con_not_possible([C1|Cs]) ->
Con = clause_con(C1),
{More,Rest} = splitwith(fun (C) -> clause_con(C) =:= Con end, Cs),
- [{Con,[C1|More]}|select_bin_con_2(Rest)];
-select_bin_con_2([]) -> [].
+ [{Con,[C1|More]}|handle_bin_con_not_possible(Rest)];
+handle_bin_con_not_possible([]) -> [].
%% select_bin_int([Clause]) -> {k_bin_int,[Clause]}
%% If the first pattern in each clause selects the same integer,
@@ -1902,10 +1920,6 @@ select_utf8(Val0) ->
throw(not_possible)
end.
-%% select(Con, [Clause]) -> [Clause].
-
-select(T, Cs) -> [ C || C <- Cs, clause_con(C) =:= T ].
-
%% match_value([Var], Con, [Clause], Default, State) -> {SelectExpr,State}.
%% At this point all the clauses have the same constructor, we must
%% now separate them according to value.
@@ -2040,6 +2054,10 @@ get_match(#k_cons{}, St0) ->
get_match(#k_binary{}, St0) ->
{[V]=Mes,St1} = new_vars(1, St0),
{#k_binary{segs=V},Mes,St1};
+get_match(#k_bin_seg{size=#k_atom{val=all},next={k_bin_end,[]}}=Seg, St0) ->
+ {[S,N0],St1} = new_vars(2, St0),
+ N = set_kanno(N0, [no_usage]),
+ {Seg#k_bin_seg{seg=S,next=N},[S],St1};
get_match(#k_bin_seg{}=Seg, St0) ->
{[S,N0],St1} = new_vars(2, St0),
N = set_kanno(N0, [no_usage]),
@@ -2067,6 +2085,9 @@ new_clauses(Cs0, U, St) ->
#k_cons{hd=H,tl=T} -> [H,T|As];
#k_tuple{es=Es} -> Es ++ As;
#k_binary{segs=E} -> [E|As];
+ #k_bin_seg{size=#k_atom{val=all},
+ seg=S,next={k_bin_end,[]}} ->
+ [S|As];
#k_bin_seg{seg=S,next=N} ->
[S,N|As];
#k_bin_int{next=N} ->
diff --git a/lib/compiler/test/beam_except_SUITE.erl b/lib/compiler/test/beam_except_SUITE.erl
index 9380fe06c8..8e3b373d29 100644
--- a/lib/compiler/test/beam_except_SUITE.erl
+++ b/lib/compiler/test/beam_except_SUITE.erl
@@ -84,9 +84,16 @@ coverage(_) ->
{'EXIT',{function_clause,
[{?MODULE,fc,[y],[File,{line,2}]}|_]}} =
(catch fc(y)),
- {'EXIT',{function_clause,
- [{?MODULE,fc,[[a,b,c]],[File,{line,6}]}|_]}} =
- (catch fc([a,b,c])),
+ case ?MODULE of
+ beam_except_no_opt_SUITE ->
+ %% There will be a different stack fram in
+ %% unoptimized code.
+ ok;
+ _ ->
+ {'EXIT',{function_clause,
+ [{?MODULE,fc,[[a,b,c]],[File,{line,6}]}|_]}} =
+ (catch fc([a,b,c]))
+ end,
{'EXIT',{undef,[{erlang,error,[a,b,c],_}|_]}} =
(catch erlang:error(a, b, c)),
diff --git a/lib/compiler/test/beam_jump_SUITE.erl b/lib/compiler/test/beam_jump_SUITE.erl
index 759d884dc4..a456f31d79 100644
--- a/lib/compiler/test/beam_jump_SUITE.erl
+++ b/lib/compiler/test/beam_jump_SUITE.erl
@@ -79,12 +79,13 @@ checks(Wanted) ->
{catch case river() of sheet -> begin +Wanted, if "da" -> Wanted end end end, catch case river() of sheet -> begin + Wanted, if "da" -> Wanted end end end}.
unsafe_move_elimination(_Config) ->
- {{left,right,false},false} = unsafe_move_elimination(left, right, false),
- {{false,right,false},false} = unsafe_move_elimination(false, right, true),
- {{true,right,right},right} = unsafe_move_elimination(true, right, true),
+ {{left,right,false},false} = unsafe_move_elimination_1(left, right, false),
+ {{false,right,false},false} = unsafe_move_elimination_1(false, right, true),
+ {{true,right,right},right} = unsafe_move_elimination_1(true, right, true),
+ [ok = unsafe_move_elimination_2(I) || I <- lists:seq(0,16)],
ok.
-unsafe_move_elimination(Left, Right, Simple0) ->
+unsafe_move_elimination_1(Left, Right, Simple0) ->
id(1),
%% The move at label 29 would be removed by beam_jump, which is unsafe because
@@ -115,6 +116,44 @@ unsafe_move_elimination(Left, Right, Simple0) ->
end,
{id({Left,Right,Simple}),Simple}.
+unsafe_move_elimination_2(Int) ->
+ %% The type optimization pass would recognize that TagInt can only be
+ %% [0 .. 7], so the first 'case' would select_val over [0 .. 6] and swap
+ %% out the fail label with the block for 7.
+ %%
+ %% A later optimization would merge this block with 'expects_h' in the
+ %% second case, as the latter is only reachable from the former.
+ %%
+ %% ... but this broke down when the move elimination optimization didn't
+ %% take the fail label of the first select_val into account. This caused it
+ %% to believe that the only way to reach 'expects_h' was through the second
+ %% case when 'Tag' =:= 'h', which made it remove the move instruction
+ %% added in the first case, passing garbage to expects_h/2.
+ TagInt = Int band 2#111,
+ Tag = case TagInt of
+ 0 -> a;
+ 1 -> b;
+ 2 -> c;
+ 3 -> d;
+ 4 -> e;
+ 5 -> f;
+ 6 -> g;
+ 7 -> h
+ end,
+ case Tag of
+ g -> expects_g(TagInt, Tag);
+ h -> expects_h(TagInt, Tag);
+ _ -> Tag = id(Tag), ok
+ end.
+
+expects_g(6, Atom) ->
+ Atom = id(g),
+ ok.
+
+expects_h(7, Atom) ->
+ Atom = id(h),
+ ok.
+
-record(message2, {id, p1}).
-record(message3, {id, p1, p2}).
diff --git a/lib/compiler/test/beam_validator_SUITE.erl b/lib/compiler/test/beam_validator_SUITE.erl
index 2660bf222c..de5a3c2873 100644
--- a/lib/compiler/test/beam_validator_SUITE.erl
+++ b/lib/compiler/test/beam_validator_SUITE.erl
@@ -34,7 +34,8 @@
undef_label/1,illegal_instruction/1,failing_gc_guard_bif/1,
map_field_lists/1,cover_bin_opt/1,
val_dsetel/1,bad_tuples/1,bad_try_catch_nesting/1,
- receive_stacked/1,aliased_types/1]).
+ receive_stacked/1,aliased_types/1,type_conflict/1,
+ infer_on_eq/1]).
-include_lib("common_test/include/ct.hrl").
@@ -63,7 +64,8 @@ groups() ->
undef_label,illegal_instruction,failing_gc_guard_bif,
map_field_lists,cover_bin_opt,val_dsetel,
bad_tuples,bad_try_catch_nesting,
- receive_stacked,aliased_types]}].
+ receive_stacked,aliased_types,type_conflict,
+ infer_on_eq]}].
init_per_suite(Config) ->
test_lib:recompile(?MODULE),
@@ -107,13 +109,12 @@ xrange(Config) when is_list(Config) ->
Errors = do_val(xrange, Config),
[{{t,sum_1,2},
{{bif,'+',{f,0},[{x,-1},{x,1}],{x,0}},4,
- {uninitialized_reg,{x,-1}}}},
+ {bad_register,{x,-1}}}},
{{t,sum_2,2},
- {{bif,'+',{f,0},[{x,0},{x,1023}],{x,0}},4,
- {uninitialized_reg,{x,1023}}}},
+ {{bif,'+',{f,0},[{x,0},{x,1023}],{x,0}},4,limit}},
{{t,sum_3,2},
{{bif,'+',{f,0},[{x,0},{x,1}],{x,-1}},4,
- {invalid_store,{x,-1},number}}},
+ {bad_register,{x,-1}}}},
{{t,sum_4,2},
{{bif,'+',{f,0},[{x,0},{x,1}],{x,1023}},4,limit}}] = Errors,
ok.
@@ -122,15 +123,15 @@ yrange(Config) when is_list(Config) ->
Errors = do_val(yrange, Config),
[{{t,sum_1,2},
{{move,{x,1},{y,-1}},5,
- {invalid_store,{y,-1},term}}},
+ {bad_register,{y,-1}}}},
{{t,sum_2,2},
{{bif,'+',{f,0},[{x,0},{y,1024}],{x,0}},7,
- {uninitialized_reg,{y,1024}}}},
+ limit}},
{{t,sum_3,2},
{{move,{x,1},{y,1024}},5,limit}},
{{t,sum_4,2},
{{move,{x,1},{y,-1}},5,
- {invalid_store,{y,-1},term}}}] = Errors,
+ {bad_register,{y,-1}}}}] = Errors,
ok.
stack(Config) when is_list(Config) ->
@@ -157,8 +158,8 @@ call_last(Config) when is_list(Config) ->
merge_undefined(Config) when is_list(Config) ->
Errors = do_val(merge_undefined, Config),
[{{t,handle_call,2},
- {{call_ext,1,{extfunc,erlang,exit,1}},
- 10,
+ {{call_ext,2,{extfunc,debug,filter,2}},
+ 22,
{uninitialized_reg,{y,_}}}}] = Errors,
ok.
@@ -178,7 +179,7 @@ unsafe_catch(Config) when is_list(Config) ->
Errors = do_val(unsafe_catch, Config),
[{{t,small,2},
{{bs_put_integer,{f,0},{integer,16},1,
- {field_flags,[unsigned,big]},{y,0}},
+ {field_flags,[unsigned,big]},{y,0}},
20,
{unassigned,{y,0}}}}] = Errors,
ok.
@@ -223,7 +224,7 @@ bad_catch_try(Config) when is_list(Config) ->
{{try_case,{y,1}},12,{invalid_tag,{y,1},term}}},
{{bad_catch_try,bad_6,1},
{{move,{integer,1},{y,1}},7,
- {invalid_store,{y,1},{integer,1}}}}] = Errors,
+ {invalid_store,{y,1}}}}] = Errors,
ok.
cons_guard(Config) when is_list(Config) ->
@@ -247,7 +248,7 @@ freg_range(Config) when is_list(Config) ->
{{t,sum_3,2},
{{bif,fadd,{f,0},[{fr,0},{fr,1}],{fr,-1}},
7,
- {bad_target,{fr,-1}}}},
+ {bad_register,{fr,-1}}}},
{{t,sum_4,2},
{{bif,fadd,{f,0},[{fr,0},{fr,1}],{fr,1024}},
7,
@@ -631,6 +632,53 @@ aliased_types_3(Bug) ->
hd(List)
end.
+
+%% ERL-867; validation proceeded after a type conflict, causing incorrect types
+%% to be joined.
+
+-record(r, { e1 = e1, e2 = e2 }).
+
+type_conflict(Config) when is_list(Config) ->
+ {e1, e2} = type_conflict_1(#r{}),
+ ok.
+
+type_conflict_1(C) ->
+ Src = id(C#r.e2),
+ TRes = try id(Src) of
+ R -> R
+ catch
+ %% C:R can never match, yet it assumed that the type of 'C' was
+ %% an atom from here on.
+ C:R -> R
+ end,
+ {C#r.e1, TRes}.
+
+%% ERL-886; validation failed to infer types on both sides of '=:='
+
+infer_on_eq(Config) when is_list(Config) ->
+ {ok, gurka} = infer_on_eq_1(id({gurka})),
+ {ok, gaffel} = infer_on_eq_2(id({gaffel})),
+ {ok, elefant} = infer_on_eq_3(id({elefant})),
+ {ok, myra} = infer_on_eq_4(id({myra})),
+ ok.
+
+infer_on_eq_1(T) ->
+ 1 = erlang:tuple_size(T),
+ {ok, erlang:element(1, T)}.
+
+infer_on_eq_2(T) ->
+ Size = erlang:tuple_size(T),
+ Size = 1,
+ {ok, erlang:element(1, T)}.
+
+infer_on_eq_3(T) ->
+ true = 1 =:= erlang:tuple_size(T),
+ {ok, erlang:element(1, T)}.
+
+infer_on_eq_4(T) ->
+ true = erlang:tuple_size(T) =:= 1,
+ {ok, erlang:element(1, T)}.
+
%%%-------------------------------------------------------------------------
transform_remove(Remove, Module) ->
diff --git a/lib/compiler/test/beam_validator_SUITE_data/merge_undefined.S b/lib/compiler/test/beam_validator_SUITE_data/merge_undefined.S
index 481d55045d..aa344807e4 100644
--- a/lib/compiler/test/beam_validator_SUITE_data/merge_undefined.S
+++ b/lib/compiler/test/beam_validator_SUITE_data/merge_undefined.S
@@ -15,8 +15,9 @@
{select_val,{x,0},{f,1},{list,[{atom,gurka},{f,3},{atom,delete},{f,4}]}}.
{label,3}.
{allocate_heap,2,6,2}.
- %% The Y registers are not initialized here.
{test,is_eq_exact,{f,5},[{x,0},{atom,ok}]}.
+ %% This is unreachable since {x,0} is known not to be 'ok'. We should not
+ %% fail with "uninitialized y registers" on erlang:exit/1
{move,{atom,nisse},{x,0}}.
{call_ext,1,{extfunc,erlang,exit,1}}.
{label,4}.
@@ -29,6 +30,7 @@
{call_ext,2,{extfunc,io,format,2}}.
{test,is_ne_exact,{f,6},[{x,0},{atom,ok}]}.
{label,5}.
+ %% The Y registers are not initialized here.
{move,{atom,logReader},{x,1}}.
{move,{atom,console},{x,0}}.
{call_ext,2,{extfunc,debug,filter,2}}.
diff --git a/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S b/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S
index 5b974119c6..a878204d16 100644
--- a/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S
+++ b/lib/compiler/test/beam_validator_SUITE_data/receive_stacked.S
@@ -240,7 +240,7 @@
{y,0}}.
{'%',{no_bin_opt,{binary_used_in,{test,is_binary,{f,34},[{y,0}]}},
[63,{file,"receive_stacked.erl"}]}}.
- {test,is_binary,{f,34},[{y,0}]}.
+ {test,is_eq_exact,{f,34},[{y,0},{literal,<<0,1,2,3>>}]}.
remove_message.
{move,{integer,42},{x,0}}.
{line,[{location,"receive_stacked.erl",64}]}.
@@ -283,7 +283,7 @@
{y,0}}.
{'%',{no_bin_opt,{[{x,1},{y,0}],{loop_rec_end,{f,38}},not_handled},
[70,{file,"receive_stacked.erl"}]}}.
- {test,is_binary,{f,39},[{x,0}]}.
+ {test,is_eq_exact,{f,39},[{x,0},{literal,<<0,1,2,3>>}]}.
remove_message.
{move,{integer,42},{x,0}}.
{line,[{location,"receive_stacked.erl",71}]}.
diff --git a/lib/compiler/test/float_SUITE.erl b/lib/compiler/test/float_SUITE.erl
index 831e8279aa..0fa8070dc8 100644
--- a/lib/compiler/test/float_SUITE.erl
+++ b/lib/compiler/test/float_SUITE.erl
@@ -21,15 +21,16 @@
-export([all/0, suite/0,groups/0,init_per_suite/1, end_per_suite/1,
init_per_group/2,end_per_group/2,
pending/1,bif_calls/1,math_functions/1,mixed_float_and_int/1,
- subtract_number_type/1]).
+ subtract_number_type/1,float_followed_by_guard/1]).
-include_lib("common_test/include/ct.hrl").
suite() -> [{ct_hooks,[ts_install_cth]}].
-all() ->
+all() ->
[pending, bif_calls, math_functions,
- mixed_float_and_int, subtract_number_type].
+ mixed_float_and_int, subtract_number_type,
+ float_followed_by_guard].
groups() ->
[].
@@ -187,5 +188,21 @@ fact(0, P) -> P;
fact(1, P) -> P;
fact(N, P) -> fact(N-1, P*N).
+float_followed_by_guard(Config) when is_list(Config) ->
+ true = ffbg_1(5, 1),
+ false = ffbg_1(1, 5),
+ ok.
+
+ffbg_1(A, B0) ->
+ %% This is a non-guard block followed by a *guard block* that starts with a
+ %% floating point operation, and the compiler erroneously assumed that it
+ %% was safe to skip fcheckerror because the next block started with a float
+ %% op.
+ B = id(B0) / 1.0,
+ if
+ A - B > 0.0 -> true;
+ A - B =< 0.0 -> false
+ end.
+
id(I) -> I.
diff --git a/lib/compiler/test/receive_SUITE.erl b/lib/compiler/test/receive_SUITE.erl
index 12108445f0..0038eb1a4b 100644
--- a/lib/compiler/test/receive_SUITE.erl
+++ b/lib/compiler/test/receive_SUITE.erl
@@ -25,7 +25,8 @@
init_per_group/2,end_per_group/2,
init_per_testcase/2,end_per_testcase/2,
export/1,recv/1,coverage/1,otp_7980/1,ref_opt/1,
- wait/1,recv_in_try/1,double_recv/1,receive_var_zero/1]).
+ wait/1,recv_in_try/1,double_recv/1,receive_var_zero/1,
+ match_built_terms/1]).
-include_lib("common_test/include/ct.hrl").
@@ -45,7 +46,8 @@ all() ->
groups() ->
[{p,test_lib:parallel(),
[recv,coverage,otp_7980,ref_opt,export,wait,
- recv_in_try,double_recv,receive_var_zero]}].
+ recv_in_try,double_recv,receive_var_zero,
+ match_built_terms]}].
init_per_suite(Config) ->
@@ -400,5 +402,29 @@ receive_var_zero(Config) when is_list(Config) ->
zero() -> 0.
+%% ERL-862; the validator would explode when a term was constructed in a
+%% receive guard.
+
+-define(MATCH_BUILT_TERM(Ref, Expr),
+ (fun() ->
+ Ref = make_ref(),
+ A = id($a),
+ B = id($b),
+ Built = id(Expr),
+ self() ! {Ref, A, B},
+ receive
+ {Ref, A, B} when Expr =:= Built ->
+ ok
+ after 5000 ->
+ ct:fail("Failed to match message with term built in "
+ "receive guard.")
+ end
+ end)()).
+
+match_built_terms(Config) when is_list(Config) ->
+ ?MATCH_BUILT_TERM(Ref, [A, B]),
+ ?MATCH_BUILT_TERM(Ref, {A, B}),
+ ?MATCH_BUILT_TERM(Ref, <<A, B>>),
+ ?MATCH_BUILT_TERM(Ref, #{ 1 => A, 2 => B}).
id(I) -> I.
diff --git a/lib/compiler/vsn.mk b/lib/compiler/vsn.mk
index efedb414ad..a523627384 100644
--- a/lib/compiler/vsn.mk
+++ b/lib/compiler/vsn.mk
@@ -1 +1 @@
-COMPILER_VSN = 7.3.1
+COMPILER_VSN = 7.3.2
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-19 03:39:13 +0000