← Back to branch summary

~rdoering/ubuntu/karmic/erlang/fix-535090

« back to all changes in this revision

Viewing changes to lib/hipe/misc/hipe_sdi.erl

  • Committer: Bazaar Package Importer
  • Author(s): Sergei Golovan
  • Date: 2009-02-15 16:42:52 UTC
  • mfrom: (3.1.2 squeeze)
  • Revision ID: james.westby@ubuntu.com-20090215164252-q5x4rcf8a5pbesb1
Tags: 1:12.b.5-dfsg-2
Upload to unstable after lenny is released.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/hipe/misc/hipe_sdi.erl
18
18
 
19
19
%%------------------------------------------------------------------------
20
20
 
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?
23
23
 
24
 
-type(label()      :: non_neg_integer()).
25
 
-type(address()    :: non_neg_integer()).
 
24
-type label()      :: non_neg_integer().
 
25
-type address()    :: non_neg_integer().
26
26
 
27
27
%%------------------------------------------------------------------------
28
28
 
72
72
%%%   data from the symbol table. This avoids repeated O(logn) time
73
73
%%%   lookup costs for the labels.
74
74
 
75
 
-spec(pass1_init/0 :: () -> #pass1{}).
 
75
-spec pass1_init() -> #pass1{}.
76
76
pass1_init() ->
77
77
  #pass1{prevSdi=(-1), preS=[], labelMap=gb_trees:empty()}.
78
78
 
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}.
85
85
 
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{}) ->
 
87
        #pass1{}.
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]}.
92
92
 
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}.
96
96
 
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{}]) ->
 
98
        tuple().
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,
107
107
 
108
108
%%% Pass2.
109
109
 
110
 
-spec(pass2/1 :: (#pass1{}) -> {gb_tree(), non_neg_integer()}).
 
110
-spec pass2(#pass1{}) -> {gb_tree(), non_neg_integer()}.
111
111
pass2(Pass1) ->
112
112
  {N,SDIS,LabelMap} = pass1_finalise(Pass1),
113
113
  LONG = mk_long(N),
125
125
%%% Implementation notes:
126
126
%%% - LONG is an integer array indexed from 0 to N-1.
127
127
 
128
 
-spec(mk_long/1 :: (non_neg_integer()) -> hipe_array()).
 
128
-spec mk_long(non_neg_integer()) -> hipe_array().
129
129
mk_long(N) ->
130
130
  mk_array_of_zeros(N).
131
131
 
156
156
%%%   compute PARENTS[j] from the SDI vector when needed. This
157
157
%%%   reduces memory overheads, and may reduce time overheads too.
158
158
 
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)).
162
162
 
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;
167
167
     true ->
192
192
%%% - The result is the updated LONG array. Afterwards, S, SPAN,
193
193
%%%   and PARENTS are no longer useful.
194
194
 
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).
200
200
 
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;
205
205
     true ->
208
208
      initWKL(SdiNr-1, SDIS, SPAN, WKL2)
209
209
  end.
210
210
 
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).
217
217
 
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)
231
230
  end.
232
231
 
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, []).
237
236
 
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),
251
250
    end,
252
251
  parentsOfChild(SdiNr-1, SDIS, Child, NewPS).
253
252
 
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).
261
260
 
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)
275
274
  end.
276
275
 
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
281
280
    true -> WKL;
282
281
    false -> [SdiNr|WKL]
283
282
  end.
284
283
 
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.
288
287
 
289
 
-spec(sdiLongIncr/1 :: (#sdi_data{}) -> byte()).
 
288
-spec sdiLongIncr(#sdi_data{}) -> byte().
290
289
sdiLongIncr(#sdi_data{si=#sdi_info{incr=Incr}}) -> Incr.
291
290
 
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.
302
301
 
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)).
307
306
 
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};
313
311
     true ->
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].
328
326
 
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()).
332
330
 
333
 
-type(label_pair() :: {label(), #label_data{}}).
 
331
-type label_pair() :: {label(), #label_data{}}.
334
332
 
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.
348
346
 
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).
351
349
 
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.
357
355
 
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).
360
358
 
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).
363
361
 
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).