aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler/src/beam_ssa_share.erl
blob: 85ab088d14e76948ade153fa56d66805aaf6d7a4 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
%%
%% %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%
%%

%%
%% Share code for semantically equivalent blocks referred to
%% to by `br` and `switch` instructions.
%%
%% A similar optimization is done in beam_jump, but doing it here as
%% well is beneficial as it may enable other optimizations. If there
%% are many semantically equivalent clauses, this optimization can
%% substanstially decrease compilation times.
%%
%% block/2 is called from the liveness optimization pass in
%% beam_ssa_opt, as code sharing helps the liveness pass and vice
%% versa.
%%

-module(beam_ssa_share).
-export([module/2,block/2]).

-include("beam_ssa.hrl").

-import(lists, [keyfind/3,reverse/1,sort/1]).

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

module(#b_module{body=Fs0}=Module, _Opts) ->
    Fs = [function(F) || F <- Fs0],
    {ok,Module#b_module{body=Fs}}.

-spec block(Blk0, Blocks0) -> Blk when
      Blk0 :: beam_ssa:b_blk(),
      Blocks0 :: beam_ssa:block_map(),
      Blk :: beam_ssa:b_blk().

block(#b_blk{last=Last0}=Blk, Blocks) ->
    case share_terminator(Last0, Blocks) of
        none -> Blk;
        Last -> Blk#b_blk{last=beam_ssa:normalize(Last)}
    end.

%%%
%%% Local functions.
%%%

function(#b_function{anno=Anno,bs=Blocks0}=F) ->
    try
        PO = reverse(beam_ssa:rpo(Blocks0)),
        {Blocks1,Changed} = blocks(PO, Blocks0, false),
        Blocks = case Changed of
                     true ->
                         beam_ssa:trim_unreachable(Blocks1);
                     false ->
                         Blocks0
                 end,
        F#b_function{bs=Blocks}
    catch
        Class:Error:Stack ->
            #{func_info:={_,Name,Arity}} = Anno,
            io:fwrite("Function: ~w/~w\n", [Name,Arity]),
            erlang:raise(Class, Error, Stack)
    end.

blocks([L|Ls], Blocks, Changed) ->
    #b_blk{last=Last0} = Blk0 = map_get(L, Blocks),
    case block(Blk0, Blocks) of
        #b_blk{last=Last0} ->
            blocks(Ls, Blocks, Changed);
        #b_blk{}=Blk ->
            blocks(Ls, Blocks#{L:=Blk}, true)
    end;
blocks([], Blocks, Changed) ->
    {Blocks,Changed}.

share_terminator(#b_br{bool=#b_var{},succ=Succ0,fail=Fail0}=Br, Blocks) ->
    {Succ,SuccBlk} = shortcut_nonempty_block(Succ0, Blocks),
    {Fail,FailBlk} = shortcut_nonempty_block(Fail0, Blocks),
    case are_equivalent(Succ, SuccBlk, Fail, FailBlk, Blocks) of
        true ->
            %% The blocks are semantically equivalent.
            Br#b_br{succ=Succ,fail=Succ};
        false ->
            if
                Succ =:= Succ0, Fail =:= Fail0 ->
                    %% None of blocks were cut short.
                    none;
                true ->
                    %% One or both labels were cut short
                    %% to avoid jumping to an empty block.
                    Br#b_br{succ=Succ,fail=Fail}
            end
    end;
share_terminator(#b_switch{}=Sw, Blocks) ->
    share_switch(Sw, Blocks);
share_terminator(_Last, _Blocks) -> none.

%% Test whether the two blocks are semantically equivalent.  This
%% function is specially optimized to return `false` as fast as
%% possible if the blocks are not equivalent, as that is the common
%% case.

are_equivalent(_Succ, _, ?EXCEPTION_BLOCK, _, _Blocks) ->
    %% ?EXCEPTION_BLOCK is special. Sharing could be incorrect.
    false;
are_equivalent(_Succ, #b_blk{is=Is1,last=#b_ret{arg=RetVal1}=Ret1},
         _Fail, #b_blk{is=Is2,last=#b_ret{arg=RetVal2}=Ret2}, _Blocks) ->
    case {RetVal1,RetVal2} of
        {#b_literal{},#b_literal{}} ->
            case RetVal1 =:= RetVal2 of
                true ->
                    %% The return values are identical literals. We
                    %% only need to compare the canonicalized bodies.
                    Can1 = canonical_is(Is1),
                    Can2 = canonical_is(Is2),
                    Can1 =:= Can2;
                false ->
                    %% Non-equal literals.
                    false
            end;
        {#b_var{},#b_var{}} ->
            %% The return values are varibles. We must canonicalize
            %% the blocks (including returns) and compare them.
            Can1 = canonical_is(Is1 ++ [Ret1]),
            Can2 = canonical_is(Is2 ++ [Ret2]),
            Can1 =:= Can2;
        {_,_} ->
            %% One literal and one variable.
            false
    end;
are_equivalent(Succ,
         #b_blk{is=Is1,
                last=#b_br{bool=#b_literal{val=true},
                           succ=Target}},
         Fail,
         #b_blk{is=Is2,
                last=#b_br{bool=#b_literal{val=true},
                           succ=Target}},
         Blocks) ->
    %% Both blocks end with an unconditional branch to the
    %% same target block. If the target block has phi nodes,
    %% we must pick up the values from the phi nodes and
    %% compare them.
    #b_blk{is=Is} = map_get(Target, Blocks),
    Phis1 = canonical_terminator_phis(Is, Succ),
    Phis2 = canonical_terminator_phis(Is, Fail),
    case {Phis1,Phis2} of
        {[#b_set{args=[#b_literal{}]}|_],_} when Phis1 =/= Phis2 ->
            %% Different values are used in the phi nodes.
            false;
        {_,[#b_set{args=[#b_literal{}]}|_]} when Phis1 =/= Phis2 ->
            %% Different values are used in the phi nodes.
            false;
        {_,_} ->
            %% The values in the phi nodes are variables or identical
            %% literals. We must canonicalize the blocks and compare
            %% them.
            Can1 = canonical_is(Is1 ++ Phis1),
            Can2 = canonical_is(Is2 ++ Phis2),
            Can1 =:= Can2
    end;
are_equivalent(Succ0, #b_blk{is=Is1,last=#b_br{bool=#b_var{},fail=Same}},
         Fail0, #b_blk{is=Is2,last=#b_br{bool=#b_var{},fail=Same}},
         Blocks) ->
    %% Two-way branches with identical failure labels. First compare the
    %% canonicalized bodies of the blocks.
    case canonical_is(Is1) =:= canonical_is(Is2) of
        false ->
            %% Different bodies.
            false;
        true ->
            %% Bodies were equal. That is fairly uncommon, so to keep
            %% the code simple we will rewrite the `br` to a `switch`
            %% and let share_switch/2 do the work of following the
            %% branches.
            Sw = #b_switch{arg=#b_var{name=not_used},fail=Fail0,
                           list=[{#b_literal{},Succ0}]},
            #b_switch{fail=Fail,list=[{_,Succ}]} = share_switch(Sw, Blocks),
            Fail =:= Succ
    end;
are_equivalent(_, _, _, _, _) -> false.

share_switch(#b_switch{fail=Fail0,list=List0}=Sw, Blocks) ->
    Prep = share_prepare_sw([{value,Fail0}|List0], Blocks, 0, []),
    Res = do_share_switch(Prep, Blocks, []),
    [{_,Fail}|List] = [VL || {_,VL} <- sort(Res)],
    Sw#b_switch{fail=Fail,list=List}.

share_prepare_sw([{V,L0}|T], Blocks, N, Acc) ->
    {L,_Blk} = shortcut_nonempty_block(L0, Blocks),
    share_prepare_sw(T, Blocks, N+1, [{{L,#{}},{N,{V,L}}}|Acc]);
share_prepare_sw([], _, _, Acc) -> Acc.

do_share_switch(Prep, Blocks, Acc) ->
    Map = share_switch_1(Prep, Blocks, #{}),
    share_switch_2(maps:values(Map), Blocks, Acc).

share_switch_1([{Next0,Res}|T], Blocks, Map) ->
    {Can,Next} = canonical_block(Next0, Blocks),
    case Map of
        #{Can:=Ls} ->
            share_switch_1(T, Blocks, Map#{Can:=[{Next,Res}|Ls]});
        #{} ->
            share_switch_1(T, Blocks, Map#{Can=>[{Next,Res}]})
    end;
share_switch_1([], _Blocks, Map) -> Map.

share_switch_2([[{_,{N,Res}}]|T], Blocks, Acc) ->
    %% This block is not equivalent to any other block.
    share_switch_2(T, Blocks, [{N,Res}|Acc]);
share_switch_2([[{done,{_,{_,Common}}}|_]=Eqs|T], Blocks, Acc0) ->
    %% Two or more blocks are semantically equivalent, and all blocks
    %% are either terminated with a `ret` or a `br` to the same target
    %% block. Replace the labels in the `switch` for all of those
    %% blocks with the label for the first of the blocks.
    Acc = [{N,{V,Common}} || {done,{N,{V,_}}} <- Eqs] ++ Acc0,
    share_switch_2(T, Blocks, Acc);
share_switch_2([[{_,_}|_]=Prep|T], Blocks, Acc0) ->
    %% Two or more blocks are semantically equivalent, but they have
    %% different successful successor blocks. Now we must check
    %% recursively whether the successor blocks are equivalent too.
    Acc = do_share_switch(Prep, Blocks, Acc0),
    share_switch_2(T, Blocks, Acc);
share_switch_2([], _, Acc) -> Acc.

canonical_block({L,VarMap0}, Blocks) ->
    #b_blk{is=Is,last=Last0} = map_get(L, Blocks),
    case canonical_terminator(L, Last0, Blocks) of
        none ->
            %% The block has a terminator that we don't handle.
            {{none,L},done};
        {Last,done} ->
            %% The block ends with a `ret` or an unconditional `br` to
            %% another block.
            {Can,_VarMap} = canonical_is(Is ++ Last, VarMap0, []),
            {Can,done};
        {Last,Next} ->
            %% The block ends with a conditional branch.
            {Can,VarMap} = canonical_is(Is ++ Last, VarMap0, []),
            {Can,{Next,VarMap}}
    end.

%% Translate a sequence of instructions to a canonical representation. If the
%% canonical representation of two blocks compare equal, the blocks are
%% semantically equivalent. The following translations are done:
%%
%%    * Variables defined in the instruction sequence are replaced with
%%    {var,0}, {var,1}, and so on. Free variables are not changed.
%%
%%    * `location` annotations that would produce a `line` instruction are
%%    kept. All other annotations are cleared.
%%
%%    * Instructions are repackaged into tuples instead of into the
%%    usual records. The main reason is to avoid violating the types for
%%    the SSA records. We can simplify things a little by linking the
%%    instructions directly instead of putting them into a list.

canonical_is(Is) ->
    {Can,_} = canonical_is(Is, #{}, []),
    Can.

canonical_is([#b_set{op=Op,dst=Dst,args=Args0}=I|Is], VarMap0, Acc) ->
    Args = [canonical_arg(Arg, VarMap0) || Arg <-Args0],
    Var = {var,map_size(VarMap0)},
    VarMap = VarMap0#{Dst=>Var},
    LineAnno = case Op of
                   bs_match ->
                       %% The location annotation for a bs_match instruction
                       %% is only used in warnings, never to emit a `line`
                       %% instruction. Therefore, it should not be included.
                       [];
                   _ ->
                       %% The location annotation will be used in a `line`
                       %% instruction. It must be included.
                       beam_ssa:get_anno(location, I, none)
               end,
    canonical_is(Is, VarMap, {Op,LineAnno,Var,Args,Acc});
canonical_is([#b_ret{arg=Arg}], VarMap, Acc0) ->
    Acc1 = case Acc0 of
               {call,_Anno,Var,[#b_local{}|_]=Args,PrevAcc} ->
                   %% This is a tail-recursive call to a local function.
                   %% There will be no line instruction generated;
                   %% thus, the annotation is not significant.
                   {call,[],Var,Args,PrevAcc};
               _ ->
                   Acc0
           end,
    {{ret,canonical_arg(Arg, VarMap),Acc1},VarMap};
canonical_is([#b_br{bool=#b_var{},fail=Fail}], VarMap, Acc) ->
    {{br,succ,Fail,Acc},VarMap};
canonical_is([#b_br{succ=Succ}], VarMap, Acc) ->
    {{br,Succ,Acc},VarMap};
canonical_is([], VarMap, Acc) ->
    {Acc,VarMap}.

canonical_terminator(_L, #b_ret{}=Ret, _Blocks) ->
    {[Ret],done};
canonical_terminator(L, #b_br{bool=#b_literal{val=true},succ=Succ}=Br, Blocks) ->
    #b_blk{is=Is} = map_get(Succ, Blocks),
    case canonical_terminator_phis(Is, L) of
        [] ->
            {[],Succ};
        [_|_]=Phis ->
            {Phis ++ [Br],done}
    end;
canonical_terminator(_L, #b_br{bool=#b_var{},succ=Succ}=Br, _Blocks) ->
    {[Br],Succ};
canonical_terminator(_, _, _) -> none.

canonical_terminator_phis([#b_set{op=phi,args=PhiArgs}=Phi|Is], L) ->
    {Value,L} = keyfind(L, 2, PhiArgs),
    [Phi#b_set{op=copy,args=[Value]}|canonical_terminator_phis(Is, L)];
canonical_terminator_phis([#b_set{op=peek_message}=I|_], L) ->
    %% We could get stuck into an infinite loop if we allowed the
    %% comparisons to continue into this block. Force an unequal
    %% compare with all other predecessors of this block.
    [I#b_set{op=copy,args=[#b_literal{val=L}]}];
canonical_terminator_phis(_, _) -> [].

canonical_arg(#b_var{}=Var, VarMap) ->
    case VarMap of
        #{Var:=CanonicalVar} ->
            CanonicalVar;
        #{} ->
            Var
    end;
canonical_arg(#b_remote{mod=Mod,name=Name}, VarMap) ->
    {remote,canonical_arg(Mod, VarMap),
     canonical_arg(Name, VarMap)};
canonical_arg(Other, _VarMap) -> Other.

%% Shortcut branches to empty blocks if safe.

shortcut_nonempty_block(L, Blocks) ->
    case map_get(L, Blocks) of
        #b_blk{is=[],last=#b_br{bool=#b_literal{val=true},succ=Succ}}=Blk ->
            %% This block is empty.
            case is_forbidden(Succ, Blocks) of
                false ->
                    shortcut_nonempty_block(Succ, Blocks);
                true ->
                    {L,Blk}
            end;
        #b_blk{}=Blk ->
            {L,Blk}
    end.

is_forbidden(L, Blocks) ->
    case map_get(L, Blocks) of
        #b_blk{is=[#b_set{op=phi}|_]} -> true;
        #b_blk{is=[#b_set{op=peek_message}|_]} -> true;
        #b_blk{} -> false
    end.