From 84adefa331c4159d432d22840663c38f155cd4c1 Mon Sep 17 00:00:00 2001 From: Erlang/OTP Date: Fri, 20 Nov 2009 14:54:40 +0000 Subject: The R13B03 release. --- lib/hipe/regalloc/hipe_ls_regalloc.erl | 788 +++++++++++++++++++++++++++++++++ 1 file changed, 788 insertions(+) create mode 100644 lib/hipe/regalloc/hipe_ls_regalloc.erl (limited to 'lib/hipe/regalloc/hipe_ls_regalloc.erl') diff --git a/lib/hipe/regalloc/hipe_ls_regalloc.erl b/lib/hipe/regalloc/hipe_ls_regalloc.erl new file mode 100644 index 0000000000..d06b938bea --- /dev/null +++ b/lib/hipe/regalloc/hipe_ls_regalloc.erl @@ -0,0 +1,788 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%% ===================================================================== +%% @doc +%% 
+%%  Module   :	hipe_ls_regalloc
+%%  Purpose  :  Perform a register allocation based on the 
+%%              "linear-scan algorithm".
+%%  Notes    :  * This is an implementation of 
+%%                "Linear Scan Register Allocation" by 
+%%                Massimiliano Poletto & Vivek Sarkar described in
+%%                ACM TOPLAS Vol 21, No 5, September 1999.
+%%
+%%              * This implementation is target-independent and
+%%                requires a target specific interface module
+%%                as argument.  
+%%                (Still waiting for a modular module system for Erlang.)
+%%
+%% @end +%% +%% History : * 2000-04-07 Erik Johansson (happi@it.uu.se): Created. +%% * 2001-07-16 Erik Johansson: Made less sparc-specific. +%% ===================================================================== +%% Exported functions (short description): +%% regalloc(CFG,PhysRegs,Entrypoints, Options) -> +%% {Coloring, NumberOfSpills} +%% Takes a CFG and returns a coloring of all used registers. +%% PhysRegs should be a list of available physical registers. +%% Entrypoints should be a list of names of Basic Blocks that have +%% external entry points. +%% +%% The Coloring will be in the form of the "allocation datastructure" +%% described below, that is, a list of tuples on the form +%% {Name, {reg, PhysicalRegister}} or +%% {Name, {spill, SpillIndex}} +%% The NumberOfSpills is either 0 indicating no spill or the +%% SpillIndex of the last spilled register. +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-module(hipe_ls_regalloc). +-export([regalloc/7]). + +%%-define(DEBUG,1). +-define(HIPE_INSTRUMENT_COMPILER, true). + +-include("../main/hipe.hrl"). + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% @spec +%% regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, +%% Target) -> +%% {Coloring, NumberOfSpills} +%% CFG = cfg() +%% PhysRegs = [reg()] +%% Entrypoints = [labelname()] +%% DontSpill = reg() +%% Options = proplist:proplist() +%% Target = atom() +%% Coloring = [{temp(), pos()}] +%% NumberOfSpills = integer() +%% reg() = integer() +%% temp() = integer() +%% pos() = {reg, reg()} | {spill, integer()} +%% +%% @doc +%% Calculates an allocation of registers using a linear_scan algorithm. +%% There are three steps in the algorithm: +%%
    +%%
  1. Calculate live-ranges for all registers.
    2. +%%
  2. Calculate live-intervals for each register. +%% The live interval consists of a start position and an end +%% position. These are the first definition and last use of the +%% register given as instruction numbers in a breadth-first +%% traversal of the control-flow-graph.
    3. +%%
  3. Perform a linear scan allocation over the live intervals.
    4. +%%
+%% @end +%%- - - - - - - - - - - - - - - - - - - - - - - - +regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) -> + ?debug_msg("LinearScan: ~w\n", [erlang:statistics(runtime)]), + %% Step 1: Calculate liveness (Call external implementation.) + Liveness = liveness(CFG, Target), + ?debug_msg("liveness (done)~w\n", [erlang:statistics(runtime)]), + USIntervals = calculate_intervals(CFG, Liveness, + Entrypoints, Options, Target), + ?debug_msg("intervals (done) ~w\n", [erlang:statistics(runtime)]), + Intervals = sort_on_start(USIntervals), + ?debug_msg("sort intervals (done) ~w\n", [erlang:statistics(runtime)]), + %% ?debug_msg("Intervals ~w\n", [Intervals]), + ?debug_msg("No intervals: ~w\n",[length(Intervals)]), + ?debug_msg("count intervals (done) ~w\n", [erlang:statistics(runtime)]), + Allocation = allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target), + ?debug_msg("allocation (done) ~w\n", [erlang:statistics(runtime)]), + Allocation. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% %% +%% Step 2: Calculate live-intervals for each register. %% +%% %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% calculate_intervals(CFG,Liveness,Entrypoints, Options, Target) +%% CFG: The Control-Flow Graph. +%% Liveness: A map of live-in and live-out sets for each Basic-Block. +%% Entrypoints: A set of BB names that have external entrypoints. +%% +calculate_intervals(CFG,Liveness,_Entrypoints, Options, Target) -> + %% Add start point for the argument registers. + Args = arg_vars(CFG, Target), + Interval = + add_def_point(Args, 0, empty_interval(Target:number_of_temporaries(CFG))), + %% Interval = add_livepoint(Args, 0, empty_interval()), + Worklist = + case proplists:get_value(ls_order, Options) of + reversepostorder -> + Target:reverse_postorder(CFG); + breadth -> + Target:breadthorder(CFG); + postorder -> + Target:postorder(CFG); + inorder -> + Target:inorder(CFG); + reverse_inorder -> + Target:reverse_inorder(CFG); + preorder -> + Target:preorder(CFG); + prediction -> + Target:predictionorder(CFG); + random -> + Target:labels(CFG); + _ -> + Target:reverse_postorder(CFG) + end, + %% ?inc_counter(bbs_counter, length(Worklist)), + %% ?debug_msg("No BBs ~w\n",[length(Worklist)]), + intervals(Worklist, Interval, 1, CFG, Liveness, Target). + +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% intervals(WorkList, Intervals, InstructionNr, CFG, Liveness, Target) +%% WorkList: List of BB-names to handle. +%% Intervals: Intervals seen so far (sorted on register names). +%% InstructionNr: The number of examined insturctions. +%% CFG: The Control-Flow Graph. +%% Liveness: A map of live-in and live-out sets for each Basic-Block. +%% Target: The backend for which we generate code. +%%- - - - - - - - - - - - - - - - - - - - - - - - +intervals([L|ToDO], Intervals, InstructionNr, CFG, Liveness, Target) -> + %% Add all variables that are live at the entry of this block + %% to the interval data structure. + LiveIn = livein(Liveness, L, Target), + Intervals2 = add_def_point(LiveIn, InstructionNr, Intervals), + LiveOut = liveout(Liveness, L, Target), + + %% Traverse this block instruction by instruction and add all + %% uses and defines to the intervals. + Code = hipe_bb:code(bb(CFG, L, Target)), + {Intervals3, NewINr} = + traverse_block(Code, InstructionNr+1, Intervals2, Target), + + %% Add end points for the registers that are in the live-out set. + Intervals4 = add_use_point(LiveOut, NewINr+1, Intervals3), + + intervals(ToDO, Intervals4, NewINr+1, CFG, Liveness, Target); +intervals([], Intervals, _, _, _, _) -> + %% Return the calculated intervals + LI = interval_to_list(Intervals), + %% io:format("Intervals:~n~p~n", [LI]), + LI. + +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% traverse_block(Code, InstructionNo, Intervals, Unchanged) +%% Examine each instruction in the Code: +%% For each temporary T used or defined by instruction number N: +%% extend the interval of T to include N. +%%- - - - - - - - - - - - - - - - - - - - - - - - +traverse_block([Instruction|Is],InstrNo,Intervals, Target) -> + %% Get defined temps. + DefsSet = defines(Instruction, Target), + Intervals1 = add_def_point(DefsSet, InstrNo, Intervals), + + %% Get used temps. + UsesSet = uses(Instruction, Target), + %% Extend the intervals for these temporaries to include InstrNo. + Intervals2 = add_use_point(UsesSet, InstrNo, Intervals1), + + %% Handle the next instruction. + traverse_block(Is,InstrNo+1,Intervals2,Target); +traverse_block([], InstrNo, Intervals, _) -> + %% Return the new intervals and the number of the next instruction. + {Intervals,InstrNo}. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% %% +%% Step 3. Do a linear scan allocation over the live intervals. %% +%% %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% allocate(Intervals, PhysicalRegisters, DontSpill, Target) +%% +%% This function performs the linear scan algorithm. +%% Intervals contains the start and stop position of each register, +%% sorted on increasing startpositions +%% PhysicalRegisters is a list of available Physical registers to use. +%% +%%- - - - - - - - - - - - - - - - - - - - - - - - +allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target) -> + ActiveRegisters =[], + AllocatedRegisters = empty_allocation(), + AllFree = create_freeregs(PhysRegs), + allocate(Intervals, AllFree, ActiveRegisters, + AllocatedRegisters, SpillIndex, DontSpill, Target). +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% allocate(Intervals, Free, Active, Allocated, SpillIndex, Target) +%% Iterates of each register interval. +%% Intervals: The list of register intervals. +%% Free: Currently available physical registers. +%% Active: Currently used physical registers (sorted on increasing +%% interval enpoints) +%% Allocated: The mapping of register names to physical registers or +%% to spill positions. +%% SpillIndex: The number of spilled registers. +%%- - - - - - - - - - - - - - - - - - - - - - - - +allocate([RegInt|RIS], Free, Active, Alloc, SpillIndex, DontSpill, Target) -> + %io:format("~nAlloc:~n~p", [Alloc]), + %% Remove from the active list those registers who's intervals + %% ends before the start of the current interval. + {NewActive, NewFree} = + expire_old_intervals(Active, startpoint(RegInt), Free, Target), + ?debug_msg("Alloc interval: ~w, Free ~w\n",[RegInt, NewFree]), + %% Get the name of the temp in the current interval. + Temp = reg(RegInt), + case is_precoloured(Temp, Target) of + true -> + %% This is a precoloured register we don't need to find a color + %% Get the physical name of the register. + PhysName = physical_name(Temp, Target), + %% Bind it to the precoloured name. + NewAlloc = alloc(Temp, PhysName, Alloc), + case is_global(Temp, Target) of + true -> + %% this is a global precoloured register + allocate(RIS, NewFree, NewActive, + NewAlloc, SpillIndex, DontSpill, Target); + false -> + case is_free(PhysName, NewFree) of + {true,Rest} -> + allocate(RIS, Rest, + add_active(endpoint(RegInt), startpoint(RegInt), + PhysName, Temp, NewActive), + NewAlloc, + SpillIndex, DontSpill, Target); + false -> + %% Some other temp has taken this precoloured register, + %% throw it out. + {OtherActive, NewActive2} = deactivate(PhysName, NewActive), + OtherTemp = active_name(OtherActive), + OtherEnd = active_endpoint(OtherActive), + OtherStart = active_startpoint(OtherActive), + NewActive3 = add_active(endpoint(RegInt), startpoint(RegInt), + PhysName, Temp, NewActive2), + case exists_free_register(OtherStart, NewFree) of + {true, NewPhys, RestFree} -> + allocate(RIS, RestFree, + add_active(OtherEnd, OtherStart, + NewPhys, OtherTemp, NewActive3), + alloc(OtherTemp,NewPhys,NewAlloc), + SpillIndex, DontSpill, Target); + false -> + NewSpillIndex = Target:new_spill_index(SpillIndex), + {NewAlloc2, NewActive4} = + spill(OtherTemp, OtherEnd, OtherStart, NewActive3, + NewAlloc, SpillIndex, DontSpill, Target), + allocate(RIS, + NewFree, + NewActive4, + NewAlloc2, NewSpillIndex, DontSpill, Target) + end + end + end; + false -> + %% This is not a precoloured register. + case NewFree of + [] -> + %% No physical registers available, we have to spill. + NewSpillIndex = Target:new_spill_index(SpillIndex), + {NewAlloc, NewActive2} = + spill(Temp, endpoint(RegInt), startpoint(RegInt), + Active, Alloc, SpillIndex, DontSpill, Target), + %% io:format("Spilled ~w\n",[NewAlloc]), + allocate(RIS, NewFree, NewActive2, NewAlloc, NewSpillIndex, + DontSpill, Target); + + [{FreeReg,_Start} | Regs] -> + %% The register FreeReg is available, let's use it. + %%io:format("Allocating Reg:~p~n",[FreeReg]), + allocate(RIS,Regs, + add_active(endpoint(RegInt), startpoint(RegInt), + FreeReg, Temp, NewActive), + alloc(Temp, FreeReg, Alloc), + SpillIndex, DontSpill, Target) + end + end; +allocate([],_,_,Alloc,SpillIndex, _, _) -> + %% No more register intervals to handle + %% return the result. + %%io:format("~nAlloc:~n~p", [Alloc]), + {Alloc, SpillIndex}. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% expire_old_intervals(ActiveRegisters, CurrentPos, FreeRegisters) +%% Remove all registers 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. + Reg = active_reg(Act), + %% Add the register to the free pool. + NewFree = + case is_arg(Reg, Target) of + true -> + [{Reg, CurrentPos}|Free]; + false -> + [{Reg, CurrentPos}|Free] + %% Here we could try appending the + %% register to get a more widespread + %% use of registers. + %% Free ++ [active_reg(Act)]); + %% At the moment this does not seem to + %% improve performance at all, + %% on the other hand, the cost is very low. + end, + expire_old_intervals(Acts, CurrentPos, NewFree, Target); + false -> + %% No -> Then we cannot free any more registers. + %% (Since they are sorted on endpoints...) + {AllActives, Free} + end; +expire_old_intervals([], _, Free, _) -> + {[], Free}. + +deactivate(Reg, [Active|Actives]) -> + case Reg =:= active_reg(Active) of + true -> + {Active, Actives}; + false -> + {TheActive, NewActives} = deactivate(Reg, Actives), + {TheActive, [Active|NewActives]} + end; +deactivate(_,[]) -> {no,[]}. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% spill(CurrentReg, CurrentEndpoint, Active, Alloc, SpillIndex, +%% DontSpill, Target) +%% Find the register with the longest live range and spill it to memory. +%% +%% --------------------------------------------------------------------- +spill(CurrentReg, CurrentEndpoint,CurrentStartpoint, + Active = [_|_], + Alloc, SpillIndex, + DontSpill, Target) -> + ?debug_msg("spilling one of ~w\nDOnt spill ~w\n", + [[CurrentReg|Active], DontSpill]), + + %% Find a spill candidate (one of the active): + %% The register with the longest live-range. + {NewActive, SpillCandidate} = butlast_last(Active), + + SpillStartpoint = active_startpoint(SpillCandidate) , + SpillEndpoint = active_endpoint(SpillCandidate) , + SpillName = active_name(SpillCandidate), + SpillPhysName = active_reg(SpillCandidate), + + case SpillEndpoint > CurrentEndpoint of + true -> + %% There is an already allocated register that has + %% a longer live-range than the current register. + case can_spill(SpillName, DontSpill, Target) and + (SpillStartpoint =< CurrentStartpoint) of + false -> + {NewAlloc, NewActive2} = + spill(CurrentReg, CurrentEndpoint, CurrentStartpoint, + NewActive, Alloc, SpillIndex, DontSpill, Target), + {NewAlloc, + add_active(SpillEndpoint, SpillStartpoint, SpillPhysName, + SpillName, NewActive2)}; + true -> + %% It is not precoloured... or have too short liverange + + %% Allocate SpillCandidate to spill-slot SpillIndex + SpillAlloc = + spillalloc(active_name(SpillCandidate), SpillIndex, + Alloc), + + %% Allocated the current register to the physical register + %% used by the spill candidate. + NewAlloc = alloc(CurrentReg, SpillPhysName, SpillAlloc), + + %% Add the current register to the active registers + NewActive2 = + add_active(CurrentEndpoint, CurrentStartpoint, + SpillPhysName, CurrentReg, NewActive), + {NewAlloc, NewActive2} + end; + + false -> + %% The current register has the longest live-range. + + case can_spill(CurrentReg, DontSpill, Target) of + false -> + %% Cannot spill a precoloured register + {NewAlloc, NewActive2} = + spill(SpillName, SpillEndpoint, SpillStartpoint, + NewActive, Alloc, SpillIndex, DontSpill, Target), + NewActive3 = + add_active(CurrentEndpoint, CurrentStartpoint, + SpillPhysName, CurrentReg, NewActive2), + {NewAlloc, NewActive3}; + true -> + %% It is not precoloured... + %% Allocate the current register to spill-slot SpillIndex + {spillalloc(CurrentReg, SpillIndex, Alloc), Active} + end + end; +spill(CurrentReg, _CurrentEndpoint, _CurrentStartpoint, [], + Alloc, SpillIndex, DontSpill, Target) -> + case can_spill(CurrentReg, DontSpill, Target) of + false -> %% Can't spill current! + ?error_msg("Can't allocate registers\n",[]), + ?EXIT({cannot_allocate_regs}); + true -> %% Can spill current. + %% Allocate the current register to spill-slot SpillIndex + {spillalloc(CurrentReg, SpillIndex, Alloc), []} + end. + +can_spill(Name, DontSpill, Target) -> + (Name < DontSpill) and (not is_precoloured(Name, Target)). + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% %% +%% 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} +%% The allocation is either {reg, physical register} or +%% {spill, spill index} +%% +%% --------------------------------------------------------------------- +empty_allocation() -> []. + +alloc(Name,Reg,[{Name,_}|A]) -> + [{Name,{reg,Reg}}|A]; +alloc(Name,Reg,[{Name2,Binding}|Bindings]) when Name > Name2 -> + [{Name2,Binding}|alloc(Name,Reg,Bindings)]; +alloc(Name,Reg,Bindings) -> + [{Name,{reg,Reg}}|Bindings]. + +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]. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% +butlast_last([X]) -> + {[],X}; +butlast_last([X|Y]) -> + {L,Last} = butlast_last(Y), + {[X|L],Last}. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% The active datastructure. +%% Keeps tracks of currently active (allocated) physical registers. +%% It is sorted on end points in the intervals +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +add_active(Endpoint, StartPoint, PhysReg, RegName, + [{P1,R1,O1,S1}|Active]) when P1 < Endpoint -> + [{P1,R1,O1,S1}|add_active(Endpoint, StartPoint, PhysReg, RegName, Active)]; +add_active(Endpoint, StartPoint, PhysReg, RegName, Active) -> + [{Endpoint, PhysReg, RegName, StartPoint}|Active]. + +active_reg({_,PhysReg,_,_}) -> + PhysReg. +active_endpoint({EndPoint,_,_,_}) -> + EndPoint. +active_startpoint({_,_,_,StartPoint}) -> + StartPoint. +active_name({_,_,RegName,_}) -> + RegName. +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% 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 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 teh 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 occures before the beginning + %% of the interval, then extend the beginning to + %% this position. + NewBeginning = erlang:min(Pos, Beginning), + %% If this position occures after the end + %% of the interval, then extend the end to + %% this position. + NewEnd = erlang:max(Pos, End), + {NewBeginning, NewEnd}. + +-else. %% isdef 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 teh 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 occures after the end + %% of the interval, then extend the end to + %% this position. + NewEnd = erlang:max(Pos, End), + {NewBeginning, NewEnd}. +-endif. %% gb_intervals + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% The Freel data structure. +%% +%%- - - - - - - - - - - - - - - - - - - - - - - - + +is_free(R, Free) -> + is_free(R, Free, []). + +is_free(R, [{R,_}|Rest], Acc) -> + {true,lists:reverse(Acc)++Rest}; +is_free(R, [X|Rs],Acc) -> + is_free(R, Rs, [X|Acc]); +is_free(_, [], _) -> + false. + +exists_free_register(Start, Regs) -> + exists_free_register(Start, Regs, []). + +exists_free_register(Start, [{Phys, Start0}|Rest], Acc) + when Start > Start0 -> + {true, Phys, lists:reverse(Acc)++Rest}; +exists_free_register(Start, [Free|Rest], Acc) -> + exists_free_register(Start, Rest, [Free|Acc]); +exists_free_register(_, [], _) -> + false. + +create_freeregs([Phys|Rest]) -> + [{Phys,-1}|create_freeregs(Rest)]; +create_freeregs([]) -> + []. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Interface to external functions. +%% XXX: Make this efficient somehow... +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +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). + +is_precoloured(R, Target) -> + Target:is_precoloured(R). + +is_global(R, Target) -> + Target:is_global(R). + +physical_name(R, Target) -> + Target:physical_name(R). + +regnames(Regs, Target) -> + [Target:reg_nr(X) || X <- Regs]. + +arg_vars(CFG, Target) -> + Target:args(CFG). + +is_arg(Reg, Target) -> + Target:is_arg(Reg). -- cgit v1.2.3