From 60d4e673149aaa34e977e42aabeef3efd4b7c34e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 20 Sep 2018 04:23:12 +0200 Subject: Move optimization of 'move' from beam_flatten to beam_ssa_codegen The purpose of beam_flatten is to eliminate the blocks created by beam_block, but it also does a few optimizations because at the time the optimizations were added, beam_flatten was the most convenient place. Move the optimization that places `{move,Something,{x,0}}` before `call` instructions from beam_flatten to beam_ssa_codegen. This change will very slightly improve compilation times, and it will also apply the optimization in more places. In particular, a `{move,Literal,{x,0}}` would never be moved passed a `trim` instruction before this change. Now it will. --- lib/compiler/src/beam_flatten.erl | 33 +---------------- lib/compiler/src/beam_ssa_codegen.erl | 68 +++++++++++++++++++++++++++++++++-- 2 files changed, 67 insertions(+), 34 deletions(-) diff --git a/lib/compiler/src/beam_flatten.erl b/lib/compiler/src/beam_flatten.erl index 973d16a1bc..c8bc1b7b84 100644 --- a/lib/compiler/src/beam_flatten.erl +++ b/lib/compiler/src/beam_flatten.erl @@ -32,8 +32,7 @@ module({Mod,Exp,Attr,Fs,Lc}, _Opt) -> {ok,{Mod,Exp,Attr,[function(F) || F <- Fs],Lc}}. function({function,Name,Arity,CLabel,Is0}) -> - Is1 = block(Is0), - Is = opt(Is1), + Is = block(Is0), {function,Name,Arity,CLabel,Is}. block(Is) -> @@ -115,33 +114,3 @@ insert_alloc_1([{bs_init=Op,Fail,Info0,Live,Ss,Dst}|Is], reverse(Acc, [I|Is]); insert_alloc_1([{bs_put,_,_,_}=I|Is], Alloc, Acc) -> insert_alloc_1(Is, Alloc, [I|Acc]). - -%% opt(Is0) -> Is -%% Simple peep-hole optimization to move a {move,Any,{x,0}} past -%% any kill up to the next call instruction. (To give the loader -%% an opportunity to combine the 'move' and the 'call' instructions.) -%% -opt(Is) -> - opt_1(Is, []). - -opt_1([{move,_,{x,0}}=I|Is0], Acc0) -> - case move_past_kill(Is0, I, Acc0) of - impossible -> opt_1(Is0, [I|Acc0]); - {Is,Acc} -> opt_1(Is, Acc) - end; -opt_1([I|Is], Acc) -> - opt_1(Is, [I|Acc]); -opt_1([], Acc) -> reverse(Acc). - -move_past_kill([{kill,Src}|_], {move,Src,_}, _) -> - impossible; -move_past_kill([{kill,_}=I|Is], Move, Acc) -> - move_past_kill(Is, Move, [I|Acc]); -move_past_kill([{trim,N,_}=I|Is], {move,Src,Dst}=Move, Acc) -> - case Src of - {y,Y} when Y < N-> impossible; - {y,Y} -> {Is,[{move,{y,Y-N},Dst},I|Acc]}; - _ -> {Is,[Move,I|Acc]} - end; -move_past_kill(Is, Move, Acc) -> - {Is,[Move|Acc]}. diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl index 5085c950b5..cae9920f40 100644 --- a/lib/compiler/src/beam_ssa_codegen.erl +++ b/lib/compiler/src/beam_ssa_codegen.erl @@ -1196,11 +1196,40 @@ bif_to_test(Name, Args, Fail) -> opt_call_moves(Is0, Arity) -> {Moves0,Is} = splitwith(fun({move,_,_}) -> true; + ({kill,_}) -> true; (_) -> false end, Is0), Moves = opt_call_moves_1(Moves0, Arity), Moves ++ Is. +opt_call_moves_1([{move,Src,{x,_}=Tmp}=M1|[{kill,_}|_]=Is], Arity) -> + %% There could be a {move,Tmp,{x,0}} instruction after the + %% kill/1 instructions (moved to there by opt_move_to_x0/1). + case splitwith(fun({kill,_}) -> true; + (_) -> false + end, Is) of + {Kills,[{move,{x,_}=Tmp,{x,0}}=M2]} -> + %% The two move/2 instructions (M1 and M2) can be combined + %% to one. The question is, though, is it safe to place + %% them after the kill/1 instructions? + case is_killed(Src, Kills, Arity) of + true -> + %% Src (a Y register) is killed by one of the + %% kill/1 instructions. Thus M1 and M2 + %% must be placed before the kill/1 instructions + %% (essentially undoing what opt_move_to_x0/1 + %% did, which turned out to be a pessimization + %% in this case). + opt_call_moves_1([M1,M2|Kills], Arity); + false -> + %% Src is not killed by any of the kill/1 + %% instructions. Thus it is safe to place + %% M1 and M2 after the kill/1 instructions. + opt_call_moves_1(Kills++[M1,M2], Arity) + end; + {_,_} -> + [M1|Is] + end; opt_call_moves_1([{move,Src,{x,_}=Tmp}=M1,{move,Tmp,Dst}=M2|Is], Arity) -> case is_killed(Tmp, Is, Arity) of true -> @@ -1214,6 +1243,10 @@ opt_call_moves_1([M|Ms], Arity) -> [M|opt_call_moves_1(Ms, Arity)]; opt_call_moves_1([], _Arity) -> []. +is_killed(Y, [{kill,Y}|_], _) -> + true; +is_killed(R, [{kill,_}|Is], Arity) -> + is_killed(R, Is, Arity); is_killed(R, [{move,R,_}|_], _) -> false; is_killed(R, [{move,_,R}|_], _) -> @@ -1221,7 +1254,9 @@ is_killed(R, [{move,_,R}|_], _) -> is_killed(R, [{move,_,_}|Is], Arity) -> is_killed(R, Is, Arity); is_killed({x,X}, [], Arity) -> - X >= Arity. + X >= Arity; +is_killed({y,_}, [], _) -> + false. cg_alloc(#cg_alloc{stack=none,words=#need{h=0,f=0}}, _St) -> []; @@ -1621,12 +1656,41 @@ phi_copies([#b_set{dst=Dst,args=PhiArgs}|Sets], L) -> [#cg_set{op=copy,dst=Dst,args=CopyArgs}|phi_copies(Sets, L)]; phi_copies([], _) -> []. +%% opt_move_to_x0([Instruction]) -> [Instruction]. +%% Simple peep-hole optimization to move a {move,Any,{x,0}} past +%% any kill up to the next call instruction. (To give the loader +%% an opportunity to combine the 'move' and the 'call' instructions.) + +opt_move_to_x0(Moves) -> + opt_move_to_x0(Moves, []). + +opt_move_to_x0([{move,_,{x,0}}=I|Is0], Acc0) -> + case move_past_kill(Is0, I, Acc0) of + impossible -> opt_move_to_x0(Is0, [I|Acc0]); + {Is,Acc} -> opt_move_to_x0(Is, Acc) + end; +opt_move_to_x0([I|Is], Acc) -> + opt_move_to_x0(Is, [I|Acc]); +opt_move_to_x0([], Acc) -> reverse(Acc). + +move_past_kill([{kill,Src}|_], {move,Src,_}, _) -> + impossible; +move_past_kill([{kill,_}=I|Is], Move, Acc) -> + move_past_kill(Is, Move, [I|Acc]); +move_past_kill(Is, Move, Acc) -> + {Is,[Move|Acc]}. + %% setup_args(Args, Anno, Context) -> [Instruction]. %% setup_args(Args) -> [Instruction]. %% Set up X registers for a call. setup_args(Args, Anno, none, St) -> - setup_args(Args) ++ kill_yregs(Anno, St); + case {setup_args(Args),kill_yregs(Anno, St)} of + {Moves,[]} -> + Moves; + {Moves,Kills} -> + opt_move_to_x0(Moves ++ Kills) + end; setup_args(Args, _, _, _) -> setup_args(Args). -- cgit v1.2.3