path: root/lib/compiler/src/beam_ssa_codegen.erl

%%
%% %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%
%%
%% Purpose: Generate BEAM assembly code from the SSA format.

-module(beam_ssa_codegen).

-export([module/2]).
-export([classify_heap_need/2]).    %Called from beam_ssa_pre_codegen.

-export_type([ssa_register/0]).

-include("beam_ssa.hrl").

-import(lists, [foldl/3,keymember/3,keysort/2,map/2,mapfoldl/3,
                reverse/1,reverse/2,sort/1,splitwith/2,takewhile/2]).

-record(cg, {lcount=1 :: beam_label(),          %Label counter
	     functable=#{} :: #{fa()=>beam_label()},
             labels=#{} :: #{ssa_label()=>0|beam_label()},
             used_labels=gb_sets:empty() :: gb_sets:set(ssa_label()),
             regs=#{} :: #{beam_ssa:var_name()=>ssa_register()},
             ultimate_fail=1 :: beam_label(),
             catches=gb_sets:empty() :: gb_sets:set(ssa_label()),
             fc_label=1 :: beam_label()
             }).

-spec module(beam_ssa:b_module(), [compile:option()]) ->
                    {'ok',beam_asm:module_code()}.

module(#b_module{name=Mod,exports=Es,attributes=Attrs,body=Fs}, _Opts) ->
    {Asm,St} = functions(Fs, {atom,Mod}),
    {ok,{Mod,Es,Attrs,Asm,St#cg.lcount}}.

-record(need, {h=0 :: non_neg_integer(),
               f=0 :: non_neg_integer()}).

-record(cg_blk, {anno=#{} :: anno(),
                 is=[] :: [instruction()],
                 last :: terminator()}).

-record(cg_set, {anno=#{} :: anno(),
                 dst :: b_var(),
                 op :: beam_ssa:op(),
                 args :: [beam_ssa:argument() | xreg()]}).

-record(cg_alloc, {anno=#{} :: anno(),
                   stack=none :: 'none' | pos_integer(),
                   words=#need{} :: #need{},
                   live :: 'undefined' | pos_integer(),
                   def_yregs=[] :: [yreg()]
                  }).

-record(cg_br, {bool :: beam_ssa:value(),
                succ :: ssa_label(),
                fail :: ssa_label()
               }).
-record(cg_ret, {arg :: cg_value(),
                 dealloc=none :: 'none' | pos_integer()
                }).
-record(cg_switch, {arg :: cg_value(),
                    fail :: ssa_label(),
                    list :: [sw_list_item()]
                   }).

-type fa() :: {beam_asm:function_name(),arity()}.
-type ssa_label() :: beam_ssa:label().
-type beam_label() :: beam_asm:label().

-type anno() :: beam_ssa:anno().

-type b_var() :: beam_ssa:b_var().
-type b_literal() :: beam_ssa:b_literal().

-type cg_value() :: beam_ssa:value() | xreg().

-type cg_set() :: #cg_set{}.
-type cg_alloc() :: #cg_alloc{}.

-type instruction() :: cg_set() | cg_alloc().

-type cg_br() :: #cg_br{}.
-type cg_ret() :: #cg_ret{}.
-type cg_switch() :: #cg_switch{}.
-type terminator() :: cg_br() | cg_ret() | cg_switch().

-type sw_list_item() :: {b_literal(),ssa_label()}.

-type reg_num() :: beam_asm:reg_num().
-type xreg() :: {'x',reg_num()}.
-type yreg() :: {'y',reg_num()}.

-type ssa_register() :: xreg() | yreg() | {'fr',reg_num()} | {'z',reg_num()}.

functions(Forms, AtomMod) ->
    mapfoldl(fun (F, St) -> function(F, AtomMod, St) end,
             #cg{lcount=1}, Forms).

function(#b_function{anno=Anno,bs=Blocks}, AtomMod, St0) ->
    #{func_info:={_,Name,Arity}} = Anno,
    try
        assert_exception_block(Blocks),            %Assertion.
        Regs = maps:get(registers, Anno),
        St1 = St0#cg{labels=#{},used_labels=gb_sets:empty(),
                     regs=Regs},
        {Fi,St2} = new_label(St1),              %FuncInfo label
        {Entry,St3} = local_func_label(Name, Arity, St2),
        {Ult,St4} = new_label(St3),             %Ultimate failure
        Labels = (St4#cg.labels)#{0=>Entry,?EXCEPTION_BLOCK=>0},
        St5 = St4#cg{labels=Labels,used_labels=gb_sets:singleton(Entry),
                     ultimate_fail=Ult},
        {Body,St} = cg_fun(Blocks, St5#cg{fc_label=Fi}),
        Asm = [{label,Fi},line(Anno),
               {func_info,AtomMod,{atom,Name},Arity}] ++
               add_parameter_annos(Body, Anno) ++
               [{label,Ult},if_end],
        Func = {function,Name,Arity,Entry,Asm},
        {Func,St}
    catch
        Class:Error:Stack ->
            io:fwrite("Function: ~w/~w\n", [Name,Arity]),
            erlang:raise(Class, Error, Stack)
    end.

assert_exception_block(Blocks) ->
    %% Assertion: ?EXCEPTION_BLOCK must be a call erlang:error(badarg).
    case Blocks of
        #{?EXCEPTION_BLOCK:=Blk} ->
            #b_blk{is=[#b_set{op=call,dst=Ret,
                              args=[#b_remote{mod=#b_literal{val=erlang},
                                              name=#b_literal{val=error}},
                                    #b_literal{val=badarg}]}],
                   last=#b_ret{arg=Ret}} = Blk,
            ok;
        #{} ->
            %% ?EXCEPTION_BLOCK has been removed because it was never used.
            ok
    end.

add_parameter_annos([{label, _}=Entry | Body], Anno) ->
    ParamInfo = maps:get(parameter_type_info, Anno, #{}),
    Annos = maps:fold(
        fun(K, V, Acc) when is_map_key(K, ParamInfo) ->
                TypeInfo = maps:get(K, ParamInfo),
                [{'%', {type_info, V, TypeInfo}} | Acc];
           (_K, _V, Acc) ->
                Acc
        end, [], maps:get(registers, Anno)),
    [Entry | sort(Annos)] ++ Body.

cg_fun(Blocks, St0) ->
    Linear0 = linearize(Blocks),
    St = collect_catch_labels(Linear0, St0),
    Linear1 = need_heap(Linear0),
    Linear2 = prefer_xregs(Linear1, St),
    Linear3 = liveness(Linear2, St),
    Linear4 = defined(Linear3, St),
    Linear = opt_allocate(Linear4, St),
    cg_linear(Linear, St).

%% collect_catch_labels(Linear, St) -> St.
%%  Collect all catch labels (labels for blocks that begin
%%  with 'landingpad' instructions) for later use.

collect_catch_labels(Linear, St) ->
    Labels = collect_catch_labels_1(Linear),
    St#cg{catches=gb_sets:from_list(Labels)}.

collect_catch_labels_1([{L,#cg_blk{is=[#cg_set{op=landingpad}|_]}}|Bs]) ->
    [L|collect_catch_labels_1(Bs)];
collect_catch_labels_1([_|Bs]) ->
    collect_catch_labels_1(Bs);
collect_catch_labels_1([]) -> [].

%% need_heap([{BlockLabel,Block]) -> [{BlockLabel,Block}].
%%  Insert need_heap instructions in the instruction list. Try to be smart and
%%  collect them together as much as possible.

need_heap(Bs0) ->
    Bs1 = need_heap_allocs(Bs0, #{}),
    {Bs,#need{h=0,f=0}} = need_heap_blks(reverse(Bs1), #need{}, []),
    Bs.

need_heap_allocs([{L,#cg_blk{is=Is0,last=Terminator}=Blk0}|Bs], Counts0) ->
    Next = next_block(Bs),
    Successors = successors(Terminator),
    Counts = foldl(fun(S, Cnts) ->
                           case Cnts of
                               #{S:=C} -> Cnts#{S:=C+1};
                               #{} when S =:= Next -> Cnts#{S=>1};
                               #{} -> Cnts#{S=>42}
                           end
                   end, Counts0, Successors),
    case Counts of
        #{L:=1} ->
            [{L,Blk0}|need_heap_allocs(Bs, Counts)];
        #{L:=_} ->
            %% This block has multiple predecessors. Force an allocation
            %% in this block so that the predecessors don't need to do
            %% an allocation on behalf of this block.
            Is = case need_heap_never(Is0) of
                     true -> Is0;
                     false -> [#cg_alloc{}|Is0]
                 end,
            Blk = Blk0#cg_blk{is=Is},
            [{L,Blk}|need_heap_allocs(Bs, Counts)];
        #{} ->
            [{L,Blk0}|need_heap_allocs(Bs, Counts)]
    end;
need_heap_allocs([], _) -> [].

need_heap_never([#cg_alloc{}|_]) -> true;
need_heap_never([#cg_set{op=recv_next}|_]) -> true;
need_heap_never([#cg_set{op=wait}|_]) -> true;
need_heap_never(_) -> false.

need_heap_blks([{L,#cg_blk{is=Is0}=Blk0}|Bs], H0, Acc) ->
    {Is1,H1} = need_heap_is(reverse(Is0), H0, []),
    {Ns,H} = need_heap_terminator(Bs, L, H1),
    Is = Ns ++ Is1,
    Blk = Blk0#cg_blk{is=Is},
    need_heap_blks(Bs, H, [{L,Blk}|Acc]);
need_heap_blks([], H, Acc) ->
    {Acc,H}.

need_heap_is([#cg_alloc{words=Words}=Alloc0|Is], N, Acc) ->
    Alloc = Alloc0#cg_alloc{words=add_heap_words(N, Words)},
    need_heap_is(Is, #need{}, [Alloc|Acc]);
need_heap_is([#cg_set{anno=Anno,op=bs_init}=I0|Is], N, Acc) ->
    Alloc = case need_heap_need(N) of
                [#cg_alloc{words=Need}] -> alloc(Need);
                [] -> 0
            end,
    I = I0#cg_set{anno=Anno#{alloc=>Alloc}},
    need_heap_is(Is, #need{}, [I|Acc]);
need_heap_is([#cg_set{op=Op,args=Args}=I|Is], N, Acc) ->
    case classify_heap_need(Op, Args) of
        {put,Words} ->
            %% Pass through adding to needed heap.
            need_heap_is(Is, add_heap_words(N, Words), [I|Acc]);
        put_float ->
            need_heap_is(Is, add_heap_float(N), [I|Acc]);
        neutral ->
            need_heap_is(Is, N, [I|Acc]);
        gc ->
            need_heap_is(Is, #need{}, [I]++need_heap_need(N)++Acc)
    end;
need_heap_is([], N, Acc) ->
    {Acc,N}.

need_heap_terminator([{_,#cg_blk{last=#cg_br{succ=L,fail=L}}}|_], L, N) ->
    %% Fallthrough.
    {[],N};
need_heap_terminator([{_,#cg_blk{is=Is,last=#cg_br{succ=L}}}|_], L, N) ->
    case need_heap_need(N) of
        [] ->
            {[],#need{}};
        [_|_]=Alloc ->
            %% If the preceding instructions are a binary construction,
            %% hoist the allocation and incorporate into the bs_init
            %% instruction.
            case reverse(Is) of
                [#cg_set{op=succeeded},#cg_set{op=bs_init}|_] ->
                    {[],N};
                [#cg_set{op=bs_put}|_] ->
                    {[],N};
                _ ->
                    %% Not binary construction. Must emit an allocation
                    %% instruction in this block.
                    {Alloc,#need{}}
            end
    end;
need_heap_terminator([{_,#cg_blk{}}|_], _, N) ->
    {need_heap_need(N),#need{}};
need_heap_terminator([], _, H) ->
    {need_heap_need(H),#need{}}.

need_heap_need(#need{h=0,f=0}) -> [];
need_heap_need(#need{}=N) -> [#cg_alloc{words=N}].

add_heap_words(#need{h=H1,f=F1}, #need{h=H2,f=F2}) ->
    #need{h=H1+H2,f=F1+F2};
add_heap_words(#need{h=Heap}=N, Words) when is_integer(Words) ->
    N#need{h=Heap+Words}.

add_heap_float(#need{f=F}=N) ->
    N#need{f=F+1}.

%% classify_heap_need(Operation, Arguments) ->
%%        gc | neutral | {put,Words} | put_float.
%%  Classify the heap need for this instruction. The return
%%  values have the following meaning.
%%
%%  {put,Words} means that the instruction will use Words words to build
%%  something on the heap.
%%
%%  'put_float' means that the instruction will build one floating point
%%  number on the heap.
%%
%%  'gc' means that that the instruction can potentially do a GC or throw an
%%  exception. That means that an allocation instruction for any building
%%  must be placed after this instruction.
%%
%%  'neutral' means that the instruction does nothing to disturb the heap.

-spec classify_heap_need(beam_ssa:op(), [beam_ssa:value()]) ->
                                'gc' | 'neutral' |
                                {'put',non_neg_integer()} | 'put_float'.

classify_heap_need(put_list, _) ->
    {put,2};
classify_heap_need(put_tuple_arity, [#b_literal{val=Words}]) ->
    {put,Words+1};
classify_heap_need(put_tuple, Elements) ->
    {put,length(Elements)+1};
classify_heap_need({bif,Name}, Args) ->
    case is_gc_bif(Name, Args) of
        false -> neutral;
        true -> gc
    end;
classify_heap_need({float,Op}, _Args) ->
    case Op of
        get -> put_float;
        _ -> neutral
    end;
classify_heap_need(Name, _Args) ->
    classify_heap_need(Name).

%% classify_heap_need(Operation) -> gc | neutral.
%%  Return either 'gc' or 'neutral'.
%%
%%  'gc' means that that the instruction can potentially do a GC or throw an
%%  exception. That means that an allocation instruction for any building
%%  must be placed after this instruction.
%%
%%  'neutral' means that the instruction does nothing to disturb the heap.
%%
%%  Note: Only handle operations in this function that are not handled
%%  by classify_heap_need/2.

classify_heap_need(bs_add) -> gc;
classify_heap_need(bs_get) -> gc;
classify_heap_need(bs_get_tail) -> gc;
classify_heap_need(bs_init) -> gc;
classify_heap_need(bs_init_writable) -> gc;
classify_heap_need(bs_match_string) -> gc;
classify_heap_need(bs_put) -> neutral;
classify_heap_need(bs_restore) -> neutral;
classify_heap_need(bs_save) -> neutral;
classify_heap_need(bs_get_position) -> gc;
classify_heap_need(bs_set_position) -> neutral;
classify_heap_need(bs_skip) -> gc;
classify_heap_need(bs_start_match) -> neutral;
classify_heap_need(bs_test_tail) -> neutral;
classify_heap_need(bs_utf16_size) -> neutral;
classify_heap_need(bs_utf8_size) -> neutral;
classify_heap_need(build_stacktrace) -> gc;
classify_heap_need(call) -> gc;
classify_heap_need(catch_end) -> gc;
classify_heap_need(copy) -> neutral;
classify_heap_need(extract) -> gc;
classify_heap_need(get_hd) -> neutral;
classify_heap_need(get_map_element) -> neutral;
classify_heap_need(get_tl) -> neutral;
classify_heap_need(get_tuple_element) -> neutral;
classify_heap_need(has_map_field) -> neutral;
classify_heap_need(is_nonempty_list) -> neutral;
classify_heap_need(is_tagged_tuple) -> neutral;
classify_heap_need(kill_try_tag) -> gc;
classify_heap_need(landingpad) -> gc;
classify_heap_need(make_fun) -> gc;
classify_heap_need(match_fail) -> gc;
classify_heap_need(new_try_tag) -> gc;
classify_heap_need(peek_message) -> gc;
classify_heap_need(put_map) -> gc;
classify_heap_need(put_tuple_elements) -> neutral;
classify_heap_need(raw_raise) -> gc;
classify_heap_need(recv_next) -> gc;
classify_heap_need(remove_message) -> neutral;
classify_heap_need(resume) -> gc;
classify_heap_need(set_tuple_element) -> gc;
classify_heap_need(succeeded) -> neutral;
classify_heap_need(timeout) -> gc;
classify_heap_need(wait) -> gc;
classify_heap_need(wait_timeout) -> gc.

%%%
%%% Because beam_ssa_pre_codegen has inserted 'copy' instructions to copy
%%% variables that must be saved on the stack, a value can for some time
%%% be in both an X register and a Y register.
%%%
%%% Here we will keep track of variables that have the same value and
%%% rewrite instructions to use the variable that refers to the X
%%% register instead of the Y register. That could improve performance,
%%% since the BEAM interpreter have more optimized instructions
%%% operating on X registers than on Y registers.
%%%
%%% 'call' and 'make_fun' are handled somewhat specially. If a value
%%% already is in the correct X register, the X register will always
%%% be used instead of the Y register. However, if there are one or more
%%% values in the wrong X registers, the X registers variables will be
%%% used only if that does not cause more 'move' instructions to be
%%% be emitted than if the Y register variables were used.
%%%
%%% Here are some examples. The first example shows how a 'move' from
%%% an Y register is eliminated:
%%%
%%%     move x0 y1
%%%     move y1 x0   %%Will be eliminated.
%%%
%%%     call f/1
%%%
%%% Here is an example when x0 and x1 must be swapped to load the argument
%%% registers. Here the 'call' instruction will use the Y registers to
%%% avoid introducing an extra 'move' insruction:
%%%
%%%     move x0 y0
%%%     move x1 y1
%%%
%%%     move y0 x1
%%%     move y1 x0
%%%
%%%     call f/2
%%%
%%% Using the X register to load the argument registers would need
%%% an extra 'move' instruction like this:
%%%
%%%     move x0 y0
%%%     move x1 y1
%%%
%%%     move x1 x2
%%%     move x0 x1
%%%     move x2 x0
%%%
%%%     call f/2
%%%

prefer_xregs(Linear, St) ->
    prefer_xregs(Linear, St, #{0=>#{}}).

prefer_xregs([{L,#cg_blk{is=Is0,last=Last0}=Blk0}|Bs], St, Map0) ->
    Copies0 = maps:get(L, Map0),
    {Is,Copies} = prefer_xregs_is(Is0, St, Copies0, []),
    Last = prefer_xregs_terminator(Last0, Copies, St),
    Blk = Blk0#cg_blk{is=Is,last=Last},
    Successors = successors(Last),
    Map = prefer_xregs_successors(Successors, Copies, Map0),
    [{L,Blk}|prefer_xregs(Bs, St, Map)];
prefer_xregs([], _St, _Map) -> [].

prefer_xregs_successors([L|Ls], Copies0, Map0) ->
    case Map0 of
        #{L:=Copies1} ->
            Copies = merge_copies(Copies0, Copies1),
            Map = Map0#{L:=Copies},
            prefer_xregs_successors(Ls, Copies0, Map);
        #{} ->
            Map = Map0#{L=>Copies0},
            prefer_xregs_successors(Ls, Copies0, Map)
    end;
prefer_xregs_successors([], _, Map) -> Map.

prefer_xregs_is([#cg_alloc{}=I|Is], St, Copies0, Acc) ->
    Copies = case I of
                 #cg_alloc{stack=none,words=#need{h=0,f=0}} ->
                     Copies0;
                 #cg_alloc{} ->
                     #{}
             end,
    prefer_xregs_is(Is, St, Copies, [I|Acc]);
prefer_xregs_is([#cg_set{op=copy,dst=Dst,args=[Src]}=I|Is], St, Copies0, Acc) ->
    Copies1 = prefer_xregs_prune(I, Copies0, St),
    Copies = case beam_args([Src,Dst], St) of
                 [Same,Same] -> Copies1;
                 [_,_] -> Copies1#{Dst=>Src}
             end,
    prefer_xregs_is(Is, St, Copies, [I|Acc]);
prefer_xregs_is([#cg_set{op=call,dst=Dst}=I0|Is], St, Copies, Acc) ->
    I = prefer_xregs_call(I0, Copies, St),
    prefer_xregs_is(Is, St, #{Dst=>{x,0}}, [I|Acc]);
prefer_xregs_is([#cg_set{op=make_fun,dst=Dst}=I0|Is], St, Copies, Acc) ->
    I = prefer_xregs_call(I0, Copies, St),
    prefer_xregs_is(Is, St, #{Dst=>{x,0}}, [I|Acc]);
prefer_xregs_is([#cg_set{op=set_tuple_element}=I|Is], St, Copies, Acc) ->
    %% FIXME: HiPE translates the following code segment incorrectly:
    %%     {call_ext,3,{extfunc,erlang,setelement,3}}.
    %%     {move,{x,0},{y,3}}.
    %%     {set_tuple_element,{y,1},{y,3},1}.
    %% Therefore, skip the translation of the arguments for set_tuple_element.
    prefer_xregs_is(Is, St, Copies, [I|Acc]);
prefer_xregs_is([#cg_set{args=Args0}=I0|Is], St, Copies0, Acc) ->
    Args = [do_prefer_xreg(A, Copies0, St) || A <- Args0],
    I = I0#cg_set{args=Args},
    Copies = prefer_xregs_prune(I, Copies0, St),
    prefer_xregs_is(Is, St, Copies, [I|Acc]);
prefer_xregs_is([], _St, Copies, Acc) ->
    {reverse(Acc),Copies}.

prefer_xregs_terminator(#cg_br{bool=Arg0}=I, Copies, St) ->
    Arg = do_prefer_xreg(Arg0, Copies, St),
    I#cg_br{bool=Arg};
prefer_xregs_terminator(#cg_ret{arg=Arg0}=I, Copies, St) ->
    Arg = do_prefer_xreg(Arg0, Copies, St),
    I#cg_ret{arg=Arg};
prefer_xregs_terminator(#cg_switch{arg=Arg0}=I, Copies, St) ->
    Arg = do_prefer_xreg(Arg0, Copies, St),
    I#cg_switch{arg=Arg}.

prefer_xregs_prune(#cg_set{anno=#{clobbers:=true}}, _, _) ->
    #{};
prefer_xregs_prune(#cg_set{dst=Dst}, Copies, St) ->
    DstReg = beam_arg(Dst, St),
    F = fun(_, Alias) ->
                beam_arg(Alias, St) =/= DstReg
        end,
    maps:filter(F, Copies).

%% prefer_xregs_call(Instruction, Copies, St) -> Instruction.
%%  Given a 'call' or 'make_fun' instruction, minimize the number
%%  of 'move' instructions to set up the argument registers.
%%  Prefer using X registers over Y registers, unless that will
%%  result in more 'move' instructions.

prefer_xregs_call(#cg_set{args=[_]}=I, _Copies, _St) ->
    I;
prefer_xregs_call(#cg_set{args=[F|Args0]}=I, Copies, St) ->
    case Args0 of
        [A0] ->
            %% Only one argument. Always prefer the X register
            %% if available.
            A = do_prefer_xreg(A0, Copies, St),
            I#cg_set{args=[F,A]};
        [_|_] ->
            %% Two or more arguments. Try rewriting arguments in
            %% two ways and see which way produces the least
            %% number of 'move' instructions.
            Args1 = prefer_xregs_call_1(Args0, Copies, 0, St),
            Args2 = [do_prefer_xreg(A, Copies, St) || A <- Args0],
            case {count_moves(Args1, St),count_moves(Args2, St)} of
                {N1,N2} when N1 < N2 ->
                    %% There will be fewer 'move' instructions if
                    %% we keep using Y registers.
                    I#cg_set{args=[F|Args1]};
                {_,_} ->
                    %% Always use the values in X registers.
                    I#cg_set{args=[F|Args2]}
            end
    end.

count_moves(Args, St) ->
    length(setup_args(beam_args(Args, St))).

prefer_xregs_call_1([#b_var{}=A|As], Copies, X, St) ->
    case {beam_arg(A, St),Copies} of
        {{y,_},#{A:=Other}} ->
            case beam_arg(Other, St) of
                {x,X} ->
                    %% This value is already in the correct X register.
                    %% It is always benefical to use the X register variable.
                    [Other|prefer_xregs_call_1(As, Copies, X+1, St)];
                _ ->
                    %% This value is another X register. Keep using
                    %% the Y register variable.
                    [A|prefer_xregs_call_1(As, Copies, X+1, St)]
            end;
        {_,_} ->
            %% The value is not available in an X register.
            [A|prefer_xregs_call_1(As, Copies, X+1, St)]
    end;
prefer_xregs_call_1([A|As], Copies, X, St) ->
    [A|prefer_xregs_call_1(As, Copies, X+1, St)];
prefer_xregs_call_1([], _, _, _) -> [].

do_prefer_xreg(#b_var{}=A, Copies, St) ->
    case {beam_arg(A, St),Copies} of
        {{y,_},#{A:=Copy}} ->
            Copy;
        {_,_} ->
            A
    end;
do_prefer_xreg(A, _, _) -> A.

merge_copies(Copies0, Copies1) when map_size(Copies0) =< map_size(Copies1) ->
    maps:filter(fun(K, V) ->
                        case Copies1 of
                            #{K:=V} -> true;
                            #{} -> false
                        end
                end, Copies0);
merge_copies(Copies0, Copies1) ->
    merge_copies(Copies1, Copies0).


%%%
%%% Add annotations for the number of live registers.
%%%

liveness(Linear, #cg{regs=Regs}) ->
    liveness(reverse(Linear), #{}, Regs, []).

liveness([{L,#cg_blk{is=Is0,last=Last0}=Blk0}|Bs], LiveMap0, Regs, Acc) ->
    Successors = liveness_successors(Last0),
    Live0 = ordsets:union([liveness_get(S, LiveMap0) || S <- Successors]),
    Live1 = liveness_terminator(Last0, Live0),
    {Is,Live} = liveness_is(reverse(Is0), Regs, Live1, []),
    LiveMap = LiveMap0#{L=>Live},
    Blk = Blk0#cg_blk{is=Is},
    liveness(Bs, LiveMap, Regs, [{L,Blk}|Acc]);
liveness([], _LiveMap, _Regs, Acc) -> Acc.

liveness_get(S, LiveMap) ->
    case LiveMap of
        #{S:=Live} -> Live;
        #{} -> []
    end.

liveness_successors(Terminator) ->
    successors(Terminator) -- [?EXCEPTION_BLOCK].

liveness_is([#cg_alloc{}=I0|Is], Regs, Live, Acc) ->
    I = I0#cg_alloc{live=num_live(Live, Regs)},
    liveness_is(Is, Regs, Live, [I|Acc]);
liveness_is([#cg_set{dst=Dst,args=Args}=I0|Is], Regs, Live0, Acc) ->
    Live1 = liveness_clobber(I0, Live0, Regs),
    I1 = liveness_yregs_anno(I0, Live1, Regs),
    Live2 = liveness_args(Args, Live1),
    Live = ordsets:del_element(Dst, Live2),
    I = liveness_anno(I1, Live, Regs),
    liveness_is(Is, Regs, Live, [I|Acc]);
liveness_is([], _, Live, Acc) ->
    {Acc,Live}.

liveness_terminator(#cg_br{bool=Arg}, Live) ->
    liveness_terminator_1(Arg, Live);
liveness_terminator(#cg_switch{arg=Arg}, Live) ->
    liveness_terminator_1(Arg, Live);
liveness_terminator(#cg_ret{arg=Arg}, Live) ->
    liveness_terminator_1(Arg, Live).

liveness_terminator_1(#b_var{}=V, Live) ->
    ordsets:add_element(V, Live);
liveness_terminator_1(#b_literal{}, Live) ->
    Live;
liveness_terminator_1(Reg, Live) ->
    _ = verify_beam_register(Reg),
    ordsets:add_element(Reg, Live).

liveness_args([#b_var{}=V|As], Live) ->
    liveness_args(As, ordsets:add_element(V, Live));
liveness_args([#b_remote{mod=Mod,name=Name}|As], Live) ->
    liveness_args([Mod,Name|As], Live);
liveness_args([A|As], Live) ->
    case is_beam_register(A) of
        true ->
            liveness_args(As, ordsets:add_element(A, Live));
        false ->
            liveness_args(As, Live)
    end;
liveness_args([], Live) -> Live.

liveness_anno(#cg_set{op=Op}=I, Live, Regs) ->
    case need_live_anno(Op) of
        true ->
            NumLive = num_live(Live, Regs),
            Anno = (I#cg_set.anno)#{live=>NumLive},
            I#cg_set{anno=Anno};
        false ->
            I
    end.

liveness_yregs_anno(#cg_set{op=Op,dst=Dst}=I, Live0, Regs) ->
    case need_live_anno(Op) of
        true ->
            Live = ordsets:del_element(Dst, Live0),
            LiveYregs = [V || V <- Live, is_yreg(V, Regs)],
            Anno = (I#cg_set.anno)#{live_yregs=>LiveYregs},
            I#cg_set{anno=Anno};
        false ->
            I
    end.

liveness_clobber(#cg_set{anno=Anno}, Live, Regs) ->
    case Anno of
        #{clobbers:=true} ->
            [R || R <- Live, is_yreg(R, Regs)];
        _ ->
            Live
    end.

is_yreg(R, Regs) ->
    case Regs of
        #{R:={y,_}} -> true;
        #{} -> false
    end.

num_live(Live, Regs) ->
    Rs = ordsets:from_list([get_register(V, Regs) || V <- Live]),
    num_live_1(Rs, 0).

num_live_1([{x,X}|T], X) ->
    num_live_1(T, X+1);
num_live_1([{x,_}|_]=T, X) ->
    %% error({hole,{x,X},expected,Next});
    num_live_1(T, X+1);
num_live_1([{y,_}|_], X) ->
    X;
num_live_1([{z,_}|_], X) ->
    X;
num_live_1([{fr,_}|T], X) ->
    num_live_1(T, X);
num_live_1([], X) ->
    X.

get_live(#cg_set{anno=#{live:=Live}}) ->
    Live.

%% need_live_anno(Operation) -> true|false.
%%  Return 'true' if the instruction needs a 'live' annotation with
%%  the number live X registers, or 'false' otherwise.

need_live_anno(Op) ->
    case Op of
        {bif,_} -> true;
        bs_get -> true;
        bs_init -> true;
        bs_get_position -> true;
        bs_get_tail -> true;
        bs_start_match -> true;
        bs_skip -> true;
        call -> true;
        put_map -> true;
        _ -> false
    end.

%%%
%%% Add the following annotations for Y registers:
%%%
%%%   def_yregs   An ordset with variables that refer to live Y registers.
%%%               That is, Y registers that that have been killed
%%%               are not included. This annotation is added to all
%%%               instructions that require Y registers to be initialized.
%%%
%%%   kill_yregs  This annotation is added to call instructions. It is
%%%               an ordset containing variables referring to Y registers
%%%               that will no longer be used after the call instruction.
%%%

defined(Linear, #cg{regs=Regs}) ->
    def(Linear, #{}, Regs).

def([{L,#cg_blk{is=Is0,last=Last}=Blk0}|Bs], DefMap0, Regs) ->
    Def0 = def_get(L, DefMap0),
    {Is,Def,MaybeDef} = def_is(Is0, Regs, Def0, []),
    DefMap = def_successors(Last, Def, MaybeDef, DefMap0),
    Blk = Blk0#cg_blk{is=Is},
    [{L,Blk}|def(Bs, DefMap, Regs)];
def([], _, _) -> [].

def_get(L, DefMap) ->
    case DefMap of
        #{L:=Def} -> Def;
        #{} -> []
    end.

def_is([#cg_alloc{anno=Anno0}=I0|Is], Regs, Def, Acc) ->
    I = I0#cg_alloc{anno=Anno0#{def_yregs=>Def}},
    def_is(Is, Regs, Def, [I|Acc]);
def_is([#cg_set{op=succeeded,args=[Var]}=I], Regs, Def, Acc) ->
    %% Var will only be defined on the success branch of the `br`
    %% for this block.
    MaybeDef = def_add_yreg(Var, [], Regs),
    {reverse(Acc, [I]),Def,MaybeDef};
def_is([#cg_set{op=kill_try_tag,args=[#b_var{}=Tag]}=I|Is], Regs, Def0, Acc) ->
    Def = ordsets:del_element(Tag, Def0),
    def_is(Is, Regs, Def, [I|Acc]);
def_is([#cg_set{op=catch_end,args=[#b_var{}=Tag|_]}=I|Is], Regs, Def0, Acc) ->
    Def = ordsets:del_element(Tag, Def0),
    def_is(Is, Regs, Def, [I|Acc]);
def_is([#cg_set{anno=Anno0,op=call,dst=Dst}=I0|Is],
       Regs, Def0, Acc) ->
    #{live_yregs:=LiveYregVars} = Anno0,
    LiveRegs = gb_sets:from_list([maps:get(V, Regs) || V <- LiveYregVars]),
    Kill0 = ordsets:subtract(Def0, LiveYregVars),

    %% Kill0 is the set of variables that have just died. However, the registers
    %% used for killed variables may have been reused, so we must check that the
    %% registers to be killed are not used by other variables.
    Kill = [K || K <- Kill0, not gb_sets:is_element(maps:get(K, Regs), LiveRegs)],
    Anno = Anno0#{def_yregs=>Def0,kill_yregs=>Kill},
    I = I0#cg_set{anno=Anno},
    Def1 = ordsets:subtract(Def0, Kill),
    Def = def_add_yreg(Dst, Def1, Regs),
    def_is(Is, Regs, Def, [I|Acc]);
def_is([#cg_set{anno=Anno0,op={bif,Bif},dst=Dst,args=Args}=I0|Is],
       Regs, Def0, Acc) ->
    Arity = length(Args),
    I = case is_gc_bif(Bif, Args) orelse not erl_bifs:is_safe(erlang, Bif, Arity) of
            true ->
                I0#cg_set{anno=Anno0#{def_yregs=>Def0}};
            false ->
                I0
        end,
    Def = def_add_yreg(Dst, Def0, Regs),
    def_is(Is, Regs, Def, [I|Acc]);
def_is([#cg_set{anno=Anno0,dst=Dst}=I0|Is], Regs, Def0, Acc) ->
    I = case need_y_init(I0) of
            true ->
                I0#cg_set{anno=Anno0#{def_yregs=>Def0}};
            false ->
                I0
        end,
    Def = def_add_yreg(Dst, Def0, Regs),
    def_is(Is, Regs, Def, [I|Acc]);
def_is([], _, Def, Acc) ->
    {reverse(Acc),Def,[]}.

def_add_yreg(Dst, Def, Regs) ->
    case is_yreg(Dst, Regs) of
        true -> ordsets:add_element(Dst, Def);
        false -> Def
    end.

def_successors(#cg_br{bool=#b_var{},succ=Succ,fail=Fail}, Def, MaybeDef, DefMap0) ->
    DefMap = def_successors([Fail], ordsets:subtract(Def, MaybeDef), DefMap0),
    def_successors([Succ], Def, DefMap);
def_successors(Last, Def, [], DefMap) ->
    def_successors(successors(Last), Def, DefMap).

def_successors([S|Ss], Def0, DefMap) ->
    case DefMap of
        #{S:=Def1} ->
            Def = ordsets:intersection(Def0, Def1),
            def_successors(Ss, Def0, DefMap#{S:=Def});
        #{} ->
            def_successors(Ss, Def0, DefMap#{S=>Def0})
    end;
def_successors([], _, DefMap) -> DefMap.

%% need_y_init(#cg_set{}) -> true|false.
%%  Return true if this instructions needs initialized Y registers
%%  (because the instruction may do a GC or cause an exception
%%  so that the stack will be scanned), or false otherwise.

need_y_init(#cg_set{anno=#{clobbers:=Clobbers}}) -> Clobbers;
need_y_init(#cg_set{op=bs_get}) -> true;
need_y_init(#cg_set{op=bs_get_position}) -> true;
need_y_init(#cg_set{op=bs_get_tail}) -> true;
need_y_init(#cg_set{op=bs_init}) -> true;
need_y_init(#cg_set{op=bs_skip,args=[#b_literal{val=Type}|_]}) ->
    case Type of
        utf8 -> true;
        utf16 -> true;
        utf32 -> true;
        _ -> false
    end;
need_y_init(#cg_set{op=bs_start_match}) -> true;
need_y_init(#cg_set{op=put_map}) -> true;
need_y_init(#cg_set{}) -> false.

%% opt_allocate([{BlockLabel,Block}], #st{}) -> [BeamInstruction].
%%  Update the def_yregs field of each #cg_alloc{} that allocates
%%  a stack frame. #cg_alloc.def_yregs will list all Y registers
%%  that will be initialized by the subsequent code (thus, the
%%  listed Y registers don't require init/1 instructions).

opt_allocate(Linear, #cg{regs=Regs}) ->
    opt_allocate_1(Linear, Regs).

opt_allocate_1([{L,#cg_blk{is=[#cg_alloc{stack=Stk}=I0|Is]}=Blk0}|Bs]=Bs0, Regs)
  when is_integer(Stk) ->
    %% Collect the variables that are initialized by copy
    %% instruction in this block.
    case ordsets:from_list(opt_allocate_defs(Is, Regs)) of
        Yregs when length(Yregs) =:= Stk ->
            %% Those copy instructions are sufficient to fully
            %% initialize the stack frame.
            I = I0#cg_alloc{def_yregs=Yregs},
            [{L,Blk0#cg_blk{is=[I|Is]}}|opt_allocate_1(Bs, Regs)];
        Yregs0 ->
            %% Determine a conservative approximation of the Y
            %% registers that are guaranteed to be initialized by all
            %% successors of this block, and to it add the variables
            %% initialized by copy instructions in this block.
            Yregs1 = opt_alloc_def(Bs0, gb_sets:singleton(L), []),
            Yregs = ordsets:union(Yregs0, Yregs1),
            I = I0#cg_alloc{def_yregs=Yregs},
            [{L,Blk0#cg_blk{is=[I|Is]}}|opt_allocate_1(Bs, Regs)]
    end;
opt_allocate_1([B|Bs], Regs) ->
    [B|opt_allocate_1(Bs, Regs)];
opt_allocate_1([], _) -> [].

opt_allocate_defs([#cg_set{op=copy,dst=Dst}|Is], Regs) ->
    case is_yreg(Dst, Regs) of
        true -> [Dst|opt_allocate_defs(Is, Regs)];
        false -> []
    end;
opt_allocate_defs(_, _Regs) -> [].

opt_alloc_def([{L,#cg_blk{is=Is,last=Last}}|Bs], Ws0, Def0) ->
    case gb_sets:is_member(L, Ws0) of
        false ->
            opt_alloc_def(Bs, Ws0, Def0);
        true ->
            case opt_allocate_is(Is) of
                none ->
                    Succ = successors(Last),
                    Ws = gb_sets:union(Ws0, gb_sets:from_list(Succ)),
                    opt_alloc_def(Bs, Ws, Def0);
                Def1 when is_list(Def1) ->
                    Def = [Def1|Def0],
                    opt_alloc_def(Bs, Ws0, Def)
            end
    end;
opt_alloc_def([], _, Def) ->
    ordsets:intersection(Def).

opt_allocate_is([#cg_set{anno=Anno}|Is]) ->
    case Anno of
        #{def_yregs:=Yregs} ->
            Yregs;
        #{} ->
            opt_allocate_is(Is)
    end;
opt_allocate_is([#cg_alloc{anno=#{def_yregs:=Yregs},stack=none}|_]) ->
    Yregs;
opt_allocate_is([#cg_alloc{}|Is]) ->
    opt_allocate_is(Is);
opt_allocate_is([]) -> none.

%%%
%%% Here follows the main code generation functions.
%%%

%% cg_linear([{BlockLabel,Block}]) -> [BeamInstruction].
%%  Generate BEAM instructions.

cg_linear([{L,#cg_blk{anno=#{recv_set:=L}=Anno0}=B0}|Bs], St0) ->
    Anno = maps:remove(recv_set, Anno0),
    B = B0#cg_blk{anno=Anno},
    {Is,St1} = cg_linear([{L,B}|Bs], St0),
    {Fail,St} = use_block_label(L, St1),
    {[{recv_set,Fail}|Is],St};
cg_linear([{L,#cg_blk{is=Is0,last=Last}}|Bs], St0) ->
    Next = next_block(Bs),
    St1 = new_block_label(L, St0),
    {Is1,St2} = cg_block(Is0, Last, Next, St1),
    {Is2,St} = cg_linear(Bs, St2),
    {def_block_label(L, St)++Is1++Is2,St};
cg_linear([], St) -> {[],St}.

cg_block([#cg_set{op=recv_next}], #cg_br{succ=Lr0}, _Next, St0) ->
    {Lr,St} = use_block_label(Lr0, St0),
    {[{loop_rec_end,Lr}],St};
cg_block([#cg_set{op=wait}], #cg_br{succ=Lr0}, _Next, St0) ->
    {Lr,St} = use_block_label(Lr0, St0),
    {[{wait,Lr}],St};
cg_block(Is0, Last, Next, St0) ->
    case Last of
        #cg_br{succ=Next,fail=Next} ->
            cg_block(Is0, none, St0);
        #cg_br{succ=Same,fail=Same} when Same =:= ?EXCEPTION_BLOCK ->
            %% An expression in this block *always* throws an exception, so we
            %% terminate it with an 'if_end' to make sure the validator knows
            %% that the following instructions won't actually be reached.
            {Is,St} = cg_block(Is0, none, St0),
            {Is++[if_end],St};
        #cg_br{succ=Same,fail=Same} ->
            {Fail,St1} = use_block_label(Same, St0),
            {Is,St} = cg_block(Is0, none, St1),
            {Is++[jump(Fail)],St};
        #cg_br{bool=Bool,succ=Next,fail=Fail0} ->
            {Fail,St1} = use_block_label(Fail0, St0),
            {Is,St} = cg_block(Is0, {Bool,Fail}, St1),
            {Is,St};
        #cg_br{bool=Bool,succ=Succ0,fail=Fail0} ->
            {[Succ,Fail],St1} = use_block_labels([Succ0,Fail0], St0),
            {Is,St} = cg_block(Is0, {Bool,Fail}, St1),
            {Is++[jump(Succ)],St};
        #cg_ret{arg=Src0,dealloc=N} ->
            Src = beam_arg(Src0, St0),
            cg_block(Is0, {return,Src,N}, St0);
        #cg_switch{} ->
            cg_switch(Is0, Last, St0)
    end.

cg_switch(Is0, Last, St0) ->
    #cg_switch{arg=Src0,fail=Fail0,list=List0} = Last,
    Src = beam_arg(Src0, St0),
    {Fail1,St1} = use_block_label(Fail0, St0),
    Fail = ensure_label(Fail1, St1),
    {List1,St2} =
        flatmapfoldl(fun({V,L}, S0) ->
                             {Lbl,S} = use_block_label(L, S0),
                             {[beam_arg(V, S),Lbl],S}
                     end, St1, List0),
    {Is1,St} = cg_block(Is0, none, St2),
    case reverse(Is1) of
        [{bif,tuple_size,_,[Tuple],{z,_}=Src}|More] ->
            List = map(fun({integer,Arity}) -> Arity;
                          ({f,_}=F) -> F
                       end, List1),
            Is = reverse(More, [{select_tuple_arity,Tuple,Fail,{list,List}}]),
            {Is,St};
        _ ->
            SelectVal = {select_val,Src,Fail,{list,List1}},
            {Is1 ++ [SelectVal],St}
    end.

jump({f,_}=Fail) ->
    {jump,Fail};
jump({catch_tag,Fail}) ->
    {jump,Fail}.

bif_fail({f,_}=Fail) -> Fail;
bif_fail({catch_tag,_}) -> {f,0}.

next_block([]) -> none;
next_block([{Next,_}|_]) -> Next.

%% Certain instructions (such as get_map_element or is_nonempty_list)
%% are only used in guards and **must** have a non-zero label;
%% otherwise, the loader will refuse to load the
%% module. ensure_label/2 replaces a zero label with the "ultimate
%% failure" label to make the module loadable.  The instruction that
%% have had the zero label replaced is **not** supposed to ever fail
%% and actually jump to the label.

ensure_label(Fail0, #cg{ultimate_fail=Lbl}) ->
    case bif_fail(Fail0) of
        {f,0} -> {f,Lbl};
        {f,_}=Fail -> Fail
    end.

cg_block([#cg_set{anno=#{recv_mark:=L}=Anno0}=I0|T], Context, St0) ->
    Anno = maps:remove(recv_mark, Anno0),
    I = I0#cg_set{anno=Anno},
    {Is,St1} = cg_block([I|T], Context, St0),
    {Fail,St} = use_block_label(L, St1),
    {[{recv_mark,Fail}|Is],St};
cg_block([#cg_set{op=new_try_tag,dst=Tag,args=Args}], {Tag,Fail0}, St) ->
    {catch_tag,Fail} = Fail0,
    [Reg,{atom,Kind}] = beam_args([Tag|Args], St),
    {[{Kind,Reg,Fail}],St};
cg_block([#cg_set{anno=Anno,op={bif,Name},dst=Dst0,args=Args0}=I,
          #cg_set{op=succeeded,dst=Bool}], {Bool,Fail0}, St) ->
    [Dst|Args] = beam_args([Dst0|Args0], St),
    Line0 = call_line(body, {extfunc,erlang,Name,length(Args)}, Anno),
    Fail = bif_fail(Fail0),
    Line = case Fail of
               {f,0} -> Line0;
               {f,_} -> []
           end,
    case is_gc_bif(Name, Args) of
        true ->
            Live = get_live(I),
            Kill = kill_yregs(Anno, St),
            {Kill++Line++[{gc_bif,Name,Fail,Live,Args,Dst}],St};
        false ->
            {Line++[{bif,Name,Fail,Args,Dst}],St}
    end;
cg_block([#cg_set{op={bif,tuple_size},dst=Arity0,args=[Tuple0]},
          #cg_set{op={bif,'=:='},dst=Bool,args=[Arity0,#b_literal{val=Ar}]}=Eq],
         {Bool,Fail}=Context, St0) ->
    Tuple = beam_arg(Tuple0, St0),
    case beam_arg(Arity0, St0) of
        {z,_} ->
            %% The size will only be used once. Combine to a test_arity instruction.
            Test = {test,test_arity,ensure_label(Fail, St0),[Tuple,Ar]},
            {[Test],St0};
        Arity ->
            %% The size will be used more than once. Must do an explicit
            %% BIF call followed by the '==' test.
            TupleSize = {bif,tuple_size,{f,0},[Tuple],Arity},
            {Is,St} = cg_block([Eq], Context, St0),
            {[TupleSize|Is],St}
    end;
cg_block([#cg_set{op={bif,Name},dst=Dst0,args=Args0}]=Is0, {Dst0,Fail}, St0) ->
    [Dst|Args] = beam_args([Dst0|Args0], St0),
    case Dst of
        {z,_} ->
            %% The result of the BIF call will only be used once. Convert to
            %% a test instruction.
            {Test,St1} = bif_to_test(Name, Args, ensure_label(Fail, St0), St0),
            {Test,St1};
        _ ->
            %% Must explicitly call the BIF since the result will be used
            %% more than once.
            {Is1,St1} = cg_block(Is0, none, St0),
            {Is2,St} = cg_block([], {Dst0,Fail}, St1),
            {Is1++Is2,St}
    end;
cg_block([#cg_set{anno=Anno,op={bif,Name},dst=Dst0,args=Args0}=I|T],
         Context, St0) ->
    [Dst|Args] = beam_args([Dst0|Args0], St0),
    {Is0,St} = cg_block(T, Context, St0),
    case is_gc_bif(Name, Args) of
        true ->
            Line = call_line(body, {extfunc,erlang,Name,length(Args)}, Anno),
            Live = get_live(I),
            Kill = kill_yregs(Anno, St),
            Is = Kill++Line++[{gc_bif,Name,{f,0},Live,Args,Dst}|Is0],
            {Is,St};
        false ->
            Is = [{bif,Name,{f,0},Args,Dst}|Is0],
            {Is,St}
    end;
cg_block([#cg_set{op=bs_init,dst=Dst0,args=Args0,anno=Anno}=I,
          #cg_set{op=succeeded,dst=Bool}], {Bool,Fail0}, St) ->
    Fail = bif_fail(Fail0),
    Line = line(Anno),
    Alloc = map_get(alloc, Anno),
    [#b_literal{val=Kind}|Args1] = Args0,
    case Kind of
        new ->
            [Dst,Size,{integer,Unit}] = beam_args([Dst0|Args1], St),
            Live = get_live(I),
            {[Line|cg_bs_init(Dst, Size, Alloc, Unit, Live, Fail)],St};
        private_append ->
            [Dst,Src,Bits,{integer,Unit}] = beam_args([Dst0|Args1], St),
            Flags = {field_flags,[]},
            Is = [Line,{bs_private_append,Fail,Bits,Unit,Src,Flags,Dst}],
            {Is,St};
        append ->
            [Dst,Src,Bits,{integer,Unit}] = beam_args([Dst0|Args1], St),
            Flags = {field_flags,[]},
            Live = get_live(I),
            Is = [Line,{bs_append,Fail,Bits,Alloc,Live,Unit,Src,Flags,Dst}],
            {Is,St}
    end;
cg_block([#cg_set{anno=Anno,op=bs_start_match,dst=Ctx0,args=[Bin0]}=I,
          #cg_set{op=succeeded,dst=Bool}], {Bool,Fail}, St) ->
    [Dst,Bin1] = beam_args([Ctx0,Bin0], St),
    {Bin,Pre} = force_reg(Bin1, Dst),
    Live = get_live(I),
    %% num_slots is only set when using the old instructions.
    case maps:find(num_slots, Anno) of
        {ok, Slots} ->
            Is = Pre ++ [{test,bs_start_match2,Fail,Live,[Bin,Slots],Dst}],
            {Is,St};
        error ->
            Is = Pre ++ [{test,bs_start_match3,Fail,Live,[Bin],Dst}],
            {Is,St}
    end;
cg_block([#cg_set{op=bs_get}=Set,
          #cg_set{op=succeeded,dst=Bool}], {Bool,Fail}, St) ->
    {cg_bs_get(Fail, Set, St),St};
cg_block([#cg_set{op=bs_match_string,args=[CtxVar,#b_literal{val=String}]},
          #cg_set{op=succeeded,dst=Bool}], {Bool,Fail}, St) ->
    CtxReg = beam_arg(CtxVar, St),
    Is = [{test,bs_match_string,Fail,[CtxReg,String]}],
    {Is,St};
cg_block([#cg_set{dst=Dst0,op=landingpad,args=Args0}|T], Context, St0) ->
    [Dst,{atom,Kind},Tag] = beam_args([Dst0|Args0], St0),
    case Kind of
        'catch' ->
            cg_catch(Dst, T, Context, St0);
        'try' ->
            cg_try(Dst, Tag, T, Context, St0)
    end;
cg_block([#cg_set{op=kill_try_tag,args=Args0}|Is], Context, St0) ->
    [Reg] = beam_args(Args0, St0),
    {Is0,St} = cg_block(Is, Context, St0),
    {[{try_end,Reg}|Is0],St};
cg_block([#cg_set{op=catch_end,dst=Dst0,args=Args0}|Is], Context, St0) ->
    [Dst,Reg,{x,0}] = beam_args([Dst0|Args0], St0),
    {Is0,St} = cg_block(Is, Context, St0),
    {[{catch_end,Reg}|copy({x,0}, Dst)++Is0],St};
cg_block([#cg_set{op=call}=I,
          #cg_set{op=succeeded,dst=Bool}], {Bool,_Fail}, St) ->
    %% A call in try/catch block.
    cg_block([I], none, St);
cg_block([#cg_set{op=match_fail}=I,
          #cg_set{op=succeeded,dst=Bool}], {Bool,_Fail}, St) ->
    %% A match_fail instruction in a try/catch block.
    cg_block([I], none, St);
cg_block([#cg_set{op=get_map_element,dst=Dst0,args=Args0},
          #cg_set{op=succeeded,dst=Bool}], {Bool,Fail0}, St) ->
    [Dst,Map,Key] = beam_args([Dst0|Args0], St),
    Fail = ensure_label(Fail0, St),
    {[{get_map_elements,Fail,Map,{list,[Key,Dst]}}],St};
cg_block([#cg_set{op=Op,dst=Dst0,args=Args0}=I,
          #cg_set{op=succeeded,dst=Bool}], {Bool,Fail}, St) ->
    [Dst|Args] = beam_args([Dst0|Args0], St),
    {cg_test(Op, bif_fail(Fail), Args, Dst, I),St};
cg_block([#cg_set{op=bs_put,dst=Bool,args=Args0}], {Bool,Fail}, St) ->
    Args = beam_args(Args0, St),
    {cg_bs_put(bif_fail(Fail), Args),St};
cg_block([#cg_set{op=bs_test_tail,dst=Bool,args=Args0}], {Bool,Fail}, St) ->
    [Ctx,{integer,Bits}] = beam_args(Args0, St),
    {[{test,bs_test_tail2,bif_fail(Fail),[Ctx,Bits]}],St};
cg_block([#cg_set{op={float,checkerror},dst=Bool}], {Bool,Fail}, St) ->
    {[{fcheckerror,bif_fail(Fail)}],St};
cg_block([#cg_set{op=is_tagged_tuple,dst=Bool,args=Args0}], {Bool,Fail}, St) ->
    [Src,{integer,Arity},Tag] = beam_args(Args0, St),
    {[{test,is_tagged_tuple,ensure_label(Fail, St),[Src,Arity,Tag]}],St};
cg_block([#cg_set{op=is_nonempty_list,dst=Bool,args=Args0}], {Bool,Fail}, St) ->
    Args = beam_args(Args0, St),
    {[{test,is_nonempty_list,ensure_label(Fail, St),Args}],St};
cg_block([#cg_set{op=has_map_field,dst=Bool,args=Args0}], {Bool,Fail}, St) ->
    [Src,Key] = beam_args(Args0, St),
    {[{test,has_map_fields,Fail,Src,{list,[Key]}}],St};
cg_block([#cg_set{op=call}=Call], {_Bool,_Fail}=Context, St0) ->
    {Is0,St1} = cg_call(Call, body, none, St0),
    {Is1,St} = cg_block([], Context, St1),
    {Is0++Is1,St};
cg_block([#cg_set{op=call,dst=Dst0}=Call], Context, St) ->
    Dst = beam_arg(Dst0, St),
    case Context of
        {return,Dst,_} ->
            cg_call(Call, tail, Context, St);
        _ ->
            cg_call(Call, body, Context, St)
    end;
cg_block([#cg_set{op=call}=Call|T], Context, St0) ->
    {Is0,St1} = cg_call(Call, body, none, St0),
    {Is1,St} = cg_block(T, Context, St1),
    {Is0++Is1,St};
cg_block([#cg_set{op=make_fun,dst=Dst0,args=[Local|Args0]}|T],
         Context, St0) ->
    #b_local{name=#b_literal{val=Func},arity=Arity} = Local,
    [Dst|Args] = beam_args([Dst0|Args0], St0),
    {FuncLbl,St1} = local_func_label(Func, Arity, St0),
    Is0 = setup_args(Args) ++
        [{make_fun2,{f,FuncLbl},0,0,length(Args)}|copy({x,0}, Dst)],
    {Is1,St} = cg_block(T, Context, St1),
    {Is0++Is1,St};
cg_block([#cg_set{op=copy}|_]=T0, Context, St0) ->
    {Is0,T} = cg_copy(T0, St0),
    {Is1,St} = cg_block(T, Context, St0),
    Is = Is0 ++ Is1,
    case is_call(T) of
        {yes,Arity} ->
            {opt_call_moves(Is, Arity),St};
        no ->
            {Is,St}
    end;
cg_block([#cg_set{op=match_fail,args=Args0,anno=Anno}], none, St) ->
    Args = beam_args(Args0, St),
    Is = cg_match_fail(Args, line(Anno), none),
    {Is,St};
cg_block([#cg_set{op=match_fail,args=Args0,anno=Anno}|T], Context, St0) ->
    FcLabel = case Context of
                  {return,_,none} ->
                      %% There is no stack frame. If this is a function_clause
                      %% exception, it is safe to jump to the label of the
                      %% func_info instruction.
                      St0#cg.fc_label;
                  _ ->
                      %% This is most probably not a function_clause.
                      %% If this is a function_clause exception
                      %% (rare), it is not safe to jump to the
                      %% func_info label.
                      none
              end,
    Args = beam_args(Args0, St0),
    Is0 = cg_match_fail(Args, line(Anno), FcLabel),
    {Is1,St} = cg_block(T, Context, St0),
    {Is0++Is1,St};
cg_block([#cg_set{op=Op,dst=Dst0,args=Args0}=Set], none, St) ->
    [Dst|Args] = beam_args([Dst0|Args0], St),
    Is = cg_instr(Op, Args, Dst, Set),
    {Is,St};
cg_block([#cg_set{op=Op,dst=Dst0,args=Args0}=Set|T], Context, St0) ->
    [Dst|Args] = beam_args([Dst0|Args0], St0),
    Is0 = cg_instr(Op, Args, Dst, Set),
    {Is1,St} = cg_block(T, Context, St0),
    {Is0++Is1,St};
cg_block([#cg_alloc{}=Alloc|T], Context, St0) ->
    Is0 = cg_alloc(Alloc, St0),
    {Is1,St} = cg_block(T, Context, St0),
    {Is0++Is1,St};
cg_block([], {return,Arg,none}, St) ->
    Is = copy(Arg, {x,0}) ++ [return],
    {Is,St};
cg_block([], {return,Arg,N}, St) ->
    Is = copy(Arg, {x,0}) ++ [{deallocate,N},return],
    {Is,St};
cg_block([], none, St) ->
    {[],St};
cg_block([], {Bool0,Fail}, St) ->
    [Bool] = beam_args([Bool0], St),
    {[{test,is_eq_exact,Fail,[Bool,{atom,true}]}],St}.

cg_copy(T0, St) ->
    {Copies,T} = splitwith(fun(#cg_set{op=copy}) -> true;
                              (_) -> false
                           end, T0),
    Moves0 = cg_copy_1(Copies, St),
    Moves1 = [Move || {move,Src,Dst}=Move <- Moves0, Src =/= Dst],
    Moves = order_moves(Moves1),
    {Moves,T}.

cg_copy_1([#cg_set{dst=Dst0,args=Args}|T], St) ->
    [Dst,Src] = beam_args([Dst0|Args], St),
    Copies = cg_copy_1(T, St),
    case keymember(Dst, 3, Copies) of
        true ->
            %% Will be overwritten. Don't generate a move instruction.
            Copies;
        false ->
            [{move,Src,Dst}|Copies]
    end;
cg_copy_1([], _St) -> [].

-define(IS_LITERAL(Val), (Val =:= nil orelse
                          element(1, Val) =:= integer orelse
                          element(1, Val) =:= float orelse
                          element(1, Val) =:= atom orelse
                          element(1, Val) =:= literal)).

bif_to_test('or', [V1,V2], {f,Lbl}=Fail, St0) when Lbl =/= 0 ->
    {SuccLabel,St} = new_label(St0),
    {[{test,is_eq_exact,{f,SuccLabel},[V1,{atom,false}]},
      {test,is_eq_exact,Fail,[V2,{atom,true}]},
      {label,SuccLabel}],St};
bif_to_test(Op, Args, Fail, St) ->
    {bif_to_test(Op, Args, Fail),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('not', [Var], Fail) ->
    [{test,is_eq_exact,Fail,[Var,{atom,false}]}];
bif_to_test(Name, Args, Fail) ->
    [bif_to_test_1(Name, Args, Fail)].

bif_to_test_1(is_atom,     [_]=Ops, Fail) ->
    {test,is_atom,Fail,Ops};
bif_to_test_1(is_boolean,  [_]=Ops, Fail) ->
    {test,is_boolean,Fail,Ops};
bif_to_test_1(is_binary,   [_]=Ops, Fail) ->
    {test,is_binary,Fail,Ops};
bif_to_test_1(is_bitstring,[_]=Ops, Fail) ->
    {test,is_bitstr,Fail,Ops};
bif_to_test_1(is_float,    [_]=Ops, Fail) ->
    {test,is_float,Fail,Ops};
bif_to_test_1(is_function, [_]=Ops, Fail) ->
    {test,is_function,Fail,Ops};
bif_to_test_1(is_function, [_,_]=Ops, Fail) ->
    {test,is_function2,Fail,Ops};
bif_to_test_1(is_integer,  [_]=Ops, Fail) ->
    {test,is_integer,Fail,Ops};
bif_to_test_1(is_list,     [_]=Ops, Fail) ->
    {test,is_list,Fail,Ops};
bif_to_test_1(is_map,      [_]=Ops, Fail) ->
    {test,is_map,Fail,Ops};
bif_to_test_1(is_number,   [_]=Ops, Fail) ->
    {test,is_number,Fail,Ops};
bif_to_test_1(is_pid,      [_]=Ops, Fail) ->
    {test,is_pid,Fail,Ops};
bif_to_test_1(is_port,     [_]=Ops, Fail) ->
    {test,is_port,Fail,Ops};
bif_to_test_1(is_reference, [_]=Ops, Fail) ->
    {test,is_reference,Fail,Ops};
bif_to_test_1(is_tuple,    [_]=Ops, Fail) ->
    {test,is_tuple,Fail,Ops};
bif_to_test_1('=<', [A,B], Fail) ->
    {test,is_ge,Fail,[B,A]};
bif_to_test_1('>', [A,B], Fail) ->
    {test,is_lt,Fail,[B,A]};
bif_to_test_1('<', [_,_]=Ops, Fail) ->
    {test,is_lt,Fail,Ops};
bif_to_test_1('>=', [_,_]=Ops, Fail) ->
    {test,is_ge,Fail,Ops};
bif_to_test_1('==', [C,A], Fail) when ?IS_LITERAL(C) ->
    {test,is_eq,Fail,[A,C]};
bif_to_test_1('==', [_,_]=Ops, Fail) ->
    {test,is_eq,Fail,Ops};
bif_to_test_1('/=', [C,A], Fail) when ?IS_LITERAL(C) ->
    {test,is_ne,Fail,[A,C]};
bif_to_test_1('/=', [_,_]=Ops, Fail) ->
    {test,is_ne,Fail,Ops};
bif_to_test_1('=:=', [C,A], Fail) when ?IS_LITERAL(C) ->
    {test,is_eq_exact,Fail,[A,C]};
bif_to_test_1('=:=', [_,_]=Ops, Fail) ->
    {test,is_eq_exact,Fail,Ops};
bif_to_test_1('=/=', [C,A], Fail) when ?IS_LITERAL(C) ->
    {test,is_ne_exact,Fail,[A,C]};
bif_to_test_1('=/=', [_,_]=Ops, Fail) ->
    {test,is_ne_exact,Fail,Ops}.

opt_call_moves(Is0, Arity) ->
    {Moves0,Is} = splitwith(fun({move,_,_}) -> true;
                               ({kill,_}) -> true;
                               (_) -> false
                            end, Is0),
    Moves = opt_call_moves_1(Moves0, Arity),
    Moves ++ Is.

opt_call_moves_1([{move,Src,{x,_}=Tmp}=M1|[{kill,_}|_]=Is], Arity) ->
    %% There could be a {move,Tmp,{x,0}} instruction after the
    %% kill/1 instructions (moved to there by opt_move_to_x0/1).
    case splitwith(fun({kill,_}) -> true;
                      (_) -> false
                   end, Is) of
        {Kills,[{move,{x,_}=Tmp,{x,0}}=M2]} ->
            %% The two move/2 instructions (M1 and M2) can be combined
            %% to one. The question is, though, is it safe to place
            %% them after the kill/1 instructions?
            case is_killed(Src, Kills, Arity) of
                true ->
                    %% Src (a Y register) is killed by one of the
                    %% kill/1 instructions. Thus M1 and M2
                    %% must be placed before the kill/1 instructions
                    %% (essentially undoing what opt_move_to_x0/1
                    %% did, which turned out to be a pessimization
                    %% in this case).
                    opt_call_moves_1([M1,M2|Kills], Arity);
                false ->
                    %% Src is not killed by any of the kill/1
                    %% instructions. Thus it is safe to place
                    %% M1 and M2 after the kill/1 instructions.
                    opt_call_moves_1(Kills++[M1,M2], Arity)
            end;
        {_,_} ->
            [M1|Is]
    end;
opt_call_moves_1([{move,Src,{x,_}=Tmp}=M1,{move,Tmp,Dst}=M2|Is], Arity) ->
    case is_killed(Tmp, Is, Arity) of
        true ->
            %% The X register Tmp is never used again. We can collapse
            %% the two move instruction into one.
            [{move,Src,Dst}|opt_call_moves_1(Is, Arity)];
        false ->
            [M1|opt_call_moves_1([M2|Is], Arity)]
    end;
opt_call_moves_1([M|Ms], Arity) ->
    [M|opt_call_moves_1(Ms, Arity)];
opt_call_moves_1([], _Arity) -> [].

is_killed(Y, [{kill,Y}|_], _) ->
    true;
is_killed(R, [{kill,_}|Is], Arity) ->
    is_killed(R, Is, Arity);
is_killed(R, [{move,R,_}|_], _) ->
    false;
is_killed(R, [{move,_,R}|_], _) ->
    true;
is_killed(R, [{move,_,_}|Is], Arity) ->
    is_killed(R, Is, Arity);
is_killed({x,X}, [], Arity) ->
    X >= Arity;
is_killed({y,_}, [], _) ->
    false.

cg_alloc(#cg_alloc{stack=none,words=#need{h=0,f=0}}, _St) ->
    [];
cg_alloc(#cg_alloc{stack=none,words=Need,live=Live}, _St) ->
    [{test_heap,alloc(Need),Live}];
cg_alloc(#cg_alloc{stack=Stk,words=Need,live=Live,def_yregs=DefYregs},
         #cg{regs=Regs}) when is_integer(Stk) ->
    Alloc = alloc(Need),
    All = [{y,Y} || Y <- lists:seq(0, Stk-1)],
    Def = ordsets:from_list([maps:get(V, Regs) || V <- DefYregs]),
    NeedInit = ordsets:subtract(All, Def),
    NoZero = length(Def)*2 > Stk,
    I = case {NoZero,Alloc} of
            {true,0} -> {allocate,Stk,Live};
            {true,_} -> {allocate_heap,Stk,Alloc,Live};
            {false,0} -> {allocate_zero,Stk,Live};
            {false,_} -> {allocate_heap_zero,Stk,Alloc,Live}
        end,
    [I|case NoZero of
           true -> [{init,Y} || Y <- NeedInit];
           false -> []
       end].

alloc(#need{h=Words,f=0}) ->
    Words;
alloc(#need{h=Words,f=Floats}) ->
    {alloc,[{words,Words},{floats,Floats}]}.

is_call([#cg_set{op=call,args=[#b_var{}|Args]}|_]) ->
    {yes,1+length(Args)};
is_call([#cg_set{op=call,args=[_|Args]}|_]) ->
    {yes,length(Args)};
is_call([#cg_set{op=make_fun,args=[_|Args]}|_]) ->
    {yes,length(Args)};
is_call(_) ->
    no.

cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=[#b_local{}=Func0|Args0]},
        Where, Context, St0) ->
    [Dst|Args] = beam_args([Dst0|Args0], St0),
    #b_local{name=Name0,arity=Arity} = Func0,
    {atom,Name} = beam_arg(Name0, St0),
    {FuncLbl,St} = local_func_label(Name, Arity, St0),
    Line = call_line(Where, local, Anno),
    Call = build_call(call, Arity, {f,FuncLbl}, Context, Dst),
    Is = setup_args(Args, Anno, Context, St) ++ Line ++ Call,
    case Anno of
        #{ result_type := Info } ->
            {Is ++ [{'%', {type_info, Dst, Info}}], St};
        #{} ->
            {Is, St}
    end;
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, 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], Anno0, Context, St) ++
                [line(Anno0)] ++ Apply,
            {Is,St}
    end;
cg_call(#cg_set{anno=Anno,op=call,dst=Dst0,args=Args0},
        Where, Context, St) ->
    [Dst,Func|Args] = beam_args([Dst0|Args0], St),
    Line = call_line(Where, Func, Anno),
    Arity = length(Args),
    Call = build_call(call_fun, Arity, Func, Context, Dst),
    Is = setup_args(Args++[Func], Anno, Context, St) ++ Line ++ Call,
    {Is,St}.

cg_match_fail([{atom,function_clause}|Args], Line, Fc) ->
    case Fc of
        none ->
            %% There is a stack frame (probably because of inlining).
            %% Jumping to the func_info label is not allowed by
            %% beam_validator. Rewrite the instruction as a call to
            %% erlang:error/2.
            make_fc(Args, Line);
        _ ->
            setup_args(Args) ++ [{jump,{f,Fc}}]
    end;
cg_match_fail([{atom,Op}], Line, _Fc) ->
    [Line,Op];
cg_match_fail([{atom,Op},Val], Line, _Fc) ->
    [Line,{Op,Val}].

make_fc(Args, Line) ->
    %% Recreate the original call to erlang:error/2.
    Live = foldl(fun({x,X}, A) -> max(X+1, A);
                    (_, A) -> A
                 end, 0, Args),
    TmpReg = {x,Live},
    StkMoves = build_stk(reverse(Args), TmpReg, nil),
    [{test_heap,2*length(Args),Live}|StkMoves] ++
        [{move,{atom,function_clause},{x,0}},
         Line,
         {call_ext,2,{extfunc,erlang,error,2}}].

build_stk([V], _TmpReg, Tail) ->
    [{put_list,V,Tail,{x,1}}];
build_stk([V|Vs], TmpReg, Tail) ->
    I = {put_list,V,Tail,TmpReg},
    [I|build_stk(Vs, TmpReg, TmpReg)];
build_stk([], _TmpReg, nil) ->
    [{move,nil,{x,1}}].

build_call(call_fun, Arity, _Func, none, Dst) ->
    [{call_fun,Arity}|copy({x,0}, Dst)];
build_call(call_fun, Arity, _Func, {return,Dst,N}, Dst) when is_integer(N) ->
    [{call_fun,Arity},{deallocate,N},return];
build_call(call_fun, Arity, _Func, {return,Val,N}, _Dst) when is_integer(N) ->
    [{call_fun,Arity},{move,Val,{x,0}},{deallocate,N},return];
build_call(call_ext, 2, {extfunc,erlang,'!',2}, none, Dst) ->
    [send|copy({x,0}, Dst)];
build_call(call_ext, 2, {extfunc,erlang,'!',2}, {return,Dst,N}, Dst)
  when is_integer(N) ->
    [send,{deallocate,N},return];
build_call(Prefix, Arity, Func, {return,Dst,none}, Dst) ->
    I = case Prefix of
            call -> call_only;
            call_ext -> call_ext_only
        end,
    [{I,Arity,Func}];
build_call(call_ext, Arity, {extfunc,Mod,Name,Arity}=Func, {return,_,none}, _Dst) ->
    true = erl_bifs:is_exit_bif(Mod, Name, Arity), %Assertion.
    [{call_ext_only,Arity,Func}];
build_call(Prefix, Arity, Func, {return,Dst,N}, Dst) when is_integer(N) ->
    I = case Prefix of
            call -> call_last;
            call_ext -> call_ext_last
        end,
    [{I,Arity,Func,N}];
build_call(I, Arity, Func, {return,Val,N}, _Dst) when is_integer(N) ->
    [{I,Arity,Func}|copy(Val, {x,0})++[{deallocate,N},return]];
build_call(I, Arity, Func, none, Dst) ->
    [{I,Arity,Func}|copy({x,0}, Dst)].

build_apply(Arity, {return,Dst,N}, Dst) when is_integer(N) ->
    [{apply_last,Arity,N}];
build_apply(Arity, {return,Val,N}, _Dst) when is_integer(N) ->
    [{apply,Arity}|copy(Val, {x,0})++[{deallocate,N},return]];
build_apply(Arity, none, Dst) ->
    [{apply,Arity}|copy({x,0}, Dst)].

cg_instr(bs_get_tail, [Src], Dst, Set) ->
    Live = get_live(Set),
    [{bs_get_tail,Src,Dst,Live}];
cg_instr(bs_get_position, [Ctx], Dst, Set) ->
    Live = get_live(Set),
    [{bs_get_position,Ctx,Dst,Live}];
cg_instr(put_map, [{atom,assoc},SrcMap|Ss], Dst, Set) ->
    Live = get_live(Set),
    [{put_map_assoc,{f,0},SrcMap,Dst,Live,{list,Ss}}];
cg_instr(Op, Args, Dst, _Set) ->
    cg_instr(Op, Args, Dst).

cg_instr(bs_init_writable, Args, Dst) ->
    setup_args(Args) ++ [bs_init_writable|copy({x,0}, Dst)];
cg_instr(bs_restore, [Ctx,Slot], _Dst) ->
    case Slot of
        {integer,N} ->
            [{bs_restore2,Ctx,N}];
        {atom,start} ->
            [{bs_restore2,Ctx,Slot}]
    end;
cg_instr(bs_save, [Ctx,Slot], _Dst) ->
    {integer,N} = Slot,
    [{bs_save2,Ctx,N}];
cg_instr(bs_set_position, [Ctx,Pos], _Dst) ->
    [{bs_set_position,Ctx,Pos}];
cg_instr(build_stacktrace, Args, Dst) ->
    setup_args(Args) ++ [build_stacktrace|copy({x,0}, Dst)];
cg_instr(set_tuple_element=Op, [New,Tuple,{integer,Index}], _Dst) ->
    [{Op,New,Tuple,Index}];
cg_instr({float,clearerror}, [], _Dst) ->
    [fclearerror];
cg_instr({float,get}, [Src], Dst) ->
    [{fmove,Src,Dst}];
cg_instr({float,put}, [Src], Dst) ->
    [{fmove,Src,Dst}];
cg_instr(get_hd=Op, [Src], Dst) ->
    [{Op,Src,Dst}];
cg_instr(get_tl=Op, [Src], Dst) ->
    [{Op,Src,Dst}];
cg_instr(get_tuple_element=Op, [Src,{integer,N}], Dst) ->
    [{Op,Src,N,Dst}];
cg_instr(put_list=Op, [Hd,Tl], Dst) ->
    [{Op,Hd,Tl,Dst}];
cg_instr(put_tuple, Elements, Dst) ->
    [{put_tuple2,Dst,{list,Elements}}];
cg_instr(put_tuple_arity, [{integer,Arity}], Dst) ->
    [{put_tuple,Arity,Dst}];
cg_instr(put_tuple_elements, Elements, _Dst) ->
    [{put,E} || E <- Elements];
cg_instr(raw_raise, Args, Dst) ->
    setup_args(Args) ++ [raw_raise|copy({x,0}, Dst)];
cg_instr(remove_message, [], _Dst) ->
    [remove_message];
cg_instr(resume, [A,B], _Dst) ->
    [{bif,raise,{f,0},[A,B],{x,0}}];
cg_instr(timeout, [], _Dst) ->
    [timeout].

cg_test(bs_add=Op, Fail, [Src1,Src2,{integer,Unit}], Dst, _I) ->
    [{Op,Fail,[Src1,Src2,Unit],Dst}];
cg_test(bs_skip, Fail, Args, _Dst, I) ->
    cg_bs_skip(Fail, Args, I);
cg_test(bs_utf8_size=Op, Fail, [Src], Dst, _I) ->
    [{Op,Fail,Src,Dst}];
cg_test(bs_utf16_size=Op, Fail, [Src], Dst, _I) ->
    [{Op,Fail,Src,Dst}];
cg_test({float,convert}, Fail, [Src], Dst, _I) ->
    {f,0} = Fail,                               %Assertion.
    [{fconv,Src,Dst}];
cg_test({float,Op0}, Fail, Args, Dst, #cg_set{anno=Anno}) ->
    Op = case Op0 of
             '+' -> fadd;
             '-' when length(Args) =:= 2 -> fsub;
             '-' -> fnegate;
             '*' -> fmul;
             '/' -> fdiv
         end,
    [line(Anno),{bif,Op,Fail,Args,Dst}];
cg_test(peek_message, Fail, [], Dst, _I) ->
    [{loop_rec,Fail,{x,0}}|copy({x,0}, Dst)];
cg_test(put_map, Fail, [{atom,exact},SrcMap|Ss], Dst, Set) ->
    Live = get_live(Set),
    [{put_map_exact,Fail,SrcMap,Dst,Live,{list,Ss}}];
cg_test(wait_timeout, Fail, [Timeout], _Dst, _) ->
    case Timeout of
        {atom,infinity} ->
            [{wait,Fail}];
        _ ->
            [{wait_timeout,Fail,Timeout}]
    end.

cg_bs_get(Fail, #cg_set{dst=Dst0,args=[#b_literal{val=Type}|Ss0]}=Set, St) ->
    Op = case Type of
             integer -> bs_get_integer2;
             float   -> bs_get_float2;
             binary  -> bs_get_binary2;
             utf8    -> bs_get_utf8;
             utf16   -> bs_get_utf16;
             utf32   -> bs_get_utf32
         end,
    [Dst|Ss1] = beam_args([Dst0|Ss0], St),
    Ss = case Ss1 of
             [Ctx,{literal,Flags},Size,{integer,Unit}] ->
                 %% Plain integer/float/binary.
                 [Ctx,Size,Unit,field_flags(Flags, Set)];
             [Ctx,{literal,Flags}] ->
                 %% Utf8/16/32.
                 [Ctx,field_flags(Flags, Set)]
         end,
    Live = get_live(Set),
    [{test,Op,Fail,Live,Ss,Dst}].

cg_bs_skip(Fail, [{atom,Type}|Ss0], Set) ->
    Op = case Type of
             utf8 -> bs_skip_utf8;
             utf16 -> bs_skip_utf16;
             utf32 -> bs_skip_utf32;
             _ -> bs_skip_bits2
         end,
    Live = get_live(Set),
    Ss = case Ss0 of
             [Ctx,{literal,Flags},Size,{integer,Unit}] ->
                 %% Plain integer/float/binary.
                 [Ctx,Size,Unit,field_flags(Flags, Set)];
             [Ctx,{literal,Flags}] ->
                 %% Utf8/16/32.
                 [Ctx,Live,field_flags(Flags, Set)]
         end,
    case {Type,Ss} of
        {binary,[_,{atom,all},1,_]} ->
            [];
        {binary,[R,{atom,all},U,_]} ->
            [{test,bs_test_unit,Fail,[R,U]}];
        {_,_} ->
            [{test,Op,Fail,Ss}]
    end.

field_flags(Flags, #cg_set{anno=#{location:={File,Line}}}) ->
    {field_flags,[{anno,[Line,{file,File}]}|Flags]};
field_flags(Flags, _) ->
    {field_flags,Flags}.

cg_bs_put(Fail, [{atom,Type},{literal,Flags}|Args]) ->
    Op = case Type of
             integer -> bs_put_integer;
             float   -> bs_put_float;
             binary  -> bs_put_binary;
             utf8    -> bs_put_utf8;
             utf16   -> bs_put_utf16;
             utf32   -> bs_put_utf32
         end,
    case Args of
        [Src,Size,{integer,Unit}] ->
            [{Op,Fail,Size,Unit,{field_flags,Flags},Src}];
        [Src] ->
            [{Op,Fail,{field_flags,Flags},Src}]
    end.

cg_bs_init(Dst, Size0, Alloc, Unit, Live, Fail) ->
    Op = case Unit of
             1 -> bs_init_bits;
             8 -> bs_init2
         end,
    Size = cg_bs_init_size(Size0),
    [{Op,Fail,Size,Alloc,Live,{field_flags,[]},Dst}].

cg_bs_init_size({x,_}=R) -> R;
cg_bs_init_size({y,_}=R) -> R;
cg_bs_init_size({integer,Int}) -> Int.

cg_catch(Agg, T0, Context, St0) ->
    {Moves,T1} = cg_extract(T0, Agg, St0),
    {T,St} = cg_block(T1, Context, St0),
    {Moves++T,St}.

cg_try(Agg, Tag, T0, Context, St0) ->
    {Moves0,T1} = cg_extract(T0, Agg, St0),
    Moves = order_moves(Moves0),
    [#cg_set{op=kill_try_tag}|T2] = T1,
    {T,St} = cg_block(T2, Context, St0),
    {[{try_case,Tag}|Moves++T],St}.

cg_extract([#cg_set{op=extract,dst=Dst0,args=Args0}|Is0], Agg, St) ->
    [Dst,Agg,{integer,X}] = beam_args([Dst0|Args0], St),
    {Ds,Is} = cg_extract(Is0, Agg, St),
    case keymember(Dst, 3, Ds) of
        true ->
            %% This destination will be overwritten.
            {Ds,Is};
        false ->
            {copy({x,X}, Dst)++Ds,Is}
    end;
cg_extract(Is, _, _) ->
    {[],Is}.

copy(Src, Src) -> [];
copy(Src, Dst) -> [{move,Src,Dst}].

force_reg({literal,_}=Lit, Reg) ->
    {Reg,[{move,Lit,Reg}]};
force_reg({integer,_}=Lit, Reg) ->
    {Reg,[{move,Lit,Reg}]};
force_reg({atom,_}=Lit, Reg) ->
    {Reg,[{move,Lit,Reg}]};
force_reg({float,_}=Lit, Reg) ->
    {Reg,[{move,Lit,Reg}]};
force_reg(nil=Lit, Reg) ->
    {Reg,[{move,Lit,Reg}]};
force_reg({Kind,_}=R, _) when Kind =:= x; Kind =:= y ->
    {R,[]}.

%% successors(Terminator) -> [Successor].
%%  Return an ordset of all successors for the given terminator.

successors(#cg_br{succ=Succ,fail=Fail}) ->
    ordsets:from_list([Succ,Fail]);
successors(#cg_switch{fail=Fail,list=List}) ->
    ordsets:from_list([Fail|[Lbl || {_,Lbl} <- List]]);
successors(#cg_ret{}) -> [].

%% linearize(Blocks) -> [{BlockLabel,#cg_blk{}}].
%%  Linearize the intermediate representation of the code. Also
%%  translate blocks from the SSA records to internal record types
%%  used only in this module.

linearize(Blocks) ->
    Linear = beam_ssa:linearize(Blocks),
    linearize_1(Linear, Blocks).

linearize_1([{?EXCEPTION_BLOCK,_}|Ls], Blocks) ->
    linearize_1(Ls, Blocks);
linearize_1([{L,Block0}|Ls], Blocks) ->
    Block = translate_block(L, Block0, Blocks),
    [{L,Block}|linearize_1(Ls, Blocks)];
linearize_1([], _Blocks) -> [].

%% translate_block(BlockLabel, #b_blk{}, Blocks) -> #cg_blk{}.
%%  Translate a block to the internal records used in this module.
%%  Also eliminate phi nodes, replacing them with 'copy' instructions
%%  in the predecessor blocks.

translate_block(L, #b_blk{anno=Anno,is=Is0,last=Last0}, Blocks) ->
    Last = translate_terminator(Last0),
    PhiCopies = translate_phis(L, Last, Blocks),
    Is1 = translate_is(Is0, PhiCopies),
    Is = case Anno of
             #{frame_size:=Size} ->
                 Alloc = #cg_alloc{stack=Size},
                 [Alloc|Is1];
             #{} -> Is1
         end,
    #cg_blk{anno=Anno,is=Is,last=Last}.

translate_is([#b_set{op=phi}|Is], Tail) ->
    translate_is(Is, Tail);
translate_is([#b_set{anno=Anno0,op=Op,dst=Dst,args=Args}=I|Is], Tail) ->
    Anno = case beam_ssa:clobbers_xregs(I) of
               true -> Anno0#{clobbers=>true};
               false -> Anno0
           end,
    [#cg_set{anno=Anno,op=Op,dst=Dst,args=Args}|translate_is(Is, Tail)];
translate_is([], Tail) -> Tail.

translate_terminator(#b_ret{anno=Anno,arg=Arg}) ->
    Dealloc = case Anno of
                  #{deallocate:=N} -> N;
                  #{} -> none
              end,
    #cg_ret{arg=Arg,dealloc=Dealloc};
translate_terminator(#b_br{bool=#b_literal{val=true},succ=Succ}) ->
    #cg_br{bool=#b_literal{val=true},succ=Succ,fail=Succ};
translate_terminator(#b_br{bool=#b_literal{val=false},fail=Fail}) ->
    #cg_br{bool=#b_literal{val=true},succ=Fail,fail=Fail};
translate_terminator(#b_br{bool=Bool,succ=Succ,fail=Fail}) ->
    #cg_br{bool=Bool,succ=Succ,fail=Fail};
translate_terminator(#b_switch{arg=Bool,fail=Fail,list=List}) ->
    #cg_switch{arg=Bool,fail=Fail,list=List}.

translate_phis(L, #cg_br{succ=Target,fail=Target}, Blocks) ->
    #b_blk{is=Is} = maps:get(Target, Blocks),
    Phis = takewhile(fun(#b_set{op=phi}) -> true;
                        (#b_set{}) -> false
                     end, Is),
    phi_copies(Phis, L);
translate_phis(_, _, _) -> [].

phi_copies([#b_set{dst=Dst,args=PhiArgs}|Sets], L) ->
    CopyArgs = [V || {V,Target} <- PhiArgs, Target =:= L],
    [#cg_set{op=copy,dst=Dst,args=CopyArgs}|phi_copies(Sets, L)];
phi_copies([], _) -> [].

%% opt_move_to_x0([Instruction]) -> [Instruction].
%%  Simple peep-hole optimization to move a {move,Any,{x,0}} past
%%  any kill up to the next call instruction. (To give the loader
%%  an opportunity to combine the 'move' and the 'call' instructions.)

opt_move_to_x0(Moves) ->
    opt_move_to_x0(Moves, []).

opt_move_to_x0([{move,_,{x,0}}=I|Is0], Acc0) ->
    case move_past_kill(Is0, I, Acc0) of
       impossible -> opt_move_to_x0(Is0, [I|Acc0]);
       {Is,Acc} -> opt_move_to_x0(Is, Acc)
    end;
opt_move_to_x0([I|Is], Acc) ->
    opt_move_to_x0(Is, [I|Acc]);
opt_move_to_x0([], Acc) -> reverse(Acc).

move_past_kill([{kill,Src}|_], {move,Src,_}, _) ->
    impossible;
move_past_kill([{kill,_}=I|Is], Move, Acc) ->
    move_past_kill(Is, Move, [I|Acc]);
move_past_kill(Is, Move, Acc) ->
    {Is,[Move|Acc]}.

%% setup_args(Args, Anno, Context) -> [Instruction].
%% setup_args(Args) -> [Instruction].
%%  Set up X registers for a call.

setup_args(Args, Anno, none, St) ->
    case {setup_args(Args),kill_yregs(Anno, St)} of
        {Moves,[]} ->
            Moves;
        {Moves,Kills} ->
            opt_move_to_x0(Moves ++ Kills)
    end;
setup_args(Args, _, _, _) ->
    setup_args(Args).

setup_args([]) ->
    [];
setup_args([_|_]=Args) ->
    Moves = gen_moves(Args, 0, []),
    order_moves(Moves).

%% kill_yregs(Anno, #cg{}) -> [{kill,{y,Y}}].
%%  Kill Y registers that will not be used again.

kill_yregs(#{kill_yregs:=Kill}, #cg{regs=Regs}) ->
    ordsets:from_list([{kill,maps:get(V, Regs)} || V <- Kill]);
kill_yregs(#{}, #cg{}) -> [].

%% gen_moves(As, I, Acc)
%%  Generate the basic move instruction to move the arguments
%%  to their proper registers. The list will be sorted on
%%  destinations. (I.e. the move to {x,0} will be first --
%%  see the comment to order_moves/2.)

gen_moves([A|As], I, Acc) ->
    gen_moves(As, I+1, copy(A, {x,I}) ++ Acc);
gen_moves([], _, Acc) ->
    keysort(3, Acc).

%% order_moves([Move]) -> [Move]
%%  Orders move instruction so that source registers are not
%%  destroyed before they are used. If there are cycles
%%  (such as {move,{x,0},{x,1}}, {move,{x,1},{x,1}}),
%%  swap instructions will be used to break up the cycle.
%%
%%  If possible, the first move of the input list is placed
%%  last in the result list (to make the move to {x,0} occur
%%  just before the call to allow the Beam loader to coalesce
%%  the instructions).

order_moves(Ms) -> order_moves(Ms, []).

order_moves([{move,_,_}=M|Ms0], Acc0) ->
    {Chain,Ms} = collect_chain(Ms0, [M]),
    Acc = reverse(Chain, Acc0),
    order_moves(Ms, Acc);
order_moves([], Acc) -> Acc.

collect_chain(Ms, Path) ->
    collect_chain(Ms, Path, []).

collect_chain([{move,Src,Same}=M|Ms0], [{move,Same,_}|_]=Path, Others) ->
    case keymember(Src, 3, Path) of
        false ->
            collect_chain(reverse(Others, Ms0), [M|Path], []);
        true ->
            %% There is a cycle.
            {break_up_cycle(M, Path),reverse(Others, Ms0)}
    end;
collect_chain([M|Ms], Path, Others) ->
    collect_chain(Ms, Path, [M|Others]);
collect_chain([], Path, Others) ->
    {Path,Others}.

break_up_cycle({move,Src,_Dst}=M, Path) ->
    break_up_cycle_1(Src, [M|Path], []).

break_up_cycle_1(Dst, [{move,_Src,Dst}|Path], Acc) ->
    reverse(Acc, Path);
break_up_cycle_1(Dst, [{move,S,D}|Path], Acc) ->
    break_up_cycle_1(Dst, Path, [{swap,S,D}|Acc]).

%%%
%%% General utility functions.
%%%

verify_beam_register({x,_}=Reg) -> Reg.

is_beam_register({x,_}) -> true;
is_beam_register(_) -> false.

get_register(V, Regs) ->
    case is_beam_register(V) of
        true -> V;
        false -> maps:get(V, Regs)
    end.

beam_args(As, St) ->
    [beam_arg(A, St) || A <- As].

beam_arg(#b_var{}=Name, #cg{regs=Regs}) ->
    maps:get(Name, Regs);
beam_arg(#b_literal{val=Val}, _) ->
    if
        is_atom(Val) -> {atom,Val};
        is_float(Val) -> {float,Val};
        is_integer(Val) -> {integer,Val};
        Val =:= [] -> nil;
        true -> {literal,Val}
    end;
beam_arg(Reg, _) ->
    verify_beam_register(Reg).

new_block_label(L, St0) ->
    {_Lbl,St} = label_for_block(L, St0),
    St.

def_block_label(L, #cg{labels=Labels,used_labels=Used}) ->
    Lbl = maps:get(L, Labels),
    case gb_sets:is_member(Lbl, Used) of
        false -> [];
        true -> [{label,Lbl}]
    end.

use_block_labels(Ls, St) ->
    mapfoldl(fun use_block_label/2, St, Ls).

use_block_label(L, #cg{used_labels=Used,catches=Catches}=St0) ->
    {Lbl,St} = label_for_block(L, St0),
    case gb_sets:is_member(L, Catches) of
        true ->
            {{catch_tag,{f,Lbl}},
             St#cg{used_labels=gb_sets:add(Lbl, Used)}};
        false ->
            {{f,Lbl},St#cg{used_labels=gb_sets:add(Lbl, Used)}}
    end.

label_for_block(L, #cg{labels=Labels0}=St0) ->
    case Labels0 of
        #{L:=Lbl} ->
            {Lbl,St0};
        #{} ->
            {Lbl,St} = new_label(St0),
            Labels = Labels0#{L=>Lbl},
            {Lbl,St#cg{labels=Labels}}
    end.

%% local_func_label(Name, Arity, State) -> {Label,State'}
%% local_func_label({Name,Arity}, State) -> {Label,State'}
%%  Get the function entry label for a local function.

local_func_label(Name, Arity, St) ->
    local_func_label({Name,Arity}, St).

local_func_label(Key, #cg{functable=Map}=St0) ->
    case Map of
       #{Key := Label} ->
            {Label,St0};
        _ ->
            {Label,St} = new_label(St0),
            {Label,St#cg{functable=Map#{Key => Label}}}
    end.

%% is_gc_bif(Name, Args) -> true|false.
%%  Determines whether the BIF Name/Arity might do a GC.

-spec is_gc_bif(atom(), [beam_ssa:value()]) -> boolean().

is_gc_bif(hd, [_]) -> false;
is_gc_bif(tl, [_]) -> false;
is_gc_bif(self, []) -> false;
is_gc_bif(node, []) -> false;
is_gc_bif(node, [_]) -> false;
is_gc_bif(element, [_,_]) -> false;
is_gc_bif(get, [_]) -> false;
is_gc_bif(is_map_key, [_,_]) -> false;
is_gc_bif(map_get, [_,_]) -> false;
is_gc_bif(tuple_size, [_]) -> false;
is_gc_bif(Bif, Args) ->
    Arity = length(Args),
    not (erl_internal:bool_op(Bif, Arity) orelse
	 erl_internal:new_type_test(Bif, Arity) orelse
	 erl_internal:comp_op(Bif, Arity)).

%% new_label(St) -> {L,St}.

new_label(#cg{lcount=Next}=St) ->
    {Next,St#cg{lcount=Next+1}}.

%% call_line(tail|body, Func, Anno) -> [] | [{line,...}].
%%  Produce a line instruction if it will be needed by the
%%  call to Func.

call_line(_Context, {extfunc,Mod,Name,Arity}, Anno) ->
    case erl_bifs:is_safe(Mod, Name, Arity) of
	false ->
	    %% The call could be to a BIF.
	    %% We'll need a line instruction in case the
	    %% BIF call fails.
	    [line(Anno)];
	true ->
	    %% Call to a safe BIF. Since it cannot fail,
	    %% we don't need any line instruction here.
	    []
    end;
call_line(body, _, Anno) ->
    [line(Anno)];
call_line(tail, local, _) ->
    %% Tail-recursive call to a local function. A line
    %% instruction will not be useful.
    [];
call_line(tail, _, Anno) ->
    %% Call to a fun.
    [line(Anno)].

%% line(Le) -> {line,[] | {location,File,Line}}
%%  Create a line instruction, containing information about
%%  the current filename and line number. A line information
%%  instruction should be placed before any operation that could
%%  cause an exception.

line(#{location:={File,Line}}) ->
    {line,[{location,File,Line}]};
line(#{}) ->
    {line,[]}.

flatmapfoldl(F, Accu0, [Hd|Tail]) ->
    {R,Accu1} = F(Hd, Accu0),
    {Rs,Accu2} = flatmapfoldl(F, Accu1, Tail),
    {R++Rs,Accu2};
flatmapfoldl(_, Accu, []) -> {[],Accu}.