hipe_optimistic_regalloc.erl

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

%% -*- erlang-indent-level: 2 -*-
%%-----------------------------------------------------------------------
%% File    : hipe_optimistic_regalloc.erl
%% Authors : NilsOla Linnermark <[e-mail]>
%%           Petter Holmberg <[e-mail]>
%% 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} =