From 9212ce67e22e3f45190ded62bea82291d084351d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 1 Nov 2018 05:19:48 +0100 Subject: beam_trim: Use maps/cerl_sets instead of gb_trees/gb_sets --- lib/compiler/src/beam_trim.erl | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) (limited to 'lib/compiler/src/beam_trim.erl') diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl index 1acbedd45b..61dd94d456 100644 --- a/lib/compiler/src/beam_trim.erl +++ b/lib/compiler/src/beam_trim.erl @@ -24,7 +24,7 @@ -import(lists, [reverse/1,reverse/2,splitwith/2,sort/1]). -record(st, - {safe :: gb_sets:set(beam_asm:label()), %Safe labels. + {safe :: cerl_sets:set(beam_asm:label()), %Safe labels. lbl :: beam_utils:code_index() %Code at each label. }). @@ -132,16 +132,16 @@ create_map(Trim, []) -> (Any) -> Any end; create_map(Trim, Moves) -> - GbTree0 = [{Src,Dst-Trim} || {move,{y,Src},{y,Dst}} <- Moves], - GbTree = gb_trees:from_orddict(sort(GbTree0)), - IllegalTargets = gb_sets:from_list([Dst || {move,_,{y,Dst}} <- Moves]), + Map0 = [{Src,Dst-Trim} || {move,{y,Src},{y,Dst}} <- Moves], + Map = maps:from_list(Map0), + IllegalTargets = cerl_sets:from_list([Dst || {move,_,{y,Dst}} <- Moves]), fun({y,Y0}) when Y0 < Trim -> - case gb_trees:lookup(Y0, GbTree) of - {value,Y} -> {y,Y}; - none -> throw(not_possible) - end; + case Map of + #{Y0:=Y} -> {y,Y}; + #{} -> throw(not_possible) + end; ({y,Y}) -> - case gb_sets:is_element(Y, IllegalTargets) of + case cerl_sets:is_element(Y, IllegalTargets) of true -> throw(not_possible); false -> {y,Y-Trim} end; @@ -225,7 +225,7 @@ safe_labels([{label,L}, safe_labels(Is, [L|Acc]); safe_labels([_|Is], Acc) -> safe_labels(Is, Acc); -safe_labels([], Acc) -> gb_sets:from_list(Acc). +safe_labels([], Acc) -> cerl_sets:from_list(Acc). %% frame_layout([Instruction], [{kill,_}], St) -> %% [{kill,Reg} | {live,Reg} | {dead,Reg}] @@ -293,7 +293,7 @@ frame_size(_, _) -> throw(not_possible). frame_size_branch(0, Is, Safe) -> frame_size(Is, Safe); frame_size_branch(L, Is, Safe) -> - case gb_sets:is_member(L, Safe) of + case cerl_sets:is_element(L, Safe) of false -> throw(not_possible); true -> frame_size(Is, Safe) end. -- cgit v1.2.3 From e7b3dcde36969be9442e05b18919ecb5b61bf6a4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 1 Nov 2018 06:19:52 +0100 Subject: beam_trim, beam_jump: Print Name/Arity if there is a crash This will help investigation of compiler bugs. --- lib/compiler/src/beam_trim.erl | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'lib/compiler/src/beam_trim.erl') diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl index 61dd94d456..13cbedf3c0 100644 --- a/lib/compiler/src/beam_trim.erl +++ b/lib/compiler/src/beam_trim.erl @@ -36,10 +36,15 @@ module({Mod,Exp,Attr,Fs0,Lc}, _Opts) -> {ok,{Mod,Exp,Attr,Fs,Lc}}. function({function,Name,Arity,CLabel,Is0}) -> - %%ok = io:fwrite("~w: ~p\n", [?LINE,{Name,Arity}]), - St = #st{safe=safe_labels(Is0, []),lbl=beam_utils:index_labels(Is0)}, - Is = trim(Is0, St, []), - {function,Name,Arity,CLabel,Is}. + try + St = #st{safe=safe_labels(Is0, []),lbl=beam_utils:index_labels(Is0)}, + Is = trim(Is0, St, []), + {function,Name,Arity,CLabel,Is} + catch + Class:Error:Stack -> + io:fwrite("Function: ~w/~w\n", [Name,Arity]), + erlang:raise(Class, Error, Stack) + end. trim([{kill,_}|_]=Is0, St, Acc) -> {Kills0,Is1} = splitwith(fun({kill,_}) -> true; -- cgit v1.2.3 From ff758397d8a2e4cc6038e72bc09bcc063de1b621 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 1 Nov 2018 07:26:11 +0100 Subject: beam_trim: Stop using beam_utils:is_not_used/3 Eliminate the use of beam_utils:is_not_used/3 by implementing a simple is_not_used() function in beam_trim itself. The new version actually makes trimming possible in more circumstances, because beam_utils:is_not_used/3 was too conservative for the purpose of stack trimming (it was previously used for optimizations where it was necessary to be more conservative). Alternatives considered: I tried to implement stack trimming in beam_ssa_codegen but it turned out to be a total mess. Not surprisingly, it turns out that an optimization that renumbers Y registers is hard to do on an intermediate representation that still use variables instead of BEAM registers. --- lib/compiler/src/beam_trim.erl | 83 ++++++++++++++++++++++++++++++++++++++---- 1 file changed, 75 insertions(+), 8 deletions(-) (limited to 'lib/compiler/src/beam_trim.erl') diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl index 13cbedf3c0..0f1144e87f 100644 --- a/lib/compiler/src/beam_trim.erl +++ b/lib/compiler/src/beam_trim.erl @@ -21,12 +21,11 @@ -module(beam_trim). -export([module/2]). --import(lists, [reverse/1,reverse/2,splitwith/2,sort/1]). +-import(lists, [member/2,reverse/1,reverse/2,splitwith/2,sort/1]). -record(st, - {safe :: cerl_sets:set(beam_asm:label()), %Safe labels. - lbl :: beam_utils:code_index() %Code at each label. - }). + {safe :: cerl_sets:set(beam_asm:label()) %Safe labels. + }). -spec module(beam_utils:module_code(), [compile:option()]) -> {'ok',beam_utils:module_code()}. @@ -37,7 +36,7 @@ module({Mod,Exp,Attr,Fs0,Lc}, _Opts) -> function({function,Name,Arity,CLabel,Is0}) -> try - St = #st{safe=safe_labels(Is0, []),lbl=beam_utils:index_labels(Is0)}, + St = #st{safe=safe_labels(Is0, [])}, Is = trim(Is0, St, []), {function,Name,Arity,CLabel,Is} catch @@ -236,9 +235,9 @@ safe_labels([], Acc) -> cerl_sets:from_list(Acc). %% [{kill,Reg} | {live,Reg} | {dead,Reg}] %% Figure out the layout of the stack frame. -frame_layout(Is, Kills, #st{safe=Safe,lbl=D}) -> +frame_layout(Is, Kills, #st{safe=Safe}) -> N = frame_size(Is, Safe), - IsKilled = fun(R) -> beam_utils:is_not_used(R, Is, D) end, + IsKilled = fun(R) -> is_not_used(R, Is) end, {N,frame_layout_1(Kills, 0, N, IsKilled, [])}. frame_layout_1([{kill,{y,Y}}=I|Ks], Y, N, IsKilled, Acc) -> @@ -290,7 +289,8 @@ frame_size([{make_fun2,_,_,_,_}|Is], Safe) -> frame_size(Is, Safe); frame_size([{get_map_elements,{f,L},_,_}|Is], Safe) -> frame_size_branch(L, Is, Safe); -frame_size([{deallocate,N}|_], _) -> N; +frame_size([{deallocate,N}|_], _) -> + N; frame_size([{line,_}|Is], Safe) -> frame_size(Is, Safe); frame_size(_, _) -> throw(not_possible). @@ -302,3 +302,70 @@ frame_size_branch(L, Is, Safe) -> false -> throw(not_possible); true -> frame_size(Is, Safe) end. + +%% is_not_used(Y, [Instruction]) -> true|false. +%% Test whether the value of Y is unused in the instruction sequence. +%% Return true if the value of Y is not used, and false if it is used. +%% +%% This function handles the same instructions as frame_size/2. It +%% assumes that any labels in the instructions are safe labels. + +is_not_used(Y, [{apply,_}|Is]) -> + is_not_used(Y, Is); +is_not_used(Y, [{bif,_,{f,_},Ss,Dst}|Is]) -> + is_not_used_ss_dst(Y, Ss, Dst, Is); +is_not_used(Y, [{block,Bl}|Is]) -> + case is_not_used_block(Y, Bl) of + used -> false; + killed -> true; + transparent -> is_not_used(Y, Is) + end; +is_not_used(Y, [{bs_init,_,_,_,Ss,Dst}|Is]) -> + is_not_used_ss_dst(Y, Ss, Dst, Is); +is_not_used(Y, [{bs_put,{f,_},_,Ss}|Is]) -> + not member(Y, Ss) andalso is_not_used(Y, Is); +is_not_used(Y, [{call,_,_}|Is]) -> + is_not_used(Y, Is); +is_not_used(Y, [{call_ext,_,_}=I|Is]) -> + beam_jump:is_exit_instruction(I) orelse is_not_used(Y, Is); +is_not_used(Y, [{call_fun,_}|Is]) -> + is_not_used(Y, Is); +is_not_used(_Y, [{deallocate,_}|_]) -> + true; +is_not_used(Y, [{gc_bif,_,{f,_},_Live,Ss,Dst}|Is]) -> + is_not_used_ss_dst(Y, Ss, Dst, Is); +is_not_used(Y, [{get_map_elements,{f,_},S,{list,List}}|Is]) -> + {Ss,Ds} = beam_utils:split_even(List), + case member(Y, [S|Ss]) of + true -> + false; + false -> + member(Y, Ds) orelse is_not_used(Y, Is) + end; +is_not_used(Y, [{kill,Yreg}|Is]) -> + Y =:= Yreg orelse is_not_used(Y, Is); +is_not_used(Y, [{line,_}|Is]) -> + is_not_used(Y, Is); +is_not_used(Y, [{make_fun2,_,_,_,_}|Is]) -> + is_not_used(Y, Is); +is_not_used(Y, [{test,_,_,Ss}|Is]) -> + not member(Y, Ss) andalso is_not_used(Y, Is); +is_not_used(Y, [{test,_Op,{f,_},_Live,Ss,Dst}|Is]) -> + is_not_used_ss_dst(Y, Ss, Dst, Is). + +is_not_used_block(Y, [{set,Ds,Ss,_}|Is]) -> + case member(Y, Ss) of + true -> + used; + false -> + case member(Y, Ds) of + true -> + killed; + false -> + is_not_used_block(Y, Is) + end + end; +is_not_used_block(_Y, []) -> transparent. + +is_not_used_ss_dst(Y, Ss, Dst, Is) -> + not member(Y, Ss) andalso (Y =:= Dst orelse is_not_used(Y, Is)). -- cgit v1.2.3 From 1565b1518f77b2c078c59c2554305b7dca668f72 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 1 Nov 2018 08:18:19 +0100 Subject: beam_trim: Handle the new binary matching instructions --- lib/compiler/src/beam_trim.erl | 15 +++++++++++++++ 1 file changed, 15 insertions(+) (limited to 'lib/compiler/src/beam_trim.erl') diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl index 0f1144e87f..c11ecab927 100644 --- a/lib/compiler/src/beam_trim.erl +++ b/lib/compiler/src/beam_trim.erl @@ -166,6 +166,12 @@ try_remap([], _, _) -> throw(not_possible). remap([{block,Bl0}|Is], Map, Acc) -> Bl = remap_block(Bl0, Map, []), remap(Is, Map, [{block,Bl}|Acc]); +remap([{bs_get_tail,Src,Dst,Live}|Is], Map, Acc) -> + I = {bs_get_tail,Map(Src),Map(Dst),Live}, + remap(Is, Map, [I|Acc]); +remap([{bs_set_position,Src1,Src2}|Is], Map, Acc) -> + I = {bs_set_position,Map(Src1),Map(Src2)}, + remap(Is, Map, [I|Acc]); remap([{call_fun,_}=I|Is], Map, Acc) -> remap(Is, Map, [I|Acc]); remap([{call,_,_}=I|Is], Map, Acc) -> @@ -293,6 +299,10 @@ frame_size([{deallocate,N}|_], _) -> N; frame_size([{line,_}|Is], Safe) -> frame_size(Is, Safe); +frame_size([{bs_set_position,_,_}|Is], Safe) -> + frame_size(Is, Safe); +frame_size([{bs_get_tail,_,_,_}|Is], Safe) -> + frame_size(Is, Safe); frame_size(_, _) -> throw(not_possible). frame_size_branch(0, Is, Safe) -> @@ -320,10 +330,15 @@ is_not_used(Y, [{block,Bl}|Is]) -> killed -> true; transparent -> is_not_used(Y, Is) end; +is_not_used(Y, [{bs_get_tail,Src,Dst,_}|Is]) -> + is_not_used_ss_dst(Y, [Src], Dst, Is); is_not_used(Y, [{bs_init,_,_,_,Ss,Dst}|Is]) -> is_not_used_ss_dst(Y, Ss, Dst, Is); is_not_used(Y, [{bs_put,{f,_},_,Ss}|Is]) -> not member(Y, Ss) andalso is_not_used(Y, Is); +is_not_used(Y, [{bs_set_position,Src1,Src2}|Is]) -> + Y =/= Src1 andalso Y =/= Src2 andalso + is_not_used(Y, Is); is_not_used(Y, [{call,_,_}|Is]) -> is_not_used(Y, Is); is_not_used(Y, [{call_ext,_,_}=I|Is]) -> -- cgit v1.2.3 From ae481c6c374f4e54b6cad44aea02322c23e105b5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 1 Nov 2018 11:58:07 +0100 Subject: beam_trim: Recognize more safe labels Recognize more safe labels to enable stack trimming in more circumstances. --- lib/compiler/src/beam_trim.erl | 57 ++++++++++++++++++++++++++++++++---------- 1 file changed, 44 insertions(+), 13 deletions(-) (limited to 'lib/compiler/src/beam_trim.erl') diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl index c11ecab927..f8efc38d53 100644 --- a/lib/compiler/src/beam_trim.erl +++ b/lib/compiler/src/beam_trim.erl @@ -21,7 +21,7 @@ -module(beam_trim). -export([module/2]). --import(lists, [member/2,reverse/1,reverse/2,splitwith/2,sort/1]). +-import(lists, [any/2,member/2,reverse/1,reverse/2,splitwith/2,sort/1]). -record(st, {safe :: cerl_sets:set(beam_asm:label()) %Safe labels. @@ -221,22 +221,53 @@ remap_block([{set,Ds0,Ss0,Info}|Is], Map, Acc) -> Ss = [Map(S) || S <- Ss0], remap_block(Is, Map, [{set,Ds,Ss,Info}|Acc]); remap_block([], _, Acc) -> reverse(Acc). - -safe_labels([{label,L},{line,_},{badmatch,{Tag,_}}|Is], Acc) when Tag =/= y -> - safe_labels(Is, [L|Acc]); -safe_labels([{label,L},{line,_},{case_end,{Tag,_}}|Is], Acc) when Tag =/= y -> - safe_labels(Is, [L|Acc]); -safe_labels([{label,L},{line,_},if_end|Is], Acc) -> - safe_labels(Is, [L|Acc]); -safe_labels([{label,L}, - {block,[{set,[{x,0}],[{Tag,_}],move}]}, - {line,_}, - {call_ext,1,{extfunc,erlang,error,1}}|Is], Acc) when Tag =/= y -> - safe_labels(Is, [L|Acc]); + +%% safe_labels([Instruction], Accumulator) -> gb_set() +%% Build a gb_set of safe labels. The code at a safe +%% label does not depend on the values in a specific +%% Y register, only that all Y registers are initialized +%% so that it safe to scan the stack when an exception +%% is generated. +%% +%% In other words, code at a safe label will continue +%% to work if Y registers have been renumbered and +%% the size of the stack frame has changed. + +safe_labels([{label,L}|Is], Acc) -> + case is_safe_label(Is) of + true -> safe_labels(Is, [L|Acc]); + false -> safe_labels(Is, Acc) + end; safe_labels([_|Is], Acc) -> safe_labels(Is, Acc); safe_labels([], Acc) -> cerl_sets:from_list(Acc). +is_safe_label([{line,_}|Is]) -> + is_safe_label(Is); +is_safe_label([{badmatch,{Tag,_}}|_]) -> + Tag =/= y; +is_safe_label([{case_end,{Tag,_}}|_]) -> + Tag =/= y; +is_safe_label([{try_case_end,{Tag,_}}|_]) -> + Tag =/= y; +is_safe_label([if_end|_]) -> + true; +is_safe_label([{block,Bl}|Is]) -> + is_safe_label_block(Bl) andalso is_safe_label(Is); +is_safe_label([{call_ext,_,{extfunc,M,F,A}}|_]) -> + erl_bifs:is_exit_bif(M, F, A); +is_safe_label(_) -> false. + +is_safe_label_block([{set,Ds,Ss,_}|Is]) -> + IsYreg = fun({y,_}) -> true; + (_) -> false + end, + %% This instruction is safe if the instruction + %% neither reads or writes Y registers. + not (any(IsYreg, Ss) orelse any(IsYreg, Ds)) andalso + is_safe_label_block(Is); +is_safe_label_block([]) -> true. + %% frame_layout([Instruction], [{kill,_}], St) -> %% [{kill,Reg} | {live,Reg} | {dead,Reg}] %% Figure out the layout of the stack frame. -- cgit v1.2.3 From 0c374a1de1a4b880fe2f7dba8ef4eefafc975af7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 1 Nov 2018 16:29:06 +0100 Subject: beam_trim: Add comments about how all this works Also rename a few functions in attempt to make it clearer. --- lib/compiler/src/beam_trim.erl | 132 +++++++++++++++++++++++++++-------------- 1 file changed, 87 insertions(+), 45 deletions(-) (limited to 'lib/compiler/src/beam_trim.erl') diff --git a/lib/compiler/src/beam_trim.erl b/lib/compiler/src/beam_trim.erl index f8efc38d53..51ff580a7a 100644 --- a/lib/compiler/src/beam_trim.erl +++ b/lib/compiler/src/beam_trim.erl @@ -51,14 +51,33 @@ trim([{kill,_}|_]=Is0, St, Acc) -> end, Is0), Kills = sort(Kills0), try - {FrameSize,Layout} = frame_layout(Is1, Kills, St), - Configs = trim_instructions(Layout), - try_remap(Configs, Is1, FrameSize) - of + %% Find out the size and layout of the stack frame. + %% Example of a layout: + %% + %% [{kill,{y,0}},{dead,{y,1},{live,{y,2}},{kill,{y,3}}] + %% + %% That means that y0 and y3 are to be killed, that y1 + %% has been killed previously, and that y2 is live. + {FrameSize,Layout} = frame_layout(Is1, Kills, St), + + %% Calculate all recipes that are not worse in terms + %% of estimated execution time. The recipes are ordered + %% in descending order from how much they trim. + Recipes = trim_recipes(Layout), + + %% Try the recipes in order. A recipe may not work out because + %% a register that was previously killed may be + %% resurrected. If that happens, the next recipe, which trims + %% less, will be tried. + try_remap(Recipes, Is1, FrameSize) + of {Is,TrimInstr} -> + %% One of the recipes was applied. trim(Is, St, reverse(TrimInstr)++Acc) catch not_possible -> + %% No recipe worked out. Use the original kill + %% instructions. trim(Is1, St, reverse(Kills, Acc)) end; trim([I|Is], St, Acc) -> @@ -66,34 +85,42 @@ trim([I|Is], St, Acc) -> trim([], _, Acc) -> reverse(Acc). -%% trim_instructions([{kill,R}|{live,R}|{dead,R}]) -> {[Instruction],MapFun} -%% Figure out the sequence of moves and trim to use. +%% trim_recipes([{kill,R}|{live,R}|{dead,R}]) -> [Recipe]. +%% Recipe = {Kills,NumberToTrim,Moves} +%% Kills = [{kill,Y}] +%% Moves = [{move,SrcY,DstY}] +%% +%% Calculate how to best trim the stack and kill the correct +%% Y registers. Return a list of possible recipes. The best +%% recipe (the one that trims the most) is first in the list. +%% All of the recipes are no worse in estimated execution time +%% than the original sequences of kill instructions. -trim_instructions(Layout) -> +trim_recipes(Layout) -> Cost = length([I || {kill,_}=I <- Layout]), - trim_instructions_1(Layout, 0, [], {Cost,[]}). + trim_recipes_1(Layout, 0, [], {Cost,[]}). -trim_instructions_1([{kill,{y,Trim0}}|Ks], Trim0, Moves, Config0) -> +trim_recipes_1([{kill,{y,Trim0}}|Ks], Trim0, Moves, Recipes0) -> Trim = Trim0 + 1, - Config = save_config(Ks, Trim, Moves, Config0), - trim_instructions_1(Ks, Trim, Moves, Config); -trim_instructions_1([{dead,{y,Trim0}}|Ks], Trim0, Moves, Config0) -> + Recipes = save_recipe(Ks, Trim, Moves, Recipes0), + trim_recipes_1(Ks, Trim, Moves, Recipes); +trim_recipes_1([{dead,{y,Trim0}}|Ks], Trim0, Moves, Recipes0) -> Trim = Trim0 + 1, - Config = save_config(Ks, Trim, Moves, Config0), - trim_instructions_1(Ks, Trim, Moves, Config); -trim_instructions_1([{live,{y,Trim0}=Src}|Ks0], Trim0, Moves0, Config0) -> + Recipes = save_recipe(Ks, Trim, Moves, Recipes0), + trim_recipes_1(Ks, Trim, Moves, Recipes); +trim_recipes_1([{live,{y,Trim0}=Src}|Ks0], Trim0, Moves0, Recipes0) -> case take_last_dead(Ks0) of none -> - {_,ConfigList} = Config0, - ConfigList; + {_,RecipesList} = Recipes0, + RecipesList; {Dst,Ks} -> Trim = Trim0 + 1, Moves = [{move,Src,Dst}|Moves0], - Config = save_config(Ks, Trim, Moves, Config0), - trim_instructions_1(Ks, Trim, Moves, Config) + Recipes = save_recipe(Ks, Trim, Moves, Recipes0), + trim_recipes_1(Ks, Trim, Moves, Recipes) end; -trim_instructions_1([], _, _, {_,ConfigList}) -> - ConfigList. +trim_recipes_1([], _, _, {_,RecipesList}) -> + RecipesList. take_last_dead(L) -> take_last_dead_1(reverse(L)). @@ -104,28 +131,48 @@ take_last_dead_1([{dead,Reg}|Is]) -> {Reg,reverse(Is)}; take_last_dead_1(_) -> none. -save_config(Ks, Trim, Moves, {MaxCost,Acc}=Config) -> - case config_cost(Ks, Moves) of - Cost when Cost =< MaxCost -> - {MaxCost,[{Ks,Trim,Moves}|Acc]}; +save_recipe(Ks, Trim, Moves, {MaxCost,Acc}=Recipes) -> + case recipe_cost(Ks, Moves) of + Cost when Cost =< MaxCost -> + %% The price is right. + {MaxCost,[{Ks,Trim,Moves}|Acc]}; _Cost -> - Config + %% Too expensive. + Recipes end. -config_cost(Ks, Moves) -> +recipe_cost(Ks, Moves) -> %% We estimate that a {move,{y,_},{y,_}} instruction is roughly twice as %% expensive as a {kill,{y,_}} instruction. A {trim,_} instruction is %% roughly as expensive as a {kill,{y,_}} instruction. - config_cost_1(Ks, 1+2*length(Moves)). + recipe_cost_1(Ks, 1+2*length(Moves)). + +recipe_cost_1([{kill,_}|Ks], Cost) -> + recipe_cost_1(Ks, Cost+1); +recipe_cost_1([_|Ks], Cost) -> + recipe_cost_1(Ks, Cost); +recipe_cost_1([], Cost) -> Cost. -config_cost_1([{kill,_}|Ks], Cost) -> - config_cost_1(Ks, Cost+1); -config_cost_1([_|Ks], Cost) -> - config_cost_1(Ks, Cost); -config_cost_1([], Cost) -> Cost. +%% try_remap([Recipe], [Instruction], FrameSize) -> +%% {[Instruction],[TrimInstruction]}. +%% Try to renumber Y registers in the instruction stream. The +%% first rececipe that works will be used. +%% +%% This function will issue a `not_possible` exception if none +%% of the recipes were possible to apply. + +try_remap([R|Rs], Is, FrameSize) -> + {TrimInstr,Map} = expand_recipe(R, FrameSize), + try + {remap(Is, Map, []),TrimInstr} + catch + throw:not_possible -> + try_remap(Rs, Is, FrameSize) + end; +try_remap([], _, _) -> throw(not_possible). -expand_config({Layout,Trim,Moves}, FrameSize) -> +expand_recipe({Layout,Trim,Moves}, FrameSize) -> Kills = [Kill || {kill,_}=Kill <- Layout], {Kills++reverse(Moves, [{trim,Trim,FrameSize-Trim}]),create_map(Trim, Moves)}. @@ -153,16 +200,6 @@ create_map(Trim, Moves) -> (Any) -> Any end. -try_remap([C|Cs], Is, FrameSize) -> - {TrimInstr,Map} = expand_config(C, FrameSize), - try - {remap(Is, Map, []),TrimInstr} - catch - throw:not_possible -> - try_remap(Cs, Is, FrameSize) - end; -try_remap([], _, _) -> throw(not_possible). - remap([{block,Bl0}|Is], Map, Acc) -> Bl = remap_block(Bl0, Map, []), remap(Is, Map, [{block,Bl}|Acc]); @@ -215,7 +252,7 @@ remap([return|_]=Is, _, Acc) -> reverse(Acc, Is); remap([{line,_}=I|Is], Map, Acc) -> remap(Is, Map, [I|Acc]). - + remap_block([{set,Ds0,Ss0,Info}|Is], Map, Acc) -> Ds = [Map(D) || D <- Ds0], Ss = [Map(S) || S <- Ss0], @@ -294,6 +331,11 @@ frame_layout_2(Is) -> reverse(Is). %% frame_size([Instruction], SafeLabels) -> FrameSize %% Find out the frame size by looking at the code that follows. +%% +%% Implicitly, also check that the instructions are a straight +%% sequence of code that ends in a return. Any branches are +%% to safe labels (i.e., the code at those labels don't depend +%% on the contents of any Y register). frame_size([{block,_}|Is], Safe) -> frame_size(Is, Safe); -- cgit v1.2.3