diff options
author | Hans Bolinder <[email protected]> | 2016-12-20 11:36:52 +0100 |
---|---|---|
committer | Hans Bolinder <[email protected]> | 2017-01-11 09:34:58 +0100 |
commit | 3c6dbbeb252247ef97cad93921deb4c6e313f11b (patch) | |
tree | 6353e4292b543f2f2d695bc47ade6f5c30d4a303 /lib/dialyzer/src/dialyzer_callgraph.erl | |
parent | c87ddb41318396a0d3acc44be13f9258d57b96f3 (diff) | |
download | otp-3c6dbbeb252247ef97cad93921deb4c6e313f11b.tar.gz otp-3c6dbbeb252247ef97cad93921deb4c6e313f11b.tar.bz2 otp-3c6dbbeb252247ef97cad93921deb4c6e313f11b.zip |
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.
Diffstat (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl')
-rw-r--r-- | lib/dialyzer/src/dialyzer_callgraph.erl | 63 |
1 files 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}. |