hipe_coalescing_regalloc.erl

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

%% -*- erlang-indent-level: 2 -*-
%%-----------------------------------------------------------------------
%% File    : hipe_coalescing_regalloc.erl
%% Authors : Andreas Wallin <[e-mail]>
%%           Thorild Sel閚 <d95ths@.it.uu.se>
%%           Ingemar 舃erg <[e-mail]>
%% Purpose : Play paintball with registers on a target machine.  We win
%%           if they are all colored.  This is an iterated coalescing
%%           register allocator.
%% Created : 4 Mar 2000
%%-----------------------------------------------------------------------

-module(hipe_coalescing_regalloc).
-export([regalloc/5]).

%%-ifndef(DEBUG).
%%-define(DEBUG,true).
%%-endif.
-include("../main/hipe.hrl").

%%-----------------------------------------------------------------------
%% Function:    regalloc
%%
%% Description: Creates a K coloring for a function.
%% Parameters:
%%   CFG         -- A control flow graph
%%   SpillIndex  -- Last index of spill variable
%%   SpillLimit  -- Temporaries with numbers higher than this have
%%                  infinite 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
%%-----------------------------------------------------------------------
regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
  %% Build interference graph
  ?debug_msg("Build IG\n",[]),
  IG = hipe_ig:build(CFG, Target),
  %% io:format("IG: ~p\n",[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),

  %% Add registers with their own coloring
  ?debug_msg("Moves\n",[]),
  Move_sets = hipe_moves:new(IG),

  ?debug_msg("Build Worklist\n",[]),
  Worklists = 
    hipe_reg_worklists:new(IG, Target, CFG, Move_sets, K, No_temporaries),
  Alias = initAlias(No_temporaries),

  ?debug_msg("Do coloring\n~p~n",[Worklists]),
  {_IG0, Worklists0, _Moves0, Alias0} = 
    do_coloring(IG, Worklists, Move_sets, Alias, K, SpillLimit, Target),
  %% io:format("SelStk0 ~w\n",[SelStk0]),
  ?debug_msg("Init node sets\n",[]),
  Node_sets = hipe_node_sets:new(),
  %% io:format("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("Assign colors\n",[]),
  {Color1,Node_sets2} =
    assignColors(hipe_reg_worklists:stack(Worklists0), Node_sets1, Color0, 
		 Alias0, All_colors, Target),
  %% io:format("color0:~w\nColor1:~w\nNodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Color0,Color1,Node_sets,Node_sets2,No_temporaries]),

  ?debug_msg("Build mapping ~p\n",[Node_sets2]),
  Coloring = build_namelist(Node_sets2,SpillIndex,Alias0,Color1),
  ?debug_msg("Coloring ~p\n",[Coloring]),
  Coloring.

%%----------------------------------------------------------------------
%% 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
%%   
%%----------------------------------------------------------------------

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(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(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(Worklists, Moves, IG, K, Alias, SpillLimit),
      do_coloring(IG, Worklists0, Moves0, 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
%%----------------------------------------------------------------------

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, New_moves} =
    decrement_degree(Adjacent, IG, Worklists01, Moves, K),
  simplify(Nodes, New_ig, Worklists1, New_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.
%%----------------------------------------------------------------------

decrement_degree([], IG, Worklists, Moves, _K) -> 
  {IG, Worklists, Moves};
decrement_degree([Node|Nodes], IG, Worklists, Moves, K) ->
  PrevDegree = hipe_ig:get_node_degree(Node, IG),
  IG0 = hipe_ig:dec_node_degree(Node, IG),
  if PrevDegree =:= K ->
      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(Nodes, IG0, Worklists1, Moves0, K);
	_ ->
	  Worklists1 = hipe_reg_worklists:add_simplify(Node, Worklists0),
	  decrement_degree(Nodes, IG0, Worklists1, Moves0, K)
      end;
     true ->
      decrement_degree(Nodes, IG0, Worklists, Moves, 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
%%----------------------------------------------------------------------

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.

%%----------------------------------------------------------------------
%% Function:    enable_moves_active_to_worklist
%%
%% 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
%%----------------------------------------------------------------------

enable_moves_active_to_worklist([], Moves) -> Moves;
enable_moves_active_to_worklist([Node|Nodes], Moves) ->
  NewMoves =
    case hipe_moves:member_active(Node, Moves) of
      true ->
	hipe_moves:add_worklist(Node, hipe_moves:remove_active(Node, Moves));
      _ ->
	Moves
    end,
  enable_moves_active_to_worklist(Nodes, NewMoves).

%% Build the namelists, these functions are fast hacks, they use knowledge 
%% about data representation that they shouldn't know, bad abstraction.

build_namelist(NodeSets, Index, Alias, Color) ->
  ?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(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).

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

build_reglist([],_Color,List) -> 
  List;
build_reglist([Node|Ns],Color,List) ->
  build_reglist(Ns,Color,[{Node,{reg,getColor(Node,Color)}}|List]).

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

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