aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorHans Bolinder <[email protected]>2011-12-01 15:29:54 +0100
committerHans Bolinder <[email protected]>2011-12-08 14:40:19 +0100
commit1a304b90c18c08c7399751b047c8d7725d8c96e8 (patch)
treed25b5252e396898ef0427d205c84566c9fdd716f
parentac3cbe8bee6b826004c02a1d21f8093899716b33 (diff)
downloadotp-1a304b90c18c08c7399751b047c8d7725d8c96e8.tar.gz
otp-1a304b90c18c08c7399751b047c8d7725d8c96e8.tar.bz2
otp-1a304b90c18c08c7399751b047c8d7725d8c96e8.zip
Optimize join_maps() in dialyzer_dataflow
By keeping tracks of modified types the joining of maps ha become significantly faster.
-rw-r--r--lib/dialyzer/src/dialyzer_dataflow.erl146
1 files changed, 101 insertions, 45 deletions
diff --git a/lib/dialyzer/src/dialyzer_dataflow.erl b/lib/dialyzer/src/dialyzer_dataflow.erl
index d74c04385b..6008dba080 100644
--- a/lib/dialyzer/src/dialyzer_dataflow.erl
+++ b/lib/dialyzer/src/dialyzer_dataflow.erl
@@ -101,6 +101,12 @@
behaviour_api_dict = [] ::
dialyzer_behaviours:behaviour_api_dict()}).
+-record(map, {dict = dict:new() :: dict(),
+ subst = dict:new() :: dict(),
+ modified = [] :: [Key :: term()],
+ modified_stack = [] :: [{[Key :: term()],reference()}],
+ ref = undefined :: reference() | undefined}).
+
%% Exported Types
-opaque state() :: #state{}.
@@ -1058,12 +1064,13 @@ handle_case(Tree, Map, #state{callgraph = Callgraph} = State) ->
RaceListSize + 1, State1);
false -> State1
end,
+ Map2 = join_maps_begin(Map1),
{MapList, State3, Type} =
handle_clauses(Clauses, Arg, ArgType, ArgType, State2,
- [], Map1, [], []),
- Map2 = join_maps(MapList, Map1),
+ [], Map2, [], []),
+ Map3 = join_maps_end(MapList, Map2),
debug_pp_map(Map2),
- {State3, Map2, Type}
+ {State3, Map3, Type}
end.
%%----------------------------------------
@@ -1640,14 +1647,15 @@ bind_pat_vars([Pat|PatLeft], [Type|TypeLeft], Acc, Map, State, Rev) ->
false ->
SubTuples = t_tuple_subtypes(Tuple),
%% Need to call the top function to get the try-catch wrapper
+ MapJ = join_maps_begin(Map),
Results =
case Rev of
true ->
[bind_pat_vars_reverse(Es, t_tuple_args(SubTuple), [],
- Map, State)
+ MapJ, State)
|| SubTuple <- SubTuples];
false ->
- [bind_pat_vars(Es, t_tuple_args(SubTuple), [], Map, State)
+ [bind_pat_vars(Es, t_tuple_args(SubTuple), [], MapJ, State)
|| SubTuple <- SubTuples]
end,
case lists:keyfind(opaque, 2, Results) of
@@ -1661,7 +1669,7 @@ bind_pat_vars([Pat|PatLeft], [Type|TypeLeft], Acc, Map, State, Rev) ->
false -> bind_error([Pat], Tuple, t_none(), bind)
end;
Maps ->
- Map1 = join_maps(Maps, Map),
+ Map1 = join_maps_end(Maps, MapJ),
TupleType = t_sup([t_tuple(EsTypes)
|| {M, EsTypes} <- Results, M =/= error]),
{Map1, TupleType}
@@ -2308,27 +2316,29 @@ handle_guard_and(Guard, Map, Env, Eval, State) ->
end
end;
neg ->
+ MapJ = join_maps_begin(Map),
{Map1, Type1} =
- try bind_guard(Arg1, Map, Env, neg, State)
- catch throw:{fail, _} -> bind_guard(Arg2, Map, Env, pos, State)
+ try bind_guard(Arg1, MapJ, Env, neg, State)
+ catch throw:{fail, _} -> bind_guard(Arg2, MapJ, Env, pos, State)
end,
{Map2, Type2} =
- try bind_guard(Arg2, Map, Env, neg, State)
- catch throw:{fail, _} -> bind_guard(Arg1, Map, Env, pos, State)
+ try bind_guard(Arg2, MapJ, Env, neg, State)
+ catch throw:{fail, _} -> bind_guard(Arg1, MapJ, Env, pos, State)
end,
case t_is_atom(false, Type1) orelse t_is_atom(false, Type2) of
- true -> {join_maps([Map1, Map2], Map), t_atom(false)};
+ true -> {join_maps_end([Map1, Map2], MapJ), t_atom(false)};
false -> signal_guard_fail(Eval, Guard, [Type1, Type2], State)
end;
dont_know ->
- {Map1, Type1} = bind_guard(Arg1, Map, Env, dont_know, State),
- {Map2, Type2} = bind_guard(Arg2, Map, Env, dont_know, State),
+ MapJ = join_maps_begin(Map),
+ {Map1, Type1} = bind_guard(Arg1, MapJ, Env, dont_know, State),
+ {Map2, Type2} = bind_guard(Arg2, MapJ, Env, dont_know, State),
Bool1 = t_inf(Type1, t_boolean()),
Bool2 = t_inf(Type2, t_boolean()),
case t_is_none(Bool1) orelse t_is_none(Bool2) of
true -> throw({fatal_fail, none});
false ->
- NewMap = join_maps([Map1, Map2], Map),
+ NewMap = join_maps_end([Map1, Map2], MapJ),
NewType =
case {t_atom_vals(Bool1), t_atom_vals(Bool2)} of
{['true'] , ['true'] } -> t_atom(true);
@@ -2344,20 +2354,21 @@ handle_guard_or(Guard, Map, Env, Eval, State) ->
[Arg1, Arg2] = cerl:call_args(Guard),
case Eval of
pos ->
+ MapJ = join_maps_begin(Map),
{Map1, Bool1} =
- try bind_guard(Arg1, Map, Env, pos, State)
+ try bind_guard(Arg1, MapJ, Env, pos, State)
catch
- throw:{fail,_} -> bind_guard(Arg1, Map, Env, dont_know, State)
+ throw:{fail,_} -> bind_guard(Arg1, MapJ, Env, dont_know, State)
end,
{Map2, Bool2} =
- try bind_guard(Arg2, Map, Env, pos, State)
+ try bind_guard(Arg2, MapJ, Env, pos, State)
catch
- throw:{fail,_} -> bind_guard(Arg2, Map, Env, dont_know, State)
+ throw:{fail,_} -> bind_guard(Arg2, MapJ, Env, dont_know, State)
end,
case ((t_is_atom(true, Bool1) andalso t_is_boolean(Bool2))
orelse
(t_is_atom(true, Bool2) andalso t_is_boolean(Bool1))) of
- true -> {join_maps([Map1, Map2], Map), t_atom(true)};
+ true -> {join_maps_end([Map1, Map2], MapJ), t_atom(true)};
false -> signal_guard_fail(Eval, Guard, [Bool1, Bool2], State)
end;
neg ->
@@ -2372,14 +2383,15 @@ handle_guard_or(Guard, Map, Env, Eval, State) ->
end
end;
dont_know ->
- {Map1, Type1} = bind_guard(Arg1, Map, Env, dont_know, State),
- {Map2, Type2} = bind_guard(Arg2, Map, Env, dont_know, State),
+ MapJ = join_maps_begin(Map),
+ {Map1, Type1} = bind_guard(Arg1, MapJ, Env, dont_know, State),
+ {Map2, Type2} = bind_guard(Arg2, MapJ, Env, dont_know, State),
Bool1 = t_inf(Type1, t_boolean()),
Bool2 = t_inf(Type2, t_boolean()),
case t_is_none(Bool1) orelse t_is_none(Bool2) of
true -> throw({fatal_fail, none});
false ->
- NewMap = join_maps([Map1, Map2], Map),
+ NewMap = join_maps_end([Map1, Map2], MapJ),
NewType =
case {t_atom_vals(Bool1), t_atom_vals(Bool2)} of
{['false'], ['false']} -> t_atom(false);
@@ -2493,8 +2505,9 @@ mk_guard_msg(Eval, F, Args, ArgTypes, State) ->
end
end.
-bind_guard_case_clauses(Arg, Clauses, Map, Env, Eval, State) ->
+bind_guard_case_clauses(Arg, Clauses, Map0, Env, Eval, State) ->
Clauses1 = filter_fail_clauses(Clauses),
+ Map = join_maps_begin(Map0),
{GenMap, GenArgType} = bind_guard(Arg, Map, Env, dont_know, State),
bind_guard_case_clauses(GenArgType, GenMap, Arg, Clauses1, Map, Env, Eval,
t_none(), [], State).
@@ -2594,7 +2607,7 @@ bind_guard_case_clauses(_GenArgType, _GenMap, _ArgExpr, [], Map, _Env, _Eval,
AccType, AccMaps, _State) ->
case t_is_none(AccType) of
true -> throw({fail, none});
- false -> {join_maps(AccMaps, Map), AccType}
+ false -> {join_maps_end(AccMaps, Map), AccType}
end.
%%% ===========================================================================
@@ -2604,11 +2617,34 @@ bind_guard_case_clauses(_GenArgType, _GenMap, _ArgExpr, [], Map, _Env, _Eval,
%%% ===========================================================================
map__new() ->
- {dict:new(), dict:new()}.
+ #map{}.
+
+%% join_maps_begin pushes 'modified' to the stack; join_maps pops
+%% 'modified' from the stack.
+
+join_maps_begin(#map{modified = M, modified_stack = S, ref = Ref} = Map) ->
+ Map#map{ref = make_ref(), modified = [], modified_stack = [{M,Ref} | S]}.
+
+join_maps_end(Maps, MapOut) ->
+ #map{ref = Ref, modified_stack = [{M1,R1} | S]} = MapOut,
+ true = lists:all(fun(M) -> M#map.ref =:= Ref end, Maps), % sanity
+ Keys0 = lists:usort(lists:append([M#map.modified || M <- Maps])),
+ #map{dict = Dict, subst = Subst} = MapOut,
+ Keys = [Key ||
+ Key <- Keys0,
+ dict:is_key(Key, Dict) orelse dict:is_key(Key, Subst)],
+ Out = case Maps of
+ [] -> join_maps(Maps, MapOut);
+ _ -> join_maps(Keys, Maps, MapOut)
+ end,
+ debug_join_check(Maps, MapOut, Out),
+ Out#map{ref = R1,
+ modified = Out#map.modified ++ M1, % duplicates possible
+ modified_stack = S}.
join_maps(Maps, MapOut) ->
- {Map, Subst} = MapOut,
- Keys = ordsets:from_list(dict:fetch_keys(Map) ++ dict:fetch_keys(Subst)),
+ #map{dict = Dict, subst = Subst} = MapOut,
+ Keys = ordsets:from_list(dict:fetch_keys(Dict) ++ dict:fetch_keys(Subst)),
join_maps(Keys, Maps, MapOut).
join_maps([Key|Left], Maps, MapOut) ->
@@ -2631,6 +2667,17 @@ join_maps_one_key([Map|Left], Key, AccType) ->
join_maps_one_key([], _Key, AccType) ->
AccType.
+-ifdef(DEBUG).
+debug_join_check(Maps, MapOut, Out) ->
+ #map{dict = Dict, subst = Subst} = Out,
+ #map{dict = Dict2, subst = Subst2} = join_maps(Maps, MapOut),
+ F = fun(D) -> lists:keysort(1, dict:to_list(D)) end,
+ [throw({bug, join_maps}) ||
+ F(Dict) =/= F(Dict2) orelse F(Subst) =/= F(Subst2)].
+-else.
+debug_join_check(_Maps, _MapOut, _Out) -> ok.
+-endif.
+
enter_type_lists([Key|KeyTail], [Val|ValTail], Map) ->
Map1 = enter_type(Key, Val, Map),
enter_type_lists(KeyTail, ValTail, Map1);
@@ -2643,20 +2690,21 @@ enter_type_list([{Key, Val}|Left], Map) ->
enter_type_list([], Map) ->
Map.
-enter_type(Key, Val, {Map, Subst} = MS) ->
+enter_type(Key, Val, MS) ->
case cerl:is_literal(Key) of
true -> MS;
false ->
case cerl:is_c_values(Key) of
true ->
- Keys = cerl:values_es(Key),
+ Keys = cerl:values_es(Key),
case t_is_any(Val) orelse t_is_none(Val) of
true ->
enter_type_lists(Keys, [Val || _ <- Keys], MS);
false ->
- enter_type_lists(cerl:values_es(Key), t_to_tlist(Val), MS)
+ enter_type_lists(Keys, t_to_tlist(Val), MS)
end;
false ->
+ #map{dict = Dict, subst = Subst} = MS,
KeyLabel = get_label(Key),
case dict:find(KeyLabel, Subst) of
{ok, NewKey} ->
@@ -2664,21 +2712,25 @@ enter_type(Key, Val, {Map, Subst} = MS) ->
enter_type(NewKey, Val, MS);
error ->
?debug("Entering ~p :: ~s\n", [KeyLabel, t_to_string(Val)]),
- case dict:find(KeyLabel, Map) of
+ case dict:find(KeyLabel, Dict) of
{ok, Val} -> MS;
- {ok, _OldVal} -> {dict:store(KeyLabel, Val, Map), Subst};
- error -> {dict:store(KeyLabel, Val, Map), Subst}
+ {ok, _OldVal} -> store_map(KeyLabel, Val, MS);
+ error -> store_map(KeyLabel, Val, MS)
end
end
end
end.
-enter_subst(Key, Val, {Map, Subst} = MS) ->
+store_map(Key, Val, #map{dict = Dict, ref = undefined} = Map) ->
+ Map#map{dict = dict:store(Key, Val, Dict)};
+store_map(Key, Val, #map{dict = Dict, modified = Mod} = Map) ->
+ Map#map{dict = dict:store(Key, Val, Dict), modified = [Key | Mod]}.
+
+enter_subst(Key, Val, #map{subst = Subst} = MS) ->
KeyLabel = get_label(Key),
case cerl:is_literal(Val) of
true ->
- NewMap = dict:store(KeyLabel, literal_type(Val), Map),
- {NewMap, Subst};
+ store_map(KeyLabel, literal_type(Val), MS);
false ->
case cerl:is_c_var(Val) of
false -> MS;
@@ -2691,25 +2743,29 @@ enter_subst(Key, Val, {Map, Subst} = MS) ->
if KeyLabel =:= ValLabel -> MS;
true ->
?debug("Subst: storing ~p = ~p\n", [KeyLabel, ValLabel]),
- NewSubst = dict:store(KeyLabel, ValLabel, Subst),
- {Map, NewSubst}
+ store_subst(KeyLabel, ValLabel, MS)
end
end
end
end.
-lookup_type(Key, {Map, Subst}) ->
- lookup(Key, Map, Subst, t_none()).
+store_subst(Key, Val, #map{subst = S, ref = undefined} = Map) ->
+ Map#map{subst = dict:store(Key, Val, S)};
+store_subst(Key, Val, #map{subst = S, modified = Mod} = Map) ->
+ Map#map{subst = dict:store(Key, Val, S), modified = [Key | Mod]}.
+
+lookup_type(Key, #map{dict = Dict, subst = Subst}) ->
+ lookup(Key, Dict, Subst, t_none()).
-lookup(Key, Map, Subst, AnyNone) ->
+lookup(Key, Dict, Subst, AnyNone) ->
case cerl:is_literal(Key) of
true -> literal_type(Key);
false ->
Label = get_label(Key),
case dict:find(Label, Subst) of
- {ok, NewKey} -> lookup(NewKey, Map, Subst, AnyNone);
+ {ok, NewKey} -> lookup(NewKey, Dict, Subst, AnyNone);
error ->
- case dict:find(Label, Map) of
+ case dict:find(Label, Dict) of
{ok, Val} -> Val;
error -> AnyNone
end
@@ -2744,8 +2800,8 @@ mark_as_fresh([], Map) ->
Map.
-ifdef(DEBUG).
-debug_pp_map(Map = {Map0, _Subst}) ->
- Keys = dict:fetch_keys(Map0),
+debug_pp_map(#map{dict = Dict}=Map) ->
+ Keys = dict:fetch_keys(Dict),
io:format("Map:\n", []),
lists:foreach(fun (Key) ->
io:format("\t~w :: ~s\n",