aboutsummaryrefslogtreecommitdiffstats
path: root/lib
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 /lib
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.
Diffstat (limited to 'lib')
-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).