aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2018-08-31 07:13:05 +0200
committerBjörn Gustavsson <[email protected]>2018-09-12 14:19:06 +0200
commit4edd266876f2383ccc33b91a3bbe8550279368f5 (patch)
tree0b1bab227e1ba4ef6b00440d65d2c26a865e27a5 /lib/compiler
parentf89331e61b5b6fc6eadc289d4ce126d6a4219238 (diff)
downloadotp-4edd266876f2383ccc33b91a3bbe8550279368f5.tar.gz
otp-4edd266876f2383ccc33b91a3bbe8550279368f5.tar.bz2
otp-4edd266876f2383ccc33b91a3bbe8550279368f5.zip
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.
Diffstat (limited to 'lib/compiler')
-rw-r--r--lib/compiler/src/beam_ssa_opt.erl121
-rw-r--r--lib/compiler/test/guard_SUITE.erl10
-rw-r--r--lib/compiler/test/guard_SUITE_data/guard_SUITE_tuple_size.S30
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}}.