From da2a7ff4d340db6d139c3c6abdcfa978dcadb4c2 Mon Sep 17 00:00:00 2001
From: Hans Bolinder <hasse@erlang.org>
Date: Thu, 19 Jan 2017 16:22:06 +0100
Subject: dialyzer: Sort graphs topologically

Although some variable names indicate that lists of SCCs and modules
are sorted, that was not always the case. The effect on the execution
time of sorting them doesn't seem to be significant.

dialyzer_coordinator:sccs_to_pids() should now always return an empty
second list (not yet started workers).

Since the condensation of graphs often needs a lot of heap memory, it
is run in a separate process.
---
 lib/dialyzer/src/dialyzer_callgraph.erl | 79 ++++++++++++++++++++++-----------
 1 file changed, 53 insertions(+), 26 deletions(-)

diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl
index 8f6a3b99b3..27249440e9 100644
--- a/lib/dialyzer/src/dialyzer_callgraph.erl
+++ b/lib/dialyzer/src/dialyzer_callgraph.erl
@@ -287,7 +287,9 @@ module_postorder(#callgraph{digraph = DG}) ->
   digraph_confirm_vertices(sets:to_list(Nodes), MDG),
   Foreach = fun({M1,M2}) -> _ = digraph:add_edge(MDG, M1, M2) end,
   lists:foreach(Foreach, sets:to_list(Edges)),
-  {digraph_utils:topsort(MDG), {'d', MDG}}.
+  %% The out-neighbors of a vertex are the vertices called directly.
+  %% The used vertices are to occur *before* the calling vertex:
+  {lists:reverse(digraph_utils:topsort(MDG)), {'d', MDG}}.
 
 edge_fold({{M1,_,_},{M2,_,_}}, Set) ->
   case M1 =/= M2 of
@@ -774,28 +776,53 @@ to_ps(#callgraph{} = CG, File, Args) ->
   ok.
 
 condensation(G) ->
-  SCCs = digraph_utils:strong_components(G),
-  %% Assign unique numbers to SCCs:
-  Ints = lists:seq(1, length(SCCs)),
-  IntToSCC = lists:zip(Ints, SCCs),
-  IntScc = sofs:relation(IntToSCC, [{int, scc}]),
-  %% Subsitute strong components for vertices in edges using the
-  %% unique numbers:
-  C2V = sofs:relation([{SC, V} || SC <- SCCs, V <- SC], [{scc, v}]),
-  I2V = sofs:relative_product(IntScc, C2V), % [{v, int}]
-  Es = sofs:relation(digraph:edges(G), [{v, v}]),
-  R1 = sofs:relative_product(I2V, Es),
-  R2 = sofs:relative_product(I2V, sofs:converse(R1)),
-  %% Create in- and out-neighbours:
-  In = sofs:relation_to_family(sofs:strict_relation(R2)),
-  R3 = sofs:converse(R2),
-  Out = sofs:relation_to_family(sofs:strict_relation(R3)),
-  [OutETS, InETS, MapsETS] =
-    [ets:new(Name,[{read_concurrency, true}]) ||
-      Name <- [callgraph_deps_out, callgraph_deps_in, callgraph_scc_map]],
-  ets:insert(OutETS, sofs:to_external(Out)),
-  ets:insert(InETS, sofs:to_external(In)),
-  %% Create mappings from SCCs to unique integers, and the inverse:
-  ets:insert(MapsETS, lists:zip([{'scc', SCC} || SCC<- SCCs], Ints)),
-  ets:insert(MapsETS, IntToSCC),
-  {{'e', OutETS, InETS, MapsETS}, SCCs}.
+  erlang:garbage_collect(), % reduce heap size
+  {Pid, Ref} = erlang:spawn_monitor(do_condensation(G, self())),
+  receive {'DOWN', Ref, process, Pid, Result} ->
+      {SCCInts, OutETS, InETS, MapsETS} = Result,
+      NewSCCs = [ets:lookup_element(MapsETS, SCCInt, 2) || SCCInt <- SCCInts],
+      {{'e', OutETS, InETS, MapsETS}, NewSCCs}
+  end.
+
+-spec do_condensation(digraph:graph(), pid()) -> fun(() -> no_return()).
+
+do_condensation(G, Parent) ->
+  fun() ->
+      [OutETS, InETS, MapsETS] =
+        [ets:new(Name,[{read_concurrency, true}]) ||
+          Name <- [callgraph_deps_out, callgraph_deps_in, callgraph_scc_map]],
+      SCCs = digraph_utils:strong_components(G),
+      %% Assign unique numbers to SCCs:
+      Ints = lists:seq(1, length(SCCs)),
+      IntToSCC = lists:zip(Ints, SCCs),
+      IntScc = sofs:relation(IntToSCC, [{int, scc}]),
+      %% Create mapping from unique integers to SCCs:
+      ets:insert(MapsETS, IntToSCC),
+      %% Subsitute strong components for vertices in edges using the
+      %% unique numbers:
+      C2V = sofs:relation([{SC, V} || SC <- SCCs, V <- SC], [{scc, v}]),
+      I2V = sofs:relative_product(IntScc, C2V), % [{v, int}]
+      Es = sofs:relation(digraph:edges(G), [{v, v}]),
+      R1 = sofs:relative_product(I2V, Es),
+      R2 = sofs:relative_product(I2V, sofs:converse(R1)),
+      R2Strict = sofs:strict_relation(R2),
+      %% Create out-neighbours:
+      Out = sofs:relation_to_family(sofs:converse(R2Strict)),
+      ets:insert(OutETS, sofs:to_external(Out)),
+      %% Sort the SCCs topologically:
+      DG = sofs:family_to_digraph(Out),
+      lists:foreach(fun(I) -> digraph:add_vertex(DG, I) end, Ints),
+      SCCInts0 = digraph_utils:topsort(DG),
+      digraph:delete(DG),
+      %% The out-neighbors of a vertex are the vertices called directly.
+      %% The used vertices are to occur *before* the calling vertex:
+      SCCInts = lists:reverse(SCCInts0),
+      %% Create in-neighbours:
+      In = sofs:relation_to_family(R2Strict),
+      ets:insert(InETS, sofs:to_external(In)),
+      %% Create mapping from SCCs to unique integers:
+      ets:insert(MapsETS, lists:zip([{'scc', SCC} || SCC<- SCCs], Ints)),
+      lists:foreach(fun(E) -> true = ets:give_away(E, Parent, any)
+                    end, [OutETS, InETS, MapsETS]),
+      exit({SCCInts, OutETS, InETS, MapsETS})
+  end.
-- 
cgit v1.2.3