Keep the set of unset variables as small as possible

Refactor the code to avoid putting any variable from a skippable block
into the set of unset variables. Keeping the set of unset variables as
small as possible will make beam_ssa_dead almost twice as fast when
compiling lib/unicode/tokenizer.ex in elixir.

1 files changed, 129 insertions, 114 deletions

diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl
index 2cca9ebadf..dc0381f105 100644
--- a/lib/compiler/src/beam_ssa_dead.erl
+++ b/lib/compiler/src/beam_ssa_dead.erl
@@ -27,7 +27,8 @@
 -export([opt/1]).
 
 -include("beam_ssa.hrl").
--import(lists, [append/1,last/1,member/2,takewhile/2,reverse/1]).
+-import(lists, [append/1,keymember/3,last/1,member/2,
+                takewhile/2,reverse/1]).
 
 -type used_vars() :: #{beam_ssa:label():=ordsets:ordset(beam_ssa:var_name())}.
 
@@ -181,139 +182,148 @@ shortcut_2(L, Bs0, UnsetVars0, St) ->
                     %% We have a potentially suitable br.
                     %% Now update the set of variables that will never
                     %% be set if this block will be skipped.
-                    SetInThisBlock = [V || #b_set{dst=V} <- Is],
-                    UnsetVars = update_unset_vars(L, Br, SetInThisBlock,
-                                                  UnsetVars0, St),
-
-                    %% Continue checking whether this br is suitable.
-                    shortcut_3(Br, Bs#{from:=L}, UnsetVars, St)
+                    case update_unset_vars(L, Is, Br, UnsetVars0, St) of
+                        unsafe ->
+                            %% It is unsafe to use this br,
+                            %% because it refers to a variable defined
+                            %% in this block.
+                            shortcut_unsafe_br(Br, Bs, UnsetVars0, St);
+                        UnsetVars ->
+                            %% Continue checking whether this br is
+                            %% suitable.
+                            shortcut_test_br(Br, Bs#{from:=L},
+                                             UnsetVars, St)
+                    end
             end
     end.
 
-shortcut_3(Br, Bs, UnsetVars, #st{target=Target}=St) ->
+shortcut_test_br(Br, Bs, UnsetVars, St) ->
     case is_br_safe(UnsetVars, Br, St) of
         false ->
-            %% Branching using this `br` is unsafe, either because it
-            %% is an unconditional branch to a phi node, or because
-            %% one or more of the variables that are not set will be
-            %% used. Try to follow branches of this `br`, to find a
-            %% safe `br`.
-            case Br of
-                #b_br{bool=#b_literal{val=true},succ=L} ->
-                    case Target of
-                        L ->
-                            %% We have reached the forced target, and it
-                            %% is unsafe. Give up.
-                            none;
-                        _ ->
-                            %% Try following this branch to see whether it
-                            %% leads to a safe `br`.
-                            shortcut_2(L, Bs, UnsetVars, St)
-                    end;
-                #b_br{bool=#b_var{},succ=Succ,fail=Fail} ->
-                    case {Succ,Fail} of
-                        {L,Target} ->
-                            %% The failure label is the forced target.
-                            %% Try following the success label to see
-                            %% whether it also ultimately ends up at the
-                            %% forced target.
-                            shortcut_2(L, Bs, UnsetVars, St);
-                        {Target,L} ->
-                            %% The success label is the forced target.
-                            %% Try following the failure label to see
-                            %% whether it also ultimately ends up at the
-                            %% forced target.
-                            shortcut_2(L, Bs, UnsetVars, St);
-                        {_,_} ->
-                            case Target of
-                                any ->
-                                    %% This two-way branch is unsafe. Try reducing
-                                    %% it to a one-way branch.
-                                    shortcut_two_way(Br, Bs, UnsetVars, St);
-                                one_way ->
-                                    %% This two-way branch is unsafe. Try reducing
-                                    %% it to a one-way branch.
-                                    shortcut_two_way(Br, Bs, UnsetVars, St);
-                                _ when is_integer(Target) ->
-                                    %% This two-way branch is unsafe, and
-                                    %% there already is a forced target.
-                                    %% Give up.
-                                    none
-                            end
-                    end
-            end;
+            shortcut_unsafe_br(Br, Bs, UnsetVars, St);
         true ->
-            %% This `br` instruction is safe. It does not
-            %% branch to a phi node, and all variables that
-            %% will be used are guaranteed to be defined.
-            case Br of
-                #b_br{bool=#b_literal{val=true},succ=L} ->
-                    %% This is a one-way branch.
+            shortcut_safe_br(Br, Bs, UnsetVars, St)
+    end.
+
+shortcut_unsafe_br(Br, Bs, UnsetVars, #st{target=Target}=St) ->
+    %% Branching using this `br` is unsafe, either because it
+    %% is an unconditional branch to a phi node, or because
+    %% one or more of the variables that are not set will be
+    %% used. Try to follow branches of this `br`, to find a
+    %% safe `br`.
+    case Br of
+        #b_br{bool=#b_literal{val=true},succ=L} ->
+            case Target of
+                L ->
+                    %% We have reached the forced target, and it
+                    %% is unsafe. Give up.
+                    none;
+                _ ->
+                    %% Try following this branch to see whether it
+                    %% leads to a safe `br`.
+                    shortcut_2(L, Bs, UnsetVars, St)
+            end;
+        #b_br{bool=#b_var{},succ=Succ,fail=Fail} ->
+            case {Succ,Fail} of
+                {L,Target} ->
+                    %% The failure label is the forced target.
+                    %% Try following the success label to see
+                    %% whether it also ultimately ends up at the
+                    %% forced target.
+                    shortcut_2(L, Bs, UnsetVars, St);
+                {Target,L} ->
+                    %% The success label is the forced target.
+                    %% Try following the failure label to see
+                    %% whether it also ultimately ends up at the
+                    %% forced target.
+                    shortcut_2(L, Bs, UnsetVars, St);
+                {_,_} ->
                     case Target of
                         any ->
-                            %% No forced target. Success!
-                            {Br,Bs,UnsetVars};
+                            %% This two-way branch is unsafe. Try
+                            %% reducing it to a one-way branch.
+                            shortcut_two_way(Br, Bs, UnsetVars, St);
                         one_way ->
-                            %% The target must be a one-way branch, which this
-                            %% `br` is. Success!
-                            {Br,Bs,UnsetVars};
-                        L when is_integer(Target) ->
-                            %% The forced target is L. Success!
-                            {Br,Bs,UnsetVars};
+                            %% This two-way branch is unsafe. Try
+                            %% reducing it to a one-way branch.
+                            shortcut_two_way(Br, Bs, UnsetVars, St);
                         _ when is_integer(Target) ->
-                            %% Wrong forced target. Try following this branch
-                            %% to see if it ultimately ends up at the forced
-                            %% target.
-                            shortcut_2(L, Bs, UnsetVars, St)
-                    end;
-                #b_br{bool=#b_var{}} ->
-                    %% This is a two-way branch.
-                    if
-                        Target =:= any; Target =:= one_way ->
-                            %% No specific forced target. Try to reduce the
-                            %% two-way branch to an one-way branch.
-                            case shortcut_two_way(Br, Bs, UnsetVars, St) of
-                                none when Target =:= any ->
-                                    %% This `br` can't be reduced to a one-way
-                                    %% branch. Return the `br` as-is.
-                                    {Br,Bs,UnsetVars};
-                                none when Target =:= one_way ->
-                                    %% This `br` can't be reduced to a one-way
-                                    %% branch. The caller wants a one-way branch.
-                                    %% Give up.
-                                    none;
-                                {_,_,_}=Res ->
-                                    %% This `br` was successfully reduced to a
-                                    %% one-way branch.
-                                    Res
-                            end;
-                        is_integer(Target) ->
-                            %% There is a forced target, which can't
-                            %% be reached because this `br` is a two-way
-                            %% branch. Give up.
+                            %% This two-way branch is unsafe, and
+                            %% there already is a forced target.
+                            %% Give up.
                             none
                     end
             end
     end.
 
-update_unset_vars(L, Br, SetInThisBlock, UnsetVars, #st{skippable=Skippable}) ->
+shortcut_safe_br(Br, Bs, UnsetVars, #st{target=Target}=St) ->
+    %% This `br` instruction is safe. It does not branch to a phi
+    %% node, and all variables that will be used are guaranteed to be
+    %% defined.
+    case Br of
+        #b_br{bool=#b_literal{val=true},succ=L} ->
+            %% This is a one-way branch.
+            case Target of
+                any ->
+                    %% No forced target. Success!
+                    {Br,Bs,UnsetVars};
+                one_way ->
+                    %% The target must be a one-way branch, which this
+                    %% `br` is. Success!
+                    {Br,Bs,UnsetVars};
+                L when is_integer(Target) ->
+                    %% The forced target is L. Success!
+                    {Br,Bs,UnsetVars};
+                _ when is_integer(Target) ->
+                    %% Wrong forced target. Try following this branch
+                    %% to see if it ultimately ends up at the forced
+                    %% target.
+                    shortcut_2(L, Bs, UnsetVars, St)
+            end;
+        #b_br{bool=#b_var{}} ->
+            %% This is a two-way branch.
+            if
+                Target =:= any; Target =:= one_way ->
+                    %% No specific forced target. Try to reduce the
+                    %% two-way branch to an one-way branch.
+                    case shortcut_two_way(Br, Bs, UnsetVars, St) of
+                        none when Target =:= any ->
+                            %% This `br` can't be reduced to a one-way
+                            %% branch. Return the `br` as-is.
+                            {Br,Bs,UnsetVars};
+                        none when Target =:= one_way ->
+                            %% This `br` can't be reduced to a one-way
+                            %% branch. The caller wants a one-way
+                            %% branch.  Give up.
+                            none;
+                        {_,_,_}=Res ->
+                            %% This `br` was successfully reduced to a
+                            %% one-way branch.
+                            Res
+                    end;
+                is_integer(Target) ->
+                    %% There is a forced target, which can't
+                    %% be reached because this `br` is a two-way
+                    %% branch. Give up.
+                    none
+            end
+    end.
+
+update_unset_vars(L, Is, Br, UnsetVars, #st{skippable=Skippable}) ->
     case is_map_key(L, Skippable) of
         true ->
             %% None of the variables used in this block are used in
-            %% the successors. We can speed up compilation by avoiding
-            %% adding variables to the UnsetVars if the presence of
-            %% those variable would not change the outcome of the
-            %% tests in is_br_safe/2.
+            %% the successors. Thus, there is no need to add the
+            %% variables to the set of unset variables.
             case Br of
-                #b_br{bool=Bool} ->
-                    case member(Bool, SetInThisBlock) of
+                #b_br{bool=#b_var{}=Bool} ->
+                    case keymember(Bool, #b_set.dst, Is) of
                         true ->
                             %% Bool is a variable defined in this
-                            %% block. It will change the outcome of
-                            %% the `not member(V, UnsetVars)` check in
-                            %% is_br_safe/2. The other variables
-                            %% defined in this block will not.
-                            ordsets:add_element(Bool, UnsetVars);
+                            %% block. Using the br instruction from
+                            %% this block (and skipping the body of
+                            %% the block) is unsafe.
+                            unsafe;
                         false ->
                             %% Bool is either a variable not defined
                             %% in this block or a literal. Adding it
@@ -321,9 +331,14 @@ update_unset_vars(L, Br, SetInThisBlock, UnsetVars, #st{skippable=Skippable}) ->
                             %% the outcome of the tests in
                             %% is_br_safe/2.
                             UnsetVars
-                    end
+                    end;
+                #b_br{} ->
+                    UnsetVars
             end;
         false ->
+            %% Some variables defined in this block are used by
+            %% successors. We must update the set of unset variables.
+            SetInThisBlock = [V || #b_set{dst=V} <- Is],
             ordsets:union(UnsetVars, ordsets:from_list(SetInThisBlock))
     end.