diff options
Diffstat (limited to 'lib/hipe/misc')
| -rw-r--r-- | lib/hipe/misc/Makefile | 113 | ||||
| -rw-r--r-- | lib/hipe/misc/hipe_consttab.erl | 503 | ||||
| -rw-r--r-- | lib/hipe/misc/hipe_consttab.hrl | 27 | ||||
| -rw-r--r-- | lib/hipe/misc/hipe_data_pp.erl | 158 | ||||
| -rw-r--r-- | lib/hipe/misc/hipe_gensym.erl | 244 | ||||
| -rw-r--r-- | lib/hipe/misc/hipe_pack_constants.erl | 211 | ||||
| -rw-r--r-- | lib/hipe/misc/hipe_sdi.erl | 378 | ||||
| -rw-r--r-- | lib/hipe/misc/hipe_sdi.hrl | 25 |
8 files changed, 1659 insertions, 0 deletions
diff --git a/lib/hipe/misc/Makefile b/lib/hipe/misc/Makefile new file mode 100644 index 0000000000..d5c395855a --- /dev/null +++ b/lib/hipe/misc/Makefile @@ -0,0 +1,113 @@ +# +# %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% +# + +ifndef EBIN +EBIN = ../ebin +endif + +ifndef DOCS +DOCS = ../doc +endif + +include $(ERL_TOP)/make/target.mk +include $(ERL_TOP)/make/$(TARGET)/otp.mk + +# ---------------------------------------------------- +# Application version +# ---------------------------------------------------- +include ../vsn.mk +VSN=$(HIPE_VSN) + +# ---------------------------------------------------- +# Release directory specification +# ---------------------------------------------------- +RELSYSDIR = $(RELEASE_PATH)/lib/hipe-$(VSN) + +# ---------------------------------------------------- +# Target Specs +# ---------------------------------------------------- +ifdef HIPE_ENABLED +HIPE_MODULES = hipe_data_pp hipe_pack_constants hipe_sdi +else +HIPE_MODULES = +endif +MODULES = hipe_consttab hipe_gensym $(HIPE_MODULES) + +HRL_FILES= hipe_sdi.hrl +ERL_FILES= $(MODULES:%=%.erl) +TARGET_FILES= $(MODULES:%=$(EBIN)/%.$(EMULATOR)) +DOC_FILES= $(MODULES:%=$(DOCS)/%.html) + +# APP_FILE= +# APP_SRC= $(APP_FILE).src +# APP_TARGET= $(EBIN)/$(APP_FILE) +# +# APPUP_FILE= +# APPUP_SRC= $(APPUP_FILE).src +# APPUP_TARGET= $(EBIN)/$(APPUP_FILE) + +# ---------------------------------------------------- +# FLAGS +# ---------------------------------------------------- + +include ../native.mk + +ERL_COMPILE_FLAGS += +warn_exported_vars +warn_missing_spec +warn_untyped_record + +# ---------------------------------------------------- +# Targets +# ---------------------------------------------------- + +debug opt: $(TARGET_FILES) + +docs: $(DOC_FILES) + +clean: + rm -f $(TARGET_FILES) + rm -f core + +$(DOCS)/%.html:%.erl + erl -noshell -run edoc_run file '"$<"' '[{dir, "$(DOCS)"}]' -s init stop + +# ---------------------------------------------------- +# Special Build Targets +# ---------------------------------------------------- + + + +# ---------------------------------------------------- +# Release Target +# ---------------------------------------------------- +include $(ERL_TOP)/make/otp_release_targets.mk + +release_spec: opt + $(INSTALL_DIR) $(RELSYSDIR)/misc + $(INSTALL_DATA) $(ERL_FILES) $(HRL_FILES) $(RELSYSDIR)/misc + $(INSTALL_DIR) $(RELSYSDIR)/ebin + $(INSTALL_DATA) $(TARGET_FILES) $(RELSYSDIR)/ebin + +release_docs_spec: + +distclean: clean +realclean: clean + +$(EBIN)/hipe_consttab.beam: hipe_consttab.hrl +$(EBIN)/hipe_data_pp.beam: hipe_consttab.hrl +$(EBIN)/hipe_pack_constants.beam: hipe_consttab.hrl ../../kernel/src/hipe_ext_format.hrl +$(EBIN)/hipe_sdi.beam: hipe_sdi.hrl diff --git a/lib/hipe/misc/hipe_consttab.erl b/lib/hipe/misc/hipe_consttab.erl new file mode 100644 index 0000000000..c381e6a057 --- /dev/null +++ b/lib/hipe/misc/hipe_consttab.erl @@ -0,0 +1,503 @@ +%% -*- 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% +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% @doc +%% CONSTTAB - maps labels to constants. +%% <p> +%% <strong> Note:</strong> 'constant' is a misnomer throughout this code. +%% </p> +%% <p> +%% There are two different types of constants that can be stored: +%% <ul> +%% <li>Erlang terms</li> +%% <li>Blocks of binary data</li> +%% </ul> +%% </p> +%% <p> +%% Erlang terms are just what you would expect, you can store any +%% Erlang term in the constant table. +%% The term is assumed to be loaded to the place in memory denoted by the +%% label returned by the insertion function. +%% </p> +%% <p> +%% Blocks of binary data comes in some different shapes, you can +%% either insert a block of integers (of byte, word (4 bytes), or +%% word (8 bytes) size) or a list of references to code. +%% These references will then be threated as word sized addresses +%% and can be used for jumptables. +%% The list of references can have an optional ordering, so that +%% you can create a jumptable that will be sorted on the load-time +%% representation of e.g. atoms. +%% </p> +%% @type ctdata() = #ctdata{}. See {@link mk_ctdata/4}. +%% @type ct_type() = term | block | sorted_block | ref +%% @type data() = term() | [term()] | [byte()] | internal(). +%% This type is dependent on ct_type +%% <ul> +%% <li> If ct_type() = term -- data() = term() </li> +%% <li> If ct_type() = block -- data() = [byte()] </li> +%% <li> If ct_type() = sorted_block -- data() = [term()] </li> +%% <li> If ct_type() = ref -- data() = internal() </li> +%% </ul> +%% @type ct_alignment(). +%% Alignment is always a power of two equal to the number of bytes +%% in the machine word. +%% @end +%% @type byte(). <code>B</code> is an integer between 0 and 255. +%% @type hipe_consttab(). +%% An abstract datatype for storing data. +%% @end +%% Internal note: +%% A hipe_consttab is a tuple {Data, ReferedLabels, NextConstLabel} +%% @type hipe_constlbl(). +%% An abstract datatype for referring to data. +%% @type element_type() = byte | word | ctab_array() +%% @type ctab_array() = {ctab_array, Type::element_type(), +%% NoElements::pos_integer()} +%% @type block() = [integer() | label_ref()] +%% @type label_ref() = {label, Label::code_label()} +%% @type code_label() = hipe_sparc:label_name() | hipe_x86:label_name() +%% @end +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-module(hipe_consttab). + +-export([new/0, % new() -> ConstTab + insert_term/2, % insert_term(ConstTab, Term) -> {NewTab, Lbl} + %% insert_fun/2, % insert_term(ConstTab, Fun) -> {NewTab, Lbl} + %% insert_word/2, % insert_word(ConstTab, Value) -> {NewTab, Lbl} + insert_sorted_block/2, % insert_word(ConstTab, ValueList) -> + % {NewTab, Lbl} + insert_sorted_block/4, + insert_block/3, + %% insert_global_word/2, + %% insert_global_block/4, + %% update_word/3, % update_word(ConstTab, Value) -> {NewTab, Lbl} + %% update_block/5, + %% update_global_word/3, + %% update_global_block/5, + lookup/2, % lookup(Key, ConstTab) -> [Term|Block] + labels/1, % labels(ConstTab) -> LabelList + referred_labels/1, % referred_labels(ConstTab) -> LabelList + update_referred_labels/2, + decompose/1, + size_of/1, + const_type/1, + const_align/1, + const_exported/1, + const_data/1, + const_size/1 + %% block_size/1 % size of a block in bytes + ]). + +%%----------------------------------------------------------------------------- + +-include("hipe_consttab.hrl"). + +-type code_label() :: term(). % XXX: FIXME +-type label_ref() :: {'label', code_label()}. +-type block() :: [hipe_constlbl() | label_ref()]. + +-type ctab_array() :: {'ctab_array', 'byte' | 'word', pos_integer()}. +-type element_type() :: 'byte' | 'word' | ctab_array(). + +-type sort_order() :: term(). % XXX: FIXME + +%%----------------------------------------------------------------------------- + +%% @doc Create a new constant table. +-spec new() -> hipe_consttab(). +new() -> {tree_empty(), [], 0}. + + +%% @spec insert_term(ConstTab::hipe_consttab(), Term::term()) -> {NewTab, Lbl} +%% NewTab = hipe_consttab() +%% Lbl = hipe_constlbl() +%% @doc Inserts an erlang term into the const table if the term was not +%% present before, otherwise do nothing. +-spec insert_term(hipe_consttab(), term()) -> {hipe_consttab(),hipe_constlbl()}. +insert_term(ConstTab, Term) -> + case lookup_const(ConstTab, term, word_size(), false, Term) of + {value, Label} -> + {ConstTab, Label}; + none -> + insert_const(ConstTab, term, word_size(), false, Term) + end. + + +%% %% @spec insert_fun(ConstTab::hipe_consttab(), Term::term()) -> {NewTab, Lbl} +%% %% NewTab = hipe_consttab() +%% %% Lbl = hipe_constlbl() +%% %% @doc Inserts a Fun into the const table. +%% %% Don't ask me what this is for... +%% -spec insert_fun(hipe_consttab(), term()) -> {hipe_consttab(), hipe_constlbl()}. +%% insert_fun(ConstTab, Fun) -> +%% insert_const(ConstTab, term, word_size(), false, Fun). + + +%% @spec (ConstTab::hipe_consttab(), TermList::[term()]) -> {NewTab, Lbl} +%% NewTab = hipe_consttab() +%% Lbl = hipe_constlbl() +%% @doc Inserts a list of terms into the const table. +-spec insert_sorted_block(hipe_consttab(), [term()]) -> {hipe_consttab(), hipe_constlbl()}. +insert_sorted_block(CTab, TermList) -> + insert_const(CTab, sorted_block, word_size(), false, TermList). + +%% %% @spec (ConstTab::hipe_consttab(), InitVal::integer()) -> {NewTab, Lbl} +%% %% NewTab = hipe_consttab() +%% %% Lbl = hipe_constlbl() +%% %% @doc Inserts a word into the const table. +%% %% Shorthand for inserting a word. +%% insert_word(ConstTab, InitVal) -> +%% insert_block(ConstTab, word, [InitVal]). + +%% %% @spec (ConstTab::hipe_consttab(), InitVal::integer()) -> {NewTab, Lbl} +%% %% NewTab = hipe_consttab() +%% %% Lbl = hipe_constlbl() +%% %% @doc Inserts a word into the const table. +%% %% This constant should be exported from the function... +%% %% <strong>Note</strong> Global constants are +%% %% not supported in current version of HiPE. +%% insert_global_word(ConstTab, InitVal) -> +%% insert_global_block(ConstTab, word_size(), word, [InitVal]). + + +%% @spec (ConstTab::hipe_consttab(), +%% ElementType::element_type(), +%% InitList::block()) -> {hipe_consttab(), hipe_constlbl()} +%% @doc Inserts a block into the const table. +%% The block can consist of references to labels in the code. +%% This is used for jump tables. These references should be tracked +%% and the corresponding BBs should not be considered dead. +-spec insert_block(hipe_consttab(), element_type(), block()) -> + {hipe_consttab(), hipe_constlbl()}. +insert_block({ConstTab, RefToLabels, NextLabel}, ElementType, InitList) -> + ReferredLabels = get_labels(InitList, []), + NewRefTo = ReferredLabels ++ RefToLabels, + {NewTa, Id} = insert_const({ConstTab, NewRefTo, NextLabel}, + block, word_size(), false, + {ElementType,InitList}), + {insert_backrefs(NewTa, Id, ReferredLabels), Id}. + + +%% @spec (ConstTab::hipe_consttab(), ElementType::element_type(), +%% InitList::block(), SortOrder) -> {hipe_consttab(), hipe_constlbl()} +%% @doc Inserts a block into the const table. +%% The block can consist of references to labels in the code. +%% This is used for jump tables. These references should be tracked +%% and the corresponding BBs should not be considered dead. +%% At load-time the block will be sorted according to SortOrder. +%% This is used to make jump tables on atom indices. +-spec insert_sorted_block(hipe_consttab(), element_type(), block(), sort_order()) -> + {hipe_consttab(), hipe_constlbl()}. +insert_sorted_block({ConstTab, RefToLabels, NextLabel}, + ElementType, InitList, SortOrder) -> + ReferredLabels = get_labels(InitList, []), + NewRefTo = ReferredLabels ++ RefToLabels, + {NewTa, Id} = insert_const({ConstTab, NewRefTo, NextLabel}, + block, word_size(), false, + {ElementType, InitList, SortOrder}), + {insert_backrefs(NewTa, Id, ReferredLabels), Id}. + +insert_backrefs(Tbl, From, ToLabels) -> + lists:foldl(fun(To, Tab) -> + insert_ref(Tab, From, To) + end, Tbl, ToLabels). + +insert_ref({Table, RefToLabels, NextLblNr}, From, To) -> + Ref = {To, ref}, + case tree_lookup(Ref, Table) of + none -> + {tree_insert(Ref, [From], Table), RefToLabels, NextLblNr}; + {value, RefList} -> + {tree_update(Ref, [From|RefList], Table), RefToLabels, NextLblNr} + end. + +find_refs(To, {Table,_,_}) -> + %% returns 'none' or {value, V} + tree_lookup({To, ref}, Table). + +delete_ref(To, {ConstTab, RefToLabels, NextLabel}) -> + {tree_delete({To, ref}, ConstTab), RefToLabels, NextLabel}. + +%% TODO: handle refs to labels. +%% insert_global_block(ConstTab, Align, ElementType, InitList) -> +%% ByteList = decompose(size_of(ElementType), InitList), +%% insert_const(ConstTab, block, Align, true, {byte,ByteList}). + +get_labels([{label, L}|Rest], Acc) -> + get_labels(Rest, [L|Acc]); +get_labels([I|Rest], Acc) when is_integer(I) -> + get_labels(Rest, Acc); +get_labels([], Acc) -> + Acc. + +%% @spec size_of(element_type()) -> pos_integer() +%% @doc Returns the size in bytes of an element_type. +%% The is_atom/1 guard in the clause handling arrays +%% constraints the argument to 'byte' | 'word' +-spec size_of(element_type()) -> pos_integer(). +size_of(byte) -> 1; +size_of(word) -> word_size(); +size_of({ctab_array,S,N}) when is_atom(S), is_integer(N), N > 0 -> + N * size_of(S). + +%% @spec decompose({element_type(), block()}) -> [byte()] +%% @doc Turns a block into a list of bytes. +%% <strong>Note:</strong> Be careful with the byte order here. +-spec decompose({element_type(), block()}) -> [byte()]. +decompose({ElementType, Data}) -> + decompose(size_of(ElementType), Data). + +decompose(_Bytes, []) -> + []; +decompose(Bytes, [X|Xs]) -> + number_to_bytes(Bytes, X, decompose(Bytes, Xs)). + +number_to_bytes(0, X, Bytes) when is_integer(X) -> + Bytes; +number_to_bytes(N, X, Bytes) -> + Byte = X band 255, + number_to_bytes(N-1, X bsr 8, [Byte|Bytes]). + +%% @spec block_size({element_type(), block()}) -> non_neg_integer() +%% @doc Returns the size in bytes of a block. +block_size({ElementType, Block}) -> + length(Block) * size_of(ElementType); +block_size({ElementType, Block, _SortOrder}) -> + length(Block) * size_of(ElementType). + + +%%-------------------- +%% ctdata and friends +%%-------------------- + +-type ct_type() :: 'block' | 'ref' | 'sorted_block' | 'term'. + +-record(ctdata, {type :: ct_type(), + alignment :: ct_alignment(), + exported :: boolean(), + data :: term()}). +-type ctdata() :: #ctdata{}. + +-spec mk_ctdata(Type::ct_type(), Alignment::ct_alignment(), + Exported::boolean(), Data::term()) -> ctdata(). +mk_ctdata(Type, Alignment, Exported, Data) -> + #ctdata{type = Type, alignment = Alignment, exported = Exported, data = Data}. + +-spec const_type(ctdata()) -> ct_type(). +const_type(#ctdata{type = Type}) -> Type. + +-spec const_align(ctdata()) -> ct_alignment(). +const_align(#ctdata{alignment = Alignment}) -> Alignment. + +-spec const_exported(ctdata()) -> boolean(). +const_exported(#ctdata{exported = Exported}) -> Exported. + +-spec const_data(ctdata()) -> term(). +const_data(#ctdata{data = Data}) -> Data. + +-spec update_const_data(ctdata(), {_,[_]} | {_,[_],_}) -> ctdata(). +update_const_data(CTData, Data) -> + CTData#ctdata{data = Data}. + +%% @doc Returns the size in bytes. +-spec const_size(ctdata()) -> non_neg_integer(). +const_size(Constant) -> + case const_type(Constant) of + %% term: you can't and shouldn't ask for its size + block -> block_size(const_data(Constant)); + sorted_block -> length(const_data(Constant)) * word_size() + end. + +-spec word_size() -> ct_alignment(). +word_size() -> + hipe_rtl_arch:word_size(). + + +%%-------------------- +%% Update a label +%%-------------------- + + +%% TODO: Remove RefsTOfrom overwitten labels... +%% update_word(ConstTab, Label, InitVal) -> +%% update_block(ConstTab, Label, word_size(), word, [InitVal]). +%% +%% update_global_word(ConstTab, Label, InitVal) -> +%% update_global_block(ConstTab, Label, word_size(), word, [InitVal]). + +%% +%% Update info for an existing label +%% +%% Returns NewTable +%% +%% +%% update_block(ConstTab, Label, Align, ElementType, InitList) -> +%% ByteList = decompose(size_of(ElementType), InitList), +%% update_const(ConstTab, Label, block, Align, false, {ElementType,ByteList}). + +update_block_labels(ConstTab, DataLbl, OldLbl, NewLbl) -> + Const = lookup(DataLbl, ConstTab), + Old = {label, OldLbl}, + case const_data(Const) of + {Type, Data} -> + NewData = update_data(Data, Old, NewLbl), + update(ConstTab, DataLbl, update_const_data(Const, {Type,NewData})); + {Type, Data, Order} -> + NewData = update_data(Data, Old, NewLbl), + update(ConstTab, DataLbl, update_const_data(Const, {Type,NewData,Order})) + end. + +update_data(Data, Old, New) -> + [if Lbl =:= Old -> {label, New}; true -> Lbl end || Lbl <- Data]. + +%% update_global_block(ConstTab, Label, Align, ElementType, InitList) -> +%% ByteList = decompose(size_of(ElementType), InitList), +%% update_const(ConstTab, Label, block, Align, true, ByteList). + +%% +%% Insert a constant in the table, returns {NewTable, Label}. +%% + +insert_const({Table, RefToLabels, NextLblNr}, Type, Alignment, Exported, Data) -> + Const = mk_ctdata(Type, Alignment, Exported, Data), + {{tree_insert(NextLblNr, Const, Table), RefToLabels, NextLblNr+1}, + NextLblNr}. + +%% %% Update information for a label, returns NewTable. +%% %% (Removes old info.) +%% +%% update_const({Table, RefToLabels, NextLblNr}, Label, Type, Alignment, Exported, Data) -> +%% Const = mk_ctdata(Type, Alignment, Exported, Data), +%% {tree_update(Label, Const, Table), RefToLabels, NextLblNr}. + +update({Table, RefToLabels, NextLblNr}, Label, NewConst) -> + {tree_update(Label, NewConst, Table), RefToLabels, NextLblNr}. + +%% @spec lookup(hipe_constlbl(), hipe_consttab()) -> ctdata() +%% @doc Lookup a label. +-spec lookup(hipe_constlbl(), hipe_consttab()) -> ctdata(). +lookup(Lbl, {Table, _RefToLabels, _NextLblNr}) -> + tree_get(Lbl, Table). + +%% Find out if a constant term is present in the constant table. +lookup_const({Table, _RefToLabels, _NextLblNr}, + Type, Alignment, Exported, Data) -> + Const = mk_ctdata(Type, Alignment, Exported, Data), + tree_lookup_key_for_value(Const, Table). + +%% @doc Return the labels bound in a table. +-spec labels(hipe_consttab()) -> [hipe_constlbl() | {hipe_constlbl(), 'ref'}]. +labels({Table, _RefToLabels, _NextLblNr}) -> + tree_keys(Table). + +%% @spec referred_labels(hipe_consttab()) -> [hipe_constlbl()] +%% @doc Return the referred labels bound in a table. +-spec referred_labels(hipe_consttab()) -> [hipe_constlbl()]. +referred_labels({_Table, RefToLabels, _NextLblNr}) -> + RefToLabels. + + +%% +%% Change label names in constant blocks (jump_tables). +%% +-spec update_referred_labels(hipe_consttab(), + [{hipe_constlbl(), hipe_constlbl()}]) -> + hipe_consttab(). +update_referred_labels(Table, LabelMap) -> + %% io:format("LabelMap: ~w\nTb:~w\n", [LabelMap, Table]), + {Tb, Refs, Next} = + lists:foldl( + fun({OldLbl, NewLbl}, Tbl) -> + case find_refs(OldLbl, Tbl) of + none -> + Tbl; + {value, DataLbls} -> + %% A label may be referred several times. + UniqueLbls = ordsets:from_list(DataLbls), + lists:foldl(fun(DataLbl, AccTbl) -> + insert_ref( + delete_ref(OldLbl, + update_block_labels(AccTbl, DataLbl, OldLbl, NewLbl)), + DataLbl, NewLbl) + end, + Tbl, + UniqueLbls) + end + end, + Table, + LabelMap), + NewRefs = [case lists:keyfind(Lbl, 1, LabelMap) of + {_, New} -> New; + false -> Lbl + end || Lbl <- Refs], + %% io:format("NewTb:~w\n", [{Tb, NewRefs, Next}]), + {Tb, NewRefs, Next}. + + +%%----------------------------------------------------------------------------- +%% primitives for constants +%%----------------------------------------------------------------------------- + +%% Since using `gb_trees' is not safe because of term ordering, we use +%% the `dict' module instead since it matches with =:= on the keys. + +tree_keys(T) -> + dict:fetch_keys(T). + +-spec tree_to_list(dict()) -> [{_, _}]. +tree_to_list(T) -> + dict:to_list(T). + +tree_get(Key, T) -> + dict:fetch(Key, T). + +tree_update(Key, Val, T) -> + dict:store(Key, Val, T). + +tree_insert(Key, Val, T) -> + dict:store(Key, Val, T). + +tree_delete(Key, T) -> + dict:erase(Key, T). + +tree_lookup(Key, T) -> + case dict:find(Key, T) of + {ok, Val} -> + {value, Val}; + error -> + none + end. + +-spec tree_empty() -> dict(). +tree_empty() -> + dict:new(). + +-spec tree_lookup_key_for_value(ctdata(), dict()) -> 'none' | {'value', _}. +tree_lookup_key_for_value(Val, T) -> + tree_lookup_key_for_value_1(tree_to_list(T), Val). + +-spec tree_lookup_key_for_value_1([{_,_}], ctdata()) -> 'none' | {'value', _}. +tree_lookup_key_for_value_1([{Key, Val}|_], Val) -> + {value, Key}; +tree_lookup_key_for_value_1([_|Left], Val) -> + tree_lookup_key_for_value_1(Left, Val); +tree_lookup_key_for_value_1([], _Val) -> + none. diff --git a/lib/hipe/misc/hipe_consttab.hrl b/lib/hipe/misc/hipe_consttab.hrl new file mode 100644 index 0000000000..39018dac34 --- /dev/null +++ b/lib/hipe/misc/hipe_consttab.hrl @@ -0,0 +1,27 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2008-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% +%% +%%----------------------------------------------------------------------------- + +-type ct_alignment() :: 4 | 8. + +-type hipe_constlbl() :: non_neg_integer(). +-type hipe_consttab() :: {dict(), [hipe_constlbl()], hipe_constlbl()}. + +%%----------------------------------------------------------------------------- diff --git a/lib/hipe/misc/hipe_data_pp.erl b/lib/hipe/misc/hipe_data_pp.erl new file mode 100644 index 0000000000..0f206e8ade --- /dev/null +++ b/lib/hipe/misc/hipe_data_pp.erl @@ -0,0 +1,158 @@ +%% -*- 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 +%% Time-stamp: <2008-04-20 14:57:08 richard> +%% ==================================================================== +%% Module : hipe_data_pp +%% Purpose : +%% Notes : +%% History : * 2001-02-25 Erik Johansson ([email protected]): Created. +%% ==================================================================== +%% Exports : +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-module(hipe_data_pp). +-export([pp/4]). + +%%----------------------------------------------------------------------------- + +-include("hipe_consttab.hrl"). + +-type hipe_code_type() :: 'icode' | 'rtl' | 'arm' | 'ppc' | 'sparc' | 'x86'. + +%%----------------------------------------------------------------------------- +%% +%% Pretty print + +-spec pp(io:device(), hipe_consttab(), hipe_code_type(), string()) -> 'ok'. + +pp(Dev, Table, CodeType, Pre) -> + Ls = hipe_consttab:labels(Table), + lists:foreach(fun ({{_, ref}, _}) -> ok; + ({L, E}) -> pp_element(Dev, L, E, CodeType, Pre) + end, + [{L, hipe_consttab:lookup(L, Table)} || L <- Ls]). + +pp_element(Dev, Name, Element, CodeType, Prefix) -> + %% Alignment + case hipe_consttab:const_align(Element) of + 4 -> ok; %% Wordalignment is assumed + Alignment -> + io:format(Dev, " .align~w\n", [Alignment]) + end, + %% Local or exported? + Exported = hipe_consttab:const_exported(Element), + case CodeType of + rtl -> + case Exported of + true -> + io:format(Dev, "DL~w: ", [Name]); + false -> + io:format(Dev, ".DL~w: ", [Name]) + end; + _ -> + io:format(Dev, "~w ", [Name]) + end, + %% Type and data... + case hipe_consttab:const_type(Element) of + term -> + io:format(Dev, "~w\n", [hipe_consttab:const_data(Element)]); + sorted_block -> + Data = hipe_consttab:const_data(Element), + pp_block(Dev, {word, lists:sort(Data)}, CodeType, Prefix); + block -> + pp_block(Dev, hipe_consttab:const_data(Element), CodeType, Prefix) + end. + +pp_block(Dev, {word, Data, SortOrder}, CodeType, Prefix) -> + case CodeType of + rtl -> + io:format(Dev, "\n",[]); + _ -> + ok + end, + pp_wordlist(Dev, Data, CodeType, Prefix), + case CodeType of + rtl -> + io:format(Dev, ";; Sorted by ~w\n",[SortOrder]); + _ -> + ok + end; +pp_block(Dev, {word, Data}, CodeType, Prefix) -> + case CodeType of + rtl -> + io:format(Dev, ".word\n",[]); + _ -> + ok + end, + pp_wordlist(Dev, Data, CodeType, Prefix); +pp_block(Dev, {byte, Data}, CodeType, _Prefix) -> + case CodeType of + rtl -> + io:format(Dev, ".byte\n ",[]); + _ -> + ok + end, + pp_bytelist(Dev, Data, CodeType), + case CodeType of + rtl -> + io:format(Dev, " ;; ~s\n ", [Data]); + _ -> ok + end. + +pp_wordlist(Dev, [{label, L}|Rest], CodeType, Prefix) -> + case CodeType of + rtl -> + io:format(Dev, " &L~w\n", [L]); + _ -> + io:format(Dev, " <~w>\n", [L]) + end, + pp_wordlist(Dev, Rest, CodeType, Prefix); +pp_wordlist(Dev, [D|Rest], CodeType, Prefix) -> + case CodeType of + rtl -> + io:format(Dev, " ~w\n", [D]); + _ -> + io:format(Dev, " ~w\n", [D]) + end, + pp_wordlist(Dev, Rest, CodeType, Prefix); +pp_wordlist(_Dev, [], _CodeType, _Prefix) -> + ok. + +pp_bytelist(Dev, [D], CodeType) -> + case CodeType of + rtl -> + io:format(Dev, "~w\n", [D]); + _ -> + io:format(Dev, "~w\n", [D]) + end, + ok; +pp_bytelist(Dev, [D|Rest], CodeType) -> + case CodeType of + rtl -> + io:format(Dev, "~w,", [D]); + _ -> + io:format(Dev, "~w,", [D]) + end, + pp_bytelist(Dev, Rest, CodeType); +pp_bytelist(Dev, [], _CodeType) -> + io:format(Dev, "\n", []). diff --git a/lib/hipe/misc/hipe_gensym.erl b/lib/hipe/misc/hipe_gensym.erl new file mode 100644 index 0000000000..84fc8fa7e8 --- /dev/null +++ b/lib/hipe/misc/hipe_gensym.erl @@ -0,0 +1,244 @@ +%% -*- 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% +%% +%%======================================================================= +%% File : hipe_gensym.erl +%% Author : Eric Johansson and Kostis Sagonas +%% Description : Generates unique symbols and fresh integer counts. +%%======================================================================= +%% $Id$ +%%======================================================================= +%% Notes: Written while we were in Montreal, Canada for PPDP-2000 as an +%% exercise in Principles and Practice of Declarative Programming! +%%======================================================================= + +-module(hipe_gensym). + +-export([%% init/0, new_var/0, new_label/0, + %% update_lblrange/1, update_vrange/1, var_range/0, label_range/0, + set_var/1, get_var/0, get_next_var/0, + set_label/1, get_label/0, get_next_label/0]). +-export([init/1, new_var/1, new_label/1, + update_vrange/2, update_lblrange/2, var_range/1, label_range/1, + set_var_range/3, set_label_range/3, + set_var/2, get_var/1, get_next_var/1, + set_label/2, get_label/1, get_next_label/1]). + +%%----------------------------------------------------------------------- +%% Types of allowable entities to set global variables for +%%----------------------------------------------------------------------- + +-type gvarname() :: 'icode' | 'rtl' | 'arm' | 'ppc' | 'sparc' | 'x86'. + +%%----------------------------------------------------------------------- + +%% init() -> +%% put(var_count, 0), +%% put(label_count, 0), +%% put(var_min, 0), +%% put(var_max, 0), +%% put(lbl_min, 1), +%% put(lbl_max, 1), +%% ok. + +-spec init(gvarname()) -> 'ok'. + +init(What) -> + put({What,var_count}, 0), + put({What,label_count}, 0), + put({What,var_min}, 0), + put({What,var_max}, 0), + put({What,lbl_min}, 1), + put({What,lbl_max}, 1), + ok. + +%% new_var() -> +%% V = get(var_count), +%% put(var_count, V+1), +%% V. + +-spec new_var(gvarname()) -> non_neg_integer(). + +new_var(What) -> + T = {What, var_count}, + V = get(T), + put(T, V+1), + V. + +%% new_label() -> +%% L = get(label_count), +%% put(label_count, L+1), +%% L. + +-spec new_label(gvarname()) -> non_neg_integer(). + +new_label(What) -> + T = {What, label_count}, + L = get(T), + put(T, L+1), + L. + +%% update_vrange(V) -> +%% Vmax = get(var_max), +%% Vmin = get(var_min), +%% put(var_min, erlang:min(V, Vmin)), +%% put(var_max, erlang:max(V, Vmax)), +%% ok. + +-spec update_vrange(gvarname(), non_neg_integer()) -> 'ok'. +update_vrange(What, V) -> + Tmin = {What, var_min}, + Tmax = {What, var_max}, + Vmax = get(Tmax), + Vmin = get(Tmin), + put(Tmin, erlang:min(V, Vmin)), + put(Tmax, erlang:max(V, Vmax)), + ok. + +%% update_lblrange(L) -> +%% Lmax = get(lbl_max), +%% Lmin = get(lbl_min), +%% put(lbl_min, erlang:min(L, Lmin)), +%% put(lbl_max, erlang:max(L, Lmax)), +%% ok. + +-spec update_lblrange(gvarname(), non_neg_integer()) -> 'ok'. + +update_lblrange(What, L) -> + Tmin = {What, lbl_min}, + Tmax = {What, lbl_max}, + Lmax = get(Tmax), + Lmin = get(Tmin), + put(Tmin, erlang:min(L, Lmin)), + put(Tmax, erlang:max(L, Lmax)), + ok. + +%% var_range() -> +%% {get(var_min), get(var_max)}. + +-spec var_range(gvarname()) -> {non_neg_integer(), non_neg_integer()}. + +var_range(What) -> + {get({What,var_min}), get({What,var_max})}. + +-spec set_var_range(gvarname(), non_neg_integer(), non_neg_integer()) -> 'ok'. + +set_var_range(What, Min, Max) -> + put({What,var_min}, Min), + put({What,var_max}, Max), + ok. + +%% label_range() -> +%% {get(lbl_min), get(lbl_max)}. + +-spec label_range(gvarname()) -> {non_neg_integer(), non_neg_integer()}. + +label_range(What) -> + {get({What,lbl_min}), get({What,lbl_max})}. + +-spec set_label_range(gvarname(), non_neg_integer(), non_neg_integer()) -> 'ok'. + +set_label_range(What, Min, Max) -> + put({What,lbl_min}, Min), + put({What,lbl_max}, Max), + ok. + +%%----------------------------------------------------------------------- +%% Variable counter +%%----------------------------------------------------------------------- + +-spec set_var(non_neg_integer()) -> 'ok'. + +set_var(X) -> + put(var_max, X), + ok. + +-spec set_var(gvarname(), non_neg_integer()) -> 'ok'. + +set_var(What, X) -> + put({What,var_max}, X), + ok. + +-spec get_var() -> non_neg_integer(). + +get_var() -> + get(var_max). + +-spec get_var(gvarname()) -> non_neg_integer(). + +get_var(What) -> + get({What,var_max}). + +-spec get_next_var() -> non_neg_integer(). + +get_next_var() -> + C = get(var_max), + put(var_max, C+1), + C+1. + +-spec get_next_var(gvarname()) -> non_neg_integer(). + +get_next_var(What) -> + T = {What, var_max}, + C = get(T), + put(T, C+1), + C+1. + +%%----------------------------------------------------------------------- +%% Label counter +%%----------------------------------------------------------------------- + +-spec set_label(non_neg_integer()) -> 'ok'. + +set_label(X) -> + put(lbl_max, X), + ok. + +-spec set_label(gvarname(), non_neg_integer()) -> 'ok'. + +set_label(What, X) -> + put({What,lbl_max}, X), + ok. + +-spec get_label() -> non_neg_integer(). + +get_label() -> + get(lbl_max). + +-spec get_label(gvarname()) -> non_neg_integer(). + +get_label(What) -> + get({What,lbl_max}). + +-spec get_next_label() -> non_neg_integer(). + +get_next_label() -> + C = get(lbl_max), + put(lbl_max, C+1), + C+1. + +-spec get_next_label(gvarname()) -> non_neg_integer(). + +get_next_label(What) -> + T = {What, lbl_max}, + C = get(T), + put(T, C+1), + C+1. + +%%----------------------------------------------------------------------- diff --git a/lib/hipe/misc/hipe_pack_constants.erl b/lib/hipe/misc/hipe_pack_constants.erl new file mode 100644 index 0000000000..e214d7ebbc --- /dev/null +++ b/lib/hipe/misc/hipe_pack_constants.erl @@ -0,0 +1,211 @@ +%% -*- erlang-indent-level: 2 -*- +%%============================================================================= +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2003-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% +%% + +-module(hipe_pack_constants). +-export([pack_constants/2, slim_refs/1, slim_constmap/1]). + +-include("hipe_consttab.hrl"). +-include("../../kernel/src/hipe_ext_format.hrl"). + +%%----------------------------------------------------------------------------- + +-type raw_data() :: binary() | number() | list() | tuple(). +-type tbl_ref() :: {hipe_constlbl(), non_neg_integer()}. + +-record(pcm_entry, {mfa :: mfa(), + label :: hipe_constlbl(), + const_num :: non_neg_integer(), + start :: non_neg_integer(), + type :: 0 | 1 | 2, + raw_data :: raw_data()}). + +%%----------------------------------------------------------------------------- + +-spec pack_constants([{mfa(),[_],hipe_consttab()}], ct_alignment()) -> + {ct_alignment(), + non_neg_integer(), + [#pcm_entry{}], + [{mfa(),[tbl_ref() | {'sorted',non_neg_integer(),[tbl_ref()]}]}]}. + +pack_constants(Data, Align) -> + pack_constants(Data, 0, Align, 0, [], []). + +pack_constants([{MFA,_,ConstTab}|Rest], Size, Align, ConstNo, Acc, Refs) -> + Labels = hipe_consttab:labels(ConstTab), + %% RefToLabels = hipe_consttab:referred_labels(ConstTab), + {NewSize, NewAlign, Map, NewConstNo, RefToLabels} = + pack_labels(Labels, MFA, ConstTab, Size, Align, ConstNo, Acc, []), + NewRefs = + case RefToLabels of + [] -> Refs; + _ -> [{MFA,RefToLabels}|Refs] + end, + pack_constants(Rest, NewSize, NewAlign, NewConstNo, Map, NewRefs); +pack_constants([], Size, Align, _, Acc, Refs) -> + {Align, Size, Acc, Refs}. + +%% +%% pack_labels converts a ConstTab to a packed ConstMap, which +%% maps {MFA,Label} pairs to information about individual constants, +%% including their ConstNo and start offset in the constants pool. +%% +pack_labels([{_Label,ref}|Labels],MFA,ConstTab,Size,Align,ConstNo,Acc, Refs) -> + pack_labels(Labels, MFA, ConstTab, Size, Align, ConstNo, Acc, Refs); +pack_labels([Label|Labels],MFA,ConstTab,AccSize,OldAlign,ConstNo, Acc, Refs) -> + Const = hipe_consttab:lookup(Label, ConstTab), + Align = hipe_consttab:const_align(Const), + NewAlign = erlang:max(Align, OldAlign), + Start = + case AccSize rem Align of + 0 -> AccSize; + N -> AccSize + (Align - N) + end, + %% io:format("Const ~w\n", [Const]), + RawType = hipe_consttab:const_type(Const), + Type = ?CONST_TYPE2EXT(RawType), + RawData = hipe_consttab:const_data(Const), + case RawType of + term -> + %% If the constant term is already in the constant map we want + %% to use the same constant number so that, in the end, the + %% constant term is not duplicated. + case lists:keyfind(RawData, 7, Acc) of + false -> + NewInfo = #pcm_entry{mfa=MFA, label=Label, const_num=ConstNo, + start=0, type=Type, raw_data=RawData}, + pack_labels(Labels, MFA, ConstTab, AccSize, OldAlign, ConstNo+1, + [NewInfo|Acc], Refs); + #pcm_entry{const_num=OtherConstNo, type=Type, raw_data=RawData} -> + NewInfo = #pcm_entry{mfa=MFA, label=Label, const_num=OtherConstNo, + start=0, type=Type, raw_data=RawData}, + pack_labels(Labels, MFA, ConstTab, AccSize, OldAlign, ConstNo, + [NewInfo|Acc], Refs); + _ -> + NewInfo = #pcm_entry{mfa=MFA, label=Label, const_num=ConstNo, + start=0, type=Type, raw_data=RawData}, + pack_labels(Labels, MFA, ConstTab, AccSize, OldAlign, ConstNo+1, + [NewInfo|Acc], Refs) + end; + sorted_block -> + Need = hipe_consttab:const_size(Const), + NewInfo = #pcm_entry{mfa=MFA, label=Label, const_num=ConstNo, + start=Start, type=Type, raw_data=RawData}, + pack_labels(Labels, MFA, ConstTab, Start+Need, NewAlign, ConstNo+1, + [NewInfo|Acc], Refs); + block -> + Need = hipe_consttab:const_size(Const), + {Data, NewRefs} = + case RawData of + {ElementType, ElementData} -> + decompose_block(ElementType, ElementData, Start); + {ElementType, ElementData, SortOrder} -> + {TblData, TblRefs} = get_sorted_refs(ElementData, SortOrder), + {hipe_consttab:decompose({ElementType, TblData}), + [{sorted,Start,TblRefs}]} + end, + NewInfo = #pcm_entry{mfa=MFA, label=Label, const_num=ConstNo, + start=Start, type=Type, raw_data=Data}, + pack_labels(Labels, MFA, ConstTab, Start+Need, NewAlign, ConstNo+1, + [NewInfo|Acc], NewRefs++Refs) + end; +pack_labels([], _, _, Size, Align, ConstNo, Acc, Refs) -> + {Size, Align, Acc, ConstNo, Refs}. + +decompose_block(ElementType, Data, Addr) -> + ElementSize = hipe_consttab:size_of(ElementType), + {NewData, Refs} = get_refs(Data, Addr, ElementSize), + {hipe_consttab:decompose({ElementType, NewData}), Refs}. + +get_refs([{label,L}|Rest], Pos, ElementSize) -> + {NewData, Refs} = get_refs(Rest, Pos+ElementSize, ElementSize), + {[0|NewData], [{L,Pos}|Refs]}; +get_refs([D|Rest], Pos, ElementSize) -> + {NewData, Refs} = get_refs(Rest, Pos+ElementSize, ElementSize), + {[D|NewData], Refs}; +get_refs([], _, _) -> + {[],[]}. + +get_sorted_refs([{label,L}|Rest], [Ordering|Os]) -> + {NewData, Refs} = get_sorted_refs(Rest, Os), + {[0|NewData], [{L,Ordering}|Refs]}; +get_sorted_refs([D|Rest], [_Ordering|Os]) -> + {NewData, Refs} = get_sorted_refs(Rest, Os), + {[D|NewData], Refs}; +get_sorted_refs([], []) -> + {[], []}. + +-type ref_type() :: 0..4. + +-spec slim_refs([{ref_type(),non_neg_integer(),term()}]) -> + [{ref_type(), [{term(), [non_neg_integer()]}]}]. +slim_refs([]) -> []; +slim_refs(Refs) -> + [Ref|Rest] = lists:keysort(1, Refs), + compact_ref_types(Rest, element(1, Ref), [Ref], []). + +compact_ref_types([Ref|Refs], Type, AccofType, Acc) -> + case element(1, Ref) of + Type -> + compact_ref_types(Refs, Type, [Ref|AccofType], Acc); + NewType -> + compact_ref_types(Refs, NewType, [Ref], + [{Type,lists:sort(compact_dests(AccofType))}|Acc]) + end; +compact_ref_types([], Type, AccofType ,Acc) -> + [{Type,lists:sort(compact_dests(AccofType))}|Acc]. + + +%% compact_dests([]) -> []; % clause is redundant +compact_dests(Refs) -> + [Ref|Rest] = lists:keysort(3, Refs), + compact_dests(Rest, element(3,Ref), [element(2,Ref)], []). + +compact_dests([Ref|Refs], Dest, AccofDest, Acc) -> + case element(3, Ref) of + Dest -> + compact_dests(Refs, Dest, [element(2,Ref)|AccofDest], Acc); + NewDest -> + compact_dests(Refs, NewDest, [element(2,Ref)], [{Dest,AccofDest}|Acc]) + end; +compact_dests([], Dest, AccofDest, Acc) -> + [{Dest,AccofDest}|Acc]. + +%% +%% slim_constmap/1 takes a packed ConstMap, as produced by pack_labels +%% called from hipe_pack_constants:pack_constants/2, and converts it +%% to the slimmed and flattened format ConstMap which is put in object +%% files. +%% +-spec slim_constmap([#pcm_entry{}]) -> [raw_data()]. +slim_constmap(Map) -> + slim_constmap(Map, gb_sets:new(), []). + +-spec slim_constmap([#pcm_entry{}], gb_set(), [raw_data()]) -> [raw_data()]. +slim_constmap([#pcm_entry{const_num=ConstNo, start=Offset, + type=Type, raw_data=Term}|Rest], Inserted, Acc) -> + case gb_sets:is_member(ConstNo, Inserted) of + true -> + slim_constmap(Rest, Inserted, Acc); + false -> + NewInserted = gb_sets:insert(ConstNo, Inserted), + slim_constmap(Rest, NewInserted, [ConstNo, Offset, Type, Term|Acc]) + end; +slim_constmap([], _Inserted, Acc) -> Acc. diff --git a/lib/hipe/misc/hipe_sdi.erl b/lib/hipe/misc/hipe_sdi.erl new file mode 100644 index 0000000000..ef1b5b48c5 --- /dev/null +++ b/lib/hipe/misc/hipe_sdi.erl @@ -0,0 +1,378 @@ +%%% -*- 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% +%%% +%%% An implementation of the algorithm described in: +%%% "Assembling Code for Machines with Span-Dependent Instructions", +%%% Thomas G. Szymanski, CACM 21(4), April 1978, pp. 300--308. +%%% +%%% Copyright (C) 2000, 2004, 2007 Mikael Pettersson + +-module(hipe_sdi). +-export([pass1_init/0, + pass1_add_label/3, + pass1_add_sdi/4, + pass2/1]). + +-include("hipe_sdi.hrl"). + +%%------------------------------------------------------------------------ + +-type hipe_array() :: integer(). % declare this in hipe.hrl or builtin? + +-type label() :: non_neg_integer(). +-type address() :: non_neg_integer(). + +%%------------------------------------------------------------------------ + +-record(label_data, {address :: address(), + prevSdi :: integer()}). + +-record(pre_sdi_data, {address :: address(), + label :: label(), + si :: #sdi_info{}}). + +-record(pass1, {prevSdi :: integer(), + preS = [] :: [#pre_sdi_data{}], + labelMap = gb_trees:empty() :: gb_tree()}). + +-record(sdi_data, {address :: address(), + label_address :: address(), + prevSdi :: integer(), %% -1 is the first previous + si :: #sdi_info{}}). + +%%------------------------------------------------------------------------ + +%%% "During the first pass we assign addresses to instructions +%%% and build a symbol table of labels and their addresses +%%% according to the minimum address assignment. We do this by +%%% treating each sdi as having its shorter length. We also +%%% number the sdi's [sic] from 1 to n in order of occurrence +%%% and record in the symbol table entry for each label the +%%% number of sdi's [sic] preceding it in the program. +%%% Simultaneously with pass 1 we build a set +%%% S = {(i,a,l,c) | 1 <= i <= n, a is the minimum address of +%%% the ith sdi, l and c, are the label and constant +%%% components of the operand of the ith sdi respectively}." +%%% +%%% Implementation notes: +%%% - We number the SDIs from 0 to n-1, not from 1 to n. +%%% - SDIs target only labels, so the constant offsets are omitted. +%%% - The set S is represented by a vector S[0..n-1] such that if +%%% (i,a,l) is in the set, then S[i] = (a,l). +%%% - The symbol table maps a label to its minimum address and the +%%% number of the last SDI preceding it (-1 if none). +%%% - To allow this module to make architecture-specific decisions +%%% without using callbacks or making it architecture-specific, +%%% the elements in the set S include a fourth component, SdiInfo, +%%% supplied by the caller of this module. +%%% - At the end of the first pass we finalise the preliminary SDIs +%%% by replacing their symbolic target labels with the corresponding +%%% data from the symbol table. This avoids repeated O(logn) time +%%% lookup costs for the labels. + +-spec pass1_init() -> #pass1{}. +pass1_init() -> + #pass1{prevSdi = -1}. + +-spec pass1_add_label(#pass1{}, non_neg_integer(), label()) -> #pass1{}. +pass1_add_label(Pass1, Address, Label) -> + #pass1{prevSdi=PrevSdi, labelMap=LabelMap} = Pass1, + LabelData = #label_data{address=Address, prevSdi=PrevSdi}, + LabelMap2 = gb_trees:insert(Label, LabelData, LabelMap), + Pass1#pass1{labelMap=LabelMap2}. + +-spec pass1_add_sdi(#pass1{}, non_neg_integer(), label(), #sdi_info{}) -> + #pass1{}. +pass1_add_sdi(Pass1, Address, Label, SdiInfo) -> + #pass1{prevSdi=PrevSdi, preS=PreS} = Pass1, + PreSdiData = #pre_sdi_data{address=Address, label=Label, si=SdiInfo}, + Pass1#pass1{prevSdi=PrevSdi+1, preS=[PreSdiData|PreS]}. + +-spec pass1_finalise(#pass1{}) -> {non_neg_integer(),tuple(),gb_tree()}. +pass1_finalise(#pass1{prevSdi=PrevSdi, preS=PreS, labelMap=LabelMap}) -> + {PrevSdi+1, pass1_finalise_preS(PreS, LabelMap, []), LabelMap}. + +-spec pass1_finalise_preS([#pre_sdi_data{}], gb_tree(), [#sdi_data{}]) -> + tuple(). +pass1_finalise_preS([], _LabelMap, S) -> vector_from_list(S); +pass1_finalise_preS([PreSdiData|PreS], LabelMap, S) -> + #pre_sdi_data{address=Address, label=Label, si=SdiInfo} = PreSdiData, + LabelData = gb_trees:get(Label, LabelMap), + #label_data{address=LabelAddress, prevSdi=PrevSdi} = LabelData, + SdiData = #sdi_data{address=Address, label_address=LabelAddress, + prevSdi=PrevSdi, si=SdiInfo}, + pass1_finalise_preS(PreS, LabelMap, [SdiData|S]). + +%%% Pass2. + +-spec pass2(#pass1{}) -> {gb_tree(), non_neg_integer()}. +pass2(Pass1) -> + {N,SDIS,LabelMap} = pass1_finalise(Pass1), + LONG = mk_long(N), + SPAN = mk_span(N, SDIS), + PARENTS = mk_parents(N, SDIS), + update_long(N, SDIS, SPAN, PARENTS, LONG), + {INCREMENT,CodeSizeIncr} = mk_increment(N, LONG), + {adjust_label_map(LabelMap, INCREMENT), CodeSizeIncr}. + +%%% "Between passes 1 and 2 we will construct an integer table +%%% LONG[1:n] such that LONG[i] is nonzero if and only if the +%%% ith sdi must be given a long form translation. Initially +%%% LONG[i] is zero for all i." +%%% +%%% Implementation notes: +%%% - LONG is an integer array indexed from 0 to N-1. + +-spec mk_long(non_neg_integer()) -> hipe_array(). +mk_long(N) -> + mk_array_of_zeros(N). + +%%% "At the heart of our algorithm is a graphical representation +%%% of the interdependencies of the sdi's [sic] of the program. +%%% For each sdi we construct a node containing the empty span +%%% of that instruction. Nodes of this graph will be referred to +%%% by the number of the sdi to which they correspond. Directed +%%% arcs are now added to the graph so that i->j is an arc if +%%% and only if the span of the ith sdi depends on the size of +%%% the jth sdi, that is, the jth sdi lies between the ith sdi +%%% and the label occurring in its operand. It is easy to see +%%% that the graph we have just described can be constructed from +%%% the information present in the set S and the symbol table. +%%% +%%% The significance if this graph is that sizes can be assigned +%%% to the sdi's [sic] of the program so that the span of the ith +%%% sdi is equal to the number appearing in node i if and only if +%%% all the children of i can be given short translations." +%%% +%%% Implementation notes: +%%% - The nodes are represented by an integer array SPAN[0..n-1] +%%% such that SPAN[i] contains the current span of sdi i. +%%% - Since the graph is traversed from child to parent nodes in +%%% Step 3, the edges are represented by a vector PARENTS[0..n-1] +%%% such that PARENTS[j] = { i | i is a parent of j }. +%%% - An explicit PARENTS graph would have size O(n^2). Instead we +%%% compute PARENTS[j] from the SDI vector when needed. This +%%% reduces memory overheads, and may reduce time overheads too. + +-spec mk_span(non_neg_integer(), tuple()) -> hipe_array(). +mk_span(N, SDIS) -> + initSPAN(0, N, SDIS, mk_array_of_zeros(N)). + +-spec initSPAN(non_neg_integer(), non_neg_integer(), + tuple(), hipe_array()) -> hipe_array(). +initSPAN(SdiNr, N, SDIS, SPAN) -> + if SdiNr >= N -> SPAN; + true -> + SdiData = vector_sub(SDIS, SdiNr), + #sdi_data{address=SdiAddress, label_address=LabelAddress} = SdiData, + SdiSpan = LabelAddress - SdiAddress, + array_update(SPAN, SdiNr, SdiSpan), + initSPAN(SdiNr+1, N, SDIS, SPAN) + end. + +mk_parents(N, SDIS) -> {N,SDIS}. + +%%% "After the structure is built we process it as follows. +%%% For any node i whose listed span exceeds the architectural +%%% limit for a short form instruction, the LONG[i] equal to +%%% the difference between the long and short forms of the ith +%%% sdi. Increment the span of each parent of i by LONG[i] if +%%% the parent precedes the child in the program. Otherwise, +%%% decrement the span of the parent by LONG[i]. Finally, remove +%%% node i from the graph. Clearly this process must terminate. +%%% Any nodes left in the final graph correspond to sdi's [sic] +%%% which can be translated in the short form." +%%% +%%% Implementation notes: +%%% - We use a simple worklist algorithm, operating on a set +%%% of SDIs known to require long form. +%%% - A node is removed from the graph by setting its span to zero. +%%% - The result is the updated LONG array. Afterwards, S, SPAN, +%%% and PARENTS are no longer useful. + +-spec update_long(non_neg_integer(), tuple(), hipe_array(), + {non_neg_integer(),tuple()},hipe_array()) -> 'ok'. +update_long(N, SDIS, SPAN, PARENTS, LONG) -> + WKL = initWKL(N-1, SDIS, SPAN, []), + processWKL(WKL, SDIS, SPAN, PARENTS, LONG). + +-spec initWKL(integer(), tuple(), + hipe_array(), [non_neg_integer()]) -> [non_neg_integer()]. +initWKL(SdiNr, SDIS, SPAN, WKL) -> + if SdiNr < 0 -> WKL; + true -> + SdiSpan = array_sub(SPAN, SdiNr), + WKL2 = updateWKL(SdiNr, SDIS, SdiSpan, WKL), + initWKL(SdiNr-1, SDIS, SPAN, WKL2) + end. + +-spec processWKL([non_neg_integer()], tuple(), hipe_array(), + {non_neg_integer(), tuple()}, hipe_array()) -> 'ok'. +processWKL([], _SDIS, _SPAN, _PARENTS, _LONG) -> ok; +processWKL([Child|WKL], SDIS, SPAN, PARENTS, LONG) -> + WKL2 = updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG), + processWKL(WKL2, SDIS, SPAN, PARENTS, LONG). + +-spec updateChild(non_neg_integer(), [non_neg_integer()], tuple(), hipe_array(), + {non_neg_integer(),tuple()}, hipe_array()) -> [non_neg_integer()]. +updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG) -> + case array_sub(SPAN, Child) of + 0 -> WKL; % removed + _ -> + SdiData = vector_sub(SDIS, Child), + Incr = sdiLongIncr(SdiData), + array_update(LONG, Child, Incr), + array_update(SPAN, Child, 0), % remove child + PS = parentsOfChild(PARENTS, Child), + updateParents(PS, Child, Incr, SDIS, SPAN, WKL) + end. + +-spec parentsOfChild({non_neg_integer(),tuple()}, + non_neg_integer()) -> [non_neg_integer()]. +parentsOfChild({N,SDIS}, Child) -> + parentsOfChild(N-1, SDIS, Child, []). + +-spec parentsOfChild(integer(), tuple(), non_neg_integer(), + [non_neg_integer()]) -> [non_neg_integer()]. +parentsOfChild(-1, _SDIS, _Child, PS) -> PS; +parentsOfChild(SdiNr, SDIS, Child, PS) -> + SdiData = vector_sub(SDIS, SdiNr), + #sdi_data{prevSdi=PrevSdi} = SdiData, + {LO,HI} = % inclusive + if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi}; % forwards + true -> {PrevSdi+1, SdiNr-1} % backwards + end, + NewPS = + if LO =< Child, Child =< HI -> [SdiNr | PS]; + true -> PS + end, + parentsOfChild(SdiNr-1, SDIS, Child, NewPS). + +-spec updateParents([non_neg_integer()], non_neg_integer(), + byte(), tuple(), hipe_array(), + [non_neg_integer()]) -> [non_neg_integer()]. +updateParents([], _Child, _Incr, _SDIS, _SPAN, WKL) -> WKL; +updateParents([P|PS], Child, Incr, SDIS, SPAN, WKL) -> + WKL2 = updateParent(P, Child, Incr, SDIS, SPAN, WKL), + updateParents(PS, Child, Incr, SDIS, SPAN, WKL2). + +-spec updateParent(non_neg_integer(), non_neg_integer(), + byte(), tuple(), hipe_array(), + [non_neg_integer()]) -> [non_neg_integer()]. +updateParent(Parent, Child, Incr, SDIS, SPAN, WKL) -> + case array_sub(SPAN, Parent) of + 0 -> WKL; % removed + OldSpan -> + NewSpan = + if Parent < Child -> OldSpan + Incr; + true -> OldSpan - Incr + end, + array_update(SPAN, Parent, NewSpan), + updateWKL(Parent, SDIS, NewSpan, WKL) + end. + +-spec updateWKL(non_neg_integer(), tuple(), + integer(), [non_neg_integer()]) -> [non_neg_integer()]. +updateWKL(SdiNr, SDIS, SdiSpan, WKL) -> + case sdiSpanIsShort(vector_sub(SDIS, SdiNr), SdiSpan) of + true -> WKL; + false -> [SdiNr|WKL] + end. + +-spec sdiSpanIsShort(#sdi_data{}, integer()) -> boolean(). +sdiSpanIsShort(#sdi_data{si = #sdi_info{lb = LB, ub = UB}}, SdiSpan) -> + SdiSpan >= LB andalso SdiSpan =< UB. + +-spec sdiLongIncr(#sdi_data{}) -> byte(). +sdiLongIncr(#sdi_data{si = #sdi_info{incr = Incr}}) -> Incr. + +%%% "Now construct a table INCREMENT[0:n] by defining +%%% INCREMENT[0] = 0 and INCREMENT[i] = INCREMENT[i-1]+LONG[i] +%%% for 1 <= i <= n. INCREMENT[i] represents the total increase +%%% in size of the first i sdi's [sic] in the program." +%%% +%%% Implementation notes: +%%% - INCREMENT is an integer vector indexed from 0 to n-1. +%%% INCREMENT[i] = SUM(0 <= j <= i)(LONG[j]), for 0 <= i < n. +%%% - Due to the lack of an SML-like Array.extract operation, +%%% INCREMENT is an array, not an immutable vector. + +-spec mk_increment(non_neg_integer(), hipe_array()) -> + {hipe_array(), non_neg_integer()}. +mk_increment(N, LONG) -> + initINCR(0, 0, N, LONG, mk_array_of_zeros(N)). + +-spec initINCR(non_neg_integer(), non_neg_integer(), non_neg_integer(), + hipe_array(), hipe_array()) -> {hipe_array(), non_neg_integer()}. +initINCR(SdiNr, PrevIncr, N, LONG, INCREMENT) -> + if SdiNr >= N -> {INCREMENT, PrevIncr}; + true -> + SdiIncr = PrevIncr + array_sub(LONG, SdiNr), + array_update(INCREMENT, SdiNr, SdiIncr), + initINCR(SdiNr+1, SdiIncr, N, LONG, INCREMENT) + end. + +%%% "At this point we can adjust the addresses of each label L +%%% in the symbol table. If L is preceded by i sdi's [sic] in +%%% the program, then add INCREMENT[i] to the value of L in the +%%% symbol table." +%%% +%%% Implementation notes: +%%% - Due to the 0..n-1 SDI numbering, a label L with address +%%% a and previous sdi i is remapped to a+incr(i), where +%%% incr(i) = if i < 0 then 0 else INCREMENT[i]. + +-spec adjust_label_map(gb_tree(), hipe_array()) -> gb_tree(). +adjust_label_map(LabelMap, INCREMENT) -> + applyIncr(gb_trees:to_list(LabelMap), INCREMENT, gb_trees:empty()). + +-type label_pair() :: {label(), #label_data{}}. + +-spec applyIncr([label_pair()], hipe_array(), gb_tree()) -> gb_tree(). +applyIncr([], _INCREMENT, LabelMap) -> LabelMap; +applyIncr([{Label,LabelData}|List], INCREMENT, LabelMap) -> + #label_data{address=Address, prevSdi=PrevSdi} = LabelData, + Incr = + if PrevSdi < 0 -> 0; + true -> array_sub(INCREMENT, PrevSdi) + end, + applyIncr(List, INCREMENT, gb_trees:insert(Label, Address+Incr, LabelMap)). + +%%% ADT for immutable vectors, indexed from 0 to N-1. +%%% Currently implemented as tuples. +%%% Used for the 'SDIS' and 'PARENTS' vectors. + +-spec vector_from_list([#sdi_data{}]) -> tuple(). +vector_from_list(Values) -> list_to_tuple(Values). + +vector_sub(Vec, I) -> element(I+1, Vec). + +%%% ADT for mutable integer arrays, indexed from 0 to N-1. +%%% Currently implemented as HiPE arrays. +%%% Used for the 'LONG', 'SPAN', and 'INCREMENT' arrays. + +-spec mk_array_of_zeros(non_neg_integer()) -> hipe_array(). +mk_array_of_zeros(N) -> hipe_bifs:array(N, 0). + +-spec array_update(hipe_array(), non_neg_integer(), integer()) -> hipe_array(). +array_update(A, I, V) -> hipe_bifs:array_update(A, I, V). + +-spec array_sub(hipe_array(), non_neg_integer()) -> integer(). +array_sub(A, I) -> hipe_bifs:array_sub(A, I). diff --git a/lib/hipe/misc/hipe_sdi.hrl b/lib/hipe/misc/hipe_sdi.hrl new file mode 100644 index 0000000000..f89cae1529 --- /dev/null +++ b/lib/hipe/misc/hipe_sdi.hrl @@ -0,0 +1,25 @@ +%% -*- 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% +%% + + +-record(sdi_info, + {lb :: integer(), % span lower bound for short form + ub :: integer(), % span upper bound for short form + incr :: byte()}). % instruction size increase for long form |