The R13B03 release.OTP_R13B03

1 files changed, 2043 insertions, 0 deletions

diff --git a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
new file mode 100644
index 0000000000..183ec1994c
--- /dev/null
+++ b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl
@@ -0,0 +1,2043 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2005-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_optimistic_regalloc.erl
+%% Authors : NilsOla Linnermark <[email protected]>
+%%           Petter Holmberg <[email protected]>
+%% Purpose : Play paintball with registers on a target machine.  We win
+%%           if they are all colored.  This is an optimistic coalescing
+%%           register allocator.
+%% Created : Spring 2005
+%%-----------------------------------------------------------------------
+
+-module(hipe_optimistic_regalloc).
+-export([regalloc/5]).
+
+-ifndef(DEBUG).
+%%-define(DEBUG,true).
+-else.
+-ifndef(COMPARE_ITERATED_OPTIMISTIC).
+%% If this macro is turned on you can easily compare 
+%% each intermediate step in the iterated coalescing
+%% register allocator and the optimitsitc coalescing
+%% register allocator. This is useful for debugging -
+%% many small erlang functions should render the same
+%% register allocaton for both allocators.
+-define(COMPARE_ITERATED_OPTIMISTIC, true).
+-endif.
+-endif.
+-include("../main/hipe.hrl").
+-ifdef(DEBUG_PRINTOUTS).
+-define(print_adjacent(IG), hipe_ig:print_adjacent(IG)).
+-define(print_degrees(IG), hipe_ig:print_degrees(IG)).
+-define(print_spill_costs(IG),  hipe_ig:print_spill_costs(IG)).
+-define(mov_print_memberships(MV),  hipe_moves:print_memberships(MV)).
+-define(reg_print_memberships(WL), hipe_reg_worklists:print_memberships(WL)).
+-define(print_alias(A), printAlias(A)).
+-define(print_colors(T,C), printColors(T,C)).
+-else.
+-define(print_adjacent(IG), no_print).
+-define(print_degrees(IG), no_print).
+-define(print_spill_costs(IG), no_print).
+-define(mov_print_memberships(MV), no_print).
+-define(reg_print_memberships(WL), no_print).
+-define(print_alias(A), no_print).
+-define(print_colors(T,C), no_print).
+-endif.
+
+
+%%-----------------------------------------------------------------------
+%% Function:    regalloc
+%%
+%% Description: Creates a K coloring for a function.
+%% Parameters:
+%%   CFG         -- A control flow graph
+%%   SpillIndex  -- Last index of spill variable
+%%   SpillLimit  -- Temporaris with numbers higher than this have
+%%                  infinit spill cost. 
+%%                  Consider changing this to a set.
+%%   Target      -- The module containing the target-specific functions.
+%%
+%% Returns:
+%%   Coloring    -- A coloring for specified CFG
+%%   SpillIndex0 -- A new spill index
+%%-----------------------------------------------------------------------
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
+  ?debug_msg("optimistic ~w\n",[Target]),
+  ?debug_msg("CFG: ~p\n",[CFG]),
+  %% Build interference graph
+  ?debug_msg("Build IG\n",[]),
+  IG_O = hipe_ig:build(CFG, Target),
+  IG = hipe_ig:build(CFG, Target),
+  ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]),
+  ?debug_msg("IG:\n",[]),
+  ?print_adjacent(IG),
+  ?print_degrees(IG),
+  ?print_spill_costs(IG),
+
+  SavedSpillCosts = hipe_ig:spill_costs(IG),
+  SavedAdjList = hipe_ig:adj_list(IG),
+
+  ?debug_msg("Init\n",[]),
+  No_temporaries = Target:number_of_temporaries(CFG),
+  ?debug_msg("Coalescing RA: num_temps = ~p~n", [No_temporaries]),
+  Allocatable = Target:allocatable(),
+  K = length(Allocatable),
+  All_colors = colset_from_list(Allocatable),
+  ?debug_msg("K: ~w~nAll_colors: ~p\n",[K, All_colors]), 
+
+  %% Add registers with their own coloring
+  ?debug_msg("Moves\n",[]),
+  Move_sets_O = hipe_moves:new(IG_O),
+  Move_sets = hipe_moves:new(IG),
+  ?debug_msg("Move_sets:\n ~p\n",[Move_sets]),
+  ?mov_print_memberships(Move_sets),
+
+  ?debug_msg("Build Worklist\n",[]),
+  Worklists_O = hipe_reg_worklists:new(IG_O, Target, CFG, Move_sets_O, K, No_temporaries),
+  ?debug_msg("Worklists:\n ~p\n", [Worklists_O]),
+  ?reg_print_memberships(Worklists_O),
+
+  Worklists = hipe_reg_worklists:new(IG, Target, CFG, K, No_temporaries),
+  ?debug_msg("New Worklists:\n ~p\n", [Worklists]),
+  ?reg_print_memberships(Worklists),
+
+  Alias_O = initAlias(No_temporaries),
+  Alias = initAlias(No_temporaries),
+  ?print_alias(Alias),
+
+  ?debug_msg("Do coloring\n~p~n",[Worklists_O]),
+  {IG0_O, Worklists0_O, Moves0_O, Alias0_O} = 
+    do_coloring(IG_O, Worklists_O, Move_sets_O, Alias_O,
+		K, SpillLimit, Target),
+  ?debug_msg("IG_O after color:\n ~p\n",[IG0_O]),
+  ?print_adjacent(IG0_O),
+  ?print_degrees(IG0_O),
+  ?print_spill_costs(IG0_O),
+  ?debug_msg("Move_sets after color:\n ~p\n",[Moves0_O]),
+  ?mov_print_memberships(Moves0_O),
+  ?debug_msg("Worklists after color:\n ~p\n", [Worklists0_O]),
+  ?reg_print_memberships(Worklists0_O),
+
+  {IG0, Moves0, Alias0, Worklists0} = 
+    do_coalescing(IG, Worklists, Move_sets, Alias, K, Target),
+  ?debug_msg("IG after coalescing:\n",[]),
+  ?print_adjacent(IG0),
+  ?print_degrees(IG0),
+  ?print_spill_costs(IG0),
+  ?debug_msg("Move_sets after coalescing:\n ~p\n",[Moves0]),
+  ?mov_print_memberships(Moves0),
+  ?debug_msg("New Worklists after coalescing:\n ~p\n",
+             [Worklists0]),
+  ?reg_print_memberships(Worklists0),
+
+  {IG1, Worklists1, Moves1, Alias1} = 
+    do_simplify_or_spill(IG0, Worklists0, Moves0, Alias0, 
+                         K, SpillLimit, Target),
+  ?debug_msg("IG after simplify_or_spill:\n",[]),
+  ?print_adjacent(IG1),
+  ?print_degrees(IG1),
+  ?print_spill_costs(IG1),
+  ?debug_msg("Saved spill costs ~p~n", [SavedSpillCosts]),
+  ?debug_msg("Move_sets after simplify_or_spill:\n ~p\n",[Moves1]),
+  ?mov_print_memberships(Moves1),
+  ?debug_msg("New Worklists after simplify_or_spill:\n ~p\n",
+             [Worklists1]),
+  ?reg_print_memberships(Worklists1),
+  ?print_alias(Alias1),
+
+  %% only for testing undoCoalescing and member_coalesced_to
+  %test_undoCoalescing(No_temporaries, Alias1, Worklists1),
+
+  %% only for testing fixAdj
+  %?debug_msg("adj_lists_before_fixAdj ~n~p~n", [hipe_ig:adj_list(IG1)]),
+  %IG2 = test_fixAdj(No_temporaries, SavedAdjList, IG1, Target),
+  %?debug_msg("adj_lists__after_fixAdj ~n~p~n", [hipe_ig:adj_list(IG2)]),
+
+  ?debug_msg("Init node sets\n",[]),
+  Node_sets = hipe_node_sets:new(),
+  %% ?debug_msg("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,Target:non_alloc(CFG)]),
+  ?debug_msg("Default coloring\n",[]),
+  {Color0,Node_sets1} = 
+    defaultColoring(Target:all_precoloured(),
+		    initColor(No_temporaries), Node_sets, Target),
+  ?debug_msg("Color0\n",[]),
+  ?print_colors(No_temporaries, Color0),
+
+  ?debug_msg("----------------------Assign colors _N\n",[]),
+
+  Stack = hipe_reg_worklists:stack(Worklists1), 
+  ?debug_msg("The stack _N ~p~n", [Stack]), 
+  %SortedStack = sort_stack(Stack),
+  %?debug_msg("The stack _N ~p~n", [SortedStack]), 
+
+  %?debug_msg("Nodes _N ~w~n", [Node_sets1]),
+
+  {Color1,Node_sets2,Alias2} =
+    assignColors(Worklists1, Stack, Node_sets1, Color0, 
+        	 No_temporaries, SavedAdjList, SavedSpillCosts, IG1, Alias1, All_colors, Target),
+  ?print_colors(No_temporaries, Color1),
+  ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]),
+
+  ?debug_msg("Build mapping _N ~w\n",[Node_sets2]),
+  Coloring = build_namelist(Node_sets2,SpillIndex,Alias2,Color1),
+  ?debug_msg("Coloring ~p\n",[Coloring]),
+  SortedColoring = { sort_stack(element(1, Coloring)), element(2, Coloring)},
+  ?debug_msg("SortedColoring ~p\n",[SortedColoring]),
+  %%Coloring.
+  ?debug_msg("----------------------Assign colors _O\n",[]),
+  {Color1_O,Node_sets2_O} =
+    assignColors_O(hipe_reg_worklists:stack(Worklists0_O), Node_sets1, Color0, 
+		 Alias0_O, All_colors, Target),
+  ?print_colors(No_temporaries, Color1_O),
+  ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2_O,No_temporaries]),
+
+  ?debug_msg("Build mapping ~w\n",[Node_sets2_O]),
+  Coloring_O = build_namelist_O(Node_sets2_O,SpillIndex,Alias0_O,Color1_O),
+  ?debug_msg("Coloring_O ~p\n",[Coloring_O]),
+  SortedColoring_O = {sort_stack(element(1, Coloring_O)), element(2, Coloring_O)},
+  ?debug_msg("SortedColoring_O ~p\n",[SortedColoring_O]),
+  sanity_compare(SortedColoring_O, SortedColoring),
+  Coloring.
+-else.
+regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
+  ?debug_msg("optimistic ~w\n",[Target]),
+  ?debug_msg("CFG: ~p\n",[CFG]),
+  %% Build interference graph
+  ?debug_msg("Build IG\n",[]),
+  IG = hipe_ig:build(CFG, Target),
+  ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]),
+  ?debug_msg("IG:\n",[]),
+  ?print_adjacent(IG),
+  ?print_degrees(IG),
+  ?print_spill_costs(IG),
+
+  SavedSpillCosts = hipe_ig:spill_costs(IG),
+  SavedAdjList = hipe_ig:adj_list(IG),
+
+  ?debug_msg("Init\n",[]),
+  No_temporaries = Target:number_of_temporaries(CFG),
+  ?debug_msg("Coalescing RA: num_temps = ~p~n", [No_temporaries]),
+  Allocatable = Target:allocatable(),
+  K = length(Allocatable),
+  All_colors = colset_from_list(Allocatable),
+  ?debug_msg("K: ~w~nAll_colors: ~p\n",[K, All_colors]), 
+
+  %% Add registers with their own coloring
+  ?debug_msg("Moves\n",[]),
+  Move_sets = hipe_moves:new(IG),
+  ?debug_msg("Move_sets:\n ~p\n",[Move_sets]),
+  ?mov_print_memberships(Move_sets),
+
+  ?debug_msg("Build Worklist\n",[]),
+
+  Worklists = hipe_reg_worklists:new(IG, Target, CFG, K, No_temporaries),
+  ?debug_msg("New Worklists:\n ~p\n", [Worklists]),
+  ?reg_print_memberships(Worklists),
+
+  Alias = initAlias(No_temporaries),
+  ?print_alias(Alias),
+
+  {IG0, Moves0, Alias0, Worklists0} = 
+    do_coalescing(IG, Worklists, Move_sets, Alias, K, Target),
+  ?debug_msg("IG after coalescing:\n",[]),
+  ?print_adjacent(IG0),
+  ?print_degrees(IG0),
+  ?print_spill_costs(IG0),
+  ?debug_msg("Move_sets after coalescing:\n ~p\n",[Moves0]),
+  ?mov_print_memberships(Moves0),
+  ?debug_msg("New Worklists after coalescing:\n ~p\n",
+             [Worklists0]),
+  ?reg_print_memberships(Worklists0),
+
+  {IG1, Worklists1, _Moves1, Alias1} = 
+    do_simplify_or_spill(IG0, Worklists0, Moves0, Alias0, 
+                         K, SpillLimit, Target),
+  ?debug_msg("IG after simplify_or_spill:\n",[]),
+  ?print_adjacent(IG1),
+  ?print_degrees(IG1),
+  ?print_spill_costs(IG1),
+  ?debug_msg("Saved spill costs ~p~n", [SavedSpillCosts]),
+  ?debug_msg("New Worklists after simplify_or_spill:\n ~p\n",
+             [Worklists1]),
+  ?reg_print_memberships(Worklists1),
+  ?print_alias(Alias1),
+
+  %% only for testing undoCoalescing and member_coalesced_to
+  %test_undoCoalescing(No_temporaries, Alias1, Worklists1),
+
+  %% only for testing fixAdj
+  %?debug_msg("adj_lists_before_fixAdj ~n~p~n", [hipe_ig:adj_list(IG1)]),
+  %IG2 = test_fixAdj(No_temporaries, SavedAdjList, IG1, Target),
+  %?debug_msg("adj_lists__after_fixAdj ~n~p~n", [hipe_ig:adj_list(IG2)]),
+
+  ?debug_msg("Init node sets\n",[]),
+  Node_sets = hipe_node_sets:new(),
+  %% ?debug_msg("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,Target:non_alloc(CFG)]),
+  ?debug_msg("Default coloring\n",[]),
+  {Color0,Node_sets1} = 
+    defaultColoring(Target:all_precoloured(),
+		    initColor(No_temporaries), Node_sets, Target),
+  ?debug_msg("Color0\n",[]),
+  ?print_colors(No_temporaries, Color0),
+
+  ?debug_msg("----------------------Assign colors _N\n",[]),
+
+  Stack = hipe_reg_worklists:stack(Worklists1), 
+  ?debug_msg("The stack _N ~p~n", [Stack]), 
+  %SortedStack = sort_stack(Stack),
+  %?debug_msg("The stack _N ~p~n", [SortedStack]), 
+
+  %?debug_msg("Nodes _N ~w~n", [Node_sets1]),
+
+  {Color1,Node_sets2,Alias2} =
+    assignColors(Worklists1, Stack, Node_sets1, Color0, 
+        	 No_temporaries, SavedAdjList, SavedSpillCosts, IG1, Alias1, All_colors, Target),
+  ?print_colors(No_temporaries, Color1),
+  ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]),
+
+  ?debug_msg("Build mapping _N ~w\n",[Node_sets2]),
+  Coloring = build_namelist(Node_sets2,SpillIndex,Alias2,Color1),
+  ?debug_msg("Coloring ~p\n",[Coloring]),
+  Coloring.
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    do_coloring
+%%
+%% Description: Create a coloring. That is, play paintball.
+%% Parameters:
+%%   IG          --  An interference graph
+%%   Worklists   --  Worklists, that is simplify, spill and freeze
+%%   Moves       --  Moves sets, that is coalesced, constrained 
+%%                   and so on.
+%%   Alias       --  Tells if two temporaries can have their value
+%%                   in the same register.
+%%   K           --  Want to create a K coloring.
+%%   SpillLimit  --  Try not to spill nodes that are above the spill limit.
+%%
+%% Returns:
+%%   IG          --  Updated interference graph
+%%   Worklists   --  Updated Worklists structure
+%%   Moves       --  Updated Moves structure 
+%%   Alias       --  Updates Alias structure
+%%   
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+do_coloring(IG, Worklists, Moves, Alias, K, SpillLimit, Target) ->
+  Simplify = not(hipe_reg_worklists:is_empty_simplify(Worklists)),
+  Coalesce = not(hipe_moves:is_empty_worklist(Moves)),
+  Freeze   = not(hipe_reg_worklists:is_empty_freeze(Worklists)),
+  Spill    = not(hipe_reg_worklists:is_empty_spill(Worklists)),
+  if Simplify =:= true ->
+      {IG0, Worklists0, Moves0} = 
+	simplify_O(hipe_reg_worklists:simplify(Worklists),
+		   IG, 
+		   Worklists, 
+		   Moves, 
+		   K),
+      do_coloring(IG0, Worklists0, Moves0, Alias, K, SpillLimit, Target);
+     Coalesce =:= true ->
+      {Moves0, IG0, Worklists0, Alias0} =
+	coalesce_O(Moves, IG, Worklists, Alias, K, Target),
+      do_coloring(IG0, Worklists0, Moves0, Alias0, K, SpillLimit, Target);
+     Freeze =:= true ->
+      {Worklists0, Moves0} = 
+	freeze(K, Worklists, Moves, IG, Alias),
+      do_coloring(IG, Worklists0, Moves0, Alias, K, SpillLimit, Target);
+     Spill =:= true ->
+      {Worklists0, Moves0} = 
+	selectSpill_O(Worklists, Moves, IG, K, Alias, SpillLimit),
+      do_coloring(IG, Worklists0, Moves0, Alias, K, SpillLimit, Target);
+     true -> % Catchall case
+      {IG, Worklists, Moves, Alias}
+    end.
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    do_coalescing
+%%
+%% Description: Try to coalesce everything (find out later if it was
+%%              possible).
+%% Parameters:
+%%   IG          --  An interference graph
+%%   Moves       --  Moves sets, that is coalesced, constrained 
+%%                   and so on.
+%%   Alias       --  Tells if two temporaries can have their value
+%%                   in the same register.
+%%
+%% Returns:
+%%   IG          --  Updated interference graph
+%%   Moves       --  Updated Moves structure 
+%%   Alias       --  Updates Alias structure
+%%   
+%%----------------------------------------------------------------------
+
+do_coalescing(IG, Worklists, Moves, Alias, K, Target) ->
+  case hipe_moves:is_empty_worklist(Moves) of
+    true ->
+      {IG, Moves, Alias, Worklists};
+    _ ->
+      {Moves0, IG0, Alias0, Worklists0} =
+	coalesce(Moves, IG, Worklists, Alias, K, Target),
+      do_coalescing(IG0, Worklists0, Moves0, Alias0, K, Target)
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    do_simplify_or_spill
+%%
+%% Parameters:
+%%   IG          --  An interference graph
+%%   Worklists   --  Worklists, that is simplify, spill and freeze
+%%   Moves       --  Moves sets, that is coalesced, constrained 
+%%                   and so on.
+%%   Alias       --  Tells if two temporaries can have their value
+%%                   in the same register.
+%%   K           --  Want to create a K coloring.
+%%   SpillLimit  --  Try not to spill nodes that are above the spill limit.
+%%
+%% Returns:
+%%   IG          --  Updated interference graph
+%%   Worklists   --  Updated Worklists structure
+%%   Moves       --  Updated Moves structure 
+%%   Alias       --  Updates Alias structure
+%%   
+%%----------------------------------------------------------------------
+
+do_simplify_or_spill(IG, Worklists, Moves, Alias, K, SpillLimit, Target) ->
+  Simplify = not(hipe_reg_worklists:is_empty_simplify(Worklists)),
+  Spill    = not(hipe_reg_worklists:is_empty_spill(Worklists)),
+  if Simplify =:= true ->
+      {IG0, Worklists0, Moves0} = 
+	simplify(hipe_reg_worklists:simplify(Worklists),
+		 IG, 
+		 Worklists, 
+		 Moves, 
+		 K),
+      do_simplify_or_spill(IG0, Worklists0, Moves0, Alias,
+		  K, SpillLimit, Target);
+     Spill =:= true ->
+      Worklists0 = 
+	selectSpill(Worklists, IG, SpillLimit),
+      do_simplify_or_spill(IG, Worklists0, Moves, Alias, 
+			   K, SpillLimit, Target);
+     true -> % Catchall case
+      {IG, Worklists, Moves, Alias}
+    end.
+
+%%----------------------------------------------------------------------
+%% Function:    adjacent
+%%
+%% Description: Adjacent nodes that's not coalesced, on the stack or
+%%               precoloured.
+%% Parameters:
+%%   Node        --  Node that you want to adjacents of
+%%   IG          --  The interference graph
+%%
+%%   Returns: 
+%%     A set with nodes/temporaries that are not coalesced, on the 
+%%      stack or precoloured.
+%%----------------------------------------------------------------------
+
+adjacent(Node, IG, Worklists) ->
+  Adjacent_edges = hipe_ig:node_adj_list(Node, IG),
+  hipe_reg_worklists:non_stacked_or_coalesced_nodes(Adjacent_edges, Worklists).
+
+%%----------------------------------------------------------------------
+%% Function:    simplify
+%%
+%% Description: Simplify graph by removing nodes of low degree. This
+%%               function simplify all nodes it can at once.
+%% Parameters:
+%%   [Node|Nodes]  --  The simplify worklist
+%%   IG            --  The interference graph
+%%   Worklists     --  The worklists data-structure
+%%   Moves         --  The moves data-structure
+%%   K             --  Produce a K coloring
+%%
+%%   Returns: 
+%%     IG          --  An updated interference graph
+%%     Worklists   --  An updated worklists data-structure
+%%     Moves       --  An updated moves data-structure
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+simplify_O([], IG, Worklists, Moves, _K) -> 
+  {IG, Worklists, Moves};
+simplify_O([Node|Nodes], IG, Worklists, Moves, K) ->
+  Worklists0 = hipe_reg_worklists:remove_simplify(Node, Worklists),
+  ?debug_msg("putting ~w on stack~n",[Node]),
+  Adjacent = adjacent(Node, IG, Worklists0),
+  Worklists01 = hipe_reg_worklists:push_stack(Node, Adjacent, Worklists0),
+  {New_ig, Worklists1, New_moves} =
+    decrement_degree_O(Adjacent, IG, Worklists01, Moves, K),
+  simplify_O(Nodes, New_ig, Worklists1, New_moves, K).
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    simplify
+%%
+%% Description: Simplify graph by removing nodes of low degree. This
+%%               function simplify all nodes it can at once.
+%% Parameters:
+%%   [Node|Nodes]  --  The simplify worklist
+%%   IG            --  The interference graph
+%%   Worklists     --  The worklists data-structure
+%%   Moves         --  The moves data-structure
+%%   K             --  Produce a K coloring
+%%
+%%   Returns: 
+%%     IG          --  An updated interference graph
+%%     Worklists   --  An updated worklists data-structure
+%%     Moves       --  An updated moves data-structure
+%%----------------------------------------------------------------------
+
+simplify([], IG, Worklists, Moves, _K) -> 
+  {IG, Worklists, Moves};
+simplify([Node|Nodes], IG, Worklists, Moves, K) ->
+  Worklists0 = hipe_reg_worklists:remove_simplify(Node, Worklists),
+  ?debug_msg("putting ~w on stack~n",[Node]),
+  Adjacent = adjacent(Node, IG, Worklists0),
+  Worklists01 = hipe_reg_worklists:push_stack(Node, Adjacent, Worklists0),
+  {New_ig, Worklists1} = decrement_degree(Adjacent, IG, Worklists01, K),
+  simplify(Nodes, New_ig, Worklists1, Moves, K).
+
+%%----------------------------------------------------------------------
+%% Function:    decrement_degree
+%%
+%% Description: Decrement the degree on a number of nodes/temporaries.
+%% Parameters:
+%%   [Node|Nodes]  --  Decrement degree on these nodes
+%%   IG            --  The interference graph
+%%   Worklists     --  The Worklists data structure
+%%   Moves         --  The Moves data structure.
+%%   K             --  We want to create a coloring with K colors
+%%
+%%   Returns: 
+%%     IG          --  An updated interference graph (the degrees)
+%%     Worklists   --  Updated Worklists. Changed if one degree goes
+%%                     down to K.
+%%     Moves       --  Updated Moves. Changed if a move related temporary
+%%                     gets degree K.
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+decrement_degree_O([], IG, Worklists, Moves, _K) -> 
+  {IG, Worklists, Moves};
+decrement_degree_O([Node|Nodes], IG, Worklists, Moves, K) ->
+  PrevDegree = hipe_ig:get_node_degree(Node, IG),
+  IG0 = hipe_ig:dec_node_degree(Node, IG),
+  case PrevDegree =:= K of
+    true ->
+      AdjList = hipe_ig:node_adj_list(Node, IG0),
+      %% OK since Node (a) is still in IG, and (b) cannot be adjacent to itself.
+      Moves00 = enable_moves_active_to_worklist(hipe_moves:node_movelist(Node, Moves),
+						Moves),
+      Moves0 = enable_moves(AdjList, Worklists, Moves00),
+      Worklists0 = hipe_reg_worklists:remove_spill(Node, Worklists),
+      case hipe_moves:move_related(Node, Moves0) of
+	true ->
+	  Worklists1 = hipe_reg_worklists:add_freeze(Node, Worklists0),
+	  decrement_degree_O(Nodes, IG0, Worklists1, Moves0, K);
+	_ ->
+	  Worklists1 = hipe_reg_worklists:add_simplify(Node, Worklists0),
+	  decrement_degree_O(Nodes, IG0, Worklists1, Moves0, K)
+      end;
+     _ ->
+      decrement_degree_O(Nodes, IG0, Worklists, Moves, K)
+  end.
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    decrement_degree
+%%
+%% Description: Decrement the degree on a number of nodes/temporaries.
+%% Parameters:
+%%   [Node|Nodes]  --  Decrement degree on these nodes
+%%   IG            --  The interference graph
+%%   Worklists     --  The Worklists data structure
+%%   Moves         --  The Moves data structure.
+%%   K             --  We want to create a coloring with K colors
+%%
+%%   Returns: 
+%%     IG          --  An updated interference graph (the degrees)
+%%     Worklists   --  Updated Worklists. Changed if one degree goes
+%%                     down to K.
+%%     Moves       --  Updated Moves. Changed if a move related temporary
+%%                     gets degree K.
+%%----------------------------------------------------------------------
+
+decrement_degree([], IG, Worklists, _K) -> 
+  {IG, Worklists};
+decrement_degree([Node|Nodes], IG, Worklists, K) ->
+  PrevDegree = hipe_ig:get_node_degree(Node, IG),
+  IG0 = hipe_ig:dec_node_degree(Node, IG),
+  case PrevDegree =:= K of
+    true ->
+      Worklists0 = hipe_reg_worklists:remove_spill(Node, Worklists),
+      Worklists1 = hipe_reg_worklists:add_simplify(Node, Worklists0),
+      decrement_degree(Nodes, IG0, Worklists1, K);
+     _ ->
+      decrement_degree(Nodes, IG0, Worklists, K)
+  end.
+	    
+%%----------------------------------------------------------------------
+%% Function:    enable_moves
+%%
+%% Description: Make (move-related) nodes that are not yet considered for
+%%               coalescing, ready for possible coalescing.
+%%               
+%% Parameters:
+%%   [Node|Nodes]   --  A list of move nodes
+%%   Moves          --  The moves data-structure
+%%
+%%   Returns: 
+%%     An updated moves data-structure
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+enable_moves([], _Worklists, Moves) -> Moves;
+enable_moves([Node|Nodes], Worklists, Moves) ->
+  case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of
+    true -> enable_moves(Nodes, Worklists, Moves);
+    _ ->
+      %% moveList[n] suffices since we're checking for activeMoves membership
+      Node_moves = hipe_moves:node_movelist(Node, Moves),
+      New_moves = enable_moves_active_to_worklist(Node_moves, Moves),
+      enable_moves(Nodes, Worklists, New_moves)
+  end.
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    enable_moves_active_to_worklist
+%%
+%% Description: Make (move-related) nodes that are not yeat considered for
+%%               coalescing, ready for possible coalescing.
+%%               
+%% Parameters:
+%%   [Node|Nodes]   --  A list of move nodes
+%%   Moves          --  The moves data-structure
+%%
+%%   Returns: 
+%%     An updated moves data-structure
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+enable_moves_active_to_worklist([], Moves) -> Moves;
+enable_moves_active_to_worklist([Node|Nodes], Moves) ->
+  case hipe_moves:member_active(Node, Moves) of
+    true ->
+      New_moves = 
+	hipe_moves:add_worklist(Node, hipe_moves:remove_active(Node, Moves)),
+      enable_moves_active_to_worklist(Nodes, New_moves);
+    _ ->
+      enable_moves_active_to_worklist(Nodes, Moves)
+  end.
+-endif.
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+sanity_compare(Coloring, Coloring_N) ->
+  case compare_sanity(Coloring, Coloring_N) of
+    false ->
+      ?debug_msg("mismatch for coloring: ~n~p~n~p", [Coloring, Coloring_N]);
+    _ -> true
+  end.
+compare_sanity({[], _C}, {[], _C_N}) ->
+  ?debug_msg("Sanity - OK!~n", []),
+  true;
+compare_sanity({_Coloring_list, _C}, {[], _C_N}) ->
+  ?debug_msg("Sanity - unequal numbers~n", []),
+  false;
+compare_sanity({[], _C}, {_Coloring_list_N, _C_N}) ->
+  ?debug_msg("Sanity - unequal numbers~n", []),
+  false;
+compare_sanity({[Color|Coloring_list], C}, {[Color_N|Coloring_list_N], C_N}) ->
+  case element(1, Color) =:= element(1, Color_N) of
+    false ->
+      ?debug_msg("Sanity - unequal measure~n", []),
+      false;
+    _ -> 
+      case element(2, Color) =:= element(2, Color_N) of
+        false ->  
+	  ?debug_msg("Sanity - unequal color~n", []),
+	  false;
+	_ ->
+	  case C =:= C_N of
+	    false ->
+	      ?debug_msg("Sanity - unequal last element~n", []),
+	      false;
+	    _ ->
+	      compare_sanity({Coloring_list, C}, {Coloring_list_N, C_N})
+	  end
+      end
+  end.
+-endif.
+  
+  
+%% Build the namelists, these functions are fast hacks, they use knowledge 
+%% about data representation that they shouldn't know, bad abstraction.
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+build_namelist_O(NodeSets,Index,Alias,Color) ->
+  ?debug_msg("NodeSets ~w~n", [NodeSets]),
+  ?debug_msg("Building mapping\n",[]),
+  ?debug_msg("Vector to list\n",[]),
+  AliasList = 
+    build_alias_list(aliasToList(Alias),
+		     0, %% The first temporary has index 0
+		     []), %% Accumulator
+  ?debug_msg("Alias list:~p\n",[AliasList]),
+  ?debug_msg("Coalesced\n",[]),
+  NL1 = build_coalescedlist(AliasList,Color,Alias,[]),
+  ?debug_msg("Coalesced list:~p\n",[NL1]),
+  ?debug_msg("Regs\n",[]),
+  NL2 = build_reglist_O(hipe_node_sets:colored(NodeSets),Color,NL1),
+  ?debug_msg("Regs list:~p\n",[NL2]),
+  ?debug_msg("Spills\n",[]),
+  build_spillist(hipe_node_sets:spilled(NodeSets),Index,NL2).
+-endif.
+
+build_namelist(NodeSets,Index,Alias,Color) ->
+  ?debug_msg("NodeSets _N ~w~n", [NodeSets]),
+  ?debug_msg("Building mapping _N\n",[]),
+  ?debug_msg("Vector to list _N\n",[]),
+  AliasList = 
+    build_alias_list(aliasToList(Alias),
+		     0, %% The first temporary has index 0
+		     []), %% Accumulator
+  ?debug_msg("Alias list _N:~p\n",[AliasList]),
+  ?debug_msg("Coalesced\n",[]),
+  NL1 = build_coalescedlist(AliasList,Color,Alias,[]),
+  ?debug_msg("Coalesced list:~p\n",[NL1]),
+  ?debug_msg("Regs _N\n",[]),
+  ColoredNodes = hipe_node_sets:colored(NodeSets),
+  ?debug_msg("ColoredNodes ~p~n", [ColoredNodes]),
+  NL2 = build_reglist_N(ColoredNodes,Color,NL1,NL1),
+  ?debug_msg("Regs list _N:~p\n",[NL2]),
+  ?debug_msg("Spills _N\n",[]),
+  build_spillist(hipe_node_sets:spilled(NodeSets),Index,NL2).
+
+build_spillist([],Index,List) ->
+  {List,Index};
+build_spillist([Node|Nodes],Index,List) ->
+  ?debug_msg("[~p]: Spill ~p to ~p\n", [?MODULE,Node,Index]),
+  build_spillist(Nodes,Index+1,[{Node,{spill,Index}}|List]).
+
+build_coalescedlist([],_Color,_Alias,List) ->
+  List;
+build_coalescedlist([Node|Ns],Color,Alias,List) when is_integer(Node) ->
+  ?debug_msg("Alias of ~p is ~p~n",[Node,getAlias(Node,Alias)]),
+  AC = getColor(getAlias(Node,Alias),Color),
+  build_coalescedlist(Ns,Color,Alias,[{Node,{reg,AC}}|List]).
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+build_reglist_O([],_Color,List) -> 
+  List;
+build_reglist_O([Node|Ns],Color,List) ->
+  build_reglist_O(Ns,Color,[{Node,{reg,getColor(Node,Color)}}|List]).
+-endif.
+
+build_reglist_N([],_Color,List,_OrgList) -> 
+  List;
+build_reglist_N([Node|Ns],Color,List,OrgList) ->
+  %% XXX this could be done more efficiently if both lists were sorted
+  case is_already_in_list(Node, OrgList) of
+    true -> build_reglist_N(Ns, Color, List, OrgList);
+    _ -> build_reglist_N(Ns,Color,[{Node,{reg,getColor(Node,Color)}}|List], OrgList)
+  end.
+
+is_already_in_list(_Node, []) ->
+  false;
+is_already_in_list(Node, [L|List]) ->
+  ?debug_msg("---test--- Node ~w  element ~w~n", [Node, element(1, L)]),
+  case Node =:= element(1, L) of
+    true -> true;
+    _ -> is_already_in_list(Node, List)
+  end.
+
+build_alias_list([], _I, List) ->
+  List;
+build_alias_list([Alias|Aliases], I, List) when is_integer(Alias) ->
+  build_alias_list(Aliases, I+1, [I|List]);
+build_alias_list([_Alias|Aliases], I, List) ->
+  build_alias_list(Aliases, I+1, List).
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+sort_stack([]) -> [];
+sort_stack([Pivot|Rest]) ->
+  {Smaller, Bigger} = sort_stack_split(Pivot, Rest),
+  lists:append(sort_stack(Smaller), [Pivot|sort_stack(Bigger)]).
+
+sort_stack_split(Pivot, L) ->
+  sort_stack_split(Pivot, L, [], []).
+
+sort_stack_split(_Pivot, [], Smaller, Bigger) -> 
+  {Smaller, Bigger};
+sort_stack_split(Pivot, [H|T], Smaller, Bigger) when element(1, H) > element(1, Pivot) ->
+  sort_stack_split(Pivot, T, [H|Smaller], Bigger);
+sort_stack_split(Pivot, [H|T], Smaller, Bigger) ->
+  sort_stack_split(Pivot, T, Smaller, [H|Bigger]).
+-endif.
+
+%sort([]) -> [];
+%sort([Pivot|Rest]) ->
+%  {Smaller, Bigger} = sort_split(Pivot, Rest),
+%  lists:append(sort(Smaller), [Pivot|sort(Bigger)]).
+%
+%sort_split(Pivot, L) ->
+%  sort_split(Pivot, L, [], []).
+%
+%sort_split(_Pivot, [], Smaller, Bigger) -> {Smaller, Bigger};
+%sort_split(Pivot, [H|T], Smaller, Bigger) when H > Pivot ->
+%  sort_split(Pivot, T, [H|Smaller], Bigger);
+%sort_split(Pivot, [H|T], Smaller, Bigger) ->
+%  sort_split(Pivot, T, Smaller, [H|Bigger]).
+
+%%----------------------------------------------------------------------
+%% Function:    assignColors
+%%
+%% Description: Tries to assign colors to nodes in a stack.
+%% Parameters:
+%%   Worklists       --  The Worklists data structure.
+%%   Stack           --  The SelectStack built by the Select function, 
+%%                       this stack contains tuples in the form {Node,Edges} 
+%%                       where Node is the Node number and Edges is an ordset 
+%%                       containing the numbers of all the adjacent nodes.
+%%   NodeSets        --  This is a record containing all the different node 
+%%                       sets that are used in the register allocator.
+%%   Color           --  A mapping from nodes to their respective color.
+%%   No_temporaries  --  Number of temporaries.
+%%   SavedAdjList    --  Saved adjacency list (from before coalescing).
+%%   SavedSpillCosts --  Saved spill costs (from before coalescing).
+%%   IG              --  The interference graph.
+%%   Alias           --  This is a mapping from nodes to nodes. If a node has 
+%%                       been coalesced, this mapping shows the alias for that 
+%%                       node.
+%%   AllColors       --  This is an ordset containing all the available colors
+%%   Target          --  The module containing the target-specific functions.
+%%
+%% Returns:
+%%   Color          --  A mapping from nodes to their respective color.
+%%   NodeSets       --  The updated node sets.
+%%   Alias          --  The updated aliases.
+%%----------------------------------------------------------------------
+
+assignColors(Worklists, Stack, NodeSets, Color, No_Temporaries,
+	     SavedAdjList, SavedSpillCosts, IG, Alias, AllColors, Target) ->
+  case Stack of
+    [] ->
+      {Color,NodeSets,Alias};
+    [{Node,Edges}|Stack1] ->
+      ?debug_msg("Coloring Node: ~p~n",[Node]),
+      ?IF_DEBUG(lists:foreach(fun (_E) ->
+				  ?msg("  Edge ~w-><~w>->~w~n",
+				       begin A = getAlias(_E,Alias),
+					     [_E,A,getColor(A,Color)]
+				       end)
+			      end, Edges),
+		[]),
+      %% When debugging, check that Node isn't precoloured.
+      OkColors = findOkColors(Edges, AllColors, Color, Alias),
+      case colset_is_empty(OkColors) of
+	true -> % Spill case
+	  case hipe_reg_worklists:member_coalesced_to(Node, Worklists) of
+	    true ->
+	      ?debug_msg("Alias case. Undoing coalescing.~n", []),
+              {Alias1, IG1, NodeSets1, Color1, Stack2} = tryPrimitiveNodes(Node, Stack1, NodeSets, AllColors, Color, No_Temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, Target),
+              %{Alias1, IG1, NodeSets1, Color1, Stack2} = {Alias, IG, NodeSets, Color, Stack1},
+	      assignColors(Worklists, Stack2, NodeSets1, Color1, No_Temporaries, SavedAdjList, SavedSpillCosts, IG1, Alias1, AllColors, Target);
+	    false ->
+	      ?debug_msg("Spill case. Spilling node.~n", []),
+	      NodeSets1 = hipe_node_sets:add_spilled(Node, NodeSets),
+	      assignColors(Worklists, Stack1, NodeSets1, Color, No_Temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, AllColors, Target)
+	  end;
+	false -> % Color case
+	  Col = colset_smallest(OkColors),
+	  NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets),
+	  Color1 = setColor(Node, Target:physical_name(Col), Color),
+	  ?debug_msg("Color case. Assigning color ~p to node.~n", [Col]),
+	  assignColors(Worklists, Stack1, NodeSets1, Color1, No_Temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, AllColors, Target)
+      end
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    tryPrimitiveNodes
+%%
+%% Description: Undoes coalescing of a non-colorable coalesced node and tries
+%%              to assign colors to its primitives, such that the cheapest
+%%              potential spill cost is achieved.
+%% Parameters:
+%%   Node            --  The representative node to undo coalescing for.
+%%   Stack           --  The SelectStack built by the Select function, 
+%%                       this stack contains tuples in the form {Node,Edges} 
+%%                       where Node is the Node number and Edges is an ordset 
+%%                       containing the numbers of all the adjacent nodes.
+%%   NodeSets        --  This is a record containing all the different node 
+%%                       sets that are used in the register allocator.
+%%   AllColors       --  This is an ordset containing all the available colors.
+%%   No_temporaries  --  Number of temporaries.
+%%   SavedAdjList    --  Saved adjacency list (from before coalescing).
+%%   SavedSpillCosts --  Saved spill costs (from before coalescing).
+%%   IG              --  The interference graph.
+%%   Alias           --  This is a mapping from nodes to nodes. If a node has 
+%%                       been coalesced, this mapping shows the alias for that 
+%%                       node.
+%%   Target          --  The module containing the target-specific functions.
+%%
+%% Returns:
+%%   Alias           --  The restored aliases after the uncoalescing.
+%%   IG              --  An updated interference graph after the uncoalescing.
+%%   NodeSets        --  The updated node sets.
+%%   Color           --  A mapping from nodes to their respective color.
+%%   Stack           --  The updated SelectStack with non-colored primitives
+%%                       placed at the bottom.
+%%----------------------------------------------------------------------
+
+tryPrimitiveNodes(Node, Stack, NodeSets, AllColors, Color, No_temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, Target) ->
+  ?debug_msg("Undoing coalescing of node ~p.~n", [Node]),
+  {PrimitiveNodes, Alias1, IG1} = undoCoalescing(Node, No_temporaries, Alias, SavedAdjList, IG, Target),
+  ?debug_msg("Spilling non-colorable primitives.~n", []),
+  {ColorableNodes, NodeSets1} = spillNonColorablePrimitives([], PrimitiveNodes, NodeSets, AllColors, Color, SavedAdjList, Alias1),
+  ?debug_msg("Generating splits of colorable nodes.~n", []),
+  Splits = splits(ColorableNodes, SavedSpillCosts),
+  {NodeSets2, Color1, Stack1} = processSplits(Splits, AllColors, IG1, Color, NodeSets1, Alias1, Target, Stack),
+  {Alias1, IG1, NodeSets2, Color1, Stack1}.
+
+%% Spill all non-colorable primitives and return the remaining set of nodes.
+
+spillNonColorablePrimitives(ColorableNodes, [], NodeSets, _AllColors, _Color, _SavedAdjList, _Alias) ->
+  {ColorableNodes, NodeSets};
+spillNonColorablePrimitives(ColorableNodes, [Primitive|Primitives], NodeSets, AllColors, Color, SavedAdjList, Alias) ->
+  OkColors = findOkColors(hipe_adj_list:edges(Primitive, SavedAdjList), AllColors, Color, Alias),
+  case colset_is_empty(OkColors) of
+    true -> % Spill case
+      ?debug_msg("  Spilling primitive node ~p.~n", [Primitive]),
+      NodeSets1 = hipe_node_sets:add_spilled(Primitive, NodeSets),
+      spillNonColorablePrimitives(ColorableNodes, Primitives, NodeSets1, AllColors, Color, SavedAdjList, Alias);
+    false -> % Colorable case
+      ?debug_msg("  Primitive node ~p is colorable.~n", [Primitive]),
+      spillNonColorablePrimitives([Primitive|ColorableNodes], Primitives, NodeSets, AllColors, Color, SavedAdjList, Alias)
+  end.
+
+%% Generate all splits of colorable primitives, sorted in spill cost order.
+
+splits([], _SavedSpillCosts) ->
+  [{[], [], 0}];
+splits([L|Ls], SavedSpillCosts) ->
+  Spl = splits(Ls, SavedSpillCosts),
+  SpillCost = hipe_spillcost:spill_cost(L, SavedSpillCosts),
+  Spl1 = [splits_1(S, L) || S <- Spl],
+  Spl2 = [splits_2(S, L, SpillCost) || S <- Spl],
+  spillCostOrderedMerge(Spl1, Spl2, []).
+
+splits_1({Cols, NonCols, OldSpillCost}, L) ->
+    {[L|Cols], NonCols, OldSpillCost}.
+
+splits_2({Cols, NonCols, OldSpillCost}, L, SpillCost) ->
+    {Cols, [L|NonCols], OldSpillCost + SpillCost}.
+ 
+%% Merge two ordered sub-splits into one.
+
+spillCostOrderedMerge(Spl1, [], Spl) ->
+  lists:reverse(Spl) ++ Spl1;
+spillCostOrderedMerge([], Spl2, Spl) ->
+  lists:reverse(Spl) ++ Spl2;
+spillCostOrderedMerge(Spl1, Spl2, Spl) ->
+  {_, _, SpillCost1} = hd(Spl1),
+  {_, _, SpillCost2} = hd(Spl2),
+  case SpillCost1 =< SpillCost2 of
+    true ->
+      spillCostOrderedMerge(tl(Spl1), Spl2, [hd(Spl1)|Spl]);
+    false ->
+      spillCostOrderedMerge(Spl1, tl(Spl2), [hd(Spl2)|Spl])
+  end.
+
+%% Process splits, finding the one with the smallest spill cost that
+%% can be assigned one color.
+
+processSplits([], _AllColors, _IG, Color, NodeSets, _Alias, _Target, Stack) ->
+  {NodeSets, Color, Stack};
+processSplits([{Cols, NonCols, _SpillCost}|Splits], AllColors, IG, Color, NodeSets, Alias, Target, Stack) ->
+  OkColors = findCommonColors(Cols, IG, Color, Alias, AllColors),
+  case colset_is_empty(OkColors) of
+    false -> % This split can be colored with one color - use it
+      ?debug_msg("Found a colorable split.~n", []),
+      Col = colset_smallest(OkColors),
+      {NodeSets1, Color1} = colorSplit(Cols, Col, NodeSets, Color, Target),
+      Stack1 = enqueueSplit(NonCols, IG, Stack),
+      {NodeSets1, Color1, Stack1};
+    true -> % This split cannot be colored with one color - try another
+      ?debug_msg("Unable to color split.~n", []),
+      processSplits(Splits, AllColors, IG, Color, NodeSets, Alias, Target, Stack)
+  end.
+
+%% Find the set of colors that can be assigned to one split.
+
+findCommonColors([], _IG, _Color, _Alias, OkColors) ->
+  OkColors;
+findCommonColors([Primitive|Primitives], IG, Color, Alias, OkColors) ->
+  OkColors1 = findOkColors(hipe_ig:node_adj_list(Primitive, IG), OkColors, Color, Alias),
+  findCommonColors(Primitives, IG, Color, Alias, OkColors1).
+
+%% Color nodes in a split.
+
+colorSplit([], _Col, NodeSets, Color, _Target) ->
+  {NodeSets, Color};
+colorSplit([Node|Nodes], Col, NodeSets, Color, Target) ->
+  ?debug_msg("  Coloring node ~p with color ~p.~n", [Node, Col]),
+  NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets),
+  Color1 = setColor(Node, Target:physical_name(Col), Color),
+  colorSplit(Nodes, Col, NodeSets1, Color1, Target).
+
+%% Place non-colorable nodes in a split at the bottom of the SelectStack.
+
+enqueueSplit([], _IG, Stack) ->
+  Stack;
+enqueueSplit([Node|Nodes], IG, Stack) ->
+  ?debug_msg("  Placing node ~p at the bottom of the stack.~n", [Node]),
+  Edges = hipe_ig:node_adj_list(Node, IG),
+  Stack1 = Stack ++ [{Node, Edges}],
+  enqueueSplit(Nodes, IG, Stack1).
+
+%%----------------------------------------------------------------------
+%% Function:    assignColors
+%%
+%% Description: Tries to assign colors to nodes in a stack.
+%% Parameters:
+%%   Stack          --  The SelectStack built by the Select function, 
+%%                      this stack contains tuples in the form {Node,Edges} 
+%%                      where  Node is the Node number and Edges is an ordset 
+%%                      containing the numbers of all the adjacent nodes.
+%%   NodeSets       --  This is a record containing all the different node 
+%%                      sets that are used in the register allocator.
+%%   Alias          --  This is a mapping from nodes to nodes, if a node has 
+%%                      been coalesced this mapping shows the alias for that 
+%%                      node.
+%%   AllColors      --  This is an ordset containing all the available colors
+%%
+%%   Target         --  The module containing the target-specific functions.
+%%
+%% Returns:
+%%   Color          --  A mapping from nodes to their respective color.
+%%   NodeSets       --  The updated node sets.
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+assignColors_O(Stack,NodeSets,Color,Alias,AllColors,Target) ->
+  case Stack of
+    [] ->
+      {Color,NodeSets};
+    [{Node,Edges}|Stack1] ->
+      ?debug_msg("Coloring Node: ~p~n",[Node]),
+      ?IF_DEBUG(lists:foreach(fun (_E) ->
+				  ?msg("  Edge ~w-><~w>->~w~n",
+				       begin A = getAlias(_E,Alias),
+					     [_E,A,getColor(A,Color)]
+				       end)
+			      end, Edges),
+		[]),
+      %% When debugging, check that Node isn't precoloured.
+      OkColors = findOkColors(Edges, AllColors, Color, Alias),
+      case colset_is_empty(OkColors) of
+	true -> % Spill case
+	  NodeSets1 = hipe_node_sets:add_spilled(Node, NodeSets),
+	  assignColors_O(Stack1, NodeSets1, Color, Alias, AllColors, Target);
+	false -> % Colour case
+	  Col = colset_smallest(OkColors),
+	  NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets),
+	  Color1 = setColor(Node, Target:physical_name(Col), Color),
+	  assignColors_O(Stack1, NodeSets1, Color1, Alias, AllColors, Target)
+      end
+  end.
+-endif.
+
+%%---------------------------------------------------------------------
+%% Function:     defaultColoring
+%% 
+%% Description: Make the default coloring
+%% Parameters:
+%%   Regs           -- The list of registers to be default colored
+%%   Color          -- The color mapping that shall be changed
+%%   NodeSets       -- The node sets that shall be updated
+%%   Target         -- The module containing the target-specific functions.
+%%
+%% Returns:
+%%   NewColor       -- The updated color mapping
+%%   NewNodeSets    -- The updated node sets
+%%---------------------------------------------------------------------
+
+defaultColoring([], Color, NodeSets, _Target) ->
+  {Color,NodeSets};
+defaultColoring([Reg|Regs], Color, NodeSets, Target) ->
+  Color1 = setColor(Reg,Target:physical_name(Reg), Color),
+  NodeSets1 = hipe_node_sets:add_colored(Reg, NodeSets),
+  defaultColoring(Regs, Color1, NodeSets1, Target).
+
+%% Find the colors that are OK for a node with certain edges.
+
+findOkColors(Edges, AllColors, Color, Alias) ->
+  find(Edges, AllColors, Color, Alias).
+
+%% Find all the colors of the nodes in the list [Node|Nodes] and remove them 
+%% from the set OkColors, when the list is empty, return OkColors.
+
+find([], OkColors, _Color, _Alias) ->
+  OkColors;
+find([Node0|Nodes], OkColors, Color, Alias) ->
+  Node = getAlias(Node0, Alias),
+  case getColor(Node, Color) of
+    [] ->
+      find(Nodes, OkColors, Color, Alias);
+    Col ->
+      OkColors1 = colset_del_element(Col, OkColors),
+      find(Nodes, OkColors1, Color, Alias)
+  end.
+
+%%%
+%%% ColSet -- ADT for the set of available colours while
+%%% assigning colours.
+%%%
+-ifdef(notdef). % old ordsets-based implementation
+colset_from_list(Allocatable) ->
+  ordsets:from_list(Allocatable).
+
+colset_del_element(Colour, ColSet) ->
+  ordsets:del_element(Colour, ColSet).
+
+colset_is_empty(ColSet) ->
+  case ColSet of
+    [] -> true;
+    [_|_] -> false
+  end.
+
+colset_smallest([Colour|_]) ->
+  Colour.
+-endif.
+
+-ifdef(notdef). % new gb_sets-based implementation
+colset_from_list(Allocatable) ->
+  gb_sets:from_list(Allocatable).
+
+colset_del_element(Colour, ColSet) ->
+  %% Must use gb_sets:delete_any/2 since gb_sets:del_element/2
+  %% fails if the element isn't present. Bummer.
+  gb_sets:delete_any(Colour, ColSet).
+
+colset_is_empty(ColSet) ->
+  gb_sets:is_empty(ColSet).
+
+colset_smallest(ColSet) ->
+  gb_sets:smallest(ColSet).
+-endif.
+
+%%-ifdef(notdef). % new bitmask-based implementation
+colset_from_list(Allocatable) ->
+  colset_from_list(Allocatable, 0).
+
+colset_from_list([], ColSet) ->
+  ColSet;
+colset_from_list([Colour|Allocatable], ColSet) ->
+  colset_from_list(Allocatable, ColSet bor (1 bsl Colour)).
+
+colset_del_element(Colour, ColSet) ->
+  ColSet band bnot(1 bsl Colour).
+
+colset_is_empty(0) -> true;
+colset_is_empty(_) -> false.
+
+colset_smallest(ColSet) ->
+  bitN_log2(ColSet band -ColSet, 0).
+
+bitN_log2(BitN, ShiftN) ->
+  case BitN > 16#ffff of
+    true ->
+      bitN_log2(BitN bsr 16, ShiftN + 16);
+    _ ->
+      ShiftN + hweight16(BitN - 1)
+  end.
+
+hweight16(W) ->
+  Res1 = (   W band 16#5555) + ((   W bsr 1) band 16#5555),
+  Res2 = (Res1 band 16#3333) + ((Res1 bsr 2) band 16#3333),
+  Res3 = (Res2 band 16#0F0F) + ((Res2 bsr 4) band 16#0F0F),
+         (Res3 band 16#00FF) + ((Res3 bsr 8) band 16#00FF).
+%%-endif.
+
+%%%
+%%% Colour ADT providing a partial mapping from nodes to colours.
+%%%
+
+initColor(NrNodes) ->
+  {colmap, hipe_bifs:array(NrNodes, [])}.
+
+getColor(Node, {colmap, ColMap}) ->
+  hipe_bifs:array_sub(ColMap, Node).
+
+setColor(Node, Color, {colmap, ColMap} = C) ->
+  hipe_bifs:array_update(ColMap, Node, Color),  
+  C.
+
+-ifdef(DEBUG_PRINTOUTS).
+printColors(0, _) ->
+  true;
+printColors(Node, {colmap, ColMap} = C) ->
+  NextNode = Node - 1,
+  ?debug_msg("node ~w  color ~w~n", [NextNode, hipe_bifs:array_sub(ColMap, NextNode)]),
+  printColors(NextNode, C).
+-endif.
+
+%%%
+%%% Alias ADT providing a partial mapping from nodes to nodes.
+%%%
+
+initAlias(NrNodes) ->
+  {alias, hipe_bifs:array(NrNodes, [])}.
+
+%% Get alias for a node. 
+%% Note that non-aliased nodes could be represented in
+%% two ways, either not aliased or aliased to itself. 
+%% Including the latter case prevents looping bugs.
+getAlias(Node, {alias, AliasMap} = Alias) ->
+  case hipe_bifs:array_sub(AliasMap, Node) of
+    [] ->
+      Node;
+    Node ->
+      Node;
+    AliasNode ->
+      getAlias(AliasNode, Alias)
+  end.
+
+-ifdef(DEBUG_PRINTOUTS).
+printAlias({alias, AliasMap} = Alias) ->
+  ?debug_msg("Aliases:\n",[]),
+  printAlias(hipe_bifs:array_length(AliasMap), Alias).
+
+printAlias(0, {alias, _}) ->
+  true ;
+printAlias(Node, {alias, _AliasMap} = Alias) ->
+  ?debug_msg("alias ~p ~p\n", [Node - 1, getAlias(Node - 1, Alias)]),
+  printAlias(Node - 1, Alias).
+-endif.
+
+setAlias(Node, AliasNode, {alias, AliasMap} = Alias) ->
+  hipe_bifs:array_update(AliasMap, Node, AliasNode),
+  Alias.
+
+aliasToList({alias, AliasMap}) ->
+  aliasToList(AliasMap, hipe_bifs:array_length(AliasMap), []).
+
+aliasToList(AliasMap, I1, Tail) ->
+  I0 = I1 - 1,
+  case I0 >= 0 of
+    true ->
+      aliasToList(AliasMap, I0, [hipe_bifs:array_sub(AliasMap, I0)|Tail]);
+    _ ->
+      Tail
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    coalesce
+%%
+%% Description: Coalesces nodes in worklist
+%% Parameters:
+%%   Moves       -- Current move information
+%%   IG          -- Interference graph
+%%   Worklists   -- Current worklists
+%%   Alias       -- Current aliases for temporaries
+%%   K           -- Number of registers
+%%   
+%% Returns:
+%%   {Moves, IG, Worklists, Alias}
+%%         (Updated versions of above structures, after coalescing)
+%%----------------------------------------------------------------------
+
+coalesce(Moves, IG, Worklists, Alias, K, Target) ->
+  case hipe_moves:worklist_get_and_remove(Moves) of
+    {[],Moves0} ->
+      %% Moves marked for removal from worklistMoves by FreezeMoves()
+      %% are removed by worklist_get_and_remove(). This case is unlikely,
+      %% but can occur if only stale moves remain in worklistMoves.
+      {Moves0, IG, Alias};
+    {Move,Moves0} ->
+      {Dest,Source} = hipe_moves:get_move(Move, Moves0),
+      ?debug_msg("Testing nodes ~p and ~p for coalescing~n",[Dest,Source]),
+      Alias_src = getAlias(Source, Alias),
+      Alias_dst = getAlias(Dest, Alias),
+      {U,V} = case Target:is_precoloured(Alias_dst) of
+		true -> {Alias_dst, Alias_src};
+		false -> {Alias_src, Alias_dst}
+	      end,
+      %% When debugging, check that neither V nor U is on the stack.
+      case U =:= V of
+        true ->
+	  %% drop coalesced move Move
+	  {Moves0, IG, Alias, Worklists};
+	_ ->
+	  case (Target:is_precoloured(V) orelse
+		hipe_ig:nodes_are_adjacent(U, V, IG)) of 
+	    true ->
+	      %% drop constrained move Move
+	      {Moves0, IG, Alias, Worklists};
+	    false ->
+	      case (case Target:is_precoloured(U) of
+		      true ->
+			AdjV = hipe_ig:node_adj_list(V, IG),
+			all_adjacent_ok(AdjV, U, Worklists, IG, K, Target);
+		      false ->
+			AdjV = hipe_ig:node_adj_list(V, IG),
+			AdjU = hipe_ig:node_adj_list(U, IG),
+			conservative(AdjU, AdjV, U, Worklists, IG, K)
+		    end) of
+		true ->
+		  %% drop coalesced move Move
+		  {IG1, Alias1, Worklists1} = 
+		    combine(U, V, IG, Alias, Worklists, K, Target),
+		  {Moves0, IG1, Alias1, Worklists1};
+		false ->
+		  Moves1 = hipe_moves:add_active(Move, Moves0),
+		  {Moves1, IG, Alias, Worklists}
+	      end
+	  end
+      end
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    coalesce_O
+%%
+%% Description: Coalesces nodes in worklist
+%% Parameters:
+%%   Moves       -- Current move information
+%%   IG          -- Interference graph
+%%   Worklists   -- Current worklists
+%%   Alias       -- Current aliases for temporaries
+%%   K           -- Number of registers
+%%   
+%% Returns:
+%%   {Moves, IG, Worklists, Alias}
+%%         (Updated versions of above structures, after coalescing)
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+coalesce_O(Moves, IG, Worklists, Alias, K, Target) ->
+  case hipe_moves:worklist_get_and_remove(Moves) of
+    {[],Moves0} ->
+      %% Moves marked for removal from worklistMoves by FreezeMoves()
+      %% are removed by worklist_get_and_remove(). This case is unlikely,
+      %% but can occur if only stale moves remain in worklistMoves.
+      {Moves0,IG,Worklists,Alias};
+    {Move,Moves0} ->
+      {Dest,Source} = hipe_moves:get_move(Move, Moves0),
+      ?debug_msg("Testing nodes ~p and ~p for coalescing~n",[Dest,Source]),
+      Alias_src = getAlias(Source, Alias),
+      Alias_dst = getAlias(Dest, Alias),
+      {U,V} = case Target:is_precoloured(Alias_dst) of
+		true -> {Alias_dst, Alias_src};
+		false -> {Alias_src, Alias_dst}
+	      end,
+      %% When debugging, check that neither V nor U is on the stack.
+      case U =:= V of
+         true ->
+	  Moves1 = Moves0, % drop coalesced move Move
+	  Worklists1 = add_worklist(Worklists, U, K, Moves1, IG, Target),
+	  {Moves1, IG, Worklists1, Alias};
+	 _ ->
+	  case (Target:is_precoloured(V) orelse
+		hipe_ig:nodes_are_adjacent(U, V, IG)) of 
+	    true ->
+	      Moves1 = Moves0, % drop constrained move Move
+	      Worklists1 = add_worklist(Worklists, U, K, Moves1, IG, Target),
+	      Worklists2 = add_worklist(Worklists1, V, K, Moves1, IG, Target),
+	      {Moves1, IG, Worklists2, Alias};
+	    false ->
+	      case (case Target:is_precoloured(U) of
+		      true ->
+			AdjV = hipe_ig:node_adj_list(V, IG),
+			all_adjacent_ok(AdjV, U, Worklists, IG, K, Target);
+		      false ->
+			AdjV = hipe_ig:node_adj_list(V, IG),
+			AdjU = hipe_ig:node_adj_list(U, IG),
+			conservative(AdjU, AdjV, U, Worklists, IG, K)
+		    end) of
+		true ->
+		  Moves1 = Moves0, % drop coalesced move Move
+		  {IG1,Worklists1,Moves2,Alias1} =
+		    combine_O(U, V, IG, Worklists, Moves1, Alias, K, Target),
+		  Worklists2 = add_worklist(Worklists1, U, K, Moves2, IG1, Target),
+		  {Moves2, IG1, Worklists2, Alias1};
+		false ->
+		  Moves1 = hipe_moves:add_active(Move, Moves0),
+		  {Moves1, IG, Worklists, Alias}
+	      end
+	  end
+      end
+  end.
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    add_worklist
+%%
+%% Description: Builds new worklists where U is transferred from freeze
+%%              to simplify, if possible
+%%
+%% Parameters:
+%%   Worklists     -- Current worklists
+%%   U             -- Node to operate on
+%%   K             -- Number of registers
+%%   Moves         -- Current move information
+%%   IG            -- Interference graph
+%%   Target        -- The containing the target-specific functions
+%%   
+%% Returns:
+%%   Worklists (updated)
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+add_worklist(Worklists, U, K, Moves, IG, Target) ->
+  case (not(Target:is_precoloured(U))
+	andalso not(hipe_moves:move_related(U, Moves))
+	andalso (hipe_ig:is_trivially_colourable(U, K, IG))) of
+    true ->
+      hipe_reg_worklists:transfer_freeze_simplify(U, Worklists);
+    false ->
+      Worklists
+  end.
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    combine
+%%
+%% Description: Combines two nodes into one (used when coalescing)
+%%
+%% Parameters:
+%%   U          -- First node to operate on
+%%   V          -- Second node to operate on
+%%   IG         -- Interference graph
+%%   Worklists  -- Current worklists
+%%   Moves      -- Current move information
+%%   Alias      -- Current aliases for temporaries
+%%   K          -- Number of registers
+%%
+%% Returns:
+%%   {IG, Worklists, Moves, Alias} (updated)
+%%----------------------------------------------------------------------
+       
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+combine_O(U, V, IG, Worklists, Moves, Alias, K, Target) ->
+  Worklists1 = case hipe_reg_worklists:member_freeze(V, Worklists) of
+		 true -> hipe_reg_worklists:remove_freeze(V, Worklists);
+		 false -> hipe_reg_worklists:remove_spill(V, Worklists)
+	       end,
+  Worklists11 = hipe_reg_worklists:add_coalesced(V, Worklists1),
+  
+  ?debug_msg("Coalescing ~p and ~p to ~p~n",[V,U,U]),
+  
+  Alias1 = setAlias(V, U, Alias),
+  
+  %% Typo in published algorithm: s/nodeMoves/moveList/g to fix.
+  %% XXX: moveList[u] \union moveList[v] OR NodeMoves(u) \union NodeMoves(v) ???
+  %% XXX: NodeMoves() is correct, but unnecessarily strict. The ordsets:union
+  %% constrains NodeMoves() to return an ordset.
+  Moves1 = hipe_moves:update_movelist(U,
+				      ordsets:union(hipe_moves:node_moves(U, Moves),
+						    hipe_moves:node_moves(V, Moves)),
+				      Moves),
+  %% Missing in published algorithm. From Tiger book Errata.
+  Moves2 = enable_moves_active_to_worklist(hipe_moves:node_movelist(V, Moves1), Moves1),
+  AdjV = hipe_ig:node_adj_list(V, IG),
+  
+  {IG1, Worklists2, Moves3} =
+    combine_edges_O(AdjV, U, IG, Worklists11, Moves2, K, Target),
+
+  New_worklists = case (not(hipe_ig:is_trivially_colourable(U, K, IG1))
+			andalso hipe_reg_worklists:member_freeze(U, Worklists2)) of
+		    true -> hipe_reg_worklists:transfer_freeze_spill(U, Worklists2);
+		    false -> Worklists2
+		  end,
+  {IG1, New_worklists, Moves3, Alias1}.
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    combine
+%%
+%% Description: Combines two nodes into one (used when coalescing)
+%%
+%% Parameters:
+%%   U          -- First node to operate on
+%%   V          -- Second node to operate on
+%%   IG         -- Interference graph
+%%   Worklists  -- Current worklists
+%%   Moves      -- Current move information
+%%   Alias      -- Current aliases for temporaries
+%%   K          -- Number of registers
+%%
+%% Returns:
+%%   {IG, Worklists, Moves, Alias} (updated)
+%%----------------------------------------------------------------------
+       
+combine(U, V, IG, Alias, Worklists, K, Target) ->
+  ?debug_msg("N_Coalescing ~p and ~p to ~p~n",[V,U,U]),
+  Worklists1 = hipe_reg_worklists:add_coalesced(V, U, Worklists),
+  Alias1 = setAlias(V, U, Alias),
+  AdjV = hipe_ig:node_adj_list(V, IG),
+  IG1 = combine_edges(AdjV, U, IG, Worklists1, K, Target),
+  {IG1, Alias1, Worklists1}.
+
+%%----------------------------------------------------------------------
+%% Function:    combine_edges
+%%
+%% Description: For each node in a list, make an edge between that node
+%%              and node U, and decrement its degree by 1
+%%              (Used when two nodes are coalesced, to connect all nodes
+%%              adjacent to one node to the other node)
+%%
+%% Parameters:
+%%   [T|Ts]      -- List of nodes to make edges to
+%%   U           -- Node to make edges from
+%%   IG          -- Interference graph
+%%   Worklists   -- Current worklists
+%%   Moves       -- Current move information
+%%   K           -- Number of registers
+%%
+%% Returns:
+%%   {IG, Worklists, Moves} (updated)
+%%----------------------------------------------------------------------
+
+combine_edges([], _U, IG, _Worklists, _K, _Target) ->
+  IG;
+combine_edges([T|Ts], U, IG, Worklists, K, Target) ->
+  case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of
+    true -> combine_edges(Ts, U, IG, Worklists, K, Target);
+    _ ->
+      IG1 = hipe_ig:add_edge(T, U, IG, Target),
+      IG2 = case Target:is_precoloured(T) of
+	      true -> IG1;
+	      false -> hipe_ig:dec_node_degree(T, IG1)
+	    end,
+      combine_edges(Ts, U, IG2, Worklists, K, Target)
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    combine_edges
+%%
+%% Description: For each node in a list, make an edge between that node
+%%              and node U, and decrement its degree by 1
+%%              (Used when two nodes are coalesced, to connect all nodes
+%%              adjacent to one node to the other node)
+%%
+%% Parameters:
+%%   [T|Ts]      -- List of nodes to make edges to
+%%   U           -- Node to make edges from
+%%   IG          -- Interference graph
+%%   Worklists   -- Current worklists
+%%   Moves       -- Current move information
+%%   K           -- Number of registers
+%%
+%% Returns:
+%%   {IG, Worklists, Moves} (updated)
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+combine_edges_O([], _U, IG, Worklists, Moves, _K, _Target) ->
+  {IG, Worklists, Moves};
+combine_edges_O([T|Ts], U, IG, Worklists, Moves, K, Target) ->
+  case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of
+    true -> combine_edges_O(Ts, U, IG, Worklists, Moves, K, Target);
+    _ ->
+      %% XXX: The issue below occurs because the T->V edge isn't removed.
+      %% This causes adjList[T] to contain stale entries, to possibly grow
+      %% (if T isn't already adjacent to U), and degree[T] to possibly
+      %% increase (again, if T isn't already adjacent to U).
+      %% The decrement_degree() call repairs degree[T] but not adjList[T].
+      %% It would be better to physically replace T->V with T->U, and only
+      %% decrement_degree(T) if T->U already existed.
+      %%
+      %% add_edge() may change a low-degree move-related node to be of
+      %% significant degree. In this case the node belongs in the spill
+      %% worklist, and that's where decrement_degree() expects to find it.
+      %% This issue is not covered in the published algorithm.
+      OldDegree = hipe_ig:get_node_degree(T, IG),
+      IG1 = hipe_ig:add_edge(T, U, IG, Target),
+      NewDegree = hipe_ig:get_node_degree(T, IG1),
+      Worklists0 =
+	if NewDegree =:= K, OldDegree =:= K-1 ->
+	    %% ?debug_msg("~w:combine_edges_O(): repairing worklist membership for node ~w\n", [?MODULE,T]),
+	    %% The node T must be on the freeze worklist:
+	    %% 1. Since we're coalescing, the simplify worklist must have been
+	    %%    empty when combine_edges_O() started.
+	    %% 2. decrement_degree() may put the node T back on the simplify
+	    %%    worklist, but that occurs after the worklists repair step.
+	    %% 3. There are no duplicates among the edges.
+	    Worklists00 = hipe_reg_worklists:remove_freeze(T, Worklists),
+	    hipe_reg_worklists:add_spill(T, Worklists00);
+	   true ->
+	    Worklists
+	end,
+      {IG2, Worklists1, Moves1} =
+	decrement_degree_O([T], IG1, Worklists0, Moves, K),
+      combine_edges_O(Ts, U, IG2, Worklists1, Moves1, K, Target)
+  end.
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    undoCoalescing
+%%
+%% Description: Returns necessary information for a coalesced node
+%%
+%% Parameters:
+%%   N              -- The node to uncoalesce
+%%   No_temporaries -- Number of temporaries
+%%   Alias          -- The Alias vector before undoing
+%%   SavedAdj       -- Saved adjacency list
+%%   IG             -- Interference graph
+%%   Target         -- The module containing the target-specific functions.
+%%   
+%% Returns:
+%%   list of primitive nodes, that is all nodes that were previously
+%%           coalesced to N
+%%   updated alias vector
+%%   updated Interferece graph
+%%----------------------------------------------------------------------
+undoCoalescing(N, No_temporaries, Alias, SavedAdj, IG, Target) ->
+  Primitives = findPrimitiveNodes(No_temporaries, N, Alias),
+  Alias1 = restoreAliases(Primitives, Alias),
+  IG1 = fixAdj(N, SavedAdj, IG, Target),
+  {Primitives, Alias1, IG1}.
+
+%% Restore aliasinfo for primitive nodes, that is 
+%% unalias the node sthat were aliased to the primitive
+%% nodes. Note that an unaliased node could be
+%% represented in two ways, either not aliased or aliased
+%% to itself. See also getAlias
+restoreAliases([], Alias) ->
+  Alias;
+restoreAliases([Primitive|Primitives], Alias) ->
+  Alias1 = setAlias(Primitive, Primitive, Alias),
+  restoreAliases(Primitives, Alias1).
+
+%% find the primitive nodes to N, that is find all
+%% nodes that are aliased to N
+findPrimitiveNodes(No_temporaries, N, Alias) ->
+  findPrimitiveNodes(No_temporaries, N, Alias, []).
+
+findPrimitiveNodes(0, _N, _Alias, PrimitiveNodes) ->
+  PrimitiveNodes;
+findPrimitiveNodes(Node, N, Alias, PrimitiveNodes) ->
+  NextNode = Node - 1,
+  case (getAlias(NextNode, Alias) =:= N) of
+    true -> findPrimitiveNodes(NextNode, N, Alias, [NextNode | PrimitiveNodes]);
+    _ -> findPrimitiveNodes(NextNode, N, Alias, PrimitiveNodes)
+  end.
+
+%test_undoCoalescing(No_temporaries, Alias, Worklists) ->
+%  test_undoCoalescing(No_temporaries, No_temporaries, Alias, Worklists).
+%
+%test_undoCoalescing(0, _No_temporaries, _Alias, _Worklists) ->
+%  true;
+%test_undoCoalescing(Node, No_temporaries, Alias, Worklists) ->
+%  %?debug_msg("++ the adj list: ~p~n", [SavedAdj]),
+%  %?debug_msg("Node ~p~n", [Node]),
+%  NextNode = Node - 1,
+%  Coalesced_to = hipe_reg_worklists:member_coalesced_to(NextNode, Worklists),
+%  ?debug_msg("��-- member coalesced: ~p~n", [Coalesced_to]),
+%  {Primitives, Alias1} = undoCoalescing(NextNode, No_temporaries, Alias),
+%  ?debug_msg("��-- primitivenodes ~w\n", [Primitives]),
+%  case (Coalesced_to) of
+%    true -> printAlias(Alias1);
+%    _ -> true
+%  end,
+%  test_undoCoalescing(NextNode, No_temporaries, Alias, Worklists).
+
+%%----------------------------------------------------------------------
+%% Function:    fixAdj
+%%
+%% Description: Fixes adajency set and adjacency list when undoing coalescing
+%%
+%% Parameters:
+%%   N             -- Node that should be uncoalesced
+%%   SavedAdj      -- Saved adjacency list
+%%   IG            -- Interference graph
+%%   Target        -- The module containing the target-specific functions.
+%%   
+%% Returns:
+%%   updated Interferece graph
+%%----------------------------------------------------------------------
+fixAdj(N, SavedAdj, IG, Target) ->
+  %Saved = hipe_vectors:get(SavedAdj, N),
+  Saved = hipe_adj_list:edges(N, SavedAdj),
+  ?debug_msg("��--adj to ~p: ~p~n", [N, Saved]),
+  Adj = hipe_ig:node_adj_list(N, IG),
+  ?debug_msg("��--adj to ~p: ~p~n", [N, Adj]),
+  New = findNew(Adj, Saved),
+  ?debug_msg("++--new adj to ~p: ~p~n", [N, New]),
+  removeAdj(New, N, IG, Target),
+  %% XXX the following lines seems to make double nodes in
+  %% some adj_lists, which is a bug, apart from that they
+  %% don't seem to make any difference at all (even though
+  %% they are in the pseudocode of "optimistic coalescing")
+  %% addedge for all in the restored adj_list
+  %%RestoredAdj = hipe_ig:node_adj_list(N, IG),
+  %%?debug_msg("adj_lists_before_restore_o ~n~p~n", [hipe_ig:adj_list(IG)]),
+  %%restoreAdj(RestoredAdj, N, IG, Alias, Target).
+  IG.
+
+removeAdj([], _N, _IG, _Target) ->
+  true;
+removeAdj([V| New], N, IG, Target) ->
+  hipe_ig:remove_edge(V, N, IG, Target),
+  removeAdj(New, N, IG, Target).
+
+%%restoreAdj([], _N, IG, _Alias, _Target) ->
+%%  %%?debug_msg("adj_lists__after_restore_o ~n~p~n", [hipe_ig:adj_list(IG)]),
+%%  IG;
+%%restoreAdj([V| AdjToN], N, IG, Alias, Target) ->
+%%  AliasToV = getAlias(V, Alias),
+%%  IG1 = hipe_ig:add_edge(N, AliasToV, IG, Target),
+%%  restoreAdj(AdjToN, N, IG1, Alias, Target).
+
+%% XXX This is probably a clumsy way of doing it
+%% better to assure the lists are sorted from the beginning
+%% also coalesce findNew and removeAdj should improve performance
+findNew(Adj, Saved) ->
+  findNew(Adj, Saved, []).
+
+findNew([], _Saved, New) ->
+  New;
+findNew([A| Adj], Saved, New) ->
+  case lists:member(A, Saved) of
+    true -> findNew(Adj, Saved, New);
+    _ -> findNew(Adj, Saved, [A| New])
+  end.
+
+%test_fixAdj(0, _SavedAdj, IG, _Target) ->
+%  IG;
+%test_fixAdj(Node, SavedAdj, IG, Target) ->
+%  NextNode = Node - 1,
+%  IG1 = fixAdj(NextNode, SavedAdj, IG, Target),
+%  test_fixAdj(NextNode, SavedAdj, IG1, Target).
+%%----------------------------------------------------------------------
+%% Function:    ok
+%%
+%% Description: Checks if a node T is suitable to coalesce with R
+%%
+%% Parameters:
+%%   T             -- Node to test
+%%   R             -- Other node to test
+%%   IG            -- Interference graph
+%%   K             -- Number of registers
+%%   Target        -- The module containing the target-specific functions
+%%   
+%% Returns:
+%%   true iff coalescing is OK
+%%----------------------------------------------------------------------
+
+ok(T, R, IG, K, Target) ->
+  ((hipe_ig:is_trivially_colourable(T, K, IG))
+   orelse Target:is_precoloured(T)
+   orelse hipe_ig:nodes_are_adjacent(T, R, IG)).
+
+%%----------------------------------------------------------------------
+%% Function:    all_ok
+%%
+%% Description: True iff, for every T in the list, OK(T,U)
+%%
+%% Parameters:
+%%   [T|Ts]        -- Nodes to test
+%%   U             -- Node to test for coalescing
+%%   IG            -- Interference graph
+%%   K             -- Number of registers
+%%   Target        -- The module containing the target-specific functions
+%%   
+%% Returns:
+%%   true iff coalescing is OK for all nodes in the list
+%%----------------------------------------------------------------------
+
+all_adjacent_ok([], _U, _Worklists, _IG, _K, _Target) -> true;
+all_adjacent_ok([T|Ts], U, Worklists, IG, K, Target) ->
+  case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of
+    true -> all_adjacent_ok(Ts, U, Worklists, IG, K, Target);
+    _ ->
+      %% 'andalso' does not preserve tail-recursion
+      case ok(T, U, IG, K, Target) of
+	true -> all_adjacent_ok(Ts, U, Worklists, IG, K, Target);
+	false -> false
+      end
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    conservative
+%%
+%% Description: Checks if nodes can be safely coalesced according to
+%%              the Briggs' conservative coalescing heuristic
+%%
+%% Parameters:
+%%   Nodes         -- Adjacent nodes
+%%   IG            -- Interference graph
+%%   K             -- Number of registers
+%%   
+%% Returns:
+%%   true iff coalescing is safe
+%%----------------------------------------------------------------------
+
+conservative(AdjU, AdjV, U, Worklists, IG, K) ->
+  conservative_countU(AdjU, AdjV, U, Worklists, IG, K, 0).
+
+%%----------------------------------------------------------------------
+%% Function:    conservative_count
+%%
+%% Description: Counts degrees for conservative (Briggs' heuristics)
+%%
+%% Parameters:
+%%   Nodes         -- (Remaining) adjacent nodes
+%%   IG            -- Interference graph
+%%   K             -- Number of registers
+%%   Cnt           -- Accumulator for counting
+%%   
+%% Returns:
+%%   Final value of accumulator
+%%----------------------------------------------------------------------
+
+conservative_countU([], AdjV, U, Worklists, IG, K, Cnt) ->
+  conservative_countV(AdjV, U, Worklists, IG, K, Cnt);
+conservative_countU([Node|AdjU], AdjV, U, Worklists, IG, K, Cnt) ->
+  case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of
+    true -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt);
+    _ ->
+      case hipe_ig:is_trivially_colourable(Node, K, IG) of
+	true -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt);
+	_ ->
+	  Cnt1 = Cnt + 1,
+	  if Cnt1 < K -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt1);
+	     true -> false
+	  end
+      end
+  end.
+
+conservative_countV([], _U, _Worklists, _IG, _K, _Cnt) -> true;
+conservative_countV([Node|AdjV], U, Worklists, IG, K, Cnt) ->
+  case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of
+    true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt);
+    _ ->
+      case hipe_ig:nodes_are_adjacent(Node, U, IG) of
+	true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt);
+	_ ->
+	  case hipe_ig:is_trivially_colourable(Node, K, IG) of
+	    true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt);
+	    _ ->
+	      Cnt1 = Cnt + 1,
+	      if Cnt1 < K -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt1);
+		 true -> false
+	      end
+	  end
+      end
+  end.
+
+%%---------------------------------------------------------------------
+%% Function:    selectSpill
+%% 
+%% Description: Select the node to spill and spill it
+%% Parameters:
+%%   WorkLists      -- A datatype containing the different worklists
+%%   IG             -- The interference graph
+%%   K              -- The number of available registers
+%%   Alias          -- The alias mapping
+%%   SpillLimit     -- Try not to spill any nodes above the spill limit
+%%
+%% Returns:
+%%   WorkLists      -- The updated worklists
+%%---------------------------------------------------------------------
+
+selectSpill(WorkLists, IG, SpillLimit) ->
+  [CAR|CDR] = hipe_reg_worklists:spill(WorkLists),
+  SpillCost = getCost(CAR, IG, SpillLimit),
+  M = findCheapest(CDR, IG, SpillCost, CAR, SpillLimit),
+  WorkLists1 = hipe_reg_worklists:remove_spill(M, WorkLists),
+  hipe_reg_worklists:add_simplify(M, WorkLists1).
+
+%%---------------------------------------------------------------------
+%% Function:    selectSpill
+%% 
+%% Description: Select the node to spill and spill it
+%% Parameters:
+%%   WorkLists      -- A datatype containing the different worklists
+%%   Moves          -- A datatype containing the move sets
+%%   IG             -- The interference graph
+%%   K              -- The number of available registers
+%%   Alias          -- The alias mapping
+%%   SpillLimit     -- Try not to spill any nodes above the spill limit
+%%
+%% Returns:
+%%   WorkLists      -- The updated worklists
+%%   Moves          -- The updated moves
+%%---------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+selectSpill_O(WorkLists, Moves, IG, K, Alias, SpillLimit) ->
+  [CAR|CDR] = hipe_reg_worklists:spill(WorkLists),
+  
+  SpillCost = getCost(CAR, IG, SpillLimit),
+  M = findCheapest(CDR, IG, SpillCost, CAR, SpillLimit),
+  
+  WorkLists1 = hipe_reg_worklists:remove_spill(M, WorkLists),
+  %% The published algorithm adds M to the simplify worklist
+  %% before the freezeMoves() call. That breaks the worklist
+  %% invariants, which is why the order is switched here.
+  {WorkLists2,Moves1} = freezeMoves(M, K, WorkLists1, Moves, IG, Alias),
+  WorkLists3 = hipe_reg_worklists:add_simplify(M, WorkLists2),
+  {WorkLists3,Moves1}.
+-endif.
+
+%% Find the node that is cheapest to spill
+
+findCheapest([], _IG, _Cost, Cheapest, _SpillLimit) ->
+  Cheapest;
+findCheapest([Node|Nodes], IG, Cost, Cheapest, SpillLimit) ->
+  ThisCost = getCost(Node, IG, SpillLimit),
+  case ThisCost < Cost of
+    true ->
+      findCheapest(Nodes, IG, ThisCost, Node, SpillLimit);
+    false ->
+      findCheapest(Nodes, IG, Cost, Cheapest, SpillLimit)
+  end.
+
+%% Get the cost for spilling a certain node, node numbers above the spill 
+%% limit are extremely expensive.
+
+getCost(Node, IG, SpillLimit) ->
+  case Node > SpillLimit of
+    true -> inf;
+    false ->
+      SpillCost = hipe_ig:node_spill_cost(Node, IG),
+      ?debug_msg("Actual spillcost f node ~w is ~w~n", [Node, SpillCost]),
+      SpillCost
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    freeze
+%%
+%% Description: When both simplifying and coalescing is impossible we 
+%%              rather freezes a node in stead of spilling, this function
+%%              selects a node for freezing (it just picks the first one in
+%%              the list)
+%%
+%% Parameters:
+%%   K              -- The number of available registers
+%%   WorkLists      -- A datatype containing the different worklists
+%%   Moves          -- A datatype containing the different movelists
+%%   IG             -- Interference graph
+%%   Alias          -- An alias mapping, shows the alias of all coalesced 
+%%                      nodes  
+%%
+%% Returns:
+%%   WorkLists      -- The updated worklists
+%%   Moves          -- The updated movelists
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+freeze(K, WorkLists, Moves, IG, Alias) ->
+  [U|_] = hipe_reg_worklists:freeze(WorkLists),         % Smarter routine?
+  ?debug_msg("freezing node ~p~n", [U]),
+  WorkLists0 = hipe_reg_worklists:remove_freeze(U, WorkLists),
+  %% The published algorithm adds U to the simplify worklist
+  %% before the freezeMoves() call. That breaks the worklist
+  %% invariants, which is why the order is switched here.
+  {WorkLists1, Moves1} = freezeMoves(U, K, WorkLists0, Moves, IG, Alias),
+  WorkLists2 = hipe_reg_worklists:add_simplify(U, WorkLists1),
+  {WorkLists2, Moves1}.
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    freezeMoves
+%%
+%% Description: Make all move related interferences for a certain node 
+%%              into ordinary interference arcs.
+%%              
+%% Parameters:
+%%   U              -- The node we want to freeze
+%%   K              -- The number of available registers
+%%   WorkLists      -- A datatype containing the different worklists
+%%   Moves          -- A datatype containing the different movelists
+%%   IG             -- Interference graph
+%%   Alias          -- An alias mapping, shows the alias of all coalesced 
+%%                     nodes  
+%%
+%% Returns:
+%%   WorkLists      -- The updated worklists
+%%   Moves          -- The updated movelists
+%%----------------------------------------------------------------------
+
+-ifdef(COMPARE_ITERATED_OPTIMISTIC).
+freezeMoves(U, K, WorkLists, Moves, IG, Alias) ->
+  Nodes = hipe_moves:node_moves(U, Moves),
+  freezeEm(U, Nodes, K, WorkLists, Moves, IG, Alias).
+
+%% Find what the other value in a copy instruction is, return false if 
+%% the instruction isn't a move with the first argument in it.
+
+moves(U, Move, Alias, Moves) ->
+  {X,Y} = hipe_moves:get_move(Move, Moves),
+  %% The old code (which followed the published algorithm) did
+  %% not follow aliases before looking for "the other" node.
+  %% This caused moves() to skip some moves, making some nodes
+  %% still move-related after freezeMoves(). These move-related
+  %% nodes were then added to the simplify worklist (by freeze()
+  %% or selectSpill()), breaking the worklist invariants. Nodes
+  %% already simplified appeared in coalesce_O(), were re-added to
+  %% the simplify worklist by add_worklist(), simplified again,
+  %% and coloured multiple times by assignColors(). Ouch!
+  X1 = getAlias(X, Alias),
+  Y1 = getAlias(Y, Alias),
+  if U =:= X1 -> Y1;
+     U =:= Y1 -> X1;
+     true -> exit({?MODULE,moves}) % XXX: shouldn't happen
+  end.
+
+freezeEm(_U, [], _K, WorkLists, Moves, _IG, _Alias) -> 
+  {WorkLists,Moves};
+freezeEm(U, [M|Ms], K, WorkLists, Moves, IG, Alias) ->
+  V = moves(U, M, Alias, Moves),
+  {WorkLists2,Moves2} = freezeEm2(U, V, M, K, WorkLists, Moves, IG, Alias),
+  freezeEm(U, Ms, K, WorkLists2, Moves2, IG, Alias).
+
+freezeEm2(U, V, M, K, WorkLists, Moves, IG, Alias) ->
+  case hipe_moves:member_active(M, Moves) of
+    true ->
+      Moves1 = hipe_moves:remove_active(M, Moves),
+      freezeEm3(U, V, M, K, WorkLists, Moves1, IG, Alias);	
+    false ->
+      Moves1 = hipe_moves:remove_worklist(M, Moves),
+      freezeEm3(U, V, M, K, WorkLists, Moves1, IG, Alias)
+  end.
+
+freezeEm3(_U,V,_M,K,WorkLists,Moves,IG,_Alias) ->
+  Moves1 = Moves, % drop frozen move M
+  V1 = V, % getAlias(V,Alias),
+  %% "not MoveRelated(v)" is cheaper than "NodeMoves(v) = {}"
+  case ((not hipe_moves:move_related(V1,Moves1)) andalso
+	hipe_ig:is_trivially_colourable(V1,K,IG)) of
+    true ->
+      ?debug_msg("freezing move to ~p~n", [V]),
+      Worklists1 = hipe_reg_worklists:transfer_freeze_simplify(V1, WorkLists),
+      {Worklists1,Moves1};
+    false ->
+      {WorkLists,Moves1}
+  end.
+-endif.