aboutsummaryrefslogtreecommitdiffstats
path: root/lib/dialyzer/src
diff options
context:
space:
mode:
authorHans Bolinder <[email protected]>2017-01-19 16:22:06 +0100
committerHans Bolinder <[email protected]>2017-02-03 08:58:00 +0100
commitda2a7ff4d340db6d139c3c6abdcfa978dcadb4c2 (patch)
tree7e67f452859ad8027e8fc5fb865b01a7ebfc45c6 /lib/dialyzer/src
parent643b7dbdb7f208ff69265b4f6b14f79175865c2b (diff)
downloadotp-da2a7ff4d340db6d139c3c6abdcfa978dcadb4c2.tar.gz
otp-da2a7ff4d340db6d139c3c6abdcfa978dcadb4c2.tar.bz2
otp-da2a7ff4d340db6d139c3c6abdcfa978dcadb4c2.zip
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.
Diffstat (limited to 'lib/dialyzer/src')
-rw-r--r--lib/dialyzer/src/dialyzer_callgraph.erl79
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.