hipe_icode_range.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 1,642 行 · 第 1/4 页

%%%-------------------------------------------------------------------
%%% File    : hipe_icode_range.erl
%%% Author  : Per Gustafsson <[e-mail]>
%%% Description : 
%%%
%%% Created : 12 Mar 2007 by Per Gustafsson <[e-mail]>
%%%-------------------------------------------------------------------
-module(hipe_icode_range).

-export([cfg/3,pp_ann/1]).

%%=====================================================================
%% Icode Coordinator Callbacks
%%=====================================================================

-export([replace_nones/1,
	 update__info/2, new__info/1, return__info/1,
	 return_none/0, return_none_args/2, return_any_args/2]).

%%=====================================================================

-import(erl_types, [t_any/0,
		    t_inf/2, t_integer/0,
		    t_from_range_unsafe/2,
		    t_to_string/1,
		    t_none/0,
		    number_min/1, number_max/1
		   ]).

-record(ann,   {range, type, count}).
-record(range, {range, other}).

-define(WIDEN, 1).

-include("hipe_icode.hrl").
-include("hipe_icode_primops.hrl").
-include("../main/hipe.hrl").

-define(TAG_IMMED1_SIZE, 4).

-define(BITS, 64).

cfg(Cfg, IcodeFun, Options) ->
  case proplists:get_bool(concurrent_comp, Options) of
    true ->
      concurrent_cfg(Cfg, IcodeFun, Options, 
		     proplists:get_value(icode_range_server, Options));
    false ->
      ordinary_cfg(Cfg, IcodeFun, Options)
  end.

concurrent_cfg(Cfg, MFA, Options, CompServer) ->
  CompServer ! {ready, {MFA,self()}},
  {ArgsFun,CallFun,FinalFun} = do_analysis(Cfg, MFA, Options),
  do_rewrite(Cfg, MFA, Options, ArgsFun, CallFun, FinalFun).

do_analysis(Cfg, MFA, Options) ->
  receive
    {analyse, {ArgsFun, CallFun, FinalFun}} ->
      analyse(Cfg, {MFA, ArgsFun, CallFun, FinalFun}),
      do_analysis(Cfg, MFA, Options);
    {done, {NewArgsFun, NewCallFun, NewFinalFun}} ->
      {NewArgsFun, NewCallFun, NewFinalFun}
  end.

do_rewrite(Cfg, MFA, Options, ArgsFun, CallFun, FinalFun) ->
  common_rewrite(Cfg, MFA, Options, {MFA, ArgsFun, CallFun, FinalFun}).
 
ordinary_cfg(Cfg, MFA, Options) ->
  Data = make_data(Cfg,MFA),
  common_rewrite(Cfg, MFA, Options, Data).
  
common_rewrite(Cfg, _MFA, _Options, Data) ->
  State = analyse(Cfg, Data),
  State2 = rewrite_blocks(State),
  Cfg1 = state__cfg(State2),
  Cfg2 = hipe_icode_cfg:remove_unreachable_code(Cfg1),
  Cfg3 = convert_cfg_to_types(Cfg2),
  hipe_icode_type:specialize(Cfg3).

make_data(Cfg, {_M,_F,A}=MFA) ->
  NoArgs = 
   case hipe_icode_cfg:is_closure(Cfg) of
      true -> hipe_icode_cfg:closure_arity(Cfg)+1;
      false -> A
    end,
  Args = lists:duplicate(NoArgs, any_type()), 
  ArgsFun = fun(_,_) -> Args end,
  CallFun = fun(_,_) -> [any_type()] end,
  FinalFun = fun(_,_) -> ok end,
  {MFA,ArgsFun,CallFun,FinalFun}.

analyse(Cfg, Data={MFA,_,_,_}) ->
  try 
    State = state__init(Cfg,Data),
    Work = init_work(State),
    NewState = analyse_blocks(State,Work,false),
    (state__resultaction(NewState))(MFA,state__ret_type(NewState)),
    NewState
  catch throw:no_input -> ok
  end.

rewrite_blocks(State) ->
  Cfg = state__cfg(State),
  Start = hipe_icode_cfg:start_label(Cfg),
  rewrite_blocks([Start], State, [Start]).

rewrite_blocks([Next|Rest], State, Visited) ->
  Info = state__info_in(State, Next),
  {NewState, NewLabels} = analyse_block(Next, Info, State, true),
  NewLabelsSet = ordsets:from_list(NewLabels),
  RealNew = ordsets:subtract(NewLabelsSet, Visited),
  NewVisited = ordsets:union([RealNew,Visited,[Next]]),
  NewWork = ordsets:union([RealNew,Rest]),
  rewrite_blocks(NewWork, NewState, NewVisited);
rewrite_blocks([], State, _) ->
  State.

analyse_blocks(State, Work, Rewrite) ->
  case get_work(Work) of
    fixpoint ->
      State;
    {Label, NewWork} ->
      Info = state__info_in(State, Label),
      %%if Label == 20 -> io:format("Infoin: ~p~n", [gb_trees:to_list(Info)]); true -> ok end,
      {NewState, NewLabels}  = 
	try analyse_block(Label, Info, State, Rewrite)
	catch throw:none_range ->
	    {State,[]}
	end,
      NewWork2 = add_work(NewWork, NewLabels),
      analyse_blocks(NewState, NewWork2, Rewrite)
  end.

analyse_block(Label, Info, State, Rewrite) ->
  case state__bb(State, Label) of
    not_found ->
      io:format("Unknown Label: ~w~n", [Label]),
      {State,[]};
    BB ->
      Code = hipe_bb:code(BB),
      {NewCode, InfoList, RetType} = 
	analyse_BB(Code,Info,[],Rewrite,state__lookupfun(State)),
      State1 = state__bb_add(State, Label, hipe_bb:mk_bb(NewCode)),
      State2 = state__ret_type_update(State1, RetType),
      state__update_info(State2, InfoList, Rewrite)
  end.

analyse_BB([Last], Info, Code, Rewrite, LookupFun) ->
  %%io:format("I: ~w~n",[Last]),
  {{NewI,InfoList},RetType} = analyse_last_insn(Last, Info, Rewrite, LookupFun),
  {lists:reverse([NewI|Code]), InfoList, RetType};
analyse_BB([Insn|InsnList], Info, Code, Rewrite, LookupFun) ->
  {NewInfo,NewI} = analyse_insn(Insn, Info, LookupFun), 
  analyse_BB(InsnList, NewInfo, [NewI|Code], Rewrite, LookupFun).

analyse_insn(I, Info, LookupFun) ->
  %%io:format("~w Info: ~p~n",[I,Info]),
  NewI = handle_args(I,Info),
  FinalI = 
    case NewI of 
      #call{} -> analyse_call(NewI, LookupFun);
      #move{} -> analyse_move(NewI);
      #phi{} -> analyse_phi(NewI);
      #fmove{} -> analyse_fmove(NewI);
      #begin_handler{} -> analyse_begin_handler(NewI)
    end,
  {enter_vals(FinalI,Info), FinalI}.

handle_args(I, Info) ->
  WidenFun = fun update_three/3,
  handle_args(I, Info, WidenFun).

handle_args(I, Info, WidenFun) ->
  Uses = hipe_icode:uses(I),
  PresentRanges = [lookup(V,Info) || V <- Uses],
  %%io:format("Uses: ~p~nRanges: ~p~n",[Uses,PresentRanges]),
  JoinFun = fun(Var, Range) -> update_info(Var, Range, WidenFun) end,
  NewUses = lists:zipwith(JoinFun, Uses, PresentRanges),
  hipe_icode:subst_uses(lists:zip(Uses, NewUses),I).

join_info(Ann = #ann{range=R1,type=Type,count=?WIDEN}, R2, Fun)  ->
  Ann#ann{range = Fun(R1,R2,range_from_type(Type))};
join_info(Ann = #ann{range=R1,type=Type,count=C}, R2, _Fun) when C < ?WIDEN -> 
  case join_three(R1, R2, range_from_type(Type)) of
    R1 -> Ann;
    NewR -> Ann#ann{range = NewR, count=C+1}
  end.

join_three(R1,R2,R3) ->
  inf(sup(R1,R2),R3).

update_info(Var, Range) ->
  update_info(Var, Range, fun update_three/3).

update_info({var,Name,Ann}, R, Fun) ->
  {var,Name,update_info1(Ann,R,Fun)};
update_info({reg,Name}, _R, _) ->
  {reg,Name};
update_info({fvar,Name}, _R, _) ->
  {fvar,Name}.

update_info1(Ann = #ann{range=R1,type=Type,count=?WIDEN}, R2, Fun)  ->
  Ann#ann{range = Fun(R1,R2,range_from_type(Type))};
update_info1(Ann = #ann{range=R1,type=Type,count=C}, R2, _Fun) -> 
  case update_three(R1, R2, range_from_type(Type)) of
    R1 -> Ann;
    NewR -> Ann#ann{range = NewR, count=C+1}
  end;
update_info1(Type,R2, _Fun) ->
  #ann{range = inf(range_from_type(Type),R2), type = Type, count=1}.

update_three(_R1,R2,R3) ->
  inf(R2,R3).

safe_widen(#range{range=Old},#range{range=New},T = #range{range=Wide}) ->
  ResRange = 
    case {Old,New,Wide} of
      {{Min,Max1},{Min,Max2},{_,Max}} ->
	case inf_geq(OMax = next_up_limit(inf_max([Max1,Max2])),Max) of
	  true -> {Min,Max};
	  false -> {Min,OMax}
	end;
      {{Min1,Max},{Min2,Max},{Min,_}} ->
	case inf_geq(Min, OMin = next_down_limit(inf_min([Min1,Min2]))) of
	  true -> {Min,Max};
	  false -> {OMin,Max}
	end;
      {{Min1,Max1},{Min2,Max2},{Min,Max}} -> 
	RealMax =
	  case inf_geq(OMax = next_up_limit(inf_max([Max1,Max2])),Max) of
	    true -> Max;
	    false -> OMax
	  end,
	RealMin = 
	  case inf_geq(Min, OMin = next_down_limit(inf_min([Min1,Min2]))) of
	    true -> Min;
	    false -> OMin
	  end,
	{RealMin,RealMax};
      _ ->
	Wide
    end,
  T#range{range=ResRange}.

widen(#range{range=Old},#range{range=New},T = #range{range=Wide}) ->
  ResRange = 
    case {Old,New,Wide} of
      {{Min,_},{Min,Max2},{_,Max}} ->
	case inf_geq(OMax = next_up_limit(Max2),Max) of
	  true -> {Min,Max};
	  false -> {Min,OMax}
	end;
      {{_,Max},{Min2,Max},{Min,_}} ->
	case inf_geq(Min, OMin = next_down_limit(Min2)) of
	  true -> {Min,Max};
	  false -> {OMin,Max}
	end;
      {_,{Min2,Max2},{Min,Max}} -> 
	RealMax =
	  case inf_geq(OMax = next_up_limit(Max2),Max) of
	    true -> Max;
	    false -> OMax
	  end,
	RealMin = 
	  case inf_geq(Min, OMin = next_down_limit(Min2)) of
	    true -> Min;
	    false -> OMin
	  end,
	{RealMin,RealMax};
      _ ->
	Wide
    end,
  T#range{range=ResRange}.
	
analyse_call(Call, LookupFun) ->
  Args = hipe_icode:args(Call),
  Dsts = hipe_icode:call_dstlist(Call),
  Fun = hipe_icode:call_fun(Call),
  Type = hipe_icode:call_type(Call),
  DstRange = analyse_call_or_enter_fun(Fun, Args, Type, LookupFun),
  NewDefs = [update_info(Var,DstRange) || Var <- Dsts],
  hipe_icode:subst_defines(lists:zip(Dsts,NewDefs),Call).

analyse_fmove(FMove) ->
  Dst = hipe_icode:fmove_dst(FMove),
  DstRange = none_range(),
  NewDst = update_info(Dst,DstRange),
  hipe_icode:subst_defines([{Dst,NewDst}],FMove).

analyse_move(Move) ->
  Src = hipe_icode:move_src(Move),
  Dst = hipe_icode:move_dst(Move),
  Range = get_range_from_arg(Src),
  NewDst = update_info(Dst,Range),  
  hipe_icode:subst_defines([{Dst,NewDst}],Move).

analyse_begin_handler(Handler) ->
  SubstList =
    [{Dst,update_info(Dst,any_type())} || 
      Dst <- hipe_icode:begin_handler_dstlist(Handler)],
  hipe_icode:subst_defines(SubstList,Handler).
    
analyse_phi(Phi) ->
  {_, Args} = lists:unzip(hipe_icode:phi_arglist(Phi)),
  Dst = hipe_icode:phi_dst(Phi),
  Arg_ranges = get_range_from_args(Args),
  %%%%io:format("Phi-Arg_ranges: ~p ~n", [Arg_ranges]),
  DstRange = sup(Arg_ranges),
  NewDst = update_info(Dst,DstRange,fun widen/3),  
  hipe_icode:subst_defines([{Dst,NewDst}],Phi).

analyse_last_insn(I, Info, Rewrite, LookupFun) ->
  %%io:format("~w Info: ~p~n",[I,Info]),
  NewI = handle_args(I,Info),
  %%io:format("~w -> ~w~n",[NewI,I]),
  case NewI of 
    #return{} -> analyse_return(NewI, Info);
    #enter{} -> analyse_enter(NewI, Info, LookupFun);
    #switch_val{} -> {analyse_switch_val(NewI, Info, Rewrite),[none_type()]};
    #'if'{} -> {analyse_if(NewI, Info, Rewrite),[none_type()]};
    #goto{} -> {analyse_goto(NewI, Info),[none_type()]};	
    #type{} -> {analyse_type(NewI, Info, Rewrite),[none_type()]};
    #fail{} -> {analyse_fail(NewI, Info),[none_type()]};
    #call{} -> {analyse_last_call(NewI, Info, LookupFun),[none_type()]};
    #switch_tuple_arity{} -> 
      {analyse_switch_tuple_arity(NewI, Info),[none_type()]};
    #begin_try{} -> {analyse_begin_try(NewI, Info),[none_type()]}
  end.

analyse_return(Insn, _Info) ->
  RetRange = get_range_from_args(hipe_icode:return_vars(Insn)),
  {{Insn,[]},RetRange}.
  
analyse_enter(Insn, _Info, LookupFun) ->
  Args = hipe_icode:args(Insn),
  Fun = hipe_icode:enter_fun(Insn),
  CallType = hipe_icode:enter_type(Insn),
  RetRange = analyse_call_or_enter_fun(Fun,Args,CallType,LookupFun),
  {{Insn,[]},[RetRange]}.

analyse_switch_val(Switch, Info, Rewrite) -> 
  Arg = hipe_icode:switch_val_arg(Switch),
  SwitchRange = get_range_from_arg(Arg),
  Cases = hipe_icode:switch_val_cases(Switch), 
  {FailRange, LabelRangeList} = get_range_label_list(Cases, SwitchRange, []),
  case range__is_none(FailRange) of
    true -> 
      InfoList = update_infos(Arg, Info, LabelRangeList),
      if Rewrite -> {update_switch(Switch,LabelRangeList,false),InfoList};
	 true -> {Switch,InfoList}
      end;
    false ->
      FailLabel = hipe_icode:switch_val_fail_label(Switch),
      InfoList = update_infos(Arg, Info, [{FailRange, FailLabel}|LabelRangeList]),
      if Rewrite -> {update_switch(Switch,LabelRangeList,true),
		     InfoList};
	 true -> {Switch,InfoList}
      end
  end.

update_infos(Arg, Info, [{Range, Label}|Rest]) ->
  [{Label,enter_define({Arg,Range},Info)} | update_infos(Arg,Info,Rest)];
update_infos(_, _, []) -> [].

get_range_label_list([{Val,Label}|Cases],SRange,Acc) ->
  VRange = get_range_from_arg(Val),
  None = none_type(),
  case inf(SRange, VRange) of
    None ->
      get_range_label_list(Cases, SRange, Acc);
    ResRange ->
      get_range_label_list(Cases, SRange, [{ResRange,Label}|Acc])
  end;
get_range_label_list([], SRange, Acc) ->
  {PointTypes, _} = lists:unzip(Acc),
  {remove_point_types(SRange, PointTypes), Acc}.

update_switch(Switch, LabelRangeList, KeepFail) ->
  S2 = 
    case label_range_list_to_cases(LabelRangeList,[]) of
      no_update ->
	Switch;
      Cases -> 
	hipe_icode:switch_val_cases_update(Switch, Cases)
    end,
  if KeepFail -> S2;
     true -> S2
  end.


label_range_list_to_cases([{#range{range={C,C},other=false},Label}|Rest],
			  Acc) when is_integer(C) -> 
  label_range_list_to_cases(Rest,[{hipe_icode:mk_const(C),Label}|Acc]);
label_range_list_to_cases([{_NotAConstantRange,_Label}|_Rest],_Acc) ->
  no_update;
label_range_list_to_cases([],Acc) ->
  lists:reverse(Acc).
  
analyse_switch_tuple_arity(Switch, Info) -> 
  Arg = hipe_icode:switch_tuple_arity_arg(Switch),
  NewInfo = enter_define({Arg,get_range_from_arg(Arg)},Info),
  Cases = hipe_icode:switch_tuple_arity_cases(Switch),
  Fail = hipe_icode:switch_tuple_arity_fail_label(Switch),
  {_, Case_labels} = lists:unzip(Cases),
  Labels = [Fail|Case_labels],
  {Switch,[{Label,NewInfo} || Label <- Labels]}.

analyse_goto(Insn, Info) ->
  GotoLabel = hipe_icode:goto_label(Insn),
  {Insn,[{GotoLabel,Info}]}.