hipe_ultra_prio.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 292 行

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%	      PRIORITY HANDLING AND PRIORITY CALCULATION
%%
%% Handling of ready nodes and priorities.
%% Priorities are mainly from the critical path. More priorities are added.
%%  * One version is adding priorities just depending on the instr, so
%%    for example loads get higher priority than stores, and ordered
%%    after reg's and offset for better cache performance.
%%  * The other version gives higher priority to a node that adds more new
%%    nodes to the ready list. This one is maybe not so effectively
%%    implemented, but was added too late for smarter solutions.
%% One version is commented away

-module(hipe_ultra_prio).
-export([init_ready/2,
	 init_instr_prio/2,
	 %% initial_ready_set/4,
	 next_ready/7,
	 add_ready_nodes/2,
	 insert_node/3
	]).

-include("../sparc/hipe_sparc.hrl").

% At first, only nodes with no predecessors are selected.
% - if R is empty, there is an error (unless BB itself is empty)

%% Arguments : Size  - size of ready-array
%%             Preds - array with number of predecessors for each node
%% Returns   : An array with list of ready-nodes for each cycle.

init_ready(Size, Preds) ->
    P = hipe_vectors:size(Preds),
    Ready = hipe_vectors:new(Size, []),
    R = initial_ready_set(1, P, Preds, []),
    hipe_vectors:set(Ready, 0, R).

init_instr_prio(N, DAG) ->
    critical_path(N, DAG).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Function    : initial_ready_set
%% Argument    : M     - current node-index
%%               N     - where to stop
%%               Preds - array with number of predecessors for each node
%%               Ready - list with ready-nodes
%% Returns     : Ready - list with ready-nodes
%% Description : Finds all nodes with no predecessors and adds them to ready.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

initial_ready_set(M, N, Preds, Ready) ->
    if
	M > N ->
	    Ready;
	true ->
	    case hipe_vectors:get(Preds, M-1) of
		0 ->
		    initial_ready_set(M+1, N, Preds, [M|Ready]);
		V when is_integer(V), V > 0 ->
		    initial_ready_set(M+1, N, Preds, Ready)
	    end
    end.

%% The following handles the nodes ready to schedule:
%% 1. select the ready queue of given cycle
%% 2. if queue empty, return none
%% 3. otherwise, remove entry with highest priority
%%    and return {next,Highest_Prio,NewReady}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Function    : next_ready
%% Argument    : C     - current cycle
%%               Ready - array with ready nodes
%%               Prio  - array with cpath-priorities for all nodes
%%               Nodes - indexed list [{N, Instr}]
%% Returns     : none / {next,Highest_Prio,NewReady}
%% Description :  1. select the ready queue of given cycle
%%                2. if queue empty, return none
%%                3. otherwise, remove entry with highest priority
%%                   and return {next,Highest_Prio,NewReady} where Highest_Prio
%%                   = Id of instr and NewReady = updated ready-array.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

next_ready(C, Ready, Prio, Nodes, DAG, Preds, Earl) ->
    Curr = hipe_vectors:get(Ready, C-1),
    case Curr of
	[] -> 
	    none;
	Instrs ->
	    {BestI,RestIs} = 
		get_best_instr(Instrs, Prio, Nodes, DAG, Preds, Earl, C),
	    {next,BestI,hipe_vectors:set(Ready,C-1,RestIs)}
    end.

% next_ready(C,Ready,Prio,Nodes) ->
%     Curr = hipe_vectors:get(Ready,C-1),
%     case Curr of
% 	[] ->   
% 	    none;
% 	Instrs ->
% 	    {BestInstr,RestInstrs} = get_best_instr(Instrs, Prio, Nodes),
% 	    {next,BestInstr,hipe_vectors:set(Ready,C-1,RestInstrs)}
%     end.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Function    : get_best_instr
%% Argument    : Instrs - list of node-id's
%%               Prio   - array with cpath-priorities for the nodes
%%               Nodes  - indexed list [{Id, Instr}]
%% Returns     : {BestSoFar, Rest} - Id of best instr and the rest of id's
%% Description : Returns the id of the instr that is the best choice.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

get_best_instr([Instr|Instrs], Prio, Nodes, DAG, Preds, Earl, C) ->
    get_best_instr(Instrs, [], Instr, Prio, Nodes, DAG, Preds, Earl, C).

get_best_instr([], Rest, BestSoFar, _Prio, _Nodes, _DAG, _Preds, _Earl, _C) -> 
    {BestSoFar, Rest};
get_best_instr([Instr|Instrs], PassedInstrs, BestSoFar, Prio, Nodes,
	       DAG, Preds, Earl, C) ->
    case better(Instr, BestSoFar, Prio, Nodes, DAG, Preds, Earl, C) of
        true ->
	    get_best_instr(Instrs, [BestSoFar|PassedInstrs],
			   Instr, Prio, Nodes, DAG, Preds, Earl, C);
	false -> 
	    get_best_instr(Instrs, [Instr|PassedInstrs], BestSoFar, Prio, 
			   Nodes, DAG, Preds, Earl, C)
    end.

% get_best_instr([Instr|Instrs], Prio, Nodes) ->
%     get_best_instr(Instrs, [], Instr, Prio, Nodes).

% get_best_instr([], Rest, BestSoFar, Prio, Nodes) -> {BestSoFar, Rest};
% get_best_instr([Instr|Instrs], PassedInstrs, BestSoFar, Prio, Nodes) ->
%     case better(Instr, BestSoFar, Prio, Nodes) of
%         true ->
% 	    get_best_instr(Instrs, [BestSoFar|PassedInstrs], 
% 			   Instr, Prio, Nodes);
% 	false -> 
% 	    get_best_instr(Instrs, [Instr|PassedInstrs],BestSoFar, Prio, Nodes)
%     end.
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Function    : better
%% Argument    : Instr1 - Id of instr 1
%%               Instr2 - Id of instr 2
%%               Prio   - array with cpath-priorities for the nodes
%%               Nodes  - indexed list [{Id, Instr}]
%% Returns     : true if Instr1 has higher priority than Instr2
%% Description : Checks if Instr1 is a better choice than Instr2 for scheduling
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

better(Instr1, Instr2, Prio, Nodes, DAG, Preds, Earl, C) ->
    better_hlp(priority(Instr1, Prio, Nodes, DAG, Preds, Earl, C), 
	       priority(Instr2, Prio, Nodes, DAG, Preds, Earl, C)).

better_hlp([], []) -> false;
better_hlp([], [_|_]) -> false;
better_hlp([_|_], []) -> true;
better_hlp([X|Xs], [Y|Ys]) -> (X > Y) or ((X =:= Y) and better_hlp(Xs,Ys)).

%%
%% Returns the instr corresponding to id
%%
get_instr(InstrId, [{InstrId,Instr}|_]) -> Instr;
get_instr(InstrId, [_|Xs]) -> get_instr(InstrId, Xs).
				      
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Function    : priority
%% Argument    : InstrId - Id
%%               Prio    - array with cpath-priorities for the nodes
%%               Nodes   - indexed list [{Id, Instr}]
%% Returns     : PrioList - list of priorities [MostSignificant, LessSign, ...]
%% Description : Returns a list of priorities where the first element is the
%%               cpath-priority and the rest are added depending on what kind
%%               of instr it is. Used to order loads/stores sequentially and
%%               there is possibility to add whatever stuff...  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

priority(InstrId, Prio, Nodes, DAG, Preds, Earl, C) ->
    {ReadyNodes,_,_,_} = hipe_schedule:delete_node(C,InstrId,DAG,Preds,Earl),
    Instr = get_instr(InstrId, Nodes),
    Prio1 = hipe_vectors:get(Prio, InstrId-1),
    Prio2 = length(ReadyNodes),
    PrioRest =
	case Instr of
	 #load_atom{} ->
	    [3];
	 #move{} ->
	    [3];
	 #load{} -> 
  	    Src = hipe_sparc:load_src(Instr),
  	    Off = hipe_sparc:load_off(Instr),
	    case hipe_sparc:is_reg(Off) of
		false -> [3, 
			  -(hipe_sparc:reg_nr(Src)), 
			  -(hipe_sparc:imm_value(Off))];
		true -> [1]
	    end;
	 #store{} -> 
	     Src = hipe_sparc:store_dest(Instr),
	     Off = hipe_sparc:store_off(Instr),
	     case hipe_sparc:is_reg(Off) of
		 false -> [2, 
			   -(hipe_sparc:reg_nr(Src)), 
			   -(hipe_sparc:imm_value(Off))];
		 true -> [1]
	     end;
	 _ -> [0]
	end,
    [Prio1,Prio2|PrioRest].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Function    : add_ready_nodes
%% Argument    : Nodes - list of [{Cycle,Id}]
%%               Ready - array of ready nodes for all cycles
%% Returns     : NewReady - updated ready-array
%% Description : Gets a list of instrs and adds them to the ready-array
%%               to the corresponding cycle.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

add_ready_nodes([], Ready) -> Ready;
add_ready_nodes([{C,I}|Xs], Ready) ->
    add_ready_nodes(Xs, insert_node(C, I, Ready)).

insert_node(C, I, Ready) ->
    Old = hipe_vectors:get(Ready, C-1),
    hipe_vectors:set(Ready, C-1, [I|Old]).

%%
%% Computes the latency for the "most expensive" way through the graph
%% for all nodes.  Returns an array of priorities for all nodes.
%%
critical_path(N, DAG) ->
    critical_path(1, N, DAG, hipe_vectors:new(N, -1)).

critical_path(M, N, DAG, Prio) ->
    if
	M > N ->
	    Prio;
	true ->
	    critical_path(M+1, N, DAG, cpath(M, DAG, Prio))
    end.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Function    : cpath
%% Argument    : M    - current node id
%%               DAG  - the dependence graph
%%               Prio - array of priorities for all nodes
%% Returns     : Prio - updated prio array
%% Description : If node has prio -1, it has not been visited
%%                - otherwise, compute priority as max of priorities of 
%%                  successors (+ latency)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

cpath(M, DAG, Prio) ->
    InitPrio = hipe_vectors:get(Prio, M-1),
    if
	InitPrio =:= -1 ->
	    cpath_node(M, DAG, Prio);
	true ->
	    Prio
    end.

cpath_node(N, DAG, Prio) ->
    SuccL = dag_succ(DAG, N),
    {Max, NewPrio} = cpath_succ(SuccL, DAG, Prio),
    hipe_vectors:set(NewPrio, N-1, Max).

cpath_succ(SuccL, DAG, Prio) ->
    cpath_succ(SuccL, DAG, Prio, 0).

%% performs an unnecessary lookup of priority of Succ, but that might
%% not be such a big deal

cpath_succ([], _DAG, Prio, NodePrio) -> {NodePrio,Prio};
cpath_succ([{Lat,Succ}|Xs], DAG, Prio, NodePrio) ->
    NewPrio = cpath(Succ, DAG, Prio),
    NewNodePrio = max(hipe_vectors:get(NewPrio, Succ - 1) + Lat, NodePrio),
    cpath_succ(Xs, DAG, NewPrio, NewNodePrio).

dag_succ(DAG, N) when is_integer(N) ->
    hipe_vectors:get(DAG, N-1).

max(X, Y) ->
    if
	X < Y -> Y;
	true -> X
    end.