diff options
Diffstat (limited to 'lib/hipe/regalloc/hipe_ig.erl')
| -rw-r--r-- | lib/hipe/regalloc/hipe_ig.erl | 776 |
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)). |