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