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%%% File    : hipe_reg_worklists.erl
17%%% Author  : Andreas Wallin <d96awa@csd.uu.se>
18%%% Purpose : Represents sets of nodes/temporaries that we are
19%%%           working on, such as simplify and spill sets.
20%%% Created : 3 Feb 2000 by Andreas Wallin <d96awa@csd.uu.se>
21%%% Modified: Spring 2005 by NilsOla Linnermark <nilsola@abc.se>
22%%%           to suit the optimistic coalesching allocator
23%%%----------------------------------------------------------------------
24
25-module(hipe_reg_worklists).
26-author(['Andreas Wallin',  'Thorild Selén']).
27-export([new/6,			% only used by optimistic allocator
28	 new/7,
29	 simplify/1,
30	 spill/1,
31	 freeze/1,
32	 stack/1,
33	 add_simplify/2,
34	 add_freeze/2,
35	 add_coalesced/2,
36	 add_coalesced/3,	% only used by optimistic allocator
37	 add_spill/2,
38	 push_stack/3,
39	 remove_simplify/2,
40	 remove_spill/2,
41	 remove_freeze/2,
42	 is_empty_simplify/1,
43	 is_empty_spill/1,
44	 is_empty_freeze/1,
45	 member_freeze/2,
46	 member_coalesced_to/2,	% only used by optimistic allocator
47	 member_stack_or_coalesced/2,
48	 non_stacked_or_coalesced_nodes/2,
49	 transfer_freeze_simplify/2,
50	 transfer_freeze_spill/2
51	]).
52-ifdef(DEBUG_PRINTOUTS).
53-export([print_memberships/1]).
54-endif.
55
56-record(worklists,
57	{simplify,   % Low-degree nodes (if coalescing non move-related)
58	 stack,	     % Stack of removed low-degree nodes, with adjacency lists
59	 membership, % Mapping from temp to which set it is in
60	 coalesced_to,  % if the node is coalesced to (only used by optimistic allocator)
61	 spill,	     % Significant-degree nodes
62	 freeze      % Low-degree move-related nodes
63	}).
64
65%%-ifndef(DEBUG).
66%%-define(DEBUG,true).
67%%-endif.
68-include("../main/hipe.hrl").
69
70%%%----------------------------------------------------------------------
71%% Function:    new
72%%
73%% Description: Constructor for worklists structure
74%%
75%% Parameters:
76%%   IG              -- Interference graph
77%%   Target          -- Target module name
78%%   CFG             -- Target-specific CFG
79%%   Move_sets       -- Move information
80%%   K               -- Number of registers
81%%
82%% Returns:
83%%   A new worklists data structure
84%%
85%%%----------------------------------------------------------------------
86
87%% only used by optimistic allocator
88new(IG, TargetMod, TargetCtx, CFG, K, No_temporaries) ->
89  CoalescedTo = hipe_bifs:array(No_temporaries, 'none'),
90  init(initial(TargetMod, TargetCtx, CFG), K, IG,
91       empty(No_temporaries, CoalescedTo)).
92
93new(IG, TargetMod, TargetCtx, CFG, Move_sets, K, No_temporaries) ->
94  init(initial(TargetMod, TargetCtx, CFG), K, IG, Move_sets,
95       empty(No_temporaries, [])).
96
97initial(TargetMod, TargetCtx, CFG) ->
98  {Min_temporary, Max_temporary} = TargetMod:var_range(CFG, TargetCtx),
99  NonAlloc = TargetMod:non_alloc(CFG, TargetCtx),
100  non_precoloured(TargetMod, TargetCtx, Min_temporary, Max_temporary, [])
101    -- [TargetMod:reg_nr(X, TargetCtx) || X <- NonAlloc].
102
103non_precoloured(TargetMod, TargetCtx, Current, Max_temporary, Initial) ->
104  if Current > Max_temporary ->
105      Initial;
106     true ->
107      NewInitial =
108	case TargetMod:is_precoloured(Current, TargetCtx) of
109	  true -> Initial;
110	  false -> [Current|Initial]
111	end,
112      non_precoloured(TargetMod, TargetCtx, Current+1, Max_temporary, NewInitial)
113  end.
114
115%% construct an empty initialized worklists data structure
116empty(No_temporaries, CoalescedTo) ->
117  #worklists{
118       membership = hipe_bifs:array(No_temporaries, 'none'),
119       coalesced_to = CoalescedTo, % only used by optimistic allocator
120       simplify = ordsets:new(),
121       stack    = [],
122       spill    = ordsets:new(),
123       freeze   = ordsets:new()
124      }.
125
126%% Selectors for worklists record
127
128simplify(Worklists) -> Worklists#worklists.simplify.
129spill(Worklists)    -> Worklists#worklists.spill.
130freeze(Worklists)   -> Worklists#worklists.freeze.
131stack(Worklists)    -> Worklists#worklists.stack.
132
133%% Updating worklists records
134
135set_simplify(Simplify, Worklists) ->
136  Worklists#worklists{simplify = Simplify}.
137set_spill(Spill, Worklists) ->
138  Worklists#worklists{spill = Spill}.
139set_freeze(Freeze, Worklists) ->
140  Worklists#worklists{freeze = Freeze}.
141
142
143%%----------------------------------------------------------------------
144%% Function:    init
145%%
146%% Description: Initializes worklists
147%%
148%% Parameters:
149%%   Initials        -- Not precoloured temporaries
150%%   K               -- Number of registers
151%%   IG              -- Interference graph
152%%   Move_sets       -- Move information
153%%   Worklists       -- (Empty) worklists structure
154%%
155%% Returns:
156%%   Initialized worklists structure
157%%
158%%----------------------------------------------------------------------
159
160init([], _, _, Worklists) -> Worklists;
161init([Initial|Initials], K, IG, Worklists) ->
162    case hipe_ig:is_trivially_colourable(Initial, K, IG) of
163	false ->
164	    New_worklists = add_spill(Initial, Worklists),
165	    init(Initials, K, IG, New_worklists);
166	_ ->
167	    New_worklists = add_simplify(Initial, Worklists),
168	    init(Initials, K, IG, New_worklists)
169    end.
170
171init([], _, _, _, Worklists) -> Worklists;
172init([Initial|Initials], K, IG, Move_sets, Worklists) ->
173    case hipe_ig:is_trivially_colourable(Initial, K, IG) of
174	false ->
175	    New_worklists = add_spill(Initial, Worklists),
176	    init(Initials, K, IG, Move_sets, New_worklists);
177	_ ->
178	    case hipe_moves:move_related(Initial, Move_sets) of
179		true ->
180		    New_worklists = add_freeze(Initial, Worklists),
181		    init(Initials, K, IG, Move_sets, New_worklists);
182		_ ->
183		    New_worklists = add_simplify(Initial, Worklists),
184		    init(Initials, K, IG, Move_sets, New_worklists)
185	    end
186    end.
187
188%%%----------------------------------------------------------------------
189%% Function:    is_empty
190%%
191%% Description: Tests if the selected worklist if empty or not.
192%%
193%% Parameters:
194%%   Worklists                -- A worklists data structure
195%%
196%% Returns:
197%%   true  -- If the worklist was empty
198%%   false -- otherwise
199%%
200%%%----------------------------------------------------------------------
201
202is_empty_simplify(Worklists) ->
203  simplify(Worklists) =:= [].
204
205is_empty_spill(Worklists) ->
206  spill(Worklists) =:= [].
207
208is_empty_freeze(Worklists) ->
209  freeze(Worklists) =:= [].
210
211%%%----------------------------------------------------------------------
212%% Function:    add
213%%
214%% Description: Adds one element to one of the worklists.
215%%
216%% Parameters:
217%%   Element                  -- An element you want to add to the
218%%                                selected worklist. The element should
219%%                                be a node/temporary.
220%%   Worklists                -- A worklists data structure
221%%
222%% Returns:
223%%   An worklists data-structure that have Element in selected
224%%    worklist.
225%%
226%%%----------------------------------------------------------------------
227add_coalesced(Element, Worklists) ->
228  Membership = Worklists#worklists.membership,
229  hipe_bifs:array_update(Membership, Element, 'stack_or_coalesced'),
230  Worklists.
231
232add_coalesced(From, To, Worklists) -> % only used by optimistic allocator
233  Membership = Worklists#worklists.membership,
234  hipe_bifs:array_update(Membership, From, 'stack_or_coalesced'),
235  Coalesced_to = Worklists#worklists.coalesced_to,
236  hipe_bifs:array_update(Coalesced_to, To, 'coalesced_to'),
237  Worklists.
238
239add_simplify(Element, Worklists) ->
240  Membership = Worklists#worklists.membership,
241  hipe_bifs:array_update(Membership, Element, 'simplify'),
242  Simplify = ordsets:add_element(Element, simplify(Worklists)),
243  set_simplify(Simplify, Worklists).
244
245add_spill(Element, Worklists) ->
246  Membership = Worklists#worklists.membership,
247  hipe_bifs:array_update(Membership, Element, 'spill'),
248  Spill = ordsets:add_element(Element, spill(Worklists)),
249  set_spill(Spill, Worklists).
250
251add_freeze(Element, Worklists) ->
252  Membership = Worklists#worklists.membership,
253  hipe_bifs:array_update(Membership, Element, 'freeze'),
254  Freeze = ordsets:add_element(Element, freeze(Worklists)),
255  set_freeze(Freeze, Worklists).
256
257push_stack(Node, AdjList, Worklists) ->
258  Membership = Worklists#worklists.membership,
259  hipe_bifs:array_update(Membership, Node, 'stack_or_coalesced'),
260  Stack = Worklists#worklists.stack,
261  Worklists#worklists{stack = [{Node,AdjList}|Stack]}.
262
263%%%----------------------------------------------------------------------
264%% Function:    remove
265%%
266%% Description: Removes one element to one of the worklists.
267%%
268%% Parameters:
269%%   Element                  -- An element you want to remove from the
270%%                                selected worklist. The element should
271%%                                be a node/temporary.
272%%   Worklists                -- A worklists data structure
273%%
274%% Returns:
275%%   A worklists data-structure that don't have Element in selected
276%%    worklist.
277%%
278%%%----------------------------------------------------------------------
279remove_simplify(Element, Worklists) ->
280  Membership = Worklists#worklists.membership,
281  hipe_bifs:array_update(Membership, Element, 'none'),
282  Simplify = ordsets:del_element(Element, simplify(Worklists)),
283  set_simplify(Simplify, Worklists).
284
285remove_spill(Element, Worklists) ->
286  Membership = Worklists#worklists.membership,
287  hipe_bifs:array_update(Membership, Element, 'none'),
288  Spill = ordsets:del_element(Element, spill(Worklists)),
289  set_spill(Spill, Worklists).
290
291remove_freeze(Element, Worklists) ->
292  Membership = Worklists#worklists.membership,
293  hipe_bifs:array_update(Membership, Element, 'none'),
294  Freeze = ordsets:del_element(Element, freeze(Worklists)),
295  set_freeze(Freeze, Worklists).
296
297%%%----------------------------------------------------------------------
298%% Function:    transfer
299%%
300%% Description: Moves element from one worklist to another.
301%%
302%%%----------------------------------------------------------------------
303transfer_freeze_simplify(Element, Worklists) ->
304  add_simplify(Element, remove_freeze(Element, Worklists)).
305
306transfer_freeze_spill(Element, Worklists) ->
307  add_spill(Element, remove_freeze(Element, Worklists)).
308
309%%%----------------------------------------------------------------------
310%% Function:    member
311%%
312%% Description: Checks if one element if member of selected worklist.
313%%
314%% Parameters:
315%%   Element                  -- Element you want to know if it's a
316%%                                member of selected worklist.
317%%   Worklists                -- A worklists data structure
318%%
319%% Returns:
320%%   true   --  if Element is a member of selected worklist
321%%   false  --  Otherwise
322%%
323%%%----------------------------------------------------------------------
324
325member_coalesced_to(Element, Worklists) -> % only used by optimistic allocator
326  hipe_bifs:array_sub(Worklists#worklists.coalesced_to, Element) =:= 'coalesced_to'.
327
328member_freeze(Element, Worklists) ->
329  hipe_bifs:array_sub(Worklists#worklists.membership, Element) =:= 'freeze'.
330
331member_stack_or_coalesced(Element, Worklists) ->
332  hipe_bifs:array_sub(Worklists#worklists.membership, Element) =:= 'stack_or_coalesced'.
333
334non_stacked_or_coalesced_nodes(Nodes, Worklists) ->
335  Membership = Worklists#worklists.membership,
336  [Node || Node <- Nodes,
337	   hipe_bifs:array_sub(Membership, Node) =/= 'stack_or_coalesced'].
338
339%%%----------------------------------------------------------------------
340%% Print functions - only used for debugging
341
342-ifdef(DEBUG_PRINTOUTS).
343print_memberships(Worklists) ->
344  ?debug_msg("Worklist memeberships:\n", []),
345  Membership = Worklists#worklists.membership,
346  NrElems = hipe_bifs:array_length(Membership),
347  Coalesced_to = Worklists#worklists.coalesced_to,
348  print_membership(NrElems, Membership, Coalesced_to).
349
350print_membership(0, _, _) ->
351  true;
352print_membership(Element, Membership, Coalesced_to) ->
353  NextElement = Element - 1,
354  ?debug_msg("worklist ~w ~w ~w\n",
355	     [NextElement, hipe_bifs:array_sub(Membership, NextElement),
356			   hipe_bifs:array_sub(Coalesced_to, NextElement)]),
357  print_membership(NextElement, Membership, Coalesced_to).
358-endif.
359