Solve big SCC constraints in parallel

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..3f73afb971 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(erlang:system_info(logical_processors_available), 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),