aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/flow/cfg.inc
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/flow/cfg.inc')
-rw-r--r--lib/hipe/flow/cfg.inc129
1 files changed, 99 insertions, 30 deletions
diff --git a/lib/hipe/flow/cfg.inc b/lib/hipe/flow/cfg.inc
index 0bad2a8dd7..cb5f397f64 100644
--- a/lib/hipe/flow/cfg.inc
+++ b/lib/hipe/flow/cfg.inc
@@ -32,6 +32,8 @@
%% bb(CFG, Label) - returns the basic block named 'Label' from the CFG.
%% bb_add(CFG, Label, NewBB) - makes NewBB the basic block associated
%% with Label.
+%% map_bbs(Fun, CFG) - map over all code without changing control flow.
+%% fold_bbs(Fun, Acc, CFG) - fold over the basic blocks in a CFG.
%% succ(Map, Label) - returns a list of successors of basic block 'Label'.
%% pred(Map, Label) - returns the predecessors of basic block 'Label'.
%% fallthrough(CFG, Label) - returns fall-through successor of basic
@@ -89,6 +91,7 @@
-define(BREADTH_ORDER,true). % for linear scan
-define(PARAMS_NEEDED,true).
-define(START_LABEL_UPDATE_NEEDED,true).
+-define(MAP_FOLD_NEEDED,true).
-endif.
%%=====================================================================
@@ -307,11 +310,7 @@ redirect_phis([I|Rest], OldPred, NewPred, Acc) ->
%% @doc Adds a new basic block to a CFG (or updates an existing block).
bb_add(CFG, Label, NewBB) ->
%% Asserting that the NewBB is a legal basic block
- Last = hipe_bb:last(NewBB),
- case is_branch(Last) of
- true -> ok;
- false -> throw({?MODULE, {"Basic block ends without branch", Last}})
- end,
+ Last = assert_bb(NewBB),
%% The order of the elements from branch_successors/1 is
%% significant. It determines the basic block order when the CFG is
%% converted to linear form. That order may have been tuned for
@@ -339,11 +338,53 @@ bb_add(CFG, Label, NewBB) ->
HT2, OldSucc -- Succ),
CFG#cfg{table = HT3}.
+-ifdef(MAP_FOLD_NEEDED).
+-spec map_bbs(fun((cfg_lbl(), hipe_bb:bb()) -> hipe_bb:bb()), cfg()) -> cfg().
+%% @doc Map over the code in a CFG without changing any control flow.
+map_bbs(Fun, CFG = #cfg{table=HT0}) ->
+ HT = gb_trees:map(
+ fun(Lbl, {OldBB, OldSucc, OldPred}) ->
+ NewBB = Fun(Lbl, OldBB),
+ %% Assert preconditions
+ NewLast = assert_bb(NewBB),
+ OldSucc = remove_duplicates(branch_successors(NewLast)),
+ {NewBB, OldSucc, OldPred}
+ end, HT0),
+ CFG#cfg{table=HT}.
+
+-spec fold_bbs(fun((cfg_lbl(), hipe_bb:bb(), Acc) -> Acc), Acc, cfg()) -> Acc.
+%% @doc Fold over the basic blocks in a CFG in unspecified order.
+fold_bbs(Fun, InitAcc, #cfg{table=HT}) ->
+ gb_trees_fold(fun(Lbl, {BB, _, _}, Acc) -> Fun(Lbl, BB, Acc) end,
+ InitAcc, HT).
+
+gb_trees_fold(Fun, InitAcc, Tree) ->
+ gb_trees_fold_1(Fun, InitAcc, gb_trees:iterator(Tree)).
+
+gb_trees_fold_1(Fun, InitAcc, Iter0) ->
+ case gb_trees:next(Iter0) of
+ none -> InitAcc;
+ {Key, Value, Iter} ->
+ gb_trees_fold_1(Fun, Fun(Key, Value, InitAcc), Iter)
+ end.
+-endif. % MAP_FOLD_NEEDED
+
+assert_bb(BB) ->
+ assert_bb_is(hipe_bb:code(BB)).
+
+assert_bb_is([Last]) ->
+ true = is_branch(Last),
+ Last;
+assert_bb_is([I|Is]) ->
+ false = is_branch(I),
+ false = is_label(I),
+ assert_bb_is(Is).
+
remove_pred(HT, FromL, PredL) ->
case gb_trees:lookup(FromL, HT) of
{value, {Block, Succ, Preds}} ->
Code = hipe_bb:code(Block),
- NewCode = remove_pred_from_phis(Code, PredL, []),
+ NewCode = remove_pred_from_phis(PredL, Code),
NewBlock = hipe_bb:code_update(Block, NewCode),
gb_trees:update(FromL, {NewBlock,Succ,lists:delete(PredL,Preds)}, HT);
none ->
@@ -374,20 +415,20 @@ add_pred(HT, ToL, PredL) ->
-ifdef(CFG_CAN_HAVE_PHI_NODES).
%% phi-instructions in a removed block's successors must be aware of
%% the change.
-remove_pred_from_phis(List = [I|Left], Label, Acc) ->
+remove_pred_from_phis(Label, List = [I|Left]) ->
case is_phi(I) of
- true ->
- NewAcc = [phi_remove_pred(I, Label)|Acc],
- remove_pred_from_phis(Left, Label, NewAcc);
+ true ->
+ NewI = phi_remove_pred(I, Label),
+ [NewI | remove_pred_from_phis(Label, Left)];
false ->
- lists:reverse(Acc) ++ List
+ List
end;
-remove_pred_from_phis([], _Label, Acc) ->
- lists:reverse(Acc).
+remove_pred_from_phis(_Label, []) ->
+ [].
-else.
%% this is used for code representations like those of back-ends which
%% do not have phi-nodes.
-remove_pred_from_phis(Code, _Label, _Acc) ->
+remove_pred_from_phis(_Label, Code) ->
Code.
-endif.
@@ -927,24 +968,52 @@ merge(BB, BB2, BB2_Label) ->
remove_unreachable_code(CFG) ->
Start = start_label(CFG),
- Reachable = find_reachable([Start], CFG, gb_sets:from_list([Start])),
- %% Reachable is an ordset: it comes from gb_sets:to_list/1.
- %% So use ordset:subtract instead of '--' below.
- Labels = ordsets:from_list(labels(CFG)),
- case ordsets:subtract(Labels, Reachable) of
- [] ->
- CFG;
+ %% No unreachable block will make another block reachable, so no fixpoint
+ %% looping is required
+ Reachable = find_reachable([], [Start], CFG, #{Start=>[]}),
+ case [L || L <- labels(CFG), not maps:is_key(L, Reachable)] of
+ [] -> CFG;
Remove ->
- NewCFG = lists:foldl(fun(X, Acc) -> bb_remove(Acc, X) end, CFG, Remove),
- remove_unreachable_code(NewCFG)
+ HT0 = CFG#cfg.table,
+ HT1 = lists:foldl(fun gb_trees:delete/2, HT0, Remove),
+ ReachableP = fun(Lbl) -> maps:is_key(Lbl, Reachable) end,
+ HT = gb_trees:map(fun(_,B)->prune_preds(B, ReachableP)end, HT1),
+ CFG#cfg{table=HT}
end.
-find_reachable([Label|Left], CFG, Acc) ->
- NewAcc = gb_sets:add(Label, Acc),
- Succ = succ(CFG, Label),
- find_reachable([X || X <- Succ, not gb_sets:is_member(X, Acc)] ++ Left,
- CFG, NewAcc);
-find_reachable([], _CFG, Acc) ->
- gb_sets:to_list(Acc).
+find_reachable([], [], _CFG, Acc) -> Acc;
+find_reachable([Succ|Succs], Left, CFG, Acc) ->
+ case Acc of
+ #{Succ := _} -> find_reachable(Succs, Left, CFG, Acc);
+ #{} -> find_reachable(Succs, [Succ|Left], CFG, Acc#{Succ => []})
+ end;
+find_reachable([], [Label|Left], CFG, Acc) ->
+ find_reachable(succ(CFG, Label), Left, CFG, Acc).
+
+%% Batch prune unreachable predecessors. Asymptotically faster than deleting
+%% unreachable blocks one at a time with bb_remove, at least when
+%% CFG_CAN_HAVE_PHI_NODES is undefined. Otherwise a phi_remove_preds might be
+%% needed to achieve that.
+prune_preds(B={Block, Succ, Preds}, ReachableP) ->
+ case lists:partition(ReachableP, Preds) of
+ {_, []} -> B;
+ {NewPreds, Unreach} ->
+ NewCode = remove_preds_from_phis(Unreach, hipe_bb:code(Block)),
+ {hipe_bb:code_update(Block, NewCode), Succ, NewPreds}
+ end.
+-ifdef(CFG_CAN_HAVE_PHI_NODES).
+remove_preds_from_phis(_, []) -> [];
+remove_preds_from_phis(Preds, List=[I|Left]) ->
+ case is_phi(I) of
+ false -> List;
+ true ->
+ NewI = lists:foldl(fun(L,IA)->phi_remove_pred(IA,L)end,
+ I, Preds),
+ [NewI | remove_preds_from_phis(Preds, Left)]
+ end.
+-else.
+remove_preds_from_phis(_, Code) -> Code.
-endif.
+
+-endif. %% -ifdef(REMOVE_UNREACHABLE_CODE)
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-01 21:00:52 +0000