dialyzer_icode.erl

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

%% -*- erlang-indent-level: 2 -*-
%%--------------------------------------------------------------------
%% ``The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved via the world wide web at http://www.erlang.org/.
%% 
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%% 
%% Copyright 2006, Tobias Lindahl and Kostis Sagonas
%% 
%%     $Id$
%%

%%%-------------------------------------------------------------------
%%% File    : dialyzer_icode.erl
%%% Author  : Tobias Lindahl <[e-mail]>
%%% Description : 
%%%
%%% Created : 15 Apr 2005 by Tobias Lindahl <[e-mail]>
%%%-------------------------------------------------------------------
-module(dialyzer_icode).

-export([run_analysis/5]).

-include("hipe_icode.hrl").
-include("dialyzer.hrl").
-define(TYPE_DEPTH, 3).

-import(erl_types, [t_any/0, t_atom/1, t_atom/0, t_atom_vals/1,
		    t_binary/0, t_bool/0, t_cons/0, t_constant/0, 
		    t_pos_improper_list/0,
		    t_float/0, t_from_term/1, t_fun/0, t_fun/1, t_fun/2,
		    t_fun_args/1, t_fun_arity/1,
		    t_fun_range/1,t_inf/2, t_inf_lists/2, 
		    t_integer/0,
		    t_integer/1, t_is_atom/1, t_is_atom/2, 
		    t_is_any/1, t_is_binary/1,
		    t_is_bool/1, t_is_cons/1, t_is_constant/1,
		    t_is_pos_improper_list/1, t_is_equal/2, t_is_float/1,
		    t_is_fun/1, t_is_integer/1, t_is_number/1,
		    t_is_list/1, t_is_nil/1, t_is_port/1, t_is_pid/1,
		    t_is_ref/1, t_is_subtype/2, 
		    t_is_tuple/1,
		    t_is_none/1, t_limit/2, t_list/0, t_nil/0,
		    t_number/0, t_number/1, t_number_vals/1, t_pid/0,
		    t_port/0, t_product/1, t_ref/0, t_subtract/2, 
		    t_sup/1, t_sup/2,
		    t_to_string/1, t_tuple/0, t_tuple/1,
		    t_tuple_arities/1, t_none/0]).


-record(state, {succmap, predmap, info_map, cfg, liveness, arg_types,
		created_funs=[]}).

%%-define(DEBUG, true).

run_analysis(Cfg, IcodeFun, Plt, NoWarnUnused, SendWarn) ->
  OldSig = init_mfa_info(IcodeFun, Plt),
  State = analyze(Cfg),
  pp(State, IcodeFun, "Pre-specialization"),
  NewState = cfg_loop(State),
  pp(NewState, IcodeFun, "Post-specialization"),
  Warnings =
    case SendWarn of
      true -> warn_on_type_errors(Cfg, State, NewState, NoWarnUnused, IcodeFun);
      false -> []
    end,
  return(NewState, IcodeFun, OldSig, Warnings).

cfg_loop(State) ->
  Labels = hipe_icode_cfg:reverse_postorder(state__cfg(State)),  
  simplify_controlflow(Labels, State).


return(State, IcodeFun, OldSig, Warnings) ->
  Labels = hipe_icode_cfg:labels(state__cfg(State)),
  {IcodeReturn0, _, _} = find_return_type(Labels, State),
  IcodeArgs = State#state.arg_types,
  case t_is_none(IcodeReturn0) of
    true ->
      IcodeReturn = t_any();
    false ->
      IcodeReturn = IcodeReturn0
  end,
  
  NewArgs =  
    case t_fun_args(OldSig) of
      any -> IcodeArgs;
      PltArgs -> PltArgs
    end,
  
  Fixpoint =   
    case t_is_equal(IcodeReturn, t_fun_range(OldSig)) of
      true -> fixpoint;
      false -> not_fixpoint
    end,
  {Fixpoint, {IcodeFun, IcodeReturn, NewArgs}, Warnings}.


%% _________________________________________________________________
%% 
%% Global type analysis on the whole function. Demands that the code
%% is in SSA-form. When we encounter a phi-node, the types of the
%% arguments are joined. At the end of a block the information out is
%% joined with the current information in for all _valid_ successors,
%% that is, of all successors that actually can be reached. If the
%% join produces new information in for the successor, this
%% information is added to the worklist.
%%

analyze(Cfg) ->
  %%hipe_icode_cfg:pp(Cfg),
  State1 = new_state(Cfg),
  analyze_blocks(State1).

analyze_blocks(State) ->
  Work = init_work(State),
  analyze_blocks(Work, State).

analyze_blocks(Work, State) ->
  case get_work(Work) of
    fixpoint ->
      State;
    {Label, NewWork} ->
      Info = state__info_in(State, Label),
      {NewState2, NewLabels} = analyze_block(Label, Info, State),
      NewWork2 = add_work(NewWork, NewLabels),
      analyze_blocks(NewWork2, NewState2)
  end.
  
analyze_block(Label, InfoIn, State) ->
  %%io:format("Handling ~w\n", [Label]),
  BB = state__bb(State, Label),
  Code = hipe_bb:butlast(BB),
  Last = hipe_bb:last(BB),
  InfoOut = analyze_insns(Code, InfoIn),
  NewState = state__info_out_update(State, Label, InfoOut),

  case Last of
    #'if'{} ->
      UpdateInfo = do_if(Last, InfoOut),
      do_updates(NewState, UpdateInfo);
    #type{} ->
      UpdateInfo = do_type(Last, InfoOut),
      do_updates(NewState, UpdateInfo);
    #switch_tuple_arity{} ->
      UpdateInfo = do_switch_tuple_arity(Last, InfoOut),
      do_updates(NewState, UpdateInfo);
    #switch_val{} ->
      UpdateInfo = do_switch_val(Last, InfoOut),
      do_updates(NewState, UpdateInfo);
    #call{} ->
      {DstType, NewArgTypes} = do_call(Last, InfoOut),
      NewInfoOut = enter_defines(Last, DstType, InfoOut),
      NewState1 = state__info_out_update(NewState, Label, NewInfoOut),
      ContInfo = enter_lists(args(Last), NewArgTypes, NewInfoOut),
      Cont = hipe_icode:call_continuation(Last),
      Fail = hipe_icode:call_fail_label(Last),
      UpdateInfo =
	case Fail of
	  [] ->
	    case call_always_fails(Last, InfoOut) of
	       true ->
		[];
	      false ->
		[{Cont, ContInfo}]
	    end;
	  _ ->
	    case call_always_fails(Last, InfoOut) of
	      true ->
		[{Fail, NewInfoOut}];
	      false ->
		Fun = hipe_icode:call_fun(Last),
		case hipe_icode_primops:fails(Fun) of
		  true ->
		    [{Cont, ContInfo}, {Fail, NewInfoOut}];
		  false ->
		    [{Cont, ContInfo}]
		end
	    end
	end,
      do_updates(NewState1, UpdateInfo);
    _ ->
      UpdateInfo = [{X, InfoOut}||X<-state__succ(NewState, Label)],
      do_updates(NewState, UpdateInfo)
  end.

analyze_insns([I|Insns], Info) ->
  NewInfo = analyze_insn(I, Info),
  analyze_insns(Insns, NewInfo);
analyze_insns([], Info) ->
  Info.

analyze_insn(I, Info) ->
  case I of
    #move{} ->
      do_move(I, Info);
    #call{} ->
      {DstType, NewArgTypes} = do_call(I, Info),
      NewInfo = enter_defines(I, DstType, Info),
      enter_lists(args(I), NewArgTypes, NewInfo);
    #phi{} ->
      Type = t_limit(join_list(args(I), Info), ?TYPE_DEPTH),
      enter_defines(I, Type, Info);
    #begin_handler{} ->
      enter_defines(I, t_any(), Info);
    _ ->
      %% Just an assert
      case defines(I) of
	[] -> Info;
	_ -> erlang:fault({"Instruction with destination not analyzed", I})
      end
  end.

do_move(I, Info) ->
  %% Can't use uses/1 since we must keep constants.
  [Src] = args(I),
  case hipe_icode:is_const(Src) of
    true -> 
      enter_defines(I, const_type(Src), Info);
    false ->
      %% Make the destination point to the source.
      enter_defines(I, Src, Info)
  end.

do_call(I, Info) ->
  Fun = hipe_icode:call_fun(I),
  CallType = hipe_icode:call_type(I),
  call_or_enter_type(I, Fun, args(I), Info, CallType).

call_or_enter_type(_I, Fun, Args, Info, primop) ->
  ArgTypes = lookup_list(Args, Info),
  DstType = primop_type(Fun, ArgTypes),      
  case t_fun_args(find_signature_primop(Fun, length(ArgTypes))) of
    any -> {DstType, ArgTypes};
    ArgConstr -> {DstType, t_inf_lists(ArgTypes, ArgConstr)}
  end;
call_or_enter_type(I, MFA, Args, Info, OtherType) when OtherType =:= local;
						       OtherType =:= remote ->
  ArgTypes = lookup_list(Args, Info),
  PltSig = find_signature(MFA, ArgTypes),
  {M, F, A} = MFA,
  BifType = erl_bif_types:type(M, F, A, ArgTypes),
  %% XXX: This should be removed when the annotated form is not used anymore.
  AnnotatedType =
    case I of
      #call{} ->
	case hipe_icode:call_dst_type(I) of
	  [] -> t_any();
	  T -> 
	    %% Make sure that the core type pass has not 
	    %% annotated this with none()
	    case t_is_none(T) of
	      true -> t_any();
	      false -> T
	    end
	end;
      #enter{} ->
	t_any()
    end,
  DstType = t_inf(AnnotatedType, t_inf(BifType, t_fun_range(PltSig))),
  case t_fun_args(PltSig) of
    any ->
      {DstType, ArgTypes};
    ArgConstr ->      
      NewArgTypes = t_inf_lists(ArgTypes, ArgConstr),
      case any_is_none(NewArgTypes) of
	true -> {t_none(), NewArgTypes};
	false -> {DstType, NewArgTypes}
      end
  end.

do_if(I, Info) ->
  %%% XXX: Could probably do better than this.
  TrueLab = hipe_icode:if_true_label(I),
  FalseLab = hipe_icode:if_false_label(I),
  case hipe_icode:if_args(I) of
    [Arg1, Arg2] = Args ->
      [Type1, Type2] = lookup_list(Args, Info),
      %% io:format("Type1 = ~w, Type2 = ~w\n", [Type1, Type2]),
      case t_is_none(Type1) orelse t_is_none(Type2) of
	true ->
	  [{TrueLab, Info}, {FalseLab, Info}];
	false ->
	  Inf = t_inf(Type1, Type2),
	  case hipe_icode:if_op(I) of
	    '=:='->
	      case t_is_none(Inf) of
		true -> [{FalseLab, Info}];
		false -> [{TrueLab, enter(Arg1, Inf, enter(Arg2, Inf, Info))}, 
			  {FalseLab, Info}]
	      end;
	    '=/=' ->
	      case t_is_none(Inf) of
		true -> 
		  [{TrueLab, Info}];
		false ->
		  [{FalseLab, enter(Arg1, Inf, enter(Arg2, Inf, Info))}, 
		   {TrueLab, Info}]
	      end;
	    Op ->
	      Eval = erl_bif_types:type(erlang, Op, 2, [Type1, Type2]),
	      case t_is_atom(true, Eval) of
		true -> [{TrueLab, Info}];
		false ->
		  case t_is_atom(false, Eval) of
		    true -> [{FalseLab, Info}];
		    false -> [{TrueLab, Info}, {FalseLab, Info}]
		  end
	      end
	  end
      end;
    _ ->
      %% Only care for binary if:s
      [{TrueLab, Info}, {FalseLab, Info}]
  end.

do_type(I, Info) ->
  case args(I) of
    [Var] -> do_type(I, Info, Var);
    [Var1,Var2] -> do_type2(I, Info, Var1, Var2)
  end.

do_type2(I, Info, FunVar, ArityVar) -> % function2(Fun,Arity)
  %% Just for sanity.
  function2 = hipe_icode:type_type(I),  
  FunType = lookup(FunVar, Info),
  ArityType = lookup(ArityVar, Info),
  TrueLab = hipe_icode:type_true_label(I),
  FalseLab = hipe_icode:type_false_label(I),
  case combine_test(test_type(function, FunType), 
		    test_type(integer, ArityType)) of
    true ->
      Arity = t_fun_arity(FunType),
      case t_number_vals(ArityType) of
	any ->
	  if Arity =/= any -> [{TrueLab, Info}, {FalseLab, Info}];
	     true -> [{TrueLab, enter(ArityVar, t_from_term(Arity), Info)},
		      {FalseLab, Info}]
	  end;
	[Arity] ->
	  [{TrueLab, Info}];
	List ->
	  case lists:member(Arity, List) of
	    true ->
	      T = t_from_term(Arity), 
	      [{TrueLab, enter(ArityVar, T, Info)},
	       {FalseLab, enter(ArityVar, t_subtract(ArityType, T), Info)}];
	    false ->
	      [{FalseLab, Info}]
	  end
      end;
    false ->
      [{FalseLab, Info}];
    maybe ->
      GenTrueArity = t_inf(t_integer(), ArityType),
      GenTrueFun = t_inf(t_fun(), FunType),
      case {t_number_vals(GenTrueArity), t_fun_arity(GenTrueFun)} of
	{any, any} -> 
	  TrueInfo = enter_lists([FunVar, ArityVar], 
				 [GenTrueFun, GenTrueArity], Info),
	  [{TrueLab, TrueInfo}, {FalseLab, Info}];
	{any, Arity} when is_integer(Arity) ->
	  TrueInfo = enter_lists([FunVar, ArityVar], 
				 [GenTrueFun, t_integer(Arity)], Info),
	  [{TrueLab, TrueInfo}, {FalseLab, Info}];
	{[Val], any} when is_integer(Val) ->
	  TrueInfo = enter_lists([FunVar, ArityVar], 
				 [t_inf(GenTrueFun, t_fun(Val, t_any())),
				  GenTrueArity], Info),
	  [{TrueLab, TrueInfo}, {FalseLab, Info}];
	{Vals, any} when is_list(Vals) ->
	  %% The function type gets widened when we have more than one arity.
	  TrueInfo = enter_lists([FunVar, ArityVar], 
				 [GenTrueFun, GenTrueArity], Info),
	  [{TrueLab, TrueInfo}, {FalseLab, Info}];
	{Vals, Arity} when is_list(Vals), is_integer(Arity) ->
	  case lists:member(Arity, Vals) of
	    false ->
	      [{FalseLab, Info}];
	    true ->
	      TrueInfo = enter_lists([FunVar, ArityVar], 
				     [GenTrueFun, t_integer(Arity)], Info),
	      [{TrueLab, TrueInfo}, {FalseLab, Info}]
	  end
      end
  end.

combine_test(true, true) -> true;
combine_test(false, _)   -> false;
combine_test(_, false)   -> false;
combine_test(_, _)       -> maybe.


do_type(I, Info, Var) ->
  TrueLab = hipe_icode:type_true_label(I),
  FalseLab = hipe_icode:type_false_label(I),
  None = t_none(),
  
  case lookup(Var, Info) of
    None ->
      [{TrueLab, Info}, {FalseLab, Info}];
    VarInfo ->
      case hipe_icode:type_type(I) of
	cons ->
	  test_cons_or_nil(t_cons(), Var, VarInfo, TrueLab, FalseLab, Info);
	nil ->
	  test_cons_or_nil(t_nil(), Var, VarInfo, TrueLab, FalseLab, Info);
	{atom, A} ->
	  test_number_or_atom(fun(X) -> t_atom(X) end,
			      A, Var, VarInfo, {atom, A}, 
			      TrueLab, FalseLab, Info);
	{integer, N} ->
	  test_number_or_atom(fun(X) -> t_number(X) end, 
			      N, Var, VarInfo, {integer, N}, 
			      TrueLab, FalseLab, Info);
	{record, Atom, Size} ->
	  test_record(Atom, Size, Var, VarInfo, TrueLab, FalseLab, Info);
	Other ->
	  case t_is_any(VarInfo) of
	    true ->
	      TrueType = t_inf(true_branch_info(Other), VarInfo),
	      TrueInfo = enter(Var, TrueType, Info),
	      [{TrueLab, TrueInfo}, {FalseLab, Info}];
	    false ->