beam_ssa_opt: Add a scaffold for module-level optimizations

This serves as a base for the upcoming module-level type
optimization, but may come in handy for other passes like
beam_ssa_funs and beam_ssa_bsm that have their own ad-hoc
implementations.

5 files changed, 326 insertions, 86 deletions

diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile
index 074d9b881b..97c73d0e07 100644
--- a/lib/compiler/src/Makefile
+++ b/lib/compiler/src/Makefile
@@ -103,6 +103,7 @@ BEAM_H = $(wildcard ../priv/beam_h/*.h)
 
 HRL_FILES= \
 	beam_disasm.hrl \
+	beam_ssa_opt.hrl \
 	beam_ssa.hrl \
 	core_parse.hrl \
 	v3_kernel.hrl
diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl
index c587f9fb44..93c5922547 100644
--- a/lib/compiler/src/beam_ssa_opt.erl
+++ b/lib/compiler/src/beam_ssa_opt.erl
@@ -18,61 +18,153 @@
 %% %CopyrightEnd%
 %%
 
+%%%
+%%% This is a collection of various optimizations that don't need a separate
+%%% pass by themselves and/or are mutually beneficial to other passes.
+%%%
+%%% The optimizations are applied in "phases," each with a list of sub-passes
+%%% to run. These sub-passes are applied on all functions in a module before
+%%% moving on to the next phase, which lets us gather module-level information
+%%% in one phase and then apply it in the next without having to risk working
+%%% with incomplete information.
+%%%
+%%% Each sub-pass operates on a #st{} record and a func_info_db(), where the
+%%% former is just a #b_function{} whose blocks can be represented either in
+%%% linear or map form, and the latter is a map with information about all
+%%% functions in the module (see beam_ssa_opt.hrl for more details).
+%%%
+
 -module(beam_ssa_opt).
 -export([module/2]).
 
--include("beam_ssa.hrl").
+-include("beam_ssa_opt.hrl").
+
 -import(lists, [append/1,foldl/3,keyfind/3,member/2,
                 reverse/1,reverse/2,
-                splitwith/2,takewhile/2,unzip/1]).
+                splitwith/2,sort/1,takewhile/2,unzip/1]).
+
+-define(DEFAULT_REPETITIONS, 2).
 
 -spec module(beam_ssa:b_module(), [compile:option()]) ->
                     {'ok',beam_ssa:b_module()}.
 
-module(#b_module{body=Fs0}=Module, Opts) ->
-    Ps = passes(Opts),
-    Fs = functions(Fs0, Ps),
-    {ok,Module#b_module{body=Fs}}.
+-record(st, {ssa :: [{beam_ssa:label(),beam_ssa:b_blk()}] |
+                    beam_ssa:block_map(),
+             args :: [beam_ssa:b_var()],
+             cnt :: beam_ssa:label(),
+             anno :: beam_ssa:anno()}).
+-type st_map() :: #{ func_id() => #st{} }.
+
+module(Module, Opts) ->
+    FuncDb0 = case proplists:get_value(no_module_opt, Opts, false) of
+                  false -> build_func_db(Module);
+                  true -> #{}
+              end,
+
+    %% Passes that perform module-level optimizations are often aided by
+    %% optimizing callers before callees and vice versa, so we optimize all
+    %% functions in call order, flipping it as required.
+    StMap0 = build_st_map(Module),
+    Order = get_call_order_po(StMap0, FuncDb0),
 
-functions([F|Fs], Ps) ->
-    [function(F, Ps)|functions(Fs, Ps)];
-functions([], _Ps) -> [].
+    Phases =
+        [{Order, prologue_passes(Opts)}] ++
+        repeat(Opts, repeated_passes(Opts), Order) ++
+        [{Order, epilogue_passes(Opts)}],
 
--type b_blk() :: beam_ssa:b_blk().
--type b_var() :: beam_ssa:b_var().
--type label() :: beam_ssa:label().
+    {StMap, _FuncDb} = foldl(fun({FuncIds, Ps}, {StMap, FuncDb}) ->
+                                     phase(FuncIds, Ps, StMap, FuncDb)
+                             end, {StMap0, FuncDb0}, Phases),
+
+    {ok, finish(Module, StMap)}.
+
+phase([FuncId | Ids], Ps, StMap, FuncDb0) ->
+    try
+        {St, FuncDb} =
+            compile:run_sub_passes(Ps, {map_get(FuncId, StMap), FuncDb0}),
+
+        phase(Ids, Ps, StMap#{ FuncId => St }, FuncDb)
+    catch
+        Class:Error:Stack ->
+            #b_local{name=Name,arity=Arity} = FuncId,
+            io:fwrite("Function: ~w/~w\n", [Name,Arity]),
+            erlang:raise(Class, Error, Stack)
+    end;
+phase([], _Ps, StMap, FuncDb) ->
+    {StMap, FuncDb}.
+
+%% Repeats the given passes, alternating the order between runs to make the
+%% type pass more efficient.
+repeat(Opts, Ps, OrderA) ->
+    Repeat = proplists:get_value(ssa_opt_repeat, Opts, ?DEFAULT_REPETITIONS),
+    OrderB = reverse(OrderA),
+    repeat_1(Repeat, Ps, OrderA, OrderB).
+
+repeat_1(0, _Opts, _OrderA, _OrderB) ->
+    [];
+repeat_1(N, Ps, OrderA, OrderB) when N > 0, N rem 2 =:= 0 ->
+    [{OrderA, Ps} | repeat_1(N - 1, Ps, OrderA, OrderB)];
+repeat_1(N, Ps, OrderA, OrderB) when N > 0, N rem 2 =:= 1 ->
+    [{OrderB, Ps} | repeat_1(N - 1, Ps, OrderA, OrderB)].
+
+%%
+
+get_func_id(F) ->
+    {_Mod, Name, Arity} = beam_ssa:get_anno(func_info, F),
+    #b_local{name=#b_literal{val=Name}, arity=Arity}.
+
+-spec build_st_map(#b_module{}) -> st_map().
+build_st_map(#b_module{body=Fs}) ->
+    build_st_map_1(Fs, #{}).
+
+build_st_map_1([F | Fs], Map) ->
+    #b_function{anno=Anno,args=Args,cnt=Counter,bs=Bs} = F,
+    St = #st{anno=Anno,args=Args,cnt=Counter,ssa=Bs},
+    build_st_map_1(Fs, Map#{ get_func_id(F) => St });
+build_st_map_1([], Map) ->
+    Map.
+
+-spec finish(#b_module{}, st_map()) -> #b_module{}.
+finish(#b_module{body=Fs0}=Module, StMap) ->
+    Module#b_module{body=finish_1(Fs0, StMap)}.
+
+finish_1([F0 | Fs], StMap) ->
+    #st{anno=Anno,cnt=Counter,ssa=Blocks} = map_get(get_func_id(F0), StMap),
+    F = F0#b_function{anno=Anno,bs=Blocks,cnt=Counter},
+    [F | finish_1(Fs, StMap)];
+finish_1([], _StMap) ->
+    [].
+
+%%
 
--record(st, {ssa :: beam_ssa:block_map() | [{label(),b_blk()}],
-             args :: [b_var()],
-             cnt :: label()}).
 -define(PASS(N), {N,fun N/1}).
 
-passes(Opts0) ->
+prologue_passes(Opts) ->
     Ps = [?PASS(ssa_opt_split_blocks),
           ?PASS(ssa_opt_coalesce_phis),
           ?PASS(ssa_opt_element),
           ?PASS(ssa_opt_linearize),
           ?PASS(ssa_opt_tuple_size),
           ?PASS(ssa_opt_record),
-
-          %% Run ssa_opt_cse twice, because it will help ssa_opt_dead,
-          %% and ssa_opt_dead will help ssa_opt_cse.
-          %%
-          %% Run ssa_opt_live twice, because it will help ssa_opt_dead
-          %% and ssa_opt_dead will help ssa_opt_live.
-          %%
-          %% Run beam_ssa_type twice, because there will be more
-          %% opportunities for optimizations after running beam_ssa_dead.
-          ?PASS(ssa_opt_cse),
-          ?PASS(ssa_opt_type),
-          ?PASS(ssa_opt_live),
+          ?PASS(ssa_opt_cse)                   %Helps the first type pass.
+          ],
+    passes_1(Ps, Opts).
+
+%% These passes all benefit from each other (in roughly this order), so they
+%% are repeated as required.
+repeated_passes(Opts) ->
+    Ps = [?PASS(ssa_opt_live),
           ?PASS(ssa_opt_bs_puts),
           ?PASS(ssa_opt_dead),
-          ?PASS(ssa_opt_cse),                   %Second time.
-          ?PASS(ssa_opt_float),
-          ?PASS(ssa_opt_type),                  %Second time.
-          ?PASS(ssa_opt_live),                  %Second time.
-
+          ?PASS(ssa_opt_cse),
+          ?PASS(ssa_opt_type)],                 %Must run after ssa_opt_dead to
+                                                %clean up phi nodes.
+    passes_1(Ps, Opts).
+
+epilogue_passes(Opts) ->
+    Ps = [?PASS(ssa_opt_float),
+          ?PASS(ssa_opt_live),                  %One last time to clean up the
+                                                %mess left by the float pass.
           ?PASS(ssa_opt_bsm),
           ?PASS(ssa_opt_bsm_units),
           ?PASS(ssa_opt_bsm_shortcut),
@@ -81,6 +173,9 @@ passes(Opts0) ->
           ?PASS(ssa_opt_sink),
           ?PASS(ssa_opt_merge_blocks),
           ?PASS(ssa_opt_trim_unreachable)],
+    passes_1(Ps, Opts).
+
+passes_1(Ps, Opts0) ->
     Negations = [{list_to_atom("no_"++atom_to_list(N)),N} ||
                     {N,_} <- Ps],
     Opts = proplists:substitute_negations(Negations, Opts0),
@@ -92,36 +187,121 @@ passes(Opts0) ->
              {NoName,fun(S) -> S end}
      end || {Name,_}=P <- Ps].
 
-function(#b_function{anno=Anno,bs=Blocks0,args=Args,cnt=Count0}=F, Ps) ->
+%% Builds a function information map with basic information about incoming and
+%% outgoing local calls, as well as whether the function is exported.
+-spec build_func_db(#b_module{}) -> func_info_db().
+build_func_db(#b_module{body=Fs,exports=Exports}) ->
     try
-        St = #st{ssa=Blocks0,args=Args,cnt=Count0},
-        #st{ssa=Blocks,cnt=Count} = compile:run_sub_passes(Ps, St),
-        F#b_function{bs=Blocks,cnt=Count}
+        fdb_1(Fs, gb_sets:from_list(Exports), #{})
     catch
-        Class:Error:Stack ->
-            #{func_info:={_,Name,Arity}} = Anno,
-            io:fwrite("Function: ~w/~w\n", [Name,Arity]),
-            erlang:raise(Class, Error, Stack)
+        %% All module-level optimizations are invalid when a NIF can override a
+        %% function, so we have to bail out.
+        throw:load_nif -> #{}
     end.
 
+fdb_1([#b_function{ bs=Bs }=F | Fs], Exports, FuncDb0) ->
+    Id = get_func_id(F),
+
+    #b_local{name=#b_literal{val=Name}, arity=Arity} = Id,
+    Exported = gb_sets:is_element({Name, Arity}, Exports),
+
+    FuncDb1 = case FuncDb0 of
+                  %% We may have an entry already if someone's called us.
+                  #{ Id := Info } ->
+                      FuncDb0#{ Id := Info#func_info{ exported=Exported }};
+                  #{} ->
+                      FuncDb0#{ Id => #func_info{ exported=Exported }}
+              end,
+
+    FuncDb = beam_ssa:fold_rpo(fun(_L, #b_blk{is=Is}, FuncDb) ->
+                                       fdb_is(Is, Id, FuncDb)
+                               end, FuncDb1, Bs),
+
+    fdb_1(Fs, Exports, FuncDb);
+fdb_1([], _Exports, FuncDb) ->
+    FuncDb.
+
+fdb_is([#b_set{op=call,
+               args=[#b_local{}=Callee | _]} | Is],
+       Caller, FuncDb) ->
+    fdb_is(Is, Caller, fdb_update(Caller, Callee, FuncDb));
+fdb_is([#b_set{op=call,
+               args=[#b_remote{mod=#b_literal{val=erlang},
+                               name=#b_literal{val=load_nif}},
+                     _Path, _LoadInfo]} | _Is], _Caller, _FuncDb) ->
+    throw(load_nif);
+fdb_is([_ | Is], Caller, FuncDb) ->
+    fdb_is(Is, Caller, FuncDb);
+fdb_is([], _Caller, FuncDb) ->
+    FuncDb.
+
+fdb_update(Caller, Callee, FuncDb) ->
+    CallerVertex = maps:get(Caller, FuncDb, #func_info{}),
+    CalleeVertex = maps:get(Callee, FuncDb, #func_info{}),
+
+    Calls = ordsets:add_element(Callee, CallerVertex#func_info.out),
+    CalledBy = ordsets:add_element(Caller, CalleeVertex#func_info.in),
+
+    FuncDb#{ Caller => CallerVertex#func_info{out=Calls},
+             Callee => CalleeVertex#func_info{in=CalledBy} }.
+
+%% Returns the post-order of all local calls in this module. That is, it starts
+%% with the functions that don't call any others and then walks up the call
+%% chain.
+%%
+%% Functions where module-level optimization is disabled are added last in
+%% arbitrary order.
+
+get_call_order_po(StMap, FuncDb) ->
+    Leaves = maps:fold(fun(Id, #func_info{out=[]}, Acc) ->
+                               [Id | Acc];
+                          (_, _, Acc) ->
+                               Acc
+                       end, [], FuncDb),
+
+    Order = gco_po_1(sort(Leaves), FuncDb, [], #{}),
+
+    Order ++ maps:fold(fun(K, _V, Acc) ->
+                               case is_map_key(K, FuncDb) of
+                                   false -> [K | Acc];
+                                   true -> Acc
+                               end
+                       end, [], StMap).
+
+gco_po_1([Id | Ids], FuncDb, Children, Seen) when not is_map_key(Id, Seen) ->
+    [Id | gco_po_1(Ids, FuncDb, [Id | Children], Seen#{ Id => true })];
+gco_po_1([_Id | Ids], FuncDb, Children, Seen) ->
+    gco_po_1(Ids, FuncDb, Children, Seen);
+gco_po_1([], FuncDb, [_|_]=Children, Seen) ->
+    gco_po_1(gco_po_parents(Children, FuncDb), FuncDb, [], Seen);
+gco_po_1([], _FuncDb, [], _Seen) ->
+    [].
+
+gco_po_parents([Child | Children], FuncDb) ->
+    #{ Child := #func_info{in=Parents}} = FuncDb,
+    Parents ++ gco_po_parents(Children, FuncDb);
+gco_po_parents([], _FuncDb) ->
+    [].
+
 %%%
 %%% Trivial sub passes.
 %%%
 
-ssa_opt_dead(#st{ssa=Linear}=St) ->
-    St#st{ssa=beam_ssa_dead:opt(Linear)}.
+ssa_opt_dead({#st{ssa=Linear}=St, FuncDb}) ->
+    {St#st{ssa=beam_ssa_dead:opt(Linear)}, FuncDb}.
 
-ssa_opt_linearize(#st{ssa=Blocks}=St) ->
-    St#st{ssa=beam_ssa:linearize(Blocks)}.
+ssa_opt_linearize({#st{ssa=Blocks}=St, FuncDb}) ->
+    {St#st{ssa=beam_ssa:linearize(Blocks)}, FuncDb}.
 
-ssa_opt_type(#st{ssa=Linear,args=Args}=St) ->
-    St#st{ssa=beam_ssa_type:opt(Linear, Args)}.
+ssa_opt_type({#st{ssa=Linear0,args=Args}=St0, FuncDb}) ->
+    Linear = beam_ssa_type:opt(Linear0, Args),
+    {St0#st{ssa=Linear}, FuncDb}.
 
-ssa_opt_blockify(#st{ssa=Linear}=St) ->
-    St#st{ssa=maps:from_list(Linear)}.
+ssa_opt_blockify({#st{ssa=Linear}=St, FuncDb}) ->
+    {St#st{ssa=maps:from_list(Linear)}, FuncDb}.
 
-ssa_opt_trim_unreachable(#st{ssa=Blocks}=St) ->
-    St#st{ssa=beam_ssa:trim_unreachable(Blocks)}.
+ssa_opt_trim_unreachable({#st{ssa=Blocks}=St, FuncDb}) ->
+    {St#st{ssa=beam_ssa:trim_unreachable(Blocks)}, FuncDb}.
 
 %%%
 %%% Split blocks before certain instructions to enable more optimizations.
@@ -133,14 +313,14 @@ ssa_opt_trim_unreachable(#st{ssa=Blocks}=St) ->
 %%% for sinking get_tuple_element instructions.
 %%%
 
-ssa_opt_split_blocks(#st{ssa=Blocks0,cnt=Count0}=St) ->
+ssa_opt_split_blocks({#st{ssa=Blocks0,cnt=Count0}=St, FuncDb}) ->
     P = fun(#b_set{op={bif,element}}) -> true;
            (#b_set{op=call}) -> true;
            (#b_set{op=make_fun}) -> true;
            (_) -> false
         end,
     {Blocks,Count} = beam_ssa:split_blocks(P, Blocks0, Count0),
-    St#st{ssa=Blocks,cnt=Count}.
+    {St#st{ssa=Blocks,cnt=Count}, FuncDb}.
 
 %%%
 %%% Coalesce phi nodes.
@@ -164,10 +344,10 @@ ssa_opt_split_blocks(#st{ssa=Blocks0,cnt=Count0}=St) ->
 %%% different registers).
 %%%
 
-ssa_opt_coalesce_phis(#st{ssa=Blocks0}=St) ->
+ssa_opt_coalesce_phis({#st{ssa=Blocks0}=St, FuncDb}) ->
     Ls = beam_ssa:rpo(Blocks0),
     Blocks = c_phis_1(Ls, Blocks0),
-    St#st{ssa=Blocks}.
+    {St#st{ssa=Blocks}, FuncDb}.
 
 c_phis_1([L|Ls], Blocks0) ->
     case maps:get(L, Blocks0) of
@@ -247,7 +427,7 @@ c_fix_branches([], _, Blocks) -> Blocks.
 %%% be replaced with get_tuple_element/3 instructions.
 %%%
 
-ssa_opt_element(#st{ssa=Blocks}=St) ->
+ssa_opt_element({#st{ssa=Blocks}=St, FuncDb}) ->
     %% Collect the information about element instructions in this
     %% function.
     GetEls = collect_element_calls(beam_ssa:linearize(Blocks)),
@@ -259,7 +439,7 @@ ssa_opt_element(#st{ssa=Blocks}=St) ->
 
     %% For each chain, swap the first element call with the
     %% element call with the highest index.
-    St#st{ssa=swap_element_calls(Chains, Blocks)}.
+    {St#st{ssa=swap_element_calls(Chains, Blocks)}, FuncDb}.
 
 collect_element_calls([{L,#b_blk{is=Is0,last=Last}}|Bs]) ->
     case {Is0,Last} of
@@ -320,9 +500,9 @@ swap_element_calls_1([], _, Blocks) ->
 %%% when applicable.
 %%%
 
-ssa_opt_record(#st{ssa=Linear}=St) ->
+ssa_opt_record({#st{ssa=Linear}=St, FuncDb}) ->
     Blocks = maps:from_list(Linear),
-    St#st{ssa=record_opt(Linear, Blocks)}.
+    {St#st{ssa=record_opt(Linear, Blocks)}, FuncDb}.
 
 record_opt([{L,#b_blk{is=Is0,last=Last}=Blk0}|Bs], Blocks) ->
     Is = record_opt_is(Is0, Last, Blocks),
@@ -406,9 +586,9 @@ is_tagged_tuple_4([], _, _) -> no.
 %%% subexpressions across instructions that clobber the X registers.
 %%%
 
-ssa_opt_cse(#st{ssa=Linear}=St) ->
+ssa_opt_cse({#st{ssa=Linear}=St, FuncDb}) ->
     M = #{0=>#{}},
-    St#st{ssa=cse(Linear, #{}, M)}.
+    {St#st{ssa=cse(Linear, #{}, M)}, FuncDb}.
 
 cse([{L,#b_blk{is=Is0,last=Last0}=Blk}|Bs], Sub0, M0) ->
     Es0 = maps:get(L, M0),
@@ -549,13 +729,13 @@ cse_suitable(#b_set{}) -> false.
          bs :: beam_ssa:block_map()
         }).
 
-ssa_opt_float(#st{ssa=Linear0,cnt=Count0}=St) ->
+ssa_opt_float({#st{ssa=Linear0,cnt=Count0}=St, FuncDb}) ->
     NonGuards0 = float_non_guards(Linear0),
     NonGuards = gb_sets:from_list(NonGuards0),
     Blocks = maps:from_list(Linear0),
     Fs = #fs{non_guards=NonGuards,bs=Blocks},
     {Linear,Count} = float_opt(Linear0, Count0, Fs),
-    St#st{ssa=Linear,cnt=Count}.
+    {St#st{ssa=Linear,cnt=Count}, FuncDb}.
 
 float_non_guards([{L,#b_blk{is=Is}}|Bs]) ->
     case Is of
@@ -793,12 +973,12 @@ float_flush_regs(#fs{regs=Rs}) ->
 %%% with a cheaper instructions
 %%%
 
-ssa_opt_live(#st{ssa=Linear0}=St) ->
+ssa_opt_live({#st{ssa=Linear0}=St, FuncDb}) ->
     RevLinear = reverse(Linear0),
     Blocks0 = maps:from_list(RevLinear),
     Blocks = live_opt(RevLinear, #{}, Blocks0),
     Linear = beam_ssa:linearize(Blocks),
-    St#st{ssa=Linear}.
+    {St#st{ssa=Linear}, FuncDb}.
 
 live_opt([{L,Blk0}|Bs], LiveMap0, Blocks) ->
     Blk1 = beam_ssa_share:block(Blk0, Blocks),
@@ -911,10 +1091,10 @@ live_opt_unused(_) -> keep.
 %%%   with bs_test_tail.
 %%%
 
-ssa_opt_bsm(#st{ssa=Linear}=St) ->
+ssa_opt_bsm({#st{ssa=Linear}=St, FuncDb}) ->
     Extracted0 = bsm_extracted(Linear),
     Extracted = cerl_sets:from_list(Extracted0),
-    St#st{ssa=bsm_skip(Linear, Extracted)}.
+    {St#st{ssa=bsm_skip(Linear, Extracted)}, FuncDb}.
 
 bsm_skip([{L,#b_blk{is=Is0}=Blk}|Bs0], Extracted) ->
     Bs = bsm_skip(Bs0, Extracted),
@@ -1012,14 +1192,14 @@ coalesce_skips_is(_, _, _) ->
 %%% Short-cutting binary matching instructions.
 %%%
 
-ssa_opt_bsm_shortcut(#st{ssa=Linear}=St) ->
+ssa_opt_bsm_shortcut({#st{ssa=Linear}=St, FuncDb}) ->
     Positions = bsm_positions(Linear, #{}),
     case map_size(Positions) of
         0 ->
             %% No binary matching instructions.
-            St;
+            {St, FuncDb};
         _ ->
-            St#st{ssa=bsm_shortcut(Linear, Positions)}
+            {St#st{ssa=bsm_shortcut(Linear, Positions)}, FuncDb}
     end.
 
 bsm_positions([{L,#b_blk{is=Is,last=Last}}|Bs], PosMap0) ->
@@ -1081,8 +1261,8 @@ bsm_shortcut([], _PosMap) -> [].
 %%% Eliminate redundant bs_test_unit2 instructions.
 %%%
 
-ssa_opt_bsm_units(#st{ssa=Linear}=St) ->
-    St#st{ssa=bsm_units(Linear, #{})}.
+ssa_opt_bsm_units({#st{ssa=Linear}=St, FuncDb}) ->
+    {St#st{ssa=bsm_units(Linear, #{})}, FuncDb}.
 
 bsm_units([{L,#b_blk{last=#b_br{succ=Succ,fail=Fail}}=Block0} | Bs], UnitMaps0) ->
     UnitsIn = maps:get(L, UnitMaps0, #{}),
@@ -1190,9 +1370,9 @@ bsm_units_join_1([], _MapA, Right) ->
 %%% to bs_put_string instructions in later pass.
 %%%
 
-ssa_opt_bs_puts(#st{ssa=Linear0,cnt=Count0}=St) ->
+ssa_opt_bs_puts({#st{ssa=Linear0,cnt=Count0}=St, FuncDb}) ->
     {Linear,Count} = opt_bs_puts(Linear0, Count0, []),
-    St#st{ssa=Linear,cnt=Count}.
+    {St#st{ssa=Linear,cnt=Count}, FuncDb}.
 
 opt_bs_puts([{L,#b_blk{is=Is}=Blk0}|Bs], Count0, Acc0) ->
     case Is of
@@ -1410,9 +1590,9 @@ opt_bs_put_split_int_1(Int, L, R) ->
 %%% is_tuple_of_arity instruction by the loader.
 %%%
 
-ssa_opt_tuple_size(#st{ssa=Linear0,cnt=Count0}=St) ->
+ssa_opt_tuple_size({#st{ssa=Linear0,cnt=Count0}=St, FuncDb}) ->
     {Linear,Count} = opt_tup_size(Linear0, Count0, []),
-    St#st{ssa=Linear,cnt=Count}.
+    {St#st{ssa=Linear,cnt=Count}, FuncDb}.
 
 opt_tup_size([{L,#b_blk{is=Is,last=Last}=Blk}|Bs], Count0, Acc0) ->
     case {Is,Last} of
@@ -1485,9 +1665,9 @@ opt_tup_size_is([], _, _, _Acc) -> none.
 %%% is 'true' or 'false' can be rewritten to a is_boolean test.
 %%%
 
-ssa_opt_sw(#st{ssa=Linear0,cnt=Count0}=St) ->
+ssa_opt_sw({#st{ssa=Linear0,cnt=Count0}=St, FuncDb}) ->
     {Linear,Count} = opt_sw(Linear0, #{}, Count0, []),
-    St#st{ssa=Linear,cnt=Count}.
+    {St#st{ssa=Linear,cnt=Count}, FuncDb}.
 
 opt_sw([{L,#b_blk{is=Is,last=#b_switch{}=Last0}=Blk0}|Bs], Phis0, Count0, Acc) ->
     Phis = opt_sw_phis(Is, Phis0),
@@ -1578,9 +1758,10 @@ opt_sw_literals([], Acc) -> Acc.
 %%% Merge blocks.
 %%%
 
-ssa_opt_merge_blocks(#st{ssa=Blocks}=St) ->
+ssa_opt_merge_blocks({#st{ssa=Blocks}=St, FuncDb}) ->
     Preds = beam_ssa:predecessors(Blocks),
-    St#st{ssa=merge_blocks_1(beam_ssa:rpo(Blocks), Preds, Blocks)}.
+    Merged = merge_blocks_1(beam_ssa:rpo(Blocks), Preds, Blocks),
+    {St#st{ssa=Merged}, FuncDb}.
 
 merge_blocks_1([L|Ls], Preds0, Blocks0) ->
     case Preds0 of
@@ -1590,6 +1771,7 @@ merge_blocks_1([L|Ls], Preds0, Blocks0) ->
                 true ->
                     #b_blk{is=Is0} = Blk0,
                     #b_blk{is=Is1} = Blk1,
+                    verify_merge_is(Is1),
                     Is = Is0 ++ Is1,
                     Blk = Blk1#b_blk{is=Is},
                     Blocks1 = maps:remove(L, Blocks0),
@@ -1615,6 +1797,13 @@ merge_update_preds([], _, _, Preds) -> Preds.
 rename_label(From, From, To) -> To;
 rename_label(Lbl, _, _) -> Lbl.
 
+verify_merge_is([#b_set{op=Op}|_]) ->
+    %% The merged block has only one predecessor, so it should not have any phi
+    %% nodes.
+    true = Op =/= phi;                          %Assertion.
+verify_merge_is(_) ->
+    ok.
+
 is_merge_allowed(_, _, #b_blk{is=[#b_set{op=peek_message}|_]}) ->
     false;
 is_merge_allowed(L, Blk0, #b_blk{}) ->
@@ -1639,7 +1828,7 @@ is_merge_allowed(L, Blk0, #b_blk{}) ->
 %%% extracted values.
 %%%
 
-ssa_opt_sink(#st{ssa=Blocks0}=St) ->
+ssa_opt_sink({#st{ssa=Blocks0}=St, FuncDb}) ->
     Linear = beam_ssa:linearize(Blocks0),
 
     %% Create a map with all variables that define get_tuple_element
@@ -1680,7 +1869,7 @@ ssa_opt_sink(#st{ssa=Blocks0}=St) ->
                            From = maps:get(V, Defs),
                            move_defs(V, From, To, A)
                    end, Blocks0, DefLoc),
-    St#st{ssa=Blocks}.
+    {St#st{ssa=Blocks}, FuncDb}.
 
 def_blocks([{L,#b_blk{is=Is}}|Bs]) ->
     def_blocks_is(Is, L, def_blocks(Bs));
diff --git a/lib/compiler/src/beam_ssa_opt.hrl b/lib/compiler/src/beam_ssa_opt.hrl
new file mode 100644
index 0000000000..21a45f562a
--- /dev/null
+++ b/lib/compiler/src/beam_ssa_opt.hrl
@@ -0,0 +1,37 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2019. 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%
+%%
+
+-include("beam_ssa.hrl").
+
+-record(func_info,
+        {%% Local calls going in/out of this function.
+         in = ordsets:new() :: ordsets:ordset(func_id()),
+         out = ordsets:new() :: ordsets:ordset(func_id()),
+
+         %% Whether the function is exported or not; some optimizations may
+         %% need to be suppressed if it is.
+         exported = true :: boolean()}).
+
+%% Per-function metadata used by various optimization passes to perform
+%% module-level optimization. If a function is absent it means that
+%% module-level optimization has been turned off for said function.
+
+-type func_id() :: beam_ssa:b_local().
+-type func_info_db() :: #{ func_id() => #func_info{} }.
diff --git a/lib/compiler/test/Makefile b/lib/compiler/test/Makefile
index 40428b7f2d..f042a5cb51 100644
--- a/lib/compiler/test/Makefile
+++ b/lib/compiler/test/Makefile
@@ -105,6 +105,8 @@ CORE_MODULES = \
 	lfe_andor_SUITE \
 	lfe_guard_SUITE
 
+NO_MOD_OPT = $(NO_OPT)
+
 NO_OPT_MODULES= $(NO_OPT:%=%_no_opt_SUITE)
 NO_OPT_ERL_FILES= $(NO_OPT_MODULES:%=%.erl)
 POST_OPT_MODULES= $(NO_OPT:%=%_post_opt_SUITE)
@@ -113,6 +115,8 @@ INLINE_MODULES= $(INLINE:%=%_inline_SUITE)
 INLINE_ERL_FILES= $(INLINE_MODULES:%=%.erl)
 R21_MODULES= $(R21:%=%_r21_SUITE)
 R21_ERL_FILES= $(R21_MODULES:%=%.erl)
+NO_MOD_OPT_MODULES= $(NO_MOD_OPT:%=%_no_module_opt_SUITE)
+NO_MOD_OPT_ERL_FILES= $(NO_MOD_OPT_MODULES:%=%.erl)
 
 ERL_FILES= $(MODULES:%=%.erl)
 CORE_FILES= $(CORE_MODULES:%=%.core)
@@ -142,7 +146,7 @@ EBIN = .
 # ----------------------------------------------------
 
 make_emakefile: $(NO_OPT_ERL_FILES) $(POST_OPT_ERL_FILES) \
-  $(INLINE_ERL_FILES) $(R21_ERL_FILES)
+  $(INLINE_ERL_FILES) $(R21_ERL_FILES) $(NO_MOD_OPT_ERL_FILES)
 	$(ERL_TOP)/make/make_emakefile $(ERL_COMPILE_FLAGS) -o$(EBIN) $(MODULES) \
 	> $(EMAKEFILE)
 	$(ERL_TOP)/make/make_emakefile +no_copt +no_postopt \
@@ -154,6 +158,8 @@ make_emakefile: $(NO_OPT_ERL_FILES) $(POST_OPT_ERL_FILES) \
 	-o$(EBIN) $(INLINE_MODULES) >> $(EMAKEFILE)
 	$(ERL_TOP)/make/make_emakefile +r21 $(ERL_COMPILE_FLAGS) \
 	-o$(EBIN) $(R21_MODULES) >> $(EMAKEFILE)
+	$(ERL_TOP)/make/make_emakefile +no_module_opt $(ERL_COMPILE_FLAGS) \
+	-o$(EBIN) $(NO_MOD_OPT_MODULES) >> $(EMAKEFILE)
 	$(ERL_TOP)/make/make_emakefile +from_core $(ERL_COMPILE_FLAGS) \
 	-o$(EBIN) $(CORE_MODULES) >> $(EMAKEFILE)
 
@@ -183,6 +189,9 @@ docs:
 %_r21_SUITE.erl: %_SUITE.erl
 	sed -e 's;-module($(basename $<));-module($(basename $@));' $< > $@
 
+%_no_module_opt_SUITE.erl: %_SUITE.erl
+	sed -e 's;-module($(basename $<));-module($(basename $@));' $< > $@
+
 # ----------------------------------------------------
 # Release Target
 # ---------------------------------------------------- 
@@ -195,7 +204,8 @@ release_tests_spec: make_emakefile
 	$(INSTALL_DATA) compiler.spec compiler.cover \
 		$(EMAKEFILE) $(ERL_FILES) "$(RELSYSDIR)"
 	$(INSTALL_DATA) $(NO_OPT_ERL_FILES) $(POST_OPT_ERL_FILES) \
-		$(INLINE_ERL_FILES) $(R21_ERL_FILES) "$(RELSYSDIR)"
+		$(INLINE_ERL_FILES) $(R21_ERL_FILES) \
+		$(NO_MOD_OPT_ERL_FILES) "$(RELSYSDIR)"
 	$(INSTALL_DATA) $(CORE_FILES) "$(RELSYSDIR)"
 	for file in $(ERL_DUMMY_FILES); do \
 	    module=`basename $$file .erl`; \
diff --git a/lib/compiler/test/test_lib.erl b/lib/compiler/test/test_lib.erl
index 4502f5b68a..08f2e8fae9 100644
--- a/lib/compiler/test/test_lib.erl
+++ b/lib/compiler/test/test_lib.erl
@@ -81,6 +81,7 @@ opt_opts(Mod) ->
                     (no_put_tuple2) -> true;
                     (no_bsm3) -> true;
                     (no_bsm_opt) -> true;
+                    (no_module_opt) -> true;
 		    (_) -> false
 		 end, Opts).
 
@@ -93,8 +94,9 @@ get_data_dir(Config) ->
     Opts = [{return,list}],
     Data1 = re:replace(Data0, "_no_opt_SUITE", "_SUITE", Opts),
     Data2 = re:replace(Data1, "_post_opt_SUITE", "_SUITE", Opts),
-    Data = re:replace(Data2, "_inline_SUITE", "_SUITE", Opts),
-    re:replace(Data, "_r21_SUITE", "_SUITE", Opts).
+    Data3 = re:replace(Data2, "_inline_SUITE", "_SUITE", Opts),
+    Data4 = re:replace(Data3, "_r21_SUITE", "_SUITE", Opts),
+    re:replace(Data4, "_no_module_opt_SUITE", "_SUITE", Opts).
 
 is_cloned_mod(Mod) ->
     is_cloned_mod_1(atom_to_list(Mod)).
@@ -105,6 +107,7 @@ is_cloned_mod_1("no_opt_SUITE") -> true;
 is_cloned_mod_1("post_opt_SUITE") -> true;
 is_cloned_mod_1("inline_SUITE") -> true;
 is_cloned_mod_1("21_SUITE") -> true;
+is_cloned_mod_1("no_module_opt_SUITE") -> true;
 is_cloned_mod_1([_|T]) -> is_cloned_mod_1(T);
 is_cloned_mod_1([]) -> false.