aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler/src/beam_trim.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/compiler/src/beam_trim.erl')
-rw-r--r--lib/compiler/src/beam_trim.erl132
1 files changed, 87 insertions, 45 deletions
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);
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-04 21:37:21 +0000