aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorStavros Aronis <[email protected]>2012-02-15 15:47:46 +0100
committerHenrik Nord <[email protected]>2012-05-21 15:31:16 +0200
commit130465c94d6c56e97dab1c1880435e68e57759c7 (patch)
treebf420449b53017d3aad59ec94416bca2e6ff7a35
parentbceee0662a9f6aac6b0987517498bff2ade144df (diff)
downloadotp-130465c94d6c56e97dab1c1880435e68e57759c7.tar.gz
otp-130465c94d6c56e97dab1c1880435e68e57759c7.tar.bz2
otp-130465c94d6c56e97dab1c1880435e68e57759c7.zip
Flatten order of dataflow analyses
Dataflow analysis was structured to find SCCs of modules, without making any use of the information that these were indeed SCCs.
-rw-r--r--lib/dialyzer/src/dialyzer_callgraph.erl49
-rw-r--r--lib/dialyzer/src/dialyzer_succ_typings.erl31
2 files changed, 19 insertions, 61 deletions
diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl
index effd619bde..13eb9418dc 100644
--- a/lib/dialyzer/src/dialyzer_callgraph.erl
+++ b/lib/dialyzer/src/dialyzer_callgraph.erl
@@ -238,33 +238,30 @@ renew_race_info(CG, RaceCode, PublicTables, NamedTables) ->
modules(#callgraph{digraph = DG}) ->
ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]).
--spec module_postorder(callgraph()) -> [[module()]].
+-spec module_postorder(callgraph()) -> [module()].
module_postorder(#callgraph{digraph = DG}) ->
- {MDG, _Nodes} = get_module_digraph_and_nodes(DG),
- MDG1 = digraph_utils:condensation(MDG),
- PostOrder = digraph_utils:postorder(MDG1),
- PostOrder1 = sort_sccs_internally(PostOrder, MDG),
- digraph:delete(MDG1),
- digraph_delete(MDG),
- PostOrder1.
-
-get_module_digraph_and_nodes(DG) ->
Edges = digraph_edges(DG),
Nodes = ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]),
- MDG = digraph:new(),
- MDG = digraph_confirm_vertices(Nodes, MDG),
- MDG = create_module_digraph(Edges, MDG),
- {MDG, Nodes}.
+ MDG = digraph:new([acyclic]),
+ MDG1 = digraph_confirm_vertices(Nodes, MDG),
+ MDG2 = create_module_digraph(Edges, MDG1),
+ PostOrder = digraph_utils:postorder(MDG2),
+ digraph:delete(MDG2),
+ PostOrder.
%% The module deps of a module are modules that depend on the module
-spec module_deps(callgraph()) -> dict().
module_deps(#callgraph{digraph = DG}) ->
- {MDG, Nodes} = get_module_digraph_and_nodes(DG),
- Deps = [{N, ordsets:from_list(digraph:in_neighbours(MDG, N))}
+ Edges = digraph_edges(DG),
+ Nodes = ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]),
+ MDG = digraph:new(),
+ MDG1 = digraph_confirm_vertices(Nodes, MDG),
+ MDG2 = create_module_digraph(Edges, MDG1),
+ Deps = [{N, ordsets:from_list(digraph:in_neighbours(MDG2, N))}
|| N <- Nodes],
- digraph_delete(MDG),
+ digraph_delete(MDG2),
dict:from_list(Deps).
-spec strip_module_deps(dict(), set()) -> dict().
@@ -276,22 +273,6 @@ strip_module_deps(ModDeps, StripSet) ->
FilterFun2 = fun(_Key, ValSet) -> ValSet =/= [] end,
dict:filter(FilterFun2, ModDeps1).
-sort_sccs_internally(PO, MDG) ->
- sort_sccs_internally(PO, MDG, []).
-
-sort_sccs_internally([SCC|SCCs], MDG, Acc) ->
- case SCC of
- [_, _, _ | _] -> % length(SCC) >= 3
- TmpDG = digraph_utils:subgraph(MDG, SCC),
- NewSCC = digraph_utils:postorder(TmpDG),
- digraph_delete(TmpDG),
- sort_sccs_internally(SCCs, MDG, [NewSCC|Acc]);
- _ ->
- sort_sccs_internally(SCCs, MDG, [SCC|Acc])
- end;
-sort_sccs_internally([], _MDG, Acc) ->
- lists:reverse(Acc).
-
create_module_digraph([{{M, _, _}, {M, _, _}}|Left], MDG) ->
create_module_digraph(Left, MDG);
create_module_digraph([{{M1, _, _}, {M2, _, _}}|Left], MDG) ->
@@ -314,7 +295,7 @@ reset_from_funs(Funs, #callgraph{digraph = DG} = CG) ->
digraph_delete(SubGraph),
CG#callgraph{postorder = Postorder}.
--spec module_postorder_from_funs([mfa_or_funlbl()], callgraph()) -> [[module()]].
+-spec module_postorder_from_funs([mfa_or_funlbl()], callgraph()) -> [module()].
module_postorder_from_funs(Funs, #callgraph{digraph = DG} = CG) ->
SubGraph = digraph_reaching_subgraph(Funs, DG),
diff --git a/lib/dialyzer/src/dialyzer_succ_typings.erl b/lib/dialyzer/src/dialyzer_succ_typings.erl
index 5982603b7b..2c2c39951c 100644
--- a/lib/dialyzer/src/dialyzer_succ_typings.erl
+++ b/lib/dialyzer/src/dialyzer_succ_typings.erl
@@ -181,17 +181,13 @@ refine_succ_typings(ModulePostorder, State) ->
?debug("Module postorder: ~p\n", [ModulePostorder]),
refine_succ_typings(ModulePostorder, State, []).
-refine_succ_typings([SCC|SCCs], State, Fixpoint) ->
- Msg = io_lib:format("Dataflow of one SCC: ~w\n", [SCC]),
+refine_succ_typings([M|Rest], State, Fixpoint) ->
+ Msg = io_lib:format("Dataflow of module: ~w\n", [M]),
send_log(State#st.parent, Msg),
?debug("~s\n", [Msg]),
- {NewState, FixpointFromScc} =
- case SCC of
- [M] -> refine_one_module(M, State);
- [_|_] -> refine_one_scc(SCC, State)
- end,
+ {NewState, FixpointFromScc} = refine_one_module(M, State),
NewFixpoint = ordsets:union(Fixpoint, FixpointFromScc),
- refine_succ_typings(SCCs, NewState, NewFixpoint);
+ refine_succ_typings(Rest, NewState, NewFixpoint);
refine_succ_typings([], State, Fixpoint) ->
case Fixpoint =:= [] of
true -> {fixpoint, State};
@@ -225,25 +221,6 @@ refine_one_module(M, State) ->
st__renew_state_calls(Callgraph, State) ->
State#st{callgraph = Callgraph}.
-refine_one_scc(SCC, State) ->
- refine_one_scc(SCC, State, []).
-
-refine_one_scc(SCC, State, AccFixpoint) ->
- {NewState, FixpointFromScc} = refine_mods_in_scc(SCC, State, []),
- case FixpointFromScc =:= [] of
- true -> {NewState, AccFixpoint};
- false ->
- NewAccFixpoint = ordsets:union(AccFixpoint, FixpointFromScc),
- refine_one_scc(SCC, NewState, NewAccFixpoint)
- end.
-
-refine_mods_in_scc([Mod|Mods], State, Fixpoint) ->
- {NewState, FixpointFromModule} = refine_one_module(Mod, State),
- NewFixpoint = ordsets:union(FixpointFromModule, Fixpoint),
- refine_mods_in_scc(Mods, NewState, NewFixpoint);
-refine_mods_in_scc([], State, Fixpoint) ->
- {State, Fixpoint}.
-
reached_fixpoint(OldTypes, NewTypes) ->
reached_fixpoint(OldTypes, NewTypes, false).