hipe_icode_range_an.erl

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

%% -*- erlang-indent-level: 2 -*-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% @doc	This module performs integer range analysis on ICode.
%%
%% <h3>Purpose</h3>
%%
%% <p>iterating, fixing and adding in a happily manner.</p>
%%
%% @end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

-module(hipe_icode_range_an).

-export([init/4]).
-export([to_string/1]).

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

-define(LABELITERATIONS, 10).
-define(PHIWIDENING, 4).
-define(FUNCTION_FIXPOINT_DEPTH, 5).

%%-define(not_done_debug, fun(X, Y) -> io:format(X, Y) end).
-define(not_done_debug, fun(_, _) -> ok end).

%% -define(MFA_debug, fun(MFA, X, Y) -> 
%%   		       if MFA =:= {epp,scan_toks,3} ->
%%   			   io:format("~s ~p~n", [X, Y]);
%%   			  true  ->
%%   			   ok
%%   		       end
%%   		   end).
-define(MFA_debug, fun(_, _, _) -> ok end).

%%-define(call_or_enter_debug, fun(X, Y) -> io:format(X, Y) end).
-define(call_or_enter_debug, fun(_, _) -> ok end).

%%todo snodd
-define(TAG_IMMED1_SIZE, 4).

-define(BITS, (hipe_rtl_arch:word_size() bsl 3) - ?TAG_IMMED1_SIZE).
-define(FIXNUM_UPPER, ((1 bsl (?BITS - 1)) - 1)).
-define(FIXNUM_LOWER, -(1 bsl (?BITS - 1))).
-define(MAX_BYTE, 255).
-define(MAX_CHAR, 16#10ffff).

%%-define(DEBUG, false).

-define(DO_RANGE_TEST, true).

-ifdef(DO_RANGE_TEST).
-export([test/0]).
-else.
-define(NO_UNUSED, true).
-endif.

%% This record is used when returning information
-record(range_info, {live_labels, 
		     in_label_range_trees,
		     out_label_range_trees,
		     return_points,
		     warn
		    }).	

%% This record is used by the range analyser
-record(info_struct, {worklist, 
		      phi_values=gb_trees:empty(), 
		      range_trees=gb_trees:empty(),
		      pred_trees=gb_trees:empty(),
		      current_range_tree=gb_trees:empty(),
		      current_label,
		      is_recursive=false,
		      current_mfa,
		      current_mfa_not_done=false,
		      label_counters=gb_trees:empty(),
		      return_vars=[],
		      predmap,
		      liveness,
		      live_labels=gb_sets:empty(),
		      startlabel,
		      wideningvalues=[posinf, neginf], 
		      server,
		      warn
		     }).

%% This is the representation of a range.
-record(var_range, {var_name,
		    range=empty,
		    other
		   }).

%%
%% Init
%%
%% Initializes the analysis
%%

init(IC, Options, Server, MFA) ->  
  %%io:format("analysing ~p ~n", [MFA]),
  %%hipe_icode_pp:pp(hipe_icode_cfg:cfg_to_linear(IC)),
  case info_struct__init(IC, Server, Options, MFA) of
    break ->
      none;
    Info ->
      Info2 = analyse_icode(IC, Info),
      case info_struct__current_mfa_not_done(Info2) of 
	true ->
	  server__update_return_value(Info2),
	  not_fixpoint;
	false ->
	  server__update_return_value(Info2), % I Know :)
	  Range_info = range_info_from_info_struct(Info2),	
	  %% Specialization
	  SpecIC = specialize_IC(IC, Range_info),
	  %% Optional annotation phase controlled by a compiler option
	  case proplists:get_bool(icode_range_analysis_annotate, Options) of
	    true ->
	      NewIC = annotate_IC(SpecIC, Range_info),
	      print_icode_to_file(NewIC, Info2);
	    false ->
	      ok
	  end,
	  case proplists:get_bool(icode_range_analysis_insn_count, Options) of
	    true ->
	      Old = hipe_icode_instruction_counter:cfg(IC, MFA, Options),
	      New = hipe_icode_instruction_counter:cfg(SpecIC, MFA, Options),
	      %%io:format("Old insn count ~p ~n", [gb_trees:to_list(Old)]),
	      hipe_icode_instruction_counter:compare(MFA, Old, New);
	    false ->
	      ok
	  end,	  
	  SpecIC 
      end
  end.

%%
%% Server
%%
%% Handles communication with the information server
%%

server__update_return_value(Info) ->
  Return_range = return_range(Info),
  Return_range_is_not_set = var_range__is_empty(Return_range) andalso var_range__is_not_other(Return_range),
  MFA = info_struct__current_mfa(Info),
  Not_done = info_struct__current_mfa_not_done(Info),
  Server = info_struct__server(Info),
  ?MFA_debug(MFA, "return range", Return_range),
  %%io:format("MFA ~p ~p ~n", [MFA, Return_range]),
  if not Return_range_is_not_set ->
      Wideningvalues = info_struct__wideningvalues(Info),
      Fun = fun (MessageTree) ->
		Key = {MFA, return_range},
		{State, Prev_return_range} = 
		  case gb_trees:lookup(Key, MessageTree) of
		    none ->
		      {0, range_init(return_range, empty, false)};
		    {value, {Lookup_return_range, Prev_state}} ->
		      {Prev_state, Lookup_return_range}
		  end,
		Fixed_return_range = 
		  if State > ?FUNCTION_FIXPOINT_DEPTH ->
		      range_widening(Prev_return_range, Return_range, 
				     Wideningvalues);
		     true ->
		      Return_range
		  end, 
		Is_not_updated = var_range__is_equal(Fixed_return_range, 
						     Prev_return_range),
		if Is_not_updated -> 
		    MessageTree;
		   true -> 
		    gb_trees:enter(Key, {Fixed_return_range, State + 1}, 
				   MessageTree)
		end
	    end,
      Server ! {self(), {transaction, Fun}};
     not Not_done ->
      Fun = fun(MessageTree) ->
		Key = {MFA, return_range},
		Any = range_init(return_range, {neginf, posinf}, true),
		case gb_trees:lookup(Key, MessageTree) of
		  none ->
		    %%io:format("no returnpoints ~p ~n", [MFA]),
		    gb_trees:enter(Key, {Any, 1}, 
				   MessageTree);
		  {value, _Val} ->
		    MessageTree
		end
	    end,
      Server ! {self(), {transaction, Fun}};
     true ->
      ok
  end.

server__update_call_args(MFA, Args, Info) -> %% TODO Needs comments
  Server = info_struct__server(Info),
  Server ! {self(), {load, message, {MFA, args}}},
  Rename_fun = fun(Arg) -> 
		   var_range__copy(get_range_from_arg(Arg, Info), param) 
	       end,
  receive
    none ->
      Lookup_state = 0,
      Args_updated = true,
      Insert_args = lists:map(Rename_fun, Args);
    {value, {Lookup_args, Lookup_state}} when is_integer(Lookup_state) ->
      %% io:format("Lookup_args ~p ~n MFA ~p ~n", [Lookup_args, MFA]),
      Arg_ranges = lists:map(Rename_fun, Args), %% this isn't needed
      Tuple_args_list = lists:zipwith(fun(X, Y) -> [X,Y] end,
				      Arg_ranges, Lookup_args),
      %% io:format("Tuple ~p ~n", [Tuple_args_list]),
      Union_args = lists:map(fun(Ranges) -> range_union(param, Ranges) end,
			     Tuple_args_list),
      %% io:format("Lookup state ~p ~n", [Lookup_state]),
      Insert_args = 
	if Lookup_state > ?FUNCTION_FIXPOINT_DEPTH ->
	    Widening_range_list = lists:zip(Lookup_args, Union_args),
	    Wideningvalues = info_struct__wideningvalues(Info),
	    Widened_ranges = 
	      lists:map(
		fun({Old_range, New_range}) ->
		    range_widening(Old_range, New_range, Wideningvalues)
		end,
		Widening_range_list),
	    %% io:format("New_wided ~p ~n", [R]),
	    Widened_ranges;
	   true ->
	    Union_args
	end,
      Range_tuple_list = lists:zip(Insert_args, Lookup_args),
      Args_updated = lists:foldl(fun({Range1, Range2}, Bool) ->
				     (Range1 =/= Range2) or Bool
				 end,
				 false,
				 Range_tuple_list)
  end,
  New_info =
    if Args_updated ->
	%%?not_done_debug("server_update_args break ~n", []),
	Server ! {self(), {message, {MFA, args}, {Insert_args, Lookup_state + 1}}},
	info_struct__set_current_mfa_not_done(Info, true);
       true ->
	Info
    end,
  New_info.


%%--------------------------------------------------------------------------
%% Icode helper functions
%%--------------------------------------------------------------------------

unannotate_var(An_var) ->
  case hipe_icode:is_annotated_var(An_var) of
    true ->
      hipe_icode:unannotate_var(An_var);
    false ->
      An_var
  end.

name_from_icode_var(An_var) ->
  Var = unannotate_var(An_var),
  case hipe_icode:is_var(Var) of
    true ->
      hipe_icode:var_name(Var);
    false ->
      case Var of 
	{reg, N} ->
	  {reg, N};
	{const, _} ->
	  const;
	_ ->
	  {f, hipe_icode:fvar_name(Var)}
      end
      %% constants??
  end.

get_range_from_args(Arglist, Info) ->
  lists:map(fun (Arg) -> get_range_from_arg(Arg, Info) end, Arglist).

get_range_from_arg(Arg, Info) ->
  UnannoArg = unannotate_var(Arg),
  case hipe_icode:is_const(UnannoArg) of
    true ->
      Value = hipe_icode:const_value(UnannoArg),
      case is_integer(Value) of
	true ->
	  range_init(const, {Value, Value}, false);
	false ->
	  range_init(const, empty, true)
      end;
    false -> % It's a variable
      case hipe_icode:is_fvar(Arg) of
	true ->
	  range_init(Arg, empty, true);
	false ->	
	  Var_name = name_from_icode_var(UnannoArg),
	  info_struct__get_range(Var_name, Info)
      end
  end.

int_range_from_number_val(Number) ->
  case Number of 
    any ->
      {neginf, posinf};
    N when is_integer(N) ->
      {N, N};
    none ->
      empty
  end.

int_range_from_number_vals([]) -> empty;
int_range_from_number_vals([First_number|Numbers]) ->
  The_union =
    fun(Number_val, Acc) ->
	case Acc of
	  {Min2, Max2} ->
	    case int_range_from_number_val(Number_val) of
	      {Min1, Max1} ->
		New_min = inf_min([Min1, Min2]),
		New_max = inf_max([Max1, Max2]),
		{New_min, New_max};
	      empty ->
		{Min2, Max2}
	    end;
	  empty ->
	    case int_range_from_number_val(Number_val) of
	      {Min1, Max1} ->
		{Min1, Max1};
	      empty ->
		empty
	    end
	end
    end,
  lists:foldl(The_union, int_range_from_number_val(First_number), Numbers);
int_range_from_number_vals(Number) ->
  int_range_from_number_val(Number).

get_range_from_annotation(Arg_info, Key) ->
  Is_byte = erl_types:t_is_byte(Arg_info),
  Is_char = erl_types:t_is_char(Arg_info),
  Is_integer = erl_types:t_is_integer(Arg_info),
  {Int_range, Other} = 
    if Is_byte ->
	{{0, ?MAX_BYTE}, false};
       Is_char ->
	{{0, ?MAX_CHAR}, false};
       Is_integer ->
	{{neginf, posinf}, false};
       true ->
	Number_vals = erl_types:t_number_vals(Arg_info),
	Arg = 
	  case Arg_info of 
	    [_|_] ->
	      [erl_types:t_integer()|Arg_info];
	    _ ->
	      [erl_types:t_integer(),Arg_info]
	  end,
	Is_only_int = erl_types:t_is_integer(erl_types:t_sup(Arg)),
	{int_range_from_number_vals(Number_vals), not Is_only_int} 
    end,
  range_init(Key, Int_range, Other).

keep_vars(Vars) ->
  [V || V <- Vars, hipe_icode:is_var(unannotate_var(V))].

dont_keep_vars(Vars)->
  [V || V <- Vars, not hipe_icode:is_var(unannotate_var(V))].

defines(I) ->
  keep_vars(hipe_icode:defines(I)).

uses(I) ->
  keep_vars(hipe_icode:uses(I)).

consts(I) ->
  dont_keep_vars(hipe_icode:args(I)).

%%
%% Icode analysis
%%
%% Propagates range information using Icode.
%%

analyse_icode(IC, Info) ->
  {Work, Info2} = info_struct__get_work(Info),
  case Work of
    {value, Label} ->
      case info_struct__set_new_current_tree(Label, Info2) of
	break ->
	  analyse_icode(IC, Info2);
	Info3 ->
	  %% io:format("Analysing ~p ~n", [Label]),
	  BB = hipe_icode_cfg:bb(IC, Label),
	  Code = hipe_bb:code(BB),
	  %% hipe_icode_pp:pp_block(Code),
	  Info4 = analyse_BB(Code, Info3),
	  analyse_icode(IC, Info4)