diff options
Diffstat (limited to 'lib/hipe/regalloc/hipe_reg_worklists.erl')
| -rw-r--r-- | lib/hipe/regalloc/hipe_reg_worklists.erl | 360 |
1 files changed, 360 insertions, 0 deletions
diff --git a/lib/hipe/regalloc/hipe_reg_worklists.erl b/lib/hipe/regalloc/hipe_reg_worklists.erl new file mode 100644 index 0000000000..67a5788c7c --- /dev/null +++ b/lib/hipe/regalloc/hipe_reg_worklists.erl @@ -0,0 +1,360 @@ +%%% -*- erlang-indent-level: 2 -*- +%%% +%%% %CopyrightBegin% +%%% +%%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%%% +%%% The contents of this file are subject to the Erlang Public License, +%%% Version 1.1, (the "License"); you may not use this file except in +%%% compliance with the License. You should have received a copy of the +%%% Erlang Public License along with this software. If not, it can be +%%% retrieved online at http://www.erlang.org/. +%%% +%%% Software distributed under the License is distributed on an "AS IS" +%%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%%% the License for the specific language governing rights and limitations +%%% under the License. +%%% +%%% %CopyrightEnd% +%%% +%%%---------------------------------------------------------------------- +%%% File : hipe_reg_worklists.erl +%%% Author : Andreas Wallin <[email protected]> +%%% Purpose : Represents sets of nodes/temporaries that we are +%%% working on, such as simplify and spill sets. +%%% Created : 3 Feb 2000 by Andreas Wallin <[email protected]> +%%% Modified: Spring 2005 by NilsOla Linnermark <[email protected]> +%%% to suit the optimistic coalesching allocator +%%%---------------------------------------------------------------------- + +-module(hipe_reg_worklists). +-author(['Andreas Wallin', 'Thorild Sel�n']). +-export([new/5, % only used by optimistic allocator + new/6, + simplify/1, + spill/1, + freeze/1, + stack/1, + add_simplify/2, + add_freeze/2, + add_coalesced/2, + add_coalesced/3, % only used by optimistic allocator + add_spill/2, + push_stack/3, + remove_simplify/2, + remove_spill/2, + remove_freeze/2, + is_empty_simplify/1, + is_empty_spill/1, + is_empty_freeze/1, + member_freeze/2, + member_coalesced_to/2, % only used by optimistic allocator + member_stack_or_coalesced/2, + non_stacked_or_coalesced_nodes/2, + transfer_freeze_simplify/2, + transfer_freeze_spill/2 + ]). +-ifdef(DEBUG_PRINTOUTS). +-export([print_memberships/1]). +-endif. + +-record(worklists, + {simplify, % Low-degree nodes (if coalescing non move-related) + stack, % Stack of removed low-degree nodes, with adjacency lists + membership, % Mapping from temp to which set it is in + coalesced_to, % if the node is coalesced to (only used by optimistic allocator) + spill, % Significant-degree nodes + freeze % Low-degree move-related nodes + }). + +%%-ifndef(DEBUG). +%%-define(DEBUG,true). +%%-endif. +-include("../main/hipe.hrl"). + +%%%---------------------------------------------------------------------- +%% Function: new +%% +%% Description: Constructor for worklists structure +%% +%% Parameters: +%% IG -- Interference graph +%% Target -- Target module name +%% CFG -- Target-specific CFG +%% Move_sets -- Move information +%% K -- Number of registers +%% +%% Returns: +%% A new worklists data structure +%% +%%%---------------------------------------------------------------------- + +new(IG, Target, CFG, K, No_temporaries) -> % only used by optimistic allocator + CoalescedTo = hipe_bifs:array(No_temporaries, 'none'), + init(initial(Target, CFG), K, IG, empty(No_temporaries, CoalescedTo)). + +new(IG, Target, CFG, Move_sets, K, No_temporaries) -> + init(initial(Target, CFG), K, IG, Move_sets, empty(No_temporaries, [])). + +initial(Target, CFG) -> + {Min_temporary, Max_temporary} = Target:var_range(CFG), + NonAlloc = Target:non_alloc(CFG), + non_precoloured(Target, Min_temporary, Max_temporary, []) + -- [Target:reg_nr(X) || X <- NonAlloc]. + +non_precoloured(Target, Current, Max_temporary, Initial) -> + if Current > Max_temporary -> + Initial; + true -> + NewInitial = + case Target:is_precoloured(Current) of + true -> Initial; + false -> [Current|Initial] + end, + non_precoloured(Target, Current+1, Max_temporary, NewInitial) + end. + +%% construct an empty initialized worklists data structure +empty(No_temporaries, CoalescedTo) -> + #worklists{ + membership = hipe_bifs:array(No_temporaries, 'none'), + coalesced_to = CoalescedTo, % only used by optimistic allocator + simplify = ordsets:new(), + stack = [], + spill = ordsets:new(), + freeze = ordsets:new() + }. + +%% Selectors for worklists record + +simplify(Worklists) -> Worklists#worklists.simplify. +spill(Worklists) -> Worklists#worklists.spill. +freeze(Worklists) -> Worklists#worklists.freeze. +stack(Worklists) -> Worklists#worklists.stack. + +%% Updating worklists records + +set_simplify(Simplify, Worklists) -> + Worklists#worklists{simplify = Simplify}. +set_spill(Spill, Worklists) -> + Worklists#worklists{spill = Spill}. +set_freeze(Freeze, Worklists) -> + Worklists#worklists{freeze = Freeze}. + + +%%---------------------------------------------------------------------- +%% Function: init +%% +%% Description: Initializes worklists +%% +%% Parameters: +%% Initials -- Not precoloured temporaries +%% K -- Number of registers +%% IG -- Interference graph +%% Move_sets -- Move information +%% Worklists -- (Empty) worklists structure +%% +%% Returns: +%% Initialized worklists structure +%% +%%---------------------------------------------------------------------- + +init([], _, _, Worklists) -> Worklists; +init([Initial|Initials], K, IG, Worklists) -> + case hipe_ig:is_trivially_colourable(Initial, K, IG) of + false -> + New_worklists = add_spill(Initial, Worklists), + init(Initials, K, IG, New_worklists); + _ -> + New_worklists = add_simplify(Initial, Worklists), + init(Initials, K, IG, New_worklists) + end. + +init([], _, _, _, Worklists) -> Worklists; +init([Initial|Initials], K, IG, Move_sets, Worklists) -> + case hipe_ig:is_trivially_colourable(Initial, K, IG) of + false -> + New_worklists = add_spill(Initial, Worklists), + init(Initials, K, IG, Move_sets, New_worklists); + _ -> + case hipe_moves:move_related(Initial, Move_sets) of + true -> + New_worklists = add_freeze(Initial, Worklists), + init(Initials, K, IG, Move_sets, New_worklists); + _ -> + New_worklists = add_simplify(Initial, Worklists), + init(Initials, K, IG, Move_sets, New_worklists) + end + end. + +%%%---------------------------------------------------------------------- +%% Function: is_empty +%% +%% Description: Tests if the selected worklist if empty or not. +%% +%% Parameters: +%% Worklists -- A worklists data structure +%% +%% Returns: +%% true -- If the worklist was empty +%% false -- otherwise +%% +%%%---------------------------------------------------------------------- + +is_empty_simplify(Worklists) -> + simplify(Worklists) =:= []. + +is_empty_spill(Worklists) -> + spill(Worklists) =:= []. + +is_empty_freeze(Worklists) -> + freeze(Worklists) =:= []. + +%%%---------------------------------------------------------------------- +%% Function: add +%% +%% Description: Adds one element to one of the worklists. +%% +%% Parameters: +%% Element -- An element you want to add to the +%% selected worklist. The element should +%% be a node/temporary. +%% Worklists -- A worklists data structure +%% +%% Returns: +%% An worklists data-structure that have Element in selected +%% worklist. +%% +%%%---------------------------------------------------------------------- +add_coalesced(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'stack_or_coalesced'), + Worklists. + +add_coalesced(From, To, Worklists) -> % only used by optimistic allocator + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, From, 'stack_or_coalesced'), + Coalesced_to = Worklists#worklists.coalesced_to, + hipe_bifs:array_update(Coalesced_to, To, 'coalesced_to'), + Worklists. + +add_simplify(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'simplify'), + Simplify = ordsets:add_element(Element, simplify(Worklists)), + set_simplify(Simplify, Worklists). + +add_spill(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'spill'), + Spill = ordsets:add_element(Element, spill(Worklists)), + set_spill(Spill, Worklists). + +add_freeze(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'freeze'), + Freeze = ordsets:add_element(Element, freeze(Worklists)), + set_freeze(Freeze, Worklists). + +push_stack(Node, AdjList, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Node, 'stack_or_coalesced'), + Stack = Worklists#worklists.stack, + Worklists#worklists{stack = [{Node,AdjList}|Stack]}. + +%%%---------------------------------------------------------------------- +%% Function: remove +%% +%% Description: Removes one element to one of the worklists. +%% +%% Parameters: +%% Element -- An element you want to remove from the +%% selected worklist. The element should +%% be a node/temporary. +%% Worklists -- A worklists data structure +%% +%% Returns: +%% A worklists data-structure that don't have Element in selected +%% worklist. +%% +%%%---------------------------------------------------------------------- +remove_simplify(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'none'), + Simplify = ordsets:del_element(Element, simplify(Worklists)), + set_simplify(Simplify, Worklists). + +remove_spill(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'none'), + Spill = ordsets:del_element(Element, spill(Worklists)), + set_spill(Spill, Worklists). + +remove_freeze(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'none'), + Freeze = ordsets:del_element(Element, freeze(Worklists)), + set_freeze(Freeze, Worklists). + +%%%---------------------------------------------------------------------- +%% Function: transfer +%% +%% Description: Moves element from one worklist to another. +%% +%%%---------------------------------------------------------------------- +transfer_freeze_simplify(Element, Worklists) -> + add_simplify(Element, remove_freeze(Element, Worklists)). + +transfer_freeze_spill(Element, Worklists) -> + add_spill(Element, remove_freeze(Element, Worklists)). + +%%%---------------------------------------------------------------------- +%% Function: member +%% +%% Description: Checks if one element if member of selected worklist. +%% +%% Parameters: +%% Element -- Element you want to know if it's a +%% member of selected worklist. +%% Worklists -- A worklists data structure +%% +%% Returns: +%% true -- if Element is a member of selected worklist +%% false -- Otherwise +%% +%%%---------------------------------------------------------------------- + +member_coalesced_to(Element, Worklists) -> % only used by optimistic allocator + hipe_bifs:array_sub(Worklists#worklists.coalesced_to, Element) =:= 'coalesced_to'. + +member_freeze(Element, Worklists) -> + hipe_bifs:array_sub(Worklists#worklists.membership, Element) =:= 'freeze'. + +member_stack_or_coalesced(Element, Worklists) -> + hipe_bifs:array_sub(Worklists#worklists.membership, Element) =:= 'stack_or_coalesced'. + +non_stacked_or_coalesced_nodes(Nodes, Worklists) -> + Membership = Worklists#worklists.membership, + [Node || Node <- Nodes, + hipe_bifs:array_sub(Membership, Node) =/= 'stack_or_coalesced']. + +%%%---------------------------------------------------------------------- +%% Print functions - only used for debugging + +-ifdef(DEBUG_PRINTOUTS). +print_memberships(Worklists) -> + ?debug_msg("Worklist memeberships:\n", []), + Membership = Worklists#worklists.membership, + NrElems = hipe_bifs:array_length(Membership), + Coalesced_to = Worklists#worklists.coalesced_to, + print_membership(NrElems, Membership, Coalesced_to). + +print_membership(0, _, _) -> + true; +print_membership(Element, Membership, Coalesced_to) -> + NextElement = Element - 1, + ?debug_msg("worklist ~w ~w ~w\n", + [NextElement, hipe_bifs:array_sub(Membership, NextElement), + hipe_bifs:array_sub(Coalesced_to, NextElement)]), + print_membership(NextElement, Membership, Coalesced_to). +-endif. |