hipe_x86_x87.erl

OTP是开放电信平台的简称

%% -*- erlang-indent-level: 2 -*-
%% $Id$
%% Floating point handling.

-ifdef(HIPE_AMD64).
-define(HIPE_X86_X87,       hipe_amd64_x87).
-define(HIPE_X86_DEFUSE,    hipe_amd64_defuse).
-define(HIPE_X86_LIVENESS,  hipe_amd64_liveness).
-define(HIPE_X86_REGISTERS, hipe_amd64_registers).
-else.
-define(HIPE_X86_X87,       hipe_x86_x87).
-define(HIPE_X86_DEFUSE,    hipe_x86_defuse).
-define(HIPE_X86_LIVENESS,  hipe_x86_liveness).
-define(HIPE_X86_REGISTERS, hipe_x86_registers).
-endif.

-module(?HIPE_X86_X87).
-include("../x86/hipe_x86.hrl").
-include("../main/hipe.hrl").
-export([map/1]).

map(Defun) ->
  CFG0 = hipe_x86_cfg:init(Defun),
  %%hipe_x86_cfg:pp(CFG0),
  Liveness = ?HIPE_X86_LIVENESS:analyse(CFG0),
  StartLabel = hipe_x86_cfg:start_label(CFG0),
  SuccMap = hipe_x86_cfg:succ_map(CFG0),
  {CFG1, _} = do_blocks([], [StartLabel], CFG0, Liveness, [], SuccMap, 
			gb_trees:empty()),
  hipe_x86_cfg:linearise(CFG1).


do_blocks(Pred, [Lbl|Lbls], CFG, Liveness, Map, SuccMap, BlockMap) ->
  case gb_trees:lookup(Lbl, BlockMap) of
    none ->
      %% This block has not been visited.
      Block = hipe_x86_cfg:bb(CFG, Lbl),
      Succ = hipe_x86_cfg:succ(SuccMap, Lbl),
      NewBlockMap = gb_trees:insert(Lbl, Map, BlockMap),
      LiveOut = [X || X <- ?HIPE_X86_LIVENESS:liveout(Liveness, Lbl),
			   is_fp(X)],
      Code = hipe_bb:code(Block),
      ReverseCode = lists:reverse(Code),
      {NewCode0, NewMap, NewBlockMap1, Dirty} = 
	do_block(ReverseCode, LiveOut, Map, NewBlockMap),
      {NewCFG1, NewSuccMap} =
	case Dirty of
	  true ->
	    NewBlock = hipe_bb:code_update(Block, NewCode0),
	    {hipe_x86_cfg:bb_add(CFG, Lbl, NewBlock), SuccMap};
	  _ ->
	    {CFG, SuccMap}
	end,
      {NewCFG3, NewBlockMap2} = 
	do_blocks(Lbl,Succ, NewCFG1, Liveness, NewMap, 
 		  NewSuccMap, NewBlockMap1),
      do_blocks(Pred,Lbls, NewCFG3, Liveness, 
		Map, NewSuccMap, NewBlockMap2);
    {value, fail} ->
      %% Don't have to follow this trace any longer.
      do_blocks(Pred,Lbls, CFG, Liveness, 
		Map, SuccMap, BlockMap);
    {value, ExistingMap} ->
      %% This block belongs to a trace already handled.
      %% The Map coming in must be identical to the one used
      %% when the block was processed.
      if ExistingMap =:= Map -> 
	  do_blocks(Pred,Lbls, CFG, Liveness, 
		    Map, SuccMap, BlockMap);
	 true ->
	  NewCFG = do_shuffle(Pred,Lbl,CFG, Map,ExistingMap),
	  NewSuccMap = hipe_x86_cfg:succ_map(NewCFG),
	  do_blocks(Pred, Lbls, NewCFG, Liveness, Map, 
		    NewSuccMap, BlockMap)
      end
  end;
do_blocks(_Pred, [], CFG, _Liveness, _Map, _SuccMap, BlockMap) ->
  {CFG, BlockMap}.

do_block(Ins, LiveOut, Map, BlockMap) ->
  do_block(Ins, LiveOut, Map, BlockMap, false).

do_block([I|Is], LiveOut, Map, BlockMap, Dirty) ->
  case handle_insn(I) of
    false -> 
      {NewCode, NewMap, NewBlockMap, NewDirty} = 
	do_block(Is, LiveOut, Map, BlockMap, Dirty),
      {NewCode++[I], NewMap, NewBlockMap, NewDirty};
    true ->
      Def = ordsets:from_list(?HIPE_X86_DEFUSE:insn_def(I)),
      Use = ordsets:from_list(?HIPE_X86_DEFUSE:insn_use(I)),
      NewLiveOut = 
	ordsets:filter(fun(X) -> is_fp(X) end,
		       ordsets:union(ordsets:subtract(LiveOut, Def), Use)),
      {NewCode, NewMap, NewBlockMap, NewDirty} = 
	do_block(Is, NewLiveOut, Map, BlockMap, Dirty),
      {NewI, NewMap1, NewBlockMap1} = 
	do_insn(I, LiveOut, NewMap, NewBlockMap),
      NewDirty1 =
	if NewDirty =:= true -> true;
	   NewI =:= [I] -> false;
	   true -> true
	end,
      {NewCode++NewI, NewMap1, NewBlockMap1, NewDirty1}
  end;
do_block([], LiveOut, Map, BlockMap, Dirty) ->
  case lists:filter(fun(X) -> not lists:member(X, LiveOut) end, Map) of
    [] ->
      {[], Map, BlockMap, Dirty}; 
    Pop ->
      {PopIns, NewMap} = pop_dead(Pop, Map),
      {PopIns, NewMap, BlockMap, true}
  end.

do_shuffle(Pred,Lbl,CFG, OldMap, NewMap) ->
  %% First make sure both maps has the same members.
  Push = NewMap -- OldMap,
  Pop = OldMap -- NewMap,
  {PopInsn, OldMap0} = pop_dead(Pop, OldMap),
  {PushInsn, OldMap1} = 
    case Push of
      []-> {[], OldMap0};
      _-> push_list(lists:reverse(Push), OldMap0)
    end,
  Code =
    if OldMap1=:=NewMap ->
	%% It was enough to push and pop.
	PopInsn ++ PushInsn ++ [hipe_x86:mk_jmp_label(Lbl)];
       true->
	%% Shuffle the positions so the maps match
	Cycles = find_swap_cycles(OldMap1, NewMap),
	SwitchInsns = do_switching(Cycles),
	PopInsn ++ PushInsn ++ SwitchInsns ++ [hipe_x86:mk_jmp_label(Lbl)]
    end,
  %% Update the CFG.
  NewLabel = hipe_gensym:get_next_label(x86),
  NewCFG1 = hipe_x86_cfg:bb_add(CFG, NewLabel, hipe_bb:mk_bb(Code)),
  OldPred = hipe_x86_cfg:bb(NewCFG1, Pred),
  PredCode = hipe_bb:code(OldPred),
  NewLast = redirect(lists:last(PredCode), Lbl,NewLabel),
  NewPredCode = butlast(PredCode) ++ [NewLast],
  NewPredBB = hipe_bb:code_update(OldPred, NewPredCode),
  hipe_x86_cfg:bb_add(NewCFG1, Pred, NewPredBB).


find_swap_cycles(OldMap, NewMap) ->
  Moves = [get_pos(X,NewMap,1) || X <- OldMap],
  find_swap_cycles(OldMap, Moves, lists:seq(1,length(OldMap)), []).

find_swap_cycles(OldMap, Moves, NotHandled, Cycles) ->
  if NotHandled =:= [] -> Cycles;
     true -> 
      Cycle = find_cycle(Moves, [hd(NotHandled)]),
      NewNotHandled = NotHandled -- Cycle,
      case lists:member(1, Cycle) of
	true->
	  %% The cycle that contains the first element on the stack
	  %% must be processed last.
	  NewCycle = format_cycle(Cycle),
	  find_swap_cycles(OldMap, Moves, NewNotHandled,
			   Cycles++[NewCycle]);
	_ ->
	  NewCycle = format_cycle(Cycle),
	  find_swap_cycles(OldMap, Moves, NewNotHandled,
			   [NewCycle|Cycles])
      end
  end.

find_cycle(Moves, Cycle) ->
  To = lists:nth(lists:last(Cycle),Moves),
  if To =:= hd(Cycle) -> Cycle;
     true -> find_cycle(Moves, Cycle++[To])
  end.

format_cycle(C) ->
  %% The position numbers start with 1 - should start with 0.
  %% If position 0 is in the cycle it will be permuted until
  %% the 0 is first and then remove it.
  %% Otherwise the first element is also added last.
  NewCycle = [X - 1 || X <- C],
  case lists:member(0, NewCycle) of
    true -> format_cycle(NewCycle, []);
    _ -> NewCycle ++ [hd(NewCycle)]
  end.

format_cycle([H|T], NewCycle) ->
  case H of
    0 -> T ++ NewCycle;
    _ -> format_cycle(T,NewCycle++[H])
  end.

do_switching(Cycles) ->
  do_switching(Cycles, []).

do_switching([C|Cycles], Insns) ->
  NewInsns = Insns ++ [hipe_x86:mk_fp_unop(fxch, mk_st(X)) || X <- C],
  do_switching(Cycles, NewInsns);
do_switching([], Insns) ->
  Insns.

redirect(Insn, OldLbl, NewLbl) ->
  case Insn of
    #pseudo_call{contlab=ContLab, sdesc=SDesc} ->
      #x86_sdesc{exnlab=ExnLab} = SDesc,
      if ContLab =:= OldLbl -> 
	  Insn#pseudo_call{contlab=NewLbl};
	 ExnLab =:= OldLbl ->
	  Insn#pseudo_call{sdesc=SDesc#x86_sdesc{exnlab=NewLbl}}
      end;
    _ -> 
      hipe_x86_cfg:redirect_jmp(Insn, OldLbl, NewLbl)
  end.

do_insn(I, LiveOut, Map, BlockMap) ->
  case I of
    #pseudo_call{'fun'=Fun, contlab=ContLab}->
      case Fun of
	%% We don't want to spill anything if an exception has been thrown.
	{_, 'handle_fp_exception'} ->
	  NewBlockMap = 
	    case gb_trees:lookup(ContLab, BlockMap) of
	      {value, fail} ->
		BlockMap;
	      {value, _} ->
		gb_trees:update(ContLab, fail, BlockMap);
	      none ->
		gb_trees:insert(ContLab, fail, BlockMap)
	    end,
	  {[I], [], NewBlockMap};
	_ ->
	  {pop_all(Map)++[I],[],BlockMap}
      end;
    #fp_unop{op='fwait'} ->
      Store = pseudo_pop(Map),
      {Store ++ [I], Map, BlockMap};
    #fp_unop{} ->
      {NewI, NewMap} = do_fp_unop(I, LiveOut, Map),
      {NewI, NewMap, BlockMap};
    #fp_binop{} ->
      {NewI, NewMap} = do_fp_binop(I, LiveOut, Map),
      {NewI, NewMap, BlockMap};
    #fmove{src=Src, dst=Dst} ->
      if Src=:=Dst ->
	  %% Don't need to keep this instruction!
	  %% However, we may need to pop from the stack.
	  case is_liveOut(Src, LiveOut) of
	    true->
	      {[], Map, BlockMap};
	    false ->
	      {SwitchInsn, NewMap0} = switch_first(Dst, Map),
	      NewMap = pop(NewMap0),
	      {SwitchInsn++pop_insn(), NewMap, BlockMap}
	  end;
	 true -> 
	  {NewI, NewMap} = do_fmove(Src, Dst, LiveOut, Map),
	  {NewI, NewMap, BlockMap}
      end;
    _ ->
      {[I], Map, BlockMap}
  end.

do_fmove(Src, Dst=#x86_mem{},LiveOut, Map) ->
%%% Storing a float from the stack into memory.
  {SwitchInsn, NewMap0} = switch_first(Src, Map),
  case is_liveOut(Src, LiveOut) of
    true ->
      {SwitchInsn ++ [hipe_x86:mk_fp_unop(fst, Dst)], NewMap0};
    _ ->
      NewMap1 = pop(NewMap0),
      {SwitchInsn ++ [hipe_x86:mk_fp_unop(fstp, Dst)], NewMap1}
  end;
do_fmove(Src=#x86_mem{}, Dst, _LiveOut, Map) ->
%%% Pushing a float into the stack.
  case in_map(Dst, Map) of
    true -> ?EXIT({loadingExistingFpVariable,{Src,Dst}});
    _ -> ok
  end,
  {PushOp, [_|NewMap0]} = push(Src, Map),
  %% We want Dst in the map rather than Src.
  NewMap = [Dst|NewMap0],
  {PushOp, NewMap};
do_fmove(Src, Dst, LiveOut, Map) ->
%%% Copying a float that either is spilled or is on the fp stack,
%%% or converting a fixnum in a temp to a float on the fp stack.
  case in_map(Dst, Map) of
    true -> ?EXIT({copyingToExistingFpVariable,{Src,Dst}});
    _ -> ok
  end,
  IsConv =
    case Src of
      #x86_temp{type=Type} -> Type =/= 'double';
      _ -> false
    end,
  case IsConv of
    true ->
      do_conv(Src,Dst,Map);
    _ ->
      %% Copying.
      case {is_liveOut(Src, LiveOut),in_map(Src, Map)} of
	{false,true} ->
	  %% Just remap Dst to Src
	  {Head,[_|T]} = lists:splitwith(fun(X) -> X /= Src end, Map),
	  {[], Head ++ [Dst|T]};
	_ ->
	  {PushOp, [_|NewMap0]} = push(Src, Map),
	  %% We want Dst in the map rather than Src.
	  NewMap = [Dst|NewMap0],
	  {PushOp, NewMap}
      end
  end.

do_conv(Src=#x86_temp{reg=Reg}, Dst, Map) ->
  %% Converting. Src must not be a register, so we 
  %% might have to put it into memory in between.
  {Move, NewSrc} =