aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/rtl/hipe_rtl_mk_switch.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/rtl/hipe_rtl_mk_switch.erl')
-rw-r--r--lib/hipe/rtl/hipe_rtl_mk_switch.erl985
1 files changed, 985 insertions, 0 deletions
diff --git a/lib/hipe/rtl/hipe_rtl_mk_switch.erl b/lib/hipe/rtl/hipe_rtl_mk_switch.erl
new file mode 100644
index 0000000000..e5175217d6
--- /dev/null
+++ b/lib/hipe/rtl/hipe_rtl_mk_switch.erl
@@ -0,0 +1,985 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2001-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%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Copyright (c) 2001 by Erik Johansson. All Rights Reserved
+%% ====================================================================
+%% Filename : hipe_rtl_mk_switch.erl
+%% Module : hipe_rtl_mk_switch
+%% Purpose : Implements switching on Erlang values.
+%% Notes : Only fixnums are supported well,
+%% atoms work with table search,
+%% the inline search of atoms might have some bugs.
+%% Should be extended to handle bignums and floats.
+%%
+%% History : * 2001-02-28 Erik Johansson ([email protected]):
+%% Created.
+%% * 2001-04-01 Erik Trulsson ([email protected]):
+%% Stefan Lindstr�m ([email protected]):
+%% Added clustering and inlined binary search trees.
+%% * 2001-07-30 EJ ([email protected]):
+%% Fixed some bugs and started cleanup.
+%% ====================================================================
+%% Exports :
+%% gen_switch_val(I, VarMap, ConstTab, Options)
+%% gen_switch_tuple(I, Map, ConstTab, Options)
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-module(hipe_rtl_mk_switch).
+
+-export([gen_switch_val/4, gen_switch_tuple/4]).
+
+%%-------------------------------------------------------------------------
+
+-include("../main/hipe.hrl").
+
+%%-------------------------------------------------------------------------
+
+-define(MINFORJUMPTABLE,9).
+ % Minimum number of integers needed to use something else than an inline search.
+-define(MINFORINTSEARCHTREE,65). % Must be at least 3
+ % Minimum number of integer elements needed to use a non-inline binary search.
+
+-define(MININLINEATOMSEARCH,8).
+ % Minimum number of atoms needed to use an inline binary search instead
+ % of a fast linear search.
+
+-define(MINFORATOMSEARCHTREE,20). % Must be at least 3
+ % Minimum number of atoms needed to use a non-inline binary search instead
+ % of a linear search.
+
+-define(MAXINLINEATOMSEARCH,64). % Must be at least 3
+ % The cutoff point between inlined and non-inlined binary search for atoms
+
+-define(WORDSIZE, hipe_rtl_arch:word_size()).
+-define(MINDENSITY, 0.5).
+ % Minimum density required to use a jumptable instead of a binary search.
+
+%% The reason why MINFORINTSEARCHTREE and MINFORATOMSEARCHTREE must be
+%% at least 3 is that the function tab/5 will enter an infinite loop
+%% and hang when faced with a switch of size 1 or 2.
+
+
+%% Options used by this module:
+%%
+%% [no_]use_indexing
+%% Determines if any indexing be should be done at all. Turned on
+%% by default at optimization level o2 and higher.
+%%
+%% [no_]use_clusters
+%% Controls whether we attempt to divide sparse integer switches
+%% into smaller dense clusters for which jumptables are practical.
+%% Turned off by default since it can increase compilation time
+%% considerably and most programs will gain little benefit from it.
+%%
+%% [no_]use_inline_atom_search
+%% Controls whether we use an inline binary search for small number
+%% of atoms. Turned off by default since this is currently only
+%% supported on SPARC (and not on x86) and probably needs a bit
+%% more testing before it can be turned on by default.
+
+gen_switch_val(I, VarMap, ConstTab, Options) ->
+ case proplists:get_bool(use_indexing, Options) of
+ false -> gen_slow_switch_val(I, VarMap, ConstTab, Options);
+ true -> gen_fast_switch_val(I, VarMap, ConstTab, Options)
+ end.
+
+gen_fast_switch_val(I, VarMap, ConstTab, Options) ->
+ {Arg, VarMap0} =
+ hipe_rtl_varmap:icode_var2rtl_var(hipe_icode:switch_val_term(I), VarMap),
+ IcodeFail = hipe_icode:switch_val_fail_label(I),
+ {Fail, VarMap1} = hipe_rtl_varmap:icode_label2rtl_label(IcodeFail, VarMap0),
+ %% Important that the list of cases is sorted when handling integers.
+ UnsortedCases = hipe_icode:switch_val_cases(I),
+ Cases = lists:sort(UnsortedCases),
+
+ check_duplicates(Cases),
+ %% This check is currently not really necessary. The checking
+ %% happens at an earlier phase of the compilation.
+ {Types, InitCode} = split_types(Cases, Arg),
+ handle_types(Types, InitCode, VarMap1, ConstTab, Arg, {I, Fail, Options}).
+
+handle_types([{Type,Lbl,Cases}|Types], Code, VarMap, ConstTab, Arg, Info) ->
+ {Code1,VarMap1,ConstTab1} = gen_fast_switch_on(Type, Cases,
+ VarMap,
+ ConstTab, Arg, Info),
+ handle_types(Types, [Code,Lbl,Code1], VarMap1, ConstTab1, Arg, Info);
+handle_types([], Code, VarMap, ConstTab, _, _) ->
+ {Code, VarMap, ConstTab}.
+
+
+gen_fast_switch_on(integer, Cases, VarMap, ConstTab, Arg, {I, Fail, Options}) ->
+ {First,_} = hd(Cases),
+ Min = hipe_icode:const_value(First),
+ if length(Cases) < ?MINFORJUMPTABLE ->
+ gen_small_switch_val(Arg,Cases,Fail,VarMap,ConstTab,Options);
+ true ->
+ case proplists:get_bool(use_clusters, Options) of
+ false ->
+ M = list_to_tuple(Cases),
+ D = density(M, 1, tuple_size(M)),
+ if
+ D >= ?MINDENSITY ->
+ gen_jump_table(Arg,Fail,hipe_icode:switch_val_fail_label(I),VarMap,ConstTab,Cases,Min);
+ true ->
+ gen_search_switch_val(Arg, Cases, Fail, VarMap, ConstTab, Options)
+ end;
+ true ->
+ MC = minclusters(Cases),
+ Cl = cluster_split(Cases,MC),
+ CM = cluster_merge(Cl),
+ find_cluster(CM,VarMap,ConstTab,Options,Arg,Fail,hipe_icode:switch_val_fail_label(I))
+ end
+ end;
+gen_fast_switch_on(atom, Cases, VarMap, ConstTab, Arg, {_I, Fail, Options}) ->
+ case proplists:get_bool(use_inline_atom_search, Options) of
+ true ->
+ if
+ length(Cases) < ?MININLINEATOMSEARCH ->
+ gen_linear_switch_val(Arg, Cases, Fail, VarMap, ConstTab, Options);
+ length(Cases) > ?MAXINLINEATOMSEARCH ->
+ gen_search_switch_val(Arg, Cases, Fail, VarMap, ConstTab, Options);
+ true ->
+ gen_atom_switch_val(Arg,Cases,Fail,VarMap,ConstTab,Options)
+ end;
+ false ->
+ if length(Cases) < ?MINFORATOMSEARCHTREE ->
+ gen_linear_switch_val(Arg, Cases, Fail, VarMap, ConstTab, Options);
+ true ->
+ gen_search_switch_val(Arg, Cases, Fail, VarMap, ConstTab, Options)
+ end
+ end;
+gen_fast_switch_on(_, _, VarMap, ConstTab, _, {I,_Fail,Options}) ->
+ %% We can only handle smart indexing of integers and atoms
+ %% TODO: Consider bignum
+ gen_slow_switch_val(I, VarMap, ConstTab, Options).
+
+
+%% Split different types into separate switches.
+split_types([Case|Cases], Arg) ->
+ Type1 = casetype(Case),
+ Types = split(Cases,Type1,[Case],[]),
+ switch_on_types(Types,[], [], Arg);
+split_types([],_) ->
+ %% Cant happen.
+ ?EXIT({empty_caselist}).
+
+switch_on_types([{Type,Cases}], AccCode, AccCases, _Arg) ->
+ Lbl = hipe_rtl:mk_new_label(),
+ I = hipe_rtl:mk_goto(hipe_rtl:label_name(Lbl)),
+ {[{Type,Lbl,lists:reverse(Cases)} | AccCases], lists:reverse([I|AccCode])};
+switch_on_types([{other,Cases} | Rest], AccCode, AccCases, Arg) ->
+ %% Make sure the general case is handled last.
+ switch_on_types(Rest ++ [{other,Cases}], AccCode, AccCases, Arg);
+switch_on_types([{Type,Cases} | Rest], AccCode, AccCases, Arg) ->
+ TLab = hipe_rtl:mk_new_label(),
+ FLab = hipe_rtl:mk_new_label(),
+ TestCode =
+ case Type of
+ integer ->
+ hipe_tagscheme:test_fixnum(Arg, hipe_rtl:label_name(TLab),
+ hipe_rtl:label_name(FLab), 0.5);
+ atom ->
+ hipe_tagscheme:test_atom(Arg, hipe_rtl:label_name(TLab),
+ hipe_rtl:label_name(FLab), 0.5);
+ bignum ->
+ hipe_tagscheme:test_bignum(Arg, hipe_rtl:label_name(TLab),
+ hipe_rtl:label_name(FLab), 0.5);
+ _ -> ?EXIT({ooops, type_not_handled, Type})
+ end,
+ switch_on_types(Rest, [[TestCode,FLab] | AccCode],
+ [{Type,TLab,lists:reverse(Cases)} | AccCases], Arg).
+
+split([Case|Cases], Type, Current, Rest) ->
+ case casetype(Case) of
+ Type ->
+ split(Cases, Type, [Case|Current],Rest);
+ Other ->
+ split(Cases, Other, [Case], [{Type,Current}|Rest])
+ end;
+split([], Type, Current, Rest) ->
+ [{Type, Current} | Rest].
+
+%% Determine what type an entry in the caselist has
+
+casetype({Const,_}) ->
+ casetype(hipe_icode:const_value(Const));
+casetype(A) ->
+ if
+ is_integer(A) ->
+ case hipe_tagscheme:is_fixnum(A) of
+ true -> integer;
+ false -> bignum
+ end;
+ is_float(A) -> float;
+ is_atom(A) -> atom;
+ true -> other
+ end.
+
+%% check that no duplicate values occur in the case list and also
+%% check that all case values have the same type.
+check_duplicates([]) -> true;
+check_duplicates([_]) -> true;
+check_duplicates([{Const1,_},{Const2,L2}|T]) ->
+ C1 = hipe_icode:const_value(Const1),
+ C2 = hipe_icode:const_value(Const2),
+ %% T1 = casetype(C1),
+ %% T2 = casetype(C2),
+ if C1 =/= C2 -> %% , T1 =:= T2 ->
+ check_duplicates([{Const2,L2}|T]);
+ true ->
+ ?EXIT({bad_values_in_switchval,C1})
+ end.
+
+%%
+%% Determine the optimal way to divide Cases into clusters such that each
+%% cluster is dense.
+%%
+%% See:
+%% Producing Good Code for the Case Statement, Robert L. Bernstein
+%% Software - Practice and Experience vol 15, 1985, no 10, pp 1021--1024
+%% And
+%% Correction to "Producing Good Code for the Case Statement"
+%% Sampath Kannan and Todd A. Proebsting,
+%% Software - Practice and Experience vol 24, 1994, no 2, p 233
+%%
+%% (The latter is where the algorithm comes from.)
+
+%% This function will return a tuple with the first element being 0
+%% The rest of the elements being integers. A value of M at index N
+%% (where the first element is considered to have index 0) means that
+%% the first N cases can be divided into M (but no fewer) clusters where
+%% each cluster is dense.
+
+minclusters(Cases) when is_list(Cases) ->
+ minclusters(list_to_tuple(Cases));
+minclusters(Cases) when is_tuple(Cases) ->
+ N = tuple_size(Cases),
+ MinClusters = list_to_tuple([0|n_list(N,inf)]),
+ i_loop(1,N,MinClusters,Cases).
+
+%% Create a list with N elements initialized to Init
+n_list(0,_) -> [];
+n_list(N,Init) -> [Init | n_list(N-1,Init)].
+
+%% Do the dirty work of minclusters
+i_loop(I,N,MinClusters,_Cases) when I > N ->
+ MinClusters;
+i_loop(I,N,MinClusters,Cases) when I =< N ->
+ M = j_loop(0, I-1, MinClusters, Cases),
+ i_loop(I+1, N, M, Cases).
+
+%% More dirty work
+j_loop(J,I1,MinClusters,_Cases) when J > I1 ->
+ MinClusters;
+j_loop(J,I1,MinClusters,Cases) when J =< I1 ->
+ D = density(Cases,J+1,I1+1),
+ A0 = element(J+1,MinClusters),
+ A = if
+ is_number(A0) ->
+ A0+1;
+ true ->
+ A0
+ end,
+ B = element(I1+2,MinClusters),
+ M = if
+ D >= ?MINDENSITY, A<B ->
+ setelement(I1+2,MinClusters,A);
+ true ->
+ MinClusters
+ end,
+ j_loop(J+1,I1,M,Cases).
+
+
+%% Determine the density of a (subset of a) case list
+%% A is a tuple with the cases in order from smallest to largest
+%% I is the index of the first element and J of the last
+
+density(A,I,J) ->
+ {AI,_} = element(I,A),
+ {AJ,_} = element(J,A),
+ (J-I+1)/(hipe_icode:const_value(AJ)-hipe_icode:const_value(AI)+1).
+
+
+%% Split a case list into dense clusters
+%% Returns a list of lists of cases.
+%%
+%% Cases is the case list and Clust is a list describing the optimal
+%% clustering as returned by minclusters
+%%
+%% If the value in the last place in minclusters is M then we can
+%% split the case list into M clusters. We then search for the last
+%% (== right-most) occurance of the value M-1 in minclusters. That
+%% indicates the largest number of cases that can be split into M-1
+%% clusters. This means that the cases in between constitute one
+%% cluster. Then we recurse on the remainder of the cases.
+%%
+%% The various calls to lists:reverse are just to ensure that the
+%% cases remain in the correct, sorted order.
+
+cluster_split(Cases, Clust) ->
+ A = tl(tuple_to_list(Clust)),
+ Max = element(tuple_size(Clust), Clust),
+ L1 = lists:reverse(Cases),
+ L2 = lists:reverse(A),
+ cluster_split(Max, [], [], L1, L2).
+
+cluster_split(0, [], Res, Cases, _Clust) ->
+ L = lists:reverse(Cases),
+ {H,_} = hd(L),
+ {T,_} = hd(Cases),
+ [{dense,hipe_icode:const_value(H),hipe_icode:const_value(T),L}|Res];
+cluster_split(N, [], Res, Cases, [N|_] = Clust) ->
+ cluster_split(N-1, [], Res, Cases, Clust);
+cluster_split(N,Sofar,Res,Cases,[N|Clust]) ->
+ {H,_} = hd(Sofar),
+ {T,_} = lists:last(Sofar),
+ cluster_split(N-1,[],[{dense,hipe_icode:const_value(H),hipe_icode:const_value(T),Sofar}|Res],Cases,[N|Clust]);
+cluster_split(N,Sofar,Res,[C|Cases],[_|Clust]) ->
+ cluster_split(N,[C|Sofar],Res,Cases,Clust).
+
+%%
+%% Merge adjacent small clusters into larger sparse clusters
+%%
+cluster_merge([C]) -> [C];
+cluster_merge([{dense,Min,Max,C}|T]) when length(C) >= ?MINFORJUMPTABLE ->
+ C2 = cluster_merge(T),
+ [{dense,Min,Max,C}|C2];
+cluster_merge([{sparse,Min,_,C},{sparse,_,Max,D}|T]) ->
+ R = {sparse,Min,Max,C ++ D},
+ cluster_merge([R|T]);
+cluster_merge([{sparse,Min,_,C},{dense,_,Max,D}|T]) when length(D) < ?MINFORJUMPTABLE ->
+ R = {sparse,Min,Max,C ++ D},
+ cluster_merge([R|T]);
+cluster_merge([{dense,Min,_,C},{dense,_,Max,D}|T]) when length(C) < ?MINFORJUMPTABLE, length(D) < ?MINFORJUMPTABLE ->
+ R = {sparse,Min,Max,C ++ D},
+ cluster_merge([R|T]);
+cluster_merge([{dense,Min,_,D},{sparse,_,Max,C}|T]) when length(D) < ?MINFORJUMPTABLE ->
+ R = {sparse,Min,Max,C ++ D},
+ cluster_merge([R|T]);
+cluster_merge([A,{dense,Min,Max,C}|T]) when length(C) >= ?MINFORJUMPTABLE ->
+ R = cluster_merge([{dense,Min,Max,C}|T]),
+ [A|R].
+
+
+%% Generate code to search for the correct cluster
+
+find_cluster([{sparse,_Min,_Max,C}],VarMap,ConstTab,Options,Arg,Fail,_IcodeFail) ->
+ case length(C) < ?MINFORINTSEARCHTREE of
+ true ->
+ gen_small_switch_val(Arg,C,Fail,VarMap,ConstTab,Options);
+ _ ->
+ gen_search_switch_val(Arg,C,Fail,VarMap,ConstTab,Options)
+ end;
+find_cluster([{dense,Min,_Max,C}],VarMap,ConstTab,Options,Arg,Fail,IcodeFail) ->
+ case length(C) < ?MINFORJUMPTABLE of
+ true ->
+ gen_small_switch_val(Arg,C,Fail,VarMap,ConstTab,Options);
+ _ ->
+ gen_jump_table(Arg,Fail,IcodeFail,VarMap,ConstTab,C,Min)
+ end;
+find_cluster([{Density,Min,Max,C}|T],VarMap,ConstTab,Options,Arg,Fail,IcodeFail) ->
+ ClustLab = hipe_rtl:mk_new_label(),
+ NextLab = hipe_rtl:mk_new_label(),
+ {ClustCode,V1,C1} = find_cluster([{Density,Min,Max,C}],VarMap,ConstTab,Options,Arg,Fail,IcodeFail),
+
+ {Rest,V2,C2} = find_cluster(T,V1,C1,Options,Arg,Fail,IcodeFail),
+
+ {[
+ hipe_rtl:mk_branch(Arg, gt, hipe_rtl:mk_imm(hipe_tagscheme:mk_fixnum(Max)),
+ hipe_rtl:label_name(NextLab),
+ hipe_rtl:label_name(ClustLab), 0.50),
+ ClustLab
+ ] ++
+ ClustCode ++
+ [NextLab] ++
+ Rest,
+ V2,C2}.
+
+%% Generate efficient code for a linear search through the case list.
+%% Only works for atoms and integer.
+gen_linear_switch_val(Arg,Cases,Fail,VarMap,ConstTab,_Options) ->
+ {Values,_Labels} = split_cases(Cases),
+ {LabMap,VarMap1} = lbls_from_cases(Cases,VarMap),
+ Code = fast_linear_search(Arg,Values,LabMap,Fail),
+ {Code,VarMap1,ConstTab}.
+
+fast_linear_search(_Arg,[],[],Fail) ->
+ [hipe_rtl:mk_goto(hipe_rtl:label_name(Fail))];
+fast_linear_search(Arg,[Case|Cases],[Label|Labels],Fail) ->
+ Reg = hipe_rtl:mk_new_reg_gcsafe(),
+ NextLab = hipe_rtl:mk_new_label(),
+ C2 = fast_linear_search(Arg,Cases,Labels,Fail),
+ C1 =
+ if
+ is_integer(Case) ->
+ TVal = hipe_tagscheme:mk_fixnum(Case),
+ [
+ hipe_rtl:mk_move(Reg,hipe_rtl:mk_imm(TVal)),
+ hipe_rtl:mk_branch(Arg,eq,Reg,
+ Label,
+ hipe_rtl:label_name(NextLab), 0.5),
+ NextLab
+ ];
+ is_atom(Case) ->
+ [
+ hipe_rtl:mk_load_atom(Reg,Case),
+ hipe_rtl:mk_branch(Arg,eq,Reg,
+ Label,
+ hipe_rtl:label_name(NextLab), 0.5),
+ NextLab
+ ];
+ true -> % This should never happen !
+ ?EXIT({internal_error_in_switch_val,Case})
+ end,
+ [C1,C2].
+
+
+%% Generate code to search through a small cluster of integers using
+%% binary search
+gen_small_switch_val(Arg,Cases,Fail,VarMap,ConstTab,_Options) ->
+ {Values,_Labels} = split_cases(Cases),
+ {LabMap,VarMap1} = lbls_from_cases(Cases,VarMap),
+ Keys = [hipe_tagscheme:mk_fixnum(X) % Add tags to the values
+ || X <- Values],
+ Code = inline_search(Keys, LabMap, Arg, Fail),
+ {Code, VarMap1, ConstTab}.
+
+
+%% Generate code to search through a small cluster of atoms
+gen_atom_switch_val(Arg,Cases,Fail,VarMap,ConstTab,_Options) ->
+ {Values, _Labels} = split_cases(Cases),
+ {LabMap,VarMap1} = lbls_from_cases(Cases,VarMap),
+ LMap = [{label,L} || L <- LabMap],
+ {NewConstTab,Id} = hipe_consttab:insert_sorted_block(ConstTab, Values),
+ {NewConstTab2,LabId} =
+ hipe_consttab:insert_sorted_block(NewConstTab, word, LMap, Values),
+ Code = inline_atom_search(0, length(Cases)-1, Id, LabId, Arg, Fail, LabMap),
+ {Code, VarMap1, NewConstTab2}.
+
+
+%% calculate the middle position of a list (+ 1 because of 1-indexing of lists)
+get_middle(List) ->
+ N = length(List),
+ N div 2 + 1.
+
+%% get element [N1, N2] from a list
+get_cases(_, 0, 0) ->
+ [];
+get_cases([H|T], 0, N) ->
+ [H | get_cases(T, 0, N - 1)];
+get_cases([_|T], N1, N2) ->
+ get_cases(T, N1 - 1, N2 - 1).
+
+
+%% inline_search/4 creates RTL code for a inlined binary search.
+%% It requires two sorted tables - one with the keys to search
+%% through and one with the corresponding labels to jump to.
+%%
+%% Input:
+%% KeyList - A list of keys to search through.
+%% LableList - A list of labels to jump to.
+%% KeyReg - A register containing the key to search for.
+%% Default - A label to jump to if the key is not found.
+%%
+
+inline_search([], _LabelList, _KeyReg, _Default) -> [];
+inline_search(KeyList, LabelList, KeyReg, Default) ->
+ %% Create some registers and labels that we need.
+ Reg = hipe_rtl:mk_new_reg_gcsafe(),
+ Lab1 = hipe_rtl:mk_new_label(),
+ Lab2 = hipe_rtl:mk_new_label(),
+ Lab3 = hipe_rtl:mk_new_label(),
+
+ Length = length(KeyList),
+
+ if
+ Length >= 3 ->
+ %% Get middle element and keys/labels before that and after
+ Middle_pos = get_middle(KeyList),
+ Middle_key = lists:nth(Middle_pos, KeyList),
+ Keys_beginning = get_cases(KeyList, 0, Middle_pos - 1),
+ Labels_beginning = get_cases(LabelList, 0, Middle_pos - 1),
+ Keys_ending = get_cases(KeyList, Middle_pos, Length),
+ Labels_ending = get_cases(LabelList, Middle_pos, Length),
+
+ %% Create the code.
+
+ %% Get the label and build it up properly
+ Middle_label = lists:nth(Middle_pos, LabelList),
+
+ A = [hipe_rtl:mk_move(Reg, hipe_rtl:mk_imm(Middle_key)),
+ hipe_rtl:mk_branch(KeyReg, lt, Reg,
+ hipe_rtl:label_name(Lab2),
+ hipe_rtl:label_name(Lab1), 0.5),
+ Lab1,
+ hipe_rtl:mk_branch(KeyReg, gt, Reg,
+ hipe_rtl:label_name(Lab3),
+ Middle_label , 0.5),
+ Lab2],
+ %% build search tree for keys less than the middle element
+ B = inline_search(Keys_beginning, Labels_beginning, KeyReg, Default),
+ %% ...and for keys bigger than the middle element
+ D = inline_search(Keys_ending, Labels_ending, KeyReg, Default),
+
+ %% append the code and return it
+ A ++ B ++ [Lab3] ++ D;
+
+ Length =:= 2 ->
+ %% get the first and second elements and theirs labels
+ Key_first = hd(KeyList),
+ First_label = hd(LabelList),
+
+ %% Key_second = hipe_tagscheme:mk_fixnum(lists:nth(2, KeyList)),
+ Key_second = lists:nth(2, KeyList),
+ Second_label = lists:nth(2, LabelList),
+
+ NewLab = hipe_rtl:mk_new_label(),
+
+ %% compare them
+ A = [hipe_rtl:mk_move(Reg,hipe_rtl:mk_imm(Key_first)),
+ hipe_rtl:mk_branch(KeyReg, eq, Reg,
+ First_label,
+ hipe_rtl:label_name(NewLab) , 0.5),
+ NewLab],
+
+ B = [hipe_rtl:mk_move(Reg,hipe_rtl:mk_imm(Key_second)),
+ hipe_rtl:mk_branch(KeyReg, eq, Reg,
+ Second_label,
+ hipe_rtl:label_name(Default) , 0.5)],
+ A ++ B;
+
+ Length =:= 1 ->
+ Key = hd(KeyList),
+ Label = hd(LabelList),
+
+ [hipe_rtl:mk_move(Reg,hipe_rtl:mk_imm(Key)),
+ hipe_rtl:mk_branch(KeyReg, eq, Reg,
+ Label,
+ hipe_rtl:label_name(Default) , 0.5)]
+ end.
+
+
+inline_atom_search(Start, End, Block, LBlock, KeyReg, Default, Labels) ->
+ Reg = hipe_rtl:mk_new_reg_gcsafe(),
+
+ Length = (End - Start) + 1,
+
+ if
+ Length >= 3 ->
+ Lab1 = hipe_rtl:mk_new_label(),
+ Lab2 = hipe_rtl:mk_new_label(),
+ Lab3 = hipe_rtl:mk_new_label(),
+ Lab4 = hipe_rtl:mk_new_label(),
+
+ Mid = ((End-Start) div 2)+Start,
+ End1 = Mid-1,
+ Start1 = Mid+1,
+ A = [
+ hipe_rtl:mk_load_word_index(Reg,Block,Mid),
+ hipe_rtl:mk_branch(KeyReg, lt, Reg,
+ hipe_rtl:label_name(Lab2),
+ hipe_rtl:label_name(Lab1), 0.5),
+ Lab1,
+ hipe_rtl:mk_branch(KeyReg, gt, Reg,
+ hipe_rtl:label_name(Lab3),
+ hipe_rtl:label_name(Lab4), 0.5),
+ Lab4,
+ hipe_rtl:mk_goto_index(LBlock, Mid, Labels),
+ Lab2
+ ],
+ B = [inline_atom_search(Start,End1,Block,LBlock,KeyReg,Default,Labels)],
+ C = [inline_atom_search(Start1,End,Block,LBlock,KeyReg,Default,Labels)],
+ A ++ B ++ [Lab3] ++ C;
+
+ Length =:= 2 ->
+ L1 = hipe_rtl:mk_new_label(),
+ L2 = hipe_rtl:mk_new_label(),
+ L3 = hipe_rtl:mk_new_label(),
+ [
+ hipe_rtl:mk_load_word_index(Reg,Block,Start),
+ hipe_rtl:mk_branch(KeyReg,eq,Reg,
+ hipe_rtl:label_name(L1),
+ hipe_rtl:label_name(L2), 0.5),
+ L1,
+ hipe_rtl:mk_goto_index(LBlock,Start,Labels),
+
+ L2,
+ hipe_rtl:mk_load_word_index(Reg,Block,End),
+ hipe_rtl:mk_branch(KeyReg,eq,Reg,
+ hipe_rtl:label_name(L3),
+ hipe_rtl:label_name(Default), 0.5),
+ L3,
+ hipe_rtl:mk_goto_index(LBlock, End, Labels)
+ ];
+
+ Length =:= 1 ->
+ NewLab = hipe_rtl:mk_new_label(),
+ [
+ hipe_rtl:mk_load_word_index(Reg,Block,Start),
+ hipe_rtl:mk_branch(KeyReg, eq, Reg,
+ hipe_rtl:label_name(NewLab),
+ hipe_rtl:label_name(Default), 0.9),
+ NewLab,
+ hipe_rtl:mk_goto_index(LBlock, Start, Labels)
+ ]
+ end.
+
+
+%% Create a jumptable
+gen_jump_table(Arg,Fail,IcodeFail,VarMap,ConstTab,Cases,Min) ->
+ %% Map is a rtl mapping of Dense
+ {Max,DenseTbl} = dense_interval(Cases,Min,IcodeFail),
+ {Map,VarMap2} = lbls_from_cases(DenseTbl,VarMap),
+
+ %% Make some labels and registers that we need.
+ BelowLab = hipe_rtl:mk_new_label(),
+ UntaggedR = hipe_rtl:mk_new_reg_gcsafe(),
+ StartR = hipe_rtl:mk_new_reg_gcsafe(),
+
+ %% Generate the code to do the switch...
+ {[
+ %% Untag the index.
+ hipe_tagscheme:untag_fixnum(UntaggedR, Arg)|
+ %% Check that the index is within Min and Max.
+ case Min of
+ 0 -> %% First element is 0 this is simple.
+ [hipe_rtl:mk_branch(UntaggedR, gtu, hipe_rtl:mk_imm(Max),
+ hipe_rtl:label_name(Fail),
+ hipe_rtl:label_name(BelowLab), 0.01),
+ BelowLab,
+ %% StartR contains the index into the jumptable
+ hipe_rtl:mk_switch(UntaggedR, Map)];
+ _ -> %% First element is not 0
+ [hipe_rtl:mk_alu(StartR, UntaggedR, sub,
+ hipe_rtl:mk_imm(Min)),
+ hipe_rtl:mk_branch(StartR, gtu, hipe_rtl:mk_imm(Max-Min),
+ hipe_rtl:label_name(Fail),
+ hipe_rtl:label_name(BelowLab), 0.01),
+ BelowLab,
+ %% StartR contains the index into the jumptable
+ hipe_rtl:mk_switch(StartR, Map)]
+ end],
+ VarMap2,
+ ConstTab}.
+
+
+%% Generate the jumptable for Cases while filling in unused positions
+%% with the fail label
+
+dense_interval(Cases, Min, IcodeFail) ->
+ dense_interval(Cases, Min, IcodeFail, 0, 0).
+dense_interval([Pair = {Const,_}|Rest], Pos, Fail, Range, NoEntries) ->
+ Val = hipe_icode:const_value(Const),
+ if
+ Pos < Val ->
+ {Max, Res} =
+ dense_interval([Pair|Rest], Pos+1, Fail, Range+1, NoEntries),
+ {Max,[{hipe_icode:mk_const(Pos), Fail}|Res]};
+ true ->
+ {Max, Res} = dense_interval(Rest, Pos+1, Fail, Range+1, NoEntries+1),
+ {Max, [Pair | Res]}
+ end;
+dense_interval([], Max, _, _, _) ->
+ {Max-1, []}.
+
+
+%%-------------------------------------------------------------------------
+%% switch_val without jumptable
+%%
+
+gen_slow_switch_val(I, VarMap, ConstTab, Options) ->
+ Is = rewrite_switch_val(I),
+ ?IF_DEBUG_LEVEL(3,?msg("Switch: ~w\n", [Is]), no_debug),
+ hipe_icode2rtl:translate_instrs(Is, VarMap, ConstTab, Options).
+
+rewrite_switch_val(I) ->
+ Var = hipe_icode:switch_val_term(I),
+ Fail = hipe_icode:switch_val_fail_label(I),
+ Cases = hipe_icode:switch_val_cases(I),
+ rewrite_switch_val_cases(Cases, Fail, Var).
+
+rewrite_switch_val_cases([{C,L}|Cases], Fail, Arg) ->
+ Tmp = hipe_icode:mk_new_var(),
+ NextLab = hipe_icode:mk_new_label(),
+ [hipe_icode:mk_move(Tmp, C),
+ hipe_icode:mk_if(op_exact_eqeq_2, [Arg, Tmp], L,
+ hipe_icode:label_name(NextLab)),
+ NextLab |
+ rewrite_switch_val_cases(Cases, Fail, Arg)];
+rewrite_switch_val_cases([], Fail, _Arg) ->
+ [hipe_icode:mk_goto(Fail)].
+
+
+%%-------------------------------------------------------------------------
+%% switch_val with binary search jumptable
+%%
+
+gen_search_switch_val(Arg, Cases, Default, VarMap, ConstTab, _Options) ->
+ ValTableR = hipe_rtl:mk_new_reg_gcsafe(),
+
+ {Values,_Labels} = split_cases(Cases),
+ {NewConstTab,Id} = hipe_consttab:insert_sorted_block(ConstTab, Values),
+ {LabMap,VarMap1} = lbls_from_cases(Cases,VarMap),
+
+ Code =
+ [hipe_rtl:mk_load_address(ValTableR, Id, constant)|
+ tab(Values,LabMap,Arg,ValTableR,Default)],
+ {Code, VarMap1, NewConstTab}.
+
+
+%%-------------------------------------------------------------------------
+%%
+%% tab/5 creates RTL code for a binary search.
+%% It requires two sorted tables one with the keys to search
+%% through and one with the corresponding labels to jump to.
+%%
+%% The implementation is derived from John Bentlys
+%% Programming Pearls.
+%%
+%% Input:
+%% KeyList - A list of keys to search through.
+%% (Just used to calculate the number of elements.)
+%% LableList - A list of labels to jump to.
+%% KeyReg - A register containing the key to search for.
+%% TablePntrReg - A register containing a pointer to the
+%% tables with keys
+%% Default - A lable to jump to if the key is not found.
+%%
+%% Example:
+%% KeyTbl: < a, b, d, f, h, i, z >
+%% Lbls: < 5, 3, 2, 4, 1, 7, 6 >
+%% Default: 8
+%% KeyReg: v37
+%% TablePntrReg: r41
+%%
+%% should give code like:
+%% r41 <- KeyTbl
+%% r42 <- 0
+%% r43 <- [r41+16]
+%% if (r43 gt v37) then L17 (0.50) else L16
+%% L16:
+%% r42 <- 16
+%% goto L17
+%% L17:
+%% r46 <- r42 add 16
+%% r45 <- [r41+r46]
+%% if (r45 gt v37) then L21 (0.50) else L20
+%% L20:
+%% r42 <- r46
+%% goto L21
+%% L21:
+%% r48 <- r42 add 8
+%% r47 <- [r41+r48]
+%% if (r47 gt v37) then L23 (0.50) else L22
+%% L22:
+%% r42 <- r48
+%% goto L23
+%% L23:
+%% r50 <- r42 add 4
+%% r49 <- [r41+r50]
+%% if (r49 gt v37) then L25 (0.50) else L24
+%% L24:
+%% r42 <- r42 add 4
+%% goto L25
+%% L25:
+%% if (r42 gt 28) then L6 (0.50) else L18
+%% L18:
+%% r44 <- [r41+r42]
+%% if (r44 eq v37) then L19 (0.90) else L8
+%% L19:
+%% r42 <- r42 sra 2
+%% switch (r42) <L5, L3, L2, L4, L1,
+%% L7, L6>
+
+%%
+%% The search is done like a rolled out binary search,
+%% but instead of starting in the middle we start at
+%% the power of two closest above the middle.
+%%
+%% We let IndexReg point to the lower bound of our
+%% search, and then we speculatively look at a
+%% position at IndexReg + I where I is a power of 2.
+%%
+%% Example: Looking for 'h' in
+%% KeyTbl: < a, b, d, f, h, i, z >
+%%
+%% We start with IndexReg=0 and I=4
+%% < a, b, d, f, h, i, z >
+%% ^ ^
+%% IndexReg + I
+%%
+%% 'f' < 'h' so we add I to IndexReg and divide I with 2
+%% IndexReg=4 and I=2
+%% < a, b, d, f, h, i, z >
+%% ^ ^
+%% IndexReg + I
+%%
+%% 'i' > 'h' so we keep IndexReg and divide I with 2
+%% IndexReg=4 and I=1
+%% < a, b, d, f, h, i, z >
+%% ^ ^
+%% IndexReg+ I
+%% Now we have found 'h' so we add I to IndexReg -> 5
+%% And we can load switch to the label at position 5 in
+%% the label table.
+%%
+%% Now since the wordsize is 4 all numbers above are
+%% Multiples of 4.
+
+tab(KeyList, LabelList, KeyReg, TablePntrReg, Default) ->
+ %% Calculate the size of the table:
+ %% the number of keys * wordsize
+ LastOffset = (length(KeyList)-1)*?WORDSIZE,
+
+ %% Calculate the power of two closest to the size of the table.
+ Pow2 = 1 bsl trunc(math:log(LastOffset) / math:log(2)),
+
+ %% Create some registers and lables that we need
+ IndexReg = hipe_rtl:mk_new_reg_gcsafe(),
+ Temp = hipe_rtl:mk_new_reg_gcsafe(),
+ Temp2 = hipe_rtl:mk_new_reg_gcsafe(),
+ Lab1 = hipe_rtl:mk_new_label(),
+ Lab2 = hipe_rtl:mk_new_label(),
+ Lab3 = hipe_rtl:mk_new_label(),
+ Lab4 = hipe_rtl:mk_new_label(),
+
+ %% Calculate the position to start looking at
+ Init = (LastOffset)-Pow2,
+
+ %% Create the code
+ [
+ hipe_rtl:mk_move(IndexReg,hipe_rtl:mk_imm(0)),
+ hipe_rtl:mk_load(Temp,TablePntrReg,hipe_rtl:mk_imm(Init)),
+ hipe_rtl:mk_branch(Temp, geu, KeyReg,
+ hipe_rtl:label_name(Lab2),
+ hipe_rtl:label_name(Lab1), 0.5),
+ Lab1,
+ hipe_rtl:mk_alu(IndexReg, IndexReg, add, hipe_rtl:mk_imm(Init+?WORDSIZE)),
+ hipe_rtl:mk_goto(hipe_rtl:label_name(Lab2)),
+ Lab2] ++
+
+ step(Pow2 div 2, TablePntrReg, IndexReg, KeyReg) ++
+
+ [hipe_rtl:mk_branch(IndexReg, gt, hipe_rtl:mk_imm(LastOffset),
+ hipe_rtl:label_name(Default),
+ hipe_rtl:label_name(Lab3), 0.5),
+ Lab3,
+ hipe_rtl:mk_load(Temp2,TablePntrReg,IndexReg),
+ hipe_rtl:mk_branch(Temp2, eq, KeyReg,
+ hipe_rtl:label_name(Lab4),
+ hipe_rtl:label_name(Default), 0.9),
+ Lab4,
+ hipe_rtl:mk_alu(IndexReg, IndexReg, sra,
+ hipe_rtl:mk_imm(hipe_rtl_arch:log2_word_size())),
+ hipe_rtl:mk_sorted_switch(IndexReg, LabelList, KeyList)
+ ].
+
+step(I,TablePntrReg,IndexReg,KeyReg) ->
+ Temp = hipe_rtl:mk_new_reg_gcsafe(),
+ TempIndex = hipe_rtl:mk_new_reg_gcsafe(),
+ Lab1 = hipe_rtl:mk_new_label(),
+ Lab2 = hipe_rtl:mk_new_label(),
+ [hipe_rtl:mk_alu(TempIndex, IndexReg, add, hipe_rtl:mk_imm(I)),
+ hipe_rtl:mk_load(Temp,TablePntrReg,TempIndex),
+ hipe_rtl:mk_branch(Temp, gtu, KeyReg,
+ hipe_rtl:label_name(Lab2),
+ hipe_rtl:label_name(Lab1) , 0.5),
+ Lab1] ++
+ case ?WORDSIZE of
+ I -> %% Recursive base case
+ [hipe_rtl:mk_alu(IndexReg, IndexReg, add, hipe_rtl:mk_imm(I)),
+ hipe_rtl:mk_goto(hipe_rtl:label_name(Lab2)),
+ Lab2
+ ];
+ _ -> %% Recursion case
+ [hipe_rtl:mk_move(IndexReg, TempIndex),
+ hipe_rtl:mk_goto(hipe_rtl:label_name(Lab2)),
+ Lab2
+ | step(I div 2, TablePntrReg, IndexReg, KeyReg)
+ ]
+ end.
+
+%%-------------------------------------------------------------------------
+
+lbls_from_cases([{_,L}|Rest], VarMap) ->
+ {Map,VarMap1} = lbls_from_cases(Rest, VarMap),
+ {RtlL, VarMap2} = hipe_rtl_varmap:icode_label2rtl_label(L,VarMap1),
+ %% {[{label,hipe_rtl:label_name(RtlL)}|Map],VarMap2};
+ {[hipe_rtl:label_name(RtlL)|Map],VarMap2};
+lbls_from_cases([], VarMap) ->
+ {[], VarMap}.
+
+%%-------------------------------------------------------------------------
+
+split_cases(L) ->
+ split_cases(L, [], []).
+
+split_cases([], Vs, Ls) -> {lists:reverse(Vs),lists:reverse(Ls)};
+split_cases([{V,L}|Rest], Vs, Ls) ->
+ split_cases(Rest, [hipe_icode:const_value(V)|Vs], [L|Ls]).
+
+%%-------------------------------------------------------------------------
+%%
+%% {switch_tuple_arity,X,Fail,N,[{A1,L1},...,{AN,LN}]}
+%%
+%% if not boxed(X) goto Fail
+%% Hdr := *boxed_val(X)
+%% switch_int(Hdr,Fail,[{H(A1),L1},...,{H(AN),LN}])
+%% where H(Ai) = make_arityval(Ai)
+%%
+%%-------------------------------------------------------------------------
+
+gen_switch_tuple(I, Map, ConstTab, _Options) ->
+ Var = hipe_icode:switch_tuple_arity_term(I),
+ {X, Map1} = hipe_rtl_varmap:icode_var2rtl_var(Var, Map),
+ Fail0 = hipe_icode:switch_tuple_arity_fail_label(I),
+ {Fail1, Map2} = hipe_rtl_varmap:icode_label2rtl_label(Fail0, Map1),
+ FailLab = hipe_rtl:label_name(Fail1),
+ {Cases, Map3} =
+ lists:foldr(fun({A,L}, {Rest,M}) ->
+ {L1,M1} = hipe_rtl_varmap:icode_label2rtl_label(L, M),
+ L2 = hipe_rtl:label_name(L1),
+ A1 = hipe_icode:const_value(A),
+ H1 = hipe_tagscheme:mk_arityval(A1),
+ {[{H1,L2}|Rest], M1} end,
+ {[], Map2},
+ hipe_icode:switch_tuple_arity_cases(I)),
+ Hdr = hipe_rtl:mk_new_reg_gcsafe(),
+ IsBoxedLab = hipe_rtl:mk_new_label(),
+ {[hipe_tagscheme:test_is_boxed(X, hipe_rtl:label_name(IsBoxedLab),
+ FailLab, 0.9),
+ IsBoxedLab,
+ hipe_tagscheme:get_header(Hdr, X) |
+ gen_switch_int(Hdr, FailLab, Cases)],
+ Map3, ConstTab}.
+
+%%
+%% RTL-level switch-on-int
+%%
+
+gen_switch_int(X, FailLab, [{C,L}|Rest]) ->
+ NextLab = hipe_rtl:mk_new_label(),
+ [hipe_rtl:mk_branch(X, eq, hipe_rtl:mk_imm(C), L,
+ hipe_rtl:label_name(NextLab), 0.5),
+ NextLab |
+ gen_switch_int(X, FailLab, Rest)];
+gen_switch_int(_, FailLab, []) ->
+ [hipe_rtl:mk_goto(FailLab)].
+