diff options
Diffstat (limited to 'lib/compiler/src/beam_ssa_pre_codegen.erl')
-rw-r--r-- | lib/compiler/src/beam_ssa_pre_codegen.erl | 120 |
1 files changed, 102 insertions, 18 deletions
diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl index 9af72afca7..7f816b9802 100644 --- a/lib/compiler/src/beam_ssa_pre_codegen.erl +++ b/lib/compiler/src/beam_ssa_pre_codegen.erl @@ -156,7 +156,9 @@ passes(Opts) -> %% Allocate registers. ?PASS(linear_scan), ?PASS(frame_size), - ?PASS(turn_yregs)], + ?PASS(turn_yregs), + + ?PASS(assert_no_critical_edges)], [P || P <- Ps, P =/= ignore]. function(#b_function{anno=Anno,args=Args,bs=Blocks0,cnt=Count0}=F0, @@ -1321,10 +1323,11 @@ fix_receives_1([{L,Blk}|Ls], Blocks0, Count0) -> LoopExit = find_loop_exit(Rm, Blocks0), Defs0 = beam_ssa:def([L], Blocks0), CommonUsed = recv_common(Defs0, LoopExit, Blocks0), - {Blocks1,Count1} = recv_fix_common(CommonUsed, LoopExit, Rm, - Blocks0, Count0), + {Blocks1,Count1} = recv_crit_edges(Rm, LoopExit, Blocks0, Count0), + {Blocks2,Count2} = recv_fix_common(CommonUsed, LoopExit, Rm, + Blocks1, Count1), Defs = ordsets:subtract(Defs0, CommonUsed), - {Blocks,Count} = fix_receive(Rm, Defs, Blocks1, Count1), + {Blocks,Count} = fix_receive(Rm, Defs, Blocks2, Count2), fix_receives_1(Ls, Blocks, Count); #b_blk{} -> fix_receives_1(Ls, Blocks0, Count0) @@ -1341,6 +1344,57 @@ recv_common(Defs, Exit, Blocks) -> Def = ordsets:subtract(Defs, ExitDefs), ordsets:intersection(Def, ExitUsed). +%% recv_crit_edges([RemoveMessageLabel], LoopExit, +%% Blocks0, Count0) -> {Blocks,Count}. +%% +%% Adds dummy blocks on all conditional jumps to the exit block so that +%% recv_fix_common/5 can insert phi nodes without having to worry about +%% critical edges. + +recv_crit_edges(_Rms, none, Blocks0, Count0) -> + {Blocks0, Count0}; +recv_crit_edges(Rms, Exit, Blocks0, Count0) -> + Ls = beam_ssa:rpo(Rms, Blocks0), + rce_insert_edges(Ls, Exit, Count0, Blocks0). + +rce_insert_edges([L | Ls], Exit, Count0, Blocks0) -> + Successors = beam_ssa:successors(map_get(L, Blocks0)), + case member(Exit, Successors) of + true when Successors =/= [Exit] -> + {Blocks, Count} = rce_insert_edge(L, Exit, Count0, Blocks0), + rce_insert_edges(Ls, Exit, Count, Blocks); + _ -> + rce_insert_edges(Ls, Exit, Count0, Blocks0) + end; +rce_insert_edges([], _Exit, Count, Blocks) -> + {Blocks, Count}. + +rce_insert_edge(L, Exit, Count, Blocks0) -> + #b_blk{last=Last0} = FromBlk0 = map_get(L, Blocks0), + + ToExit = #b_br{bool=#b_literal{val=true},succ=Exit,fail=Exit}, + + FromBlk = FromBlk0#b_blk{last=rce_reroute_terminator(Last0, Exit, Count)}, + EdgeBlk = #b_blk{anno=#{},is=[],last=ToExit}, + + Blocks = Blocks0#{ Count => EdgeBlk, L => FromBlk }, + {Blocks, Count + 1}. + +rce_reroute_terminator(#b_br{succ=Exit}=Last, Exit, New) -> + rce_reroute_terminator(Last#b_br{succ=New}, Exit, New); +rce_reroute_terminator(#b_br{fail=Exit}=Last, Exit, New) -> + rce_reroute_terminator(Last#b_br{fail=New}, Exit, New); +rce_reroute_terminator(#b_br{}=Last, _Exit, _New) -> + Last; +rce_reroute_terminator(#b_switch{fail=Exit}=Last, Exit, New) -> + rce_reroute_terminator(Last#b_switch{fail=New}, Exit, New); +rce_reroute_terminator(#b_switch{list=List0}=Last, Exit, New) -> + List = [if + Lbl =:= Exit -> {Arg, New}; + Lbl =/= Exit -> {Arg, Lbl} + end || {Arg, Lbl} <- List0], + Last#b_switch{list=List}. + %% recv_fix_common([CommonVar], LoopExit, [RemoveMessageLabel], %% Blocks0, Count0) -> {Blocks,Count}. %% Handle variables alwys defined in a receive and used @@ -1409,21 +1463,51 @@ fix_receive([], _Defs, Blocks, Count) -> {Blocks,Count}. %% find_loop_exit([Label], Blocks) -> Label | none. -%% Find the block to which control is transferred when the -%% the receive loop is exited. - -find_loop_exit([L1,L2|_Ls], Blocks) -> - Path1 = beam_ssa:rpo([L1], Blocks), - Path2 = beam_ssa:rpo([L2], Blocks), - find_loop_exit_1(Path1, cerl_sets:from_list(Path2)); -find_loop_exit(_, _) -> none. - -find_loop_exit_1([H|T], OtherPath) -> - case cerl_sets:is_element(H, OtherPath) of - true -> H; - false -> find_loop_exit_1(T, OtherPath) +%% Given the list of all blocks with the remove_message instructions +%% for this receive, find the block to which control is transferred +%% when the receive loop is exited (if any). + +find_loop_exit([_,_|_]=RmBlocks, Blocks) -> + %% We used to only analyze the path from two of the remove_message + %% blocks. That would fail to find a common block if one or both + %% of the blocks happened to raise an exception. To be sure that + %% we always find a common block if there is one (shared by at + %% least two clauses), we must analyze the path from all + %% remove_message blocks. + {Dominators,_} = beam_ssa:dominators(Blocks), + RmSet = cerl_sets:from_list(RmBlocks), + Rpo = beam_ssa:rpo(RmBlocks, Blocks), + find_loop_exit_1(Rpo, RmSet, Dominators); +find_loop_exit(_, _) -> + %% There is (at most) a single clause. There is no common + %% loop exit block. + none. + +find_loop_exit_1([?BADARG_BLOCK|Ls], RmSet, Dominators) -> + %% ?BADARG_BLOCK is a marker and not an actual block, so it is not + %% the block we are looking for. + find_loop_exit_1(Ls, RmSet, Dominators); +find_loop_exit_1([L|Ls], RmSet, Dominators) -> + DomBy = map_get(L, Dominators), + case any(fun(E) -> cerl_sets:is_element(E, RmSet) end, DomBy) of + true -> + %% This block is dominated by one of the remove_message blocks, + %% which means that the block is part of only one clause. + %% It is not the block we are looking for. + find_loop_exit_1(Ls, RmSet, Dominators); + false -> + %% This block is the first block that is not dominated by + %% any of the blocks with remove_message instructions, + %% which means that at least two of the receive clauses + %% will ultimately transfer control to it. It is the block + %% we are looking for. + L end; -find_loop_exit_1([], _) -> none. +find_loop_exit_1([], _, _) -> + %% None of clauses transfers control to a common block after the receive + %% statement. That means that the receive statement is a the end of a + %% function (or that all clauses raise exceptions). + none. %% find_rm_blocks(StartLabel, Blocks) -> [Label]. %% Find all blocks that start with remove_message within the receive |