From 3c6dbbeb252247ef97cad93921deb4c6e313f11b Mon Sep 17 00:00:00 2001
From: Hans Bolinder <hasse@erlang.org>
Date: Tue, 20 Dec 2016 11:36:52 +0100
Subject: dialyzer: Reduce ETS usage during the typesig phase

The condensed graph of SCCs occupies less ETS memory. A table
translating to and from SCC to a unique integer is introduced.
---
 lib/dialyzer/src/dialyzer_callgraph.erl | 63 +++++++++++++++++++++------------
 1 file changed, 41 insertions(+), 22 deletions(-)

diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl
index 724628d747..5e02e7a2cc 100644
--- a/lib/dialyzer/src/dialyzer_callgraph.erl
+++ b/lib/dialyzer/src/dialyzer_callgraph.erl
@@ -119,7 +119,11 @@
 
 -opaque callgraph() :: #callgraph{}.
 
--type active_digraph() :: {'d', digraph:graph()} | {'e', ets:tid(), ets:tid()}.
+-type active_digraph() :: {'d', digraph:graph()}
+                        | {'e',
+                           Out :: ets:tid(),
+                           In :: ets:tid(),
+                           Map :: ets:tid()}.
 
 %%----------------------------------------------------------------------
 
@@ -248,24 +252,30 @@ find_non_local_calls([], Set) ->
 
 -spec get_depends_on(scc() | module(), callgraph()) -> [scc()].
 
-get_depends_on(SCC, #callgraph{active_digraph = {'e', Out, _In}}) ->
-  case ets_lookup_dict(SCC, Out) of
-    {ok, Value} -> Value;
-    error -> []
-  end;
+get_depends_on(SCC, #callgraph{active_digraph = {'e', Out, _In, Maps}}) ->
+  lookup_scc(SCC, Out, Maps);
 get_depends_on(SCC, #callgraph{active_digraph = {'d', DG}}) ->
   digraph:out_neighbours(DG, SCC).
 
 -spec get_required_by(scc() | module(), callgraph()) -> [scc()].
 
-get_required_by(SCC, #callgraph{active_digraph = {'e', _Out, In}}) ->
-  case ets_lookup_dict(SCC, In) of
-    {ok, Value} -> Value;
-    error -> []
-  end;
+get_required_by(SCC, #callgraph{active_digraph = {'e', _Out, In, Maps}}) ->
+  lookup_scc(SCC, In, Maps);
 get_required_by(SCC, #callgraph{active_digraph = {'d', DG}}) ->
   digraph:in_neighbours(DG, SCC).
 
+lookup_scc(SCC, Table, Maps) ->
+  case ets_lookup_dict({'scc', SCC}, Maps) of
+    {ok, SCCInt} ->
+      case ets_lookup_dict(SCCInt, Table) of
+        {ok, Ints} ->
+          [ets:lookup_element(Maps, Int, 2) || Int <- Ints];
+        error ->
+          []
+      end;
+    error -> []
+  end.
+
 %%----------------------------------------------------------------------
 %% Handling of modules & SCCs
 %%----------------------------------------------------------------------
@@ -582,9 +592,10 @@ digraph_delete(DG) ->
 
 active_digraph_delete({'d', DG}) ->
   digraph:delete(DG);
-active_digraph_delete({'e', Out, In}) ->
+active_digraph_delete({'e', Out, In, Maps}) ->
   ets:delete(Out),
-  ets:delete(In).
+  ets:delete(In),
+  ets:delete(Maps).
 
 digraph_edges(DG) ->
   digraph:edges(DG).
@@ -758,20 +769,28 @@ to_ps(#callgraph{} = CG, File, Args) ->
   ok.
 
 condensation(G) ->
-  SCs = digraph_utils:strong_components(G),
-  %% Subsitute strong components for vertices in edges:
-  C2V = sofs:relation([{SC, V} || SC <- SCs, V <- SC], [{scc, v}]),
+  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(C2V, Es),
-  R2 = sofs:relative_product(C2V, sofs:converse(R1)),
+  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] =
+  [OutETS, InETS, MapsETS] =
     [ets:new(Name,[{read_concurrency, true}]) ||
-      Name <- [callgraph_deps_out, callgraph_deps_in]],
+      Name <- [callgraph_deps_out, callgraph_deps_in, callgraph_scc_map]],
   ets:insert(OutETS, sofs:to_external(Out)),
   ets:insert(InETS, sofs:to_external(In)),
-  erlang:garbage_collect(),
-  {{'e', OutETS, InETS}, SCs}.
+  %% 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}.
-- 
cgit v1.2.3