Parallel typesig analysis

1 files changed, 99 insertions, 41 deletions

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),