beam_type: Use the complete register map when calculating liveness

When calculating the number of live registers for allocation
instruction, it is not always safe to start with the number of live
registers at the start of the block. We will need to use the register
map to know whether there are any holes (dead registers) that are not
subsequently filled.

If the allocation instruction already has a number of live registers
calculated, there is nothing to be gained by raising it.

1 files changed, 14 insertions, 13 deletions

diff --git a/lib/compiler/src/beam_type.erl b/lib/compiler/src/beam_type.erl
index 8dd6e5f1c6..26c933481a 100644
--- a/lib/compiler/src/beam_type.erl
+++ b/lib/compiler/src/beam_type.erl
@@ -329,27 +329,27 @@ build_alloc(Words, Floats) -> {alloc,[{words,Words},{floats,Floats}]}.
 
 %% flt_liveness([Instruction]) -> [Instruction]
 %%  (Re)calculate the number of live registers for each heap allocation
-%%  function. We base liveness of the number of live registers at
-%%  entry to the instruction sequence.
+%%  function. We base liveness of the number of register map at the
+%%  beginning of the instruction sequence.
 %%
 %%  A 'not_possible' term will be thrown if the set of live registers
 %%  is not continous at an allocation function (e.g. if {x,0} and {x,2}
 %%  are live, but not {x,1}).
 
-flt_liveness([{'%live',Live,_}=LiveInstr|Is]) ->
-    flt_liveness_1(Is, init_regs(Live), [LiveInstr]).
+flt_liveness([{'%live',_Live,Regs}=LiveInstr|Is]) ->
+    flt_liveness_1(Is, Regs, [LiveInstr]).
 
-flt_liveness_1([{set,Ds,Ss,{alloc,_,Alloc}}|Is], Regs0, Acc) ->
-    Live = live_regs(Regs0),
+flt_liveness_1([{set,Ds,Ss,{alloc,Live0,Alloc}}|Is], Regs0, Acc) ->
+    Live = min(Live0, live_regs(Regs0)),
     I = {set,Ds,Ss,{alloc,Live,Alloc}},
-    Regs = foldl(fun(R, A) -> set_live(R, A) end, Regs0, Ds),
+    Regs1 = init_regs(Live),
+    Regs = x_live(Ds, Regs1),
     flt_liveness_1(Is, Regs, [I|Acc]);
 flt_liveness_1([{set,Ds,_,_}=I|Is], Regs0, Acc) ->
-    Regs = foldl(fun(R, A) -> set_live(R, A) end, Regs0, Ds),
+    Regs = x_live(Ds, Regs0),
     flt_liveness_1(Is, Regs, [I|Acc]);
-flt_liveness_1([{'%live',_,_}=I|Is], Regs, Acc) ->
-    flt_liveness_1(Is, Regs, [I|Acc]);
-flt_liveness_1([], _Regs, Acc) -> reverse(Acc).
+flt_liveness_1([{'%live',_,_}], _Regs, Acc) ->
+    reverse(Acc).
 
 init_regs(Live) ->
     (1 bsl Live) - 1.
@@ -364,8 +364,9 @@ live_regs_1(R, N) ->
 	1 -> live_regs_1(R bsr 1, N+1)
     end.
 
-set_live({x,X}, Regs) -> Regs bor (1 bsl X);
-set_live(_, Regs) -> Regs.
+x_live([{x,N}|Rs], Regs) -> x_live(Rs, Regs bor (1 bsl N));
+x_live([_|Rs], Regs) -> x_live(Rs, Regs);
+x_live([], Regs) -> Regs.
 
 %% update(Instruction, TypeDb) -> NewTypeDb
 %%  Update the type database to account for executing an instruction.