beam_ssa_opt: Add an optimization of tuple_size/1

This optimization working on the SSA format will replace
the similar optimization in beam_dead. See the comment
for an explanation of what the new optimization does.

3 files changed, 121 insertions, 40 deletions

diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl
index 67c92d5ae2..0bb4a204a2 100644
--- a/lib/compiler/src/beam_ssa_opt.erl
+++ b/lib/compiler/src/beam_ssa_opt.erl
@@ -59,6 +59,7 @@ passes(Opts0) ->
           ?PASS(ssa_opt_bsm),
           ?PASS(ssa_opt_bsm_shortcut),
           ?PASS(ssa_opt_misc),
+          ?PASS(ssa_opt_tuple_size),
           ?PASS(ssa_opt_sw),
           ?PASS(ssa_opt_blockify),
           ?PASS(ssa_opt_sink),
@@ -1089,6 +1090,126 @@ eval_or(Args) ->
     end.
 
 %%%
+%%% Optimize expressions such as "tuple_size(Var) =:= 2".
+%%%
+%%% Consider this code:
+%%%
+%%% 0:
+%%%   .
+%%%   .
+%%%   .
+%%%   Size = bif:tuple_size Var
+%%%   BoolVar1 = succeeded Size
+%%%   br BoolVar1, label 4, label 3
+%%%
+%%% 4:
+%%%   BoolVar2 = bif:'=:=' Size, literal 2
+%%%   br BoolVar2, label 6, label 3
+%%%
+%%% 6: ...   %% OK
+%%%
+%%% 3: ...   %% Not a tuple of size 2
+%%%
+%%% The BEAM code will look this:
+%%%
+%%%   {bif,tuple_size,{f,3},[{x,0}],{x,0}}.
+%%%   {test,is_eq_exact,{f,3},[{x,0},{integer,2}]}.
+%%%
+%%% Better BEAM code will be produced if we transform the
+%%% code like this:
+%%%
+%%% 0:
+%%%   .
+%%%   .
+%%%   .
+%%%   br label 10
+%%%
+%%% 10:
+%%%   NewBoolVar = bif:is_tuple Var
+%%%   br NewBoolVar, label 11, label 3
+%%%
+%%% 11:
+%%%   Size = bif:tuple_size Var
+%%%   br label 4
+%%%
+%%% 4:
+%%%   BoolVar2 = bif:'=:=' Size, literal 2
+%%%   br BoolVar2, label 6, label 3
+%%%
+%%% (The key part of the transformation is the removal of
+%%% the 'succeeded' instruction to signal to the code generator
+%%% that the call to tuple_size/1 can't fail.)
+%%%
+%%% The BEAM code will look like:
+%%%
+%%%   {test,is_tuple,{f,3},[{x,0}]}.
+%%%   {test_arity,{f,3},[{x,0},2]}.
+%%%
+%%% Those two instructions will be combined into a single
+%%% is_tuple_of_arity instruction by the loader.
+%%%
+
+ssa_opt_tuple_size(#st{ssa=Linear0,cnt=Count0}=St) ->
+    {Linear,Count} = opt_tup_size(Linear0, Count0, []),
+    St#st{ssa=Linear,cnt=Count}.
+
+opt_tup_size([{L,#b_blk{is=Is,last=Last}=Blk}|Bs], Count0, Acc0) ->
+    case {Is,Last} of
+        {[#b_set{op={bif,'=:='},dst=Bool,args=[#b_var{}=Tup,#b_literal{val=Arity}]}],
+         #b_br{bool=Bool}} when is_integer(Arity), Arity >= 0 ->
+            {Acc,Count} = opt_tup_size_1(Tup, L, Count0, Acc0),
+            opt_tup_size(Bs, Count, [{L,Blk}|Acc]);
+        {_,_} ->
+            opt_tup_size(Bs, Count0, [{L,Blk}|Acc0])
+    end;
+opt_tup_size([], Count, Acc) ->
+    {reverse(Acc),Count}.
+
+opt_tup_size_1(Size, EqL, Count0, [{L,Blk0}|Acc]) ->
+    case Blk0 of
+        #b_blk{is=Is0,last=#b_br{bool=Bool,succ=EqL,fail=Fail}} ->
+            case opt_tup_size_is(Is0, Bool, Size, []) of
+                none ->
+                    {[{L,Blk0}|Acc],Count0};
+                {PreIs,TupleSizeIs,Tuple} ->
+                    opt_tup_size_2(PreIs, TupleSizeIs, L, EqL,
+                                   Tuple, Fail, Count0, Acc)
+            end;
+        #b_blk{} ->
+            {[{L,Blk0}|Acc],Count0}
+    end;
+opt_tup_size_1(_, _, Count, Acc) ->
+    {Acc,Count}.
+
+opt_tup_size_2(PreIs, TupleSizeIs, PreL, EqL, Tuple, Fail, Count0, Acc) ->
+    IsTupleL = Count0,
+    TupleSizeL = Count0 + 1,
+    Bool = #b_var{name={'@ssa_bool',Count0+2}},
+    Count = Count0 + 3,
+
+    True = #b_literal{val=true},
+    PreBr = #b_br{bool=True,succ=IsTupleL,fail=IsTupleL},
+    PreBlk = #b_blk{is=PreIs,last=PreBr},
+
+    IsTupleIs = [#b_set{op={bif,is_tuple},dst=Bool,args=[Tuple]}],
+    IsTupleBr = #b_br{bool=Bool,succ=TupleSizeL,fail=Fail},
+    IsTupleBlk = #b_blk{is=IsTupleIs,last=IsTupleBr},
+
+    TupleSizeBr = #b_br{bool=True,succ=EqL,fail=EqL},
+    TupleSizeBlk = #b_blk{is=TupleSizeIs,last=TupleSizeBr},
+    {[{TupleSizeL,TupleSizeBlk},
+      {IsTupleL,IsTupleBlk},
+      {PreL,PreBlk}|Acc],Count}.
+
+opt_tup_size_is([#b_set{op={bif,tuple_size},dst=Size,args=[Tuple]}=I,
+                 #b_set{op=succeeded,dst=Bool,args=[Size]}],
+                Bool, Size, Acc) ->
+    {reverse(Acc),[I],Tuple};
+opt_tup_size_is([I|Is], Bool, Size, Acc) ->
+    opt_tup_size_is(Is, Bool, Size, [I|Acc]);
+opt_tup_size_is([], _, _, _Acc) -> none.
+
+%%%
 %%% Optimize #b_switch{} instructions.
 %%%
 %%% If the argument for a #b_switch{} comes from a phi node with all
diff --git a/lib/compiler/test/guard_SUITE.erl b/lib/compiler/test/guard_SUITE.erl
index 73a8dc0fda..6ccc0c8fd4 100644
--- a/lib/compiler/test/guard_SUITE.erl
+++ b/lib/compiler/test/guard_SUITE.erl
@@ -1779,16 +1779,6 @@ t_tuple_size(Config) when is_list(Config) ->
     error = ludicrous_tuple_size({a,b,c}),
     error = ludicrous_tuple_size([a,b,c]),
 
-    %% Test the "unsafe case" - the register assigned the tuple size is
-    %% not killed.
-    DataDir = test_lib:get_data_dir(Config),
-    File = filename:join(DataDir, "guard_SUITE_tuple_size"),
-    {ok,Mod,Code} = compile:file(File, [from_asm,binary]),
-    code:load_binary(Mod, File, Code),
-    14 = Mod:t({1,2,3,4}),
-    _ = code:delete(Mod),
-    _ = code:purge(Mod),
-
     good_ip({1,2,3,4}),
     good_ip({1,2,3,4,5,6,7,8}),
     error = validate_ip({42,11}),
diff --git a/lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S b/lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S
deleted file mode 100644
index cffb792920..0000000000
--- a/lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S
+++ /dev/null
@@ -1,30 +0,0 @@
-{module, guard_SUITE_tuple_size}.  %% version = 0
-
-{exports, [{t,1}]}.
-
-{attributes, []}.
-
-{labels, 5}.
-
-
-{function, t, 1, 2}.
-  {label,1}.
-    {func_info,{atom,guard_SUITE_tuple_size},{atom,t},1}.
-  {label,2}.
-    {bif,tuple_size,{f,4},[{x,0}],{x,1}}.
-    {test,is_eq_exact,{f,4},[{x,1},{integer,4}]}.
-    {test,is_tuple,{f,3},[{x,0}]}.
-    {test,test_arity,{f,3},[{x,0},4]}.
-    {get_tuple_element,{x,0},0,{x,5}}.
-    {get_tuple_element,{x,0},1,{x,2}}.
-    {get_tuple_element,{x,0},2,{x,3}}.
-    {get_tuple_element,{x,0},3,{x,4}}.
-    {gc_bif,'+',{f,0},6,[{x,1},{x,2}],{x,0}}.
-    {gc_bif,'+',{f,0},6,[{x,0},{x,3}],{x,0}}.
-    {gc_bif,'+',{f,0},6,[{x,0},{x,4}],{x,0}}.
-    {gc_bif,'+',{f,0},6,[{x,0},{x,5}],{x,0}}.
-    return.
-  {label,3}.
-    {badmatch,{x,0}}.
-  {label,4}.
-    {jump,{f,1}}.