The R13B03 release.OTP_R13B03

1 files changed, 304 insertions, 0 deletions

diff --git a/lib/hipe/opt/hipe_ultra_prio.erl b/lib/hipe/opt/hipe_ultra_prio.erl
new file mode 100644
index 0000000000..9e2c1a0489
--- /dev/null
+++ b/lib/hipe/opt/hipe_ultra_prio.erl
@@ -0,0 +1,304 @@
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2001-2009. All Rights Reserved.
+%% 
+%% The contents of this file are subject to the Erlang Public License,
+%% Version 1.1, (the "License"); you may not use this file except in
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%% 
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%% 
+%% %CopyrightEnd%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%%	      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 = erlang: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).
+