From 84adefa331c4159d432d22840663c38f155cd4c1 Mon Sep 17 00:00:00 2001 From: Erlang/OTP Date: Fri, 20 Nov 2009 14:54:40 +0000 Subject: The R13B03 release. --- lib/hipe/misc/hipe_sdi.erl | 378 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 378 insertions(+) create mode 100644 lib/hipe/misc/hipe_sdi.erl (limited to 'lib/hipe/misc/hipe_sdi.erl') 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). -- cgit v1.2.3