compiler: Limit tuple element type information to first 12 elements

This fixes the catastrophic growth of type information in cases
where we have extremely nested and wide tuples, such as the
generated test code in beam_SUITE:packed_registers/1.

The effect on type optimization is rather minimal, with only a
handful degradations in all of OTP.

7 files changed, 48 insertions, 49 deletions

diff --git a/erts/emulator/test/beam_SUITE.erl b/erts/emulator/test/beam_SUITE.erl
index cf27052e39..b1f1e115ac 100644
--- a/erts/emulator/test/beam_SUITE.erl
+++ b/erts/emulator/test/beam_SUITE.erl
@@ -133,14 +133,7 @@ packed_registers(Config) when is_list(Config) ->
 	       "id([_@Vars,_@NewVars,_@MoreNewVars]).\n"
 	       "id(I) -> I.\n"]),
 
-    %% FIXME: For the moment, we must turn off module optimization for
-    %% compilation of this module to terminate. We will probably have
-    %% to add some limitation to how much type information the
-    %% compiler will collect before the release of OTP 23, but for now
-    %% we will apply the ostrich algorithm.
-
-    Opts = [no_module_opt],
-    merl:compile_and_load(Code, Opts),
+    merl:compile_and_load(Code, []),
 
     %% Optionally print the generated code.
     PrintCode = false,                          %Change to true to print code.
diff --git a/lib/compiler/src/beam_call_types.erl b/lib/compiler/src/beam_call_types.erl
index 571542f2a3..4dbedde7ae 100644
--- a/lib/compiler/src/beam_call_types.erl
+++ b/lib/compiler/src/beam_call_types.erl
@@ -216,7 +216,7 @@ types(erlang, element, [PosType, TupleType]) ->
     RetType = case TupleType of
                   #t_tuple{size=Sz,elements=Es} when Index =< Sz,
                                                      Index >= 1 ->
-                      beam_types:get_element_type(Index, Es);
+                      beam_types:get_tuple_element(Index, Es);
                   _ ->
                       any
               end,
@@ -229,7 +229,7 @@ types(erlang, setelement, [PosType, TupleType, ArgType]) ->
                       %% This is an exact index, update the type of said
                       %% element or return 'none' if it's known to be out of
                       %% bounds.
-                      Es = beam_types:set_element_type(Index, ArgType, Es0),
+                      Es = beam_types:set_tuple_element(Index, ArgType, Es0),
                       case T#t_tuple.exact of
                           false ->
                               T#t_tuple{size=max(Index, Size),elements=Es};
@@ -416,7 +416,7 @@ types(lists, keyfind, [KeyType,PosType,_]) ->
     TupleType = case PosType of
                     #t_integer{elements={Index,Index}} when is_integer(Index),
                                                             Index >= 1 ->
-                        Es = beam_types:set_element_type(Index, KeyType, #{}),
+                        Es = beam_types:set_tuple_element(Index, KeyType, #{}),
                         #t_tuple{size=Index,elements=Es};
                     _ ->
                         #t_tuple{}
@@ -536,6 +536,6 @@ lists_zip_type(Types) ->
           end, list, Types).
 
 make_two_tuple(Type1, Type2) ->
-    Es0 = beam_types:set_element_type(1, Type1, #{}),
-    Es = beam_types:set_element_type(2, Type2, Es0),
+    Es0 = beam_types:set_tuple_element(1, Type1, #{}),
+    Es = beam_types:set_tuple_element(2, Type2, Es0),
     #t_tuple{size=2,exact=true,elements=Es}.
diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl
index c4d93be263..727a0f1856 100644
--- a/lib/compiler/src/beam_ssa_type.erl
+++ b/lib/compiler/src/beam_ssa_type.erl
@@ -540,7 +540,7 @@ simplify(#b_set{op={bif,Op},args=Args}=I, Ts) ->
 simplify(#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=N}]}=I, Ts) ->
     #t_tuple{size=Size,elements=Es} = normalized_type(Tuple, Ts),
     true = Size > N,                            %Assertion.
-    ElemType = beam_types:get_element_type(N + 1, Es),
+    ElemType = beam_types:get_tuple_element(N + 1, Es),
     case beam_types:get_singleton_value(ElemType) of
         {ok, Val} -> #b_literal{val=Val};
         error -> I
@@ -931,7 +931,7 @@ type(get_tuple_element, [Tuple, Offset], _Anno, Ts, _Ds) ->
     #t_tuple{size=Size,elements=Es} = normalized_type(Tuple, Ts),
     #b_literal{val=N} = Offset,
     true = Size > N, %Assertion.
-    beam_types:get_element_type(N + 1, Es);
+    beam_types:get_tuple_element(N + 1, Es);
 type(is_nonempty_list, [_], _Anno, _Ts, _Ds) ->
     beam_types:make_boolean();
 type(is_tagged_tuple, [_,#b_literal{},#b_literal{}], _Anno, _Ts, _Ds) ->
@@ -945,7 +945,7 @@ type(put_list, _Args, _Anno, _Ts, _Ds) ->
 type(put_tuple, Args, _Anno, Ts, _Ds) ->
     {Es, _} = foldl(fun(Arg, {Es0, Index}) ->
                             Type = raw_type(Arg, Ts),
-                            Es = beam_types:set_element_type(Index, Type, Es0),
+                            Es = beam_types:set_tuple_element(Index, Type, Es0),
                             {Es, Index + 1}
                     end, {#{}, 1}, Args),
     #t_tuple{exact=true,size=length(Args),elements=Es};
@@ -1343,7 +1343,7 @@ infer_type(succeeded, [#b_var{}=Src], Ts, Ds) ->
 %% not branching on 'succeeded'.
 infer_type(is_tagged_tuple, [#b_var{}=Src,#b_literal{val=Size},
                              #b_literal{}=Tag], _Ts, _Ds) ->
-    Es = beam_types:set_element_type(1, raw_type(Tag, #{}), #{}),
+    Es = beam_types:set_tuple_element(1, raw_type(Tag, #{}), #{}),
     T = {Src,#t_tuple{exact=true,size=Size,elements=Es}},
     {[T], [T]};
 infer_type(is_nonempty_list, [#b_var{}=Src], _Ts, _Ds) ->
@@ -1440,7 +1440,7 @@ infer_eq_lit(#b_set{op=get_tuple_element,
                     args=[#b_var{}=Tuple,#b_literal{val=N}]},
              #b_literal{}=Lit) ->
     Index = N + 1,
-    Es = beam_types:set_element_type(Index, raw_type(Lit, #{}), #{}),
+    Es = beam_types:set_tuple_element(Index, raw_type(Lit, #{}), #{}),
     [{Tuple,#t_tuple{size=Index,elements=Es}}];
 infer_eq_lit(_, _) ->
     [].
diff --git a/lib/compiler/src/beam_types.erl b/lib/compiler/src/beam_types.erl
index 3c1f192f6d..f873234dd0 100644
--- a/lib/compiler/src/beam_types.erl
+++ b/lib/compiler/src/beam_types.erl
@@ -31,7 +31,7 @@
          is_boolean_type/1,
          normalize/1]).
 
--export([get_element_type/2, set_element_type/3]).
+-export([get_tuple_element/2, set_tuple_element/3]).
 
 -export([make_type_from_value/1]).
 
@@ -390,21 +390,23 @@ is_boolean_type(_) ->
 is_singleton_type(Type) ->
     get_singleton_value(Type) =/= error.
 
--spec set_element_type(Key, Type, Elements) -> Elements when
-      Key :: term(),
+-spec set_tuple_element(Index, Type, Elements) -> Elements when
+      Index :: pos_integer(),
       Type :: type(),
-      Elements :: elements().
-set_element_type(_Key, none, Es) ->
+      Elements :: tuple_elements().
+set_tuple_element(Index, _Type, Es) when Index > ?TUPLE_ELEMENT_LIMIT ->
     Es;
-set_element_type(Key, any, Es) ->
-    maps:remove(Key, Es);
-set_element_type(Key, Type, Es) ->
-    Es#{ Key => Type }.
-
--spec get_element_type(Key, Elements) -> type() when
-      Key :: term(),
-      Elements :: elements().
-get_element_type(Index, Es) ->
+set_tuple_element(_Index, none, Es) ->
+    Es;
+set_tuple_element(Index, any, Es) ->
+    maps:remove(Index, Es);
+set_tuple_element(Index, Type, Es) ->
+    Es#{ Index => Type }.
+
+-spec get_tuple_element(Index, Elements) -> type() when
+      Index :: pos_integer(),
+      Elements :: tuple_elements().
+get_tuple_element(Index, Es) ->
     case Es of
         #{ Index := T } -> T;
         #{} -> any
@@ -449,7 +451,7 @@ mtfv_1(M) when is_map(M) -> #t_map{};
 mtfv_1(T) when is_tuple(T) ->
     {Es,_} = foldl(fun(Val, {Es0, Index}) ->
                            Type = mtfv_1(Val),
-                           Es = set_element_type(Index, Type, Es0),
+                           Es = set_tuple_element(Index, Type, Es0),
                            {Es, Index + 1}
                    end, {#{}, 1}, tuple_to_list(T)),
     #t_tuple{exact=true,size=tuple_size(T),elements=Es};
@@ -713,7 +715,7 @@ lub_elements_1([Key | Keys], Es1, Es2, Acc0) ->
     case {Es1, Es2} of
         {#{ Key := Type1 }, #{ Key := Type2 }} ->
             %% Note the use of join/2; elements don't need to be normal types.
-            Acc = set_element_type(Key, join(Type1, Type2), Acc0),
+            Acc = set_tuple_element(Key, join(Type1, Type2), Acc0),
             lub_elements_1(Keys, Es1, Es2, Acc);
         {#{}, #{}} ->
             lub_elements_1(Keys, Es1, Es2, Acc0)
@@ -829,6 +831,7 @@ verified_normal_type(#t_tuple{size=Size,elements=Es}=T) ->
     %% entire tuple to 'none'.
     maps:fold(fun(Index, Element, _) when is_integer(Index),
                                           1 =< Index, Index =< Size,
+                                          Index =< ?TUPLE_ELEMENT_LIMIT,
                                           Element =/= any, Element =/= none ->
                       verified_type(Element)
               end, [], Es),
diff --git a/lib/compiler/src/beam_types.hrl b/lib/compiler/src/beam_types.hrl
index 09f87d61ba..cedf570b58 100644
--- a/lib/compiler/src/beam_types.hrl
+++ b/lib/compiler/src/beam_types.hrl
@@ -55,19 +55,17 @@
 -record(t_bitstring, {unit=1 :: pos_integer()}).
 -record(t_bs_context, {slots=0 :: non_neg_integer(),
                        valid=0 :: non_neg_integer()}).
--record(t_map, {elements=#{} :: map_elements()}).
+-record(t_map, {}).
 -record(t_tuple, {size=0 :: integer(),
                   exact=false :: boolean(),
                   elements=#{} :: tuple_elements()}).
 
-%% Known element types, unknown elements are assumed to be 'any'. The key is
-%% a 1-based integer index for tuples, and a plain literal for maps (that is,
-%% not wrapped in a #b_literal{}, just the value itself).
+%% Known element types, where the key is a 1-based integer index. Unknown
+%% elements are assumed to be 'any', and indexes above ?TUPLE_ELEMENT_LIMIT are
+%% ignored for performance reasons.
 
+-define(TUPLE_ELEMENT_LIMIT, 12).
 -type tuple_elements() :: #{ Key :: pos_integer() => type() }.
--type map_elements() :: #{ Key :: term() => type() }.
-
--type elements() :: tuple_elements() | map_elements().
 
 -type normal_type() :: any | none |
                        list | number |
diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index 5b680994b7..8f32566590 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -436,7 +436,7 @@ valfun_1({put_tuple2,Dst,{list,Elements}}, Vst0) ->
     Vst = eat_heap(Size+1, Vst0),
     {Es,_} = foldl(fun(Val, {Es0, Index}) ->
                        Type = get_term_type(Val, Vst0),
-                       Es = beam_types:set_element_type(Index, Type, Es0),
+                       Es = beam_types:set_tuple_element(Index, Type, Es0),
                        {Es, Index + 1}
                    end, {#{}, 1}, Elements),
     Type = #t_tuple{exact=true,size=Size,elements=Es},
@@ -457,14 +457,14 @@ valfun_1({put,Src}, Vst0) ->
             error(not_building_a_tuple);
         #st{puts_left={1,{Dst,Sz,Es0}}} ->
             ElementType = get_term_type(Src, Vst0),
-            Es = beam_types:set_element_type(Sz, ElementType, Es0),
+            Es = beam_types:set_tuple_element(Sz, ElementType, Es0),
             St = St0#st{puts_left=none},
             Type = #t_tuple{exact=true,size=Sz,elements=Es},
             create_term(Type, put_tuple, [], Dst, Vst#vst{current=St});
         #st{puts_left={PutsLeft,{Dst,Sz,Es0}}} when is_integer(PutsLeft) ->
             Index = Sz - PutsLeft + 1,
             ElementType = get_term_type(Src, Vst0),
-            Es = beam_types:set_element_type(Index, ElementType, Es0),
+            Es = beam_types:set_tuple_element(Index, ElementType, Es0),
             St = St0#st{puts_left={PutsLeft-1,{Dst,Sz,Es}}},
             Vst#vst{current=St}
     end;
@@ -479,7 +479,7 @@ valfun_1({set_tuple_element,Src,Tuple,N}, Vst) ->
     %% narrowing) known elements, and we can't use extract_term either since
     %% the source tuple may be aliased.
     #t_tuple{elements=Es0}=Type = normalize(get_term_type(Tuple, Vst)),
-    Es = beam_types:set_element_type(I, get_term_type(Src, Vst), Es0),
+    Es = beam_types:set_tuple_element(I, get_term_type(Src, Vst), Es0),
     override_type(Type#t_tuple{elements=Es}, Tuple, Vst);
 %% Instructions for optimization of selective receives.
 valfun_1({recv_mark,{f,Fail}}, Vst) when is_integer(Fail) ->
@@ -625,7 +625,7 @@ valfun_1({get_tuple_element,Src,N,Dst}, Vst) ->
     assert_not_literal(Src),
     assert_type(#t_tuple{size=Index}, Src, Vst),
     #t_tuple{elements=Es} = normalize(get_term_type(Src, Vst)),
-    Type = beam_types:get_element_type(Index, Es),
+    Type = beam_types:get_tuple_element(Index, Es),
     extract_term(Type, {bif,element}, [{integer,Index}, Src], Dst, Vst);
 valfun_1({jump,{f,Lbl}}, Vst) ->
     branch(Lbl, Vst,
@@ -1702,7 +1702,7 @@ infer_types_1(#value{op={bif,'=/='},args=[LHS,RHS]}, Val, Op, Vst) ->
 infer_types_1(#value{op={bif,element},args=[{integer,Index},Tuple]},
               Val, Op, Vst) when Index >= 1 ->
     ElementType = get_term_type(Val, Vst),
-    Es = beam_types:set_element_type(Index, ElementType, #{}),
+    Es = beam_types:set_tuple_element(Index, ElementType, #{}),
     Type = #t_tuple{size=Index,elements=Es},
     case Op of
         eq_exact -> update_type(fun meet/2, Type, Tuple, Vst);
diff --git a/lib/compiler/test/property_test/beam_types_prop.erl b/lib/compiler/test/property_test/beam_types_prop.erl
index 8199d1bd5a..788cfb44bf 100644
--- a/lib/compiler/test/property_test/beam_types_prop.erl
+++ b/lib/compiler/test/property_test/beam_types_prop.erl
@@ -34,6 +34,8 @@
 -include_lib("proper/include/proper.hrl").
 -define(MOD_eqc,proper).
 
+-import(lists, [foldl/3]).
+
 %% The default repetitions of 100 is a bit too low to reliably cover all type
 %% combinations, so we crank it up a bit.
 -define(REPETITIONS, 1000).
@@ -208,11 +210,14 @@ gen_wide_union(Depth) ->
 gen_tuple_union(Depth) ->
     ?SIZED(Size,
            ?LET(Tuples, sized_list(Size, gen_tuple(Depth)),
-                lists:foldl(fun join/2, none, Tuples))).
+                foldl(fun join/2, none, Tuples))).
 
 gen_tuple_elements(Size, Depth) ->
     ?LET(Types, sized_list(rand:uniform(Size div 4 + 1), gen_element(Depth)),
-         maps:from_list([{rand:uniform(Size), T} || T <- Types])).
+         foldl(fun(Type, Acc) ->
+                       Index = rand:uniform(Size),
+                       beam_types:set_tuple_element(Index, Type, Acc)
+               end, #{}, Types)).
 
 gen_element(Depth) ->
     ?LAZY(?SUCHTHAT(Type, type(Depth),