hipe_ls_regalloc.erl

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

%% -*- erlang-indent-level: 2 -*-
%% =====================================================================
%% @doc
%% <pre>
%%  Filename : 	hipe_ls_regalloc.erl
%%  Module   :	hipe_ls_regalloc
%%  Purpose  :  Perform a register allocation based on the 
%%              "linear-scan algorithm".
%%  Notes    :  * This is an implementation of 
%%                "Linear Scan Register Allocation" by 
%%                Massimiliano Poletto &amp; Vivek Sarkar described in
%%                ACM TOPLAS Vol 21, No 5, September 1999.
%%
%%              * This implementation is target-independent and
%%                requires a target specific interface module
%%                as argument.  
%%                (Still waiting for a modular module system for Erlang.)
%% </pre>
%% @end
%%              
%%  History  :	* 2000-04-07 Erik Johansson ([e-mail]): Created.
%%              * 2001-07-16 EJ: Made less sparc-specific.
%% CVS:
%%    $Author: mikpe $
%%    $Date: 2006/09/14 13:33:28 $
%%    $Revision: 1.32 $
%% =====================================================================
%% Exported functions (short description):
%%   regalloc(CFG,PhysRegs,Entrypoints, Options) -> 
%%    {Coloring, NumberOfSpills}
%%    Takes a (SPARC) CFG and returns a coloring of all used registers.  
%%    PhysRegs should be a list of available physical registers.
%%    Entrypoints should be a list of names of Basic Blocks that have
%%     external entry points.
%%
%%    The Coloring will be in the form of the "allocation datastructure"
%%     described below, that is, a list of tuples on the form
%%      {Name, {reg, PhysicalRegister}} or
%%      {Name, {spill, SpillIndex}}
%%    The NumberOfSpills is either 0 indicating no spill or the 
%%     SpillIndex of the last spilled register.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

-module(hipe_ls_regalloc).
-export([regalloc/7]).
%-define(DEBUG,1).
-define(HIPE_INSTRUMENT_COMPILER, true).
-include("../main/hipe.hrl").


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% @spec
%% regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options,
%%          Target) ->
%%    {Coloring, NumberOfSpills}
%%  CFG = cfg()
%%  PhysRegs = [reg()]
%%  Entrypoints = [labelname()]
%%  DontSpill = reg()
%%  Options = proplist:proplist()
%%  Target = atom()
%%  Coloring = [{temp(), pos()}]
%%  NumberOfSpills = integer()
%%  reg() = integer()
%%  temp() = integer()
%%  pos() = {reg, reg()} | {spill, integer()}
%% 
%% @doc
%%   Calculates an allocation of registers using a linear_scan algorithm.
%%   There are three steps in the algorithm:
%%   <ol>
%%    <li> Calculate live-ranges for all registers.</li>
%%    <li> Calculate live-intervals for each register.
%%         The live interval consists of a start position and an end
%%	   position. These are the first definition and last use of the
%%	   register given as instruction numbers in a breadth-first
%%	   traversal of the control-flow-graph.</li>
%%    <li> Perform a linear scan allocation over the live intervals.</li>
%%   </ol>
%% @end
%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
regalloc(CFG,PhysRegs,Entrypoints, SpillIndex, DontSpill, Options, Target) ->
  ?debug_msg("LinearScan: ~w\n",[erlang:statistics(runtime)]),
  %%     Step 1: Calculate liveness (Call external implementation.)
  Liveness = liveness(CFG, Target),
  ?debug_msg("liveness (done)~w\n",[erlang:statistics(runtime)]),
  USIntervals = calculate_intervals(CFG, Liveness,
				    Entrypoints, Options,
				    Target),
  ?debug_msg("intervals (done) ~w\n",[erlang:statistics(runtime)]),
  Intervals = sort_on_start(USIntervals),
  ?debug_msg("sort intervals (done) ~w\n",[erlang:statistics(runtime)]),
  %% ?debug_msg("Intervals ~w\n",[Intervals]),
  ?debug_msg("No intervals: ~w\n",[length(Intervals)]),

  ?debug_msg("count intervals (done) ~w\n",[erlang:statistics(runtime)]),
  Allocation = allocate(Intervals,PhysRegs, SpillIndex, DontSpill, Target),
  ?debug_msg("allocation (done) ~w\n",[erlang:statistics(runtime)]),
  Allocation.
%%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                                                    %%
%%        Step 2: Calculate live-intervals for each register.         %%
%%                                                                    %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
%% calculate_intervals(CFG,Liveness,Entrypoints, Options, Target)
%%  CFG: The Control-Flow Graph.
%%  Liveness: A map of live-in and live-out sets for each Basic-Block.
%%  Entrypoints: A set of BB names that have external entrypoints.
%%
calculate_intervals(CFG,Liveness,_Entrypoints, Options, Target) ->
  %% Add start point for the argument registers.
  Args = arg_vars(CFG, Target),
  Interval = 
    add_def_point(Args, 0, 
		  empty_interval(Target:number_of_temporaries(CFG))),

  %% Interval = add_livepoint(Args, 0, empty_interval()),
  Worklist =
    case proplists:get_value(ls_order, Options) of
      reversepostorder ->
	Target:reverse_postorder(CFG);
      breadth ->
	Target:breadthorder(CFG);
      postorder ->
	Target:postorder(CFG);
      inorder ->
	Target:inorder(CFG);
      reverse_inorder ->
	Target:reverse_inorder(CFG);
      preorder ->
	Target:preorder(CFG);
      prediction ->
	Target:predictionorder(CFG);
      random ->
	Target:labels(CFG);
      _ ->
	Target:reverse_postorder(CFG)
    end,

  %% ?inc_counter(bbs_counter, length(Worklist)),
  %% ?debug_msg("No BBs ~w\n",[length(Worklist)]),
  intervals(Worklist, Interval, 1, CFG, Liveness, succ_map(CFG, Target), Target).

%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
%% intervals(WorkList, Intervals, InstructionNr,
%%           CFG, Liveness, SuccMap)
%%  WorkList: List of BB-names to handle.
%%  Intervals: Intervals seen so far (sorted on register names).
%%  InstructionNr: The number of examined insturctions.
%%  CFG: The Control-Flow Graph.
%%  Liveness: A map of live-in and live-out sets for each Basic-Block.
%%  SuccMap: A map of successors for each BB name.
%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
intervals([L|ToDO],Intervals,InstructionNr,CFG,Liveness,SuccMap, Target) ->
  %% Add all variables that are live at the entry of this block
  %% to the interval data structure.
  LiveIn = livein(Liveness,L, Target),
  Intervals2 = add_def_point(LiveIn,InstructionNr,Intervals),
  LiveOut = liveout(Liveness,L, Target),

  %% Traverse this block instruction by instruction and add all
  %% uses and defines to the intervals.
  Code = hipe_bb:code(bb(CFG,L, Target)),
  {Intervals3, NewINr} = 
    traverse_block(Code, InstructionNr+1,
		   Intervals2,
		   Target),
  
  %% Add end points for the registers that are in the live-out set.
  Intervals4 = add_use_point(LiveOut, NewINr+1, Intervals3),
  
  intervals(ToDO, Intervals4, NewINr+1, CFG, Liveness, SuccMap, Target);
intervals([],Intervals,_,_,_,_, _) -> 
  %% Return the calculated intervals
  LI =interval_to_list(Intervals),
  %io:format("Intervals:~n~p~n", [LI]),
  LI.

%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
%% traverse_block(Code, InstructionNo, Intervals, Unchanged) 
%%  Examine each instruction in the Code:
%%   For each temporary T used or defined by instruction number N:
%%    extend the interval of T to include N.
%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
traverse_block([Instruction|Is],InstrNo,Intervals, Target) ->
  %% Get defined temps.
  DefsSet = defines(Instruction, Target),
  Intervals1 = add_def_point(DefsSet, InstrNo, Intervals),

  %% Get used temps.
  UsesSet = uses(Instruction, Target),
  %% Extend the intervals for these temporaries to include InstrNo.
  Intervals2 = add_use_point(UsesSet, InstrNo, Intervals1),

  %% Handle the next instruction.
  traverse_block(Is,InstrNo+1,Intervals2,Target);
traverse_block([], InstrNo, Intervals, _) -> 
  %% Return the new intervals and the number of the next instruction.
  {Intervals,InstrNo}.
%%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                                                    %%
%%    Step 3. Do a linear scan allocation over the live intervals.    %%
%%                                                                    %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% allocate(Intervals, PhysicalRegisters, DontSpill, Target)
%%
%% This function performs the linear scan algorithm.
%%  Intervals contains the start and stop position of each register,
%%            sorted on increasing startpositions
%%  PhysicalRegisters is a list of available Physical registers to use.
%%
%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target) ->
  ActiveRegisters =[],
  AllocatedRegisters = empty_allocation(),
  AllFree = create_freeregs(PhysRegs),
  allocate(Intervals, AllFree, ActiveRegisters,
	   AllocatedRegisters, SpillIndex, DontSpill, Target).
%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
%% allocate(Intervals, Free, Active, Allocated, SpillIndex, Target) 
%%  Iterates of each register interval.
%%   Intervals: The list of register intervals.
%%   Free: Currently available physical registers.
%%   Active: Currently used physical registers (sorted on increasing 
%%            interval enpoints)
%%   Allocated: The mapping of register names to physical registers or
%%              to spill positions.
%%   SpillIndex: The number of spilled registers. 
%%-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
allocate([RegInt|RIS], Free, Active, Alloc, SpillIndex, DontSpill, Target) ->
  %io:format("~nAlloc:~n~p", [Alloc]),
  %% Remove from the active list those registers who's intervals 
  %% ends before the start of the current interval.
  {NewActive, NewFree} = 
    expire_old_intervals(Active, startpoint(RegInt), Free, Target),
  ?debug_msg("Alloc interval: ~w, Free ~w\n",[RegInt, NewFree]),
  %% Get the name of the temp in the current interval.
  Temp = reg(RegInt), 
  case is_precoloured(Temp, Target) of
    true -> 
      %% This is a precoloured register we don't need to find a color
      %% Get the physical name of the register.
      PhysName = physical_name(Temp, Target), 
      %% Bind it to the precoloured name.
      NewAlloc = alloc(Temp, PhysName, Alloc,Target), 
      case is_global(Temp, Target) of
	true -> 
	  %% this is a global precoloured register 
	  allocate(RIS, NewFree, NewActive,
		   NewAlloc, SpillIndex, DontSpill, Target);
	false ->
	  case is_free(PhysName, NewFree) of
	    {true,Rest} ->
	      allocate(RIS, Rest, 
		       add_active(endpoint(RegInt), startpoint(RegInt), 
				  PhysName, Temp, NewActive),
		       NewAlloc,
		       SpillIndex, DontSpill, Target);
	    false ->
	      %% Some other temp has taken this precoloured register,
	      %% throw it out.
	      {OtherActive, NewActive2} = deactivate(PhysName, NewActive),
	      OtherTemp = active_name(OtherActive),
	      OtherEnd = active_endpoint(OtherActive),
	      OtherStart = active_startpoint(OtherActive),
	      NewActive3 = add_active(endpoint(RegInt), startpoint(RegInt),
					  PhysName, Temp, NewActive2),
	      case exists_free_register(OtherStart, NewFree) of
		{true, NewPhys, RestFree} ->
		  allocate(RIS, RestFree, 
			   add_active(OtherEnd, OtherStart, 
				      NewPhys, OtherTemp, NewActive3),
			   alloc(OtherTemp,NewPhys,NewAlloc,Target),
			   SpillIndex, DontSpill, Target);
		false ->
		  NewSpillIndex = Target:new_spill_index(SpillIndex),
		  {NewAlloc2, NewActive4} = 
		    spill(OtherTemp, OtherEnd, OtherStart, NewActive3, 
			  NewAlloc, SpillIndex, DontSpill, Target),
		  allocate(RIS, 
			   NewFree, 
			   NewActive4,
			   NewAlloc2, NewSpillIndex, DontSpill, Target)
	      end
	  end
      end;
    false -> 
      %% This is not a precoloured register.
      case NewFree of 
	[] -> 
	  %% No physical registers available, we have to spill.
	  NewSpillIndex = Target:new_spill_index(SpillIndex),
	  {NewAlloc, NewActive2} = 
	    spill(Temp, endpoint(RegInt), startpoint(RegInt),
		  Active, Alloc, SpillIndex, DontSpill, Target),
	  %% io:format("Spilled ~w\n",[NewAlloc]),
	  allocate(RIS, NewFree, NewActive2, NewAlloc, NewSpillIndex,
		   DontSpill, Target);

	[{FreeReg,_Start} | Regs] -> 
	  %% The register FreeReg is available, let's use it.
	  %%io:format("Allocating Reg:~p~n",[FreeReg]),
	  allocate(RIS,Regs,
		   add_active(endpoint(RegInt), startpoint(RegInt),
			      FreeReg, Temp, NewActive),
		   alloc(Temp, FreeReg, Alloc,Target),
		   SpillIndex, DontSpill, Target)
      end
  end;
allocate([],_,_,Alloc,SpillIndex, _, _) -> 
  %% No more register intervals to handle
  %%  return the result.
  %%io:format("~nAlloc:~n~p", [Alloc]),
  {Alloc, SpillIndex}.
%%^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^