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