diff options
71 files changed, 1027 insertions, 761 deletions
diff --git a/lib/hipe/amd64/Makefile b/lib/hipe/amd64/Makefile index 8dc2af2679..ea3559b7e6 100644 --- a/lib/hipe/amd64/Makefile +++ b/lib/hipe/amd64/Makefile @@ -57,10 +57,10 @@ MODULES=hipe_amd64_assemble \ hipe_amd64_ra_naive \ hipe_amd64_ra_postconditions \ hipe_amd64_ra_sse2_postconditions \ - hipe_amd64_ra_x87_ls \ hipe_amd64_registers \ hipe_amd64_spill_restore \ hipe_amd64_x87 \ + hipe_amd64_sse2 \ hipe_rtl_to_amd64 ERL_FILES=$(MODULES:%=%.erl) @@ -125,10 +125,10 @@ $(EBIN)/hipe_amd64_ra_ls.beam: ../main/hipe.hrl ../x86/hipe_x86_ra_ls.erl $(EBIN)/hipe_amd64_ra_naive.beam: ../main/hipe.hrl ../x86/hipe_x86.hrl ../x86/hipe_x86_ra_naive.erl $(EBIN)/hipe_amd64_ra_postconditions.beam: ../main/hipe.hrl ../x86/hipe_x86.hrl ../x86/hipe_x86_ra_postconditions.erl $(EBIN)/hipe_amd64_ra_sse2_postconditions.beam: ../main/hipe.hrl -$(EBIN)/hipe_amd64_ra_x87_ls.beam: ../main/hipe.hrl ../x86/hipe_x86_ra_x87_ls.erl $(EBIN)/hipe_amd64_registers.beam: ../rtl/hipe_literals.hrl $(EBIN)/hipe_amd64_spill_restore.beam: ../main/hipe.hrl ../x86/hipe_x86.hrl ../flow/cfg.hrl ../x86/hipe_x86_spill_restore.erl $(EBIN)/hipe_amd64_x87.beam: ../x86/hipe_x86_x87.erl +$(EBIN)/hipe_amd64_sse2.beam: ../main/hipe.hrl ../x86/hipe_x86.hrl $(EBIN)/hipe_rtl_to_amd64.beam: ../x86/hipe_rtl_to_x86.erl ../rtl/hipe_rtl.hrl $(TARGET_FILES): ../x86/hipe_x86.hrl ../misc/hipe_consttab.hrl diff --git a/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl b/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl index b1f7bd7572..bbf9170bc3 100644 --- a/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl +++ b/lib/hipe/amd64/hipe_amd64_ra_sse2_postconditions.erl @@ -21,7 +21,7 @@ -module(hipe_amd64_ra_sse2_postconditions). --export([check_and_rewrite/2]). +-export([check_and_rewrite/2, check_and_rewrite/3]). -include("../x86/hipe_x86.hrl"). -define(HIPE_INSTRUMENT_COMPILER, true). @@ -29,40 +29,48 @@ -define(count_temp(T), ?cons_counter(counter_mfa_mem_temps, T)). -check_and_rewrite(AMD64Defun, Coloring) -> +check_and_rewrite(AMD64CFG, Coloring) -> + check_and_rewrite(AMD64CFG, Coloring, 'normal'). + +check_and_rewrite(AMD64CFG, Coloring, Strategy) -> %%io:format("Converting\n"), TempMap = hipe_temp_map:cols2tuple(Coloring,hipe_amd64_specific_sse2), %%io:format("Rewriting\n"), - #defun{code=Code0} = AMD64Defun, - {Code1, DidSpill} = do_insns(Code0, TempMap, [], false), - {AMD64Defun#defun{code=Code1, var_range={0, hipe_gensym:get_var(x86)}}, - DidSpill}. - -do_insns([I|Insns], TempMap, Accum, DidSpill0) -> - {NewIs, DidSpill1} = do_insn(I, TempMap), - do_insns(Insns, TempMap, lists:reverse(NewIs, Accum), DidSpill0 or DidSpill1); -do_insns([], _TempMap, Accum, DidSpill) -> + do_bbs(hipe_x86_cfg:labels(AMD64CFG), TempMap, Strategy, AMD64CFG, false). + +do_bbs([], _, _, CFG, DidSpill) -> {CFG, DidSpill}; +do_bbs([Lbl|Lbls], TempMap, Strategy, CFG0, DidSpill0) -> + Code0 = hipe_bb:code(BB = hipe_x86_cfg:bb(CFG0, Lbl)), + {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0), + CFG = hipe_x86_cfg:bb_add(CFG0, Lbl, hipe_bb:code_update(BB, Code)), + do_bbs(Lbls, TempMap, Strategy, CFG, DidSpill). + +do_insns([I|Insns], TempMap, Strategy, Accum, DidSpill0) -> + {NewIs, DidSpill1} = do_insn(I, TempMap, Strategy), + do_insns(Insns, TempMap, Strategy, lists:reverse(NewIs, Accum), + DidSpill0 or DidSpill1); +do_insns([], _TempMap, _Strategy, Accum, DidSpill) -> {lists:reverse(Accum), DidSpill}. -do_insn(I, TempMap) -> % Insn -> {Insn list, DidSpill} +do_insn(I, TempMap, Strategy) -> % Insn -> {Insn list, DidSpill} case I of #fmove{} -> - do_fmove(I, TempMap); + do_fmove(I, TempMap, Strategy); #fp_unop{} -> - do_fp_unop(I, TempMap); + do_fp_unop(I, TempMap, Strategy); #fp_binop{} -> - do_fp_binop(I, TempMap); + do_fp_binop(I, TempMap, Strategy); _ -> %% All non sse2 ops {[I], false} end. %%% Fix an fp_binop. -do_fp_binop(I, TempMap) -> +do_fp_binop(I, TempMap, Strategy) -> #fp_binop{src=Src,dst=Dst} = I, case is_mem_opnd(Dst, TempMap) of true -> - Tmp = clone(Dst), + Tmp = clone(Dst, Strategy), {[#fmove{src=Dst, dst=Tmp}, I#fp_binop{src=Src,dst=Tmp}, #fmove{src=Tmp,dst=Dst}], @@ -71,11 +79,11 @@ do_fp_binop(I, TempMap) -> {[I], false} end. -do_fp_unop(I, TempMap) -> +do_fp_unop(I, TempMap, Strategy) -> #fp_unop{arg=Arg} = I, case is_mem_opnd(Arg, TempMap) of true -> - Tmp = clone(Arg), + Tmp = clone(Arg, Strategy), {[#fmove{src=Arg, dst=Tmp}, I#fp_unop{arg=Tmp}, #fmove{src=Tmp,dst=Arg}], @@ -85,7 +93,7 @@ do_fp_unop(I, TempMap) -> end. %%% Fix an fmove op. -do_fmove(I, TempMap) -> +do_fmove(I, TempMap, Strategy) -> #fmove{src=Src,dst=Dst} = I, case (is_mem_opnd(Src, TempMap) andalso is_mem_opnd(Dst, TempMap)) @@ -93,7 +101,7 @@ do_fmove(I, TempMap) -> orelse ((not is_float_temp(Src)) andalso is_mem_opnd(Dst, TempMap)) of true -> - Tmp = spill_temp(double), + Tmp = spill_temp(double, Strategy), {[#fmove{src=Src, dst=Tmp},I#fmove{src=Tmp,dst=Dst}], true}; false -> @@ -106,86 +114,45 @@ is_float_temp(#x86_mem{}) -> false. %%% Check if an operand denotes a memory cell (mem or pseudo). is_mem_opnd(Opnd, TempMap) -> - R = - case Opnd of - #x86_mem{} -> true; - #x86_temp{type=double} -> - Reg = hipe_x86:temp_reg(Opnd), - case hipe_x86:temp_is_allocatable(Opnd) of - true -> - case tuple_size(TempMap) > Reg of - true -> - case - hipe_temp_map:is_spilled(Reg, TempMap) of - true -> - ?count_temp(Reg), - true; - false -> false - end; - _ -> false - end; - false -> true - end; - _ -> false - end, - %% io:format("Op ~w mem: ~w\n",[Opnd,R]), - R. - -%%% Check if an operand is a spilled Temp. - -%%src_is_spilled(Src, TempMap) -> -%% case hipe_x86:is_temp(Src) of -%% true -> -%% Reg = hipe_x86:temp_reg(Src), -%% case hipe_x86:temp_is_allocatable(Src) of -%% true -> -%% case tuple_size(TempMap) > Reg of -%% true -> -%% case hipe_temp_map:is_spilled(Reg, TempMap) of -%% true -> -%% ?count_temp(Reg), -%% true; -%% false -> -%% false -%% end; -%% false -> -%% false -%% end; -%% false -> true -%% end; -%% false -> false -%% end. - -%% is_spilled(Temp, TempMap) -> -%% case hipe_x86:temp_is_allocatable(Temp) of -%% true -> -%% Reg = hipe_x86:temp_reg(Temp), -%% case tuple_size(TempMap) > Reg of -%% true -> -%% case hipe_temp_map:is_spilled(Reg, TempMap) of -%% true -> -%% ?count_temp(Reg), -%% true; -%% false -> -%% false -%% end; -%% false -> -%% false -%% end; -%% false -> true -%% end. + case Opnd of + #x86_mem{} -> true; + #x86_temp{type=double} -> + Reg = hipe_x86:temp_reg(Opnd), + case hipe_x86:temp_is_allocatable(Opnd) of + true -> + case tuple_size(TempMap) > Reg of + true -> + case + hipe_temp_map:is_spilled(Reg, TempMap) of + true -> + ?count_temp(Reg), + true; + false -> false + end; + _ -> false + end; + false -> true + end; + _ -> false + end. %%% Make Reg a clone of Dst (attach Dst's type to Reg). -clone(Dst) -> +clone(Dst, Strategy) -> Type = case Dst of #x86_mem{} -> hipe_x86:mem_type(Dst); #x86_temp{} -> hipe_x86:temp_type(Dst) end, - spill_temp(Type). - -spill_temp(Type) -> + spill_temp(Type, Strategy). + +spill_temp(Type, 'normal') -> + hipe_x86:mk_new_temp(Type); +spill_temp(double, 'linearscan') -> + hipe_x86:mk_temp(hipe_amd64_specific_sse2:temp0(), double); +spill_temp(Type, 'linearscan') when Type =:= tagged; Type =/= untagged -> + %% We can make a new temp here since we have yet to allocate registers for + %% these types hipe_x86:mk_new_temp(Type). %%% Make a certain reg into a clone of Dst diff --git a/lib/hipe/amd64/hipe_amd64_ra_x87_ls.erl b/lib/hipe/amd64/hipe_amd64_ra_x87_ls.erl deleted file mode 100644 index 6da3f44cd3..0000000000 --- a/lib/hipe/amd64/hipe_amd64_ra_x87_ls.erl +++ /dev/null @@ -1,21 +0,0 @@ -%% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2004-2016. All Rights Reserved. -%% -%% 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. -%% -%% %CopyrightEnd% -%% - --include("../x86/hipe_x86_ra_x87_ls.erl"). diff --git a/lib/hipe/amd64/hipe_amd64_registers.erl b/lib/hipe/amd64/hipe_amd64_registers.erl index 780c2cc547..ada5311453 100644 --- a/lib/hipe/amd64/hipe_amd64_registers.erl +++ b/lib/hipe/amd64/hipe_amd64_registers.erl @@ -52,6 +52,7 @@ tailcall_clobbered/0, temp0/0, temp1/0, + sse2_temp0/0, %% fixed/0, wordsize/0 ]). @@ -107,6 +108,8 @@ heap_limit_offset() -> ?P_HP_LIMIT. -define(TEMP0, ?R14). -define(TEMP1, ?R13). +-define(SSE2_TEMP0, 00). + -define(PROC_POINTER, ?RBP). reg_name(R) -> @@ -204,6 +207,8 @@ allocatable() -> allocatable_sse2() -> [00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15]. %% xmm0 - xmm15 +sse2_temp0() -> ?SSE2_TEMP0. + allocatable_x87() -> [0,1,2,3,4,5,6]. diff --git a/lib/hipe/amd64/hipe_amd64_sse2.erl b/lib/hipe/amd64/hipe_amd64_sse2.erl new file mode 100644 index 0000000000..ea6b6cb9ba --- /dev/null +++ b/lib/hipe/amd64/hipe_amd64_sse2.erl @@ -0,0 +1,82 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2016. All Rights Reserved. +%% +%% 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. +%% +%% %CopyrightEnd% +%% +%% Fix {mem, mem} floating point operations that result from linear scan +%% allocated floats. + +-module(hipe_amd64_sse2). + +-export([map/1]). + +-include("../x86/hipe_x86.hrl"). +-include("../main/hipe.hrl"). + +%%---------------------------------------------------------------------- + +map(CFG) -> + hipe_x86_cfg:map_bbs(fun do_bb/2, CFG). + +do_bb(_Lbl, BB) -> + Code = do_insns(hipe_bb:code(BB), []), + hipe_bb:code_update(BB, Code). + +do_insns([I|Insns], Accum) -> + NewIs = do_insn(I), + do_insns(Insns, lists:reverse(NewIs, Accum)); +do_insns([], Accum) -> + lists:reverse(Accum). + +do_insn(I) -> + case I of + #fp_binop{} -> do_fp_binop(I); + #fmove{} -> do_fmove(I); + _ -> [I] + end. + +do_fp_binop(I = #fp_binop{src=Src0,dst=Dst}) -> + {FixSrc, Src} = fix_binary(Src0, Dst), + FixSrc ++ [I#fp_binop{src=Src}]. + +do_fmove(I = #fmove{src=Src0,dst=Dst}) -> + {FixSrc, Src} = fix_binary(Src0, Dst), + FixSrc ++ [I#fmove{src=Src}]. + +fix_binary(Src0, Dst) -> + case is_mem_opnd(Src0) of + false -> {[], Src0}; + true -> + case is_mem_opnd(Dst) of + false -> {[], Src0}; + true -> + Src1 = spill_temp(), + {[hipe_x86:mk_fmove(Src0, Src1)], Src1} + end + end. + +is_mem_opnd(#x86_fpreg{reg=Reg}) -> + not hipe_amd64_registers:is_precoloured_sse2(Reg); +is_mem_opnd(#x86_temp{type=double, reg=Reg}) -> + not hipe_amd64_registers:is_precoloured_sse2(Reg); +is_mem_opnd(#x86_temp{type=_, reg=Reg}) -> + not hipe_amd64_registers:is_precoloured(Reg); +is_mem_opnd(#x86_mem{}) -> true. + +spill_temp() -> + hipe_x86:mk_temp(hipe_amd64_registers:sse2_temp0(), double). diff --git a/lib/hipe/arm/hipe_arm_cfg.erl b/lib/hipe/arm/hipe_arm_cfg.erl index f2fa0a5164..2fb6675da9 100644 --- a/lib/hipe/arm/hipe_arm_cfg.erl +++ b/lib/hipe/arm/hipe_arm_cfg.erl @@ -24,6 +24,7 @@ -export([init/1, labels/1, start_label/1, succ/2, + map_bbs/2, fold_bbs/3, bb/2, bb_add/3]). -export([postorder/1]). -export([linearise/1]). @@ -35,6 +36,7 @@ -define(BREADTH_ORDER,true). % for linear scan -define(PARAMS_NEEDED,true). -define(START_LABEL_UPDATE_NEEDED,true). +-define(MAP_FOLD_NEEDED,true). -include("hipe_arm.hrl"). -include("../flow/cfg.hrl"). diff --git a/lib/hipe/arm/hipe_arm_finalise.erl b/lib/hipe/arm/hipe_arm_finalise.erl index a4b2f9c73c..55651d7180 100644 --- a/lib/hipe/arm/hipe_arm_finalise.erl +++ b/lib/hipe/arm/hipe_arm_finalise.erl @@ -20,13 +20,17 @@ %% -module(hipe_arm_finalise). --export([finalise/1]). +-export([finalise/2]). -include("hipe_arm.hrl"). -finalise(Defun) -> +finalise(Defun, Options) -> #defun{code=Code0} = Defun, - Code1 = peep(expand(Code0)), - Defun#defun{code=Code1}. + Code1Rev = expand(Code0), + Code2 = case proplists:get_bool(peephole, Options) of + true -> peep(Code1Rev); + false -> lists:reverse(Code1Rev) + end, + Defun#defun{code=Code2}. expand(Insns) -> expand_list(Insns, []). @@ -34,7 +38,7 @@ expand(Insns) -> expand_list([I|Insns], Accum) -> expand_list(Insns, expand_insn(I, Accum)); expand_list([], Accum) -> - lists:reverse(Accum). + Accum. expand_insn(I, Accum) -> case I of @@ -63,12 +67,67 @@ expand_insn(I, Accum) -> [I|Accum] end. -peep(Insns) -> - peep_list(Insns, []). +%% We do peephole "bottom-up" (in reverse, but applying rules to the correctly +%% ordered list). This way, we can do replacements that would take multiple +%% passes with an in-order peephole optimiser. +%% +%% N.B., if a rule wants to produce multiple instructions (even if some of them +%% are unchanged, it should push the additional instructions on the More list, +%% so that only the top instruction on Insns is new or changed, i.e. tl(Insns) +%% should have been peepholed previously. +peep(RevInsns) -> + peep_list_skip([], RevInsns). + +peep_list([#b_label{'cond'='al',label=Label} + | (Insns = [#label{label=Label}|_])], More) -> + peep_list_skip(Insns, More); + +peep_list([#move{movop='mov',s=false,dst=#arm_temp{reg=Dst} + ,am1=#arm_temp{reg=Dst}}|Insns], More) -> + peep_list_skip(Insns, More); + +peep_list([#move{movop='mov',s=false,dst=Dst,am1={Src,lsr,Imm}}, + #move{movop='mov',s=false,dst=Dst,am1={Dst,lsl,Imm}} + |Insns], More) when Imm > 0, Imm =< 8 -> + peep_list([#alu{aluop='bic',s=false,dst=Dst,src=Src,am1={(1 bsl Imm)-1,0}} + |Insns], More); +peep_list([#move{movop='mov',s=false,dst=Dst,am1={Src,lsl,Imm}}, + #move{movop='mov',s=false,dst=Dst,am1={Dst,lsr,Imm}} + |Insns], More) when Imm >= 24, Imm < 32 -> + peep_list([#alu{aluop='and',s=false,dst=Dst,src=Src + ,am1={(1 bsl (32-Imm))-1,0}} | Insns], More); + +%% XXX: Load-after-store optimisation should also be applied to RTL, where it +%% can be more general, expose opportunities for constant propagation, etc. +peep_list([#store{stop='strb',src=Src,am2=Mem}=Str, + #load {ldop='ldrb',dst=Dst,am2=Mem} | Insns], More) -> + peep_list([#alu{aluop='and',s=false,dst=Dst,src=Src,am1={16#ff,0}}|Insns], + [Str|More]); +peep_list([#store{stop='str',src=Src,am2=Mem}=Str, + #load {ldop='ldr',dst=Dst,am2=Mem} | Insns], More) -> + peep_list([#move{movop='mov',s=false,dst=Dst,am1=Src}|Insns], [Str|More]); + +peep_list([#alu{aluop='and',s=false,dst=Dst,src=Src,am1={Mask,0}}, + #alu{aluop='bic',s=false,dst=Dst,src=Dst,am1={InvMask,0}} + |Insns], More) -> + peep_list([#alu{aluop='and',s=false,dst=Dst,src=Src + ,am1={Mask band (bnot InvMask),0}} | Insns], More); + +%% XXX: The place that generates brain-dead code like the following should be +%% fixed rather than trying to patch it over here. +peep_list([#load{ldop='ldrb',dst=Dst,am2=_Mem}, + #alu{aluop='bic',s=false,dst=Dst,src=Dst,am1={16#ff,0}} + | Insns], More) -> + peep_list([#move{movop='mov',s=false,dst=Dst,am1={0,0}}|Insns], More); + +peep_list(Insns, [I|More]) -> + peep_list([I|Insns], More); +peep_list(Accum, []) -> + Accum. -peep_list([#b_label{'cond'='al',label=Label} | (Insns = [#label{label=Label}|_])], Accum) -> - peep_list(Insns, Accum); -peep_list([I|Insns], Accum) -> - peep_list(Insns, [I|Accum]); -peep_list([], Accum) -> - lists:reverse(Accum). +%% Used as an optimisation instead of tailcalling peep_list/2 when Insns has +%% already been peeped or is otherwise uninteresting (such as empty). +peep_list_skip(Insns, [I|More]) -> + peep_list([I|Insns], More); +peep_list_skip(Accum, []) -> + Accum. diff --git a/lib/hipe/arm/hipe_arm_frame.erl b/lib/hipe/arm/hipe_arm_frame.erl index e1e441a967..9a349b47d3 100644 --- a/lib/hipe/arm/hipe_arm_frame.erl +++ b/lib/hipe/arm/hipe_arm_frame.erl @@ -27,16 +27,14 @@ -define(LIVENESS_ALL, hipe_arm_liveness_gpr). % since we have no FP yet -frame(Defun) -> - Formals = fix_formals(hipe_arm:defun_formals(Defun)), - Temps0 = all_temps(hipe_arm:defun_code(Defun), Formals), - MinFrame = defun_minframe(Defun), +frame(CFG) -> + Formals = fix_formals(hipe_arm_cfg:params(CFG)), + Temps0 = all_temps(CFG, Formals), + MinFrame = defun_minframe(CFG), Temps = ensure_minframe(MinFrame, Temps0), - ClobbersLR = clobbers_lr(hipe_arm:defun_code(Defun)), - CFG0 = hipe_arm_cfg:init(Defun), - Liveness = ?LIVENESS_ALL:analyse(CFG0), - CFG1 = do_body(CFG0, Liveness, Formals, Temps, ClobbersLR), - hipe_arm_cfg:linearise(CFG1). + ClobbersLR = clobbers_lr(CFG), + Liveness = ?LIVENESS_ALL:analyse(CFG), + do_body(CFG, Liveness, Formals, Temps, ClobbersLR). fix_formals(Formals) -> fix_formals(hipe_arm_registers:nr_args(), Formals). @@ -51,32 +49,21 @@ do_body(CFG0, Liveness, Formals, Temps, ClobbersLR) -> do_prologue(CFG1, Context). do_blocks(CFG, Context) -> - Labels = hipe_arm_cfg:labels(CFG), - do_blocks(Labels, CFG, Context). + hipe_arm_cfg:map_bbs(fun(Lbl, BB) -> do_block(Lbl, BB, Context) end, CFG). -do_blocks([Label|Labels], CFG, Context) -> +do_block(Label, Block, Context) -> Liveness = context_liveness(Context), LiveOut = ?LIVENESS_ALL:liveout(Liveness, Label), - Block = hipe_arm_cfg:bb(CFG, Label), Code = hipe_bb:code(Block), - NewCode = do_block(Code, LiveOut, Context), - NewBlock = hipe_bb:code_update(Block, NewCode), - NewCFG = hipe_arm_cfg:bb_add(CFG, Label, NewBlock), - do_blocks(Labels, NewCFG, Context); -do_blocks([], CFG, _) -> - CFG. - -do_block(Insns, LiveOut, Context) -> - do_block(Insns, LiveOut, Context, context_framesize(Context), []). + NewCode = do_block(Code, LiveOut, Context, context_framesize(Context), []), + hipe_bb:code_update(Block, NewCode). do_block([I|Insns], LiveOut, Context, FPoff0, RevCode) -> {NewIs, FPoff1} = do_insn(I, LiveOut, Context, FPoff0), do_block(Insns, LiveOut, Context, FPoff1, lists:reverse(NewIs, RevCode)); do_block([], _, Context, FPoff, RevCode) -> FPoff0 = context_framesize(Context), - if FPoff =:= FPoff0 -> []; - true -> exit({?MODULE,do_block,FPoff}) - end, + FPoff0 = FPoff, lists:reverse(RevCode, []). do_insn(I, LiveOut, Context, FPoff) -> @@ -543,39 +530,46 @@ temp_is_pseudo(Temp) -> %%% Detect if a Defun's body clobbers LR. %%% -clobbers_lr(Insns) -> +clobbers_lr(CFG) -> LRreg = hipe_arm_registers:lr(), LRtagged = hipe_arm:mk_temp(LRreg, 'tagged'), LRuntagged = hipe_arm:mk_temp(LRreg, 'untagged'), - clobbers_lr(Insns, LRtagged, LRuntagged). - -clobbers_lr([I|Insns], LRtagged, LRuntagged) -> - Defs = hipe_arm_defuse:insn_def_gpr(I), - case lists:member(LRtagged, Defs) of - true -> true; - false -> - case lists:member(LRuntagged, Defs) of - true -> true; - false -> clobbers_lr(Insns, LRtagged, LRuntagged) - end - end; -clobbers_lr([], _LRtagged, _LRuntagged) -> false. + any_insn(fun(I) -> + Defs = hipe_arm_defuse:insn_def_gpr(I), + lists:member(LRtagged, Defs) + orelse lists:member(LRuntagged, Defs) + end, CFG). + +any_insn(Pred, CFG) -> + %% Abuse fold to do an efficient "any"-operation using nonlocal control flow + FoundSatisfying = make_ref(), + try fold_insns(fun (I, _) -> + case Pred(I) of + true -> throw(FoundSatisfying); + false -> false + end + end, false, CFG) + of _ -> false + catch FoundSatisfying -> true + end. %%% %%% Build the set of all temps used in a Defun's body. %%% -all_temps(Code, Formals) -> - S0 = find_temps(Code, tset_empty()), +all_temps(CFG, Formals) -> + S0 = fold_insns(fun find_temps/2, tset_empty(), CFG), S1 = tset_del_list(S0, Formals), tset_filter(S1, fun(T) -> temp_is_pseudo(T) end). -find_temps([I|Insns], S0) -> +find_temps(I, S0) -> S1 = tset_add_list(S0, hipe_arm_defuse:insn_def_all(I)), - S2 = tset_add_list(S1, hipe_arm_defuse:insn_use_all(I)), - find_temps(Insns, S2); -find_temps([], S) -> - S. + tset_add_list(S1, hipe_arm_defuse:insn_use_all(I)). + +fold_insns(Fun, InitAcc, CFG) -> + hipe_arm_cfg:fold_bbs( + fun(_, BB, Acc0) -> lists:foldl(Fun, Acc0, hipe_bb:code(BB)) end, + InitAcc, CFG). tset_empty() -> gb_sets:new(). @@ -604,16 +598,11 @@ tset_to_list(S) -> %%% in the middle of a tailcall. %%% -defun_minframe(Defun) -> - MaxTailArity = body_mta(hipe_arm:defun_code(Defun), 0), - MyArity = length(fix_formals(hipe_arm:defun_formals(Defun))), +defun_minframe(CFG) -> + MaxTailArity = fold_insns(fun insn_mta/2, 0, CFG), + MyArity = length(fix_formals(hipe_arm_cfg:params(CFG))), erlang:max(MaxTailArity - MyArity, 0). -body_mta([I|Code], MTA) -> - body_mta(Code, insn_mta(I, MTA)); -body_mta([], MTA) -> - MTA. - insn_mta(I, MTA) -> case I of #pseudo_tailcall{arity=Arity} -> diff --git a/lib/hipe/arm/hipe_arm_main.erl b/lib/hipe/arm/hipe_arm_main.erl index dce1193b24..8a7fa86394 100644 --- a/lib/hipe/arm/hipe_arm_main.erl +++ b/lib/hipe/arm/hipe_arm_main.erl @@ -24,15 +24,17 @@ rtl_to_arm(MFA, RTL, Options) -> Defun1 = hipe_rtl_to_arm:translate(RTL), + CFG1 = hipe_arm_cfg:init(Defun1), %% io:format("~w: after translate\n", [?MODULE]), %% hipe_arm_pp:pp(Defun1), - Defun2 = hipe_arm_ra:ra(Defun1, Options), + CFG2 = hipe_arm_ra:ra(CFG1, Options), %% io:format("~w: after regalloc\n", [?MODULE]), - %% hipe_arm_pp:pp(Defun2), - Defun3 = hipe_arm_frame:frame(Defun2), + %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG2)), + CFG3 = hipe_arm_frame:frame(CFG2), + Defun3 = hipe_arm_cfg:linearise(CFG3), %% io:format("~w: after frame\n", [?MODULE]), %% hipe_arm_pp:pp(Defun3), - Defun4 = hipe_arm_finalise:finalise(Defun3), + Defun4 = hipe_arm_finalise:finalise(Defun3, Options), %% io:format("~w: after finalise\n", [?MODULE]), pp(Defun4, MFA, Options), {native, arm, {unprofiled, Defun4}}. diff --git a/lib/hipe/arm/hipe_arm_ra.erl b/lib/hipe/arm/hipe_arm_ra.erl index 2f65e864fd..5a7884b63c 100644 --- a/lib/hipe/arm/hipe_arm_ra.erl +++ b/lib/hipe/arm/hipe_arm_ra.erl @@ -22,36 +22,36 @@ -module(hipe_arm_ra). -export([ra/2]). -ra(Defun0, Options) -> - %% hipe_arm_pp:pp(Defun0), - {Defun1, Coloring_fp, SpillIndex} +ra(CFG0, Options) -> + %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG0)), + {CFG1, Coloring_fp, SpillIndex} = case proplists:get_bool(inline_fp, Options) of %% true -> -%% hipe_regalloc_loop:ra_fp(Defun0, Options, +%% hipe_regalloc_loop:ra_fp(CFG0, Options, %% hipe_coalescing_regalloc, %% hipe_arm_specific_fp); false -> - {Defun0,[],0} + {CFG0,[],0} end, - %% hipe_arm_pp:pp(Defun1), - {Defun2, Coloring} + %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG1)), + {CFG2, Coloring} = case proplists:get_value(regalloc, Options, coalescing) of coalescing -> - ra(Defun1, SpillIndex, Options, hipe_coalescing_regalloc); + ra(CFG1, SpillIndex, Options, hipe_coalescing_regalloc); optimistic -> - ra(Defun1, SpillIndex, Options, hipe_optimistic_regalloc); + ra(CFG1, SpillIndex, Options, hipe_optimistic_regalloc); graph_color -> - ra(Defun1, SpillIndex, Options, hipe_graph_coloring_regalloc); + ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc); linear_scan -> - hipe_arm_ra_ls:ra(Defun1, SpillIndex, Options); + hipe_arm_ra_ls:ra(CFG1, SpillIndex, Options); naive -> - hipe_arm_ra_naive:ra(Defun1, Coloring_fp, Options); + hipe_arm_ra_naive:ra(CFG1, Coloring_fp, Options); _ -> exit({unknown_regalloc_compiler_option, proplists:get_value(regalloc,Options)}) end, - %% hipe_arm_pp:pp(Defun2), - hipe_arm_ra_finalise:finalise(Defun2, Coloring, Coloring_fp). + %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG2)), + hipe_arm_ra_finalise:finalise(CFG2, Coloring, Coloring_fp). -ra(Defun, SpillIndex, Options, RegAllocMod) -> - hipe_regalloc_loop:ra(Defun, SpillIndex, Options, RegAllocMod, hipe_arm_specific). +ra(CFG, SpillIndex, Options, RegAllocMod) -> + hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, hipe_arm_specific). diff --git a/lib/hipe/arm/hipe_arm_ra_finalise.erl b/lib/hipe/arm/hipe_arm_ra_finalise.erl index 4faeadcd7f..2a3fded147 100644 --- a/lib/hipe/arm/hipe_arm_ra_finalise.erl +++ b/lib/hipe/arm/hipe_arm_ra_finalise.erl @@ -23,12 +23,13 @@ -export([finalise/3]). -include("hipe_arm.hrl"). -finalise(Defun, TempMap, _FPMap0=[]) -> - Code = hipe_arm:defun_code(Defun), - {_, SpillLimit} = hipe_arm:defun_var_range(Defun), +finalise(CFG, TempMap, _FPMap0=[]) -> + {_, SpillLimit} = hipe_gensym:var_range(arm), Map = mk_ra_map(TempMap, SpillLimit), - NewCode = ra_code(Code, Map, []), - Defun#defun{code=NewCode}. + hipe_arm_cfg:map_bbs(fun(_Lbl, BB) -> ra_bb(BB, Map) end, CFG). + +ra_bb(BB, Map) -> + hipe_bb:code_update(BB, ra_code(hipe_bb:code(BB), Map, [])). ra_code([I|Insns], Map, Accum) -> ra_code(Insns, Map, [ra_insn(I, Map) | Accum]); diff --git a/lib/hipe/arm/hipe_arm_ra_ls.erl b/lib/hipe/arm/hipe_arm_ra_ls.erl index d9a360d00c..f9193ca9e0 100644 --- a/lib/hipe/arm/hipe_arm_ra_ls.erl +++ b/lib/hipe/arm/hipe_arm_ra_ls.erl @@ -23,15 +23,12 @@ -module(hipe_arm_ra_ls). -export([ra/3]). -ra(Defun, SpillIndex, Options) -> - NewDefun = Defun, %% hipe_${ARCH}_ra_rename:rename(Defun,Options), - CFG = hipe_arm_cfg:init(NewDefun), +ra(CFG, SpillIndex, Options) -> SpillLimit = hipe_arm_specific:number_of_temporaries(CFG), - alloc(NewDefun, SpillIndex, SpillLimit, Options). + alloc(CFG, SpillIndex, SpillLimit, Options). -alloc(Defun, SpillIndex, SpillLimit, Options) -> - CFG = hipe_arm_cfg:init(Defun), - {Coloring, _NewSpillIndex} = +alloc(CFG, SpillIndex, SpillLimit, Options) -> + {Coloring, _NewSpillIndex, Liveness} = regalloc( CFG, hipe_arm_registers:allocatable_gpr()-- @@ -41,16 +38,16 @@ alloc(Defun, SpillIndex, SpillLimit, Options) -> [hipe_arm_cfg:start_label(CFG)], SpillIndex, SpillLimit, Options, hipe_arm_specific), - {NewDefun, _DidSpill} = + {NewCFG, _DidSpill} = hipe_arm_ra_postconditions:check_and_rewrite( - Defun, Coloring, 'linearscan'), + CFG, Coloring, 'linearscan'), TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_arm_specific), {SpillMap, _NewSpillIndex2} = - hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options, + hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options, hipe_arm_specific, TempMap), Coloring2 = hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), SpillMap), - {NewDefun, Coloring2}. + {NewCFG, Coloring2}. regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) -> hipe_ls_regalloc:regalloc( diff --git a/lib/hipe/arm/hipe_arm_ra_naive.erl b/lib/hipe/arm/hipe_arm_ra_naive.erl index 6201269f44..0ea4b04092 100644 --- a/lib/hipe/arm/hipe_arm_ra_naive.erl +++ b/lib/hipe/arm/hipe_arm_ra_naive.erl @@ -24,7 +24,7 @@ -include("hipe_arm.hrl"). -ra(Defun, _Coloring_fp, _Options) -> % -> {Defun, Coloring} - {NewDefun,_DidSpill} = - hipe_arm_ra_postconditions:check_and_rewrite2(Defun, [], 'naive'), - {NewDefun, []}. +ra(CFG, _Coloring_fp, _Options) -> % -> {CFG, Coloring} + {NewCFG,_DidSpill} = + hipe_arm_ra_postconditions:check_and_rewrite2(CFG, [], 'naive'), + {NewCFG, []}. diff --git a/lib/hipe/arm/hipe_arm_ra_postconditions.erl b/lib/hipe/arm/hipe_arm_ra_postconditions.erl index 40978e65f6..04365f29b0 100644 --- a/lib/hipe/arm/hipe_arm_ra_postconditions.erl +++ b/lib/hipe/arm/hipe_arm_ra_postconditions.erl @@ -25,17 +25,13 @@ -include("hipe_arm.hrl"). -check_and_rewrite(Defun, Coloring, Allocator) -> +check_and_rewrite(CFG, Coloring, Allocator) -> TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_arm_specific), - check_and_rewrite2(Defun, TempMap, Allocator). + check_and_rewrite2(CFG, TempMap, Allocator). -check_and_rewrite2(Defun, TempMap, Allocator) -> +check_and_rewrite2(CFG, TempMap, Allocator) -> Strategy = strategy(Allocator), - #defun{code=Code0} = Defun, - {Code1,DidSpill} = do_insns(Code0, TempMap, Strategy, [], false), - VarRange = {0, hipe_gensym:get_var(arm)}, - {Defun#defun{code=Code1, var_range=VarRange}, - DidSpill}. + do_bbs(hipe_arm_cfg:labels(CFG), TempMap, Strategy, CFG, false). strategy(Allocator) -> case Allocator of @@ -44,6 +40,13 @@ strategy(Allocator) -> 'naive' -> 'fixed' end. +do_bbs([], _, _, CFG, DidSpill) -> {CFG, DidSpill}; +do_bbs([Lbl|Lbls], TempMap, Strategy, CFG0, DidSpill0) -> + Code0 = hipe_bb:code(BB = hipe_arm_cfg:bb(CFG0, Lbl)), + {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0), + CFG = hipe_arm_cfg:bb_add(CFG0, Lbl, hipe_bb:code_update(BB, Code)), + do_bbs(Lbls, TempMap, Strategy, CFG, DidSpill). + do_insns([I|Insns], TempMap, Strategy, Accum, DidSpill0) -> {NewIs, DidSpill1} = do_insn(I, TempMap, Strategy), do_insns(Insns, TempMap, Strategy, lists:reverse(NewIs, Accum), DidSpill0 or DidSpill1); diff --git a/lib/hipe/arm/hipe_rtl_to_arm.erl b/lib/hipe/arm/hipe_rtl_to_arm.erl index 93342aba33..2f9181d517 100644 --- a/lib/hipe/arm/hipe_rtl_to_arm.erl +++ b/lib/hipe/arm/hipe_rtl_to_arm.erl @@ -138,7 +138,6 @@ mk_shift(S, Dst, Src1, ShiftOp, Src2) -> end. mk_shift_ii(S, Dst, Src1, ShiftOp, Src2) -> - io:format("~w: RTL alu with two immediates\n", [?MODULE]), Tmp = new_untagged_temp(), mk_li(Tmp, Src1, mk_shift_ri(S, Dst, Tmp, ShiftOp, Src2)). @@ -179,7 +178,6 @@ mk_arith(S, Dst, Src1, ArithOp, Src2) -> end. mk_arith_ii(S, Dst, Src1, ArithOp, Src2) -> - io:format("~w: RTL alu with two immediates\n", [?MODULE]), Tmp = new_untagged_temp(), mk_li(Tmp, Src1, mk_arith_ri(S, Dst, Tmp, ArithOp, Src2)). @@ -277,7 +275,6 @@ mk_branch(Src1, Cond, Src2, TrueLab, FalseLab, Pred) -> end. mk_branch_ii(Imm1, Cond, Imm2, TrueLab, FalseLab, Pred) -> - io:format("~w: RTL branch with two immediates\n", [?MODULE]), Tmp = new_untagged_temp(), mk_li(Tmp, Imm1, mk_branch_ri(Tmp, Cond, Imm2, @@ -472,7 +469,6 @@ mk_load(Dst, Base1, Base2, LoadSize, LoadSign) -> end. mk_load_ii(Dst, Base1, Base2, LdOp) -> - io:format("~w: RTL load with two immediates\n", [?MODULE]), Tmp = new_untagged_temp(), mk_li(Tmp, Base1, mk_load_ri(Dst, Tmp, Base2, LdOp)). @@ -485,7 +481,6 @@ mk_load_rr(Dst, Base1, Base2, LdOp) -> [hipe_arm:mk_load(LdOp, Dst, Am2)]. mk_ldrsb_ii(Dst, Base1, Base2) -> - io:format("~w: RTL load signed byte with two immediates\n", [?MODULE]), Tmp = new_untagged_temp(), mk_li(Tmp, Base1, mk_ldrsb_ri(Dst, Tmp, Base2)). @@ -543,7 +538,7 @@ conv_return(I, Map, Data) -> {I2, Map0, Data}. conv_store(I, Map, Data) -> - {Base, Map0} = conv_dst(hipe_rtl:store_base(I), Map), + {Base, Map0} = conv_src(hipe_rtl:store_base(I), Map), {Src, Map1} = conv_src(hipe_rtl:store_src(I), Map0), {Offset, Map2} = conv_src(hipe_rtl:store_offset(I), Map1), StoreSize = hipe_rtl:store_size(I), @@ -567,13 +562,28 @@ mk_store(Src, Base, Offset, StoreSize) -> end. mk_store2(Src, Base, Offset, StOp) -> - case hipe_arm:is_temp(Offset) of + case hipe_arm:is_temp(Base) of true -> - mk_store_rr(Src, Base, Offset, StOp); - _ -> - mk_store_ri(Src, Base, Offset, StOp) + case hipe_arm:is_temp(Offset) of + true -> + mk_store_rr(Src, Base, Offset, StOp); + _ -> + mk_store_ri(Src, Base, Offset, StOp) + end; + false -> + case hipe_arm:is_temp(Offset) of + true -> + mk_store_ri(Src, Offset, Base, StOp); + _ -> + mk_store_ii(Src, Base, Offset, StOp) + end end. - + +mk_store_ii(Src, Base, Offset, StOp) -> + Tmp = new_untagged_temp(), + mk_li(Tmp, Base, + mk_store_ri(Src, Tmp, Offset, StOp)). + mk_store_ri(Src, Base, Offset, StOp) -> hipe_arm:mk_store(StOp, Src, Base, Offset, 'new', []). diff --git a/lib/hipe/flow/cfg.inc b/lib/hipe/flow/cfg.inc index a18bfbc526..cb5f397f64 100644 --- a/lib/hipe/flow/cfg.inc +++ b/lib/hipe/flow/cfg.inc @@ -32,6 +32,8 @@ %% bb(CFG, Label) - returns the basic block named 'Label' from the CFG. %% bb_add(CFG, Label, NewBB) - makes NewBB the basic block associated %% with Label. +%% map_bbs(Fun, CFG) - map over all code without changing control flow. +%% fold_bbs(Fun, Acc, CFG) - fold over the basic blocks in a CFG. %% succ(Map, Label) - returns a list of successors of basic block 'Label'. %% pred(Map, Label) - returns the predecessors of basic block 'Label'. %% fallthrough(CFG, Label) - returns fall-through successor of basic @@ -89,6 +91,7 @@ -define(BREADTH_ORDER,true). % for linear scan -define(PARAMS_NEEDED,true). -define(START_LABEL_UPDATE_NEEDED,true). +-define(MAP_FOLD_NEEDED,true). -endif. %%===================================================================== @@ -307,11 +310,7 @@ redirect_phis([I|Rest], OldPred, NewPred, Acc) -> %% @doc Adds a new basic block to a CFG (or updates an existing block). bb_add(CFG, Label, NewBB) -> %% Asserting that the NewBB is a legal basic block - Last = hipe_bb:last(NewBB), - case is_branch(Last) of - true -> ok; - false -> throw({?MODULE, {"Basic block ends without branch", Last}}) - end, + Last = assert_bb(NewBB), %% The order of the elements from branch_successors/1 is %% significant. It determines the basic block order when the CFG is %% converted to linear form. That order may have been tuned for @@ -339,6 +338,48 @@ bb_add(CFG, Label, NewBB) -> HT2, OldSucc -- Succ), CFG#cfg{table = HT3}. +-ifdef(MAP_FOLD_NEEDED). +-spec map_bbs(fun((cfg_lbl(), hipe_bb:bb()) -> hipe_bb:bb()), cfg()) -> cfg(). +%% @doc Map over the code in a CFG without changing any control flow. +map_bbs(Fun, CFG = #cfg{table=HT0}) -> + HT = gb_trees:map( + fun(Lbl, {OldBB, OldSucc, OldPred}) -> + NewBB = Fun(Lbl, OldBB), + %% Assert preconditions + NewLast = assert_bb(NewBB), + OldSucc = remove_duplicates(branch_successors(NewLast)), + {NewBB, OldSucc, OldPred} + end, HT0), + CFG#cfg{table=HT}. + +-spec fold_bbs(fun((cfg_lbl(), hipe_bb:bb(), Acc) -> Acc), Acc, cfg()) -> Acc. +%% @doc Fold over the basic blocks in a CFG in unspecified order. +fold_bbs(Fun, InitAcc, #cfg{table=HT}) -> + gb_trees_fold(fun(Lbl, {BB, _, _}, Acc) -> Fun(Lbl, BB, Acc) end, + InitAcc, HT). + +gb_trees_fold(Fun, InitAcc, Tree) -> + gb_trees_fold_1(Fun, InitAcc, gb_trees:iterator(Tree)). + +gb_trees_fold_1(Fun, InitAcc, Iter0) -> + case gb_trees:next(Iter0) of + none -> InitAcc; + {Key, Value, Iter} -> + gb_trees_fold_1(Fun, Fun(Key, Value, InitAcc), Iter) + end. +-endif. % MAP_FOLD_NEEDED + +assert_bb(BB) -> + assert_bb_is(hipe_bb:code(BB)). + +assert_bb_is([Last]) -> + true = is_branch(Last), + Last; +assert_bb_is([I|Is]) -> + false = is_branch(I), + false = is_label(I), + assert_bb_is(Is). + remove_pred(HT, FromL, PredL) -> case gb_trees:lookup(FromL, HT) of {value, {Block, Succ, Preds}} -> diff --git a/lib/hipe/flow/hipe_bb.erl b/lib/hipe/flow/hipe_bb.erl index 2da3a6dc99..08f5e0a0cb 100644 --- a/lib/hipe/flow/hipe_bb.erl +++ b/lib/hipe/flow/hipe_bb.erl @@ -41,6 +41,8 @@ -include("hipe_bb.hrl"). +-export_type([bb/0]). + %% %% Constructs a basic block. %% Returns a basic block: {bb, Code} diff --git a/lib/hipe/main/hipe.app.src b/lib/hipe/main/hipe.app.src index acae2c637d..6c3a2741b3 100644 --- a/lib/hipe/main/hipe.app.src +++ b/lib/hipe/main/hipe.app.src @@ -49,12 +49,12 @@ hipe_amd64_ra_naive, hipe_amd64_ra_postconditions, hipe_amd64_ra_sse2_postconditions, - hipe_amd64_ra_x87_ls, hipe_amd64_registers, hipe_amd64_specific, hipe_amd64_specific_sse2, hipe_amd64_specific_x87, hipe_amd64_spill_restore, + hipe_amd64_sse2, hipe_amd64_x87, hipe_arm, hipe_arm_assemble, @@ -217,7 +217,6 @@ hipe_x86_ra_ls, hipe_x86_ra_naive, hipe_x86_ra_postconditions, - hipe_x86_ra_x87_ls, hipe_x86_registers, hipe_x86_specific, hipe_x86_specific_x87, diff --git a/lib/hipe/main/hipe.erl b/lib/hipe/main/hipe.erl index 6c525dd143..4e6de2e0dc 100644 --- a/lib/hipe/main/hipe.erl +++ b/lib/hipe/main/hipe.erl @@ -1118,9 +1118,10 @@ help_hiper() -> help_options() -> HostArch = erlang:system_info(hipe_architecture), - O1 = expand_options([o1], HostArch), - O2 = expand_options([o2], HostArch), - O3 = expand_options([o3], HostArch), + O0 = expand_options([o0] ++ ?COMPILE_DEFAULTS, HostArch), + O1 = expand_options([o1] ++ ?COMPILE_DEFAULTS, HostArch), + O2 = expand_options([o2] ++ ?COMPILE_DEFAULTS, HostArch), + O3 = expand_options([o3] ++ ?COMPILE_DEFAULTS, HostArch), io:format("HiPE Compiler Options\n" ++ " Boolean-valued options generally have corresponding " ++ "aliases `no_...',\n" ++ @@ -1139,15 +1140,16 @@ help_options() -> " pp_x86 = pp_native,\n" ++ " pp_amd64 = pp_native,\n" ++ " pp_ppc = pp_native,\n" ++ - " o0,\n" ++ - " o1 = ~p,\n" ++ + " o0 = ~p,\n" ++ + " o1 = ~p ++ o0,\n" ++ " o2 = ~p ++ o1,\n" ++ " o3 = ~p ++ o2.\n", [ordsets:from_list([verbose, debug, time, load, pp_beam, pp_icode, pp_rtl, pp_native, pp_asm, timeout]), expand_options([pp_all], HostArch), - O1 -- [o1], + O0 -- [o0], + (O1 -- O0) -- [o1], (O2 -- O1) -- [o2], (O3 -- O2) -- [o3]]), ok. @@ -1382,8 +1384,15 @@ opt_keys() -> %% Definitions: +o0_opts(_TargetArch) -> + [concurrent_comp, {regalloc,linear_scan}]. + o1_opts(TargetArch) -> - Common = [inline_fp, pmatch, peephole], + Common = [inline_fp, pmatch, peephole, + icode_ssa_const_prop, icode_ssa_copy_prop, icode_inline_bifs, + rtl_ssa, rtl_ssa_const_prop, rtl_ssapre, + spillmin_color, use_indexing, remove_comments, + binary_opt, {regalloc,coalescing} | o0_opts(TargetArch)], case TargetArch of ultrasparc -> Common; @@ -1402,11 +1411,8 @@ o1_opts(TargetArch) -> end. o2_opts(TargetArch) -> - Common = [icode_ssa_const_prop, icode_ssa_copy_prop, % icode_ssa_struct_reuse, - icode_type, icode_inline_bifs, icode_call_elim, rtl_lcm, - rtl_ssa, rtl_ssa_const_prop, - spillmin_color, use_indexing, remove_comments, - concurrent_comp, binary_opt | o1_opts(TargetArch)], + Common = [icode_type, icode_call_elim, % icode_ssa_struct_reuse, + rtl_lcm | (o1_opts(TargetArch) -- [rtl_ssapre])], case TargetArch of T when T =:= amd64 orelse T =:= ppc64 -> % 64-bit targets [icode_range | Common]; @@ -1416,7 +1422,7 @@ o2_opts(TargetArch) -> o3_opts(TargetArch) -> %% no point checking for target architecture since this is checked in 'o1' - [icode_range, {regalloc,coalescing} | o2_opts(TargetArch)]. + [icode_range | o2_opts(TargetArch)]. %% Note that in general, the normal form for options should be positive. %% This is a good programming convention, so that tests in the code say @@ -1481,7 +1487,8 @@ opt_basic_expansions() -> [{pp_all, [pp_beam, pp_icode, pp_rtl, pp_native]}]. opt_expansions(TargetArch) -> - [{o1, o1_opts(TargetArch)}, + [{o0, o0_opts(TargetArch)}, + {o1, o1_opts(TargetArch)}, {o2, o2_opts(TargetArch)}, {o3, o3_opts(TargetArch)}, {to_llvm, llvm_opts(o3, TargetArch)}, @@ -1528,13 +1535,21 @@ expand_kt2(Opts) -> -spec expand_options(comp_options(), hipe_architecture()) -> comp_options(). -expand_options(Opts, TargetArch) -> +expand_options(Opts0, TargetArch) -> + Opts1 = proplists:normalize(Opts0, [{aliases, opt_aliases()}]), + Opts = normalise_opt_options(Opts1), proplists:normalize(Opts, [{negations, opt_negations()}, - {aliases, opt_aliases()}, {expand, opt_basic_expansions()}, {expand, opt_expansions(TargetArch)}, {negations, opt_negations()}]). +normalise_opt_options([o0|Opts]) -> [o0] ++ (Opts -- [o0, o1, o2, o3]); +normalise_opt_options([o1|Opts]) -> [o1] ++ (Opts -- [o0, o1, o2, o3]); +normalise_opt_options([o2|Opts]) -> [o2] ++ (Opts -- [o0, o1, o2, o3]); +normalise_opt_options([o3|Opts]) -> [o3] ++ (Opts -- [o0, o1, o2, o3]); +normalise_opt_options([O|Opts]) -> [O|normalise_opt_options(Opts)]; +normalise_opt_options([]) -> []. + -spec check_options(comp_options()) -> 'ok'. check_options(Opts) -> diff --git a/lib/hipe/opt/hipe_spillmin.erl b/lib/hipe/opt/hipe_spillmin.erl index 4eeb1d71db..6bb6980ad5 100644 --- a/lib/hipe/opt/hipe_spillmin.erl +++ b/lib/hipe/opt/hipe_spillmin.erl @@ -49,7 +49,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -module(hipe_spillmin). --export([stackalloc/6, mapmerge/2]). +-export([stackalloc/6, stackalloc/7, mapmerge/2]). %%-define(DEBUG, 1). -define(HIPE_INSTRUMENT_COMPILER, true). @@ -69,16 +69,24 @@ -spec stackalloc(#cfg{}, [_], non_neg_integer(), comp_options(), module(), hipe_temp_map()) -> - {hipe_spill_map(), non_neg_integer()}. + {hipe_spill_map(), non_neg_integer()}. stackalloc(CFG, StackSlots, SpillIndex, Options, Target, TempMap) -> + Liveness = Target:analyze(CFG), + stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, Target, TempMap). + +-spec stackalloc(#cfg{}, _, [_], non_neg_integer(), + comp_options(), module(), hipe_temp_map()) -> + {hipe_spill_map(), non_neg_integer()}. + +stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, Target, TempMap) -> case proplists:get_bool(spillmin_color, Options) of false -> - ?option_time(hipe_spillmin_scan:stackalloc(CFG, StackSlots, SpillIndex, + ?option_time(hipe_spillmin_scan:stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, Target, TempMap), "Spill minimize, linear scan", Options); true -> - ?option_time(hipe_spillmin_color:stackalloc(CFG, StackSlots, SpillIndex, + ?option_time(hipe_spillmin_color:stackalloc(CFG, Liveness, StackSlots, SpillIndex, Options, Target, TempMap), "Spill minimize, graph coloring", Options) end. diff --git a/lib/hipe/opt/hipe_spillmin_color.erl b/lib/hipe/opt/hipe_spillmin_color.erl index 7c23de44b4..9c62fdf11a 100644 --- a/lib/hipe/opt/hipe_spillmin_color.erl +++ b/lib/hipe/opt/hipe_spillmin_color.erl @@ -41,7 +41,7 @@ -module(hipe_spillmin_color). --export([stackalloc/6]). +-export([stackalloc/7]). %%-ifndef(DO_ASSERT). %%-define(DO_ASSERT, true). @@ -66,13 +66,13 @@ %% where Location is {spill,M}. %% {spill,M} denotes the Mth spilled node --spec stackalloc(#cfg{}, [_], non_neg_integer(), +-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) -> +stackalloc(CFG, Live, _StackSlots, SpillIndex, _Options, Target, TempMap) -> ?report2("building IG~n", []), - {IG, NumNodes} = build_ig(CFG, Target, TempMap), + {IG, NumNodes} = build_ig(CFG, Live, Target, TempMap), {Cols, MaxColors} = color_heuristic(IG, 0, NumNodes, NumNodes, NumNodes, Target, 1), SortedCols = lists:sort(Cols), @@ -167,8 +167,8 @@ remap_temp_map0(Cols, [_Y|Ys], SpillIndex) -> %% Returns {Interference_graph, Number_Of_Nodes} %% -build_ig(CFG, Target, TempMap) -> - try build_ig0(CFG, Target, TempMap) +build_ig(CFG, Live, Target, TempMap) -> + try build_ig0(CFG, Live, Target, TempMap) catch error:Rsn -> exit({regalloc, build_ig, Rsn}) end. @@ -185,8 +185,7 @@ setup_ets0([X|Xs], Table, N) -> ets:insert(Table, {X, N}), setup_ets0(Xs, Table, N+1). -build_ig0(CFG, Target, TempMap) -> - Live = Target:analyze(CFG), +build_ig0(CFG, Live, Target, TempMap) -> TempMapping = map_spilled_temporaries(TempMap), TempMappingTable = setup_ets(TempMapping), NumSpilled = length(TempMapping), diff --git a/lib/hipe/opt/hipe_spillmin_scan.erl b/lib/hipe/opt/hipe_spillmin_scan.erl index 06b68e1934..53cbc0014b 100644 --- a/lib/hipe/opt/hipe_spillmin_scan.erl +++ b/lib/hipe/opt/hipe_spillmin_scan.erl @@ -60,7 +60,7 @@ -module(hipe_spillmin_scan). --export([stackalloc/6]). +-export([stackalloc/7]). %%-define(DEBUG, 1). -define(HIPE_INSTRUMENT_COMPILER, true). @@ -85,15 +85,12 @@ %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% --spec stackalloc(#cfg{}, [_], non_neg_integer(), +-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) -> +stackalloc(CFG, Liveness, 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)]), @@ -538,9 +535,6 @@ extend_interval(Pos, {Beginning, End}) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -liveness(CFG, Target) -> - Target:analyze(CFG). - bb(CFG, L, Target) -> Target:bb(CFG, L). diff --git a/lib/hipe/ppc/hipe_ppc_cfg.erl b/lib/hipe/ppc/hipe_ppc_cfg.erl index 34d4bf54c5..ee9b4432e0 100644 --- a/lib/hipe/ppc/hipe_ppc_cfg.erl +++ b/lib/hipe/ppc/hipe_ppc_cfg.erl @@ -24,6 +24,7 @@ -export([init/1, labels/1, start_label/1, succ/2, + map_bbs/2, fold_bbs/3, bb/2, bb_add/3]). -export([postorder/1]). -export([linearise/1, params/1, reverse_postorder/1]). @@ -34,6 +35,7 @@ -define(BREADTH_ORDER,true). -define(PARAMS_NEEDED,true). -define(START_LABEL_UPDATE_NEEDED,true). +-define(MAP_FOLD_NEEDED,true). -include("hipe_ppc.hrl"). -include("../flow/cfg.hrl"). diff --git a/lib/hipe/ppc/hipe_ppc_frame.erl b/lib/hipe/ppc/hipe_ppc_frame.erl index ff0450270f..8d37159ad8 100644 --- a/lib/hipe/ppc/hipe_ppc_frame.erl +++ b/lib/hipe/ppc/hipe_ppc_frame.erl @@ -24,16 +24,14 @@ -include("hipe_ppc.hrl"). -include("../rtl/hipe_literals.hrl"). -frame(Defun) -> - Formals = fix_formals(hipe_ppc:defun_formals(Defun)), - Temps0 = all_temps(hipe_ppc:defun_code(Defun), Formals), - MinFrame = defun_minframe(Defun), +frame(CFG) -> + Formals = fix_formals(hipe_ppc_cfg:params(CFG)), + Temps0 = all_temps(CFG, Formals), + MinFrame = defun_minframe(CFG), Temps = ensure_minframe(MinFrame, Temps0), - ClobbersLR = clobbers_lr(hipe_ppc:defun_code(Defun)), - CFG0 = hipe_ppc_cfg:init(Defun), - Liveness = hipe_ppc_liveness_all:analyse(CFG0), - CFG1 = do_body(CFG0, Liveness, Formals, Temps, ClobbersLR), - hipe_ppc_cfg:linearise(CFG1). + ClobbersLR = clobbers_lr(CFG), + Liveness = hipe_ppc_liveness_all:analyse(CFG), + do_body(CFG, Liveness, Formals, Temps, ClobbersLR). fix_formals(Formals) -> fix_formals(hipe_ppc_registers:nr_args(), Formals). @@ -44,27 +42,16 @@ fix_formals(_, []) -> []. do_body(CFG0, Liveness, Formals, Temps, ClobbersLR) -> Context = mk_context(Liveness, Formals, Temps, ClobbersLR), - CFG1 = do_blocks(CFG0, Context), + CFG1 = hipe_ppc_cfg:map_bbs( + fun(Lbl, BB) -> do_block(Lbl, BB, Context) end, CFG0), do_prologue(CFG1, Context). -do_blocks(CFG, Context) -> - Labels = hipe_ppc_cfg:labels(CFG), - do_blocks(Labels, CFG, Context). - -do_blocks([Label|Labels], CFG, Context) -> +do_block(Label, Block, Context) -> Liveness = context_liveness(Context), LiveOut = hipe_ppc_liveness_all:liveout(Liveness, Label), - Block = hipe_ppc_cfg:bb(CFG, Label), Code = hipe_bb:code(Block), - NewCode = do_block(Code, LiveOut, Context), - NewBlock = hipe_bb:code_update(Block, NewCode), - NewCFG = hipe_ppc_cfg:bb_add(CFG, Label, NewBlock), - do_blocks(Labels, NewCFG, Context); -do_blocks([], CFG, _) -> - CFG. - -do_block(Insns, LiveOut, Context) -> - do_block(Insns, LiveOut, Context, context_framesize(Context), []). + NewCode = do_block(Code, LiveOut, Context, context_framesize(Context), []), + hipe_bb:code_update(Block, NewCode). do_block([I|Insns], LiveOut, Context, FPoff0, RevCode) -> {NewIs, FPoff1} = do_insn(I, LiveOut, Context, FPoff0), @@ -573,29 +560,41 @@ temp_is_pseudo(Temp) -> %%% Detect if a Defun's body clobbers LR. %%% -clobbers_lr([I|Insns]) -> - case I of - #pseudo_call{} -> true; - %% mtspr to lr cannot occur yet - _ -> clobbers_lr(Insns) - end; -clobbers_lr([]) -> false. +clobbers_lr(CFG) -> + any_insn(fun(#pseudo_call{}) -> true; + (_) -> false + end, CFG). + +any_insn(Pred, CFG) -> + %% Abuse fold to do an efficient "any"-operation using nonlocal control flow + FoundSatisfying = make_ref(), + try fold_insns(fun (I, _) -> + case Pred(I) of + true -> throw(FoundSatisfying); + false -> false + end + end, false, CFG) + of _ -> false + catch FoundSatisfying -> true + end. %%% %%% Build the set of all temps used in a Defun's body. %%% -all_temps(Code, Formals) -> - S0 = find_temps(Code, tset_empty()), +all_temps(CFG, Formals) -> + S0 = fold_insns(fun find_temps/2, tset_empty(), CFG), S1 = tset_del_list(S0, Formals), tset_filter(S1, fun(T) -> temp_is_pseudo(T) end). -find_temps([I|Insns], S0) -> +find_temps(I, S0) -> S1 = tset_add_list(S0, hipe_ppc_defuse:insn_def_all(I)), - S2 = tset_add_list(S1, hipe_ppc_defuse:insn_use_all(I)), - find_temps(Insns, S2); -find_temps([], S) -> - S. + tset_add_list(S1, hipe_ppc_defuse:insn_use_all(I)). + +fold_insns(Fun, InitAcc, CFG) -> + hipe_ppc_cfg:fold_bbs( + fun(_, BB, Acc0) -> lists:foldl(Fun, Acc0, hipe_bb:code(BB)) end, + InitAcc, CFG). tset_empty() -> gb_sets:new(). @@ -624,16 +623,11 @@ tset_to_list(S) -> %%% in the middle of a tailcall. %%% -defun_minframe(Defun) -> - MaxTailArity = body_mta(hipe_ppc:defun_code(Defun), 0), - MyArity = length(fix_formals(hipe_ppc:defun_formals(Defun))), +defun_minframe(CFG) -> + MaxTailArity = fold_insns(fun insn_mta/2, 0, CFG), + MyArity = length(fix_formals(hipe_ppc_cfg:params(CFG))), erlang:max(MaxTailArity - MyArity, 0). -body_mta([I|Code], MTA) -> - body_mta(Code, insn_mta(I, MTA)); -body_mta([], MTA) -> - MTA. - insn_mta(I, MTA) -> case I of #pseudo_tailcall{arity=Arity} -> diff --git a/lib/hipe/ppc/hipe_ppc_main.erl b/lib/hipe/ppc/hipe_ppc_main.erl index fd5cc2befb..5d1b0d0305 100644 --- a/lib/hipe/ppc/hipe_ppc_main.erl +++ b/lib/hipe/ppc/hipe_ppc_main.erl @@ -24,8 +24,10 @@ rtl_to_ppc(MFA, RTL, Options) -> PPC1 = hipe_rtl_to_ppc:translate(RTL), - PPC2 = hipe_ppc_ra:ra(PPC1, Options), - PPC3 = hipe_ppc_frame:frame(PPC2), + PPC1CFG = hipe_ppc_cfg:init(PPC1), + PPC2CFG = hipe_ppc_ra:ra(PPC1CFG, Options), + PPC3CFG = hipe_ppc_frame:frame(PPC2CFG), + PPC3 = hipe_ppc_cfg:linearise(PPC3CFG), PPC4 = hipe_ppc_finalise:finalise(PPC3), ppc_pp(PPC4, MFA, Options), {native, powerpc, {unprofiled, PPC4}}. diff --git a/lib/hipe/ppc/hipe_ppc_ra.erl b/lib/hipe/ppc/hipe_ppc_ra.erl index 87c776f5d1..bfb4d35139 100644 --- a/lib/hipe/ppc/hipe_ppc_ra.erl +++ b/lib/hipe/ppc/hipe_ppc_ra.erl @@ -22,36 +22,36 @@ -module(hipe_ppc_ra). -export([ra/2]). -ra(Defun0, Options) -> - %% hipe_ppc_pp:pp(Defun0), - {Defun1, Coloring_fp, SpillIndex} +ra(CFG0, Options) -> + %% hipe_ppc_pp:pp(hipe_ppc_cfg:linearise(CFG0)), + {CFG1, Coloring_fp, SpillIndex} = case proplists:get_bool(inline_fp, Options) of true -> - hipe_regalloc_loop:ra_fp(Defun0, Options, + hipe_regalloc_loop:ra_fp(CFG0, Options, hipe_coalescing_regalloc, hipe_ppc_specific_fp); false -> - {Defun0,[],0} + {CFG0,[],0} end, - %% hipe_ppc_pp:pp(Defun1), - {Defun2, Coloring} + %% hipe_ppc_pp:pp(hipe_ppc_cfg:linearise(CFG1)), + {CFG2, Coloring} = case proplists:get_value(regalloc, Options, coalescing) of coalescing -> - ra(Defun1, SpillIndex, Options, hipe_coalescing_regalloc); + ra(CFG1, SpillIndex, Options, hipe_coalescing_regalloc); optimistic -> - ra(Defun1, SpillIndex, Options, hipe_optimistic_regalloc); + ra(CFG1, SpillIndex, Options, hipe_optimistic_regalloc); graph_color -> - ra(Defun1, SpillIndex, Options, hipe_graph_coloring_regalloc); + ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc); linear_scan -> - hipe_ppc_ra_ls:ra(Defun1, SpillIndex, Options); + hipe_ppc_ra_ls:ra(CFG1, SpillIndex, Options); naive -> - hipe_ppc_ra_naive:ra(Defun1, Coloring_fp, Options); + hipe_ppc_ra_naive:ra(CFG1, Coloring_fp, Options); _ -> exit({unknown_regalloc_compiler_option, proplists:get_value(regalloc,Options)}) end, - %% hipe_ppc_pp:pp(Defun2), - hipe_ppc_ra_finalise:finalise(Defun2, Coloring, Coloring_fp). + %% hipe_ppc_pp:pp(hipe_ppc_cfg:linearise(CFG2)), + hipe_ppc_ra_finalise:finalise(CFG2, Coloring, Coloring_fp). -ra(Defun, SpillIndex, Options, RegAllocMod) -> - hipe_regalloc_loop:ra(Defun, SpillIndex, Options, RegAllocMod, hipe_ppc_specific). +ra(CFG, SpillIndex, Options, RegAllocMod) -> + hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, hipe_ppc_specific). diff --git a/lib/hipe/ppc/hipe_ppc_ra_finalise.erl b/lib/hipe/ppc/hipe_ppc_ra_finalise.erl index ea163221c2..78f123116e 100644 --- a/lib/hipe/ppc/hipe_ppc_ra_finalise.erl +++ b/lib/hipe/ppc/hipe_ppc_ra_finalise.erl @@ -23,13 +23,14 @@ -export([finalise/3]). -include("hipe_ppc.hrl"). -finalise(Defun, TempMap, FPMap0) -> - Code = hipe_ppc:defun_code(Defun), - {_, SpillLimit} = hipe_ppc:defun_var_range(Defun), +finalise(CFG, TempMap, FPMap0) -> + {_, SpillLimit} = hipe_gensym:var_range(ppc), Map = mk_ra_map(TempMap, SpillLimit), FPMap1 = mk_ra_map_fp(FPMap0, SpillLimit), - NewCode = ra_code(Code, Map, FPMap1, []), - Defun#defun{code=NewCode}. + hipe_ppc_cfg:map_bbs(fun(_Lbl, BB) -> ra_bb(BB, Map, FPMap1) end, CFG). + +ra_bb(BB, Map, FpMap) -> + hipe_bb:code_update(BB, ra_code(hipe_bb:code(BB), Map, FpMap, [])). ra_code([I|Insns], Map, FPMap, Accum) -> ra_code(Insns, Map, FPMap, [ra_insn(I, Map, FPMap) | Accum]); diff --git a/lib/hipe/ppc/hipe_ppc_ra_ls.erl b/lib/hipe/ppc/hipe_ppc_ra_ls.erl index 6e8304467e..52562fc321 100644 --- a/lib/hipe/ppc/hipe_ppc_ra_ls.erl +++ b/lib/hipe/ppc/hipe_ppc_ra_ls.erl @@ -23,15 +23,12 @@ -module(hipe_ppc_ra_ls). -export([ra/3]). -ra(Defun, SpillIndex, Options) -> - NewDefun = Defun, %% hipe_${ARCH}_ra_rename:rename(Defun,Options), - CFG = hipe_ppc_cfg:init(NewDefun), +ra(CFG, SpillIndex, Options) -> SpillLimit = hipe_ppc_specific:number_of_temporaries(CFG), - alloc(NewDefun, SpillIndex, SpillLimit, Options). + alloc(CFG, SpillIndex, SpillLimit, Options). -alloc(Defun, SpillIndex, SpillLimit, Options) -> - CFG = hipe_ppc_cfg:init(Defun), - {Coloring, _NewSpillIndex} = +alloc(CFG, SpillIndex, SpillLimit, Options) -> + {Coloring, _NewSpillIndex, Liveness} = regalloc( CFG, hipe_ppc_registers:allocatable_gpr()-- @@ -41,16 +38,16 @@ alloc(Defun, SpillIndex, SpillLimit, Options) -> [hipe_ppc_cfg:start_label(CFG)], SpillIndex, SpillLimit, Options, hipe_ppc_specific), - {NewDefun, _DidSpill} = + {NewCFG, _DidSpill} = hipe_ppc_ra_postconditions:check_and_rewrite( - Defun, Coloring, 'linearscan'), + CFG, Coloring, 'linearscan'), TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific), {TempMap2,_NewSpillIndex2} = - hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options, + hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options, hipe_ppc_specific, TempMap), Coloring2 = hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2), - {NewDefun, Coloring2}. + {NewCFG, Coloring2}. regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) -> hipe_ls_regalloc:regalloc( diff --git a/lib/hipe/ppc/hipe_ppc_ra_naive.erl b/lib/hipe/ppc/hipe_ppc_ra_naive.erl index 24995be252..ba269ae981 100644 --- a/lib/hipe/ppc/hipe_ppc_ra_naive.erl +++ b/lib/hipe/ppc/hipe_ppc_ra_naive.erl @@ -24,7 +24,7 @@ -include("hipe_ppc.hrl"). -ra(Defun, _Coloring_fp, _Options) -> % -> {Defun, Coloring} - {NewDefun,_DidSpill} = - hipe_ppc_ra_postconditions:check_and_rewrite2(Defun, [], 'naive'), - {NewDefun, []}. +ra(CFG, _Coloring_fp, _Options) -> % -> {CFG, Coloring} + {NewCFG,_DidSpill} = + hipe_ppc_ra_postconditions:check_and_rewrite2(CFG, [], 'naive'), + {NewCFG, []}. diff --git a/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl b/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl index 0b16ec3891..412aeeeba6 100644 --- a/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl +++ b/lib/hipe/ppc/hipe_ppc_ra_postconditions.erl @@ -25,17 +25,13 @@ -include("hipe_ppc.hrl"). -check_and_rewrite(Defun, Coloring, Allocator) -> +check_and_rewrite(CFG, Coloring, Allocator) -> TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific), - check_and_rewrite2(Defun, TempMap, Allocator). + check_and_rewrite2(CFG, TempMap, Allocator). -check_and_rewrite2(Defun, TempMap, Allocator) -> +check_and_rewrite2(CFG, TempMap, Allocator) -> Strategy = strategy(Allocator), - #defun{code=Code0} = Defun, - {Code1,DidSpill} = do_insns(Code0, TempMap, Strategy, [], false), - VarRange = {0, hipe_gensym:get_var(ppc)}, - {Defun#defun{code=Code1, var_range=VarRange}, - DidSpill}. + do_bbs(hipe_ppc_cfg:labels(CFG), TempMap, Strategy, CFG, false). strategy(Allocator) -> case Allocator of @@ -44,6 +40,13 @@ strategy(Allocator) -> 'naive' -> 'fixed' end. +do_bbs([], _, _, CFG, DidSpill) -> {CFG, DidSpill}; +do_bbs([Lbl|Lbls], TempMap, Strategy, CFG0, DidSpill0) -> + Code0 = hipe_bb:code(BB = hipe_ppc_cfg:bb(CFG0, Lbl)), + {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0), + CFG = hipe_ppc_cfg:bb_add(CFG0, Lbl, hipe_bb:code_update(BB, Code)), + do_bbs(Lbls, TempMap, Strategy, CFG, DidSpill). + do_insns([I|Insns], TempMap, Strategy, Accum, DidSpill0) -> {NewIs, DidSpill1} = do_insn(I, TempMap, Strategy), do_insns(Insns, TempMap, Strategy, lists:reverse(NewIs, Accum), DidSpill0 or DidSpill1); diff --git a/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl b/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl index 821aa66c11..553fac882b 100644 --- a/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl +++ b/lib/hipe/ppc/hipe_ppc_ra_postconditions_fp.erl @@ -23,13 +23,16 @@ -export([check_and_rewrite/2]). -include("hipe_ppc.hrl"). -check_and_rewrite(Defun, Coloring) -> +check_and_rewrite(CFG, Coloring) -> TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_ppc_specific_fp), - #defun{code=Code0} = Defun, - {Code1,DidSpill} = do_insns(Code0, TempMap, [], false), - VarRange = {0, hipe_gensym:get_var(ppc)}, - {Defun#defun{code=Code1, var_range=VarRange}, - DidSpill}. + do_bbs(hipe_ppc_cfg:labels(CFG), TempMap, CFG, false). + +do_bbs([], _TempMap, CFG, DidSpill) -> {CFG, DidSpill}; +do_bbs([Lbl|Lbls], TempMap, CFG0, DidSpill0) -> + Code0 = hipe_bb:code(BB = hipe_ppc_cfg:bb(CFG0, Lbl)), + {Code, DidSpill} = do_insns(Code0, TempMap, [], DidSpill0), + CFG = hipe_ppc_cfg:bb_add(CFG0, Lbl, hipe_bb:code_update(BB, Code)), + do_bbs(Lbls, TempMap, CFG, DidSpill). do_insns([I|Insns], TempMap, Accum, DidSpill0) -> {NewIs, DidSpill1} = do_insn(I, TempMap), diff --git a/lib/hipe/ppc/hipe_rtl_to_ppc.erl b/lib/hipe/ppc/hipe_rtl_to_ppc.erl index a994659616..a01e67a789 100644 --- a/lib/hipe/ppc/hipe_rtl_to_ppc.erl +++ b/lib/hipe/ppc/hipe_rtl_to_ppc.erl @@ -1031,7 +1031,7 @@ conv_return(I, Map, Data) -> {I2, Map0, Data}. conv_store(I, Map, Data) -> - {Base1, Map0} = conv_dst(hipe_rtl:store_base(I), Map), + {Base1, Map0} = conv_src(hipe_rtl:store_base(I), Map), {Src, Map1} = conv_src(hipe_rtl:store_src(I), Map0), {Base2, Map2} = conv_src(hipe_rtl:store_offset(I), Map1), StoreSize = hipe_rtl:store_size(I), @@ -1056,13 +1056,28 @@ mk_store(Src, Base1, Base2, StoreSize) -> end. mk_store2(Src, Base1, Base2, StOp) -> - case hipe_ppc:is_temp(Base2) of + case hipe_ppc:is_temp(Base1) of true -> - mk_store_rr(Src, Base1, Base2, StOp); + case hipe_ppc:is_temp(Base2) of + true -> + mk_store_rr(Src, Base1, Base2, StOp); + _ -> + mk_store_ri(Src, Base1, Base2, StOp) + end; _ -> - mk_store_ri(Src, Base1, Base2, StOp) + case hipe_ppc:is_temp(Base2) of + true -> + mk_store_ri(Src, Base2, Base1, StOp); + _ -> + mk_store_ii(Src, Base1, Base2, StOp) + end end. - + +mk_store_ii(Src, Base, Disp, StOp) -> + Tmp = new_untagged_temp(), + mk_li(Tmp, Base, + mk_store_ri(Src, Tmp, Disp, StOp)). + mk_store_ri(Src, Base, Disp, StOp) -> hipe_ppc:mk_store(StOp, Src, Disp, Base, 'new', []). diff --git a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl index 50e5869d45..2e5804337d 100644 --- a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl +++ b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl @@ -42,7 +42,9 @@ reg_nr/1, non_alloc/1, allocatable/0, - physical_name/1, + allocatable/1, + temp0/0, + physical_name/1, all_precoloured/0, new_spill_index/1, %% used by hipe_ls_regalloc var_range/1, @@ -52,7 +54,8 @@ %% callbacks for hipe_regalloc_loop -export([defun_to_cfg/1, - check_and_rewrite/2]). + check_and_rewrite/2, + check_and_rewrite/3]). %%---------------------------------------------------------------------------- @@ -60,11 +63,15 @@ %%---------------------------------------------------------------------------- -defun_to_cfg(Defun) -> - hipe_x86_cfg:init(Defun). +defun_to_cfg(AlreadyACFG) -> + AlreadyACFG. -check_and_rewrite(Defun, Coloring) -> - hipe_amd64_ra_sse2_postconditions:check_and_rewrite(Defun, Coloring). +check_and_rewrite(CFG, Coloring) -> + hipe_amd64_ra_sse2_postconditions:check_and_rewrite(CFG, Coloring). + +check_and_rewrite(CFG, Coloring, Strategy) -> + hipe_amd64_ra_sse2_postconditions:check_and_rewrite( + CFG, Coloring, Strategy). reverse_postorder(CFG) -> hipe_x86_cfg:reverse_postorder(CFG). @@ -75,8 +82,8 @@ breadthorder(CFG) -> postorder(CFG) -> hipe_x86_cfg:postorder(CFG). -is_global(_Reg) -> - false. +is_global(Reg) -> + hipe_amd64_registers:sse2_temp0() =:= Reg. is_fixed(_Reg) -> false. @@ -109,7 +116,16 @@ liveout(BB_in_out_liveness, Label) -> %% Registers stuff allocatable() -> - hipe_amd64_registers:allocatable_sse2(). + allocatable('normal'). + +allocatable('normal') -> + hipe_amd64_registers:allocatable_sse2(); +allocatable('linearscan') -> + hipe_amd64_registers:allocatable_sse2() -- + [hipe_amd64_registers:sse2_temp0()]. + +temp0() -> + hipe_amd64_registers:sse2_temp0(). all_precoloured() -> allocatable(). diff --git a/lib/hipe/regalloc/hipe_arm_specific.erl b/lib/hipe/regalloc/hipe_arm_specific.erl index 4e34cb1d99..e04d80f690 100644 --- a/lib/hipe/regalloc/hipe_arm_specific.erl +++ b/lib/hipe/regalloc/hipe_arm_specific.erl @@ -53,11 +53,11 @@ -export([defun_to_cfg/1, check_and_rewrite/2]). -defun_to_cfg(Defun) -> - hipe_arm_cfg:init(Defun). +defun_to_cfg(AlreadyACFG) -> + AlreadyACFG. -check_and_rewrite(Defun, Coloring) -> - hipe_arm_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal'). +check_and_rewrite(CFG, Coloring) -> + hipe_arm_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal'). reverse_postorder(CFG) -> hipe_arm_cfg:reverse_postorder(CFG). diff --git a/lib/hipe/regalloc/hipe_coalescing_regalloc.erl b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl index e2f817d369..bbb2e3ecf0 100644 --- a/lib/hipe/regalloc/hipe_coalescing_regalloc.erl +++ b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl @@ -51,13 +51,14 @@ %% %% Returns: %% Coloring -- A coloring for specified CFG -%% SpillIndex0 -- A new spill index +%% SpillIndex2 -- A new spill index %%----------------------------------------------------------------------- regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> %% Build interference graph ?debug_msg("Build IG\n", []), - IG = hipe_ig:build(CFG, Target), + Liveness = Target:analyze(CFG), + IG = hipe_ig:build(CFG, Liveness, Target), %% io:format("IG: ~p\n", [IG]), ?debug_msg("Init\n", []), @@ -94,9 +95,10 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> %% io:format("color0:~w\nColor1:~w\nNodes:~w\nNodes2:~w\nNum_Temps:~w\n",[Color0,Color1,Node_sets,Node_sets2,Num_Temps]), ?debug_msg("Build mapping ~p\n", [Node_sets2]), - Coloring = build_namelist(Node_sets2, SpillIndex, Alias0, Color1), + {Coloring, SpillIndex2} = + build_namelist(Node_sets2, SpillIndex, Alias0, Color1), ?debug_msg("Coloring ~p\n", [Coloring]), - Coloring. + {Coloring, SpillIndex2, Liveness}. %%---------------------------------------------------------------------- %% Function: do_coloring diff --git a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl index bc6e442236..1a3ea90c05 100644 --- a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl +++ b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl @@ -82,7 +82,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> PhysRegs = Target:allocatable(), ?report2("building IG~n", []), - {IG, Spill} = build_ig(CFG, Target), + {IG, Spill, Live} = build_ig(CFG, Target), %% check_ig(IG), ?report3("graph: ~p~nphysical regs: ~p~n", [list_ig(IG), PhysRegs]), @@ -102,7 +102,7 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> Coloring = [{X, {reg, X}} || X <- NotAllocatable] ++ Cols, ?ASSERT(check_coloring(Coloring, IG, Target)), - {Coloring, NewSpillIndex}. + {Coloring, NewSpillIndex, Live}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -126,7 +126,7 @@ build_ig0(CFG, Target) -> empty_ig(NumN), empty_spill(NumN), Target), - {normalize_ig(IG), Spill}. + {normalize_ig(IG), Spill, Live}. build_ig_bbs([], _CFG, _Live, IG, Spill, _Target) -> {IG, Spill}; diff --git a/lib/hipe/regalloc/hipe_ig.erl b/lib/hipe/regalloc/hipe_ig.erl index 8fd5d0df1f..47f8f6d08d 100644 --- a/lib/hipe/regalloc/hipe_ig.erl +++ b/lib/hipe/regalloc/hipe_ig.erl @@ -28,7 +28,7 @@ -module(hipe_ig). --export([build/2, +-export([build/3, nodes_are_adjacent/3, node_spill_cost/2, node_adj_list/2, @@ -368,10 +368,9 @@ initial_ig(NumTemps, Target) -> %% An interference graph for the given CFG. %%---------------------------------------------------------------------- --spec build(#cfg{}, atom()) -> #igraph{}. +-spec build(#cfg{}, Liveness::_, atom()) -> #igraph{}. -build(CFG, Target) -> - BBs_in_out_liveness = Target:analyze(CFG), +build(CFG, BBs_in_out_liveness, Target) -> Labels = Target:labels(CFG), %% How many temporaries exist? NumTemps = Target:number_of_temporaries(CFG), diff --git a/lib/hipe/regalloc/hipe_ls_regalloc.erl b/lib/hipe/regalloc/hipe_ls_regalloc.erl index d24b803524..c318927077 100644 --- a/lib/hipe/regalloc/hipe_ls_regalloc.erl +++ b/lib/hipe/regalloc/hipe_ls_regalloc.erl @@ -56,7 +56,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -module(hipe_ls_regalloc). --export([regalloc/7]). +-export([regalloc/7, regalloc/8]). %%-define(DEBUG,1). -define(HIPE_INSTRUMENT_COMPILER, true). @@ -96,10 +96,18 @@ %% @end %%- - - - - - - - - - - - - - - - - - - - - - - - regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) -> + regalloc(CFG, undefined, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target). + +regalloc(CFG, Liveness0, 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)]), + Liveness = case Liveness0 of + undefined -> + L=liveness(CFG, Target), + ?debug_msg("liveness (done)~w\n", [erlang:statistics(runtime)]), + L; + _ -> Liveness0 + end, USIntervals = calculate_intervals(CFG, Liveness, Entrypoints, Options, Target), ?debug_msg("intervals (done) ~w\n", [erlang:statistics(runtime)]), @@ -108,10 +116,10 @@ regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) -> %% ?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), + {Coloring, NewSpillIndex} + = allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target), ?debug_msg("allocation (done) ~w\n", [erlang:statistics(runtime)]), - Allocation. - + {Coloring, NewSpillIndex, Liveness}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% diff --git a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl index 2ed9ec3b45..67674be14c 100644 --- a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl +++ b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl @@ -78,7 +78,7 @@ %% %% Returns: %% Coloring -- A coloring for specified CFG -%% SpillIndex0 -- A new spill index +%% SpillIndex2 -- A new spill index %%----------------------------------------------------------------------- -ifdef(COMPARE_ITERATED_OPTIMISTIC). regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> @@ -86,8 +86,9 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ?debug_msg("CFG: ~p\n",[CFG]), %% Build interference graph ?debug_msg("Build IG\n",[]), - IG_O = hipe_ig:build(CFG, Target), - IG = hipe_ig:build(CFG, Target), + Liveness = Target:analyze(CFG), + IG_O = hipe_ig:build(CFG, Liveness, Target), + IG = hipe_ig:build(CFG, Liveness, Target), ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]), ?debug_msg("IG:\n",[]), ?print_adjacent(IG), @@ -199,9 +200,10 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]), ?debug_msg("Build mapping _N ~w\n",[Node_sets2]), - Coloring = build_namelist(Node_sets2,SpillIndex,Alias2,Color1), + {Coloring,SpillIndex2} = + build_namelist(Node_sets2,SpillIndex,Alias2,Color1), ?debug_msg("Coloring ~p\n",[Coloring]), - SortedColoring = { sort_stack(element(1, Coloring)), element(2, Coloring)}, + SortedColoring = {sort_stack(Coloring), SpillIndex2}, ?debug_msg("SortedColoring ~p\n",[SortedColoring]), %%Coloring. ?debug_msg("----------------------Assign colors _O\n",[]), @@ -217,14 +219,15 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> SortedColoring_O = {sort_stack(element(1, Coloring_O)), element(2, Coloring_O)}, ?debug_msg("SortedColoring_O ~p\n",[SortedColoring_O]), sanity_compare(SortedColoring_O, SortedColoring), - Coloring. + {Coloring,SpillIndex2,Liveness}. -else. regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ?debug_msg("optimistic ~w\n",[Target]), ?debug_msg("CFG: ~p\n",[CFG]), %% Build interference graph ?debug_msg("Build IG\n",[]), - IG = hipe_ig:build(CFG, Target), + Liveness = Target:analyze(CFG), + IG = hipe_ig:build(CFG, Liveness, Target), ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]), ?debug_msg("IG:\n",[]), ?print_adjacent(IG), @@ -316,9 +319,9 @@ regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]), ?debug_msg("Build mapping _N ~w\n",[Node_sets2]), - Coloring = build_namelist(Node_sets2,SpillIndex,Alias2,Color1), + {Coloring, SpillIndex2} = build_namelist(Node_sets2,SpillIndex,Alias2,Color1), ?debug_msg("Coloring ~p\n",[Coloring]), - Coloring. + {Coloring,SpillIndex2,Liveness}. -endif. %%---------------------------------------------------------------------- diff --git a/lib/hipe/regalloc/hipe_ppc_specific.erl b/lib/hipe/regalloc/hipe_ppc_specific.erl index c49b1e510f..988501c96f 100644 --- a/lib/hipe/regalloc/hipe_ppc_specific.erl +++ b/lib/hipe/regalloc/hipe_ppc_specific.erl @@ -53,11 +53,11 @@ -export([defun_to_cfg/1, check_and_rewrite/2]). -defun_to_cfg(Defun) -> - hipe_ppc_cfg:init(Defun). +defun_to_cfg(AlreadyACFG) -> + AlreadyACFG. -check_and_rewrite(Defun, Coloring) -> - hipe_ppc_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal'). +check_and_rewrite(CFG, Coloring) -> + hipe_ppc_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal'). reverse_postorder(CFG) -> hipe_ppc_cfg:reverse_postorder(CFG). diff --git a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl index 454aa4c686..6f00111777 100644 --- a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl +++ b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl @@ -53,11 +53,11 @@ -export([defun_to_cfg/1, check_and_rewrite/2]). -defun_to_cfg(Defun) -> - hipe_ppc_cfg:init(Defun). +defun_to_cfg(AlreadyACFG) -> + AlreadyACFG. -check_and_rewrite(Defun, Coloring) -> - hipe_ppc_ra_postconditions_fp:check_and_rewrite(Defun, Coloring). +check_and_rewrite(CFG, Coloring) -> + hipe_ppc_ra_postconditions_fp:check_and_rewrite(CFG, Coloring). reverse_postorder(CFG) -> hipe_ppc_cfg:reverse_postorder(CFG). diff --git a/lib/hipe/regalloc/hipe_regalloc_loop.erl b/lib/hipe/regalloc/hipe_regalloc_loop.erl index d29615a3a0..fa42cdd0fb 100644 --- a/lib/hipe/regalloc/hipe_regalloc_loop.erl +++ b/lib/hipe/regalloc/hipe_regalloc_loop.erl @@ -38,20 +38,19 @@ ra_common(Defun, SpillIndex, Options, RegAllocMod, TargetMod) -> ?inc_counter(ra_calls_counter, 1), CFG = TargetMod:defun_to_cfg(Defun), SpillLimit = TargetMod:number_of_temporaries(CFG), - alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod). + alloc(Defun, CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod). -alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) -> +alloc(Defun, CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) -> ?inc_counter(ra_iteration_counter, 1), - CFG = TargetMod:defun_to_cfg(Defun), - {Coloring, _NewSpillIndex} = - RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit, TargetMod, Options), + {Coloring, _NewSpillIndex, Liveness} = + RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit,TargetMod, Options), {NewDefun, DidSpill} = TargetMod:check_and_rewrite(Defun, Coloring), case DidSpill of false -> %% No new temps, we are done. ?add_spills(Options, _NewSpillIndex), TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod), - {TempMap2, NewSpillIndex2} = - hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options, + {TempMap2, NewSpillIndex2} = + hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options, TargetMod, TempMap), Coloring2 = hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2), @@ -63,7 +62,8 @@ alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) -> %% end, {NewDefun, Coloring2, NewSpillIndex2}; _ -> + NewCFG = TargetMod:defun_to_cfg(NewDefun), %% Since SpillLimit is used as a low-water-mark %% the list of temps not to spill is uninteresting. - alloc(NewDefun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) + alloc(NewDefun, NewCFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) end. diff --git a/lib/hipe/regalloc/hipe_sparc_specific.erl b/lib/hipe/regalloc/hipe_sparc_specific.erl index 8d34604f84..29d0908caf 100644 --- a/lib/hipe/regalloc/hipe_sparc_specific.erl +++ b/lib/hipe/regalloc/hipe_sparc_specific.erl @@ -53,11 +53,11 @@ -export([defun_to_cfg/1, check_and_rewrite/2]). -defun_to_cfg(Defun) -> - hipe_sparc_cfg:init(Defun). +defun_to_cfg(AlreadyACFG) -> + AlreadyACFG. -check_and_rewrite(Defun, Coloring) -> - hipe_sparc_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal'). +check_and_rewrite(CFG, Coloring) -> + hipe_sparc_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal'). reverse_postorder(CFG) -> hipe_sparc_cfg:reverse_postorder(CFG). diff --git a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl index 2edd3cb47e..08c2541b41 100644 --- a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl +++ b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl @@ -53,11 +53,11 @@ -export([defun_to_cfg/1, check_and_rewrite/2]). -defun_to_cfg(Defun) -> - hipe_sparc_cfg:init(Defun). +defun_to_cfg(AlreadyACFG) -> + AlreadyACFG. -check_and_rewrite(Defun, Coloring) -> - hipe_sparc_ra_postconditions_fp:check_and_rewrite(Defun, Coloring). +check_and_rewrite(CFG, Coloring) -> + hipe_sparc_ra_postconditions_fp:check_and_rewrite(CFG, Coloring). reverse_postorder(CFG) -> hipe_sparc_cfg:reverse_postorder(CFG). diff --git a/lib/hipe/regalloc/hipe_x86_specific.erl b/lib/hipe/regalloc/hipe_x86_specific.erl index 4edf8674b7..f1007c95ed 100644 --- a/lib/hipe/regalloc/hipe_x86_specific.erl +++ b/lib/hipe/regalloc/hipe_x86_specific.erl @@ -68,11 +68,11 @@ -export([defun_to_cfg/1, check_and_rewrite/2]). -defun_to_cfg(Defun) -> - hipe_x86_cfg:init(Defun). +defun_to_cfg(AlreadyACFG) -> + AlreadyACFG. -check_and_rewrite(Defun, Coloring) -> - ?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite(Defun, Coloring, 'normal'). +check_and_rewrite(CFG, Coloring) -> + ?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite(CFG, Coloring, 'normal'). reverse_postorder(CFG) -> hipe_x86_cfg:reverse_postorder(CFG). diff --git a/lib/hipe/regalloc/hipe_x86_specific_x87.erl b/lib/hipe/regalloc/hipe_x86_specific_x87.erl index ece07cb2f9..0c022d5a27 100644 --- a/lib/hipe/regalloc/hipe_x86_specific_x87.erl +++ b/lib/hipe/regalloc/hipe_x86_specific_x87.erl @@ -32,7 +32,7 @@ -endif. -module(?HIPE_X86_SPECIFIC_X87). --export([allocatable/0, +-export([allocatable/1, is_precoloured/1, %% var_range/1, %% def_use/1, @@ -58,7 +58,14 @@ physical_name/1, breadthorder/1, postorder/1, - reverse_postorder/1]). + reverse_postorder/1]). + +%% callbacks for hipe_x86_ra_ls +-export([check_and_rewrite/3]). + +%% Rewrite happens in hipe_x86_ra_finalise:finalise/4 +check_and_rewrite(CFG, _Coloring, 'linearscan') -> + {CFG, false}. breadthorder(CFG) -> hipe_x86_cfg:breadthorder(CFG). @@ -103,7 +110,7 @@ liveout(BB_in_out_liveness,Label) -> %% Registers stuff -allocatable() -> +allocatable('linearscan') -> ?HIPE_X86_REGISTERS:allocatable_x87(). is_precoloured(Reg) -> diff --git a/lib/hipe/rtl/hipe_rtl_binary.erl b/lib/hipe/rtl/hipe_rtl_binary.erl index fb9c0c196d..ad23df80d2 100644 --- a/lib/hipe/rtl/hipe_rtl_binary.erl +++ b/lib/hipe/rtl/hipe_rtl_binary.erl @@ -106,10 +106,20 @@ create_lbls(0) -> %%------------------------------------------------------------------------------ get_word_integer(Var, Register, SystemLimitLblName, FalseLblName) -> - [EndLbl] = create_lbls(1), - EndName = hipe_rtl:label_name(EndLbl), - get_word_integer(Var, Register,SystemLimitLblName, FalseLblName, EndName, EndName, - [EndLbl]). + case hipe_rtl:is_imm(Var) of + true -> + TaggedVal = hipe_rtl:imm_value(Var), + true = hipe_tagscheme:is_fixnum(TaggedVal), + Val = hipe_tagscheme:fixnum_val(TaggedVal), + if Val < 0 -> [hipe_rtl:mk_goto(FalseLblName)]; + true -> [hipe_rtl:mk_move(Register, hipe_rtl:mk_imm(Val))] + end; + false -> + [EndLbl] = create_lbls(1), + EndName = hipe_rtl:label_name(EndLbl), + get_word_integer(Var, Register,SystemLimitLblName, FalseLblName, + EndName, EndName, [EndLbl]) + end. get_word_integer(Var, Register, SystemLimitLblName, FalseLblName, TrueLblName, BigLblName, Tail) -> diff --git a/lib/hipe/sparc/hipe_rtl_to_sparc.erl b/lib/hipe/sparc/hipe_rtl_to_sparc.erl index f9c043eafe..e170fec3d6 100644 --- a/lib/hipe/sparc/hipe_rtl_to_sparc.erl +++ b/lib/hipe/sparc/hipe_rtl_to_sparc.erl @@ -625,7 +625,7 @@ conv_return(I, Map, Data) -> {I2, Map0, Data}. conv_store(I, Map, Data) -> - {Base1, Map0} = conv_dst(hipe_rtl:store_base(I), Map), % no immediates allowed + {Base1, Map0} = conv_src(hipe_rtl:store_base(I), Map), {Src, Map1} = conv_src(hipe_rtl:store_src(I), Map0), {Base2, Map2} = conv_src(hipe_rtl:store_offset(I), Map1), StOp = conv_stop(hipe_rtl:store_size(I)), @@ -649,13 +649,27 @@ mk_store(StOp, Src, Base1, Base2) -> end. mk_store2(StOp, Src, Base1, Base2) -> - case hipe_sparc:is_temp(Base2) of + case hipe_sparc:is_temp(Base1) of true -> - mk_store_rr(StOp, Src, Base1, Base2); + case hipe_sparc:is_temp(Base2) of + true -> + mk_store_rr(StOp, Src, Base1, Base2); + _ -> + mk_store_ri(StOp, Src, Base1, Base2) + end; _ -> - mk_store_ri(StOp, Src, Base1, Base2) + case hipe_sparc:is_temp(Base2) of + true -> + mk_store_ri(StOp, Src, Base2, Base1); + _ -> + mk_store_ii(StOp, Src, Base1, Base2) + end end. +mk_store_ii(StOp, Src, Base, Disp) -> + Tmp = new_untagged_temp(), + mk_set(Base, Tmp, mk_store_ri(StOp, Src, Tmp, Disp)). + mk_store_ri(StOp, Src, Base, Disp) -> hipe_sparc:mk_store(StOp, Src, Base, Disp, 'new', []). diff --git a/lib/hipe/sparc/hipe_sparc_cfg.erl b/lib/hipe/sparc/hipe_sparc_cfg.erl index 0b2c77f27b..957c8a0d24 100644 --- a/lib/hipe/sparc/hipe_sparc_cfg.erl +++ b/lib/hipe/sparc/hipe_sparc_cfg.erl @@ -24,6 +24,7 @@ -export([init/1, labels/1, start_label/1, succ/2, + map_bbs/2, fold_bbs/3, bb/2, bb_add/3]). -export([postorder/1, reverse_postorder/1]). -export([linearise/1]). diff --git a/lib/hipe/sparc/hipe_sparc_frame.erl b/lib/hipe/sparc/hipe_sparc_frame.erl index a42c1983f4..37f29e660a 100644 --- a/lib/hipe/sparc/hipe_sparc_frame.erl +++ b/lib/hipe/sparc/hipe_sparc_frame.erl @@ -25,16 +25,14 @@ -include("hipe_sparc.hrl"). -include("../rtl/hipe_literals.hrl"). -frame(Defun) -> - Formals = fix_formals(hipe_sparc:defun_formals(Defun)), - Temps0 = all_temps(hipe_sparc:defun_code(Defun), Formals), - MinFrame = defun_minframe(Defun), +frame(CFG) -> + Formals = fix_formals(hipe_sparc_cfg:params(CFG)), + Temps0 = all_temps(CFG, Formals), + MinFrame = defun_minframe(CFG), Temps = ensure_minframe(MinFrame, Temps0), - ClobbersRA = clobbers_ra(hipe_sparc:defun_code(Defun)), - CFG0 = hipe_sparc_cfg:init(Defun), - Liveness = hipe_sparc_liveness_all:analyse(CFG0), - CFG1 = do_body(CFG0, Liveness, Formals, Temps, ClobbersRA), - hipe_sparc_cfg:linearise(CFG1). + ClobbersRA = clobbers_ra(CFG), + Liveness = hipe_sparc_liveness_all:analyse(CFG), + do_body(CFG, Liveness, Formals, Temps, ClobbersRA). fix_formals(Formals) -> fix_formals(hipe_sparc_registers:nr_args(), Formals). @@ -550,29 +548,41 @@ temp_is_pseudo(Temp) -> %%% Detect if a Defun's body clobbers RA. %%% -clobbers_ra(Insns) -> - case Insns of - [#pseudo_call{}|_] -> true; - %% moves to RA cannot occur yet - [_|Rest] -> clobbers_ra(Rest); - [] -> false +clobbers_ra(CFG) -> + any_insn(fun(#pseudo_call{}) -> true; + (_) -> false + end, CFG). + +any_insn(Pred, CFG) -> + %% Abuse fold to do an efficient "any"-operation using nonlocal control flow + FoundSatisfying = make_ref(), + try fold_insns(fun (I, _) -> + case Pred(I) of + true -> throw(FoundSatisfying); + false -> false + end + end, false, CFG) + of _ -> false + catch FoundSatisfying -> true end. %%% %%% Build the set of all temps used in a Defun's body. %%% -all_temps(Code, Formals) -> - S0 = find_temps(Code, tset_empty()), +all_temps(CFG, Formals) -> + S0 = fold_insns(fun find_temps/2, tset_empty(), CFG), S1 = tset_del_list(S0, Formals), tset_filter(S1, fun(T) -> temp_is_pseudo(T) end). -find_temps([I|Insns], S0) -> +find_temps(I, S0) -> S1 = tset_add_list(S0, hipe_sparc_defuse:insn_def_all(I)), - S2 = tset_add_list(S1, hipe_sparc_defuse:insn_use_all(I)), - find_temps(Insns, S2); -find_temps([], S) -> - S. + tset_add_list(S1, hipe_sparc_defuse:insn_use_all(I)). + +fold_insns(Fun, InitAcc, CFG) -> + hipe_sparc_cfg:fold_bbs( + fun(_, BB, Acc0) -> lists:foldl(Fun, Acc0, hipe_bb:code(BB)) end, + InitAcc, CFG). tset_empty() -> gb_sets:new(). @@ -601,16 +611,11 @@ tset_to_list(S) -> %%% in the middle of a tailcall. %%% -defun_minframe(Defun) -> - MaxTailArity = body_mta(hipe_sparc:defun_code(Defun), 0), - MyArity = length(fix_formals(hipe_sparc:defun_formals(Defun))), +defun_minframe(CFG) -> + MaxTailArity = fold_insns(fun insn_mta/2, 0, CFG), + MyArity = length(fix_formals(hipe_sparc_cfg:params(CFG))), erlang:max(MaxTailArity - MyArity, 0). -body_mta([I|Code], MTA) -> - body_mta(Code, insn_mta(I, MTA)); -body_mta([], MTA) -> - MTA. - insn_mta(I, MTA) -> case I of #pseudo_tailcall{arity=Arity} -> diff --git a/lib/hipe/sparc/hipe_sparc_main.erl b/lib/hipe/sparc/hipe_sparc_main.erl index c16751c7bd..8e9c560bb2 100644 --- a/lib/hipe/sparc/hipe_sparc_main.erl +++ b/lib/hipe/sparc/hipe_sparc_main.erl @@ -24,12 +24,14 @@ rtl_to_sparc(MFA, RTL, Options) -> Defun1 = hipe_rtl_to_sparc:translate(RTL), + CFG1 = hipe_sparc_cfg:init(Defun1), %% io:format("~w: after translate\n", [?MODULE]), %% hipe_sparc_pp:pp(Defun1), - Defun2 = hipe_sparc_ra:ra(Defun1, Options), + CFG2 = hipe_sparc_ra:ra(CFG1, Options), %% io:format("~w: after regalloc\n", [?MODULE]), - %% hipe_sparc_pp:pp(Defun2), - Defun3 = hipe_sparc_frame:frame(Defun2), + %% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG2)), + CFG3 = hipe_sparc_frame:frame(CFG2), + Defun3 = hipe_sparc_cfg:linearise(CFG3), %% io:format("~w: after frame\n", [?MODULE]), %% hipe_sparc_pp:pp(Defun3), Defun4 = hipe_sparc_finalise:finalise(Defun3), diff --git a/lib/hipe/sparc/hipe_sparc_ra.erl b/lib/hipe/sparc/hipe_sparc_ra.erl index afea8c9b4c..5f955c2058 100644 --- a/lib/hipe/sparc/hipe_sparc_ra.erl +++ b/lib/hipe/sparc/hipe_sparc_ra.erl @@ -22,36 +22,36 @@ -module(hipe_sparc_ra). -export([ra/2]). -ra(Defun0, Options) -> - %% hipe_sparc_pp:pp(Defun0), - {Defun1, Coloring_fp, SpillIndex} +ra(CFG0, Options) -> + %% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG0)), + {CFG1, Coloring_fp, SpillIndex} = case proplists:get_bool(inline_fp, Options) of true -> - hipe_regalloc_loop:ra_fp(Defun0, Options, + hipe_regalloc_loop:ra_fp(CFG0, Options, hipe_coalescing_regalloc, hipe_sparc_specific_fp); false -> - {Defun0,[],0} + {CFG0,[],0} end, - %% hipe_sparc_pp:pp(Defun1), - {Defun2, Coloring} + %% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG1)), + {CFG2, Coloring} = case proplists:get_value(regalloc, Options, coalescing) of coalescing -> - ra(Defun1, SpillIndex, Options, hipe_coalescing_regalloc); + ra(CFG1, SpillIndex, Options, hipe_coalescing_regalloc); optimistic -> - ra(Defun1, SpillIndex, Options, hipe_optimistic_regalloc); + ra(CFG1, SpillIndex, Options, hipe_optimistic_regalloc); graph_color -> - ra(Defun1, SpillIndex, Options, hipe_graph_coloring_regalloc); + ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc); linear_scan -> - hipe_sparc_ra_ls:ra(Defun1, SpillIndex, Options); + hipe_sparc_ra_ls:ra(CFG1, SpillIndex, Options); naive -> - hipe_sparc_ra_naive:ra(Defun1, Coloring_fp, Options); + hipe_sparc_ra_naive:ra(CFG1, Coloring_fp, Options); _ -> exit({unknown_regalloc_compiler_option, proplists:get_value(regalloc,Options)}) end, - %% hipe_sparc_pp:pp(Defun2), - hipe_sparc_ra_finalise:finalise(Defun2, Coloring, Coloring_fp). + %% hipe_sparc_pp:pp(hipe_sparc_cfg:linearise(CFG2)), + hipe_sparc_ra_finalise:finalise(CFG2, Coloring, Coloring_fp). -ra(Defun, SpillIndex, Options, RegAllocMod) -> - hipe_regalloc_loop:ra(Defun, SpillIndex, Options, RegAllocMod, hipe_sparc_specific). +ra(CFG, SpillIndex, Options, RegAllocMod) -> + hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, hipe_sparc_specific). diff --git a/lib/hipe/sparc/hipe_sparc_ra_finalise.erl b/lib/hipe/sparc/hipe_sparc_ra_finalise.erl index dc1e69c101..5d6056071c 100644 --- a/lib/hipe/sparc/hipe_sparc_ra_finalise.erl +++ b/lib/hipe/sparc/hipe_sparc_ra_finalise.erl @@ -23,13 +23,14 @@ -export([finalise/3]). -include("hipe_sparc.hrl"). -finalise(Defun, TempMap, FPMap0) -> - Code = hipe_sparc:defun_code(Defun), - {_, SpillLimit} = hipe_sparc:defun_var_range(Defun), +finalise(CFG, TempMap, FPMap0) -> + {_, SpillLimit} = hipe_gensym:var_range(sparc), Map = mk_ra_map(TempMap, SpillLimit), FPMap1 = mk_ra_map_fp(FPMap0, SpillLimit), - NewCode = ra_code(Code, Map, FPMap1, []), - Defun#defun{code=NewCode}. + hipe_sparc_cfg:map_bbs(fun(_Lbl, BB) -> ra_bb(BB, Map, FPMap1) end, CFG). + +ra_bb(BB, Map, FpMap) -> + hipe_bb:code_update(BB, ra_code(hipe_bb:code(BB), Map, FpMap, [])). ra_code([I|Insns], Map, FPMap, Accum) -> ra_code(Insns, Map, FPMap, [ra_insn(I, Map, FPMap) | Accum]); diff --git a/lib/hipe/sparc/hipe_sparc_ra_ls.erl b/lib/hipe/sparc/hipe_sparc_ra_ls.erl index 19e7c92d2f..ced9addd31 100644 --- a/lib/hipe/sparc/hipe_sparc_ra_ls.erl +++ b/lib/hipe/sparc/hipe_sparc_ra_ls.erl @@ -23,15 +23,12 @@ -module(hipe_sparc_ra_ls). -export([ra/3]). -ra(Defun, SpillIndex, Options) -> - NewDefun = Defun, %% hipe_${ARCH}_ra_rename:rename(Defun,Options), - CFG = hipe_sparc_cfg:init(NewDefun), +ra(CFG, SpillIndex, Options) -> SpillLimit = hipe_sparc_specific:number_of_temporaries(CFG), - alloc(NewDefun, SpillIndex, SpillLimit, Options). + alloc(CFG, SpillIndex, SpillLimit, Options). -alloc(Defun, SpillIndex, SpillLimit, Options) -> - CFG = hipe_sparc_cfg:init(Defun), - {Coloring, _NewSpillIndex} = +alloc(CFG, SpillIndex, SpillLimit, Options) -> + {Coloring, _NewSpillIndex, Liveness} = regalloc( CFG, hipe_sparc_registers:allocatable_gpr()-- @@ -41,16 +38,16 @@ alloc(Defun, SpillIndex, SpillLimit, Options) -> [hipe_sparc_cfg:start_label(CFG)], SpillIndex, SpillLimit, Options, hipe_sparc_specific), - {NewDefun, _DidSpill} = + {NewCFG, _DidSpill} = hipe_sparc_ra_postconditions:check_and_rewrite( - Defun, Coloring, 'linearscan'), + CFG, Coloring, 'linearscan'), TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific), {TempMap2,_NewSpillIndex2} = - hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options, + hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options, hipe_sparc_specific, TempMap), Coloring2 = hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2), - {NewDefun, Coloring2}. + {NewCFG, Coloring2}. regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) -> hipe_ls_regalloc:regalloc( diff --git a/lib/hipe/sparc/hipe_sparc_ra_naive.erl b/lib/hipe/sparc/hipe_sparc_ra_naive.erl index b6c33dec6c..f621d94553 100644 --- a/lib/hipe/sparc/hipe_sparc_ra_naive.erl +++ b/lib/hipe/sparc/hipe_sparc_ra_naive.erl @@ -24,7 +24,7 @@ -include("hipe_sparc.hrl"). -ra(Defun, _Coloring_fp, _Options) -> % -> {Defun, Coloring} - {NewDefun,_DidSpill} = - hipe_sparc_ra_postconditions:check_and_rewrite2(Defun, [], 'naive'), - {NewDefun, []}. +ra(CFG, _Coloring_fp, _Options) -> % -> {CFG, Coloring} + {NewCFG,_DidSpill} = + hipe_sparc_ra_postconditions:check_and_rewrite2(CFG, [], 'naive'), + {NewCFG, []}. diff --git a/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl b/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl index ab31b3c8d9..0336a6c59f 100644 --- a/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl +++ b/lib/hipe/sparc/hipe_sparc_ra_postconditions.erl @@ -25,17 +25,13 @@ -include("hipe_sparc.hrl"). -check_and_rewrite(Defun, Coloring, Allocator) -> +check_and_rewrite(CFG, Coloring, Allocator) -> TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific), - check_and_rewrite2(Defun, TempMap, Allocator). + check_and_rewrite2(CFG, TempMap, Allocator). -check_and_rewrite2(Defun, TempMap, Allocator) -> +check_and_rewrite2(CFG, TempMap, Allocator) -> Strategy = strategy(Allocator), - #defun{code=Code0} = Defun, - {Code1,DidSpill} = do_insns(Code0, TempMap, Strategy, [], false), - VarRange = {0, hipe_gensym:get_var(sparc)}, - {Defun#defun{code=Code1, var_range=VarRange}, - DidSpill}. + do_bbs(hipe_sparc_cfg:labels(CFG), TempMap, Strategy, CFG, false). strategy(Allocator) -> case Allocator of @@ -44,6 +40,13 @@ strategy(Allocator) -> 'naive' -> 'fixed' end. +do_bbs([], _, _, CFG, DidSpill) -> {CFG, DidSpill}; +do_bbs([Lbl|Lbls], TempMap, Strategy, CFG0, DidSpill0) -> + Code0 = hipe_bb:code(BB = hipe_sparc_cfg:bb(CFG0, Lbl)), + {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0), + CFG = hipe_sparc_cfg:bb_add(CFG0, Lbl, hipe_bb:code_update(BB, Code)), + do_bbs(Lbls, TempMap, Strategy, CFG, DidSpill). + do_insns([I|Insns], TempMap, Strategy, Accum, DidSpill0) -> {NewIs, DidSpill1} = do_insn(I, TempMap, Strategy), do_insns(Insns, TempMap, Strategy, lists:reverse(NewIs, Accum), DidSpill0 or DidSpill1); diff --git a/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl b/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl index d893ac26e9..d3e1d8cf93 100644 --- a/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl +++ b/lib/hipe/sparc/hipe_sparc_ra_postconditions_fp.erl @@ -25,13 +25,16 @@ -include("hipe_sparc.hrl"). -check_and_rewrite(Defun, Coloring) -> +check_and_rewrite(CFG, Coloring) -> TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_sparc_specific_fp), - #defun{code=Code0} = Defun, - {Code1,DidSpill} = do_insns(Code0, TempMap, [], false), - VarRange = {0, hipe_gensym:get_var(sparc)}, - {Defun#defun{code=Code1, var_range=VarRange}, - DidSpill}. + do_bbs(hipe_sparc_cfg:labels(CFG), TempMap, CFG, false). + +do_bbs([], _TempMap, CFG, DidSpill) -> {CFG, DidSpill}; +do_bbs([Lbl|Lbls], TempMap, CFG0, DidSpill0) -> + Code0 = hipe_bb:code(BB = hipe_sparc_cfg:bb(CFG0, Lbl)), + {Code, DidSpill} = do_insns(Code0, TempMap, [], DidSpill0), + CFG = hipe_sparc_cfg:bb_add(CFG0, Lbl, hipe_bb:code_update(BB, Code)), + do_bbs(Lbls, TempMap, CFG, DidSpill). do_insns([I|Insns], TempMap, Accum, DidSpill0) -> {NewIs, DidSpill1} = do_insn(I, TempMap), diff --git a/lib/hipe/test/hipe_testsuite_driver.erl b/lib/hipe/test/hipe_testsuite_driver.erl index a3048d907e..88576775ca 100644 --- a/lib/hipe/test/hipe_testsuite_driver.erl +++ b/lib/hipe/test/hipe_testsuite_driver.erl @@ -99,7 +99,7 @@ write_suite(Suite) -> write_header(#suite{suitename = SuiteName, outputfile = OutputFile, testcases = TestCases}) -> Exports = format_export(TestCases), - TimeLimit = 5, %% with 1 or 2 it fails on some slow machines... + TimeLimit = 6, %% with 1, 2, or 3 it fails on some slow machines... io:format(OutputFile, "%% ATTENTION!\n" "%% This is an automatically generated file. Do not edit.\n\n" @@ -168,6 +168,10 @@ run(TestCase, Dir, _OutDir) -> HiPEOpts = try TestCase:hipe_options() catch error:undef -> [] end, {ok, TestCase} = hipe:c(TestCase, HiPEOpts), ok = TestCase:test(), + {ok, TestCase} = hipe:c(TestCase, [o1|HiPEOpts]), + ok = TestCase:test(), + {ok, TestCase} = hipe:c(TestCase, [o0|HiPEOpts]), + ok = TestCase:test(), ToLLVM = try TestCase:to_llvm() catch error:undef -> true end, case ToLLVM andalso hipe:llvm_support_available() of true -> diff --git a/lib/hipe/x86/Makefile b/lib/hipe/x86/Makefile index 93f8b955dd..9b21270426 100644 --- a/lib/hipe/x86/Makefile +++ b/lib/hipe/x86/Makefile @@ -60,7 +60,6 @@ MODULES=hipe_rtl_to_x86 \ hipe_x86_ra_ls \ hipe_x86_ra_naive \ hipe_x86_ra_postconditions \ - hipe_x86_ra_x87_ls \ hipe_x86_registers \ hipe_x86_spill_restore \ hipe_x86_x87 @@ -133,7 +132,6 @@ $(EBIN)/hipe_x86_ra: ../main/hipe.hrl $(EBIN)/hipe_x86_ra_dummy.beam: ../main/hipe.hrl $(EBIN)/hipe_x86_ra_ls.beam: ../main/hipe.hrl $(EBIN)/hipe_x86_ra_postconditions.beam: ../main/hipe.hrl -$(EBIN)/hipe_x86_ra_x87_ls.beam: ../main/hipe.hrl $(EBIN)/hipe_x86_registers.beam: ../rtl/hipe_literals.hrl $(EBIN)/hipe_x86_spill_restore.beam: ../main/hipe.hrl ../flow/cfg.hrl $(EBIN)/hipe_x86_x87.beam: ../main/hipe.hrl diff --git a/lib/hipe/x86/hipe_rtl_to_x86.erl b/lib/hipe/x86/hipe_rtl_to_x86.erl index d13f63b1d9..4c8c98551c 100644 --- a/lib/hipe/x86/hipe_rtl_to_x86.erl +++ b/lib/hipe/x86/hipe_rtl_to_x86.erl @@ -85,7 +85,7 @@ conv_insn(I, Map, Data) -> true -> conv_shift(Dst, Src1, BinOp, Src2); false -> - conv_alu(Dst, Src1, BinOp, Src2, []) + conv_alu_nocc(Dst, Src1, BinOp, Src2, []) end, {FixSrc1++FixSrc2++I2, Map2, Data}; #alub{} -> @@ -144,7 +144,7 @@ conv_insn(I, Map, Data) -> {I2, Map, Data}; #load{} -> {Dst, Map0} = conv_dst(hipe_rtl:load_dst(I), Map), - {FixSrc, Src, Map1} = conv_src(hipe_rtl:load_src(I), Map0), + {FixSrc, Src, Map1} = conv_src_noimm(hipe_rtl:load_src(I), Map0), {FixOff, Off, Map2} = conv_src(hipe_rtl:load_offset(I), Map1), I2 = case {hipe_rtl:load_size(I), hipe_rtl:load_sign(I)} of {byte, signed} -> @@ -171,6 +171,7 @@ conv_insn(I, Map, Data) -> Src = hipe_x86:mk_imm_from_atom(hipe_rtl:load_atom_atom(I)), I2 = [hipe_x86:mk_move(Src, Dst)], {I2, Map0, Data}; + #move{src=Dst, dst=Dst} -> {[], Map, Data}; #move{} -> {Dst, Map0} = conv_dst(hipe_rtl:move_dst(I), Map), {FixSrc, Src, Map1} = conv_src(hipe_rtl:move_src(I), Map0), @@ -182,11 +183,11 @@ conv_insn(I, Map, Data) -> I2 = move_retvals(Args, [hipe_x86:mk_ret(-1)]), {FixArgs++I2, Map0, Data}; #store{} -> - {Ptr, Map0} = conv_dst(hipe_rtl:store_base(I), Map), + {FixPtr, Ptr, Map0} = conv_src_noimm(hipe_rtl:store_base(I), Map), {FixSrc, Src, Map1} = conv_src(hipe_rtl:store_src(I), Map0), {FixOff, Off, Map2} = conv_src(hipe_rtl:store_offset(I), Map1), I2 = mk_store(hipe_rtl:store_size(I), Src, Ptr, Off), - {FixSrc++FixOff++I2, Map2, Data}; + {FixPtr++FixSrc++FixOff++I2, Map2, Data}; #switch{} -> % this one also updates Data :-( %% from hipe_rtl2sparc, but we use a hairy addressing mode %% instead of doing the arithmetic manually @@ -206,7 +207,7 @@ conv_insn(I, Map, Data) -> {I2, Map1, NewData}; #fload{} -> {Dst, Map0} = conv_dst(hipe_rtl:fload_dst(I), Map), - {[], Src, Map1} = conv_src(hipe_rtl:fload_src(I), Map0), + {[], Src, Map1} = conv_src_noimm(hipe_rtl:fload_src(I), Map0), {[], Off, Map2} = conv_src(hipe_rtl:fload_offset(I), Map1), I2 = [hipe_x86:mk_fmove(hipe_x86:mk_mem(Src, Off, 'double'),Dst)], {I2, Map2, Data}; @@ -249,6 +250,22 @@ conv_insn(I, Map, Data) -> %%% Finalise the conversion of a 3-address ALU operation, taking %%% care to not introduce more temps and moves than necessary. +conv_alu_nocc(Dst, Src1, 'add', Src2, Tail) -> + case (not same_opnd(Dst, Src1)) andalso (not same_opnd(Dst, Src2)) + andalso (hipe_x86:is_temp(Src1) orelse hipe_x86:is_temp(Src2)) + of + false -> conv_alu(Dst, Src1, 'add', Src2, Tail); + true -> % Use LEA + Type = typeof_dst(Dst), + Mem = case hipe_x86:is_temp(Src1) of + true -> hipe_x86:mk_mem(Src1, Src2, Type); + false -> hipe_x86:mk_mem(Src2, Src1, Type) + end, + [hipe_x86:mk_lea(Mem, Dst) | Tail] + end; +conv_alu_nocc(Dst, Src1, BinOp, Src2, Tail) -> + conv_alu(Dst, Src1, BinOp, Src2, Tail). + conv_alu(Dst, Src1, 'imul', Src2, Tail) -> mk_imul(Src1, Src2, Dst, Tail); conv_alu(Dst, Src1, BinOp, Src2, Tail) -> @@ -572,6 +589,16 @@ conv_fun(Fun, Map) -> end end. +conv_src_noimm(Opnd, Map) -> + R={FixSrc0, Src, NewMap} = conv_src(Opnd, Map), + case hipe_x86:is_imm(Src) of + false -> R; + true -> + Tmp = new_untagged_temp(), + {FixSrc0 ++ [hipe_x86:mk_move(Src, Tmp)], + Tmp, NewMap} + end. + %%% Convert an RTL source operand (imm/var/reg). conv_src(Opnd, Map) -> diff --git a/lib/hipe/x86/hipe_x86_cfg.erl b/lib/hipe/x86/hipe_x86_cfg.erl index ab40b68580..b9f9c711f3 100644 --- a/lib/hipe/x86/hipe_x86_cfg.erl +++ b/lib/hipe/x86/hipe_x86_cfg.erl @@ -24,7 +24,7 @@ -export([init/1, labels/1, start_label/1, succ/2, pred/2, - bb/2, bb_add/3]). + bb/2, bb_add/3, map_bbs/2, fold_bbs/3]). -export([postorder/1, reverse_postorder/1]). -export([linearise/1, params/1, arity/1, redirect_jmp/3]). @@ -33,6 +33,7 @@ -define(BREADTH_ORDER,true). -define(PARAMS_NEEDED,true). -define(START_LABEL_UPDATE_NEEDED,true). +-define(MAP_FOLD_NEEDED,true). -include("hipe_x86.hrl"). -include("../flow/cfg.hrl"). @@ -107,7 +108,7 @@ mk_goto(Label) -> hipe_x86:mk_jmp_label(Label). is_label(I) -> - hipe_x86:is_label(I). + case I of #label{} -> true; _ -> false end. label_name(Label) -> hipe_x86:label_label(Label). diff --git a/lib/hipe/x86/hipe_x86_frame.erl b/lib/hipe/x86/hipe_x86_frame.erl index 4cdc04007d..fc782571bf 100644 --- a/lib/hipe/x86/hipe_x86_frame.erl +++ b/lib/hipe/x86/hipe_x86_frame.erl @@ -46,15 +46,13 @@ -include("../x86/hipe_x86.hrl"). -include("../rtl/hipe_literals.hrl"). -frame(Defun, _Options) -> - Formals = fix_formals(hipe_x86:defun_formals(Defun)), - Temps0 = all_temps(hipe_x86:defun_code(Defun), Formals), - MinFrame = defun_minframe(Defun), +frame(CFG0, _Options) -> + Formals = fix_formals(hipe_x86_cfg:params(CFG0)), + Temps0 = all_temps(CFG0, Formals), + MinFrame = defun_minframe(CFG0), Temps = ensure_minframe(MinFrame, Temps0), - CFG0 = hipe_x86_cfg:init(Defun), Liveness = ?HIPE_X86_LIVENESS:analyse(CFG0), - CFG1 = do_body(CFG0, Liveness, Formals, Temps), - hipe_x86_cfg:linearise(CFG1). + do_body(CFG0, Liveness, Formals, Temps). fix_formals(Formals) -> fix_formals(?HIPE_X86_REGISTERS:nr_args(), Formals). @@ -69,23 +67,14 @@ do_body(CFG0, Liveness, Formals, Temps) -> do_prologue(CFG1, Context). do_blocks(CFG, Context) -> - Labels = hipe_x86_cfg:labels(CFG), - do_blocks(Labels, CFG, Context). + hipe_x86_cfg:map_bbs(fun(Lbl, BB) -> do_block(Lbl, BB, Context) end, CFG). -do_blocks([Label|Labels], CFG, Context) -> +do_block(Label, Block, Context) -> Liveness = context_liveness(Context), LiveOut = ?HIPE_X86_LIVENESS:liveout(Liveness, Label), - Block = hipe_x86_cfg:bb(CFG, Label), Code = hipe_bb:code(Block), - NewCode = do_block(Code, LiveOut, Context), - NewBlock = hipe_bb:code_update(Block, NewCode), - NewCFG = hipe_x86_cfg:bb_add(CFG, Label, NewBlock), - do_blocks(Labels, NewCFG, Context); -do_blocks([], CFG, _) -> - CFG. - -do_block(Insns, LiveOut, Context) -> - do_block(Insns, LiveOut, Context, context_framesize(Context), []). + NewCode = do_block(Code, LiveOut, Context, context_framesize(Context), []), + hipe_bb:code_update(Block, NewCode). do_block([I|Insns], LiveOut, Context, FPoff0, RevCode) -> {NewIs, FPoff1} = do_insn(I, LiveOut, Context, FPoff0), @@ -609,18 +598,20 @@ temp_is_pseudo(Temp) -> %%% Build the set of all temps used in a Defun's body. %%% -all_temps(Code, Formals) -> - S0 = find_temps(Code, tset_empty()), +all_temps(CFG, Formals) -> + S0 = fold_insns(fun find_temps/2, tset_empty(), CFG), S1 = tset_del_list(S0, Formals), S2 = tset_filter(S1, fun(T) -> temp_is_pseudo(T) end), S2. -find_temps([I|Insns], S0) -> +find_temps(I, S0) -> S1 = tset_add_list(S0, hipe_x86_defuse:insn_def(I)), - S2 = tset_add_list(S1, hipe_x86_defuse:insn_use(I)), - find_temps(Insns, S2); -find_temps([], S) -> - S. + tset_add_list(S1, hipe_x86_defuse:insn_use(I)). + +fold_insns(Fun, InitAcc, CFG) -> + hipe_x86_cfg:fold_bbs( + fun(_, BB, Acc0) -> lists:foldl(Fun, Acc0, hipe_bb:code(BB)) end, + InitAcc, CFG). -compile({inline, [tset_empty/0, tset_size/1, tset_insert/2, tset_filter/2, tset_to_list/1]}). @@ -654,16 +645,11 @@ tset_to_list(S) -> %%% in the middle of a tailcall. %%% -defun_minframe(Defun) -> - MaxTailArity = body_mta(hipe_x86:defun_code(Defun), 0), - MyArity = length(fix_formals(hipe_x86:defun_formals(Defun))), +defun_minframe(CFG) -> + MaxTailArity = fold_insns(fun insn_mta/2, 0, CFG), + MyArity = length(fix_formals(hipe_x86_cfg:params(CFG))), erlang:max(MaxTailArity - MyArity, 0). -body_mta([I|Code], MTA) -> - body_mta(Code, insn_mta(I, MTA)); -body_mta([], MTA) -> - MTA. - insn_mta(I, MTA) -> case I of #pseudo_tailcall{arity=Arity} -> diff --git a/lib/hipe/x86/hipe_x86_main.erl b/lib/hipe/x86/hipe_x86_main.erl index 13b0bb6b28..341269b698 100644 --- a/lib/hipe/x86/hipe_x86_main.erl +++ b/lib/hipe/x86/hipe_x86_main.erl @@ -53,19 +53,23 @@ ?RTL_TO_X86(MFA, RTL, Options) -> Translated = ?option_time(?HIPE_RTL_TO_X86:translate(RTL), "RTL-to-"?X86STR, Options), - SpillRest = + TransCFG = ?option_time(hipe_x86_cfg:init(Translated), + ?X86STR" to cfg", Options), + SpillRestCFG = case proplists:get_bool(caller_save_spill_restore, Options) of true -> - ?option_time(?HIPE_X86_SPILL_RESTORE:spill_restore(Translated, Options), + ?option_time(?HIPE_X86_SPILL_RESTORE:spill_restore(TransCFG, Options), ?X86STR" spill restore", Options); false -> - Translated + TransCFG end, - Allocated = ?option_time(?HIPE_X86_RA:ra(SpillRest, Options), - ?X86STR" register allocation", Options), - Framed = ?option_time(?HIPE_X86_FRAME:frame(Allocated, Options), - ?X86STR" frame", Options), - Finalised = ?option_time(hipe_x86_postpass:postpass(Framed, Options), - ?X86STR" finalise", Options), + AllocatedCFG = ?option_time(?HIPE_X86_RA:ra(SpillRestCFG, Options), + ?X86STR" register allocation", Options), + FramedCFG = ?option_time(?HIPE_X86_FRAME:frame(AllocatedCFG, Options), + ?X86STR" frame", Options), + Framed = ?option_time(hipe_x86_cfg:linearise(FramedCFG), + ?X86STR" linearise", Options), + Finalised = ?option_time(hipe_x86_postpass:postpass(Framed, Options), + ?X86STR" finalise", Options), ?HIPE_X86_PP:optional_pp(Finalised, MFA, Options), {native, ?X86TAG, {unprofiled, Finalised}}. diff --git a/lib/hipe/x86/hipe_x86_ra.erl b/lib/hipe/x86/hipe_x86_ra.erl index f66961a7a7..3af333ab4b 100644 --- a/lib/hipe/x86/hipe_x86_ra.erl +++ b/lib/hipe/x86/hipe_x86_ra.erl @@ -41,60 +41,80 @@ %%-define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation. -include("../main/hipe.hrl"). -ra(Defun0, Options) -> - %% ?HIPE_X86_PP:pp(Defun0), - {Defun1, Coloring_fp, SpillIndex} = ra_fp(Defun0, Options), - %% ?HIPE_X86_PP:pp(Defun1), +-ifdef(HIPE_INSTRUMENT_COMPILER). +code_size(CFG) -> + hipe_x86_cfg:fold_bbs(fun(_, BB, Acc) -> Acc + length(hipe_bb:code(BB)) end, + 0, CFG). +-endif. %% ifdef(HIPE_INSTRUMENT_COMPILER) + +ra(CFG0, Options) -> + %% hipe_x86_cfg:pp(CFG0), + {CFG1, Coloring_fp, SpillIndex, Liveness} = + case ra_fp(CFG0, Options) of + {G, C, I} -> {G, C, I, undefined}; + {_,_,_,_}=T -> T + end, + %% hipe_x86_cfg:pp(CFG1), ?start_ra_instrumentation(Options, - length(hipe_x86:defun_code(Defun1)), - element(2,hipe_x86:defun_var_range(Defun1))), - {Defun2, Coloring} + code_size(CFG1), + element(2,hipe_gensym:var_range(x86))), + {CFG2, Coloring} = case proplists:get_value(regalloc, Options, coalescing) of coalescing -> - ra(Defun1, SpillIndex, Options, hipe_coalescing_regalloc); + ra(CFG1, SpillIndex, Options, hipe_coalescing_regalloc); optimistic -> - ra(Defun1, SpillIndex, Options, hipe_optimistic_regalloc); + ra(CFG1, SpillIndex, Options, hipe_optimistic_regalloc); graph_color -> - ra(Defun1, SpillIndex, Options, hipe_graph_coloring_regalloc); + ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc); linear_scan -> - ?HIPE_X86_RA_LS:ra(Defun1, SpillIndex, Options); + ?HIPE_X86_RA_LS:ra(CFG1, Liveness, SpillIndex, Options); naive -> - ?HIPE_X86_RA_NAIVE:ra(Defun1, Coloring_fp, Options); + ?HIPE_X86_RA_NAIVE:ra(CFG1, Coloring_fp, Options); _ -> exit({unknown_regalloc_compiler_option, proplists:get_value(regalloc,Options)}) end, ?stop_ra_instrumentation(Options, - length(hipe_x86:defun_code(Defun2)), - element(2,hipe_x86:defun_var_range(Defun2))), - %% ?HIPE_X86_PP:pp(Defun2), - ?HIPE_X86_RA_FINALISE:finalise(Defun2, Coloring, Coloring_fp, Options). + code_size(CFG2), + element(2,hipe_gensym:var_range(x86))), + %% hipe_x86_cfg:pp(CFG2), + ?HIPE_X86_RA_FINALISE:finalise(CFG2, Coloring, Coloring_fp, Options). -ra(Defun, SpillIndex, Options, RegAllocMod) -> - hipe_regalloc_loop:ra(Defun, SpillIndex, Options, RegAllocMod, ?HIPE_X86_SPECIFIC). +ra(CFG, SpillIndex, Options, RegAllocMod) -> + hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, ?HIPE_X86_SPECIFIC). -ifdef(HIPE_AMD64). -ra_fp(Defun, Options) -> - case proplists:get_bool(inline_fp, Options) and - (proplists:get_value(regalloc, Options) =/= naive) of - true -> - case proplists:get_bool(x87, Options) of - true -> - hipe_amd64_ra_x87_ls:ra(Defun, Options); - false -> - hipe_regalloc_loop:ra_fp(Defun, Options, - hipe_coalescing_regalloc, - hipe_amd64_specific_sse2) - end; - false -> - {Defun,[],0} +ra_fp(CFG, Options) -> + Regalloc0 = proplists:get_value(regalloc, Options), + {Regalloc, TargetMod} = + case proplists:get_bool(inline_fp, Options) and (Regalloc0 =/= naive) of + false -> {naive, undefined}; + true -> + case proplists:get_bool(x87, Options) of + true -> {linear_scan, hipe_amd64_specific_x87}; + false -> {Regalloc0, hipe_amd64_specific_sse2} + end + end, + case Regalloc of + coalescing -> ra_fp(CFG, Options, hipe_coalescing_regalloc, TargetMod); + optimistic -> ra_fp(CFG, Options, hipe_optimistic_regalloc, TargetMod); + graph_color -> ra_fp(CFG, Options, hipe_graph_coloring_regalloc, + TargetMod); + linear_scan -> hipe_amd64_ra_ls:ra_fp(CFG, Options, TargetMod); + naive -> {CFG,[],0}; + _ -> + exit({unknown_regalloc_compiler_option, + proplists:get_value(regalloc,Options)}) end. + +ra_fp(CFG, Options, RegAllocMod, TargetMod) -> + hipe_regalloc_loop:ra_fp(CFG, Options, RegAllocMod, TargetMod). -else. -ra_fp(Defun, Options) -> +ra_fp(CFG, Options) -> case proplists:get_bool(inline_fp, Options) of true -> - hipe_x86_ra_x87_ls:ra(Defun, Options); + hipe_x86_ra_ls:ra_fp(CFG, Options, hipe_x86_specific_x87); false -> - {Defun,[],0} + {CFG,[],0} end. -endif. diff --git a/lib/hipe/x86/hipe_x86_ra_finalise.erl b/lib/hipe/x86/hipe_x86_ra_finalise.erl index 5dd75cb7ae..62009abb76 100644 --- a/lib/hipe/x86/hipe_x86_ra_finalise.erl +++ b/lib/hipe/x86/hipe_x86_ra_finalise.erl @@ -25,23 +25,36 @@ -define(HIPE_X86_RA_FINALISE, hipe_amd64_ra_finalise). -define(HIPE_X86_REGISTERS, hipe_amd64_registers). -define(HIPE_X86_X87, hipe_amd64_x87). +-define(HIPE_X86_SSE2, hipe_amd64_sse2). +-define(IF_HAS_SSE2(Expr), Expr). -else. -define(HIPE_X86_RA_FINALISE, hipe_x86_ra_finalise). -define(HIPE_X86_REGISTERS, hipe_x86_registers). -define(HIPE_X86_X87, hipe_x86_x87). +-define(IF_HAS_SSE2(Expr),). -endif. -module(?HIPE_X86_RA_FINALISE). -export([finalise/4]). -include("../x86/hipe_x86.hrl"). -finalise(Defun, TempMap, FpMap, Options) -> - Defun1 = finalise_ra(Defun, TempMap, FpMap, Options), +finalise(CFG0, TempMap, FpMap, Options) -> + CFG1 = finalise_ra(CFG0, TempMap, FpMap, Options), case proplists:get_bool(x87, Options) of true -> - ?HIPE_X86_X87:map(Defun1); + ?HIPE_X86_X87:map(CFG1); _ -> - Defun1 + case + proplists:get_bool(inline_fp, Options) + and (proplists:get_value(regalloc, Options) =:= linear_scan) + of + %% Ugly, but required to avoid Dialyzer complaints about "Unknown + %% function" hipe_x86_sse2:map/1 + ?IF_HAS_SSE2(true -> + ?HIPE_X86_SSE2:map(CFG1);) + false -> + CFG1 + end end. %%% @@ -50,15 +63,16 @@ finalise(Defun, TempMap, FpMap, Options) -> %%% but I just want this to work now) %%% -finalise_ra(Defun, [], [], _Options) -> - Defun; -finalise_ra(Defun, TempMap, FpMap, Options) -> - Code = hipe_x86:defun_code(Defun), - {_, SpillLimit} = hipe_x86:defun_var_range(Defun), +finalise_ra(CFG, [], [], _Options) -> + CFG; +finalise_ra(CFG, TempMap, FpMap, Options) -> + {_, SpillLimit} = hipe_gensym:var_range(x86), Map = mk_ra_map(TempMap, SpillLimit), FpMap0 = mk_ra_map_fp(FpMap, SpillLimit, Options), - NewCode = ra_code(Code, Map, FpMap0), - Defun#defun{code=NewCode}. + hipe_x86_cfg:map_bbs(fun(_Lbl, BB) -> ra_bb(BB, Map, FpMap0) end, CFG). + +ra_bb(BB, Map, FpMap) -> + hipe_bb:code_update(BB, ra_code(hipe_bb:code(BB), Map, FpMap)). ra_code(Code, Map, FpMap) -> [ra_insn(I, Map, FpMap) || I <- Code]. diff --git a/lib/hipe/x86/hipe_x86_ra_ls.erl b/lib/hipe/x86/hipe_x86_ra_ls.erl index 3e34433111..9f019f9561 100644 --- a/lib/hipe/x86/hipe_x86_ra_ls.erl +++ b/lib/hipe/x86/hipe_x86_ra_ls.erl @@ -35,40 +35,65 @@ -endif. -module(?HIPE_X86_RA_LS). --export([ra/3,regalloc/7]). +-export([ra/4,ra_fp/3]). -define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation. -include("../main/hipe.hrl"). -ra(Defun, SpillIndex, Options) -> - NewDefun = Defun, %% hipe_${ARCH}_ra_rename:rename(Defun,Options), - CFG = hipe_x86_cfg:init(NewDefun), - +ra(CFG, Liveness, SpillIndex, Options) -> SpillLimit = ?HIPE_X86_SPECIFIC:number_of_temporaries( CFG), ?inc_counter(bbs_counter, length(hipe_x86_cfg:labels(CFG))), - alloc(NewDefun, SpillIndex, SpillLimit, Options). + alloc(CFG, Liveness, SpillIndex, SpillLimit, Options). + +ra_fp(CFG, Options, TargetMod) -> + ?inc_counter(ra_calls_counter,1), + %% ?inc_counter(ra_caller_saves_counter,count_caller_saves(CFG)), + SpillIndex = 0, + SpillLimit = TargetMod:number_of_temporaries(CFG), + ?inc_counter(bbs_counter, length(hipe_x86_cfg:labels(CFG))), + + ?inc_counter(ra_iteration_counter,1), + %% ?HIPE_X86_PP:pp(Defun), + {Coloring,NewSpillIndex,Liveness} = + regalloc(CFG, + undefined, + TargetMod:allocatable('linearscan'), + [hipe_x86_cfg:start_label(CFG)], + SpillIndex, SpillLimit, Options, + TargetMod), + + {NewCFG, _DidSpill} = + TargetMod:check_and_rewrite(CFG, Coloring, 'linearscan'), + TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod), + {TempMap2, NewSpillIndex2} = + hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options, + TargetMod, TempMap), + Coloring2 = + hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2), + ?add_spills(Options, NewSpillIndex), + {NewCFG, Coloring2, NewSpillIndex2, Liveness}. -alloc(Defun, SpillIndex, SpillLimit, Options) -> +alloc(CFG, Liveness0, SpillIndex, SpillLimit, Options) -> ?inc_counter(ra_iteration_counter,1), %% ?HIPE_X86_PP:pp(Defun), - CFG = hipe_x86_cfg:init(Defun), - {Coloring, NewSpillIndex} = + {Coloring, NewSpillIndex, Liveness} = regalloc( - CFG, + CFG, + Liveness0, ?HIPE_X86_REGISTERS:allocatable()-- [?HIPE_X86_REGISTERS:temp1(), ?HIPE_X86_REGISTERS:temp0()], [hipe_x86_cfg:start_label(CFG)], SpillIndex, SpillLimit, Options, ?HIPE_X86_SPECIFIC), - {NewDefun, _DidSpill} = + {NewCFG, _DidSpill} = ?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite( - Defun, Coloring, 'linearscan'), + CFG, Coloring, 'linearscan'), %% ?HIPE_X86_PP:pp(NewDefun), TempMap = hipe_temp_map:cols2tuple(Coloring, ?HIPE_X86_SPECIFIC), - {TempMap2,NewSpillIndex2} = - hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options, + {TempMap2,NewSpillIndex2} = + hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options, ?HIPE_X86_SPECIFIC, TempMap), Coloring2 = hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2), @@ -79,8 +104,9 @@ alloc(Defun, SpillIndex, SpillLimit, Options) -> ok end, ?add_spills(Options, NewSpillIndex), - {NewDefun, Coloring2}. + {NewCFG, Coloring2}. -regalloc(CFG,PhysRegs,Entrypoints, SpillIndex, DontSpill, Options, Target) -> - hipe_ls_regalloc:regalloc(CFG,PhysRegs,Entrypoints, SpillIndex, +regalloc(CFG,Liveness,PhysRegs,Entrypoints, SpillIndex, DontSpill, Options, + Target) -> + hipe_ls_regalloc:regalloc(CFG,Liveness,PhysRegs,Entrypoints, SpillIndex, DontSpill, Options, Target). diff --git a/lib/hipe/x86/hipe_x86_ra_naive.erl b/lib/hipe/x86/hipe_x86_ra_naive.erl index 0ef4ef0a04..27e5af4aee 100644 --- a/lib/hipe/x86/hipe_x86_ra_naive.erl +++ b/lib/hipe/x86/hipe_x86_ra_naive.erl @@ -39,9 +39,8 @@ -define(HIPE_INSTRUMENT_COMPILER, true). % enable instrumentation -include("../main/hipe.hrl"). -ra(X86Defun, Coloring_fp, Options) -> - #defun{code=Code0} = X86Defun, - Code1 = do_insns(Code0), +ra(CFG0, Coloring_fp, Options) -> + CFG = hipe_x86_cfg:map_bbs(fun do_bb/2, CFG0), NofSpilledFloats = count_non_float_spills(Coloring_fp), NofFloats = length(Coloring_fp), ?add_spills(Options, hipe_gensym:get_var(x86) - @@ -49,10 +48,12 @@ ra(X86Defun, Coloring_fp, Options) -> NofSpilledFloats - NofFloats), TempMap = [], - {X86Defun#defun{code=Code1, - var_range={0, hipe_gensym:get_var(x86)}}, + {CFG, TempMap}. +do_bb(_Lbl, BB) -> + hipe_bb:code_update(BB, do_insns(hipe_bb:code(BB))). + count_non_float_spills(Coloring_fp) -> count_non_float_spills(Coloring_fp, 0). diff --git a/lib/hipe/x86/hipe_x86_ra_postconditions.erl b/lib/hipe/x86/hipe_x86_ra_postconditions.erl index 0a70bd1d22..c73d029b9b 100644 --- a/lib/hipe/x86/hipe_x86_ra_postconditions.erl +++ b/lib/hipe/x86/hipe_x86_ra_postconditions.erl @@ -40,14 +40,18 @@ -include("../main/hipe.hrl"). -define(count_temp(T), ?cons_counter(counter_mfa_mem_temps, T)). -check_and_rewrite(Defun, Coloring, Strategy) -> +check_and_rewrite(CFG, Coloring, Strategy) -> %% io:format("Converting\n"), TempMap = hipe_temp_map:cols2tuple(Coloring, ?HIPE_X86_SPECIFIC), %% io:format("Rewriting\n"), - #defun{code=Code0} = Defun, - {Code1, DidSpill} = do_insns(Code0, TempMap, Strategy, [], false), - {Defun#defun{code=Code1,var_range={0,hipe_gensym:get_var(x86)}}, - DidSpill}. + do_bbs(hipe_x86_cfg:labels(CFG), TempMap, Strategy, CFG, false). + +do_bbs([], _, _, CFG, DidSpill) -> {CFG, DidSpill}; +do_bbs([Lbl|Lbls], TempMap, Strategy, CFG0, DidSpill0) -> + Code0 = hipe_bb:code(BB = hipe_x86_cfg:bb(CFG0, Lbl)), + {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0), + CFG = hipe_x86_cfg:bb_add(CFG0, Lbl, hipe_bb:code_update(BB, Code)), + do_bbs(Lbls, TempMap, Strategy, CFG, DidSpill). do_insns([I|Insns], TempMap, Strategy, Accum, DidSpill0) -> {NewIs, DidSpill1} = do_insn(I, TempMap, Strategy), @@ -169,14 +173,22 @@ do_jmp_switch(I, TempMap, Strategy) -> %%% Fix a lea op. do_lea(I, TempMap, Strategy) -> - #lea{temp=Temp} = I, - case is_spilled(Temp, TempMap) of - false -> - {[I], false}; - true -> - NewTmp = spill_temp('untagged', Strategy), - {[I#lea{temp=NewTmp}, hipe_x86:mk_move(NewTmp, Temp)], - true} + #lea{mem=Mem0,temp=Temp0} = I, + {FixMem, Mem, DidSpill1} = fix_mem_operand(Mem0, TempMap, temp1(Strategy)), + case Mem of + #x86_mem{base=Base, off=#x86_imm{value=0}} -> + %% We've decayed into a move due to both operands being memory (there's an + %% 'add' in FixMem). + {FixMem ++ [hipe_x86:mk_move(Base, Temp0)], DidSpill1}; + #x86_mem{} -> + {StoreTemp, Temp, DidSpill2} = + case is_mem_opnd(Temp0, TempMap) of + false -> {[], Temp0, false}; + true -> + Temp1 = clone2(Temp0, temp0(Strategy)), + {[hipe_x86:mk_move(Temp1, Temp0)], Temp1, true} + end, + {FixMem ++ [I#lea{mem=Mem,temp=Temp} | StoreTemp], DidSpill1 or DidSpill2} end. %%% Fix a move op. diff --git a/lib/hipe/x86/hipe_x86_ra_x87_ls.erl b/lib/hipe/x86/hipe_x86_ra_x87_ls.erl deleted file mode 100644 index 1ee76e5948..0000000000 --- a/lib/hipe/x86/hipe_x86_ra_x87_ls.erl +++ /dev/null @@ -1,64 +0,0 @@ -%% $Id$ -%% -%% %CopyrightBegin% -%% -%% Copyright Ericsson AB 2006-2016. All Rights Reserved. -%% -%% 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. -%% -%% %CopyrightEnd% -%% - -%% Linear Scan register allocator for x87 - --ifdef(HIPE_AMD64). --define(HIPE_X86_RA_X87_LS, hipe_amd64_ra_x87_ls). --define(HIPE_X86_SPECIFIC_X87, hipe_amd64_specific_x87). --define(HIPE_X86_PP, hipe_amd64_pp). --define(HIPE_X86_RA_LS, hipe_amd64_ra_ls). --else. --define(HIPE_X86_RA_X87_LS, hipe_x86_ra_x87_ls). --define(HIPE_X86_SPECIFIC_X87, hipe_x86_specific_x87). --define(HIPE_X86_PP, hipe_x86_pp). --define(HIPE_X86_RA_LS, hipe_x86_ra_ls). --endif. - --module(?HIPE_X86_RA_X87_LS). --export([ra/2]). - -%%-define(DEBUG,1). - --define(HIPE_INSTRUMENT_COMPILER, false). %% Turn off instrumentation. --include("../main/hipe.hrl"). - -ra(Defun, Options) -> - ?inc_counter(ra_calls_counter,1), - CFG = hipe_x86_cfg:init(Defun), - %% ?inc_counter(ra_caller_saves_counter,count_caller_saves(CFG)), - SpillIndex = 0, - SpillLimit = ?HIPE_X86_SPECIFIC_X87:number_of_temporaries(CFG), - ?inc_counter(bbs_counter, length(hipe_x86_cfg:labels(CFG))), - - ?inc_counter(ra_iteration_counter,1), - %% ?HIPE_X86_PP:pp(Defun), - Cfg = hipe_x86_cfg:init(Defun), % XXX: didn't we just compute this above? - - {Coloring,NewSpillIndex} = - ?HIPE_X86_RA_LS:regalloc(Cfg, - ?HIPE_X86_SPECIFIC_X87:allocatable(), - [hipe_x86_cfg:start_label(Cfg)], - SpillIndex, SpillLimit, Options, - ?HIPE_X86_SPECIFIC_X87), - - ?add_spills(Options, NewSpillIndex), - {Defun, Coloring, NewSpillIndex}. diff --git a/lib/hipe/x86/hipe_x86_spill_restore.erl b/lib/hipe/x86/hipe_x86_spill_restore.erl index f17b91f33b..32b1eb7b40 100644 --- a/lib/hipe/x86/hipe_x86_spill_restore.erl +++ b/lib/hipe/x86/hipe_x86_spill_restore.erl @@ -25,13 +25,11 @@ -ifdef(HIPE_AMD64). -define(HIPE_X86_SPILL_RESTORE, hipe_amd64_spill_restore). -define(HIPE_X86_LIVENESS, hipe_amd64_liveness). --define(HIPE_X86_SPECIFIC, hipe_amd64_specific). -define(HIPE_X86_REGISTERS, hipe_amd64_registers). -define(X86STR, "amd64"). -else. -define(HIPE_X86_SPILL_RESTORE, hipe_x86_spill_restore). -define(HIPE_X86_LIVENESS, hipe_x86_liveness). --define(HIPE_X86_SPECIFIC, hipe_x86_specific). -define(HIPE_X86_REGISTERS, hipe_x86_registers). -define(X86STR, "x86"). -endif. @@ -51,15 +49,13 @@ -include("../flow/cfg.hrl"). % Added for the definition of #cfg{} %% Main function -spill_restore(Defun, Options) -> - CFG = ?option_time(firstPass(Defun), ?X86STR" First Pass", Options), - CFGFinal = ?option_time(secondPass(CFG), ?X86STR" Second Pass", Options), - hipe_x86_cfg:linearise(CFGFinal). +spill_restore(CFG0, Options) -> + CFG1 = ?option_time(firstPass(CFG0), ?X86STR" First Pass", Options), + ?option_time(secondPass(CFG1), ?X86STR" Second Pass", Options). %% Performs the first pass of the algorithm. %% By working bottom up, introduce the pseudo_spills. -firstPass(Defun) -> - CFG0 = ?HIPE_X86_SPECIFIC:defun_to_cfg(Defun), +firstPass(CFG0) -> %% get the labels bottom up Labels = hipe_x86_cfg:postorder(CFG0), Liveness = ?HIPE_X86_LIVENESS:analyse(CFG0), diff --git a/lib/hipe/x86/hipe_x86_x87.erl b/lib/hipe/x86/hipe_x86_x87.erl index e874490252..10bb6aa75c 100644 --- a/lib/hipe/x86/hipe_x86_x87.erl +++ b/lib/hipe/x86/hipe_x86_x87.erl @@ -41,13 +41,12 @@ %%---------------------------------------------------------------------- -map(Defun) -> - CFG0 = hipe_x86_cfg:init(Defun), +map(CFG0) -> %% hipe_x86_cfg:pp(CFG0), Liveness = ?HIPE_X86_LIVENESS:analyse(CFG0), StartLabel = hipe_x86_cfg:start_label(CFG0), {CFG1,_} = do_blocks([], [StartLabel], CFG0, Liveness, [], gb_trees:empty()), - hipe_x86_cfg:linearise(CFG1). + CFG1. do_blocks(Pred, [Lbl|Lbls], CFG, Liveness, Map, BlockMap) -> case gb_trees:lookup(Lbl, BlockMap) of |