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