diff options
Diffstat (limited to 'lib/compiler')
| -rw-r--r-- | lib/compiler/src/beam_block.erl | 45 | ||||
| -rw-r--r-- | lib/compiler/src/beam_clean.erl | 21 | ||||
| -rw-r--r-- | lib/compiler/src/beam_flatten.erl | 3 | ||||
| -rw-r--r-- | lib/compiler/src/beam_split.erl | 7 | ||||
| -rw-r--r-- | lib/compiler/src/beam_type.erl | 619 | ||||
| -rw-r--r-- | lib/compiler/src/beam_utils.erl | 105 | ||||
| -rw-r--r-- | lib/compiler/src/beam_validator.erl | 31 | ||||
| -rw-r--r-- | lib/compiler/test/beam_type_SUITE.erl | 25 | ||||
| -rw-r--r-- | lib/compiler/test/beam_validator_SUITE.erl | 12 | ||||
| -rw-r--r-- | lib/compiler/test/beam_validator_SUITE_data/bad_try_catch_nesting.S | 64 |
10 files changed, 628 insertions, 304 deletions
diff --git a/lib/compiler/src/beam_block.erl b/lib/compiler/src/beam_block.erl index 9543aa1355..8cd271e1dc 100644 --- a/lib/compiler/src/beam_block.erl +++ b/lib/compiler/src/beam_block.erl @@ -36,13 +36,11 @@ module({Mod,Exp,Attr,Fs0,Lc}, Opts) -> function({function,Name,Arity,CLabel,Is0}, Blockify) -> try %% Collect basic blocks and optimize them. - Is2 = case Blockify of - true -> - Is1 = blockify(Is0), - embed_lines(Is1); - false -> - Is0 + Is1 = case Blockify of + false -> Is0; + true -> blockify(Is0) end, + Is2 = embed_lines(Is1), Is3 = local_cse(Is2), Is4 = beam_utils:anno_defs(Is3), Is5 = move_allocates(Is4), @@ -139,6 +137,11 @@ embed_lines([{block,B2},{line,_}=Line,{block,B1}|T], Acc) -> embed_lines([{block,B1},{line,_}=Line|T], Acc) -> B = {block,[{set,[],[],Line}|B1]}, embed_lines([B|T], Acc); +embed_lines([{block,B2},{block,B1}|T], Acc) -> + %% This can only happen when beam_block is run for + %% the second time. + B = {block,B1++B2}, + embed_lines([B|T], Acc); embed_lines([I|Is], Acc) -> embed_lines(Is, [I|Acc]); embed_lines([], Acc) -> Acc. @@ -206,7 +209,7 @@ move_allocates([]) -> []. move_allocates_1([{'%anno',_}|Is], Acc) -> move_allocates_1(Is, Acc); -move_allocates_1([I|Is], [{set,[],[],{alloc,Live0,Info}}|Acc]=Acc0) -> +move_allocates_1([I|Is], [{set,[],[],{alloc,Live0,Info0}}|Acc]=Acc0) -> case alloc_may_pass(I) of false -> move_allocates_1(Is, [I|Acc0]); @@ -215,6 +218,7 @@ move_allocates_1([I|Is], [{set,[],[],{alloc,Live0,Info}}|Acc]=Acc0) -> not_possible -> move_allocates_1(Is, [I|Acc0]); Live when is_integer(Live) -> + Info = safe_info(Info0), A = {set,[],[],{alloc,Live,Info}}, move_allocates_1(Is, [A,I|Acc]) end @@ -230,6 +234,13 @@ alloc_may_pass({set,_,_,put_list}) -> false; alloc_may_pass({set,_,_,put}) -> false; alloc_may_pass({set,_,_,_}) -> true. +safe_info({nozero,Stack,Heap,_}) -> + %% nozero is not safe if the allocation instruction is moved + %% upwards past an instruction that may throw an exception + %% (such as element/2). + {zero,Stack,Heap,[]}; +safe_info(Info) -> Info. + %% opt([Instruction]) -> [Instruction] %% Optimize the instruction stream inside a basic block. @@ -352,10 +363,18 @@ opt_tuple_element_1([{set,[D],[S],move}|Is0], I0, {_,S}, Acc) -> case eliminate_use_of_from_reg(Is0, S, D) of no -> no; - {yes,Is} -> + {yes,Is1} -> {set,[S],Ss,Op} = I0, I = {set,[D],Ss,Op}, - {yes,reverse(Acc, [I|Is])} + case opt_move_rev(S, Acc, [I|Is1]) of + not_possible -> + %% Not safe because the move of the + %% get_tuple_element instruction would cause the + %% result of a previous instruction to be ignored. + no; + {_,Is} -> + {yes,Is} + end end; opt_tuple_element_1([{set,Ds,Ss,_}=I|Is], MovedI, {S,D}=Regs, Acc) -> case member(S, Ds) orelse member(D, Ss) of @@ -620,7 +639,13 @@ cse_find(Expr, Es) -> end. cse_expr({set,[D],Ss,{bif,N,_}}) -> - {ok,D,{{bif,N},Ss}}; + case D of + {fr,_} -> + %% There are too many things that can go wrong. + none; + _ -> + {ok,D,{{bif,N},Ss}} + end; cse_expr({set,[D],Ss,{alloc,_,{gc_bif,N,_}}}) -> {ok,D,{{gc_bif,N},Ss}}; cse_expr({set,[D],Ss,put_list}) -> diff --git a/lib/compiler/src/beam_clean.erl b/lib/compiler/src/beam_clean.erl index e094c2c320..7ddf9fa2e2 100644 --- a/lib/compiler/src/beam_clean.erl +++ b/lib/compiler/src/beam_clean.erl @@ -24,7 +24,7 @@ -export([module/2]). -export([bs_clean_saves/1]). -export([clean_labels/1]). --import(lists, [foldl/3,reverse/1,filter/2]). +-import(lists, [foldl/3,reverse/1]). -spec module(beam_utils:module_code(), [compile:option()]) -> {'ok',beam_utils:module_code()}. @@ -303,8 +303,21 @@ maybe_remove_lines(Fs, Opts) -> end. remove_lines([{function,N,A,Lbl,Is0}|T]) -> - Is = filter(fun({line,_}) -> false; - (_) -> true - end, Is0), + Is = remove_lines_fun(Is0), [{function,N,A,Lbl,Is}|remove_lines(T)]; remove_lines([]) -> []. + +remove_lines_fun([{line,_}|Is]) -> + remove_lines_fun(Is); +remove_lines_fun([{block,Bl0}|Is]) -> + Bl = remove_lines_block(Bl0), + [{block,Bl}|remove_lines_fun(Is)]; +remove_lines_fun([I|Is]) -> + [I|remove_lines_fun(Is)]; +remove_lines_fun([]) -> []. + +remove_lines_block([{set,_,_,{line,_}}|Is]) -> + remove_lines_block(Is); +remove_lines_block([I|Is]) -> + [I|remove_lines_block(Is)]; +remove_lines_block([]) -> []. diff --git a/lib/compiler/src/beam_flatten.erl b/lib/compiler/src/beam_flatten.erl index 4045ab6dc5..c60211f516 100644 --- a/lib/compiler/src/beam_flatten.erl +++ b/lib/compiler/src/beam_flatten.erl @@ -73,7 +73,8 @@ norm({set,[D],[S|Puts],{alloc,R,{put_map,Op,F}}}) -> {put_map,F,Op,S,D,R,{list,Puts}}; norm({set,[],[],remove_message}) -> remove_message; norm({set,[],[],fclearerror}) -> fclearerror; -norm({set,[],[],fcheckerror}) -> {fcheckerror,{f,0}}. +norm({set,[],[],fcheckerror}) -> {fcheckerror,{f,0}}; +norm({set,[],[],{line,_}=Line}) -> Line. norm_allocate({_Zero,nostack,Nh,[]}, Regs) -> [{test_heap,Nh,Regs}]; diff --git a/lib/compiler/src/beam_split.erl b/lib/compiler/src/beam_split.erl index d041f18806..52dd89b5bb 100644 --- a/lib/compiler/src/beam_split.erl +++ b/lib/compiler/src/beam_split.erl @@ -50,8 +50,9 @@ split_block([{set,[R],[_,_,_]=As,{bif,is_record,{f,Lbl}}}|Is], Bl, Acc) -> split_block(Is, [], [{bif,is_record,{f,Lbl},As,R}|make_block(Bl, Acc)]); split_block([{set,[R],As,{bif,N,{f,Lbl}=Fail}}|Is], Bl, Acc) when Lbl =/= 0 -> split_block(Is, [], [{bif,N,Fail,As,R}|make_block(Bl, Acc)]); -split_block([{set,[R],As,{bif,raise,{f,_}=Fail}}|Is], Bl, Acc) -> - split_block(Is, [], [{bif,raise,Fail,As,R}|make_block(Bl, Acc)]); +split_block([{set,[],[],{line,_}=Line}, + {set,[R],As,{bif,raise,{f,_}=Fail}}|Is], Bl, Acc) -> + split_block(Is, [], [{bif,raise,Fail,As,R},Line|make_block(Bl, Acc)]); split_block([{set,[R],As,{alloc,Live,{gc_bif,N,{f,Lbl}=Fail}}}|Is], Bl, Acc) when Lbl =/= 0 -> split_block(Is, [], [{gc_bif,N,Fail,Live,As,R}|make_block(Bl, Acc)]); @@ -61,8 +62,6 @@ split_block([{set,[D],[S|Puts],{alloc,R,{put_map,Op,{f,Lbl}=Fail}}}|Is], make_block(Bl, Acc)]); split_block([{set,[R],[],{try_catch,Op,L}}|Is], Bl, Acc) -> split_block(Is, [], [{Op,R,L}|make_block(Bl, Acc)]); -split_block([{set,[],[],{line,_}=Line}|Is], Bl, Acc) -> - split_block(Is, [], [Line|make_block(Bl, Acc)]); split_block([I|Is], Bl, Acc) -> split_block(Is, [I|Bl], Acc); split_block([], Bl, Acc) -> make_block(Bl, Acc). diff --git a/lib/compiler/src/beam_type.erl b/lib/compiler/src/beam_type.erl index b83ed17b55..28f36db399 100644 --- a/lib/compiler/src/beam_type.erl +++ b/lib/compiler/src/beam_type.erl @@ -17,14 +17,15 @@ %% %% %CopyrightEnd% %% -%% Purpose : Type-based optimisations. +%% Purpose: Type-based optimisations. See the comment for verified_type/1 +%% the very end of this file for a description of the types in the +%% type database. -module(beam_type). -export([module/2]). --import(lists, [filter/2,foldl/3,keyfind/3,member/2, - reverse/1,reverse/2,sort/1]). +-import(lists, [foldl/3,member/2,reverse/1,reverse/2,sort/1]). -define(UNICODE_INT, {integer,{0,16#10FFFF}}). @@ -93,22 +94,28 @@ simplify_basic([I0|Is], Ts0, Acc) -> simplify_basic([], Ts, Acc) -> {reverse(Acc),Ts}. +%% simplify_instr(Instruction, Ts) -> [Instruction]. + +%% Simplify a simple instruction using type information. Return an +%% empty list if the instruction should be removed, or a list with +%% the original or modified instruction. + simplify_instr({set,[D],[{integer,Index},Reg],{bif,element,_}}=I, Ts) -> case max_tuple_size(Reg, Ts) of Sz when 0 < Index, Index =< Sz -> [{set,[D],[Reg],{get_tuple_element,Index-1}}]; _ -> [I] end; -simplify_instr({test,is_atom,_,[R]}=I, Ts) -> - case tdb_find(R, Ts) of - boolean -> []; - _ -> [I] - end; -simplify_instr({test,is_integer,_,[R]}=I, Ts) -> +simplify_instr({test,Test,Fail,[R]}=I, Ts) -> case tdb_find(R, Ts) of - integer -> []; - {integer,_} -> []; - _ -> [I] + any -> + [I]; + Type -> + case will_succeed(Test, Type) of + yes -> []; + no -> [{jump,Fail}]; + maybe -> [I] + end end; simplify_instr({set,[D],[TupleReg],{get_tuple_element,0}}=I, Ts) -> case tdb_find(TupleReg, Ts) of @@ -117,31 +124,17 @@ simplify_instr({set,[D],[TupleReg],{get_tuple_element,0}}=I, Ts) -> _ -> [I] end; -simplify_instr({test,is_tuple,_,[R]}=I, Ts) -> - case tdb_find(R, Ts) of - {tuple,_,_,_} -> []; - _ -> [I] - end; simplify_instr({test,test_arity,_,[R,Arity]}=I, Ts) -> case tdb_find(R, Ts) of {tuple,exact_size,Arity,_} -> []; _ -> [I] end; -simplify_instr({test,is_map,_,[R]}=I, Ts) -> - case tdb_find(R, Ts) of - map -> []; - _ -> [I] - end; -simplify_instr({test,is_nonempty_list,_,[R]}=I, Ts) -> - case tdb_find(R, Ts) of - nonempty_list -> []; - _ -> [I] - end; -simplify_instr({test,is_eq_exact,Fail,[R,{atom,_}=Atom]}=I, Ts) -> +simplify_instr({test,is_eq_exact,Fail,[R,{atom,A}=Atom]}=I, Ts) -> case tdb_find(R, Ts) of {atom,_}=Atom -> []; - {atom,_} -> [{jump,Fail}]; - _ -> [I] + boolean when is_boolean(A) -> [I]; + any -> [I]; + _ -> [{jump,Fail}] end; simplify_instr({test,is_record,_,[R,{atom,_}=Tag,{integer,Arity}]}=I, Ts) -> case tdb_find(R, Ts) of @@ -162,16 +155,6 @@ simplify_instr({test,bs_test_unit,_,[Src,Unit]}=I, Ts) -> {binary,U} when U rem Unit =:= 0 -> []; _ -> [I] end; -simplify_instr({test,is_binary,_,[Src]}=I, Ts) -> - case tdb_find(Src, Ts) of - {binary,U} when U rem 8 =:= 0 -> []; - _ -> [I] - end; -simplify_instr({test,is_bitstr,_,[Src]}=I, Ts) -> - case tdb_find(Src, Ts) of - {binary,_} -> []; - _ -> [I] - end; simplify_instr(I, _) -> [I]. simplify_select_val_int({select,select_val,R,_,L0}=I, {Min,Max}) -> @@ -200,6 +183,53 @@ eq_ranges([H], H, H) -> true; eq_ranges([H|T], H, Max) -> eq_ranges(T, H+1, Max); eq_ranges(_, _, _) -> false. +%% will_succeed(TestOperation, Type) -> yes|no|maybe. +%% Test whether TestOperation applied to an argument of type Type +%% will succeed. Return yes, no, or maybe. +%% +%% Type is a type as described in the comment for verified_type/1 at +%% the very end of this file, but it will *never* be 'any'. + +will_succeed(is_atom, Type) -> + case Type of + {atom,_} -> yes; + boolean -> yes; + _ -> no + end; +will_succeed(is_binary, Type) -> + case Type of + {binary,U} when U rem 8 =:= 0 -> yes; + {binary,_} -> maybe; + _ -> no + end; +will_succeed(is_bitstr, Type) -> + case Type of + {binary,_} -> yes; + _ -> no + end; +will_succeed(is_integer, Type) -> + case Type of + integer -> yes; + {integer,_} -> yes; + _ -> no + end; +will_succeed(is_map, Type) -> + case Type of + map -> yes; + _ -> no + end; +will_succeed(is_nonempty_list, Type) -> + case Type of + nonempty_list -> yes; + _ -> no + end; +will_succeed(is_tuple, Type) -> + case Type of + {tuple,_,_,_} -> yes; + _ -> no + end; +will_succeed(_, _) -> maybe. + %% simplify_float([Instruction], TypeDatabase) -> %% {[Instruction],TypeDatabase'} | not_possible %% Simplify floating point operations in blocks. @@ -229,7 +259,7 @@ simplify_float_1([{set,[D0],[A0],{alloc,_,{gc_bif,'-',{f,0}}}}=I|Is]=Is0, {D,Rs} = find_dest(D0, Rs1), Areg = fetch_reg(A, Rs), Acc = [{set,[D],[Areg],{bif,fnegate,{f,0}}}|clearerror(Acc1)], - Ts = tdb_update([{D0,float}], Ts0), + Ts = tdb_store(D0, float, Ts0), simplify_float_1(Is, Ts, Rs, Acc); _Other -> Ts = update(I, Ts0), @@ -252,7 +282,7 @@ simplify_float_1([{set,[D0],[A0,B0],{alloc,_,{gc_bif,Op0,{f,0}}}}=I|Is]=Is0, Areg = fetch_reg(A, Rs), Breg = fetch_reg(B, Rs), Acc = [{set,[D],[Areg,Breg],{bif,Op,{f,0}}}|clearerror(Acc2)], - Ts = tdb_update([{D0,float}], Ts0), + Ts = tdb_store(D0, float, Ts0), simplify_float_1(Is, Ts, Rs, Acc) end; simplify_float_1([{set,_,_,{try_catch,_,_}}=I|Is]=Is0, _Ts, Rs0, Acc0) -> @@ -425,104 +455,100 @@ update({'%anno',_}, Ts) -> Ts; update({set,[D],[S],move}, Ts) -> tdb_copy(S, D, Ts); -update({set,[D],[{integer,I},Reg],{bif,element,_}}, Ts0) -> - tdb_update([{Reg,{tuple,min_size,I,[]}},{D,kill}], Ts0); -update({set,[D],[_Index,Reg],{bif,element,_}}, Ts0) -> - tdb_update([{Reg,{tuple,min_size,0,[]}},{D,kill}], Ts0); -update({set,[D],Args,{bif,N,_}}, Ts0) -> +update({set,[D],[Index,Reg],{bif,element,_}}, Ts0) -> + MinSize = case Index of + {integer,I} -> I; + _ -> 0 + end, + Ts = tdb_meet(Reg, {tuple,min_size,MinSize,[]}, Ts0), + tdb_store(D, any, Ts); +update({set,[D],Args,{bif,N,_}}, Ts) -> Ar = length(Args), BoolOp = erl_internal:new_type_test(N, Ar) orelse erl_internal:comp_op(N, Ar) orelse erl_internal:bool_op(N, Ar), - case BoolOp of - true -> - tdb_update([{D,boolean}], Ts0); - false -> - tdb_update([{D,kill}], Ts0) + Type = case BoolOp of + true -> boolean; + false -> unary_op_type(N) + end, + tdb_store(D, Type, Ts); +update({set,[D],[S],{get_tuple_element,0}}, Ts0) -> + if + D =:= S -> + tdb_store(D, any, Ts0); + true -> + Ts = tdb_store(D, {tuple_element,S,0}, Ts0), + tdb_store(S, {tuple,min_size,1,[]}, Ts) end; -update({set,[D],[S],{get_tuple_element,0}}, Ts) -> - tdb_update([{D,{tuple_element,S,0}}], Ts); update({set,[D],[S],{alloc,_,{gc_bif,float,{f,0}}}}, Ts0) -> %% Make sure we reject non-numeric literal argument. case possibly_numeric(S) of - true -> tdb_update([{D,float}], Ts0); - false -> Ts0 + true -> tdb_store(D, float, Ts0); + false -> Ts0 end; update({set,[D],[S1,S2],{alloc,_,{gc_bif,'band',{f,0}}}}, Ts) -> - case keyfind(integer, 1, [S1,S2]) of - {integer,N} -> - update_band(N, D, Ts); - false -> - tdb_update([{D,integer}], Ts) - end; -update({set,[D],[S1,S2],{alloc,_,{gc_bif,'/',{f,0}}}}, Ts0) -> + Type = band_type(S1, S2, Ts), + tdb_store(D, Type, Ts); +update({set,[D],[S1,S2],{alloc,_,{gc_bif,'/',{f,0}}}}, Ts) -> %% Make sure we reject non-numeric literals. case possibly_numeric(S1) andalso possibly_numeric(S2) of - true -> tdb_update([{D,float}], Ts0); - false -> Ts0 + true -> tdb_store(D, float, Ts); + false -> Ts end; update({set,[D],[S1,S2],{alloc,_,{gc_bif,Op,{f,0}}}}, Ts0) -> case op_type(Op) of integer -> - tdb_update([{D,integer}], Ts0); - {float,_} -> - case {tdb_find(S1, Ts0),tdb_find(S2, Ts0)} of - {float,_} -> tdb_update([{D,float}], Ts0); - {_,float} -> tdb_update([{D,float}], Ts0); - {_,_} -> tdb_update([{D,kill}], Ts0) - end; - unknown -> - tdb_update([{D,kill}], Ts0) - end; -update({set,[],_Src,_Op}, Ts0) -> Ts0; -update({set,[D],_Src,_Op}, Ts0) -> - tdb_update([{D,kill}], Ts0); + tdb_store(D, integer, Ts0); + {float,_} -> + case {tdb_find(S1, Ts0),tdb_find(S2, Ts0)} of + {float,_} -> tdb_store(D, float, Ts0); + {_,float} -> tdb_store(D, float, Ts0); + {_,_} -> tdb_store(D, any, Ts0) + end; + Type -> + tdb_store(D, Type, Ts0) + end; +update({set,[D],[_],{alloc,_,{gc_bif,Op,{f,0}}}}, Ts) -> + tdb_store(D, unary_op_type(Op), Ts); +update({set,[],_Src,_Op}, Ts) -> + Ts; +update({set,[D],_Src,_Op}, Ts) -> + tdb_store(D, any, Ts); update({kill,D}, Ts) -> - tdb_update([{D,kill}], Ts); + tdb_store(D, any, Ts); %% Instructions outside of blocks. -update({test,is_float,_Fail,[Src]}, Ts0) -> - tdb_update([{Src,float}], Ts0); -update({test,test_arity,_Fail,[Src,Arity]}, Ts0) -> - tdb_update([{Src,{tuple,exact_size,Arity,[]}}], Ts0); -update({test,is_map,_Fail,[Src]}, Ts0) -> - tdb_update([{Src,map}], Ts0); +update({test,test_arity,_Fail,[Src,Arity]}, Ts) -> + tdb_meet(Src, {tuple,exact_size,Arity,[]}, Ts); update({get_map_elements,_,Src,{list,Elems0}}, Ts0) -> + Ts1 = tdb_meet(Src, map, Ts0), {_Ss,Ds} = beam_utils:split_even(Elems0), - Elems = [{Dst,kill} || Dst <- Ds], - tdb_update([{Src,map}|Elems], Ts0); -update({test,is_nonempty_list,_Fail,[Src]}, Ts0) -> - tdb_update([{Src,nonempty_list}], Ts0); -update({test,is_eq_exact,_,[Reg,{atom,_}=Atom]}, Ts) -> - case tdb_find(Reg, Ts) of - error -> - Ts; - {tuple_element,TupleReg,0} -> - tdb_update([{TupleReg,{tuple,min_size,1,[Atom]}}], Ts); - _ -> - Ts - end; + foldl(fun(Dst, A) -> tdb_store(Dst, any, A) end, Ts1, Ds); +update({test,is_eq_exact,_,[Reg,{atom,_}=Atom]}, Ts0) -> + Ts = case tdb_find_source_tuple(Reg, Ts0) of + {source_tuple,TupleReg} -> + tdb_meet(TupleReg, {tuple,min_size,1,[Atom]}, Ts0); + none -> + Ts0 + end, + tdb_meet(Reg, Atom, Ts); update({test,is_record,_Fail,[Src,Tag,{integer,Arity}]}, Ts) -> - tdb_update([{Src,{tuple,exact_size,Arity,[Tag]}}], Ts); + tdb_meet(Src, {tuple,exact_size,Arity,[Tag]}, Ts); %% Binaries and binary matching. -update({test,is_binary,_Fail,[Src]}, Ts0) -> - tdb_update([{Src,{binary,8}}], Ts0); -update({test,is_bitstr,_Fail,[Src]}, Ts0) -> - tdb_update([{Src,{binary,1}}], Ts0); update({test,bs_get_integer2,_,_,Args,Dst}, Ts) -> - tdb_update([{Dst,get_bs_integer_type(Args)}], Ts); + tdb_store(Dst, get_bs_integer_type(Args), Ts); update({test,bs_get_utf8,_,_,_,Dst}, Ts) -> - tdb_update([{Dst,?UNICODE_INT}], Ts); + tdb_store(Dst, ?UNICODE_INT, Ts); update({test,bs_get_utf16,_,_,_,Dst}, Ts) -> - tdb_update([{Dst,?UNICODE_INT}], Ts); + tdb_store(Dst, ?UNICODE_INT, Ts); update({test,bs_get_utf32,_,_,_,Dst}, Ts) -> - tdb_update([{Dst,?UNICODE_INT}], Ts); + tdb_store(Dst, ?UNICODE_INT, Ts); update({bs_init,_,{bs_init2,_,_},_,_,Dst}, Ts) -> - tdb_update([{Dst,{binary,8}}], Ts); + tdb_store(Dst, {binary,8}, Ts); update({bs_init,_,_,_,_,Dst}, Ts) -> - tdb_update([{Dst,{binary,1}}], Ts); + tdb_store(Dst, {binary,1}, Ts); update({bs_put,_,_,_}, Ts) -> Ts; update({bs_save2,_,_}, Ts) -> @@ -530,21 +556,31 @@ update({bs_save2,_,_}, Ts) -> update({bs_restore2,_,_}, Ts) -> Ts; update({bs_context_to_binary,Dst}, Ts) -> - tdb_update([{Dst,kill}], Ts); -update({test,bs_start_match2,_,_,[Src,_],Dst}, Ts) -> - Type = case tdb_find(Src, Ts) of - {binary,_}=Type0 -> Type0; - _ -> {binary,1} - end, - tdb_update([{Dst,Type}], Ts); + tdb_store(Dst, {binary,1}, Ts); +update({test,bs_start_match2,_,_,[Src,_],Dst}, Ts0) -> + Ts = tdb_meet(Src, {binary,1}, Ts0), + tdb_copy(Src, Dst, Ts); update({test,bs_get_binary2,_,_,[_,_,Unit,_],Dst}, Ts) -> true = is_integer(Unit), %Assertion. - tdb_update([{Dst,{binary,Unit}}], Ts); + tdb_store(Dst, {binary,Unit}, Ts); update({test,bs_get_float2,_,_,_,Dst}, Ts) -> - tdb_update([{Dst,float}], Ts); + tdb_store(Dst, float, Ts); update({test,bs_test_unit,_,[Src,Unit]}, Ts) -> - tdb_update([{Src,{binary,Unit}}], Ts); - + tdb_meet(Src, {binary,Unit}, Ts); + +%% Other test instructions +update({test,Test,_Fail,[Src]}, Ts) -> + Type = case Test of + is_binary -> {binary,8}; + is_bitstr -> {binary,1}; + is_boolean -> boolean; + is_float -> float; + is_integer -> integer; + is_map -> map; + is_nonempty_list -> nonempty_list; + _ -> any + end, + tdb_meet(Src, Type, Ts); update({test,_Test,_Fail,_Other}, Ts) -> Ts; @@ -552,7 +588,7 @@ update({test,_Test,_Fail,_Other}, Ts) -> update({call_ext,Ar,{extfunc,math,Math,Ar}}, Ts) -> case is_math_bif(Math, Ar) of - true -> tdb_update([{{x,0},float}], Ts); + true -> tdb_store({x,0}, float, Ts); false -> tdb_kill_xregs(Ts) end; update({call_ext,3,{extfunc,erlang,setelement,3}}, Ts0) -> @@ -569,7 +605,7 @@ update({call_ext,3,{extfunc,erlang,setelement,3}}, Ts0) -> %% first element of the tuple. {tuple,SzKind,Sz,[]} end, - tdb_update([{{x,0},T}], Ts); + tdb_store({x,0}, T, Ts); _ -> Ts end; @@ -585,20 +621,27 @@ update({'%',_}, Ts) -> Ts; %% The instruction is unknown. Kill all information. update(_I, _Ts) -> tdb_new(). -update_band(N, Reg, Ts) -> - Type = update_band_1(N, 0), - tdb_update([{Reg,Type}], Ts). +band_type({integer,Int}, Other, Ts) -> + band_type_1(Int, Other, Ts); +band_type(Other, {integer,Int}, Ts) -> + band_type_1(Int, Other, Ts); +band_type(_, _, _) -> integer. + +band_type_1(Int, OtherSrc, Ts) -> + Type = band_type_2(Int, 0), + OtherType = tdb_find(OtherSrc, Ts), + meet(Type, OtherType). -update_band_1(N, Bits) when Bits < 64 -> +band_type_2(N, Bits) when Bits < 64 -> case 1 bsl Bits of P when P =:= N + 1 -> {integer,{0,N}}; P when P > N + 1 -> integer; _ -> - update_band_1(N, Bits+1) + band_type_2(N, Bits+1) end; -update_band_1(_, _) -> +band_type_2(_, _) -> %% Negative or large positive number. Give up. integer. @@ -722,7 +765,15 @@ op_type('bxor') -> integer; op_type('bsl') -> integer; op_type('bsr') -> integer; op_type('div') -> integer; -op_type(_) -> unknown. +op_type(_) -> any. + +unary_op_type(bit_size) -> integer; +unary_op_type(byte_size) -> integer; +unary_op_type(length) -> integer; +unary_op_type(map_size) -> integer; +unary_op_type(size) -> integer; +unary_op_type(tuple_size) -> integer; +unary_op_type(_) -> any. flush(Rs, [{set,[_],[_,_,_],{bif,is_record,_}}|_]=Is0, Acc0) -> Acc = flush_all(Rs, Is0, Acc0), @@ -805,41 +856,39 @@ checkerror_1([], OrigIs) -> OrigIs. checkerror_2(OrigIs) -> [{set,[],[],fcheckerror}|OrigIs]. -%%% Routines for maintaining a type database. The type database +%%% Routines for maintaining a type database. The type database %%% associates type information with registers. %%% -%%% {tuple,min_size,Size,First} means that the corresponding register contains -%%% a tuple with *at least* Size elements (conversely, exact_size means that it -%%% contains a tuple with *exactly* Size elements). An tuple with unknown size -%%% is represented as {tuple,min_size,0,[]}. First is either [] (meaning that -%%% the tuple's first element is unknown) or [FirstElement] (the contents of -%%% the first element). -%%% -%%% 'float' means that the register contains a float. -%%% -%%% 'integer' or {integer,{Min,Max}} that the register contains an -%%% integer. -%%% -%%% {binary,Unit} means that the register contains a binary/bitstring aligned -%%% to unit Unit. +%%% See the comment for verified_type/1 at the end of module for +%%% a description of the possible types. %% tdb_new() -> EmptyDataBase %% Creates a new, empty type database. tdb_new() -> []. -%% tdb_find(Register, Db) -> Information|error +%% tdb_find(Register, Db) -> Type %% Returns type information or the atom error if there is no type %% information available for Register. +%% +%% See the comment for verified_type/1 at the end of module for +%% a description of the possible types. -tdb_find({x,_}=K, Ts) -> tdb_find_1(K, Ts); -tdb_find({y,_}=K, Ts) -> tdb_find_1(K, Ts); -tdb_find(_, _) -> error. +tdb_find(Reg, Ts) -> + case tdb_find_raw(Reg, Ts) of + {tuple_element,_,_} -> any; + Type -> Type + end. -tdb_find_1(K, Ts) -> - case orddict:find(K, Ts) of - {ok,Val} -> Val; - error -> error +%% tdb_find_source_tuple(Register, Ts) -> {source_tuple,Register} | 'none'. +%% Find the tuple whose first element was fetched to the register Register. + +tdb_find_source_tuple(Reg, Ts) -> + case tdb_find_raw(Reg, Ts) of + {tuple_element,Src,0} -> + {source_tuple,Src}; + _ -> + none end. %% tdb_copy(Source, Dest, Db) -> Db' @@ -847,9 +896,9 @@ tdb_find_1(K, Ts) -> %% as the Source. tdb_copy({Tag,_}=S, D, Ts) when Tag =:= x; Tag =:= y -> - case tdb_find(S, Ts) of - error -> orddict:erase(D, Ts); - Type -> orddict:store(D, Type, Ts) + case tdb_find_raw(S, Ts) of + any -> orddict:erase(D, Ts); + Type -> orddict:store(D, Type, Ts) end; tdb_copy(Literal, D, Ts) -> Type = case Literal of @@ -861,14 +910,89 @@ tdb_copy(Literal, D, Ts) -> {literal,Tuple} when tuple_size(Tuple) >= 1 -> Lit = tag_literal(element(1, Tuple)), {tuple,exact_size,tuple_size(Tuple),[Lit]}; - _ -> term + _ -> any end, - if - Type =:= term -> - orddict:erase(D, Ts); - true -> - verify_type(Type), - orddict:store(D, Type, Ts) + tdb_store(D, verified_type(Type), Ts). + +%% tdb_store(Register, Type, Ts0) -> Ts. +%% Store a new type for register Register. Return the update type +%% database. Use this function when a new value is assigned to +%% a register. +%% +%% See the comment for verified_type/1 at the end of module for +%% a description of the possible types. + +tdb_store(Reg, any, Ts) -> + erase(Reg, Ts); +tdb_store(Reg, Type, Ts) -> + store(Reg, verified_type(Type), Ts). + +store(Key, New, [{K,_}|_]=Dict) when Key < K -> + [{Key,New}|Dict]; +store(Key, New, [{K,Val}=E|Dict]) when Key > K -> + case Val of + {tuple_element,Key,_} -> store(Key, New, Dict); + _ -> [E|store(Key, New, Dict)] + end; +store(Key, New, [{_K,Old}|Dict]) -> %Key == K + case Old of + {tuple,_,_,_} -> + [{Key,New}|erase_tuple_element(Key, Dict)]; + _ -> + [{Key,New}|Dict] + end; +store(Key, New, []) -> [{Key,New}]. + +erase(Key, [{K,_}=E|Dict]) when Key < K -> + [E|Dict]; +erase(Key, [{K,Val}=E|Dict]) when Key > K -> + case Val of + {tuple_element,Key,_} -> erase(Key, Dict); + _ -> [E|erase(Key, Dict)] + end; +erase(Key, [{_K,Val}|Dict]) -> %Key == K + case Val of + {tuple,_,_,_} -> erase_tuple_element(Key, Dict); + _ -> Dict + end; +erase(_, []) -> []. + +erase_tuple_element(Key, [{_,{tuple_element,Key,_}}|Dict]) -> + erase_tuple_element(Key, Dict); +erase_tuple_element(Key, [E|Dict]) -> + [E|erase_tuple_element(Key, Dict)]; +erase_tuple_element(_Key, []) -> []. + +%% tdb_meet(Register, Type, Ts0) -> Ts. +%% Update information of a register that is used as the source for an +%% instruction. The type Type will be combined using the meet operation +%% with the previous type information for the register, resulting in +%% narrower (more specific) type. +%% +%% For example, if the previous type is {tuple,min_size,2,[]} and the +%% the new type is {tuple,exact_size,5,[]}, the meet of the types will +%% be {tuple,exact_size,5,[]}. +%% +%% See the comment for verified_type/1 at the end of module for +%% a description of the possible types. + +tdb_meet(Reg, NewType, Ts) -> + Update = fun(Type0) -> meet(Type0, NewType) end, + orddict:update(Reg, Update, NewType, Ts). + +%%% +%%% Here follows internal helper functions for accessing and +%%% updating the type database. +%%% + +tdb_find_raw({x,_}=K, Ts) -> tdb_find_raw_1(K, Ts); +tdb_find_raw({y,_}=K, Ts) -> tdb_find_raw_1(K, Ts); +tdb_find_raw(_, _) -> any. + +tdb_find_raw_1(K, Ts) -> + case orddict:find(K, Ts) of + {ok,Val} -> Val; + error -> any end. tag_literal(A) when is_atom(A) -> {atom,A}; @@ -877,45 +1001,6 @@ tag_literal(I) when is_integer(I) -> {integer,I}; tag_literal([]) -> nil; tag_literal(Lit) -> {literal,Lit}. -%% tdb_update([UpdateOp], Db) -> NewDb -%% UpdateOp = {Register,kill}|{Register,NewInfo} -%% Updates a type database. If a 'kill' operation is given, the type -%% information for that register will be removed from the database. -%% A kill operation takes precedence over other operations for the same -%% register (i.e. [{{x,0},kill},{{x,0},{tuple,min_size,5,[]}}] means that the -%% the existing type information, if any, will be discarded, and the -%% the '{tuple,min_size,5,[]}' information ignored. -%% -%% If NewInfo information is given and there exists information about -%% the register, the old and new type information will be merged. -%% For instance, {tuple,min_size,5,_} and {tuple,min_size,10,_} will be merged -%% to produce {tuple,min_size,10,_}. - -tdb_update(Uis0, Ts0) -> - Uis1 = filter(fun ({{x,_},_Op}) -> true; - ({{y,_},_Op}) -> true; - (_) -> false - end, Uis0), - tdb_update1(lists:sort(Uis1), Ts0). - -tdb_update1([{Key,kill}|Ops], [{K,_Old}|_]=Db) when Key < K -> - tdb_update1(remove_key(Key, Ops), Db); -tdb_update1([{Key,Type}=New|Ops], [{K,_Old}|_]=Db) when Key < K -> - verify_type(Type), - [New|tdb_update1(Ops, Db)]; -tdb_update1([{Key,kill}|Ops], [{Key,_}|Db]) -> - tdb_update1(remove_key(Key, Ops), Db); -tdb_update1([{Key,NewInfo}|Ops], [{Key,OldInfo}|Db]) -> - [{Key,merge_type_info(NewInfo, OldInfo)}|tdb_update1(Ops, Db)]; -tdb_update1([{_,_}|_]=Ops, [Old|Db]) -> - [Old|tdb_update1(Ops, Db)]; -tdb_update1([{Key,kill}|Ops], []) -> - tdb_update1(remove_key(Key, Ops), []); -tdb_update1([{_,Type}=New|Ops], []) -> - verify_type(Type), - [New|tdb_update1(Ops, [])]; -tdb_update1([], Db) -> Db. - %% tdb_kill_xregs(Db) -> NewDb %% Kill all information about x registers. Also kill all tuple_element %% dependencies from y registers to x registers. @@ -924,44 +1009,106 @@ tdb_kill_xregs([{{x,_},_Type}|Db]) -> tdb_kill_xregs(Db); tdb_kill_xregs([{{y,_},{tuple_element,{x,_},_}}|Db]) -> tdb_kill_xregs(Db); tdb_kill_xregs([Any|Db]) -> [Any|tdb_kill_xregs(Db)]; tdb_kill_xregs([]) -> []. - -remove_key(Key, [{Key,_Op}|Ops]) -> remove_key(Key, Ops); -remove_key(_, Ops) -> Ops. -merge_type_info(I, I) -> I; -merge_type_info({tuple,min_size,Sz1,Same}, {tuple,min_size,Sz2,Same}=Max) when Sz1 < Sz2 -> +%% meet(Type1, Type2) -> Type +%% Returns the "meet" of Type1 and Type2. The meet is a narrower +%% type than Type1 and Type2. For example: +%% +%% meet(integer, {integer,{0,3}}) -> {integer,{0,3}} +%% +%% The meet for two different types result in 'none', which is +%% the bottom element for our type lattice: +%% +%% meet(integer, map) -> none + +meet(T, T) -> + T; +meet({integer,_}=T, integer) -> + T; +meet(integer, {integer,_}=T) -> + T; +meet({integer,{Min1,Max1}}, {integer,{Min2,Max2}}) -> + {integer,{max(Min1, Min2),min(Max1, Max2)}}; +meet({tuple,min_size,Sz1,Same}, {tuple,min_size,Sz2,Same}=Max) when Sz1 < Sz2 -> Max; -merge_type_info({tuple,min_size,Sz1,Same}=Max, {tuple,min_size,Sz2,Same}) when Sz1 > Sz2 -> +meet({tuple,min_size,Sz1,Same}=Max, {tuple,min_size,Sz2,Same}) when Sz1 > Sz2 -> Max; -merge_type_info({tuple,exact_size,_,Same}=Exact, {tuple,_,_,Same}) -> +meet({tuple,exact_size,_,Same}=Exact, {tuple,_,_,Same}) -> Exact; -merge_type_info({tuple,_,_,Same},{tuple,exact_size,_,Same}=Exact) -> +meet({tuple,_,_,Same},{tuple,exact_size,_,Same}=Exact) -> Exact; -merge_type_info({tuple,SzKind1,Sz1,[]}, {tuple,_SzKind2,_Sz2,First}=Tuple2) -> - merge_type_info({tuple,SzKind1,Sz1,First}, Tuple2); -merge_type_info({tuple,_SzKind1,_Sz1,First}=Tuple1, {tuple,SzKind2,Sz2,_}) -> - merge_type_info(Tuple1, {tuple,SzKind2,Sz2,First}); -merge_type_info(integer, {integer,_}) -> - integer; -merge_type_info({integer,_}, integer) -> - integer; -merge_type_info({integer,{Min1,Max1}}, {integer,{Min2,Max2}}) -> - {integer,{max(Min1, Min2),min(Max1, Max2)}}; -merge_type_info({binary,U1}, {binary,U2}) -> +meet({tuple,SzKind1,Sz1,[]}, {tuple,_SzKind2,_Sz2,First}=Tuple2) -> + meet({tuple,SzKind1,Sz1,First}, Tuple2); +meet({tuple,_SzKind1,_Sz1,First}=Tuple1, {tuple,SzKind2,Sz2,_}) -> + meet(Tuple1, {tuple,SzKind2,Sz2,First}); +meet({binary,U1}, {binary,U2}) -> {binary,max(U1, U2)}; -merge_type_info(NewType, _) -> - verify_type(NewType), - NewType. - -verify_type({atom,_}) -> ok; -verify_type({binary,U}) when is_integer(U) -> ok; -verify_type(boolean) -> ok; -verify_type(integer) -> ok; -verify_type({integer,{Min,Max}}) - when is_integer(Min), is_integer(Max) -> ok; -verify_type(map) -> ok; -verify_type(nonempty_list) -> ok; -verify_type({tuple,_,Sz,[]}) when is_integer(Sz) -> ok; -verify_type({tuple,_,Sz,[_]}) when is_integer(Sz) -> ok; -verify_type({tuple_element,_,_}) -> ok; -verify_type(float) -> ok. +meet(T1, T2) -> + case is_any(T1) of + true -> + verified_type(T2); + false -> + case is_any(T2) of + true -> + verified_type(T1); + false -> + none %The bottom element. + end + end. + +is_any(any) -> true; +is_any({tuple_element,_,_}) -> true; +is_any(_) -> false. + +%% verified_type(Type) -> Type +%% Returns the passed in type if it is one of the defined types. +%% Crashes if there is anything wrong with the type. +%% +%% Here are all possible types: +%% +%% any Any Erlang term (top element for the type lattice). +%% +%% {atom,Atom} The specific atom Atom. +%% {binary,Unit} Binary/bitstring aligned to unit Unit. +%% boolean 'true' | 'false' +%% float Floating point number. +%% integer Integer. +%% {integer,{Min,Max}} Integer in the inclusive range Min through Max. +%% map Map. +%% nonempty_list Nonempty list. +%% {tuple,_,_,_} Tuple (see below). +%% +%% none No type (bottom element for the type lattice). +%% +%% {tuple,min_size,Size,First} means that the corresponding register +%% contains a tuple with *at least* Size elements (conversely, +%% {tuple,exact_size,Size,First} means that it contains a tuple with +%% *exactly* Size elements). An tuple with unknown size is +%% represented as {tuple,min_size,0,[]}. First is either [] (meaning +%% that the tuple's first element is unknown) or [FirstElement] (the +%% contents of the first element). +%% +%% There is also a pseudo-type called {tuple_element,_,_}: +%% +%% {tuple_element,SrcTuple,ElementNumber} +%% +%% that does not provide any information about the type of the +%% register itself, but provides a link back to the source tuple that +%% the register got its value from. +%% +%% Note that {tuple_element,_,_} will *never* be returned by tdb_find/2. +%% Use tdb_find_source_tuple/2 to locate the source tuple for a register. + +verified_type(any=T) -> T; +verified_type({atom,_}=T) -> T; +verified_type({binary,U}=T) when is_integer(U) -> T; +verified_type(boolean=T) -> T; +verified_type(integer=T) -> T; +verified_type({integer,{Min,Max}}=T) + when is_integer(Min), is_integer(Max) -> T; +verified_type(map=T) -> T; +verified_type(nonempty_list=T) -> T; +verified_type({tuple,_,Sz,[]}=T) when is_integer(Sz) -> T; +verified_type({tuple,_,Sz,[_]}=T) when is_integer(Sz) -> T; +verified_type({tuple_element,_,_}=T) -> T; +verified_type(float=T) -> T. diff --git a/lib/compiler/src/beam_utils.erl b/lib/compiler/src/beam_utils.erl index 4dcce30583..814cfb8265 100644 --- a/lib/compiler/src/beam_utils.erl +++ b/lib/compiler/src/beam_utils.erl @@ -118,7 +118,7 @@ is_killed(R, Is, D) -> St = #live{lbl=D,res=gb_trees:empty()}, case check_liveness(R, Is, St) of {killed,_} -> true; - {exit_not_used,_} -> true; + {exit_not_used,_} -> false; {_,_} -> false end. @@ -131,7 +131,7 @@ is_killed_at(R, Lbl, D) when is_integer(Lbl) -> St0 = #live{lbl=D,res=gb_trees:empty()}, case check_liveness_at(R, Lbl, St0) of {killed,_} -> true; - {exit_not_used,_} -> true; + {exit_not_used,_} -> false; {_,_} -> false end. @@ -148,7 +148,7 @@ is_not_used(R, Is, D) -> St = #live{lbl=D,res=gb_trees:empty()}, case check_liveness(R, Is, St) of {used,_} -> false; - {exit_not_used,_} -> false; + {exit_not_used,_} -> true; {_,_} -> true end. @@ -440,8 +440,11 @@ check_liveness(R, [{bs_init,_,_,Live,Ss,Dst}|Is], St) -> case member(R, Ss) of true -> {used,St}; false -> + %% If the exception is taken, the stack may + %% be scanned. Therefore the register is not + %% guaranteed to be killed. if - R =:= Dst -> {killed,St}; + R =:= Dst -> {not_used,St}; true -> not_used(check_liveness(R, Is, St)) end end @@ -735,8 +738,8 @@ check_liveness_block_1(R, Ss, Ds, Op, Is, St0) -> end end. -check_liveness_block_2(R, {gc_bif,_Op,{f,Lbl}}, _Ss, St) -> - check_liveness_block_3(R, Lbl, St); +check_liveness_block_2(R, {gc_bif,Op,{f,Lbl}}, Ss, St) -> + check_liveness_block_3(R, Lbl, {Op,length(Ss)}, St); check_liveness_block_2(R, {bif,Op,{f,Lbl}}, Ss, St) -> Arity = length(Ss), case erl_internal:comp_op(Op, Arity) orelse @@ -744,16 +747,23 @@ check_liveness_block_2(R, {bif,Op,{f,Lbl}}, Ss, St) -> true -> {killed,St}; false -> - check_liveness_block_3(R, Lbl, St) + check_liveness_block_3(R, Lbl, {Op,length(Ss)}, St) end; check_liveness_block_2(R, {put_map,_Op,{f,Lbl}}, _Ss, St) -> - check_liveness_block_3(R, Lbl, St); + check_liveness_block_3(R, Lbl, {unsafe,0}, St); check_liveness_block_2(_, _, _, St) -> {killed,St}. -check_liveness_block_3(_, 0, St) -> +check_liveness_block_3({x,_}, 0, _FA, St) -> {killed,St}; -check_liveness_block_3(R, Lbl, St0) -> +check_liveness_block_3({y,_}, 0, {F,A}, St) -> + %% If the exception is thrown, the stack may be scanned, + %% thus implicitly using the y register. + case erl_bifs:is_safe(erlang, F, A) of + true -> {killed,St}; + false -> {used,St} + end; +check_liveness_block_3(R, Lbl, _FA, St0) -> check_liveness_at(R, Lbl, St0). index_labels_1([{label,Lbl}|Is0], Acc) -> @@ -994,47 +1004,52 @@ live_opt([{recv_mark,_}=I|Is], Regs, D, Acc) -> live_opt([], _, _, Acc) -> Acc. -live_opt_block([{set,Ds,Ss,Op0}|Is], Regs0, D, Acc) -> - Regs1 = x_live(Ss, x_dead(Ds, Regs0)), - {Op, Regs} = live_opt_block_op(Op0, Regs1, D), - I = {set, Ds, Ss, Op}, - - case Ds of - [{x,X}] -> - case (not is_live(X, Regs0)) andalso Op =:= move of - true -> - live_opt_block(Is, Regs0, D, Acc); - false -> - live_opt_block(Is, Regs, D, [I|Acc]) - end; - _ -> - live_opt_block(Is, Regs, D, [I|Acc]) +live_opt_block([{set,[{x,X}]=Ds,Ss,move}=I|Is], Regs0, D, Acc) -> + Regs = x_live(Ss, x_dead(Ds, Regs0)), + case is_live(X, Regs0) of + true -> + live_opt_block(Is, Regs, D, [I|Acc]); + false -> + %% Useless move, will never be used. + live_opt_block(Is, Regs, D, Acc) end; -live_opt_block([{'%anno',_}|Is], Regs, D, Acc) -> - live_opt_block(Is, Regs, D, Acc); -live_opt_block([], Regs, _, Acc) -> {Acc,Regs}. - -live_opt_block_op({alloc,Live0,AllocOp}, Regs0, D) -> - Regs = - case AllocOp of - {Kind, _N, Fail} when Kind =:= gc_bif; Kind =:= put_map -> - live_join_label(Fail, D, Regs0); - _ -> - Regs0 - end, +live_opt_block([{set,Ds,Ss,{alloc,Live0,AllocOp}}|Is], Regs0, D, Acc) -> + %% Calculate liveness from the point of view of the GC. + %% There will never be a GC if the instruction fails, so we should + %% ignore the failure branch. + GcRegs1 = x_dead(Ds, Regs0), + GcRegs = x_live(Ss, GcRegs1), + Live = live_regs(GcRegs), %% The life-time analysis used by the code generator is sometimes too %% conservative, so it may be possible to lower the number of live %% registers based on the exact liveness information. The main benefit is %% that more optimizations that depend on liveness information (such as the - %% beam_bool and beam_dead passes) may be applied. - Live = live_regs(Regs), - true = Live =< Live0, - {{alloc,Live,AllocOp}, live_call(Live)}; -live_opt_block_op({bif,_N,Fail} = Op, Regs, D) -> - {Op, live_join_label(Fail, D, Regs)}; -live_opt_block_op(Op, Regs, _D) -> - {Op, Regs}. + %% beam_dead pass) may be applied. + true = Live =< Live0, %Assertion. + I = {set,Ds,Ss,{alloc,Live,AllocOp}}, + + %% Calculate liveness from the point of view of the preceding instruction. + %% The liveness is the union of live registers in the GC and the live + %% registers at the failure label. + Regs1 = live_call(Live), + Regs = live_join_alloc(AllocOp, D, Regs1), + live_opt_block(Is, Regs, D, [I|Acc]); +live_opt_block([{set,Ds,Ss,{bif,_,Fail}}=I|Is], Regs0, D, Acc) -> + Regs1 = x_dead(Ds, Regs0), + Regs2 = x_live(Ss, Regs1), + Regs = live_join_label(Fail, D, Regs2), + live_opt_block(Is, Regs, D, [I|Acc]); +live_opt_block([{set,Ds,Ss,_}=I|Is], Regs0, D, Acc) -> + Regs = x_live(Ss, x_dead(Ds, Regs0)), + live_opt_block(Is, Regs, D, [I|Acc]); +live_opt_block([{'%anno',_}|Is], Regs, D, Acc) -> + live_opt_block(Is, Regs, D, Acc); +live_opt_block([], Regs, _, Acc) -> {Acc,Regs}. + +live_join_alloc({Kind,_Name,Fail}, D, Regs) when Kind =:= gc_bif; Kind =:= put_map -> + live_join_label(Fail, D, Regs); +live_join_alloc(_, _, Regs) -> Regs. live_join_labels([{f,L}|T], D, Regs0) when L =/= 0 -> Regs = gb_trees:get(L, D) bor Regs0, diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index 7e5d86c177..c30ab34ac7 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -1153,6 +1153,7 @@ set_type_y(Type, {y,Y}=Reg, #vst{current=#st{y=Ys0}=St}=Vst) {value,_} -> gb_trees:update(Y, Type, Ys0) end, + check_try_catch_tags(Type, Y, Ys0), Vst#vst{current=St#st{y=Ys}}; set_type_y(Type, Reg, #vst{}) -> error({invalid_store,Reg,Type}). @@ -1160,6 +1161,29 @@ set_catch_end({y,Y}, #vst{current=#st{y=Ys0}=St}=Vst) -> Ys = gb_trees:update(Y, initialized, Ys0), Vst#vst{current=St#st{y=Ys}}. +check_try_catch_tags(Type, LastY, Ys) -> + case is_try_catch_tag(Type) of + false -> + ok; + true -> + %% Every catch or try/catch must use a lower Y register + %% number than any enclosing catch or try/catch. That will + %% ensure that when the stack is scanned when an + %% exception occurs, the innermost try/catch tag is found + %% first. + Bad = [{{y,Y},Tag} || {Y,Tag} <- gb_trees:to_list(Ys), + Y < LastY, is_try_catch_tag(Tag)], + case Bad of + [] -> + ok; + [_|_] -> + error({bad_try_catch_nesting,{y,LastY},Bad}) + end + end. + +is_try_catch_tag({catchtag,_}) -> true; +is_try_catch_tag({trytag,_}) -> true; +is_try_catch_tag(_) -> false. is_reg_defined({x,_}=Reg, Vst) -> is_type_defined_x(Reg, Vst); is_reg_defined({y,_}=Reg, Vst) -> is_type_defined_y(Reg, Vst); @@ -1349,7 +1373,12 @@ branch_arities([Sz,{f,L}|T], Tuple, #vst{current=St}=Vst0) Vst = branch_state(L, Vst1), branch_arities(T, Tuple, Vst#vst{current=St}). -branch_state(0, #vst{}=Vst) -> Vst; +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. + 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 diff --git a/lib/compiler/test/beam_type_SUITE.erl b/lib/compiler/test/beam_type_SUITE.erl index e33df809ff..541075af2a 100644 --- a/lib/compiler/test/beam_type_SUITE.erl +++ b/lib/compiler/test/beam_type_SUITE.erl @@ -122,7 +122,7 @@ do_integers_5(X0, Y0) -> 3 -> three end. -coverage(_Config) -> +coverage(Config) -> {'EXIT',{badarith,_}} = (catch id(1) bsl 0.5), {'EXIT',{badarith,_}} = (catch id(2.0) bsl 2), {'EXIT',{badarith,_}} = (catch a + 0.5), @@ -133,6 +133,29 @@ coverage(_Config) -> id(id(42) band 387439739874298734983787934283479243879), id(-1 band id(13)), + error = if + is_map(Config), is_integer(Config) -> ok; + true -> error + end, + error = if + is_map(Config), is_atom(Config) -> ok; + true -> error + end, + error = if + is_map(Config), is_tuple(Config) -> ok; + true -> error + end, + error = if + is_integer(Config), is_bitstring(Config) -> ok; + true -> error + end, + + ok = case Config of + <<_>> when is_binary(Config) -> + impossible; + [_|_] -> + ok + end, ok. booleans(_Config) -> diff --git a/lib/compiler/test/beam_validator_SUITE.erl b/lib/compiler/test/beam_validator_SUITE.erl index 63a13281a8..b8fff7b100 100644 --- a/lib/compiler/test/beam_validator_SUITE.erl +++ b/lib/compiler/test/beam_validator_SUITE.erl @@ -33,7 +33,7 @@ state_after_fault_in_catch/1,no_exception_in_catch/1, 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]). + val_dsetel/1,bad_tuples/1,bad_try_catch_nesting/1]). -include_lib("common_test/include/ct.hrl"). @@ -62,7 +62,7 @@ groups() -> state_after_fault_in_catch,no_exception_in_catch, undef_label,illegal_instruction,failing_gc_guard_bif, map_field_lists,cover_bin_opt,val_dsetel, - bad_tuples]}]. + bad_tuples,bad_try_catch_nesting]}]. init_per_suite(Config) -> Config. @@ -523,6 +523,14 @@ bad_tuples(Config) -> ok. +bad_try_catch_nesting(Config) -> + Errors = do_val(bad_try_catch_nesting, Config), + [{{bad_try_catch_nesting,main,2}, + {{'try',{y,2},{f,3}}, + 7, + {bad_try_catch_nesting,{y,2},[{{y,1},{trytag,[5]}}]}}}] = Errors, + ok. + %%%------------------------------------------------------------------------- transform_remove(Remove, Module) -> diff --git a/lib/compiler/test/beam_validator_SUITE_data/bad_try_catch_nesting.S b/lib/compiler/test/beam_validator_SUITE_data/bad_try_catch_nesting.S new file mode 100644 index 0000000000..9f1b21a17b --- /dev/null +++ b/lib/compiler/test/beam_validator_SUITE_data/bad_try_catch_nesting.S @@ -0,0 +1,64 @@ +{module, bad_try_catch_nesting}. %% version = 0 + +{exports, [{main,2},{module_info,0},{module_info,1}]}. + +{attributes, []}. + +{labels, 11}. + + +{function, main, 2, 2}. + {label,1}. + {line,[{location,"bad_try_catch_nesting.erl",4}]}. + {func_info,{atom,bad_try_catch_nesting},{atom,main},2}. + {label,2}. + {allocate_zero,3,2}. + {'try',{y,1},{f,5}}. + {move,{x,1},{y,0}}. + {'try',{y,2},{f,3}}. + {line,[{location,"bad_try_catch_nesting.erl",7}]}. + {call_fun,0}. + {try_end,{y,2}}. + {jump,{f,4}}. + {label,3}. + {try_case,{y,2}}. + {test,is_ne_exact,{f,4},[{x,0},{atom,error}]}. + {line,[]}. + {bif,raise,{f,0},[{x,2},{x,1}],{x,0}}. + {label,4}. + {move,{y,0},{x,0}}. + {kill,{y,0}}. + {line,[{location,"bad_try_catch_nesting.erl",12}]}. + {call_fun,0}. + {try_end,{y,1}}. + {deallocate,3}. + return. + {label,5}. + {try_case,{y,1}}. + {test,is_eq_exact,{f,6},[{x,0},{atom,throw}]}. + {deallocate,3}. + return. + {label,6}. + {line,[]}. + {bif,raise,{f,0},[{x,2},{x,1}],{x,0}}. + + +{function, module_info, 0, 8}. + {label,7}. + {line,[]}. + {func_info,{atom,bad_try_catch_nesting},{atom,module_info},0}. + {label,8}. + {move,{atom,bad_try_catch_nesting},{x,0}}. + {line,[]}. + {call_ext_only,1,{extfunc,erlang,get_module_info,1}}. + + +{function, module_info, 1, 10}. + {label,9}. + {line,[]}. + {func_info,{atom,bad_try_catch_nesting},{atom,module_info},1}. + {label,10}. + {move,{x,0},{x,1}}. + {move,{atom,bad_try_catch_nesting},{x,0}}. + {line,[]}. + {call_ext_only,2,{extfunc,erlang,get_module_info,2}}. |