From 7a47b20c3accf323bdbf7bcf9c86fbf8b2c18e20 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Wed, 22 Jul 2015 09:45:04 +0200
Subject: beam_block: Clean up optimization of move optimizations

The 'move' optimization was relatively clean until GC BIFs
were introduced. Instead of re-thinking the implementation,
the existing code was fixed and patched.

The current code unsuccessfully attempts to eliminate 'move'
instructions across GC BIF and allocation instructions. We can
simplify the code if we give up as soon as we encounter any
instruction that allocates.
---
 lib/compiler/src/beam_block.erl | 83 ++++++++++++++++++-----------------------
 1 file changed, 37 insertions(+), 46 deletions(-)

(limited to 'lib/compiler')

diff --git a/lib/compiler/src/beam_block.erl b/lib/compiler/src/beam_block.erl
index 4861a2d7ec..58e8f77a2c 100644
--- a/lib/compiler/src/beam_block.erl
+++ b/lib/compiler/src/beam_block.erl
@@ -287,60 +287,51 @@ opt_moves(Ds, Is) ->
 %%  If there is a {move,Dest,FinalDest} instruction
 %%  in the instruction stream, remove the move instruction
 %%  and let FinalDest be the destination.
-%%
-%%  For this optimization to be safe, we must be sure that
-%%  Dest will not be referenced in any other by other instructions
-%%  in the rest of the instruction stream. Not even the indirect
-%%  reference by an instruction that may allocate (such as
-%%  test_heap/2 or a GC Bif) is allowed.
 
 opt_move(Dest, Is) ->
-    opt_move_1(Dest, Is, ?MAXREG, []).
-
-opt_move_1(R, [{set,_,_,{alloc,Live,_}}|_]=Is, SafeRegs, Acc) when Live < SafeRegs ->
-    %% Downgrade number of safe regs and rescan the instruction, as it most probably
-    %% is a gc_bif instruction.
-    opt_move_1(R, Is, Live, Acc);
-opt_move_1(R, [{set,[{x,X}=D],[R],move}|Is], SafeRegs, Acc) ->
-    case X < SafeRegs andalso beam_utils:is_killed_block(R, Is) of
-	true -> opt_move_2(D, Acc, Is);
-	false -> not_possible
-    end;
-opt_move_1(R, [{set,[D],[R],move}|Is], _SafeRegs, Acc) ->
+    opt_move_1(Dest, Is, []).
+
+opt_move_1(R, [{set,[D],[R],move}|Is], Acc) ->
+    %% Check whether this instruction can be safely eliminated.
+    %% First check that the source (R) is not used by the
+    %% instructions that follow.
     case beam_utils:is_killed_block(R, Is) of
-	true -> opt_move_2(D, Acc, Is);
+	true -> opt_move_rev(D, Acc, Is);
 	false -> not_possible
     end;
-opt_move_1(R, [I|Is], SafeRegs, Acc) ->
-    case is_transparent(R, I) of
-	false -> not_possible;
-	true -> opt_move_1(R, Is, SafeRegs, [I|Acc])
-    end.
+opt_move_1({x,_}, [{set,_,_,{alloc,_,_}}|_], _) ->
+    %% The optimization is not possible. If the X register is not
+    %% killed by allocation, the optimization would not be safe.
+    %% If the X register is killed, it means that there cannot
+    %% follow a 'move' instruction with this X register as the
+    %% source.
+    not_possible;
+opt_move_1(R, [{set,_,_,_}=I|Is], Acc) ->
+    %% If the source register is either killed or used by this
+    %% instruction, the optimimization is not possible.
+    case is_killed_or_used(R, I) of
+	true -> not_possible;
+	false -> opt_move_1(R, Is, [I|Acc])
+    end;
+opt_move_1(_, _, _) ->
+    not_possible.
 
-%% Reverse the instructions, while checking that there are no instructions that
-%% would interfere with using the new destination register chosen.
+%% Reverse the instructions, while checking that there are no
+%% instructions that would interfere with using the new destination
+%% register (D).
 
-opt_move_2(D, [I|Is], Acc) ->
-    case is_transparent(D, I) of
-	false -> not_possible;
-	true -> opt_move_2(D, Is, [I|Acc])
-    end;
-opt_move_2(D, [], Acc) -> {D,Acc}.
-
-%% is_transparent(Register, Instruction) -> true | false
-%%  Returns true if Instruction does not in any way references Register
-%%  (even indirectly by an allocation instruction).
-%%  Returns false if Instruction does reference Register, or we are
-%%  not sure.
-
-is_transparent({x,X}, {set,_,_,{alloc,Live,_}}) when X < Live ->
-    false;
-is_transparent(R, {set,Ds,Ss,_Op}) ->
-    case member(R, Ds) of
-	true -> false;
-	false -> not member(R, Ss)
+opt_move_rev(D, [I|Is], Acc) ->
+    case is_killed_or_used(D, I) of
+	true -> not_possible;
+	false -> opt_move_rev(D, Is, [I|Acc])
     end;
-is_transparent(_, _) -> false.
+opt_move_rev(D, [], Acc) -> {D,Acc}.
+
+%% is_killed_or_used(Register, {set,_,_,_}) -> bool()
+%%  Test whether the register is used by the instruction.
+
+is_killed_or_used(R, {set,Ss,Ds,_}) ->
+    member(R, Ds) orelse member(R, Ss).
 
 %% opt_alloc(Instructions) -> Instructions'
 %%  Optimises all allocate instructions.
-- 
cgit v1.2.3