Ensure that the stack slots are initialized when matching maps

When matching a map, the compiler could fail to generate code that
would initialize all stack slots (Y registers) properly. Here is a
general outline of code that *could* cause this problem:

    foo(Key, Map) ->
         Res = case Map of
                  #{Key := Val} ->
                      %% Do something with Val here.
		        .
			.
			.
                  #{} ->
		      []
              end,
	%% The stack slot for Val might not have been initialized
	%% here if the key was not present in the map.
	.
	.
	.
	%% Use Res.
	.
	.
	.

The code generator would wrongly assume that the map matching would
always initialize the stack slot, and if nothing else happened to
force that stack slot to be initialized, it would remain
uninitialized, which would likely crash the runtime system at the next
garbage collection.

`beam_validator` is supposed to find these kind of problems, but a bug
in `beam_validator` prevented it from detecting this problem.

https://bugs.erlang.org/browse/ERL-1017

3 files changed, 56 insertions, 11 deletions

diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl
index 07f4c8b461..08641e2abc 100644
--- a/lib/compiler/src/beam_ssa_codegen.erl
+++ b/lib/compiler/src/beam_ssa_codegen.erl
@@ -764,9 +764,8 @@ defined(Linear, #cg{regs=Regs}) ->
 
 def([{L,#cg_blk{is=Is0,last=Last}=Blk0}|Bs], DefMap0, Regs) ->
     Def0 = def_get(L, DefMap0),
-    {Is,Def} = def_is(Is0, Regs, Def0, []),
-    Successors = successors(Last),
-    DefMap = def_successors(Successors, Def, DefMap0),
+    {Is,Def,MaybeDef} = def_is(Is0, Regs, Def0, []),
+    DefMap = def_successors(Last, Def, MaybeDef, DefMap0),
     Blk = Blk0#cg_blk{is=Is},
     [{L,Blk}|def(Bs, DefMap, Regs)];
 def([], _, _) -> [].
@@ -780,6 +779,11 @@ def_get(L, DefMap) ->
 def_is([#cg_alloc{anno=Anno0}=I0|Is], Regs, Def, Acc) ->
     I = I0#cg_alloc{anno=Anno0#{def_yregs=>Def}},
     def_is(Is, Regs, Def, [I|Acc]);
+def_is([#cg_set{op=succeeded,args=[Var]}=I], Regs, Def, Acc) ->
+    %% Var will only be defined on the success branch of the `br`
+    %% for this block.
+    MaybeDef = def_add_yreg(Var, [], Regs),
+    {reverse(Acc, [I]),Def,MaybeDef};
 def_is([#cg_set{op=kill_try_tag,args=[#b_var{}=Tag]}=I|Is], Regs, Def0, Acc) ->
     Def = ordsets:del_element(Tag, Def0),
     def_is(Is, Regs, Def, [I|Acc]);
@@ -822,7 +826,7 @@ def_is([#cg_set{anno=Anno0,dst=Dst}=I0|Is], Regs, Def0, Acc) ->
     Def = def_add_yreg(Dst, Def0, Regs),
     def_is(Is, Regs, Def, [I|Acc]);
 def_is([], _, Def, Acc) ->
-    {reverse(Acc),Def}.
+    {reverse(Acc),Def,[]}.
 
 def_add_yreg(Dst, Def, Regs) ->
     case is_yreg(Dst, Regs) of
@@ -830,6 +834,12 @@ def_add_yreg(Dst, Def, Regs) ->
         false -> Def
     end.
 
+def_successors(#cg_br{bool=#b_var{},succ=Succ,fail=Fail}, Def, MaybeDef, DefMap0) ->
+    DefMap = def_successors([Fail], ordsets:subtract(Def, MaybeDef), DefMap0),
+    def_successors([Succ], Def, DefMap);
+def_successors(Last, Def, [], DefMap) ->
+    def_successors(successors(Last), Def, DefMap).
+
 def_successors([S|Ss], Def0, DefMap) ->
     case DefMap of
         #{S:=Def1} ->
diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index ebe9631e09..370481d08a 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -1068,8 +1068,11 @@ verify_get_map(Fail, Src, List, Vst0) ->
 %%    {get_map_elements,{f,7},{x,1},{list,[{atom,a},{x,1},{atom,b},{x,2}]}}.
 %%
 %% If 'a' exists but not 'b', {x,1} is overwritten when we jump to {f,7}.
+%%
+%% We must be careful to preserve the uninitialized status for Y registers
+%% that have been allocated but not yet defined.
 clobber_map_vals([Key,Dst|T], Map, Vst0) ->
-    case is_reg_defined(Dst, Vst0) of
+    case is_reg_initialized(Dst, Vst0) of
         true ->
             Vst = extract_term(term, {bif,map_get}, [Key, Map], Dst, Vst0),
             clobber_map_vals(T, Map, Vst);
@@ -1079,6 +1082,17 @@ clobber_map_vals([Key,Dst|T], Map, Vst0) ->
 clobber_map_vals([], _Map, Vst) ->
     Vst.
 
+is_reg_initialized({x,_}=Reg, #vst{current=#st{xs=Xs}}) ->
+    is_map_key(Reg, Xs);
+is_reg_initialized({y,_}=Reg, #vst{current=#st{ys=Ys}}) ->
+    case Ys of
+        #{Reg:=Val} ->
+            Val =/= uninitialized;
+        #{} ->
+            false
+    end;
+is_reg_initialized(V, #vst{}) -> error({not_a_register, V}).
+
 extract_map_keys([Key,_Val|T]) ->
     [Key|extract_map_keys(T)];
 extract_map_keys([]) -> [].
@@ -1885,10 +1899,6 @@ check_try_catch_tags(Type, {y,N}=Reg, Vst) ->
             ok
     end.
 
-is_reg_defined({x,_}=Reg, #vst{current=#st{xs=Xs}}) -> is_map_key(Reg, Xs);
-is_reg_defined({y,_}=Reg, #vst{current=#st{ys=Ys}}) -> is_map_key(Reg, Ys);
-is_reg_defined(V, #vst{}) -> error({not_a_register, V}).
-
 assert_term(Src, Vst) ->
     _ = get_term_type(Src, Vst),
     ok.
diff --git a/lib/compiler/test/beam_ssa_SUITE.erl b/lib/compiler/test/beam_ssa_SUITE.erl
index dd1b7ddcd3..6f99b0e28e 100644
--- a/lib/compiler/test/beam_ssa_SUITE.erl
+++ b/lib/compiler/test/beam_ssa_SUITE.erl
@@ -23,7 +23,7 @@
 	 init_per_group/2,end_per_group/2,
          calls/1,tuple_matching/1,recv/1,maps/1,
          cover_ssa_dead/1,combine_sw/1,share_opt/1,
-         beam_ssa_dead_crash/1]).
+         beam_ssa_dead_crash/1,stack_init/1]).
 
 suite() -> [{ct_hooks,[ts_install_cth]}].
 
@@ -39,7 +39,8 @@ groups() ->
        cover_ssa_dead,
        combine_sw,
        share_opt,
-       beam_ssa_dead_crash
+       beam_ssa_dead_crash,
+       stack_init
       ]}].
 
 init_per_suite(Config) ->
@@ -589,6 +590,30 @@ do_beam_ssa_dead_crash(A, B) ->
             end
     end.
 
+stack_init(_Config) ->
+    6 = stack_init(a, #{a => [1,2,3]}),
+    0 = stack_init(missing, #{}),
+    ok.
+
+stack_init(Key, Map) ->
+    %% beam_ssa_codegen would wrongly assume that y(0) would always be
+    %% initialized by the `get_map_elements` instruction that follows, and
+    %% would set up the stack frame using an `allocate` instruction and
+    %% would not generate an `init` instruction to initialize y(0).
+    Res = case Map of
+              #{Key := Elements} ->
+                  %% Elements will be assigned to y(0) if the key Key exists.
+                  lists:foldl(fun(El, Acc) ->
+                                      Acc + El
+                              end, 0, Elements);
+              #{} ->
+                  %% y(0) will be left uninitialized when the key is not
+                  %% present in the map.
+                  0
+          end,
+    %% y(0) would be uninitialized here if the key was not present in the map
+    %% (if the second clause was executed).
+    id(Res).
 
 %% The identity function.
 id(I) -> I.