From c5771f6d7adfbd0d8dd4202dce5d4a090d4ad50b Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Mon, 18 Feb 2019 11:43:51 +0100
Subject: Improve optimization of switches

Part of the switch optimization done by `ssa_opt_sw` can be better
done in `beam_ssa_type`.
---
 lib/compiler/src/beam_ssa_type.erl | 79 +++++++++++++++++++++++++++-----------
 1 file changed, 56 insertions(+), 23 deletions(-)

(limited to 'lib/compiler/src/beam_ssa_type.erl')

diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl
index 4b53848a74..83f8a3cc56 100644
--- a/lib/compiler/src/beam_ssa_type.erl
+++ b/lib/compiler/src/beam_ssa_type.erl
@@ -23,7 +23,8 @@
 
 -include("beam_ssa_opt.hrl").
 -import(lists, [all/2,any/2,droplast/1,foldl/3,last/1,member/2,
-                partition/2,reverse/1,reverse/2,seq/2,sort/1]).
+                keyfind/3,partition/2,reverse/1,reverse/2,
+                seq/2,sort/1]).
 
 -define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}).
 
@@ -664,25 +665,45 @@ opt_terminator(#b_br{bool=#b_var{}}=Br, Ts, Ds) ->
     simplify_not(Br, Ts, Ds);
 opt_terminator(#b_switch{arg=#b_literal{}}=Sw, _Ts, _Ds) ->
     beam_ssa:normalize(Sw);
-opt_terminator(#b_switch{arg=#b_var{}=V}=Sw0, Ts, Ds) ->
-    Type = get_type(V, Ts),
+opt_terminator(#b_switch{arg=#b_var{}=V}=Sw, Ts, Ds) ->
+    case get_type(V, Ts) of
+        any ->
+            beam_ssa:normalize(Sw);
+        Type ->
+            beam_ssa:normalize(opt_switch(Sw, Type, Ts, Ds))
+    end;
+opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> Ret.
+
+
+opt_switch(#b_switch{fail=Fail,list=List0}=Sw0, Type, Ts, Ds) ->
+    List = prune_switch_list(List0, Fail, Type, Ts),
+    Sw1 = Sw0#b_switch{list=List},
     case Type of
         #t_integer{elements={_,_}=Range} ->
-            simplify_switch_int(Sw0, Range);
-        _ ->
+            simplify_switch_int(Sw1, Range);
+        #t_atom{elements=[_|_]} ->
             case t_is_boolean(Type) of
                 true ->
-                    case simplify_switch_bool(Sw0, Ts, Ds) of
-                        #b_br{}=Br ->
-                            opt_terminator(Br, Ts, Ds);
-                        Sw ->
-                            beam_ssa:normalize(Sw)
-                    end;
+                    #b_br{} = Br = simplify_switch_bool(Sw1, Ts, Ds),
+                    opt_terminator(Br, Ts, Ds);
                 false ->
-                    beam_ssa:normalize(Sw0)
-            end
+                    simplify_switch_atom(Type, Sw1)
+            end;
+        _ ->
+            Sw1
+    end.
+
+prune_switch_list([{_,Fail}|T], Fail, Type, Ts) ->
+    prune_switch_list(T, Fail, Type, Ts);
+prune_switch_list([{Arg,_}=Pair|T], Fail, Type, Ts) ->
+    case meet(get_type(Arg, Ts), Type) of
+        none ->
+            %% Different types. This value can never match.
+            prune_switch_list(T, Fail, Type, Ts);
+        _ ->
+            [Pair|prune_switch_list(T, Fail, Type, Ts)]
     end;
-opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> Ret.
+prune_switch_list([], _, _, _) -> [].
 
 update_successors(#b_br{bool=#b_literal{val=true},succ=S}, Ts, D) ->
     update_successor(S, Ts, D);
@@ -1079,6 +1100,17 @@ bs_match_type(utf16, _) ->
 bs_match_type(utf32, _) ->
     ?UNICODE_INT.
 
+simplify_switch_atom(#t_atom{elements=Atoms}, #b_switch{list=List0}=Sw) ->
+    case sort([A || {#b_literal{val=A},_} <- List0]) of
+        Atoms ->
+            %% All possible atoms are included in the list. The
+            %% failure label will never be used.
+            [{_,Fail}|List] = List0,
+            Sw#b_switch{fail=Fail,list=List};
+        _ ->
+            Sw
+    end.
+
 simplify_switch_int(#b_switch{list=List0}=Sw, {Min,Max}) ->
     List1 = sort(List0),
     Vs = [V || {#b_literal{val=V},_} <- List1],
@@ -1123,14 +1155,14 @@ simplify_is_record(I, any, _Size, _Tag, _Ts) ->
 simplify_is_record(_I, _Type, _Size, _Tag, _Ts) ->
     #b_literal{val=false}.
 
-simplify_switch_bool(#b_switch{arg=B,list=List0}=Sw, Ts, Ds) ->
-    List = sort(List0),
-    case List of
-        [{#b_literal{val=false},Fail},{#b_literal{val=true},Succ}] ->
-            simplify_not(#b_br{bool=B,succ=Succ,fail=Fail}, Ts, Ds);
-        [_|_] ->
-            Sw
-    end.
+simplify_switch_bool(#b_switch{arg=B,fail=Fail,list=List0}, Ts, Ds) ->
+    FalseVal = #b_literal{val=false},
+    TrueVal = #b_literal{val=true},
+    List1 = List0 ++ [{FalseVal,Fail},{TrueVal,Fail}],
+    {_,FalseLbl} = keyfind(FalseVal, 1, List1),
+    {_,TrueLbl} = keyfind(TrueVal, 1, List1),
+    Br = beam_ssa:normalize(#b_br{bool=B,succ=TrueLbl,fail=FalseLbl}),
+    simplify_not(Br, Ts, Ds).
 
 simplify_not(#b_br{bool=#b_var{}=V,succ=Succ,fail=Fail}=Br0, Ts, Ds) ->
     case Ds of
@@ -1144,7 +1176,8 @@ simplify_not(#b_br{bool=#b_var{}=V,succ=Succ,fail=Fail}=Br0, Ts, Ds) ->
             end;
         #{} ->
             Br0
-    end.
+    end;
+simplify_not(#b_br{bool=#b_literal{}}=Br, _Ts, _Ds) -> Br.
 
 %%%
 %%% Calculate the set of variables that are only used once in the
-- 
cgit v1.2.3