diff options
Diffstat (limited to 'lib/hipe/rtl/hipe_rtl_mk_switch.erl')
| -rw-r--r-- | lib/hipe/rtl/hipe_rtl_mk_switch.erl | 985 |
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)]. + |