From 5341108ec6ba9465497c590679f35e8bef0c7b3f Mon Sep 17 00:00:00 2001 From: Hans Bolinder Date: Wed, 25 Jan 2017 13:48:43 +0100 Subject: dialyzer: Optimize evaluation of complex code Improve the evaluation of long lists of constraints. --- lib/dialyzer/src/dialyzer_typesig.erl | 37 +++++++++++++++++++++++++++-------- 1 file changed, 29 insertions(+), 8 deletions(-) (limited to 'lib/dialyzer/src') diff --git a/lib/dialyzer/src/dialyzer_typesig.erl b/lib/dialyzer/src/dialyzer_typesig.erl index a9ebac6c8b..a7b55d1d79 100644 --- a/lib/dialyzer/src/dialyzer_typesig.erl +++ b/lib/dialyzer/src/dialyzer_typesig.erl @@ -2,7 +2,7 @@ %%----------------------------------------------------------------------- %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2006-2016. All Rights Reserved. +%% Copyright Ericsson AB 2006-2017. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. @@ -2105,6 +2105,12 @@ v2_solve_disj([I|Is], [C|Cs], I, Map0, V2State0, UL, MapL, Eval, Uneval, end; v2_solve_disj([], [], _I, _Map, V2State, UL, MapL, Eval, Uneval, Failed) -> {ok, V2State, lists:reverse(Eval), UL, MapL, lists:reverse(Uneval), Failed}; +v2_solve_disj(every_i, Cs, I, Map, V2State, UL, MapL, Eval, Uneval, Failed) -> + NewIs = case Cs of + [] -> []; + _ -> [I|every_i] + end, + v2_solve_disj(NewIs, Cs, I, Map, V2State, UL, MapL, Eval, Uneval, Failed); v2_solve_disj(Is, [C|Cs], I, Map, V2State, UL, MapL, Eval, Uneval0, Failed) -> Uneval = [{I,C#constraint_list.id} || not is_failed_list(C, V2State)] ++ Uneval0, @@ -2176,7 +2182,7 @@ v2_solve_conj([I|Is], [Cs|Tail], I, Map0, Conj, IsFlat, V2State0, M = lists:keydelete(I, 1, vars_per_child(U, Masks)), {V2State2, NewF0} = save_updated_vars_list(AllCs, M, V2State1), {NewF, F} = lists:splitwith(fun(J) -> J < I end, NewF0), - Is1 = lists:umerge(Is, F), + Is1 = umerge_mask(Is, F), NewFs = [NewF|NewFs0], v2_solve_conj(Is1, Tail, I+1, Map, Conj, IsFlat, V2State2, [U|UL], NewFs, VarsUp, LastMap, LastFlags) @@ -2198,6 +2204,14 @@ v2_solve_conj([], _Cs, _I, Map, Conj, IsFlat, V2State, UL, NewFs, VarsUp, v2_solve_conj(NewFlags, Cs, 1, Map, Conj, IsFlat, V2State, [], [], [U|VarsUp], Map, NewFlags) end; +v2_solve_conj(every_i, Cs, I, Map, Conj, IsFlat, V2State, UL, NewFs, VarsUp, + LastMap, LastFlags) -> + NewIs = case Cs of + [] -> []; + _ -> [I|every_i] + end, + v2_solve_conj(NewIs, Cs, I, Map, Conj, IsFlat, V2State, UL, NewFs, VarsUp, + LastMap, LastFlags); v2_solve_conj(Is, [_|Tail], I, Map, Conj, IsFlat, V2State, UL, NewFs, VarsUp, LastMap, LastFlags) -> v2_solve_conj(Is, Tail, I+1, Map, Conj, IsFlat, V2State, UL, NewFs, VarsUp, @@ -2214,7 +2228,12 @@ report_detected_loop(_) -> add_mask_to_flags(Flags, [Im|M], I, L) when I > Im -> add_mask_to_flags(Flags, M, I, [Im|L]); add_mask_to_flags(Flags, [_|M], _I, L) -> - {lists:umerge(M, Flags), lists:reverse(L)}. + {umerge_mask(Flags, M), lists:reverse(L)}. + +umerge_mask(every_i, _F) -> + every_i; +umerge_mask(Is, F) -> + lists:umerge(Is, F). get_mask(V, Masks) -> case maps:find(V, Masks) of @@ -2228,7 +2247,7 @@ get_flags(#v2_state{constr_data = ConData}=V2State0, C) -> error -> ?debug("get_flags Id=~w Flags=all ~w\n", [Id, length(Cs)]), V2State = V2State0#v2_state{constr_data = maps:put(Id, {[],[]}, ConData)}, - {V2State, lists:seq(1, length(Cs))}; + {V2State, every_i}; {ok, failed} -> {V2State0, failed_list}; {ok, {Part,U}} when U =/= [] -> @@ -2989,7 +3008,7 @@ find_constraint_deps([Type|Tail], Acc) -> NewAcc = [[t_var_name(D) || D <- t_collect_vars(Type)]|Acc], find_constraint_deps(Tail, NewAcc); find_constraint_deps([], Acc) -> - lists:flatten(Acc). + lists:append(Acc). mk_constraint_1(Lhs, eq, Rhs, Deps) when Lhs < Rhs -> #constraint{lhs = Lhs, op = eq, rhs = Rhs, deps = Deps}; @@ -3097,8 +3116,8 @@ expand_to_conjunctions(#constraint_list{type = disj, list = List}) -> List1 = [C || C <- List, is_simple_constraint(C)], %% Just an assert. [] = [C || #constraint{} = C <- List1], - Expanded = lists:flatten([expand_to_conjunctions(C) - || #constraint_list{} = C <- List]), + Expanded = lists:append([expand_to_conjunctions(C) + || #constraint_list{} = C <- List]), ReturnList = Expanded ++ List1, if length(ReturnList) > ?DISJ_NORM_FORM_LIMIT -> throw(too_many_disj); true -> ReturnList @@ -3123,8 +3142,10 @@ calculate_deps(List) -> calculate_deps([H|Tail], Acc) -> Deps = get_deps(H), calculate_deps(Tail, [Deps|Acc]); +calculate_deps([], []) -> []; +calculate_deps([], [L]) -> L; calculate_deps([], Acc) -> - ordsets:from_list(lists:flatten(Acc)). + lists:umerge(Acc). mk_conj_constraint_list(List) -> mk_constraint_list(conj, List). -- cgit v1.2.3 From dd297a2ccb53bd70c4b7f218eedb4ddc5593db1d Mon Sep 17 00:00:00 2001 From: Hans Bolinder Date: Mon, 30 Jan 2017 10:15:43 +0100 Subject: dialyzer: Optimize typesig dialyzer_typesig:traverse_scc() now resets the context for each element of the SCC. Since the results of traversing the elements are saved in the 'cmap' table, there is no need to create an SCC conjunction. For huge SCCs this saves quite some time: the lift_lists() function added one element at a time, which made the calculation of deps very slow. --- lib/dialyzer/src/dialyzer_typesig.erl | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'lib/dialyzer/src') diff --git a/lib/dialyzer/src/dialyzer_typesig.erl b/lib/dialyzer/src/dialyzer_typesig.erl index a7b55d1d79..fc1e892e28 100644 --- a/lib/dialyzer/src/dialyzer_typesig.erl +++ b/lib/dialyzer/src/dialyzer_typesig.erl @@ -209,7 +209,8 @@ traverse_scc([{M,_,_}=MFA|Left], Codeserver, DefSet, ModRecs, AccState) -> {M, Rec} = lists:keyfind(M, 1, ModRecs), TmpState1 = state__set_rec_dict(AccState, Rec), DummyLetrec = cerl:c_letrec([Def], cerl:c_atom(foo)), - {NewAccState, _} = traverse(DummyLetrec, DefSet, TmpState1), + TmpState2 = state__new_constraint_context(TmpState1), + {NewAccState, _} = traverse(DummyLetrec, DefSet, TmpState2), traverse_scc(Left, Codeserver, DefSet, ModRecs, NewAccState); traverse_scc([], _Codeserver, _DefSet, _ModRecs, AccState) -> AccState. @@ -2927,8 +2928,9 @@ state__get_rec_var(Fun, #state{fun_map = Map}) -> maps:find(Fun, Map). state__finalize(State) -> - State1 = enumerate_constraints(State), - order_fun_constraints(State1). + State1 = state__new_constraint_context(State), + State2 = enumerate_constraints(State1), + order_fun_constraints(State2). %% ============================================================================ %% -- cgit v1.2.3