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(<<B:1,Tail/binary>>) ->
    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(<<B:1,Tail/binary>>) ->
    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.

4 files changed, 215 insertions, 13 deletions

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;
diff --git a/lib/compiler/test/Makefile b/lib/compiler/test/Makefile
index 6553d10077..0cd8618730 100644
--- a/lib/compiler/test/Makefile
+++ b/lib/compiler/test/Makefile
@@ -11,6 +11,7 @@ MODULES= \
 	beam_validator_SUITE \
 	beam_disasm_SUITE \
 	beam_except_SUITE \
+	beam_type_SUITE \
 	beam_utils_SUITE \
 	bs_bincomp_SUITE \
 	bs_bit_binaries_SUITE \
@@ -43,6 +44,7 @@ NO_OPT= \
 	andor \
 	apply \
 	beam_except \
+	beam_type \
 	beam_utils \
 	bs_construct \
         bs_match \
diff --git a/lib/compiler/test/beam_type_SUITE.erl b/lib/compiler/test/beam_type_SUITE.erl
new file mode 100644
index 0000000000..8d99d76180
--- /dev/null
+++ b/lib/compiler/test/beam_type_SUITE.erl
@@ -0,0 +1,87 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2015. All Rights Reserved.
+%%
+%% Licensed under the Apache License, Version 2.0 (the "License");
+%% you may not use this file except in compliance with the License.
+%% You may obtain a copy of the License at
+%%
+%%     http://www.apache.org/licenses/LICENSE-2.0
+%%
+%% Unless required by applicable law or agreed to in writing, software
+%% distributed under the License is distributed on an "AS IS" BASIS,
+%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%% See the License for the specific language governing permissions and
+%% limitations under the License.
+%%
+%% %CopyrightEnd%
+%%
+-module(beam_type_SUITE).
+
+-export([all/0,suite/0,groups/0,init_per_suite/1,end_per_suite/1,
+	 init_per_group/2,end_per_group/2,
+	 integers/1,coverage/1]).
+
+suite() -> [{ct_hooks,[ts_install_cth]}].
+
+all() ->
+    test_lib:recompile(?MODULE),
+    [{group,p}].
+
+groups() ->
+    [{p,[parallel],
+      [integers,
+       coverage
+      ]}].
+
+init_per_suite(Config) ->
+    Config.
+
+end_per_suite(_Config) ->
+    ok.
+
+init_per_group(_GroupName, Config) ->
+    Config.
+
+end_per_group(_GroupName, Config) ->
+    Config.
+
+integers(_Config) ->
+    a = do_integers_1(2#11000),
+    b = do_integers_1(2#11001),
+
+    a = do_integers_2(<<0:1>>),
+    {'EXIT',{{case_clause,-1},_}} = (catch do_integers_2(<<1:1>>)),
+
+    ok.
+
+do_integers_1(B0) ->
+    B = B0 band 1,
+    case B band 15 of
+	0 -> a;
+	1 -> b
+    end.
+
+do_integers_2(Bin) ->
+    <<B:1/signed>> = Bin,
+    case B of
+	0 -> a;
+	1 -> b
+    end.
+
+coverage(_Config) ->
+    {'EXIT',{badarith,_}} = (catch id(1) bsl 0.5),
+    {'EXIT',{badarith,_}} = (catch id(2.0) bsl 2),
+    {'EXIT',{badarith,_}} = (catch a + 0.5),
+    {'EXIT',{badarith,_}} = (catch 2.0 * b),
+
+    {'EXIT',{badarith,_}} = (catch id(42.0) / (1 bsl 2000)),
+
+    id(id(42) band 387439739874298734983787934283479243879),
+    id(-1 band id(13)),
+
+    ok.
+
+id(I) ->
+    I.
diff --git a/lib/compiler/test/bs_match_SUITE.erl b/lib/compiler/test/bs_match_SUITE.erl
index 6e138b0a43..a19b152bc5 100644
--- a/lib/compiler/test/bs_match_SUITE.erl
+++ b/lib/compiler/test/bs_match_SUITE.erl
@@ -36,7 +36,7 @@
 	 match_string/1,zero_width/1,bad_size/1,haystack/1,
 	 cover_beam_bool/1,matched_out_size/1,follow_fail_branch/1,
 	 no_partition/1,calling_a_binary/1,binary_in_map/1,
-	 match_string_opt/1]).
+	 match_string_opt/1,select_on_integer/1]).
 
 -export([coverage_id/1,coverage_external_ignore/2]).
 
@@ -62,7 +62,7 @@ groups() ->
        otp_7498,match_string,zero_width,bad_size,haystack,
        cover_beam_bool,matched_out_size,follow_fail_branch,
        no_partition,calling_a_binary,binary_in_map,
-       match_string_opt]}].
+       match_string_opt,select_on_integer]}].
 
 
 init_per_suite(Config) ->
@@ -1225,6 +1225,20 @@ match_string_opt(Config) when is_list(Config) ->
 do_match_string_opt({<<1>>,{v,V}}=T) ->
     {x,V,T}.
 
+select_on_integer(Config) when is_list(Config) ->
+    42 = do_select_on_integer(<<42>>),
+    <<"abc">> = do_select_on_integer(<<128,"abc">>),
+
+    {'EXIT',_} = (catch do_select_on_integer(<<0:1>>)),
+    {'EXIT',_} = (catch do_select_on_integer(<<1:1>>)),
+    {'EXIT',_} = (catch do_select_on_integer(<<0:1,0:15>>)),
+    ok.
+
+%% The ASN.1 compiler frequently generates code like this.
+do_select_on_integer(<<0:1,I:7>>) ->
+    I;
+do_select_on_integer(<<1:1,_:7,Bin/binary>>) ->
+    Bin.
 
 check(F, R) ->
     R = F().