From 075164d2fd2eec46a82bd0bf71923cf4a91e3b3a Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 14 Feb 2019 15:25:16 +0100
Subject: 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.
---
 lib/compiler/src/beam_ssa_opt.erl | 43 +++++++++++++++++----------------------
 1 file changed, 19 insertions(+), 24 deletions(-)

(limited to 'lib/compiler/src')

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.
-- 
cgit v1.2.3