diff options
| -rw-r--r-- | lib/hipe/opt/hipe_schedule.erl | 1483 | ||||
| -rw-r--r-- | lib/hipe/opt/hipe_schedule_prio.erl | 53 | ||||
| -rw-r--r-- | lib/hipe/opt/hipe_target_machine.erl | 87 | ||||
| -rw-r--r-- | lib/hipe/opt/hipe_ultra_mod2.erl | 233 | ||||
| -rw-r--r-- | lib/hipe/opt/hipe_ultra_prio.erl | 298 |
5 files changed, 0 insertions, 2154 deletions
diff --git a/lib/hipe/opt/hipe_schedule.erl b/lib/hipe/opt/hipe_schedule.erl deleted file mode 100644 index 0f25940e3d..0000000000 --- a/lib/hipe/opt/hipe_schedule.erl +++ /dev/null @@ -1,1483 +0,0 @@ -%% Licensed under the Apache License, Version 2.0 (the "License"); -%% you may not use this file except in compliance with the License. -%% You may obtain a copy of the License at -%% -%% http://www.apache.org/licenses/LICENSE-2.0 -%% -%% Unless required by applicable law or agreed to in writing, software -%% distributed under the License is distributed on an "AS IS" BASIS, -%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -%% See the License for the specific language governing permissions and -%% limitations under the License. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% INSTRUCTION SCHEDULER -%% -%% This is a basic ILP cycle scheduler: -%% * set cycle = 0 -%% * while ready[cycle] nonempty do -%% - take x with greatest priority from ready[cycle] -%% - try to schedule x; -%% * if scheduling x was possible, -%% - reserve resources -%% - add x to schedule and delete x from dag -%% - update earliest-time for all successor nodes -%% as max[earliest[y],cycle+latency[x]] -%% - if some node y now has no predecessors, -%% add y to ready[earliest[y]] -%% * if it was impossible, put x in ready[cycle+1] -%% (= try again) -%% -%% We use the following data structures: -%% 1. all nodes are numbered and indices used as array keys -%% 2. priority per node can be computed statically or dynamically -%% * statically: before scheduling, each node gets a priority value -%% * dynamically: at each cycle, compute priorities for all ready nodes -%% 3. earliest: earliest cycle of issue, starts at 0 -%% and is updated as predecessors issue -%% 4. predecessors: number of predecessors (0 = ready to issue) -%% 5. successors: list of {Latency,NodeID} -%% 6. ready: an array indexed by cycle-time (integer), where -%% ready nodes are kept. -%% 7. resources: a resource representation (ADT) that answers -%% certain queries, e.g., "can x be scheduled this cycle" -%% and "reserve resources for x". -%% 8. schedule: list of scheduled instructions {Instr,Cycle} -%% in the order of issue -%% 9. instructions: maps IDs back to instructions -%% -%% Inputs: -%% - a list of {ID,Node} pairs (where ID is a unique key) -%% - a dependence list {ID0,Latency,ID1}, which is used to -%% build the DAG. -%% -%% Note that there is some leeway in how things are represented -%% from here. -%% -%% MODIFICATIONS: -%% - Some basic blocks are not worth scheduling (e.g., GC save/restore code) -%% yet are pretty voluminous. How do we skip them? -%% - Scheduling should be done at finalization time: when basic block is -%% linearized and is definitely at Sparc assembly level, THEN reorder -%% stuff. - --module(hipe_schedule). --export([cfg/1, est_cfg/1, delete_node/5]). - --include("../sparc/hipe_sparc.hrl"). - -%%-define(debug1,true). - --define(debug2(Str,Args),ok). -%%-define(debug2(Str,Args),io:format(Str,Args)). - --define(debug3(Str,Args),ok). -%%-define(debug3(Str,Args),io:format(Str,Args)). - --define(debug4(Str,Args),ok). -%%-define(debug4(Str,Args),io:format(Str,Args)). - --define(debug5(Str,Args),ok). -%%-define(debug5(Str,Args),io:format(Str,Args)). - --define(debug(Str,Args),ok). -%%-define(debug(Str,Args),io:format(Str,Args)). - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : cfg -%% Argument : CFG - the control flow graph -%% Returns : CFG - A new cfg with scheduled blocks -%% Description : Takes each basic block and schedules them one by one. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -cfg(CFG) -> - ?debug3("CFG: ~n~p", [CFG]), - update_all( [ {L, - hipe_bb:mk_bb( - block(L,hipe_bb:code(hipe_sparc_cfg:bb(CFG,L))) )} - || L <- hipe_sparc_cfg:labels(CFG) ], CFG). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : update_all -%% Argument : Blocks - [{Label, Block}] , a list with labels and new code -%% used for updating the old CFG. -%% CFG - The old controlflow graph -%% Returns : An updated controlflow graph. -%% Description : Just swappes the basic blocks in the CFG to the scheduled one. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -update_all([],CFG) -> CFG; -update_all([{L,NewB}|Ls],CFG) -> - update_all(Ls,hipe_sparc_cfg:bb_add(CFG,L,NewB)). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -est_cfg(CFG) -> - update_all([ {L, hipe_bb:mk_bb(est_block(hipe_bb:code(hipe_sparc_cfg:bb(CFG,L))))} - || L <- hipe_sparc_cfg:labels(CFG) ], CFG). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% Provides an estimation of how quickly a block will execute. -%% This is done by chaining all instructions in sequential order -%% by 0-cycle dependences (which means they will never be reordered), -%% then scheduling the mess. - -est_block([]) -> []; -est_block([I]) -> [I]; -est_block(Blk) -> - {IxBlk,DAG} = est_deps(Blk), - Sch = bb(IxBlk,DAG), - separate_block(Sch,IxBlk). - -est_deps(Blk) -> - IxBlk = indexed_bb(Blk), - DAG = deps(IxBlk), - {IxBlk, chain_instrs(IxBlk,DAG)}. - -chain_instrs([{N,_}|Xs],DAG) -> - chain_i(N,Xs,DAG). - -chain_i(_,[],DAG) -> DAG; -chain_i(N,[{M,_}|Xs],DAG) -> - NewDAG = dep_arc(N,zero_latency(),M,DAG), - chain_i(M,Xs,NewDAG). - -zero_latency() -> 0. - -lookup_instr([{N,I}|_], N) -> I; -lookup_instr([_|Xs], N) -> lookup_instr(Xs, N). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : block -%% Argument : Instrs - [Instr], list of all the instructions in a basic -%% block. -%% Returns : A new scheduled block -%% Description : Schedule a basic block -%% -%% Note: does not consider delay slots! -%% (another argument for using only annulled delay slots?) -%% * how do we add delay slots? somewhat tricky to -%% reconcile with the sort of scheduling we consider. -%% (as-early-as-possible) -%% => rewrite scheduler into as-late-as-possible? -%% (=> just reverse the dependence arcs??) -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%% Don't fire up the scheduler if there's no work to do. -block(_, []) -> - []; -block(_L, [I]) -> - case hipe_sparc:is_any_branch(I) of - true -> [hipe_sparc:nop_create(), I]; - false -> [I] - end; -block(_L, Blk) -> - IxBlk = indexed_bb(Blk), - case IxBlk of - [{_N, I}] -> % comments and nops may have been removed. - case hipe_sparc:is_any_branch(I) of - true -> [hipe_sparc:nop_create(), I]; - false -> [I] - end; - _ -> - Sch = bb(IxBlk, {DAG, _Preds} = deps(IxBlk)), - {NewSch, NewIxBlk} = fill_delays(Sch, IxBlk, DAG), - X = finalize_block(NewSch, NewIxBlk), - debug1_stuff(Blk, DAG, IxBlk, Sch, X), - X - end. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : fill_delays -%% Argument : Sch - List of {{cycle, C}, {node, N}} : C = current cycle -%% N = node index -%% IxBlk - Indexed block [{N, Instr}] -%% DAG - Dependence graph -%% Returns : {NewSch, NewIxBlk} - vector with new schedule and vector -%% with {N, Instr} -%% Description : Goes through the schedule from back to front looking for -%% branches/jumps. If one is found fill_del tries to find -%% an instr to fill the delayslot. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -fill_delays(Sch, IxBlk, DAG) -> - NewIxBlk = hipe_vectors:list_to_vector(IxBlk), - %% NewSch = hipe_vectors:list_to_vector(Sch), - NewSch = fill_del(length(Sch), hipe_vectors:list_to_vector(Sch), - NewIxBlk, DAG), - {NewSch, NewIxBlk}. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : fill_del -%% Argument : N - current index in the schedule -%% Sch - schedule -%% IxBlk - indexed block -%% DAG - dependence graph -%% Returns : Sch - New schedule with possibly a delay instr in the last -%% position. -%% Description : If a call/jump is found fill_branch_delay/fill_call_delay -%% is called to find a delay-filler. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -fill_del(N, Sch, _IxBlk, _DAG) when N < 1 -> Sch; -fill_del(N, Sch, IxBlk, DAG) -> - Index = get_index(Sch, N), - ?debug2("Index for ~p: ~p~nInstr: ~p~n", - [N, Index, get_instr(IxBlk, Index)]), - NewSch = - case get_instr(IxBlk, Index) of - #call_link{} -> - fill_branch_delay(N - 1, N, Sch, IxBlk, DAG); - #jmp_link{} -> - fill_call_delay(N - 1, N, Sch, IxBlk, DAG); - #jmp{} -> - fill_call_delay(N - 1, N, Sch, IxBlk, DAG); - #b{} -> - fill_branch_delay(N - 1, N, Sch, IxBlk, DAG); - #br{} -> - fill_branch_delay(N - 1, N, Sch, IxBlk, DAG); - #goto{} -> - fill_branch_delay(N - 1, N, Sch, IxBlk, DAG); - _Other -> - Sch - end, - NewSch. - %% fill_del(N - 1, NewSch, IxBlk, DAG). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : fill_call_delay -%% Argument : Cand - index in schedule of delay-candidate -%% Call - index in schedule of call -%% Sch - schedule vector: < {{cycle,Ci},{node,Nj}}, ... > -%% IxBlk - block vector: < {N, Instr1}, {N+1, Instr2} ... > -%% DAG - dependence graph -%% Returns : Sch - new updated schedule. -%% Description : Searches backwards through the schedule trying to find an -%% instr without conflicts with the Call-instr. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -fill_call_delay(Cand, _Call, Sch, _IxBlk, _DAG) when Cand < 1 -> Sch; -fill_call_delay(Cand, Call, Sch, IxBlk, DAG) -> - CandIndex = get_index(Sch, Cand), - CallIndex = get_index(Sch, Call), - CandI = get_instr(IxBlk, CandIndex), - case move_or_alu(CandI) of - true -> - case single_depend(CandIndex, CallIndex, DAG) of - false -> % Other instrs depends on Cand ... - fill_call_delay(Cand - 1, Call, Sch, IxBlk, DAG); - - true -> - CallI = get_instr(IxBlk, CallIndex), - - CandDefs = ordsets:from_list(hipe_sparc:defines(CandI)), - %% CandUses = ordsets:from_list(hipe_sparc:uses(CandI)), - %% CallDefs = ordsets:from_list(hipe_sparc:defines(CallI)), - CallUses = ordsets:from_list(hipe_sparc:uses(CallI)), - - Args = case CallI of - #jmp_link{} -> - ordsets:from_list( - hipe_sparc:jmp_link_args(CallI)); - #jmp{} -> - ordsets:from_list(hipe_sparc:jmp_args(CallI)); - #call_link{} -> - ordsets:from_list( - hipe_sparc:call_link_args(CallI)) - end, - CallUses2 = ordsets:subtract(CallUses, Args), - Conflict = ordsets:intersection(CandDefs, CallUses2), - %% io:format("single_depend -> true:~n ~p~n, ~p~n,~p~n",[CandI,CallI,DAG]), - %% io:format("Cand = ~p~nCall = ~p~n",[CandI,CallI]), - %% io:format("CandDefs = ~p~nCallDefs = ~p~n",[CandDefs,CallDefs]), - %% io:format("CandUses = ~p~nCallUses = ~p~n",[CandUses,CallUses]), - %% io:format("Args = ~p~nCallUses2 = ~p~n",[Args,CallUses2]), - %% io:format("Conflict = ~p~n",[Conflict]), - - case Conflict of - [] -> % No conflicts ==> Cand can fill delayslot after Call - update_schedule(Cand, Call, Sch); - _ -> % Conflict: try with preceeding instrs - fill_call_delay(Cand - 1, Call, Sch, IxBlk, DAG) - end - end; - false -> - fill_call_delay(Cand - 1, Call, Sch, IxBlk, DAG) - end. - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : fill_branch_delay -%% Argument : Cand - index in schedule of delay-candidate -%% Branch - index in schedule of branch -%% Sch - schedule -%% IxBlk - indexed block -%% DAG - dependence graph -%% Returns : Sch - new updated schedule. -%% Description : Searches backwards through the schedule trying to find an -%% instr without conflicts with the Branch-instr. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -fill_branch_delay(Cand, _Br, Sch, _IxBlk, _DAG) when Cand < 1 -> Sch; -fill_branch_delay(Cand, Br, Sch, IxBlk, DAG) -> - CandIndex = get_index(Sch, Cand), - BrIndex = get_index(Sch, Br), - CandI = get_instr(IxBlk, CandIndex), - case move_or_alu(CandI) of - true -> - case single_depend(CandIndex, BrIndex, DAG) of - false -> % Other instrs depends on Cand ... - fill_branch_delay(Cand - 1, Br, Sch, IxBlk, DAG); - - true -> - BrI = get_instr(IxBlk, BrIndex), - CandDefs = ordsets:from_list(hipe_sparc:defines(CandI)), - %% CandUses = ordsets:from_list(hipe_sparc:uses(CandI)), - %% BrDefs = ordsets:from_list(hipe_sparc:defines(BrI)), - BrUses = ordsets:from_list(hipe_sparc:uses(BrI)), - - Conflict = ordsets:intersection(CandDefs, BrUses), - %% io:format("single_depend -> true: ~p~n, ~p~n,~p~n", [CandI, BrI, DAG]), - %% io:format("Cand = ~p~nBr = ~p~n",[CandI,BrI]), - %% io:format("CandDefs = ~p~nBrDefs = ~p~n",[CandDefs,BrDefs]), - %% io:format("CandUses = ~p~nBrUses = ~p~n",[CandUses,BrUses]), - %% io:format("Conflict = ~p~n",[Conflict]); - - case Conflict of - [] -> % No conflicts ==> - % Cand can fill delayslot after Branch - update_schedule(Cand, Br, Sch); - _ -> % Conflict: try with preceeding instrs - fill_branch_delay(Cand - 1, Br, Sch, IxBlk, DAG) - end - end; - false -> - fill_branch_delay(Cand - 1, Br, Sch, IxBlk, DAG) - end. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : update_schedule -%% Argument : From - the position from where to switch indexes in Sch -%% To - the position to where to switch indexes in Sch -%% Sch - schedule -%% Returns : Sch - an updated schedule -%% Description : If From is the delay-filler and To is the Call/jump, the -%% schedule is updated so From gets index To, To gets index -%% To - 1, and the nodes between From and To gets old_index - 1. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -update_schedule(To, To, Sch) -> - {{cycle, C}, {node, _N} = Node} = hipe_vectors:get(Sch, To-1), - hipe_vectors:set(Sch, To-1, {{cycle, C+1}, Node}); -update_schedule(From, To, Sch) -> - Temp = hipe_vectors:get(Sch, From-1), - Sch1 = hipe_vectors:set(Sch, From-1, hipe_vectors:get(Sch, From)), - update_schedule(From + 1, To, hipe_vectors:set(Sch1, From, Temp)). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : single_depend -%% Argument : N - Index of the delayslot candidate -%% M - Index of the node that N possibly has a single -%% depend to. -%% DAG - The dependence graph -%% Returns : true if no other nodes than N os depending on N -%% Description : Checks that no other nodes than M depends on N and that the -%% latency between them is zero or 1. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -single_depend(N, M, DAG) -> - Deps = hipe_vectors:get(DAG, N-1), - single_depend(M, Deps). - -single_depend(_N, []) -> true; -single_depend(N, [{0, N}]) -> true; -single_depend(N, [{1, N}]) -> true; -single_depend(_N, [{_Lat, _}|_]) -> false. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : get_index -%% Argument : Sch - schedule -%% N - index in schedule -%% Returns : Index - index of the node -%% Description : Returns the index of the node on position N in the schedule. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -get_index(Sch, N) -> - {{cycle, _C}, {node, Index}} = hipe_vectors:get(Sch,N-1), - Index. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : get_instr -%% Argument : IxBlk - indexed block -%% N - index in block -%% Returns : Instr -%% Description : Returns the instr on position N in the indexed block. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -get_instr(IxBlk, N) -> - {_, Instr} = hipe_vectors:get(IxBlk, N-1), - Instr. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : get_instr -%% Argument : Sch - schedule -%% IxBlk - indexed block -%% N - index in schedule -%% Returns : Instr -%% Description : Returns the instr on position N in the schedule. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -get_instr(Sch, IxBlk, N) -> - {{cycle, _C}, {node, Index}} = hipe_vectors:get(Sch, N-1), - {_, Instr} = hipe_vectors:get(IxBlk, Index-1), - Instr. - -separate_block(Sch,IxBlk) -> - sep_comments([{C,lookup_instr(IxBlk,N)} || {{cycle,C},{node,N}} <- Sch]). - -sep_comments([]) -> []; -sep_comments([{C,I}|Xs]) -> - [hipe_sparc:comment_create({cycle,C}), I | sep_comments(Xs,C)]. - -sep_comments([], _) -> []; -sep_comments([{C1,I}|Xs], C0) -> - if - C1 > C0 -> - [hipe_sparc:comment_create({cycle,C1}),I|sep_comments(Xs,C1)]; - true -> - [I|sep_comments(Xs, C0)] - end. - -finalize_block(Sch, IxBlk) -> - ?debug5("Sch: ~p~nIxBlk: ~p~n",[Sch,IxBlk]), - finalize_block(1, hipe_vectors:size(Sch), 1, Sch, IxBlk, []). - -finalize_block(N, End, _C, Sch, IxBlk, _Instrs) when N =:= End - 1 -> - NextLast = get_instr(Sch, IxBlk, N), - Last = get_instr(Sch, IxBlk, End), - ?debug5("NextLast: ~p~nLast: ~p~n",[NextLast,Last]), - case hipe_sparc:is_any_branch(Last) of - true -> % Couldn't fill delayslot ==> add NOP - [NextLast , hipe_sparc:nop_create(), Last]; - false -> % Last is a delayslot-filler ==> change order... - [Last, NextLast] - end; -finalize_block(N, End, C0, Sch, IxBlk, Instrs) -> - {{cycle, _C1}, {node, _M}} = hipe_vectors:get(Sch, N-1), - Instr = get_instr(Sch, IxBlk, N), - ?debug5("Instr: ~p~n~n",[Instr]), - [Instr | finalize_block(N + 1, End, C0, Sch, IxBlk, Instrs)]. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : bb -%% Argument : IxBlk - indexed block -%% DAG - {Dag, Preds} where Dag is dependence graph and -%% Preds is number of predecessors for each node. -%% Returns : Sch -%% Description : Initializes earliest-list, ready-list, priorities, resources -%% and so on, and calls the cycle_sched which does the scheduling -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -bb(IxBlk,DAG) -> - bb(length(IxBlk), IxBlk, DAG). - -bb(N,IxBlk,{DAG, Preds}) -> - Earliest = init_earliest(N), - BigArray = N*10, % "nothing" is this big :-) - Ready = hipe_schedule_prio:init_ready(BigArray,Preds), - I_res = init_instr_resources(N, IxBlk), - - Prio = hipe_schedule_prio:init_instr_prio(N,DAG), - Rsrc = init_resources(BigArray), - ?debug4("I_res: ~n~p~nPrio: ~n~p~nRsrc: ~n~p~n", [I_res,Prio,Rsrc]), - ?debug('cycle 1~n',[]), - Sch = empty_schedule(), - cycle_sched(1,Ready,DAG,Preds,Earliest,Rsrc,I_res,Prio,Sch,N,IxBlk). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : cycle_sched -%% Argument : - C is current cycle, 1 or more. -%% - Ready is an array (Cycle -> [Node]) -%% yielding the collection of nodes ready to be -%% scheduled in a cycle. -%% - DAG is an array (Instr -> [{Latency,Instr}]) -%% represents the dependence DAG. -%% - Preds is an array (Instr -> NumPreds) -%% counts the number of predecessors -%% (0 preds = ready to be scheduled). -%% - Earl is an array (Instr -> EarliestCycle) -%% holds the earliest cycle an instruction can be scheduled. -%% - Rsrc is a 'resource ADT' that handles scheduler resource -%% management checks whether instruction can be scheduled -%% this cycle without a stall. -%% - I_res is an array (Instr -> Required_resources) -%% holds the resources required to schedule an instruction. -%% - Sch is the representation of the schedule current schedule. -%% - N is the number of nodes remaining to be scheduled -%% tells us when to stop the scheduler. -%% - IxBlk is the indexed block with instrs -%% Returns : present schedule -%% Description : Scheduler main loop. -%% Pick next ready node in priority order for cycle C until -%% none remain. -%% * check each node if it can be scheduled w/o stalling -%% * if so, schedule it -%% * otherwise, bump the node to the next cycle -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -cycle_sched(C,Ready,DAG,Preds,Earl,Rsrc,I_res,Prio,Sch,N,IxBlk) -> - case hipe_schedule_prio:next_ready(C,Ready,Prio,IxBlk,DAG,Preds,Earl) of -% case hipe_schedule_prio:next_ready(C,Ready,Prio,IxBlk) of - {next,I,Ready1} -> - ?debug('try ~p~n==> ready = ~p~n',[I, Ready1]), - case resources_available(C,I,Rsrc,I_res) of - {yes,NewRsrc} -> - ?debug(' scheduled~n==> Rscrs = ~p~n',[NewRsrc]), - NewSch = add_to_schedule(I,C,Sch), - {ReadyNs,NewDAG,NewPreds,NewEarl} = - delete_node(C,I,DAG,Preds,Earl), - ?debug("NewPreds : ~p~n",[Preds]), - ?debug(' ReadyNs: ~p~n',[ReadyNs]), - NewReady = hipe_schedule_prio:add_ready_nodes(ReadyNs, - Ready1), - ?debug(' New ready: ~p~n',[NewReady]), - cycle_sched(C,NewReady,NewDAG,NewPreds,NewEarl, - NewRsrc,I_res,Prio,NewSch,N-1, IxBlk); - no -> - ?debug(' resource conflict~n',[]), - NewReady = hipe_schedule_prio:insert_node(C+1,I,Ready1), - cycle_sched(C,NewReady,DAG,Preds,Earl,Rsrc, - I_res,Prio,Sch,N,IxBlk) - end; - none -> % schedule next cycle if some node remains - if - N > 0 -> - ?debug('cycle ~p~n',[C+1]), - cycle_sched(C+1,Ready,DAG,Preds,Earl, - advance_cycle(Rsrc), - I_res,Prio,Sch,N, IxBlk); - true -> - present_schedule(Sch) - end - end. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : init_earliest -%% Argument : N - number of instrs -%% Returns : -%% Description : -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -init_earliest(N) -> - hipe_vectors:new(N,1). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% Schedule is kept reversed until the end. - --define(present_node(I,Cycle),{{cycle,Cycle},{node,I}}). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : empty_schedule -%% Description : Returns an empty schedule. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -empty_schedule() -> []. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : add_to_schedule -%% Argument : I - instr -%% Cycle - cycle when I was placed -%% Sch - schedule -%% Description : Adds instr to schedule -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -add_to_schedule(I,Cycle,Sch) -> - [?present_node(I,Cycle)|Sch]. - -present_schedule(Sch) -> lists:reverse(Sch). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% Interface to resource manager: -%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : init_resources -%% Description : Yields a 'big enough' array mapping (Cycle -> Resources); -%% this array is called Rsrc below. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -init_resources(S) -> - hipe_target_machine:init_resources(S). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : init_instr_resources -%% Argument : Nodes - a list of the instructions -%% N - is the number of nodes -%% Description : return a vector (NodeID -> Resource_requirements) -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -init_instr_resources(N,Nodes) -> - hipe_target_machine:init_instr_resources(N,Nodes). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : resources_available -%% Argument : Cycle - the current cycle -%% I - the current instruction (index = NodeID) -%% Rsrc - a map (Cycle -> Resources) -%% I_res - maps (NodeID -> Resource_requirements) -%% Description : returns {yes,NewResTab} | no -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -resources_available(Cycle,I,Rsrc,I_res) -> - hipe_target_machine:resources_available(Cycle,I,Rsrc,I_res). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : advance_cycle -%% Argument : Rsrc - resources -%% Description : Returns an empty resources-state -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -advance_cycle(Rsrc) -> - hipe_target_machine:advance_cycle(Rsrc). - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : delete_node -%% Argument : Cycle - current cycle -%% I - index of instr -%% DAG - dependence dag -%% Preds - array with number of predecessors for nodes -%% Earl - array with earliest-times for nodes -%% Returns : {ReadyNs,NewDAG,NewPreds,NewEarl} -%% Description : Deletes node I and updates earliest times for the rest. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -delete_node(Cycle,I,DAG,Preds,Earl) -> - Succ = hipe_vectors:get(DAG,I-1), - NewDAG = hipe_vectors:set(DAG,I-1,scheduled), % provides debug 'support' - {ReadyNs,NewPreds,NewEarl} = update_earliest(Succ,Cycle,Preds,Earl,[]), - ?debug('earliest after ~p: ~p~n',[I,[{Ix+1,V} || {Ix,V} <- hipe_vectors:list(NewEarl)]]), - {ReadyNs,NewDAG,NewPreds,NewEarl}. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : update_earliest -%% Argument : Succ - successor list -%% Cycle - current cycle -%% Preds - predecessors -%% Earl - earliest times for nodes -%% Ready - array with readynodes for cycles -%% Returns : {Ready,Preds,Earl} -%% Description : Updates the earliest times for nodes and updates number of -%% predecessors for nodes -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -update_earliest([],_Cycle,Preds,Earl,Ready) -> - {Ready,Preds,Earl}; -update_earliest([{Lat,N}|Xs],Cycle,Preds,Earl,Ready) -> - Old_earl = hipe_vectors:get(Earl,N-1), - New_earl = erlang:max(Old_earl,Cycle+Lat), - NewEarl = hipe_vectors:set(Earl,N-1,New_earl), - Num_preds = hipe_vectors:get(Preds,N-1), - NewPreds = hipe_vectors:set(Preds,N-1,Num_preds-1), - if - Num_preds =:= 0 -> - ?debug('inconsistent DAG~n',[]), - exit({update_earliest,N}); - Num_preds =:= 1 -> - NewReady = [{New_earl,N}|Ready], - NewPreds2 = hipe_vectors:set(NewPreds,N-1,0), - update_earliest(Xs,Cycle,NewPreds2,NewEarl,NewReady); - is_integer(Num_preds), Num_preds > 1 -> - update_earliest(Xs,Cycle,NewPreds,NewEarl,Ready) - end. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% Collect instruction dependences. -%% -%% Three forms: -%% - data/register -%% * insert RAW, WAR, WAW dependences -%% - memory -%% * stores serialize memory references -%% * alias analysis may allow loads to bypass stores -%% - control -%% * unsafe operations are 'trapped' between branches -%% * branches are ordered -%% -%% returns { [{Index,Instr}], DepDAG } -%% DepDAG is defined below. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : deps -%% Argument : BB - Basic block -%% Returns : {IxBB,DAG} - indexed block and dependence graph. DAG consists -%% of both Dag and Preds, where Preds is number -%% of predecessors for nodes. -%% Description : Collect instruction dependences. -%% -%% Three forms: -%% - data/register -%% * insert RAW, WAR, WAW dependences -%% - memory -%% * stores serialize memory references -%% * alias analysis may allow loads to bypass stores -%% - control -%% * unsafe operations are 'trapped' between branches -%% * branches are ordered -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -deps(IxBB) -> - N = length(IxBB), - DAG = empty_dag(N), % The DAG contains both dependence-arcs and - % number of predeccessors... - {_DepTab,DAG1} = dd(IxBB, DAG), - DAG2 = md(IxBB, DAG1), - cd(IxBB, DAG2). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : empty_dag -%% Argument : N - number of nodes -%% Returns : empty DAG -%% Description : DAG consists of dependence graph and predeccessors -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -empty_dag(N) -> - {hipe_vectors:new(N, []), hipe_vectors:new(N, 0)}. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : indexed_bb -%% Argument : BB - basic block -%% Returns : [{N, Instr}] -%% Description : Puts indexes to all instrs of a block, removes comments. -%% NOP's are also removed because if both sparc_schedule and -%% sparc_post_schedule options are used, the first pass will -%% add nop's before the branch if necessary, and these are -%% removed before scheduling the second pass. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -indexed_bb(BB) -> - indexed_bb(BB,1). - -indexed_bb([],_N) -> []; -indexed_bb([X|Xs],N) -> - case X of - #comment{} -> - indexed_bb(Xs,N); - #nop{} -> - indexed_bb(Xs,N); - _Other -> - [{N,X}|indexed_bb(Xs,N+1)] - end. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : dep_arc -%% Argument : N - Current node -%% Lat - Latency from current node to M -%% M - The dependent node -%% DAG - The dependence graph. Consists of both DAG and -%% predeccessors -%% Returns : A new DAG with the arc added and number of predeccessors for -%% M increased. -%% Description : Adds a new arc to the graph, if an older arc goes from N to M -%% it will be replaced with a new arc {max(OldLat, NewLat), M}. -%% Number of predeccessors for node M is increased. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -dep_arc(N, Lat, M, {Dag,Preds}) -> - OldDeps = hipe_vectors:get(Dag, N-1), - %% io:format("{OldDeps} = {~p}~n",[OldDeps]), - {NewDeps, Status} = add_arc(Lat, M, OldDeps), - %% io:format("{NewDeps, Status} = {~p, ~p}~n",[NewDeps, Status]), - NewDag = hipe_vectors:set(Dag, N-1, NewDeps), - NewPreds = case Status of - added -> % just increase preds if new arc was added - OldPreds = hipe_vectors:get(Preds, M-1), - hipe_vectors:set(Preds, M-1, OldPreds + 1); - non_added -> - Preds - end, - {NewDag, NewPreds}. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : add_arc -%% Argument : Lat - The latency from current node to To. -%% To - The instr-id of the node which the dependence goes to -%% Arcs - The dependecies that are already in the dep-graph -%% Returns : A dependence graph sorted by To. -%% Description : A new arc that is added is sorted in the right place, and if -%% there is already an arc between nodes A and B, the one with -%% the greatest latency is chosen. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -add_arc(Lat,To, []) -> {[{Lat, To}], added}; -add_arc(Lat1, To, [{Lat2, To} | Arcs]) -> - {[{erlang:max(Lat1, Lat2), To} | Arcs], non_added}; -add_arc(Lat1,To1, [{Lat2, To2} | Arcs]) when To1 < To2 -> - {[{Lat1, To1}, {Lat2, To2} | Arcs], added}; -add_arc(Lat1 ,To1, [{Lat2, To2} | Arcs]) -> - {Arcs1, Status} = add_arc(Lat1, To1, Arcs), - {[{Lat2, To2} | Arcs1], Status}. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% The register/data dependence DAG of a block is represented -%% as a mapping (Variable -> {NextWriter,NextReaders}) -%% where NextWriter is a pair {Ix,Type} -%% and NextReaders is a list of pairs {Ix,Type}. -%% -%% Type is used to determine latencies of operations; on the UltraSparc, -%% latencies of arcs (n -> m) are determined by both n and m. (E.g., if -%% n is an integer op and m is a store, then latency is 0; if m is an -%% integer op, it's 1.) - -dd([],DAG) -> { empty_deptab(), DAG }; -dd([{N,I}|Is],DAG0) -> - {DepTab,DAG1} = dd(Is,DAG0), - add_deps(N,I,DepTab,DAG1). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : add_deps -%% Argument : N - current node -%% Instr - current instr -%% DepTab - hashtable with {next-writer, next-readers} for reg -%% DAG - dependence graph -%% Returns : {DepTab, BlockInfo, DAG} - with new values -%% Description : Adds dependencies for node N to the graph. The registers that -%% node N defines and uses are used for computing the -%% dependencies to the following nodes. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -add_deps(N,Instr,DepTab,DAG) -> - {Ds,Us} = def_use(Instr), - Type = dd_type(Instr), - {DepTab1,DAG1} = add_write_deps(Ds,N,Type,DepTab,DAG), - add_read_deps(Us,N,Type,DepTab1,DAG1). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Instructions are classified into symbolic categories, -%% which are subsequently used to determine operation latencies -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -dd_type(Instr) -> - case Instr of - #b{} -> branch; - %% #br{} -> branch; - #call_link{} -> branch; - #jmp_link{} -> branch; - #jmp{} -> branch; - #goto{} -> branch; - #load{} -> load; - #store{} -> store; - #alu{} -> alu; - #move{} -> alu; - #multimove{} -> - Src = hipe_sparc:multimove_src(Instr), - Lat = round(length(Src)/2), - {mmove,Lat}; - #sethi{} -> alu; - #alu_cc{} -> alu_cc; - %% #cmov_cc{} -> cmov_cc; - %% #cmov_r{} -> alu; - #load_atom{} -> alu; - #load_address{} -> alu; - #pseudo_enter{} -> pseudo; - #pseudo_pop{} -> pseudo; - #pseudo_return{} -> pseudo; - #pseudo_spill{} -> pseudo; - #pseudo_unspill{} -> pseudo - end. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : add_write_deps -%% Argument : Defs - registers that node N defines. -%% N - current node -%% Ty - the type of current instr -%% DepTab - Dependence-table -%% DAG - The dependence graph. -%% Returns : {DepTab,DAG} - with new values -%% Description : Adds dependencies to the graph for nodes that depends on the -%% registers that N defines. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -add_write_deps([],_N,_Ty,DepTab,DAG) -> {DepTab,DAG}; -add_write_deps([D|Ds],N,Ty,DepTab,DAG) -> - {NewDepTab,NewDAG} = add_write_dep(D,N,Ty,DepTab,DAG), - add_write_deps(Ds,N,Ty,NewDepTab,NewDAG). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : add_write_dep -%% Description : Updates the dependence table with N as next writer, and -%% updates the DAG with the dependencies from N to subsequent -%% nodes. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -add_write_dep(X,N,Ty,DepTab,DAG) -> - {NxtWriter,NxtReaders} = lookup(X,DepTab), - NewDepTab = writer(X,N,Ty,DepTab), - NewDAG = write_deps(N,Ty,NxtWriter,NxtReaders,DAG), - {NewDepTab, NewDAG}. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : write_deps -%% Argument : Instr - Current instr -%% Ty - Type of current instr -%% NxtWriter - The node that is the next writer of the ragister -%% that Instr defines. -%% NxtReaders - The nodes that are subsequent readers of the -%% register that N defines. -%% DAG - The dependence graph -%% Returns : Calls raw_deps that finally returns a new DAG with the new -%% dependence arcs added. -%% Description : If a next writer exists a dependence arc for this node is -%% added, and after this raw_deps is called to compute the -%% arcs for read-after-write dependencies. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -write_deps(Instr,Ty,NxtWriter,NxtReaders,DAG) -> - DAG1 = case NxtWriter of - none -> - DAG; - {Instr,_} -> - DAG; - {Wr,WrTy} -> - dep_arc(Instr, - hipe_target_machine:waw_latency(Ty,WrTy), - Wr, DAG) - end, - raw_deps(Instr,Ty,NxtReaders,DAG1). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : raw_deps -%% Argument : Instr - current instr -%% Type - type of instr -%% Readers - subsequent readers -%% DAG - dependence graph -%% Returns : DAG - A new DAG with read-after-write dependencies added -%% Description : Updates the DAG with the dependence-arcs from Instr to the -%% subsequent readers, with the appropriate latencies. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -raw_deps(_Instr,_Type,[],DAG) -> DAG; -raw_deps(Instr,Ty,[{Rd,RdTy}|Xs],DAG) -> - raw_deps(Instr,Ty,Xs, - dep_arc(Instr,hipe_target_machine:raw_latency(Ty,RdTy), - Rd,DAG)). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : add_read_deps -%% Argument : Uses - The registers that node N uses. -%% N - Index of the current node. -%% Ty - Type of current node. -%% DepTab - Dependence table -%% DAG - Dependence graph -%% Returns : {DepTab, DAG} - with updated values. -%% Description : Adds the read dependencies from node N to subsequent ones, -%% according to the registers that N uses. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -add_read_deps([],_N,_Ty,DepTab,DAG) -> {DepTab,DAG}; -add_read_deps([U|Us],N,Ty,DepTab,DAG) -> - {NewDepTab,NewDAG} = add_read_dep(U,N,Ty,DepTab,DAG), - add_read_deps(Us,N,Ty,NewDepTab,NewDAG). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : add_read_dep -%% Argument : X - Used register -%% N - Index of checked instr -%% Ty - Type of checked instr -%% DepTab - Hashtable with {next-writer, next-readers} -%% DAG - Dependence graph -%% Returns : {DepTab, DAG} - with updated values -%% Description : Looks up what the next-writer/next-readers are, and adjusts -%% the table with current node as new reader. Finally -%% read-dependencies are added to the DAG. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -add_read_dep(X,N,Ty,DepTab,DAG) -> - {NxtWriter,_NxtReaders} = lookup(X,DepTab), - NewDepTab = reader(X,N,Ty,DepTab), - NewDAG = read_deps(N,Ty,NxtWriter,DAG), - {NewDepTab, NewDAG}. - -% If NxtWriter is 'none', then this var is not written subsequently -% Add WAR from Instr to NxtWriter (if it exists) -% *** UNFINISHED *** -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : read_deps -%% Argument : N - Index of current node -%% Ty - Type of current node -%% Writer - tuple {NextWriter, WrType} where NextWriter is the -%% subsequent instr that writes this register next time, -%% and WrType is the type of that instr. -%% DAG - The dependence graph -%% Returns : DAG -%% Description : Returns a new DAG if a next-writer exists, otherwise the old -%% DAG is returned. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -read_deps(_Instr,_Ty,none,DAG) -> - DAG; -read_deps(_Instr,_Ty,{_Instr,_},DAG) -> - DAG; -read_deps(Instr,Ty,{NxtWr,NxtWrTy},DAG) -> - dep_arc(Instr,hipe_target_machine:war_latency(Ty,NxtWrTy),NxtWr, - DAG). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : empty_deptab -%% Description : Creates an empty dependence table (hash-table) -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -empty_deptab() -> - gb_trees:empty(). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : lookup -%% Argument : X - key (register) -%% DepTab - dependence table -%% Returns : {NextWriter, NextReaders} -%% Description : Returns next writer and a list of following readers on -%% register X. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -lookup(X, DepTab) -> - case gb_trees:lookup(X, DepTab) of - none -> - {none, []}; - {value, {W, Rs} = Val} -> - Val - end. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : writer -%% Argument : X - key (register) -%% N - index of writer -%% Ty - type of writer -%% DepTab - dependence table to be updated -%% Returns : DepTab - new dependence table -%% Description : Sets N tobe next writer on X -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -writer(X, N, Ty, DepTab) -> - gb_trees:enter(X, {{N, Ty}, []}, DepTab). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : reader -%% Argument : X - key (register) -%% N - index of reader -%% Ty - type of reader -%% DepTab - dependence table to be updated -%% Returns : DepTab - new dependence table -%% Description : Adds N to the dependence table as a reader. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -reader(X,N,Ty,DepTab) -> - {W,Rs} = lookup(X,DepTab), - gb_trees:enter(X,{W,[{N,Ty}|Rs]},DepTab). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% The following version of md/2 separates heap- and stack operations, -%% which allows for greater reordering. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : md -%% Argument : IxBB - indexed block -%% DAG - dependence graph -%% Returns : DAG - new dependence graph -%% Description : Adds arcs for load/store dependencies to the DAG. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -md(IxBB, DAG) -> - md(IxBB,empty_md_state(),DAG). - -md([],_,DAG) -> DAG; -md([{N,I}|Is],St,DAG) -> - case md_type(I) of - other -> - md(Is,St,DAG); - {st,T} -> - { WAW_nodes, WAR_nodes, NewSt } = st_overlap(N,T,St), - md(Is,NewSt, - md_war_deps(WAR_nodes,N,md_waw_deps(WAW_nodes,N,DAG))); - {ld,T} -> - { RAW_nodes, NewSt } = ld_overlap(N,T,St), - md(Is,NewSt, - md_raw_deps(RAW_nodes,N,DAG)) - end. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : md_war_deps -%% Argument : WAR_nodes - write-after-read nodes depending on N -%% N - index of current instr -%% DAG - dependence graph -%% Returns : DAG - updated DAG -%% Description : Adds arcs for write-after-read dependencies for N -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -md_war_deps([],_,DAG) -> DAG; -md_war_deps([M|Ms],N,DAG) -> - md_war_deps(Ms,N,dep_arc(M,hipe_target_machine:m_war_latency(),N,DAG)). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : md_waw_deps -%% Argument : WAW_nodes - write-after-write nodes depending on N -%% N - index of current instr -%% DAG - dependence graph -%% Returns : DAG - updated DAG -%% Description : Adds arcs for write-after-write dependencies for N -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -md_waw_deps([],_,DAG) -> DAG; -md_waw_deps([M|Ms],N,DAG) -> - md_waw_deps(Ms,N,dep_arc(M,hipe_target_machine:m_waw_latency(),N,DAG)). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : md_raw_deps -%% Argument : RAW_nodes - read-after-write nodes depending on N -%% N - index of current instr -%% DAG - dependence graph -%% Returns : DAG - updated DAG -%% Description : Adds arcs for read-after-write dependencies for N -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -md_raw_deps([],_,DAG) -> DAG; -md_raw_deps([M|Ms],N,DAG) -> - md_raw_deps(Ms,N,dep_arc(M,hipe_target_machine:m_raw_latency(),N,DAG)). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : empty_md_state -%% Description : Returns an empty memorydependence state, eg. 4 lists -%% representing {StackStores, HeapStores, StackLoads, HeapLoads} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -empty_md_state() -> {[], [], [], []}. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : md_type -%% Argument : I - instr -%% Description : Maps the instr-type to a simplified type, telling if it's -%% store/load resp. heap or stack. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -md_type(I) -> - case I of - #load{} -> - Sp = hipe_sparc_registers:stack_pointer(), - Src = hipe_sparc:load_src(I), - N = hipe_sparc:reg_nr(Src), - Off = hipe_sparc:load_off(I), - if - N =:= Sp -> % operation on stack - {ld,{sp,Off}}; - true -> - {ld,{hp,Src,Off}} - end; - #store{} -> - Sp = hipe_sparc_registers:stack_pointer(), - Dst = hipe_sparc:store_dest(I), - N = hipe_sparc:reg_nr(Dst), - Off = hipe_sparc:store_off(I), - if - N =:= Sp -> - {st,{sp,Off}}; - true -> - {st,{hp,Dst,Off}} - end; - _ -> - other - end. - -%% Given a memory operation and a 'memory op state', -%% overlap(N,MemOp,State) returns { Preceding_Dependent_Ops, NewState }. -%% which are either a tuple { WAW_deps, WAR_deps } or a list RAW_deps. -%% -%% NOTES: -%% Note that Erlang's semantics ("heap stores never overwrite existing data") -%% means we can be quite free in reordering stores to the heap. -%% Ld/St to the stack are simply handled by their offsets; since we do not -%% rename the stack pointer, this is sufficient. -%% *** We assume all memory ops have uniform size = 4 *** -%% -%% NOTES: -%% The method mentioned above has now been changed because the assumption that -%% "heap stores never overwrite existing data" caused a bug when the -%% process-pointer was treated the same way as the heap. We were also told -%% that the semantics can possibly change in the future, so it would be more -%% safe to treat the heap store/loads as the stack. -%% A future improvement can be to do an alias analysis to give more freedom -%% in reordering stuff... -%% -%% Alias state: -%% { [StackOp], [HeapOp], [StackOp], [HeapOp] } -%% where StackOp = {InstrID, Offset} -%% HeapOp = {InstrID, Reg, Offset} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : st_overlap -%% Argument : N - Index of current node -%% Type - {sp,Off} or {hp,Dst,Off}, store on stack or heap -%% State - { [StackStrs], [HeapStrs], [StackLds], [HeapLds] } -%% where StackStrs/StackLds = {InstrID, Offset} -%% and HeapStrs/HeapLds = {InstrID, Reg, Offset} -%% Returns : { DepStrs, DepLds, State } - -%% where DepStrs/DepLds = [NodeId] -%% and State is the new state -%% Description : Adds dependencies for overlapping stores. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -st_overlap(N, {sp, Off}, {St_Sp, St_Hp, Ld_Sp, Ld_Hp}) -> - {DepSt, IndepSt_Sp} = st_sp_dep(St_Sp, Off), - {DepLd, IndepLd_Sp} = ld_sp_dep(Ld_Sp, Off), - {DepSt, DepLd, {[{N, Off}|IndepSt_Sp], St_Hp, IndepLd_Sp, Ld_Hp}}; -st_overlap(N, {hp, Dst, Off}, {St_Sp, St_Hp, Ld_Sp, Ld_Hp}) -> - DstOff = {Dst, Off}, - {DepSt,_IndepSt_Hp} = st_hp_dep(St_Hp, DstOff), - {DepLd, IndepLd_Hp} = ld_hp_dep(Ld_Hp, DstOff), - {DepSt, DepLd, {St_Sp, [{N, Dst, Off}|St_Hp], Ld_Sp, IndepLd_Hp}}. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : ld_overlap -%% Argument : N - Index of current node -%% Type - {sp,Off} or {hp,Dst,Off}, store on stack or heap -%% State - { [StackStrs], [HeapStrs], [StackLds], [HeapLds] } -%% where StackStrs/StackLds = {InstrID, Offset} -%% and HeapStrs/HeapLds = {InstrID, Reg, Offset} -%% Returns : { DepStrs, State } -%% Description : Adds dependencies for overlapping laods -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -ld_overlap(N, {sp, Off}, {St_Sp, St_Hp, Ld_Sp, Ld_Hp}) -> - DepSt = sp_dep_only(St_Sp, Off), - {DepSt, {St_Sp, St_Hp, [{N, Off}|Ld_Sp], Ld_Hp}}; -ld_overlap(N, {hp, Src, Off}, {St_Sp, St_Hp, Ld_Sp, Ld_Hp}) -> - DepSt = hp_dep_only(St_Hp, Src, Off), - {DepSt, {St_Sp, St_Hp, Ld_Sp, [{N, Src, Off}|Ld_Hp]}}. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : st_sp_dep -%% Description : Adds dependencies that are depending on a stack store -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -st_sp_dep(Stores, Off) -> - sp_dep(Stores, Off, [], []). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : ld_sp_dep -%% Description : Adds dependencies that are depending on a stack load -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -ld_sp_dep(Loads, Off) -> - sp_dep(Loads, Off, [], []). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : st_hp_dep -%% Description : Adds dependencies that are depending on a heap store -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -st_hp_dep(Stores, {_Reg, _Off} = RegOff) -> - hp_dep(Stores, RegOff, [], []). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : ld_hp_dep -%% Description : Adds dependencies that are depending on a heap load -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -ld_hp_dep(Loads, {_Reg, _Off} = RegOff) -> - hp_dep(Loads, RegOff, [], []). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : sp_dep -%% Description : Returns {Dependent, Independent} which are lists of nodes -%% that depends or not on a stack load/store -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -sp_dep([], _Off, Dep, Indep) -> {Dep, Indep}; -sp_dep([{N,Off}|Xs], Off, Dep, Indep) -> - sp_dep(Xs, Off, [N|Dep], Indep); -sp_dep([X|Xs], Off, Dep, Indep) -> - sp_dep(Xs, Off, Dep, [X|Indep]). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : hp_dep -%% Description : Returns {Dependent, Independent} which are lists of nodes -%% that depends or not on a heap load/store -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -hp_dep([], {_Reg,_Off}, Dep, Indep) -> {Dep,Indep}; -hp_dep([{N,Reg,Off1}|Xs], {Reg,Off}, Dep, Indep) when Off1 =/= Off -> - hp_dep(Xs, {Reg,Off}, Dep, [{N,Reg,Off1}|Indep]); -hp_dep([{N,_,_}|Xs], {Reg,Off}, Dep, Indep) -> - hp_dep(Xs, {Reg,Off}, [N|Dep], Indep). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : sp_dep_only -%% Description : Returns a list of nodes that are depending on a stack store -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -sp_dep_only(Stores, Off) -> - [N || {N,Off0} <- Stores, Off =:= Off0]. - -%% Dependences from heap stores to heap loads. -%% *** UNFINISHED *** -%% - but works -%% This is somewhat subtle: -%% - a heap load can only bypass a heap store if we KNOW it won't -%% load the stored value -%% - unfortunately, we do not know the relationships between registers -%% at this point, so we can't say that store(p+4) is independent of -%% load(q+0). -%% (OR CAN WE? A bit closer reasoning might show that it's possible?) -%% - We can ONLY say that st(p+c) and ld(p+c') are independent when c /= c' -%% -%% (As said before, it might be possible to lighten this restriction?) - -hp_dep_only([], _Reg, _Off) -> []; -hp_dep_only([{_N,Reg,Off_1}|Xs], Reg, Off) when Off_1 =/= Off -> - hp_dep_only(Xs, Reg, Off); -hp_dep_only([{N,_,_}|Xs], Reg, Off) -> - [N|hp_dep_only(Xs, Reg, Off)]. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Control dependences: -%% - add dependences so that -%% * branches are performed in order -%% * unsafe operations are 'fenced in' by surrounding branches -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : cd -%% Argument : IxBB - indexed block -%% DAG - dependence graph -%% Returns : DAG - new dependence graph -%% Description : Adds conditional dependencies to the DAG -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -cd(IxBB,DAG) -> - cd(IxBB, DAG, none, [], []). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : cd -%% Argument : IxBB - indexed block -%% DAG - dependence graph -%% PrevBr - previous branch -%% PrevUnsafe - previous unsafe instr (mem-op) -%% PrevOthers - previous other instrs, used to "fix" preceeding -%% instrs so they don't bypass a branch. -%% Returns : DAG - new dependence graph -%% Description : Adds conditional dependencies to the graph. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -cd([], DAG, _PrevBr, _PrevUnsafe, _PrevOthers) -> - DAG; -cd([{N,I}|Xs], DAG, PrevBr, PrevUnsafe, PrevOthers) -> - case cd_type(I) of - {branch,Ty} -> - DAG1 = cd_branch_to_other_deps(N, PrevOthers, DAG), - NewDAG = cd_branch_deps(PrevBr, PrevUnsafe, N, Ty, DAG1), - cd(Xs,NewDAG,{N,Ty},[],[]); - {unsafe,Ty} -> - NewDAG = cd_unsafe_deps(PrevBr,N,Ty,DAG), - cd(Xs, NewDAG, PrevBr, [{N,Ty}|PrevUnsafe], PrevOthers); - {other,_Ty} -> - cd(Xs, DAG, PrevBr, PrevUnsafe, [N|PrevOthers]) - end. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : cd_branch_to_other_deps -%% Argument : N - index of branch -%% Ms - list of indexes of "others" preceding instrs -%% DAG - dependence graph -%% Returns : DAG - new graph -%% Description : Makes preceding instrs fixed so they don't bypass a branch -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -cd_branch_to_other_deps(_, [], DAG) -> - DAG; -cd_branch_to_other_deps(N, [M | Ms], DAG) -> - cd_branch_to_other_deps(N, Ms, dep_arc(M, zero_latency(), N, DAG)). - -%% Is the operation a branch, an unspeculable op or something else? - -%% Returns -%% {branch,BranchType} -%% {unsafe,OpType} -%% {other,OpType} - -%% *** UNFINISHED *** -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : cd_type -%% Argument : I - instr -%% Description : Maps instrs to a simpler type. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -cd_type(I) -> - case I of - #goto{} -> - {branch,uncond}; - #br{} -> - {branch,'cond'}; - #b{} -> - {branch,'cond'}; - #call_link{} -> - {branch,call}; - #jmp_link{} -> - {branch,call}; - #jmp{} -> - {branch,call}; - #load{} -> - {unsafe,load}; - #store{} -> - {unsafe,load}; - T -> - {other,T} - end. - -%% add dependences to keep order of branches + unspeculable ops: -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : cd_branch_deps -%% Argument : PrevBr - preceeding branch -%% PrevUnsafe - preceeding unsafe ops, eg, mem-ops -%% N - current id. -%% Ty - type of current instr -%% DAG - dependence graph -%% Returns : DAG - new DAG -%% Description : Adds arcs between branches and calls deps_to_unsafe that adds -%% arcs between branches and unsafe ops. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -cd_branch_deps(PrevBr, PrevUnsafe, N, Ty, DAG) -> - DAG1 = case PrevBr of - none -> - DAG; - {Br,BrTy} -> - dep_arc(Br, - hipe_target_machine:br_br_latency(BrTy,Ty), - N, DAG) - end, - deps_to_unsafe(PrevUnsafe, N, Ty, DAG1). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : deps_to_unsafe -%% Description : Adds dependencies between unsafe's and branches -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -deps_to_unsafe([], _, _, DAG) -> DAG; -deps_to_unsafe([{M,UTy}|Us], N, Ty, DAG) -> - deps_to_unsafe(Us,N,Ty, - dep_arc(M, hipe_target_machine:unsafe_to_br_latency(UTy,Ty), - N, DAG)). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : cd_unsafe_deps -%% Description : Adds dependencies between branches and unsafe's -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -cd_unsafe_deps(none, _, _, DAG) -> - DAG; -cd_unsafe_deps({Br,BrTy}, N, Ty, DAG) -> - dep_arc(Br, hipe_target_machine:br_to_unsafe_latency(BrTy, Ty), N, DAG). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : def_use -%% Argument : Instr -%% Description : Returns the registers that Instr defines resp. uses as 2 lists -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -def_use(Instr) -> - {hipe_sparc:defines(Instr), hipe_sparc:uses(Instr)}. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Function : move_or_alu -%% Description : True if the instruction is a move or an alu; false otherwise -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -move_or_alu(#move{}) -> true; -move_or_alu(#alu{}) -> true; -move_or_alu(_) -> false. - -%% Debugging stuff below %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - --ifdef(debug1). -debug1_stuff(Blk, DAG, IxBlk, Sch, X) -> - io:format("Blk: ~p~n",[Blk]), - io:format("DAG: ~n~p~n~p",[DAG,IxBlk]), - io:format("~n"), - print_instrs(IxBlk), - print_sch(Sch, IxBlk), - print_instrs2(X). - -print_instrs([]) -> - io:format("~n"); -print_instrs([{N,Instr} | Instrs]) -> - io:format("(~p): ",[N]), - hipe_sparc_pp:pp_instr(Instr), - io:format("~p~n",[element(1,Instr)]), - print_instrs(Instrs). - -print_instrs2([]) -> - io:format("~n"); -print_instrs2([Instr | Instrs]) -> - hipe_sparc_pp:pp_instr(Instr), - print_instrs2(Instrs). - -print_sch([],_) -> io:format("~n"); -print_sch([{{cycle,Cycle},{node,I}} | Rest], IxBlk) -> - io:format("{C~p, N~p} ",[Cycle,I]), - print_node(I, IxBlk), - print_sch(Rest, IxBlk). - -print_node(_, []) -> - io:format("~n"); -print_node(I, [{I, Instr} | _]) -> - hipe_sparc_pp:pp_instr(Instr); -print_node(I, [_ | IxBlk]) -> - print_node(I, IxBlk). --else. -debug1_stuff(_Blk, _DAG, _IxBlk, _Sch, _X) -> - ok. --endif. diff --git a/lib/hipe/opt/hipe_schedule_prio.erl b/lib/hipe/opt/hipe_schedule_prio.erl deleted file mode 100644 index 339bb82aab..0000000000 --- a/lib/hipe/opt/hipe_schedule_prio.erl +++ /dev/null @@ -1,53 +0,0 @@ -%% -*- erlang-indent-level: 2 -*- -%% -%% Licensed under the Apache License, Version 2.0 (the "License"); -%% you may not use this file except in compliance with the License. -%% You may obtain a copy of the License at -%% -%% http://www.apache.org/licenses/LICENSE-2.0 -%% -%% Unless required by applicable law or agreed to in writing, software -%% distributed under the License is distributed on an "AS IS" BASIS, -%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -%% See the License for the specific language governing permissions and -%% limitations under the License. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% PRIORITY HANDLING AND PRIORITY CALCULATION -%% -%% Handling of ready nodes and priorities. -%% - at present, all nodes have the same priority and so on. -%% -%% *** UNFINISHED *** -%% - should compute a static priority estimate -%% - should dynamically modify priorities + possibly insert NOPs -%% (e.g., to separate branches, etc.) -%% - thus, ought to be passed the current schedule and/or resources as well - --module(hipe_schedule_prio). --export([init_ready/2, - init_instr_prio/2, - %% initial_ready_set/4, - next_ready/7, - add_ready_nodes/2, - insert_node/3 - ]). - -init_ready(Size,Preds) -> - hipe_ultra_prio:init_ready(Size,Preds). - -init_instr_prio(N,DAG) -> - hipe_ultra_prio:init_instr_prio(N,DAG). - -%% initial_ready_set(M,N,Preds,Ready) -> -%% hipe_ultra_prio:initial_ready_set(M,N,Preds,Ready). - -next_ready(C,Ready,Prio,Nodes,DAG,Preds,Earl) -> - hipe_ultra_prio:next_ready(C,Ready,Prio,Nodes,DAG,Preds,Earl). - -add_ready_nodes(NodeLst,Ready) -> - hipe_ultra_prio:add_ready_nodes(NodeLst,Ready). - -insert_node(C,I,Ready) -> - hipe_ultra_prio:insert_node(C,I,Ready). diff --git a/lib/hipe/opt/hipe_target_machine.erl b/lib/hipe/opt/hipe_target_machine.erl deleted file mode 100644 index 75993cb95e..0000000000 --- a/lib/hipe/opt/hipe_target_machine.erl +++ /dev/null @@ -1,87 +0,0 @@ -%% Licensed under the Apache License, Version 2.0 (the "License"); -%% you may not use this file except in compliance with the License. -%% You may obtain a copy of the License at -%% -%% http://www.apache.org/licenses/LICENSE-2.0 -%% -%% Unless required by applicable law or agreed to in writing, software -%% distributed under the License is distributed on an "AS IS" BASIS, -%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -%% See the License for the specific language governing permissions and -%% limitations under the License. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% INTERFACE TO TARGET MACHINE MODEL -%% -%% Interfaces the instruction scheduler to the (resource) machine model. - --module(hipe_target_machine). --export([init_resources/1, - init_instr_resources/2, - resources_available/4, - advance_cycle/1 - ]). --export([raw_latency/2, - war_latency/2, - waw_latency/2, - %% m_raw_latency/2, - %% m_war_latency/2, - %% m_waw_latency/2, - m_raw_latency/0, - m_war_latency/0, - m_waw_latency/0, - br_to_unsafe_latency/2, - unsafe_to_br_latency/2, - br_br_latency/2 - ]). - --define(target,hipe_ultra_mod2). - -init_resources(X) -> - ?target:init_resources(X). - -init_instr_resources(X,Y) -> - ?target:init_instr_resources(X,Y). - -resources_available(X,Y,Z,W) -> - ?target:resources_available(X,Y,Z,W). - -advance_cycle(X) -> - ?target:advance_cycle(X). - -raw_latency(From,To) -> - ?target:raw_latency(From,To). - -war_latency(From,To) -> - ?target:war_latency(From,To). - -waw_latency(From,To) -> - ?target:waw_latency(From,To). - -%% m_raw_latency(From,To) -> -%% ?target:m_raw_latency(From,To). - -%% m_war_latency(From,To) -> -%% ?target:m_war_latency(From,To). - -%% m_waw_latency(From,To) -> -%% ?target:m_waw_latency(From,To). - -m_raw_latency() -> - ?target:m_raw_latency(). - -m_war_latency() -> - ?target:m_war_latency(). - -m_waw_latency() -> - ?target:m_waw_latency(). - -br_to_unsafe_latency(Br,U) -> - ?target:br_to_unsafe_latency(Br,U). - -unsafe_to_br_latency(U,Br) -> - ?target:unsafe_to_br_latency(U,Br). - -br_br_latency(Br1,Br2) -> - ?target:br_br_latency(Br1,Br2). diff --git a/lib/hipe/opt/hipe_ultra_mod2.erl b/lib/hipe/opt/hipe_ultra_mod2.erl deleted file mode 100644 index cec9c56a1e..0000000000 --- a/lib/hipe/opt/hipe_ultra_mod2.erl +++ /dev/null @@ -1,233 +0,0 @@ -%% Licensed under the Apache License, Version 2.0 (the "License"); -%% you may not use this file except in compliance with the License. -%% You may obtain a copy of the License at -%% -%% http://www.apache.org/licenses/LICENSE-2.0 -%% -%% Unless required by applicable law or agreed to in writing, software -%% distributed under the License is distributed on an "AS IS" BASIS, -%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -%% See the License for the specific language governing permissions and -%% limitations under the License. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% ULTRASPARC MACHINE MODEL -%% -%% This module is used by the scheduler. -%% The following interface is used: -%% ... -%% -%% NOTES: -%% - the machine model is simple (on the verge of simplistic) -%% * all FUs are pipelined => model only one cycle at a time -%% * instruction latencies are mostly 1 -%% * floating point is left for later (I _think_ it works, but ...) -%% - conservative: instructions that require multiple resources are -%% modelled as 'single'; instead, they could reserve IEU+BR or whatever -%% - possibly inefficient: I think machine state model could be turned into -%% a bitvector. - --module(hipe_ultra_mod2). --export([init_resources/1, - init_instr_resources/2, - resources_available/4, - advance_cycle/1 - ]). --export([raw_latency/2, - war_latency/2, - waw_latency/2, - %% m_raw_latency/2, - %% m_war_latency/2, - %% m_waw_latency/2, - m_raw_latency/0, - m_war_latency/0, - m_waw_latency/0, - br_to_unsafe_latency/2, - unsafe_to_br_latency/2, - br_br_latency/2 - ]). - --include("../sparc/hipe_sparc.hrl"). - --define(debug(Str,Args),ok). -%-define(debug(Str,Args),io:format(Str,Args)). - --define(debug_ultra(Str,Args),ok). -%-define(debug_ultra(Str,Args),io:format(Str,Args)). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% Straightforward and somewhat simplistic model for UltraSparc: -%% - only one cycle at a time is modelled -%% - resources are simplified: -%% * ieu0, ieu1, ieu, mem, br, single -%% * per-cycle state = done | { I0, I1, NumI, X, Mem, Br } -%% * unoptimized representation (could be bit vector) - -init_resources(_Size) -> - ?debug_ultra('init res ~p~n',[_Size]), - empty_state(). - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -init_instr_resources(N,Nodes) -> - ultra_instr_rsrcs(Nodes,hipe_vectors:new(N, '')). - -ultra_instr_rsrcs([],I_res) -> I_res; -ultra_instr_rsrcs([N|Ns],I_res) -> - ultra_instr_rsrcs(Ns,ultra_instr_type(N,I_res)). - -ultra_instr_type({N,I},I_res) -> - hipe_vectors:set(I_res,N-1,instr_type(I)). - -instr_type(I) -> - case I of - #move{} -> - ieu; - #multimove{} -> %% TODO: expand multimoves before scheduling - ieu; - #alu{} -> - case hipe_sparc:alu_operator(I) of - '>>' -> ieu0; - '<<' -> ieu0; - _ -> ieu - end; - #alu_cc{} -> - ieu1; - #sethi{} -> - ieu; - #load{} -> - mem; - #store{} -> - mem; - #b{} -> - br; - #br{} -> - br; - #goto{} -> - br; - #jmp_link{} -> % imprecise; should be mem+br? - single; - #jmp{} -> % imprecise - br; - #call_link{} -> % imprecise; should be mem+br? - single; - #cmov_cc{} -> % imprecise - single; - #cmov_r{} -> % imprecise - single; - #load_atom{} -> % should be resolved to sethi/or - single; - #load_address{} -> % should be resolved to sethi/or - single; - #load_word_index{} -> % should be resolved to sethi/or - single; - %% uncommon types: - #label{} -> - none; - #nop{} -> - none; - #comment{} -> - none; - _ -> - exit({ultrasparc_instr_type,{cant_schedule,I}}) - end. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -resources_available(_Cycle, I, Rsrc, I_res) -> - res_avail(instruction_resource(I_res, I), Rsrc). - -instruction_resource(I_res, I) -> - hipe_vectors:get(I_res, I-1). - -%% The following function checks resource availability. -%% * all function units are assumed to be fully pipelined, so only -%% one cycle at a time is modelled. -%% * for IEU0 and IEU1, these must precede all generic IEU instructions -%% (handled by X bit) -%% * at most 2 integer instructions can issue in a cycle -%% * mem is straightforward -%% * br closes the cycle (= returns done). -%% * single requires an entirely empty state and closes the cycle - -res_avail(ieu0, { free, I1, NumI, free, Mem, Br }) - when is_integer(NumI), NumI < 2 -> - { yes, { occ, I1, NumI+1, free, Mem, Br }}; -res_avail(ieu1, { _I0, free, NumI, free, Mem, Br }) - when is_integer(NumI), NumI < 2 -> - { yes, { free, occ, NumI+1, free, Mem, Br }}; -res_avail(ieu, { I0, I1, NumI, _X, Mem, Br }) - when is_integer(NumI), NumI < 2 -> - { yes, { I0, I1, NumI+1, occ, Mem, Br }}; -res_avail(mem, { I0, I1, NumI, X, free, Br }) -> - { yes, { I0, I1, NumI, X, occ, Br }}; -res_avail(br, { _I0, _I1, _NumI, _X, _Mem, free }) -> - { yes, done }; -res_avail(single, { free, free, 0, free, free, free }) -> - { yes, done }; -res_avail(_, _) -> - no. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -advance_cycle(_Rsrc) -> - empty_state(). - -empty_state() -> { free, free, 0, free, free, free }. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% Latencies are taken from UltraSparc hardware manual -%% -%% *** UNFINISHED *** -%% more precisely, they are taken from my memory of the US-manual -%% at the moment. -%% -%% Note: all ld/st are assumed to hit in the L1 cache (D-cache), -%% which is sort of imprecise. - -raw_latency(alu, store) -> 0; -raw_latency(load, _) -> 2; % only if load is L1 hit -raw_latency(alu_cc, b) -> 0; -raw_latency(_I0, _I1) -> - 1. - -war_latency(_I0, _I1) -> - 0. - -waw_latency(_I0, _I1) -> - 1. - -%% *** UNFINISHED *** -%% At present, all load/stores are assumed to hit in the L1 cache, -%% which isn't really satisfying. - -%% m_raw_latency(_St, _Ld) -> -%% 1. -%% -%% m_war_latency(_Ld, _St) -> -%% 1. -%% -%% m_waw_latency(_St1, _St2) -> -%% 1. - -%% Use these for 'default latencies' = do not permit reordering. - -m_raw_latency() -> - 1. - -m_war_latency() -> - 1. - -m_waw_latency() -> - 1. - -br_to_unsafe_latency(_BrTy, _UTy) -> - 0. - -unsafe_to_br_latency(_UTy, _BrTy) -> - 0. - -br_br_latency(_BrTy1, _BrTy2) -> - 0. diff --git a/lib/hipe/opt/hipe_ultra_prio.erl b/lib/hipe/opt/hipe_ultra_prio.erl deleted file mode 100644 index 6dd240a33a..0000000000 --- a/lib/hipe/opt/hipe_ultra_prio.erl +++ /dev/null @@ -1,298 +0,0 @@ -%% Licensed under the Apache License, Version 2.0 (the "License"); -%% you may not use this file except in compliance with the License. -%% You may obtain a copy of the License at -%% -%% http://www.apache.org/licenses/LICENSE-2.0 -%% -%% Unless required by applicable law or agreed to in writing, software -%% distributed under the License is distributed on an "AS IS" BASIS, -%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -%% See the License for the specific language governing permissions and -%% limitations under the License. -%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% -%% 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). - |