hipe_icode_range.erl

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

  NewMax = inf_max([Max1,Max2]),
  {NewMin,NewMax}.

other_sup(O1, O2) -> O1 or O2.

%%== Call Support =============================================================

analyse_call_or_enter_fun(Fun, Args, CallType, LookupFun) ->
  case basic_type(Fun) of
    {bin, Operation} ->
      [Arg_range1,Arg_range2] = get_range_from_args(Args),
      A1_is_empty = range__is_empty(Arg_range1),
      A2_is_empty = range__is_empty(Arg_range2),
      if A1_is_empty or A2_is_empty ->
	  none_type();
	 true ->
	  Operation(Arg_range1, Arg_range2)
      end;
    {unary, Operation} ->
      [Arg_range] = get_range_from_args(Args),
      case range__is_empty(Arg_range) of
	true ->
	  none_type();
	false ->
	  Operation(Arg_range)
      end;
    {fcall, MFA} ->
      case CallType of
	local ->
	  [Range] = LookupFun(MFA, get_range_from_args(Args)),
	  case range__is_none(Range) of
	    true ->
	      throw(none_range);
	    false ->
	      Range
	  end;
	remote ->
	  any_type()
      end;
    not_int ->
      any_type();
    not_analysed -> 
      any_type();
    {hipe_bs_primop, {bs_get_integer, Size, Flags}} ->
      {Min, Max} = analyse_bs_get_integer_funs(Size, Flags, length(Args) =:= 1),
      #range{range={Min, Max}, other=false};
    {hipe_bs_primop, _} = Primop ->
      Type = hipe_icode_primops:type(Primop),
      range_from_type(Type)
  end.

%% Arithmetic operations
basic_type('+') -> {bin, fun(R1, R2) -> range_add(R1, R2) end};
basic_type('-') -> {bin, fun(R1, R2) -> range_sub(R1, R2) end};
basic_type('*') -> {bin, fun(R1, R2) -> range_mult(R1, R2) end};
basic_type('/') -> not_int;
basic_type('div') -> {bin, fun(R1, R2) -> range_div(R1, R2) end};
basic_type('rem') -> {bin, fun(R1, R2) -> range_rem(R1, R2) end};
basic_type('bor') -> {bin, fun(R1, R2) -> range_bor(R1, R2) end};
basic_type('band') -> {bin, fun(R1, R2) -> range_band(R1, R2) end};
basic_type('bxor') -> {bin, fun(R1, R2) -> range_bxor(R1, R2) end};
basic_type('bnot') -> {unary, fun(R1) -> range_bnot(R1) end};
basic_type('bsl') -> {bin, fun(R1, R2) -> range_bsl(R1, R2) end};
basic_type('bsr') -> {bin, fun(R1, R2) -> range_bsr(R1, R2) end};
%% unsafe_*
basic_type('unsafe_bor') ->  
  {bin, fun(R1, R2) -> range_bor(R1, R2) end};
basic_type('unsafe_band') ->
  {bin, fun(R1, R2) -> range_band(R1, R2) end};
basic_type('unsafe_bxor') ->
  {bin, fun(R1, R2) -> range_bxor(R1, R2) end};
basic_type('unsafe_bnot') ->
  {unary, fun(R1) -> range_bnot(R1) end};
basic_type('unsafe_bsl') ->
  {bin, fun(R1, R2) -> range_bsl(R1, R2) end};
basic_type('unsafe_bsr') ->
  {bin, fun(R1, R2) -> range_bsr(R1, R2) end};
basic_type('unsafe_add') ->
  {bin, fun(R1, R2) -> range_add(R1, R2) end};
basic_type('unsafe_sub') ->
  {bin, fun(R1, R2) -> range_sub(R1, R2) end};
basic_type('extra_unsafe_add') ->
  {bin, fun(R1, R2) -> range_add(R1, R2) end};
basic_type('extra_unsafe_sub') ->
  {bin, fun(R1, R2) -> range_sub(R1, R2) end};
%% Binaries
basic_type({hipe_bs_primop, Todo}) -> {hipe_bs_primop, Todo};
%% Unknown, other
basic_type(call_fun) -> not_analysed;
basic_type(clear_timeout) -> not_analysed;
basic_type(redtest) -> not_analysed;
basic_type(set_timeout) -> not_analysed;
basic_type(#apply_N{}) -> not_analysed;
basic_type(#closure_element{}) -> not_analysed; 
basic_type(#gc_test{}) -> not_analysed;
%% Message handling
basic_type(check_get_msg) -> not_analysed; 
basic_type(next_msg) -> not_analysed; 
basic_type(select_msg) -> not_analysed; 
basic_type(suspend_msg) -> not_analysed;
%% Functions
basic_type(enter_fun) -> not_analysed;
basic_type(#mkfun{}) -> not_int;
basic_type({M,F,A}) -> {fcall, {M,F,A}}; 
%% Floats
basic_type(conv_to_float) -> not_int;
basic_type(fclearerror) -> not_analysed;
basic_type(fcheckerror) -> not_analysed;
basic_type(fnegate) -> not_int;
basic_type(fp_add) -> not_int;
basic_type(fp_div) -> not_int;
basic_type(fp_mul) -> not_int;
basic_type(fp_sub) -> not_int;
basic_type(unsafe_tag_float) -> not_int;
basic_type(unsafe_untag_float) -> not_int;
%% Lists, tuples, records
basic_type(cons) -> not_int;
basic_type(mktuple) -> not_int;
basic_type(unsafe_hd) -> not_analysed;
basic_type(unsafe_tl) -> not_int;
basic_type(#element{}) -> not_analysed;
basic_type(#unsafe_element{}) -> not_analysed;
basic_type(#unsafe_update_element{}) -> not_analysed.

analyse_bs_get_integer_funs(Size, Flags, true) ->
  Signed = Flags band 4,
  if Signed =:= 0 ->
      Max = 1 bsl Size - 1,
      Min = 0;
     true ->
      Max = 1 bsl (Size-1) - 1,
      Min = -(1 bsl (Size-1))
  end,
  {Min, Max};
analyse_bs_get_integer_funs(_Size, _Flags, false) ->
  any_r().

%%---------------------------------------------------------------------------
%% Range operations
%%---------------------------------------------------------------------------

%% Arithmetic

range_add(Range1, Range2) ->
  NewMin = inf_add(range__min(Range1), range__min(Range2)),
  NewMax = inf_add(range__max(Range1), range__max(Range2)),
  Other = other(Range1) orelse other(Range2),
  range_init({NewMin, NewMax}, Other).

range_sub(Range1, Range2) ->
  Min_sub = inf_min([inf_inv(range__max(Range2)), 
		     inf_inv(range__min(Range2))]),
  Max_sub = inf_max([inf_inv(range__max(Range2)), 
		     inf_inv(range__min(Range2))]),
  NewMin = inf_add(range__min(Range1), Min_sub),
  NewMax = inf_add(range__max(Range1), Max_sub),
  Other = other(Range1) orelse other(Range2),
  range_init({NewMin, NewMax}, Other).

range_mult(#range{range = empty, other = true}, _Range2) ->
  range_init(empty, true); 
range_mult(_Range1, #range{range = empty, other = true}) ->
  range_init(empty, true); 
range_mult(Range1, Range2) ->
  Min1 = range__min(Range1),
  Min2 = range__min(Range2),
  Max1 = range__max(Range1),
  Max2 = range__max(Range2),
  GreaterMin1 = inf_greater_zero(Min1),
  GreaterMin2 = inf_greater_zero(Min2),
  GreaterMax1 = inf_greater_zero(Max1),
  GreaterMax2 = inf_greater_zero(Max2),
  Range = 
    if GreaterMin1 -> 
	if GreaterMin2 -> {inf_mult(Min1, Min2), inf_mult(Max1, Max2)};
	   GreaterMax2 -> {inf_mult(Min2, Max1), inf_mult(Max2, Max1)};
	   true        -> {inf_mult(Min2, Max1), inf_mult(Max2, Min1)}
	end;
       %% Kolumn 1 eller 2
       GreaterMin2 -> % Kolumn 1 eller 2 rad 3
	range(range_mult(Range2, Range1));
       GreaterMax1 -> %Kolumn 2 Rad 1 eller 2
	if GreaterMax2 -> % Kolumn 2 Rad 2
	    NewMin = inf_min([inf_mult(Min2, Max1), inf_mult(Max2, Min1)]),
	    NewMax = inf_max([inf_mult(Min2, Min1), inf_mult(Max2, Max1)]),
	    {NewMin, NewMax};
	   true -> % Kolumn 2 Rad 1
	    {inf_mult(Min2, Max1), inf_mult(Min2, Min1)}
	end;
       GreaterMax2 -> % Kolumn 1 Rad 2	
	range(range_mult(Range2, Range1));
       true -> % Kolumn 1 Rad 1 
	{inf_mult(Max1, Max2), inf_mult(Min2, Min1)}
    end,
  Other = other(Range1) orelse other(Range2),
  range_init(Range, Other).

extreme_divisors(#range{range={0,0}}) -> {0,0};
extreme_divisors(#range{range={0,Max}}) -> {1,Max};
extreme_divisors(#range{range={Min,0}}) -> {Min,-1};
extreme_divisors(#range{range={Min,Max}}) ->
  case inf_geq(Min, 0) of 
    true -> {Min, Max};
    false -> %Min < 0
      case inf_geq(0, Max) of
	true -> {Min,Max}; %Max < 0
	false -> {-1,1} %Max > 0
      end
  end.

%% this is div, not /.
range_div(_, #range{range={0,0}}) ->
  range_init(empty, false);
range_div(#range{range=empty}, _) ->
  range_init(empty, false);
range_div(_, #range{range=empty}) ->
  range_init(empty, false);
range_div(Range1, Den) ->
  Min1 = range__min(Range1),
  Max1 = range__max(Range1),
  {Min2, Max2} = extreme_divisors(Den),
  Min_max_list = [inf_div(Min1, Min2), inf_div(Min1, Max2),
		  inf_div(Max1, Min2), inf_div(Max1, Max2)],
  range_init({inf_min(Min_max_list), inf_max(Min_max_list)}, false).

range_rem(Range1, Range2) ->
  %% Range1 desides the sign of the answer.
  Min1 = range__min(Range1),
  Max1 = range__max(Range1),
  Min2 = range__min(Range2),
  Max2 = range__max(Range2),
  Min1_geq_zero = inf_geq(Min1, 0),
  Max1_leq_zero = inf_geq(0, Max1),
  Max_range2 = inf_max([inf_abs(Min2), inf_abs(Max2)]),
  Max_range2_leq_zero = inf_geq(0, Max_range2),
  New_min = 
    if Min1_geq_zero ->	0;
       Max_range2_leq_zero -> Max_range2;
       true -> inf_inv(Max_range2)
    end,
  New_max = 
    if Max1_leq_zero -> 0;
       Max_range2_leq_zero -> inf_inv(Max_range2);
       true -> Max_range2
    end,
  range_init({New_min, New_max}, false).

%%--- Bit operations ----------------------------

range_bsr(Range1, Range2=#range{range={Min, Max}}) -> 
  New_Range2 = range_init({inf_inv(Max), inf_inv(Min)}, other(Range2)), 
  Ans = range_bsl(Range1, New_Range2),
  %%io:format("bsr res:~w~nInput:= ~w~n",[Ans,{Range1,Range2}]),
  Ans.

range_bsl(Range1, Range2) ->
  Min1 = range__min(Range1),
  Min2 = range__min(Range2),
  Max1 = range__max(Range1),
  Max2 = range__max(Range2),
  Min1Geq0 = inf_geq(Min1, 0),
  Max1Less0 = not inf_geq(Max1, 0),
  {Min, Max} = 
    if Min1Geq0 ->
	{inf_bsl(Min1, Min2), inf_bsl(Max1, Max2)};
       true ->
	if Max1Less0 -> {inf_bsl(Min1, Max2), inf_bsl(Max1, Min2)};
	   true -> {inf_bsl(Min1, Max2), inf_bsl(Max1, Max2)}
	end
    end,
  range_init({Min, Max}, false).

range_bnot(Range) ->
  Minus_one = range_init({-1,-1}, false),
  range_add(range_mult(Range, Minus_one), Minus_one).

width({Min, Max}) -> inf_max([width(Min), width(Max)]);
width(pos_inf) -> pos_inf;
width(neg_inf) -> pos_inf;
width(X) when is_integer(X), X >= 0 -> poswidth(X, 0);
width(X) when is_integer(X), X < 0 -> negwidth(X, 0).

poswidth(X, N) ->
  case X < (1 bsl N) of
    true  -> N;
    false -> poswidth(X, N+1)
  end.

negwidth(X, N) ->
  case X > (-1 bsl N) of
    true  -> N;
    false -> negwidth(X, N+1)
  end.

range_band(R1, R2) ->
  {Min1, Max1} = range(R1),
  {Min2, Max2} = range(R2),
  Width1 = width({Min1, Max1}),
  Width2 = width({Min2, Max2}),
  Range = 
    case {classify_range(R1), classify_range(R2)} of
      {minus_minus, minus_minus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), -1};
      {minus_minus, minus_plus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), Max2};
      {minus_minus, plus_plus} ->
	{0, Max2};
      {minus_plus,  minus_minus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), Max1};
      {minus_plus,  minus_plus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), inf_max([Max1,Max2])};
      {minus_plus,  plus_plus} ->
	{0, Max2};
      {plus_plus,   minus_minus} ->
	{0, Max1};
      {plus_plus,   minus_plus} ->
	{0, Max1};
      {plus_plus,   plus_plus} ->
	{0, inf_min([Max1, Max2])}
    end,
  range_init(Range, false).  

range_bor(R1, R2) ->
  {Min1, Max1} = range(R1),
  {Min2, Max2} = range(R2),
  Width1 = width({Min1, Max1}),
  Width2 = width({Min2, Max2}),
  Range = 
    case {classify_range(R1), classify_range(R2)} of
      {minus_minus, minus_minus} ->
	{inf_max([Min1, Min2]), -1};
      {minus_minus, minus_plus} ->
	{Min1, -1};
      {minus_minus, plus_plus} ->
	{Min1, -1};
      {minus_plus,  minus_minus} ->
	{Min2, -1};
      {minus_plus,  minus_plus} ->
	Width = inf_max([Width1, Width2]),
	{inf_min([Min1, Min2]), inf_add(-1,inf_bsl(1, Width))};
      {minus_plus,  plus_plus} ->
	Width = inf_max([Width1, Width2]),
	{Min1, inf_add(-1,inf_bsl(1, Width))};
      {plus_plus,   minus_minus} ->
	{Min2, -1};
      {plus_plus,   minus_plus} ->
	Width = inf_max([Width1, Width2]),
	{Min2, inf_add(-1,inf_bsl(1, Width))};
      {plus_plus,   plus_plus} ->
	Width = inf_max([Width1, Width2]),
	{0, inf_add(-1,inf_bsl(1, Width))}
    end,
  range_init(Range, false).  

classify_range(Range) ->
  case range(Range) of
    {neg_inf, Number} when is_integer(Number), Number < 0 -> minus_minus;
    {neg_inf, Number} when is_integer(Number), Number >= 0 -> minus_plus;
    {Number, pos_inf} when is_integer(Number), Number < 0 -> minus_plus;
    {Number, pos_inf} when is_integer(Number), Number >= 0 -> plus_plus;
    {neg_inf, pos_inf} -> minus_plus;
    {Number1,Number2} when is_integer(Number1), is_integer(Number2) ->
      classify_int_range(Number1, Number2)
  end.

classify_int_range(Number1,_Number2) when Number1 >= 0 ->
  plus_plus;
classify_int_range(_Number1,Number2) when Number2 < 0 ->
  minus_minus;
classify_int_range(_Number1,_Number2) ->
  minus_plus.
       
range_bxor(R1, R2) ->
  {Min1, Max1} = range(R1),
  {Min2, Max2} = range(R2),
  Width1 = width({Min1, Max1}),
  Width2 = width({Min2, Max2}),
  Range = 
    case {classify_range(R1), classify_range(R2)} of
      {minus_minus, minus_minus} ->
	Width = inf_max([Width1, Width2]),
	{0, inf_add(-1,inf_bsl(1, Width))};
      {minus_minus, minus_plus} ->
	MinWidth = inf_max([Width1,width({0,Max2})]),
	MaxWidth = inf_max([Width1,width({Min2,-1})]),
	{inf_bsl(-1, MinWidth), inf_add(-1,inf_bsl(1, MaxWidth))};
      {minus_minus, plus_plus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), -1};
      {minus_plus,  minus_minus} ->
	MinWidth = inf_max([Width2,width({0,Max1})]),
	MaxWidth = inf_max([Width2,width({Min1,-1})]),
	{inf_bsl(-1, MinWidth), inf_add(-1,inf_bsl(1, MaxWidth))};
      {minus_plus,  minus_plus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), inf_add(-1,inf_bsl(1, Width))};
      {minus_plus,  plus_plus} ->
	MinWidth = inf_max([Width2,width({Min1,-1})]),
	MaxWidth = inf_max([Width2,width({0,Max1})]),
	{inf_bsl(-1, MinWidth), inf_add(-1,inf_bsl(1, MaxWidth))};
      {plus_plus,   minus_minus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), -1};
      {plus_plus,   minus_plus} ->
	MinWidth = inf_max([Width1,width({Min2,-1})]),
	MaxWidth = inf_max([Width1,width({0,Max2})]),
	{inf_bsl(-1, MinWidth), inf_add(-1,inf_bsl(1, MaxWidth))};