aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/icode/hipe_icode_split_arith.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/icode/hipe_icode_split_arith.erl')
-rw-r--r--lib/hipe/icode/hipe_icode_split_arith.erl553
1 files changed, 553 insertions, 0 deletions
diff --git a/lib/hipe/icode/hipe_icode_split_arith.erl b/lib/hipe/icode/hipe_icode_split_arith.erl
new file mode 100644
index 0000000000..d59f9247fa
--- /dev/null
+++ b/lib/hipe/icode/hipe_icode_split_arith.erl
@@ -0,0 +1,553 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2004-2009. All Rights Reserved.
+%%
+%% The contents of this file are subject to the Erlang Public License,
+%% Version 1.1, (the "License"); you may not use this file except in
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%%
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%%
+%% %CopyrightEnd%
+%%
+%%-------------------------------------------------------------------
+%% File : hipe_icode_split_arith.erl
+%% Author : Tobias Lindahl <[email protected]>
+%% Description :
+%%
+%% Created : 12 Nov 2003 by Tobias Lindahl <[email protected]>
+%%-------------------------------------------------------------------
+-module(hipe_icode_split_arith).
+
+-export([cfg/3]).
+
+-include("../main/hipe.hrl").
+-include("hipe_icode.hrl").
+-include("../flow/cfg.hrl").
+
+-define(MIN_RATIO, 0.005).
+
+%%-------------------------------------------------------------------
+
+-spec cfg(#cfg{}, mfa(), comp_options()) -> #cfg{}.
+
+cfg(Cfg, _MFA, Options) ->
+ Icode = hipe_icode_cfg:cfg_to_linear(Cfg),
+ case proplists:get_bool(split_arith_unsafe, Options) of
+ true -> make_split_unsafe(Icode);
+ _ ->
+ case preprocess(Icode) of
+ {do_not_split, _Ratio} ->
+ Cfg;
+ {split, _Ratio, Icode1} ->
+ NewCfg = split(Icode1),
+ %% hipe_icode_cfg:pp(NewCfg),
+ NewCfg
+ end
+ end.
+
+check_nofix_const([Arg1|Arg2]) ->
+ case hipe_icode:is_const(Arg1) of
+ true ->
+ Val1 = hipe_tagscheme:fixnum_val(hipe_icode:const_value(Arg1)),
+ case hipe_tagscheme:is_fixnum(Val1) of
+ true ->
+ check_nofix_const(Arg2);
+ false -> {no}
+ end;
+ false ->
+ check_nofix_const(Arg2)
+ end;
+check_nofix_const([]) -> true.
+
+check_const([I|Left]) ->
+ case I of
+ #icode_call{} ->
+ case is_arith(I) of
+ true ->
+ Args = hipe_icode:call_args(I),
+ case check_nofix_const(Args) of
+ {no} -> {do_not_split};
+ _ -> check_const(Left)
+ end;
+ _ -> check_const(Left)
+ end;
+ _ -> check_const(Left)
+ end;
+check_const([]) -> {yes}.
+
+make_split_unsafe(Icode) ->
+ LinearCode = hipe_icode:icode_code(Icode),
+ NewLinearCode = change_unsafe(LinearCode),
+ NewIcode = hipe_icode:icode_code_update(Icode, NewLinearCode),
+ hipe_icode_cfg:linear_to_cfg(NewIcode).
+
+change_unsafe([I|Is]) ->
+ case I of
+ #icode_call{} ->
+ case is_arith_extra_unsafe(I) of
+ true ->
+ NewOp = arithop_to_extra_unsafe(hipe_icode:call_fun(I)),
+ NewI1 = hipe_icode:call_fun_update(I, NewOp),
+ [NewI1|change_unsafe(Is)];
+ false ->
+ [I|change_unsafe(Is)]
+ end;
+ _ ->
+ [I|change_unsafe(Is)]
+ end;
+change_unsafe([]) -> [].
+
+preprocess(Icode) ->
+ LinearCode = hipe_icode:icode_code(Icode),
+ case check_const(LinearCode) of
+ {do_not_split} -> %%io:format("NO FIXNUM....."),
+ {do_not_split, 1.9849}; % Ratio val is ignored
+ _ ->
+ {NofArith, NofIns, NewLinearCode} = preprocess_code(LinearCode),
+ case NofArith / NofIns of
+ X when X >= ?MIN_RATIO ->
+ NewIcode = hipe_icode:icode_code_update(Icode, NewLinearCode),
+ {split, X, NewIcode};
+ Y ->
+ {do_not_split, Y}
+ end
+ end.
+
+preprocess_code([H|Code]) ->
+ preprocess_code(Code, 0, 0, [H]).
+
+preprocess_code([I|Left], NofArith, NofIns, CodeAcc = [PrevI|_]) ->
+ case I of
+ #icode_call{} ->
+ case is_arith(I) of
+ true ->
+ %% Note that we need to put these instructions in a separate
+ %% basic block since we need the ability to fail to these
+ %% instructions, but also fail from them. The basic block
+ %% merger will take care of unnecessary splits.
+
+ %% If call is an arithmetic operation replace the operation
+ %% with the specified replacement operator.
+ NewOp = arithop_to_split(hipe_icode:call_fun(I)),
+ NewI = hipe_icode:call_fun_update(I, NewOp),
+ case hipe_icode:is_label(PrevI) of
+ true ->
+ case (Left =:= []) orelse hipe_icode:is_label(hd(Left)) of
+ true ->
+ preprocess_code(Left, NofArith+1, NofIns+1, [NewI|CodeAcc]);
+ false ->
+ NewLabel = hipe_icode:mk_new_label(),
+ NewLabelName = hipe_icode:label_name(NewLabel),
+ NewI1 = hipe_icode:call_set_continuation(NewI, NewLabelName),
+ preprocess_code(Left, NofArith+1, NofIns+1,
+ [NewLabel, NewI1|CodeAcc])
+ end;
+ false ->
+ RevPreCode =
+ case hipe_icode:is_branch(PrevI) of
+ true ->
+ [hipe_icode:mk_new_label()];
+ false ->
+ NewLabel1 = hipe_icode:mk_new_label(),
+ NewLabelName1 = hipe_icode:label_name(NewLabel1),
+ [NewLabel1, hipe_icode:mk_goto(NewLabelName1)]
+ end,
+ case (Left =:= []) orelse hipe_icode:is_label(hd(Left)) of
+ true ->
+ preprocess_code(Left, NofArith+1, NofIns+1,
+ [NewI|RevPreCode] ++ CodeAcc);
+ false ->
+ NewLabel2 = hipe_icode:mk_new_label(),
+ NewLabelName2 = hipe_icode:label_name(NewLabel2),
+ NewI1 = hipe_icode:call_set_continuation(NewI, NewLabelName2),
+ preprocess_code(Left, NofArith+1, NofIns+1,
+ [NewLabel2, NewI1|RevPreCode] ++ CodeAcc)
+ end
+ end;
+ false ->
+ preprocess_code(Left, NofArith, NofIns + 1, [I|CodeAcc])
+ end;
+ #icode_label{} ->
+ %% Don't count labels as instructions.
+ preprocess_code(Left, NofArith, NofIns, [I|CodeAcc]);
+ _ ->
+ preprocess_code(Left, NofArith, NofIns+1, [I|CodeAcc])
+ end;
+preprocess_code([], NofArith, NofIns, CodeAcc) ->
+ {NofArith, NofIns, lists:reverse(CodeAcc)}.
+
+split(Icode) ->
+ LinearCode = hipe_icode:icode_code(Icode),
+ %% create a new icode label for each existing icode label
+ %% create mappings, NewToOld and OldToNew.
+ AllLabels = lists:foldl(fun(I, Acc) ->
+ case hipe_icode:is_label(I) of
+ true -> [hipe_icode:label_name(I)|Acc];
+ false -> Acc
+ end
+ end, [], LinearCode),
+ {OldToNewMap, NewToOldMap} = new_label_maps(AllLabels),
+
+ %% the call below doubles the number of basic blocks with the new
+ %% labels instead of the old.
+
+ NewLinearCode = map_code(LinearCode, OldToNewMap),
+ NewIcode = hipe_icode:icode_code_update(Icode, NewLinearCode),
+ NewCfg = hipe_icode_cfg:linear_to_cfg(NewIcode),
+ NewCfg2 =
+ insert_tests(NewCfg, [gb_trees:get(X, OldToNewMap) || X<-AllLabels],
+ NewToOldMap, OldToNewMap),
+ %% io:format("split(Cfg): Inserting testsL Done\n", []),
+ NewCfg2.
+
+map_code(OldCode, LabelMap) ->
+ AddedCode = map_code(OldCode, none, LabelMap, []),
+ OldCode ++ AddedCode.
+
+map_code([I|Left], ArithFail, LabelMap, Acc) ->
+ case I of
+ #icode_call{} ->
+ case is_arith(I) of
+ true ->
+ case hipe_icode:defines(I) of
+ []->
+ map_code(Left, ArithFail, LabelMap, [redirect(I, LabelMap)|Acc]);
+ _ ->
+ NewOp = split_to_unsafe(I),
+ NewI1 = hipe_icode:call_fun_update(I, NewOp),
+ NewI2 = redirect(NewI1, LabelMap),
+ NewI3 = hipe_icode:call_set_fail_label(NewI2, ArithFail),
+ map_code(Left, ArithFail, LabelMap, [NewI3|Acc])
+ end;
+ false ->
+ map_code(Left, ArithFail, LabelMap, [redirect(I, LabelMap)|Acc])
+ end;
+ #icode_label{} ->
+ LabelName = hipe_icode:label_name(I),
+ NewLabel = hipe_icode:mk_label(gb_trees:get(LabelName, LabelMap)),
+ map_code(Left, LabelName, LabelMap, [NewLabel|Acc]);
+ _ ->
+ map_code(Left, ArithFail, LabelMap, [redirect(I, LabelMap)|Acc])
+ end;
+map_code([], _ArithFail, _LabelMap, Acc) ->
+ lists:reverse(Acc).
+
+insert_tests(Cfg, Labels,NewToOldMap, OldToNewMap) ->
+ InfoMap = infomap_init(Labels),
+ %%io:format("insert_tests/3: Finding testpoints ...\n", []),
+ NewInfoMap = find_testpoints(Cfg, Labels, InfoMap),
+ %%io:format("insert_tests/3: Finding testpoints: Done\n", []),
+ %%io:format("insert_tests/3: Infomap: ~w\n", [gb_trees:to_list(NewInfoMap)]),
+ make_tests(Cfg, NewInfoMap, NewToOldMap, OldToNewMap).
+
+find_testpoints(Cfg, Labels, InfoMap) ->
+ case find_testpoints(Labels, InfoMap, Cfg, false) of
+ {dirty, NewInfoMap} ->
+ %%io:format("find_testpoints/3: Looping\n", []),
+ find_testpoints(Cfg, Labels, NewInfoMap);
+ fixpoint ->
+ InfoMap
+ end.
+
+find_testpoints([Lbl|Left], InfoMap, Cfg, Dirty) ->
+ Code = hipe_bb:code(hipe_icode_cfg:bb(Cfg, Lbl)),
+ InfoOut = join_info(hipe_icode_cfg:succ(Cfg, Lbl), InfoMap),
+ OldInfoIn = infomap_get_all(Lbl, InfoMap),
+ NewInfoIn = traverse_code(lists:reverse(Code), InfoOut),
+ case (gb_sets:is_subset(OldInfoIn, NewInfoIn) andalso
+ gb_sets:is_subset(NewInfoIn, OldInfoIn)) of
+ true ->
+ find_testpoints(Left, InfoMap, Cfg, Dirty);
+ false ->
+ %%io:format("find_testpoints/4: Label: ~w: OldMap ~w\nNewMap: ~w\n",
+ %% [Lbl, gb_sets:to_list(OldInfoIn), gb_sets:to_list(NewInfoIn)]),
+ NewInfoMap = gb_trees:update(Lbl, NewInfoIn, InfoMap),
+ find_testpoints(Left, NewInfoMap, Cfg, true)
+ end;
+find_testpoints([], InfoMap, _Cfg, Dirty) ->
+ if Dirty -> {dirty, InfoMap};
+ true -> fixpoint
+ end.
+
+traverse_code([I|Left], Info) ->
+ NewInfo = kill_defines(I, Info),
+ case I of
+ #icode_call{} ->
+ case is_unsafe_arith(I) of
+ true ->
+ %% The dst is sure to be a fixnum. Remove the 'killed' mark.
+ Dst = hd(hipe_icode:call_dstlist(I)),
+ NewInfo1 = gb_sets:delete_any({killed, Dst}, NewInfo),
+ NewInfo2 =
+ gb_sets:union(NewInfo1, gb_sets:from_list(hipe_icode:uses(I))),
+ traverse_code(Left, NewInfo2);
+ false ->
+ traverse_code(Left, NewInfo)
+ end;
+ #icode_move{} ->
+ Dst = hipe_icode:move_dst(I),
+ case gb_sets:is_member(Dst, Info) of
+ true ->
+ %% The dst is an argument to an arith op. Transfer the test
+ %% to the src and remove the 'killed' mark from the dst.
+ NewInfo1 = gb_sets:delete({killed, Dst}, NewInfo),
+ Src = hipe_icode:move_src(I),
+ case hipe_icode:is_const(Src) of
+ true ->
+ traverse_code(Left, NewInfo1);
+ false ->
+ NewInfo2 = gb_sets:add(Src, NewInfo1),
+ traverse_code(Left, NewInfo2)
+ end;
+ false ->
+ traverse_code(Left, NewInfo)
+ end;
+ _ ->
+ traverse_code(Left, NewInfo)
+ end;
+traverse_code([], Info) ->
+ Info.
+
+kill_defines(I, Info) ->
+ Defines = hipe_icode:defines(I),
+ case [X || X<-Defines, gb_sets:is_member(X, Info)] of
+ [] ->
+ Info;
+ List ->
+ TmpInfo = gb_sets:difference(Info, gb_sets:from_list(List)),
+ gb_sets:union(gb_sets:from_list([{killed, X} || X <- List]), TmpInfo)
+ end.
+
+make_tests(Cfg, InfoMap, NewToOldMap, OldToNewMap) ->
+ %%io:format("make_tests 0:\n",[]),
+ WorkList = make_worklist(gb_trees:keys(NewToOldMap), InfoMap,
+ NewToOldMap, Cfg, []),
+ %%io:format("make_tests 1:Worklist: ~w\n",[WorkList]),
+ NewCfg = make_tests(WorkList, Cfg),
+ %%io:format("make_tests 2\n",[]),
+ %% If the arguments to this function are used in unsafe arith
+ %% they should be marked as killed by a new start block.
+ Args = hipe_icode_cfg:params(NewCfg),
+ Start = hipe_icode_cfg:start_label(NewCfg),
+ AltStart = gb_trees:get(Start, OldToNewMap),
+ UnsafeIn = gb_sets:to_list(infomap_get(AltStart, InfoMap)),
+ case [X || X <- UnsafeIn, Y <- Args, X =:= Y] of
+ [] ->
+ hipe_icode_cfg:start_label_update(NewCfg, AltStart);
+ KilledArgs ->
+ NewStart = hipe_icode:label_name(hipe_icode:mk_new_label()),
+ NewCfg1 = insert_test_block(NewStart, AltStart, Start,
+ KilledArgs, NewCfg),
+ hipe_icode_cfg:start_label_update(NewCfg1, NewStart)
+ end.
+
+make_worklist([Lbl|Left], InfoMap, LabelMap, Cfg, Acc) ->
+ Vars = infomap_get_killed(Lbl, InfoMap),
+ case gb_sets:is_empty(Vars) of
+ true -> make_worklist(Left, InfoMap, LabelMap, Cfg, Acc);
+ false ->
+ %% io:format("make_worklist 1 ~w\n", [Vars]),
+ NewAcc0 =
+ [{Lbl, Succ, gb_trees:get(Succ, LabelMap),
+ gb_sets:intersection(infomap_get(Succ, InfoMap), Vars)}
+ || Succ <- hipe_icode_cfg:succ(Cfg, Lbl)],
+ NewAcc = [{Label, Succ, FailLbl, gb_sets:to_list(PrunedVars)}
+ || {Label, Succ, FailLbl, PrunedVars} <- NewAcc0,
+ gb_sets:is_empty(PrunedVars) =:= false] ++ Acc,
+ %% io:format("make_worklist 2\n", []),
+ make_worklist(Left, InfoMap, LabelMap, Cfg, NewAcc)
+ end;
+make_worklist([], _InfoMap, _LabelMap, _Cfg, Acc) ->
+ Acc.
+
+make_tests([{FromLbl, ToLbl, FailLbl, Vars}|Left], Cfg) ->
+ NewLbl = hipe_icode:label_name(hipe_icode:mk_new_label()),
+ TmpCfg = insert_test_block(NewLbl, ToLbl, FailLbl, Vars, Cfg),
+ NewCfg = hipe_icode_cfg:redirect(TmpCfg, FromLbl, ToLbl, NewLbl),
+ make_tests(Left, NewCfg);
+make_tests([], Cfg) ->
+ Cfg.
+
+insert_test_block(NewLbl, Succ, FailLbl, Vars, Cfg) ->
+ Code = [hipe_icode:mk_type(Vars, fixnum, Succ, FailLbl, 0.99)],
+ BB = hipe_bb:mk_bb(Code),
+ hipe_icode_cfg:bb_add(Cfg, NewLbl, BB).
+
+infomap_init(Labels) ->
+ infomap_init(Labels, gb_trees:empty()).
+
+infomap_init([Lbl|Left], Map) ->
+ infomap_init(Left, gb_trees:insert(Lbl, gb_sets:empty(), Map));
+infomap_init([], Map) ->
+ Map.
+
+join_info(Labels, Map) ->
+ join_info(Labels, Map, gb_sets:empty()).
+
+join_info([Lbl|Left], Map, Set) ->
+ join_info(Left, Map, gb_sets:union(Set, infomap_get(Lbl, Map)));
+join_info([], _Map, Set) ->
+ Set.
+
+infomap_get(Lbl, Map) ->
+ case gb_trees:lookup(Lbl, Map) of
+ none -> gb_sets:empty();
+ {value, Val} ->
+ gb_sets:filter(fun(X) -> case X of
+ {killed, _} -> false;
+ _ -> true
+ end
+ end,
+ Val)
+ end.
+
+infomap_get_all(Lbl, Map) ->
+ case gb_trees:lookup(Lbl, Map) of
+ none -> gb_sets:empty();
+ {value, Val} -> Val
+ end.
+
+infomap_get_killed(Lbl, Map) ->
+ case gb_trees:lookup(Lbl, Map) of
+ none -> gb_sets:empty();
+ {value, Val} ->
+ Fun = fun(X, Acc) ->
+ case X of
+ {killed, Var} -> [Var|Acc];
+ _ -> Acc
+ end
+ end,
+ gb_sets:from_list(lists:foldl(Fun, [], gb_sets:to_list(Val)))
+ end.
+
+%%%-------------------------------------------------------------------
+%%% General replace of '+'/'-' to super safe version
+
+arithop_to_split(Op) ->
+ case Op of
+ '+' -> gen_add;
+ '-' -> gen_sub;
+ _ -> Op
+ end.
+
+%%%-------------------------------------------------------------------
+%%% Check if it's an arith op that needs to be split
+
+is_arith(I) ->
+ case hipe_icode:call_fun(I) of
+ '+' -> true;
+ '-' -> true;
+ gen_add -> true;
+ gen_sub -> true;
+ 'bor' -> true;
+ 'bxor' -> true;
+ 'bsr' ->
+ %% Need to check that the second argument is a non-negative
+ %% fixnum. We only allow for constants to simplify things.
+ [_, Arg2] = hipe_icode:args(I),
+ hipe_icode:is_const(Arg2) andalso (hipe_icode:const_value(Arg2) >= 0);
+ 'bsl' ->
+ %% There are major issues with bsl since it doesn't flag
+ %% overflow. We cannot allow for this in this optimization pass.
+ false;
+ 'bnot' -> true;
+ 'band' -> true;
+ _ -> false
+ end.
+
+%%%-------------------------------------------------------------------
+
+is_unsafe_arith(I) ->
+ case hipe_icode:call_fun(I) of
+ unsafe_add -> true;
+ unsafe_sub -> true;
+ unsafe_bor -> true;
+ unsafe_bxor -> true;
+ unsafe_bsr -> true;
+ unsafe_bsl -> true;
+ unsafe_bnot -> true;
+ unsafe_band -> true;
+ _ -> false
+ end.
+
+split_to_unsafe(I) ->
+ case hipe_icode:call_fun(I) of
+ gen_add -> unsafe_add;
+ gen_sub -> unsafe_sub;
+ 'bor' -> unsafe_bor;
+ 'bxor' -> unsafe_bxor;
+ 'bsr' ->
+ case is_arith(I) of
+ true -> unsafe_bsr;
+ false -> 'bsr'
+ end;
+ 'bsl' ->
+ %% There are major issues with bsl since it doesn't flag
+ %% overflow. We cannot allow for this in this optimization pass.
+ 'bsl';
+ 'bnot' -> unsafe_bnot;
+ 'band' -> unsafe_band;
+ Op -> Op
+ end.
+
+%%%-------------------------------------------------------------------
+%%% FLAG = split_arith_unsafe
+
+is_arith_extra_unsafe(I) ->
+ case hipe_icode:call_fun(I) of
+ '+' -> true;
+ '-' -> true;
+ 'bor' -> true;
+ 'bxor' -> true;
+ 'bsr' -> is_arith(I);
+ 'bsl' -> false; %% See comment in is_arith/1
+ 'bnot' -> true;
+ 'band' -> true;
+ _ -> false
+ end.
+
+arithop_to_extra_unsafe(Op) ->
+ case Op of
+ '+' -> extra_unsafe_add;
+ '-' -> extra_unsafe_sub;
+ 'bor' -> unsafe_bor;
+ 'bxor' -> unsafe_bxor;
+ 'bsr' -> unsafe_bsr;
+ 'bsl' -> 'bsl'; %% See comment in split_to_unsafe/1
+ 'bnot' -> unsafe_bnot;
+ 'band' -> unsafe_band
+ end.
+
+%%%-------------------------------------------------------------------
+
+redirect(I, LabelMap) ->
+ case hipe_icode:successors(I) of
+ [] -> I;
+ Successors ->
+ RedirectMap = [{X, gb_trees:get(X, LabelMap)} || X <- Successors],
+ redirect_1(RedirectMap, I)
+ end.
+
+redirect_1([{From, To}|Left], I) ->
+ redirect_1(Left, hipe_icode:redirect_jmp(I, From, To));
+redirect_1([], I) ->
+ I.
+
+new_label_maps(Labels) ->
+ new_label_maps(Labels, gb_trees:empty(), gb_trees:empty()).
+
+new_label_maps([Lbl|Left], Map1, Map2) ->
+ NewLabel = hipe_icode:label_name(hipe_icode:mk_new_label()),
+ NewMap1 = gb_trees:insert(Lbl, NewLabel, Map1),
+ NewMap2 = gb_trees:insert(NewLabel, Lbl, Map2),
+ new_label_maps(Left, NewMap1, NewMap2);
+new_label_maps([], Map1, Map2) ->
+ {Map1, Map2}.