From f89331e61b5b6fc6eadc289d4ce126d6a4219238 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Thu, 30 Aug 2018 05:22:13 +0200
Subject: beam_ssa_opt: Add simplification of switch lists

When the argument for a #b_switch{} comes from a phi node
with only literal values, the switch list could be pruned to
only contain the possible values. It could also be possible
to eliminate the failure label.

Also simplify a switch with a single value list or switch that can be
replaced with an is_boolean test.
---
 lib/compiler/src/beam_ssa_opt.erl | 105 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 105 insertions(+)

diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl
index bb9c316f50..67c92d5ae2 100644
--- a/lib/compiler/src/beam_ssa_opt.erl
+++ b/lib/compiler/src/beam_ssa_opt.erl
@@ -59,6 +59,7 @@ passes(Opts0) ->
           ?PASS(ssa_opt_bsm),
           ?PASS(ssa_opt_bsm_shortcut),
           ?PASS(ssa_opt_misc),
+          ?PASS(ssa_opt_sw),
           ?PASS(ssa_opt_blockify),
           ?PASS(ssa_opt_sink),
           ?PASS(ssa_opt_merge_blocks)],
@@ -1087,6 +1088,110 @@ eval_or(Args) ->
         [_,_] -> error
     end.
 
+%%%
+%%% Optimize #b_switch{} instructions.
+%%%
+%%% If the argument for a #b_switch{} comes from a phi node with all
+%%% literals, any values in the switch list which are not in the phi
+%%% node can be removed.
+%%%
+%%% If the values in the phi node and switch list are the same,
+%%% the failure label can't be reached and be eliminated.
+%%%
+%%% A #b_switch{} with only one value can be rewritten to
+%%% a #b_br{}. A switch that only verifies that the argument
+%%% is 'true' or 'false' can be rewritten to a is_boolean test.
+%%%
+
+ssa_opt_sw(#st{ssa=Linear0,cnt=Count0}=St) ->
+    {Linear,Count} = opt_sw(Linear0, #{}, Count0, []),
+    St#st{ssa=Linear,cnt=Count}.
+
+opt_sw([{L,#b_blk{is=Is,last=#b_switch{}=Last0}=Blk0}|Bs], Phis0, Count0, Acc) ->
+    Phis = opt_sw_phis(Is, Phis0),
+    case opt_sw_last(Last0, Phis) of
+        #b_switch{arg=Arg,fail=Fail,list=[{Lit,Lbl}]} ->
+            %% Rewrite a single value switch to a br.
+            Bool = #b_var{name={'@ssa_bool',Count0}},
+            Count = Count0 + 1,
+            IsEq = #b_set{op={bif,'=:='},dst=Bool,args=[Arg,Lit]},
+            Br = #b_br{bool=Bool,succ=Lbl,fail=Fail},
+            Blk = Blk0#b_blk{is=Is++[IsEq],last=Br},
+            opt_sw(Bs, Phis, Count, [{L,Blk}|Acc]);
+        #b_switch{arg=Arg,fail=Fail,
+                  list=[{#b_literal{val=B1},Lbl},{#b_literal{val=B2},Lbl}]}
+          when B1 =:= not B2 ->
+            %% Replace with is_boolean test.
+            Bool = #b_var{name={'@ssa_bool',Count0}},
+            Count = Count0 + 1,
+            IsBool = #b_set{op={bif,is_boolean},dst=Bool,args=[Arg]},
+            Br = #b_br{bool=Bool,succ=Lbl,fail=Fail},
+            Blk = Blk0#b_blk{is=Is++[IsBool],last=Br},
+            opt_sw(Bs, Phis, Count, [{L,Blk}|Acc]);
+        Last0 ->
+            opt_sw(Bs, Phis, Count0, [{L,Blk0}|Acc]);
+        Last ->
+            Blk = Blk0#b_blk{last=Last},
+            opt_sw(Bs, Phis, Count0, [{L,Blk}|Acc])
+    end;
+opt_sw([{L,#b_blk{is=Is}=Blk}|Bs], Phis0, Count, Acc) ->
+    Phis = opt_sw_phis(Is, Phis0),
+    opt_sw(Bs, Phis, Count, [{L,Blk}|Acc]);
+opt_sw([], _Phis, Count, Acc) ->
+    {reverse(Acc),Count}.
+
+opt_sw_phis([#b_set{op=phi,dst=Dst,args=Args}|Is], Phis) ->
+    case opt_sw_literals(Args, []) of
+        error ->
+            opt_sw_phis(Is, Phis);
+        Literals ->
+            opt_sw_phis(Is, Phis#{Dst=>Literals})
+    end;
+opt_sw_phis(_, Phis) -> Phis.
+
+opt_sw_last(#b_switch{arg=Arg,fail=Fail,list=List0}=Sw0, Phis) ->
+    case Phis of
+        #{Arg:=Values0} ->
+            Values = gb_sets:from_list(Values0),
+
+            %% Prune the switch list to only contain the possible values.
+            List1 = [P || {Lit,_}=P <- List0, gb_sets:is_member(Lit, Values)],
+
+            %% Now test whether the failure label can ever be reached.
+            Sw = case gb_sets:size(Values) =:= length(List1) of
+                     true ->
+                         %% The switch list has the same number of values as the phi node.
+                         %% The values must be the same, because the values that were not
+                         %% possible were pruned from the switch list. Therefore, the
+                         %% failure label can't possibly be reached, and we can choose a
+                         %% a new failure label by picking a value from the list.
+                         case List1 of
+                             [{#b_literal{},Lbl}|List] ->
+                                 Sw0#b_switch{fail=Lbl,list=List};
+                             [] ->
+                                 Sw0#b_switch{list=List1}
+                         end;
+                     false ->
+                         %% There are some values in the phi node that are not in the
+                         %% switch list; thus, the failure label can still be reached.
+                         Sw0
+                 end,
+            beam_ssa:normalize(Sw);
+        #{} ->
+            %% Ensure that no label in the switch list is the same
+            %% as the failure label.
+            List = [{Val,Lbl} || {Val,Lbl} <- List0, Lbl =/= Fail],
+            Sw = Sw0#b_switch{list=List},
+            beam_ssa:normalize(Sw)
+    end.
+
+opt_sw_literals([{#b_literal{}=Lit,_}|T], Acc) ->
+    opt_sw_literals(T, [Lit|Acc]);
+opt_sw_literals([_|_], _Acc) ->
+    error;
+opt_sw_literals([], Acc) -> Acc.
+
+
 %%%
 %%% Merge blocks.
 %%%
-- 
cgit v1.2.3