From 4763811e1d67a0d2ac3442d4694b4e1dee1b4364 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Mon, 4 Feb 2019 10:03:55 +0100 Subject: beam_ssa_type: Propagate the 'none' type from calls Consider this pseudo code: f(...) -> Val = case Expr of ... -> ... ; ... -> ... ; ... -> my_abort(something_went_wrong) end, %% Here follows code that uses Val. . . . my_abort(Reason) -> throw({error,Reason}). The first two clauses in the case will probably provide some information about the type of the variable `Var`, information that would be useful for optimizing the code that follows the case. However, the third clause would ruin everything. The call to `my_abort/1` could return anything, and thus `Val` could also have any type. 294d66a295f6 introduced module-level type analysis, which will in general keep track of the return type of a local function call. However, it does not improve the optimization for this specific function. When a function never returns, that is, when its type is `none`, it does not propagate the `none` type, but instead pretends that the return type is `any`. This commit extends the handling of functions that don't return to properly handle the `none` type. Any instructions that directly follows the function that does not return will be discarded, and the call will be rewritten to a tail-recursive call. For this specific example, it means that the type for `Val` deduced from the first two clauses will be retained and can be used for optimizing the code after the case. --- lib/compiler/src/beam_ssa_type.erl | 145 +++++++++++++++-------------------- lib/debugger/test/int_eval_SUITE.erl | 5 +- lib/stdlib/test/erl_eval_SUITE.erl | 12 ++- 3 files changed, 75 insertions(+), 87 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl index e51f8cdcb7..6fa02da89d 100644 --- a/lib/compiler/src/beam_ssa_type.erl +++ b/lib/compiler/src/beam_ssa_type.erl @@ -23,7 +23,7 @@ -include("beam_ssa_opt.hrl"). -import(lists, [all/2,any/2,droplast/1,foldl/3,last/1,member/2, - partition/2,reverse/1,seq/2,sort/1]). + partition/2,reverse/1,reverse/2,seq/2,sort/1]). -define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}). @@ -124,7 +124,7 @@ opt_continue_1(Linear0, Args, Id, Ts, FuncDb0) -> ls=#{0=>Ts,?BADARG_BLOCK=>#{}}, once=UsedOnce }, - {Linear, FuncDb, NewRet} = opt_1(Linear0, D, []), + {Linear, FuncDb, NewRet} = opt(Linear0, D, []), case FuncDb of #{ Id := Entry0 } -> @@ -192,57 +192,42 @@ get_func_id(Anno) -> #{func_info:={_Mod, Name, Arity}} = Anno, #b_local{name=#b_literal{val=Name}, arity=Arity}. -opt_1([{L,Blk}|Bs], #d{ls=Ls}=D, Acc) -> +opt([{L,Blk}|Bs], #d{ls=Ls}=D, Acc) -> case Ls of #{L:=Ts} -> - opt_2(L, Blk, Bs, Ts, D, Acc); + opt_1(L, Blk, Bs, Ts, D, Acc); #{} -> %% This block is never reached. Discard it. - opt_1(Bs, D, Acc) + opt(Bs, D, Acc) end; -opt_1([], D, Acc) -> +opt([], D, Acc) -> #d{func_db=FuncDb,ret_type=NewRet} = D, {reverse(Acc), FuncDb, NewRet}. -opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, #d{sub=Sub}=D0, Acc) -> - case Is0 of - [#b_set{op=call,dst=Dst, - args=[#b_remote{mod=#b_literal{val=Mod}, - name=#b_literal{val=Name}}=Rem|Args0]}=I0] -> - case erl_bifs:is_exit_bif(Mod, Name, length(Args0)) of - true -> - %% This call will never reach the successor block. - %% Rewrite the terminator to a 'ret', and remove - %% all type information for this label. That will - %% simplify the phi node in the former successor. - Args = simplify_args(Args0, Sub, Ts), - I = I0#b_set{args=[Rem|Args]}, - Ret = #b_ret{arg=Dst}, - Blk = Blk0#b_blk{is=[I],last=Ret}, - Ls = maps:remove(L, D0#d.ls), - - %% We potentially lack a return value. - RetType = join([none | D0#d.ret_type]), - - D = D0#d{ls=Ls,ret_type=[RetType]}, - opt_1(Bs, D, [{L,Blk} | Acc]); - false -> - opt_3(L, Blk0, Bs, Ts, D0, Acc) - end; - _ -> - opt_3(L, Blk0, Bs, Ts, D0, Acc) +opt_1(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, + #d{ds=Ds0,sub=Sub0,func_db=Fdb0}=D0, Acc) -> + case opt_is(Is0, Ts0, Ds0, Fdb0, D0, Sub0, []) of + {Is,Ts,Ds,Fdb,Sub} -> + D1 = D0#d{ds=Ds,sub=Sub,func_db=Fdb}, + Last1 = simplify_terminator(Last0, Sub, Ts, Ds), + Last = opt_terminator(Last1, Ts, Ds), + D = update_successors(Last, Ts, D1), + Blk = Blk0#b_blk{is=Is,last=Last}, + opt(Bs, D, [{L,Blk}|Acc]); + {no_return,Ret,Is,Ds,Fdb,Sub} -> + %% This call will never reach the successor block. + %% Rewrite the terminator to a 'ret', and remove + %% all type information for this label. That can + %% potentially narrow the type of the phi node + %% in the former successor. + Ls = maps:remove(L, D0#d.ls), + RetType = join([none|D0#d.ret_type]), + D = D0#d{ds=Ds,ls=Ls,sub=Sub, + func_db=Fdb,ret_type=[RetType]}, + Blk = Blk0#b_blk{is=Is,last=Ret}, + opt(Bs, D, [{L,Blk}|Acc]) end. -opt_3(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, - #d{ds=Ds0,ls=Ls0,sub=Sub0,func_db=Fdb0}=D0, Acc) -> - {Is,Ts,Ds,Fdb,Sub} = opt_is(Is0, Ts0, Ds0, Fdb0, Ls0, D0, Sub0, []), - D1 = D0#d{ds=Ds,sub=Sub,func_db=Fdb}, - Last1 = simplify_terminator(Last0, Sub, Ts, Ds), - Last = opt_terminator(Last1, Ts, Ds), - D = update_successors(Last, Ts, D1), - Blk = Blk0#b_blk{is=Is,last=Last}, - opt_1(Bs, D, [{L,Blk} | Acc]). - simplify_terminator(#b_br{bool=Bool}=Br, Sub, Ts, _Ds) -> Br#b_br{bool=simplify_arg(Bool, Sub, Ts)}; simplify_terminator(#b_switch{arg=Arg}=Sw, Sub, Ts, _Ds) -> @@ -256,7 +241,7 @@ simplify_terminator(#b_ret{arg=Arg}=Ret, Sub, Ts, Ds) -> end. opt_is([#b_set{op=phi,dst=Dst,args=Args0}=I0|Is], - Ts0, Ds0, Fdb, Ls, D, Sub0, Acc) -> + Ts0, Ds0, Fdb, #d{ls=Ls}=D, Sub0, Acc) -> %% Simplify the phi node by removing all predecessor blocks that no %% longer exists or no longer branches to this block. Args = [{simplify_arg(Arg, Sub0, Ts0),From} || @@ -267,43 +252,39 @@ opt_is([#b_set{op=phi,dst=Dst,args=Args0}=I0|Is], %% value or if the values are identical. [{Val,_}|_] = Args, Sub = Sub0#{Dst=>Val}, - opt_is(Is, Ts0, Ds0, Fdb, Ls, D, Sub, Acc); + opt_is(Is, Ts0, Ds0, Fdb, D, Sub, Acc); false -> I = I0#b_set{args=Args}, Ts = update_types(I, Ts0, Ds0), Ds = Ds0#{Dst=>I}, - opt_is(Is, Ts, Ds, Fdb, Ls, D, Sub0, [I|Acc]) + opt_is(Is, Ts, Ds, Fdb, D, Sub0, [I|Acc]) end; -opt_is([#b_set{op=call,args=Args0,dst=Dst}=I0 | Is], - Ts0, Ds0, Fdb0, Ls, D, Sub, Acc) -> +opt_is([#b_set{op=call,args=Args0,dst=Dst}=I0|Is], + Ts0, Ds0, Fdb0, D, Sub, Acc) -> Args = simplify_args(Args0, Sub, Ts0), I1 = beam_ssa:normalize(I0#b_set{args=Args}), - - %% This is a bit of a kludge; we know that any instruction whose return - %% type is 'none' will fail at runtime, but we don't yet have a way to cut - %% a block short so we move on like nothing nothing happened. - %% - %% This complicates argument type optimization as unreachable calls can - %% add types that will never occur, so we skip optimizing this call if - %% the type of any of its arguments is 'none'. - [_Callee | Rest] = Args, - case all(fun(Arg) -> get_type(Arg, Ts0) =/= none end, Rest) of - true -> - {Ts, Ds, Fdb, I} = opt_call(I1, D, Ts0, Ds0, Fdb0), - opt_is(Is, Ts, Ds, Fdb, Ls, D, Sub, [I|Acc]); - false -> - Ts = Ts0#{ Dst => any }, - Ds = Ds0#{ Dst => I1 }, - opt_is(Is, Ts, Ds, Fdb0, Ls, D, Sub, [I1|Acc]) + {Ts,Ds,Fdb,I} = opt_call(I1, D, Ts0, Ds0, Fdb0), + case {map_get(Dst, Ts),Is} of + {none,[#b_set{op=succeeded}]} -> + %% This call instruction is inside a try/catch + %% block. Don't attempt to optimize it. + opt_is(Is, Ts, Ds, Fdb, D, Sub, [I|Acc]); + {none,_} -> + %% This call never returns. The rest of the + %% instructions will not be executed. + Ret = #b_ret{arg=Dst}, + {no_return,Ret,reverse(Acc, [I]),Ds,Fdb,Sub}; + _ -> + opt_is(Is, Ts, Ds, Fdb, D, Sub, [I|Acc]) end; opt_is([#b_set{op=set_tuple_element}=I0|Is], - Ts0, Ds0, Fdb, Ls, D, Sub, Acc) -> + Ts0, Ds0, Fdb, D, Sub, Acc) -> %% This instruction lacks a return value and destructively updates its %% source, so it needs special handling to update the source type. {Ts, Ds, I} = opt_set_tuple_element(I0, Ts0, Ds0, Sub), - opt_is(Is, Ts, Ds, Fdb, Ls, D, Sub, [I|Acc]); + opt_is(Is, Ts, Ds, Fdb, D, Sub, [I|Acc]); opt_is([#b_set{op=succeeded,args=[Arg],dst=Dst}=I], - Ts0, Ds0, Fdb, Ls, D, Sub0, Acc) -> + Ts0, Ds0, Fdb, D, Sub0, Acc) -> case Ds0 of #{ Arg := #b_set{op=call} } -> %% The success check of a call is part of exception handling and @@ -312,22 +293,22 @@ opt_is([#b_set{op=succeeded,args=[Arg],dst=Dst}=I], Ts = update_types(I, Ts0, Ds0), Ds = Ds0#{Dst=>I}, - opt_is([], Ts, Ds, Fdb, Ls, D, Sub0, [I|Acc]); + opt_is([], Ts, Ds, Fdb, D, Sub0, [I|Acc]); #{} -> Args = simplify_args([Arg], Sub0, Ts0), Type = type(succeeded, Args, Ts0, Ds0), case get_literal_from_type(Type) of #b_literal{}=Lit -> Sub = Sub0#{Dst=>Lit}, - opt_is([], Ts0, Ds0, Fdb, Ls, D, Sub, Acc); + opt_is([], Ts0, Ds0, Fdb, D, Sub, Acc); none -> Ts = Ts0#{Dst=>Type}, Ds = Ds0#{Dst=>I}, - opt_is([], Ts, Ds, Fdb, Ls, D, Sub0, [I|Acc]) + opt_is([], Ts, Ds, Fdb, D, Sub0, [I|Acc]) end end; opt_is([#b_set{args=Args0,dst=Dst}=I0|Is], - Ts0, Ds0, Fdb, Ls, D, Sub0, Acc) -> + Ts0, Ds0, Fdb, D, Sub0, Acc) -> Args = simplify_args(Args0, Sub0, Ts0), I1 = beam_ssa:normalize(I0#b_set{args=Args}), case simplify(I1, Ts0) of @@ -335,22 +316,22 @@ opt_is([#b_set{args=Args0,dst=Dst}=I0|Is], I = beam_ssa:normalize(I2), Ts = update_types(I, Ts0, Ds0), Ds = Ds0#{Dst=>I}, - opt_is(Is, Ts, Ds, Fdb, Ls, D, Sub0, [I|Acc]); + opt_is(Is, Ts, Ds, Fdb, D, Sub0, [I|Acc]); #b_literal{}=Lit -> Sub = Sub0#{Dst=>Lit}, - opt_is(Is, Ts0, Ds0, Fdb, Ls, D, Sub, Acc); + opt_is(Is, Ts0, Ds0, Fdb, D, Sub, Acc); #b_var{}=Var -> case Is of [#b_set{op=succeeded,dst=SuccDst,args=[Dst]}] -> %% We must remove this 'succeeded' instruction. Sub = Sub0#{Dst=>Var,SuccDst=>#b_literal{val=true}}, - opt_is([], Ts0, Ds0, Fdb, Ls, D, Sub, Acc); + opt_is([], Ts0, Ds0, Fdb, D, Sub, Acc); _ -> Sub = Sub0#{Dst=>Var}, - opt_is(Is, Ts0, Ds0, Fdb, Ls, D, Sub, Acc) + opt_is(Is, Ts0, Ds0, Fdb, D, Sub, Acc) end end; -opt_is([], Ts, Ds, Fdb, _Ls, _D, Sub, Acc) -> +opt_is([], Ts, Ds, Fdb, _D, Sub, Acc) -> {reverse(Acc), Ts, Ds, Fdb, Sub}. opt_call(#b_set{dst=Dst,args=[#b_local{}=Callee|Args]}=I0, D, Ts0, Ds0, Fdb0) -> @@ -375,14 +356,13 @@ opt_call(#b_set{dst=Dst}=I, _D, Ts0, Ds0, Fdb) -> {Ts, Ds, Fdb, I}. opt_local_call(#b_set{dst=Dst,args=[Id|_]}=I0, Ts0, Ds0, Fdb) -> - %% We skip propagating 'none' as we don't yet have a good way to cut a - %% block short. Type = case Fdb of - #{ Id := #func_info{ret_type=[T]} } when T =/= none -> T; + #{ Id := #func_info{ret_type=[T]} } -> T; #{} -> any end, I = case Type of any -> I0; + none -> I0; _ -> beam_ssa:add_anno(result_type, validator_anno(Type), I0) end, Ts = Ts0#{ Dst => Type }, @@ -396,11 +376,6 @@ update_arg_types([Arg | Args], [TypeMap0 | TypeMaps], CallId, Ts) -> #t_bs_match{} -> {binary, 1}; Type -> Type end, - PrevType = maps:get(CallId, TypeMap0, NewType), - - %% The new type must be narrower than the old one. - true = meet(NewType, PrevType) =/= none, %Assertion. - TypeMap = TypeMap0#{ CallId => NewType }, [TypeMap | update_arg_types(Args, TypeMaps, CallId, Ts)]; update_arg_types([], [], _CallId, _Ts) -> diff --git a/lib/debugger/test/int_eval_SUITE.erl b/lib/debugger/test/int_eval_SUITE.erl index 0542e45142..324a44bad8 100644 --- a/lib/debugger/test/int_eval_SUITE.erl +++ b/lib/debugger/test/int_eval_SUITE.erl @@ -285,7 +285,10 @@ do_eval(Config, Mod) -> DataDir = proplists:get_value(data_dir, Config), ok = file:set_cwd(DataDir), - {ok,Mod} = compile:file(Mod, [report,debug_info]), + %% Turn off type-based optimizations across function calls, as it + %% would turn many body-recursive calls into tail-recursive calls, + %% which would change the stacktrace. + {ok,Mod} = compile:file(Mod, [no_module_opt,report,debug_info]), {module,Mod} = code:load_file(Mod), CompiledRes = Mod:Mod(), ok = io:format("Compiled:\n~p", [CompiledRes]), diff --git a/lib/stdlib/test/erl_eval_SUITE.erl b/lib/stdlib/test/erl_eval_SUITE.erl index f4019d477b..2436c8091c 100644 --- a/lib/stdlib/test/erl_eval_SUITE.erl +++ b/lib/stdlib/test/erl_eval_SUITE.erl @@ -1156,7 +1156,17 @@ simple() -> {A}. simple1() -> - erlang:error(simple). + %% If the compiler could see that this function would always + %% throw an error exception, it would rewrite simple() like this: + %% + %% simple() -> simple1(). + %% + %% That would change the stacktrace. To prevent the compiler from + %% doing that optimization, we must obfuscate the code. + case get(a_key_that_is_not_defined) of + undefined -> erlang:error(simple); + WillNeverHappen -> WillNeverHappen + end. %% Simple cases, just to cover some code. funs(Config) when is_list(Config) -> -- cgit v1.2.3