19
19
%%------------------------------------------------------------------------
21
-type(gb_tree() :: tuple()). % temporarily until there is a proper datatype
22
-type(hipe_array() :: [] | integer()). % declare this in hipe.hrl or builtin?
21
-type gb_tree() :: tuple(). % temporarily until there is a proper datatype
22
-type hipe_array() :: integer(). % declare this in hipe.hrl or builtin?
24
-type(label() :: non_neg_integer()).
25
-type(address() :: non_neg_integer()).
24
-type label() :: non_neg_integer().
25
-type address() :: non_neg_integer().
27
27
%%------------------------------------------------------------------------
72
72
%%% data from the symbol table. This avoids repeated O(logn) time
73
73
%%% lookup costs for the labels.
75
-spec(pass1_init/0 :: () -> #pass1{}).
75
-spec pass1_init() -> #pass1{}.
77
77
#pass1{prevSdi=(-1), preS=[], labelMap=gb_trees:empty()}.
79
-spec(pass1_add_label/3 :: (#pass1{}, non_neg_integer(), label()) -> #pass1{}).
79
-spec pass1_add_label(#pass1{}, non_neg_integer(), label()) -> #pass1{}.
80
80
pass1_add_label(Pass1, Address, Label) ->
81
81
#pass1{prevSdi=PrevSdi, labelMap=LabelMap} = Pass1,
82
82
LabelData = #label_data{address=Address, prevSdi=PrevSdi},
83
83
LabelMap2 = gb_trees:insert(Label, LabelData, LabelMap),
84
84
Pass1#pass1{labelMap=LabelMap2}.
86
-spec(pass1_add_sdi/4 ::
87
(#pass1{}, non_neg_integer(), label(), #sdi_info{}) -> #pass1{}).
86
-spec pass1_add_sdi(#pass1{}, non_neg_integer(), label(), #sdi_info{}) ->
88
88
pass1_add_sdi(Pass1, Address, Label, SdiInfo) ->
89
89
#pass1{prevSdi=PrevSdi, preS=PreS} = Pass1,
90
90
PreSdiData = #pre_sdi_data{address=Address, label=Label, si=SdiInfo},
91
91
Pass1#pass1{prevSdi=PrevSdi+1, preS=[PreSdiData|PreS]}.
93
-spec(pass1_finalise/1 :: (#pass1{}) -> {non_neg_integer(),tuple(),gb_tree()}).
93
-spec pass1_finalise(#pass1{}) -> {non_neg_integer(),tuple(),gb_tree()}.
94
94
pass1_finalise(#pass1{prevSdi=PrevSdi, preS=PreS, labelMap=LabelMap}) ->
95
95
{PrevSdi+1, pass1_finalise_preS(PreS, LabelMap, []), LabelMap}.
97
-spec(pass1_finalise_preS/3 ::
98
([#pre_sdi_data{}], gb_tree(), [#sdi_data{}]) -> tuple()).
97
-spec pass1_finalise_preS([#pre_sdi_data{}], gb_tree(), [#sdi_data{}]) ->
99
99
pass1_finalise_preS([], _LabelMap, S) -> vector_from_list(S);
100
100
pass1_finalise_preS([PreSdiData|PreS], LabelMap, S) ->
101
101
#pre_sdi_data{address=Address, label=Label, si=SdiInfo} = PreSdiData,
156
156
%%% compute PARENTS[j] from the SDI vector when needed. This
157
157
%%% reduces memory overheads, and may reduce time overheads too.
159
-spec(mk_span/2 :: (non_neg_integer(), tuple()) -> hipe_array()).
159
-spec mk_span(non_neg_integer(), tuple()) -> hipe_array().
160
160
mk_span(N, SDIS) ->
161
161
initSPAN(0, N, SDIS, mk_array_of_zeros(N)).
163
-spec(initSPAN/4 :: (non_neg_integer(), non_neg_integer(),
164
tuple(), hipe_array()) -> hipe_array()).
163
-spec initSPAN(non_neg_integer(), non_neg_integer(),
164
tuple(), hipe_array()) -> hipe_array().
165
165
initSPAN(SdiNr, N, SDIS, SPAN) ->
166
166
if SdiNr >= N -> SPAN;
192
192
%%% - The result is the updated LONG array. Afterwards, S, SPAN,
193
193
%%% and PARENTS are no longer useful.
195
-spec(update_long/5 :: (non_neg_integer(), tuple(), hipe_array(),
196
{non_neg_integer(),tuple()},hipe_array()) -> 'ok').
195
-spec update_long(non_neg_integer(), tuple(), hipe_array(),
196
{non_neg_integer(),tuple()},hipe_array()) -> 'ok'.
197
197
update_long(N, SDIS, SPAN, PARENTS, LONG) ->
198
198
WKL = initWKL(N-1, SDIS, SPAN, []),
199
199
processWKL(WKL, SDIS, SPAN, PARENTS, LONG).
201
-spec(initWKL/4 :: (integer(), tuple(),
202
hipe_array(), [non_neg_integer()]) -> [non_neg_integer()]).
201
-spec initWKL(integer(), tuple(),
202
hipe_array(), [non_neg_integer()]) -> [non_neg_integer()].
203
203
initWKL(SdiNr, SDIS, SPAN, WKL) ->
204
204
if SdiNr < 0 -> WKL;
208
208
initWKL(SdiNr-1, SDIS, SPAN, WKL2)
211
-spec(processWKL/5 :: ([non_neg_integer()], tuple(), hipe_array(),
212
{non_neg_integer(), tuple()}, hipe_array()) -> 'ok').
211
-spec processWKL([non_neg_integer()], tuple(), hipe_array(),
212
{non_neg_integer(), tuple()}, hipe_array()) -> 'ok'.
213
213
processWKL([], _SDIS, _SPAN, _PARENTS, _LONG) -> ok;
214
214
processWKL([Child|WKL], SDIS, SPAN, PARENTS, LONG) ->
215
215
WKL2 = updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG),
216
216
processWKL(WKL2, SDIS, SPAN, PARENTS, LONG).
218
-spec(updateChild/6 ::
219
(non_neg_integer(), [non_neg_integer()], tuple(), hipe_array(),
220
{non_neg_integer(),tuple()}, hipe_array()) -> [non_neg_integer()]).
218
-spec updateChild(non_neg_integer(), [non_neg_integer()], tuple(), hipe_array(),
219
{non_neg_integer(),tuple()}, hipe_array()) -> [non_neg_integer()].
221
220
updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG) ->
222
221
case array_sub(SPAN, Child) of
223
222
0 -> WKL; % removed
230
229
updateParents(PS, Child, Incr, SDIS, SPAN, WKL)
233
-spec(parentsOfChild/2 :: ({non_neg_integer(),tuple()},
234
non_neg_integer()) -> [non_neg_integer()]).
232
-spec parentsOfChild({non_neg_integer(),tuple()},
233
non_neg_integer()) -> [non_neg_integer()].
235
234
parentsOfChild({N,SDIS}, Child) ->
236
235
parentsOfChild(N-1, SDIS, Child, []).
238
-spec(parentsOfChild/4 :: (integer(), tuple(), non_neg_integer(),
239
[non_neg_integer()]) -> [non_neg_integer()]).
237
-spec parentsOfChild(integer(), tuple(), non_neg_integer(),
238
[non_neg_integer()]) -> [non_neg_integer()].
240
239
parentsOfChild(-1, _SDIS, _Child, PS) -> PS;
241
240
parentsOfChild(SdiNr, SDIS, Child, PS) ->
242
241
SdiData = vector_sub(SDIS, SdiNr),
252
251
parentsOfChild(SdiNr-1, SDIS, Child, NewPS).
254
-spec(updateParents/6 :: ([non_neg_integer()], non_neg_integer(),
255
byte(), tuple(), hipe_array(),
256
[non_neg_integer()]) -> [non_neg_integer()]).
253
-spec updateParents([non_neg_integer()], non_neg_integer(),
254
byte(), tuple(), hipe_array(),
255
[non_neg_integer()]) -> [non_neg_integer()].
257
256
updateParents([], _Child, _Incr, _SDIS, _SPAN, WKL) -> WKL;
258
257
updateParents([P|PS], Child, Incr, SDIS, SPAN, WKL) ->
259
258
WKL2 = updateParent(P, Child, Incr, SDIS, SPAN, WKL),
260
259
updateParents(PS, Child, Incr, SDIS, SPAN, WKL2).
262
-spec(updateParent/6 :: (non_neg_integer(), non_neg_integer(),
263
byte(), tuple(), hipe_array(),
264
[non_neg_integer()]) -> [non_neg_integer()]).
261
-spec updateParent(non_neg_integer(), non_neg_integer(),
262
byte(), tuple(), hipe_array(),
263
[non_neg_integer()]) -> [non_neg_integer()].
265
264
updateParent(Parent, Child, Incr, SDIS, SPAN, WKL) ->
266
265
case array_sub(SPAN, Parent) of
267
266
0 -> WKL; % removed
274
273
updateWKL(Parent, SDIS, NewSpan, WKL)
277
-spec(updateWKL/4 :: (non_neg_integer(), tuple(),
278
integer(), [non_neg_integer()]) -> [non_neg_integer()]).
276
-spec updateWKL(non_neg_integer(), tuple(),
277
integer(), [non_neg_integer()]) -> [non_neg_integer()].
279
278
updateWKL(SdiNr, SDIS, SdiSpan, WKL) ->
280
279
case sdiSpanIsShort(vector_sub(SDIS, SdiNr), SdiSpan) of
282
281
false -> [SdiNr|WKL]
285
-spec(sdiSpanIsShort/2 :: (#sdi_data{}, integer()) -> bool()).
284
-spec sdiSpanIsShort(#sdi_data{}, integer()) -> bool().
286
285
sdiSpanIsShort(#sdi_data{si=#sdi_info{lb=LB,ub=UB}}, SdiSpan) ->
287
286
SdiSpan >= LB andalso SdiSpan =< UB.
289
-spec(sdiLongIncr/1 :: (#sdi_data{}) -> byte()).
288
-spec sdiLongIncr(#sdi_data{}) -> byte().
290
289
sdiLongIncr(#sdi_data{si=#sdi_info{incr=Incr}}) -> Incr.
292
291
%%% "Now construct a table INCREMENT[0:n] by defining
300
299
%%% - Due to the lack of an SML-like Array.extract operation,
301
300
%%% INCREMENT is an array, not an immutable vector.
303
-spec(mk_increment/2 ::
304
(non_neg_integer(), hipe_array()) -> {hipe_array(), non_neg_integer()}).
302
-spec mk_increment(non_neg_integer(), hipe_array()) ->
303
{hipe_array(), non_neg_integer()}.
305
304
mk_increment(N, LONG) ->
306
305
initINCR(0, 0, N, LONG, mk_array_of_zeros(N)).
308
-spec(initINCR/5 :: (non_neg_integer(), non_neg_integer(), non_neg_integer(),
309
hipe_array(), hipe_array()) ->
310
{hipe_array(), non_neg_integer()}).
307
-spec initINCR(non_neg_integer(), non_neg_integer(), non_neg_integer(),
308
hipe_array(), hipe_array()) -> {hipe_array(), non_neg_integer()}.
311
309
initINCR(SdiNr, PrevIncr, N, LONG, INCREMENT) ->
312
310
if SdiNr >= N -> {INCREMENT, PrevIncr};
326
324
%%% a and previous sdi i is remapped to a+incr(i), where
327
325
%%% incr(i) = if i < 0 then 0 else INCREMENT[i].
329
-spec(adjust_label_map/2 :: (gb_tree(), hipe_array()) -> gb_tree()).
327
-spec adjust_label_map(gb_tree(), hipe_array()) -> gb_tree().
330
328
adjust_label_map(LabelMap, INCREMENT) ->
331
329
applyIncr(gb_trees:to_list(LabelMap), INCREMENT, gb_trees:empty()).
333
-type(label_pair() :: {label(), #label_data{}}).
331
-type label_pair() :: {label(), #label_data{}}.
335
-spec(applyIncr/3 :: ([label_pair()], hipe_array(), gb_tree()) -> gb_tree()).
333
-spec applyIncr([label_pair()], hipe_array(), gb_tree()) -> gb_tree().
336
334
applyIncr([], _INCREMENT, LabelMap) -> LabelMap;
337
335
applyIncr([{Label,LabelData}|List], INCREMENT, LabelMap) ->
338
336
#label_data{address=Address, prevSdi=PrevSdi} = LabelData,
346
344
%%% Currently implemented as tuples.
347
345
%%% Used for the 'SDIS' and 'PARENTS' vectors.
349
-spec(vector_from_list/1 :: ([#sdi_data{}]) -> tuple()).
347
-spec vector_from_list([#sdi_data{}]) -> tuple().
350
348
vector_from_list(Values) -> list_to_tuple(Values).
352
350
vector_sub(Vec, I) -> element(I+1, Vec).
355
353
%%% Currently implemented as HiPE arrays.
356
354
%%% Used for the 'LONG', 'SPAN', and 'INCREMENT' arrays.
358
-spec(mk_array_of_zeros/1 :: (non_neg_integer()) -> hipe_array()).
356
-spec mk_array_of_zeros(non_neg_integer()) -> hipe_array().
359
357
mk_array_of_zeros(N) -> hipe_bifs:array(N, 0).
361
-spec(array_update/3 :: (hipe_array(), non_neg_integer(), integer()) -> []).
359
-spec array_update(hipe_array(), non_neg_integer(), integer()) -> hipe_array().
362
360
array_update(A, I, V) -> hipe_bifs:array_update(A, I, V).
364
-spec(array_sub/2 :: (hipe_array(), non_neg_integer()) -> integer()).
362
-spec array_sub(hipe_array(), non_neg_integer()) -> integer().
365
363
array_sub(A, I) -> hipe_bifs:array_sub(A, I).