%% -*- 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.