%% -*- erlang-indent-level: 2 -*-
%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
%%
%% http://www.apache.org/licenses/LICENSE-2.0
%%
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
%%
%%----------------------------------------------------------------------
%% 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/4,
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/5,
remove_edge/5,
%% 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").
-type target_context() :: any().
-type target() :: {TargetMod :: module(), TargetContext :: target_context()}.
%%----------------------------------------------------------------------
-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, {TargetMod, TargetCtx}) ->
Degree = hipe_bifs:array(No_temporaries, 0),
K = length(TargetMod:allocatable(TargetCtx)),
Inf = K + No_temporaries,
precoloured_to_inf_degree(TargetMod:all_precoloured(TargetCtx), 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(), target()) -> #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
%% TargetMod -- The module that contains the target-specific functions
%% TargetCtx -- Context data to pass to TargetMod
%%
%% Returns:
%% An interference graph for the given CFG.
%%----------------------------------------------------------------------
-spec build(#cfg{}, Liveness::_, module(), target_context()) -> #igraph{}.
build(CFG, BBs_in_out_liveness, TargetMod, TargetCtx) ->
Target = {TargetMod, TargetCtx},
Labels = TargetMod:labels(CFG, TargetCtx),
%% How many temporaries exist?
NumTemps = TargetMod:number_of_temporaries(CFG, TargetCtx),
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, along with its context data
%%
%% 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 = bb(CFG, L, Target),
% Get basic block code
BB_code = hipe_bb:code(BB),
% Temporaries that are live out from this basic block, only numbers
BB_liveout_numbers = liveout(BBs_in_out_liveness, L, 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,
%% along with its context data.
%%
%% 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} = def_use(Instruction, Target),
%% 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, along
%% with its context data
%% Returns:
%% Live -- An updated live set
%% IG -- An updated interference graph
%%----------------------------------------------------------------------
analyze_move(Instruction, Live, Def_numbers, Use_numbers, IG, Target) ->
case is_move(Instruction,Target) 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, along
%% with its context data.
%% 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
%% TargetMod -- The module containing the target-specific functions.
%% TargetCtx -- Context data to pass to TargetMod
%% Returns:
%% An updated interference graph.
%%----------------------------------------------------------------------
add_edge(U, V, IG, TargetMod, TargetCtx) ->
add_edge(U, V, IG, {TargetMod, TargetCtx}).
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
%% TargetMod -- The module containing the target-specific functions.
%% TargetCtx -- Context data for TargetMod.
%% Returns:
%% An updated interference graph.
%%----------------------------------------------------------------------
remove_edge(U, V, IG, TargetMod, TargetCtx) ->
remove_edge(U, V, IG, {TargetMod, TargetCtx}).
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, along with its context data.
%%
%% 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 is_precoloured(Temp,Target) 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, along with its context data.
%%
%% 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 is_precoloured(Temp, Target) 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, along with
%% its context data.
%% Returns:
%% A list of register numbers.
%%----------------------------------------------------------------------
reg_numbers(Regs, {TgtMod, TgtCtx}) ->
[TgtMod:reg_nr(X,TgtCtx) || 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)).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Interface to external functions.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
bb(CFG, L, {TgtMod,TgtCtx}) ->
TgtMod:bb(CFG,L,TgtCtx).
def_use(Instruction, {TgtMod,TgtCtx}) ->
TgtMod:def_use(Instruction, TgtCtx).
is_move(Instruction, {TgtMod,TgtCtx}) ->
TgtMod:is_move(Instruction, TgtCtx).
is_precoloured(R, {TgtMod,TgtCtx}) ->
TgtMod:is_precoloured(R,TgtCtx).
liveout(Liveness,L, Target={TgtMod,TgtCtx}) ->
reg_numbers(TgtMod:liveout(Liveness,L,TgtCtx), Target).
