hipe_graph_coloring_regalloc.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 802 行 · 第 1/2 页

	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(Rs, Target) ->
  Regs = 
    case Target of
      hipe_sparc_specific ->
	hipe_sparc:keep_registers(Rs);
      _ ->
	Rs
    end,
  [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} = precolor0(Xs, Cols, Target),
  ?report("    yielded ~p~n", [Cs]),
  {Cs,NewCol}.

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