aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2019-02-15 10:18:49 +0100
committerBjörn Gustavsson <[email protected]>2019-02-15 10:18:49 +0100
commitbe028069230e492e8e7fd9887ca5f481c2078a3a (patch)
treee2120d8a09431b4db98deca9b95407022cfc662e /lib
parent05320ffbaa725bb9b25404974fc52219b1c1674c (diff)
parent075164d2fd2eec46a82bd0bf71923cf4a91e3b3a (diff)
downloadotp-be028069230e492e8e7fd9887ca5f481c2078a3a.tar.gz
otp-be028069230e492e8e7fd9887ca5f481c2078a3a.tar.bz2
otp-be028069230e492e8e7fd9887ca5f481c2078a3a.zip
Merge branch 'bjorn/compiler/beam_ssa_opt'
* bjorn/compiler/beam_ssa_opt: Make sure that beam_ssa_opt optimizes all functions
Diffstat (limited to 'lib')
-rw-r--r--lib/compiler/src/beam_ssa_opt.erl43
1 files changed, 19 insertions, 24 deletions
diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl
index 2bd3612c06..355d2d060d 100644
--- a/lib/compiler/src/beam_ssa_opt.erl
+++ b/lib/compiler/src/beam_ssa_opt.erl
@@ -249,22 +249,14 @@ fdb_update(Caller, Callee, FuncDb) ->
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.
+%% Returns the post-order of all local calls in this module. That is,
+%% called functions will be ordered before the functions calling them.
%%
%% 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 = gco_po(FuncDb),
Order ++ maps:fold(fun(K, _V, Acc) ->
case is_map_key(K, FuncDb) of
false -> [K | Acc];
@@ -272,20 +264,23 @@ get_call_order_po(StMap, FuncDb) ->
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(FuncDb) ->
+ All = sort(maps:keys(FuncDb)),
+ {RPO,_} = gco_rpo(All, FuncDb, cerl_sets:new(), []),
+ reverse(RPO).
-gco_po_parents([Child | Children], FuncDb) ->
- #{ Child := #func_info{in=Parents}} = FuncDb,
- Parents ++ gco_po_parents(Children, FuncDb);
-gco_po_parents([], _FuncDb) ->
- [].
+gco_rpo([Id|Ids], FuncDb, Seen0, Acc0) ->
+ case cerl_sets:is_element(Id, Seen0) of
+ true ->
+ gco_rpo(Ids, FuncDb, Seen0, Acc0);
+ false ->
+ #func_info{out=Successors} = map_get(Id, FuncDb),
+ Seen1 = cerl_sets:add_element(Id, Seen0),
+ {Acc,Seen} = gco_rpo(Successors, FuncDb, Seen1, Acc0),
+ gco_rpo(Ids, FuncDb, Seen, [Id|Acc])
+ end;
+gco_rpo([], _, Seen, Acc) ->
+ {Acc,Seen}.
%%%
%%% Trivial sub passes.