aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/x86/hipe_x86_ra_naive.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/x86/hipe_x86_ra_naive.erl')
-rw-r--r--lib/hipe/x86/hipe_x86_ra_naive.erl409
1 files changed, 409 insertions, 0 deletions
diff --git a/lib/hipe/x86/hipe_x86_ra_naive.erl b/lib/hipe/x86/hipe_x86_ra_naive.erl
new file mode 100644
index 0000000000..e9b99cd2c5
--- /dev/null
+++ b/lib/hipe/x86/hipe_x86_ra_naive.erl
@@ -0,0 +1,409 @@
+%%% -*- erlang-indent-level: 2 -*-
+%%%
+%%% %CopyrightBegin%
+%%%
+%%% Copyright Ericsson AB 2005-2009. All Rights Reserved.
+%%%
+%%% The contents of this file are subject to the Erlang Public License,
+%%% Version 1.1, (the "License"); you may not use this file except in
+%%% compliance with the License. You should have received a copy of the
+%%% Erlang Public License along with this software. If not, it can be
+%%% retrieved online at http://www.erlang.org/.
+%%%
+%%% Software distributed under the License is distributed on an "AS IS"
+%%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%%% the License for the specific language governing rights and limitations
+%%% under the License.
+%%%
+%%% %CopyrightEnd%
+%%%
+%%% simple local x86 regalloc
+
+-ifdef(HIPE_AMD64).
+-define(HIPE_X86_RA_NAIVE, hipe_amd64_ra_naive).
+-define(HIPE_X86_REGISTERS, hipe_amd64_registers).
+-define(HIPE_X86_SPECIFIC_FP, hipe_amd64_specific_sse2).
+-define(ECX, rcx).
+-else.
+-define(HIPE_X86_RA_NAIVE, hipe_x86_ra_naive).
+-define(HIPE_X86_REGISTERS, hipe_x86_registers).
+-define(HIPE_X86_SPECIFIC_FP, hipe_x86_specific_x87).
+-define(ECX, ecx).
+-endif.
+
+-module(?HIPE_X86_RA_NAIVE).
+-export([ra/3]).
+
+-include("../x86/hipe_x86.hrl").
+-define(HIPE_INSTRUMENT_COMPILER, true). % enable instrumentation
+-include("../main/hipe.hrl").
+
+ra(X86Defun, Coloring_fp, Options) ->
+ #defun{code=Code0} = X86Defun,
+ Code1 = do_insns(Code0),
+ NofSpilledFloats = count_non_float_spills(Coloring_fp),
+ NofFloats = length(Coloring_fp),
+ ?add_spills(Options, hipe_gensym:get_var(x86) -
+ ?HIPE_X86_REGISTERS:first_virtual()-
+ NofSpilledFloats -
+ NofFloats),
+ TempMap = [],
+ {X86Defun#defun{code=Code1,
+ var_range={0, hipe_gensym:get_var(x86)}},
+ TempMap}.
+
+count_non_float_spills(Coloring_fp) ->
+ count_non_float_spills(Coloring_fp, 0).
+
+count_non_float_spills([{_,To}|Tail], Num) ->
+ case ?HIPE_X86_SPECIFIC_FP:is_precoloured(To) of
+ true ->
+ count_non_float_spills(Tail, Num);
+ false ->
+ count_non_float_spills(Tail, Num+1)
+ end;
+count_non_float_spills([], Num) ->
+ Num.
+
+do_insns([I|Insns]) ->
+ do_insn(I) ++ do_insns(Insns);
+do_insns([]) ->
+ [].
+
+do_insn(I) -> % Insn -> Insn list
+ case I of
+ #alu{} ->
+ do_alu(I);
+ #cmp{} ->
+ do_cmp(I);
+ #imul{} ->
+ do_imul(I);
+ #jmp_switch{} ->
+ do_jmp_switch(I);
+ #lea{} ->
+ do_lea(I);
+ #move{} ->
+ do_move(I);
+ #move64{} ->
+ do_move64(I);
+ #movzx{} ->
+ do_movx(I);
+ #movsx{} ->
+ do_movx(I);
+ #fmove{} ->
+ do_fmove(I);
+ #fp_unop{} ->
+ do_fp_unop(I);
+ #fp_binop{} ->
+ do_fp_binop(I);
+ #shift{} ->
+ do_shift(I);
+ #label{} ->
+ [I];
+ #pseudo_jcc{} ->
+ [I];
+ #pseudo_call{} ->
+ [I];
+ #ret{} ->
+ [I];
+ #pseudo_tailcall_prepare{} ->
+ [I];
+ #pseudo_tailcall{} ->
+ [I];
+ #push{} ->
+ [I];
+ #jmp_label{} ->
+ [I];
+ #comment{} ->
+ [I];
+ _ ->
+ io:format("Unknown Instruction = ~w\n", [I]),
+ exit({?MODULE, unknown_instruction, I})
+ end.
+
+%%% Fix an alu op.
+
+do_alu(I) ->
+ #alu{src=Src0,dst=Dst0} = I,
+ {FixSrc,Src,FixDst,Dst} = do_binary(Src0, Dst0),
+ FixSrc ++ FixDst ++ [I#alu{src=Src,dst=Dst}].
+
+%%% Fix a cmp op.
+
+do_cmp(I) ->
+ #cmp{src=Src0,dst=Dst0} = I,
+ {FixSrc, Src, FixDst, Dst} = do_binary(Src0, Dst0),
+ FixSrc ++ FixDst ++ [I#cmp{src=Src,dst=Dst}].
+
+%%% Fix an imul op.
+
+do_imul(I) ->
+ #imul{imm_opt=ImmOpt,src=Src0,temp=Temp0} = I,
+ {FixSrc,Src} = fix_src_operand(Src0), % may use temp0
+ {FixTempSrc,Temp,FixTempDst} =
+ case temp_is_pseudo(Temp0) of
+ false ->
+ {[], Temp0, []};
+ true ->
+ Reg = hipe_x86:mk_temp(?HIPE_X86_REGISTERS:temp1(), 'untagged'),
+ {case ImmOpt of
+ [] -> [hipe_x86:mk_move(Temp0, Reg)]; % temp *= src
+ _ -> [] % temp = src * imm
+ end,
+ Reg,
+ [hipe_x86:mk_move(Reg, Temp0)]}
+ end,
+ FixSrc ++ FixTempSrc ++ [I#imul{src=Src,temp=Temp}] ++ FixTempDst.
+
+%%% Fix a jmp_switch op.
+
+-ifdef(HIPE_AMD64).
+do_jmp_switch(I) ->
+ #jmp_switch{temp=Temp, jtab=Tab} = I,
+ case temp_is_pseudo(Temp) of
+ false ->
+ case temp_is_pseudo(Tab) of
+ false ->
+ [I];
+ true ->
+ Reg = hipe_x86:mk_temp(hipe_amd64_registers:temp0(), 'untagged'),
+ [hipe_x86:mk_move(Temp, Reg), I#jmp_switch{jtab=Reg}]
+ end;
+ true ->
+ Reg = hipe_x86:mk_temp(hipe_amd64_registers:temp1(), 'untagged'),
+ case temp_is_pseudo(Tab) of
+ false ->
+ [hipe_x86:mk_move(Temp, Reg), I#jmp_switch{temp=Reg}];
+ true ->
+ Reg2 = hipe_x86:mk_temp(hipe_amd64_registers:temp0(), 'untagged'),
+ [hipe_x86:mk_move(Temp, Reg),
+ hipe_x86:mk_move(Tab, Reg2),
+ I#jmp_switch{temp=Reg, jtab=Reg2}]
+ end
+ end.
+-else.
+do_jmp_switch(I) ->
+ #jmp_switch{temp=Temp} = I,
+ case temp_is_pseudo(Temp) of
+ false ->
+ [I];
+ true ->
+ Reg = hipe_x86:mk_temp(?HIPE_X86_REGISTERS:temp0(), 'untagged'),
+ [hipe_x86:mk_move(Temp, Reg), I#jmp_switch{temp=Reg}]
+ end.
+-endif.
+
+%%% Fix a lea op.
+
+do_lea(I) ->
+ #lea{temp=Temp} = I,
+ case temp_is_pseudo(Temp) of
+ false ->
+ [I];
+ true ->
+ Reg = hipe_x86:mk_temp(?HIPE_X86_REGISTERS:temp0(), 'untagged'),
+ [I#lea{temp=Reg}, hipe_x86:mk_move(Reg, Temp)]
+ end.
+
+%%% Fix a move op.
+
+do_move(I) ->
+ #move{src=Src0,dst=Dst0} = I,
+ {FixSrc, Src, FixDst, Dst} = do_binary(Src0, Dst0),
+ FixSrc ++ FixDst ++ [I#move{src=Src,dst=Dst}].
+
+-ifdef(HIPE_AMD64).
+do_move64(I) ->
+ #move64{dst=Dst} = I,
+ case is_mem_opnd(Dst) of
+ false ->
+ [I];
+ true ->
+ Reg = hipe_amd64_registers:temp1(),
+ NewDst = clone(Dst, Reg),
+ [I#move64{dst=NewDst}, hipe_x86:mk_move(NewDst, Dst)]
+ end.
+-else.
+do_move64(I) -> exit({?MODULE, I}).
+-endif.
+
+do_movx(I) ->
+ {{FixSrc, Src}, {FixDst, Dst}} =
+ case I of
+ #movsx{src=Src0,dst=Dst0} ->
+ {fix_src_operand(Src0), fix_dst_operand(Dst0)};
+ #movzx{src=Src0,dst=Dst0} ->
+ {fix_src_operand(Src0), fix_dst_operand(Dst0)}
+ end,
+ Reg = ?HIPE_X86_REGISTERS:temp0(),
+ Dst2 = clone(Dst, Reg),
+ I2 = case is_mem_opnd(Dst) of
+ true ->
+ Reg = ?HIPE_X86_REGISTERS:temp0(),
+ Dst2 = clone(Dst, Reg),
+ case I of
+ #movsx{} ->
+ [hipe_x86:mk_movsx(Src, Dst2), hipe_x86:mk_move(Dst2, Dst)];
+ #movzx{} ->
+ [hipe_x86:mk_movzx(Src, Dst2), hipe_x86:mk_move(Dst2, Dst)]
+ end;
+ false ->
+ case I of
+ #movsx{} ->
+ [hipe_x86:mk_movsx(Src, Dst)];
+ #movzx{} ->
+ [hipe_x86:mk_movzx(Src, Dst)]
+ end
+ end,
+ FixSrc ++ FixDst ++ I2.
+
+
+%%% Fix a fmove op.
+%% conv_to_float
+do_fmove(I=#fmove{src=#x86_temp{type=untagged},
+ dst=#x86_temp{type=double}}) ->
+ #fmove{src=Src0,dst=Dst0} = I,
+ Src = clone(Src0, ?HIPE_X86_REGISTERS:temp0()),
+ Dst = clone(Dst0, ?HIPE_X86_REGISTERS:temp1()),
+ [hipe_x86:mk_move(Src0, Src),
+ I#fmove{src=Src, dst=Dst},
+ hipe_x86:mk_fmove(Dst, Dst0)];
+%% fmove
+do_fmove(I) ->
+ #fmove{src=Src0,dst=Dst0} = I,
+ {FixSrc, Src, FixDst, Dst} = do_binary(Src0, Dst0),
+ FixSrc ++ FixDst ++ [I#fmove{src=Src,dst=Dst}].
+
+do_fp_unop(I) ->
+ #fp_unop{arg=Arg} = I,
+ case is_mem_opnd(Arg) of
+ false ->
+ [I];
+ true ->
+ Reg = ?HIPE_X86_REGISTERS:temp1(),
+ NewArg = clone(Arg, Reg),
+ [hipe_x86:mk_fmove(Arg, NewArg),
+ I#fp_unop{arg=NewArg},
+ hipe_x86:mk_fmove(NewArg, Arg)]
+ end.
+
+do_fp_binop(I) ->
+ #fp_binop{src=Src0, dst=Dst0} = I,
+ {FixSrc, Src} = fix_src_operand(Src0),
+ {FixDst, Dst} = fix_dst_operand(Dst0),
+ Reg = ?HIPE_X86_REGISTERS:temp1(),
+ Dst2 = clone(Dst, Reg),
+ FixSrc ++ FixDst ++ [hipe_x86:mk_fmove(Dst, Dst2),
+ I#fp_binop{src=Src, dst=Dst2},
+ hipe_x86:mk_fmove(Dst2, Dst)].
+
+do_shift(I) ->
+ #shift{src=Src0,dst=Dst0} = I,
+ {FixDst, Dst} = fix_dst_operand(Dst0),
+ Reg = ?HIPE_X86_REGISTERS:?ECX(),
+ case Src0 of
+ #x86_imm{} ->
+ FixDst ++ [I#shift{dst=Dst}];
+ #x86_temp{reg=Reg} ->
+ FixDst ++ [I#shift{dst=Dst}]
+ end.
+
+%%% Fix the operands of a binary op.
+%%% 1. remove pseudos from any explicit memory operands
+%%% 2. if both operands are (implicit or explicit) memory operands,
+%%% move src to a reg and use reg as src in the original insn
+
+do_binary(Src0, Dst0) ->
+ {FixSrc, Src} = fix_src_operand(Src0),
+ {FixDst, Dst} = fix_dst_operand(Dst0),
+ {FixSrc3, Src3} =
+ case is_mem_opnd(Src) of
+ false ->
+ {FixSrc, Src};
+ true ->
+ case is_mem_opnd(Dst) of
+ false ->
+ {FixSrc, Src};
+ true ->
+ Reg = ?HIPE_X86_REGISTERS:temp0(),
+ Src2 = clone(Src, Reg),
+ FixSrc2 = FixSrc ++ [mk_move(Src, Src2)],
+ {FixSrc2, Src2}
+ end
+ end,
+ {FixSrc3, Src3, FixDst, Dst}.
+
+%%% Fix any x86_mem operand to not refer to any pseudos.
+%%% The fixup may use additional instructions and registers.
+%%% 'src' operands may clobber '%temp0'.
+%%% 'dst' operands may clobber '%temp1'.
+
+fix_src_operand(Opnd) ->
+ fix_mem_operand(Opnd, ?HIPE_X86_REGISTERS:temp0()).
+
+fix_dst_operand(Opnd) ->
+ fix_mem_operand(Opnd, ?HIPE_X86_REGISTERS:temp1()).
+
+fix_mem_operand(Opnd, Reg) -> % -> {[fixupcode], newop}
+ case Opnd of
+ #x86_mem{base=Base,off=Off} ->
+ case is_mem_opnd(Base) of
+ false ->
+ case src_is_pseudo(Off) of
+ false ->
+ {[], Opnd};
+ true -> % pseudo(reg)
+ Temp = clone(Off, Reg),
+ {[hipe_x86:mk_move(Off, Temp)],
+ Opnd#x86_mem{off=Temp}}
+ end;
+ true ->
+ Temp = clone(Base, Reg),
+ case src_is_pseudo(Off) of
+ false -> % imm/reg(pseudo)
+ {[hipe_x86:mk_move(Base, Temp)],
+ Opnd#x86_mem{base=Temp}};
+ true -> % pseudo1(pseudo0)
+ {[hipe_x86:mk_move(Base, Temp),
+ hipe_x86:mk_alu('add', Off, Temp)],
+ Opnd#x86_mem{base=Temp, off=hipe_x86:mk_imm(0)}}
+ end
+ end;
+ _ ->
+ {[], Opnd}
+ end.
+
+%%% Check if an operand denotes a memory cell (mem or pseudo).
+
+is_mem_opnd(Opnd) ->
+ case Opnd of
+ #x86_mem{} -> true;
+ #x86_temp{} -> temp_is_pseudo(Opnd);
+ _ -> false
+ end.
+
+%%% Check if an operand is a pseudo-Temp.
+
+src_is_pseudo(Src) ->
+ case hipe_x86:is_temp(Src) of
+ true -> temp_is_pseudo(Src);
+ false -> false
+ end.
+
+temp_is_pseudo(Temp) ->
+ not(?HIPE_X86_REGISTERS:is_precoloured(hipe_x86:temp_reg(Temp))).
+
+%%% Make Reg a clone of Dst (attach Dst's type to Reg).
+
+clone(Dst, Reg) ->
+ Type =
+ case Dst of
+ #x86_mem{} -> hipe_x86:mem_type(Dst);
+ #x86_temp{} -> hipe_x86:temp_type(Dst)
+ end,
+ hipe_x86:mk_temp(Reg, Type).
+
+mk_move(Src, Dst=#x86_temp{type=double}) ->
+ hipe_x86:mk_fmove(Src, Dst);
+mk_move(Src, Dst) ->
+ hipe_x86:mk_move(Src, Dst).