From c0c5943c3a2646a3383d974c2a1afcff8c5d16d3 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Wed, 23 Sep 2015 07:23:15 +0200 Subject: beam_type: Improve optimization by keeping track of integers The ASN.1 compiler often generates code similar to: f(<<0:1,...>>) -> ...; f(<<1:1,...>>) -> .... Internally that will be rewritten to (conceptually): f(<>) -> case B of 0 -> case Tail of ... end; 1 -> case Tail of ... end; _ -> error(case_clause) end. Since B comes from a bit field of one bit, we know that the only possible values are 0 and 1. Therefore the error clause can be eliminated like this: f(<>) -> case B of 0 -> case Tail of ... end; _ -> case Tail of ... end end. Similarly, we can also a deduce the range for an integer from a 'band' operation with a literal integer. While we are at it, also add a test case to improve the coverage. --- lib/compiler/src/beam_type.erl | 121 +++++++++++++++++++++++++++++++++++++---- 1 file changed, 110 insertions(+), 11 deletions(-) (limited to 'lib/compiler/src/beam_type.erl') diff --git a/lib/compiler/src/beam_type.erl b/lib/compiler/src/beam_type.erl index bb91bbcc0a..17ce7082f6 100644 --- a/lib/compiler/src/beam_type.erl +++ b/lib/compiler/src/beam_type.erl @@ -23,7 +23,8 @@ -export([module/2]). --import(lists, [foldl/3,reverse/1,filter/2]). +-import(lists, [filter/2,foldl/3,keyfind/3,member/2, + reverse/1,reverse/2,sort/1]). module({Mod,Exp,Attr,Fs0,Lc}, _Opts) -> Fs = [function(F) || F <- Fs0], @@ -94,6 +95,12 @@ simplify_basic_1([{set,[D],[TupleReg],{get_tuple_element,0}}=I|Is0], Ts0, Acc) - end; simplify_basic_1([{set,_,_,{try_catch,_,_}}=I|Is], _Ts, Acc) -> simplify_basic_1(Is, tdb_new(), [I|Acc]); +simplify_basic_1([{test,is_integer,_,[R]}=I|Is], Ts, Acc) -> + case tdb_find(R, Ts) of + integer -> simplify_basic_1(Is, Ts, Acc); + {integer,_} -> simplify_basic_1(Is, Ts, Acc); + _ -> simplify_basic_1(Is, Ts, [I|Acc]) + end; simplify_basic_1([{test,is_tuple,_,[R]}=I|Is], Ts, Acc) -> case tdb_find(R, Ts) of {tuple,_,_} -> simplify_basic_1(Is, Ts, Acc); @@ -137,6 +144,14 @@ simplify_basic_1([{test,is_record,_,[R,{atom,_}=Tag,{integer,Arity}]}=I|Is], Ts0 Ts = update(I, Ts0), simplify_basic_1(Is, Ts, [I|Acc]) end; +simplify_basic_1([{select,select_val,Reg,_,_}=I0|Is], Ts, Acc) -> + I = case tdb_find(Reg, Ts) of + {integer,Range} -> + simplify_select_val_int(I0, Range); + _ -> + I0 + end, + simplify_basic_1(Is, tdb_new(), [I|Acc]); simplify_basic_1([I|Is], Ts0, Acc) -> Ts = update(I, Ts0), simplify_basic_1(Is, Ts, [I|Acc]); @@ -144,6 +159,23 @@ simplify_basic_1([], Ts, Acc) -> Is = reverse(Acc), {Is,Ts}. +simplify_select_val_int({select,select_val,R,_,L0}=I, {Min,Max}) -> + Vs = sort([V || {integer,V} <- L0]), + case eq_ranges(Vs, Min, Max) of + false -> I; + true -> simplify_select_val_1(L0, {integer,Max}, R, []) + end. + +simplify_select_val_1([Val,F|T], Val, R, Acc) -> + L = reverse(Acc, T), + {select,select_val,R,F,L}; +simplify_select_val_1([V,F|T], Val, R, Acc) -> + simplify_select_val_1(T, Val, R, [F,V|Acc]). + +eq_ranges([H], H, H) -> true; +eq_ranges([H|T], H, Max) -> eq_ranges(T, H+1, Max); +eq_ranges(_, _, _) -> false. + %% simplify_float([Instruction], TypeDatabase) -> %% {[Instruction],TypeDatabase'} | not_possible %% Simplify floating point operations in blocks. @@ -390,6 +422,13 @@ update({set,[D],[S],{alloc,_,{gc_bif,float,{f,0}}}}, Ts0) -> true -> tdb_update([{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) -> %% Make sure we reject non-numeric literals. case possibly_numeric(S1) andalso possibly_numeric(S2) of @@ -397,15 +436,17 @@ update({set,[D],[S1,S2],{alloc,_,{gc_bif,'/',{f,0}}}}, Ts0) -> false -> Ts0 end; update({set,[D],[S1,S2],{alloc,_,{gc_bif,Op,{f,0}}}}, Ts0) -> - case arith_op(Op) of - no -> - tdb_update([{D,kill}], Ts0); - {yes,_} -> + 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 + end; + unknown -> + tdb_update([{D,kill}], Ts0) end; update({set,[],_Src,_Op}, Ts0) -> Ts0; update({set,[D],_Src,_Op}, Ts0) -> @@ -437,6 +478,8 @@ update({test,is_record,_Fail,[Src,Tag,{integer,Arity}]}, Ts) -> tdb_update([{Src,{tuple,Arity,[Tag]}}], Ts); update({test,_Test,_Fail,_Other}, Ts) -> Ts; +update({test,bs_get_integer2,_,_,Args,Dst}, Ts) -> + tdb_update([{Dst,get_bs_integer_type(Args)}], Ts); update({call_ext,Ar,{extfunc,math,Math,Ar}}, Ts) -> case is_math_bif(Math, Ar) of true -> tdb_update([{{x,0},float}], Ts); @@ -453,10 +496,43 @@ update({call,_Arity,_Func}, Ts) -> tdb_kill_xregs(Ts); update({call_ext,_Arity,_Func}, Ts) -> tdb_kill_xregs(Ts); update({make_fun2,_,_,_,_}, Ts) -> tdb_kill_xregs(Ts); update({line,_}, Ts) -> Ts; +update({bs_save2,_,_}, Ts) -> Ts; +update({bs_restore2,_,_}, 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). + +update_band_1(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) + end; +update_band_1(_, _) -> + %% Negative or large positive number. Give up. + integer. + +get_bs_integer_type([_,{integer,N},U,{field_flags,Fl}]) + when N*U < 64 -> + NumBits = N*U, + case member(unsigned, Fl) of + true -> + {integer,{0,(1 bsl NumBits)-1}}; + false -> + %% Signed integer. Don't bother. + integer + end; +get_bs_integer_type(_) -> + %% Avoid creating ranges with a huge upper limit. + integer. + is_math_bif(cos, 1) -> true; is_math_bif(cosh, 1) -> true; is_math_bif(sin, 1) -> true; @@ -545,11 +621,22 @@ load_reg(V, Ts, Rs0, Is0) -> {Rs,Is} end. -arith_op('+') -> {yes,fadd}; -arith_op('-') -> {yes,fsub}; -arith_op('*') -> {yes,fmul}; -arith_op('/') -> {yes,fdiv}; -arith_op(_) -> no. +arith_op(Op) -> + case op_type(Op) of + {float,Instr} -> {yes,Instr}; + _ -> no + end. + +op_type('+') -> {float,fadd}; +op_type('-') -> {float,fsub}; +op_type('*') -> {float,fmul}; +%% '/' and 'band' are specially handled. +op_type('bor') -> integer; +op_type('bxor') -> integer; +op_type('bsl') -> integer; +op_type('bsr') -> integer; +op_type('div') -> integer; +op_type(_) -> unknown. flush(Rs, [{set,[_],[],{put_tuple,_}}|_]=Is0, Acc0) -> Acc = flush_all(Rs, Is0, Acc0), @@ -639,6 +726,9 @@ checkerror_2(OrigIs) -> [{set,[],[],fcheckerror}|OrigIs]. %%% of the first element). %%% %%% 'float' means that the register contains a float. +%%% +%%% 'integer' or {integer,{Min,Max}} that the register contains an +%%% integer. %% tdb_new() -> EmptyDataBase %% Creates a new, empty type database. @@ -728,10 +818,19 @@ merge_type_info({tuple,Sz1,[]}, {tuple,_Sz2,First}=Tuple2) -> merge_type_info({tuple,Sz1,First}, Tuple2); merge_type_info({tuple,_Sz1,First}=Tuple1, {tuple,Sz2,_}) -> merge_type_info(Tuple1, {tuple,Sz2,First}); +merge_type_info(integer, {integer,_}=Int) -> + Int; +merge_type_info({integer,_}=Int, integer) -> + Int; +merge_type_info({integer,{Min1,Max1}}, {integer,{Min2,Max2}}) -> + {integer,{max(Min1, Min2),min(Max1, Max2)}}; merge_type_info(NewType, _) -> verify_type(NewType), NewType. +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; -- cgit v1.2.3