1%% -*- erlang-indent-level: 2 -*-
2%%
3%% Licensed under the Apache License, Version 2.0 (the "License");
4%% you may not use this file except in compliance with the License.
5%% You may obtain a copy of the License at
6%%
7%%     http://www.apache.org/licenses/LICENSE-2.0
8%%
9%% Unless required by applicable law or agreed to in writing, software
10%% distributed under the License is distributed on an "AS IS" BASIS,
11%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12%% See the License for the specific language governing permissions and
13%% limitations under the License.
14%%
15%% ===========================================================================
16%% Copyright (c) 2002 by Niklas Andersson, Andreas Lundin, and Erik Johansson.
17%% ===========================================================================
18%%  Module   :	hipe_spillmin_scan
19%%  Purpose  :  Optimizes the number of stack slots used by using a
20%%              "linear-scan algorithm" to allocate stack slots.
21%%  Notes    :  * This is a simplified implementation of
22%%                "Linear Scan Register Allocation" by
23%%                Massimiliano Poletto & Vivek Sarkar described in
24%%                ACM TOPLAS Vol 21, No 5, September 1999.
25%%
26%%              * This implementation is target-independent and
27%%                requires a target specific interface module
28%%                as argument.
29%%
30%%              * Based on the hipe_ls_regalloc module by Erik Johansson
31%%
32%%  History  :  * 2002-04-01, NA & AL: Created
33%%              * 2002-10-08, Happi: Cleanup and speedup
34%% ============================================================================
35%% Exported functions (short description):
36%%   stackalloc(CFG, StackSlots, SpillIndex, Options, Target, TempMap) ->
37%%                    {Coloring, NumberOfSpills}
38%%    Takes a CFG and the TempMap from register allocation and returns
39%%    a coloring of stack slots.
40%%    StackSlots should be a list of used stack slots, usually empty at
41%%    first call to function.
42%%    SpillIndex is the the first position we will spill to, usually 0.
43%%    TempMap is the TempMap from the register allocation
44%%
45%%    The Coloring will be in the form of the "allocation datastructure"
46%%    described below, that is, a list of tuples on the form
47%%      {Name, {spill, SpillIndex}}
48%%    The NumberOfSpills is either 0 indicating no spill or the
49%%    SpillIndex of the last spilled register.
50%%
51%%  mapmerge
52%%
53%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54
55-module(hipe_spillmin_scan).
56
57-export([stackalloc/8]).
58
59%%-define(DEBUG, 1).
60-define(HIPE_INSTRUMENT_COMPILER, true).
61
62%%----------------------------------------------------------------------------
63
64-include("../main/hipe.hrl").
65-include("../flow/cfg.hrl").
66
67-type target_context() :: any().
68
69%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
70%%
71%% stackalloc(CFG, StackSlots,  SpillIndex, Options, Target, TempMap)
72%%   Calculates an allocation of stack slots using a linear_scan algorithm.
73%%   There are three steps in the algorithm:
74%%    1. Calculate live-ranges for all spilled temporaries.
75%%    2. Calculate live-intervals for each temporary.
76%%       The live interval consists of a start position and a end position
77%%       these are the first definition and last use of the temporary
78%%       given as instruction numbers in a breadth-first traversal of the
79%%       control-flow-graph.
80%%    3. Do a linear scan allocation over the live intervals.
81%%
82%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
83
84-spec stackalloc(#cfg{}, _, [_], non_neg_integer(),
85		 comp_options(), module(), target_context(), hipe_temp_map()) ->
86                                {hipe_spill_map(), non_neg_integer()}.
87
88stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, TargetMod,
89	   TargetContext, TempMap) ->
90  Target = {TargetMod, TargetContext},
91  ?debug_msg("LinearScan: ~w\n", [erlang:statistics(runtime)]),
92  USIntervals = calculate_intervals(CFG, Liveness, Options,
93				    Target, TempMap),
94  %% ?debug_msg("intervals (done) ~w\n", [erlang:statistics(runtime)]),
95  Intervals = sort_on_start(USIntervals),
96  ?debug_msg("sort intervals (done) ~w\n", [erlang:statistics(runtime)]),
97  ?debug_msg("Intervals ~w\n", [Intervals]),
98  ?debug_msg("No intervals: ~w\n", [length(Intervals)]),
99  ?debug_msg("count intervals (done) ~w\n", [erlang:statistics(runtime)]),
100  Allocation = allocate(Intervals, StackSlots, SpillIndex, Target),
101  ?debug_msg("allocation (done) ~w\n", [erlang:statistics(runtime)]),
102  Allocation.
103
104
105%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
106%%                                                                    %%
107%%        Step 2: Calculate live-intervals for each temporary.        %%
108%%                                                                    %%
109%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
110
111%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
112%% calculate_intervals(CFG, Liveness, Options, Target, TempMap)
113%%  CFG: The Control-Flow Graph.
114%%  Liveness: A map of live-in and live-out sets for each Basic-Block.
115%%  TempMap: The TempMap from the register allocation
116%%
117%%  This function will only consider the intervals of the temporaries
118%%  that have been spilled during register allocation, and will ignore
119%%  all other.
120%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
121calculate_intervals(CFG, Liveness, _Options, Target, TempMap) ->
122  Interval = empty_interval(number_of_temporaries(CFG, Target)),
123  Worklist = reverse_postorder(CFG, Target),
124  intervals(Worklist, Interval, 1, CFG, Liveness, Target, TempMap).
125
126%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
127%% intervals(WorkList, Intervals, InstructionNr,
128%%           CFG, Liveness, Target, TempMap)
129%%  WorkList: List of BB-names to handle.
130%%  Intervals: Intervals seen so far (sorted on register names).
131%%  InstructionNr: The number of examined instructions.
132%%  CFG: The Control-Flow Graph.
133%%  Liveness: A map of live-in and live-out sets for each Basic-Block.
134%%  Target: The backend for which we generate native code.
135%%  TempMap: The TempMap from the register allocation
136%%
137%%  This function will only consider the intervals of the temporaries
138%%  that have been spilled during register allocation, and will ignore
139%%  all other.
140%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
141intervals([L|ToDO], Intervals, InstructionNr, CFG, Liveness, Target,
142	  TempMap) ->
143  ?debug_msg("Block ~w\n", [L]),
144  %% Add all variables that are live at the entry of this block
145  %% to the interval data structure.
146
147  %% Only consider spilled temporaries in LiveIn
148  LiveIn = [X || X <- livein(Liveness, L, Target),
149		 hipe_temp_map:is_spilled(X, TempMap)],
150  Intervals2 = add_def_point(LiveIn, InstructionNr, Intervals),
151
152  %% Only consider spilled temporaries in LiveOut
153  LiveOut = [X2 || X2 <- liveout(Liveness, L, Target),
154		   hipe_temp_map:is_spilled(X2, TempMap)],
155  ?debug_msg("In ~w -> Out ~w\n", [LiveIn, LiveOut]),
156
157  %% Traverse this block instruction by instruction and add all
158  %% uses and defines to the intervals.
159  Code = hipe_bb:code(bb(CFG, L, Target)),
160  {Intervals3, NewINr} = traverse_block(Code, InstructionNr+1,
161					Intervals2, Target, TempMap),
162
163  %% Add end points for the temporaries that are in the live-out set.
164  Intervals4 = add_use_point(LiveOut, NewINr+1, Intervals3),
165
166  intervals(ToDO, Intervals4, NewINr+1, CFG, Liveness, Target, TempMap);
167intervals([], Intervals, _, _, _, _, _) ->
168  %% Return the calculated intervals
169  interval_to_list(Intervals).
170  %% Intervals.
171
172%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
173%% traverse_block(Code, InstructionNo, Intervals, Unchanged)
174%%  Examine each instruction in the Code:
175%%   For each temporary T used or defined by instruction number N:
176%%    extend the interval of T to include N.
177%%  TempMap: The TempMap from the register allocation
178%%
179%%  This function will only consider the the instruction that have temporaries
180%%  that have been spilled during register allocation, and will ignore
181%%  all other.
182%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
183
184traverse_block([Instruction|Is], InstrNo, Intervals, Target, TempMap) ->
185  %% Get used temps.
186  %% Only consider spilled temporaries in the Use set.
187  UsesSet = [X || X <- uses(Instruction, Target),
188		  hipe_temp_map:is_spilled(X, TempMap)],
189  %% Get defined temps.
190  %% Only consider spilled temporaries in the Def set.
191  DefsSet = [X2 || X2 <- defines(Instruction, Target),
192		   hipe_temp_map:is_spilled(X2, TempMap)],
193  %% Only consider those temps that starts or ends their lifetime
194  %% within the basic block (that is remove all Unchanged temps).
195  Intervals1 = add_def_point( DefsSet, InstrNo, Intervals),
196  %% Extend the intervals for these temporaries to include InstrNo.
197  Intervals2 = add_use_point(UsesSet, InstrNo, Intervals1),
198  %% Handle the next instruction.
199  traverse_block(Is, InstrNo+1, Intervals2, Target, TempMap);
200traverse_block([], InstrNo, Intervals, _, _) ->
201  %% Return the new intervals and the number of the next instruction.
202  {Intervals,InstrNo}.
203
204
205%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
206%%                                                                    %%
207%%    Step 3. Do a linear scan allocation over the live intervals.    %%
208%%                                                                    %%
209%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
210
211%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
212%%
213%% allocate(Intervals, PhysicalRegisters, Target)
214%%
215%% This function performs the linear scan algorithm.
216%%  Intervals contains the start and stop position of each spilled temporary,
217%%            sorted on increasing startpositions
218%%  StackSlots is a list of available Stack slots to use. If they run out a
219%%  new stack slot is allocated from an (in theory) infinite domain.
220%%
221%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
222allocate(Intervals, StackSlots, SpillIndex, Target) ->
223  AllocatedSlots = empty_allocation(),
224  allocate(Intervals, StackSlots, [], AllocatedSlots, SpillIndex, Target).
225
226%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
227%% allocate(Intervals, Free, Active, Allocated, SpillIndex, Target)
228%%  Iterates on each temporary interval.
229%%   Intervals: The list of temporary intervals.
230%%   Free: Currently available stack slots.
231%%   Active: Currently used stack slots (sorted on increasing
232%%            interval enpoints)
233%%   Allocated: The mapping of register names to spill positions.
234%%   SpillIndex: The number of spilled registers.
235%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
236allocate([TempInt|TIS], Free, Active, Alloc, SpillIndex,  Target) ->
237  %% Remove from the active list those temporaries whose interval
238  %% ends before the start of the current interval.
239  {NewActive, NewFree} =
240    expire_old_intervals(Active, startpoint(TempInt), Free, Target),
241  %% Get the name of the temp in the current interval.
242  Temp = reg(TempInt),
243  case NewFree of
244    [] ->
245      %% There are no free spill slots, so we allocate a new one
246      NewSpillIndex = SpillIndex+1,
247      NewAlloc = spillalloc(Temp, SpillIndex, Alloc),
248      NewActive2 = add_active(endpoint(TempInt), SpillIndex, NewActive),
249      allocate(TIS, NewFree, NewActive2, NewAlloc, NewSpillIndex, Target);
250    [FreeSpillslot | Spillslots] ->
251      %% The spill slot FreeSpillSlot is available, let's use it.
252      allocate(TIS, Spillslots,
253	       add_active(endpoint(TempInt), FreeSpillslot, NewActive),
254	       spillalloc(Temp, FreeSpillslot, Alloc),
255	       SpillIndex, Target)
256  end;
257allocate([], _, _, Alloc, SpillIndex, _) ->
258  %% No more register intervals to handle;
259  %% return the result sorted on regnames.
260  {lists:sort(Alloc), SpillIndex}.
261
262
263%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
264%%
265%% expire_old_intervals(ActiveTemps, CurrentPos, FreeRegisters)
266%%   Remove all temporaries that have live-ranges that ends before the
267%%   current position from the active list and put them into the free
268%%   list instead.
269%%
270%% ---------------------------------------------------------------------
271expire_old_intervals([Act|Acts] = AllActives, CurrentPos, Free, Target) ->
272  %% Does the live-range of the first active register end before
273  %% the current position?
274
275  %% We expand multimove before regalloc, ignore the next 2 lines.
276  %%  %% We don't free registers that end at the current position,
277  %%  %% since a multimove can decide to do the moves in another order...
278  case active_endpoint(Act) =< CurrentPos of
279    true -> %% Yes -> Then we can free that register.
280      Spillslot = active_spillslot(Act),
281      %% Add the spillslot to the free pool.
282      NewFree = [Spillslot|Free],
283      %% Here we could try appending the register to get a more
284      %% widespread use of registers.
285      %% Free ++ [active_spillslot(Act)]);
286      expire_old_intervals(Acts, CurrentPos, NewFree, Target);
287    false ->
288      %% No -> Then we cannot free any more temporaries.
289      %%       (Since they are sorted on endpoints...)
290      {AllActives, Free}
291  end;
292expire_old_intervals([], _, Free, _) ->
293  {[], Free}.
294
295%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
296%%                                                                    %%
297%%                   D A T A   S T R U C T U R E S                    %%
298%%                                &                                   %%
299%%               A U X I L I A R Y   F U N C T I O N S                %%
300%%                                                                    %%
301%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
302
303
304%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
305%%
306%% The "allocation datastructure"
307%%
308%% This is an order list of register names paired with their allocations.
309%%  {Name, Allocation}
310%% Since we are only dealing with spills, the allocation will look like:
311%%  {spill, SpillIndex}
312%%
313%% ---------------------------------------------------------------------
314
315empty_allocation() -> [].
316
317spillalloc(Name, N, Allocation) -> [{Name,{spill,N}}|Allocation].
318
319%% spillalloc(Name,N,[{Name,_}|A]) ->
320%%   ?debug_msg("Spilled ~w\n",[Name]),
321%%   [{Name,{spill,N}}|A];
322%% spillalloc(Name,N,[{Name2,Binding}|Bindings]) when Name > Name2 ->
323%%   [{Name2,Binding}|spillalloc(Name,N,Bindings)];
324%% spillalloc(Name,N,Bindings) ->
325%%   [{Name,{spill,N}}|Bindings].
326
327%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
328%%
329%%  The active datastructure.
330%%   Keeps tracks of currently active (allocated) spill slots.
331%%   It is sorted on end points in the intervals
332%%
333%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
334
335add_active(Endpoint, SpillSlot, [A1={P1,_}|Active]) when P1 < Endpoint ->
336  [A1|add_active(Endpoint, SpillSlot, Active)];
337add_active(Endpoint, SpillSlot, Active) ->
338  [{Endpoint, SpillSlot}|Active].
339
340active_spillslot({_,SpillSlot}) ->
341  SpillSlot.
342
343active_endpoint({EndPoint,_}) ->
344  EndPoint.
345
346%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
347%% The Interval data structure.
348%%
349%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
350
351%% mk_interval(Name, Start, End) ->
352%%   {Name, Start, End}.
353
354endpoint({_R,_S,Endpoint}) ->
355  Endpoint.
356
357startpoint({_R,Startpoint,_E}) ->
358  Startpoint.
359
360reg({RegName,_S,_E}) ->
361  RegName.
362
363%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
364%% The Intervals data structure.
365
366sort_on_start(I) ->
367 lists:keysort(2, I).
368
369-ifdef(gb_intervals).
370empty_interval(_) ->
371  gb_trees:empty().
372
373interval_to_list(Intervals) ->
374  lists:flatten(
375    lists:map(
376      fun({T, I}) when is_list(I) ->
377	  lists:map(
378	    fun ({none, End}) ->
379		{T,End,End};
380		({Beg, none}) ->
381		{T,Beg, Beg}
382	    end,
383	    I);
384	 ({T,{B,E}}) -> {T, B, E}
385      end,
386      gb_trees:to_list(Intervals))).
387
388add_use_point([Temp|Temps], Pos, Intervals) ->
389  %% Extend the old interval...
390  NewInterval =
391    case gb_trees:lookup(Temp, Intervals) of
392      %% This temp has an old interval...
393      {value, Value} ->
394	%% ... extend it.
395	extend_interval(Pos, Value);
396      %% This is the first time we see this temp...
397      none ->
398	%% ... create a new interval
399	{Pos, Pos}
400    end,
401  %% Add or update the extended interval.
402  Intervals2 = gb_trees:enter(Temp, NewInterval, Intervals),
403  %% Add the rest of the temporaries.
404  add_use_point(Temps, Pos, Intervals2);
405add_use_point([], _, I) ->
406  %% No more to add return the interval.
407  I.
408
409add_def_point([Temp|Temps], Pos, Intervals) ->
410  %% Extend the old interval...
411  NewInterval =
412    case gb_trees:lookup(Temp, Intervals) of
413      %% This temp has an old interval...
414      {value, Value} ->
415	%% ... extend it.
416	extend_interval(Pos, Value);
417      %% This is the first time we see this temp...
418      none ->
419	%% ... create a new interval
420	{Pos, Pos}
421    end,
422  %% Add or update the extended interval.
423  Intervals2 = gb_trees:enter(Temp, NewInterval, Intervals),
424  %% Add the rest of the temporaries.
425  add_def_point(Temps, Pos, Intervals2);
426add_def_point([], _, I) ->
427  %% No more to add return the interval.
428  I.
429
430extend_interval(Pos, {Beginning, End}) ->
431  %% If this position occurs before the beginning of the interval,
432  %% then extend the beginning to this position.
433  NewBeginning = erlang:min(Pos, Beginning),
434  %% If this position occurs after the end of the interval, then
435  %% extend the end to this position.
436  NewEnd = erlang:max(Pos, End),
437  {NewBeginning, NewEnd}.
438
439extend_def_interval(Pos, {Beginning, End}) ->
440  %% If this position occurs before the beginning of the interval,
441  %% then extend the beginning to this position.
442  NewBeginning = erlang:min(Pos, Beginning),
443  %% If this position occurs after the end of the interval, then
444  %% extend the end to this position.
445  NewEnd = erlang:max(Pos, End),
446  {NewBeginning, NewEnd};
447extend_def_interval(Pos, [{Beginning, none}|More]) ->
448  [{Pos,none}, {Beginning, none}|More];
449extend_def_interval(Pos, Intervals) ->
450  {Pos, Pos}.
451
452-else. %% ifdef gb_intervals
453
454empty_interval(N) ->
455  hipe_vectors:new(N, none).
456
457interval_to_list(Intervals) ->
458  add_indices(hipe_vectors:vector_to_list(Intervals), 0).
459
460add_indices([{B, E}|Xs], N) ->
461  [{N, B, E}|add_indices(Xs, N+1)];
462add_indices([List|Xs], N) when is_list(List) ->
463  flatten(List, N, Xs);
464add_indices([none|Xs], N) ->
465  add_indices(Xs, N+1);
466add_indices([], _N) -> [].
467
468flatten([{none, End}|Rest], N, More) ->
469  [{N,End,End} | flatten(Rest, N, More)];
470flatten([{Beg, none}|Rest], N ,More) ->
471  [{N,Beg,Beg} | flatten(Rest, N, More)];
472flatten([], N, More) ->
473  add_indices(More, N+1).
474
475add_use_point([Temp|Temps], Pos, Intervals) ->
476  %% Extend the old interval...
477  NewInterval =
478    case hipe_vectors:get(Intervals, Temp) of
479      %% This is the first time we see this temp...
480      none ->
481	%% ... create a new interval
482	{Pos, Pos};
483      %% This temp has an old interval...
484      Value ->
485	%% ... extend it.
486	extend_interval(Pos, Value)
487    end,
488  %% Add or update the extended interval.
489  Intervals2 = hipe_vectors:set(Intervals, Temp, NewInterval),
490  %% Add the rest of the temporaries.
491  add_use_point(Temps, Pos, Intervals2);
492add_use_point([], _, I) ->
493  %% No more to add return the interval.
494  I.
495
496add_def_point([Temp|Temps], Pos, Intervals) ->
497  %% Extend the old interval...
498  NewInterval =
499    case hipe_vectors:get(Intervals, Temp) of
500      %% This is the first time we see this temp...
501      none ->
502	%% ... create a new interval
503	{Pos, Pos};
504      %% This temp has an old interval...
505      Value ->
506	%% ... extend it.
507	extend_interval(Pos, Value)
508    end,
509  %% Add or update the extended interval.
510  Intervals2 = hipe_vectors:set(Intervals, Temp, NewInterval),
511  %% Add the rest of the temporaries.
512  add_def_point(Temps, Pos, Intervals2);
513add_def_point([], _, I) ->
514  %% No more to add return the interval.
515  I.
516
517extend_interval(Pos, {Beginning, End})
518  when is_integer(Beginning), is_integer(End) ->
519  %% If this position occurs before the beginning of the interval,
520  %% then extend the beginning to this position.
521  NewBeginning = erlang:min(Pos, Beginning),
522  %% If this position occurs after the end of the interval, then
523  %% extend the end to this position.
524  NewEnd = erlang:max(Pos, End),
525  {NewBeginning, NewEnd}.
526
527-endif. %% gb_intervals
528
529
530%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
531%%
532%% Interface to external functions.
533%%
534%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
535
536bb(CFG, L, {TgtMod,TgtCtx}) ->
537  TgtMod:bb(CFG, L, TgtCtx).
538
539livein(Liveness, L, Target={TgtMod,TgtCtx}) ->
540  regnames(TgtMod:livein(Liveness, L, TgtCtx), Target).
541
542liveout(Liveness, L, Target={TgtMod,TgtCtx}) ->
543  regnames(TgtMod:liveout(Liveness, L, TgtCtx), Target).
544
545number_of_temporaries(CFG, {TgtMod,TgtCtx}) ->
546  TgtMod:number_of_temporaries(CFG, TgtCtx).
547
548uses(I, Target={TgtMod,TgtCtx}) ->
549  regnames(TgtMod:uses(I,TgtCtx), Target).
550
551defines(I, Target={TgtMod,TgtCtx}) ->
552  regnames(TgtMod:defines(I,TgtCtx), Target).
553
554regnames(Regs, {TgtMod,TgtCtx}) ->
555  [TgtMod:reg_nr(X,TgtCtx) || X <- Regs].
556
557reverse_postorder(CFG, {TgtMod,TgtCtx}) ->
558  TgtMod:reverse_postorder(CFG, TgtCtx).
559