hipe_icode.erl

OTP是开放电信平台的简称

  
%% This representation of a variable is used when pretty printing 
%% typed icode.
annotate_var({var, Name}, Type) -> {var, Name, Type};
annotate_var({var, Name, _OldType}, Type) -> {var, Name, Type}.
is_annotated_var({var, _Name, _Type}) -> true;
is_annotated_var(_) -> false.
var_annotation({var, _Name, Type}) -> Type.
unannotate_var({var, Name, _}) -> {var, Name}.

-record(reg, {name}).

mk_reg(V) -> #reg{name=V}.
reg_name(#reg{name=Name}) -> Name.
reg_is_gcsafe(#reg{}) -> false. % for now
%% @spec is_reg(icode_arg()) -> bool()
is_reg(#reg{}) -> true;
is_reg(_) -> false.

-record(fvar, {name}).

mk_fvar(V) -> #fvar{name=V}.
fvar_name(#fvar{name=Name}) -> Name.
%% @spec is_fvar(icode_arg()) -> bool()
is_fvar(#fvar{}) -> true;
is_fvar(_) -> false.

%% @spec is_var_or_fvar_or_reg(icode_arg()) -> bool()
is_var_or_fvar_or_reg(#var{}) -> true;
is_var_or_fvar_or_reg(#fvar{}) -> true;
is_var_or_fvar_or_reg(#reg{}) -> true;
is_var_or_fvar_or_reg(_) -> false.

%%
%% Floating point Icode instructions.
%%

%%
%% fmove
%%

mk_fmove(Dst, Src) -> #fmove{dst=Dst, src=Src}.
fmove_dst(#fmove{dst=Dst}) -> Dst.
fmove_src(#fmove{src=Src}) -> Src.
%%fmove_dst_update(M, NewDst) -> M#fmove{dst=NewDst}.
%%fmove_src_update(M, NewSrc) -> M#fmove{src=NewSrc}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Liveness info 
%%

%% @spec uses(icode_instruction()) -> [icode_arg()]
uses(Instr) ->
  remove_constants(args(Instr)).

%% @spec args(icode_instruction()) -> [var()]
args(I) ->
  case I of
    #'if'{} -> if_args(I);
    #switch_val{} -> [switch_val_arg(I)];
    #switch_tuple_arity{} -> [switch_tuple_arity_arg(I)];
    #type{} -> type_args(I);
    #move{} -> [move_src(I)];
    #fail{} -> fail_args(I);
    #call{} -> call_args(I);
    #enter{} -> enter_args(I);
    #return{} -> return_vars(I);
    #fmove{} -> [fmove_src(I)];
    #phi{} -> phi_args(I);
    #goto{} -> [];
    #begin_try{} -> [];
    #begin_handler{} -> [];
    #end_try{} -> [];
    #comment{} -> [];
    #label{} -> []
  end.

defines(I) ->
  case I of
    #move{} -> remove_constants([move_dst(I)]);
    #fmove{} -> remove_constants([fmove_dst(I)]);
    #call{} -> remove_constants(call_dstlist(I));
    #begin_handler{} -> remove_constants(begin_handler_dstlist(I));
    #phi{} -> remove_constants([phi_dst(I)]);
    #'if'{} -> [];
    #switch_val{} -> [];
    #switch_tuple_arity{} -> [];
    #type{} -> [];
    #goto{} -> [];
    #fail{} -> [];
    #enter{} -> [];
    #return{} -> [];
    #begin_try{} -> [];
    #end_try{} -> [];
    #comment{} -> [];
    #label{} -> []
  end.


remove_constants(L) ->
  lists:filter(fun(X) -> not is_const(X) end, L).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Utilities
%%

%%
%% Substitution: replace occurrences of X by Y if {X,Y} is in the
%%   Subst_list.

subst(Subst, X) ->
  subst_defines(Subst, subst_uses(Subst,X)).

subst_uses(Subst, X) ->
  case X of
    #'if'{} -> X#'if'{args = subst_list(Subst, if_args(X))};
    #switch_val{} -> X#switch_val{arg = subst1(Subst, switch_val_arg(X))};
    #switch_tuple_arity{} ->
      X#switch_tuple_arity{arg = subst1(Subst, switch_tuple_arity_arg(X))};
    #type{} -> X#type{args = subst_list(Subst, type_args(X))};
    #move{} -> X#move{src = subst1(Subst, move_src(X))};
    #fail{} -> X#fail{args = subst_list(Subst, fail_args(X))};
    #call{} -> X#call{args = subst_list(Subst, call_args(X))};
    #enter{} -> X#enter{args = subst_list(Subst, enter_args(X))};
    #return{} -> X#return{vars = subst_list(Subst, return_vars(X))};
    #fmove{} -> X#fmove{src = subst1(Subst, fmove_src(X))};
    #phi{} -> phi_argvar_subst(X, Subst);
%%  #goto{} -> X;
%%  #begin_try{} -> X;
%%  #begin_handler{} -> X;
%%  #end_try{} -> X;
%%  #comment{} -> X;
%%  #label{} -> X
    _ -> X
  end.

subst_defines(Subst, X) ->
  case X of
    #move{} -> X#move{dst = subst1(Subst, move_dst(X))};
    #call{} -> X#call{dstlist = subst_list(Subst, call_dstlist(X))};
    #begin_handler{} -> 
      X#begin_handler{dstlist = subst_list(Subst,
					   begin_handler_dstlist(X))};
    #fmove{} -> X#fmove{dst = subst1(Subst, fmove_dst(X))};
    #phi{} -> X#phi{dst = subst1(Subst, phi_dst(X))};
%%    #'if'{} -> X;
%%    #switch_val{} -> X;
%%    #switch_tuple_arity{} -> X;
%%    #type{} -> X;
%%    #goto{} -> X;
%%    #fail{} -> X;
%%    #enter{} -> X;
%%    #return{} -> X;
%%    #begin_try{} -> X;
%%    #end_try{} -> X;
%%    #comment{} -> X;
%%    #label{} -> X
    _ -> X
  end.

subst_list(S,Xs) ->
  [subst1(S,X) || X <- Xs].

subst1([],X) -> X;
subst1([{X,Y}|_],X) -> Y;
subst1([_|Xs],X) -> subst1(Xs,X).

%%
%% @doc Returns the successors of an Icode branch instruction.
%%

successors(Jmp) ->
  case Jmp of
    #'if'{} -> [if_true_label(Jmp), if_false_label(Jmp)];
    #goto{} -> [goto_label(Jmp)];
    #switch_val{} -> [switch_val_fail_label(Jmp)|
		      lists:map(fun (C) -> element(2,C) end,
				switch_val_cases(Jmp))];
    #switch_tuple_arity{} -> [switch_tuple_arity_fail_label(Jmp)|
			      lists:map(fun (C) -> element(2,C) end,
					switch_tuple_arity_cases(Jmp))];
    #type{} -> [type_true_label(Jmp), type_false_label(Jmp)];
    #call{} -> [call_continuation(Jmp)|
	        case call_fail_label(Jmp) of [] -> []; L -> [L] end];
    #begin_try{} -> [begin_try_successor(Jmp), begin_try_label(Jmp)];
    #fail{} -> case fail_label(Jmp) of [] -> []; L -> [L] end;
    _ -> []
  end.

%%
%% @doc Returns the fail-labels of an Icode instruction.
%%

fails_to(I) ->
  case I of
    #switch_val{} -> [switch_val_fail_label(I)];
    #switch_tuple_arity{} -> [switch_tuple_arity_fail_label(I)];
    #call{} -> [call_fail_label(I)];
    #begin_try{} -> [begin_try_label(I)];  % just for safety
    #fail{} -> [fail_label(I)];
    _ -> []
  end.

%%
%% @doc Redirects jumps from label Old to label New. If the
%%      instruction does not jump to Old, it remains unchanged.
%%

redirect_jmp(Jmp, ToOld, ToOld) ->
  Jmp;    % no need to do anything
redirect_jmp(Jmp, ToOld, ToNew) ->
  NewIns =
    case Jmp of
      #'if'{} ->
	NewJmp = case if_true_label(Jmp) of
		   ToOld -> if_true_label_update(Jmp, ToNew);
		   _ -> Jmp
		 end,
	case if_false_label(NewJmp) of
	  ToOld -> if_false_label_update(NewJmp, ToNew);
	  _ -> NewJmp
	end;
      #goto{} ->
	case goto_label(Jmp) of
	  ToOld -> Jmp#goto{label=ToNew};
	  _ -> Jmp
	end;
      #switch_val{} ->
	NewJmp = case switch_val_fail_label(Jmp) of
		   ToOld -> switch_val_fail_label_update(Jmp, ToNew);
		   _ -> Jmp
		 end,
	NewJmp#switch_val{cases = 
			  lists:map(fun (Pair) ->
					case Pair of 
					  ({Val,ToOld}) -> {Val,ToNew};
					  (Unchanged) -> Unchanged
					end
				    end, 
				    switch_val_cases(NewJmp))
			 };
      #switch_tuple_arity{} ->
	NewJmp = case switch_tuple_arity_fail_label(Jmp) of
		   ToOld -> 
		     Jmp#switch_tuple_arity{fail_label=ToNew};
		   _ -> Jmp
		 end,
	NewJmp#switch_tuple_arity{cases = 
				  lists:map(fun (Pair) -> 
						case Pair of
						  ({Val,ToOld}) -> {Val,ToNew};
						  (Unchanged) -> Unchanged
						end
					    end, 
					    switch_tuple_arity_cases(NewJmp))
				 };
      #type{} ->
	NewJmp = case type_true_label(Jmp) of
		   ToOld -> Jmp#type{true_label=ToNew};
		   _ -> Jmp
		 end,
	case type_false_label(NewJmp) of
	  ToOld -> NewJmp#type{false_label=ToNew};
	  _ -> NewJmp
	end;
      #call{} -> 
	NewCont = case call_continuation(Jmp) of
		    ToOld -> ToNew;
		    OldCont -> OldCont
		  end,
	NewFail = case call_fail_label(Jmp) of
		    ToOld -> ToNew;
		    OldFail -> OldFail
		  end,
	Jmp#call{continuation = NewCont, 
		 fail_label = NewFail};
      #begin_try{} ->
	NewLabl = case begin_try_label(Jmp) of
		    ToOld ->  ToNew;
		    OldLab -> OldLab
		  end,
	NewSucc = case begin_try_successor(Jmp) of
		    ToOld ->  ToNew;
		    OldSucc -> OldSucc
		  end,
	Jmp#begin_try{label = NewLabl,successor=NewSucc};
      #fail{} ->
	case fail_label(Jmp) of
	  ToOld -> Jmp#fail{fail_label=ToNew};
	  _ -> Jmp
	end;
      _ -> Jmp
    end,
  simplify_branch(NewIns).

%%
%% @doc Turns a branch into a goto if it has only one successor and it
%%      is safe to do so.
%%

simplify_branch(I) ->
  case ordsets:from_list(successors(I)) of
    [Label] ->
      Goto = mk_goto(Label),
      case I of
	#type{} -> Goto;
	#'if'{} -> Goto;
	#switch_tuple_arity{} -> Goto;
	#switch_val{} -> Goto;
	_ -> I
      end;
    _ -> I
  end.

%%
%% Is this an unconditional jump (causes a basic block not to have a 
%% fallthrough successor).
%%

%% is_uncond(I) ->
%%   case I of
%%     #goto{} -> true;
%%     #fail{} -> true;
%%     #enter{} -> true;
%%     #return{} -> true;
%%     #call{} -> 
%%       case call_fail_label(I) of
%% 	[] -> 
%% 	  case call_continuation(I) of
%% 	    [] -> false;
%% 	    _ -> true
%% 	  end;
%% 	_ -> true
%%       end;
%%     _ -> false
%%   end.

%% @spec is_branch(icode_instruction()) -> bool()
%%
%% @doc Succeeds if the Icode instruction is a branch. I.e. a
%%      (possibly conditional) discontinuation of linear control flow.
%% @end

is_branch(Instr) ->
  case Instr of
    #'if'{} -> true;
    #switch_val{} -> true;
    #switch_tuple_arity{} -> true;
    #type{} -> true;
    #goto{} -> true;
    #fail{} -> true;
    #call{} -> 
      case call_fail_label(Instr) of
	[] -> 
	  case call_continuation(Instr) of
	    [] -> false;
	    _ -> true
	  end;
	_ -> true
      end;
    #enter{} -> true;
    #return{} -> true;
    #begin_try{} -> true;
    _ -> false
  end.

%%
%% @doc Makes a new variable.
%%

mk_new_var() ->
  mk_var(hipe_gensym:get_next_var(icode)).

%%
%% @doc Makes a new fp variable.
%%

mk_new_fvar() ->
  mk_fvar(hipe_gensym:get_next_var(icode)).

%%
%% @doc Makes a new register.
%%

mk_new_reg() ->
  mk_reg(hipe_gensym:get_next_var(icode)).

%%
%% @doc Makes a new label.
%%

mk_new_label() ->
  mk_label(hipe_gensym:get_next_label(icode)).

%%
%% @doc Makes a bunch of move operations.
%%

mk_moves([], []) ->
  [];
mk_moves([X|Xs], [Y|Ys]) ->
  [mk_move(X, Y) | mk_moves(Xs, Ys)].

%%
%% Makes a series of element operations.
%%

%% mk_elements(_, []) -> 
%%   [];
%% mk_elements(Tuple, [X|Xs]) ->
%%   [mk_primop([X], #unsafe_element{index=length(Xs)+1}, [Tuple]) | 
%%    mk_elements(Tuple, Xs)].

%%
%% @doc Removes comments from Icode.
%%

strip_comments(ICode) ->
  icode_code_update(ICode, no_comments(icode_code(ICode))).

no_comments([]) ->
  [];
no_comments([I|Xs]) ->
  case is_comment(I) of 
    true -> no_comments(Xs);
    false -> [I|no_comments(Xs)]
  end.

%%-----------------------------------------------------------------------

%% @spec is_safe(icode_instruction()) -> bool()
%%
%% @doc True if an Icode instruction is safe (can be removed if the
%% result is not used). Note that pure control flow instructions
%% cannot be reguarded as safe, as they are not defining anything.

is_safe(Instr) ->
  case Instr of
    %% Instructions that are safe, or might be safe to remove.
    #move{} -> true;
    #fmove{} -> true;
    #phi{} -> true;
    #begin_handler{} -> true;
    #call{} ->
      case call_fun(Instr) of
	{M,F,A} ->
	  erl_bifs:is_safe(M,F,A);
	Op ->
	  hipe_icode_primops:is_safe(Op)
      end;
    %% Control flow instructions.
    #'if'{} -> false;
    #switch_val{} -> false;
    #switch_tuple_arity{} -> false;
    #type{} -> false;
    #goto{} -> false;
    #label{} -> false;
    %% Returning instructions without defines.
    #return{} -> false;
    #fail{} -> false;
    #enter{} -> false;
    %% Internal auxilary instructions that should not be removed
    %% unless you really know what you are doing.
    #comment{} -> false;
    #begin_try{} -> false;
    #end_try{} -> false
  end.

%%-----------------------------------------------------------------------

highest_var(Code) ->
  highest_var(Code, 0).

highest_var([I|Is], Max) ->
  Defs = defines(I),
  Uses = uses(I),
  highest_var(Is, new_max(Defs++Uses, Max));
highest_var([], Max) ->
  Max.

new_max([V|Vs], Max) ->
  VName = 
    case is_var(V) of
      true ->
	var_name(V);
      false ->
	case is_fvar(V) of
	  true ->
	    fvar_name(V);
	  _ ->
	    reg_name(V)
	end
    end,
  if VName > Max ->
      new_max(Vs, VName);
     true ->
      new_max(Vs, Max)
  end;
new_max([], Max) when is_integer(Max) ->
  Max.

%%-----------------------------------------------------------------------

highest_label(Code) ->
  highest_label(Code, 0).

highest_label([I|Is], Max) ->
  case is_label(I) of 
    true ->
      L = label_name(I),
      NewMax = if L > Max -> L; true -> Max end,
      highest_label(Is, NewMax);
    false ->
      highest_label(Is, Max)
  end;
highest_label([], Max) when is_integer(Max) ->
  Max.

%%-----------------------------------------------------------------------