diff options
Diffstat (limited to 'lib/hipe/regalloc/hipe_moves.erl')
| -rw-r--r-- | lib/hipe/regalloc/hipe_moves.erl | 165 |
1 files changed, 165 insertions, 0 deletions
diff --git a/lib/hipe/regalloc/hipe_moves.erl b/lib/hipe/regalloc/hipe_moves.erl new file mode 100644 index 0000000000..afec4aa4ce --- /dev/null +++ b/lib/hipe/regalloc/hipe_moves.erl @@ -0,0 +1,165 @@ +%% -*- 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% +%% + +-module(hipe_moves). +-export([new/1, + update_movelist/3, + node_moves/2, + move_related/2, + node_movelist/2, + get_move/2, + is_empty_worklist/1, + worklist_get_and_remove/1, + remove_worklist/2, + remove_active/2, + add_worklist/2, + add_active/2, + member_active/2 + ]). +-ifdef(DEBUG_PRINTOUTS). +-export([print_memberships/1]). +-endif. + +-record(movesets, + {worklist, % Moves enabled for possible coalescing + membership, % Maps move numbers to 'worklist' or 'active' or 'none' + moveinsns, % Maps move numbers to move insns ({Dst,Src}-tuples) + movelist % Mapping from node to list of moves it's associated with + }). + +%%-ifndef(DEBUG). +%%-define(DEBUG,true). +%%-endif. +-include("../main/hipe.hrl"). + +worklist(MoveSets) -> MoveSets#movesets.worklist. +movelist(MoveSets) -> MoveSets#movesets.movelist. + +set_worklist(New_worklist, MoveSets) -> + MoveSets#movesets{worklist = New_worklist}. +set_movelist(New_movelist, MoveSets) -> + MoveSets#movesets{movelist = New_movelist}. + +update_movelist(Node, MoveList, MoveSets) -> + set_movelist(hipe_vectors:set(movelist(MoveSets), Node, MoveList), + MoveSets). + +new(IG) -> + {MoveList,NrMoves,MoveInsns} = hipe_ig:get_moves(IG), + Worklist = case NrMoves of 0 -> []; _ -> lists:seq(0, NrMoves-1) end, + #movesets{worklist = Worklist, + membership = hipe_bifs:array(NrMoves, 'worklist'), + moveinsns = MoveInsns, + movelist = MoveList}. + +remove_worklist(Element, MoveSets) -> + Membership = MoveSets#movesets.membership, + %% check for 'worklist' membership here, if debugging + hipe_bifs:array_update(Membership, Element, 'none'), + %% Implementing this faithfully would require a SET structure, such + %% as an ordset or a gb_set. However, removal of elements not at the + %% head of the structure is a fairly infrequent event (only done by + %% FreezeMoves()), so instead we let the elements remain but mark + %% them as being removed. It is the task of worklist_get_and_remove() + %% to filter out any stale elements. + MoveSets. + +remove_active(Element, MoveSets) -> + Membership = MoveSets#movesets.membership, + %% check for 'active' membership here, if debugging + hipe_bifs:array_update(Membership, Element, 'none'), + MoveSets. + +add_worklist(Element, MoveSets) -> + Membership = MoveSets#movesets.membership, + %% check for 'none' membership here, if debugging + hipe_bifs:array_update(Membership, Element, 'worklist'), + set_worklist([Element | worklist(MoveSets)], MoveSets). + +add_active(Element, MoveSets) -> + Membership = MoveSets#movesets.membership, + %% check for 'none' membership here, if debugging + hipe_bifs:array_update(Membership, Element, 'active'), + MoveSets. + +member_active(Element, MoveSets) -> + hipe_bifs:array_sub(MoveSets#movesets.membership, Element) =:= 'active'. + +is_empty_worklist(MoveSets) -> + %% This is an approximation. See worklist_get_and_remove(). + worklist(MoveSets) =:= []. + +worklist_get_and_remove(MoveSets) -> + worklist_get_and_remove(worklist(MoveSets), MoveSets#movesets.membership, MoveSets). + +worklist_get_and_remove([], _Membership, MoveSets) -> + {[], set_worklist([], MoveSets)}; +worklist_get_and_remove([Move|Worklist], Membership, MoveSets) -> + case hipe_bifs:array_sub(Membership, Move) of + 'worklist' -> + hipe_bifs:array_update(Membership, Move, 'none'), + {Move, set_worklist(Worklist, MoveSets)}; + _ -> + worklist_get_and_remove(Worklist, Membership, MoveSets) + end. + +node_moves(Node, MoveSets) -> + Associated = node_movelist(Node, MoveSets), + Membership = MoveSets#movesets.membership, + %% The ordsets:union() in hipe_coalescing_regalloc:combine() + %% constrains us to return an ordset here. + [X || X <- Associated, hipe_bifs:array_sub(Membership, X) =/= 'none']. + +move_related(Node, MoveSets) -> + %% Same as node_moves(Node, MoveSets) =/= [], but less expensive to compute. + %% XXX: George&Appel'96 hints that this should be maintained as a per-node counter. + move_related2(node_movelist(Node, MoveSets), MoveSets#movesets.membership). + +move_related2([], _Membership) -> false; +move_related2([Move|MoveSets], Membership) -> + case hipe_bifs:array_sub(Membership, Move) of + 'none' -> move_related2(MoveSets, Membership); + _ -> true % 'active' or 'worklist' + end. + +node_movelist(Node, MoveSets) -> + hipe_vectors:get(movelist(MoveSets), Node). + +get_move(Move, MoveSets) -> + element(Move+1, MoveSets#movesets.moveinsns). + +%%---------------------------------------------------------------------- +%% Print functions - only used for debugging + +-ifdef(DEBUG_PRINTOUTS). +print_memberships(MoveSets) -> + ?debug_msg("Move memeberships:\n", []), + Membership = MoveSets#movesets.membership, + NrMoves = hipe_bifs:array_length(Membership), + print_membership(NrMoves, Membership). + +print_membership(0, _) -> + true; +print_membership(Element, Membership) -> + NextElement = Element - 1, + ?debug_msg("move ~w ~w\n", [NextElement, hipe_bifs:array_sub(Membership, NextElement)]), + print_membership(NextElement, Membership). +-endif. + |