From 130465c94d6c56e97dab1c1880435e68e57759c7 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Wed, 15 Feb 2012 15:47:46 +0100 Subject: 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. --- lib/dialyzer/src/dialyzer_callgraph.erl | 49 ++++++++++----------------------- 1 file changed, 15 insertions(+), 34 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') 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), -- cgit v1.2.3 From b45b7e76502cb2df55bec392c5d6badfecd997ca Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Sun, 12 Feb 2012 19:41:27 +0100 Subject: Simplify typesig postorder calculation As the storing in the codeserver is organized per function there is no need for fancy code to make use of the old caching capabilities. --- lib/dialyzer/src/dialyzer_callgraph.erl | 62 +-------------------------------- 1 file changed, 1 insertion(+), 61 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 13eb9418dc..2a01b0f753 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -515,68 +515,8 @@ digraph_in_neighbours(V, DG) -> List -> List end. -%% Pick all the independent nodes (leaves) from one module. Then try -%% to stay within the module until no more independent nodes can be -%% chosen. Then pick a new module and so on. -%% -%% Note that an SCC that ranges over more than one module is -%% considered to belong to all modules to make sure that we do not -%% lose any nodes. - digraph_postorder(Digraph) -> - %% Remove all self-edges for SCCs. - Edges = [digraph:edge(Digraph, E) || E <- digraph:edges(Digraph)], - SelfEdges = [E || {E, V, V, _} <- Edges], - true = digraph:del_edges(Digraph, SelfEdges), - %% Determine the first module outside of the loop. - Leaves = digraph_leaves(Digraph), - case Leaves =:= [] of - true -> []; - false -> - {Module, Taken} = take_sccs_from_fresh_module(Leaves), - true = digraph:del_vertices(Digraph, Taken), - digraph_postorder(Digraph, Module, [Taken]) - end. - -digraph_postorder(Digraph, LastModule, Acc) -> - Leaves = digraph_leaves(Digraph), - case Leaves =:= [] of - true -> lists:append(lists:reverse(Acc)); - false -> - case [SCC || SCC <- Leaves, scc_belongs_to_module(SCC, LastModule)] of - [] -> - {NewModule, NewTaken} = take_sccs_from_fresh_module(Leaves), - true = digraph:del_vertices(Digraph, NewTaken), - digraph_postorder(Digraph, NewModule, [NewTaken|Acc]); - NewTaken -> - true = digraph:del_vertices(Digraph, NewTaken), - digraph_postorder(Digraph, LastModule, [NewTaken|Acc]) - end - end. - -digraph_leaves(Digraph) -> - [V || V <- digraph:vertices(Digraph), digraph:out_degree(Digraph, V) =:= 0]. - -take_sccs_from_fresh_module(Leaves) -> - NewModule = find_module(hd(Leaves)), - {NewModule, - [SCC || SCC <- Leaves, scc_belongs_to_module(SCC, NewModule)]}. - --spec scc_belongs_to_module(scc(), module()) -> boolean(). - -scc_belongs_to_module([Label|Left], Module) when is_integer(Label) -> - scc_belongs_to_module(Left, Module); -scc_belongs_to_module([{M, _, _}|Left], Module) -> - if M =:= Module -> true; - true -> scc_belongs_to_module(Left, Module) - end; -scc_belongs_to_module([], _Module) -> - false. - --spec find_module(scc()) -> module(). - -find_module([{M, _, _}|_]) -> M; -find_module([Label|Left]) when is_integer(Label) -> find_module(Left). + digraph_utils:postorder(Digraph). digraph_finalize(DG) -> DG1 = digraph_utils:condensation(DG), -- cgit v1.2.3 From e6fa01359a41d3b054260d01d2880820c867ca2b Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Fri, 10 Feb 2012 14:42:30 +0100 Subject: Parallel typesig analysis --- lib/dialyzer/src/dialyzer_callgraph.erl | 140 ++++++++++++++++++++++---------- 1 file changed, 99 insertions(+), 41 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 2a01b0f753..1cbb83a44a 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -43,12 +43,14 @@ %% module_postorder/1, module_postorder_from_funs/2, new/0, + mini_callgraph/1, + get_depends_on/2, + get_required_by/2, in_neighbours/2, renew_race_info/4, reset_from_funs/2, scan_core_tree/2, strip_module_deps/2, - take_scc/1, remove_external/1, to_dot/2, to_ps/3]). @@ -65,7 +67,6 @@ %%---------------------------------------------------------------------- --type mfa_or_funlbl() :: label() | mfa(). -type scc() :: [mfa_or_funlbl()]. -type mfa_calls() :: [{mfa_or_funlbl(), mfa_or_funlbl()}]. @@ -78,9 +79,6 @@ %% digraph - A digraph representing the callgraph. %% Nodes are represented as MFAs or labels. %% esc - A set of all escaping functions as reported by dialyzer_dep. -%% postorder - A list of strongly connected components of the callgraph -%% sorted in a topological bottom-up order. -%% This is produced by calling finalize/1. %% name_map - A mapping from label to MFA. %% rev_name_map - A reverse mapping of the name_map. %% rec_var_map - A dict mapping from letrec bound labels to function names. @@ -91,13 +89,13 @@ %%----------------------------------------------------------------------------- -record(callgraph, {digraph = digraph:new() :: digraph(), - esc = sets:new() :: set(), - name_map = dict:new() :: dict(), - rev_name_map = dict:new() :: dict(), - postorder = [] :: [scc()], - rec_var_map = dict:new() :: dict(), - self_rec = sets:new() :: set(), - calls = dict:new() :: dict(), + active_digraph :: digraph(), + esc = sets:new() :: set() | ets:tid(), + name_map = dict:new() :: dict() | ets:tid(), + rev_name_map = dict:new() :: dict() | ets:tid(), + rec_var_map = dict:new() :: dict() | ets:tid(), + self_rec = sets:new() :: set() | ets:tid(), + calls = dict:new() :: dict() | ets:tid(), race_code = dict:new() :: dict(), public_tables = [] :: [label()], named_tables = [] :: [string()], @@ -115,6 +113,25 @@ new() -> #callgraph{}. +-spec mini_callgraph(callgraph()) -> callgraph(). + +mini_callgraph(#callgraph{digraph = Digraph, + active_digraph = ActiveDigraph, + esc = Esc, + name_map = NameMap, + rev_name_map = RevNameMap, + rec_var_map = RecVarMap, + self_rec = SelfRecs, + calls = Calls}) -> + #callgraph{digraph = Digraph, + active_digraph = ActiveDigraph, + esc = Esc, + name_map = NameMap, + rev_name_map = RevNameMap, + rec_var_map = RecVarMap, + self_rec = SelfRecs, + calls = Calls}. + -spec delete(callgraph()) -> 'true'. delete(#callgraph{digraph = Digraph}) -> @@ -129,32 +146,32 @@ all_nodes(#callgraph{digraph = DG}) -> lookup_rec_var(Label, #callgraph{rec_var_map = RecVarMap}) when is_integer(Label) -> - dict:find(Label, RecVarMap). + ets_lookup_dict(Label, RecVarMap). -spec lookup_call_site(label(), callgraph()) -> 'error' | {'ok', [_]}. % XXX: refine lookup_call_site(Label, #callgraph{calls = Calls}) when is_integer(Label) -> - dict:find(Label, Calls). + ets_lookup_dict(Label, Calls). -spec lookup_name(label(), callgraph()) -> 'error' | {'ok', mfa()}. lookup_name(Label, #callgraph{name_map = NameMap}) when is_integer(Label) -> - dict:find(Label, NameMap). + ets_lookup_dict(Label, NameMap). -spec lookup_label(mfa_or_funlbl(), callgraph()) -> 'error' | {'ok', integer()}. lookup_label({_,_,_} = MFA, #callgraph{rev_name_map = RevNameMap}) -> - dict:find(MFA, RevNameMap); + ets_lookup_dict(MFA, RevNameMap); lookup_label(Label, #callgraph{}) when is_integer(Label) -> {ok, Label}. -spec in_neighbours(mfa_or_funlbl(), callgraph()) -> 'none' | [mfa_or_funlbl(),...]. -in_neighbours(Label, #callgraph{digraph = Digraph, name_map = NameMap}) +in_neighbours(Label, #callgraph{digraph = Digraph} = CG) when is_integer(Label) -> - Name = case dict:find(Label, NameMap) of + Name = case lookup_name(Label, CG) of {ok, Val} -> Val; error -> Label end, @@ -165,12 +182,12 @@ in_neighbours({_, _, _} = MFA, #callgraph{digraph = Digraph}) -> -spec is_self_rec(mfa_or_funlbl(), callgraph()) -> boolean(). is_self_rec(MfaOrLabel, #callgraph{self_rec = SelfRecs}) -> - sets:is_element(MfaOrLabel, SelfRecs). + ets_lookup_set(MfaOrLabel, SelfRecs). -spec is_escaping(label(), callgraph()) -> boolean(). is_escaping(Label, #callgraph{esc = Esc}) when is_integer(Label) -> - sets:is_element(Label, Esc). + ets_lookup_set(Label, Esc). -type callgraph_edge() :: {mfa_or_funlbl(),mfa_or_funlbl()}. -spec add_edges([callgraph_edge()], callgraph()) -> callgraph(). @@ -186,13 +203,6 @@ add_edges(Edges, MFAs, #callgraph{digraph = DG} = CG) -> DG = digraph_confirm_vertices(MFAs, DG), add_edges(Edges, CG). --spec take_scc(callgraph()) -> 'none' | {'ok', scc(), callgraph()}. - -take_scc(#callgraph{postorder = [SCC|SCCs]} = CG) -> - {ok, SCC, CG#callgraph{postorder = SCCs}}; -take_scc(#callgraph{postorder = []}) -> - none. - -spec remove_external(callgraph()) -> {callgraph(), [tuple()]}. remove_external(#callgraph{digraph = DG} = CG) -> @@ -229,6 +239,16 @@ renew_race_info(CG, RaceCode, PublicTables, NamedTables) -> public_tables = PublicTables, named_tables = NamedTables}. +-spec get_depends_on(scc(), callgraph()) -> [scc()]. + +get_depends_on(SCC, #callgraph{active_digraph = DG}) -> + digraph:out_neighbours(DG, SCC). + +-spec get_required_by(scc(), callgraph()) -> [scc()]. + +get_required_by(SCC, #callgraph{active_digraph = DG}) -> + digraph:in_neighbours(DG, SCC). + %%---------------------------------------------------------------------- %% Handling of modules & SCCs %%---------------------------------------------------------------------- @@ -282,18 +302,44 @@ create_module_digraph([{_, _}|Left], MDG) -> create_module_digraph([], MDG) -> MDG. --spec finalize(callgraph()) -> callgraph(). - -finalize(#callgraph{digraph = DG} = CG) -> - CG#callgraph{postorder = digraph_finalize(DG)}. - --spec reset_from_funs([mfa_or_funlbl()], callgraph()) -> callgraph(). - -reset_from_funs(Funs, #callgraph{digraph = DG} = CG) -> +-spec finalize(callgraph()) -> {[scc()], callgraph()}. + +finalize(#callgraph{digraph = DG, + esc = Esc, + name_map = NameMap, + rev_name_map = RevNameMap, + rec_var_map = RecVarMap, + self_rec = SelfRec, + calls = Calls + } = CG) -> + [ETSEsc, ETSNameMap, ETSRevNameMap, ETSRecVarMap, ETSSelfRec, ETSCalls] = + [ets:new(N,[public]) || + N <- [callgraph_esc, callgraph_name_map, callgraph_rev_name_map, + callgraph_rec_var_map, callgraph_self_rec, callgraph_calls]], + [true,true] = [ets:insert(ETS, [{E} || E <- sets:to_list(Data)]) || + {ETS, Data} <- [{ETSEsc, Esc}, {ETSSelfRec, SelfRec}]], + [true, true, true, true] = + [ets:insert(ETS, dict:to_list(Data)) || + {ETS, Data} <- [{ETSNameMap, NameMap}, {ETSRevNameMap, RevNameMap}, + {ETSRecVarMap, RecVarMap}, {ETSCalls, Calls}]], + {ActiveDG, Postorder} = digraph_finalize(DG), + {Postorder, CG#callgraph{active_digraph = ActiveDG, + esc = ETSEsc, + name_map = ETSNameMap, + rev_name_map = ETSRevNameMap, + rec_var_map = ETSRecVarMap, + self_rec = ETSSelfRec, + calls = ETSCalls}}. + +-spec reset_from_funs([mfa_or_funlbl()], callgraph()) -> {[scc()], callgraph()}. + +reset_from_funs(Funs, #callgraph{digraph = DG, + active_digraph = OldActiveDG} = CG) -> + digraph_delete(OldActiveDG), SubGraph = digraph_reaching_subgraph(Funs, DG), - Postorder = digraph_finalize(SubGraph), + {NewActiveDG, Postorder} = digraph_finalize(SubGraph), digraph_delete(SubGraph), - CG#callgraph{postorder = Postorder}. + {Postorder, CG#callgraph{active_digraph = NewActiveDG}}. -spec module_postorder_from_funs([mfa_or_funlbl()], callgraph()) -> [module()]. @@ -302,7 +348,20 @@ module_postorder_from_funs(Funs, #callgraph{digraph = DG} = CG) -> PO = module_postorder(CG#callgraph{digraph = SubGraph}), digraph_delete(SubGraph), PO. - + +ets_lookup_dict(Key, Table) -> + try ets:lookup_element(Table, Key, 2) of + Val -> {ok, Val} + catch + _:_ -> error + end. + +ets_lookup_set(Key, Table) -> + case ets:lookup(Table, Key) of + [] -> false; + _ -> true + end. + %%---------------------------------------------------------------------- %% Core code %%---------------------------------------------------------------------- @@ -516,13 +575,12 @@ digraph_in_neighbours(V, DG) -> end. digraph_postorder(Digraph) -> - digraph_utils:postorder(Digraph). + digraph_utils:topsort(Digraph). digraph_finalize(DG) -> DG1 = digraph_utils:condensation(DG), Postorder = digraph_postorder(DG1), - digraph:delete(DG1), - Postorder. + {DG1, Postorder}. digraph_reaching_subgraph(Funs, DG) -> Vertices = digraph_utils:reaching(Funs, DG), -- cgit v1.2.3 From ffadf7f6f8a113fbcc42a2be36d2dd5c841d48e3 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Thu, 16 Feb 2012 16:03:51 +0100 Subject: Moving code between callgraph & dataflow --- lib/dialyzer/src/dialyzer_callgraph.erl | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 1cbb83a44a..ddda27adb4 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -48,6 +48,7 @@ get_required_by/2, in_neighbours/2, renew_race_info/4, + renew_race_code/2, reset_from_funs/2, scan_core_tree/2, strip_module_deps/2, @@ -239,6 +240,14 @@ renew_race_info(CG, RaceCode, PublicTables, NamedTables) -> public_tables = PublicTables, named_tables = NamedTables}. +-spec renew_race_code(dialyzer_races:races(), callgraph()) -> callgraph(). + +renew_race_code(Races, #callgraph{race_code = RaceCode} = Callgraph) -> + Fun = dialyzer_races:get_curr_fun(Races), + FunArgs = dialyzer_races:get_curr_fun_args(Races), + Code = lists:reverse(dialyzer_races:get_race_list(Races)), + Callgraph#callgraph{race_code = dict:store(Fun, [FunArgs, Code], RaceCode)}. + -spec get_depends_on(scc(), callgraph()) -> [scc()]. get_depends_on(SCC, #callgraph{active_digraph = DG}) -> -- cgit v1.2.3 From 7640a30bbd0a45ccea356bd9f9393c445471cbc4 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Thu, 16 Feb 2012 16:04:43 +0100 Subject: Remove unused race detection related code --- lib/dialyzer/src/dialyzer_callgraph.erl | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index ddda27adb4..fd6bc89e25 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -49,6 +49,7 @@ in_neighbours/2, renew_race_info/4, renew_race_code/2, + renew_race_public_tables/2, reset_from_funs/2, scan_core_tree/2, strip_module_deps/2, @@ -248,6 +249,11 @@ renew_race_code(Races, #callgraph{race_code = RaceCode} = Callgraph) -> Code = lists:reverse(dialyzer_races:get_race_list(Races)), Callgraph#callgraph{race_code = dict:store(Fun, [FunArgs, Code], RaceCode)}. +-spec renew_race_public_tables(label(), callgraph()) -> callgraph(). + +renew_race_public_tables(VarLabel, #callgraph{public_tables = PT} = CG) -> + CG#callgraph{public_tables = ordsets:add_element(VarLabel, PT)}. + -spec get_depends_on(scc(), callgraph()) -> [scc()]. get_depends_on(SCC, #callgraph{active_digraph = DG}) -> -- cgit v1.2.3 From b8e96486af6b63c20cefd8af788a8e275a9d8e53 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Fri, 17 Feb 2012 17:18:47 +0100 Subject: Separate race related fields of callgraph --- lib/dialyzer/src/dialyzer_callgraph.erl | 216 ++++++++++++++++++++++---------- 1 file changed, 153 insertions(+), 63 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index fd6bc89e25..7379fbc3c4 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -61,7 +61,7 @@ get_race_code/1, get_race_detection/1, race_code_new/1, put_digraph/2, put_race_code/2, put_race_detection/2, put_named_tables/2, put_public_tables/2, put_behaviour_api_calls/2, - get_behaviour_api_calls/1]). + get_behaviour_api_calls/1, dispose_race_server/1, duplicate/1]). -export_type([callgraph/0, mfa_or_funlbl/0]). @@ -98,11 +98,13 @@ rec_var_map = dict:new() :: dict() | ets:tid(), self_rec = sets:new() :: set() | ets:tid(), calls = dict:new() :: dict() | ets:tid(), - race_code = dict:new() :: dict(), - public_tables = [] :: [label()], - named_tables = [] :: [string()], race_detection = false :: boolean(), - beh_api_calls = [] :: [{mfa(), mfa()}]}). + race_data_server = new_race_data_server() :: pid()}). + +-record(race_data_state, {race_code = dict:new() :: dict(), + public_tables = [] :: [label()], + named_tables = [] :: [string()], + beh_api_calls = [] :: [{mfa(), mfa()}]}). %% Exported Types @@ -233,27 +235,6 @@ find_non_local_calls([{Label1, Label2}|Left], Set) when is_integer(Label1), find_non_local_calls([], Set) -> sets:to_list(Set). --spec renew_race_info(callgraph(), dict(), [label()], [string()]) -> - callgraph(). - -renew_race_info(CG, RaceCode, PublicTables, NamedTables) -> - CG#callgraph{race_code = RaceCode, - public_tables = PublicTables, - named_tables = NamedTables}. - --spec renew_race_code(dialyzer_races:races(), callgraph()) -> callgraph(). - -renew_race_code(Races, #callgraph{race_code = RaceCode} = Callgraph) -> - Fun = dialyzer_races:get_curr_fun(Races), - FunArgs = dialyzer_races:get_curr_fun_args(Races), - Code = lists:reverse(dialyzer_races:get_race_list(Races)), - Callgraph#callgraph{race_code = dict:store(Fun, [FunArgs, Code], RaceCode)}. - --spec renew_race_public_tables(label(), callgraph()) -> callgraph(). - -renew_race_public_tables(VarLabel, #callgraph{public_tables = PT} = CG) -> - CG#callgraph{public_tables = ordsets:add_element(VarLabel, PT)}. - -spec get_depends_on(scc(), callgraph()) -> [scc()]. get_depends_on(SCC, #callgraph{active_digraph = DG}) -> @@ -605,20 +586,68 @@ digraph_reaching_subgraph(Funs, DG) -> %% Races %%---------------------------------------------------------------------- +-spec renew_race_info(callgraph(), dict(), [label()], [string()]) -> + callgraph(). + +renew_race_info(#callgraph{race_data_server = RaceDataServer} = CG, + RaceCode, PublicTables, NamedTables) -> + ok = race_data_server_cast( + {renew_race_info, {RaceCode, PublicTables, NamedTables}}, + RaceDataServer), + CG. + +renew_race_info({RaceCode, PublicTables, NamedTables}, + #race_data_state{} = State) -> + State#race_data_state{race_code = RaceCode, + public_tables = PublicTables, + named_tables = NamedTables}. + +-spec renew_race_code(dialyzer_races:races(), callgraph()) -> callgraph(). + +renew_race_code(Races, #callgraph{race_data_server = RaceDataServer} = CG) -> + Fun = dialyzer_races:get_curr_fun(Races), + FunArgs = dialyzer_races:get_curr_fun_args(Races), + Code = lists:reverse(dialyzer_races:get_race_list(Races)), + ok = race_data_server_cast( + {renew_race_code, {Fun, FunArgs, Code}}, + RaceDataServer), + CG; +renew_race_code({Fun, FunArgs, Code}, + #race_data_state{race_code = RaceCode} = State) -> + State#race_data_state{race_code = dict:store(Fun, [FunArgs, Code], RaceCode)}. + +-spec renew_race_public_tables(label(), callgraph()) -> callgraph(). + +renew_race_public_tables(VarLabel, + #callgraph{race_data_server = RaceDataServer} = CG) -> + ok = + race_data_server_cast({renew_race_public_tables, VarLabel}, RaceDataServer), + CG; +renew_race_public_tables(VarLabel, + #race_data_state{public_tables = PT} = State) -> + State#race_data_state{public_tables = ordsets:add_element(VarLabel, PT)}. + -spec cleanup(callgraph()) -> callgraph(). -cleanup(#callgraph{digraph = Digraph, - name_map = NameMap, - rev_name_map = RevNameMap, - public_tables = PublicTables, - named_tables = NamedTables, - race_code = RaceCode}) -> +cleanup(#callgraph{digraph = Digraph, + name_map = NameMap, + rev_name_map = RevNameMap, + race_data_server = RaceDataServer}) -> #callgraph{digraph = Digraph, - name_map = NameMap, - rev_name_map = RevNameMap, - public_tables = PublicTables, - named_tables = NamedTables, - race_code = RaceCode}. + name_map = NameMap, + rev_name_map = RevNameMap, + race_data_server = race_data_server_call(dup, RaceDataServer)}. + +-spec duplicate(callgraph()) -> callgraph(). + +duplicate(#callgraph{race_data_server = RaceDataServer} = Callgraph) -> + Callgraph#callgraph{ + race_data_server = race_data_server_call(dup, RaceDataServer)}. + +-spec dispose_race_server(callgraph()) -> ok. + +dispose_race_server(#callgraph{race_data_server = RaceDataServer}) -> + race_data_server_cast(stop, RaceDataServer). -spec get_digraph(callgraph()) -> digraph(). @@ -627,28 +656,34 @@ get_digraph(#callgraph{digraph = Digraph}) -> -spec get_named_tables(callgraph()) -> [string()]. -get_named_tables(#callgraph{named_tables = NamedTables}) -> - NamedTables. +get_named_tables(#callgraph{race_data_server = RaceDataServer}) -> + race_data_server_call(get_named_tables, RaceDataServer). -spec get_public_tables(callgraph()) -> [label()]. -get_public_tables(#callgraph{public_tables = PT}) -> - PT. +get_public_tables(#callgraph{race_data_server = RaceDataServer}) -> + race_data_server_call(get_public_tables, RaceDataServer). -spec get_race_code(callgraph()) -> dict(). -get_race_code(#callgraph{race_code = RaceCode}) -> - RaceCode. +get_race_code(#callgraph{race_data_server = RaceDataServer}) -> + race_data_server_call(get_race_code, RaceDataServer). -spec get_race_detection(callgraph()) -> boolean(). get_race_detection(#callgraph{race_detection = RD}) -> RD. +-spec get_behaviour_api_calls(callgraph()) -> [{mfa(), mfa()}]. + +get_behaviour_api_calls(#callgraph{race_data_server = RaceDataServer}) -> + race_data_server_call(get_behaviour_api_calls, RaceDataServer). + -spec race_code_new(callgraph()) -> callgraph(). -race_code_new(Callgraph) -> - Callgraph#callgraph{race_code = dict:new()}. +race_code_new(#callgraph{race_data_server = RaceDataServer} = CG) -> + ok = race_data_server_cast(race_code_new, RaceDataServer), + CG. -spec put_digraph(digraph(), callgraph()) -> callgraph(). @@ -657,8 +692,9 @@ put_digraph(Digraph, Callgraph) -> -spec put_race_code(dict(), callgraph()) -> callgraph(). -put_race_code(RaceCode, Callgraph) -> - Callgraph#callgraph{race_code = RaceCode}. +put_race_code(RaceCode, #callgraph{race_data_server = RaceDataServer} = CG) -> + ok = race_data_server_cast({put_race_code, RaceCode}, RaceDataServer), + CG. -spec put_race_detection(boolean(), callgraph()) -> callgraph(). @@ -667,13 +703,79 @@ put_race_detection(RaceDetection, Callgraph) -> -spec put_named_tables([string()], callgraph()) -> callgraph(). -put_named_tables(NamedTables, Callgraph) -> - Callgraph#callgraph{named_tables = NamedTables}. +put_named_tables(NamedTables, + #callgraph{race_data_server = RaceDataServer} = CG) -> + ok = race_data_server_cast({put_named_tables, NamedTables}, RaceDataServer), + CG. -spec put_public_tables([label()], callgraph()) -> callgraph(). -put_public_tables(PublicTables, Callgraph) -> - Callgraph#callgraph{public_tables = PublicTables}. +put_public_tables(PublicTables, + #callgraph{race_data_server = RaceDataServer} = CG) -> + ok = race_data_server_cast({put_public_tables, PublicTables}, RaceDataServer), + CG. + +-spec put_behaviour_api_calls([{mfa(), mfa()}], callgraph()) -> callgraph(). + +put_behaviour_api_calls(Calls, + #callgraph{race_data_server = RaceDataServer} = CG) -> + ok = race_data_server_cast({put_behaviour_api_calls, Calls}, RaceDataServer), + CG. + + +new_race_data_server() -> + spawn(fun() -> race_data_server_loop(#race_data_state{}) end). + +race_data_server_loop(State) -> + receive + {call, From, Ref, Query} -> + Reply = race_data_server_handle_call(Query, State), + From ! {Ref, Reply}, + race_data_server_loop(State); + {cast, stop} -> + ok; + {cast, Message} -> + NewState = race_data_server_handle_cast(Message, State), + race_data_server_loop(NewState) + end. + +race_data_server_call(Query, Server) -> + Ref = make_ref(), + Server ! {call, self(), Ref, Query}, + receive + {Ref, Reply} -> Reply + end. + +race_data_server_cast(Message, Server) -> + Server ! {cast, Message}, + ok. + +race_data_server_handle_cast(race_code_new, State) -> + State#race_data_state{race_code = dict:new()}; +race_data_server_handle_cast({Tag, Data}, State) -> + case Tag of + renew_race_info -> renew_race_info(Data, State); + renew_race_code -> renew_race_code(Data, State); + renew_race_public_tables -> renew_race_public_tables(Data, State); + put_race_code -> State#race_data_state{race_code = Data}; + put_public_tables -> State#race_data_state{public_tables = Data}; + put_named_tables -> State#race_data_state{named_tables = Data}; + put_behaviour_api_calls -> State#race_data_state{beh_api_calls = Data} + end. + +race_data_server_handle_call(Query, + #race_data_state{race_code = RaceCode, + public_tables = PublicTables, + named_tables = NamedTables, + beh_api_calls = BehApiCalls} + = State) -> + case Query of + dup -> spawn(fun() -> race_data_server_loop(State) end); + get_race_code -> RaceCode; + get_public_tables -> PublicTables; + get_named_tables -> NamedTables; + get_behaviour_api_calls -> BehApiCalls + end. %%============================================================================= %% Utilities for 'dot' @@ -701,15 +803,3 @@ to_ps(#callgraph{} = CG, File, Args) -> Command = io_lib:format("dot -Tps ~s -o ~s ~s", [Args, File, Dot_File]), _ = os:cmd(Command), ok. - -%------------------------------------------------------------------------------- - --spec put_behaviour_api_calls([{mfa(), mfa()}], callgraph()) -> callgraph(). - -put_behaviour_api_calls(Calls, Callgraph) -> - Callgraph#callgraph{beh_api_calls = Calls}. - --spec get_behaviour_api_calls(callgraph()) -> [{mfa(), mfa()}]. - -get_behaviour_api_calls(Callgraph) -> - Callgraph#callgraph.beh_api_calls. -- cgit v1.2.3 From 12c5985b862c5e8e7e88033a21e909b51225d76f Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Fri, 17 Feb 2012 18:47:58 +0100 Subject: Parallel dataflow --- lib/dialyzer/src/dialyzer_callgraph.erl | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 7379fbc3c4..385f5621d6 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -262,9 +262,8 @@ module_postorder(#callgraph{digraph = DG}) -> 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. + PostOrder = digraph_utils:topsort(MDG2), + {PostOrder, MDG2}. %% The module deps of a module are modules that depend on the module -spec module_deps(callgraph()) -> dict(). @@ -341,9 +340,9 @@ reset_from_funs(Funs, #callgraph{digraph = DG, module_postorder_from_funs(Funs, #callgraph{digraph = DG} = CG) -> SubGraph = digraph_reaching_subgraph(Funs, DG), - PO = module_postorder(CG#callgraph{digraph = SubGraph}), + {PO, Active} = module_postorder(CG#callgraph{digraph = SubGraph}), digraph_delete(SubGraph), - PO. + {PO, CG#callgraph{active_digraph = Active}}. ets_lookup_dict(Key, Table) -> try ets:lookup_element(Table, Key, 2) of -- cgit v1.2.3 From af4247993e9b68bd123df37d08b06690c0640259 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Sat, 18 Feb 2012 15:59:08 +0100 Subject: Callgraph is ets based from the start --- lib/dialyzer/src/dialyzer_callgraph.erl | 120 ++++++++++++++------------------ 1 file changed, 52 insertions(+), 68 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 385f5621d6..9eba64dd57 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -92,12 +92,12 @@ -record(callgraph, {digraph = digraph:new() :: digraph(), active_digraph :: digraph(), - esc = sets:new() :: set() | ets:tid(), - name_map = dict:new() :: dict() | ets:tid(), - rev_name_map = dict:new() :: dict() | ets:tid(), - rec_var_map = dict:new() :: dict() | ets:tid(), - self_rec = sets:new() :: set() | ets:tid(), - calls = dict:new() :: dict() | ets:tid(), + esc :: ets:tid(), + name_map :: ets:tid(), + rev_name_map :: ets:tid(), + rec_var_map :: ets:tid(), + self_rec :: ets:tid(), + calls :: ets:tid(), race_detection = false :: boolean(), race_data_server = new_race_data_server() :: pid()}). @@ -115,7 +115,16 @@ -spec new() -> callgraph(). new() -> - #callgraph{}. + [ETSEsc, ETSNameMap, ETSRevNameMap, ETSRecVarMap, ETSSelfRec, ETSCalls] = + [ets:new(N,[public]) || + N <- [callgraph_esc, callgraph_name_map, callgraph_rev_name_map, + callgraph_rec_var_map, callgraph_self_rec, callgraph_calls]], + #callgraph{esc = ETSEsc, + name_map = ETSNameMap, + rev_name_map = ETSRevNameMap, + rec_var_map = ETSRecVarMap, + self_rec = ETSSelfRec, + calls = ETSCalls}. -spec mini_callgraph(callgraph()) -> callgraph(). @@ -299,32 +308,9 @@ create_module_digraph([], MDG) -> -spec finalize(callgraph()) -> {[scc()], callgraph()}. -finalize(#callgraph{digraph = DG, - esc = Esc, - name_map = NameMap, - rev_name_map = RevNameMap, - rec_var_map = RecVarMap, - self_rec = SelfRec, - calls = Calls - } = CG) -> - [ETSEsc, ETSNameMap, ETSRevNameMap, ETSRecVarMap, ETSSelfRec, ETSCalls] = - [ets:new(N,[public]) || - N <- [callgraph_esc, callgraph_name_map, callgraph_rev_name_map, - callgraph_rec_var_map, callgraph_self_rec, callgraph_calls]], - [true,true] = [ets:insert(ETS, [{E} || E <- sets:to_list(Data)]) || - {ETS, Data} <- [{ETSEsc, Esc}, {ETSSelfRec, SelfRec}]], - [true, true, true, true] = - [ets:insert(ETS, dict:to_list(Data)) || - {ETS, Data} <- [{ETSNameMap, NameMap}, {ETSRevNameMap, RevNameMap}, - {ETSRecVarMap, RecVarMap}, {ETSCalls, Calls}]], +finalize(#callgraph{digraph = DG} = CG) -> {ActiveDG, Postorder} = digraph_finalize(DG), - {Postorder, CG#callgraph{active_digraph = ActiveDG, - esc = ETSEsc, - name_map = ETSNameMap, - rev_name_map = ETSRevNameMap, - rec_var_map = ETSRecVarMap, - self_rec = ETSSelfRec, - calls = ETSCalls}}. + {Postorder, CG#callgraph{active_digraph = ActiveDG}}. -spec reset_from_funs([mfa_or_funlbl()], callgraph()) -> {[scc()], callgraph()}. @@ -367,34 +353,34 @@ ets_lookup_set(Key, Table) -> -spec scan_core_tree(cerl:c_module(), callgraph()) -> callgraph(). -scan_core_tree(Tree, #callgraph{calls = OldCalls, - esc = OldEsc, - name_map = OldNameMap, - rec_var_map = OldRecVarMap, - rev_name_map = OldRevNameMap, - self_rec = OldSelfRec} = CG) -> +scan_core_tree(Tree, #callgraph{calls = ETSCalls, + esc = ETSEsc, + name_map = ETSNameMap, + rec_var_map = ETSRecVarMap, + rev_name_map = ETSRevNameMap, + self_rec = ETSSelfRec} = CG) -> %% Build name map and recursion variable maps. - {NewNameMap, NewRevNameMap, NewRecVarMap} = - build_maps(Tree, OldRecVarMap, OldNameMap, OldRevNameMap), + build_maps(Tree, ETSRecVarMap, ETSNameMap, ETSRevNameMap), %% First find the module-local dependencies. {Deps0, EscapingFuns, Calls} = dialyzer_dep:analyze(Tree), - NewCalls = dict:merge(fun(_Key, Val, Val) -> Val end, OldCalls, Calls), - NewEsc = sets:union(sets:from_list(EscapingFuns), OldEsc), + true = ets:insert(ETSCalls, dict:to_list(Calls)), + true = ets:insert(ETSEsc, [{E} || E <- EscapingFuns]), + LabelEdges = get_edges_from_deps(Deps0), %% Find the self recursive functions. Named functions get both the %% key and their name for convenience. SelfRecs0 = lists:foldl(fun({Key, Key}, Acc) -> - case dict:find(Key, NewNameMap) of + case ets_lookup_dict(Key, ETSNameMap) of error -> [Key|Acc]; {ok, Name} -> [Key, Name|Acc] end; (_, Acc) -> Acc end, [], LabelEdges), - SelfRecs = sets:union(sets:from_list(SelfRecs0), OldSelfRec), + true = ets:insert(ETSSelfRec, [{S} || S <- SelfRecs0]), - NamedEdges1 = name_edges(LabelEdges, NewNameMap), + NamedEdges1 = name_edges(LabelEdges, ETSNameMap), %% We need to scan for inter-module calls since these are not tracked %% by dialyzer_dep. Note that the caller is always recorded as the @@ -413,27 +399,25 @@ scan_core_tree(Tree, #callgraph{calls = OldCalls, NewNamedEdges1 = [E || {From, To} = E <- NamedEdges1, From =/= top, To =/= top], NamedEdges3 = NewNamedEdges1 ++ NewNamedEdges2, - CG1 = add_edges(NamedEdges3, Names3, CG), - CG1#callgraph{calls = NewCalls, - esc = NewEsc, - name_map = NewNameMap, - rec_var_map = NewRecVarMap, - rev_name_map = NewRevNameMap, - self_rec = SelfRecs}. - -build_maps(Tree, RecVarMap, NameMap, RevNameMap) -> + add_edges(NamedEdges3, Names3, CG). + +build_maps(Tree, ETSRecVarMap, ETSNameMap, ETSRevNameMap) -> %% We only care about the named (top level) functions. The anonymous %% functions will be analysed together with their parents. Defs = cerl:module_defs(Tree), Mod = cerl:atom_val(cerl:module_name(Tree)), - lists:foldl(fun({Var, Function}, {AccNameMap, AccRevNameMap, AccRecVarMap}) -> - FunName = cerl:fname_id(Var), - Arity = cerl:fname_arity(Var), - MFA = {Mod, FunName, Arity}, - {dict:store(get_label(Function), MFA, AccNameMap), - dict:store(MFA, get_label(Function), AccRevNameMap), - dict:store(get_label(Var), MFA, AccRecVarMap)} - end, {NameMap, RevNameMap, RecVarMap}, Defs). + Fun = + fun({Var, Function}) -> + FunName = cerl:fname_id(Var), + Arity = cerl:fname_arity(Var), + MFA = {Mod, FunName, Arity}, + FunLabel = get_label(Function), + VarLabel = get_label(Var), + true = ets:insert(ETSNameMap, {FunLabel, MFA}), + true = ets:insert(ETSRevNameMap, {MFA, FunLabel}), + true = ets:insert(ETSRecVarMap, {VarLabel, MFA}) + end, + lists:foreach(Fun, Defs). get_edges_from_deps(Deps) -> %% Convert the dependencies as produced by dialyzer_dep to a list of @@ -446,22 +430,22 @@ get_edges_from_deps(Deps) -> end, [], Deps), lists:flatten(Edges). -name_edges(Edges, NameMap) -> +name_edges(Edges, ETSNameMap) -> %% If a label is present in the name map it is renamed. Otherwise %% keep the label as the identity. MapFun = fun(X) -> - case dict:find(X, NameMap) of + case ets_lookup_dict(X, ETSNameMap) of error -> X; {ok, MFA} -> MFA end end, - name_edges(Edges, MapFun, NameMap, []). + name_edges(Edges, MapFun, []). -name_edges([{From, To}|Left], MapFun, NameMap, Acc) -> +name_edges([{From, To}|Left], MapFun, Acc) -> NewFrom = MapFun(From), NewTo = MapFun(To), - name_edges(Left, MapFun, NameMap, [{NewFrom, NewTo}|Acc]); -name_edges([], _MapFun, _NameMap, Acc) -> + name_edges(Left, MapFun, [{NewFrom, NewTo}|Acc]); +name_edges([], _MapFun, Acc) -> Acc. scan_core_funs(Tree) -> -- cgit v1.2.3 From 08d6fa6c97be82c4b4a480ec04aa06ae8e781783 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Sun, 19 Feb 2012 01:40:54 +0100 Subject: Parallel compilation of files under analysis --- lib/dialyzer/src/dialyzer_callgraph.erl | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 9eba64dd57..bf939655d0 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -28,6 +28,7 @@ -module(dialyzer_callgraph). -export([add_edges/2, + add_edges/3, all_nodes/1, delete/1, finalize/1, @@ -358,10 +359,10 @@ scan_core_tree(Tree, #callgraph{calls = ETSCalls, name_map = ETSNameMap, rec_var_map = ETSRecVarMap, rev_name_map = ETSRevNameMap, - self_rec = ETSSelfRec} = CG) -> + self_rec = ETSSelfRec}) -> %% Build name map and recursion variable maps. build_maps(Tree, ETSRecVarMap, ETSNameMap, ETSRevNameMap), - + %% First find the module-local dependencies. {Deps0, EscapingFuns, Calls} = dialyzer_dep:analyze(Tree), true = ets:insert(ETSCalls, dict:to_list(Calls)), @@ -399,7 +400,7 @@ scan_core_tree(Tree, #callgraph{calls = ETSCalls, NewNamedEdges1 = [E || {From, To} = E <- NamedEdges1, From =/= top, To =/= top], NamedEdges3 = NewNamedEdges1 ++ NewNamedEdges2, - add_edges(NamedEdges3, Names3, CG). + {Names3, NamedEdges3}. build_maps(Tree, ETSRecVarMap, ETSNameMap, ETSRevNameMap) -> %% We only care about the named (top level) functions. The anonymous -- cgit v1.2.3 From b8ab5bc3211fdee28000e2fd35a47dafa2a4316c Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Sun, 19 Feb 2012 22:05:47 +0100 Subject: Fix types and specs in Dialyzer --- lib/dialyzer/src/dialyzer_callgraph.erl | 29 +++++++++++++++++------------ 1 file changed, 17 insertions(+), 12 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index bf939655d0..bb96ada65f 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -264,7 +264,7 @@ get_required_by(SCC, #callgraph{active_digraph = DG}) -> modules(#callgraph{digraph = DG}) -> ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]). --spec module_postorder(callgraph()) -> [module()]. +-spec module_postorder(callgraph()) -> {[module()], digraph()}. module_postorder(#callgraph{digraph = DG}) -> Edges = digraph_edges(DG), @@ -323,7 +323,8 @@ reset_from_funs(Funs, #callgraph{digraph = DG, digraph_delete(SubGraph), {Postorder, CG#callgraph{active_digraph = NewActiveDG}}. --spec module_postorder_from_funs([mfa_or_funlbl()], callgraph()) -> [module()]. +-spec module_postorder_from_funs([mfa_or_funlbl()], callgraph()) -> + {[module()], callgraph()}. module_postorder_from_funs(Funs, #callgraph{digraph = DG} = CG) -> SubGraph = digraph_reaching_subgraph(Funs, DG), @@ -352,7 +353,8 @@ ets_lookup_set(Key, Table) -> %% The set of labels in the tree must be disjoint from the set of %% labels already occuring in the callgraph. --spec scan_core_tree(cerl:c_module(), callgraph()) -> callgraph(). +-spec scan_core_tree(cerl:c_module(), callgraph()) -> + {[mfa_or_funlbl()], [callgraph_edge()]}. scan_core_tree(Tree, #callgraph{calls = ETSCalls, esc = ETSEsc, @@ -595,9 +597,10 @@ renew_race_code(Races, #callgraph{race_data_server = RaceDataServer} = CG) -> ok = race_data_server_cast( {renew_race_code, {Fun, FunArgs, Code}}, RaceDataServer), - CG; -renew_race_code({Fun, FunArgs, Code}, - #race_data_state{race_code = RaceCode} = State) -> + CG. + +renew_race_code_handler({Fun, FunArgs, Code}, + #race_data_state{race_code = RaceCode} = State) -> State#race_data_state{race_code = dict:store(Fun, [FunArgs, Code], RaceCode)}. -spec renew_race_public_tables(label(), callgraph()) -> callgraph(). @@ -606,9 +609,11 @@ renew_race_public_tables(VarLabel, #callgraph{race_data_server = RaceDataServer} = CG) -> ok = race_data_server_cast({renew_race_public_tables, VarLabel}, RaceDataServer), - CG; -renew_race_public_tables(VarLabel, - #race_data_state{public_tables = PT} = State) -> + CG. + +renew_race_public_tables_handler(VarLabel, + #race_data_state{public_tables = PT} + = State) -> State#race_data_state{public_tables = ordsets:add_element(VarLabel, PT)}. -spec cleanup(callgraph()) -> callgraph(). @@ -739,8 +744,8 @@ race_data_server_handle_cast(race_code_new, State) -> race_data_server_handle_cast({Tag, Data}, State) -> case Tag of renew_race_info -> renew_race_info(Data, State); - renew_race_code -> renew_race_code(Data, State); - renew_race_public_tables -> renew_race_public_tables(Data, State); + renew_race_code -> renew_race_code_handler(Data, State); + renew_race_public_tables -> renew_race_public_tables_handler(Data, State); put_race_code -> State#race_data_state{race_code = Data}; put_public_tables -> State#race_data_state{public_tables = Data}; put_named_tables -> State#race_data_state{named_tables = Data}; @@ -775,7 +780,7 @@ to_dot(#callgraph{digraph = DG, esc = Esc} = CG, File) -> end end, Escaping = [{Fun(L), {color, red}} - || L <- sets:to_list(Esc), L =/= external], + || L <- [E || {E} <- ets:tab2list(Esc)], L =/= external], Vertices = digraph_edges(DG), hipe_dot:translate_list(Vertices, File, "CG", Escaping). -- cgit v1.2.3 From 0bae6c82503b348e62f11edfbfc880145ef06794 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Tue, 21 Feb 2012 16:01:50 +0100 Subject: Avoid digraph_utils:condensation and ordering in typesig --- lib/dialyzer/src/dialyzer_callgraph.erl | 85 ++++++++++++++++++++++++++------- 1 file changed, 67 insertions(+), 18 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index bb96ada65f..0c3e8ca311 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -92,7 +92,7 @@ %%----------------------------------------------------------------------------- -record(callgraph, {digraph = digraph:new() :: digraph(), - active_digraph :: digraph(), + active_digraph :: active_digraph(), esc :: ets:tid(), name_map :: ets:tid(), rev_name_map :: ets:tid(), @@ -111,6 +111,8 @@ -type callgraph() :: #callgraph{}. +-type active_digraph() :: {'d', digraph()} | {'e', ets:tid(), ets:tid()}. + %%---------------------------------------------------------------------- -spec new() -> callgraph(). @@ -247,12 +249,22 @@ find_non_local_calls([], Set) -> -spec get_depends_on(scc(), callgraph()) -> [scc()]. -get_depends_on(SCC, #callgraph{active_digraph = DG}) -> +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 = {'d', DG}}) -> digraph:out_neighbours(DG, SCC). -spec get_required_by(scc(), callgraph()) -> [scc()]. -get_required_by(SCC, #callgraph{active_digraph = DG}) -> +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 = {'d', DG}}) -> digraph:in_neighbours(DG, SCC). %%---------------------------------------------------------------------- @@ -273,7 +285,7 @@ module_postorder(#callgraph{digraph = DG}) -> MDG1 = digraph_confirm_vertices(Nodes, MDG), MDG2 = create_module_digraph(Edges, MDG1), PostOrder = digraph_utils:topsort(MDG2), - {PostOrder, MDG2}. + {PostOrder, {'d', MDG2}}. %% The module deps of a module are modules that depend on the module -spec module_deps(callgraph()) -> dict(). @@ -310,23 +322,24 @@ create_module_digraph([], MDG) -> -spec finalize(callgraph()) -> {[scc()], callgraph()}. finalize(#callgraph{digraph = DG} = CG) -> - {ActiveDG, Postorder} = digraph_finalize(DG), + {ActiveDG, Postorder} = condensation(DG), {Postorder, CG#callgraph{active_digraph = ActiveDG}}. -spec reset_from_funs([mfa_or_funlbl()], callgraph()) -> {[scc()], callgraph()}. -reset_from_funs(Funs, #callgraph{digraph = DG, - active_digraph = OldActiveDG} = CG) -> - digraph_delete(OldActiveDG), +reset_from_funs(Funs, #callgraph{digraph = DG, active_digraph = ADG} = CG) -> + active_digraph_delete(ADG), SubGraph = digraph_reaching_subgraph(Funs, DG), - {NewActiveDG, Postorder} = digraph_finalize(SubGraph), + {NewActiveDG, Postorder} = condensation(SubGraph), digraph_delete(SubGraph), {Postorder, CG#callgraph{active_digraph = NewActiveDG}}. -spec module_postorder_from_funs([mfa_or_funlbl()], callgraph()) -> {[module()], callgraph()}. -module_postorder_from_funs(Funs, #callgraph{digraph = DG} = CG) -> +module_postorder_from_funs(Funs, #callgraph{digraph = DG, + active_digraph = ADG} = CG) -> + active_digraph_delete(ADG), SubGraph = digraph_reaching_subgraph(Funs, DG), {PO, Active} = module_postorder(CG#callgraph{digraph = SubGraph}), digraph_delete(SubGraph), @@ -544,6 +557,12 @@ remove_unconfirmed([], DG, Unconfirmed) -> digraph_delete(DG) -> digraph:delete(DG). +active_digraph_delete({'d', DG}) -> + digraph:delete(DG); +active_digraph_delete({'e', Out, In}) -> + ets:delete(Out), + ets:delete(In). + digraph_edges(DG) -> digraph:edges(DG). @@ -556,14 +575,6 @@ digraph_in_neighbours(V, DG) -> List -> List end. -digraph_postorder(Digraph) -> - digraph_utils:topsort(Digraph). - -digraph_finalize(DG) -> - DG1 = digraph_utils:condensation(DG), - Postorder = digraph_postorder(DG1), - {DG1, Postorder}. - digraph_reaching_subgraph(Funs, DG) -> Vertices = digraph_utils:reaching(Funs, DG), digraph_utils:subgraph(DG, Vertices). @@ -792,3 +803,41 @@ to_ps(#callgraph{} = CG, File, Args) -> Command = io_lib:format("dot -Tps ~s -o ~s ~s", [Args, File, Dot_File]), _ = os:cmd(Command), ok. + +condensation(G) -> + SCs = digraph_utils:strong_components(G), + V2I = ets:new(condensation, []), + I2C = ets:new(condensation, []), + I2I = ets:new(condensation, [bag]), + CFun = + fun(SC, N) -> + lists:foreach(fun(V) -> true = ets:insert(V2I, {V,N}) end, SC), + true = ets:insert(I2C, {N, SC}), + N + 1 + end, + lists:foldl(CFun, 1, SCs), + Fun1 = + fun({V1, V2}) -> + I1 = ets:lookup_element(V2I, V1, 2), + I2 = ets:lookup_element(V2I, V2, 2), + case I1 =:= I2 of + true -> true; + false -> ets:insert(I2I, {I1, I2}) + end + end, + lists:foreach(Fun1, digraph:edges(G)), + Fun3 = + fun({I1, I2}, {Out, In}) -> + SC1 = ets:lookup_element(I2C, I1, 2), + SC2 = ets:lookup_element(I2C, I2, 2), + {dict:append(SC1, SC2, Out), dict:append(SC2, SC1, In)} + end, + {OutDict, InDict} = ets:foldl(Fun3, {dict:new(), dict:new()}, I2I), + OutETS = ets:new(out,[]), + InETS = ets:new(in,[]), + ets:insert(OutETS, dict:to_list(OutDict)), + ets:insert(InETS, dict:to_list(InDict)), + ets:delete(V2I), + ets:delete(I2C), + ets:delete(I2I), + {{'e', OutETS, InETS}, SCs}. -- cgit v1.2.3 From 7b622408befa56eefb2dc821c195727fe840d055 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Wed, 22 Feb 2012 12:18:32 +0100 Subject: Add read_concurrency option to some ETS tables --- lib/dialyzer/src/dialyzer_callgraph.erl | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 0c3e8ca311..cd465b26dc 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -119,7 +119,7 @@ new() -> [ETSEsc, ETSNameMap, ETSRevNameMap, ETSRecVarMap, ETSSelfRec, ETSCalls] = - [ets:new(N,[public]) || + [ets:new(N,[public, {read_concurrency, true}]) || N <- [callgraph_esc, callgraph_name_map, callgraph_rev_name_map, callgraph_rec_var_map, callgraph_self_rec, callgraph_calls]], #callgraph{esc = ETSEsc, @@ -833,8 +833,8 @@ condensation(G) -> {dict:append(SC1, SC2, Out), dict:append(SC2, SC1, In)} end, {OutDict, InDict} = ets:foldl(Fun3, {dict:new(), dict:new()}, I2I), - OutETS = ets:new(out,[]), - InETS = ets:new(in,[]), + [OutETS, InETS] = + [ets:new(Name,[{read_concurrency, true}]) || Name <- [out, in]], ets:insert(OutETS, dict:to_list(OutDict)), ets:insert(InETS, dict:to_list(InDict)), ets:delete(V2I), -- cgit v1.2.3 From e200c6519651319ddcb874d0aff23cc21e1a9c83 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Wed, 22 Feb 2012 16:04:20 +0100 Subject: Fix specs --- lib/dialyzer/src/dialyzer_callgraph.erl | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index cd465b26dc..80f2c48676 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -247,7 +247,7 @@ find_non_local_calls([{Label1, Label2}|Left], Set) when is_integer(Label1), find_non_local_calls([], Set) -> sets:to_list(Set). --spec get_depends_on(scc(), callgraph()) -> [scc()]. +-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 @@ -257,7 +257,7 @@ get_depends_on(SCC, #callgraph{active_digraph = {'e', Out, _In}}) -> get_depends_on(SCC, #callgraph{active_digraph = {'d', DG}}) -> digraph:out_neighbours(DG, SCC). --spec get_required_by(scc(), callgraph()) -> [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 @@ -276,7 +276,7 @@ get_required_by(SCC, #callgraph{active_digraph = {'d', DG}}) -> modules(#callgraph{digraph = DG}) -> ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]). --spec module_postorder(callgraph()) -> {[module()], digraph()}. +-spec module_postorder(callgraph()) -> {[module()], {'d', digraph()}}. module_postorder(#callgraph{digraph = DG}) -> Edges = digraph_edges(DG), -- cgit v1.2.3 From 913ee73601e3f7d0b27d833bd67cf6ee3868018a Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Wed, 22 Feb 2012 15:31:16 +0100 Subject: All spawns are now spawn_links --- lib/dialyzer/src/dialyzer_callgraph.erl | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 80f2c48676..0384160abc 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -724,7 +724,7 @@ put_behaviour_api_calls(Calls, new_race_data_server() -> - spawn(fun() -> race_data_server_loop(#race_data_state{}) end). + spawn_link(fun() -> race_data_server_loop(#race_data_state{}) end). race_data_server_loop(State) -> receive @@ -770,7 +770,7 @@ race_data_server_handle_call(Query, beh_api_calls = BehApiCalls} = State) -> case Query of - dup -> spawn(fun() -> race_data_server_loop(State) end); + dup -> spawn_link(fun() -> race_data_server_loop(State) end); get_race_code -> RaceCode; get_public_tables -> PublicTables; get_named_tables -> NamedTables; -- cgit v1.2.3 From 9f30b73af775daeca99e8094b08ca4e5d9b6cd82 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Tue, 28 Feb 2012 11:04:12 +0100 Subject: More efficient calculation of module deps and postorder --- lib/dialyzer/src/dialyzer_callgraph.erl | 45 +++++++++++++++++---------------- 1 file changed, 23 insertions(+), 22 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 0384160abc..cc26d9fdd5 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -279,26 +279,36 @@ modules(#callgraph{digraph = DG}) -> -spec module_postorder(callgraph()) -> {[module()], {'d', digraph()}}. module_postorder(#callgraph{digraph = DG}) -> - Edges = digraph_edges(DG), - Nodes = ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]), + Edges = lists:foldl(fun edge_fold/2, sets:new(), digraph_edges(DG)), + Nodes = sets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]), MDG = digraph:new([acyclic]), - MDG1 = digraph_confirm_vertices(Nodes, MDG), - MDG2 = create_module_digraph(Edges, MDG1), - PostOrder = digraph_utils:topsort(MDG2), - {PostOrder, {'d', MDG2}}. + MDG = 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)), + PostOrder = digraph_utils:topsort(MDG), + {PostOrder, {'d', MDG}}. + +edge_fold({{M1,_,_},{M2,_,_}}, Set) -> + case M1 =/= M2 of + true -> sets:add_element({M1,M2},Set); + false -> Set + end; +edge_fold(_, Set) -> Set. + %% The module deps of a module are modules that depend on the module -spec module_deps(callgraph()) -> dict(). module_deps(#callgraph{digraph = DG}) -> - Edges = digraph_edges(DG), - Nodes = ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]), + Edges = lists:foldl(fun edge_fold/2, sets:new(), digraph_edges(DG)), + Nodes = sets: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(MDG2), + MDG = 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)), + Deps = [{N, ordsets:from_list(digraph:in_neighbours(MDG, N))} + || N <- sets:to_list(Nodes)], + digraph_delete(MDG), dict:from_list(Deps). -spec strip_module_deps(dict(), set()) -> dict(). @@ -310,15 +320,6 @@ strip_module_deps(ModDeps, StripSet) -> FilterFun2 = fun(_Key, ValSet) -> ValSet =/= [] end, dict:filter(FilterFun2, ModDeps1). -create_module_digraph([{{M, _, _}, {M, _, _}}|Left], MDG) -> - create_module_digraph(Left, MDG); -create_module_digraph([{{M1, _, _}, {M2, _, _}}|Left], MDG) -> - create_module_digraph(Left, digraph_add_edge(M1, M2, MDG)); -create_module_digraph([{_, _}|Left], MDG) -> - create_module_digraph(Left, MDG); -create_module_digraph([], MDG) -> - MDG. - -spec finalize(callgraph()) -> {[scc()], callgraph()}. finalize(#callgraph{digraph = DG} = CG) -> -- cgit v1.2.3 From ec142ae5c0696bb7893a67ff6356c7da3369a7fc Mon Sep 17 00:00:00 2001 From: Kostis Sagonas Date: Sun, 4 Mar 2012 16:16:52 +0100 Subject: Code simplifications (tidier) --- lib/dialyzer/src/dialyzer_callgraph.erl | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index cc26d9fdd5..854d67e835 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -354,10 +354,7 @@ ets_lookup_dict(Key, Table) -> end. ets_lookup_set(Key, Table) -> - case ets:lookup(Table, Key) of - [] -> false; - _ -> true - end. + ets:lookup(Table, Key) =/= []. %%---------------------------------------------------------------------- %% Core code -- cgit v1.2.3 From 49ccc5df4f2f64ff19dd5751523c8ba45adaf658 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Mon, 5 Mar 2012 10:38:01 +0100 Subject: Better reflect side-effect based code in dialyzer_callgraph --- lib/dialyzer/src/dialyzer_callgraph.erl | 31 ++++++++++++++++--------------- 1 file changed, 16 insertions(+), 15 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 854d67e835..3330ec252d 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -206,17 +206,17 @@ is_escaping(Label, #callgraph{esc = Esc}) when is_integer(Label) -> ets_lookup_set(Label, Esc). -type callgraph_edge() :: {mfa_or_funlbl(),mfa_or_funlbl()}. --spec add_edges([callgraph_edge()], callgraph()) -> callgraph(). +-spec add_edges([callgraph_edge()], callgraph()) -> ok. -add_edges([], CG) -> - CG; -add_edges(Edges, #callgraph{digraph = Digraph} = CG) -> - CG#callgraph{digraph = digraph_add_edges(Edges, Digraph)}. +add_edges([], _CG) -> + ok; +add_edges(Edges, #callgraph{digraph = Digraph}) -> + digraph_add_edges(Edges, Digraph). --spec add_edges([callgraph_edge()], [mfa_or_funlbl()], callgraph()) -> callgraph(). +-spec add_edges([callgraph_edge()], [mfa_or_funlbl()], callgraph()) -> ok. add_edges(Edges, MFAs, #callgraph{digraph = DG} = CG) -> - DG = digraph_confirm_vertices(MFAs, DG), + digraph_confirm_vertices(MFAs, DG), add_edges(Edges, CG). -spec remove_external(callgraph()) -> {callgraph(), [tuple()]}. @@ -282,7 +282,7 @@ module_postorder(#callgraph{digraph = DG}) -> Edges = lists:foldl(fun edge_fold/2, sets:new(), digraph_edges(DG)), Nodes = sets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]), MDG = digraph:new([acyclic]), - MDG = digraph_confirm_vertices(sets:to_list(Nodes), MDG), + 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)), PostOrder = digraph_utils:topsort(MDG), @@ -303,7 +303,7 @@ module_deps(#callgraph{digraph = DG}) -> Edges = lists:foldl(fun edge_fold/2, sets:new(), digraph_edges(DG)), Nodes = sets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]), MDG = digraph:new(), - MDG = digraph_confirm_vertices(sets:to_list(Nodes), MDG), + 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)), Deps = [{N, ordsets:from_list(digraph:in_neighbours(MDG, N))} @@ -511,9 +511,10 @@ get_label(T) -> %%---------------------------------------------------------------------- digraph_add_edges([{From, To}|Left], DG) -> - digraph_add_edges(Left, digraph_add_edge(From, To, DG)); -digraph_add_edges([], DG) -> - DG. + digraph_add_edge(From, To, DG), + digraph_add_edges(Left, DG); +digraph_add_edges([], _DG) -> + ok. digraph_add_edge(From, To, DG) -> case digraph:vertex(DG, From) of @@ -525,13 +526,13 @@ digraph_add_edge(From, To, DG) -> {To, _} -> ok end, digraph:add_edge(DG, {From, To}, From, To, []), - DG. + ok. digraph_confirm_vertices([MFA|Left], DG) -> digraph:add_vertex(DG, MFA, confirmed), digraph_confirm_vertices(Left, DG); -digraph_confirm_vertices([], DG) -> - DG. +digraph_confirm_vertices([], _DG) -> + ok. digraph_remove_external(DG) -> Vertices = digraph:vertices(DG), -- cgit v1.2.3 From 76b7c72882ee521a7c5a39d33ecf1009a72ee4e3 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Mon, 5 Mar 2012 13:01:11 +0100 Subject: Fix types and specs --- lib/dialyzer/src/dialyzer_callgraph.erl | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 3330ec252d..d6307ec658 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -64,7 +64,7 @@ put_named_tables/2, put_public_tables/2, put_behaviour_api_calls/2, get_behaviour_api_calls/1, dispose_race_server/1, duplicate/1]). --export_type([callgraph/0, mfa_or_funlbl/0]). +-export_type([callgraph/0, mfa_or_funlbl/0, callgraph_edge/0]). -include("dialyzer.hrl"). -- cgit v1.2.3 From d24d65f1a76871d3e9c8f5c19f0b4ace6de393aa Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Wed, 21 Mar 2012 16:34:58 +0100 Subject: Remove needless conversion The final version of the callgraph needs not be "reduced" for more efficient copying. --- lib/dialyzer/src/dialyzer_callgraph.erl | 20 -------------------- 1 file changed, 20 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index d6307ec658..327092e23c 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -44,7 +44,6 @@ %% module_postorder/1, module_postorder_from_funs/2, new/0, - mini_callgraph/1, get_depends_on/2, get_required_by/2, in_neighbours/2, @@ -129,25 +128,6 @@ new() -> self_rec = ETSSelfRec, calls = ETSCalls}. --spec mini_callgraph(callgraph()) -> callgraph(). - -mini_callgraph(#callgraph{digraph = Digraph, - active_digraph = ActiveDigraph, - esc = Esc, - name_map = NameMap, - rev_name_map = RevNameMap, - rec_var_map = RecVarMap, - self_rec = SelfRecs, - calls = Calls}) -> - #callgraph{digraph = Digraph, - active_digraph = ActiveDigraph, - esc = Esc, - name_map = NameMap, - rev_name_map = RevNameMap, - rec_var_map = RecVarMap, - self_rec = SelfRecs, - calls = Calls}. - -spec delete(callgraph()) -> 'true'. delete(#callgraph{digraph = Digraph}) -> -- cgit v1.2.3 From 24c2c72cab2c282eb17c8ac97c832106ecaf4ed8 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Wed, 21 Mar 2012 17:58:09 +0100 Subject: Better names for callgaph ETS tables --- lib/dialyzer/src/dialyzer_callgraph.erl | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 327092e23c..4ff9f5920b 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -785,9 +785,9 @@ to_ps(#callgraph{} = CG, File, Args) -> condensation(G) -> SCs = digraph_utils:strong_components(G), - V2I = ets:new(condensation, []), - I2C = ets:new(condensation, []), - I2I = ets:new(condensation, [bag]), + V2I = ets:new(condensation_v2i, []), + I2C = ets:new(condensation_i2c, []), + I2I = ets:new(condensation_i2i, [bag]), CFun = fun(SC, N) -> lists:foreach(fun(V) -> true = ets:insert(V2I, {V,N}) end, SC), @@ -813,7 +813,8 @@ condensation(G) -> end, {OutDict, InDict} = ets:foldl(Fun3, {dict:new(), dict:new()}, I2I), [OutETS, InETS] = - [ets:new(Name,[{read_concurrency, true}]) || Name <- [out, in]], + [ets:new(Name,[{read_concurrency, true}]) || + Name <- [callgraph_deps_out, callgraph_deps_in]], ets:insert(OutETS, dict:to_list(OutDict)), ets:insert(InETS, dict:to_list(InDict)), ets:delete(V2I), -- cgit v1.2.3 From 720b65deff021ddb17aaa125046f97ff13ade883 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Tue, 20 Mar 2012 12:07:42 +0100 Subject: Regulate all kinds of running workers up to the number of schedulers --- lib/dialyzer/src/dialyzer_callgraph.erl | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index 4ff9f5920b..64e0ee88af 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -265,8 +265,7 @@ 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)), - PostOrder = digraph_utils:topsort(MDG), - {PostOrder, {'d', MDG}}. + {digraph_utils:topsort(MDG), {'d', MDG}}. edge_fold({{M1,_,_},{M2,_,_}}, Set) -> case M1 =/= M2 of -- cgit v1.2.3