%% -*- erlang-indent-level: 2 -*-
%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 2001-2011. All Rights Reserved.
%%
%% The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved online at http://www.erlang.org/.
%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%%
%% %CopyrightEnd%
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%@doc
%% GRAPH COLORING REGISTER ALLOCATOR
%%
%% A simple graph coloring register allocator:
%%
%% - build interference graph + estimate spill costs
%% - simplify graph (push on stack + spill)
%% - select colors
%%
%% Emits a coloring: a list of {TempName,Location}
%% where Location is {reg,N} or {spill,M}
%% and {reg,N} denotes some register N
%% and {spill,M} denotes the Mth spilled node
%% You have to figure out how to rewrite the code yourself.
%%
%% This version uses vectors rather than hash tables, and uses
%% faster algorithms since all vars are known at the start.
%% The result should be considerably quicker than earlier versions.
%%
%% Deficiencies:
%% - no renaming (to reduce unnecessary register pressure)
%% - spill costs are naive (should use better; e.g., exec.estimates)
%% - no biased coloring (which coalesces moves)
%% - no live range splitting (possibly not critical)
%%
%% *** NOTE ***
%% Uses apply for target specific functions, takes the module name as
%% argument. This target specific module should implement all target
%% specific functions, see the end of the file.
%%
-module(hipe_graph_coloring_regalloc).
-export([regalloc/5]).
%%-ifndef(DO_ASSERT).
%%-define(DO_ASSERT, true).
%%-endif.
%%-ifndef(DEBUG).
%%-define(DEBUG,0).
%%-endif.
-include("../main/hipe.hrl").
%% Define these as 'ok' or 'report(X,Y)' depending on how much output you want.
-define(report0(X,Y), ?IF_DEBUG_LEVEL(0,?msg(X, Y),ok)).
-define(report(X,Y), ?IF_DEBUG_LEVEL(1,?msg(X, Y),ok)).
-define(report2(X,Y), ?IF_DEBUG_LEVEL(2,?msg(X, Y),ok)).
-define(report3(X,Y), ?IF_DEBUG_LEVEL(3,?msg(X, Y),ok)).
%% Given CFG and number of colors K, produce a coloring list
%% of items {reg,N} (0 =< N =< K) and {spill,M}, where M is
%% an index denoting 'a location'.
%% (You might use it as a stack index, perhaps.)
%%
%% You can in principle delete check_coloring/2; it merely checks
%% that the coloring agrees with the interference graph (that is, that
%% no neighbors have the same register or spill location).
%% @spec regalloc(#cfg{}, non_neg_fixnum(), non_neg_fixnum(), atom(), list()) -> {, non_neg_fixnum()}
regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
PhysRegs = Target:allocatable(),
?report2("building IG~n", []),
{IG, Spill} = build_ig(CFG, Target),
%% check_ig(IG),
?report3("graph: ~p~nphysical regs: ~p~n", [list_ig(IG), PhysRegs]),
%% These nodes *can't* be allocated to registers.
NotAllocatable = [Target:reg_nr(X) || X <- Target:non_alloc(CFG)],
%% i.e. Arguments on x86
?report2("Nonalloc ~w~n", [NotAllocatable]),
{Cols, NewSpillIndex} =
color(IG, Spill,
ordsets:from_list(PhysRegs),
SpillIndex,
SpillLimit,
Target:number_of_temporaries(CFG),
Target, NotAllocatable),
Coloring = [{X, {reg, X}} || X <- NotAllocatable] ++ Cols,
?ASSERT(check_coloring(Coloring, IG, Target)),
{Coloring, NewSpillIndex}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% *** BUILD THE INTERFERENCE GRAPH ***
%%
%% Returns {Interference_graph, Spill_cost_dictionary}
%%
build_ig(CFG, Target) ->
try build_ig0(CFG, Target)
catch error:Rsn -> exit({?MODULE, build_ig, Rsn})
end.
build_ig0(CFG, Target) ->
Live = Target:analyze(CFG),
NumN = Target:number_of_temporaries(CFG), % poss. N-1?
{IG, Spill} = build_ig_bbs(Target:labels(CFG),
CFG,
Live,
empty_ig(NumN),
empty_spill(NumN),
Target),
{normalize_ig(IG), Spill}.
build_ig_bbs([], _CFG, _Live, IG, Spill, _Target) ->
{IG, Spill};
build_ig_bbs([L|Ls], CFG, Live, IG, Spill, Target) ->
Xs = bb(CFG, L, Target),
{_, NewIG, NewSpill} =
build_ig_bb(Xs, liveout(Live, L, Target), IG, Spill, Target),
build_ig_bbs(Ls, CFG, Live, NewIG, NewSpill, Target).
build_ig_bb([], LiveOut, IG, Spill, _Target) ->
{LiveOut, IG, Spill};
build_ig_bb([X|Xs], LiveOut, IG, Spill, Target) ->
{Live,NewIG,NewSpill} = build_ig_bb(Xs, LiveOut, IG, Spill, Target),
build_ig_instr(X, Live, NewIG, NewSpill, Target).
%% Note: We could add move-related arcs here as well.
%%
%% Note: Ideally, we would like to add all registers to the IG
%% at once rather than doing 'add_nodes' for each instruction.
%% (This is costly, since nodes that already are present are checked!)
build_ig_instr(X, Live, IG, Spill, Target) ->
{Def, Use} = def_use(X, Target),
?report3("Live ~w\n~w : Def: ~w Use ~w\n", [Live, X, Def,Use]),
DefList = ordsets:to_list(Def),
NewSpill = inc_spill_costs(DefList,
inc_spill_costs(ordsets:to_list(Use), Spill)),
NewIG = interference_arcs(DefList, ordsets:to_list(Live), IG),
NewLive = ordsets:union(Use, ordsets:subtract(Live, Def)),
{NewLive, NewIG, NewSpill}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
interference_arcs([], _Live, IG) ->
IG;
interference_arcs([X|Xs], Live, IG) ->
interference_arcs(Xs, Live, i_arcs(X, Live, IG)).
i_arcs(_X, [], IG) ->
IG;
i_arcs(X, [Y|Ys], IG) ->
i_arcs(X, Ys, add_edge(X,Y, IG)).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
inc_spill_costs([], Spill) -> Spill;
inc_spill_costs([X|Xs], Spill) ->
inc_spill_costs(Xs, inc_spill_cost(X, Spill)).
inc_spill_cost(X, Spill) ->
set_spill_cost(X, get_spill_cost(X, Spill)+1, Spill).
get_spill_cost(X, Spill) ->
spill_cost_lookup(X, Spill).
set_spill_cost(X, N, Spill) ->
spill_cost_update(X, N, Spill).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% *** COLORING ***
%%
%% Coloring is done straightforwardly:
%% - find the low-degree nodes, put them in low
%% - while low non-empty:
%% * remove x from low
%% * push x on stack
%% * decrement degree of neighbors of x
%% * for each neighbor y of low degree, put y on low
%% - when low empty:
%% - if graph empty, return stack
%% - otherwise
%% * select a node z to spill
%% * push z on stack
%% * decrement degree of neighbors of z
%% * add low-degree neighbors of z to low
%% * restart the while-loop above
color(IG, Spill, PhysRegs, SpillIx, SpillLimit, NumNodes, Target, NotAllocatable) ->
try color_0(IG, Spill, PhysRegs, SpillIx, SpillLimit,
NumNodes, Target, NotAllocatable)
catch
error:Rsn ->
?error_msg("Coloring failed with ~p~n", [Rsn]),
?EXIT(Rsn)
end.
color_0(IG, Spill, PhysRegs, SpillIx, SpillLimit, NumNodes, Target,
NotAllocatable) ->
?report("simplification of IG~n", []),
K = ordsets:size(PhysRegs),
Nodes = list_ig(IG),
Low = low_degree_nodes(Nodes, K, NotAllocatable),
%% Any nodes above the spillimit must be colored first...
MustNotSpill =
if NumNodes > SpillLimit+1 ->
sort_on_degree(lists:seq(SpillLimit+1,NumNodes-1) -- Low,IG);
true -> []
end,
?report(" starting with low degree nodes ~p~n",[Low]),
EmptyStk = [],
Precolored = Target:all_precoloured(),
{Stk, NewSpillIx} =
simplify(Low, NumNodes, Precolored,
IG, Spill, K, SpillIx, EmptyStk,
SpillLimit, Target, NotAllocatable, MustNotSpill),
?report("selecting colors~n",[]),
{select(Stk, Precolored, IG, K, PhysRegs, NumNodes, Target),
NewSpillIx}.
sort_on_degree(Nodes, IG) ->
[ Node3 || {_,Node3} <-
lists:sort([{degree(Info),Node2} ||
{Info,Node2} <- [{hipe_vectors:get(IG, Node),
Node} || Node <-
Nodes]])].
%%%%%%%%%%%%%%%%%%%%
%%
%% Simplification: push all easily colored nodes on a stack;
%% when the list of easy nodes becomes empty, see if graph is
%% empty as well. If it is not, spill a node and continue.
%% If it is empty, return the stack.
%%
%% Notes:
%% - We keep the set of visited nodes around for spill purposes
%% (visited nodes are not considered for spilling)
%%
%% - At present, nodes can be pushed onto the stack even if they
%% already are on the stack. This can be fixed by another 'Vis'
%% dictionary that keeps track of what is on the stack.
%% Currently, we just skip already colored nodes.
%%
%% - Arguments:
%% Low: low-degree nodes (ready to color)
%% NumNodes: number of remaining nodes in graph
%% IG: interference graph
%% Spill: spill costs of nodes
%% K: number of colors
%% Ix: next spill index
%% Stk: stack of already simplified nodes
%%
%% Physical registers are marked as 'visited' prior to simplify.
%% This has the following effect:
%% - they are not considered for spilling
%% - they are not pushed on the stack
%% - since we do NOT decrement degrees of surrounding vars, the
%% non-physreg variables must still take them into account.
simplify(Low, NumNodes, PreC, IG, Spill, K, Ix, Stk, SpillLimit,
Target, NotAllocatable, MustNotSpill) ->
Vis = visit_all(PreC, none_visited(NumNodes)),
Vis1 = visit_all(NotAllocatable, Vis),
ActualNumNodes = (NumNodes-length(PreC))-length(NotAllocatable),
%% Make sure that the registers that must not be spilled
%% get a degree less than K by spilling other regs.
{Stk2, Ix2, Vis2, Low2} =
handle_non_spill(MustNotSpill, IG, Spill, K, Ix, Stk, Vis1, Low,
SpillLimit, Target),
simplify_ig(Low2, ActualNumNodes-length(Stk2), IG, Spill, K, Ix2, Stk2, Vis2,
SpillLimit, Target).
handle_non_spill([], _IG, _Spill, _K, Ix, Stk, Vis, Low, _SpillLimit, _Target) ->
{Stk, Ix, Vis, Low};
handle_non_spill([X|Xs] = L, IG, Spill, K, Ix, Stk, Vis, Low, SpillLimit, Target) ->
Info = hipe_vectors:get(IG, X),
Degree = degree(Info),
?report("Can't Spill ~w with degree ~w\n", [X,Degree]),
if Degree > K ->
?report(" *** spill required (N<~w)***~n", [SpillLimit]),
{Y, NewLow, NewIG} = spill(IG, Vis, Spill, K, SpillLimit, Target),
NewVis = visit(Y,Vis),
{NewStk, NewIx} = push_spill_node(Y, Ix, Stk),
?report(" node ~w spilled~n", [Y]),
handle_non_spill(L, NewIG, Spill, K, NewIx, NewStk, NewVis,
Low ++ NewLow, SpillLimit, Target);
true ->
{NewLow, NewIG} = decrement_neighbors(X, Low, IG, Vis, K),
?report(" node ~w pushed\n(~w now ready)~n", [X,NewLow]),
NewStk = push_colored(X, Stk),
handle_non_spill(Xs, NewIG, Spill, K, Ix, NewStk, visit(X,Vis),
NewLow, SpillLimit, Target)
end.
simplify_ig([], 0, _IG, _Spill, _K, Ix, Stk, _Vis, _SpillLimit, _Target) ->
{Stk, Ix};
simplify_ig([], N, IG, Spill, K, Ix, Stk, Vis, SpillLimit, Target)
when N > 0 ->
?report3("N: ~w Stk: ~w N+Stk ~w\n", [N,length(Stk),N+length(Stk)]),
?report(" *** spill required (N<~w)***~n", [SpillLimit]),
{X, Low, NewIG} = spill(IG, Vis, Spill, K, SpillLimit, Target),
NewVis = visit(X,Vis),
{NewStk, NewIx} = push_spill_node(X, Ix, Stk),
?report(" node ~w spilled\n(~w now ready)~n", [X, Low]),
simplify_ig(Low, N-1, NewIG, Spill, K, NewIx, NewStk, NewVis,
SpillLimit, Target);
simplify_ig([X|Xs], N, IG, Spill, K, Ix, Stk, Vis, SpillLimit, Target) ->
?report3("N: ~w Stk: ~w N+Stk ~w\n", [N,length(Stk),N+length(Stk)]),
case is_visited(X,Vis) of
true ->
?report(" node ~p already visited~n",[X]),
simplify_ig(Xs, N, IG, Spill, K, Ix, Stk, Vis, SpillLimit, Target);
false ->
?report("Stack ~w\n", [Stk]),
{NewLow, NewIG} = decrement_neighbors(X, Xs, IG, Vis, K),
?report(" node ~w pushed\n(~w now ready)~n", [X,NewLow]),
NewStk = push_colored(X, Stk),
simplify_ig(NewLow, N-1, NewIG, Spill, K, Ix, NewStk, visit(X,Vis),
SpillLimit, Target)
end.
%% Returns { NowLowDegreeNeighbors, NewIG }
decrement_neighbors(X, Xs, IG, Vis, K) ->
Ns = unvisited_neighbors(X, Vis, IG),
?report(" node ~p has neighbors ~w\n(unvisited ~p)~n",
[X, neighbors(X, IG), Ns]),
decrement_each(Ns, Xs, IG, Vis, K).
%% For each node, decrement its degree and check if it is now
%% a low-degree node. In that case, add it to the 'low list'.
decrement_each([], Low, IG, _Vis, _K) ->
{Low, IG};
decrement_each([N|Ns], OldLow, IG, Vis, K) ->
{Low, CurrIG} = Res = decrement_each(Ns, OldLow, IG, Vis, K),
case is_visited(N, Vis) of
true ->
Res;
false ->
{D, NewIG} = decrement_degree(N, CurrIG),
if
D =:= K-1 ->
{[N|Low], NewIG};
true ->
{Low, NewIG}
end
end.
%%%%%%%%%%%%%%%%%%%%
%%
%% The spill cost of a node is:
%% est_spill_cost / current_degree
%%
%% For all unvisited nodes, compute spill cost and select the minimum.
%% This node is chosen to be spilled. Then decrement the degree of its
%% neighbors, and return those of low degree.
%%
%% Notes:
%% - A better method for computing spill costs is to just keep the
%% minimum cost node. But for debugging purposes, we compute a list
%% of {node,spillcost} pairs and select the minimum.
%%
%% Returns:
%% {Spilled_node, Low_degree_neighbors, New_interference_graph}
spill(IG, Vis, Spill, K, SpillLimit, Target) ->
Ns = list_ig(IG),
Costs = spill_costs(Ns, IG, Vis, Spill, SpillLimit, Target),
?report3("spill costs are ~p~n", [Costs]),
ActualCosts = lists:sort(Costs),
?report3("actual costs are ~p~n", [ActualCosts]),
case ActualCosts of
[] ->
?error_msg("There is no node to spill", []),
?EXIT('no node to spill');
[{_Cost,N}|_] ->
{Low, NewIG} = decrement_neighbors(N, [], IG, Vis, K),
%% ?report("spilled node ~p at cost ~p (~p now ready)~n", [N,Cost,Low]),
{N, Low, NewIG}
end.
spill_costs([], _IG, _Vis, _Spill, _SpillLimit, _Target) ->
[];
spill_costs([{N,Info}|Ns], IG, Vis, Spill, SpillLimit, Target) ->
case degree(Info) of
0 -> spill_costs(Ns,IG,Vis,Spill, SpillLimit, Target);
Deg ->
case is_visited(N,Vis) of
true ->
spill_costs(Ns,IG,Vis,Spill, SpillLimit, Target);
_ ->
case Target:is_fixed(N) of
true ->
spill_costs(Ns, IG, Vis, Spill, SpillLimit, Target);
false ->
if N > SpillLimit ->
spill_costs(Ns, IG, Vis, Spill, SpillLimit, Target);
true ->
[{spill_cost_of(N,Spill)/Deg,N} |
spill_costs(Ns,IG, Vis, Spill, SpillLimit, Target)]
end
end
end
end.
%%%%%%%%%%%%%%%%%%%%
%%
%% Returns a list of {Name,Location}, where Location is
%% either {spill,M} or {reg,R}
%%
%% Note: we use pessimistic coloring here.
%% - we could use optimistic coloring: for spilled node, check if there is
%% an unused color among the neighbors and choose that.
select(Stk, PreC, IG, K, PhysRegs, NumNodes, Target) ->
%% NumNodes = length(Stk)+length(PreC),
{PhysColors, Cols} = precolor(PreC, none_colored(NumNodes), Target),
?report("precoloring has yielded ~p~n",[list_coloring(Cols)]),
PhysColors ++ select_colors(Stk, IG, Cols, PhysRegs, K).
select_colors([], _IG, _Cols, _PhysRegs, _K) ->
?report("all nodes colored~n",[]),
[];
select_colors([{X,colorable}|Xs], IG, Cols, PhysRegs, K) ->
?report("color of ~p\n",[X]),
{Reg,NewCols} = select_color(X, IG, Cols, PhysRegs),
?report("~p~n",[Reg]),
[{X,{reg,Reg}} | select_colors(Xs, IG, NewCols, PhysRegs, K)];
%%select_colors([{X,{spill,M}}|Xs], IG, Cols, PhysRegs, K) ->
%% ?report('spilled: ~p~n',[X]),
%% %% Check if optimistic coloring could have found a color
%% case catch select_color(X,IG,Cols,K) of
%% {'EXIT',_} -> % no color possible
%% ?report('(no optimistic color)~n',[]),
%% [{X,{spill,M}}|select_colors(Xs, IG, Cols, PhysRegs, K)];
%% {Reg,NewCols} ->
%% ?report('(optimistic color: ~p)~n',[Reg]),
%% [{X,{reg,Reg}}|select_colors(Xs, IG, Cols, PhysRegs, K)]
%% end.
%% Old code / pessimistic coloring:
select_colors([{X,{spill,M}}|Xs], IG, Cols, PhysRegs, K) ->
?report("spilled: ~p~n",[X]),
%% Check if optimistic coloring could have found a color
%% case catch select_color(X,IG,Cols,K) of
%% {'EXIT',_} -> % no color possible
%% ?report('(no optimistic color)~n',[]);
%% {Reg,NewCols} ->
%% ?report('(optimistic color: ~p)~n',[Reg])
%% end,
[{X,{spill,M}} | select_colors(Xs, IG, Cols, PhysRegs, K)].
select_color(X, IG, Cols, PhysRegs) ->
UsedColors = get_colors(neighbors(X, IG), Cols),
Reg = select_unused_color(UsedColors, PhysRegs),
{Reg, set_color(X, Reg, Cols)}.
%%%%%%%%%%%%%%%%%%%%
get_colors([], _Cols) -> [];
get_colors([X|Xs], Cols) ->
case color_of(X, Cols) of
uncolored ->
get_colors(Xs, Cols);
{color,R} ->
[R|get_colors(Xs, Cols)]
end.
select_unused_color(UsedColors, PhysRegs) ->
Summary = ordsets:from_list(UsedColors),
AvailRegs = ordsets:to_list(ordsets:subtract(PhysRegs, Summary)),
hd(AvailRegs).
%% select_avail_reg(AvailRegs).
%% We choose the register to use randomly from the set of available
%% registers.
%%
%% Note: Another way of doing it is LRU-order:
%% - Have an LRU-queue of register names; when coloring, try the colors in that
%% order (some may be occupied).
%% - When a color has been selected, put it at the end of the LRU.
%% select_avail_reg(Regs) ->
%% case get(seeded) of
%% undefined ->
%% random:seed(),
%% put(seeded,true);
%% true ->
%% ok
%% end,
%% NReg = length(Regs),
%% RegNo = random:uniform(NReg),
%% lists:nth(RegNo, Regs).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
push_spill_node(X, M, Stk) ->
{[{X,{spill,M}}|Stk], M+1}.
push_colored(X, Stk) ->
[{X, colorable} | Stk].
%%%%%%%%%%%%%%%%%%%%
low_degree_nodes([], _K, _NotAllocatable) -> [];
low_degree_nodes([{N,Info}|Xs], K, NotAllocatable) ->
case lists:member(N, NotAllocatable) of
true ->
low_degree_nodes(Xs,K, NotAllocatable);
false ->
?report0("node ~p has degree ~p: ~w~n",[N,degree(Info),neighbors(Info)]),
Deg = degree(Info),
if
Deg < K ->
[N|low_degree_nodes(Xs, K, NotAllocatable)];
true ->
low_degree_nodes(Xs, K, NotAllocatable)
end
end.
%%%%%%%%%%%%%%%%%%%%
unvisited_neighbors(X, Vis, IG) ->
ordsets:from_list(unvisited(neighbors(X,IG), Vis)).
unvisited([], _Vis) -> [];
unvisited([X|Xs], Vis) ->
case is_visited(X, Vis) of
true ->
unvisited(Xs, Vis);
false ->
[X|unvisited(Xs, Vis)]
end.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% *** ABSTRACT DATATYPES ***
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% The ig datatype:
%%
%% Note: if we know the number of temps used, we can use a VECTOR
%% instead, which will speed up things.
%%
%% Note: later on, we may wish to add 'move-related' support.
-record(ig_info, {neighbors=[], degree=0 :: integer()}).
empty_ig(NumNodes) ->
hipe_vectors:new(NumNodes, #ig_info{neighbors=[], degree=0}).
degree(Info) ->
Info#ig_info.degree.
neighbors(Info) ->
Info#ig_info.neighbors.
add_edge(X, X, IG) -> IG;
add_edge(X, Y, IG) ->
add_arc(X, Y, add_arc(Y, X, IG)).
add_arc(X, Y, IG) ->
Info = hipe_vectors:get(IG, X),
Old = neighbors(Info),
New = Info#ig_info{neighbors=[Y|Old]},
hipe_vectors:set(IG, X, New).
normalize_ig(IG) ->
Size = hipe_vectors:size(IG),
normalize_ig(Size-1, IG).
normalize_ig(-1, IG) ->
IG;
normalize_ig(I, IG) ->
Info = hipe_vectors:get(IG, I),
N = ordsets:from_list(neighbors(Info)),
NewIG = hipe_vectors:set(IG, I, Info#ig_info{neighbors=N, degree=length(N)}),
normalize_ig(I-1, NewIG).
%%degree(X, IG) ->
%% Info = hipe_vectors:get(IG, X),
%% Info#ig_info.degree.
neighbors(X, IG) ->
Info = hipe_vectors:get(IG, X),
Info#ig_info.neighbors.
decrement_degree(X, IG) ->
Info = hipe_vectors:get(IG, X),
Degree = degree(Info),
NewDegree = Degree-1,
NewInfo = Info#ig_info{degree=NewDegree},
{NewDegree, hipe_vectors:set(IG,X,NewInfo)}.
list_ig(IG) ->
hipe_vectors:list(IG).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% The spill cost datatype:
%%
%% Note: if we know the number of temps used, we can use a VECTOR
%% instead, which will speed up things.
empty_spill(NumNodes) ->
hipe_vectors:new(NumNodes, 0).
spill_cost_of(X, Spill) ->
hipe_vectors:get(Spill, X).
spill_cost_lookup(X, Spill) ->
spill_cost_of(X, Spill).
spill_cost_update(X, N, Spill) ->
hipe_vectors:set(Spill, X, N).
%%list_spill_costs(Spill) ->
%% hipe_vectors:list(Spill).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% The coloring datatype:
none_colored(NumNodes) ->
hipe_vectors:new(NumNodes,uncolored).
color_of(X,Cols) ->
hipe_vectors:get(Cols,X).
set_color(X,R,Cols) ->
hipe_vectors:set(Cols,X,{color,R}).
-ifdef(DEBUG).
list_coloring(Cols) ->
hipe_vectors:list(Cols).
-endif.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Note: there might be a slight gain in separating the two versions
%% of visit/2 and visited/2. (So that {var,X} selects X and calls the
%% integer version.
none_visited(NumNodes) ->
hipe_vectors:new(NumNodes, false).
visit(X,Vis) ->
hipe_vectors:set(Vis, X, true).
is_visited(X,Vis) ->
hipe_vectors:get(Vis, X).
visit_all([], Vis) -> Vis;
visit_all([X|Xs], Vis) ->
visit_all(Xs, visit(X, Vis)).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Check that all arcs in IG are bidirectional + degree is correct
%% check_ig(IG) ->
%% check_ig(list_ig(IG),IG).
%% check_ig([],IG) ->
%% ok;
%% check_ig([{N,Info}|Xs],IG) ->
%% Ns = neighbors(Info),
%% NumNs = length(Ns),
%% D = degree(Info),
%% if
%% D =:= NumNs ->
%% ok;
%% true ->
%% ?WARNING_MSG('node ~p has degree ~p but ~p neighbors~n',[N,D,NumNs])
%% end,
%% check_neighbors(N,Ns,IG),
%% check_ig(Xs,IG).
%% check_neighbors(N,[],IG) ->
%% ok;
%% check_neighbors(N,[M|Ms],IG) ->
%% Ns = neighbors(M,IG),
%% case member(N,Ns) of
%% true ->
%% ok;
%% true ->
%% ?WARNING_MSG('node ~p should have ~p as neighbor (has ~p)~n',[M,N,Ns])
%% end,
%% check_neighbors(N,Ms,IG).
-ifdef(DO_ASSERT).
%%%%%%%%%%%%%%%%%%%%
%% Check that the coloring is correct (if the IG is correct):
%%
check_coloring(Coloring, IG, Target) ->
?report0("checking coloring ~p~n",[Coloring]),
check_cols(list_ig(IG),init_coloring(Coloring, Target)).
init_coloring(Xs, Target) ->
hipe_temp_map:cols2tuple(Xs, Target).
check_color_of(X, Cols) ->
%% if
%% is_precoloured(X) ->
%% phys_reg_color(X,Cols);
%% true ->
case hipe_temp_map:find(X, Cols) of
unknown ->
?WARNING_MSG("node ~p: color not found~n", [X]),
uncolored;
C ->
C
end.
check_cols([], Cols) ->
?report("coloring valid~n",[]),
true;
check_cols([{X,Info}|Xs], Cols) ->
Cs = [{N, check_color_of(N, Cols)} || N <- neighbors(Info)],
C = check_color_of(X, Cols),
case valid_coloring(X, C, Cs) of
yes ->
check_cols(Xs, Cols);
{no,Invalids} ->
?WARNING_MSG("node ~p has same color (~p) as ~p~n", [X,C,Invalids]),
check_cols(Xs, Cols)
end.
valid_coloring(X, C, []) ->
yes;
valid_coloring(X, C, [{Y,C}|Ys]) ->
case valid_coloring(X, C, Ys) of
yes -> {no, [Y]};
{no,Zs} -> {no, [Y|Zs]}
end;
valid_coloring(X, C, [_|Ys]) ->
valid_coloring(X, C, Ys).
-endif.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% *** INTERFACES TO OTHER MODULES ***
%%
liveout(CFG, L, Target) ->
ordsets:from_list(reg_names(Target:liveout(CFG, L), Target)).
bb(CFG, L, Target) ->
hipe_bb:code(Target:bb(CFG, L)).
def_use(X, Target) ->
{ordsets:from_list(reg_names(Target:defines(X), Target)),
ordsets:from_list(reg_names(Target:uses(X), Target))}.
reg_names(Regs, Target) ->
[Target:reg_nr(X) || X <- Regs].
%%
%% Precoloring: use this version when a proper implementation of
%% physical_name(X) is available!
%%
precolor(Xs, Cols, Target) ->
?report("precoloring ~p~n", [Xs]),
{_Cs, _NewCol} = Res = precolor0(Xs, Cols, Target),
?report(" yielded ~p~n", [_Cs]),
Res.
precolor0([], Cols, _Target) ->
{[], Cols};
precolor0([R|Rs], Cols, Target) ->
{Cs, Cols1} = precolor0(Rs, Cols, Target),
{[{R, {reg, physical_name(R, Target)}}|Cs],
set_color(R, physical_name(R, Target), Cols1)}.
physical_name(X, Target) ->
Target:physical_name(X).
