diff options
author | Henrik Nord <[email protected]> | 2012-05-31 15:57:44 +0200 |
---|---|---|
committer | Henrik Nord <[email protected]> | 2012-05-31 15:57:51 +0200 |
commit | 3e348c69b6921dd0e2c5b699ccd36d46321c953c (patch) | |
tree | 411b2ac33b8a2d84b39d1f4b9341c38de06cfff4 /lib/dialyzer/src/dialyzer_typesig.erl | |
parent | cdd1bc668112289cb2ee573c067ba106ca707b91 (diff) | |
parent | 49c657461866f0fe87de2ee7578b46b1b926db10 (diff) | |
download | otp-3e348c69b6921dd0e2c5b699ccd36d46321c953c.tar.gz otp-3e348c69b6921dd0e2c5b699ccd36d46321c953c.tar.bz2 otp-3e348c69b6921dd0e2c5b699ccd36d46321c953c.zip |
Merge branch 'sa/dialyzer-parallel' into maint
* sa/dialyzer-parallel: (54 commits)
Logfile-like statistics (enabled with --resources)
Anonymous SCCtoPID ETS table
Anonymous time server
Regulate all kinds of running workers up to the number of schedulers
Relocate start and stop of timing server
Better names for callgaph ETS tables
Remove needless conversion
Fix types and specs
Inline a function in dialyzer_worker
Remove unused function
Change --time to --statistics and include more info
Better reflect side-effect based code in dialyzer_callgraph
Code simplifications (tidier)
More efficient calculation of module deps and postorder
Solve big SCC constraints in parallel
Coordinator is no longer a separate process
All spawns are now spawn_links
Fix race in coordinator
Typesig and dataflow analyses no longer use ticket regulation
Plain concatenation for typesig not-fixpoint list
...
OTP-10103
Diffstat (limited to 'lib/dialyzer/src/dialyzer_typesig.erl')
-rw-r--r-- | lib/dialyzer/src/dialyzer_typesig.erl | 214 |
1 files changed, 173 insertions, 41 deletions
diff --git a/lib/dialyzer/src/dialyzer_typesig.erl b/lib/dialyzer/src/dialyzer_typesig.erl index d0d27740f3..6ee1795fc5 100644 --- a/lib/dialyzer/src/dialyzer_typesig.erl +++ b/lib/dialyzer/src/dialyzer_typesig.erl @@ -91,23 +91,25 @@ -type typesig_scc() :: [{mfa(), {cerl:c_var(), cerl:c_fun()}, dict()}]. -type typesig_funmap() :: [{type_var(), type_var()}]. %% Orddict --record(state, {callgraph :: dialyzer_callgraph:callgraph(), - cs = [] :: [constr()], - cmap = dict:new() :: dict(), - fun_map = [] :: typesig_funmap(), - fun_arities = dict:new() :: dict(), - in_match = false :: boolean(), - in_guard = false :: boolean(), - module :: module(), - name_map = dict:new() :: dict(), - next_label :: label(), - self_recs :: [label()], - plt :: dialyzer_plt:plt(), - prop_types = dict:new() :: dict(), - records = dict:new() :: dict(), - opaques = [] :: [erl_types:erl_type()], - scc = [] :: [type_var()], - mfas = [] :: [dialyzer_callgraph:mfa_or_funlbl()] +-type dict_or_ets() :: {'d', dict()} | {'e', ets:tid()}. + +-record(state, {callgraph :: dialyzer_callgraph:callgraph(), + cs = [] :: [constr()], + cmap = {'d', dict:new()} :: dict_or_ets(), + fun_map = [] :: typesig_funmap(), + fun_arities = dict:new() :: dict(), + in_match = false :: boolean(), + in_guard = false :: boolean(), + module :: module(), + name_map = dict:new() :: dict(), + next_label = 0 :: label(), + self_rec :: erl_types:erl_type(), + plt :: dialyzer_plt:plt(), + prop_types = {'d', dict:new()} :: dict_or_ets(), + records = dict:new() :: dict(), + opaques = [] :: [erl_types:erl_type()], + scc = [] :: [type_var()], + mfas :: [tuple()] }). %%----------------------------------------------------------------------------- @@ -1665,7 +1667,12 @@ solve([Fun], State) -> solve([_|_] = SCC, State) -> ?debug("============ Analyzing SCC: ~w ===========\n", [[debug_lookup_name(F) || F <- SCC]]), - solve_scc(SCC, dict:new(), State, false). + {Parallel, NewState} = + case parallel_split(SCC) of + false -> {false, State}; + SplitSCC -> {SplitSCC, minimize_state(State)} + end, + solve_scc(SCC, Parallel, dict:new(), NewState, false). solve_fun(Fun, FunMap, State) -> Cs = state__get_cs(Fun, State), @@ -1680,8 +1687,7 @@ solve_fun(Fun, FunMap, State) -> end, enter_type(Fun, NewType, NewFunMap1). -solve_scc(SCC, Map, State, TryingUnit) -> - State1 = state__mark_as_non_self_rec(SCC, State), +solve_scc(SCC, Parallel, Map, State, TryingUnit) -> Vars0 = [{Fun, state__get_rec_var(Fun, State)} || Fun <- SCC], Vars = [Var || {_, {ok, Var}} <- Vars0], Funs = [Fun || {Fun, {ok, _}} <- Vars0], @@ -1692,9 +1698,12 @@ solve_scc(SCC, Map, State, TryingUnit) -> end, Map, SCC), Map1 = enter_type_lists(Vars, RecTypes, CleanMap), ?debug("Checking SCC: ~w\n", [[debug_lookup_name(F) || F <- SCC]]), - SolveFun = fun(X, Y) -> scc_fold_fun(X, Y, State1) end, - Map2 = lists:foldl(SolveFun, Map1, SCC), FunSet = ordsets:from_list([t_var_name(F) || F <- SCC]), + Map2 = + case Parallel of + false -> solve_whole_scc(SCC, Map1, State); + SplitSCC -> solve_whole_scc_parallel(SplitSCC, Map1, State) + end, case maps_are_equal(Map2, Map, FunSet) of true -> ?debug("SCC ~w reached fixpoint\n", [SCC]), @@ -1708,15 +1717,127 @@ solve_scc(SCC, Map, State, TryingUnit) -> true -> t_fun(t_fun_args(T), t_unit()) end || T <- NewTypes], Map3 = enter_type_lists(Funs, UnitTypes, Map2), - solve_scc(SCC, Map3, State, true); + solve_scc(SCC, Parallel, Map3, State, true); false -> + case Parallel of + false -> true; + _ -> dispose_state(State) + end, Map2 end; false -> ?debug("SCC ~w did not reach fixpoint\n", [SCC]), - solve_scc(SCC, Map2, State, TryingUnit) + solve_scc(SCC, Parallel, Map2, State, TryingUnit) + end. + +solve_whole_scc(SCC, Map, State) -> + SolveFun = fun(X, Y) -> scc_fold_fun(X, Y, State) end, + lists:foldl(SolveFun, Map, SCC). + +%%------------------------------------------------------------------------------ + +-define(worth_it, 42). + +parallel_split(SCC) -> + Length = length(SCC), + case Length > 2*?worth_it of + false -> false; + true -> + case min(dialyzer_utils:parallelism(), 8) of + 1 -> false; + CPUs -> + FullShare = Length div CPUs + 1, + Unit = max(FullShare, ?worth_it), + split(SCC, Unit, []) + end end. +minimize_state(#state{ + cmap = {d, CMap}, + fun_map = FunMap, + fun_arities = FunArities, + self_rec = SelfRec, + prop_types = {d, PropTypes}, + opaques = Opaques + }) -> + ETSCMap = ets:new(cmap,[{read_concurrency, true}]), + ETSPropTypes = ets:new(prop_types,[{read_concurrency, true}]), + true = ets:insert(ETSCMap, dict:to_list(CMap)), + true = ets:insert(ETSPropTypes, dict:to_list(PropTypes)), + #state + {cmap = {e, ETSCMap}, + fun_map = FunMap, + fun_arities = FunArities, + self_rec = SelfRec, + prop_types = {e, ETSPropTypes}, + opaques = Opaques + }. + +dispose_state(#state{cmap = {e, ETSCMap}, + prop_types = {e, ETSPropTypes}}) -> + true = ets:delete(ETSCMap), + true = ets:delete(ETSPropTypes). + +solve_whole_scc_parallel(SplitSCC, Map, State) -> + Workers = spawn_workers(SplitSCC, Map, State), + wait_results(Workers, Map, fold_res_fun(State)). + +spawn_workers(SplitSCC, Map, State) -> + Spawner = solve_scc_spawner(self(), Map, State), + lists:foreach(Spawner, SplitSCC), + length(SplitSCC). + +wait_results(0, Map, _FoldResFun) -> + Map; +wait_results(Pending, Map, FoldResFun) -> + Res = receive_scc_result(), + NewMap = lists:foldl(FoldResFun, Map, Res), + wait_results(Pending-1, NewMap, FoldResFun). + +solve_scc_spawner(Parent, Map, State) -> + fun(SCCPart) -> + spawn_link(fun() -> solve_scc_worker(Parent, SCCPart, Map, State) end) + end. + +split([], _Unit, Acc) -> + Acc; +split(List, Unit, Acc) -> + {Taken, Rest} = + try + lists:split(Unit, List) + catch + _:_ -> {List, []} + end, + split(Rest, Unit, [Taken|Acc]). + +solve_scc_worker(Parent, SCCPart, Map, State) -> + SolveFun = fun(X, Y) -> scc_fold_fun(X, Y, State) end, + FinalMap = lists:foldl(SolveFun, Map, SCCPart), + Res = + [{F, t_limit(unsafe_lookup_type(F, FinalMap), ?TYPE_LIMIT)} || + F <- SCCPart], + send_scc_result(Parent, Res). + +fold_res_fun(State) -> + fun({F, Type}, Map) -> + case state__get_rec_var(F, State) of + {ok, R} -> + enter_type(R, Type, enter_type(F, Type, Map)); + error -> + enter_type(F, Type, Map) + end + end. + +receive_scc_result() -> + receive + {scc_fun, Res} -> Res + end. + +send_scc_result(Parent, Res) -> + Parent ! {scc_fun, Res}. + +%%------------------------------------------------------------------------------ + scc_fold_fun(F, FunMap, State) -> Deps = get_deps(state__get_cs(F, State)), Cs = mk_constraint_ref(F, Deps), @@ -2090,11 +2211,19 @@ new_state(SCC0, NextLabel, CallGraph, Plt, PropTypes) -> NameMap = dict:from_list(List), MFAs = [MFA || {MFA, _Var} <- List], SCC = [mk_var(Fun) || {_MFA, {_Var, Fun}, _Rec} <- SCC0], - SelfRecs = [F || F <- SCC, - dialyzer_callgraph:is_self_rec(t_var_name(F), CallGraph)], + SelfRec = + case SCC of + [OneF] -> + Label = t_var_name(OneF), + case dialyzer_callgraph:is_self_rec(Label, CallGraph) of + true -> OneF; + false -> false + end; + _Many -> false + end, #state{callgraph = CallGraph, name_map = NameMap, next_label = NextLabel, - prop_types = PropTypes, plt = Plt, scc = ordsets:from_list(SCC), - mfas = MFAs, self_recs = ordsets:from_list(SelfRecs)}. + prop_types = {d, PropTypes}, plt = Plt, scc = ordsets:from_list(SCC), + mfas = MFAs, self_rec = SelfRec}. state__set_rec_dict(State, RecDict) -> State#state{records = RecDict}. @@ -2193,14 +2322,21 @@ state__plt(#state{plt = PLT}) -> state__new_constraint_context(State) -> State#state{cs = []}. -state__prop_domain(FunLabel, #state{prop_types = PropTypes}) -> +state__prop_domain(FunLabel, #state{prop_types = {e, ETSPropTypes}}) -> + try ets:lookup_element(ETSPropTypes, FunLabel, 2) of + {_Range_Fun, Dom} -> {ok, Dom}; + FunType -> {ok, t_fun_args(FunType)} + catch + _:_ -> error + end; +state__prop_domain(FunLabel, #state{prop_types = {d, PropTypes}}) -> case dict:find(FunLabel, PropTypes) of error -> error; {ok, {_Range_Fun, Dom}} -> {ok, Dom}; {ok, FunType} -> {ok, t_fun_args(FunType)} end. -state__add_prop_constrs(Tree, #state{prop_types = PropTypes} = State) -> +state__add_prop_constrs(Tree, #state{prop_types = {d, PropTypes}} = State) -> Label = cerl_trees:get_label(Tree), case dict:find(Label, PropTypes) of error -> State; @@ -2263,21 +2399,17 @@ state__mk_vars(N, #state{next_label = NL} = State) -> Vars = [t_var(X) || X <- lists:seq(NL, NewLabel-1)], {State#state{next_label = NewLabel}, Vars}. -state__store_constrs(Id, Cs, #state{cmap = Dict} = State) -> +state__store_constrs(Id, Cs, #state{cmap = {d, Dict}} = State) -> NewDict = dict:store(Id, Cs, Dict), - State#state{cmap = NewDict}. + State#state{cmap = {d, NewDict}}. -state__get_cs(Var, #state{cmap = Dict}) -> +state__get_cs(Var, #state{cmap = {e, ETSDict}}) -> + ets:lookup_element(ETSDict, Var, 2); +state__get_cs(Var, #state{cmap = {d, Dict}}) -> dict:fetch(Var, Dict). -%% The functions here will not be treated as self recursive. -%% These functions will need to be handled as such manually. -state__mark_as_non_self_rec(SCC, #state{self_recs = SelfRecs} = State) -> - %% TODO: Check if the result is always empty and just set it to [] if so. - State#state{self_recs = ordsets:subtract(SelfRecs, ordsets:from_list(SCC))}. - -state__is_self_rec(Fun, #state{self_recs = SelfRecs}) -> - ordsets:is_element(Fun, SelfRecs). +state__is_self_rec(Fun, #state{self_rec = SelfRec}) -> + Fun =:= SelfRec. state__store_funs(Vars0, Funs0, #state{fun_map = Map} = State) -> debug_make_name_map(Vars0, Funs0), |