diff options
Diffstat (limited to 'lib/compiler/src/sys_core_fold.erl')
| -rw-r--r-- | lib/compiler/src/sys_core_fold.erl | 725 |
1 files changed, 489 insertions, 236 deletions
diff --git a/lib/compiler/src/sys_core_fold.erl b/lib/compiler/src/sys_core_fold.erl index cda3f7d81e..eb9c302334 100644 --- a/lib/compiler/src/sys_core_fold.erl +++ b/lib/compiler/src/sys_core_fold.erl @@ -70,7 +70,7 @@ -export([module/2,format_error/1]). -import(lists, [map/2,foldl/3,foldr/3,mapfoldl/3,all/2,any/2, - reverse/1,reverse/2,member/2,nth/2,flatten/1]). + reverse/1,reverse/2,member/2,nth/2,flatten/1,unzip/1]). -import(cerl, [ann_c_cons/3,ann_c_tuple/2]). @@ -246,6 +246,16 @@ expr(#c_tuple{anno=Anno,es=Es0}=Tuple, Ctxt, Sub) -> value -> ann_c_tuple(Anno, Es) end; +expr(#c_map{var=V0,es=Es0}=Map, Ctxt, Sub) -> + Es = pair_list(Es0, Ctxt, Sub), + case Ctxt of + effect -> + add_warning(Map, useless_building), + expr(make_effect_seq(Es, Sub), Ctxt, Sub); + value -> + V = expr(V0, Ctxt, Sub), + Map#c_map{var=V,es=Es} + end; expr(#c_binary{segments=Ss}=Bin0, Ctxt, Sub) -> %% Warn for useless building, but always build the binary %% anyway to preserve a possible exception. @@ -295,6 +305,10 @@ expr(#c_let{}=Let, Ctxt, Sub) -> %% Now recursively re-process the new expression. expr(Expr, Ctxt, sub_new_preserve_types(Sub)) end; +expr(#c_letrec{body=#c_var{}}=Letrec, effect, _Sub) -> + %% This is named fun in an 'effect' context. Warn and ignore. + add_warning(Letrec, useless_building), + void(); expr(#c_letrec{defs=Fs0,body=B0}=Letrec, Ctxt, Sub) -> Fs1 = map(fun ({Name,Fb}) -> {Name,expr(Fb, {letrec,Ctxt}, Sub)} @@ -302,18 +316,54 @@ expr(#c_letrec{defs=Fs0,body=B0}=Letrec, Ctxt, Sub) -> B1 = body(B0, value, Sub), Letrec#c_letrec{defs=Fs1,body=B1}; expr(#c_case{}=Case0, Ctxt, Sub) -> + %% Ideally, the compiler should only emit warnings when there is + %% a real mistake in the code being compiled. We use the follow + %% heuristics in an attempt to approach that ideal: + %% + %% * If the guard for a clause always fails, we will emit a + %% warning. + %% + %% * If a case expression is a literal, we will emit no warnings + %% for clauses that will not match or for clauses that are + %% shadowed after a clause that will always match. That means + %% that code such as: + %% + %% case ?DEBUG of + %% false -> ok; + %% true -> ... + %% end + %% + %% (where ?DEBUG expands to either 'true' or 'false') will not + %% produce any warnings. + %% + %% * If the case expression is not literal, warnings will be + %% emitted for every clause that don't match and for all + %% clauses following a clause that will always match. + %% + %% * If no clause will ever match, there will be a warning + %% (in addition to any warnings that may have been emitted + %% according to the rules above). + %% case opt_bool_case(Case0) of #c_case{arg=Arg0,clauses=Cs0}=Case1 -> Arg1 = body(Arg0, value, Sub), - {Arg2,Cs1} = case_opt(Arg1, Cs0), - Cs2 = clauses(Arg2, Cs1, Case1, Ctxt, Sub), - Case = eval_case(Case1#c_case{arg=Arg2,clauses=Cs2}, Sub), - bsm_an(Case); + LitExpr = cerl:is_literal(Arg1), + {Arg2,Cs1} = case_opt(Arg1, Cs0, Sub), + Cs2 = clauses(Arg2, Cs1, Ctxt, Sub, LitExpr), + Case = Case1#c_case{arg=Arg2,clauses=Cs2}, + warn_no_clause_match(Case1, Case), + Expr = eval_case(Case, Sub), + case move_case_into_arg(Case, Sub) of + impossible -> + bsm_an(Expr); + Other -> + expr(Other, Ctxt, sub_new_preserve_types(Sub)) + end; Other -> expr(Other, Ctxt, Sub) end; expr(#c_receive{clauses=Cs0,timeout=T0,action=A0}=Recv, Ctxt, Sub) -> - Cs1 = clauses(#c_var{name='_'}, Cs0, Recv, Ctxt, Sub), %This is all we know + Cs1 = clauses(#c_var{name='_'}, Cs0, Ctxt, Sub, false), T1 = expr(T0, value, Sub), A1 = body(A0, Ctxt, Sub), Recv#c_receive{clauses=Cs1,timeout=T1,action=A1}; @@ -377,6 +427,16 @@ expr(#c_try{anno=A,arg=E0,vars=Vs0,body=B0,evars=Evs0,handler=H0}=Try, _, Sub0) expr_list(Es, Ctxt, Sub) -> [expr(E, Ctxt, Sub) || E <- Es]. +pair_list(Es, Ctxt, Sub) -> + [pair(E, Ctxt, Sub) || E <- Es]. + +pair(#c_map_pair{key=K,val=V}, effect, Sub) -> + make_effect_seq([K,V], Sub); +pair(#c_map_pair{key=K0,val=V0}=Pair, value=Ctxt, Sub) -> + K = expr(K0, Ctxt, Sub), + V = expr(V0, Ctxt, Sub), + Pair#c_map_pair{key=K,val=V}. + bitstr_list(Es, Sub) -> [bitstr(E, Sub) || E <- Es]. @@ -547,6 +607,14 @@ eval_binary_1([#c_bitstr{val=#c_literal{val=Val},size=#c_literal{val=Sz}, error:_ -> throw(impossible) end; +eval_binary_1([#c_bitstr{val=#c_literal{},size=#c_literal{}, + unit=#c_literal{},type=#c_literal{}, + flags=#c_cons{}=Flags}=Bitstr|Ss], Acc0) -> + case cerl:fold_literal(Flags) of + #c_literal{} = Flags1 -> + eval_binary_1([Bitstr#c_bitstr{flags=Flags1}|Ss], Acc0); + _ -> throw(impossible) + end; eval_binary_1([], Acc) -> Acc; eval_binary_1(_, _) -> throw(impossible). @@ -646,7 +714,7 @@ useless_call(effect, #c_call{anno=Anno, useless_call(_, _) -> no. %% make_effect_seq([Expr], Sub) -> #c_seq{}|void() -%% Convert a list of epressions evaluated in effect context to a chain of +%% Convert a list of expressions evaluated in effect context to a chain of %% #c_seq{}. The body in the innermost #c_seq{} will be void(). %% Anything that will not have any effect will be thrown away. @@ -1452,14 +1520,14 @@ let_subst_list([], [], _) -> {[],[],[]}. %%pattern(Pat, Sub) -> pattern(Pat, Sub, Sub). -pattern(#c_var{name=V0}=Pat, Isub, Osub) -> +pattern(#c_var{}=Pat, Isub, Osub) -> case sub_is_val(Pat, Isub) of true -> V1 = make_var_name(), Pat1 = #c_var{name=V1}, {Pat1,sub_set_var(Pat, Pat1, scope_add([V1], Osub))}; false -> - {Pat,sub_del_var(Pat, scope_add([V0], Osub))} + {Pat,sub_del_var(Pat, Osub)} end; pattern(#c_literal{}=Pat, _, Osub) -> {Pat,Osub}; pattern(#c_cons{anno=Anno,hd=H0,tl=T0}, Isub, Osub0) -> @@ -1469,6 +1537,9 @@ pattern(#c_cons{anno=Anno,hd=H0,tl=T0}, Isub, Osub0) -> pattern(#c_tuple{anno=Anno,es=Es0}, Isub, Osub0) -> {Es1,Osub1} = pattern_list(Es0, Isub, Osub0), {ann_c_tuple(Anno, Es1),Osub1}; +pattern(#c_map{anno=Anno,es=Es0}=Map, Isub, Osub0) -> + {Es1,Osub1} = map_pair_pattern_list(Es0, Isub, Osub0), + {Map#c_map{anno=Anno,es=Es1},Osub1}; pattern(#c_binary{segments=V0}=Pat, Isub, Osub0) -> {V1,Osub1} = bin_pattern_list(V0, Isub, Osub0), {Pat#c_binary{segments=V1},Osub1}; @@ -1478,6 +1549,23 @@ pattern(#c_alias{var=V0,pat=P0}=Pat, Isub, Osub0) -> Osub = update_types(V1, [P1], Osub2), {Pat#c_alias{var=V1,pat=P1},Osub}. +map_pair_pattern_list(Ps0, Isub, Osub0) -> + {Ps,{_,Osub}} = mapfoldl(fun map_pair_pattern/2, {Isub,Osub0}, Ps0), + {Ps,Osub}. + +map_pair_pattern(#c_map_pair{op=#c_literal{val=exact},key=K0,val=V0}=Pair,{Isub,Osub0}) -> + {K,Osub1} = case cerl:type(K0) of + binary -> + K1 = eval_binary(K0), + case cerl:type(K1) of + literal -> {K1,Osub0}; + _ -> pattern(K0,Isub,Osub0) + end; + _ -> pattern(K0,Isub,Osub0) + end, + {V,Osub} = pattern(V0,Isub,Osub1), + {Pair#c_map_pair{key=K,val=V},{Isub,Osub}}. + bin_pattern_list(Ps0, Isub, Osub0) -> {Ps,{_,Osub}} = mapfoldl(fun bin_pattern/2, {Isub,Osub0}, Ps0), {Ps,Osub}. @@ -1522,6 +1610,9 @@ is_subst(_) -> false. %% chains so we never have to search more than once. Use orddict so %% we know the format. %% +%% In addition to the list of substitutions, we also keep track of +%% all variable currently live (the scope). +%% %% sub_subst_scope/1 adds dummy substitutions for all variables %% in the scope in order to force renaming if variables in the %% scope occurs as pattern variables. @@ -1548,8 +1639,17 @@ sub_set_name(V, Val, #sub{v=S,s=Scope,t=Tdb0}=Sub) -> Tdb = copy_type(V, Val, Tdb1), Sub#sub{v=orddict:store(V, Val, S),s=gb_sets:add(V, Scope),t=Tdb}. -sub_del_var(#c_var{name=V}, #sub{v=S,t=Tdb}=Sub) -> - Sub#sub{v=orddict:erase(V, S),t=kill_types(V, Tdb)}. +sub_del_var(#c_var{name=V}, #sub{v=S,s=Scope,t=Tdb}=Sub) -> + %% Profiling shows that for programs with many record operations, + %% sub_del_var/2 is a bottleneck. Since the scope contains all + %% variables that are live, we know that V cannot be present in S + %% if it is not in the scope. + case gb_sets:is_member(V, Scope) of + false -> + Sub#sub{s=gb_sets:insert(V, Scope)}; + true -> + Sub#sub{v=orddict:erase(V, S),t=kill_types(V, Tdb)} + end. sub_subst_var(#c_var{name=V}, Val, #sub{v=S0}) -> %% Fold chained substitutions. @@ -1559,47 +1659,50 @@ sub_subst_scope(#sub{v=S0,s=Scope}=Sub) -> S = [{-1,#c_var{name=Sv}} || Sv <- gb_sets:to_list(Scope)]++S0, Sub#sub{v=S}. -sub_is_val(#c_var{name=V}, #sub{v=S}) -> - v_is_value(V, S). - -v_is_value(Var, Sub) -> - any(fun ({_,#c_var{name=Val}}) when Val =:= Var -> true; - (_) -> false - end, Sub). - -%% clauses(E, [Clause], TopLevel, Context, Sub) -> [Clause]. -%% Trim the clauses by removing all clauses AFTER the first one which -%% is guaranteed to match. Also remove all trivially false clauses. - -clauses(E, Cs0, TopLevel, Ctxt, Sub) -> - Cs = clauses_1(E, Cs0, Ctxt, Sub), - - %% Here we want to warn if no clauses whatsoever will ever - %% match, because that is probably a mistake. - case all(fun is_compiler_generated/1, Cs) andalso - any(fun(C) -> not is_compiler_generated(C) end, Cs0) of +sub_is_val(#c_var{name=V}, #sub{v=S,s=Scope}) -> + %% When the bottleneck in sub_del_var/2 was eliminated, this + %% became the new bottleneck. Since the scope contains all + %% live variables, a variable V can only be the target for + %% a substitution if it is in the scope. + gb_sets:is_member(V, Scope) andalso v_is_value(V, S). + +v_is_value(Var, [{_,#c_var{name=Var}}|_]) -> true; +v_is_value(Var, [_|T]) -> v_is_value(Var, T); +v_is_value(_, []) -> false. + +%% warn_no_clause_match(CaseOrig, CaseOpt) -> ok +%% Generate a warning if none of the user-specified clauses +%% will match. + +warn_no_clause_match(CaseOrig, CaseOpt) -> + OrigCs = cerl:case_clauses(CaseOrig), + OptCs = cerl:case_clauses(CaseOpt), + case any(fun(C) -> not is_compiler_generated(C) end, OrigCs) andalso + all(fun is_compiler_generated/1, OptCs) of true -> %% The original list of clauses did contain at least one %% user-specified clause, but none of them will match. %% That is probably a mistake. - add_warning(TopLevel, no_clause_match); + add_warning(CaseOrig, no_clause_match); false -> %% Either there were user-specified clauses left in %% the transformed clauses, or else none of the original %% clauses were user-specified to begin with (as in 'andalso'). ok - end, + end. - Cs. +%% clauses(E, [Clause], TopLevel, Context, Sub) -> [Clause]. +%% Trim the clauses by removing all clauses AFTER the first one which +%% is guaranteed to match. Also remove all trivially false clauses. -clauses_1(E, [C0|Cs], Ctxt, Sub) -> +clauses(E, [C0|Cs], Ctxt, Sub, LitExpr) -> #c_clause{pats=Ps,guard=G} = C1 = clause(C0, E, Ctxt, Sub), %%ok = io:fwrite("~w: ~p~n", [?LINE,{E,Ps}]), case {will_match(E, Ps),will_succeed(G)} of {yes,yes} -> - Line = get_line(core_lib:get_anno(C1)), - case core_lib:is_literal(E) of + case LitExpr of false -> + Line = get_line(core_lib:get_anno(C1)), shadow_warning(Cs, Line); true -> %% If the case expression is a literal, @@ -1608,15 +1711,13 @@ clauses_1(E, [C0|Cs], Ctxt, Sub) -> ok end, [C1]; %Skip the rest - {no,_Suc} -> - clauses_1(E, Cs, Ctxt, Sub); %Skip this clause - {_Mat,no} -> + {_Mat,no} -> %Guard fails. add_warning(C1, nomatch_guard), - clauses_1(E, Cs, Ctxt, Sub); %Skip this clause + clauses(E, Cs, Ctxt, Sub, LitExpr); %Skip this clause {_Mat,_Suc} -> - [C1|clauses_1(E, Cs, Ctxt, Sub)] + [C1|clauses(E, Cs, Ctxt, Sub, LitExpr)] end; -clauses_1(_, [], _, _) -> []. +clauses(_, [], _, _, _) -> []. shadow_warning([C|Cs], none) -> add_warning(C, nomatch_shadow), @@ -1634,69 +1735,18 @@ will_succeed(#c_literal{val=true}) -> yes; will_succeed(#c_literal{val=false}) -> no; will_succeed(_Guard) -> maybe. -%% will_match(Expr, [Pattern]) -> yes | maybe | no. -%% Test if we know whether a match will succeed/fail or just don't -%% know. Be conservative. +%% will_match(Expr, [Pattern]) -> yes | maybe. +%% We KNOW that this function is only used after optimizations +%% in case_opt/4. Therefore clauses that can definitely not match +%% have already been pruned. will_match(#c_values{es=Es}, Ps) -> - will_match_list(Es, Ps, yes); + will_match_1(cerl_clauses:match_list(Ps, Es)); will_match(E, [P]) -> - will_match_1(E, P). - -will_match_1(_E, #c_var{}) -> yes; %Will always match -will_match_1(E, #c_alias{pat=P}) -> %Pattern decides - will_match_1(E, P); -will_match_1(#c_var{}, _P) -> maybe; -will_match_1(#c_tuple{es=Es}, #c_tuple{es=Ps}) -> - will_match_list(Es, Ps, yes); -will_match_1(#c_literal{val=Lit}, P) -> - will_match_lit(Lit, P); -will_match_1(_, _) -> maybe. - -will_match_list([E|Es], [P|Ps], M) -> - case will_match_1(E, P) of - yes -> will_match_list(Es, Ps, M); - maybe -> will_match_list(Es, Ps, maybe); - no -> no - end; -will_match_list([], [], M) -> M. - -will_match_lit(Cons, #c_cons{hd=Hp,tl=Tp}) -> - case Cons of - [H|T] -> - case will_match_lit(H, Hp) of - yes -> will_match_lit(T, Tp); - Other -> Other - end; - _ -> - no - end; -will_match_lit(Tuple, #c_tuple{es=Es}) -> - case is_tuple(Tuple) andalso tuple_size(Tuple) =:= length(Es) of - true -> will_match_lit_list(tuple_to_list(Tuple), Es); - false -> no - end; -will_match_lit(Bin, #c_binary{}) -> - case is_bitstring(Bin) of - true -> maybe; - false -> no - end; -will_match_lit(_, #c_var{}) -> - yes; -will_match_lit(Lit, #c_alias{pat=P}) -> - will_match_lit(Lit, P); -will_match_lit(Lit1, #c_literal{val=Lit2}) -> - case Lit1 =:= Lit2 of - true -> yes; - false -> no - end. + will_match_1(cerl_clauses:match(P, E)). -will_match_lit_list([H|T], [P|Ps]) -> - case will_match_lit(H, P) of - yes -> will_match_lit_list(T, Ps); - Other -> Other - end; -will_match_lit_list([], []) -> yes. +will_match_1({false,_}) -> maybe; +will_match_1({true,_}) -> yes. %% opt_bool_case(CoreExpr) - CoreExpr'. %% Do various optimizations to case statement that has a @@ -1895,166 +1945,274 @@ opt_bool_case_guard(Arg, [#c_clause{pats=[#c_literal{val=false}]}=Fc,Tc]) -> %% last clause is guaranteed to match so if there is only one clause %% with a pattern containing only variables then rewrite to a let. -eval_case(#c_case{arg=#c_var{name=V}, - clauses=[#c_clause{pats=[P],guard=G,body=B}|_]}=Case, - #sub{t=Tdb}=Sub) -> - case orddict:find(V, Tdb) of - {ok,Type} -> - case {will_match_type(P, Type),will_succeed(G)} of - {yes,yes} -> - {Ps,Es} = remove_non_vars(P, Type), - expr(#c_let{vars=Ps,arg=#c_values{es=Es},body=B}, - sub_new(Sub)); - {_,_} -> - eval_case_1(Case, Sub) - end; - error -> eval_case_1(Case, Sub) - end; -eval_case(Case, Sub) -> eval_case_1(Case, Sub). - -eval_case_1(#c_case{arg=E,clauses=[#c_clause{pats=Ps,body=B}]}=Case, Sub) -> - case is_var_pat(Ps) of - true -> expr(#c_let{vars=Ps,arg=E,body=B}, sub_new(Sub)); - false -> eval_case_2(E, Ps, B, Case) - end; -eval_case_1(Case, _) -> Case. - -eval_case_2(E, [P], B, Case) -> - %% Recall that there is only one clause and that it is guaranteed to match. - %% If E and P are literals, they must be the same literal and the body - %% can be used directly as there are no variables that need to be bound. - %% Otherwise, P could be an alias meaning that two or more variables - %% would be bound to E. We don't bother to optimize that case as it - %% is rather uncommon. - case core_lib:is_literal(E) andalso core_lib:is_literal(P) of - false -> Case; - true -> B - end; -eval_case_2(_, _, _, Case) -> Case. - -is_var_pat(Ps) -> - all(fun (#c_var{}) -> true; - (_Pat) -> false - end, Ps). - -will_match_type(#c_tuple{es=Es}, #c_tuple{es=Ps}) -> - will_match_list_type(Es, Ps); -will_match_type(#c_literal{val=Atom}, #c_literal{val=Atom}) -> yes; -will_match_type(#c_var{}, #c_var{}) -> yes; -will_match_type(#c_var{}, #c_alias{}) -> yes; -will_match_type(_, _) -> no. - -will_match_list_type([E|Es], [P|Ps]) -> - case will_match_type(E, P) of - yes -> will_match_list_type(Es, Ps); - no -> no - end; -will_match_list_type([], []) -> yes; -will_match_list_type(_, _) -> no. %Different length - -remove_non_vars(Ps0, Es0) -> - {Ps,Es} = remove_non_vars(Ps0, Es0, [], []), - {reverse(Ps),reverse(Es)}. - -remove_non_vars(#c_tuple{es=Ps}, #c_tuple{es=Es}, Pacc, Eacc) -> - remove_non_vars_list(Ps, Es, Pacc, Eacc); -remove_non_vars(#c_var{}=Var, #c_alias{var=Evar}, Pacc, Eacc) -> - {[Var|Pacc],[Evar|Eacc]}; -remove_non_vars(#c_var{}=Var, #c_var{}=Evar, Pacc, Eacc) -> - {[Var|Pacc],[Evar|Eacc]}; -remove_non_vars(P, E, Pacc, Eacc) -> - true = core_lib:is_literal(P) andalso core_lib:is_literal(E), %Assertion. - {Pacc,Eacc}. - -remove_non_vars_list([P|Ps], [E|Es], Pacc0, Eacc0) -> - {Pacc,Eacc} = remove_non_vars(P, E, Pacc0, Eacc0), - remove_non_vars_list(Ps, Es, Pacc, Eacc); -remove_non_vars_list([], [], Pacc, Eacc) -> - {Pacc,Eacc}. +eval_case(#c_case{arg=E,clauses=[#c_clause{pats=Ps0, + guard=#c_literal{val=true}, + body=B}]}=Case, Sub) -> + Es = case cerl:is_c_values(E) of + true -> cerl:values_es(E); + false -> [E] + end, + %% Consider: + %% + %% case SomeSideEffect() of + %% X=Y -> ... + %% end + %% + %% We must not rewrite it to: + %% + %% let <X,Y> = <SomeSideEffect(),SomeSideEffect()> in ... + %% + %% because SomeSideEffect() would be evaluated twice. + %% + %% Instead we must evaluate the case expression in an outer let + %% like this: + %% + %% let NewVar = SomeSideEffect() in + %% let <X,Y> = <NewVar,NewVar> in ... + %% + Vs = make_vars([], length(Es)), + case cerl_clauses:match_list(Ps0, Vs) of + {false,_} -> + %% This can only happen if the Core Erlang code is + %% handwritten or generated by another code generator + %% than v3_core. Assuming that the Core Erlang program + %% is correct, the clause will always match at run-time. + Case; + {true,Bs} -> + {Ps,As} = unzip(Bs), + InnerLet = cerl:c_let(Ps, core_lib:make_values(As), B), + Let = cerl:c_let(Vs, E, InnerLet), + expr(Let, sub_new(Sub)) + end; +eval_case(Case, _) -> Case. %% case_opt(CaseArg, [Clause]) -> {CaseArg,[Clause]}. -%% Try and optimise case by avoid building a tuple in -%% the case expression. Instead of building a tuple -%% in the case expression, combine the elements into -%% multiple "values". If a clause refers to the tuple -%% in the case expression (that was not built), introduce -%% a let into the guard and/or body to build the tuple. +%% Try and optimise a case by avoid building tuples or lists +%% in the case expression. Instead combine the variable parts +%% of the case expression to multiple "values". If a clause +%% refers to the constructed term in the case expression (which +%% was not built), introduce a let into the guard and/or body to +%% build the term. %% -%% case {Expr1,Expr2} of case <Expr1,Expr2> of -%% {P1,P2} -> ... <P1,P2> -> ... +%% case {ok,[Expr1,Expr2]} of case <Expr1,Expr2> of +%% {ok,[P1,P2]} -> ... <P1,P2> -> ... %% . ==> . %% . . %% . . -%% Var -> <Var1,Var2> -> -%% ... Var ... let <Var> = {Var1,Var2} -%% in ... Var ... +%% Var -> <Var1,Var2> -> +%% ... Var ... let <Var> = {ok,[Var1,Var2]} +%% in ... Var ... %% . . %% . . %% . . -%% end. end. +%% end. end. %% -case_opt(#c_tuple{anno=A,es=Es}, Cs0) -> - Cs1 = case_opt_cs(Cs0, length(Es)), - {core_lib:set_anno(core_lib:make_values(Es), A),Cs1}; -case_opt(Arg, Cs) -> {Arg,Cs}. - -case_opt_cs([#c_clause{pats=Ps0,guard=G,body=B}=C|Cs], Arity) -> - case case_tuple_pat(Ps0, Arity) of - {ok,Ps1,Avs} -> - Flet = fun ({V,Pat}, Body) -> letify(V, Pat, Body) end, - [C#c_clause{pats=Ps1, - guard=foldl(Flet, G, Avs), - body=foldl(Flet, B, Avs)}|case_opt_cs(Cs, Arity)]; - error -> %Can't match - add_warning(C, nomatch_clause_type), - case_opt_cs(Cs, Arity) +case_opt(Arg, Cs0, Sub) -> + Cs1 = [{cerl:clause_pats(C),C,[],[]} || C <- Cs0], + Args0 = case cerl:is_c_values(Arg) of + false -> [Arg]; + true -> cerl:values_es(Arg) + end, + LitExpr = cerl:is_literal(Arg), + {Args,Cs2} = case_opt_args(Args0, Cs1, Sub, LitExpr, []), + Cs = [cerl:update_c_clause(C, + reverse(Ps), + letify(Bs, cerl:clause_guard(C)), + letify(Bs, cerl:clause_body(C))) || + {[],C,Ps,Bs} <- Cs2], + {core_lib:make_values(Args),Cs}. + +case_opt_args([A0|As0], Cs0, Sub, LitExpr, Acc) -> + case case_opt_arg(A0, Sub, Cs0, LitExpr) of + error -> + %% Nothing to be done. Move on to the next argument. + Cs = [{Ps,C,[P|PsAcc],Bs} || {[P|Ps],C,PsAcc,Bs} <- Cs0], + case_opt_args(As0, Cs, Sub, LitExpr, [A0|Acc]); + {ok,As1,Cs} -> + %% The argument was either expanded (from tuple/list) or + %% removed (literal). + case_opt_args(As1++As0, Cs, Sub, LitExpr, Acc) + end; +case_opt_args([], Cs, _Sub, _LitExpr, Acc) -> + {reverse(Acc),Cs}. + +%% case_opt_arg(Expr, Sub, Clauses0, LitExpr) -> +%% {ok,Args,Clauses} | error +%% Try to expand one argument to several arguments (if tuple/list) +%% or to remove a literal argument. +%% +case_opt_arg(E0, Sub, Cs, LitExpr) -> + E = maybe_replace_var(E0, Sub), + case cerl:is_data(E) of + false -> + error; + true -> + case cerl:data_type(E) of + {atomic,_} -> + case_opt_lit(E, Cs, LitExpr); + _ -> + case_opt_data(E, Cs, LitExpr) + end + end. + +%% maybe_replace_var(Expr0, Sub) -> Expr +%% If Expr0 is a variable that has been previously matched and +%% is known to be a tuple, return the tuple instead. Otherwise +%% return Expr0 unchanged. +%% +maybe_replace_var(E, Sub) -> + case cerl:is_c_var(E) of + false -> E; + true -> maybe_replace_var_1(E, Sub) + end. + +maybe_replace_var_1(E, #sub{t=Tdb}) -> + case orddict:find(cerl:var_name(E), Tdb) of + {ok,T0} -> + case cerl:is_c_tuple(T0) of + false -> + E; + true -> + cerl_trees:map(fun(C) -> + case cerl:is_c_alias(C) of + false -> C; + true -> cerl:alias_pat(C) + end + end, T0) + end; + error -> + E + end. + +%% case_opt_lit(Literal, Clauses0, LitExpr) -> +%% {ok,[],Clauses} | error +%% The current part of the case expression is a literal. That +%% means that we will know at compile-time whether a clause +%% will match, and we can remove the corresponding pattern from +%% each clause. +%% +%% The only complication is if the literal is a binary. Binary +%% pattern matching is tricky, so we will give up in that case. + +case_opt_lit(Lit, Cs0, LitExpr) -> + try case_opt_lit_1(Cs0, Lit, LitExpr) of + Cs -> + {ok,[],Cs} + catch + throw:impossible -> + error + end. + +case_opt_lit_1([{[P|Ps],C,PsAcc,Bs0}|Cs], E, LitExpr) -> + case cerl_clauses:match(P, E) of + none -> + %% The pattern will not match the literal. Remove the clause. + %% Unless the entire case expression is a literal, also + %% emit a warning. + case LitExpr of + false -> add_warning(C, nomatch_clause_type); + true -> ok + end, + case_opt_lit_1(Cs, E, LitExpr); + {true,Bs} -> + %% The pattern matches the literal. Remove the pattern + %% and update the bindings. + [{Ps,C,PsAcc,Bs++Bs0}|case_opt_lit_1(Cs, E, LitExpr)]; + {false,_} -> + %% Binary literal and pattern. We are not sure whether + %% the pattern will match. + throw(impossible) end; -case_opt_cs([], _) -> []. +case_opt_lit_1([], _, _) -> []. + +%% case_opt_data(Expr, Clauses0, LitExpr) -> {ok,Exprs,Clauses} -%% case_tuple_pat([Pattern], Arity) -> {ok,[Pattern],[{AliasVar,Pat}]} | error. +case_opt_data(E, Cs0, LitExpr) -> + Es = cerl:data_es(E), + Cs = case_opt_data_1(Cs0, Es, + {cerl:data_type(E),cerl:data_arity(E)}, + LitExpr), + {ok,Es,Cs}. + +case_opt_data_1([{[P|Ps0],C,PsAcc,Bs0}|Cs], Es, TypeSig, LitExpr) -> + case case_data_pat(P, TypeSig) of + {ok,Ps1,Bs1} -> + [{Ps1++Ps0,C,PsAcc,Bs1++Bs0}| + case_opt_data_1(Cs, Es, TypeSig,LitExpr)]; + error -> + case LitExpr of + false -> add_warning(C, nomatch_clause_type); + true -> ok + end, + case_opt_data_1(Cs, Es, TypeSig, LitExpr) + end; +case_opt_data_1([], _, _, _) -> []. + +%% case_data_pat(Pattern, Type, Arity) -> {ok,[Pattern],[{AliasVar,Pat}]} | error. + +case_data_pat(P, TypeSig) -> + case cerl:is_data(P) of + false -> + case_data_pat_var(P, TypeSig); + true -> + case {cerl:data_type(P),cerl:data_arity(P)} of + TypeSig -> + {ok,cerl:data_es(P),[]}; + {_,_} -> + error + end + end. -case_tuple_pat([#c_tuple{es=Ps}], Arity) when length(Ps) =:= Arity -> - {ok,Ps,[]}; -case_tuple_pat([#c_literal{val=T}], Arity) when tuple_size(T) =:= Arity -> - Ps = [#c_literal{val=E} || E <- tuple_to_list(T)], - {ok,Ps,[]}; -case_tuple_pat([#c_var{anno=Anno0}=V], Arity) -> - Vars = make_vars(Anno0, 1, Arity), +%% case_data_pat_var(Pattern, {DataType,ArityType}) -> +%% {ok,[Pattern],[{AliasVar,Pat}]} +case_data_pat_var(P, {Type,Arity}=TypeSig) -> %% If the entire case statement is evaluated in an effect %% context (e.g. "case {A,B} of ... end, ok"), there will %% be a warning that a term is constructed but never used. - %% To avoid that warning, we must annotate the tuple as - %% compiler generated. - - Anno = [compiler_generated|Anno0], - {ok,Vars,[{V,#c_tuple{anno=Anno,es=Vars}}]}; -case_tuple_pat([#c_alias{var=V,pat=P}], Arity) -> - case case_tuple_pat([P], Arity) of - {ok,Ps,Avs} -> - Anno0 = core_lib:get_anno(P), - Anno = [compiler_generated|Anno0], - {ok,Ps,[{V,#c_tuple{anno=Anno,es=unalias_pat_list(Ps)}}|Avs]}; - error -> + %% To avoid that warning, we must annotate the data + %% constructor as compiler generated. + Ann = [compiler_generated|cerl:get_ann(P)], + case cerl:type(P) of + var -> + Vars = make_vars(cerl:get_ann(P), Arity), + {ok,Vars,[{P,cerl:ann_make_data(Ann, Type, Vars)}]}; + alias -> + V = cerl:alias_var(P), + Apat = cerl:alias_pat(P), + case case_data_pat(Apat, TypeSig) of + {ok,Ps,Bs} -> + {ok,Ps,[{V,cerl:ann_make_data(Ann, Type, unalias_pat_list(Ps))}|Bs]}; + error -> + error + end; + _ -> error - end; -case_tuple_pat(_, _) -> error. + end. %% unalias_pat(Pattern) -> Pattern. %% Remove all the aliases in a pattern but using the alias variables %% instead of the values. We KNOW they will be bound. -unalias_pat(#c_alias{var=V}) -> V; -unalias_pat(#c_cons{anno=Anno,hd=H0,tl=T0}) -> - H1 = unalias_pat(H0), - T1 = unalias_pat(T0), - ann_c_cons(Anno, H1, T1); -unalias_pat(#c_tuple{anno=Anno,es=Ps}) -> - ann_c_tuple(Anno, unalias_pat_list(Ps)); -unalias_pat(Atomic) -> Atomic. +unalias_pat(P) -> + case cerl:is_c_alias(P) of + true -> + cerl:alias_var(P); + false -> + case cerl:is_data(P) of + false -> + P; + true -> + Es = unalias_pat_list(cerl:data_es(P)), + cerl:update_data(P, cerl:data_type(P), Es) + end + end. unalias_pat_list(Ps) -> [unalias_pat(P) || P <- Ps]. +make_vars(A, Max) -> + make_vars(A, 1, Max). + make_vars(A, I, Max) when I =< Max -> [make_var(A)|make_vars(A, I+1, Max)]; make_vars(_, _, _) -> []. @@ -2067,6 +2225,11 @@ make_var_name() -> put(new_var_num, N+1), list_to_atom("fol"++integer_to_list(N)). +letify(Bs, Body) -> + foldr(fun({V,Val}, B) -> + letify(V, Val, B) + end, Body, Bs). + letify(#c_var{name=Vname}=Var, Val, Body) -> case core_lib:is_var_used(Vname, Body) of true -> @@ -2087,7 +2250,7 @@ opt_case_in_let_0([#c_var{name=V}], Arg, case is_simple_case_arg(Arg) andalso not core_lib:is_var_used(V, Case#c_case{arg=#c_literal{val=nil}}) of true -> - opt_bool_case(Case#c_case{arg=Arg}); + expr(opt_bool_case(Case#c_case{arg=Arg,clauses=Cs}), sub_new()); false -> Let end; @@ -2342,6 +2505,25 @@ move_let_into_expr(#c_let{vars=Lvs0,body=Lbody0}=Let, Case#c_case{arg=Cexpr,clauses=[Ca,Cb]}; {_,_,_} -> impossible end; +move_let_into_expr(#c_let{vars=Lvs0,body=Lbody0}=Let, + #c_seq{arg=Sarg0,body=Sbody0}=Seq, Sub0) -> + %% + %% let <Lvars> = do <Seq-arg> + %% <Seq-body> + %% in <Let-body> + %% + %% ==> + %% + %% do <Seq-arg> + %% let <Lvars> = <Seq-body> + %% in <Let-body> + %% + Sarg = body(Sarg0, Sub0), + Sbody1 = body(Sbody0, Sub0), + {Lvs,Sbody,Sub} = let_substs(Lvs0, Sbody1, Sub0), + Lbody = body(Lbody0, Sub), + Seq#c_seq{arg=Sarg,body=Let#c_let{vars=Lvs,arg=core_lib:make_values(Sbody), + body=Lbody}}; move_let_into_expr(_Let, _Expr, _Sub) -> impossible. is_failing_clause(#c_clause{body=B}) -> @@ -2429,6 +2611,77 @@ opt_simple_let_2(Let, Vs0, Arg0, Body, value, Sub) -> value, Sub) end. +move_case_into_arg(#c_case{arg=#c_let{vars=OuterVars0,arg=OuterArg, + body=InnerArg0}=Outer, + clauses=InnerClauses}=Inner, Sub) -> + %% + %% case let <OuterVars> = <OuterArg> in <InnerArg> of + %% <InnerClauses> + %% end + %% + %% ==> + %% + %% let <OuterVars> = <OuterArg> + %% in case <InnerArg> of <InnerClauses> end + %% + ScopeSub0 = sub_subst_scope(Sub#sub{t=[]}), + {OuterVars,ScopeSub} = pattern_list(OuterVars0, ScopeSub0), + InnerArg = body(InnerArg0, ScopeSub), + Outer#c_let{vars=OuterVars,arg=OuterArg, + body=Inner#c_case{arg=InnerArg,clauses=InnerClauses}}; +move_case_into_arg(#c_case{arg=#c_case{arg=OuterArg, + clauses=[OuterCa0,OuterCb]}=Outer, + clauses=InnerClauses}=Inner0, Sub) -> + case is_failing_clause(OuterCb) of + true -> + #c_clause{pats=OuterPats0,guard=OuterGuard0, + body=InnerArg0} = OuterCa0, + %% + %% case case <OuterArg> of + %% <OuterPats> when <OuterGuard> -> <InnerArg> + %% <OuterCb> + %% ... + %% end of + %% <InnerClauses> + %% end + %% + %% ==> + %% + %% case <OuterArg> of + %% <OuterPats> when <OuterGuard> -> + %% case <InnerArg> of <InnerClauses> end + %% <OuterCb> + %% end + %% + ScopeSub0 = sub_subst_scope(Sub#sub{t=[]}), + {OuterPats,ScopeSub} = pattern_list(OuterPats0, ScopeSub0), + OuterGuard = guard(OuterGuard0, ScopeSub), + InnerArg = body(InnerArg0, ScopeSub), + Inner = Inner0#c_case{arg=InnerArg,clauses=InnerClauses}, + OuterCa = OuterCa0#c_clause{pats=OuterPats,guard=OuterGuard, + body=Inner}, + Outer#c_case{arg=OuterArg, + clauses=[OuterCa,OuterCb]}; + false -> + impossible + end; +move_case_into_arg(#c_case{arg=#c_seq{arg=OuterArg,body=InnerArg}=Outer, + clauses=InnerClauses}=Inner, _Sub) -> + %% + %% case do <OuterArg> <InnerArg> of + %% <InnerClauses> + %% end + %% + %% ==> + %% + %% do <OuterArg> + %% case <InnerArg> of <InerClauses> end + %% + Outer#c_seq{arg=OuterArg, + body=Inner#c_case{arg=InnerArg,clauses=InnerClauses}}; +move_case_into_arg(_, _) -> + impossible. + %% In guards only, rewrite a case in a let argument like %% %% let <Var> = case <> of |