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