Skip to content

Commit

Permalink
beam_bool: Fix unsafe optimization
Browse files Browse the repository at this point in the history 
beam_bool would make the following code unsafe (which would be
reported by beam_validator):

scotland(Echo) ->
  found(case Echo of
	    Echo when true; Echo, Echo, Echo ->
		Echo;
	    echo ->
		[]
	end,
	Echo = placed).

found(_, _) -> million.

Basically, beam_bool would see that the 'case' would always return
the value of Echo. Thus:

scotland(Echo) ->
  found(Echo, Echo = placed).

The only problem is that beam_bool would also remove a 'move'
instruction that would save Echo to the stack. Here is the
assembly code for part of the function:

    {allocate_zero,1,1}.

    {move,{x,0},{y,0}}.           %% Save Echo on stack.

    {bif,'=:=',{f,7},[{x,0},{atom,true}],{x,1}}.
    {bif,'=:=',{f,7},[{x,0},{atom,true}],{x,2}}.
    {bif,'=:=',{f,7},[{x,0},{atom,true}],{x,3}}.
    {bif,'and',{f,7},[{x,2},{x,3}],{x,2}}.
    {bif,'and',{f,7},[{x,1},{x,2}],{x,1}}.
    {jump,{f,8}}.

  {label,7}.
    {move,{atom,false},{x,1}}.

  {label,8}.
    {bif,'or',{f,6},[{atom,true},{x,1}],{x,1}}.
    {test,is_eq_exact,{f,6},[{x,1},{atom,true}]}. %% Jump never taken.

    {jump,{f,5}}.

  {label,6}.
    {test,is_eq_exact,{f,9},[{x,0},{atom,echo}]}.
    {move,nil,{x,0}}.
    {jump,{f,5}}.
  {label,9}.
    {test_heap,3,0}.
    {put_tuple,2,{x,0}}.
    {put,{atom,case_clause}}.
    {put,{y,0}}.
    {line,[{location,"t.erl",5}]}.
    {call_ext,1,{extfunc,erlang,error,1}}.
    {jump,{f,5}}.

  {label,5}.
    {test,is_eq_exact,{f,12},[{atom,placed},{y,0}]}.

beam_bool would see that the is_eq_exact test at label 8 would
always succeed. It could therefore remove most of the code before
the jump to label 5. Unfortunately it also removed the essential
move of Echo to the stack:

    {allocate_zero,1,1}.

    %% Instruction incorrectly removed: {move,{x,0},{y,0}}.

    {jump,{f,5}}.

  {label,5}.
    {test,is_eq_exact,{f,12},[{atom,placed},{y,0}]}.

The root cause of the problem is that the 'move' instruction is
included in the block of 'bif' instructions before label 8.
Normally the 'move' instruction would not have been discarded,
but because the left operand to the 'or' BIF is 'true', the
entire block with 'bif' instructions are dropped.

As far as I can see, there is no gain by including 'move'
instructions in the first place. There is no way that better
code will be produced. In fact, the entire optimization can
be given up if 'move' instructions are found in the block.

Thus we can fix this bug by never including any 'move' instructions
in the block of 'bif' instructions. We can also remove all the
code that deals with 'move' instructions within blocks.

Reported-by: Thomas Arts
  • Loading branch information
@bjorng
bjorng committed Jan 7, 2016
1 parent 82a835d commit 7c72e25
Show file tree
Hide file tree
Showing 2 changed files with 27 additions and 50 deletions.
50 changes: 2 additions & 48 deletions lib/compiler/src/beam_bool.erl
View file
Original file line number Diff line number Diff line change
Expand Up @@ -142,11 +142,6 @@ bopt_block(Reg, Fail, OldIs, [{block,Bl0}|Acc0], St0) ->
throw:not_boolean_expr ->
failed;

%% The block contains a 'move' instruction that could
%% not be handled.
throw:move ->
failed;

%% The optimization is not safe. (A register
%% used by the instructions following the
%% optimized code is either not assigned a
Expand Down Expand Up @@ -215,37 +210,14 @@ ensure_opt_safe(Bl, NewCode, OldIs, Fail, PrecedingCode, St) ->
false -> throw(all_registers_not_killed);
true -> ok
end,
Same = assigned_same_value(Bl, NewCode),
MustBeUnused = ordsets:subtract(ordsets:union(NotSet, NewDst),
ordsets:union(MustBeKilled, Same)),
MustBeKilled),
case none_used(MustBeUnused, OldIs, Fail, St) of
false -> throw(registers_used);
true -> ok
end,
ok.

%% assigned_same_value(OldCode, NewCodeReversed) -> [DestinationRegs]
%% Return an ordset with a list of all y registers that are always
%% assigned the same value in the old and new code. Currently, we
%% are very conservative in that we only consider identical move
%% instructions in the same order.
%%
assigned_same_value(Old, New) ->
case reverse(New) of
[{block,Bl}|_] ->
assigned_same_value(Old, Bl, []);
_ ->
ordsets:new()
end.

assigned_same_value([{set,[{y,_}=D],[S],move}|T1],
[{set,[{y,_}=D],[S],move}|T2], Acc) ->
assigned_same_value(T1, T2, [D|Acc]);
assigned_same_value(_, _, Acc) ->
ordsets:from_list(Acc).

update_fail_label([{set,_,_,move}=I|Is], Fail, Acc) ->
update_fail_label(Is, Fail, [I|Acc]);
update_fail_label([{set,Ds,As,{bif,N,{f,_}}}|Is], Fail, Acc) ->
update_fail_label(Is, Fail, [{set,Ds,As,{bif,N,{f,Fail}}}|Acc]);
update_fail_label([{set,Ds,As,{alloc,Regs,{gc_bif,N,{f,_}}}}|Is], Fail, Acc) ->
Expand Down Expand Up @@ -314,8 +286,6 @@ split_block_1(Is, Fail, ProhibitFailLabel) ->
end
end.

split_block_2([{set,_,_,move}=I|Is], Fail, Acc) ->
split_block_2(Is, Fail, [I|Acc]);
split_block_2([{set,[_],_,{bif,_,{f,Fail}}}=I|Is], Fail, Acc) ->
split_block_2(Is, Fail, [I|Acc]);
split_block_2([{set,[_],_,{alloc,_,{gc_bif,_,{f,Fail}}}}=I|Is], Fail, Acc) ->
Expand Down Expand Up @@ -343,8 +313,6 @@ dst_regs([{set,[D],_,{bif,_,{f,_}}}|Is], Acc) ->
dst_regs(Is, [D|Acc]);
dst_regs([{set,[D],_,{alloc,_,{gc_bif,_,{f,_}}}}|Is], Acc) ->
dst_regs(Is, [D|Acc]);
dst_regs([{set,[D],_,move}|Is], Acc) ->
dst_regs(Is, [D|Acc]);
dst_regs([_|Is], Acc) ->
dst_regs(Is, Acc);
dst_regs([], Acc) -> ordsets:from_list(Acc).
Expand Down Expand Up @@ -411,13 +379,6 @@ bopt_tree([{protected,[Dst],Code,_}|Is], Forest0, Pre) ->
_Res ->
throw(not_boolean_expr)
end;
bopt_tree([{set,[Dst],[Src],move}=Move|Is], Forest, Pre) ->
case {Src,Dst} of
{{tmp,_},_} -> throw(move);
{_,{tmp,_}} -> throw(move);
_ -> ok
end,
bopt_tree(Is, Forest, [Move|Pre]);
bopt_tree([{set,[Dst],As,{bif,N,_}}=Bif|Is], Forest0, Pre) ->
Ar = length(As),
case safe_bool_op(N, Ar) of
Expand Down Expand Up @@ -589,10 +550,6 @@ free_variables(Is) ->
E = gb_sets:empty(),
free_vars_1(Is, E, E, E).

free_vars_1([{set,Ds,As,move}|Is], F0, N0, A) ->
F = gb_sets:union(F0, gb_sets:difference(var_list(As), N0)),
N = gb_sets:union(N0, var_list(Ds)),
free_vars_1(Is, F, N, A);
free_vars_1([{set,Ds,As,{bif,_,_}}|Is], F0, N0, A) ->
F = gb_sets:union(F0, gb_sets:difference(var_list(As), N0)),
N = gb_sets:union(N0, var_list(Ds)),
Expand Down Expand Up @@ -632,8 +589,6 @@ free_vars_regs(X) -> [{x,X-1}|free_vars_regs(X-1)].
rename_regs(Is, Regs) ->
rename_regs(Is, Regs, []).

rename_regs([{set,_,_,move}=I|Is], Regs, Acc) ->
rename_regs(Is, Regs, [I|Acc]);
rename_regs([{set,[Dst0],Ss0,{alloc,_,Info}}|Is], Regs0, Acc) ->
Live = live_regs(Regs0),
Ss = rename_sources(Ss0, Regs0),
Expand Down Expand Up @@ -737,8 +692,7 @@ ssa_assign({x,_}=R, #ssa{sub=Sub0}=Ssa0) ->
Sub1 = gb_trees:update(R, NewReg, Sub0),
Sub = gb_trees:insert(NewReg, NewReg, Sub1),
Ssa#ssa{sub=Sub}
end;
ssa_assign(_, Ssa) -> Ssa.
end.

ssa_sub_list(List, Sub) ->
[ssa_sub(E, Sub) || E <- List].
Expand Down
27 changes: 25 additions & 2 deletions lib/compiler/test/guard_SUITE.erl
View file
Original file line number Diff line number Diff line change
Expand Up @@ -34,7 +34,7 @@
tricky/1,rel_ops/1,rel_op_combinations/1,literal_type_tests/1,
basic_andalso_orelse/1,traverse_dcd/1,
check_qlc_hrl/1,andalso_semi/1,t_tuple_size/1,binary_part/1,
bad_constants/1,bad_guards/1]).
bad_constants/1,bad_guards/1,scotland/1]).

suite() -> [{ct_hooks,[ts_install_cth]}].

Expand All @@ -52,7 +52,7 @@ groups() ->
rel_ops,rel_op_combinations,
literal_type_tests,basic_andalso_orelse,traverse_dcd,
check_qlc_hrl,andalso_semi,t_tuple_size,binary_part,
bad_constants,bad_guards]}].
bad_constants,bad_guards,scotland]}].

init_per_suite(Config) ->
Config.
Expand Down Expand Up @@ -1831,6 +1831,29 @@ bad_guards_2(M, [_]) when M#{a := 0, b => 0}, map_size(M) ->
bad_guards_3(M, [_]) when is_map(M) andalso M#{a := 0, b => 0}, length(M) ->
ok.

%% beam_bool would remove the initialization of {y,0}.
%% (Thanks to Thomas Arts and QuickCheck.)

scotland(_Config) ->
million = do_scotland(placed),
{'EXIT',{{badmatch,placed},_}} = (catch do_scotland(false)),
{'EXIT',{{badmatch,placed},_}} = (catch do_scotland(true)),
{'EXIT',{{badmatch,placed},_}} = (catch do_scotland(echo)),
ok.

do_scotland(Echo) ->
found(case Echo of
Echo when true; Echo, Echo, Echo ->
Echo;
echo ->
[]
end,
Echo = placed).

found(_, _) -> million.



%% Call this function to turn off constant propagation.
id(I) -> I.

Expand Down

0 comments on commit 7c72e25

Please sign in to comment.