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.

2 files changed, 26 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.
diff --git a/lib/compiler/test/guard_SUITE.erl b/lib/compiler/test/guard_SUITE.erl
index 8db47ffa40..08279d9408 100644
--- a/lib/compiler/test/guard_SUITE.erl
+++ b/lib/compiler/test/guard_SUITE.erl
@@ -1802,6 +1802,12 @@ bad_guards(Config) when is_list(Config) ->
     fc(catch bad_guards_2(#{a=>0,b=>0}, [x])),
     fc(catch bad_guards_2(not_a_map, [x])),
     fc(catch bad_guards_2(42, [x])),
+
+    fc(catch bad_guards_3(#{a=>0,b=>0}, [])),
+    fc(catch bad_guards_3(#{a=>0,b=>0}, [x])),
+    fc(catch bad_guards_3(not_a_map, [x])),
+    fc(catch bad_guards_3(42, [x])),
+
     ok.
 
 %% beam_bool used to produce GC BIF instructions whose
@@ -1813,6 +1819,12 @@ bad_guards_1(X, [_]) when {{X}}, -X ->
 bad_guards_2(M, [_]) when M#{a := 0, b => 0}, map_size(M) ->
     ok.
 
+%% beam_type used to produce an GC BIF instruction whose Live operand
+%% included uninitialized registers.
+
+bad_guards_3(M, [_]) when is_map(M) andalso M#{a := 0, b => 0}, length(M) ->
+    ok.
+
 %% Call this function to turn off constant propagation.
 id(I) -> I.