Speed up beam_ssa_dead

Compilation of code similar the following would be very slow:

    uts46_map(CP) when 0 =< CP, CP =< 44 -> '3';
    uts46_map(CP) when 45 =< CP, CP =< 46 -> 'V';
    uts46_map(CP) when 48 =< CP, CP =< 57 -> 'V';
    %% More than 2500 similar lines follows.
      .
      .
      .

The code is from from:

https://github.com/benoitc/erlang-idna/blob/3eb54ccbfa6fb917c0f4ca9197da337ad888ffe0/src/idna_mapping.erl#L6780

By using information about skippable blocks, the beam_ssa_dead
pass can be sped up to compile idna_mapping.erl about 10 times faster.

1 files changed, 39 insertions, 8 deletions

diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl
index 067d9a6741..09b29025c6 100644
--- a/lib/compiler/src/beam_ssa_dead.erl
+++ b/lib/compiler/src/beam_ssa_dead.erl
@@ -181,9 +181,9 @@ 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.
-                    UnsetVars1 = [V || #b_set{dst=V} <- Is],
-                    UnsetVars = ordsets:union(UnsetVars0,
-                                              ordsets:from_list(UnsetVars1)),
+                    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)
@@ -296,6 +296,37 @@ shortcut_3(Br, Bs, UnsetVars, #st{target=Target}=St) ->
             end
     end.
 
+update_unset_vars(L, Br, SetInThisBlock, 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.
+            case Br of
+                #b_br{bool=Bool} ->
+                    case member(Bool, SetInThisBlock) 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);
+                        false ->
+                            %% Bool is either a variable not defined
+                            %% in this block or a literal. Adding it
+                            %% to the UnsetVars set would not change
+                            %% the outcome of the tests in
+                            %% is_br_safe/2.
+                            UnsetVars
+                    end
+            end;
+        false ->
+            ordsets:union(UnsetVars, ordsets:from_list(SetInThisBlock))
+    end.
+
 shortcut_two_way(#b_br{succ=Succ,fail=Fail}, Bs0, UnsetVars0, St) ->
     case shortcut_2(Succ, Bs0, UnsetVars0, St#st{target=Fail}) of
         {#b_br{bool=#b_literal{},succ=Fail},_,_}=Res ->
@@ -919,11 +950,11 @@ used_vars([{L,#b_blk{is=Is}=Blk}|Bs], UsedVars0, Skip0) ->
     Used = used_vars_blk(Blk, Used0),
     UsedVars = used_vars_phis(Is, L, Used, UsedVars0),
 
-    %% combine_eqs/1 needs different variable usage
-    %% information than shortcut_opt/1. The Skip
-    %% map will have an entry for each block that
-    %% can be skipped (does not bind any variable used
-    %% in successor).
+    %% combine_eqs/1 needs different variable usage information than
+    %% shortcut_opt/1. The Skip map will have an entry for each block
+    %% that can be skipped (does not bind any variable used in
+    %% successor). This information is also useful for speeding up
+    %% shortcut_opt/1.
 
     Defined0 = [Def || #b_set{dst=Def} <- Is],
     Defined = ordsets:from_list(Defined0),