1%%
2%% %CopyrightBegin%
3%%
4%% Copyright Ericsson AB 2018-2020. All Rights Reserved.
5%%
6%% Licensed under the Apache License, Version 2.0 (the "License");
7%% you may not use this file except in compliance with the License.
8%% You may obtain a copy of the License at
9%%
10%%     http://www.apache.org/licenses/LICENSE-2.0
11%%
12%% Unless required by applicable law or agreed to in writing, software
13%% distributed under the License is distributed on an "AS IS" BASIS,
14%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15%% See the License for the specific language governing permissions and
16%% limitations under the License.
17%%
18%% %CopyrightEnd%
19%%
20%% Purpose: Type definitions and utilities for the SSA format.
21
22-module(beam_ssa).
23-export([add_anno/3,get_anno/2,get_anno/3,
24         between/4,
25         clobbers_xregs/1,def/2,def_unused/3,
26         definitions/2,
27         dominators/2,dominators_from_predecessors/2,common_dominators/3,
28         flatmapfold_instrs/4,
29         fold_blocks/4,
30         fold_instrs/4,
31         insert_on_edges/3,
32         is_loop_header/1,
33         linearize/1,
34         mapfold_blocks/4,
35         mapfold_instrs/4,
36         merge_blocks/2,
37         normalize/1,
38         no_side_effect/1,
39         predecessors/1,
40         rename_vars/3,
41         rpo/1,rpo/2,
42         split_blocks/4,
43         successors/1,successors/2,
44         trim_unreachable/1,
45         used/1,uses/2]).
46
47-export_type([b_module/0,b_function/0,b_blk/0,b_set/0,
48              b_ret/0,b_br/0,b_switch/0,terminator/0,
49              b_var/0,b_literal/0,b_remote/0,b_local/0,
50              value/0,argument/0,label/0,
51              var_name/0,var_base/0,literal_value/0,
52              op/0,anno/0,block_map/0,dominator_map/0,
53              rename_map/0,rename_proplist/0,usage_map/0,
54              definition_map/0,predecessor_map/0]).
55
56-include("beam_ssa.hrl").
57
58-type b_module()   :: #b_module{}.
59-type b_function() :: #b_function{}.
60-type b_blk()      :: #b_blk{}.
61-type b_set()      :: #b_set{}.
62
63-type b_br()       :: #b_br{}.
64-type b_ret()      :: #b_ret{}.
65-type b_switch()   :: #b_switch{}.
66-type terminator() :: b_br() | b_ret() | b_switch().
67
68-type construct()  :: b_module() | b_function() | b_blk() | b_set() |
69                      terminator().
70
71-type b_var()      :: #b_var{}.
72-type b_literal()  :: #b_literal{}.
73-type b_remote()   :: #b_remote{}.
74-type b_local()    :: #b_local{}.
75
76-type value()      :: b_var() | b_literal().
77-type phi_value()  :: {value(),label()}.
78-type argument()   :: value() | b_remote() | b_local() | phi_value().
79-type label()      :: non_neg_integer().
80
81-type var_name()   :: var_base() | {var_base(),non_neg_integer()}.
82-type var_base()   :: atom() | non_neg_integer().
83
84-type literal_value() :: atom() | integer() | float() | list() |
85                         nil() | tuple() | map() | binary() | fun().
86
87-type op()   :: {'bif',atom()} |
88                {'float',float_op()} |
89                {'succeeded', 'guard' | 'body'} |
90                prim_op() |
91                cg_prim_op().
92
93-type anno() :: #{atom() := any()}.
94
95-type block_map() :: #{label():=b_blk()}.
96-type dominator_map() :: #{label():=[label()]}.
97-type numbering_map() :: #{label():=non_neg_integer()}.
98-type usage_map() :: #{b_var():=[{label(),b_set() | terminator()}]}.
99-type definition_map() :: #{b_var():=b_set()}.
100-type predecessor_map() :: #{label():=[label()]}.
101-type rename_map() :: #{b_var():=value()}.
102-type rename_proplist() :: [{b_var(),value()}].
103
104%% Note: By default, dialyzer will collapse this type to atom().
105%% To avoid the collapsing, change the value of SET_LIMIT to 50 in the
106%% file erl_types.erl in the dialyzer application.
107
108-type prim_op() :: 'bs_add' | 'bs_extract' | 'bs_get_tail' |
109                   'bs_init' | 'bs_init_writable' |
110                   'bs_match' | 'bs_put' | 'bs_start_match' | 'bs_test_tail' |
111                   'bs_utf16_size' | 'bs_utf8_size' | 'build_stacktrace' |
112                   'call' | 'catch_end' |
113                   'extract' |
114                   'get_hd' | 'get_map_element' | 'get_tl' | 'get_tuple_element' |
115                   'has_map_field' |
116                   'is_nonempty_list' | 'is_tagged_tuple' |
117                   'kill_try_tag' |
118                   'landingpad' |
119                   'make_fun' | 'new_try_tag' | 'old_make_fun' |
120                   'peek_message' | 'phi' | 'put_list' | 'put_map' | 'put_tuple' |
121                   'raw_raise' | 'recv_next' | 'remove_message' | 'resume' |
122                   'wait_timeout'.
123
124-type float_op() :: 'checkerror' | 'clearerror' | 'convert' | 'get' | 'put' |
125                    '+' | '-' | '*' | '/'.
126
127%% Primops only used internally during code generation.
128-type cg_prim_op() :: 'bs_get' | 'bs_get_position' | 'bs_match_string' |
129                      'bs_restore' | 'bs_save' | 'bs_set_position' | 'bs_skip' |
130                      'copy' | 'match_fail' | 'put_tuple_arity' |
131                      'put_tuple_element' | 'put_tuple_elements' |
132                      'set_tuple_element' | 'succeeded'.
133
134-import(lists, [foldl/3,mapfoldl/3,member/2,reverse/1,sort/1]).
135
136-spec add_anno(Key, Value, Construct) -> Construct when
137      Key :: atom(),
138      Value :: any(),
139      Construct :: construct().
140
141add_anno(Key, Val, #b_function{anno=Anno}=Bl) ->
142    Bl#b_function{anno=Anno#{Key=>Val}};
143add_anno(Key, Val, #b_blk{anno=Anno}=Bl) ->
144    Bl#b_blk{anno=Anno#{Key=>Val}};
145add_anno(Key, Val, #b_set{anno=Anno}=Bl) ->
146    Bl#b_set{anno=Anno#{Key=>Val}};
147add_anno(Key, Val, #b_br{anno=Anno}=Bl) ->
148    Bl#b_br{anno=Anno#{Key=>Val}};
149add_anno(Key, Val, #b_ret{anno=Anno}=Bl) ->
150    Bl#b_ret{anno=Anno#{Key=>Val}};
151add_anno(Key, Val, #b_switch{anno=Anno}=Bl) ->
152    Bl#b_switch{anno=Anno#{Key=>Val}}.
153
154-spec get_anno(atom(), construct()) -> any().
155
156get_anno(Key, Construct) ->
157    map_get(Key, get_anno(Construct)).
158
159-spec get_anno(atom(), construct(),any()) -> any().
160
161get_anno(Key, Construct, Default) ->
162    maps:get(Key, get_anno(Construct), Default).
163
164get_anno(#b_function{anno=Anno}) -> Anno;
165get_anno(#b_blk{anno=Anno}) -> Anno;
166get_anno(#b_set{anno=Anno}) -> Anno;
167get_anno(#b_br{anno=Anno}) -> Anno;
168get_anno(#b_ret{anno=Anno}) -> Anno;
169get_anno(#b_switch{anno=Anno}) -> Anno.
170
171%% clobbers_xregs(#b_set{}) -> true|false.
172%%  Test whether the instruction invalidates all X registers.
173
174-spec clobbers_xregs(b_set()) -> boolean().
175
176clobbers_xregs(#b_set{op=Op}) ->
177    case Op of
178        bs_init_writable -> true;
179        build_stacktrace -> true;
180        call -> true;
181        landingpad -> true;
182        old_make_fun -> true;
183        peek_message -> true;
184        raw_raise -> true;
185        wait_timeout -> true;
186        _ -> false
187    end.
188
189%% no_side_effect(#b_set{}) -> true|false.
190%%  Test whether this instruction has no side effect and thus is safe
191%%  not to execute if its value is not used. Note that even if `true`
192%%  is returned, the instruction could still be impure (e.g. bif:get).
193
194-spec no_side_effect(b_set()) -> boolean().
195
196no_side_effect(#b_set{op=Op}) ->
197    case Op of
198        {bif,_} -> true;
199        {float,get} -> true;
200        bs_add -> true;
201        bs_init -> true;
202        bs_init_writable -> true;
203        bs_extract -> true;
204        bs_match -> true;
205        bs_start_match -> true;
206        bs_test_tail -> true;
207        bs_get_tail -> true;
208        bs_put -> true;
209        bs_utf16_size -> true;
210        bs_utf8_size -> true;
211        build_stacktrace -> true;
212        extract -> true;
213        get_hd -> true;
214        get_tl -> true;
215        get_map_element -> true;
216        get_tuple_element -> true;
217        has_map_field -> true;
218        is_nonempty_list -> true;
219        is_tagged_tuple -> true;
220        make_fun -> true;
221        phi -> true;
222        put_map -> true;
223        put_list -> true;
224        put_tuple -> true;
225        {succeeded,guard} -> true;
226        _ -> false
227    end.
228
229%% insert_on_edges(Insertions, BlockMap, Count) -> {BlockMap, Count}.
230%%  Inserts instructions on the specified normal edges. It will not work on
231%%  exception edges.
232%%
233%%  That is, `[{12, 34, [CallInstr]}]` will insert `CallInstr` on all jumps
234%%  from block 12 to block 34.
235-spec insert_on_edges(Insertions, Blocks, Count) -> Result when
236    Insertions :: [{From, To, Is}],
237    From :: label(),
238    To :: label(),
239    Is :: [b_set()],
240    Blocks :: block_map(),
241    Count :: label(),
242    Result :: {block_map(), label()}.
243
244insert_on_edges(Insertions, Blocks, Count) ->
245    %% Sort insertions to simplify the handling of duplicates.
246    insert_on_edges_1(sort(Insertions), Blocks, Count).
247
248insert_on_edges_1([{_, ?EXCEPTION_BLOCK, _} | _], _, _) ->
249    %% Internal error; we can't run code on specific exception edges without
250    %% adding try/catch everywhere. Passes must avoid this.
251    error(unsafe_edge);
252insert_on_edges_1([{From, To, IsA}, {From, To, IsB} | Insertions],
253                  Blocks, Count) ->
254    %% Join duplicate insertions into the same block so we won't have to track
255    %% which edges we've already inserted code on.
256    insert_on_edges_1([{From, To, IsA ++ IsB} | Insertions], Blocks, Count);
257insert_on_edges_1([{From, To, Is} | Insertions], Blocks0, Count0) ->
258    #b_blk{last=FromLast0} = FromBlk0 = map_get(From, Blocks0),
259    #b_blk{is=ToIs0} = ToBlk0 = map_get(To, Blocks0),
260
261    EdgeLbl = Count0,
262    Count = Count0 + 1,
263
264    FromLast = insert_on_edges_reroute(FromLast0, To, EdgeLbl),
265    FromBlk = FromBlk0#b_blk{last=FromLast},
266
267    {EdgeIs0, ToIs} = insert_on_edges_is(ToIs0, From, EdgeLbl, []),
268    EdgeIs = EdgeIs0 ++ Is,
269
270    Br = #b_br{bool=#b_literal{val=true},
271               succ=To,
272               fail=To},
273
274    EdgeBlk = #b_blk{is=EdgeIs,last=Br},
275    ToBlk = ToBlk0#b_blk{is=ToIs},
276
277    Blocks1 = Blocks0#{ EdgeLbl => EdgeBlk,
278                        From := FromBlk,
279                        To := ToBlk },
280    Blocks = update_phi_labels([To], From, EdgeLbl, Blocks1),
281
282    insert_on_edges_1(Insertions, Blocks, Count);
283insert_on_edges_1([], Blocks, Count) ->
284    {Blocks, Count}.
285
286insert_on_edges_reroute(#b_switch{fail=Fail0,list=List0}=Sw, Old, New) ->
287    Fail = rename_label(Fail0, Old, New),
288    List = [{Value, rename_label(Dst, Old, New)} || {Value, Dst} <- List0],
289    Sw#b_switch{fail=Fail,list=List};
290insert_on_edges_reroute(#b_br{succ=Succ0,fail=Fail0}=Br, Old, New) ->
291    Succ = rename_label(Succ0, Old, New),
292    Fail = rename_label(Fail0, Old, New),
293    Br#b_br{succ=Succ,fail=Fail}.
294
295insert_on_edges_is([#b_set{op=bs_extract}=I | Is], FromLbl, EdgeLbl, EdgeIs) ->
296    %% Bit-syntax instructions span across edges, so we must hoist them into
297    %% the edge block to avoid breaking them.
298    %%
299    %% This is safe because we *KNOW* that there are no other edges leading to
300    %% this block.
301    insert_on_edges_is(Is, FromLbl, EdgeLbl, [I | EdgeIs]);
302insert_on_edges_is(ToIs0, FromLbl, EdgeLbl, EdgeIs) ->
303    case ToIs0 of
304        [#b_set{op=landingpad} | _] ->
305            %% We can't run code on specific exception edges without adding
306            %% try/catch everywhere. Passes must avoid this.
307            error(unsafe_edge);
308        _ ->
309            ToIs = update_phi_labels_is(ToIs0, FromLbl, EdgeLbl),
310            {reverse(EdgeIs), ToIs}
311    end.
312
313%% is_loop_header(#b_set{}) -> true|false.
314%%  Test whether this instruction is a loop header.
315
316-spec is_loop_header(b_set()) -> boolean().
317
318is_loop_header(#b_set{op=wait_timeout,args=[Args]}) ->
319    case Args of
320        #b_literal{val=0} ->
321            %% Never jumps back to peek_message
322            false;
323        _ ->
324            true
325    end;
326is_loop_header(#b_set{op=Op}) ->
327    Op =:= peek_message.
328
329-spec predecessors(Blocks) -> Result when
330      Blocks :: block_map(),
331      Result :: predecessor_map().
332
333predecessors(Blocks) ->
334    P0 = [{S,L} || {L,Blk} <- maps:to_list(Blocks),
335                   S <- successors(Blk)],
336    P1 = sofs:relation(P0),
337    P2 = sofs:rel2fam(P1),
338    P3 = sofs:to_external(P2),
339    P = [{0,[]}|P3],
340    maps:from_list(P).
341
342-spec successors(b_blk()) -> [label()].
343
344successors(#b_blk{last=Terminator}) ->
345    case Terminator of
346        #b_br{bool=#b_literal{val=true},succ=Succ} ->
347            [Succ];
348        #b_br{bool=#b_literal{val=false},fail=Fail} ->
349            [Fail];
350        #b_br{succ=Succ,fail=Fail} ->
351            [Fail,Succ];
352        #b_switch{fail=Fail,list=List} ->
353            [Fail|[L || {_,L} <- List]];
354        #b_ret{} ->
355            []
356    end.
357
358%% normalize(Instr0) -> Instr.
359%%  Normalize instructions to help optimizations.
360%%
361%%  For commutative operators (such as '+' and 'or'), always
362%%  place a variable operand before a literal operand.
363%%
364%%  Normalize #b_br{} to one of the following forms:
365%%
366%%    #b_br{b_literal{val=true},succ=Label,fail=Label}
367%%    #b_br{b_var{},succ=Label1,fail=Label2} where Label1 =/= Label2
368%%
369%%  Simplify a #b_switch{} with a literal argument to a #b_br{}.
370%%
371%%  Simplify a #b_switch{} with a variable argument and an empty
372%%  switch list to a #b_br{}.
373
374-spec normalize(b_set() | terminator()) ->
375                       b_set() | terminator().
376
377normalize(#b_set{op={bif,Bif},args=Args}=Set) ->
378    case {is_commutative(Bif),Args} of
379        {false,_} ->
380            Set;
381        {true,[#b_literal{}=Lit,#b_var{}=Var]} ->
382            Set#b_set{args=[Var,Lit]};
383        {true,_} ->
384            Set
385    end;
386normalize(#b_set{}=Set) ->
387    Set;
388normalize(#b_br{}=Br) ->
389    case Br of
390        #b_br{bool=Bool,succ=Same,fail=Same} ->
391            case Bool of
392                #b_literal{val=true} ->
393                    Br;
394                _ ->
395                    Br#b_br{bool=#b_literal{val=true}}
396            end;
397        #b_br{bool=#b_literal{val=true},succ=Succ} ->
398            Br#b_br{fail=Succ};
399        #b_br{bool=#b_literal{val=false},fail=Fail} ->
400            Br#b_br{bool=#b_literal{val=true},succ=Fail};
401        #b_br{} ->
402            Br
403    end;
404normalize(#b_switch{arg=Arg,fail=Fail,list=List}=Sw) ->
405    case Arg of
406        #b_literal{} ->
407            normalize_switch(Arg, List, Fail);
408        #b_var{} when List =:= [] ->
409            #b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail};
410        #b_var{} ->
411            Sw#b_switch{list=sort(List)}
412    end;
413normalize(#b_ret{}=Ret) ->
414    Ret.
415
416normalize_switch(Val, [{Val,L}|_], _Fail) ->
417    #b_br{bool=#b_literal{val=true},succ=L,fail=L};
418normalize_switch(Val, [_|T], Fail) ->
419    normalize_switch(Val, T, Fail);
420normalize_switch(_Val, [], Fail) ->
421    #b_br{bool=#b_literal{val=true},succ=Fail,fail=Fail}.
422
423-spec successors(label(), block_map()) -> [label()].
424
425successors(L, Blocks) ->
426    successors(map_get(L, Blocks)).
427
428-spec def(Ls, Blocks) -> Def when
429      Ls :: [label()],
430      Blocks :: block_map(),
431      Def :: ordsets:ordset(var_name()).
432
433def(Ls, Blocks) ->
434    Blks = [map_get(L, Blocks) || L <- Ls],
435    def_1(Blks, []).
436
437-spec def_unused(Ls, Used, Blocks) -> {Def,Unused} when
438      Ls :: [label()],
439      Used :: ordsets:ordset(var_name()),
440      Blocks :: block_map(),
441      Def :: ordsets:ordset(var_name()),
442      Unused :: ordsets:ordset(var_name()).
443
444def_unused(Ls, Unused, Blocks) ->
445    Blks = [map_get(L, Blocks) || L <- Ls],
446    Preds = sets:from_list(Ls, [{version, 2}]),
447    def_unused_1(Blks, Preds, [], Unused).
448
449%% dominators(Labels, BlockMap) -> {Dominators,Numbering}.
450%%  Calculate the dominator tree, returning a map where each entry
451%%  in the map is a list that gives the path from that block to
452%%  the top of the dominator tree. (Note that the suffixes of the
453%%  paths are shared with each other, which make the representation
454%%  of the dominator tree highly memory-efficient.)
455%%
456%%  The implementation is based on:
457%%
458%%     http://www.hipersoft.rice.edu/grads/publications/dom14.pdf
459%%     Cooper, Keith D.; Harvey, Timothy J; Kennedy, Ken (2001).
460%%        A Simple, Fast Dominance Algorithm.
461
462-spec dominators(Labels, Blocks) -> Result when
463      Labels :: [label()],
464      Blocks :: block_map(),
465      Result :: {dominator_map(), numbering_map()}.
466dominators(Labels, Blocks) ->
467    Preds = predecessors(Blocks),
468    dominators_from_predecessors(Labels, Preds).
469
470-spec dominators_from_predecessors(Labels, Preds) -> Result when
471      Labels :: [label()],
472      Preds :: predecessor_map(),
473      Result :: {dominator_map(), numbering_map()}.
474dominators_from_predecessors(Top0, Preds) ->
475    Df = maps:from_list(number(Top0, 0)),
476    [{0,[]}|Top] = [{L,map_get(L, Preds)} || L <- Top0],
477
478    %% The flow graph for an Erlang function is reducible, and
479    %% therefore one traversal in reverse postorder is sufficient.
480    Acc = #{0=>[0]},
481    {dominators_1(Top, Df, Acc),Df}.
482
483%% common_dominators([Label], Dominators, Numbering) -> [Label].
484%%  Calculate the common dominators for the given list of blocks
485%%  and Dominators and Numbering as returned from dominators/1.
486
487-spec common_dominators([label()], dominator_map(), numbering_map()) -> [label()].
488common_dominators(Ls, Dom, Numbering) ->
489    Doms = [map_get(L, Dom) || L <- Ls],
490    dom_intersection(Doms, Numbering).
491
492-spec fold_instrs(Fun, Labels, Acc0, Blocks) -> any() when
493      Fun :: fun((b_blk()|terminator(), any()) -> any()),
494      Labels :: [label()],
495      Acc0 :: any(),
496      Blocks :: block_map().
497
498fold_instrs(Fun, Labels, Acc0, Blocks) ->
499    fold_instrs_1(Labels, Fun, Blocks, Acc0).
500
501%% mapfold_blocks(Fun, [Label], Acc, BlockMap) -> {BlockMap,Acc}.
502%%  Like mapfold_instrs but at the block level to support lookahead
503%%  and scope-dependent transformations.
504
505-spec mapfold_blocks(Fun, Labels, Acc, Blocks) -> Result when
506      Fun :: fun((label(), b_blk(), any()) -> {b_blk(), any()}),
507      Labels :: [label()],
508      Acc :: any(),
509      Blocks :: block_map(),
510      Result :: {block_map(), any()}.
511mapfold_blocks(Fun, Labels, Acc, Blocks) ->
512    foldl(fun(Lbl, A) ->
513                  mapfold_blocks_1(Fun, Lbl, A)
514          end, {Blocks, Acc}, Labels).
515
516mapfold_blocks_1(Fun, Lbl, {Blocks0, Acc0}) ->
517    Block0 = map_get(Lbl, Blocks0),
518    {Block, Acc} = Fun(Lbl, Block0, Acc0),
519    Blocks = Blocks0#{Lbl:=Block},
520    {Blocks, Acc}.
521
522-spec mapfold_instrs(Fun, Labels, Acc0, Blocks0) -> {Blocks,Acc} when
523      Fun :: fun((b_blk()|terminator(), any()) -> any()),
524      Labels :: [label()],
525      Acc0 :: any(),
526      Acc :: any(),
527      Blocks0 :: block_map(),
528      Blocks :: block_map().
529
530mapfold_instrs(Fun, Labels, Acc0, Blocks) ->
531    mapfold_instrs_1(Labels, Fun, Blocks, Acc0).
532
533-spec flatmapfold_instrs(Fun, Labels, Acc0, Blocks0) -> {Blocks,Acc} when
534      Fun :: fun((b_blk()|terminator(), any()) -> any()),
535      Labels :: [label()],
536      Acc0 :: any(),
537      Acc :: any(),
538      Blocks0 :: block_map(),
539      Blocks :: block_map().
540
541flatmapfold_instrs(Fun, Labels, Acc0, Blocks) ->
542    flatmapfold_instrs_1(Labels, Fun, Blocks, Acc0).
543
544-type fold_fun() :: fun((label(), b_blk(), any()) -> any()).
545
546%% fold_blocks(Fun, [Label], Acc0, Blocks) -> Acc.  Fold over all blocks
547%%  from a given set of labels in a reverse postorder traversal of the
548%%  block graph; that is, first visit a block, then visit its successors.
549
550-spec fold_blocks(Fun, Labels, Acc0, Blocks) -> any() when
551      Fun :: fold_fun(),
552      Labels :: [label()],
553      Acc0 :: any(),
554      Blocks :: #{label():=b_blk()}.
555
556fold_blocks(Fun, Labels, Acc0, Blocks) ->
557    fold_blocks_1(Labels, Fun, Blocks, Acc0).
558
559%% linearize(Blocks) -> [{BlockLabel,#b_blk{}}].
560%%  Linearize the intermediate representation of the code.
561%%  Unreachable blocks will be discarded, and phi nodes will
562%%  be adjusted so that they no longer refers to discarded
563%%  blocks or to blocks that no longer are predecessors of
564%%  the phi node block.
565
566-spec linearize(Blocks) -> Linear when
567      Blocks :: block_map(),
568      Linear :: [{label(),b_blk()}].
569
570linearize(Blocks) ->
571    Seen = sets:new([{version, 2}]),
572    {Linear0,_} = linearize_1([0], Blocks, Seen, []),
573    Linear = fix_phis(Linear0, #{}),
574    Linear.
575
576-spec rpo(Blocks) -> [Label] when
577      Blocks :: block_map(),
578      Label :: label().
579
580rpo(Blocks) ->
581    rpo([0], Blocks).
582
583-spec rpo(From, Blocks) -> Labels when
584      From :: [label()],
585      Blocks :: block_map(),
586      Labels :: [label()].
587
588rpo(From, Blocks) ->
589    Seen = sets:new([{version, 2}]),
590    {Ls,_} = rpo_1(From, Blocks, Seen, []),
591    Ls.
592
593%% between(From, To, Preds, Blocks) -> RPO
594%%  Returns all the blocks between `From` and `To` in reverse post-order. This
595%%  is most efficient when `From` dominates `To`, as it won't visit any
596%%  unnecessary blocks in that case.
597
598-spec between(From, To, Preds, Blocks) -> Labels when
599      From :: label(),
600      To :: label(),
601      Preds :: predecessor_map(),
602      Blocks :: block_map(),
603      Labels :: [label()].
604
605between(From, To, Preds, Blocks) ->
606    %% Gather the predecessors of `To` and then walk forward from `From`,
607    %% skipping the blocks that don't precede `To`.
608    %%
609    %% As an optimization we initialize the predecessor set with `From` to stop
610    %% gathering once seen since we're only interested in the blocks inbetween.
611    %% Uninteresting blocks can still be added if `From` doesn't dominate `To`,
612    %% but that has no effect on the final result.
613    Filter = between_make_filter([To], Preds, sets:from_list([From], [{version, 2}])),
614    {Paths, _} = between_rpo([From], Blocks, Filter, []),
615
616    Paths.
617
618-spec rename_vars(Rename, [label()], block_map()) -> block_map() when
619      Rename :: rename_map() | rename_proplist().
620
621rename_vars(Rename, Labels, Blocks) when is_list(Rename) ->
622    rename_vars(maps:from_list(Rename), Labels, Blocks);
623rename_vars(Rename, Labels, Blocks) when is_map(Rename)->
624    Preds = sets:from_list(Labels, [{version, 2}]),
625    F = fun(#b_set{op=phi,args=Args0}=Set) ->
626                Args = rename_phi_vars(Args0, Preds, Rename),
627                normalize(Set#b_set{args=Args});
628           (#b_set{args=Args0}=Set) ->
629                Args = [rename_var(A, Rename) || A <- Args0],
630                normalize(Set#b_set{args=Args});
631           (#b_switch{arg=Bool}=Sw) ->
632                normalize(Sw#b_switch{arg=rename_var(Bool, Rename)});
633           (#b_br{bool=Bool}=Br) ->
634                normalize(Br#b_br{bool=rename_var(Bool, Rename)});
635           (#b_ret{arg=Arg}=Ret) ->
636                normalize(Ret#b_ret{arg=rename_var(Arg, Rename)})
637        end,
638    map_instrs_1(Labels, F, Blocks).
639
640%% split_blocks(Predicate, Blocks0, Count0) -> {Blocks,Count}.
641%%  Call Predicate(Instruction) for each instruction in all
642%%  blocks. If Predicate/1 returns true, split the block
643%%  before this instruction.
644
645-spec split_blocks(Labels, Pred, Blocks0, Count0) -> {Blocks,Count} when
646      Labels :: [label()],
647      Pred :: fun((b_set()) -> boolean()),
648      Blocks :: block_map(),
649      Count0 :: label(),
650      Blocks0 :: block_map(),
651      Blocks :: block_map(),
652      Count :: label().
653
654split_blocks(Ls, P, Blocks, Count) ->
655    split_blocks_1(Ls, P, Blocks, Count).
656
657-spec trim_unreachable(SSA0) -> SSA when
658      SSA0 :: block_map() | [{label(),b_blk()}],
659      SSA :: block_map() | [{label(),b_blk()}].
660
661%% trim_unreachable(Blocks0) -> Blocks.
662%%  Remove all unreachable blocks. Adjust all phi nodes so
663%%  they don't refer to blocks that has been removed or no
664%%  no longer branch to the phi node in question.
665
666trim_unreachable(Blocks) when is_map(Blocks) ->
667    %% Could perhaps be optimized if there is any need.
668    maps:from_list(linearize(Blocks));
669trim_unreachable([_|_]=Blocks) ->
670    trim_unreachable_1(Blocks, sets:from_list([0], [{version, 2}])).
671
672-spec used(b_blk() | b_set() | terminator()) -> [var_name()].
673
674used(#b_blk{is=Is,last=Last}) ->
675    used_1([Last|Is], ordsets:new());
676used(#b_br{bool=#b_var{}=V}) ->
677    [V];
678used(#b_ret{arg=#b_var{}=V}) ->
679    [V];
680used(#b_set{op=phi,args=Args}) ->
681    ordsets:from_list([V || {#b_var{}=V,_} <- Args]);
682used(#b_set{args=Args}) ->
683    ordsets:from_list(used_args(Args));
684used(#b_switch{arg=#b_var{}=V}) ->
685    [V];
686used(_) -> [].
687
688-spec definitions(Labels :: [label()], Blocks :: block_map()) -> definition_map().
689definitions(Labels, Blocks) ->
690    fold_instrs(fun(#b_set{ dst = Var }=I, Acc) ->
691                            Acc#{Var => I};
692                       (_Terminator, Acc) ->
693                            Acc
694                    end, Labels, #{}, Blocks).
695
696%% uses(Labels, BlockMap) -> UsageMap
697%%  Traverse the blocks given by labels and builds a usage map
698%%  with variables as keys and a list of labels-instructions
699%%  tuples as values.
700-spec uses(Labels, Blocks) -> usage_map() when
701      Labels :: [label()],
702      Blocks :: block_map().
703uses(Labels, Blocks) ->
704    fold_blocks(fun fold_uses_block/3, Labels, #{}, Blocks).
705
706fold_uses_block(Lbl, #b_blk{is=Is,last=Last}, UseMap0) ->
707    F = fun(I, UseMap) ->
708                foldl(fun(Var, Acc) ->
709                              Uses0 = maps:get(Var, Acc, []),
710                              Uses = [{Lbl, I} | Uses0],
711                              maps:put(Var, Uses, Acc)
712                      end, UseMap, used(I))
713        end,
714    F(Last, foldl(F, UseMap0, Is)).
715
716-spec merge_blocks([label()], block_map()) -> block_map().
717
718merge_blocks(Labels, Blocks) ->
719    Preds = predecessors(Blocks),
720
721    %% We must traverse the blocks in reverse postorder to avoid
722    %% embedding succeeded:guard instructions into the middle of
723    %% blocks when this function is called from beam_ssa_bool.
724    merge_blocks_1(Labels, Preds, Blocks).
725
726%%%
727%%% Internal functions.
728%%%
729
730is_commutative('and') -> true;
731is_commutative('or') -> true;
732is_commutative('xor') -> true;
733is_commutative('band') -> true;
734is_commutative('bor') -> true;
735is_commutative('bxor') -> true;
736is_commutative('+') -> true;
737is_commutative('*') -> true;
738is_commutative('=:=') -> true;
739is_commutative('==') -> true;
740is_commutative('=/=') -> true;
741is_commutative('/=') -> true;
742is_commutative(_) -> false.
743
744def_unused_1([#b_blk{is=Is,last=Last}|Bs], Preds, Def0, Unused0) ->
745    Unused1 = ordsets:subtract(Unused0, used(Last)),
746    {Def,Unused} = def_unused_is(Is, Preds, Def0, Unused1),
747    def_unused_1(Bs, Preds, Def, Unused);
748def_unused_1([], _Preds, Def, Unused) ->
749    {ordsets:from_list(Def), Unused}.
750
751def_unused_is([#b_set{op=phi,dst=Dst,args=Args}|Is],
752            Preds, Def0, Unused0) ->
753    Def = [Dst|Def0],
754    %% We must be careful to only include variables that will
755    %% be used when arriving from one of the predecessor blocks
756    %% in Preds.
757    Unused1 = [V || {#b_var{}=V,L} <- Args, sets:is_element(L, Preds)],
758    Unused = ordsets:subtract(Unused0, ordsets:from_list(Unused1)),
759    def_unused_is(Is, Preds, Def, Unused);
760def_unused_is([#b_set{dst=Dst}=I|Is], Preds, Def0, Unused0) ->
761    Def = [Dst|Def0],
762    Unused = ordsets:subtract(Unused0, used(I)),
763    def_unused_is(Is, Preds, Def, Unused);
764def_unused_is([], _Preds, Def, Unused) ->
765    {Def,Unused}.
766
767def_1([#b_blk{is=Is}|Bs], Def0) ->
768    Def = def_is(Is, Def0),
769    def_1(Bs, Def);
770def_1([], Def) ->
771    ordsets:from_list(Def).
772
773def_is([#b_set{dst=Dst}|Is], Def) ->
774    def_is(Is, [Dst|Def]);
775def_is([], Def) -> Def.
776
777dominators_1([{L,Preds}|Ls], Df, Doms) ->
778    DomPreds = [map_get(P, Doms) || P <- Preds, is_map_key(P, Doms)],
779    Dom = [L|dom_intersection(DomPreds, Df)],
780    dominators_1(Ls, Df, Doms#{L=>Dom});
781dominators_1([], _Df, Doms) -> Doms.
782
783dom_intersection([S], _Df) ->
784    S;
785dom_intersection([S|Ss], Df) ->
786    dom_intersection(S, Ss, Df).
787
788dom_intersection(S1, [S2|Ss], Df) ->
789    dom_intersection(dom_intersection_1(S1, S2, Df), Ss, Df);
790dom_intersection(S, [], _Df) -> S.
791
792dom_intersection_1([E1|Es1]=Set1, [E2|Es2]=Set2, Df) ->
793    %% Blocks are numbered in the order they are found in
794    %% reverse postorder.
795    #{E1:=Df1,E2:=Df2} = Df,
796    if Df1 > Df2 ->
797            dom_intersection_1(Es1, Set2, Df);
798       Df2 > Df1 ->
799            dom_intersection_1(Es2, Set1, Df);  %switch arguments!
800       true ->                                  %Set1 == Set2
801            %% The common suffix of the sets is the intersection.
802            Set1
803    end.
804
805number([L|Ls], N) ->
806    [{L,N}|number(Ls, N+1)];
807number([], _) -> [].
808
809fold_blocks_1([L|Ls], Fun, Blocks, Acc0) ->
810    Block = map_get(L, Blocks),
811    Acc = Fun(L, Block, Acc0),
812    fold_blocks_1(Ls, Fun, Blocks, Acc);
813fold_blocks_1([], _, _, Acc) -> Acc.
814
815fold_instrs_1([L|Ls], Fun, Blocks, Acc0) ->
816    #b_blk{is=Is,last=Last} = map_get(L, Blocks),
817    Acc1 = foldl(Fun, Acc0, Is),
818    Acc = Fun(Last, Acc1),
819    fold_instrs_1(Ls, Fun, Blocks, Acc);
820fold_instrs_1([], _, _, Acc) -> Acc.
821
822mapfold_instrs_1([L|Ls], Fun, Blocks0, Acc0) ->
823    #b_blk{is=Is0,last=Last0} = Block0 = map_get(L, Blocks0),
824    {Is,Acc1} = mapfoldl(Fun, Acc0, Is0),
825    {Last,Acc} = Fun(Last0, Acc1),
826    Block = Block0#b_blk{is=Is,last=Last},
827    Blocks = Blocks0#{L:=Block},
828    mapfold_instrs_1(Ls, Fun, Blocks, Acc);
829mapfold_instrs_1([], _, Blocks, Acc) ->
830    {Blocks,Acc}.
831
832flatmapfold_instrs_1([L|Ls], Fun, Blocks0, Acc0) ->
833    #b_blk{is=Is0,last=Last0} = Block0 = map_get(L, Blocks0),
834    {Is,Acc1} = flatmapfoldl(Fun, Acc0, Is0),
835    {[Last],Acc} = Fun(Last0, Acc1),
836    Block = Block0#b_blk{is=Is,last=Last},
837    Blocks = Blocks0#{L:=Block},
838    flatmapfold_instrs_1(Ls, Fun, Blocks, Acc);
839flatmapfold_instrs_1([], _, Blocks, Acc) ->
840    {Blocks,Acc}.
841
842linearize_1([L|Ls], Blocks, Seen0, Acc0) ->
843    case sets:is_element(L, Seen0) of
844        true ->
845            linearize_1(Ls, Blocks, Seen0, Acc0);
846        false ->
847            Seen1 = sets:add_element(L, Seen0),
848            Block = map_get(L, Blocks),
849            Successors = successors(Block),
850            {Acc,Seen} = linearize_1(Successors, Blocks, Seen1, Acc0),
851            linearize_1(Ls, Blocks, Seen, [{L,Block}|Acc])
852    end;
853linearize_1([], _, Seen, Acc) ->
854    {Acc,Seen}.
855
856fix_phis([{L,Blk0}|Bs], S) ->
857    Blk = case Blk0 of
858              #b_blk{is=[#b_set{op=phi}|_]=Is0} ->
859                  Is = fix_phis_1(Is0, L, S),
860                  Blk0#b_blk{is=Is};
861              #b_blk{} ->
862                  Blk0
863          end,
864    Successors = successors(Blk),
865    [{L,Blk}|fix_phis(Bs, S#{L=>Successors})];
866fix_phis([], _) -> [].
867
868fix_phis_1([#b_set{op=phi,args=Args0}=I|Is], L, S) ->
869    Args = [{Val,Pred} || {Val,Pred} <- Args0,
870                          is_successor(L, Pred, S)],
871    [I#b_set{args=Args}|fix_phis_1(Is, L, S)];
872fix_phis_1(Is, _, _) -> Is.
873
874is_successor(L, Pred, S) ->
875    case S of
876        #{Pred:=Successors} ->
877            member(L, Successors);
878        #{} ->
879            %% This block has been removed.
880            false
881    end.
882
883trim_unreachable_1([{L,Blk0}|Bs], Seen0) ->
884    Blk = trim_phis(Blk0, Seen0),
885    case sets:is_element(L, Seen0) of
886        false ->
887            trim_unreachable_1(Bs, Seen0);
888        true ->
889            case successors(Blk) of
890                [] ->
891                    [{L,Blk}|trim_unreachable_1(Bs, Seen0)];
892                [Next] ->
893                    Seen = sets:add_element(Next, Seen0),
894                    [{L,Blk}|trim_unreachable_1(Bs, Seen)];
895                [_|_]=Successors ->
896                    Seen = sets:union(Seen0, sets:from_list(Successors, [{version, 2}])),
897                    [{L,Blk}|trim_unreachable_1(Bs, Seen)]
898            end
899    end;
900trim_unreachable_1([], _) -> [].
901
902trim_phis(#b_blk{is=[#b_set{op=phi}|_]=Is0}=Blk, Seen) ->
903    Is = trim_phis_1(Is0, Seen),
904    Blk#b_blk{is=Is};
905trim_phis(Blk, _Seen) -> Blk.
906
907trim_phis_1([#b_set{op=phi,args=Args0}=I|Is], Seen) ->
908    Args = [P || {_,L}=P <- Args0, sets:is_element(L, Seen)],
909    [I#b_set{args=Args}|trim_phis_1(Is, Seen)];
910trim_phis_1(Is, _Seen) -> Is.
911
912between_make_filter([L | Ls], Preds, Acc0) ->
913    case sets:is_element(L, Acc0) of
914        true ->
915            between_make_filter(Ls, Preds, Acc0);
916        false ->
917            Next = map_get(L, Preds),
918            Acc1 = sets:add_element(L, Acc0),
919
920            Acc = between_make_filter(Next, Preds, Acc1),
921            between_make_filter(Ls, Preds, Acc)
922    end;
923between_make_filter([], _Preds, Acc) ->
924    Acc.
925
926between_rpo([L | Ls], Blocks, Filter0, Acc0) ->
927    case sets:is_element(L, Filter0) of
928        true ->
929            Block = map_get(L, Blocks),
930            Filter1 = sets:del_element(L, Filter0),
931
932            Successors = successors(Block),
933            {Acc, Filter} = between_rpo(Successors, Blocks, Filter1, Acc0),
934            between_rpo(Ls, Blocks, Filter, [L | Acc]);
935        false ->
936            between_rpo(Ls, Blocks, Filter0, Acc0)
937    end;
938between_rpo([], _, Filter, Acc) ->
939    {Acc, Filter}.
940
941rpo_1([L|Ls], Blocks, Seen0, Acc0) ->
942    case sets:is_element(L, Seen0) of
943        true ->
944            rpo_1(Ls, Blocks, Seen0, Acc0);
945        false ->
946            Block = map_get(L, Blocks),
947            Seen1 = sets:add_element(L, Seen0),
948            Successors = successors(Block),
949            {Acc,Seen} = rpo_1(Successors, Blocks, Seen1, Acc0),
950            rpo_1(Ls, Blocks, Seen, [L|Acc])
951    end;
952rpo_1([], _, Seen, Acc) ->
953    {Acc,Seen}.
954
955rename_var(#b_var{}=Old, Rename) ->
956    case Rename of
957        #{Old:=New} -> New;
958        #{} -> Old
959    end;
960rename_var(#b_remote{mod=Mod0,name=Name0}=Remote, Rename) ->
961    Mod = rename_var(Mod0, Rename),
962    Name = rename_var(Name0, Rename),
963    Remote#b_remote{mod=Mod,name=Name};
964rename_var(Old, _) -> Old.
965
966rename_phi_vars([{Var,L}|As], Preds, Ren) ->
967    case sets:is_element(L, Preds) of
968        true ->
969            [{rename_var(Var, Ren),L}|rename_phi_vars(As, Preds, Ren)];
970        false ->
971            [{Var,L}|rename_phi_vars(As, Preds, Ren)]
972    end;
973rename_phi_vars([], _, _) -> [].
974
975map_instrs_1([L|Ls], Fun, Blocks0) ->
976    #b_blk{is=Is0,last=Last0} = Blk0 = map_get(L, Blocks0),
977    Is = [Fun(I) || I <- Is0],
978    Last = Fun(Last0),
979    Blk = Blk0#b_blk{is=Is,last=Last},
980    Blocks = Blocks0#{L:=Blk},
981    map_instrs_1(Ls, Fun, Blocks);
982map_instrs_1([], _, Blocks) -> Blocks.
983
984flatmapfoldl(F, Accu0, [Hd|Tail]) ->
985    {R,Accu1} = F(Hd, Accu0),
986    {Rs,Accu2} = flatmapfoldl(F, Accu1, Tail),
987    {R++Rs,Accu2};
988flatmapfoldl(_, Accu, []) -> {[],Accu}.
989
990split_blocks_1([L|Ls], P, Blocks0, Count0) ->
991    #b_blk{is=Is0} = Blk = map_get(L, Blocks0),
992    case split_blocks_is(Is0, P, []) of
993        {yes,Bef,Aft} ->
994            NewLbl = Count0,
995            Count = Count0 + 1,
996            Br = #b_br{bool=#b_literal{val=true},succ=NewLbl,fail=NewLbl},
997            BefBlk = Blk#b_blk{is=Bef,last=Br},
998            NewBlk = Blk#b_blk{is=Aft},
999            Blocks1 = Blocks0#{L:=BefBlk,NewLbl=>NewBlk},
1000            Successors = successors(NewBlk),
1001            Blocks = update_phi_labels(Successors, L, NewLbl, Blocks1),
1002            split_blocks_1([NewLbl|Ls], P, Blocks, Count);
1003        no ->
1004            split_blocks_1(Ls, P, Blocks0, Count0)
1005    end;
1006split_blocks_1([], _, Blocks, Count) ->
1007    {Blocks,Count}.
1008
1009split_blocks_is([I|Is], P, []) ->
1010    split_blocks_is(Is, P, [I]);
1011split_blocks_is([I|Is], P, Acc) ->
1012    case P(I) of
1013        true ->
1014            {yes,reverse(Acc),[I|Is]};
1015        false ->
1016            split_blocks_is(Is, P, [I|Acc])
1017    end;
1018split_blocks_is([], _, _) -> no.
1019
1020update_phi_labels_is([#b_set{op=phi,args=Args0}=I0|Is], Old, New) ->
1021    Args = [{Arg,rename_label(Lbl, Old, New)} || {Arg,Lbl} <- Args0],
1022    I = I0#b_set{args=Args},
1023    [I|update_phi_labels_is(Is, Old, New)];
1024update_phi_labels_is(Is, _, _) -> Is.
1025
1026rename_label(Old, Old, New) -> New;
1027rename_label(Lbl, _Old, _New) -> Lbl.
1028
1029used_args([#b_var{}=V|As]) ->
1030    [V|used_args(As)];
1031used_args([#b_remote{mod=Mod,name=Name}|As]) ->
1032    used_args([Mod,Name|As]);
1033used_args([_|As]) ->
1034    used_args(As);
1035used_args([]) -> [].
1036
1037used_1([H|T], Used0) ->
1038    Used = ordsets:union(used(H), Used0),
1039    used_1(T, Used);
1040used_1([], Used) -> Used.
1041
1042
1043%%% Merge blocks.
1044
1045merge_blocks_1([L|Ls], Preds0, Blocks0) ->
1046    case Preds0 of
1047        #{L:=[P]} ->
1048            #{P:=Blk0,L:=Blk1} = Blocks0,
1049            case is_merge_allowed(L, Blk0, Blk1) of
1050                true ->
1051                    #b_blk{is=Is0} = Blk0,
1052                    #b_blk{is=Is1} = Blk1,
1053                    verify_merge_is(Is1),
1054                    Is = merge_fix_succeeded(Is0 ++ Is1, Blk1),
1055                    Blk = Blk1#b_blk{is=Is},
1056                    Blocks1 = maps:remove(L, Blocks0),
1057                    Blocks2 = Blocks1#{P:=Blk},
1058                    Successors = successors(Blk),
1059                    Blocks = update_phi_labels(Successors, L, P, Blocks2),
1060                    Preds = merge_update_preds(Successors, L, P, Preds0),
1061                    merge_blocks_1(Ls, Preds, Blocks);
1062                false ->
1063                    merge_blocks_1(Ls, Preds0, Blocks0)
1064            end;
1065        #{} ->
1066            merge_blocks_1(Ls, Preds0, Blocks0)
1067    end;
1068merge_blocks_1([], _Preds, Blocks) -> Blocks.
1069
1070%% Since we process the candidates in reverse postorder it is necessary
1071%% to update the predecessors. Reverse postorder is necessary to ensure
1072%% that merge_fix_succeeded/2 will find and remove all succeeded:guard
1073%% not followed by a two-way branch.
1074merge_update_preds([L|Ls], From, To, Preds0) ->
1075    case Preds0 of
1076        #{L := [P]} ->
1077            Preds = Preds0#{L := [rename_label(P, From, To)]},
1078            merge_update_preds(Ls, From, To, Preds);
1079        #{} ->
1080            %% More than one predecessor, so this block will not be
1081            %% merged. Updating the predecessors is not needed and
1082            %% updating would waste a lot of time if there are many
1083            %% predecessors.
1084            merge_update_preds(Ls, From, To, Preds0)
1085    end;
1086merge_update_preds([], _, _, Preds) -> Preds.
1087
1088merge_fix_succeeded(Is, #b_blk{last=#b_br{succ=Succ,fail=Fail}}) when Succ =/= Fail ->
1089    %% This is a two-way branch. There is no need look at the instructions.
1090    Is;
1091merge_fix_succeeded([_|_]=Is0, #b_blk{}) ->
1092    %% Not a two-way branch.
1093    case reverse(Is0) of
1094        [#b_set{op={succeeded,guard},args=[Dst]},#b_set{dst=Dst}|Is] ->
1095            %% This succeeded:guard instruction MUST be followed by a
1096            %% two-way branch. It is not, which means that its result
1097            %% will never be used. Therefore, the instruction and
1098            %% succeeded:guard must be removed.
1099            %%
1100            %% We remove those instructions for the benefit of the
1101            %% beam_ssa_bool pass. When called from beam_ssa_opt there
1102            %% should be no such instructions left.
1103            reverse(Is);
1104        _ ->
1105            Is0
1106    end;
1107merge_fix_succeeded(Is, _Blk) -> Is.
1108
1109verify_merge_is([#b_set{op=Op}|_]) ->
1110    %% The merged block has only one predecessor, so it should not have any phi
1111    %% nodes.
1112    true = Op =/= phi;                          %Assertion.
1113verify_merge_is(_) ->
1114    ok.
1115
1116is_merge_allowed(?EXCEPTION_BLOCK, #b_blk{}, #b_blk{}) ->
1117    false;
1118is_merge_allowed(_L, #b_blk{is=[#b_set{op=landingpad} | _]}, #b_blk{}) ->
1119    false;
1120is_merge_allowed(_L, #b_blk{}, #b_blk{is=[#b_set{op=landingpad} | _]}) ->
1121    false;
1122is_merge_allowed(L, #b_blk{}=Blk1, #b_blk{is=[#b_set{}=I|_]}=Blk2) ->
1123    not is_loop_header(I) andalso
1124        is_merge_allowed_1(L, Blk1, Blk2);
1125is_merge_allowed(L, Blk1, Blk2) ->
1126    is_merge_allowed_1(L, Blk1, Blk2).
1127
1128is_merge_allowed_1(L, #b_blk{last=#b_br{}}=Blk, #b_blk{is=Is}) ->
1129    %% The predecessor block must have exactly one successor (L) for
1130    %% the merge to be safe.
1131    case successors(Blk) of
1132        [L] ->
1133            case Is of
1134                [#b_set{op=phi,args=[_]}|_] ->
1135                    %% The type optimizer pass must have been
1136                    %% turned off, since it would have removed this
1137                    %% redundant phi node. Refuse to merge the blocks
1138                    %% to ensure that this phi node remains at the
1139                    %% beginning of a block.
1140                    false;
1141                _ ->
1142                    true
1143            end;
1144        [_|_] ->
1145            false
1146    end;
1147is_merge_allowed_1(_, #b_blk{last=#b_switch{}}, #b_blk{}) ->
1148    false.
1149
1150%% update_phi_labels([BlockLabel], Old, New, Blocks0) -> Blocks.
1151%%  In the given blocks, replace label Old in with New in all
1152%%  phi nodes. This is useful after merging or splitting
1153%%  blocks.
1154
1155update_phi_labels([L|Ls], Old, New, Blocks0) ->
1156    case Blocks0 of
1157        #{L:=#b_blk{is=[#b_set{op=phi}|_]=Is0}=Blk0} ->
1158            Is = update_phi_labels_is(Is0, Old, New),
1159            Blk = Blk0#b_blk{is=Is},
1160            Blocks = Blocks0#{L:=Blk},
1161            update_phi_labels(Ls, Old, New, Blocks);
1162        #{L:=#b_blk{}} ->
1163            %% No phi nodes in this block.
1164            update_phi_labels(Ls, Old, New, Blocks0)
1165    end;
1166update_phi_labels([], _, _, Blocks) -> Blocks.
1167