diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | lib/compiler/src/Makefile | 1 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa_opt.erl | 353 | ||||
| -rw-r--r-- | lib/compiler/src/beam_ssa_opt.hrl | 37 | ||||
| -rw-r--r-- | lib/compiler/test/Makefile | 14 | ||||
| -rw-r--r-- | lib/compiler/test/test_lib.erl | 7 |
6 files changed, 327 insertions, 86 deletions
diff --git a/.gitignore b/.gitignore index 02894c4786..e426c042a2 100644 --- a/.gitignore +++ b/.gitignore @@ -247,6 +247,7 @@ JAVADOC-GENERATED /lib/compiler/test/*_post_opt_SUITE.erl /lib/compiler/test/*_inline_SUITE.erl /lib/compiler/test/*_r21_SUITE.erl +/lib/compiler/test/*_no_module_opt_SUITE.erl # crypto /lib/crypto/test/crypto_SUITE_data/*.rsp 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. |