The R13B03 release.OTP_R13B03

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