hipe_graph_coloring_regalloc.erl

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

%% -*- erlang-indent-level: 2 -*-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%@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) ->
  case catch build_ig0(CFG, Target) of
    {'EXIT',Rsn} ->
      exit({?MODULE, build_ig, Rsn});
    Else ->
      Else
  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) ->
   case catch color_0(IG, Spill, PhysRegs, SpillIx, SpillLimit,
		      NumNodes, Target, NotAllocatable) of
      {'EXIT',Rsn} ->
	 ?error_msg("Coloring failed with ~p~n", [Rsn]),
	 ?EXIT(Rsn);
      Else ->
	 Else
   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], 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([X|Xs], 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} = decrement_each(Ns, OldLow, IG, Vis, K),
  case is_visited(N, Vis) of
    true ->
      {Low, CurrIG};
    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