The R13B03 release.OTP_R13B03

1 files changed, 776 insertions, 0 deletions

diff --git a/lib/hipe/regalloc/hipe_ig.erl b/lib/hipe/regalloc/hipe_ig.erl
new file mode 100644
index 0000000000..4991e73e53
--- /dev/null
+++ b/lib/hipe/regalloc/hipe_ig.erl
@@ -0,0 +1,776 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2001-2009. All Rights Reserved.
+%% 
+%% The contents of this file are subject to the Erlang Public License,
+%% Version 1.1, (the "License"); you may not use this file except in
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%% 
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%% 
+%% %CopyrightEnd%
+%%
+%%----------------------------------------------------------------------
+%% File    : hipe_ig.erl
+%% Author  : Andreas Wallin <[email protected]>
+%% Purpose : Creates an interference graph that tells which temporaries
+%%           interfere with each other.
+%% Created : 5 Feb 2000
+%%----------------------------------------------------------------------
+
+-module(hipe_ig).
+
+-export([build/2, 
+	 nodes_are_adjacent/3,
+	 node_spill_cost/2,
+	 node_adj_list/2,
+	 get_moves/1,
+	 %% degree/1,
+	 %% number_of_temps/1,
+	 spill_costs/1,
+	 adj_list/1,
+	 %% adj_set/1,
+	 add_edge/4,
+	 remove_edge/4,
+	 %% set_adj_set/2,
+	 %% set_adj_list/2,
+	 %% set_ig_moves/2,
+	 %% set_spill_costs/2,
+	 %% set_degree/2
+	 get_node_degree/2,
+	 dec_node_degree/2,
+	 is_trivially_colourable/3
+	]).
+-ifdef(DEBUG_PRINTOUTS).
+-export([print_spill_costs/1,
+	 print_adjacent/1,
+	 print_degrees/1
+	]).
+-endif.
+
+%%-ifndef(DEBUG).
+%%-define(DEBUG,true).
+%%-endif.
+
+-include("../main/hipe.hrl").
+-include("../flow/cfg.hrl").
+-include("hipe_spillcost.hrl").
+
+%%----------------------------------------------------------------------
+
+-record(igraph, {adj_set, adj_list, ig_moves, degree,
+		 spill_costs :: #spill_cost{},
+		 num_temps   :: non_neg_integer()}).
+
+%%----------------------------------------------------------------------
+%% Degree: array mapping nodes to integer degrees.
+%% Precoloured nodes have 'infinite' degrees: they are initialised with
+%% degrees K + number_of_temporaries.
+%% Operations include incrementing, decrementing, and querying a node's
+%% degree, and testing for trivial colourability (degree < K).
+%%----------------------------------------------------------------------
+
+degree_new(No_temporaries, Target) ->
+  Degree = hipe_bifs:array(No_temporaries, 0),
+  K = length(Target:allocatable()),
+  Inf = K + No_temporaries,
+  precoloured_to_inf_degree(Target:all_precoloured(), Inf, Degree).
+
+precoloured_to_inf_degree([], _Inf, Degree) -> Degree;
+precoloured_to_inf_degree([P|Ps], Inf, Degree) ->
+  hipe_bifs:array_update(Degree, P, Inf),
+  precoloured_to_inf_degree(Ps, Inf, Degree).
+
+degree_inc(Node, Degree) ->
+  hipe_bifs:array_update(Degree, Node, hipe_bifs:array_sub(Degree, Node) + 1).
+
+degree_dec(Node, Degree) ->
+  hipe_bifs:array_update(Degree, Node, hipe_bifs:array_sub(Degree, Node) - 1).
+
+degree_get(Node, Degree) ->
+  hipe_bifs:array_sub(Degree, Node).
+
+degree_is_trivially_colourable(Node, K, Degree) ->
+  hipe_bifs:array_sub(Degree, Node) < K.
+
+%%----------------------------------------------------------------------
+%% AdjSet:
+%% Implements sets of adjacent nodes.
+%% Symmetry implies that when (U,V) is a member, then so is (V,U).
+%% Hence, only (U,V), where U<V, is actually stored.
+%% Supports queries and destructive updates, but not enumeration.
+%% Implemented as a bit array in an array of bytes, augmented by an
+%% index vector for fast address calculations.
+%%----------------------------------------------------------------------
+
+-define(USE_NEW_BITARRAY_BIFS, true).
+%%-define(EMULATE_BITARRAY_BIFS, true).
+
+-ifdef(USE_NEW_BITARRAY_BIFS).
+-define(HIPE_BIFS_BITARRAY(ArrayBits, Val), hipe_bifs:bitarray(ArrayBits, Val)).
+-define(HIPE_BIFS_BITARRAY_UPDATE(Array, BitNr, Val), hipe_bifs:bitarray_update(Array, BitNr, Val)).
+-define(HIPE_BIFS_BITARRAY_SUB(Array, BitNr), hipe_bifs:bitarray_sub(Array, BitNr)).
+-endif.
+
+-ifdef(EMULATE_BITARRAY_BIFS).
+
+-define(LOG2_BITS_PER_WORD, 3).
+-define(BITS_PER_WORD, (1 bsl ?LOG2_BITS_PER_WORD)).
+
+hipe_bifs_bitarray(ArrayBits, Val) ->
+  ArrayWords = (ArrayBits + (?BITS_PER_WORD - 1)) bsr ?LOG2_BITS_PER_WORD,
+  Byte =
+    case Val of
+      true -> 16#FF;
+      false -> 16#00
+    end,
+  hipe_bifs:bytearray(ArrayWords, Byte).
+
+hipe_bifs_bitarray_update(Array, BitNr, Val) ->
+  WordNr = BitNr bsr ?LOG2_BITS_PER_WORD,
+  WordMask = 1 bsl (BitNr band (?BITS_PER_WORD - 1)),
+  Word = hipe_bifs:bytearray_sub(Array, WordNr),
+  NewWord =
+    case Val of
+      true -> Word bor WordMask;
+      false -> Word band (bnot WordMask)
+    end,
+  hipe_bifs:bytearray_update(Array, WordNr, NewWord).
+
+hipe_bifs_bitarray_sub(Array, BitNr) ->
+  WordNr = BitNr bsr ?LOG2_BITS_PER_WORD,
+  WordMask = 1 bsl (BitNr band (?BITS_PER_WORD - 1)),
+  Word = hipe_bifs:bytearray_sub(Array, WordNr),
+  Word band WordMask =/= 0.
+
+-define(HIPE_BIFS_BITARRAY(ArrayBits, Val), hipe_bifs_bitarray(ArrayBits, Val)).
+-define(HIPE_BIFS_BITARRAY_UPDATE(Array, BitNr, Val), hipe_bifs_bitarray_update(Array, BitNr, Val)).
+-define(HIPE_BIFS_BITARRAY_SUB(Array, BitNr), hipe_bifs_bitarray_sub(Array, BitNr)).
+
+-endif. % EMULATE_BITARRAY_BIFS
+
+-record(adjset, {index, array}).
+-record(adjset_chunked, {index, chunks}).
+
+-spec adjset_new(non_neg_integer()) -> #adjset{} | #adjset_chunked{}.
+
+adjset_new(NrTemps) ->
+  ArrayBits = (NrTemps * (NrTemps - 1)) div 2,
+  Index = adjset_mk_index(NrTemps, []),
+  try ?HIPE_BIFS_BITARRAY(ArrayBits, false) of
+    Array ->
+      #adjset{index=Index,array=Array}
+  catch
+    _:_ ->
+      #adjset_chunked{index=Index,chunks=adjset_mk_chunks(ArrayBits)}
+  end.
+
+-define(LOG2_CHUNK_BITS, 19).	% 2^19 bits == 64KB
+-define(CHUNK_BITS, (1 bsl ?LOG2_CHUNK_BITS)).
+
+adjset_mk_chunks(ArrayBits) ->
+  Tail =
+    case ArrayBits band (?CHUNK_BITS - 1) of
+      0 -> [];
+      LastChunkBits -> [?HIPE_BIFS_BITARRAY(LastChunkBits, false)]
+    end,
+  N = ArrayBits bsr ?LOG2_CHUNK_BITS,
+  adjset_mk_chunks(N, Tail).
+
+adjset_mk_chunks(0, Tail) ->
+  list_to_tuple(Tail);
+adjset_mk_chunks(N, Tail) ->
+  adjset_mk_chunks(N-1, [?HIPE_BIFS_BITARRAY(?CHUNK_BITS, false) | Tail]).
+
+adjset_mk_index(0, Tail) ->
+  list_to_tuple(Tail);
+adjset_mk_index(N, Tail) ->
+  I = N - 1,
+  adjset_mk_index(I, [(I * (I-1)) div 2 | Tail]).
+
+adjset_add_edge(U0, V0, #adjset{index=Index,array=Array}) -> % PRE: U0 =/= V0
+  {U,V} =
+    if U0 < V0 -> {U0,V0};
+       true -> {V0,U0}
+    end,
+  %% INV: U < V
+  BitNr = element(V+1, Index) + U,
+  ?HIPE_BIFS_BITARRAY_UPDATE(Array, BitNr, true);
+adjset_add_edge(U0, V0, #adjset_chunked{index=Index,chunks=Chunks}) -> % PRE: U0 =/= V0
+  {U,V} =
+    if U0 < V0 -> {U0,V0};
+       true -> {V0,U0}
+    end,
+  %% INV: U < V
+  BitNr = element(V+1, Index) + U,
+  %% here things become different
+  ChunkNr = BitNr bsr ?LOG2_CHUNK_BITS,
+  ChunkBit = BitNr band (?CHUNK_BITS - 1),
+  Chunk = element(ChunkNr+1, Chunks),
+  ?HIPE_BIFS_BITARRAY_UPDATE(Chunk, ChunkBit, true).
+
+adjset_remove_edge(U0, V0, #adjset{index=Index,array=Array}) -> % PRE: U0 =/= V0
+  {U,V} =
+    if U0 < V0 -> {U0,V0};
+       true -> {V0,U0}
+    end,
+  %% INV: U < V
+  BitNr = element(V+1, Index) + U,
+  ?HIPE_BIFS_BITARRAY_UPDATE(Array, BitNr, false);
+adjset_remove_edge(U0, V0, #adjset_chunked{index=Index,chunks=Chunks}) -> % PRE: U0 =/= V0
+  {U,V} =
+    if U0 < V0 -> {U0,V0};
+       true -> {V0,U0}
+    end,
+  %% INV: U < V
+  BitNr = element(V+1, Index) + U,
+  %% here things become different
+  ChunkNr = BitNr bsr ?LOG2_CHUNK_BITS,
+  ChunkBit = BitNr band (?CHUNK_BITS - 1),
+  Chunk = element(ChunkNr+1, Chunks),
+  ?HIPE_BIFS_BITARRAY_UPDATE(Chunk, ChunkBit, false).
+
+adjset_are_adjacent(U0, V0, #adjset{index=Index,array=Array}) ->
+  {U,V} =
+    if U0 < V0 -> {U0,V0};
+       U0 =:= V0 -> exit({?MODULE,adjacent,U0,V0}); % XXX: probably impossible
+       true -> {V0,U0}
+    end,
+  %% INV: U < V
+  BitNr = element(V+1, Index) + U,
+  ?HIPE_BIFS_BITARRAY_SUB(Array, BitNr);
+adjset_are_adjacent(U0, V0, #adjset_chunked{index=Index,chunks=Chunks}) ->
+  {U,V} =
+    if U0 < V0 -> {U0,V0};
+       U0 =:= V0 -> exit({?MODULE,adjacent,U0,V0}); % XXX: probably impossible
+       true -> {V0,U0}
+    end,
+  %% INV: U < V
+  BitNr = element(V+1, Index) + U,
+  %% here things become different
+  ChunkNr = BitNr bsr ?LOG2_CHUNK_BITS,
+  ChunkBit = BitNr band (?CHUNK_BITS - 1),
+  Chunk = element(ChunkNr+1, Chunks),
+  ?HIPE_BIFS_BITARRAY_SUB(Chunk, ChunkBit).
+
+%%---------------------------------------------------------------------
+%% Print functions - only used for debugging
+
+-ifdef(DEBUG_PRINTOUTS).
+print_adjacent(IG) ->
+  ?debug_msg("Adjacent nodes:\n", []),
+  adjset_print(number_of_temps(IG),IG).
+
+adjset_print(2, IG) ->
+  adjset_print(1, 0, IG);
+adjset_print(Ntemps, IG) ->
+  adjset_print(Ntemps - 1, Ntemps - 2, IG),
+  adjset_print(Ntemps - 1, IG).
+
+adjset_print(U, 0, IG) ->
+  case nodes_are_adjacent(U, 0, IG) of
+    true -> ?debug_msg("edge ~w ~w\n", [U, 0]);
+    _ -> true
+  end;
+adjset_print(U, V, IG) ->
+  case nodes_are_adjacent(U, V, IG) of
+    true -> ?debug_msg("edge ~w ~w\n", [U, V]);
+    _ -> true
+  end,
+  adjset_print(U, V - 1, IG).
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    adj_set, adj_list, degree, spill_costs
+%%
+%% Description: Selector functions. Used to get one of the encapsulated 
+%%              data-structure contained in the IG structure.
+%% Parameters:
+%%   IG     --  An interference graph
+%%
+%% Returns: 
+%%   One of the encapsulated data-structures.
+%%----------------------------------------------------------------------
+adj_set(IG)     -> IG#igraph.adj_set.
+adj_list(IG)    -> IG#igraph.adj_list.
+ig_moves(IG)    -> IG#igraph.ig_moves.    
+degree(IG)      -> IG#igraph.degree.
+
+-spec spill_costs(#igraph{}) -> #spill_cost{}.
+spill_costs(IG) -> IG#igraph.spill_costs.
+
+-ifdef(DEBUG_PRINTOUTS).
+number_of_temps(IG) -> IG#igraph.no_temps.
+-endif.
+
+%%----------------------------------------------------------------------
+%% Function:    set_adj_set, set_adj_list, set_degree, set_spill_costs
+%%
+%% Description: Modifier functions. Used to set one of the encapsulated 
+%%              data-structure contained in the IG structure.
+%% Parameters:
+%%   Data-structure --  Data-structure you want to set. An adj_set 
+%%                       data-structure for example.
+%%   IG             --  An interference graph
+%%
+%% Returns: 
+%%   An updated interference graph.
+%%----------------------------------------------------------------------
+
+%%set_adj_set(Adj_set, IG)       -> IG#igraph{adj_set  = Adj_set}.
+set_adj_list(Adj_list, IG)       -> IG#igraph{adj_list = Adj_list}.
+set_ig_moves(IG_moves, IG)       -> IG#igraph{ig_moves = IG_moves}.
+%%set_degree(Degree, IG)         -> IG#igraph{degree   = Degree}.
+set_spill_costs(Spill_costs, IG) -> IG#igraph{spill_costs = Spill_costs}.
+
+%%----------------------------------------------------------------------
+%% Function:    initial_ig
+%%
+%% Description: The initial interference record that we start with when
+%%              building the interference graph.
+%% Parameters:
+%%   NumTemps -- Number of temporaries in the CFG we work on. This is
+%%               because we have some data structures built out of vectors.
+%%
+%% Returns: 
+%%   A new interference record
+%%----------------------------------------------------------------------
+
+-spec initial_ig(non_neg_integer(), atom()) -> #igraph{}.
+
+initial_ig(NumTemps, Target) ->
+  #igraph{adj_set     = adjset_new(NumTemps),
+	  adj_list    = hipe_adj_list:new(NumTemps),
+	  ig_moves    = hipe_ig_moves:new(NumTemps),
+	  degree      = degree_new(NumTemps, Target),
+	  spill_costs = hipe_spillcost:new(NumTemps),
+	  num_temps   = NumTemps
+	 }.
+
+%%----------------------------------------------------------------------
+%% Function:    build
+%%
+%% Description: Constructs an interference graph for the specifyed CFG.
+%%
+%% Parameters:
+%%   CFG     -- A Control Flow Graph
+%%   Target  -- The module that contains the target-specific functions
+%%
+%% Returns: 
+%%   An interference graph for the given CFG.
+%%----------------------------------------------------------------------
+
+-spec build(#cfg{}, atom()) -> #igraph{}.
+
+build(CFG, Target) ->
+  BBs_in_out_liveness = Target:analyze(CFG),
+  Labels = Target:labels(CFG),
+  %% How many temporaries exist?
+  NumTemps = Target:number_of_temporaries(CFG),
+  IG0 = initial_ig(NumTemps, Target),
+  %%?debug_msg("initial adjset: ~p\n",[element(2, IG0)]),
+  %%?debug_msg("initial adjset array: ~.16b\n",[element(3, element(2, IG0))]),
+  analyze_bbs(Labels, BBs_in_out_liveness, IG0, CFG, Target).
+
+%%----------------------------------------------------------------------
+%% Function:    analyze_bbs
+%%
+%% Description: Looks up the code that exists in all basic blocks and
+%%              analyse instructions use and def's to see what 
+%%              temporaries that interfere with each other.
+%%
+%% Parameters:
+%%   L                    --  A label
+%%   Ls                   --  Other labels that exits in the CFG
+%%   BBs_in_out_liveness  --  The in and out liveness on all basic blocks
+%%   IG                   --  The interference graph in it's current state
+%%   CFG                  --  The Control Flow Graph that we constructs 
+%%                            the interference graph from.
+%%   Target               --  The module containing the target-specific
+%%                            functions
+%%
+%% Returns: 
+%%   An interference graph for the given CFG.
+%%----------------------------------------------------------------------
+
+analyze_bbs([], _, IG, _, _) -> IG;
+analyze_bbs([L|Ls], BBs_in_out_liveness, IG, CFG, Target) ->
+    % Get basic block associated with label L
+    BB = Target:bb(CFG, L),
+    % Get basic block code
+    BB_code = hipe_bb:code(BB),
+    % Temporaries that are live out from this basic block
+    BB_liveout = Target:liveout(BBs_in_out_liveness, L),
+    % Only temporary numbers
+    BB_liveout_numbers = reg_numbers(BB_liveout, Target),
+    % {Liveness, New Interference Graph}
+    {_, New_ig, Ref} = analyze_bb_instructions(BB_code,
+					       ordsets:from_list(BB_liveout_numbers),
+					       IG,
+					       Target),
+    Newer_ig = set_spill_costs(hipe_spillcost:ref_in_bb(Ref,
+							spill_costs(New_ig)),
+			      New_ig),
+    analyze_bbs(Ls, BBs_in_out_liveness, Newer_ig, CFG, Target).
+
+%%----------------------------------------------------------------------
+%% Function:    analyze_bb_instructions
+%%
+%% Description: Analyzes all instructions that is contained in a basic
+%%              block in reverse order. 
+%%
+%% Parameters:
+%%   Instruction   --  An instruction
+%%   Instructions  --  The remaining instructions
+%%   Live          --  All temporaries that are live at the time.
+%%                     Live is a set of temporary "numbers only".
+%%   IG            --  The interference graph in it's current state
+%%   Target        --  The mopdule containing the target-specific functions
+%%
+%% Returns: 
+%%   Live  --  Temporaries that are live at entery of basic block
+%%              that we analyze.
+%%   IG    --  Updated interference graph.
+%%   Ref   --  Set of temporaries referred to in this bb.
+%%----------------------------------------------------------------------
+
+%% Ref: set of temporaries referred to in this bb
+analyze_bb_instructions([], Live, IG, _) -> {Live, IG, ordsets:new()};
+analyze_bb_instructions([Instruction|Instructions], Live, IG, Target) ->
+  %% Analyze last instruction first.
+  {Live0, IG0, Ref} = analyze_bb_instructions(Instructions, Live, 
+					      IG, Target),
+  %% Check for temporaries that are defined and used in instruction
+  {Def, Use} = Target:def_use(Instruction),
+  %% Convert to register numbers
+  Def_numbers = ordsets:from_list(reg_numbers(Def, Target)),
+  Use_numbers = ordsets:from_list(reg_numbers(Use, Target)),
+  Ref_numbers = ordsets:union(Ref, ordsets:union(Def_numbers, Use_numbers)),
+  %% Increase spill cost on all used temporaries
+  IG1 = set_spill_costs(hipe_spillcost:inc_costs(Use_numbers,
+						 spill_costs(IG0)),
+			IG0),
+  {Live1, IG2} = analyze_move(Instruction, 
+			      Live0, 
+			      Def_numbers, 
+			      Use_numbers, 
+			      IG1, 
+			      Target),
+  %% Adding Def to Live here has the effect of creating edges between
+  %% the defined registers, which is O(N^2) for an instruction that
+  %% clobbers N registers.
+  %%
+  %% Adding Def to Live is redundant when:
+  %% 1. Def is empty, or
+  %% 2. Def is a singleton, or
+  %% 3. Def contains only precoloured registers, or
+  %% 4. Def contains exactly one non-precoloured register, and the
+  %%    remaining ones are all non-allocatable precoloured registers.
+  %%
+  %% HiPE's backends only create multiple-element Def sets
+  %% for CALL instructions, and then all elements are precoloured.
+  %%
+  %% Therefore we can avoid adding Def to Live. The benefit is greatest
+  %% on backends with many physical registers, since CALLs clobber all
+  %% physical registers.
+  Live2 = Live1, % ordsets:union(Live1, Def_numbers),
+  IG3 = interfere(Def_numbers, Live2, IG2, Target),
+  Live3 = ordsets:union(Use_numbers, ordsets:subtract(Live2, Def_numbers)),
+  {Live3, IG3, Ref_numbers}.
+
+%%----------------------------------------------------------------------
+%% Function:    analyze_move
+%%
+%% Description: If a move instructions is discovered, this function is
+%%              called. It is used to remember what move instructions
+%%              a temporary is associated with and all moves that exists
+%%              in the CFG. 
+%%
+%% Parameters:
+%%   Instruction  --  An instruction
+%%   Live         --  All temporaries that are live at the time.
+%%                    Live is a set of temporary "numbers only".
+%%   Def_numbers  --  Temporaries that are defined at this instruction
+%%   Use_numbers  --  Temporaries that are used at this instruction
+%%   IG           --  The interference graph in its current state
+%%   Target       --  The module containing the target-specific functions
+%% Returns:
+%%   Live  --  An updated live set
+%%   IG    --  An updated interference graph
+%%----------------------------------------------------------------------
+
+analyze_move(Instruction, Live, Def_numbers, Use_numbers, IG, Target) ->
+  case Target:is_move(Instruction) of
+    true ->
+      case {Def_numbers, Use_numbers} of
+	{[Dst], [Src]} ->
+	  New_IG = set_ig_moves(hipe_ig_moves:new_move(Dst, Src, ig_moves(IG)), IG),
+	  New_live = ordsets:del_element(Src, Live),
+	  {New_live, New_IG};
+	_ ->
+	  {Live, IG}
+      end;
+    _ ->
+      {Live, IG}
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    interfere
+%%
+%% Description: A number of temporaries that are defined interfere with
+%%              everything in the current live set.
+%%
+%% Parameters:
+%%   Define     --  A Define temporary
+%%   Defines    --  Rest of temporaries.
+%%   Live       --  Current live set
+%%   IG         --  An interference graph
+%%
+%% Returns: 
+%%   An updated interference graph.
+%%----------------------------------------------------------------------
+
+interfere([], _, IG, _) -> IG;
+interfere([Define|Defines], Living, IG, Target) ->
+  New_ig = interfere_with_living(Define, Living, IG, Target),
+  interfere(Defines, Living, New_ig, Target).
+
+%%----------------------------------------------------------------------
+%% Function:    interfere_with_living
+%%
+%% Description: Let one temporary that is in the define set interfere 
+%%              with all live temporaries.
+%%
+%% Parameters:
+%%   Define     --  A Define temporary
+%%   Live       --  Current live set
+%%   Lives      --  Rest of living temporaries.
+%%   IG         --  An interference graph
+%%   Target     --  The module containing the target-specific functions
+%% Returns: 
+%%   An updated interference graph
+%%----------------------------------------------------------------------
+
+interfere_with_living(_, [], IG, _) -> IG;
+interfere_with_living(Define, [Live|Living], IG, Target) ->
+  New_ig = add_edge(Define, Live, IG, Target),
+  interfere_with_living(Define, Living, New_ig, Target).
+
+%%
+%% nodes_are_adjacent(U, V, IG)
+%% returns true if nodes U and V are adjacent in interference graph IG
+%%
+-spec nodes_are_adjacent(integer(), integer(), #igraph{}) -> boolean().
+nodes_are_adjacent(U, V, IG) ->
+  adjset_are_adjacent(U, V, adj_set(IG)).
+
+%%
+%% node_adj_set(Node, IG)
+%% returns list of Node's adjacent nodes in interference graph IG
+%%
+node_adj_list(Node, IG) ->
+  hipe_adj_list:edges(Node, adj_list(IG)).
+
+%%
+%% node_spill_cost(Node, IG)
+%% returns the Node's spill cost
+%%
+node_spill_cost(Node, IG) ->
+  hipe_spillcost:spill_cost(Node, spill_costs(IG)).
+
+%%----------------------------------------------------------------------
+%% Print functions - only used for debugging
+
+-ifdef(DEBUG_PRINTOUTS).
+print_spill_costs(IG) ->
+  ?debug_msg("Spill costs:\n", []),
+  print_spill_costs(number_of_temps(IG), IG).
+
+print_spill_costs(0, _) ->
+  true;
+print_spill_costs(Node, IG) ->
+  NextNode = Node - 1,
+  case hipe_spillcost:nr_of_use(NextNode, spill_costs(IG)) of
+    0 ->
+      ?debug_msg("node ~w not used\n", [NextNode]);
+    _ ->
+      ?debug_msg("node ~w sc ~p\n", [NextNode, node_spill_cost(NextNode, IG)])
+  end,
+  print_spill_costs(NextNode, IG).
+-endif.
+
+%%----------------------------------------------------------------------
+
+get_moves(IG) ->
+  hipe_ig_moves:get_moves(ig_moves(IG)).
+
+%%----------------------------------------------------------------------
+%% Function:    add_edge
+%%
+%% Description: Adds an edge to the adj_set data structure if it is
+%%              not already a part of it and if U is not precoloured
+%%              we add V to its adj_list. If V is not precoloured
+%%              we add U to its adj_list.
+%%
+%% Parameters:
+%%   U          --  A temporary number
+%%   V          --  A temporary number
+%%   Target     --  The module containing the target-specific functions
+%% Returns: 
+%%   An updated interference graph.
+%%----------------------------------------------------------------------
+
+add_edge(U, U, IG, _) -> IG;
+add_edge(U, V, IG, Target) ->
+  case nodes_are_adjacent(U, V, IG) of
+    true ->
+      IG;
+    false ->
+      _ = adjset_add_edge(U, V, adj_set(IG)),
+      Degree = degree(IG),
+      AdjList0 = interfere_if_uncolored(U, V, adj_list(IG), Degree, Target),
+      AdjList1 = interfere_if_uncolored(V, U, AdjList0, Degree, Target),
+      set_adj_list(AdjList1, IG)
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    remove_edge
+%%
+%% Description: Removes an edge to the adj_set data-structure if it's
+%%              a part of it and if U is not precoloured
+%%              we remove V from it's adj_list. If V is not precoloured
+%%              we remove U from it's adj_list.
+%%
+%% Parameters:
+%%   U          --  A temporary number
+%%   V          --  A temporary number
+%%   Target     --  The module containing the target-specific functions
+%% Returns: 
+%%   An updated interference graph.
+%%----------------------------------------------------------------------
+
+remove_edge(U, U, IG, _) -> IG;
+remove_edge(U, V, IG, Target) ->
+  case nodes_are_adjacent(U, V, IG) of
+    false ->
+      IG;
+    true ->
+      _ = adjset_remove_edge(U, V, adj_set(IG)),
+      Degree = degree(IG),
+      AdjList0 = remove_if_uncolored(U, V, adj_list(IG), Degree, Target),
+      AdjList1 = remove_if_uncolored(V, U, AdjList0, Degree, Target),
+      set_adj_list(AdjList1, IG)
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    remove_if_uncolored
+%%
+%% Description:
+%%
+%% Parameters:
+%%   Temporary            --  A temporary that is added to the adjacent 
+%%                             list if it's not precoloured.
+%%   Interfere_temporary  --  Temporary will interfere with 
+%%                             Interfere_temporary if temporary is not
+%%                             precoloured.
+%%   Adj_list             --  An adj_list
+%%   Degree               --  The degree that all nodes currently have
+%%   Target               --  The module containing the target-specific 
+%%                            functions
+%%
+%% Returns: 
+%%   Adj_list  --  An updated adj_list data structure
+%%   Degree    --  An updated degree data structure (via side-effects)
+%%----------------------------------------------------------------------
+
+remove_if_uncolored(Temp, InterfereTemp, Adj_list, Degree, Target) ->
+  case Target:is_precoloured(Temp) of
+    false ->
+      New_adj_list = hipe_adj_list:remove_edge(Temp, InterfereTemp, Adj_list),
+      degree_dec(Temp, Degree),
+      New_adj_list;
+    true ->
+      Adj_list
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    interfere_if_uncolored
+%%
+%% Description: Let a not precoloured temporary interfere with another.
+%%
+%% Parameters:
+%%   Temporary            --  A temporary that is added to the adjacent 
+%%                             list if it's not precoloured.
+%%   Interfere_temporary  --  Temporary will interfere with 
+%%                             Interfere_temporary if temporary is not
+%%                             precoloured.
+%%   Adj_list             --  An adj_list
+%%   Degree               --  The degree that all nodes currently have
+%%   Target               --  The module containing the target-specific 
+%%                            functions
+%%
+%% Returns: 
+%%   Adj_list  --  An updated adj_list data structure
+%%   Degree    --  An updated degree data structure (via side-effects)
+%%----------------------------------------------------------------------
+
+interfere_if_uncolored(Temp, InterfereTemp, Adj_list, Degree, Target) ->
+  case Target:is_precoloured(Temp) of
+    false ->
+      New_adj_list = hipe_adj_list:add_edge(Temp, InterfereTemp, Adj_list),
+      degree_inc(Temp, Degree),
+      New_adj_list;
+    true ->
+      Adj_list
+  end.
+
+%%----------------------------------------------------------------------
+%% Function:    reg_numbers
+%%
+%% Description: Converts a list of tuple with {something, reg_number}
+%%              to a list of register numbers.
+%%
+%% Parameters:
+%%   TRs     -- A list of temporary registers
+%%   Target  -- The module containing the target-specific functions
+%% Returns: 
+%%   A list of register numbers.
+%%----------------------------------------------------------------------
+
+reg_numbers(Regs, Target) -> 
+  [Target:reg_nr(X) || X <- Regs].
+
+%%---------------------------------------------------------------------
+%% Print functions - only used for debugging
+
+-ifdef(DEBUG_PRINTOUTS).
+print_degrees(IG) ->
+  ?debug_msg("The nodes degrees:\n", []),
+  print_node_degree(number_of_temps(IG), IG).
+
+print_node_degree(0, _) ->
+  true;
+print_node_degree(Node, IG) ->
+  NextNode = Node - 1,
+  ?debug_msg("node ~w ~w\n", [NextNode, get_node_degree(NextNode, IG)]),
+  print_node_degree(NextNode, IG).
+-endif.
+
+%%----------------------------------------------------------------------
+
+get_node_degree(Node, IG) ->
+  degree_get(Node, degree(IG)).
+
+dec_node_degree(Node, IG) ->
+  degree_dec(Node, degree(IG)),
+  IG.
+
+is_trivially_colourable(Node, K, IG) ->
+  degree_is_trivially_colourable(Node, K, degree(IG)).