From cfc2b4ff4a6a2c46a3e2458eb87fd089e610783a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Micha=C5=82=20Muska=C5=82a?= Date: Wed, 9 Aug 2017 13:51:16 +0200 Subject: Run the sharing optimisation in beam_jump until fixpoint This is especially useful after inlining a function with a case. Today the compiler would most probably be able to unify all the leafs of the case during the sharing optimisation, but it would fail to unify the pattern matching itself. Naively running the optimisation multiple times wouldn't be able to find the common code either, because it would differ in jump/fail targets of various instructions. To remedy this, after doing each sharing pass we traverse the code backwards when reversing and update all the jump targets with the new targets that were discovered during the unification pass. This allows running the optimisation until fixpoint and makes sure all sharing opportunities will be discovered. This optimisation also helps with the Elixir's `with/else` construct. --- lib/compiler/src/beam_jump.erl | 65 ++++++++++++++++++++++++++---------------- 1 file changed, 40 insertions(+), 25 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl index 576d20505d..c33de217bd 100644 --- a/lib/compiler/src/beam_jump.erl +++ b/lib/compiler/src/beam_jump.erl @@ -156,41 +156,46 @@ function({function,Name,Arity,CLabel,Asm0}) -> %%% share(Is0) -> - %% We will get more sharing if we never fall through to a label. - Is = eliminate_fallthroughs(Is0, []), - share_1(Is, #{}, [], []). + Is1 = eliminate_fallthroughs(Is0, []), + Is2 = find_fixpoint(fun(Is) -> + share_1(Is, #{}, #{}, [], []) + end, Is1), + reverse(Is2). -share_1([{label,L}=Lbl|Is], Dict0, [_|_]=Seq, Acc) -> +share_1([{label,L}=Lbl|Is], Dict0, Lbls0, [_|_]=Seq, Acc) -> case maps:find(Seq, Dict0) of error -> Dict = maps:put(Seq, L, Dict0), - share_1(Is, Dict, [], [Lbl|Seq ++ Acc]); + share_1(Is, Dict, Lbls0, [], [Lbl|Seq ++ Acc]); {ok,Label} -> - share_1(Is, Dict0, [], [Lbl,{jump,{f,Label}}|Acc]) + Lbls = maps:put(L, Label, Lbls0), + share_1(Is, Dict0, Lbls, [], [Lbl,{jump,{f,Label}}|Acc]) end; -share_1([{func_info,_,_,_}=I|Is], _, [], Acc) -> - reverse(Is, [I|Acc]); -share_1([{'catch',_,_}=I|Is], Dict0, Seq, Acc) -> - Dict = clean_non_sharable(Dict0), - share_1(Is, Dict, [I|Seq], Acc); -share_1([{'try',_,_}=I|Is], Dict0, Seq, Acc) -> - Dict = clean_non_sharable(Dict0), - share_1(Is, Dict, [I|Seq], Acc); -share_1([{try_case,_}=I|Is], Dict0, Seq, Acc) -> - Dict = clean_non_sharable(Dict0), - share_1(Is, Dict, [I|Seq], Acc); -share_1([{catch_end,_}=I|Is], Dict0, Seq, Acc) -> - Dict = clean_non_sharable(Dict0), - share_1(Is, Dict, [I|Seq], Acc); -share_1([I|Is], Dict, Seq, Acc) -> +share_1([{func_info,_,_,_}|_]=Is, _, Lbls, [], Acc) when Lbls =/= #{} -> + beam_utils:replace_labels(Acc, Is, Lbls, fun(Old) -> Old end); +share_1([{func_info,_,_,_}|_]=Is, _, Lbls, [], Acc) when Lbls =:= #{} -> + reverse(Acc, Is); +share_1([{'catch',_,_}=I|Is], Dict0, Lbls0, Seq, Acc) -> + {Dict,Lbls} = clean_non_sharable(Dict0, Lbls0), + share_1(Is, Dict, Lbls, [I|Seq], Acc); +share_1([{'try',_,_}=I|Is], Dict0, Lbls0, Seq, Acc) -> + {Dict,Lbls} = clean_non_sharable(Dict0, Lbls0), + share_1(Is, Dict, Lbls, [I|Seq], Acc); +share_1([{try_case,_}=I|Is], Dict0, Lbls0, Seq, Acc) -> + {Dict,Lbls} = clean_non_sharable(Dict0, Lbls0), + share_1(Is, Dict, Lbls, [I|Seq], Acc); +share_1([{catch_end,_}=I|Is], Dict0, Lbls0, Seq, Acc) -> + {Dict,Lbls} = clean_non_sharable(Dict0, Lbls0), + share_1(Is, Dict, Lbls, [I|Seq], Acc); +share_1([I|Is], Dict, Lbls, Seq, Acc) -> case is_unreachable_after(I) of false -> - share_1(Is, Dict, [I|Seq], Acc); + share_1(Is, Dict, Lbls, [I|Seq], Acc); true -> - share_1(Is, Dict, [I], Acc) + share_1(Is, Dict, Lbls, [I], Acc) end. -clean_non_sharable(Dict) -> +clean_non_sharable(Dict0, Lbls0) -> %% We are passing in or out of a 'catch' or 'try' block. Remove %% sequences that should not be shared over the boundaries of the %% block. Since the end of the sequence must match, the only @@ -198,7 +203,17 @@ clean_non_sharable(Dict) -> %% the 'catch'/'try' block is a sequence that ends with an %% instruction that causes an exception. Any sequence that causes %% an exception must contain a line/1 instruction. - maps:filter(fun(K, _V) -> sharable_with_try(K) end, Dict). + Dict1 = maps:to_list(Dict0), + Lbls1 = maps:to_list(Lbls0), + {Dict2,Lbls2} = foldl(fun({K, V}, {Dict,Lbls}) -> + case sharable_with_try(K) of + true -> + {[{K,V}|Dict],lists:keydelete(V, 2, Lbls)}; + false -> + {Dict,Lbls} + end + end, {[],Lbls1}, Dict1), + {maps:from_list(Dict2),maps:from_list(Lbls2)}. sharable_with_try([{line,_}|_]) -> %% This sequence may cause an exception and may potentially -- cgit v1.2.3 From 7fed1e036b0c70aaa1e738a403379bab96745e63 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Micha=C5=82=20Muska=C5=82a?= Date: Wed, 6 Jun 2018 19:10:05 +0200 Subject: Optimise beam_jump This is an alternative to #1832. The optimisation relies on special-casing the common pattern of "renaming" a label by direct jump to another label. The change makes beam_jump recognise couple more opportunities for optimisation. The optimisation additionally avoids superfluous list concatenations by only flattening the accumulator at the very end. --- lib/compiler/src/beam_jump.erl | 21 +++++++++++++-------- 1 file changed, 13 insertions(+), 8 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl index c33de217bd..19c26d4ef9 100644 --- a/lib/compiler/src/beam_jump.erl +++ b/lib/compiler/src/beam_jump.erl @@ -164,17 +164,19 @@ share(Is0) -> share_1([{label,L}=Lbl|Is], Dict0, Lbls0, [_|_]=Seq, Acc) -> case maps:find(Seq, Dict0) of - error -> - Dict = maps:put(Seq, L, Dict0), - share_1(Is, Dict, Lbls0, [], [Lbl|Seq ++ Acc]); - {ok,Label} -> + error -> + Dict = maps:put(Seq, L, Dict0), + share_1(Is, Dict, Lbls0, [], [[Lbl|Seq]|Acc]); + {ok,Label} -> Lbls = maps:put(L, Label, Lbls0), - share_1(Is, Dict0, Lbls, [], [Lbl,{jump,{f,Label}}|Acc]) + share_1(Is, Dict0, Lbls, [], [[Lbl,{jump,{f,Label}}]|Acc]) end; -share_1([{func_info,_,_,_}|_]=Is, _, Lbls, [], Acc) when Lbls =/= #{} -> - beam_utils:replace_labels(Acc, Is, Lbls, fun(Old) -> Old end); +share_1([{func_info,_,_,_}|_]=Is0, _, Lbls, [], Acc0) when Lbls =/= #{} -> + lists:foldl(fun(Is, Acc) -> + beam_utils:replace_labels(Is, Acc, Lbls, fun(Old) -> Old end) + end, Is0, Acc0); share_1([{func_info,_,_,_}|_]=Is, _, Lbls, [], Acc) when Lbls =:= #{} -> - reverse(Acc, Is); + lists:foldl(fun lists:reverse/2, Is, Acc); share_1([{'catch',_,_}=I|Is], Dict0, Lbls0, Seq, Acc) -> {Dict,Lbls} = clean_non_sharable(Dict0, Lbls0), share_1(Is, Dict, Lbls, [I|Seq], Acc); @@ -187,6 +189,9 @@ share_1([{try_case,_}=I|Is], Dict0, Lbls0, Seq, Acc) -> share_1([{catch_end,_}=I|Is], Dict0, Lbls0, Seq, Acc) -> {Dict,Lbls} = clean_non_sharable(Dict0, Lbls0), share_1(Is, Dict, Lbls, [I|Seq], Acc); +share_1([{jump,{f,To}}=I,{label,L}=Lbl|Is], Dict0, Lbls0, _Seq, Acc) -> + Lbls = maps:put(L, To, Lbls0), + share_1(Is, Dict0, Lbls, [], [[Lbl,I]|Acc]); share_1([I|Is], Dict, Lbls, Seq, Acc) -> case is_unreachable_after(I) of false -> -- cgit v1.2.3