diff options
| -rw-r--r-- | lib/dialyzer/src/dialyzer_callgraph.erl | 79 |
1 files 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. |