%%% -*- erlang-indent-level: 2 -*-
%%%======================================================================
%%%
%%% Licensed under the Apache License, Version 2.0 (the "License");
%%% you may not use this file except in compliance with the License.
%%% You may obtain a copy of the License at
%%%
%%% http://www.apache.org/licenses/LICENSE-2.0
%%%
%%% Unless required by applicable law or agreed to in writing, software
%%% distributed under the License is distributed on an "AS IS" BASIS,
%%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%%% See the License for the specific language governing permissions and
%%% limitations under the License.
%%%
%%% 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 hipe_vector(E) :: {} | {E} | {E, E} | {E, E, E} | tuple().
-type label() :: non_neg_integer().
-type address() :: non_neg_integer().
-type parents() :: {hipe_vector(_ :: integer()), hipe_segment_trees:tree()}.
%%------------------------------------------------------------------------
-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_trees: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_trees: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_trees: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_trees: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
%%% observe that (i is a parent of j) iff (j \in range(i)), where
%%% range(i) is a constant function. We can thus precompute all the
%%% ranges i and insert them into a data structure built for such
%%% queries. In this case, we use a segment tree.
-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.
-spec mk_parents(non_neg_integer(), tuple()) -> parents().
mk_parents(N, SDIS) ->
PrevSDIS = vector_from_list(select_prev_sdis(N-1, SDIS, [])),
Ranges = parents_generate_ranges(N-1, PrevSDIS, []),
{PrevSDIS, hipe_segment_trees:build(Ranges)}.
select_prev_sdis(-1, _SDIS, Acc) -> Acc;
select_prev_sdis(SdiNr, SDIS, Acc) ->
#sdi_data{prevSdi=PrevSdi} = vector_sub(SDIS, SdiNr),
select_prev_sdis(SdiNr-1, SDIS, [PrevSdi|Acc]).
parents_generate_ranges(-1, _PrevSDIS, Acc) -> Acc;
parents_generate_ranges(SdiNr, PrevSDIS, Acc) ->
%% inclusive
{LO,HI} = parents_generate_range(SdiNr, PrevSDIS),
parents_generate_ranges(SdiNr-1, PrevSDIS, [{LO,HI}|Acc]).
-compile({inline, parents_generate_range/2}).
parents_generate_range(SdiNr, PrevSDIS) ->
PrevSdi = vector_sub(PrevSDIS, SdiNr),
if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi}; % forwards
true -> {PrevSdi+1, SdiNr-1} % backwards
end.
%%% "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(),
parents(),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(),
parents(), hipe_array()) -> 'ok'.
processWKL([], _SDIS, _SPAN, _PARENTS, _LONG) -> ok;
processWKL([Child|WKL], SDIS, SPAN, PARENTS0, LONG) ->
{WKL2, PARENTS} =
case array_sub(SPAN, Child) of
0 -> {WKL, PARENTS0}; % removed
_ ->
SdiData = vector_sub(SDIS, Child),
Incr = sdiLongIncr(SdiData),
array_update(LONG, Child, Incr),
array_update(SPAN, Child, 0), % remove child
PARENTS1 = deleteParent(PARENTS0, Child),
PS = parentsOfChild(PARENTS1, Child),
{updateParents(PS, Child, Incr, SDIS, SPAN, WKL), PARENTS1}
end,
processWKL(WKL2, SDIS, SPAN, PARENTS, LONG).
-spec parentsOfChild(parents(), non_neg_integer()) -> [non_neg_integer()].
parentsOfChild({_PrevSDIS, SegTree}, Child) ->
hipe_segment_trees:intersect(Child, SegTree).
-spec deleteParent(parents(), non_neg_integer()) -> parents().
deleteParent({PrevSDIS, SegTree0}, Parent) ->
{LO,HI} = parents_generate_range(Parent, PrevSDIS),
SegTree = hipe_segment_trees:delete(Parent, LO, HI, SegTree0),
{PrevSDIS, SegTree}.
-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.
-compile({inline, sdiSpanIsShort/2}). %% Only called once
-spec sdiSpanIsShort(#sdi_data{}, integer()) -> boolean().
sdiSpanIsShort(#sdi_data{si = #sdi_info{lb = LB, ub = UB}}, SdiSpan) ->
SdiSpan >= LB andalso SdiSpan =< UB.
-compile({inline, sdiLongIncr/1}). %% Only called once
-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_trees:tree(), hipe_array()) -> gb_trees: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_trees:tree()) ->
gb_trees: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([E]) -> hipe_vector(E).
vector_from_list(Values) -> list_to_tuple(Values).
-compile({inline, vector_sub/2}).
-spec vector_sub(hipe_vector(E), non_neg_integer()) -> V when V :: E.
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).
-compile({inline, array_update/3}).
-spec array_update(hipe_array(), non_neg_integer(), integer()) -> hipe_array().
array_update(A, I, V) -> hipe_bifs:array_update(A, I, V).
-compile({inline, array_sub/2}).
-spec array_sub(hipe_array(), non_neg_integer()) -> integer().
array_sub(A, I) -> hipe_bifs:array_sub(A, I).
