Merge pull request #1955 from bjorng/bjorn/compiler/beam_ssa_dead

Replace beam_dead with beam_ssa_dead

16 files changed, 2189 insertions, 1386 deletions

diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile
index bd35f20442..522523726b 100644
--- a/lib/compiler/src/Makefile
+++ b/lib/compiler/src/Makefile
@@ -52,7 +52,6 @@ MODULES =  \
 	beam_bs \
 	beam_bsm \
 	beam_clean \
-	beam_dead \
 	beam_dict \
 	beam_disasm \
 	beam_except \
@@ -61,9 +60,9 @@ MODULES =  \
 	beam_listing \
 	beam_opcodes \
 	beam_peep \
-	beam_split \
 	beam_ssa \
 	beam_ssa_codegen \
+	beam_ssa_dead \
 	beam_ssa_lint \
 	beam_ssa_opt \
 	beam_ssa_pp \
@@ -194,6 +193,7 @@ $(EBIN)/beam_listing.beam: core_parse.hrl v3_kernel.hrl beam_ssa.hrl
 $(EBIN)/beam_kernel_to_ssa.beam: v3_kernel.hrl beam_ssa.hrl
 $(EBIN)/beam_ssa.beam: beam_ssa.hrl
 $(EBIN)/beam_ssa_codegen.beam: beam_ssa.hrl
+$(EBIN)/beam_ssa_dead.beam: beam_ssa.hrl
 $(EBIN)/beam_ssa_lint.beam: beam_ssa.hrl
 $(EBIN)/beam_ssa_opt.beam: beam_ssa.hrl
 $(EBIN)/beam_ssa_pp.beam: beam_ssa.hrl
diff --git a/lib/compiler/src/beam_a.erl b/lib/compiler/src/beam_a.erl
index 266e8f46c8..0abc845310 100644
--- a/lib/compiler/src/beam_a.erl
+++ b/lib/compiler/src/beam_a.erl
@@ -52,6 +52,13 @@ function({function,Name,Arity,CLabel,Is0}) ->
 	    erlang:raise(Class, Error, Stack)
     end.
 
+rename_instrs([{test,is_eq_exact,_,[Dst,Src]}=Test,
+               {move,Src,Dst}|Is]) ->
+    %% The move instruction is not needed.
+    rename_instrs([Test|Is]);
+rename_instrs([{test,is_eq_exact,_,[Same,Same]}|Is]) ->
+    %% Same literal or same register. Will always succeed.
+    rename_instrs(Is);
 rename_instrs([{apply_last,A,N}|Is]) ->
     [{apply,A},{deallocate,N},return|rename_instrs(Is)];
 rename_instrs([{call_last,A,F,N}|Is]) ->
diff --git a/lib/compiler/src/beam_block.erl b/lib/compiler/src/beam_block.erl
index 0ed2a03a81..d28c0fd9e4 100644
--- a/lib/compiler/src/beam_block.erl
+++ b/lib/compiler/src/beam_block.erl
@@ -83,8 +83,8 @@ collect({allocate_heap,Ns,Nh,R}) -> {set,[],[],{alloc,R,{nozero,Ns,Nh,[]}}};
 collect({allocate_heap_zero,Ns,Nh,R}) -> {set,[],[],{alloc,R,{zero,Ns,Nh,[]}}};
 collect({init,D})            -> {set,[D],[],init};
 collect({test_heap,N,R})     -> {set,[],[],{alloc,R,{nozero,nostack,N,[]}}};
-collect({bif,N,F,As,D})      -> {set,[D],As,{bif,N,F}};
-collect({gc_bif,N,F,R,As,D}) -> {set,[D],As,{alloc,R,{gc_bif,N,F}}};
+collect({bif,N,{f,0},As,D})  -> {set,[D],As,{bif,N,{f,0}}};
+collect({gc_bif,N,{f,0},R,As,D}) ->   {set,[D],As,{alloc,R,{gc_bif,N,{f,0}}}};
 collect({move,S,D})          -> {set,[D],[S],move};
 collect({put_list,S1,S2,D})  -> {set,[D],[S1,S2],put_list};
 collect({put_tuple,A,D})     -> {set,[D],[],{put_tuple,A}};
@@ -95,12 +95,8 @@ collect({set_tuple_element,S,D,I}) -> {set,[],[S,D],{set_tuple_element,I}};
 collect({get_hd,S,D})  ->       {set,[D],[S],get_hd};
 collect({get_tl,S,D})  ->       {set,[D],[S],get_tl};
 collect(remove_message)      -> {set,[],[],remove_message};
-collect({put_map,F,Op,S,D,R,{list,Puts}}) ->
-    {set,[D],[S|Puts],{alloc,R,{put_map,Op,F}}};
-collect({'catch'=Op,R,L}) ->
-    {set,[R],[],{try_catch,Op,L}};
-collect({'try'=Op,R,L}) ->
-    {set,[R],[],{try_catch,Op,L}};
+collect({put_map,{f,0},Op,S,D,R,{list,Puts}}) ->
+    {set,[D],[S|Puts],{alloc,R,{put_map,Op,{f,0}}}};
 collect(fclearerror)         -> {set,[],[],fclearerror};
 collect({fcheckerror,{f,0}}) -> {set,[],[],fcheckerror};
 collect({fmove,S,D})         -> {set,[D],[S],fmove};
diff --git a/lib/compiler/src/beam_dead.erl b/lib/compiler/src/beam_dead.erl
deleted file mode 100644
index 546f0461b9..0000000000
--- a/lib/compiler/src/beam_dead.erl
+++ /dev/null
@@ -1,881 +0,0 @@
-%%
-%% %CopyrightBegin%
-%%
-%% Copyright Ericsson AB 2002-2018. All Rights Reserved.
-%%
-%% Licensed under the Apache License, Version 2.0 (the "License");
-%% you may not use this file except in compliance with the License.
-%% You may obtain a copy of the License at
-%%
-%%     http://www.apache.org/licenses/LICENSE-2.0
-%%
-%% Unless required by applicable law or agreed to in writing, software
-%% distributed under the License is distributed on an "AS IS" BASIS,
-%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-%% See the License for the specific language governing permissions and
-%% limitations under the License.
-%%
-%% %CopyrightEnd%
-%%
-
--module(beam_dead).
-
--export([module/2]).
-
-%%% Dead code is code that is executed but has no effect. This
-%%% optimization pass either removes dead code or jumps around it,
-%%% potentially making it unreachable and a target for the
-%%% the beam_jump pass.
-
--import(lists, [mapfoldl/3,reverse/1]).
-
-
--spec module(beam_utils:module_code(), [compile:option()]) ->
-                    {'ok',beam_utils:module_code()}.
-
-module({Mod,Exp,Attr,Fs0,_}, _Opts) ->
-    {Fs1,Lc1} = beam_clean:clean_labels(Fs0),
-    {Fs,Lc} = mapfoldl(fun function/2, Lc1, Fs1),
-    %%{Fs,Lc} = {Fs1,Lc1},
-    {ok,{Mod,Exp,Attr,Fs,Lc}}.
-
-function({function,Name,Arity,CLabel,Is0}, Lc0) ->
-    try
-	Is1 = beam_jump:remove_unused_labels(Is0),
-
-	%% Initialize label information with the code
-	%% for the func_info label. Without it, a register
-	%% may seem to be live when it is not.
-	[{label,L}|FiIs] = Is1,
-	D0 = beam_utils:empty_label_index(),
-	D = beam_utils:index_label(L, FiIs, D0),
-
-	%% Optimize away dead code.
-	{Is2,Lc} = forward(Is1, Lc0),
-	Is3 = backward(Is2, D),
-	Is = move_move_into_block(Is3, []),
-	{{function,Name,Arity,CLabel,Is},Lc}
-    catch
-        Class:Error:Stack ->
-	    io:fwrite("Function: ~w/~w\n", [Name,Arity]),
-	    erlang:raise(Class, Error, Stack)
-    end.
-
-%% 'move' instructions outside of blocks may thwart the jump optimizer.
-%% Move them back into the block.
-
-move_move_into_block([{block,Bl0},{move,S,D}|Is], Acc) ->
-    Bl = Bl0 ++ [{set,[D],[S],move}],
-    move_move_into_block([{block,Bl}|Is], Acc);
-move_move_into_block([{move,S,D}|Is], Acc) ->
-    Bl = [{set,[D],[S],move}],
-    move_move_into_block([{block,Bl}|Is], Acc);
-move_move_into_block([I|Is], Acc) ->
-    move_move_into_block(Is, [I|Acc]);
-move_move_into_block([], Acc) -> reverse(Acc).
-
-%%%
-%%% Scan instructions in execution order and remove redundant 'move'
-%%% instructions. 'move' instructions are redundant if we know that
-%%% the register already contains the value being assigned, as in the
-%%% following code:
-%%%
-%%%           test is_eq_exact SomeLabel Src Dst
-%%%           move Src Dst
-%%%
-%%% or in:
-%%%
-%%%           select_val Register FailLabel [... Literal => L1...]
-%%%                      .
-%%%                      .
-%%%                      .
-%%%   L1:     move Literal Register
-%%%
-%%% Also add extra labels to help the second backward pass.
-%%%
-
-forward(Is, Lc) ->
-    forward(Is, #{}, Lc, []).
-
-forward([{move,_,_}=Move|[{label,L}|_]=Is], D, Lc, Acc) ->
-    %% move/2 followed by jump/1 is optimized by backward/3.
-    forward([Move,{jump,{f,L}}|Is], D, Lc, Acc);
-forward([{bif,_,_,_,_}=Bif|[{label,L}|_]=Is], D, Lc, Acc) ->
-    %% bif/4 followed by jump/1 is optimized by backward/3.
-    forward([Bif,{jump,{f,L}}|Is], D, Lc, Acc);
-forward([{block,[]}|Is], D, Lc, Acc) ->
-    %% Empty blocks can prevent optimizations.
-    forward(Is, D, Lc, Acc);
-forward([{select,select_val,Reg,_,List}=I|Is], D0, Lc, Acc) ->
-    D = update_value_dict(List, Reg, D0),
-    forward(Is, D, Lc, [I|Acc]);
-forward([{label,Lbl}=LblI,{block,[{set,[Dst],[Lit],move}|BlkIs]}=Blk|Is], D, Lc, Acc) ->
-    %% Assumption: The target labels in a select_val/3 instruction
-    %% cannot be reached in any other way than through the select_val/3
-    %% instruction (i.e. there can be no fallthrough to such label and
-    %% it cannot be referenced by, for example, a jump/1 instruction).
-    Key = {Lbl,Dst},
-    Block = case D of
-                #{Key := Lit} -> {block,BlkIs}; %Safe to remove move instruction.
-                _ -> Blk                        %Must keep move instruction.
-            end,
-    forward([Block|Is], D, Lc, [LblI|Acc]);
-forward([{label,Lbl}=LblI|[{move,Lit,Dst}|Is1]=Is0], D, Lc, Acc) ->
-    %% Assumption: The target labels in a select_val/3 instruction
-    %% cannot be reached in any other way than through the select_val/3
-    %% instruction (i.e. there can be no fallthrough to such label and
-    %% it cannot be referenced by, for example, a jump/1 instruction).
-    Is = case maps:find({Lbl,Dst}, D) of
-	     {ok,Lit} -> Is1;     %Safe to remove move instruction.
-	     _ -> Is0		  %Keep move instruction.
-	 end,
-    forward(Is, D, Lc, [LblI|Acc]);
-forward([{test,is_eq_exact,_,[Same,Same]}|Is], D, Lc, Acc) ->
-    forward(Is, D, Lc, Acc);
-forward([{test,is_eq_exact,_,[Dst,Src]}=I,
-	 {block,[{set,[Dst],[Src],move}|Bl]}|Is], D, Lc, Acc) ->
-    forward([I,{block,Bl}|Is], D, Lc, Acc);
-forward([{test,is_eq_exact,_,[Dst,Src]}=I,{move,Src,Dst}|Is], D, Lc, Acc) ->
-    forward([I|Is], D, Lc, Acc);
-forward([{test,_,_,_}=I|Is]=Is0, D, Lc, Acc) ->
-    %% Help the second, backward pass to by inserting labels after
-    %% relational operators so that they can be skipped if they are
-    %% known to be true.
-    case useful_to_insert_label(Is0) of
-	false -> forward(Is, D, Lc, [I|Acc]);
-	true -> forward(Is, D, Lc+1, [{label,Lc},I|Acc])
-    end;
-forward([I|Is], D, Lc, Acc) ->
-    forward(Is, D, Lc, [I|Acc]);
-forward([], _, Lc, Acc) -> {Acc,Lc}.
-
-update_value_dict([Lit,{f,Lbl}|T], Reg, D0) ->
-    Key = {Lbl,Reg},
-    D = case D0 of
-            #{Key := inconsistent} -> D0;
-            #{Key := _} -> D0#{Key := inconsistent};
-            _ -> D0#{Key => Lit}
-        end,
-    update_value_dict(T, Reg, D);
-update_value_dict([], _, D) -> D.
-
-useful_to_insert_label([_,{label,_}|_]) ->
-    false;
-useful_to_insert_label([{test,Op,_,_}|_]) ->
-    case Op of
-	is_lt -> true;
-	is_ge -> true;
-	is_eq_exact -> true;
-	is_ne_exact -> true;
-	_ -> false
-    end.
-
-%%%
-%%% Scan instructions in reverse execution order and try to
-%%% shortcut branch instructions.
-%%%
-%%% For example, in this code:
-%%%
-%%%             move Literal Register
-%%%             jump L1
-%%%                .
-%%%                .
-%%%                .
-%%%     L1:     test is_{integer,atom} FailLabel Register
-%%%             select_val {x,0} FailLabel [... Literal => L2...]
-%%%                .
-%%%                .
-%%%                .
-%%%     L2:        ...
-%%%
-%%% the 'selectval' instruction will always transfer control to L2,
-%%% so we can just as well jump to L2 directly by rewriting the
-%%% first part of the sequence like this:
-%%%
-%%%           move Literal Register
-%%%           jump L2
-%%%
-%%% If register Register is killed at label L2, we can remove the
-%%% 'move' instruction, leaving just the 'jump' instruction:
-%%%
-%%%           jump L2
-%%%
-%%% These transformations may leave parts of the code unreachable.
-%%% The beam_jump pass will remove the unreachable code.
-
-backward(Is, D) ->
-    backward(Is, D, []).
-
-backward([{test,is_eq_exact,Fail,[Dst,{integer,Arity}]}=I|
-	  [{bif,tuple_size,Fail,[Reg],Dst}|Is]=Is0], D, Acc) ->
-    %% Provided that Dst is killed following this sequence,
-    %% we can rewrite the instructions like this:
-    %%
-    %% bif tuple_size Fail Reg Dst  ==>  is_tuple Fail Reg
-    %% is_eq_exact Fail Dst Integer    	 test_arity Fail Reg Integer
-    %%
-    %% (still two instructions, but they they will be combined to
-    %% one by the loader).
-    case beam_utils:is_killed(Dst, Acc, D) andalso (Arity bsr 32) =:= 0 of
-	false ->
-	    %% Not safe because the register Dst is not killed
-	    %% (probably cannot not happen in practice) or the arity
-	    %% does not fit in 32 bits (the loader will fail to load
-	    %% the module). We must move the first instruction to the
-	    %% accumulator to avoid an infinite loop.
-	    backward(Is0, D, [I|Acc]);
-	true ->
-	    %% Safe.
-	    backward([{test,test_arity,Fail,[Reg,Arity]},
-		      {test,is_tuple,Fail,[Reg]}|Is], D, Acc)
-    end;
-backward([{label,Lbl}=L|Is], D, Acc) ->
-    backward(Is, beam_utils:index_label(Lbl, Acc, D), [L|Acc]);
-backward([{select,select_val,Reg,{f,Fail0},List0}|Is], D, Acc) ->
-    List1 = shortcut_select_list(List0, Reg, D, []),
-    Fail = shortcut_label(Fail0, D),
-    List = prune_redundant(List1, Fail),
-    case List of
-	[] ->
-	    Jump = {jump,{f,Fail}},
-	    backward([Jump|Is], D, Acc);
-	[V,F] ->
-	    Test = {test,is_eq_exact,{f,Fail},[Reg,V]},
-	    Jump = {jump,F},
-	    backward([Jump,Test|Is], D, Acc);
-	[{atom,B1},F,{atom,B2},F] when B1 =:= not B2 ->
-	    Test = {test,is_boolean,{f,Fail},[Reg]},
-	    Jump = {jump,F},
-	    backward([Jump,Test|Is], D, Acc);
-	[_|_] ->
-	    Sel = {select,select_val,Reg,{f,Fail},List},
-	    backward(Is, D, [Sel|Acc])
-    end;
-backward([{jump,{f,To0}},{move,Src,Reg}=Move|Is], D, Acc) ->
-    To = shortcut_select_label(To0, Reg, Src, D),
-    Jump = {jump,{f,To}},
-    case is_killed_at(Reg, To, D) of
-	false -> backward([Move|Is], D, [Jump|Acc]);
-	true -> backward([Jump|Is], D, Acc)
-    end;
-backward([{jump,{f,To}}=J|[{bif,Op,{f,BifFail},Ops,Reg}|Is]=Is0], D, Acc) ->
-    try replace_comp_op(To, Reg, Op, Ops, D) of
-	{Test,Jump} ->
-            backward([Jump,Test|Is], D, Acc)
-    catch
-	throw:not_possible ->
-	    case To =:= BifFail of
-		true ->
-		    %% The bif instruction is redundant. See the comment
-		    %% in the next clause for why there is no need to
-		    %% test for liveness of Reg at label To.
-		    backward([J|Is], D, Acc);
-		false ->
-		    backward(Is0, D, [J|Acc])
-	    end
-    end;
-backward([{jump,{f,To}}=J|[{gc_bif,_,{f,To},_,_,_Dst}|Is]], D, Acc) ->
-    %% The gc_bif instruction is redundant, since either the gc_bif
-    %% instruction itself or the jump instruction will transfer control
-    %% to label To. Note that a gc_bif instruction does not assign its
-    %% destination register if the failure branch is taken; therefore,
-    %% the code at label To is not allowed to assume that the destination
-    %% register is initialized, and it is therefore no need to test
-    %% for liveness of the destination register at label To.
-    backward([J|Is], D, Acc);
-backward([{test,bs_start_match2,F,Live,[Src,_]=Args,Ctxt}|Is], D, Acc0) ->
-    {f,To0} = F,
-    case test_bs_literal(F, Ctxt, D, Acc0) of
-        {none,Acc} ->
-            %% Ctxt killed immediately after bs_start_match2.
-            To = shortcut_bs_context_to_binary(To0, Src, D),
-            I = {test,is_bitstr,{f,To},[Src]},
-            backward(Is, D, [I|Acc]);
-        {Literal,Acc} ->
-            %% Ctxt killed after matching a literal.
-            To = shortcut_bs_context_to_binary(To0, Src, D),
-            Eq = {test,is_eq_exact,{f,To},[Src,{literal,Literal}]},
-            backward(Is, D, [Eq|Acc]);
-        not_killed ->
-            %% Ctxt not killed. Not much to do.
-            To = shortcut_bs_start_match(To0, Src, D),
-            I = {test,bs_start_match2,{f,To},Live,Args,Ctxt},
-            backward(Is, D, [I|Acc0])
-    end;
-backward([{test,Op,{f,To0},Ops0}|Is], D, Acc) ->
-    To1 = shortcut_label(To0, D),
-    To2 = shortcut_rel_op(To1, Op, Ops0, D),
-
-    %% Try to shortcut a repeated test:
-    %%
-    %%        test Op {f,Fail1} Operands	test Op {f,Fail2} Operands
-    %%        . . .		          ==>   ...
-    %% Fail1: test Op {f,Fail2} Operands        Fail1: test Op {f,Fail2} Operands
-    %%
-    To = case beam_utils:code_at(To2, D) of
-	     [{test,Op,{f,To3},Ops}|_] ->
-		 case equal_ops(Ops0, Ops) of
-		     true -> To3;
-		     false -> To2
-		 end;
-	     _Code ->
-		 To2
-	 end,
-    I = case Op of
-	    is_eq_exact -> combine_eqs(To, Ops0, D, Acc);
-	    _ -> {test,Op,{f,To},Ops0}
-	end,
-    case I of
-	{test,_,_,_} ->
-	    %% Still a test instruction. Done.
-	    backward(Is, D, [I|Acc]);
-	_ ->
-	    %% Rewritten to a select_val. Rescan.
-	    backward([I|Is], D, Acc)
-    end;
-backward([{test,Op,{f,To0},Live,Ops0,Dst}|Is], D, Acc) ->
-    To1 = shortcut_label(To0, D),
-
-    %% Try to shortcut a repeated test:
-    %%
-    %%        test Op {f,Fail1} _ Ops _ 	test Op {f,Fail2} _ Ops _
-    %%        . . .		          ==>   ...
-    %% Fail1: test Op {f,Fail2} _ Ops _   Fail1: test Op {f,Fail2} _ Ops _
-    %%
-    To = case beam_utils:code_at(To1, D) of
-	     [{test,Op,{f,To2},_,Ops,_}|_] ->
-		 case equal_ops(Ops0, Ops) of
-		     true -> To2;
-		     false -> To1
-		 end;
-	     _Code ->
-		 To1
-	 end,
-    I = {test,Op,{f,To},Live,Ops0,Dst},
-    backward(Is, D, [I|Acc]);
-backward([{kill,_}=I|Is], D, [{line,_},Exit|_]=Acc) ->
-    case beam_jump:is_exit_instruction(Exit) of
-	false -> backward(Is, D, [I|Acc]);
-	true -> backward(Is, D, Acc)
-    end;
-backward([{bif,'or',{f,To0},[Dst,{atom,false}],Dst}=I|Is], D,
-	 [{test,is_eq_exact,{f,To},[Dst,{atom,true}]}|_]=Acc) ->
-    case shortcut_label(To0, D) of
-	To ->
-	    backward(Is, D, Acc);
-	_ ->
-	    backward(Is, D, [I|Acc])
-    end;
-backward([{bif,map_get,{f,FF},[Key,Map],_}=I0,
-          {test,has_map_fields,{f,FT}=F,[Map|Keys0]}=I1|Is], D, Acc) when FF =/= 0 ->
-    case shortcut_label(FF, D) of
-        FT ->
-            case lists:delete(Key, Keys0) of
-                [] ->
-                    backward([I0|Is], D, Acc);
-                Keys ->
-                    Test = {test,has_map_fields,F,[Map|Keys]},
-                    backward([Test|Is], D, [I0|Acc])
-            end;
-        _ ->
-            backward([I1|Is], D, [I0|Acc])
-    end;
-backward([{bif,map_get,{f,FF},[_,Map],_}=I0,
-          {test,is_map,{f,FT},[Map]}=I1|Is], D, Acc) when FF =/= 0 ->
-    case shortcut_label(FF, D) of
-        FT -> backward([I0|Is], D, Acc);
-        _ -> backward([I1|Is], D, [I0|Acc])
-    end;
-backward([I|Is], D, Acc) ->
-    backward(Is, D, [I|Acc]);
-backward([], _D, Acc) -> Acc.
-
-equal_ops([{field_flags,FlA0}|T0], [{field_flags,FlB0}|T1]) ->
-    FlA = lists:keydelete(anno, 1, FlA0),
-    FlB = lists:keydelete(anno, 1, FlB0),
-    FlA =:= FlB andalso equal_ops(T0, T1);
-equal_ops([Op|T0], [Op|T1]) ->
-    equal_ops(T0, T1);
-equal_ops([], []) -> true;
-equal_ops(_, _) -> false.
-    
-shortcut_select_list([Lit,{f,To0}|T], Reg, D, Acc) ->
-    To = shortcut_select_label(To0, Reg, Lit, D),
-    shortcut_select_list(T, Reg, D, [{f,To},Lit|Acc]);
-shortcut_select_list([], _, _, Acc) -> reverse(Acc).
-
-shortcut_label(0, _) ->
-    0;
-shortcut_label(To0, D) ->
-    case beam_utils:code_at(To0, D) of
-  	[{jump,{f,To}}|_] -> shortcut_label(To, D);
-	_ -> To0
-    end.
-
-shortcut_select_label(To, Reg, Lit, D) ->
-    shortcut_rel_op(To, is_ne_exact, [Reg,Lit], D).
-
-prune_redundant([_,{f,Fail}|T], Fail) ->
-    prune_redundant(T, Fail);
-prune_redundant([V,F|T], Fail) ->
-    [V,F|prune_redundant(T, Fail)];
-prune_redundant([], _) -> [].
-
-%% Replace a comparison operator with a test instruction and a jump.
-%% For example, if we have this code:
-%%
-%%     	  bif '=:=' Fail Src1 Src2 {x,0}
-%%    	  jump L1
-%%           .
-%%           .
-%%           .
-%%   L1:  select_val {x,0} FailLabel [... true => L2..., ...false => L3...]
-%%
-%% the first two instructions can be replaced with
-%%
-%%        test is_eq_exact L3 Src1 Src2
-%%	  jump L2
-%%
-%% provided that {x,0} is killed at both L2 and L3.
-
-replace_comp_op(To, Reg, Op, Ops, D) ->
-    False = comp_op_find_shortcut(To, Reg, {atom,false}, D),
-    True = comp_op_find_shortcut(To, Reg, {atom,true}, D),
-    {bif_to_test(Op, Ops, False),{jump,{f,True}}}.
-
-comp_op_find_shortcut(To0, Reg, Val, D) ->
-    case shortcut_select_label(To0, Reg, Val, D) of
-	To0 ->
-	    not_possible();
-	To ->
-	    case is_killed_at(Reg, To, D) of
-		false -> not_possible();
-		true -> To
-	    end
-    end.
-
-bif_to_test(Name, Args, Fail) ->
-    try
-	beam_utils:bif_to_test(Name, Args, {f,Fail})
-    catch
-	error:_ -> not_possible()
-    end.
-
-not_possible() -> throw(not_possible).
-
-%% combine_eqs(To, Operands, Acc) -> Instruction.
-%%  Combine two is_eq_exact instructions or (an is_eq_exact
-%%  instruction and a select_val instruction) to a select_val
-%%  instruction if possible.
-%%
-%%  Example:
-%%
-%%      is_eq_exact F1 Reg Lit1		    select_val Reg F2 [ Lit1 L1
-%%   L1:                .                                       Lit2 L2 ]
-%%                      .
-%%                      .	     ==>
-%%                      .
-%%   F1:  is_eq_exact F2 Reg Lit2          F1: is_eq_exact F2 Reg Lit2
-%%   L2:  ....				   L2:
-%%
-combine_eqs(To, [Reg,{Type,_}=Lit1]=Ops, D, Acc)
-    when Type =:= atom; Type =:= integer ->
-    Next = case Acc of
-               [{label,Lbl}|_] -> Lbl;
-               [{jump,{f,Lbl}}|_] -> Lbl
-           end,
-    case beam_utils:code_at(To, D) of
-	[{test,is_eq_exact,{f,F2},[Reg,{Type,_}=Lit2]},
-	 {label,L2}|_] when Lit1 =/= Lit2 ->
-	    {select,select_val,Reg,{f,F2},[Lit1,{f,Next},Lit2,{f,L2}]};
-	[{test,is_eq_exact,{f,F2},[Reg,{Type,_}=Lit2]},
-	 {jump,{f,L2}}|_] when Lit1 =/= Lit2 ->
-	    {select,select_val,Reg,{f,F2},[Lit1,{f,Next},Lit2,{f,L2}]};
-	[{select,select_val,Reg,{f,F2},[{Type,_}|_]=List0}|_] ->
-	    List = remove_from_list(Lit1, List0),
-	    {select,select_val,Reg,{f,F2},[Lit1,{f,Next}|List]};
-	_Is ->
-	    {test,is_eq_exact,{f,To},Ops}
-	end;
-combine_eqs(To, Ops, _D, _Acc) ->
-    {test,is_eq_exact,{f,To},Ops}.
-
-remove_from_list(Lit, [Lit,{f,_}|T]) ->
-    T;
-remove_from_list(Lit, [Val,{f,_}=Fail|T]) ->
-    [Val,Fail|remove_from_list(Lit, T)];
-remove_from_list(_, []) -> [].
-
-
-test_bs_literal(F, Ctxt, D,
-                [{test,bs_match_string,F,[Ctxt,Bs]},
-                 {test,bs_test_tail2,F,[Ctxt,0]}|Acc]) ->
-    test_bs_literal_1(Ctxt, Acc, D, Bs);
-test_bs_literal(F, Ctxt, D, [{test,bs_test_tail2,F,[Ctxt,0]}|Acc]) ->
-    test_bs_literal_1(Ctxt, Acc, D, <<>>);
-test_bs_literal(_, Ctxt, D, Acc) ->
-    test_bs_literal_1(Ctxt, Acc, D, none).
-
-test_bs_literal_1(Ctxt, Is, D, Literal) ->
-    case beam_utils:is_killed(Ctxt, Is, D) of
-        true -> {Literal,Is};
-        false -> not_killed
-    end.
-
-%% shortcut_bs_start_match(TargetLabel, Reg) -> TargetLabel
-%%  A failing bs_start_match2 instruction means that the source (Reg)
-%%  cannot be a binary. That means that it is safe to skip
-%%  bs_context_to_binary instructions operating on Reg, and
-%%  bs_start_match2 instructions operating on Reg.
-
-shortcut_bs_start_match(To, Reg, D) ->
-    shortcut_bs_start_match_1(beam_utils:code_at(To, D), Reg, To, D).
-
-shortcut_bs_start_match_1([{bs_context_to_binary,Reg}|Is], Reg, To, D) ->
-    shortcut_bs_start_match_1(Is, Reg, To, D);
-shortcut_bs_start_match_1([{jump,{f,To}}|_], Reg, _, D) ->
-    Code = beam_utils:code_at(To, D),
-    shortcut_bs_start_match_1(Code, Reg, To, D);
-shortcut_bs_start_match_1([{test,bs_start_match2,{f,To},_,[Reg|_],_}|_],
-			  Reg, _, D) ->
-    Code = beam_utils:code_at(To, D),
-    shortcut_bs_start_match_1(Code, Reg, To, D);
-shortcut_bs_start_match_1(_, _, To, _) ->
-    To.
-
-%% shortcut_bs_context_to_binary(TargetLabel, Reg) -> TargetLabel
-%%  If a bs_start_match2 instruction has been eliminated, the
-%%  bs_context_to_binary instruction can be eliminated too.
-
-shortcut_bs_context_to_binary(To, Reg, D) ->
-    shortcut_bs_ctb_1(beam_utils:code_at(To, D), Reg, To, D).
-
-shortcut_bs_ctb_1([{bs_context_to_binary,Reg}|Is], Reg, To, D) ->
-    shortcut_bs_ctb_1(Is, Reg, To, D);
-shortcut_bs_ctb_1([{jump,{f,To}}|_], Reg, _, D) ->
-    Code = beam_utils:code_at(To, D),
-    shortcut_bs_ctb_1(Code, Reg, To, D);
-shortcut_bs_ctb_1(_, _, To, _) ->
-    To.
-
-%% shortcut_rel_op(FailLabel, Operator, [Operand], D) -> FailLabel'
-%%  Try to shortcut the given test instruction. Example:
-%%
-%%           is_ge L1 {x,0} 48
-%%     .
-%%     .
-%%     .
-%%     L1:   is_ge L2 {x,0} 65
-%%
-%%  The first test instruction can be rewritten to "is_ge L2 {x,0} 48"
-%%  since the instruction at L1 will also fail.
-%%
-%%  If there are instructions between L1 and the other test instruction
-%%  it may still be possible to do the shortcut. For example:
-%%
-%%     L1:   is_eq_exact L3 {x,0} 92
-%%           is_ge L2 {x,0} 65
-%%
-%%  Since the first test instruction failed, we know that {x,0} must
-%%  be less than 48; therefore, we know that {x,0} cannot be equal to
-%%  92 and the jump to L3 cannot happen.
-
-shortcut_rel_op(To, Op, Ops, D) ->
-    case normalize_op({test,Op,{f,To},Ops}) of
-	{{NormOp,A,B},_} ->
-	    Normalized = {negate_op(NormOp),A,B},
-	    shortcut_rel_op_fp(To, Normalized, D);
-	{_,_} ->
-	    To;
-	error ->
-	    To
-    end.
-
-shortcut_rel_op_fp(To0, Normalized, D) ->
-    Code = beam_utils:code_at(To0, D),
-    case shortcut_any_label(Code, Normalized) of
-	error ->
-	    To0;
-	To ->
-	    shortcut_rel_op_fp(To, Normalized, D)
-    end.
-
-%% shortcut_any_label([Instruction], PrevCondition) -> FailLabel | error
-%%  Using PrevCondition (a previous condition known to be true),
-%%  try to shortcut to another failure label.
-
-shortcut_any_label([{jump,{f,Lbl}}|_], _Prev) ->
-    Lbl;
-shortcut_any_label([{label,Lbl}|_], _Prev) ->
-    Lbl;
-shortcut_any_label([{select,select_val,R,{f,Fail},L}|_], Prev) ->
-    shortcut_selectval(L, R, Fail, Prev);
-shortcut_any_label([I|Is], Prev) ->
-    case normalize_op(I) of
-	error ->
-	    error;
-	{Normalized,Fail} ->
-	    %% We have a relational operator.
-	    case will_succeed(Prev, Normalized) of
-		no ->
-		    %% This test instruction will always branch
-		    %% to Fail.
-		    Fail;
-		yes ->
-		    %% This test instruction will never branch,
-		    %% so we will look at the next instruction.
-		    shortcut_any_label(Is, Prev);
-		maybe ->
-		    %% May or may not branch. From now on, we can only
-		    %% shortcut to the this specific failure label
-		    %% Fail.
-		    shortcut_specific_label(Is, Fail, Prev)
-	    end
-    end.
-
-%% shortcut_specific_label([Instruction], FailLabel, PrevCondition) ->
-%%    FailLabel | error
-%%  We have previously encountered a test instruction that may or
-%%  may not branch to FailLabel. Therefore we are only allowed
-%%  to do the shortcut to the same fail label (FailLabel).
-
-shortcut_specific_label([{label,_}|Is], Fail, Prev) ->
-    shortcut_specific_label(Is, Fail, Prev);
-shortcut_specific_label([{select,select_val,R,{f,F},L}|_], Fail, Prev) ->
-    case shortcut_selectval(L, R, F, Prev) of
-	Fail -> Fail;
-	_ -> error
-    end;
-shortcut_specific_label([I|Is], Fail, Prev) ->
-    case normalize_op(I) of
-	error ->
-	    error;
-	{Normalized,Fail} ->
-	    case will_succeed(Prev, Normalized) of
-		no ->
-		    %% Will branch to FailLabel.
-		    Fail;
-		yes ->
-		    %% Will definitely never branch.
-		    shortcut_specific_label(Is, Fail, Prev);
-		maybe ->
-		    %% May branch, but still OK since it will branch
-		    %% to FailLabel.
-		    shortcut_specific_label(Is, Fail, Prev)
-	    end;
-	{Normalized,_} ->
-	    %% This test instruction will branch to a different
-	    %% fail label, if it branches at all.
-	    case will_succeed(Prev, Normalized) of
-		yes ->
-		    %% Still OK, since the branch will never be
-		    %% taken.
-		    shortcut_specific_label(Is, Fail, Prev);
-		no ->
-		    %% Give up. The branch will definitely be taken
-		    %% to a different fail label.
-		    error;
-		maybe ->
-		    %% Give up. If the branch is taken, it will be
-		    %% to a different fail label.
-		    error
-	    end
-    end.
-
-
-%% shortcut_selectval(List, Reg, Fail, PrevCond) -> FailLabel | error
-%%  Try to shortcut a selectval instruction. A selectval instruction
-%%  is equivalent to the following instruction sequence:
-%%
-%%      is_ne_exact L1 Reg Value1
-%%              .
-%%              .
-%%              .
-%%      is_ne_exact LN Reg ValueN
-%%      jump DefaultFailLabel
-%%
-shortcut_selectval([Val,{f,Lbl}|T], R, Fail, Prev) ->
-    case will_succeed(Prev, {'=/=',R,get_literal(Val)}) of
-	yes -> shortcut_selectval(T, R, Fail, Prev);
-	no -> Lbl;
-	maybe -> error
-    end;
-shortcut_selectval([], _, Fail, _) -> Fail.
-
-%% will_succeed(PrevCondition, Condition) -> yes | no | maybe
-%%  PrevCondition is a condition known to be true. This function
-%%  will tell whether Condition will succeed.
-
-will_succeed({Op1,Reg,A}, {Op2,Reg,B}) ->
-    will_succeed_1(Op1, A, Op2, B);
-will_succeed({'=:=',Reg,{literal,A}}, {TypeTest,Reg}) ->
-    case erlang:TypeTest(A) of
-	false -> no;
-	true -> yes
-    end;
-will_succeed({_,_,_}, maybe) ->
-    maybe;
-will_succeed({_,_,_}, Test) when is_tuple(Test) ->
-    maybe.
-
-will_succeed_1('=:=', A, '<', B) ->
-    if
-	B =< A -> no;
-	true -> yes
-    end;
-will_succeed_1('=:=', A, '=<', B) ->
-    if
-	B < A -> no;
-	true -> yes
-    end;
-will_succeed_1('=:=', A, '=:=', B) ->
-    if
-	A =:= B -> yes;
-	true -> no
-    end;
-will_succeed_1('=:=', A, '=/=', B) ->
-    if
-	A =:= B -> no;
-	true -> yes
-    end;
-will_succeed_1('=:=', A, '>=', B) ->
-    if
-	B > A -> no;
-	true -> yes
-    end;
-will_succeed_1('=:=', A, '>', B) ->
-    if
-	B >= A -> no;
-	true -> yes
-    end;
-
-will_succeed_1('=/=', A, '=/=', B) when A =:= B -> yes;
-will_succeed_1('=/=', A, '=:=', B) when A =:= B -> no;
-
-will_succeed_1('<', A, '=:=', B)  when B >= A -> no;
-will_succeed_1('<', A, '=/=', B)  when B >= A -> yes;
-will_succeed_1('<', A, '<',   B)  when B >= A -> yes;
-will_succeed_1('<', A, '=<',  B)  when B > A  -> yes;
-will_succeed_1('<', A, '>=',  B)  when B > A  -> no;
-will_succeed_1('<', A, '>',   B)  when B >= A -> no;
-
-will_succeed_1('=<', A, '=:=', B) when B > A  -> no;
-will_succeed_1('=<', A, '=/=', B) when B > A  -> yes;
-will_succeed_1('=<', A, '<',   B) when B > A  -> yes;
-will_succeed_1('=<', A, '=<',  B) when B >= A -> yes;
-will_succeed_1('=<', A, '>=',  B) when B > A  -> no;
-will_succeed_1('=<', A, '>',   B) when B >= A -> no;
-
-will_succeed_1('>=', A, '=:=', B) when B < A  -> no;
-will_succeed_1('>=', A, '=/=', B) when B < A  -> yes;
-will_succeed_1('>=', A, '<',   B) when B =< A -> no;
-will_succeed_1('>=', A, '=<',  B) when B < A  -> no;
-will_succeed_1('>=', A, '>=',  B) when B =< A -> yes;
-will_succeed_1('>=', A, '>',   B) when B < A  -> yes;
-
-will_succeed_1('>', A, '=:=', B)  when B =< A -> no;
-will_succeed_1('>', A, '=/=', B)  when B =< A -> yes;
-will_succeed_1('>', A, '<',   B)  when B =< A -> no;
-will_succeed_1('>', A, '=<',  B)  when B < A  -> no;
-will_succeed_1('>', A, '>=',  B)  when B =< A -> yes;
-will_succeed_1('>', A, '>',   B)  when B < A  -> yes;
-
-will_succeed_1(_, _, _, _) -> maybe.
-
-%% normalize_op(Instruction) -> {Normalized,FailLabel} | error
-%%    Normalized = {Operator,Register,Literal} |
-%%                 {TypeTest,Register} |
-%%                 maybe
-%%    Operation = '<' | '=<' | '=:=' | '=/=' | '>=' | '>'
-%%    TypeTest = is_atom | is_integer ...
-%%    Literal = {literal,Term}
-%%
-%%  Normalize a relational operator to facilitate further
-%%  comparisons between operators. Always make the register
-%%  operand the first operand. Thus the following instruction:
-%%
-%%    {test,is_ge,{f,99},{integer,13},{x,0}}
-%%
-%%  will be normalized to:
-%%
-%%    {'=<',{x,0},{literal,13}}
-%%
-%%  NOTE: Bit syntax test instructions are scary. They may change the
-%%  state of match contexts and update registers, so we don't dare
-%%  mess with them.
-
-normalize_op({test,is_ge,{f,Fail},Ops}) ->
-    normalize_op_1('>=', Ops, Fail);
-normalize_op({test,is_lt,{f,Fail},Ops}) ->
-    normalize_op_1('<', Ops, Fail);
-normalize_op({test,is_eq_exact,{f,Fail},Ops}) ->
-    normalize_op_1('=:=', Ops, Fail);
-normalize_op({test,is_ne_exact,{f,Fail},Ops}) ->
-    normalize_op_1('=/=', Ops, Fail);
-normalize_op({test,Op,{f,Fail},[R]}) ->
-    case erl_internal:new_type_test(Op, 1) of
-	true -> {{Op,R},Fail};
-	false -> {maybe,Fail}
-    end;
-normalize_op({test,_,{f,Fail},_}=I) ->
-    case beam_utils:is_pure_test(I) of
-	true -> {maybe,Fail};
-	false -> error
-    end;
-normalize_op(_) ->
-    error.
-
-normalize_op_1(Op, [Op1,Op2], Fail) ->
-    case {get_literal(Op1),get_literal(Op2)} of
-	{error,error} ->
-	    %% Both operands are registers.
-	    {maybe,Fail};
-	{error,Lit} ->
-	    {{Op,Op1,Lit},Fail};
-	{Lit,error} ->
-	    {{turn_op(Op),Op2,Lit},Fail};
-	{_,_} ->
-	    %% Both operands are literals. Can probably only
-	    %% happen if the Core Erlang optimizations passes were
-	    %% turned off, so don't bother trying to do something
-	    %% smart here.
-	    {maybe,Fail}
-    end.
-
-turn_op('<') -> '>';
-turn_op('>=') -> '=<';
-turn_op('=:='=Op) -> Op;
-turn_op('=/='=Op) -> Op.
-
-negate_op('>=') -> '<';
-negate_op('<') -> '>=';
-negate_op('=<') -> '>';
-negate_op('>') -> '=<';
-negate_op('=:=') -> '=/=';
-negate_op('=/=') -> '=:='.
-
-get_literal({atom,Val}) ->
-    {literal,Val};
-get_literal({integer,Val}) ->
-    {literal,Val};
-get_literal({float,Val}) ->
-    {literal,Val};
-get_literal(nil) ->
-    {literal,[]};
-get_literal({literal,_}=Lit) ->
-    Lit;
-get_literal({_,_}) -> error.
-
-
-%%%
-%%% Removing stores to Y registers is not always safe
-%%% if there is an instruction that causes an exception
-%%% within a catch. In practice, there are few or no
-%%% opportunities for removing stores to Y registers anyway
-%%% if sys_core_fold has been run.
-%%%
-
-is_killed_at({x,_}=Reg, Lbl, D) ->
-    beam_utils:is_killed_at(Reg, Lbl, D);
-is_killed_at({y,_}, _, _) ->
-    false.
diff --git a/lib/compiler/src/beam_jump.erl b/lib/compiler/src/beam_jump.erl
index 42b4cdaf4f..6d0a8db2dc 100644
--- a/lib/compiler/src/beam_jump.erl
+++ b/lib/compiler/src/beam_jump.erl
@@ -22,7 +22,7 @@
 -module(beam_jump).
 
 -export([module/2,
-	 is_unreachable_after/1,is_exit_instruction/1,
+	 is_exit_instruction/1,
 	 remove_unused_labels/1]).
 
 %%% The following optimisations are done:
@@ -128,27 +128,123 @@
 %%% on the program state.
 %%% 
 
--import(lists, [reverse/1,reverse/2,foldl/3]).
+-import(lists, [foldl/3,mapfoldl/3,reverse/1,reverse/2]).
 
 -type instruction() :: beam_utils:instruction().
 
 -spec module(beam_utils:module_code(), [compile:option()]) ->
                     {'ok',beam_utils:module_code()}.
 
-module({Mod,Exp,Attr,Fs0,Lc}, _Opt) ->
-    Fs = [function(F) || F <- Fs0],
+module({Mod,Exp,Attr,Fs0,Lc0}, _Opt) ->
+    {Fs,Lc} = mapfoldl(fun function/2, Lc0, Fs0),
     {ok,{Mod,Exp,Attr,Fs,Lc}}.
 
 %% function(Function) -> Function'
 %%  Optimize jumps and branches.
 %%
 %%  NOTE: This function assumes that there are no labels inside blocks.
-function({function,Name,Arity,CLabel,Asm0}) ->
-    Asm1 = share(Asm0),
-    Asm2 = move(Asm1),
-    Asm3 = opt(Asm2, CLabel),
-    Asm = remove_unused_labels(Asm3),
-    {function,Name,Arity,CLabel,Asm}.
+function({function,Name,Arity,CLabel,Asm0}, Lc0) ->
+    Asm1 = eliminate_moves(Asm0),
+    {Asm2,Lc} = insert_labels(Asm1, Lc0, []),
+    Asm3 = share(Asm2),
+    Asm4 = move(Asm3),
+    Asm5 = opt(Asm4, CLabel),
+    Asm = remove_unused_labels(Asm5),
+    {{function,Name,Arity,CLabel,Asm},Lc}.
+
+%%%
+%%% Scan instructions in execution order and remove redundant 'move'
+%%% instructions. 'move' instructions are redundant if we know that
+%%% the register already contains the value being assigned, as in the
+%%% following code:
+%%%
+%%%           select_val Register FailLabel [... Literal => L1...]
+%%%                      .
+%%%                      .
+%%%                      .
+%%%   L1:     move Literal Register
+%%%
+
+eliminate_moves(Is) ->
+    eliminate_moves(Is, #{}, []).
+
+eliminate_moves([{select,select_val,Reg,_,List}=I|Is], D0, Acc) ->
+    D = update_value_dict(List, Reg, D0),
+    eliminate_moves(Is, D, [I|Acc]);
+eliminate_moves([{label,Lbl},{block,[{set,[Dst],[Lit],move}|BlkIs]}=Blk0|Is],
+        D, Acc0) ->
+    Acc = [{label,Lbl}|Acc0],
+    case already_has_value(Lit, Lbl, Dst, D) andalso
+        no_fallthrough(Acc0) of
+        true ->
+            %% Remove redundant 'move' instruction.
+            Blk = {block,BlkIs},
+            eliminate_moves([Blk|Is], D, Acc);
+        false ->
+            %% Keep 'move' instruction.
+            eliminate_moves([Blk0|Is], D, Acc)
+    end;
+eliminate_moves([{block,[]}|Is], D, Acc) ->
+    %% Empty blocks can prevent further jump optimizations.
+    eliminate_moves(Is, D, Acc);
+eliminate_moves([I|Is], D0, Acc) ->
+    D = update_unsafe_labels(I, D0),
+    eliminate_moves(Is, D, [I|Acc]);
+eliminate_moves([], _, Acc) -> reverse(Acc).
+
+no_fallthrough([I|_]) ->
+    is_unreachable_after(I).
+
+already_has_value(Lit, Lbl, Reg, D) ->
+    Key = {Lbl,Reg},
+    case D of
+        #{Lbl:=unsafe} ->
+            false;
+        #{Key:=Lit} ->
+            true;
+        #{} ->
+            false
+    end.
+
+update_value_dict([Lit,{f,Lbl}|T], Reg, D0) ->
+    Key = {Lbl,Reg},
+    D = case D0 of
+            #{Key := inconsistent} -> D0;
+            #{Key := _} -> D0#{Key := inconsistent};
+            _ -> D0#{Key => Lit}
+        end,
+    update_value_dict(T, Reg, D);
+update_value_dict([], _, D) -> D.
+
+update_unsafe_labels(I, D) ->
+    Ls = instr_labels(I),
+    update_unsafe_labels_1(Ls, D).
+
+update_unsafe_labels_1([L|Ls], D) ->
+    update_unsafe_labels_1(Ls, D#{L=>unsafe});
+update_unsafe_labels_1([], D) -> D.
+
+%%%
+%%% It seems to be useful to insert extra labels after certain
+%%% test instructions. This used to be done by beam_dead.
+%%%
+
+insert_labels([{test,Op,_,_}=I|Is], Lc, Acc) ->
+    Useful = case Op of
+                 is_lt -> true;
+                 is_ge -> true;
+                 is_eq_exact -> true;
+                 is_ne_exact -> true;
+                 _ -> false
+             end,
+    case Useful of
+	false -> insert_labels(Is, Lc, [I|Acc]);
+	true -> insert_labels(Is, Lc+1, [{label,Lc},I|Acc])
+    end;
+insert_labels([I|Is], Lc, Acc) ->
+    insert_labels(Is, Lc, [I|Acc]);
+insert_labels([], Lc, Acc) ->
+    {reverse(Acc),Lc}.
 
 %%%
 %%% (1) We try to share the code for identical code segments by replacing all
@@ -571,58 +667,76 @@ drop_upto_label([{label,_}|_]=Is) -> Is;
 drop_upto_label([_|Is]) -> drop_upto_label(Is);
 drop_upto_label([]) -> [].
 
-%% ulbl(Instruction, UsedGbSet) -> UsedGbSet'
-%%  Update the gb_set UsedGbSet with any function-local labels
+%% ulbl(Instruction, UsedCerlSet) -> UsedCerlSet'
+%%  Update the cerl_set UsedCerlSet with any function-local labels
 %%  (i.e. not with labels in call instructions) referenced by
 %%  the instruction Instruction.
 %%
 %%  NOTE: This function does NOT look for labels inside blocks.
 
-ulbl({test,_,Fail,_}, Used) ->
-    mark_used(Fail, Used);
-ulbl({test,_,Fail,_,_,_}, Used) ->
-    mark_used(Fail, Used);
-ulbl({select,_,_,Fail,Vls}, Used) ->
-    mark_used_list(Vls, mark_used(Fail, Used));
-ulbl({'try',_,Lbl}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({'catch',_,Lbl}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({jump,Lbl}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({loop_rec,Lbl,_}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({loop_rec_end,Lbl}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({wait,Lbl}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({wait_timeout,Lbl,_To}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({bif,_Name,Lbl,_As,_R}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({gc_bif,_Name,Lbl,_Live,_As,_R}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({bs_init,Lbl,_,_,_,_}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({bs_put,Lbl,_,_}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({put_map,Lbl,_Op,_Src,_Dst,_Live,_List}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({get_map_elements,Lbl,_Src,_List}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({recv_mark,Lbl}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({recv_set,Lbl}, Used) ->
-    mark_used(Lbl, Used);
-ulbl({fcheckerror,Lbl}, Used) ->
-    mark_used(Lbl, Used);
-ulbl(_, Used) -> Used.
-
-mark_used({f,0}, Used) -> Used;
-mark_used({f,L}, Used) -> cerl_sets:add_element(L, Used).
-
-mark_used_list([{f,L}|T], Used) ->
-    mark_used_list(T, cerl_sets:add_element(L, Used));
-mark_used_list([_|T], Used) ->
-    mark_used_list(T, Used);
-mark_used_list([], Used) -> Used.
+ulbl(I, Used) ->
+    case instr_labels(I) of
+        [] ->
+            Used;
+        [Lbl] ->
+            cerl_sets:add_element(Lbl, Used);
+        [_|_]=L ->
+            ulbl_list(L, Used)
+    end.
+
+ulbl_list([L|Ls], Used) ->
+    ulbl_list(Ls, cerl_sets:add_element(L, Used));
+ulbl_list([], Used) -> Used.
+
+-spec instr_labels(Instruction) -> Labels when
+      Instruction :: instruction(),
+      Labels :: [beam_asm:label()].
+
+instr_labels({test,_,Fail,_}) ->
+    do_instr_labels(Fail);
+instr_labels({test,_,Fail,_,_,_}) ->
+    do_instr_labels(Fail);
+instr_labels({select,_,_,Fail,Vls}) ->
+    do_instr_labels_list(Vls, do_instr_labels(Fail));
+instr_labels({'try',_,Lbl}) ->
+    do_instr_labels(Lbl);
+instr_labels({'catch',_,Lbl}) ->
+    do_instr_labels(Lbl);
+instr_labels({jump,Lbl}) ->
+    do_instr_labels(Lbl);
+instr_labels({loop_rec,Lbl,_}) ->
+    do_instr_labels(Lbl);
+instr_labels({loop_rec_end,Lbl}) ->
+    do_instr_labels(Lbl);
+instr_labels({wait,Lbl}) ->
+    do_instr_labels(Lbl);
+instr_labels({wait_timeout,Lbl,_To}) ->
+    do_instr_labels(Lbl);
+instr_labels({bif,_Name,Lbl,_As,_R}) ->
+    do_instr_labels(Lbl);
+instr_labels({gc_bif,_Name,Lbl,_Live,_As,_R}) ->
+    do_instr_labels(Lbl);
+instr_labels({bs_init,Lbl,_,_,_,_}) ->
+    do_instr_labels(Lbl);
+instr_labels({bs_put,Lbl,_,_}) ->
+    do_instr_labels(Lbl);
+instr_labels({put_map,Lbl,_Op,_Src,_Dst,_Live,_List}) ->
+    do_instr_labels(Lbl);
+instr_labels({get_map_elements,Lbl,_Src,_List}) ->
+    do_instr_labels(Lbl);
+instr_labels({recv_mark,Lbl}) ->
+    do_instr_labels(Lbl);
+instr_labels({recv_set,Lbl}) ->
+    do_instr_labels(Lbl);
+instr_labels({fcheckerror,Lbl}) ->
+    do_instr_labels(Lbl);
+instr_labels(_) -> [].
+
+do_instr_labels({f,0}) -> [];
+do_instr_labels({f,F}) -> [F].
+
+do_instr_labels_list([{f,F}|T], Acc) ->
+    do_instr_labels_list(T, [F|Acc]);
+do_instr_labels_list([_|T], Acc) ->
+    do_instr_labels_list(T, Acc);
+do_instr_labels_list([], Acc) -> Acc.
diff --git a/lib/compiler/src/beam_peep.erl b/lib/compiler/src/beam_peep.erl
index 74da6aa704..2323a439e9 100644
--- a/lib/compiler/src/beam_peep.erl
+++ b/lib/compiler/src/beam_peep.erl
@@ -112,6 +112,10 @@ peep([{select,Op,R,F,Vls0}|Is], SeenTests0, Acc0) ->
             %% Single value left. Convert to regular test
             Is1 = [{test,test_arity,F,[R,Arity]},{jump,Lbl}|Is],
             peep(Is1, SeenTests0, Acc0);
+	[{atom,B1},Lbl,{atom,B2},Lbl] when B1 =:= not B2 ->
+            %% Replace with is_boolean test.
+            Is1 = [{test,is_boolean,F,[R]},{jump,Lbl}|Is],
+            peep(Is1, SeenTests0, Acc0);
 	[_|_]=Vls ->
 	    I = {select,Op,R,F,Vls},
 	    peep(Is, gb_sets:empty(), [I|Acc0])
diff --git a/lib/compiler/src/beam_split.erl b/lib/compiler/src/beam_split.erl
deleted file mode 100644
index 7b18946ae0..0000000000
--- a/lib/compiler/src/beam_split.erl
+++ /dev/null
@@ -1,90 +0,0 @@
-%%
-%% %CopyrightBegin%
-%%
-%% Copyright Ericsson AB 2011-2018. All Rights Reserved.
-%%
-%% Licensed under the Apache License, Version 2.0 (the "License");
-%% you may not use this file except in compliance with the License.
-%% You may obtain a copy of the License at
-%%
-%%     http://www.apache.org/licenses/LICENSE-2.0
-%%
-%% Unless required by applicable law or agreed to in writing, software
-%% distributed under the License is distributed on an "AS IS" BASIS,
-%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-%% See the License for the specific language governing permissions and
-%% limitations under the License.
-%%
-%% %CopyrightEnd%
-%%
-
--module(beam_split).
--export([module/2]).
-
--import(lists, [reverse/1]).
-
--spec module(beam_utils:module_code(), [compile:option()]) ->
-                    {'ok',beam_utils:module_code()}.
-
-module({Mod,Exp,Attr,Fs0,Lc}, _Opts) ->
-    Fs = [split_blocks(F) || F <- Fs0],
-    {ok,{Mod,Exp,Attr,Fs,Lc}}.
-
-%% We must split the basic block when we encounter instructions with labels,
-%% such as catches and BIFs. All labels must be visible outside the blocks.
-
-split_blocks({function,Name,Arity,CLabel,Is0}) ->
-    Is = split_blocks(Is0, []),
-    {function,Name,Arity,CLabel,Is}.
-
-split_blocks([{block,Bl}|Is], Acc0) ->
-    Acc = split_block(Bl, [], Acc0),
-    split_blocks(Is, Acc);
-split_blocks([I|Is], Acc) ->
-    split_blocks(Is, [I|Acc]);
-split_blocks([], Acc) -> reverse(Acc).
-
-split_block([{set,[R],As,{bif,N,{f,Lbl}=Fail}}|Is], Bl, Acc) when Lbl =/= 0 ->
-    split_block(Is, [], [{bif,N,Fail,As,R}|make_block(Bl, Acc)]);
-split_block([{set,[],[],{line,_}=Line},
-             {set,[R],As,{bif,raise,{f,_}=Fail}}|Is], Bl, Acc) ->
-    split_block(Is, [], [{bif,raise,Fail,As,R},Line|make_block(Bl, Acc)]);
-split_block([{set,[R],As,{alloc,Live,{gc_bif,N,{f,Lbl}=Fail}}}|Is], Bl, Acc)
-  when Lbl =/= 0 ->
-    split_block(Is, [], [{gc_bif,N,Fail,Live,As,R}|make_block(Bl, Acc)]);
-split_block([{set,[D],[S|Puts],{alloc,R,{put_map,Op,{f,Lbl}=Fail}}}|Is],
-	    Bl, Acc) when Lbl =/= 0 ->
-    split_block(Is, [], [{put_map,Fail,Op,S,D,R,{list,Puts}}|
-			 make_block(Bl, Acc)]);
-split_block([{set,[R],[],{try_catch,Op,L}}|Is], Bl, Acc) ->
-    split_block(Is, [], [{Op,R,L}|make_block(Bl, Acc)]);
-split_block([I|Is], Bl, Acc) ->
-    split_block(Is, [I|Bl], Acc);
-split_block([], Bl, Acc) -> make_block(Bl, Acc).
-
-make_block([], Acc) -> Acc;
-make_block([{set,[D],Ss,{bif,Op,Fail}}|Bl]=Bl0, Acc) ->
-    %% If the last instruction in the block is a comparison or boolean operator
-    %% (such as '=:='), move it out of the block to facilitate further
-    %% optimizations.
-    Arity = length(Ss),
-    case erl_internal:comp_op(Op, Arity) orelse
-	erl_internal:new_type_test(Op, Arity) orelse
-	erl_internal:bool_op(Op, Arity) of
-	false ->
-	    [{block,reverse(Bl0)}|Acc];
-	true ->
-	    I = {bif,Op,Fail,Ss,D},
-	    case Bl =:= [] of
-		true -> [I|Acc];
-		false -> [I,{block,reverse(Bl)}|Acc]
-	    end
-    end;
-make_block([{set,[Dst],[Src],move}|Bl], Acc) ->
-    %% Make optimization of {move,Src,Dst}, {jump,...} possible.
-    I = {move,Src,Dst},
-    case Bl =:= [] of
-	true -> [I|Acc];
-	false -> [I,{block,reverse(Bl)}|Acc]
-    end;
-make_block(Bl, Acc) -> [{block,reverse(Bl)}|Acc].
diff --git a/lib/compiler/src/beam_ssa.erl b/lib/compiler/src/beam_ssa.erl
index a2766a0501..fc13ba06de 100644
--- a/lib/compiler/src/beam_ssa.erl
+++ b/lib/compiler/src/beam_ssa.erl
@@ -27,11 +27,14 @@
          fold_instrs_rpo/4,
          linearize/1,
          mapfold_instrs_rpo/4,
+         normalize/1,
+         no_side_effect/1,
          predecessors/1,
          rename_vars/3,
          rpo/1,rpo/2,
          split_blocks/3,
          successors/1,successors/2,
+         trim_unreachable/1,
          update_phi_labels/4,used/1]).
 
 -export_type([b_module/0,b_function/0,b_blk/0,b_set/0,
@@ -102,7 +105,7 @@
 -type cg_prim_op() :: 'bs_get' | 'bs_match_string' | 'bs_restore' | 'bs_skip' |
 'copy' | 'put_tuple_arity' | 'put_tuple_element'.
 
--import(lists, [foldl/3,mapfoldl/3,reverse/1]).
+-import(lists, [foldl/3,keyfind/3,mapfoldl/3,member/2,reverse/1]).
 
 -spec add_anno(Key, Value, Construct) -> Construct when
       Key :: atom(),
@@ -150,6 +153,37 @@ clobbers_xregs(#b_set{op=Op}) ->
         _ -> false
     end.
 
+%% no_side_effect(#b_set{}) -> true|false.
+%%  Test whether this instruction has no side effect and thus is safe
+%%  not to execute if its value is not used. Note that even if `true`
+%%  is returned, the instruction could still be impure (e.g. bif:get).
+
+-spec no_side_effect(b_set()) -> boolean().
+
+no_side_effect(#b_set{op=Op}) ->
+    case Op of
+        {bif,_} -> true;
+        {float,get} -> true;
+        bs_init -> true;
+        bs_extract -> true;
+        bs_match -> true;
+        bs_start_match -> true;
+        bs_test_tail -> true;
+        bs_put -> true;
+        extract -> true;
+        get_hd -> true;
+        get_tl -> true;
+        get_tuple_element -> true;
+        has_map_field -> true;
+        is_nonempty_list -> true;
+        is_tagged_tuple -> true;
+        put_map -> true;
+        put_list -> true;
+        put_tuple -> true;
+        succeeded -> true;
+        _ -> false
+    end.
+
 -spec predecessors(Blocks) -> #{BlockNumber:=[Predecessor]} when
       Blocks :: block_map(),
       BlockNumber :: label(),
@@ -180,6 +214,69 @@ successors(#b_blk{last=Terminator}) ->
             []
     end.
 
+%% normalize(Instr0) -> Instr.
+%%  Normalize instructions to help optimizations.
+%%
+%%  For commutative operators (such as '+' and 'or'), always
+%%  place a variable operand before a literal operand.
+%%
+%%  Normalize #b_br{} to one of the following forms:
+%%
+%%    #b_br{b_literal{val=true},succ=Label,fail=Label}
+%%    #b_br{b_var{},succ=Label1,fail=Label2} where Label1 =/= Label2
+%%
+%%  Simplify a #b_switch{} with a literal argument to a #b_br{}.
+%%
+%%  Simplify a #b_switch{} with a variable argument and an empty
+%%  switch list to a #b_br{}.
+
+-spec normalize(b_set() | terminator()) ->
+                       b_set() | terminator().
+
+normalize(#b_set{op={bif,Bif},args=Args}=Set) ->
+    case {is_commutative(Bif),Args} of
+        {false,_} ->
+            Set;
+        {true,[#b_literal{}=Lit,#b_var{}=Var]} ->
+            Set#b_set{args=[Var,Lit]};
+        {true,_} ->
+            Set
+    end;
+normalize(#b_set{}=Set) ->
+    Set;
+normalize(#b_br{}=Br) ->
+    case Br of
+        #b_br{bool=Bool,succ=Same,fail=Same} ->
+            case Bool of
+                #b_literal{val=true} ->
+                    Br;
+                _ ->
+                    Br#b_br{bool=#b_literal{val=true}}
+            end;
+        #b_br{bool=#b_literal{val=true},succ=Succ} ->
+            Br#b_br{fail=Succ};
+        #b_br{bool=#b_literal{val=false},fail=Fail} ->
+            Br#b_br{bool=#b_literal{val=true},succ=Fail};
+        #b_br{} ->
+            Br
+    end;
+normalize(#b_switch{arg=Arg,fail=Fail,list=List}=Sw) ->
+    case Arg of
+        #b_literal{} ->
+            case keyfind(Arg, 1, List) of
+                false ->
+                    #b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail};
+                {Arg,L} ->
+                    #b_br{bool=#b_literal{val=true},succ=L,fail=L}
+            end;
+        #b_var{} when List =:= [] ->
+            #b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail};
+        #b_var{} ->
+            Sw
+    end;
+normalize(#b_ret{}=Ret) ->
+    Ret.
+
 -spec successors(label(), block_map()) -> [label()].
 
 successors(L, Blocks) ->
@@ -312,14 +409,19 @@ fold_po(Fun, From, Acc0, Blocks) ->
 
 %% linearize(Blocks) -> [{BlockLabel,#b_blk{}}].
 %%  Linearize the intermediate representation of the code.
+%%  Unreachable blocks will be discarded, and phi nodes will
+%%  be adjusted so that they no longer refers to discarded
+%%  blocks or to blocks that no longer are predecessors of
+%%  the phi node block.
 
 -spec linearize(Blocks) -> Linear when
       Blocks :: block_map(),
       Linear :: [{label(),b_blk()}].
 
 linearize(Blocks) ->
-    Seen = gb_sets:empty(),
-    {Linear,_} = linearize_1([0], Blocks, Seen, []),
+    Seen = cerl_sets:new(),
+    {Linear0,_} = linearize_1([0], Blocks, Seen, []),
+    Linear = fix_phis(Linear0, #{}),
     Linear.
 
 -spec rpo(Blocks) -> [Label] when
@@ -335,7 +437,7 @@ rpo(Blocks) ->
       Labels :: [label()].
 
 rpo(From, Blocks) ->
-    Seen = gb_sets:empty(),
+    Seen = cerl_sets:new(),
     {Ls,_} = rpo_1(From, Blocks, Seen, []),
     Ls.
 
@@ -346,7 +448,7 @@ rename_vars(Rename, From, Blocks) when is_list(Rename) ->
     rename_vars(maps:from_list(Rename), From, Blocks);
 rename_vars(Rename, From, Blocks) when is_map(Rename)->
     Top = rpo(From, Blocks),
-    Preds = gb_sets:from_list(Top),
+    Preds = cerl_sets:from_list(Top),
     F = fun(#b_set{op=phi,args=Args0}=Set) ->
                 Args = rename_phi_vars(Args0, Preds, Rename),
                 Set#b_set{args=Args};
@@ -379,6 +481,19 @@ split_blocks(P, Blocks, Count) ->
     Ls = beam_ssa:rpo(Blocks),
     split_blocks_1(Ls, P, Blocks, Count).
 
+-spec trim_unreachable(Blocks0) -> Blocks when
+      Blocks0 :: block_map(),
+      Blocks :: block_map().
+
+%% trim_unreachable(Blocks0) -> Blocks.
+%%  Remove all unreachable blocks. Adjust all phi nodes so
+%%  they don't refer to blocks that has been removed or no
+%%  no longer branch to the phi node in question.
+
+trim_unreachable(Blocks) ->
+    %% Could perhaps be optimized if there is any need.
+    maps:from_list(linearize(Blocks)).
+
 %% update_phi_labels([BlockLabel], Old, New, Blocks0) -> Blocks.
 %%  In the given blocks, replace label Old in with New in all
 %%  phi nodes. This is useful after merging or splitting
@@ -424,6 +539,20 @@ used(_) -> [].
 %%% Internal functions.
 %%%
 
+is_commutative('and') -> true;
+is_commutative('or') -> true;
+is_commutative('xor') -> true;
+is_commutative('band') -> true;
+is_commutative('bor') -> true;
+is_commutative('bxor') -> true;
+is_commutative('+') -> true;
+is_commutative('*') -> true;
+is_commutative('=:=') -> true;
+is_commutative('==') -> true;
+is_commutative('=/=') -> true;
+is_commutative('/=') -> true;
+is_commutative(_) -> false.
+
 def_used_1([#b_blk{is=Is,last=Last}|Bs], Preds, Def0, Used0) ->
     {Def,Used1} = def_used_is(Is, Preds, Def0, Used0),
     Used = gb_sets:union(gb_sets:from_list(used(Last)), Used1),
@@ -501,11 +630,11 @@ flatmapfold_instrs_rpo_1([], _, Blocks, Acc) ->
     {Blocks,Acc}.
 
 linearize_1([L|Ls], Blocks, Seen0, Acc0) ->
-    case gb_sets:is_member(L, Seen0) of
+    case cerl_sets:is_element(L, Seen0) of
         true ->
             linearize_1(Ls, Blocks, Seen0, Acc0);
         false ->
-            Seen1 = gb_sets:insert(L, Seen0),
+            Seen1 = cerl_sets:add_element(L, Seen0),
             Block = maps:get(L, Blocks),
             Successors = successors(Block),
             {Acc,Seen} = linearize_1(Successors, Blocks, Seen1, Acc0),
@@ -514,13 +643,40 @@ linearize_1([L|Ls], Blocks, Seen0, Acc0) ->
 linearize_1([], _, Seen, Acc) ->
     {Acc,Seen}.
 
+fix_phis([{L,Blk0}|Bs], S) ->
+    Blk = case Blk0 of
+              #b_blk{is=[#b_set{op=phi}|_]=Is0} ->
+                  Is = fix_phis_1(Is0, L, S),
+                  Blk0#b_blk{is=Is};
+              #b_blk{} ->
+                  Blk0
+          end,
+    Successors = successors(Blk),
+    [{L,Blk}|fix_phis(Bs, S#{L=>Successors})];
+fix_phis([], _) -> [].
+
+fix_phis_1([#b_set{op=phi,args=Args0}=I|Is], L, S) ->
+    Args = [{Val,Pred} || {Val,Pred} <- Args0,
+                          is_successor(L, Pred, S)],
+    [I#b_set{args=Args}|fix_phis_1(Is, L, S)];
+fix_phis_1(Is, _, _) -> Is.
+
+is_successor(L, Pred, S) ->
+    case S of
+        #{Pred:=Successors} ->
+            member(L, Successors);
+        #{} ->
+            %% This block has been removed.
+            false
+    end.
+
 rpo_1([L|Ls], Blocks, Seen0, Acc0) ->
-    case gb_sets:is_member(L, Seen0) of
+    case cerl_sets:is_element(L, Seen0) of
         true ->
             rpo_1(Ls, Blocks, Seen0, Acc0);
         false ->
             Block = maps:get(L, Blocks),
-            Seen1 = gb_sets:insert(L, Seen0),
+            Seen1 = cerl_sets:add_element(L, Seen0),
             Successors = successors(Block),
             {Acc,Seen} = rpo_1(Successors, Blocks, Seen1, Acc0),
             rpo_1(Ls, Blocks, Seen, [L|Acc])
@@ -540,7 +696,7 @@ rename_var(#b_remote{mod=Mod0,name=Name0}=Remote, Rename) ->
 rename_var(Old, _) -> Old.
 
 rename_phi_vars([{Var,L}|As], Preds, Ren) ->
-    case gb_sets:is_member(L, Preds) of
+    case cerl_sets:is_element(L, Preds) of
         true ->
             [{rename_var(Var, Ren),L}|rename_phi_vars(As, Preds, Ren)];
         false ->
diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl
index 006c41c0e0..40c2d8c07a 100644
--- a/lib/compiler/src/beam_ssa_codegen.erl
+++ b/lib/compiler/src/beam_ssa_codegen.erl
@@ -1180,6 +1180,16 @@ cg_copy_1([#cg_set{dst=Dst0,args=Args}|T], St) ->
     end;
 cg_copy_1([], _St) -> [].
 
+bif_to_test('and', [V1,V2], Fail) ->
+    [{test,is_eq_exact,Fail,[V1,{atom,true}]},
+     {test,is_eq_exact,Fail,[V2,{atom,true}]}];
+bif_to_test('or', [V1,V2], {f,Lbl}=Fail) when Lbl =/= 0 ->
+    %% Labels are spaced 2 apart. We can create a new
+    %% label by incrementing the Fail label.
+    SuccLabel = Lbl + 1,
+    [{test,is_eq_exact,{f,SuccLabel},[V1,{atom,false}]},
+     {test,is_eq_exact,Fail,[V2,{atom,true}]},
+     {label,SuccLabel}];
 bif_to_test('not', [Var], Fail) ->
     [{test,is_eq_exact,Fail,[Var,{atom,false}]}];
 bif_to_test(Name, Args, Fail) ->
@@ -1260,21 +1270,29 @@ cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=[#b_local{}=Func0|Args0]},
     Call = build_call(call, Arity, {f,FuncLbl}, Context, Dst),
     Is = setup_args(Args, Anno, Context, St) ++ Line ++ Call,
     {Is,St};
-cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=[#b_remote{}=Func0|Args0]},
+cg_call(#cg_set{anno=Anno0,op=call,dst=Dst0,args=[#b_remote{}=Func0|Args0]},
         Where, Context, St) ->
     [Dst|Args] = beam_args([Dst0|Args0], St),
     #b_remote{mod=Mod0,name=Name0,arity=Arity} = Func0,
     case {beam_arg(Mod0, St),beam_arg(Name0, St)} of
         {{atom,Mod},{atom,Name}} ->
             Func = {extfunc,Mod,Name,Arity},
-            Line = call_line(Where, Func, Anno),
+            Line = call_line(Where, Func, Anno0),
             Call = build_call(call_ext, Arity, Func, Context, Dst),
+            Anno = case erl_bifs:is_exit_bif(Mod, Name, Arity) of
+                       true ->
+                           %% There is no need to kill Y registers
+                           %% before calling an exit BIF.
+                           maps:remove(kill_yregs, Anno0);
+                       false ->
+                           Anno0
+                   end,
             Is = setup_args(Args, Anno, Context, St) ++ Line ++ Call,
             {Is,St};
         {Mod,Name} ->
             Apply = build_apply(Arity, Context, Dst),
-            Is = setup_args(Args++[Mod,Name], Anno, Context, St) ++
-                [line(Anno)] ++ Apply,
+            Is = setup_args(Args++[Mod,Name], Anno0, Context, St) ++
+                [line(Anno0)] ++ Apply,
             {Is,St}
     end;
 cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=Args0},
@@ -1785,7 +1803,9 @@ is_gc_bif(Bif, Args) ->
 %% new_label(St) -> {L,St}.
 
 new_label(#cg{lcount=Next}=St) ->
-    {Next,St#cg{lcount=Next+1}}.
+    %% Advance the label counter by 2 to allow us to create
+    %% a label for 'or' by incrementing an existing label.
+    {Next,St#cg{lcount=Next+2}}.
 
 %% call_line(tail|body, Func, Anno) -> [] | [{line,...}].
 %%  Produce a line instruction if it will be needed by the
diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl
new file mode 100644
index 0000000000..7cdb4315fe
--- /dev/null
+++ b/lib/compiler/src/beam_ssa_dead.erl
@@ -0,0 +1,1001 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2018. All Rights Reserved.
+%%
+%% Licensed under the Apache License, Version 2.0 (the "License");
+%% you may not use this file except in compliance with the License.
+%% You may obtain a copy of the License at
+%%
+%%     http://www.apache.org/licenses/LICENSE-2.0
+%%
+%% Unless required by applicable law or agreed to in writing, software
+%% distributed under the License is distributed on an "AS IS" BASIS,
+%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%% See the License for the specific language governing permissions and
+%% limitations under the License.
+%%
+%% %CopyrightEnd%
+%%
+%% Dead code is code that is executed but has no effect. This
+%% optimization pass either removes dead code or jumps around it,
+%% potentially making it unreachable so that it can be dropped
+%% the next time beam_ssa:linearize/1 is called.
+%%
+
+-module(beam_ssa_dead).
+-export([opt/1]).
+
+-include("beam_ssa.hrl").
+-import(lists, [append/1,last/1,member/2,takewhile/2,reverse/1]).
+
+-type used_vars() :: #{beam_ssa:label():=ordsets:ordset(beam_ssa:var_name())}.
+
+-type basic_type_test() :: atom() | {'is_tagged_tuple',pos_integer(),atom()}.
+-type type_test() :: basic_type_test() | {'not',basic_type_test()}.
+-type op_name() :: atom().
+-type basic_rel_op() :: {op_name(),beam_ssa:b_var(),beam_ssa:value()} |
+                         {basic_type_test(),beam_ssa:value()}.
+-type rel_op() :: {op_name(),beam_ssa:b_var(),beam_ssa:value()} |
+                  {type_test(),beam_ssa:value()}.
+
+-record(st,
+        {bs :: beam_ssa:block_map(),
+         us :: used_vars(),
+         skippable :: #{beam_ssa:label():='true'},
+         rel_op=none :: 'none' | rel_op(),
+         target=any :: 'any' | 'one_way' | beam_ssa:label()
+        }).
+
+-spec opt([{Label0,Block0}]) -> [{Label,Block}] when
+      Label0 :: beam_ssa:label(),
+      Block0 :: beam_ssa:b_blk(),
+      Label :: beam_ssa:label(),
+      Block :: beam_ssa:b_blk().
+
+opt(Linear) ->
+    {Used,Skippable} = used_vars(Linear),
+    Blocks0 = maps:from_list(Linear),
+    St0 = #st{bs=Blocks0,us=Used,skippable=Skippable},
+    St = shortcut_opt(St0),
+    #st{bs=Blocks} = combine_eqs(St),
+    beam_ssa:linearize(Blocks).
+
+%%%
+%%% Shortcut br/switch targets.
+%%%
+%%% A br/switch may branch to another br/switch that in turn always
+%%% branches to another target. Rewrite br/switch to refer to the
+%%% ultimate targets directly. That will save execution time, but
+%%% could also reduce the size of the code if some of the original
+%%% targets become unreachable and be deleted.
+%%%
+%%% When rewriting branches, we must be careful not to skip instructions
+%%% that have side effects or that bind variables that will be used
+%%% at the new target.
+%%%
+%%% We must also avoid branching to phi nodes.  The reason is
+%%% twofold. First, we might create a critical edge which is strictly
+%%% forbidden. Second, there will be a branch from a block that is not
+%%% listed in the list of predecessors in the phi node.  Those
+%%% limitations could probably be overcome, but it is not clear how
+%%% much that would improve the code.
+%%%
+
+shortcut_opt(#st{bs=Blocks}=St) ->
+    %% Processing the blocks in reverse post order seems to give more
+    %% opportunities for optimizations compared to post order. (Based on
+    %% running scripts/diffable with both PO and RPO and looking at
+    %% the diff.)
+    Ls = beam_ssa:rpo(Blocks),
+    shortcut_opt(Ls, #{from=>0}, St).
+
+shortcut_opt([L|Ls], Bs0, #st{bs=Blocks0}=St) ->
+    #b_blk{is=Is,last=Last0} = Blk0 = get_block(L, St),
+    Bs = Bs0#{from:=L},
+    case shortcut_terminator(Last0, Is, Bs, St) of
+        Last0 ->
+            %% No change. No need to update the block.
+            shortcut_opt(Ls, Bs, St);
+        Last ->
+            %% The terminator was simplified in some way.
+            %% Update the block.
+            Blk = Blk0#b_blk{last=Last},
+            Blocks = Blocks0#{L=>Blk},
+            shortcut_opt(Ls, Bs, St#st{bs=Blocks})
+    end;
+shortcut_opt([], _, St) -> St.
+
+shortcut_terminator(#b_br{bool=#b_literal{val=true},succ=Succ0},
+                    _Is, Bs, St0) ->
+    St = St0#st{rel_op=none},
+    shortcut(Succ0, Bs, St);
+shortcut_terminator(#b_br{bool=#b_var{}=Bool,succ=Succ0,fail=Fail0}=Br,
+                    Is, Bs, St0) ->
+    St = St0#st{target=one_way},
+    RelOp = get_rel_op(Bool, Is),
+    SuccBs = bind_var(Bool, #b_literal{val=true}, Bs),
+    BrSucc = shortcut(Succ0, SuccBs, St#st{rel_op=RelOp}),
+    FailBs = bind_var(Bool, #b_literal{val=false}, Bs),
+    BrFail = shortcut(Fail0, FailBs, St#st{rel_op=invert_op(RelOp)}),
+    case {BrSucc,BrFail} of
+        {#b_br{bool=#b_literal{val=true},succ=Succ},
+         #b_br{bool=#b_literal{val=true},succ=Fail}}
+          when Succ =/= Succ0; Fail =/= Fail0 ->
+            %% One or both of the targets were cut short.
+            beam_ssa:normalize(Br#b_br{succ=Succ,fail=Fail});
+        {_,_} ->
+            %% No change.
+            Br
+    end;
+shortcut_terminator(#b_switch{arg=Bool,list=List0}=Sw, _Is, Bs, St) ->
+    List = shortcut_switch(List0, Bool, Bs, St),
+    beam_ssa:normalize(Sw#b_switch{list=List});
+shortcut_terminator(Last, _Is, _Bs, _St) ->
+    Last.
+
+shortcut_switch([{Lit,L0}|T], Bool, Bs, St0) ->
+    St = St0#st{rel_op=normalize_op({bif,'=:='}, [Bool,Lit])},
+    #b_br{bool=#b_literal{val=true},succ=L} =
+        shortcut(L0, bind_var(Bool, Lit, Bs), St#st{target=one_way}),
+    [{Lit,L}|shortcut_switch(T, Bool, Bs, St0)];
+shortcut_switch([], _, _, _) -> [].
+
+shortcut(L, Bs, St) ->
+    shortcut_1(L, Bs, ordsets:new(), St).
+
+shortcut_1(L, Bs0, UnsetVars0, St) ->
+    case shortcut_2(L, Bs0, UnsetVars0, St) of
+        none ->
+            %% No more shortcuts found. Package up the previous
+            %% label in an unconditional branch.
+            #b_br{bool=#b_literal{val=true},succ=L,fail=L};
+        {#b_br{bool=#b_var{}}=Br,_,_} ->
+            %% This is a two-way branch. We can't do any better.
+            Br;
+        {#b_br{bool=#b_literal{val=true},succ=Succ},Bs,UnsetVars} ->
+            %% This is a safe `br`, but try to find a better one.
+            shortcut_1(Succ, Bs#{from:=L}, UnsetVars, St)
+    end.
+
+%% Try to shortcut this block, branching to a successor.
+shortcut_2(L, Bs0, UnsetVars0, St) ->
+    #b_blk{is=Is,last=Last} = get_block(L, St),
+    case eval_is(Is, Bs0, St) of
+        none ->
+            %% It is not safe to avoid this block because it
+            %% has instructions with potential side effects.
+            none;
+        Bs ->
+            %% The instructions in the block (if any) don't
+            %% have any side effects and can be skipped.
+            %% Evaluate the terminator.
+            case eval_terminator(Last, Bs, St) of
+                none ->
+                    %% The terminator is not suitable (could be
+                    %% because it is a switch that can't be simplified
+                    %% or it is a ret instruction).
+                    none;
+                #b_br{}=Br ->
+                    %% 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=#b_var{name=V}} <- Is],
+                    UnsetVars = ordsets:union(UnsetVars0,
+                                              ordsets:from_list(UnsetVars1)),
+
+                    %% Continue checking whether this br is suitable.
+                    shortcut_3(Br, Bs#{from:=L}, UnsetVars, St)
+            end
+    end.
+
+shortcut_3(Br, Bs, UnsetVars, #st{target=Target}=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;
+        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.
+                    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
+    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 ->
+            Res;
+        none ->
+            case shortcut_2(Fail, Bs0, UnsetVars0, St#st{target=Succ}) of
+                {#b_br{bool=#b_literal{},succ=Succ},_,_}=Res ->
+                    Res;
+                none ->
+                    none
+            end
+    end.
+
+get_block(L, St) ->
+    #st{bs=#{L:=Blk}} = St,
+    Blk.
+
+is_br_safe(UnsetVars, Br, #st{us=Us}=St) ->
+    %% Check that none of the unset variables will be used.
+    case Br of
+        #b_br{bool=#b_var{name=V},succ=Succ,fail=Fail} ->
+            #{Succ:=Used0,Fail:=Used1} = Us,
+
+            %% A two-way branch never branches to a phi node, so there
+            %% is no need to check for phi nodes here.
+             not member(V, UnsetVars) andalso
+                ordsets:is_disjoint(Used0, UnsetVars) andalso
+                ordsets:is_disjoint(Used1, UnsetVars);
+        #b_br{succ=Same,fail=Same} ->
+            %% An unconditional branch must not jump to
+            %% a phi node.
+            not is_forbidden(Same, St) andalso
+                ordsets:is_disjoint(map_get(Same, Us), UnsetVars)
+    end.
+
+is_forbidden(L, St) ->
+    case get_block(L, St) of
+        #b_blk{is=[#b_set{op=phi}|_]} -> true;
+        #b_blk{is=[#b_set{op=peek_message}|_]} -> true;
+        #b_blk{} -> false
+    end.
+
+
+%% Evaluate the instructions in the block.
+%% Return the updated bindings, or 'none' if there is
+%% any instruction with potential side effects.
+
+eval_is([#b_set{op=phi,dst=Dst,args=Args}|Is], Bs0, St) ->
+    From = maps:get(from, Bs0),
+    [Val] = [Val || {Val,Pred} <- Args, Pred =:= From],
+    Bs = bind_var(Dst, Val, Bs0),
+    eval_is(Is, Bs, St);
+eval_is([#b_set{op={bif,_},dst=Dst}=I0|Is], Bs, St) ->
+    I = sub(I0, Bs),
+    case eval_bif(I, St) of
+        #b_literal{}=Val ->
+            eval_is(Is, bind_var(Dst, Val, Bs), St);
+        none ->
+            eval_is(Is, Bs, St)
+    end;
+eval_is([#b_set{op=Op,dst=Dst}=I|Is], Bs, St)
+  when Op =:= is_tagged_tuple; Op =:= is_nonempty_list ->
+    #b_set{args=Args} = sub(I, Bs),
+    case eval_rel_op(Op, Args, St) of
+        #b_literal{}=Val ->
+            eval_is(Is, bind_var(Dst, Val, Bs), St);
+        none ->
+            eval_is(Is, Bs, St)
+    end;
+eval_is([#b_set{}=I|Is], Bs, St) ->
+    case beam_ssa:no_side_effect(I) of
+        true ->
+            %% This instruction has no side effects. It can
+            %% safely be omitted.
+            eval_is(Is, Bs, St);
+        false ->
+            %% This instruction may have some side effect.
+            %% It is not safe to avoid this instruction.
+            none
+    end;
+eval_is([], Bs, _St) -> Bs.
+
+eval_terminator(#b_br{bool=#b_var{}=Bool}=Br, Bs, _St) ->
+    Val = get_value(Bool, Bs),
+    beam_ssa:normalize(Br#b_br{bool=Val});
+eval_terminator(#b_br{bool=#b_literal{}}=Br, _Bs, _St) ->
+    beam_ssa:normalize(Br);
+eval_terminator(#b_switch{arg=Arg,fail=Fail,list=List}=Sw, Bs, St) ->
+    case get_value(Arg, Bs) of
+        #b_literal{}=Val ->
+            %% Literal argument. Simplify to a `br`.
+            beam_ssa:normalize(Sw#b_switch{arg=Val});
+        #b_var{} ->
+            case St of
+                #st{rel_op=none} ->
+                    %% No previous relational operator is stored.
+                    %% Give up.
+                    none;
+                #st{} ->
+                    %% There is a previous relational operator stored.
+                    %% Try optimizing the switch.
+                    case eval_switch(List, Arg, St, Fail) of
+                        none ->
+                            none;
+                        To when is_integer(To) ->
+                            %% Either one of the values in the switch
+                            %% matched a previous value in a '=:=' test, or
+                            %% none of the values matched a previous test.
+                            #b_br{bool=#b_literal{val=true},succ=To,fail=To}
+                    end
+            end
+    end;
+eval_terminator(#b_ret{}, _Bs, _St) ->
+    none.
+
+eval_switch([{Lit,Lbl}|T], Arg, St, Fail) ->
+    case eval_rel_op({bif,'=:='}, [Arg,Lit], St) of
+        none ->
+            %% This label could be reached.
+            eval_switch(T, Arg, St, none);
+        #b_literal{val=false} ->
+            %% This branch will never be taken.
+            eval_switch(T, Arg, St, Fail);
+        #b_literal{val=true} ->
+            %% Success. This branch will always be taken.
+            Lbl
+    end;
+eval_switch([], _Arg, _St, Fail) ->
+    %% Fail is now either the failure label or 'none'.
+    Fail.
+
+bind_var(Var, Val0, Bs) ->
+    Val = get_value(Val0, Bs),
+    Bs#{Var=>Val}.
+
+get_value(#b_var{}=Var, Bs) ->
+    case Bs of
+        #{Var:=Val} -> get_value(Val, Bs);
+        #{} -> Var
+    end;
+get_value(#b_literal{}=Lit, _Bs) -> Lit.
+
+eval_bif(#b_set{op={bif,Bif},args=Args}, St) ->
+    Arity = length(Args),
+    case erl_bifs:is_pure(erlang, Bif, Arity) of
+        false ->
+            none;
+        true ->
+            case [Lit || #b_literal{val=Lit} <- Args] of
+                LitArgs when length(LitArgs) =:= Arity ->
+                    try apply(erlang, Bif, LitArgs) of
+                        Val -> #b_literal{val=Val}
+                    catch
+                        error:_ -> none
+                    end;
+                _ ->
+                    %% Not literal arguments. Try to evaluate
+                    %% it based on a previous relational operator.
+                    eval_rel_op({bif,Bif}, Args, St)
+            end
+    end.
+
+%%%
+%%% Handling of relational operators.
+%%%
+
+get_rel_op(Bool, [_|_]=Is) ->
+    case last(Is) of
+        #b_set{op=Op,dst=Bool,args=Args} ->
+            normalize_op(Op, Args);
+        #b_set{} ->
+            none
+    end;
+get_rel_op(_, []) -> none.
+
+%% normalize_op(Instruction) -> {Normalized,FailLabel} | error
+%%    Normalized = {Operator,Variable,Variable|Literal} |
+%%                 {TypeTest,Variable}
+%%    Operation = '<' | '=<' | '=:=' | '=/=' | '>=' | '>'
+%%    TypeTest = is_atom | is_integer ...
+%%    Variable = #b_var{}
+%%    Literal = #b_literal{}
+%%
+%%  Normalize a relational operator to facilitate further
+%%  comparisons between operators. Always make the register
+%%  operand the first operand. If there are two registers,
+%%  order the registers in lexical order.
+%%
+%%  For example, this instruction:
+%%
+%%    #b_set{op={bif,=<},args=[#b_literal{}, #b_var{}}
+%%
+%%  will be normalized to:
+%%
+%%    {'=<',#b_var{},#b_literal{}}
+
+-spec normalize_op(Op, Args) -> NormalizedOp | 'none' when
+      Op :: beam_ssa:op(),
+      Args :: [beam_ssa:value()],
+      NormalizedOp :: basic_rel_op().
+
+normalize_op(is_tagged_tuple, [Arg,#b_literal{val=Size},#b_literal{val=Tag}])
+  when is_integer(Size), is_atom(Tag) ->
+    {{is_tagged_tuple,Size,Tag},Arg};
+normalize_op(is_nonempty_list, [Arg]) ->
+    {is_nonempty_list,Arg};
+normalize_op({bif,Bif}, [Arg]) ->
+    case erl_internal:new_type_test(Bif, 1) of
+        true -> {Bif,Arg};
+        false -> none
+    end;
+normalize_op({bif,Bif}, [_,_]=Args) ->
+    case erl_internal:comp_op(Bif, 2) of
+        true ->
+            normalize_op_1(Bif, Args);
+        false ->
+            none
+    end;
+normalize_op(_, _) -> none.
+
+normalize_op_1(Bif, Args) ->
+    case Args of
+        [#b_literal{}=Arg1,#b_var{}=Arg2] ->
+            {turn_op(Bif),Arg2,Arg1};
+        [#b_var{}=Arg1,#b_literal{}=Arg2] ->
+            {Bif,Arg1,Arg2};
+        [#b_var{}=A,#b_var{}=B] ->
+            if A < B -> {Bif,A,B};
+               true -> {turn_op(Bif),B,A}
+            end;
+        [#b_literal{},#b_literal{}] ->
+            none
+    end.
+
+-spec invert_op(basic_rel_op() | 'none') -> rel_op() | 'none'.
+
+invert_op({Op,Arg1,Arg2}) ->
+    {invert_op_1(Op),Arg1,Arg2};
+invert_op({TypeTest,Arg}) ->
+    {{'not',TypeTest},Arg};
+invert_op(none) -> none.
+
+invert_op_1('>=') -> '<';
+invert_op_1('<') -> '>=';
+invert_op_1('=<') -> '>';
+invert_op_1('>') -> '=<';
+invert_op_1('=:=') -> '=/=';
+invert_op_1('=/=') -> '=:=';
+invert_op_1('==') -> '/=';
+invert_op_1('/=') -> '=='.
+
+turn_op('<') -> '>';
+turn_op('=<') -> '>=';
+turn_op('>') -> '<';
+turn_op('>=') -> '=<';
+turn_op('=:='=Op) -> Op;
+turn_op('=/='=Op) -> Op;
+turn_op('=='=Op) -> Op;
+turn_op('/='=Op) -> Op.
+
+eval_rel_op(_Bif, _Args, #st{rel_op=none}) ->
+    none;
+eval_rel_op(Bif, Args, #st{rel_op=Prev}) ->
+    case normalize_op(Bif, Args) of
+        none ->
+            none;
+        RelOp ->
+            case will_succeed(Prev, RelOp) of
+                yes -> #b_literal{val=true};
+                no -> #b_literal{val=false};
+                maybe -> none
+            end
+    end.
+
+%% will_succeed(PrevCondition, Condition) -> yes | no | maybe
+%%  PrevCondition is a condition known to be true. This function
+%%  will tell whether Condition will succeed.
+
+will_succeed({_Op,_Var,_Value}=Same, {_Op,_Var,_Value}=Same) ->
+    %% Repeated test.
+    yes;
+will_succeed({Op1,Var,#b_literal{val=A}}, {Op2,Var,#b_literal{val=B}}) ->
+    will_succeed_1(Op1, A, Op2, B);
+will_succeed({Op1,Var,#b_var{}=A}, {Op2,Var,#b_var{}=B}) ->
+    will_succeed_vars(Op1, A, Op2, B);
+will_succeed({'=:=',Var,#b_literal{val=A}}, {TypeTest,Var}) ->
+    eval_type_test(TypeTest, A);
+will_succeed({_,_}=Same, {_,_}=Same) ->
+    %% Repeated type test.
+    yes;
+will_succeed({Test1,Var}, {Test2,Var}) ->
+    will_succeed_test(Test1, Test2);
+will_succeed({_,_}, {_,_}) ->
+    maybe;
+will_succeed({_,_}, {_,_,_}) ->
+    maybe;
+will_succeed({_,_,_}, {_,_}) ->
+    maybe;
+will_succeed({_,_,_}, {_,_,_}) ->
+    maybe.
+
+will_succeed_test({'not',Test1}, Test2) ->
+    case Test1 =:= Test2 of
+        true -> no;
+        false -> maybe
+    end;
+will_succeed_test(is_tuple, {is_tagged_tuple,_,_}) ->
+    maybe;
+will_succeed_test({is_tagged_tuple,_,_}, is_tuple) ->
+    yes;
+will_succeed_test(is_list, is_nonempty_list) ->
+    maybe;
+will_succeed_test(is_nonempty_list, is_list) ->
+    yes;
+will_succeed_test(T1, T2) ->
+    case is_numeric_test(T1) andalso is_numeric_test(T2) of
+        true -> maybe;
+        false -> no
+    end.
+
+will_succeed_1('=:=', A, '<', B) ->
+    if
+	B =< A -> no;
+	true -> yes
+    end;
+will_succeed_1('=:=', A, '=<', B) ->
+    if
+	B < A -> no;
+	true -> yes
+    end;
+will_succeed_1('=:=', A, '=:=', B) when A =/= B ->
+    no;
+will_succeed_1('=:=', A, '=/=', B) ->
+    if
+	A =:= B -> no;
+	true -> yes
+    end;
+will_succeed_1('=:=', A, '>=', B) ->
+    if
+	B > A -> no;
+	true -> yes
+    end;
+will_succeed_1('=:=', A, '>', B) ->
+    if
+	B >= A -> no;
+	true -> yes
+    end;
+
+will_succeed_1('=/=', A, '=:=', B) when A =:= B -> no;
+
+will_succeed_1('<', A, '=:=', B)  when B >= A -> no;
+will_succeed_1('<', A, '=/=', B)  when B >= A -> yes;
+will_succeed_1('<', A, '<',   B)  when B >= A -> yes;
+will_succeed_1('<', A, '=<',  B)  when B > A  -> yes;
+will_succeed_1('<', A, '>=',  B)  when B > A  -> no;
+will_succeed_1('<', A, '>',   B)  when B >= A -> no;
+
+will_succeed_1('=<', A, '=:=', B) when B > A  -> no;
+will_succeed_1('=<', A, '=/=', B) when B > A  -> yes;
+will_succeed_1('=<', A, '<',   B) when B > A  -> yes;
+will_succeed_1('=<', A, '=<',  B) when B >= A -> yes;
+will_succeed_1('=<', A, '>=',  B) when B > A  -> no;
+will_succeed_1('=<', A, '>',   B) when B >= A -> no;
+
+will_succeed_1('>=', A, '=:=', B) when B < A  -> no;
+will_succeed_1('>=', A, '=/=', B) when B < A  -> yes;
+will_succeed_1('>=', A, '<',   B) when B =< A -> no;
+will_succeed_1('>=', A, '=<',  B) when B < A  -> no;
+will_succeed_1('>=', A, '>=',  B) when B =< A -> yes;
+will_succeed_1('>=', A, '>',   B) when B < A  -> yes;
+
+will_succeed_1('>', A, '=:=', B)  when B =< A -> no;
+will_succeed_1('>', A, '=/=', B)  when B =< A -> yes;
+will_succeed_1('>', A, '<',   B)  when B =< A -> no;
+will_succeed_1('>', A, '=<',  B)  when B < A  -> no;
+will_succeed_1('>', A, '>=',  B)  when B =< A -> yes;
+will_succeed_1('>', A, '>',   B)  when B < A  -> yes;
+
+will_succeed_1('==', A, '==', B) ->
+    if
+	A == B -> yes;
+	true -> no
+    end;
+will_succeed_1('==', A, '/=', B) ->
+    if
+	A == B -> no;
+	true -> yes
+    end;
+will_succeed_1('/=', A, '/=', B) when A == B -> yes;
+will_succeed_1('/=', A, '==', B) when A == B -> no;
+
+will_succeed_1(_, _, _, _) -> maybe.
+
+will_succeed_vars('=/=', Val, '=:=', Val) -> no;
+will_succeed_vars('=:=', Val, '=/=', Val) -> no;
+will_succeed_vars('=:=', Val, '>=',  Val) -> yes;
+will_succeed_vars('=:=', Val, '=<',  Val) -> yes;
+
+will_succeed_vars('/=', Val1, '==', Val2) when Val1 == Val2 -> no;
+will_succeed_vars('==', Val1, '/=', Val2) when Val1 == Val2 -> no;
+
+will_succeed_vars(_, _, _, _) -> maybe.
+
+is_numeric_test(is_float) -> true;
+is_numeric_test(is_integer) -> true;
+is_numeric_test(is_number) -> true;
+is_numeric_test(_) -> false.
+
+eval_type_test(Test, Arg) ->
+    case eval_type_test_1(Test, Arg) of
+        true -> yes;
+        false -> no
+    end.
+
+eval_type_test_1(is_nonempty_list, Arg) ->
+    case Arg of
+        [_|_] -> true;
+        _ -> false
+    end;
+eval_type_test_1({is_tagged_tuple,Sz,Tag}, Arg) ->
+    if
+        tuple_size(Arg) =:= Sz, element(1, Arg) =:= Tag ->
+            true;
+        true ->
+            false
+    end;
+eval_type_test_1(Test, Arg) ->
+    erlang:Test(Arg).
+
+%%%
+%%% Combine bif:'=:=' and switch instructions
+%%% to switch instructions.
+%%%
+%%% Consider this code:
+%%%
+%%%     0:
+%%%       @ssa_bool = bif:'=:=' Var, literal 1
+%%%       br @ssa_bool, label 2, label 3
+%%%
+%%%     2:
+%%%       ret literal a
+%%%
+%%%     3:
+%%%       @ssa_bool:7 = bif:'=:=' Var, literal 2
+%%%       br @ssa_bool:7, label 4, label 999
+%%%
+%%%     4:
+%%%       ret literal b
+%%%
+%%%     999:
+%%%       .
+%%%       .
+%%%       .
+%%%
+%%% The two bif:'=:=' instructions can be combined
+%%% to a switch:
+%%%
+%%%     0:
+%%%       switch Var, label 999, [ { literal 1, label 2 },
+%%%                                { literal 2, label 3 } ]
+%%%
+%%%     2:
+%%%       ret literal a
+%%%
+%%%     4:
+%%%       ret literal b
+%%%
+%%%     999:
+%%%       .
+%%%       .
+%%%       .
+%%%
+
+combine_eqs(#st{bs=Blocks}=St) ->
+    Ls = reverse(beam_ssa:rpo(Blocks)),
+    combine_eqs_1(Ls, St).
+
+combine_eqs_1([L|Ls], #st{bs=Blocks0}=St0) ->
+    case comb_get_sw(L, St0) of
+        none ->
+            combine_eqs_1(Ls, St0);
+        {_,Arg,_,Fail0,List0} ->
+            case comb_get_sw(Fail0, St0) of
+                {true,Arg,Fail1,Fail,List1} ->
+                    %% Another switch/br with the same arguments was
+                    %% found. Try combining them.
+                    case combine_lists(Fail1, List0, List1, Blocks0) of
+                        none ->
+                            %% Different types of literals in the lists,
+                            %% or the success cases in the first switch
+                            %% could branch to the second switch
+                            %% (increasing code size and repeating tests).
+                            combine_eqs_1(Ls, St0);
+                        List ->
+                            %% Everything OK! Combine the lists.
+                            Sw0 = #b_switch{arg=Arg,fail=Fail,list=List},
+                            Sw = beam_ssa:normalize(Sw0),
+                            Blk0 = maps:get(L, Blocks0),
+                            Blk = Blk0#b_blk{last=Sw},
+                            Blocks = Blocks0#{L:=Blk},
+                            St = St0#st{bs=Blocks},
+                            combine_eqs_1(Ls, St)
+                    end;
+                {true,_OtherArg,_,_,_} ->
+                    %% The other switch/br uses a different Arg.
+                    combine_eqs_1(Ls, St0);
+                {false,_,_,_,_} ->
+                    %% Not safe: Bindings of variables that will be used
+                    %% or execution of instructions with potential
+                    %% side effects will be skipped.
+                    combine_eqs_1(Ls, St0);
+                none ->
+                    %% No switch/br at this label.
+                    combine_eqs_1(Ls, St0)
+            end
+    end;
+combine_eqs_1([], St) -> St.
+
+comb_get_sw(L, Blocks) ->
+    comb_get_sw(L, true, Blocks).
+
+comb_get_sw(L, Safe0, #st{bs=Blocks,skippable=Skippable}=St) ->
+    #b_blk{is=Is,last=Last} = maps:get(L, Blocks),
+    Safe1 = Safe0 andalso is_map_key(L, Skippable),
+    case Last of
+        #b_ret{} ->
+            none;
+        #b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail} ->
+            case comb_is(Is, Bool, Safe1) of
+                {none,_} ->
+                    none;
+                {#b_set{op={bif,'=:='},args=[#b_var{}=Arg,#b_literal{}=Lit]},Safe} ->
+                    {Safe,Arg,L,Fail,[{Lit,Succ}]};
+                {#b_set{},_} ->
+                    none
+            end;
+        #b_br{bool=#b_literal{val=true},succ=Succ} ->
+            comb_get_sw(Succ, Safe1, St);
+        #b_switch{arg=#b_var{}=Arg,fail=Fail,list=List} ->
+            {none,Safe} = comb_is(Is, none, Safe1),
+            {Safe,Arg,L,Fail,List}
+    end.
+
+comb_is([#b_set{dst=#b_var{}=Bool}=I], Bool, Safe) ->
+    {I,Safe};
+comb_is([#b_set{}=I|Is], Bool, Safe0) ->
+    Safe = Safe0 andalso beam_ssa:no_side_effect(I),
+    comb_is(Is, Bool, Safe);
+comb_is([], _Bool, Safe) ->
+    {none,Safe}.
+
+%% combine_list(Fail, List1, List2, Blocks) -> List|none.
+%%  Try to combine two switch lists, returning the combined
+%%  list or 'none' if not possible.
+%%
+%%  The values in the two lists must be all of the same type.
+%%
+%%  The code reached from the labels in the first list must
+%%  not reach the failure label (if they do, tests could
+%%  be repeated).
+%%
+
+combine_lists(Fail, L1, L2, Blocks) ->
+    Ls = beam_ssa:rpo([Lbl || {_,Lbl} <- L1], Blocks),
+    case member(Fail, Ls) of
+        true ->
+            %% One or more of labels in the first list
+            %% could reach the failure label. That
+            %% means that the second switch/br instruction
+            %% will be retained, increasing code size and
+            %% potentially also execution time.
+            none;
+        false ->
+            %% The combined switch will replace both original
+            %% br/switch instructions, leading to a reduction in code
+            %% size and potentially also in execution time.
+            combine_lists_1(L1, L2)
+    end.
+
+combine_lists_1(List0, List1) ->
+    case are_lists_compatible(List0, List1) of
+        true ->
+            First = maps:from_list(List0),
+            List0 ++ [{Val,Lbl} || {Val,Lbl} <- List1,
+                                   not is_map_key(Val, First)];
+        false ->
+            none
+    end.
+
+are_lists_compatible([{#b_literal{val=Val1},_}|_],
+                     [{#b_literal{val=Val2},_}|_]) ->
+    case lit_type(Val1) of
+        none -> false;
+        Type -> Type =:= lit_type(Val2)
+    end.
+
+lit_type(Val) ->
+    if
+        is_atom(Val) -> atom;
+        is_float(Val) -> float;
+        is_integer(Val) -> integer;
+        true -> none
+    end.
+
+%%%
+%%% Calculate used variables for each block.
+%%%
+
+used_vars(Linear) ->
+    used_vars(reverse(Linear), #{}, #{}).
+
+used_vars([{L,#b_blk{is=Is}=Blk}|Bs], UsedVars0, Skip0) ->
+    %% Calculate the variables used by each block and its
+    %% successors. This information is used by
+    %% shortcut_opt/1.
+
+    Successors = beam_ssa:successors(Blk),
+    Used0 = used_vars_succ(Successors, L, UsedVars0),
+    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).
+
+    Defined0 = [Def || #b_set{dst=#b_var{name=Def}} <- Is],
+    Defined = ordsets:from_list(Defined0),
+    MaySkip = ordsets:is_disjoint(Defined, Used0),
+    case MaySkip of
+        true ->
+            Skip = Skip0#{L=>true},
+            used_vars(Bs, UsedVars, Skip);
+        false ->
+            used_vars(Bs, UsedVars, Skip0)
+    end;
+used_vars([], UsedVars, Skip) ->
+    {UsedVars,Skip}.
+
+used_vars_succ([S|Ss], L, UsedVars) ->
+    Live0 = used_vars_succ(Ss, L, UsedVars),
+    Key = {S,L},
+    case UsedVars of
+        #{Key:=Live} ->
+            ordsets:union(Live, Live0);
+        #{S:=Live} ->
+            ordsets:union(Live, Live0);
+        #{} ->
+            Live0
+    end;
+used_vars_succ([], _, _) ->
+    ordsets:new().
+
+used_vars_phis(Is, L, Live0, UsedVars0) ->
+    UsedVars = UsedVars0#{L=>Live0},
+    Phis = takewhile(fun(#b_set{op=Op}) -> Op =:= phi end, Is),
+    case Phis of
+        [] ->
+            UsedVars;
+        [_|_] ->
+            PhiArgs = append([Args || #b_set{args=Args} <- Phis]),
+            case [{P,V} || {#b_var{name=V},P} <- PhiArgs] of
+                [_|_]=PhiVars ->
+                    PhiLive0 = rel2fam(PhiVars),
+                    PhiLive = [{{L,P},ordsets:union(ordsets:from_list(Vs), Live0)} ||
+                                  {P,Vs} <- PhiLive0],
+                    maps:merge(UsedVars, maps:from_list(PhiLive));
+                [] ->
+                    %% There were only literals in the phi node(s).
+                    UsedVars
+            end
+    end.
+
+used_vars_blk(#b_blk{is=Is,last=Last}, Used0) ->
+    Used = ordsets:union(Used0, beam_ssa:used(Last)),
+    used_vars_is(reverse(Is), Used).
+
+used_vars_is([#b_set{op=phi}|Is], Used) ->
+    used_vars_is(Is, Used);
+used_vars_is([#b_set{dst=#b_var{name=Dst}}=I|Is], Used0) ->
+    Used1 = ordsets:union(Used0, beam_ssa:used(I)),
+    Used = ordsets:del_element(Dst, Used1),
+    used_vars_is(Is, Used);
+used_vars_is([], Used) ->
+    Used.
+
+%%%
+%%% Common utilities.
+%%%
+
+sub(#b_set{args=Args}=I, Sub) ->
+    I#b_set{args=[sub_arg(A, Sub) || A <- Args]}.
+
+sub_arg(Old, Sub) ->
+    case Sub of
+        #{Old:=New} -> New;
+        #{} -> Old
+    end.
+
+rel2fam(S0) ->
+    S1 = sofs:relation(S0),
+    S = sofs:rel2fam(S1),
+    sofs:to_external(S).
diff --git a/lib/compiler/src/beam_ssa_opt.erl b/lib/compiler/src/beam_ssa_opt.erl
index da466a3316..83ee918b25 100644
--- a/lib/compiler/src/beam_ssa_opt.erl
+++ b/lib/compiler/src/beam_ssa_opt.erl
@@ -48,16 +48,28 @@ functions([], _Ps) -> [].
 
 passes(Opts0) ->
     Ps = [?PASS(ssa_opt_split_blocks),
+          ?PASS(ssa_opt_coalesce_phis),
           ?PASS(ssa_opt_element),
           ?PASS(ssa_opt_linearize),
           ?PASS(ssa_opt_record),
+
+          %% Run ssa_opt_cse twice, because it will help ssa_opt_dead,
+          %% and ssa_opt_dead will help ssa_opt_cse. Run ssa_opt_live
+          %% twice, because it will help ssa_opt_dead and ssa_opt_dead
+          %% will help ssa_opt_live.
           ?PASS(ssa_opt_cse),
           ?PASS(ssa_opt_type),
-          ?PASS(ssa_opt_float),
           ?PASS(ssa_opt_live),
+          ?PASS(ssa_opt_dead),
+          ?PASS(ssa_opt_cse),                   %Second time.
+          ?PASS(ssa_opt_float),
+          ?PASS(ssa_opt_live),                  %Second time.
+
           ?PASS(ssa_opt_bsm),
           ?PASS(ssa_opt_bsm_shortcut),
           ?PASS(ssa_opt_misc),
+          ?PASS(ssa_opt_tuple_size),
+          ?PASS(ssa_opt_sw),
           ?PASS(ssa_opt_blockify),
           ?PASS(ssa_opt_sink),
           ?PASS(ssa_opt_merge_blocks)],
@@ -88,6 +100,9 @@ function(#b_function{anno=Anno,bs=Blocks0,args=Args,cnt=Count0}=F, Ps) ->
 %%% Trivial sub passes.
 %%%
 
+ssa_opt_dead(#st{ssa=Linear}=St) ->
+    St#st{ssa=beam_ssa_dead:opt(Linear)}.
+
 ssa_opt_linearize(#st{ssa=Blocks}=St) ->
     St#st{ssa=beam_ssa:linearize(Blocks)}.
 
@@ -117,6 +132,102 @@ ssa_opt_split_blocks(#st{ssa=Blocks0,cnt=Count0}=St) ->
     St#st{ssa=Blocks,cnt=Count}.
 
 %%%
+%%% Coalesce phi nodes.
+%%%
+%%% Nested cases can led to code such as this:
+%%%
+%%%     10:
+%%%       _1 = phi {literal value1, label 8}, {Var, label 9}
+%%%       br 11
+%%%
+%%%     11:
+%%%       _2 = phi {_1, label 10}, {literal false, label 3}
+%%%
+%%% The phi nodes can be coalesced like this:
+%%%
+%%%     11:
+%%%       _2 = phi {literal value1, label 8}, {Var, label 9}, {literal false, label 3}
+%%%
+%%% Coalescing can help other optimizations, and can in some cases reduce register
+%%% shuffling (if the phi variables for two phi nodes happens to be allocated to
+%%% different registers).
+%%%
+
+ssa_opt_coalesce_phis(#st{ssa=Blocks0}=St) ->
+    Ls = beam_ssa:rpo(Blocks0),
+    Blocks = c_phis_1(Ls, Blocks0),
+    St#st{ssa=Blocks}.
+
+c_phis_1([L|Ls], Blocks0) ->
+    case maps:get(L, Blocks0) of
+        #b_blk{is=[#b_set{op=phi}|_]}=Blk ->
+            Blocks = c_phis_2(L, Blk, Blocks0),
+            c_phis_1(Ls, Blocks);
+        #b_blk{} ->
+            c_phis_1(Ls, Blocks0)
+    end;
+c_phis_1([], Blocks) -> Blocks.
+
+c_phis_2(L, #b_blk{is=Is0}=Blk0, Blocks0) ->
+    case c_phis_args(Is0, Blocks0) of
+        none ->
+            Blocks0;
+        {_,_,Preds}=Info ->
+            Is = c_rewrite_phis(Is0, Info),
+            Blk = Blk0#b_blk{is=Is},
+            Blocks = Blocks0#{L:=Blk},
+            c_fix_branches(Preds, L, Blocks)
+    end.
+
+c_phis_args([#b_set{op=phi,args=Args0}|Is], Blocks) ->
+    case c_phis_args_1(Args0, Blocks) of
+        none ->
+            c_phis_args(Is, Blocks);
+        Res ->
+            Res
+    end;
+c_phis_args(_, _Blocks) -> none.
+
+c_phis_args_1([{Var,Pred}|As], Blocks) ->
+    case c_get_pred_vars(Var, Pred, Blocks) of
+        none ->
+            c_phis_args_1(As, Blocks);
+        Result ->
+            Result
+    end;
+c_phis_args_1([], _Blocks) -> none.
+
+c_get_pred_vars(Var, Pred, Blocks) ->
+    case maps:get(Pred, Blocks) of
+        #b_blk{is=[#b_set{op=phi,dst=Var,args=Args}]} ->
+            {Var,Pred,Args};
+        #b_blk{} ->
+            none
+    end.
+
+c_rewrite_phis([#b_set{op=phi,args=Args0}=I|Is], Info) ->
+    Args = c_rewrite_phi(Args0, Info),
+    [I#b_set{args=Args}|c_rewrite_phis(Is, Info)];
+c_rewrite_phis(Is, _Info) -> Is.
+
+c_rewrite_phi([{Var,Pred}|As], {Var,Pred,Values}) ->
+    Values ++ As;
+c_rewrite_phi([{Value,Pred}|As], {_,Pred,Values}) ->
+    [{Value,P} || {_,P} <- Values] ++ As;
+c_rewrite_phi([A|As], Info) ->
+    [A|c_rewrite_phi(As, Info)];
+c_rewrite_phi([], _Info) -> [].
+
+c_fix_branches([{_,Pred}|As], L, Blocks0) ->
+    #b_blk{last=Last0} = Blk0 = maps:get(Pred, Blocks0),
+    #b_br{bool=#b_literal{val=true}} = Last0,   %Assertion.
+    Last = Last0#b_br{bool=#b_literal{val=true},succ=L,fail=L},
+    Blk = Blk0#b_blk{last=Last},
+    Blocks = Blocks0#{Pred:=Blk},
+    c_fix_branches(As, L, Blocks);
+c_fix_branches([], _, Blocks) -> Blocks.
+
+%%%
 %%% Order element/2 calls.
 %%%
 %%% Order an unbroken chain of element/2 calls for the same tuple
@@ -318,7 +429,13 @@ cse_successors(_Is, Blk, Es, M) ->
 
 cse_successors_1([L|Ls], Es0, M) ->
     case M of
+        #{L:=Es1} when map_size(Es1) =:= 0 ->
+            %% The map is already empty. No need to do anything
+            %% since the intersection will be empty.
+            cse_successors_1(Ls, Es0, M);
         #{L:=Es1} ->
+            %% Calculate the intersection of the two maps.
+            %% Both keys and values must match.
             Es = maps:filter(fun(Key, Value) ->
                                      case Es1 of
                                          #{Key:=Value} -> true;
@@ -381,11 +498,20 @@ cse_suitable(#b_set{op=get_hd}) -> true;
 cse_suitable(#b_set{op=get_tl}) -> true;
 cse_suitable(#b_set{op=put_list}) -> true;
 cse_suitable(#b_set{op=put_tuple}) -> true;
-cse_suitable(#b_set{op={bif,Name},args=Args}) ->
+cse_suitable(#b_set{op={bif,tuple_size}}) ->
+    %% Doing CSE for tuple_size/1 can prevent the
+    %% creation of test_arity and select_tuple_arity
+    %% instructions. That could decrease performance
+    %% and beam_validator could fail to understand
+    %% that tuple operations that follow are safe.
+    false;
+cse_suitable(#b_set{anno=Anno,op={bif,Name},args=Args}) ->
+    %% Doing CSE for floating point operators is unsafe.
     %% Doing CSE for comparison operators would prevent
     %% creation of 'test' instructions.
     Arity = length(Args),
-    not (erl_internal:new_type_test(Name, Arity) orelse
+    not (is_map_key(float_op, Anno) orelse
+         erl_internal:new_type_test(Name, Arity) orelse
          erl_internal:comp_op(Name, Arity) orelse
          erl_internal:bool_op(Name, Arity));
 cse_suitable(#b_set{}) -> false.
@@ -410,14 +536,15 @@ cse_suitable(#b_set{}) -> false.
         {s=undefined :: 'undefined' | 'cleared',
          regs=#{} :: #{beam_ssa:b_var():=beam_ssa:b_var()},
          fail=none :: 'none' | beam_ssa:label(),
-         ren=#{} :: #{beam_ssa:label():=beam_ssa:label()},
-         non_guards :: gb_sets:set(beam_ssa:label())
+         non_guards :: gb_sets:set(beam_ssa:label()),
+         bs :: beam_ssa:block_map()
         }).
 
 ssa_opt_float(#st{ssa=Linear0,cnt=Count0}=St) ->
     NonGuards0 = float_non_guards(Linear0),
     NonGuards = gb_sets:from_list(NonGuards0),
-    Fs = #fs{non_guards=NonGuards},
+    Blocks = maps:from_list(Linear0),
+    Fs = #fs{non_guards=NonGuards,bs=Blocks},
     {Linear,Count} = float_opt(Linear0, Count0, Fs),
     St#st{ssa=Linear,cnt=Count}.
 
@@ -430,42 +557,35 @@ float_non_guards([{L,#b_blk{is=Is}}|Bs]) ->
     end;
 float_non_guards([]) -> [?BADARG_BLOCK].
 
-float_opt([{L,Blk0}|Bs], Count, Fs) ->
-    Blk = float_rename_phis(Blk0, Fs),
-    case float_need_flush(Blk, Fs) of
-        true ->
-            float_flush(L, Blk, Bs, Count, Fs);
-        false ->
-            float_opt_1(L, Blk, Bs, Count, Fs)
-    end;
-float_opt([], Count, _Fs) ->
-    {[],Count}.
-
-float_opt_1(L, #b_blk{last=#b_br{fail=F}}=Blk, Bs0,
+float_opt([{L,#b_blk{last=#b_br{fail=F}}=Blk}|Bs0],
             Count0, #fs{non_guards=NonGuards}=Fs) ->
     case gb_sets:is_member(F, NonGuards) of
         true ->
             %% This block is not inside a guard.
             %% We can do the optimization.
-            float_opt_2(L, Blk, Bs0, Count0, Fs);
+            float_opt_1(L, Blk, Bs0, Count0, Fs);
         false ->
             %% This block is inside a guard. Don't do
             %% any floating point optimizations.
             {Bs,Count} = float_opt(Bs0, Count0, Fs),
             {[{L,Blk}|Bs],Count}
     end;
-float_opt_1(L, Blk, Bs, Count, Fs) ->
-    float_opt_2(L, Blk, Bs, Count, Fs).
+float_opt([{L,Blk}|Bs], Count, Fs) ->
+    float_opt_1(L, Blk, Bs, Count, Fs);
+float_opt([], Count, _Fs) ->
+    {[],Count}.
 
-float_opt_2(L, #b_blk{is=Is0}=Blk0, Bs0, Count0, Fs0) ->
+float_opt_1(L, #b_blk{is=Is0}=Blk0, Bs0, Count0, Fs0) ->
     case float_opt_is(Is0, Fs0, Count0, []) of
         {Is1,Fs1,Count1} ->
-            Fs = float_fail_label(Blk0, Fs1),
-            Split = float_split_conv(Is1, Blk0),
-            {Blks0,Count2} = float_number(Split, L, Count1),
-            {Blks,Count3} = float_conv(Blks0, Fs#fs.fail, Count2),
-            {Bs,Count} = float_opt(Bs0, Count3, Fs),
-            {Blks++Bs,Count};
+            Fs2 = float_fail_label(Blk0, Fs1),
+            Fail = Fs2#fs.fail,
+            {Flush,Blk,Fs,Count2} = float_maybe_flush(Blk0, Fs2, Count1),
+            Split = float_split_conv(Is1, Blk),
+            {Blks0,Count3} = float_number(Split, L, Count2),
+            {Blks,Count4} = float_conv(Blks0, Fail, Count3),
+            {Bs,Count} = float_opt(Bs0, Count4, Fs),
+            {Blks++Flush++Bs,Count};
         none ->
             {Bs,Count} = float_opt(Bs0, Count0, Fs0),
             {[{L,Blk0}|Bs],Count}
@@ -525,14 +645,42 @@ float_conv([{L,#b_blk{is=Is0}=Blk0}|Bs0], Fail, Count0) ->
             end
     end.
 
-float_need_flush(#b_blk{is=Is}, #fs{s=cleared}) ->
+float_maybe_flush(Blk0, #fs{s=cleared,fail=Fail,bs=Blocks}=Fs0, Count0) ->
+    #b_blk{last=#b_br{bool=#b_var{},succ=Succ}=Br} = Blk0,
+    #b_blk{is=Is} = maps:get(Succ, Blocks),
     case Is of
         [#b_set{anno=#{float_op:=_}}|_] ->
-            false;
+            %% The next operation is also a floating point operation.
+            %% No flush needed.
+            {[],Blk0,Fs0,Count0};
         _ ->
-            true
+            %% Flush needed.
+            {Bool0,Count1} = new_reg('@ssa_bool', Count0),
+            Bool = #b_var{name=Bool0},
+
+            %% Allocate block numbers.
+            CheckL = Count1,              %For checkerror.
+            FlushL = Count1 + 1,          %For flushing of float regs.
+            Count = Count1 + 2,
+            Blk = Blk0#b_blk{last=Br#b_br{succ=CheckL}},
+
+            %% Build the block with the checkerror instruction.
+            CheckIs = [#b_set{op={float,checkerror},dst=Bool}],
+            CheckBr = #b_br{bool=Bool,succ=FlushL,fail=Fail},
+            CheckBlk = #b_blk{is=CheckIs,last=CheckBr},
+
+            %% Build the block that flushes all registers.
+            FlushIs = float_flush_regs(Fs0),
+            FlushBr = #b_br{bool=#b_literal{val=true},succ=Succ,fail=Succ},
+            FlushBlk = #b_blk{is=FlushIs,last=FlushBr},
+
+            %% Update state and blocks.
+            Fs = Fs0#fs{s=undefined,regs=#{},fail=none},
+            FlushBs = [{CheckL,CheckBlk},{FlushL,FlushBlk}],
+            {FlushBs,Blk,Fs,Count}
     end;
-float_need_flush(_, _) -> false.
+float_maybe_flush(Blk, Fs, Count) ->
+    {[],Blk,Fs,Count}.
 
 float_opt_is([#b_set{op=succeeded,args=[Src]}=I0],
              #fs{regs=Rs}=Fs, Count, Acc) ->
@@ -557,27 +705,6 @@ float_opt_is([], Fs, _Count, _Acc) ->
     #fs{s=undefined} = Fs,                      %Assertion.
     none.
 
-float_rename_phis(#b_blk{is=Is}=Blk, #fs{ren=Ren}) ->
-    if
-        map_size(Ren) =:= 0 ->
-            Blk;
-        true ->
-            Blk#b_blk{is=float_rename_phis_1(Is, Ren)}
-    end.
-
-float_rename_phis_1([#b_set{op=phi,args=Args0}=I|Is], Ren) ->
-    Args = [float_phi_arg(Arg, Ren) || Arg <- Args0],
-    [I#b_set{args=Args}|float_rename_phis_1(Is, Ren)];
-float_rename_phis_1(Is, _) -> Is.
-
-float_phi_arg({Var,OldLbl}, Ren) ->
-    case Ren of
-        #{OldLbl:=NewLbl} ->
-            {Var,NewLbl};
-        #{} ->
-            {Var,OldLbl}
-    end.
-
 float_make_op(#b_set{op={bif,Op},dst=Dst,args=As0}=I0,
               Ts, #fs{s=S,regs=Rs0}=Fs, Count0) ->
     {As1,Rs1,Count1} = float_load(As0, Ts, Rs0, Count0, []),
@@ -634,37 +761,6 @@ new_reg(Base, Count) ->
     Fr = {Base,Count},
     {Fr,Count+1}.
 
-float_flush(L, Blk, Bs0, Count0, #fs{s=cleared,fail=Fail,ren=Ren0}=Fs0) ->
-    {Bool0,Count1} = new_reg('@ssa_bool', Count0),
-    Bool = #b_var{name=Bool0},
-
-    %% Insert two blocks before the current block. First allocate
-    %% block numbers.
-    FirstL = L,                                  %For checkerror.
-    MiddleL = Count1,                            %For flushed float regs.
-    LastL = Count1 + 1,                          %For original block.
-    Count2 = Count1 + 2,
-
-    %% Build the block with the checkerror instruction.
-    CheckIs = [#b_set{op={float,checkerror},dst=Bool}],
-    FirstBlk = #b_blk{is=CheckIs,last=#b_br{bool=Bool,succ=MiddleL,fail=Fail}},
-
-    %% Build the block that flushes all registers. Note that this must be a
-    %% separate block in case the original block begins with a phi instruction,
-    %% to avoid embedding a phi instruction in the middle of a block.
-    FlushIs = float_flush_regs(Fs0),
-    MiddleBlk = #b_blk{is=FlushIs,last=#b_br{bool=#b_literal{val=true},
-                                             succ=LastL,fail=LastL}},
-
-    %% The last block is the original unmodified block.
-    LastBlk = Blk,
-
-    %% Update state and blocks.
-    Ren = Ren0#{L=>LastL},
-    Fs = Fs0#fs{s=undefined,regs=#{},fail=none,ren=Ren},
-    Bs1 = [{FirstL,FirstBlk},{MiddleL,MiddleBlk},{LastL,LastBlk}|Bs0],
-    float_opt(Bs1, Count2, Fs).
-
 float_fail_label(#b_blk{last=Last}, Fs) ->
     case Last of
         #b_br{bool=#b_var{},fail=Fail} ->
@@ -721,11 +817,16 @@ live_opt_phis(Is, L, Live0, LiveMap0) ->
             LiveMap;
         [_|_] ->
             PhiArgs = append([Args || #b_set{args=Args} <- Phis]),
-            PhiVars = [{P,V} || {#b_var{name=V},P} <- PhiArgs],
-            PhiLive0 = rel2fam(PhiVars),
-            PhiLive = [{{L,P},gb_sets:union(gb_sets:from_list(Vs), Live0)} ||
-                          {P,Vs} <- PhiLive0],
-            maps:merge(LiveMap, maps:from_list(PhiLive))
+            case [{P,V} || {#b_var{name=V},P} <- PhiArgs] of
+                [_|_]=PhiVars ->
+                    PhiLive0 = rel2fam(PhiVars),
+                    PhiLive = [{{L,P},gb_sets:union(gb_sets:from_list(Vs), Live0)} ||
+                                  {P,Vs} <- PhiLive0],
+                    maps:merge(LiveMap, maps:from_list(PhiLive));
+                [] ->
+                    %% There were only literals in the phi node(s).
+                    LiveMap
+            end
     end.
 
 live_opt_blk(#b_blk{is=Is0,last=Last}=Blk, Live0) ->
@@ -769,14 +870,14 @@ live_opt_is([#b_set{op=succeeded,dst=#b_var{name=SuccDst}=SuccDstVar,
                     end
             end
     end;
-live_opt_is([#b_set{op=Op,dst=#b_var{name=Dst}}=I|Is], Live0, Acc) ->
+live_opt_is([#b_set{dst=#b_var{name=Dst}}=I|Is], Live0, Acc) ->
     case gb_sets:is_member(Dst, Live0) of
         true ->
             Live1 = gb_sets:union(Live0, gb_sets:from_ordset(beam_ssa:used(I))),
             Live = gb_sets:delete_any(Dst, Live1),
             live_opt_is(Is, Live, [I|Acc]);
         false ->
-            case is_pure(Op) of
+            case beam_ssa:no_side_effect(I) of
                 true ->
                     live_opt_is(Is, Live0, Acc);
                 false ->
@@ -787,19 +888,6 @@ live_opt_is([#b_set{op=Op,dst=#b_var{name=Dst}}=I|Is], Live0, Acc) ->
 live_opt_is([], Live, Acc) ->
     {Acc,Live}.
 
-is_pure({bif,_}) -> true;
-is_pure({float,get}) -> true;
-is_pure(bs_extract) -> true;
-is_pure(extract) -> true;
-is_pure(get_hd) -> true;
-is_pure(get_tl) -> true;
-is_pure(get_tuple_element) -> true;
-is_pure(is_nonempty_list) -> true;
-is_pure(is_tagged_tuple) -> true;
-is_pure(put_list) -> true;
-is_pure(put_tuple) -> true;
-is_pure(_) -> false.
-
 live_opt_unused(#b_set{op=get_map_element}=Set) ->
     {replace,Set#b_set{op=has_map_field}};
 live_opt_unused(_) -> keep.
@@ -941,6 +1029,22 @@ misc_opt_is([#b_set{op=phi}=I0|Is], Sub0, Acc) ->
         false ->
             misc_opt_is(Is, Sub0, [I|Acc])
     end;
+misc_opt_is([#b_set{op={bif,'and'}}=I0], Sub, Acc) ->
+    #b_set{dst=Dst,args=Args} = I = sub(I0, Sub),
+    case eval_and(Args) of
+        error ->
+            misc_opt_is([], Sub, [I|Acc]);
+        Val ->
+            misc_opt_is([], Sub#{Dst=>Val}, Acc)
+    end;
+misc_opt_is([#b_set{op={bif,'or'}}=I0], Sub, Acc) ->
+    #b_set{dst=Dst,args=Args} = I = sub(I0, Sub),
+    case eval_or(Args) of
+        error ->
+            misc_opt_is([], Sub, [I|Acc]);
+        Val ->
+            misc_opt_is([], Sub#{Dst=>Val}, Acc)
+    end;
 misc_opt_is([#b_set{}=I0|Is], Sub, Acc) ->
     #b_set{op=Op,dst=Dst,args=Args} = I = sub(I0, Sub),
     case make_literal(Op, Args) of
@@ -973,6 +1077,244 @@ make_literal_list([_|_], _) ->
 make_literal_list([], Acc) ->
     reverse(Acc).
 
+eval_and(Args) ->
+    case Args of
+        [_,#b_literal{val=false}=Res] -> Res;
+        [Res,#b_literal{val=true}] -> Res;
+        [_,_] -> error
+    end.
+
+eval_or(Args) ->
+    case Args of
+        [Res,#b_literal{val=false}] -> Res;
+        [_,#b_literal{val=true}=Res] -> Res;
+        [_,_] -> error
+    end.
+
+%%%
+%%% Optimize expressions such as "tuple_size(Var) =:= 2".
+%%%
+%%% Consider this code:
+%%%
+%%% 0:
+%%%   .
+%%%   .
+%%%   .
+%%%   Size = bif:tuple_size Var
+%%%   BoolVar1 = succeeded Size
+%%%   br BoolVar1, label 4, label 3
+%%%
+%%% 4:
+%%%   BoolVar2 = bif:'=:=' Size, literal 2
+%%%   br BoolVar2, label 6, label 3
+%%%
+%%% 6: ...   %% OK
+%%%
+%%% 3: ...   %% Not a tuple of size 2
+%%%
+%%% The BEAM code will look this:
+%%%
+%%%   {bif,tuple_size,{f,3},[{x,0}],{x,0}}.
+%%%   {test,is_eq_exact,{f,3},[{x,0},{integer,2}]}.
+%%%
+%%% Better BEAM code will be produced if we transform the
+%%% code like this:
+%%%
+%%% 0:
+%%%   .
+%%%   .
+%%%   .
+%%%   br label 10
+%%%
+%%% 10:
+%%%   NewBoolVar = bif:is_tuple Var
+%%%   br NewBoolVar, label 11, label 3
+%%%
+%%% 11:
+%%%   Size = bif:tuple_size Var
+%%%   br label 4
+%%%
+%%% 4:
+%%%   BoolVar2 = bif:'=:=' Size, literal 2
+%%%   br BoolVar2, label 6, label 3
+%%%
+%%% (The key part of the transformation is the removal of
+%%% the 'succeeded' instruction to signal to the code generator
+%%% that the call to tuple_size/1 can't fail.)
+%%%
+%%% The BEAM code will look like:
+%%%
+%%%   {test,is_tuple,{f,3},[{x,0}]}.
+%%%   {test_arity,{f,3},[{x,0},2]}.
+%%%
+%%% Those two instructions will be combined into a single
+%%% is_tuple_of_arity instruction by the loader.
+%%%
+
+ssa_opt_tuple_size(#st{ssa=Linear0,cnt=Count0}=St) ->
+    {Linear,Count} = opt_tup_size(Linear0, Count0, []),
+    St#st{ssa=Linear,cnt=Count}.
+
+opt_tup_size([{L,#b_blk{is=Is,last=Last}=Blk}|Bs], Count0, Acc0) ->
+    case {Is,Last} of
+        {[#b_set{op={bif,'=:='},dst=Bool,args=[#b_var{}=Tup,#b_literal{val=Arity}]}],
+         #b_br{bool=Bool}} when is_integer(Arity), Arity >= 0 ->
+            {Acc,Count} = opt_tup_size_1(Tup, L, Count0, Acc0),
+            opt_tup_size(Bs, Count, [{L,Blk}|Acc]);
+        {_,_} ->
+            opt_tup_size(Bs, Count0, [{L,Blk}|Acc0])
+    end;
+opt_tup_size([], Count, Acc) ->
+    {reverse(Acc),Count}.
+
+opt_tup_size_1(Size, EqL, Count0, [{L,Blk0}|Acc]) ->
+    case Blk0 of
+        #b_blk{is=Is0,last=#b_br{bool=Bool,succ=EqL,fail=Fail}} ->
+            case opt_tup_size_is(Is0, Bool, Size, []) of
+                none ->
+                    {[{L,Blk0}|Acc],Count0};
+                {PreIs,TupleSizeIs,Tuple} ->
+                    opt_tup_size_2(PreIs, TupleSizeIs, L, EqL,
+                                   Tuple, Fail, Count0, Acc)
+            end;
+        #b_blk{} ->
+            {[{L,Blk0}|Acc],Count0}
+    end;
+opt_tup_size_1(_, _, Count, Acc) ->
+    {Acc,Count}.
+
+opt_tup_size_2(PreIs, TupleSizeIs, PreL, EqL, Tuple, Fail, Count0, Acc) ->
+    IsTupleL = Count0,
+    TupleSizeL = Count0 + 1,
+    Bool = #b_var{name={'@ssa_bool',Count0+2}},
+    Count = Count0 + 3,
+
+    True = #b_literal{val=true},
+    PreBr = #b_br{bool=True,succ=IsTupleL,fail=IsTupleL},
+    PreBlk = #b_blk{is=PreIs,last=PreBr},
+
+    IsTupleIs = [#b_set{op={bif,is_tuple},dst=Bool,args=[Tuple]}],
+    IsTupleBr = #b_br{bool=Bool,succ=TupleSizeL,fail=Fail},
+    IsTupleBlk = #b_blk{is=IsTupleIs,last=IsTupleBr},
+
+    TupleSizeBr = #b_br{bool=True,succ=EqL,fail=EqL},
+    TupleSizeBlk = #b_blk{is=TupleSizeIs,last=TupleSizeBr},
+    {[{TupleSizeL,TupleSizeBlk},
+      {IsTupleL,IsTupleBlk},
+      {PreL,PreBlk}|Acc],Count}.
+
+opt_tup_size_is([#b_set{op={bif,tuple_size},dst=Size,args=[Tuple]}=I,
+                 #b_set{op=succeeded,dst=Bool,args=[Size]}],
+                Bool, Size, Acc) ->
+    {reverse(Acc),[I],Tuple};
+opt_tup_size_is([I|Is], Bool, Size, Acc) ->
+    opt_tup_size_is(Is, Bool, Size, [I|Acc]);
+opt_tup_size_is([], _, _, _Acc) -> none.
+
+%%%
+%%% 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.
 %%%
@@ -1283,20 +1625,23 @@ rel2fam(S0) ->
     S = sofs:rel2fam(S1),
     sofs:to_external(S).
 
-sub(#b_set{op=phi,args=Args}=I, Sub) ->
+sub(I, Sub) ->
+    beam_ssa:normalize(sub_1(I, Sub)).
+
+sub_1(#b_set{op=phi,args=Args}=I, Sub) ->
     I#b_set{args=[{sub_arg(A, Sub),P} || {A,P} <- Args]};
-sub(#b_set{args=Args}=I, Sub) ->
+sub_1(#b_set{args=Args}=I, Sub) ->
     I#b_set{args=[sub_arg(A, Sub) || A <- Args]};
-sub(#b_br{bool=#b_var{}=Old}=Br, Sub) ->
+sub_1(#b_br{bool=#b_var{}=Old}=Br, Sub) ->
     New = sub_arg(Old, Sub),
     Br#b_br{bool=New};
-sub(#b_switch{arg=#b_var{}=Old}=Sw, Sub) ->
+sub_1(#b_switch{arg=#b_var{}=Old}=Sw, Sub) ->
     New = sub_arg(Old, Sub),
     Sw#b_switch{arg=New};
-sub(#b_ret{arg=#b_var{}=Old}=Ret, Sub) ->
+sub_1(#b_ret{arg=#b_var{}=Old}=Ret, Sub) ->
     New = sub_arg(Old, Sub),
     Ret#b_ret{arg=New};
-sub(Last, _) -> Last.
+sub_1(Last, _) -> Last.
 
 sub_arg(#b_remote{mod=Mod,name=Name}=Rem, Sub) ->
     Rem#b_remote{mod=sub_arg(Mod, Sub),name=sub_arg(Name, Sub)};
diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl
index 54aa2efaf6..7f67e315f5 100644
--- a/lib/compiler/src/beam_ssa_pre_codegen.erl
+++ b/lib/compiler/src/beam_ssa_pre_codegen.erl
@@ -1016,14 +1016,19 @@ recv_fix_common_1([], [], _Msg, Blocks) -> Blocks.
 
 fix_exit_phi_args([V|Vs], [Rm|Rms], Exit, Blocks) ->
     Path = beam_ssa:rpo([Rm], Blocks),
-    Pred = exit_predecessor(Path, Exit),
-    [{V,Pred}|fix_exit_phi_args(Vs, Rms, Exit, Blocks)];
+    Preds = exit_predecessors(Path, Exit, Blocks),
+    [{V,Pred} || Pred <- Preds] ++ fix_exit_phi_args(Vs, Rms, Exit, Blocks);
 fix_exit_phi_args([], [], _, _) -> [].
 
-exit_predecessor([Pred,Exit|_], Exit) ->
-    Pred;
-exit_predecessor([_|Bs], Exit) ->
-    exit_predecessor(Bs, Exit).
+exit_predecessors([L|Ls], Exit, Blocks) ->
+    Blk = map_get(L, Blocks),
+    case member(Exit, beam_ssa:successors(Blk)) of
+        true ->
+            [L|exit_predecessors(Ls, Exit, Blocks)];
+        false ->
+            exit_predecessors(Ls, Exit, Blocks)
+    end;
+exit_predecessors([], _Exit, _Blocks) -> [].
 
 %% fix_receive([Label], Defs, Blocks0, Count0) -> {Blocks,Count}.
 %%  Add a copy instruction for all variables that are matched out and
diff --git a/lib/compiler/src/beam_ssa_type.erl b/lib/compiler/src/beam_ssa_type.erl
index e5f15da836..058e40106c 100644
--- a/lib/compiler/src/beam_ssa_type.erl
+++ b/lib/compiler/src/beam_ssa_type.erl
@@ -22,13 +22,15 @@
 -export([opt/2]).
 
 -include("beam_ssa.hrl").
--import(lists, [any/2,droplast/1,foldl/3,last/1,member/2,
-                reverse/1,search/2,sort/1]).
+-import(lists, [all/2,any/2,droplast/1,foldl/3,last/1,member/2,
+                reverse/1,sort/1]).
 
 -define(UNICODE_INT, #t_integer{elements={0,16#10FFFF}}).
 
 -record(d, {ds :: #{beam_ssa:var_name():=beam_ssa:b_set()},
-            ls :: #{beam_ssa:label():=type_db()}}).
+            ls :: #{beam_ssa:label():=type_db()},
+            sub :: #{beam_ssa:var_name():=beam_ssa:value()}
+           }).
 
 -define(ATOM_SET_SIZE, 5).
 
@@ -60,7 +62,7 @@ opt(Linear, Args) ->
                                               arity=0}]},
     Defs = maps:from_list([{V,FakeCall#b_set{dst=Var}} ||
                               #b_var{name=V}=Var <- Args]),
-    D = #d{ds=Defs,ls=#{0=>Ts}},
+    D = #d{ds=Defs,ls=#{0=>Ts},sub=#{}},
     opt_1(Linear, D).
 
 opt_1([{L,Blk}|Bs], #d{ls=Ls}=D) ->
@@ -71,9 +73,9 @@ opt_1([{L,Blk}|Bs], #d{ls=Ls}=D) ->
             %% This block is never reached. Discard it.
             opt_1(Bs, D)
     end;
-opt_1([], _) -> [].
+opt_1([], #d{}) -> [].
 
-opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, D0) ->
+opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, #d{sub=Sub}=D0) ->
     case Is0 of
         [#b_set{op=call,dst=Dst,
                 args=[#b_remote{mod=#b_literal{val=Mod},
@@ -84,7 +86,7 @@ opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, D0) ->
                     %% Rewrite the terminator to a 'ret', and remove
                     %% all type information for this label. That will
                     %% simplify the phi node in the former successor.
-                    Args = [simplify_arg(Arg, Ts) || Arg <- Args0],
+                    Args = simplify_args(Args0, Sub, Ts),
                     I = I0#b_set{args=[Rem|Args]},
                     Ret = #b_ret{arg=Dst},
                     Blk = Blk0#b_blk{is=[I],last=Ret},
@@ -98,61 +100,120 @@ opt_2(L, #b_blk{is=Is0}=Blk0, Bs, Ts, D0) ->
             opt_3(L, Blk0, Bs, Ts, D0)
     end.
 
-opt_3(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0, #d{ds=Ds0,ls=Ls0}=D0) ->
-    {Is,Ts,Ds} = opt_is(Is0, Ts0, Ds0, Ls0, []),
-    D1 = D0#d{ds=Ds},
-    Last = opt_terminator(Last0, Ts, Ds),
+opt_3(L, #b_blk{is=Is0,last=Last0}=Blk0, Bs, Ts0,
+      #d{ds=Ds0,ls=Ls0,sub=Sub0}=D0) ->
+    {Is,Ts,Ds,Sub} = opt_is(Is0, Ts0, Ds0, Ls0, Sub0, []),
+    D1 = D0#d{ds=Ds,sub=Sub},
+    Last1 = simplify_terminator(Last0, Sub, Ts),
+    Last = opt_terminator(Last1, Ts, Ds),
     D = update_successors(Last, Ts, D1),
     Blk = Blk0#b_blk{is=Is,last=Last},
     [{L,Blk}|opt_1(Bs, D)].
 
-opt_is([#b_set{op=phi,dst=#b_var{name=Dst},args=Args0}=I0|Is], Ts0, Ds0, Ls, Acc) ->
+simplify_terminator(#b_br{bool=Bool}=Br, Sub, Ts) ->
+    Br#b_br{bool=simplify_arg(Bool, Sub, Ts)};
+simplify_terminator(#b_switch{arg=Arg}=Sw, Sub, Ts) ->
+    Sw#b_switch{arg=simplify_arg(Arg, Sub, Ts)};
+simplify_terminator(#b_ret{arg=Arg}=Ret, Sub, Ts) ->
+    Ret#b_ret{arg=simplify_arg(Arg, Sub, Ts)}.
+
+opt_is([#b_set{op=phi,dst=#b_var{name=Dst},args=Args0}=I0|Is],
+       Ts0, Ds0, Ls, Sub0, Acc) ->
     %% Simplify the phi node by removing all predecessor blocks that no
     %% longer exists or no longer branches to this block.
-    Args = [P || {_,From}=P <- Args0, maps:is_key(From, Ls)],
-    I = I0#b_set{args=Args},
-    Ts = update_types(I, Ts0, Ds0),
-    Ds = Ds0#{Dst=>I},
-    opt_is(Is, Ts, Ds, Ls, [I|Acc]);
-opt_is([#b_set{dst=#b_var{name=Dst}}=I0|Is], Ts0, Ds0, Ls, Acc) ->
-    I = simplify(I0, Ts0),
-    Ts = update_types(I, Ts0, Ds0),
-    Ds = Ds0#{Dst=>I},
-    opt_is(Is, Ts, Ds, Ls, [I|Acc]);
-opt_is([], Ts, Ds, _Ls, Acc) ->
-    {reverse(Acc),Ts,Ds}.
+    Args = [{simplify_arg(Arg, Sub0, Ts0),From} ||
+               {Arg,From} <- Args0, maps:is_key(From, Ls)],
+    case all_same(Args) of
+        true ->
+            %% Eliminate the phi node if there is just one source
+            %% value or if the values are identical.
+            [{Val,_}|_] = Args,
+            Sub = Sub0#{Dst=>Val},
+            opt_is(Is, Ts0, Ds0, Ls, Sub, Acc);
+        false ->
+            I = I0#b_set{args=Args},
+            Ts = update_types(I, Ts0, Ds0),
+            Ds = Ds0#{Dst=>I},
+            opt_is(Is, Ts, Ds, Ls, Sub0, [I|Acc])
+    end;
+opt_is([#b_set{args=Args0,dst=#b_var{name=Dst}}=I0|Is],
+       Ts0, Ds0, Ls, Sub0, Acc) ->
+    Args = simplify_args(Args0, Sub0, Ts0),
+    I1 = beam_ssa:normalize(I0#b_set{args=Args}),
+    case simplify(I1, Ts0) of
+        #b_set{}=I2 ->
+            I = beam_ssa:normalize(I2),
+            Ts = update_types(I, Ts0, Ds0),
+            Ds = Ds0#{Dst=>I},
+            opt_is(Is, Ts, Ds, Ls, Sub0, [I|Acc]);
+        #b_literal{}=Lit ->
+            Sub = Sub0#{Dst=>Lit},
+            opt_is(Is, Ts0, Ds0, Ls, Sub, Acc);
+        #b_var{}=Var ->
+            Sub = Sub0#{Dst=>Var},
+            opt_is(Is, Ts0, Ds0, Ls, Sub, Acc)
+    end;
+opt_is([], Ts, Ds, _Ls, Sub, Acc) ->
+    {reverse(Acc),Ts,Ds,Sub}.
 
+simplify(#b_set{op={bif,'and'},args=Args}=I, Ts) ->
+    case is_safe_bool_op(Args, Ts) of
+        true ->
+            case Args of
+                [_,#b_literal{val=false}=Res] -> Res;
+                [Res,#b_literal{val=true}] -> Res;
+                _ -> eval_bif(I, Ts)
+            end;
+        false ->
+            I
+    end;
+simplify(#b_set{op={bif,'or'},args=Args}=I, Ts) ->
+    case is_safe_bool_op(Args, Ts) of
+        true ->
+            case Args of
+                [Res,#b_literal{val=false}] -> Res;
+                [_,#b_literal{val=true}=Res] -> Res;
+                _ -> eval_bif(I, Ts)
+            end;
+        false ->
+            I
+    end;
 simplify(#b_set{op={bif,element},args=[#b_literal{val=Index},Tuple]}=I, Ts) ->
     case t_tuple_size(get_type(Tuple, Ts)) of
         {_,Size} when is_integer(Index), 1 =< Index, Index =< Size ->
             I#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=Index-1}]};
         _ ->
-            I
+            eval_bif(I, Ts)
     end;
 simplify(#b_set{op={bif,hd},args=[List]}=I, Ts) ->
     case get_type(List, Ts) of
         cons ->
             I#b_set{op=get_hd};
         _ ->
-            I
+            eval_bif(I, Ts)
     end;
 simplify(#b_set{op={bif,tl},args=[List]}=I, Ts) ->
     case get_type(List, Ts) of
         cons ->
             I#b_set{op=get_tl};
         _ ->
-            I
+            eval_bif(I, Ts)
     end;
 simplify(#b_set{op={bif,size},args=[Term]}=I, Ts) ->
     case get_type(Term, Ts) of
         #t_tuple{} ->
-            I#b_set{op={bif,tuple_size}};
+            simplify(I#b_set{op={bif,tuple_size}}, Ts);
+        _ ->
+            eval_bif(I, Ts)
+    end;
+simplify(#b_set{op={bif,tuple_size},args=[Term]}=I, Ts) ->
+    case get_type(Term, Ts) of
+        #t_tuple{size=Size,exact=true} ->
+            #b_literal{val=Size};
         _ ->
             I
     end;
-simplify(#b_set{op={bif,'=='},args=Args0}=I0, Ts) ->
-    Args = [simplify_arg(Arg, Ts) || Arg <- Args0],
-    I = I0#b_set{args=Args},
+simplify(#b_set{op={bif,'=='},args=Args}=I, Ts) ->
     Types = get_types(Args, Ts),
     EqEq = case {meet(Types),join(Types)} of
                {none,any} -> true;
@@ -164,50 +225,147 @@ simplify(#b_set{op={bif,'=='},args=Args0}=I0, Ts) ->
            end,
     case EqEq of
         true ->
-            I#b_set{op={bif,'=:='}};
+            simplify(I#b_set{op={bif,'=:='}}, Ts);
         false ->
-            I
+            eval_bif(I, Ts)
+    end;
+simplify(#b_set{op={bif,'=:='},args=[Same,Same]}, _Ts) ->
+    #b_literal{val=true};
+simplify(#b_set{op={bif,'=:='},args=Args}=I, Ts) ->
+    case meet(get_types(Args, Ts)) of
+        none -> #b_literal{val=false};
+        _ -> eval_bif(I, Ts)
     end;
-simplify(#b_set{op={bif,Op},args=Args0}=I0, Ts) ->
-    Args = [simplify_arg(Arg, Ts) || Arg <- Args0],
-    I = I0#b_set{args=Args},
+simplify(#b_set{op={bif,Op},args=Args}=I, Ts) ->
     Types = get_types(Args, Ts),
     case is_float_op(Op, Types) of
         false ->
-            I;
+            eval_bif(I, Ts);
         true ->
             AnnoArgs = [anno_float_arg(A) || A <- Types],
-            beam_ssa:add_anno(float_op, AnnoArgs, I)
+            eval_bif(beam_ssa:add_anno(float_op, AnnoArgs, I), Ts)
     end;
-simplify(#b_set{op=wait_timeout,args=[Timeout0]}=I, Ts) ->
-    case simplify_arg(Timeout0, Ts) of
-        #b_literal{val=infinity} ->
-            I#b_set{op=wait,args=[]};
-        Timeout ->
-            I#b_set{args=[Timeout]}
+simplify(#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=0}]}=I, Ts) ->
+    case get_type(Tuple, Ts) of
+        #t_tuple{elements=[First]} ->
+            #b_literal{val=First};
+        #t_tuple{} ->
+            I
     end;
-simplify(#b_set{op=Op,args=Args0}=I, Ts) ->
-    Safe = case Op of
-               call -> true;
-               put_list -> true;
-               put_tuple -> true;
-               _ -> false
-           end,
-    case Safe of
-        true ->
-            Args = [simplify_arg(Arg, Ts) || Arg <- Args0],
-            I#b_set{args=Args};
+simplify(#b_set{op=is_nonempty_list,args=[Src]}=I, Ts) ->
+    case get_type(Src, Ts) of
+        any ->  I;
+        list -> I;
+        cons -> #b_literal{val=true};
+        _ ->    #b_literal{val=false}
+    end;
+simplify(#b_set{op=is_tagged_tuple,
+                args=[Src,#b_literal{val=Size},#b_literal{val=Tag}]}=I, Ts) ->
+    case get_type(Src, Ts) of
+        #t_tuple{exact=true,size=Size,elements=[Tag]} ->
+            #b_literal{val=true};
+        #t_tuple{exact=true,size=ActualSize,elements=[]} ->
+            if
+                Size =/= ActualSize ->
+                    #b_literal{val=false};
+                true ->
+                    I
+            end;
+        #t_tuple{exact=false} ->
+            I;
+        any ->
+            I;
+        _ ->
+            #b_literal{val=false}
+    end;
+simplify(#b_set{op=put_list,args=[#b_literal{val=H},
+                                  #b_literal{val=T}]}, _Ts) ->
+    #b_literal{val=[H|T]};
+simplify(#b_set{op=put_tuple,args=Args}=I, _Ts) ->
+    case make_literal_list(Args) of
+        none -> I;
+        List -> #b_literal{val=list_to_tuple(List)}
+    end;
+simplify(#b_set{op=succeeded,args=[#b_literal{}]}, _Ts) ->
+    #b_literal{val=true};
+simplify(#b_set{op=wait_timeout,args=[#b_literal{val=infinity}]}=I, _Ts) ->
+    I#b_set{op=wait,args=[]};
+simplify(I, _Ts) -> I.
+
+make_literal_list(Args) ->
+    make_literal_list(Args, []).
+
+make_literal_list([#b_literal{val=H}|T], Acc) ->
+    make_literal_list(T, [H|Acc]);
+make_literal_list([_|_], _) ->
+    none;
+make_literal_list([], Acc) ->
+    reverse(Acc).
+
+is_safe_bool_op(Args, Ts) ->
+    [T1,T2] = get_types(Args, Ts),
+    t_is_boolean(T1) andalso t_is_boolean(T2).
+
+all_same([{H,_}|T]) ->
+    all(fun({E,_}) -> E =:= H end, T).
+
+eval_bif(#b_set{op={bif,Bif},args=Args}=I, Ts) ->
+    Arity = length(Args),
+    case erl_bifs:is_pure(erlang, Bif, Arity) of
         false ->
-            I
+            I;
+        true ->
+            case make_literal_list(Args) of
+                none ->
+                    case get_types(Args, Ts) of
+                        [any] ->
+                            I;
+                        [Type] ->
+                            case will_succeed(Bif, Type) of
+                                yes ->
+                                    #b_literal{val=true};
+                                no ->
+                                    #b_literal{val=false};
+                                maybe ->
+                                    I
+                            end;
+                        _ ->
+                            I
+                    end;
+                LitArgs ->
+                    try apply(erlang, Bif, LitArgs) of
+                        Val -> #b_literal{val=Val}
+                    catch
+                        error:_ -> I
+                    end
+
+            end
     end.
 
-simplify_arg(#b_var{}=Arg, Ts) ->
-    Type = get_type(Arg, Ts),
-    case get_literal_from_type(Type) of
-        none -> Arg;
-        #b_literal{}=Lit -> Lit
+simplify_args(Args, Sub, Ts) ->
+    [simplify_arg(Arg, Sub, Ts) || Arg <- Args].
+
+simplify_arg(#b_var{}=Arg0, Sub, Ts) ->
+    case sub_arg(Arg0, Sub) of
+        #b_literal{}=LitArg ->
+            LitArg;
+        #b_var{}=Arg ->
+            Type = get_type(Arg, Ts),
+            case get_literal_from_type(Type) of
+                none -> Arg;
+                #b_literal{}=Lit -> Lit
+            end
     end;
-simplify_arg(Arg, _Ts) -> Arg.
+simplify_arg(#b_remote{mod=Mod,name=Name}=Rem, Sub, Ts) ->
+    Rem#b_remote{mod=simplify_arg(Mod, Sub, Ts),
+                 name=simplify_arg(Name, Sub, Ts)};
+simplify_arg(Arg, _Sub, _Ts) -> Arg.
+
+sub_arg(#b_var{name=V}=Old, Sub) ->
+    case Sub of
+        #{V:=New} -> New;
+        #{} -> Old
+    end.
 
 is_float_op('-', [float]) ->
     true;
@@ -228,67 +386,49 @@ anno_float_arg(float) -> float;
 anno_float_arg(_) -> convert.
 
 opt_terminator(#b_br{bool=#b_literal{}}=Br, _Ts, _Ds) ->
-    Br;
-opt_terminator(#b_br{bool=#b_var{name=V}=Var}=Br, Ts, Ds) ->
-    BoolType = get_type(Var, Ts),
-    case get_literal_from_type(BoolType) of
-        #b_literal{}=BoolLit ->
-            Br#b_br{bool=BoolLit};
-        none ->
-            #{V:=Set} = Ds,
-            case Set of
-                #b_set{op={bif,'=:='},args=[Bool,#b_literal{val=true}]} ->
-                    case t_is_boolean(get_type(Bool, Ts)) of
-                        true ->
-                            %% Bool =:= true   ==>  Bool
-                            simplify_not(Br#b_br{bool=Bool}, Ts, Ds);
-                        false ->
-                            Br
-                    end;
-                #b_set{} ->
-                    simplify_not(Br, Ts, Ds)
-            end
+    beam_ssa:normalize(Br);
+opt_terminator(#b_br{bool=#b_var{name=V}}=Br, Ts, Ds) ->
+    #{V:=Set} = Ds,
+    case Set of
+        #b_set{op={bif,'=:='},args=[Bool,#b_literal{val=true}]} ->
+            case t_is_boolean(get_type(Bool, Ts)) of
+                true ->
+                    %% Bool =:= true   ==>  Bool
+                    simplify_not(Br#b_br{bool=Bool}, Ts, Ds);
+                false ->
+                    Br
+            end;
+        #b_set{} ->
+            simplify_not(Br, Ts, Ds)
     end;
-opt_terminator(#b_switch{arg=#b_literal{val=Val0}=Arg,fail=Fail,list=List},
-               _Ts, _Ds) ->
-    {value,{_,L}} = search(fun({#b_literal{val=Val1},_}) ->
-                                   Val1 =:= Val0
-                           end, List ++ [{Arg,Fail}]),
-    #b_br{bool=#b_literal{val=true},succ=L,fail=L};
-opt_terminator(#b_switch{arg=V}=Sw0, Ts, Ds) ->
-    case get_literal_from_type(Ts) of
-        #b_literal{}=Lit ->
-            Sw = Sw0#b_switch{arg=Lit},
-            opt_terminator(Sw, Ts, Ds);
-        none ->
-            case get_type(V, Ts) of
-                #t_integer{elements={_,_}=Range} ->
-                    simplify_switch_int(Sw0, Range);
-                Type ->
-                    case t_is_boolean(Type) of
-                        true ->
-                            case simplify_switch_bool(Sw0, Ts, Ds) of
-                                #b_br{}=Br ->
-                                    opt_terminator(Br, Ts, Ds);
-                                Sw ->
-                                    Sw
-                            end;
-                        false ->
-                            Sw0
-                    end
+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),
+    case Type of
+        #t_integer{elements={_,_}=Range} ->
+            simplify_switch_int(Sw0, Range);
+        _ ->
+            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;
+                false ->
+                    beam_ssa:normalize(Sw0)
             end
     end;
-opt_terminator(#b_ret{}=Ret, _Ts, _Ds) ->
-    Ret.
+opt_terminator(#b_ret{}=Ret, _Ts, _Ds) -> Ret.
 
-update_successors(#b_br{bool=#b_literal{val=false},fail=S}, Ts, D) ->
-    update_successor(S, Ts, D);
 update_successors(#b_br{bool=#b_literal{val=true},succ=S}, Ts, D) ->
     update_successor(S, Ts, D);
-update_successors(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}, Ts, D0) ->
-    D = update_successor(Fail, Ts#{V:=t_atom(false)}, D0),
-    SuccTs = infer_types(V, Ts, D0),
-    update_successor(Succ, SuccTs#{V:=t_atom(true)}, D);
+update_successors(#b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail}, Ts, D0) ->
+    D = update_successor_bool(Bool, false, Fail, Ts, D0),
+    SuccTs = infer_types(Bool, Ts, D0),
+    update_successor_bool(Bool, true, Succ, SuccTs, D);
 update_successors(#b_switch{arg=#b_var{name=V},fail=Fail,list=List}, Ts, D0) ->
     D = update_successor(Fail, Ts, D0),
     foldl(fun({Val,S}, A) ->
@@ -297,6 +437,16 @@ update_successors(#b_switch{arg=#b_var{name=V},fail=Fail,list=List}, Ts, D0) ->
           end, D, List);
 update_successors(#b_ret{}, _Ts, D) -> D.
 
+update_successor_bool(#b_var{name=V}=Var, BoolValue, S, Ts, D) ->
+    case t_is_boolean(get_type(Var, Ts)) of
+        true ->
+            update_successor(S, Ts#{V:=t_atom(BoolValue)}, D);
+        false ->
+            %% The `br` terminator is preceeded by an instruction that
+            %% does not produce a boolean value, such a `new_try_tag`.
+            update_successor(S, Ts, D)
+    end.
+
 update_successor(S, Ts0, #d{ls=Ls}=D) ->
     case Ls of
         #{S:=Ts1} ->
@@ -313,41 +463,8 @@ update_types(#b_set{op=Op,dst=#b_var{name=Dst},args=Args}, Ts, Ds) ->
 type(phi, Args, Ts, _Ds) ->
     Types = [get_type(A, Ts) || {A,_} <- Args],
     join(Types);
-type({bif,'=:='}, [Same,Same], _Ts, _Ds) ->
-    t_atom(true);
-type({bif,'=:='}, [_,_]=Args, Ts, _Ds) ->
-    case get_literals(Args, Ts) of
-        [#b_literal{val=Lit1},#b_literal{val=Lit2}] ->
-            t_atom(Lit1 =:= Lit2);
-        [_,_] ->
-            case meet(get_types(Args, Ts)) of
-                none -> t_atom(false);
-                _ -> t_boolean()
-            end
-    end;
-type({bif,tuple_size}, [Src], Ts, _Ds) ->
-    case t_tuple_size(get_type(Src, Ts)) of
-        {exact,Size} ->
-            t_integer(Size);
-        _ ->
-            t_integer()
-    end;
 type({bif,'band'}, Args, Ts, _Ds) ->
     band_type(Args, Ts);
-type({bif,Bif}, [Src]=Args, Ts, _Ds) ->
-    case get_type(Src, Ts) of
-        any ->
-            bif_type(Bif, Args);
-        Type ->
-            case will_succeed(Bif, Type) of
-                yes ->
-                    t_atom(true);
-                no ->
-                    t_atom(false);
-                maybe ->
-                    bif_type(Bif, Args)
-            end
-    end;
 type({bif,Bif}, Args, Ts, _Ds) ->
     case bif_type(Bif, Args) of
         number ->
@@ -399,42 +516,12 @@ type(call, [#b_remote{mod=#b_literal{val=Mod},
                 false -> any
             end
     end;
-type(get_tuple_element, [Tuple,#b_literal{val=0}], Ts, _Ds) ->
-    case get_type(Tuple, Ts) of
-        #t_tuple{elements=[First]} ->
-            get_type(#b_literal{val=First}, Ts);
-        #t_tuple{} ->
-            any
-    end;
-type(is_nonempty_list, [Src], Ts, _Ds) ->
-    case get_type(Src, Ts) of
-        any ->
-            t_boolean();
-        list ->
-            t_boolean();
-        cons ->
-            t_atom(true);
-        _ ->
-            t_atom(false)
-    end;
-type(is_tagged_tuple, [Src,#b_literal{val=Size},#b_literal{val=Tag}], Ts, _Ds) ->
-    case get_type(Src, Ts) of
-        #t_tuple{exact=true,size=Size,elements=[Tag]} ->
-            t_atom(true);
-        #t_tuple{exact=true,size=ActualSize,elements=[]} ->
-            if
-                Size =/= ActualSize ->
-                    t_atom(false);
-                true ->
-                    t_boolean()
-            end;
-        #t_tuple{exact=false} ->
-            t_boolean();
-        any ->
-            t_boolean();
-        _ ->
-            t_atom(false)
-    end;
+type(is_nonempty_list, [_], _Ts, _Ds) ->
+    t_boolean();
+type(is_tagged_tuple, [_,#b_literal{},#b_literal{}], _Ts, _Ds) ->
+    t_boolean();
+type(put_map, _Args, _Ts, _Ds) ->
+    map;
 type(put_list, _Args, _Ts, _Ds) ->
     cons;
 type(put_tuple, Args, _Ts, _Ds) ->
@@ -449,6 +536,11 @@ type(succeeded, [#b_var{name=Src}], Ts, Ds) ->
         #b_set{op={bif,Bif},args=BifArgs} ->
             Types = get_types(BifArgs, Ts),
             case {Bif,Types} of
+                {BoolOp,[T1,T2]} when BoolOp =:= 'and'; BoolOp =:= 'or' ->
+                    case t_is_boolean(T1) andalso t_is_boolean(T2) of
+                        true -> t_atom(true);
+                        false -> t_boolean()
+                    end;
                 {byte_size,[{binary,_}]} ->
                     t_atom(true);
                 {bit_size,[{binary,_}]} ->
@@ -493,7 +585,6 @@ arith_op_type(Args, Ts) ->
              (number, #t_integer{}) -> number;
              (number, float) -> float;
              (any, _) -> number;
-             (_, any) -> number;
              (Same, Same) -> Same;
              (_, _) -> none
           end, unknown, Types).
@@ -554,7 +645,6 @@ will_succeed(is_list, Type) ->
     case Type of
         list -> yes;
         cons -> yes;
-        nil -> yes;
         _ -> no
     end;
 will_succeed(is_map, Type) ->
@@ -577,8 +667,6 @@ will_succeed(is_tuple, Type) ->
 will_succeed(_, _) -> maybe.
 
 
-band_type([#b_literal{val=Int},Other], Ts) when is_integer(Int) ->
-    band_type_1(Int, Other, Ts);
 band_type([Other,#b_literal{val=Int}], Ts) when is_integer(Int) ->
     band_type_1(Int, Other, Ts);
 band_type([_,_], _) -> t_integer().
@@ -662,25 +750,22 @@ simplify_switch_bool(#b_switch{arg=B,list=List0}=Sw, Ts, Ds) ->
             Sw
     end.
 
-simplify_not(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}=Br, Ts, Ds) ->
+simplify_not(#b_br{bool=#b_var{name=V},succ=Succ,fail=Fail}=Br0, Ts, Ds) ->
     case Ds of
         #{V:=#b_set{op={bif,'not'},args=[Bool]}} ->
             case t_is_boolean(get_type(Bool, Ts)) of
                 true ->
-                    Br#b_br{bool=Bool,succ=Fail,fail=Succ};
+                    Br = Br0#b_br{bool=Bool,succ=Fail,fail=Succ},
+                    beam_ssa:normalize(Br);
                 false ->
-                    Br
+                    Br0
             end;
         #{} ->
-            Br
+            Br0
     end.
 
-get_literals(Values, Ts) ->
-    [get_literal_from_type(get_type(Val, Ts)) || Val <- Values].
-
 get_types(Values, Ts) ->
     [get_type(Val, Ts) || Val <- Values].
-
 -spec get_type(beam_ssa:value(), type_db()) -> type().
 
 get_type(#b_var{name=V}, Ts) ->
@@ -709,7 +794,7 @@ get_type(#b_literal{val=Val}, _Ts) ->
             any
     end.
 
-infer_types(V, Ts, #d{ds=Ds}) ->
+infer_types(#b_var{name=V}, Ts, #d{ds=Ds}) ->
     #{V:=#b_set{op=Op,args=Args}} = Ds,
     Types = infer_type(Op, Args, Ds),
     meet_types(Types, Ts).
@@ -755,7 +840,6 @@ infer_type(_Op, _Args, _Ds) ->
 %%  Note that that the following BIFs are handle elsewhere:
 %%
 %%     band/2
-%%     tuple_size/1
 
 bif_type(abs, [_]) -> number;
 bif_type(bit_size, [_]) -> t_integer();
@@ -766,9 +850,12 @@ bif_type(floor, [_]) -> t_integer();
 bif_type(is_map_key, [_,_]) -> t_boolean();
 bif_type(length, [_]) -> t_integer();
 bif_type(map_size, [_]) -> t_integer();
+bif_type(node, []) -> #t_atom{};
+bif_type(node, [_]) -> #t_atom{};
 bif_type(round, [_]) -> t_integer();
 bif_type(size, [_]) -> t_integer();
 bif_type(trunc, [_]) -> t_integer();
+bif_type(tuple_size, [_]) -> t_integer();
 bif_type('bnot', [_]) -> t_integer();
 bif_type('bor', [_,_]) -> t_integer();
 bif_type('bsl', [_,_]) -> t_integer();
@@ -807,8 +894,12 @@ inferred_bif_type(byte_size, [_]) -> {binary,1};
 inferred_bif_type(ceil, [_]) -> number;
 inferred_bif_type(float, [_]) -> number;
 inferred_bif_type(floor, [_]) -> number;
+inferred_bif_type(hd, [_]) -> cons;
+inferred_bif_type(length, [_]) -> list;
+inferred_bif_type(map_size, [_]) -> map;
 inferred_bif_type(round, [_]) -> number;
 inferred_bif_type(trunc, [_]) -> number;
+inferred_bif_type(tl, [_]) -> cons;
 inferred_bif_type(tuple_size, [_]) -> #t_tuple{};
 inferred_bif_type(_, _) -> any.
 
@@ -1025,13 +1116,9 @@ meet(#t_integer{elements={Min1,Max1}},
      #t_integer{elements={Min2,Max2}}) ->
     #t_integer{elements={max(Min1, Min2),min(Max1, Max2)}};
 meet(#t_integer{}=T, number) -> T;
-meet(float, number) -> float;
-meet(#t_integer{}=T, number) -> T;
-meet(float, number) -> float;
+meet(float=T, number) -> T;
 meet(number, #t_integer{}=T) -> T;
-meet(#t_integer{}=T, number) -> T;
 meet(number, float=T) -> T;
-meet(float=T, number) -> T;
 meet(list, cons) -> cons;
 meet(list, nil) -> nil;
 meet(cons, list) -> cons;
diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index 953aced66e..8d699f2abd 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -598,6 +598,14 @@ valfun_4({bif,is_map_key,{f,Fail},[_Key,Map]=Src,Dst}, Vst0) ->
     Vst = set_type(map, Map, Vst1),
     Type = propagate_fragility(bool, Src, Vst),
     set_type_reg(Type, Dst, Vst);
+valfun_4({bif,Op,{f,Fail},[Cons]=Src,Dst}, Vst0)
+  when Op =:= hd; Op =:= tl ->
+    validate_src(Src, Vst0),
+    Vst1 = branch_state(Fail, Vst0),
+    Vst = set_type(cons, Cons, Vst1),
+    Type0 = bif_type(Op, Src, Vst),
+    Type = propagate_fragility(Type0, Src, Vst),
+    set_type_reg(Type, Dst, Vst);
 valfun_4({bif,Op,{f,Fail},Src,Dst}, Vst0) ->
     validate_src(Src, Vst0),
     Vst = branch_state(Fail, Vst0),
@@ -610,7 +618,13 @@ valfun_4({gc_bif,Op,{f,Fail},Live,Src,Dst}, #vst{current=St0}=Vst0) ->
     St = kill_heap_allocation(St0),
     Vst1 = Vst0#vst{current=St},
     Vst2 = branch_state(Fail, Vst1),
-    Vst = prune_x_regs(Live, Vst2),
+    Vst3 = prune_x_regs(Live, Vst2),
+    Vst = case Op of
+              map_size ->
+                  set_type(map, hd(Src), Vst3);
+              _ ->
+                  Vst3
+          end,
     validate_src(Src, Vst),
     Type0 = bif_type(Op, Src, Vst),
     Type = propagate_fragility(Type0, Src, Vst),
@@ -648,10 +662,12 @@ valfun_4({set_tuple_element,Src,Tuple,I}, Vst) ->
 %% Match instructions.
 valfun_4({select_val,Src,{f,Fail},{list,Choices}}, Vst0) ->
     assert_term(Src, Vst0),
+    assert_choices(Choices),
     Vst = branch_state(Fail, Vst0),
     kill_state(select_val_branches(Src, Choices, Vst));
 valfun_4({select_tuple_arity,Tuple,{f,Fail},{list,Choices}}, Vst) ->
     assert_type(tuple, Tuple, Vst),
+    assert_arities(Choices),
     TupleType = case get_term_type(Tuple, Vst) of
                     {fragile,TupleType0} -> TupleType0;
                     TupleType0 -> TupleType0
@@ -1088,6 +1104,29 @@ prune_x_regs(Live, #vst{current=St0}=Vst)
     St = St0#st{x=gb_trees:from_orddict(Xs),defs=Defs,aliases=Aliases},
     Vst#vst{current=St}.
 
+%% All choices in a select_val list must be integers, floats, or atoms.
+%% All must be of the same type.
+assert_choices([{Tag,_},{f,_}|T]) ->
+    if
+        Tag =:= atom; Tag =:= float; Tag =:= integer ->
+            assert_choices_1(T, Tag);
+        true ->
+            error(bad_select_list)
+    end;
+assert_choices([]) -> ok.
+
+assert_choices_1([{Tag,_},{f,_}|T], Tag) ->
+    assert_choices_1(T, Tag);
+assert_choices_1([_,{f,_}|_], _Tag) ->
+    error(bad_select_list);
+assert_choices_1([], _Tag) -> ok.
+
+assert_arities([Arity,{f,_}|T]) when is_integer(Arity) ->
+    assert_arities(T);
+assert_arities([]) -> ok;
+assert_arities(_) -> error(bad_tuple_arity_list).
+
+
 %%%
 %%% Floating point checking.
 %%%
@@ -1919,6 +1958,12 @@ is_bif_safe(self, 0) -> true;
 is_bif_safe(node, 0) -> true;
 is_bif_safe(_, _) -> false.
 
+arith_type([A], Vst) ->
+    %% Unary '+' or '-'.
+    case get_term_type(A, Vst) of
+	{float,_} -> {float,[]};
+        _ -> number
+    end;
 arith_type([A,B], Vst) ->
     case {get_term_type(A, Vst),get_term_type(B, Vst)} of
 	{{float,_},_} -> {float,[]};
diff --git a/lib/compiler/src/compile.erl b/lib/compiler/src/compile.erl
index 883a5d8a1f..74ad864163 100644
--- a/lib/compiler/src/compile.erl
+++ b/lib/compiler/src/compile.erl
@@ -841,10 +841,6 @@ asm_passes() ->
 	 {iff,dexcept,{listing,"except"}},
 	 {unless,no_bs_opt,{pass,beam_bs}},
 	 {iff,dbs,{listing,"bs"}},
-	 {pass,beam_split},
-	 {iff,dsplit,{listing,"split"}},
-	 {unless,no_dead,{pass,beam_dead}},
-	 {iff,ddead,{listing,"dead"}},
 	 {unless,no_jopt,{pass,beam_jump}},
 	 {iff,djmp,{listing,"jump"}},
 	 {unless,no_peep_opt,{pass,beam_peep}},
@@ -2036,7 +2032,6 @@ pre_load() ->
 	 beam_bs,
 	 beam_bsm,
 	 beam_clean,
-	 beam_dead,
 	 beam_dict,
 	 beam_except,
 	 beam_flatten,
@@ -2046,11 +2041,11 @@ pre_load() ->
 	 beam_peep,
 	 beam_ssa,
 	 beam_ssa_codegen,
+	 beam_ssa_dead,
 	 beam_ssa_opt,
 	 beam_ssa_pre_codegen,
 	 beam_ssa_recv,
 	 beam_ssa_type,
-	 beam_split,
 	 beam_trim,
 	 beam_utils,
 	 beam_validator,
diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src
index 74529f7fef..bb281376ef 100644
--- a/lib/compiler/src/compiler.app.src
+++ b/lib/compiler/src/compiler.app.src
@@ -27,7 +27,6 @@
 	     beam_bs,
 	     beam_bsm,
 	     beam_clean,
-	     beam_dead,
 	     beam_dict,
 	     beam_disasm,
 	     beam_except,
@@ -39,13 +38,13 @@
 	     beam_peep,
              beam_ssa,
              beam_ssa_codegen,
+             beam_ssa_dead,
              beam_ssa_lint,
              beam_ssa_opt,
              beam_ssa_pp,
              beam_ssa_pre_codegen,
              beam_ssa_recv,
              beam_ssa_type,
-	     beam_split,
 	     beam_trim,
 	     beam_utils,
 	     beam_validator,