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