hipe_icode_range.erl

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

      {plus_plus,   plus_plus} ->
	Width = inf_max([Width1, Width2]),
	{0, inf_add(-1,inf_bsl(1, Width))}
    end,
  range_init(Range, false).  

%%---------------------------------------------------------------------------
%% Inf operations
%%---------------------------------------------------------------------------

inf_max([]) -> empty;
inf_max([H|T])->
  if H =:= empty ->
      inf_max(T);
     true ->
      lists:foldl(fun(Elem, Max) ->
			  Geq = inf_geq(Elem, Max),
			  if not Geq or (Elem =:= empty) ->
				  Max;
			     true ->
				  Elem
			  end
		  end,
		  H,
		  T)
  end.

inf_min([]) -> empty;
inf_min([H|T])->
  if H =:= empty ->
      inf_min(T);
     true ->
      lists:foldl(fun(Elem, Min) ->
		      Geq = inf_geq(Elem, Min),
		      if Geq or (Elem =:= empty) ->
			  Min;
			 true ->
			  Elem
		      end
		  end,
		  H,
		  T)
  end. 

inf_abs(pos_inf) -> pos_inf;
inf_abs(neg_inf) -> pos_inf;
inf_abs(Number) when is_integer(Number), (Number < 0) -> - Number;
inf_abs(Number) when is_integer(Number) -> Number.

inf_add(pos_inf, _Number) -> pos_inf;
inf_add(neg_inf, _Number) -> neg_inf;
inf_add(_Number, pos_inf) -> pos_inf;
inf_add(_Number, neg_inf) -> neg_inf;
inf_add(Number1, Number2) when is_integer(Number1), is_integer(Number2) ->
  Number1 + Number2.

inf_inv(pos_inf) -> neg_inf;
inf_inv(neg_inf) -> pos_inf;
inf_inv(Number) -> -Number.

inf_geq(pos_inf, _) -> true;
inf_geq(_, pos_inf) -> false;
inf_geq(_, neg_inf) -> true;
inf_geq(neg_inf, _) -> false;
inf_geq(A, B) -> A >= B.

inf_greater_zero(pos_inf) -> true;
inf_greater_zero(neg_inf) -> false;
inf_greater_zero(Number) when is_integer(Number), Number >= 0 -> true;
inf_greater_zero(Number) when is_integer(Number), Number < 0 -> false.

inf_div(Number, 0) ->
  Greater = inf_greater_zero(Number),
  if Greater -> pos_inf;
     true -> neg_inf
  end;
inf_div(pos_inf, Number) ->
  Greater = inf_greater_zero(Number),
  if Greater -> pos_inf;
     true -> neg_inf
  end;
inf_div(neg_inf, Number) ->
  Greater = inf_greater_zero(Number),
  if Greater -> neg_inf;
     true -> pos_inf
  end;
inf_div(Number, pos_inf) -> 
  Greater = inf_greater_zero(Number),
  if Greater -> pos_inf;
     true -> neg_inf
  end;
inf_div(Number, neg_inf) ->
  Greater = inf_greater_zero(Number),
  if Greater -> neg_inf;
     true -> pos_inf
  end;
inf_div(Number1, Number2) -> Number1 div Number2.

inf_mult(neg_inf, Number) -> 
  Greater = inf_greater_zero(Number), 
  if Greater -> neg_inf;
     true -> pos_inf
  end;
inf_mult(pos_inf, Number) -> 
  Greater = inf_greater_zero(Number),
  if Greater -> pos_inf;
     true -> neg_inf
  end;
inf_mult(Number, pos_inf) -> inf_mult(pos_inf, Number);
inf_mult(Number, neg_inf) -> inf_mult(neg_inf, Number);
inf_mult(Number1, Number2) -> Number1 * Number2.

inf_bsl(pos_inf, _) -> pos_inf;
inf_bsl(neg_inf, _) -> neg_inf;
inf_bsl(Number, pos_inf) when is_integer(Number), Number >= 0 -> pos_inf;
inf_bsl(_, pos_inf) -> neg_inf;
inf_bsl(Number, neg_inf) when is_integer(Number), Number >= 0 -> 0;
inf_bsl(_Number, neg_inf) -> -1;
inf_bsl(Number1, Number2) when is_integer(Number1), is_integer(Number2) ->
  %% We can not shift left with a number which is not a fixnum. We
  %% don't have enough memory.
  Bits = ?BITS,
  if Number2 > (Bits bsl 1) -> inf_bsl(Number1, pos_inf);
     Number2 < (-Bits bsl 1) ->	inf_bsl(Number1, neg_inf);
     true -> Number1 bsl Number2
  end.

%% State

-record(state, {info_map, counter=dict:new(), 
		cfg, liveness, ret_type, 
		lookupfun, resultaction}).

state__init(Cfg,{MFA,ArgsFun,CallFun,FinalFun}) ->
  Start = hipe_icode_cfg:start_label(Cfg),  
  Params = hipe_icode_cfg:params(Cfg),
  Ranges = ArgsFun(MFA,Cfg),
  %%io:format("MFA: ~w~nRanges: ~w~n",[MFA,Ranges]),
  Liveness = hipe_icode_ssa:ssa_liveness__analyze(
	       hipe_icode_type:unannotate_cfg(Cfg)),
  case lists:any(fun range__is_none/1, Ranges) of
    true -> 
      FinalFun(MFA,[none_type()]),
      throw(no_input);
    false ->
      NewParams = lists:zipwith(fun update_info/2, Params, Ranges),
      NewCfg = hipe_icode_cfg:params_update(Cfg, NewParams),
      Info = enter_defines(NewParams,gb_trees:empty()),
      InfoMap = gb_trees:insert({Start, in}, Info, gb_trees:empty()),
      #state{info_map=InfoMap, cfg=NewCfg, liveness=Liveness,
	     ret_type=[none_type()],
	     lookupfun=CallFun, resultaction=FinalFun}
  end.

state__cfg(#state{cfg=Cfg}) ->
  Cfg.

state__bb(#state{cfg=Cfg}, Label) ->
  hipe_icode_cfg:bb(Cfg, Label).
  
state__bb_add(S=#state{cfg=Cfg}, Label, BB) ->
  NewCfg = hipe_icode_cfg:bb_add(Cfg, Label, BB),
  S#state{cfg=NewCfg}.

state__lookupfun(#state{lookupfun = LF}) -> LF.

state__resultaction(#state{resultaction = RA}) -> RA.

state__ret_type(#state{ret_type = RT}) -> RT.

state__ret_type_update(#state{ret_type=RT} = State, NewType) ->
  TotType = lists:zipwith(fun sup/2, RT, NewType),
  State#state{ret_type=TotType}.

state__info_in(S, Label) ->
  state__info(S, {Label, in}).

state__info(#state{info_map=IM}, Key) ->
  gb_trees:get(Key,IM).

state__update_info(State,LabelInfo,Rewrite) ->
  update_info(LabelInfo,State,[],Rewrite).

update_info([{Label,InfoIn}|Rest],State,LabelAcc,Rewrite) ->
  case state__info_in_update(State, Label, InfoIn) of
    fixpoint ->
      if Rewrite ->
	  update_info(Rest,State,[Label|LabelAcc],Rewrite);
	 true ->
	  update_info(Rest,State,LabelAcc,Rewrite)
      end;
    NewState ->
      update_info(Rest,NewState,[Label|LabelAcc],Rewrite)
  end;
update_info([], State, LabelAcc,_Rewrite) ->
  {State, LabelAcc}.

state__info_in_update(S=#state{info_map=IM,liveness=Liveness}, Label, Info) ->
  case gb_trees:lookup({Label, in}, IM) of
    none -> 
      Pred = hipe_icode_cfg:pred(state__cfg(S), Label),
      RawLiveIn = [hipe_icode_ssa:ssa_liveness__livein(Liveness, Label, X) ||
		X <- Pred],
      LiveIn = ordsets:from_list(lists:flatten(RawLiveIn)),
      NamesLiveIn = [Name || {var,Name} <- LiveIn],
      OldInfo = gb_trees:empty(),
      case join_info_in(NamesLiveIn, OldInfo, Info) of
	fixpoint -> 
	  S#state{info_map=gb_trees:insert({Label,in},OldInfo,IM)};
	NewInfo ->
	  S#state{info_map=gb_trees:enter({Label, in},NewInfo,IM)}
      end;
    {value, OldInfo} ->
      OldVars = gb_trees:keys(OldInfo),
      case join_info_in(OldVars, OldInfo, Info) of
	fixpoint -> 
	  fixpoint;
	NewInfo ->
	  S#state{info_map=gb_trees:update({Label,in},NewInfo,IM)}
      end
  end.
	  
join_info_in(Vars, OldInfo, NewInfo) ->
  case join_info_in(Vars, OldInfo, NewInfo, gb_trees:empty(), false) of
    {Res, true} -> Res;
    {_, false} -> fixpoint
  end.
  
join_info_in([Var|Left], Info1, Info2, Acc, Changed) ->
  Type1 = gb_trees:lookup(Var, Info1),
  Type2 = gb_trees:lookup(Var, Info2),
  case {Type1, Type2} of
    {none, none} ->
      NewTree = gb_trees:insert(Var, none_type(), Acc),
      join_info_in(Left, Info1, Info2, NewTree, true);
    {none, {value, Val}} ->
      NewTree = gb_trees:insert(Var, Val, Acc),
      join_info_in(Left, Info1, Info2, NewTree, true);
    {{value, Val}, none} ->
      NewTree = gb_trees:insert(Var, Val, Acc),
      join_info_in(Left, Info1, Info2, NewTree, Changed);
    {{value, Val}, {value, Val}} ->
      NewTree = gb_trees:insert(Var, Val, Acc),
      join_info_in(Left, Info1, Info2, NewTree, Changed);
    {{value, Val1}, {value, Val2}} ->
      NewVal = 
	case sup(Val1,Val2) of
	  Val1 -> 
	    NewChanged = Changed,
	    Val1;
	  Val ->
	    NewChanged = true,
	    Val
	end,
      NewTree = gb_trees:insert(Var, NewVal, Acc),
      join_info_in(Left, Info1, Info2, NewTree, NewChanged)
  end;
join_info_in([], _Info1, _Info2, Acc, NewChanged) ->
  {Acc, NewChanged}.

enter_defines([Def|Rest],Info) ->
  enter_defines(Rest,enter_define(Def,Info));
enter_defines([], Info) -> Info.

enter_define({{var,Name,_},Range}, Info) ->
  gb_trees:enter(Name,Range,Info);
enter_define({var,Name,#ann{range=Range}}, Info) ->
  gb_trees:enter(Name,Range,Info);
enter_define(_, Info) -> Info.

enter_vals(Ins,Info) ->
  NewInfo = enter_defines(hipe_icode:args(Ins),Info),
  enter_defines(hipe_icode:defines(Ins),NewInfo).
  
lookup({var,Name,_},Info) ->
  case gb_trees:lookup(Name,Info) of
    none ->
      none_type();
    {value,Val} ->
      Val
  end;
lookup({reg,_},_Info) ->
  any_type();
lookup({fvar,_},_Info) ->
  none_range().

%% _________________________________________________________________
%%
%% The worklist.
%%

init_work(State) ->
  %%Labels = hipe_icode_cfg:reverse_postorder(state__cfg(State)),
  Labels = [hipe_icode_cfg:start_label(state__cfg(State))],
  {Labels, [], sets:from_list(Labels)}.

get_work({[Label|Left], List, Set}) ->
  NewWork = {Left, List, sets:del_element(Label, Set)},
  {Label, NewWork};
get_work({[], [], _Set}) ->
  fixpoint;
get_work({[], List, Set}) ->
  get_work({lists:reverse(List), [], Set}).

add_work(Work = {List1, List2, Set},[Label|Left]) ->
  case sets:is_element(Label, Set) of
    true ->
      add_work(Work, Left);
    false ->
      %%io:format("Adding work: ~w\n", [Label]),
      add_work({List1, [Label|List2], sets:add_element(Label, Set)}, Left)
  end;
add_work(Work, []) ->
  Work.

convert_cfg_to_types(Cfg) ->
  Lbls = hipe_icode_cfg:reverse_postorder(Cfg),
  lists:foldl(fun convert_lbl_to_type/2, Cfg, Lbls).

convert_lbl_to_type(Lbl,Cfg) -> 
  BB = hipe_icode_cfg:bb(Cfg, Lbl),
  Code = hipe_bb:code(BB),
  NewCode = [convert_instr_to_type(I) || I <- Code],
  hipe_icode_cfg:bb_add(Cfg,Lbl,hipe_bb:mk_bb(NewCode)).

convert_instr_to_type(I) ->
  Uses = hipe_icode:uses(I),
  UseSubstList = [{Use,{var,Name,convert_ann_to_types(Ann)}} ||
		   Use = {var,Name,Ann = #ann{}} <- Uses],
  NewI = hipe_icode:subst_uses(UseSubstList,I),
  Defs = hipe_icode:defines(NewI),
  DefSubstList = [{Def,{var,Name,convert_ann_to_types(Ann)}} ||
		   Def = {var,Name,Ann = #ann{}} <- Defs],
  hipe_icode:subst_defines(DefSubstList, NewI).

convert_ann_to_types(#ann{range=#range{range={Min,Max},other=false}}) ->
  t_from_range_unsafe(Min,Max);
convert_ann_to_types(#ann{range=#range{range=empty,other=false}}) ->
  t_none();
convert_ann_to_types(#ann{range=#range{other=true},type=Type}) ->
  Type.

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

replace_nones(Args) ->
  [replace_none(Arg) || Arg <- Args].

replace_none(Arg) ->
  case range__is_none(Arg) of
    true -> any_type();
    false -> Arg
  end.
      
update__info(NewRanges,OldRanges) ->
  SupFun = fun(Ann,Range) -> 
	       join_info(Ann, Range, fun safe_widen/3)
	   end,
  EqFun = fun(X,Y) -> X =:= Y end,
  ResRanges = lists:zipwith(SupFun,OldRanges,NewRanges),
  Change = lists:zipwith(EqFun,ResRanges,OldRanges),
  {lists:all(fun(X) -> X end, Change),ResRanges}.

new__info(NewRanges) ->
  [#ann{range=Range,count=1,type=t_any()} || Range <- NewRanges].

return__info(Ranges) ->
  [Range || #ann{range=Range} <- Ranges].

return_none() ->  
  [none_type()].

return_none_args(Cfg,{_M,_F,A}) ->
  NoArgs = 
    case hipe_icode_cfg:is_closure(Cfg) of
      true -> hipe_icode_cfg:closure_arity(Cfg)+1;
      false -> A
    end,
  lists:duplicate(NoArgs,none_type()).

return_any_args(Cfg,{_M,_F,A}) ->
  NoArgs = 
    case hipe_icode_cfg:is_closure(Cfg) of
      true -> hipe_icode_cfg:closure_arity(Cfg)+1;
      false -> A
    end,
  lists:duplicate(NoArgs,any_type()).

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

next_up_limit(X) when is_integer(X), X < 0 -> 0;
next_up_limit(X) when is_integer(X), X < 255 -> 255;
next_up_limit(X) when is_integer(X), X < 16#10ffff -> 16#10ffff;
next_up_limit(X) when is_integer(X), X < 16#7ffffff -> 16#7ffffff;
next_up_limit(X) when is_integer(X), X < 16#7fffffff -> 16#7fffffff;
next_up_limit(X) when is_integer(X), X < 16#ffffffff -> 16#ffffffff;
next_up_limit(X) when is_integer(X), X < 16#fffffffffff -> 16#fffffffffff;
next_up_limit(X) when is_integer(X), X < 16#7fffffffffffffff -> 16#7fffffffffffffff;
next_up_limit(_X) -> pos_inf.

next_down_limit(X) when is_integer(X), X > 0 -> 0;
next_down_limit(X) when is_integer(X), X > -256 -> -256;
next_down_limit(X) when is_integer(X), X > -16#10ffff -> -16#10ffff;
next_down_limit(X) when is_integer(X), X > -16#8000000 -> -16#8000000;
next_down_limit(X) when is_integer(X), X > -16#80000000 -> -16#80000000;
next_down_limit(X) when is_integer(X), X > -16#800000000000000 -> -16#800000000000000;
next_down_limit(_X) -> neg_inf.