hipe_icode_range.erl

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

analyse_fail(Fail, Info) ->
  case hipe_icode:fail_label(Fail) of
    [] -> {Fail,[]};
    Label -> {Fail,[{Label,Info}]}
  end.

analyse_begin_try(Insn, Info) ->
  Label = hipe_icode:begin_try_label(Insn),
  Successor = hipe_icode:begin_try_successor(Insn),
  {Insn,[{Label,Info},{Successor,Info}]}.

analyse_last_call(Call, Info, LookupFun) ->
  %% hipe_icode_pp:pp_block([Insn]),
  NewI = analyse_call(Call, LookupFun),
  Continuation = hipe_icode:call_continuation(Call),
  NewInfo = enter_vals(NewI,Info),
  case hipe_icode:call_fail_label(Call) of
    [] -> 
      {NewI,[{Continuation,NewInfo}]};
    Fail ->
      {NewI,[{Continuation,NewInfo},{Fail,Info}]}
  end.

analyse_if(If, Info, Rewrite) ->
  case hipe_icode:if_args(If) of
    Args = [_,_] ->
      analyse_sane_if(If, Info, Args, get_range_from_args(Args), Rewrite);
    _ ->
      TrueLabel = hipe_icode:if_true_label(If),
      FalseLabel = hipe_icode:if_false_label(If),
      {If,[{TrueLabel,Info},{FalseLabel,Info}]}
  end.

analyse_sane_if(If, Info, [Arg1, Arg2], [Range1, Range2], Rewrite) ->
  case normalize_name(hipe_icode:if_op(If)) of
    '>' ->
      {TrueRange2, TrueRange1, FalseRange2, FalseRange1} = 
	range_inequality_propagation(Range2, Range1);
    '==' -> 
      {TempTrueRange1, TempTrueRange2, FalseRange1, FalseRange2}=
	range_equality_propagation(Range1, Range2),
      TrueRange1 = set_other(TempTrueRange1,other(Range1)),
      TrueRange2 = set_other(TempTrueRange2,other(Range2));
    '<' ->
      {TrueRange1, TrueRange2, FalseRange1, FalseRange2} = 
	range_inequality_propagation(Range1, Range2);
    '>=' ->
      {FalseRange1, FalseRange2, TrueRange1, TrueRange2} =
	range_inequality_propagation(Range1, Range2);
    '=<' ->
      {FalseRange2, FalseRange1, TrueRange2, TrueRange1} = 
	range_inequality_propagation(Range2, Range1);
    '=:=' ->
      {TrueRange1, TrueRange2, FalseRange1, FalseRange2}=
	range_equality_propagation(Range1, Range2);
    '=/=' ->
      {FalseRange1, FalseRange2, TrueRange1, TrueRange2} =
	range_equality_propagation(Range1, Range2);
    '/=' -> 
      {TempFalseRange1, TempFalseRange2, TrueRange1, TrueRange2}=
	range_equality_propagation(Range1, Range2),
      FalseRange1 = set_other(TempFalseRange1,other(Range1)),
      FalseRange2 = set_other(TempFalseRange2,other(Range2))
  end,
  TrueLabel = hipe_icode:if_true_label(If),
  FalseLabel = hipe_icode:if_false_label(If),
  TrueInfo = 
    enter_defines([{Arg1,TrueRange1}, {Arg2,TrueRange2}],Info),
  FalseInfo = 
    enter_defines([{Arg1,FalseRange1}, {Arg2,FalseRange2}],Info),
  True = 
    case lists:any(fun range__is_none/1,[TrueRange1,TrueRange2]) of
      true -> [];
      false -> [{TrueLabel,TrueInfo}]
    end,
  False = 
    case lists:any(fun range__is_none/1, [FalseRange1,FalseRange2]) of
      true -> [];
      false -> [{FalseLabel,FalseInfo}]
    end,
  UpdateInfo = True++False,
  NewIF =
    if Rewrite ->
	%%io:format("~w~n~w~n",[{Arg1,FalseRange1},{Arg2,FalseRange2}]),
	%%io:format("Any none: ~w~n", [lists:any(fun range__is_none/1,[FalseRange1,FalseRange2])]),
	case UpdateInfo of
	  [] -> %%This is weird
	    If;
	  [{Label,_Info}] ->
	    hipe_icode:mk_goto(Label);
	  [_,_] ->
	    If
	end;
       true ->
	If
    end,
  {NewIF, UpdateInfo}.

normalize_name(Name) ->
  case Name of
    'fixnum_eq'  -> '=:='; 
    'fixnum_neq' ->   '=/=';
    'fixnum_gt'  ->  '>' ;
    'fixnum_lt' ->  '<' ;
    'fixnum_ge' ->  '>=';
    'fixnum_le' -> '=<';
    Name -> Name
  end.

range_equality_propagation(Range_1, Range_2) ->  
  True_range = inf(Range_1, Range_2),
  case {range(Range_1) ,range(Range_2)} of
    {{N,N},{N,N}} ->
      False_range_1 = none_range(),
      False_range_2 = none_range();
    {{N1,N1},{N2,N2}} ->
      False_range_1 = Range_1,
      False_range_2 = Range_2;
    {{N,N},_} ->
      False_range_1 = Range_1,
      {_,False_range_2} = compare_with_integer(N, Range_2);
    {_,{N,N}} ->
      False_range_2 = Range_2,
      {_,False_range_1} = compare_with_integer(N, Range_1);
    {_,_} ->
      False_range_1 = Range_1,
      False_range_2 = Range_2
  end,
  {True_range, True_range, False_range_1, False_range_2}.

%% Range1 < Range2
range_inequality_propagation(Range1, Range2) ->
  R1_other = other(Range1),
  R2_other = other(Range2),
  {R1_true_range, R1_false_range, R2_true_range, R2_false_range} =
    case {range(Range1),range(Range2)} of
      {{N1,N1},{N2,N2}} ->
	case inf_geq(N2,inf_add(N1,1)) of
	  true ->
	    {{N1,N1},empty,{N2,N2},empty};
	  false ->
	    {empty,{N1,N1},empty,{N2,N2}}
	  end;
      {{N1,N1},{Min2,Max2}} ->
	case inf_geq(Min2,inf_add(N1,1)) of
	  true ->
	    {{N1,N1},empty,{inf_add(N1,1),Max2},empty};
	  false ->
	    case inf_geq(N1,Max2) of
	      true ->
		{empty,{N1,N1},empty,{Min2,N1}};
	      false ->
		{{N1,N1},{N1,N1},{inf_add(N1,1),Max2},{Min2,N1}}
	    end
	end;
      {{Min1,Max1},{N2,N2}} ->
	case inf_geq(N2,inf_add(Max1,1)) of
	  true ->
	  {{Min1,inf_add(N2,-1)},empty,{N2,N2},empty};
	  false ->
	    case inf_geq(Min1,N2) of
	      true ->
		{empty,{N2,Max1},empty,{N2,N2}};
	      false ->
		{{Min1,inf_add(N2,-1)},{N2,Max1},{N2,N2},{N2,N2}}
	    end
	end;
      {empty,{Min2,Max2}} ->
	{empty,empty,{Min2,Max2},{Min2,Max2}};
      {{Min1,Max1},empty} ->
	{{Min1,Max1},{Min1,Max1},empty,empty};
      {empty,empty} ->
	{empty,empty,empty,empty};
      {{Min1,Max1},{Min2,Max2}} ->
	{{Min1,inf_min([Max1,inf_add(Max2,-1)])},
	 {inf_max([Min1,Min2]),Max1},
	 {inf_max([inf_add(Min1,1),Min2]),Max2},
	 {Min2,inf_min([Max1,Max2])}}
    end,
  {range_init(R1_true_range, R1_other),
   range_init(R2_true_range, R2_other),
   range_init(R1_false_range, R1_other),
   range_init(R2_false_range, R2_other)}.

analyse_type(Type, Info, Rewrite) ->
  Type_type = hipe_icode:type_type(Type),
  [Arg|_] = hipe_icode:type_args(Type),
  OldVarRange = get_range_from_arg(Arg),
  case Type_type of
    {integer, N} ->
      {TrueRange,FalseRange} = compare_with_integer(N,OldVarRange);
    integer ->
      TrueRange = inf(any_range(),OldVarRange),
      FalseRange = inf(none_range(),OldVarRange);
    _ ->
      TrueRange = inf(none_range(),OldVarRange),
      FalseRange = OldVarRange
  end,
  TrueLabel = hipe_icode:type_true_label(Type),
  FalseLabel = hipe_icode:type_false_label(Type),
  TrueInfo = 
    enter_define({Arg,TrueRange},Info),
  FalseInfo = 
    enter_define({Arg,FalseRange},Info),
  True = 
    case range__is_none(TrueRange) of
      true -> [];
      false -> [{TrueLabel,TrueInfo}]
    end,
  False = 
    case range__is_none(FalseRange) of
      true -> [];
      false -> [{FalseLabel,FalseInfo}]
    end,
  UpdateInfo = True++False,
  NewType =
    if Rewrite ->
	case UpdateInfo of
	  [] -> %%This is weird
	    Type;
	  [{Label,_Info}] ->
	    hipe_icode:mk_goto(Label);
	  [_,_] ->
	    Type
	end;
       true ->
	Type
    end,
  {NewType,True ++ False}.

compare_with_integer(N, OldVarRange) ->
  TestRange = range_init({N, N}, false),
  TrueRange = inf(TestRange,OldVarRange),
  %% False range
  TempFalseRange = 
    range__remove_constant(OldVarRange,TestRange),
  BetterRange = 
    case range(TempFalseRange) of
      {Min, Max} ->
	New_small = inf_geq(Min, N),
	New_large = inf_geq(N, Max),
	if New_small and not New_large ->
	    {N + 1, Max};
	   New_large and not New_small ->
	    {Min, N - 1};
	   true -> 
	    {Min, Max}
	end;
      Not_tuple ->
	Not_tuple
    end,
  FalseRange = range_init(BetterRange, other(TempFalseRange)),
  {TrueRange,FalseRange}.

%%== Ranges ==================================================================

pp_ann(#ann{range=#range{range=R,other=false}}) ->
  pp_range(R);
pp_ann(#ann{range=#range{range=empty,other=true},type=Type}) ->
  t_to_string(Type);
pp_ann(#ann{range=#range{range=R,other=true},type=Type}) ->
  pp_range(R) ++ " | " ++ t_to_string(Type);
pp_ann(Type) ->
  t_to_string(Type).

pp_range(empty) ->
  "none";

pp_range({Min,Max}) ->
  val_to_string(Min) ++ ".." ++ val_to_string(Max).

val_to_string(pos_inf) -> "inf";
val_to_string(neg_inf) -> "-inf";
val_to_string(X) when is_integer(X) -> integer_to_list(X).

range_from_type(Type) ->
  None = t_none(),
  case t_inf(t_integer(),Type) of
    None ->
      #range{range=empty,other=true};
    Type ->
      Range = {number_min(Type),number_max(Type)},
      #range{range=Range,other=false};
    NewType ->
      Range = {number_min(NewType),number_max(NewType)},
      #range{range=Range,other=true}
  end.

range_init({Min,Max},Other) ->
  case inf_geq(Max,Min) of
    true ->
      #range{range={Min,Max},other=Other};
    false ->
      #range{range=empty,other=Other}
  end;
range_init(empty,Other) ->
  #range{range=empty,other=Other}.

range(#range{range=R}) -> R.

other(#range{other=O}) -> O.

set_other(R,O) -> R#range{other=O}.

range__min(#range{range=empty}) -> empty;
range__min(#range{range={Min,_}}) -> Min.

range__max(#range{range=empty}) -> empty;
range__max(#range{range={_,Max}}) -> Max.

range__is_none(#range{range=empty, other=false}) -> true;
range__is_none(#range{}) -> false.

range__is_empty(#range{range=empty}) -> true;
range__is_empty(#range{range={_,_}}) -> false.

remove_point_types(Range, Ranges) ->
  Sorted = lists:sort(Ranges),
  FoldFun = fun(R,Acc) -> range__remove_constant(Acc,R) end,
  Range1 = lists:foldl(FoldFun,Range,Sorted),
  lists:foldl(FoldFun,Range1,lists:reverse(Sorted)).

range__remove_constant(R = #range{range={C,C}}, #range{range={C,C}}) ->
  R#range{range=empty};
range__remove_constant(R = #range{range={C,H}}, #range{range={C,C}}) ->
  R#range{range={C+1,H}};
range__remove_constant(R = #range{range={L,C}}, #range{range={C,C}}) ->
  R#range{range={L,C-1}};
range__remove_constant(R = #range{}, #range{range={C,C}}) ->
  R;
range__remove_constant(R, _) ->
  R.

%% type_from_range(#range{range={Low,High},other=false}) ->
%%   t_from_range(Low,High);
%% type_from_range(#range{}) ->
%%   t_any().

any_type() ->
  #range{range=any_r(), other=true}.

any_range() ->
  #range{range=any_r(), other=false}.

none_range() ->
  #range{range=empty, other=true}.

none_type() ->
  #range{range=empty, other=false}.

any_r() -> {neg_inf,pos_inf}.
  
get_range_from_args(Args) ->
  [get_range_from_arg(Arg) || Arg <- Args].

get_range_from_arg(Arg) ->
  case hipe_icode:is_const(Arg) of
    true ->
      Value = hipe_icode:const_value(Arg),
      case is_integer(Value) of
	true ->
	  #range{range={Value,Value},other=false};
	false ->
	  #range{range=empty,other=true}
      end;
    false ->
      case Arg of
	{var,_,#ann{range=Range}} ->
	  Range;
	{var,_,Type} ->
	  range_from_type(Type);
	_ ->
	  any_type()
      end
  end.

%% inf([R]) ->
%%   R;
%% inf([R1,R2|Rest]) ->
%%   inf([inf(R1,R2)|Rest]).

inf(#range{range=R1,other=O1}, #range{range=R2,other=O2}) -> 
  #range{range=range_inf(R1,R2),other=other_inf(O1,O2)}.

range_inf(empty, _) -> empty;
range_inf(_, empty) -> empty;
range_inf({Min1,Max1}, {Min2,Max2}) ->
  NewMin = inf_max([Min1,Min2]),
  NewMax = inf_min([Max1,Max2]),
  case inf_geq(NewMax,NewMin) of
    true ->
      {NewMin,NewMax};
    false ->
      empty
  end.

other_inf(O1,O2) -> O1 and O2.

sup([R]) ->
  R;
sup([R1,R2|Rest]) ->
  sup([sup(R1,R2)|Rest]).

sup(#range{range=R1,other=O1}, #range{range=R2,other=O2}) -> 
  #range{range=range_sup(R1,R2),other=other_sup(O1,O2)}.

range_sup(empty, R) -> R;
range_sup(R, empty) -> R;
range_sup({Min1,Max1}, {Min2,Max2}) ->
  NewMin = inf_min([Min1,Min2]),