The R13B03 release.OTP_R13B03

1 files changed, 474 insertions, 0 deletions

diff --git a/lib/hipe/icode/hipe_icode_exceptions.erl b/lib/hipe/icode/hipe_icode_exceptions.erl
new file mode 100644
index 0000000000..787fb05415
--- /dev/null
+++ b/lib/hipe/icode/hipe_icode_exceptions.erl
@@ -0,0 +1,474 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2004-2009. All Rights Reserved.
+%% 
+%% 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 online 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.
+%% 
+%% %CopyrightEnd%
+%%
+%% ====================================================================
+%%  Filename : 	hipe_icode_exceptions.erl
+%%  Module   :	hipe_icode_exceptions
+%%  Purpose  :  Rewrite calls in intermediate code to use Continuation
+%%              and Fail-To labels.
+%%
+%%		Catch-instructions work as follows:
+%%                - A begin_try(FailLabel) starts a catch-region which
+%%                  is ended by a corresponding end_try(FailLabel).
+%%                - The handler begins with a begin_handler(FailLabel).
+%%
+%%		However, the begin/end instructions do not always appear
+%%		as parentheses around the section that they protect (in
+%%		linear Beam/Icode). Also, different begin_catch
+%%		instructions can reach the same basic blocks (which may
+%%		raise exceptions), due to code compation optimizations
+%%		in the Beam compiler, even though they have different
+%%		handlers. Because of this, a data flow analysis is
+%%		necessary to find out which catches may reach which
+%%		basic blocks. After that, we clone basic blocks as
+%%		needed to ensure that each block belongs to at most one
+%%		unique begin_catch. The Beam does not have this problem,
+%%		since it will find the correct catch-handler frame
+%%		pushed on the stack. (Note that since there can be no
+%%		tail-calls within a catch region, our dataflow analysis
+%%		for finding all catch-stacks is sure to terminate.)
+%%
+%%		Finally, we can remove all special catch instructions
+%%		and rewrite calls within catch regions to use explicit
+%%		fail-to labels, which is the main point of all this.
+%%		Fail labels that were set before this pass are kept.
+%%		(Note that calls that have only a continuation label do
+%%		not always end their basic blocks. Adding a fail label
+%%		to such a call can thus force us to split the block.)
+%%
+%%  Notes    :  As of November 2003, primops that do not fail in the 
+%%              normal sense are allowed to have a fail-label even
+%%              before this pass. (Used for the mbox-empty + get_msg
+%%              primitive in receives.)
+%%
+%%              Native floating point operations cannot fail in the
+%%              normal sense. Instead they throw a hardware exception
+%%              which will be caught by a special fp check error
+%%              instruction. These primops do not need a fail label even
+%%              in a catch. This pass checks for this with
+%%              hipe_icode_primops:fails/1. If a call cannot fail, no
+%%              fail label is added.
+%%
+%%              Explicit fails (exit, error and throw) inside
+%%              a catch have to be handled. They have to build their
+%%              exit value and jump directly to the catch handler. An
+%%              alternative solution would be to have a new type of
+%%              fail instruction that takes a fail-to label...
+%%
+%%  CVS:
+%%    $Id$
+%% ====================================================================
+
+-module(hipe_icode_exceptions).
+
+-export([fix_catches/1]).
+
+-include("hipe_icode.hrl").
+-include("../flow/cfg.hrl").
+
+%%----------------------------------------------------------------------------
+
+-spec fix_catches(#cfg{}) -> #cfg{}.
+
+fix_catches(CFG) ->
+  {Map, State} = build_mapping(find_catches(init_state(CFG))),
+  hipe_icode_cfg:remove_unreachable_code(get_cfg(rewrite(State, Map))).
+
+%% This finds the set of possible catch-stacks for each basic block
+
+find_catches(State) ->
+  find_catches(get_start_labels(State),
+	       clear_visited(clear_changed(State))).
+
+find_catches([L|Ls], State0) ->
+  case is_visited(L, State0) of
+    true ->
+      find_catches(Ls, State0);
+    false ->
+      State1 = set_visited(L, State0),
+      Code = get_bb_code(L, State1),
+      Cs = get_new_catches_in(L, State1),
+      State2 = set_catches_in(L, Cs, State1),  % memorize
+      Cs1 = catches_out(Code, Cs),
+      Ls1 = get_succ(L, State2) ++ Ls,
+      Cs0 = get_catches_out(L, State2),
+      if Cs1 =:= Cs0 ->
+	  find_catches(Ls1, State2);
+	 true ->
+	  State3 = set_catches_out(L, Cs1, State2),
+	  find_catches(Ls1, set_changed(State3))
+      end
+  end;
+find_catches([], State) ->
+  case is_changed(State) of
+    true ->
+      find_catches(State);
+    false ->
+      State
+  end.
+
+catches_out([I|Is], Cs) ->
+  catches_out(Is, catches_out_instr(I, Cs));
+catches_out([], Cs) ->
+  Cs.
+
+catches_out_instr(I, Cs) ->
+  case I of
+    #icode_begin_try{} ->
+      Id = hipe_icode:begin_try_label(I),
+      push_catch(Id, Cs);
+    #icode_end_try{} ->
+      pop_catch(Cs);
+    #icode_begin_handler{} ->
+      pop_catch(Cs);
+    _ ->
+      Cs
+  end.
+
+
+%% This builds the mapping used for cloning
+
+build_mapping(State) ->
+  build_mapping(get_start_labels(State), clear_visited(State),
+		new_mapping()).
+
+build_mapping([L|Ls], State0, Map) ->
+  case is_visited(L, State0) of
+    true ->
+      build_mapping(Ls, State0, Map);
+    false ->
+      State1 = set_visited(L, State0),
+      Cs = list_of_catches(get_catches_in(L, State1)),  % get memorized
+      {Map1, State2} = map_bb(L, Cs, State1, Map),
+      Ls1 = get_succ(L, State2) ++ Ls,
+      build_mapping(Ls1, State2, Map1)
+  end;
+build_mapping([], State, Map) ->
+  {Map, State}.
+
+map_bb(_L, [_C], State, Map) ->
+  {Map, State};
+map_bb(L, [C | Cs], State, Map) ->
+  %% This block will be cloned - we need to create N-1 new labels.
+  %% The identity mapping will be used for the first element.
+  Map1 = new_catch_labels(Cs, L, Map),
+  State1 = set_catches_in(L, single_catch(C), State),  % update catches in
+  Code = get_bb_code(L, State1),
+  State2 = clone(Cs, L, Code, State1, Map1),
+  {Map1, State2}.
+
+clone([C | Cs], L, Code, State, Map) ->
+  Ren = get_renaming(C, Map),
+  L1 = Ren(L),
+  State1 = set_bb_code(L1, Code, State),
+  State2 = set_catches_in(L1, single_catch(C), State1),  % set catches in
+  clone(Cs, L, Code, State2, Map);
+clone([], _L, _Code, State, _Map) ->
+  State.
+
+new_catch_labels([C | Cs], L, Map) ->
+  L1 = hipe_icode:label_name(hipe_icode:mk_new_label()),
+  Map1 = set_mapping(C, L, L1, Map),
+  new_catch_labels(Cs, L, Map1);
+new_catch_labels([], _L, Map) ->
+  Map.
+
+
+%% This does all the actual rewriting and cloning.
+
+rewrite(State, Map) ->
+  rewrite(get_start_labels(State), clear_visited(State), Map).
+
+rewrite([L|Ls], State0, Map) ->
+  case is_visited(L, State0) of
+    true ->
+      rewrite(Ls, State0, Map);
+    false ->
+      State1 = set_visited(L, State0),
+      Code = get_bb_code(L, State1),
+      Cs = list_of_catches(get_catches_in(L, State1)),  % get memorized
+      State2 = rewrite_bb(L, Cs, Code, State1, Map),
+      Ls1 = get_succ(L, State2) ++ Ls,
+      rewrite(Ls1, State2, Map)
+  end;
+rewrite([], State, _Map) ->
+  State.
+
+rewrite_bb(L, [C], Code, State, Map) ->
+  {Code1, State1} = rewrite_code(Code, C, State, Map),
+  set_bb_code(L, Code1, State1).
+
+rewrite_code(Is, C, State, Map) ->
+  rewrite_code(Is, C, State, Map, []).
+
+rewrite_code([I|Is], C, State, Map, As) ->
+  [C1] = list_of_catches(catches_out_instr(I, single_catch(C))),
+  case I of
+    #icode_begin_try{} ->
+      {I1, Is1, State1} = update_begin_try(I, Is, C, State, Map),
+      I2 = redirect_instr(I1, C, Map),
+      rewrite_code(Is1, C1, State1, Map, [I2 | As]);
+    #icode_end_try{} ->
+      rewrite_code(Is, C1, State, Map, As);
+    #icode_call{} ->
+      {I1, Is1, State1} = update_call(I, Is, C, State, Map),
+      I2 = redirect_instr(I1, C, Map),
+      rewrite_code(Is1, C1, State1, Map, [I2 | As]);
+    #icode_fail{} ->
+      {I1, Is1, State1} = update_fail(I, Is, C, State, Map),
+      I2 = redirect_instr(I1, C, Map),
+      rewrite_code(Is1, C1, State1, Map, [I2 | As]);
+    _ ->
+      I1 = redirect_instr(I, C, Map),
+      rewrite_code(Is, C1, State, Map, [I1 | As])
+  end;
+rewrite_code([], _C, State, _Map, As) ->
+  {lists:reverse(As), State}.
+
+redirect_instr(I, C, Map) ->
+  redirect_instr_1(I, hipe_icode:successors(I), get_renaming(C, Map)).
+
+redirect_instr_1(I, [L0 | Ls], Ren) ->
+  I1 = hipe_icode:redirect_jmp(I, L0, Ren(L0)),
+  redirect_instr_1(I1, Ls, Ren);
+redirect_instr_1(I, [], _Ren) ->
+  I.
+
+update_begin_try(I, Is, _C, State0, _Map) ->
+  L = hipe_icode:begin_try_successor(I),
+  I1 = hipe_icode:mk_goto(L),
+  {I1, Is, State0}.
+
+update_call(I, Is, C, State0, Map) ->
+  case top_of_stack(C) of
+    [] ->
+      %% No active catch. Assume cont./fail labels are correct as is.
+      {I, Is, State0};
+    L ->
+      %% Only update the fail label if the call *can* fail.
+      case hipe_icode_primops:fails(hipe_icode:call_fun(I)) of
+	true ->
+	  %% We only update the fail label if it is not already set.
+	  case hipe_icode:call_fail_label(I) of
+	    [] ->
+	      I1 = hipe_icode:call_set_fail_label(I, L),
+	      %% Now the call will end the block, so we must put the rest of
+	      %% the code (if nonempty) in a new block!
+	      if Is =:= [] ->
+		  {I1, Is, State0};
+		 true ->
+		  L1 = hipe_icode:label_name(hipe_icode:mk_new_label()),
+		  I2 = hipe_icode:call_set_continuation(I1, L1),
+		  State1 = set_bb_code(L1, Is, State0),
+		  State2 = set_catches_in(L1, single_catch(C), State1),
+		  State3 = rewrite_bb(L1, [C], Is, State2, Map),
+		  {I2, [], State3}
+	      end;
+	    _ when Is =:= [] ->
+	      %% Something is very wrong if Is is not empty here. A call
+	      %% with a fail label should have ended its basic block.
+	      {I, Is, State0}
+	  end;
+	false ->
+	  %% Make sure that the fail label is not set.
+	  I1 = hipe_icode:call_set_fail_label(I, []),
+	  {I1, Is, State0}
+      end
+  end.
+
+update_fail(I, Is, C, State, _Map) ->
+  case hipe_icode:fail_label(I) of
+    [] -> 
+      {hipe_icode:fail_set_label(I, top_of_stack(C)), Is, State};
+    _ ->
+      {I, Is, State}
+  end.
+
+
+%%---------------------------------------------------------------------
+%% Abstraction for sets of catch stacks.
+
+%% This is the bottom element
+no_catches() -> [].
+
+%% A singleton set
+single_catch(C) -> [C].
+
+%% A single, empty stack
+empty_stack() -> [].
+
+%% Getting the label to fail to
+top_of_stack([C|_]) -> C;
+top_of_stack([]) -> [].    % nil is used in Icode for "no label"
+
+join_catches(Cs1, Cs2) ->
+  ordsets:union(Cs1, Cs2).
+
+list_of_catches(Cs) -> Cs.
+
+%% Note that prepending an element to all elements in the list will
+%% preserve the ordering of the list, and will never make two existing
+%% elements become identical, so the list is still an ordset. 
+
+push_catch(L, []) ->
+  [[L]];
+push_catch(L, Cs) ->
+  push_catch_1(L, Cs).
+
+push_catch_1(L, [C|Cs]) ->
+  [[L|C] | push_catch_1(L, Cs)];
+push_catch_1(_L, []) ->
+  [].
+
+%% However, after discarding the head of all elements, the list
+%% is no longer an ordset, and must be processed.
+
+pop_catch(Cs) ->
+  ordsets:from_list(pop_catch_1(Cs)).
+
+pop_catch_1([[_|C] | Cs]) ->
+  [C | pop_catch_1(Cs)];
+pop_catch_1([]) ->
+  [].
+
+
+%%---------------------------------------------------------------------
+%% Mapping from catch-stacks to renamings on labels.
+
+new_mapping() ->
+  gb_trees:empty().
+
+set_mapping(C, L0, L1, Map) ->
+  Dict = case gb_trees:lookup(C, Map) of
+	   {value, Dict0} ->
+	     gb_trees:enter(L0, L1, Dict0);
+	   none ->
+	     gb_trees:insert(L0, L1, gb_trees:empty())
+	 end,
+  gb_trees:enter(C, Dict, Map).
+
+%% Return a label renaming function for a particular catch-stack
+
+get_renaming(C, Map) ->
+  case gb_trees:lookup(C, Map) of
+    {value, Dict} ->
+      fun (L0) ->
+	  case gb_trees:lookup(L0, Dict) of
+	    {value, L1} -> L1;
+	    none -> L0
+	  end
+      end;
+    none ->
+      fun (L0) -> L0 end
+  end.
+
+
+%%---------------------------------------------------------------------
+%% State abstraction
+
+-record(state, {cfg					:: #cfg{},
+		changed = false				:: boolean(),
+		succ					:: #cfg{},
+		pred					:: #cfg{},
+		start_labels				:: [icode_lbl(),...],
+		visited = hipe_icode_cfg:none_visited()	:: gb_set(),
+		out     = gb_trees:empty()		:: gb_tree(),
+		in      = gb_trees:empty()		:: gb_tree()
+	       }).
+
+init_state(CFG) ->
+  State = #state{cfg = CFG},
+  refresh_state_cache(State).
+
+refresh_state_cache(State) ->
+  CFG = State#state.cfg,
+  SLs = [hipe_icode_cfg:start_label(CFG)],
+  State#state{succ = CFG, pred = CFG, start_labels = SLs}.
+
+get_cfg(State) ->
+  State#state.cfg.
+
+get_start_labels(State) ->
+  State#state.start_labels.
+
+get_pred(L, State) ->
+  hipe_icode_cfg:pred(State#state.pred, L).
+
+get_succ(L, State) ->
+  hipe_icode_cfg:succ(State#state.succ, L).
+
+set_changed(State) ->
+  State#state{changed = true}.
+
+is_changed(State) ->
+  State#state.changed.
+
+clear_changed(State) ->
+  State#state{changed = false}.
+
+set_catches_out(L, Cs, State) ->
+  State#state{out = gb_trees:enter(L, Cs, State#state.out)}.
+
+get_catches_out(L, State) ->
+  case gb_trees:lookup(L, State#state.out) of
+    {value, Cs} -> Cs;
+    none -> no_catches()
+  end.
+
+set_catches_in(L, Cs, State) ->
+  State#state{in = gb_trees:enter(L, Cs, State#state.in)}.
+
+get_catches_in(L, State) ->
+  case gb_trees:lookup(L, State#state.in) of
+    {value, Cs} -> Cs;
+    none -> no_catches()
+  end.
+
+set_visited(L, State) ->
+  State#state{visited = hipe_icode_cfg:visit(L, State#state.visited)}.
+
+is_visited(L, State) ->
+  hipe_icode_cfg:is_visited(L, State#state.visited).
+
+clear_visited(State) ->
+  State#state{visited = hipe_icode_cfg:none_visited()}.
+
+get_bb_code(L, State) ->
+  hipe_bb:code(hipe_icode_cfg:bb(State#state.cfg, L)).
+
+set_bb_code(L, Code, State) ->
+  CFG = State#state.cfg,
+  CFG1 = hipe_icode_cfg:bb_add(CFG, L, hipe_bb:mk_bb(Code)),
+  refresh_state_cache(State#state{cfg = CFG1}).
+
+get_new_catches_in(L, State) ->
+  Ps = get_pred(L, State),
+  Cs = case lists:member(L, get_start_labels(State)) of
+	 true -> single_catch(empty_stack());
+	 false -> no_catches()
+       end,
+  get_new_catches_in(Ps, Cs, State).
+
+get_new_catches_in([P | Ps], Cs, State) ->
+  Cs1 = join_catches(Cs, get_catches_out(P, State)),
+  get_new_catches_in(Ps, Cs1, State);
+get_new_catches_in([], Cs, _) ->
+  Cs.
+
+%%---------------------------------------------------------------------