aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2019-02-14 15:25:16 +0100
committerBjörn Gustavsson <[email protected]>2019-02-15 09:46:17 +0100
commit075164d2fd2eec46a82bd0bf71923cf4a91e3b3a (patch)
treef7d0a07a7fb3a4fc8e5af5355a8c4adc501de96b
parente54daec589fc0da3d454f683eee2ea1af8eb7684 (diff)
downloadotp-075164d2fd2eec46a82bd0bf71923cf4a91e3b3a.tar.gz
otp-075164d2fd2eec46a82bd0bf71923cf4a91e3b3a.tar.bz2
otp-075164d2fd2eec46a82bd0bf71923cf4a91e3b3a.zip
Make sure that beam_ssa_opt optimizes all functions
The function `get_call_order_po/2` did not always include all functions in a module. The method it used was to first find all leave functions (functions not calling any other function), and then find all others functions that called any of the leave functions either directly or indirectly. Functions that did not call a leave function (directly or indirectly) would not be included in the list of functions to optimize. Reimplement `get_call_order_po/2` to use the standard algorithm for constructing a list of nodes in reverse postorder and then reverse that list.
-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.