Optimize named funs and fun-wrapped macros

If a fun is defined locally and only used for calls, it can be replaced
with direct calls to the relevant function. This greatly speeds up "named
functions" (which rely on make_fun to recreate themselves) and macros that
wrap their body in a fun.

5 files changed, 156 insertions, 0 deletions

diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile
index 26ae6566e6..d475e5a19a 100644
--- a/lib/compiler/src/Makefile
+++ b/lib/compiler/src/Makefile
@@ -63,6 +63,7 @@ MODULES =  \
 	beam_ssa_bsm \
 	beam_ssa_codegen \
 	beam_ssa_dead \
+	beam_ssa_funs \
 	beam_ssa_lint \
 	beam_ssa_opt \
 	beam_ssa_pp \
diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl
index 1a2e759965..a71802cf80 100644
--- a/lib/compiler/src/beam_ssa.erl
+++ b/lib/compiler/src/beam_ssa.erl
@@ -198,6 +198,7 @@ no_side_effect(#b_set{op=Op}) ->
         has_map_field -> true;
         is_nonempty_list -> true;
         is_tagged_tuple -> true;
+        make_fun -> true;
         put_map -> true;
         put_list -> true;
         put_tuple -> true;
diff --git a/lib/compiler/src/beam_ssa_funs.erl b/lib/compiler/src/beam_ssa_funs.erl
new file mode 100644
index 0000000000..38df50fd74
--- /dev/null
+++ b/lib/compiler/src/beam_ssa_funs.erl
@@ -0,0 +1,149 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2018. 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%
+%%
+
+%%%
+%%% If a fun is defined locally and only used for calls, it can be replaced
+%%% with direct calls to the relevant function. This greatly speeds up "named
+%%% functions" (which rely on make_fun to recreate themselves) and macros that
+%%% wrap their body in a fun.
+%%%
+
+-module(beam_ssa_funs).
+
+-export([module/2]).
+
+-include("beam_ssa.hrl").
+
+-import(lists, [foldl/3]).
+
+-spec module(Module, Options) -> Result when
+      Module :: beam_ssa:b_module(),
+      Options :: [compile:option()],
+      Result :: {ok, beam_ssa:b_module()}.
+
+module(#b_module{body=Fs0}=Module, _Opts) ->
+    Trampolines = foldl(fun find_trampolines/2, #{}, Fs0),
+    Fs = [lfo(F, Trampolines) || F <- Fs0],
+    {ok, Module#b_module{body=Fs}}.
+
+%% If a function does absolutely nothing beyond calling another function with
+%% the same arguments in the same order, we can shave off a call by short-
+%% circuiting it.
+find_trampolines(#b_function{args=Args,bs=Blocks}=F, Trampolines) ->
+    case maps:get(0, Blocks) of
+        #b_blk{is=[#b_set{op=call,
+                          args=[#b_local{}=Actual | Args],
+                          dst=Dst}],
+               last=#b_ret{arg=Dst}} ->
+            {_, Name, Arity} = beam_ssa:get_anno(func_info, F),
+            Trampoline = #b_local{name=#b_literal{val=Name},arity=Arity},
+            maps:put(Trampoline, Actual, Trampolines);
+        _ ->
+            Trampolines
+    end.
+
+lfo(#b_function{bs=Blocks0}=F, Trampolines) ->
+    Linear0 = beam_ssa:linearize(Blocks0),
+    Linear = lfo_optimize(Linear0, lfo_analyze(Linear0, #{}), Trampolines),
+    F#b_function{bs=maps:from_list(Linear)}.
+
+%% Gather a map of the locally defined funs that are only used for calls.
+lfo_analyze([{_L,#b_blk{is=Is,last=Last}}|Bs], LFuns0) ->
+    LFuns = lfo_analyze_last(Last, lfo_analyze_is(Is, LFuns0)),
+    lfo_analyze(Bs, LFuns);
+lfo_analyze([], LFuns) ->
+    LFuns.
+
+lfo_analyze_is([#b_set{op=make_fun,
+                       dst=Dst,
+                       args=[#b_local{} | FreeVars]}=Def | Is],
+               LFuns0) ->
+    LFuns = maps:put(Dst, Def, maps:without(FreeVars, LFuns0)),
+    lfo_analyze_is(Is, LFuns);
+lfo_analyze_is([#b_set{op=call,
+                       args=[Fun | CallArgs]} | Is],
+               LFuns) when is_map_key(Fun, LFuns) ->
+    #b_set{args=[#b_local{arity=Arity} | FreeVars]} = maps:get(Fun, LFuns),
+    case length(CallArgs) + length(FreeVars) of
+        Arity ->
+            lfo_analyze_is(Is, maps:without(CallArgs, LFuns));
+        _ ->
+            %% This will `badarity` at runtime, and it's easier to disable the
+            %% optimization than to simulate it.
+            lfo_analyze_is(Is, maps:without([Fun | CallArgs], LFuns))
+    end;
+lfo_analyze_is([#b_set{args=Args} | Is], LFuns) when map_size(LFuns) =/= 0 ->
+    %% We disqualify funs that are used outside calls because this forces them
+    %% to be created anyway, and the slight performance gain from direct calls
+    %% is not enough to offset the potential increase in stack frame size (the
+    %% free variables need to be kept alive until the call).
+    %%
+    %% This is also a kludge to make HiPE work, as the latter will generate
+    %% code with the assumption that the functions referenced in a make_fun
+    %% will only be used by funs, which will not be the case if we mix it with
+    %% direct calls. See cerl_cconv.erl for details.
+    %%
+    %% Future optimizations like delaying fun creation until use may require us
+    %% to copy affected functions so that HiPE gets its own to play with (until
+    %% HiPE is fixed anyway).
+    lfo_analyze_is(Is, maps:without(Args, LFuns));
+lfo_analyze_is([_ | Is], LFuns) ->
+    lfo_analyze_is(Is, LFuns);
+lfo_analyze_is([], LFuns) ->
+    LFuns.
+
+lfo_analyze_last(#b_switch{arg=Arg}, LFuns) ->
+    maps:remove(Arg, LFuns);
+lfo_analyze_last(#b_ret{arg=Arg}, LFuns) ->
+    maps:remove(Arg, LFuns);
+lfo_analyze_last(_, LFuns) ->
+    LFuns.
+
+%% Replace all calls of suitable funs with a direct call to their
+%% implementation. Liveness optimization will get rid of the make_fun
+%% instruction.
+lfo_optimize(Linear, LFuns, _Trampolines) when map_size(LFuns) =:= 0 ->
+    Linear;
+lfo_optimize(Linear, LFuns, Trampolines) ->
+    lfo_optimize_1(Linear, LFuns, Trampolines).
+
+lfo_optimize_1([{L,#b_blk{is=Is0}=Blk}|Bs], LFuns, Trampolines) ->
+    Is = lfo_optimize_is(Is0, LFuns, Trampolines),
+    [{L,Blk#b_blk{is=Is}} | lfo_optimize_1(Bs, LFuns, Trampolines)];
+lfo_optimize_1([], _LFuns, _Trampolines) ->
+    [].
+
+lfo_optimize_is([#b_set{op=call,
+                        args=[Fun | CallArgs]}=Call0 | Is],
+                LFuns, Trampolines) when is_map_key(Fun, LFuns) ->
+    #b_set{args=[Local | FreeVars]} = maps:get(Fun, LFuns),
+    Args = [lfo_short_circuit(Local, Trampolines) | CallArgs ++ FreeVars],
+    Call = beam_ssa:add_anno(local_fun_opt, Fun, Call0#b_set{args=Args}),
+    [Call | lfo_optimize_is(Is, LFuns, Trampolines)];
+lfo_optimize_is([I | Is], LFuns, Trampolines) ->
+    [I | lfo_optimize_is(Is, LFuns, Trampolines)];
+lfo_optimize_is([], _LFuns, _Trampolines) ->
+    [].
+
+lfo_short_circuit(Call, Trampolines) ->
+    case maps:find(Call, Trampolines) of
+        {ok, Other} -> lfo_short_circuit(Other, Trampolines);
+        error -> Call
+    end.
diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl
index d894694c79..b4a446e532 100644
--- a/lib/compiler/src/compile.erl
+++ b/lib/compiler/src/compile.erl
@@ -823,6 +823,9 @@ kernel_passes() ->
      {unless,no_bsm_opt,{pass,beam_ssa_bsm}},
      {iff,dssabsm,{listing,"ssabsm"}},
      {iff,ssalint,{pass,beam_ssa_lint}},
+     {unless,no_fun_opt,{pass,beam_ssa_funs}},
+     {iff,dssafuns,{listing,"ssafuns"}},
+     {iff,ssalint,{pass,beam_ssa_lint}},
      {unless,no_ssa_opt,{pass,beam_ssa_opt}},
      {iff,dssaopt,{listing,"ssaopt"}},
      {iff,ssalint,{pass,beam_ssa_lint}},
@@ -2047,6 +2050,7 @@ pre_load() ->
 	 beam_ssa_bsm,
 	 beam_ssa_codegen,
 	 beam_ssa_dead,
+         beam_ssa_funs,
 	 beam_ssa_opt,
 	 beam_ssa_pre_codegen,
 	 beam_ssa_recv,
diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src
index 7b802fdd62..86259270bd 100644
--- a/lib/compiler/src/compiler.app.src
+++ b/lib/compiler/src/compiler.app.src
@@ -39,6 +39,7 @@
              beam_ssa_bsm,
              beam_ssa_codegen,
              beam_ssa_dead,
+             beam_ssa_funs,
              beam_ssa_lint,
              beam_ssa_opt,
              beam_ssa_pp,