diff options
Diffstat (limited to 'lib/hipe/opt/hipe_spillmin_scan.erl')
| -rw-r--r-- | lib/hipe/opt/hipe_spillmin_scan.erl | 559 |
1 files changed, 559 insertions, 0 deletions
diff --git a/lib/hipe/opt/hipe_spillmin_scan.erl b/lib/hipe/opt/hipe_spillmin_scan.erl new file mode 100644 index 0000000000..c58906c389 --- /dev/null +++ b/lib/hipe/opt/hipe_spillmin_scan.erl @@ -0,0 +1,559 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2005-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% +%% +%% =========================================================================== +%% Copyright (c) 2002 by Niklas Andersson, Andreas Lundin, and Erik Johansson. +%% =========================================================================== +%% Module : hipe_spillmin_scan +%% Purpose : Optimizes the number of stack slots used by using a +%% "linear-scan algorithm" to allocate stack slots. +%% Notes : * This is a simplified implementation of +%% "Linear Scan Register Allocation" by +%% Massimiliano Poletto & Vivek Sarkar described in +%% ACM TOPLAS Vol 21, No 5, September 1999. +%% +%% * This implementation is target-independent and +%% requires a target specific interface module +%% as argument. +%% +%% * Based on the hipe_ls_regalloc module by Erik Johansson +%% +%% History : * 2002-04-01, NA & AL: Created +%% * 2002-10-08, Happi: Cleanup and speedup +%% ============================================================================ +%% Exported functions (short description): +%% stackalloc(CFG, StackSlots, SpillIndex, Options, Target, TempMap) -> +%% {Coloring, NumberOfSpills} +%% Takes a CFG and the TempMap from register allocation and returns +%% a coloring of stack slots. +%% StackSlots should be a list of used stack slots, usually empty at +%% first call to function. +%% SpillIndex is the the first position we will spill to, usually 0. +%% TempMap is the TempMap from the register allocation +%% +%% The Coloring will be in the form of the "allocation datastructure" +%% described below, that is, a list of tuples on the form +%% {Name, {spill, SpillIndex}} +%% The NumberOfSpills is either 0 indicating no spill or the +%% SpillIndex of the last spilled register. +%% +%% mapmerge +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-module(hipe_spillmin_scan). + +-export([stackalloc/6]). + +%%-define(DEBUG, 1). +-define(HIPE_INSTRUMENT_COMPILER, true). + +%%---------------------------------------------------------------------------- + +-include("../main/hipe.hrl"). +-include("../flow/cfg.hrl"). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% stackalloc(CFG, StackSlots, SpillIndex, Options, Target, TempMap) +%% Calculates an allocation of stack slots using a linear_scan algorithm. +%% There are three steps in the algorithm: +%% 1. Calculate live-ranges for all spilled temporaries. +%% 2. Calculate live-intervals for each temporary. +%% The live interval consists of a start position and a end position +%% these are the first definition and last use of the temporary +%% given as instruction numbers in a breadth-first traversal of the +%% control-flow-graph. +%% 3. Do a linear scan allocation over the live intervals. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-spec stackalloc(#cfg{}, [_], non_neg_integer(), + comp_options(), module(), hipe_temp_map()) -> + {hipe_spill_map(), non_neg_integer()}. + +stackalloc(CFG, StackSlots, SpillIndex, Options, Target, TempMap) -> + ?debug_msg("LinearScan: ~w\n", [erlang:statistics(runtime)]), + %% Step 1: Calculate liveness (Call external implementation.) + Liveness = liveness(CFG, Target), + ?debug_msg("liveness (done)~w\n", [erlang:statistics(runtime)]), + USIntervals = calculate_intervals(CFG, Liveness, Options, + Target, TempMap), + %% ?debug_msg("intervals (done) ~w\n", [erlang:statistics(runtime)]), + Intervals = sort_on_start(USIntervals), + ?debug_msg("sort intervals (done) ~w\n", [erlang:statistics(runtime)]), + ?debug_msg("Intervals ~w\n", [Intervals]), + ?debug_msg("No intervals: ~w\n", [length(Intervals)]), + ?debug_msg("count intervals (done) ~w\n", [erlang:statistics(runtime)]), + Allocation = allocate(Intervals, StackSlots, SpillIndex, Target), + ?debug_msg("allocation (done) ~w\n", [erlang:statistics(runtime)]), + Allocation. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% %% +%% Step 2: Calculate live-intervals for each temporary. %% +%% %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% calculate_intervals(CFG, Liveness, Options, Target, TempMap) +%% CFG: The Control-Flow Graph. +%% Liveness: A map of live-in and live-out sets for each Basic-Block. +%% TempMap: The TempMap from the register allocation +%% +%% This function will only consider the intervals of the temporaries +%% that have been spilled during register allocation, and will ignore +%% all other. +%%- - - - - - - - - - - - - - - - - - - - - - - - +calculate_intervals(CFG, Liveness, _Options, Target, TempMap) -> + Interval = empty_interval(Target:number_of_temporaries(CFG)), + Worklist = Target:reverse_postorder(CFG), + intervals(Worklist, Interval, 1, CFG, Liveness, Target, TempMap). + +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% intervals(WorkList, Intervals, InstructionNr, +%% CFG, Liveness, Target, TempMap) +%% WorkList: List of BB-names to handle. +%% Intervals: Intervals seen so far (sorted on register names). +%% InstructionNr: The number of examined instructions. +%% CFG: The Control-Flow Graph. +%% Liveness: A map of live-in and live-out sets for each Basic-Block. +%% Target: The backend for which we generate native code. +%% TempMap: The TempMap from the register allocation +%% +%% This function will only consider the intervals of the temporaries +%% that have been spilled during register allocation, and will ignore +%% all other. +%%- - - - - - - - - - - - - - - - - - - - - - - - +intervals([L|ToDO], Intervals, InstructionNr, CFG, Liveness, Target, + TempMap) -> + ?debug_msg("Block ~w\n", [L]), + %% Add all variables that are live at the entry of this block + %% to the interval data structure. + + %% Only consider spilled temporaries in LiveIn + LiveIn = [X || X <- livein(Liveness, L, Target), + hipe_temp_map:is_spilled(X, TempMap)], + Intervals2 = add_def_point(LiveIn, InstructionNr, Intervals), + + %% Only consider spilled temporaries in LiveOut + LiveOut = [X2 || X2 <- liveout(Liveness, L, Target), + hipe_temp_map:is_spilled(X2, TempMap)], + ?debug_msg("In ~w -> Out ~w\n", [LiveIn, LiveOut]), + + %% Traverse this block instruction by instruction and add all + %% uses and defines to the intervals. + Code = hipe_bb:code(bb(CFG, L, Target)), + {Intervals3, NewINr} = traverse_block(Code, InstructionNr+1, + Intervals2, Target, TempMap), + + %% Add end points for the temporaries that are in the live-out set. + Intervals4 = add_use_point(LiveOut, NewINr+1, Intervals3), + + intervals(ToDO, Intervals4, NewINr+1, CFG, Liveness, Target, TempMap); +intervals([], Intervals, _, _, _, _, _) -> + %% Return the calculated intervals + interval_to_list(Intervals). + %% Intervals. + +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% traverse_block(Code, InstructionNo, Intervals, Unchanged) +%% Examine each instruction in the Code: +%% For each temporary T used or defined by instruction number N: +%% extend the interval of T to include N. +%% TempMap: The TempMap from the register allocation +%% +%% This function will only consider the the instruction that have temporaries +%% that have been spilled during register allocation, and will ignore +%% all other. +%%- - - - - - - - - - - - - - - - - - - - - - - - + +traverse_block([Instruction|Is], InstrNo, Intervals, Target, TempMap) -> + %% Get used temps. + %% Only consider spilled temporaries in the Use set. + UsesSet = [X || X <- uses(Instruction, Target), + hipe_temp_map:is_spilled(X, TempMap)], + %% Get defined temps. + %% Only consider spilled temporaries in the Def set. + DefsSet = [X2 || X2 <- defines(Instruction, Target), + hipe_temp_map:is_spilled(X2, TempMap)], + %% Only consider those temps that starts or ends their lifetime + %% within the basic block (that is remove all Unchanged temps). + Intervals1 = add_def_point( DefsSet, InstrNo, Intervals), + %% Extend the intervals for these temporaries to include InstrNo. + Intervals2 = add_use_point(UsesSet, InstrNo, Intervals1), + %% Handle the next instruction. + traverse_block(Is, InstrNo+1, Intervals2, Target, TempMap); +traverse_block([], InstrNo, Intervals, _, _) -> + %% Return the new intervals and the number of the next instruction. + {Intervals,InstrNo}. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% %% +%% Step 3. Do a linear scan allocation over the live intervals. %% +%% %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% allocate(Intervals, PhysicalRegisters, Target) +%% +%% This function performs the linear scan algorithm. +%% Intervals contains the start and stop position of each spilled temporary, +%% sorted on increasing startpositions +%% StackSlots is a list of available Stack slots to use. If they run out a +%% new stack slot is allocated from an (in theory) infinite domain. +%% +%%- - - - - - - - - - - - - - - - - - - - - - - - +allocate(Intervals, StackSlots, SpillIndex, Target) -> + AllocatedSlots = empty_allocation(), + allocate(Intervals, StackSlots, [], AllocatedSlots, SpillIndex, Target). + +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% allocate(Intervals, Free, Active, Allocated, SpillIndex, Target) +%% Iterates on each temporary interval. +%% Intervals: The list of temporary intervals. +%% Free: Currently available stack slots. +%% Active: Currently used stack slots (sorted on increasing +%% interval enpoints) +%% Allocated: The mapping of register names to spill positions. +%% SpillIndex: The number of spilled registers. +%%- - - - - - - - - - - - - - - - - - - - - - - - +allocate([TempInt|TIS], Free, Active, Alloc, SpillIndex, Target) -> + %% Remove from the active list those temporaries whose interval + %% ends before the start of the current interval. + {NewActive, NewFree} = + expire_old_intervals(Active, startpoint(TempInt), Free, Target), + %% Get the name of the temp in the current interval. + Temp = reg(TempInt), + case NewFree of + [] -> + %% There are no free spill slots, so we allocate a new one + NewSpillIndex = SpillIndex+1, + NewAlloc = spillalloc(Temp, SpillIndex, Alloc), + NewActive2 = add_active(endpoint(TempInt), SpillIndex, NewActive), + allocate(TIS, NewFree, NewActive2, NewAlloc, NewSpillIndex, Target); + [FreeSpillslot | Spillslots] -> + %% The spill slot FreeSpillSlot is available, let's use it. + allocate(TIS, Spillslots, + add_active(endpoint(TempInt), FreeSpillslot, NewActive), + spillalloc(Temp, FreeSpillslot, Alloc), + SpillIndex, Target) + end; +allocate([], _, _, Alloc, SpillIndex, _) -> + %% No more register intervals to handle; + %% return the result sorted on regnames. + {lists:sort(Alloc), SpillIndex}. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% expire_old_intervals(ActiveTemps, CurrentPos, FreeRegisters) +%% Remove all temporaries that have live-ranges that ends before the +%% current position from the active list and put them into the free +%% list instead. +%% +%% --------------------------------------------------------------------- +expire_old_intervals([Act|Acts] = AllActives, CurrentPos, Free, Target) -> + %% Does the live-range of the first active register end before + %% the current position? + + %% We expand multimove before regalloc, ignore the next 2 lines. + %% %% We don't free registers that end at the current position, + %% %% since a multimove can decide to do the moves in another order... + case active_endpoint(Act) =< CurrentPos of + true -> %% Yes -> Then we can free that register. + Spillslot = active_spillslot(Act), + %% Add the spillslot to the free pool. + NewFree = [Spillslot|Free], + %% Here we could try appending the register to get a more + %% widespread use of registers. + %% Free ++ [active_spillslot(Act)]); + expire_old_intervals(Acts, CurrentPos, NewFree, Target); + false -> + %% No -> Then we cannot free any more temporaries. + %% (Since they are sorted on endpoints...) + {AllActives, Free} + end; +expire_old_intervals([], _, Free, _) -> + {[], Free}. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% %% +%% D A T A S T R U C T U R E S %% +%% & %% +%% A U X I L I A R Y F U N C T I O N S %% +%% %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% The "allocation datastructure" +%% +%% This is an order list of register names paired with their allocations. +%% {Name, Allocation} +%% Since we are only dealing with spills, the allocation will look like: +%% {spill, SpillIndex} +%% +%% --------------------------------------------------------------------- + +empty_allocation() -> []. + +spillalloc(Name, N, Allocation) -> [{Name,{spill,N}}|Allocation]. + +%% spillalloc(Name,N,[{Name,_}|A]) -> +%% ?debug_msg("Spilled ~w\n",[Name]), +%% [{Name,{spill,N}}|A]; +%% spillalloc(Name,N,[{Name2,Binding}|Bindings]) when Name > Name2 -> +%% [{Name2,Binding}|spillalloc(Name,N,Bindings)]; +%% spillalloc(Name,N,Bindings) -> +%% [{Name,{spill,N}}|Bindings]. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% The active datastructure. +%% Keeps tracks of currently active (allocated) spill slots. +%% It is sorted on end points in the intervals +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +add_active(Endpoint, SpillSlot, [A1={P1,_}|Active]) when P1 < Endpoint -> + [A1|add_active(Endpoint, SpillSlot, Active)]; +add_active(Endpoint, SpillSlot, Active) -> + [{Endpoint, SpillSlot}|Active]. + +active_spillslot({_,SpillSlot}) -> + SpillSlot. + +active_endpoint({EndPoint,_}) -> + EndPoint. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% The Interval data structure. +%% +%%- - - - - - - - - - - - - - - - - - - - - - - - + +%% mk_interval(Name, Start, End) -> +%% {Name, Start, End}. + +endpoint({_R,_S,Endpoint}) -> + Endpoint. + +startpoint({_R,Startpoint,_E}) -> + Startpoint. + +reg({RegName,_S,_E}) -> + RegName. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% The Intervals data structure. + +sort_on_start(I) -> + lists:keysort(2, I). + +-ifdef(gb_intervals). +empty_interval(_) -> + gb_trees:empty(). + +interval_to_list(Intervals) -> + lists:flatten( + lists:map( + fun({T, I}) when is_list(I) -> + lists:map( + fun ({none, End}) -> + {T,End,End}; + ({Beg, none}) -> + {T,Beg, Beg} + end, + I); + ({T,{B,E}}) -> {T, B, E} + end, + gb_trees:to_list(Intervals))). + +add_use_point([Temp|Temps], Pos, Intervals) -> + %% Extend the old interval... + NewInterval = + case gb_trees:lookup(Temp, Intervals) of + %% This temp has an old interval... + {value, Value} -> + %% ... extend it. + extend_interval(Pos, Value); + %% This is the first time we see this temp... + none -> + %% ... create a new interval + {Pos, Pos} + end, + %% Add or update the extended interval. + Intervals2 = gb_trees:enter(Temp, NewInterval, Intervals), + %% Add the rest of the temporaries. + add_use_point(Temps, Pos, Intervals2); +add_use_point([], _, I) -> + %% No more to add return the interval. + I. + +add_def_point([Temp|Temps], Pos, Intervals) -> + %% Extend the old interval... + NewInterval = + case gb_trees:lookup(Temp, Intervals) of + %% This temp has an old interval... + {value, Value} -> + %% ... extend it. + extend_interval(Pos, Value); + %% This is the first time we see this temp... + none -> + %% ... create a new interval + {Pos, Pos} + end, + %% Add or update the extended interval. + Intervals2 = gb_trees:enter(Temp, NewInterval, Intervals), + %% Add the rest of the temporaries. + add_def_point(Temps, Pos, Intervals2); +add_def_point([], _, I) -> + %% No more to add return the interval. + I. + +extend_interval(Pos, {Beginning, End}) -> + %% If this position occurs before the beginning of the interval, + %% then extend the beginning to this position. + NewBeginning = erlang:min(Pos, Beginning), + %% If this position occurs after the end of the interval, then + %% extend the end to this position. + NewEnd = erlang:max(Pos, End), + {NewBeginning, NewEnd}. + +extend_def_interval(Pos, {Beginning, End}) -> + %% If this position occurs before the beginning of the interval, + %% then extend the beginning to this position. + NewBeginning = erlang:min(Pos, Beginning), + %% If this position occurs after the end of the interval, then + %% extend the end to this position. + NewEnd = erlang:max(Pos, End), + {NewBeginning, NewEnd}; +extend_def_interval(Pos, [{Beginning, none}|More]) -> + [{Pos,none}, {Beginning, none}|More]; +extend_def_interval(Pos, Intervals) -> + {Pos, Pos}. + +-else. %% ifdef gb_intervals + +empty_interval(N) -> + hipe_vectors:new(N, none). + +interval_to_list(Intervals) -> + add_indices(hipe_vectors:vector_to_list(Intervals), 0). + +add_indices([{B, E}|Xs], N) -> + [{N, B, E}|add_indices(Xs, N+1)]; +add_indices([List|Xs], N) when is_list(List) -> + flatten(List, N, Xs); +add_indices([none|Xs], N) -> + add_indices(Xs, N+1); +add_indices([], _N) -> []. + +flatten([{none, End}|Rest], N, More) -> + [{N,End,End} | flatten(Rest, N, More)]; +flatten([{Beg, none}|Rest], N ,More) -> + [{N,Beg,Beg} | flatten(Rest, N, More)]; +flatten([], N, More) -> + add_indices(More, N+1). + +add_use_point([Temp|Temps], Pos, Intervals) -> + %% Extend the old interval... + NewInterval = + case hipe_vectors:get(Intervals, Temp) of + %% This is the first time we see this temp... + none -> + %% ... create a new interval + {Pos, Pos}; + %% This temp has an old interval... + Value -> + %% ... extend it. + extend_interval(Pos, Value) + end, + %% Add or update the extended interval. + Intervals2 = hipe_vectors:set(Intervals, Temp, NewInterval), + %% Add the rest of the temporaries. + add_use_point(Temps, Pos, Intervals2); +add_use_point([], _, I) -> + %% No more to add return the interval. + I. + +add_def_point([Temp|Temps], Pos, Intervals) -> + %% Extend the old interval... + NewInterval = + case hipe_vectors:get(Intervals, Temp) of + %% This is the first time we see this temp... + none -> + %% ... create a new interval + {Pos, Pos}; + %% This temp has an old interval... + Value -> + %% ... extend it. + extend_interval(Pos, Value) + end, + %% Add or update the extended interval. + Intervals2 = hipe_vectors:set(Intervals, Temp, NewInterval), + %% Add the rest of the temporaries. + add_def_point(Temps, Pos, Intervals2); +add_def_point([], _, I) -> + %% No more to add return the interval. + I. + +extend_interval(Pos, {Beginning, End}) + when is_integer(Beginning), is_integer(End) -> + %% If this position occurs before the beginning of the interval, + %% then extend the beginning to this position. + NewBeginning = erlang:min(Pos, Beginning), + %% If this position occurs after the end of the interval, then + %% extend the end to this position. + NewEnd = erlang:max(Pos, End), + {NewBeginning, NewEnd}. + +-endif. %% gb_intervals + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Interface to external functions. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +liveness(CFG, Target) -> + Target:analyze(CFG). + +bb(CFG, L, Target) -> + Target:bb(CFG, L). + +livein(Liveness, L, Target) -> + regnames(Target:livein(Liveness, L), Target). + +liveout(Liveness, L, Target) -> + regnames(Target:liveout(Liveness, L), Target). + +uses(I, Target) -> + regnames(Target:uses(I), Target). + +defines(I, Target) -> + regnames(Target:defines(I), Target). + +regnames(Regs, Target) -> + [Target:reg_nr(X) || X <- Regs]. |