From 871a67b5f2696cca6124e85a9b3ad9355a041ba6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sat, 24 Nov 2012 08:47:41 +0100 Subject: beam_jump: Move bs_context_to_binary/1 + exit instruction Generate slightly smaller and faster code. --- lib/compiler/src/beam_jump.erl | 2 ++ 1 file changed, 2 insertions(+) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl index b05d01b2a1..636c299e47 100644 --- a/lib/compiler/src/beam_jump.erl +++ b/lib/compiler/src/beam_jump.erl @@ -220,6 +220,8 @@ extract_seq([{line,_}=Line|Is], Acc) -> extract_seq(Is, [Line|Acc]); extract_seq([{block,_}=Bl|Is], Acc) -> extract_seq_1(Is, [Bl|Acc]); +extract_seq([{bs_context_to_binary,_}=I|Is], Acc) -> + extract_seq_1(Is, [I|Acc]); extract_seq([{label,_}|_]=Is, Acc) -> extract_seq_1(Is, Acc); extract_seq(_, _) -> no. -- cgit v1.2.3 From 4b01f5b318a866fc5fb9392ddadd1fa54f862692 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Mon, 26 Nov 2012 12:15:25 +0100 Subject: beam_bsm: Make the optimization applicable in more circumstances When determining whether the delayed creation of sub-binaries optimizations is applicable, this module some tests whether the register containg the match state is killed. That is actually a stronger condition than necessary; since the register is initialized, it suffices to test whether the register is unused. --- lib/compiler/src/beam_bsm.erl | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_bsm.erl b/lib/compiler/src/beam_bsm.erl index 37053e1cc4..c9c5b59bf2 100644 --- a/lib/compiler/src/beam_bsm.erl +++ b/lib/compiler/src/beam_bsm.erl @@ -287,11 +287,11 @@ btb_reaches_match_2([{bs_restore2,Src,_}=I|Is], Regs0, D) -> btb_reaches_match_1(Is, Regs0, D); true -> %% Check that all other copies of the context registers - %% are killed by the following instructions. + %% are unused by the following instructions. Regs = btb_kill([Src], Regs0), CtxRegs = btb_context_regs(Regs), - case btb_are_all_killed(CtxRegs, Is, D) of - false -> btb_error({CtxRegs,not_all_killed_after,I}); + case btb_are_all_unused(CtxRegs, Is, D) of + false -> btb_error({CtxRegs,not_all_unused_after,I}); true -> D#btb{must_not_save=true} end end; @@ -301,11 +301,11 @@ btb_reaches_match_2([{bs_context_to_binary,Src}=I|Is], Regs0, D) -> btb_reaches_match_1(Is, Regs0, D); true -> %% Check that all other copies of the context registers - %% are killed by the following instructions. + %% are unused by the following instructions. Regs = btb_kill([Src], Regs0), CtxRegs = btb_context_regs(Regs), - case btb_are_all_killed(CtxRegs, Is, D) of - false -> btb_error({CtxRegs,not_all_killed_after,I}); + case btb_are_all_unused(CtxRegs, Is, D) of + false -> btb_error({CtxRegs,not_all_unused_after,I}); true -> D#btb{must_not_save=true} end end; @@ -343,7 +343,7 @@ btb_call(Arity, Lbl, Regs0, Is, D0) -> %% tucked away in a y register. RegList = btb_context_regs(Regs), YRegs = [R || {y,_}=R <- RegList], - case btb_are_all_killed(YRegs, Is, D) of + case btb_are_all_unused(YRegs, Is, D) of true -> D; false -> btb_error({multiple_uses,RegList}) end; @@ -426,11 +426,11 @@ btb_reaches_match_block([], Regs) -> Regs. %% btb_are_all_killed([Register], [Instruction], D) -> true|false -%% Test whether all of the register are killed in the instruction stream. +%% Test whether all of the register are unused in the instruction stream. -btb_are_all_killed(RegList, Is, #btb{index=Li}) -> +btb_are_all_unused(RegList, Is, #btb{index=Li}) -> all(fun(R) -> - beam_utils:is_killed(R, Is, Li) + beam_utils:is_not_used(R, Is, Li) end, RegList). %% btp_regs_from_list([Register]) -> RegisterSet. -- cgit v1.2.3 From debb6589b998b37d02a52d55f12a2117b2dd0e38 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Mon, 26 Nov 2012 12:28:07 +0100 Subject: beam_utils: Improve is_not_used/3 for bit syntax matching --- lib/compiler/src/beam_utils.erl | 18 +++++------------- 1 file changed, 5 insertions(+), 13 deletions(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_utils.erl b/lib/compiler/src/beam_utils.erl index 8b661e6901..8af0447f63 100644 --- a/lib/compiler/src/beam_utils.erl +++ b/lib/compiler/src/beam_utils.erl @@ -263,19 +263,11 @@ check_liveness(R, [{test,_,{f,Fail},As}|Is], St0) -> {_,_}=Other -> Other end end; -check_liveness(R, [{test,_,{f,Fail},Live,Ss,_}|Is], St0) -> - case R of - {x,X} -> - case X < Live orelse member(R, Ss) of - true -> {used,St0}; - false -> check_liveness_at(R, Fail, St0) - end; - {y,_} -> - case check_liveness_at(R, Fail, St0) of - {killed,St} -> check_liveness(R, Is, St); - {_,_}=Other -> Other - end - end; +check_liveness(R, [{test,Op,Fail,Live,Ss,Dst}|Is], St) -> + %% Check this instruction as a block to get a less conservative + %% result if the caller is is_not_used/3. + Block = [{set,[Dst],Ss,{alloc,Live,{bif,Op,Fail}}}], + check_liveness(R, [{block,Block}|Is], St); check_liveness(R, [{select,_,R,_,_}|_], St) -> {used,St}; check_liveness(R, [{select,_,_,Fail,Branches}|_], St) -> -- cgit v1.2.3 From c38a6726500cd726dd3e605b3be389ee96df131c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sun, 25 Nov 2012 05:59:34 +0100 Subject: beam_bsm: Improve handling of bs_start_match2 instructions The handling of bs_start_match2 was both too conservative and too careless. It was too conservative in that would not do the optimization if the were copies of the match state in other registers. It was careless in that it did not consider the failure branch. Reorganize the code and fix both these issues. Add a test case to test that the failure branch is considered. --- lib/compiler/src/beam_bsm.erl | 48 +++++++++++++++++++++++++++--------- lib/compiler/test/bs_match_SUITE.erl | 30 ++++++++++++++++++++-- 2 files changed, 64 insertions(+), 14 deletions(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/beam_bsm.erl b/lib/compiler/src/beam_bsm.erl index c9c5b59bf2..02794a8e18 100644 --- a/lib/compiler/src/beam_bsm.erl +++ b/lib/compiler/src/beam_bsm.erl @@ -241,21 +241,45 @@ btb_reaches_match_2([{bif,_,{f,F},Ss,Dst}=I|Is], Regs0, D0) -> Regs = btb_kill([Dst], Regs0), D = btb_follow_branch(F, Regs, D0), btb_reaches_match_1(Is, Regs, D); -btb_reaches_match_2([{test,bs_start_match2,_,_,[Ctx,_],Ctx}|Is], Regs, D) -> - case btb_context_regs(Regs) of - [Ctx] -> - D; - CtxRegs -> - case member(Ctx, CtxRegs) of - false -> btb_reaches_match_2(Is, Regs, D); - true -> btb_error(unsuitable_bs_start_match) +btb_reaches_match_2([{test,bs_start_match2,{f,F},Live,[Ctx,_],Ctx}=I|Is], + Regs0, D0) -> + CtxRegs = btb_context_regs(Regs0), + case member(Ctx, CtxRegs) of + false -> + %% This bs_start_match2 instruction does not use "our" + %% match state. Therefore we can continue the search + %% for another bs_start_match2 instruction. + D = btb_follow_branch(F, Regs0, D0), + Regs = btb_kill_not_live(Live, Regs0), + btb_reaches_match_2(Is, Regs, D); + true -> + %% OK. This instruction will use "our" match state, + %% but we must make sure that all other copies of the + %% match state are killed in the code that follows + %% the instruction. (We know that the fail branch cannot + %% be taken in this case.) + OtherCtxRegs = CtxRegs -- [Ctx], + case btb_are_all_unused(OtherCtxRegs, Is, D0) of + false -> btb_error({OtherCtxRegs,not_all_unused_after,I}); + true -> D0 end end; -btb_reaches_match_2([{test,bs_start_match2,_,_,[Bin,_],Ctx}|Is], Regs, D) -> - CtxRegs = btb_context_regs(Regs), +btb_reaches_match_2([{test,bs_start_match2,{f,F},Live,[Bin,_],Ctx}|Is], + Regs0, D0) -> + CtxRegs = btb_context_regs(Regs0), case member(Bin, CtxRegs) orelse member(Ctx, CtxRegs) of - false -> btb_reaches_match_2(Is, Regs, D); - true -> btb_error(unsuitable_bs_start_match) + false -> + %% This bs_start_match2 does not reference any copy of the + %% match state. Therefore it can safely be passed on the + %% way to another (perhaps more suitable) bs_start_match2 + %% instruction. + D = btb_follow_branch(F, Regs0, D0), + Regs = btb_kill_not_live(Live, Regs0), + btb_reaches_match_2(Is, Regs, D); + true -> + %% This variant of the bs_start_match2 instruction does + %% not accept a match state as source. + btb_error(unsuitable_bs_start_match) end; btb_reaches_match_2([{test,_,{f,F},Ss}=I|Is], Regs, D0) -> btb_ensure_not_used(Ss, I, Regs), diff --git a/lib/compiler/test/bs_match_SUITE.erl b/lib/compiler/test/bs_match_SUITE.erl index e8f5c55c1a..d63d2235d7 100644 --- a/lib/compiler/test/bs_match_SUITE.erl +++ b/lib/compiler/test/bs_match_SUITE.erl @@ -33,7 +33,7 @@ matching_meets_construction/1,simon/1,matching_and_andalso/1, otp_7188/1,otp_7233/1,otp_7240/1,otp_7498/1, match_string/1,zero_width/1,bad_size/1,haystack/1, - cover_beam_bool/1,matched_out_size/1]). + cover_beam_bool/1,matched_out_size/1,follow_fail_branch/1]). -export([coverage_id/1,coverage_external_ignore/2]). @@ -57,7 +57,7 @@ groups() -> matching_meets_construction,simon, matching_and_andalso,otp_7188,otp_7233,otp_7240, otp_7498,match_string,zero_width,bad_size,haystack, - cover_beam_bool,matched_out_size]}]. + cover_beam_bool,matched_out_size,follow_fail_branch]}]. init_per_suite(Config) -> @@ -1108,6 +1108,32 @@ mos_bin(<>) -> L = byte_size(Bin), Bin. +follow_fail_branch(_) -> + 42 = ffb_1(<<0,1>>, <<0>>), + 8 = ffb_1(<<0,1>>, [a]), + 42 = ffb_2(<<0,1>>, <<0>>, 17), + 8 = ffb_2(<<0,1>>, [a], 0), + ok. + +ffb_1(<<_,T/bitstring>>, List) -> + case List of + <<_>> -> + 42; + [_|_] -> + %% The fail branch of the bs_start_match2 instruction + %% pointing to here would be ignored, making the compiler + %% incorrectly assume that the delayed sub-binary + %% optimization was safe. + bit_size(T) + end. + +ffb_2(<<_,T/bitstring>>, List, A) -> + case List of + <<_>> when A =:= 17 -> 42; + [_|_] -> bit_size(T) + end. + + check(F, R) -> R = F(). -- cgit v1.2.3